實時紅外圖像拼接中的LSH快速配準算法

王雨曦，亓洪興，葛明峰，舒 嶸

(中國科學院上海技術物理研究所空間主動光電技術重點實驗室，上海200083)

1 引言

當前大視場(大于 60°)機載熱紅外(8～12 μm)成像儀在軍事偵察、海上搜救、核電站溫排水監測等領域都具有廣泛的應用需求。傳統的大視場熱紅外成像技術都是采用單元器件或者線陣器件進行物方掃描實現大視場觀測，其缺點就是空間分辨率低，通常都被限制在mrad量級。隨著小面陣熱紅外探測器技術的逐漸成熟，利用小面陣探測器通過畫幅式擺掃方式實現大視場、高分辨率觀測可以使得空間分辨率達到優于100 μrad的水平。其基本工作原理如圖1所示，飛機向前飛行過程中，在翼展方向上利用光機擺掃機構實行面陣探測器畫幅式掃描成像，每一幅圖像之間保持一定的重疊率，飛行方向上掃描行與掃描行之間保持一定的重疊率。這樣，通過實時的圖像拼接就可以獲取連續的大視場高分辨率熱紅外圖像。

圖1 畫幅式擺掃成像Fig.1 Frame－sweep imaging

圖像拼接是將有共同部分的待拼接圖像通過計算機技術進行處理，拼接成一幅整體圖像［1］。畫幅式擺掃成像需要同時在航向和掃描方向進行拼接。為了完成實時的圖像拼接，需要一種快速的圖像配準算法來獲取相鄰圖像的幾何變換關系。傳統的配準算法主要是基于空間劃分和查找的，如randomized Kd－trees、hierarchical k－means tree和 ANN(Aggregate Nearest Neighbors)等。根據文獻［2］，傳統算法在高維空間下都會退化為線性復雜度，無法滿足實時拼接的要求。為了提高特征匹配的速度，本文利用文獻［3］提出的基于Hash函數投影來加速高維特征近鄰查找的算法思想來加速相鄰圖像間的配準速度。由于算法對高維特征距離的敏感性，所以被稱為局部敏感哈希算法，即 LSH(Locality Sensitive Hashing)算法。

LSH算法目前主要應用于圖像檢索、虛擬場景和3D重建等領域。在圖像配準應用中，國內的研究還比較少。文獻［4］利用LSH對SIFT特征配準進行了加速，取得了不錯的效果。但需要將SIFT特征轉換到Hamming空間，降低了配準速度，同時也沒有考慮其他LSH方法的性能。

LSH主要分為基于 Hamming距離［3］、余弦距離［5］和 Euclidean l2距離［6］的 LSH，簡稱為(Hamming LSH、Arccos LSH 和 L2 LSH)。文獻［7］～［10］對不同LSH的理論復雜度進行了分析。本文對這三種LSH方案的實時性和召回率進行了實驗，驗證了LSH對傳統方法實時性的提高。同時在Hamming LSH的基礎上，提出了一種改進算法。通過對紅外遙感圖像的快速配準系統的實現，驗證了LSH對配準性能的提升。

2 LSH算法

在畫幅式擺掃圖像拼接中，需要紅外圖像的高維特征，然后與相鄰多幅圖像進行特征匹配。若采用傳統的線性搜索算法，算法的復雜度為O(N2)，N為紅外圖像中的點特征數量。當紅外圖像中點特征數量較多時，算法復雜度也會隨著大量增加。

利用LSH算法可以將特征匹配的計算量降低為線性時間。LSH算法將高維特征通過Hash函數投影到不同的Hash桶內，同時距離近的高維特征投影到同一個Hash桶內的概率較大。通過Hash散列，高維特征匹配時只需要對同一Hash桶內的特征進行匹配，減少了待匹配的特征數量。實際應用中的LSH算法框架如圖2所示。

圖2 LSH框架Fig.2 Framework of LSH

選取M個Hash Function鍵值通過AND散列得到Hash Table索引，使得只有M個Hash鍵值均相同時才能得到相等的Hash Table索引。同時選取L個Hash Table通過OR操作，使得任一Hash Table索引相等即可以加入待匹配特征集。設Hash Function的沖突概率為P，則LSH總的沖突概率為:

Pc=1－(1－PM)L

總的沖突概率也叫召回率，衡量了特征匹配的準確率。常用的三種Hash Function的沖突概率如表1所示。

表1 Hash Function沖突概率Tab.1 Collision of Hash Function

Hamming LSH是利用比特采樣的方式從特征向量中隨機抽取一定的比特位進行Hash。r和d分別代表Hamming距離和向量維度。

Arccos LSH利用同維度的隨機矢量來分割高維球面空間，利用特征向量的余弦距離作為相似性度量，其中:

L2 LSH是基于p－stable分布的LSH，其中p=2。L2 LSH以歐式距離為相似性度量，將高維特征投影在分段直線上，并利用線段值來獲取Hash鍵值。其中c=‖－‖2，fp為Cauchy分布函數。

3 基于LSH的圖像配準算法

3.1 圖像配準流程

基于LSH的圖像配準流程如圖3所示。

圖3 LSH圖像配準流程Fig.3 Flow of LSH－based image registration

將源圖像和待匹配圖像進行特征提取后，將源圖像的特征投影到不同的Hash索引中，然后利用待配準圖像的特征對同一Hash索引中的特征進行匹配。特征匹配后的結果需要利用RANSAC［11］算法進一步消除誤匹配。

LSH Build需要從Hash函數集中隨機選取M個Hash Function組成Hash Table，然后對輸入特征向量，通過 L個Hash Table映射得到 Hash索引。LSH Query則需要對每一個Hash Table檢索待查詢向量對應的Hash索引，并將索引內的原始向量加入查找范圍并在查找范圍內選擇近鄰特征向量。

3.2 LSH算法性能

為了驗證LSH算法對傳統線性搜索算法在實時性上的提升，采用美國FLIR SC325熱紅外相機在大連獲取的熱紅外圖像進行配準實驗，同時也對三種LSH算法的實時性能進行了比較。SC325熱紅外圖像分辨率為320×256，驗證實驗共選取了101張連續遙感圖像，分別對M=1～10和N=1，3，5進行了召回率和運行時間的測試。

LSH算法的實時性測試采用與傳統的線性搜索的運行時間比值作為衡量指標，如圖4所示。

圖中橫坐標代表Hash函數數量，即M的值，縱坐標則表示與線性搜索時間的比值。縱坐標越小，代表了匹配時間提升的越多。

從實驗數據中可以發現，Hamming LSH在實時性能方面有最大的提升，而Arccos LSH和L2 LSH則相差不多。同時隨著M的增加，數據分布在更大的范圍內，匹配時間會減低。而隨著L的增加，計算量和匹配時間都會增加。

需要指出的是LSH算法的實時性提高是以損失匹配的精度為代價實現的。為了衡量LSH算法在匹配精度上的損失，需要比較LSH算法的匹配結果與線性搜索算法的匹配結果在準確率上的區別。LSH算法匹配的準確率以2－近鄰的召回率衡量:

圖5 LSH召回率曲線Fig.5 Recall rate of LSH

圖中橫坐標代表Hash函數數量，即M的值，縱坐標為2－近鄰的召回率。根據圖5可以看出召回率曲線符合LSH總的沖突概率公式。隨著M增加召回率逐漸降低，同時隨著L的增加，召回率也會在一定程度上增加，但增加的值有限。

從結果中可以發現Arccos LSH召回率最高，并且下降緩慢，而L2 LSH和Hamming的召回率則有所降低。

綜合實時性和召回率的性能，Hamming LSH具有最好的實時性能，同時在召回率性能上也具有較好的效果。L2 LSH和Arccos LSH只有在M較大時才能提供更好的實時性，但M增加時會導致召回率的性能較低。考慮到畫幅式擺掃快速配準對實時性的要求，應優先考慮使用Hamming LSH算法。

3.3 改進的Hamming LSH

當遙感圖像的內容或像素具有相關性時會導致特征矢量在某些維度過于密集，如果采用隨機比特采樣時會導致Hash表中特征向量的不均勻性。而當Hash表特征向量較少時會導致特征匹配的誤匹配增加和召回率降低，如圖6加形曲線所示。

圖6 召回率變化曲線Fig.6 Curve of Recall Rate

改進后的Hamming LSH的召回率如圖6方形曲線所示，可以看到，改進后的Hamming LSH在召回率較低的情況下有了較大的改善，同時整體的召回率性能也有所提升。

3.4 圖像配準性能驗證

為了驗證LSH算法在拼接系統中的性能，同時也驗證LSH在匹配準確率降低的情況下仍然能取得較好的拼接效果，本文利用11張熱紅外遙感圖像數據進行圖像拼接性能驗證，圖像數據來源同3.2節。具體步驟如下:

(1)利用ORB特征算子從熱紅外圖像中提取高維特征。

(2)分別利用線性搜索和改進的Hamming LSH算法對相鄰圖像進行特征匹配，參數配置選取M=5，L=3。

(3)利用RANSAC消除誤匹配，并利用匹配信息得到相鄰圖像間的基礎矩陣。

(4)圖像反投影到統一平面上并融合得到拼接后的全景圖像。

實驗結果如圖7所示。

圖7 圖像配準結果Fig.7 Result of Image Registration

從實驗結果可以看出LSH算法較好地完成了紅外圖像配準，驗證了LSH在特征匹配中的性能。同時通過統計LSH配準算法和線性搜索配準算法的時間，得到LSH在配準時間上減少了48.6%，提高了圖像拼接的實時性。

4 結語

本文針對LSH算法在畫幅式擺掃熱紅外圖像實時拼接中的應用，對三種LSH與傳統配準方法的實時性進行了比較，驗證了LSH算法對配準速度的提高。并對LSH算法精確率性能進行了比較，選取了綜合性能最好的Hamming LSH算法。本文針對Hamming LSH在較低召回率的情況下進行了改進，并利用畫幅式熱紅外遙感圖像進行配準性能驗證。實驗結果表明，Hamming LSH配準算法能在保證配準精度的前提下提高拼接的速度，可以實現畫幅式紅外圖像的快速拼接。本文的研究成果對基于畫幅式擺掃成像的大視場高分辨率紅外觀測技術的發展具有較好的推動作用。

［1］ WEI Chuan，ZHANG Gongguo，L Xiaomeng.Application of image mosaic in binocular cameras surveillance［J］.Laser＆ Infrared，2014，44(4):447－451.(in Chinese)魏川，張功國，呂曉萌.圖像拼接技術在雙攝像機監控中的應用［J］.激光與紅外，2014，44(4):447－451.

［2］ Weber R，Scjel H J，Blott S.A quantitative analysis and performance study for similarity－search methods in high－dimensional spaces［C］.VLDB.1998，98:194－205.

［3］ Indyk P，Motwani R.Approximate nearest neighbors:towards removing the curse of dimensionality［C］.Proceedings of the thirtieth annual ACM symposium on Theory of computing.ACM，1998:604－613.

［4］ GONG Weiguo，ZHANG Xuan，LI Zhenghao.Image registration based on extended LSH［J］.Optics and Precision Engineering，2011，19(6):1375－1382.(in Chinese)龔衛國，張旋，李正浩.基于改進局部敏感散列算法的圖像配準［J］.光學 精密工程，2011，19(6):1375－1382.

［5］ Charikar M S.Similarity estimation techniques from rounding algorithms［C］.Proceedings of the thiry－fourth annual ACM symposium on Theory of computing.ACM，2002:380－388.

［6］ Datar M，Immorlica N，Indyk P，et al.Locality－sensitive hashing scheme based on p－stable distributions［C］.Proceedings of the twentieth annual symposium on Computational geometry，ACM，2004:253－262.

［7］ Andoni A.Nearest neighbor search:the old，the new，and the impossible［D］.Massachusetts:Massachusetts Institute of Technology，2009.

［8］ Andoni A，Indyk P.Near－optimal hashing algorithms for approximate nearest neighbor in high dimensions［C］.Foundations of Computer Science，2006.FOCS'06.47th Annual IEEE Symposium on.IEEE，2006:459－468.

［9］ Rajaraman A，Ullman J D.Mining of massive datasets［M］.Cambridge:Cambridge University Press，2011:97－108.

［10］ Paulevé，LoC，Hervé JéGou，Laurent Amsaleg.Locality sensitive hashing:A comparison of hash function types and querying mechanisms［J］.Pattern Recognition Letters，2010，31(11):1348－1358.

［11］ Fischler M A，Bolles R C.Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography［J］.Communications of the ACM，1981，24(6):381－395.