“Depixelizing pixel art” by Kopf and Lischinski

We describe a novel algorithm for extracting a resolution-independent vector representation from pixel art images, which enables magnifying the results 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 creates ambiguities in the connectedness and separation of diagonal neighbors. 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.

1. Adobe, Inc., 2010. Adobe Illustrator CS5. http://www.adobe.com/products/illustrator/.Google Scholar
2. de Boor, C. 1978. A Practical Guide to Splines. Springer-Verlag.Google Scholar
3. Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. Proceedings of SIGGRAPH ’95, 173–182. Google Scholar
4. Fattal, R. 2007. Image upsampling via imposed edge statistics. ACM Trans. Graph. 26, 3, 95:1–95:8. Google ScholarDigital Library
5. Glasner, D., Bagon, S., and Irani, M. 2009. Super-resolution from a single image. In Proc. ICCV, IEEE.Google Scholar
6. Hormann, K. 2001. Theory and Applications of Parameterizing Triangulations. PhD thesis, University of Erlangen.Google Scholar
7. Jeschke, S., Cline, D., and Wonka, P. 2009. A GPU Laplacian solver for diffusion curves and Poisson image editing. ACM Trans. Graph. 28, 5, 116:1–116:8. Google ScholarDigital Library
8. Kong, T. Y., and Rosenfeld, A., Eds. 1996. Topological Algorithms for Digital Image Processing. Elsevier Science Inc., New York, NY, USA. Google Scholar
9. Lai, Y.-K., Hu, S.-M., and Martin, R. R. 2009. Automatic and topology-preserving gradient mesh generation for image vectorization. ACM Trans. Graph. 28, 3, 85:1–85:8. Google ScholarDigital Library
10. Lecot, G., and Levy, B. 2006. ARDECO: Automatic region detection and conversion. In Proc. EGSR 2006, 349–360. Google Scholar
11. Liauw Kie Fa, D., 2001. 2xSaI: The advanced 2x Scale and Interpolation engine. http://www.xs4all.nl/~vdnoort/emulation/2xsai/, retrieved May 2011.Google Scholar
12. Mazzoleni, A., 2001. Scale2x. http://scale2x.sourceforge.net, retrieved May 2011.Google Scholar
13. Nehab, D., and Hoppe, H. 2008. Random-access rendering of general vector graphics. ACM Trans. Graph. 27, 5, 135:1–135:10. Google ScholarDigital Library
14. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: a vector representation for smooth-shaded images. ACM Trans. Graph. 27, 3, 92:1–92:8. Google ScholarDigital Library
15. Selinger, P., 2003. Potrace: a polygon-based tracing algorithm. http://potrace.sourceforge.net, retrieved May 2011.Google Scholar
16. Stepin, M., 2003. Demos & Docs — hq2x/hq3x/hq4x Magnification Filter. http://www.hiend3d.com/demos.html, retrieved May 2011.Google Scholar
17. Vector Magic, Inc., 2010. Vector Magic. http://vectormagic.com.Google Scholar
18. Wikipedia, 2011. Pixel art scaling algorithms. http://en.wikipedia.org/wiki/Pixel_art_scaling_algorithms, 15 April 2011.Google Scholar
19. Wolberg, G. 1990. Digital Image Warping, 1st ed. IEEE Computer Society Press, Los Alamitos, CA, USA. Google Scholar
20. Xia, T., Liao, B., and Yu, Y. 2009. Patch-based image vectorization with automatic curvilinear feature alignment. ACM Trans. Graph. 28, 5, 115:1–115:10. Google ScholarDigital Library