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.1 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),4 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.
Belief Propagation Formulation for Stereo Matching
Given the left and right images , , and the parameters , , , and , we describe the energy model for a 2-D Markov random field (MRF) as follows.4denotes the data cost of the label at the pixel in the image , and denotes the discontinuity cost between the label and of the neighbor nodes . The disparity can be estimated using the BP’s message̱update̱function and the decisioṉfunction as follows: denotes the neighbors of other than , and denotes the normalization value. At each node , the message at iteration times is updated synchronously using neighboring message and sent from node to neighbor node . After iterations, the at each node is decided by Eq. 2.
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.4 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 pixels in Fig. 1, scan lines can be separated into groups, and the lines of each group can be processed in parallel with 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 . For synchronous iteration from 1 to , for group from 0 to , for each parallel processor from 0 to , .
1 Inward processing to root, for , message̱update̱function for rightward message.
2 Outward processing to leaf, for , message̱update̱function for leftward message message̱update̱function for downward message message̱update̱function for upward message decisioṉfunction .
As shown in Fig. 2 , the processors calculate the messages in the parallel, receiving the left and right pixel data from the scan line buffers, and reading and writing with each message buffer. The processor consists of the processing elements (PE) , , , , and . Using the image data and the neighboring messages, calculates the forward message in the inward time and , , , and calculate each direction’s message and disparity in the outward time.
Architecture of Processing Element
The PE is the basis logic to calculate the new message at each node as follows., by the recursive backward and forward methods of the distance transform,4 the time complexity is for disparity levels. Due to our pipeline structure, 2-D clocks are necessary for calculating the message . In the forward initialization, , ( is as big as possible).
For clock from 0 to in the forward PE,.
For clock from 0 to in the backward PE,2 shows the PE architecture. The data cost PE calculates the data cost from the left and right image pixels. The forward PE reads , which is the sum of the messages and the data cost; outputs the forward cost , which is the minimum value between and ; and saves it to the stack. In Eq. 3, the parameters are calculated for the backward time. In our system, the minimum cost of is used for the normalized parameter .
The backward processor reads the from the stack, calculates the minimum value recursively, outputs the minimum value between and the parameter , and then subtracts it by for the normalization.
As shown in Fig. 3 , we tested our system using four grayscale images and ground truth data from the Middlebury database.1 The error rate represents the percentage of disparity error of more than 1 between output and ground truth ,is the pixel area except for the occlusion part, and is the pixel number in this area. As shown in Fig. 4 and Table 1 , our system, iterated a small number of times, shows the results superior to the local method2, 3 and BP in the Tsukuba image. Based on Fig. 4, our disparity error converges rapidly around 12 iterations.
Error rate comparison in several images.
|Methods(iteration)||Tsukuba 384×288||Venus 436×383||Map 436×380||Sawtooth 284×216||Speedperformance|
|Local case[i]||4.3%||1.5%||0.8%||1.3%||No real-time hardware|
|Local case[ii]||4.3%||2.2%||0.8%||2.1%||SIMD in Pentium 4, ,|
|BP||4.8%||8.9%||4.2%||1.4%||No real-time hardware|
|Our chip(12)||2.6%||0.8%||0.2%||0.8%||FPGA ,|
Given an image, disparity levels, and iterations, we need only 2-D forward and backward processing clocks in PE, and inward and outward processing steps at each scan line. groups are iterated times by processors in parallel at frame rates. From Fig. 5 , the total necessary number of clocks to process frames in one second is clocks . Our system’s clock was enough for real-time processing.
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 . Given as the size of message at each disparity level and processors, the message buffer memory size is as follows: leftward message: , rightward message: , upward and downward message: .
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 data bus. Two processors use the internal block RAMs on the FPGA. The overall memory resource usage is described in Fig. 5.
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.