LINEAR FEATURES EXTRACTION BY STRING MATCHING
FOR AUTOMATIC DEM GENERATION
King-Chang Lo
Professor, Institute of Survey Engineering,
National Cheng Kung University, Taiwan, Republic of China
Commission III, Working Group 2
KEY WORDS: Features Extraction, String Matching, Cost Function, DEM Generation
ABSTRACT:
According to the strategy "refinement from coarse" for automatic DEM generation, highly reliable coarse DEM
data need to be produced first. We start with image conditional smoothing to remove minor features or noise
by non-linear filter, e.g., the conditional rankorder filter. Then we use a gradient filter to detect the pronounced
linear features in each epipolar line at the zero crossing of the grey value function, then, a string of pronounced
linear features have been detected along the conjugated epipolar lines, but these are not always found to
correspond to each other because different terrain situations give different reflections. To solve this problem, an
algorithm called string matching must be found to confirm and extract the real corresponding feature pairs based
on the theory of minimum cost sequence of error transformations. By applying string matching at feature level
rather than signal processing level to extract the corresponding feature pairs in conjugated epipolar line pairs,
we confirm the extracted linear features again by checking the continuation of linear features between neighbour-
ing epipolar lines, the reliability can be increased still more. These extracted corresponding linear feature pairs
can be used to generate a coarse DEM. The major requirement for generating a coarse DEM with high reliability
is then fulfilled. Based on these high reliable coarse DEM as good conjugacy position prediction, the refinement
process, such as object space least squares matching, can be done for high quality DEM generation.
1. INTRODUCTION
Based on the strategy "coarse to fine" for DEM
generation, highly reliable coarse DEM data need to be
produced first. Not only the edge features of
homogeneous intensity regions and uniform texture
regions can be used for coarse DEM generation
[Lo,1993], but also the linear features. Therefore, the
string matching of linear features is presented for
coarse DEM generation.
We start with image conditional smoothing to
distinguish the linear features and reduce minor
features or noise by non-linear filter, eg, the
conditional rankorder filter [Mulder & Sijmons,1984].
A gradient filter is used to detect the pronounced linear
features in each epipolar line at the zero crossing of the
grey value function, and apply string matching at
feature level rather than signal processing level to
extract the corresponding feature pairs in conjugated
epipolar line pairs. These conjugated feature pairs are
used for producing coarse DEM and then be refined by
a high accuracy matching method, such as, object space
least squares matching [Wrobel,1987;Heipke, 1992].
472
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
2. LINEAR FEATURES DETECTION
As a result of the conditional rankorder operator,
pronounced linear features show up as a string along an
epipolar line. Convolution of the image with a gradient
filter [1,-1,0] gives the zero crossing phenomenon when
linear features exist (Fig. 1).
In Fig. 1a, there are linear features which show up as
peaks and valleys. From Fig. 1b, the properties
(attributes) that can be obtained for linear features are:
(a) the position (PS) of the peak/valley which is
located at position I+1 of the zero crossing I(+) to
I+1(-)or I(-) to I+1(+) (this implies a Laplacian filter
effect)
(b) the slope at the front (SF) of the peak/valley and
the slope at the back (SB) of the peak/valley which can
be obtained at positions I and I+1in Fig. 1b. An
additional property is the grey level (GL) of the
peak/valley which can be obtained at the position of
the peak/valley in previous conditional rankorder
smoothing image file (Fig. 1a).
which
Fig. 1:
3. LIN
MA’
After
remove
pronot
the cc
found
terrain
this pi
and e
on the
cost sé
minim
There
using |
condit
could
corres
measu
with n
we ch
values
curve
assign
then
suitab