Update. The latest version with some corrections and clarifications canbe found below.

Update. The LaTex sources of the paper and the slides are now available on GitHub.

Abstract

This paper studies the minimization of non-convex and non-smooth composite functionsIn particular, we discuss the algorithm proposed by Ochs et al. in [1], called iPiano. Following [1], we present a global convergence result for functions satisfying the Kurdyka-Lojasiewicz property [2,3] which is based on the work by Attouch et al. [4]. Furthermore, we discuss the implementation of iPiano and apply the algorithm to image denoising and image segmentation. In contrast to [1], we use simple denoising functionals instead of Fields of Expert [5,6] to demonstrate that simple functionals may benefit from non-smooth and non-convex terms. Finally, we demonstrate the applicability of the algorithm to image segmentation based on a 2-phase fields approximation of the Mumford-Shah functional [7].

Seminar PaperPresentation Slides

Implementation

iPiano has been implemented in C++ based on Eigen. Applications include image denoising, image segmentation (utilizing OpenCV) and compressed sensing. The implementation is vailable on GitHub:

Some articles related to the implementation can be found here:

• Implementation for Non-Convex and Non-Smooth Optimization

References

• [1] P. Ochs, Y. Chen, T. Brox, T. Pock. iPiano: Inertial proximal algorithm for nonconvex optimization., SIAM J. Imaging Sciences, 7 (2014), pp. 1388–1419.
• [2] S. Lojasiewicz. Sur la gomtrie semi- et sous- analytique. Annales de l’institut Fourier, 43 (1993), pp. 1575–1595.
• [3] K. Kurdyka. On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier, 48 (1998), pp. 769–783.
• [4] H. Attouch, J. Bolte, B. F. Svaiter .Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods. Math. Program., 137 (2013), pp. 91–129.
• [5] S. Roth and M. J. Black, Fields of experts, International Journal of Computer Vision, 82 (2009), pp. 205–229.
• [6] Y. Chen, T. Pock, R. Ranftl, H. Bischof. Revisiting loss-specific training of filter-based MRFs for image restoration. in Pattern Recognition, German Conference on, Saarbr¨ucken, Germany, September 2013, pp. 271–281.
• [7] J. Shen. Gamma-convergence approximation to piecewise constant mumford-shah segmentation. in Advanced Concepts for Intelligent Vision Systems, International Conference on, vol. 3708 of Lecture Notes in Computer Science, Antwerpen, Belgium, September 2005, Springer, pp. 499–506.