1.

Introduction

Stereo matching algorithms find corresponding points in a pair of images to locate 3-D positions. They can be classified into either local or global matching approaches.¹ Local approaches, like correlation and dynamic programming methods, deal only with subimages. These approaches have the advantage of real-time speed,^{2, 3} but tend to produce high errors. In contrast, the global approaches, like graph cuts and belief propagations (BPs),⁴ deal with full images. These approaches have the advantage of low errors, but tend to execute huge computational loads. In real-time applications, like robot vision, the stereo matching system should be compact and fast. In this context, we present a very large scale integration (VLSI) architecture for stereo matching with BP.

2.

Belief Propagation Formulation for Stereo Matching

Given the left and right images $g^r$ , $g^l$ , and the parameters $c_d$ , $c_v$ , $K_d$ , and $K_v$ , we describe the energy model for a 2-D Markov random field (MRF) as follows.⁴

3.

Proposed Architecture of Stereo Matching

Generally, BP can be separated into two methods, mainly according to the update style. The first method updates all the nodes synchronously on the 2-D MRF.⁴ The second method updates all the nodes sequentially; first in the inward direction from the leaf to the root and next in the reverse direction.^{5, 6} The sequential method needs to update only once at each node and obtains the final results. Therefore, the nodes can be propagated fast with the small number of operations. In Ref. 5, the authors reported that the sequential update based on spanning trees in MRF can achieve fast convergence. We applied the tree structure to each scan line, as shown in Figs. 1 and 1 . The tree messages are updated using messages from the neighboring scan lines that have been determined in the previous iteration times. For the image with $M\times N$ pixels in Fig. 1, $N$ scan lines can be separated into $G$ groups, and the $H$ lines of each group $g∊[0,G-1]$ can be processed in parallel with $H$ processors. This observation is shown in our VLSI parallel sequences as follows. A node located in a pixel is denoted by a 2-D vector $\mathbf{p}={\left[p_0{p}_1\right]}^T$ . For synchronous iteration $k$ from 1 to $K$ , for group $g$ from 0 to $G-1(=N∕H-1)$ , for each parallel processor $h$ from 0 to $\mathbf{H}-1$ , $(\mathbf{p}={[gH+h{p}_1]}^T)$ .

Fig. 1

Update sequence at $k$ iteration times on 2-D MRF: (a) inward processing, (b) outward processing, and (c) parallel processing within group.

As shown in Fig. 2 , the $H$ processors calculate the messages in the parallel, receiving the left and right pixel data from the $H$ scan line buffers, and reading and writing with each message buffer. The processor consists of the processing elements (PE) ${\mathit{PE}}^f$ , ${\mathit{PE}}^b$ , ${\mathit{PE}}^u$ , ${\mathit{PE}}^d$ , and ${\mathit{PE}}^o$ . Using the image data and the neighboring messages, ${\mathit{PE}}^f$ calculates the forward message in the inward time and ${\mathit{PE}}^b$ , ${\mathit{PE}}^u$ , ${\mathit{PE}}^d$ , and ${\mathit{PE}}^o$ calculate each direction’s message and disparity $\widehat{d}$ in the outward time.

Fig. 2

Parallel and pipeline architecture: (a) processor array and (b) PE.

4.

Architecture of Processing Element

The PE is the basis logic to calculate the new message at each node as follows.

For clock $t$ from 0 to $D-1$ in the forward PE,

For clock $t$ from 0 to $D-1$ in the backward PE,

The backward processor reads the $m_f(D-1-t)$ from the stack, calculates the minimum value $D_3\left(t\right)$ recursively, outputs the minimum value between $D_3\left(t\right)$ and the parameter $m_f(-1)$ , and then subtracts it by $\alpha$ for the normalization.

5.

Experimental Results

As shown in Fig. 3 , we tested our system using four grayscale images and ground truth data from the Middlebury database.¹ The error rate represents the percentage of disparity error of more than 1 between output $d(x,y)$ and ground truth $d_{\text{TRUE}}(x,y)$ ,

Fig. 3

Left images: (a) Tsukuba, (b) Venus, (c) Sawtooth, and (d) Map.

Fig. 4

Comparison of outputs in Tsukuba: (a) ground truth, (b) convergence rate, (c) our system at 12 iterations, (d) BP at 12 iterations, (e) local method,² and (f) local method.³

Table 1

Error rate comparison in several images.

Given an $M\times N$ image, $D$ disparity levels, and $T$ iterations, we need only 2-D forward and backward processing clocks in PE, and $2M$ inward and outward processing steps at each scan line. $G(=N∕H)$ groups are iterated $T$ times by $H$ processors in parallel at $F$ frame rates. From Fig. 5 , the total necessary number of clocks to process $F$ frames in one second is $49M$ clocks $[=2\mathrm{D}\left(2M\right)(N∕H)TF=(16\times 2)\times (256\times 2)\times (240∕24)\times 12\times 25]$ . Our system’s $65\text{-}\mathrm{MHz}$ clock was enough for real-time processing.

Fig. 5

Chip specifications: (a) overall system and (b) resource usage and output performance.

As shown in Fig. 2, the overall memory is spent for the scan line buffer and message buffer. For real-time processing, our processors should be allowed to access a pair of images in the scan line buffer, while the buffer loads new images from the cameras continuously. Hence, the size of buffer for four images is allocated on the field programmable gate array (FPGA), which means $2\mathrm{Mbits}[=4\times (256\times 240\times 8)]$ . Given $C(=4)\text{bits}$ as the size of message at each disparity level and $H(=24)$ processors, the message buffer memory size is as follows:   leftward message: $1.5\mathrm{kbits}=\mathrm{HCD}$ , rightward message: $0.4\mathrm{Mbits}=\mathrm{HCDM}$ ,  upward and downward message: $8\mathrm{Mbits}=2HCDMG$ .

In outward processing, the newly calculated leftward message is only used for the next pixel processing. One scan line size of rightward messages in inward time should be stored for outward processing. Since the upward and downward messages are updated synchronously for the entire image, we need to store all the pixel messages in the image. Due to this big memory size, 22 processors access the external memory through an $8\times 22\text{-}\text{bit}$ data bus. Two processors use the internal block RAMs on the FPGA. The overall memory resource usage is described in Fig. 5.

6.

Conclusions

Although BP produces good error performances in the area of image processing, the VLSI architecture has not been fully studied yet. In this context, we propose a parallel VLSI architecture for stereo matching. The test system has only 16 disparity levels, which might not be satisfactory for 3-D recognition tasks. However, for applications, like real-time Z-keying and target-background separation, where low disparity error at the object boundary is important, the proposed chip can be effectively used.