Reconstruction of 3D Sparse images using Non-linear Filtering Compressed Sensing 3D Techniques

Reconstruction of 3D Sparse images using Non-linear Filtering Compressed Sensing 3D Techniques

1Srinivasareddy Putluri

Department of Electronics and Communication Engg., RRS College of Engineering and Technology, Muthangi, Post Graduate student of Electronics and Communication Engineering,

Jawaharlal Nehru Technological University, Hyderabad, India.

AbstractThe objective of this project is to reconstruct 3D sparse images using Non-linear Filtering Compressed Sensing (NFCS) 3D Anisotropic and 3D Isotropic techniques. Compressed Sensing is a new paradigm for signal recovery and sampling. Using proposed NFCS techniques, a random mask is generated for the selected input 3D image using a sampling matrix. Now, a sparse image is generated for the selected 3D image. Applying Normalization, the original image will be reconstructed from the sparse 3D

is an unknown signal which is K-sparse in the transform domain. This is described by orthogonal matrix and = is the coefficients vector of reconstruction in that domain.

The perfect recovery obtained from the number of given measurements depends upon length N and sparsity level K of original signal and on the acquisition matrix [1], [3].

If the unknown signal has sparse gradient, it has been shown in [2], [3] that it can be recovered by casting problem (1) as

||||1, subject to = . (2)

The above formulation is particularly suited to the image recovery problem, since many images can be modelled as piece-wise smooth functions containing a number of jump discontinuities.

Exact measurements are often not possible in real problems, so if the measurements are corrupted with random noise, namely we have

2

||a||1, subject to || + ||2 2

(3)

or

|||| 2 2

image in iterations. The obtained reconstructed 3D image will be filtered using an appropriate adaptive non-linear filter in proposed NFCS 3D

(4)

1, subject to ||

+ ||2

techniques. The output parameters like Normalized Factor, PSNR, and CPU elapsed time will be calculated and compared along with simulation results. The results obtained using proposed techniques will confirm that these possess properties of efficiency, stability, low computational cost, fast recovery of 3D images in few seconds and its performance is competitive with those of state of art algorithms.

Keywords – NFCS, Anisotropic, Isotropic, Compressed Sensing, Normalized Factor

I.INTROCUCTION

Compressed Sensing is a new 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. In transform domain, the signals that that have a sparse representation can be exactly recovered from these measurements by solving an optimization problem of the form

minimize ||1|| subject to = (1) where is an mxn measurement matrix, (m<<n) which possess restricted isometry property [1], [3],

with the original signal can be reconstructed with an error comparable to the noise level by solving the above minimum problem.

The idealized sparse signals are rarely encounter in applications, but real signals are quite often compressible with respect to an orthogonal basis. This means that, if expressed in that basis, their coefficients exhibit exponential decay when sorted by magnitude. The compressible signals are well approximated by K-sparse signals and the compressed sensing paradigm guarantees that from m linear measurements, we can obtain a reconstruction with an error comparable to that of the best possible K-terms approximation within the sparsing basis [2].

In data processing, the traditional practice is to measure data in full length and then compress the resulting measurements before storage or transmission. In such a scheme, recovery of data is generally straightforward. This traditional data- acquisition process can be described as full sensing plus compressing.

Compressive Sensing (CS) represents a paradigm shift in which the number of measurements is reduced during acquisition so that no additional compression is necessary. The price to pay is that more sophisticated recovery

procedures become necessary. In this paper, NFCS 3D Anisotropic and Isotropic techniques for image recovery in a fast and efficient way are described. These NFCS Anisotropic and NFCS Isotropic Adaptive non-linear filtering strategies are discussed in an iterative framework in comparison with 2D image techniques for image recovery.

In the NFCS 3D methods, a sparse image is generated by applying FFT for the input image. From the sparse image, original image will be reconstructed using NFCS strategies by normalization process. NFCS 3D Anisotropic and NFCS Isotropic methods use non-linear filters in an iterative approach to filter the reconstructed image. These methods possess the required properties of efficiency, stability and low computational cost and its performance is competitive than those of existing algorithms.

1. LITERATURE REVIEW

   A crucial point in the practical application of compressed sensing is the numerical solution of

   step on f2, followed by a backward (implicit) step on f1.

   This algorithm makes it possible to derive existence, uniqueness, characterization, and stability results in a unified and standardized fashion for a large class of apparently disparate problems. But, signal must be recovered from a collection of measurements of lower dimensional signals; in phase retrieval, holography, or band- limited extrapolation. Another disadvantage is that it is not efficient for multidimensional signals like 3D signals. [7]

   C.BOUNDCONSTRAINED RECONSTRUCTION

   When dealing with image reconstruction problems it is well known that image intensity values have to be not negative and R, with R>0. From this, we could insert more information in the compressed sensing reconstruction problem by adding a bound constraint to (5) and (6), and considering: find that solves

   2

   problems (1)(4). A large amount of research has been aimed at finding fast algorithms for solving such problems. Previously there are many reconstruction algorithms which are used for recovery of 2 dimensional images. Following are

   or

   F (u), subject to = (5)

   few previous algorithms that will operate on 2 D images for image recovery.

   F (u), subject to || ||2 < 2 (6)

   1. ITERATIVE REWEIGHTED ALGORITHM

      The theory of compressive sensing has shown that sparse signals can be reconstructed exactly from many fewer measurements than traditionally

      Where C is the closed convex set

      C= { 12 : 0 , R, i=1,1, j=1. 2} and linear operator orresponds to a sub-sampled orthogonal transform.

      believed necessary. In [4], it was shown

      empirically that using `p minimization with p < 1

      NFCS 2D ALGORITHMS

      can do so with fewer measurements than with p =

      1. In this algorithm, the local minima of the non- convex problem can be computed. In particular, a regularization strategy is found to greatly improve the ability of a reweighted least-squares algorithm to recover sparse signals, with exact recovery being observed for signals that are much less sparse than required by an unregularized version (such as FOCUSS, [5]). However, Improvements in terms of speed and multidimensional applicability ae also observed for the reweighted-`1 approach of [6]

   B.FORWARD-BACKWARD SPLITTING

   Various inverse problems in signal recovery can be formulated as the generic problem of minimizing the sum of two convex functions with certain regularity properties. The principle of this algorithm is to use at every iteration the functions f1 and f2 separately; more specifically the core of iteration consists of a forward (explicit) gradient

   Here, an extension of non-linear filtering approach to the 2D case is considered. As in [9], we focus on a recovery problem where the optimal solution, in addition to satisfying the acquisition constraints, has minimal bounded variation norm, namely, it minimizes. The optimal reconstruction is evaluated by solving a sequence of total variation regularized unconstrained sub-problems, where both isotropic and anisotropic TV estimates have been considered. For each value of the penalization parameter the unconstrained sub-problems are approached making use of a two-step iterative procedure in fixed number of iterations based upon the forward-backward splitting method [8].

   Interestingly, in compressed sensing 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. The image recovery speed can be increased better

   and these algorithms can only work efficiently for 2 D signals shown in Fig. 1.

   . 2

   Original image Reconstructed image II. 2

   Original image Reconstructed image Fig.1.Test Images – 2 and 2

   Methods

   (a) Horse image (b) Reconstructed image

   In NFCS 2D Anisotropic and Isotropic methods, a random mask and sparse image are generated for the input Horse image. A non-linear filter is used to recover original image from the sparse image. The output parameters like Error, PSNR, No. of iterations and CPU elapsed time are tabulated in Table I.

   The image quality has been evaluated using the PSNR value, defined as

   Method	Error	PSNR	Iterations	CPU Time
   2	1.5648e-004	119.0459	14	11.886620 s
   2	1.8419e-005	49.7175	14	42.789134 s

2. PROPOSED METHODOLOGY

   In this paper, the image reconstruction and non-linear filtering are extended to 3 dimensional images. Compressed Sensing image recovery problem can be overcomed using proposed NFCS 3D Anisotropic and Isotropic methods.

   Using NFCS 3D methods, a sparse image is generated by applying FFT for the input image. From the sparse image, original image will be reconstructed using NFCS strategies by applying normalization process. NFCS 3D Anisotropic and NFCS 3D Isotropic methods use non-linear filters in an iterative approach to filter the reconstructed image. These methods possess the required properties of efficiency, stability and low computational cost and its performance is competitive than those of existing algorithms.

   1. Block Diagram

      Figure 1 shows the block diagram for NFCS 3D Anisotropic and NFCS 3D Isotropic methods. Firstly, an orthogonal transform is applied for the original input image and a random mask is generated using a sampling matrix for the transformed input image. Now, sparse image is generated after applying FFT for the input image. From the sparse image, original image will be reconstructed using NFCS strategies using normalization.

      10

      = 20

      (7)

      MSE=

      12

      (8)

      Figure 2. Block Diagram for NFCS 3D Methods

      where R>0 is the maximum value of the image gray level range and

      Error=|| ||2= 1 . 2 (, , )2 (9)

      . 3 and 3 Methods

      Using these proposed 3 and

      3 methods, non-linear filters are used in

      =1 =1

      TABLE I: Output Parameters with Horse Image

      an iterative approach to filter the reconstructed image. The output parameters like Normalized factor, PSNR ratio and CPU elapsed time will be calculated and compared with the 2D results.

      3 method uses a Median filter to filter the reconstructed image whereas 3 Method uses a digital TV filter for filtering.

      C.Reconstruction Approach

      Let S belongs to R(N1XN2) be a randomly generated binary mask, such that the point-to-point 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

      In the present NFCS 3D methods, there is no limitation, since approach for these problems is done implicitly, thus, avoiding the need to deal with ill-conditioned linear systems.

      The corresponding bound constrained two-step iterative algorithm is the following:

      = + } (14)

      = .

      , = 1

      =

      (10)

      =

      + 1 || ||2

      0, = 0

      +1

      2

      2

      denotes the sampling matrix, which is considered as the random generated mask for the selected input image.

      Let T be an orthogonal transform acting on an image X denoted by

      = . () (11)

      The randomly sub-sampled orthogonal transform considered here is the Fast Fourier Transform.

      Then the input data can be represented as

      = . =

      To find u that belongs to R (N1xN2) can solve

      12

      , . =

      In the case of input data perturbed by additive white Gaussian noise with standard deviation .

      = . + = + (12) The problem can be stated as –

      , || ||2 <2

      (15)

      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 two-step approach, minimizes the penalization function for the given value of LAMBDA.

      The generalized approach of the proposed NFCS 3D methods is applied for 3D images considering three dimensions in every step is as following:

      Step A-0: Initialization

      Given F (.), y, , >0, > 0,0 < < 1,

      ,

      And 0 0 < 0

      Set k=0, 0,0 =0 and 0,0=0

      Step A-0: Start with the outer Iterations=10 While (,0> and || ,0 y||2 > Toll)

      Step B-0: Start with the inner Iterations=4

      12

      2

      i=0;

      2= 2( + 2 2) (13)

      To overcome this problem, penalization approach that considers a sequence of unconstrained

      Step B-1:

      Updating Step: , = , + ,

      Constrained Non-linear filtering step:

      ,+1 {

      2

      minimization sub problems of the form

      = 1 2

      2

      , ,

      +

      12

      +

      1

      2

      || ||2

      Convergence Test:

      ( )

      If (,+1) ( ,)

      ,+1

      i=i+1 and , =,1

      go to step B-1.

      ,

      Otherwise go to Step A-2.

      Step A-2: Outer Iteration Updating K=k+1

      ,0= .,

      ,0 = ,+1

      end while

      Terminate with ,0 as an approximation of

      The automatic stopping criterion of the outer loop depends upon which problem that is considering.

3. RESULTS AND ANALYSIS

   The output parameters like Error, PSNR, No. of iterations and CPU elapsed time from (7), (8) and

   1. are tabulated in Table I.

      . 3

      Original image Reconstructed image II. 3

      Original image Reconstructed image Fig.3.Test Images – 3 and 3

      Methods

      1. Handsome boy image (b) Reconstructed image

   TABLE II: Output Parameters with Handsome boy Image

   Method	Error	PSNR	Iterations	CPU Time
   3	5.5434e-005	128.9371	14	16.996123 s
   3	4.6344e-005	99.6398	14	67.128490 s

   Comparing the results of NFCS 2D and NFCS 3D methods, 3 method provides faster recovery and more PSNR value than all other methods as tabulated in Table III.

   TABLE III. Comparison of Results – NFCS 2D and NFCS 3D Methods

   Method	Error	PSNR	Iterations	CPU Time
   2	1.5648e- 004	119.0459	14	11.88662 s
   2	1.8419e- 005	49.7175	14	42.789134 s
   3	5.5434e- 005	128.9371	14	16.996123 s
   3	4.6344e- 005	99.6398	14	67.128490 s

   Analyzing the above results from both NFCS 2D and NFCS 3D methods, the NFCS 3D methods provide a faster and efficient way of recovery of 3D images. In both NFCS 2D and NFCS 3D methods, Anisotropic methods provide more PSNR values, thereby less noise in comparison with the Isotropic methods.

4. CONCLUSIONS

For the solution of the compressed sensing reconstruction problem we have proposed an efficient iterative algorithm for 3D images, based upon an adaptive nonlinear filtering strategy, and its convergence property has been established. The capabilities, in terms of accuracy, stability, and speed of NFCS-3D, are illustrated by the results considering 3D images and compared the results from NFCS 2D methods for the selected images. Of these proposed NFCS 3D methods, NFCS 3D Anisotropic methods offers faster image recovery and offers more PSNR value in comparison other NFCS 2D and existing methods.

REFERENCES

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

2. 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.

3. E. J. Candés, J. Romberg, and T. Tao, Robust uncertainty principle: Exact signal reconstruction from highly incomplete frequency information,IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489509, Feb. 2006.

4. R. Chartrand, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., vol. 14, pp. 707710, 2007.

5. B. D. Rao and K. Kreutz-Delgado, An affine scaling methodology for best basis selection, IEEE Trans. Signal Process., vol. 47, pp. 187200, 1999.

6. E. J. Cand`es, M. B. Wakin, and S. P. Boyd, Enhancing sparsity by reweighted `1 minimization. Preprint.

7. H. C. Andrews and B. R. Hunt, Digital Image Restoration, Prentice-Hall, Englewood Cliffs, NJ, 1977.

8. P. L. Combettes and V. R.Wajs, Signal recovery by proximal forward backward splitting, SIAM J. Multiscale Model. Sim., vol. 4, no. 4, pp. 11681200, Nov. 2005.

9. T. Goldstein and S. Osher, The split Bregman algorithm for L1 regularized problems, UCLA, Los Angeles, CA, UCLA CAMRep. 0829, 2008.

AUTHOR DETAILS:

SRINIVASAREDDY P,

Post Graduate Student, Department of Electronics and Communication Engg, RRS College of Engineering and Technology, Muthangi, Patancheru, Hyderabad, Andhra Pradesh, India.