Efficient Algorithms for Optimization-based Image Segmentation

概要

論文の詳細を見る
Separating an object in an image from its background is a central problem (called segmentation) in pattern recognition and computer vision. In this paper, we study the complexity of the segmentation problem, assuming that the object forms a connected region in an intensity image. We show that the optimization problem of separating a connected region in an n-pixel grid is NP-hard under the interclass variance, a criterion that is used in discriminant analysis. More importantly, we consider the basic case in which the object is separated by two x-monotone curves (i.e., the object itself is x-monotone), and present polynomial-time algorithms for computing exact and approximate optimal segmentation. Our main algorithm for exact optimal segmentation by two x-monotone curves runs in O(n^2) time; this algorithm is based on several techniques such as a parametric optimization formulation, a hand-probing algorithm for the convex hull of an unknown point set, and dynamic programming using fast matrix searching. Our efficient approximation scheme obtains an ε-approximate solution in O(ε^<-1>n log L) time, whereεis any fixed constant with 1>ε>0, and L is the total sum of the absolute values of brightness levels of the image.
World Scientific Publishingの論文
2001-04-00