影像檢索：基於內容的影像檢索技術（四）

2020 年 3 月 18 日
筆記

近似最近鄰搜索

基於樹結構的最近鄰搜索方法和基於哈希的最近鄰搜索方法在理論電腦科學、機器學習以及電腦視覺中是一個很活躍的領域，這些方法通過將特徵空間劃分成很多小的單元，以此減少空間搜索的區域，從而達到次線性的計算複雜度。

基於樹的影像檢索方法將影像對應的特徵以樹結構的方法組織起來，使得在檢索的時候其計算複雜度降到關於影像庫樣本數目n的對數的複雜度。基於樹結構的搜索方法有KD-樹8、M-樹9等。在眾多的樹結構搜索方法中，以KD-樹應用得最為廣泛，KD-樹在構建樹的階段，不斷以方差最大的維對空間進行劃分，其儲存對應的樹結構則不斷的向下生長，並將樹結構保存在記憶體中，如圖2.1右圖示例了一個簡單的KD-樹劃分過程：在搜索階段，查詢數據從樹根節點達到葉節點後，對葉節點下的數據與查詢數據進行逐一比較以及回溯方式從而找到最近鄰。雖然基於樹結構的檢索技術大大縮減了單次檢索的響應時間，但是對於高維特徵比如維度為幾百的時候，基於樹結構的索引方法其在檢索時候的性能會急劇的下降，甚至會下降到接近或低於暴力搜索的性能，如表2.1所示，在LabelMe數據集上對512維的GIST特徵進行索引的時候，單次查詢Spill樹(KD-樹的變形)耗時比暴力搜索用時還要多。此外，基於樹結構的檢索方法在構建樹結構的時候其佔用的存儲空間往往要比原來的數據大得多，並且對數據分布敏感，從而使得基於樹結構的檢索方法在大規模影像資料庫上也會面臨記憶體受限的問題。

相比基於樹結構的影像檢索方法，基於哈希的影像檢索方法由於能夠將原特徵編碼成緊緻的二值哈希碼，使得基於哈希的影像檢索方法能夠大幅的降低記憶體的消耗，並且由於在計算漢明距離的時候可以使用電腦內部運算器具有的XOR異或運算，從而使的漢明距離的計算能夠在微秒量級內完成，從而大大縮減了單次查詢響應所需要的時間。如表2.1所示，在LabelMe影像數據集上，相比於暴力搜索方法以及基於樹結構的搜索方法，通過將影像的特徵編碼後進行搜索，在編碼位數為30比特時基於哈希的搜索方法單次查詢時間比暴力搜索以及基於樹結構的方法降低了將近4個數量級，並且特徵維度由原來的512維降低至30維，因而極大的提高了檢索的效率。

基於哈希的影像檢索方法其關鍵之處在於設計一個有效的哈希函數集，使得原空間中的數據經過該哈希函數集映射後，在漢明空間其數據間的相似性能夠得到較好的保持或增強。由於未經編碼的特徵在數域上是連續的，而哈希編碼得到的是一個二值哈希碼，也就是說從數域上來講哈希函數集是一個將數值從連續域變換到離散域的過程，因而會導致在優化哈希函數集時往往難於求解10，從而使得設計一個有效的哈希函數集極其不易。在過去的十幾年裡，儘管設計有效的哈希函數集面臨很大的挑戰，但研究者們仍然提出了很多基於哈希的影像檢索方法，其中最經典的哈希方法是局部敏感哈希方法11(LSH, Locality Sensitive Hashing)。

局部敏感哈希被認為是高維空間(比如成百上千維)快速最近鄰搜索的重要突破，它在構造哈希函數的時候採用隨機超平面的方法，即使用隨機超平面將空間分割成很多子區域，每一個子區域可以被視為一個」桶」，如圖2.1右圖所示。在構建階段，局部敏感哈希僅需要生成隨機超平面，因而沒有訓練的過程；在索引階段，樣本被映射成二進位哈希碼，如圖2.1右圖示意的二進位哈希碼，具有相同的二進位哈希碼的樣本被保存在同一個「桶」中；在查詢階段，查詢樣本通過同樣的映射後可以鎖定查詢樣本位於哪個「桶」中，然後在鎖定的」桶」中將查詢樣本與該「桶」中的樣本進行逐一的比較，從而得到最終的近鄰。局部敏感哈希其有效性在理論分析中得到了保證，但是由於局部敏感哈希在構造哈希函數過程中並沒有利用到數據本身，使得在應用局部敏感哈希時為了獲得較高的精索精度常常採用很長的編碼位，但在長編碼位數下會降低相似樣本在哈希離散過程中的碰撞概率，從而導致檢索的召回率會出現比較大的下降，因此出現了多個哈希表的局部敏感哈希。在相同的編碼長度下，相比於只有一個哈希表的局部敏感哈希(即單哈希表局部敏感哈希)，多哈希表局部敏感哈希中的每一個哈希表的編碼長度減小為單哈希表局部敏感哈希編碼長度的L分之一倍(假設L為多哈希表局部敏感哈希)，因此多哈希表局部敏感哈希能夠獲得比具有相同編碼長度的單哈希表局部敏感哈希更高的召回率，但無論是多哈希表局部敏感哈希還是單哈希表局部敏感哈希，它們的編碼都不是緊緻的，從而使得它們在記憶體使用效率方面並不是很有效。

在面向大規模影像檢索時，除了採用影像哈希方法外，還有另一類方法，即向量量化的方法，向量量化的方法中比較典型的代表是乘積量化(PQ, Product Quantization)方法，它將特徵空間分解為多個低維子空間的笛卡爾乘積，然後單獨地對每一個子空間進行量化。在訓練階段，每一個子空間經過聚類後得到k

個類心(即量化器)，所有這些類心的笛卡爾乘積構成了一個對全空間的密集劃分，並且能夠保證量化誤差比較小；經過量化學習後，對於給定的查詢樣本，通過查表的方式可以計算出查詢樣本和庫中樣本的非對稱距離12。乘積量化方法雖然在近似樣本間的距離時比較的精確，但是乘積量化方法的數據結構通常要比二值哈希碼的複雜，它也不能夠得到低維的特徵表示，此外為了達到良好的性能必須加上不對稱距離，並且它還需要每個維度的方差比較平衡，如果方差不平衡，乘積量化方法得到的結果很差。

參考文獻

LOWE D G. Distinctive Image Features from Scale-Invariant Keypoints, Int. J. Comput. Vis., 2004, 60(2):91–110.
BAY H, TUYTELAARS T, GOOL L J V. SURF: Speeded Up Robust Features, Proc. IEEE Int. Conf. Comput. Vis., 2006:404–417.
RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB: An Efficient Alternative to SIFT or SURF, Proc. IEEE Int. Conf. Comput. Vis., 2011:2564–2571.
CSURKA G, DANCE C, FAN L, et al. Visual Categorization with Bags of Keypoints, Workshop on statistical learning in computer vision, Eur. Conf. Comput. Vis., 2004,1:1–2.
JEGOU H, DOUZE M, SCHMID C, et al. Aggregating Local Descriptors into A Compact Image Representation, Proc. IEEE Int. Conf. Comput. Vis. Pattern Recognit., 2010:3304–3311.
PERRONNIN F, SÁNCHEZ J, MENSINK T. Improving the Fisher Kernel for Large-Scale Image Classification, Proc. Eur. Conf. Comput. Vis., 2010:143–156.
KIAPOUR M H, HAN X, LAZEBNIK S, et al. Where to Buy It: Matching Street Clothing Photos in Online Shops, Proc. IEEE Int. Conf. Comput. Vis., 2015:3343–3351.
BENTLEY J L. Multidimensional Binary Search Trees Used for Associative Searching, Commun. ACM, 1975, 18(9):509–517.
UHLMANN J K. Satisfying General Proximity/Similarity Queries with Metric Trees, Inf. Process. Lett., 1991, 40(4):175–179.
GE T, HE K, SUN J. Graph Cuts for Supervised Binary Coding, Proc. Eur. Conf. Comput. Vis., 2014:250–264.
DATAR M, IMMORLICA N, INDYK P, et al. Locality-Sensitive Hashing Scheme Based on p-stable Distributions, Proc. Symp. Comput. Geom., 2004:253–262.
DONG W, CHARIKAR M, LI K. Asymmetric Distance Estimation with Sketches for Similarity Search in High-dimensional Spaces, Proc. ACM SIGIR Conf. Res. Develop. Inf. Retr., 2008:123–130.