=Paper=
{{Paper
|id=Vol-2665/paper32
|storemode=property
|title=A comparative study of restoration techniques for images defined by chaotically scattered point set
|pdfUrl=https://ceur-ws.org/Vol-2665/paper32.pdf
|volume=Vol-2665
|authors=Yuliya Vybornova,Aleksey Maksimov
}}
==A comparative study of restoration techniques for images defined by chaotically scattered point set ==
https://ceur-ws.org/Vol-2665/paper32.pdf
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