We implemented the "Depixelizing Pixel Art" Algorithm by Kopf & Lischinski [1] in Java and made an Android Pixel-Painter App out of it.

At some points we departed a bit from the original paper:

For the (approximate) Voronoi diagram we do not use a lookup table but look at the orientation of each neighboring edge to determine the resulting pixel shape because of that we have a special step that makes cell containing a single pixel surrounded by another color a bit bigger, as otherwise single pixel features appear too small (e.g. the dolphin from the original paper would otherwise get tiny Howard-Moon-Style eyes) we use Catmull-Rom Splines instead of B-Splines. As CR Splines go through their control points, we do not need the correction step for spline positions mentioned in the paper.

We have not figured out how to add the shading for non-contour edges yet. SVG (which is our target format) only allows Radial and Linear Gradients. We thought about using Mesh Gradients or diffusion curves, but they are not part of SVG yet... Also, the energy minimization step is still quite slow. We use local relaxation as recommended in the paper, which works but is not very fast. We want to try out some global methods that will hopefully speed the process up.

What do you think?

[1] (http://research.microsoft.com/en-us/um/people/kopf/pixelart/)