Energy Minimization Methods in Computer Vision and Pattern Recognition

The efficient definition of the tumor area is crucial in brain tumor resection planning. But current methods embedded in computer aided diagnosis systems can be time consuming, while the initialization of the segmentation mask may be possible. In this work, we develop a method for rapid automated segmentation of brain tumors.

The main contribution of our work is an efficient method to initialize the segmentation by casting it as nonparametric density mode estimation, and developing a Branch and Bound-based method to efficiently find the mode (maximum) of the density function. Our technique is exact, has guaranteed convergence to the global optimum, and scales logarithmically in the volume dimensions by virtue of recursively subdividing the search space through Branch-and-Bound and Dual-Tress data structures.

This estimated mode provides our system with an initial tumor hypothesis which is then refined by graph-cuts to provide a sharper outline of the tumor area.

We demonstrate a 12-fold acceleration with respect to a standard mean-shift implementation, allowing us to accelerate tumor detection to a level that would facilitate a high-degree brain tumor resection planning.

It is of great interest in image-guided prostate interventions and diagnosis of prostate cancer to accurately and efficiently delineate the boundaries of prostate, especially its two clinically meaningful sub-regions/zones of the central gland (CZ) and the peripheral zone (PZ), in the given magnetic resonance (MR) images. We propose a novel coupled level-sets/contours evolution approach to simultaneously locating the prostate region and its two sub-regions, which properly introduces the recently developed convex relaxation technique to jointly evolve two coupled level-sets in a global optimization manner. Especially, in contrast to the classical level-set methods, we demonstrate that the two coupled level-sets can be simultaneously moved to their globally optimal positions at each discrete time-frame while preserving the spatial inter-surface consistency; we study the resulting complicated combinatorial optimization problem at each discrete time evolution by means of convex relaxation and show its global and exact optimality, for which we introduce the novel coupled continuous max-flow model and demonstrate its duality to the investigated convex relaxed optimization problem with the region constraint. The proposed coupled continuous max-flow model naturally leads to a new and efficient algorithm, which enjoys great advantages in numerics and can be readily implemented on GPUs. Experiments over 10 T2-weighted 3D prostate MRIs, by inter- and intra-operator variability, demonstrate the promising performance of the proposed approach.

Osmosis is a transport phenomenon that is omnipresent in nature. It differs from diffusion by the fact that it allows nonconstant steady states. In our paper we lay the foundations of osmosis filtering for visual computing applications. We model filters with osmotic properties by means of linear drift-diffusion processes. They preserve the average grey value and the nonnegativity of the initial image. Most interestingly, however, we show how the nonconstant steady state of an osmosis evolution can be steered by its drift vector field. We interpret this behaviour as a data integration mechanism. In the integrable case, we characterise the steady state as a minimiser of a suitable energy functional. In the nonintegrable case, we can exploit osmosis as a framework to fuse incompatible data in a visually convincing way. Osmotic data fusion differs from gradient domain methods by its intrinsic invariance under multiplicative grey scale changes. The osmosis framework constitutes a novel class of methods that can be taylored to solve various problems in image processing, computer vision, and computer graphics. We demonstrate its versatility by proposing osmosis models for compact image respresentation, shadow removal, and seamless image cloning.

Blind deconvolution involves the estimation of a sharp signal or image given only a blurry observation. Because this problem is fundamentally ill-posed, strong priors on both the sharp image and blur kernel are required to regularize the solution space. While this naturally leads to a standard MAP estimation framework, performance is compromised by unknown trade-off parameter settings, optimization heuristics, and convergence issues stemming from non-convexity and/or poor prior selections. To mitigate these problems, several authors have recently proposed substituting a variational Bayesian (VB) strategy that marginalizes over the high-dimensional image space leading to better estimates of the blur kernel. However, the underlying cost function now involves both integrals with no closed-form solution and complex, function-valued arguments, thus losing the transparency of MAP. To elucidate these issues, we demonstrate that the VB methodology can be recast as an unconventional MAP problem with a very particular penalty/prior that couples the image, blur kernel, and noise level in a principled way. This unique penalty has a number of useful characteristics pertaining to relative concavity, local minima avoidance, and scale-invariance that allow us to rigorously explain the success of VB including its existing implementational heuristics and approximations. It also provides strict criteria for choosing the optimal image prior that, perhaps counter-intuitively, need not reflect the statistics of natural scenes. In so doing we challenge the prevailing notion of why VB is successful for blind deconvolution while providing a transparent platform for introducing enhancements and extensions.

Traditionally, bit-depth expansion is an image processing technique to display a low bit-depth image on a high bit-depth monitor. In this paper, we study a variational method for expanding the bit-depth of low contrast images. Our idea is to develop a variational approach containing an energy functional to determine a local mapping function f(r,x) for bit-depth expansion via a smoothing technique, such that each pixel can be adjusted locally to a high bit-depth value. In order to enhance low contrast images, we make use of the histogram equalization technique for such local mapping function. Both bit-depth expansion and equalization terms can be combined together into the resulting objective function. In order to minimize the differences among the local mapping function at the nearby pixel locations, the spatial regularization of the mapping is incorporated in the objective function. Experimental results are reported to show that the performance of the proposed method is competitive with the other compared methods for several testing low contrast images.

Second derivative regularization methods for dense stereo matching is a topic of intense research. Some of the most successful recent methods employ so called binary fusion moves where the combination of two proposal solutions is computed. In many cases the fusion move can be solved optimally, but the approach is limited to fusing pairs of proposals in each move. For multiple proposals iterative binary fusion may potentially lead to local minima.

In this paper we demonstrate how to simultaneously fuse more than two proposals at the same time for a 2nd order stereo regularizer. The optimization is made possible by effectively computing a generalized distance transform. This allows for computation of messages in linear time in the number of proposals. In addition the approach provides a lower bound on the globally optimal solution of the multi-fusion problem. We verify experimentally that the lower bound is very close to the computed solution, thus providing a near optimal solution.

Minimal partition problems describe the task of partitioning a domain into a set of meaningful regions. Two important examples are image segmentation and 3D reconstruction. They can both be formulated as energy minimization problems requiring minimum boundary length or surface area of the regions. This common prior often leads to the removal of thin or elongated structures. Volume constraints impose an additional prior which can help preserve such structures. There exist a multitude of algorithms to minimize such convex functionals under convex constraints. We systematically compare the recent Primal Dual (PD) algorithm [1] to the Alternating Direction Method of Multipliers (ADMM) [2] on volume-constrained minimal partition problems. Our experiments indicate that the ADMM approach provides comparable and often better performance.

A new approach for the effective computation of geodesic regression curves in shape spaces is presented. Here, one asks for a geodesic curve on the shape manifold that minimizes a sum of dissimilarity measures between given two- or three-dimensional input shapes and corresponding shapes along the regression curve. The proposed method is based on a variational time discretization of geodesics. Curves in shape space are represented as deformations of suitable reference shapes, which renders the computation of a discrete geodesic as a PDE constrained optimization for a family of deformations. The PDE constraint is deduced from the discretization of the covariant derivative of the velocity in the tangential direction along a geodesic. Finite elements are used for the spatial discretization, and a hierarchical minimization strategy together with a Lagrangian multiplier type gradient descent scheme is implemented. The method is applied to the analysis of root growth in botany and the morphological changes of brain structures due to aging.

In the paper we address a challenging problem of incorporating preferences on possible shapes of an object in a binary image segmentation framework. We extend the well-known conditional random fields model by adding new variables that are responsible for the shape of an object. We describe the shape via a flexible graph augmented with vertex positions and edge widths. We derive exact and approximate algorithms for MAP estimation of label and shape variables given an image. An original learning procedure for tuning parameters of our model based on unlabeled images with only shape descriptions given is also presented. Experiments confirm that our model improves the segmentation quality in hard-to-segment images by taking into account the knowledge about typical shapes of the object.

Finding optimal data for inpainting is a key problem in the context of partial differential equation-based image compression. We present a new model for optimising the data used for the reconstruction by the underlying homogeneous diffusion process. Our approach is based on an optimal control framework with a strictly convex cost functional containing an L ₁ term to enforce sparsity of the data and non-convex constraints. We propose a numerical approach that solves a series of convex optimisation problems with linear constraints. Our numerical examples show that it outperforms existing methods with respect to quality and computation time.

To obtain high-quality segmentation results the integration of semantic information is indispensable. In contrast to existing segmentation methods which use a spatial regularizer, i.e. a local interaction between image points, the co-occurrence prior [15] imposes penalties on the co-existence of different labels in a segmentation. We propose a continuous domain formulation of this prior, using a convex relaxation multi-labeling approach. While the discrete approach [15] is employs minimization by sequential alpha expansions, our continuous convex formulation is solved by efficient primal-dual algorithms, which are highly parallelizable on the GPU. Also, our framework allows isotropic regularizers which do not exhibit grid bias. Experimental results on the MSRC benchmark confirm that the use of co-occurrence priors leads to drastic improvements in segmentation compared to the classical Potts model formulation when applied.

We revisit the Chan-Vese model of image segmentation with a focus on the encoding with several integer-valued labeling functions. We relate several representations with varying amount of complexity and demonstrate the connection to recent relaxations for product sets and to dual maxflow-based formulations. For some special cases, it can be shown that it is possible to guarantee binary minimizers. While this is not true in general, we show how to derive a convex approximation of the combinatorial problem for more than 4 phases. We also provide a method to avoid overcounting of boundaries in the original Chan-Vese model without departing from the efficient product-set representation. Finally, we derive an algorithm to solve the associated discretized problem, and demonstrate that it allows to obtain good approximations for the segmentation problem with various number of regions.

Variational models as the Mumford-Shah model and the active contour model have many applications in image segmentation. In this paper, we propose a new multiclass segmentation model by combining the Rudin-Osher-Fatemi model with an iterative thresholding procedure. We show that our new model for two classes is indeed equivalent to the Chan-Vese model but with an adapted regularization parameter which allows to segment classes with similar gray values. We propose an efficient algorithm and discuss its convergence under certain conditions. Experiments on cartoon, texture and medical images demonstrate that our algorithm is not only fast but provides very good segmentation results in comparison with other state-of-the-art segmentation models in particular for images containing classes of similar gray values.

We propose a unified graph cut based global minimization method for multiphase image segmentation by convexifying the non-convex image segmentation cost functionals. As examples, we shall apply this method to the non-convex multiphase Chan-Vese (CV) model and piecewise constant level set method (PCLSM). Both continuous and discretized formulations will be treated. For the discrete models, we propose a unified graph cut algorithm to implement the CV and PCLSM models, which extends the result of Bae and Tai [1] to any phases CV model. Moreover, in the continuous case, we further improve the model to be convex without any conditions using a number of techniques that are unique to the continuous segmentation models. With the convex relaxation and the dual method, the related continuous dual model is convex and we can mathematically show that the global minimization can be achieved. The corresponding continuous max-flow algorithm is easy and stable. Experimental results show that our model is very efficient.

We address the problem of segmenting an image into a previously unknown number of segments from the perspective of graph partitioning. Specifically, we consider minimum multicuts of superpixel affinity graphs in which all affinities between non-adjacent superpixels are negative. We propose a relaxation by Lagrangian decomposition and a constrained set of re-parameterizations for which we can optimize exactly and efficiently. Our contribution is to show how the planarity of the adjacency graph can be exploited if the affinity graph is non-planar. We demonstrate the effectiveness of this approach in user-assisted image segmentation and show that the solution of the relaxed problem is fast and the relaxation is tight in practice.

Multi-Instance Multi-Label (MIML) learning is one of challenging research problems in machine learning. The main aim of this paper is to propose and develop a novel sparsity-based MIML learning algorithm. Our idea is to formulate and construct a transductive objective function for labels indicator to be learned by using the method of random walk with restart that exploits the relationships among instances and labels of objects, and computes the affinities among the objects. Then sparsity can be introduced in the labels indicator of the objective function such that relevant and irrelevant objects with respect to a given class can be distinguished. The resulting sparsity-based MIML model can be given as a constrained convex optimization problem, and it can be solved very efficiently by using the augmented Lagrangian method. Experimental results on benchmark data have shown that the proposed sparse-MIML algorithm is computationally efficient, and effective in label prediction for MIML data. We demonstrate that the performance of the proposed method is better than the other testing MIML learning algorithms.

Consensus clustering methodologies combine a set of partitions on the clustering ensemble providing a consensus partition. One of the drawbacks of the standard combination algorithms is that all the partitions of the ensemble have the same weight on the aggregation process. By making a differentiation among the partitions the quality of the consensus could be improved. In this paper we propose a novel formulation that tries to find a median-partition for the clustering ensemble process based on the evidence accumulation framework, but including a weighting mechanism that allows to differentiate the importance of the partitions of the ensemble in order to become more robust to noisy ensembles. Experiments on both synthetic and real benchmark data show the effectiveness of the proposed approach.

We present novel variational approaches for segmenting and cosegmenting images. Our supervised segmentation approach extends the classical Continuous Cut approach by a global appearance-based data term enforcing closeness of aggregated appearance statistics to a given prior model. This novel data term considers non-spatial, deformation-invariant statistics with the help of the Wasserstein distance in a single global model. The unsupervised cosegmentation model also employs the Wasserstein distance for finding the common object in two images. We introduce tight convex relaxations for both presented models together with efficient algorithmic schemes for computing global minimizers. Numerical experiments demonstrate the effectiveness of our models and the convex relaxations.

In this paper, we present a general convex formulation for global histogram-based binary segmentation. The model relies on a data term measuring the histograms of the regions to segment w.r.t. reference histograms as well as TV regularization allowing the penalization of the length of the interface between the two regions. The framework is based on some l ¹ data term, and the obtained functional is minimized with an algorithm adapted to non smooth optimization. We present the functional and the related numerical algorithm and we then discuss the incorporation of color histograms, cumulative histograms or structure tensor histograms. Experiments show the interest of the method for a large range of data including both gray-scale and color images. Comparisons with a local approach based on the Potts model or with a recent one based on Wasserstein distance also show the interest of our method.

The competition between discrete (MRF based) and continuous (PDE based) formulations has a very long history, especially in context of segmentation. Obviously, both have their advantages and drawbacks. Therefore the choice of a discrete or continuous framework is often driven by a particular application or (even more often) by personal preferences of a particular researcher. In this work we present a model for binary segmentation, where discrete and continuous parts are combined in a well founded and simple way. We discuss the properties of the proposed model, give a basic inference algorithm and validate it on a benchmark database.