×

Mumford-Shah and Potts regularization for manifold-valued data. (English) Zbl 1344.49055

Summary: Mumford-Shah and Potts functionals are powerful variational models for regularization which are widely used in signal and image processing. Typical applications are edge-preserving denoising and segmentation. Being both nonsmooth and nonconvex, they are computationally challenging even for scalar data. For manifold-valued data, the problem becomes even more involved since typical features of vector spaces are not available. In this paper, we propose algorithms for Mumford-Shah and for Potts regularization of manifold-valued signals and images. For the univariate problems, we derive solvers based on dynamic programming combined with (convex) optimization techniques for manifold-valued data. For the class of Cartan-Hadamard manifolds (which includes the data space in Diffusion Tensor Imaging (DTI)), we show that our algorithms compute global minimizers for any starting point. For the multivariate Mumford-Shah and Potts problems (for image regularization), we propose a splitting into suitable subproblems which we can solve exactly using the techniques developed for the corresponding univariate problems. Our method does not require any a-priori restrictions on the edge set and we do not have to discretize the data space. We apply our method to DTI as well as Q-ball imaging. Using the DTI model, we obtain a segmentation of the corpus callosum on real data.

MSC:

49M37 Numerical methods based on nonlinear programming
49L20 Dynamic programming in optimal control and differential games
90C25 Convex programming
90C39 Dynamic programming
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
68U10 Computing methodologies for image processing

References:

[1] Afsari, B., Tron, R., Vidal, R.: On the convergence of gradient descent for finding the Riemannian center of mass. SIAM J. Control Optim. 51(3), 2230-2260 (2013) · Zbl 1285.90031 · doi:10.1137/12086282X
[2] Alexander, D., Barker, G., Arridge, S.: Detection and modeling of non-Gaussian apparent diffusion coefficient profiles in human brain data. Magn. Reson. Med. 48(2), 331-340 (2002) · doi:10.1002/mrm.10209
[3] Alexander, A., Lee, J., Lazar, M., Boudos, R., DuBray, M., Oakes, T., Miller, J., Lu, J., Jeong, E.K., McMahon, W., et al.: Diffusion tensor imaging of the corpus callosum in autism. Neuroimage 34(1), 61-73 (2007) · doi:10.1016/j.neuroimage.2006.08.032
[4] Alexeev, B., Ward, R.: On the complexity of Mumford-Shah-type regularization, viewed as a relaxed sparsity constraint. IEEE Trans. Image Process. 19(10), 2787-2789 (2010) · Zbl 1371.94020 · doi:10.1109/TIP.2010.2048969
[5] Ambrosio, L., Tortorelli, V.M.: Approximation of functional depending on jumps by elliptic functional via \[{\varGamma }\] Γ-convergence. Commun. Pure Appl. Math. 43(8), 999-1036 (1990) · Zbl 0722.49020 · doi:10.1002/cpa.3160430805
[6] Arnaudon, M., Nielsen, F.: On approximating the Riemannian 1-center. Comput. Geom. 46(1), 93-104 (2013) · Zbl 1259.65036 · doi:10.1016/j.comgeo.2012.04.007
[7] Arsigny, V., Fillard, P., Pennec, X., Ayache, N.: Fast and simple calculus on tensors in the log-Euclidean framework. In: Medical Image Computing and Computer-Assisted Intervention-MICCAI 2005, pp. 115-122. Springer, Berlin (2005) · Zbl 1309.65071
[8] Assaf, Y., Pasternak, O.: Diffusion tensor imaging (DTI)-based white matter mapping in brain research: a review. J. Mol. Neurosci. 34(1), 51-61 (2008) · doi:10.1007/s12031-007-0029-0
[9] Bačák, M.: Computing medians and means in Hadamard spaces. SIAM J. Optim. 24, 1542-1566 (2014) · Zbl 1306.49046 · doi:10.1137/140953393
[10] Ballmann, W., Gromov, M., Schroeder, V.: Manifolds of Nonpositive Curvature. Birkhäuser, Boston (1985) · Zbl 0591.53001 · doi:10.1007/978-1-4684-9159-3
[11] Basser, P., Mattiello, J., LeBihan, D.: MR diffusion tensor spectroscopy and imaging. Biophys. J. 66(1), 259-267 (1994) · doi:10.1016/S0006-3495(94)80775-1
[12] Basu, S., Fletcher, T., Whitaker, R.: Rician noise removal in diffusion tensor MRI. In: Medical Image Computing and Computer-Assisted Intervention 2006, pp. 117-125. Springer, Berlin (2006)
[13] Behrens, T., Johansen-Berg, H., Jbabdi, S., Rushworth, M., Woolrich, M.: Probabilistic diffusion tractography with multiple fibre orientations: what can we gain? Neuroimage 34(1), 144-155 (2007) · doi:10.1016/j.neuroimage.2006.09.018
[14] Bergmann, R., Laus, F., Steidl, G., Weinmann, A.: Second order differences of cyclic data and applications in variational denoising. SIAM J. Imaging Sci. 7(4), 2916-2953 (2014) · Zbl 1309.65022 · doi:10.1137/140969993
[15] Bertsekas, D.: Multiplier methods: a survey. Automatica 12(2), 133-145 (1976) · Zbl 0321.49027 · doi:10.1016/0005-1098(76)90077-7
[16] Bhattacharya, R., Patrangenaru, V.: Large sample theory of intrinsic and extrinsic sample means on manifolds II. Ann. Stat. 1225-1259 (2005) · Zbl 1072.62033
[17] Bhattacharya, R., Patrangenaru, V.: Large sample theory of intrinsic and extrinsic sample means on manifolds I. Ann. Stat. 1-29 (2003) · Zbl 1020.62026
[18] Blake, A., Zisserman, A.: Visual Reconstruction. MIT Press, Cambridge (1987)
[19] Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23(11), 1222-1239 (2001) · doi:10.1109/34.969114
[20] Boysen, L., Kempe, A., Liebscher, V., Munk, A., Wittich, O.: Consistencies and rates of convergence of jump-penalized least squares estimators. Ann. Stat. 37(1), 157-183 (2009) · Zbl 1155.62034 · doi:10.1214/07-AOS558
[21] Chambolle, A.: Image segmentation by variational methods: Mumford and Shah functional and the discrete approximations. SIAM J. Appl. Math. 55(3), 827-863 (1995) · Zbl 0830.49015 · doi:10.1137/S0036139993257132
[22] Chambolle, A.: Finite-differences discretizations of the Mumford-Shah functional. ESAIM Math. Modell. Numer. Anal. 33(02), 261-288 (1999) · Zbl 0947.65076 · doi:10.1051/m2an:1999115
[23] Chan, T., Kang, S., Shen, J.: Total variation denoising and enhancement of color images based on the CB and HSV color models. J. Vis. Commun. Image Represent. 12, 422-435 (2001) · doi:10.1006/jvci.2001.0491
[24] Chefd’Hotel, C., Tschumperlé, D., Deriche, R., Faugeras, O.: Regularizing flows for constrained matrix-valued images. J. Math. Imaging Vis. 20(1-2), 147-162 (2004) · Zbl 1034.68585 · doi:10.1023/B:JMIV.0000011324.14508.fb
[25] Cheng, G., Salehian, H., Vemuri, B.: Efficient recursive algorithms for computing the mean diffusion tensor and applications to DTI segmentation. In: Computer Vision-ECCV 2012, pp. 390-401. Springer, Berlin (2012)
[26] Chen, B., Hsu, E.: Noise removal in magnetic resonance diffusion tensor imaging. Magn. Reson. Med. 54, 393-401 (2005) · doi:10.1002/mrm.20582
[27] Cook, P., Bai, Y., Nedjati-Gilani, S., Seunarine, K., Hall, M., Parker, G., Alexander, D.: Camino: Open-source diffusion-MRI reconstruction and processing. In: 14th Scientific Meeting of the International Society for Magnetic Resonance in Medicine, p. 2759 (2006) · Zbl 1296.65087
[28] Descoteaux, M., Angelino, E., Fitzgibbons, S., Deriche, R.: Regularized, fast, and robust analytical Q-ball imaging. Magn. Reson. Med. 58(3), 497-510 (2007) · doi:10.1002/mrm.21277
[29] do Carmo, M.: Riemannian Geometry. Birkhäuser, Boston (1992) · Zbl 0752.53001 · doi:10.1007/978-1-4757-2201-7
[30] Feddern, C., Weickert, J., Burgeth, B.: Level-set methods for tensor-valued images. In: Proc. Second IEEE Workshop on Geometric and Level Set Methods in Computer Vision, pp. 65-72 (2003)
[31] Ferreira, R., Xavier, J., Costeira, J., Barroso, V.: Newton algorithms for Riemannian distance related problems on connected locally symmetric manifolds. IEEE J. Sel. Top. Signal Process. 7, 634-645 (2013) · doi:10.1109/JSTSP.2013.2261799
[32] Fillard, P., Pennec, X., Arsigny, V., Ayache, N.: Clinical DT-MRI estimation, smoothing, and fiber tracking with log-Euclidean metrics. IEEE Trans. Med. Imaging 26(11), 1472-1482 (2007) · doi:10.1109/TMI.2007.899173
[33] Fletcher, P., Lu, C., Pizer, S., Joshi, S.: Principal geodesic analysis for the study of nonlinear statistics of shape. IEEE Trans. Med. Imaging 23, 995-1005 (2004) · doi:10.1109/TMI.2004.831793
[34] Fletcher, P.: Geodesic regression and the theory of least squares on Riemannian manifolds. Int. J. Comput. Vis. 105, 171-185 (2013) · Zbl 1304.62092 · doi:10.1007/s11263-012-0591-y
[35] Fletcher, P., Joshi, S.: Riemannian geometry for the statistical analysis of diffusion tensor data. Signal Process. 87(2), 250-262 (2007) · Zbl 1186.94126 · doi:10.1016/j.sigpro.2005.12.018
[36] Foong, J., Maier, M., Clark, C., Barker, G., Miller, D., Ron, M.: Neuropathological abnormalities of the corpus callosum in schizophrenia: a diffusion tensor imaging study. J. Neurol. Neurosurg. Psychiatry 68(2), 242-244 (2000) · doi:10.1136/jnnp.68.2.242
[37] Fornasier, M., March, R., Solombrino, F.: Existence of minimizers of the Mumford-Shah functional with singular operators and unbounded data. Ann. Mat. Pura Appl. 192(3), 361-391 (2013) · Zbl 1266.49071 · doi:10.1007/s10231-011-0228-8
[38] Fornasier, M., Ward, R.: Iterative thresholding meets free-discontinuity problems. Found. Comput. Math. 10(5), 527-567 (2010) · Zbl 1202.65070 · doi:10.1007/s10208-010-9071-3
[39] Frank, L.: Characterization of anisotropy in high angular resolution diffusion-weighted MRI. Magn. Reson. Med. 47(6), 1083-1099 (2002) · doi:10.1002/mrm.10156
[40] Friedrich, F., Kempe, A., Liebscher, V., Winkler, G.: Complexity penalized M-estimation. J. Comput. Graph. Stat. 17(1), 201-224 (2008) · doi:10.1198/106186008X285591
[41] Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6(6), 721-741 (1984) · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[42] Goh, A., Lenglet, C., Thompson, P., Vidal, R.: A nonparametric Riemannian framework for processing high angular resolution diffusion images (HARDI). In: IEEE Conference on Computer Vision and Pattern Recognition., pp. 2496-2503 (2009) · Zbl 1171.65451
[43] Grohs, P., Hardering, H., Sander, O.: Optimal a priori discretization error bounds for geodesic finite elements. Found. Comput. Math. 15, 1357-1411 (2014) · Zbl 1331.65153 · doi:10.1007/s10208-014-9230-z
[44] Grohs, P., Wallner, J.: Interpolatory wavelets for manifold-valued data. Appl. Comput. Harmonic Anal. 27, 325-333 (2009) · Zbl 1171.65451 · doi:10.1016/j.acha.2009.05.005
[45] Hess, C., Mukherjee, P., Han, E., Xu, D., Vigneron, D.: Q-ball reconstruction of multimodal fiber orientations using the spherical harmonic basis. Magn. Reson. Med. 56(1), 104-117 (2006) · doi:10.1002/mrm.20931
[46] Hohm, K., Storath, M., Weinmann, A.: An algorithmic framework for Mumford-Shah regularization of inverse problems in imaging. Inverse Probl. 31(11), 115011 (2015) · Zbl 1329.35351 · doi:10.1088/0266-5611/31/11/115011
[47] Jiang, M., Maass, P., Page, T.: Regularizing properties of the Mumford-Shah functional for imaging applications. Inverse Probl. 30(3), 035,007 (2014) · Zbl 1293.94016 · doi:10.1088/0266-5611/30/3/035007
[48] Johansen-Berg, H., Behrens, T.: Diffusion MRI: From Quantitative Measurement to In-Vivo Neuroanatomy. Academic Press, London (2009)
[49] Jonasson, L., Bresson, X., Hagmann, P., Cuisenaire, O., Meuli, R., Thiran, J.P.: White matter fiber tract segmentation in DT-MRI using geometric flows. Med. Image Anal. 9(3), 223-236 (2005) · doi:10.1016/j.media.2004.07.004
[50] Karcher, H.: Riemannian center of mass and mollifier smoothing. Commun. Pure Appl. Math. 30, 509-541 (1977) · Zbl 0354.57005 · doi:10.1002/cpa.3160300502
[51] Kendall, W.: Probability, convexity, and harmonic maps with small image I: uniqueness and fine existence. Proc. Lond. Math. Soc. 3, 371-406 (1990) · Zbl 0675.58042 · doi:10.1112/plms/s3-61.2.371
[52] Killick, R., Fearnhead, P., Eckley, I.: Optimal detection of changepoints with a linear computational cost. J. Am. Stat. Assoc. 107(500), 1590-1598 (2012) · Zbl 1258.62091 · doi:10.1080/01621459.2012.737745
[53] Kimmel, R., Sochen, N.: Orientation diffusion or how to comb a porcupine. J. Vis. Commun. Image Represent. 13, 238-248 (2002) · doi:10.1006/jvci.2001.0501
[54] Kirchheim, B.: Rectifiable metric spaces: local structure and regularity of the Hausdorff measure. Proc. Am. Math. Soc. 121(1), 113-123 (1994) · Zbl 0806.28004 · doi:10.1090/S0002-9939-1994-1189747-7
[55] Kubicki, M., McCarley, R., Westin, C.F., Park, H.J., Maier, S., Kikinis, R., Jolesz, F., Shenton, M.: A review of diffusion tensor imaging studies in schizophrenia. J. Psychiatr. Res. 41(1), 15-30 (2007) · doi:10.1016/j.jpsychires.2005.05.005
[56] Lai, R., Osher, S.: A splitting method for orthogonality constrained problems. J. Sci. Comput. 58(2), 431-449 (2014) · Zbl 1296.65087 · doi:10.1007/s10915-013-9740-x
[57] Le Bihan, D., Mangin, J.F., Poupon, C., Clark, C., Pappata, S., Molko, N., Chabriat, H.: Diffusion tensor imaging: concepts and applications. J. Magn. Reson. Imaging 13, 534-546 (2001) · doi:10.1002/jmri.1076
[58] Lellmann, J., Strekalovskiy, E., Koetter, S., Cremers, D.: Total variation regularization for functions with values in a manifold. In: Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 2944-2951 (2013)
[59] Massonnet, D., Feigl, K.: Radar interferometry and its application to changes in the earth’s surface. Rev. Geophys. 36, 441-500 (1998) · doi:10.1029/97RG03139
[60] Mumford, D., Shah, J.: Boundary detection by minimizing functionals. IEEE Conf. Comput. Vis. Pattern Recogn. 17, 137-154 (1985)
[61] Mumford, D., Shah, J.: Optimal approximations by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math. 42(5), 577-685 (1989) · Zbl 0691.49036 · doi:10.1002/cpa.3160420503
[62] Oller, J., Corcuera, J.: Intrinsic analysis of statistical estimation. Ann. Stat. 1562-1581 (1995) · Zbl 0843.62027
[63] Özarslan, E., Mareci, T.: Generalized diffusion tensor imaging and analytical relationships between diffusion tensor imaging and high angular resolution diffusion imaging. Magn. Reson. Med. 50(5), 955-965 (2003) · doi:10.1002/mrm.10596
[64] Pennec, X.: Intrinsic statistics on Riemannian manifolds: basic tools for geometric measurements. J. Math. Imaging Vis. 25(1), 127-154 (2006) · Zbl 1478.94072 · doi:10.1007/s10851-006-6228-4
[65] Pennec, X., Fillard, P., Ayache, N.: A Riemannian framework for tensor computing. Int. J. Comput. Vis. 66(1), 41-66 (2006) · Zbl 1287.53031 · doi:10.1007/s11263-005-3222-z
[66] Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the Mumford-Shah functional. In: IEEE International Conference on Computer Vision and Pattern Recognition, pp. 1133-1140 (2009) · Zbl 1155.62034
[67] Potts, R.: Some generalized order-disorder transformations. Math. Proc. Camb. Philos. Soc. 48(01), 106-109 (1952) · Zbl 0048.45601 · doi:10.1017/S0305004100027419
[68] Rahman, I.U., Drori, I., Stodden, V.C., Donoho, D.L., Schröder, P.: Multiscale representations for manifold-valued data. Multiscale Model. Simul. 4(4), 1201-1232 (2005) · Zbl 1236.65166 · doi:10.1137/050622729
[69] Rao, C.: Information and accuracy attainable in the estimation of statistical parameters. Bull. Calcutta Math. Soc. 37(3), 81-91 (1945) · Zbl 0063.06420
[70] Rosas, H., Lee, S., Bender, A., Zaleta, A., Vangel, M., Yu, P., Fischl, B., Pappu, V., Onorato, C., Cha, J.H., et al.: Altered white matter microstructure in the corpus callosum in Huntington’s disease: implications for cortical “disconnection”. Neuroimage 49(4), 2995-3004 (2010) · doi:10.1016/j.neuroimage.2009.10.015
[71] Rosman, G., Bronstein, M., Bronstein, A., Wolf, A., Kimmel, R.: Group-valued regularization framework for motion segmentation of dynamic non-rigid shapes. In: Scale Space and Variational Methods in Computer Vision, pp. 725-736. Springer, Berlin (2012) · Zbl 1342.94023
[72] Storath, M., Weinmann, A., Unser, M.: Exact algorithms for \[L^1\] L1-TV regularization of real-valued or circle-valued signals. SIAM J. Sci. Comput. (to appear). arXiv:1504.00499 · Zbl 1382.94029
[73] Storath, M., Weinmann, A., Demaret, L.: Jump-sparse and sparse recovery using Potts functionals. IEEE Trans. Signal Process. 62(14), 3654-3666 (2014) · Zbl 1394.94561 · doi:10.1109/TSP.2014.2329263
[74] Storath, M., Weinmann, A., Frikel, J., Unser, M.: Joint image reconstruction and segmentation using the Potts model. Inverse Probl. 31(2), 025,003 (2014) · Zbl 1342.94029 · doi:10.1088/0266-5611/31/2/025003
[75] Storath, M., Weinmann, A.: Fast partitioning of vector-valued images. SIAM J. Imaging Sci. 7(3), 1826-1852 (2014) · Zbl 1308.94023 · doi:10.1137/130950367
[76] Sturm, K.T.: Probability measures on metric spaces of nonpositive curvature. In: Heat Kernels and Analysis on Manifolds, Graphs, and Metric Spaces, Contemporary Mathematics, vol. 338, pp. 357-390. American Mathematical Society, Providence (2003) · Zbl 1040.60002
[77] Tsai, A., Yezzi Jr, A., Willsky, A.: Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification. IEEE Trans. Image Process. 10(8), 1169-1186 (2001) · Zbl 1062.68595 · doi:10.1109/83.935033
[78] Tschumperlé, D., Deriche, R.: Diffusion tensor regularization with constraints preservation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. I948-I953 (2001) · Zbl 1371.94020
[79] Tuch, D., Reese, T., Wiegell, M., Makris, N., Belliveau, J., Wedeen, V.: High angular resolution diffusion imaging reveals intravoxel white matter fiber heterogeneity. Magn. Reson. Med. 48(4), 577-582 (2002) · doi:10.1002/mrm.10268
[80] Tuch, D.: Q-ball imaging. Magn. Reson. Med. 52(6), 1358-1372 (2004) · doi:10.1002/mrm.20279
[81] Veksler, O.: Efficient graph-based energy minimization methods in computer vision. Ph.D. thesis, Cornell University (1999)
[82] Vese, L., Osher, S.: Numerical methods for p-harmonic flows and applications to image processing. SIAM J. Numer. Anal. 40, 2085-2104 (2002) · Zbl 1035.65065 · doi:10.1137/S0036142901396715
[83] Wallner, J., Dyn, N.: Convergence and \[C^1\] C1 analysis of subdivision schemes on manifolds by proximity. Comput. Aided Geom. Des. 22, 593-622 (2005) · Zbl 1083.65023 · doi:10.1016/j.cagd.2005.06.003
[84] Wang, Z., Vemuri, B.: An affine invariant tensor dissimilarity measure and its applications to tensor-valued image segmentation. In: IEEE Conference on Computer Vision and Pattern Recognition., pp. I228-I233 (2004) · Zbl 1285.90031
[85] Wang, Z., Vemuri, B.: DTI segmentation using an information theoretic tensor dissimilarity measure. IEEE Trans. Med. Imaging 24(10), 1267-1277 (2005) · doi:10.1109/TMI.2005.854516
[86] Weinmann, A.: Interpolatory multiscale representation for functions between manifolds. SIAM J. Math. Anal. 44, 162-191 (2012) · Zbl 1243.65026 · doi:10.1137/100803584
[87] Weinmann, A., Demaret, L., Storath, M.: Total variation regularization for manifold-valued data. SIAM J. Imaging Sci. 7(4), 2226-2257 (2014) · Zbl 1309.65071 · doi:10.1137/130951075
[88] Weinmann, A., Storath, M., Demaret, L.: The \[{L}^1\] L1-Potts functional for robust jump-sparse reconstruction. SIAM J. Numer. Anal. 53(1), 644-673 (2015) · Zbl 1312.65097 · doi:10.1137/120896256
[89] Wiegell, M., Tuch, D., Larsson, H., Wedeen, V.: Automatic segmentation of thalamic nuclei from diffusion tensor magnetic resonance imaging. NeuroImage 19(2), 391-401 (2003) · doi:10.1016/S1053-8119(03)00044-2
[90] Winkler, G., Liebscher, V.: Smoothers for discontinuous signals. J. Nonparametric Stat. 14(1-2), 203-222 (2002) · Zbl 1019.62090 · doi:10.1080/10485250211388
[91] Wittich, O., Kempe, A., Winkler, G., Liebscher, V.: Complexity penalized least squares estimators: analytical results. Math. Nachr. 281(4), 582-595 (2008) · Zbl 1152.62062 · doi:10.1002/mana.200510627
[92] Zhukov, L., Whitaker, R., Museth, K., Breen, D., Barr, A.H.: Level set modeling and segmentation of diffusion tensor magnetic resonance imaging brain data. J. Electron. Imaging 12(1), 125-133 (2003) · doi:10.1117/1.1527628
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.