Repository navigation
Expand file tree
/
Copy path04-regions.html
More file actions
224 lines (215 loc) · 14.9 KB
/
Copy path04-regions.html
File metadata and controls
224 lines (215 loc) · 14.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Regions — inkvec</title>
<link rel="stylesheet" href="assets/doc.css">
</head>
<body>
<div class="wrap">
<header class="masthead">
<p class="eyebrow">Stage 4 of 16</p>
<h1>Turning a colour map into a set of shapes</h1>
<p class="standfirst">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.</p>
<p class="pairlink">Technical reference: <a href="04-regions.md">04-regions.md</a></p>
</header>
<main>
<section>
<h2>A colour is not yet a shape</h2>
<p>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.</p>
<p>This stage answers each of those questions in turn, and hands the next stage a
set of connected, single-ink regions it can trust.</p>
</section>
<section>
<h2>The sliver problem</h2>
<p>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.</p>
<p>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.</p>
<figure>
<svg viewBox="0 0 640 260" role="img" aria-label="A thin ribbon of blend pixels along a boundary shown as its own fragile region before absorption, and folded back into the ink it belongs to afterwards">
<text x="20" y="24" class="fig-label-strong">A sliver, before and after absorption</text>
<g transform="translate(30,55)">
<text x="0" y="-10" class="fig-label">Before — the ribbon is its own region</text>
<rect x="0" y="0" width="46" height="46" fill="#2b2622" stroke="var(--rule)"/>
<rect x="46" y="0" width="46" height="46" fill="#5c4b3a" stroke="var(--rule)"/>
<rect x="92" y="0" width="46" height="46" fill="#a08a6f" stroke="var(--rule)"/>
<rect x="138" y="0" width="46" height="46" fill="#cdbfa9" stroke="var(--rule)"/>
<rect x="184" y="0" width="46" height="46" fill="#efe9dd" stroke="var(--rule)"/>
<rect x="46" y="-6" width="138" height="58" fill="none" stroke="var(--copper)" stroke-width="2" stroke-dasharray="4 3"/>
<text x="115" y="70" text-anchor="middle" class="fig-label" fill="var(--copper)">its own thin face, with a boundary on both sides</text>
</g>
<g transform="translate(30,175)">
<text x="0" y="-10" class="fig-label">After — folded back into the ink it mixes with</text>
<rect x="0" y="0" width="46" height="46" fill="#2b2622" stroke="var(--rule)"/>
<rect x="46" y="0" width="46" height="46" fill="#5c4b3a" stroke="var(--rule)"/>
<rect x="92" y="0" width="46" height="46" fill="#a08a6f" stroke="var(--rule)"/>
<rect x="138" y="0" width="46" height="46" fill="#cdbfa9" stroke="var(--rule)"/>
<rect x="184" y="0" width="46" height="46" fill="#efe9dd" stroke="var(--rule)"/>
<rect x="0" y="-6" width="138" height="58" fill="none" stroke="var(--copper)" stroke-width="2"/>
<rect x="138" y="-6" width="92" height="58" fill="none" stroke="var(--ink-faint)" stroke-width="2"/>
<text x="69" y="70" text-anchor="middle" class="fig-label" fill="var(--copper)">one region, one boundary</text>
</g>
</svg>
<figcaption>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.</figcaption>
</figure>
<p>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.</p>
<div class="aside">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.</div>
</section>
<section>
<h2>Same colour, different objects</h2>
<p>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.</p>
<p>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.</p>
<p>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.</p>
</section>
<section>
<h2>The one true ambiguity: four pixels at a corner</h2>
<p>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.</p>
<figure>
<svg viewBox="0 0 640 320" role="img" aria-label="Four pixels meeting at one corner, two diagonal readings: one connected bowtie shape, or two shapes that merely touch at a point">
<text x="20" y="24" class="fig-label-strong">The chequerboard corner: two equally valid readings</text>
<g transform="translate(40,50)">
<text x="60" y="-10" text-anchor="middle" class="fig-label">The four pixels</text>
<rect x="0" y="0" width="60" height="60" fill="#3a3530" stroke="var(--rule)"/>
<rect x="60" y="0" width="60" height="60" fill="#cbb89a" stroke="var(--rule)"/>
<rect x="0" y="60" width="60" height="60" fill="#cbb89a" stroke="var(--rule)"/>
<rect x="60" y="60" width="60" height="60" fill="#3a3530" stroke="var(--rule)"/>
<circle cx="60" cy="60" r="4" fill="var(--copper)"/>
<text x="60" y="140" text-anchor="middle" class="fig-label">shared corner</text>
</g>
<g transform="translate(300,50)">
<text x="75" y="-10" text-anchor="middle" class="fig-label-strong">Reading 1 — one shape, welded</text>
<rect x="0" y="0" width="60" height="60" fill="#3a3530" stroke="var(--rule)"/>
<rect x="60" y="0" width="60" height="60" fill="#cbb89a" stroke="var(--rule)"/>
<rect x="0" y="60" width="60" height="60" fill="#cbb89a" stroke="var(--rule)"/>
<rect x="60" y="60" width="60" height="60" fill="#3a3530" stroke="var(--rule)"/>
<path d="M 0,0 L 60,0 L 60,60 L 120,60 L 120,120 L 60,120 L 60,60 L 0,60 Z"
fill="none" stroke="var(--copper)" stroke-width="3"/>
<circle cx="60" cy="60" r="4" fill="var(--copper)"/>
<text x="75" y="145" text-anchor="middle" class="fig-label" fill="var(--copper)">one outline, one point where it pinches to nothing</text>
</g>
<g transform="translate(300,215)">
<text x="75" y="-10" text-anchor="middle" class="fig-label-strong">Reading 2 — two shapes touching</text>
<rect x="0" y="0" width="60" height="60" fill="#3a3530" stroke="var(--rule)"/>
<rect x="60" y="0" width="60" height="60" fill="#cbb89a" stroke="var(--rule)"/>
<rect x="0" y="60" width="60" height="60" fill="#cbb89a" stroke="var(--rule)"/>
<rect x="60" y="60" width="60" height="60" fill="#3a3530" stroke="var(--rule)"/>
<path d="M 0,0 L 58,0 L 58,58 L 0,58 Z" fill="none" stroke="var(--copper)" stroke-width="3"/>
<path d="M 62,62 L 120,62 L 120,120 L 62,120 Z" fill="none" stroke="var(--copper)" stroke-width="3"/>
<circle cx="58" cy="58" r="3.5" fill="var(--copper)"/>
<circle cx="62" cy="62" r="3.5" fill="var(--copper)"/>
<text x="75" y="140" text-anchor="middle" class="fig-label" fill="var(--copper)">two outlines, each keeping its own copy of the corner</text>
</g>
</svg>
<figcaption>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.</figcaption>
</figure>
<p>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.</p>
<p>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.</p>
<div class="aside">This corner-merging pass is an experiment. It is built only into a
research version of the tracer, and is switched <b>off</b> 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.</div>
</section>
<section>
<h2>What this stage hands forward</h2>
<p>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.</p>
</section>
</main>
<nav class="stages">
<a href="00-overview.html">Overview</a>
<a href="01-intake.html">1 Intake</a>
<a href="02-coverage.html">2 Coverage</a>
<a href="03-palette.html">3 Palette</a>
<a href="04-regions.html" aria-current="page">4 Regions</a>
<a href="05-gradients.html">5 Gradients</a>
<a href="06-planar-map.html">6 Planar map</a>
<a href="07-subpixel.html">7 Sub-pixel</a>
<a href="08-boundary-solve.html">8 Boundary solve</a>
<a href="09-decode.html">9 Decode</a>
<a href="10-symmetry.html">10 Symmetry</a>
<a href="11-fitting.html">11 Curve fitting</a>
<a href="12-repair.html">12 Repair</a>
<a href="13-emit.html">13 Emit</a>
<a href="14-fast-mode.html">14 Fast mode</a>
<a href="15-strokes.html">15 Strokes</a>
<a href="constants.md">Constants</a>
</nav>
</div>
</body>
</html>