Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cs.msu.su/pub/2014.ICSP.Krylov_Nasonov.Warping1D.en.pdf Дата изменения: Wed Aug 13 15:42:43 2014 Дата индексирования: Sat Apr 9 23:29:13 2016 Кодировка:

GRID WARPING FOR IMAGE SHARPENING USING ONE-DIMENSIONAL APPROACH Andrey Krylov, Alexandra Nasonova and Andrey Nasonov Laboratory of Mathematical Methods of Image Processing Faculty of Computational Mathematics and Cybernetics Lomonosov Moscow State University Email: kryl@cs.msu.ru
ABSTRACT A new method for image sharpening via image warping is proposed. The idea of the method is to warp the uniform grid of the image in a way that the pixels around the blurred edge move closer to the edge according to its blurriness. The advantage of the proposed method is that instead of an accurate estimation of the blur kernel only approximate value of the edge blur level is required. Also, since image warping does not change pixel values and only moves pixels, the developed method does not increase the noise level. The proposed technique preserves the overall luminosity and textures of the image, while making the edges sharper and less noisy. Index Terms-- Image warping, sharpening, deblurring, edge width 1. INTRODUCTION Image sharpening is generally viewed as the problem of image deconvolution [1]. In this case the blurred image is usually modeled as a convolution of the original image with some blur kernel [2], [3]. This problem is ill-posed, and even the slightest error in the estimation of the blur kernel may introduce strong artifacts in the resulting image. In this work we propose another image sharpening approach. Instead of accurately estimating the blur kernel of the whole image and performing deconvolution, we warp the uniform grid of the image so that pixels in the neighborhood of the blurred edge move closer to the edge. Warping approach for image enhancement had been introduced in [4]. The grid warping is performed according to the solution of a differential equation that is derived from the warping process constraints. The solution of the equation is used to shift edge neighborhood pixels closer to the edge, and the areas between edges are stretched. The drawback of this method is in its global nature: it is applied to the whole image, which may lead to the distortion of the edges. In [5] the warping map is computed using simple local measures of the image. The measures are computed separately for rows and for columns of the image with restrictions that prevent two consecutive samples from interchanging their order in the 1D sequence. This approach does not introduce edge overshoot and does not amplify the noise, but it can introduce small local changes in the direction of edges. In [6] a method is proposed that preserves the contours during enlargement, the method combines the warping of the coordinate point with the biasing of the signal amplitude. The warping approach is close to the morphology-based sharpening [7] and shock filters [8, 9, 10] and has the following advantages over them: the proposed method is applied to edges locally so the textures are preserved, also warping does not make the image piecewise constant. The method is computationally efficient. The method proposed in this work requires the approximate knowledge of the blur level of the image. In [11] an edge width estimation algorithm has been introduced. The method is based on the assumption that the blur of the image is close to Gaussian. The image is divided into blocks, and the blur kernel is supposed to be uniform inside the block. The estimation of the blurriness of the block is based on the maximum of difference ratio between an original image and its two re-blurred versions. In this work we also propose an edge width estimation method that works under the same assumption that the blur of the image is close to the Gaussian blur. We accurately estimate the standard deviation of the Gaussian kernel such that its convolution with the ideal step edge function gives the edge of interest. 2. ONE-DIMENSIONAL GRID WARPING The idea of one-dimensional edge sharpening is based on the assumption that the edge can be approximated by a step-edge function H (x) smoothed with a Gaussian kernel with a standard deviation [12]: H ( x) = 1, 0, x 0, x < 0, (1)

E (x) = [H G ](x).


The aim of the proposed method is to transform edge points coordinates in such a way that the slope of the edge becomes steeper (see Fig. 1).

The value mg is constant for each particle, so it is denoted k = A. Parameter A > 0 is responsible for the strength of grid warping. Thus, the equation for the new position of the particle is x - x = A cot (x). ~ ~ (2)
mg k

The dependence of the angle = (x) is obtained from ~ the equation of tangent:
a. Proposed approach: pixels are shifted b. Typical deblurring approach: pixel values are modified

tan = E (x) = [H G ](x) = G (x), ~ ~ ~ tan = tan ( + ) = - cot . 2 2 Thus, the main equation for one-dimensional grid warping (2) takes the following form: =- x - x = AG (x). ~ ~ (3)

Fig. 1. The idea of one-dimensional edge sharpening

2.1. A physical model for grid warping In the case of a continuous Gaussian edge (1) we redistribute the x-axis values according to the following physical model (see Fig. 2): let us assume that each point x of the edge is a particle with mass m situated on the edge slope E (x). The particle x is connected to its position via a spring with the coefficient of elasticity k . The end of the spring can move freely along y -axis at the point x and the spring always remains horizontal. The length of the spring in relaxed state is 0. Due to the force of gravity the spring is deformed until the particle reaches equilibrium. The new position x(x) now corresponds ~ to the edge intensity I (x) (see Fig. 1). This model ensures that the shape of the edge is not distorted and the grid transformation is smooth.

2.2. Theoretical constraints on the strength parameter A In order to make the result of edge warping continuous, the equation (3) should give one-to-one correspondence between x and x. The equation (3) is symmetric about the origin, ~ which gives us the opportunity to work only with the case of x 0: -x-(-x) = AG (-x) x-x = -AG (-x) = AG (x). ~ ~ ~ ~ ~

Fig. 2. Physical model for 1D edge sharpening The described physical model leads to the following equation for equilibrium at the point x(x) along the tangent line : ~ k x sin + mg cos = 0. The angle depends on the position x, = (x). The ~ ~ displacement along x-axis is x = x - x. ~ Thus, the displacement along the tangent line equals mg x = cot . k

Fig. 3. Graphical solution of the warp equation. Red curve represents the right part of the equation, blue lines represent the left part of the equation depending on parameter x. While solving the warp equation (3) with unknown x, in ~ the case of multiple solutions the one closest to zero is taken as a new coordinate for point x (see Fig. 3). Let us consider x = x0 such that the line l0 : y = x - x0 ~ is tangential to the graph of the function y = AG (x) in the ~ point of intersection x0 closest to 0. The equation of a tangent ~ line at the point x0 takes the following form: ~ l0 : y = AG (x0 )(x - x0 ) + AG (x0 ) = ~~~ ~ = AG (x0 ) · x + (AG (x0 ) - AG (x0 ) · x0 ). ~ ~ ~ ~ ~ This leads to the following:


AG (x0 ) · x + (AG (x0 ) - AG (x0 ) · x0 ) x - x0 ~ ~ ~ ~ ~ ~ AG (x0 ) = 1. ~ The equation AG (x) = 1 either a. has no solution, in this case the warp equation (3) has a single solution x for all x (see Fig. 4a), ~ or b. has a solution x0 , which leads to a discontinuity in ~ the solution of the warp equation (3) at x0 (see Fig. 4b).

Fig. 5. Displacements for two-dimensional grid warping. The thick line represents the exact edge location, white circles represent edge pixels, black circles represent pixels from the edge neighborhood 3.1. The edge blur level estimation We perform the estimation of the blur level of the detected edges E = {ei }N for the image I . We assume that the edge 1 width remains the same for the entire edge. For each edge ei we find a point pi belonging to this edge with the maximum gradient magnitude: pi ei : |g rad(I (pi ))| = max |g rad(I (p))|.
pe
i

a. continuous

b. discontinuous

Fig. 4. Warp equation solution. The X axis represents the original pixel coordinates while the Y axis -- the pixel coordinates after warping The above consideration gives us the following constraints on the strength parameter A: in order to have a continuous solution of the warp equation (3), the strength parameter A should be such that A< We use A = 0.99 · sharpening effect. 3. 2D EXTENSION The following algorithm has been developed for warping the grid of the 2D images in the neighborhood of the previously detected edges: 1. Estimate the blur level (the average standard deviation of Gaussian filter) for the edges. 2. For all pixels in the neighborhood of the edge compute the distance to the nearest edge point. 3. Compute vector field of displacements based on found distances (see Fig. 5). 4. Interpolate the image from the warped grid to the old uniform grid. In our work we use the result of Canny edge detection [13] as the input of the algorithm. The result of image warping is highly dependent on the input edges and it is very important to perform the edge detection carefully. The parameters of the Canny method ( and high threshold Thigh ) are chosen individually for each image. 1 . max G (x)
x

At the point pi we compute the edge profile P (pi ): we interpolate the image in the direction of the image gradient at this point. Then for the one-dimensional edge profile P (pi ) we analyze its width wi using the algorithm proposed in [12], [14] based on unsharp masking technique, where unsharp masking of a signal I is defined as: U, [I ] = (1 + )I - I G . 1. Given values: , UE , 1-dimensional edge profile E0 (x). 2. for = min to max step step compute U, [E0 ](x), find local maxima xmax of U, [E0 ](x), if U, [E0 ](xmax ) UE result = , stop cycle. 3. Output: result. In this work we use the following values: = 4, UE = 1.24, min = 0.5, max = 10, step = 0.1. For all found edge widths {i }N we take the median edge 1 width med and consider the image I to be blurred with a Gaussian kernel with standard deviation med : I = Isharp Gmed . 3.2. Distance transform to the nearest edge points We use the set of points M in the neighborhood of the edges E such that the distance from each point of M does not exceed 3 · wmed : M = {p : d(p, E ) 3 · wmed }. The value of the proposed radius is due to the fact that 99% of information of the Gaussian kernel of standard deviation is located in the interval [-3, 3 ].

1 max G (x)
x

in order to get a strong


For each point p of M we compute the Euclidean distance d to the nearest edge point. 3.3. Vector field of displacements The image I is considered to be defined on a uniform grid with each pixel having a coordinate (x, y ). The idea of 2D grid warping is to find such a vector of displacement v = {x, y } for each coordinate (x, y ) that the new coordinate (x + x, y + y ) becomes closer to the edge in terms of Euclidean distance. For each point p in the neighborhood of the edges with distance d to the nearest edge point e we solve the warp equation (3) with x d. The solution x gives the new distance ~ ~ d to the edge point e, and the magnitude of the displacement ~ vector v equals |v | = d - d. Also, the vector of displacement v is parallel to the direction of the image gradient at the point e and is directed towards e. For the points not from the neighborhood of the edges we consider the vector of displacement to be zero. 3.4. Image interpolation The idea of interpolation from the warped grid to the uniform grid is as follows: the intensity of the image at pixel (i, j ) is computed as a weighted sum of intensities of all points on the warped grid in the neighborhood of that pixel (see Fig. 6c): for a given radius r and all neighboring points {(xk , yk ) : (i - xk )2 + (j - yk )2 r}K the intensity of a dk = k=1 sharpened image Is at (i, j ) is computed as
K

Reference image

Blurred image

Level 1 (Blurred and noisy)

Level 2 (+ motion blur)

Fig. 7. Example of input images

Is (i, j ) =
k=1

1 I (xk , yk ), Dk

where Dk =

dk
K

.

dl
l=1

a. displacements

b. warped grid

c. interpolation

Fig. 6. Grid warping and interpolation We use the interpolation radius r = 1.5. 4. RESULTS The proposed method was tested on 29 images from LIVE database [15]. Two levels of degradation were considered.

The first degradation level contains the reference images blurred with Gauss blur with random radius in range [1, 6]. Gaussian white noise with random standard deviation in range [0, 10] was added. In the second level, the Gauss filter radius was multiplied by 0.6, noise level was doubled and random motion blur was added. The PSF of motion blur was modeled as a set of coordinates of a randomly moving point. The point had initial moving vector randomized in [-0.2, 0.2] range that was changed at every iteration by random value in [-0.1, 0.1] range, 30 iterations were taken. An example of input images is shown in Fig. 7. The proposed method was compared to common image deblurring algorithms. The image warping was applied both to degraded image and as post-processing algorithm for image deblurring algorithms. The results are shown in Fig. 8 and Table 1. It can be seen that the proposed technique makes the edges sharper and less noisy while keeping image textures almost intact. The developed image warping method also improves the results of other image deblurring methods. In comparison to other methods, the proposed method shows better results in hard cases, for example, in the presence of noise or when an accurate estimation of PSF is not available. The results of the proposed method for real images is shown in Fig 9. The edge map at the input of the algorithm has a great influence on the result of grid warping because only detected edges will be sharpened. In our work we use Canny edge map. As illustrated in Fig. 9, the method works best for strong


Reference image

Blurred and noise image

Method Blurred and noisy images Unsharp masking TV regularization Low-frequency TV reg. [16] TVMM [2] Lucy-Richardson [17] Wiener [17] MatLab blind deconvolution Proposed

Direct Level 1 Level 2 22.84 21.77 23.00 20.87 23.30 20.72 23.08 21.64 23.31 21.50 23.83 21.27 24.00 21.94 23.79 20.98 23.29 22.14

Post-processing Level 1 Level 2 -- -- 23.54 21.55 23.35 20.98 23.15 21.78 23.33 21.54 23.94 21.58 24.08 22.01 23.93 21.44 23.29 22.14

Table 1. Average PSNR values for the blurred and noisy images from LIVE database Blind deconvolution Unsharp mask ( = 4, = 2)

TV regularization

Low frequency TV reg [16]

TVMM [2]

Lucy-Richardson

Real blurred and noisy image

The result of LF TV reg [16]

Wiener filter [17]

Proposed method

The proposed method Wiener filter + proposed LF TV reg + proposed Fig. 9. The result of image warping for real image Fig. 8. Results of deblurring of blurred and noisy images


edges. The warping effect is non-perceptible for short edges, and the performance of the algorithm depends on the amount of edges, so it is better to process only isolated strong edges like basic edges [18]. Also the sharpening effect may be reduced if there are two or more edges closely situated, so the method will not work very well for some textures. At the current stage the sharpening of 512x512 Lena image with selected 140 edge segments takes as an example about half a second to be processed on computer with 2GHz Intel Core i5 processor. Meanwhile the proposed algorithm can be effectively parallelized in order to improve its performance. 5. CONCLUSION A method for image sharpening using image warping has been developed. The results show the effectiveness of the proposed method in the case of noisy images with inaccurately estimated blur kernels that is usual when deblurring real images. The method does not produce artifacts like ringing and noise amplification. The proposed method is effective as post-processing for edge sharpening in combination with other image deblurring methods. The developed warping method can be easily extended to the problem of image resampling with edge sharpness control. The work was supported by Russian Science Foundation grant 14-11-00308. 6. REFERENCES [1] M. Almeida and M. Figueiredo, "Parameter estimation for blind and non-blind deblurring using residual whiteness measures," IEEE Trans. Image Processing, vol. 22, pp. 2751­2763, 2013. [2] J. Oliveira, J. M. Bioucas-Dia, and M. Figueiredo, "Adaptive total variation image deblurring: A majorization-minimization approach," Signal Process., vol. 89, pp. 1683­1693, 2009. [3] S. D. Babacan, R. Molina, and A. K. Katsaggelos, "Variational bayesian blind deconvolution using a total variation prior," IEEE Transactions on Image Processing, vol. 18, pp. 12­26, 2009. [4] N. Arad and C. Gotsman, "Enhancement by imagedependent warping," IEEE Trans. Image Proc., vol. 8, pp. 1063­1074, 1999. [5] J. Prades-Nebot et al., "Image enhancement using warping technique," IEEE Electronics Letters, vol. 39, pp. 32­33, 2003. [6] A. Shimura and A. Taguchi, "Digital image interpolation with warping of coordinate point and biasing of

signal amplitude," Electronics and Communications in Japan, vol. 88, pp. 10­21, 2005. [7] J. Schavemaker, M. Reinders, J. Gerbrands, and E. Backer, "Image sharpening by morphological filtering," Pattern Recognition. [8] S. Osher and L. I. Rudin, "Feature-oriented image enhancement using shock filters," SIAM Journal on Numerical Analysis, vol. 27, no. 4, pp. 919­940, 1999. [9] G. Gilboa, N. A. Sochen, and Y. Y. Zeevi, "Regularized shock filters and complex diffusion," Lecture Notes in Computer Science, vol. 2350, pp. 399­413, 2002. [10] J. Weickert, "Coherence-enhancing shock filters," Lecture Notes in Computer Science, vol. 2781, pp. 1­8, 2003. [11] H. Hu and G. de Haan, "Low cost robust blur estimator," in IEEE International Conference on Image Processing, 2006, pp. 617­620. [12] A. A. Chernomorets and A. V. Nasonov, "Deblurring in fundus images," in 22-th Int. Conf. GraphiCon'2012, Moscow, Russia, 2012, pp. 76­79. [13] J. Canny, "A computational approach to edge detection," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, pp. 679­698, 1986. [14] A. A. Nasonova and A. S. Krylov, "Determination of image edge width by unsharp masking," Computational Mathematics and Modelling, vol. 25, pp. 72­78, 2014. [15] H. Sheikh, M. Sabir, and A. Bovik, "A statistical evaluation of recent full reference image quality assessment algorithms," IEEE Transactions on Image Processing, vol. 15, no. 11, pp. 3440­3451, 2006. [16] A. S. Krylov and A. V. Nasonov, "Adaptive image deblurring with ringing control," Fifth International Conference on Image and Graphics (ICIG '09), pp. 72­75, 2009. [17] J. G. Nagy, K. Palmer, and L. Perrone, "Iterative methods for image deblurring: A matlab object-oriented approach," Numerical Algorithms, vol. 36, no. 1, pp. 73­ 93, 2004. [18] A. V. Nasonov and A. S. Krylov, "Edge quality metrics for image enhancement," Pattern Recognition and Image Analysis, vol. 22, pp. 346­353, 2012.