Natural Computing Project Proposal

The first problem I wanted to focus on in my nature-inspired metaheuristics project was circle packing in a circle, which aims to fit N unit circles within a larger circle as tightly as possible. It seems that just 25 cases for N have solutions known that don’t leave any circles loose (moveable without overlap). From what I found N = 91 is the largest. ^[?]

^{Above: Set of optimal circle packings with loose circles coloured pink (source)}

Although nature-inspired algorithms may have a chance at finding more of these ‘maximum density’ solutions, I think any attempt I make would be ineffective; packomania has archived optimal solutions from N = 1 to 2600 and beyond.

Explaining the rare occurance of these perfect circle packings is out of this project’s scope, and may even already be known (?), so instead this project takes inspiration from another interesting application of algorithms…

Image Approximation by Particle Swarm Optimisation

Background

Digital images go through data compression to make storing and sharing them more practical. The intermediate data in the compression process can be a set of points, illustrated in the image below, that resemble the original image when isolated and graphed.^[1] Patterns in this form are called ‘stippling’ patterns and are found in natural,^[2] academic and artistic contexts.

^{Above: Stippling using Voronoi technique (source)}

Different computational stippling techniques such as weighted centroidal Voronoi tesselation (CVT), ordered dithering and random probabilistic distribution are known to generate “dramatically” different patterns from the same images.^[3][4]

Problem

The generalised aim of this project is to experiment with how distinctly swarm intelligence can (be used in order to) approximate still or moving images.

Approach to Solution

Particle swarm optimisation (PSO) will be used for stippling image approximations. In the implementation:

• The search-space will be a two-dimensional array (e.g. 128x128 photo)
• The particles will refer to 2D positions corresponding to the image
• The solution will be the population of particles that most distinctly expresses the image (visual perception is quite subjective but metaheuristics like PSO don’t infer a global optimal solution either way)
• The fitness function will get particle’s underlying brightnesses in the most simple case, and can be extended to derive higher-level filters such as the standard deviation of neighbouring pixels’ RGB/HSB values in optimisation

Although PSO was first intended to simulate social behaviour in bird flocks and fish schools,^[5] it has properties that should be valuable in the problem of image approximation and stippling. Special consideration will be given to PSO’s inclusion of:

• Separation which will limit over-exploitation (many particles converged on a single optima is ineffective as they’d appear as one point in stippling)
• Alignment which will limit noise by reducing lone individual exploration (photos may have noise that we don’t want to pick up)
• Learning factors which will bias particles to move towards their personal best position and the global best position (swarms should be numerous instead of being unified around one “best” position)

A last benefit to PSO is that it doesn’t involve stochasticity after initialising the particles. On one hand this implies less exploration, which is needed to find the fittest regions. On the other hand it should make watching the particle interactions easier to understand, and enable the “bottom-up” strategy to engineer the desired emergent behaviour for approximating images by tuning particles based on observation.

Methods of Final Evaluation

The most objective way to evaluate image resemblance would be to compress and decompress images using their stippling approximations, which is far out the scope of this project. Many qualitative methods will be used however, revolving around side-by-side visual comparisons of algorithmic results with their corresponding source images. These graphic demonstrations will include:

• Comparisons of different PSO configurations on the same images (resemblance)
• Comparisons of the same PSO configurations on different images (robustness)
• Comparisons of results from other stippling algorithms (cross-comparison)

Stippling will be evaluated temporally (in animated format) to compare solution’s emergence over time.

Results will be post-processed to optimise the subjective results, such as by solving and graphing the travelling salesman problem which adds the effect of segmentation:

^{Above: Travelling salesman problem solved over stippling (source)}

Pattern recognition varies between people, so an accurate evaluation will come from collecting multiple people’s responses to a questionnaire on the visual results. The quantitative answers to questions on resemblance (etc) will be averaged. Blind examples (presenting stippling images without their corresponding source) will be included in the questionnaire to minimise issues like confirmation bias from effecting the results.

[1] Centroidal Voronoi Tessellations: Applications and Algorithms

[2] Stippling pattern on lily flower

[3] TSP Art

[4] The Travelling Artist Problem

[5] Particle Swarm Optimisation

For Natural Computing (IS53052A)