تقسیم بندی تعاملی از برجستگی های شکل غیرستاره توسط برنامه ریزی پویا

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 [1], [2] and [3]. 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 [3], [4] and [5] 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 [6] is a simple and computationally inexpensive technique for interactive segmentation based on a set of seed points. The more sophisticated approach from [7] uses the seed pixels to estimate the labels of unlabeled pixels by learning on probabilistic hypergraphs. Intelligent scissors [8] allows a user to choose a minimum cost contour by roughly tracing the object's boundary with the mouse. Active contours or snakes [9] evolutionally improve a manually specified initial contour. The interactive graph cut algorithm [10] 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 [11] and the lazy snapping algorithm [12]. The work [13] extends the classical region growing to a maximal similarity based interactive segmentation. A linear programming approach is presented in [14]. Recently, a comparative evaluation of four interactive segmentation algorithms is reported in [15]. 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 [16] and [17]. 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 [18] and contains more algorithmic details and experimental validation. Full-size image (19 K) Fig. 1. Outline of the Rack algorithm.

We have developed an algorithm to combine dynamic programming with a user-driven image transformation. The Rack algorithm enables the user to successively specify and edit the underlying structure of the contour by means of a small number of points and solve the optimal contour problem efficiently (within O(|V|log|V|)O(|V|log|V|) time). The experimental results indicate its ability of combining an acceptable amount of user interaction with generally good segmentation results. An advantage of the Rack algorithm compared to boundary template based methods is that the object of interest can be sketched very roughly. While an approximation of the object border might be very tedious on complex contours, placing a rack somewhere more or less centered inside the object requires far less precision. As the border of most real objects has limited complexity while still being slightly non-star-shaped, a simple rack generally is both necessary and sufficient. As shown in Fig. 10, even in case of star-shaped shapes (of small kernel) our rack approach may be advantageous in terms of user friendliness compared to traditional dynamic programming. On the other hand, the Rack algorithm is not suited for very complex structures. Objects like tree branches would require a very detailed rack. Another drawback is that the user has no direct influence on the contour detection process, i.e. there is no mechanism to adjust single parts of the contour that do not match the user's expectation. There is room for further improvement. Currently, we simply apply the Sobel operator to calculate the image's edge strength. On complex images, the performance of the algorithm could be greatly improved by using preprocessing techniques like denoising or texture analysis. Another interesting idea would be to let the user construct the rack as a continuous stroke to receive a smoother ρρ function. This corresponds to a substantially larger number of points on the rack, but has no influence on the overall computational complexity of the Rack algorithm. In order to segment the desired object, a suitable rack has to be designed by the user or from some a priori knowledge. Useful is an automatic construction of a rack or at least improvement of an initial rack for the most prominent structure in the image.