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]

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.  Google Scholar

[2]

Springer-Verlag, New York, 2002.  Google Scholar

[3]

IPOL, 2012. Google Scholar

[4]

Oxford Mathematical Monographs. Oxford, 2000.  Google Scholar

[5]

Comm. Pure Appl. Math., 43 (1990), 999-1036. doi: 10.1002/cpa.3160430805.  Google Scholar

[6]

Control Cybernet., 34 (2005), 81-101.  Google Scholar

[7]

Interfaces and Free Boundaries, 14 (2012), 401-430. doi: 10.4171/IFB/286.  Google Scholar

[8]

Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006. Applications to PDEs and optimization.  Google Scholar

[9]

Applicable Analysis, 84 (2005), 15-35. doi: 10.1080/0003681042000267920.  Google Scholar

[10]

Int. J. Comp. Vision, 67 (2006), 111-136. doi: 10.1007/s11263-006-4331-z.  Google Scholar

[11]

ESAIM, Math. Model. Numer. Anal., 41 (2007), 607-625. doi: 10.1051/m2an:2007027.  Google Scholar

[12]

J. Math. Imaging Vision, 33 (2009), 122-134. doi: 10.1007/s10851-008-0121-2.  Google Scholar

[13]

Oxford University Press, Oxford, 2002. doi: 10.1093/acprof:oso/9780198507840.001.0001.  Google Scholar

[14]

J. Math. Imaging Vision, 20 (2004), 89-97. doi: 10.1023/B:JMIV.0000011321.19549.88.  Google Scholar

[15]

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.  Google Scholar

[16]

In O. Scherzer, editor, Handbook of mathematical methods in imaging. Springer Reference. Berlin: Springer, 2011. Google Scholar

[17]

SIAM J. Imaging Sci.,, 5 (2012), 1113-1158. doi: 10.1137/110856733.  Google Scholar

[18]

J. Math. Imaging Vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.  Google Scholar

[19]

IEEE Trans. Image Processing, 10 (2001), 266-277. doi: 10.1109/83.902291.  Google Scholar

[20]

Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997.  Google Scholar

[21]

Progress in Nonlinear Differential Equations and their Applications, 8. Birkhäuser Boston Inc., Boston, MA, 1993. doi: 10.1007/978-1-4612-0327-8.  Google Scholar

[22]

IEEE Trans. Image Process., 17 (2008), 657-663. doi: 10.1109/TIP.2008.919367.  Google Scholar

[23]

Interfaces Free Bound., 12 (2010), 497-525. doi: 10.4171/IFB/243.  Google Scholar

[24]

Inverse Problems, 20 (2004), 121-135. doi: 10.1088/0266-5611/20/1/007.  Google Scholar

[25]

Comm. Pure Appl. Math., 57 (2004), 1609-1626. doi: 10.1002/cpa.20045.  Google Scholar

[26]

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]

SIAM J. Appl. Math., 67 (2007), 1213-1232. doi: 10.1137/060662708.  Google Scholar

[29]

Proc. Roy. Soc. Edinburgh Sect. A, 111 (1989), 69-84. doi: 10.1017/S0308210500025026.  Google Scholar

[30]

Arch. Rational Mech. Anal., 98 (1987), 123-142. doi: 10.1007/BF00251230.  Google Scholar

[31]

Boll. Un. Mat. Ital. B (5), 14 (1977), 285-299.  Google Scholar

[32]

Commun. Pure Appl. Math., 42 (1989), 577-685. doi: 10.1002/cpa.3160420503.  Google Scholar

[33]

J. Comput. Phys., 79 (1988), 12-49. doi: 10.1016/0021-9991(88)90002-2.  Google Scholar

[34]

Exp. Math., 20 (2011), 260-270. doi: 10.1080/10586458.2011.565233.  Google Scholar

[35]

Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[36]

IEEE Trans. Pat. Anal. Mach. Int., 22 (2000), 888-905. Google Scholar

[37]

Interfaces Free Bound., 5 (2003), 27-46. doi: 10.4171/IFB/70.  Google Scholar

[38]

Appl. Math. Optimization, 44 (2001), 131-161. doi: 10.1007/s00245-001-0017-7.  Google Scholar

[39]

Stat. Comput., 17 (2007), 395-416. doi: 10.1007/s11222-007-9033-z.  Google Scholar

[40]

In Vision, Modeling, and Visualization. IOS press, 2008. Google Scholar

show all references

References:
[1]

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.  Google Scholar

[2]

Springer-Verlag, New York, 2002.  Google Scholar

[3]

IPOL, 2012. Google Scholar

[4]

Oxford Mathematical Monographs. Oxford, 2000.  Google Scholar

[5]

Comm. Pure Appl. Math., 43 (1990), 999-1036. doi: 10.1002/cpa.3160430805.  Google Scholar

[6]

Control Cybernet., 34 (2005), 81-101.  Google Scholar

[7]

Interfaces and Free Boundaries, 14 (2012), 401-430. doi: 10.4171/IFB/286.  Google Scholar

[8]

Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006. Applications to PDEs and optimization.  Google Scholar

[9]

Applicable Analysis, 84 (2005), 15-35. doi: 10.1080/0003681042000267920.  Google Scholar

[10]

Int. J. Comp. Vision, 67 (2006), 111-136. doi: 10.1007/s11263-006-4331-z.  Google Scholar

[11]

ESAIM, Math. Model. Numer. Anal., 41 (2007), 607-625. doi: 10.1051/m2an:2007027.  Google Scholar

[12]

J. Math. Imaging Vision, 33 (2009), 122-134. doi: 10.1007/s10851-008-0121-2.  Google Scholar

[13]

Oxford University Press, Oxford, 2002. doi: 10.1093/acprof:oso/9780198507840.001.0001.  Google Scholar

[14]

J. Math. Imaging Vision, 20 (2004), 89-97. doi: 10.1023/B:JMIV.0000011321.19549.88.  Google Scholar

[15]

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.  Google Scholar

[16]

In O. Scherzer, editor, Handbook of mathematical methods in imaging. Springer Reference. Berlin: Springer, 2011. Google Scholar

[17]

SIAM J. Imaging Sci.,, 5 (2012), 1113-1158. doi: 10.1137/110856733.  Google Scholar

[18]

J. Math. Imaging Vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.  Google Scholar

[19]

IEEE Trans. Image Processing, 10 (2001), 266-277. doi: 10.1109/83.902291.  Google Scholar

[20]

Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997.  Google Scholar

[21]

Progress in Nonlinear Differential Equations and their Applications, 8. Birkhäuser Boston Inc., Boston, MA, 1993. doi: 10.1007/978-1-4612-0327-8.  Google Scholar

[22]

IEEE Trans. Image Process., 17 (2008), 657-663. doi: 10.1109/TIP.2008.919367.  Google Scholar

[23]

Interfaces Free Bound., 12 (2010), 497-525. doi: 10.4171/IFB/243.  Google Scholar

[24]

Inverse Problems, 20 (2004), 121-135. doi: 10.1088/0266-5611/20/1/007.  Google Scholar

[25]

Comm. Pure Appl. Math., 57 (2004), 1609-1626. doi: 10.1002/cpa.20045.  Google Scholar

[26]

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]

SIAM J. Appl. Math., 67 (2007), 1213-1232. doi: 10.1137/060662708.  Google Scholar

[29]

Proc. Roy. Soc. Edinburgh Sect. A, 111 (1989), 69-84. doi: 10.1017/S0308210500025026.  Google Scholar

[30]

Arch. Rational Mech. Anal., 98 (1987), 123-142. doi: 10.1007/BF00251230.  Google Scholar

[31]

Boll. Un. Mat. Ital. B (5), 14 (1977), 285-299.  Google Scholar

[32]

Commun. Pure Appl. Math., 42 (1989), 577-685. doi: 10.1002/cpa.3160420503.  Google Scholar

[33]

J. Comput. Phys., 79 (1988), 12-49. doi: 10.1016/0021-9991(88)90002-2.  Google Scholar

[34]

Exp. Math., 20 (2011), 260-270. doi: 10.1080/10586458.2011.565233.  Google Scholar

[35]

Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[36]

IEEE Trans. Pat. Anal. Mach. Int., 22 (2000), 888-905. Google Scholar

[37]

Interfaces Free Bound., 5 (2003), 27-46. doi: 10.4171/IFB/70.  Google Scholar

[38]

Appl. Math. Optimization, 44 (2001), 131-161. doi: 10.1007/s00245-001-0017-7.  Google Scholar

[39]

Stat. Comput., 17 (2007), 395-416. doi: 10.1007/s11222-007-9033-z.  Google Scholar

[40]

In Vision, Modeling, and Visualization. IOS press, 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]

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

[4]

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

[5]

Antonio De Rosa, Domenico Angelo La Manna. A non local approximation of the Gaussian perimeter: Gamma convergence and Isoperimetric properties. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021059

[6]

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

[7]

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

[8]

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

[9]

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

[10]

Florian Bossmann, Jianwei Ma. Enhanced image approximation using shifted rank-1 reconstruction. Inverse Problems & Imaging, 2020, 14 (2) : 267-290. doi: 10.3934/ipi.2020012

[11]

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

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

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2019 Impact Factor: 1.373

Metrics

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

[Back to Top]