onstraints, ; 
iakes. The 
nakes, we 
mulated in 
kes (Least 
n of any a 
1ultaneous 
ation. The 
ns consist 
'onstraints 
1umber of 
to control 
ling of the 
raints are 
nd global 
along the 
90). The 
proaches, 
a lack of 
stence and 
1e balance 
. Also, the 
e. 
in a least 
mages for 
elopment, 
ir familiar 
IS can be 
obtained 
nce, e. g. 
'stimated 
al snakes, 
ound and 
ualitative 
sidered as 
| template 
rough the 
approach 
e, which 
»cclusions 
Digital Image(s) 
  
  
lo Image Preprocessing | ® 
' 
| Feature Identification & Classification | (M) 
eG 
| Dynamic Programming | (A) 
   
    
   
    
   
   
  
  
LSB-Snakes 
   
   
   
   
Camera 
Model(s) 
  
\ Y 
Monoplotting 
  
  
     
   
  
    
  
     
  
Multiple Images 
3-D Object Outline 
(D Input (A) Automatic (M) Manually © Output 
Fig. 1. A semi-automatic feature extraction scheme. 
2. LSB-Snakes 
LSB-Snakes derive their name from the fact that they are a 
combination of least squares template matching (Gruen, 1985) 
and B-spline snakes (Trinder, Li, 1995). In least squares notation 
we use three types of observations. These can be divided in two 
classes, photometric observations that formulate the grey level 
matching of images and the object model and geometric 
observations that express the geometric constraints and the a 
priori knowledge of the location and shape of the feature to be 
extracted. 
2.1 Photometric observation equations 
Assume a template and image region are given as discrete two 
dimensional functions PM(x, y) and g(x, y) , which might have 
been derived from the a priori knowledge of the feature of 
interest and a discretization of continuous functions (analogue 
photographs). They can be considered as the conjugate regions of 
a stereopair in the ‘left’ and the ‘right’ photograph respectively. 
An ideal situation gives 
PM(x, y) = g(x,y). (2-1) 
Taking into consideration the noise and assuming that the 
template is noise free or its noise is independent of the image 
noise, equation (2-1) becomes, 
PM(x, y) - e(x, y) = g(%, y), (2-2) 
where e(x, y) is a true error function. 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
In terms of least squares estimation, equation (2-2) can be 
considered as a nonlinear observation equation which models the 
observation vector of PM(x, y) with a discrete function g(x, y) . 
Applying Taylor’s series to equation (2-2), dropping second and 
higher order terms, with notations 
d 
G, "P 3,805 y) , 
5 (2-3) 
e 3€ y), 
the linearized form of the observation equation becomes 
-e(x, y) 2 G,(9, 9)Ax € G, (x9, y9)Ay 4 
guid ; (2-4) 
* (g(x9, y9) - PM(x, y) . 
The relationship between the template and the image patch needs 
to be determined in order to extract the feature, i. e. the 
corrections Ax , Ay in equation (2-4) have to be estimated. In the 
conventional least squares template matching applied to feature 
extraction, an image patch is related to a template through a 
geometrical transformation, formulated normally by a six 
parameter affine transformation to model the geometric 
deformation (Gruen, 1985). The template is typically square or 
rectangular and sizes range from 5x5 to 25x25 pixels. 
Originally the LSM technique is only a local operator used for 
high precision point measurement. It was extended to an edge 
tracking technique to automatically extract edge segments 
(Gruen, Stallmann, 1991), and a further extension was made 
through the introduction of object-type-dependent neighbour- 
    
  
= 
initial 
  
position final 
solution 
(a) 
  
(b) 
Fig. 2. Visualization of (a) least squares template matching of 
an edge and (b) LSB-Snakes of a road segment, with the 
initial position (black) and final solution (white). 
267