16-Sector Coding & Codebook

Each ringgrid marker carries a unique identity encoded as a binary pattern in the annular code band between its inner and outer rings. The code band is divided into 16 equal angular sectors, each rendered as either black or white, forming a 16-bit codeword. The detector ships with a stable 893-codeword baseline profile and an opt-in extended profile for larger ID spaces, while still handling unknown orientation through cyclic matching.

Sector layout

The code band is the annular region between the inner and outer dark ring bands. It is divided into 16 sectors of equal angular extent (22.5 degrees each), numbered 0 through 15 proceeding counterclockwise. Each sector is filled with either a dark (0) or light (1) value, producing a 16-bit binary word.

Because the marker can appear at any in-plane rotation in the image, the absolute angular reference of sector 0 is unknown at detection time. The codebook matching algorithm handles this by trying all 16 cyclic rotations (see below).

The codebook

ringgrid embeds two related profiles:

Key codebook properties:

The baseline minimum cyclic Hamming distance of 2 means that for any two distinct baseline codewords A and B, the Hamming distance between A and every cyclic rotation of B is at least 2. This guarantees that a single-bit error will not silently produce a different valid baseline codeword, though it is not sufficient for guaranteed single-bit error correction (which would require a minimum distance of 3).

The extended profile keeps the same baseline prefix but appends the remaining rotationally unique 16-bit words whose complement classes are not already claimed by the shipped profile. That expands capacity substantially without introducing new polarity ambiguity beyond the fixed baseline, but still lowers the minimum cyclic Hamming distance to 1 and therefore weakens the baseline profile’s ambiguity guarantee. This is why extended is explicit opt-in.

Additional constraints enforced during codebook generation:

• No rotational symmetry: no codeword equals any of its own non-trivial cyclic rotations. This ensures that each physical marker has a unique observed pattern regardless of orientation.
• Pairwise uniqueness under rotation: no two distinct codewords share any cyclic rotation, preventing ambiguous matches.

The codebook is embedded as a compile-time constant array in crates/ringgrid/src/marker/codebook.rs:

#![allow(unused)]
fn main() {
pub const CODEBOOK_BITS: usize = 16;
pub const CODEBOOK_N: usize = 893;
pub const CODEBOOK_MIN_CYCLIC_DIST: usize = 2;
pub const CODEBOOK_SEED: u64 = 1;
pub const CODEBOOK_EXTENDED_N: usize = 2180;
pub const CODEBOOK_EXTENDED_MIN_CYCLIC_DIST: usize = 1;

pub const CODEBOOK: [u16; 893] = [
    0x035D, 0x1F95, 0x0B1D, /* ... */
];

pub const CODEBOOK_EXTENDED: [u16; 2180] = [
    0x035D, 0x1F95, 0x0B1D, /* ... */
];
}

This file is generated by tools/gen_codebook.py and should never be edited by hand. To regenerate:

python3 tools/gen_codebook.py \
    --n 893 --seed 1 \
    --out_json tools/codebook.json \
    --out_rs crates/ringgrid/src/marker/codebook.rs
cargo build  # rebuild after regenerating

Decoding process

The detector decodes a marker’s identity after fitting its outer ellipse. The process has four stages: sampling, thresholding, binarization, and codebook matching.

1. Sampling sector intensities

For each of the 16 sectors, the detector samples pixel intensities at multiple points within the code band. Sampling is controlled by DecodeConfig:

#![allow(unused)]
fn main() {
pub struct DecodeConfig {
    /// Embedded codebook profile.
    pub codebook_profile: CodebookProfile, // default: base
    /// Ratio of code band center radius to outer ellipse semi-major axis.
    pub code_band_ratio: f32,        // default: 0.76
    /// Number of angular samples per sector.
    pub samples_per_sector: usize,   // default: 5
    /// Number of radial rings to sample.
    pub n_radial_rings: usize,       // default: 3
    /// Maximum Hamming distance for a valid decode.
    pub max_decode_dist: u8,         // default: 3
    /// Minimum confidence for a valid decode.
    pub min_decode_confidence: f32,  // default: 0.30
    /// Minimum Hamming margin for a valid decode.
    pub min_decode_margin: u8,       // default: 1
}
}

The sampling radius is code_band_ratio * r_mean, where r_mean is the mean semi-axis of the fitted outer ellipse. Multiple angular samples per sector (spaced evenly within the sector) and multiple radial rings (spanning +/-10% of the center ratio) provide robustness against localized noise.

The mean semi-axis is used rather than the ellipse angle because the ellipse angle reflects perspective distortion of the circular marker, not the board-to-image rotation. Sector angular alignment is handled entirely by the cyclic rotation matching.

Each sector’s intensity is the average of all valid samples (those falling within image bounds).

2. Thresholding

The sampled intensities are binarized using an iterative 2-means clustering algorithm:

1. Initialize the threshold at the midpoint of the intensity range.
2. Split sectors into two groups (above and below threshold).
3. Recompute the threshold as the midpoint of the two group means.
4. Repeat until convergence (up to 10 iterations).

A minimum contrast check rejects markers where the intensity range is too narrow (less than 0.03 on a [0, 1] scale), which would indicate a featureless or uniform code band.

3. Binarization

Each sector with intensity above the threshold is assigned bit 1; below gets bit 0. This produces a 16-bit observed word.

4. Codebook matching

The observed word is matched against the selected embedded profile. For each codeword, all 16 cyclic rotations are tried, and the Hamming distance is computed for each:

distance = popcount(observed_word XOR rotate(codeword, k))

The match with the smallest Hamming distance wins. If the best match has a high distance or low confidence, the detector also tries the inverted polarity (!observed_word), which handles the case where marker contrast is reversed (dark-on-light vs. light-on-dark).

The better of the normal and inverted matches is selected based on the confidence heuristic:

confidence = clamp(1 - dist/6) * clamp(margin / active_profile_min_cyclic_dist)

where margin = second_best_dist - best_dist. In the shipped baseline profile, active_profile_min_cyclic_dist = 2, so a perfect decode with margin 2 or greater scores 1.0. In the opt-in extended profile that denominator is 1, which makes exact matches easier to accept but reflects the profile’s weaker minimum-distance guarantee. High confidence still requires both a low distance to the best match and a comfortable gap to the runner-up.

A decode is accepted only if:

• best_dist <= max_decode_dist (default: 3)
• margin >= min_decode_margin (default: 1)
• confidence >= min_decode_confidence (default: 0.30)

The generator preserves the committed baseline profile as the fixed prefix, then appends the remaining valid rotational equivalence classes whose complement classes are not already claimed by the shipped profile to form the extended profile. For the committed --n 893 --seed 1 artifacts:

• baseline minimum cyclic Hamming distance: 2
• extended minimum cyclic Hamming distance: 1

Decode metrics

Every decode attempt produces a DecodeMetrics record with full diagnostic information:

#![allow(unused)]
fn main() {
pub struct DecodeMetrics {
    /// Raw 16-bit word sampled from the code band.
    pub observed_word: u16,
    /// Best-matching codebook entry index.
    pub best_id: usize,
    /// Cyclic rotation that produced the best match.
    pub best_rotation: u8,
    /// Hamming distance to the best-matching codeword.
    pub best_dist: u8,
    /// Margin: second_best_dist - best_dist.
    pub margin: u8,
    /// Confidence heuristic in [0, 1].
    pub decode_confidence: f32,
}
}

The margin field is particularly useful for assessing decode reliability. A margin of 0 means the best and second-best matches are equally close – the decode is ambiguous. Higher margins indicate increasingly unambiguous matches.

Cyclic matching in detail

Because a marker can appear at any in-plane rotation, the detector does not know which physical sector corresponds to bit 0 of the codeword. The cyclic matching algorithm compensates by testing all 16 rotational alignments:

#![allow(unused)]
fn main() {
pub fn rotate_left_16(word: u16, k: u32) -> u16 {
    word.rotate_left(k % 16)
}
}

For each codeword in the codebook, the matcher rotates the codeword by 0, 1, 2, …, 15 positions and computes the Hamming distance to the observed word at each offset. The rotation that produces the minimum distance is recorded as best_rotation.

This design means the detector never needs to determine the marker’s orientation independently – rotation recovery is a free byproduct of the codebook match.

Polarity fallback

In some imaging conditions the marker contrast may be inverted relative to the expected dark-ring-on-light-background convention. Rather than requiring a fixed polarity, the decoder tries both:

1. Match observed_word against the codebook (normal polarity).
2. Match !observed_word (bitwise complement) against the codebook (inverted polarity).
3. Select whichever match yields higher confidence.

The appended profile entries exclude new complement-equivalent duplicates, so enabling extended does not widen the baseline profile’s existing polarity ambiguity.

The DecodeDiagnostics struct records whether the inverted polarity was used via the inverted_used flag.