Variational, Geometric, and Level Set Methods in Computer Vision

Frontmatter

A Study of Non-smooth Convex Flow Decomposition

Abstract

We present a mathematical and computational feasibility study of the variational convex decomposition of 2D vector fields into coherent structures and additively superposed flow textures. Such decompositions are of interest for the analysis of image sequences in experimental fluid dynamics and for highly non-rigid image flows in computer vision.

Our work extends current research on image decomposition into structural and textural parts in a twofold way. Firstly, based on Gauss’ integral theorem, we decompose flows into three components related to the flow’s divergence, curl, and the boundary flow. To this end, we use proper operator discretizations that yield exact analogs of the basic continuous relations of vector analysis. Secondly, we decompose simultaneously both the divergence and the curl component into respective structural and textural parts. We show that the variational problem to achieve this decomposition together with necessary compatibility constraints can be reliably solved using a single convex second-order conic program.

Jing Yuan, Christoph Schnörr, Gabriele Steidl, Florian Becker

Denoising Tensors via Lie Group Flows

Abstract

The need to regularize tensor fields arise recently in various applications. We treat in this paper tensors that belong to matrix Lie groups. We formulate the problem of these SO(N) flows in terms of the principal chiral model (PCM) action. This action is defined over a Lie group manifold. By minimizing the PCM action with respect to the group element, we obtain the equations of motion for the group element (or the corresponding connection). Then, by writing the gradient descent equations we obtain the PDE for the Lie group flows. We use these flows to regularize in particular the group of N-dimensional orthogonal matrices with determinant one i.e. SO(N). This type of regularization preserves their properties (i.e., the orthogonality and the determinant). A special numerical scheme that preserves the Lie group structure is used. However, these flows regularize the tensor field isotropically and therefore discontinuities are not preserved. We modify the functional and thereby the gradient descent PDEs in order to obtain an anisotropic tensor field regularization. We demonstrate our formalism with various examples.

Y. Gur, N. Sochen

Nonlinear Inverse Scale Space Methods for Image Restoration

Abstract

In this paper we generalize the iterated refinement method, introduced by the authors in [8],to a time-continuous inverse scale-space formulation. The iterated refinement procedure yields a sequence of convex variational problems, evolving toward the noisy image.

The inverse scale space method arises as a limit for a penalization parameter tending to zero, while the number of iteration steps tends to infinity. For the limiting flow, similar properties as for the iterated refinement procedure hold. Specifically, when a discrepancy principle is used as the stopping criterion, the error between the reconstruction and the noise-free image decreases until termination, even if only the noisy image is available and a bound on the variance of the noise is known.

The inverse flow is computed directly for one-dimensional signals, yielding high quality restorations. In higher spatial dimensions, we introduce a relaxation technique using two evolution equations. These equations allow accurate, efficient and straightforward implementation.

Martin Burger, Stanley Osher, Jinjun Xu, Guy Gilboa

Towards PDE-Based Image Compression

Abstract

While methods based on partial differential equations (PDEs) and variational techniques are powerful tools for denoising and inpainting digital images, their use for image compression was mainly focussing on pre- or postprocessing so far. In our paper we investigate their potential within the decoding step. We start with the observation that edge-enhancing diffusion (EED), an anisotropic nonlinear diffusion filter with a diffusion tensor, is well-suited for scattered data interpolation: Even when the interpolation data are very sparse, good results are obtained that respect discontinuities and satisfy a maximum–minimum principle. This property is exploited in our studies on PDE-based image compression. We use an adaptive triangulation method based on B-tree coding for removing less significant pixels from the image. The remaining points serve as scattered interpolation data for the EED process. They can be coded in a compact and elegant way that reflects the B-tree structure. Our experiments illustrate that for high compression rates and non-textured images, this PDE-based approach gives visually better results than the widely-used JPEG coding.

Irena Galić, Joachim Weickert, Martin Welk, Andrés Bruhn, Alexander Belyaev, Hans-Peter Seidel

Color Image Deblurring with Impulsive Noise

Abstract

We propose a variational approach for deblurring and impulsive noise removal in multi-channel images. A robust data fidelity measure and edge preserving regularization are employed. We consider several regularization approaches, such as Beltrami flow, Mumford-Shah and Total-Variation Mumford-Shah. The latter two methods are extended to multi-channel images and reformulated using the Γ-convergence approximation. Our main contribution is in the unification of image deblurring and impulse noise removal in a multi-channel variational framework. Theoretical and experimental results show that the Mumford-Shah and Total Variation Mumford Shah regularization methods are superior to other color image restoration regularizers. In addition, these two methods yield a denoised edge map of the image.

Leah Bar, Alexander Brook, Nir Sochen, Nahum Kiryati

Using an Oriented PDE to Repair Image Textures

Abstract

PDE-based image inpainting efficiently recovers structured features. We expand this to textures. We adjust the coordinates to proper directions, and embed in anisotropy terms the brightness correlation between pixels adjoining on the new grid. A simple elliptic equation then repairs both oriented textures and edges by one uniform, automated algorithm. Extensive experimental results on a variety of standard natural images show the technique’s generality and stability.

Yan Niu, Tim Poston

Image Cartoon-Texture Decomposition and Feature Selection Using the Total Variation Regularized L 1 Functional

Abstract

This paper studies the model of minimizing total variation with an L ¹-norm fidelity term for decomposing a real image into the sum of cartoon and texture. This model is also analyzed and shown to be able to select features of an image according to their scales.

Wotao Yin, Donald Goldfarb, Stanley Osher

Structure-Texture Decomposition by a TV-Gabor Model

Abstract

This paper explores new aspects of the image decomposition problem using modern variational techniques. We aim at splitting an original image f into two components u and v, where u holds the geometrical information and v holds the textural information. Our aim is to provide the necessary variational tools and suggest the suitable functional spaces to extract specific types of textures.

Our modeling uses the total-variation semi-norm for extracting the structural part and a new tunable norm, presented here for the first time, based on Gabor functions, for the textural part. A way to select the splitting parameter based on the orthogonality of structure and texture is also suggested.

Jean-François Aujol, Guy Gilboa, Tony Chan, Stanley Osher

From Inpainting to Active Contours

Abstract

We introduce a novel type of region based active contour using image inpainting. Usual region based active contours assume that the image is divided into several semantically meaningful regions and attempt to differentiate them through recovering dynamically statistical optimal parameters for each region. In case when perceptually distinct regions have similar intensity distributions, the methods mentioned above fail. In this work, we formulate the problem as optimizing a ”background disocclusion” criterion, a disocclusion that can be performed by inpainting. We look especially at a family of inpainting formulations that includes the Chan and Shen Total Variation Inpainting (more precisely a regularization of it). In this case, the optimization leads formally to a coupled contour evolution equation, an inpainting equation, as well as a linear PDE depending on the inpainting. The contour evolution is implemented in the framework of level sets. Finally, the proposed method is validated on various examples.

François Lauze, Mads Nielsen

Sobolev Active Contours

Abstract

All previous geometric active contour models that have been formulated as gradient flows of various energies use the same L ²-type inner product to define the notion of gradient. Recent work has shown that this inner product induces a pathological Riemannian metric on the space of smooth curves. However, there are also undesirable features associated with the gradient flows that this inner product induces. In this paper, we reformulate the generic geometric active contour model by redefining the notion of gradient in accordance with Sobolev-type inner products. We call the resulting flows Sobolev active contours. Sobolev metrics induce favorable regularity properties in their gradient flows. In addition, Sobolev active contours favor global translations, but are not restricted to such motions. This is particularly useful in tracking applications. We demonstrate the general methodology by reformulating some standard edge-based and region-based active contour models as Sobolev active contours and show the substantial improvements gained in segmentation and tracking applications.

Ganesh Sundaramoorthi, Anthony Yezzi, Andrea Mennucci

Advances in Variational Image Segmentation Using AM-FM Models: Regularized Demodulation and Probabilistic Cue Integration

Abstract

Current state-of-the-art methods in variational image segmentation using level set methods are able to robustly segment complex textured images in an unsupervised manner. In recent work, [18,19] we have explored the potential of AM-FM features for driving the unsupervised segmentation of a wide variety of textured images. Our first contribution in this work is at the feature extraction level, where we introduce a regularized approach to the demodulation of the AM-FM -modelled signals. By replacing the cascade of multiband filtering and subsequent differentiation with analytically derived equivalent filtering operations, increased noise-robustness can be achieved, while discretization problems in the implementation of the demodulation algorithm are alleviated. Our second contribution is based on a generative model we have recently proposed [18,20] that offers a measure related to the local prominence of a specific class of features, like edges and textures. The introduction of these measures as weighting terms in the evolution equations facilitates the fusion of different cues in a simple and efficient manner. Our systematic evaluation on the Berkeley segmentation benchmark demonstrates that this fusion method offers improved results when compared to our previous work as well as current state-of-the-art methods.

Georgios Evangelopoulos, Iasonas Kokkinos, Petros Maragos

Entropy Controlled Gauss-Markov Random Measure Field Models for Early Vision

Abstract

We present a computationally efficient segmentation–restoration method, based on a probabilistic formulation, for the joint estimation of the label map (segmentation) and the parameters of the feature generator models (restoration). Our algorithm computes an estimation of the posterior marginal probability distributions of the label field based on a Gauss Markov Random Measure Field model. Our proposal introduces an explicit entropy control for the estimated posterior marginals, therefore it improves the parameter estimation step. If the model parameters are given, our algorithm computes the posterior marginals as the global minimizers of a quadratic, linearly constrained energy function; therefore, one can compute very efficiently the optimal (Maximizer of the Posterior Marginals or MPM) estimator for multi–class segmentation problems. Moreover, a good estimation of the posterior marginals allows one to compute estimators different from the MPM for restoration problems, denoising and optical flow computation. Experiments demonstrate better performance over other state of the art segmentation approaches.

Mariano Rivera, Omar Ocegueda, Jose L. Marroquin

Global Minimization of the Active Contour Model with TV-Inpainting and Two-Phase Denoising

Abstract

The active contour model [8,9,2] is one of the most well-known variational methods in image segmentation. In a recent paper by Bresson et al. [1], a link between the active contour model and the variational denoising model of Rudin-Osher-Fatemi (ROF) [10] was demonstrated. This relation provides a method to determine the global minimizer of the active contour model. In this paper, we propose a variation of this method to determine the global minimizer of the active contour model in the case when there are missing regions in the observed image. The idea is to turn off the L ¹-fidelity term in some subdomains, in particular the regions for image inpainting. Minimizing this energy provides a unified way to perform image denoising, segmentation and inpainting.

Shingyu Leung, Stanley Osher

Combined Geometric-Texture Image Classification

Abstract

In this paper, we propose a framework to carry out supervised classification of images containing both textured and non textured areas. Our approach is based on active contours. Using a decomposition algorithm inspired by the recent work of Y. Meyer, we can get two channels from the original image to classify: one containing the geometrical information, and the other the texture. Using the logic framework by Chan and Sandberg, we can then combine the information from both channels in a user definable way. Thus, we design a classification algorithm in which the different classes are characterized both from geometrical and textured features. Moreover, the user can choose different ways to combine information.

Jean-François Aujol, Tony Chan

Heuristically Driven Front Propagation for Geodesic Paths Extraction

Abstract

In this paper we present a simple modification of the Fast Marching algorithm to speed up the computation using a heuristic. This modification leads to an algorithm that is similar in spirit to the A^* algorithm used in artificial intelligence. Using a heuristic allows to extract geodesics from a single source to a single goal very quickly and with a low memory requirement. Any application that needs to compute a lot of geodesic paths can gain benefits from our algorithm. The computational saving is even more important for 3D medical images with tubular structures and for higher dimensional data.

Gabriel Peyré, Laurent Cohen

Trimap Segmentation for Fast and User-Friendly Alpha Matting

Abstract

Given an image, digital matting consists in extracting a foreground element from the background. Standard methods are initialized with a trimap, a partition of the image into three regions: a definite foreground, a definite background, and a blended region where pixels are considered as a mixture of foreground and background colors. Recovering these colors and the proportion of mixture between both is an under-constrained inverse problem, sensitive to its initialization: one has to specify an accurate trimap, leaving undetermined as few pixels as possible.

First, we propose a new segmentation scheme to extract an accurate trimap from just a coarse indication of some background and/or foreground pixels. Standard statistical models are used for the foreground and the background, while a specific one is designed for the blended region. The segmentation of the three regions is conducted simultaneously by an iterative Graph Cut based optimization scheme. This user-friendly trimap is similar to carefully hand specified ones.

As a second step, we take advantage of our blended region model to design an improved matting method coherent. Based on global statistics rather than on local ones, our method is much faster than standard Bayesian matting, without quality loss, and also usable with manual trimaps.

Olivier Juan, Renaud Keriven

Uncertainty-Driven Non-parametric Knowledge-Based Segmentation: The Corpus Callosum Case

Abstract

In this paper we propose a novel variational technique for the knowledge based segmentation of two dimensional objects. One of the elements of our approach is the use of higher order implicit polynomials to represent shapes. The most important contribution is the estimation of uncertainties on the registered shapes, which can be used with a variable bandwidth kernel-based non-parametric density estimation process to model prior knowledge about the object of interest. Such a non-linear model with uncertainty measures is integrated with an adaptive visual-driven data term that aims to separate the object of interest from the background. Promising results obtained for the segmentation of the corpus callosum in MR mid-sagittal brain slices demonstrate the potential of such a framework.

Maxime Taron, Nikos Paragios, Marie-Pierre Jolly

Dynamical Statistical Shape Priors for Level Set Based Sequence Segmentation

Abstract

In recent years, researchers have proposed to introduce statistical shape knowledge into the level set method in order to cope with insufficient low-level information. While these priors were shown to drastically improve the segmentation of images or image sequences, so far the focus has been on statistical shape priors that are time-invariant. Yet, in the context of tracking deformable objects, it is clear that certain silhouettes may become more or less likely over time. In this paper, we tackle the challenge of learning dynamical statistical models for implicitly represented shapes. We show how these can be integrated into a segmentation process in a Bayesian framework for image sequence segmentation. Experiments demonstrate that such shape priors with memory can drastically improve the segmentation of image sequences.

Daniel Cremers, Gareth Funka-Lea

Non-rigid Shape Comparison of Implicitly-Defined Curves

Abstract

We present a novel variational model to find shape-based correspondences between two sets of level curves. While the usual correspondence techniques work with parametrized curves, we use a level-set formulation that enables us to handle curves with arbitrary topology. Given the functions \(\Phi_{1}: (\Omega_{1} \subseteq IR^{2}) \longrightarrow IR\) and \(\Phi_{2}: (\Omega_{2} \subseteq IR^{2}) \longrightarrow IR\) whose 0-level curves we want to match, we search for a diffeomorphism that minimizes the rate of change of the difference in tangential orientation of the zero-level sets. To make the formulation symmetric and to simplify computations, we map the domains of the level-set functions Φ _i to a common domain Ω by initial diffeomorphisms that are chosen arbitrarily. We then search for diffeomorphisms from Ω to itself, generating them by flows of certain vector fields on Ω. The resulting correspondences are scale- and rotation-invariant with respect to the curves. We show how this model can be used as a basis to compare curves of different topology. The model was tested on synthetic and MRI cardiac data,with good results.

Sheshadri R. Thiruvenkadam, David Groisser, Yunmei Chen

Incorporating Rigid Structures in Non-rigid Registration Using Triangular B-Splines

Abstract

For non-rigid registration, the objects in medical images are usually treated as a single deformable body with homogeneous stiffness distribution. However, this assumption is invalid for certain parts of the human body, where bony structures move rigidly, while the others may deform. In this paper, we introduce a novel registration technique that models local rigidity of pre-identified rigid structures as well as global non-rigidity in the transformation field using triangular B-splines. In contrast to the conventional registration method based on tensor-product B-splines, our approach recovers local rigid transformation with fewer degrees of freedom (DOFs), and accurately simulates sharp features (C ⁰ continuity) along the interface between deformable regions and rigid structures, because of the unique advantages offered by triangular B-splines, such as flexible triangular domain, local control and space-varying smoothness modeling. The accurate matching of the source image with the target one is accomplished through the use of a variational framework, in which a composite energy, measuring the image dissimilarity and enforcing local rigidity and global smoothness, is minimized subject to pre-defined point-based constraints. The algorithm is tested on both synthetic and real 2D images for its applicability. The experimental results show that, by accurately modeling sharp features using triangular B-splines, the deformable regions in the vicinity of rigid structures are less constrained by the global smoothness regularization and therefore contribute extra flexibility to the optimization process. Consequently, the registration quality is improved considerably.

Kexiang Wang, Ying He, Hong Qin

Geodesic Image Interpolation: Parameterizing and Interpolating Spatiotemporal Images

Abstract

We develop a practical, symmetric, data-driven formulation, geodesic image interpolation (GII), for interpolating images with respect to geometric and photometric variables. GII captures, in implementation, the desirable properties of symmetry that comes from the theory of diffeomorphisms and Grenander’s computational anatomy (CA). Geodesic diffeomorphisms are a desirable transformation model as they provide a symmetric deforming path connecting images or a series of images. Once estimated, this geodesic may be used to (re)parameterize and interpolate image sets in approximation of continuous, deforming dynamic processes. One may then closely recover the original continuous signal from a few samples. The method, based on our work in symmetric diffeomorphic image registration, generalizes the concept of point set reparameterization to the case where point sets are replaced by image sets. This problem differs from point reparameterization in that a variational image correspondence problem must be solved before resampling. Our image reparameterization method is applied to solve similar problems to point reparameterization: dense interpolation, matching and simulation of dynamic processes are illustrated.

Brian B. Avants, C. L. Epstein, J. C. Gee

A Variational Approach for Object Contour Tracking

Abstract

In this paper we describe a new framework for the tracking of closed curves described through implicit surface modeling. The approach proposed here enables a continuous tracking along an image sequence of deformable object contours. Such an approach is formalized through the minimization of a global spatio-temporal continuous cost functional stemming from a Bayesian Maximum a posteriori estimation of a Gaussian probability distribution. The resulting minimization sequence consists in a forward integration of an evolution law followed by a backward integration of an adjoint evolution model. This latter pde include also a term related to the discrepancy between the curve evolution law and a noisy observation of the curve. The efficiency of the approach is demonstrated on image sequences showing deformable objects of different natures.

Nicolas Papadakis, Etienne Mémin, Frédéric Cao

Implicit Free-Form-Deformations for Multi-frame Segmentation and Tracking

Abstract

In this paper, we propose a novel technique to address motion estimation and tracking. Such technique represents the motion field using a regular grid of thin-plate splines, and the moving objects using an implicit function on the image plane that is a cubic interpolation of a ”level set function” defined on this grid. Optical flow is determined through the deformation of the grid and consequently of the underlying image structures towards satisfying the constant brightness constraint. Tracking is performed in similar fashion through the consistent recovery in the temporal domain of the zero iso-surfaces of a level set that is the projection of the Free Form Deformation (FFD) implicit function according to the cubic spline formulation. Such an approach is a compromise between dense motion estimation and parametric motion models, introduces smoothness in an implicit fashion, is intrinsic, and can cope with important object deformations. Promising results demonstrate the potentials of our approach.

Konstantinos Karantzalos, Nikos Paragios

A Surface Reconstruction Method for Highly Noisy Point Clouds

Abstract

In this paper we propose a surface reconstruction method for highly noisy and non-uniform data based on minimal surface model and tensor voting method. To deal with ill-posedness, noise and/or other uncertainties in the data we processes the raw data first using tensor voting before we do surface reconstruction. The tensor voting procedure allows more global and robust communications among the data to extract coherent geometric features and saliency independent of the surface reconstruction. These extracted information will be used to preprocess the data and to guide the final surface reconstruction. Numerically the level set method is used for surface reconstruction. Our method can handle complicated topology as well as highly noisy and/or non-uniform data set. Moreover, improvements of efficiency in implementing the tensor voting method are also proposed. We demonstrate the ability of our method using synthetic and real data.

DanFeng Lu, HongKai Zhao, Ming Jiang, ShuLin Zhou, Tie Zhou

A C 1 Globally Interpolatory Spline of Arbitrary Topology

Abstract

Converting point samples and/or triangular meshes to a more compact spline representation for arbitrarily topology is both desirable and necessary for computer vision and computer graphics. This paper presents a C ¹ manifold interpolatory spline that can exactly pass through all the vertices and interpolate their normals for data input of complicated topological type. Starting from the Powell-Sabin spline as a building block, we integrate the concepts of global parametrization, affine atlas, and splines defined over local, open domains to arrive at an elegant, easy-to-use spline solution for complicated datasets. The proposed global spline scheme enables the rapid surface reconstruction and facilitates the shape editing and analysis functionality.

Ying He, Miao Jin, Xianfeng Gu, Hong Qin

Solving PDEs on Manifolds with Global Conformal Parametriazation

Abstract

In this paper, we propose a method to solve PDEs on surfaces with arbitrary topologies by using the global conformal parametrization. The main idea of this method is to map the surface conformally to 2D rectangular areas and then transform the PDE on the 3D surface into a modified PDE on the 2D parameter domain. Consequently, we can solve the PDE on the parameter domain by using some well-known numerical schemes on ℝ². To do this, we have to define a new set of differential operators on the manifold such that they are coordinates invariant. Since the Jacobian of the conformal mapping is simply a multiplication of the conformal factor, the modified PDE on the parameter domain will be very simple and easy to solve. In our experiments, we demonstrated our idea by solving the Navier-Stoke’s equation on the surface. We also applied our method to some image processing problems such as segmentation, image denoising and image inpainting on the surfaces.

Lok Ming Lui, Yalin Wang, Tony F. Chan

Fast Marching Method for Generic Shape from Shading

Abstract

We develop a fast numerical method to approximate the solutions of a wide class of equations associated to the Shape From Shading problem. Our method, which is based on the control theory and the interfaces propagation, is an extension of the “Fast Marching Method” (FMM) [30,25]. In particular our method extends the FMM to some equations for which the solution is not systematically decreasing along the optimal trajectories. We apply with success our one-pass method to the Shape From Shading equations which are involved by the most relevant and recent modelings [22,21] and which cannot be handled by the most recent extensions of the FMM [26,8].

Emmanuel Prados, Stefano Soatto

A Gradient Descent Procedure for Variational Dynamic Surface Problems with Constraints

Abstract

Many problems in image analysis and computer vision involving boundaries and regions can be cast in a variational formulation. This means that m-surfaces, e.g. curves and surfaces, are determined as minimizers of functionals using e.g. the variational level set method. In this paper we consider such variational problems with constraints given by functionals. We use the geometric interpretation of gradients for functionals to construct gradient descent evolutions for these constrained problems. The result is a generalization of the standard gradient projection method to an infinite-dimensional level set framework. The method is illustrated with examples and the results are valid for surfaces of any dimension.

Jan Erik Solem, Niels Chr. Overgaard

Regularization of Mappings Between Implicit Manifolds of Arbitrary Dimension and Codimension

Abstract

We study in this paper the problem of regularization of mappings between manifolds of arbitrary dimension and codimension using variational methods. This is of interest in various applications such as diffusion tensor imaging and EEG processing on the cortex. We consider the cases where the source and target manifold are represented implicitly, using multiple level set functions, or explicitly, as functions of the spatial coordinates. We derive the general implicit differential operators, and show how they can be used to generalize previous results concerning the Beltrami flow and other similar flows.

As examples, We show how these results can be used to regularize gray level and color images on manifolds, and to regularize tangent vector fields and direction fields on manifolds.

David Shafrir, Nir A. Sochen, Rachid Deriche

Lens Distortion Calibration Using Level Sets

Abstract

This paper addresses the problem of calibrating camera lens distortion, which can be significant in medium to wide-angle lenses. Our approach is based on the analysis of distorted images of straight lines. We use a PDE-based level set method to find the lens distortion parameters that straighten these lines. One advantage of this method is that it integrates the extraction of image distorted lines and the computation of distortion parameters within one energy functional which is minimized during level set evolution. Some experiments to evaluate the performance of this approach are reported.

Moumen T. El-Melegy, Nagi H. Al-Ashwal

Backmatter