Stochastic Diffusion Search: Finding Symmetry

Stochastic Diffusion Search (SDS) is a multi-agent optimisation algorithm formed of two steps, testing and diffusion . The test phase calculates an individual’s objective value, and the diffusion phase controls decentralised communication between agents. The standard SDS algorithm comprises a population of agents with each agent’s features initialised randomly within a search space. These features serve as the agent’s hypothesis. The test phase calculates whether their hypothesis is correct or incorrect and sets each individual’s status to active or inactive based upon said hypothesis. The diffusion phase then governs communication between active and inactive agents. If an agent is inactive, it will select another agent randomly. If this selected agent is active, then the original agent will adopt it’s hypothesis as their own. However, if this chosen agent is inactive then the agent will randomise their hypothesis once more to continue exploring the search space. Many variations of the algorithm exist to adapt to different problem spaces by altering properties such as the recruitment strategy and context mechanism used.

After this weeks lab, I set about finding the vertical axis of symmetry in simple images using SDS. I created a basic program in Processing that generated symmetrical images using random walkers to test the algorithm.

Examples of symmetry generated using random walkers.

In this experiment, each agent is initialised with a random x and y coordinate in the image to serve as it’s hypothesis. Upon the test phase, the agent will check it’s x “neighbourhood”. The neighbourhood is the number of pixels that each agent will check horizontally to the left and right of itself. In the example above, the neighbourhood size is set to 100. The agent will check if the pixel n steps away from it on the left matches the pixel n steps away from it on the right. Each agent performs a count of how many of these corresponding pixels are equal in colour value and if this number is equal to the neighbourhood size, then the agent’s status will update to active. Once active, the agent will draw a vertical line at it’s successful x coordinate to highlight the symmetry axis.

Finding vertical axis of symmetry where neighbourhood size is 100.

This implementation utilises passive recruitment in that inactive agent’s are responsible for initialising one-to-one communication with a randomly picked agent. If this communication is with an active agent, the agent will move to the same location as said active agent. If the communication is with an inactive agent, then the agent will generate a random hypothesis again. In this application, once one agent has found a solution then the communication process leads to a very fast convergence over the global line of symmetry. Due to the stochasticity of the test phase however, there is no guarantee on how many iterations it will take for the population to find this solution.

Introducing a context sensitive mechanism using an active recruitment strategy could aid in finding multiple vertical axes of symmetry. By prompting active agents to randomise their hypothesis if they communicate with an active agent with an equal hypothesis, agents are then provoked to explore further areas in the search space even when a solution has been found.

The size of the neighbourhood makes a huge impact on symmetrical solutions found. When using a much smaller neighbourhood size, agents find many more local examples of symmetry. Although in that small area the agents may find an instance of symmetry, it does not correspond to our perception of symmetry when we view the image as a whole.

Finding vertical axis of symmetry where neighbourhood size is 30.

When generating the symmetry, large areas of the background remained unfilled. The agents would define these spaces as symmetrical as the neighbourhood to the left and right contain purely black pixels and so both sides are identical. This required implementing a check for this scenario where a counter was created to increment when a pixel the colour of the background was found. If this counter returned the size of the neighbourhood overall, then this agent’s status would not be set to active to avoid false solutions.

Carrying out this implementation illuminated how difficult highlighting symmetry would be in an even slightly more complex setting. In my own generation, the pixels have not been manipulated by any compression and so the number of different colour values are six. In other images, compression creates artefacts and photographs themselves contain huge variations in perceptually identical pixels. My method of simply checking that the left area of the agent equals the right area is too simplistic to identify more complex models of symmetry. To combat this, perhaps allowing variation in what qualifies as an exact match may help. By averaging an agent’s local neighbourhood for dominant colour values, it can determine which pixel quality to allow variance in in it’s neighbourhood check.

Next I will focus on locating n-fold rotational symmetry and experiment with more complex images using SDS.