## 2 Omni-Directional SGM with Reliable Cost Propagation
### Cost Volume Update Scheme  
Although all pixels in the reference image are taken into account in our omni-directional SGM, it is still challenging to correctly recover disparities for pixels in large weakly textured area. Therefore, we use the output of previous pass to improve the robustness of initial  
Figure 3: Message propagation strategies in SGM variants. (**a–d**) show the ways to compute aggregated costs of root node along each tree in our method. The output of root node in each direction can be computed directly from the outputs of its children nodes (red lines). (**e**) Pixels contributing the output of root node in our method. (**d**) Pixels contributing to the output of root node in SGM along eight directions [22]. (**e**) The means of pixels contributing to the output of root node in simple complementary trees, red line indicates aggregating the output of the first pass [33]. (**d**) Dynamic programming on a minimum spanning tree [34]. matching cost. It is implemented by three steps: (1) an confidence map is built to evaluate the reliability of aggregated cost in last pass; (2) normalizing the aggregated costs to the same range as initial costs; (3) integrating normalized aggregated cost with initial matching cost based on the confidence of aggregated cost. These three steps are iteratively carried out until the last pass, enabling reliable information to propagate across the entire image. We utilize the gap between the first minimum cost and the second minimum cost to define the confidence of aggregated cost for each pixel. Denote the first minimum cost and the second minimum cost as \(L_{r}^{m1}\) and \(L_{r}^{m2}\) respectively. For pixel \(\mathbf{p}\), we have:  
\[\Gamma(\mathbf{p})=\frac{\left(L_{r}^{m2}(\mathbf{p})-L_{r}^{m1}(\mathbf{p})\right)}{L_{r} ^{m2}(\mathbf{p})+\varepsilon_{1}} \tag{11}\]  
where \(\varepsilon_{1}\) is a small number to avoid division by zero. In order to normalize aggregated cost to the same range with initial cost volume, we first estimate the maximum of initial cost volume, \(C_{max}^{I}\), the minimum and the maximum of aggregated cost for the last pass, \(C_{min}^{A}\) and \(C_{max}^{A}\), and then the normalized aggregated cost of pixel \(\mathbf{p}\) at disparity \(d\) in direction \(\mathbf{r}\) can be formulated by:  
\[L_{r}^{N}(\mathbf{p},d)=\frac{\left(L_{r}(\mathbf{p},d)-C_{min}^{A}\right)\times C_{ max}^{I}}{\left(C_{max}^{A}-C_{min}^{A}+\varepsilon_{2}\right)} \tag{12}\]  
where \(\varepsilon_{2}\) also is a small number, \(L_{r}^{N}(\mathbf{p},d)\) is the normalized cost of pixel \(\mathbf{p}\) at disparity \(d\). The cost update scheme is an adaptive combination of initial cost volume and the normalized aggregated cost in the previous pass. In order to inhibit the propagation of unreliable information, we introduce parameter \(\omega\) to decide the ratio of two kind of costs in the updated cost volume. For pixel \(\mathbf{p}\) at disparity \(d\), we have:  
\[\varphi(\mathbf{p})= \min(\omega\cdot\zeta(\Gamma(\mathbf{p}),\tau),1.0) \tag{13}\] \[\tilde{C}(\mathbf{p},d)= (1-\varphi(\mathbf{p}))C(\mathbf{p},d)+\varphi(\mathbf{p})\cdot L_{r}^{N}( \mathbf{p},d) \tag{14}\]  
where \(\omega\) decides the amount of cost propagated to initial cost volume. \(\zeta(\lambda,\tau)\) is a truncation function which is \(\lambda\) when \(\lambda\geq\tau\), and 0 otherwise. \(\tau\) is a threshold determining the cost of which pixel will be updated. Equation (13) decides the ratio of normalized aggregated cost for each pixel in updated cost volume. The \(min\) operation in Equation (13) indicates the ratio of normalized aggregated cost in the updated cost volume should be smaller than 1.0. When \(\omega\approx 0\), then \(\varphi(\mathbf{p})\) is close to 0. This means that initial cost volume nearly remains the same in the aggregation procedures along multiple directions.