改進(jìn)的基于α擴(kuò)展移動(dòng)的立體匹配算法

李惠光，翁良寶，姜洪磊

（燕山大學(xué) 電氣工程學(xué)院，河北 秦皇島066004）

0 引 言

立體匹配在計(jì)算機(jī)視覺研究是一個(gè)重要領(lǐng)域。它通過匹配給定的兩幅或多幅圖像，尋找圖像中的物體在另一張圖像中相對(duì)應(yīng)點(diǎn)的關(guān)系，計(jì)算出兩者之間的視差 （Disparity），從而獲得物體深度等信息［1］。近年來，隨著圖論的發(fā)展和完善，圖割思想的算法在立體匹配方面逐漸成為一個(gè)熱點(diǎn)［2－3］，其中，由 Boykov等人［4－5］提 出 的α 擴(kuò) 展 移 動(dòng) 算 法的應(yīng)用較為廣泛，該算法的匹配精度高，尤其在底紋理區(qū)域和不連續(xù)區(qū)域的匹配也可以獲得良好地匹配效果［6］，但是，α擴(kuò)展移動(dòng)算法在匹配過程中需要不斷構(gòu)建網(wǎng)格圖，進(jìn)行圖切割優(yōu)化，這占用了大量的計(jì)算時(shí)間，針對(duì)這一問題，本文提出了一種改進(jìn)的α擴(kuò)展算法，該算法首先定義了一個(gè)循環(huán)停止參數(shù)，當(dāng)計(jì)算的循環(huán)停止參數(shù)滿足循環(huán)停止條件時(shí)，停止循環(huán)，其次是改變了傳統(tǒng)α擴(kuò)展移動(dòng)算法的無序迭代，優(yōu)先設(shè)定經(jīng)初始視差計(jì)算后大概率分布視差值。

1 α擴(kuò)展移動(dòng)算法的相關(guān)知識(shí)

1.1 構(gòu)造能量函數(shù)

計(jì)算機(jī)視覺里的很多問題都可以歸結(jié)為能量函數(shù)的優(yōu)化問題［7］，比如圖像的立體匹配問題，可以通過構(gòu)造能量函數(shù)，采用優(yōu)化算法求解能量函數(shù)的最小值，與最小值對(duì)應(yīng)的像素標(biāo)記的視差值就是匹配的結(jié)果。

立體匹配的能量函數(shù)一般由數(shù)據(jù)項(xiàng)約束Edata（f）和光滑項(xiàng)約束Esmooth（f）組成，如下

則能量函數(shù)可以表示為

式中：P——圖片所有像素點(diǎn)的集合，p——集合中的一個(gè)像素點(diǎn)，｛p，q｝∈N——圖片中相鄰的兩個(gè)像素點(diǎn)，fp∈L——p的標(biāo)記視差，L——視差范圍，則 Dp（fp）——p點(diǎn)在視差為fp時(shí)匹配代價(jià)，它的表達(dá)式為

式 （3）是圖像中相鄰像素間的懲罰項(xiàng)，它反應(yīng)了區(qū)域內(nèi)部的連續(xù)性和邊界的不連續(xù)性。本文選用了Potts模型的平滑項(xiàng)函數(shù)

其中k＝20，當(dāng)fp＝fq時(shí)，T＝0；fp≠fq時(shí)，T＝1。

1.2 α擴(kuò)展移動(dòng)算法具體描述

由于能量函數(shù)E（f）的最小化求解是一個(gè)非確定性多項(xiàng)式問題，如果采用窮舉法，則算法的計(jì)算量過大，它的狀態(tài)空間為LH×W，其中L為視差范圍，H為圖片的高度，W為圖片的寬度；采用變分方法或者條件迭代模式算法 （iterated conditional mode，ICM 算法），在求解的過程中容易遇到對(duì)初始值敏感、易得到局部極小值的問題，因此，如何計(jì)算出全局最小值一直是個(gè)難題。針對(duì)這個(gè)問題，Boykov采用了ICM算法循環(huán)迭代的思想［8］，通過α擴(kuò)展移動(dòng)對(duì)求得的能量函數(shù)不斷迭代循環(huán)，使其最終收斂于最小值。與ICM算法不同的是α擴(kuò)展移動(dòng)算法是同時(shí)改變大部分的像素標(biāo)記視差值，每次擴(kuò)展移動(dòng)都會(huì)使能量函數(shù)有很大變化，這樣就很好的克服了ICM算法的單個(gè)像素的移動(dòng)中容易遇到局部極小值的問題，使能量函數(shù)向全局最小值收斂。α擴(kuò)展移動(dòng)算法的流程圖如圖1所示。

圖1 α擴(kuò)展移動(dòng)算法流程

a在流程圖中，步驟3到步驟5的執(zhí)行稱為一次內(nèi)部迭代，在內(nèi)部迭代的過程，α是在視差的范圍里隨機(jī)設(shè)定的，步驟2到步驟5的執(zhí)行稱為一次外部循環(huán)。其中，步驟中如何計(jì)算f＾＝argminE（f′）是一個(gè)非常關(guān)鍵的問題，Boykov構(gòu)建了α擴(kuò)展移動(dòng)能量網(wǎng)格圖，首先對(duì)所有視差標(biāo)記不為α的像素點(diǎn)建立能量網(wǎng)格圖，然后通過最大流最小割算法對(duì)能量網(wǎng)格圖進(jìn)行 “切割”（可以簡單理解為優(yōu)化），“切割優(yōu)化”的結(jié)果使其中的部分像素視差被重新標(biāo)記為α，而剩余的則保持原來不變的視差標(biāo)記［9］。α擴(kuò)展移動(dòng)算法采用這樣的優(yōu)化方式不斷循環(huán)修改每個(gè)像素的視差標(biāo)記值，使能量函數(shù)逐漸收斂，最終收斂到全局最小值。

1.3 能量網(wǎng)格圖的構(gòu)造

圖2為α擴(kuò)展移動(dòng)時(shí)構(gòu)造的能量網(wǎng)格圖，為方便理解，把Gα設(shè)置成一維圖像。

圖2 α擴(kuò)展移動(dòng)算法網(wǎng)格

對(duì)于每個(gè)像素點(diǎn)p∈P通過t－linktap和t珔ap連接到源點(diǎn)α和匯點(diǎn)珔α，構(gòu)造的輔助節(jié)點(diǎn)a｛p，q｝通過輔助邊ε｛p，q｝＝｛e｛p，a｝，e｛a，q｝，t珔αα｝連接到p，q，珔α點(diǎn)，所以圖2中所有點(diǎn)的連接邊為

各個(gè)連接邊的權(quán)值容量大小設(shè)置見表1。

表1 連接邊的權(quán)值設(shè)置

1.4 最大流最小割求解能量函數(shù)

在構(gòu)建完能量網(wǎng)格圖后，利用最大流最小割求解能量函數(shù)E（f∧）。本文采用的是Boykov和Kolmogorov提出的最大流最小割算法，該算法是一種雙向搜索并重用搜索樹的增廣路徑算法，雖然算法的理論復(fù)雜度比較高，為，其中s是最大流算法的最大增廣數(shù)目，m和n分別是網(wǎng)格圖中的連接邊和節(jié)點(diǎn)，iter是收斂時(shí)需要迭代的次數(shù)，k是視差的數(shù)目，但是計(jì)算機(jī)視覺的實(shí)際應(yīng)用中卻有著非常高的效率［10］，比其他最大流算法快了2～5倍，因此在立體匹配、圖像恢復(fù)等方面廣泛使用。

2 改進(jìn)的α擴(kuò)展移動(dòng)算法

為分析匹配算法的性能，本文采用均方根誤差 （式（10））和錯(cuò)誤匹配率 （式 （11））兩個(gè)指標(biāo)

其中dc（x，y）是算法計(jì)算所得的視差值，dGT（x，y）是真實(shí)的視差值，δd是容許的錯(cuò)誤視差閾值，本文中δd＝1。

2.1 構(gòu)造循環(huán)停止參數(shù)簡化循環(huán)過程

以 Middlebury［11］提供的標(biāo)準(zhǔn)圖 Tsukuba （384＊288）為例，圖3為經(jīng)過第i次循環(huán)后的視差值分布圖。

圖3 第i次循環(huán)后的視差值分布

本文以視差fp在視差值分布圖中的分布概率構(gòu)造一個(gè)向量P，按照式 （12）構(gòu)造一個(gè)循環(huán)停止參數(shù)θ

圖4是Tsukuba在α擴(kuò)展移動(dòng)后的能量函數(shù)E（f）變化圖，Run0為隨機(jī)標(biāo)記視差后的能量函數(shù)的初始狀態(tài)。仔細(xì)觀察可以發(fā)現(xiàn)在最初的幾次外部循環(huán)后能量函數(shù)值 （直方柱表示）迅速下降，隨著循環(huán)次數(shù)的不斷增加而逐漸單調(diào)遞減，一直衰減到能量函數(shù)最小值時(shí)停止循環(huán)。然而，在不斷循環(huán)的過程中，能量函數(shù)值在接近最小值時(shí)，其收斂速度明顯減小，變化也越來越微弱，這說明α擴(kuò)展移動(dòng)算法的在后面的幾個(gè)循環(huán)中的效率越來越低。

圖4 循環(huán)過程中能量函數(shù)E（f）與Theta（θ）的變化

為了更全面的研究α擴(kuò)展移動(dòng)算法，本文也通過誤匹配率和均方根誤差這兩個(gè)指標(biāo)去分析外部循環(huán)過程中的其他變化。如圖5所示，同樣也可以發(fā)現(xiàn)，隨著不斷地循環(huán)，誤匹配率和均方根誤差也逐漸單調(diào)減小，最后緩慢的收斂于最小值。

圖5 循環(huán)過程中誤匹配率與均方根誤差的變化

針對(duì)以上兩圖的分析，為了提高擴(kuò)展移動(dòng)算法的計(jì)算效率，節(jié)省算法的運(yùn)行時(shí)間，根據(jù)式 （12）構(gòu)造的θ，建立新的循環(huán)機(jī)制，即第i次與第i－1次之間的視差分布變化向量越來越小，當(dāng)循環(huán)停止參數(shù)滿足循環(huán)停止閾值的條件θ＜θthreshold時(shí) （θthreshold為循環(huán)停止閾值），就停止繼續(xù)循環(huán)，這樣相較于傳統(tǒng)的α擴(kuò)展移動(dòng)算法的循環(huán)過程，就減少了循環(huán)過程中能量函數(shù)變化很小的區(qū)間循環(huán)，縮短了算法的計(jì)算時(shí)間，提高了算法的計(jì)算效率。

2.2 改變?chǔ)翑U(kuò)展移動(dòng)順序

在α擴(kuò)展移動(dòng)算法的內(nèi)部迭代過程中，α值的設(shè)定是在視差值范圍［fmin，fmax］隨機(jī)選取的。如果將α值按照標(biāo)準(zhǔn)視差分布圖中大概率的視差值優(yōu)先設(shè)定，那么與其他的α小概率分布視差值相比，在進(jìn)行α擴(kuò)展移動(dòng)時(shí)能量函數(shù)的變化會(huì)有更大的影響。因此，本文采用了將待匹配的圖像進(jìn)行初始視差計(jì)算的方法，將α按照計(jì)算后的初始視差大概率分布視差值優(yōu)先設(shè)定，這樣在內(nèi)部迭代的過程中，能量函數(shù)能以更快的速度收斂于最小值。

由于初始視差計(jì)算的方法對(duì)視差計(jì)算的匹配精度結(jié)果要求不高，只要求計(jì)算出視差值范圍內(nèi)的大概率視差值，本文選擇了基于區(qū)域的局部匹配算法中的SAD算法 （sum of absolute differences）。SAD算法是在左圖中待匹配像素點(diǎn)創(chuàng)建一個(gè)n×n的窗口，然后沿著極線在右圖視差范圍內(nèi)選擇相似性最大的像素點(diǎn)作為匹配點(diǎn)。

2.3 改進(jìn)的α擴(kuò)展移動(dòng)算法的流程圖

圖6是改進(jìn)的α擴(kuò)展移動(dòng)算法的流程圖。和原始的流程圖比較，本文對(duì)步驟2、步驟7和步驟8做了修改，在步驟2中，優(yōu)先將α按照初始視差計(jì)算后的大概率視差值設(shè)定，步驟7中，增加了θ的計(jì)算，步驟8中，增加一個(gè)閾值判定，即當(dāng)計(jì)算的θ滿足循環(huán)停止閾值時(shí)就不再進(jìn)行循環(huán)，計(jì)算停止，反之，則繼續(xù)循環(huán)。閾值θthreshold的選擇嚴(yán)重影響著算法的匹配時(shí)間和精度。表2是以Tsukuba為例在不同θthreshold條件下的實(shí)驗(yàn)結(jié)果，如果θthreshold選擇過大，算法匹配時(shí)間縮短，但算法的匹配精度有很大誤差，如果θthreshold選擇過小，則算法匹配時(shí)間延長，匹配精度提高。本文改進(jìn)α擴(kuò)展移動(dòng)算法選擇的θthreshold＝1。

表2 不同θthreshold的實(shí)驗(yàn)結(jié)果

圖6 改進(jìn)的α擴(kuò)展移動(dòng)算法的流程

3 實(shí)驗(yàn)和結(jié)果

為了驗(yàn)證改進(jìn)的圖割算法的正確性，本文根據(jù)Middleburry上提供的標(biāo)準(zhǔn)圖像進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)的數(shù)據(jù)結(jié)果以匹配時(shí)間、均方根誤差和錯(cuò)誤匹配率作為評(píng)價(jià)指標(biāo)。實(shí)驗(yàn)圖像和數(shù)據(jù)結(jié)果如圖7和表3所示。

圖7 匹配后的視差圖對(duì)比

表3 視差圖的評(píng)價(jià)指標(biāo)對(duì)比

根據(jù)圖7原始算法和改進(jìn)算法匹配后的視差圖對(duì)比，直觀上觀察改進(jìn)算法獲得了幾乎和原始算法一致的稠密視差圖，根據(jù)表格3中的均方根誤差和誤匹配率的指標(biāo)對(duì)比，原始的α擴(kuò)展移動(dòng)算法和改進(jìn)的α擴(kuò)展移動(dòng)算法匹配的都獲得了良好的匹配效果，而表格2視差圖的匹配時(shí)間表明，改進(jìn)算法比原始算法在效率上卻明顯提高，計(jì)算時(shí)間大大縮短，這是由于構(gòu)造的循環(huán)停止參數(shù)滿足條件時(shí)停止循環(huán)，減少算法的循環(huán)過程，將α優(yōu)先按初始匹配后的大概率視差分布設(shè)置則使能量函數(shù)以更快的速度收斂，這樣使改進(jìn)的算法不僅可以得到精確視差圖的同時(shí)，匹配時(shí)間也大大減小了。

4 結(jié)束語

在計(jì)算機(jī)視覺領(lǐng)域中，采用α擴(kuò)展移動(dòng)算法去解決立體匹配問題是一種有效的方法，通過建立能量網(wǎng)格圖不斷的循環(huán)優(yōu)化求解能量函數(shù)最小值，在低紋理區(qū)域也可以獲得稠密精確的視差圖，但該類算法的復(fù)雜度很高，匹配時(shí)間比較長。本文仔細(xì)研究了α擴(kuò)展移動(dòng)算法能量函數(shù)的優(yōu)化過程，提出了兩個(gè)改進(jìn)，一是在外部循環(huán)的過程中提出了循環(huán)停止機(jī)制，，二是改變了原始算法α設(shè)定的隨機(jī)性。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法 “遺傳了”α擴(kuò)展移動(dòng)算法的優(yōu)點(diǎn)，不僅可以獲得幾乎一致匹配精確高的稠密視差圖，而且在算法的匹配時(shí)間大大縮短了，與原始算法比較減少了60～75%。由于α擴(kuò)展移動(dòng)也應(yīng)用于計(jì)算機(jī)視覺的其他領(lǐng)域如圖像恢復(fù)和圖像分割等方面［12－14］，不同的是能量函數(shù)表達(dá)式不一樣，因此改進(jìn)的算法也可以在圖像處理方面的其他領(lǐng)域里獲得應(yīng)用。

［1］BAI Ming，ZHUANG Yan，WANG Wei.Progress in binocular stereo matching algorithms ［J］.Control and Decision，2008，23 （7）：721－729（in Chinese）.［白明，莊嚴(yán)，王偉.雙目立體匹配算法的研究與進(jìn)展 ［J］.控制與決策，2008，23 （7）：721－729.］

［2］WANG Nian，F(xiàn)AN Yizheng，BAO Wenxia.An images matching algorithm based on graph cuts ［J］ACTA Electronica Sinica，2006，34 （2）：232－236 （in Chinese）.［王年，范益正，鮑文霞.基于圖割的圖像匹配算法 ［J］.電子學(xué)報(bào)，2006，34 （2）：232－236.］

［3］ZHANG Lingtao，QU Daokui，XU Fang.An improved stereo matching algorithm based on graph cuts［J］.Robot，2010，32 （1）：215－219（in Chinese）.［張令濤，曲道奎，徐方.一種基于圖割的改進(jìn)立體匹配算法 ［J］.機(jī)器人，2010，32 （1）：215－219.］

［4］Boykov Y，Veksler O，Zabih R.Fast approximate energy minimization via graphcuts ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23 （11）：1222－1239.

［5］Kolmogorov V，Zabin R.What energy functions can be minimized via graphcuts ［J］.IEEE Transon Pattern Analysis and Machine Intelligence，2004，26 （2）：147－159.

［6］LU Ali，TANG Zhenmin.Anα－expansion stereo algorithm based on segment－constraint ［J］.PR＆AI，2010，23 （3）：385－395 （in Chinese）.［盧阿麗，唐振民.基于分割約束的α擴(kuò)展體視算法［J］.模式識(shí)別與人工智能，2010，23 （3）：385－395.］

［7］WU Chunhong，F(xiàn)U Guoliang.A stereo matching method based on K－means segmentation and neighborhood constraints relaxation ［J］.Chinese Journal of Computers，2011，34 （4）755－760 （in Chinese）.［伍春洪，付國亮.一種基于圖像分割及鄰域限制與放松的立體匹配方法 ［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34 （4）755－760.］

［8］Gong M.A performance study on different cost aggregation approaches used in real－time stereo matching ［J］.International Journal of Computer Vision，2007，75 （2）：283－296.

［9］XU Sheng，YUN Ting，YE Ning.Research on stereo matching algotithm based on disparity map optimization ［J］.Computer Engineering and Design，2012，33 （2）：658－664 （in Chinese）.［徐昇，云挺，業(yè)寧.基于視差圖優(yōu)化的立體匹配算法研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33 （2）：658－664.］

［10］Candemir S，Akgul Y S.Adaptive regularization parameter for graph cut segmentation ［C］／／Proceedings of the 7th International Conference on Image Analysis and Recognition.Springer Berlin Heidelberg，2010：117－126.

［11］Microsoft research of disparity matching algorithm ［EB／OL］.［2009－07－26］.http：／／vision.meiddlebuty.edu／stereo／.

［12］Boykov Y，F(xiàn)unka－Lea G.Graph cuts and efficient N－D image segmentation ［J］.International Journal of Computer Vision，2006，70 （2）：109－131.

［13］Boykov Y，Veksler O.Graph cuts in vision and graphics：Theories and applications ［C］／／Handbook of Mathematical Mode－ls in Computer Vision.New York：Springer US，2006：79－96.

［14］LIU Songtao，YIN Fuliang.The basic principle and its new advances of image segmentation methods based on graph cut［J］.Acta Automatica Sinica，2012，38 （6）：911－922 （in Chinese）.［劉松濤，殷福亮.基于圖割的圖像分割方法及其新進(jìn)展 ［J］.自動(dòng)化學(xué)報(bào)，2012，38 （6）：911－922.］