1 Introduction

Creating aesthetically pleasing imagery has been dominated by the application of evolutionary computing. The “Bimorphs” of Dawkins (1986), “Mutators” of Latham Todd et al. (1991), and “Virtual Creatures” of Sims (1994) are the classical examples. Although some impressive results have been achieved, there still remain problems with the aesthetic selection. That is devising a fitness function to replace human adjustment in the process of generation and evaluation.

In this study we investigate the aesthetics of cellular automata (CA) behaviour. CA invented by von Neumann in the late 1940s as material-independent systems to investigate the possibility of self-reproduction. A cellular automaton consists of a lattice of uniformly arranged finite state automata each of which taking input from the neighbouring automata; they in turn compute their next states by utilising a state transition function. A synchronous or asynchronous interactive application of state transition function (or rule) over the states of automata (or cells) generates the global behaviour of a cellular automaton that sometimes can be very complex with high aesthetic quality.

The property of CA that makes them particularly interesting to digital artists is their ability to produce visually appealing and logically deep patterns on the basis of very simply stated preconditions. Traditional scientific intuition, and early computer art, might lead one to assume that simple programs would always produce pictures too simple and rigid to be of artistic interest. But extrapolating from Wolfram’s work on CA, “it becomes clear that even a program that may have extremely simple rules will often be able to generate pictures that have striking aesthetic qualities sometimes reminiscent of nature, but often unlike anything ever seen before” (Wolfram 2002, p. 11). This is a new way of generating imagery which has no precedent in human culture (Roth and Deutsch 2011). CA have been used as artistic tool since the 1960s. The most notable examples are “Pixillation”, one of the early computer-generated animations (Schwartz and Schwartz 1992), the digital art works of Struycken (Scha 2006; Struycken 1976) and Brown (Beddard and Dodds 2009; Brown 2001) [a review of the application of CA in digital art provided in Javaheri Javid et al. (2015)]. Images generation by CA has unique qualities compared to imagery generated by other approaches like evolutionary art. This is due to processing elements which are pixels in evolutionary approaches where in CA the processing elements are cells. In addition there is always an implicit relationship between cells and its surround because of the neighbourhood relation. Although classical one-dimensional CA with binary states can generate complex behaviours, experiments with multi-state two-dimensional (2D) CA have shown that adding more states significantly increases the complexity of behaviour, therefore, generating very complex symmetrical patterns (Javaheri Javid et al. 2014; Javaheri Javid and te Boekhorst 2006) which are extremely challenging to generate using conventional mathematical methods. A recent work by Adamatzky and Martínez (2016) offers insights in the production of art works, using simple computational models with morphological behaviour, at the edge of mathematics, computer science, physics and biology, where CA is explored in further details.

In this study we approach the problem in the framework of dynamical systems and define a criterion for aesthetic selection in terms of its association with symmetry. The association of aesthetics and symmetry has been investigated from different points of view. In this paper, a brief account on cellular automata is presented, followed by a section on symmetry and its significance in aesthetics. Then, a swarm intelligence algorithm—Stochastic Diffusion Search—is explained, highlighting its main features, including its unique partial function evaluation aspect. Afterwards, the application of the algorithm in detecting points of symmetry is detailed, illustrating the performance of the method proposed.

2 Cellular automata

For the purpose of this study we provide a formal definition for 2D CA as follows and for the rest of the paper all the notions will be referring to this definition.

Definition 1

A deterministic finite automaton is formally defined (Linz 2001) as a quintuple of \(\mathcal {M}\) such that:

$$\begin{aligned} \mathcal {M=}\langle Q,\varSigma ,\delta ,q_{0},F\rangle \end{aligned}$$
(1)
  1. 1.

    Q is a finite set of states,

  2. 2.

    \(\varSigma \) is a finite set of symbols as input alphabet,

  3. 3.

    \(\delta : Q \times \varSigma \mapsto Q\) is the state transition function,

  4. 4.

    \(q_{0} \in Q\) is the start or initial state,

  5. 5.

    \(F\subseteq Q \) is a set of accepting or final states.

The state transaction function \(\delta \) determines the transitions from one state to another state. It takes two arguments as \(q \in Q\) and an input symbol \(a \in \varSigma \) then maps them to a final state \(q_1 \in Q\) (i.e \(\delta (q,a)=q_1\)).

Definition 2

A lattice (L) is a regular tiling of a space by a unit cell.

The Euclidean plane is considered so the lattice L is over \(Z^2\). Lattices can have square, hexagonal or triangle for their unit cells. A lattice can be infinite with open boundary conditions or finite with periodic boundary conditions. A finite lattice with periodic boundary conditions where the opposite borders (up and down with left and right) are connected, forms a virtual torus shape (Fig. 1).

Fig. 1
figure 1

Formation of virtual torus shape in a lattice with periodic boundary conditions

Full size image

Definition 3

A cellular automaton is a lattice of regularly tiled by deterministic finite state automaton as unit cell.

A cellular automaton is presented as a quadruple of \(\mathcal {A}\) such that:

$$\begin{aligned} \mathcal {A}= \langle L,S,N,f \rangle \end{aligned}$$
(2)
  1. 1.

    L is a finite square lattice with periodic boundary conditions,

  2. 2.

    \(S \subseteq \mathbb {N}^0\) is a finite set of non-negative integers as states,

  3. 3.

    \(N \subseteq \mathbb {N}^+\) is a finite set of non-negative integers as neighbourhood,

  4. 4.

    \(f: S^{|N|} \mapsto S\) is the state transition function.

Fig. 2
figure 2

von Neumann (a) and Moore (b) neighbourhood templates

Full size image
Fig. 3
figure 3

A space–time diagram depicts the behaviour of a cellular automaton as the sequence of configurations

Full size image

The state transition function f maps from the set of neighbourhood states \( S^{|N|}\) where |N| is the cardinality of neighbourhood set, to the set of states \(S=\{s_{0},\ldots ,s_{n-1}\}\) synchronously in discrete time intervals of \( t = \{0,1, 2 , 3,\ldots , n\} \) where \( t_0 \) is the initial time of the cellular automaton. By convention every automaton on the lattice is in neighbourhood relation with itself. A mapping that satisfies \(f ( s_{0},\ldots ,s_{0} ) = s_{0}\) where \(s_{0}\in S\) is called a quiescent state. In other words, if a lattice is considered as a set, then its elements are deterministic finite automata such that \(L=\{m_1, m_2,\ldots , m_n\} \). The state of each cell at time \((t+1)\) is determined by the states of immediate neighbouring cells (nearest neighbourhood) at time (t) given a neighbourhood template. There are two commonly used neighbourhood templates considered for 2D CA. A five-cell mapping (\(f: S^{5} \mapsto S\)) known as von Neumann neighbourhood (Eq. 3; Fig. 2a) and a nine-cell mapping (\(f: S^{9} \mapsto S\)) known as Moore neighbourhood (Eq. 4; Fig. 2b).

$$\begin{aligned} s_{i,j}^{t+1}= & {} f \left( \begin{array}{ccc} &{} s_{(i,j+1)}^{t} &{} \\ s_{(i-1,j)}^{t} &{} s_{(i,j)}^{t} &{} s_{(i+1,j)}^{t} \\ &{} s_{(i,j-1)}^{t} &{} \end{array} \right) \end{aligned}$$
(3)
$$\begin{aligned} s_{i,j}^{t+1}= & {} f \left( \begin{array}{ccc} s_{(i-1,j+1)}^{t} &{} s_{(i,j+1)}^{t} &{} s_{(i+1,j+1)}^{t} \\ s_{(i-1,j)}^{t} &{} s_{(i,j)}^{t} &{} s_{(i+1,j)}^{t} \\ s_{(i-1,j-1)}^{t}&{} s_{(i,j-1)}^{t} &{} s_{(i+1,j-1)}^{t} \end{array} \right) \end{aligned}$$
(4)

A function \( F : S^L \mapsto S^L\) which gives the global state as configuration C over the lattice L at time t is the global transition function. F maps the configuration at time t to the configuration at time \( t+1 \) where \( C \in S^L\).

$$\begin{aligned} C^{t+1} = F \left( C^t\right) \end{aligned}$$
(5)

The sequence (\( c^0, c^1 , c^2,\ldots , c^{n-1}\)) collectively is the behaviour of a cellular automata (also referred as the global behaviour) where \(c^0\) is the initial configuration at \(t=0\). The graphical representation of the sequence of configurations as the behaviour of a cellular automaton by assigning a colour for cell states over the lattice called a space–time diagram (Fig. 3).

Table 1 A Comparison of the rule spaces for two state 2D CA using formulas
Full size table
Fig. 4
figure 4

Formation of patterns from a single cell as initial configuration

Full size image
Fig. 5
figure 5

Formation of patterns from a glider as initial configuration

Full size image

The total number of possible state transition functions as the size of rule space \( \varPhi \) can be obtained from

$$\begin{aligned} \varPhi =|S|^{|S|^{|N|}} \end{aligned}$$
(6)

where |S| is the cardinality of S and |N| is the cardinality of N. For instance given a two state (\(|S|=2 \)) mapping with Moore neighbourhood template (\(|N|=9 \)), then \( \varPhi = 2^{2^9}=2^{512} \approx 1.3 \times 10^{154}\). In order to put this number in perspective it can be noted that the number of atoms in visible universe is \(\approx 10^{80}\). This excessively large number of state transition functions neither can be stored in any modern computer nor it can be algorithmically defined. A common approach to overcome this problem is to define a subset(s) of all possible state transition functions by a formula. Two commonly applied formulas to generate such subsets are totalistic rules and outer totalistic rules where the state of each cell is updated according to the sum of the states of the neighbouring cells in given template. Equations 7 and 9 show the generation of totalistic (tot) and outer totalistic (outer-tot) rules for Moore neighbourhood template. The new state by applying an outer totalistic rule depends on a tuple, namely the old state (\( s_{i,j}^t \)) and the sum of the neighbourhood without the current state. It does not only depend on the neighbourhood’s sum as in the totalistic rule.

Table 2 Specifications of cellular automaton 1
Full size table
Table 3 Specifications of cellular automaton 2
Full size table
$$\begin{aligned} \text {Totalistic rules: } s_{i,j}^{t+1} = f_{tot}(\sigma _{tot}) \end{aligned}$$
(7)

where

$$\begin{aligned}&\sigma _\mathrm{tot} = \sum \left\{ \begin{array}{ccc} s_{(i-1,j+1)}^{t} &{} s_{(i,j+1)}^{t} &{} s_{(i+1,j+1)}^{t} \\ s_{(i-1,j)}^{t} &{} s_{(i,j)}^{t} &{} s_{(i+1,j)}^{t} \\ s_{(i-1,j-1)}^{t}&{} s_{(i,j-1)}^{t} &{} s_{(i+1,j-1)}^{t} \end{array} \right\} \end{aligned}$$
(8)
$$\begin{aligned}&\text {Outer totalistic rules: }s_{i,j}^{t+1} = f_\mathrm{outer-tot} (\sigma _\mathrm{outer-tot}) \end{aligned}$$
(9)

where

$$\begin{aligned} \sigma _\mathrm{outer-tot} = \sum \left\{ \begin{array}{ccc} s_{(i-1,j+1)}^{t} &{} s_{(i,j+1)}^{t} &{} s_{(i+1,j+1)}^{t} \\ s_{(i-1,j)}^{t} &{} &{} s_{(i+1,j)}^{t} \\ s_{(i-1,j-1)}^{t}&{} s_{(i,j-1)}^{t} &{} s_{(i+1,j-1)}^{t} \end{array} \right\} \end{aligned}$$
(10)

Table 1 demonstrates the reduction in the size of rule space by formulas to generate subset of state transaction functions.

The behaviour of a particular cellular automaton is constrained by initial configuration, transaction function, the number of states and the number of time intervals. In the lack of any viable model to evaluate the behaviour of 2D CA given state transition function, the only available method is to run simulations. Given the vast size of the rule space and the fact that rule space is an unstructured space such that by knowing the behaviour a particular cellular automaton or a set of CA, the behaviour of other CA cannot be induced. CA examples (Tables 2 and 3) demonstrate the formation of patterns from a single cell (Fig. 4) and glider as initial configurations (Fig. 5). And Fig. 6 shows experimental patterns generated by the authors to demonstrate the generative capabilities of CA in creating very complex symmetrical patterns.

Fig. 6
figure 6

Sample complex symmetrical patters generated by CA

Full size image

3 Symmetry and aesthetics

The association of aesthetic preferences and symmetry of a stimulus has been investigated extensively in the literature. Symmetry having proportionality and balance is considered to be an important element of aesthetics. The role of symmetry in art, architecture and its association with aesthetic preferences is a well-known concept (Møller 1998). Natural objects displaying symmetry evoke wonder and surprise because of their intricacy. For example, architecture and architectural details, such as stain windows, mosaics, and friezes, visual arts, pottery and ceramics, quilts, textiles, and carpets, make a varied use of symmetry as an important principle in their design. An examination of architecture and cell biology in terms of biosemiotics, with architectural structures, discussed as context-dependent semiotic objects with functional and/or aesthetic values. Both the natural and man-made environment can be perceived as locus, place, site, or a part of a mental map of a cultural framework. Maybe for that reason symmetry is so often seen not only beautiful but also conducive to visual communication (Ferreira 2012).

People find symmetrical patterns more beautiful than asymmetrical patterns (Jacobsen et al. 2006). A study investigating the effect of symmetry on interface judgements, and relationship between a higher symmetry value and aesthetic appeal for the basic imagery shows preference of symmetric over asymmetric images (Bauerly and Liu 2006). Further studies found that if symmetry is present in the face or the body, an individual is judged as being relatively more attractive and if the body is asymmetric the face is rated unattractive, even if the person doing the rating never sees the body (Randy and Steven 1993; Gangestad et al. 1994). Symmetry plays a crucial role in theories of perception and is even considered a fundamental structuring principle of cognition (Leyton 1992). From evolutionary perceptive physical appearances like as symmetry, and perceived level of aesthetics as an indirect measure in mate selection (Møller 1998; Møller and Cuervo 1999). It is not surprising that humans find sensory delight in symmetry, given the world in which we evolved. In our world the animals that have interested us and our ancestors (as prey, menace, or mate) are overwhelming symmetric along at least one axis (Railton 1998). Studies demonstrate the direct effects of symmetry on attractiveness (Grammer and Thornhill 1994). In other words symmetry is positively linked with both psychological and physiological health indicators (Shackelford 1997). The processing fluency theory states that a person has a certain mental state that facilitates the processing of specific information. This state may emerge from both stimulus attributes (e.g. it is easier to process symmetrical stimuli; Reber et al. 2004). In particular, symmetric objects are more readily perceived (Carroll 2003).

In geometry a shape is attributed as symmetrical if it is invariant to the application of one or more symmetry operations like translation, rotation, reflection, and glide reflection. The type of a symmetrical object is also specified with respect to a given symmetry operation(s) applied to the object when this operation preserves some property of the object. Such operations form a symmetry group of the object. In geometry symmetrical shapes are generated by applying symmetry operations like translations, rotations, reflections, and glide reflections. There are several types of symmetry, for example, the line or the radial mirror symmetry. Mirror symmetry, a symmetrical object is often defined as the correspondence in size, form, and arrangement of similar parts on the opposite sides of a point, line (axis), or plane. A figure that has line symmetry has two halves which coincide if folded along its line of symmetry, and these halves are congruent, it means, they are the same size and shape. Symmetrical objects show elements of symmetry, for example, a shape of a crystal may show rotation axes, a centre of symmetry, or mirror planes, imaginary planes that separate an object into halves. Radial symmetry in an object occurs when it can be rotated around the rotation axis and retain the same appearance as before rotating, repeating itself several times during a complete rotation. Symmetry exists not only in geometry but also in natural world and human works.

Scientists and artists see a purpose in symmetry investigations, for example, mathematicians, anthropologists, artists, designers, architects who conduct computer analysis of the facades, friezes, and some architectural details, as well as researchers in many fields of natural sciences, medicine, pharmacology, biology, geology, or chemistry. Many artists have created masterpieces this way. Artists used to transform patterns and repetitions to apply the unity or symmetry in their compositions (for example, by examining a Fibonacci sequence, prime numbers and magic squares, a golden section, or tessellation techniques). Mathematicians, computing scientists, and artists used to apply visual metaphors as a cognitive tool to visualise the world’s structure and our knowledge. The theme of symmetry can certainly be considered inspirational to create biologically inspired art, because symmetrical forms and shapes possess an aesthetic beauty and an order reflected by their geometry. We can appreciate these forms finding the importance of adaptations that animals develop as an answer to the conditions of life, examining mathematical order in natural forms, and re-creating it in our own artwork. With generative approach, artists draw from natural phenomena observed in biology and physics, and their creative process may evolve into a sequence of iterative solutions and modifications transforming the artwork.

However, developing computational methods which generate symmetrical patterns is still a challenge since it has to connect abstract mathematics with the noisy, imperfect, real-world; and few computational tools exist for dealing with real-world symmetries (Liu 2002). Applying evolutionary algorithms to produce symmetrical forms leaves the formulation of fitness functions, which generate and select symmetrical phenotypes, to be addressed. Lewis describes two strategies in evolutionary algorithms approach for generating and selecting symmetrical forms: “a common approach is to hope for properties like symmetry to gradually emerge by selecting for them. Another strategy is to build in symmetry functions which are sometimes activated and are appearing suddenly. However, this leads to a lack of control, as offspring resulting from slight mutations (i.e. small steps in the solution space) bear little resemblance to their ancestors” (Lewis 2008).

The next section explains the swarm intelligence algorithm which will be used in detecting symmetrical patterns.

4 Swarm intelligence

The swarm intelligence algorithm used in this work is Stochastic Diffusion Search (SDS) (Bishop 1989; al-Rifaie and Bishop 2013) which is a probabilistic approach for solving best-fit pattern recognition and matching problems. SDS, as a multi-agent population-based global search and optimisation algorithm, is a distributed mode of computation utilising interaction between simple agents. Its computational roots stem from Geoff Hinton’s interest 3D object classification and mapping. See Hinton (1981) for Hinton’s work and Bishop and Torr (2004) for the connection between Hinton mapping and SDS. SDS algorithm has been used in various fields including optimisation, generative arts and medical imaging (e.g. al-Rifaie et al. 2012a, b). SDS has a strong mathematical framework

Unlike many natured inspired search algorithms, SDS has a strong mathematical framework, which describes the behaviour of the algorithm by investigating its resource allocation (Nasuto 1999), convergence to global optimum (Nasuto and Bishop 1999), robustness and minimal convergence criteria (Myatt et al. 2004) and linear time complexity (Nasuto et al. 1998). The full mathematical model and proof of SDS convergence are elaborated in al-Rifaie and Bishop (2013).

4.1 SDS architecture

Similar to other swarm intelligence algorithms, SDS commences a search or optimisation by initialising its population. In any SDS search, each agent maintains a hypothesis, h, defining a possible problem solution. After initialisation, the two phases of SDS are followed (see Algorithm 1 for a high-level description of SDS):

  • Test phase

  • Diffusion phase

In the test phase, SDS checks whether the agent hypothesis is successful or not by performing a partial hypothesis evaluation and returning a domain-independent boolean value. Later in the iteration, contingent on the strategy employed, successful hypotheses diffuse across the population and in this way information on potentially good solutions spreads throughout the entire population of agents.

In other words, in the Test phase, each agent performs partial function evaluation, pFE, which is some function of the agent’s hypothesis, \(\hbox {pFE}=f(h)\), where f is the function and h is the hypothesis; and in the diffusion phase, each agent recruits another agent for interaction and potential communication of hypothesis.

figure a

4.2 Standard SDS and passive recruitment

In standard SDS, passive recruitment mode is employed. In this mode, if the agent is inactive, a second agent is randomly selected for diffusion; if the second agent is active, its hypothesis is communicated (diffused) to the inactive one. Otherwise there is no flow of information between agents; instead a completely new hypothesis is generated for the first inactive agent at random (see Algorithm 2). Therefore, recruitment is not the responsibility of the active agents. Higher rate of inactivity boosts exploration, whereas a lower rate biases the performance towards exploitation. Details of the test phase and the fitness function is described later in this paper.

figure b

4.3 Partial function evaluation

One of the concerns associated with many optimisation algorithms (e.g. Genetic Algorithm, Particle Swarm Optimisation and etc.) is the repetitive evaluation of a computationally expensive fitness function. In some applications, such as tracking a rapidly moving object or generation of CA patters, the repetitive function evaluation significantly increases the computational cost of the algorithm. Therefore, in addition to reducing the number of function evaluations, other measures can be used in an attempt to reduce the computations carried out during the evaluation of each possible solution, as part of the overall optimisation (or search) processes.

The commonly used benchmarks for evaluating the performance of swarm intelligence algorithms are typically small in terms of their objective functions computational costs (Digalakis and Margaritis 2002; Whitley et al. 1996), which is often not the case in real-world applications (examples of costly evaluation functions are seismic data interpretation, selection of sites for the transmission infrastructure of wireless communication networks and radio wave propagation calculations of one site, etc.).

Costly objective function evaluations have been investigated under different conditions (Jin 2005) and the following two broad approaches have been proposed to reduce the cost of function evaluations:

  • The first is to estimate the fitness by taking into account the fitness of the neighbouring elements, the former generations or the fitness of the same element through statistical techniques introduced in Branke et al. (2001).

  • In the second approach, the costly fitness function is substituted with a cheaper, approximate fitness function.

When agents are about to converge, the original fitness function can be used for evaluation to check the validity of the convergence (Jin 2005).

The approach that the standard SDS algorithm uses is similar to the second method. Many fitness functions are decomposable to components that can be evaluated separately. During the test phase of SDS, in partial function evaluation (pFE, which is some function of the agent’s hypothesis, \(\hbox {pFE}=f(h)\), where f is the function and h is the hypothesis), the evaluation of one or more of the components may provide partial information to guide the subsequent optimisation process.

In other words, instead of evaluating the hypothesis in its entirely, part of it, which is called micro-feature, is selected and evaluated accordingly. Therefore, during the test phase, only the randomly selected micro-features of the hypotheses are evaluated and the status of each agent is thus determined. Thus, if the micro-feature of each hypothesis consists of, say, \(\frac{1}{10}\) of the entire hypothesis, the computational expense for the evaluation process of each hypothesis would be \(\frac{9}{10}\) computationally cheaper.

Next, details of the process through which SDS performs its spatial-independent symmetry detection is presented.

5 Experiments and results

This section explains the design of the experiments conducted along with the results of applying SDS to identify partial or full symmetries on the cellular automata-generated patternsFootnote 1. The inputs to the system are sample patterns used as proof of principle to show the functionality of the method; afterwards, some real-world cellular automata-generated patterns are fed in the system to evaluate the overall performance of the algorithm in detecting the aforementioned types of symmetries.

In order to adopt SDS to identify symmetries, the following important considerations are taken into account (see Algorithm 3 for more details):

  • the search space comprises of the entire cells on the grid (see Fig. 7-left where the search space size is \(5 \times 5\))

  • SDS hypothesis is a cell index (x, y). For instance the coordinate \((x,y)=(2,2)\) could be the hypothesis and micro-featuresFootnote 2 can be selected by specifying the \(x_d\) and \(y_d\) distances from the hypothesis; for instance if the \((x_d,y_d)\) distance is (2, 0), this micro-features can be found at the following coordinates: \((x-x_d, y-y_d)\) and \((x+x_d, y+y_d)\); therefore, the coordinates of the micro-features in this example will be \((2-2, 2-0)\) and \((2+2, 2+0)\) resulting in (0, 2) and (4, 2). See Fig. 7-right.

  • the environment in cellular automata is torus, which means if moving downwards along the search space when we reach the last raw, the next row to be visited is the top row. The same is applicable when moving between columns (see Fig. 1 shows the 2D representation of the cellular automata and its real structure as torus).

figure c
Fig. 7
figure 7

Left: search space (\(5 \times 5\)); right: active hypothesis is shown in green; and the selected micro-features are highlighted in blue (colour figure online)

Full size image
Fig. 8
figure 8

Sample hypothesis set to be (3, 2); active hypotheses are shown in green and the inactive ones are displayed in red; the selected micro-features are highlighted in blue (colour figure online)

Full size image

The patterns in Fig. 8 show the hypothesis (3, 2) and the various possible micro-features, some of which resulting in the hypothesis’ status to be true while some others lead to the hypothesis’ status to be false. In other words, various micro-features are selected to test the symmetry of the pattern along various axes of symmetry. Figure 9 shows the four axes of symmetry in a fourfold symmetrical pattern on the centre of the pattern and Fig. 10 shows each of these axes separately, again on the centre of the pattern. The torus structure of cellular automata is demonstrated in the choice of some of the corresponding micro-features; see, for example, Fig. 8 top-right corner, where the micro-feature is chosen at \((-1,-1)\) distance. Thus the corresponding cell is chosen at (1, 1) distance from the hypothesis, which means moving out of the 2D canvas from the right border and entering again from the left.

Having considered the details above, the process through which SDS commences with the initialisation phase and then cycle through the two phases and test and diffusion is explained next.

5.1 Initialisation phase

During the initialisation phase each one of the agents in the population is assigned a hypothesis which is a random (x, y) coordinate from the search space. Additionally, the status of all agents are initially set to false.

5.2 Test phase

In the test phase, each agent, which is already allocated a hypothesis, picks a random \(x_d\) and \(y_d\) distances from the hypothesis cell as its micro-feature; the randomly selected micro-feature is then compared against its corresponding mirrored cells to check if the mirrored cell has the same value. If the values are the same, the status of the agent is set to true, otherwise false

5.3 Diffusion phase

The process in the diffusion phase is the same as the one detailed in the algorithm description: each inactive agent picks an agent randomly from the population; if the randomly selected agent is active, the inactive agent adopts the hypothesis of the active agent (i.e. the (x, y) coordinate), otherwise the inactive agent picks a random coordinate from the search space.

Fig. 9
figure 9

Four axes of symmetry in a fourfold symmetrical pattern

Full size image
Fig. 10
figure 10

Individual axes of symmetry

Full size image

After n number of iterations, agents converge on the (x, y) coordinates with the most symmetrical quality.

Fig. 11
figure 11

SDS agents convergence on the point of symmetry. Top: two input patterns; middle: SDS agents after \(n=10\) iterations; bottom: SDS agents after \(n=30\) iterations

Full size image
Fig. 12
figure 12

Passive recruitment mode

Full size image
Fig. 13
figure 13

Context-sensitive mechanism

Full size image

5.4 Experiments and discussion

One of the main features of SDS is partial function evaluation which here manifests itself in the following: each time comparing one cell on one side of the symmetrical point to its corresponding cell on the other side. Therefore, even when an agent is active, in the next iteration it picks another micro-feature and checks the point from “a different perspective” to ensure that the symmetry still holds. In other words, using this approach, the algorithm allocates its resources “wisely” and repeatedly tests the already maintained points of interest against any asymmetrical discovery. Therefore, the agents’ focus is guided towards the more promising area of the search space, where the algorithm identifies partial symmetry. The area with the identified partial symmetry is further investigated; the repeated exploration of the promising areas guarantees the agents’ convergence to the location of symmetry.

For the experiments reported in this work, the population size is empirically calculated using the following formula:

$$\begin{aligned} \mathrm{pSize} = \left\lceil \frac{w^2}{4} \right\rceil \end{aligned}$$
(11)

where pSize is the population size and w is the width of the search space. Using this setup, the agents land on fourth of the search space; therefore, for the search space introduced earlier, the population size will be set to \(\hbox {pSize} = \left\lceil \frac{5^2}{4}\right\rceil = 6\). Figure 11 shows two patterns which are processed by SDS algorithm and the results are shown after \(n = 10\) and \(n = 30\) iterationsFootnote 3. The figures in the last row show better convergence to the point of symmetry as they are allowed more SDS iterations. As illustrated in the figures, some agents became active on (x, y) coordinates which do not represent the full fourfold symmetry; these agents will eventually pick different micro-features in the next iterations and become inactive; consequently, when they are inactive, they need to choose random agents; given that the number of active agents on the centre of symmetry increases over time (thanks to the diffusion phase), it is likely that an active agent is chosen. This would lead to the inactive agents picking micro-features from the centre of symmetry in their next iterations and become/stay active. Note that in these experiments, alpha is used for the transparency of the agents’ colour (where \(\alpha = 200\)); therefore, as shown in the figures, the cell with the largest number of active agents can be distinguished from others.

There are occasions when more than one centre of symmetry exists, or there exist some partial symmetries in the image along with full centre of symmetry; in this case another flavour of the recruitment strategy is deployed which is called context-sensitive mechanism. This strategy frees up some of the agents who are active and share the same hypothesis and therefore allows the algorithm to constantly check for traces of symmetry in the input pattern.

In other words, the use of context-sensitive mechanism biases the search towards global exploration. Therefore, if an active agent randomly chooses another active agent that maintains the same hypothesis, the selecting agent is set inactive and adopts a random hypothesis. This mechanism frees up some of the resources in order to have a wider exploration throughout the search space as well as preventing cluster size from overgrowing while ensuring the formation of large clusters in case there exists a perfect match or good sub-optimal solutions (see Algorithm 4).

figure d

The next set of experiments use more complex patterns, generated by cellular automata techniques. Initially an experiment is run that utilises the passive recruitment mode without the introduced context-sensitive mechanism and later, the impact of context-sensitivity is discussed.

Fig. 14
figure 14

Passive recruitment mode: finding the absolute symmetry at iterations \(n = 100\) and 200

Full size image
Fig. 15
figure 15

Context-sensitive mechanism: finding partial symmetry at iterations \(n = 100\) and 200

Full size image

The graph in Fig. 12 illustrates the behaviour of the agents’ activities; this graph demonstrates that after the initialisation phase, the number of active and inactive agents are balanced; however, over time, and due to the presence of a centre of symmetry in the pattern, the number of active agents increases and the number of inactive agents decreases. Therefore, ultimately, once the absolute centre of symmetry (where symmetry holds irrespective of the micro-features chosen) is identified, the entire agent population becomes active and the number of inactive agents drops to zero.

In the next experiment, the graph in Fig. 13 illustrates the behaviour of SDS algorithm using the context-sensitive mechanism, where the populations are biased towards global exploration. In this graph, while the increase in active agents and the decrease in inactive agents are visible, it is evident that there are always agents which are released back from the centre of symmetry to the search space to explore the possibility of further symmetrical points. This feature is particularly useful in dynamic environments, and where there are more than one absolute point of symmetry. The figure shows many active (green) and inactive (red) agents throughout the search space. On the other hand, there are no roaming agents in Fig. 12 and all agents are drawn to the centre of symmetry.

The next experiment, which uses a more symmetrically complex CA-generated pattern, demonstrates the crucial difference when using SDS with or without the context-sensitive mechanism. As stated before context-sensitive mechanism reduces the greediness of the agents and allows the agents to explore the search space for any undetected symmetry, while the passive mechanism is greedy and once it finds the absolute point of symmetry (where symmetry holds no matter which micro-feature is picked), it gradually pulls all the agents and stops them from locating partial symmetries in the canvas.

The new input to be used in this experiment has two identically CA grown patterns one on the top-left quarter and another on the bottom-left quarter. When running the SDS algorithm, it becomes clear that the passive recruitment strategy (see Fig. 14) initially locates two points of symmetry (when \(n = 100\) iterations) and later (when \(n = 200\) iterations) all agents are drawn to the absolute point of symmetry (note that the search spaces in cellular automata are torus).

However, by using the context-sensitive approach, the largest partial symmetries are also identified and highlighted (see Fig. 15). The graphs at the bottom of Figs. 14 and 15 show clearly the behaviour of the agents in both modes.

As displayed in the graph of Fig. 15, while the number of active and inactive agents are distinguishably far from one another, yet it is shown that the number of active agents does not reach the maximum possibleFootnote 4 and the number of inactive agents does not drop to zero. This mechanism insures the identification of other symmetrical points in the input. Therefore, depending on the functionalities needed, either of these approaches could be used.

Whenever there is a full-match, SDS has been proven mathematically to converge (Nasuto and Bishop 1999) to the optimum solution. This proof is strongly based on the presence of the partial function evaluation aspect of SDS where a micro-feature is selected and evaluated individually of other micro-features. This makes the algorithm robust in dealing with false positive or false negative.

Another observation to be expanded in the future work is the direct proportionality of the agents’ activity to the ‘strength’ of the symmetry. Therefore, while context-sensitive mechanism finds partial symmetries, it is able to rank the various clusters formed over the pattern.

6 Conclusion

CA provide perspective and powerful tools in generating graphical contents. The multi-state CA rule space is a vast set of possible rules which can generate interesting patterns with high aesthetic qualities. The interaction of CA rules at local level generates emergent global behaviour that can sometimes demonstrate attractive complexity. Some characteristics of CA, such as the regularity and complexity of the rules that are employed locally, suggest that they could be well suited to generate artificially generated aesthetic images.

This paper demonstrates the capability of a swarm intelligence algorithm—Stochastic Diffusion Search—in detecting absolute symmetries (when present) and the centre of partial symmetrical patterns within the input image. Evaluating the symmetry of cellular automata-generated patterns is often a difficult task partly due the large size of the search space, and partly due to the constantly changing, dynamic environment in which the cellular automata patterns are generated. These factors contribute to making the detection of symmetrical patterns computationally expensive. One of the main features of Stochastic Diffusion Search is partial function evaluation which is particularly useful when dealing with large problems with high dimensions and costly evaluation function (e.g. in this case, the expensive computational cost of detecting symmetry in cellular automata-generated patterns). The performance of this algorithm is explained in the paper and the results are accordingly demonstrated.

Following the introduction of this novel technique, among the future research topics are: conducting a comparison with other evolutionary and non-evolutionary techniques; computing the correlation between the size of the search space and the computational complexity of the process as well as ranking the quality of the symmetries detected.