⚡ v0.9.9 Performance Refactor — Up to 70× Faster #60
brandonmpetty
started this conversation in
Show and tell
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
⚡ v0.9.9 Performance Refactor — Up to 70× Faster
The latest release is a performance-focused refactor of the Δoxa core. Every algorithm was re-examined for how it traverses a local window, and the results are substantial: several of the most computationally expensive algorithms are now 28× to 70× faster, while the everyday workhorses (Sauvola, Niblack, Wolf, Nick) gained a further 20–45%. Best of all, output is bit-for-bit identical to prior releases — this is a pure performance gain, with no change to result quality.
Building on a Strong Foundation
Δoxa has always treated performance as a first-class concern, and the framework already rested on a foundation of well-established optimizations:
These techniques are what allow Sauvola-class algorithms to run in a few milliseconds. Version 0.9.9 extends that same discipline to the areas of the framework that hadn't yet benefited from it.
What's New in v0.9.9
The Chan family gains a masking variant
The three Chan calculators now share a single, unified sliding-window implementation in
ChanCalc.hpp. The centerpiece of this release is a new variant,ChanMaskedCalc, which computes windowed count, sum, and — optionally — sum-of-squares over only the pixels selected by a binary mask, in constant time per pixel.This capability unlocked the largest gains. Algorithms such as Gatos and Su previously opened a nested loop at every pixel to tally its neighborhood — an expensive quadratic pattern. By expressing that neighborhood tally as a single sliding pass, kept branchless by the guarantee that mask pixels are always
0x00or0xFF, the per-pixel cost collapses to a handful of operations. 🎯 Gatos improved from roughly 610 ms to 9 ms; Su from roughly 318 ms to 6 ms.Separable morphology with van Herk / Gil-Werman
Grayscale Erode, Dilate, Open, and Close were rewritten around the van Herk / Gil-Werman (vHGW) algorithm. A square window is separable, so the implementation applies a fast one-dimensional min/max filter across each row and then down each column. This replaces a custom algorithm that accomplished the same goal, just not as efficiently.
This directly benefits Bernsen, which is built on local minima and maxima, and feeds into Wan. The impact is significant: 🎯 Bernsen improved from roughly 202 ms to 4.5 ms (44× faster), and Wan from roughly 102 ms to 3.6 ms (28× faster).
A leaner flood-fill for ISauvola
ISauvola's connected-component trace replaced its hash-set frontier with a simple stack and now reuses the output image itself as the visited set, ensuring each pixel is touched at most once. The result is a cleaner, more cache-friendly routine that runs approximately twice as fast.
A more efficient AdOtsu
AdOtsu's multi-scale path (AdOtsuMS) received two targeted improvements: the global Otsu threshold is now computed once and reused across every scale iteration rather than recomputed each time, and the per-pixel unit-step decision is served from a precomputed 256-entry lookup table instead of repeated floating-point arithmetic. Together these reduced AdOtsuMS runtime by nearly 70% (3.2× faster). AdOtsu is also now explicitly marked Experimental while its correspondence to the source paper is under review.
Correctness hardening
Otsu's histogram sums were widened to 64-bit integers, preventing overflow on images larger than approximately 8 megapixels — a robustness improvement that accompanies the performance work.
📊 Results
Benchmarked with Google Benchmark on a representative document image:
Run on (8 X 2304 MHz CPU s)
CPU Caches:
A few already-fast algorithms (Bataineh, Wellner, Feng, XDoG) show movements of a few percent in either direction. These fall within normal run-to-run measurement variance and don't represent genuine regressions.
The Bottom Line 🚀
The most expensive algorithms are now genuinely practical. Everything that used to run in the hundreds of milliseconds — Gatos, Su, Bernsen, Wan — now completes in single-digit milliseconds, bringing entire classes of algorithms into range for real-time and batch workloads. And it all comes for free: every correctness test passes unchanged, so the gains are purely a matter of doing the same math more efficiently.
Just as importantly, the techniques behind these numbers — the unified Chan calculators and the separable vHGW morphology — aren't one-off tricks. They're general-purpose building blocks that any future algorithm in the framework can build on.
As with every release, benchmarks run on all three platforms (Linux, Windows, and macOS) in CI, each with its own tracked baseline. We'd love to hear what you think. 🙌
All reactions