近來研究立體匹配，從入門開始，先學習1些基本的算法思想。
立體匹配算法中，全局匹配是1個很重要的部份，利用圖象的全局束縛信息，對局部圖象的模糊不敏感，它的計算代價很高。全局匹配算法通過構建全局能量函數，然后通過優化方法最小化全局能量函數以求得致密視差圖。

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

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

參考論文：
雙目視覺立體匹配方法研究-魏朋玉-重慶大學
基于動態計劃的立體匹配算法研究-龔文-南昌航空大學
基于動態計劃和置信傳播 的立體匹配算法的研究 -劉英杰-燕山東大學學

1：首先了解下動態計劃算法的思想：
解決爬樓梯的問題：
1個人每次只能走1層樓梯或兩層樓梯，問走到80層1共有多少種方法。
解：設DP[i]為走到第i層1共有多少種方法，那末DP[80]就是所求的目標。很明顯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
則自頂向下的解法：

自低向上的解法：

動態計劃大致就是這個思路。

2：動態計劃立體匹配基于極線束縛，通過順次尋覓每條極線上匹配點對的最小代價路徑的動態尋優方法求解全局能量最小化，得到匹配視差圖。算法步驟：
A：階段劃分：傳統的方法是只在水平方向尋覓掃描點，所以算法是在水平掃描線的視差空間切面上尋覓最優路徑的進程，以像素點的行方向為橫坐標，視差值d為縱坐標，順次將全部進程分為1,2,3,4……k個階段，每一個x坐標點對應1個階段，把立體匹配劃分成可以排序的若干個階段。

B：肯定狀態
將上述各個階段所處的匹配階段用不同的狀態表示。狀態的選擇要滿足無后向性。無后向性的意思就是當前階段的狀態只是之前階段的綜合結果，其實不對后續階段產生影響。

共有3種狀態：相互匹配M，左可見右遮擋為L（某點在右圖中沒有匹配點），右可見左遮擋為R（如果前1個點的視差比后1個視差大，就是前面點的匹配點在后1個點的匹配點的后面）。
C：狀態轉移方程：所謂狀態轉移方程就是根據前1階段的狀態肯定當前階段的狀態，根據順序性的束縛，允許的狀態轉移情勢有7種（用小寫字母表示前1階段的狀態，大寫字母表示當前階段的狀態）

0表示正確匹配，1、2表示匹配產生左圖象遮擋，4、5表示產生右圖象遮擋點，3、6表示圖象由背景進入前景，視差跳變產生其實不連續點。

D：求取最優解，并記錄該最優解的路徑
在實際編程中，按順序自左向右，或自右向左對各階段（即同1極線上的點）順次進行計算，計算類似性測度函數和平滑函數的最小值，當所有階段都計算完成后，全局能量函數最小的1條最優匹配路徑也就得出來了。

全局能量函數表示以下，
E(d)= E(data) + E(smooth)
其中 E(data) 為圖象數據束縛項，判斷匹配像素點之間的類似性， E(smooth)為相鄰點間的平滑束縛項，判斷相鄰點之間的連續性。

數據項由匹配代價取得

其中表示左像素點與視差為d的右像素點的匹配代價函數。

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

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

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

最優解d*=arg minE(d)，這里是指使E(d)獲得最小值時的d值。d是1個數組，傳統的是1行行求每一個點的視差，每行組合起來就是視差圖，并且是稠密的。

傳統的動態計劃思想：
我做1個類比，求這個最優路徑就相當于上面求怎樣最少步數的登上80層，每步上幾個臺階就相當于每個點的視差值，每點的視差值得范圍是設定的視差搜索范圍，求出最優路徑就是把每步上的臺階數計算出來了，相當于每步的視差也就計算出來了。邊界值就設為0，可能有更好的想法，然后順次計算。

先逐一計算每一個像素在每一個視差下的匹配代價聚合值，這樣1行像素就構成1個以行像素為橫坐標，以視差值為縱坐標的2維數組，然后根據唯1性束縛溫柔序性束縛使全局能量函數最小，就是求所有點的視差匹配代價加上平滑束縛得到的值最小。這樣既求得比較精確的視差又讓視差平滑了。
不知道這樣理解對不對。誰理解的更好，請指點1下，菜鳥求指點

這樣的動態計劃求出的只是在水平掃描線上尋徑，疏忽了掃描線間視差的束縛，視差圖有明顯的條紋現象。

3：改進的動態計劃：

A：基于行列雙通道的動態計劃算法，在行掃描線上尋徑的同時斟酌垂直方向的視差1致束縛，對掃描行間也進行動態計劃的尋優。首先用水平路徑所求的匹配視差結果作為初始視差值，再次在列方向上2次動態尋優，求取能量函數最小值，生成致密視差圖。

引入1種賞罰的方法，通過減小初始視差值d*所對應匹配代價函數的值來引導其在列方向動態尋優，行將在行方向上動態尋優求解得到的初始視差值作為1個結果，然后對這個視差結果對應的數據項給予1個更新，其它數據項在這個進程中保持不變。

r是1個相對代價函數較小的數，這里取3，太大會對列尋優沒作用，太小對行尋優沒意思。

在列方向上進行動態尋優，即為只斟酌列方向上相鄰像素點的視差束縛，運算進程與行方向1致。這樣可以改啥條紋現象，但時間復雜度比原來高出1倍，失去了效力優勢。

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

B：基于樹結構的動態計劃算法
在全局能量函數中的平滑項 E(smooth)表示相鄰像素點p、q在其對應視差值dp、dq情況下束縛項。

其中集合N表示像素點間相互束縛的鄰域范圍，這個算法是研究鄰域N的幾種樹結構DP算法。

a就是傳統的行掃描線動態尋優；
b是1種類似于樹的結構來連接4個方向的點，排除邊界點與角點，鄰域N選擇上下左右4個方向，每一個點都與它的4個相鄰像素點有關，算法有效解決行掃描線間的垂直束縛問題。
c、e是算法對每個像素點建立水平和垂直兩個方向的樹結構，首先在行掃描方向進行動態尋優計算最好匹配代價值，然后檢查最優值是否是也是垂直方向的最優值，用WTA得到最優視差值。

d是將匹配中2維束縛近似轉化為多個1維束縛，采取以中心像素點為根節點的8個不同方向的平滑束縛對圖象進行動態計劃尋徑，缺點是在求解最優視差值的進程中各個方向都不能提供有效的紋理信息使得算法在弱紋理區域誤匹配率高。

其中b的解決方案：
首先對每列做向下的動態計劃運算，得到極線間從最左側開始的每個像素的最優匹配代價，將所得的優化代價寄存在矩陣

接著對每列做向上的動態計劃運算，得到極線間從最下邊開始的每個像素的左右匹配代價，這時候的q指向p下面的像素，把得到的結果寄存在矩陣

為了得到每一個像素的優化代價，可以將向上和向下動態計劃運算代價進行積累，在座標（x,y）的像素記為px,y，則賦予它視差d時的最小能量函數

上式等于

最后在得到優化矩陣后，將極線間的動態計劃與極線上的動態計劃結合，用已獲得的運算結果更新視差空間代價值

其中a是用來調劑極線間動態計劃對視差結果影響的參數。

然落后行極線上的動態計劃，在基于上面的更新后的視差空間進行的，最后把積累結果寄存在矩陣
最小化這個矩陣，就能夠求取每一個像素的視差了。
這類方法復雜度過大，時間太長。

4：基于控制點的雙向動態計劃匹配。
利用事前肯定的正確匹配點作為匹配控制點，在動態計劃進程中對尋優路徑進行指點，從而煎炒條紋瑕疵，下降了復雜度。

控制點是那些事前知道的正確的匹配點。那末就能夠通過將這些正確匹配點設為1個較小值迫使所找尋的路徑經過這些正確點。這些點滿足左右1致性束縛；避免偽最優匹配，匹配代價小于遮擋代價，排除孤立的控制點，即那些沒有直接近鄰控制點的點。

b中的斑點就是控制點，有效縮小搜索空間。

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

C：初始匹配代價的聚集
首次在極線間分別采取下面兩式進行自上而下和自下而上的動態計劃計算，然落后行垂直方向的匹配代價積累

為避免視差圖在極線間出現垂直條紋，采取權重方式實現匹配代價的更新。

D：基于控制點的雙向動態計劃
以左圖為準時，從左到右搜索最優路徑，以右圖為準時，從右到左搜索最優路徑。當路徑到達控制點時，記錄下控制點處的視差值，用來束縛控制點后面像素的能量函數計算，進而到達束縛后面像素的視差結果的作用。非控制點處，左右極線上分別進行動態計劃的計算，然后利用動態計劃回溯的方法尋覓每一個像素的視差。

計算出左右視差圖象后，根據弱1致性束縛，當左視差圖象中的某點視差大于右視差圖象對應點的視差時采取其對應點的視差取代，這樣可以有效的處理半遮擋及前景物體區域的誤匹配。
對無紋理區域的誤匹配利用同區域已匹配點的視差填充。

對大視差的圖象對誤差比較大。
若求取的控制點個數為C，那末控制點的采取可使傳統復雜度由O(MND*D)下降為O((MN-C)D*D)，取得的控制點越多，動態計劃的計算復雜度越小。

在論文中看到的測試結果