and Heipke 1994]. These previous works show that the
Moravec operator and the Fórstner interest operator perform
best for real images. The Fórstner interest operator was chosen
because of its salient features such as rotation invariant and
subpixel accuracy. For a more detailed description of the
Fórstner interest operator the reader is referred to Fórstner and
Gülch [1987].
Linear feature extraction (edge detection) plays a crucial part
in digital photogrammetry and computer vision. Boundaries of
objects tend to show up as intensity discontinuities in an image
(edges). An edge operator algorithm is designed to detect local
edges within small spatial extents. The computer vision and
image processing literature is abound with edge operators, see,
e.g. [Ballard et al. 1982, Haralick and Shapiro 1992].
To obtain the straight lines with corner points as their end
points, the straight line extraction algorithm must be well
behaved around the corner points and should produce as long
and straight lines as possible. In addition, the algorithm must
have good geometric precision(localization). After investigating
existing linear feature extraction algorithms, a simple algorithm
which fulfills to some extent all the necessities described above
is developed.
The proposed straight line extraction algorithm is based on
two properties:
1. good geometric precision (localization).
2. [lines are as straight and long as possible.
The first property can be achieved by applying the 2x2 Robert
gradient operator which is optimal among 2x2 operators
[Haralick and Shapiro 1992]. The computed gradient magnitude
is thresholded by a free parameter which is estimated from the
whole image content. This weight threshold step prevents
generating weak and less meaningful straight lines. The second
property, long and straight line, can be obtained by the analysis
of the chain of edge pixels which results from edge following.
The edge following can be implemented in two different ways:
e gradient magnitude based approach,
e gradient orientation based approach.
The paper [Burns et al. 1986] shows that the gradient
orientation varies relatively less over the intensity surface than
the gradient magnitude. Thus, the gradient orientation based
approach of edge following is selected. Next, the chain of edge
pixels is analyzed to extract a long and straight line from the
chain. The algorithm for extracting a long and straight line from
the chain of edge pixels is mainly based on an algorithm of
Douglas and Peuker [Ballard and Brown 1982]. With the
Douglas and Peuker algorithm, the straightness of line can be
achieved by a small threshold for norm distance.
The suggested algorithm is simple, computing efficient and
does not require any postprocessing such as thinning. Since the
2 x 2 Robert gradient operator is implemented, it interacts well
with the physical boundaries. However, because the operator
window size is small, it may suffer from the noise in an image.
It must be noted that the success of matching depends heavily
on good feature descriptions. However, the primary concern of
this work is not feature extraction but relational matching and
its related procedures.
2.1 Feature Postprocessing
The interest point operator fails to detect corner points of
feature lines that intersect outside of the threshold angle. The
gradient disturbance around corner points also causes the failure
of detecting corner points. Some of those missing corner points
can be recovered by using extracted straight lines. When two
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
or more straight lines extracted by the suggested algorithm meet
at a point which is not detected as a corner point by the interest
point operator, the point is considered as a corner point.
However, if the angle between straight lines is less than 30
degrees, the point is not considered as a corner point and also
two straight lines are not taken as one long straight line.
Due to noise, low resolution of the image, and shadow cast by
a building, the line following does not reach the corner points
detected by the interest point operator or passes over the corner
points. To solve this problem, a corner point is searched inside
the area A which is created by width w and distance d. The
search for a corner point is based on the following two rules:
] Proximity.
2. Forward primary.
Based on the proximity rule, the search starts from the end
point of a straight line by checking its 8 neighborhood. The
forward primary rule means that the search follows primarily
the extending line direction. If a corner point is not found after
the search moves one pixel forward along the line, it moves one
pixel backward along the line. This procedure repeats until a
corner point is found or to the end of search area. When the
search finds more than one corner point, the corner point that is
closest to the line and is in the forward direction is selected
based on the two rules.
3. PROPOSED RELATIONAL MATCHING SCHEME
The proposed scheme of relational matching utilizes straight
line primitives and their binary relations. A potential problem
of relational matching is a large search space which may result
in unacceptable computation cost. Two measures are introduced
to prune the large search space. For one, only a limited number
of binary relations between line primitives are allowed. The
second measure is to determine good initial approximations.
Because the two relational descriptions do not match
precisely (noise, occlusion, etc.), inexact matching and nil
mapping is used. The evaluation functions have been widely
used to guide the heuristic search to find the solution. To
compare the behavior of a heuristic search with respect to
evaluation functions, two evaluation functions (cost and benefit
functions) are implemented. The heuristic tree search method
A* with heuristics (unit ordering and modified forward
checking) is implemented to find the mapping between two
relational descriptions.
3.1 Description of Primitives and Relations
The relational description consists of primitives and relational
tuples among the primitives. Three primitives are used in this
study: (1) Open straight line, (2) Half-open straight line and (3)
Closed straight line. Each straight line may have none, one or
two corner points at its ends. An open straight line has no
corner points, the half-open straight line has one corner point.
and the closed straight line has two corner points. Each line
primitive has three attributes: Length, Orientation and Contrast.
The units of length and orientation are in pixels and degrees,
respectively. The contrast could be 0 or 1 depending on the
direction of line gradient and line orientation. Figure 1
illustrates the attributes of the line primitives.
Three 2-D binary relations constitute the relational description:
1. Central distance: the distance between the centers of
two straight lines.
2. Short distance: the shortest distance between two
straight lines.
112
contrast = (
^
Figur:
3. "^AI
Figure 2 illu:
three relation
spatial relati
that all attrib
relational 1
quantities ex
proposed pri
with large
described ab
rotation exist
angle
|
short
| dista
b Lam
Figure 2
3.2 2-D Bin
Each primi
binary rela
density and
the straight-
the midpoir
approach i:
rectangles s
of line prim
Two-dim
image into
certain nur
rectangular
the neighb:
binary rela
of a 2-D
representec
centers of
have 4 or 5
In the in
approach a
In summai
neighborh«
] Th
