Exploiting Spatial Variability for Disparity Estimation Maria Trujillo and Ebroul Izquierdo  of intensity and disparity” and proposed an iterative algorithm Abstract—In this correspondence a block-matching strategy that controls the size and the shape of the window using a for disparity estimation is introduced. In the proposed approach measure of uncertainty of the disparity estimation [8]. the size of the matching window is adapted according to the Different strategies have been proposed for selecting the size spatial variability of the matching areas. That is, the window size is constrained by the variations of the image intensity. A modified of the window [9], using different size of the windows [10], semivariogram function is proposed to measure the spatial [11] and enforcing the inter-window dependency [12]. variability of concerned sampling positions. Results of computer In this paper, an approach for selecting adaptively the experiments aimed at validating the performance of the proposed window size is proposed. The approach exploits intensity approach are reported. As expected, using adaptive matching variation using a relevant statistical measure. A modified window size provides better disparity estimations than those semivariogram function is introduced for measuring the obtained by using a fixed window. intensity variation or spatial variability in the surrounding Index Terms—Adaptive window size, block matching, areas. Experimental evaluations showed better estimations of motion/disparity estimation, semivariogram function. disparity vectors by using adaptive window size. I. INTRODUCTION II. EXPLOITING SPATIAL VARIABILITY FOR WINDOW SIZE ESTIMATION T HE main goal of stereo image analysis is to recover the 3D scene structure by estimating depth from corresponding points. Corresponding points in images taken from different To increase estimation accuracy the matching window size should depend on the spatial variability of the matching areas. perspectives are called disparities and can be seen as a vector For large variability of the surrounding areas a small matching field mapping one stereo image into the other. The estimation window is required. On the other hand, a large matching of this vector field is called the correspondence problem. window deliver better results for flat matching regions. Several methods have been proposed for solving the Consequently, spatial pixel dependences can play a critical correspondence task. Most of them use iterative non-linear role in solving the correspondence problem using matching techniques subject to complex constraints to control the techniques. The autocorrelation function for measuring spatial instability of the problem [1], [2], [3]. These approaches tend dependence is called semivariogram [13]. It provides a to fail in occluded and low textured areas of the image. measure of spatial dependences. It depends on the distance at Another powerful technique is based on area. It finds which two points are separated and compares all pair of points displacement vectors measuring the similarity of the at the same distance. In this work, we are interested in corresponding surrounding areas in the first and second determining the window size based on the similarity between images [4]. Usually, the surrounding areas have a rectangular the intensity value at a given point p and intensity values in shape and are called matching windows. Disparity estimation surrounding areas. A modification of the semivariogram by block-matching is a basic technique in computer vision [5], function is proposed for this application. [6]. Although a large variety of block-matching based methods Let I(p) be the intensity value at a given position p=(u,v). have been developed in the past, most of them use matching The modified semivariogram is given by windows of fixed size and shape. 1 Only a few approaches from the literature adaptively J p ( h) ¦ 2 N ( h)  p  h ( I ( p )  I ( p  h)) 2 , (1) change the shape of the matching window. A pioneering work in this direction was introduced by Levine et al. [7] in the where the N(h) is the number of points at distance h. early 1970’s. They adapted the window size according to the While the modified semivariogram (1) measures local intensity variation. Using windows, as Kanade et al. pointed variations, the variance measures global variations. Moreover, out, requires “the surface to be covered by a window to have local variations can be regarded as global when there are the same disparity”. Kanade et al. suggested that “a window abrupt discontinuities or change in intensity values. size must be selected adaptively depending on local variations Consequently, the window size can be selected according to the local variations. A suitable size for the matching window M. Trujillo is with the Systems and Computer Engineering School of the can be determined as the distance at which the modified University of Valley, Cali, Colombia (e-mail:mtrujillo@eisc.univalle.edu.co ). E. Izquierdo is with the Electronic Engineering Department of Queen Mary University of London, UK (e-mail: ebroul.izquierdo@elec.qmul.ac.uk). a) Sequence SAXO b) Sequence PIANO Fig. 1: Selected interest points plotted on the first image at the middle and their estimated corresponding points plotted on the second image at the left calculated using adaptive window size and at the right calculated using a 5x5 window size. semivariogram equals the variance: [3] Goulermas J. Y., and Liatsis P. “A Collective-Based Adaptive h Symbiotic Model for Surface Reconstruction in Area-Based Stereo,” 1 2 ¦ V 2 ( h) ( I ( p  i)  I ) 2 . (2) IEEE Trans. on Evolutionary Computation, Vol. 7, No. 5 , pp. 482-502, 2h  1 i  h 2003. [4] Zhang Z., Deriche R., Faugeras O., and Luong Q-T. “A Robust Technique for Matching Two Uncalibrated Images Through the Recovery of the Unknown Epipolar Geometry,” Artificial Intelligence, No. 78, pp. 87-119, 1995. III. EXPERIMENTAL EVALUATION [5] Cochran S. and Medioni G. “3-D Surface Description from Binocular The performance of the method presented has been verified Stereo,” IEEE Trans. on Pattern Analysis and Machine Intelligence, by processing a set of stereoscopic test sequences. All Vol. 14, pp. 981-994, 1992. [6] Scharstein D., and Szeliski R. “High-Accuracy Stereo Depth Maps experiments reported here were conducted according to the Using Structure Light,” IEEE Computer Society Conference on following procedure: Initially, interest points were extracted Computer Vision and Patter Recognition, Vol. 1, pp. 195-202, 2003. using the Canny detector. A bi-directional local maximisation [7] Levine M., O’Handley D., and Yagi G. “Computer determination of algorithm was then used to estimate correspondences for depth maps,” Computer Graphic Image Processing, Vol. 2, No. 4, pp. 131-150, 1973. selected interest points. The Pearson correlation coefficient [8] Kanade T., and Okutomi M. “A Stereo Matching with an Adaptive was used as measure of similarity between matching windows. Window: Theory and Experiment,” IEEE Trans. on Pattern Analysis The proposed adaptive window approach (ADPT) was and Machine Intelligence, Vol. 16, No. 9, pp. 920-932, 1994. [9] Fusiello A., Roberto V. and Trucco E. “Efficient Stereo with Multiple compared with a similar approach using a fixed 5x5 window Windowing,” IEEE Computer Society Conference on Computer Vision size (FIX). Results obtained using the sequences SAXO and and Pattern Recognition, pp. 858-863, 1997. PIANO are presented in Fig. 1. It can be observed that in both [10] Ohm J.-R., Izquierdo E., and Müller K. “System for Disparity-Based cases the proposed ADPT approach (left) outperforms the Multiple-View Interpolation,” IEEE Proceedings International Symposium on Circuits and Systems, Vol. 5, pp. 502-505, 1998. conventional FIX technique. [11] Izquierdo E. “Stereo Matching for Enhanced Telepresence in Three- Dimensional Videocommunications,” IEEE Transa. on Circuits and REFERENCES System for Video Technology, Vol. 7, No. 4, pp. 629-643, 1997. [12] Goulermas J. Y., Liatsis P., and Fernando T. “Depth Estimation with [1] Ohta Y., and Kanade. T. “Stereo by Intra- and Inter-Scaling Search Constrained Non-Linear Programming,” IEEE Trans. on Circuits and Using Dynamic Programming,” IEEE Trans. on Pattern Analysis and Systems for Video Technology, Vol. 5, No. 4, pp. 550-565, 2005. Machine Intelligence, Vol. 7, pp. 139-154, 1985. [13] Cressie N. Statistics for Spatial Data. John Wiley and Sons, 1993. [2] Cross A. D. J., and Hancock. E. R. “Graph Matching with a Dual-Step EM Algorithm,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 20, No. 11, pp. 1236-1253, 1998.