劉芳萍，王 沛，馬 艷，張 倩

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 200234)

基于環(huán)境差異度的自適應(yīng)角點(diǎn)匹配算法

劉芳萍，王 沛，馬 艷，張 倩

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 200234)

基于圖像灰度梯度提取的Harris角點(diǎn)，由于角點(diǎn)近鄰處其灰度梯度的對(duì)比度不明顯而造成檢測(cè)定位偏差，從而導(dǎo)致角點(diǎn)的誤匹配率的提高。針對(duì)該現(xiàn)象提出了一種“虛影點(diǎn)”改進(jìn)，同時(shí)引入環(huán)境差異度作為評(píng)判原則，自適應(yīng)調(diào)整角點(diǎn)間的競(jìng)爭(zhēng)機(jī)制的殘酷度，結(jié)合奇異值分解最終達(dá)到優(yōu)勝劣汰的匹配效果。實(shí)驗(yàn)證明，該算法在不影響角點(diǎn)匹配速度的情況下，與其他算法相比對(duì)角點(diǎn)的匹配精度有很大的改善。

Harris匹配；虛影點(diǎn)；環(huán)境差異度

這些算法都在一定程度上提高了角點(diǎn)的匹配精度，但是應(yīng)用于雙目立體圖像對(duì)的角點(diǎn)匹配中效果并不理想，這是由于角點(diǎn)近鄰處其灰度梯度的對(duì)比度不明顯而造成檢測(cè)定位偏差，只能通過(guò)后續(xù)的RANSAC[6]進(jìn)行篩選， 實(shí)現(xiàn)特征點(diǎn)的精匹配。因此，本文模仿貪婪搜索策略提出角點(diǎn)匹配的“虛擬點(diǎn)”假設(shè)，從而擴(kuò)大候選點(diǎn)集的規(guī)模，同時(shí)引入環(huán)境差異度作為衡量候選集中對(duì)象的競(jìng)爭(zhēng)度，自適應(yīng)地調(diào)整匹配的代價(jià)函數(shù)，再結(jié)合奇異值分解算法，提高算法的運(yùn)算速度和精度，最終達(dá)到較高精度的匹配效果。

1 角點(diǎn)匹配的“虛影點(diǎn)”假設(shè)

雙目圖像中角點(diǎn)的立體匹配，其實(shí)就是對(duì)調(diào)整后的雙目立體圖像對(duì)的左圖L和右圖R進(jìn)行Harris角點(diǎn)檢測(cè)后[7]，分別將L圖和R圖中的角點(diǎn)放入集合PCL，PCR

(1)

(2)

式中：Ii為左圖中的角點(diǎn)；Jj為右圖中的角點(diǎn)。然后，取集合PCL中的角點(diǎn)Ii分別與集合PCR中的角點(diǎn)Jj，以兩個(gè)角點(diǎn)W×W鄰域中像素關(guān)系建立匹配代價(jià)函數(shù)[8]進(jìn)行篩選匹配，匹配的效果主要取決于候選的角點(diǎn)集、搜索策略以及代價(jià)函數(shù)的建立。目前常見的角點(diǎn)匹配算法應(yīng)用于雙目立體圖像中通常會(huì)出現(xiàn)如圖1所示的誤匹配現(xiàn)象：左邊的角點(diǎn)A錯(cuò)誤地匹配到了右邊的C點(diǎn)。

圖1 Bowling中的截圖

其主要原因：一是獲得的角點(diǎn)位置是像素級(jí)的；二是在某些被判定為角點(diǎn)的相鄰像素也具有角點(diǎn)特性，但是在檢測(cè)的時(shí)候選擇最優(yōu)又排除了近鄰。為此本文提出角點(diǎn)的“虛影點(diǎn)”假設(shè)，其主要原理是：Harris角點(diǎn)從定義上講就是表征圖像中灰度在多方向上變化最劇烈的點(diǎn)，但是鑒于雙目圖像對(duì)在亮度、對(duì)比度和拍攝角度上的差異，往往兩幅圖像中相應(yīng)角點(diǎn)的定位并不在一條直線上?！疤撚包c(diǎn)”假設(shè)就是模擬貪婪搜素的原理，假設(shè)角點(diǎn)J的八通道方向上存在角點(diǎn)j，則兩者之間的關(guān)系滿足

(3)

式中：m和n的取值為-1，0，1。若t

對(duì)圖1右側(cè)引入角點(diǎn)的“虛影點(diǎn)”假設(shè)，并歸為PCR集合中，可以擴(kuò)大候選集的規(guī)模，促進(jìn)角點(diǎn)間競(jìng)爭(zhēng)的強(qiáng)度，通過(guò)個(gè)體競(jìng)爭(zhēng)進(jìn)一步提高角點(diǎn)匹配的精度。

河套灌區(qū)淖爾水滴灌調(diào)蓄能力及發(fā)展方式分析……………………………………… 徐 冰，田德龍，李澤坤，任 杰，湯鵬程（44）

2 改進(jìn)的匹配代價(jià)函數(shù)

為了進(jìn)一步提高角點(diǎn)匹配的精度和速度，避免相似紋理導(dǎo)致的誤匹配現(xiàn)象，本文提出了一種新的參量：環(huán)境差異度。其定義如下

(4)

(5)

(6)

(7)

式中：M和N分別表示Ii和Jj角點(diǎn)鄰域A中的元素個(gè)數(shù)；a1m和b1n分別表示A中的像素；Ii和Jj為中心點(diǎn)像素；Bij和Cij同式(7)。該算法一方面可以節(jié)省求均值的時(shí)間，另一方面所求的相關(guān)系數(shù)值更多地關(guān)注到要匹配的角點(diǎn)與其鄰域點(diǎn)的關(guān)系，這樣可以避免由于窗口選擇的大小原因，或者是窗口中與中心像素差距大的像素影響到窗口內(nèi)的平均值，使待匹配的兩個(gè)角點(diǎn)鄰域窗口中平均值差距變大，從而影響角點(diǎn)匹配的相關(guān)系數(shù)。

圖2 權(quán)重分配圖

同時(shí)，本文考慮到左右圖像中相匹配角點(diǎn)的深度不能超過(guò)深度值d的最大限度，建立一個(gè)懲罰因子，再結(jié)合奇異值分解算法，構(gòu)造相似矩陣G，其中Gij表示為

(8)

式中：Gij代表相似度的值；λ1，λ2，λ3為權(quán)重因子；γ為懲罰因子，其值根據(jù)角點(diǎn)Ii和Jj橫坐標(biāo)之差來(lái)決定；設(shè)兩個(gè)角點(diǎn)的橫坐標(biāo)分別為ix和jx，圖像的最大深度為Dmax，γ表示為

(9)

根據(jù)矩陣G進(jìn)行奇異值分解，利用奇異值分解進(jìn)行特征匹配是由Pilut進(jìn)一步改進(jìn)并用于立體視覺匹配中的[8]，其主要步驟為：將特征點(diǎn)相似度矩陣G分解之后得到兩個(gè)正交距陣T，U，表達(dá)如下

G=TDUT

(10)

式中：G為M×N矩陣；T為M×M方陣；U為N×N矩陣，它們?yōu)檎痪仃?；矩陣D為M×N的對(duì)角矩陣。注意此時(shí)將D中的對(duì)角線元素不為0的賦值為1，得到矩陣E，此時(shí)得到新的匹配矩陣為

P=TEUT

(11)

把所判斷的Pij值既是行最大，又是列最大的點(diǎn)作為最匹配的點(diǎn)。奇異值分解算法既滿足角點(diǎn)匹配的相似性準(zhǔn)則，又滿足唯一性準(zhǔn)則。同時(shí)，它在對(duì)角點(diǎn)進(jìn)行匹配時(shí)，不需要嚴(yán)格地執(zhí)行左圖中的每個(gè)角點(diǎn)必須與右圖中的角點(diǎn)至少一點(diǎn)匹配。

3 試驗(yàn)結(jié)果比較

本文選取Middleburry提供的矯正過(guò)的bowling和cone這兩幅圖，在Visual 2010軟件上進(jìn)行試驗(yàn)。這兩幅圖中，前者紋理相對(duì)較少，而后者紋理相對(duì)較多。本文采用文獻(xiàn)[9]中方法對(duì)Harris角點(diǎn)進(jìn)行檢測(cè)，結(jié)合上述的角點(diǎn)檢測(cè)和匹配代價(jià)函數(shù)原理，選擇λ1，λ2，λ3分別為0.5，0.3，0.2，A為5×5，B為11×11，C為15×15，分別獲得了如圖5、圖8的試驗(yàn)結(jié)果，并與文獻(xiàn)[10]提出的一種基于Harris-Susan的角點(diǎn)匹配算法，以及文獻(xiàn)[11]所提出的改進(jìn)的基于Canny-Harris-SIFT的角點(diǎn)匹配算法進(jìn)行對(duì)比，如圖3、圖4、圖6、圖7所示。比較這些圖，本文算法的匹配點(diǎn)增多的同時(shí)誤匹配點(diǎn)反而變少了。這里對(duì)改進(jìn)后的bowling匹配圖相同位置截圖，如圖9所示，角點(diǎn)A正確匹配到了角點(diǎn)B，匹配效果大大改善。

圖3 文獻(xiàn)[10]算法的bowling匹配圖

圖4 文獻(xiàn)[11]算法的bowling匹配圖

圖5 本文算法的bowling匹配圖

圖6 文獻(xiàn)[10]算法的cone匹配圖

圖7 文獻(xiàn)[11]算法的cone匹配圖

圖8 本文算法的cone匹配圖

圖9 改進(jìn)后的bowling中的截圖

根據(jù)上述bowling圖像和cone圖像的結(jié)果對(duì)照，分別列出表1、表2算法的效果對(duì)比。

表1 bowling圖像算法效果對(duì)比

表2 cone圖像算法效果對(duì)比

對(duì)比表1、表2的各項(xiàng)數(shù)據(jù)，針對(duì)低紋理和多紋理圖像，文獻(xiàn)[10]中提出的算法相對(duì)比較穩(wěn)定，但是正確的匹配點(diǎn)對(duì)不多，效率也不高，而文獻(xiàn)[11]中提出的算法經(jīng)過(guò)極線約束后，相匹配的點(diǎn)數(shù)變少了，從匹配率上看，該算法更適用于紋理較少的，對(duì)比度明顯的圖像。而本文算法針對(duì)低紋理和多紋理圖像的匹配效率相對(duì)比較穩(wěn)定，不論在匹配的點(diǎn)數(shù)還是正確率上都優(yōu)于另外兩種算法[12]。

4 結(jié)論

本文針對(duì)雙目立體圖像對(duì)進(jìn)行的角點(diǎn)“虛影點(diǎn)”假設(shè)，能夠有效地?cái)U(kuò)大候選點(diǎn)的規(guī)模，將待匹配的角點(diǎn)對(duì)數(shù)成倍地提高，同時(shí)改進(jìn)的匹配代價(jià)函數(shù)利用窗口區(qū)域劃分權(quán)重、引入懲罰因子改善算法的計(jì)算量，能夠進(jìn)一步篩選出最匹配的角點(diǎn)對(duì)。經(jīng)過(guò)試驗(yàn)證明，本文算法對(duì)試驗(yàn)的兩幅圖像都有比較好的匹配效率，能夠克服低紋理圖像匹配點(diǎn)少以及多紋理圖像誤匹配率高的不足，具有很廣的應(yīng)用范圍。同時(shí)，本文算法所匹配的角點(diǎn)具有很高的精確性，適合與模板匹配或遺傳算法、粒子群算法相結(jié)合，從而進(jìn)一步提取立體圖像的深度圖。

[1]白明，莊嚴(yán)，王偉.雙目立體匹配算法的研究與進(jìn)展[J].控制與決策，2008，29(7)：724-729.

[2]HARRIS C，STEPHENS M. A combined corner and edge detector[C]//Proc. 4th Alvey Vision Conference.Manchester，UK：[s.n.]，1998：21-51.

[3]趙峰，黃慶明，高文.一種基于奇異值分解的圖像匹配算法[J].計(jì)算機(jī)研究與發(fā)展，2010，47(1)：23-32.

[4]李海超，張廣軍.基于旋轉(zhuǎn)不變的角點(diǎn)匹配方法[J].紅外與激光工程，2008，37(3)：562-564.

[5]劉寧盧，榮勝.基于高斯曲面模型的亞像素Harris角點(diǎn)定位算法[J].電子測(cè)量技術(shù)，2011，34(12)：43-50.

[6]FUSIELLO A，TRUCCO E， VERRI A. A compact algorithm for rectication of stereo pairs[J].Matching Vision and Application，2000，12(1)：16-22.

[7] MCDONNEL M. Box-filtering techniques[J]. Computer Graphics and Image Processing，1981，17(1)：65-70.

[8] YOON K，KWEON I. Adaptive support-weight approach for correspondence search[J]. IEEE Trans. PAMI，2006，28(4)：650-656.

[9]王民鋼，王超.基于Harris的角點(diǎn)檢測(cè)改進(jìn)算法[J].計(jì)算機(jī)仿真，2012，29(11)：294-298.

[10]周舒篁，袁杰.一種有效的角點(diǎn)檢測(cè)與匹配算法[J].現(xiàn)代電子技術(shù)，2010，135(4)：45-48.

[11]江祥奎，王曙光.基于Canny-Harris-SIFT算法的立體匹配[J].機(jī)床與液壓，2013，41(13)：60-63.

[12]LIU Fangping,WANG Pei.An improved stereo matching algorithm based on corner points[C]//Proc.ICALIP 2014.Shanghai:IEEE Press,2014:120-123.

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

Adaptive Corner Matching Algorithm Based on Environment Difference

LIU Fangping，WANG Pei，MA Yan，ZHANG Qian

(CollegeofMechanicalandElectronicEngineering，ShanghaiNormalUniversity，Shanghai200234，China)

The corners of Harris extracted based on the image gray gradient always have detection bias，because of the unclear gray gradient near the corners. In this paper，the “virtual” corner are proposed， and the environmental difference are introduced as a criterion. They can adjust the cruel of the competitive mechanism between corners adaptively. And they can reach a good matching result by combining with singular value decomposition. Experiments show that， this algorithm not only does not affect the corner matching speed， but also the matching precision of corner points have greatly improved.

Harris matching；virtual corner；environmental difference

國(guó)家自然科學(xué)基金項(xiàng)目(61373004)

TP391

A

10.16280/j.videoe.2015.01.006

2014-02-22

【本文獻(xiàn)信息】劉芳萍，王沛，馬艷，等.基于環(huán)境差異度的自適應(yīng)角點(diǎn)匹配算法[J].電視技術(shù),2015，39(1).