See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/344609903

Unsupervised Edge Detector based on Evolved Cellular Automata

Conference Paper · October 2020

DOI: 10.1016/j.procs.2020.08.049

CITATIONS READS

0 31

4 authors:

Alina Enescu Delia Dumitru

Babeş-Bolyai University Babeş-Bolyai University
9 PUBLICATIONS   5 CITATIONS    3 PUBLICATIONS   1 CITATION   

SEE PROFILE SEE PROFILE

Anca Andreica Laura Diosan

Babeş-Bolyai University Babeş-Bolyai University
67 PUBLICATIONS   227 CITATIONS    61 PUBLICATIONS   351 CITATIONS   

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

http://embodiedcognition2020.devpsychology.ro/ View project

DeepRiemann View project

All content following this page was uploaded by Alina Enescu on 12 October 2020.

The user has requested enhancement of the downloaded file.

 Available online at www.sciencedirect.com
Available online at www.sciencedirect.com
Available online at www.sciencedirect.com

ScienceDirect
00 (2020) 000–000
00Science
Procedia Computer (2020) 000–000
176 (2020) 470–479

24th International Conference on Knowledge-Based and Intelligent Information & Engineering

24th International Conference on Knowledge-Based
Systems and Intelligent Information & Engineering
Systems
Unsupervised
Unsupervised Edge
Edge Detector
Detector based
based on
on Evolved
Evolved Cellular
Cellular Automata
Automata
Alina Enescua,b a,b,c a,c
a,b , Delia Dumitrua,b,c , Anca Andreicaa,c , Laura Dioşana,c
a,c
Alina
a
Enescu , Delia Dumitru , Anca Andreica , Laura Dioşan
Babeş-Bolyai University, Mathematics and Computer Science Faculty, Cluj-Napoca, 400084, Romania
a Babeş-BolyaiUniversity,
b RomanianMathematics and Computer
Institute of Science Science Faculty,
and Technology, Cluj-Napoca,
Cluj-Napoca, Romania400084, Romania
b Romanian Institute of Science and Technology, Cluj-Napoca, Romania
c IMOGEN Research Institute, County Clinical Emergency Hospital, 400006, Cluj-Napoca, Romania
c IMOGEN Research Institute, County Clinical Emergency Hospital, 400006, Cluj-Napoca, Romania

Abstract
Abstract
Extensive research has been performed in image processing to find the best edge detector, from the gradient-based operators to
Extensive research
evolved Cellular has been
Automata performed
(CA). Some ofinthese
image processing
detectors havetoweak
findpoints,
the best edge
such detector, fromedges,
as disconnected the gradient-based
the incapacity operators to
of detecting
evolved Cellular
the branching Automata
edges or the (CA).
need of Some of these
a ground detectors
truth havealways
that is not weak points, suchToasovercome
available. disconnected
theseedges,
issues,thewe
incapacity
propose aofCA-based
detecting
the
edgebranching edges ortothe
detector adapted theneed of a ground
particularities of truth that isThe
the image. not adaption
always available.
means toTo overcome
identify these
the best CAissues, we propose
rule, which a CA-based
is an optimization
edge detector adapted to the particularities of the image. The adaption means to identify the best CA rule, which
problem solved by a Genetic Algorithm (GA). The GA requires a fitness function and we propose to use an unsupervised fitnessis an optimization
problem
based on solved by a GeneticThe
edge dissimilarity. Algorithm
performed(GA). The GAexperiments
numerical requires a fitness function
are meant and wethepropose
to evaluate to use
proposed an unsupervised
approach fitness
and to emphasize
based on edge dissimilarity. The performed numerical experiments are meant to evaluate
that some of the weak points of a well-known detector (Canny) can be overcome by our method. the proposed approach and to emphasize
that some of the weak points of a well-known detector (Canny) can be overcome by our method.
© 2020 The
© 2020 The Authors.
Author(s).Published
PublishedbybyElsevier
ElsevierB.V.
B.V.
© 2020an
This The Author(s). Published bythe Elsevier B.V.
This is
is an open
open access
access article
article under
under the CC
CC BY-NC-ND
BY-NC-ND license
license (https://creativecommons.org/licenses/by-nc-nd/4.0/)
(https://creativecommons.org/licenses/by-nc-nd/4.0)
This is an open access article
Peer-review under responsibilityunder
responsibility of the
of the
KES CC BY-NC-ND
International.
scientific license
committee of the(https://creativecommons.org/licenses/by-nc-nd/4.0/)
KES International.
Peer-review under responsibility of KES International.
Keywords: Edge detection; Cellular Automata; Genetic Algorithms; Unsupervised
Keywords: Edge detection; Cellular Automata; Genetic Algorithms; Unsupervised

1. Introduction
1. Introduction
Cellular Automata are a suitable choice for developing image analysis and computer vision algorithms for large
Cellular Automataimages
or high-dimensional are a suitable choiceintrinsically
due to their for developing image
parallel analysis
nature sinceand computer
each visionindependently
cell operates algorithms foroflarge
the
or high-dimensional images due to their intrinsically parallel nature since each cell operates independently
other cells [8, 26]. One of the most important tasks in image analysis is edge detection. This task may be seen ofasthea
other cells
pre-step [8, 26].
in more One ofapplications.
complex the most important tasks inofimage
In the context imageanalysis is edge
processing, edgedetection.
detection This
aims task may
to find be seen as a
discontinuities
pre-step in more complex applications. In the context of image processing, edge detection aims to find discontinuities
in pixel brightness. Edges provide information about the content of an image such as variations in depth, illumination
in
or pixel brightness.
material Edges
properties and,provide
ideally, information aboutobject
they would mark the content of an image
boundaries throughsuch asof
a set variations
connectedin curves
depth, illumination
[29].
or material properties and, ideally, they would mark object boundaries through a set of connected
Several methods were proposed to perform edge detection in grayscale images. Among these, we can curves [29].mention
Several methods were proposed to perform edge detection in grayscale images. Among these, we
deterministic methods in which the filter is fixed such as Canny [4], Sobel operator [21], and optimization methodscan mention
deterministic methods in which the filter is fixed such as Canny [4], Sobel operator [21], and optimization methods

∗ Enescu Alina. Tel.: +4-074-614-5369

∗ Enescu Alina. Tel.: +4-074-614-5369
E-mail address: aenescu@cs.ubbcluj.ro
E-mail address: aenescu@cs.ubbcluj.ro

1877-0509 © © 2020 The Authors.

Author(s).Published
PublishedbybyElsevier
ElsevierB.V.
B.V.
1877-0509
Thisisisan
This © 2020
anopen
open Thearticle
access
access Author(s).
article Published
under
under by BY-NC-ND
Elsevierlicense
the BY-NC-ND
the CC CC B.V. license (https://creativecommons.org/licenses/by-nc-nd/4.0)
(https://creativecommons.org/licenses/by-nc-nd/4.0/)
This is an open
Peer-review
Peer-review access
under
under article under
responsibility
responsibility theofCC
of KES theBY-NC-ND
scientific license
International. committee(https://creativecommons.org/licenses/by-nc-nd/4.0/)
of the KES International.
10.1016/j.procs.2020.08.049
Peer-review under responsibility of KES International.
 Alina Enescu et al. / Procedia Computer Science 176 (2020) 470–479 471
Author / 00 (2020) 000–000 2

based on CA which evolve the filter [28, 24, 23, 9]. The Canny method has some weak points such as disconnected
edges, lack of detecting branching edges, while the latter methods are supervised which means that they need a ground
truth to evolve the edge detector, ground truth that is not always available. To surpass these issues, we propose a CA-
based edge detector adapted to grayscale images. To adapt to the image we choose to find the best CA’s rule by the
means of a Genetic Algorithm (GA). The GA uses an unsupervised fitness function based on edge dissimilarity.
The main difference between the proposed approach and similar CA-based methods within the current literature
is the fitness function. Compared to these methods, the proposed approach doesn’t need a ground truth to evaluate
the optimization process. Compared to our previous methods [11, 10], not only do we use an unsupervised fitness
function, but we also use a GA to find all the optimal parameters of the edge detector, not only the linear rule.
The experiments along with the results shown in this paper are meant to evaluate the capabilities of the unsupervised
edge detector based on evolved cellular automata.
The rest of the paper is structured as follows: Section 2 is a theoretical overview on the edge detection problem
and cellular automata; related work in the field is briefly presented in section 3; section 4 details the proposed edge
detection approach and the results are presented in Section 5; a summary of the experiments together with future
improvements is discussed in Section 6.

2. Theoretical background

Before describing the approaches existing in the literature, the edge detection problem is formulated and then a
short introduction to cellular automata is given.

2.1. Edge detection problem

Given the point P0 of a grayscale image with values in {0, 1, . . . , 255} and its eight neighbours Pi , i ∈ {1, 2, . . . , 8}
as in Figure 1a, the point may be classified as an edge [13] if a local significant change in intensity is detected within
the neighbourhood Pi , i ∈ {1, 2, . . . , 8}, while a contour may be defined as the curve composed of the points classified
as edges.
The mechanism that produces a set of edge points from a given image is an algorithm known as an edge detector.
The edge detection problem refers to finding an edge detector for a set of images.

(a) (b)

Figure 1: Visual representations of Moore neighbourhood. (a) A visual representation of a point P0 and its eight surrounding neighbors Pi , i ∈
{1, 2, . . . , 8}. (b) A visual representation of the nine fundamental rules for a 2D cellular automaton with a Moore neighbourhood, based on which a
linear rule is obtained.

2.2. Cellular automata

Cellular Automata (CA) are highly parallelizable computational models that can be represented by a five–tuple

CA = {C, N, S , s0 , ρ},

where the state (within the set of states S ) of a cell c ∈ C is updated in parallel with all other cells depending on
the states of neighbouring cells N (a finite set of size n with n = |N|), and the cell itself, based on the transition rule
ρ : S n → S . s0 is the initial state of the automaton [20].
2
472 Alina Enescu et al. / Procedia Computer Science 176 (2020) 470–479
Author / 00 (2020) 000–000 3

For describing the dependency of a cell’s state on its neighbours within a Moore neighbourhood, linear rules,
also known as Wolfram rules, have been introduced [26]. Linear rules are obtained by EX-OR operations among
the neighbours that contribute to a cell’s next state [15]. This contribution can be modelled in a binary manner by
assigning the value 1 to a neighbour which is taken into consideration and the value 0 to a neighbour which is not. By
assigning a power of 2 to each cell in the neighbourhood using the convention in Figure 1b, a binary number which
describes these dependencies is obtained. A linear rule is identified by the decimal analogue of this binary number.
Rules corresponding to powers of 2 are called fundamental rules. A linear rule can be obtained by summing up several
fundamental rules, for example Rule 140 = Rule 4 + Rule 8 + Rule 128 [8, 14, 15].

3. State of the art

There are multiple edge detection approaches in the literature which involve the use of cellular automata. For edge
detection on binary images, [19] uses a cellular automaton with a custom non-linear rule and applies it to images
of written characters. In [18] the aim is to show that there are four linear rules (namely rules 29, 113, 263 and 449)
which obtain the best binary edge detection results, while [2] searches for optimal outer totalistic rules tested on clean
images and also on images injected with various types of noise. In totalistic rules, the cell’s state depends only on the
total (or the average) of its neighbours’ states.
For grayscale edge detection there are approaches such as [22], which focuses on characterizing linear rules and
categorizing them into no-edge, weak-edge and strong-edge rules. There are also several approaches that involve
automatic identification of the best rules through various optimization methods. In [17] a cellular learning automaton
is used for identifying the optimal neighbourhood topology for each cell in a binary or grayscale image, after which a
threshold-based rule is applied, that outputs smoother edges than some classical edge detectors.
EAs have also been proposed for optimizing cellular automata rules for edge detection. [27] uses GAs by encoding
the binary representation of a linear rule into a chromosome. The fitness is computed as the distance between the
obtained edge map and the ground truth. The algorithm runs until the distance drops below a set threshold. In Uguz
et al. [28] the parameters of a two-step rule, consisting of a fuzzy membership function and a threshold function, are
optimized using PSO.
Apart from these methods, we mention the classic well-known methods based on computing the gradient: Canny
edge detector [4], Sobel operator and Prewitt operator [21]. The Canny edge detector presented in [4] is a method char-
acterized by three principles: detection, localization and single edge response. The first step of the Canny method is to
smooth the greyscale image by Gaussian filtering, then to compute the first derivative in both vertical and horizontal
directions. As the second step, it finds the magnitude and direction of each pixel. As a final step, it uses a non-maximal
suppression to ensure that the edges have one-pixel width and it uses two thresholds to select the final edge points and
to trace them. As complex as it is, this method has some weak points. Some improvements were proposed such as
[1, 6] where the authors try to surpass the loss of edges caused by the Gaussian filtering and the false negatives caused
by the Canny method’s sensitivity to noise, tested on images with asphalt concrete [1]. In [7], the authors propose a
solution to the missing edges issue that Canny has. They observed the results of the gradient magnitudes of the smooth
image obtained after applying the Gaussian filtering and because the gradient magnitude might not be larger than the
pixel value of the neighbours in the direction of the gradient, some edges are not detected. From the experiments that
were performed, they saw that fewer edges are detected on vertical, especially at the intersection with other edges,
and in case of the letters u, v, w, where the diagonal lines meet.

4. Proposed approach

In this section, we present each component of the proposed approach. The main focus of our method, called
Unsupervised Genetic Algorithm Edge Detector (Unsup-GA-ED), is to optimize the CA’s rule to detect edge points in
grayscale images without using any ground truth.
3
 Alina Enescu et al. / Procedia Computer Science 176 (2020) 470–479 473
Author / 00 (2020) 000–000 4

4.1. Cellular Automata Model

The main component of the proposed approach is a 2D-CA. The cells are arranged as a grid and mapped to an
image, the set of states is S = {0, 1, . . . , 255} corresponding to 256 grey levels, the chosen neighbourhood N is
the Moore neighbourhood and the initial state is given by the input image. To compute the next state, first an edge
membership function [28] is applied. The edge membership for a pixel P0 ∈ {0, 1, ..., 255} and its eight neighbours
Pi ∈ {0, 1, ..., 255} is defined as:


|P0 − Pi |
i
µ(P0 ) =  , (1)
∆ + i |P0 − Pi |

where i ∈ {1, 2, ..., 8} is selected according to a linear rule and µ ∈ [0, 1] [28].
The parameter ∆ ∈ {0, ..., 255} (one of the possible gray values for a pixel represented on 8 bits) is inversely
proportional to the number of detected edges. The higher its value, the fewer edges will be detected. The transition
rule is a function ρ : S n → {0, 1}, n = |N|, given by Equation (2) [28] which gives the final edge map.
The value of the threshold τ ∈ [0, 1) controls the number of pixels that pass as edges, therefore the higher the
threshold the fewer values will pass.

 1, if µ(P0 ) > τ
ρ(P0 ) = (2)
0, if µ(P0 ) ≤ τ

The quality of the edge detection is influenced by the ∆ and τ parameters as well as the linear rule.

4.2. Evolved Cellular Automata

The next component of the proposed approach is the GA that evolves the CA’s rule to detect edge points and it is
presented in the following.
The chromosome encodes the three parameters of the detector that need to be optimised: δ, τ and the linear rule.
The first two parameters are represented by using a grey encoding [12, 5, 25], while the rule is represented by using
binary encoding. In order to use the grey encoding for the real parameter τ, we encoded an integer value within
{0, 1, . . . , 127} and divided it by 128 to obtain the real value when the Equation 2 is applied. We chose to use the
grey encoding of the two parameters in order to keep the genetic operators, crossover and mutation, used in the binary
encoding and to overcome the Hamming Cliff [25] problem when using the binary encoding of an integer. An example
of a chromosome may be seen in Figure 2 where the rule 392’s binary representation is highlighted in blue, the grey
encoding of the threshold in purple and the grey encoding of the parameter ∆ in red, respectively.

Figure 2: An example of a chromosome composed of rule 392, the threshold τ = 120 (for Equation 2 will be 120/128 = 0.9375) and ∆ = 218.

In order to assess the quality of the individuals, a fitness function is needed. In this case, we use an unsupervised
function that measures the edge dissimilarity [3] over the entire image. The edge dissimilarity corresponding to a pixel
measures the disparity between two regions separated by an edge. In this case, the dissimilarity metric is the difference
between the average grey values of each region [3]. Considering a 3x3 Moore neighbourhood, cf. [3] it is possible to
defines valid two-neighbour edge structures in Figure 3a.
4
474 Alina Enescu et al. / Procedia Computer Science 176 (2020) 470–479
Author / 00 (2020) 000–000 5

We implemented a new variation of edge dissimilarity. This flavour quantifies the rendering of unnecessary or
inaccurate edges by penalizing invalid edge structures with a certain penalty. We may define the fitness function as
Σδ(P), where P is the set of pixels and δ : P → R is given by


|avg(r1 ) − avg(r2 )|, P0 has a valid edge structure as in Figure 3a
δ(P0 ) = (3)
, otherwise

where r1 , r2 are the two regions as in Figure 3b, avg(r) is the average over the intensity values of region r and  ∈ R
is either a reward (a positive value) when a greater sensitivity to edges is needed, either a penalty (a negative value)
when less sensitivity to edges such as noise reduction is needed.

x x x x x
x x x x x
x x

x x x x x
x x x x x
x x

x x x
x x x x x x
x x x

(b) Regions proposed for valid two-neighbour edge structures.

(a) Valid two-neighbour edge structures.

Figure 3: (a) Valid edge structures. Each edge structure is represented by a Moore neighbourhood where the pixel being considered is the central
pixel. The cells marked with a cross represent edge pixels while the unmarked cells represent non-edge pixels. (b) Regions proposed for valid edge
structures. There are two regions, each marked with black and grey, respectively.

For crossover, two individuals are selected by using the binary tournament selection and three random cutting–
points are chosen such as all three components are crossed. Then the three–points crossover is applied as expressed in
Figure 4. The bit flip mutation is applied to each offspring’s component: for each chromosome, a random gene (a bit)
is selected for each component and it is inverted.

Figure 4: Three-points crossover between two individuals encoding rule 392 with threshold τ = 120 and ∆ = 218, and rule 452 with threshold
τ = 27 and ∆ = 163, respectively. Two offspring are obtained encoding the rule 388 with threshold τ = 24 and ∆ = 220, and rule 456 with threshold
τ = 123 and ∆ = 165, respectively.

5
 Alina Enescu et al. / Procedia Computer Science 176 (2020) 470–479 475
Author / 00 (2020) 000–000 6

4.3. Edge Detector Schema

The proposed approach has a grayscale image as input. The first step is to extract the CA initial configuration from
the input image, called the input state. Each cell represents a pixel of the input image, therefore the cell’s initial state
is given by the intensity of the pixel.
The next step is running the GA that evolves the rules to detect edge points. The initial population is generated as
follows: the chromosomes, each encoding the binary representation of a linear rule, the grey code of a threshold and
the grey code of ∆, are randomly generated. Then the chromosomes are evaluated and the best one is kept to be added
to the new population obtained after applying the genetic operators to the current population. The process is repeated
for a fixed number of generations.
One best chromosome is obtained after the execution of the GA is finished. The best chromosome encodes the best
rule that will be used as detector for the considered image.

5. Experiments and comparisons

As described in the state-of-the-art, the Canny method has some weak points, such as disconnected edges and
sensitivity to branching edges. In the next experiments, the proposed approach will be compared with the Canny
method in the situations in which this method fails.
In the first experiment, as in [7] some images with different numbers of homogeneous regions will be tested. The
purpose of this experiment is to establish the capability of the proposed approach to obtain continuous edges compared
to the Canny method.
Firstly, an image that contains only four homogeneous regions, similar to the one taken as an example in the first
experiment presented in [7], is given as input to the proposed approach. Several runs are performed for this image as
input, with different values of the parameters received by the proposed approach, such as the penalty values for the
fitness function, number of generations or size of population for the GA. We state here that the search space of our
method is 512 × 128 × 256, as there are 512 linear rule, 128 values that threshold τ may have and 256 the parameter
∆ may have. The values that are given to the penalty influence directly the performance of the edge detector: if the
penalty is too high, fewer edges are detected, if the penalty is too low, more edges are detected, and in case of reward,
if the reward is too high, too many edges are detected, but if the reward is too low, much fewer edges are detected. As
for the population size, a small size would not be enough for the optimal parameters to be found, while a large size
would impact the speed of the algorithm and so the time spent to search for the optimal parameters. Regarding the
number of generations, a great number could give a better result, but even a relatively small number could give a good
result and would keep a short time spent on evolving the parameters.

(a) (b) (c) (d) (e) (f)

Figure 5: Results obtained on an image of four homogeneous regions: (a) Input image. (b) Ground truth. (c) Canny [4] result. (d) Proposed approach
result. (e) Canny [4] result zoomed on the central part. (f) Proposed approach result zoomed on the central part.

The results of the Canny method and the proposed approach on the image that contains four well defined homo-
geneous regions are presented in Figure 5. As the authors in [7] highlight in their experiments, the Canny method
produces disconnected edges at the intersection of the four regions. The same result we also obtained for the imple-
mentation from Matlab2013 of the Canny method. However, the proposed approach can detect branching edges for
all four regions similar to the ground truth.
6
476 Alina Enescu et al. / Procedia Computer Science 176 (2020) 470–479
Author / 00 (2020) 000–000 7

Next, to evaluate the impact of each parameter received by the proposed approach, we performed multiple runs
for this image, varying the values of the parameters. We chose for the fitness function two parameters: a reward in
case of a Moore neighbourhood of only white pixels (edge points) and a penalty in all the other cases, apart of the
neighbourhoods defined to compute the dissimilarities. The most impact on the performance of the edge detector
was recorded for the reward parameter given to the fitness function. Because of the low complexity of the image, the
only parameter that makes a significant difference is the reward, while the size of the population and the number of
generations had a minimal impact on the result. For example, in the case of an optimal value of the reward, the small
size of the population didn’t change the result at all, while in the case of a sub-optimal value of the reward, not even a
high number of generations could improve the result.

(a) (b) (c) (d)

Figure 6: Images obtained on the image with 16 homogeneous regions: (a) Input image. (b) Ground truth. (c) Canny [4] result. (d) Proposed
approach result.

We further test the algorithms on an image with 16 homogeneous regions, 8 dark and 8 light, with small variance
in intensity. The challenge of this image is the small differences in intensity of the neighbouring regions. In [7] the
authors report an incapacity of the Canny method to detect branching edges which can be also seen in Figure 6.
Compared to the Canny method, our proposed method can detect all edges including the branching edges.
To evaluate the impact of the parameters on this image, similar tests were done as for the previous image. The same
conclusions can be drawn in the case of the population size and the number of generations, because not even with 500
generations the best rule, ∆ and τ couldn’t be found for a bad value of the reward or penalty. But compared to the
previous experiment, the increased complexity of this example influenced the choice of the reward and penalty. We
observed that for this image a lower penalty had to be set to produce the desired edges.
The second set of experiments were done for images that contain printed text. The authors in [7] report in their
experiments on printed text images that the Canny method misses the edges at the intersection of diagonal lines as in
letters v and w. The purpose of this experiment is to emphasize the capability of our approach to detect even these
edges. The first image given as input is a similar image to the one used in the experiments of [7] and represents a light
grey text on a dark background. As it may be seen from Figure 7, the proposed approach succeeds in detecting the
edges even for the letters v and w as opposed to the Canny method where these edges are disconnected.

(a) (b) (c) (d)

Figure 7: Images obtained on the image with printed text: (a) Input image. (b) Ground truth. (c) Canny [4] result. (d) Proposed approach result.

As for the impact of the parameters on this image, several tests were done. The size of the population and the
number of generations used in these tests didn’t change the performance of the edge detector, but the value of the
penalty applied to compute the fitness had a much bigger impact on the performance of the edge detector: a high
penalty led to poor detection of edges.
7
 Alina Enescu et al. / Procedia Computer Science 176 (2020) 470–479 477
Author / 00 (2020) 000–000 8

(a) (b) (c) (d)

Figure 8: Images obtained on the image with printed text zoomed on specific parts: (a) Canny [4] result on letter w. (b) Proposed approach result
on letter w. (c) Canny [4] result on letter v. (d) Proposed approach result on letter v.

Another image that contains text but with two types of grey intensities, a white text and a light grey text on a black
background, was given as input. The issue, in this case, would be to detect the edges for both pieces of text and to
detect the edges of letter y. The results are shown in Figure 9. Both methods succeed in detecting edges for the two
pieces of text but the Canny method failed to detect the branching edges in the letter y.
(a) (b) (c) (d)

Figure 9: Images obtained on the image with printed text: (a) Input image. (b) Ground truth. (c) Canny [4] result. (d) Proposed approach result.

As the second part of these experiments, some performance measures are computed, such as the information en-
tropy, the Peak Signal to Noise Ratio (PSNR) and the correlation coefficient [6]. The information entropy measures
the degree of information of image. The higher the value of the information entropy is, the chance of more information
the image has. Even though is unusual to choose the information entropy in the evaluation process, it is an important
measure among the measures of information and by comparing the value computed on the edge detector result with
the value computed on the ground truth, it evaluates the similarity between the two edge images. The PSNR measure
the quality of the image and it is the ratio between two values: the maximum value a pixel can have (in fact, the power
of the signal) and the power of distorting noise that affects the quality of image representation. The greater the value
of PSNR is, the better quality the image has. The correlation coefficient measures the degree of relevance between two
images that are compared. The closer to 1 the value of the correlation coefficient is, the higher the relevance between
images is. While the information entropy is unary operator computed only based on the image that is meant to be
evaluated, the PSNR and the correlation coefficient are binary operators which use both the evaluated image and the
ground truth.

Table 1: Performance measures for the results of the two methods on the two images with homogeneous regions, 4 homogeneous regions and 16
homogeneous regions, respectively.

Four homogeneous regions image 16 Homogeneous regions image

Ground Truth Canny Prop. approach Ground Truth Canny Prop. approach
Entropy 0.1210 0.1178 0.1853 0.3093 0.1776 0.3068
PSNR 8.9178 8.9303 6.2788 6.2873
Correlation coeff. 1 -0.0122 0.5551 1 -0.0328 0.4756

The three measures computed for the two images resulted by applying the two compared methods, Canny method
and the proposed approach, and the ground truth image when the image that contains the four well-defined regions
is given as input, are displayed in Table 1. In the case of information entropy computed for this image the difference
8
478 Alina Enescu et al. / Procedia Computer Science 176 (2020) 470–479
Author / 00 (2020) 000–000 9

between the two compared methods is not too large, even though the greatest value is obtained for the proposed
approach. So in this case, the proposed approach image contains more information. The small difference between
the two values of the PSNR indicates a good quality of both images, but a better quality of the image obtained by
the proposed approach. As for the correlation coefficient, the greatest value and the closer one to the value one, as
obtained for the ground truth image, is obtained for the image given by the proposed method. This means that this
image is the closest to the ground truth image.
The second part of Table 1 contains the values of the three measures computed for the image that contains 16
homogeneous regions. As it may be seen, the image with the most information and the closest to the ground truth
based on information entropy is the one obtained by the proposed approach. We also obtain a small difference between
the two PSNR values for these examples as well as for the next two, as seen in Table 2. The conclusion is the same
for these three images, both methods obtain great quality images. As for the correlation coefficient, a better result is
obtained for the proposed approach.
As for the images that contain printed text, the conclusions are the same. The images obtained by the proposed
approach contain the most information as well. Moreover, the first image similar to the one used in [7] has the closest
value of the entropy to the one computed for the ground image, which means they contain almost the same amount
of information. Lastly, the value of the correlation coefficient is almost the same and the closest to 1 for both images
obtained by our method. The values of the three measures for the images that contain printed text are shown in Table
2.
Table 2: Performance measures for the results of the two methods on the images that contain printed text.

Printed text image 1 [7] Printed text image 2

Ground Truth Canny Prop. approach Ground Truth Canny Prop. approach
Entropy 0.7161 0.2778 0.6338 0.9122 0.2323 0.5363
PSNR 5.3762 5.3896 7.1049 7.1203
Correlation coeff. 1 0.3144 0.7424 1 0.2936 0.6597

In the end, the same three measures were computed for a subset of 22 images [28] extracted from Berkely dataset
[16]. The complexity of these images in terms of the number of objects, regions of grey and intensities of grey is
higher than the previous images used in the experiments. As may be seen from Table 3 and according to the Wilcoxon
Signed-Ranks Test p-values, even though the images obtained by the Canny method may contain more information
than the ones obtained by the proposed approach, our method contains a similar amount of information as the ground
truth. While the images obtained by the Canny method may be closer to the ground truth than the ones obtained by
the proposed approach, by a small margin, in terms of correlation coefficient, our method has better quality than the
Canny method in terms of PSNR. The average time spent on a generation for an image of size 321 × 481 is no more
than half a minute. Experiments were run on a computer with an Intel Core i7 processor, running at 1800 MHz using
8 GB of RAM, running Windows 10.

Table 3: Performance measures as average over the results of the two methods on a subset of 22 images from Berkely dataset [16].

Ground Truth Canny method Proposed approach Wilcoxon test

Entropy 0.1191 2.5588 0.8657 0.00004
PSNR 4.7266 9.1073 0.00004
Correlation coeff. 1 0.1050 0.0986 0.2626

6. Conclusions

In this paper we present an unsupervised edge detector based on evolved Cellular Automata for grayscale images.
The main advantage of this method is that it does not need a ground truth to evaluate the optimization of the three
parameters of the proposed approach. Compared to gradient-based methods, such as the Canny method, the proposed
approach adapts to the input image and so better results are achieved.
9
 Alina Enescu et al. / Procedia Computer Science 176 (2020) 470–479 479
Author / 00 (2020) 000–000 10

Based on the experiments shown in this paper, the proposed approach performs well, the obtained images contain
the most information according to the entropy measure computed on the results, have good quality according to the
PSNR and are the most similar to the ground truth according to the correlation coefficient. Compared with the methods
existing in the literature, the proposed approach overcomes some of the weak points of them.
As future work, more improvements can be done to the unsupervised fitness function, such as a better understanding
of the penalty parameter and the adjustment to the right amount of penalty for each level of complexity of the images.

References

[1] Agaian, S., Almuntashri, A., Papagiannakis, A., 2009. An improved canny edge detection application for asphalt concrete, in: 2009 IEEE
International Conference on Systems, Man and Cybernetics, IEEE. pp. 3683–3687.
[2] Amrogowicz, S., Zhao, Y., Zhao, Y., 2016. An edge detection method using outer totalistic cellular automata. Neurocomputing 214, 643–653.
[3] Bhandarkar, S.M., 1994. An edge detection technique using genetic algorithm-based optimization. Pattern Recognition 27, 1159 – 1180.
[4] Canny, J., 1986. A computational approach to edge detection. IEEE Transactions on pattern analysis and machine intelligence , 679–698.
[5] Caruana, R.A., Schaffer, J.D., 1988. Representation and hidden bias: Gray vs. binary coding for genetic algorithms, in: Machine Learning
Proceedings 1988. Elsevier, pp. 153–161.
[6] Deng, C.X., Wang, G.B., Yang, X.R., 2013. Image edge detection algorithm based on improved canny operator, in: 2013 International Confer-
ence on Wavelet Analysis and Pattern Recognition, IEEE. pp. 168–172.
[7] Ding, L., Goshtasby, A., 2001. On the canny edge detector. Pattern Recognition 34, 721–725.
[8] Dios, an, L., Andreica, A., Enescu, A., 2017. The use of simple cellular automata in image processing. Studia Universitatis Babes, -Bolyai
Informatica 62, 5–16. doi:10.24193/subbi.2017.2.01.
[9] Diwakar, M., Patel, P.K., Gupta, K., 2013. Cellular automata based edge-detection for brain tumor, in: ICACCI, IEEE. pp. 53–59.
[10] Dumitru, D., Andreica, A., Diosan, L., Bálint, Z., 2019. Particle swarm optimization of cellular automata rules for edge detection, in: 2019
21st International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), IEEE. pp. 320–325.
[11] Enescu, A., Andreica, A., Diosan, L., 2019. Evolved cellular automata for edge detection in grayscale images, in: 2019 21st International
Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), IEEE. pp. 326–332.
[12] Frank, G., 1953. Pulse code communication. US Patent 2,632,058.
[13] Jain, R., Kasturi, R., Schunck, B.G., 1995. Edge detection, in: Machine vision, McGraw-Hill New York. pp. 140–185.
[14] Kari, J., 2005. Theory of Cellular Automata: A Survey. Theor. Comput. Sci. 334, 3–33. doi:10.1016/j.tcs.2004.11.021.
[15] Khan, A.R., Choudhury, P.P., Dihidar, K., Mitra, S., Sarkar, P., 1997. Vlsi architecture of a cellular automata machine. Computers & Mathe-
matics with Applications 33, 79–94.
[16] Martin, D., Fowlkes, C., Tal, D., Malik, J., 2001. A database of human segmented natural images and its application to evaluating segmentation
algorithms and measuring ecological statistics, in: Proc. 8th Int’l Conf. Computer Vision, pp. 416–423.
[17] Mohammad, H.M., Sadeghi, S., Rezvanian, A., Meybodi, M.R., 2015. Cellular edge detection: Combining cellular automata and cellular
learning automata. AEU - International Journal of Electronics and Communications 69, 1282–1290. doi:10.1016/j.aeue.2015.05.010.
[18] Mohammed, J., Nayak, D.R., 2014. An efficient edge detection technique by two dimensional rectangular cellular automata, in: Information
Communication and Embedded Systems (ICICES), 2014 International Conference on, IEEE. pp. 1–4.
[19] Nayak, D.R., Dash, R., Majhi, B., Mohammed, J., 2016. Non-linear cellular automata based edge detector for optical character images.
Simulation 92, 849–859.
[20] Neumann, J.V., 1966. Theory of Self-Reproducing Automata. University of Illinois Press, Urbana, Illinois. Edited and completed by Arthur
W. Burks.
[21] Poobathy, D., Chezian, R.M., 2014. Edge detection operators: Peak signal to noise ratio based comparison. International Journal of Image,
Graphics and signal processing 6, 55.
[22] Qadir, F., Peer, M.A., Khan, K.A., 2012. Efficient edge detection methods for diagnosis of lung cancer based on two dimensional cellular
automata. Advances in Applied Science Research 4, 2050–2058.
[23] Rosin, P.L., Sun, X., 2014. Edge detection using cellular automata, in: Cellular automata in image processing and geometry, Springer. pp.
85–103.
[24] Sato, S., Kanoh, H., 2010. Evolutionary design of cellular automata for noise reduction of grayscale images. Transactions of the Japanese
Society for Artificial Intelligence 25, 311–319. doi:10.1527/tjsai.25.311.
[25] Schaffer, J., 1989. A study of control parameters affecting online performance of genetic algorithms for function optimization. San Meteo,
California .
[26] Schiff, J.L., 2007. ”Cellular Automata: A Discrete View of the World (Wiley Series in Discrete Mathematics & Optimization)”.
[27] Slatnia, S., Batouche, M., Melkemi, K.E., 2007. Evolutionary cellular automata based-approach for edge detection, in: Masulli, F., Mitra, S.,
Pasi, G. (Eds.), Applications of Fuzzy Sets Theory, 7th International Workshop on Fuzzy Logic and Applications, WILF 2007, Camogli, Italy,
July 7-10, 2007, Proceedings, Springer. pp. 404–411. URL: http://dx.doi.org/10.1007/978-3-540-73400-0_51.
[28] Uguz, S., Sahin, U., Sahin, F., 2015. Edge detection with fuzzy cellular automata transition function optimized by pso. Computers & Electrical
Engineering 43, 180–192.
[29] Umbaugh, S.E., 2010. ”Digital Image Processing and Analysis: Human and Computer Vision Applications with CVIPtools, Second Edition”.
2nd ed., CRC Press, Inc., Boca Raton, FL, USA.

10

View publication stats