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).

[2]

G. Allaire, Shape Optimization by the Homogenization Method, volume 146 of Applied Mathematical Sciences,, Springer-Verlag, (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. 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.

[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.

[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).

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[16]

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

[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.

[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.

[19]

T. Chan and L. Vese, Active contours without edges,, IEEE Trans. Image Processing, 10 (2001), 266. 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, (1997).

[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.

[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.

[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.

[24]

S. Esedoglu, Blind deconvolution of bar code signals,, Inverse Problems, 20 (2004), 121. 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. 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. 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. 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. doi: 10.1007/BF00251230.

[31]

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

[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.

[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.

[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.

[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.

[36]

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

[37]

M. Solci and E. Vitali, Variational models for phase separation,, Interfaces Free Bound., 5 (2003), 27. 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. doi: 10.1007/s00245-001-0017-7.

[39]

U. von Luxburg, A tutorial on spectral clustering,, Stat. Comput., 17 (2007), 395. 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, (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, (1964).

[2]

G. Allaire, Shape Optimization by the Homogenization Method, volume 146 of Applied Mathematical Sciences,, Springer-Verlag, (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. 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.

[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.

[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).

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[16]

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

[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.

[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.

[19]

T. Chan and L. Vese, Active contours without edges,, IEEE Trans. Image Processing, 10 (2001), 266. 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, (1997).

[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.

[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.

[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.

[24]

S. Esedoglu, Blind deconvolution of bar code signals,, Inverse Problems, 20 (2004), 121. 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. 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. 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. 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. doi: 10.1007/BF00251230.

[31]

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

[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.

[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.

[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.

[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.

[36]

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

[37]

M. Solci and E. Vitali, Variational models for phase separation,, Interfaces Free Bound., 5 (2003), 27. 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. doi: 10.1007/s00245-001-0017-7.

[39]

U. von Luxburg, A tutorial on spectral clustering,, Stat. Comput., 17 (2007), 395. 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, (2008).

[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]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Liuyang Yuan, Zhongping Wan, Qiuhua Tang. A criterion for an approximation global optimal solution based on the filled functions. Journal of Industrial & Management Optimization, 2016, 12 (1) : 375-387. doi: 10.3934/jimo.2016.12.375

2017 Impact Factor: 1.465

Metrics

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

[Back to Top]