基于區(qū)域的稠密立體匹配方法

金 玲

（遼寧大學(xué)信息學(xué)院，遼寧 葫蘆島 110036）

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

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

1 基本思想

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

2 種子點(diǎn)的魯棒性匹配算法

2.1 SIFT算法求取特征點(diǎn)

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

Lowe提出的 SIFT（Scale Invariant Feature Transform）特征點(diǎn)檢測(cè)和匹配算法，相對(duì)于傳統(tǒng)的Harris等角點(diǎn)檢測(cè)方法在實(shí)際應(yīng)用中對(duì)圖像變形呈現(xiàn)出更好的魯棒性。因此，本文采用基于SIFT特征匹配的方法來(lái)確定初始的候選種子點(diǎn)，并且經(jīng)實(shí)驗(yàn)表明能去除大部分的誤匹配，但是為了獲得更為可靠和精確的對(duì)應(yīng)點(diǎn)作為種子點(diǎn)，我們?cè)趯?shí)驗(yàn)中，對(duì)SIFT得到的匹配通過(guò)魯棒估計(jì)進(jìn)行了進(jìn)一步的剔除。見(jiàn)圖 2（c）（d）。

2.2 種子點(diǎn)（對(duì)應(yīng)點(diǎn)初匹配）

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

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

2.3 去除外點(diǎn)，種子點(diǎn)求精

關(guān)于魯棒估計(jì)，即使用某種方法對(duì)外點(diǎn)加以識(shí)別，或者說(shuō)從測(cè)量數(shù)據(jù)中確定出內(nèi)點(diǎn)（inlier）或稱有效點(diǎn)，然后再重新進(jìn)行模型估計(jì)，這就是魯棒估計(jì)的原理。常用的魯棒估計(jì)法有RANSAC方法，最大后驗(yàn)的RANSAC方法，M-估計(jì)和最小中值估計(jì)等。本文使用 RANSAC（Random Sampling Consensus）方法，它是由Fischler和Bolles于1981年所引入的魯棒方法。最初它被用于3點(diǎn)確定攝像機(jī)姿態(tài)的估計(jì)，現(xiàn)在無(wú)論在計(jì)算機(jī)視覺(jué)領(lǐng)域還是在其他學(xué)科的估計(jì)問(wèn)題中都有廣泛的應(yīng)用。對(duì)于處理大比例的外點(diǎn)，RANSAC是一種十分有效的方法。經(jīng)過(guò)RANSAC算法消除誤匹配點(diǎn)見(jiàn)圖 4（g）（h）。

3 基于區(qū)域的稠密匹配

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

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

文章基于區(qū)域增長(zhǎng)的稠密匹配的步驟如下：

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

（2）從種子隊(duì)列中取出R（u，v）分?jǐn)?shù)最高的匹配值記為R0（u，v），并將它從種子隊(duì)列中刪除；對(duì)于R0（u，v），按照公式（2）求出搜索窗口的大小N0以便于下一步R0（u，v）增長(zhǎng)。

（3）在N0范圍內(nèi)按R（u，v）值從高到低排成另一個(gè)臨時(shí)局部隊(duì)列；從局部隊(duì)列中逐個(gè)去除候選匹配，如果候選匹配的R值超過(guò)既定的閾值，并且沒(méi)有被匹配過(guò)（即相應(yīng)的標(biāo)志位為0），就將它判為正確匹配存入種子隊(duì)列中并將匹配標(biāo)志置為1。隨后更新相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。

（4）重復(fù)步驟（1）-（3）直到種子隊(duì)列為空。

在實(shí)驗(yàn)中發(fā)現(xiàn)，種子點(diǎn)增長(zhǎng)過(guò)程的速度很快，往往只需要幾個(gè)種子點(diǎn)就可以匹配圖像大部分的紋理區(qū)域，前提條件是建立在種子匹配可靠性很高的基礎(chǔ)上的。通常情況下，種子越多，分布越均勻，結(jié)果就越好。說(shuō)明了種子匹配點(diǎn)獲取環(huán)節(jié)的重要性。

4 實(shí)驗(yàn)分析

圖1 原始圖像

圖2 提取特征點(diǎn)之后的圖像

圖3 提取種子點(diǎn)圖像

圖4 種子點(diǎn)消除誤匹配圖像

圖5 區(qū)域增長(zhǎng)后的種子點(diǎn)

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

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

6 結(jié)論

為了獲得致密視差圖，文章提出了改進(jìn)的基于區(qū)域的稠密立體匹配方法。采用分步思想的策略先提取出圖像對(duì)中匹配的種子點(diǎn)，在此基礎(chǔ)之上采用變窗口方法進(jìn)行區(qū)域增長(zhǎng)，從而得到致密視差圖。通過(guò)對(duì)測(cè)試圖像的實(shí)驗(yàn)，證實(shí)本算法的可行性和準(zhǔn)確性，具有實(shí)用價(jià)值。