Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cmc.msu.ru/pub/2015.ACIVS.Umnov_Krylov_Nasonov.SparseDeringing.en.pdf Дата изменения: Tue Aug 25 19:34:43 2015 Дата индексирования: Sat Apr 9 22:42:14 2016 Кодировка:

Ringing Artifact Suppression using Sparse Representation
Alexey V. Umnov, Andrey S. Krylov, and Andrey V. Nasonov
Laboratory of Mathematical Methods of Image Processing, Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University kryl@cs.msu.ru

Abstract. The article refers to the problem of ringing artifact suppression. The ringing effect is caused by high-frequency information corruption or loss, it appears as waves or oscillations near strong edges. We propose a novel method for ringing artifact suppression after Fourier cut-off filtering. It can be also used for image deringing in the case of image resampling and other applications where the frequency loss can be estimated. The method is based on the joint sparse coding approach. The proposed method preserves more small image details than the stateof-the-art algorithms based on total variation minimization, and outperforms them in terms of image quality metrics. Keywords: ringing artifact, ringing suppression, sparse coding

1

Intro duction

Gibbs phenomenon also known as ringing effect appears as waves or oscillations near strong edges. An example of ringing effect is shown in Fig. 1. The source of the ringing effect is high-frequency information corruption or loss [9]. It can be the result of many image processing algorithms and applications that change the high-frequency information, i.e. image and video compression, deblurring, resampling, denoising, and in analog video [16]. There are many papers that consider the problem of ringing effect detection and suppression in JPEG and JPEG2000 images [7, 11]. On the other hand there are only few works that pose the problem of general ringing detection and suppression [13, 17, 23, 24]. Suppression algorithms are based on the connection of ringing effect with total variation [9], and total variation minimization proposed for image enhancement in [21]. However these methods do not distinguish between ringing oscillations and small image details, thus these details are usually corrupted. In this work we present a novel method for ringing suppression after Fourier cut-off filtering. It can be also used for image deringing in the case of image resampling and other applications where the frequency loss can be estimated. The method is based on sparse representation approach, widely used in many image processing tasks [3], including image quality enhancement problems. The


proposed method is based on the joint sparse coding method, which was previously used for image deblurring and image super-resolution [25]. The joint sparse coding method is described in detail in subsection 2.2.

Fig. 1. Example of the ringing effect: reference image (left) and image with ringing effect (right).

2
2.1

Ringing Suppression
Problem Formulation

Consider the ringing effect produced by high frequency cut-off filter Rd which removes all the frequencies in the Fourier domain outside the circular mask with radius d = 21 centered at zero frequency point: d Rd ( I ) = F
-1

(F (I ) · ld ),

where F and F -1 are Fourier transform and inverse Fourier transform respectively, ld is the mask 2 2 1, if x + y d , ld (x , y ) = 2 2 0, if x + y > d . This filter produce ringing effect with oscillation width equal to d. Let us denote the original image as ys and the image with ringing effect as yr . Then


yr = Rd (ys ). Given yr , the problem of ringing suppression is to find ys so that ys ys . ^ ^ The problem is ill-posed, as the solution is not unique. 2.2 Joint Sparse Co ding

In order to solve the problem of ringing suppression we use the joint sparse coding approach introduced by Yang et al. [25]. We assume that the original image can be sparsely represented in some dictionary Ds with sparsity : ys = Ds x, x
0

.

We also assume that it is possible to recover the original sparse codes from the image with ringing effect. Therefore the image with the ringing effect can be sparsely represented in some dictionary Dr with the same codes: yr = Dr x. If dictionaries Ds and Dr , and are known, the ringing suppression procedure is done as follows. Given the image with the ringing effect yr , the sparse representation problem with dictionary Dr is solved: x = arg min yr - Dr x 2 , ^
x

s.t.

x

0

.

The vector x is the estimation of the sparse representation of the both ys ^ and yr with the dictionaries Ds and Dr respectively. Thus it can be used to get the original image estimation: ys = Ds x. ^ ^ However in the general case the dictionaries are not known so it is necessary to estimate them using dictionary learning procedure. This can be done using the training set of images with the ringing effect and the corresponding original images. Denote Ys as the matrix with original images as columns and Yr as the matrix with the corresponding images with ringing effect as columns. Then the dictionary learning problem can be formulated as follows:
Ds ,Dr ,X

min ·

Ys - Ds X

2 F

+ Yr - Dr X

2 F

,

s.t.

X

0,inf

,
n

where the as follows:

0,inf

norm for the matrix X with columns x1 , . . . , x

is defined

X So the X -sparse.
0,inf

0,inf

= max

i=1,...,n

xi 0 .

condition effectively means that all representations are


Denoting Y= and D= the problem can be rewritten as
D ,X

Y Y D D

s r

s r

,

min Y - D X

2 F

,

s.t.

X

0,inf

.

This problem can be solved using any sparse dictionary learning algorithm. In our work we use the K-SVD algorithm [1] for dictionary learning and OMP algorithm [10] for sparse coding. 2.3 Ringing Suppression Metho d

The proposed method requires a set of images for learning. We split all images into overlapping 6 в 6 blocks and process each block separately. The images from the learning set are used to create a set of corresponding original blocks and blocks with ringing effect. Then the joint dictionary learning procedure is applied to this set of samples. The ringing suppression method uses learned joint dictionaries to get sparse codes of the blocks with ringing artifact and then to get the original block estimation from these codes. The resulting full image is composed from the estimated blocks by averaging the values in the overlapping areas. In order to improve the ringing suppression performance we add several modifications to the joint sparse coding approach. Regularization In our preliminary experiments we have found that the method performs better when different sparsity parameter is used in learning and testing phase (learn = 10 and test = 2). We suppose that it is caused by the fact that the blocks with ringing effect are less informative than the ringing free blocks. Thus in the testing phase (when the method builds the representation only from the block with ringing) stronger regularization makes the method more stable. Extending dictionary by rotations Edges play the most important role in the ringing suppression problem because ringing effect is the most noticeable near strong edges. We have also discovered that some blocks with edges are not represented well enough in the testing phase due to absence of edges with approximately the same direction in the training set. In order to improve the performance for these blocks we extend the dictionaries by their rotated versions after the learning process. Denote the Rota as the operator that rotates all atoms in the dictionary by a°, then the extended dictionaries are built as follows (here base base Ds , Dr are the dictionaries obtained in the dictionary learning phase):


Ds = D

base s

; Rot90 (D

base s

); Rot180 (D

base s

); Rot270 (D

base s

)

Dr = D

base r

; Rot90 (D

base r

); Rot180 (D

base r

); Rot270 (D

base r

)

We use only these three rotations (90°, 180°, 270°) because they can be applied to the square images without introducing interpolation errors. Postpro cessing The joint sparse coding approach provides good results in most parts of the image, but the total variation minimization approach [17] works better for edges. The total variation deringing method is formulated as the minimization problem I
R

= arg min I - I
I

2 02

+ T V (I ),

(1)

where I0 is the given image with ringing effect, is the regularization parameter that controls the strength of ringing suppression, T V (I ) is the total variation of the image I : T V (I ) =
x,y

| I (x, y )|.

In order to improve the performance of the proposed method we merge the results of the joint sparse coding deringing and the results of the total variation minimization deringing. Denote the image obtained by joint sparse coding deringing as Isc (x, y ), the image obtained by total variation minimization as Itv (x, y ) and the distance from the nearest edge as (x, y ) (see below). Then the final image is constructed as follows: I (x, y ) = I tv (x, y ), I sc (x, y ), if (x, y ) 3; else.

Thus the values on the edges are taken from the total variation minimization deringing method, and other values are taken from the joint sparse coding deringing method. The set of edge pixels is constructed by Canny edge detection algorithm [2]. Then edge masking is applied to remove ringing oscillations and textures from the edge pixel set. We use edge masking approach from [14, 15] and take only the edge pixels that match the condition g (x0 , y0 ) > max g (x, y )((x - x0 )2 + (y - y0 )2 ),
x,y 1 where g (x, y ) is the gradient modulus at pixel (x, y ), (d2 ) = 2 exp - 2d 2 , is the parameter of Canny edge detection algorithm. We use = 2. The distance to the nearest edge is then calculated using eucludean distance transform [4].
2


3

Evaluation

We test our method using images from the MMIP Ringing Database [12]. This database uses the reference images from TID [20] and LIVE [22] databases and contains images with modeled ringing effect produced by different image processing methods. A subset of images containing strong edges is taken for the evaluation of the proposed algorithm. For dictionary learning, we use 5 images (avion, bikes, boats, house, lighthouse) with ideal ringing effect produced by cut-off filter. Dictionaries are learned individually for each ringing parameter d. The performance of the proposed algorithm is analyzed using images with ringing effect produced by cut-off filter and resampling algorithms. A weak white noise is also added to the test images in order to model the real ringing effect. We compare the proposed method with the method based on total variation minimization (1) with parameter maximizing the target metric. SSIM metric is used for measuring the performance of ringing suppression algorithms. The comparison of the proposed method with total variation deringing is shown in Fig. 2 and Fig. 3. Both the proposed method and the method based on the total variation minimization suppress almost all ringing effect. Unlike the total variation minimization method, the proposed method preserves most of the small details. The proposed method is also able to reduce aliasing effect and make the edges smoother. Numerical results for images with ringing effect produced by cut-off filter with d = 2 and d = 2.5 are shown in Table 1 and Table 2 respectively. The results of ringing suppression after resampling with a factor of 2 using regularization-based algorithm [8] are shown in Table 3. We base on the fact that for the problem of image resampling the ringing parameter d equals to the scale factor [14]. For the images 'barbara' and 'clown' from Table 3, the proposed method does not show satisfactory results in the areas containing a lot of parallel lines due to texture corruption during downsampling process. The proposed algorithm takes d as the input parameter and assumes that the input image contains ringing effect. Application of the proposed method to images without ringing effect results in edge and texture smoothing, and the edge width [18] of sharp edges becomes equal to d.

4

Conclusion

A novel ringing suppression method has been presented. Its advantages are fine detail preserving including textures, almost all ringing oscillations removal and aliased edge smoothing. The open problems are automatic choosing the parameter d and testing on images with different sources of ringing artifacts. Acknowledgements. The SciPy [6], Matplotlib [5] and Scikit-learn [19] Python libraries were used in this work. The work was supported by the Russian Science Foundation grant no. 1411-00308.


a

b

c

d

a

b

c

d

Fig. 2. Ringing suppression examples (d = 2) near edges for cameraman and plane images with ringing effect modeled by cut-off filter. a) Image with ringing, b) ringing suppression using total variation minimization, c) ringing suppression using the proposed method, d) reference image.


a

b

c

d

a

b

c

d

Fig. 3. Ringing suppression examples (d = 2) in areas with small details for caps and paintedhouse images. a) Image with ringing, b) ringing suppression using total variation minimization, c) ringing suppression using the proposed method, d) reference image.


Table 1. Results of the ringing suppression (d = 2) after high frequency cut-off, SSIM. Best value in each row is highlighted. The overall average value is given in the last row. Image name cameraman caps house2 peppers plane barbara clown lena lighthouse2 mandarin monarch paintedhouse parrots Average Ringing TV-based Prop osed 0.8924 0.9162 0.9180 0.9319 0.9541 0.9560 0.9282 0.9490 0.9512 0.9297 0.9482 0.9509 0.9301 0.9491 0.9497 0.8223 0.8307 0.8318 0.9223 0.9360 0.9369 0.9400 0.9555 0.9581 0.9030 0.9182 0.9186 0.9260 0.9435 0.9447 0.9504 0.9748 0.9753 0.8884 0.8988 0.8998 0.9491 0.9725 0.9735 0.9164 0.9343 0.9357

Table 2. Results of the ringing suppression (d = 2.5) after high frequency cut-off, SSIM. Best value in each row is highlighted. The overall average value is given in the last row. Image name cameraman caps house2 peppers plane barbara clown lena lighthouse2 mandarin monarch paintedhouse parrots Average Ringing TV-based Prop osed 0.8600 0.8863 0.9009 0.9148 0.9403 0.9489 0.9144 0.9384 0.9453 0.9178 0.9394 0.9460 0.9104 0.9316 0.9395 0.7987 0.8097 0.8202 0.8975 0.9129 0.9198 0.9239 0.9423 0.9509 0.8684 0.8857 0.8990 0.8918 0.9118 0.9225 0.9362 0.9621 0.9662 0.8462 0.8584 0.8739 0.9378 0.9632 0.9677 0.8937 0.9140 0.9231


Table 3. Results of the ringing suppression after resampling (d = 2), SSIM. Best value in each row is highlighted. The overall average value is given in the last row. Image name cameraman caps house2 peppers plane barbara clown lena lighthouse2 mandarin monarch paintedhouse parrots Average Ringing TV-based Prop osed 0.9200 0.9162 0.9276 0.9591 0.9541 0.9626 0.9489 0.9490 0.9555 0.9499 0.9482 0.9527 0.9510 0.9491 0.9580 0.8587 0.8307 0.8533 0.9294 0.9360 0.9298 0.9576 0.9555 0.9594 0.9218 0.9182 0.9305 0.9478 0.9435 0.9550 0.9739 0.9747 0.9748 0.9087 0.8988 0.9185 0.9761 0.9725 0.9773 0.9387 0.9343 0.9427

References
1. Aharon, M., Elad, M., Bruckstein, A.: K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation. Signal Processing, IEEE Transactions on 54(11), 4311­4322 (2006) 2. Canny, J.: A computational approach to edge detection. IEEE Trans. PAMI 8, 679­714 (1986) 3. Elad, M., Figueiredo, M.A., Ma, Y.: On the role of sparse and redundant representations in image processing. Proceedings of the IEEE 98(6), 972­982 (2010) 4. Fabbri, R., da F. Costa, L., Torelli, J.C., Bruno, O.M.: 2D Euclidean distance transforms: A comparative survey. ACM Computing Surveys 40(1), 2:1­2:44 (2008) 5. Hunter, J.D.: Matplotlib: A 2D graphics environment. Computing in Science & Engineering 9(3), 90­95 (2007) 6. Jones, E., Oliphant, T., Peterson, P., et al.: SciPy: Open source scientific tools for Python (2001­), http://www.scipy.org/, [Online; accessed 2015-04-30] 7. Liu, H., Klomp, N., Heynderickx, I.: A perceptually relevant approach to ringing region detection. IEEE Transactions on Image Processing 19(6), 1414­1426 (2010) 8. Lukin, A., Krylov, A., Nasonov, A.: Image interpolation by super-resolution. In: 16th International Conference Graphicon'2006. pp. 239­242. Novosibirsk Akademgorodok, Russia (July 2006) 9. Mallat, S.: A Wavelet Tour of Signal Processing. Academic Press (1999) 10. Mallat, S.G., Zhang, Z.: Matching pursuits with time-frequency dictionaries. Signal Processing, IEEE Transactions on 41(12), 3397­3415 (1993) 11. Marziliano, P., Dufaux, F., Winkler, S., Ebrahimi, T.: Perceptual blur and ringing metrics: application to JPEG2000. Signal Processing: Image Communication 19, 163­172 (2004) 12. MMIP Lab: MMIP Ringing Database (2015), http://imaging.cs.msu.ru/en/ research/ringing/database


13. Mosleh, A., Langlois, J.P., Green, P.: Image deconvolution ringing artifact detection and removal via psf frequency analysis. Lecture Notes in Computer Science 8692, 247­262 (2014) 14. Nasonov, A.V., Krylov, A.S.: Finding areas of typical artifacts of image enhancement methods. Pattern Recognition and Image Analysis 21(2), 316­318 (2011) 15. Nasonov, A.V., Krylov, A.S.: Image enhancement quality metrics. 21-th International Conference on Computer Graphics GraphiCon'2011 pp. 128­131 (2011) 16. Nasonov, A.V., Krylov, A.S.: Edge quality metrics for image enhancement. Pattern Recognition and Image Analysis 22(1), 346­353 (2012) 17. Nasonov, A.V., Krylov, A.S.: Adaptive image deringing. In: Proceedings of GraphiCon2009. pp. 151­154 (2009) 18. Nasonova, A.A., Krylov, A.S.: Determination of image edge width by unsharp masking. Computational Mathematics and Modeling 25(1), 72­78 (2014) 19. Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 12, 2825­2830 (2011) 20. Ponomarenko, N., Lukin, V., Zelensky, A., Egiazarian, K., Carli, M., Battisti, F.: TID2008-a database for evaluation of full-reference visual quality assessment metrics. Advances of Modern Radioelectronics 10(4), 30­45 (2009) 21. Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259­268 (1992) 22. Sheikh, H.R., Wang, Z., Cormack, L., Bovik, A.C.: Live image quality assessment database rel. 2 (2005) 23. Sitdikov, I.T., Krylov, A.S.: Variational image deringing using varying regularization parameter. Pattern Recognition and Image Analysis 25(1), 96­100 (2015) 24. Umnov, A.V., Nasonov, A.V., Krylov, A.S., Yong, D.: Sparse method for ringing artifact detection. In: Signal Processing (ICSP), 2014 12th International Conference on. pp. 662­667. IEEE (2014) 25. Yang, J., Wright, J., Huang, T.S., Ma, Y.: Image super-resolution via sparse representation. Image Processing, IEEE Transactions on 19(11), 2861­2873 (2010)