An efficient algorithm for image segmentation
Abstract
Problems of statistical inference involve the adjustment of
sample observations so they fit some a-priori rank requirements,
or order constraints. In such problems the objective is to
minimize the {\em deviation cost} function that depends on the
distance between the observed value and the modify value. In
Markov random field problems there is also a pairwise relationship
between the objects. The objective in Markov random field problem
is to minimize the sum of the deviation cost function and a
penalty function that grows with the distance between the values
of related pairs -- separation function.
We discuss Markov random fields problems in the context of a
representative application -- the image segmentation
problem. In this problem the goal is to modify color shades
assigned to pixels of an image so that the penalty function
consisting of one term due to the deviation from the initial
color shade and a second term that penalizes differences in
assigned values to neighboring pixels is minimized. We present
here an algorithm that solves the problem in polynomial time when
the deviation function is convex and separation function is
linear; and in strongly polynomial time when the deviation cost
function is linear, quadratic or piecewise linear convex with few
pieces (where ``few" means a number exponential in a polynomial
function of the number of variables and constraints). The
complexity of the algorithm for a problem on n pixels or
variables, m adjacency relations or constraints, and range of
variable values (colors) U, is O(T(n,m)+n\log U) where
T(n,m) is the complexity of solving the minimum s,t cut problem
on a graph with n nodes and m arcs. Furthermore, other
algorithms are shown to solve the problem with convex deviation
and convex separation in running time O(mn\log n\log nU) and the
problem
with nonconvex deviation and convex separation in running time
O(T(nU,mU).
The nonconvex separation problem is NP-hard even for fixed value
of U.
For the family of problems with convex deviation
functions and linear separation function, the algorithm described
here runs in polynomial time which is demonstrated
to be fastest possible.
Download Information
Click on the following title to view and download the paper in PostScript format.
- An efficient algorithm for image
segmentation, Markov Random Fields and related problems (17 pages, 260 KB)
- Dorit S. Hochbaum. Manuscript (2000), For published version see Journal
of the ACM Vol 48, No 2, July 2001 pp. 686 - 701.
hochbaum@ieor.berkeley.edu
7/30/01