The purpose of this paper is to analyze the practical applicability of spatial interpolation methods in the task of estimating the missing pixels of partially defined images. The paper presents three methods of spatial interpolation: inverse distance weighting, interpolation based on a triangulated irregular network, and kriging. The results of experimental research on these methods are given. Experiments show that all methods demonstrate a high quality of pixel prediction, but the choice of the most appropriate method directly depends on the input data.
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 [
The interpolation techniques known today can be classified into deterministic and statistical [
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 [
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 [
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:
m z(s0 ) wi z(si ) i1 m i1 d0jp
j1 m z(si )d0ip , where z(s0 ) is an estimated value of a point in a certain location s0 , and z(s1), z(s2 ), , z(sn ) – reference point values.
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 wi 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 [
To date, research on kriging in image processing tasks is limited to several publications [
n z(s0 ) i z(si ) ,
i1 , z(sn ) are the reference points, and z(s0 ) is a value of the point to be where z(s1), z(s2 ),
n evaluated. Also, it should be noted that i 1.
i1
The main task is to determine the weights i so as to minimize the variance of the estimate, taking into account the unbiasedness requirement E z(s0 ) z(s) 0 .
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:
V (h) average((z(si ) z(s j ))2 )
. 2
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: (h) c0 c1t ; 2) circular: (h) c0 c1 2
t 1 t 2 arcsin t ;
Here, t ah , a is a range of influence, c0 is a nugget, c0 c1 is a threshold.
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.
(a) (b) (c) (d)
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. p=2, r=4 p=2, r=5 p=2, r=6 p=2, r=7 p=2, r=8 p=2, r=9 p=2, r=10 linear nearest natural cubic linear circular spherical exponential gaussian stable
From Table 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.
TIN
Kriging % r=9 natural exponential p=5 natural exponential Table 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. natural exponential natural stable natural exponential natural
stable p=6 p=5 p=5 % natural exponential natural exponential
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.
Mitas L and Mitasova H 1999 Spatial interpolation Geographical Information Systems: Principles, Techniques, Management and Applications 1 481-492 Lee D T and Schachter B J 1980 Two algorithms for constructing a Delaunay triangulation International Journal of Computer and Information Sciences 9(3) 219-242 Dumitru P D, Plopeanu M and Badea D 2013 Comparative study regarding the methods of interpolation Recent Advances in Geodesy and Geomatics Engineering 1 45-52