Convexity and Other Shape priors for Single and Multiple Object Segmentation

Duration: 1 hour 2 mins

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/2628607/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Veksler, O (University of Western Ontario) Monday 11th December 2017 - 11:30 to 12:30


Created:	2017-12-14 13:06
Collection:	Variational methods and effective algorithms for imaging and vision
Publisher:	Isaac Newton Institute
Copyright:	Veksler, O
Language:	eng (English)


Abstract:	Shape is a useful regularization prior for image segmentation. First we will talk about convexity shape prior for single object segmentation. In the context of discrete optimization, object convexity is represented as a sum of 3-clique potentials penalizing any 1-0-1 configuration on all straight lines. We show that these nonsubmodular interactions can be efficiently optimized using a trust region approach. While the quadratic number of all 3-cliques is prohibitively high, we designed a dynamic programming technique for evaluating and approximating these cliques in linear time. Our experiments demonstrate general usefulness of the proposed convexity constraint on synthetic and real image segmentation examples. Unlike standard second order length regularization, our convexity prior is scale invariant, does not have shrinking bias, and is virtually parameter-free. Segmenting multiple objects with convex shape prior presents its own challenges as distinct objects interact in non-trivial manner. We extend our work on single convex object optimization by proposing a mutli-object convexity shape prior for multi-label image segmentation. Next we consider simple shape priors, i.e. priors that can be optimized exactly with a single graph cut in the context of single object segmentation. Segmenting multiple objects with such simple shape priors presents its own challenges. We propose a new class of energies for segmentation of multiple foreground objects with a common simple shape prior. Our energy involves infinity constraints. For such energies standard expansion algorithm has no optimality guarantees and in practice gets stuck in bad local minima. Therefore, we develop a new move making algorithm, we call double expansion. In contrast to expansion, the new move allows each pixel to choose a label from a pair of new labels or keep the old label. This results in an algorithm with optimality guarantees and robust performance in practice. We experiment with several types of shape prior such as star-shape, compactness and a novel symmetry prior, and empirically demonstrate the advantage of the double expansion.

Abstract:

Shape is a useful regularization prior for image segmentation. First we will talk about convexity shape prior for single object segmentation. In the context of discrete optimization, object convexity is represented as a sum of 3-clique potentials penalizing any 1-0-1 configuration on all straight lines. We show that these nonsubmodular interactions can be efficiently optimized using a trust region approach. While the quadratic number of all 3-cliques is prohibitively high, we designed a dynamic programming technique for evaluating and approximating these cliques in linear time. Our experiments demonstrate general usefulness of the proposed convexity constraint on synthetic and real image segmentation examples. Unlike standard second order length regularization, our convexity prior is scale invariant, does not have shrinking bias, and is virtually parameter-free. Segmenting multiple objects with convex shape prior presents its own challenges as distinct objects interact in non-trivial manner. We extend our work on single convex object optimization by proposing a mutli-object convexity shape prior for multi-label image segmentation. Next we consider simple shape priors, i.e. priors that can be optimized exactly with a single graph cut in the context of single object segmentation. Segmenting multiple objects with such simple shape priors presents its own challenges. We propose a new class of energies for segmentation of multiple foreground objects with a common simple shape prior. Our energy involves infinity constraints. For such energies standard expansion algorithm has no optimality guarantees and in practice gets stuck in bad local minima. Therefore, we develop a new move making algorithm, we call double expansion. In contrast to expansion, the new move allows each pixel to choose a label from a pair of new labels or keep the old label. This results in an algorithm with optimality guarantees and robust performance in practice. We experiment with several types of shape prior such as star-shape, compactness and a novel symmetry prior, and empirically demonstrate the advantage of the double expansion.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.97 Mbits/sec	916.39 MB	View	Download
WebM	640x360	577.58 kbits/sec	262.28 MB	View	Download
iPod Video	480x270	530.24 kbits/sec	240.78 MB	View	Download
MP3	44100 Hz	249.81 kbits/sec	115.27 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)