Repository navigation
Expand file tree
/
Copy path08-boundary-solve.html
More file actions
288 lines (279 loc) · 18.8 KB
/
Copy path08-boundary-solve.html
File metadata and controls
288 lines (279 loc) · 18.8 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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Boundary solve — inkvec</title>
<link rel="stylesheet" href="assets/doc.css">
</head>
<body>
<div class="wrap">
<header class="masthead">
<p class="eyebrow">Stage 8 of 16</p>
<h1>Moving every edge at once</h1>
<p class="standfirst">Every earlier stage nudges one boundary point at a time, guided
by the pixels right next to it. This stage stops doing that. It gathers every point
on every boundary into a single problem and asks a much harder, much better
question: if I actually painted the picture this geometry describes, would it match
the image — not approximately, exactly?</p>
<p class="pairlink">Technical reference: <a href="08-boundary-solve.md">08-boundary-solve.md</a></p>
</header>
<main>
<section>
<h2>Why one point at a time is not enough</h2>
<p>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.</p>
<p>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 <em>all</em>
of them, and no single point can account for that on its own. Second, a point can
happily slide sideways, <em>along</em> 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.</p>
<p>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.</p>
</section>
<section>
<h2>The yardstick: paint it and compare</h2>
<p>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?"</p>
<figure>
<svg viewBox="0 0 640 240" role="img" aria-label="A pixel grid crossed by a boundary line, with the area on the ink side of the boundary shaded to show the exact clipped coverage">
<text x="20" y="24" class="fig-label-strong">One pixel, clipped exactly by the boundary crossing it</text>
<g transform="translate(40,50)">
<!-- 4x4 grid of pixels, each 45px -->
<g stroke="var(--rule)" fill="none">
<rect x="0" y="0" width="180" height="180"/>
<line x1="45" y1="0" x2="45" y2="180"/>
<line x1="90" y1="0" x2="90" y2="180"/>
<line x1="135" y1="0" x2="135" y2="180"/>
<line x1="0" y1="45" x2="180" y2="45"/>
<line x1="0" y1="90" x2="180" y2="90"/>
<line x1="0" y1="135" x2="180" y2="135"/>
</g>
<!-- ink region: everything right of a diagonal boundary -->
<path d="M 20,0 L 60,45 L 45,90 L 100,135 L 95,180 L 180,180 L 180,0 Z" fill="var(--copper-soft)"/>
<!-- the boundary curve itself -->
<path d="M 20,0 L 60,45 L 45,90 L 100,135 L 95,180" fill="none" class="fig-accent-stroke" stroke-width="2.5"/>
<!-- highlight one clipped pixel -->
<rect x="45" y="45" width="45" height="45" fill="none" stroke="var(--ink)" stroke-width="2"/>
<!-- shade the ink-side fraction of that pixel more strongly -->
<path d="M 60,45 L 90,45 L 90,90 L 45,90 L 45,90 L 60,45 Z" fill="var(--copper)" opacity="0.55"/>
<text x="95" y="70" class="fig-label" fill="var(--ink)">this pixel:</text>
<text x="95" y="86" class="fig-label" fill="var(--ink)">31% ink, 69% background</text>
</g>
</svg>
<figcaption>The stage computes this fraction — the pixel's exact clipped area —
for every boundary point at once, rather than approximating it, and moves the
points so the computed fraction matches the pixel's real colour.</figcaption>
</figure>
<p>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.</p>
<p>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.</p>
</section>
<section>
<h2>Two habits of mind, built in</h2>
<p>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:</p>
<ul>
<li><b>Prefer a smooth line to a corner, and a gentle corner to a sharp one.</b>
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.</li>
<li><b>Do not drift without reason.</b> 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.</li>
</ul>
</section>
<section>
<h2>Where three shapes meet, trust the intersection, not one pixel</h2>
<p>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.</p>
<p>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.</p>
</section>
<section>
<h2>The sawtooth: a real limit of the idea, honestly reported</h2>
<p>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.</p>
<figure>
<svg viewBox="0 0 640 220" role="img" aria-label="A smooth straight stroke compared with a jagged sawtooth stroke that renders to nearly the same pixels">
<text x="20" y="24" class="fig-label-strong">Two boundaries, almost the same picture</text>
<g transform="translate(30,50)">
<text x="0" y="0" class="fig-label">What the artwork looked like</text>
<rect x="0" y="14" width="260" height="120" fill="none" stroke="var(--rule)"/>
<path d="M 20,44 L 240,44" class="fig-accent-stroke" stroke-width="2"/>
<path d="M 20,104 L 240,104" class="fig-accent-stroke" stroke-width="2"/>
<rect x="20" y="44" width="220" height="60" fill="var(--ink)" opacity="0.85"/>
</g>
<g transform="translate(340,50)">
<text x="0" y="0" class="fig-label">A boundary that "cheats" and matches the same pixels</text>
<rect x="0" y="14" width="260" height="120" fill="none" stroke="var(--rule)"/>
<path d="M 20,44 L 40,52 L 60,40 L 80,52 L 100,40 L 120,52 L 140,40 L 160,52 L 180,40 L 200,52 L 220,44 L 240,44"
class="fig-accent-stroke" stroke-width="2"/>
<path d="M 20,104 L 40,96 L 60,108 L 80,96 L 100,108 L 120,96 L 140,108 L 160,96 L 180,108 L 200,96 L 220,104 L 240,104"
class="fig-accent-stroke" stroke-width="2"/>
<path d="M20,44 L 40,52 L 60,40 L 80,52 L 100,40 L 120,52 L 140,40 L 160,52 L 180,40 L 200,52 L 220,44 L 240,44 L 240,104 L 220,104 L 200,96 L 180,108 L 160,96 L 140,108 L 120,96 L 100,108 L 80,96 L 60,108 L 40,96 L 20,104 Z"
fill="var(--ink)" opacity="0.85"/>
</g>
</svg>
<figcaption>Rendered to pixels, these two look almost identical — the coloured
picture barely changes. Drawn as a shape, one is an honest stroke and the other
is a saw. Pixel-matching alone cannot always tell them apart.</figcaption>
</figure>
<p>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.</p>
<div class="aside">The documented conclusion is blunt, and worth stating plainly: a
thin ribbon's two edges are not really two independent boundaries — they are one
stroke with a centre and a width, and none of the general-purpose fixes applied to
"two independent edges" could substitute for modelling it that way. The fix the
source code names is in how a thin shape is represented: as a centre line and a
width. For a while, the pixels where a ribbon's two edges compete were simply left
out of the comparison, like the pixels where boundaries meet. Once the solver was
made to finish its work properly (below), leaving them out turned from a help into
a harm: on a stroke two pixels wide those are nearly all the pixels it has. They are
counted again now; the smoothness preference and the knot check below are what keep
the two edges apart.</div>
</section>
<section>
<h2>A safety catch: never let the fix tie the boundary in a knot</h2>
<p>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.</p>
<p>So after solving, the stage checks whether it introduced any <em>new</em>
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 <em>whole picture</em> back for a single
crossing anywhere, and on some icons that threw away nearly all of the work.</p>
</section>
<section>
<h2>How long to keep solving</h2>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
</section>
<section>
<h2>When a picture is too busy to solve</h2>
<p>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.</p>
<p>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.</p>
<p>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.</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">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" aria-current="page">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>