Evolutionary Image Transition Using Random Walks

Abstract

We present a study demonstrating how random walk algorithms can be used for evolutionary image transition. We design different mutation operators based on uniform and biased random walks and study how their combination with a baseline mutation operator can lead to interesting image transition processes in terms of visual effects and artistic features. Using feature-based analysis we investigate the evolutionary image transition behaviour with respect to different features and evaluate the images constructed during the image transition process.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Evolutionary algorithms (EAs) have been widely and successfully used in the areas of music and art [1,2,3]. In this application area the primary aim is to evolve artistic and creative outputs through an evolutionary process [4,5,6,7]. The use of evolutionary algorithms for the generation of art has attracted strong research interest. Different representations have been used to create works of greater complexity in 2D and 3D [8,9,10], and in image animation [11,12,13]. The great majority of this work relates to the use of evolution to produce a final artistic product in the form of a picture, sculpture or animation.

Another application of evolutionary algorithms to art is the creation of image transitions. Earlier work by Sims [11] described methods for cross-dissolving of images by changes in an expression genotype. Banzhaf [14] used interactive evolution to help determine parameters for image morphing. Furthermore, Karungaru [15] used an evolutionary algorithm to automatically identify features for morphing faces. More recently, deep neural networks have recently been used to create artistic images through the transfer of artistic style from one image to another [16].

Neumann et al. [17] described an image transition process where the key idea is to use the evolutionary process itself in an artistic way. The focus of our paper is to study how random walk algorithms can be used in the evolutionary image transition process defined in [17] as mutation operators. We consider the well-studied (1+1) EA, popular random walk algorithms and provide new approach to evolutionary art by using theoretical approaches for evolutionary image transition.

The transition process consists of evolving a given starting image S into a given target image T by random decisions. Considering an error function which assigns to a given current image X the number of pixels where it agrees with T and maximizes this function boils down to the classical ONEMAX problem for which numerous theoretical results on the runtime behaviour of evolutionary algorithms are available [18,19,20]. An important topic related to the theory of evolutionary algorithms are random walks [21, 22]. We consider random walks on images where each time the walk visits a pixel its value is set to the value of the given target image. By biasing the random walk towards pixels that are similar to the current pixel we can study the effect of such biases which might be more interesting from an artistic perspective. After observing these two basic random processes for image transition, we study how they can be combined to give the evolutionary process additional interesting new properties. We study the effect of running random walks for short periods of time as part of a mutation operator in a (1+1) EA. Furthermore, we consider the effect of combining them with the asymmetric mutation operator for evolutionary image transition introduced in [17]. Our results show that the area of evolutionary image transition based on random walks provides a rich source of artistic possibilities for creating video art. All our approaches are pixel-based and creating videos based on the evolutionary processes show frames corresponding to the images created every few hundred generations¹.

After introducing these different approaches to evolutionary image transition based on random walks, we study their behaviour with respect to different aesthetic features. Feature-based analysis of heuristic search methods has gained increasing interest in recent years [23,24,25]. In other application areas feature-based analysis is an important method to increase the theoretical understanding algorithm performance and in particularly useful for algorithm selection and configuration [26, 27]. For evolutionary image transition, we study how artistic features behave during the transition process. This allows the measurement of the evolutionary image transition process in a quantitative way and provides a basis to compare our different approaches with respect to artistic measures.

Fig. 1.

Starting image X (Yellow-Red-Blue, 1925 by Wassily Kandinsky) and target image T (Soft Hard, 1927 by Wassily Kandinsky) (Color figure online)

The outline of the paper is as follows. In Sect. 2, we introduce the evolutionary transition process. In Sect. 3, we study how variants of random walks can be used for the image transition process. We examine the use of random walks as part of mutation operators and study their combinations with asymmetric mutation during the evolutionary process in Sect. 4. In Sect. 5, we analyse the different approaches for evolutionary image transition with respect to aesthetic features. Finally, we finish with some concluding remarks.

2 Evolutionary Image Transition

We consider the evolutionary image transition process introduced in [17]. It transforms a given image $S=(S_{ij})$ of size $m \times n$ into a given target image $T= (T_{ij})$ of size $m \times n$. This is done by producing images X for which $X_{ij} \in \{S_{ij}, T_{ij} \}$ holds. Given a starting image $S=(S_{ij})$ a target image $T=(T_{ij})$, and a current image $X= (X_{ij})$, we say that pixel $X_{ij}$ is in state s if $X_{ij} = S_{ij}$, and $X_{ij}$ is in state t if $X_{ij}=T_{ij}$. Our goal is to study different ways of using random walk algorithms for evolutionary image transition.

Throughout this paper, we assume that $S_{ij} \not = T_{ij}$ as pixels with $S_{ij} = T_{ij}$ can not change values and therefore do not have to be considered in the evolutionary process. To illustrate the effect of the different methods presented in this paper, we consider the Yellow-Red-Blue, 1925 by Wassily Kandinsky as the starting image and the T Soft Hard, 1927 by Wassily Kandinsky as the target image (see Fig. 1). In principle, this process can be carried out with any starting and target image. Using artistic images for this has the advantage that artistic properties of images are transformed during the evolutionary image transition process. We will later on study how the different operators used in the algorithms influence artistic appearance in terms of different artistic features.

We use the fitness function for evolutionary image transition used in [17] and measure the fitness of an image X as the number of pixels where X and T agree. This fitness function is equivalent to the OneMax problem when interpreting the pixels of S as 0’s and the pixels of T as 1’s. Hence, the fitness of an image X with respect to the target image T is given by

$$ f(X,T) = |\{X_{ij} \in X \mid X_{ij}=T_{ij}\}|. $$

We consider simple variants of the classical (1+1) EA in the context of image transition. The algorithm is using mutation only and accepts an offspring if it is at least as good as its parent according to the fitness function. The approach is given in Algorithm 1. Using this algorithm has the advantage that parents and offspring do not differ too much from the number of pixels. This ensures a smooth process for transitioning the starting image into the target. Furthermore, we can interpret each step of the random walks flipping a visited pixel to the target outlined in Sect. 3 as a mutation step which according to the fitness function is always accepted.

Fig. 2.

Image Transition using asymmetric mutation with $c_s=100$ and $c_t=50$

As the baseline mutation operator we consider the asymmetric mutation operator which has been studied in the area of runtime analysis for special linear functions [18] as well as the minimum spanning tree problems [28]. Using this mutation operator instead of standard bit mutations for OneMax problems has the advantage that it does not suffer from the coupon collectors effect at the end of the transition process.

We use the generalization of this asymmetric mutation operator already proposed in [17] and shown in Algorithm 2. Let $|X|_T$ be the number of pixels where X and T agree. Similarly, let $|X|_S$ be the number of pixels where X and S agree. Each pixel is starting state s is flipped with probability $c_s/(2|X|_S)$ and each pixel in target state t is flipped with probability $c_t/(2|X|_T)$. The special case of $c_s=c_t=1$ has been mathematically analyzed with respect to the runtime behaviour on OneMax and other pseudo-Boolean functions.

We set $c_s=100$ and $c_t=50$ as in [17]. This allows both a decent speed for the image transition process and enough exchanges of pixels for an interesting evolutionary process. We should mention that obtaining the last pixels of the target image may take a long time compared to the other progress steps when using large values of $c_t$. However, for image transition, this only effects steps when there are at most $c_t/2$ source pixels remaining in the image. From a practical perspective, this means that the evolutionary process has almost converged towards the target image and setting the remaining missing target pixels to their target values provides an easy solution.

All experimental results for evolutionary image transition in this paper are shown for the process of moving from the starting image to the target image given in Fig. 1 where the images are of size $200 \times 200$ pixels. The algorithms have been implemented in Matlab. In order to visualize the process, we show the images obtained when the evolutionary process reaches 12.5%, 37.5%, 62.5% and 87.5% pixels of target image for the first time. We should mention that all processes except the use of the biased random walk are independent of the starting and target image which implies that the use of other starting and target images would show the same effects in terms of the way that target pixels are displayed during the transition process.

In Fig. 2 we show the experimental results of the asymmetric mutation approach as the baseline. On the first image from left we can see the starting image S with lightly stippling dots in randomly chosen areas of the target image T. Consequently the area of the yellow dimensional abstract face disappears and black abstract figure appears. Meanwhile the background has adopted a dot pattern, where a nuance of dark and light develops steadily. In the last image we barely see the starting image S and the target image T appearing permanently with the background becoming darker blue ton, whereby the stippling effect shown in the middle two frames decreases. The most valuable image in terms of aesthetic and evolutionary creativity emerge at the picture at 62,5% of the evolutionary processes. We can see in this third picture elements of both images compounded with the very special effect that imitate an artistic painting technique.

3 Random Walks for Image Transition

Our evolutionary algorithms for image transition build on random walk algorithms and use them later on as part of a mutation step. We investigate the use of random walk algorithms for image transition which move, at each step, from a current pixel $X_{ij}$ to one pixel in its neighbourhood.

Fig. 3.

Image transition for uniform random walk (top) and biased random walk (bottom) (Color figure online)

We define the neighbourhood $N(X_{ij})$ of $X_{ij}$ as

$$ N(X_{ij}) = \{ X_{(i-1)j}, X_{(i+1)j}, X_{i(j-1)} X_{i(j+1)} \} $$

where we work modulo the dimensions of the image in the case that the values leave the pixel ranges, $i \in \{1, \ldots , m\}$, $j \in \{1, \ldots , n\}$. This implies that from a current pixel, we can move up, down, left, or right. Furthermore, we wrap around when exceeding the boundary of the image.

The classical random walk chooses an element $X_{kl} \in N(X_{ij})$ uniformly at random. We call this the uniform random walk in the following. The cover time of the uniform random walk on a $n \times n$ torus is upper bounded by $4n^2 (\log n)^2/\pi$ [22] which implies that the expected number of steps of the uniform random walk until the target image is obtained (assuming $m=n$) is upper bounded by $4n^2 (\log n)^2/ \pi ))$.

We also consider a biased random walk where the probability of choosing the element $X_{kl}$ is dependent on the difference in RGB-values for $T_{ij}$ and $T_{kl}$. Weighted random walks have been used in a similar way in the context of image segmentation [29]. We denote by $T_{ij}^r$, $1 \le r \le 3$, the rth RGB value of $T_{ij}$ and define

$$ \gamma (X_{kl}) = \max \left\{ \sum _{r=1}^3 |T_{kl}^r - T_{ij}^r|,1 \right\} $$

In our random walk, we want to prefer $X_{kl}$ if $\gamma (X_{kl})$ is small compared to the other elements in $N(X_{ij})$. In order to compute the probability of moving to a new neighbour we consider $(1/ \gamma ( X_{kl})) \in [0,1]$ and prefer elements in $N(X_{ij})$ where this value is large.

In the biased random walk, the probability of moving from $X_{ij}$ to an element $X_{kl} \in N(X_{ij})$ is given by

$$\begin{aligned} p(X_{kl})= & {} \frac{(1/\gamma (X_{kl}))}{\sum _{X_{st} \in N(X_{ij})} (1/\gamma (X_{st}))}.\\ \end{aligned}$$

The biased random walk is dependent on the target image when carrying out mutation or random walk steps and the importance of moving to a pixel with similar color. Introducing the bias in terms of pixels that are similar, the bias can take the evolutionary image transition process to take exponentially long as the walk might encounter effects similar to the gambler’s ruin process [30]. For our combined approaches described in the next section, we use the random walks as mutation components which ensures that the evolutionary image transition is carried out efficiently. We will use the biased random walk for evolutionary image transition in Sect. 4.

In Fig. 3 we show the experimental results of the uniform random walk and biased random walk. At the beginning, we can observe the image with the characteristic random walk pathway appearing as a patch in the starting image S. Through the transition process, the clearly recognisable patches on the target image T emerge. In the advanced stages the darker patches from the background of the target image dominate. The effect in animation is that the source image is scratched away in a random fashion to reveal an underlying target image.

The four images of the biased random walk are clearly different to the images of the uniform random walk. During the course of the transition, the difference becomes more prominent, especially in the background where at 87.5% pixels of the target image there is nearly an absolute transition to the target image T. In strong contrast, the darker abstract figure of the images stay nearly untouched, so that we see a layer of the yellow face in starting image S in the centre of the abstract black figure in target image T. In this image the figure itself is also very incomplete with much of the source picture showing through. These effects arise from biased probabilities in the random walk which makes it difficult for the walk to penetrate areas of high contrast to the current pixel location.

4 Combined Approaches

The asymmetric mutation operator and the random walk algorithms have quite different behaviour when applied to image transition. We now study the effect of combining the approaches for evolutionary image transition into order to obtain a more artistic evolutionary process.

4.1 Random Walk Mutation

Firstly, we explore the use of random walks as mutation operators and call this a random walk mutation.

Fig. 4.

Image transition for EA-UniformWalk (top) and EA-BiasedWalk (bottom) (Color figure online)

The uniform random walk mutation selects the position of a pixel $X_{ij}$ uniformly at random and runs the uniform random walk for $t_{\max }$ steps (iterations of the while-loop). We call the resulting algorithm EA-UniformWalk. Similarly, the biased random walk mutation selects the position of a pixel $X_{ij}$ uniformly at random and runs the biased random walk for $t_{\max }$ steps. This algorithm is called EA-BiasedWalk. For our experiments, we set $t_{\max }=100$.

Figure 4 shows the results of the experiments for EA-UniformWalk and EA-BiasedWalk. The transitions produced were significantly different from the previous ones. In both experiments we can see the target image emerging through a series of small patches at first, then steadily changing through a more chaotic phase where elements of the source and target image appear with roughly equal frequency. On the last image of each experiment we can see most details of the target image.

Fig. 5.

Image transition for EA-AsymUniformWalk (top) and EA-AsymBiasedWalk (bottom)

The images from EA-BiasedWalk appear similar to those in EA-UniformWalk in the beginning but differences emerge at the final stages of transition where, in EA-BiasedWalk, elements of the source image still show through in areas of high contrast in the target image, which the biased random walk has difficulty traversing. This mirrors, at a more local scale the effects of bias in the earlier random walk experiments. At a global scale it can be seen that the blue background, which is a low contrast area, is slightly more complete in the final frame of EA-BiasedWalk than the same frame in EA-UniformWalk.

4.2 Combination of Asymmetric and Random Walk Mutation

Furthermore, we explore the combination of the asymmetric mutation operator and random walk mutation. Here, we run the asymmetric mutation operator as described in Algorithm 2 and a random walk mutation every $\tau$ generations. We explore two combinations, namely the combination of the asymmetric mutation operator with the uniform random walk mutation (leading to the algorithm EA-AsymUniformWalk) as well as the combination of the asymmetric mutation operator with the biased random walk mutation (leading to Algorithm EA-AsymBiasedWalk). We set $\tau =1$ and $t_{\max }=2000$ which means that the process is alternating between asymmetric mutation and random walk mutation where each random walk mutation carries out 2000 steps.

In Fig. 5, we show the results of EA-AsymUniformWalk and EA-AsymBiasedWalk. From a visual perspective both experiments combine the stippled effect of the asymmetric mutation with the patches of the random walk. In EA-AsymBiasedWalk there is a lower tendency for patches generated by random walks to deviate into areas of high contrast. As the experiment progresses, the pixel transitions caused by the asymmetric mutation have a tendency to degrade contrast barriers.

However, even in the final frames there is clearly more background from the target image in EA-AsymBiasedWalk than in EA-AsymUniformWalk. Moreover, there are more remaining patches of the source image near the edges of the base of the abstract figure, creating interesting effects.

5 Feature-Based Analysis

We now analyze the different introduced approaches for evolutionary image transition with respect to some features that measure aesthetic behaviour. Our goal is twofold. First, we analyze how the aesthetic feature values change during the process of transition. Furthermore, we compare the different approaches against each other and show where they differ with respect to the examined features when used for evolutionary image transition. For our investigations, we examine the starting and target image of Fig. 1, the transition of a black starting image into a white target image, and the transition of the starting image Color1 into the target image Color2 as shown in Fig. 6. Taking the last two pairs of images allows us to get additional systematic insights into the process of evolutionary image transition. Note that the images of Fig. 6 are only swapping the colored squares.

Fig. 6.

Starting image S (Color1) and target image T (Color2) (Color figure online)

The set of features we use are, in order of appearance, Benford’s Law [31], Global Contrast Factor [32], Mean Hue, and Colorfulness [33]. We describe each of them in the following.

The Benford’s Law feature ($\text{ Ben }$) is a measure of naturalness in an image X. Jolion [31] observed that the sorted histogram of luminosities in natural images followed the shape of Benford’s Law distribution of first digits. Here we use the encoding of the Benford’s Law feature based on the one used by den Heijer [34].

To calculate $\text{ Ben }(X)$ we first calculate a nine-bin histogram $H_X$ of the luminosities of X. The bins of $H_X$ are then sorted by frequency and scaled to sum to 1.0. We define

$$\text{ Ben }(X)=1- d_{total}/d_{max} $$

where

$$d_{total}=\sum _{i=1}^9 H_X(i)- H_{benford}(i)$$

and $H_{benford}$ is a 9-bin histogram, encoding Benford’s Law distribution, with the bin frequencies 0.301, 0.176, 0.125, 0.097, 0.079, 0.067, 0.058, 0.051, 0.046. The value

$$d_{max}=(1-H_{benford}(1))+\sum _{i=2}^9 H_{benford}(i)$$

is the maximum possible value for $d_{total}$ which is the largest possible deviation of $H_X$ from $H_{benford}$.

Global Contrast Factor, GCF is a measure of mean contrast between neighbouring pixels at different image resolutions. To calculate $\text{ GCF }(X)$ we calculate the local contrast at each pixel at a given resolution r: $\text{ lc }_r(X_{ij})=\sum _{X_{kl} \in N(X_{ij})} |\text{ lum }(X_{kl}) -\text{ lum }(X_{ij})|$ where $\text{ lum }(P)$ is the perceptual luminosity of pixel P and $N(X_{ij})$ are the four neighbouring pixels of $X_{ij}$ at resolution r. The mean local contrast at the current resolution is defined $C_r=(\sum _{i=1}^m \sum _{j=1}^n \text{ lc }_r(X_{ij}))/(mn)$. From these local contrasts, $\text{ GCF }$ is calculated as $GCF = \sum _{r=1}^9 w_r \cdot C_r.$

The pixel resolutions correspond to different superpixel sizes of 1, 2, 4, 8, 16, 25, 50, 100, and 200. Each superpixel is set to the average luminosity of the pixel’s it contains. The $w_r$ are empirically derived weights of resolutions from [32] giving highest weight to moderate resolutions.

The Mean Hue ($\text{ Hue }$) of an image X is

$$\text{ Hue }(X) = \left( \sum _{i=1}^m \sum _{j=1}^n \text{ h }(X_{ij})\right) /(m\times n)$$

where $\text{ h }(X_{ij})$ is the hue value for pixel $X_{ij}$ in the range [0, 1]. The function $\text{ Hue }$ measures where on average the image X sits on the color spectrum. Because the color spectrum is a circular construct one color, cyan in our case, is mapped to both 1 and 0.

Colorfulness ($\text{ Color }$) is a measure of the perceived color of an image. We use Hasler’s simplified metric for calculating colorfulness [33]. This measure quantifies spreads and intensities of opponent colors by calculating for the RGB values in each pixel $X_{ij}$ the red-green difference: $\text{ rg }_{ij} =|R_{ij}-G_{ij}|$, and the yellow-blue difference: $\text{ yb }_{ij}=|(R_{ij}+G_{ij})/2-B_{ij}|$. The means: $\mu _{rg}$, $\mu _{yb}$ and standard-deviations: $\sigma _{rg}$, $\sigma _{yb}$ for these differences are then combined to form a weighted magnitude estimate for colorfulness for the whole image:

$$ \text{ Color }(X)=\sqrt{\sigma _{rg}^2 + \sigma _{yb}^2} + 0.3 \sqrt{\mu _{rg}^2 + \mu _{yb}^2} $$

Fig. 7.

Features during transition for images for Asymmmetric Mutation (), Uniform Random Walk (), Biased Random Walk (), EA-UniformWalk (), EA-BiasedWalk (), EA-AsymUniformWalk () and EA-AsymBiasedWalk () for images from Fig. 1 (left), Black-White (middle), Fig. 6 (right). Generation number is shown on the x-axis and features values on the y-axis. (Color figure online)

Figure 7 shows how the features evolve over time during the image transition process. The first column refers to the transition process of the starting and target image given in Fig. 1. The second column shows the transition of a complete black image starting image to a complete white target image, and the third column shows the transition of the color starting image to the color target image of Fig. 6. Each figure shows the results of 10 runs for each algorithm that we have considered for evolutionary image transition.

Considering the results for the images of Fig. 1 (left column), it can be observed that the feature values for Benford’s Law reduce at the first half of the transition process and increase afterwards. Furthermore, the value for the target image is quite low, but the evolutionary image transition process produces images where the value for Benford’s Law is significantly higher than the one for the starting and the target image in the last third of the image transition process. In terms of global contrast, it can also be observed that the transition process creates images of higher feature value than the ones of the starting and target image. All considered algorithms follow the same pattern for these two features, but it can be observed that the pure random walk algorithms of Sect. 3 overall achieve higher values for Benford’s Law and the combined approaches are able to obtain a trajectory of higher values for Global Contrast Factor.

Considering the features Mean Hue and Colorfulness, the features values are following a more direct trajectory from the value of the starting image to the one of the target. For Hue, this trajectory is also very concentrated around the linear function connecting these two values where as for Colorfulness a strong deviation, especially for the pure random walk algorithms of Sect. 3, can be observed.

The transition process for the images of Fig. 6 carries out a process where the features values of the starting and target image are of the same value. Again it can be observed that the algorithms obtain higher values for Benford’s Law and Global Contrast Factor during the transition for most of the runs. An exception is the biased random walk algorithm of Sect. 3 that sometimes produces lower values for these two figures during the transition. Mean Hue and Colorfulness again exhibit a more direct trajectory between the starting and target feature value with the random walk algorithms showing a stronger fluctuation and in particular lower values with respect to Colorfulness.

Considering the transition for Black to White images, it can be observed that Benford’s Law and Global Contrast Factor increase during the transition process. The concentrated behaviour for Benford’s Law is due to the calculation of this feature as the feature value is fully determined by the number of black and white pixel. Furthermore, there are no changes during the transition process for Mean Hue and Colorfulness.

6 Conclusions and Future Work

Evolutionary image transition uses the run of an evolutionary algorithm to transfer a starting image into a target image. In this paper, we have investigated how random walk algorithms can be used in the evolutionary image transition process. We have shown that mutation operators using different ways of incorporating uniform and biased random walks lead to different effects during the transition process. Furthermore, we have studied the impact of the different approaches with respect to different artistic features and observed that the process creates images which significantly differ from the starting and target image with respect to these features.

All our investigations are based on a fitness function that is equivalent to the well-known OneMax problem. For future research it would be interesting to study more complex fitness functions and their impact on the artistic behaviour of evolutionary image transition.