RU2367019C2 - Method for digital image interpolation - Google Patents

Abstract

FIELD: physics; image processing.

SUBSTANCE: invention relates to processing digital images, particularly to methods of changing the scale of a digital image, i.e. calculating luminance values in points, which do not belong to the initial set of points in which luminance values are known. A method is proposed for interpolation of a digital image with increase in sampling frequency by t times, comprising the following stages: pre-processing the image; determining the viewing window size m, degree of interpolation function n and scaling factor t; coefficient vector K is calculated, which corresponds to the given m, n, t combination; for each pixel of the initial image, m-1 nearest neighbours are determined, which, together with that pixel, form the viewing window, m; luminance of pixels, which form the viewing window m, are standardised to the k (k=1) level; luminance t² of pixels is calculated using an m-dimensional interpolation polynomial of degree n, with vector K as coefficients; each interpolated pixel is assigned new coordinates (x', y); all previous steps are repeated for each colour component; the image is post-processed to reduce defects.

EFFECT: design of a linear spatial interpolation method, with improved capabilities and considerably less artefacts.

6 cl, 13 dwg

Description

The invention relates to digital image processing methods. In particular, to methods for changing the size (scale) of a digital image, i.e. calculating brightness values at points that do not originally belong to the original set of points at which brightness values are known.

There is a wide variety of different interpolation methods. All these methods can be classified according to accuracy, quality criteria, approximation and the mathematical apparatus used. Most bitmap interpolation algorithms are based on replacing the unknown function of the two-dimensional brightness distribution of the interpolated image with a function close to the unknown and having properties that make it easy to perform certain analytical or computational operations. Moreover, depending on the choice of the class of interpolating functions, the solution to the interpolation problem is reduced to solving systems of linear or nonlinear equations.

Linear methods are extremely important for image processing, since they rely on a significant body of well-studied theoretical and practical results (see US Pat. No. 5,671,298 [1], No. 6,320,593 [2], No. 6,496,609 [3], United States Patent 6965705 [4] )

Nonlinear methods (see US Patent No. 6,823,091 [5]), although sometimes lead to better results, are not always predictable, unambiguous, and for the most part insufficiently studied theoretically. Also, a significant drawback of nonlinear methods compared to linear ones is the increased requirements for computing resources and low interpolation speed.

A further development of nonlinear interpolation methods is the use of adaptive algorithms (see, for example, US Pat. Nos. 5,532,950 [6], 6,191,788 [7]), the behavior of which varies depending on the static properties of the image within the scope of the interpolating function. As practice shows, the performance of more computationally adaptive algorithms is usually better than the methods previously considered, however, increased computational requirements for the implementation of adaptive methods, despite their high efficiency, slightly reduce their scope.

Of all the methods closest to the claimed invention are methods based on linear spatial interpolation. As a prototype of the claimed invention, the linear cubic interpolation method described in US Pat. No. 5,671,298 [8] was selected.

Interpolation with cubic splines consists in the search for such polynomials of the third degree on each of the segments (whose boundaries are adjacent points) whose first and second derivatives coincide with the first and second derivatives of the neighboring polynomial. Thus, the resulting continuous piecewise polynomial function has continuous first and second derivatives.

A significant drawback of the interpolation method described in the prototype [8] is the presence of characteristic artifacts in the interpolated image that degrade the accuracy of scaling in the region of sharp changes in brightness. Typical artifacts include the appearance of a serrated edge effect on slanted lines, blur due to limitations in the recovery of high-frequency components of the interpolated data, and the Gibbs effect, which manifests itself as spurious wave-like oscillations of the interpolation function that are absent in the interpolated image.

The technical problem to which the claimed invention is directed is to create a linear spatial interpolation method with improved interpolation capabilities and with much smaller artifacts characteristic of conventional linear interpolation algorithms.

The problem is solved by developing a method of image interpolation with increasing the sampling frequency of a digital image by t times, consisting of the following steps:

- carry out preliminary image processing;

- determine the size of the window of sight m, the degree of the interpolation function n and the scale factor t;

- read the vector of coefficients K corresponding to a given combination of m, n, t;

- determine for each pixel of the original image m-1 the nearest neighbors, which together with this pixel form a window of sight m;

- carry out the normalization of the brightness of the pixels forming the viewing window m to the level k (k = 1);

- calculate the brightness of t ² pixels using m dimensional interpolation polynomial of degree n having the vector K as coefficients;

- assign to each interpolated pixel new coordinates (x ', y');

- repeat all the previous steps for each color component;

- spend the final processing of the image to reduce artifacts.

Thus, the solution reduces to creating a linear spatial interpoliant based on a multidimensional piecewise continuous algebraic polynomial (polynomial spline). The dimension and degree of the polynomial are selected based on the requirements of the accuracy of signal reconstruction and computational capabilities.

For the functioning of the polynomial spline corresponding to the task, it is necessary to find such coefficients of the polynomial that will optimally satisfy the condition for achieving maximum accuracy of the interpolation function

The method according to claim 1, characterized in that the coefficients are determined using multiple regression analysis and a set of reference images that are distorted by the same algorithm as the processed image.

Their number and type is selected based on the fulfillment of the condition for achieving the specified accuracy of the interpolation function. In the general case, to obtain good results, it is sufficient to use any image with the widest possible range of changes in local contrasts as a reference, however, the best result from the point of view of minimizing the interpolation error is achieved only in the case of a rational (representative) selection of standards.

The technical result of the claimed invention is the creation of a linear spatial interpolation polynomial by implementing a number of modifications of the interpolation method described in the prototype. These modifications are based on the following conclusions.

The bicubic method is based on the approximation of a multidimensional interpolation function of degree 3 within a window of 4 × 4 points. Solving the problem of determining the value of the interpolated pixel, after some mathematical transformations, you can get the resulting expression, which is defined as the sum of the values of 16 neighboring interpolated pixels, multiplied by the weight coefficients a _ij corresponding to their location.

The weighting coefficients a _ij for the bicubic method are independent of the values of the function f (x _i , y _i ) and are uniquely calculated on the basis of observing the continuity conditions within the interval of the interpolation function itself, its first and second derivatives and the given values of the first or second derivative at the boundaries of the interval. Obviously, from a mathematical point of view, expression (*) can also be defined as a 16-dimensional polynomial of the first degree, in which the brightness values of 16 neighboring interpolated pixels are monomials. An interesting fact is that both in the case of using an interpolating function of any other degree and in the case of more or less severe imposed conditions, the form of the expression (*) remains unchanged, and all possible options will be realized only through weighting factors a _ij .

The proposed method is a generalization of the bicubic method and its further development, which is expressed in the following changes:

1. The number of taken into account neighboring interpolated pixels is no longer limited to 16, but can take any values.

2. The degree of the polynomial is no longer limited to the first, but can take any other integer and non-negative values.

3. The coefficients a _{ij are} determined only by the condition for ensuring a minimum error, and no other conditions (smoothness, for example) are imposed. Moreover, to find them, the problem is solved on the basis of the multiple regression analysis method.

Moreover, it becomes obvious that the proposed method does not solve the problem of finding the interpolation function. Therefore, this method cannot be used in the case of solving problems of finding a functional dependence. The most important and positive property of the proposed method is a balanced combination of qualities such as high computation speed, which is typical of conventional linear methods, and high quality interpolation, which is characteristic of resource-intensive nonlinear adaptive methods.

Most often, when solving image scaling problems, various interpolation algorithms are used. The result of the work of such algorithms is the convolution of the desired image with a large-scale window restored with some error. To improve visual quality, various sharpening algorithms are often used. As a result, due to the accumulation of errors, the result of the work of such methods is imperfect, and the time costs are significant. A distinctive feature of the proposed method is that it is based on solving an inverse incorrect problem and its operation is similar to an inverse filter. There are modern scaling methods that solve this problem in a similar way, using, for example, back-convolution (deconvolution) algorithms using various regularization procedures. However, for the first time, a multidimensional piecewise continuous multidimensional algebraic polynomial was used to solve such problems. Unlike the most common algorithms, which are based on the search for an unknown function of the two-dimensional distribution of brightness of an interpolated image, the proposed method aims to find the law of change in brightness of an interpolated pixel.

For a better understanding of the essence of the claimed invention the following is a detailed description with the use of graphic materials.

Figure 1. The block diagram of the basic components of the system.

Figure 2. Illustration of the task of interpolating an elementary pixel of an image.

Figure 3. The block diagram of the steps in the process of calculating the optimal polynomial coefficients.

Figure 4. A block diagram of the steps of an image interpolation process.

Figure 5. Examples of the algorithm.

The image interpolation method, that is, increasing the sampling frequency of a digital image by a factor of t, works as follows:

1. Perform preliminary image processing, if necessary;

2. Set the window size m, the degree of the interpolation function n, and the scale factor t;

3. Download the vector of coefficients K corresponding to a given combination of m, n, t.

4. For each pixel of the source image, m-1 nearest neighbors are determined, which together with this pixel form a sighting window m;

5. Normalize the brightness of the pixels forming the window of sight, to the level k (k = 1);

6. Calculate the brightness t ² pixels using the m-dimensional interpolation polynomial of degree n having the vector K as coefficients;

7. Each interpolated pixel is assigned a new coordinate (x ', y');

8. Repeat steps 4-7 for each color component;

9. If necessary, perform subsequent image processing to reduce artifacts.

The method can be applied to both color and black and white (with shades of gray) images and provides high-quality and sharp images with high spatial resolution.

Figure 1. shows the main components of the system on which this method can be implemented. The implementation of the method is controlled by a processor 101 that executes program code stored in the memory 102. Also, the original black-and-white or color photograph is stored in the memory 102. The image is analyzed, a new image is created, the pixels of which are calculated using the pixels of the original image. The new image is transmitted to a display device 104, or to a printing device 103. Information is transmitted in the system via a data bus 106.

The following describes the process of creating an interpolated image.

Figure 2. illustrates the problem of image interpolation, where 2.1 and 2.2 are downsampling, and 2.3 is upsampling.

Let there be an image I (x, y), where x∈ [1, x _max ] y∈ [1, y _max ], which was obtained from X after downsampling in a known manner t times. Despite the wide variety of acceptable methods for reducing image sizes, an average method will be considered below as an example:

,

,

, которое бы согласно выбранному критерию близости в максимальной степени было близко к восстанавливаемому изображению X. Несмотря на возможность применения большого множества различных критериев близости в заявляемом способе предлагается использовать наиболее простой и самый распространенный критерий - метод наименьших квадратов (МНК):Then the problem of qualitative interpolation (upsampling) is formulated as follows. According to the available image I, it is required to obtain such an image

which, according to the selected proximity criterion, would be as close as possible to the reconstructed image X. Despite the possibility of applying a large number of different proximity criteria, the proposed method proposes to use the simplest and most common criterion - the least squares method (least squares):

,

,

The basis of the described algorithm is the method of multiple regression analysis using m dimensional piecewise continuous polynomial of degree n with fixed coefficients K of the form:

, при этом

,

, wherein

,

- m мерный полином степени n.Where:

- m dimensional polynomial of degree n.

ν ₁ , ν ₂ , ... ν _w form the vector V, the form of which is determined by this polynomial.

k ₁ , k ₂ , ... k _w form the vector K - coefficients of the polynomial.

- Приведенные к единому масштабу элементы изображения, принадлежащие оконной выборке, размер которой определяется параметром m. I_i∈[0, 1]

- Reduced to a single scale image elements belonging to the window selection, the size of which is determined by the parameter m. I _i ∈ [0, 1]

d _{(x, y)} - Scale factor for the current window.

I _{(x, y)} - Interpolated image pixel.

For each pixel of the original image I _{(x, y)} , the following procedure is performed: m-1 of the nearest neighbors of the processed point I _{(x, y)} are selected, which form the sighting window m. After that, the brightness values inside the sighting window lead to a single scale by normalizing each variable to the range of variation of the brightness values inside the window. In the simplest version, this is a linear conversion to a unit segment:

,

,

wherein: d _i = I _{i, max} -I _{i, min} ,

where: I _{i, max} , and I _{i, max} - the maximum and minimum values of the brightness of pixels in a given window.

The length w of the vectors V and K is determined by the following formula:

,

,

To find the coefficient vector of the polynomial by the OLS method, it is necessary for each interpolated pixel to solve an overdetermined system of linear equations of the form:

, где

where

,

,

,

,

Where S is the matrix of coefficients of a system of linear equations of size [w, w].

U is the vector of the right side of the system of equations of size [w].

K is the coefficient vector of a polynomial of size [w].

The coefficients of the matrix S, U are determined by the following formulas:

Where r is the number of measurements:

In the case of m = 9, n = 2 and t = 4, the variables a _i and b _{i are} determined by the following expressions:

The elementary window for each pixel of the original image I (x, y) for the case m = 9 is defined by the following formulas:

I ₁ = I (x-1, y-1); I ₂ = I (x, y-1); I ₃ = I (x + 1, y-1);

I ₄ = I (x-1, y); I ₅ = I (x, y); I ₆ = I (x + 1, y);

I ₇ = I (x-1, y + 1); I ₈ = I (x, y + 1); I ₉ = I (x + 1, y + 1);

Moreover, x∈ [2, x _max -1] and y∈ [2, y _max -1]

After that, system (1) is solved by some method for uniquely defined linear systems, in particular, taking into account the symmetry of SLAEs. The solution to the system is the desired vector of coefficients K.

The solution of linear systems of equations of large dimension, as a rule, is a non-trivial task due to their poor conditionality. The system is well solved until the computational error, which is inevitable in any computer calculations, begins to influence the error of the algorithm for solving it. To obtain reliable results of solving systems, it is required to use special methods that reduce the number of conditionality. Since the conditionality of the system is directly proportional to its dimension, the choice of the degree of the approximating polynomial and its dimension is an important task, which involves determining such optimal values for which the interpolation error is minimal and the computational cost is acceptable.

Figure 3 shows the block diagram of the steps implementing the method of finding the vector of optimal coefficients K for the case m = 9, t = 2, n = 2.

First, it is necessary to set the scale interpolation coefficient t, and also depending on the required accuracy and computational capabilities, it is necessary to determine the degree (n) and dimension (m) of the applied interpolation polynomial, 301.

After that, it is necessary to select a reference image X that satisfies the requirement of obtaining a minimum interpolation error and determine (or set) a scaling transfer function (for example, the method of average values), 301.

Then, the operation of reducing the reference image X by t times in a known manner determined by the scaling function 302 is performed. As a result, after reducing the image X, images I.

Then, for each point of the original image I (x, y), 303, the following procedure is performed:

The m-1 nearest neighbors of the processed point 304 are selected, which form the sighting window m, 305. Then, in a certain m neighborhood, the minimum and maximum brightness values are determined, then the neighborhood is scaled to the segment [0, 1], 306.

,

,

where d _i = I _{i, max} -I _{i, min} ,

Next, a vector of arguments of the regression function (S) and a vector (U), 307, are formed.

The accumulation of the values of the argument of the function (S) and the vector (U), 308.

After that, solving SLAE, the desired vector of optimal coefficients K, 309 is determined.

Figure 4 shows the block diagram of the steps of the process of interpolating the image with a spline polynomial for the case m = 9, t = 2, n = 2.

First, it is necessary to set the scale interpolation coefficient t, and also, depending on the required accuracy and acceptable time and system resources, determine the degree (n) and dimension (m) of the applied interpolation polynomial, 401.

Depending on the selected parameters, m, t and n load the previously calculated coefficient vector of the polynomial K, 401.

Then, for each pixel of the original image I (x, y) 402, m-1 nearest neighbors, 403. are selected. As a result, a sighting window of size m, 404 is formed. In this case, if the window border goes beyond the interpolated data, the missing pixels (with a negative or coordinate) in the simplest case, duplicate adjacent brightness values, or to obtain better results calculated by linear extrapolation.

Then, in the obtained m neighborhood, the minimum and maximum brightness values are determined, after which the neighborhood is scaled to the segment [0, 1], 405.

,

,

where d _i = I _{i, max} -I _{i, min} ,

Next, form a vector of arguments of the regression function, 406.

After that, a polynomial is calculated and the interpolated pixel values, 407, are found.

Then the obtained values are scaled back to the [local _min , local _min ] segment:

After that, the obtained coordinates are assigned the corresponding coordinates, 408.

The described procedure, namely steps 402-408, is performed for each color component in the RGB or YCrCb, 410 space. After condition 409 is fulfilled, the image is sent to an output device (printer, display, or some other) or stored in memory.

Figure 5 illustrates the problem of interpolating the image 4 times in two ways: the bicubic and the new method described above, where 5.1 are the source images, 5.2, 5.4 and 5.6 are images interpolated by the prototype method, 5.3, 5.5, 5.7 are images interpolated by the claimed way.

It should be borne in mind that the above embodiment of the invention is set forth for the purpose of illustration and it is obvious to those skilled in the art that various modifications, additions and substitutions are possible without departing from the scope and meaning of the present invention disclosed in the attached description and claims. So, for example, by modifying the method for the case of one-dimensional data (image - two-dimensional distribution), you can use it to process sound, and by modifying the method for the case of three-dimensional data, you can use it to increase the temporal resolution of video sequences. You can also modify the algorithm to implement the adaptability of the method to local features of the interpolated image.

Claims (6)

1. The method of interpolation of a digital image with an increase in sampling frequency t times, consisting of the following steps:
carry out preliminary image processing;
determine the size of the window of sight m, the degree of interpolation polynomial n and the scale factor t;
reading the coefficient vector K corresponding to a given combination of m, n, t;
determine for each pixel of the original image m-1 the nearest neighbors, which together with this pixel form a window of sight m;
carry out the normalization of the brightness of the pixels forming the sighting window m to the level k (k = 1);
calculate the brightness of t ² pixels using m dimensional interpolation polynomial of degree n with fixed coefficients K of the form:

Where

- m dimensional polynomial of degree n, v ₁ , v ₂ , ... v _w form the vector V, the form of which is determined by the given polynomial, k ₁ , k ₂ , ... k _w are the coefficients of the polynomial forming the vector K, d _{(x, y)} - scale factor for the current window, I _{(x, y)} - interpolated image pixel;
Assign new coordinates to each interpolated pixel (x ', y');
repeat all the previous steps for each color component;
perform final image processing to reduce artifacts. 2. The method according to claim 1, characterized in that the coefficients K of the m-dimensional polynomial are calculated based on the task of reducing the sampling frequency of the digital image by a different number of times and its reverse recovery with the condition that the result of the restoration of the digital image is similar to the original digital image in the sense of least squares , while the search for the coefficients K is carried out using the method of multiple regression analysis using the aforementioned m-dimensional piecewise continuous polynomial of degree n with fixed oeffitsientami K. 3. The method according to claim 1, characterized in that the K coefficients are determined using multiple regression analysis and a set of reference images that are distorted by the same algorithm as the processed image. 4. The method according to claim 1, characterized in that the parameters of the polynomial are fixed and independent of the interpolated data. 5. The method according to claim 1, characterized in that, as the only optimality criterion, minimization of the scaling error is adopted, for which a scale interpolation coefficient t is preliminarily set, and, depending on the required accuracy and computational capabilities, the degree (n) and dimension (m ) applied interpolation polynomial. 6. The method according to claim 1, characterized in that the calculation of the K coefficients of the polynomial for each variant of the interpolation parameters, including the size of the viewing window, the degree of the polynomial, the scale factor, is performed once, while the found parameters are used to scale an arbitrary image.

Images