ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision‘, Graz, 2002
4. The Matching Approach
In our application of automatic DSM generation from TLS
imagery, a combination of algorithms for grid point matching
and feature point matching is used. Image pyramids are
incorporated into the matching strategy. An image matching
algorithm, which has the ability to bridge over the poor texture
areas and preserve the terrain features at high accuracy, by
using the TLS raw images, was developed. The work-flow of
our combined matching approach is shown in Figure 2.
[ TLS raw images and orientation data |
| Image Pyramids |
Y
Geometrically Constrained
_Eeature Point Matching _
DSM (Approx.)
Geometrically
Constrained
[ Relaxation Matching L1 Candidate
Feat Search
eature
Point A À
Extraction | [ DSM (intermediate) |} — ———m —
[Modified MPGC | | GCMM (optional) |
|
Final DSM
Figure 2: Work-flow of our combined image matching
4.1 Input Data and Derivation of Approximations
The input data includes the TLS strip which normally consists
of three images of the forward, nadir and backward view CCD
arrays, and information about their interior and exterior
orientation parameters (for details see Gruen and Zhang, 2002).
Raw images from most other line-scanner digital sensors need a
special rectification process in order to eliminate distortions
caused by high frequency positional and attitude variations of
the camera during the flight. In this rectification process, each
scan-line of the raw image data is projected to a planar surface
defined by a horizontal plane at the mean terrain height.
Because of unknown object model at this point the rectified
images have no correct geometry and the results of this process
are only quasi-epipolar images. In the TLS system, a high
quality stabilizer is used in image acquisition, so the raw image
data can be directly used for image matching.
The image pyramid starts from the original TLS image. Each
pyramid level is generated by multiplying a generation kernel
and reduces the resolution by factor 3. The pyramid level
number is a pre-defined value which is either a user input or can
be determined according to the height range of the imaging
area.
The approximations for the following matching procedures are
extracted by geometrically constrained feature point matching,
which exploits the orientations of the TLS (see Figure 3).
Feature point extraction by using the Moravec interest operator
is performed on the highest level of the image pyramid in the
nadir view TLS image. Given a feature point in the nadir image,
an image ray that connects the instant perspective center and
this image point can be determined. Given a height
approximation Zo and a height interval AZ, the coordinates of
three object points (X,, Y, Zy-AZ), (Xo, Yo, Zo) and (Xj, Yi, Zo-
AZ) can be computed by using the pixel coordinates and
orientation elements. The height approximation Zo and the value
AZ can be derived from the user input (the maximum, minimum
and the average terrain height of the imaging area) By
projecting these three object points back to the forward and
backward view images, search windows can be determined.
These windows are assumed to be rectangular for a small region
in first approximation. Their width is + 5 to 11 pixels depending
on the level of the pyramid. The matches in the search images
are derived by cross-correlation technique, and they are
accepted if their correlation coefficient lies above a certain user-
defined threshold. We choose this threshold value as 0.9. As a
result, for each feature point on the nadir view TLS image a
conjugate image point triplet can be obtained. By using forward
intersection some blunders can be detected. The matching result
is used to interpolate the approximate values for the following
relaxation matching on the highest level of the image pyramid.
flight trajectory
es
ul I
Nadir Image
du
search window
Figure 3: The determination of the search window
4.2 Grid Point Matching based on Relaxation
The matching procedure can be treated as a labeling problem
and solved by relaxation technique. That is, we regard the
template image (for example, the nadir view image) as the
model and another image as the scene, and then use the feature
points in the model as a set of labels to label the feature points
extracted from the scene. Relaxation is one of the efficient
methods to solve the labeling problem. The work of Hancock
and Kittler, 1990 that uses Bayesian probability theory has
provided a theoretical framework and rigorous basis for the
relaxation method.
The important aspect of the relaxation matching algorithm that
distinguishes it from the single point matching is its compatible
coefficient function and its smoothness constraint satisfaction
scheme (Baltsavias, 1991; Zhang et al, 1992). This is most
important for areas with homogeneous or only little texture. In
such areas, the single point matching is unable to match images
because of the lack of information. With the smoothness
constraint, such areas can be bridged over, assuming that the
terrain surface varies smoothly over the area.
Firstly, the points are selected in form of a regular grid in the
template image (nadir view image). Given a grid point in the
template image, a search window can be determined (see Figure
3). The correct match of this point should lie in this search
window. However, due to repetitive texture or poor texture
information, there could be several candidate matches appearing
in the search window. These candidate matches are located
along the epipolar curve. They can be derived by traditional
cross-correlation technique, and the candidate matches are
selected if their correlation coefficient lies above a certain user-
defined threshold (we choose this threshold value as 0.7). The
approximations can be derived from the matching results of the
previous pyramid level.
Let /; be one of the grid points on the template image and /,
(j=1,..,m) its candidate matches on the search image. P(i,j) is
the probability of match /j—/;. Moreover, let I, be one of the
A- 133
me
