Restoration of manifold-valued images by half-quadratic minimization

Ronny  Bergmann; Raymond H. Chan; Ralf  Hielscher; Johannes  Persch; Gabriele  Steidl

doi:10.3934/ipi.2016001

Article Contents

2016, Volume 10, Issue 2: 281-304. Doi: 10.3934/ipi.2016001

This issue Previous Article Next Article Forward and backward filtering based on backward stochastic differential equations

Restoration of manifold-valued images by half-quadratic minimization

1.
Department of Mathematics, University of Kaiserslautern, Paul-Ehrlich-Str. 31, 67663 Kaiserslautern
2.
Department of Mathematics, Chinese University of Hong Kong, Shatin, Hong Kong
3.
Faculty of Mathematics, University of Chemnitz, Reichenhainer Str. 39, 09107 Chemnitz

Received: May 2015

Revised: November 2015

Published: May 2016

Abstract / Introduction Related Papers Cited by

Abstract

The paper addresses the generalization of the half-quadratic minimization method for the restoration of images having values in a complete, connected Riemannian manifold. We recall the half-quadratic minimization method using the notation of the $c$-transform and adapt the algorithm to our special variational setting. We prove the convergence of the method for Hadamard spaces. Extensive numerical examples for images with values on spheres, in the rotation group $SO(3)$, and in the manifold of positive definite matrices demonstrate the excellent performance of the algorithm. In particular, the method with $SO(3)$-valued data shows promising results for the restoration of images obtained from Electron Backscattered Diffraction which are of interest in material science.

Keywords:

Mathematics Subject Classification: 65K10, 49Q99, 49M20, 49M37.

Citation:

Related Papers

Cited by

References

[1]	P.-A. Absil, R. Mahony and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton and Oxford, Princeton University Press, 2008.doi: 10.1515/9781400830244.
[2]	B. L. Adams, S. I. Wright and K. Kunze, Orientation imaging: The emergence of a new microscopy, Journal Metallurgical and Materials Transactions A, 24 (1993), 819-831.doi: 10.1007/BF02656503.
[3]	A. D. Aleksandrov, A theorem on triangles in a metric space and some of its applications, in Trudy Mat. Inst. Steklov., v 38, Izdat. Akad. Nauk SSSR, Moscow, 38 (1951), 5-23.
[4]	M. Allain, J. Idier and Y. Goussard, On global and local convergence of half-quadratic algorithms, IEEE Transactions on Image Processing, 2 (2002), 633-836.doi: 10.1109/ICIP.2002.1040080.
[5]	M. Bačák, R. Bergmann, G. Steidl and A. Weinmann, A second order non-smooth variational model for restoring manifold-valued images, SIAM Journal of Scientific Computing, 38 (2016), A567-A597.doi: 10.1137/15M101988X.
[6]	M. Bačák, Convex Analysis and Optimization in Hadamard Spaces, vol. 22 of De Gruyter Series in Nonlinear Analysis and Applications, De Gruyter, Berlin, 2014.doi: 10.1515/9783110361629.
[7]	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, Journal of Applied Crystallography, 43 (2010), 1338-1355.doi: 10.1107/S002188981003027X.
[8]	F. Bachmann, R. Hielscher and H. Schaeben, Grain detection from 2d and 3d EBSD data - specification of the MTEX algorithm, Ultramicroscopy, 111 (2011), 1720-1733.doi: 10.1016/j.ultramic.2011.08.002.
[9]	R. Bergmann, F. Laus, G. Steidl and A. Weinmann, Second order differences of cyclic data and applications in variational denoising, SIAM Journal on Imaging Sciences, 7 (2014), 2916-2953.doi: 10.1137/140969993.
[10]	R. Bergmann and A. Weinmann, Inpainting of cyclic data using first and second order differences, in EMMCVPR2015 (eds. X.-C. Tai, E. Bai, T. Chan, S. Y. Leung and M. Lysaker), Lecture Notes in Computer Science, Springer, Berlin, 8932 (2015), 155-168.doi: 10.1007/978-3-319-14612-6_12.
[11]	R. Bergmann and A. Weinmann, A second order TV-type approach for inpainting and denoising higher dimensional combined cyclic and vector space data, Journal of Mathematical Imaging and Vision, (2016), 1-27, arXiv:1501.02684.doi: 10.1007/s10851-015-0627-3.
[12]	G. E. Bredon, Topology and Geometry, vol. 139 of Graduate Texts in Mathematics, Springer, New York, 1993.doi: 10.1007/978-1-4757-6848-0.
[13]	R. Bürgmann, P. A. Rosen and E. J. Fielding, Synthetic aperture radar interferometry to measure earth's surface topography and its deformation, Annual Reviews Earth and Planetary Science, 28 (2000), 169-209.
[14]	F. Champagnat and J. Idier, A connection between half-quadratic criteria and EM algorithms, IEEE Signal Processing Letters, 11 (2004), 709-712.doi: 10.1109/LSP.2004.833511.
[15]	T. F. Chan, S. Kang and J. Shen, Total variation denoising and enhancement of color images based on the CB and HSV color models, Journal of Visual Communication and Image Representation, 12 (2001), 422-435.doi: 10.1006/jvci.2001.0491.
[16]	P. Charbonnier, L. Blanc-Féraud, G. Aubert and M. Barlaud, Deterministic edge-preserving regularization in computed imaging, IEEE Transactions on Image Processing, 6 (1997), 298-311.doi: 10.1109/83.551699.
[17]	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 Proc. Intl. Soc. Mag. Reson. Med. 14, Seattle, WA, USA, 2006, p2759.
[18]	I. Daubechies, R. DeVore and C. S. Güntürk, Iteratively reweighted least squares minimization for sparse recovery, Communications in Pure and Applied Mathematics, 63 (2010), 1-38.doi: 10.1002/cpa.20303.
[19]	A. H. Delaney and Y. Bresler, Globally convergent edge-preserving regularized reconstruction: An application to limited-angle tomography, IEEE Transactions on Image Processing, 7 (1998), 204-221.doi: 10.1109/83.660997.
[20]	C.-A. Deledalle, L. Denis and F. Tupin, NL-InSAR: Nonlocal interferogram estimation, IEEE Transactions on Geoscience Remote Sensing, 49 (2011), 1441-1452.doi: 10.1109/TGRS.2010.2076376.
[21]	D. Geman and G. Reynolds, Constrained restoration and the recovery of discontinuities, IEEE Transactions on Pattern Analysis and Machine Intelligence, 14 (1992), 367-383.doi: 10.1109/34.120331.
[22]	D. Geman and C. Yang, Nonlinear image recovery with half-quadratic regularization, IEEE Transactions on Image Processing, 4 (1995), 932-946.doi: 10.1109/83.392335.
[23]	M. Gräf, A unified approach to scattered data approximation on $\mathbb S^{3}$ and $SO(3)$, Advances in Computational Mathematics, 37 (2012), 379-392.doi: 10.1007/s10444-011-9214-3.
[24]	P. Grohs and M. Sprecher, Total variation regularization by iteratively reweighted least squares on Hadamard spaces and the sphere, Preprint 2014-39, ETH Zürich.
[25]	V. K. Gupta and S. R. Agnew, A simple algorithm to eliminate ambiguities in EBSD orientation map visualization and analyses: Application to fatigue crack-tips/wakes in aluminum alloys, Microscopy and Microanalysis, 16 (2010), 831-841.doi: 10.1017/S1431927610093992.
[26]	J. Jost, Nonpositive Curvature: Geometric and Analytic Aspects, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 1997.doi: 10.1007/978-3-0348-8918-6.
[27]	R. Kimmel and N. Sochen, Orientation diffusion or how to comb a porcupine, Journal of Visual Communication and Image Representation, 13 (2002), 238-248.doi: 10.1006/jvci.2001.0501.
[28]	K. Kunze, S. I. Wright, B. L. Adams and D. J. Dingley, Advances in automatic EBSP single orientation measurements, Textures and Microstructures, 20 (1993), 41-54.doi: 10.1155/TSM.20.41.
[29]	R. Lai and S. Osher, A splitting method for orthogonality constrained problems, Journal of Scientific Computing, 58 (2014), 431-449.doi: 10.1007/s10915-013-9740-x.
[30]	C. L. Lawson, Contributions to the Theory of Linear Least Maximum Approximation, Ph.D. Thesis, University of California, Los Angeles.
[31]	J. Lellmann, E. Strekalovskiy, S. Koetter and D. Cremers, Total variation regularization for functions with values in a manifold, in IEEE ICCV 2013, 2013, 2944-2951.doi: 10.1109/ICCV.2013.366.
[32]	M. Moakher and P. G. Batchelor, Symmetric positive-definite matrices: From geometry to applications and visualization, in Visualization and Processing of Tensor Fields (eds. J. Weickert and H. Hagen), Springer Berlin Heidelberg, Berlin, Heidelberg, 452 (2006), 285-298.doi: 10.1007/3-540-31272-2_17.
[33]	M. Nikolova and R. H. Chan, The equivalence of half-quadratic minimization and the gradient linearization iteration, IEEE Transactions on Image Processing, 16 (2007), 1623-1627.doi: 10.1109/TIP.2007.896622.
[34]	M. Nikolova and M. K. Ng, Analysis of half-quadratic minimization methods for signal and image recovery, SIAM Journal on Scientific Computing, 27 (2005), 937-966.doi: 10.1137/030600862.
[35]	J. F. Nye, Some geometrical relations in dislocated crystals, Acta Metallurgica, 1 (1953), 153-162.doi: 10.1016/0001-6160(53)90054-6.
[36]	X. Pennec, P. Fillard and N. Ayache, A Riemannian framework for tensor computing, International Journal of Computer Vision, 66 (2006), 41-66.doi: 10.1007/s11263-005-3222-z.
[37]	M. H. Quang, S. H. Kang and T. M. Le, Image and video colorization using vector-valued reproducing kernel Hilbert spaces, Journal of Mathematical Imaging and Vision, 37 (2010), 49-65.doi: 10.1007/s10851-010-0192-8.
[38]	M. Raptis and S. Soatto, Tracklet descriptors for action modeling and video analysis, in ECCV 2010, Springer, 6311 (2010), 577-590.doi: 10.1007/978-3-642-15549-9_42.
[39]	J. G. Rešetnjak, Non-expansive maps in a space of curvature no greater than $K$, Akademija Nauk SSSR. Sibirskoe Otdelenie. Sibirskiĭ Matematičeskiĭ Žurnal, 9 (1968), 918-927.
[40]	G. Rosman, M. Bronstein, A. Bronstein, A. Wolf and R. Kimmel, Group-valued regularization framework for motion segmentation of dynamic non-rigid shapes, in Scale Space and Variational Methods in Computer Vision, Springer, 6667 (2012), 725-736.doi: 10.1007/978-3-642-24785-9_61.
[41]	G. Rosman, X.-C. Tai, R. Kimmel and A. M. Bruckstein, Augmented-Lagrangian regularization of manifold-valued maps, Methods and Applications of Analysis, 21 (2014), 105-121.doi: 10.4310/MAA.2014.v21.n1.a5.
[42]	L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[43]	Z.-Z. Shi and J.-S., Lecomte, private communication, 2014.
[44]	S. Sra and R. Hosseini, Conic geometric optimization on the manifold of positive definite matrices, SIAM J. Optim., 25 (2015), 713-739, arXiv:1320.1039v3.doi: 10.1137/140978168.
[45]	G. Steidl, S. Setzer, B. Popilka and B. Burgeth, Restoration of matrix fields by second order cone programming, Computing, 81 (2007), 161-178.doi: 10.1007/s00607-007-0247-x.
[46]	E. Strekalovskiy and D. Cremers, Total variation for cyclic structures: Convex relaxation and efficient minimization, in IEEE CVPR 2011, IEEE, 2011, 1905-1911.doi: 10.1109/CVPR.2011.5995573.
[47]	E. Strekalovskiy and D. Cremers, Total cyclic variation and generalizations, Journal of Mathematical Imaging and Vision, 47 (2013), 258-277.doi: 10.1007/s10851-012-0396-1.
[48]	K. T. Sturm, Probability measures on metric spaces of nonpositive curvature, heat kernels and analysis on manifolds, graphs, and metric spaces, Contemporary Mathematics, 338 (2003), 357-390.doi: 10.1090/conm/338/06080.
[49]	S. Sun, B. Adams and W. King, Observation of lattice curvature near the interface of a deformed aluminium bicrystal, Philosophical Magazine A, 80 (2000), 9-25.doi: 10.1080/01418610008212038.
[50]	O. Tuzel, F. Porikli and P. Meer, Learning on Lie groups for invariant detection and tracking, in CVPR 2008, IEEE, 2008, 1-8.doi: 10.1109/CVPR.2008.4587521.
[51]	L. Vese and S. Osher, Numerical methods for p-harmonic flows and applications to image processing, SIAM Journal on Numerical Analysis, 40 (2002), 2085-2104.doi: 10.1137/S0036142901396715.
[52]	C. Villani, Topics in Optimal Transportation, AMS, Providence, 2003.doi: 10.1007/b12016.
[53]	C. R. Vogel and M. E. Oman, Iterative method for total variation denoising, SIAM Journal on Scientific Computing, 17 (1996), 227-238.doi: 10.1137/0917016.
[54]	C. R. Vogel and M. E. Oman, Fast, robust total variation-based reconstruction of noisy, blurred images, IEEE Transactions on Image Processing, 7 (1998), 813-824.doi: 10.1109/83.679423.
[55]	J. Weickert, C. Feddern, M. Welk, B. Burgeth and T. Brox, PDEs for tensor image processing, in Visualization and Processing of Tensor Fields (eds. J. Weickert and H. Hagen), Springer, Berlin, 2006, 399-414.doi: 10.1007/3-540-31272-2_25.
[56]	A. Weinmann, L. Demaret and M. Storath, Total variation regularization for manifold-valued data, SIAM Journal on Imaging Sciences, 7 (2014), 2226-2257.doi: 10.1137/130951075.
[57]	M. Welk, C. Feddern, B. Burgeth and J. Weickert, Median filtering of tensor-valued images, in Pattern Recognition (eds. B. Michaelis and G. Krell), Lecture Notes in Computer Science, 2781, Springer, Berlin, 2003, 17-24.doi: 10.1007/978-3-540-45243-0_3.