Why one point at a time is not enough
Picture a boundary as a dot-to-dot drawing: a chain of points, each one free to slide back and forth along its own short line perpendicular to the edge, hunting for the spot where the pixel underneath it looks exactly half-covered. That is roughly what the earlier refinement stages do, and it works well for an isolated, well-separated edge.
It breaks down in two ways that a single point, working alone, cannot see. First, a pixel's colour is not only about the one boundary running near it — if several shapes meet close together, that pixel's colour is a blend of all of them, and no single point can account for that on its own. Second, a point can happily slide sideways, along the boundary rather than across it, without changing how any pixel looks at all — nothing in a one-point-at-a-time process stops it drifting, because no single pixel measurement objects.
So this stage treats the whole boundary — every point on it — as one set of unknowns to be solved together, against one shared yardstick: how closely the shape, if rendered honestly, would reproduce the actual picture.
The yardstick: paint it and compare
The honest way to check whether a boundary is in the right place is to ask what a careful renderer would do with it — not "is the point near the edge", but "if I clipped this exact pixel square by this exact boundary, what fraction of it falls on each side, and does mixing the two colours in that proportion match what the pixel actually shows?"
That clipped fraction can be computed exactly, as a plain area calculation, and — this is what makes solving thousands of points at once practical rather than impossibly slow — the way that area changes as any one point moves can also be worked out exactly, by algebra, instead of by nudging the point slightly and re-measuring. Nudging-and-re-measuring for every point against every pixel would be far too slow; having the exact formula in hand is what lets the whole boundary move together in reasonable time.
The comparison covers every pixel near the boundary, not only the pixels a boundary happens to cross right now. That matters more than it sounds. An earlier version compared only the crossed pixels, so the moment a boundary slid out of a pixel, that pixel simply dropped out of the score, and the score jumped. The solver spent most of its effort bumping into those jumps instead of settling. Scoring a fixed strip of pixels around the boundary, each painted exactly from the current shape, makes the score change smoothly as points move: a pixel a boundary leaves is still scored, as a plain pixel of the colour now covering it.
Two habits of mind, built in
Matching pixels exactly is not, by itself, enough to produce a sensible boundary — an infinite number of wiggly shapes can match a set of pixels equally well (more on that below). Two additional preferences are built into the maths, both scaled automatically to the size and contrast of the particular image so they mean the same thing on a plain two-colour logo and on a crowded, busy emoji:
- Prefer a smooth line to a corner, and a gentle corner to a sharp one. Corners are allowed — a sharp corner in the artwork should stay sharp — but a corner costs something in proportion to how sharp it is, so the solver does not spend one big, honest corner's worth of "cost" on ten small, meaningless zigzags instead.
- Do not drift without reason. Every point starts from where the earlier, careful measurement put it, and unless the picture gives it good reason to move, it stays close to that starting position — especially along the boundary's own length, in the direction a pixel-matching test cannot see at all.
Where three shapes meet, trust the intersection, not one pixel
Where two boundaries meet a third — a corner where three colours come together — a single pixel there is a blend of three or more shapes at once, and reading a clean signal out of that blend is much less reliable than reading it from an ordinary two-colour edge. This stage handles that by holding those meeting points firmly in place, several times more firmly than an ordinary point, and leaves the pixels where two boundaries meet out of the pixel-matching comparison entirely: they still move, because the ordinary boundary points on either side of them pull them along, but the pixels right at the meeting point do not get a vote on exactly where it sits. An earlier stage has already placed that point by working out precisely where the two boundary lines geometrically cross, which is sturdier evidence than one blended pixel.
This was tried the other way — letting those meeting-point pixels vote too — and it made results measurably worse across a large test set of icons, not better. The blended-pixel signal there is weak enough that letting it vote costs more than it buys.
The sawtooth: a real limit of the idea, honestly reported
Matching pixels exactly has a blind spot. Picture a thin ribbon — a stroke about two pixels wide. Its two long edges are close enough together that they are competing for the same pixels. If one edge nibbles a little area away from a pixel and the other edge, right next to it, gives a little area back, the total picture is unchanged — the maths cannot tell the difference between a smooth straight edge and a jagged, saw-toothed one that happens to trade area back and forth in exactly this way.
The team measured, and rejected, four different general-purpose fixes for this — turning up the smoothness preference further, adding a penalty for how long the boundary is, weighting each point by how confidently it was originally measured, and simply stopping the solver earlier before the teeth have time to grow. Every one of them either failed to remove the sawtooth, or removed it at the cost of blurring away real, wanted detail somewhere else in the corpus of test images. None of the four was shipped.
A safety catch: never let the fix tie the boundary in a knot
Because points move together rather than one at a time, there is a real risk that the solved answer accidentally pulls one side of a boundary through the other — imagine pulling both edges of that thin ribbon toward the same strip of dark pixels until they cross. A crossed boundary is not a small cosmetic problem downstream; it can make a shape's inside and outside ambiguous and force a lot of expensive repair work later.
So after solving, the stage checks whether it introduced any new crossing that was not already there before it started (an existing tangle from earlier stages is a separate problem, not this stage's to fix). A crossing involves two particular boundaries, so only those two are pulled back toward where they started, halfway at a time, until the crossing is gone; every other boundary in the picture keeps its improvement. In the worst case the two boundaries go back exactly where they were. The check used to pull the whole picture back for a single crossing anywhere, and on some icons that threw away nearly all of the work.
How long to keep solving
Like any iterative process, this one has to decide when to stop. The boundaries of one picture usually fall into a handful of separate groups that share no pixel (the letters of a word, the pieces of an emoji), and each group is solved on its own, so a simple shape can finish while a complicated one keeps going.
The method remembers its last few steps to judge how curved the score is, a standard technique from numerical optimisation. How far to go along each step is decided by a second standard technique: it tries the natural step length, and if the score is still falling steeply there it goes further; if it overshot, it fits a smooth curve through what it has seen and aims for the bottom. The version before could only shorten a step, never lengthen it, and it stopped as soon as its steps got short — which they did because it had shortened them, not because the work was done. On one icon it stopped after two steps with both bars of an equals sign a twentieth of a pixel too thin.
A group now stops when another step would not change the score of the whole picture by more than a ten-millionth of what is left to gain, or when the score is flat in every direction it is allowed to move, or after 64 steps at most. Measuring "worth continuing" against the whole picture, not against the group, lets a group with almost nothing to gain stop at once and a large one keep going. The 64-step limit was chosen by measurement: doubling it bought a fifth of a percent more accuracy on 512-pixel icons for a trace about 15 % slower.
Measured on the 246 test icons against the previous release, the finished traces match the artist's originals more closely at every size the tests use — about 6 % closer on 512-pixel icons on a transparent background, 3 % on a white one, and 12 % on 128-pixel icons, this stage together with the border fix of the intake stage — with fewer numbers in the file, for about a fifth more trace time.
When a picture is too busy to solve
To score its strip of pixels quickly, the stage prepares some tables before it starts: for each stretch of the strip, the colour every nearby shape would paint at every pixel, and running totals of those colours. On ordinary artwork these tables are small — a few megabytes for an icon, about 22 megabytes for the largest, most detailed image in the test sets.
A few kinds of picture break that. Think of stripes one pixel wide, a checkerboard of single pixels, the grey-and-white "transparency" checkerboard some images have baked in behind the artwork, or a small picture blown up with hard square pixels. There every pixel sits next to a boundary, so the strip covers whole rows, and a row crosses hundreds of shapes. The tables grow with the square of that number: for one-pixel stripes on a 512-pixel image they would have needed about 265 gigabytes, and the trace crashed.
So the stage now adds up the size of those tables before it builds any of them. If they would pass a fixed allowance — 256 MiB, or 32 bytes per pixel on images larger than about 2,900 pixels square — it skips the solve altogether and keeps the boundary the earlier stages measured, exactly as if the solve had found nothing to improve. Little is lost: what the solve can buy on such pictures is small, and on the stripes, where every pixel is a blend of two shapes whatever the boundary does, it gains nothing at all. The skip covers the whole picture, so an icon drawn on a baked checkerboard keeps its measured edges too; on test images of that kind the result came out very slightly less accurate, with half the memory. On the test sets the tracer is judged on, the allowance is never reached.