Boundary Extraction by Lineal Feature Growing
Randal C. NelsonDepartment of Computer Science
University of Rochester
We have developed a method for extracting lineal features, both curved and straight, from an image using extended local information to provide robustness and sensitivity. Such features are useful because they frequently correspond to object or material boundaries, which are of interest in e.g., object recognition systems. The method utilizes gradient magnitude and direction information, as the low-level boundary hypothesis, and incorporates explicit lineal and end-stop terms to measure the quality of a proposed extended feature. These terms are combined non-linearly to produce an energy landscape in which local minima correspond to lineal features called sticks. Subjectively these correspond to well terminated smooth curves or line segments. A gradient descent (stick-growing) process is used to find these minima. The method has been compared to two others for the case of line-segment extraction and shown to haveWhen used to find line segment and shown to have improved gap-crossing characteristics. Similar behavior has been observered for curved features.
The essence of the method is to utilize a conceptual
matching criterion by which any proposed boundary curve
can be compared against an image and given a score.
Then conceptually, a good set of boundaries can be found by
finding, from all possible smmoth curves, the one that produces the best
score, nullifying the effect of the image components contributing to
it, and repeating, until enough curves had been found.
The main practical problems with this method are making it efficient,
since it is
clearly impractical to look through all possible curves multiple
times; and designing an appropriate matching measure.
The efficiency problem can potentially be dealt with using any of
several approximate maximization techniques.
In this case, the problem is well enough behaved that a gradient descent
method is effective.
The issue of designing a matching criterion for mapping lineal features
to line segments is a bit subtle.
The main difficulty is that, while smooth curves can be well defined
mathematically in several ways, the notion of a lineal feature is a
subjective one, and must be dealt with at this level.
Intuitively, a lineal feature consists of a smooth, extended part,
and two ends.
Our matching criterion includes explicit representations for the
extended section of the feature, and the end stops.
We call the combined representation a stick.
The matching criterion is applied to the image as follows.
The gradient magnitude and direction are determined by applying a
set of local convolution operators to the image.
A local order statistic is applied to enhance gradient magnitude
values corresponding to discontinuities as opposed to those
arising from shading effects.
[Details of low-level processing]
These values represent local hypotheses about the existence of a boundary
at a particular orientation at a point.
To compute the match-score for a particular stick, the magnitude image
is convolved with three templates at the appropriate positions and
orientations.
One of these represents an extended segment, the other two end stop patterns.
The extended segment is, conceptually, a Gaussian whose central profile has
been stetched along the curve, and the end stop patterns are differences
of Gaussians with centers separated by two standard deviations.
The correlations are computed using only points whose gradient
direction is consistent with the direction of the curve.
The match score is computed by adding the straight correlation value to any
positive response from the end stop measures.
Negative values from the end-stop measures are ignored.
This non-linearity prevents a sudden brightening in the line from
inhibiting the growth of a stick.
[Details of energy measure]
Sticks are fitted to lineal features in the image as follows.
First, the gradient direction and magnitude are determined.
A starting point is then selected from a separate, thinned edge map.
Generally this is a point with high gradient magnitude, where a lineal
feature might be expected to pass.
Starting with a short initial stick aligned perpendicular to the local gradient
and centered at the staring point,
a gradient descent procedure is performed, varying the centerpoint,
orientation and length, the stick incrementally
in an attempt to maximize the match score.
This is done up to a length of about 13 pixels producing a seed segment.
Beyond that point, the effect of extension at both ends is explored by probing
out from a base point
with extension templates with a restriction that the orientation can
change only gradually.
This permits smooth curves to be followed.
The algorithm naturally terminates the growth process at corners or
on occlusion of the boundary. This accounts for over 95% of terminations
in most images. There are also a couple of special cases that are checked.
One is a closed boundary, and the other a gradual fadeout, as
occurs occasionally with highlights on semi-glossy surfaces.
[Details of growth process]
In order to find multiple segments,
the image is broken up into neighborhoods, and sticks are grown starting at the
top N locations in each neighborhood.
Pixels in the seed image near a completed curve are marked as subsumed, so that
the same boundaries are not found repeatedly.
A new starting location is not selected until completion of the growth
phase of the previous stick, since some previously attractive start
locations may be subsumed by the new feature.
A stick can grow out of its original neighborhood, which can have the
effect of eliminating some start-point candidates in others it passes through.
The pictures shown represent half-resolution examples of the performance
of the algorithm run on increasingly difficult images.
The green dots indicate start points for the growth of contours.
No user supplied parameters are needed. The algorithm runs "as is"
on images provided.
Click on the pictures to see full resolution versions.
Randal C. Nelson, ``Finding Line Segments by Stick Growing'', IEEE Transactions on PAMI, Vol. 16, 5, May 1994, 519-523. Abstract,
Galen C. Hunt and Randal C. Nelson, ``Lineal Feature Extraction by Parallel Stick Growing'', Third International Workshop on Parallel Algorithms for Irregularly Structured Problems (IRREGULAR96), Santa Barbara CA, August, 1996. Abstract,
Galen C. Hunt and Randal C. Nelson, ``Lineal Feature Extraction by Parallel Stick Growing'', University of Rochester, Computer Science TR 625, June, 1996. Abstract,
Full
Publication List
Back to
research page
Back to
Randal Nelson's home page