·Table of Contents
·Computer Processing and Simulation
A Fast non-Iterative Algorithm for the Removal of Blur Caused by Uniform Linear motion in X-Ray ImagesDomingo Mery, Dieter Filbert
Institute for Measurement Technology and Control EngineeringTechnical University of Berlin
Einsteinufer 19, Sekr. E2
D-10587 Berlin, Germany
Tel.: ++49 +30 314 73431, ++49 +30 314 22541
Fax: ++49 +30 314 25717
e-mail: email@example.com, firstname.lastname@example.org
WWW home page: http://ima.ee.tu-berlin.de
Image reconstruction is concerned with recovering detail in severely blurred s, when the causes of the imperfections are known a priori . This knowledge may come as analytic models, or other a priori information coupled with the knowledge (or assumption) of some physical system that provided the imaging process in the first place . The purpose of restoration is then to estimate the best source , given the blurred and some a priori knowledge.
In this paper we concentrate on the particular case of blur caused by uniform linear motion, which may be introduced by relative motion between detector and object. Early work on restoring an degraded by blurring calculated the deblurring function as an inverse filtering. The inverse filtering evaluation of the blurring function H (or point spread function PSF) in the frequency domain tends to be very sensitive to noise . The cause of this sensitivity is the lowpass nature of the PSF: its frequency response H(w ) contains very small values, and small noise in the frequency regions where 1/ H(w ) is very large, may be greatly emphasized. Iterative procedures to evaluate the inverse filtering are described in  and , but the computational load is notably high and the restored for the linear motion blur case is not satisfactory.
Sondhi, in  or , proposed a non-iterative algorithm to find a solution to the uniform-blurring case, but the computational load is extremely high in small motions. Other two non-iterative approaches are presented in . The first one, the matrix left division, calculates the restored signal as a signal that has the fewest possible nonzero components. This solution differs strongly from the original signal because the original signal must not have necessarily many zero components. The second one, the Moore-Penrose pseudoinverse of a matrix, finds a restored signal whose norm is smaller than any other solution. This solution is very good, but the estimation is based on Singular-Value Decomposition, whose computation load is very high.
In this paper, we address the above problems and reduce the computational times significantly using a new technique that minimize the norm between blurred and original . The paper is organized as follows: in Section 2, the problem of the restoration of a degraded that has been blurred by uniform linear motion is formulated. In Section 3, we present the solution of this problem. In Section 4, the proposed method is tested on numerically blurred s. Finally, in Section 5 we present our conclusions and suggestions for future research.
A blurred X-ray g( x, y ) that has been degraded by a motion in the vertical direction x( ¯ ) and the horizontal direction y (®) can be modeled by
where f , T , xt(t) and yt(t) represent, respectively, the deterministic original X-ray , the duration of the exposure and the time-varying component of motion in the x and y directions . In this case the total exposure is obtained by integrating the instantaneous exposure over the time interval during which the shutter is open. By rotation of the camera or by using a transformation that rotates the blurred , a new system of coordinates is chosen in which xt(t) is zero. Considering that the original f( x,y ) undergoes uniform linear motion in the horizontal direction y only, at a rate given by yt(t) = ct/T, let us write (1), with u = y -ct/T , as
or as a digital that has been discretized in spatial coordinate by taking N samples Dy = Y / N units apart
Fig. 1 shows a row f = [f1 ... fM]T of an original and its corresponding row g=[g1 ... gN]T of the blurred for n = 3 pixels. Equation (3) describes an underdetermined system of N simultaneous equations (one for each element of vector g) and M = N + n - 1 unknowns (one for each element of vector f ) with M > N :
The elements of the N ´ M matrix H are hi for i =1,...,n.
Fig 1: (a) Original row. (b) Blurred row with pixels.
Fig 2: Spectrum of a blurred which was degraded by uniform linear motion with . (a) 2D-Fourier Transformation. (b) Mean of the rows of (a). The size of the degraded is 300´256.
If the PSF is not exactly known, but if we know that it corresponds to a uniform linear motion, the parameter n can be estimated from the spectrum of the blurred . An example is shown in Fig. 2. The 2D-Fourier Transformation of a blurred test is represented in Fig. 2a, in this case it took place a horizontal degradation with n = 16 . The mean of its rows is illustrated in Fig. 2b. We observe that the period of this function corresponds to the length of the blurring process in pixels.
The problem of restoring an X-ray that has been blurred by uniform linear motion consists of solving the underdetermined system (4). The objective is to estimate an original row per row ( f ), given each row of a blurred ( g ) and a priori knowledge of the degradation phenomenon ( H ). Since there is an infinite number of exact solutions for f in the sense that H . f - g = 0 , an additional criterion that finds a sharp restored is required.
|| Fig 3: Restoration of a row of a blurred . (a) Original row. (b) Degraded row with n=2 pixels. (c), (d), (e) and (f) Four possible solutions for f that satisfy equation H.f - g=0. |
We observed that most solutions for f strongly oscillate. Fig. 3 shows an example in which four different solutions for f are estimated, all solutions satisfy equation (4): H . f = g . Although these solutions are mathematically right, they do not correspond to the original signal. By the assumption that the components of the higher frequencies of f are not so significant in the wanted solution, these oscillations can be reduced by minimization of the distance between fk and gk, i.e. we take a vector as a sharp solution of H . f = g so, that this presents the smallest distance between original signal and blurred signal: we seek then to minimize the objective function
The application of this criterion does not mean that is equal to g, because this solution does not satisfy the system of equations (4) and the orders of and g are different. The solution also is defined as the vector in the solution space of the underdetermined system H . f = g whose first N components has the minimum distance to the measured data, i.e. , where are the first N elements of f. We can express vector as =P.f, with P a N ´ M matrix which projects the vector f on the support of g :
|Fig 4: MATLAB program for the removal of blur in G caused from horizontal degraded function h.|
The original optimization problem is now:
subject to the constraint . Applying the technique of Lagrange multipliers , , this problem can be alternatively formulated as an optimization problem without constraints:
if l is large enough. The solution of this problem is easy computing the partial derivative of criterion V respect to the unknown f:
This solution for the example of Fig. 3b is almost identical to the original sharp input signal of Fig. 3a. Fig. 4 summarizes the algorithm in MATLAB.
We have tested the proposed algorithm, on several s, the results of some of which are presented in this section. In these numerical experiments the size of the original s is 256 x 256 pixels with 256 gray scales. We define the matrix F as the deterministic original X-ray , its picture elements are Fij for i = 1,...,L and for j = 1,...,N with L = N = 256 ; the matrix G as the simulated blurred can be calculated as follows:
with M = N - n + 1 , where n is the linear motion blur in pixels. Equation (10) can be written in matrix form as where the elements of matrix H are defined in Equation (4), with hi = 1 / n. In our MATLAB program of Fig. 4 is h = ones(1,n)/n and the (simulated) blurred can be obtained from G = conv2(F,h,'valid') or
G = F*H'.
Using the proposed method, the restored is calculated (matrix Fr in MATLAB program of Fig. 4). Results of this method are shown in Fig. 5. In the degraded the details of the aluminum castings are not visible, while in the restored these details are recovered.
Fig 5: Restoration in simulated degraded X-ray images.
The improvement in signal-to-noise-ratio (ISNR), used in , is applied to these experiments as an objective measure of performance:
Fig. 6a shows the corresponding ISNR values for a restored test as a function of n for the proposed algorithm in comparison with the method of Sondhi,  or , and the Moore-Penrose pseudoinverse . There is a small difference for n > 40 pixels, which does not have any meaning for the human eye. The cause of this difference is the exclusion from the last n -1 terms fk for k = N + 1,...,M in the objective function (5). The required computational time for the same example of Fig. 6a is given in Fig. 6b. The methods were executed on a workstation SUN-SPARC 2. We observe that the computational load for the method of Sondhi is extremely high by small motions. Furthermore, the computational burned by the Moore-Penrose pseudoinverse is between 8 and 2 times greater than the required computational time of our method.
Fig 6: Improvement in signal-to-noise-ratio and computational time vs. length of the blurring process in pixels for the proposed algorithm in comparison with Sondhi and Pseudoinverse methods.
In this paper, we introduced a new method to restore an X-ray that has been blurred by uniform linear motion. The length of this blurring process n can be estimated from the degraded using its frequency spectrum. The model proposed includes an underdetermined system of linear equations, which has an infinite number of exact solutions. An additional criterion that considers the smoothness characteristic of both the degraded and restored s is used to solve the equations. The approach minimizes the norm of the difference of the original and the output blurred s.
The quality of the restoration is as satisfactory as the classical methods, nevertheless the computation load is decreased considerably by small motions (n<16 pixels). Realistically speaking, however, larger motions do not occur frequently in radiography.
This method can also be used to restore s that have been degraded by other kind of smooth blur functions, if we know its corresponding PSF. Obviously the algorithm is not restricted to restoration of X-ray s.
The authors are grateful to the German Academic Exchange Service, DAAD, and YXLON International GmbH, Hamburg, for their support. We thank also the anonymous reviewers of IEEE Transaction on Processing for interesting improvements of this method.
|© AIPnD , created by NDT.net|||Home| |Top||