A Parallel Matching Algorithm for Stereo Vision

A PARALLEL MATCHING ALGORITHM FOR STEREO VISION

Y. Nishimoto

Asada Research Laboratory Kobe Steel , Ltd .

53-3, Maruyama, Gomo, Nada-ku, Kobe, Japan

ABSTRACT

This paper proposes a parallel matehing algorithm for feature-based stereo vision. Features are zero-crossing (ZC) points detected with various sizes of Laplacian-Gaussian filters. In order to obtain candidate intervals of disparity , the disparity histogram is computed all over the image. The image is, then, divided into small areas and the disparity histogram in each local area is computed within the candidate intervals. The local dis­ parity histograms in all the channels are fed to the fusion evalua­ tor and the most probable disparity is detected in each local area. Once the most probable disparity is detected, disparities for all the finest ZC points are determined in the local area to obtain a high resolution disparity map. The. matehing pairs are removed from a set of ZC points. A series of processes are iterated until no more disparities are determined.

Experiments with a sample scene reveals that the algorithm has advantages in efficiency and perfortnance.

INTRODUCTION

Among various types of range finding methods, stereo vision is worthy of notice since it needs no active media. How­ ever, it is so difficult to match corresponding points in the two images that the stereo vision has. not been fully established as a computer vision system.

There have been many matehing algorithms proposed, which may be classified into feature-based method and area­ based method.

In feature-based method, Marr and Hildreth introduced the convolution operator 'V 2 G, where 'V 2 is the Laplacian opera­ tor and G stands for the two-dimensional Gaussian distribution, and adopted the zero-crossing (ZC) of the 'V 2 G-filtered image as the features to be matched (Marr and Hildreth, 1980). A problern with matehing the ZC is that ZC points may appear randomly in .the region of little intensity change. If we try to match ZCs including such random ones, the probability of false matehing becomes !arge.

Another problern is concerned about how to match corresponding points. Marr and Poggio proposed the hierarchical matehing algorithm, in which matehing process is started in the coarsest channel of ZC and followed by finer oncs (Marr and Poggio, 1979). As was successfully implemented by Grimson the algorithm is quite reasonable for a scene where the depth change smoothly (Grimson, 1981 ). However, it turns out to be inefficient in certain cases. The frrst is a case where a scene includes many objects at different positions as observed in usual room scenes. The inheritance of disparity information from a coarser channel to a finer one frequently fails, especially at the discontinuities of depth. The second is a case where the and

Y. Shirai

Automatie Control Division Electrotechnical Laboratory

1-1-4, Umezono, Sakura-mura Niihari-gun , Ibaraki, Japan

main feature consists of high spatial frequency component alone. A white wall with small scratches is one of the examples. In that case the matehing process can not start in the coarsest channel.

In order to solve problems mentioned above, we have developed and implemented a parallel matehing algorithm.

li OUTUNE OF ALGORITHM

The general block diagram of the parallel matehing algo­ rithm is shown in Figure I .

Features are the ZC points detected with various sizes of 'Y' 2 G. In order to obtain candidate intervals of disparity, the disparity histogram is computed all over the image. The image is, then, divided into small areas and the disparity histogram in each local area is computed within the candidate intervals. The local disparity histograms in all the channels are fed to the fusion evaluator and the most probable disparity is detected in each local area. Once the most probable disparity is detected, disparities for all the finest ZC points are determined in the local area to obtain a high resolution disparity map. A series of processes are iterated until no more disparities are determined.

MATCHING ALGORITHM

(

GDH : Global Disparity histogram)

LDH : Local Disparity histogram

IIl FEATURE EXTRACTION

Let the input image and 'i7 2 G-filtered image be denoted by E(x)(i, j) and B 0 (xl(i , j), where a is the standard deviation of G and x means either right (R) or left (L). B 0 (x)(i , j) is given by the following equation :

where "*" denotes the convolution operation. The filtered image B0 <x>o , j) has no dc component and can be equally divided into positive and negative regions. The boundaries between the two regions turn out to be the ZC. Here, we define the ZC as unit vector r 0 <x>(i , j) along the boundary.

A ZC point corresponding to a small cantrast is removed on the basis of the gradient value of the G-filtered image on that ZC, that is ,

where G 0 is a predetermined Ihreshold value.

IV DISPARITY HISTOGRAMMING

The calculation of disparity histogram is generally the most time-consuming process in the matehing operation. Here, the global disparity histogram (GDH) is first computed to find an approximate disparity distribution. The GDH is defined as :

where d stands for a disparity and A is the whole image plane. Since points on the physical surface constitute clusters in space, the true matches tend to fall in some intervals of disparity, while the false matches randomly scatter. The GDH consequent­ ly gives the approximate disparity distribution of objects in the scene.

Now Iet the peak value of GDH 0 (x)(d) be H. Intervals S determined in the following equation is the disparity intervals for the local dispari ty histogram (LDH) to be calculated in.

where a is a constant value and O<a< I. S may generally consist of multiple intervals corresponding to objects in the scene. In this way we can Iimit the candidate intervals of disparity and greatly improve the efficiency of the LDH process.

The LDH represents the disparity distribution of true and false matches within window W0 of M0 x M0 araund ZC point P(i , j), where M0 is determined as the average pitch of ZCs, that is, a function of a . The LDH for a fixed window on the rigl1t image is defined as:

where d E S.

V FUSION EVALUATION

Now the fusion for each window area is evaluated using LDHs of all channels. The best fusion channel is first selected as the one such that the difference between the first and second largest peaks in LDH is the largest. Let the difference of the peaks in the best channel be F<x>(d; i, j ; a). The local fusion is established if the following condition is satisfied for a certain dispari ty d *:

where Fo is a predetermined Ihreshold value. Disparity d* can be regarded as the mostprobable disparity in W 0 .

VI DETERMINATION OF DISPARITY MAP

Once the most probable disparity d* is obtained in W 0 , disparilies for all ZC points in W 0 are determined in the follow­ ing manner. Let the disparilies between a ZC point in the right image and matehing candidates in the left image be d1, dz , .. . , dn in the finest channel, and the disparity which is the nearest to d* among d1, dz, ... dn be dop·

If I dop - d* I < d0 , then the disparity for the ZC is finally determined to be dap, otherwise, the determi­ nation is postoponed,

where d0 is the predetermined value. Once the pair Q (Pm , Pn) is determined as a true match, pairs Q (Pk , Pn) (bcm) and pairs Q (Pm, Pk) (k;Cn) are regarded false matches and removed in the succeeding iterations, where Pm and Pn are a ZC point in the rigll t and left image.

The processes from GDH calculation to this process are iterated until no more disparilies are determined. The dispari­ ties are transformed to depths by means of predetermined geometrical relations and camera parameters in a straiglltforward manner.

VII EXPERIMENT

The parallel matehing algorithm was tested with the scene shown in Figure 2, with the Prime 750 in the Information Computer System of Electrotechnical Laboratory. The scene has many objects such as a plaster figure, a telephone, a book, plant, and a coffee cup in front of a shelf, white paper, and a calendar. The telephone has a glossy surface and the plant has quite a complex profile. In addition, the calendar has a periodi­ cal pattern which is, in principle, unsuitable for stereo vision.

The ZC points in the fine , middle, and coarse channel are shown in Figure 3, and the filtered ZC points in the fine channel is shown in Figure 4. The global disparity histogram from the right at the first iteration is shown in Figure 5. The disparilies finally obtained are shown in Figure 6, where the !arger disparilies (nearer to the camera) are displayed by the brighter points. There are 9424 ZC points in all in the right image, of which about 6500 ZC points have correspondences and the left are those in the occluding or uncommon regions. Most of the disparilies of 6500 ZC points were reasonably determined.

It is revealed that the ZC points whose correspondences are detected by a finer channel, mainly lie in the region near edges of objects, that is, the area of discontinuous depth, while the ZC points whose correspondences are detected by a coarser channel lie in the region of little change of depth, or in the periodical pattern on the calendar.

The cpu time is about 20 minutes except the calculation of feature extraction which could be quickly executed with special hardware.

VIII CONCLUSION

A parallel matehing algorithrn for feature-based stereo vision is proposed.

1t has the following features. Since the algorithrn uses the Features in the various resolutions evenly and complernental­ ly, it can deal with the correspondence problern according to the way how the depth changes on and between the physical surfaces of objects. For example, if an object has a surface on which the depth changes little, a coarser channel is autornatically excited and the disparilies over the wide area can be determined. at a time. lntroduction of GDH enables us to Iimit the search intervals of disparity and to reduce the amount of calculations. In addition, the algorithrn is essentially suitable for hardware due to its parallel architecture.

However, there is roorn for improvement in the details of algorithm. Especially , the criterion of evaluation of fusion and the procedure of iteration need further refinernent through experiments with various types of scenes.