Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cs.msu.ru/pub/Deringing08.pdf Дата изменения: Wed Sep 17 23:00:00 2008 Дата индексирования: Mon Oct 1 19:38:10 2012 Кодировка:

ADAPTIVE TOTAL VARIATION DERINGING METHOD FOR IMAGE INTERPOLATION Andrey Krylov, Andrey Nasonov Faculty of Computational Mathematics and Cybernetics, Moscow Lomonosov State University 119991, Leninskie Gory, Moscow, Russia
ABSTRACT This paper presents a new adaptive post-processing algorithm for ringing artifact reduction after image interpolation (upsampling). The algorithm is based on the concept of total variation (TV) for ringing control. It uses known TV of the blocks of the low-resolution image. Conditional gradient, subgradient and projection subgradient methods for this algorithm are considered and analyzed. A test set of 181300 overlapping 11x11 blocks of real images was used for local algorithm optimization and analysis. Local conditional gradient method shows the best objective and subjective results. Index Terms-- deringing, total interpolation, image enhancement 1. INTRODUCTION Existing image deringing algorithms are usually focused on ringing reduction after specific resampling or compression algorithms and do not use information on the downsamlped or undisturbed image. They can be divided into the following large groups: 1. Algorithms that suppress ringing and block effect for specific compression algorithms. For example, methods based on partial differential equations are used for JPEG2000 deringing [1]. JPEG blocking and ringing effects are reduced by filtering in DCT domain [2], or by specific artifacts removing algorithms [3]. 2. Algorithms using knowledge of the structure of image or using edge detection. The example is cartoon deringing using example-based synthesize [4]. 3. General filtering algorithms like median filtering [5], diffusion [6], deconvolution, regularization [7], or edge enhancement [8]. Ringing suppression in this case is not a primary goal and it results in image oversmoothing. In this paper we design an adaptive image deringing (Gibbs effect suppression) algorithm for the case of image post-processing after image interpolation (upsampling). The method is based on the concept of TV for ringing control. It uses known TV of the blocks of the low-resolution image. Originally, TV method in image processing literature was proposed by Rudin, Osher and Fatemi [9] where TV variation, image image denoising was considered. Gibbs phenomenon (ringing) is also associated with image TV [10]. In two-dimensional case, TV can be defined in different ways.

1. TV ( z ) 2. TV ( z )




z d




| z x |2 | z y |2 d,




| z x | | z y | d.

The first variant was used by Rudin, Osher, Fatemi, but many image processing algorithms use the second one [11]. We use the second variant. General TV minimization problem can be posed in 3 forms. 1. z arg min( Az u TV ( z )),
zZ

2. z arg min Az u , M {z Z | TV ( z ) C},
zM

3. z arg minTV ( z ), M {z Z | Az u },
zM

where A is a continuous linear operator. The first problem is a particular case of Tikhonov regularization method, a nd this problem is well-posed [12], because TV ( z ) is a convex functional. The second one is a particular case of a problem of finding quasi-solutions [13]. The set M is convex, and the obtained problem is well-posed under additional condition that z lie in a bounded set. This is true in the case of A E (unit operator). The third problem is also wellposed. Using the approach [14] we have proved the equivalence of these forms in the case A E . Thus for any C there are and , so the solution of the first problem is also the solution of the second and the third problems and vice versa. 2. PROBLEM DEFINITION First we consider one-dimensional TV problem with A E in discrete form for an initial signal v and upsampled signal u with scale factor s . TV of high-resolution signals and images is usually greater than their low-resolution variants. Many real objects have fractal nature and there are fractalbased resampling algorithms [15], but most of the resampling algorithms do not use this fact. We assume, that TV does not change, and additional variation of upsampled


image is caused by ringing artifacts. So, if TV (u) TV (v) , then we solve the following variational problem for 1-D: z arg min z u 2 , where
zM

M {z Z | TV ( z) C TV (v)} , TV ( z )


i

| zi z

i 1

|.

blocks from 7x7 (4x4 in initial image) to 15x15 in interpolated image (8x8 in initial image). Small size results in bad ringing suppression, big block size give loss of fine details. Our test results were practically the same for block size in the region from 7x7 to 15x15. 3. NUMERICAL METHODS ANALYSIS There are several effective iterative methods to solve problems (1) and (2). We consider conditional gradient method and subgradient projection method for solving ( 1), and subgradient method for solving (2). A set of 100 nature and architecture images with 400x300 resolution was used to test the methods. We downsampled the images by 2 using Gauss blur with radius 0.7 and then upsampled them by regularization-based interpolation algorithm [16]. Next we applied deringing method and compared the results with initial images (reference images). Below we show the results for overlapping 11x11 blocks (1813 per image) and for the global method. 3.1. Conditional gradient method Conditional gradient method for minimization of convex functional F ( z ) z u
2 2

In two-dimensional case, we assume, that the variation of any single row or column does not change, but the number of rows and columns is proportional to the scale factor s . So, the problem of image deringing can be considered as z arg min z u 2 , where

M {z Z | TV ( z) C s TV (v)} ,

zM

TV ( z )

|
i, j

z

i, j

z

i , j 1

|


i, j

|z

i, j

z

i 1, j

|.

We pose two problems: standard (global) TV problem for entire image and local block TV variation problem. 2.1. Global deringing We consider interpolated image u as a function of a Hilbert space H with Euclidian norm and scalar product. The set of images with bounded TV M {z Z | TV ( z) C TV (v)} is a convex set in H . We find Euclidian projection of u onto M : z arg min z u 2 , where zM (1 ) M {z Z | TV ( z) C s TV (v)} . This algorithm can also be used for general deringing, when initial image is unknown. In this case, we define TV reduction factor k [0, 1] and solve the problem

in a convex polyhedron was

z arg min z u 2 , M {z Z | TV ( z) C k TV (v)} .
zM

This problem can be also solved by regularization method: z arg min( z u 2 TV ( z )) , (2 ) zZ

where (C ) is a regularization parameter. The problem (1) is equivalent to (2). 2.2. Local deringing Images are not uniform, and ringing artifacts are not uniformly distributed and the method, which reduces TV for the whole image is not effective. Ringing artifacts should be removed locally. We divide both initial and interpolated image into a set of corresponding square blocks with equal size. Each pair of blocks is processed by global deringing algorithm separately. Overlapping blocks are taken to eliminate blocking artifacts. The size of these blocks is chosen in accordance to the size of ringing effect. It depends on used interpolation algorithm. For example, for interpolation by 2, we analyzed

introduced in [17]. The main idea of this method is to find a minimizing direction from a finite set of vectors [18]. The vertices of the convex set M {z | TV ( z) C} can be written easily only for one-dimensional case and we use onedimensional algorithm to process two-dimensional images. It is applied separately to a set of corresponding rows and columns of the source and interpolated images. The following ways of constructing the resulting twodimensional image by the algorithm were analyzed: 1. We process the interpolated image horizontally (by rows) z z H . This means that each row of image z is processed independently from others, and the processed rows form image z H . Next we process the interpolated image vertically (by columns) z zV , and calculate the weighted sum between these resulting images z R z H (1 ) zV , [0, 1] . 2. We compute two resulting images: the first one is processed horizontally and then vertically z z H z HV , and the second one is processed vertically and then horizontally z zV zVH . The final image is calculated as

z R z HV (1 ) zVH , [0, 1] . This is twice slower than the first way. Weight value can also be chosen differently: 1. 0.5 . 2. The weight is chosen in accordance with minimization the discrepancy z R u 2 . It is correlated with


the optimal coefficient



opt

, which minimizes the

discrepancy between the resulting image and reference image z R u 2 . For the test image set cor ( , opt ) 0.27 .

3. Choose equal to 0 or 1 by analysis of the block structure. This way is twice faster than first two, because we need to calculate only single result z H or zV ( z HV or zVH ), but not both. We use the following algorithm: if horizontal TV suppression value is greater than vertical where TVH (u) s TVH (v) TVV (u) s TVV (v) ,

is similar to subgradient method and it can be formulated in the following form [19]: (3 ) z ( k 1) prM ( z ( k ) k g ( k ) ), where prM is the projection operator onto convex set M . If the set M is defined as M {z | f ( z) 0} , where f ( z ) is a convex functional, then the projection operator can be approximated iteratively. In our case

F ( z) z u 2 ,

2

TVH (u ) | u x | d , TVV (u ) | u y | d , then we use

1 , else 0 .









f ( z) TV ( z) C , and the solution of minimization problem is equal to the projection of u onto the set M , or just
performing one iteration of (3) with z (0) u . This approach is also used for image restoration in [20]. The projection can be calculated approximately as z ( k 1) z ( k ) k g ( k ) , where

The average PSNR test set results for 200 iterations 1st way 2nd way no processing 2 8 .3 8 0.5 2 9 .1 5 2 9 .2 [0, 1] 2 9 .0 0 2 9 .2 2 9 .0 5 2 9 .2 0 or 1
Table 1. 2-D processing parameter analysis results.

are

g
4 3 2

(k )

f ( z 0,

(k )

),

z z

(k ) (k )

M, M .

3.4. Methods summary We have analyzed the behavior of these methods in onedimensional case for 50 iterations.

The second way of calculating z R and 0.5 gives the best results. However, the third way of choosing can be used if we need to accelerate the algorithm. 3.2. Subgradient method Generally, the subgradient method looks like follows [19]: z ( k 1) z ( k ) k g ( k ) , g ( k ) F ( z ( k ) ) , where g ( k ) is any subgradient of F ( z ) in z ( k ) , k are the step lengths. g of
(k )

250

original image interpolated image conditional gradient subgradient projection gradient

64
250

66

68

70

72

74

76

78

80

is an element of subgradient set F ( z

(k )

)

F ( z)

in
(k )

z

(k )

if

it
(k )

satisfies

the

condition
200

F ( z) F ( z

) (g

(k )

,zz

) for all z . We use this
k

method for minimizing functional (2) with k 0 . This method is effective in two-dimensional case as well as in one-dimensional, but the disadvantage is that it needs calculation of regularization parameter , while the function is unknown. The function (C ) f ( x) f (log ) C( ) is non-increasing and close to linear function. We estimate x log by using dichotomy method. However, it requires to run the minimization of regularization functional (2) for several different , so the subgradient method is quite slow. 3.3. Projection subgradient method Projection subgradient method is used instead of simple subgradient method if a problem has a constraint z M . It

original image interpolated image conditional gradient subgradient projection gradient

150 28 30 32 34 36 38 40 42 44 46 48 50

Fig. 1. Numerical methods comparison in 1-D case.

Conditional gradient method shows good results on simple input data like step function, but it convergences very slowly on complex data even for bar function. So, it can be effectively used only for processing of small blocks. Regularization (subgradient) method (2) provides good results, but it requires pre-calculating regularization parameter, so this method is quite slow. Both conditional and subgradient methods converge to the solution of (1) if number of iterations tends to infinity. One-step projection gradient method is effective, but it never converges to the solution of (1). This method


smoothes edges but if the Gibbs phenomenon is low, then the difference between interpolated image and optimal image is small, and the error between optimal image and the result of projection gradient method is very low. Next, we have processed the test image set by these methods and calculated average PSNR values, which are shown in table 2. The results were different for different images. Note that subgradient method for global deringing is a solution for pure TV minimization problem (1). Global Local deringing deringing No processing 2 8 .3 8 Conditional gradient method 23.33 2 9 .2 4 (2nd way, 0.5 ) Fast conditional gradient 2 2 .1 7 2 9 .2 2 method(2nd way, 0 or 1) Subgradient method 2 8 .7 1 2 8 .6 4 Projection subgradient 2 8 .7 5 2 8 .6 8
Table 2. Results for test image set.

Image upsamling result by a modification of Lanczos interpolation method and post-processed image by the proposed method (2nd way conditional gradient method with = 0.5) is given in Fig. 2.

a)

b)

c)

d)

Fig. 2. Method results: a) low-resolution image; b) reference image; c) interpolated image; d)deringed image.

4. CONCLUSION New image deringing method for image interpolation using information on the TV from initial image has been proposed. It was found that local approach with conditional gradient method shows better results than pure TV approach. Experiments show high efficiency of the method for resampling post-processing. The corresponding free resampling software is available at http://imaging.cs.msu.su/software. The work was supported by RFBR grant 06-01-39006-_. 5. REFERENCES
[1] S.S. Yao, W.S. Lin, Z.K. Lu, E.P. Ong, and X.K. Yang, "Adaptive nonlinear diffusion processes for ringing artifacts removal on JPEG 2000 images," IEEE International Conference on Multimedia and Expo, Vol.1, pp.691-694, 2004. [2] Tao Chen, Hong Ren Wu, and Bin Qiu, "Adaptive Postfiltering of Transform Coefficients for the Reduction of Blocking Artifacts," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 11, No. 5, pp. 594-602, May 2001.

[3] Y. L. Lee, H. C. Kim, and H. W. Park, "Blocking Effect Reduction of JPEG Images by Signal Adaptive Filtering," IEEE Trans. on Image Proc., Vol. 7, No. 2, pp. 229-234, 1998. [4] Guangyu Wang, Tien-Tsin Wong, and Pheng-Ann Heng, "Deringing Cartoons by Image Analogies," ACM Transactions on Graphics, Vol. 25 , Issue 4, pp. 1360-1379, October 2006. [5] M. Beermann, A. Jalil, and J-R. Ohm, "Thresholded Weighted Median Filters for Ringing Reduction in Processed Images," IEEE 7th Workshop on Multimed. Sign. Proc., Shanghai, pp. 1-4, 2005. [6] Y-L. You, W. Xu, A. Tannenbaum, M. Kaveh, "Behavioral Analysis of Anisotrpic Diffusion in Image Processing," IEEE Trans. on Image Proc., Vol. 5, NO. 11, pp. 1539-1553, 1996. [7] Y. Li, and F. Santosa, "A Computational Algorithm for Minimizing Total Variation in Image Restoration," IEEE Trans. on Image Proc., Vol. 5, No. 6, pp. 987-995, June 1996. [8] Y-L. You, and M. Kaveh, "Ringing Reduction in Image Restoration by Orientation-Selective Regularization," IEEE Signal Proc. Letters, Vol. 3, No. 2, pp. 29-31, 1996. [9] L. Rudin, S. Osher, and E. Fatemi, "Nonlinear total variation based noise removal algorithms," Physica D, No. 60, pp. 259-268, 1992. [10] S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, 1999. [11] S. Farsiu, M.D. Robinson, M. Elad, and P. Milanfar, "Fast and Robust Multi-Frame Super-Resolution," IEEE Trans. on Image Proc., Vol. 13, No. 10, pp. 1327 -1344, June 2003. [12] A.N. Tikhonov, and V.Y. Arsenin, Solutions of Ill Posed Problems, WH Winston, Washington DC, 1977. [13] V.K. Ivanov, "On linear ill-posed problems," Dokl. Acad. Nauk SSSR, Vol. 145, pp. 270-272, 1962 (in Russian). [14] V.V. Vasin, "Relationship of several variational methods for the approximate solution of ill-posed problems," Math Notes, Vol. 7, pp. 161-166, 1970. [15] J.R. Price., and M.H. Hayes, "Resampling and reconstruction with fractal interpolation functions," IEEE Signal Processing letters, Vol. 5, No. 9, pp. 228-230, Sep 1998. [16] A. Nasonov, A.S. Krylov, and A. Lukin, "Post-processing by Total Variation Quasi-solution Method for Image Interpolation," Graphicon'2007 Conf. proc., Moscow, pp. 178-181, 2007. [17] A.N. Tikhonov, A.V. Goncharsky, V.V. Stepanov, and A.G. Yagola, Regularizing algorithms and apriori information, Nauka, Moscow, 1983 (in Russian). [18] A. Lukin, A.S. Krylov, and A. Nasonov, "Image Interpolation by Super-Resolution," Graphicon'2006 Conf. proc., Novosibirsk, pp. 239-242, 2006. [19] S. Boyd, L. Xiao, and A. Mutapcic, "Subgradient methods," Lect. notes of EE392o, Stanford University, 2003. [20] P.L. Combettes, and J.-C. Pesquet, "Image restoration subject to a total variation constraint," IEEE Transactions on Image Processing, Vol. 13, Issue 9, pp. 1213-1222, Sept. 2004.