Analysis and Application of Cellular Automata Based Edge Detection Methods on Bio-Medical Images

Analysis and Application of Cellular Automata Based Edge Detection Methods on Bio-Medical Images

Rupashri Barik

Department of Information Technology JIS College of Engineering

Kalyani, India.

Sourav Modak

Department of Information Technology JIS College of Engineering

Kalyani, India.

1. Nazma B. J. Naskar

   School of Computer Engineering KIIT University

   Bhubaneswar, India.

   Ujjwal Verma

   Department of Information Technology JIS College of Engineering

   Kalyani, India.

   Abstract In the domain of digital image processing, a number of methods for detecting edges have been proposed till now like Robert, Sobel, Prewitt, Canny, etc. All these methods have some benefits and some drawbacks. Edge detection can be done in more efficient way using the concept of Cellular Automata. Different rules for cellular automata are efficient to find out the edge of bio-medical images also. Outputs obtain on applying cellular automata are better in terms of computation time and clarity. As consequences the detected edges using Cellular Automata are clear and continual. The outcomes of edge detection of bio-medical images can be confirmed with graphical instances.

   Keywords Edge Detection, Cellular Automata, Cellular Edge Detection, Bio-Medical Image Processing

   1. INTRODUCTION

      In this era medical science has a vital role towards the society to keep it moving and digital image processing helps the medical science a lot by providing proper diagnosis tools. Edge detection of different medical images is very much important to diagnose the problems like bone fractures, brain tumors, mammography, breast cancer, etc. In the field of digital image processing, different Edge Detection algorithms

      [1] exist, like Robert, Sobel, Prewitt, Canny, etc. Sobel, Prewitt edge detectors are simple but produces edges with noise whereas Canny edge detector is more complex and time consuming but improves signal to noise ratio. These edge detection techniques are efficient and fast for detecting edges of different objects. But these methods produce edges with very low precision. Especially for bio-medical images, these traditional approaches are not so effective due to this low precision.

      Day by day computer science field has escalated anticipation on technologies of computations based on Cellular Automata (CA) [2] theory also. Cellular Automata also can be used in the field of image processing. Using different rules of CA clear and continuous edges of images can be obtained. Nevertheless, so far there are plenty of edge detection methods based on CA. MATLAB is a good simulation tool for implementing the operations of digital image processing. Hence MATLAB has been used to

      implement all the algorithms to be discussed here. This paper emphasizes a survey on edge detection applying CA based Algorithms has been done and a comparison of CA based algorithm has been done with the conventional edge detection methods.

   2. BACKGROUND STUDY

1. Edge Detection

   Edge detection is a primitive tool for machine vision systems. An edge is a zone of demarcation between two regions that differ according to some measure of homogeneity. In general, edge can be denoted as the borderline between contrasting regions in image whereas specifically it can be defined as abrupt local change in brightness. Conventional approaches for detecting edges demand convolving the image with a 2-D filter. It is assumed that the operator is sensitive for large gradients in the image while recovering the values of zero in consistent areas.

   Most of the classical edge detection methods use first- order derivatives for estimating the edge magnitude. Pixels identified at edges are needed to be thresholded and continued. Detection of edge is usually accomplished using local operators, but these edges may not be prominent locally in the image represents that mapping of edges are inclined to fragmentation.

   1. Sobel Edge Detection Algorithm

      Though Sobel Edge Detection method [3] is based on one- dimensional analysis, but this concept is also applicable for two-dimension matrix also as there an exact estimation is present for computing derivative of two-dimensional images. Sobel edge detector produces one resultant image performing a 2-D spatial gradient measurement on an image. The Sobel operator uses a pair of 3×3 convolution masks, one of them estimates the gradient in the x-direction (columns) and another one estimates the gradient in the y-direction (rows).

      -1	0	+1 +1 +2 +1 It is suitable to use two- dimensional CA model as
      -2	0	+2 0 0 0 because digital images are presented as two-dimensional
      -1	0	+1 -1 -2 -1 arrays of p x q pixels. For any CA based specific problem, it is

      -1	0	+1 +1 +2 +1 It is suitable to use two- dimensional CA model as
      -2	0	+2 0 0 0 because digital images are presented as two-dimensional
      -1	0	+1 -1 -2 -1 arrays of p x q pixels. For any CA based specific problem, it is

      Gx Gy

      The gradient magnitude is obtained by

      highly needed to be aware regarding the lattice geometry, initial conditions, conditions for boundary, neighborhood size, set of different states and the corresponding rule of transition.

      |G| = (G 2 + G 2) (1)

      x y The central cell or the core cell and all other adjacent cells

      An estimation of magnitude can be represented as

      |G| = |Gx| + |Gy| (2)

   2. Prewitt Edge Detection Algorithm

      Prewitt Edge detection algorithm [4] is used for detecting edges based on applying a horizontal as well as a vertical filter in a particular order. Both filters are moved over the whole image and then they are added together to get the ultimate result. These kinds of filters are basically convolution filters in terms of horizontal kernel and vertical kernel.

      whose states help to determine the next level of state of the core cell are considered as neighborhood of a cell. There are various ideas of neighborhood structures specifically for cellular automata. Von Neumann and Moore neighborhood are mostly used concept. One-dimensional cellular automata are comprised of a row of cells. Every cell has a specific state among multiple states and has a set of transitions rules for changing the states.

      +1	0	-1
      +1	0	-1
      +1	0	-1

      +1	+1	+1
      0	0	0
      -1	-1	-1

      +1	0	-1
      +1	0	-1
      +1	0	-1

      +1	+1	+1
      0	0	0
      -1	-1	-1

      Fig1: Structure of 1D CA	Fig2: Structure of 2D CA/p>

      Fig1: Structure of 1D CA	Fig2: Structure of 2D CA

      Gx Gy

      The gradient magnitude is then calculated same way like Sobel edge detector.

   3. Canny Edge Detection Algorithm

      Canny edge detector [5] finds out the edges of images using a multi-phase algorithm for detecting a broad variety of edges of images. At first phase the image is being smoothen using Gaussian convolution filter. Next, to highlight the areas of the images a 2-D first derivative filter or operator is used to the obtained image that is being smoothen in the early step. In the gradient magnitude image, ridges are produced by the edges. After that, top of these ridges is being marked and for producing a thin line in the output all pixels are set to zero if they are not on the top of the ridge. This way whole process is controlled by two thresholds that help to confirm that noisy edges are not scattered into multiple edge pieces.

2. Cellular Automata

   Cellular automata are active systems which show complex and global characteristic from easy and local communication as well as evaluation. Basically, CA is consistent. Thus, heterogeneity has also been instigated in modified form, local rule, lattice structure and neighborhood dependency. CA is building up from well-ordered grid of cells. Individual cell may have limited number of probable states. The cell state is updated periodically and decided by the preceding states of the neighborhood cells by which it is surrounded. It is done with the support of a particular transition rule. Hence, CA rules are confined and consistent. If all cells follow one identical rule, then that specific CA are called uniform CA. 1-D, 2-D and 3- D CA models are present. 1D CA is composed of cells those are linear. In 2D CA, all the cells are organized in a rectangular structure or hexagonal structure of grids. These grids maintain connections among the cells those are neighboring to them as represented in fig.2.

   Fig.1. represents structure of 1D CA. It is linear in structure. Structure of a two-dimensional cellular automata is as Fig. 2 which is very much similar to a digital image. A 2D CA has rows and columns and each cell of a 2D CA can be considered as a pixel of a digital image.

   a b c

   Fig 3: Neighborhood models a. Von Neumann, b. Moore, and

   c. Extended Moore

   Fig.3(a) represents Von Neumann neighborhood models and Fig.3(b) is the representation of Moore Neighborhood model. Fig.3(c) shows the representation of Extended Moore structure.

   Any digital image also considers regular grid of cells called pixels and henceforth cellular automata is performed for image processing for the edge detection in digital image. Edge detection methods based on Cellular Automata has major advantages over conventional approaches because it is computationally effective, and may be utilized for particular applications by choosing suitable rules. Various CA based edge detection approaches are implemented and tested for enabling a primary comparison between existing approaches.

3. Cellular Edge Detection

   Cellular edge detection [6] is a method where Cellular Automata are initialized to an image in a manner such as every cell of CA correlate to one particular image pixel. Besides this, the Cellular Learning Automata specifies the CA neighborhood type. These two approaches together detect the edges first for the images and then merge with the edge map that is optimal.

4. Bio-Medical Image Processing

Bio-medical image processing is a vast area; it includes biomedical signal gathering, formation and processing of image and image display for medical diagnosis depending on features extraction of images. Fundamentally, some primary image processing techniques including thresholding, edge detection, etc. can be explored together. Different types of radiological imaging like radiography, ultrasound, nuclear medicine and CT are there needed to be analyzed. X-ray CT is magnificent for static anatomical images and it moves toward the measurement of dynamic function.

1. LITERATURE SURVEY

   K. Bhattacharjee et al. [6] had introduced various types of CAs, there distinct characterization aids, the overall functioning of CAs, like reversibility, universality, dynamics, etc. This paper is mainly concentrated on non-uniformity in CA and as well as to non-uniform fundamental of CA, that is so effective to solve different real-life problems.

   Paul L Rosin et al. [7] provided an overall view of edge detection techniques based on CA, and evaluate their relative advantages and disadvantages in their works. Here different CA based techniques for edge detection are implemented and tested to validate a preliminary collation between competing methods.

   Parul Kundra et al. [8] have considered binary images for the detection of edges and applied objective function for the selection of rule set from the Look up Table. In this work, firstly the operation for edge detection is performed and then derived result is compared to different edge detection techniques. In first step find all 28 (= 256) possible rule-set and remove the symmetry by using 51 rule set operation for the edge detection. Finally, Sequential Floating Forward Search algorithm (SFFS) is applied to find the group of best rule set among the used rule sets on image for the edge detection. After applying SFFS, a single rule is achieved that is equivalent to other 51 rule sets at their respective points in image. Rule set and selection of best rule set.

   Deepak Ranjan Nayak et al. [9] focused on a new concept of CA based approach for finding out optimal edges for the binary images considering two-dimensional twenty-five neighborhood cellular automata. This approach contemplates only linear rule of CA used to extract the edges considering null boundary condition.

   Anand Prakash Shukla et al. [10] approached to a novel method to train two dimensional cellular automata for detecting edges of digital images. Training of two-dimensional cellular automata tends for selecting the appropriate rule set among the given set of rules for performing a particular task. In this approach first, the size of rule set is reduced and then the

   sequential floating forward search (SFFS) method is used for selecting the best rule set for edge detection. For the objective function to train the cellular automata for detecting the edges, misclassification error has been used.

   Mahesh Kumar et al. [11] proposed one improved cellular automata-based approach. An improved cellular automaton (ICA) has been approached here for detecting edge applying a CA Algorithm based on 2D cellular automata. The outcomes of edge detection are defined with graphical instances. Rule number 124, among 1024 rules, has been applied here as it produces clear and uninterrupted edges.

   Sartra Wongthanavasu et al. [12] mentioned cellular automata-based technique that appears in the guise of a basic tool to process images with their non-global behavior along with the parallel computing execution. Here few cellular automata-based methods have been applied for medical image processing. Starting with cellular automata fundamentals, the proposed algorithm is carried over to a number of cellular automata-based techniques for detecting edges of medical images, detecting spots, noise filtering and segmentation were represented.

   Laura Diosan et al. [13] applied Totalistic Rule, Linear Rule in their works. The aim of this paper was to inspect some present methods those providing the widen goal of recognizing different rules of Cellular Automata those are able to spontaneously segment images.

   Mohammad Hasanzadeh Mofrada et al. [14] proposed a cellular edge detection technique (CED) that uses cellular learning automata (CLA) along with cellular automata (CA). Here, CA local rule had been introduced to generate the edge map of image using adaptive neighborhood type as contradict to CA with fixed neighborhood. CED algorithm loses less description during extraction of image edges in contrast to other edge detection techniques.

   Manoj Diwakar et al. [15] analyzed different methods for detecting edges using Cellular Automata in his works. In this paper, the CA based edge detection method has been utilized to detect cancerous cells in brain. CA rules help to determine the proper location and volume of the tumor even as edges identified applying CA are thin, uninterrupted and properly visible.

   Popovici and Popovici [16] approached an edge detection technique considering the differences of states between the pixels in its neighborhood following Von-Neumann concept and the central pixel. Here the comparison has made for all the absolute state differences. If the differences are greater than of the defined threshold , then it remains unaltered otherwise, the state of the central pixel will be 0. This rule can be represented as:

   0 , if | vi – vc | , for all i Nc

   vc+ =

   vc , otherwise

   An approach proposed by Wongthanavasu and Sadananda [17] was based on a conditional rule for updating the state of cellular as:

   vc , if vc vmax – vmin

   vc+ =

   vmax – vmin , otherwise

   where, vmin and vmax are the minimum and maximum states, neighbourhood concept of the central cell c.

   Khadijeh respectively, in the von-Neumann

   Mirzaei et al. [18] approached a new method that helps to eliminate noise and to detect image edges using of fuzzy cellular automata. Here, the mentioned algorithm has been used to detect edges of gray level images as well as for eliminating salt and pepper noise present in images.

   Haralick et al. [19] presumed the concept of second directional derivative approach of edge detector. This may be represented as a combination of statistical hypothesis testing and differentiation method that tends to perform in a better way in noisy environment.

   Shohei Sato et al. [20] alleged to design an advanced CA based edge detection technique. Basically, training the CA was carried over by canny edge detector. Two objective functions were calculated from there. A multi-objective evolutionary algorithm optimizes both the objective functions.

   Fasel Qadir et al. [21] explored the linear rules of CA to detect edges. In addition to this, on basis of this finding the classification of the rules has been done for no edge detection rules as well as strong and weak edge detection rules. A comparison also had been made between the proposed methods with existing methods for edge detection with results showing desirable performance.

   Parwinder Kaur Dhillon et al. [22] mentioned a vigorous edge detection method based on Cellular Automata (CA). Here the edge pixels or the edgels are strongly represented along with the non-edge pixels those are comparatively weak.

2. RESULTS & DISCUSSIONS

   Here different edge detection methods have been implemented to get the edges of medical images. Above mentioned edge detection algorithms have been implemented in MATLAB.

   In this paper images of bone fracture and brain tumor have been considered for analysis. Sobel, Prewitt and Canny edge detection algorithms have been applied to the medical images to get the edges for the corresponding. The results have been compared with the edges obtained by applying the Cellular Automata also.

   Here one of the CA based approach has been implemented to detect the edges for both the medical images. Methodology proposed by Popovici and Popovici [16] has been illustrated here.

   1. Illustration of the Cellular Automata based Algorithm for Edge Detection:

      Step 1: Read Image

      Step 2: Pad the image with 0

      Step 3: Repeat step 3 until all the pixels are being processed considering the following rule:

      New value of vc will be 0 if (vi-vc) is less than threshold value otherwise it will be 0.

      Step 4: Get the output image containing edges.

      Step 5: Stop

      Here Fig. 4 represents the edges of the bio-medical images obtained by applying different classical edge detection algorithms as well as CA based approaches. The threshold value has been considered as 150.

      Original Image of Bone Fracture	Original Image of Brain Tumor
      Edge detected using Sobel Operator	Edge detected using Sobel Operator
      Edge detected using Prewitt Operator	Edge detected using Prewitt Operator
      Edge detected using Canny Operator	Edge detected using Canny Operator
      Edge detected using Cellular Automata	Edge detected using Cellular Automata

      Fig 4: Edges obtained after applying different edge detection approaches

      Fig. 4 illustrates that the edge detection algorithms like Sobel and Prewitt are able to find out the edges of the bone fracture image in a pretty good manner whereas in case of the brain tumor the affected area has not been detected at all. Moreover, Canny edge detector has found out the edges more effectively but it includes the other unwanted edges also, so that the points of concern are very confusing.

      But in case of the output produced by applying cellular automata approach are more convenient in both the cases. It also identified the mass of the affected region also.

      Though Cellular Automata produces effective edges as well as the mass of concentration of bio-medical images but it doesnt help so much to produce the edges of other images.

      TABLE 1: COMPARISON AMONG DIFFERENT EDGE DETECTION METHODS

      	Sobel	Prewitt	Canny	CA method
      Avg. success %	37	37	55	77

      Table 1 illustrates the comparison of performance success ratio for the various edge detection techniques.

      Fig 5: Comparison among different edge detection methods

      Fig. 5 compares the performances in terms of edge detection using various methods. It analyses the success ratios for finding out the edges using above mentioned techniques. The experimental results show that on an average Cellular Automata based method is approximately 77% successful in achieving the desired edges.

      The PSNR is for computing the peak signal-to-noise ratio of two images. It is measured in terms of decibel(dB). PSNR is used for measuring the quality improvement between the original and a modified image. The higher value of PSNR indicates better in quality of the reconstructed image.

      Moreover, here one more performance-based comparison has been made considering the PSNR values for the obtained images. Table 2 illustrates the comparison of PSNR values for the resultant images.

      TABLE 2: COMPARISON OF PSNR VALUES AMONG DIFFERENT EDGE DETECTION METHODS

      	Sobel	Prewitt	Canny	CA method
      Brain Image	28.646 dB	28.653 dB	28.694 dB	29.659 dB
      Bone Image	30.264 dB	30.281 dB	30.565 dB	31.295 dB

      From Table 2 it can be clearly observed that the PSNR values are slightly higher in case of CA based edge detection methods comparative to other edge detection methods like Sobel, Prewitt and Canny. It implies that the image obtained applying Cellular Automata based edge detection technique are much more efficient than the images obtained from other edge detection techniques.

3. CONCLUSION

As now a days bio-medical images have a great impact on our society, so further analysis on bio-medical images needs to be done with more importance. This analysis can be done moe efficiently using Cellular Automata. Here the images of brain tumor and bone fracture have been considered and it has been observed that CA based approach detected the mass of brain tumor very well. Here defining the threshold value is an issue to get better edges of bio-medical images in a better way. Cellular Automata can play a major role to detect several health issues of living being by producing the edges of the corresponding radiology diagram.

REFERENCES

1. R. C. Gonzalez, R. E. Woods, Digital Image Processing, Prentice Hall, 2nd ed, 2002.

2. Jarkko Kari, Cellular Automata, Spring 2013.

3. Poonam Dhankhar, Neha Sahu, A Review and Research of Edge Detection Techniques for Image Segmentation, Inter-national Journal of Computer Science and Mobile Computing, IJCSMC, Vol. 2, Issue. 7, July2013, pg.8692

4. Pooja Sharma, Gurpreet Singh, Amandeep Kaur, Different Techniques of Edge Detection In Digital Image Processing, International Journal of Engineering Research and Applications (IJERA) ISSN: 2248-9622, Vol. 3, Issue 3, May-Jun 2013, pp.458- 461

5. Amruta L Kabade, V.G. Sangam, Canny edge detection algorithm, International Journal of Advanced Research in Electronics and Communication Engineering (IJARECE)Volume 5, Issue 5,

   May2016, ISSN:2278 909X

6. K. Bhattacharjee, N. Naskar, S. Roy, S. Das: A Survey of Cellular Automata: Types, Dynamics, Non-uniformity and Applications, cited at. arXiv:1607.02291v3

7. Paul L Rosin, Xianfang Sun: Edge Detection Using Cellular Automata, Cellular Automata in Image Processing & Geometry, Springer.

8. Parul Kundra, Hari Mohan Singh, Vinod Kumar, Pooja Juneja: Digital Edge Detection using Cellular Automata, International Journal of Innovative Technology and Exploring Engineering (IJITEE) ISSN: 2278-3075, Volume-8 Issue-7S2, May 2019.

9. Deepak Ranjan Nayak, Sumit Kumar Sahu, Jahangir Mohammed: A Cellular Automata based Optimal Edge Detection Technique using Twenty-Five Neighborhood Model, International Journal of Computer Applications (0975 8887) Volume 84 No 10, December 2013.