Image deblurring – Wiener filter versus TSVD approach

86 Advances in Electrical and Electronic Engineering IMAGE DEBLURRING – WIENER FILTER VERSUS TSVD APPROACH P. Bojarczak 1) , Z. Łukasik 2) 1) Radom University of Technology, Institute of Automatics and Telematics of Transport ul.Malczewskiego 29, 26-600 Radom tel.:+48 48 361 77 05, mail: [email protected] 2) Radom University of Technology, Institute of Automatics and Telematics of Transport ul.Malczewskiego 29, 26-600 Radom tel.:+48 48 361 77 00, mail: [email protected] Summary This paper presents comparison study of two different deblurring methods: Wiener filter and TSVD decomposition. Wiener filter is a method giving the best results when variance of the noise incorporated in blurring process is known a priori. In TSVD decomposition the knowledge of precise variance of the noise is not necessary to image restoration. The paper also discusses basis blurring forms and their mathematical description. 1. INTRODUCTION Image deblurring plays an important role in an image restoration process. Image capture process causes degradation of original image. There are several factors having contribution to blurring, two of them are the most important [1]: - movement of camera or capturing object when long exposure time is set, being called motion blur - out of focus optic caused by wide angle lens setting or atmospheric turbulence, being called out of focus blur Degraded image is additionally corrupted by the noise. The noise is a consequence of imperfection of image sensor and acquisition part of camera. Degradation process can be described by the following formula [2]: nKfg + = (1) where: g is a vector corresponding to blurred (degraded) image, K is a large usually illconditioned matrix modeling blurring operation, f is vector corresponding to perfect image and n is the noise vector. Degradation process can also be presented in another form [1]:  − − +−−= +∗= 1 1 21221121 21212121 1 2 ),(),(),( ),(),(),(),( N k M k nnnknknfkkk nnnnnfnnknng (2) where: ),( 21 nng is blurred (degraded) image, ),( 21 nnk is kernel or point-spread function (PSF) modeling blurring operation, ),( 21 nnf is perfect image, ),( 21 nnn is the noise, N and M correspond to the number of image pixels in horizontal and vertical axes respectively and asterisk ( ∗ ) stands for convolution. If blur is independent of the position, then it is called spatial invariant blur, otherwise it is called spatial variant blur [2]. We are only concerned with spatial invariant blur. It turns out both motion and out of focus spatial invariant blurs can be modeled with the use of PSF function of special form. In case of motion blur, PSF has following form [1]:     −=≤+ = elsewhere y xL yxif L Lyxk 0 tan, 2 1 ),;,( 22 φ φ (3) where: L means length of motion equal to camera (object) constant velocity times camera exposure interval and φ is the angle (in radius) of the camera (object) movement in horizontal axis. PSF function corresponding to out of focus blur is of the form [1]:     ≤+ = elsewhere Ryxif R Ryxk 0 1 );,( 222 2 π (4) where: R is a radius of the circle of confusion (COC) arising from circular aperture of camera (imperfection of lens). Fig1. presents exemplary results of motion and out of focus blurs. Results are obtained for motion blur of L= 20 and φ = 0 and Fig.1c is obtained for out of focus blur of R =10. Fig1.Ilustration of blurring process a) original image, b) image after motion blurring of L= 20, c) image after out of focus blurring of R=10 The deblurring process consists in an estimation of original image f ( ),( 21 nnf ) on the basis of Image deblurring – Wiener filter versus TSVD approach 87 available blurred image g ( ),( 21 nng ) -, known form of matrix K ( ),( 21 nnk PSF function) and some information about the nature of the noise n ( ),( 21 nnn ). In order to impartially judge the quality of deblurring process, the following quality gauge called Improvement in Signal to Noise Ratio (ISNR) has been proposed in [3]:         − − =             − − = ),( ˆ ),( image difference of variance ),(),( image difference of variance log10 ˆ log10][ 2121 2121 10 2 2 10 nnfnnf nngnnf dBISNR F F ff gf (5) where: 2 F is a Frobenius norm and f ˆ is the reconstructed image from (1) and ),( ˆ 21 nnf is reconstructed image from (2). 2. DEBLURRING OF IMAGE WITH WIENER FILTER If the blurring process is presented in the form (2), then the restored image ),( ˆ 21 nnf can be obtained by convoluting ),( 21 nng with the ),( 21 nnh PSF function of linear filter [1]:  − − −−= ∗= 1 1 221121 212121 1 2 ),(),( ),(),(),( ˆ N k M k knkngkkh nngnnhnnf (6) or in spectral domain: ),(),(),( ˆvuGvuHvuF = (7) where: [ ] ),( ˆ 2),( ˆ 21 nnfDFTvuF = , [ ] ),(2),( 21 nnhDFTvuH = , [ ] ),(2),( 21 nngDFTvuG = and 2 DFT means two dimensional Discrete Fourier Transform. When noise term ),( 21 nnn in (2) is absent, then the relationship in spatial domain between ),( 21 nnk blurring PSF function and ),( 21 nnh PSF function of linear filter is of the form: function delta Dirac a is ),( ),(),(),( ),(),( 21 1 1 21221121 2121 1 2 nn nnknknkkkh nnknnh N k M k δ δ  − − =−− = ∗ (8) and in spectral domain: [ ] ),(2),( ),( 1 ),(1),(),( 21 nnkDFTvuK vuK vuHvuKvuH = == (9) In this case, the blurred image can be perfectly reconstructed by linear filter of ),( 21 nnh PSF function fulfilling the relationship (9). However when noise term in (3) is present, then application of filter of ),( 21 nnh fulfilling the relationship (9) leads to the following reconstruction of degraded image [1]: ( ) [ ] ),(2),( ),( ),( ),( ),(),(),( ),( 1 ),(),(),( ˆ 21 nnnDFTvuN vuK vuN vuF vuNvuFvuK vuK vuGvuHvuF = += += = (10) As it can be seen from (10), two factors can cause poor reconstruction of the image. First resulting from existence of frequencies (u,v), for which ),( vuK approaches to zero, what in turn can lead to the lack of the solution of (10). Second even if the solution happens to exist, for frequencies (u,v), for which ),( vuK has small values, the noise term ),( 21 nnn is amplified significantly - second term in (10). In order to minimize the influence of noise term on the whole reconstruction, the ),( 21 nnh PSF function of filter is calculated such that minimizes the mean-squared error (MSE) between original ),( 21 nnf and reconstructed image ),( ˆ 21 nnf : ( ) 2 1 1 2121 1 2 ),( ˆ ),(  − − −= N n M n nnfnnfMSE (11) Minimization of (11) leads to modified formula for ),( 21 nnh PSF function of filter having following form in spectral domain: [ ] ),(/),(),(),( ),( ),( * * vuSvuSvuKvuK vuK vuH fn + = (12) where: ),( * vuK is a complex conjugate of ),( vuK , and ),( vuS n and ),( vuS f are the power spectrum of the noise and ideal image respectively. If the noise is uncorrelated then its power spectrum is easy available by: ),( allfor ),( 2 vuvuS nn σ = (13) where: 2 n σ is a noise variance. 88 Advances in Electrical and Electronic Engineering Basing on it, it is possible to estimate power spectrum of original image on the basis of power spectrum of blurred image ),( vuS g and the information about the noise variance [1]: 2 ),(),( ngf vuSvuS σ −≈ (14) In Wiener filter approach, information about the noise variance is necessary to good quality restoration. Fig.2a shows original image, and Fig.2b shows distorted image through out of focus blur of L=10 with gaussian noise of variance=1. Fig2c shows the image restored by Wiener filter tuned to variance of 1. Fig2d shows image restored by the same filter with the variance parameter of 5. As it can be seen, Wiener filter tuned to the actual noise variance almost perfectly reconstructs the original image (INSR=1,55dB). However, mismatching filter variance parameter to actual noise variance causes significant degradation of filter’s performance (INSR=-0.13dB). Fig2.Illustration of Wiener filter’ performance The main drawback of Wiener filter is the necessity of a priori knowledge of type and magnitude of noise, which is often unavailable or hardly accessible in practice. 3. DEBLURRING OF IMAGE WITH TSVD DECOMPOSITION If the blurring process is presented in the form of (1) , deblurring process can be treated as the inverse problem what means finding original image through [4], [5]: gKf 1− = (15) As it can be seen from (15), it is typical inverse problem. Inverse problem often suffers from illposedness [4] . Lack of uniqueness, stability and existence of the solution (10) characterize ill-posed problem [5]. Instability can cause large perturbation in solution resulting from small perturbation in input data. It means that small error occurring in blurred image g corresponding to noise term n in (1) has a large influence on the solution. Fig.3b shows the image obtained through direct application of formula (15). The restoration of the image is very poor resulting from above mentioned factors. In order to cope with ill-posed problem, some methods stabilizing the solution is introduced [6]. Truncated Singular Value Decomposition (TSVD) is one of such methods [7]. In Singular Value Decomposition (SVD) any matrix A of dimension mxn can be presented in the following form [7]:  = =Σ= p i T iii T 1 vuUUA σ (16) where: i u being called left singular vector is orthonormal column xm1 of ],,,[ 21 m uuuU Κ= , i v being called right singular vector is orthonormal column xn1 of ],,,[ 21 n vvvV Κ= and Σ is diagonal matrix of dimension mxn with singular values 0 21 ≥≥≥≥ p σσσ Κ arranged on its main diagonal and zero elsewhere, where ),min( mnp = . Fig3.Illustration of ill-posed problem If we assume that K = A, then the solution f ˆ corresponding to the image restoration is of the form [7]: i p ii T i v gu gKf  = − == 1 1 ˆ σ (17) Fig3b confirms poor reconstructing property of formula (17). It results from errors occurring in matrix K and the vector g. Fig.4 presents Picard plot showing variation of singular value i σ and i T i σ /|| gu versus index i for the image from Fig3a. Image deblurring – Wiener filter versus TSVD approach 89 Fig.4 Picard plots a)Variation of singular value i σ - green circles, and b) i T i σ /|| gu -red crosses for the image from Fig3a . As it can be seen form Picard plots, singular values i σ gradually decreases, simultaneously term i T i σ /|| gu corresponding to the noise incorporated in blurring process gradually increases. If we take to reconstruction of image form formula (17) only k <p first singular values rejecting all singular values for which the term i T i σ /|| gu begins to increase, then it is possible to eliminate (reduce) the influence of the noise on the reconstruction process. The number of singular values used in reconstruction is chosen on the basis of Picard plot of fig4b). Chosen value of k is equal to 184. Fig5 presents reconstructed image obtained for 184 first singular values. Fig5. Image reconstruction through TSVD decomposition with 184 first singular values The quality of reconstructed image (INSR = 1.12dB) is comparable with the reconstruction with the use of Wiener filter tuned to actual noise variance (INSR=1.55dB). The main advantage of TSVD approach is the ability to determine the magnitude of noise on the basis of deblurred image. Picard plot is used to estimate the noise level. 4. CONCLUSION Both presented here deblurring methods lend themselves to the image reconstruction. TSVD method has an advantage allowing for the estimation noise level of the image on the basis of Picard plot, what makes it attractive in application where the information about noise is not available a priori. On the other hand when the detailed information about noise level of image is well known, then Wiener filter seems to be a better solution. REFERENCES [1] BOVIK. A.: Handbook of Image and Video Processing, Academic Press, 2002 [2] GONZALES. R, WOODS. R.: Digital Image Processing, Addison Wesley, 1993 [3] HANSEN. P.: Deconvolution and regularization with Toeplitz matrices, Informatics and Mathematical Modeling, Danish Technical University, Numerical Algorithms 29, 2002 [4] GROETSCH. G.: Inverse Problems in the Mathematical Sciences, Vieweg Mathematics For Scientists and Engineers, Vieweg, 1993 [5] BERTERO. M, BOCCACCI. P.: Introduction to Inverse Problems in Imaging, IOP Publishing Ltd London, 1998 [6] HANSEN. P.: Regularization tools: A Matlab package for the analysis and solution of discrete ill-posed problems, Numerical Algorithms vol 6, 1994 [7] KAMM. J, NAGY. J.: Kronecker product and SVD approximation in image restoration, Linear Algebra Applications, 1998