CELLULAR AUTOMATA BASED IDENTIFICATION AND REMOVAL OF IMPULSIVE NOISE FROM CORRUPTED IMAGES

Fasel Qadir; M. A. Peer; K. A. Khan

CELLULAR AUTOMATA BASED IDENTIFICATION AND REMOVAL OF IMPULSIVE NOISE FROM CORRUPTED IMAGES

Fasel Qadir¹, M. A. Peer², K. A. Khan³

Research Scholar , Kashmir
Chairman BOPEE Kashmir
Associate Professor Kashmir

Corresponding Author: Fasel Qadir, E-mail: faselqadir@gmail.com

Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Global Research in Computer Sciences

Abstract

Cellular Automata (CA) is a methodology that uses discrete space to represent the state of each element of a domain and this state can be changed according to a transition rule. Image noise is unwanted information of an image. Noise can occur during image capture, transmission or processing and it may depend or may not depend on image content. Noise reduction is one of the important processes in the pre-processing of digital images. Most primitive approaches used neighbour pixel values to replacement of noisy pixels. But these methods have a big disadvantage that they are applied on all the pixels, corrupted as well as un-corrupted pixels. So the images loosed vital texture such as edges. Recently researchers have been proposed classification based methods, in this case first identify the corrupted pixel and then replace it by the neighbour values whereas uncorrupted pixels remain unchanged. The proposed method first identifies the noise and then removes it from the corrupted image based on CA. To illustrate the proposed method, some experiments have been performed on several standard test images and compared with popular methods of filtering. The results show that the proposed method relatively has the desirable performance visibly as well as. First the concept of CA is introduced, and then accordingly to the structure of the neighbors, proposed model and then the experimental results.

Keywords

Cellular automata, Image Processing, Noise Filtering.

INTRODUCTION

Cellular automata (CA) are dynamical systems in which space and time are discrete. This basic theory of the classical CA was established by Von neumann [1]. Later, Stephen Wolfran developed the theory [2]. CA can simulate abundant and complicated process of evaluation and can be considered as a dynamics system whose dimension is infinite. CA models is more than an important model of computer theory and it is applied in the study of non-linear appearance and fractal structure in mathematics, physics, biology, chemistry, geography and economics.

In transmission process, the data value of input image will suffer from various kinds of noises. These sources of noise may come from external interferences, e.g. atmospheric noise, man-made noise, that will cause the perturbations to the system. These perturbations can produce the wrong information in system operation. The random disturbances in the images are shown as noise and are often caused by the malfunctioning pixels in camera sensors, faulty memory locations in hardware or transmission in the noisy channel.

The noises well reduce the quality of images and damage the expression of information for images effectively. Image filtering can effectively reduce the noise and make the image smooth. The common methods of image filtering in general are spatial filtering and frequency domain filtering. The goal of impulse noise removal is to suppress the noise while preserving the integrity of edge and detail information, to reduce the degradation related to noise of any kind, a pre processing or filtering step could be applied [3].

There has been a lot of effort in designing an efficient filtering algorithm. Median filter has been known to perform better in removing impulse noise than the linear filters [4][5]. Others are adaptive median filter [6] and progressive switching median [7]. In this paper, we present a filter based on cellular automata, which is used to remove impulse noise from noise-corrupted images [8] [9]. Our cellular automaton algorithm is applicable to both binary images and greyscale images, and show significant improvements over the performance of [8][9].

CELLULAR AUTOMATA

CA model is composed of cell, state set of cell, neighbourhood and local rule. Time advances in discrete steps and the rules of the universe are expressed by a single receipt through which, at each step computes its new state from that of its close neighbours. Thus the rules of the system are local and uniform. There are one- dimensional, two-dimensional and three-dimensional CA models. For example, a simple two-state, one dimensional CA consists of a line of cells, each of which can take value „0ÃÂ¢Ãâ¬ÃÅ¸ or „1ÃÂ¢Ãâ¬ÃÅ¸. Using a local rule (usually deterministic), the value of the cells are updated synchronously in discrete time steps. With a k-state CA model each cell can take any of the integer values between 0and k-1. In general, the rule controls the evolution of the CA model.

We can define a CA model as follows [9]:

A CA is a 4-tuple {L, S, N, F} where L is the regular lattice of cells, S is the finite state of cells, N is the finite set of neighbors indicating the position of one cell related to another cells on the lattice N, and F is the function which assigns a new state to a cell where | | : N F S S

There are 256 (28 = 256) kinds of different local rules. Therefore, S. Wolfran numbered for elementary cellular automata by its local rules and studies it deeply. The results shows that even through elementary cellular automata is so simple, their space configuration which it presents is extraordinary complex.

Below figure (1) illustrates a 1D binary state nearest neighbor cellular automaton. The lattice configuration (7 cells wide) is shown at two successive time steps. For example, the local neighborhood configuration of the third cell at time step t = 0 is “111” (the current values of the second, third, and fourth cells), and the lookup table states that this cell will be in state “0.66” at the next time step t = 1. All cells in the lattice are updated in a similar way and simultaneously.

STRUCTURE OF THE NEIGHBORHOODS

As the image is a two dimensional, here we use 2DCA model. In 2DCA model, there are three regular lattices namely, triangular, square, and hexagonal. In most cases, the square lattice is used and in only occasionally is the triangular or hexagonal a better choice. In our experiment, a rectangular regular grid is used to represent a digital image and each cell represents one pixel of the image. So initial configuration at t=0, is the original image. Before designing the de-noising rule based on CA, it is necessary to determine the structure of the neighbours firstly. The structure of the neighbours mainly includes von Neumann neighbourhood and moore neighbourhood are shown in figure (2):

Von Neumann neighbourhood, four cells, the cell above and below, right and left from each cell is called von Neumann neighbourhood of this cell. The radius of this definition is 1, as only the next layer is considered. The total number of neighbourhood cells including itself is 5 [10] as shown in the equation (1):

N(I,j) = { (k,l) ÃÂÃâ L : |k-i| + |l-j| ≤ 1 } (1)

Where, k is the number of states for the cell and l is the space of image pixels. Besides the four cells of von Neumann neighbourhood, moore neighbourhood also includes the four next nearest cells along the diagonal. In this case, the radius r=1 too. The total number of neighbour cells including itself is 9 all as shown in the equation (2):

N(I,j) = { (k,l) ÃÂÃâ L : max (|k-i|,|l-j|) ≤ 1 } (2)

The state of the target cell at time t+1 depends on the states of itself and the cells in the moore neighbourhood at time t, that is:

To compare the central pixelwith the neighbourhoods we use the concept of structuring element as shown in the equation (4)

SE = Strel („squareÃÂ¢Ãâ¬ÃÅ¸, w) (4)

creates a square structuring element whose width is w pixels. w must be a non-negative integer scalar as shown in the figure 3:

PROPOSED METHOD FOR NOISE FILTERING

Methodology:

The method that we propose is based in a fact that if the central element is higher than its neighbours, then these neighbours will get contribution from the central element, whereas in the opposite case, the central will gain the contribution from the neighbours. The proposed methodology is shown in figure 4.

Algorithm:

a. Read the input image I, affected by noise and add periodic boundary condition to I.

b. Compute Smax, Smin, and Smed – the maximum, minimum and median values of the pixel values in the moore neighborhood where r=1 and the central pixel of the neighborhood is the pixel which is testing for impulse.

c. If Smin < Sti,j < Smax, then the pixel Sti,j is un-corrupted and its value is unchanged.

d. If the testing pixel falls in any one of the following category then go to step 5.

i) Test pixel value less than all the pixel values in the neighborhood.

ii) Test pixel value greater than all the pixels values in the neighborhood.

e. Si,j (t+1) = Med( si-1,j-1(t), si+1,j(t), si-1,j+1(t), si,j-1, si,j(t) si,j+1(t), si+1j-1(t), si+1,j(t), si+1,j+1(t) )

f. Repeat the step 2-4 for all the pixels of the input image I.

Architecture:

The general framework of this scheme is shown in figure 5. When the filtering process starts, S1 accepts the noisy image and S2 connects to impulse detection block only in the first iteration. The switch S4 is controlled by the output of the noise estimation block, which decides the number of iterations required for the filtering operation. The switch S3 either selects the output of the median filter or unfiltered input pixel depending upon the information provided by the impulse detector for subsequent iteration, the output of the previous iteration is taken as input by the switch S1.

RESULTS

The experimental image is selected as the classical Lena and Mandrill images, whose sizes are 256×256 with varying percentage of impulse noise. In order to evaluate the performance of the traditional and CA based algorithms objectively, Peak Signal to Noise Ratio (PSNR) between denoised image and original image is used, as defined by equation (5)[11].

As to the equation, M and N are the dimensions of the image and a(i,j) & b(i,j) indicates the pixel values in place of i,j for the noisy image and enhanced image. Also, higher the value of the PSNR means better restored image. Table 1 presents the PSNR comparison of the proposed method and traditional filtering methods.

Figure 6 is the first image called Lena, the greyscale of Lena. Fig. 6.1 is the original image. In Fig. 6.2, it is evident that 20% salt and pepper noise has been added to the image. Fig. 6.3 shows the result of the median filter. Finally, Fig. 6.4 illustrates the resulted image after filtered using CA.

CONCLUSION

To improve performance even further, there are several areas to investigate. An extension is to use non-uniform cellular automata rules, as the output of the proposed method looks moderate at low noise ratio up to 40% but shows poor performance as the noise ratio increases.

References

J. Von Neumann, “Theory of Self-Reproducing Automata”, University of Illinois Press, 1966.
Wolfram S., “Computation Theory of Cellular Automata”, Commun. Math. Phys., 1984, pp. 15-57.
R. C. Gonzales and R. E. Woods, Digital Image Processing, 2nd ed. Reading, MA: Addison –Wesley, 2002.
I. Pitas, A.Venetsanopou. Nonlinear Digital Filters: Principles and Application, Norwell, MA: Kluwer,1990.
T.S. Huang, G.J. Yang, and G.Y. Tang. Fast twodimensional median filtering algorithm. IEEE Trans. Acoust. Speech Signal Process., 27(1): 13–18, February 1979.
H.Wang and R.A Hadad “adaptive median filters: new algorithms and results” , IEEE transactions on image processing, vol. 4, no. 4, PP. 499-502, 1995.
Z. Wang and D Zhang,” progressive switching median filters for the removal of impulsive noise from highly corrupted images”, IEEE transactions on circuits and system II: analog and digital signal processing, vol. 46, no. 1 PP. 78-80, 1999.
A. Popovici and D. Popovici, “Cellular automata in image processing,” in Proceedings of the 15th International Symposium on the Mathematical Theory of Networks and Systems, D. S. Gilliam and J. Rosenthal, Eds., 2002, electronic proceedings.
M. A. Peer, N. A. Shah and R. A. Khan,” image processing systems based on cellular automata”, proceeding of the national conference on recent advances and future in IT(RAFIT-2005).
Songtao Liu, Hongguan Chan, Shaoging Yang, “An effective filtering algorithm for salt-peper noises based on cellular automata”, IEEE congress on image and signal processing, 2008.
Tavassoli. S, Rezvanian. A, Ebadzadeh. M.M, “A New Method for Impulse Noise Reduction from Digital Images Based on Adaptive Neuro-Fuzzy System and Fuzzy Wavelet Shrinkage”, In Proceedings of the 2nd International Conference on Computer Engineering and Technology (ICCET 2010), Vol. 4, pp. 297-301, 2010, Chengdu, China.