2) d,,, denotes the maximum value of disparity of the
stereo pair. For each region p; in I,, the candidates of
match in I, are searched in a space defined by a
parallelogram-shaped window W(p;) similar to which is
defined and used by Medioni and Nevatia(1985).
Stereo matching is then performed as follows. For each
region p, in the left image 7, , the region(s) lying in
searching window W(p,) in right image I, are picked
up as the candidate(s) for matching. A region with the
"closest" attributes to the p; is selected as the match. In
case more than one candidates are close enough to a
candidate, ambiguities should be resolved. Here is a
simple method for sovling such a problem : 1) sliding
each candidate along a direction parallel to the epipolar
line; 2) computing the maximum overlapping area with
in finite sliding range; 3) the candidate that leads to
largest overlapping area is thought to be the match. If
there still exist ambiguities after that process, the
geometric order is suggested to be used to resolve them.
3.2 Line-Based Stereo Matching
Line-based matching is carried out for two purposes. One
is to estimate the ground height (see the next section),
while the other is to extract 3D lines above the ground,
which can be important due for house extraction.
The line-based matching is performed by comparing the
voting arrays by Hough transform between left and right
images. The searching window for candidate selection is
similar to what was defined in section 3.1. Candidates are
then chosen in corresponding searching window. One
will see in Chapter 4 that, for the purpose of ground
height estimation, it is no need to search the unique
match for each line. That is, the presence of ambiguities
in line matching does not affect the accuracy of ground
height very much.
4. GROUND HEIGHT ESTIMATION AND
HOUSE HYPOTHESIS EXTRACTION
Last two chapters described how to segment images into
meaningful regions and lines, and how to get their match
pairs through stereo matching. Since the houses are
generally located above the ground surface, if the height
of ground surface is known, we can easily capture the
house by simply comparing the height of each region
pairs or 3D lines with the height of ground. It is then
crucial to estimate the height of ground surface in order
to extract houses from stereo images.
782
4.1 Ground Height Estimation
For the purpose of ground height estimation from the
stereo images of urban areas, it is reasonable to assume
that : if all pixels of extracted region boundaries(many of
them are houses) are removed from the edge images,
most of the left features should approximately lie on a
flat plane(with certain tolerance), i.e., ground surface.
Based on that assumption, a computational algorithm
aiming at the ground height estimation is proposed and
developed by the authors. It can be described as :
1) Finding the minimum and maximum values of
disparities d,,,, and d,,,. Let AD d,,, —d,.
2) The range of disparity AD is equally divided into k
intervals(k € Zik » 0, generally k=10). Let
AD = V Ad,
i=1,k
3) A vote is given to a interval Ad; when the
disparity of a matched lines lies in disparity interval
Ad;.
4) The disparity of the "ground surface" is thought to
be Ad, where a voting peak is reached.
A Disparity
E Ground surface lies
5 where the maximu
votes reached
4
AD Aem
1
3
6
Y X Ad. Votes
»
Fig.2. "Voting" for ground surface
estimation : a new concept.
4.2 House Hypothesis Extraction
As mentioned before, after the ground surface was
conformed, houses are able to be extracted simply by
comparing the disparity or height of each region or line
pair with that of the ground surface. These pairs which
lie above the ground are thought to be the candidate
elements constructing house hypotheses. House
hypotheses can be extracted from following three
models :
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996
a FC o Ru o: 3
peu. amp IN py my