)rises 
, and 
ich is 
' and 
857- 
chine 
chine 
MIT 
al of 
ional 
ures, 
sion, 
ence 
  
Dimitris Skarlatos 
  
IMAGE MATCHING TOWARDS MATURITY 
Dimitris P. SKARLATOS 
Department of Surveying, National Technical University, GR-15780 Athens, Greece 
dskarlat@survey.ntua.gr 
Working Group III/2 
KEY WORDS: Image Matching, Automation, Quality Control, Algorithms, Surface Reconstruction 
ABSTRACT 
This paper deals with the least squares matching algorithm, focused on stereo pairs, without the use of epipolar 
geometry. The least squares matching algorithm although widely used has still some shortcomings, which in certain 
cases keep it away from commercial production. The shortcomings are the low reliability of the "successful" matches 
and the automation/adaptation of the algorithm, which has numerous parameters. These problems will be addressed in 
this paper by introducing a new algorithm for dynamic adaptation of the template size and two new algorithms to 
enhance accuracy and reliability. Discussion and examples will be presented along with proposals for further work, 
based on the combination of the three algorithms and the use of epipolar geometry. 
1 INTRODUCTION 
Itis well known that the main algorithm for least squares matching is an ingenious concept and very well documented, 
which nowadays is included in every digital photogrammetric software. This research is part of a Ph.D. thesis, 
concerning image matching in stereo pairs, since the bulk of the commercial production is still based on pairs. The least 
squares matching (LSM), which is the basic model under analysis, has two phases, namely the initial approximations 
and the least squares (LS) solution. The former stage is basically addressed with image pyramids or interest point 
operators, while the LS are responsible for the acceptance of the initial values and the accuracy of the final fix. The 
initial approximation problem seems to have been solved for aerial photography, while it is still challenging in close 
range photogrammetry where abrupt scale differences are causing large shifts, which cannot be dealt with the 
aforementioned methods. The well-established least square matching with 6 or 8 parameters was the basic model for 
investigation. Since the sub-pixel accuracy of the method is unquestionable, the problems that still pose are the quality 
control and the reliability over the matches (correct matches that are rejected or wrong matches, which are assumed 
correct) and the automated adaptation of the algorithm parameters. Epipolar geometry hasn't been included in the model 
yet, so that the algorithm is more general and doesn't relate only to central projection, nor to a priori knowledge. 
Manual correction is still needed on automatically collected digital elevation models ( DEMs) not only to fill gaps but to 
correct the wrong matches as well, which in some cases is even more painful and time-consuming than collecting 
manually the points from the very beginning. Therefore elimination of wrong matches would save a lot of time, not to 
mention that high confidence matching could give a new thrust to the initial approximation problem. 
The automation over the LS parameters is something that one considers only when one tries to write the code. Not only 
they are too many, but often difficult to predict. All these parameters increase the complexity of the matching algorithm 
when used by unskilled users, while the experts cannot choose "average" parameters for the whole area. Therefore the 
parameters should change dynamically in the overlapping area. 
2 ADAPTIVE TEMPLATE 
Adaptive template addresses the problem of automation and better adaptation over the area. The template size should be 
"big enough for signal and small enough for minimum geometric distortions and good localization". The word "enough" 
cannot be measured in any terms and it's up to the user to interpret. It should be mentioned that some commercial 
packages offer automation on this aspect, claiming adaptation of the template size, without giving any information 
about how is this being done. Nevertheless the criteria used for the adaptation are not mentioned in published articles 
nor in manuals (none that the author is aware of) and therefore the research started from scratch. 
It has been suggested that the template size could be increased in order to grab "signal that is close but was not 
originally included" (Gruen, 1985). The method has been applied and tested. Starting from a small template (e.g. 5x5) 
the solution converges rather easily, especially when the model incorporates the two radiometric parameters (against 
the application of Wallis prior to LS, Baltsavias 1991), which in small templates dominate and manage to force 
convergence even in wrong solutions. Although there should be an upper limit of the template size there is always the 
possibility for the template to grow until it contains too much signal so that the LS provides some solution, which if the 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 845