Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cmc.msu.ru/pub/2009.Graphicon.Krylov_Nasonov.IntComb.en.pdf
Дата изменения: Fri Aug 21 23:00:00 2009
Дата индексирования: Mon Oct 1 19:39:09 2012
Кодировка:

Combined linear resampling method with ringing control
Andrey S. Krylov, Andrey V. Nasonov, Alexandra A. Chernomorets Laboratory of Mathematical Methods of Image Processing, Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, {kryl, nasonov}@cs.msu.ru

Abstract
New method to combine different linear interpolation algorithms is suggested. It uses total variation analysis to suppress ringing artifact of the combination. This method enables to construct fast edge adaptive resampling methods. Its usage is illustrated with combinations of sinc, Papoulis and bicubic interpolation algorithms using new image metrics for interpolation methods quality analysis. The method can be also used to combine non-linear methods. Keywords: Image interpolation, ringing artifact, deringing, total variation, image metrics.

2. INTERPOLATION
We consider only the case of one-dimensional interpolation. For two-dimensional images, we perform interpolation first by rows, then by columns. Generally, linear interpolation of a function F (x) given on a discrete set {xi = ih} looks as:
+

f (x) =
i=-

F (ih)K (i - x/h),

(1)

where K (x) is an interpolation kernel. In this work the following interpolation methods are used: 1. Sinc (or 'ideal') interpolation. If the input function satisfies the condition of the Shannon-Kotelnikov sampling theorem, then it can be reconstructed using (1) with K (x) = sincx = sin x . x

1. INTRODUCTION
Every linear resampling method has its own trade-off between three types of artifacts: ringing, aliasing and blur, illustrated in Fig.1. For example, 'ideal' interpolation method which reconstructs the image by a sampling theorem processes edges good, but introduces strong ringing effect. On the other hand, bilinear interpolation adds blur and aliasing to the edges, but does not add ringing artifact. The detailed overview of linear image interpolation methods can be found in [1].

2. Bicubic interpolation: 1, (a + 2)|x|3 - (a + 3)|x|2 + 1, K (x) = a|x|3 - 5a|x|2 + 8a|x| - 4a, 0, We use bicubic interpolation with a = -0.5.

for x = 0, for 0 < |x| < 1, for 1 < |x| < 2, otherwise.

Blur

Aliasing

Ringing

3. Interpolation using Papoulis sampling theorem [7, 8]. If the original signal is represented as a series of its samples and its first and second derivatives (we call it Papoulis-2), it can be reconstructed as
+

f (x) = 3 sin3 ( x) Figure 1: Typical artifacts of linear interpolation methods. +F (i) One of the ways to improve the quality of linear interpolation methods is to perform additional postprocessing to suppress the artifacts. Lots of general purpose deblur and deringing algorithms were developed. Most of the deblurring algorithms are based on deconvolution problem with regularization [2, 3]. In [4], image is decomposed into cartoon-like component and texture component and different methods are used to process these components. Regularization approach is also used for image deringing [5]. Another way is to embed artifact suppression method in the interpolation algorithm. It can be done by a method that constructs highresolution images using a combination of two interpolation methods, where one of the methods works well in the edge area while the other method shows better results in the rest of the image. At the same time the edge detection procedure to detect edge areas is time consuming and often suffers from noise. In our approach, we use total variation (TV) analysis instead of edge detection. TV value is closely related with ringing effect [6]. If TV increases after interpolation, we assume that the method causes ringing effect.
i=-

F (i)

2 + 2 (x - i)2 + 6 3 (x - i)3 (2)

1 1 + F (i) 3 . 3 3 (x - i)2 6 (x - i)

We do not know the derivatives of F (x) in sampling points, so we use the following approximation: F (i + 1) - F (i - 1) , 2 F (i + 2) - 2F (i) + F (i - 2) . F (i) = 4 F (i) = Thus, the formula (2) can be interpreted as linear interpolation method (1) with K (x) = 3 sin3 ( x) 1 3
3

1 2x +2 + x3 (x - 1)2 1 1 + , x(x2 - 4) 6 x

(3)

K (0) = 1, K (1) = K (-1) = K (2) = K (-2) = 0. The kernels of these methods are illustrated in Fig.2.

1.0

1.0

0.8

0.8

If we consider the problem of interpolation of F (x) on a discrete grid with interpolation factor q , we do not need to construct the continuous function r(x), and the formula (6) takes the form k(x) = T V (R, x - nh, x + nh) , T V (F, x - nh, x + nh) (7)

0.6

0.6

0.4

0.4

0.2

0.2

0.0

0.0

-0.2

-0.2

where R(x) is r(x) defined on the grid {xi = ih/q }.
-10 -5 0 5 10

-10

-5

0

5

10

We use the following criteria for (x) computation: 1. If k(x) B , we assume that the ringing effect is noticeable, and we take (x) = 1. 2. If k(x) A, we assume that the ringing effect is unnoticeable, and we use (x) = 0. 3. if A < k (x) < B , we use (x) =
k(x)-A B -A

1.0

0.8

0.6

0.4

0.2

.

0.0

Parameters A and B are the thresholds.
-10 -5 0 5 10

-0.2

3.2 Threshold Analysis
We estimate the parameters A and B experimentally using minimization the 2D image quality metrics from [9]. B E P (Basic Edges Points RMSE) value measures the root of the average square error in edge points area. B E N (Basic Edges Neighborhood RMSE) value calculates the error in edge neighborhood where ringing effect usually appears. As an example, sinc interpolation shows good B E P and bad B E N while bicubic interpolation results in good B E N and bad B E P . To find a balance between these two metrics, we use B E Q metrics: B E Q = log
2

Figure 2: Interpolation kernels for sinc interpolation (left graph), bicubic interpolation (right graph) and Papoulis-2 interpolation (bottom graph).

3. COMBINED METHOD
We construct the interpolated function f (x) as a combination of two functions f (x) = (x)s(x) + (1 - (x))r(x), (4)

BEN BEP + log2 , B E P B E N

where r(x) is the interpolation of F (x) using the method which produces ringing effect but processes edges well, and s(x) is the result of interpolation method which produces smooth image with smaller ringing effect.

where B E P and B E N are the normalization constants. These constants do not affect the difference between BEQ values of different images. We choose B E P and B E N as the minimal values of B E P and B E N respectively of the results of interpolation methods for the given image. The proposed combined method was analyzed with different pairs of interpolation methods. The analysis consisted in choice of threshold values A and B by minimization of the B E Q value. Experiments show that the parameters A and B depend on the used pair of interpolation methods. We have calculated threshold values A and B for combinations of sinc, Papoulis-2 and bicubic interpolation methods on a set of standard test images Lena, Barbara, Peppers, Boat, House. The results are presented in table.1. Interpolation Methods Sinc + Bicubic Sinc + Papoulis-2 Papolis-2 + Bicubic threshold A 1.10 1.09 1.20 threshold B 1.31 1.19 1.32

3.1 Total Variation Approach
The coefficient (x) in (4) is calculated using the analysis of total variation (TV) of F (x) and r(x). In one-dimensional case, TV functional is defined as
b

T V (f , a, b) =
a

|f (x)|dx.

In the discrete case {xi = ih}, it is computed as:
ib -1

T V (f , a, b) =
i=ia

|f ((i + 1)h) - f (ih)| +

+(ia h - a)|f (ia h) - f ((ia - 1)h)| + +(b - ib h)|f ((ib + 1)h) - f (ib h)|, where ia = a/h), ib = b/h).
a h b h

(5)

Table 1: Optimal threshold values A and B for different combinations of interpolation methods.

(the less integer value greater than or equal to (the greater integer value less than or equal to

3.3 Method speed-up
The performance of TV calculation of the proposed method can be improved using the additive property of TV T V (f , a, b) + T V (f , b, c) = T V (f , a, c) for a b c. This means, that if we shift the window of TV calculation by x, we need just to update the previously calculated TV value T V (f , a+x, b+x) = T V (f , a, b)+T V (f , b, b+x)-T V (f , a, a+x).

We calculate the ratio between TV of the input image row (column) and TV of its interpolation k(x) = T V (r, x - nh, x + nh) , T V (F, x - nh, x + nh) (6)

where the parameter n defines the half-size of the window of TV calculation. Experiments have shown that good results are obtained with n = 3.

4. RESULTS
The proposed method is illustrated with 'house' image from the test image set in Fig. 3. The values of MSE, BEP, BEN and BEQ metrics for these images are shown in Tab. 2. It can be seen that the combined method keeps both BEP and BEN metrics low. Despite of slightly increased MSE value, the results of the combined method looks better than of pure sinc or bicubic methods. B E Q metrics correlates with the perceptual image quality.

[2] Hiroyuki Takeda, Sina Farsiu, and Peyman Milanfar, "Deblurring using regularized locally adaptive kernel regression," IEEE Trans. Image Proc., vol. 17, no. 4, pp. 550563, 2008. [3] Li Chen, , and Kim-Hui Yap, "A soft double regularization approach to parametric blind image deconvolution," IEEE Trans. Image Proc., vol. 14, no. 5, pp. 624633, 2005. [4] Takahiro Saito, Yuki Ishii, Haruya Aizawa, and Takashi Komatsu, "High-quality image interpolation via nonlinear image decomposition," Proceedings of the SPIE, vol. 6812, pp. 68120V68120V12, 2008. [5] V. B. S. Prasath and A. Singh, "Ringing artifact reduction in blind image deblurring and denoising problems by regularization methods," International Conference on Advances in Pattern Recognition, pp. 333336, 2009.

Reference image

BEP area

BEN area

[6] S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, 1999. [7] F. Deschenes A. Hore, D. Ziou, "A new image scaling algorithm based on the sampling theorem of papoulis and application to color images," ICIG 2007, pp. 3944, 2007. [8] A. Papoulis, "Generalized sampling theorem," IEEE Trans. on Circuits and Systems, vol. 24, pp. 652654, 1977.

Sinc interpolation

Bicubic interpolation

Combined method

[9] A. V. Nasonov and A. S. Krylov, "Adaptive image deringing," Proceeding of Graphicon'2009, 2009.

Figure 3: Illustration of the proposed method by the test image with sinc and bicubic methods. Grey lines in BEP and BEN areas images are the edges. MSE 109.5 112.1 125.4 112.1 109.4 113.3 BEP 14.124 14.247 15.178 14.181 13.894 14.302 BEN 4.426 4.032 3.971 3.970 4.039 3.981 BEQ 0.181 0.059 0.128 0.029 0.025 0.046

About authors
Andrey S. Krylov is associated professor, Head of the Laboratory of Mathematical Methods of Image Processing, CMC MSU. Email: kryl@cs.msu.ru Andrey V. Nasonov is member of scientific staff of CMC MSU. Email: nasonov@cs.msu.ru Alexandra A. Chernomorets is a student of CMC MSU.

Sinc interpolation Papoulis interpolation Bicubic interpolation Sinc + Bicubic Sinc + Papoulis Papoulis + Bicubic

Table 2: The values of metrics for the images from Fig. 3.

5. CONCLUSION
It was shown that total variation analysis concept enables to combine different linear interpolation algorithms to suppress ringing artifact. New image metrics for interpolation methods quality analysis were used to numerically evaluate the results of the proposed method. Experiments show that the combined method parameter selection using these metrics correspond well to visual image quality enhancement. Fast and effective implementation of the proposed method which is useful for embedded solutions has been suggested. The algorithm can be extended using the combination of more than two methods which are not necessary linear. The work was supported by federal target program "Scientific and scientific-pedagogical personnel of innovative Russia in 20092013" and RFBR grant 09-01-92470-MHKC.

6. REFERENCES
[1] P. Thevenaz, T. Blu, and M. Unser, "Interpolation revisited," IEEE Trans. Medical Imaging, vol. 19, no. 7, pp. 739758, 2000.