A coding-cost framework for super-resolution motion layer decomposition.

We consider the problem of decomposing a video sequence into a superposition of (a given number of) moving layers. For this problem, we propose an energy minimization approach based on the coding cost. Our contributions affect both the model (what is minimized) and the algorithmic side (how it is minimized). The novelty of the coding-cost model is the inclusion of a refined model of the image formation process, known as super resolution. This accounts for camera blur and area averaging arising in a physically plausible image formation process. It allows us to extract sharp high-resolution layers from the video sequence. The algorithmic framework is based on an alternating minimization scheme and includes the following innovations. 1) A video labeling, we optimize the layer domains. This allows to regularize the shapes of the layers and a very elegant handling of occlusions. 2) We present an efficient parallel algorithm for extracting super-resolved layers based on TV filtering.

The elastic ratio: introducing curvature into ratio-based image segmentation.

We present the first ratio-based image segmentation method that allows imposing curvature regularity of the region boundary. Our approach is a generalization of the ratio framework pioneered by Jermyn and Ishikawa so as to allow penalty functions that take into account the local curvature of the curve. The key idea is to cast the segmentation problem as one of finding cyclic paths of minimal ratio in a graph where each graph node represents a line segment. Among ratios whose discrete counterparts can be globally minimized with our approach, we focus in particular on the elastic ratio [Formula: see text] that depends, given an image I, on the oriented boundary C of the segmented region candidate. Minimizing this ratio amounts to finding a curve, neither small nor too curvy, through which the brightness flux is maximal. We prove the existence of minimizers for this criterion among continuous curves with mild regularity assumptions. We also prove that the discrete minimizers provided by our graph-based algorithm converge, as the resolution increases, to continuous minimizers. In contrast to most existing segmentation methods with computable and meaningful, i.e., nondegenerate, global optima, the proposed approach is fully unsupervised in the sense that it does not require any kind of user input such as seed nodes. Numerical experiments demonstrate that curvature regularity allows substantial improvement of the quality of segmentations. Furthermore, our results allow drawing conclusions about global optima of a parameterization-independent version of the snakes functional: the proposed algorithm allows determining parameter values where the functional has a meaningful solution and simultaneously provides the corresponding global solution.

A combinatorial solution for model-based image segmentation and real-time tracking.

We propose a combinatorial solution to determine the optimal elastic matching of a deformable template to an image. The central idea is to cast the optimal matching of each template point to a corresponding image pixel as a problem of finding a minimum cost cyclic path in the three-dimensional product space spanned by the template and the input image. We introduce a cost functional associated with each cycle, which consists of three terms: a data fidelity term favoring strong intensity gradients, a shape consistency term favoring similarity of tangent angles of corresponding points, and an elastic penalty for stretching or shrinking. The functional is normalized with respect to the total length to avoid a bias toward shorter curves. Optimization is performed by Lawler's Minimum Ratio Cycle algorithm parallelized on state-of-the-art graphics cards. The algorithm provides the optimal segmentation and point correspondence between template and segmented curve in computation times that are essentially linear in the number of pixels. To the best of our knowledge, this is the only existing globally optimal algorithm for real-time tracking of deformable shapes.