Realtime Multi-Barcode Tracking

Part III — many barcodes, and live frames

Part I established the geometry: a circular barcode reads the same along any chord through its centre, so a 2D pose problem becomes a 1D pattern match on a single row of pixels. Part II built the matcher: scan-line edges relate to template positions by a Möbius transform — the exact 1D projective map — recovered automatically from an anchor search, a DP alignment, and a least-squares refit.

Part II finds one barcode, on one row, of a simulated frame. This notebook removes all three limits:

1. One barcode → many. The anchor search already works on contiguous runs of scan edges, so a barcode is a local phenomenon. Detection becomes: keep every candidate that survives a residual test, then suppress overlaps.
2. One row → a row set. A chord only reads the template pattern if it passes near the centre. With several barcodes no single row centres them all, so we scan a strided set of rows and let the residual pick the best row per barcode.
3. Simulated → live. A webcam supplies real optics, noise and motion blur. It is not the speed target — there is no scan-line access to a webcam. It is a realism test for the algorithm.

The endgame is still a sensor streaming one row at a time at kHz rates, so the figure of merit is not frames per second. It is rows touched per detection and microseconds per row. Both stay on screen throughout.

§1 A scene with several barcodes

Part I's simulator renders one textured cube and lets you orbit it. Here we want several barcodes at independent poses, because that is what forces every remaining problem in this notebook: overlapping edge runs, barcodes at different scales, and — most importantly — the fact that no single scan row passes through all their centres.

The barcode texture is Part I's synthetic cell: concentric rings drawn straight from the 56-bit template, so the simulated target and the matcher's template are guaranteed to agree by construction.

§2 Which rows to scan

Part II assumed the scan line passes through the barcode's centre. That assumption is load-bearing: a chord at perpendicular distance d from the centre cuts a ring of radius r at ±√(r² − d²), so an off-centre chord reads a compressed pattern that is no longer the template. With one barcode you can hunt for the right row. With several, no single row centres them all.

The cheap fix, and the one that keeps the scan-line thesis intact, is to scan a strided set of rows and let the residual decide. Each barcode is then near-centred on at least one row, provided the stride is smaller than the barcode's radius. Nothing else in the pipeline changes, and the cost is exactly linear in rows touched — the quantity we care about.

(§7 revisits this with the proper generalisation: put d into the model so any row works.)

§3 Replacing the anchor SVD with a cross-ratio test

Part II's computeAnchorCandidatesFast is the inner loop of the whole system. For every contiguous window of scan edges (i, j) whose edge count is plausible, it takes four correspondences — the two outermost template edges and the two next-innermost — fits a Möbius transform by SVD least-squares, and scores the window by the residual.

That is doing a lot of work to learn one number. A Möbius map

has four parameters defined up to scale, so three degrees of freedom. Four correspondences impose four constraints. The fit therefore has exactly one excess constraint, and the SVD residual on those same four points is measuring precisely that one scalar.

That scalar has a name. The cross ratio of four collinear points is the complete projective invariant of the configuration — unchanged by any Möbius map:

So a window admits a Möbius map onto the template anchors if and only if its cross ratio equals the template's. We compute the template's cross ratio once, reject windows with a handful of floating-point operations, and run the SVD only on survivors.

This is not an approximation of Part II's test — it is the same test, evaluated directly instead of via a matrix decomposition.

What the benchmark actually showed

The first version of this gate rejected 0% of windows and bought a 1.5× speedup that was pure noise. The reason turned out to be a property of Part II's anchor choice, not of the idea.

Part II anchors on (kMin, kLeftInner, kRightInner, kMax) — but kLeftInner is one step from kMin, and kRightInner is one step from kMax. Two tightly-spaced pairs, far apart. The cross ratio of such a configuration is

which is a hair from 1 — one of the three degenerate values of the cross ratio. Every window whose first two edges are close together and whose last two edges are close together lands in the same place, so the invariant carries almost no information. Part II's SVD residual on those four points was measuring a quantity that barely varies.

Moving the two inner anchors to the thirds of the template fixes it: $\mathrm{CR}(-27,\,-13,\,13,\,27) = 1.1396$, far enough from 1 to discriminate. With ground truth from the simulator, the three genuinely centre-crossing rows score cross-ratio distances of 0.005, 0.008 and 0.009 — all well inside a 0.02 tolerance — while two thirds of all windows are rejected outright.

The same spread anchors also give a better-conditioned initial Möbius fit than four points bunched at the interval ends, so the change pays twice.

The topWindowAgreement figure above is no longer a meaningful check: the windows the two methods now disagree on are mostly off-centre rows where Part II returns a spurious fit. §5 replaces it with a precision/recall measurement against ground truth.

§4 From one detection to many

Part II ends with refineAnchorCandidates(...)[0] — it takes the single best window and discards the rest. But the candidate list is already a ranked set of disjoint or overlapping edge-index intervals, and a second barcode on the same row is simply another interval further along. Nothing about the search needs to change.

So multi-instance detection is three rules applied to the ranked list:

1. Accept a candidate only if its full-template residual is small enough and it matched enough template edges (occlusion and blur drop some, so this is a fraction, not equality).
2. Suppress any candidate whose edge-index interval overlaps one already accepted — the classic non-max suppression, made cheap here because a barcode occupies a contiguous run of scan edges.
3. Report the centre, which the fit hands us for free: binaryToEdges centres the template on zero, so the barcode's centre in the image is exactly $x = \texttt{xFromK}(\text{mobius},\, 0)$.

That last point is worth dwelling on. We are not estimating the centre from the extent of the detection — we are reading it off the recovered projective map, which is what makes it sub-pixel-capable and robust to a partially occluded rim.

§5 Putting the chord offset into the model

Everything so far inherits Part II's assumption that the scan line passes through the barcode's centre. §2 worked around it by scanning many rows and letting the residual pick the best one. That is a workaround: it quantises the answer to the row grid, and it throws away every row that nearly hit the centre.

The honest fix is to admit that the chord is offset and put that in the model.

Write $k$ for a template edge — and note that in Part II's coordinates $|k|$ is the ring radius, because binaryToEdges centres the template on zero. A chord at perpendicular distance $d$ from the centre meets the ring of radius $|k|$ at

and misses it entirely when $|k| \le |d|$. So an off-centre chord does two things at once: it compresses the pattern toward the ends, and it drops the innermost rings. The second effect is the more useful one — the number of surviving rings is itself a strong function of $d$.

This is a one-parameter family of templates, so the fit gains a fourth unknown alongside the three Möbius degrees of freedom. Two consequences:

• The map from chord to image is still an exact Möbius transform. The offset changes the template, not the projection. So all of Part II's machinery applies unchanged to $k_{\text{eff}}$ — this is a change of input, not of algorithm.
• $d$ enters only as $d^{2}$, so a single chord can never tell you which side of the centre it passed. That sign ambiguity is what §6 resolves by combining rows.

What the offset model bought, and what it cost

Putting $d$ into the search — a coarse sweep over offsets at detection time, then a local refinement — changed the numbers on the static test frame like this:

The recovered offset tracks the truth closely over most of each barcode. For the mid-sized target the fitted $d$ runs 16.7, 10.7, 4.7, 1.3, 7.3, 19.3 against a true 16.8, 10.8, 4.8, 1.2, 7.2, 19.1 as the rows sweep down through it — including the turning point, which is the centre. Errors are mostly under 0.2 template units.

Three findings worth recording, two of them mistakes:

The rim edge was missing from the template. binaryToEdges only reports transitions inside the ring array, so the disk's outer boundary against the background — the highest-contrast edge in the whole image — was absent. Every candidate offset was therefore charged for two scan edges it could never explain, which biased the search low: one row fitted $d = 4.25$ where the truth was $6.13$. Adding $\pm N/2$ to the template fixed that row to $6.30$, and as a side effect lifted the cross-ratio gate's rejection rate from 66.7% to 82.6%.

A fitted Möbius map cannot be carried between offsets. The first refinement re-used the coarse fit's map as the initialiser at every $d$. But that map is expressed in the effective coordinate $k_{\text{eff}}$ of the offset it was fitted at, so at a different offset the projection lands far enough away that the least-squares refit goes degenerate — image residuals of 15 to 24 pixels, and two confident detections at the left edge of a frame that contained nothing there. Re-deriving the initial map per offset from the window's own anchors removed both phantoms and found the third barcode.

There is a genuine ambiguity at the resolution limit. The smallest barcode packs 56 rings into a 32 px radius, so its inner rings are not resolved by the edge detector at all. The detector cannot distinguish "the chord missed those rings" from "the camera cannot see those rings" — both predict the same missing edges. That is why its offsets are the worst in the table (one row fits $d = 12$ where the truth is $0.63$) even though its centre is still located to within a pixel or so. The fix is not a better search: it is to make the model resolution-aware, so a missing ring only counts as evidence for an offset when the ring would have been resolvable.

§6 Making it fast enough to mean something

Putting the offset in the search cost 8 ms → 63 ms per frame. Before optimising anything, here is where that time actually went, measured over one frame of 40 rows:

So ~90% of the frame is the DP alignment and its least-squares refit, at about 61 µs per candidate. The cross-ratio work from §3 is already down in the noise — optimising it further would have been chasing the wrong number, which is exactly why it was worth profiling first.

Reading Part II's dpAlign shows why it is slow, and none of the reasons are the algorithm:

• matchCost is a callback invoked per DP cell, and getX/getS run typeof plus the in operator per cell — roughly 1 700 cells per candidate.
• Two typed arrays are allocated per call (~16 KB), so ~8 MB of garbage per frame.
• The backtrace builds a seven-field object per aligned pair, then reverses the array — but refineAnchorCandidates only ever reads templateToScan.

dpAlignFast fixes all three: scratch buffers reused across candidates, the cost inlined, and only an Int32Array of scan indices emitted. Part II's original stays imported as the oracle, and refineOracleCheck runs both over every row and every coarse offset of the benchmark frame: 51 of 51 windows identical, zero difference in either residual. Same answers, 63 ms → 15 ms.

The refit that looked like a free win and was not

fitMobiusLS runs a full SVD per candidate to solve what, once the scale is fixed at s = 1, is a 3×3 normal-equation system. fitMobius3 does that in closed form, and on 500 synthetic noise-free fits it matched the truth to ~1e-12 while the SVD blew up on 2.4% of cases. That looked conclusive. It was not — noise-free data has an exact solution, which is the one regime where the two objectives agree.

They are not the same objective. The SVD takes the unit-norm null vector of [x, 1, −kx, −k], minimising an algebraic residual over all four parameters — total least squares, which treats error in x and in k symmetrically. Pinning s = 1 and solving normal equations minimises the k-residual only. On real scan edges, with mismatched and missing rings, they land in different places — and each one looks better when scored by its own residual, so no comparison of kRMSE against kRMSE can settle it.

The cell below settles it the only way that is not self-referential: run the whole pipeline under each solver and score against the simulator's ground truth.

The closed form is nearly twice as fast and its matched rows are more precise — but it finds one barcode fewer and invents five false detections at the left frame edge. Recall and precision are what the detector is for, so the SVD stays, and the speedup is taken entirely from the DP. That is still a 4× frame, with output identical to Part II's to the last bit.

While reading dpAlign I found a latent bug worth reporting upstream. getS returns the value itself when the input is a plain number, so for the numeric arrays refineAnchorCandidates passes it, a point's position is used as its polarity, and Math.sign(st) !== Math.sign(ss) fires on any pair straddling the origin. It is harmless today only because refineAnchorCandidates hard-codes polarityPenalty: 0.

§7 From rows to a centre

Everything so far is per-row. A row hit gives two numbers: footX, the image x of the foot of the perpendicular from the barcode centre onto that scan line, and d, the perpendicular distance from the centre to that line — but in template units, and only its magnitude. §5 showed why the sign is gone: the chord meets the ring of radius k at ±sqrt(k² − d²), and only d² appears, so one chord cannot tell above from below.

Stack the rows and it comes back. If the centre is at image row y_c and the barcode images at s pixels per template unit vertically, then every row obeys

which is a V in (y, d) — and the rows above the centre sit on one arm, the rows below on the other. Two unknowns, one equation per row, so three rows already over-determine it, and the sign ambiguity is resolved by the fit rather than assumed away.

The V is only piecewise linear, but it is linear once you commit to which rows are above the centre. Sort by y and there are just n+1 such splits, each an exact two-parameter least squares — no search, no initialisation, no local minima. Take the split with the lowest residual that is self-consistent.

s is not a nuisance parameter, it is the second thing you wanted: pixels per template unit is apparent size, and apparent size is range.

For x, footX is very nearly constant down a barcode, but not exactly — under tilt it drifts a little with y. So fit a line through footX against y and read it at y_c rather than averaging.

What the V bought, and what it did not

Fusing rows is worth more than it looks. The per-row x readings scatter by 1.372 px rms; the fused centres sit 0.34 px in x and 0.26 px in y from truth, and the apparent radius comes out at 56.00 px against a true 56.10 — from scan lines 12 px apart. Sub-pixel in both axes, from a detector that only ever looked at 8% of the rows.

Two honest qualifications.

The zero residual is quantisation, not perfection. refineOffset sweeps d on a fixed grid, so the fitted offsets land on multiples of ⅔ of a template unit. For the large barcode the true V happens to pass exactly through those grid points, and the residual collapses to 1e-14. That is the discretisation agreeing with itself. The residual is a useful outlier detector — it is what catches the bad row — but it is not a measure of absolute accuracy. The ground-truth columns are.

One bad row costs several pixels. Row y=270 fits d=18.67 where the truth is 13.15, and it drags the whole V: without the robust pass the radius comes out 4.4 px short and y_c is 1.5 px off. The first cut is computed against a fit that the outlier has already contaminated, so it also rejects a good row (y=282, whose own d was accurate to 0.19). Re-selecting from all rows against each refit vindicates that row on the next pass — which is why the loop reconsiders every row rather than only the survivors.

The third barcode is still missing. It survives detection on only two rows, and two points cannot pin a V that has two parameters — minRows is 3. This is the same resolution limit as §5: 56 rings inside a 32 px radius, where "the chord missed those rings" and "the camera cannot resolve those rings" predict identical evidence. More scan rows would fix it; a better search would not.

And the shape estimate is deliberately one-sided. The V measures the vertical scale, because horizontal scan lines only ever sample vertical offsets. Nothing here recovers the horizontal extent, so nothing here recovers tilt — the crosshair is drawn with a vertical extent bar and no ellipse, because an ellipse would be claiming more than was measured. That is what a vertical scan pass is for.

§8 Real pixels

Everything up to here ran on a simulator, which is what made the numbers meaningful: every claim in §4–§7 is checked against a pose the renderer actually used. A camera has no ground truth, so this section proves something different — that the detector works on pixels nobody generated for it. Real optics, real noise, real motion blur, real rolling shutter.

It is not a speed test. A webcam hands over whole frames, so reading 40 rows out of one costs exactly as much as reading all 480 — the saving this whole line of work is built on only materialises when the sensor can be told which rows to read out. The figure to watch is still rows touched and µs per row, not frames per second. What the camera tests is whether the 1D matcher survives contact with a real image.

Nothing below requests the camera until you turn it on.

Turn the camera on and point it at barcodeTarget above — on a second screen, a phone, or printed. The overlay is the same three layers as the simulator: faint red scan rows, amber per-row fits with a ring on the foot of each perpendicular, and a violet crosshair with a vertical extent bar wherever three or more rows fuse into a centre.

Nothing about the detector changed for this section. runPipeline takes a frame, and a frame is {gray, w, h} — the camera path just fills that shape from getImageData instead of from WebGL. The same clusterHits and fuseCluster from §7 run on the result.

Two things to expect that the simulator never showed. The rings are painted with hard black-and-white edges, so a real lens and a real sensor will soften them; if rowHits stays at zero, edgeThreshold is the first knob to reach for, not the matcher. And the barcode has to be large enough in frame — the §5 resolution limit is not a simulation artifact, and a barcode 60 px across on a webcam is the same 56-rings-in-30-pixels problem that lost the third barcode in §7.

What the camera actually did

First run against a real lens, handheld, barcode shown on a second screen — 354 frames:

Three things are worth reading off that.

The detector survives contact with real optics without a single parameter changed from the simulator — same edgeThreshold, same crTol, same maxRMSE. A 94% frame hit rate handheld is not a marginal result.

The cross-ratio pre-filter works harder on camera than on synthetic frames — 90.7% of windows rejected versus 82.6% in §3. Real images produce far more spurious edges, so there are many more windows to reject, and almost all of them fail an invariant that costs four subtractions to check. That is exactly the shape of thing you want in front of an expensive matcher.

And the frame is 3 ms rather than the simulator's 15, because so little survives to reach the DP. The per-row cost is what to quote — 75 µs, against 40 rows — since that is the number that would still hold if the sensor handed over only those rows.

The fit residuals are honest about the change of régime: the fused centres came back with yResidual of 4.9 and 7.6 px, against 0.56 in simulation. Nothing here has ground truth, so those residuals are the only quality signal available — and unlike §7 they cannot be checked against a known pose. The two centres in the best frame have apparent radii of 126 px and 21 px, so at most one of them is the barcode that was actually being held up. Without ground truth this section can demonstrate that the pipeline runs and locks on; it cannot certify what it locked on to. That is the price of leaving the simulator, and it is why §4–§7 were measured before this section existed.