一種抗視角變換的改進SIFT景象匹配算法

蘇可心 ，韓廣良 ，孫海江

1.中國科學院大學，北京 100039

2.中國科學院 長春光學精密機械與物理研究所 圖像室，長春 130033

1 引言

近年來，精度高、突防能力強、殺傷力大的精確制導武器在現代化戰爭中起著主導作用[1]。而景象匹配作為高精度末制導技術已廣泛應用于精確制導系統中：利用電視導引頭實時獲取的前視圖像（實時圖）與存儲在彈體導引頭中的目標區域圖像（基準圖）進行匹配，依據匹配結果判定當前是否到達目標區域，從而對目標進行精確定位，為末制導跟蹤過程提供必要的目標初始信息[2]?？梢?，景象匹配算法的性能將直接影響末制導定位精度。

目前，基于局部特征的景象匹配成為國內外研究的熱點。其中，David Lowe[3]于2004年提出的SIFT算法因其對旋轉、尺度變換、光照變化等都具有良好的魯棒性而得到廣泛研究。如SURF[4]算法旨在改善SIFT的計算復雜度；針對SIFT無法適應大視角變換的缺點，Morel[5]于2009年提出ASIFT算法，通過模擬相機拍攝視角的變化，實現了全仿射不變性，但其匹配效率相對較低。

本文針對末制導導彈目標匹配階段，彈載相機拍攝的實時圖與預存的基準圖之間存在大視角差異的情形，提出了一種抗視角變換的改進SIFT景象匹配算法。該算法較原始SIFT算法得到更多匹配點對并且明顯提高了匹配準確率，滿足工程應用需求。

2 SIFT算法原理

SIFT特征點提取與匹配過程一般包括如下4個步驟[6-9]：

（1）尺度空間極值點檢測，即在圖像二維平面空間和尺度空間中同時檢測局部極值點。并通過擬合三維二次函數來精確特征點的位置和尺度。

（2）特征點方向分配，采用基于梯度方向直方圖統計的方法來確定特征點的方向。

（3）建立特征點的描述符，SIFT描述子是對特征點鄰域高斯圖像梯度統計結果的一種表示。

（4）SIFT特征點集的匹配。以歐氏距離作為相似度量準則來完成特征向量集的匹配，并采用RANSAC[10]算法對匹配點對進行篩選，從而提高變換模型參數估計的準確性。

3 SIFT算法改進

通過實驗發現，當實時圖和基準圖之間存在較大視角差異時，SIFT算法得到的匹配對數明顯減少且誤匹配增多。針對此問題，本文受到Matas等人[11]的啟發后在提取SIFT特征點環節即步驟（1）對其進行改進：首先，在高斯尺度空間中提取抗仿射變換區域；第二，用逐層篩選的方法去除近似重復的冗余區域，得到最終尺度不變的抗仿射變換區域集；第三，采用合理的變換矩陣對不規則形狀的區域集進行歸一化處理；最后，由各歸一化區域的圓心構成抗視角變換特征點集。下面將具體介紹其實現方法。

3.1 提取抗仿射變換區域

在SIFT算法中，特征點鄰域的梯度分布直接影響特征點方向的分配以及描述符的生成。而工程實際中經常出現的視角差異過大，會導致圖像發生不規則的幾何形變，同時特征點鄰域梯度分布也會隨之發生畸變，使得SIFT算法性能明顯下降。針對此問題，本文首先在SIFT的高斯尺度空間中檢測抗仿射變換區域來改善算法對視角變換的適應性。將提取的區域做如下數學描述：

對于灰度圖像I，滿足I:D?Z2→S映射關系，如果S具有全序結構，并且定義了像素間的鄰接關系A?D×D（這里采用4-鄰域），那么可將圖像中的區域R定義為在D上滿足鄰接關系A的連通子集，即對于任意的p，q∈R均有：

其中ai∈Q，i=1，2，…，n。

區域Q的邊界?Q是由不屬于Q，但至少與Q中一個像素滿足鄰接關系的點集，即

對于區域Q?D及其邊界?Q，如果滿足?p∈Q和?q∈?Q，并且I(p)＞I(q)恒成立，則稱Q為極大值區域；反之如果I(p)＜I(q)恒成立，則稱Q為極小值區域。

令序列Q1，Q2，…，Qi-1，Qi，… 表示一組相互嵌套的極值區域，即Qi?Qi+1。如果Qi的面積變化率：

在i處取得局部最小值，則稱Qi為抗仿射變換區域。式（3）中Δ表示閾值變化情況， ||?為區域面積（即區域覆蓋的像素個數）。

經分析可知，提取抗仿射變換區域主要包括獲取極值區域和判定抗仿射變換區域兩部分。具體實現過程為：

（1）采用高效的箱排序（Bin Sort）法對輸入圖像像素按灰度值進行快速排序。

（2）引入分離集合森林數據結構中的并查集，即合并-查找（Union-Find）算法，維護相連區域的列表和面積；并運用按秩合并與路徑壓縮策略分別優化其合并與查找的過程，以快速獲取極值區域。

（3）構建用于保存數據結構中相鄰極值區域的成分樹，當像素點全部植入森林后，即得到該圖像所對應的全部極值區域。成分樹的每層對應一個閾值圖像，并且每層上的每個節點代表相應閾值圖像上的一個極值區域。所求取的抗仿射變換區域即為成分樹上當閾值在2Δ范圍內變化時具有極小面積變化率的區域。

（4）最后要依據面積變化率進行區域的清除：面積變化率過大的區域穩定性差；面積變化率過小的區域多由噪聲引起，本文經實驗證實，保留面積變化率為0.5～1的區域，其穩定性最佳。

為更穩定地獲取圖像中對應目標的關聯特征，本文從正、反兩個方向完成區域提取過程。其中，反向過程即為提取原始圖像的灰度反轉圖像中的區域。所提取的抗仿射變換區域如圖1所示。其中，正向區域標識為綠色，反向區域標識為紅色。

圖1 抗仿射變換區域

由于在提取抗仿射變換區域的過程中，整個區域的信息隨著融合過程的不斷進行而被覆蓋，結果僅剩最后一個抗仿射變換區域的空間位置及其對應閾值。因此要得到全部抗仿射變換區域，需對該區域重新做閾值化處理，導致算法的時間復雜度過高，針對此問題，本文參考文獻[12]的方法，采用鄰域四叉樹的數據結構將雙向鏈表和分離集合森林結合在一起，以便恢復那些存在于任意一棵樹上的節點信息，從而實現對該過程的加速。對于提取抗仿射變換區域來說，即意味著給出任意一個像素點及灰度閾值，就可以根據鄰域四叉樹算法求出區域的全部像素信息，從而有效降低該過程的時間復雜度。

3.2 獲得抗視角變換特征點集

針對高斯尺度空間中檢測圖像的抗仿射變換區域時存在區域重復提取的問題，本文采用逐層篩選的方法對冗余的區域進行處理：

（1）將高斯尺度空間第i層的區域ai變換至第i+1層的尺度上，并表示為區域a′i+1。

（2）設ai+1為第i+1層中與之對應的區域，若同時滿足關系：

則消除第i+1層的相應區域ai+1。其中，C表示對應區域的質心，S表示區域的面積。經實驗驗證，Δ1=3，Δ2=0.2時所得到的區域最穩定。

（3）逐層進行相同的處理，直至遍歷整個高斯尺度空間后即得到尺度不變的抗仿射變換區域集。

由于得到的抗仿射變換區域的形狀是不規則的，不利于特征描述的操作，因此需對這些特征區域進行合理的數學擬合及規則化處理[13]。由于特征區域協方差矩陣的特征值和特征向量唯一確定一個橢圓，因此本文采用橢圓擬合方法。即通過變換矩陣A將圓映射為橢圓的方式進行特征區域擬合。

設灰度圖像I(x，y)中抗仿射變換區域Φ的質心為Xc=(xc，yc)T，則以 Xc為圓心單位圓上的 X滿足：

矩陣A將圓上的點X映射到橢圓上，故有：

比較式（6）、式（7）可知：

式（7）、式（8）中，Κ為抗仿射變換區域Φ的協方差矩陣，I為二階單位矩陣，設：

其中m20、m11、m02為Φ的二階中心矩，分別定義為：該式中m00為Φ的面積，(xc，yc)為Φ的質心坐標，計算公式分別為：

聯立式（8）、式（9），可推導出變換矩陣 A為：

通過式（13）中的矩陣A可將不規則形狀的抗仿射變換區域Φ映射為一個橢圓。其中，橢圓的形狀和主軸傾角由Φ的二階中心矩構成的協方差矩陣唯一確定，中心與Φ的質心重合。圖2為對抗仿射變換區域進行橢圓擬合的結果。

圖2 抗仿射變換區域的橢圓擬合結果

為便于關聯特征間比較，需進一步對得到的橢圓區域進行歸一化處理，即將不同尺寸的橢圓擬合區域映射為某個固定大小的圓形區域。假設待規則化的橢圓中心在點 X′c處，區域規則化的數學描述為：對于橢圓上的點 X=(x，y)T，尋找一個2×2的變換矩陣 A，使得式（14）成立。

其中r為規則化后的圓半徑。因為點X在橢圓上，故有：

其中 Κ 為協方差矩陣（見式（9））。由式（14）、式（15）可以推導出：

聯立式（9）、式（16）可求得：

至此，通過變換矩陣A可將橢圓區域映射至一個固定大小的圓域。對于各圓域，本文取圓心處為特征點位置，即構成抗視角變換特征點集。圖3為分別取自待匹配圖像中某橢圓擬合區域的歸一化結果及特征點位置。

圖3 分別取自待匹配圖像中某橢圓擬合區域的歸一化結果及特征點位置

可見，本文采用的橢圓擬合、歸一化抗仿射變換區域、選取特征點的方法能夠有效消除形變干擾，使特征區域在形態上表現出較強的視覺一致性，有效提取出便于描述和匹配的抗視角變換特征點集。圖4為提取的抗視角變換特征點集。

圖4 抗視角變換特征點集

3.3 抗視角變換特征點集匹配

對上述提取的抗視角變換特征點集運用SIFT算法的步驟（2）～（4）進行描述和匹配，本文采用最小歐氏距離作為匹配準則，即以k-d樹搜索策略在歐氏空間中搜索各特征向量的最近鄰和次近鄰，當兩者之比小于某個閾值（實驗中設定為0.7），則認為兩特征向量匹配。并引入RANSAC算法對特征匹配結果進行誤匹配剔除，完成匹配。

4 仿真結果及實驗分析

實驗仿真平臺的硬件環境為：Intel?CoreTMi3-2120 CPU，主頻3.29 GHz，內存2 GB的PC機；軟件開發工具為：Windows XP 操作系統、VC++6.0、MatlabR2010b。實驗所采用的圖像分別來自Mikolajczyk數據集[14]和實拍圖片。

首先采用 640×800、視角分別為 70°和 20°（視角差為50°）的Graf圖片進行實驗。實驗結果如圖5所示，其中（a）為SIFT的匹配結果；（b）和（c）分別為本文算法的粗匹配及去除誤匹配后的結果；（d）和（e）分別為SURF、ASIFT的匹配結果；實驗數據見表1。

表1 視角差為50°的Graf圖片匹配實驗數據

圖5 視角差為50°的Graf圖片匹配實驗結果

實驗中設定SIFT和本文算法的閾值均為0.6。從圖5及表1中可以看出：在視角差為50°時，SIFT、SURF算法雖耗時較少，但是誤匹配點對增多、匹配可信度明顯下降。ASIFT算法由于實現了全仿射不變性，其匹配效果最佳，對視角變換的魯棒性最好，但由于其算法復雜度高，匹配效率低的缺點，很難滿足工程實際要求。本文算法較SIFT算法增加19組準確匹配點對，準確率提高約4.55倍；較SURF算法增加17組準確匹配點對；相比ASIFT算法，本文算法在耗時方面亦有明顯優勢。

進一步加大待匹配圖像的視角差異：采用640×800、視角分別為60°和0°（視角差為60°）的Graf圖片進行實驗，限于篇幅，圖6僅給出SIFT算法、本文算法及其去除誤匹配的實驗結果，實驗數據見表2。

表2 視角差為60°的Graf圖片匹配實驗數據

從圖6及表2中可以看出：在視角差為60°時，本文算法較SIFT算法增加18組準確匹配點對，匹配準確率提高近5倍；較SURF算法增加17組準確匹配點對；對大視角差異表現出良好的適應性。ASIFT算法的匹配效果最佳，但耗時仍最多。

將本文算法用于實際光電成像制導過程：模擬彈載相機在俯仰角為－63°、飛行高度為1 000 m時拍攝的實時圖與彈體預存的衛星航拍目標區域基準圖（均為315×315）的匹配。圖7中（a）為SIFT算法的匹配結果；（b）為本文算法的匹配結果，實驗數據見表3。

從圖7及表3中可以看出：存在尺度、視角變換情形的光電成像制導過程中，本文算法較SIFT、SURF算法得到更多匹配點對，且匹配點對相對均勻地分布在目標場景內，明顯提高了匹配可信度；較ASIFT算法耗時更少、具備更高的工程實用價值。

圖7 存在尺度、視角變換情形的匹配實驗結果

表3 存在尺度、視角變換情形的匹配實驗數據

圖8為一組模擬彈載相機在航向角為20°、俯仰角為－65°、飛行高度為1 100 m時拍攝的實時圖與預存基準圖的匹配實驗結果。其中，（a）、（b）分別為SIFT和本文算法的匹配結果，實驗數據見表4。

圖8 存在旋轉、尺度和視角變換情形的匹配實驗結果

從圖8及表4中可以看出：本文算法在光電成像制導過程中當基準圖和實時圖之間存在旋轉、尺度和較大視角差異時，也能快速準確地捕獲目標區域，從而盡早為末制導跟蹤系統提供精準的目標初始態信息。具備較高的工程應用價值。

表4 存在旋轉、尺度和視角變換情形的匹配實驗數據

從上述各組實驗中均可以看出，與SIFT、SURF算法相比，本文算法對大視角變換具有良好的魯棒性。但在明顯增加正確匹配點對數的同時，算法耗時增多，這是由于：雖然本文算法相當于只對部分圖像計算SIFT描述子并進行匹配，且引入鄰域四叉樹策略在一定程度上降低了算法的時間復雜度，但在高斯尺度空間中提取抗仿射變換區域，進而得到抗視角變換特征點集是算法中最耗時的環節，這一點仍有待進一步優化。同時，本文算法較ASIFT算法時間復雜度更低、實時性更強?？梢姡疚乃惴ㄔ谄ヅ錅蚀_度和算法耗時兩方面實現了良好的折衷。

5 結束語

本文針對光電成像制導過程中，導引頭目標場景自動識別的實時圖和基準圖之間存在較大視角差異時，SIFT算法的正確匹配點對數減少從而影響對變換模型參數估計的情況，提出了一種抗視角變換的改進SIFT景象匹配算法。仿真結果表明，該算法相比SIFT、SURF算法，在視角差高達50°～60°以上的情況下得到的正確匹配點對數明顯增加，有效提高了匹配算法的可信度。并且較ASIFT具有更低的時間復雜度，利于實時性的實現。后續將針對本文算法的優化和加速開展工作。

[1]陳冰，趙亦工，李欣.基于快速魯棒性特征的景象匹配[J].系統工程與電子技術，2009，31（11）：2714-2718.

[2]邸男，李桂菊，魏雅娟.采用SIFT的末制導圖像匹配技術[J].紅外與激光工程，2011，40（8）：1549-1593.

[3]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vsion，2004，60（2）：91-110.

[4]Herbert B，Tinne T，Luc V G.SURF：speeded up robust features[J].ComputerVision and ImageUnderstanding，2008，110（3）：346-359.

[5]Morel J M，Yu G.ASIFT：a new framework for fully affine invariant imagecomparison[J].SIAM Journal onImaging Science，2009，2（2）：438-468.

[6]丘文濤，趙建，劉杰.結合區域分割的SIFT圖像匹配方法[J].液晶與顯示，2012，27（6）：827-831.

[7]呂倩利，邵永社.基于SIFT特征的異源遙感影像匹配方法研究[J].計算機工程與應用，2012，48（36）：171-176.

[8]王民，劉偉光.基于改進SIFT特征的雙目圖像匹配算法[J].計算機工程與應用，2013，49（2）：203-206.

[9]孔軍，湯心溢，蔣敏.多尺度特征提取的雙目視覺匹配[J].計算機工程與應用，2010，46（33）：1-5.

[10]Fischler M A，Bolles R C.Random sample consensus：a paradigm for model fitting with applications to image analysisand automated cartography[J].Communications of the ACM，1981，24（6）：381-395.

[11]Matas J，Chum O，Urban M，et al.Robust wide-baseline stereo from maximally stable extremal regions[J].Image Vision Computing，2004，22（10）：761-767.

[12]孫晶.圖像局部不變特征提取技術研究及其應用[D].遼寧大連：大連理工大學，2009.

[13]廉藺，李國輝，王海濤，等.基于MSER的紅外與可見光圖像關聯特征提取算法[J].電子與信息學報，2011，37（7）：1625-1631.

[14]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

[15]嚴磊，汪增福.基于多局部特征匹配的全自動圖像拼接[J].計算機應用與軟件，2010，27（10）：5-7.

[16]Mikolajczyk K，Schmid C.Scale&affine invariant interest point detectors[J].International Journal of Computer Vision，2004，60（1）：63-86.

[17]王永明，王貴錦.圖像局部不變性特征與描述[M].北京：國防工業出版社，2010：150-163.