基于區域的稠密立體匹配方法

金 玲

（遼寧大學信息學院，遼寧 葫蘆島 110036）

稠密立體匹配指計算圖像中所有像素的視差值得到致密的視差圖，它對三維重建的質量具有十分重要的意義，作為立體匹配的重要研究方向，稠密立體匹配更是計算機視覺領域極富挑戰性的研究課題。

近年來各國學者對稠密立體匹配方法進行了不斷深入的研究。自適應窗口算法通過調節不同像素點的窗口尺寸[1]提高匹配準確性，不過計算非常復雜，無法實現實時運算。Vladimir Kolmogorov等將圖論中的最小割算法應用到立體匹配算法中，求得的最短路徑給出了整個圖像的視差曲面。此算法復雜度也較高，計算效率低。基于區域增長的半稠密匹配算法具有較好的魯棒性和可實現性，但是此算法存在一些缺陷：在匹配平滑的區域，匹配關系的傳播就會停止。區域匹配的缺陷可歸納成3點：①區域匹配直接利用圖像的灰度值進行匹配導致圖像的旋轉以及光強和對比度的變化對區域匹配影響較大；②相似測度函數的時空復雜性比較大；③匹配窗口大小難以選擇，窗口過大導致視差跳躍處出現誤匹配，窗口選擇過小導致區域的灰度分布不能得到充分體現。

1 基本思想

為了克服上述基于區域存在的問題，本文算法先提取特征點進行匹配，然后將匹配之后得到的種子點消除誤匹配；再次，根據種子點匹配度排序策略進行區域增長，按照種子點的匹配可靠系數，動態改變搜索窗口得大小，進而生成稠密視差圖。實驗表明，本文基于區域增長獲得的視差圖在保證致密的情況下，運行效率比較高。

2 種子點的魯棒性匹配算法

2.1 SIFT算法求取特征點

Lhuillier和Quan指出即使種子匹配存在較多外點，增長效果依然能夠良好地進行，但算法的運行時間與復雜度明顯增加。在實驗中我們發現，通過特征匹配和極線幾何的魯棒估計，已經可以正確恢復出圖像對的極幾何關系。此外，種子點如果能夠在圖像中均勻分布，增長后的對應點就能覆蓋圖像的大部分區域，從而在紋理豐富和稀疏區域存在足夠多的匹配，以提高重建效果。

Lowe提出的 SIFT（Scale Invariant Feature Transform）特征點檢測和匹配算法，相對于傳統的Harris等角點檢測方法在實際應用中對圖像變形呈現出更好的魯棒性。因此，本文采用基于SIFT特征匹配的方法來確定初始的候選種子點，并且經實驗表明能去除大部分的誤匹配，但是為了獲得更為可靠和精確的對應點作為種子點，我們在實驗中，對SIFT得到的匹配通過魯棒估計進行了進一步的剔除。見圖 2（c）（d）。

2.2 種子點（對應點初匹配）

在提取圖像的特征點后，對兩幅圖像提取的特征點進行初始匹配，即確定哪兩個點是空間同一場景的投影點，建立候選匹配集合。對于這個初始候選匹配點對集合，它允許包含錯誤的匹配，但這些錯誤的匹配將在后續的魯棒匹配階段剔除掉。建立初始匹配集，采用相似性,度量函數對兩幅圖像中的對應點匹配之后成為種子點。文章采用的是去均值的歸一化相關算法：

上式中，U，V為模板大小；u，v為匹配點；f（x，y）為圖像中匹配區域的像素灰度值t（x-u，y-ν）為模板中的像素灰度值，t為模板的灰度均值，f（u，ν）為圖像中匹配區域的均值。由于受環境影響、圖像亮度或圖像內可能存在的相似特征，必然存在許多誤匹配，通過魯棒的估計基礎矩陣可以剔除更多的誤匹配，得到一個精度較高的匹配點集。種子點的可靠匹配是十分重要的，它是以后區域增長的基礎。見圖 3（e）（f）。

2.3 去除外點，種子點求精

關于魯棒估計，即使用某種方法對外點加以識別，或者說從測量數據中確定出內點（inlier）或稱有效點，然后再重新進行模型估計，這就是魯棒估計的原理。常用的魯棒估計法有RANSAC方法，最大后驗的RANSAC方法，M-估計和最小中值估計等。本文使用 RANSAC（Random Sampling Consensus）方法，它是由Fischler和Bolles于1981年所引入的魯棒方法。最初它被用于3點確定攝像機姿態的估計，現在無論在計算機視覺領域還是在其他學科的估計問題中都有廣泛的應用。對于處理大比例的外點，RANSAC是一種十分有效的方法。經過RANSAC算法消除誤匹配點見圖 4（g）（h）。

3 基于區域的稠密匹配

考慮到窗口的選擇對匹配精度有很大影響，所以在匹配傳播過程中，為了避免前一個點的匹配誤差對后一個點匹配精度的影響，本文提出了以下動態改變搜索窗的方法：若前一對匹配點的R（u，v）值比較大，則下一個匹配點就可以在它的較小鄰域內搜索求得；若前一對匹配點的R（u，v）值較小，則下一個匹配點就需要在它的較大鄰域內搜索求得。這就是說，搜索窗的大小N與 R（u，v）值成反比，如公式（2）。

在公式（2）中的常數因子λ需要根據待匹配的圖像對的情況由實驗確定，通常它的取值在1~2之間。采用自適應的搜索窗既可以有效地減少計算時間，又可以提高匹配算法的準確性，同時避免了區域增長過程中匹配誤差的累積。見圖5、圖6（i）（j）。

文章基于區域增長的稠密匹配的步驟如下：

（1）將種子匹配按R（u，v）值從高到低排成一個隊列，稱之為全局種子隊列；建立兩個與圖像同大小的標志矩陣，矩陣中每個元素不是1就是0，分別標志對應像素是否找到匹配（0表示沒有被匹配，1表示已被匹配，初始為0）。

（2）從種子隊列中取出R（u，v）分數最高的匹配值記為R0（u，v），并將它從種子隊列中刪除；對于R0（u，v），按照公式（2）求出搜索窗口的大小N0以便于下一步R0（u，v）增長。

（3）在N0范圍內按R（u，v）值從高到低排成另一個臨時局部隊列；從局部隊列中逐個去除候選匹配，如果候選匹配的R值超過既定的閾值，并且沒有被匹配過（即相應的標志位為0），就將它判為正確匹配存入種子隊列中并將匹配標志置為1。隨后更新相應的數據結構。

（4）重復步驟（1）-（3）直到種子隊列為空。

在實驗中發現，種子點增長過程的速度很快，往往只需要幾個種子點就可以匹配圖像大部分的紋理區域，前提條件是建立在種子匹配可靠性很高的基礎上的。通常情況下，種子越多，分布越均勻，結果就越好。說明了種子匹配點獲取環節的重要性。

4 實驗分析

圖1 原始圖像

圖2 提取特征點之后的圖像

圖3 提取種子點圖像

圖4 種子點消除誤匹配圖像

圖5 區域增長后的種子點

圖6 以左圖像為參考圖像的視差圖

文章使用一組杯子，其大小為 640×480，見圖 1（a）（b）；圖 2（c）（d）是采用第二節的算法獲取的特征點,共705對，它們比較均勻地分布于兩幅圖像中；圖3（e）（f）是種子點提取效果圖；圖4（g）（h）是采用第二節去除誤匹配后得到的精匹配種子點，共生成127對種子點；圖5是采用第三小節的算法對種子點進行區域增長之后得到的結果，共50 183個種子點；圖6是以左圖象為參考圖像生成的視差圖。

6 結論

為了獲得致密視差圖，文章提出了改進的基于區域的稠密立體匹配方法。采用分步思想的策略先提取出圖像對中匹配的種子點，在此基礎之上采用變窗口方法進行區域增長，從而得到致密視差圖。通過對測試圖像的實驗，證實本算法的可行性和準確性，具有實用價值。