et 
id 
se 
  
2. IMAGE PREPROCESSING 
Image preprocessing which includes feature detection and 
image segmentation, is a very important step in our 
system. In this chapter, both the region and line 
segmentation techniques will be addressed. 
2.1 Region Segmentation 
Region boundaries are derived by employing Shi and 
Shibasaki's  algorithm(1994), which consists of 
multiresolution decomposition of images based upon 
wavelet transform, edge and comer detection as well as 
Modulus Based Image segmentation(MOBIS). 
In addition, in order to resolve the correspondence 
problem in region-based stereo matching, a metric for 
measuring the similarities or dissimilarities is needed 
According to Marapane and Tridedi(1989), following six 
attributes are critical for assessing the similarities or 
dissimilarities between regions : mean gray level, area, 
perimeter, width of principal axis(PA, denoting an axis 
which is parallel to X axis as well as pass through the 
centroid of a region), height perpendicular to the PA, and 
width-to-height ratio. In our system, however, we exploit 
area-to-perimeter ratio in stead of width-to-height ratio. 
Experiments show that it can greatly reduce the 
ambiguities between irregular regions. 
2.2 Line Feature Extraction 
Line segmentation in our system, consists of following 
procedures : 
1) Wavelet transform supported edge detection, 
involving edgels(edge pixels) and their orientations. 
2) Contrast sign or zero-crossing sign computation. 
3) Line segmentation based on Hough transform(see 
Duda and Hart, 1972). 
The major property of our algorithm is that the zero- 
crossing sign is also taken into account besides the 
constraints of orientation and average contrast. That is, 
only these edgels, which have the same contrast signs of 
Zero-crossings, are able to the candidates for forming a 
line. Hence, two distinct voting arrays will be produced 
corresponding to different contrast sign. One of the major 
advantages of the use of Hough transform is that the 
disconnectivity of lines can be resolved In fact, there 
exist abundant occlusions in images from urban aerial 
scenes. 
781 
3. STEREO-MATCHING ALGORITHMS 
It has been widely recognized that no single feature based 
stereo matching(e.g. either region-based matching or line- 
based matching) can provide enough information for 3D 
object reconstruction from complex urban scenes. A 
matching system which integrates both the region and 
line matching schemes is proposed and its basic 
framework is shown in Fig.1. 
Stereo-Matching Starting from Lowest Level 
I 
Level k 
  
Fig.1. A framework of multi-level stereo 
matching algorithm. 
According to Fig.1, the stereo-matching process starts 
from the regions at lowest level of pyramid because there 
exist the least information as well as noises, and 
therefore smallest ambiguities in matching scheme. The 
matching results at a lower resolution will be used to 
guide and fasten stereo-matching at a higher resolution. 
On the other hand, the results of region-based matching 
are applied to reduce the matching ambiguities of line- 
based matching at same scale. 
Note that in order to impose an epipolar line constraint, 
it is reasonable to assume that the images used in our 
system have already been rectified, by no loss of 
generality. 
3.1 Region-Based Stereo Matching 
We would like to give some definitions at first : 
1) Let I, and I, denote, respectively, left and right 
images of a stereo pair. A, and R, denote total regions 
in left and right images respectively, while p, and qj 
denote any individual region of left and right images, 
respectively. It indicates that R, ={p) and 
R, = {4}: 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996