Color Image Denoising Using the 4-Band Higher Order Singular Value Decomposition

Color Image Denoising Using the 4-Band Higher Order Singular Value Decomposition

Lekshmy Priya V. S., M. Tech Student, Dept. Of ECE, Marian Engineering College Dr. M. SasiKumar, HOD, Dept. of ECE, Marian Engineering College

Abstract This paper proposes a simple and elegant, patch- based technique for image denoising using the 4-Band higher order singular value decomposition (4-Band HOSVD). The technique decomposes the image into four bands. It groups together similar patches (with similarity defined by a statistically motivated criterion) in each band into a 4D stack, computes the HOSVD coefficients of this stack. Then manipulates these coefficients by hard thresholding, inverts the HOSVD transform and performs hypotheses averaging at each pixel to produce the denoised bands and finally combines it to produce the final filtered image. This technique chooses all required parameters in a principled way, relating them to the noise model. This paper experimentally demonstrate the excellent performance of the proposed technique on colour images producing state of the art results, outperforming other colour image denoising algorithms at moderately high noise levels.

Index Terms: – Image denoising, singular value decomposition (SVD), higher order singular value decomposition (HOSVD), coefficient thresholding, patch similarity.

1. INTRODUCTION

   V

   ISUAL information transmitted in the form of digital images is becoming a major method of communication

   in the modern age, but the image obtained after transmission is often corrupted with noise. The received image needs processing before it can be used in applications. Image noise may also be caused by different intrinsic (i.e., sensor) and extrinsic (i.e., environment) conditions which are often not possible to avoid in practical situations. Therefore, image denoising plays an important role in a wide range of applications such as image restoration, visual tracking, image registration and image classification, where obtaining the original image content is crucial for strong performance. Image denoising involves the manipulation of the image data to produce a visually high quality image. The denoising techniques that have been developed so far are partial differential equations (PDEs), spatially varying convolution and regression, nonlocal techniques, transform based techniques, and techniques based on machine learning.

   PDE-based methods diffuse a noisy image in an anisotropic manner that extracts and respects the edge geometry, allowing diffusion along but not across the image edges [1], [2]. Some PDEs are obtained from the Euler Lagrange equations

   corresponding to functionals that are based on a piecewise constant [3] or piecewise linear [4] model for natural images. A rich class of techniques for image filtering involves the so- called spatially varying convolutions. In these methods, an image is convolved with a pointwise-varying local geometry- driven mask [5]. A closely related idea is the local modeling of an image with a low-order polynomial function whose coefficients are computed by a weighted least squares regression, and these are then used to compute the value of the (filtered) image at a central point.

   Transform-domain denoising approaches typically work at the level of small image patches. In these approaches, the image patch is projected onto an orthonormal basis, such as a wavelet [6] or discrete cosine transform (DCT) [7], to yield a set of coefficients which, for natural images, are known to be sparse and decorrelated [8].To perform denoising, the smaller coefficients are modified (typically by hard thresholding [9]), and the patch is reconstructed by inversion of the transform. This procedure is repeated for every patch. If the patches are chosen to be nonoverlapping, one can observe seam artifacts at the patch boundaries and ringing artifacts around image edges or salient features, which can be attenuated by performing the aforementioned three steps in a sliding window fashion and averaging the multiple hypotheses, yielding superior results [6], [7]. There exist several more sophisticated methods to manipulate wavelet coefficients, such as those that exploit dependencies in transform coefficients at the same spatial location but at different scales (e.g., in [10] or the BLS-GSM (Bayesian Least Squares Gaussian Scale Mixtures) method in [11] or at adjacent spatial locations [12].

   Nonlocal techniques [13], [14] exploit the fact that natural images often contain patches in distant regions that are very similar to each other. NL-Means obtains a denoised image by minimizing a penalty term on the average weighted distance between an image patch and all other patches in the image, where the weights are decreasing functions of the squared difference between the intensity values in the patches. This yields an update rule that can be interpreted as a spatially varying convolution with nonlocally derived masks. NL- Means can also be interpreted as a minimizer of the conditional entropy of a central pixel value given the intensity values in its neighbourhood [15], [16].

   A combination of nonlocal and transform-domain approaches has led to the development of the block matching in three dimensions (BM3D) method [17], which is considered the current state of the art in image denoising. This method operates at the patch level and for each reference patch in the image, it collects a group of similar patches (after a DCT-based prefiltering step), which are then stacked together to form a 3D array. The entire 3D array is projected onto a 3D transform basis (product of DCT/ biorthogonal and Haar bases) to yield a set of coefficients which are hard thresholded. The filtered patches are then reconstructed by inversion of the transform. This process is repeated over the entire image in a sliding window fashion with averaging of hypotheses to yield an intermediate image. This image is then smoothed (heuristically) with a nonlocal empirical Wiener filter to produce a final filtered image. The results using the BM3D method [17] are outstanding. However, the method is complex, with several tunable parameters such as choice of bases, patch-size, transform thresholds, similarity measures, etc.

   and produces the final denoised image. The image quality of the denoised output can be further improved by using a bicubic interpolation method. Since HOSVD is applied on each band separately rather than on the whole image, computation time can be reduced and produces state-of-the-art results.

   1. Selection of similar patches

      Let Pref be the reference patch in each of the four bands of noisy image in RGB space, we can compute its K nearest neighbours from the image, but this requires a choice of K which may not be the same for every image patch. Hence, a distance threshold d [18] is used and select all patches Pi such that

      ||Pref Pi||2 < d (1)

      Assuming a fixed, known noise model – N(0,), if Pref and Pi were different noisy versions of the same underlying patch, the following random variable would have a (n2) distribution:

      The Higher Order Singular Value Decomposition based image denoising [18] achieves close to the state-of-the-art

      2

      =

      =1

      , 2

      2 2

      . The cumulative of a 2(z) random

      performance. It groups together similar patches from the noisy image and create a 3D stack for grayscale images. Then computes the HOSVD coefficients of this stack, manipulates

      variable is given by F(x; z) = ( , , where (x, a) stands for

      2 2

      the incomplete gamma function defined as , =

      these coefficients by hard thresholding and inverts the

      1 x

      et t(a1)dt with a = et t(a1)dt being the

      (a) t=0 0

      HOSVD transform to produce the final filtered image. On color images, this method creates a 4D stack and performs the HOSVD algorithm. The denoised image is filtered using Wiener filter to improve the image quality. But higher computational time is required for implementing this technique.

      This paper proposes a 4-Band HOSVD based denoising technique which produces close to the state-of-the-art performance for color images which is comparatively simple and easy to implement. It also requires very less computation time when compared with the previous HOSVD based method.

2. THE PROPOSED METHOD

   The proposed method in this paper for color image denoising is a simple, patch-based technique using 4-Band higher order singular value decomposition. Assume a zero mean i.i.d (independent and identically distributed) Gaussian distribution of fixed, known standard deviation (i.e. N (0, )) as the noise model. The only free parameter is the patch size.

   This method process the noisy color image in RGB plane itself. The noisy image is first decomposed into four bands for each of the R, G and B planes. Then groups similar patches together into a 4D stack for each reference patch in all the four bands (using (1)) and HOSVD [18] denoising is applied on each band. Finally all the denoised bands are combined The exact equations are of the form

   Gamma function. It is observed that if z 3, for any x 3z then F(x; z) 0.99. Therefore, for a patch-size of n × n and under the given , we choose d = 3*32n2

   1. Implementation of 4-Band HOSVD for denoising

      The HOSVD is a generalization of the matrix SVD to higher order matrices [18][19]. Some pioneering and successful applications of the HOSVD in computer vision have been proposed in [20]. In this paper, we demonstrate the aptness of the 4-Band HOSVD as a transform basis for efficient and effective patch-based denoising.

      Given a p × p reference patch Pref in each of the four bands of noisy image In, create a 4D stack of K-1 similar patches for each reference patch. Here, similarity is defined as in (1), and hence K varies from pixel to pixel. Let us denote the stack as Z ××× ; where D is the total number of image planes ( D = 3). The HOSVD of this 4D stack given as follows [18]:

      Z = S ×1 U(1) ×2 U(2) ×3 U(3) ×4 U(4) (2)

      where U(1) × , U(2) × , U(3) × , U(4) × are orthonormal matrices, and S is a 4D coefficient array of size p ×p× K×D. Here, the symbol ×n stands for the nth mode tensor product defined in [19]. The orthonormal matrices U(1), U(2), U(3) , U(4) are, in practice, computed from the SVD of the unfolding Z(1) , Z(2) ,Z(3) and Z(4) , respectively [19].

      The patches from Z are then projected onto the HOSVD

      = ().

      . (+1,3) (+2,3) ; where

      transform. The parameter for thresholding the transform

      1 k 4 (which are equivalent representations for the HOSVD). For computational speed, we impose the constraint that K 30.

      coefficients are picked to be 2 log 2 , again as per the rule from [21]. The stack Z is then reconstructed after inverting the transform, thereby filtering all the individual patches. The procedure is repeated over all pixels in sliding

      window fashion with averaging of hypotheses. Then, the four denoised bands are combined to obtain the final filtered image. The denoised image quality can be further improved by using a bicubic interpolation step.

3. RESULTS

   In this section, MATLAB simulation results of the proposed method for denoising images having size 256×256 which is corrupted by N(0,20) noise are presented (Fig 1).

   1. (b)

   (c) (d)

   (e) (f)

   Fig 1. Noisy images and the corresponding denoised outputs of the images from Kodak gallery.

   The computation time (in seconds) for obtaining the denoised images using the proposed method and the previous method is tabulated in Table I for 10 RGB images from the Kodak gallery. The input images taken are corrupted by noise N(0,20).

   COMPUTATION TIME (IN SECONDS) FOR OBTAINING THE DENOISED IMAGES USING EXISTING METHOD AND PROPOSED METHOD FOR IMAGES CORRUPTED BY NOISE N(0,20).

   Image #	HOSVD	4-Band HOSVD
   1	1050.35586	298.2576
   2	1212.99998	351.1936
   3	1147.58710	317.4678
   4	1134.06057	321.1190
   5	974.15904	255.8190
   6	1282.15392	324.5241
   7	980.25967	295.8563
   8	923.932537	258.704329
   9	1100.34231	302.9413
   10	1190.7452	316.4176

   From the table, it has been found that existing HOSVD denoising technique requires high computational time. The proposed method produces the denoised output with high computational speed compared to the existing method as HOSVD is applied here on each band separately.

   TABLE II

   PSNR AND SSIM VALUES OF THE DENOISED IMAGES OBTAINED BY EXISTING METHOD AND PROPOSED METHOD FOR IMAGES CORRUPTED BY NOISE

   Image #	HOSVD	4-Band HOSVD
   1	27.341, 0.771	27.3567, 0.7676
   2	30.827, 0.796	30.4594, 0.7771
   3	32.337, 0.878	30.8521, 0.8323
   4	31.068, 0.809	29.6454, 0.7848
   5	27.557, 0.834	25.1526, 0.7615
   6	28.378, 0.798	28.2994, 0.7402
   7	31.726, 0.911	27.9167, 0.8282
   8	28.028, 0.864	26.3160, 0.8457
   9	32.447, 0.883	30.3466, 0.8520
   10	32.005, 0.862	29.5832, 0.8121

   N(0,30)

   TABLE I.

   The PSNR (Peak Signal to Noise Ratio) and SSIM value (Structured Similarity Index matrix ) of the denoised images obtained by using proposed 4-Band HOSVD method and previous HOSVD method is tabulated in the Table II . The 10 RGB images are taken from the Kodak gallery and are corrupted by noise N(0,30) . The proposed method produces denoised images having psnr and ssim values close to the

   existing denoising techniques such as HOSVD and BM3D with lesser computation time.

4. CONCLUSION

In this paper, an extremely simple algorithm for color image denoising is proposed. The proposed method of denoising image using 4-Band HOSVD has high

computational speed compared to the existing methods of denoising. It also achieves close to the state-of-the-art performance. As the parameters chosen for denoising are all tied to the noise model, this method can be elegantly and easily extended to handle some other non- Gaussian noise models. Extending this method to handle such varied noise models is one important avenue for future research.

REFERENCES

1. P. Perona and J. Malik, Scale-Space and Edge Detection Using Anisotropic Diffusion, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 7, pp. 629-639, July 1990.

2. J. Weickert, Anisotropic Diffusion in Image Processing. Teubner, 1998.

4. Y. You and M. Kaveh, Fourth Order Partial Differential Equations for Noise Removal, IEEE Trans. Image Processing, vol. 9, no. 10, pp. 1723-1730, Oct. 2000.

5. D. Tschumperle´ and R. Deriche, Vector-Valued Image Regularization with PDEs: A Common Framework for Different Applications, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no. 4, pp. 506-517, Apr. 2005.

6. R. Coifman and D. Donoho, Translation-Invariant Denoising, technical report, Yale Univ., 1995

7. L. Yaroslavsky, K. Egiazarian, and J. Astola, Transform Domain Image Restoration Methods: Review, Comparison and Interpretation, Proc. SPIE Series, Nonlinear Processing and Pattern Analysis, pp. 1- 15, 2001.

8. A. Hyvarinen, P. Hoyer, and E. Oja, Image Denoising by Sparse Code Shrinkage, Intelligent Signal Processing, pp. 1-6, IEEE Press, 1999.

9. S. Lansel, DenoiseLab, http://www.stanford.edu/~ slansel/ DenoiseLab/documentation.htm, 2006.

10. L. Sendur and I. Selesnick, Bivariate Shrinkage Functions for Wavelet-Based Denoising Exploiting Interscale Dependency, IEEE Trans. Signal Processing, vol. 50, no. 11, pp. 2744-2756, Nov. 2002

11. J. Portilla, V. Strela, M. Wainwright, and E. Simoncelli, ImageDenoising Using Scale Mixtures of Gaussians in the Wavelet Domain, IEEE Trans. Image Processing, vol. 12, no. 11, pp. 1338- 1351, Nov. 2003.

12. E. Simoncelli, Bayesian Denoising of Visual Images in the Wavelet Domain, Bayesian Inference in Wavelet Based Models, vol. 141, pp. 291-308, Springer-Verlag, 1999.

13. A. Buades, B. Coll, and J.-M. Morel, A Review of Image Denoising Algorithms, with a New One, Multiscale Modelling and Simulation, vol. 4, no. 2, pp. 490-530, 2005.

14. D. Zhang and Z. Wang, Image Information Restoration Based on Long-Range Correlation, IEEE Trans. Circuits and Systems in Video Technology, vol. 12, no. 5, pp. 331-341, May 2002.

15. S. Awate and R. Whitaker, Unsupervised, Information-Theoretic, Adaptive Image Filtering for Image Restoration, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 28, no. 3, pp. 364-376, Mar. 2006.

16. K. Popat and R. Picard, Cluster-Based Probability Model and Its Application to Image and Texture Processing, IEEE Trans. Image Processing, vol. 6, no. 2, pp. 268-284, Feb. 1997.

17. K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, Image Denoising by Sparse 3D Transform-Domain Collaborative Filtering, IEEE Trans. Image Processing, vol. 16, no. 8, pp. 2080-2095, Aug. 2007.

18. Ajit Rajwade, Anand Rangarajan and Aruna va Banerjee,Image Denoising using Higher order Singular value Decomposition, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 35, no.4, Apr 2013.

19. L. de Lathauwer, Signal Processing Based on Multilinear Algebra, PhD dissertation, Katholieke Universiteit Leuven, Belgium, 1997.

20. M. Vasilescu and D. Terzopoulos, Multilinear Analysis of Image Ensembles: Tensorfaces, Proc. Intl Conf. Pattern Recognition, pp. 511-514, 2002.

21. D. Donoho and I. Johnstone, Ideal Spatial Adaptation by Wavelet Shrinkage, Biometrika, vol. 81, pp. 425-455, 1993