 Open Access
 Total Downloads : 1075
 Authors : Joshna Bikki, B.Doss
 Paper ID : IJERTV1IS4195
 Volume & Issue : Volume 01, Issue 04 (June 2012)
 Published (First Online): 01072012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Sparse Image Reconstruction Using Nonlinear Filtering for Compressed Sensing
Joshna Bikki
Department of ECE, JNTU College of Engineering, Anantapur, Andhra Pradesh, India
B.Doss
Faculty, Department of ECE, JNTU College of Engineering, Anantapur, Andhra Pradesh, India
Abstract
Compressed sensing is a new paradigm for signal recovery and sampling. It states that a relatively small number of linear measurements of a sparse signal can contain most of its salient information and that the signal can be exactly reconstructed from these highly incomplete observations. The major challenge in practical applications of compressed sensing consists in providing efficient, stable and fast recovery algorithms which, in a few seconds, evaluate a good approximation of a compressible image from highly incomplete and noisy samples. In this paper, we propose to approach the compressed sensing image recovery problem using adaptive nonlinear filtering strategies in an iterative framework, and we prove the convergence of the resulting twosteps iterative scheme. The results of several numerical experiments confirm that the corresponding algorithm possesses the required properties of efficiency, stability and low computational cost and that its performance is competitive with those of the state of the art algorithms.

Introduction
In most image reconstruction problems, the images are not directly observable. Instead, one observes a transformed version of the image, possibly corrupted by noise. In the general case, the estimation of the image can be regarded as a simultaneous deconvolution and denoising problem. Intuitively, a better reconstruction can be obtained by incorporating knowledge of the image into the reconstruction algorithm. Compressed sensing, also known as compressive sensing. Compressed sensing is the process of acquiring and reconstructing a signal that is supposed to be sparse or compressible. It states that a relatively small number of linear measurements
of a sparse signal can contain most of its salient information. It follows that signals that have a sparse representation in a transform domain can be exactly recovered from these measurements by solving an optimization problem. However, the number of salient features hidden in massive data is usually much smaller than their sizes. Hence data are compressible. In data processing, the traditional practice is to measure (sense) data in full length and then compress the resulting measurements before storage or transmission.
Section II reviews the existing algorithms we consider. In section III we propose a method in order to analyze the reconstruction approach. Section IV presents the estimation of quality based on some numerical experiments. Section V presents simulation results and discussions. Concluding remarks are presented in section VI.

Related Work
A large amount of research has been aimed at finding fast algorithms for solving numerical solution of problems. In fact, although are convex optimization problems that can be solved using several standard methods such as interior points methods, when the problems are large, as in the case of real images, their practical use is limited by the extensive computation required to generate a solution. Recently, efficient computational methods for problems of the form have been developed.
1.1. Existing Algorithms:
They include iterated shrinkage methods, Bregman iterative algorithms, gradient projection algorithms[2], fixed point continuation algorithms iterative reweighted algorithms and the
specialized interior point method proposed in for solving the equivalent quadratic problem with linear inequality constraints. In an algorithmic framework for problems of the form and is also proposed, that represents a generalization of the iterate shrinkage methods. Other kinds of approaches to solving problems are the iterative greedy algorithms which include OMP, ROMP and COSAMP, and the combinatorial algorithms.
While detailed studies and many comparisons between the performance and efficiency of the previously mentioned algorithms are given in the literature for the reconstruction of sparse 1 Dsignals[1], it is not completely clear how they work for large 2D and 3D problems, especially from the computational speed point of view. From the results of, and it seems that the run time necessary to reconstruct 256×256 and 512×512 images ranges from one hour to a few minutes. These values are still too high to allow for their widespread use in several 3D practical applications, as, for example, medical
TV estimates have been considered. For each value of the penalization parameter the unconstrained sub problems are approached making use of a twostep iterative procedure based upon the forwardbackward splitting method .Interestingly, in compressed sensing context, where the acquisition matrix is obtained as randomly chosen rows of an orthogonal transform, the two steps of the iterative procedure become an enforcing of the current iterate to be consistent with the given measurements, and a total variation filtering step.

Reconstruction approach
We set here our notation and state the results in the following. Let S belongs to R(N1XN2) be a randomly generated binary mask, such that the pointtopoint product with any v belongs to R(N1XN2) , denoted by S x v , represents a random selection of the elements of v, namely, we have
imaging.
The only algorithm that, up to the
vs S v
with
vij ,if sij 1
s
ij
v
0, if sij 0
present, seems to be really effective for large scale problems is the splitBregman algorithm [2] . In that paper, it is shown that, by minimizing energies involving the reconstruction total variation, and using
Let T be an orthogonal transform acting on an image x, We denote by
a split formulation combined with Bregman iteration, it is possible to obtain sufficiently accurate reconstructions of 256 x256 sparse gradient images in
TS x
S (Tx )
a few tens of iterations. Recently, a new nonlinear filtering strategy has been proposed in the context of a penalized approach to the compressed sensing signal
The randomly sub sampled orthogonal transform of the input data can be represented as
recovery problem. A suitable filter is used according to the considered minimization problem and a fast flexible algorithm has been realized for its solution.
y S (Tx )
TS x
The empirical results presented in show that this nonlinear filtering approach succeeds in the perfect recovery of sparse and sparse gradient 1Dsignals [1]
We want to find u belongs to R (N1xN2) that solves
from highly incomplete data, and that the computing time is competitive with the most efficient state of the art algorithms.
min
u RN1 N2
F(u),
subjectto
TSu y
In this thesis, considered an extension of this nonlinear filtering approach to the multi dimensional case. We focus on a recovery
In the case of input data perturbed by additive white Gaussian noise with standard deviation
problem where the optimal solution, in addition to satisfying the acquisition constraints, has minimal bounded variation norm, namely, it minimizes. The
y S (Tx
e) T e
s
s
x
optimal reconstruction is evaluated by solving a sequence of total variation regularized unconstrained sub problems, where both isotropic and anisotropic
The problem can be cast as
min
u RN1 N2
F(u),
subject to
Tsu 2
vn un
T T ( y
TS un )
where 2
2 (M
y
2 2
2 2M )
S
u arg min
F(u)
1 u v 2
n 1
To overcome this problem we use the
u c 2 n 2
well known penalization approach that considers a sequence of unconstrained minimization sub problems of the form
The general scheme of the bound constrained algorithm is the following:
StepA0: Initialization.
min
u RN1 N2
F(u)
1 2
y
2
Tsu 2
k
Given F(.),y,Ts,>0,>0,0<r<1,Toll0, min and 0 such that 0< min 0.
Set k=0,u0,0=0 and 0,0= 0.
S
The convergence of the penalization method to the solution of the original constrained problem has been established (under very mild conditions). Unfortunately, in general, using very small penalization parameter values makes the unconstrained sub problems very illconditioned and difficult to solve. In the present context, we do not have this limitation, since we will approach these problems implicitly, thus, avoiding the need to deal
Step A1: Start with the inner iterations While (k,0> min and Tsuk,0y2>Toll) Step B0: Start with the outer iterations i=0;
Step B1:
Updating step:
with illconditioned linear systems. This is obtained by evaluating an approximation of the solution of
vk ,i
uk ,i
T T ( y
TS u
k ,i )
iteratively, using an operator splitting strategy (frequently considered in the literature to solve L1
Constrained Nonlinear filtering Step:
2
1 2
regularized problems), and taking advantage of the particular structure of the resulting problems.
uk ,i 1
arg min u c
F (u)
2 k ,i
u vk ,i
Fig 1: Test images (a) phantom (b) head image of size (256×256)
The corresponding bound constrained twostep iterative algorithm is the following. The proposed penalized splitting approach corresponds to an algorithm whose structure is characterized by two level iteration. There is an outer loop, which progressively diminishes the penalization parameter in order to obtain the convergence to the global minimum, and an inner loop, which iteratively, using the twostep approach, minimizes the penalization function for the given value of LAMBDA
Convergence Test:
If F(uk,i+1)F(uk,i)/ F(uk,i+1) k,i i=i+1
k,i= k,i1 go to step B1 Otherwise go to step A2.
Step A2: Outer iteration Updating
K=k+1
k,0=r. ki,i uk,0=uk1,i+1 endwhile
Terminate with uk,0 as an approximation of x

Numerical Experiment
In this, we demonstrate the effectiveness of the proposed image reconstruction algorithm by reporting several numerical experiments that highlight its reconstruction capabilities, stability
and speed. In all the experiments, we have used simulated data. This choice is motivated by the need to give an objective quantitative evaluation of the effectiveness of the proposed algorithm by using reconstructed image quality. In fact, the only visual inspection of the reconstructed images, as given in and, is not really enough to compare the performance of different reconstruction algorithms. The image quality has been evaluated using the PSNR value, defined as
generated mask
generated mask
PSNR 20 log R
Fig2: Acquisition Mask 1 & Mask 2
Where
10 RMSE
RMSE Error
N1 N2
of a sparse gradient image, and compressible image widely used for comparisons between different methods, the Head image. All the experiments are performed using sub sampled frequency acquisitions,
Where R>0 is the maximum value image gray level range and
but, in order to demonstrate the capabilities of our nonlinear filtering method, we have tested it using two different acquisition strategies corresponding to the
2
N N masks given in Fig.2 .
x
2
Error u
1 2
(ui, j
xi, j )

Experimental Results
i 1 j 1
The PSNR values that we give in the different experiments refer to the first, minimum energy reconstruction .As already mentioned, we have considered only the sparse gradient case and in all our experiments we have used both the anisotropic and isotropic discrete approximations of the total variation. Since we have experimentally seen that it is not important to find a very accurate solution of the variation problem, for all the experiments we have fixed to four the number of iterations of the isotropic estimate yielded by the digital total variation filter. This choice represents a good compromise between accuracy and efficiency. A higher iteration number increases the computing time without a real improvement in the reconstruction. The anisotropic estimate is obtained using just one iteration of the recursive new median filter. Since both the considered algorithms deal only with unconstrained minimization
We remark that, while the two methods substantially perform very well in all the experiments, we have noted some differences in their behavior that justify the use of both estimate. The images used in our experimentation, shown in Fig. 1, are the Shepp Logan Phantom, the typical test image of the computed tomography literature and an example
Simulations are performed using Matlab software which possesses excellent graphics and matrix handling capabilities. Matlab has a separate toolbox for image processing applications, which provided simpler solutions for many of the problems encountered in this research. The results shown in table 1 & 2 are obtained by running a matlab implementation of the bound constrained version of NFCS2D on a PC with an Intel pentium4 HT3.4Ghz processor and 3GB of RAM under Windows XP.
PHANTOM image Reconstruction:
original image generated mask
sparse image reconstructed image
filtered image(NFCSI) filtered image(NFCSA)
Table 2: Comparisons of PSNR, CPU Time, and Error rate for HEAD IMAGE WITH Mask2
Method
PSNR
Error Rate
CPU Time in sec
NFCS2D
62.035
39662.2
11,44sec
NFCS2DI
57.42
22479.2
24.007sec
NFCS2DA
129.395
12.67
5.66sec
HEAD IMAGE Reconstruction:
original image generated mask

Conclusion
For the solution of the compressed
sparse image reconstructed image
sensing reconstruction problem we have proposed an efficient iterative algorithm, based upon a penalized splitting approach and an adaptive nonlinear Filtering strategy, and its convergence property has been established. The capabilities, in terms of accuracy, stability, and speed of NFCS2D, are illustrated by the results of several numerical experiments and comparisons with a state of the art algorithm. We remark that, even if we have analyzed the sparse gradient case with under sampled frequency acquisitions, our approach is completely general, and works for different kinds of measurements and different choices of the function. Also for future work, it is also possible for reconstruction of 3D i.e. color images.
filtered image(NFCSI)
filtered image(NFCSA)
REFERENCES
Table 1: Comparisons of PSNR, CPU Time, and Error rate for SHEPPLOGAN WITH Mask1

L. Montefusco, D. Lazzaro, and S. Papi, Nonlinear filtering for sparse signal recovery from incomplete measurements, IEEE Trans. Signal Process. vol. 57, no. 7, pp. 24942502, Jul. 2009.

W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for minimization with applications to compressed sensing, SIAM J. Imag. Sci., vol. 1, pp. 143 168, 2008
Method
PSNR
Error Rate
CPU Time in sec 1
[NFCS2D
63.7432
32708.24
12.59 a
NFCS2DI
59.0103
18729.18
9.869 1
NFCS2DA
137.3919
2.2564
7.925 [
t

T. F. Chan, S. Osher, and J. Shen, The digital TV filter and nonlinear denoising, IEEE Trans. Image Process., vol. 0, no. 2, pp. 231241,Feb. 2001.
4] N. C. Gallagher, Jr and G. W.Wise, A theoretical nalysis of the properties of median filters, IEEE Trans. Acoust. Speech, Signal Process.,vol. ASSP29, no. 6, pp. 1361141,Dec.1981.
5] J. Darbon and M. Sigelle, A fast and exact algorithm for otal variation minimization, in PROC. 2nd Iberian Conf. Pattern Recognit. Image Anal., 2005, vol. 3522, pp. 351
359.

L. I. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, vol. 60, pp.259268,1992.

S. Kim, K. Koh, M. Lustig, and S. Boyd, An efficient method for compressed sensing, in Proc. IEEE Int. Conf. Image Process., 2007,vol. 3, pp. 117120.

J. BioucasDias and M. Figueiredo, A new TwIST: Two step iterative shrinkagethresholding algAortihms for image restoration, IEEE Trans.Image Process., vol. 16, no. 12, pp. 29923004,Dec.2007.

J. Cai, S. Osher, and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comput., to be published.

E. J. CandÃ©s, Compressive sampling, in Proc. Int. Congr. Math.,Madrid, Spain, 2006, vol. 3, pp. 14331452.

E. J. CandÃ©s, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math.,vol. 59, no. 8, pp. 12071223, 2006.