🚀 SAHI 0.12.5: postprocessing no longer scales with how crowded your boxes are

[onuralpszr]

0.12.5 finishes the memory work started in 0.12.2, which it turns out only helped when boxes were spread out, and fixes two correctness bugs found while testing it. Watch the 30 second explainer

The part we got wrong in 0.12.2

0.12.2 stopped building the N x N overlap matrix and stored one entry per intersecting pair instead. That is genuinely sparse when boxes are scattered. It is not sparse when boxes sit on top of each other. In a crowded scene each box overlaps about 900 others, so "A overlaps B" is true about 30 million times, and writing all 30 million down before the merge starts costs about 3.3 GB, against 4.2 GB for the matrix it replaced. Crowd scenes, cell imagery and dense aerial targets live exactly there, which is the reason sliced inference is used at all.

What changed

The merge loops read one row of matches at a time, and NMS and greedy NMM only ever read rows of boxes that survive. So there was never a reason to compute every pair up front. Rows are now answered from the STRtree on demand, and peak memory is bounded by O(N + max_degree) whatever the layout. On the crowded 33 337-box input only 141 boxes survive, so it asks 141 questions instead of storing 30 million answers.

case	time before	time after	memory before	memory after
crowded, 33 337 boxes	47 180 ms	135 ms	3416 MB	4 MB
crowded, 20 000 boxes	15 931 ms	57 ms	1232 MB	2 MB
crowded, 10 000 boxes	2717 ms	25 ms	311 MB	1 MB
scattered, 33 336 boxes	539 ms	188 ms	65 MB	4 MB

A non-positive match_threshold also no longer builds a matrix at all. Both metrics are non-negative, so every pair matches by definition and the answer follows from the score order. That configuration used to be the single most expensive one and reproduced the original out-of-memory failure at 25 000 boxes; it now returns in about 7 ms, and 100 000 boxes in about 33 ms.

Two correctness fixes found while testing

• NMM could merge a keeper into itself. A keeper was marked by leaving its merge_to_keep entry at -1, the same value that marks a box as unclaimed, so a box processed later could claim it. With tied scores on duplicate boxes this produced a keeper listed inside its own merge list. Reachable at ordinary thresholds, not just degenerate ones.
• Zero-area boxes emitted a RuntimeWarning. The metric divided for every pair and discarded the invalid entries afterwards; the division is now masked.

The numba backend picks its path by density

Its NMS and greedy NMM loops used to scan every pair whatever the input. Routing them by prediction count alone would have regressed crowded scenes, because the JIT loop skips suppressed boxes and stays competitive long after the numpy one stops being viable. The neighbour count decides instead, estimated from a sample.

The score sort was also an insertion sort, quadratic in its own right, and now uses the same lexsort the other backends share, which produces an identical order including ties.

One thing this release does not fix

nmm on crowded inputs still takes about 95 seconds at 33 337 boxes. Its memory dropped from 3401 MB to 18 MB, but the time is unchanged, because its merge loop visits every box rather than only the survivors and is O(pairs) in Python. Not a regression, and NMS and greedy NMM are unaffected, but worth knowing if crowded nmm is on your path. Happy to take suggestions on that one.

Upgrading

pip install -U sahi

No API changes. Same inputs give the same outputs; only the cost changed.

Pull requests: #1416, #1417, #1418, #1419.
Full notes: 0.12.5 release

[ZephyrKeXiner]

Thanks for the release and for the sparse postprocessing work. Reducing crowded NMM memory usage from 3401 MB to 18 MB is a substantial improvement, and the note about the remaining runtime bottleneck is very helpful.

I’d be happy to investigate the part of nmm on crowded imput. Since the match relationships are already stored as CSR, I’d like to profile the current merge loop and explore an array-based or Numba-compiled graph traversal over the existing representation.

I’ll first verify whether connected-components-style algorithms preserve the current score and tie-breaking semantics, rather than assuming they are equivalent. Is anyone already working on this? If not, I can share a small parity-tested prototype and benchmarks before proposing a PR.

[onuralpszr]

Thanks for the release and for the sparse postprocessing work. Reducing crowded NMM memory usage from 3401 MB to 18 MB is a substantial improvement, and the note about the remaining runtime bottleneck is very helpful.

I’d be happy to investigate the part of nmm on crowded imput. Since the match relationships are already stored as CSR, I’d like to profile the current merge loop and explore an array-based or Numba-compiled graph traversal over the existing representation.

I’ll first verify whether connected-components-style algorithms preserve the current score and tie-breaking semantics, rather than assuming they are equivalent. Is anyone already working on this? If not, I can share a small parity-tested prototype and benchmarks before proposing a PR.

Sure you can work on it.

[ZephyrKeXiner]

The final improvement is in PR #1426. If you have spared time, please check it.😃