基于圖像尺度變化的一種特征點匹配算法

曾召華，王奕婷，趙 謙，趙 肅，馮 瑞，毛昕蓉

（1.西安科技大學通信學院，陜西西安 710054;2.西安市政設施管理局，陜西西安 710003;3.中國水電顧問集團西北勘測設計研究院，陜西西安 710065）

基于圖像尺度變化的一種特征點匹配算法

曾召華1，王奕婷1，趙 謙1，趙 肅2，馮 瑞3，毛昕蓉1

（1.西安科技大學通信學院，陜西西安 710054;2.西安市政設施管理局，陜西西安 710003;3.中國水電顧問集團西北勘測設計研究院，陜西西安 710065）

通過對灰度相關法特征點匹配算法的理論研究和實驗分析，提出了一種能夠克服圖像尺度變化的特征點匹配算法。該算法主要根據圖像特征點間歐氏距離的關系，結合傳統的特征點灰度相關法和特征點的梯度相關法進行精確匹配。實驗證明，該算法容易理解，易于實現，匹配結果較精確，誤匹配點較少。

歐氏距離;相關法;特征點梯度;尺度變化

1 特征點匹配

特征點匹配［1］是計算機視覺中的關鍵技術，在運動估計、圖像識別等領域有著重要的應用。特征點是圖像局部灰度值發生劇變的點，包含豐富的圖像信息，特征點匹配就是對圖像上提取的特征點在另一圖像上找到該特征點的精確位置?；谏鲜鲆蛩兀疚奶岢隽嗽贖arris特征點提取［2］的結果上再進行匹配算法驗證的思路。而傳統的基于圖像灰度的相關匹配算法［3－5］主要是逐像素地把一個以一定大小的實時圖像窗口的灰度矩陣與參考圖像對應位置的窗口灰度陣列按某種相似性度量方法進行搜索比較，尋找出相關性最大的點。但經典相關匹配算法的運算量大，對尺度變化后的圖像進行特征點匹配精確度較差，在一定程度上影響了它的實用性。因此探索易理解、易實現的能夠克服尺度變化的圖像特征點匹配算法是必要的。本文提出的匹配算法，主要利用兩幅圖像特征點間歐氏距離［6］的關系來確定匹配點集，極大地減少了灰度相關計算的次數，也排除了一部分的誤匹配點，并使用特征點的梯度相關法進行精確匹配，結果達到了較好的精確效果。

2 基于灰度的相關匹配算法［7－8］

在檢測出特征點之后，利用角點矩形領域窗口內像素的灰度信息，通過互相關函數來判斷是否匹配。兩幅圖像不同特征點的相似程度采用互相關函數來評價，互相關關系定義為

式中:是圖像Ik上點（u，v）的鄰域灰度平均值;σ（Ik）是圖像Ik中（2n+1）×（2m+1）鄰域內點的標準偏差。R值越大，說明兩個特征點越相似。

對于圖像I1上的特征點m1和圖像I2上的特征點m2，圖像坐標分別為（u1，v1）和（u2，v2），給定以m1為中心的相關性窗口（2n+1）×（2m+1），在I2相應于m1的位置選定（2du+1）×（2dv+1）的搜索窗口，通過上述的互相關公式計算所有在搜索窗口內的特征點m2與m1的相關系數，最后為計算出來的相關系數設定閾值k來判斷，在計算結果大于設定的閾值時，認為兩點是相互匹配的點。

雖然，這種相關法匹配容易理解并實現，但是，它在理論上假定了兩幅圖像沒有光照的變化，同時沒有太大的平移和旋轉，無法精確做到發生尺度變化后的圖像匹配。這樣必然限定了該算法的應用范圍，同時固定的閾值導致了整個系統的誤判性增高，大的閾值使得很多匹配點被漏檢，小的閾值導致更多的一對多的誤匹配點出現。

3 相關算法理論

3.1 歐氏距離

在二維圖像當中的歐氏距離主要是指兩點之間的距離，本文采用歐氏距離主要是來計算一幅圖像中兩個特征點的距離，計算公式為

式中:（x1，y1）和（x2，y2）是一幅圖像特征點集中的點;d是在該圖像上的兩點之間的歐氏距離。考慮到圖像特征點之間最為直接的關系就是距離的關系，因此，無論需要匹配的兩幅圖像有無尺度變化，它們在特征點之間距離關系上是不會變的。本文采用歐氏距離來約束特征點集的匹配，主要思想是在第一幅圖像上如果離特征點A最近的距離就是特征點B，那么在對應需要匹配的另一幅圖像上肯定有與A匹配的點A1，如果特征點A與特征點A1是正確的匹配點，那么在A1對應的圖像上必然能找到距離A1最近的點，該點有可能就是B所匹配的點。

3.2 梯度算法

圖像的梯度在圖像的邊緣檢測，圖像濾波等方面的應用已十分成熟，本文主要是把梯度作為圖像特征點匹配的一個新的衡量標準，主要考慮如果兩幅圖像上的某個點是匹配的，那么它們各自的梯度值應該是相關的。

在計算圖像梯度時，主要是把圖像看成二維離散函數，圖像的梯度其實就是二維離散函數的求導，即

式中:G（i，j）就是梯度值;dx和dy分別是二維圖像的兩個方向的導數值;I是圖像像素的值;（i，j）為像素的坐標。不過，圖像梯度一般也可以用中值差分來計算，即

本文主要利用匹配特征點的梯度相關性來實現特征點的匹配。首先，分別計算兩幅圖像特征點的梯度，然后對需要匹配的特征點集進行梯度相關性的計算，梯度相關性計算主要利用相關法的計算公式，只是把灰度值的相關性比對變成梯度值的相關性比對，見式（8）。最后，計算出相關系數R，R越大，則相關性越大。

其中，各部分的計算方法同灰度相關法計算方法類似，在這里不再贅述。

3.3 本文提出的改進的特征點匹配算法

1）對于獲得的兩幅圖像的特征點集，首先需要對每組點集進行去除相同坐標點的初始化處理。然后，選擇初始的第一組精準的匹配點，該初始的匹配點組可以在基于一幅圖像的一個特征點的基礎上，通過手動地自助選擇另一幅圖像上對應點，主要操作是通過主動觀察的方法，選定相對應需要匹配的特征點在這幅圖像上大概的匹配位置，獲得一些對應的匹配點集。

2）開始對步驟1）產生的一對多的點集進行細化，首先用灰度相關法計算每兩個點之間的灰度相關系數，該相關系數小于閾值k時，認為原計算的那個點是誤匹配點，從而去除部分誤匹配點，然后對剩余點用梯度相關法來精確匹配點，主要是通過計算兩點之間的梯度相關系數，如果該系數大于閾值l，則認定該點為對應的匹配點。這樣，最終獲得初始的、精確的、一對一的匹配點。

3）在獲得初始的一組精確的匹配點組后，在第一幅圖像上用歐氏距離來計算離第一個匹配成功的特征點最近的點，該點被確定為需要匹配的第二個點。針對這個需要匹配的點，在第二幅圖像上同樣尋找離第一個匹配成功的特征點最近的點，因為需要考慮圖像發生尺度變化后可能引起的圖像畸變，因此，在這幅圖像上把該最近的距離的n倍作為閾值g，計算第一個點到其他點的歐氏距離，把在這個閾值g范圍內的點認為是第一幅圖像上第二個點可能匹配的點。然后按照步驟2）一對多地匹配點的方法來精確匹配點。

4）剩余的兩幅圖像上的特征點集，按照步驟3）的方法處理，直到特征點全部匹配完成。實現的算法流程圖如圖1所示。

圖1 改進的匹配算法的基本流程圖

4 實驗結果及分析

本文采用了MATLAB2011版本工具對新算法和經典的灰度相關匹配算法進行仿真實驗。兩幅圖中需要對300個特征點對進行匹配，但為了在圖像中能清楚看到匹配結果，避免過多的線被遮擋，所以在圖中選用部分點來顯示。圖2與圖3是在旋轉尺度變化下，按照傳統的灰度相關法所進行的特征點匹配結果圖和改進算法所進行的特征點匹配結果圖。圖4與圖5是在旋轉和縮放同時變化下傳統的灰度相關法所進行的特征點匹配結果圖和改進算法所進行的特征點匹配結果圖。表1為兩種算法的比較。

圖2 傳統的灰度相關法匹配算法的結果（旋轉）

圖3 改進的匹配算法的結果圖（旋轉）

圖4 傳統的灰度相關法匹配算法的結果（旋轉+縮放）

圖5 改進的匹配算法的結果圖（旋轉+縮放）

表1 兩種算法在時間和匹配結果上的對比

結合圖2～圖5和表1明顯可看出，灰度相關法在對尺度變化的圖像中匹配特征點應用上基本失效，同時，從本文改進算法的實驗結果可知，仍存在極少數的誤匹配點，但是與傳統算法的匹配結果相比，獲得了比較理想的結果，不過也同樣增大了運算的時間復雜度。

5 結語

本文在傳統的灰度相關法匹配特征點的思想上，提出了可以克服圖像尺度變化的特征點匹配的算法，該算法在實現和理解上都比較簡單，結果也比較理想。但同時為獲得更簡單、實用以及具有更好魯棒性的特征點匹配算法，本文算法還需進行深入研究。

:

［1］陳君，戚飛虎.一種新的基于特征點的立體匹配算法［J］.中國圖象圖形學報，2005，10（11）:1411－1414.

［2］涂春萍，柴亞輝，李廣麗，等.一種基于Harris角點特征精確匹配的圖像拼接方［J］.實驗室研究與探索，2011，30（10）:41－43.

［3］陳淑蕎.數字圖像特征點提取及匹配的研究［D］.西安:西安科技大學，2009.

［4］張汗靈，郝重陽.基于特征的自動圖像配準算法［J］.電視技術，2003，27（9）:40－43.

［5］薛菲，張榮國，張建國，等.基于NCC與SSDA的快速特征點匹配融合算法［J］.計算機與數字工程，2010，38（10）:19－21.

［6］魏志強，黃磊，紀筱鵬.基于點特征的序列圖像匹配方法研究［J］.中國圖象圖形學報，2009，14（3）:525－530.

［7］尹丹，滿家居，王梓豪.一種改進的點特征圖像匹配算法［J］.計算機與現代化，2008（3）:71－76.

［8］宋曉闖.基于灰度和幾何特征的圖像匹配算法研究［D］.天津:河北工業大學，2008.

趙 謙（1977— ），副教授，主要從事智能化圖像處理及虛擬化現實應用相關研究。

Feature Points Matching Algorithm Based on Image Scale Variations

ZENG Zhaohua1，WANG Yiting1，ZHAO Qian1，ZHAO Su2，FENG Rui3，MAO Xinrong1

（1.School of Communication and Information Engineering，Xi’an University of Science and Technology，Xi’an 710054，China;2.Xi’an Municipal Facilities Administration Bureau，Xi’an 710003，China;3.HYDRO China Xibei Engineering Corporation，Xi’an 710065，China）

A feature point matching algorithm which can overcome the image scale change is proposed by theoretical research and experimental analysis of feature points matching algorithm of gray correlation method.It is mainly based on the relationship of Euclidean distance of image feature points combined with the traditional gray correlation method of feature points and the gradient correlation method of feature points to precise matching.Experiments prove that it is easy to understand，easy to implement，have more accurate matching results and less false matching points.

euclidean distance;correlation method;gradient feature points;scale change

TN911.73;TP751

A

【本文獻信息】曾召華，王奕婷，趙謙，等.基于圖像尺度變化的一種特征點匹配算法［J］.電視技術，2014，38（3）.

陜西省科技研究發展計劃工業攻關項目（2013K07－35）;西安市科技計劃項目（CXY1343（4）;CX1258⑤;CX1258⑥）;陜西省教育廳科研計劃項目（12JK0508;12JK0535）;西安市碑林區應用技術研發項目（GX1209;GX1311;GX1310）

曾召華（1972— ），副教授，主要從事3G移動通信關鍵技術研究;

王奕婷（1987— ），女，碩士生，主要研究方向為圖像的三維重建;

責任編輯:時 雯

2013－03－19