Microsoft Develops Algorithm to Depixelate Pixel Art

Over the last 20 years, some tremendous products have come out of Microsoft Research many of which you are already familiar with such as Photosynth, Image Composite Editor, WorldWide Telescope, Surface, Songsmith, Kinnect, Street Slide, Touch Mouse, PowerPivot and so many others.

In a new research paper, Johannes Kopf of Microsoft Research and Dani Lischinski of The Hebrew University describe a new algorithm for converting pixel art (those old school 8-bit video games) into super smooth vectors which can be magnified by an arbitrary amount without image degradation.

Our algorithm resolves pixel-scale features in the input and converts them into regions with smoothly varying shading that are crisply separated by piecewise-smooth contour curves. In the original image, pixels are represented on a square pixel lattice, where diagonal neighbors are only connected through a single point. This causes thin features to become visually disconnected under magnification by conventional means, and it causes connectedness and separation of diagonal neighbors to be ambiguous. The key to our algorithm is in resolving these ambiguities. This enables us to reshape the pixel cells so that neighboring pixels belonging to the same feature are connected through edges, thereby preserving the feature connectivity under magnification. We reduce pixel aliasing artifacts and improve smoothness by fitting spline curves to contours in the image and optimizing their control points.

In the examples shown above, each of the images in the middle show the results of Kopf’s and Lischinski’s method as compared to the pixel input on the left and the results of other depixelating algorithms on the right. As can be seen, the new algorithm produces superior results.

Johannes Kopf and Dani Lischinski says that they’ve applied their algorithm to a wide variety of inputs from video games and other software. While they did not invest much time into optimizing their algorithm, it already performs quite well.

Here is a video of the algorithm being applied to Super Mario. Since the algorithm does not run in real-time speed, they dumped frames from a video game emulator to disk and applied their technique to the full frames.

There are many avenues for future work. Obviously, it would be nice to optimize the performance of the algorithm so that it can be applied in real-time in an emulator. Some of the ideas presented in this work can potentially benefit general image vectorization techniques.

Another interesting direction would be to improve the handling of anti-aliased input images. This might by done by rendering some curves as soft edges rather than sharp contours. A whole new interesting topic would be to look into temporal upsampling of animated pixel art images. If we magnify from a tiny input to HD resolution, locations are quite quantized which might result in “jumpy” animations. Since many modern display devices are operating at a much higher refresh rate than earlier hardware, one could improve the animations by generating intermediate frames.