Advanced Search
Article Contents
Article Contents

Minimal partitions and image classification using a gradient-free perimeter approximation

Abstract / Introduction Related Papers Cited by
  • In this paper a new mathematically-founded method for the optimal partitioning of domains, with applications to the classification of greyscale and color images, is proposed. Since optimal partition problems are in general ill-posed, some regularization strategy is required. Here we regularize by a non-standard approximation of the total interface length, which does not involve the gradient of approximate characteristic functions, in contrast to the classical Modica-Mortola approximation. Instead, it involves a system of uncoupled linear partial differential equations and nevertheless shows $\Gamma$-convergence properties in appropriate function spaces. This approach leads to an alternating algorithm that ensures a decrease of the objective function at each iteration, and which always provides a partition, even during the iterations. The efficiency of this algorithm is illustrated by various numerical examples. Among them we consider binary and multilabel minimal partition problems including supervised or automatic image classification, inpainting, texture pattern identification and deblurring.
    Mathematics Subject Classification: 49Q10, 49Q20, 49M25, 35J05, 35J25, 65K10.


    \begin{equation} \\ \end{equation}
  • [1]

    M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, volume 55 of National Bureau of Standards Applied Mathematics Series. For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C., 1964.


    G. Allaire, Shape Optimization by the Homogenization Method, volume 146 of Applied Mathematical Sciences, Springer-Verlag, New York, 2002.


    L. Alvarez, L. Baumela, P. Márquez-Neila and P. Henríquez, A real time morphological snakes algorithm, IPOL, 2012.


    L. Ambrosio, N. Fusco and D. Palara, Functions of Bounded Variation and Free Discontinuity Problems, Oxford Mathematical Monographs. Oxford, 2000.


    L. Ambrosio and V. M. Tortorelli, Approximation of functionals depending on jumps by elliptic functionals via $\Gamma$-convergence, Comm. Pure Appl. Math., 43 (1990), 999-1036.doi: 10.1002/cpa.3160430805.


    S. Amstutz, I. Horchani and M. Masmoudi, Crack detection by the topological gradient method, Control Cybernet., 34 (2005), 81-101.


    S. Amstutz and N. Van Goethem, Topology optimization methods with gradient-free perimeter approximation, Interfaces and Free Boundaries, 14 (2012), 401-430.doi: 10.4171/IFB/286.


    H. Attouch, G. Buttazzo and G. Michaille, Variational Analysis in Sobolev and BV Spaces, volume 6 of MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006. Applications to PDEs and optimization.


    J.-F. Aujol and G. Aubert, Optimal partitions, regularized solutions, and application to image classification, Applicable Analysis, 84 (2005), 15-35.doi: 10.1080/0003681042000267920.


    J.-F. Aujol, G. Gilboa, T. Chan and S. Osher, Structure-texture image decomposition-modeling, algorithms,and parameter selection, Int. J. Comp. Vision, 67 (2006), 111-136.doi: 10.1007/s11263-006-4331-z.


    D. Auroux, L. Jaafar Belaid and M. Masmoudi, A topological asymptotic analysis for the regularized grey-level image classification problem, ESAIM, Math. Model. Numer. Anal., 41 (2007), 607-625.doi: 10.1051/m2an:2007027.


    D. Auroux and M. Masmoudi, Image processing by topological asymptotic expansion, J. Math. Imaging Vision, 33 (2009), 122-134.doi: 10.1007/s10851-008-0121-2.


    A. Braides, $\Gamma$-convergence for Beginners, volume 22 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2002.doi: 10.1093/acprof:oso/9780198507840.001.0001.


    A. Chambolle, An algorithm for total variation minimization and applications. Special issue on mathematics and image analysis, J. Math. Imaging Vision, 20 (2004), 89-97.doi: 10.1023/B:JMIV.0000011321.19549.88.


    A. Chambolle, V. Caselles, D. Cremers, M. Novaga and T. Pock, An introduction to total variation for image analysis, In Theoretical foundations and numerical methods for sparse recovery, volume 9 of Radon Ser. Comput. Appl. Math., pages 263-340. Walter de Gruyter, Berlin, 2010.doi: 10.1515/9783110226157.263.


    A. Chambolle, V. Caselles and M. Novaga, Total variation in imaging, In O. Scherzer, editor, Handbook of mathematical methods in imaging. Springer Reference. Berlin: Springer, 2011.


    A. Chambolle, D. Cremers and T. Pock, A convex approach to minimal partitions, SIAM J. Imaging Sci.,, 5 (2012), 1113-1158.doi: 10.1137/110856733.


    A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), 120-145.doi: 10.1007/s10851-010-0251-1.


    T. Chan and L. Vese, Active contours without edges, IEEE Trans. Image Processing, 10 (2001), 266-277.doi: 10.1109/83.902291.


    F. R. K. Chung, Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics, Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997.


    G. Dal Maso, An Introduction to $\Gamma$-convergence, Progress in Nonlinear Differential Equations and their Applications, 8. Birkhäuser Boston Inc., Boston, MA, 1993.doi: 10.1007/978-1-4612-0327-8.


    J. A. Dobrosotskaya and A. L. Bertozzi, A wavelet-Laplace variational technique for image deconvolution and inpainting, IEEE Trans. Image Process., 17 (2008), 657-663.doi: 10.1109/TIP.2008.919367.


    J. A. Dobrosotskaya and A. L. Bertozzi, Wavelet analogue of the Ginzburg-Landau energy and its $\Gamma$-convergence, Interfaces Free Bound., 12 (2010), 497-525.doi: 10.4171/IFB/243.


    S. Esedoglu, Blind deconvolution of bar code signals, Inverse Problems, 20 (2004), 121-135.doi: 10.1088/0266-5611/20/1/007.


    S. Esedo$\overlineg$lu and S. J. Osher, Decomposition of images by the anisotropic Rudin-Osher-Fatemi model, Comm. Pure Appl. Math., 57 (2004), 1609-1626.doi: 10.1002/cpa.20045.


    P. Getreuer, Chan-Vese Segmentation, IPOL, 2012.doi: 10.5201/ipol.2012.g-cv.


    A. Henrot and M. PierreVariation et optimisation de formes, volume 48 of Mathématiques & Applications (Berlin) [Mathematics & Applications].


    Y. M. Jung, S. H. Kang and J. Shen, Multiphase image segmentation via Modica-Mortola phase transition, SIAM J. Appl. Math., 67 (2007), 1213-1232.doi: 10.1137/060662708.


    R. V. Kohn and P. Sternberg, Local minimisers and singular perturbations, Proc. Roy. Soc. Edinburgh Sect. A, 111 (1989), 69-84.doi: 10.1017/S0308210500025026.


    L. Modica, The gradient theory of phase transitions and the minimal interface criterion, Arch. Rational Mech. Anal., 98 (1987), 123-142.doi: 10.1007/BF00251230.


    L. Modica and S. Mortola, Un esempio di $\Gamma^{-}$-convergenza, Boll. Un. Mat. Ital. B (5), 14 (1977), 285-299.


    D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Commun. Pure Appl. Math., 42 (1989), 577-685.doi: 10.1002/cpa.3160420503.


    S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79 (1988), 12-49.doi: 10.1016/0021-9991(88)90002-2.


    É. Oudet, Approximation of partitions of least perimeter by $\Gamma$-convergence: around Kelvin's conjecture, Exp. Math., 20 (2011), 260-270.doi: 10.1080/10586458.2011.565233.


    L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.


    J. Shi and J. Malik, Normalize cuts and image segmentation, IEEE Trans. Pat. Anal. Mach. Int., 22 (2000), 888-905.


    M. Solci and E. Vitali, Variational models for phase separation, Interfaces Free Bound., 5 (2003), 27-46.doi: 10.4171/IFB/70.


    L. Vese, A study in the BV space of a denoising-deblurring variational problem, Appl. Math. Optimization, 44 (2001), 131-161.doi: 10.1007/s00245-001-0017-7.


    U. von Luxburg, A tutorial on spectral clustering, Stat. Comput., 17 (2007), 395-416.doi: 10.1007/s11222-007-9033-z.


    C. Zach, D. Gallup, J. Frahm and M. Niethammer, Fast global labelling for real-time stereo using multiple plabe sweeps, In Vision, Modeling, and Visualization. IOS press, 2008.

  • 加载中

Article Metrics

HTML views() PDF downloads(96) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint