ormations into
regarded as a
Digital Photo-
ial of FV. At
| radiometrical
account. The
semantic infor-
object surface
arth surface is
. The methods
1 surface from
inclusive the
ns should be
paper, can be
uitable models
more effective
years.
on Wavelets.
and Applied
Oberfláchen-
entierung von
)r.-Ing. thesis,
nany.
das Facetten-
f Technology,
sion, Reihe C,
'eorithmen für
University of
Geodätische
ermany.
rdnung durch
'aummodellen.
-101.
Matching by
. SPIE(-The
ing) 804, 325-
eh -1992-
nstruction by
edel, St.(eds):
ag, Karlsruhe,
igh resolution
m large scale
- An extended
' III/2, Vienna
MULTI-POINT LEAST SQUARES MATCHING WITH ARRAY RELAXATION
UNDER VARIABLE WEIGHT MODELS
Xiaoliang Wu
Space Centre for Satellite Navigation, Queensland University of Technology
GPO Box 2434 QLD 4001, Australia
E-mail: wux@redash.qut.edu.au
KEY WORDS: Three-dimensional Reconstruction, Global Image Matching, Array Algebra, Relaxation, Lest Squares Matching
ABSTRACT
In this paper, An algorithm called Array Relaxation Multi-point Least Squares Matching (ARMLSM) will be discussed in detail,
and the new formulation of Array Relaxation under the variable constraint weight model is presented. The presented new
ARMLSM can take into account both cases of the first and second order derivative constraint weight models, and the new
ARMLSM can be applied in the both of image space and object space. A hierarchical strategy is used in the ARMLSM in
order to derive the matching approximations. The hierarchical ARMLSM approach limits the searching range for matching
candidates in each image pyramid level and therefore can also improve computing efficiency.
Three test image pairs are used. The matching results of the conventional MLSM, the ARMLSM under the optimal uniform
constraint weight model and the ARMLSM under the variable constraint weight model are compared and analysed. Three
matching efficiencies are found to be near 6, 82 and 81 node points per second on SGI 4D/25, respectively, and the matching
accuracy comparison of the Loess plateau aerial images shows 0.79, 0.75 and 0.37 pixels can be reached by the three MLSM
algorithms, respectively. The ARMLSM under the variable constraint weight model has great potential for practical digital
photogrammetric systems.
1 INTRODUCTION
During the last few decades a vast variety of image matching
methods have been developed, most of them belong to sin-
gle point or features/edge matching algorithms, Reconstruct-
ing three-dimensional (3-D) surfaces is an ill-posed problem
from the mathematical point of view, recently more and more
Global Image Matching (GIM) techniques have been used in
3-D reconstruction applications such as regularization the-
ory [8, 18], stochastic optimal approach using microcanoni-
cal annealing [2, 3], neural network stereo matching [21] etc..
Various kinds of assumptions and constraints were introduced
in these GIM methods in order to get more reliable and ac-
ceptable solutions than the single point or single feature/edge
matching.
Multi-point Least Squares Matching (MLSM) is one of
GIM techniques which was developed from the single point
Least Squares Matching (LSM) by many researchers: Rosen-
holm [16, 17], Rauhala [10, 13] and Li [6, 7] etc.. Compared
to other GIM techniques, MLSM is widely used in the pho-
togrammetric community, MLSM uses simultaneous compu-
tation of parallaxes in the grid which are connected with bi-
linear finite elements describing the parallaxes differences. It
is assumed that the object model is a continuous surface, the
additional fictitious observations for continuity constraints on
parallaxes are used in MLSM. MLSM is not only applied in
the image space but also in object space [4, 5, 16, 20].
GIM (including MLSM) can provide much more reliable and
accurate matching results than the single point matching
method, for example, MLSM based on image space can reach
0.1 ~ 0.5 pixel accuracy [15] and MLSM based on object
space can reach 0.15 ~ 0.2 pixel [16], 0.25 pixel [19]. How-
ever, no matter what kind of GIM method is used, the low
computational efficiency is the common shortcoming. How
to improve the computational efficiency is the problem faced
in all GIM methods, Li [6] uses MLSM in a multiresolution,
multigrid approach, the average CPU time improvement was
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
60% (corresponding to 6 points per second based on our test).
It is desirable for MLSM that the constraint weights should be
small enough if the object surface and image intensity changes
are severe such as for the ridges, breaklines and valleys, on
the other hand, the constraint weights should be big enough
if the surface and intensity changes are gentle such as for flat
open areas. In this paper the proposed new ARMLSM (Ar-
ray Relaxation MLSM) which was developed from Rauhala's
Global Least Squares Matching (GLSM) ideas is a good ex-
ample of such MLSM, it rightly takes into account the object
surface details and the image intensity changes through the
variable constraint weight model. ARMLSM's matching effi-
ciency can reach about 15 times faster than the conventional
MLSM's.
In the following, the first two sections give a brief descrip-
tion of the conventional MLSM and Rauhala's optimal weight
model ARMLSM, then the new ARMLSM under the variable
weight model will be presented, in Section 5, we combine
multiresolution strategy and the new ARMLSM into our Hi-
erarchical ARMLSM, and finally, tests and conclusions are
discussed.
2 CONVENTIONAL MLSM
Assuming the parallax of a left epipolar line point gi(z, y) is
—a?, the observation of the single least squares matching is
(ignoring the radiometric deformation):
gi(z, y) — g2(z + 2°, y) = n(z,y) (1)
where g2(z + 2°, y) is the corresponding point of gi(z, y) in
right epipolar line, and n(z,y) means the random noise.
If the z-parallax is interpolated from its four neighbour grid
nodes through bilinear interpolation, the spacing between
neighbour nodes is 1 and the distances from the point to
node (4,7) are dy and dz (0 < dı,dz < 1), then the error
