EP0993656A1

EP0993656A1 - Image interpolation

Info

Publication number: EP0993656A1
Application number: EP99947051A
Authority: EP
Inventors: Carlo R. Alessandretti; Paola Carrai; Luigi Albani; Vittorio Rochelli; Giovanni Ramponi
Original assignee: Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 1998-04-29
Filing date: 1999-03-18
Publication date: 2000-04-19
Also published as: AU3268899A; CN1266519A; KR20010014320A; JP2002506600A; WO1999056247A1

Abstract

In an image interpolation method, interpolated pixels are inserted (51) along horizontal and vertical directions so as to obtain a grid (I2) in which interpolated lines cross themselves in original pixels. In a second step, pixels are interpolated (52) between rows and columns formed by the grid (I2) so as to fill squares delimited by the grid (I2) to obtain an interpolated image (I3).

Description

Image interpolation.

The invention relates to image interpolation.

In many video and multimedia applications it is necessary to increase image dimensions, preserving the quality of the output images. Linear operators normally used for this purpose - are not suitable to generate high quality interpolated images, because they produce smoothed images and blocking artifacts. Techniques were studied to achieve a sharper reproduction of details, but usually they are excessively complicated and require the explicit detection of the image details and the estimation of their orientation (see e.g. [1]).

Rational filters (RFs), whose input/output relation is expressed as the ratio of two polynomials in the input variables, have already been used with satisfactory results in noise smoothing, contrast enhancement and image interpolation by power-of-two factors [3,4,5].

In [5] an operator was proposed for the interpolation of the DC components of coded images, and it was shown that this algorithm can overcome the theoretical limitations of the linear ones, with respect to the rendering of sharp details in output images; at the same time, this kind of interpolator avoids blocking artifacts which could affect diagonal lines, circles, etc.. That rational interpolator was designed to operate in the two-dimensional domain in a non-separable way and it was able to resize images by repeatedly up-scaling the data by a factor of two.

It is, inter alia, an object of the invention to interpolate images by large and arbitrary factors preserving the sharpness of their contours. To this end, the invention provides an image interpolation method and device, as well as a video display apparatus or a printing apparatus comprising such an image interpolation device, as defined in the independent claims. Advantageous embodiments are defined in the dependent claims.

In a preferred embodiment, the aim of the method presented here is achieved by using a technique based on a nonlinear rational filtering (RF). To allow for up-scaling by arbitrary factors, distances between a pixel to be interpolated and surrounding pixels are preferably taken into account in the rational filtering. These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.

In the drawings: Fig. 1 illustrates the distance between an interpolated pixel and original pixels;

Figs. 2A-2C illustrate row interpolations by a factor 4; Fig. 3 illustrates original rows and columns interpolations by a factor 4; Fig. 4 illustrates pixel evaluations within the space delimited by rows and columns; Fig. 5 shows a conceptual block diagram; and

Fig. 6 shows a two-dimensional operator formula implementation.

Our focus is to study the performance of the RF algorithm as a zooming feature. This feature is a key point in a broad range of multimedia applications. Among these we could list, for instance, photo or video editing and resolution increase for printing pre-processing. However, in many of these applications, it is necessary to cope with high up-scaling factors that are not powers of two. In this description an extension of the interpolator proposed in [5] will be described. It overtakes its limitation thus allowing the use of any value.

The theoretical limitation of linear interpolation is the low-pass filtering implemented by the operators to avoid imaging artifacts in the output image. This operation limits the presence of high frequency components in the output images, corresponding to details and sharp edges in the spatial domain.

For example linear interpolation by an integer L factor is performed by inserting L-l equidistant zero-valued samples between two consecutive original samples, then a low-pass filtering is performed [2].

The proposed algorithm will be able to reconstruct high frequency components avoiding the blocking artifacts of diagonal edges due to the separability of linear interpolators.

The algorithm works in two steps. The first step is a one-dimensional interpolation of original rows and columns; the second one is the interpolation of the space among interpolated rows and columns.

The first step is the interpolation of the original rows and columns by the required factor. This step is implemented by using a one-dimensional rational interpolator, whose formula is defined by the equation (1). Pixels S_p are calculated between the original ones p₂ and p₃ by using the scheme of Fig. 1. The distance between p₂ and p₃ is equal to 1, while the distance δ between S_p(δ) and p is smaller than or equal to 1 and greater than or equal to 0.

W_p2 (^l - < )P2 + ^Wp3<5-P3

Sp( ) = w P2 (l - S) + w_p2S

5 where w_p2 = l+k((p₂-p₄)² + (p₃-ρ₄)²) and w_p3 = l+k((pι.p₃)² + (pι-p₂)²)

A; is a parameter related to the non linearity of the algorithm, while the distance δ is described in Fig. 1. The pixels pi, p , p₃ and p are the original input data aligned on the same row or

10 column. The pair w_p2 and w_p3 represents an edge sensor that is able to reconstruct luminance transitions sharply.

In Fig. 2 we can see how a one-dimensional edge in an original vector (Fig. 2A) is interpolated by a factor of 4 by using a linear interpolator (Fig. 2B) and a one-dimensional rational interpolator (Fig. 2C). We can see how the rational one-dimensional interpolator of

15 Fig. 2C reconstructs the edge more sharply; indeed the luminance transition produced by using the rational interpolator is shorter than that produced by the linear interpolator of Fig. 2B. This result is achieved by exploiting the sub-pixel information contained in the available data.

The second step of the algorithm is the interpolation of pixels between rows and 20 columns evaluated at the first step (the shadowed square of Fig. 3, in which the bigger circles indicate original pixels and the smaller circles indicate the points interpolated in the first step). The interpolation of a generic point z, located inside the internal square and having the original points (indicated by black dots) as vertexes (see Fig. 4), is performed using the points a, b, c, d, e,f, g and h interpolated in the first step and indicated by circles. These points are 25 defined once the position of the pixel to be evaluated is fixed; these pixels belong to the 0, 45, 90 and 135 degrees directions and to the interpolated rows and columns. The computation of z depends on its "rational" weights and on its distances (d_a, d_b, ..., d_h) from points a, b, ..., h. This calculation must be done for each of the (L-l)² points located inside the square. According to the above description, the value of z with reference to the Fig. 4, will be:

™ w_ac(ad_c + cd_a) + w_bd (bd_d + dd_b) _t w_eg(^{e d} _g ⁺ S^de) ^{+ w} _fl.(f ^d» ^{+ h d} _f ) όv z = 1 — — ac + ^W d + ^We_g + ^Wfi ^Wac + ^Wbd + ^We_g + ^Wβ with d_c - 1 - d_a; dd = 1 - d_b; d_e ^~ 1 - d_g; df = 1 - dh

and w = ^■ w,,, = ^■ l + k(a - c)² \ + k(b - d)²

and

w„ = r,w_Λ = ^• ^eg l + ^e - g)² ' l + k(f -h)² The role of the distances d_a, d_b, d_c, ... d_h is to weigh the contribution of first-step interpolated points taking into account their distances from the pixel to be computed. The weights w_ab, W_bd, w_eg and W_ft, are able to determine if there is a dominant direction selected, for example, among

0. 45, 90 and 135 degrees, in the square composed of original and interpolated pixels. These directions are the most reasonable, but the distances could be evaluated also along lines differently oriented. Actually, if a pair of pixels, selected among (a; c), (b; d), (e; g) and (f; h), has similar values then the respective weight will be greater and the direction which they belong to will be dominant for the evaluation of pixel z. Moreover, there is an average weighting with respect to the distance between the pair of related pixels.

In order to describe more clearly the algorithm let us review the way it works.

Starting from an input image whose size is N rows by M columns and using a scale factor SF the 2 steps to be performed for the execution of the processing can be explained as:

1. A mono-dimensional operator (1-D operator) intervention by which interpolated pixel are inserted in between 2 original pixels only along the horizontal and vertical directions in such a way to obtain a grid. In this grid interpolated lines cross themselves in original pixels; in this way we obtain an intermediate image whose nominal dimension is equal to the output image, but, with only N*M +N*M*(SF-1) + M*N*(SF-1) significant pixels; these pixels will be referenced to as grid pixels.

2. An interpolation with a 2-D operator that fills the squares delimited by the grid with new pixels (the size of the squares will be (SF+1) x (SF+1) pixels and the number of pixels to be evaluated for each squares will be (SF-1) x (SF-1)). The 2 steps can be represented graphically with the block diagram of Fig. 5. An input image II having N rows and M columns is applied to a one-dimensional operator 51 to obtain an intermediate image 12 having N*M + N*M*(SF-1) + M*N*(SF-1) significant pixels, viz. the original and interpolated pixels shown in Fig. 3. For the intermediate image 12, the original rows and columns length is increased by the scaling factor SF. The value of the

N*(SF-1)*M*(SF-1) located among original interpolated rows and columns is not yet defined. The intermediate image 12 is applied to a two-dimensional operator 52 to obtain an output image 13 having N*SF rows and M*SF columns.

A dedicated hardware could be designed to perform the required operations. The two-dimensional operator, whose behavior is affected by the choice of the "k" parameter (according to our studies a proper value can be selected around 0.1), works on every square defined by the grid pixels. Starting from one of these squares, this operator computes the value of each pixel inside, using the "grid pixels" belonging to the edges of that square and the pixel coordinates referring to the position in the square (see Fig. 3). These relative pixel co- ordinates are expressed by two integer indexes whose values are in the range (1, SF-1). The processing of the 2-D operator can be described with a block diagram as in Fig. 6.

Fig. 6 shows a two-dimensional operator formula implementation. Grid pixels GP and relative pixel coordinates RPC are applied to a grid pixel selector 61. The relative pixel coordinates RPC are also applied to a distance generator 62. An output of the grid pixel selector 61 and the parameter k are applied to a weight generator 63. Outputs of the distance generator 62 and the weight generator 63 are applied to a multiplier generator 64. Outputs of the grid pixel selector 61 and the multiplier generator 64 are applied to a multiplier accumulator 65. Outputs of the weights generator 63 and the multiplier accumulator 65 are applied to a divisor 66 that generates output pixels OP that are displayed on a display D or sent to a printing device P.

A primary aspect of the invention can be summarized as follows. A non-linear technique for image interpolation is presented. Linear techniques produce smoothed images and blocking artifacts at the output. The aim of our method is to interpolate images by large and arbitrary factors preserving the sharpness of their contours. We achieve this goal by using a technique based on the nonlinear rational filter (RF).

The presented algorithm is derived from the one described in Ref. [5]; the algorithm described there is able to perform image interpolations when the scaling factor is represented by a power of two. That kind of interpolator is important because it applies the method of "rational filters" (RF) to produce interpolated images that preserve the sharpness of the details avoiding at the same time blocking artifacts. The computational load of the algorithm seems not heavier than the one of comparable algorithms that are not based on RF. In the solution proposed here, the two dimensional interpolation scaling factor advantageously needs no longer be a power of two but can be any number (> 1). A mono- dimensional interpolator based on RF is able to work with arbitrary scaling factor (any real number >1). After a first step during which this operator is used, a two-dimensional operator is applied. Also this operator is based on RF and can work with any interpolation-scaling factor; the proposed structure is intrinsically sensitive to the edge orientation in such a way to produce contours with a high degree of sharpness even if these contours are not horizontal or vertical. The invention can be used in the zooming of natural images like those obtained from photographic or video cameras.

A primary aspect of the invention thus provides an image interpolation method comprising the steps of inserting interpolated pixels along the horizontal and vertical directions so as to obtain a grid in which interpolated lines cross themselves in original pixels; and interpolating pixels between the rows and columns formed by the grid so as to fill the squares delimited by the grid. An image interpolation device operating in accordance with this method is also provided, as well as a video display apparatus (printing apparatus) comprising such an image interpolation device for supplying an interpolated image, and a display (printing device) for displaying (printing) the interpolated image.

It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word "comprising" does not exclude the presence of other elements or steps than those listed in a claim. The invention can be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In the device claim enumerating several means, several of these means can be embodied by one and the same item of hardware. References:

[1] K. Jensen and D. Anastassiou, "Subpixel edge localization and the interpolation of still images," IEEE Trans, on Image Processing, vol. 4, no. 3, March 1995, pp. 285-295. [2] S., K., Mitra, "Digital Signal Processing, A Computer-Based Approach," McGraw-Hill Companies, New York, 1998.

[3] G. Ramponi, "The Rational Filter for Image Smoothing," IEEE Signal

Processing Letters, vol. 3, no. 3, pp. 63-65, March 1996.

[4] G. Ramponi and A. Polesel, "A Rational Unsharp Masking Technique," Journal of Electronic Imaging, vol. 7, no. 2, April 1998, pp. 333-338. [5] G. Ramponi and S. Carrato, "Interpolation of the DC Component of Coded

Images Using a Rational Filter," Proc. Fourth IEEE Intern. Conf. on Image Processing, ICIP- 97, S. Barbara, CA, Oct. 26-29, 1997.

Claims

CLAIMS:

1. An image interpolation method, comprising the steps of. inserting (51) interpolated pixels along horizontal and vertical directions so as to obtain a grid (12) in which interpolated lines cross themselves in original pixels; and interpolating (52) pixels between rows and columns formed by the grid (12) so as to fill squares delimited by the grid (12).

2. A method as claimed in claim 1, wherein rational filtering is used in said inserting step (51) and/or said interpolating step (52).

3. A method as claimed in claim 3, wherein distances between a pixel to be interpolated and surrounding pixels are taken into account in said rational filtering.

4. An image interpolation device comprising: means (51) for inserting interpolated pixels along horizontal and vertical directions so as to obtain a grid (12) in which interpolated lines cross themselves in original pixels; and means (52) for interpolating pixels between rows and columns formed by the grid (12) so as to fill squares delimited by the grid (12) to obtain an interpolated image (13).

5. A video display apparatus comprising: an image interpolation device as defined by claim 4 for supplying an interpolated image (13); and a display (D) for displaying the interpolated image (13).

A printing apparatus comprising: an image interpolation device as defined by claim 4 for supplying an interpolated image (13); and a printing device (P) for printing the interpolated image (13).