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

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

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

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

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

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

歐氏距離;相關(guān)法;特征點梯度;尺度變化

1 特征點匹配

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

2 基于灰度的相關(guān)匹配算法［7－8］

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

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

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

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

3 相關(guān)算法理論

3.1 歐氏距離

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

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

3.2 梯度算法

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

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果及分析

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

圖2 傳統(tǒng)的灰度相關(guān)法匹配算法的結(jié)果（旋轉(zhuǎn)）

圖3 改進的匹配算法的結(jié)果圖（旋轉(zhuǎn)）

圖4 傳統(tǒng)的灰度相關(guān)法匹配算法的結(jié)果（旋轉(zhuǎn)+縮放）

圖5 改進的匹配算法的結(jié)果圖（旋轉(zhuǎn)+縮放）

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

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

5 結(jié)語

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

:

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

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

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

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

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

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

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

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

趙 謙（1977— ），副教授，主要從事智能化圖像處理及虛擬化現(xiàn)實應(yīng)用相關(guān)研究。

Feature Points Matching Algorithm Based on Image Scale Variations

ZENG Zhaohua1，WANG Yiting1，ZHAO Qian1，ZHAO Su2，F(xiàn)ENG 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］.電視技術(shù)，2014，38（3）.

陜西省科技研究發(fā)展計劃工業(yè)攻關(guān)項目（2013K07－35）;西安市科技計劃項目（CXY1343（4）;CX1258⑤;CX1258⑥）;陜西省教育廳科研計劃項目（12JK0508;12JK0535）;西安市碑林區(qū)應(yīng)用技術(shù)研發(fā)項目（GX1209;GX1311;GX1310）

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

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

責(zé)任編輯:時 雯

2013－03－19