procedure, Perspective distortions also can be eliminated by rearranging
pixel arrays during it.
In section 2 the matching scheme based on coarse-to-fine correlation is
outlined. The matching algorithm consists of 3 steps of the same
structure. Regular grid points are placed on a left image and their
conjugates are searched for. The principal point of the scheme is to find
occluding grid points. Actually it is difficult to find occlusions by
direct comparison of local patterns of images. We propose, instead, a
method to find them out of the already matched grid points by median-
filtering of those x-parallaxes, which is detailed in section 4. But
actually to assure the proposed method really coming into effect,
severe matching stability is needed for any other grid points than
occluding ones. Hence section 3 is devoted to preliminary but relatively
long discussions for obtaining stable matching performance, which is
realized by narrow-band-pass filtering of images before correlation. And
in section 5, a total performace of the algorithm is tested through some
experiments.
2. Outline of Matching Algorithm
The matching algorithm consists of three-steps correlation of the same
structure from correlation in a low frequency domain to in a high
frequency domain. The frequency domain is shifted by one octave as the
process goes on to another step. Stereo images to be matched are assumed
already digitized and rectified by rearranging pixel arrays along
epipolar lines to eliminate y-parallaxes. This is necessary to make
possible one-dimensional searches. The matching procedure is outlined as
follows.
(1)The areas to be plotted in a pair of stereo images are divided into
overlapping sub-areas (called patches), since the entire areas are
usually too large to be stored in core memories at a time. Matching is
done for every patch pair independently. A left patch consists of
225x225 pixels and a right patch of 225x400 pixels. A right patch is
extended in x-direction so as to give room for searching for conjugate
points.
(2)A pair of patches are passed through a kind of narrow-band-pass
filters to produce three patch pairs, each involving only specified
band-limited signals. Let the band-limited left and/or right patches be
denoted by I,, I, and I4 from the side of lower frequencies. Their
frequency bands shift by one octave to the next. The details are
discussed in section 3 in connection with the problem of stable mathing.
(3)Regular grid points are located on the left patch and their conjugates
are searched for ( see Fig.1). The grid spacing is altered for every
matching step in accordance with the frequency band used in correlation,
i.e.to 32,16 and 8 pixels for the 1st, 2nd and 3rd steps respectively. In
consequence the left patches I,, I, and I, contain 6,12 and 24 grid
points respectively. In accordance with respective grid spacings
correlation windows are set to 63,31 and 15 pixels in width in order of
the step, so as to span 2 grid points spacing in x and y directions
respectively.
(4)At the beginning of the 1st step the terrain is assumed flat and
initial values of x-parallaxes of grid points are set to the equal. In
the 2nd or 3rd step, initial values are interpolated from the coarse x-
parallax map obtained in the previous step.
(5)In order to eliminate perspective distortions, pixel arrays of the
right patch are rearranged (see Fig.2).
(6)Correlation is performed to decide conjugates.
(7)In measured x-parallaxes random errors or noises are contained, which
give a fairly bad effect on the rearrangement process (4). For removing
them, slight low-pass-filtering of x-parallaxes is very common. But in
case occlusions exist, it is not appropriate. For the terrain is
forcedly reproduced in smooth shape with this filter, though abrupt
changes in height always occur accross the occlusions in x-direction.
Instead of it we propose a method of median-filtering of x-parallaxes,
which cleans out vibrating noises, but reserves abrupt changes in x-
parallaxes. The positions of occlusions can be found simultaneously.
- 318 -
