## 2 Omni-Directional SGM with Reliable Cost Propagation
### Stable Disparity Propagate along MST  
Disparity refinement is an extra step to further enhance the quality of disparity image. With disparity images of a stereo pair, left-right consistency check is used to divide all pixels into _stable_ or _unstable_ pixels. Various methods have been proposed to recover the disparities of mismatched pixels, such as plane fitting [12] and weighted median filter [5]. However, these methods only take pixels in local support window into account and are not geometric adaptive. [PERSON] [15] proposed a non-local refinement method utilizing the MST of reference image. A new cost value is computed for each _stable_ pixel at all candidate disparities, while it is 0 for _unstable_ pixels. Then this cost volume is filtered by the non-local filter to propagate disparities of _stable_ pixels to _unstable_ pixels. Non-local refinement method is effective in many occasions, even when there are only few _stable_ pixels in a region. However, it is time consuming to build and filter the new cost volume, especially for high-resolution stereo pairs with large label space.  
Here we propose an effective and direct way to propagate disparities of _stable_ pixels across the reference image making use of the MST, as shown in Figure 4. Similar to performing cost aggregation along the MST, our disparity propagation procedure is also implemented by traversing the MST in two sequential passes, namely from leaf nodes to root node and then from root node to leaf nodes. In the first pass, disparities of _stable_ pixels are propagated from child nodes to their parent nodes, as shown in Figure 4a. Denote the parent node and child node of node \(v\) as \(P(v)\) and \(Ch(v)\), the weight of node \(v\) as \(w(v)\). For an _unstable_ pixel \(\mathbf{i}\), its disparity is decided by the most similar _stable_ child node, which can be expressed by  
\[D(\mathbf{i})=\begin{cases}D(\mathbf{p})&\text{if }w(\mathbf{p})==\min_{q\in Ch(i),q\in stable }(w(\mathbf{q}))\\ 0&\text{else}\end{cases} \tag{15}\]  
The cost of propagating disparity \(D(\mathbf{p})\) to \(D(\mathbf{i})\) is \(c^{\dagger}(\mathbf{i})\), and \(c^{\dagger}(\mathbf{i})=w(\mathbf{p})\). In the second pass, reliable disparities are propagated from from parent node to its child nodes, as shown in Figure 4b. For an _unstable_ pixel \(\mathbf{i}\), its disparity is updated by  
\[D(\mathbf{i})=\begin{cases}D(P(i))&\text{if }c^{\dagger}(\mathbf{i})\geq w(\mathbf{i})\\ D(i)&\text{else}\end{cases} \tag{16}\]  
From Equations (15) and (16), we can see that our method selects the disparity of the most similar _stable_ pixel and propagates it to _unstable_ pixel along the MST, and there is not much computational cost in the refinement step. Thus, our propagation strategy is more efficient than the non-local refinement approach [15]. Moreover, our method inherits the advantage of the non-local refinement approach to deal with huge _unstable_ regions. In total, our strategy achieves similar performance to [PERSON]'s method [15] but more efficient.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{**Method**} & **Computational** & \multirow{2}{*}{**Parallelization**} & **Pixels under** \\  & **Complexity** & & **Consideration** \\ \hline SGM [22] & O(MND) & Yes & Few \\ MGM [30] & O(MND) & No & All \\ Our method & O(MND) & Yes & All \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of SGM, MGM and our Omni-directional SGM.