Metadata-Version: 2.1
Name: visiontrack-cpp
Version: 0.1.0
Summary: A C++ ByteTrack that is bit-for-bit identical to its NumPy reference, and ~70x faster
Keywords: multi-object-tracking,bytetrack,kalman-filter,computer-vision,cpp,pybind11,numerical-reproducibility
Author: Rushikesh Hulage
License: MIT
Classifier: Development Status :: 4 - Beta
Classifier: License :: OSI Approved :: MIT License
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Developers
Classifier: Operating System :: MacOS
Classifier: Operating System :: POSIX :: Linux
Classifier: Operating System :: Microsoft :: Windows
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering :: Image Recognition
Project-URL: Homepage, https://visiontrack.hulage.in
Project-URL: Repository, https://github.com/hulagerushikesh/visiontrack-cpp
Project-URL: Issues, https://github.com/hulagerushikesh/visiontrack-cpp/issues
Project-URL: Reference, https://github.com/hulagerushikesh/visiontrack
Requires-Python: >=3.10
Requires-Dist: numpy>=1.24
Provides-Extra: test
Requires-Dist: pytest>=7.0; extra == "test"
Requires-Dist: visiontrack-mot==0.2.0; extra == "test"
Description-Content-Type: text/markdown

# visiontrack-cpp

An optimized C++ ByteTrack, **parity-gated** against the
[`visiontrack-mot`](https://pypi.org/project/visiontrack-mot/) NumPy reference.

This is a performance-engineering project, not a research one. It answers a
single question: **how fast can an honest ByteTrack go, and what exactly buys
the speed?** The research findings live in the sibling project,
[visiontrack.hulage.in](https://visiontrack.hulage.in).

```bash
pip install visiontrack-cpp
```

![Throughput vs simultaneous objects: the C++ port runs 71-91x faster than the NumPy reference while producing identical trajectories](bench/speedup.svg)

Both halves of that figure come from one script. `bench/compare.py` feeds both
trackers the same detections, compares the full output streams bit-for-bit, and
only then reports a timing — so the speedup is, by construction, a ratio between
two identical computations. It refuses to print a number it has not verified,
and has no flag to skip the check.

## The rule

> The NumPy implementation is the oracle. A faster tracker that changes the
> numbers is worthless.

Parity is proven before any optimization is attempted, so every later speedup is
demonstrably behaviour-preserving rather than hopefully so.

## Why a separate repo

VisionTrack's claim is a from-scratch tracker whose core is readable NumPy. A
C++ core inside that repo would destroy the claim — a reader could no longer
tell which implementation produced a published number. Keeping them apart also
keeps the compiler toolchain, CMake build and platform wheels out of a project
that needs none of them.

Because `visiontrack-mot` is on PyPI, this repo depends on the reference the way
any third party would: a pinned, versioned dependency. The dependency runs one
way and never back.

## Status

**All four phases resolved.** Phases 1, 2 and 4 are complete. **Phase 3 (GPU)
is closed by measurement rather than left blocked**: the only GPU-shaped work
here is gating's `N·M` independent 4×4 solves, and it does not pay. Apple GPUs
have no float64, so a bit-exact Metal path does not exist; and even granting a
float64 GPU, Amdahl caps the win at 1.82× on synthetic scenes while dispatch
overhead exceeds the *entire* gating computation on real ones — MOT17-09's
median frame spends 0.85 µs there. [PHASE3.md](PHASE3.md) has the arithmetic
and [`bench/gpu_feasibility.py`](bench/gpu_feasibility.py) reproduces it.

**Phase 1 — all six milestones done.** Both trackers produce
**identical `(frame, track_id, box, score)` streams** over the full 525 frames of
MOT17-09 on all three detector variants — 7,545 observations, zero divergence —
and identical HOTA/IDF1/CLEAR-MOT to the last bit. Geometry, the Kalman filter
and the solver are bit-identical underneath. Two inexactnesses remain, both
measured and bounded rather than assumed away. 200 tests passing in ~5 seconds.

Run the harness yourself: [`parity/run_parity.py`](parity/run_parity.py), latest
output in [`parity/REPORT.md`](parity/REPORT.md).

| # | milestone | gate | state |
|---|---|---|---|
| 1 | Scaffold: CMake + pybind11 + Eigen | `import visiontrack_cpp` succeeds | ✅ |
| 2 | Geometry (IoU/GIoU, box formats) | unit parity vs NumPy | ✅ |
| 3 | 8-state Kalman filter (Eigen) | unit parity incl. batched gating | ✅ |
| 4 | Hungarian solver | unit parity **and** identical tie-breaking | ✅ |
| 5 | Track FSM + `ByteTracker.update` | trajectory parity, one sequence | ✅ |
| 6 | Parity harness + report | trajectory parity, all MOT17-09 variants | ✅ |

### Parity is not a property of one machine

Bit-exactness is a claim about a compiled binary, so it has to be checked on
every toolchain that compiles one. CI builds twelve wheels and runs the suite
against each, and all twelve agree with the reference exactly:

| platform | compiler | NumPy's LAPACK | NumPy versions | result |
|---|---|---|---|---|
| macOS arm64 | clang | Accelerate | 2.2.6, 2.4.6, 2.5.3 | 190 passed, 0 failed |
| Linux x86_64 | gcc | OpenBLAS | 2.2.6, 2.4.6, 2.5.3 | 190 passed, 0 failed |
| Windows x86_64 | MSVC | OpenBLAS | 2.2.6, 2.4.6, 2.5.3 | 190 passed, 0 failed |

Three compilers, two architectures, and — the part worth pausing on — **two
different LAPACK implementations**. The Kalman gain is solved, not inverted, so
the reference calls `np.linalg.solve` and the C++ calls Eigen. Those agreeing
to the last bit against both Accelerate and OpenBLAS is stronger evidence than
any single platform could give: a solve that merely looked right would not
match two independent LAPACKs.

Every wheel also has to pass [`ci/check_oracle.py`](ci/check_oracle.py) before
its tests run. It refuses to compare against a NumPy that pip built from
source, because such a NumPy links whatever LAPACK the build host had and is
therefore not the reference. That check exists because its absence sent three
CI runs chasing a divergence that was never in the tracker — see
[PHASE4.md](PHASE4.md#the-oracle-has-to-be-the-reference-build).

Milestone 4 was the risky one — see *Tie-breaking* below for what it cost.
Milestone 5 is where the parity gate stopped being a claim and became a result.

## The harness

```bash
python parity/run_parity.py                        # the report, to stdout
python parity/run_parity.py --with-tests --scaling  # + unit parity + throughput sweep
python parity/run_parity.py --markdown parity/REPORT.md --json parity/report.json
```

Exit status is 0 only if every variant reaches trajectory parity, so it drops
into CI unchanged. It needs the MOT17 cache from the sibling `visiontrack`
checkout; point `VISIONTRACK_MOT17_CACHE` elsewhere if yours lives somewhere
else, and it skips cleanly when the cache is absent.

The harness is itself tested — including that it *detects* an injected
one-ULP divergence. A gate that cannot fail proves nothing.

## Install

```bash
pip install visiontrack-cpp
```

Wheels are built for CPython 3.10-3.13 on macOS 11+ arm64, Linux x86_64
(manylinux_2_28, so glibc ≥ 2.28) and Windows x86_64. Anywhere else — Linux
aarch64, an older glibc, a newer Python — pip falls back to the sdist, which
needs a C++17 compiler and CMake ≥ 3.20; Eigen it will fetch itself if the
machine has none.

The Linux floor is glibc 2.28 rather than the older `manylinux2014` because
NumPy ≥ 2.4 requires glibc 2.27 and publishes no `manylinux2014` wheel. On an
older host pip would compile NumPy from source, and a source-built NumPy is
not the reference the parity claim is made against.

### Building from source

```bash
brew install eigen          # optional; see below
pip install -e ".[test]"
pytest
```

Eigen resolution has three steps, in order: an installed Eigen found by CMake
config, then the usual system include paths, then a **pinned** download of
Eigen 3.4.0. Two switches control it:

| flag | effect |
|---|---|
| `-DVT_SYSTEM_EIGEN=OFF` | ignore the installed Eigen and use the pinned one |
| `-DVT_FETCH_EIGEN=OFF` | never download; fail if no Eigen is installed |

The download is pinned rather than floating because Eigen picks different
kernels between versions, and this package's claim is bit-for-bit agreement
with NumPy. A floating dependency would make a wheel's numerics depend on the
day it was built. `VT_SYSTEM_EIGEN=OFF` is what a release wheel wants: it makes
the binary's arithmetic a property of this repo rather than of whatever the
build host had in `/opt/homebrew`.

Parity has been confirmed under **both** Eigen 3.4.0 and 3.5.0 — full suite and
the trajectory gate, same 7,545 observations, zero divergence either way. That
is two data points, not a guarantee for every Eigen version, which is why the
fetch is pinned.

### Checking a build is sound

```python
>>> import visiontrack_cpp as vt
>>> vt.build_info()
{'module_version': '0.1.0', 'eigen_version': '3.5.0',
 'pybind11_version': '3.1', 'cxx_standard': 201703, 'fp_contract_off': True}
```

`fp_contract_off` is the one to read. It is measured against the binary that
was actually built — not read off a macro — and `False` means the compiler
fused a multiply-add somewhere and this build cannot match NumPy. See
*Load-bearing build flags* below for why that is fatal rather than cosmetic.

## The parity gate

Metric-level agreement is **not** the gate. Association is discrete: a 1e-16
difference in one cost entry can flip an assignment, change a track ID, and
cascade through every later frame — while MOTA barely moves. Metric parity would
pass a visibly wrong tracker.

The gate is trajectory-level, in three tiers:

1. **Unit parity** — each ported function vs its NumPy original on randomized
   and degenerate inputs.
2. **Trajectory parity** *(the real gate)* — identical `(frame, track_id, box)`
   streams on MOT17-09, across all three cached detector variants.
3. **Metric parity** — a backstop, scored by the reference's own `eval/` so both
   trackers are measured by the same code.

### Load-bearing build flags

`CMakeLists.txt` sets **`-ffp-contract=off`**. Do not remove it. clang defaults
to `-ffp-contract=fast` at `-O2`/`-O3`, which fuses `a + b*c` into a single FMA
instruction that rounds **once** where NumPy rounds twice. That is a 1-ULP
difference on every height-scaled term of the Kalman process noise. It is
invisible in a single call, compounds over a trajectory, and is exactly the kind
of drift that flips a near-tied association thousands of frames later.

The FMA result is arguably *more accurate*. It is still wrong here: correctness
in this repo means "identical to the oracle", not "closer to the real number".

### The one place parity is not exact

`gating_distance` Cholesky-factorizes the innovation covariance, then calls
`np.linalg.solve` on that factor. Measuring rather than assuming produced two
findings:

- NumPy's `cholesky` is bit-identical to the textbook Cholesky–Banachiewicz
  ordering, so the port uses that instead of Eigen's `LLT`, which rounds
  differently.
- NumPy's `solve` reaches Accelerate's LAPACK, and its output matches **neither**
  a textbook LU with partial pivoting **nor** the reciprocal-scaling variant that
  LAPACK's own reference `dgetf2` describes. Matching it exactly would mean
  reimplementing a specific vendor kernel.

So gating carries a few-ULP residual, asserted at `rtol=1e-14`. The tests also
assert that no track/measurement pair disagrees about passing the chi-square
gate. Whether the residual ever changes a real association is a question only
milestone 5's trajectory parity can answer.

### Trajectory parity — the result

The gate the whole project is built around now passes. Over MOT17-09's full 525
frames, driven by the same cached public detections the reference's own
evaluator uses:

| variant | observations | divergences |
|---|---|---|
| MOT17-09-DPM | 1,162 | 0 |
| MOT17-09-FRCNN | 2,922 | 0 |
| MOT17-09-SDP | 3,461 | 0 |

Identical means identical: same track IDs, same boxes bit-for-bit, same scores,
same frames. Not "within tolerance".

That matters more than the unit tests it rests on, because a tracker is a
feedback loop — its output at frame N is part of its input at frame N+1. One
flipped association does not stay one flipped association; it renames a track
and every later frame inherits the rename. Unit parity cannot see that.

**What this did not prove.** Milestone 3 left `gating_distance` carrying a
few-ULP residual, and stages 1 and 3 compare that value against the chi-square
threshold — so in principle a pair sitting on the threshold could be gated
differently by the two implementations. Trajectory parity passing does not mean
the residual is harmless; it means the residual did not fire on these frames. So
it was measured instead:

| over MOT17-09 | |
|---|---|
| gated pairs evaluated | 57,905 |
| max \|reference − port\| residual | 1.09e-11 |
| closest any pair came to the gate | 7.56e-04 |
| margin ÷ residual, at the worst pair | 2.8e+11 |
| gate decisions that disagreed | 0 |

Eleven orders of magnitude of headroom on this data. That is an empirical
statement about MOT17-09, not a proof — a different sequence could sit closer.
The test asserts a margin of 1e6 residuals rather than merely "no
disagreement", so it fails while there is still room to investigate rather than
after a silent flip.

Because real data never lands on a gate boundary, no trajectory test can reach
that case. The boundary tests construct it directly, one ULP either side of
both gates.

### The other place parity is not exact

`appearance_distance` ends in `tf @ df.T`, which NumPy routes to Accelerate's
BLAS. It is **not** bit-exact — about 1–2 ULP, at every embedding dimension
tested including 4.

This is the exact mirror of the Kalman finding, and the pair is worth stating
together:

- In the Kalman filter, **clang** fused `a + b*c` into an FMA and NumPy did not.
  `-ffp-contract=off` fixed it.
- In appearance, **Accelerate** is the one fusing, and the port cannot follow.

Three candidate explanations were measured against `np.dot` at dimension 4 and
all three were rejected: a naive left-to-right dot product, a pairwise one, and
even an exact-then-round-once chain (a perfect FMA). It is Accelerate's own
blocked kernel — the same dead end as the gating solve.

It is tolerated because `w_app` is `0.0` in every Phase 1 path, so the term
never reaches the solver, and a test pins that default.

### Phase 1 scope guards

`TrackerConfig` accepts `use_gmc`, `use_oru` and `w_ocm` — and **refuses to
build if any of them is enabled**. Those are research extensions the plan leaves
in Python. Accepting them and quietly ignoring them would produce a tracker that
is parity-clean on the default path and silently wrong the moment someone flips
a switch, which is the worst available failure mode for a project whose entire
claim is parity.

### Tie-breaking

When two assignments have equal cost, the *implementation* picks the winner, not
the mathematics. Both solvers minimize the same sum and may legitimately return
different optima. Four behaviours turned out to be load-bearing:

- **The transpose** in `linear_assignment` when `rows > cols`. `>` not `>=`: a
  square matrix is *not* transposed, and transposing changes the scan order.
- **Both tie-break comparisons** are strictly-less, so the lowest column index
  wins. Relaxing either to `<=` still returns an optimal assignment, and a
  different one.
- **The slack expression order**: `cost - u - v`, two left-to-right
  subtractions, not `cost - (u + v)`.

The last one is the interesting one, because it nearly escaped. Regrouping the
slack changed the *values* in 82 of 2400 random matrices but never changed the
answer — it looked cosmetic. A targeted search over mixed magnitudes with
ULP-level ties found that it does flip the assignment, roughly 5 times in 6000.
Those five witnesses are pinned as a regression test.

Every one of these was verified by **mutation**: each behaviour was deliberately
broken and the suite re-run. All four fail loudly (13–16 tests each). A fifth
candidate — splitting the fused `minv`/`delta` scan into two passes — leaves the
suite green, correctly: each `minv[j]` is already final when compared, so the
fused scan yields the same minimum with the same tie-break.

Random float costs almost never tie, so a suite built on them would have passed
all five mutants. The tests are weighted towards degenerate input instead: an
exhaustive sweep of all 512 3×3 binary matrices, all 729 ternary 2×3 and 3×2
matrices, constant and circulant matrices, and saturated `1 - IoU` costs where
most box pairs do not overlap and are therefore tied at exactly 1.0 — which is
what the tracker actually feeds the solver.

When trajectory parity fails, the fix is a frame-indexed diff of the first
divergent assignment — **never** a loosened tolerance.

## Throughput — where the plan was wrong

Phase 1 was supposed to produce no speedup. The plan said so explicitly, and
gave a reason: a naive C++ port of vectorized NumPy is often *slower*, because
"NumPy's inner loops are already compiled BLAS-adjacent code".

Measured, that prediction is wrong by a wide margin — **55–74× on real
sequences, 71–91× across synthetic scenes from 5 to 400 simultaneous objects**
([`bench/BENCHMARK.md`](bench/BENCHMARK.md)).

> **Why this differs from the parity report.** `parity/REPORT.md` puts the real
> sequences at 35–55×, and it is measuring something subtly different: it runs
> both trackers in the *same* loop, one frame at a time, un-warmed and once.
> Sharing a loop with NumPy costs the C++ tracker 21% (9.55 → 11.59 µs on
> MOT17-09-SDP, measured directly) because NumPy's allocations evict its
> working set between calls — while costing NumPy itself 0.3%, since 2 µs of
> interference is nothing against a 700 µs frame. The bias is asymmetric and it
> lands entirely on the smaller number. The harness's job is the parity gate,
> where interleaving is exactly right — the two trackers must see identical
> state at identical times. For throughput, [`bench/compare.py`](bench/compare.py)
> is the measurement of record: each tracker timed alone, warmed, min-of-9.

The reason matters more than the number, and two tempting explanations are both
wrong:

- **Not `Detection` construction.** It looked like the NumPy timing might be
  inflated by object construction the array-based C++ entry point skips.
  Measured separately: at most 3% of a frame.
- **Not NumPy per-call overhead on small matrices.** Plausible — MOT17-09's
  median cost matrix is 9×7 — but it predicts the advantage collapsing as the
  problem grows. It does not: the ratio stays flat out to 400×400.

Profiling the reference gives the real answer, in two parts:

- **`_kuhn_munkres` is not vectorized NumPy at all.** It is an interpreted
  O(n³) triple loop, and the largest single entry in the profile. The plan's
  premise is simply false for that function.
- **The per-track calls operate on 4- and 8-element arrays.** `xyah_to_xyxy`
  runs ~8,850 times per 60 frames, `kalman.update` ~2,950, each on one track. At
  that size NumPy's per-call machinery dwarfs the arithmetic it performs.

So the hot path was never the vectorized numerics the plan had in mind — it was
Python-level work on tiny arrays, and that is what the port removed.

This *revises* Phase 2 rather than confirming it. The plan wanted its headline to
be "LAPJV replaced the O(n³) Hungarian and the numbers did not move". Much of
that cost turns out to have been interpreter overhead the port has already
eliminated, so the remaining algorithmic win should be expected to be **smaller**
than the plan assumed. It now has a fair baseline to be measured against, which
is what Phase 1 was for.

## Honest expectations, and how they turned out

Phase 1 was planned on the expectation of **no speedup** — that a first-draft
C++ port might even be *slower* than vectorized NumPy, whose inner loops are
already compiled. The deliverable was meant to be the harness alone.

The harness was delivered and the prediction was refuted: 55–74× on real
sequences, for the reasons in *Throughput* above. The speedup is a real
measurement, but it is not the achievement — it is a baseline, obtained from a
deliberately unoptimized port with no SIMD, no LAPJV and no memory-layout work.

What Phase 1 actually produced is the thing that makes any later number
believable: a gate that fails on a single flipped association. Without it, "50×
faster" would be an unfalsifiable claim about a tracker nobody had checked.

## New to C++ / CMake / pybind11?

[`learning/LEARNING.md`](learning/LEARNING.md) explains this project from zero — what a compiler
does, why Python is slow but NumPy isn't, what each tool in the build is for,
and why parity is checked on full output streams rather than accuracy scores.
No prior C++ assumed.

## Licence

MIT.
