Low-rank Fourier interpolation for compressed sensing imaging

A novel annihilating filter-based low-rank Hankel matrix approach can be combined with classical analytic reconstruction techniques for application to several compressed sensing imaging problems.
27 July 2016
Jong Chul Ye

Fourier imaging problems (in which unknown signals are recovered from Fourier measurements) are important in many applications. According to classical Nyquist sampling theory, the required Fourier sampling rate must be at least twice that of the signal bandwidth. In the past, this has been considered as the fundamental resolution limit in many imaging problems. However, with the recent theory of compressive sampling (CS),1–3 it is now possible to overcome the Nyquist limit for the accurate recovery of unknown sparse signals from underdetermined Fourier measurements in various imaging applications, e.g., accelerated magnetic resonance imaging (MRI), low-dose x-ray computed tomography, and optics.

Purchase SPIE Field Guide to Image ProcessingTo facilitate more robust reconstruction, recovery algorithms usually take the form of a penalized least squares or a constrained optimization framework (which are dependent on the specific signal representation and discretization scheme, rather than the nature of the original problem in the continuous domain). The Fourier CS problem is also closely related to classical harmonic retrieval problems and the sampling theory of finite rate of innovations (FRI).4–8 Although these methods do not require any discretization, they are less robust to perturbations in the measurements because the algorithm requires polynomial root findings.

To address this, we recently proposed a drastically different two-step Fourier CS framework. This can be implemented as a Fourier-domain interpolation, after which we can conduct a signal reconstruction by using classical analytic reconstruction methods.9–14 We believe that our two-step approach—the annihilating filter-based low-rank Hankel (ALOHA) matrix approach—can be used as the missing link between the CS and analytic reconstruction (because the best of the two worlds can be fully exploited in each step of the framework).

The main idea for ALOHA originated from the fundamental duality between the sparsity in the primary space and the low rankness of a structured matrix in the spectral domain.9 For example, if the underlying signal is a periodic stream of Diracs, we can calculate the annihilating filter in the Fourier domain and can thus null-out the Fourier series coefficients through the use of discrete convolution. Accordingly, we can construct a rank-deficient Hankel-structured matrix. In general, when the signal belongs to a general class of FRI signals, we can always find the minimum length annihilating filter4 for the weighted Fourier data, and the low-rank relationship always holds.9 Consequently, if some of the Fourier data for an FRI signal is missing, we can construct an appropriately weighted Hankel matrix with missing elements, and these elements can be recovered based on low-rank matrix completion algorithms.9, 17,18

Our two-layer approach is very useful for real-world applications because the low-rank interpolator can be added as a digital correction filter to existing systems. For example, the application of ALOHA to accelerated MRI problems is illustrated in Figure 1.10–12 For the case of TV regularization, structural distortion around the image edges can be easily recognized. In contrast, our ALOHA reconstruction provided the best edge structures, without boosting the noise level. We have also used a sparse and low-rank decomposition of our ALOHA matrix to decouple sparse outliers for magnetic resonance artifact removal problems.13 Our ALOHA results (see Figure 2) show that the corrupted (from low-intensity impulse noise) image could be decomposed from the down-sampled k-space (the 2D or 3D Fourier transform) data (at an acceleration factor of 5) and produce a clear—close to the original—image.

Figure 1. Illustration of the application of the annihilating filter-based low-rank Hankel (ALOHA) matrix approach to compressed sensing of magnetic resonance imaging (MRI) data (at ×4 acceleration). The original (ORIG) images are shown on the left, the results of a total variation (TV) reconstruction are shown in the center, and the ALOHA results are shown on the right. NMSE: Normalized mean square error.

Figure 2. The ALOHA approach is used to provide a robust decomposition of corrupted MRI data (at ×5 acceleration) with impulse noise. The original image (left) is decomposed into a low-rank component (middle) and an artifact component (right).

Our ALOHA concept is so general that it can also be used for other acquisition scenarios, e.g., in super-resolution microscopy (see Figure 3). For these experiments, the goal was to find the locations of fluorescent probes (Picogreen) within the images. As these fluorescent probes could be modeled as a stream of Diracs, a Hankel matrix from a properly deconvolved spectrum was low-ranked. We therefore estimated the optimal blur kernel from the measurement that gave the lowest ranked Hankel matrix.20 Moreover, after the deconvolution, we achieved true grid-free localization through classical spectral estimation techniques (using only the spectral data).

Figure 3. Results from live cell imaging experiments. The human osteosarcoma (U2OS) cells in these images were labeled with Picogreen (a fluorescent probe). (a) A conventional diffraction-limited wide-field image, constructed by accumulating 2000 raw frames. Three different reconstructions of the image in (a) are shown in (b) to (d). The deconvolution-STORM15 and FALCON16reconstruction methods are used for (b) and (c), respectively. The image in (d) was obtained with the ALOHA approach. Scale bars indicate 2μm.

Another application of our ALOHA technique is for image processing. For example, we can use ALOHA for missing data interpolation (known as image inpainting), as illustrated in Figure 4.14 Our results provide near-perfect interpolation, even in the textured area of the ‘Barbara’ test image. In addition, we use ALOHA to successfully interpolate large missing areas of the test images (see Figure 4). Furthermore, the impulse noise in the images can be considered as sparse outliers. We can thus use the sparse and low-rank decomposition of the ALOHA matrix to decouple the impulse noise.21 Indeed, our ALOHA method clearly outperforms existing approaches for impulse noise removal (see Figure 5).

Figure 4. Examples of image inpainting achieved with the ALOHA approach. The original images and images with missing pixels are shown in the left and middle columns, respectively. The results of the ALOHA inpainting are shown on the right.

Figure 5. Comparison of impulse noise removal achieved with ALOHA (bottom right) and the existing total variation L119 approach (bottom left). The original image and the impulse noise (30%) level are shown in the top left and right, respectively. PSNR: Peak signal-to-noise ratio.

In summary, we have developed a low-rank Fourier interpolation framework for compressed sensing reconstruction problems. In our ALOHA approach we use a structured low-rank interpolator in the measurement domain before the application of an analytic reconstruction procedure. Compared with existing CS approaches, our new method is quite general and can be easily combined with classical analytic reconstruction techniques for various imaging problems. Indeed, the generality of the ALOHA approach means that it can be used basically for all Fourier imaging applications. In our current work we are thus investigating its application to x-ray computed tomography, ultrasound imaging, and optical diffraction tomography.

This study was supported by the Korea Science and Engineering Foundation (grant NRF-2014R1A2A1A11052491).

Jong Chul Ye
Korea Advanced Institute of Science and Technology
Daejeon, Republic of Korea

Jong Chul Ye is currently a full professor in the Department of Bio and Brain Engineering and an endowed chair professor. He has served as an associate editor of IEEE Transactions on Image Processing, and IEEE Transactions on Computational Imaging, as well as an editorial board member for Magnetic Resonance in Medicine.

1. D. L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory 52, p. 1289-1306, 2006.
2. E. J. Candes, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory 52, p. 489-509, 2006.
3. E. J. Candes, T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory 51, p. 4203-4215, 2005.
4. M. Vetterli, P. Marziliano, T. Blu, Sampling signals with finite rate of innovation, IEEE Trans. Signal Process. 50, p. 1417-1428, 2002.
5. R. Prony, Essai expérimental et analytique, J. École Polytechn. Floréal Plairial 1, p. 24-76, 1795.
6. Y. Hua, T. K. Sarkar, Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise, IEEE Trans. Acoust. Speech Signal Process. 38, p. 814-824, 1990.
7. P. L. Dragotti, M. Vetterli, T. Blu, Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang--Fix, IEEE Trans. Signal Process. 55, p. 1741-1757, 2007.
8. I. Maravic, M. Vetterli, Sampling and reconstruction of signals with finite rate of innovation in the presence of noise, IEEE Trans. Signal Process. 53, p. 2788-2805, 2005.
9. J. C. Ye, J. M. Kim, K. H. Jin, K. Lee, Compressive sampling using annihilating filter-based low-rank interpolation, arXiv:1511.08975 [cs.IT] , 2015.
10. K. H. Jin, D. Lee, J. C. Ye, A general framework for compressed sensing and parallel MRI using annihilating filter based low-rank Hankel matrix, arXiv:1504.00532 [cs.IT] , 2015.
11. D. Lee, K. H. Jin, E. Y. Kim, S.-H. Park, J. C. Ye, Acceleration of MR parameter mapping using annihilating filter-based low rank Hankel matrix (ALOHA), Magnet. Resonance Med. , 2016. doi:10.1002/mrm.26081
12. J. Lee, K. H. Jin, J. C. Ye, Reference-free single-pass EPI Nyquist ghost correction using annihilating filter-based low rank Hankel matrix (ALOHA), Magnet. Resonance Med. , 2016. doi:10.1002/mrm.26077
13. K. H. J. Jin, J.-Y. U. Um, D. Lee, J. Lee, S.-H. Park, J. C. Ye, MRI artifact correction using sparse + low-rank decomposition of annihilating filter-based Hankel matrix, Magnet. Resonance Med. , in press, 2016.
14. K. H. Jin, J. C. Ye, Annihilating filter-based low-rank Hankel matrix approach for image inpainting, IEEE Trans. Image Process. 24, p. 3498-3511, 2015.
15. E. A. Mukamel, H. Babcock, X. Zhuang, Statistical deconvolution for superresolution fluorescence microscopy, Biophys. J. 102, p. 2391-2400, 2012.
16. J. Min, C. Vonesch, H. Kirshner, L. Carlini, N. Olivier, S. Holden, S. Manley, J. C. Ye, M. Unser, FALCON: fast and unbiased reconstruction of high-density super-resolution microscopy data, Sci. Rep. 4, p. 4577, 2014. doi:10.1038/srep04577
17. E. J. Candes, T. Tao, The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inf. Theory 56, p. 2053-2080, 2010.
18. D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inf. Theory 57, p. 1548-1566, 2011.
19. J. Yang, Y. Zhang, W. Yin, An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise, Soc. Indust. Appl. Math. J. Sci. Comp. 31, p. 2842-2865, 2009.
20. J. Min, L. Carlini, M. Unser, S. Manley, J. C. Ye, Fast live cell imaging at nanometer scale using annihilating filter-based low rank Hankel matrix approach, Proc. SPIE 9597, p. 95970V, 2015. doi:10.1117/12.2187393
21. K. H. Jin, J. C. Ye, Sparse + low rank decomposition of annihilating filter-based Hankel matrix for impulse noise removal, arXiv:1510.05559 [cs.CV] , 2015.
Recent News
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?