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

(中國科學(xué)院上海技術(shù)物理研究所空間主動(dòng)光電技術(shù)重點(diǎn)實(shí)驗(yàn)室，上海200083)

1 引言

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

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

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

LSH算法目前主要應(yīng)用于圖像檢索、虛擬場景和3D重建等領(lǐng)域。在圖像配準(zhǔn)應(yīng)用中，國內(nèi)的研究還比較少。文獻(xiàn)［4］利用LSH對SIFT特征配準(zhǔn)進(jìn)行了加速，取得了不錯(cuò)的效果。但需要將SIFT特征轉(zhuǎn)換到Hamming空間，降低了配準(zhǔn)速度，同時(shí)也沒有考慮其他LSH方法的性能。

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

2 LSH算法

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

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

圖2 LSH框架Fig.2 Framework of LSH

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

Pc=1－(1－PM)L

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

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

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

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

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

3 基于LSH的圖像配準(zhǔn)算法

3.1 圖像配準(zhǔn)流程

基于LSH的圖像配準(zhǔn)流程如圖3所示。

圖3 LSH圖像配準(zhǔn)流程Fig.3 Flow of LSH－based image registration

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

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

3.2 LSH算法性能

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

LSH算法的實(shí)時(shí)性測試采用與傳統(tǒng)的線性搜索的運(yùn)行時(shí)間比值作為衡量指標(biāo)，如圖4所示。

圖中橫坐標(biāo)代表Hash函數(shù)數(shù)量，即M的值，縱坐標(biāo)則表示與線性搜索時(shí)間的比值?？v坐標(biāo)越小，代表了匹配時(shí)間提升的越多。

從實(shí)驗(yàn)數(shù)據(jù)中可以發(fā)現(xiàn)，Hamming LSH在實(shí)時(shí)性能方面有最大的提升，而Arccos LSH和L2 LSH則相差不多。同時(shí)隨著M的增加，數(shù)據(jù)分布在更大的范圍內(nèi)，匹配時(shí)間會(huì)減低。而隨著L的增加，計(jì)算量和匹配時(shí)間都會(huì)增加。

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

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

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

從結(jié)果中可以發(fā)現(xiàn)Arccos LSH召回率最高，并且下降緩慢，而L2 LSH和Hamming的召回率則有所降低。

綜合實(shí)時(shí)性和召回率的性能，Hamming LSH具有最好的實(shí)時(shí)性能，同時(shí)在召回率性能上也具有較好的效果。L2 LSH和Arccos LSH只有在M較大時(shí)才能提供更好的實(shí)時(shí)性，但M增加時(shí)會(huì)導(dǎo)致召回率的性能較低?？紤]到畫幅式擺掃快速配準(zhǔn)對實(shí)時(shí)性的要求，應(yīng)優(yōu)先考慮使用Hamming LSH算法。

3.3 改進(jìn)的Hamming LSH

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

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

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

3.4 圖像配準(zhǔn)性能驗(yàn)證

為了驗(yàn)證LSH算法在拼接系統(tǒng)中的性能，同時(shí)也驗(yàn)證LSH在匹配準(zhǔn)確率降低的情況下仍然能取得較好的拼接效果，本文利用11張熱紅外遙感圖像數(shù)據(jù)進(jìn)行圖像拼接性能驗(yàn)證，圖像數(shù)據(jù)來源同3.2節(jié)。具體步驟如下:

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

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

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

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

實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 圖像配準(zhǔn)結(jié)果Fig.7 Result of Image Registration

從實(shí)驗(yàn)結(jié)果可以看出LSH算法較好地完成了紅外圖像配準(zhǔn)，驗(yàn)證了LSH在特征匹配中的性能。同時(shí)通過統(tǒng)計(jì)LSH配準(zhǔn)算法和線性搜索配準(zhǔn)算法的時(shí)間，得到LSH在配準(zhǔn)時(shí)間上減少了48.6%，提高了圖像拼接的實(shí)時(shí)性。

4 結(jié)語

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

［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)魏川，張功國，呂曉萌.圖像拼接技術(shù)在雙攝像機(jī)監(jiān)控中的應(yīng)用［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)龔衛(wèi)國，張旋，李正浩.基于改進(jìn)局部敏感散列算法的圖像配準(zhǔn)［J］.光學(xué) 精密工程，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.