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 & 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, (1964). Google Scholar

[2]

G. Allaire, Shape Optimization by the Homogenization Method, volume 146 of Applied Mathematical Sciences,, Springer-Verlag, (2002). Google Scholar

[3]

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

[4]

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

[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. doi: 10.1002/cpa.3160430805. Google Scholar

[6]

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

[7]

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

[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), (2006). Google Scholar

[9]

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

[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. doi: 10.1007/s11263-006-4331-z. Google Scholar

[11]

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

[12]

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

[13]

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

[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. doi: 10.1023/B:JMIV.0000011321.19549.88. Google Scholar

[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, (2010), 263. doi: 10.1515/9783110226157.263. Google Scholar

[16]

A. Chambolle, V. Caselles and M. Novaga, Total variation in imaging,, In O. Scherzer, (2011). Google Scholar

[17]

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

[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. doi: 10.1007/s10851-010-0251-1. Google Scholar

[19]

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

[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, (1997). Google Scholar

[21]

G. Dal Maso, An Introduction to $\Gamma$-convergence,, Progress in Nonlinear Differential Equations and their Applications, (1993). doi: 10.1007/978-1-4612-0327-8. Google Scholar

[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. doi: 10.1109/TIP.2008.919367. Google Scholar

[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. doi: 10.4171/IFB/243. Google Scholar

[24]

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

[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. doi: 10.1002/cpa.20045. Google Scholar

[26]

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

[27]

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

[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. doi: 10.1137/060662708. Google Scholar

[29]

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

[30]

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

[31]

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

[32]

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

[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. doi: 10.1016/0021-9991(88)90002-2. Google Scholar

[34]

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

[35]

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

[36]

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

[37]

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

[38]

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

[39]

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

[40]

C. Zach, D. Gallup, J. Frahm and M. Niethammer, Fast global labelling for real-time stereo using multiple plabe sweeps,, In Vision, (2008). Google Scholar

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, (1964). Google Scholar

[2]

G. Allaire, Shape Optimization by the Homogenization Method, volume 146 of Applied Mathematical Sciences,, Springer-Verlag, (2002). Google Scholar

[3]

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

[4]

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

[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. doi: 10.1002/cpa.3160430805. Google Scholar

[6]

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

[7]

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

[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), (2006). Google Scholar

[9]

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

[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. doi: 10.1007/s11263-006-4331-z. Google Scholar

[11]

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

[12]

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

[13]

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

[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. doi: 10.1023/B:JMIV.0000011321.19549.88. Google Scholar

[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, (2010), 263. doi: 10.1515/9783110226157.263. Google Scholar

[16]

A. Chambolle, V. Caselles and M. Novaga, Total variation in imaging,, In O. Scherzer, (2011). Google Scholar

[17]

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

[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. doi: 10.1007/s10851-010-0251-1. Google Scholar

[19]

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

[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, (1997). Google Scholar

[21]

G. Dal Maso, An Introduction to $\Gamma$-convergence,, Progress in Nonlinear Differential Equations and their Applications, (1993). doi: 10.1007/978-1-4612-0327-8. Google Scholar

[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. doi: 10.1109/TIP.2008.919367. Google Scholar

[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. doi: 10.4171/IFB/243. Google Scholar

[24]

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

[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. doi: 10.1002/cpa.20045. Google Scholar

[26]

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

[27]

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

[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. doi: 10.1137/060662708. Google Scholar

[29]

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

[30]

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

[31]

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

[32]

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

[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. doi: 10.1016/0021-9991(88)90002-2. Google Scholar

[34]

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

[35]

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

[36]

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

[37]

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

[38]

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

[39]

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

[40]

C. Zach, D. Gallup, J. Frahm and M. Niethammer, Fast global labelling for real-time stereo using multiple plabe sweeps,, In Vision, (2008). Google Scholar

[1]

Annibale Magni, Matteo Novaga. A note on non lower semicontinuous perimeter functionals on partitions. Networks & 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 & Imaging, 2013, 7 (3) : 717-736. doi: 10.3934/ipi.2013.7.717

[3]

Hassan Emamirad, Arnaud Rougirel. A functional calculus approach for the rational approximation with nonuniform partitions. Discrete & Continuous Dynamical Systems - A, 2008, 22 (4) : 955-972. doi: 10.3934/dcds.2008.22.955

[4]

Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems & Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195

[5]

Wenzhong Zhu, Huanlong Jiang, Erli Wang, Yani Hou, Lidong Xian, Joyati Debnath. X-ray image global enhancement algorithm in medical image classification. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1297-1309. doi: 10.3934/dcdss.2019089

[6]

Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems & Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022

[7]

Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems & Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591

[8]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[9]

Robert Baier, Matthias Gerdts, Ilaria Xausa. Approximation of reachable sets using optimal control algorithms. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 519-548. doi: 10.3934/naco.2013.3.519

[10]

Marcus Wagner. A direct method for the solution of an optimal control problem arising from image registration. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 487-510. doi: 10.3934/naco.2012.2.487

[11]

Angel Angelov, Marcus Wagner. Multimodal image registration by elastic matching of edge sketches via optimal control. Journal of Industrial & Management Optimization, 2014, 10 (2) : 567-590. doi: 10.3934/jimo.2014.10.567

[12]

Yangang Chen, Justin W. L. Wan. Numerical method for image registration model based on optimal mass transport. Inverse Problems & Imaging, 2018, 12 (2) : 401-432. doi: 10.3934/ipi.2018018

[13]

Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems & Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171

[14]

Virginie Bonnaillie-Noël, Corentin Léna. Spectral minimal partitions of a sector. Discrete & Continuous Dynamical Systems - B, 2014, 19 (1) : 27-53. doi: 10.3934/dcdsb.2014.19.27

[15]

Luigi Ambrosio, Michele Miranda jr., Diego Pallara. Sets with finite perimeter in Wiener spaces, perimeter measure and boundary rectifiability. Discrete & Continuous Dynamical Systems - A, 2010, 28 (2) : 591-606. doi: 10.3934/dcds.2010.28.591

[16]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[17]

Andrzej Just, Zdzislaw Stempień. Optimal control problem for a viscoelastic beam and its galerkin approximation. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 263-274. doi: 10.3934/dcdsb.2018018

[18]

Lili Chang, Wei Gong, Guiquan Sun, Ningning Yan. PDE-constrained optimal control approach for the approximation of an inverse Cauchy problem. Inverse Problems & Imaging, 2015, 9 (3) : 791-814. doi: 10.3934/ipi.2015.9.791

[19]

Mou-Hsiung Chang, Tao Pang, Moustapha Pemy. Finite difference approximation for stochastic optimal stopping problems with delays. Journal of Industrial & Management Optimization, 2008, 4 (2) : 227-246. doi: 10.3934/jimo.2008.4.227

[20]

Peter I. Kogut. On approximation of an optimal boundary control problem for linear elliptic equation with unbounded coefficients. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 2105-2133. doi: 10.3934/dcds.2014.34.2105

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (3)

[Back to Top]