雙目視覺——SGM中的動態規劃

• 雙目視覺——SGM中的動態規劃

雙目視覺——SGM中的動態規劃

由于工作上的需要，需要學習下雙目立體匹配鄰域中的一個經典算法SGBM，這里我的主要學習流程是先閱讀了下原paper
《Accurate and Efficient Stereo Processing by Semi-Global Matching and Mutual Information》，然后學習了李博士的SGM系列博客，寫得很好很用心啊，如果需要全面了解SGM算法的同學可以去參考下，這里我主要總結下SGM中最核心的聚合步驟中使用的動態規劃方法。

首先我們來重新描述下SGM中需要解決的問題，為啥需要動態規劃呢？
SGM中解決的問題實際上解決的問題就是一個最優化問題，既然是最優化問題，那么首先就需要構建一個損失函數，SGM中構建的損失函數如下所示：$$E(\mathrm{D})=\sum _{\mathrm{p}}\mathrm{C}\left(\mathrm{p},{\mathrm{D}}_{\mathrm{p}}\right)+\sum _{\mathrm{q}\in N_{\mathrm{p}}}{P}_{1}T\left[\left|{\mathrm{D}}_{\mathrm{p}}?{\mathrm{D}}_{\mathrm{q}}\right|=1\right]+\sum _{\mathrm{q}\in N_{\mathrm{p}}}{P}_{2}T\left[\left|{\mathrm{D}}_{\mathrm{p}}?{\mathrm{D}}_{\mathrm{q}}\right|>1\right]$$我們要求的實際上就是這樣一副視差圖：$$D=\underset{D}{\mathrm{argmin}}E(\mathrm{D})$$其中$\mathrm{C}\left(\mathrm{p},{\mathrm{D}}_{\mathrm{p}}\right)$就是點$\mathrm{p}$在視差圖${\mathrm{D}}_{\mathrm{p}}$下的損失項，這個損失項的構建多種多樣，在原論文中使用的是交叉熵，實際上用得比較多的是Census變換后兩幅圖對應像素點間的Hamming距離，或者簡單點，兩幅圖對應點之間的灰度差都可以，差別只是好優化后的效果好壞而已。

其中損失項$P_{1}T\left[\left|{\mathrm{D}}_{\mathrm{p}}?{\mathrm{D}}_{\mathrm{q}}\right|=1\right]$對相鄰像素視差變化很小的情況進行懲罰，損失項$P_{2}T\left[\left|{\mathrm{D}}_{\mathrm{p}}?{\mathrm{D}}_{\mathrm{q}}\right|>1\right]$對相鄰像素視差變化很大的情況進行懲罰，且$P_2$的懲罰力度通常大于$P_1$，我們的算法更加傾向于保證視差圖平滑變化而不是劇烈突變。

如果損失函數只有${\sum }_{\mathrm{p}}\mathrm{C}\left(\mathrm{p},{\mathrm{D}}_{\mathrm{p}}\right)$這一項的話，局部最優就是全局最優，那么你就可以用局部最優的方式去求解視差圖，例如你遍歷某個像素可能視差，損失函數最小的那個視差作為該像素的視差，那么再遍歷全圖的像素，這樣也可以得到一副視差圖，但是這樣極其容易受到噪聲的影響，李博士在博客【碼上實戰】【立體匹配系列】經典SGM：（2）代價計算中就做了這個實驗。

損失函數中正是由于多了兩個懲罰項所以變成了全局或者半全局最優，損失項中$\mathrm{q}\in N_{\mathrm{p}}$，也就是就是說，我們需要先知道周圍像素的最優視差才能知道當前像素的最優視差，為了高效地解決這個問題，SGM論文中剔除了一種路徑代價聚合的思路，這就是我這篇我這篇博客想要討論的動態規劃問題。

為了求得該像素所有視差下的匹配代價，我們首先通過該像素周圍某一條路徑上的像素的視差匹配代價一維聚合得到該路徑的聚合代價，然后將所有路徑聚合代價相加得到該像素聚合后的所有視差下的匹配代價值，如下圖所示，就是從八個方向進行代聚合得到點$p$（深藍色點）視差匹配代價的方式：

當然，我們還可以是四個，或者十六個方向，但是不管我們一共有四個、八個還是十六個方向聚合，我們在聚合某一個方向$r$時和其他方向是沒有關系的，因此我們可以從一個方向先遍歷全圖所有的像素，每個方向的聚合都是從圖像邊緣開始到圖像邊緣結束，如下所示是從上往下聚合時的情況：

這里我們先給了路徑代價聚合的一個定性的概念，那么所謂路徑代價聚合到底是一個什么過程呢? 在SGM的論文中將代價聚合定義成如下這樣一個公式：$$L_r(\mathrm{p},d)=\mathrm{C}(\mathrm{p},d)+\min ?\begin{array}{l}{L}_r(\mathrm{p}?\mathrm{r},d)\\ L_r(\mathrm{p}?\mathrm{r},d?1)+P_1\\ L_r(\mathrm{p}?\mathrm{r},d+1)+P_1\\ {\min }_i{L}_r(\mathrm{p}?\mathrm{r},i)+P_2\end{array}??\underset{i}{\min }{L}_r(\mathrm{p}?\mathrm{r},i)$$其中$L_r(\mathrm{p},d)$從像素$p$上從方向$r$聚合過來的視差為$d$時候的路徑聚合代價，$\mathrm{C}(\mathrm{p},d)$就是像素$p$在視差為$d$時的損失值，也就是前面提到的Census變換后的漢明距離或者交叉熵。這個公式很多同學一看就能發現這就是一個動態規劃過程，先求這個方向上前一個相鄰像素的聚合代價，然后在再求當前像素的聚合代碼，點$p$的相鄰像素出來進行研究，我們假定視差范圍設定為$[?2,2]$，這個動態過程就是下圖這么個過程：

像這樣每聚合完一個方向就得到一個方向的聚合代價圖，在各個方向都聚合完后對所有聚合代價圖進行求和就得到所有方向的聚合代價，然后求得該像素聚合代價最小的那個視差就是該像素的視差，就此就完成了SGM的代價聚合過程，得到了一張基本的視差圖。

因為目前主要做的不是這個方向，暫時只是了解了下這個算法核心思想，沒有Coding，也沒有做實驗，其實想把這個算法做好還有很多前前后后的處理，大家感興趣的話還是讀讀OpenCV源碼或者看看李博士的博客比較合適，這里我的總結就到這里啦～

總結

以上是生活随笔為你收集整理的双目视觉——SGM中的动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。