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

EDGE-PRESERVING NONLINEAR ITERATIVE IMAGE RESAMPLING METHOD Andrey S. Krylov, Alexey S. Lukin, Andrey V. Nasonov Laboratory of Mathematical Methods of Image Processing Faculty of Computational Mathematics and Cybernetics, Moscow Lomonosov State University kryl@cs.msu.ru
ABSTRACT In this paper, an edge-preserving nonlinear iterative regularization-based image resampling method for a single noise-free image is proposed. Several aspects of the resampling algorithm are investigated: choice of discrepancy and regularization norms, improvements of convergence speed using edge-directional steepest-descent method and patchbased details synthesis. A model of a downsampling operator based on a camera observation model is considered. Index Terms-- Image interpolation, regularization, edgedirectional, details synthesis, super-resolution, resampling. 1. INTRODUCTION Image interpolation (or resampling) is a well studied problem in image processing. Despite of the fast increase of resolution of modern image sensors, image interpolation remains important for high-quality conversion of legacy formats, e.g. when showing a standard-definition video on HDTV. Linear interpolation methods are typically treating images as band-limited signals and separate 2D interpolation into a set of 1D interpolation problems [1]. The interpolated signal is constructed as a convolution of the sampled signal with kernel functions, such as a box filter ("nearest neighbor interpolation"), a triangular filter ("bilinear interpolation"), a cubic spline, or a sinc filter. Failing to consider the structure of the image, linear methods suffer from 3 common artifacts: blur, jagged edges (aliasing), and ringing. The shape of the interpolation kernel defines the balance between these 3 artifacts; cubic interpolation is a popular balanced choice. Simplest nonlinear interpolation methods explicitly [2] or implicitly [3] adapt the interpolation to the local image data in order to prevent blurring across edges and encourage interpolation along the edge direction. Such methods are effective in reduction of edge jaggedness. A class of super-resolution methods [4] considers image interpolation as the inverse problem Az = u, where z
The work was supported by federal target program "Scientific and scientific-pedagogical personnel of innovative Russia in 2009-2013" and RFBR grant 09-07-92000-HHC.

is the unknown high-resolution image, u is the known lowresolution image, and A is the downscaling operator typically consisting of a low-pass filtering followed by decimation. This problem is ill-posed and is typically solved by iterative methods with regularization [5]. Learning-based (or statistical) approaches to super-resolution are mapping low-resolution image patches to the database of high-resolution image patches trained on a set of images [6]. In this paper, we are studying some modifications of iterative regularization methods for resampling and propose a new method combining iterative regularization-based resampling with a patch-based details synthesis. Our details synthesis algorithm is not based on learning, but instead exploits a similarity of the image structure in different scales. 2. REGULARIZATION-BASED INTERPOLATION We pose the image interpolation problem as the inverse problem to the image downsampling problem. The inverse problem is ill-posed. We are using a method derived from Tikhonov regularization method [7] to solve this problem. 2.1. Image downsampling To pose the image downsampling problem, we are using an observation model. The size of a camera sensor is non-zero. Every sensor averages the intensity of the observed continuous image I (x, y ). This averaging is represented by a point spread function (PSF). The resulting intensity of the discrete image z obtained by camera can be calculated as a convolution with the PSF followed by sampling. Every camera has its own PSF. The observed image also suffers from a variety of distortions such as camera lens blur, motion blur, sensor noise. For simplicity, we represent all these effects by a single Gaussian filter. Under these assumptions, we model the obtained image as z = I G , (1) where G is a Gaussian filter having radius . Usually, we estimate Gauss radius as the pixel size multiplied by a value


in the range [0.4, 0.5]. Lower radius values result in aliasing, higher values blur the image. We have defined the observation model. Now we propose a method of image downsampling by q times using the observation model. The problem of image downsampling is to construct a low-resolution discrete image u for shrunk image J (x, y ) = I (q x, q y ). We replace this problem with constructing a discrete image v from the original image I using a camera with q times bigger pixel size. The image v is calculated as v = I Gq . We do not know the initial image I , but we know the image z and the parameter (1). We calculate v from z as: v = I Gq = I G G
q 2 -1

Fig. 1. The reference high-resolution image. and BTV radiuses p to find the parameters that provide better edge preservation and overall image quality. To estimate the quality of regularization-based image resampling, several reference images were downsampled by a certain factor. Then the downsampled images were interpolated by the same factor and compared with the reference images using the PSNR metrics. The regularization parameter was chosen to maximize the PSNR. We used reference images with strong flat edges without textured areas like Fig.1. In this case, PSNR can be used as a reasonable measure of image quality. Additional experiments included photographic images. We have analyzed scale factors 2 and 4 in our experiments. The considered norms for the discrepancy term were n = 1, 2 and 3. When using n > 3, the interpolated image contains a lot of impulse noise. Norms m = 1 and 2 were used in the stabilizer. The PSNR values for the test image from Fig.1 are shown in Table 1. Norms nm 11 21 31 12 22 32 Upsampling by 2 p=1 p=2 30.95 30.37 31.81 31.30 28.78 27.28 26.30 25.37 26.54 25.21 25.24 24.04 Upsampling p=1 p=2 20.71 21.46 20.82 21.67 19.56 19.78 19.33 19.22 19.43 18.58 18.52 18.52 by 4 p=3 21.48 21.76 19.65 17.64 17.24 18.43

= z G

q 2 -1

,

because G1 G2 = G2 +2 . 1 2 Finally, the downsampling process takes the form u = Az = DH z , where H is the convolution with a Gaussian filter G D is the decimation operator. 2.2. Inverse problem The problem of image upsampling is an inverse problem to the image downsampling problem (2). It consists in finding z for known low-resolution image u: z=A 2.3. Regularization In the continuous case, the problem (3) is ill-posed, because H -1 is unbounded and produces unstable solutions. In the discrete case, the decimation operator D cannot be inverted, while operator H -1 is ill-conditioned. To make the problem well-posed, we are using the regularization method [5]: zR = arg min ( Az - u
z n n -1

(2)
q 2 -1

,

u=H

-1

D

-1

u

(3)

+ [z ])

(4)

Here the first term is called discrepancy, [z ] is the stabilizer, > 0 is the regularization coefficient, and the norm is defined as z n= |zi,j |n n
i,j

Following [4], we are using a bilateral total variation (BTV) functional as a stabilizer [z ] =
-ps,tp s t where = 0.8, Sx and Sy are shift operators along x and y axis by s and t pixels respectively, p is the BTV radius. In this work, we analyze the results of image interpolation for different discrepancy norms n, stabilizer norms m

Table 1. PSNR values (dB) for different discrepancy norms n, stabilizer norms m, BTV radiuses p and scale factors (higher PSNR is better). The best results are produced with n = 2, m = 1; this correlates with the perceived image quality. Results for the discrepancy norm n = 1 suffer from ringing artifacts. For norms n = 2 and n = 3 the results are close, but the minimization problem for the case n = 3 requires more iterations. Use of the stabilizer norm m = 2 results in ringing artifacts and edge blurring, while the norm m = 1 produces sharp edges. The results for the upscaling factor 2 are shown in



|s|+|t|

z-S

st x Sy

z

m m

,


Fig.2

optimal. 2.4. Minimization To minimize the regularization functional (4) for n = 2 and m = 1, we are using the subgradient method [8] with a fixed step size: zk = zk - k 2H T DT (DH z - u) +
- (I - Sx s S -t y st )sign(zk - Sx Sy zk )

+1

n = 1, m = 1, PSNR=30.95

n = 1, m = 2, PSNR=26.30

·
-ps,tp



|s|+|t|

(5)

Here sign(z ) is a per-element sign function, DT is the zero-padding upsampling operation, and H T = H due to the filter symmetry. The initial image z0 is approximated using non-iterative interpolation methods. The choice of step values k is discussed in [5]. 3. IMPROVEMENTS OF CONVERGENCE SPEED Minimization of the functional (4) is an iterative process that rarely converges exactly to the global minimum. And even if the global minimum is achieved, there can be a substantial difference between the solution and the ground-truth highresolution image. In order to minimize this difference, we suggest two heuristic methods: "edge-directional" modification of the steepest descent method, and patch-based details synthesis. edge-dir. descent, m = n = 1 PSNR = 32.50 edge-dir., details synth. PSNR = 33.55 3.1. Edge-directional steepest descent method Each iteration of the steepest descent method (5) consists of the following steps: 1. The current solution is downscaled: DH zk , 2. This downscaled image is compared against the known low-resolution image: sign(DH zk - u) (for n = 1), or (DH zk - u) (for n = 2), 3. The resulting difference image is upscaled: H T DT sign(DH zk - u) (for n = 1), or 2H T DT (DH zk - u) (for n = 2), and subtracted from the current approximation zn , 4. The regularization term is subtracted from the current approximation. At the 3rd step of each iteration the difference image is upsampled by zero-padding DT and filtered by the low-pass filter H T . This filter is linear and space-invariant. Our heuristics modifies this stage of the iterative process to enhance edge-sensitivity of the low-pass filter. The filter H T is replaced with a locally adaptive interpolation that prevents blurring of the upsampled correction image DT sign(DH zk - u) across edges. Interpolation weights at each point are calculated by evaluating several directional

n = 2, m = 1, PSNR=31.81

n = 2, m = 2, PSNR=26.54

Fig. 2. The results of regularization-based image interpolation (4) for different norms for the factor of 2. Considering the results, we are making a conclusion that optimal norms for edge preservation are n = 2, m = 1. For the case of multi-frame super-resolution [4], the minimization problem (4) with the norms n = 1 and m = 1 was used to perform a robust mean estimation. The second part of the experiment was the analysis of influence of BTV radius p on the results of interpolation. The higher the radius is, the wider is the smoothing area, and the edges are expected to be less aliased. Due to high computational complexity for big p, we only analyzed the cases p = 1, 2, 3. For the factor of 2, the results are similar for all p, and the value p = 1 can be used. For the factor of 4, for p = 2 the method gives better results than for p = 1. For p = 3, the results do not differ significantly from the case p = 2, so the value p = 2 is


derivatives of the image z0 . So, the operator H T DT is replaced with some well-known non-iterative edge-directional interpolation method. Additionally, the initial approximation z0 is also constructed by some edge-directional interpolation of the image u, such as NEDI [3]. In Fig.3, curves 5 and 6 demonstrate the improvement of PSNR between the upscaled image and the ground-truth high-resolution image as the result of the described heuristics.

doing several minimization iterations after applying the details synthesis. This "corrects" the resulting image by minimizing the discrepancy term. In our implementation, the block size is set to N = 4, and the search radius is set to K = 7. The amount of block overlap is the quality/complexity tradeoff. In Fig.3, curve 7 shows that the use of this details synthesis algorithm improves the PSNR of the resulting image with regard to the ground-truth high-resolution image. 4. CONCLUSION In this work, we have proposed the edge preserving nonlinear regularization-based iterative image resampling method with improvements of convergence speed. Choice of the regularization method parameters depends on the image comparison metrics. For the test images used in the paper, the PSNR metrics correlates well with the perceived image quality. Nevertheless, the choice of optimal parameters for the adaptive regularization method in a general case is still a challenging problem and requires additional investigation. We have prepared a web-page with additional sample images and a demo software implementing the described interpolation methods: http://imaging.cs.msu.ru/reg/. 5. REFERENCES [1] P. Thevenaz, T. Blu, and M. Unser, "Interpolation revisited," IEEE Trans. on Medical Imaging, vol. 19, no. 7, pp. 739­758, 2000. [2] S. Yuan, M. Abe, A. Taguchi, and M. Kawamata, "High accuracy wadi image interpolation with local gradient features," Proc. of 2005 Int. Symposium on Intelligent Signal Proc. and Comm. Systems, pp. 85­88, 2005. [3] X. Li and M. Orchard, "New edge-directed interpolation," IEEE Trans. on Image Processing, vol. 10, no. 10, pp. 1521­1527, 2001. [4] S. Farsiu, D. Robinson, M. Elad, and P. Milanfar, "Fast and robust multi-frame super-resolution," IEEE Trans. on Image Processing, vol. 13, no. 10, pp. 1327­1344, 2004. [5] A. Lukin, A. Krylov, and A. Nasonov, "Image interpolation by super-resolution," Proceedings of GraphiCon'2006, pp. 239­242, 2006. [6] W. T. Freeman, T. R. Jones, and E. C. Pasztor, "Examplebased super-resolution," IEEE Computer Graphics and Applications, vol. 22, no. 2, pp. 56­65, 2002. [7] A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-Posed Problems, WH Winston, Washington DC, 1977. [8] S. Boyd, L. Xiao, and A. Mutapcic, Subgradient methods, Lecture notes of EE392o, Stanford University, 2003.

Fig. 3. Improvement of PSNR after proposed heuristics (ED -- edge directional upsampling in steepest descent method, DS -- patch-based details synthesis).

3.2. Patch-based details synthesis A number of existing learning-based methods exist for image upsampling [6]. They are adding a missing high-frequency content to the upscaled image by searching the database of patches, which is obtained from the training set of images. We propose a similar algorithm, but without the learning stage. It exploits the property of self-similarity of many image features across different scales. As with other methods, we are breaking the image zk into a set of overlapping N в N patches. For each patch, we are looking for its closest match in the image u, without any scaling. The match is searched in a small surrounding area: ±K pixels. The best found match is separated into high frequencies and low frequencies by a 3 в 3-pixel high-pass filter. The obtained high frequencies of u are mixed into the corresponding patch of zk using a Hann weighting window that attenuates inter-patch discontinuities. The mixing gain is inversely proportional to the patch matching error. This ensures that only well-matched patches find their way into the resulting image. The described details synthesis algorithm can be applied once or several times throughout the process of iterations (5). Since this algorithm may create some artifacts, we are always