# Cellular Automata Supportingn-Connectivity

Authors: Biljana Stamatovic; Gregor Kosec; Roman Trobec; Xiao Xuan; Sinisa Stamatovic
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We propose a new algorithm based on cellular automation (CA) for preservingn-connectivity, n
>
1. The CA algorithm transforms an initial grid configuration in a grid with same number of holes but without 1-connected components. Also, maximal thinning of n-connected components, n
>
1, is achieved. The grid can be used as initial for investigating properties of initial grid. Computational performances are evaluated and measured on real cases. The obtained results indicate that the proposed approach achieves comparable complexity as standard approaches; however, the speed-up and scalability of the proposed algorithm are not limited by the number of processing nodes.


---

## Body

## 1. Introduction

The cellular automata (CA) can be considered as an alternative way of computation based on local data flow principles. The concept of CA was first proposed by Neumann in 1950s through self-reproducing systems [1]. Later, the formalization was improved by different authors [2–5] emphasizing different perspectives. The application areas of CA become very different, ranging from biology [6, 7], sociology [8], image processing [9], diffusion of soil pores [10], and so forth.A CA can be informally represented as a set of regularly and locally connected identical elements. The elements can be in a finite set of states. The CA evolves in discrete time steps, changing the states of elements according to a local rule, which is the same for all elements. The new state of each element depends on its previous state and on the state of its neighbourhood. The neighbourhood is composed of all directly connected elements. The characteristic properties of CAs are therefore locality, discreetness, and synchrony.Identification of isolated regions in binary images is important problems in image processing, machine vision, porous materials analysis, and many other fields of science. The shrinking of binary picture patterns, which is a step towards the recognition of image objects, has been first investigated, using CAs, by Neumann [1], Thatcher [2], and Levialdi [11]. Parallel versions of these algorithms have been developed in [3, 12]. An improved algorithm with a linear complexity has been proposed in [4, 13].In this paper we propose a new algorithm for thinning of an arbitrary binary rectangular grid. The algorithm preserves 2 or more levels of connectivity of all components on the grid. Hence, the number of isolated parts is preserved. Also, the thinning is maximal in sense ofn-connectivity of all components in initial grid, n
>
1.The rest of the paper is organized as follows. In Section2, basic definitions of n-connectivity and CAs are introduced. In Section 3, our CA is defined with its properties. Section 4 is devoted to implementation and performance analysis. Finally, the work is summarized in Section 5.


## 2. Definitions

We consider a cellular automation (CA) as a 2-dimensional lattice network of square cells (grid). Each cell can exist in two different sates, 0 or 1. Usually, state 0 is commonly called “white” and state 1 is commonly called “black.”Cells of the lattice network change their states in discrete moments in time, time steps. Cell’s next state is defined bylocal transition function (rule). Local transition function manages with altering state of each cell, based on the present state and states of neighbourhood’s cells. We use Moore neighbourhood (Figure 1(a)) and typical enumeration for the rectangular array (Figure 1(b)). We denote state of the central cell (
i
,
j
) in a moment t
≥
0 by c
(
i
,
j
)
t. Arguments of a local transition function are ordered collections c
t
=
(
c
(
i
+
1
,
j
-
1
)
(
t
), c
(
i
+
1
,
j
)
(
t
), c
(
i
+
1
,
j
+
1
)
(
t
), c
(
i
,
j
-
1
)
(
t
), c
(
i
,
j
)
(
t
), c
(
i
,
j
+
1
)
(
t
), c
(
i
-
1
,
j
-
1
)
(
t
), c
(
i
-
1
,
j
)
(
t
), c
(
i
-
1
,
j
+
1
)
(
t
)
) of the neighbourhoods cell’s states in time step t. We use graphical notation for this (e.g., in Figure 3). This alternation of cell states is synchronous.Moore neighbourhood and its enumeration.
(a)
(b)Configurationconf
A
(
t
,
C
0
) of the cellular automation A is the assignment of states to all cells in the grid in a moment t
≥
0 starting from an initial configuration C
0. CA is often simulated on a finite grid. In our simulation, boundary cells are in fixed state and remain constant throughout the simulation.Two cells(
i
1
,
j
1
) and (
i
2
,
j
2
) are (weakly)adjacent if (
max
⁡
⁡
{
i
1
-
i
2
,
j
1
-
j
2
}
≤
1
)
i
1
-
i
2
+
j
1
-
j
2
≤
1. Two black (white) cells (
i
1
,
j
1
) and (
i
n
,
j
n
) areconnected if there exists a sequence of black (white) cells (
i
k
,
j
k
), 2
≤
k
≤
n, such that each pair (
i
k
-
1
,
j
k
-
1
) and (
i
k
,
j
k
)  is adjacent. That sequence (
i
k
,
j
k
), 1
≤
k
≤
n, is apath which connects cells (
i
1
,
j
1
) and (
i
n
,
j
n
).Length of the path is n
-
1. Cell (
i
1
,
j
1
) is start cell and (
i
n
,
j
n
) is end cell of the path.Cycle or closed path is a path with same start and end cell. n
-cycle is a closed path of length n. According to the adjacency, we do not have 3-cycle. 2-cycle is a “column” or “row” with two cells. A maximum connected region of black cells is called acomponent.Similary, black (white) cells(
i
1
,
j
1
) and (
i
n
,
j
n
) areweakly connected if there exists a sequence of black (white) cells (
i
k
,
j
k
), 2
≤
k
≤
n, such that each pair (
i
k
-
1
,
j
k
-
1
) and (
i
k
,
j
k
)  is weakly adjacent. A maximum weakly connected region of white cells is called ahole. Always there is a single external (infinite) hole. A maximum weakly connected region of black cells is called aweakly component.For the moment, suppose that we have just one componentK on the grid. Then, we say that component K isk-connected if its complement K
¯ has (
k
-
1
) finite holes. Number k is thelevel of connectivity of the component K. Now, on the same way we can find the level of connectivity for all other components in the grid. For example, in configuration C
0 from Figure 2(a), we have three components (one is 3-connected (C
1), one is 2-connected (C
2), and one is 1-connected (C
3)) and three finite holes (H
1, H
2, and H
3).(a) A configurationC
0, (b) conf
A
1
(
C
0
,
1
), and (c) conf
A
1
(
C
0
,
7
), t
>
7.
(a)
(b)
(c)Figure 3
Local states which define local transition function for CAA
1, x
∈
{
0,1
}.Leta be a cell. Two black (white) cells are (weakly)connected in neighbourhood of
a if there exists a black (white) connected path of cells from the neighbourhood which (weakly) connect these two cells.We solve the problem of thinning an initial configuration to a configuration with the same number of holes.


## 3. Cellular AutomationA
1 and Its Properties

Define a CAA
1 with a local transition function φ
A
1 which is defined by
(1)
c
i
,
j
t
+
1
=
0
,
r
1
∨
r
2
∨
r
3
∨
r
4
∨
r
5
,
0
,
r
6
p
∨
r
7
p
∨
r
8
p
,
p
=
t
+
1
mod
⁡
4
,
c
i
,
j
t
,
otherwise
,
t
≥
0
,
where r
i or r
j
p, 1
≤
i
≤
5, 6
≤
j
≤
8, 0
≤
p
≤
3, presents local states of the central cell and its neighbourhoods in some moment t
≥
0 from Figure 3.Applying the local transition function to all cells of an configuration simultaneously, we get the sequence of configurationsconf
A
1
t
,
C
0, t
≥
1, started from some initial configuration C
0. For example, if C
0 is the configuration from Figure 2(a), then in Figures 2(b) and 2(c) we have conf
A
1
1
,
C
0 and conf
A
1
t
,
C
0, t
>
7.Theorem 1.
LetC
0 be a configuration. CA A
1 has the following properties.(1)
A finite number of time stepst
>
0 exist in which each 1-connected component in C
0 vanishes after t steps.
(2)
For eacht
>
0 and for each n-connected component, K in C
0, n
>
1, component c
o
n
f
A
1
(
t
,
K
) is n-connected in c
o
n
f
A
1
(
t
,
C
0
).
(3)
There ist
=
t
s for which c
o
n
f
A
1
(
t
+
k
,
C
0
)
=
c
o
n
f
A
1
(
t
s
,
C
0
), for all k
>
0.
(4)
Let the configurationc
o
n
f
A
1
(
t
s
,
C
0
) have components K
1
,
K
2
,
…
,
K
m, m
>
0. Let a component K
j be n
j-connected, n
j
>
1, 1
≤
j
≤
m. Let d
∈
1,2
,
…
,
m. For any black cell (
i
,
j
)
∈
K
d, if the cell changes its state to white (c
(
i
,
j
)
=
0), then the obtained component K
d
′ is l-connected, where l
<
n
d or the obtained configuration c
o
n
f
A
1
′
(
t
s
,
C
0
) has >
m components.Proof of Theorem1.
Notice, those white cells remain always white (r
5 in Figure 3). From this fact, it follows that CA A
1 cannot connect two disconnected components. So, each component can be observed independently and for each component we can assume that its complement has all white cells.
LetK be 1-connected component. For the component K we will prove that in any time step there are one or more black cells that are transformed in white. Hence, because of finiteness, after some time steps, the component will vanish.
LetK
n
,
m be circumscribing rectangle of dimensions n
×
m for K, n
,
m
≥
1.
Ifn
=
1 or m
=
1, component K is “column” or “row” and K has two ends which are transformed in white cells according to r
1, r
2, r
3, or r
4 from Figure 3.
Suppose thatn
>
1 and m
>
1. If component K has a cell with 3 or 4 adjacent white cells, then according to r
1, r
2, r
3, or r
4 from Figure 3 this cell is transformed in white.
So, we suppose that all cells have no more than 2 adjacent white cells. Traversing boundary cells in negative direction (component is always on the left side), we create a closed pathP
K
:
v
1
,
v
2
,
v
3
,
…
,
v
k
,
v
k
+
1
,
…
,
v
l
,
v
1, l
>
3, shown in Figure 4(b).
Supose that we observe a time stept, where (
t
+
1
)
mod
⁡
4
=
0. Denote by v
1 and v
k, k
∈
2,3
,
…
,
l, the bottom rightest and top rightest cells in the component, respectively. Similar, we can observe time steps t, where (
t
+
1
)
mod
⁡
4
∈
1,2
,
3.
We consider two cases:(1)
cellsv
1
,
v
2
,
v
3
,
…
,
v
k
,
v
k
+
1
,
…
,
v
l are all different,
(2)
some of cellsv
1
,
v
2
,
v
3
,
…
,
v
k
,
v
k
+
1
,
…
,
v
l are equal.
In case 1, cellsv
1, v
k have the neighbourhoods as r
7
0, r
6
0 from Figure 3. If this is not case, then one of them, for example v
1
=
(
i
,
j
), has the neighbourhood (
x
,
0
,
x
,
0,1
,
1
,
x
,
1,0
). Then, the white cell in (
i
-
1
,
j
+
1
) position surrounded by the path P
K which is in contradiction with K is 1-connected (path P
K surrounds a finite hole).
In case 2, there exists a closed pathS (see Figure 4): v
i
,
v
i
+
1
,
v
i
+
2
,
…
,
v
i
+
k
,
v
i in P
K with length k
+
1
>
3, in which all cells are different, except ends. In the closed path S, as we already proved in the previous paragraph, there exists a cell with neighbourhood as r
6
0 or r
7
0 from Figure 3.
With this we proved Theorem1, property 1.
All neighbourhoods from Figure3 are such that if central cell changes its black state to white, then connectivity of its neighbouring black cells is preserved or “new” central white cell connects already weakly connected neighbouring white cells. So, local transition function of the CA A
1 preserves the level of connectivity for each component. With this we proved Theorem 1, property 2.
Because of finiteness of components and deterministic rules, Theorem1, property 3 is obvious.
Suppose that black cella
=
(
i
,
j
)
∈
K
d. We will prove that the cell a has at least two white cells in its neighbourhood. So, we can suppose that(1)
cella has no neighbouring white cells,
(2)
cella has one neighbouring white cell.
If we have case 1, then cell(
i
-
2
,
j
) is also black (r
8
0 from Figure 3). Because of symmetry, this holds for cells (
i
+
2
,
j
), (
i
,
j
+
2
), and (
i
,
j
-
2
), also. Further, cell (
i
-
2
,
j
+
1
) is also black (r
6
0 or r
8
0 from Figure 3). Because of symmetry, this holds for cells (
i
-
1
,
j
+
2
), (
i
+
1
,
j
+
2
), (
i
+
2
,
j
+
1
), (
i
+
2
,
j
-
1
), (
i
+
1
,
j
-
2
), (
i
-
1
,
j
-
2
), and (
i
-
2
,
j
-
1
), also. Continuing, we have that all cells in conf
A
1
t
s
,
C
0 are black. Because of boundary condition and finiteness, there is a cell which changes its state in the configuration which is in contradiction that K
d is a component in conf
A
1
t
s
,
C
0 (property 3).
Same consideration holds for case 2.
Now, we will prove that cella has at least two nonweakly connected, in the neighbourhood, white neighbours. Because cell a has at least two connected black neighbours (r
1
,
r
2
,
r
3
,
r
4 from Figure 3), we have three cases.(1)
Cella has exactly two connected black neighbours. We can suppose that black cells are
(a)
(
i
+
1
,
j
) and (
i
,
j
-
1
) or
(b)
(
i
-
1
,
j
) and (
i
+
1
,
j
).
In case (a), cell(
i
+
1
,
j
-
1
) must be white (r
6
0 from Figure 3). Case (b) is obvious.
(2)
Cella has exactly three connected black neighbours. We can suppose that the tree black cells are (
i
+
1
,
j
), (
i
,
j
-
1
), and (
i
,
j
+
1
). Then, cells (
i
+
1
,
j
+
1
), (
i
+
1
,
j
-
1
) cannot be black at the same time (r
8
0 from Figure 3).
(3)
Cella has exactly four connected black neighbours. This case is obvious.
Hence, in every case we have two white cells in the neighbourhood of the cella which are nonweakly connected, in the neighbourhood.
If these two neighbours are weakly connected in the configurationconf
A
1
t
s
,
C
0, then they are from the same hole. Changing state of the cell a will increase the number of components in conf
A
1
t
s
,
C
0.
If these two neighbours are not weakly connected in the configurationconf
A
1
t
s
,
C
0, then they are from different holes. Hence, changing state of the cell a will decrease the number of holes in conf
A
1
t
s
,
C
0.(a) ComponentK with its circumscribing rectangle; (b) boundary path P
K of the K.
(a)
(b)Now, we consider the theoretical complexity of the algorithm by means of the required number of time steps. LetC be a configuration. Let C have components K
1
,
K
2
,
…
,
K
p, p
≥
1. Suppose that dimension of circumscribing rectangle of component K
i is n
i
×
m
i, 1
≤
i
≤
p. From the proof of the Theorem 1 we have the following.Corollary 2.
The worst case complexity of the CAA
1 for the configuration C is max
⁡
n
i
·
m
i
∣
1
≤
i
≤
p.


## 4. Implementation and Experimental Results

Implementations of the algorithm are made in NetLogo 5.0.4 (agent-based programming language and integrated modelling environment). The CA model is represented by 2-dimensional grid of square cells and each cell can exist in two different sates, white or black. Any cell is coloured black with probabilityp and white with probability 1 p. These probabilities are independent for every cell. Within an iteration, the whole grid is processed at once; namely, each cell is transformed to a new state without affecting the other cells. After the update, algorithm proceeds to a new iteration. The iteration takes place as long as at least one cell is changed. The global operations in the algorithm are the steady state checking and alternating numbers from 0,1
,
2,3. However, here we emphasize that the alternation of numbers from 0,1
,
2,3 is possible to substitute by randomly choosing a number from 0,1
,
2,3. With this we obtain nondeterministic CA with no need for the global operation.In Figure5 we present examples of the implementation. In all examples 201 × 201 grid is used. Differences are in generating initial grid. In Figures 5(a), 5(b), and 5(c) random grid with densities 0.55, 0.50, and 0.65 is used, respectively.Examples of grids with resolution 201 × 201. Left is original and right is after CAA
1 implementation.
(a)
Probability for black cell is 0.55
(b)
Probability for black cell is 0.60
(c)
Probability for black cell is 0.65


## 5. Conclusions

We proposed a new CA algorithm for thinning with property of preservingn-connectivity, n
>
1, of all components in any random binary grid. Simple definition of used CA has several advantages; for example, CA is not limited by the number of elements, its evolution is inherently parallel, it has a strong resemblance to the important approaches in the nature like principles of cells that are building blocks for large systems or elementary particles, and so forth. However, several drawbacks can also be identified, for example, lack of global communication, which implies problems, related to global synchronization, inability for calculation of complex mathematical operations, and so forth. However, the heterogeneous computing, supported today with data flow approaches, field programmable gate array (FPGA), and graphic processing unit (GPU) systems, systems on chips, are promising platforms for the implementation of the efficient CA algorithms. Finally, further work is also in the investigation of necessary extensions of the algorithm for 3D grids.



---

*Source: 765798-2014-11-19.xml*