One of the problems of image processing consists in predicting the values of raster cells given a certain limited number of input points on a two-dimensional grid. To solve this task interpolation methods are usually used [1].
Today, there are various interpolation methods, which can be divided into two classes: deterministic and statistical. The the deterministic methods are constructed on the basis of some distance (or area) function. The main advantage of such methods is the high processing speed. The statistical methods are based on the function of statistical spatial similarity. Their main advantage is sensitivity to multidirectional data. Therefore, such methods are mostly used to interpolate various kinds of surfaces.
Fast interpolation algorithms suggest that the value at a certain location on the image is predicted using several nearest points, instead of the entire set of known values. Thus, in this paper, a comparative analysis of existing interpolation methods is given, taking into account the choice of a specific algorithm for the construction of a reference point set.
In this paper, we study 17 methods of image reconstruction using a randomly scattered set of points.
Three classical interpolation methods (Linear [2], Nearest Neighbor [2], Cubic [2]) are compared with two well-known spatial interpolation methods: Inverse Distance Weighting (IDW) [3] and Akima [4].
For classical interpolation methods, the order of reference points is specified either by transition to a 1-D signal, or via 2-D triangulated irregular network. The transition to the 1-D signal is carried out based on progressive and zigzag scan [5], as well as Morton [6] and Hilbert-Peano [7] curves.
The triangular partition is constructed using the Delaunay triangulation [8].
In this paper, the test images are reconstructed from a set of randomly located pixels, and the mean square error (MSE) is calculated depending on the fraction of reference points.
As the test set the Waterloo Greyscale Set 2 [9] is used. Test images are shown in Fig. 1. For this set, a set of pseudo-random masks with a normal distribution and a fraction of punctured samples (noise) from 0.1 to 0.9 with a step of 0.1 was generated. Masks are shown in Fig. 2.
The experimental study was carried out as follows. A mask was applied to the test image, after which the image with punctured samples was interpolated by one of the selected methods. After, the RMSE of the interpolation was calculated relative to the original image. The results are averaged over the test set for a fixed fraction of reference points, the interpolation method, and the method of reference point set construction. The results of this experimental study are presented in Fig. 3 Also, for the IDW method, the dependences of the MSE on the noise fraction were studied for various settings of the algorithm: with a constant power p and a variable radius r, and with a constant radius r and a variable power p. The dependencies are shown in the Fig. 5. The examples of some restored images for the same fraction of reference points are presented in Fig. 6. The final dependencies are presented in Fig. 7.
As can be seen from the presented results, in the case of the one-dimensional methods for construction of the reference point set, the use of the Hilbert-Peano curve provides the smallest MSE for the nearest neighbor, linear and cubic interpolation, and also when using the Akima method. However, the use of the Hilbert-Peano curve still shows the greater error than the use of a two-dimensional partition based on the Delaunay triangulation. As for the interpolation methods, a significant advantage in terms of the mean square error of restoration can be obtained when using the Inverse Distance Weighting method. II).
The analysis of the computational complexity of the investigated methods is performed. The parameters of the computing machine are shown in Table I. The graphic accelerator was not used during the experimental study. The average processing time for one image of the test set is shown in Table II. As can be seen from Table II and Fig. 7, the Inverse Distance Weighting method provides the smallest mean square error but requires much longer processing time compared to all other methods (this case is denoted in bold). A compromise solution providing both an acceptable image restoration quality and average processing time can be obtained by constructing a set of reference points using Delaunay triangulation and predicting the missing values using the linear or cubic interpolation (italicized in Table II and denoted in red and light green in Fig. 7). It is shown that, these methods give similar values of MSE and processing time.
This paper is aimed at solving the problem of restoration of images defined by a set of randomly scattered points. We investigate five widely known interpolation methods: three classical (the nearest neighbor, linear and cubic), the Inverse Distance Weighting method, and Akima, which are implemented using various methods for construction of the reference point set.
For the classical methods and the Akima method, the dependences of the Mean Square Error (MSE) on the fraction of reference points are estimated using various techniques of the reference point set construction. Similar dependencies are calculated for the IDW method performed for various parameters of radius and power. In addition, the performance of investigated methods is evaluated.
The IDW method demonstrates the lowest MSE and the highest average processing time. For classical methods, the lowest MSE is achieved when using Triangulated Irregular Network.
The reported study was funded by RFBR (Russian Foundation for Basic Research): projects № 19-07-00474, № 19-31-90113, № 19-29-09045.