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

Publisher Website
Google Scholar
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 thedeviation costfunction 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---theimage segmentationproblem. 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 onnpixels or variables,madjacency relations or constraints, and range of variable values (colors)U, isO(T(n,m) +nlogU) whereT(n,m) is the complexity of solving the minimum s, t cut problem on a graph withnnodes andmarcs. Furthermore, other algorithms are shown to solve the problem with convex deviation and convex separation in running timeO(mnlognlognU) and the problem with nonconvex deviation and convex separation in running timeO(T(nU, mU). The nonconvex separation problem is NP-hard even for fixed value ofU.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.

This publication has 10 references indexed in Scilit: