available for each scalar component. The goal state
(where the sum of the squared residuals is minimum)
would always be found by complete search. However, for
computer implementation further development is
necessary to keep the computational load tolerable.
4. MAKING SEARCH EFFICIENT
The efficiency of any search-based method is dependent
on three factors: the total size of the search space, the
efficiency of pruning techniques for reducing the search
space, and the effort required to evaluate a single state in
the search space.
4.1 Size of the search space
The total size of the search space can be reduced by
keeping a) the number of unknown parameters as small as
possible, b) the value ranges of the unknown parameters
as tight as possible, and c) the final step size with respect
to the unknown parameters as coarse as possible. An
overall treatment of these issues is given below and we
will return to them throughout the rest of this paper.
In our problem it is possible to reduce the number of
unknown parameters by taking the fictitious gray level
variables , G,,ie A, outside the search space. Instead,
they can be evaluated within each state of the search
simply by computing the average individually for each
variable. This is possible if the normalization of the gray
levels is not necessary. In this case, the approach is
mathematically rigorous because the variables are
mutually independent. The size of the parameter vector p
in Z(X,Y,p) should be kept minimal to reduce the total
size of the search space.
The condition b) requires some case-dependent know-
ledge of the realistic ranges of unknown variables.
Condition c) is closely related with the measuring
accuracy of the matching algorithm. It could also be
called resolution. It should be sufficiently high for not
reducing the accuracy of the matching. If the expected
accuracy of a variable is for example 100 mm, then it is
not usually necessary to use a smaller than a 50 mm step
size and in no circumstances smaller than a 10 mm step
size.
4.2 Pruning techniques
Most of the pruning techniques used to reduce a search
space are heuristic and do not always guarantee that the
optimal state is found but rather a sub-optimal state
(Pearl, 1984; Sarjakoski, 1988). For our application a
hierarchical search is an obvious choice. It is based on
the principle that the search is first completed using a
wide range and a coarse step size, whereafter the search
is repeated using a tighter range and a smaller step size.
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
Hierarchical matching techniques have become a
standard method in digital photogrammetry, especially in
the production of digital elevation models (Grün and
Baltsavias, 1988; Helava, 1988; Ackermann and
Krzystek, 1991; Heipke, 1992). In principle they are not
identical with hierarchical search methods because also
the input gray level functions is different, due to the use
of image pyramids. The motivation for using hierarchical
matching is also different: they are used primarily to avoid
mismatches on high frequency features, whereas the
reduction of computation is only of secondary
importance.
4.3 Evaluating a single state
The effort required to evaluate a single candidate is the
third criterion for making a search-based technique
efficient. In our problem the number of the groundels
involved has a direct influence on the computing time and
therefore this number should be considered carefully. The
issue is strongly dependent on the application. The use of
hierarchical approaches is motivated also by this
efficiency factor.
Regarding the processing of a single groundel, the
computations involve the evaluation of the elevation
function Z(X,Y,p) and the spatial transformation function
S(X,Y,Z,r,). A continuous elevation function Z(X,Y,p)
can be expressed as a linear or as a piece-wise linear
function in X and Y. This makes it possible to
approximate the mapping from the 3-D object space to the
2-D image space with a bilinear interpolation. In this
technique the mapping is computed rigorously in the
corner points of a patch and by bilinear interpolation within
the patch. The technique is well-known as an anchor-point
method in the rectification of digital images.
The bilinear interpolation of the gray-level values can be
replaced by nearest-neighborhood interpolation in
supersampled input images. The approach is fully
rigorous if the supersampling is carried out using bilinear
interpolation with a sufficient enlargement factor. The
image pyramid is, so to say, extended some levels below
the ground by means of supersampling with bilinear
interpolation. These levels are computed only locally and
stored temporarily, due to their high storage
requirements. With this technique the repeated
resampling will be avoided in the search.
5. APPLICATION CASES
The principle of least squares matching by search has
been described above in its generic form. In this section
we specialize the technique for some frequently
encountered tasks in digital photogrammetry, especially
when aerial images are used. It must be emphasized that
the list is not meant to be complete.
726
5.1
In h
plar
sion
seal
also
dire
the
defc
can
whe
the |
5.2
With
feat
algo
foun
diffe
verti
ima(
effic
the
Grr
the |
mad
equ:
5.3
imp
orier
epip
stric
espe
knov
metl
mair
impr
eack
sear
com
nece
sear
5.4
Matc
oper
cont
simu
first
'groL
gooc
the t
