Digital image processing is widely used in various fields of science, such as medicine - Xray analysis, magnetic resonance imaging, computed tomography, cosmology - collecting information from satellites, their transmission and analysis. Image noise accompanies any of the stages of image processing - from obtaining them to segmentation and object recognition. In order to process large images in real time, the paper proposes to use CUDA technology to parallelize KNN and NLM algorithms. The subject area of the satellite images is selected for noise reduction. A comparative analysis of the effectiveness of the proposed approach. It is investigated how the computation time of successive versions of algorithms changes with increasing the size of the image itself. Based on a series of numerical experiments, it was possible to achieve an acceleration of 40 times using CUDA technology. It is shown that the calculations on the CPU significantly exceed the time spent on execution compared to the GPU. This is due to the fact that in tasks of this type, several threads on the CPU are not able to compete with thousands of threads of the graphics core. We can also observe that as the number of GPU threads increases, the time decreases significantly. This study is especially relevant in current trends in video cards. that in tasks of this type, several threads on the CPU are not able to compete with thousands of threads of the graphics core. We can also observe that as the number of GPU threads increases, the time decreases significantly. This study is especially relevant in current trends in video cards. that in tasks of this type, several threads on the CPU are not able to compete with thousands of threads of the graphics core. We can also observe that as the number of GPU threads increases, the time decreases significantly. This study is especially relevant in current trends in video cards.
Most images are affected by various types of noise caused by equipment failure, problems with
data transmission or compression, and natural factors. Therefore, the first stage of image processing is
filtering. The presence of noise in the image can cause inaccuracies and distortions in the
segmentation and recognition phase. For example, the system may perceive noise for individual
objects, which, in turn, will negatively affect further research. That is why noise removal is an
important problem in the field of image processing, which has many applications in various fields,
such as medicine (magnetic resonance imaging, computed tomography), industry, military
applications, space research, communications (satellite television) [
Most often, noise reduction is used to improve visual perception, but can also be used for
specialized purposes – for example, in medicine to increase the clarity of images on X-rays [
Despite the fact that noise reduction is a classic problem and has been studied for a long time, this task is still difficult and open. The main reason is that from a mathematical point of view, noise reduction is an inverse problem, so its solution is not unique. As a result, there are many different methods, the advantages and disadvantages of which will be discussed and analyzed in the next section.
Today there is a relevant area of image processing from satellites [
Based on the above, we can formulate the purpose of this work, namely, to conduct a comparative analysis of the effectiveness of parallel algorithms KNN and NLM based on CUDA technology to accelerate the noise of large-scale images obtained from satellite.
Significant results in the field of image noise reduction have been achieved in recent decades. This
is due to the wide range of applications in everyday life, as we are surrounded by more and more
digital devices: smartphones, webcams, surveillance cameras, drones and more. Accordingly, this
problem occurs in such areas as: satellite television, computed tomography [
Thus, image noise has remained a pressing issue for many researchers in recent times. To date,
many classical filtration algorithms have been proposed (Median Filtering, Linear Filtering,
Anisotropic Filtering) [
All linear filtering algorithms are optimal for Gaussian distribution of signals, interference and observed data, and lead to the smoothing of sharp differences in the brightness of the processed images. However, real images, strictly speaking, are usually not subject to this probability distribution.
Some of these problems are solved using non-parametric image processing methods. Studies have
shown that good results in image processing were obtained using median filtering [
One of the algorithms without the above disadvantages is Non-Local Means (NLM) [
Another effective algorithm, in terms of reducing noise and maintaining the informativeness of the
original image, is K-Nearest Neighbors [
So let's highlight the problem statement for our study:
Let Ω – image area, and and are two dots (pixels) within the image, then: is the Euclidean distance between image patches focused on and in accordance. where at the point ; is the filtered value of the image at the point ; is the unfiltered value of the image – this is the normalizing factor; is a weighing function in which ,
weight (importance), so the function and not just for .
, ,
This algorithm can be performed in two implementations: pixelwise and patchwise. In our work we use pixel implementation, because in fact there is not much difference between the two options, so the overall quality in terms of saving details is not improved with the use of patchwise all pixels in the patch
have the same can be used to mute all pixels in the patch implement them programmatically. algorithms with each other.
Develop a parallel algorithm of KNN and NLM methods based on CUDA technology and Test and compare the noise reduction results for each algorithm, as well as compare both Measure the execution time of each algorithm with a different configuration of the computer system for further calculation of acceleration and comparative analysis of efficiency.
Mathematically, the problem of image noise reduction can be modeled as follows: where – noisy input image, – unknown clear image without noise, and – is an additive of white Gaussian noise with standard deviation , which can be estimated in practice by various methods, such as the median of absolute deviations (MAD) [Ошибка! Источник ссылки не найден.3] or , the principal component algorithm (PCA) [Ошибка! Источник ссылки не найден.4].
The purpose of image noise reduction is to reduce distortion while minimizing the loss of original
features of the input image and increase the signal-to-noise ratio (SNR) [
Let's introduce the noise reduction of the color image , , and a specific pixel as ∑∈ , , , ∑∈ , , , where , denote the environment centered at the point with dimensions 2 1 2 The search area is limited by a square circumference of a fixed size, which is due to the limitation of 1, 2, 3 and
1 pixels.
. , 35 2
will depend on the Euclidean distance calculations. This is a window 21
21 for small and medium values . The window size increases to
35 for large values due to the need to detect more similar pixels to reduce additional noise.
, ,
average of the same pixel [
To calculate the weight
,
we will use the exponential function:
,
where indicates the standard deviation of the noise and ℎ is the filtering parameter set relative to the
value
12, 15 . The weight of the function is set to average similar noise patches. That is, patches
are installed to 1, while larger distances decrease faster due to the
based on the Gaussian Blur Filter algorithm [
Let
– the value of the input noisy image at the point , a
The weight of the reference pixel on average, is set as the maximum weight in the vicinity , . This parameter avoids excessive weighing of the reference point in the middle.
,
should be equal to 1 and as a result, more value will be required to reduce noise ℎ. Therefore, using the above procedure, we will be able to restore the noiseless value for each pixel .
To objectively assess the basic metrics of our noise reduction using the NLM algorithm, consider an additional algorithm – KNN [Ошибка! Источник ссылки не найден.6]. The main principle of KNN is that the category of the data point is determined according to the classification of the nearest neighbors. The KNN (k-Nearest Neighbors) filter was developed to suppress white noise, which is – the result obtained by the KNN filter with parameters ℎ and at some point . Ω is the space of a given size around the selected of this block.
Then pixel, i.e. it is a block of pixels in size the filtration formula can be represented as:
N, so that the selected pixel (dot ) is located in the center
, ∑ , where
– normalizing factor.
Since the purpose of our study is to accelerate the noise reduction of images using the GPU, for such purposes we will use CUDA [Ошибка! Источник ссылки не найден.]. Is a softwarehardware architecture of parallel computing, which allows you to significantly increase computing performance through the use of graphics processors from Nvidia. CUDA allows you to reduce the load on the processor, which gives significant benefits over time. Given the power of modern video cards, we can get a significant acceleration in the calculations. And because we will be working with images, this technology should be ideal for this type of task.
Both methods can be easily implemented using CUDA technology. Since this technology uses the SIMD parallel computing model [19], we do not need to parallelize the algorithm itself (NLM, KNN). It is enough to implement a standard version of the algorithm in the form of a kernel function. The kernel function is actually a normal sequential program, without organizing the launch of threads. Instead, the GPU runs many copies of a given function in different threads.
Consider in more detail the mechanism for organizing parallel calculations:
Host – CPU. Performs a control role – runs tasks on the device, allocates memory on the device, moves memory to/from the device.
Device – GPU. Performs the role of "subordinate" – does only what the CPU tells him.
Kernel – a task (NLM, KNN), which runs the host on the device.
Threads are grouped into blocks, in the middle of which they have shared memory and run (because algorithms split images into RGB color vector). The number of threads is equal 2 , where
1024, the maximum number of threads per block). The input noisy image is divided by blocks where , ∈ , ∈ , where – width, a – image height, respectively. Everyone
the grid block corresponds image the weight in a separate stream is calculated.
To conduct experiments, it was decided to develop a software product in the Python programming language. Accordingly, the PyCuda library was used to use the CUDA parallel computing architecture. As well as an OpenCV library for image processing. All calculations were performed in Google Colab [20],which allows you to write and execute Python code in a browser with a minimum of settings and free access to powerful computing capabilities. The configuration includes a graphics professor NVIDIA Tesla T4 with 2560 CUDA cores and 16 Gb of video memory and an Intel Xeon CPU with a clock speed of 2.20Ghz with two cores and two threads. an image block, where for each pixel of the
First, we evaluate the quality of both algorithms and evaluate the effect of noise reduction of various images. First we test the work of KNN.
Figure 1: Comparison of 1 image fragment before (left) and after (right) noise reduction using KNN algorithm Figure 2: Comparison of 5 fragments of the image before (left) and after (right) noise reduction using the KNN algorithm
Now let's perform the same tests for the NLM algorithm.
In addition, studies were performed on images of different dimensions and with different configurations of computing power to measure the runtime of algorithms with CPU/GPU comparison. The calculations were performed for images of different dimensions, where – the number of pixels in the image pixels, and for GPUs with different number of threads per block (4, 16, 64, 256 and 1024 threads, respectively). Figure 6: Execution time of parallel KNN algorithm using CPU/GPU in seconds for different image dimensions and with different program startup configuration
P
GPU 4
CPU tpb 0.062403 0.023235 0.230475 0.083275 0.853824 0.316450 3.264484 0.800226 13.059060 2.331046 23.748522 3.996524
GPU 16 tpb
We calculate the acceleration for the measurements of each algorithm. To do this, divide the execution time by CPU by the execution time by GPU.
P
P
Now let's analyze our experiments. To begin with, let's summarize the results of the noise reduction using each of the NLM and KNN algorithms.
As we can see from the above Figures 1-3, the algorithms reduce noise well and restore the original image even with loud noise. For comparison, in Figure 2 using the KNN algorithm, the image fragment after clearing loses the clarity of the contours, the image becomes slightly pixelated. At the same time in Figure 3 algorithm NLM visually makes less noise, so the image is still quite blurred, but the boundaries of the contours are not as violated as when noise reduction using the KNN algorithm. However, this is just one example, so don't judge by just one piece.
In Figure 4 shows that the image obtained with NLM, less clear compared to KNN. This is best seen in detail when looking at cars parked in the parking lot in the upper right corner of the image. Similar results can be observed in Figure 5. The image obtained during the KNN algorithm is clearer and richer. An example is the road marking lines at the bottom of the image, which in the first case, retained their geometry, not to mention the image on the right, where the lines are almost invisible, the image obtained by NLM was "blurred".
A similar problem is mentioned in [21], where the authors emphasize that in high-detail images, after the noise reduction with NLM, the geometry of objects deteriorates.
The next step is to analyze our program execution time metrics and GPU acceleration factors. For clarity, tests were performed on different image sizes. Therefore, it is clear from Table 1 and Table 2, that the largest time difference between CPU/GPU we get for scale images. This confirms the correctness of the choice of subject area for our task of accelerating noise reduction.
Considering the visualization in Figure 6 and Figure 7, respectively, we can see that the calculations on the CPU significantly exceed the time spent on execution compared to the GPU. This is due to the need for a large number of parallel calculations for image processing. For tasks of this type, multiple threads on the CPU are not able to compete with thousands of graphics core threads. We can also observe that as the number of GPU threads increases, the time decreases significantly.
In Table 3 and Table 4 there is a tendency to increase the rate of acceleration with increasing number of flows per unit. This is because the more threads, the fewer blocks, and therefore less time spent on memory operations.
Comparing the acceleration rates of both algorithms. We can see that the parallel NLM algorithm loses with a small number of threads, but wins with the largest number of threads per block. We can also see that the KNN algorithm does not receive such a large increase in acceleration as the NLM algorithm when increasing the image size for noise reduction from 45 million pixels to 81. This is well observed in Figure 8 and Figure 9, where the acceleration coefficient graph for the NLM algorithm grows faster than the KNN. Although KNN at 4 threads gets twice as fast as NLM.
If we compare the time spent on both algorithms, we can conclude that there is no clear favorite, although KNN shows better results with a small number of threads per block, due to the peculiarity of the algorithms. This can affect the results if the calculations are performed using older generation video cards, where the maximum possible number of threads per unit is many times less. In the conditions of use of modern video cards NLM, with the maximum number of threads, is ahead of the competitor.
This paper compares KNN and NLM algorithms in the context of parallel computations to accelerate the noise reduction of large images. To do this, using the Python programming language, implemented two algorithms with versions for CPUs and GPUs using the CUDA architecture.
In the course of the work, the results of each algorithm were analyzed and it was found that both algorithms cope well with the task of noise reduction and recovery of the original images obtained as satellite images.
Comparative tables are also constructed for each algorithm with a different configuration of the program start, in which you can evaluate the obtained time measurements and calculated acceleration rates. These data were visualized on graphs, which allowed us to objectively compare the obtained metrics. Regarding the obtained time metrics and acceleration metrics, we can conclude that parallel computing with CUDA on GPUs is many times better than computing on CPU. It is for these algorithms that the GPU and CUDA technology can achieve an acceleration of approximately 40 times. Thanks to these results, we can use algorithms such as KNN and NLM in real-time video processing. It will also save a lot of time on processing images obtained from telescopes and satellites, which are high resolution.
Conference on Advanced Computing and Communication Systems (ICACCS). (2017), pp. 1-6. doi:10.1109 / ICACCS.2017.8014612. [18] L. Mochurad, G. Shchur, Parallelization of Cryptographic Algorithm Based on Different Parallel Computing Technologies,. Proceedings of the Symposium on Information Technologies & Applied Sciences (IT&AS 2021). Bratislava, Slovak Republic, March 5. (2021), Vol-2824, 2029 p. [19] L. Mochurad, N. Boyko, Technologies of distributed systems and parallel computation: monograph. Lviv: Publishing House “Bona”, (2020), 261 p. [20] Google Colaboratory [Electronic resource] – Resource access mode:https://research.google.com/colaboratory/faq.html. [21] A. Buades, B. Coll, and J. Morel, On image denoising methods, Technical Report 2004-15, CMLA. (2004).