Energy Minimization Methods in Computer Vision and Pattern Recognition

In this paper we consider the classical problem of finding a low rank approximation of a given matrix. In a least squares sense a closed form solution is available via factorization. However, with additional constraints, or in the presence of missing data, the problem becomes much more difficult. In this paper we show how to efficiently compute the convex envelopes of a class of rank minimization formulations. This opens up the possibility of adding additional convex constraints and functions to the minimization problem resulting in strong convex relaxations. We evaluate the framework on both real and synthetic data sets and demonstrate state-of-the-art performance.

In this work, we study the problems of computing spatially continuous cuts, which has many important applications of image processing and computer vision. We focus on the convex relaxed formulations and investigate the corresponding flow-maximization based dual formulations. We propose a series of novel continuous max-flow models based on evaluating different constraints of flow excess, where the classical pre-flow and pseudo-flow models over graphs are re-discovered in the continuous setting and re-interpreted in a new variational manner. We propose a new generalized proximal method, which is based on a specific entropic distance function, to compute the maximum flow. This leads to new algorithms exploring flow-maximization and message-passing simultaneously. We show the proposed algorithms are superior to state of art methods in terms of efficiency.

Direct linear programming (LP) solution to binary sub-modular MRF energy has recently been promoted because i) the solution is identical to the solution by graph cuts, ii) LP is naturally parallelizable and iii) it is flexible in incorporation of constraints. Nevertheless, the conventional LP relaxation for MRF incurs a large number of auxiliary variables and constraints, resulting in expensive consumption in memory and computation. In this work, we propose to approximate the solution of the conventional LP at a significantly smaller complexity by solving a novel compact LP model. We further establish a tightenable approximation bound between our LP model and the conventional LP model. Our LP model is obtained by linearizing a novel

l

1

-norm energy derived from the Cholesky factorization of the quadratic form of the MRF energy, and it contains significantly fewer variables and constraints compared to the conventional LP relaxation. We also show that our model is closely related to the total-variation minimization problem, and it can therefore preserve the discontinuities in the labels. The latter property is very desirable in most of the imaging and vision applications. In the experiments, our method achieves similarly satisfactory results compared to the conventional LP, yet it requires significantly smaller computation cost.

The continuation method is a popular heuristic in computer vision for nonconvex optimization. The idea is to start from a simplified problem and gradually deform it to the actual task while tracking the solution. It was first used in computer vision under the name of graduated nonconvexity. Since then, it has been utilized explicitly or implicitly in various applications. In fact, state-of-the-art optical flow and shape estimation rely on a form of continuation. Despite its empirical success, there is little theoretical understanding of this method. This work provides some novel insights into this technique. Specifically, there are many ways to choose the initial problem and many ways to progressively deform it to the original task. However, here we show that when this process is constructed by Gaussian smoothing, it is optimal in a specific sense. In fact, we prove that Gaussian smoothing emerges from the best affine approximation to Vese’s nonlinear PDE. The latter PDE evolves any function to its convex envelope, hence providing the optimal convexification.

An important subclass of the min-sum labeling problem (also known as discrete energy minimization or valued constraint satisfaction) is the pairwise min-sum problem with arbitrary unary costs and attractive Potts pairwise costs (also known as the uniform metric labeling problem). In analogy with our recent result, we show that solving the LP relaxation of the Potts min-sum problem is not significantly easier than that of the general min-sum problem and thus, in turn, the general linear program. This suggests that trying to find an efficient algorithm to solve the LP relaxation of the Potts min-sum problem has a fundamental limitation. Our constructions apply also to integral solutions, yielding novel reductions of the (non-relaxed) general min-sum problem to the Potts min-sum problem.

The continuation method is a popular heuristic in computer vision for nonconvex optimization. The idea is to start from a simplified problem and gradually deform it to the actual problem while tracking the solution. There are many choices for how to map the nonconvex objective to some convex task. One popular principle for such construction is Gaussian smoothing of the objective function. This involves an integration which may be expensive to compute numerically. We argue that often simple tricks at the problem formulation plus some mild approximations can make the resulted task amenable to closed form integral.

Finding optimal data for inpainting is a key problem for image-compression with partial differential equations. Not only the location of important pixels but also their values should be optimal to maximise the quality gain. The position of important data is usually encoded in a binary mask. Recent studies have shown that allowing non-binary masks may lead to tremendous speedups but comes at the expense of higher storage costs and yields prohibitive memory requirements for the design of competitive image compression codecs. We show that a recently suggested heuristic to eliminate the additional storage costs of the non-binary mask has a strong theoretical foundation in finite dimension. Binary and non-binary masks are equivalent in the sense that they can both give the same reconstruction error if the binary mask is supplemented with optimal data which does not increase the memory footprint. Further, we suggest two fast numerical schemes to obtain this optimised data. This provides a significant building block in the conception of efficient data compression schemes with partial differential equations.

Image priors are of great importance in image restoration tasks. These problems can be addressed by decomposing the degraded image into overlapping patches, treating the patches individually and averaging them back together. Recently, the Expected Patch Log Likelihood (EPLL) method has been introduced, arguing that the chosen model should be enforced on the final reconstructed image patches. In the context of a Gaussian Mixture Model (GMM), this idea has been shown to lead to state-of-the-art results in image denoising and debluring. In this paper we combine the EPLL with a sparse-representation prior. Our derivation leads to a close yet extended variant of the popular K-SVD image denoising algorithm, where in order to effectively maximize the EPLL the denoising process should be iterated. This concept lies at the core of the K-SVD formulation, but has not been addressed before due the need to set different denoising thresholds in the successive sparse coding stages. We present a method that intrinsically determines these thresholds in order to improve the image estimate. Our results show a notable improvement over K-SVD in image denoising and inpainting, achieving comparable performance to that of EPLL with GMM in denoising.

In this work we devise two novel algorithms for blind deconvolution based on a family of logarithmic image priors. In contrast to recent approaches, we consider a minimalistic formulation of the blind deconvolution problem where there are only two energy terms: a least-squares term for the data fidelity and an image prior based on a lower-bounded logarithm of the norm of the image gradients. We show that this energy formulation is sufficient to achieve the state of the art in blind deconvolution with a good margin over previous methods. Much of the performance is due to the chosen prior. On the one hand, this prior is very effective in favoring sparsity of the image gradients. On the other hand, this prior is non convex. Therefore, solutions that can deal effectively with local minima of the energy become necessary. We devise two iterative minimization algorithms that at each iteration solve convex problems: one obtained via the primal-dual approach and one via majorization-minimization. While the former is computationally efficient, the latter achieves state-of-the-art performance on a public dataset.

In this work we consider the regularization of vectorial data such as color images. Based on the observation that edge alignment across image channels is a desirable prior for multichannel image restoration, we propose a novel scheme of minimizing the rank of the image Jacobian and extend this idea to second derivatives in the framework of total generalized variation. We compare the proposed convex and nonconvex relaxations of the rank function based on the Schatten-

q

norm to previous color image regularizers and show in our numerical experiments that they have several desirable properties. In particular, the nonconvex relaxations lead to better preservation of discontinuities. The efficient minimization of energies involving nonconvex and nonsmooth regularizers is still an important open question. We extend a recently proposed primal-dual splitting approach for nonconvex optimization and show that it can be effectively used to minimize such energies. Furthermore, we propose a novel algorithm for efficiently evaluating the proximal mapping of the ℓ

q

norm appearing during optimization. We experimentally verify convergence of the proposed optimization method and show that it performs comparably to sequential convex programming.

In this paper, we propose a novel framework for restoring color images using nonlocal total variation (NLTV) regularization. We observe that the discrete local and nonlocal gradient of a color image can be viewed as a 3D matrix/or tensor with dimensions corresponding to the spatial extend, the differences to other pixels, and the color channels. Based on this observation we obtain a new class of NLTV methods by penalizing the ℓ

p

,

q

,

r

norm of this 3D tensor. Interestingly, this unifies several local color total variation (TV) methods in a single framework. We show in several numerical experiments on image denoising and deblurring that a stronger coupling of different color channels – particularly, a coupling with the ℓ

 ∞ 

norm – yields superior reconstruction results.

Cyclic data arise in various image and signal processing applications such as interferometric synthetic aperture radar, electroencephalogram data analysis, and color image restoration in HSV or LCh spaces. In this paper we introduce a variational inpainting model for cyclic data which utilizes our definition of absolute cyclic second order differences. Based on analytical expressions for the proximal mappings of these differences we propose a cyclic proximal point algorithm (CPPA) for minimizing the corresponding functional. We choose appropriate cycles to implement this algorithm in an efficient way. We further introduce a simple strategy to initialize the unknown inpainting region. Numerical results both for synthetic and real-world data demonstrate the performance of our algorithm.

Recent research has shown that inpainting with the Laplace or biharmonic operator has a high potential for image compression, if the stored data is optimised and sufficiently sparse. The goal of our paper is to connect these linear inpainting methods to sparsity concepts. To understand these relations, we explore the theory of Green’s functions. In contrast to most work in the mathematical literature, we derive our Green’s functions in a discrete setting and on a rectangular image domain with homogeneous Neumann boundary conditions. These discrete Green’s functions can be interpreted as columns of the Moore–Penrose inverse of the discretised differential operator. More importantly, they serve as atoms in a dictionary that allows a sparse representation of the inpainting solution. Apart from offering novel theoretical insights, this representation is also simple to implement and computationally efficient if the inpainting data is sparse.

We propose to solve an image segmentation problem with connectivity constraints via projection onto the constraint set. The constraints form a convex set and the convex image segmentation problem with a total variation regularizer can be solved to global optimality in a primal-dual framework. Efficiency is achieved by directly computing the update of the primal variable via a projection onto the constraint set, which results in a special quadratic programming problem similar to the problems studied as isotonic regression methods in statistics, which can be solved with

O

(

n

log

n

) complexity. We show that especially for segmentation problems with long range connections this method is by orders of magnitudes more efficient, both in iteration number and runtime, than solving the dual of the constrained optimization problem. Experiments validate the usefulness of connectivity constraints for segmenting thin structures such as veins and arteries in medical image analysis.

In this paper we propose a variational method to adaptively decompose an image into few different modes of separate spectral bands, which are unknown before. A popular method for recursive one dimensional signal decomposition is the Empirical Mode Decomposition algorithm, introduced by Huang in the nineties. This algorithm, as well as its 2D extension, though extensively used, suffers from a lack of exact mathematical model, interpolation choice, and sensitivity to both noise and sampling. Other state-of-the-art models include synchrosqueezing, the empirical wavelet transform, and recursive variational decomposition into smooth signals and residuals. Here, we have created an entirely non-recursive 2D variational mode decomposition (2D-VMD) model, where the modes are extracted concurrently. The model looks for a number of 2D modes and their respective center frequencies, such that the bandlimited modes reproduce the input image (exactly or in least-squares sense). Preliminary results show excellent performance on both synthetic and real images. Running this algorithm on a peptide microscopy image yields accurate, timely, and autonomous segmentation - pertinent in the fields of biochemistry and nanoscience.

We focus on the multi-class segmentation problem using the piecewise constant Mumford-Shah model in a graph setting. After formulating a graph version of the Mumford-Shah energy, we propose an efficient algorithm called the MBO scheme using threshold dynamics. Theoretical analysis is developed and a Lyapunov functional is proven to decrease as the algorithm proceeds. Furthermore, to reduce the computational cost for large datasets, we incorporate the Nyström extension method which efficiently approximates eigenvectors of the graph Laplacian based on a small portion of the weight matrix. Finally, we implement the proposed method on the problem of chemical plume detection in hyper-spectral video data.

Texture is intuitively defined as a repeated arrangement of a basic pattern or object in an image. There is no mathematical definition of a texture though. The human visual system is able to identify and segment different textures in a given image. Automating this task for a computer is far from trivial.

There are three major components of any texture segmentation algorithm: (a) The features used to represent a texture, (b) the metric induced on this representation space and (c) the clustering algorithm that runs over these features in order to segment a given image into different textures.

In this paper, we propose an active contour based novel unsupervised algorithm for texture segmentation. We use intensity covariance matrices of regions as the defining feature of textures and find regions that have the most inter-region dissimilar covariance matrices using active contours. Since covariance matrices are symmetric positive definite, we use geodesic distance defined on the manifold of symmetric positive definite matrices

PD

(

n

) as a measure of dissimilarity between such matrices. Using recent convexification methods, we are able to compute a global maxima of the cost function. We demonstrate performance of our algorithm on both artificial and real texture images.

In this paper, we propose a subMarkov random walk (subRW) with the label prior with added auxiliary nodes for seeded image segmentation. We unify the proposed subRW and the other popular random walk algorithms. This unifying view can transfer the intrinsic findings between different random walk algorithms, and offer the new ideas for designing the novel random walk algorithms by changing the auxiliary nodes. According to the second benefit, we design a subRW algorithm with label prior to solve the segmentation problem of objects with thin and elongated parts. The experimental results on natural images with twigs demonstrate that our algorithm achieves better performance than the previous random walk algorithms.

In this paper, an object segmentation algorithm based on automatic shape constraint selection is proposed. Different from the traditional shape prior based object segmentation methods which only provide loose shape constraints, our proposed object segmentation gives more accurate shape constraint by selecting the most appropriate shape among the standard shape set. Furthermore, to overcome the inevitable differences between the true borders and the standard shapes, the Coherent Point Drift (CPD) is adopted to project the standard shapes to the local ones. A quantitative evaluating mechanism is introduced to pick out the most suitable shape prior. The proposed algorithm mainly consists of four steps: 1) the initial GrabCut segmentation; 2) standard shape projection by CPD registration; 3) rank the standard shapes according to the evaluation scores; 4) refine GrabCut segmentation with the chosen shape constraint. The comparison experiments with the related algorithms on Weizmann_horse dataset have demonstrated the good performance of the proposed algorithm.

Tensor-driven anisotropic diffusion and regularisation have been successfully applied to a wide range of image processing and computer vision tasks such as denoising, inpainting, and optical flow. Empirically it has been shown that anisotropic models with a diffusion tensor perform better than their isotropic counterparts with a scalar-valued diffusivity function. However, the reason for this superior performance is not well understood so far. Moreover, the specific modelling of the anisotropy has been carried out in a purely heuristic way. The goal of our paper is to address these problems. To this end, we use the statistics of natural images to derive a unifying framework for eight isotropic and anisotropic diffusion filters that have a corresponding variational formulation. In contrast to previous statistical models, we systematically investigate structure-adaptive statistics by analysing the eigenvalues of the structure tensor. With our findings, we justify existing successful models and assess the relationship between accurate statistical modelling and performance in the context of image denoising.

We propose a new principle, the

variational region competition

, to simultaneously propagate multiple disjoint level-sets in a fully time-implicit manner, minimizing the total cost w.r.t. region changes. We demonstrate, that the problem of multiphase level-set evolution can be reformulated in terms of a Potts problem, for which fast optimization algorithms are available using recent developments in convex relaxation. Further, we use an efficient recently proposed duality-based continuous max-flow method [1] implemented using massively parallel computing on GPUs for high computational performance. In contrast to conventional multi-phase level-set evolution approaches, ours allows for large time steps accelerating the evolution procedure. Further, the proposed method propagates all regions simultaneously, as opposed to the one-by-one phase movement of current time-implicit implementations. Promising experiment results demonstrate substantial improvements in a wide spectrum of practical applications.

We propose a novel iterative algorithm for multiphase image segmentation by curve evolution. Specifically, we address a multiphase version of the Chan-Vese piecewise constant segmentation energy. Our algorithm is efficient: it is based on an explicit Lagrangian representation of the curves and it converges in a relatively small number of iterations. We devise a stable curvature-free semi-implicit velocity computation scheme. This enables us to take large steps to achieve sharp decreases in the multiphase segmentation energy when possible. The velocity and curve computations are linear with respect to the number of nodes on the curves, thanks to a finite element discretization of the curve and the gradient descent equations, yielding essentially tridiagonal linear systems. The step size at each iteration is selected using a nonmonotone line search algorithm ensuring rapid progress and convergence. Thus, the user does not need to specify fixed step sizes or iteration numbers. We also introduce a novel dynamic stopping criterion, robust to various imaging conditions, to decide when to stop the iterations. Our implementation can handle topological changes of curves, such as merging and splitting as well. This is a distinct advantage of our approach, because we do not need to know the number of phases in advance. The curves can merge and split during the evolution to detect the correct regions, especially the number of phases.

We present a novel variational approach to a tensor-based total variation formulation which is called

gradient energy total variation

, GETV. We introduce the gradient energy tensor [6] into the GETV and show that the corresponding Euler-Lagrange (E-L) equation is a tensor-based partial differential equation of total variation type. Furthermore, we give a proof which shows that GETV is a convex functional. This approach, in contrast to the commonly used

structure tensor

, enables a formal derivation of the corresponding E-L equation. Experimental results suggest that GETV compares favourably to other state of the art variational denoising methods such as

extended anisotropic diffusion

(EAD)[1] and

total variation

(TV) [18] for gray-scale and colour images.

In this paper, we propose a two-stage approach for color image segmentation, which is inspired by minimal surface smoothing. Indeed, the first stage is to find a smooth solution to a convex variational model related to minimal surface smoothing. The classical primal-dual algorithm can be applied to efficiently solve the minimization problem. Once the smoothed image

u

is obtained, in the second stage, the segmentation is done by thresholding. Here, instead of using the classical K-means to find the thresholds, we propose a hill-climbing procedure to find the peaks on the histogram of

u

, which can be used to determine the required thresholds. The benefit of such approach is that it is more stable and can find the number of segments automatically. Finally, the experiment results illustrate that the proposed algorithm is very robust to noise and exhibits superior performance for color image segmentation.

In this paper, overlapping domain decomposition methods (DDMs) are used for solving the Rudin-Osher-Fatemi (ROF) model in image restoration. It is known that this problem is nonlinear and the minimization functional is non-strictly convex and non-differentiable. Therefore, it is difficult to analyze the convergence rate for this problem. In this work, we use the dual formulation of the ROF model in connection with proper subspace correction. With this approach, we overcome the problems caused by the non-strict-convexity and non-differentiability of the ROF model. However, the dual problem has a global constraint for the dual variable which is difficult to handle for subspace correction methods. We propose a stable unit decomposition, which allows us to construct the successive subspace correction method (SSC) and parallel subspace correction method (PSC) based domain decomposition. Numerical experiments are supplied to demonstrate the efficiency of our proposed methods.

We present a novel approach to the reconstruction of depth from light field data. Our method uses dictionary representations and group sparsity constraints to derive a convex formulation. Although our solution results in an increase of the problem dimensionality, we keep numerical complexity at bay by restricting the space of solutions and by exploiting an efficient Primal-Dual formulation. Comparisons with state of the art techniques, on both synthetic and real data, show promising performances.

Optical flow research has made significant progress in recent years and it can now be computed efficiently and accurately for many images. However, complex motions, large displacements, and difficult imaging conditions are still problematic. In this paper, we present a framework for estimating optical flow which leads to improvements on these difficult cases by 1) estimating occlusions and 2) using additional temporal information. First, we divide the image into discrete triangles and show how this allows for occluded regions to be naturally estimated and directly incorporated into the optimization algorithm. We additionally propose a novel method of dealing with temporal information in image sequences by using “inertial estimates” of the flow. These estimates are combined using a classifier-based fusion scheme, which significantly improves results. These contributions are evaluated on three different optical flow datasets, and we achieve state-of-the-art results on MPI-Sintel.

We present a novel approach to detect the trajectories of particles by combining (a) adaptive dictionaries that model physically consistent spatio-temporal events, and (b) convex programming for sparse matching and trajectory detection in image sequence data. The mutual parametrization of these two components are mathematically designed so as to achieve provable convergence of the overall scheme to a fixed point. While this work is motivated by the task of estimating instantaneous vessel blood flow velocity using ultrasound image velocimetry, our contribution from the optimization point of view may be of interest also to related pattern and image analysis tasks in different application fields.

In this article we propose a new method to find matches between two images, which is based on a framework similar to the Mixture Point Matching (MPM) algorithm. The main contribution is that both feature and spatial information are considered. We treat one point set as the centroid of the Gaussian Mixture Model (GMM) and the other point set as the data. Different from traditional methods, we propose to assign each GMM component a different weight according to the feature matching score. In this way the feature information is introduced as a reasonable prior to guide the matching, and the spatial transformation offers a global constraint so that local ambiguity can be alleviated. Experiments on real data show that the proposed method is not only robust to outliers, deformation and rotation, but also can acquire the most matches while preserving high precision.

Structured-output learning is a challenging problem; particularly so because of the difficulty in obtaining large datasets of fully labelled instances for training. In this paper we try to overcome this difficulty by presenting a multi-utility learning framework for structured prediction that can learn from training instances with different forms of supervision. We propose a unified technique for inferring the loss functions most suitable for quantifying the consistency of solutions with the given weak annotation. We demonstrate the effectiveness of our framework on the challenging semantic image segmentation problem for which a wide variety of annotations can be used. For instance, the popular training datasets for semantic segmentation are composed of images with hard-to-generate full pixel labellings, as well as images with easy-to-obtain weak annotations, such as bounding boxes around objects, or image-level labels that specify which object categories are present in an image. Experimental evaluation shows that the use of annotation-specific loss functions dramatically improves segmentation accuracy compared to the baseline system where only one type of weak annotation is used.

An

energy landscape map

(ELM) characterizes and visualizes an energy function with a tree structure, in which each leaf node represents a local minimum and each non-leaf node represents the barrier between adjacent energy basins. We demonstrate the utility of ELMs in analyzing non-convex energy minimization problems with two case studies: clustering with Gaussian mixture models and learning mixtures of Bernoulli templates from images. By plotting the ELMs, we are able to visualize the impact of different problem settings on the energy landscape as well as to examine and compare the behaviors of different learning algorithms on the ELMs.

In this paper, we propose a new

marked point process

(MPP) model and the associated optimization technique to extract curvilinear structures. Given an image, we compute the intensity variance and rotated gradient magnitude along the line segment. We constrain high level shape priors of the line segments to obtain smoothly connected line configuration. The optimization technique consists of two steps to reduce the significance of the parameter selection in our MPP model. We employ Monte Carlo sampler with delayed rejection to collect line hypotheses over different parameter spaces. Then, we maximize the consensus among line detection results to reconstruct the most plausible curvilinear structures without parameter estimation process. Experimental results show that the algorithm effectively localizes curvilinear structures on a wide range of datasets.

Spectral graph clustering is among the most popular algorithms for unsupervised segmentation. Applications include problems such as speech separation, segmenting motions or objects in video sequences and community detection in social media. It is based on the computation of a few eigenvectors of a matrix defining the connections between the graph nodes.

In many real world applications, not all edge weights can be defined. In video sequences, for instance, not all 3d-points of the observed objects are visible in all the images. Relations between graph nodes representing the 3d-points cannot be defined if these never co-occur in the same images. It is common practice to simply assign an affinity of zero to such edges.

In this article, we present a formal proof that this procedure decreases the separation between two clusters. An upper bound is derived on the second smallest eigenvalue of the Laplacian matrix. Furthermore, an algorithm to infer missing edges is proposed and results on synthetic and real image data are presented.

A new template matching scheme for the detection of objects on the basis of orientations is proposed. The matching scheme is based on correlations in the domain

$\mathbb{R}^2 \rtimes S^1$

of complex valued invertible orientation scores. In invertible orientation scores, a comprehensive overview of how an image is decomposed into local orientations is obtained. The presented approach allows for the efficient detection of orientation patterns in an intuitive and direct way. Furthermore, an energy minimization approach is proposed for the construction of suitable templates. The method is applied to optic nerve head detection in retinal images and extensive testing is done using images from both public and private databases. The method correctly identifies the optic nerve head in 99.7% of 1737 images.

The first stage in computer aided pulmonary nodule detection schemes is a candidate detection step designed to provide a simplified representation of the lung anatomy, such that features like the lung wall, and large airways are removed leaving only data which has greater potential to be a nodule. Nodules which are connected to blood vessels tend to be characterized by irregular geometrical features which can result in their remaining undetected by rule-based classifiers relying only local image metrics. In the current paper a novel approach for lung nodule candidate detection is proposed based on the application of global segmentation methods combined with mean curvature minimization and simple rule-based filtering. Experimental results indicate that the proposed method can accurately detect nodules displaying a diverse range of geometrical features.

We introduce a novel algorithm for hierarchical clustering on planar graphs we call “Hierarchical Greedy Planar Correlation Clustering” (HGPCC). We formulate hierarchical image segmentation as an ultrametric rounding problem on a superpixel graph where there are edges between superpixels that are adjacent in the image. We apply coordinate descent optimization where updates are based on planar correlation clustering. Planar correlation clustering is NP hard but the efficient PlanarCC solver allows for efficient and accurate approximate inference. We demonstrate HGPCC on problems in segmenting images of cells.