# American Institute of Mathematical Sciences

May  2014, 8(2): 361-387. doi: 10.3934/ipi.2014.8.361

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

 1 Laboratoire de Mathématiques d'Avignon, Université d'Avignon, Faculté des Sciences, 33 rue Louis Pasteur, 84000 Avignon, France 2 Laboratório Nacional de Computação Científica LNCC/MCT, Coordenação de Matemática Aplicada e Computacional, Av. Getúlio Vargas 333, 25651-075 Petrópolis - RJ, Brazil 3 Universidade de Lisboa, Faculdade de Ciências, Departamento de Matemática, CMAF, Av. Prof. Gama Pinto 2, 1649-003 Lisboa, Portugal

Received  May 2012 Revised  December 2013 Published  May 2014

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.
Citation: Samuel Amstutz, Antonio André Novotny, Nicolas Van Goethem. Minimal partitions and image classification using a gradient-free perimeter approximation. Inverse Problems and Imaging, 2014, 8 (2) : 361-387. doi: 10.3934/ipi.2014.8.361
##### References:
 [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. [2] G. Allaire, Shape Optimization by the Homogenization Method, volume 146 of Applied Mathematical Sciences, Springer-Verlag, New York, 2002. [3] L. Alvarez, L. Baumela, P. Márquez-Neila and P. Henríquez, A real time morphological snakes algorithm, IPOL, 2012. [4] L. Ambrosio, N. Fusco and D. Palara, Functions of Bounded Variation and Free Discontinuity Problems, Oxford Mathematical Monographs. Oxford, 2000. [5] 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. [6] S. Amstutz, I. Horchani and M. Masmoudi, Crack detection by the topological gradient method, Control Cybernet., 34 (2005), 81-101. [7] 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. [8] 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. [9] 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. [10] 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. [11] 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. [12] 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. [13] 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. [14] 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. [15] 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. [16] 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. [17] 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. [18] 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. [19] T. Chan and L. Vese, Active contours without edges, IEEE Trans. Image Processing, 10 (2001), 266-277. doi: 10.1109/83.902291. [20] 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. [21] 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. [22] 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. [23] 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. [24] S. Esedoglu, Blind deconvolution of bar code signals, Inverse Problems, 20 (2004), 121-135. doi: 10.1088/0266-5611/20/1/007. [25] 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. [26] P. Getreuer, Chan-Vese Segmentation, IPOL, 2012. doi: 10.5201/ipol.2012.g-cv. [27] A. Henrot and M. Pierre, Variation et optimisation de formes, volume 48 of Mathématiques & Applications (Berlin) [Mathematics & Applications]. [28] 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. [29] 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. [30] 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. [31] L. Modica and S. Mortola, Un esempio di $\Gamma^{-}$-convergenza, Boll. Un. Mat. Ital. B (5), 14 (1977), 285-299. [32] 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. [33] 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. [34] É. 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. [35] 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. [36] J. Shi and J. Malik, Normalize cuts and image segmentation, IEEE Trans. Pat. Anal. Mach. Int., 22 (2000), 888-905. [37] M. Solci and E. Vitali, Variational models for phase separation, Interfaces Free Bound., 5 (2003), 27-46. doi: 10.4171/IFB/70. [38] 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. [39] U. von Luxburg, A tutorial on spectral clustering, Stat. Comput., 17 (2007), 395-416. doi: 10.1007/s11222-007-9033-z. [40] 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.

show all references

##### References:
 [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. [2] G. Allaire, Shape Optimization by the Homogenization Method, volume 146 of Applied Mathematical Sciences, Springer-Verlag, New York, 2002. [3] L. Alvarez, L. Baumela, P. Márquez-Neila and P. Henríquez, A real time morphological snakes algorithm, IPOL, 2012. [4] L. Ambrosio, N. Fusco and D. Palara, Functions of Bounded Variation and Free Discontinuity Problems, Oxford Mathematical Monographs. Oxford, 2000. [5] 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. [6] S. Amstutz, I. Horchani and M. Masmoudi, Crack detection by the topological gradient method, Control Cybernet., 34 (2005), 81-101. [7] 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. [8] 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. [9] 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. [10] 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. [11] 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. [12] 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. [13] 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. [14] 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. [15] 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. [16] 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. [17] 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. [18] 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. [19] T. Chan and L. Vese, Active contours without edges, IEEE Trans. Image Processing, 10 (2001), 266-277. doi: 10.1109/83.902291. [20] 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. [21] 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. [22] 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. [23] 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. [24] S. Esedoglu, Blind deconvolution of bar code signals, Inverse Problems, 20 (2004), 121-135. doi: 10.1088/0266-5611/20/1/007. [25] 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. [26] P. Getreuer, Chan-Vese Segmentation, IPOL, 2012. doi: 10.5201/ipol.2012.g-cv. [27] A. Henrot and M. Pierre, Variation et optimisation de formes, volume 48 of Mathématiques & Applications (Berlin) [Mathematics & Applications]. [28] 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. [29] 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. [30] 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. [31] L. Modica and S. Mortola, Un esempio di $\Gamma^{-}$-convergenza, Boll. Un. Mat. Ital. B (5), 14 (1977), 285-299. [32] 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. [33] 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. [34] É. 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. [35] 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. [36] J. Shi and J. Malik, Normalize cuts and image segmentation, IEEE Trans. Pat. Anal. Mach. Int., 22 (2000), 888-905. [37] M. Solci and E. Vitali, Variational models for phase separation, Interfaces Free Bound., 5 (2003), 27-46. doi: 10.4171/IFB/70. [38] 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. [39] U. von Luxburg, A tutorial on spectral clustering, Stat. Comput., 17 (2007), 395-416. doi: 10.1007/s11222-007-9033-z. [40] 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.
 [1] Annibale Magni, Matteo Novaga. A note on non lower semicontinuous perimeter functionals on partitions. Networks and Heterogeneous Media, 2016, 11 (3) : 501-508. doi: 10.3934/nhm.2016006 [2] Jie Huang, Marco Donatelli, Raymond H. Chan. Nonstationary iterated thresholding algorithms for image deblurring. Inverse Problems and Imaging, 2013, 7 (3) : 717-736. doi: 10.3934/ipi.2013.7.717 [3] Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems and Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195 [4] Mónica Clapp, Juan Carlos Fernández, Alberto Saldaña. Critical polyharmonic systems and optimal partitions. Communications on Pure and Applied Analysis, 2021, 20 (11) : 4007-4023. doi: 10.3934/cpaa.2021141 [5] Hassan Emamirad, Arnaud Rougirel. A functional calculus approach for the rational approximation with nonuniform partitions. Discrete and Continuous Dynamical Systems, 2008, 22 (4) : 955-972. doi: 10.3934/dcds.2008.22.955 [6] Antonio De Rosa, Domenico Angelo La Manna. A non local approximation of the Gaussian perimeter: Gamma convergence and Isoperimetric properties. Communications on Pure and Applied Analysis, 2021, 20 (5) : 2101-2116. doi: 10.3934/cpaa.2021059 [7] Mónica Clapp, Angela Pistoia. Yamabe systems and optimal partitions on manifolds with symmetries. Electronic Research Archive, 2021, 29 (6) : 4327-4338. doi: 10.3934/era.2021088 [8] Wenzhong Zhu, Huanlong Jiang, Erli Wang, Yani Hou, Lidong Xian, Joyati Debnath. X-ray image global enhancement algorithm in medical image classification. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1297-1309. doi: 10.3934/dcdss.2019089 [9] Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems and Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022 [10] Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems and Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591 [11] Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems and Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321 [12] Florian Bossmann, Jianwei Ma. Enhanced image approximation using shifted rank-1 reconstruction. Inverse Problems and Imaging, 2020, 14 (2) : 267-290. doi: 10.3934/ipi.2020012 [13] Yuantian Xia, Juxiang Zhou, Tianwei Xu, Wei Gao. An improved deep convolutional neural network model with kernel loss function in image classification. Mathematical Foundations of Computing, 2020, 3 (1) : 51-64. doi: 10.3934/mfc.2020005 [14] Robert Baier, Matthias Gerdts, Ilaria Xausa. Approximation of reachable sets using optimal control algorithms. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 519-548. doi: 10.3934/naco.2013.3.519 [15] Marcus Wagner. A direct method for the solution of an optimal control problem arising from image registration. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 487-510. doi: 10.3934/naco.2012.2.487 [16] Angel Angelov, Marcus Wagner. Multimodal image registration by elastic matching of edge sketches via optimal control. Journal of Industrial and Management Optimization, 2014, 10 (2) : 567-590. doi: 10.3934/jimo.2014.10.567 [17] Yangang Chen, Justin W. L. Wan. Numerical method for image registration model based on optimal mass transport. Inverse Problems and Imaging, 2018, 12 (2) : 401-432. doi: 10.3934/ipi.2018018 [18] Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems and Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171 [19] Luigi Ambrosio, Michele Miranda jr., Diego Pallara. Sets with finite perimeter in Wiener spaces, perimeter measure and boundary rectifiability. Discrete and Continuous Dynamical Systems, 2010, 28 (2) : 591-606. doi: 10.3934/dcds.2010.28.591 [20] Virginie Bonnaillie-Noël, Corentin Léna. Spectral minimal partitions of a sector. Discrete and Continuous Dynamical Systems - B, 2014, 19 (1) : 27-53. doi: 10.3934/dcdsb.2014.19.27

2021 Impact Factor: 1.483