which belong to area-based matching, can reach subpixel
accuracies, its pull-in range, unfortunately, is even smaller,
that is to say, very precise approximations have to be
provided.
It is evident that the approximation problem is critical for
area-based matching. In recent years results of feature
matching are often used as approximations for area-based
matching. Although the complexity of matching increases in
this way, the results are still not always satisfactory,
especially in areas without any features. On the other hand,
global approaches to perform matching in object space have
been studied intensively to utilize additional information to
strengthen matching results. Some global approaches like
MATCH-T (Ackermann and Hahn, 1991), no longer need
precise approximations, at the price of a very high
complexity.
The RG-DW scheme described in this paper is one kind
of area-based matching based on some simple and common
concepts and methods. The strategies employed in the
scheme, however, are unique, and aim at both performing
good matching and keeping the procedure relatively simple.
2.1 RG — Recursive Grid
Usually, the relative geometric distortion between two
images, which form a stereo pair, is not too great. Suppose,
using a simple geometric transformation, e.g., bilinear or
affine transformation, to approximately describe this
distortion. Once the conjugate image coordinates of four
points at the four corners of the overlapping area of a stereo
pair are known, the transformation parameters between the
two images and rough positions of any corresponding
points, can be easily calculated. Although using these
coordinates as approximations may be too rough to be
accepted by general area-based matching, the situation is
certainly changed if pyramid images are used. The Recursive
Grid is just based on this idea.
As shown in figures 1 and figure 2, at first we use the
approximate conjugate coordinates of the four corner points
to calculate the geometric transformation parameters between
two images of the level 3 of pyramid images and to derive an
irregular grid on the right image, which is correspondent to
the regular grid on the left image (figure 2). Using the rough
conjugate grid as approximations, the accurate
corresponding points can be obtained by using the Dynamic
Window method, which will be explained below, and then
transmitted through scale space to the next pyramid level.
Finally a sparse grid with rather high reliability is available in
the original images. By recursively using the sparse
conjugate grid points as anchor points to calculate new
geometric transformation parameters for each conjugate
square, a dense set of corresponding grid points can be
obtained. It is clear that the smaller the interval between two
anchor points, the better the approximations of points in
between will be. If the interval between anchors is small
enough, the final dense conjugate points can be directly
acquired on the original images instead of through pyramid
images by using the Dynamic Window method. This case, in
which we proceed, from anchor points directly to a final
dense grid, is called two-stage RG-DW; if we move from
anchor points to the next level of anchor points and then to
densification, it is called three-stage RG-DW. Two or three
stages can be chosen depending on the images and the
applications as well as user preference. Someday soon
parallel processing with the RG-DW scheme will allow
simultaneous calculation of all required corresponding as
anchor points, that will be called one-stage, of course.
Obviously, the determination of each anchor point is
done by searching from the top level of pyramid images
down to the original image, and on each level of the pyramid
a set of windows with different sizes is used, so that a
reliability index, based on the searching and matching status
can be labeled to each anchor point. The higher the index,
the better the reliability. For a few anchor points with index
values less than a threshold, a measure such as automatic
shifting of the point position, interpolation, or an interactive
814
editing mode can be easily used to improve the reliability of
the matching results. In the interactive editing mode the
matching results are overlaid on top of the original images
with different colors representing the matching reliability
indices, so that the user can delete or correct wrong matches.
Level 3
Level 2
Level 1
Level 0
Figure.1 The pyramid image for pyramid matching
Level 2
Level 0
Level 3
Fig.2 The concept of the recursive grid method
2.0 DW — Dynamic Window
Different window sizes often result in different matching
results. The question is, if there is an optimal window size
for matching ? If so, is the optimal window size applicable to
different images ? This question is hard to answer, actually.
In general, the reliability of matching increases with
enlarging the window size. In the case of using a larger
window size, however, the matching accuracy decreases, or
even lost matching may happen, if there is a major geometric
distortion between the two images to be matched. In
addition, computing expense rises quickly with enlarging the
window size. On the other hand, with a smaller window size
the computing effort is smaller, but wrong matches maybe
occur frequently, if there is not enough feature information
or there exist repeating patterns in the area to be matched.
In order to take advantage of both large and small
windows and to increase the reliability of matching, a
dynamic windows is adopted in the RG-DW scheme. For
each pair of points to be matched a set of at least three
windows from small to large are used for each pyramid
image level. Only if matching results of different windows
are similar, is the matching considered successful. Otherwise
the window size is enlarged until the correct match is found
or the window size is reaches a certain threshold. In most
cases, the matching quality of all windows, such as a
cumulation of all correlation coefficients as an index,
indicates the reliability of the matching quite well. The
indices range from 1 to 12 in our case. If we overlay
matching points over the original images and represent the
reliability indices with different colors, the matching quality
can be visualized and corrected.
It should be pointed out, that during matching the
searching range on the right image is changed for each
AO L9 C) Co OY MM AY beet
t Hi