An Evaluation of Uniform Region and Depth Discontinuity Region Error In Stereo Algorithms

An Evaluation of Uniform Region and Depth Discontinuity Region Error In Stereo Algorithms

1Bindu N. S, 2H. S. Sheshadri

1Vidyavardhaka college of Engineering, Dept of E&C, Mysore, India

2PES College of Engineering, Dept of E&C, Mandya, India

Abstract Stereo matching is an actively researched topic in computer vision. The goal is to recover quantitative depth information from a set of input images, based on the visual disparity between corresponding points. Many researchers have been undergone past from many decades to find an accurate disparity, but still it is not an easy task to choose an appropriate algorithm for the required real time application. To overcome from this problem we introduce an algorithm that evaluates a set of 8 known correlation based stereo algorithms. An evaluation of correlation based stereo matching algorithms results will be very useful for selecting the appropriate stereo algorithms for a given application. This work mainly focuses on the evaluation of Uniform Region and Depth Discontinuity Region Error.

KeywordsDisparity estimation, stereo matching, Uniform region, Depth Discontinuity.

1. INTRODUCTION

   Stereo matching has been one of the most active research topics in computer vision [1]. Stereo matching algorithms aim at extracting 3D structure of a particular scene by finding the correct correspondence between the images from a different view points. Finding an accurate correspondence in any of the stereo algorithms is not an easy and simple task. During the correspondence matching their occurs a number of difficulties, some of them are occluded regions, object boundaries, texture less regions. A matching cost should be computed at each and every single pixel for all the disparities under consideration. Approaches to all the stereo correspondence problems or stereo matching algorithms can be classified into two categories: area based, and feature based. In area based method, the disparity estimation at a given pixel is based on similarity measurement performed in a finite window, whereas in Feature based methods will define global cost functions to solve an optimization problem. As far as the real time applications are concerned, area based stereo matching is the most powerful tool compare to feature based stereo matching algorithm. In this work we are particularly evaluating a set of cross correlation based stereo matching algorithms suitable for real time application, which generally have low computational complexity, less storage requirement. This paper is organized as follows. Section-2 presents the state of art of stereo matching algorithms. Section-3 presents the various area based stereo matching algorithms.Section-4 presents the experimental results and finally section -5 concludes the work.

2. EVALUATION OF STATE OF ART OF STEREO MATCHING ALGORITHMS

   As correspondence algorithm is a major aspect in detection and tracking research has been done past from many decades. All the correspondence algorithms belong to two main categories as mentioned in the section-1. In this work we are mainly concentrating on work done on the correlation based methods. In the recent years area based approaches have been received a very good attention mainly because of its attribute like flexibility and also the computational cost as it is a major role in stereo correspondence. The author Scharstein, D., Szeliski, R., Zabih, R done a detailed study on various matching algorithms that have been presented [1]. Many different correlation based similarity measures and comparisons have been done in [2] but some parameters which are essential for the efficiency is missing from the list. In [3] the author Hseu, H., Bhalerao, A., Wilson, R. has presented other similarity measures and also the analysis has been done. In [4, 5] the author has analyzed some of area based algorithms amongst various algorithms and also the feature based algorithms. Here the author has considered some parameters which are going to affect the performance. The contribution to this work will make us help in choosing the more efficient algorithm by considering different aspects of parameters. In [6] the author has proposed a method that estimates the computation time of a correlation based algorithm. In [6] the author has not considered any other parameters. In [7] the author has compared 8 different correlation based stereo algorithms. In [8] the author has compared the execution time for various stereo matching algorithms. This survey comes to a conclusion by saying that only a very few and less attempts are made for comparison and also characterizing the various aspects of correlation based matching algorithms and its application.

3. STEREO MATCHING ALGORITHMS BASED ON AREA

   As we mentioned above area based similarity measure are the most powerful and also it is more efficient methods of a correlation based algorithms. This work mainly contributes and focuses on cross correlation based stereo algorithms. Various cross correlation based stereo algorithms have been proposed and among them we will discuss only a few powerful stereo algorithms as shown in the equation 1 to 8. We consider two dissimilarity measure functions called sum of squared difference (SSD) and sum of absolute difference (SAD). Also we consider the extended versions of SAD and

   SSD in zero mean and also the least square. Normalized cross- correlation (NCC) is one of the most commonly used and standard window-based matching technique. It matches pixel of interest of two windows. The normalization compensates differences in both gain and bias within the window and also it is the optimal method which compensates Gaussian noise. As NCC is a standard window based matching technique, we include this similarity measure function. In the equation below represents the coordinates of the reference image and represents the coordinates of the search image. A proper correlation window is selected.

   SAD SSD NCC LSSD

   = |1 , 2( + , + )|

   (, )

   = (1 , 2 + , + )2

   (, )

   = (, )(1 , 2 + , + )

   2 2 , . 2( + , + )

   (1)

   (2)

   (3)

   ZSAD ZSSD ZNCC

   Fig.1. Estimated disparities of different correlation algorithms

   B. Depth Discontinuity Region Error and Uniform Region

   (, ) 1

   (, ) 2

   In this section we have evaluated two parameters which are

   , , . ( + , + + , + )

   related to disparity error, depth discontinuity region error and

   =

   (, ) 1 1 2 2

   (4)

   2 ( , , )2. ( + , + + , + )2

   uniform region error. In order to carry out this evaluation, we

   (, ) 1 1

   (, ) 2 2

   have modeled the disparity map into two regions which in turn depends on the threshold value namely uniform region and

   = |1 , 1 , 2 + , + + 2 ( + , + )|

   (, )

   = (1 , 1 , 2 + , + + 2 ( + , + ))2

   (, )

   (, )

   (5)

   (6)

   discontinuity region. Initially by keeping the original ground truth disparities and estimated disparities we apply the model which we have designed. After applying we have compared these two regions which are of different disparities. Finally we get the results in terms of error between these two regions.

   = |1 , 1

   2( + , + )|

   (7)

   Fig.2 shows the results in terms of error from the disparity of

   (, )

   2( + , + )

   NCC algorithm. From the figurewe can clearly observe that

   = ( , 1 (, ) + , + )2

   (8)

   the uniform region error decreases and also we can observe

   1

   (, )

   2 ( + , + ) 2

   that the discontinuity region error increases slowly when we start increasing the size of the window from 5 to 13. X-axis

4. EXPERIMENTAL RESULTS

   A. Method Of Evaluation

   In this evaluation we consider a pair of left and right of Aloe stereo image and also its ground truth disparity which is taken from one of most oftenely used datasets called Middlebury stereo datasets [9]. Here the disparity range is

   indicates the errors and Y- axis indicates the window size. Finally we can conclude that selection of window size plays an important role in deciding the errors.

   5

   4

   considered to be from 0 to 70 pixels. The main contribution of 3

   this work is to evaluate the above said algorithms by 2

   considering various parameters; one includes disparity,

   robustness to change in illumination and also robustness to 1

   W=5

   W=7 W=9 W=11

   W=13

   change in exposure. 0

   Uniform Region

   Discontinuou s Region

   LEFT RIGHT GROUND LSAD

   TRUTH

   Fig.2. window size on Uniform region and Depth Discontinuity errors of NCC algorithm

5. ROBUSTNESS TO CHANGE IN ILLUMINATION

   In almost all the paper, most of the authors make an assumption saying that the corresponding pixels will have similar colour values. But the above said statement does not hold for the case of stereo input image that have different corresponding colour values. In this work we consider a few

   most popular algorithms to check the robustness to change in illumination as well as robustness to change in exposure. As mentioned above we have already used Aloe [7] stereo input images. In this work we will set the index value of exposure to be as 1 and also we will vary the index value of illumination to be from 1 to 3. Here we also consider a fixed window size of

   1. Fig3. shows the output disparity. From the output disparity we can clearly observe that a small change in light source seems to be a very realistic and very challenging task in stereo matching algorithms. As I mentioned in literature review compare to NCC and ZNCC the SAD, SSD are very sensitive to change in light sources But NCC and ZNCC are very insensitive to the changes in light sources. One drawback of this NCC and ZNCC is that they create a fattening effect on the object boundaries.

      LEFT RIGHT GROUND LSAD

      TRUTH

      SAD SSD NCC LSSD

      ZSAD ZSSD ZNCC

      Fig.3. Results of Stereo Algorithms with Varying Illumination

6. CONCLUSION

   As far as real time applications are considered, the correlation based stereo algorithms play an important role as it is one of the most popular and very efficient and effective algorithms. In this work we have considered 8 correlation based stereo algorithms namely SAD, SSD, NCC, NSAD, ZSSD, ZNCC, LSAD, LSSD and also analysis has been done considering various parameters. The implemented algorithms have been compared and evaluated using several error parameters namely discontinuity region error and uniform region error. We can conclude that selection of suitable window size plays an important role in deciding the final disparity. SAD based stereo algorithms are comparably less expensive compare to all other existing methods. It is observed that NCC with large window size is most efficient and it can be used in the real time applications such as object detection and object tracking systems.

7. ACKNOWLEDGEMENT

The authors would like to thank the anonymous reviewers for their constructive comments. This research work is carried out under the scheme of PESCE, Mandya, India.

REFERENCES

1. Scharstein, D., Szeliski, R., Zabih, R.: A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms. Int. Journal of Computer Vision 47, 742 (2002)

2. Aschwanden, P., Guggenbuhl, W.: Experimental Results From A Comparative Study On Correlation Type Registration Algorithms. In: Forstner, W., Ruweidel, S. (eds.) Robust Computer Vision, Wichmann, pp. 268282 (1992)

3. Hseu, H., Bhalerao, A., Wilson, R.: Image Matching Based on the Co- Occurrence Matrix. Technical Report. University of Warwick, Coventry, UK (1998)

4. Faugeras, O., et al.: Qualitative And Quantitative Comparison of Some Area and Feature Based Stereo Algorithms. In: Fostner, W., Ruweides,

   S. (eds.) Robust Computer Vision, Wichmann, pp. 126 (1992)

5. Arsenio, A., Marques, J.S.: Performance Analysis and Characterization of Matching Algorithms. In: Proc. of the 5th International Symposium on Intelligent Robotic Systems, Stockholm, Sweden (1997)

6. Sun, C.: Multi-Resolution Rectangular Sub Regioning Stereo Matching Using Fast Correlation And Dynamic Programming Techniques. CMIS Report No 98/246 (1998)

7. Bindu N.S., H.S.Sheshadri.: An Evaluation Of Correlation Based Stereo Matching Algorithms By Considering Various Parameters. Int. Conference on Recent Trends in Signal Processing, Image Processing and VLSI, Bangalore, (2014).

8. Bindu N.S., H.S.Sheshadri.: A Comparative Study and Evaluation Of Stereo Matching Costs For Radiometric Differences. Int. Conference on Recent Trends in Signal Processing, Image Processing and VLSI, Bangalore, (2014).

Middlebury Stereo Vision, http://www.vision.middlebury.edu/stereo/