Multiscale higher-order TV operators for L1 regularization

Toby Sanders1, Rodrigo B. Platte1
1School of Mathematical and Statistical Sciences, Arizona State University, P.O. Box 871804, Tempe, AZ, 85287-1804, USA

Tóm tắt

AbstractIn the realm of signal and image denoising and reconstruction, $$\ell _1$$ 1 regularization techniques have generated a great deal of attention with a multitude of variants. In this work, we demonstrate that the $$\ell _1$$ 1 formulation can sometimes result in undesirable artifacts that are inconsistent with desired sparsity promoting $$\ell _0$$ 0 properties that the $$\ell _1$$ 1 formulation is intended to approximate. With this as our motivation, we develop a multiscale higher-order total variation (MHOTV) approach, which we show is related to the use of multiscale Daubechies wavelets. The relationship of higher-order regularization methods with wavelets, which we believe has generally gone unrecognized, is shown to hold in several numerical results, although notable improvements are seen with our approach over both wavelets and classical HOTV. These results are presented for 1D signals and 2D images, and we include several examples that highlight the potential of our approach for improving two- and three-dimensional electron microscopy imaging. In the development approach, we construct the tools necessary for MHOTV computations to be performed efficiently, via operator decomposition and alternatively converting the problem into Fourier space.

Từ khóa


Tài liệu tham khảo

Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D Nonlinear Phenomena 60(1), 259–268 (1992)

Wei, S.-J., Zhang, X.-L., Shi, J., Xiang, G.: Sparse reconstruction for SAR imaging based on compressed sensing. Prog Electromagn Res 109, 63–81 (2010)

Bhattacharya, S., Blumensath, T., Mulgrew, B., Davies, M.: Fast encoding of synthetic aperture radar raw data using compressed sensing. In: IEEE 2007 IEEE/SP 14th workshop on statistical signal processing, pp. 448–452 (2007)

Lustig, M., Donoho, D., Pauly, J.M.: Sparse MRI: the application of compressed sensing for rapid MR imaging. Magn. Resonance Med. 58(6), 1182–1195 (2007)

Lysaker, M., Lundervold, A., Tai, X.-C.: Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time. IEEE Trans. Image Process. 12(12), 1579–1590 (2003). https://doi.org/10.1109/TIP.2003.819229

Ma, S., Yin, W., Zhang, Y., Chakraborty, A.: An efficient algorithm for compressed MR imaging using total variation and wavelets. In: IEEE conference on computer vision and pattern recognition, 2008. CVPR 2008, pp. 1–8 (2008). https://doi.org/10.1109/CVPR.2008.4587391

Leary, R., Saghi, Z., Midgley, P.A., Holland, D.J.: Compressed sensing electron tomography. Ultramicroscopy 131, 70–91 (2013). https://doi.org/10.1016/j.ultramic.2013.03.019

Sanders, T., Gelb, A., Platte, R., Arslan, I., Landskron, K.: Recovering fine details from under-resolved electron tomography data using higher order total variation regularization. Ultramicroscopy 174, 97–105 (2017). https://doi.org/10.1016/j.ultramic.2016.12.020

Sanders, T., Dwyer, C.: Subsampling and inpainting approaches for electron tomography. Ultramicroscopy 182, 292–302 (2017)

King, E.J., Kutyniok, G., Lim, W.-Q.: Image inpainting: theoretical analysis and comparison of algorithms. In: SPIE optical engineering + applications, pp. 885–802 (2013)

Eldar, Y.C., Kutyniok, G.: Compressed sensing: theory and applications. Cambridge University Press, New York (2012)

Candès, E., Romberg, J.: Sparsity and incoherence in compressive sampling. Inverse Probl. 23(3), 969 (2007)

Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006)

Chan, T., Marquina, A., Mulet, P.: High-order total variation-based image restoration. SIAM J. Sci. Comput. 22(2), 503–516 (2000)

Blomgren, P., Chan, T.F., Mulet, P., Wong, C.-K., et al.: Total variation image restoration: numerical methods and extensions. ICIP 3, 384–387 (1997)

Bredies, K., Kunisch, K., Pock, T.: Total generalized variation. SIAM J. Imaging Sci. 3(3), 492–526 (2010). https://doi.org/10.1137/090769521

Hu, Y., Jacob, M.: Higher degree total variation (HDTV) regularization for image recovery. IEEE Trans. Image Process. 21(5), 2559–2571 (2012)

Starck, J.-L., Murtagh, F., Fadili, J.M.: Sparse image and signal processing: wavelets, curvelets, morphological diversity. Cambridge University Press, New York (2010)

Mallat, S.: A wavelet tour of signal processing: the sparse way. Academic Press, Burlington (2008)

Archibald, R., Gelb, A., Platte, R.B.: Image reconstruction from undersampled Fourier data using the polynomial annihilation transform. J. Sci. Comput. 67, 1–21 (2015)

Stefan, W., Renaut, R.A., Gelb, A.: Improved total variation-type regularization using higher order edge detectors. SIAM J. Imaging Sci. 3(2), 232–251 (2010)

Setzer, S., Steidl, G., Teuber, T.: Infimal convolution regularizations with discrete l1-type functionals. Commun. Math. Sci. 9(3), 797–827 (2011)

Chambolle, A., Lions, P.-L.: Image recovery via total variation minimization and related problems. Numer. Math. 76(2), 167–188 (1997)

Unser, M., Fageot, J., Ward, J.P.: Splines are universal solutions of linear inverse problems with generalized TV regularization. SIAM Rev. 59(4), 769–793 (2017)

Steidl, G., Didas, S., Neumann, J.: Splines in higher order TV regularization. Int. J. Comput. Vision 70(3), 241–255 (2006)

Scherzer, O., Weickert, J.: Relations between regularization and diffusion filtering. J. Math. Imaging Vision 12(1), 43–63 (2000)

Steidl, G., Weickert, J.: Relations between soft wavelet shrinkage and total variation denoising. Joint pattern recognition symposium, pp. 198–205. Springer, Berlin (2002)

Steidl, G., Weickert, J., Brox, T., Mrázek, P., Welk, M.: On the equivalence of soft wavelet shrinkage, total variation diffusion, total variation regularization, and sides. SIAM J. Numer. Anal. 42(2), 686–713 (2004)

Kamilov, U., Bostan, E., Unser, M.: Wavelet shrinkage with consistent cycle spinning generalizes total variation denoising. IEEE Signal Process. Lett. 19(4), 187–190 (2012)

Guo, K., Labate, D.: Optimally sparse multidimensional representation using shearlets. SIAM J. Math. Anal. 39(1), 298–318 (2007)

Kutyniok, G.: Shearlets: multiscale analysis for multivariate data. Springer, New York (2012)

Saghi, Z., Benning, M., Leary, R., Macias-Montero, M., Borras, A., Midgley, P.A.: Reduced-dose and high-speed acquisition strategies for multi-dimensional electron microscopy. Adv. Struct. Chem. Imaging 1(1), 1–10 (2015)

Sanders, T.: Parameter selection for HOTV regularization. Appl. Numer. Math. 125, 1–9 (2018)

Daubechies, I.: Ten lectures on wavelets, vol. 61. SIAM, Philadelphia (1992)

Coifman, R.R., Donoho, D.L.: Translation-invariant de-noising. Wavelets and statistics, pp. 125–150. Springer, New York (1995)

Temizel, A., Vlachos, T., Visioprime, W.: Wavelet domain image resolution enhancement using cycle-spinning. Electron. Lett. 41(3), 119–121 (2005)

Li, C., Yin, W., Jiang, H., Zhang, Y.: An efficient augmented lagrangian method with applications to total variation minimization. Comput. Optim. Appl. 56(3), 507–530 (2013). https://doi.org/10.1007/s10589-013-9576-1

Goldstein, T., Osher, S.: The split Bregman method for l1-regularized problems. SIAM J. Imaging Sci. 2(2), 323–343 (2009). https://doi.org/10.1137/080725891

Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sci. 1(3), 248–272 (2008). https://doi.org/10.1137/080724265

Sanders, T.: MATLAB Imaging algorithms: image reconstruction, restoration, and alignment, with a focus in tomography. http://www.toby-sanders.com/software, https://doi.org/10.13140/RG.2.2.33492.60801. Accessed 19 Aug 2016.

Levin, B.D., Padgett, E., Chen, C.-C., Scott, M., Xu, R., Theis, W., Jiang, Y., Yang, Y., Ophus, C., Zhang, H.: Nanomaterial datasets to advance tomography in scanning transmission electron microscopy. Sci Data 3, 160041 (2016)

Venkatakrishnan, S.V., Drummy, L.F., Jackson, M.A., De Graef, M., Simmons, J., Bouman, C.A.: A model based iterative reconstruction algorithm for high angle annular dark field-scanning transmission electron microscope (HAADF-STEM) tomography. IEEE Trans. Image Process. 22(11), 4532–4544 (2013)

Levin, B.D., Jiang, Y., Padgett, E., Waldon, S., Quammen, C., Harris, C., Ayachit, U., Hanwell, M., Ercius, P., Muller, D.A.: Tutorial on the visualization of volumetric data using tomviz. Microscopy Today 26(1), 12–17 (2018)

Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4(5), 303–320 (1969)

Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., Stuetzle, W.: Multiresolution analysis of arbitrary meshes. In: Proceedings of the 22nd annual conference on computer graphics and interactive techniques, ACM, New York, pp. 173–182 (1995).

Tenoudji, F.C.: Wavelets; multiresolution analysis. Analog and digital signal analysis. Springer, Switzerland (2016)

Gao, H.-Y.: Wavelet shrinkage denoising using the non-negative garrote. J. Comput. Graph. Stat. 7(4), 469–488 (1998)

Taswell, C.: The what, how, and why of wavelet shrinkage denoising. Comput. Sci. Eng. 2(3), 12–19 (2000)