Swarmic approach for symmetry detection of cellular automata behaviour

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.

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.

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\)).

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).

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

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). 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\).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).

The total number of possible state transition functions as the size of rule space \( \varPhi \) can be obtained fromwhere |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. where whereTable 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.

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.

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).

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 patterns¹. 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 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.

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.