李海峰，傅 侃，周文暉，曾 虹

（1.杭州電子科技大學計算機應用研究所，浙江 杭州310018；2.杭州市公安局交警支隊，浙江 杭州310006）

0 引 言

在眾多的計算機視差理論中，匹配是一個關鍵而又復雜的難點。在立體視差中，由同一時間不同位置獲取的兩幅圖像或多幅圖像，可以得到圖像中的深度信息。歸一化交叉相關［1］（Normalized Cross Correlation，NCC）是區(qū)域匹配中的一種重要的匹配方法，該方法算法簡單，物理意義明顯，獲得了廣泛的應用?；谥眯劈c擴散的三維重建的方法［2］實時效果好，魯棒性強，完全可以滿足自主導航機器人視覺的要求，本文算法的主要思想源于該工作。滾球算法［3］（Ball Pivoting Algorithm，BPA）進行物體曲面重建效果好，速度快。本文采用雙目立體視覺，使用較正后的視差灰度圖進行匹配。算法中應用了改進的NCC算法，從計算得到的視差空間中尋找置信點進行表面跟蹤，使用BPA算法對計算的點云數(shù)據(jù)來恢復地形原貌，重建三維場景。結果證實了算法的有效性。

1 高置信度的立體匹配

1.1 歸一化交叉相關算法

NCC屬于相似性度量，它以相鄰窗口灰度為匹配元，以相關程度為判別依據(jù)，對立體圖像的亮度差異進行補償。該方法基于光度測量學不變性原理，受外界環(huán)境因素影響小。

假設I1，I2分別是兩幅圖中的左圖和右圖的區(qū)域，I（x，y）為圖中x，y點對應象素值的灰度。則有：

式中，I1是指左圖中以u，v為左上角象素的區(qū)域，I2是指右圖中以u，v為左上角象素的區(qū)域，x是指在水平方向上窗口移動的距離。由于水平約束，平移x應該滿足x＞0。

1.2 視差空間中置信點的提取方法

歸一化交叉相關算法所計算出來的視差，可能存在著很多誤匹配點，也并不滿足立體視覺中所有的約束條件。所以要對計算出來的視差進行篩選，選出所有滿足約束條件的值。本文應用的算法在約束條件上加以改進，引入系數(shù)lamda。視差信息應該滿足水平約束和垂直約束，如果視差中某點的所滿足的水平約束和垂直約束上的所有點的視差值與lamda之積小于該視點的視差值，就把它設為置信點。lamda的值與置信點數(shù)目的選取有關，在置信點數(shù)目確定的條件下，一般選取最大值。本文中置信點的數(shù)目為是總象素數(shù)目的百分之一。

1.3 表面跟蹤方法

由于室外場景中的視差比較平滑，本文采用了置信點擴散的表面跟蹤方法［2］。該方法算法簡單，實現(xiàn)方法速度快，具體方法如下：

（1）把圖片中所有置信點用鏈表鏈接起來；

（2）依次對表頭至表尾所有節(jié)點在視差圖中的上下左右4個相鄰節(jié)點進行判定，如果相鄰節(jié)點未被設為置信點，則把相鄰結點與該節(jié)點的深度值進行比較，選取深度小的值為相鄰結點的深度值；

（3）把步驟2判斷過的4個點設為置信點，添加到鏈表末端；

（4）返回步驟1，直到所有的點都被判定。

1.4 計算亞象素方法

表面跟蹤方法得到的視差空間內點的深度為整數(shù)值，無法滿足地形重建平滑的需要，所以要計算點的亞象素值。一般采用二次曲線擬合對匹配點進行亞像素定位，以便能夠準確計算視差值［4］。為了滿足實時性需要，本文選取了拋物線法求亞象素差值［1］，利用所計算到的置信點以及置信點前后兩個點的相關系數(shù)，作拋物線后求出極值點與置信點之間的距離。計算式為：

1.5 中值濾波

中值濾波法是一種非線性平滑技術，它將每一象素點的灰度值設置為該點某鄰域窗口內的所有象素點灰度值的中值。它首先從圖像中的某個采樣窗口取出奇數(shù)個數(shù)據(jù)進行排序，然后用排序后的中值取代要處理的數(shù)據(jù)。

2 滾球算法

BPA是通過插入給定的物體表面樣本的點云數(shù)據(jù)來計算三角網(wǎng)的。BPA算法很簡單：如果只有3個點在指定半徑的球中，那么這3個點就構成一個三角形。它從種子三角形開始繞著一邊滾動，直到它觸及另一個點形成另一個三角形，反復的應用該方法直到判斷完所有三角形的邊。然后重新從另一個種子三角形開始，直到所有的點都得到判斷。算法的偽代碼如下：

3 實驗結果

實驗結果分為兩部分：將本文中的匹配算法結果與模擬數(shù)據(jù)真實視差圖進行比較來驗證匹配方法的有效性；將本文中的匹配算法應用于實景地形圖對，并進行地形重建［5］，觀察效果。

3.1 人工立體圖像對實驗

利用人工立體圖對進行實驗所得到的結果如圖1所示。

圖1 人工立體圖對中本文算法與真實視差圖對比

本實驗中匹配窗口大小為5×5，待匹配圖為640×480象素、24位色深的BMP圖對。由圖1中得知，該算法在視差平滑區(qū)域效果十分理想，在一些視差變化較大區(qū)域還存在一定的誤差?？梢詽M足視覺導航機器人三維場景重建的需要。

3.2 實際雙目視覺數(shù)據(jù)實驗

在實際應用中，兩幅圖受環(huán)境影響比較大。本實驗中匹配窗口為5×5，待匹配圖為320×240象素、24位色深的BMP圖對。對計算得到的視差圖邊緣進行裁剪，濾去超出視野的點后得到本文中用于地形重建的視差圖，如圖2所示：

圖2 真實地形圖對中本文算法得到的視差圖

由于實際數(shù)據(jù)實驗中無法得到真實視差圖，所以無法比較計算的結果，但是可以從三維重建的結果中觀察本文算法的有效性。圖2中（a）、（b）兩組圖三維重建的結果如圖3（a）、（b）所示。從圖3的重建結果圖可以看到算法的有效性。本文算法重建出了道路以及周邊環(huán)境的原貌，起伏路況和路邊樹木在結果中得到令人滿意的重建結果。

圖3 利用Ball Pivoting算法對點云數(shù)據(jù)進行三維重建的結果

4 結 論

本文應用的改進的歸一化交叉相關算法結合了置信點提取、表面跟蹤，計算亞象素視差后進行中值濾波得到視差圖。三維重建中使用BPA算法對計算得到的點云數(shù)據(jù)三角化。結果表明，本文算法速度快，有著高穩(wěn)定性和魯棒性，在模擬數(shù)據(jù)和實際地形的三維重建結果中都能得到比較滿意的效果。

［1］ 陳華華.視覺導航關鍵技術研究：立體視覺和路徑規(guī)劃［D］.杭州：浙江大學，2005：40-63.

［2］ Qian Chen.Multi-view Image-Based Rendering and Modeling［D］.Los Angeles：University of Southern California，2000：32-61.

［3］ BernardiniF，Mittleman J，Rushmeier H.The Ball-Pivoting Algorithm for Surface Reconstruction［J］.IEEETransactionson Visualization and Computer Graphics，1999，5（4）：349-359.

［4］ 廖素英.實時雙目立體視覺研究［D］.成都：電子科技大學，2005：48.

［5］ 王海彬.地面自主機器人視覺導航三維重建算法研究［D］.長沙：國防科技大學，2006：7-25.