Broadly speaking, interpolation is used to obtain intermediate values from a discrete set of known values. In the problem of image processing, the interpolation methods are used to predict the raster cell values when having a limited number of the input data points [1].
The interpolation techniques known today can be classified into deterministic and statistical [2]. Deterministic methods are based on a function of distance or area. The main advantage of such methods is high processing speed. Statistical methods are based on a function of spatial similarity. The main advantage of these methods is the sensitivity to the multidirectional data. That is why such methods are commonly used to interpolate various kinds of surfaces (for example, to create a digital terrain model).
In this paper, three methods of spatial interpolation are considered: inverse distance weighting, interpolation based on a triangulated irregular network, and kriging. These methods are used extensively in a wide variety of applied sciences, including geology, hydrology, meteorology and oceanography. However, in relation to image processing field, these methods have not been investigated in detail yet [3].
Our research is devoted to the applicability analysis of the above-mentioned spatial interpolation methods in the task of estimating the missing pixels of partially defined images, i.e. images with a predetermined fraction of unknown pixels.
Inverse distance weighting (IDW) is a deterministic algorithm based on the assumption that the predicted value is more influenced by the nearby points than the points located further [4].
Interpolation is performed using the known values from a neighborhood of a given point. It is assumed that each point with a known value (hereinafter, called the reference point) has a local effect decreasing with distance. The points located closer to the estimated position are assigned a greater weight, than those located further:
, where 0 () zs is an estimated value of a point in a certain location 0 s , and 12 ( ), ( ), , ( )
The weights are proportional to the inverse distance taken to the power of p. Consequently, an increase in distance leads to the fast decrease of weight. The weight decrease rate depends on the value of p. Thus, for p=0, the weights i w are the same, and the predicted value is the average of all measured points. As p increases, weights of the distant points start to decrease rapidly. If the value of p is large, only the nearest neighborhood points will affect the predicted value.
To speed up the calculations, the weights of the most distant points with little effect can be taken as zero. It is common practice to limit the number of reference points, used to predict an unknown value, by specifying the search area. In this paper, the search area is represented by a circle of a variable radius r.
Kriging [5] is a statistical interpolation method for prediction of unknown values using the values of the nearby points. Similar to the IDW method, weights are assigned to each point in accordance with the distance to the unknown value. However, here the estimation is performed on the basis of data correlation.
To date, research on kriging in image processing tasks is limited to several publications [6][7][8].
The basic kriging formula is:
, where 12 ( ), ( ), , ( ) n z s z s z s are the reference points, and 0 () zs is a value of the point to be evaluated. Also, it should be noted that
The main task is to determine the weights i so as to minimize the variance of the estimate, taking into account the unbiasedness requirement
There are several methods of kriging, which differ in the way of obtaining the weight components . i In this paper, the method of ordinary kriging is considered. This type of kriging is the most common for spatial data modeling, and is considered the best as it minimizes the estimation error variance.
The estimation process begins with the construction of an empirical variogram, for all pairs of locations separated by distance h:
After the spatial description is obtained, in order to make a prediction we need to determine the most appropriate variogram model (a curve that models the empirical variogram trends). In this paper, the following models are considered:
1) linear:
2) circular:
3) spherical:
Here,
The characteristics for model description are shown in figure 1. As can be seen from the figure, the nugget is a point at which semivariogram intersects the ordinate axis, and the threshold is the value at which the model starts to equalize. The distance to the threshold is called the range of influence. There is no spatial autocorrelation among points outside the range. The selected model allows to assign weights for the reference points and to estimate the unknown values. It should be noted that there is no universal model suitable for all input data. As a rule, the model is selected experimentally.
The interpolation method based on a triangulated irregular network (TIN) uses triangulation of data points to produce a two-dimensional function estimating the unknown values within each triangle [9].
Generally, an irregular network is obtained using the Delaunay triangulation [10]: points are connected with line segments in such a way that for any triangle obtained, all the points, except its vertices, lie outside the circumcircle of this triangle. Compared to other triangulation methods, Delaunay triangulation has several advantages: 1) the resulting triangles are close to equiangular, which makes it possible to reduce the numerical accuracy problems that can potentially arise in case of dividing the surface into long narrow triangles; 2) any point on the surface is located close to the reference point; 3) it does not depend on the point processing order. Thus, triangulation allows to obtain the appropriate reference points for each unknown point. When the triangulated irregular network is constructed, we can accurately estimate the unknown values by applying any standard interpolation method within each triangle.
In this paper, the triangulated irregular network is constructed using Delaunay triangulation, and interpolation is performed by the following standard methods [11]:
1) linear; 2) cubic; 3) nearest neighbour; 4) natural neighbour.
The practical applicability of spatial interpolation methods, described in this paper, is demonstrated on the example of binary images. The test images were converted to partially defined by removing 30, 50 and 70 percent of the pixels. The location of pixels to remove was selected using a pseudo-random number generator. The original and the resulting partially defined images are shown in figure 2. Here, the undefined pixels are indicated in gray. (f) "Ornament", 30% pixels removed; (g) "Ornament", 50% pixels removed; (h) "Ornament", 70% pixels removed.
To evaluate the quality of interpolation methods, we calculated the fraction of pixels matched for the original and interpolated images.
It is necessary to take into account that the image, obtained after interpolation, is halftone, while the original image is binary. To provide an accurate comparison, the resulting halftone images were converted into binary by thresholding. The comparison results for three interpolation methods are given in Table 1. 1 it is evident that in the case of the "Mickey" image, where the object and background are clearly distinguishable, all methods show approximately the same result for certain parameters. For the "Ornament" image, the kriging method demonstrates the best result, while the IDW method proved to be the least accurate. However, in the case of 70% removed pixels, the quality of all interpolation methods decreases significantly for both images.
The best results for each interpolation method are represented as halftone images in Table 2. 3 also shows the best interpolation results obtained for each method, but the images are converted to binary using the thresholding procedure.
It can be seen from Tables 2 and 3 that in the case of 30% removed pixels, all the methods demonstrate an excellent result, and it is almost impossible to distinguish a small difference in quality. When 50% of the pixels are removed, the interpolation quality for the "Ornament" image slightly decreases. The 70% pixel removal significantly reduces the quality of all methods for both images.
On the whole, Tables 2 and 3 confirm the results of Table 1. Thus, according to the experimental results, it can be concluded that all the investigated methods can be used for interpolation of partially defined images, but it should noted that there is no single interpolation method suitable in all situations: all methods have advantages and disadvantages. In practice, the choice of a particular interpolation method (and also the choice of parameters) should depend on the sample data and the error tolerance.
In this paper, three spatial interpolation methods are investigated: inverse distance weighting, interpolation based on a triangulated irregular network, and kriging. The practical applicability of these methods in the task of estimating the missing pixels of partially defined images is analyzed. The experiments show that all three methods can be used for solving the image processing problems, but the result of pixel prediction depends on the input data characteristics, such as the number of reference points. Hence, to provide the better results, the interpolation method should be selected separately for each input image.