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