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.

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.

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.

We consider a class of region-based energies for image segmentation and inpainting which combine region integrals with curvature regularity of the region boundary. To minimize such energies, we formulate an integer linear program which jointly estimates regions and their boundaries. Curvature regularity is imposed by respective costs on pairs of adjacent boundary segments. By solving the associated linear programming relaxation and thresholding the solution one obtains an approximate solution to the original integer problem. To our knowledge this is the first approach to impose curvature regularity in region-based formulations in a manner that is independent of initialization and allows to compute a bound on the optimal energy. In a variety of experiments on segmentation and inpainting, we demonstrate the advantages of higher-order regularity. Moreover, we demonstrate that for most experiments the optimality gap is smaller than 2% of the global optimum. For many instances we are even able to compute the global optimum.

We propose a polynomial-time algorithm for segmentation and (open) boundary estimation which takes into account a series of user-specified attraction points. In contrast to existing algorithms which impose that the segmenting boundary passes through these points, our algorithm allows an imprecision in the user input. An energy minimization approach imposes that the segmenting boundary optimally passes along high-contrast edges in such a way that at least one point along the computed boundary is as close as possible to any given attraction point. In this sense, the user input can be seen as a soft constraint. We prove that the resulting optimization problem is NP-hard. We prove that in the case that the user attraction points are ordered, then optimal solutions can be computed in polynomial time using a shortest path formulation in an appropriately constructed four-dimensional graph spanned by the image pixels, a set of tangent angles and the user attraction points. Experimental results on a variety of images demonstrate that good quality segmentations can be obtained with a few imprecise user clicks.

We propose an efficient polynomial time algorithm to match an elastically deforming shape to an image. It is based on finding a globally optimal geodesic in the product space spanned by the image and the prior contour. To this end a branch-and-bound scheme is combined with shortest path techniques. We compare this algorithm with a recently proposed ratio minimization approach. While we show that generally the ratio is the better model, for many instances the two perform similarly. We identify a class of problems where the proposed method is likely to be faster. 1 Introduction and Related Work For decades researchers have striven to develop machine vision algorithms which can compete with or even outperform the human visual system. Despite many efforts this remains a challenging problem. The human visual system makes heavily use of prior world knowledge. As a consequence

We introduce a novel energy minimization method to decompose a video into a set of super-resolved moving layers. The proposed energy corresponds to the cost of coding the sequence. It consists of a data term and two terms imposing regularity of the geometry and the intensity of each layer. In contrast to existing motion layer methods, we perform graph cut optimization in the (dual) layer space to determine which layer is visible at which video position. In particular, we show how arising higher-order terms can be accounted for by a generalization of alpha expansions. Moreover, our model accurately captures long-term temporal consistency. To the best of our knowledge, this is the first work which aims at modeling details of the image formation process (such as camera blur and downsampling) in the context of motion layer decomposition. The experimental results demonstrate that energy minimization leads to a reconstruction of a video in terms of a superposition of multiple high-resolution motion layers.

Most algorithms for real-time tracking of deformable shapes provide sub-optimal solutions for a suitable energy minimization task: The search space is typically considered too large to allow for globally optimal solutions. In this paper we show that - under reasonable constraints on the object motion - one can guarantee global optimality while maintaining real-time requirements. The problem is cast as finding the optimal cycle in a graph spanned by the prior template and the image. The underlying combinatorial algorithm is implemented on state-of- the-art graphics hardware. Solutions on FPGAs are conceivable. Experimental results demonstrate long-term tracking of cars in real-time, while coping with challenging weather conditions. In particular, we show that the proposed tracking algorithm is highly robust to illumination changes and that it outperforms local tracking methods such as the level set method.

While global methods for matching shapes to images have recently been proposed, so far research has focused on small deformations of a fixed template. In this paper we present the first global method able to pixel-accurately match non-rigidly deformable shapes across images at amenable run-times. By finding cycles of optimal ratio in a four-dimensional graph - spanned by the image, the prior shape and a set of rotation angles - we simultaneously compute a segmentation of the image plane, a matching of points on the template to points on the segmenting boundary, and a decomposition of the template into a set of deformable parts. In particular, the interpretation of the shape template as a collection of an a priori unknown number of deformable parts - an important aspect of higher-level shape representations - emerges as a byproduct of our matching algorithm. On real-world data of running people and walking animals, we demonstrate that the proposed method can match strongly deformed shapes, even in cases where simple shape measures and optic flow methods fail.

So far global optimization techniques have been developed independently for the tasks of shape matching and image segmentation. In this paper we show that both tasks can in fact be solved simultaneously using global optimization. By computing cycles of minimal ratio in a large graph spanned by the product of the input image and a shape template, we are able to compute globally optimal segmentations of the image which are similar to a familiar shape and located in places of strong gradient. The presented approach is translation-invariant and robust to local and global scaling and rotation of the given shape. We show how it can be extended to incorporate invariance to similarity transformations. The particular structure of the graph allows for run-time and memory efficient implementations. Highly parallel implementations on graphics cards allow to produce globally optimal solutions in a few seconds only.

While the majority of competitive image segmentation methods are based on energy minimization, only few allow to efficiently determine globally optimal solutions. A graph-theoretic algorithm for finding globally optimal segmentations is given by the minimum ratio cycles, first applied to segmentation by Jermyn and Ishikawa (2001). In this paper we show that the class of image segmentation problems solvable by minimum ratio cycles is significantly larger than previously considered. In particular, they allow for the introduction of higher-order regularity of the region boundary. The key idea is to introduce an extended graph representation, where each node of the graph represents an image pixel as well as the orientation of the incoming line segment. With each graph edge representing a pair of adjacent line segments, edge weights can depend on the curvature. This way arbitrary positive functions of curvature can be introduced into globally optimal segmentation by minimum ratio cycles. In numerous experiments we demonstrate that compared to length-regularity the integration of curvature-regularity will drastically improve segmentation results. Moreover, we show an interesting relation to the snakes functional: minimum ratio cycles provide a way to find one of the few cases where the snakes functional has a meaningful global minimum.