We propose a geometric convexity shape prior preservation method for variational level set based image segmentation methods. Our method is built upon the fact that the level set of a convex signed distanced function must be convex. This property enables us to transfer a complicated geometrical convexity prior into a simple inequality constraint on the function. An active set based Gauss-Seidel iteration is used to handle this constrained minimization problem to get an efficient algorithm. We apply our method to region and edge based level set segmentation models including Chan-Vese (CV) model with guarantee that the segmented region will be convex. Experimental results show the effectiveness and quality of the proposed model and algorithm.
Gorelick @cite_30 introduced a convexity constraint based on graph theory. In their work, the convexity of objects can be represented as a sum of 3-clique potentials by penalizing any 1-0-1 configuration on all straight lines. Here the label 1 denotes the object, the label 0 denotes the background in an image, with details below.
@cite_30
2328822572 2166602562 2079914085 2168555635
Convexity is a known important cue in human vision. We propose shape convexity as a new high-order regularization constraint for binary image segmentation. In the context of discrete optimization, object convexity is represented as a sum of three-clique potentials penalizing any @math - @math - @math configuration on all straight lines. We show that these non-submodular potentials can be efficiently optimized using an iterative trust region approach. At each iteration the energy is linearly approximated and globally optimized within a small trust region around the current solution. While the quadratic number of all three-cliques is prohibitively high, we design a dynamic programming technique for evaluating and approximating these cliques in linear time. We also derive a second order approximation model that is more accurate but computationally intensive. We discuss limitations of our local optimization and propose gradual non-submodularization scheme that alleviates some limitations. Our experiments demonstrate general usefulness of the proposed convexity shape prior on synthetic and real image segmentation examples. Unlike standard second-order length regularization, our convexity prior does not have shrinking bias, and is robust to changes in scale and parameter selection. We consider the following probabilistic model of a graph on n labeled vertices. First choose a random graph G(n, 1 2), and then choose randomly a subset Q of vertices of size k and force it to be a clique by joining every pair of vertices of Q by an edge. The problem is to give a polynomial time algorithm for finding this hidden clique almost surely for various values of k. This question was posed independently, in various variants, by Jerrum and by Kucera. In this paper we present an efficient algorithm for all k>cn0.5, for any fixed c>0, thus improving the trivial case k>cn0.5(log n)0.5. The algorithm is based on the spectral properties of the graph. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13: 457–466, 1998 Many collective labeling tasks require inference on graphical models where the clique potentials depend only on the number of nodes that get a particular label. We design efficient inference algorithms for various families of such potentials. Our algorithms are exact for arbitrary cardinality-based clique potentials on binary labels and for max-like and majority-like clique potentials on multiple labels. Moving towards more complex potentials, we show that inference becomes NP-hard even on cliques with homogeneous Potts potentials. We present a 13 15-approximation algorithm with runtime sub-quadratic in the clique size. In contrast, the best known previous guarantee for graphs with Potts potentials is only 0.5. We perform empirical comparisons on real and synthetic data, and show that our proposed methods are an order of magnitude faster than the well-known Tree-based re-parameterization (TRW) and graph-cut algorithms. In this paper we introduce a new shape constraint for interactive image segmentation. It is an extension of Veksler's [25] star-convexity prior, in two ways: from a single star to multiple stars and from Euclidean rays to Geodesic paths. Global minima of the energy function are obtained subject to these new constraints. We also introduce Geodesic Forests, which exploit the structure of shortest paths in implementing the extended constraints. The star-convexity prior is used here in an interactive setting and this is demonstrated in a practical system. The system is evaluated by means of a “robot user” to measure the amount of interaction required in a precise way. We also introduce a new and harder dataset which augments the existing Grabcut dataset [1] with images and ground truth taken from the PASCAL VOC segmentation challenge [7].