Semi-Global Matching (SGM) is a robust stereo method that has proven its usefulness in various applications ranging from aerial image matching to driver assistance systems. It supports pixelwise matching for maintaining sharp object boundaries and fine structures and can be implemented efficiently on different computation hardware. Furthermore, the method is not sensitive to the choice of parameters. The structure of the matching algorithm is well suited to be processed by highly paralleling hardware e.g. FPGAs and GPUs. The drawback of SGM is the temporary memory requirement that depends on the number of pixels and the disparity range. On the one hand this results in long idle times due to the bandwidth limitations of the external memory and on the other hand the capacity bounds are quickly reached. A full HD image with a size of 1920 × 1080 pixels and a disparity range of 512 pixels requires already 1 billion elements, which is at least several GB of RAM, depending on the element size, wich are not available at standard FPGA-and GPUboards. The novel memory efficient (eSGM) method is an advancement in which the amount of temporary memory only depends on the number of pixels and not on the disparity range. This permits matching of huge images in one piece and reduces the requirements of the memory bandwidth for real-time mobile robotics. The feature comes at the cost of 50% more compute operations as compared to SGM. This overhead is compensated by the previously idle compute logic within the FPGA and the GPU and therefore results in an overall performance increase. We show that eSGM produces the same high quality disparity images as SGM and demonstrate its performance both on an aerial image pair with 142 MPixel and within a real-time mobile robotic application. We have implemented the new method on the CPU, GPU and FPGA. We conclude that eSGM is advantageous for a GPU implementation and essential for an implementation on our FPGA. The justification for SGM arises from the limitations of other global approaches for the real-world applications. Graph Cuts Zabih, 2001, Szeliski et al., 2008) is a global stereo method that translates the matching problem into a graph and seeks a partition, which effectively approximates the minimization of a global energy. The method is not only slow, but also quite memory intensive. Belief Propagation (Felzenszwalb and Huttenlocher, 2004, Szeliski et al., 2008) is another approach for minimizing a global cost function. It passes messages iteratively in a three dimensional grid structure for approximating the global minimum. The size of the temporary memory is linear to the number of pixels and the disparity range, as explained above. A Dynamic Programming stereo matching method (Birchfield and Tomasi, 1998) can be implemented with much less memory requirements, since the method optimizes the global function along each scanline separately. Unfortunately, this leads to streaking artifacts. The Semi-Global Matching (SGM) method (Hirschmüller, 2008) minimizes a global cost function only in one dimension like Dynamic Programming, but the direction is not oriented along scanlines. Instead, it is performed symmetrically from eight directions towards all pixels in the image. SGM does not suffer from streaking artifacts like Dynamic Programming and does not require iterations like Belief Propagation. The rather simple and regular integer operations of the SGM algorithm make it suitable for implementations on the GPU (Rosenberg et al., 2006 , Gibson and Marques, 2008 , Ernst and Hirschmüller, 2008 and FPGA , Banz et al., 2010 , which permits real-time performance. In practice, SGM appears rather robust and insensitive to the choice of parameters in contrast to other methods like Graph Cuts. This makes SGM suitable for real world applications like (tilewise) aerial image matching (Hirschmüller, 2008 , Gehrke et al., 2010 and automotive applications (Steingrube et al., 2009 ). The drawback of SGM is its memory consumption that depends, as for all global methods, on the number of pixels and the disparity range. This limitation may be overcome in principle with tilling the input data. While this approach is usually sufficient for CPUs it does not take advantage of the high degree of parallelism commonly found in FPGAs and GPUs. The SGM method (Hirschmüller, 2008) aims to minimize the global cost function (1) The function consists of one term that sums the matching costs C over all pixels p, according to given disparities Dp. For rectified images, the absolute difference would be calculated by This just serves as an example. In practice, more robust matching costs should be used (Hirschmüller and Scharstein, 2009 ). The second term of (1) sums small penalties P1 for all pixels, where the disparity difference to the neighbor is at most one pixel. The last term sums a higher penalty P2 for all pixels with a higher ISPRS
In order to deal with the high memory requirements of SGM, REF implemented an efficient SGM algorithm (eSGM) reducing the memory requirements at the expense of an overhead of 56% in compute time.
MEMORY EFFICIENT SEMI-GLOBAL MATCHING
ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Computer Science