基于圖像尺度變化的一種特征點(diǎn)匹配算法

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

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

基于圖像尺度變化的一種特征點(diǎn)匹配算法

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

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

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

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

1 特征點(diǎn)匹配

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

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

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

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

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

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

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

3.1 歐氏距離

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

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

3.2 梯度算法

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

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

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

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

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

3.3 本文提出的改進(jìn)的特征點(diǎn)匹配算法

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

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

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

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

圖1 改進(jìn)的匹配算法的基本流程圖

4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

:

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

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

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

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

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

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

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

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

趙 謙（1977— ），副教授，主要從事智能化圖像處理及虛擬化現(xiàn)實(shí)應(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

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

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

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

王奕婷（1987— ），女，碩士生，主要研究方向?yàn)閳D像的三維重建;

責(zé)任編輯:時(shí) 雯

2013－03－19