Tab Completion

I'm Tab Atkins Jr, and I wear many hats. I work for Google on the Chrome browser as a Web Standards Hacker. I'm also a member of the CSS Working Group, and am either a member or contributor to several other working groups in the W3C. You can contact me here.
Listing of All Posts

Depixelating Pixel Art

Last updated:

For my future use, I distilled the algorithm for depixelating pixel art into its component steps, minus the explanations and figures.

I've also copied this over into a GitHub project, which will host the code when I write it.

General Algorithm

  1. Construct a graph where each pixel is a node, connected to its 8 neighbors.

  2. Remove all edges between nodes with "dissimilar" colors. (In YUV, colors with dY>48, dU>7, or dV>6.)

  3. Examine all four-squares of nodes:

    1. If all four are fully connected, remove the diagonals. (It's a block of the same color.)
    2. If they're only connected via diagonals, use feature detection to tell which diagonal to keep:
    3. Compare the length of the curves (valence-2 nodes) that each diagonal is a part of. Cast vote in favor of the longer one, with weight equal to difference.
    4. Compare the size of the connected graphs each diagonal is a part of, in an 8x8 window. Cast vote in favor of the smaller component, with weight equal to difference in size.
    5. If either diagonal connects directly to a lone pixel (valence-1 node) cast a vote in favor of it, with weight 5 (empirically determined).
  4. You now have a fully planar set of disconnected graphs.

  5. Chop each connection in half, associating each half with its closer point. Construct a Voronoi diagram from each of these points+half-connections. Quantize the Voronoi to a quarter-pixel grid.

  6. Simplify the Voronoi diagram by collapsing valence-2 nodes into lines that connect their higher/lower-connected endpoints.

  7. You now have the basic depixelated shape.

  8. Walk the graph of cell points (nodes). Ignoring junctions separating similar (connected) cells, find all runs of valence-2 cell points and turn them into quadratic b-splines, with control points set to the nodes.

  9. Simplify all 3-spline junctions.

    1. If one of the splines is a "shading spline" (separating two areas with YUV distance <= 100) and the other two are "contour spline" (YUV distance > 100), connect the two contour splines into one.
    2. Otherwise, find the two splines which connect with an angle closest to 180deg, and join them together.
    3. Keep in mind that the end-point of the non-connected spline of each triad will need to be adjusted to lie exactly on the curve defined by the connected splines.
  10. You now have a relatively smooth depixelated shape.

  11. Detect "corners" that shouldn't be smoothed away. Corners are all runs of 4-5 points that are related by the following 5 relations (plus rotations/mirrors):

    1. (0,0) (.25, .75) (.75, .75) (1, 0)
    2. (-.25, .25) (.25, .75) (.75, .75) (1, 0)
    3. (-.25, .25) (.25, .75) (.75, .75) (1.25, .25)
    4. (0,0) (0,1) (1,1) (1,0)
    5. (.75, -.25) (.25, .25) (.25, .75) (.75, .75) (1.25, .25)
  12. Optimize all remaining nodes by minimizing an energy function over them. Each node contributes the sum of:

    1. Curvature. Integrate the curvature function over the segment influenced by the node. Can use simple numerical sampling here.
    2. Position deviation. Take the fourth power (empirically determined) of the distance between its current location and its original location.

The energy function is non-linear but smooth, so you can do local modifications by randomly selecting nodes, randomly jiggling them to find a lower-energy state, and repeating until satisfied. Paper doesn't specify how many iterations they used.

  1. Rejigger the "corner" nodes to match up better with the energy-minimized nodes and minimize cell-shape distortion. Paper is unclear here: use harmonic maps; it's solving a simple sparse linear system; [Hormann 2001] has a full explanation.
  2. Remember to rejigger the endpoint of the non-connected spline in each triad connection!
  3. Render the graph accordingly. [Nehab and Hoppe 2008] Each reshaped cell diffuses its color from its centroid, constrained by the spline boundaries? Simpler if you assume that all color differences are significant; you get more contours, but they're all solid-color and look pretty good. (And can actually be done in SVG, which doesn't have diffusion-based paint servers yet.)

DONE.

Future work

  1. Detect dithering patterns used in color-constrained graphics, and consider them part of a single solid-color region.
  2. Detect "corners" (junctions where long straight lines meet) and increase the multiplicity of the knot vector to get a sharper corner.

Refs

NEHAB, D., AND HOPPE, H. 2008. Random-access rendering of general vector graphics. ACM Trans. Graph. 27, 5, 135:1–135:10.

HORMANN, K. 2001. Theory and Applications of Parameterizing Triangulations. PhD thesis, University of Erlangen.

(a limited set of Markdown is supported)

Cool stuff. Do you plan to release code at one point in the future?

Reply?

(a limited set of Markdown is supported)

Re #1: Yup, I've just added a link in the opening paragraph to the GitHub repo I started for it.

Reply?

(a limited set of Markdown is supported)

a follow up paper: http://www.ucsp.edu.pe/sibgrapi2013/eproceedings/technical/114688_2.pdf

and some tentative implementations in python you might be interested in:

https://github.com/vvanirudh/Pixel-Art https://github.com/wenderen/depixelizing

Reply?

(a limited set of Markdown is supported)