The algorithm of the impulse noise filtration in images based on an algorithm of community detection in graphs
S. V. Belim S. B. Larionov



The algorithm of the impulse noise filtration in images based on an algorithm 
of community detection in graphs 






S.V. Belim, S.B. Larionov

Dostoevsky Omsk State University, Omsk, Russia

 






Abstract


This article suggests an algorithm of impulse noise filtration, based on the community 
detection in graphs. The image is representing as non-oriented weighted graph. Each pixel 
of an image is corresponding to a vertex of the graph. Community detection algorithm 
is running on the given graph. Assumed that communities that contain only one pixel 
are corresponding to noised pixels of an image. Suggested method was tested with help of computer 
experiment. This experiment was conducted on grayscale, and on colored images, on artificial 
images and on photos. It is shown that the suggested method is better than median filter by 20%
regardless of noise percent. Higher efficiency is justified by the fact that most of filters are
changing all of image pixels, but suggested method is finding and restoring only noised pixels. 
The dependence of the effectiveness of the proposed method on the percentage of noise 
in the image is shown.

Keywords: noise reduction in images, community detection in graphs.



§ INTRODUCTION


Impulse noise in the graphical images is looks like random change of  color of some random 
pixels, that called damaged pixels <cit.>. The presense of noise in the image affects 
not only on the visual perception, but also affects the results of image segmentation algorithms,
contour highlighting, pattern recognition, etc.

There are a lot of smoothing filters are existing for reduction of noise. Most often used are
Wiener filter and median filter <cit.>. One need to point out a non-local filtration methods
<cit.>, that demonstrate a better impulse noise reduction. Nevertheless, smoothing 
filters has a significant disadvantage: they changing the whole image and not only the damaged
pixels. This changes are lead to smoothing of contours of the image and make it difficult to
additional processing.

To minimize the impact of filter on the non damaged part of the image, one can use an approach 
based on searching pixels that has changed by the impulse noise. Objective of searching 
the damaged pixels is a very complex problem and solving as a rule by using Data Mining on the 
image. In this approach the algorithm of the impulse noise reduction is consists of two steps. 
The first step is a finding of damaged pixels. And the second is choosing color for each damaged pixel.

Algorithms of damaged pixel searching can be divided into 2 groups. The first group is intended 
to search a Solt & Pepper Noise (SPN). The feature of this type of noise is that damaged pixels 
can have only maximum or minimum color of the palette. So, the SPN algorithms are based on this 
information <cit.>. However, either this type of algorithms is not guarantee that 100% 
of damaged pixels will be found. The second group is oriented on the impulse noise with random
values. For this group, algorithms based on scheme SD-ROM are most widely used <cit.>. 
The main idea of the SD-ROM scheme is that pixels are analyzing within a sliding window with size
of 3× 3 and a decision is made about the corruption of the central pixel. The decision
algorithm in SD-ROM is based on the threshold circuit. A decision algorithm, based on the 
hierarchy analysis method has suggested in the paper <cit.> wherein the sliding window 
is still using. In the paper <cit.> for damaged pixels searching the method of associative
rules has used. In the paper <cit.> for damaged pixels searching, an image segmentation
algorithm is using.

Algorithms of impulse noise filtration with a known list of damaged pixels are reduced to filling
out a table with omissions.  The easiest way is to choose color based on colors of the nearest
neighbors. This method is produce good results on the areas with uniform fill, but not acceptable
in case of sharp color transitions, since it leads to blurring of the boundaries. Much more
acceptable approach based on the linear manifolds <cit.>. Additionally, the neural networks 
can be used for impulse noise filtration.

As shown by the analysis of previous works, methods based on the analysis of the entire image
provide better impulse noise reduction then local methods. The purpose of this article is to
implement and test an algorithm for impulse noise filtration based on the method of community
detection in graphs, which has proved itself in the task of image segmentation <cit.>.



§ FORMULATION OF THE PROBLEM AND FILTRATION ALGORITHM


Its assumed that the input of the algorithm is an image damaged by impulse noise with size 
of NM pixels. There is a pair of integers (x,y) is used to determine a location of pixel 
on the image, that represents coordinates of this pixel. The number x takes integer values 
on the interval [0, N  1], y takes integer values on the interval [0, M  1]. 
In a case of colored image, a pixel with coordinates (x, y) is characterized by 3 color
components: r(x, y) – intensity of a red color, g(x, y) – intensity of a green color, 
b(x, y) – intensity of a blue color.

Lets correspond the weighted, unoriented graph G to the image. Each pixel of the image is
corresponding to a vertex in the graph G. Each vertex has an edges only to all nearest 
neighbors. The weight of an edge is calculated based on the color components of connected 
vertexes. For two neighbor vertexes v_i = (x_i, y_i) and v_j = (x_j, y_j), the weight 
of the edge will be equal to:

    d(v_i,v_j)=exp(-1/h√((r_i-r_j)^2+(g_i-g_j)^2+(b_i-b_j)^2)),

Here, r_i = r(x_i, y_j), g_i = g(x_i, y_i), b_i = b(x_i, y_i). Parameter h is used 
to change the difference between neighbor pixels, corresponding to moving into another segment 
of the image. This parameter is setting by user and used for the whole image. As it shown 
in paper <cit.> this kind of weight function allows to accurately distinguish the 
color change corresponding to the boundaries of the areas in the image. Lets split the graph 
on insets with vertexes that connected much more than others. Such kind of insets are called
communities. A quantitative estimation of the split can be obtained by Newmans modularity 
function <cit.>. Greater value of the modularity function means more qualitatively 
the partition is performed. Assumed that damaged pixels are pixels that decrease value of the
modularity function during connection to other communities. This way one can select communities
that contain only one vertex, i.e. vertexes that different from each other a lot. Lets describe
this procedure more formal.

Lets define a matrix of weights E for graph G. The values of diagonal elements E_ij 
are equal to weight of vertexes. At the first step of the algorithm assume that the weight 
of all vertexes are equal to 0. Other elements of the matrix E_ij (i≠ j) are equal 
to a weight of a corresponding edge. One should point out that matrix E_ij will contain 
a lot of non-zero elements because of only nearest neighbor vertexes are connected with edges 
in graph G. The matrix E will be symmetric with respect to the main diagonal because 
of graph G is non-oriented. Lets move to the reduced view of the matrix of weights 
e = E/m, where m=∑_i,j=1^MNE_ij. The element e_ij is equal to a part 
of edge weight in the whole graph weight. Further one can assume that matrix of weight 
will have a reduced view. Its easy to see that ∑_i,j=1^MNe_ij=1.

Modularity is defined as <cit.>:

    Q(G)=∑_i=1^Ke_ii-∑_i=1^Ka_ib_i,

where K is a count of vertex in graph, a_i – reduced outbound power of the vertex v_i
(a_i=∑_j=1,j≠ i^Ke_ij), b_i – reduced inbound power of the vertex v_i
(b_i=∑_j=1,j≠ i^Ke_ji). Given graph is non-oriented, so outbound and inbound 
power of all vertexes are equal (a_i = b_i; i = 1, ..., K). Modularity function will have 
a more simpler representation:

    Q(G)=∑_i=1^Ke_ii-∑_i=1^Ka_i^2.


Lets use a screeding procedure to find communities in the graph. Assumed that screed is 
a transformation that replace some inset H of graph G to a some vertex v_H. 
If some of vertexes of inset H has been connected by edge with vertex v from 
inset G∖ H, then the vertex v_H will be connected by edge with same weight with 
vertex v. The weight of the new edge will be equal to a sum of weights of vertexes and edges that was included to the inset H. Lets name a new graph as G_H. Lets assume that inset H 
is a community if Q(G_h) > Q(G). Lets point it out that during creation of screed, the count of graph vertexes (K) is decreasing. The main task is to find vertexes that not included to any 
big community. To find such vertexes lets use the following algorithm:

1. Consecutive ircumvention of all pixels of the image.

2. For each pixel v lets consider nearest neighbor pixels v^(i) (i = 1, ..., 8). 
Consider insets that contains two vertexes v and v^(i) (i = 1, ..., 8) 
and try to connect then into community. For each try lets calculate a delta of modularity 
function Δ Q_i (i = 1, ..., 8).

3. If delta of modularity function is negative (Δ Q_i<0, i = 1, ..., 8), assumed 
that corresponding pixel is damaged.

The delta of modularity function can be computed fast using current characteristics of the graph
that correspond to an image. For connect to vertexes lets use the following representation 
of the delta of modularity function:

    Δ Q=2(e_ij-a_ia_j).


Its obviously that suggested algorithm has linear complexity depending on pixel count.

After finding of damaged pixels one need to choose a color for all of found pixels depending 
on neighbor pixels analysis. Assume that minimal value of the color component of the
neighbor pixels is m_1, and maximum value is m_2. Lets carry out a sequential search 
all of the values of damaged pixel color from m_1 to m_2. For each value lets calculate 
delta of the modularity function Δ Q. As a result color lets use the one that takes 
a maximum value of the modularity function delta.



§ COMPUTER EXPERIMENT


Computer experiment has carried out on artificial images of geometric objects and on color photos. 
The value of the impulse noise has been characterized by p, which shows a percent of damaged pixels 
related to a whole pixel count. Impulse noise was generating with help of linear congruent generator 
of pseudo-random numbers. This generator was used both to generate colors and coordinates. During 
computer experiment the percent of damaged pixels has changed from 10% to 70%. Image filtration has carried out using suggested method and additionally using a well-known median filter.

To compare the proximity of images there is a Minkovskiy metric <cit.> has been used
according to which the proximity between images A and C is calculating using the following
formula:

    d(A,C)=max_n,m∑_k=1^N1/N|A_nm^(K)-C_nm^(K)|,

where A_nm and _nm – values of A and 
    image pixel colors, N– count of pixels.
    
    Relative image enhancement has been calculated based on distance d(orig, r) from reconstructed
    image r to original image orig and distance d(orig, pf) from damaged image pf to original image orig:
    
        δ=d(orig, pf)-d(orig, r)/d(orig, pf)· 100%.
    
    
    Experiment for a rectangular area with uniform filling showed that the proposed filter allows 
    to significantly improve the image. The dependence of the relative improvement on the percentage 
    of corrupted pixels for the proposed filter and the median filter is shown in Fig. 1.
    
    
    
    The results of applying the proposed filter and the median filter to improve the artificial image
    with the presence of a solid and gradient fill are shown in Fig. 2.
    
    
    
    As can be clearly seen from Fig. 2, the results of the proposed filter are more advantageous for
    dark areas of the image, whereas the median filter gives the best visual result for the light 
    part of the image. This effect is a related to that new color is choosing for the damaged pixel.
    When using the median filter, the colors of the restored pixels are shifted to a white area. In
    this case, the colors of the surrounding pixels also change their color. Numerical comparison of
    the results of the work shows a significant advantage of the proposed algorithm in front of the
    median filter.
    
    The dependence of the relative improvement on the percentage of noised artificial image is shown 
    in Figure 3.
    
    
    
    Additionally the proposed filter allows to get much better results for photographic images. 
    The results for the well-known  image Lena with a p = 20% are shown in Fig. 4.
    
    
    
    It is well known that the Lena image is characterized by a large number of small details 
    that create difficulties for all filters. As can be seen from Fig. 4, the proposed filter 
    gives significantly better results even in a visual comparison. The dependence of the relative
    improvement on the percentage of noise is shown in Fig. 5.
    
    
    
    § CONCLUSION
    
    
    Thus, the proposed filter has good characteristics with linear labor input. As can be seen from 
    the graphs presented in Figures 1, 3 and 5, the efficiency of this filter is approximately 20%
    higher than the median for any percentage of damaged pixels. This noticeable advantage is due to
    the fact that conventional filters change all pixels of the image. Correcting the damaged pixels
    brings the image closer to the original, but changing the undamaged pixels increases the distance
    to the original. This property is inherent not only to the median filter, but also to all
    traditional filters.
    
    The filter proposed in this article acts selectively and changes only those pixels that differ
    significantly from those around them. With a high probability, such pixels will be damaged by
    impulse noise. The choice of a new color on the basis of attaching to one of the neighboring
    communities of pixels allows to form communities of pixels close in characteristics. It should 
    also be noted the high speed of the filter, due to the linear complexity of the algorithm
    underlying it. The processing time of one image within the error is the same as the median filter.
    
    
    
    99b1
    Pitas I., Venetsanopoulos A. Nonlinear digital filters: principles and applications. Boston: Kluwer Academic Publishers, 1990. 391 p.
    b2
    Huang T. S.Two-dimensional digital signal processing II: transforms and median filters. Berlin a.o: Springer, 1981. 391 p.
    b3
    Boyle R., Sonka M., Hlavac V. Image processing, analysis, and machine vision, First Edition. University Press, Cambridge, 2008. 920 .
    b4
    Mitra S., Sicuranza G. Nonlinear image processing. Academic Press, 2001. 455 .
    b5
    Buades A., Morel J. A Non-local algorithm for image denoising. IEEE Computer Society Conference on Computer Vision and Pattern Recognition 2, Washington DC, 2005, pp. 6065.
    b6
    Dabov K., Foi A., Katkovnik V., Egiazarian K. Image denoising by sparse 3-D transform-domain collaborative filtering. IEEE Transactions on Image Processing, 2007, no. 8(16), pp. 20802095. doi: 10.1109/TIP.2007.901238
    b7
    Chan R., Ho C., Nikolova M. Salt-and-pepper noise removal by median-type noise detectors and detail-preserving Regularization. IEEE Transactions on Image Processing, 2005, no. 10(14), pp. 14791485. doi: 10.1109/TIP.2005.852196
    b8
    Kam H.S., Tan W.H. Noise Detection Fuzzy (NDF) flter for removing salt and pepper noise. IVIC 2009: Visual Informatics: Bridging Research and Practice, Kuala Lumpur, 2009. P. 479 – 486. 
    b9
    Najeer A. J., Rajamani V. Design of hybrid flter for denoising images using fuzzy network and edge detecting. American Journal of Science Research, 2009, no. 3, pp. 514.
    b10
    Abreu E., Lightstone M., Mitra S.K., Arakawa S.K. A new efficient approach for the removal of impulse noise from highly corrupted images. IEEE Transactions on Image Processing, 1996, no. 6(5), pp. 10121025. doi: 10.1109/83.503916
    b11
    Garnett R., Huegerich T., Chui C., He W. A universal noise removal algorithm with an impulse detector. IEEE Trans Image Proccess, 2005, no. 14(11), pp. 174754. doi: 10.1109/TIP.2005.8572.61
    b12
    Belim S. V., Seliverstov S. A. hierarchy analysis method as a way to detect impulse noise on images. Information Technologies, 2015, no. 4, pp. 251258.
    b13
    Belim S. V., Mayorov-Zilbernagel A. O. Algorithm for searching the broken pixels and eliminating impulse noise in images using a method of association rules. Science & Education, 2014, no. 12. Available at: http://technomag.bmstu.ru/doc/744983.html (accessed 08 February 2017) (In Russian). doi: 10.7463/1214.0744983
    b14
    Belim S. V., Kutlunin P. E. Impulse noise detection in images using a clustering algorithm. Herald of Computer and Information Technologies, 2016, no. 3, pp. 310. doi: 10.14489/vkit.2016.03.pp.003-010
    b15
    Larionov I. B. Multidimensional linear manifolds as a way to restore graphical information. Matematicheskie struktury i modelirovanie, 2010, no. 1(21), pp. 24-31 (In Russian).
    b16
    Larionov I.B. Kohonen maps as a way to restore the multimedia information. Zhurnal radioelektroniki, 2010, no. 10, p. 29.
    b17
    Belim S.V., Mayorov-Zilbernagel A.O. Image restoration with static gaps on the basis of association rules. Herald of Computer and Information Technologies, 2014, no. 12, pp. 1823. doi: 10.14489/vkit.2014.12.pp.018-023
    b18
    Belim S. V., Seliverstov S. A. The analytic hierarchy method-based algorithm for restoring broken pixels on the noisy images. Science & Education, 2014, no. 11. Available at: http://technomag.bmstu.ru/doc/742145.html (accessed 20 January 2017) (In Russian). doi: 10.7463/1114.0742145
    b19
    Belim S. V., Larionov S. B. An algorithm of image segmentation based on community detection in graphs. Computer Optics, 2016, no. 6, pp. 904910. doi: 10.18287/2412-6179-2016-40-6-904-910
    b20
    Newman M. E. Analysis of Weighted Networks. Physical Review E, 2004, vol. 70, no. 5, p. 056131. doi: 10.1103/PhysRevE.70.056131
    b21
    Clauset A., Newman M. E. J., Moore C. finding community structure in very large networks. Physical Review E, 2004, vol. 70, no. 6, p. 066111. doi: 10.1103/PhysRevE.70.066111
    b22
    DiGesu V., Staravoitov V. V. Distance-based functions for image comparison. Pattern Recognition Letters, 1999, vol. 20, pp. 207213. doi: 10.1016/S0167-8655(98)00115-9
    b23
    Jong-hyun Ryu, Sujin Kim, Hong Wan. Pareto front approximation with adaptive sum method in multiobjective simulation optimization. Proc. of the 2009 Winter Simulation Conference (WSC), 2009, Austin, pp. 623633.
