基于區(qū)域分割的動態(tài)規(guī)劃立體匹配算法

湯炎甫

(福州大學(xué)測試中心，福建 福州 350002)

基于區(qū)域分割的動態(tài)規(guī)劃立體匹配算法

湯炎甫

(福州大學(xué)測試中心，福建 福州 350002)

提出一種基于區(qū)域分割的動態(tài)規(guī)劃立體匹配算法。首先參考圖像經(jīng)自適應(yīng)多閾值切割之后，得到一個由區(qū)域組成的集合，并沿著各個閉合區(qū)域的邊界進行動態(tài)規(guī)劃跟蹤，然后對于非匹配區(qū)域和區(qū)域內(nèi)部分別作視差融合和視差插值處理，獲得最終的稠密視差圖。實驗結(jié)果表明，該算法能夠取得較為理想的效果，視差圖橫向“條紋”瑕疵和邊界區(qū)域上的誤匹配點明顯減少，層次更加分明，整個視差圖平滑性較好，匹配效率有了顯著提高。

視差圖；動態(tài)規(guī)劃；立體匹配；區(qū)域分割

立體視覺技術(shù)是人們通過研究生物捕獲三維空間信息的視覺系統(tǒng)而發(fā)展起來的一門重要的 3D顯示技術(shù)，即通過借助多方位地拍攝目標(biāo)圖像，并合成目標(biāo)的深度視差信息，以完成空間目標(biāo)的立體場景信息重建[1]。立體匹配就是從兩視點或多視點圖像組中獲取空間目標(biāo)深度信息的一個重要步驟，而視差匹配的高精確度和應(yīng)用實時性這兩大難題吸引了諸多學(xué)者前來攻關(guān)。由匹配約束對象的差異性，通常將立體匹配算法[2]劃分為兩類，一類是針對像素局部小鄰域來制定約束策略的局部匹配算法[3]，這類算法易于操作、運行速度快，但在遮擋區(qū)域的匹配效果較差；另一類是采用對整幅圖像制定約束策略的全局匹配算法，此類算法在遮擋區(qū)域能夠?qū)崿F(xiàn)較低的誤匹配率，但計算的復(fù)雜度較高，運行速率較慢，難以達到實時性要求。全局匹配算法主要包括動態(tài)規(guī)劃(dynamic programming，DP)[4-5]和圖切割(graph cuts，GC)[6]等。其中DP立體匹配算法能夠高效地實現(xiàn)稠密視差圖的獲取，但缺乏行、列雙向連續(xù)性約束的融合，視差圖易出現(xiàn)“條紋”瑕疵，同時在非連續(xù)和遮擋區(qū)域，該算法的匹配效果有限，甚至?xí)霈F(xiàn)較高的誤匹配率。針對DP算法的不足，Bobick和Intille[7]制定了地面控制點(ground control point，GCP)策略來約束多種子搜索路徑，該算法能夠較好地消除行間誤匹配對全局匹配的影響，但由于未能制定有效的行間深度關(guān)系的約束策略，容易產(chǎn)生類“拖尾”的塊狀誤匹配。而Wei和Quan[8]采用基于區(qū)域分割的方法來制定立體匹配約束策略，這種針對每個分割區(qū)域來填充視差值的做法能夠有效地避免視差圖“拖尾”現(xiàn)象的出現(xiàn)。Lin和Tomasi[9]通過多次迭代來擬合區(qū)域平面約束，此舉雖然可以得到較好的擬合結(jié)果，但耗時的數(shù)據(jù)處理不利于實際應(yīng)用。

鑒于此，該文提出一種基于區(qū)域分割的DP立體匹配算法。首先將參考圖像自適應(yīng)多閾值切割，得到一個由區(qū)域組成的集合，并沿著各個閉合區(qū)域的邊界來進行DP跟蹤，然后對于非匹配區(qū)域和區(qū)域內(nèi)部分別作視差融合和視差插值處理。經(jīng)驗證，所提算法的運行時間較快，匹配效果良好，并獲得了稠密視差圖。

1 新型視差圖獲取算法的研究

近年來，基于小區(qū)域集合分解處理數(shù)據(jù)的匹配算法被廣泛運用于立體匹配當(dāng)中，究其原因在于此類算法能夠較好地處理視差圖遮擋區(qū)域的匹配問題，同時能夠保持區(qū)域內(nèi)部視差的連續(xù)性。本算法所采用的自適應(yīng)多閾值圖像分割技術(shù)[10]主要通過捕捉二維圖像的灰度數(shù)據(jù)信息，并根據(jù)設(shè)定的精度與參數(shù)來求取閾值最優(yōu)解，確保目標(biāo)能夠在背景圖像中被有效提取，而且便于視差圖的優(yōu)化匹配。參考圖像由自適應(yīng)多閾值切割之后，得到了一個由區(qū)域組成的集合，并沿著各個閉合區(qū)域的邊界來進行DP跟蹤。相較于分割圖像區(qū)域內(nèi)部，在區(qū)域邊界上的不連續(xù)匹配點所占比例較高，故處理好區(qū)域邊界上的匹配結(jié)果會使產(chǎn)生誤匹配的概率大大減少，同時這部分的視差匹配結(jié)果更加有效、可信。本算法首先從邊界上多個種子點出發(fā)沿邊界跟蹤視差，使用GCP來約束DP路徑，并通過統(tǒng)計、計算區(qū)域內(nèi)GCP視差值，獲得區(qū)域的視差區(qū)間，同時對于非匹配區(qū)域做視差融合處理，最后采用一些匹配度較高的GCP和分割區(qū)域邊界點作為構(gòu)建Delaunay三角網(wǎng)格的已知點集，并制定相關(guān)區(qū)域內(nèi)部連續(xù)、平滑約束策略，對未匹配點進行三角片插值[11]填充，以獲取稠密視差表面。此算法流程如圖1所示。

圖1 算法流程

1.1 自適應(yīng)多閾值圖像分割

圖像分割是將一幅參考圖像劃分為若干區(qū)域的過程，在眾多的圖像分割方法中，閾值法因為其計算量小、易于操作等優(yōu)點被廣泛采用。閾值法就是對比圖像背景與目標(biāo)在灰度特征上的不同，通過設(shè)定自適應(yīng)閾值參數(shù)對圖像進行區(qū)域分割，從而提取出背景中的目標(biāo)。在實際應(yīng)用中，處理單一目標(biāo)灰度的圖像比較少，同時繁雜的目標(biāo)和背景會導(dǎo)致單一閾值難以將圖像區(qū)域進行清晰劃分，這時一般會采用多閾值分割方法。本文采用的是自適應(yīng)多閾值圖像分割算法，詳細步驟如下：①借助勢基函數(shù)[12]聚類來確定閾值劃分區(qū)間，設(shè)定A、tc和 ha分別為勢基函數(shù)類的個數(shù)、分割閾值和聚類中心灰度值；②在 hc和 hc+1之間遍歷閾值 tc，并制定形狀連通度約束準則，并求解分割閾值最優(yōu)解由公式：式中，和分別表示目標(biāo)、區(qū)域邊界點所占比例，表示連通度準則；③獲取閾值組最優(yōu)解④自適應(yīng)多閾值圖像分割。

為了檢驗自適應(yīng)閾值分割的效果，將lena實驗圖進行分步切割，如圖2所示。

圖2 多閾值圖像分割過程示意圖

由上所示，將 lena實驗圖進行多閾值圖像分割，其中勢基函數(shù)類的個數(shù)A分別從5~9取值，而多閾值分割實驗圖是由A=9時得到的。顯然，單個閾值分割效果難以滿足實際需求，需要采用自適應(yīng)多閾值圖像分割方法。

1.2 多種子動態(tài)規(guī)劃獲取邊界視差分布

獲取邊界視差分布的一個簡單方法是選定邊界上一個種子點，并從它開始搜索DP尋徑，直至獲取整個邊界視差分布。但由于區(qū)域遮擋和背景模糊等因素的干擾，僅僅依靠采用單個種子點來實現(xiàn)全局視差跟蹤的匹配效果往往不盡人意?；诖?，該算法將采用多個種子點DP尋徑策略，根據(jù)各自分割的子區(qū)域來設(shè)定匹配相似度閾值，并尋找各個區(qū)域邊界上相對應(yīng)的匹配點。一次邊界視差跟蹤過程就是從一個種子點沿著邊界路線出發(fā)直到返回該起點所獲取邊界點視差值的過程，如圖3所示。

圖3中的矩形框圖是以區(qū)域邊界上的像素點為橫軸、視差值為縱軸的視差分布平面示意圖，對每一個邊界的種子點進行動態(tài)跟蹤，以獲得其對應(yīng)的所有匹配點，將多種子DP過程作量化處理，那么相應(yīng)的匹配能量為：

其中，inE 和disE 分別為對應(yīng)到像素灰度相似性和視差連續(xù)性的能量值，1w和2w均為權(quán)值。假設(shè)當(dāng)前邊界點為n，,nid 為n和第i個候選匹配點的視差值，則通過下述途徑確定n的能量值 (,)E n d，搜

圖3 多種子動態(tài)規(guī)劃示意圖

索n在圖3中的所有可能匹配點，則有：

其中，mK 表示匹配成功，是一個預(yù)設(shè)的常值，則結(jié)合式(3)可得：

其中 i= 1,2,··, Mnum，n在圖3中候選匹配點的數(shù)目，若搜索不到候選匹配點的情況下，該算法設(shè)定能量值為一常值：

該算法采用對多個種子點進行多次邊界視差跟蹤，以提高視差結(jié)果的可靠性。由算法運行結(jié)果可知，從不同種子點出發(fā)所獲取的跟蹤路徑較為接近，而事實上，視差匹配往往出現(xiàn)的是一對多的情況，為了確定邊界點所對應(yīng)視差值的唯一解，該算法制定了一種投票選定策略，即在兩個視差值很接近的情況下，對于多個候選視差值都依存于同一邊界點時，該算法采取彼此互相支持投票的策略以表示肯定對方，最終贏票數(shù)最多的視差值就是唯一被選定的，即為所求視差值最優(yōu)解，對于每個邊界點投票選出票數(shù)和多個視差值分別假定為V、d，那么視差分布判定式為：

其中，i、j均為邊界點序號，diTH 是視差變化量閾值。由投票法則來選定所有區(qū)域邊界點的視差值，直至獲得所有分割區(qū)域邊界的視差分布。

1.3 視差點插值填充

由于不連續(xù)匹配點集中分布在區(qū)域邊界上，而區(qū)域內(nèi)部的匹配點具有連續(xù)、平滑的特點，則可以在得到區(qū)域邊界視差后采用插值方法得到區(qū)域內(nèi)部視差。由插值方式的不同，對于區(qū)域中的未匹配點視差插值可按兩種策略來處理：其一，由其鄰域內(nèi)的GCP和邊界匹配點的視差值均值來插值填充；其二，由其鄰域內(nèi)部分遮擋或無遮擋區(qū)域中的最小視差值來插值填充。

該算法采用一些匹配度較高的 GCP和分割區(qū)域邊界點作為構(gòu)建 Delaunay三角網(wǎng)格的已知點集，并制定相關(guān)區(qū)域內(nèi)部連續(xù)、平滑約束策略，對未匹配點采用三角片插值[12]填充。該插值策略操作簡單、運行較快，能夠得到很好的填充效果。

2 實驗結(jié)果與分析

實驗在Intel Core i5 4.2 GHz CPU主頻、4 G內(nèi)存、Windows XP操作系統(tǒng)平臺下進行，采用Visual C++ 2010應(yīng)用軟件來驗證該算法的實時性和精確度。該算法采用Tsukuba和Teddy(源自Middlebury網(wǎng)站)測試圖作為實驗對象，像素尺寸為384 ×288，該算法參考左圖進行自適應(yīng)多閾值圖像分割，所獲得了1、10、28、56、89、105、130、166、185、198、220、240、253、260計14個閾值，由于各區(qū)域內(nèi)存在一些孤立點或是一些孤立的小區(qū)域，該算法選擇在邊界提取前先用中值濾波方法將其并入各相鄰區(qū)域，然后沿著各個閉合區(qū)域的邊界來進行DP跟蹤并獲取視差分布，最后對非匹配區(qū)域和區(qū)域內(nèi)部分別作視差融合和視差插值處理，以獲得稠密視差圖。

為了體現(xiàn)立體匹配效果的優(yōu)越性，該算法視差結(jié)果圖與另兩種算法(分別為雙向 DP算法(DoubleDP)和傳統(tǒng)的GC算法)相對照，通過三種評價標(biāo)準來評判立體匹配的效果：E(%)、D(%)、T(s)，其中E(%)表示誤匹配率，D(%)表示匹配率，T(s) 表示算法的執(zhí)行時間。

其中， dT(i, j)表示標(biāo)準視差圖， dC(i, j)表示計算得到的視差圖，N為視差圖的像素總數(shù)，δd為視差錯誤閾值。

圖4 三種算法分別得到的視差圖

圖4和表1所示的三種算法得到的視差圖結(jié)果可知，本文算法相較于DoubleDP算法和GC算法，其立體匹配效率有了顯著提高，同時視差圖橫向“條紋”瑕疵和邊界區(qū)域上的誤匹配點明顯減少，層次更加分明，整個視差圖平滑性較好。在圖像各分割區(qū)域間隙中的一些孤立點或小區(qū)域采用中值濾波歸并到相鄰區(qū)域所導(dǎo)致匹配結(jié)果的不確定性，以及區(qū)域內(nèi)插值填充的不完整性等諸多原因，致使視差圖仍存在一些誤匹配點。

表1 三種匹配算法的性能比較

3 結(jié) 束 語

提出一種基于區(qū)域分割的DP立體匹配算法，首先參考圖像經(jīng)自適應(yīng)多閾值切割之后，得到了一個由區(qū)域組成的集合，并沿著各個閉合區(qū)域的邊界來進行DP跟蹤，然后對于非匹配區(qū)域和區(qū)域內(nèi)部分別作視差融合和視差插值處理，以獲得最終的稠密視差圖。實驗結(jié)果表明，該算法能夠取得較為理想的效果，與DP算法和GC算法相比，視差圖橫向“條紋”瑕疵和邊界區(qū)域上的誤匹配點明顯減少，層次更加分明，整個視差圖平滑性較好，匹配效率有了顯著提高。

由于 GCP的選定策略和區(qū)域自適應(yīng)閾值分割對該算法視差匹配有著較大的影響，而聚合操作能夠促使區(qū)域分割更加明晰、精確，同時 GCP的選定策略有待進一步地優(yōu)化，故將沿著更加全面準確的 GCP驗證策略和更為高效可靠的圖像分割算法方向作后續(xù)的研究工作。

[1]劉曉麗, 徐光柱, 雷幫軍, 等. 立體匹配技術(shù)研究[C]// 2010系統(tǒng)仿真技術(shù)及應(yīng)用學(xué)術(shù)會議論文集, 2010: 597-602.

[2]Shi C B, Wang G J, Pei X K, et al. An interleaving updating framework of disparity and confidence map for stereo matching [J]. IEICEeice TRANSACTIONS on Information and Systems, 2012, E95-D(5): 1552-1555.

[3]Zhou Yihao, Chen Yanqiu. Feature matching for automated and reliable initialization in three-dimensional digital image correlation [J]. Optics and Lasers in Engineering, 2013, 51(3): 213-223.

[4]Hu Tingbo, Qi Baojun, Wu Tao, et al. Stereo matching using weighted dynamic programming on a single-direction four-connected tree [J]. Computer Vision and Image Understanding, 2012, 116(8): 908-921.

[5]Yu Shuchun, Yu Xiaoyang, Hu Lijuan, et al. Stereo matching for dynamic programming on TRIZ [J]. Information Technology Journal, 2012, 11(7): 891-897.

[6]Wang Daolei, Kah B L. Obtaining depth map from segment-based stereo matching using graph cuts [J]. Journal of Visual Communication and Image Representation, 2011, 22(4): 325-331.

[7]Bobick A F, Intille S S. Large occlusion stereo [J]. International Journal of Computer Vision, 1999, 33(3): 181-200.

[8]Wei Yichen, Quan Long. Region-based progressive stereo matching [C]//Conference on Computer Vision and Pattern Recognition, Washington, DC, 2004: 106-113.

[9]Lin M H, Tomasi C. Surfaces with occlusions from layered stereo [J]. Pattern Analysis and Machine Intelligence, 2004, 26(8): 1073-1078.

[10]張 偉, 蔣 宏, 任 章. 自適應(yīng)多閾值圖像分割算法[J]. 自動化技術(shù)與應(yīng)用, 2007, 26(8): 71-73．

[11]Ji Fengxin, Ou Zongying, Qin Xujia, et al. An algorithm of reconstructing 3D surface from discrete data of layered images based on delaunay triangulation [J]. Journal of Engineering Graphics, 2001, 22(2): 53-58.

[12]裴繼紅, 謝維信. 勢函數(shù)聚類自適應(yīng)多閾值圖像分割[J]. 計算機學(xué)報, 1999, 22(7): 758-762.

Dynamic Programming Stereo Matching Algorithm Based on Region Segmentation

Tang Yanfu
(Measuring Center of Fuzhou University, Fuzhou Fujian 350002, China)

A dynamic programming stereo matching algorithm was proposed based on region segmentation. Firstly, the reference image was divided into several different regions by use of adaptive multi-threshold image segmentation. Then, the multi-seed dynamic programming approach was presented for acquiring disparity distribution along the border of closed areas. Finally, parallax in the mismatching area was fused together and interpolated within its area in order to obtain a dense disparity map. The experiment results reveal that the algorithm is better effective both in decreasing the overall matching error rates on the boundary of the domain and reducing apparent defective stripes. Moreover, its efficiency of matching is improved significantly.

disparity map; dynamic programming; stereo matching; region segmentation

TP 751

A

2095-302X(2015)01-0090-05

2014-03-25；定稿日期：2014-08-25

國家“863”重大專項基金資助項目(2012AA03A301，2013AA030601)；國家自然科學(xué)基金資助項目(61101169，61106053)；福建省自然科學(xué)基金資助項目(2011J01347)

湯炎甫(1964–)，男，福建建甌人，工程師，工學(xué)學(xué)士。主要研究方向為驅(qū)動程序開發(fā)與仿真、應(yīng)用軟件開發(fā)等。E-mail：tyf406@163.com