{'fraction_non_alphanumeric': 0.02130594727161251, 'fraction_numerical': 0.005824647455548743, 'mean_word_length': 4.857271095152603, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
P-HGRMS: A Parallel Hypergraph Based Root Mean Square Algorithm for Image Denoising

This paper presents a parallel Salt and Pepper (SP) noise removal algorithm in a grey level digital image based on the Hypergraph Based Root Mean Square (HGRMS) approach. HGRMS is generic algorithm for identifying noisy pixels in any digital image using a two level hierarchical serial approach. However, for SP noise removal, we reduce this algorithm to a parallel model by introducing a cardinality matrix and an iteration factor, k, which helps us reduce the dependencies in the existing approach. We also observe that the performance of the serial implementation is better on smaller images, but once the threshold is achieved in terms of image resolution, its computational complexity increases drastically. We test P-HGRMS using standard images from the Berkeley Segmentation dataset on NVIDIAs Compute Unified Device Architecture (CUDA) for noise identification and attenuation. We also compare the noise removal efficiency of the proposed algorithm using Peak Signal to Noise Ratio (PSNR) to the existing approach. P-HGRMS maintains the noise removal efficiency and outperforms its sequential counterpart by 6 to 18 times (6x - 18x) in computational efficiency.


INTRODUCTION
To overcome limitations in the existing spatial image filtering and noise removal algorithms, Kanna [1] proposed the HGRMS technique which uses Hypergraph based Root Mean Square approach for Salt and Pepper (SP) noise removal. HGRMS is a generic approach, which models the input image using Image Neighborhood hypergraph (INHG) parameters alpha, beta (α, β) to identify the noisy pixels. The identification of noisy hyperedge (NH) involves two sequential operations such that the NH should satisfy the property of isolated hyperedge and its cardinality equal to one. This causes severe performance penalties in computation.

PROPOSED ALGORITHM
Our noise reduction algorithm works on the following criterion: binary classification of hyperedges of an image (H0 noisy hyperedge and H1 no noisy hyperedge) and filtering the noisy parts. To modify the existing algorithm we propose the use of a cardinality matrix, and updating the image to remove the noise based on the values in the cardinality matrix. The cardinality matrix is generated based on the alpha, beta (α, β) neighborhood of the pixels in an image. The cardinality matrix serves as a platform to exploit parallelism using CUDA threads to update the original image with the Root Mean Square value of its corresponding beta neighborhood pixels. We preserve the image adaptive nature of the existing algorithm by introducing a new parameter, known as iteration factor, k. In our approach, to parallelize the algorithm, we iterate over the modified pixel values until there is no alpha-beta noise remaining in the image based on the iteration factor. Algorithm 1 illustrated below is used to form the cardinality matrix of the image I. The cardinality matrix is formed by finding the cardinality of each pixel, i.e. counting the number of closed neighborhood alpha-beta pixels with respect to that pixel in I. The cardinality number of each pixel is saved in another matrix, which we call the cardinality matrix, C.
Each CUDA thread computes the cardinality value of a pixel in image in parallel with other CUDA threads depending on its threadIdx and blockIdx value. Thus Cardinality matrix, C is generated in parallel. In algorithm 2, for each cell in C, if cardinality is found to be less than the threshold value, 3, we find the open neighborhood alpha-beta of the pixel in I, and count the number of pixels which exceed this value. If the count exceeds threshold value, we replace identified noisy pixel by Root Mean Square value of open neighborhood of this pixel in a temporary image matrix, I'. The temporary matrix enables us to remove data race conditions. Once all the CUDA threads are synchronized, we copy the temporary image matrix to original image matrix. We repeat the above steps until no further noise remains with respect to alpha and beta. We iteratively call algorithm 1 and algorithm 2 one after another until no further noise remains with respect to alpha and beta.
The iteration factor, k, helps us to control the number of iterations. The number of times algorithm 1 and algorithm 2 are called in succession depends on this iteration factor, k. This factor is necessary to preserve the image adaptive nature of HGRMS algorithm. The value of k is dependent on the INHG parameter, β. For our computation, we use k=5.

EXPERIMENTAL RESULTS
The existing algorithm HGRMS was implemented and tested on a system with an Intel Core i5 Processor with 4 GB of RAM. For the GPU implementation we used and Amazon AWS cluster, having 2 X NVIDIA Tesla M2050 GPUs having 1690 GB of instance storage and 22 GiB of memory. The images are acquired from the Berkeley Segmentation dataset [2]. Table 1 shown above gives us the run time of both algorithms with image noise levels ranging from 5 % to 20 %. It is evident from the results that a change in noise level does not significantly impact the performance of the proposed algorithm. This was expected as our algorithm is dependent on the size of the image, irrespective of any other factor.
Restoration performance is quantitatively measured by the peak signal-to-noise ratio (PSNR). Table 2 shown above compares PSNR values of the existing HGRMS algorithm and the proposed P-HGRMS algorithm.

CONCLUSION:
In this paper, we proposed a two phase parallel algorithm for noise filtering in images with preserving the image details. Our results show that the proposed algorithm outperforms its existing Hypergraph based root mean square approach. It is worth mentioning that when images are contaminated with high SP noise, the proposed scheme is able to clean images quiet efficiently without loss of image details. The proposed algorithm in this work is highly performance efficient as compared to its serial implementation. Even at higher noise ranges of 20 % the algorithm performed as efficiently as its serial counterpart.
This algorithm represents a very fast and promising approach in denoising salt and pepper noise in digital images. Future work includes reducing processing time further by testing with the MPI implementation and superior hardware capabilities. We also plan to devise a mechanism where the algorithm would itself decide the iteration factor, k, based on the input image, rather than a pre-defined iteration factor.