A Region-Based Stereo Algorithm

1. Introduction

Stereo has been a hot topic in computer vision [Xu et al., 1987]. Feature-based stereo is currently the main­ stream [Grimson, 1981a; Medioni and Nevatia, 1985; Ohta and Kanade, 1985]. The central problem is the correspon­ dence problem, or the "false targets" problem; that is, for a feature in one image there are two or more match candidates in the other [Marr & Poggio, 1979; Grimson, 1981a,b]. At the beginning, feature meant point; points are matched between the images [Grimson 1981a,b]. Later, segment-based stereo - segments rather than individual points are matched- were also intensively studied [Grim­ son 1985; Medioni and Nevatia, 1985; Ohta and Kanade, 1985] . Matching becomes easier because segment is more characteristic than point . A spontaneous extension, then, was to try region-based stereo; that is, regions are matched between images (it was first suggested in [Barrow & Pop­ plestone, 1971].) Region is even more characteristic than segment. Each region has a long vector of descriptions, such as area, perimeter, centroid, and so on. Matching based on these descriptions would have a much less proba­ bility of false targets provided that the images are not full of repetitive patterns. Anyway, it appears that everything is ready.

t The work was done at Osaka University. !>r. Gang Xu's address from this autumn is Center of Information Science, Peking University, Beijing, China

The only thing that we have overlooked above is region segmentation. In fact, it is the failure to satisfy this pre­ condition that has been the obstacle. Region segmentation in practice is subtle and unstable, and it is not guaranteed that region boundaries in left and right images correspond to same physical positions. Thus, to fully appreciate the ease of matching between regions, we have first to somehow overcome the difficulty of segmenting stereo images into re­ gions that strictly correspond to same physical positions.

Our idea is to sharpen intensity contrast between re­ gions by projecting a random pattern to the visual field. The reason for preferring a random pattern is that it makes each region statistically distinguishable from its neighbor regions, while repetitive patterns suffer the "false targets" problem [Echigo and Yachida, 1985; Sato and lnokuchi, 1987]. We share the idea of random pattern with [Nishihara, 1983], but the two approaches have fundamental dif­ ferences: we match regions that are projected from the pat­ tern; Nishihara calculates correlation values between sign images (that are obtained by filtering the original image with a Gaussian and then binarizing it,) and does not rely on features in the projection pattern. The algorithm is particularly suitable for acquiring range data of industrial parts, because a projected random pattern can also make a dense texture on the surfaces, which industrial parts usu­ ally do not have themselves. The matching algorithm is fairly general and not restricted to pattern-projected im­ ages. Any stereo images that can be segmented to satisfy the special requirement can be matched by this algorithm, although it seems that there are few such images.

2. The Random Pattern Images

The algorithm consists of four steps:

• (1)segment images into regions;
• (2)calculate area, perimeter, centroid, y-limits, and number of holes for each region;
• (3)match regions in the left and right images; and
• ( 4 )assign disparities to vertical boundary points.

Before describing the four steps in detail, we first introduce the computer-generated random pattern to be pro­ jected onto the scene. A random pattern image is obtained by filtering a computer-generated random dot image with a Gaussian of a suitable size and then thresholding it. An example is shown in Fig. 1. Compared with a random dot image, it has connected dot clusters of limited size and random shape, which are desirable properties for regionbased matching. One problem is the size of regions in the pattern. A larger region will be more statistically signif­ icant and thus makes matching easier, but is more likely to cross an occluding boundary, and makes matching more difficult. There is a trade-off. To lessen the difficulty of matching the regions that cross an occluding boundary, we regulate the size of the Gaussian filter and the threshold to restrict the size of regions as far as it does not pose any problem to the disambiguation power of the matching pro­ cess. Also the size of regions in the images can be changed by adjusting the focal length of the projector.

3. Region Segmentation and Region Descriptions

The stereo images are taken in low ambient light. We assume that the albedo of objects in a scene is uniform. Because of the sharp intensity contrast, simple threshold­ ing is sufficient to separate bright pixels from dark ones. If the ambient light cannot be kept low enough, then we take four images, two before and two after the projection. Subtracting the two images on each viewpoint precedes thresholding and makes it easier. The next step is to de­ fine and number bright regions by tracing boundary pix­ els. Only the bright regions are matched between the left and right images, while the dark pixels are regarded as a dark background. Disparities along bright boundaries and disparities along dark boundaries are identical. The 4connectedness is used to make it easy to separate different regions. Boundary pixels are distinguished from inner pix­ els. The image edges are treated as boundary pixels when needed. Being able to define each region perfectly, we can avoid the troubles of allowing one region in one image to be matched against, say, two regions in the other, and vice versa.

Once the images are segmented into regions, a vec­ tor of descriptions is calculated for each region [Ballard & Brown, 1982] . Area is simply the sum of the pixels of a region, and perimeter is the sum of the pixels of that re­ gion's boundary. Centroid is calculated by the following equations:

The y-coordinates of the highest and lowest points, referred to as yh and yl, respectively, are also recorded to indicate the region's height. In case where a hole exists inside the region (usually no,) it is also recorded.

4. Region Matching

The matching algorithm assumes, as the other stereo matchers often do, that the two cameras are so set that the epipolar lines are horizontal. But in practice it is only ap­ proximately satisfied. Thus it is desirable for the matching algorithm to be tolerant of small vertical disparities. Be­ cause of region's relatively large area, region-based match­ ing deals well with small vertical disparities, and it is one of the advantages of matching larger entities, including both regions and segments.

Matching proceeds from the No. 1 region in the left image. For a region whose centroid is at (xc, yc), the search range in the right image is a rectangle with the length a little longer than the designed maximal disparity, as shown in Fig. 2. Any regions in the search range whose centroids are in this rectangle are regarded as candidates. The true match out of the candidates must simultaneously satisfy

the following conditions:

The reason for these inequalities is that area, perimeter and height are the relatively invariant parameters of re­ gions in the two images. The differences depend mainly on the viewing angles of the two cameras (see Appendix for a disc.ussion.) The thresholds T1, T2 and T3 is to be determined in Section 6. If there are two candidates satis­ fying the inequalties, then we go to the next region to see whether one of the two candidates is this region's match. If so, then the remaining candidate is regarded as the unique match of the previous region. This has been called the "pulling effect" [Grimson, 1981a,b].

5. Disparity for Boundary Points and Dealing with Occlusiop

Once two regions are matched, disparity values are measured along the boundary. Since disparities for hori­ zontal boundary points is meaningless, they are neglected. By horizontal boundary points we mean those points whose two closest neighbors are on the same horizontal line. (Re­ call that 4-connectness is employed to trace boundaries.) The disparity between the two centroids is used as an es­ timate to align the two boundaries. lnspite of a possible small vertical disparity, we still draw completely horizon­ tal epipolarlines. The non-horizontal boundary points are matched by the orders that they appear on the horizontal epipolar lines. A histogram is drawn to show the distri­ bution of disparity values along a boundary. If the region does not cover two depths, then disparity cannot change drastically along a single boundary (this is an application of the continuity constraint.) Only the points with small deviations (say, no more than 2. pixels) from the peak value are assigned disparities, while those with large deviations are discarded as noise.

Along depth discontinuities, two regions in the left im­ age may merge into one in the right image, or reversely, one region in the left image may split into two in the right image. These regions basically cannot be matched by the above procedure, but are easily distinguished from the

matched ones. If the limits in y-direction (max(yh1, yh2), min(yll, yl2)) and the sum of the areas of the two regions in one image are nearly the same as those of the region in the other image, then the one-to-two region correspondence relations are determined instead of one-to-one relations. Again completely horizontal epipolar lines are drawn. As shown in Fig. 3, if an epipolar line intersects two regions, then the two ends are selected as the matches of the boundary points on the same epipolar line in the other image. The selection is correct as far as the disparity is not large enough to reverse the orders that any points appear in the two images. A histogram is drawn to show the distribution of disparity values along the boundary. There should be two peaks, because the region crosses two surfaces in dif­ ferent depths. Points far away from either of the two peaks are discarded as noise.

6. Implementation and Results

The algorithm has been implemented on a Sun-3 work­ station and a Tospix-2 image processor. Thresholding, numbering, attribute calculation are executed by the im­ age processor, and region matching and contour matching by the workstation. Both computer-generated random pat­ tern stereo images and pattern-projected real stereo images have been successfully matched.

An image taken before the pattern projection is shown in Fig. 4. The image shown in Fig. 1 is used as the random pattern and projected onto the scene. The stereo images are taken as the pattern is projected. The image size is 256 by 256 pixels. Their thresholded images are shown in Fig. 5. There are 291 and 300 regions in the left and right images, respectively. The image processor spends less than 2 sec. and the workstation spends about 12 sec. (region matching 2 sec. and contour matching 10 sec.). The length and width of the search range are 65 and 3 pixels, respec­ tively. There are in the left image 143 regions that each have only 1 candidate, 82 regions that each have 2 candi­ dates, 16 regions that each have 3 and more candidates, and 46 regions that have no candidate, in their respec­ tive search ranges. After applying the inequalities and the "pulling effect", the situation changes to: 216 regions have only one candidate (the match), no regions have 2 or more candidates, and 75 regions (most of them are along the left edge of the image) have no candidate, in their respective search ranges. In the equalities, the thresholds for area, perimeter and height are 0.5, 0.5 and 2 pixels, respectively. Disparity values are measured along matched boundaries. A histogram of disparity values is taken for each bound-

...... . . ... . ~- .-.--

ary, and the boundary points whose disparities are more than 2 pixels away from the peak value are discarded as noise. To the unmatched 75 regions, we further apply the method described in Section 5 to find the one-to-two corre­ spondence relations and select matching points. Then the number of unmatched regions reduces to 57.

The histograms of the differences of area, perimeter and height of the regions between the two images are shown in Fig. 8. As evident in the figure, there is a strong cor­ relation between the area difference distribution and the perimeter difference distribution. As a trial we removed perimeter from the matching algorithm, and the result showed that removing it did not influence the matching. This suggests that we use only area and height as the descriptions for each region. Height is theoretically com­ pletely invariant between the two images, and actually the difference of height is no more than 2 pixels for nearly all

.. - .._. -

regions, as can be seen from the figure.

The disp~ity map is shown in Fig. 9, with disparity ~~coded as bnghtness. The maximal and minimal dispar­ lhes are 53 and 22 pixels, respectively.

The experimental results were generally very satisfac­ tory. We consider that the processing time for matching can be further shortened. And a denser pattern image ~ould improv~ the quality of the range data. More exper­ lments are bemg carried out to make the algorithm appli­ cable under various conditions.

7. Conclusions

A region-based stereo algorithm has been proposed. The algorithm is original in that it matches large regions rather than segments or feature points. The region segmen­ tation problem is overcome by projecting a random pattern onto the visual field. Regions are matched by their areas and heights that are relatively invariant between the two images. Disparity values are then measured along bound­ ary points of matched regions. A special mechanism is developed to deal with regions that cross occluding bound­ aries. The algorithm yields fast, dense range data and is partcularly suitable for robotics tasks. It has been imple­ mented to match pattern-projected real images. Experi­ mental results show that the algorithm is efficient, reliable and tolerant of small vertical disparities. More experiments are being carried out to make the algorithm applicable un­ der various conditions.

Appendix The Variations of Region Descriptions between Images

Suppose that projection of the random pattern gener­ ates a bright spot on a surface in the scene. The surface patch can be approximated as planar if it is not very large. The variation in area between the left and right images is maximal if the planar surface patch is vertical with respect to the camera-centered coordinate system as shown in Fig. 10. The angle between the two lines of sight is a, and the angle between the normal of the planar patch and the left line of sight is (3. If the area of the patch is a, then the area of its projection in the left image is approximately a cos (3, and that in the right image is approximately a cos( a+ (3). The relative difference between them is defined as

Qualitatively speaking, e increases as a does. a reaches maximum when the disparity reaches maximum. Suppose that a is 20° at the maximal disparity. Then

When (3 is 45°, the relative difference is

A region's boundary is composed of horizontal bound­ ary points and vertical boundary points. Its perimeter is the number of the boundary points. When a surface patch is projected onto the two images, only the length of the hor­ izontal boundary points varies, while that of the vertical boundary points does not. Thus the difference in perimeter between the two images depends on how many horizontal boundary points the whole boundary includes. For a space rectangle whose perimeter is 41, the relative difference is

When a= 20° and (3 = 45°, e ~ 0.16.

The height of a region is invariant between the two images.