## 2 Omni-Directional SGM with Reliable Cost Propagation
### Omni-Directional SGM
#### 2.2.1 Cost Aggregation on Each Tree  
Here we use \(\mathbf{r}^{k}\in\{(1,0),(-1,0),(0,1),(0,-1)\},k=1,2,3,4\) to denote the directions of four tree structures, and use \(r^{k+}\) and \(r^{k-}\) to denote the positions of child nodes in diagonal directions, as shown in Figure 2. For instance, if we perform cost aggregation from left-to-right, so we have \(\mathbf{r}^{k}=(1,0)\), \(r^{k+}=(1,-1)\) and \(r^{k-}=(1,1)\). The three child nodes of root node \(\mathbf{p}\) on this tree are \(\mathbf{p}-\mathbf{r}^{k}\), \(\mathbf{p}-\mathbf{r}^{k+}\) and \(\mathbf{p}-\mathbf{r}^{k-}\).  
When computing aggregated cost of pixel \(\mathbf{p}\) along the tree in direction \(\mathbf{r}^{k}\), all pixels on the tree can be divided into three parts, which are pixels connected to three child nodes \(\mathbf{p}-\mathbf{r}^{k}\), \(\mathbf{p}-\mathbf{r}^{k+}\) and \(\mathbf{p}-\mathbf{r}^{k-}\) respectively, as shown in Figure 3a-d. Thus we compute the contributions of pixels in these three parts independently and fuse the results of three child nodes to obtain the output of root node in this pass. The contribution of each node can be recursively computed from the outputs of its child nodes in the next layer. Denote the supports from three child nodes of root node \(\mathbf{p}\) as \(L^{\mathbf{r}^{k+}}(\mathbf{p})\), \(L^{\mathbf{r}^{k}}(\mathbf{p})\) and \(L^{\mathbf{r}^{k-}}(\mathbf{p})\). The support from child node in direction \(\mathbf{r}^{k+}\) can be computed from \(L^{\mathbf{r}^{k+}}(\mathbf{p}-\mathbf{r}^{k+})\) and \(L^{\mathbf{r}^{k}}(\mathbf{p}-\mathbf{r}^{k+})\), thus for pixel \(\mathbf{p}\) at disparity \(d\), we have  
\[L^{\mathbf{r}^{k+}}(\mathbf{p},d)=C(\mathbf{p},d)+\min_{d}((L^{\mathbf{r}^{k+}}(\mathbf{p}-\mathbf{r}^ {k+},d)+L^{\mathbf{r}^{k}}(\mathbf{p}-\mathbf{r}^{k+},d))/2+V(d,d^{{}^{\prime}})). \tag{6}\]  
Here, \(L^{\mathbf{r}^{k+}}(\mathbf{p}-\mathbf{r}^{k+},d)\) and \(L^{\mathbf{r}^{k}}(\mathbf{p}-\mathbf{r}^{k+},d)\) are the outputs of pixel \((\mathbf{p}-\mathbf{r}^{k+})\) at disparity \(d\) in directions \(\mathbf{r}^{k+}\) and \(\mathbf{r}^{k}\) respectively.  
The support from pixels in direction \(\mathbf{r}^{k}\) for root node \(\mathbf{p}\) at disparity \(d\) can be computed from the outputs of its child node in the same direction, which is  
\[L^{\mathbf{r}^{k}}(\mathbf{p},d)=C(\mathbf{p},d)+\min_{d}(L^{\mathbf{r}^{k}}(\mathbf{p}-\mathbf{r}^{k },d)+V(d,d^{{}^{\prime}})). \tag{7}\]  
Similar to Equation (6), the support from the child node in direction \(\mathbf{r}^{k-}\) can be expressed as:  
\[L^{\mathbf{r}^{k-}}(\mathbf{p},d)=C(\mathbf{p},d)+\min_{d}((L^{\mathbf{r}^{k-}}(\mathbf{p}-\mathbf{r}^ {k-},d)+L^{\mathbf{r}^{k}}(\mathbf{p}-\mathbf{r}^{k-},d))/2+V(d,d^{{}^{\prime}})) \tag{8}\]  
where \(L^{\mathbf{r}^{k-}}(\mathbf{p}-\mathbf{r}^{k-},d)\) and \(L^{\mathbf{r}}(\mathbf{p}-\mathbf{r}^{k-},d)\) are the outputs of pixel \((\mathbf{p}-\mathbf{r}^{k-})\) at disparity \(d\) in directions \(\mathbf{r}^{k-}\) and \(\mathbf{r}^{k}\) respectively.  
The aggregated cost of pixel \(\mathbf{p}\) at disparity \(d\) on the tree structure in direction \(\mathbf{r}^{k}\) is denoted by \(L^{\mathbf{r}^{k}}_{T}(\mathbf{p},d)\), which is the average of supports from its three child nodes, so we have  
\[L^{\mathbf{r}^{k}}_{T}(\mathbf{p},d)=(L^{\mathbf{r}^{k+}}(\mathbf{p},d)+L^{\mathbf{r}^{k}}(\mathbf{p}, d)+L^{\mathbf{r}^{k-}}(\mathbf{p},d))/3. \tag{9}\]  
Figure 2: Directions of information propagation on each tree structure. Red node is the root node, and orange nodes are children nodes.