Partial differential equations and variational methods for geometric processing of images. (English) Zbl 1476.49007
This paper is the output of a minisymposium, held in 2018 at the 9th International Conference on Curves and Surface in Arcachon, France, which featured a variety of recent developments of geometric partial differential equations and variational models which are directly or indirectly related to several problems in image and data processing.
The paper involves the talks of Blanche Buet, Jean-Marie Mirebeau, and Yves van Gennip, who were three minisymposium speakers.
Section 1 of the paper is about the talk of Yves van Gennip. This talk gives an overview of recent research activities in the field of PDEs on graphs and focused on techniques related to the graph Ginzburg-Landau variational model.
Section 2 was written by Jean-Marie Mirebeau, François Desquilbet, Johann Dreo, and Frédéric Barbaresco. This section gives recent numerical method devoted to computing curves that globally minimize an energy featuring both a data driven term, and a second order curvature penalizing term. Some applications to image segmentation and recent research progress on radar network configuration are given.
Section 3 is on the work of Blanche Buet, Gian Paolo Leonardi, and Simon Masnou on the definition and the approximation of weak curvatures for a large class of generalized surfaces, and in particular for point clouds, based on the geometric measure theoretic notion of varifolds. Details discussions are also given.
The paper involves the talks of Blanche Buet, Jean-Marie Mirebeau, and Yves van Gennip, who were three minisymposium speakers.
Section 1 of the paper is about the talk of Yves van Gennip. This talk gives an overview of recent research activities in the field of PDEs on graphs and focused on techniques related to the graph Ginzburg-Landau variational model.
Section 2 was written by Jean-Marie Mirebeau, François Desquilbet, Johann Dreo, and Frédéric Barbaresco. This section gives recent numerical method devoted to computing curves that globally minimize an energy featuring both a data driven term, and a second order curvature penalizing term. Some applications to image segmentation and recent research progress on radar network configuration are given.
Section 3 is on the work of Blanche Buet, Gian Paolo Leonardi, and Simon Masnou on the definition and the approximation of weak curvatures for a large class of generalized surfaces, and in particular for point clouds, based on the geometric measure theoretic notion of varifolds. Details discussions are also given.
Reviewer: Yekini Shehu (Nsukka)
MSC:
| 49J20 | Existence theories for optimal control problems involving partial differential equations |
| 49J35 | Existence of solutions for minimax problems |
| 68U10 | Computing methodologies for image processing |
Software:
CMA-ESReferences:
| [1] | Allard, W. K., On the first variation of a varifold., Ann. Math., 95, 417-491 (1972) · Zbl 0252.49028 · doi:10.2307/1970868 |
| [2] | Almgren, F.; Taylor, J. E.; Wang, L., Curvature-driven flows: a variational approach, SIAM J. Control Optimization, 31, 2, 387-438 (1993) · Zbl 0783.35002 · doi:10.1137/0331020 |
| [3] | Anderson, C. R., A Rayleigh-Chebyshev procedure for finding the smallest eigenvalues and associated eigenvectors of large sparse Hermitian matrices, J. Comput. Phys., 229, 19, 7477-7487 (2010) · Zbl 1197.65034 · doi:10.1016/j.jcp.2010.06.030 |
| [4] | Barbaresco, F., Computation of most threatening radar trajectories areas and corridors based on fast-marching & level sets, IEEE Symposium on Computational Intelligence for Security and Defence Applications, 51-58 (2011) |
| [5] | Bardi, M.; Capuzzo-Dolcetta, I., Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations (2008), Birkhäuser · Zbl 1134.49002 |
| [6] | Barles, G.; Georgelin, C., A simple proof of convergence for an approximation scheme for computing motions by mean curvature, SIAM J. Numer. Anal., 32, 2, 484-500 (1995) · Zbl 0831.65138 · doi:10.1137/0732020 |
| [7] | Barles, G.; Soner, H. M.; Souganidis, P. E., Front propagation and phase field theory, SIAM J. Control Optimization, 31, 2, 439-469 (1993) · Zbl 0785.35049 · doi:10.1137/0331021 |
| [8] | Bertozzi, A. L.; Flenner, A., Diffuse interface models on graphs for analysis of high dimensional data, SIAM J. Multiscale Mod. Simul., 10, 3, 1090-1118 (2012) · Zbl 1259.68215 · doi:10.1137/11083109X |
| [9] | Bogachev, V. I., Measure Theory II (2007), Springer · Zbl 1120.28001 |
| [10] | Boschand, J.; Klamt, S.; Stoll, M., Generalizing diffuse interface methods on graphs: non-smooth potentials and hypergraphs, SIAM J. Appl. Math., 78, 3, 1350-1377 (2018) · Zbl 1385.68032 |
| [11] | Braides, A., \( \Gamma \)-convergence for beginners (2002), Oxford University Press · Zbl 1198.49001 · doi:10.1093/acprof:oso/9780198507840.001.0001 |
| [12] | Brakke, K. A., The motion of a surface by its mean curvature (1978), Princeton University Press · Zbl 0386.53047 |
| [13] | Bresson, X.; Chan, T. F., Non-local Unsupervised Variational Image Segmentation (2008) |
| [14] | Bronsard, L.; Kohn, R. V., Motion by mean curvature as the singular limit of Ginzburg-Landau dynamics, J. Differ. Equations, 90, 2, 211-237 (1991) · Zbl 0735.35072 · doi:10.1016/0022-0396(91)90147-2 |
| [15] | Budd, J.; van Gennip, Y., Mass-preserving diffusion-based dynamics on graphs · Zbl 1509.34029 |
| [16] | Budd, J.; van Gennip, Y., Graph MBO as a semi-discrete implicit Euler scheme for graph Allen-Cahn (2019) |
| [17] | Buet, B.; Leonardi, G. P.; Masnou, S., A varifold approach to surface approximation., Arch. Ration. Mech. Anal., 226, 639-694 (2017) · Zbl 1378.49052 · doi:10.1007/s00205-017-1141-0 |
| [18] | Buet, B.; Leonardi, G. P.; Masnou, S., Weak and approximate curvatures of a measure: a varifold perspective. (2019) |
| [19] | Calatroni, L.; van Gennip, Y.; Schönlieb, C.-B.; Rowland, H.; Flenner, A., Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images, J. Math. Imaging Vis., 57, 2, 269-291 (2017) · Zbl 1369.94019 · doi:10.1007/s10851-016-0678-0 |
| [20] | Calder, J., Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data (2017) |
| [21] | Calder, J., The game theoretic \(p\)-Laplacian and semi-supervised learning with few labels, Nonlinearity, 32, 1, 301-330 (2018) · Zbl 1408.35048 · doi:10.1088/1361-6544/aae949 |
| [22] | Calder, J.; Slepčev, D., Properly-weighted graph Laplacian for semi-supervised learning (2018) |
| [23] | Chen, D.; Mirebeau, J.-M.; Cohen, L. D., Global minimum for a Finsler Elastica minimal path approach, Int. J. Comput. Vision, 122, 3, 458-483 (2017) · Zbl 1477.68341 · doi:10.1007/s11263-016-0975-5 |
| [24] | Chung, F., Spectral Graph Theory (1997), American Mathematical Society · Zbl 0867.05046 |
| [25] | Cohen, L. D.; Kimmel, R., Global minimum for active contour models: A minimal path approach., Int. J. Comput. Vision, 24, 1, 57-78 (1997) · doi:10.1023/A:1007922224810 |
| [26] | Cucuringu, M.; Pizzoferrato, A.; van Gennip, Y., An MBO scheme for clustering and semi-supervised clustering of signed networks (2019) · Zbl 1479.90046 |
| [27] | Dal Maso, G., An introduction to \(\Gamma \)-convergence (1993), Birkhäuser · Zbl 0816.49001 |
| [28] | Digne, J.; Audfray, N.; Lartigue, C.; Mehdi-Souzani, C.; Morel, J.-M., Farman Institute 3D Point Sets - High Precision 3D Data Sets, IPOL Journal, 1, 281-291 (2011) |
| [29] | Dreo, J.; Desquilbet, F.; Barbaresco, F.; Mirebeau, J.-M., Netted multi-function radars positioning and modes selection by non-holonomic fast marching computation of highest threatening trajectories, International RADAR’19 conference (2019), IEEE |
| [30] | Duits, R.; Meesters, S. P. L.; Mirebeau, J.-M.; Portegies, J. M., Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis, J. Math. Imaging Vis., 1-33 (2018) · Zbl 1398.65135 |
| [31] | Dunlop, M. M.; Slepčev, D.; Stuart, A. M.; Thorpe, M., Large data and zero noise limits of graph-based semi-supervised learning algorithms (2018) · Zbl 1442.62768 |
| [32] | Elmoataz, A.; Buyssens, P., On the connection between tug-of-war games and nonlocal PDEs on graphs, C. R. Méc. Acad. Sci. Paris, 345, 3, 177-183 (2017) |
| [33] | Elmoataz, A.; Desquesnes, X.; Lézoray, O., Non-local morphological PDEs and p-Laplacian equation on graphs with applications in image processing and machine learning, IEEE Sel. Top. Signal Process., 6, 7, 764-779 (2012) · doi:10.1109/JSTSP.2012.2216504 |
| [34] | Elmoataz, A.; Desquesnes, X.; Toutain, M., On the game \(p\)-Laplacian on weighted graphs with applications in image processing and data clustering, Eur. J. Appl. Math., 28, 922-948 (2017) · Zbl 1390.91039 · doi:10.1017/S0956792517000122 |
| [35] | Evans, L. C., Convergence of an algorithm for mean curvature motion, Indiana Univ. Math. J., 42, 2, 533-557 (1993) · Zbl 0802.65098 · doi:10.1512/iumj.1993.42.42024 |
| [36] | Fowlkes, C.; Belongie, S.; Chung, F.; Malik, J., Spectral grouping using the Nystrom method, IEEE Trans. Pattern Anal. Mach. Intell., 26, 2, 214-225 (2004) · doi:10.1109/TPAMI.2004.1262185 |
| [37] | Garcia-Cardona, C.; Flenner, A.; Percus, A. G., Multiclass diffuse interface models for semi-supervised learning on graphs, Proceedings of the 2nd International Conference on Pattern Recognition Applications and Methods (ICPRAM 2013), 78-86 (2013) |
| [38] | Garcia-Cardona, C.; Flenner, A.; Percus, A. G., Multiclass semi-supervised learning on graphs using Ginzburg-Landau functional minimization, Adv. Intell. Syst. Comput., 318, 19-135 (2015) |
| [39] | Garcia-Cardona, C.; Merkurjev, E.; Bertozzi, A. L.; Flenner, A.; Percus, A. G., Multiclass data segmentation using diffuse interface methods on graphs, IEEE Trans. Pattern Anal. Mach. Intell., 36, 1600-1613 (2014) · Zbl 1329.68222 · doi:10.1109/TPAMI.2014.2300478 |
| [40] | Garcia Trillos, N.; Murray, R., A new analytical approach to consistency and overfitting in regularized empirical risk minimization, Eur. J. Appl. Math., 28, 886-921 (2017) · Zbl 1383.49029 · doi:10.1017/S0956792517000201 |
| [41] | Garcia Trillos, N.; Murray, R., A maximum principle argument for the uniform convergence of graph Laplacian regressors (2019) |
| [42] | Garcia Trillos, N.; Slepčev, D., Continuum limit of total variation on point clouds, Arch. Ration. Mech. Anal., 220, 1, 193-241 (2016) · Zbl 1336.68215 · doi:10.1007/s00205-015-0929-z |
| [43] | Garcia Trillos, N.; Slepčev, D.; von Brecht, J.; Laurent, T.; Bresson, X., Consistency of Cheeger and Ratio Graph Cuts, J. Mach. Learn. Res., 17, 1-46 (2016) · Zbl 1392.62180 |
| [44] | Gilboa, G.; Osher, S. J., Nonlocal Operators with Applications to Image Processing, SIAM J. Multiscale Mod. Simul., 7, 3, 1005-1028 (2008) · Zbl 1181.35006 · doi:10.1137/070698592 |
| [45] | Hafiene, Y.; Fadili, J.; Elmoataz, A., Nonlocal \(p\)-Laplacian evolution problems on graphs, SIAM J. Numer. Anal., 56, 2, 1064-1090 (2018) · Zbl 1448.65200 · doi:10.1137/17M1123596 |
| [46] | Hafiene, Y.; Fadili, J.; Elmoataz, A., Nonlocal \(p\)-Laplacian variational problems on graphs (2018) · Zbl 1448.65200 |
| [47] | Hansen, N.; Müller, S. D.; Koumoutsakos, P., Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)., Evol. Comput., 11, 1, 1-18 (2003) · doi:10.1162/106365603321828970 |
| [48] | Hutchinson, J. E., Geometric measure theory and the calculus of variations, \(44, {C}^{1,\alpha }\) multiple function regularity and tangent cone behaviour for varifolds with second fundamental form in \({L}^p\). (1986), American Mathematical Society · Zbl 0635.49020 · doi:10.1090/pspum/044/840281 |
| [49] | Hutchinson, J. E., Second fundamental form for varifolds and the existence of surfaces minimising curvature., Indiana Univ. Math. J., 35, 1 (1986) · Zbl 0561.53008 · doi:10.1512/iumj.1986.35.35003 |
| [50] | Kass, M.; Witkin, A.; Terzopoulos, D., Snakes: Active contour models., Int. J. Comput. Vision, 14, 321-331 (1988) · doi:10.1007/BF00133570 |
| [51] | Keetch, B.; van Gennip, Y., Approximation of the Max-K-Cut via a signless graph Allen-Cahn equation |
| [52] | Keetch, B.; van Gennip, Y., A Max-Cut approximation using a graph based MBO scheme (2017) · Zbl 1421.05086 |
| [53] | Liao, W.; Rohr, K.; Wörz, S., Globally Optimal Curvature - Regularized Fast Marching For Vessel Segmentation,, Medical Image Computing and Computer-Assisted Intervention - MICCAI 2013, 550-557 (2013), Springer |
| [54] | Lozes, F.; Hidane, M.; Elmoataz, A.; Lezoray, O., Nonlocal segmentation of point clouds with graphs, 2013 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013 - Proceedings, 459-462 (2013) · doi:10.1109/GlobalSIP.2013.6736914 |
| [55] | Luckhaus, S.; Sturzenhecker, T., Implicit time discretization for the mean curvature flow equation, Calc. Var. Partial Differ. Equ., 3, 2, 253-271 (1995) · Zbl 0821.35003 · doi:10.1007/BF01205007 |
| [56] | Luo, X.; Bertozzi, A. L., Convergence of the graph Allen-Cahn scheme, J. Stat. Phys., 167, 3, 934-958 (2017) · Zbl 1375.82023 · doi:10.1007/s10955-017-1772-4 |
| [57] | Manfredi, J. J.; Oberman, A. M.; Sviridov, A. P., Nonlinear elliptic partial differential equations and \(p\)-harmonic functions on graphs, Differ. Integral Equ., 28, 1-2, 79-102 (2015) · Zbl 1349.35382 |
| [58] | Medvedev, G. S., The nonlinear heat equation on dense graphs and graph limits, SIAM J. Math. Anal., 46, 4, 2743-2766 (2014) · Zbl 1307.34062 · doi:10.1137/130943741 |
| [59] | Meng, Z.; Merkurjev, E.; Koniges, A.; Bertozzi, A. L., Hyperspectral Image Classification Using Graph Clustering Methods, IPOL Journal, 7, 218-245 (2017) · doi:10.5201/ipol.2017.204 |
| [60] | Merkurjev, E.; Garcia-Cardona, C.; Bertozzi, A. L.; Flenner, A.; Percus, A. G., Diffuse interface methods for multiclass segmentation of high-dimensional data, Appl. Math. Lett., 33, 29-34 (2014) · Zbl 1329.68222 · doi:10.1016/j.aml.2014.02.008 |
| [61] | Merkurjev, E.; Kostic, T.; Bertozzi, A. L., An MBO scheme on graphs for segmentation and image processing, SIAM J. Imaging Sci., 6, 4, 1903-1930 (2013) · Zbl 1279.68335 · doi:10.1137/120886935 |
| [62] | Merriman, B.; Bence, J. K.; Osher, S. J., Motion of multiple functions: a level set approach, J. Comput. Phys., 112, 2, 334-363 (1994) · Zbl 0805.65090 · doi:10.1006/jcph.1994.1105 |
| [63] | Mirebeau, J.-M., Fast-marching methods for curvature penalized shortest paths., J. Math. Imaging Vis., 1-32 (2017) |
| [64] | Mirebeau, J.-M.; Dreo, J., Automatic differentiation of non-holonomic fast marching for computing most threatening trajectories under sensors surveillance., Geometrical Science of Information (2017) · Zbl 1428.65002 · doi:10.1007/978-3-319-68445-1_91 |
| [65] | Mirebeau, J.-M.; Portegies, J. M., Hamiltonian fast marching: A numerical solver for anisotropic and non-holonomic eikonal PDEs., IPOL Journal, 9, 47-93 (2019) · doi:10.5201/ipol.2019.227 |
| [66] | Modica, L., The gradient theory of phase transitions and the minimal interface criterion, Arch. Ration. Mech. Anal., 98, 2, 123-142 (1987) · Zbl 0616.76004 · doi:10.1007/BF00251230 |
| [67] | Modica, L.; Mortola, S., Un esempio di \(\Gamma \)-convergenza, Boll. Unione Mat. Ital., 5, 14, 285-299 (1977) · Zbl 0356.49008 |
| [68] | Nyström, E. J., Über die Praktische Auflösung von Linearen Integralgleichungen mit Anwendungen auf Randwertaufgaben der Potentialtheorie, Commentat. Phys.-Math., 4, 15, 1-52 (1928) · JFM 55.0819.02 |
| [69] | Oberman, A. M.; Calder, J., Lipschitz regularized deep neural networks converge and generalize (2018) |
| [70] | Sethian, J. A., A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci. USA, 93, 4, 1591-1595 (1996) · Zbl 0852.65055 · doi:10.1073/pnas.93.4.1591 |
| [71] | Shi, Z.; Wang, B.; Osher, S. J., Error estimation of weighted nonlocal Laplacian on random point cloud (2018) |
| [72] | Simon, L., Lectures on geometric measure theory, Proceedings of the Centre for Mathematical Analysis, Australian National University, 3 (1983), Australian National University Centre for Mathematical Analysis · Zbl 0546.49019 |
| [73] | Skolnik, M. I., Radar handbook (1970), McGraw-Hill Book Co. |
| [74] | Slepčev, D.; Thorpe, M., Analysis of \(p\)-Laplacian regularization in semi-supervised learning (2017) |
| [75] | Strandmark, P.; Ulen, J.; Kahl, F.; Grady, L., Shortest Paths with Curvature and Torsion, 2013 IEEE International Conference on Computer Vision(ICCV), 2024-2031 (2013), IEEE · doi:10.1109/ICCV.2013.253 |
| [76] | Strode, C., Optimising multistatic sensor locations using path planning and game theory, IEEE Symposium on Computational Intelligence for Security and Defence Applications, 9-16 (2011), IEEE |
| [77] | Taylor, J. E., Mathematics of Microstructure Evolution, 4, Anisotropic interface motion, 135-148 (1996), The Minerals, Metals & Materials Society |
| [78] | Thorpe, M.; Theil, F., Asymptotic Analysis of the Ginzburg-Landau Functional on Point Clouds, Proc. R. Soc. Edinb., Sect. A, Math., 149, 387-427 (2019) · Zbl 1417.49013 · doi:10.1017/prm.2018.32 |
| [79] | Thorpe, M.; van Gennip, Y., Deep Limits of Residual Neural Networks (2018) |
| [80] | Tudisco, F.; Hein, M., A nodal domain theorem and a higher-order Cheeger inequality for the graph \(p\)-Laplacian, J. Spectr. Theory, 8, 3, 883-908 (2018) · Zbl 1491.05126 · doi:10.4171/JST/216 |
| [81] | van Gennip, Y., An MBO scheme for minimizing the graph Ohta-Kawasaki functional, J. Nonlinear Sci., 1-49 (2018) |
| [82] | van Gennip, Y.; Bertozzi, A. L., \( \Gamma \)-convergence of graph Ginzburg-Landau functionals, Adv. Differ. Equ., 17, 11-12, 1115-1180 (2012) · Zbl 1388.35200 |
| [83] | van Gennip, Y.; Guillen, N.; Osting, B.; Bertozzi, A. L., Mean Curvature, Threshold Dynamics, and Phase Field Theory on Finite Graphs, Milan J. Math., 82, 1, 3-65 (2014) · Zbl 1325.35245 · doi:10.1007/s00032-014-0216-8 |
| [84] | von Luxburg, U., A tutorial on spectral clustering, Statistics and Computing, 17, 4, 395-416 (2007) · doi:10.1007/s11222-007-9033-z |
| [85] | Wagner, D.; Wagner, F., Between min cut and graph bisection, International Symposium on Mathematical Foundations of Computer Science, 744-750 (1993), Springer · Zbl 0925.05053 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
