projective-grid 0.8.0

Generic 2D projective grid graph construction, traversal, and homography tools
Documentation 
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

# projective-grid

Pattern-agnostic algorithms for turning a 2D point cloud into a labelled
grid: seed-and-grow BFS, boundary extension via fitted homography,
post-grow validation, per-cell rectification.

`projective-grid` is the algorithmic backbone behind every grid-based
detector in the [calib-targets] workspace — chessboard, ChArUco, marker
board, PuzzleBoard — but has no calibration-specific dependencies.

Full API reference: see the [`projective-grid` book chapter][book-chapter].

## Install

```toml
[dependencies]
projective-grid = "0.8"
nalgebra = "0.34"
```

## Pipeline at a glance

`projective-grid` ships two grid-construction pipelines that produce
the same `(i, j) → corner_idx` map and share the same downstream
validation, rectification, and component-merge machinery. Pattern-
specific gates (parity, axis-cluster, marker rules, …) plug into the
[`square::grow::GrowValidator`] trait; the geometric machinery
underneath is generic.

### Square seed-and-grow (default)

```rust
use projective_grid::square::{
    grow::{bfs_grow, GrowParams, GrowValidator, Seed},
    extension::{extend_via_global_homography, ExtensionParams},
    validate::{validate, LabelledEntry, ValidationParams},
};

// 1. Caller supplies: corner positions, a 2×2 seed quad, a validator
//    that knows the pattern's invariants, and a cell-size estimate.
let positions: Vec<nalgebra::Point2<f32>> = /* … */;
let seed: Seed = /* … */;
let cell_size: f32 = /* … */;
let validator: &impl GrowValidator = /* … */;

// 2. Stage 5: BFS-grow with adaptive local-step prediction.
let mut grow = bfs_grow(&positions, seed, cell_size, &GrowParams::default(), validator);

// 3. Stage 6 (optional): extend the labelled set via a globally-fit
//    homography. Refuses to extrapolate when the H residuals on the
//    BFS-validated set indicate the planar / pinhole assumption is
//    violated (heavy lens distortion, non-planar target).
let _stats = extend_via_global_homography(
    &positions,
    &mut grow,
    cell_size,
    &ExtensionParams::default(),
    validator,
);

// 4. Stage 7: line / local-H residual validation produces a blacklist of
//    outlier corner indices to drop and re-grow.
let entries: Vec<LabelledEntry> = /* (corner_idx, pixel, grid) per labelled */;
let _result = validate(&entries, cell_size, &ValidationParams::default());
```

The chessboard / ChArUco / PuzzleBoard detectors in the workspace
implement their pattern-specific `GrowValidator` and call the same
machinery. Their orchestrators iterate grow + validate with a
blacklist until the labelled set converges, then run boundary
extension, then re-validate.

### Local-homography boundary extension

`square::extension::extend_via_local_homography` is the per-candidate
counterpart to `extend_via_global_homography`. Instead of fitting one
global `H`, it fits a separate `H` from the `K` nearest labelled
corners for each candidate cell. The per-candidate worst-residual
gate tolerates heavy radial distortion and multi-region perspective
where a single `H` breaks. Configured via `LocalExtensionParams`.

### Topological grid finder

`projective_grid::build_grid_topological` is the image-free Shu /
Brunton / Fiala 2009 grid finder: Delaunay triangulation, edge
classification by per-edge axis match, triangle-pair → quad merge,
and flood-fill `(i, j)` labelling.

```rust
use projective_grid::{build_grid_topological, merge_components_local,
    ComponentInput, LocalMergeParams, TopologicalParams};

let params = TopologicalParams::default();
let topo = build_grid_topological(&positions, &axes_hints, &params)?;

// merge_components_local reunites partial components (shared by both pipelines).
let views: Vec<ComponentInput<'_>> = topo.components.iter()
    .map(|c| ComponentInput { labelled: &c.labelled, positions: &positions })
    .collect();
let merged = merge_components_local(&views, &LocalMergeParams::default());
```

See `docs/TOPOLOGICAL_PIPELINE.md` in the workspace for the per-stage
algorithm description and known limitations. The chessboard detector
selects between the two pipelines via
`DetectorParams::graph_build_algorithm`; ChArUco unconditionally
pins seed-and-grow because marker-internal corners poison the per-cell
axis test the topological path relies on.

## Inputs and outputs

| Stage | Input | Output |
|---|---|---|
| Cell-size estimate | `&[Point2<f32>]` | [`GlobalStepEstimate`] (`cell_size`, `confidence`, …) |
| Local-step refinement | per-corner positions + axes | `Vec<LocalStep<F>>` (for `square_find_inconsistent_corners_step_aware`) |
| Seed primitives | corner positions + quad indices | [`SeedOutput`] (`seed`, `cell_size`) |
| BFS-grow | positions + seed + validator + [`GrowParams`] | [`GrowResult`] (`labelled`, `holes`, `ambiguous`) |
| Boundary extension | positions + `GrowResult` + validator + [`ExtensionParams`] | [`ExtensionStats`] (residuals, attached, rejection counters) |
| Validation | labelled corners + [`ValidationParams`] | [`ValidationResult`] (blacklist + per-corner local-H residuals) |
| Rectification | labelled corners | [`SquareGridHomography`] (single global) or [`SquareGridHomographyMesh`] (per-cell) |

All public types re-exported at the crate root; the detailed module
layout sits under [`square`] and [`hex`].

## Configuration

Tuning knobs cluster into three groups. Defaults are chosen so that clean
synthetic grids "just work"; tune only when a specific input fails.

- **[`GrowParams`]** — `attach_search_rel` (search radius as a fraction
  of `cell_size`), `attach_ambiguity_factor`, and
  `boundary_search_factor` (open up the search when the target is being
  extrapolated outward instead of interpolated between two opposing
  labelled neighbours).
- **[`ExtensionParams`]** — `min_labels_for_h`,
  `max_median_residual_rel` / `max_residual_rel` (residual gate on the
  globally-fit H over the BFS-validated set), `search_rel`,
  `ambiguity_factor`, `max_iters`.
- **[`ValidationParams`]** — line-collinearity (`line_tol_rel`,
  `line_min_members`) and local-H (`local_h_tol_rel`) residual
  thresholds for the post-grow cleanup.

## Limitations

- **2D only.** Coordinates are `nalgebra::Point2<f32>`; no 3D support.
- **Roughly-square cells.** Strongly anisotropic aspect ratios (>3:1)
  degrade the local-step prediction; rescale the input cloud first.
- **Hex grids: geometry only.** `hex` ships D6 alignment + per-cell
  homography mesh + smoothness, but not seed-and-grow yet.
- **Heavy radial distortion.** A single global H can't fit fish-eye
  data; the H-residual gate refuses to extrapolate in that case
  (Stage 6 becomes a no-op). Use [`SquareGridHomographyMesh`] for per-cell
  rectification.

## Design notes

- **Local invariants, not global homography**, in BFS-grow: each step
  reasons about a target and its nearest neighbours, which is
  affine-locally valid even under moderate perspective. Per-neighbour
  finite-difference local-step prediction handles foreshortening as
  long as the labelled set has labels on both sides of the target.
- **Global H at the boundary.** When the target sits one step outside
  the labelled bbox, the local-step model is asymmetric and overshoots.
  Stage 6 falls back to a globally-fitted homography for boundary
  cells, gated on a reprojection-residual check on the labelled set so
  it disables itself under non-planar / fish-eye conditions.
- **Undirected-angle circular means.** Any function averaging axis
  angles accumulates `(cos 2θ, sin 2θ)` and halves the resulting
  `atan2` — naive `(cos θ, sin θ)` averaging breaks at the 0°/180°
  seam. See [`circular_stats::refine_2means_double_angle`].
- **Plateau-aware peak picking.** When a physical direction's mass
  straddles a histogram-bin boundary, the smoothed peak is flat-topped
  across two adjacent bins. [`circular_stats::pick_two_peaks`] detects
  the plateau midpoint so axis estimates stay stable as input rotates.

## Related crates

- [calib-targets-chessboard][] — the reference consumer: invariant-first
  chessboard detector.
- [calib-targets-puzzleboard][] — self-identifying chessboard variant.
- [calib-targets][] — workspace facade with `detect_*` / `detect_*_best`.

[calib-targets]: https://docs.rs/calib-targets
[calib-targets-chessboard]: https://docs.rs/calib-targets-chessboard
[calib-targets-puzzleboard]: https://docs.rs/calib-targets-puzzleboard
[book-chapter]: https://vitalyvorobyev.github.io/calib-targets-rs/projective_grid.html