基于特征序列匹配函數的快速圖像匹配

鄭興明

(南京航空航天大學計算機科學與技術學院，江蘇 南京 210016)

利用圖像信息對目標物體進行搜尋和攻擊，在當前越來越受到重視，特別是在航空航天、軍事打擊、醫學手術中的應用，其準確性，精確性和實時性一直是該領域的主要研究方向。圖像信息除了包含內容的局部信息，還包含內容之間相互關系的全局信息，局部信息特征表述了目標特征區域的信息，如圖像的直線、顏色特征、角度、輪廓以及這些特征之間的相互關系。全局特征描述的是整個圖像的信息，如圖像的灰度直方圖等。圖像全局特征信息在某些細節上淡化了局部目標區域的細節特征，不能體現匹配的結果，利用圖像的局部特征進行匹配越來越受到重視，并成為計算機視覺領域的熱點。

目前針對圖像匹配的主要方法有基于像素點匹配的歸一化積相關灰度匹配、序貫相似性檢測匹配(Similarity Sequential Detection Algorithm，SSDA)、基于特征匹配的［1］(Scale － Invariant Features Transform，SIFT)和仿射不變特征點提取方法 Harris－ Affine［2－4］。模板匹配的主要思想是將待匹配的圖像作為模板圖像，以窗口的方式，在待查找的源圖像中掃描一遍，通過該模板所對應區域的圖像與模板圖像之間的相似距離來判斷識別的結果。序貫相似性檢測匹配主要解決模板匹配算法計算量大的問題，模板匹配每滑動一次就要做一次匹配運算，除了匹配點外在其他匹配點做了“無用功”，導致匹配算法計算量上升，一旦發現所在的參考位置為非匹配點，立刻換到新的參考點計算，加大匹配速度。SIFT方法能夠從匹配圖像中提取顯著不變特征，使不同視角目標或場景圖像穩定匹配，該特征向量對圖像尺度、旋轉變化、噪聲和光照變化不敏感。由于SIFT對目標遮擋和圖像混雜穩定性較強，因此在目標識別中取得良好效果。仿射不變特征方法主要解決大視角變化的圖像匹配問題，在仿射高斯空間的基礎上，用多尺度Harris特征點，檢測算子提取適應仿射變換的特征點，然后用特征點的橢圓鄰域代替圓形鄰域。通過迭代估計特征點鄰域的仿射形狀，不斷調整特征點所在的尺度、位置和形狀收斂直到不變為止，最終得到仿射不變特征向量。利用像素點進行匹配的主要缺陷是計算量過大，對圖像的灰度變換敏感，尤其是非線性的光照變化。此外，對目標的旋轉，變形以及遮擋也比較敏感［5］。因而基于像素點匹配的方法不適合實際場景中的應用，為克服這些缺點，可以利用圖像的特征進行匹配，一方面圖像的特征點比像素點要少，減少了匹配過程的計算量。另一方面局部特征點［6］的匹配度量值對位置的旋轉、變形以及遮擋不是很敏感，可以大大提高匹配的精度。而且特征點的提取過程可以減少噪聲的影響，對灰度變化，圖像變形以及遮擋等有較好的適應能力。文中采用失配函數的思想，解決像素點計算量過大的缺陷，同時利用局部特征匹配的優勢，提高圖像匹配的精確度和執行速度。

1 尺度不變特征

尺度不變特征(Scale－Invariant Feature Transform，SIFT)是一種計算機視覺用于偵測與描述圖片中局部特征的，它在空間尺度中尋找極值點，并提取出其位置、尺度、旋轉不變量等相關特征。

局部特征的描述與偵測可以幫助識別物體，SIFT特征是基于物體上一些局部外觀的興趣點，而與影像的大小和旋轉無關。對于光線、噪聲、些微視角改變的容忍度較高?；谶@些特性，它們是高度顯著而且相對容易擷取，在龐大的特征數據庫中，容易辨識物體且鮮有誤認。使用SIFT特征描述對于部分物體遮蔽的偵測率也較高，甚至只需要3個以上的SIFT物體特征就能計算出位置與方位。在現今的計算機硬件速度下和小型的特征數據庫條件下，辨識速度可接近即時運算。SIFT特征的信息量大，適合在海量數據庫中快速準確匹配。

SIFT架構中的特征點是利用不同尺度下高斯濾波器(Gaussian Filters)進行卷積(Convolved)，然后利用連續高斯模糊化差異，根據不同尺度下的高斯差(Difference of Gaussians)中最大最小值導出，其公式如下

其中，L(x，y，kiσ)是在尺度 kiσ 的條件下，由原始圖像I(x，y)與高斯模糊 G(x，y，kσ)進行卷積

G(x，y，kσ)是尺度可變高斯函數

為減少噪聲對特征點的影響，避免將邊緣附近的點也誤認為是特征點，采用Hessian［7］矩陣對極值點進行過濾，其公式如下

在得到特征點的尺度和位置信息后，為使特征點描述向量對旋轉不變，需要為特征點分配角度信息。計算特征點梯度大小 m(x，y)和角度 θ(x，y)。

最后利用特征點的梯度方向構建一個36 bin的角度直方圖，直方圖的峰值代表局部梯度的主方向。以特征點為中心取16×16個像素的窗口，分成16個4×4的子塊，在每個 4 ×4 的子塊上計算 0°，45°，90°，135°，180°，225°，270°，315°這 8 個方向的梯度大小和梯度方向直方圖。因此，一個4×4的子塊可以得到一個8方向描述符，則16個4×4的子塊可以得到128個方向描述符，這個1×128的向量就定義為特征描述符向量。如圖1所示分別在不同像素下提取的SIFT匹配特征，圖1(a)是相同大小測試圖像和匹配圖像，分辨率較低，其特征點的個數只有5個，圖1(b)特征點的個數為32個，圖1(c)特征點個數為43個，圖1(d)特征點個數為106個。

圖1 SIFT在不同分辨率圖像下的特征匹配

2 匹配函數

文中提出的匹配函數［8］是利用匹配本身的特征信息來決策出重新進行匹配的起始點。假設特征序列構成的描述符向量可以表示為一串由字母組成的字符串:P=abcabcacab，同樣查找圖像的特征序列也被表示成一串很長的字符串:S=…abacbdfe…，問題轉變為在主串S中查找出是否具有P特性的匹配串。

令S=s0s1…sm－1是主串，要確定P是否在si開始處匹配。如果si≠a則接下來顯然要用si－1與a比較。同理，若si=a且si+1≠b，則接下來要用si+1與a比較。若sisi+1=ab且si+2≠c，則有以下情形

其中，“?”表示S在該位置的值是多少無關緊要。第一個“?”表示si+2且si+2≠c，下一次應該用P的第一個字符直接與si+2比較，而不是與si+1比較，因為P的特征序列的第2個字符b與S中si+1相等，一定有si+1≠a。假定P的前4個特征字符和S匹配，但下一個特征字符失配，即si+4≠b

此時應該用si+4與P的第2個特征字符進行比較，等效于把P向右滑動，使它的子串對準S的一個子串，然后比較兩個相等子串后面的第一個字符?？梢缘贸?，根據特征字符串P中的字符信息，以及匹配失效主串的字符位置，可以確定接下來應該用特征字符串中的哪個特征字符和主串的當前失配字符繼續比較，而無需回去比較主串的較前位置字符。

特征串p=p0p1…pn－1的匹配函數定義為

由定義可得，如果部分匹配結果是 si－j…si－1=p0p1…pj－1且 si≠pj，則接下來如果 j≠0，應該用 si與pf(j－1)+1相比;如果 j=0，用 p0與 si+1相比。

3 算法執行

圖像匹配的過程是目標圖像在測試圖像中查找相似特征的目標。首先將目標圖像分割，假設目標圖像的大小是M×N，對圖像長M進行m等分，對圖像寬N進行n等分，這樣目標圖像就被分割成m×n個大小模塊的子圖像，每個子圖像的大小為，同樣對測試圖像進行相同的處理。處理結果如圖2所示。

圖2 分割為m×n大小的目標圖像

分割好的目標圖像分別計算SIFT局部特征，將計算完的特征按照圖像字塊的順序從左到右從上到下排列成一行序列，其長度為m×n，目標圖像就被表示成了一串具有SIFT特征的序列串，每個串的值代表了當前分塊子圖像的細節特征表述，如圖3所示。

圖3 SIFT提取映射后的特征序列

分塊子圖像的SIFT特征是1×128個特征向量描述符。它包含了該子圖像的特征信息，由于每個子圖像包含的細節不相同，保證了特征序列間沒有太大的關聯性，同時子圖像內容之間是連續的，特征序列之間又保持著關聯性。同樣測試圖像也按照上述方法進行分割，在測試圖像匹配目標圖像就轉變到在測試圖像特征序列里查找目標圖像的特征序列，SIFT提取出的特征向量表述符之間的相似性采用歐氏距離的來確定，設置某一閾值σ，當特征向量之間的歐氏距離＜σ時，判定這兩個特征向量之間是相似或者相近的，當特征向量之間的歐氏距離＞σ時，判定該特征向量之間不匹配，利用匹配函數重新定位新的匹配點，重新進行匹配，直至測試圖片整個特征序列結束。

算法執行流程如下:

(1)初始化測試圖片和目標圖片，分別將其轉化成灰度圖像。

(2)測試圖片和目標圖片分別分割成具有相同大小的子圖像，并按圖像內容組織成一行序列。

(3)分別對上述一行序列進行SIFT特征提取，以向量的形式存儲。

(4)計算測試圖片的特征序列和目標圖片的特征序列是否相近或相似，如果相似則繼續匹配，否則轉到(5)。

(5)利用匹配函數計算出在測試圖片中失效匹配點重新匹配的位置，重復(4)。

(6)測試圖像特征序列結束，輸出匹配序列。

4 實驗結果

本方法利用SIFT對目標分割子圖像進行特征提取，將提取出的特征按照子圖像分割的序列進行重構，目標圖像和測試圖像就轉換成一行具有特征描述符的序列，對特征描述符進行匹配函數計算，進行匹配過程。圖片大小直接影響到子圖像的分割和特征序列的生成，同時提高各個子圖像不同的特征序列之間的差異性，實驗圖片選取分辨率較高的1500×1500的測試圖片和分辨率為300×300的目標圖片，子圖像的大小為15×15，這樣測試圖片就被劃分為10000個特征序列，目標圖像被劃分為400個特征序列。特征序列之間的相似度和相近程度用歐氏距離來確定，實驗的過程中歐氏距離的誤差閾值σ≤20，當歐氏距離在這個范圍內，特征圖片匹配。實驗一方面從單張圖片匹配結果進行討論，另一方面從單張圖片在模板匹配方法，序貫相似性匹配方法和SIFT本身匹配進行比較。圖4顯示的是匹配的結果，圖4(b)中灰色區域為匹配的目標區域，如圖5所示，黑色為匹配結果，從圖中可以看出，除了目標區域被匹配，其他區域也被匹配，實驗過程中為了降低匹配函數帶來的負面影響，在最優情況下連續20個特征序列匹配，該20個特征序列就是匹配的區域，匹配過程中產生的其他匹配是因為在該20個特征序列內，其相似程度的歐氏距離都小于閾值σ≤20，由于增大了連續匹配成功的特征序列的長度以及減小特征序列的相似度的閾值，使得匹配的結果較為合理。實驗的目標區域特征為房屋建筑，具有棱角和直線的特征，在區域劃分很小的情況下很難區分出來，導致結果在房屋建筑上匹配有誤差。

圖4 分辨率為的測試結果

圖5 目標圖片

匹配函數在目的上解決了重新匹配的新配點的計算，同時又是以局部特征為匹配，而不是以單純的像素點來匹配，加大了匹配的速度，其匹配執行速度要高于模板匹配，序貫相似匹配方法和SIFT本身匹配進行比較，表1顯示了在上述匹配方法執行速度。

表1 3種匹配方法的執行速度

5 結束語

文中主要利用提出的匹配函數來對圖像匹配進行快速匹配，加快圖像匹配的速度，關鍵點在于子圖像的劃分和局部特征提取，子圖像的大小直接影響到局部特征的提取，子圖像太小，局部細節丟失嚴重，特征序列之間的相關性丟失，匹配函數匹配重復計算率提高，子圖像太大，特征序列之間相關性過大和寬度過短，匹配函數不起作用。局部特征提取才用SIFT特征提取，一方面SIFT特征在全局圖像匹配中具有良好的匹配結果，在其基礎上加快處理速度。因子圖像的劃分和相似度的閾值是根據仿真和先驗只是初步估算，接下來的工作主要研究子圖像大小的劃分和局部特征的提取，從圖像本身特征的角度自適應劃分子圖像的大小以及對其局部特征的提取。

［1］LOWE D G.Distinctive image features from scale－ invariant keypoints［J］.International Journal of Computer Vision(S0920 －5691)，2004，60(2):91 －110.

［2］MIKOLAJCZYK K，CORDELIA S.Scale ＆ affine invariant interest point detectors［J］.International Journal of Computer Vision(S0920 －5691)，2004，60(1):63 －86.

［3］MIKOLAJCZYK K，TUYTELAARS T，SCHMID C，et al.A comparison of affine region detectors［J］.International Journal of Computer Vision(S0920 － 5691)，2005，65(1):43－72.

［4］MIKOLAJCZYK K，CORDELIA S.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence(S0162 － 8828)，2005，27(10):1615－1630.

［5］ZHAO Zhenbing，WANG Rui.A method of infrared/visible image matching based on edge extraction［C］.International Congress on Image and Signal Processing，2010:871 －874.

［6］田金文，楊磊.基于局部分形特征的快速圖像匹配方法［J］.華中理工大學學報，1996，24(2):12 －14.

［7］劉小軍，楊杰.基于主成分分析的放射不變特征圖像匹配方法［J］.系統仿真學報，2004，20(4):977 －980.

［8］ELLIS H，SARTAJ S.Fundamentals of data structures in C［M］.2 ed.，Berlin:Springer Press，2003.