Real-time FPGA implementation of the Semi-Global Matching stereo vision algorithm for a 4K/UHD video stream

Information on the 3D structure (depth) of a scene is very important in many robotic systems, including self-driving cars and unmanned aerial vehicles (UAVs), as it is used in object detection and navigation modules. The depth map can be estimated using several different approaches, active: LiDAR (Light Detection and Ranging), Time of Flight (ToF) cameras, stereo vision with structured lighting; and passive: stereo vision. Stereo vision uses two or more cameras that acquire the same scene, but from slightly different points in space. A detailed discussion of the advantages and disadvantages of different sensors can be found in the work of Jamwal, Jindal, and Singh [1].

Stereo vision, in its passive variant, is an often used solution in embedded systems due to the low price of the equipment, its small size and weight (no need for a laser light source, rotating elements or projectors). The accuracy of the results obtained with this technology strictly depends on the algorithm used to process the acquired images. The methods used can be divided into two groups: local and global [2]. In both cases, the key element is to find the same pixels in the image captured by the left (usually considered as the base) and right camera (reference). Their offset expressed in pixels is referred to as the disparity. This value can be easily converted to the distance from the sensors using the vision system parameters.

Global methods introduce appropriate discontinuity penalties in order to smooth the disparity map. Their aim is to optimise the energy function defined over the whole image. By means of global algorithms, much more reliable and accurate disparity maps are determined, but the smoothing task is NP-hard and algorithms are very computationally demanding, and for this reason they are not suitable for implementation in real-time systems.

It should be also noted that the current dominant trend is depth estimation using deep neural networks [3]. However, due to the high computational complexity, especially for high-resolution video streams, this topic remains outside the focus of our present work.

The SGM (Semi-Global Matching) algorithm was introduced by Hirshmüller in 2005 [4] and 2008 [5]. It is based on two components: (1) matching at a single pixel level with the use of mutual information and (2) approximation of a global, two-dimensional smoothness constraint (obtained by combining multiple 1D constraints). The SGM algorithm is an example of an intermediate method between local and global approaches for determining disparity maps and is a compromise between accuracy and computational complexity. However, using SGM for high-resolution images is still challenging. For example, for a resolution of $1920\times 1080$ pixels at 30 frames per second, an execution of about 2 TOPS (Tera Operations Per Second) with memory bandwidth of 39 Tb/s is required to process all pixels (2 million) [6].

In this paper we present an architecture of a stereo vision system with a modified SGM algorithm to process a 4K/Ultra HD ($3840\times 2160$ pixels @ 30 frames per second) video stream in 4ppc (pixel per clock) format and its implementation in an FPGA (Field Programmable Gate Array) device. The proposed modification solves the data dependency problem while not affecting the algorithm’s accuracy. To the authors’ knowledge, this is the only verified hardware implementation of the SGM method for 4K/Ultra HD resolution.

The reminder of this paper is organised as follows. In Section 2 we present basic information about the SGM algorithm. In Section 3 we review the previous work on SGM implementation on FPGAs. We describe the proposed method and architecture, as well as the evaluation of the algorithm and the hardware implementation in Section 4. The paper ends with conclusions and future research directions.

As mentioned in the introduction, the SGM algorithm is an intermediate approach between local and global methods for determining disparity maps. Furthermore, it is possible to implement it in an FPGA, in a pipelined vision system.

The input to the algorithm is a pair of rectified images. It consists of the following steps: calculation of the matching cost, aggregation of the cost (calculation of the smoothness constraint) and determination of the final disparity map.

In this work, the cost of matching $C(p,d)$ between a pixel $\mathbf{p}=[p_{x},p_{y}]^{T}$ from the base image $I_{b}$, and the potentially corresponding pixel (shifted by the disparity $d$ in a horizontal line) in the reference image $I_{m}$, is calculated using the Census transform and the Hamming distance measure, as shown in Figure 1.

Determining the correspondence between pixels using only the matching cost alone can lead to ambiguous and incorrect results. Therefore, an additional global condition is proposed in the SGM algorithm, which adds a “penalty” for changing the disparity value (i.e, supports the smoothness of the image), by aggregating the costs along independent paths.

Let $L_{\mathbf{r}}$ denote the path in the direction $\mathbf{r}$. The path cost $L_{\mathbf{r}}(\mathbf{p},d)$ is defined recursively as:

where: $C(p,d)$ is the matching cost, and the second part of the equation is the minimum path cost for the previous pixel $\mathbf{p}-\mathbf{r}$ on the path, taking into account the corresponding discontinuity penalty. Two penalties were applied in the algorithm, $P1$ for a 1-level change in disparity and $P2$ for a larger change.

Finally, the matching cost is given as:

The author of SGM recommend aggregation along at least 8 paths, i.e, vertically, horizontally and diagonally in both directions (cf. Figure 3), although he suggests that good results are achieved for the number 16. The disparity map $D_{b}$ corresponding to the base image $I_{b}$ is obtained by selecting for each value $\mathbf{p}$ the disparity $d$ that corresponds to the minimum cost i.e, $min_{d}S(\mathbf{p},d)$. Optional element of the algorithm is the final post-processing: median filtering and map consistency check (so called left-right consistency check).

Due to the reasonable trade-off between computational complexity and the quality of the resulting disparity map, the SGM algorithm has become very popular. It is a basic method in the popular OpenCV library and the Computer Vision Toolbox of the Matlab software. It also provides an attractive solution for hardware implementations in FPGAs.

The topic of implementing stereo correspondence using FPGAs is very extensive, and hence this review is narrowed only to selected articles describing the SGM algorithm. Interested readers are referred to the review [7].

The paper written by Gehrig, Eberli, and Meye in 2009 [8] described an SGM architecture for processing images with a resolution of $750\times 480$ pixels (effectively $340\times 200$) @ 27 fps at 64 levels of disparity. It is worth noting that this was the first implementation of the SGM method in an FPGA.

The paper of Hofmann, Korinth, and Koch from 2016 [9] also proposes a hardware implementation of the SGM algorithm. The architecture features scalability and combines coarse-grain and fine-grain parallelisation capabilities. The authors performed tests for different configurations and resolutions. For $1920\times 1080$ pixels @ 30 fps and 128 disparity levels, real-time processing was achieved at a clock of 130 MHz (VC709 board with Virtex-7 FPGA device).

In the paper of Zhao et al. from 2020 [10], the authors presented the FP-Stereo library, which uses the HLS language and allows the creation of SGM disparity calculation modules. The module has been designed in the form of an accelerator interfacing with a DMA controller, rather than directly with the video stream. For a 300 MHz clock, a resolution of $1242\times 374$ pixels and 128 disparity range, 161 fps were achieved on the ZCU 102 board with the Xilinx Zynq UltraScale+ MPSoC device.

In the latest publications by Shrivastava et al. in 2020 [11] and Lee with Kim in 2021 [6], the support for parallel pixel processing has been added to increase throughput. In this approach, the main challenge is the presence of an inherent data dependency. In the paper from 2020 [11], it is addressed by dependency relaxation, i.e, the aggregation is performed on the basis of the pixel $k$ earlier, where $k$ is the number of pixels processed simultaneously. The author points out that such a solution represents a trade-off between accuracy and throughput.

In the work from 2021 [6], on the other hand, a different approach is presented, in which operations involving the inherent data dependency are performed not on a single pixel, but on a vector of pixels. This allows the generation of disparity maps with very close accuracy to the original SGM algorithm. In both solutions, the matching costs are determined based on the Census transform. In the first publication [11], for images at a resolution of $1280\times 960$ pixels and disparity range of 64, 322 fps, and in the second [6] for a resolution of $1920\times 1080$ pixels and disparity range of 128, 103 fps were obtained.

We also propose a solution to the inherent data dependency problem. Our architecture is based on estimating the previous pixel aggregation cost on a path with minimal additional logic needed. That allows us to process images with a 4K resolution and also to obtain comparable results to the original SGM algorithm without parallelism.

The aim of our work was to implement a hardware architecture capable of processing a video stream with a resolution of $3840\times 2160$ pixels in real-time (i.e processing 30 frames per second with no pixel dropping). That stream transmitted in a 1 pixel per clock format requires a pixel clock frequency of approximately 250 MHz. Adding to this value i.e, the vertical and horizontal blanking fields, the required clock equals about 300 MHz, which is too high for the rather complicated SGM algorithm. At the bottleneck, cost aggregation calculations take more than 10 ns on our platform. So, in order to process the data in the desired resolution, it is necessary to introduce parallelisation. In this work, a 4ppc (pixel per clock) format is used, in which 4 pixels are processed in parallel. This allows the pixel clock to be lowered to approximately 75 MHz. However, the use of such format has significant implications on the implementation of the SGM algorithm, due to the inherent data dependency.

A general scheme for the proposed vision system is shown in Figure 2. The module accepts a synchronised video stream of rectified images, the base $I_{B}(p)$ and the reference $I_{M}(p)$ one. Further processing consists of several steps: determination of the matching cost $C(p,d)$ using the Census transform based matching method, calculation of the cost aggregation $L_{r}(p,d)$, summation of the aggregation costs from all directions $S(p,d)$ and disparity determination $D(p)$.

In this paper, we presented a hardware architecture for an SGM algorithm to process a 4K/Ultra HD video stream in real-time. We proposed a solution to the inherent data dependency problem. It allowed us to maintain high accuracy of the depth map estimation, while making it possible to take advantage of the 4ppc vector format. We implemented the module on a Virtex-7 FPGA platform achieving 30 frames per second for a resolution of $3840\times 2160$ pixels with 64 disparity levels.

In future work, we plan to add more aggregation paths to the algorithm. With that, it will be possible to get more accurate results, but at the cost of latency and resource usage. We also plan to implement a video stream rectification module.