在視覺定位這片技術戰場上，近年來一個奇怪的現象逐漸形成：盡管局部特征匹配理論上更適合精確定位，但研究者們卻越來越依賴全局嵌入技術。這種趨勢就像一場集體迷失，大家似乎不約而同地放棄了直接使用局部特征的可能性。然而，谷歌研究團隊最近的研究結果可能將重新洗牌這一領域。他們提出的約束近似最近鄰（CANN）算法，只用局部特征就能同時在外觀和幾何空間中搜索，不僅顯著超越了全局特征方法，還比使用局部特征聚合的方法快了一個數量級。這一發現挑戰了視覺定位領域長期以來的共識，或許會讓我們重新思考：我們真的需要兩種特征類型來實現高質量的視覺定位嗎？

定位困境

視覺定位技術在過去十多年經歷了顯著的發展。從自動駕駛到增強現實，從機器人導航到虛擬旅游，準確確定相機在三維空間中的位置和姿態已成為眾多應用的基礎。這些系統大多依賴于一個共同的基礎：通過結構運動恢復（Structure-from-Motion，SfM）技術從圖像集合構建的三維點云。

這些三維點云代表了大規模場景的幾何和外觀特征。每個三維點都有一個關聯的描述符，這個描述符是從圖像像素中提取的。想象一下，當你在博物館拍照時，墻上每幅畫的每個特征點都被記錄下來，包括它在空間中的確切位置和它的視覺特征。這就形成了一個巨大的三維＂地圖＂，里面包含了成千上萬個這樣的點。

當我們需要定位一張新拍攝的照片時，系統會從這張照片中提取局部特征，然后嘗試找到與三維模型中點的對應關系。這聽起來很直接，但實際操作中充滿挑戰：視覺混淆（不同物體看起來相似）、場景變化（如季節變化或物體移動）、噪聲等都會干擾匹配過程。

更大的問題是數據規模。假設一個城市場景的三維模型包含數百萬個點，而一張查詢圖像有上千個特征點，直接匹配意味著要進行數十億次比較。這在計算上是非常昂貴的。

為了解決這個問題，研究者們提出了混合方法：先使用全局特征（整張圖像的單一描述符）進行圖像檢索，找出數據庫中最相似的幾張圖像，然后只與這些圖像中的局部特征進行匹配。這種方法大大減少了搜索空間，但也帶來了新的問題：我們需要為每張查詢圖像計算兩種不同類型的特征，增加了系統復雜性和延遲。

這種混合方法在最近的研究中變得如此主流，以至于全局嵌入似乎成了視覺定位中圖像檢索的必備元素。例如，2020年發布的一個重要定位基準在發布時甚至沒有考慮基于局部特征的檢索方法。

全局特征方法如AP-GeM、DELG和NetVLAD在圖像檢索任務中表現出色，但它們只能提供粗略的位置估計，無法滿足高精度定位的需求。局部特征則保留了圖像的細節信息，理論上更適合精確定位，但如何在海量數據中高效找到匹配一直是一個未解決的難題。

研究者們也嘗試了局部特征聚合方案，如ASMK（Aggregated Selective Match Kernels），它將局部描述符聚合成高維的全局圖像表示。這種方法在一定程度上結合了全局和局部方法的優勢，但聚合過程會丟失一些細節信息，而且在部分視圖和獨特細節的匹配上表現不佳。

視覺定位技術似乎陷入了一個兩難境地：全局特征高效但精度不足，直接使用局部特征精度高但效率低下，而混合方法又增加了系統復雜性。我們是否有可能找到一種方法，只使用局部特征就能高效、精確地進行定位呢？

算法革新

約束近似最近鄰（CANN）算法正是為解決這一難題而生。這個方法的核心思想非常直觀：在進行特征匹配時，不僅考慮描述符的相似度，還考慮匹配點在三維空間中的位置關系。

想象一下，當你拍攝一張照片時，照片中的所有物體必然都位于你相機的視野范圍內，形成一個錐形區域。如果我們能在匹配過程中優先考慮那些位于同一視野錐內的三維點，就能大大提高匹配的準確性。

CANN算法正是基于這一洞察，提出了一種聯合解決方案，同時在幾何和外觀空間進行k-最近鄰搜索。這是一個長期以來被認為困難的問題，CANN提供了第一個實用的解決方案。

算法的理論基礎是構建一個能夠在多個度量空間中同時搜索的k-最近鄰檢索系統。具體來說，CANN引入了一個評分函數，用于對索引中的圖像進行排名：

對于每個查詢特征qj，計算它與圖像i中最近特征的正規化歐氏距離dij。然后，通過一個精心設計的公式計算每個圖像的總分si，這個分數綜合考慮了所有查詢特征與該圖像特征的距離。

這聽起來很簡單，但實現起來面臨一個技術挑戰：如何高效地找到每個查詢特征在所有索引圖像中的最近鄰？傳統方法需要為每個圖像建立一個單獨的最近鄰數據結構，查詢時間與圖像數量成正比，這在大規模場景中是不可接受的。

為了解決這個問題，CANN提出了兩種實現方案：CANN-RS（基于范圍搜索）和CANN-RG（基于隨機網格）。

CANN-RS是一個簡單但有效的方法，它使用隨機范圍搜索數據結構索引所有特征，然后對每個查詢特征，枚舉半徑R內的所有鄰居，統計每個圖像ID出現的次數。這種方法的優點是簡單直接，但缺點是可能需要枚舉大量不相關的點。

CANN-RG則更加復雜和高效。它基于隨機網格技術，通過對高維向量應用隨機旋轉和平移，然后將它們散列到一組鍵上。對于半徑為R的每個查詢點，CANN-RG報告范圍內的所有顏色（圖像ID），而不需要枚舉實際的點或計算描述符空間中的距離。

這兩種方法都實現了同一個目標：高效獲取一組2D-3D對應關系，這些對應不僅在描述符空間相似，而且在三維空間中也是緊湊的。實驗表明，與傳統方法相比，CANN能夠檢索到更多內點匹配（符合幾何驗證的匹配），減少外點（不相關的匹配）。

CANN-RG特別值得關注，因為它在保持高質量結果的同時，大大降低了計算成本。在實驗中，CANN-RG的查詢時間可以低至幾毫秒，與全局特征方法相當，同時保持了局部特征的高精度。

值得注意的是，CANN完全不依賴全局特征，這意味著我們不再需要為每張查詢圖像計算兩種不同類型的特征。這不僅簡化了系統架構，還減少了處理延遲，對于實時應用如增強現實和機器人導航尤為重要。

CANN的另一個優勢是它的適應性。它可以與不同類型的局部特征（如HOW、FIRE和R2D2）結合使用，并在不同的場景中表現良好。與需要針對數據分布調整的碼本方法不同，CANN只需調整度量本身的參數，這使它在面對不同數據集時更具魯棒性。

在實現上，CANN算法非常簡單，易于并行化，運行速度非常快。在一些數據集上，CANN-RG的查詢時間可以低至20毫秒，比傳統局部特征聚合方法如ASMK快一個數量級。

CANN不僅在視覺定位中表現優異，在一般圖像檢索任務中也有應用潛力。初步結果表明，CANN與全局特征結合使用，在ROxford數據集上能夠達到最先進的性能水平。

總的來說，CANN算法代表了視覺定位技術的一次重要突破，它重新提出了一種解決方案，聯合優化外觀和幾何空間的搜索，這比之前提出的兩步過濾方法更高效、更優雅。它挑戰了視覺定位領域長期以來的假設，證明局部特征不僅可以與全局特征競爭，而且在許多情況下表現更好。

實驗佐證

約束近似最近鄰（CANN）算法不只是理論上的創新，在實際應用中也表現出色。谷歌研究團隊在四個大型公共數據集上進行了嚴格測試：百度購物中心（Baidu-Mall）、江南站（Gangnam Station）、牛津機器人汽車四季（RobotCar Seasons）和亞琛晝夜（Aachen Day-Night v1.1）。這些數據集代表了不同場景的挑戰——室內重復環境、戶外城市場景，以及晝夜光照變化等復雜情況。

在評估過程中，研究者們使用了兩個關鍵指標：一是圖像檢索性能，即通過檢索到的圖像及其已知位姿計算等權重質心（EWB）；二是最終定位質量，使用僅基于排名前k的圖像特征的現有定位流程。這兩個指標分別評估了系統在圖像檢索和精確定位兩個階段的性能。

為了全面比較，CANN與當前最先進的全局特征方法（AP-GeM、DELG-GLDv2、DenseVLAD和NetVLAD）以及基于局部特征聚合的方法（ASMK）進行了對比。同時，研究者們還測試了三種不同類型的局部圖像特征：HOW、FIRE和R2D2，這些特征各有特點，適用于不同場景。

實驗結果令人驚訝：在所有數據集上，基于局部特征的CANN方法幾乎全面超越了全局特征方法，而且優勢顯著。特別在那些只有部分重疊或具有獨特細節的場景中，CANN的優勢更為明顯。

以江南站數據集為例，當使用前50張排名圖像時，CANN+FIRE在SFM指標（0.25米，2.0度精度要求）下實現了約67%的定位率，而最好的全局特征方法DELG-R101僅達到約58%。這個差距在亞琛晝夜的夜間子集中更加明顯：CANN+HOW達到了約65%的定位率，而DELG-R101只有約45%。

這種性能差異揭示了一個關鍵事實：全局特征雖然計算效率高，但在細粒度匹配上存在本質局限。當場景變化大、視角差異明顯或光照條件變化時，全局特征往往難以捕捉關鍵的局部細節。

CANN不僅超越了全局特征方法，還在多數情況下優于ASMK這類局部特征聚合方案。在百度購物中心數據集上，CANN+HOW在SFM指標下達到了約64%的定位率，比ASMK+HOW高出約4個百分點。這表明CANN的搜索策略比簡單的特征聚合更有效，能更好地保留和利用局部特征的細節信息。

更令人印象深刻的是CANN在效率方面的表現。在速度測試中，CANN-RG的查詢時間比ASMK快了一個數量級。具體來說，在江南站數據集上，CANN-RG平均每張查詢圖像僅需0.05秒（使用HOW特征），而ASMK則需要0.41秒。這種效率提升在大規模應用中尤為重要，可以極大降低系統延遲。

在復雜環境下的適應性測試也證明了CANN的穩健性。在牛津機器人汽車四季的夜間子集中，傳統方法往往因為光照條件變化而失效，但CANN+HOW仍然實現了約25%的定位率（SFM指標），比最好的全局特征方法高出約10個百分點。這表明CANN能更好地處理極端條件下的匹配問題。

值得注意的是，選擇合適的局部特征對CANN的性能影響很大。在大多數數據集上，HOW和FIRE特征表現優于R2D2特征。這并不奇怪，因為HOW和FIRE是專為圖像檢索設計的，雖然它們在后續的特征匹配階段不如R2D2適用。這也說明了選擇適合任務的特征類型的重要性。

為了驗證CANN的泛化能力，研究者們還在ROxford通用圖像檢索數據集上進行了初步實驗。結果顯示，DELG與CANN-RG+HOW的加權組合在中等難度任務上達到了83.3%的準確率，在高難度任務上達到了64.2%的準確率，超過了當時最先進的方法。這說明CANN不僅適用于視覺定位，在一般圖像檢索任務中也有潛力。

這些實驗結果顛覆了視覺定位領域的常見認知，證明基于局部特征的方法不僅可以與全局特征方法競爭，而且可以在性能和效率上全面超越它們。這為未來視覺定位系統的設計提供了新的思路。

前景展望

CANN技術的成功不僅在于它解決了特定的技術問題，更在于它挑戰并改變了視覺定位領域的思維方式。長期以來，研究者們似乎已經放棄了直接使用局部特征進行高效視覺定位的可能性，轉而采用全局特征和局部特征的混合方法。CANN的出現證明，這種假設并不成立。

這一發現促使我們重新思考視覺定位的技術路線。傳統混合方法需要為每張查詢圖像計算兩種不同類型的特征：全局特征用于初步檢索，局部特征用于精確匹配。這不僅增加了系統復雜性，還引入了額外的計算開銷和延遲。

使用CANN，我們可以構建一個更加簡潔的系統，僅使用局部特征就能實現高效、精確的定位。這簡化了系統架構，減少了冗余計算，并可能提高系統的整體響應速度。特別是在資源受限的設備上，如移動AR設備或小型機器人，這種簡化可能帶來顯著的性能提升。

當然，CANN也面臨自己的挑戰和權衡。最明顯的是內存消耗：使用局部特征意味著需要在內存中保存整個三維地圖的所有特征，這可能對大規模應用構成挑戰。相比之下，使用全局特征的方法可以將局部特征存儲在磁盤上，只在需要時加載特定區域的數據。

不過，這個問題可以通過幾種方式緩解。一種方法是使用層次化的索引結構，先用較低維度的特征進行粗略定位，再加載相關區域的高維特征進行精確匹配。另一種方法是利用特征壓縮技術，如量化或哈希，減少內存占用。隨著硬件性能的不斷提升，這個挑戰可能會變得越來越不重要。

CANN在效率和精度之間提供了靈活的權衡。CANN-RG允許通過調整參數來平衡查詢時間和結果質量。在需要高速響應的應用中，可以犧牲一些精度來獲得更快的查詢速度；而在精度要求高的場景中，可以適當增加計算時間來提高匹配質量。這種靈活性使CANN能夠適應不同的應用需求。

在一般圖像檢索任務中，CANN也展示了應用前景。初步實驗表明，將CANN與全局特征結合使用可以達到甚至超過當前最先進方法的性能。這表明CANN的核心思想——在多個度量空間中聯合搜索——可能對更廣泛的計算機視覺任務有價值。

值得一提的是，CANN的簡潔性和效率使它特別適合移動設備和嵌入式系統。隨著AR/VR技術的普及和機器人技術的發展，這些平臺上的視覺定位需求將越來越大。CANN可能成為這些應用的關鍵技術。

未來研究可能從幾個方向繼續推進CANN：一是進一步優化算法效率，減少內存占用；二是探索與其他技術的結合，如神經輻射場（NeRF）或場景理解；三是將CANN擴展到更廣泛的場景，如大規模城市環境或動態變化的場景。

特別值得關注的是CANN在處理動態場景變化方面的潛力。傳統的基于三維點云的定位方法在面對季節變化、建筑變動或臨時物體（如停放的車輛）時往往表現不佳。CANN的局部特征匹配方式可能更容易適應這些變化，因為它可以找到場景中保持不變的關鍵細節。

CANN的簡單性也是其重要優勢。與需要復雜訓練過程的深度學習方法不同，CANN是一個純算法解決方案，易于實現和部署。這使得它可以快速適應不同的應用場景，無需大量的領域特定數據或昂貴的重新訓練過程。

總的來說，CANN技術代表了視覺定位領域的一個重要突破。它不僅提供了一個高效、精確的定位解決方案，還挑戰了領域內的傳統思維，開辟了新的研究方向。隨著技術的不斷完善和應用的拓展，我們可以期待CANN及其衍生技術在未來計算機視覺和機器人領域發揮更大的作用。

參考資料

1. Aiger， D.， Araujo， A.， &； Lynen， S. （2023）. Yes， we CANN: Constrained Approximate Nearest Neighbors for local feature-based visual localization. In Proceedings of the IEEE International Conference on Computer Vision （ICCV）.

2. Aiger， D.， Kappes， J. H.， Kokiopoulou， E.， &； Pajdla， T. （2013）. Approximate nearest neighbor search in high dimensions. In Advances in neural information processing systems.

3. Sarlin， P. E.， Cadena， C.， Siegwart， R.， &； Dymczyk， M. （2019）. From coarse to fine: Robust hierarchical localization at large scale. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.

4. Arandjelovi?， R.， Gronat， P.， Torii， A.， Pajdla， T.， &； Sivic， J. （2016）. NetVLAD: CNN architecture for weakly supervised place recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition.

5. Cao， B.， Araujo， A.， &； Sim， J. （2020）. Unifying deep local and global features for image search. In European Conference on Computer Vision.