Accelerating integral histograms using an adaptive approach

Many approaches in computer vision require multiple retrievals of histograms for rectangular patches of an input image. In 2005 an algorithm to accelerate these retrievals was presented. The data structure utilized is called Integral Histogram, which was based on the well known Integral Image. In this paper we propose a novel approximating method to obtain these integral histograms that outperforms the original algorithm and reduces computational cost to more than a tenth. Alongside we will show that our adaptive approach still provides reasonable accuracy - which allows dramatic performance improvements for real-time applications while still being well suited for numerous computer vision tasks.