羅嗣卿，賈子書

（東北林業(yè)大學(xué)信息與計算機(jī)工程學(xué)院，哈爾濱150040）

·圖形圖像處理·

基于動態(tài)規(guī)劃的快速立體匹配算法

羅嗣卿，賈子書

（東北林業(yè)大學(xué)信息與計算機(jī)工程學(xué)院，哈爾濱150040）

為提高立體匹配算法的匹配速度使其滿足實(shí)時性要求，同時減少視差圖中的條紋現(xiàn)象提高匹配準(zhǔn)確率，基于動態(tài)規(guī)劃原理提出一種快速立體匹配算法。利用快速自適應(yīng)權(quán)重累積策略累積匹配成本，通過二維有序表結(jié)構(gòu)加快動態(tài)規(guī)劃的計算速度，采用基于方向?yàn)V波的視差后處理方法減少視差圖中的條紋現(xiàn)象。實(shí)驗(yàn)結(jié)果表明，該算法在保證視差圖準(zhǔn)確的基礎(chǔ)上能有效提高立體匹配效率，可應(yīng)用于實(shí)時匹配系統(tǒng)。

立體匹配；動態(tài)規(guī)劃；自適應(yīng)權(quán)重；快速累積；積分圖像

1 概述

立體匹配是計算機(jī)視覺領(lǐng)域中的一個經(jīng)典問題，目前國內(nèi)外學(xué)者已提出大量的匹配算法來解決這個問題，但由于問題本身的病態(tài)性而導(dǎo)致較少有算法能完美解決匹配中的所有困難。文獻(xiàn)［1］對目前已有的各種算法進(jìn)行了全面的分析和綜述。根據(jù)該文獻(xiàn)提出的分類標(biāo)準(zhǔn)，立體匹配方法可分為局部立體匹配方法和全局立體匹配方法。局部立體匹配方法的關(guān)鍵問題是確定支撐窗口。支撐窗口一方面要盡可能大以便包含足夠多的灰度信息變化從而增強(qiáng)匹配的可靠性，另一方面要盡可能小，以避免投影畸變和窗口內(nèi)視差不一致而導(dǎo)致的不正確匹配。支撐窗口的選擇主要集中在2個方面：一方面集中在支撐窗口的尺寸與形狀，例如文獻(xiàn)［2-3］方法；另一方面集中在窗口內(nèi)像素的支撐權(quán)重，例如文獻(xiàn)［4-5］方法。雖然局部立體匹配方法在匹配準(zhǔn)確率上已取得了較大的進(jìn)展，但是由于在匹配過程中沒有綜合考慮全局信息，導(dǎo)致在非紋理區(qū)域和物體邊界容易產(chǎn)生誤匹配。全局立體匹配方法綜合考慮了立體像對中的全局信息，通過優(yōu)化算法最小化全局能量函數(shù)來求解最優(yōu)視差，這類方法主要包括動態(tài)規(guī)劃［6-9］、置信傳播［10-11］和圖割［12-13］方法。基于圖割和置信傳播的立體匹配方法是一種基于整體圖像的全局匹配算法，其特點(diǎn)是匹配精度高、準(zhǔn)確性好，但算法復(fù)雜度高?；趧討B(tài)規(guī)劃的立體匹配算法是一種基于掃描行的全局匹配算法，其特點(diǎn)是實(shí)現(xiàn)簡單、效率高，但在匹配過程中由于缺少行間一致性約束而導(dǎo)致在視差圖中出現(xiàn)較為明顯的條紋現(xiàn)象。目前，大部分學(xué)者主要針對動態(tài)規(guī)劃立體匹配方法中的兩大問題進(jìn)行研究：一是解決匹配中的條紋現(xiàn)象；二是加快動態(tài)規(guī)劃立體匹配的速度使之成為一種實(shí)時立體匹配方法。Birchfie等人提出一種點(diǎn)對點(diǎn)（Pixelto-Pixel）的動態(tài)規(guī)劃立體匹配方法［9］。該方法分為2個階段：匹配階段和后處理階段。匹配階段包括2個版本的動態(tài)規(guī)劃立體匹配算法：Backw ard-Looking算法和Forward-Looking算法。這2種算法在計算最優(yōu)路徑的過程中執(zhí)行了大量的冗余計算，為此，Birchfie又提出一種快速Forward-Looking算法，有效地縮短了Forw ard-Looking算法的計算時間。但該快速算法在理論上損失了最終解路徑的最優(yōu)性，造成了視差精度損失，而且由于缺少成本累積階段也造成了一部分視差精度的損失。

本文針對快速Forward-Looking算法存在的缺點(diǎn)，提出一種基于動態(tài)規(guī)劃的立體匹配算法。首先根據(jù)快速自適應(yīng)權(quán)重累積策略在視差空間圖中累積匹配成本，然后利用快速Backw ard-Looking算法計算視差，最后通過視差后處理方法去除視差圖中的條紋現(xiàn)象，提高視差精度。

2 視差空間建立

視差空間圖（Disparity-space Image，DSI）［6］是一個三維數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)中的每一點(diǎn)（x，y，d）都代表參考圖像中的像素點(diǎn)（x，y）被賦予視差d時的匹配代價。本文提出的快速立體匹配算法利用這個數(shù)據(jù)結(jié)構(gòu)來表達(dá)匹配中的遮擋和匹配，并通過動態(tài)規(guī)劃獲得一個最小成本路徑，其中路徑中的每一節(jié)點(diǎn)都代表一對匹配。

2.1 匹配成本

匹配成本是立體匹配方法的基礎(chǔ)，它測量的是2個位置的相似性或者不相似性。計算匹配成本最直接方法是采用像素點(diǎn)的灰度差絕對值，但該方法對噪聲和輻射差異的魯棒性很差，易造成能量函數(shù)中的數(shù)據(jù)項(xiàng)不能準(zhǔn)確反應(yīng)匹配約束。因此，在實(shí)際計算過程中經(jīng)常采用截斷的匹配代價計算方法，其計算公式如下：

其中，IL（x，y）表示參考圖像；IR（x，y）表示匹配圖像；IS表示截斷閾值。

2.2 快速積累方法

在匹配過程中，經(jīng)常需要對匹配成本進(jìn)行累積以增加匹配的可靠性，其成本累積形式可表示為：

將式（3）代入式（2）整理得：

為了能使用積分圖像加速該權(quán)重函數(shù)的計算，本文將函數(shù)f（k）取為恒定的常數(shù)函數(shù)ω，為此，式（4）可簡化為：

針對式（5）中的c（p，d），c（p，d）IL（p），c（p，d）和IL（p）分別建立積分圖像，然后使用這些積分圖像累積匹配成本，從而提高累積過程的計算效率，使累積過程的計算復(fù)雜度與窗口大小無關(guān)。

3 動態(tài)規(guī)劃原理及快速實(shí)現(xiàn)

3.1 動態(tài)規(guī)劃原理

本文提出的立體匹配方法是一種基于掃描行優(yōu)化的全局立體匹配方法，它把立體匹配中的對應(yīng)搜索問題闡述為在每一掃描行y0所對應(yīng)的二維代價矩陣φy0［d，x］=c（x，y0，d）中（如圖1（a）所示）查找最優(yōu)成本路徑問題，其最優(yōu)路徑上的每一節(jié)點(diǎn)代表著相應(yīng)的匹配點(diǎn)。針對每一掃描行y0，其相應(yīng)的能量函數(shù)可表達(dá)為：

其中，κOCC表示遮擋懲罰；kr表示匹配獎勵；c（xi，y0，d）表示匹配成本；NOCC和Nm分別表示遮擋數(shù)和匹配數(shù)。如圖1（b）和圖1（c）所示，根據(jù)次序性約束和遮擋約束，當(dāng)前匹配點(diǎn)（di，xi）的直接前驅(qū)和直接后繼可分別表示為：

其中，Δ表示最大視差。利用動態(tài)規(guī)劃技術(shù)在代價矩陣φy0［x，d］上求解最優(yōu)成本路徑，相當(dāng)于計算如式（9）所示的遞歸公式：

反向追蹤找到最優(yōu)成本路徑。在文獻(xiàn)［9］中根據(jù)圖1（b）更新代價矩陣的算法稱為Backward-Looking算法，而根據(jù)圖1（c）更新代價矩陣的算法稱為Forward-Looking算法。

圖1 動態(tài)規(guī)劃的搜索空間

3.2 快速Forward-Looking算法的最優(yōu)性分析

Backward-Looking算法和Forward-Looking算法在計算最優(yōu)路徑時執(zhí)行了大量的冗余計算，為減少這部分冗余計算，文獻(xiàn)［9］提出了一種快速的Forw ard-Looking算法。該算法是在Forward-Looking算法的基礎(chǔ)上通過修剪策略減少這些不必要的計算，該修剪策略為：如果某一匹配的匹配成本大于其所在行中的最低匹配成本，則拒絕向右擴(kuò)展該匹配；類似地，如果某一匹配的匹配成本大于其所在列中的最低匹配成本，則拒絕向下擴(kuò)展該匹配。雖然該算法減少了大量的冗余計算，提高了算法的匹配速度，將優(yōu)化部分的時間復(fù)雜度從O（nΔ2）降到了O（nΔlgΔ），但是該算法導(dǎo)致解路徑損失了最優(yōu)性，造成了視差精度的損失。

如圖2所示，存在一匹配點(diǎn)p和及其后繼匹配點(diǎn)c，它們之間存在著左遮擋?，F(xiàn)假設(shè)存在一點(diǎn)r，它與匹配點(diǎn)p位于同一掃描行并且假設(shè)r點(diǎn)的匹配成本小于p點(diǎn)的匹配成本即r0（r）＜r0（p）。那么當(dāng)快速算法遇見匹配點(diǎn)p時，則拒絕向右擴(kuò)展匹配點(diǎn)p，因?yàn)樵谒诘男兄写嬖诟偷钠ヅ涑杀?。然而，如果p點(diǎn)左邊那些匹配點(diǎn)的匹配成本都大于p點(diǎn)的匹配成本時，則到c點(diǎn)的最優(yōu)路徑很可能會經(jīng)過p點(diǎn)，所以會使解路徑損失其最優(yōu)性，從而導(dǎo)致視差精度的損失。

圖2 最優(yōu)性損失

3.3 快速Backw ard-Looking算法

為了提高動態(tài)規(guī)劃立體匹配方法的匹配效率同時保證不損害解路徑的最優(yōu)性，本文提出了一種快速Backward-Looking算法。該算法以Backward-Looking算法為基礎(chǔ)，通過二維有序表結(jié)構(gòu)加快了動態(tài)規(guī)劃部分的計算，而且該算法在理論上沒有損失解路徑的最優(yōu)性?？焖賹?shí)現(xiàn)動態(tài)規(guī)劃立體匹配算法的關(guān)鍵是快速實(shí)現(xiàn)遞歸公式（式（9））中的最小化操作。Birchfie提出的Forward-Looking算法和Backward-Looking算法實(shí)現(xiàn)最小化操作的時間復(fù)雜度為O（Δ），而其提出的快速Forward-Looking算法通過修剪策略減少了不必要的節(jié)點(diǎn)擴(kuò)展，將最小操作的時間復(fù)雜度降低為O（lgΔ）。為了加快最小化操作的計算速度，本文首先分析式（9）中最小化操作的結(jié)構(gòu)。由于式（9）中的遮擋懲罰κOCC是一個恒定的常數(shù)項(xiàng)，因此

其中的最小化操作可以簡化為：

如果已知：

則式（10）可以簡化為：

通過式（13）計算動態(tài)規(guī)劃中的最小化操作只需3次比較，與視差范圍Δ無關(guān)。由于二維數(shù)組a，b存在如式（14）與式（15）所示的遞歸關(guān)系：

因此，本文設(shè)計2個二維有序表a和b，其中的每一點(diǎn)都分別代表垂直方向和對角方向上的最小值，而且維護(hù)每個二維有序表僅需要一次比較，其二維有序表的結(jié)構(gòu)如圖3所示。其中，成本矩陣φ中每個元素對應(yīng)著視差空間圖中相應(yīng)的元素；有序表a中每個元素都是一個三元組（v，d，x），v代表φ［0，x］～φ［d，x］之間的最小值，d和x代表其相應(yīng)的坐標(biāo)；有序表b中每個元素也都是一個三元組（v，d，x），v代表φ［d+x，0］～φ［d，x］之間的最小值，d和x代表其相應(yīng)的坐標(biāo)。

圖3 最小化操作的快速實(shí)現(xiàn)過程

本文以計算φ［4，4］為例來說明這一快速計算過程，如圖3中代價矩陣所示，φ［4，4］為圖3中的黑色單元格。如果根據(jù)式（9）計算該單元格的值，則有：

式（16）表明計算每個單元格需要Δ次比較。如果根據(jù)有序表a和b計算該值，則有：

式（17）表明根據(jù)有序表計算該值僅需要3次比較，而且維護(hù)有序表a和b僅需要2次比較，通過該快速計算方法可以節(jié)省大量的計算時間，而且沒有損失解路徑的最優(yōu)性。

本文提出的加速方法僅適用于Backward-Looking算法，因?yàn)楫?dāng)計算當(dāng)前節(jié)點(diǎn)最優(yōu)匹配代價時，它的所有前驅(qū)節(jié)點(diǎn)都已計算完成，而且可以在計算最優(yōu)代價的同時來維護(hù)這2個有序表，具體算法如下所示：

3.4 基于方向?yàn)V波的視差后處理

由于動態(tài)規(guī)劃立體匹配算法在優(yōu)化過程中缺少行間一致性限制導(dǎo)致在視差圖中產(chǎn)生了條紋現(xiàn)象。因此本文提出一種基于方向?yàn)V波的視差后處理方法，該方法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單、速度快，可以有效地減少條紋現(xiàn)象。

在該視差后處理方法中，首先提出一種線狀濾波器族，該濾波器族中的每個濾波器之間間隔相等的角度，且每個濾波器與水平方向分別成θi角度，然后分別使用這些濾波器對視差圖中的每個像素進(jìn)行處理。

圖4顯示了一個線狀濾波器族，圖中的每個濾波器之間相隔15°。

圖4 線狀濾波器族

一般來講，每個線狀濾波器含有2 l+1個像素，且與水平方向成θi角度，其數(shù)學(xué)表達(dá)式為：

基于方向?yàn)V波的視差后處理方法的具體過程如下：

（1）在濾波器族中選擇一濾波器fθi（x，y）。

（2）在視差圖中選擇一像素點(diǎn)（x，y），然后對在該點(diǎn)濾波器內(nèi)的像素進(jìn)行統(tǒng)計生成視差直方圖，視差直方圖內(nèi)視差出現(xiàn)頻率最高的視差即為mode，其頻率為max（x）；（x，y）點(diǎn)的視差d及其左右相鄰視差d-1，d+1的出現(xiàn)頻率分別為hist［d］，hist［d-1］，hist［d+1］，它們的頻率和為inertia=hist［d］+ hist［d-1］+hist［d+1］。

（3）如果max（x）＞inertia，則當(dāng)前點(diǎn)（x，y）的視差為mode，否則如果hist［d-1］＞max（x），則當(dāng)前點(diǎn)（x，y）的視差為d-1，否則如果hist［d+1］＞max（x），則當(dāng)前點(diǎn)（x，y）的視差為d+1。

經(jīng)過上述濾波處理之后，已基本去除視差圖中的條紋現(xiàn)象，而且可以有效提高視差的準(zhǔn)確度。在實(shí)際應(yīng)用當(dāng)中，一般選擇較少的濾波器即可獲得較好的效果，本文選擇了4個濾波器，即θi∈［0°，45°，90°，135°］。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

為驗(yàn)證本文算法的性能，本文使用了C++語言實(shí)現(xiàn)了該算法，并在CPU Pentium IV 2.2 GHz，內(nèi)存2 GB，操作系統(tǒng)W indow s XP的環(huán)境下對M iddlebury網(wǎng)站上提供的立體數(shù)據(jù)集Tsukuba，Venus，Saw tooth和Map進(jìn)行了測試。

4.2 經(jīng)驗(yàn)參數(shù)分析

在本文提出的立體匹配方法當(dāng)中涉及到了一些經(jīng)驗(yàn)參數(shù)的選擇，這些參數(shù)會直接影響立體匹配方法的匹配精度，要選擇合適的經(jīng)驗(yàn)參數(shù)保證達(dá)到最好的匹配效果。為此，本文以M ap立體像對為測試對象，分析了成本截斷閾值、遮擋成本及匹配獎勵對立體匹配精度的影響以確定合適的經(jīng)驗(yàn)參數(shù)。

分別進(jìn)行3組實(shí)驗(yàn)測試經(jīng)驗(yàn)參數(shù)對匹配精度的影響。

實(shí)驗(yàn)1 分析了成本截斷閾值TS對匹配精度的影響。首先假定遮擋成本κOCC=15，匹配獎勵kr= 30，然后測試成本截斷閾值對匹配精度的影響，具體測試結(jié)果如表1所示。實(shí)驗(yàn)1結(jié)果表明成本截斷閾值為30時，壞點(diǎn)比例最低，立體匹配效果最好。

表1 成本截斷閾值對匹配精度的影響

實(shí)驗(yàn)2 分析匹配獎勵kr對匹配精度的影響。首先假定遮擋成本κOCC=15，成本截斷閾值TS=30，測試匹配獎勵kr對匹配精度的影響，具體測試結(jié)果如表2所示。實(shí)驗(yàn)2結(jié)果表明匹配獎勵為40，45，50時，壞點(diǎn)比例最低，具有較好的匹配效果。

表2 匹配獎勵對匹配精度的影響

實(shí)驗(yàn)3 分析遮擋懲罰κOCC對匹配精度的影響。首先假定匹配獎勵kr=40，成本截斷閾值TS=30，測試遮擋懲罰對匹配精度的影響，具體測試結(jié)果如表3所示。實(shí)驗(yàn)3結(jié)果表明遮擋懲罰為15時，壞點(diǎn)比例最低。

表3 遮擋懲罰對匹配精度的影響

通過以上3組實(shí)驗(yàn)可以看出，當(dāng)匹配獎勵kr= 40，成本截斷閾值TS=30及κOCC=15時，可以達(dá)到最佳的匹配效果。因此，在后續(xù)的測試當(dāng)中，選擇該組參數(shù)進(jìn)行測試。

4.3 時間復(fù)雜度分析

為提高匹配精度，本文在匹配之前加入了成本累積，該累積策略只包含了值域支撐支持，忽略了空間支撐；然后選擇了二次函數(shù)作為窗口函數(shù)；最后通過積分圖像加速該過程的計算速度使其與窗口大小無關(guān)。本文提出的快速自適應(yīng)成本累積的計算時間與沒有使用積分圖像累積過程的計算時間對比如圖5所示。可以看出，當(dāng)沒有使用積分圖像時，累積速度隨著窗口大小的增加而迅速增加；而當(dāng)使用積分圖像時，該過程的計算時間與窗口大小無關(guān)，其計算時間表現(xiàn)為平行于x軸的一條直線。

圖5 累積過程的時間對比

Backw ard-Looking算法和Forw ard-Looking算法的時間復(fù)雜度為O（nΔ2），其中，n為圖像寬度，Δ為最大視差搜索范圍；快速Forw ard-Looking算法的時間復(fù)雜度為O（nΔlgΔ）；而本文提出的快速Backw ard-Looking算法的時間復(fù)雜為O（nΔ）。上述4種算法的運(yùn)行時間對比如圖6所示，可以看出本文的快速算法具有更快的匹配速度，而且該算法沒有導(dǎo)致解路徑損失最優(yōu)性造成視差精度損失。

圖6 運(yùn)行時間對比

4.4 匹配精度分析

為驗(yàn)證本文算法的立體匹配效果，利用本文算法對Tsukuba，Venus，Saw tooth和M ap進(jìn)行實(shí)驗(yàn)，結(jié)果分別如圖7～圖10所示?？梢钥闯?，經(jīng)過視差后處理之后視差圖中的條紋現(xiàn)象明顯減少，本文算法的最終視差圖非常接近于真實(shí)視差圖，具有較好的匹配效果。

圖7 Tsukuba圖像實(shí)驗(yàn)結(jié)果

圖8 Venus圖像實(shí)驗(yàn)結(jié)果

圖9 Saw tooth圖像實(shí)驗(yàn)結(jié)果

圖10 M ap圖像實(shí)驗(yàn)結(jié)果

將本文算法與同類算法（傳統(tǒng)DP，SO，GCP+ DP算法、Two-Pass算法、TreeDP算法和Pixel-to-Pixel算法）的壞點(diǎn)比例進(jìn)行對比，結(jié)果如表4所示?？梢钥闯觯疚奶岢龅暮筇幚硭惴◤?fù)雜度非常低，處理實(shí)驗(yàn)中的立體像對的時間一般在0.2 s左右。為了給出匹配精度的定量分析，本文同時計算了非遮

擋區(qū)域all、非紋理區(qū)域untex和視差不連續(xù)區(qū)域disc的誤匹配率，并與其他同類算法進(jìn)行了對比。

表4 本文算法與其他算法的處理結(jié)果對比%

由表4可見，本文算法的優(yōu)于其他動態(tài)規(guī)劃算法，而且該匹配算法具有較快的匹配速度。實(shí)驗(yàn)結(jié)果表明，本文算法是一種高效可靠的立體匹配算法，它不僅可以獲得準(zhǔn)確性較高的視差圖，而且具有較快的匹配速度，有效地提高了算法的匹配效率，可以應(yīng)用于實(shí)時匹配系統(tǒng)。

5 結(jié)束語

通過分析成本函數(shù)結(jié)構(gòu)發(fā)現(xiàn)，利用恒定的遮擋懲罰能大幅簡化成本函數(shù)的結(jié)構(gòu)，使用2個二維有序表可有效提高算法的計算速度。為此，本文在此基礎(chǔ)上提出了一種基于動態(tài)規(guī)劃的快速立體匹配算法。首先利用積分圖像加快自適應(yīng)權(quán)重累積策略的計算速度，使計算量與窗口大小無關(guān)，然后通過一種二維有序表結(jié)構(gòu)在保證不損失解最優(yōu)性的情況下提高動態(tài)規(guī)劃部分的運(yùn)算速度，最后采用視差后處理方法減少視差圖中的條紋現(xiàn)象。實(shí)驗(yàn)結(jié)果表明，該算法是一種高效可靠的立體匹配算法，可以應(yīng)用于實(shí)時匹配系統(tǒng)。下一步將研究保存邊緣的濾波方法以改善成本累積過程，并嘗試將本文算法移植到GPU平臺，以加快匹配速度。

［1］ Scharstein D，Szeliski R.A Taxonomy and Evaluation of Dense Two-frame Stereo Correspondence Algorithms［J］. International Journal of Computer Vision，2002，47（1）：7-42.

［2］ Yang Qingxiong.Stereo Matching Using Tree Filtering［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，37（4）：834-846.

［3］ 祝世平，李 政.基于改進(jìn)梯度和自適應(yīng)窗口的立體匹配算法［J］.光學(xué)學(xué)報，2015，35（1）：123-131.

［4］ Heo Y S，Lee K M，Lee S U.Robust Stereo Matching Using Adaptive Normalized Cross-correlation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（4）：807-822.

［5］ 翟振剛，陸 耀，趙 紅.利用塊幾何約束及視差概率的立體匹配算法［J］.軟件學(xué)報，2010，21（11）：2985-2998.

［6］ Bobick A F，Intille S S.Large Occlusions Stereo［J］. International Journal of Computing Vision，1999，33（3）：181-200.

［7］ Kim JC，Lee K M，Choi B T，et al.A Dense Stereo Matching Using Two-pass Dynamic Programming with Generalized Ground Control Points［C］//Proceedings of IEEE Computing Society Conference on Computing V ision and Pattern Recognition.San Diego，USA：IEEE Press，2005：1075-1082.

［8］ Veksler O.Stereo Correspondence by Dynamic Programming on a Tree［C］//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego，USA：IEEE Press，2005：384-390.

［9］ Birchfield S，Tomasi C.Depth Discontinuities by Pixelto-Pixel Stereo［J］.International Journal of Computing Vision，1999，35（3）：269-293.

［10］ Da Feipeng，He Fu，Chen Zhangwen.Stereo Matching Based on Dissimilar Intensity Support and Belief Propagation［J］.Journal of Mathematical Imaging and Vision，2013，47（1/2）：27-34.

［11］ 張驚雷，王艷姣.基于圖像區(qū)域分割和置信傳播的立體匹配算法［J］.計算機(jī)工程，2013，39（7）：257-260，278.

［12］ Wang Daolei，Lim K B.Obtaining Depth Map from Segment-based Stereo Matching Using Graph Cuts［J］. Journal of Visual Communication and Image Representation，2011，22（4）：325-331.

［13］ 祝世平，楊 柳.基于自適應(yīng)分水嶺的圖割的立體匹配算法［J］.光學(xué)學(xué)報，2013，33（3）：228-236.

編輯金胡考

Fast Stereo Matching Algorithm Based on Dynamic Programming

LUO Siqing，JIA Zishu
（College of Information and Computing Engineering，Northeast Forestry University，Harbin 150040，China）

A fast stereo matching algorithm based on dynamic programming is proposed to improve the efficiency of stereo matching to meet the real-time requirement and reduce the streaking phenomenon in a disparity map to increase matching accuracy.In this algorithm，the fast adaptive weight aggregation is firstly used to aggregate raw matching costs. Secondly，the stage of dynamic programming for computation of disparities is accelerated by two dimensional order tables.Finally，a disparity post processing method based on oriented filters is em ployed to reduce the streaking phenomenon in a disparity map.Experimental results show that the proposed algorithm can improve the efficiency of stereo matching and the matching accuracy.It can be applied in real time matching system.

stereo matching；dynamic programming；adaptive weight；fast aggregation；integral image

羅嗣卿，賈子書.基于動態(tài)規(guī)劃的快速立體匹配算法［J］.計算機(jī)工程，2015，41（11）：224-231.

英文引用格式：Luo Siqing，Jia Zishu.Fast Stereo Matching Algorithm Based on Dynamic Programming［J］.Computer Engineering，2015，41（11）：224-231.

1000-3428（2015）11-0224-08

A

TP391.41

10.3969/j.issn.1000-3428.2015.11.039

國家自然科學(xué)基金資助項(xiàng)目（71473034）。

羅嗣卿（1964-），男，副教授、碩士，主研方向：圖像處理，數(shù)據(jù)挖掘；賈子書，碩士。

2015-06-01

2015-07-21 E-m ail：luosq@nefu.edu.cn