摘 要: 在雙目立體視覺系統(tǒng)中,圖像匹配是關(guān)鍵步驟之一。在眾多匹配算法中,歸一化互相關(guān)(NCC)算法由于具有精度高、魯棒性強(qiáng)等優(yōu)點(diǎn)得到廣泛應(yīng)用,但其計(jì)算量大、運(yùn)算速度較慢,使其難以在線應(yīng)用。為此,本文提出一種改進(jìn)的NCC立體匹配算法,通過引入積分圖像和平方積分圖像,將矩形窗口區(qū)域像素求和運(yùn)算轉(zhuǎn)化為四個(gè)像素點(diǎn)值的簡(jiǎn)單相加減,同時(shí)剔除基準(zhǔn)圖像中無法匹配區(qū)域以減小搜索范圍,使計(jì)算復(fù)雜度得到簡(jiǎn)化,計(jì)算量大為降低。實(shí)驗(yàn)證明,改進(jìn)后的NCC算法在保證匹配質(zhì)量的基礎(chǔ)上,執(zhí)行速度得到顯著提高,利于在線應(yīng)用。
關(guān)鍵詞: 圖像匹配;歸一化互相關(guān)(NCC); 積分圖像 ; 圖像處理
0 引言
雙目立體視覺是計(jì)算機(jī)視覺的一個(gè)重要分支,近年來,雙目立體視覺技術(shù)得到了大量研究[1],主要應(yīng)用在機(jī)器人導(dǎo)航、三維測(cè)量和虛擬現(xiàn)實(shí)等領(lǐng)域。雙目立體視覺系統(tǒng)的實(shí)現(xiàn)過程由圖像獲取、攝像機(jī)標(biāo)定、特征點(diǎn)提取、圖像匹配和三維立體重建等步驟組成[2]。圖像匹配本質(zhì)上是尋找兩幅圖像的相似性[3-4],是恢復(fù)三維立體場(chǎng)景的先決條件[5],是立體視覺系統(tǒng)中的關(guān)鍵技術(shù)之一。雙目立體視覺圖像匹配[6]技術(shù)是通過兩臺(tái)水平擺放的攝像機(jī)分別獲取兩幅圖像,并從中找出相同景物各像素點(diǎn)的對(duì)應(yīng)關(guān)系,得到其最佳視差值,最終獲得圖像視差圖的技術(shù)。
圖像匹配方法按照匹配基元不同可分為特征匹配[7]、相位匹配[8]和區(qū)域匹配[1,9]三種。特征匹配是針對(duì)提取的特征進(jìn)行描述,然后運(yùn)用所描述的參數(shù)進(jìn)行匹配的一類算法,計(jì)算量小,速度快,但是匹配效果受到圖像特征稀疏性的影響難以獲得致密視差圖。相位匹配是最近才發(fā)展起來的一類算法,能夠反映信號(hào)的結(jié)構(gòu)信息和抑制圖像的高頻噪聲,適用于并行處理存在相位奇點(diǎn)和相位卷繞問題的情況。區(qū)域匹配是基于局部窗口間灰度信息相關(guān)程度的匹配算法,常用的匹配相似度量函數(shù)有NCC(Normalized Cross Correlation,歸一化互相關(guān))、SAD(Sum of Absolute Differences,差絕對(duì)值和)和SSD(Sum of Squared Differences,差平方和)。這三種算法中,NCC算法最常用,它通過計(jì)算視差范圍內(nèi)基準(zhǔn)圖像與實(shí)時(shí)圖像對(duì)應(yīng)像素點(diǎn)間的相關(guān)性來獲取視差圖,相關(guān)系數(shù)一般在[-1,1]之間取值,該算法將搜索相關(guān)系數(shù)最大值對(duì)應(yīng)的視差作為最佳視差值,具有精度高、魯棒性強(qiáng)[10]的優(yōu)點(diǎn),缺點(diǎn)是計(jì)算量大、速度慢,在線應(yīng)用受到限制。
本文針對(duì)NCC算法的缺點(diǎn),通過在立體匹配中引入積分圖像和平方積分圖像,并且剔除基準(zhǔn)圖像中無法匹配區(qū)域,對(duì)原NCC算法進(jìn)行了改進(jìn),在保證匹配質(zhì)量的情況下,使匹配速度得到顯著提高,實(shí)驗(yàn)結(jié)果驗(yàn)證了該改進(jìn)算法的有效性和快速性[11]。
1 積分圖像及平方積分圖像
1.1 積分圖像
積分圖像(Integral Image)理論是Viola P.等于2001年提出的[12]。積分圖像是一種用于快速計(jì)算圖像某窗口區(qū)域灰度和的一種圖像中間表示,有較廣泛的應(yīng)用[13-15]。積分圖像中任意一點(diǎn)(i,j)的值用ii(i,j)表示,代表了源圖像中行數(shù)小于i、列數(shù)小于j的所有灰度值的和,即:
其中i(x,y)表示源圖像中(x,y)點(diǎn)的灰度值。令s(i,j)為源圖像中第i行、第j列的灰度值積分,則有:
s(i,j)=s(i,j-1)+i(i,j)(2)
ii(i,j)=ii(i-1,j)+s(i,j)(3)
利用式(2)和式(3)編程實(shí)現(xiàn)時(shí),應(yīng)該擴(kuò)展一行一列以確保i-1,j-1為正數(shù)。
如果要計(jì)算原始圖像中頂點(diǎn)依次為A、B、C、D的矩形窗口,只需將原圖像遍歷一遍得到積分圖像后,利用四個(gè)頂點(diǎn)對(duì)應(yīng)的值進(jìn)行簡(jiǎn)單加減運(yùn)算,即可求得該區(qū)域灰度。不管矩形窗口區(qū)域有多大,利用積分圖像只需進(jìn)行3次加減運(yùn)算,即:
S=p(D)+p(A)-p(B)-p(C)(4)
其中,S表示矩形窗口區(qū)域的灰度值;p(A)、p(B)、p(C)和p(D)分別表示矩形頂點(diǎn)的灰度值。
1.2 平方積分圖像
為了能夠快速獲得區(qū)域內(nèi)像素點(diǎn)灰度平方和,在積分圖像基礎(chǔ)上引入了平方積分圖像[15],在實(shí)際應(yīng)用中以矩陣形式存儲(chǔ),平方積分圖像中任意一點(diǎn)值表示為Pii(i,j),即:
其中i2(x,y)表示源圖像中(x,y)點(diǎn)的灰度值的平方,參考式(2)、式(3),源圖像中第i行、第j列的灰度平方積分Ps(i,j)以及平方積分圖像中任意一點(diǎn)(i,j)的值 Pii(i,j)可以分別由下面公式求得:
Ps(i,j)=Ps(i,j-1)+i2(i,j)(6)
Pii(i,j)=Pii(i-1,j)+Ps(i,j)(7)
再利用式(4),可求出某窗口區(qū)域的灰度值平方和,運(yùn)算簡(jiǎn)單,計(jì)算量大幅降低。
2 NCC算法及其改進(jìn)
2.1 原NCC匹配算法
圖像匹配本質(zhì)上是求兩圖像間的相似性,即針對(duì)右圖待匹配點(diǎn),在視差d所有可能取值范圍[0,disMax]內(nèi),計(jì)算(disMax+1)個(gè)歸一化系數(shù),取相關(guān)系數(shù)最大值對(duì)應(yīng)的左圖點(diǎn)作為最佳匹配點(diǎn),對(duì)應(yīng)的d為最佳視差。若選擇圖像尺寸為M×N,模板窗口尺寸為m×m,則歸一化互相關(guān)系數(shù)計(jì)算式如下[16]:
由式(8)可知,對(duì)于每一視差,在計(jì)算相關(guān)性系數(shù)時(shí)都需要對(duì)窗口區(qū)域求均值,復(fù)雜度較高,消耗的時(shí)間長(zhǎng),所以實(shí)時(shí)性差。
2.2 改進(jìn)的NCC算法
在原NCC算法中涉及到求窗口區(qū)域像素的均值,因此在計(jì)算每一個(gè)視差值時(shí)都要進(jìn)行6(m×m-1)次加法、4(m×m-1)次減法、2(m×m-1)次乘方、2次乘法、3次除法和1次開方,而且計(jì)算的次數(shù)隨著窗口m×m大小的變化而變化,模板窗口越大,匹配時(shí)消耗的時(shí)間越多。為了減低計(jì)算量,對(duì)歸一化互相關(guān)系數(shù)先不進(jìn)行求均值運(yùn)算,而是將其分子分母先展開化簡(jiǎn)?;诖?,對(duì)歸一化互相關(guān)系數(shù)進(jìn)行重推可得:
其中:
其中,式(14)利用卷積運(yùn)算降低計(jì)算復(fù)雜度,而式(15)~(18)均可以用積分圖像或平方積分圖像計(jì)算窗口區(qū)域的值,因此區(qū)域灰度值的和可用四個(gè)頂點(diǎn)簡(jiǎn)單的加減運(yùn)算來代替?;谏鲜龇治?,對(duì)于每一個(gè)視差值只需要進(jìn)行8次加法、7次減法、4次除法、4次乘法、1次開方和1次卷積,而且在計(jì)算量上不會(huì)隨模板窗口大小變化而變化,這極大地降低了計(jì)算相關(guān)系數(shù)過程中的難度。從計(jì)算量上引入積分圖像后有利于降低復(fù)雜度,提高運(yùn)算速度。
由于雙目立體匹配中兩圖像間存在視差,右圖右邊界的許多點(diǎn)在左圖上找不到相匹配的點(diǎn)并且模板窗口有一定的尺寸,由此其實(shí)際匹配的區(qū)域范圍是y≤N-dispMax+m,x≤M-m。剔除掉無法匹配的區(qū)域既能確保匹配點(diǎn)完全被搜索到,又可以減少匹配時(shí)間、提高搜索效率。
圖像匹配是三維重建的一個(gè)重要步驟,而在獲得圖像時(shí)物體的幾何信息會(huì)丟失,因此匹配時(shí)需要遵循多個(gè)約束條件[17]才能保證重建過程的正常進(jìn)行,包括:
?。?)外極線約束;
?。?)唯一性約束,指右圖中某點(diǎn)與左圖的對(duì)應(yīng)點(diǎn)是確定且唯一的,它們的關(guān)系與一次函數(shù)中自變量和應(yīng)變量的關(guān)系是一樣的,不存在一對(duì)多的形式;
?。?)連續(xù)性約束;
?。?)視差有限性約束,認(rèn)為在匹配時(shí)兩圖像間的視差是有界的;
?。?)左右一致性約束,指不管選擇左圖或右圖作為基準(zhǔn)圖,它們之間的對(duì)應(yīng)關(guān)系是不變的。
通過前面分析,對(duì)NCC算法進(jìn)行改進(jìn),引入積分圖像和平方積分圖像后,其實(shí)現(xiàn)步驟如下:
輸入:右攝像機(jī)采集的基準(zhǔn)圖像IR,左攝像機(jī)采集的實(shí)時(shí)圖像IL。
輸出:視差矩陣,顯示視差圖。
步驟1:計(jì)算IR和IL對(duì)應(yīng)的積分圖像和平方積分圖像,用SR、SRR和SL、SLL表示,并且對(duì)x、y賦初值。
步驟2:在視差范圍內(nèi),利用式(4)對(duì)積分圖像和平方積分圖像進(jìn)行簡(jiǎn)單的加減運(yùn)算,求取模板窗口和搜索窗口覆蓋區(qū)域灰度值的和及其灰度值的平方和。
步驟3:利用矩陣卷積,計(jì)算模板窗口與搜索窗口所包含區(qū)域的SRL。
步驟4:利用式(13)計(jì)算相關(guān)系數(shù),重復(fù)步驟2~3,直到滿足y≤N-dispMax+m且x≤M-m條件時(shí),獲得最佳匹配的視差矩陣,返回視差圖。算法流程圖如圖1所示。
3 實(shí)驗(yàn)驗(yàn)證與分析
本文實(shí)驗(yàn)采用CPU為Pentium(R)Dual-Core、內(nèi)存為1.96 GHz的PC機(jī),采用的編程環(huán)境為MATLAB 2011b。
3.1 標(biāo)準(zhǔn)測(cè)試圖像驗(yàn)證與分析
文中采用兩組國(guó)際通用標(biāo)準(zhǔn)測(cè)試圖進(jìn)行實(shí)驗(yàn)。圖2為測(cè)試圖Teddy;圖3為測(cè)試圖Cones;圖4為兩組測(cè)試圖的標(biāo)準(zhǔn)視差圖;圖5是利用NCC算法獲得的視差圖;圖6是本文提出的改進(jìn)NCC算法獲得的視差圖。
由圖5可以看出在右邊界區(qū)域不存在匹配點(diǎn),利用NCC算法在此區(qū)域進(jìn)行匹配會(huì)增加計(jì)算時(shí)間,影響實(shí)時(shí)性;圖6的改進(jìn)NCC算法在匹配時(shí)剔除了無法匹配的區(qū)域,提高了算法的計(jì)算效率。表1給出了當(dāng)模板尺寸為m=7像素和m=9像素時(shí)的時(shí)間消耗,從中可以看出,改進(jìn)的NCC算法比原算法耗時(shí)大為減少,提高了算法的實(shí)時(shí)性。當(dāng)m=9像素時(shí)消耗的時(shí)間僅為原算法的38%,并且時(shí)間消耗幾乎不受模板尺寸的影響。同時(shí),將兩種算法得到的視差圖與標(biāo)準(zhǔn)視差圖進(jìn)行比較發(fā)現(xiàn),改進(jìn)NCC算法具有更好的精度和魯棒性。
3.2 實(shí)際采集圖像驗(yàn)證與分析
本實(shí)驗(yàn)采用Point Grey公司生產(chǎn)的Bumblebee2型號(hào)立體攝像機(jī)對(duì)場(chǎng)景進(jìn)行采集,得到校正后的圖像見圖7,選擇右攝像機(jī)拍攝的圖像為基準(zhǔn)圖像、左攝像機(jī)拍攝的圖像為實(shí)時(shí)圖像。圖8為利用NCC算法和本文算法得到的視差圖。
表2給出了兩種算法的耗時(shí)情況,從中可以看出,改進(jìn)NCC算法減少時(shí)間消耗顯著。比較表1和表2數(shù)據(jù),當(dāng)圖像尺寸和模板尺寸越大時(shí),改進(jìn)的NCC算法越能夠表現(xiàn)其優(yōu)越性。
4 結(jié)束語
本文通過引入積分圖像和平方積分圖像,并剔除源圖像中無法匹配區(qū)域,改進(jìn)了原NCC算法,降低了計(jì)算復(fù)雜度,提高了匹配速度。當(dāng)圖像尺寸和模板窗口越大、左右圖像視差越大時(shí),耗時(shí)減少更為顯著,且保持了較好的匹配精度,如果利用VC等高級(jí)語言移植到機(jī)器人等環(huán)境建模,可以進(jìn)行在線立體匹配。
參考文獻(xiàn)
[1] 隋婧,金偉其.雙目立體視覺技術(shù)的實(shí)現(xiàn)及其進(jìn)展[J].電子技術(shù)應(yīng)用,2004,30(10):3-7.
[2] 程黃金.雙目立體視覺系統(tǒng)的技術(shù)分析與應(yīng)用前景[J].電腦知識(shí)與技術(shù),2011,7(9):2145-2147.
[3] 孫卜郊,周東華.基于NCC的快速匹配算法[J].傳感器與微系統(tǒng),2007,26(9):104-106.
[4] ZITOVA B, FLUSSER J. Image registration methods: a survey[J]. Image and Vision Computing, 2003,21(11): 977-1000.
[5] 賈貝貝,阮秋琦.雙目立體視覺的三維人臉重建方法[J].智能系統(tǒng)學(xué)報(bào),2009,4(6):513-520.
[6] 錢曾波,邱振戈,張永強(qiáng).計(jì)算機(jī)立體視覺研究的進(jìn)展[J].測(cè)繪學(xué)院學(xué)報(bào),2001,18(4):267-272.
[7] 曾巒,王元?dú)J,譚久彬.改進(jìn)的SIFT特征提取和匹配算法[J].光學(xué)精密工程,2011,19(6):1391-1397.
[8] 林靜,江開勇,林俊義,等.基于立體校正的快速相位立體匹配[J].貴州師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,31(2):92-95.
[9] 白明,莊嚴(yán),王偉.雙目立體匹配算法的研究與進(jìn)展[J].控制與決策,2008,23(7):721-729.
[10] WEI S, LAI S. Fast template matching based on normalized cross correlation with adaptive multilevel winner update[J]. IEEE Transactions on Image Processing, 2008,17(11): 2227-2235.
[11] 徐奕,周軍.立體視覺匹配技術(shù)[J].計(jì)算機(jī)工程與應(yīng)用,2003,15(5):58-62.
[12] VIOLA P, JONES M. Rapid object detection using a boosted cascade of simple features[C]. Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2001:511-518.
[13] PORIKLI F. Integral histogram: a fast way to extract histograms in cartesian spaces [C]. Proceedings 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2005:829-837.
[14] LAMPERT C, BLASCHKO M, HOFMANN T. Efficient sub-window search: a branch and bound framework for object localization[J]. Pattern Analysis and Machine Intelligence, 2009,31(12):2129-2142.
[15] 邵平,楊路明.基于模板分解和積分圖像的快速Kirsch邊緣檢測(cè)[J].自動(dòng)化學(xué)報(bào),2007,33(8):795-800.
[16] 韓冰,王永明,劉楊,等.一種基于積分圖像的快速歸一化積相關(guān)算法[J].彈箭與制導(dǎo)學(xué)報(bào),2009,29(5):283-286.
[17] 肖艷青,劉黨輝,孫朋.圖像立體匹配研究進(jìn)展[J].測(cè)控技術(shù),2009,28(8):1-5.