Academic
Publications
Convex Multi-class Image Labeling by Simplex-Constrained Total Variation

Convex Multi-class Image Labeling by Simplex-Constrained Total Variation,10.1007/978-3-642-02256-2_13,Jan Lellmann,Jörg H. Kappes,Jing Yuan,Florian Be

Convex Multi-class Image Labeling by Simplex-Constrained Total Variation   (Citations: 21)
BibTex | RIS | RefWorks Download
Multi-class labeling is one of the core problems in image analysis. We show how this combinatorial problem can be approximately solved using tools from convex optimization. We suggest a novel functional based on a multidimensional total variation formulation, allowing for a broad range of data terms. Optimization is carried out in the operator splitting framework using Douglas-Rachford Splitting. In this connection, we compare two methods to solve the Rudin-Osher-Fatemi type subproblems and demonstrate the performance of our approach on single- and multichannel images.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Recently, similar convex formulations have also been proposed for the continuous Potts model with more than two labels (Zach et al. 2008; Lellmann et al. 2009; Pock et al. 2009), by relaxing the integrability constraint of the labeling function...
    • ...Some other relaxations closely related to (Zach et al. 2008; Lellmann et al. 2009) have later been proposed in (Brown et al. 2009, 2010)...
    • ...This paper builds on the work of Zach et al. (2008) and Lellmann et al. (2009)...
    • ...A new algorithm derived from the smoothed dual formulation is shown to be significantly more efficient than the state of art works (Zach et al. 2008; Lellmann et al. 2009)...
    • ...This work builds on the convex relaxation method of the nonconvex Potts model (Zach et al. 2008; Lellmann et al. 2009)...
    • ...Zach et al. (2008) and Lellmann et al. (2009) proposed to use the indicator function of the largest component ui as an approximate binary solution, i.e...
    • ...Secondly, we evaluate quality and efficiency with the approaches of (Zach et al. 2008; Lellmann et al. 2009)...
    • ...7 and 8 was first used by Lellmann et al. (2009)...
    • ...Observe also that our approach can obtain solutions of lower energy than the approaches (Zach et al. 2008; Lellmann et al. 2009)...
    • ...This benefit can also be observed in the energy plots of Fig. 10: we can obtain binary solutions of lower energy than the approaches of Zach et al. (2008), Lellmann et al. (2009)...
    • ...We will now compare the cpu time and convergence with the approaches (Zach et al. 2008; Lellmann et al. 2009)...
    • ...Furthermore, each iteration of this loop has a computational cost approximately equal to one inner loop iteration of (Zach et al. 2008; Lellmann et al. 2009)...
    • ...between 0 and 1. The approaches (Lellmann et al. 2009; Zach et al. 2008) require more parameters, like the outer time step τ , inner time step, accuracy of solving inner problem etc...
    • ...Another algorithm was derived which was shown to converge faster than the approaches of Lellmann et al. (2009), Zach et al. (2008)...

    Egil Baeet al. Global Minimization for Continuous Multiphase Partitioning Problems Us...

    • ...Recently, Chan’s model (1) was extended to more than two regions in [18, 16, 4], which proposes multi-way cuts in a continuous configuration and was applied to solve multi-labeling problems...

    Jing Yuanet al. A study on continuous max-flow and min-cut approaches

    • ...However, by relaxing the original problem to a convex constraint set, good solutions for the original problem can be recovered using convex optimization [22,4,13,14]...

    Jan Lellmannet al. Fast and Exact Primal-Dual Iterations for Variational Problems in Comp...

    • ...[3,18,19,20,21,22]. Compared to level set methods, great advantages in numerics can be achieved, e.g...
    • ...In [18,22], such convex minimization problem is computed directly through the minimization over the labeling functions, i.e...
    • ...Experiments show that our max-flow algorithm is much more efficient than the state of art of computational methods [18,22]...
    • ...Our experiments show it is around 4 times faster than the previous methods [18,22]...
    • ...Clearly, the Potts model (4) is nonconvex due to the binary configuration of each function ui(x) ∈{ 0, 1} .T heconvex relaxed Potts model [20,22,21] proposes to relax such binary constraints to the convex interval [0, 1] and approximates (4) by the reduced convex optimization problem:...
    • ...In [22], a Douglas-Rachford splitting algorithm was proposed to solve a quite similar problem as (5), where a variant of the total-variation term is considered:...
    • ...In contrast to [18,22,20,27], [21] did not try to tackle the labeling function of the continuous min-cut problem (5) directly, but solved its equivalent dual formulation:...
    • ...In numerics, its great advantages over previous works are: it avoids pointwise projections onto the simplex constraint S within each outer loop as [18,22]; in comparison to [21,26], it exactly solves (6) without any smoothing procedure; it is globally optimized based on an efficient and reliable multiplier-based max-flow algorithm, in contrast to the PDE-descent method [20,27] whose convergence may suffer from uncareful stepsizes resulting ...
    • ... onto the simplex constraint S within each outer loop as [18,22]; in comparison to [21,26], it exactly solves (6) without any smoothing procedure; it is globally optimized based on an efficient and reliable multiplier-based max-flow algorithm, in contrast to the PDE-descent method [20,27] whose convergence may suffer from uncareful stepsizes resulting in suboptimums; experiments show a faster convergence rate, about 4 times, than [18,22]...
    • ...The quality of the relaxation (5) has been evaluated extensively in [18,22,21] where it has been shown to be competitive to several state of the art methods from discrete optimization like alpha expansion and alpha beta-swap [2] for approximately minimizing the Pott’s energy...
    • ...The Douglas-Rachford splitting approach given in [22] can also be proved to converge (in the discrete setting), but we experienced that our approach was more efficient than both these approaches...
    • ...However, in contrast to [18,22] our approach avoids iterative projections to the convex set S and consequently require much less outer iterations...
    • ...E∗ . For the three images (see Fig. 2), dif ferent precision � are taken and the total number of iterations to reach convergence is evaluated, see Tab 1: clearly, our method is about 4 times faster than the Douglas-Rachford-splitting [22], the approach in [18] is even slower and failed to reach such a low precision...
    • ...Table 1. Comparisons between algorithms: Zach et al [18], Lellmann [22] and the proposed max-flow algorithm: for the three images (see Fig. 2), different precision � are taken and the total number of iterations to reach convergence is evaluated...
    • ...Zach et al [18] fail to reach such a precision Lellmann et al [22] 421 iter...

    Jing Yuanet al. A Continuous Max-Flow Approach to Potts Model

    • ...(a) Input image (b) Lellmann et al. [22] (c) Zach et al. [30] (d) Proposed relaxation...
    • ...More recently, Lellman et al. in [22] proposed a qualitatively comparable approach with a slightly different length term...
    • ...Figure 3 shows a comparison of the proposed approach to the relaxation approach of [30] and [22] by means of a simple three-label segmentation problem...
    • ...The solution of our approach achieves an energy ofE = 13975 which is clearly aboveE = 13972 achieved by [30] andE = 13960 achieved by [22]...

    Thomas Pocket al. A convex relaxation approach for computing minimal partitions

Sort by: