# Voronoi image approximation

## Image approximation.

After coming across some research using voronoi diagrams produced by a genetic algorithm to approximate an image, I thought it may be of some practical use in working with animation - a media form that would appear ideally suited to such representation. I have produced a program which, when given a bitmap image, will eventually produce a set of points for a voronoi diagram that approximates it. The approach used is simpler than a true genetic algorithm, nothing more than a very cpu-intensive hill-climbing, but sufficient to produce a quite impressive result.

These representations can function as a form of lossy compression, but the quality leaves much to be desired. The image demonstrated here can, when gziped, fit in 2.8K. 

=> images/voropony.png A demonstration of image approximation. This cartoon was very popular when I did the testing.

## Image inpainting/disocclusion/interpolation

A simple modification to avoid masked-off areas in the fitness calculation and the algorithm turns into a way to fill in gaps in an image. This was the real purpose: To remove channel logos.

It works. Sort of. It's non-deterministic, so the result is inconsistent, but it has potential. The results vary widely even for the same input.

=> images/vorony_interpolate.png An image with occlusions, and the algorithm's guess at what fills the gap.

Using it for animation, the computational effort can be re-used between frames. Doing this avoids the flickering image problem, and the resulting fill in is, if far from perfect, comparable to other tools for the same purpose. This experiment was done long before deep learning image generation was available. While an interesting idea though, it's hard to make this approach practical: It is just too unpredictable, and computationally expensive in this un-optimised prototype form.

Though this was back when the Core 2 Quad processor was new. Perhaps it would be more practical today. Should I ever find myself needing to remove channel logos from some old cartoon that cannot be sourced undamaged, I may have to revive this abandoned project.

=> images/before.png Animation test, before.
=> images/after.png Animation test, after.