IMAGE SEGMENTATION WITH ASTEROIDALITY/TUBULARITY AND SMOOTHNESS CONSTRAINTS
Danny Z. Chen, Jie Wang, Xiaodong Wu · International Journal of Computational Geometry & Applications · 2002
Image segmentation with specific constraints has found applications in several areas such as biomedical image analysis and data mining. In this paper, we study the problem of segmenting star-shaped and smooth objects in 2-D and tubular objects in 3-D images. Image objects of these shapes are often studied in medical applications. For the 2-D case of the problem, we present an O(IJ log J) time algorithm, improving the previously best known O(IJ2M) time algorithm by a factor of [Formula: see text] time, where the size of the input 2-D image is I × J and M is the smoothness parameter with 1 ≤ M ≤ J. Our 2-D algorithm is based on a combination of dynamic programming and divide-and-conquer strategy, and on computing an optimal path in an implicitly represented graph. We also prove that a generalized version of the 3-D case of the problem is NP-hard.