تقسیم بندی تعاملی از برجستگی های شکل غیرستاره توسط برنامه ریزی پویا
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|25726||2011||9 صفحه PDF||سفارش دهید||5885 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Pattern Recognition, Volume 44, Issue 9, September 2011, Pages 2008–2016
In this paper we present the Rack algorithm for the detection of optimal non-star-shaped contours in images. It is based on the combination of a user-driven image transformation and dynamic programming. The fundamental idea is to interactively specify and edit the general shape of the desired object by using a rack. This rack is used to model the image as a directed acyclic weighted graph that contains a path corresponding to the expected contour. In this graph, the shortest path with respect to an adequate cost function can be calculated efficiently via dynamic programming. The experimental results indicate the algorithm's ability of combining an acceptable amount of user interaction with generally good segmentation results.
Dynamic programming (DP) is a popular technique for contour segmentation due to its elegance and guarantee of optimality ,  and . However, the contours that can be handled by such techniques are limited to star-shaped only. Some approaches have been proposed to deal with more complex shapes ,  and  by means of increased human interaction or additional prior information. In this work we address the task with a new approach that will be called the Rack algorithm. The idea is to specify and edit the general shape of the desired object by using a rack; see Fig. 7. This rack is used to model the image as a directed acyclic graph (DAG) that contains a path corresponding to the expected contour. With the image's edge strength or whatever other suitable measures as graph weights, an optimal contour can be defined as the shortest path in the DAG with respect to some cost function, which can be globally minimized via dynamic programming. Our approach is in line with interactive image segmentation. Fully automated segmentation is known to be an ill-posed problem due to the fact that there is neither a clear definition nor an objective goodness measure of a semantic segment. The user intention is manifold and depends on applications. In order to perform a semantically meaningful segmentation, it is thus helpful to take a priori information about the objects into account. Interactive segmentation algorithms provide a solution by invoking the aid of a human operator to supply the high-level information needed to detect and extract semantic objects through a series of interactions. For instance, the user may mark (small) areas of the image as object or background and the algorithm updates the segmentation using the new information. By iteratively providing more interactions the user can refine the segmentation. The goal of interactive segmentation is thus to provide a means of extracting semantic objects from an image quickly and accurately. The early approach of seeded region growing  is a simple and computationally inexpensive technique for interactive segmentation based on a set of seed points. The more sophisticated approach from  uses the seed pixels to estimate the labels of unlabeled pixels by learning on probabilistic hypergraphs. Intelligent scissors  allows a user to choose a minimum cost contour by roughly tracing the object's boundary with the mouse. Active contours or snakes  evolutionally improve a manually specified initial contour. The interactive graph cut algorithm  formulates the interactive segmentation problem within a MAP-MRF framework, subsequently determining a globally optimal solution using a fast mincut/max-flow algorithm. Two further variants of this category are the GrabCut algorithm  and the lazy snapping algorithm . The work  extends the classical region growing to a maximal similarity based interactive segmentation. A linear programming approach is presented in . Recently, a comparative evaluation of four interactive segmentation algorithms is reported in . While these works are devoted to general object extraction from photographs and natural scenes, there are also application-specific demands and related developments. For instance, interactive segmentation methods are indispensable for biomedical image analysis  and . The remainder of this work is organized as follows. We discuss related works on DP-based contour detection in Section 2. In Section 3, we describe our algorithm according to the three steps shown in Fig. 1. The image is first modeled as an undirected graph and then turned into a DAG. As a third step, the shortest path is calculated in this DAG, which represents an optimal contour. The key issue of transforming the undirected graph into a DAG guided by a user-specified rack is tackled in Section 4. Experimental results are shown in Section 5. Finally, we conclude with a discussion in Section 6. This paper is an extended version of the conference version  and contains more algorithmic details and experimental validation. Full-size image (19 K) Fig. 1. Outline of the Rack algorithm.
نتیجه گیری انگلیسی