Analysis and an interior-point approach for TV image reconstruction problems on smooth surfaces. (English) Zbl 1408.94240
Summary: R. Lai and T. F. Chan [Comput. Vis. Image Underst. 115, 1647–1661 (2011)] introduced an analogue of the total variation image reconstruction approach of Rudin, Osher, and Fatemi [L. I. Rudin et al., Physica D 60, No. 1–4, 259–268 (1992; Zbl 0780.49028)] for images on smooth surfaces. The problem is defined in terms of quantities intrinsic to the surface and is therefore independent of the parametrization. In this paper, a rigorous analytical framework is developed for this model and its Fenchel predual. It is shown that the predual of the total variation problem is a quadratic optimization problem for the predual vector field \(\boldsymbol{q} \in \boldsymbol{H}(\operatorname{div};S)\) with pointwise inequality constraints on the surface. As in the flat case, \( \boldsymbol{q}\) serves as an edge detector. A function space interior-point method is proposed for the predual problem, which is discretized by conforming Raviart–Thomas finite elements on a triangulation of the surface. Well-posedness of the barrier problems is established. Numerical examples including denoising and inpainting problems with both gray-scale and color images on scanned three-dimensional geometries of considerable complexity are presented.
MSC:
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 92C55 | Biomedical imaging and signal processing |
| 68U10 | Computing methodologies for image processing |
| 49M29 | Numerical methods involving duality |
| 65K05 | Numerical mathematical programming methods |
Keywords:
total bounded variation; Fenchel predual problem; interior-point methods; image reconstruction; image denoising; image inpainting; surfacesCitations:
Zbl 0780.49028References:
| [1] | H. Attouch, G. Buttazzo, and G. Michaille, Variational Analysis in Sobolev and BV Spaces: Applications to PDEs and Optimization, 2nd ed., MOS-SIAM Ser. Optim. 17, SIAM, Philadelphia, 2014, . · Zbl 1311.49001 |
| [2] | T. Aubin, A Course in Differential Geometry, Grad. Stud. Math. 27, American Mathematical Society, Providence, RI, 2001. · Zbl 0966.53001 |
| [3] | C. L. Bajaj and G. Xu, Anisotropic diffusion of surfaces and functions on surfaces, ACM Trans. Graph., 22 (2003), pp. 4–32. |
| [4] | S. Bartels, Total variation minimization with finite elements: Convergence and iterative solution, SIAM J. Numer. Anal., 50 (2012), pp. 1162–1180, . · Zbl 1257.65067 |
| [5] | S. Bartels, Error control and adaptivity for a variational model problem defined on functions of bounded variation, Math. Comp., 84 (2015), pp. 1217–1240, . · Zbl 1311.65141 |
| [6] | M. Ben-Artzi and P. G. LeFloch, Well-posedness theory for geometry-compatible hyperbolic conservation laws on manifolds, Ann. Inst. H. Poincaré Anal. Non Linéaire, 24 (2007), pp. 989–1008, . · Zbl 1138.35055 |
| [7] | H. Benninghoff and H. Garcke, Segmentation and restoration of images on surfaces by parametric active contours with topology changes, J. Math. Imaging Vision, 55 (2016), pp. 105–124, . · Zbl 1405.94014 |
| [8] | M. Bertalmío, L.-T. Cheng, S. Osher, and G. Sapiro, Variational problems and partial differential equations on implicit surfaces, J. Comput. Phys., 174 (2001), pp. 759–780, . · Zbl 0991.65055 |
| [9] | H. Biddle, I. von Glehn, C. B. Macdonald, and T. März, A volume-based method for denoising on curved surfaces, in Proceedings of the 2013 IEEE International Conference on Image Processing, 2013, pp. 529–533, . |
| [10] | P. Blomgren and T. Chan, Color TV: Total variation methods for restoration of vector-valued images, IEEE Trans. Image Process., 7 (1998), pp. 304–309, . |
| [11] | K. Bredies and D. Lorenz, Mathematische Bildverarbeitung, Vieweg+Teubner, 2011, . |
| [12] | X. Bresson and T. F. Chan, Fast dual minimization of the vectorial total variation norm and applications to color image processing, Inverse Probl. Imaging, 2 (2008), pp. 455–484, . · Zbl 1188.68337 |
| [13] | J.-F. Cai, S. Osher, and Z. Shen, Linearized Bregman iterations for frame-based image deblurring, SIAM J. Imaging Sci., 2 (2009), pp. 226–252, . · Zbl 1175.94010 |
| [14] | J. L. Carter, Dual Methods for Total Variation-Based Image Restoration, Ph.D. thesis, UCLA, Los Angeles, CA, 2001. |
| [15] | A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vision, 20 (2004), pp. 89–97, . · Zbl 1366.94048 |
| [16] | 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 |
| [17] | A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), pp. 120–145, . · Zbl 1255.68217 |
| [18] | T. Chan, S. Esedoglu, F. Park, and A. Yip, Total variation image restoration: Overview and recent developments, in Handbook of Mathematical Models in Computer Vision, Springer, Boston, 2006, pp. 17–31, . |
| [19] | T. F. Chan, G. H. Golub, and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20 (1999), pp. 1964–1977, . · Zbl 0929.68118 |
| [20] | T. F. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods, SIAM, Philadelphia, 2005, . · Zbl 1095.68127 |
| [21] | U. Clarenz, U. Diewald, and M. Rumpf, Processing textured surfaces via anisotropic geometric diffusion, IEEE Trans. Image Process., 13 (2004), pp. 248–261, . |
| [22] | M. Desbrun, M. Meyer, P. Schröder, and A. H. Barr, Anisotropic feature-preserving denoising of height fields and bivariate data, in Proceedings of Graphics Interface 2000, Montreal, 2000, Canadian Human-Computer Communications Society, pp. 145–152, . |
| [23] | P. Destuynder, M. Jaoua, and H. Sellami, A dual algorithm for denoising and preserving edges in image processing, J. Inverse Ill-Posed Probl., 15 (2007), pp. 149–165, . · Zbl 1162.68784 |
| [24] | M. P. do Carmo, Riemannian Geometry, Math. Theory Appl., Birkhäuser Boston, Boston, 1992 (translated from the second Portuguese edition by Francis Flaherty). · Zbl 0752.53001 |
| [25] | D. C. Dobson and F. Santosa, Recovery of blocky images from noisy and blurred data, SIAM J. Appl. Math., 56 (1996), pp. 1181–1198, . · Zbl 0858.68121 |
| [26] | Y. Dong, M. Hintermüller, and M. M. Rincon-Camacho, A multi-scale vectorial \(L^τ\)-TV framework for color image restoration, Int. J. Comput. Vis., 92 (2011), pp. 296–307, . · Zbl 1235.68259 |
| [27] | I. Ekeland and R. Témam, Convex Analysis and Variational Problems, Classics Appl. Math. 28, SIAM, Philadelphia, 1999, . · Zbl 0939.49002 |
| [28] | G. Enrico, Minimal Surfaces and Functions of Bounded Variation, Monogr. Math. 80, Birkäuser, Basel, 1984. · Zbl 0545.49018 |
| [29] | A. Ern and J.-L. Guermond, Theory and Practice of Finite Elements, Springer, Berlin, 2004. · Zbl 1059.65103 |
| [30] | V. Girault and P.-A. Raviart, Finite Element Methods for Navier-Stokes Equations, Springer-Verlag, Berlin, 1986. · Zbl 0585.65077 |
| [31] | T. Goldstein and S. Osher, The split Bregman method for \(L1\)-regularized problems, SIAM J. Imaging Sci., 2 (2009), pp. 323–343, . · Zbl 1177.65088 |
| [32] | E. Hebey, Sobolev Spaces on Riemannian Manifolds, Lecture Notes in Math. 1635, Springer-Verlag, Berlin, 1996. · Zbl 0866.58068 |
| [33] | E. Hebey, Nonlinear Analysis on Manifolds: Sobolev Spaces and Inequalities, Courant Lect. Notes Math. 5, New York University, Courant Institute of Mathematical Sciences, New York; American Mathematical Society, Providence, RI, 2000. · Zbl 0981.58006 |
| [34] | R. Herzog, G. Stadler, and G. Wachsmuth, Directional sparsity in optimal control of partial differential equations, SIAM J. Control Optim., 50 (2012), pp. 943–963, . · Zbl 1244.49038 |
| [35] | M. Hintermüller and K. Kunisch, Total bounded variation regularization as a bilaterally constrained optimization problem, SIAM J. Appl. Math., 64 (2004), pp. 1311–1333, . · Zbl 1055.94504 |
| [36] | J. R. Jensen, Introductory Digital Image Processing: A Remote Sensing Perspective, 4th ed., Prentice-Hall, Englewood Cliffs, NJ, 2015. |
| [37] | J. John and M. Wilscy, Image processing techniques for surface characterization of nanostructures, in Proceedings of the 2016 International Conference on Circuit, Power and Computing Technologies (ICCPCT), IEEE, 2016, . |
| [38] | W. Kühnel, Differentialgeometrie, Aufbaukurs Mathematik, 6th ed., Springer Spektrum, Wiesbaden, 2013. |
| [39] | R. Lai and T. F. Chan, A framework for intrinsic image processing on surfaces, Computer Vis. Image Underst., 115 (2011), pp. 1647–1661, . |
| [40] | A. Logg, K.-A. Mardal, and G. Wells, eds., Automated Solution of Differential Equations by the Finite Element Method, Lect. Notes Comput. Sci. Eng. 84, Springer, Berlin, Heidelberg, 2012. · Zbl 1247.65105 |
| [41] | L. D. López Pérez, Régularisation d’images sur des surfaces non planes, Ph.D. thesis, Université de Nice Sophia Antipolis, 2006, . |
| [42] | F. Malgouyres and F. Guichard, Edge direction preserving image zooming: A mathematical and numerical analysis, SIAM J. Numer. Anal., 39 (2001), pp. 1–37, . · Zbl 1001.68174 |
| [43] | E. Naden, T. März, and C. B. Macdonald, Anisotropic Diffusion Filtering of Images on Curved Surfaces, preprint, , 2014. |
| [44] | P. Perona and J. Malik, Scale-space and edge detection using anisotropic diffusion, IEEE Trans. Pattern Anal. Mach. Intell., 12 (1990), pp. 629–639, . |
| [45] | A. Pressley, Elementary Differential Geometry, 2nd ed., Springer Undergrad. Math. Ser., Springer-Verlag, London, 2010, . · Zbl 1191.53002 |
| [46] | U. Prüfert, F. Tröltzsch, and M. Weiser, The convergence of an interior point method for an elliptic control problem with mixed control-state constraints, Comput. Optim. Appl., 39 (2008), pp. 183–218, . · Zbl 1144.90511 |
| [47] | P.-A. Raviart and J. M. Thomas, A mixed finite element method for \(2\)nd order elliptic problems, in Mathematical Aspects of Finite Element Methods (Proc. Conf., Consiglio Naz. delle Ricerche (C.N.R.), Rome, 1975), Lecture Notes in Math. 606, Springer, Berlin, 1977, pp. 292–315. · Zbl 0362.65089 |
| [48] | M. E. Rognes, D. A. Ham, C. J. Cotter, and A. T. T. McRae, Automating the solution of PDEs on the sphere and other manifolds in FEniCS 1.2, Geosci. Model Dev., 6 (2013), pp. 2099–2119, . |
| [49] | M. E. Rognes, R. C. Kirby, and A. Logg, Efficient assembly of H\textup(div) and H\textup(curl) conforming finite elements, SIAM J. Sci. Comput., 31 (2009), pp. 4130–4151, . · Zbl 1206.65248 |
| [50] | S. Rosenberg, The Laplacian on a Riemannian Manifold. An Introduction to Analysis on Manifolds, London Math. Soc. Stud. Texts 31, Cambridge University Press, Cambridge, UK, 1997. · Zbl 0868.58074 |
| [51] | 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 |
| [52] | A. Schiela, Barrier methods for optimal control problems with state constraints, SIAM J. Optim., 20 (2009), pp. 1002–1031, . · Zbl 1201.90201 |
| [53] | D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization, Inverse Problems, 19 (2003), pp. S165–S187, . · Zbl 1043.94512 |
| [54] | M. Ulbrich and S. Ulbrich, Primal-dual interior point methods for PDE-constrained optimization, Math. Program., 117 (2009), pp. 435–485, . · Zbl 1171.90018 |
| [55] | D. Wachsmuth, Numerical solution of optimal control problems with convex control constraints, in Systems, Control, Modeling and Optimization, IFIP Int. Fed. Inf. Process. 202, Springer, New York, 2006, pp. 319–327, . · Zbl 1214.49026 |
| [56] | Y. Wang, J. Yang, W. Yin, and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1 (2008), pp. 248–272, . · Zbl 1187.68665 |
| [57] | C. Zălinescu, Convex Analysis in General Vector Spaces, World Scientific, River Edge, NJ, 2002, . · Zbl 1023.46003 |
| [58] | W. P. Ziemer, Weakly Differentiable Functions. Sobolev Spaces and Functions of Bounded Variation, Grad. Texts in Math. 120, Springer-Verlag, New York, 1989, . · Zbl 0692.46022 |
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.
