Fast Multi-Target Circular Barcode Pose Tracking

About

Part V of a super long [younger me, 2012] and infrequently worked on project for fast optical localization. In this installment I added

• Detect multiple circular barcodes in the scene
• Decode them so each has an unambiguous code for matching
• Compile into WASM via AssemblyScript for fast performance
• Use Web Workers for parallelism
• Fuse multiple barcodes to get a pose

Less than 2ms per frame on MacBook, 16ms on phone 🤙 which is complete overkill for the browser as both max out at 30 f.p.s. for webcams, however, the long term aim is for hardware.

There are lots of optical tracking systems, including circular barcodes. The unique thing about this one is the design around single scan lines, so barcodes can be recognized with appropriate hardware as pixels leave the camera's MIPI. This is potentially hundreds of times faster than the frames per second rating of a camera.

This lets you run the barcode matcher a few ways

• wave your mobile displaying the pattern §2 in front of your webcam on a laptop running this notebook
• print out the pattern §2 on paper and track with this notebook on your mobile
• connect Claude Code to the notebook live on your laptop and let it drive and take measurements (also /remote-control from Claude Code from mobile)
• download the notebook as a single file and let Claude Code choose how to edit and run it

The barcode is designed so it is easy to recognize and localize from a single scan line of pixels. The encoding gives it a label and edges for sharp positioning.

A scan row goes through each ring twice. Once on the way into the centre, and once out. The order is symmetric. So there is a match for each edge crossing across a mirror down the middle: an involution (a function that is its own inverse).

Once you adjust for the perspective (Möbius transform, Part III), those pairs are on a straight line defining the tilt angle of the scanline relative to the camera.

One scanline is enough to determine 3 of the 6 position/orientation degrees of freedom for the barcode in 3D space.

The first step towards pose retrieval is edge detection

Adjacent parallel scanlines can be joined if their P are close

A lock joins the nearest open cluster whose last row is within 4 · stride above it and whose last P is within max(10px, 0.35 · wHalf) — the window drawn on the figure below — and otherwise opens its own. The match is on P and never on the decoded id, because rows that locate but fail to decode are exactly what the ellipse fit is made of.

A cluster becomes a barcode on three independent things: at least 3 rows, an id with at least 2 votes that beats the runner-up 2:1, and a pose fitManPose calls plausible. Clutter reliably produces one of the three and rarely two. If two clusters claim the same id the better-evidenced one keeps it, on rows, then vote margin, then coverage, so one id stays one piece of paper.

A row scan measures a barcode's x and extrapolates its y, and a column scan of the same frame inverts that. Both cost two scans, both run on the worker pool, and they often disagree on the centre. They have to decode the same id to be paired at all, so all the merge has to do is choose: it takes the column pass's y unless the row pass decoded with a strictly larger vote margin.

Summed absolute y error over the 37 barcodes the bank fuses from both passes, against an oracle that reads the frozen label and always picks the closer pass:

Blue reads the answer key, so it is a floor and not a rule. Green is what ships, and it closes 87% of the distance to that floor from the better fixed pass. The two greys below it are rules that were tried.

As the barcodes have labels the hexagonal grid of 7 barcodes can be trivially fitted allowing more spatial fusion for pose estimation in 6 DOF space.

As each barcode fit also carries the local scale a and b, only two barcodes are needed to determine a plane, and the live pose fits with them.

asc 0.28.20 · compiled in 166ms

Byte for byte identical to the binary saved in this file — 6883 bytes.

The bank's reference labels (§3.1) are computed from a slower, more accurate offline procedure: row stride 1 instead of 4, a sweep over the edge threshold, and a sub-pixel refinement stage.

1. The edge threshold is chosen per frame.
2. Every centre is refined on its own ring lattice.
3. The plane is fitted by exhaustive RANSAC over the 4-subsets.
4. The plane may flag a measurement, but not replace one.

For lattice refinement, all edges of the barcode, through every scan line, in 12 directions are used to fit a perspective distorted concentric ring model, with an ink bleed parameter.

Fit the whole set at once:

|A (p − c)| = teeth[t] + δ · polarity

c is the centre in the image, A the inverse of the local plane-to-image map, and δ a single ink-bleed offset. Seven parameters against thousands of observations.

δ is identifiable. Thickening the ink moves a dark→light boundary outward and a light→dark boundary inward. The involution pairs require ss[f] === -ss[e], so both edges of a pair take the same signed shift, and consecutive teeth alternate polarity. Across the bank, ink bleed fits 0.06mm.

An affine A is not enough. Under a homography concentric circles map to ellipses that are not concentric: the imaged ellipse of a ring drifts toward the vanishing point as the ring grows. An affine fit has no term for that, so on a tilted sheet it carries a bias. Two additional perspective parameters remove the bias, solved as a second stage after the converged affine fit.

Measured against a synthetic image, adding perspective correction takes the relabelling from a median error of 0.118px to 0.010px, and its worst case from 0.721px to 0.027px.

There is more we can do to improve accuracy in realtime applications e.g. adaptive tuning of the edge detector parameters, or adjustment of scanlines focus across frames. We do not use frame similarity information at all!

My primary next goal however is running faster than 30 frames per second. This does not appear to be easily achieved with browser, so next work will attempt to apply this algorithm to real hardware like the Arducam 100fps Mono Global Shutter USB Camera, 720P OV9281 UVC Webcam Module which has hardware support for changing scan line settings and capture rate.