A Review on Image Reconstruction Using Compressed Sensing Algorithms: OMP, CoSaMP and NIHT

Full Text (PDF, 1011KB), PP.30-41

Views: 0 Downloads: 0

Author(s)

Hemant S. Goklani 1,* Jignesh N. Sarvaiya 1 Fahad Abdul 1

1. Electronics Engineering Department, SVNIT, Surat, 395007, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2017.08.04

Received: 12 Apr. 2017 / Revised: 17 Apr. 2017 / Accepted: 20 Apr. 2017 / Published: 8 Aug. 2017

Index Terms

Compressed Sensing (CS), Sparsity, Sampling, Nyquist rate, Orthgonal Matching Pursuit (OMP), Compressive Sampling Matching Pursuit(CoSaMP) and Normalized Iterative Hard Thresholding (NIHT)

Abstract

A sampled signal can be properly reconstructed if the sampling rate follows the Nyquist criteria. If Nyquist criteria is imposed on various image and video processing applications, a large number of samples are produced. Hence, storage, processing and transmission of these huge amounts of data make this task impractical. As an alternate, Compressed Sensing (CS) concept was applied to reduce the sampling rate. Compressed sensing method explores signal sparsity and hence the signal acquisition process in the area of transformation can be carried out below the Nyquist rate. As per CS theory, signal can be represented by alternative non-adaptive linear projections, which preserve the signal structure and the reconstruction of the signal can be achieved using optimization process. Hence signals can be reconstructed from severely undersampled measurements by taking advantage of their inherent low-dimensional structure. As Compressed Sensing, requires a lower sampling rate for reconstruction, data captured within the specified time will be obviously less than the traditional method. 
In this paper, three Compressed Sensing algorithms, namely Orthogonal Matching Pursuit (OMP), Compressive Sampling Matching Pursuit (CoSaMP) and Normalized Iterative Hard Thresholding (NIHT) are reviewed and their performance is evaluated at different sparsity levels for image reconstruction.

Cite This Paper

Hemant S. Goklani, Jignesh N. Sarvaiya, Fahad Abdul,"A Review on Image Reconstruction Using Compressed Sensing Algorithms: OMP, CoSaMP and NIHT", International Journal of Image, Graphics and Signal Processing(IJIGSP), Vol.9, No.8, pp.30-41, 2017. DOI: 10.5815/ijigsp.2017.08.04

Reference

[1]V. Kotelnikov, “On the carrying capacity of the ether and wire in telecommunications, In Izd. Red. Upr. Svyazi RKKA, Moscow, Russia, 1933.

[2]H. Nyquist, “Certain topics in telegraph transmission theory, Trans. AIEE, 47:617644,1928. DOI: 10.1109/5.989875.

[3]D.L.Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52:1289-1306, 2006. DOI:10.1109/TIT.2006.871582.

[4]Cand’es, E.J.Wakin, M.B, “An Introduction To Compressive Sampling, Signal Processing Magazine IEEE, Vol.2 (5), March 2008. DOI: 10.1109/MSP.2007.914731.

[5]E.Candes, J.Romberg, “Sparsity and incoherence in compressive sampling, Inverse Problems, Vol.23, p.969, 2007. DOI:10.1088/0266- 5611/23/3/008.

[6]E.Candes, J.Romberg, T.Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans.Inform.Theory, Vol.52, no.2, p.489, 2006. DOI:10.1109/TIT.2005.862083

[7]Yonina C. Eldar, Gitta Kutyniok, “Compressed Sensing, Theory and application, Cambridge University Press,2012.

[8]M. Vetterli, P. Marziliano, T. Blu, “Sampling signals with finite rate of innovation, IEEE Trans. Signal Processing, Vol. 50(6):1417-1428, 2002. DOI: 10.1109/TSP.2002.1003065.

[9]A.Beurling, “Sur les integrales de Fourier absolument convergentes et leur application a une transformation fonctionelle”, In Proc. Scandinavian Math. Congress, Helsinki, Finland, 1938.

[10]E.Candes, “The restricted isometry property and its implications for compressed sensing”, Comptes Rendus Mathematique, Vol.346, no.9-10, pp.589-592, 2008. DOI:10.1016/j.crma.2008.03.014.

[11]E. Candes and T. Tao, Decoding by linear programing, IEEE Transactions on Information Theory, 51(12):42034215, Dec. 2005. DOI: 10.1109/TIT.2005.858979

[12]Tropp, “Greed is Good: Algorithmic Results for Sparse Approximation, IEEE Transactions on information theory, Vol. 50(10),Oct 2004.DOI: 10.1109/TIT.2004.834793.

[13]J. A. Tropp, A. C. Gilbert, and M. J. Strauss, “Sparse representations in signal processing”, in Proc. 2005 IEEE Intl. Conf. Acoustics, Speech, and Signal Processing(ICASSP), Vol.5, pp. 721-724, Philadelphia, PA, Mar 2005.DOI: 10.1109/TIT.2004.834793.

[14]Schnas, H. Rauhut and P. Vandergheynst, “Compressed sensing and redundant dictionaries, IEEE Transactions on Information Theory, Vol. 54(5):22102219, 2008. DOI: 10.1109/TIT.2008.920190.

[15]Scaglione, A., Xiao Li, “Compressed channel sensing: Is the Restricted Isometry Property the right metric?, Digital Signal Processing (DSP), 2011 17th International Conference on, pp.18, 2011. DOI:10.1109/ICDSP.2011.6005010.

[16]Qun Mo, Yi Shen, “A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit, Vol. 58(6), pp. 3654-3656, 2012.DOI: 10.1109/TIT.2012.2185923.

[17]J.Tropp, A.Gilbert, “Signal recovery from random measurements via orthogonal matching pursuit”, Information Theory, Vol.53 (12), pp. 46-55, 2007.DOI: 10.1109/TIT.2007.909108.

[18]Meenakshi, Sumit Budhiraja,“Compressive Sensing based Image Reconstruction Using Generalized Adaptive OMP with Forward-Backward Movement”, International Journal of Image, Graphics and Signal Processing(IJIGSP), Vol.8, No.10, pp.19-28, 2016.DOI:10.5815/ijigsp.2016.10.03.

[19]S.Mallat, Z.Zhang,“Matching pursuits with time-frequency dictionaries, IEEE Transactions on signal processing, Vol.41 (12), pp.3397-3415, 1993.DOI: 10.1109/78.258082.

[20]D.Needell, J.Tropp, “CoSaMP: Iterative signal recovery from incomplete and inaccurate samples”, Applied and Computational Harmonic Analysis, Vol.26 (3), pp.301-321, 2009.DOI:10.1016/j.acha.2008.07.002.

[21]T.Blumensath, M.Davies. “Iterative thresholding for sparse approximations”, Journal of Fourier Analysis and Applications, special issue on sparsity , 2008. DOI: 10.1007/s00041-008-9035-z.

[22]T.Blumensath, M.Davies, “Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance”, IEEE Journal of Selected Topics in Signal Processing, 2010. DOI: 10.1109/JSTSP.2010.2042411.

[23]Michael Elad, “Optimized Projections for Compressed Sensing”, The Department of Computer Science, The Technion Israel Institute of Technology, Israel, 2006. DOI:r 10.1109/TSP.2007.900760.

[24]Joel A. Tropp,m Michael B. Wakin, Marco F. Duarte, Dror Baron and Richard G. Baraniuk, “Random Filters For Comprssive Sampling and Reconstruction”, Proc. Int. Conf. Acoustics, Speech, Signal Processing, ICASSP, May 2006. DOI: 10.1186/1687-6180-2014-94.

[25]Wang, Z., Bovik, A., Sheikh, H., and Simoncelli, E., “Image quality assessment: from error visibility to structural similarity”, IEEE Trans. on Image Processing, Vol. 13(4), pp.600-612, 2004.

[26]Sheikh, H. and Bovik, A,“Image information and visual quality”, IEEE Transactions on Image Processing, Vol.15(2), pp.430-444, 2006.

[27]Zhou Wang, “A Universal Image Quality Index”, IEEE SIGNAL PROCESSING LETTERS, Vol. 9, pp. 81-84, 2002.