# ADR-075: Min-Cut Based Person Separation from Subcarrier Correlation

- **Status:** Proposed
- **Date:** 2026-04-02
- **Issue:** #348 — `n_persons` always reports 4 regardless of actual occupancy
- **Depends on:** ADR-016 (RuVector integration), ADR-041 (person tracking), ADR-073 (multifrequency mesh scan)

## Context

### The Bug

Issue #348 reports that the ESP32 firmware's multi-person counting always reports
`n_persons = 4`. The root cause is in the WASM edge module
`sig_mincut_person_match.rs`, which uses a fixed `MAX_PERSONS = 4` constant and a
threshold-based variance classifier to populate person slots. The classifier bins
subcarriers into "dynamic" vs "static" using a single fixed variance threshold
(`DYNAMIC_VAR_THRESH = 0.15`). In practice:

1. The threshold is miscalibrated for real-world CSI data — almost any room with
   multipath reflections pushes a majority of subcarriers above 0.15 variance.
2. The subcarrier-to-person assignment uses a greedy Hungarian-lite matcher that
   fills all 4 slots once there are >= 4 dynamic subcarriers (which is nearly
   always the case).
3. There is no mechanism to determine how many independent movers exist — the
   algorithm assumes all 4 slots should be filled.

### Prior Art

The Rust crate `ruvector-mincut` (vendored at `vendor/ruvector/crates/ruvector-mincut/`)
implements a full dynamic min-cut algorithm with O(n^{o(1)}) amortized update time,
Stoer-Wagner exact min-cut, and online edge insert/delete. It is already integrated
in the training pipeline (`wifi-densepose-train/src/metrics.rs`) via
`DynamicPersonMatcher`.

### WiFi Sensing Insight

When a person moves through a room, they perturb the Fresnel zones of specific
subcarrier frequencies. Subcarriers whose Fresnel zones overlap the person's body
change **together** — their amplitudes are temporally correlated. When two people
move independently, they create two **separate** groups of correlated subcarriers.
This correlation structure forms a natural graph partitioning problem.

## Decision

Replace the fixed-threshold person counter with a spectral min-cut algorithm
operating on the subcarrier temporal correlation graph. This runs in the bridge
script (`scripts/mincut-person-counter.js`) or on Cognitum Seed, and feeds the
corrected person count back to the feature vector before ingest.

### Algorithm

1. **Sliding window accumulation**: Maintain the last 2 seconds of subcarrier
   amplitude data (~40 frames at 20 fps). Each frame provides a 64-element
   amplitude vector (one per subcarrier).

2. **Pairwise Pearson correlation**: For all subcarrier pairs (i, j), compute
   the Pearson correlation coefficient over the sliding window:

   ```
   r(i,j) = cov(amp_i, amp_j) / (std(amp_i) * std(amp_j))
   ```

   This produces a 64x64 correlation matrix.

3. **Graph construction**: Build a weighted undirected graph:
   - **Nodes** = subcarriers (64 for single-antenna ESP32-S3, up to 128 for dual)
   - **Edges** = pairs with |r(i,j)| > 0.3 (correlation threshold)
   - **Weight** = |r(i,j)| (correlation strength)
   - Discard null subcarriers (amplitude consistently near zero)
   - Expected: ~1500-2500 edges for 64 active subcarriers

4. **Iterative Stoer-Wagner min-cut**: Apply the Stoer-Wagner algorithm to find
   the global minimum cut. If the min-cut weight is below a separation threshold
   (empirically 2.0), the cut represents a real boundary between independent
   movers. Split the graph at the cut and recurse on each partition.

5. **Person count**: The number of partitions after all valid cuts = number of
   independent movers = person count. A single connected component with high
   internal correlation and no low-weight cut = 1 person (or 0 if variance is
   also low).

6. **Empty room detection**: If the total variance across all subcarriers is
   below a noise floor threshold, report 0 persons regardless of graph structure.

### Stoer-Wagner Algorithm

Stoer-Wagner finds the exact global minimum cut of an undirected weighted graph
in O(V * E) time using a sequence of "minimum cut phases":

```
function stoerWagner(G):
    best_cut = infinity
    while |V(G)| > 1:
        (s, t, cut_of_phase) = minimumCutPhase(G)
        if cut_of_phase < best_cut:
            best_cut = cut_of_phase
            best_partition = partition induced by t
        merge(s, t)  // contract vertices s and t
    return best_cut, best_partition

function minimumCutPhase(G):
    A = {arbitrary start vertex}
    while A != V(G):
        z = vertex most tightly connected to A
        // "most tightly connected" = max sum of edge weights to A
        add z to A
    s = second-to-last vertex added
    t = last vertex added (most tightly connected)
    cut_of_phase = sum of weights of edges incident to t
    return (s, t, cut_of_phase)
```

For V=64 subcarriers and E~2000 edges, this runs in ~8 million operations,
well under 1ms on modern hardware and under 10ms even on ESP32-S3.

### Integration Points

```
ESP32 Node 1 ──UDP 5006──┐
                          ├──> mincut-person-counter.js ──> corrected n_persons
ESP32 Node 2 ──UDP 5006──┘         │
                                   ├──> seed_csi_bridge.py (feature dim 5 override)
                                   └──> csi-graph-visualizer.js (debug view)
```

The person counter runs as a standalone Node.js process alongside the existing
`rf-scan.js` and `seed_csi_bridge.py` bridge scripts. It can also replay
recorded `.csi.jsonl` files for offline analysis.

## Alternatives Considered

### 1. Threshold-based peak counting (current, broken)

Count subcarriers with variance above a threshold, then cluster by proximity.
**Problem:** threshold is environment-dependent, miscalibrates easily, and
cannot distinguish correlated from independent motion.

### 2. PCA / spectral clustering on correlation matrix

Compute eigenvectors of the correlation matrix; the number of large eigenvalues
indicates the number of independent sources. **Problem:** requires choosing an
eigenvalue gap threshold, which is as fragile as the current variance threshold.
Also does not give per-person subcarrier assignments.

### 3. Min-cut on correlation graph (this ADR)

**Advantages:**
- Directly models the physical structure (Fresnel zone groupings)
- Threshold-free person counting (cut weight is a natural separation metric)
- Produces per-person subcarrier groups as a side effect
- Stoer-Wagner is simple to implement (~100 lines) and runs in polynomial time
- Already validated in Rust via `ruvector-mincut` integration

## Performance

| Metric | Value |
|--------|-------|
| Graph size | V=64, E~2000 |
| Stoer-Wagner complexity | O(V * E) = O(128,000) per cut |
| Iterative cuts (max 4) | O(512,000) total |
| Wall time (Node.js) | < 5 ms per 2-second window |
| Wall time (Rust/WASM) | < 0.5 ms |
| Memory | ~32 KB for correlation matrix + graph |
| Sliding window | 2 seconds = ~40 frames * 64 subcarriers * 8 bytes = 20 KB |

## Consequences

### Positive

- Fixes #348: person count now reflects actual independent movers
- Robust across environments (no per-room threshold calibration)
- Per-person subcarrier groups enable per-person feature extraction
- Graph visualization aids debugging and room mapping
- Algorithm is well-understood (Stoer-Wagner, 1997)

### Negative

- Adds a new process to the sensing pipeline
- 2-second latency for person count changes (sliding window)
- Correlation-based: cannot detect stationary persons (no motion = no signal)
- Assumes independent motion — two people walking in sync may be counted as one

### Migration

1. Deploy `scripts/mincut-person-counter.js` alongside existing bridge
2. Override feature vector dimension 5 (`n_persons`) with corrected count
3. Once validated, port Stoer-Wagner to C for direct ESP32-S3 firmware integration
4. Deprecate the fixed-threshold `PersonMatcher` in `sig_mincut_person_match.rs`

## References

- Stoer, M. & Wagner, F. (1997). "A Simple Min-Cut Algorithm." JACM 44(4).
- `vendor/ruvector/crates/ruvector-mincut/src/algorithm/mod.rs` — DynamicMinCut API
- `v2/.../sig_mincut_person_match.rs` — current (broken) WASM edge matcher
- `scripts/rf-scan.js` — CSI packet parsing and subcarrier classification