My first attempt was available on my Github, featured some awesome characteristics such as terrible performance, ugly memory management and was basically not working. I decided to delete it, start over and adopt a more thoughtful approach.
A detailed analysis of the properties of the algorithm reveals that many steps can be cut and that some processing just boils down to very simple operations on integers. The code is still ugly but the early steps are now lightning fast. I'm still having a hard time minimizing processing time, so the work is far from being finished, but I thought it would be nice to show some results obtained so far. The picture on the left is an upscale of the original image, and the one on the right is the simplified voronoi partition of the pixels after the transformation. Each cell is a pixel. (No colors, sorry.)
You may want to follow me on twitter.