The Vault

Joint edge-directed interpolation and adaptive sharpening filter
Research Paper / Feb 2014

Joint edge-directed interpolation and adaptive sharpening filter Rahul Vanam, Yan Ye, and Serhad Doken InterDigital Communications, Inc., 9710 Scranton Road, San Diego, CA 92121 E-mail: {rahul.vanam, yan.ye, serhad.doken}@interdigital.com Abstract—In this paper, we present a joint filter that upsamples and adaptively sharpens a video/image simultaneously. The joint filter has been designed by combining a low complexity edge- directed interpolator with an adaptive Laplacian of Gaussian (LoG) filter. The joint filter yields sharp upsampled images, and is demonstrated to have lower computational complexity and similar visual quality when compared to using separate upsampling and sharpening filters. Index Terms—post-processing, blurriness, video resize, sharp- ening filter, Sobel operator. I. INTRODUCTION With the advances of wireless networks and the increasing popularity of video-capable mobile devices such as tablets and smartphones, consumption of digital video content has been increasing rapidly. Video hosting websites such as YouTube and Dailymotion often stores the same video content in a va- riety of bit rates and resolutions. When a user requests a certain video over wireless networks, usually the lower resolution and lower bit rate version is delivered due to bandwidth constraints. A commonly noticed artifact in these videos is blurriness. Further, if the encoded video has a resolution lower than the screen resolution on the device, the video is usually upsampled before being displayed to fit the whole screen. Upsampling can further enhance the visibility of the blurriness in the video, and the blurriness can be reduced using a sharpening filter. Since mobile devices have power and computation MIPS constraints, low complexity upsampling and sharpening filters are needed to enable real-time video playback with good visual quality. Much prior work in upsampling and sharpening already exists. For upsampling, it has been shown that edge-directed interpolation (EDI) reduces blurriness around object edges in the upsampled image [1-8]. Li et al. performed EDI by using the geometric duality principle for interpolating high resolution covariance from its low resolution counterpart [2]. In [3], EDI is performed by modeling the interpolated image as a Markov random field. Yang et al. present an explicit EDI scheme, where local gradient magnitudes and angles are used during interpolation [4]. A graphic processor unit friendly EDI scheme was presented in [5]. In [6], the downsampled image is first divided into diagonal and non-diagonal direction images, each of which is interpolated in one of the three specified directions using 1D polynomial interpolation. Zhang and Wu obtained two directional estimates of the missing pixel and fused them via linear minimum mean squared error estimation [7]. Cha and Kim used a modified bilinear method for interpolation, where the error is amended by using the interpolation error theorem in an edge-adaptive fashion [8]. Sharpening filters are used to enhance the edges in an image. Adaptive sharpening filters are often preferred since they do not sharpen noise and flat regions [9-11]. Kim et al. modified the unsharp masking filter to use positive weights for edges, and negative weights for noise-like components [9]. Kotera et al. used a histogram of second-order gradients to determine the strength of an edge, and then applied a suitable Gaussian derivative filter to sharpen the edges [10]. Kobayashi et al. proposed an approach to classify edges as long/short edges for adaptive sharpening [11]. Most of the prior work mentioned above design the up- sampling and sharpening filters separately. In this paper, we propose a joint filter for simultaneous edge-directed interpo- lation and sharpening. The joint filter preserves the fidelity of the edges and enhances them in the upsampled frame, while reducing the overall computational complexity. The rest of this paper is organized as follows. Section II describes the design of our joint filter. Results are presented in Section III, and we conclude in Section IV. II. SIMULTANEOUS EDGE-DIRECTED INTERPOLATION AND SHARPENING FILTER The framework of our joint filter is illustrated in Figure 1. A modified Sobel operator is applied to the original image pixels to obtain the local gradient angle and magnitude, which are used to adapt the joint filter for simultaneous EDI and adaptive sharpening. In this section, we describe the modified Sobel operator. Since the joint filter has been designed by combining EDI and Laplacian of Gaussian (LoG) adaptive sharpening filter, we will first describe the two filters before describing the joint filter. Fig. 1. Proposed joint filter framework. Fig. 2. Illustration of a pixel grid. Squares and circles represent original and interpolated pixels, respectively. Labels ‘A’, ‘B’, and ‘C’ correspond to the center, row, and column interpolated pixels, respectively. The arrows point to the original pixels used during interpolation. A. Modified Sobel operator The interpolated pixels are categorized into center, row, and column pixels based on their location in the pixel grid, and they are labeled as ‘A’, ‘B’, and ‘C’, respectively, in Figure 2. Our modified Sobel operators operate on rectangular array of pixels for computing the horizontal and vertical gradients (∆x and ∆y) for the three pixel categories, and are defined as follows GcenterX = [ −1 1 −1 1 ] ; GcenterY = [ 1 1 −1 −1 ] GrowX =  −1 1−2 2 −1 1  ; GrowY =  1 10 0 −1 −1  (1) GcolX = [ −1 0 1 −1 0 1 ] ; GcolY = [ 1 2 1 −1 −2 −1 ] where suffixes X and Y , represent horizontal and vertical operators, respectively. The gradient magnitude G, and angle θ are computed as follows G = |∆x|+ |∆y|, θ = tan−1(∆y/∆x). (2) B. Edge-directed interpolation Our EDI has been designed for upsampling a video by two in both dimensions. The coefficients and direction of interpolation of our EDI are determined by the gradient angle and magnitude computed in Equation (2). The pixel to be interpolated is classified as an edge pixel, if G ≥ T , where T is a heuristically determined threshold. If the gradient G < T , or if either ∆x or ∆y is zero, then interpolation is performed by averaging the nearest neighboring pixels as follows based on the pixel category: center pixel A′ = (b2 + b3 + c2 + c3)/4, row pixels B′ = (b0 + b1)/2, and column pixels C ′ = (a2 + b2)/2, (3) Fig. 3. Illustration of a pixel grid, where bold entries are original pixels, and the remaining entries are pixels to be interpolated. The gray region represents a 5× 5 window over which a LoG filter needs to be applied to sharpen C33. where a2, b0, b1, b2, b3, c2, and c3 correspond to the original pixels as illustrated in Figure 2. For G ≥ T , that is, what we consider as edge pixels, we compute the edge angle as µ = θ + 90o, (4) since the gradient is perpendicular to the edge. Our interpola- tor, as shown in Equation (5), considers only three ranges of edge angles for center pixel interpolation, and two ranges for row and column pixel interpolation, respectively. A =  1 2 (c2 + b3), 35 o < µ < 55o 1 2 (b2 + c3), 125 o < µ < 145o A′, else B = { 1 6 (c0 + a1 + 2(b0 + b1)), 0 o < µ < 90o 1 6 (a0 + c1 + 2(b0 + b1)), else C = { 1 6 (b1 + a3 + 2(a2 + b2)), 0 o < µ < 90o 1 6 (a1 + b3 + 2(a2 + b2)), else (5) where A′ is defined in Equation (3). As explained earlier, we use fewer angle ranges and fewer original pixels during inter- polation since we are primarily interested in a low complexity interpolator for mobile devices. C. Modified Laplacian of Gaussian (LoG) filter The LoG filter of size K × L is defined as LoGσ[x][y] = h(x, y, σ)− 1 KL K′∑ x=−K′ L′∑ y=−L′ h(x, y, σ), h(x, y, σ) = (x2 + y2 − 2σ2) exp(−x2+y22σ2 ) 2piσ6 ∑K′ x=−K′ ∑L′ y=−L′ exp(−x 2+y2 2σ2 ) ,(6) where K ′ = K−12 , and L ′ = L−12 . Figure 3 illustrates a pixel grid, where Cij is a pixel at location (i,j). The 5 × 5 LoG filter operation for sharpening pixel C33 is Ch = 5∑ i=1 5∑ j=1 Cijhij , (7) where hij = LoGσ[i− 3][j − 3]. The LoG filter is made adaptive by varying σ based on the gradient magnitude G computed by the modified Sobel operator in Equation (2). The following function is used to map G to σ: σ(G) =  ∞(no sharpening), G < 100 1, 100 ≤ G < 200 1.2, 200 ≤ G < 300 1.4, G > 300. (8) Larger σ is used for larger gradients, to prevent over sharpen- ing which can cause strong edges to look like artifacts. For brevity, the LoG filter and joint filter design are de- scribed for center pixels only; the design for row and column pixels is similar. In Figure 3, the entries in bold represent original pixels and the remaining entries are pixels to be interpolated, which we also refer to as “missing pixels” in this paper. A question arises: how do we sharpen C33 if the missing pixels in Figure 3 have not been interpolated yet? We answer this question by using estimated values for the missing pixels when using the LoG filter. The center, row, and column missing pixels are estimated using Equation (3). Since the LoG filter operation is now independent of EDI, we can combine EDI and LoG filter into a joint filter. We would like to design a modified adaptive sharpening fil- ter g(G) that operates only on original pixels, and yet provides the same high frequency component Ch in Equation (7). That is, Ch = 3∑ i=0 3∑ j=0 C2i,2jgij , (9) and g(G) =  g00 . . . g03... . . . ... g30 . . . g33  . (10) The filter g(G) operates on a 4 × 4 window unlike the LoG filter. To illustrate the design of g(G), we derive the coefficients g00 and g01. We first express each product term in Equation (7) in terms of the original pixels, using Equation (3) for the missing pixels, as follows: C11h11 = 0.25(C00 + C02 + C20 + C22)h11 C12h12 = 0.5(C02 + C22)h12 C13h13 = 0.25(C02 + C04 + C22 + C24)h13 ... (11) From Equation (10), the sum of the coefficients corresponding to C00 and C02 are g00 and g01, respectively. Combining the terms in Equation (11), we get g00 = 0.25h11 g01 = 0.25h11 + 0.5h12 + 0.25h13. (12) Similarly, we derive the remaining coefficients of g(G). D. Joint filter As explained in Section II-C, since our modified LoG filter operates independent of our EDI, the joint filter is obtained by combining the two filters as follows hjoint center(G,µ) = hcenter(G,µ)− g(G), (13) where hcenter(G,µ) is the EDI for center pixels given in Equation (5), and represented as hcenter(G,µ) =   0 0 0 0 0 0 0.5 0 0 0.5 0 0 0 0 0 0  , 35o < µ < 55o,and G ≥ T  0 0 0 0 0 0.5 0 0 0 0 0.5 0 0 0 0 0  , 125o < µ < 145o,and G ≥ T  0 0 0 0 0 0.25 0.25 0 0 0.25 0.25 0 0 0 0 0  , else, (14) where T is the threshold described in Section II-B. There- fore, the joint filter internally combines the interpolated pixel with its high frequency component to generate a sharpened interpolated pixel. For an original pixel, the joint filter uses the original pixel itself instead of using an interpolator in Equation (13). For each pixel category, we can predetermine the original pixels in the 5× 5 window that would be operated on by the joint filter. This gives us the joint filter size for different pixel categories, and they are listed in Table 1. Since the joint filter operates on original pixels only, its size is smaller than 5× 5. TABLE I FILTER SIZES. Pixel type EDI LoG filter Joint filter Center 2× 2 5× 5 4× 4 Row 3× 2 5× 5 3× 4 Column 2× 3 5× 5 4× 3 Original – 5× 5 3× 3 III. RESULTS We compare the complexity and visual quality of three methods: EDI only, EDI followed by adaptive sharpening called the two-step filter, and the proposed joint filter. We use the following test videos downsampled by two in both dimensions: Legend of Guardians (240 × 102), Harry Potter Clip1(240 × 100), Harry Potter Clip2 (240 × 102), Foreman (QCIF), Hall (QCIF), mobile (QCIF), and bus (QCIF), and consider upsampling these videos by two in both dimensions together with adaptive sharpening. Sharpening is disabled for the chroma components. Since all the filters share the same EDI only Two-step filter Joint filter Fig. 4. Visual quality examples. Left, middle, and right column images are obtained using EDI, two-step filter, and joint filter, respectively. modified Sobel operator before filtering, we do not include it in measuring the computational complexity. For an image of size N × M , the number of multiplications for EDI = (2 × 2 + 3 × 2 + 2 × 3)NM = 16NM , using Table I. The number of multiplications for a separable LoG filter is 4 × 5 × 2N × 2M = 80NM . The total number of multiplications for luma for the two-step filter is 96NM , while for the joint filter it is (16 + 12 + 12 + 9)NM = 49NM . Therefore, our joint filter takes about 38.75% fewer multipli- cations compared to the two-step filter. Unlike the two-step filter, where original pixels are accessed twice, our joint filter only accesses them once, thereby reducing the time taken for memory read operation. We compute the PSNR-Y of the joint filtered output relative to the two-step filtered output, since our goal is to achieve similar quality as the two-step filter, while taking fewer computations. The PSNR-Y of the joint filter averaged over all the test sequences is 41.6 dB, indicating that our joint filter yields filtered images close to the two-step filter. Furthermore, Figure 4 shows that the visual quality of the two filters are very similar, and that they are both sharper compared to the EDI approach. IV. CONCLUSION In this paper, we present a joint filter that performs edge- directed interpolation and adaptive sharpening simultaneously. The joint filter reduces the number of multiplications by 38.75% without loss in visual quality over the two-step filter approach. In our future work, we will investigate designing a joint filter using other edge-directed interpolation and sharp- ening filters, and support for upsampling factors other than two. REFERENCES [1] J. Allebach and P. Wong, “Edge-directed interpolation,” in Proc. IEEE ICIP, vol. 3, pp. 707-710, Sep. 1996. [2] X. Li and M. T. Orchard, “New edge directed interpolation,” IEEE Trans. Image Processing, vol. 10, no. 410, pp. 1521-1527, Oct 2001. [3] M. Li and T. Q. Nguyen, ”Markov random field model-based edge- directed image interpolation,” IEEE Trans. Image Processing, vol. 17, no. 7, pp. 1121-1128, July 2008. [4] S. Yang et al., “Fine edge-preserving technique for display devices,” IEEE Trans. Cons. Electron., vol. 54, no. 4, pp.1761-69. [5] M. Kraus, M. Eissele, and M. Strengert, “GPU-based edge-directed image interpolation,” in Proc. SCIA, pp. 532 - 541, 2007. [6] D. D. Muresan, “Fast edge directed polynomial interpolation,” in Proc. IEEE ICIP, vol. 2, pp. 990 - 993, 2005. [7] L.Zhang and X. Wu, “Image interpolation via directional filtering and data fusion,” IEEE Trans. Image Process., vol. 15, no. 8, pp.2226-2238, Aug. 2006. [8] Y. Cha and S. Kim, “The error-amended sharp edge (ease) scheme for image zooming,” IEEE Trans. Image Process., vol. 16, no. 6, pp.1496- 1505, Jun. 2007. [9] S. Kim and J. P. Allebach, “Optimal unsharp mask for image sharpening and noise removal,” J. Electron. Imag., vol. 15, 2005. [10] H. Kotera and H. Wang, “Multiscale image sharpening adaptive to edge profile,” J. Electronic Imag., vol. 14, no. 1, 2005. [11] T. Kobayashi and J. Tajima, “Content-Adaptive Automatic Image Sharp- ening,” in Proc. of the 2010 20th ICPR, pp. 2214-2217, 2010.