(a) Input Image
(b) New approach (a = 1.5)
(c) Facet model (7 x 7)
Figure 4: Line points detected in image (a) using the new approach (b) and using the facet model (c)
2.5 Examples
Figure 4(b) gives an example of the results obtainable with
the presented approach. Here, bright line points were extracted
from the input image given in Fig. 4(a). This image is part of
an aerial image with a ground resolution of 2m. Figure 4(c)
shows the results that were obtained using the facet model. In
both cases the sub-pixel location (p., py) of the line points and
the direction (n4, n,) perpendicular to the line are symbolized
by vectors. The strength of the line, i.e., the absolute value of
the second directional derivative along (n.., ny) is symbolized by
gray values. Line points with high saliency have dark gray values.
From Fig. 4 it can be seen that in the approach presented here
there will always be a single response to a given line. When the
facet model is used, multiple responses are quite common. Note,
for example, the line that enters the image in the middle of the left
hand side. This makes linking the individual line points into lines
rather complicated. In (Busch, 1994) the response of the operator
is thinned before linking to get around this problem. However,
this operation throws away useful information since diagonal lines
will be thinned unnecessarily. In the new approach the linking
will be considerably easier and no thinning operation is needed.
3 LINKING LINE POINTS INTO LINES
After individual line pixels have been extracted, they must be
linked into lines. In order to facilitate later mid-level vision
processes, e.g., perceptual grouping, the resulting data structure
should contain explicit information about the lines as well as the
junctions between them. This data structure should be topologi-
cally sound in the sense that junctions are represented by points
and not by extended areas as in (Busch, 1994). Furthermore, since
the presented approach yields only single responses to each line,
no thinning operation needs to be performed prior to linking. This
assures that the maximum information about the line points will
be present in the data structure.
Since there is no suitable criterion to classify the line points
into junctions and normal line points in advance without hav-
ing to resort to extended junction areas, another approach has
been adopted. From the algorithm in Sect. 2 the following
data are obtained for each pixel: the orientation of the line
(na.m,4) — (cosa,sin o), a measure of strength of the line (the
second directional derivative in the direction of o), and the sub-
pixel location of the line (pa, py).
Starting from the pixel with maximum second derivative, lines
will be constructed by adding the appropriate neighbour to the
current line. Since it can be assumed that the line point detection
824
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
algorithm will yield a fairly accurate estimate for the local direc-
tion of the line, only three neighbouring pixels that are compatible
with this direction are examined. For example, if the current pixel
is (c«, cy) and the current orientation of the line is in the interval
[—22.5°,22.5°], these points will be (c, 4- 1, c, — 1), (c« -- 1, c).
and (c, 4 1, c, -- 1). The choice about the appropriate neighbour
to add to the line is based on the distance between the respective
sub-pixel locations and the angle difference of the two points.
Let d = ||p2 — p1||, be the distance between the two points and
B — |o» — «1|, B € [0, 7/2], be the angle difference between
those points. The neighbour that is added to the line is the one
that minimizes d + wf. In the current implementation, w = 1 is
used. This algorithm will select each line point in the correct or-
der. At junction points, it will select one branch to follow without
detecting the junction. This will be detected later on. The algo-
rithm of adding line points is continued until no more line points
are found in the current neighbourhood or until the best matching
candidate is a point that has already been added to another line.
If this happens, the point is marked as a junction, and the line that
contains the point is split into two lines at the junction point.
New lines will be created as long as the starting point has
a second directional derivative that lies above a certain, user-
selectable upper threshold. Points are added to the current line as
long as their second directional derivative is greater than another
user-selectable lower threshold. This is similar to a hysteresis
threshold operation (Canny, 1986).
The contour linking approach presented here is similar to that
given in (Glazer, 1994). However, there the best neighbour is
determined from a neighbourhood that does not depend on the
current direction of the line. Furthermore, the author does not
mention whether explicit junction information is generated by the
algorithm.
With a slight modification the algorithm is able to deal with mul-
tiple responses if it is assumed that with the facet model approach
no more than three parallel responses are generated. No such case
has been encountered for mask sizes of up to 13 x 13. Under this
assumption, the algorithm can proceed as above. Additionally, if
there are multiple responses to the line in the direction perpen-
dicular to the line (e.g., the pixels (cz,cy — 1) and (cx, cy + 1)
in the example above), they are marked as processed if they have
roughly the same orientation as (cz, cy). The termination crite-
rion for lines has to be modified to stop at processed line points
instead of line points that are contained in another line.
Figure 5 shows the result of linking the line points in Fig. 4
into lines. The results are overlaid onto the original image. In
this case, the upper threshold was set to zero, i.e., all lines, no
matter how faint, were selected. If an upper threshold of 5 were
Fi:
e
dis
us
the
the
ge
ne
at
on
pb
lie
thi
ea
SC
th
th
