Cellular Automata have been considered for a series of ap- plications among which several image processing tasks

(1)

THE USE OF SIMPLE CELLULAR AUTOMATA IN IMAGE PROCESSING

LAURA DIOSAN, ANCA ANDREICA, AND ALINA ENESCU

Abstract. Cellular Automata have been considered for a series of applications among which several image processing tasks. The goal of this paper is to investigate such existing methods, supporting the broader goal of identifying Cellular Automata rules able to automatically segment images. With the same broader goal in mind as future work, a detailed description of evaluation metrics used for image segmentation is also given in this paper.

1. Introduction

The one-dimensional binary-state Cellular Automata (CA) capable of per- forming computational tasks has been extensively studied in the literature [13, 34, 19, 23, 4]. Usually, a one-dimensional lattice of N two-state cells is used for representing the CA. The state of each cell changes according to a function depending on the current states in the neighbourhood. The neighbourhood of a cell is given by the cell itself and itsr neighbours on both sides of the cell, wherer represents the radius of the CA. The initial configuration of cell states (0s and 1s) for the lattice evolves in discrete time steps updating cells simultaneously according to the CA rule.

CAs have been considered for a series of applications like computer pro- cessors, cryptography, physical reality modelling, image processing and many others. Three-dimensional CAs have mainly been used within the framework of chemical systems for tasks like percolation description, dissociation of or- ganic acid in solutions, bond interactions, simulation of diffusion controlled reaction kinetics, dissolution and many others [16].

In image processing for example, two-dimensional CAs are usually involved.

The pixels of the image represent cells of the CA and they update their state

Received by the editors: November 5, 2016.

2010Mathematics Subject Classification. 68Q80, 94A08.

1998CR Categories and Descriptors. A.1 [General Literature]: INTRODUCTORY AND SURVEY; F.1.1 [Theory of Computation]: COMPUTATION BY ABSTRACT DEVICES –Models of computation.

Key words and phrases. cellular automata, image processing.

5

(2)

based on the states of the neighbouring cells (pixels). Multiple states of CA cells allow the processing of greyscale images or colour images. Identifying the rules that apply to cells in order to answer a certain request in image processing is nevertheless a nontrivial task.

Cellular Automata have been used for various image processing tasks among which: geometric transformations, noise filtering, feature detection, edge detection. Image segmentation was also approached by the means of Cellular Automata, but there are only few attempts in the literature.

Incorporating cellular automata into image segmentation brings several ad- vantages:

• ease of implementation;

• parallel implementation;

• the number of classes does not need to be specified before segmentation is performed (both two-label and multi-label image segmentations are possible);

• extensibility (to various features extracted from images): currently, pixel intensity values have been used as state transition rules, but other image features such as texture or edges could be easily incor- porated into the update mechanism;

• possibility to work with images of any dimension (the computational complexity of the segmentation process is not directly influenced by the image size or the number of image features).

The simplest use of CA for image processing is given by the application of specific rules for different tasks, for example totalistic rule [6, 8, 25], majority rule [38] or linear rule [20, 21].

Seed-based CAs represent another category of CA applied for image processing. One of the most popular approaches found in the literature in this sense is the GrowCut algorithm [37]. In [14] the authors show that the seeded GrowCut proposed by Vezhnevets[37] is essentially no different from the Ford- Bellman algorithm that computes shortest paths from a cell to all the other cells in the CA. An unsupervised version of GrowCut is proposed in [11]. An- other version of GrowCut, that improves its ability to correctly detect the edges, is proposed in [1]. Other variants of GrowCut are proposed in [17, 12].

In [26] the authors propose an enhancement of GrowCut with automatic seed selection. In [2] the image noise is reduced (and therefore the GrowCut algorithm improved) by adding an anisotropic diffusion filter.

Another class of CAs applied to image processing involves methods for finding the optimal rule for a given task. A deterministic method based on a Hill-Climbing approach is proposed in [27]. There are also many heuristic

(3)

methods based on Genetic Algorithms [35, 24, 32, 33, 15], Particle Swarm Optimization [9], Genetic Programming [31, 30].

A CA based Level Set approach was proposed in [3], and continuous CAs have been applied for image processing tasks in [29, 28].

Due to the fact that beyond the goal of this paper, our final goal is to identify CA rules that are able to successfully segment images, we intend to study the application of CA rules for image processing tasks which are close to image segmentation, like edge detection. On this purpose, the aim of this paper is to describe in detail the first class of CAs applied for image processing, namely CAs that are using specific given rules, the class of so-called ’Simple CA’.

From the same perspective of a final goal, a detailed description of the most popular performance measures used for evaluating the segmentation results is also given in this paper.

2. Simple Cellular Automata for Image Processing

2.1. Totalistic rule. A CA very similar to the Conway’s Game of Life [10] is used in [6] in order to detect the edges of an object in an image. The authors of [6] apply this method for ultrasound kidney images. The greyscale images are binarized prior to the application of the CA based method. A black cell is called ’alive’ and will have the value 1, while a white cell is called ’dead’ and will have the value 0. The Moore neighbourhood gives the neighbours of a cell;

therefore a cell has 9 neighbours, including the cell itself. In order to apply the rule, one has to compute first the sum of the neighbours values (including the cell itself) of each cell. The rule specifies those cells with 3 alive neighbours or less will die of loneliness, while cells with 7 neighbors or more will die of overpopulation. The cells with 5 neighbours will revive and the cells with 4 or 6 will keep their previous state. After one iteration of rule application, the boundaries are detected.

The same metaphor of the Game of Life can also be found in [8]. The authors work on binarized greyscale images, use the Moore neighbourhood and have the same cell state meaning similar to [6]. They apply different ’survival’ rules and find, experimentally, that the best rule is given by the survival or the revival of the cells having 3, 4, 5, 6 and 7 alive neighbours. The results are presented for 3 real world images, the performance of the proposed method being only visually analyzed.

2.2. Linear rule. Due to the fact that the rule search space is significantly large (2²⁹ possible rules for Moore neighbourhood) and an exhaustive search is therefore out of question, there are researchers that focused their inves- tigation on linear rules. The linear rules are those that can be realized by EX-OR operation only, the search space being thus reduced to 512 rules. A

(4)

detailed presentation of theory and application of two-dimensional, null boundary, nine-neighbourhood cellular automata linear rules in given in [5]. There are 9 fundamental rules (1, 2, 4, 8, 16, 32, 64, 128, 256 - powers of 2), which are arranged in a certain order inside a 3x3 grid which resembles a Moore neighbourhood. Each of this 9 fundamental rules specifies which neighbour is considered when changing the state of the current cell, based on EX-OR operations. Adding these powers of 2 gives us other rule numbers that again represent the neighbours that contribute to the state of the current cell at the next iteration.

In [5] the 9 fundamental linear rules are applied for solving several image transformation tasks like translation, generation of multiples copies, zooming, thickening and thinning of symmetric images.

The authors of [25] apply all 512 linear rules to edge detection in one image only and identify three groups of rules: no edge detection rules, strong edge detection rules and weak edge detection rules. However, there is no strong evidence of the significance of these groups of rules since only one image has been used for testing purposes. Moreover, it is not clear how do the authors apply the linear rules for greyscale images, since supporting theory of linear rules deals only with binary images.

In [20], the authors show that there are 4 rules among the 512 linear rules described above that obtain best results for edge detection. Only two images are used in order to show the performance of these 4 rules, and one more image is used in order to provide comparisons with other existing methods for edge detection. However, the results are not conclusive since only 3 images are being used and only visual evidence of the rules performance is given.

Moreover, the images are first binarized because these rules cannot be directly applied to greyscale images.

The linear rules described above are extended to a 25 neighbourhood (extended Moore neighbourhood) in [22]. Among all resulted linear rules, the authors find some optimal rules that can be applied to edge detection. These optimal rules are applied to 2 images (a priori binarized) and the results are only visually compared to the results obtained by other methods of edge detection. Moreover, no details of the method used for identifying the optimal rules are given in this paper.

3. Evaluation measures

In image segmentation, it is very important to establish how we define similar regions or segmentations. Segmented regions and their boundaries can be compact, discontinuous, smooth, etc. One of the most popular evaluation

(5)

real segments

interest segment background segment computed

segments

interest segment TP FN

background segment FN TN

Table 1. Confusion Matrix

metrics (but not very reliable) is theDice coefficient[7]. Dice computes the overlap between regions, quantifying the similarity of two segmentations.

Given two segmentations:

• reference segmentation (gold standard) Sr

• machine segmentation S_m

Each image point (pixel) can be classified as:

• true positive (TP): S_r(x, y) is 1 ∧S_m(x, y) is 1

• false positive (FP):Sr(x, y) is 0 ∧Sm(x, y) is 1

• true negative (TN):S_r(x, y) is 0 ∧S_m(x, y) is 0

• false negative (FN): S_r(x, y) is 1 ∧S_m(x, y) is 0

The Dice similarity coefficient is computed as the ratio between the number of pixels belonging to the intersection (of two possible segmentations) and the average of their sizes:

(1) Coeff_Dice(S_m, S_r) = 2|S_r∩S_m|

|S_r|+|S_m| = 2T P 2T P +F P +F N

For increased reliability, one has to also look at how the values of each pixel in the segmented image compare against some gold standard or ground truth.¹ The four basic cardinalities of the so–calledconfusion matrix, namely the true positives (TP), the false positives (FP), the true negatives (TN), and the false negatives (FN) are defined as follows:

LetI(x, y) :R² →R be a two-dimensional image andS(I(x, y)) :R²→Ω, Ω ={0,1,2, . . . , k−1}, be a k-ry decision segmentation of the imageI(x, y).

Each of these segmentations are composed by k segments, or regions, or classes (e.g. if k = 2, then the two segments are represented by the class of interest and the background; if k = 3, then two classes of interest and the background will represent possible segments). In the case ofk= 2 segments, the confusion matrix can be represented as shown in Table 1.

1In order to call the reference segmentationground truthwe have to be certain that it is so. Manual reference segmentations drawn by experts normally approximate ground truth, in which case it can be used as gold standard, but not as the ground truth itself.

(6)

An alternative evaluation measure can be expressed as a percentage and its values range between 0 (no overlap) and 1 (perfect agreement) using the above values.

(2) F_β = (β²+ 1)∗Precision∗Recall β²∗Precision + Recall

It is also called the overlap index and makes it possible to quantify repro- ducibility. An equivalent of the Dice coefficient is, therefore, the F_β measure withβ = 1.

Precision is another measure that can be used to evaluate the quality of segmentation.

(3) T P

T P +F P

Recall is computed as the ratio between the number of positive pixels in the reference image and the number of pixels identified as positive in the segmented image.

(4) Recall = T P

T P +F N

In conjunction with Precision, Recall is used in order to compute the F–

measure.

Specificityis computed as the ration between the number of negative pixels in the reference image and the number of pixels identified as negative in the segmented image.

(5) Specificity = T N

T N+F P Recall and Specificity depend on the size of segments.

There are two other measures that are related to these metrics, namely Fallout and thefalse negative rate(FNR). They are defined by:

(6) Fallout = F P

F P +T N = 1−Specificity

(7) FNR = F N

F N+T P = 1−Recall

Since the last two measures are equivalent to Specificity and Recall, only one pair ((Recall, Specificity) or (Fallout, False Negative rate)) should be used to evaluate the performance of segmentation.

(7)

Recall is also called Sensitivity or True Positive Rate. Specificity is also called True Negative Rate (TNR). Fallout is also called the false positive rate (FPR).

Another frequently used evaluation measure is the Global Consistency Error (GCE) [18]. An error-based measure is the complement to similarity measures, in that two segmentations are identical if an error–based measure is 0.

This measure is computed as an average over the error of pixels belonging to two segmentations. It compares partitions of the same image and it is tolerant to one partition refining the other (e.g. by splitting or merging regions). For an imageI ofnpixels (n=|I|) and a segmented regionS, we denote the set of all neighbour pixels to pixel p which belong to the same segmentation region S by R(S, p). For two segmentations, one computed S_c and one reference segmentation Sr, the asymmetric Local Refinement Error in [18] at pixel p, LRE(S_c, S_r, p) is defined as

(8) LRE(S_c, S_r, p) =|R(S_c, p)−R(S_r, p)|

|R(S_c, p)|

The GCE between segmentations can be defined as a mean over the error of all points (pixels):

(9) GCE(S1, S2) = 1

|I|min







|I|

X

i=1

LRE(S1, S2, p),

|I|

X

i=1

LRE(S2, S1, p)





 By using the cardinalities previously introduced, GCE can be expressed as follows:

GCE(S_c, S_r) = _|I|¹ min (10)

F N(F N + 2T P)

T P +F N +F P(F P + 2T N)

T N+F P ,F P(F P + 2T P)

T P +F P + F N(F N+ 2T N) T N+F N

This measure is able to quantify the consistency between image segmentations of differing granularities. It has the advantage of being tolerant to (label) refinement. It makes most sense to use this measure when the two segmentations being compared have comparable numbers of segments [36].

4. Conclusions

This paper presents in detail a class of CAs applied for image processing tasks that are related to image segmentation, as well as a detailed description

(8)

of the most popular performance measures used for evaluating the segmentation results. As further work, an exhaustive description of CA based methods for image processing will be performed, followed by the proposal of competitive CA based methods for the task of image segmentation.

Acknowledgment

This work was supported by a grant of the Romanian National Authority for Scientific Research and Innovation, CNCS - UEFISCDI, project number PN-II-RU-TE-2014-4-1130.

References

[1] Ryan A Beasley. Semiautonomous medical image segmentation using seeded cellular automaton plus edge detector.ISRN Signal Processing, 2012:1–9, 2012.

[2] Lei Bi, Jinman Kim, Lingfeng Wen, A. Kumar, M. Fulham, and D.D. Feng. Cellular automata and anisotropic diffusion filter based interactive tumor segmentation for positron emission tomography. In Engineering in Medicine and Biology Society (EMBC), 2013 35th Annual International Conference of the IEEE, pages 5453–5456, 2013.

[3] Yu Chen, Zhuangzhi Yan, and Yungao Chu. Cellular automata based level set method for image segmentation. In Complex Medical Engineering, 2007. CME 2007.

IEEE/ICME International Conference on, pages 171–174, May 2007.

[4] C. Chira, A. Gog, R. I. Lung, and D. Iclanzan. Complex systems and cellular automata models in the study of complexity.Studia Informatica series, LV:33–49, 2010.

[5] Pabitra Pal Choudhury, Birendra Kumar Nayak, Sudhakar Sahoo, and Sunil Pankaj Rath. Theory and applications of two-dimensional, null-boundary, nine-neighborhood, cellular automata linear rules. CoRR, abs/0804.2346, 2008.

[6] C. Callins Christiyana, V. Rajamani, and A. Usha Devi. Article: Ultra sound kidney image retrieval using time efficient one dimensional glcm texture feature.IJCA Special Issue on Advanced Computing and Communication Technologies for HPC Applications, ACCTHPCA(4):12–17, July 2012. Full text available.

[7] Lee R. Dice. Measures of the amount of ecologic association between species.Ecology, 26(3):297–302, 1945.

[8] Manoj Diwakar, Pawan Kumar Patel, and Kunal Gupta. Cellular automata based edge- detection for brain tumor. InICACCI, pages 53–59. IEEE, 2013.

[9] Safia Djemame and Mohamed Batouche. Combining cellular automata and particle swarm optimization for edge detection. (14/):16–22, 2012.

[10] Martin Gardner. The fantastic combinations of john conway’s new solitaire game ”life”.

Scientific American, 223(10):120–123, October 1970.

[11] Payel Ghosh, Sameer Antani, L. Rodney Long, and George R. Thoma. Unsupervised grow-cut: Cellular automata-based medical image segmentation. InHISB, pages 40–47.

IEEE, 2011.

[12] Andac Hamamci, Nadir Kucuk, Kutlay Karaman, Kayihan Engin, and G¨ozde B. ¨Unal.

Tumor-cut: Segmentation of brain tumors on contrast enhanced MR images for radio- surgery applications.IEEE Trans. Med. Imaging, 31(3):790–804, 2012.

(9)

[13] Hugues Juille and Jordan B. Pollack. Coevolving the ideal trainer: Application to the discovery of cellular automata rules. In John R. Koza, Wolfgang Banzhaf, Kumar Chel- lapilla, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max H. Garzon, David E.

Goldberg, Hitoshi Iba, and Rick Riolo, editors, Genetic Programming 1998: Proceed- ings of the Third Annual Conference, pages 519–527. Morgan Kaufmann, 22-25 July 1998.

[14] Claude Kauffmann and Nicolas Piche. Seeded nd medical image segmentation by cellular automaton on gpu. Int. J. Computer Assisted Radiology and Surgery, 5(3):251–262, 2010.

[15] Okba KAZAR and Sihem SLATNIA. Evolutionary cellular automata for image segmentation and noise filtering using genetic algorithms.Journal of Applied Computer Science

& Mathematics, 11(5):33–40, 2011.

[16] A.C.J. Korte and H.J.H. Brouwers. A cellular automata approach to chemical reactions;

1 reaction controlled systems.Chemical Engineering Journal, 228:172–178, 2013.

[17] Yan Liu, H. D. Cheng, Jianhua Huang, Yingtao Zhang, and Xianglong Tang. An effec- tive approach of lesion segmentation within the breast ultrasound image based on the cellular automata principle.J. Digital Imaging, 25(5):580–590, 2012.

[18] D. R. Martin, C. C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. InICCV, pages II: 416–423, 2001.

[19] Melanie Mitchell, Michael D. Thomure, and Nathan L. Williams. The role of space in the success of coevolutionary learning. In Artificial Life X: Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems, pages 118–124. MIT Press, 2006.

[20] Jahangir Mohammed and Deepak Ranjan Nayak. An efficient edge detection technique by two dimensional rectangular cellular automata.CoRR, abs/1312.6370, 2013.

[21] Deepak Ranjan Nayak, Prashanta Kumar Patra, and Amitav Mahapatra. A survey on two dimensional cellular automata and its application in image processing. IJCA Proceedings on International Conference on Emergent Trends in Computing and Com- munication (ETCC-2014), ETCC(1):78–87, 2014.

[22] Deepak Ranjan Nayak, Sumit Kumar Sahu, and Jahangir Mohammed. A cellular automata based optimal edge detection technique using twenty-five neighborhood model.

CoRR, abs/1402.1348, 2014.

[23] Gina M. B. Oliveira, Luiz G. A. Martins, Laura B. de Carvalho, and Enrique Fynn. Some investigations about synchronization and density classification tasks in one-dimensional and two-dimensional cellular automata rule spaces.Electr. Notes Theor. Comput. Sci., 252:121–142, 2009.

[24] Blanca Priego, Daniel Souto, Francisco Bellas, and Richard J. Duro. Hyperspectral image segmentation through evolved cellular automata. Pattern Recognition Letters, 34(14):1648–1658, 2013.

[25] Fasel Qadir, Peer M. A., and Khan K. A. Efficient edge detection methods for diagnosis of lung cancer based on two dimensional cellular automata.Advances in Applied Science Research, 4(3):2050–2058, 2012.

[26] R. S. RajKumar and G. Niranjana. Image segmentation and classification of mri brain tumor based on cellular automata and neural networks. International Journal of Re- search in Engineering & Advanced Technology, 1(1):1–7, 2013.

[27] P. L. Rosin. Training cellular automata for image processing. InSCIA, pages 195–204, 2005.

(10)

[28] D. Safia and B.M. Chawki. Image segmentation using an emergent complex system:

Cellular automata. In Systems, Signal Processing and their Applications (WOSSPA), 2011 7th International Workshop on, pages 207–210, May 2011.

[29] D. Safia, D. Oussama, and B.M. Chawki. Image segmentation using continuous cellular automata. In Programming and Systems (ISPS), 2011 10th International Symposium on, pages 94–99, April 2011.

[30] Mohamed Sandeli and Mohamed Batouche. Multilevel thresholding for image segmentation based on parallel distributed optimization. In SoCPaR, pages 134–139. IEEE, 2014.

[31] S. Sato and H. Kanoh. Evolutionary design of edge detector using rule-changing cellular automata. InNature and Biologically Inspired Computing (NaBIC), 2010 Second World Congress on, pages 60–65, Dec 2010.

[32] Sihem Slatnia, Mohamed Batouche, and Kamal E. Melkemi. Evolutionary cellular automata based-approach for edge detection. In Francesco Masulli, Sushmita Mitra, and Gabriella Pasi, editors,Applications of Fuzzy Sets Theory, 7th International Workshop on Fuzzy Logic and Applications, WILF 2007, Camogli, Italy, July 7-10, 2007, Pro- ceedings, volume 4578 ofLecture Notes in Computer Science, pages 404–411. Springer, 2007.

[33] Sihem Slatnia and Okba Kazar. Evolutionary cellular automata based-approach for region detection. http://www.researchgate.net/publication/229050070, 2015.

[34] Marco Tomassini and Mattias Venzi. Evolution of asynchronous cellular automata for the density task. In Juan J. Merelo Guervs, Panagiotis Adamidis, Hans-Georg Beyer, Jos Luis Fernndez-Villacaas Martn, and Hans-Paul Schwefel, editors, PPSN, volume 2439 ofLecture Notes in Computer Science, pages 934–944. Springer, 2002.

[35] Blanca Maria Priego Torres, Daniel Souto, Francisco Bellas, and Richard J. Duro. Un- supervised segmentation of hyperspectral images through evolved cellular automata.

In Manuel Graa, Carlos Toro, Jorge Posada, Robert J. Howlett, and Lakhmi C. Jain, editors,KES, volume 243 ofFrontiers in Artificial Intelligence and Applications, pages 2160–2169. IOS Press, 2012.

[36] R. Unnikrishnan, C. Pantofaru, and M. Hebert. Toward objective evaluation of image segmentation algorithms. IEEE Trans. Pattern Analysis and Machine Intelligence, 29(6):929–944, June 2007.

[37] Vladimir Vezhnevets and Vadim Konouchine. Growcut” - interactive multi-label N-D image segmentation by cellular automata. pages 1–7. Russian Academy of Sciences, 2005.

[38] Sartra Wongthanavasu.Cellular Automata for Medical Image Processing. Cellular Au- tomata - Innovative Modelling for Science and Engineering. INTECH Open Access Publisher, unknown 2011.

Department of Computer Science, Faculty of Mathematics and Computer Sci- ence, Babes¸-Bolyai University, Cluj-Napoca, Romania

E-mail address: {lauras, anca, aenescu}@cs.ubbcluj.ro