×

Off-the-grid recovery of piecewise constant images from few Fourier samples. (English) Zbl 1372.94198

Summary: We introduce a method to recover a continuous domain representation of a piecewise constant two-dimensional image from few low-pass Fourier samples. Assuming the edge set of the image is localized to the zero set of a trigonometric polynomial, we show that the Fourier coefficients of the partial derivatives of the image satisfy a linear annihilation relation. We present necessary and sufficient conditions for unique recovery of the image from finite low-pass Fourier samples using the annihilation relation. We also propose a practical two-stage recovery algorithm that is robust to model-mismatch and noise. In the first stage we estimate a continuous domain representation of the edge set of the image. In the second stage we perform an extrapolation in Fourier domain by a least squares two-dimensional linear prediction, which recovers the exact Fourier coefficients of the underlying image. We demonstrate our algorithm on the superresolution recovery of MRI phantoms and real MRI data from low-pass Fourier samples, which shows benefits over standard approaches for single-image superresolution MRI.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
94A20 Sampling theory in information and communication theory
92C55 Biomedical imaging and signal processing
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
42B05 Fourier series and coefficients in several variables
65R32 Numerical methods for inverse problems for integral equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] R. G. Baraniuk, {\it Compressive sensing}, IEEE Signal Proc. Mag., 24 (2007), pp. 118-121, http://dx.doi.org/10.1109/MSP.2007.4286571 doi:10.1109/MSP.2007.4286571.
[2] T. Blu, P.-L. Dragotti, M. Vetterli, P. Marziliano, and L. Coulot, {\it Sparse sampling of signal innovations}, IEEE Signal Proc. Mag., 25 (2008), pp. 31-40, http://dx.doi.org/10.1109/MSP.2007.914998 doi:10.1109/MSP.2007.914998.
[3] M. Burger, {\it A level set method for inverse problems}, Inverse Problems, 17 (2001), pp. 1327-1355, http://dx.doi.org/10.1088/0266-5611/17/5/307 doi:10.1088/0266-5611/17/5/307. · Zbl 0985.35106
[4] M. Burger and S. J. Osher, {\it A survey on level set methods for inverse problems and optimal design}, European J. Appl. Math., 16 (2005), pp. 263-301, http://dx.doi.org/10.1017/S0956792505006182 doi:10.1017/S0956792505006182. · Zbl 1091.49001
[5] J. A. Cadzow, {\it Signal enhancement-a composite property mapping algorithm}, IEEE Trans. Acoust. Speech Signal Process., 36 (1988), pp. 49-62, http://dx.doi.org/10.1109/29.1488 doi:10.1109/29.1488. · Zbl 0649.93059
[6] E. J. Candès and C. Fernandez-Granda, {\it Super-resolution from noisy data}, J. Fourier Anal. Appl., 19 (2013), pp. 1229-1254, http://dx.doi.org/10.1007/s00041-013-9292-3 doi:10.1007/s00041-013-9292-3. · Zbl 1312.94015
[7] E. J. Candès and C. Fernandez-Granda, {\it Towards a mathematical theory of super-resolution}, Comm. Pure Appl. Math., 67 (2014), pp. 906-956, http://dx.doi.org/10.1002/cpa.21455 doi:10.1002/cpa.21455. · Zbl 1350.94011
[8] T. F. Chan and L. A. Vese, {\it A level set algorithm for minimizing the Mumford-Shah functional in image processing}, in Proceedings of the IEEE Workshop on Variational and Level Set Methods in Computer Vision, 2001, pp. 161-168, http://dx.doi.org/10.1109/VLSM.2001.938895 doi:10.1109/VLSM.2001.938895.
[9] R. Chartrand, {\it Fast algorithms for nonconvex compressive sensing: MRI reconstruction from very few data}, in Proceedings of the IEEE International Symposium on Biomedical Imaging (ISBI 2009), 2009, pp. 262-265, http://dx.doi.org/10.1109/ISBI.2009.5193034 doi:10.1109/ISBI.2009.5193034.
[10] R. Chartrand, E. Y. Sidky, and X. Pan, {\it Frequency extrapolation by nonconvex compressive sensing}, in Proceedings of the IEEE International Symposium on Biomedical Imaging (ISBI 2011), 2011, pp. 1056-1060, http://dx.doi.org/10.1109/ISBI.2011.5872583 doi:10.1109/ISBI.2011.5872583.
[11] C. Chen, P. Marziliano, and A. C. Kot, {\it 2D finite rate of innovation reconstruction method for step edge and polygon signals in the presence of noise}, IEEE Trans. Signal Process., 60 (2012), pp. 2851-2859, http://dx.doi.org/10.1109/TSP.2012.2189391 doi:10.1109/TSP.2012.2189391. · Zbl 1393.94674
[12] Y. Chen and Y. Chi, {\it Robust spectral compressed sensing via structured matrix completion}, IEEE Trans. Inform. Theory, 60 (2014), pp. 6576-6601, http://dx.doi.org/10.1109/TIT.2014.2343623 doi:10.1109/TIT.2014.2343623. · Zbl 1360.94064
[13] Q. Cheng and Y. Hua, {\it A review of parametric high-resolution methods}, in High-Resolution and Robust Signal Processing, Y. Hua, A. Gershman, and Q. Cheng, eds., Marcel Dekker, New York, 2004, pp. 1-62.
[14] L. Condat and A. Hirabayashi, {\it Cadzow denoising upgraded: A new projection method for the recovery of Dirac pulses from noisy linear measurements}, Sampl. Theory Signal Image Process., 14 (2015), pp. 17-47. · Zbl 1346.94023
[15] M. N. Do and M. Vetterli, {\it The contourlet transform: An efficient directional multiresolution image representation}, IEEE Trans. Image Process., 14 (2005), pp. 2091-2106, http://dx.doi.org/10.1109/TIP.2005.859376 doi:10.1109/TIP.2005.859376.
[16] D. L. Donoho, {\it Compressed sensing}, IEEE Trans. Inform. Theory, 52 (2006), pp. 1289-1306, http://dx.doi.org/10.1109/TIT.2006.871582 doi:10.1109/TIT.2006.871582. · Zbl 1288.94016
[17] O. Dorn and D. Lesselier, {\it Level set methods for inverse scattering}, Inverse Problems, 22 (2006), pp. R67-R131, http://dx.doi.org/10.1088/0266-5611/22/4/R01 doi:10.1088/0266-5611/22/4/R01. · Zbl 1191.35272
[18] P. L. Dragotti, M. Vetterli, and T. Blu, {\it Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang-Fix}, IEEE Trans. Signal Process., 55 (2007), pp. 1741-1757, http://dx.doi.org/10.1109/TSP.2006.890907 doi:10.1109/TSP.2006.890907. · Zbl 1391.94598
[19] R. E. Edwards, {\it Fourier Series: A Modern Introduction}, Vol. 2, Springer Science & Business Media, New York, 2012.
[20] R. Eslami and M. Jacob, {\it Robust reconstruction of MRSI data using a sparse spectral model and high resolution MRI priors}, IEEE Trans. Med. Imag., 29 (2010), pp. 1297-1309, http://dx.doi.org/10.1109/TMI.2010.2046673 doi:10.1109/TMI.2010.2046673.
[21] W. Fulton, {\it Introduction to Toric Varieties}, Ann. of Math. Stud. 131, Princeton University Press, Princeton, NJ, 1993. · Zbl 0813.14039
[22] E. Gong, F. Huang, K. Ying, W. Wu, S. Wang, and C. Yuan, {\it PROMISE: Parallel-imaging and compressed-sensing reconstruction of multicontrast imaging using sharable information}, Magn. Reson. Med., 73 (2015), pp. 523-535, http://dx.doi.org/10.1002/mrm.25625 doi:10.1002/mrm.25625.
[23] M. Guerquin-Kern, L. Lejeune, K. P. Pruessmann, and M. Unser, {\it Realistic analytical phantoms for parallel magnetic resonance imaging}, IEEE Trans. Med. Imag., 31 (2012), pp. 626-636, http://dx.doi.org/10.1109/TMI.2011.2174158 doi:10.1109/TMI.2011.2174158.
[24] E M. Haacke, Z.-P. Liang, and F. E. Boada, {\it Image reconstruction using POCS, model constraints, and linear prediction theory for the removal of phase, motion, and Gibbs artifacts in magnetic resonance and ultrasound imaging}, Opt. Eng., 29 (1990), pp. 555-566.
[25] E. M. Haacke, Z.-P. Liang, and S. H. Izen, {\it Superresolution reconstruction through object modeling and parameter estimation}, IEEE Trans. Acoust. Speech Signal Process., 37 (1989), pp. 592-595, http://dx.doi.org/10.1109/29.17545 doi:10.1109/29.17545.
[26] E M. Haacke, Z.-P. Liang, and S. H. Izen, {\it Constrained reconstruction: A superresolution, optimal signal-to-noise alternative to the Fourier transform in magnetic resonance imaging}, Med. Phys., 16 (1989), pp. 388-397, http://dx.doi.org/10.1118/1.596427 doi:10.1118/1.596427.
[27] J. P. Haldar, {\it Low-rank modeling of local k-space neighborhoods (LORAKS) for constrained MRI}, IEEE Trans. Med. Imag., 33 (2014), pp. 668-681, http://dx.doi.org/10.1109/TMI.2013.2293974 doi:10.1109/TMI.2013.2293974.
[28] J. P. Haldar, D. Hernando, S.-K. Song, and Z.-P. Liang, {\it Anatomically constrained reconstruction from noisy data}, Magn. Reson. Med., 59 (2008), pp. 810-818, http://dx.doi.org/10.1002/mrm.21536 doi:10.1002/mrm.21536.
[29] X. Hu, D. N. Levin, P. C. Lauterbur, and T. Spraggins, {\it SLIM: Spectral localization by imaging}, Magn. Reson. Med., 8 (1988), pp. 314-322, http://dx.doi.org/10.1002/mrm.1910080308 doi:10.1002/mrm.1910080308.
[30] Y. Hua, {\it Estimating two-dimensional frequencies by matrix enhancement and matrix pencil}, IEEE Trans. Signal Process., 40 (1992), pp. 2267-2280, http://dx.doi.org/10.1109/78.157226 doi:10.1109/78.157226. · Zbl 0850.93782
[31] M. Jacob, Y. Bresler, V. Toronov, X. Zhang, and A. Webb, {\it Level set algorithm for the reconstruction of functional activation in near-infrared spectroscopic imaging}, J. Biomed. Opt., (2006), 064029, http://dx.doi.org/10.1117/1.2400595 doi:10.1117/1.2400595.
[32] M. Jacob, X. Zhu, A. Ebel, N. Schuff, and Z.-P. Liang, {\it Improved model-based magnetic resonance spectroscopic imaging}, IEEE Trans. Med. Imag., 26 (2007), pp. 1305-1318, http://dx.doi.org/10.1109/TMI.2007.898583 doi:10.1109/TMI.2007.898583.
[33] K. H. Jin, D. Lee, and J. C. Ye, {\it A General Framework for Compressed Sensing and Parallel MRI using Annihilating Filter Based Low-Rank Hankel Matrix}, preprint, http://arxiv.org/abs/1504.00532 arXiv:1504.00532, 2015.
[34] I. Khalidov, D. Van De Ville, M. Jacob, F. Lazeyras, and M. Unser, {\it BSLIM: Spectral localization by imaging with explicit field inhomogeneity compensation}, IEEE Trans. Med. Imag., 26 (2007), pp. 990-1000, http://dx.doi.org/10.1109/TMI.2007.897385 doi:10.1109/TMI.2007.897385.
[35] J. M. Lee, {\it Smooth Manifolds}, Springer, New York, 2003.
[36] Z.-P. Liang, E. M. Haacke, and C. W. Thomas, {\it High-resolution inversion of finite Fourier transform data through a localised polynomial approximation}, Inverse Problems, 5 (1989), pp. 831-847, http://dx.doi.org/10.1088/0266-5611/5/5/011 doi:10.1088/0266-5611/5/5/011. · Zbl 0725.65142
[37] J. Luo, Y. Zhu, W. Li, P. Croisille, and I. E. Magnin, {\it MRI reconstruction from \(2\) D truncated k-space}, J. Magn. Reson. Imag., 35 (2012), pp. 1196-1206, http://dx.doi.org/10.1002/jmri.23538 doi:10.1002/jmri.23538.
[38] S. G. Mallat, {\it A theory for multiresolution signal decomposition: The wavelet representation}, IEEE Trans. Pattern Anal. Mach. Intell., 11 (1989), pp. 674-693, http://dx.doi.org/10.1109/34.192463 doi:10.1109/34.192463. · Zbl 0709.94650
[39] I. Maravic and M. Vetterli, {\it Sampling and reconstruction of signals with finite rate of innovation in the presence of noise}, IEEE Trans. Signal Process., 53 (2005), pp. 2788-2805, http://dx.doi.org/10.1109/TSP.2005.850321 doi:10.1109/TSP.2005.850321. · Zbl 1370.94398
[40] P. Milanfar, G. C. Verghese, W. C. Karl, and A. S. Willsky, {\it Reconstructing polygons from moments with connections to array processing}, IEEE Trans. Signal Process., 43 (1995), pp. 432-443, http://dx.doi.org/10.1109/78.348126 doi:10.1109/78.348126.
[41] D. Mumford and J. Shah, {\it Boundary detection by minimizing functionals}, in Image Understanding, Ablex, Norwood, MA, 1988, pp. 19-43.
[42] D. Mumford and J. Shah, {\it Optimal approximations by piecewise smooth functions and associated variational problems}, Comm. Pure Appl. Math., 42 (1989), pp. 577-685. · Zbl 0691.49036
[43] G. Ongie and M. Jacob, {\it Recovery of piecewise smooth images from few Fourier samples}, in Proceedings of the International Conference on Sampling Theory and Applications (SampTA 2015), Washington, D.C., 2015, pp. 543-547, http://dx.doi.org/10.1109/SAMPTA.2015.7148950 doi:10.1109/SAMPTA.2015.7148950.
[44] G. Ongie and M. Jacob, {\it Super-resolution MRI using finite rate of innovation curves}, in Proceedings of the IEEE International Symposium on Biomedical Imaging (ISBI 2015), Brooklyn, NY, 2015, http://dx.doi.org/10.1109/ISBI.2015.7164100 doi:10.1109/ISBI.2015.7164100.
[45] P. Pal and P. P. Vaidyanathan, {\it A grid-less approach to underdetermined direction of arrival estimation via low rank matrix denoising}, IEEE Signal Process. Lett., 21 (2014), pp. 737-741, http://dx.doi.org/10.1109/LSP.2014.2314175 doi:10.1109/LSP.2014.2314175.
[46] H. Pan, T. Blu, and P. L. Dragotti, {\it Sampling curves with finite rate of innovation}, IEEE Trans. Signal Process., 62 (2014), pp. 458-471, http://dx.doi.org/10.1109/TSP.2013.2292033 doi:10.1109/TSP.2013.2292033. · Zbl 1394.94831
[47] R. O. Schmidt, {\it Multiple emitter location and signal parameter estimation}, IEEE Trans. Antennas and Propagation, 34 (1986), pp. 276-280, http://dx.doi.org/10.1109/TAP.1986.1143830 doi:10.1109/TAP.1986.1143830.
[48] M. Schweiger, O. Dorn, A. Zacharopoulos, I. Nissila, and S. R. Arridge, {\it \(3\) D level set reconstruction of model and experimental data in diffuse optical tomography}, Opt. Express, 18 (2010), pp. 150-164, http://dx.doi.org/10.1364/OE.18.000150 doi:10.1364/OE.18.000150.
[49] I. R. Shafarevich, {\it Basic Algebraic Geometry. \(1\). Varieties in Projective Space}, Springer-Verlag, Berlin, 1994. · Zbl 0797.14001
[50] P. J. Shin, P. E. Z. Larson, M. A. Ohliger, M. Elad, J. M. Pauly, D. B. Vigneron, and M. Lustig, {\it Calibrationless parallel imaging reconstruction based on structured low-rank matrix completion}, Magn. Reson. Med., 72 (2014), pp. 959-970, http://dx.doi.org/10.1002/mrm.24997 doi:10.1002/mrm.24997.
[51] P. Shukla and P. L. Dragotti, {\it Sampling schemes for multidimensional signals with finite rate of innovation}, IEEE Trans. Signal Process., 55 (2007), pp. 3670-3686, http://dx.doi.org/10.1109/TSP.2007.894259 doi:10.1109/TSP.2007.894259. · Zbl 1391.94608
[52] J. Solymosi and T. Tao, {\it An incidence theorem in higher dimensions}, Discrete Comput. Geom., 48 (2012), pp. 255-280, http://dx.doi.org/10.1007/s00454-012-9420-x doi:10.1007/s00454-012-9420-x. · Zbl 1253.51004
[53] J.-L. Starck, E. J. Candès, and D. L. Donoho, {\it The curvelet transform for image denoising}, IEEE Trans. Image Process., 11 (2002), pp. 670-684, http://dx.doi.org/10.1109/TIP.2002.1014998 doi:10.1109/TIP.2002.1014998. · Zbl 1288.94011
[54] P. Stoica and R. L. Moses, {\it Introduction to Spectral Analysis}, Vol. 1, Prentice-Hall, Upper Saddle River, NJ, 1997. · Zbl 1051.62522
[55] M. Storath, A. Weinmann, and L. Demaret, {\it Jump-sparse and sparse recovery using Potts functionals}, 62 (2014), pp. 3654-3666, http://dx.doi.org/10.1109/TSP.2014.2329263 doi:10.1109/TSP.2014.2329263. · Zbl 1394.94561
[56] R. S. Strichartz, {\it A Guide to Distribution Theory and Fourier Transforms}, World Scientific, River Edge, NJ, 2003. · Zbl 1029.46039
[57] B. Sturmfels, {\it Polynomial equations and convex polytopes}, Amer. Math. Monthly, 105 (1998), pp. 907-922, http://dx.doi.org/10.2307/2589283 doi:10.2307/2589283. · Zbl 0988.52021
[58] G. Tang, B. N. Bhaskar, and B. Recht, {\it Near minimax line spectral estimation}, in Proceedings of the 47th Annual IEEE Conference on Information Sciences and Systems (CISS), 2013, pp. 1-6, http://dx.doi.org/10.1109/TIT.2014.2368122 doi:10.1109/TIT.2014.2368122. · Zbl 1359.94181
[59] A. Tsai, A. Yezzi, Jr., and A. S. Willsky, {\it Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification}, IEEE Trans. Image Process., 10 (2001), pp. 1169-1186, http://dx.doi.org/10.1109/83.935033 doi:10.1109/83.935033. · Zbl 1062.68595
[60] N. Vaswani and W. Lu, {\it Modified-CS: Modifying compressive sensing for problems with partially known support}, IEEE Trans. Signal Process., 58 (2010), pp. 4595-4607, http://dx.doi.org/10.1109/ISIT.2009.5205717 doi:10.1109/ISIT.2009.5205717. · Zbl 1392.94045
[61] L. A. Vese and T. F. Chan, {\it A multiphase level set framework for image segmentation using the Mumford and Shah model}, Int. J. Comput. Vis., 50 (2002), pp. 271-293, http://dx.doi.org/10.1023/A:1020874308076 doi:10.1023/A:1020874308076. · Zbl 1012.68782
[62] M. Vetterli, P. Marziliano, and T. Blu, {\it Sampling signals with finite rate of innovation}, IEEE Trans. Signal Process., 50 (2002), pp. 1417-1428, http://dx.doi.org/10.1109/TSP.2002.1003065 doi:10.1109/TSP.2002.1003065. · Zbl 1369.94309
[63] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, {\it Image quality assessment: From error visibility to structural similarity}, IEEE Trans. Image Process., 13 (2004), pp. 600-612, http://dx.doi.org/10.1109/TIP.2003.819861 doi:10.1109/TIP.2003.819861.
[64] Q.-S. Xiang, {\it Accelerating MRI by skipped phase encoding and edge deghosting (SPEED)}, Magn. Reson. Med., 53 (2005), pp. 1112-1117, http://dx.doi.org/10.1002/mrm.20453 doi:10.1002/mrm.20453.
[65] W. Xu, J.-F. Cai, K. V. Mishra, M. Cho, and A. Kruger, {\it Precise semidefinite programming formulation of atomic norm minimization for recovering d-dimensional \((d ≥ 2)\) off-the-grid frequencies}, in Proceedings of the IEEE Information Theory and Applications Workshop (ITA), 2014, http://dx.doi.org/10.1109/ITA.2014.6804267 doi:10.1109/ITA.2014.6804267.
[66] J. C. Ye, Y. Bresler, and P. Moulin, {\it A self-referencing level-set method for image reconstruction from sparse Fourier samples}, Int. J. Comput. Vis., 50 (2002), pp. 253-270, http://dx.doi.org/10.1023/A:1020822324006 doi:10.1023/A:1020822324006. · Zbl 1012.68783
[67] T. Zhang, J. M. Pauly, S. S. Vasanawala, and M. Lustig, {\it Coil compression for accelerated imaging with Cartesian sampling}, Magn. Reson. Med., 69 (2013), pp. 571-582, http://dx.doi.org/10.1002/mrm.24267 doi:10.1002/mrm.24267.
[68] M. Zhu and T. Chan, {\it An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration}, UCLA CAM Report 08-34, 2008.
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.