StereoMatching

From OpenCV on the Cell

This page describes about the optimization of Stereo Matching.

Original algorithm of Stereo Matching has a problem for SIMDizing. It is necessary to improve the algorigthm as the following shows.

Contents 1 What is Stereo Matching? 2 Main flow 2.1 An original algorithm 2.1.1 Dissimilarity Space 2.1.2 DP Table 2.1.3 Disparity Map 2.2 For SIMD 2.3 Optimization 2.3.1 Dissimilarity Space 2.3.2 DP Table 2.3.3 Disparity Map 3 Postprocessing 3.1 Y propagate 3.2 X propagete 4 Performance 5 More Optimization 6 Reference

What is Stereo Matching?

Stereo Maching has been achieved by cvFindStereoCorrespondence function. This function makes a disparity map by using right and left images as follows.

Main flow

Stereo Matching has two flows. A disparity map is made by a main flow. Postprocessing is for more moderate and higher reliability of the disparity map.

An original algorithm

This section explains the main flow of an original algorithm. There are three main steps to make the disparity map.

Dissimilarity Space

A Dissimilarity Space is made of differences between a right image and a left image as the following figure shows. Size of the Dissimilarity Space is depth x width. Depth is specified by user.

DP Table

DP Table is constructed by using the Dissimilarity Space. The Dissimilarity Space which cost information is assign to each cell of is the DP Table. Each cell of the Dissimilarity Space refers to any of among the cell on its left, in its left or the cell that is below for the cost. The cost of each cell is computed using the one with the lowest cost among the cells referred. Each cell of the DP Table has cost and position of the cell with the lowest cost. Size of the DP Table is the same as the Dissimilarity Space.

Disparity Map

Disparity Map is the final output of cvFindStereoCorrespondence function. The Disparity Map shows the number of the line which the cell with the lowest cost in. By tracking optimal pass of the DP Table, the Disparity Map is constructed. It is possible to track optimal pass by tracing the DP Table from lower rignt according to informatioin of each cell. Size of the Disparity Map is the same as the input image.

For SIMD

When each cell of DP Table is computed, the processing of the cells which are referred should be computed. What is more, for computing the multiple data by one instruction, they should be consecutive. It is difficult to process the Dissimilarity Space of the original algorithm with SIMD.

For SIMD processing, it is necessary to improve the algorithm.

Optimization

This section explains the main flow of the funciton optimized.

Dissimilarity Space

The optimal algorithm makes the Dissimilarity Space for SIMD as the following procedure:

DP Table

By using the Dissimilarity Space made as the previous figure shows, DP Table can be constructed making use of the SIMD.

Disparity Map

It is possible to make Disparity Map with SIMD using the DP Table as shown above. It is needed to trace the DP Table from upper right for making the Disparity Map.

Postprocessing

OpenCV prepares the postprocessing for more moderate and higher reliability of the Disparity Map.

It is possible to process with SIMD without changing the postprocessing algorithm. The postprocessing includes Y propagate and X propagate.

Y propagate

A reliable cell propagates along its line. Each cell is assigned the level of reliability. It is determined by the number of contiguous cells in the column agreeing on their disparity. The following figure shows that Y propagate with SIMD.

X propagete

After the cells are propagated along their lines, the same process is repeated along the rows.

Performance

The following table shows performance of cvFindStereoCorrespondence:

Core2Duo(E6300 1.86GHz) vs Cell/B.E

Image Size		640X533	1390x1110
Core2Duo		360	1183
Cell/B.E.	PPU	846	4067
	SPUx1	79	368
	SPUx6	21	84

[ms]

The conditions for measurement were as follows:

• The number of SPE is 6.
• Parameter of Max disparity is 50.
• Alignment of step of matrix that is passed is 128.

There are test images on the following sites:

• 1390x1110 test image is "Moebius" on the site of vision.middlebury.edu.
• 640x533 test image is "Pixel-based stereo" on http://www.ces.clemson.edu/~stb/ .

StereoMatching

More Optimization

• X propagation is not processed with SIMD.

Reference

[1]Stan Birchfield and Carlo Tomasi Depth Discontinuities by Pixel-to-Pixel Stereo

International Journal of Computer Vision, 35(3): 269-293, December 1999.

[2] D. Scharstein and R. Szeliski. High-accuracy stereo depth maps using structured light.

In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2003), volume 1, pages 195-202, Madison, WI, June 2003.