A graph framework for manifold-valued data. (English) Zbl 1398.65132
Summary: Graph-based methods have been proposed as a unified framework for discrete calculus of local and nonlocal image processing methods in recent years. In order to translate variational models and partial differential equations to a graph, certain operators have been investigated and successfully applied to real-world applications involving graph models. So far the graph framework has been limited to real- and vector-valued functions on Euclidean domains. In this paper we generalize this model to the case of manifold-valued data. We introduce the basic calculus needed to formulate variational models and partial differential equations for manifold-valued functions and discuss the proposed graph framework for two particular families of operators, namely, the isotropic and anisotropic graph \(p\)-Laplacian operators, \(p\geq 1\). Based on the choice of \(p\) we are in particular able to solve optimization problems on manifold-valued functions involving total variation \((p=1)\) and Tikhonov \((p=2)\) regularization. Finally, we present numerical results from processing both synthetic as well as real-world manifold-valued data, e.g., from diffusion tensor imaging and light detection and ranging data.
MSC:
| 65K10 | Numerical optimization and variational techniques |
| 35R02 | PDEs on graphs and networks (ramified or polygonal spaces) |
| 49M25 | Discrete approximations in optimal control |
| 68U10 | Computing methodologies for image processing |
Keywords:
\(p\)-Laplacian; manifold-valued data; finite weighted graphs; total variation on manifolds; nonlocal PDEs; nonsmooth variational methodsReferences:
| [1] | P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008. · Zbl 1147.65043 |
| [2] | B. L. Adams, S. I. Wright, and K. Kunze, Orientation imaging: The emergence of a new microscopy, J. Metal. Mater. Trans. A, 24 (1993), pp. 819–831, . |
| [3] | B. Afsari, R. Tron, and R. Vidal, On the convergence of gradient descent for finding the Riemannian center of mass, SIAM J. Control Optim., 51 (2013), pp. 2230–2260, . · Zbl 1285.90031 |
| [4] | J. Angulo and S. Velasco-Forero, Morphological Processing of Univariate Gaussian Distribution-Valued Images Based on Poincaré Upper-Half Plane Representation, in Geometric Theory of Information, Springer, New York, 2014, pp. 331–366, . · Zbl 1345.62018 |
| [5] | F. \AAström, S. Petra, B. Schmitzer, and C. Schnörr, Image labeling by assignment, J. Math. Imaging Vision, 58 (2017), pp. 211–238. . · Zbl 1460.62101 |
| [6] | J.-F. Aujol, G. Guy, and N. Papadakis, Fundamentals of Non-Local Total Variation Spectral Theory, in Scale Space and Variational Methods in Computer Vision, Springer, New York, 2015, pp. 66–77, . · Zbl 1450.35205 |
| [7] | D. Azagra and J. Ferrera, Proximal calculus on Riemannian manifolds, Mediterr. J. Math., 2 (2005), pp. 437–450, . · Zbl 1167.49307 |
| [8] | M. Bačák, Computing medians and means in Hadamard spaces, SIAM J. Optim., 24 (2014), pp. 1542–1566, . · Zbl 1306.49046 |
| [9] | M. Bačák, Convex Analysis and Optimization in Hadamard Spaces, De Gruyter Ser. Nonlinear Anal. Appl. 22, De Gruyter, Berlin, 2014, . · Zbl 1299.90001 |
| [10] | M. Bačák, R. Bergmann, G. Steidl, and A. Weinmann, A second order non-smooth variational model for restoring manifold-valued images, SIAM J. Sci. Comput., 38 (2016), pp. A567–A597, . · Zbl 1382.94007 |
| [11] | F. Bachmann, R. Hielscher, P. E. Jupp, W. Pantleon, H. Schaeben, and E. Wegert, Inferential statistics of electron backscatter diffraction data from within individual crystalline grains, J. Appl. Crystallogr., 43 (2010), pp. 1338–1355, . |
| [12] | E. Bae and E. Merkurjev, Convex variational methods on graphs for multiclass segmentation of high-dimensional data and point clouds, J. Math. Imaging Vision, 58 (2017), pp. 468–493. . · Zbl 1420.94007 |
| [13] | S. Bansal and A. Tatu, Active contour models for manifold valued image segmentation, J. Math. Imaging Vision, 52 (2015), pp. 303–314, . · Zbl 1357.94016 |
| [14] | P. Basser, J. Mattiello, and D. LeBihan, MR diffusion tensor spectroscopy and imaging, Biophys. J., 66 (1994), pp. 259–267, . |
| [15] | R. Bergmann, MVIRT, A toolbox for manifold-valued image registration, in IEEE International Conference on Image Processing, IEEE ICIP 2017, Beijng, China, 2017, to appear. |
| [16] | R. Bergmann, R. H. Chan, R. Hielscher, J. Persch, and G. Steidl, Restoration of manifold-valued images by half-quadratic minimization, Inverse Probl. Imaging, 2 (2016), pp. 281–304, . · Zbl 1348.65097 |
| [17] | R. Bergmann, J. H. Fitschen, J. Persch, and G. Steidl, Iterative multiplicative filters for data labeling, Int. J. Comput. Vis., 123 (2017), pp. 435–453, . · Zbl 1460.62212 |
| [18] | R. Bergmann, J. H. Fitschen, J. Persch, and G. Steidl, Infimal convolution coupling of first and second order differences on manifold-valued images, in Proceedings of the 6th International Conference on Scale Space and Variational Methods in Computer Vision: SSVM 2017, F. Lauze, Y. Dong, and A. B. Dahl, eds., Kolding, Denmark, Springer, New York, 2017, pp. 447–459, . · Zbl 1489.65037 |
| [19] | R. Bergmann, J. H. Fitschen, J. Persch, and G. Steidl, Priors with Coupled First and Second Order Differences for Manifold-Valued Image Processing, , 2017. · Zbl 1436.49040 |
| [20] | R. Bergmann, F. Laus, G. Steidl, and A. Weinmann, Second order differences of cyclic data and applications in variational denoising, SIAM J. Imaging Sci., 7 (2014), pp. 2916–2953, . · Zbl 1309.65022 |
| [21] | R. Bergmann, J. Persch, and G. Steidl, A parallel Douglas–Rachford algorithm for minimizing ROF-like functionals on images with values in symmetric Hadamard manifolds, SIAM J. Imaging Sci., 9 (2016), pp. 901–937, . · Zbl 1346.65006 |
| [22] | R. Bergmann and A. Weinmann, Inpainting of cyclic data using first and second order differences, in Energy Minimization Methods in Computer Vision and Pattern Recognition, Springer, New York, 2015, pp. 155–168, . |
| [23] | R. Bergmann and A. Weinmann, A second order TV-type approach for inpainting and denoising higher dimensional combined cyclic and vector space data, J. Math. Imaging Vision,, 55 (2016), pp. 401–427, . · Zbl 1338.65155 |
| [24] | T. Bühler and M. Hein, Spectral clustering based on the graph p-laplacian, in Proceedings of the 26th Annual International Conference on Machine Learning, ACM, 2009, pp. 81–88, . |
| [25] | M. Burger and S. Osher, Convergence rates of convex variational regularization, Inverse Problems, 20 (2004), pp. 1411–1421, . · Zbl 1068.65085 |
| [26] | R. Bürgmann, P. A. Rosen, and E. J. Fielding, Synthetic aperture radar interferometry to measure earth\textquoterights surface topography and its deformation, Ann. Rev. Earth Planet. Sci., 28 (2000), pp. 169–209, . |
| [27] | L. Calatroni, Y. van Gennip, C.-B. Schönlieb, H. M. Rowland, and A. Flenner, Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images, J. Math. Imaging Vision, 57 (2017), pp. 269–291, . · Zbl 1369.94019 |
| [28] | A. Chambolle and P.-L. Lions, Image recovery via total variation minimization and related problems, Numer. Math., 76 (1997), pp. 167–188, . · Zbl 0874.68299 |
| [29] | P. A. Cook, Y. Bai, S. Nedjati-Gilani, K. K. Seunarine, M. G. Hall, G. J. Parker, and D. C. Alexander, Camino: Open-source diffusion-MRI reconstruction and processing, in Proceedings of the International Society for Magnetic Resonance in Medicine 14, Seattle, WA, 2006, 2759, . |
| [30] | D. Cremers and E. Strekalovskiy, Total cyclic variation and generalizations, J. Math. Imaging Vision, 47 (2013), pp. 258–277, . · Zbl 1298.94011 |
| [31] | C.-A. Deledalle, L. Denis, and F. Tupin, NL-InSAR: Nonlocal interferogram estimation, IEEE Trans. Geosci. Remote Sensing, 49 (2011), pp. 1441–1452, . |
| [32] | M. P. do Carmo, Riemannian Geometry, Birkhäuser, Basel, 1992. · Zbl 0752.53001 |
| [33] | A. Elmoataz, O. Lézoray, and S. Bougleux, Nonlocal discrete regularization on weighted graphs: A framework for image and manifold processing, IEEE Trans. Image Process., 17 (2008), pp. 1047–1060. |
| [34] | A. Elmoataz, M. Toutain, and D. Tenbrinck, On the \(p\)-Laplacian and \(∞\)-Laplacian on graphs with applications in image and data processing, SIAM J. Imaging Sci., 8 (2015), pp. 2412–2451, . · Zbl 1330.35488 |
| [35] | O. P. Ferreira and P. R. Oliveira, Subgradient algorithm on Riemannian manifolds, J. Optim. Theory Appl., 97 (1998), pp. 93–104, . · Zbl 0907.90244 |
| [36] | O. P. Ferreira and P. R. Oliveira, Proximal point algorithm on Riemannian manifolds, Optimization, 51 (2002), pp. 257–270, . · Zbl 1013.49024 |
| [37] | P. Fletcher and S. Joshi, Riemannian geometry for the statistical analysis of diffusion tensor data, Signal Process., 87 (2007), pp. 250–262, . · Zbl 1186.94126 |
| [38] | D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl., 2 (1976), pp. 17–40. · Zbl 0352.65034 |
| [39] | N. García Trillos and D. Slepčev, Continuum limit of total variation on point clouds, Arch. Ration. Mech. Anal., 1 (2016), pp. 193–241, . · Zbl 1336.68215 |
| [40] | N. García Trillos, D. Slepčev, J. von Brecht, T. Laurent, and X. Bresson, Consistency of Cheeger and ratio graph cuts, J. Mach. Learn. Res., 17 (2016), pp. 1–46. · Zbl 1392.62180 |
| [41] | D. Gesch, G. Evans, J. Mauck, J. Hutchinson, and W. J. Carswell, Jr., The National Map-Elevation, Technical report, US Geological Survey, 2009. |
| [42] | G. Gilboa and S. Osher, Nonlocal operators with applications to image processing, Multiscale Model. Simul., 7 (2008), pp. 1005–1028, . · Zbl 1181.35006 |
| [43] | R. Glowinski and A. Marroco, Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires, Revue française d’automatique, informatique, recherche opérationnelle. Analyse numérique, 9 (1975), pp. 41–76. · Zbl 0368.65053 |
| [44] | L. J. Grady and J. Polimeni, Discrete Calculus: Applied Analysis on Graphs for Computational Science, Springer, New York, 2010, . · Zbl 1195.68074 |
| [45] | M. Gräf, Efficient Algorithms for the Computation of Optimal Quadrature Points on Riemannian Manifolds, TU Chemnitz, 2013; also available online from . |
| [46] | P. Grohs and S. Hosseini, \(ε\)-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds, Adv. Comput. Math., 42 (2016), pp. 333–360, . · Zbl 1338.49029 |
| [47] | M. Hidane, O. Lézoray, and A. Elmoataz, Nonlinear multilayered representation of graph-signals, J. Math. Imaging Vision,, 45 (2013), pp. 114–137, . · Zbl 1276.94006 |
| [48] | J. Jost, Riemannian Geometry and Geometric Analysis, Springer, New York, 2011, . · Zbl 1227.53001 |
| [49] | S. H. Kang, B. Shafei, and G. Steidl, Supervised and transductive multi-class segmentation using \(p\)-Laplacians and RKHS methods, J. Vis. Commun. Image Represent., 25 (2014), pp. 1136–1148, . |
| [50] | R. Kimmel and N. Sochen, Orientation diffusion or how to comb a porcupine, J. Vis. Commun. Image Represent., 13 (2002), pp. 238–248, . |
| [51] | K. Kunze, S. I. Wright, B. L. Adams, and D. J. Dingley, Advances in automatic EBSP single orientation measurements, Textures Microstruct., 20 (1993), pp. 41–54, . |
| [52] | F. Laus, M. Nikolova, J. Persch, and G. Steidl, A nonlocal denoising algorithm for manifold-valued images using second order statistics, SIAM J. Imaging Sci., 101 (2017), pp. 416–448. · Zbl 1365.68453 |
| [53] | J. M. Lee, Riemannian Manifolds. An Introduction to Curvature, Springer, New York, 1997, . · Zbl 0905.53001 |
| [54] | Y.-S. Lee and S.-Y. Chung, Extinction and positivity of solutions of the p-Laplacian evolution equation on networks, J. Math. Anal. Appl., 386 (2012), pp. 581–592, . · Zbl 1235.35041 |
| [55] | J. Lellmann, J.-M. Morel, and C.-B. Schönlieb, Anisotropic third-order regularization for sparse digital elevation models, in Proceedings of SSVM 2013, Springer, New York, 2013, pp. 161–173, . |
| [56] | J. Lellmann, K. Papafitsoros, C.-B. Schönlieb, and D. Spector, Analysis and application of a nonlocal Hessian, SIAM J. Imaging Sci., 8 (2015), pp. 2161–2202, . · Zbl 1330.94010 |
| [57] | J. Lellmann, E. Strekalovskiy, S. Koetter, and D. Cremers, Total variation regularization for functions with values in a manifold, in Proceedings of the 2013 IEEE International Conference on Computer Vision (ICCV), pp. 2944–2951, . |
| [58] | F. Lozes, A. Elmoataz, and O. Lézoray, Partial difference operators on weighted graphs for image processing on surfaces and point clouds, IEEE Trans. Image Process., 23 (2014), pp. 3896–3909, . · Zbl 1374.94237 |
| [59] | K. V. Mardia and P. E. Jupp, Directional Statistics, Wiley, Chichester, 2000. · Zbl 0935.62065 |
| [60] | D. Massonnet and K. L. Feigl, Radar interferometry and its application to changes in the earth’s surface, Rev. Geophys., 36 (1998), pp. 441–500, . |
| [61] | M. Moakher and P. G. Batchelor, Symmetric positive-definite matrices: From geometry to applications and visualization, in Visualization and Processing of Tensor Fields, Springer, New York, 2006, pp. 285–298, . |
| [62] | D. Mugnolo, Semigroup Methods for Evolution Equations on Networks, Springer, New York, 2014, . · Zbl 1306.47001 |
| [63] | J. Nash, The imbedding problem for Riemannian manifolds, Ann. of Math., 63 (1956), pp. 20–63. · Zbl 0070.38603 |
| [64] | X. Pennec, P. Fillard, and N. Ayache, A Riemannian framework for tensor computing, Int. J. Comput. Vis., 66 (2006), pp. 41–66, . · Zbl 1287.53031 |
| [65] | F. Rocca, C. Prati, and A. M. Guarnieri, Possibilities and limits of SAR interferometry, in Proceedings of the Latino-American on Radar Sensing, 1996, pp. 15–26. |
| [66] | G. Rosman, X.-C. Tai, R. Kimmel, and A. M. Bruckstein, Augmented-Lagrangian regularization of matrix-valued maps, Methods Appl. Anal., 21 (2014), pp. 121–138, . · Zbl 1292.65072 |
| [67] | G. Rosman, Y. Wang, X.-C. Tai, R. Kimmel, and A. M. Bruckstein, Fast Regularization of Matrix-Valued Images, in Efficient Algorithms for Global Optimization Methods in Computer Vision, Springer, New York, 2014, pp. 19–43, . |
| [68] | L. I. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), pp. 259–268, . · Zbl 0780.49028 |
| [69] | A. Sawatzky, D. Tenbrinck, X. Jiang, and M. Burger, A variational framework for region-based segmentation incorporating physical noise models, J. Math. Imaging Vision, 47 (2013), pp. 179–209, . · Zbl 1291.68402 |
| [70] | Z. Shi, S. Osher, and W. Zhu, Weighted Nonlocal Laplacian on Point Cloud, UCLA CAM reports cam16-88, 2016. |
| [71] | D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag., 30 (2013), pp. 83–98, . |
| [72] | G. D. Smith, Numerical Solution of Partial Differential Equations: Finite Difference Methods, 3rd ed., Oxford Appl. Math. Comput. Sci. Ser., Oxford University Press, Oxford, 1986. |
| [73] | E. Strekalovskiy and D. Cremers, Total variation for cyclic structures: Convex relaxation and efficient minimization, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE, 2011, pp. 1905–1911, . |
| [74] | M. Touttain, A. Elmoataz, and F. Lozes, Nonlocal discrete \(∞\)-Poisson and Hamilton Jacobi equations: From stochastic game to generalized distances on images, meshes, and point clouds, J. Math. Imaging Vision, 55 (2016), pp. 229–241, . · Zbl 1336.05056 |
| [75] | C. Udrişte, Convex Functions and Optimization Methods on Riemannian Manifolds, Math. Appl. 297, Kluwer Academic, Dordrecht, the Netherlands, 1994, . · Zbl 0932.53003 |
| [76] | T. Valkonen, K. Bredies, and F. Knoll, Total generalized variation in diffusion tensor imaging, SIAM J. Imaging Sci., 6 (2013), pp. 487–525, . · Zbl 1322.94024 |
| [77] | Y. van Gennip and A. L. Bertozzi, \(γ\)-convergence of graph Ginzburg–Landau functionals, Adv. Differential Equations, 17 (2012), pp. 1115–1180. · Zbl 1388.35200 |
| [78] | Y. van Gennip, N. Guillen, B. Osting, and A. L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs, Milan J. Math., 82 (2014), pp. 3–65, . · Zbl 1325.35245 |
| [79] | U. von Luxburg, M. Belkin, and O. Bousquet, Consistency of spectral clustering, Ann. Statist., 36 (2008), pp. 555–586, . · Zbl 1133.62045 |
| [80] | A. Weinmann, L. Demaret, and M. Storath, Total variation regularization for manifold-valued data, SIAM J. Imaging Sci., 7 (2014), pp. 2226–2257, . · Zbl 1309.65071 |
| [81] | H. Whitney, Differentiable manifolds, Ann. of Math., 37 (1936), pp. 645–680. · JFM 62.1454.01 |
| [82] | X. Zhou and M. Belkin, Semi-supervised learning by higher order regularization, in Proceedings of AISTATS, 2011, pp. 892–900. |
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.
