A binary search algorithm for impulsive noise removal in compressed sensing reconstruction

Abstract

Impulsive noise in compressed measurement signal (y) leads to the reconstruction of the sparse signal whose energy distribution is different than the original signal. In Approximated Measurement Preprocessing (AMP), the highest elements in y are successively removed until the energy distribution conforms to the one of images. This thesis proposes two greedy algorithms, namely Greedy Boundary Finder (GBF) and Greedy Steep Slope Finder (GSSF), with an aim to reduce the computational cost of AMP. Images are assumed to be sparse in octave discrete wavelet domain. The ratio of energy outside L3 subband and the total energy is used to detect the impulsive noise. Information in an image is highly redundant; therefore, some largest elements can be removed without causing severe degradation to the reconstruction result. Binary search is used to estimate the number of the noisy element to within +g of the actual number, where g is the predefined constant. The number of the reconstruction is a fixed number, when g is set as the unit of the percent to the length of y. GBF and GSSF uses the energy ratio and the change of energy ratio as the cost function for binary search, respectively. GBF and GSSF were compared with AMP, the reconstruction with Huber penalty function (HUBER) and Lorentzian Iterative Hard Thresholding (LIHT). The experiment on 100 1616 image blocks and 20 256256 images revealed that GBF and GSSF provided the comparable PSNR and visual quality to AMP, and required less computational time when the noise probability was higher than 0.05. Furthermore, GBF, GSSF and AMP were better than HUBER and LIHT. GBF provided higher PSNR with lower computational cost than GSSF. However, GSSF was more robust when the noise magnitude was smaller than the largest element in y. GBF and GSSF were not efficient in case that (1) an image could not be sparsified by wavelet shrinkage thresholding or (2) the noise magnitude was smaller than the largest element in y. The integration of the energy ratio to HUBER is being investigated for the rejection of small noise.