Contrast Limited Adaptive Histogram Equalization: A 37-Year Journey from O(r2) to O(1)

Contrast Limited Adaptive Histogram Equalization (CLAHE) is one of the most widely used image processing techniques in medical imaging, remote sensing, autonomous systems, and daily photography, etc. Despite of the importance of the algorithm, it took 37 years for a constant time algorithm to be discovered, which was thought impossible by most people. In this paper we review the algorithm development of CLAHE. We begin with the theoretical foundations of global histogram equalization, and follow the history to the development of adaptive histogram equalization (AHE) and CLAHE. We then focus on reviewing CLAHE algorithms of decreasing time complexity from O(r2) all the way to O(1). Now that the optimal CLAHE algorithm problem is solved, it is inspiring to look back at the 37 year journey: never stop thinking beyond impossible.