Access Restriction

Author Hochbaum, Dorit S.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Convex optimization ♦ Markov random fields ♦ Parametric minimum cut ♦ Strongly polynomial algorithms
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 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 "e;few"e; means a number exponential in a polynomial function of the number of variables and constraints). The complexity of the algorithm for a problem on $\textit{n}$ pixels or variables, $\textit{m}$ adjacency relations or constraints, and range of variable values (colors) $\textit{U},$ is $\textit{O}(\textit{T}(\textit{n,m})$ + $\textit{n}$ log $\textit{U})$ where $\textit{T}(\textit{n,m})$ is the complexity of solving the minimum s, t cut problem on a graph with $\textit{n}$ nodes and $\textit{m}$ arcs. Furthermore, other algorithms are shown to solve the problem with convex deviation and convex separation in running time $\textit{O}(\textit{mn}$ log $\textit{n}$ log $\textit{nU})$ and the problem with nonconvex deviation and convex separation in running time $\textit{O}(\textit{T}(\textit{nU,$ mU). The nonconvex separation problem is NP-hard even for fixed value of $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2001-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 48
Issue Number 4
Page Count 16
Starting Page 686
Ending Page 701

Open content in new tab

   Open content in new tab
Source: ACM Digital Library