DIAGRAM EDITION  the stages in plain languageReference edition →

Stage 4 of 16

Turning a colour map into a set of shapes

Knowing which colour a pixel is assigned to is not the same as knowing which shape it belongs to. This stage cleans up the label map into a set of solid, single-coloured, correctly separated regions — removing speckle, folding anti-aliasing back into the ink it belongs to, and resolving the one genuine ambiguity a pixel grid can produce.

Technical reference: 04-regions.md

A colour is not yet a shape

The previous stage decided, pixel by pixel, which of a small set of inks each pixel most resembles. That decision has no notion of shape at all. It does not know that a lone stray pixel is noise rather than a shape of its own. It does not know that a thin ribbon of in-between colour running along a boundary is only the blur of anti-aliasing, not a third ink. It does not know that two blobs of identical colour on opposite sides of the picture are two different objects. And it cannot tell, on its own, whether two shapes that touch at a single pixel corner are one connected mark or two shapes that happen to kiss.

This stage answers each of those questions in turn, and hands the next stage a set of connected, single-ink regions it can trust.

The sliver problem

Every soft edge between two inks is, in the label map, a thin ribbon of pixels that were each assigned to whichever palette colour they happened to sit nearest — often neither of the two inks actually forming the edge, but some third colour that happens to sit nearby in colour space. Left alone, that ribbon becomes its own skinny region: a sliver, with its own boundary on both sides, running the whole length of every edge in the picture. On one 36-cell test mosaic, leaving slivers unabsorbed turned a scene with a true count of 37 flat regions into 128 separate faces.

The fix is not to erase the ribbon, but to ask what mixture of real inks would explain its colour, and give each sliver pixel back to the ink that mixture says it mostly is — not to whichever palette colour it happens to sit nearest. A ribbon between two inks is split down the middle, each pixel going to its own side, rather than handed whole to one of them.

A sliver, before and after absorption Before — the ribbon is its own region its own thin face, with a boundary on both sides After — folded back into the ink it mixes with one region, one boundary
The pixel colours never change. What changes is which region each one is filed under — decided by asking which mixture of real inks explains it, not by which single palette colour it happens to sit nearest.

Each candidate sliver is tested against up to three neighbouring inks at once, because where boundaries meet, an edge pixel is a mixture of three colours, not two. A component is only absorbed if it is thin, if almost all of its border touches those few inks, and if at least four fifths of its pixels fit that mixture within a tolerance set from the picture's own measured noise. A second, pixel-by-pixel pass then deals with the single blend pixels left along boundaries: each moves to a neighbouring ink only when a blend of its neighbours explains its colour at least twice as well as its own ink does.

A genuinely thin real feature — a hairline stroke a single pixel wide — is protected by the same test, not caught by it: its colour does not sit on the line between its neighbours' colours, so it fails the mixture test outright and keeps its own identity.

Same colour, different objects

Colour alone cannot tell two separate shapes of the same ink apart. Two dots of identical red on opposite sides of a logo are, to a colour label, indistinguishable — but they are two different marks, and treating them as one region has real consequences beyond tidiness. A region drawn from several disconnected pieces has no single flat colour and no single sensible fill shape; asked to explain the left-over difference between its pieces, the fitting stage further downstream will happily invent a gradient to cover a difference that was never a gradient at all — it was simply two unrelated objects sharing a palette entry.

This stage separates every region into its actually-connected pieces and numbers them. Two same-coloured shapes that do not touch become two independent regions, each free to be measured, edited, and filled on its own terms.

The numbers have a ceiling: the format the rest of the tracer works in can hold 65,535 regions, and an image of pure noise can have more. Past that limit the smallest regions are merged, each into the neighbour it shares the longest border with, until the rest fit. The tracer used to lump every region past the limit together into one, which then held scattered pixels of many colours all painted the same; now every region is still one connected, single-colour shape. No icon or logo in the test sets comes anywhere near the limit.

The one true ambiguity: four pixels at a corner

There is exactly one situation a pixel grid cannot settle by itself. Picture four pixels meeting at a single shared corner, arranged so the two pixels on one diagonal are one ink and the two on the other diagonal are a second ink — a chequerboard corner. Read one way, the two same-coloured pixels are corners of one connected shape that happens to pinch down to nothing at that single point, like an hourglass. Read the other way, they are two separate shapes that simply touch at a point. Nothing in the four pixels themselves says which is true — both readings explain the same four colours equally well.

The chequerboard corner: two equally valid readings The four pixels shared corner Reading 1 — one shape, welded one outline, one point where it pinches to nothing Reading 2 — two shapes touching two outlines, each keeping its own copy of the corner
The pixels are identical in both readings. What differs is a purely topological choice: does one outline pinch shut at the corner, or do two separate outlines each keep their own copy of it, free to move apart later.

This stage resolves the ambiguity by going back to the picture itself, not the label map, and asking how much of each of the two inks actually covers each of the four pixels. Those four coverage fractions are combined into a single estimate of which ink genuinely owns the exact corner point, together with an honest measure of how uncertain that estimate is — carried through from the same pixel noise used throughout the tracer. Only when the reading clears a firm statistical margin is the corner actually merged one way or the other; below that margin, the two readings are indistinguishable and the corner is left exactly as found, neither welded nor split.

That caution matters on a real chequerboard pattern — a QR code, a chequered flag — whose corners sit exactly on the boundary between the two readings, because the two squares really do meet at a single point and neither reading is truer than the other. There the estimate lands on the half-way mark, and the corner keeps the junction it had rather than being forced one way on rounding noise.

This corner-merging pass is an experiment. It is built only into a research version of the tracer, and is switched off even there unless asked for; the released tracer does not run it. No measurement of what it does to the test sets is recorded in the current code.

What this stage hands forward

The output is a face per connected, single-ink shape: speckle gone, anti-aliasing folded into whichever ink it actually belongs to, disconnected same-coloured shapes told apart, and — in the research version — four-way corners either resolved with real statistical confidence or left honestly undecided. The gradient stage runs in the middle of this one, after the clean-up and before the split into connected pieces, so each face inherits the fill fitted to the colour region it came from. Everything after — tracing each boundary, deciding where curves bend — works on this set of faces, not on the raw colour labels underneath it.