近來(lái)研究立體匹配，從入門(mén)開(kāi)始，先學(xué)習(xí)1些基本的算法思想。
立體匹配算法中，全局匹配是1個(gè)很重要的部份，利用圖象的全局束縛信息，對(duì)局部圖象的模糊不敏感，它的計(jì)算代價(jià)很高。全局匹配算法通過(guò)構(gòu)建全局能量函數(shù)，然后通過(guò)優(yōu)化方法最小化全局能量函數(shù)以求得致密視差圖。

全局匹配算法1般有動(dòng)態(tài)計(jì)劃、置信傳播、摹擬退火、圖割法、遺傳學(xué)等，這里首先介紹動(dòng)態(tài)計(jì)劃，也是從1些論文中提取的思想，可能有不對(duì)的地方，望指正。

動(dòng)態(tài)計(jì)劃的思想就是把求解全部圖象深度值的進(jìn)程分解為1些子進(jìn)程，逐一求解子進(jìn)程，具體進(jìn)程為根據(jù)外極線(xiàn)順序束縛，通過(guò)在視差圖象上尋覓最小代價(jià)路徑得到終究視差圖，從而減少了算法的復(fù)雜度，動(dòng)態(tài)計(jì)劃的思想體現(xiàn)了順序束縛和連續(xù)性束縛。傳統(tǒng)的動(dòng)態(tài)計(jì)劃算法可以很好的處理因局部紋理單1而釀成的誤匹配，算法復(fù)雜度不高，缺點(diǎn)是匹配進(jìn)程疏忽了每條極線(xiàn)間視差的束縛，致使了視差圖有條紋瑕疵現(xiàn)象。

參考論文：
雙目視覺(jué)立體匹配方法研究-魏朋玉-重慶大學(xué)
基于動(dòng)態(tài)計(jì)劃的立體匹配算法研究-龔文-南昌航空大學(xué)
基于動(dòng)態(tài)計(jì)劃和置信傳播 的立體匹配算法的研究 -劉英杰-燕山東大學(xué)學(xué)

1：首先了解下動(dòng)態(tài)計(jì)劃算法的思想：
解決爬樓梯的問(wèn)題：
1個(gè)人每次只能走1層樓梯或兩層樓梯，問(wèn)走到80層1共有多少種方法。
解：設(shè)DP[i]為走到第i層1共有多少種方法，那末DP[80]就是所求的目標(biāo)。很明顯DP[1]=1,DP[2]=2(走到第1層只有1種就是走1層樓梯，第2層有兩種：走兩次1層樓梯或走1次兩層樓梯)。同理走到第[i]層樓梯可以從第i⑴層走1層，或從i⑵走兩層。很容易得到：
遞推公式：DP[i]=DP[i⑴]+DP[i⑵]
邊界條件：DP[1]=1 DP[2]=2
則自頂向下的解法：

自低向上的解法：

動(dòng)態(tài)計(jì)劃大致就是這個(gè)思路。

2：動(dòng)態(tài)計(jì)劃立體匹配基于極線(xiàn)束縛，通過(guò)順次尋覓每條極線(xiàn)上匹配點(diǎn)對(duì)的最小代價(jià)路徑的動(dòng)態(tài)尋優(yōu)方法求解全局能量最小化，得到匹配視差圖。算法步驟：
A：階段劃分：傳統(tǒng)的方法是只在水平方向?qū)ひ拻呙椟c(diǎn)，所以算法是在水平掃描線(xiàn)的視差空間切面上尋覓最優(yōu)路徑的進(jìn)程，以像素點(diǎn)的行方向?yàn)闄M坐標(biāo)，視差值d為縱坐標(biāo)，順次將全部進(jìn)程分為1,2,3,4……k個(gè)階段，每一個(gè)x坐標(biāo)點(diǎn)對(duì)應(yīng)1個(gè)階段，把立體匹配劃分成可以排序的若干個(gè)階段。

B：肯定狀態(tài)
將上述各個(gè)階段所處的匹配階段用不同的狀態(tài)表示。狀態(tài)的選擇要滿(mǎn)足無(wú)后向性。無(wú)后向性的意思就是當(dāng)前階段的狀態(tài)只是之前階段的綜合結(jié)果，其實(shí)不對(duì)后續(xù)階段產(chǎn)生影響。

共有3種狀態(tài)：相互匹配M，左可見(jiàn)右遮擋為L(zhǎng)（某點(diǎn)在右圖中沒(méi)有匹配點(diǎn)），右可見(jiàn)左遮擋為R（如果前1個(gè)點(diǎn)的視差比后1個(gè)視差大，就是前面點(diǎn)的匹配點(diǎn)在后1個(gè)點(diǎn)的匹配點(diǎn)的后面）。
C：狀態(tài)轉(zhuǎn)移方程：所謂狀態(tài)轉(zhuǎn)移方程就是根據(jù)前1階段的狀態(tài)肯定當(dāng)前階段的狀態(tài)，根據(jù)順序性的束縛，允許的狀態(tài)轉(zhuǎn)移情勢(shì)有7種（用小寫(xiě)字母表示前1階段的狀態(tài)，大寫(xiě)字母表示當(dāng)前階段的狀態(tài)）

0表示正確匹配，1、2表示匹配產(chǎn)生左圖象遮擋，4、5表示產(chǎn)生右圖象遮擋點(diǎn)，3、6表示圖象由背景進(jìn)入前景，視差跳變產(chǎn)生其實(shí)不連續(xù)點(diǎn)。

D：求取最優(yōu)解，并記錄該最優(yōu)解的路徑
在實(shí)際編程中，按順序自左向右，或自右向左對(duì)各階段（即同1極線(xiàn)上的點(diǎn)）順次進(jìn)行計(jì)算，計(jì)算類(lèi)似性測(cè)度函數(shù)和平滑函數(shù)的最小值，當(dāng)所有階段都計(jì)算完成后，全局能量函數(shù)最小的1條最優(yōu)匹配路徑也就得出來(lái)了。

全局能量函數(shù)表示以下，
E(d)= E(data) + E(smooth)
其中 E(data) 為圖象數(shù)據(jù)束縛項(xiàng)，判斷匹配像素點(diǎn)之間的類(lèi)似性， E(smooth)為相鄰點(diǎn)間的平滑束縛項(xiàng)，判斷相鄰點(diǎn)之間的連續(xù)性。

數(shù)據(jù)項(xiàng)由匹配代價(jià)取得

其中表示左像素點(diǎn)與視差為d的右像素點(diǎn)的匹配代價(jià)函數(shù)。

其中N表示相鄰像素對(duì)的集合，dp，dq分別表示像素點(diǎn)p與像素點(diǎn)q的視差，平滑項(xiàng)s(dp,dq)表示相鄰像素點(diǎn)p、q之間的平滑束縛，定義以下：

其中P1，P2，P3表示不同情況下的懲罰常量，Cp,q表示待匹配的像素點(diǎn)與其相鄰點(diǎn)q之間的色采差異，當(dāng)相鄰點(diǎn)視差值相同時(shí)，懲罰量為0;差值為1時(shí)懲罰量為P1，當(dāng)差值大于1且兩個(gè)對(duì)應(yīng)像素點(diǎn)的色采差異小于閾值T時(shí)，懲罰量為P2，否則懲罰量為P3。P1，P2，P3，T分別賦值10、20、40、35 。

Cp,q也能夠是圖象中相鄰像素點(diǎn)p和q之間的梯度。

最優(yōu)解d*=arg minE(d)，這里是指使E(d)獲得最小值時(shí)的d值。d是1個(gè)數(shù)組，傳統(tǒng)的是1行行求每一個(gè)點(diǎn)的視差，每行組合起來(lái)就是視差圖，并且是稠密的。

傳統(tǒng)的動(dòng)態(tài)計(jì)劃思想：
我做1個(gè)類(lèi)比，求這個(gè)最優(yōu)路徑就相當(dāng)于上面求怎樣最少步數(shù)的登上80層，每步上幾個(gè)臺(tái)階就相當(dāng)于每個(gè)點(diǎn)的視差值，每點(diǎn)的視差值得范圍是設(shè)定的視差搜索范圍，求出最優(yōu)路徑就是把每步上的臺(tái)階數(shù)計(jì)算出來(lái)了，相當(dāng)于每步的視差也就計(jì)算出來(lái)了。邊界值就設(shè)為0，可能有更好的想法，然后順次計(jì)算。

先逐一計(jì)算每一個(gè)像素在每一個(gè)視差下的匹配代價(jià)聚合值，這樣1行像素就構(gòu)成1個(gè)以行像素為橫坐標(biāo)，以視差值為縱坐標(biāo)的2維數(shù)組，然后根據(jù)唯1性束縛溫柔序性束縛使全局能量函數(shù)最小，就是求所有點(diǎn)的視差匹配代價(jià)加上平滑束縛得到的值最小。這樣既求得比較精確的視差又讓視差平滑了。
不知道這樣理解對(duì)不對(duì)。誰(shuí)理解的更好，請(qǐng)指點(diǎn)1下，菜鳥(niǎo)求指點(diǎn)

這樣的動(dòng)態(tài)計(jì)劃求出的只是在水平掃描線(xiàn)上尋徑，疏忽了掃描線(xiàn)間視差的束縛，視差圖有明顯的條紋現(xiàn)象。

3：改進(jìn)的動(dòng)態(tài)計(jì)劃：

A：基于行列雙通道的動(dòng)態(tài)計(jì)劃算法，在行掃描線(xiàn)上尋徑的同時(shí)斟酌垂直方向的視差1致束縛，對(duì)掃描行間也進(jìn)行動(dòng)態(tài)計(jì)劃的尋優(yōu)。首先用水平路徑所求的匹配視差結(jié)果作為初始視差值，再次在列方向上2次動(dòng)態(tài)尋優(yōu)，求取能量函數(shù)最小值，生成致密視差圖。

引入1種賞罰的方法，通過(guò)減小初始視差值d*所對(duì)應(yīng)匹配代價(jià)函數(shù)的值來(lái)引導(dǎo)其在列方向動(dòng)態(tài)尋優(yōu)，行將在行方向上動(dòng)態(tài)尋優(yōu)求解得到的初始視差值作為1個(gè)結(jié)果，然后對(duì)這個(gè)視差結(jié)果對(duì)應(yīng)的數(shù)據(jù)項(xiàng)給予1個(gè)更新，其它數(shù)據(jù)項(xiàng)在這個(gè)進(jìn)程中保持不變。

r是1個(gè)相對(duì)代價(jià)函數(shù)較小的數(shù)，這里取3，太大會(huì)對(duì)列尋優(yōu)沒(méi)作用，太小對(duì)行尋優(yōu)沒(méi)意思。

在列方向上進(jìn)行動(dòng)態(tài)尋優(yōu)，即為只斟酌列方向上相鄰像素點(diǎn)的視差束縛，運(yùn)算進(jìn)程與行方向1致。這樣可以改啥條紋現(xiàn)象，但時(shí)間復(fù)雜度比原來(lái)高出1倍，失去了效力優(yōu)勢(shì)。

這樣得到的結(jié)果有少許明顯的視差點(diǎn)。后處理方法：在行方向上如果1個(gè)像素點(diǎn)左右鄰域上像素點(diǎn)的視差相等，則把其左右鄰域像素視差值賦予該像素點(diǎn)；在列方向上如果1個(gè)像素點(diǎn)其上下鄰域像素點(diǎn)的視差相等，則將其上下鄰域像素的視差值賦予該像素點(diǎn)，其它情況下不變。

B：基于樹(shù)結(jié)構(gòu)的動(dòng)態(tài)計(jì)劃算法
在全局能量函數(shù)中的平滑項(xiàng) E(smooth)表示相鄰像素點(diǎn)p、q在其對(duì)應(yīng)視差值dp、dq情況下束縛項(xiàng)。

其中集合N表示像素點(diǎn)間相互束縛的鄰域范圍，這個(gè)算法是研究鄰域N的幾種樹(shù)結(jié)構(gòu)DP算法。

a就是傳統(tǒng)的行掃描線(xiàn)動(dòng)態(tài)尋優(yōu)；
b是1種類(lèi)似于樹(shù)的結(jié)構(gòu)來(lái)連接4個(gè)方向的點(diǎn)，排除邊界點(diǎn)與角點(diǎn)，鄰域N選擇上下左右4個(gè)方向，每一個(gè)點(diǎn)都與它的4個(gè)相鄰像素點(diǎn)有關(guān)，算法有效解決行掃描線(xiàn)間的垂直束縛問(wèn)題。
c、e是算法對(duì)每個(gè)像素點(diǎn)建立水平和垂直兩個(gè)方向的樹(shù)結(jié)構(gòu)，首先在行掃描方向進(jìn)行動(dòng)態(tài)尋優(yōu)計(jì)算最好匹配代價(jià)值，然后檢查最優(yōu)值是否是也是垂直方向的最優(yōu)值，用WTA得到最優(yōu)視差值。

d是將匹配中2維束縛近似轉(zhuǎn)化為多個(gè)1維束縛，采取以中心像素點(diǎn)為根節(jié)點(diǎn)的8個(gè)不同方向的平滑束縛對(duì)圖象進(jìn)行動(dòng)態(tài)計(jì)劃尋徑，缺點(diǎn)是在求解最優(yōu)視差值的進(jìn)程中各個(gè)方向都不能提供有效的紋理信息使得算法在弱紋理區(qū)域誤匹配率高。

其中b的解決方案：
首先對(duì)每列做向下的動(dòng)態(tài)計(jì)劃運(yùn)算，得到極線(xiàn)間從最左側(cè)開(kāi)始的每個(gè)像素的最優(yōu)匹配代價(jià)，將所得的優(yōu)化代價(jià)寄存在矩陣

接著對(duì)每列做向上的動(dòng)態(tài)計(jì)劃運(yùn)算，得到極線(xiàn)間從最下邊開(kāi)始的每個(gè)像素的左右匹配代價(jià)，這時(shí)候的q指向p下面的像素，把得到的結(jié)果寄存在矩陣

為了得到每一個(gè)像素的優(yōu)化代價(jià)，可以將向上和向下動(dòng)態(tài)計(jì)劃運(yùn)算代價(jià)進(jìn)行積累，在座標(biāo)（x,y）的像素記為px,y，則賦予它視差d時(shí)的最小能量函數(shù)

上式等于

最后在得到優(yōu)化矩陣后，將極線(xiàn)間的動(dòng)態(tài)計(jì)劃與極線(xiàn)上的動(dòng)態(tài)計(jì)劃結(jié)合，用已獲得的運(yùn)算結(jié)果更新視差空間代價(jià)值

其中a是用來(lái)調(diào)劑極線(xiàn)間動(dòng)態(tài)計(jì)劃對(duì)視差結(jié)果影響的參數(shù)。

然落后行極線(xiàn)上的動(dòng)態(tài)計(jì)劃，在基于上面的更新后的視差空間進(jìn)行的，最后把積累結(jié)果寄存在矩陣
最小化這個(gè)矩陣，就能夠求取每一個(gè)像素的視差了。
這類(lèi)方法復(fù)雜度過(guò)大，時(shí)間太長(zhǎng)。

4：基于控制點(diǎn)的雙向動(dòng)態(tài)計(jì)劃匹配。
利用事前肯定的正確匹配點(diǎn)作為匹配控制點(diǎn)，在動(dòng)態(tài)計(jì)劃進(jìn)程中對(duì)尋優(yōu)路徑進(jìn)行指點(diǎn)，從而煎炒條紋瑕疵，下降了復(fù)雜度。

控制點(diǎn)是那些事前知道的正確的匹配點(diǎn)。那末就能夠通過(guò)將這些正確匹配點(diǎn)設(shè)為1個(gè)較小值迫使所找尋的路徑經(jīng)過(guò)這些正確點(diǎn)。這些點(diǎn)滿(mǎn)足左右1致性束縛；避免偽最優(yōu)匹配，匹配代價(jià)小于遮擋代價(jià)，排除孤立的控制點(diǎn)，即那些沒(méi)有直接近鄰控制點(diǎn)的點(diǎn)。

b中的斑點(diǎn)就是控制點(diǎn)，有效縮小搜索空間。

具體步驟：
A：得到每一個(gè)像素的初始匹配代價(jià)C(x,y,d)，處理遮擋問(wèn)題需要計(jì)算出左右視差圖象，故左右視差圖象都需要得到。
B：控制點(diǎn)集的計(jì)算，采取以下方法計(jì)算控制點(diǎn)集。

C：初始匹配代價(jià)的聚集
首次在極線(xiàn)間分別采取下面兩式進(jìn)行自上而下和自下而上的動(dòng)態(tài)計(jì)劃計(jì)算，然落后行垂直方向的匹配代價(jià)積累

為避免視差圖在極線(xiàn)間出現(xiàn)垂直條紋，采取權(quán)重方式實(shí)現(xiàn)匹配代價(jià)的更新。

D：基于控制點(diǎn)的雙向動(dòng)態(tài)計(jì)劃
以左圖為準(zhǔn)時(shí)，從左到右搜索最優(yōu)路徑，以右圖為準(zhǔn)時(shí)，從右到左搜索最優(yōu)路徑。當(dāng)路徑到達(dá)控制點(diǎn)時(shí)，記錄下控制點(diǎn)處的視差值，用來(lái)束縛控制點(diǎn)后面像素的能量函數(shù)計(jì)算，進(jìn)而到達(dá)束縛后面像素的視差結(jié)果的作用。非控制點(diǎn)處，左右極線(xiàn)上分別進(jìn)行動(dòng)態(tài)計(jì)劃的計(jì)算，然后利用動(dòng)態(tài)計(jì)劃回溯的方法尋覓每一個(gè)像素的視差。

計(jì)算出左右視差圖象后，根據(jù)弱1致性束縛，當(dāng)左視差圖象中的某點(diǎn)視差大于右視差圖象對(duì)應(yīng)點(diǎn)的視差時(shí)采取其對(duì)應(yīng)點(diǎn)的視差取代，這樣可以有效的處理半遮擋及前景物體區(qū)域的誤匹配。
對(duì)無(wú)紋理區(qū)域的誤匹配利用同區(qū)域已匹配點(diǎn)的視差填充。

對(duì)大視差的圖象對(duì)誤差比較大。
若求取的控制點(diǎn)個(gè)數(shù)為C，那末控制點(diǎn)的采取可使傳統(tǒng)復(fù)雜度由O(MND*D)下降為O((MN-C)D*D)，取得的控制點(diǎn)越多，動(dòng)態(tài)計(jì)劃的計(jì)算復(fù)雜度越小。

在論文中看到的測(cè)試結(jié)果