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