Quadratic-Time Markov Chain Histogram Correction for High-Flux Single-Photon Lidar

Time-correlated single-photon counting (TCSPC) with free-running single-photon avalanche diodes enables high-resolution depth imaging, but at high photon flux detector dead times distort the timing histogram. The Markov Chain Histogram Correction (MCHC) algorithm corrects this distortion. Its bottleneck is the transition matrix, whose construction scales as O(N2·nTd) for N histogram bins and a dead-time span of nTd bins. We reduce this to O(N2) with a prefix-sum reformulation: closed-form expressions for hx and Ih turn every matrix entry into a range query on two cumulative sums. PS-MCHC is an exact acceleration of MCHC, not a new correction model: the matrix it builds is the same one. The cubic-to-quadratic gain is conditional. It holds when nTd∝N; for a fixed hardware dead time, both methods are O(N2), and the reformulation removes a constant factor nTd. Measured on the eight-level PDF bank with a fixed four-worker pool, the layout-matched matrix construction falls from 6.23 s to 1.42 s, a 4.4× gain. Against the implementation distributed with the reference code, which a memory-layout detail makes several times slower, the same task falls from 97.7 s to about 2 s. The construction runs at under 3% of measured memory bandwidth, so the gap between the nTd arithmetic reduction and the wall-clock gain is implementation overhead rather than memory traffic. The two corrected pipelines agree to 0.0001 m, and the difference from the uncorrected result is attributable to the matched-filter template, not to the acceleration.