IBN AL- HAITHAM J. FOR PURE & APPL. SCI. VOL.24 (1) 2011 Technique For Image De-blurring Using Adaptive Wavelet Lagrange Fuzzy Filter A. F. Sabeeh Department of Computer Science , College of Education Ibn Al-Hatham, University of Baghdad Receivein in Feb. 10 , 2011 Accepted in March 23 , 2011 Abstract A new de-blurring technique was proposed in order to reduced or remove the blur in the images. The proposed filter was designed from the Lagrange interpolation calculation with adjusted by fuzzy rules and supported by wavelet decomposing technique. The proposed Wavelet Lagrange Fuzzy filter gives good results for fully and partially blurring region in images. Keyword: image de-blur, Lagrange application, Fuzzy filter, wavelet-Fuzzy, Lagrange – fuzzy, Image processing. Introduction The de-blurring method developed relies on the facts that natural images have sparse leading edges, and edges of the blurred image are lesser sparse than that of the de-blurred images as the edges of the blurred images occupy a larger area due to blurring. So, a prior which tend to make the edges sparser will tend to make the images sharper also.[1] The assumption that edges are sparser in natural sharp images may be an oversimplification of the problem but the results obtained on this analysis are promising. The prior should be adjusted and the cost function should be altered such that initial iteration which estimate the lower frequency components of the image are regularized with bigger weight whereas later iterations which corresponds to higher frequency components should be regularized with smaller weights. This adjustment ensures noise suppression at the same time allows for better sparseness.[2] Blur is unsharp image area caused by camera or subjectmovement, inaccurate focusing, or the use of an aperturethat gives shallow depth of field. The Blur effects are filtersthat smooth transitions and decrease contrast by averagingthe pixels next to hard edges of defined lines and areaswhere there are significant color transition.[2] Blurring Types [3] In digital image there are 3 common types of Blur effects: - Average Blur The Average blur is one of several tools you can use to remove noise and specks in an image. Use it when noise is present over the entire image.This type of blurring can be distribution in horizontal andvertical direction and can be circular averaging by radius R which is evaluated by the formula: IBN AL- HAITHAM J. FOR PURE & APPL. SCI. VOL.24 (1) 2011 R =√ g2 + f2 …(1) Where: g is the horizontal size blurring direction and f is vertical blurring size direction and R is the radius size of thecircular average blurring. - Gaussian Blur The Gaussian Blur effect is a filter that blends a specificnumber of pixels incrementally, following a bell-shapedcurve. The blurring is dense in the center and feathers at the edge. Apply Gaussian Blur to an image when you want more control over the Blur effect. - Motion Blur The Motion Blur effect is a filter that makes the image appears to be moving by adding a blur in a specific direction.The motion can be controlled by angle or direction (0 to 360 degrees or –90 to +90) and/or by distance or intensity in pixels (0 to 999), based on the software used. Image De-blurring Image de-blurring is an inverse problem whose aim is to recover an image from a version of that image which has suffered a linear degradation, with or without noise. This blurring degradation can be shift-variant or shift-invariant. The algorithm focuses on linear, shift invariant degradation. Automatic de-blurring has immense applications such as remote sensing, astronomy, bio-medical image processing etc. [2] The blind de-blurring refers to de-blurring the image in which the blurring kernel is not known. If the blinding kernel is known, it is referred to as non-blind de-blurring. The filter kernel which has caused blurring to the image is considered as the point spread function (PSF). The blind de-blurring is an ill-posed and ill-conditioned problem with infinite possible solutions for de-blurred image and the PSF estimation.[2] Causes of Blurring[3] A. Deblurring Model A blurred or degraded image can be approximately described by this equation: g = PSF*f + N, …(2) Where: g the blurred image, h the distortion operator called Point Spread Function (PSF), f the original true image and F Additive noise, introduced during image acquisition that corrupts the image. Point Spread Function (PSF) is the degree to which anoptical system blurs (spreads) a point of light. The PSF is the inverse Fourier transforms of Optical Transfer Function(OTF). In the frequency domain, the OTF describes the response of a linear, position-invariant system to animpulse.OTF is the Fourier transfer of the point (PSF). B. Deblurring Techniques This paper applyies four methods deblurring image:  Wiener Filter Deblurring Technique Wiener filter is a method of restoring image in the presence of blur and noise. The frequency- domain expression for the Wiener filter is: W(s) = H(s)/F+ (s), H(s) = Fx,s (s) e as /F - x(s) …(3) Where: F(s) is blurred image, F +(s) causal, F-x(s) anti-causal  Regularized Filter Deblurring Technique Regulated filter is the deblurring method to deblur an image by using de-convolution function de-converge which is effective when the limited information is known about additive noise  Lucy-Richardson Algorithm Technique The Richardson–Lucy algorithm, also known as Richardson–Lucy de-converge, is an iterative procedurefor recovering a latent image that has been the blurred by aknown PSF. IBN AL- HAITHAM J. FOR PURE & APPL. SCI. VOL.24 (1) 2011 …(4) Where Is PSF (Pij)at location i and j,uj is the pixel value at location j inblurred image. Ci is the observed value at pixel location i.Iteration process to calculate uj given the observed ci and known p ij …(5) Where …(6)  Blind De-convolution Algorithm Technique Definition of the blind deblurring method can be expressedby: g(x, y) =PSF * f(x,y) + η(x,y) …(7) Where: g (x, y) is the observed image, PSF is Point Spread Function, f (x,y) is the constructed image and η (x,y) is the additive noise term . Wavelet Transform and Image Processing[4] Wavelets decomposition: Wavelets are families of functions generated from one single prototype function (mother wavelet)  by dilation and translation operations:  is constructed from the so-called scaling function . The wavelet transform represents the de-composition of a function into a family of wavelet functions m,n(t) where m is the scale/dilation index and n the time/spaceindex). In other words, using the wavelet transform, any arbitraryfunction can be written as a superposition of wavelets. Many constructions of wavelets have been introduced in mathematical and signal processing literature (in the context of quarter mirror filters). In the mid eighties, the introduction of multi resolution analysis and the fast wavelet transform by Mallat and Meyer provided the connection between the two approaches. The wavelet transform may be seen as a filter bank and illustrated as follows, on a one dimensional signal x[n]: •x[n] is high-pass and low-pass filtered, producing twosignals d[n] (detail) and c[n] (coarse approximation). •d[n] and c[n] may be subsampled (decimated by 2: 2) otherwise the transform is called translation invariant wavelet transform •the process is iterated on the low-pass signal c[n]. This process is illustrated in figure 1. Much information can extract at several scales (sub bands) plus an approximation of the signal (the last c[n]) In the case of images, the filtering operations are both per-formed on rows and columns, leading to the decomposition. Lagrange Interpolation Polynomial In this proposed system, the denoising technique was designed to achieve the best human visualization for the repainting image after filling the noise holes in these images after removing the noise. The method was proposed to filling the noise holes is Lagrange interpolation polynomial calculations adaptation by fuzzy rules. IBN AL- HAITHAM J. FOR PURE & APPL. SCI. VOL.24 (1) 2011 The formula of this method was first published by Waring (1779), rediscovered by Euler in 1783, and published by Lagrange in 1795 (Jeffreys and Jeffreys 1988). Lagrange interpolating polynomials are implemented in Mathematical as Interpolating Polynomial. They are used, for example, in the construction of Newton-Cotes formulas. When constructing interpolating polynomials, there is a tradeoff between having a better fit and having a smooth well-behaved fitting function. The more data points that are used in the interpolation, the higher the degree of the resulting polynomial, and therefore the greater oscillation it will exhibit between the data points. Therefore, a high-degree interpolation may be a poor predictor of the function between points, although the accuracy at the data points will be "perfect."[5] Given a set of k + 1 data points [6]: …(8) where no two xj are the same, the interpolation polynomial in the Lagrange form is a linear combination …(9) of Lagrange basis polynomials …(10) Note how, assuming no two xi are the same (and they can't be, or the data set doesn't make sense), , so this expression is always well-defined Example 1: I wish to interpolate ƒ(x) = x2 over the range 1 ≤ x ≤ 3, given these three points:[6] The interpolating polynomial is: IBN AL- HAITHAM J. FOR PURE & APPL. SCI. VOL.24 (1) 2011 The Proposed Adaptive Lagrange Fuzzy Filter The proposed Wavelet Lagrange Fuzzy filter is design based on the Lagrange interpolation polynomial calculation for estimating the lost values from the other values, and fuzzy rules (as the mean fuzzy filter design in [7]). The formulation of the proposed technique is as follows:- a. Limitation Let X = { x = (x1, x2) | 1 ≤ x1 ≤ H, 1 ≤ x2 ≤ W} be the pixel coordinates of an input image and let Y = { y = (y1, y2) | 1 ≤ y1 ≤ H, 1 ≤ y2 ≤ W} be the pixel coordinates of the corresponding filtered output image where, H and W denote the height and width respectively. At each location x ε X, a filter window is defined whose size is N = 2n+1 where, n is a non-negative integer. b. Lagrange Interpolation Processing Let w(x,y) denote a sample vector of all the pixels in a filter window including the central pixel w(x,y) i.e.- w(x,y) = [w1(x1,y1), w2(x2,y2),……..wN(xN,yN)] T ………. (11) where, w1(x1,y1) is the upper left value in the window, wN(xN,yN) is the lower right value and the pixels are scanned from left to right and top to bottom as w1(x1,y1), w2(x2,y2),….wN(xN,yN) for each raw of window. When applied the equation of the Lagrange polynomial interpolation (eqn.9) gives an estimated center window pixel. A new set of pixels values are generated due the Lagrange interpolation calculation from each filter window applied to whole image. c. Modifying the estimation window pixel by fuzzy switching For the current pixel define difference D as follows:- D(x) = min{w(x,y)-T , l(x,y) } … (12) where, i = 1,2,..or N and T is the threshold represents the mean value of the whole image pixels. The l(x,y) is the pixel value calculate from Lagrange polynomial interpolation and w(x,y) is original pixel. If μ[D(x)] ε [0, 1] is the membership function of D(x) that indicates how much the pixel x looks like a blur, then the following fuzzy rules will give :- [Rule 1] If D(x) is large, then μ[D(x)] is large. …(13) [Rule 2] If D(x) is small, then μ[D(x)] is small. …(14) With these rules we have used the S-function in MATLAB to describe the membership function of the impulse noise corruption extent of the current pixel. ……(15) Where, a and c are predefined thresholds such that if D(x) is less than a ,the pixel is considered as blur free and if D(x) is greater than b the pixel is considered as definitely blur.Here b = (a + c) / 2. The filter based on the above fuzzy rules generates the following output value:- y = ( 1 - μ[D(x)] ) * x + μ[D(x)] * D(x) ….(16) If μ[D(x)] = 0 then, y = x i.e. no deblur filtering is required and the pixel remains unaltered. If μ[D(x)] = 1 then, y = M where D(x) represent the output of the Lagrange calculation output filer, i.e. the pixel is definitely blurring and it is replaced by the estimated pixelfrom the neighboring values(D(x)). If 0 <μ[D(x)] < 1 then, the pixel is somewhat low blurring and the filter will output the weighted average of the input pixel and the Lagrange estimated value. IBN AL- HAITHAM J. FOR PURE & APPL. SCI. VOL.24 (1) 2011 The Proposed Image Deblurring System Restoration or deblurring average blur from images is a very difficult problem to resolve. In this research, we describe a strategy that can be used for solving such problems. This strategy is used to design a proposed filter to deblur image (explained in section 5). The proposed filter was design using the principles and theory of the Lagrange polynomial interpolation to estimate the pixels values replaced in the center window of the filter. The effects of the neighborhoods window pixels on the center pixel will calculate by Lagrange calculations. The replacing operation will control by adaptation technique like Fuzzy technique. The fuzzy rules were used to adjust the replacing operation or adjust the pixels value to get the adaptive sharping operation. The fuzzy rules were used to determine the pixel status (blur, less blur, no blur) and choice of the operation for each case. This filter will be applied to the image resulted from the wavelet transform (decomposed images) in order to replace the wavelet deblurring threshold with this adaption Wavelet Lagrange fuzzy calculation.In this proposed system, the wavelet transform used is the Daubechies 4D basis wavelet functions is applied on the loaded image. After decomposing operation completed, the mean value of each subbands image regions will calculate to use as threshold (T in eqn.12). The RMSE (Root Main Square Error) was achieved to show the deblurring (sharping) operation effect on the images. The main proposed system steps are as follows: - Applying Wavelet Transform on the loaded image using Daubechies 4D basis function. Then, a window of 7x7 coefficients blocks for each sub bands was used. - Applying adaptive Wavelet Lagrange-Fuzzy filter on the decomposed image. - Recomposed the deblurred image subbands. - Calculate RMS Figure 2 shows the block diagram of the proposed system block: In this proposed system, the Daubechies 4D basis filter was used to decompose loaded image into 2 level using the Daubechies 4D scaling and wavelet functions are as shown in equations (17,18) [9]. Figure (3) shows some results of the 2-level decomposed image. …..(17) …..(18) RMSE Calculation while the RMSE can calculate from : …..(19) Where , I represent the blurred and deblurred images, respectively. IBN AL- HAITHAM J. FOR PURE & APPL. SCI. VOL.24 (1) 2011 Experimental Results & Discussions Many samples were used to test the proposed system with a different blurred regions ratio (but only six samples were taken to show the proposed system works and results due to similarity in results). Some samples like S1, S3 and S5 have full blur image with a different blur ratio, while other S2, S4, and S6 have partial blurred image region with a different blur ratio. The proposed filter (adaptive wavelet Lagrange Fuzzy filter) gives good results in removing the fully/partially blurring from images with a best RMSE values. Fig(4) shows three test samples with results from applied proposed system. The RMSE of the different samples deblurring by Wavelet Lagrange Fuzzy filter is compared in Table 1. Conclusions The deblur-spatial relation can be used to constrain interpolation and extrapolation in the deblur domain. The method of polynomial interpolation gives a polynomial in the deblur domain which can be used for deblurring images with sloped regions. In this research, a Lagrange interpolation calculation was used with a wavelet transform and fuzzy technique to deblurring images with a full blurring or partial blurring. From the proposed system results, the size of the image stills the same size without effects. The changes are only in the pixels values by replacing the blurred pixels depend on the fuzzy operation decisions by the results of the Lagrange calculations to make the details and edges appearance more clear. Also, fuzzy rules have more effect in the partial blurred image with good RMSE values. References 1. Andr´eJalobeanu, Laure Blanc-F´eraud, and JosianeZerubia, February (2003), Satellite image deblurring using complex wavelet packets", International Journal Of Computer Vision 51( 3): 205-217, DOI: 10.1023/A:1021801918603,. 2. AdarshNagaraja, Blind and Semi-Blind De-blurring of Natural Images, www.cs.ucf.edu/~adarsh/blindDeconv_v2.pdf 3. Al-amri1, S. S.and Kalyankar, N.V. (2010), A Comparative Study for Deblured Average Blurred Images", (IJCSE) International Journal on Computer Science and Engineering, 02(03): 731-733. 4.Mathieu Lamard, and Guy Cazuguel et al, (2005), Content Based Image Retrieval based on Wavelet Transform coefficients distribution, Conference proceedings : Annual International Conference of the IEEE Engineering, 5. http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html 6. http://en.wikipedia.org/wiki/Lagrange_polynomial 7. RoliBansal, PritiSehgal, and PunamBedi, (2007), A Simplified Fuzzy Filter for Impulse Noise Removal using Thresholding", Proceedings of the World Congress on Engineering and Computer Science WCECS, October 24-26, , San Francisco, USA 8. Aleksandra Pizurica, Vladimir Zlokolica and Wilfried Philips,( 2004), CombinedWavelet Domain and Temporal Video Denoising, 9. http://www.bearcave.com/misl/misl_tech/wavelets/daubechies/index.html. IBN AL- HAITHAM J. FOR PURE & APPL. SCI. VOL.24 (1) 2011 Table( 1): The RMSE Results Sample name RMSE Size S1 30.32 640x480 S2 32.34 600x800 S3 31.20 600x800 S4 36.09 512x 512 S5 32.01 512x512 S6 35.10 600x800 Fig. (1): Two-channel filter bank involving sub sampling Fig.(2): The proposed system block diagram Fig.(3): Examples of the Daubechies 4D basis filter( 2 – level). Save image Loadin g image Applying the adaptivewavelet Lagrange Fuzzy filter Apply ing Wavelet Transform Average va lue ca lculations for resulted sub-band Apply ing Inverse Wavelet Transform Calculate RMSE IBN AL- HAITHAM J. FOR PURE & APPL. SCI. VOL.24 (1) 2011 S1 before S1 after S2 before S2 after S3 before S3 after Fig.(4): Some results of the proposed wavelet Lagrange Fuzzy filter