A Comparative Study of Restoration Techniques for Images Defined by Chaotically Scattered Point Set Aleksey Maksimov Yuliya Vybornova Department of Geoinformatics and Information Security Department of Geoinformatics and Information Security Samara National Research University Samara National Research University Samara, Russia Samara, Russia aleksei.maksimov.ssau@gmail.com vybornovamail@gmail.com Abstract—Fast interpolation algorithms suggest that the Hilbert-Peano [7] curves. The triangular partition is value at a particular element of the image is calculated based constructed using the Delaunay triangulation [8]. on some neighborhood, the choice of which can significantly affect the interpolation result. In this paper, we investigate how III. EXPERIMENTAL STUDY the choice of reference image elements affects the quality of interpolation methods. Three classical interpolation methods A. Restoration quality (Linear, Nearest Neighbor, and Cubic) as well as two well- In this paper, the test images are reconstructed from a set known spatial interpolation methods (Inverse Distance of randomly located pixels, and the mean square error (MSE) Weighting and Akima) are considered. Results of the is calculated depending on the fraction of reference points. experimental research, such as the dependencies of RMSE on the noise proportion in test images, are presented, as well as As the test set the Waterloo Greyscale Set 2 [9] is used. computational complexity assessment. Test images are shown in Fig. 1. Keywords—Comparative Study, Low-Level Processing, Filtering, Still Images, Image Restoration, Interpolation, Delaunay Triangulation, Morton Curve, Hilbert-Peano Scan I. INTRODUCTION 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 Fig. 1. Test images of the Waterloo Greyscale Set 2. methods are based on the function of statistical spatial similarity. Their main advantage is sensitivity to For this set, a set of pseudo-random masks with a normal multidirectional data. Therefore, such methods are mostly distribution and a fraction of punctured samples (noise) from used to interpolate various kinds of surfaces. 0.1 to 0.9 with a step of 0.1 was generated. Masks are shown Fast interpolation algorithms suggest that the value at a in Fig. 2. certain location on the image is predicted using several nearest points, instead of the entire set of known values. The experimental study was carried out as follows. A mask was applied to the test image, after which the image Thus, in this paper, a comparative analysis of existing with punctured samples was interpolated by one of the interpolation methods is given, taking into account the selected methods. After, the RMSE of the interpolation was choice of a specific algorithm for the construction of a calculated relative to the original image. reference point set. II. METHODS UNDER INVESTIGATION 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 Fig. 2. Masks used in the experimental study (punctured pixels are black). Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) Image Processing and Earth Remote Sensing 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 and Fig. 4. Fig. 4. Dependence of interpolation MSE on fraction of reference points with the use of Akima method. a a b b Fig. 5. Dependence of interpolation MSE on fraction of reference points for IDW with a) a constant radius, b) a constant power. 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. c As can be seen from the presented results, in the case of Fig. 3. Dependence of interpolation MSE on fraction of reference points the one-dimensional methods for construction of the with the use of a) nearest neighbor interpolation, b)linear interpolation, c) reference point set, the use of the Hilbert-Peano curve cubic interpolation, d) Akima method. provides the smallest MSE for the nearest neighbor, linear and cubic interpolation, and also when using the Akima Also, for the IDW method, the dependences of the MSE method. However, the use of the Hilbert-Peano curve still on the noise fraction were studied for various settings of the shows the greater error than the use of a two-dimensional algorithm: with a constant power p and a variable radius r, partition based on the Delaunay triangulation. As for the and with a constant radius r and a variable power p. The interpolation methods, a significant advantage in terms of the dependencies are shown in the Fig. 5. mean square error of restoration can be obtained when using the Inverse Distance Weighting method. VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 142 Image Processing and Earth Remote Sensing TABLE I. COMPUTER PARAMETERS Parameters of computing machine Parameter value Model Intel Core i5 3470 Processor Number of cores 4 Clock frequency 3.20 GHz RAM size 8 GB TABLE II. AVERAGED OVER THE TEST SET PROCESSING TIME OF ONE IMAGE a b Average image Method processing time, sec 1a. Nearest neighbor interpolation, 0.0777 progressive scan 1b. Nearest neighbor interpolation, zig-zag 0.1087 scan 1c. Nearest neighbor interpolation, Morton 0.0870 curve 1d. Nearest neighbor interpolation, Hilbert- 0.1189 Peano curve 1e. Nearest neighbor interpolation, Delaunay 1.2409 triangulation 2a. Linear interpolation, progressive scan 0.1165 c d 2b. Linear interpolation, zig-zag scan 0.1124 2c. Linear interpolation, Morton curve 0.0751 Fig. 6. Examples of reconstructed images with 80% puctured pixels for 2d. Linear interpolation, Hilbert-Peano curve 0.1271 “peppers.tif” image of the test set with the use of interpolation method a) 2e. Linear interpolation, Delaunay 1a; b) 2d; c) 3e; d) 4a (the index corresponds to the interpolation methods 1.0566 triangulation listed in Table II). 3a. Cubic interpolation, progressive scan 0.0770 3b. Cubic interpolation, zig-zag scan 0.1141 3c. Cubic interpolation, Morton curve 0.0861 3d. Cubic interpolation, Hilbert-Peano curve 0.1235 3e. Cubic interpolation, Delaunay 1.3289 triangulation 4а. Akima, progressive scan 0.0501 4b. Akima, zig-zag scan 0.0737 4c. Akima, Morton curve 0.0577 4d. Akima, Hilbert-Peano curve 0.0709 5. IDW with radius = 4 and power = 5 505.0556 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. IV. CONCLUSION This paper is aimed at solving the problem of restoration Fig. 7. Dependences of the interpolation MSE on the reference point of images defined by a set of randomly scattered points. We fraction for the considered interpolation methods using parameters that investigate five widely known interpolation methods: three demonstrated the lowest MSE in the dependences shown in Fig. 3-5. classical (the nearest neighbor, linear and cubic), the Inverse Distance Weighting method, and Akima, which are B. Computational Complexity implemented using various methods for construction of the The analysis of the computational complexity of the reference point set. investigated methods is performed. The parameters of the computing machine are shown in Table I. The graphic For the classical methods and the Akima method, the accelerator was not used during the experimental study. The dependences of the Mean Square Error (MSE) on the average processing time for one image of the test set is fraction of reference points are estimated using various shown in Table II. techniques of the reference point set construction. Similar dependencies are calculated for the IDW method performed VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 143 Image Processing and Earth Remote Sensing for various parameters of radius and power. In addition, the [3] D. Shepard, “A two-dimensional interpolation function for performance of investigated methods is evaluated. irregularly-spaced data,” ACM: Proceedings of the 23rd ACM national conference, pp. 517-524, 1968. The IDW method demonstrates the lowest MSE and the [4] H. Akima, “A new method of interpolation and smooth curve fitting highest average processing time. For classical methods, the based on local procedures,” Journal of the ACM (JACM), 1970. lowest MSE is achieved when using Triangulated Irregular [5] R. Candra, “The Implementation of an Efficient Zigzag Scan,” Network. Journal of Telecommunication, Electronic and Computer Engineering, vol. 9, no. 2, pp. 95-98, 2017. ACKNOWLEDGMENT [6] G. Jin, “SFCGen: A framework for efficient generation of multi- dimensional space-filling curves by recursion,” ACM Transactions on The reported study was funded by RFBR (Russian Mathematical Software, vol. 31, no. 1, pp. 120-148, 2005. Foundation for Basic Research): projects № 19-07-00474, [7] V.V. Sergeev, “Image Processing Using Hilbert-Peano Scanning,” № 19-31-90113, № 19-29-09045. Optoelectronics, Instrumentation and Data Processing, vol. 2, pp. 29- 34, 1984. REFERENCES [8] B. Zalik, “An efficient sweep-line Delaunay triangulation algorithm,” [1] Y.D. Vybornova, “Application of spatial interpolation methods for Computer-Aided Design, vol. 37, pp.1027-1038, 2005. restoration of partially defined images,” CEUR Workshop [9] Greyscale Set 2. The Waterloo Fractal Coding and Analysis Group: Proceedings, vol. 2210, pp. 89-95, 2018. Image Repository, 2009 [Online]. URL: http:// [2] M.V. Gashnikov, N.I. Glumov, A.V. Kuznetsov, V.A. Mitekin, links.uwaterloo.ca/Repository.html. V.V. Myasnikov and V.V. Sergeev, “Hyperspectral remote sensing data compression and protection,” Computer Optics, vol. 40, no. 5, pp. 689-712, 2016. DOI: 10.18287/2412-6179-2016-40-5-689-712. VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 144