Yu-Che (Eddie) Cheng

Department of Electrical Engineering

Stanford University

chengye@stanford.edu

Image interpolation estimates the missing pixel values among samples of pixels. This is useful in many applications, such as changing image resolution for display or printing, reducing image size for storage, and reconstructing color images from digital sensors sampled by color filter array.

Classical linear interpolation techniques such as nearest neighbor, bilinear, or bicubic interpolation are simple and hence popular, but they all produce images with various artifacts, especially around edges on the image. Nearest neighbor interpolation produces block artifacts and jagged edges, while bilinear and bicubic interpolations usually blur edges. The results can be improved if we use edge-adaptive interpolation techniques. Since the blurring is due to averaging across edge in linear interpolation, edge-adaptive techniques try to interpolate along edges, not across them. Therefore, they usually produce images with sharper edges.

The structure of the report is as follows. In the next section, I'll present several new and interesting edge-adaptive image interpolation techniques. Their results will be shown and compared in the section 3. Applications of these edge-adaptive interpolation techniques in color filter array (CFA) image recovery will be considered in the section 4. Again, the results will be shown and compared. The report will conclude with the summary of my findings.

Some edge-adaptive interpolation techniques try to explicitly detect the edges on the original image first to generate an edge map and then use it to assist interpolation later. The process is depicted in figure 1. Example of these technique are [Allebach '96] and [Dube '00]. This class of methods involve multiple steps and are usually complicated and computational costly. Another class of edge-adaptive techniques attempts to have edge information built into the algorithms. These techniques do not require explicit detection of edges. Example of these are [Cok '87], [Kimmel '99], [Li '00], and [Muresan '01].

The method first catches the local characteristics of the image by performing block classification and then applying different filters based on the analysis (refer to figure 1). The steps of the algorithm are as follows:

1. Divide the image in 4 x 4 sliding (overlapping) blocks. Figure 2. shows such a block. A-P are the pixels of the original image, x, y, z are the pixels needed to be interpolated in current block and pixels r and s are previous interpolated pixels.

2. Classification and analysis of the block:　

3. Interpolation of blocks:

Define the following three filters:

For Smooth block:

• x = Cubic1(E,F,G,H)
• y = Cubic(B,F,J,N)
• For pixel z, apply Cubic1 filter along four horizontal rows of the block following by Cubic1 filter in vertical direction along the four horizontal interpolation results

For Edge block:

• z = Med(F,G,J,K)
• x = Med(F,G,r,z)
• y = Med(F,J,s,z)

For Texture block:

Same as smooth block but using Cubic2.

This is a very simple technique adapted from the paper [Cok '87]. The original algorithm is described in the context of color image reconstruction from Bayer CFA. Here I use it as a general image interpolation technique. Given that we want to estimate the pixel at x from its neighboring pixels A, B, C, and D (see figure 3), the idea is just to check for horizontal and vertical edges by computer the difference of the pixel values in the horizontal and vertical direction. If one is significant larger than the other, we assume there is an edge in the direction that has large difference and use the pixels from the other direction to do the bilinear interpolation. If both differences are small, we use all neighboring pixels to do bilinear interpolation. The algorithm is shown below:

Obviously there is problem with the algorithm that only detects the edges in the vertical and horizontal directions. Improvements on this method are made in several papers such as [Chang '99] where diagonal directions are also considered. However, problem still remains for any arbitrary oriented edges.

In this technique, we calculate the likelihood that each pixel belongs to an edge based on the directional derivatives. The interpolation is such that more weights are given to the pixels lined along the edge than the pixels across it. This is an extension of [Cok '99]. Instead of using bilinear interpolation, we use weighted interpolation.

If we are to interpolate the missing pixel depicted in figure 4, with E as a directional edge measure, we'll do the following:

P_(m,n) = Sum_{(i,j) in neighborhood}P_(m+i,n+j)E_(m+i,n+j) / Sum_{(i,j) in neighborhood}E_(m+i,n+j)

The directional gradients in the x, y, x-diagonal, and y-diagonal directions are defined as follows:

D_x(P_(m,n)) = (P_(m,n-1)–P_(m,n+1)) / 2

D_y(P_(m,n)) = (P_(m-1,n)–P_(m+1,n)) / 2

D_xd(P_(m,n)) = (P_(m-1,n+1)–P_(m+1,n-1)) / 2.83

D_yd(P_(m,n)) = (P_(m-1,n-1)–P_(m+1,n+1)) / 2.83

This technique estimates local covariance characteristics and uses them to derive the optimal linear MMSE prediction for the weighted interpolation. It has been shown that covariance-based adaptation is very effective on tuning a predictor to match an arbitrarily oriented edge. However, the estimation of covariance structure at high resolution requires the complete knowledge of high-resolution image while we only have access to its low-resolution version. The key to overcome the above difficulty is to recognize the resolution-invariant property of edge orientation. That is, the low-resolution image contains (approximately) the same edge information as the high-resolution image, hence we can replace the covariance structure at high resolution with its low-resolution counterparts.

Again, we use weighted interpolation.

The weights E_(m+i,n+j) are derived from a least square problem formulation. It assume that within a fixed small region, E_(m+i,n+j) is constant for each (i,j). Using the know pixel values, we can set up a linear system of equations based on the above assumption to find E_(m+i,n+j) via a mean square error solution. Suppose we want to find the weights for each neighboring pixel in figure 4, our linear system of equation would be as follows:

An extension to this technique based on the concept of optimal recovery is described in [Muresan '01].

The interpolated images of a lighthouse test image from various interpolation techniques are show below. As shown from the results, classical linear interpolation techniques like nearest neighbor produces blocking artifacts near the edges and bilinear interpolation blurs edges. The edge-adaptive interpolation techniques produce images that are both smoother in uniform areas and sharper around the edges. It can also be seen from the results that techniques like [Li '00] and [Murasan '01] can adapt to arbitrarily oriented edges better than the other two edge-adaptive techniques. To emphasis this point and also shown the color interpolated images, two flower images interpolated by bilinear and [Li '00] techniques are shown. The images contain many different orientations of edges and the result of [Li '00] shows that it perform much better than bilinear technique in producing sharp edges.

(a) Nearest Neighbor (b) Bilinear (c) [Dube '00]

(d) [Kimmel '99] (e) [Li '00] (f) [Muresan '01]

(a) Bilinear (b) [Li '00]

Due to hardware limitation, consumer digital cameras usually use only one image sensor. To capture all colors of an image, Color Filter Array (CFA) is required, which lay on top of image sensor so that each pixel only captures one color of light. Figure 5 shows the popular Bayer pattern CFA used in most of the digital cameras today. From the pattern, we can see that the image in each color channel, red, green, or blue, has less resolution than the sensor resolution. Therefore, to reconstruct the full color image of the sensor, we need to do interpolation on each color component. Classical bilinear interpolation is popular for this application because of its simplicity. However, it can produce zipped-like artifacts near the edges on the images (shown below). Again, edge-adaptive interpolation can be used to reduce this kind of artifacts. The result of applying [Li '00] to recover color image from CFA is shown below. The test image is a portion of a sailboat. Note that the technique is applied to different color plane seperately. There are some methods that exploits the correlation between different color planes and can potentially obtain better results. [Chen '99] and [Ramanath] provide very thorough surveys of the different techniques used in the area of CFA image recovery.

Bilinear [Li '00]

This report surveys some of the new edge-adaptive image interpolation techniques. These techniques are try to interpolate along edges, not across them, to reduce the blurring of edges, as can be seen from the classical bilinear image interpolation. The results show much sharper edges when these techniques are applied. This characteristic makes edge-adaptive techniques good candidates for color image recovery from CFA because traditional bilinear interpolation usually produces zipped-like artifacts when used in this application. The result shows those artifacts are significantly reduced when edge-adaptive interpolation is used.

[Muresan '01] D. D. Muresan and T. W. Parks, “Adaptive, Optimal-Recovery Image Interpolation”, IEEE ICASSP 2001 (Utah).

[Chang '99] E. Chang, et.al., "Color Filter Array Recovery Using a Threshold-based Variable Number of Gradients," Proceedings of SPIE, January, 1999