While widely acknowledged as highly effective in computer vision, multi-label MRFs with non-convex priors are difficult to optimize. To tackle this, we introduce an algorithm that iteratively approximates the original energy with an appropriately weighted surrogate energy that is easier to minimize. Our algorithm guarantees that the original energy decreases at each iteration. In particular, we consider the scenario where the global minimizer of the weighted surrogate energy can be obtained by a multi-label graph cut algorithm, and show that our algorithm then lets us handle of large variety of non-convex priors. We demonstrate the benefits of our method over state-of-the-art MRF energy minimization techniques on stereo and inpainting problems.
@cite_25: In many computer vision applications, a desired model of some type is computed by minimizing a cost function based on several measurements. Typically, one may compute the model that minimizes the @math cost, that is the sum of squares of measurement errors with respect to the model. However, the @math solution which minimizes the sum of the @math th power of errors usually gives more robust results in the presence of outliers for some values of @math , for example, @math . The Weiszfeld algorithm is a classic algorithm for finding the geometric @math mean of a set of points in Euclidean space. It is provably optimal and requires neither differentiation, nor line search. The Weiszfeld algorithm has also been generalized to find the @math mean of a set of points on a Riemannian manifold of non-negative curvature. This paper shows that the Weiszfeld approach may be extended to a wide variety of problems to find an @math mean for @math , while maintaining simplicity and provable convergence. We apply this problem to both single-rotation averaging (under which the algorithm provably finds the global @math optimum) and multiple rotation averaging (for which no such proof exists). Experimental results of @math optimization for rotations show the improved reliability and robustness compared to @math optimization.
@cite_20: This paper presents a way of using the Iteratively Reweighted Least Squares (IRLS) method to minimize several robust cost functions such as the Huber function, the Cauchy function and others. It is known that IRLS (otherwise known as Weiszfeld) techniques are generally more robust to outliers than the corresponding least squares methods, but the full range of robust M-estimators that are amenable to IRLS has not been investigated. In this paper we address this question and show that IRLS methods can be used to minimize most common robust M-estimators. An exact condition is given and proved for decrease of the cost, from which convergence follows. In addition to the advantage of increased robustness, the proposed algorithm is far simpler than the standard L1 Weiszfeld algorithm. We show the applicability of the proposed algorithm to the rotation averaging, triangulation and point cloud alignment problems.
@cite_2: Natural image statistics indicate that we should use non-convex norms for most regularization tasks in image processing and computer vision. Still, they are rarely used in practice due to the challenge to optimize them. Recently, iteratively reweighed l1 minimization has been proposed as a way to tackle a class of non-convex functions by solving a sequence of convex l2 - l1 problems. Here we extend the problem class to linearly constrained optimization of a Lipschitz continuous function, which is the sum of a convex function and a function being concave and increasing on the non-negative orthant (possibly non-convex and non-concave on the whole space). This allows to apply the algorithm to many computer vision tasks. We show the effect of non-convex regularizers on image denoising, deconvolution, optical flow, and depth map fusion. Non-convexity is particularly interesting in combination with total generalized variation and learned image priors. Efficient optimization is made possible by some important properties that are shown to hold.
As mentioned above, our algorithm is inspired by the IRLS method. Recently, several methods similarly motivated by the IRLS have been proposed to minimize different objective functions. For instance, in @cite_25 , the @math norm (for @math ) was minimized by iteratively minimizing a weighted @math cost function. @cite_2 , an iterated @math algorithm was introduced to optimize non-convex functions that are the sum of convex data terms and concave smoothness terms. More recently, a general formulation (not restricted to weighted @math or @math minimization) was studied together with the conditions under which such iteratively reweighted algorithms ensure the cost to decrease @cite_20 . In the next section, we propose an extension of this formulation that will later allow us to tackle the case of multi-label MRFs.