### An efficient algorithm for image segmentation, Markov random fields and related problemsAn efficient algorithm for image segmentation, Markov random fields and related problems

Access Restriction
Subscribed

 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

Source: ACM Digital Library