Image Restoration Algorithm Research on Local Motion-blur

Published Online June 2011 in MECS

In the process of image formation, many reasons will cause the degradation of the image. The degradation system maybe linear, additive, space constant, or nonlinear, not added, and space variable. In the image system, there exist many degenerated sources. Some degeneration factor only affects the gradation of certain individual spot in an image; and other degradation factors can make a space region become blurred. The former is called point of degradation, the latter is known as spatial degradation [1].

Motion-blur is one of the typical degradation models. During the working process of a camera, relative motion between the target and the camera will cause motion-blur of the image. So, restoration algorithm of motion-blurred images has become the research focus in the image processing field. Many reasons can cause motion blur, which can be divided into the following two categories: one is compression blur, which is caused by the displacement of the camera during the working process that will cause the blur of the whole image; the other is local motion blur, which is caused by the movement of some objects in the aim photographic field. The latter case will be studied in this paper.

There are many methods used to eliminate the blur, including methods with hardware or software. For hardware methods, Nayar constructed a hybrid camera which can measure its own motion during the image integration [2]. In the exposure time, the blur parameter was determined by automatically testing the camera’s moving speed. And then inverse filter was used to restore the original image. But to estimate the motion-blur parameter, a hybrid camera was needed, and the cost was high. Another method was optimization of prism [3]. An inertial sensor was used to compensate the movement of the camera. This method was usually used to solve the blur caused by the shake of the camera and its effect was well when the camera’s exposure time was short. Liu designed a special CMOS sensor [4]. The sensor was used to judge if movement was exist. When movement was tested, integration of the image was stopped. So, the motion blur was inhibited. But the design process of the method was complex, and it was not suitable for the continuously moving of the aim. Therefore, software methods are widely used to eliminate the image blur.

With software methods, when we proceed to restore the image, we can do it in frequency domain, and also can do it in spatial domain [5]. Restoration methods may be divided into two kinds: unconstrained restoration and constrained restoration. Unconstrained restoration is a method that the process of image restoring is not restricted by other constraint conditions. This method seems to be very easy to get the desired results, but it is not, especially when the noises are taken into account [6]. Therefore, in order to process the image easier in mathematics, constraint conditions are often added in the restoration process, and with these conditions a criterion function is minimized. Such method is called constrained restoration. Wiener filter and constrained least squares filtering are two typical method of constrained restoration [7].

Wiener filter can be attributed to the deconvolution (or reverse filter) algorithm. It was first proposed by Wiener. The frequency domain expression of the estimated values of the image obtained from Wiener is:

H * (U, V)| H (u, v )|2 + k

G ( u , v )

Where: H* (u, v) is the duplicate conjugate of the degradation function H(u,v) , and k is the empirical value, its value depending on certain image and the noise situation.

Lim thought that error in Wiener filter mainly come from edge error [8]. By increasing the filter parameter k, the edge errors can be reduced, but the resolution of restored image can be reduced. When k > 0.01, the image has obvious ghosting effect.

Wiener filter has been applied to one dimensional signal firstly, and achieved very good results. Then it was introduced into two-dimensional signal processing, and also achieved satisfactory results, especially in the field of image restoration. Because Wiener filter has good restoration effect, lower computation, better antinoise performance, it has been widely applied in the field of image restoration. And Wiener filter has been improved continuously. Many efficient restoration algorithms are based on Wiener filter. Wiener filter is the best restoration for a family of images in statistical mean sense. It has the ability of automatically inhibiting the noise amplification, and the noise is stronger, the effect is more obvious. It avoids the excessive amplification of noise appearing in the inverse filter.

Constrained least squares filtering can be expressed by:

H * (u, v)2             2 G(u, v)

| H (u, v )| + s|P (u, v )|

To choose the suitable value of s, iteration can be used. But the formula must satisfy the following constraint condition:

g - Hf

By default, the constraint is smoothness constraint. Only the mean and variance of the noise are necessary, and they can be easily achieved by the degradation image. A comparison is made between the constrained least square filter and Wiener filter. The results show that with high or middle noise, constrained least square filter has some vantage, and with low noise, the two methods have almost the same representation. To get favorable reversion effect, PSF and noise function must be provided.

In addition, the maximum entropy restored method [910] , the Lucy-Richardson nonlinear filtering [11-12], the blind recovery method [13] all have respective characteristic, and in some cases, they all have well application.

As the blur image restoration processing is related to multiple fields, it has become an important research topic. And the problem of local motion-blur and its restoration in complex background is always a difficulty in the domain of restoration of blurred image. In this paper, the basic principle of local blur is researched. And then a blurred image restoration algorithm that based on physical method is presented. Experimental results show that the algorithm is fast and effectual.

• II.   principle of local motion-blur

• A.    Horizontal uniform-velocity blur

Horizontal uniform-velocity blur is the simplest. According to the horizontal uniform-velocity blur, we can investigate the basic method of motion-blur. The blur in motion image is the trailing smear cased by the mutual covering of the pixels during the motion. So, physical blur principle can be used to simulate the image blur. The only difference between the real blur model and the physical model is that the points of real model are continuous. But the points in the digital image are discrete, so during the blur simulating of image with slope the simulation image will appear sawtooth and the blur effect has some discrepancy with the real model. And this is the common fault of digital image.

Final                                             |п“'а| position                                          position

Г Black moving

The background part si

, of the disturbance ,

The distance s of objects moved in time t

• Figure 1 Simplified model of motion blur

Figure 1 is the simplified model of motion-blur. It indicates the generation of motion-blur. In the figure, the black object move from right to left, L represents its length, s represents the motion distance, and t represents the exposure time. The time that every point in s 1 length in the white background is covered by the black object is t=L*t ／ s. So they have the same chromaticity. The time that objects in initial position and final position which have the same length are covering by the black object is less than t. Moreover, the distance to the edge is shorter, the time is less, and the color is close to white.

Figure 2 is the original clear image. It is the joint of two images. Figure 3 is the blurred image after added a certain parameter in the function (for example, the step length of horizontal blur is 30).

Figure 2 Clear original picture

Figure 3. Blurred picture

• B.    Mathematical model of blurred images

Generally speaking, reasons cause blurred images lie in the following aspects: (1) In the process of image acquisition, the camera is moved, or the exposure time is too long; (2) The scene is outside of the focus, a wide-angle lens is used, the atmosphere causes interference or short-time exposure causes the reduction of photons coming into the camera; (3) Astigmatism anamorphosis appears in the confocal microscopy.

An improved or retrogressive image can be approximated by the equation:

g = Hf + n . (1)

Where: g is the image, H is a deformation operator, it’s also known as point spread function (PSF), f is the original real image, n is the additional noise, it is produced during the acquisition process of image and it will change the image.

In the above mathematical model, PSF is an important factor; its value will directly affect the quality of the restored images. So it’s a key component in image restoration. Generally, the mapping relation between object and image in an image-forming system can be integrated by the following formula: [1]

g(x,y) = H { f(x,y) } (2)

Where: g(x, y) is the output retrogressive image; f(x, y) is the input image; H{} is the imaging system operator.

In order to describe the imaging system conveniently, the imaging system is often looked as a linear system. Actually, there always is nonlinearity existing in the imaging system. If the nonlinear distortion would not cause excessive error, or it could satisfy linear feature locally, the imaging system usually would be described approximately by linear system, even if the imaging system is completely nonlinear. So, in actual discussion, some linear assumptions are done on nonlinear system:

• (1)    operator H{} is linear, that is to say it satisfies the linear feature:

H{af₁(x,y) + bf₂(x,y)} = aH{f₁(x,y)} + bH{f₂(x,y)} (3)

• (2)    operator H{} is shift-invariant, if the relation between input and output satisfies (1), then for any f(x, y) and α , β , there has:

g(x α ,y β ) = H{ f(x α ,y β )}     (4)

The equation (4) shows that for any point on the image, the computing results are only associated with the gray value of the points, and have nothing to do with the position of the point.

A continuous image f (x, y) can be expressed by the two-dimensional convolution of the two-dimensional sample function δ (x, y) :

f (x, y) = ∫∫ f ( α , β ) δ (x α , y β )d α d β   (5)

Put operation H{} on f (x, y) : g ( x , y ) = H { f ( x , y )} =⁺ ∫ ∫ f ( α , β ) H ( δ ( x - α , y - β )) d α d β -∞

Let be h(x,α;y,β)=H[δ(x-α,y-β)], So: +∞

g ( x , y ) = ∫ ∫ f ( α , β ) h ( x , α ; y , β ) d α d β      (7)

-∞

In the function, h(x,α;y,β) is the point spread function(PSF) or system impulse response. It indicates that every pixel of the discrete image is diffused by the operation H{} . And f (x, y) can be regarded as the result of continuous sampling of discrete point. The degradation of the image is influenced by h (x,α;y,β). In most cases, the system is constant, in the image, it is presented as constant displacement, so h(x,α;y,β) can be expressed by h(x-α,y-β).

g ( x , y ) = ∫∫ f ( α , β ) h ( x , α ; y , β ) d α d β

-∞

= ⁺ ∫ ^∞ ∫ f ( α , β ) h ( x - α ; y - β ) d α d β -∞

= f ( x , y )* h ( x , y )                     (8)

With the existence of additional noise, the image retrogressive model can be expressed as:

g(x, y) = f(x,y) h(x, y) + n(x, y) (9)

Where: n(x,y) refers to noise. This is a linear shift invariant system model. Shift-invariant often refers to space invariance in the field of image neighborhood. Retrogression in image can be represented approximately by shift invariant model.

• C.    Local motion-blur algorithm of image

For the local motion-blur is created by the moving of some objects in the whole image, it is relatively complex. In order to simulate the formation of the local motion-blur, the following realized method is adopted in this paper: image A is the image which has complex background; image B is used to simulate the local blur part in image A. Image B is blurred, and then it is pasted onto the image A.

The background image is a submarine image (Fig.4).The image need to be blurred is a starfish image

Figure 4. The background picture

Figure 5. Clear image of small starfish

We can establish the blur computing model:

A =	" 11 a 21 • • •	a 12     • a 22     •	■   a 1 . ■ a 2 n •	, representing	the
	_ a m 1	a m 2 •	■ amn _
background image.

B= " bii b21 • • • b12 b22 ..  b/ b2j • , representing the blurred . bi bi2 ■ bj. image.

Assumptions: (1) The blurred step length k=3(pixels); (2) Starting with the left edge of image B pasting onto the left edge of image A; (3) The last target image is C. C is the matrix:

	" c ii	c 12	-   c 1 n "
C =	c 21 •	c 22	■   c 2 n •
	_ c m 1	c m 2	mn J

The process of the blur operation is as follows: c 12 = (2/3)*a 12 + (1/3)*b 11           (10)

During the process of blurring, the point c ₁₂ is interfered both by the background and the blurred image noise. 2/3 of the interference comes from the background, and 1/3 comes from the blurred image. The blurring processes of the other points on this column are the same as the point c ₁₂ .

c 13 = (1/3)*a 13 + (1/3)b 11 + (1/3)b 12 (11)

For the point c 13 , 1/3 of the interference comes from the background, 1/3 comes from the point b 11 , and 1/3 comes from the point b 12 .

c 14 = (1/3)*b 11 + (1/3)b 12 + (1/3)b 13 (12)

The values of c ₁₂ , c ₁₃ ， ,c ₁₄ are known, and the matrix A and B are unknown. In a natural image, there is a strong correlation between one pixel and its adjacent pixel, and the correlation will sharply decline if there is certain distance between the pixels. So we can replace a₁₂ by a₁₁ , and according to (10), point b₁₁ can be calculated. Point a₁₃ can be calculated according to (11), then a₁₃ can be replaced by a₁₁ , the correlation between a₁₃ and a₁₁ will decline to some extent. It can be seen that with the increasing of the blurred step length and the dimension of the matrix, the result of calculation will get worse.

Based on the above discussion, a blur algorithm is designed.

In the algorithm, the blurred step length k=60(pixels), the blurred image will be placed in the center of the background.

Because the black edge of the small starfish in the original image is not completely black and some points are not completely black, the noise must be filtered, so we can get satisfactory results. A noise-remove parameter is set in the algorithm, through which we can get a better picture.

First, the two images are superimposed by the above-mentioned method. By varying the step-length k, we can get different blur result. But there appears a problem: A large black area appears, as shown in the below image:

Figure 6 Superimposed image after blurred

The main reason is that the black background is added into the image during the process of pasting. To improve the situation, the image pasting method must be improved. In consideration of the appearance of the noisy point, the noise reduction factor is set as 9. The pasting effect is obviously improved. The effect image is as follows (Fig.7):

Figure 7 Superimposed image after denoising

After improvement of the pasting method, a better blur image can be achieved through the method proposed above. The effect image is as follows (Fig.8):

Figure 8. Picture after local motion-blur process

• III.   RESTORATION ALGORITHM OF LOCAL MOTION -BLUR

The difference of restoration model between blurred stretching image and compression blurred image lies in that the columns of the compression blurred image become less after blurred. That is to say the quantity of data of the image becomes less, the data is compressed, and it is difficult to restore the image to the original status. For the blurred stretching image, after blurred processing, simply considering the blurred little image, it becomes larger. Its quantity of data also becomes larger. Because the background color of the blurred stretching image is also exposed during the blurred process, the quantity of data of the blurred image is interfered by the background color. Compare with the compression blurred image, the blurred stretching image has a new interference source.

As known from above, with the increasing of the blurred step length and the dimension of the matrix, the result of calculation will get worse. For such a blurred image, as the background color is unknown, it is difficult to restore the image.

To restore the local motion-blurred part of an image is a very complex process. In order to restore the image better, the main ideas are as follows: First, the blurred part is extracted from the complex background and pasted on the bottom of monochromatic background. Then a restorative process is done on the blurred image in the monochrome background which is easy to restore. Finally, the restored part is pasted back to the original complex background.

The restoration algorithm includes following ones:

• (1)    Extracting the edge of the blurred image from the original one;

• (2)    Pasting the blur image onto a black bottom;

• (3)    Removing the background color interference in the blurred image;

• (4)    Restoring the blurred image in the black bottom using the physical principle of image blur;

• (5)    Pasting the restored image back onto the original background;

• (6)    Restoring the background color interference to the original background.

In a monochrome background, the background can be thought as inexistent, and so the blurred image is easier to be restored. The background matrix is a zero matrix in this case.

	Г Я П	a 12	a 13	a 14	a 15	a 16	a 17	a 18	a 19
A =	a 21	a 22	a 23	a 24	a 25	a 26	a 27	a 28	a 29
	. a 31	a 32	a 33	a 34	a 35	a 36	a 37	a 38	a 39

, A represents the clear background image.

Г bn b12 b13 B = b 21 b22 b23 _ Ьз1 b32 b33 b14   b15

b 24   b 25

b 34   b 35

, B represents

the blur image.

Assumptions:

• (1)    The blurred step length k = 4(pixels);

Г ь»1

• (2)    Pasting the edge column

  b 21 of the blurred

  
  

b 31

a12

image B to the edge column a22

of A as the start;

a32

(3) The last target picture is C:

c11 c12 c13 c14 c15 c16 c17 c18 c19 C = c 21 c22 c23 c24 c25 c26 c27 c28 c 29 _ c 31 c32 c33 c34 c35 c36 c37 c38 c39 _ The desired matrix B can be calculated through this cycle several times. The following picture is the restored image on the black bottom.

Figure 9. Restored image of the small starfish

It can be seen from fig.9 that the effect of restoration is good. A local motion-blurred image often has a complex background, so the method proposed in this paper is simple, effective and fast.

In the above inversion recovery process of blurred stretching image ， the following four parameters are preconfigured:

• 1.    The moving direction of blurred image.

• 2.    The moving step length of blurred image.

• 3.    The position the blurred image inserting into the background.

• 4.    Removing the background color value participated in exposure of the blurred image.

These four points are omitted in order to simplify the blurred processing steps. Each one can be a research direction in the field of blur image processing, and they all have certain difficulty.

Finally, through the contrast enhancement ， Figure 10 can be obtained.

Figure 10. Small starfish after contrast enhancement

It can be seen from the restoration results that the restored image of the small starfish has some difference with the original image, and the processing algorithm is based on the four predetermined parameters. If the information about the image is unknown, the four key information get from procedure of analysis will has greater deviation. With these biased information, the restored results of blurred image will become even worse.

• IV. Conclusion

For most of the blurred image process, the main idea is to use various kinds of filters to restore the image in frequent domain. Most of the process options are based on signal process implementation. In this paper we researched the base of construction of basic model of local motion-blur, and the formation mechanism of local motion-blur is analyzed, and then proposed a new restoration algorithm aimed at local motion-blur in a complex background. The blur and restoration algorithm proposed in this paper are based on the physical process of the image; the main operations are matrix operations and cycles, and the method can be implemented in space domain. The experimental results show that the algorithm is fast and effective.