## 2 Omni-Directional SGM with Reliable Cost Propagation
### Semi-Global Matching  
SGM utilizes multiple efficient 1D optimizations to approximately minimize the 2D global energy function utilizing 2D Markov Random Field. The global energy function \(E(D)\) is defined by  
\[E(D)=\sum_{\mathbf{p}}(C(\mathbf{p},d^{\mathbf{p}})+\sum_{\mathbf{q}\in N(\mathbf{p})}P_{1}T[|d^{ \mathbf{p}}-d^{\mathbf{q}}|=1]+\sum_{\mathbf{q}\in N(\mathbf{p})}P_{2}T[|d^{\mathbf{p}}-d^{\mathbf{q}}| >1]) \tag{1}\]  
where \(C(\mathbf{p},d^{\mathbf{p}})\) represents the matching cost of pixel \(\mathbf{p}\) at disparity \(d^{\mathbf{p}}\). The first term is the sum of matching costs for all pixels in reference image at disparities \(D\). The second term  
Figure 1: Message propagation strategies and the results on _Adiromdack_ stereo images of SGM, MGM and our proposed OmniSGM in four directions (from top to bottom). Black line and red line indicate the directions of how message is propagated and the cost volume update scheme respectively. Black boxes in error maps show that our method and MGM successfully avoid streak artifacts in disparity image, and red boxes demonstrate that our result is more accurate result than that of MGM and SGM.  
is the constant penalty \(P_{1}\) for pixels in slant surface in the neighborhood \(N(\mathbf{p})\) of \(\mathbf{p}\). The third term adds a larger penalty \(P_{2}\) for discontinuities in disparity image. Discontinuities often align with intensity changes, since \(P_{2}\) depends on the magnitude of image gradient, such as \(P_{2}=P_{2}^{\prime}/|I(\mathbf{p})-I(\mathbf{q})|\). \(T[.]\) represents Kronecker delta function which is 1 when the condition in the bracket is satisfied, otherwise 0.  
In order to minimize \(E(D)\), SGM computes the aggregated cost of pixel \(\mathbf{p}\) at disparity \(d\) by summing the costs of multiple 1D minimum cost paths ended at pixel \(\mathbf{p}\) at disparity \(d\). The aggregated cost \(L_{\mathbf{r}}^{{}^{\prime}}(\mathbf{p},d)\) along the path in direction \(\mathbf{r}\) for pixel \(\mathbf{p}\) at disparity \(d\) can be recursively computed by  
\[L_{\mathbf{r}}^{{}^{\prime}}(\mathbf{p},d) =C(\mathbf{p},d)+\min(L_{\mathbf{r}}^{{}^{\prime}}(\mathbf{p}-\mathbf{r},d),L_\mathbf{{r}}^{{}^{\prime}}(\mathbf{p}-\mathbf{r},d-1)+P_{1},L_{\mathbf{r}}^{{}^{\prime}}(\mathbf{p}- \mathbf{r},d+1)+P_{1},\] \[\min_{l}L_{\mathbf{r}}^{{}^{\prime}}(\mathbf{p}-\mathbf{r},l)+P_{2}) \tag{2}\]  
For simplicity, we use \(V(d,d^{{}^{\prime}})\) to denote the pair-wise first-order smoothness assumption that penalizes disparity differences between neighboring pixels in Equations (1) and (2), which is  
\[V(d,d^{{}^{\prime}})=\begin{cases}0&\text{if }d=d^{{}^{\prime}}\\ P_{1}&\text{if }|d-d^{{}^{\prime}}|=1\\ P_{2}&\text{if }|d-d^{{}^{\prime}}|>1\end{cases}\]  
Since \(L_{\mathbf{r}}^{{}^{\prime}}(\mathbf{p},d)\) can be reformulated by  
\[L_{\mathbf{r}}^{{}^{\prime}}(\mathbf{p},d)=C(\mathbf{p},d)+\min_{d}(L_{\mathbf{r}}^{{}^{\prime} }(\mathbf{p}-\mathbf{r},d)+V(d,d^{{}^{\prime}})) \tag{3}\]  
As \(L_{\mathbf{r}}^{{}^{\prime}}(\mathbf{p},d)\) could increase to a very large value due to successive accumulation along the path, thus the minimum cost of previous pixel is subtracted. As the subtracted value is a constant for all disparities at each pixel, since it does not change the actual path in disparity space. The modified aggregated cost along direction r can be expressed as  
\[L_{\mathbf{r}}(\mathbf{p},d)=C(\mathbf{p},d)+\min_{d}(L_{\mathbf{r}}(\mathbf{p}-\mathbf{r},d)+V(d,d^{{ }^{\prime}}))-\min_{k}L_{\mathbf{r}}(\mathbf{p}-\mathbf{r},k) \tag{4}\]  
The final aggregated cost is the sum of \(L_{\mathbf{r}}\) at all directions, and the disparity image is decided by the winner-take-all (WTA) strategy as  
\[D(\mathbf{p})=\arg\min_{d}\sum_{\mathbf{r}}L_{\mathbf{r}}(\mathbf{p},d) \tag{5}\]