提出一种精确且确定的图像块描述符检索方法，仅需检查少量数据库项即可获得与暴力搜索一致的结果。
Exact and Deterministic Patch Descriptor Retrieval via Hierarchical Normalization
- 通过分层归一化将特征向量分为主成分和次成分，利用上界剪枝加速搜索
- 在Trevi和Halfdome数据集上实现12.7至13.7倍加速，仅0.4%样本需完整计算
- 结果完全确定，不受硬件或运行顺序影响，适合对精度要求高的场景
本文提出一种图像块描述符检索方法，能返回与穷举全向量搜索完全一致的最近邻，同时仅需评估数据库中极小部分条目，并且结果具有确定性：相同（数据库，查询）对在不同运行顺序、线程数或硬件下均产生相同结果。这与HNSW、IVF-PQ等近似最近邻方法形成对比，后者为提速牺牲了精确性且结果不一致。核心机制是分层归一化（HN）：将预归一化特征向量拆分为K维主成分（范数√(1-α)）和(128−K)维次成分（范数√α）。由于次成分内积受α限制（柯西-施瓦茨不等式），主成分相似度加α构成完整相似度的可接受上界。搜索先扫描所有条目的K维主成分，仅对无法剪枝的条目执行完整的128维计算——实现可证明的精确分支定界扫描。我们在UBC Patch数据集的notredame划分上训练修改后的HardNet，评估在trevi和halfdome上。采用缓存优化的数组结构布局，当K=8，α=1/32时，相比暴力128维搜索，Trevi和Halfdome分别提速13.7倍和12.7倍，仅有0.4%条目需完整评估。当K=16，α=1/8时，Trevi上FPR@95从0.0062升至0.0064，速度提升7.2倍，98.8%条目被跳过完整计算。
原文摘要 · Abstract (English)
We present a patch descriptor retrieval method that returns the exact nearest neighbour -- provably identical to exhaustive full-vector search -- while evaluating only a small fraction of the database, and does so deterministically: the same (database, query) pair always produces the same result, independent of run order, thread count, or hardware. This contrasts with approximate nearest-neighbour (ANN) approaches such as HNSW and IVF-PQ, which trade exactness for speed and may return different results across runs. The enabling mechanism is Hierarchical Normalization (HN): a normalisation scheme that splits the pre-normalisation feature vector into a K-dim major component (norm sqrt(1-alpha)) and a (128-K)-dim minor component (norm sqrt(alpha)). Since the minor inner product is bounded by alpha (Cauchy-Schwarz on the prescribed norms), the major similarity plus alpha is an admissible upper bound on the full similarity: the search scans the K-dim major component for all entries, then applies full 128-dim evaluation only to entries that cannot be pruned -- a provably exact branch-and-bound scan. We train HN-modified HardNet on the notredame split of the UBC patch dataset and evaluate on trevi and halfdome. With a cache-optimised Structure-of-Arrays layout and K=8, alpha=1/32, the search achieves 13.7x (trevi) / 12.7x (halfdome) speed-up over brute-force 128-dim search, with only 0.4% of entries requiring full evaluation. At K=16, alpha=1/8, FPR@95 rises from 0.0062 to 0.0064 on trevi at 7.2x speed-up, with 98.8% of entries bypassing full evaluation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。