Depixelating Pixel Art
For my future use, I distilled the algorithm for depixelating pixel art into its component steps, minus the explanations and figures.
Construct a graph where each pixel is a node, connected to its 8 neighbors.
Remove all edges between nodes with "dissimilar" colors. (In YUV, colors with dY>48, dU>7, or dV>6.)
Examine all four-squares of nodes:
- If all four are fully connected, remove the diagonals. (It's a block of the same color.)
- If they're only connected via diagonals, use feature detection to tell which diagonal to keep:
- 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.
- 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.
- If either diagonal connects directly to a lone pixel (valence-1 node) cast a vote in favor of it, with weight 5 (empirically determined).
You now have a fully planar set of disconnected graphs.
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.
Simplify the Voronoi diagram by collapsing valence-2 nodes into lines that connect their higher/lower-connected endpoints.
You now have the basic depixelated shape.
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.
Simplify all 3-spline junctions.
- 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.
- Otherwise, find the two splines which connect with an angle closest to 180deg, and join them together.
- 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.
You now have a relatively smooth depixelated shape.
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):
- (0,0) (.25, .75) (.75, .75) (1, 0)
- (-.25, .25) (.25, .75) (.75, .75) (1, 0)
- (-.25, .25) (.25, .75) (.75, .75) (1.25, .25)
- (0,0) (0,1) (1,1) (1,0)
- (.75, -.25) (.25, .25) (.25, .75) (.75, .75) (1.25, .25)
Optimize all remaining nodes by minimizing an energy function over them. Each node contributes the sum of:
- Curvature. Integrate the curvature function over the segment influenced by the node. Can use simple numerical sampling here.
- 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.
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.
Remember to rejigger the endpoint of the non-connected spline in each triad connection!
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.)
- Detect dithering patterns used in color-constrained graphics, and consider them part of a single solid-color region.
- Detect "corners" (junctions where long straight lines meet) and increase the multiplicity of the knot vector to get a sharper corner.
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.