Voronoi representation compared to original image. Test image chosen as I judged the distribution of detail would render it suited to voronoi 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.

Voronoi approximation used to fill blank areas in an image. This is just a typical example: The approximation is based upon random hill-climbing, and is by nature nondeterministic and chaotic. Results vary wildly, even for the same input.

My main interest is in disocclusion or inpainting - the use of these vorinoi diagrams to correct damage to an image, such as when a channel logo is removed from a television recording. This is achievable via a simple modification to ignore regions of the image designated as 'damaged' when producing the vorinoi approximation, then masking this approximation back into the original image in place of those areas.

A few tests show that this does work, and work well - it is espicially well suited for animation, and can rival any other form of inpainting I am aware of in terms of quality. A serious flaw is processor time: With even a core2quad computer taking several minutes to compute each frame, it is just impractical. The voronoi diagram drawing function (Recursive rectangular regions) works, but too slowly.

Though requiring substantial processor time, voronoi approximation proves quite effective at filling in blanks in animation. The complexity at the start of this test-sequence proves overwhelming, but the simpler images towards the end are disoccluded with near-perfection.