Adaptive histogram equalization in constant time

Adaptive Histogram Equalization (AHE) and its contrast-limited variant CLAHE are well-known and effective methods for improving the local contrast in an image. However, the fastest available implementations scale linearly with the filter mask size, which results in high execution times. This presents an obstacle in real-world applications, where large filter mask sizes are desired while maintaining low execution times. In this work, we propose an efficient algorithm for AHE that reduces the per-pixel computational complexity to $\mathcal{O}(1)$. To the best of our knowledge, this is the first time that a constant-time algorithm is proposed for AHE and CLAHE. In contrast to commonly used fast implementations, our method computes the exact result for each pixel without interpolation artifacts. We benchmark and compare our method to existing algorithms. Our experiments show that our method exhibits superior execution times independent of the filter mask size, which makes AHE and CLAHE fast enough to be usable in real-world applications.