Comparison of some stereo vision algorithms

 

We’ve played with 4 different implementations of stereo vision algorithms. Two of these, Block Matching (BM), and Semi Global Block Matching (SGBM), we are just using implementations provided by OpenCV. The other two, simple Sum of Absolutely Differences (SAD) and Normalised Cross Correlation (NCC) we have implemented ourselves.

I did some testing earlier to help us decide which implementation we should use. The results are presented below.

 

Quality
We are not doing any quantitative testing of the algorithms (like comparing the outputs to a ground truth and calculating percentage of error pixels), just eye-balling.

The following pictures represent, looking from left to right (as you would read)are : the original image, BM, SGBM, SAD and NCC. The SAD window size is set to 9, and the number of disparity levels is set to 80 for all of the algorithms.

 

 

It should be noted that the OpenCV algorithms deal with occlusion (i.e. when pixels in an image have no corresponding pixels in the other image). Occluded areas appear in black. In the algorithms we implemented (SAD and NCC), they are not taken care of, and so errors are likely introduced.

All the algorithms are somewhat successful at giving an appropriate depth for objects in the original images. They all struggle with large homogenous textures (like the road) and which introduces some error. From these samples, SGBM appears to produce the cleanest map (notice especially how there is very little noise in the sky region for the bottom two examples, and the road is somewhat appropriately shaded). BM doesn’t do a good job, at all, of the road, as it’s all mostly shows up as black in the disparity map.

It should also be noted that we can reduce the noise level in the images by increasing the window size with the loss of some detail. For example, the following images are calculated using a window size of 21, instead of 9: (first to last: BM, SGBM, SAD, NCCR)




 

The output is obviously smoother, and suddenly BM isn’t looking so bad. The only problem still is that the road is all black, whereas theoretically it should be smoothly go from white to black. But I’m sure this is something we can deal with in the context of our car.

Performance
We ran all of the algorithms on the above three images 10 times and noted the average time it took to run the algorithms. This was done on a laptop with an AMD Phenom X4 running at 2GHz. Please note that the OpenCV functions are optimised, whereas we have done absolutely zero optimisation to the algorithms we wrote. And it clearly shows.

 

Image 1 

Road 1 

Road 2 

 

Average (s) 

FPS 

Average (s) 

FPS 

Average (s) 

FPS 

BM 

0.096 

10.428 

0.1125

8.8889

0.1137

8.7951

SGBM 

1.038 

0.963 

1.9863

0.5034

1.9881

0.5030

SAD 

34.694

0.029 

60.8113

0.0164

61.7546

0.0162

NCC 

29.937

0.033 

58.0332

0.0172

57.0302

0.0175

 

The first thing to notice from that is our algorithms are significantly slower than the OpenCV ones. The second thing to notice is that BM is significantly faster than all the other algorithms. Something to keep in mind is that we are aiming for is real-time stereo vision on a pandaboard with a processor much slower than my test rig. Bearing that in mind, and knowing the no matter how much optimisation we do in the limited time we have, our algorithms won’t perform nearly as well as the OpenCV ones. But that’s okay, because our results are not that great anyway.

After all that, I think we will go for BM as our algorithm of choice, primarily because it’s faster and the results are acceptable. There is that problem with large homogenous textures, but I’m sure we can work around it. Plus, I am confident that we can implement it at decent frame rates on the panda board with some optimisations of our own, and by making use of the DSP.

Hassan

Advertisements

One thought on “Comparison of some stereo vision algorithms

  1. Pingback: Performance and Optimisation of the Stereo Vision algorithm on the Pandaboard | Computer Science and Electronics (Year 3)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s