0X,6, 1,1) ——
the bar profile is
kernel, a smooth
; Will be:
(x — w)) (7)
q— w)) (8)
mieu) 5i 049)
bar profile with
e derivatives of a
adually becomes
ll vanish only at
upport of go (x).
will not take on
ict, for à < 0.2
here will be two
ywever, desirable
nimumat x = 0.
that
(10)
be shown that
esponse in scale-
same scheme as
ed lines as well.
The same anal-
les as well, e.g.,
o fundamentally
e a certain value
show the desired
z"(x) having a
s have the same
rely true in real
rical bar-shaped
(11)
'sponses will be:
$e (x — w) (12)
ge (x — w) (13)
go (x — w).(14)
The location where rz (x,c, w,h) = 0, i.e., the position of the
line, is given by
z= = In(l = h) : (15)
This means that the line will be estimated in a wrong position
when the contrast is significantly different on both sides of the
line. The estimated position of the line will be within the actual
boundaries of the line as long as
hel-eUt (16)
(a) Contours (o — 1.5) (b) Smoothed Image
Figure 3: Line detection for asymmetric lines (a). Smoothed
image (b).
Figure 3(a) illustrates this effect in practice. In this image
a three pixel wide line (i.e., w = 1.5) that has a ramp with
h € [0,1] on one side is shown. Note that the position of the
line lies within the true boundaries of the line up to a rather high
value of h. Hence, relatively large contrast differences can be
handled. The estimated positions of the line come as no surprise
when one looks at Fig. 3(b), which shows the smoothed image
the algorithm looks at internally to determine the line position.
To eliminate such erroneously located lines, simple thresholding
will suffice since r7 (x, c, w, h) will have a small value as — 1.
However, for illustrational purposes, the threshold has been set to
zero in this example.
2.3 Lines in 1D, Discrete Case
The analysis so far has been carried out for analytical functions
z(x). For discrete signals only two modifications have to be made.
The first one is the choice of how to implement the convolution in
discrete space. Integrated Gaussian kernels were chosen as convo-
lutions masks, mainly because they give automatic normalization
of the masks and a direct criterion on how many coefficients are
needed for a given approximation error. The integrated Gaussian
is obtained if one regards the discrete image z,, as a piecewise con-
stant function =(x) = z, forx € (n — i. n + i] and integrating
the continuous Gaussian kernel over this area. The convolution
masks will be given by:
gna = doln+ i) — $s(n— 3) (17)
no = do(n+3)-go(n- 3) (18)
9 e = ga (n + 5) — gL(n — 1) (19)
The approximation error is set to 107^ in each case. Of
course, other schemes, like Lindeberg's discrete Gaussian deriva-
tive approximations (Lindeberg, 1993) or a recursive computation
(Deriche, 1993), are suitable for the implementation as well.
The second problem that has to be solved is how to determine
the location of a line in the discrete case In principle, one could
use a zero crossing detector for this task. However, this would
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
yield the position of the line only with pixel precision. In order
to overcome this, the second order Taylor polynomial of z, is
examined. Let r, r', and 7" be the locally estimated derivatives
at point n of the image that are obtained by convolving the image
With g,, g;, and g,. Then the Taylor polynomial is given by
Mar ru Ira (20)
The position of the line, i.e., the point where p'(x) = O is
y-——. (21)
The point 71 is declared a line point if this position falls within the
pixel's boundaries, i.e., if € [— 2, $] and the second derivative
r" is larger than a user-specified threshold. Please note that in
order to extract lines, the response r, which is the smoothed local
image intensity, is unnecessary and therefore does not need to be
computed.
2.4 Detection of Lines in 2D
Curvilinear structures in 2D can be modeled as curves s(t) that
exhibit a characteristic 1D line profile (e.g., fp or f3) in the direc-
tion perpendicular to the line, i.e., perpendicular to s’(¢). Let this
direction be n(t). This means that the first directional derivative
in the direction n(t) should vanish and the second directional
derivative should be of large absolute value. No assumption can
be made about the derivatives in the direction of s'(1). For ex-
ample, let z(x,y) be an image that results from sweeping the
profile f, along a circle s(t) of radius ». The second directional
derivative perpendicular to s'(£) will have a large negative value,
as desired. However, the second directional derivative along s' (t)
will also be non-zero.
The only problem that remains is to compute the direction of
the line locally for each image point. In order to do this, the
partial derivatives rz, ry, rzz, rzy, and ry, of the image will
have to be estimated. This can be done by convolving the image
with the appropriate 2D Gaussian kernels. The direction in which
the second directional derivative of z(x, y) takes on its maximum
absolute value will be used as the direction n(£). This direction
can be determined by calculating the eigenvalues and eigenvectors
of the Hessian matrix
d CRY ) (22)
Vay! Tyy
The calculation can be done in a numerically stable and efficient
way by using one Jacobi rotation to annihilate the ».,, term. Let the
eigenvector corresponding to the eigenvalue of maximum absolute
value, i.c., the direction perpendicular to the line, be given by
(na, ny) with ||(na, ny)|l, = 1. As in the ID case, a quadratic
polynomial will be used to determine whether the first directional
derivative along (n4, ny) vanishes within the current pixel. This
point will be given by
(psspy) 7m nz ing) . (23)
where
Dae + Ty My
(24)
t= —
2 > 2
Pax a "E 27 ayNaNy + TyyTU,
Again, (ps, py) € [-3. 3] x [75. 3] is required in order for a
point to be declared a line point. As in the 1D case, the second di-
rectional derivative along (75, 14 ), 1.€., the maximum eigenvalue,
can be used to select salient lines.
