Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cs.msu.ru/pub/2009.ICIP.Nasonov_Krylov.RinMetr.en.pdf Дата изменения: Thu Aug 6 23:00:00 2009 Дата индексирования: Mon Oct 1 19:48:18 2012 Кодировка:

SCALE-SPACE METHOD OF IMAGE RINGING ESTIMATION Andrey V. Nasonov, Andrey S. Krylov Lab. of Mathematical Methods of Image Processing, Faculty of Comp. Mathematics and Cybernetics Moscow Lomonosov State University, e-mail: nasonov@cs.msu.ru , kryl@cs.msu.ru
ABSTRACT Suppression of ringing effect is a challenging problem. It is mainly caused by absence of effective methods of ringing artifact detection. In this paper we introduce a ringing estimation method based on scale-space analysis. The estimation shows good results for low-pass filtered test images and in adaptive image deringing. Index Terms-- Ringing estimation, total variation, scale space, adaptive deringing 1. INTRODUCTION Development of image enhancement methods is one of the most important image processing tasks. Ringing effect (Gibbs phenomenon) appears in images as oscillations near sharp edges. It is a result of a cut-off of high-frequency information. Ringing can appear as a result of image compression, image upsampling and other applications. An example of this effect can be seen in old video stored in analog format (Fig.1). One of the main problems of image deringing is to detect the presence of ringing effect and to estimate the necessary ringing suppression level. But there is no algorithm which estimates ringing level in the general case. There are image ringing estimation algorithms to measure ringing effect for a specific problem. In [1] wavelet decomposition is used and ringing effect is measured for JPEG-2000 compression as a difference between correlations of neighbor coefficients of different wavelet subbands. The problem of image deringing after JPEG-2000 compression is also considered in [2], [3]. Some metrics were developed to control image deringing as a postprocessing. Regularization parameter estimation for image deringing using MAP approach is proposed in [4]. For the problem of image deringing after resampling, regularization parameter is estimated using information on the initial low resolution image [5]. In [6], the ringing metrics is defined as maximum of the differences between pixel values of the reference image and the processed image in the edge neighborhood. The size of this neighborhood is fixed a priori.
The work was supported by federal target program "Scientific and scientific-pedagogical personnel of innovative Russia in 2009-2013" and RFBR grant 09-01-92474-MHKC.

Fig. 1. A video frame with a strong ringing effect. In [7], the presence of ringing effect is detected by comparing the directions of image gradients at different scales. The work [8] does not introduce a ringing estimation method, but it presents an algorithm to find regions where the ringing effect is the most visible. It is based on luminance masking and texture masking as typical for the human visual system. In this article, we suggest new general ringing estimation algorithm based on total variation (TV) control. The TV was first used in image enhancement by Rudin, Osher and Fatemi [9] for image denoising. General relations between TV and ringing effect can be found in [10]. 2. ONE-DIMENSIONAL TOTAL VARIATION In one-dimensional case, Total Variation functional is defined as
b

T V (f ) =
a

|f (x)|dx.

In a discrete case a = x0 x1 . . . xn = b, it looks as: T V (f ) =
i=1 n

|f (xi ) - f (xi

-1

)|.

We also consider weighted TV (WTV) with weight function w(x):
b

T V (f , w ) =
a

|f (x)|w(x)dx.

In the discrete case it looks as
n

T V (f , w ) =
i=1

|f (xi ) - f (xi

-1

)|w

xi

-1

+x 2

i

.


3. RINGING ESTIMATION FOR ONE-DIMENSIONAL EDGE We consider the problem of ringing level estimation for step edge with width d: 0, x < -d/2, f d (x) = x/d + 1/2, -d/2 x < d/2, 1, x d/2. at the interval with the length d. In the discrete case, T V (f d ) = 1 for any grid. Ringing effect can be generated by ideal low-pass filter which truncates high frequency data. We implement it using sinc interpolation of the step edge f 0 (x) given at the discrete set {xk }, xk = dk + d with sampling period d: 2 fd (x) =
k

1,0

0,8

0,6

0,4

0,2

0,0 -4

x

0

-2

0

2

x

1

4

Fig. 2. Edge width estimation illustration. For the shown case, the estimated edge width is 4.3 pixels. e 2(d)2 , where controls the number of considered ringing oscillations. To find the differences between edges with ringing effect and edges without it, we analyze the functional T V (f , , wd ) = T V (f G , wd ), (2)
-
x2

f (xk )sinc

x - xk , d

(1)

where sinc(x) = sin x x . We call here the value d as ringing half-period. It is an analog of step edge width for edges with ringing effect. Real edges are corrupted by noise, so this fact is to be considered too. In this work, we analyze the case of additive uniform noise fd,n (x) = fd (x) + n (x), f d,n (x) = f d (x) + n (x), where n (x) is uniformly distributed random function which values are in (-n/2, n/2) range. We consider n n0 , where n0 is the maximum noise value.

3.1. Edge width estimation For further scale-space TV analysis, we need to make a definition of the edge width. To find edge width for an arbitrary edge f (x), we approximate it by the edge f d (x) (3). We seek for minimum f0 and maximum values f1 of f (x) in a neighborhood of the edge center. For simplicity, we consider f0 = 0, f1 = 1.The size of this neighborhood is chosen a priori and represents the maximum considered edge width. Next we find the coordinates of intersections of y = f (x) with y0 = 1/4 and with y1 = 3/4, draw a line through these points and find x0 and x1 as it is shown in Fig.2. In the case of multiple intersections we take the average of intersection points. We call the obtained value as the edge width. To reduce the influence of ringing artifact and noise to the edge width, we smooth the edge using Gauss filter with radius 3 4 d, calculate the values f0 and f1 for the smoothed edge and recalculate edge width using these values. 3.2. Scale-space TV analysis We performed an experimental analysis of edge TV with different widths d at different scales . Real edges are not infinite. To take into account only several first ringing oscillations, we use weighted TV with Gaussian weight wd (x) =

where f G is a convolution of f with Gauss filter with radius . To design an algorithm to find the value 1 that best discriminates between edges with ringing artifact and edges without ringing artifact for fixed d, fixed maximum noise level n0 and given parameter , the following analysis has been performed: A set of 5000 step edges without ringing effect f d,n (set A) and 5000 edges with ringing effect fd,n (set B ) with random noise levels 0 n n0 for each edge was generated. For every , the intervals of values of (2) were calculated for both sets A and B . If these intervals do not intersect, can be used for ringing detection. The intervals of values of function (2) for d = 10, n0 = 0.1 and = 3 are shown in Fig.3. It can be seen that there is a set of (marked as yellow area) which can be used to distinguish between sets A and B . T V values of edges with ringing artifacts are greater than T V values of edges without ringing effect. We calculated minimal value of T V of edges with ringing artifact g (d, ) = min T V (fd,n , , wd ) and maximal value of T V of edges without ringing artifact g (d, ) = min T V (f
d,n

, , wd ).

Next we found that corresponds to the maximal gap between g (d, ) and g (d, ): 1 (d) = arg max (g (d, ) - g (d, )) .


(3)

The calculated values of 1 (d) for n0 = 0.1 and = 3 for different d are shown in Fig.4. The function 1 (d) is close to linear function, its random fluctuations are caused by noise and we use the approximation 1 (d) = m(, n0 )d.


level RE (f , d) with precalculated threshold functions G (d) = g (d, m(, n0 )d), G (d) = g (d, m(, n0 )d). If RE (f , d) G (d), we assume that the edge does not have ringing artifact. If RE (f , d) G (d), we assume that the edge has ringing artifact. In practice, signals are not perfectly bandlimited and ringing effect is weakened. Thus RE (f , d) can fall into (G (d), G (d)) interval. The decision in this case needs additional analysis for each specific image class. For example, for linearly interpolated images or for video stored in analog format, we assume that ringing effect is presented in this case. The calculated threshold functions G (d) and G (d) for n0 = 0.1 and = 3 for different d are shown in Fig.5.

Fig. 3. Scale-space TV analysis for noisy edges with width d = 10, maximum noise level n0 = 0.1 and = 3 (number of oscillations 3). Blue area is the range of values of function (2) for edges with ringing effect f d,n . Red areas is the range of values of (2) for edges without ringing effect fd,n . Black area is the intersection between blue and red areas. Yellow area corresponds to possible which can be used to separate red and blue areas.
4

1,7

1,6

G
1,5

*

TV

G

*

1,4

3
Optimal

1,3


1,2

2



0

2

4

6

8

10

1

d

12

14

16

18

20

22

0

0

5

d

10

15

20

Fig. 5. Thresholds G (d) and G (d) for n0 = 0.1 and = 3. Fig. 4. The results of 1 calculation (3) for n0 = 0.1 and = 3 for different d. Thin line is a linear approximation of function 1 (d). For = 3 and n0 = 0.1, we use m(, n0 ) = 0.19. For = 3, n0 = 0.2, m(, n0 ) = 0.25. Experiments have shown that m(, n0 ) does not depend too much on for reasonable values ( > 2). This enables us to consider the value
RE (f , d) = T V (f , m(, n0 )d, wd )

4. RINGING ESTIMATION FOR TWO-DIMENSIONAL IMAGES We consider the problem of ringing estimation for twodimensional images with uniform ringing effect. It means that cut-off frequency is constant and ringing half-period D is the same for any edge normal cross-section. We apply the following algorithm: 1. Perform edge detection and extract edge normal crosssections fk , k = 1, 2, . . . , N for strong isolated edges [11]. 2. Estimate edge widths dk = d(fk ) for all k and calculate ringing half-period D. For real images, edge width is different for different edges due to blur and noise. We treat dk as a distribution and estimate D as the value of the highest density of this distribution. To reject noise and blur outliers, we take only edges where |dk /D - 1| 0.2. 3. For every edge we calculate its ringing level RE (fk , D), and we define image ringing level RI as an average of all obtained edge ringing levels. 4. At the last stage, we compare RI with the precalculated ringing thresholds G (D) and G (D) and make the decision about the presence of ringing artifact in the image.

as edge ringing level. For the case of edges with an arbitrary height, we perform a normalization. For = d, the values g ( ) and gd ( ) were found close, so it is natural to divide the value RE by T V (f , d, wd ). Ringing value takes the form: RE (f , d) = T V (f , m(, n0 )d, wd ) . T V (f , d, wd )

To make a decision about the presence of ringing effect for edge f with edge width d, we compare the calculated ringing


5. RESULTS The effectiveness of the proposed ringing estimation algorithm was shown by image deringing applications. 1. Correspondence between the proposed ringing level and existing image deringing algorithm. Ringing level was calculated for the initial low-resolution image, for the image resampled by regularization method [11] and for the resampled image postprocessed by deringing method [5]. The results are given in Fig.6. It shows that the proposed ringing estimation algorithm can be used to control ringing level in image deringing applications.

7. REFERENCES [1] Madhuri Khambete and Madhuri Joshi, "Blur and ringing artifact measurement in image compression using wavelet transform," Proceedings of World Academy of Science, Engineering and Technology, vol. 20, pp. 183­ 186, 2007. [2] Tao Wang and Guangtao Zhai, "Jpeg2000 image postprocessing with novel trilateral deringing filter," Optical Engineering, vol. 47, pp. 027005, 2008. [3] Jinyong Fang and Jun Sun, Advanced Intelligent Computing Theories and Applications. With Aspects of Contemporary Intelligent Computing Techniques, chapter Ringing Artifact Reduction for JPEG2000 Images, pp. 1026­1034, Springer Berlin Heidelberg, 2007. [4] Seungjoon Yang, Yu-Hen Hu, Truong Q. Nguyen, and Damon L. Tull, "Maximum-likelihood parameter estimation for image ringing-artifact removal," IEEE Trans. Circuits Syst. Video Technol, vol. 11, pp. 963­973, 2001.

Fig. 6. Ringing estimation for image deringing after resampling [5]. Left image: source image upsampled by pixel replication, RI = 1.05. Middle image: image interpolated by regularization-based method with low regularization [12], RI = 2.20. Right image: interpolated image postprocessed by deringing after resampling [5], RI = 1.06. 2. Automatic image deringing for real video. The strength of the deringing algorithm [5] was consecutive increased until ringing level RI of the processed video frame was less than the threshold G . A result is shown in Fig.7

[5] A. S. Krylov and A. V. Nasonov, "Adaptive total variation deringing method for image interpolation," Proceedings of ICIP'08, pp. 2608­2611, 2008. [6] Pina Marziliano, Frederic Dufaux, Stefan Winkler, and Touradj Ebrahimi, "Perceptual blur and ringing metrics: application to jpeg2000," Signal Processing: Image Communication, vol. 19, pp. 163­172, 2004. [7] T. Kartalov, Z. A. Ivanovski, L. Panovski, and L. J. Karam, "An adaptive pocs algorithm for compression artifacts removal," 9th International Symposium on Signal Processing and Its Applications, pp. 1­4, 2007. [8] Hantao Liu, Nick Klomp, and Ingrid Heynderickx, "Perceptually relevant ringing region detection method," 16th European Signal Processing Conference Proceedings, 2008.

Fig. 7. Automatic image deringing. Left image: original image with ringing effect, RI = 1.44. Right image: the result of automatic deringing with ringing level control, RI = 1.20.

[9] L. Rudin, S. Osher, and E. Fatemi, "Nonlinear total variation based noise removal algorithms," Physica D, vol. 60, pp. 259­268, 1992. [10] S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, 1999. [11] A. V. Nasonov and A. S. Krylov, "Adaptive image deringing," To appear in Graphicon'2009, 2009. [12] A. S. Lukin, A. S. Krylov, and A. V. Nasonov, "Image interpolation by super-resolution," Proceedings of GraphiCon'2006, pp. 239­242, 2006.

6. CONCLUSION Scale-space ringing level estimation for one-dimensional functions and two-dimensional images was proposed. Very promising results were achieved for deringing after resampling and adaptive deringing using ringing level control in the presence of noise. Future work on the proposed ringing level estimation method includes additional refinement of the ringing criterion for different image classes and edge width estimation.