Image Segmentation using Spectral Graph Theory
Speaker: | Gary Miller |
---|---|
Affiliation: | Carnegie Mellon University |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
In
this
talk
we
present
a
new
image
segmentation
algorithm,
Spectral
Rounding
(SR),
and
a
fast
solver.
The
combination
is
used
for
segmenting
2D
and
3D
images.
Applying
SR
to
the
Berkeley
data
base
of
human
segmented
images,
and
medical
examples
such
as
tumors
in
mammograms
and
3D
retinal
scans
gives
robust
quality
segmentations.
When
used
with
our
fast
solver
SR
is
nearly
nearly
time.
The
key
idea
in
SR
is
to
view
an
image
as
a
2D
mattress
of
springs.
Two
neighboring
pixels
are
connected
by
a
spring
where
the
spring
constant
is
determined
by
local
similarity
in
the
pixel
intensity.
Shi
and
Malik
proposed
the
important
idea
of
using
the
fundamental
modes
of
vibration
of
this
mattress,
the
eigenvectors,
to
segment
the
image.
The
straightforward
method
for
partitioning
a
graph
using
its
eigenvectors,
however,
does
not
seem
to
work
well
in
practice.
We
propose
a
relaxation
method
based
on
eigenvectors
for
finding
these
graph
cuts.
At
each
round
a
few
fundamental
eigenvectors
are
computed,
from
which
the
spring
constants
are
updated
and
these
eigenvectors
are
recomputed
using
the
new
spring
constants.
Thus
the
spring
constants
are
successively
readjusted
until
the
mattress
disconnects,
an
image
segmentation.
SR
compares
favorably
with
hand-segmented
images
from
the
Berkeley
database
and
the
normalized
cut
metric.
We
also
show
convergence
in
general
and
termination
for
several
important
cases.
The
second
issue
addressed
is
fast
algorithms
for
finding
the
associated
eigenvectors
and
solving
related
linear
systems.
This
is
a
critical
issue
because
modern
3D
medical
images
may
contain
a
billion
nodes
(voxels).
A
related
and
important
first
step
to
finding
eigenvector
and
of
interest
on
its
own
is
solving
2D
and
3D
Laplacians.
For
instance,
Siemens
uses
Laplacians
for
their
new
assisted
image
segmentation
algorithm.
We
present
the
first
linear-time
algorithm
for
2D
and
more
general
planar
Laplacians.
This represents joint work with Yiannis Koutis and David Tolliver.