I recently stumbled upon this neat algorithm by Johannes Kopf and Dani Lischinski. In short, their algorithm takes a pixelart image, such as those found in 8-bit video games, and produces a new image that somehow makes you think “hey, that looks like what the artist actually had in mind”. In other words, it tries to generate the ideal image for which the pixel art is only an imperfect representation. The results explain it better:

If you are interested in this kind of stuff, I really recommend you read their paper, it is well written, easy to understand even for people with no deep knowledge of computer graphics (like myself) or for people with no programming training. I **partially** implemented their algorithm using Common Lisp and Zach Beane’s Vecto library, here’s a very very short description, just to illustrate the different steps. Some eye-candy at the end!

**Finding Vicinities**

First, we find which regions of the original image are part of a single feature.

**Re-shaping Pixels**

Once different regions have been found, pixels are re-shaped so that each region has a well defined contour.

**Smoothing Edges**

Finally, edges are identified …

… and smoothed

Keep in mind that this is only a partial implementation, the original algorithm also re-shapes edges to make them look more natural, reducing zig-zag curves for example. (they also use a different type of curve, *b-splines*, which works better than what I’m using, *catmull rom*) and therefore produces much better results. Have a look at their examples in the linked article.

**Some Examples!**

Click on the images to enlarge

Thanks to Javier Moreno, Norman Garcia and Angie Bloor for their comments.

The old Galactus is back!

This is the kind of things that people can accomplish when someone gives a whole new deep sight to a problem and uses his own perspective to solve it.

Not so new:

http://code.google.com/p/hqx/

http://en.wikipedia.org/wiki/Hqx

For years it’s been used (in real-time) on many arcade/console emulators.

http://www.reddit.com/r/ClassicConsoleGaming/comments/c666o/if_youre_using_an_emulator_try_using_the_hqx/

Hqx implementation only handles lookup tables for 2x, 3x and 4x, and it doesnt solve staircases as this algorithm does (I didnt implement the staircasing). See for example the authors’ comparison of their algorith agains hqx at 16x:

http://research.microsoft.com/en-us/um/people/kopf/pixelart/supplementary/comparison_hq4x.html

You’re right! Staircases are nicely solved here, it looks great. Thanks for the link.

Si, da buenos resultados, tal vez pueda aplicarse a ciertos motivos precolombinos, tocaría ensayar.

Nice post and links, thanks Galactus!

Uhm. Question is: how come you came across this paper? I assume that it is not related to your job. It gives me the feeling that I should also be looking outside my main area of activities… there is much fun out there

I think it was posted on programming.reddit.com, if I’m not wrong

[…] De una imagen en pixeles a una imagen mejorada [ING] blog.crazyrobot.net/?p=420 por evol hace 2 segundos […]

great reaaaaaad thank you so much =]

Amazing work,

I’m trying to implement the same algorithm by Johannes Kopf and Dani Lischinski in c#.

But I’m having problems in reshaping the pixel cell, did you use Voronoi’s algorithm? How did you procede?

I’m having problems because my implementation of voronoi use only a point for each cell and doesn’t include the edges of my graph in the calculation.

Could you give me some help?

thanks

Hi Michael, that part is a little bit tricky, I did code my own algorithm after studying the different cases (using pen and paper). There are not that many combinations of cells/contrasts so you dont have to code a general algorithm. I can send you the lisp code if you want (email me to sergio.garcia@gmail.com)

[…] This post has been moved here […]