基于NCC的改進立體匹配算法*

歐陽鑫玉 ，張娟娟 ，趙楠楠 ，徐建楠

（1.遼寧科技大學 電子與信息工程學院，遼寧 鞍山 114051；2.國家金融安全及系統裝備工程技術研究中心，遼寧 鞍山 114051）

0 引言

雙目立體視覺是計算機視覺的一個重要分支，近年來，雙目立體視覺技術得到了大量研究[1]，主要應用在機器人導航、三維測量和虛擬現實等領域。雙目立體視覺系統的實現過程由圖像獲取、攝像機標定、特征點提取、圖像匹配和三維立體重建等步驟組成[2]。圖像匹配本質上是尋找兩幅圖像的相似性[3-4]，是恢復三維立體場景的先決條件[5]，是立體視覺系統中的關鍵技術之一。雙目立體視覺圖像匹配[6]技術是通過兩臺水平擺放的攝像機分別獲取兩幅圖像，并從中找出相同景物各像素點的對應關系，得到其最佳視差值，最終獲得圖像視差圖的技術。

圖像匹配方法按照匹配基元不同可分為特征匹配[7]、相位匹配[8]和區域匹配[1，9]三種。特征匹配是針對提取的特征進行描述，然后運用所描述的參數進行匹配的一類算法，計算量小，速度快，但是匹配效果受到圖像特征稀疏性的影響難以獲得致密視差圖。相位匹配是最近才發展起來的一類算法，能夠反映信號的結構信息和抑制圖像的高頻噪聲，適用于并行處理存在相位奇點和相位卷繞問題的情況。區域匹配是基于局部窗口間灰度信息相關程度的匹配算法，常用的匹配相似度量函數有NCC（Normalized Cross Correlation，歸一化互相關）、SAD（Sum of Absolute Differences，差絕對值和） 和 SSD （Sum of Squared Differences，差平方和）。這三種算法中，NCC算法最常用，它通過計算視差范圍內基準圖像與實時圖像對應像素點間的相關性來獲取視差圖，相關系數一般在[-1，1]之間取值，該算法將搜索相關系數最大值對應的視差作為最佳視差值，具有精度高、魯棒性強[10]的優點，缺點是計算量大、速度慢，在線應用受到限制。

本文針對NCC算法的缺點，通過在立體匹配中引入積分圖像和平方積分圖像，并且剔除基準圖像中無法匹配區域，對原NCC算法進行了改進，在保證匹配質量的情況下，使匹配速度得到顯著提高，實驗結果驗證了該改進算法的有效性和快速性[11]。

1 積分圖像及平方積分圖像

1.1 積分圖像

積分圖像（Integral Image）理論是 Viola P.等于 2001年提出的[12]。積分圖像是一種用于快速計算圖像某窗口區域灰度和的一種圖像中間表示，有較廣泛的應用[13-15]。積分圖像中任 意一點（i，j）的值用 ii（i，j）表示，代表了源圖像中行數小于i、列數小于j的所有灰度值的和，即：

其中 i（x，y）表示源圖像中（x，y）點的灰度值。 令 s（i，j）為源圖像中第i行、第j列的灰度值積分，則有：

利用式（2）和式（3）編程實現時，應該擴展一行一列以確保 i-1，j-1為正數。

如果要計算原始圖像中頂點依次為 A、B、C、D的矩形窗口，只需將原圖像遍歷一遍得到積分圖像后，利用四個頂點對應的值進行簡單加減運算，即可求得該區域灰度。不管矩形窗口區域有多大，利用積分圖像只需進行3次加減運算，即：

其中，S 表示矩形窗口區域的灰度值；p（A）、p（B）、p（C）和p（D）分別表示矩形頂點的灰度值。

1.2 平方積分圖像

為了能夠快速獲得區域內像素點灰度平方和，在積分圖像基礎上引入了平方積分圖像[15]，在實際應用中以矩陣形式存儲，平方積分圖像中任意一點值表示為 Pii（i，j），即：

其中 i2（x，y）表示源圖像中（x，y）點的灰度值的平方，參考式（2）、式（3），源圖像中第 i行、第 j列的灰度平方積分Ps（i，j） 以及平方積分圖像中任意一點 （i，j）的值Pii（i，j）可以分別由下面公式求得：

再利用式（4），可求出某窗口區域的灰度值平方和，運算簡單，計算量大幅降低。

2 NCC算法及其改進

2.1 原NCC匹配算法

圖像匹配本質上是求兩圖像間的相似性，即針對右圖待匹配點，在視差 d所有可能取值范圍[0，disMax]內，計算（disMax+1）個歸一化系數，取相關系數最大值對應的左圖點作為最佳匹配點，對應的d為最佳視差。若選擇圖像尺寸為M×N，模板窗口尺寸為m×m，則歸一化互相關系數計算式如下[16]：

其中：

由式（8）可知，對于每一視差，在計算相關性系數時都需要對窗口區域求均值，復雜度較高，消耗的時間長，所以實時性差。

2.2 改進的NCC算法

在原NCC算法中涉及到求窗口區域像素的均值，因此在計算每一個視差值時都要進行 6（m×m-1）次加法、4（m×m-1）次減法、2（m×m-1）次乘方、2 次乘法、3 次除法和1次開方，而且計算的次數隨著窗口m×m大小的變化而變化，模板窗口越大，匹配時消耗的時間越多。為了減低計算量，對歸一化互相關系數先不進行求均值運算，而是將其分子分母先展開化簡。基于此，對歸一化互相關系數進行重推可得：

其中：

其中，式（14）利用卷積運算降低計算復雜度，而式（15）～（18）均可以用積分圖像或平方積分圖像計算窗口區域的值，因此區域灰度值的和可用四個頂點簡單的加減運算來代替。基于上述分析，對于每一個視差值只需要進行8次加法、7次減法、4次除法、4次乘法、1次開方和1次卷積，而且在計算量上不會隨模板窗口大小變化而變化，這極大地降低了計算相關系數過程中的難度。從計算量上引入積分圖像后有利于降低復雜度，提高運算速度。

由于雙目立體匹配中兩圖像間存在視差，右圖右邊界的許多點在左圖上找不到相匹配的點并且模板窗口有一定的尺寸，由此其實際匹配的區域范圍是y≤N-dispMax+m，x≤M-m。剔除掉無法匹配的區域既能確保匹配點完全被搜索到，又可以減少匹配時間、提高搜索效率。

圖像匹配是三維重建的一個重要步驟，而在獲得圖像時物體的幾何信息會丟失，因此匹配時需要遵循多個約束條件[17]才能保證重建過程的正常進行，包括：

（1）外極線約束；

（2）唯一性約束，指右圖中某點與左圖的對應點是確定且唯一的，它們的關系與一次函數中自變量和應變量的關系是一樣的，不存在一對多的形式；

（3）連續性約束；

（4）視差有限性約束，認為在匹配時兩圖像間的視差是有界的；

（5）左右一致性約束，指不管選擇左圖或右圖作為基準圖，它們之間的對應關系是不變的。

通過前面分析，對NCC算法進行改進，引入積分圖像和平方積分圖像后，其實現步驟如下：

輸入：右攝像機采集的基準圖像IR，左攝像機采集的實時圖像IL。

輸出：視差矩陣，顯示視差圖。

步驟1：計算IR和IL對應的積分圖像和平方積分圖像，用 SR、SRR和 SL、SLL表示，并且對 x、y 賦初值。

步驟2：在視差范圍內，利用式（4）對積分圖像和平方積分圖像進行簡單的加減運算，求取模板窗口和搜索窗口覆蓋區域灰度值的和及其灰度值的平方和。

步驟3：利用矩陣卷積，計算模板窗口與搜索窗口所包含區域的SRL。

步驟 4：利用式（13）計算相關系數，重復步驟 2～3，直到滿足y≤N-dispMax+m且x≤M-m條件時，獲得最佳匹配的視差矩陣，返回視差圖。算法流程圖如圖1所示。

3 實驗驗證與分析

本文實驗采用CPU為Pentium （R）Dual-Core、內存為1.96 GHz的PC機，采用的編程環境為MATLAB 2011b。

圖1 改進NCC算法的流程圖

3.1 標準測試圖像驗證與分析

文中采用兩組國際通用標準測試圖進行實驗。圖2為測試圖 Teddy；圖3為測試圖 Cones；圖4為兩組測試圖的標準視差圖；圖5是利用NCC算法獲得的視差圖；圖6是本文提出的改進NCC算法獲得的視差圖。

圖2 國際通用測試圖Teddy

圖3 國際通用測試圖Cones

圖4 標準測試圖像實際視差圖

圖5 NCC算法得到的視差圖

圖6 改進NCC算法所得的視差圖

由圖5可以看出在右邊界區域不存在匹配點，利用NCC算法在此區域進行匹配會增加計算時間，影響實時性；圖6的改進NCC算法在匹配時剔除了無法匹配的區域，提高了算法的計算效率。表1給出了當模板尺寸為m=7像素和m=9像素時的時間消耗，從中可以看出，改進的NCC算法比原算法耗時大為減少，提高了算法的實時性。當m=9像素時消耗的時間僅為原算法的38%，并且時間消耗幾乎不受模板尺寸的影響。同時，將兩種算法得到的視差圖與標準視差圖進行比較發現，改進NCC算法具有更好的精度和魯棒性。

表1 NCC和改進NCC算法耗時比較

3.2 實際采集圖像驗證與分析

本實驗采用Point Grey公司生產的Bumblebee2型號立體攝像機對場景進行采集，得到校正后的圖像見圖7，選擇右攝像機拍攝的圖像為基準圖像、左攝像機拍攝的圖像為實時圖像。圖8為利用NCC算法和本文算法得到的視差圖。

圖7 實驗采集圖像

圖8 采集圖像的視差圖

表2給出了兩種算法的耗時情況，從中可以看出，改進NCC算法減少時間消耗顯著。比較表1和表2數據，當圖像尺寸和模板尺寸越大時，改進的NCC算法越能夠表現其優越性。

表2 兩種算法耗時比較

4 結束語

本文通過引入積分圖像和平方積分圖像，并剔除源圖像中無法匹配區域，改進了原NCC算法，降低了計算復雜度，提高了匹配速度。當圖像尺寸和模板窗口越大、左右圖像視差越大時，耗時減少更為顯著，且保持了較好的匹配精度，如果利用VC等高級語言移植到機器人等環境建模，可以進行在線立體匹配。

[1]隋婧，金偉其.雙目立體視覺技術的實現及其進展[J].電子技術應用，2004，30（10）：3-7.

[2]程黃金.雙目立體視覺系統的技術分析與應用前景[J].電腦知識與技術，2011，7（9）：2145-2147.

[3]孫卜郊，周東華.基于 NCC的快速匹配算法[J].傳感器與微系統，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].智能系統學報，2009，4（6）：513-520.

[6]錢曾波，邱振戈，張永強.計算機立體視覺研究的進展[J].測繪學院學報，2001，18（4）：267-272.

[7]曾巒，王元欽，譚久彬.改進的SIFT特征提取和匹配算法[J].光學精密工程，2011，19（6）：1391-1397.

[8]林靜，江開勇，林俊義，等.基于立體校正的快速相位立體匹配[J].貴州師范大學學報（自然科學版），2013，31（2）：92-95.

[9]白明，莊嚴，王偉.雙目立體匹配算法的研究與進展[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]徐奕，周軍.立體視覺匹配技術[J].計算機工程與應用，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 ComputerSocietyConferenceonComputer 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邊緣檢測[J].自動化學報，2007，33（8）：795-800.

[16]韓冰，王永明，劉楊，等.一種基于積分圖像的快速歸一化積相關算法 [J].彈箭與制導學報，2009，29（5）：283-286.

[17]肖艷青，劉黨輝，孫朋.圖像立體匹配研究進展[J].測控技術，2009，28（8）：1-5.