1 June 2005 Fast disparity estimation algorithm using the property of stereo matching
Author Affiliations +
Abstract
A fast disparity estimation algorithm based on a pixel-based approach for intermediate view reconstruction (IVR) is proposed. The proposed algorithm uses the matching property of stereo imaging: in stereo images, the disparity vector of a pixel is located between those of previous and subsequent pixels. According to the experiments, the proposed algorithm can reduce the computational complexity by about 8 times and achieves competitive or slightly better peak signal-to-noise ratio (PSNR) in comparison with the pixel-based full search approach. The algorithm is proven to be effective in the implementation of the real-time disparity estimation processor for arbitrary 720×480 stereo images.
Park , Lee, and Kim: Fast disparity estimation algorithm using the property of stereo matching

Recently, 3-D imaging systems using multiview images that allow viewers to take any viewing posture by providing full parallax images have been gaining popularity. IVR provides a solution for the problem presented by large data involved in displaying natural 3-D images.1 The disparity estimation module is a key processor for IVR. A pixel-based approach is better than a block-based approach in terms of quality, but it demands a larger computational complexity because the disparities of all pixels have to be estimated.2 For that reason, a fast algorithm with good performance is required.

Fast algorithms3 4 that are based on the block-based approach are for stereoscopic image coding and can process only stereo images that are taken from parallel camera. Therefore, they aren’t suitable for IVR applications, which demand high-quality images. Fast algorithms5 are for estimating dense disparities. However, the algorithm in Ref. 5 isn’t useful in implementing a real-time disparity estimation processor for 720×480 stereo images because of insufficient reduction in the computational complexity.

In this letter, we propose a new fast algorithm that is based on the pixel-based approach and reduces computational complexity in comparison with the conventional pixel-based full search approach. The algorithm can process stereo images taken from parallel and convergent cameras in implementing a real-time disparity estimation processor.

Figure 1 shows parallel and convergent camera geometries.6 For parallel cameras, the respective locations of image points Xcl and Xcr on the left and right imaging sensor can be given by

(1)

Xcl=f(t+2X0)2Z0h, Xcr=f(t2X0)2Z0+h
where f is the lens focal length, t is the camera separation, h is the sensor axial offset.6

Fig. 1

Camera geometries: (a) parallel camera, (b) convergent camera.

019506j.1.jpg

For convergent cameras, imaged points on sensor Xcl and Xcr are

(2)

Xcl=f×tan(αφ), Xcr=f×tan(βφ)
where α=arctan(t+2X0)/2Z0 and β=arctan(t−2X0)/2Z0. 6

If X0>X1>X2 and Z0<C are assumed in the parallel and convergent camera geometries as shown in Fig. 1, the conditions of X0cl>X1cl>X2cl and X0cr>X1cr>X2cr are met. Also, if Z0>C is assumed in the convergent cameras, the conditions of X0cl<X1cl<X2cl and X0cr<X1cr<X2cr are met. We realize the important property of stereo matching from the above example: in stereo images, the disparity vector of a pixel is located between those of previous and subsequent pixels.

The search range can be predicted by using the property of the referred stereo matching. Figure 2 shows an example. First, the disparities of the 0’th and λ’th pixels are estimated by Eq. (3). Then the disparity of (λ/2)’th pixel is estimated by Eq. (4). Since the predicted search range (PSR) is usually smaller than the search range, computational complexity is reduced.

(3)

df(i)=arg minr[U{Icur(i), Iref(i+r)}],

(4)

dp(i)=arg minr¯[U{Icur(i), Iref(i+r¯)}],
where df is the disparity estimated using the full search approach, dp is the disparity estimated using the predictive search approach, Icur is the intensity of current image, Iref is the intensity of reference image, r is the search range, is PSR, and U is the cost function, such as the sum of absolute difference.

Fig. 2

Predictive search approach.

019506j.2.jpg

The procedure of the predictive search approach of the proposed algorithm, which is based on Eqs. (3) and (4), is as follows. First, x, y, and n are initialized to 0, and λ is determined. Second, the disparities of the pixels of the λ space are estimated by using the full search approach until x is smaller than the image size. Third, if x is larger than the image size, x is changed to λ/2n+1. Fourth, the disparities of the pixels of the λ/2n space are estimated by using the predictive search approach until x is smaller than the image size. Then if PSR is smaller than 0, PSR is changed with the full search range to prevent wrong disparity estimation. Fifth, if x is larger than the image size, n is increased by 1. Sixth, we repeat steps 3 to 5 until the disparity estimation of all pixels of a line is finished. Seventh, if y is smaller than the image height, y is increased by 1 and both x and n are initialized to 0. Eighth, we repeat steps 2 to 7 until y is equal to the image height.

The proposed algorithm predicts the search range but it almost doesn’t cause the propagation and the prediction errors because the disparities for the pixels of the λ space are estimated by using the full search approach, and the PSR that is smaller than 0 is changed with the full search range. As a result, the proposed algorithm is as exact as the full search approach.

Both the full search approach and the proposed algorithm have been tested for the 450×375 “Teddy,” 434×380 “Sawtooth,” and 434×383 “Venus” stereo images,7 which are taken from a parallel camera, and for the 720×480 “Puppy” stereo images recorded by the Realistic Broadcasting Research Team of the Electronics and Telecommunications Research Institute, Daejoen, Korea, which are taken from a convergent camera. The full search range for disparity estimation is ±32 pixels. The window size of 16 by 16 has been used. In view of optimal trade-off between quality and computational complexity, λ of 16 is chosen.

Figure 3 compares the proposed algorithm with the full search approach in views of the computational complexity, the PSNR, and the reconstructed images. The reduction of computational complexity is evaluated by dividing the number of searched windows in the full search approach to the number of searched windows in the proposed algorithm. The PSNR is computed by the reconstructed image and the original image.

Fig. 3

Comparison of the full search approach with the proposed algorithmml: (a) IVR image using the full search approach, (b) IVR image using the proposed algorithm, (c) PSNR vs the reduction of computational complexity.

019506j.3.jpg

In Fig. 3, the proposed algorithm achieves competitive or slightly better PSNR and reduces the computational complexity by about 8 times in comparison with the full search approach. Therefore, the proposed algorithm is useful in implementing the real-time disparity estimation processor, which achieves over 30 frames/s for arbitrary 720×480 stereo images. The number of frames can be given by (maximum frequency×reduced computational complexity)/(image size×search range)=[over (90×106)×7.4]/(720×480×64)⩾30.11 frames/s.

We have proposed a predictive search algorithm based on a pixel-based approach for fast and efficient disparity estimation. By using the matching property of stereo imaging, we reduce the computational complexity. The experimental results show that the proposed algorithm is about 8 times faster than the full search approach while achieving competitive or slightly better PSNR. The algorithm is proven to be effective in the implementation of the real-time disparity estimation processor for arbitrary 720×480 stereo images. Hence, the algorithm can be applied to stereo image applications that require real-time and high-performance solutions, such as 3-D TV.

Acknowledgments

This research was supported by University IT Research Center Project and partly by the Digital Media R&D Center, Samsung Electronic Co., Ltd.

REFERENCES

1.  A.-R. Mansouri and J. Konrad , “Bayesian winner-take-all reconstruction of intermediate views from stereoscopic images,” IEEE Trans. Image Process. 9, 1710–1722 (2000).  Google Scholar

2.  D. Scharstein and R. Szeliski , “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms,” Int. J. Comput. Vis. 47(1), 7–42 (2002).  Google Scholar

3.  W. H. Kim and S. W. Ra , “Fast disparity estimation using geometric properties and selective sample decimation for stereoscopic image coding,” IEEE Trans. Consum. Electron. 45, 203–209 (1999).  Google Scholar

4.  J. W. Bae , H. C. Park , E. S. Kim , and J. S. Yoo , “Efficient disparity estimation algorithm based on spatial correlation,” Opt. Eng. 42, 176–181 (2003).  Google Scholar

5.  O. S. Uddin , T. T. Son , and S. Mita , “Fast implementation of window-based methods for stereo correspondence,” in Applications of Digital Image Processing, Proc. SPIE 5203, 590–598 (2003).  Google Scholar

6.  A. Woods , T. Docherty , and R. Koc , “Image distortions in stereoscopic video system,” in Stereoscopic Display and Applications IV, Proc. SPIE 1915, 36–47 (1993).  Google Scholar

7. Middlebury College Stereo Vision Research Page, http://www.middlebury.edu/stereo/. Google Scholar

© (2005) Society of Photo-Optical Instrumentation Engineers (SPIE)
Jiyong Park, Jiyong Park, Wonjae Lee, Wonjae Lee, Jaeseok Kim, Jaeseok Kim, } "Fast disparity estimation algorithm using the property of stereo matching," Optical Engineering 44(6), 060501 (1 June 2005). https://doi.org/10.1117/1.1925049 . Submission:
JOURNAL ARTICLE
2 PAGES


SHARE
Back to Top