AG 1) —— 
N 
N 
JA W 
DC 
  
SS 
NS 
  
Sum 
SS 
Ns 
SS 
N 
   
        
      
   
   
X) 0,11) —— 
Nr 
| LA 
1 #3 G 
0.6 
  
Figure 1: Scale-space behaviour of the ideal line f, when convolved with the derivatives of Gaussian kernels for x € [—3.3] and 
e € [0.2, 2] 
SNO. ee 
  
  
(xo. 1.1) —— FAX 051,1) ——— 
  
Figure 2: Scale-space behaviour of the bar-shaped line f, when convolved with the derivatives of Gaussian.kernels for x € [—-3. 3] and 
c € [0.2, 2] 
The line detection algorithm will be developed for this type of 
profile, but the implications of applying it to bar-shaped lines will 
be considered later on. 
2.2 Detection of Lines in 1D 
In order to detect lines with a profile given by (2) in an image =(x) 
without noise, it is sufficient to determine the points where ='(x) 
vanishes. However, it is usually convenient to select only salient 
lines. À useful criterion for salient lines is the magnitude of the 
second derivative z" (x) in the point where z'(z) = 0. Bright 
lines on a dark background will have z” (x) « 0 while dark lines 
on a bright background will have z" (x) 3» 0. 
Real images will contain a significant amount of noise. There- 
fore, the scheme described above is not sufficient. In this case, the 
first and second derivatives of z(x) should be estimated by con- 
volving the image with the derivatives of the Gaussian smoothing 
kernel 
2 
1 re 
—— 
— 3243 , (3) 
Varo 
The responses, i.e., the estimated derivatives, will be; 
ga Xo 
ral wi BY =" arr). f) (4) 
"o. Gu h) = iG) * for) (5) 
ur, G,w,h) seu u)x (n) (6) 
These equations are given in greater detail in (Steger, 1996). 
Equations (4)-(6) give a complete scale-space description of 
how the ideal line profile f, will look like when it is convolved 
with the derivatives of Gaussian kernels. Figure | shows the 
responses for an ideal line with w = | and h = 1 (i.e., a bright 
line on a dark background) for x € [-3,3] and e € [0.2,2]. As 
can be seen from this figure, 7, (x, 6, w, h) = 0 & x = O forall 
o. Furthermore, r7 (zx, c, w, h) takes on its maximum negative 
value at x = O for all c. Hence it is possible to determine the 
precise location of the line for all c. Furthermore, it can be seen 
that because of the smoothing the ideal line will be flattened out 
as o increases. This means that if large values for o are used, the 
threshold to select salient lines will have to be set to an accordingly 
smaller value. Section 4 will give an example of how this can be 
used in practice to select appropriate thresholds. 
For a bar profile without noise no simple criterion that depends 
only on z'(z) and z"(x) can be given since z'(x) and z"(x) 
822 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
vanish in the interval [—w, w]. However, if the bar profile is 
convolved with the derivatives of the Gaussian kernel, a smooth 
function is obtained in each case. The responses will be: 
Tor, c, w, hy uss h (os (x +w)— d(x — w)) (7) 
ry, (ix, Gu hy = h(ge (x + w) — ge(x — w)) (8) 
ri (2,0, w, him A (go (x + w) — go (a — w)) 4i n9) 
Figure 2 shows the scale-space behaviour of a bar profile with 
w = | and h = | when it is convolved with the derivatives of a 
Gaussian. It can be seen that the bar profile gradually becomes 
"round" at its corners. The first derivative will vanish only at 
x = O for all à > O because of the infinite support of go (x). 
However, the second derivative ry (x, c, w, h) will not take on 
its maximum negative value for small o. In fact, for o. « 0.2 
it will be approximately zero. Furthermore, there will be two 
distinct minima in the interval [—w, w]. It is, however, desirable 
for rj (z, c, w, h) to exhibit a clearly defined minimum at z = 0. 
After some lengthy calculations it can be shown that 
c 2w/V3 (10) 
has to hold for this. Furthermore, it can be shown that 
ry (2, 0, w, h) will have its maximum negative response in scale- 
space for c. — w/v/3. This means that the same scheme as 
described above can be used to detect bar-shaped lines as well. 
However, the restriction on « must be observed. The same anal- 
ysis could be carried out for other types of lines as well, eg, 
roof-shaped lines. However, it is expected that no fundamentally 
different results will be obtained. For all o above a certain value 
that depends on the line type the responses will show the desired 
behaviour of z'(0) — 0 and z"(0) « 0 with ="(x) having a 
distinct minimum. 
The discussion so far has assumed that lines have the same 
contrast on both sides of the line. This is rarely true in real 
images, however. For simplicity, only asymetrical bar-shaped 
lines 
0, x <—w 
fol) = L, soil St (11) 
had uw 
are considered (^ € [0, 1]). The corresponding responses will be: 
ra(x,0,w,h) = óc(x-w)-—(h-—1)és(x — w) (12) 
ra(x,o,w, h) Jo (x + w) — (h — 1)go (x — w) (13) 
Jo (x + w) — (h — 1)g! (2 — w).(14) 
ra(x,0,w,h) 
   
    
      
    
      
   
    
     
  
   
    
    
     
   
   
   
     
   
    
    
     
     
    
   
      
     
    
    
   
        
      
    
  
   
   
  
    
  
   
    
  
Fi