IEEE
TRANSACTIONS
ON
PATTERN
ANALYSIS
AND
MACHINE
INTELLIGENCE,
VOL.
PAMI-8,
NO.
4,
JULY
1986
Extracting
Straight
Lines
J.
BRIAN
BURNS,
ALLEN
R.
HANSON,
MEMBER,
IEEE,
AND
EDWARD
M.
RISEMAN,
MEMBER,
IEEE
Abstract-This
paper
presents
a
new
approach
to
the
extraction
of
straight
lines
in
intensity
images.
Pixels
are
grouped
into
line-support
regions
of
similar
gradient
orientation,
and
then
the
structure
of
the
associated
intensity
surface
is
used
to
determine
the
location
and
prop-
erties
of
the
edge.
The
resulting
regions
and
extracted
edge
parameters
form
a
low-level
representation
of
the
intensity
variations
in
the
image
that
can
be
used
for
a
variety
of
purposes.
The
algorithm
appears
to
be
more
effective
than
previous
techniques
for
two
key
reasons:
1)
the
gradient
orientation
(rather
than
gradient
magnitude)
is
used
as
the
initial
organizing
criterion
prior
to
the
extraction
of
straight
lines,
and
2)
the
global
context
of
the
intensity
variations
associated
with
a
straight
line
is
determined
prior
to
any
local
decisions
about
participating
edge
elements.
Index
Terms-Boundary
extraction,
edge-analysis,
gradient-based
segmentation,
image
processing,
line
parameters,
line
representation,
plane-fitting,
straight
lines.
I.
INTRODUCTION
T
HE
organization
of
significant
local
intensity
changes
into
the
more
global
abstractions
called
"lines"
or
"boundaries"
is
an
early,
but
important,
step
in
the
trans-
formation
of
the
visual
signal
into
useful
intermediate
constructs
for
interpretation
processes.
Despite
the
large
amount
of
research
appearing
in
the
literature,
effective
extraction
of
straight
lines
has
remained
a
difficult
prob-
lem
in
many
image
domains.
There
are
two
goals
of
this
paper:
1)
the
development
of
mechanisms
for
extracting
straight
lines
from
complex
images,
including
lines
of
ar-
bitrarily
low
contrast;
and
2)
the
construction
of
an
inter-
mediate
representation
of
edge/line
information
through
which
high-level
interpretation
mechanisms
have
efficient
access
to
relevant
lines.
To
the
degree
that
straight
lines
may
be
effectively
ex-
tracted
and
efficiently
represented,
a
variety
of
other
in-
termediate
processing
goals
are
greatly
facilitated.
Curved
lines
can
be
approximated
reasonably
well
as
aggregates
of
piecewise-linear
segments.
In
many
cases,
continuous
representations
of
a
boundary
may
be
derived
from
adja-
cent
linear
segments
by
treating
differences
in
their
ori-
entations
as
local
curvature
estimates.
In
addition,
tex-
tured
regions
can
be
extracted
as
aggregates
of
line
elements
with
specific
common
properties
of
length,
con-
trast,
orientation,
etc.
Manuscript
received
February
1,
1985;
revised
August
14,
1985.
Rec-
ommended
for
acceptance
by
W.
E.
L.
Grimson.
This
work
was
supported
in
part
by
the
Air
Force
Office
of
Scientific
Research
under
Contract
F49620-83-C-0099.
The
authors
are
with
the
Department
of
Computer
and
Information
Sci-
ence,
University
of
Massachusetts,
Amherst,
MA
01003.
IEEE
Log
Number
8406515
A.
Problems
in
Edge
Extraction
Edges
are
usually
defined
as
local
discontinuities
or
rapid
changes
in
some
image
feature,
such
as
image
lu-
minance
or
texture.
These
changes
are
detected
by
a
local
operator,
usually
of
small
spatial
extent
with
respect
to
the
image,
that
measures
the
magnitude
of
the
change
and,
in
many
cases,
its
orientation
as
well.
Lines
are
com-
monly
defined
as
collections
of
local
edges
that
are
con-
tiguous
in
the
image.
Thus,
many
algorithms
rely
on
a
two-step
process
for
line
extraction:
detection
of
local
edges
that
are
then
aggregated
into
the
more
globally
de-
fined
lines
on
the
basis
of
various
grouping
criteria.
In
the
one-dimensional
case,
an
ideal
edge
is
a
step
change
in
the
value
of
the
underlying
feature.
In
two
di-
mensions,
the
ideal
edge
may
be
viewed
as
a
step
discon-
tinuity
in
the
values
of
the
image
feature
in
a
direction
perpendicular
to
the
spatial
orientation
of
the
edge.
We
will
refer
to
a
straight
line
as
a
set
of
collinear
and
con-
tiguous
edges;
i.e.,
a
straight
line
has
a
length
associated
with
a
continuous
discontinuity.
Shortly,
we
will
discuss
the
additional
constraints
that
we
impose
on
the
intensity
change
to
organize
them
into
straight
lines.
Since
ideal
step
changes
are
rarely
found
in
real
images,
the
magni-
tude
of
the
feature
change
across
a
line
is
usually
distrib-
uted
over
an
area.
Hence,
the
underlying
image
structure
supporting
a
line
has
a
width
measured
perpendicular
to
the
line
orientation
in
addition
to
its
length.
We
refer
to
the
collection
of
pixels
so
defined
as
a
line-support
re-
gion.
Note
that
our
use
of
the
term
"line"
differs
from
some
researchers
[26],
[7],
[13]
who
use
the
term
"line"
to
refer
to
image
events
in
which
the
intensity
surface
forms
a
ridge,
possibly
of
narrow
width,
for
which
there
is
no
distinct
location
for
the
boundaries
on
either
side
of
the
ridge.
This
view
is
related
to
the
"roof"
intensity
profile
of
edges
in
the
Binford-Horn
line
tracker
[15].
In
our
view,
these
narrow
linear
image
events
will
have
a
width
formed
by
two
locally
parallel
lines
of
opposite
contrast.
It
is
only
the
location
of
the
lines
that
is
ambiguous,
not
their
existence.
In
the
case
where
the
ridge
in
the
intensity
surface
is
very
narrow,
even
to
a
subpixel
level,
we
are
taking
the
position
that
if
the
difference
in
adjacent
pixels
is
meaningful,
it
can
be
used
to
define
a
narrow
region
with
parallel
lines
delimiting
this
image
event.
The
problems
encountered
with
local
edge
operators
are
widely
known
and
are
related
to
1)
the
possibly
small
spa-
tial
extent
of
the
operator
relative
to
the
events
they
are
designed
to
detect,
2)
the
deviation
of
actual
image
data
from
assumed
models,
and
3)
aliasing
due
to
the
discrete
0162-8828/86/0700-0425$01.00
©
1986
IEEE
425
剩余30页未读，继续阅读
评论2