## 1 Introduction
As the 1D optimization operations along multiple scan lines in each pass are independent with each other, several approaches [23; 24; 25; 26; 27; 28] take advantage of field-programmable gate-array (FPGA) or graphics card (GPU) to accelerate SGM in real-time applications. However, only pixels on scan lines intersected at current pixel in the reference image contribute to the aggregated cost of root node, degrading the performance of SGM under challenging conditions. Another shortcoming of SGM is that two adjacent pixels only share pixels on the same scan line. When matching costs on this line is unreliable, messages from other directions would produce different results for these pixels, resulting in stripe artifacts in disparity image. SGM-forest [29] treats solutions in multiple directions as independent disparity proposals and formulate the fusion procedure as a classification problem that chooses the optimal estimate from given proposals. MGM [30] takes messages from the nodes visited in previous scan line into account, aiming to make full use of information in 2D dimensions in cost aggregation along the 1D path. It overemphasizes information in neighboring pixels and inhibits an informative message from being propagated in a wide range to handle pixels in weakly textured area. Tripe SGM [31] extends SGM to three images from a triplet-stereo rig which are composed by a horizontal and vertical camera pair. SGM-Net [32] learns the penalties between neighboring pixels using Convolutional Neural Networks (CNN). In our approach, useful information is propagated in a certian direction along each tree and all pixels on the tree contribute to the aggregated cost of root node, making our method not only reduce streak artifacts of traditional SGM but also alleviate the ambiguities in homogeneous region. In this paper, we propose a new version of SGM, named omni-directional SGM (OmniSGM), which acts as performing 1D optimization along all directions. We also present an iterative cost update scheme utilizing aggregated cost in the last pass to successfully improve the robustness of initial matching cost. Specifically, our method performs SGM along tree structures in four directions, namely from left-to-right, right-to-left, top-to-bottom and bottom-to-top, as shown in the last row of Figure 1. In each pass, we recursively estimate the contribution of each pixel on the tree from leaf nodes to root node, leading to all pixels on the tree contribute to the aggregated cost of root node. Then we fuse the outputsof these four trees to obtain the final aggregated cost; thus, each pixel obtains supports from pixels in the whole image, making our method alleviate some limitations of SGM, such as streak artifacts. Compared with SGM-based methods which incorporate information from multiple scan lines, our method can be regarded as aggregating information from all pixels along all directions. In order to fully exploit reliable information in aggregated cost volume, we integrate it with initial cost volume according to the confidence of each pixel. With this successive cost volume update scheme, initial cost volume becomes more robust, and reliable information tends to propagate extensively across entire image. In the post-process step, we advance the widely used non-local refinement method [15] to efficiently propagate disparities from _stable_ pixels to _unstable_ pixels. The rest of this paper is organized as follows. In Section 2, we present an introduction of traditional semi-global matching method at first, and then elaborate our proposed omni-directional SGM, cost volume update scheme and the efficient refinement strategy. Parameter settings and extensive experiments on widely used data sets are provided in Section 3. Conclusions and remarks are given in Section 4.