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]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[2]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[3]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[4]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[5]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[6]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020271

[7]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[8]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013

[9]

Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246

[10]

Wenjun Liu, Yukun Xiao, Xiaoqing Yue. Classification of finite irreducible conformal modules over Lie conformal algebra $ \mathcal{W}(a, b, r) $. Electronic Research Archive, , () : -. doi: 10.3934/era.2020123

[11]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[12]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[13]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[14]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[15]

Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032

[16]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (42)
  • HTML views (0)
  • Cited by (4)

[Back to Top]