Coarse-to-Fine Control Strategy for Matching Motion Stereo Pairs
Proceedings of the Ninth International Joint Conference on Artificial Intelligence. Perception. Pages 892-893.
© 1985 International Joint Conferences on Artificial Intelligence
Abstract
This artiele proposes a slider stereo matehing method, whieh employs a eoarse-to-fine eontrol strategy to overeome the false targets problem. At first , a stereo pair is taken at a short baseline, and a mateh is assigned to it . The resulting disparit y map is then used to restriet seareh range and to prediet oeelusion for effieiently and reli ably matehing the sueeeeding stereo pair taken at a langer baseline. The syste m iterates the sliding and matehing to obtain an enough disparity range.
- Marr, D. and Poggio, T. "Cooperative Computa- tion of Stereo Disparity" Science, N.Y.194, 1976' pp.283-287
- Marr, D. and Poggio, T. "A Computational Theory of Human Stereo Vision" Proc. R. Soc . Lond. • B204 , 1979, pp.301-328.
- Grimson, W. E. L. "Fr om Images To Surfaces: A Computational Study of the Human Early Vision System", Cambridge, MA., MIT Press, 1981
- Moravec, H. "The Stanford Cart and the CMU Rover" Proc. of IEEE, Vo1.7l,No.7,1983 pp.872- 884
- Nevatia, R. "Depth Measurement by Motion ereo" Comput. Graphics & Image Proc., o1.6, 1976. (a) ()
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. INTRODUCTION
It has been pointed out by the early researehes[l,2] on Stereopsis that at the heart of the matehing problern lies the problern of false targets, whose severity is enhaneed by both a wide disparity range and a fine resolution. To obtain both, whieh are neeessary for aeeuraey, Marr and Poggio [ 2] proposed a zer o- erossing algor i thm (implemented by Grimson [3]) based on the eoarse to- fine strategy. The stereo images were filtered at different seales, yielding a set of primitive image pairs of different resolutions. A mateh of a wide disparity range but of a eoarse resolution was ass i gned first , and this result was then used to reduee seareh spaee, for mat ehing the finer dctailed primitive pairs. While the algorithm was sueeessfully applied to a variety of images, it resulted in ineorreet matehes along oeeluding zero erossings, beeause the eontinuity eonstraint was used along those depth-diseontinuous eontours.
In this paper , we present a new stereo matehing method, whieh is based upon a different eoarse-to fine strategy. A eamera is slid along a straight line to takestereo pairs at different baselines, resulting in a set of stereo pairs of different disparity ranges . Images are eonvolved with a small - sized Laplaeian-Gaussian operator , whieh assures us of a fine resolution, and the zero erossings in the filtered images are extraeted along horizontal sean lines. Then the matehing proeess proeeeds in a eoarse-to-fine iterative manner. The pair taken at the shortest baseline is matehed first; the matehing is easy, at the expense of redueed disparity range. This result , a narrow range disparity map, ean then be used to reduee seareh spaee for matehing the langer baseline pair, again making the proeess easier . We iterate the sliding , imaging and matehing several times to obtain a wide disparity range. One important advantage of our method over the eonventional ones Motion stereo methods have been studied for a lang time by Moravec and Nevatia. The idea, however, was used to make reliable depth measurement(4] and to save computing time [ 5], while the dispari ty information available from the already matched pairs was not utilized in matehing the other pairs.
2. COARSE-TO-FINE RULE
Both our algorithm and Marr and Poggio's are based on the coarse-to- fine control strategy, aiming at obtaining both a wide disparity range and a fine resolution at last. The two algorithms, however, take different routes to reach the goal. Fig.l helps to understand the difference. While the depth accuracy in Marr and Poggio's algorithm is improved by making the resolution finer over a wide disparity range, that in ours is improved by widening the disparity range in a fine resolution.
It is important to note that, the only physieal constraint we use here is that features should not disappear, nor features newly appear, through the sliding, because the scene and the illumination condition are supposed not to ehange during this period. In general, it is satisfied exeept the eases where some feature points are occluded, as the camera is slid. These feaLure points, however, are assigned with disparities before occluded and the probability of occlusion is predicted from the disparity information obtained already. As a consequence, not only can we avoid the incorrect matches due to occlusion, but it is also possible to obtain more disparity information about the feature points occluded finally than the other stereo matchers.

3. SLIDING AND HATCHING
A camera is slid from left to right along a straight line, taking a sequence of images at predetermined intervals. The sliding is kept parallel to the horizontal axis of the camera coordinate system, so that the epipolar lines , on which correspondences can be found, are completely horizontal. Let the first image be the only left image and the remainders right ones. Note that such an arrangement is purely for simplifying our description, and the following matehing algorithm can be easily modified for other arrangements.
Images are convolved with the Laplacian-Gaussian filter, and zero-crossings in the filtered images are found. For a fine resolution, we have chosen 4 as the filter's central region width W. Besides the loca tion, an at tri bute of the zero-crossings, the cantrast sign, is also recorded, and used as a criterion for matching.
The first stereo pair, due to its reduced disparity range, can be easily matched by simply searching a small region without encountering false targets. Below, we discuss how to use the obtained disparity information for matehing the second stereo pair. Suppose that the baseline of the second stereo pair is k times that of the first one. Then for a zero crossing in the left image at position (x,y), whose disparity obtained by matcing the first stereo pair is D(x,y), its correspondence's position in the right image is estimated by
(x-kD(x,y),y).
Taking into account the error <1D in the disparity obtained already, the position is revised as
(x-kD(x,y)+k<lD,y).
Therefore, we can constrain the search for the cor responding zero-crossing in the right image of the second stereo pair to the region
<lD ~Dmaxl.
The size of search region should be selected so that the.probability for double targets in one search region is not high. A conservative value, 7 pixels, is selected for the width of the search region. Then the warst case probability of double targets is 0.5 (estimated from the result by Grimson [ 3]), and true ma tches can found by utilizin3 "ryulling effect" [2].
Now let us consider how lang we can slide the camera in each step of the successive imaging. Given .1Dmax· We can determine k, the ratio of the baselines, as 3/ <1Dmax· <1 D resul ts from many factors, such as errors in locating zero- crossings in quantized images and the physical inaccuracy in sliding the camera. We have not estimated all these factors yet. The experimental results, however, indicate that <1Dmax does not exceed 1.5 pixels in most cases; 2 is currently selected for k. Clearly, we need less sliding times for obtaining an enough disparity range than conventional motion stereo methods [4,5], which take pictures at equal intervals.
4. OCCLUSION PREDICTION
In this section, we consider how the occlusions in the successive stereo pair is predicted from the disparity map obtained already. Suppose that there are two zero-crossings P 1 and P 2 at (x 1 ,y) and (x 2 ,y) on a scan line in the left image. If they are predicted as changing to the opposite order in the right image, i.e.,
The prediction is not always true, because of the error in estimating the zero-crossing positions. Therefore, the following method is used to avoid mismatches. If the estimated distance between the occluding and occluded zero-crossings is above a threshold, then the occlusion is certain and we search for only P 1 · If below, we search for both. In the latter case, if there is only one matchable zero-crossing, then it is considered as corresponding to P 2 , the one closer to the camera.
5. EXPERIMENTS AND DISCUSSION
Wehave tested the described method for a blocks world and an indoor scene. Fig.2 (a), (b) and (c) illustrate the first, second and fifth images of an image sequence of the blocksworld, respectively. Fig.2 (d) shows the zero-crossing contours of Fig.2 (c). The contours are displayed as bright if the cantrast sign is positive, and as dark if negative. Fig.2 (e) shows the differences between the estimated zero-crossing positions and the real ones. It can be seen that they agree with each other quite well. The dark points indicate the estimated locations of zero-crossings and those predicted as occluded are displayed with !arger spots. The bright points are the actual positions in the image. Fig.2 (f) shows the top view obtained by matehing Fig.2 (a) to Fig.2(e). Fig.3(a) shows an input image of the indoor scene, and Fig.3(b) shows the disparity map, in which the disparity is displayed as proportional to the brightness.
The experiments indicate that most zero-crossings appear in the search pools, provided that the camera sliding is accurate enough. The disparities obtained along occluding zero-crossing contours also demonstrate that there are few mismatches resulting from occlusion.
One difficulty in matehing the stereo pair is that the cantrast sign along occluding zero-crossing contours sometimes changes as the camera is slid. Therefore, the cantrast sign, which played a signi ficant role in the implementation of Marr and Poggio's algorithm by Grimson, results in mismatches in this method. We consider that our method can be improved to accomodate such cases by predicting the changes in the background's intensity .
At present, the camera motion is a long a straight line. We can , however, modify the method so as to move the camera more freely in space, and give the s ystem intelligence to plan motion by observing the coarse disparity map obtained already.
@inproceedings{ijcai1985p178,
title = {Coarse-to-Fine Control Strategy for Matching Motion Stereo Pairs},
author = {Xu, Gang and Tsuji, Saburo and Asada, Minoru},
booktitle = {Proceedings of the Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-85}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Aravind Joshi},
pages = {892--893},
year = {1985},
note = {Perception},
url = {https://ijcai.org/proceedings/1985/178},
}
TY - CPAPER TI - Coarse-to-Fine Control Strategy for Matching Motion Stereo Pairs AU - Xu, Gang AU - Tsuji, Saburo AU - Asada, Minoru T2 - Proceedings of the Ninth International Joint Conference on Artificial Intelligence, IJCAI-85 PB - International Joint Conferences on Artificial Intelligence PY - 1985 SP - 892 EP - 893 UR - https://ijcai.org/proceedings/1985/178 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: