Computationally Ecient Histogram Extraction for Rectangular Image Regions
Fatih Porikli · 2005
We present a novel method, which we refer as an integral histogram, to compute the histograms of all possible target regions in an image. Our method is computationally superior and makes it possible to employ even an exhaustive search process in real-time, which was impractical before. Furthermore, it enables the description of higher level histogram features. To accomplish fast extraction, we exploit the spatial arrangement of image points, and recursively propagate an aggregated histogram by starting from an origin and traversing through the remaining images along a given scan-line. At each step, we update a single histogram bin using the values of integral histogram at the previously visited neighboring points. After integral histogram is propagated, histogram of any target region can be computed easily by using simple arithmetic operations. Our numerical analysis proves that the integral histogram method drastically decreases the amount of the required computations.