We present a novel primal-dual analysis on a class of NP-hard sparsity minimization problems to provide new interpretations for their well known convex relaxations. We show that the Lagrangian bidual (i.e., the Lagrangian dual of the Lagrangian dual) of the sparsity minimization problems can be used to derive interesting convex relaxations: the bidual of the ℓ0-minimization problem is ℓ1-minimization; and the bidual of ℓ0,1-minimization for enforcing group sparsity on structured data is ℓ1,∞-minimization problem. Intuitions from the bidual-based relaxation are used to introduce a new family of relaxations for the group sparsity minimization problem.

We propose to bridge the gap between Random Field (RF) formulations for joint categorization and segmentation (JCaS), which model local interactions among pixels and superpixels, and Bag of Features categorization algorithms, which use global descriptors. For this purpose, we introduce new higher order potentials that encode the classification cost of a histogram extracted from all the objects in an image that belong to a particular category, where the cost is given as the output of a classifier when applied to the histogram. The potentials efficiently encode the classification costs of several histograms resulting from the different possible segmentations of an image. They can be integrated with existing potentials, hence providing a natural unification of global and local interactions. The potentials' parameters can be treated as parameters of the RF and hence be jointly learnt along with the other parameters of the RF. Experiments show that our framework can be used to improve the performance of existing JCaS algorithms.

Image matting deals with the estimation of the alpha matte at each pixel, i.e., the contribution of the foreground and background objects to the composition of the image at that pixel. Existing methods for image matting are typically limited to estimating the alpha mattes for two image layers only. However, in several applications one is interested in editing images with multiple objects. In this work, we consider the problem of estimating the alpha mattes of multiple (n ≥ 2) image layers. We show that this problem can be decomposed into n simpler subproblems of alpha matte estimation for two image layers. Moreover, we show that, by construction, the estimated alpha mattes at each pixel are constrained to sum up to 1 across the multiple image layers. A key feature of our framework is that the alpha mattes can be estimated in closed form. We further show that, due to the nature of spatial regularization used in the estimation, the final estimated alpha mattes are not constrained to take values in [0, 1]. Hence, we study the optimization problem of estimating the alpha mattes for multiple image layers subject to the fact that the alpha mattes are nonnegative and sum up to 1 at each pixel. We present experiments to show that our proposed method can be used to extract mattes of multiple image layers.

Interactive image segmentation traditionally involves the use of algorithms such as graph cuts or random walker. Common concerns with using graph cuts are metrication artifacts (blockiness) and the shrinking bias (bias towards shorter boundaries). The random walker avoids these problems, but suffers from the proximity bias (sensitivity to location of pixels labeled by the user). In this work, we introduce a new family of segmentation algorithms that includes graph cuts and random walker as special cases. We explore image segmentation using continuous-valued Markov random fields (MRFs) with probability distributions following the p-norm of the difference between configurations of neighboring sites. For p=1 these MRFs may be interpreted as the standard binary MRF used by graph cuts, while for p=2 these MRFs may be viewed as Gaussian MRFs employed by the random walker algorithm. By allowing the probability distribution for neighboring sites to take any arbitrary p-norm (p ≥ 1), we pave the path for hybrid extensions of these algorithms. Experiments show that the use of a fractional p (1 <; p <; 2) can be used to resolve the aforementioned drawbacks of these algorithms.

Image matting is the task of estimating a fore- and background layer from a single image. To solve this ill posed problem, an accurate modeling of the scene's appearance is necessary. Existing methods that provide a closed form solution to this problem, assume that the colors of the foreground and background layers are locally linear. In this paper, we show that such models can be an overfit when the colors of the two layers are locally constant. We derive new closed form expressions in such cases, and show that our models are more compact than existing ones. In particular, the null space of our cost function is a subset of the null space constructed by existing approaches. We discuss the bias towards specific solutions for each formulation. Experiments on synthetic and real data confirm that our compact models estimate alpha mattes more accurately than existing techniques, without the need of additional user interaction.

We propose a scheme to introduce directionality in the random walker algorithm for image segmentation. In particular, we extend the optimization framework of this algorithm to combinatorial graphs with directed edges. Our scheme is interactive and requires the user to label a few pixels that are representative of a foreground object and of the background. These labeled pixels are used to learn intensity models for the object and the background, which allow us to automatically set the weights of the directed edges. These weights are chosen so that they bias the direction of the object boundary gradients to flow from regions that agree well with the learned object intensity model to regions that do not agree well. We use these weights to define an energy function that associates asymmetric quadratic penalties with the edges in the graph. We show that this energy function is convex, hence it has a unique minimizer. We propose a provably convergent iterative algorithm for minimizing this energy function. We also describe the construction of an equivalent electrical network with diodes and resistors that solves the same segmentation problem as our framework. Finally, our experiments on a database of 69 images show that the use of directional information does improve the segmenting power of the random Walker algorithm.

Image matting deals with finding the probability that each pixel in an image belongs to a user specified dasiaobjectpsila or to the remaining dasiabackgroundpsila. Most existing methods estimate the mattes for two groups only. Moreover, most of these methods estimate the mattes with a particular bias towards the object and hence the resulting mattes do not sum up to 1 across the different groups. In this work, we propose a general framework to estimate the alpha mattes for multiple image layers. The mattes are estimated as the solution to the Dirichlet problem on a combinatorial graph with boundary conditions. We consider the constrained optimization problem that enforces the alpha mattes to take values in [0; 1] and sum up to 1 at each pixel. We also analyze the properties of the solution obtained by relaxing either of the two constraints. Experiments demonstrate that our proposed method can be used to extract accurate mattes of multiple objects with little user interaction.

Given point correspondences in multiple perspective views of a scene containing multiple rigid-body motions, we present an algorithm for segmenting the correspondences according to the multiple motions. We exploit the fact that when the depths of the points are known, the point trajectories associated with a single motion live in a subspace of dimension at most four. Thus motion segmentation with known depths can be achieved by methods of subspace separation, such as GPCA or LSA. When the depths are unknown, we proceed iteratively. Given the segmentation, we compute the depths using standard techniques. Given the depths, we use GPCA or LSA to segment the scene into multiple motions. Experiments on the Hopkins 155 motion segmentation database show that our method compares favorably against existing affine motion segmentation methods in terms of segmentation error and execution time.

We present a closed form solution to the problem of segmenting multiple 2D motion models of the same type directly from the partial derivatives of an image sequence. We introduce the multibody brightness constancy constraint (MBCC), a polynomial equation relating motion models, image derivatives and pixel coordinates that is independent of the segmentation of the image measurements. We first show that the optical flow at a pixel can be obtained analytically as the derivative of the MBCC at the corresponding image measurement, without knowing the motion model associated with that pixel. We then show that the parameters of the multiple motion models can be obtained from the cross products of the derivatives of the MBCC at a set of image measurements that minimize a suitable distance function. Our approach requires no feature tracking, point correspondences or optical flow, and provides a global non-iterative solution that can be used to initialize more expensive iterative approaches to motion segmentation. Experiments on real and synthetic sequences are also presented.