Integral Histogram A Fast Way to Extract Histograms in Cartesian Spaces

Integral Histogram:A Fast Way to Extract Histograms in Cartesian Spaces

Fatih Porikli

Mitsubishi Electric Research Laboratories

fatih@https://www.sodocs.net/doc/a612491192.html,

Abstract

We present a novel method,which we refer as an integral histogram,to compute the histograms of all possible target regions in a Cartesian data space.Our method has three distinct advantages:1-It is computationally superior to the conventional approach.The integral histogram method makes it possible to employ even an exhaustive search pro-cess in real-time,which was impractical before.2-It can be extended to higher data dimensions,uniform and non-uniform bin formations,and multiple target scales with-out sacri?cing its computational advantages.3-It enables the description of higher level histogram features.We ex-ploit the spatial arrangement of data points,and recursively propagate an aggregated histogram by starting from the ori-gin and traversing through the remaining points along ei-ther a scan-line or a wave-front.At each step,we update a single bin using the values of integral histogram at the pre-viously visited neighboring data points.After the integral histogram is propagated,histogram of any target region can be computed easily by using simple arithmetic operations.

1.Introduction

A histogram is an array of numbers in which each ele-ment,bin,corresponds to the frequency of a range of values in the given data.For instance,each bin counts the number of pixels having the same color values in case of an image histogram.Thus,a histogram is a mapping from the set of data values to the set of non-negative real numbers.From a probabilistic point of view,the normalization of an his-togram results in a function that is most akin to the proba-bility density function of the data.It is possible to employ a histogram to answer the following questions:What kind of distribution do the data come from?What are the statistical properties of this distribution such as how spread out are the data?Are there outliers in the data?Histograms are among the most common features used in many computer vision tasks from object based retrieval[1],[2],to segmentation [3],[5]to detection[4],[6]to tracking[7].

Computational complexity is one major bottleneck of the histogram extraction and comparison based search tasks.It is obvious that only an exhaustive search can provide the global optimum.Although several sub-optimal techniques that are powered by gradient descent methods and applica-tion speci?c constraints have been developed to deliver ac-celerated alternatives to the basic exhaustive search,com-puter vision problems that rely on the optimal solutions, such as detection and tracking,still demand a theoretical breakthrough in histogram extraction as much as an power-ful computers to crunch the numbers.

To address the computational requirements of detection tasks,we develop a fast method to compute histograms of all possible target regions in a given data.We take advan-tage of the spatial positioning of data points in a Cartesian coordinate system,and propagate an aggregated function, which we refer as the integral histogram,starting from an origin point and traversing through the remaining points along a scan-line.We iterate the integral histogram at the current point using the histograms of the previously pro-cessed neighboring data points.At each step,we increase the value of the bin that the current point?ts into the bin’s range.After the integral histogram is obtained for each data point,histograms of target regions can be computed easily by using the integral histogram values at the corner points of those regions without reconstructing a separate histogram for every single region.In a2D data,such as an image,the integral histogram converts into the extraction of rectangu-lar region histograms,which are computed by intersection of the integral histogram at the four corner points.

The integral histogram method has several advantages: First,it is computationally superior than the conventional approach.It is possible to execute even an exhaustive his-togram search process in the data space,which was infea-sible with conventional approaches.It can be extended to higher dimensions,histogram bin structures,and multiple scales without sacri?cing its computational bene?ts.It en-ables description of advanced histogram features as illus-trated in Fig.1.

In the next section,we summarize the previous work.In section3,we introduce the integral histogram formulation

Figure1.Advanced features,e.g.spatial arrangement or hierarchi-cal fusion of the component histograms,can be easily computed using integral histogram for various tasks.

in detail.In section4,we give a computational complexity analysis by considering different scenarios.In section5,we present simulation results and discuss various aspects of the proposed method.

2.Previous Work

It is possible to calculate the sum of the values within rectangular regions in linear time without repeating the summation operator for each possible region[6].A constant number of operation for each rectangular sum is needed to compute such sums over distinct rectangles many times.A cumulative image function is de?ned such that each element of this function holds the sum of all values to the left and above of the pixel including the value of the pixel itself. The cumulative image can be computed for all pixels with four arithmetic operations per pixel.Starting from the top left corner and traversing?rst to the right and then to the down,the value of the cumulative image at the current pixel equal is obtained by the addition of the left and the up pixel and subtraction of the upper left pixel’s cumulative values. After the cumulative image is computed,the sum of image function in a rectangle can be computed with another four arithmetic operations with appropriate modi?cations at the border.Thus with a linear amount of computation,the sum of image function over any rectangle can be computed in linear time.

A conventional approach of measuring distances be-tween a given histogram and histograms of all possible tar-get regions is an exhaustive search.This process requires generation of histograms for the regions centered at every possible points.In case the search should be done at dif-ferent scales,i.e.different target region sizes,the whole process should be repeated as many times as the number of scales.We give a pseudo-code of the conventional his-togram in algorithm2.1.To our knowledge,the conven-tional approach is the only solution(other than the pre-sented integral histogram method)that guarantees to?nd the global optimum in histogram based search.for each

do

for each

do

for each

do

for each

do

Figure 2.Propagation of integral histogram by string

scan.

Figure 3.Propagation of integral histogram by wavefront scan.Yellow indicates already traversed points.At each step,the cur-rent integral histogram is obtained from the integral histogram val-ues of the three neighbors,and the bin that corresponds to current point’s value is increased by one.

The are different scanning and propagation approaches;here we present two of them.One is a string scan method that covers the data space along each dimension e.g.from left to right and top to bottom for an image data.The inte-gral histogram at the current point is obtained by copying the previous values and increasing the corresponding bin with respect to the current value of the point.The string scan requires only update at each step of propagation.How-ever,string scans at different dimensions should be per-formed to obtain the histogram of a polytope region in a -dimensional data as illustrated in Fig.2.

It is also possible to scan points using an active sets of points,i.e.a wavefront.The wavefront scan requires up-dating the integral histogram for such data points that their left,upper,and upper-left neighbors are already scanned in case of an image data.The integral histogram at a point is obtained by three arithmetic operations for each bin of us-ing the integral histogram values of the three neighbors as shown in Fig.3.The integral histogram values of the previ-ous point is copied to the current point before the propaga-tion.Either the updated bin is copied to all of the remaining points’bins (a total of copy operations),or all the previous bins are copied to the current bins (oper-ations),which can be done by fast hardware-level memory copy functions or by pointer tables.

3.2.Intersection

The histogram of a target region can be computed us-ing the wavefront propagated integral histogram values at the boundary points of the region.In a Cartesian space,the target region corresponds to a polytope enclosed by a ?nite number of hyperplanes such as

.The boundary points are where

their indices in each dimension have number of co-ordinates and number of coordinates.Note that,for a ?xed there exist such combinations,which is a binomial coef?cient.In other words,for there is only one point .For there are points

,,..,,and so

on.Then,the histogram is simply obtained as

(3)

This assigns the histogram bins of the current point by using the intersection of the bins of the three previous histograms.In case of an gray level image,our parameters are ,,and a wavefront scan from upper left point the propagation can be written as

(4)

and the intersection becomes

.

As opposed to the conventional histogram computation,the integral histogram method does not repeat the histogram extraction for each possible region as given in the pseudo-code below:

for each

do

for each do

for each

do

for each

do for each

do

B D Integer addition11 Integer multiply424 Integer divide36-Floating-point addition3 4.2 Floating-point multiply5113 Floating-point divide38-Type conversion--Bit-wise shift--

operations,and normalize the result using?oating point

divisions(operations)for each histogram.Then,the

cost of extraction of all histograms at all possible scales is

(6)

Of course,both methods compute histogram distances using

the given metric in addition to the above costs.

We de?ne a ratio of the computational load of the con-

ventional approach versus the integral histogram method;

(14)

We present the computational ratio results for1-D data in

Fig.4(row).The different graphs in the?rst column

represents the different target sizes plotted against the dif-

ferent number of bins in the histogram.The vertical axis

shows the amount of computational savings.As visible,the

integral histogram improves the processing time up to the

times over the conventional method.For instance,

a common task that requires searching a pattern which con-

tains points using a-bins histogram can be employed

3,347times faster than the conventional method.

5.2.2D Case:Gray Level Images

For a gray level image and a search region size

range,the parameters of the above analysis become

and,and the ratio is

2-D data is very common in most vision problems from gray-level surveillance video to mono-chrome aerial im-

agery.For instance,our problem may involve?nding a target pattern in3different resolutions using a-bins histogram.The integral histogram method hunts for

these patterns times faster.In Fig.4(row),we give the comparison results,which show the integral his-togram performs up to times faster computations.

5.3.2D Case with3D Tensors:Color Images

For a color image with a3D histogram(assuming each point has3color values in a tensor form),the parameters become and.Assuming we are searching for a template at scales,the ratio becomes

(17)

Integral histogram method becomes more advantageous in higher dimensions as shown in Fig.4(row).The savings can reach up to.For a target volume being searched in its original size()using a-bins histogram,we can achieve times improvement.

5.5.Object Detection Results

Figures5-6show detection results of given patterns us-ing histogram features.In the traf?c sign detection example, we search for the target object using a-bins color his-togram.Although the conventional approach and integral histogram give the very same similarity map,the integral histogram method runs in63msecs,however,the conven-tional approach requires2minutes on a3.2Ghz P4.The integral histogram method is not limited to color and in-tensity histograms.In texture detection example,as given in Fig.6,we use a-bins histogram of gradient orienta-tion.To get the same results with the integral

histogram Figure5.Object detection using a-bins color histogram.The computed similarity map is same as the conventional approach; however the integral histogram method runs in63msecs although the conventional exhaustive search takes approximately2minutes for100scales on a3.2Ghz

P4.

Figure6.Texture detection using a-bins gradient orientation histogram.The integral histogram takes88msecs,the conven-tional method requires more than5minutes to get the same result. that takes88msecs,the conventional method requires more than5minutes of processing time.Note that,even such a simple histogram provides suf?cient information for tex-ture segmentation,and it is possible to combine histogram to de?ne higher level features such as Haar wavelets,etc.

Note that,the integral histogram based search can be ac-celerated further by using application speci?c constraints as it is often employed for the conventional approach.

5.6.Tracking Examples

We simulated the integral histogram method to track ob-jects between the consecutive video frames.After initializa-tion of an object,we compute the color histogram similarity scores between the original histogram and the histograms of the object windows centered around every pixels.Note that, such a similarity computation would be very slow using the conventional approach.We compare our simple tracking adaptation with a gradient descent based method known as mean-shift[7].Mean-shift evaluates the histogram similar-ity(in most cases using Bhattacharya distance)only within

10

20

304050

60

70

00.5

11.522.533.54x 10

4

M = 1000

M = 2500

M = 5000

M = 7500

M = 10000

Computational improvement 1?D Time Series

histogram bin size B

× t i m e s f a s t e r

Figure https://www.sodocs.net/doc/a612491192.html,putational reduction in comparison to the conventional method.The integral histogram method is as many times as faster than the existing approach for different type of problems explained in Section 5.

Mean-shift

tracking

results

Similarity scores using integral histogram

Histogram match tracking results

Figure 7.Object moves fast and there is no overlap between the consecutive frames.Although mean-shift needs only 15msecs on average,it may fail if the relocation of the object is large and there is no overlap of boxes.Integral histogram method can ?nd the

correct position in ?55msecs regardless of the overlap.

its original kernel,that is the window of the object.There-fore,it is computationally feasible for real-time applica-tions.For an object size shown in Fig.7,the mean-shift

iterations using -bins histograms for each color channel takes only 15msecs on average depending the number of iterations (on 3.2Ghz P4).However,mean-shift owns its speed to the fact that it only evaluates the similarity within a limited search region.As a result,for the cases in which object relocation is large and there is no overlap between the object windows in the consecutive frames,it is bounded to fail as shown in the ?gures.

The integral histogram enables us to compute similar-ities all over the image plane in a relatively constant small amount of time (55msecs),thus we can track accurately fast objects even in high frame sampling rates that cause signif-icant relocation of the objects.

6.Discussion

We present a novel and computationally very fast method to compute the histograms of all possible regions in a Carte-

sian space.The integral histogram provides not a sub-optimal or a partial solution,but an optimum and complete solution for the histogram based search problems.

Our experiments with different number of bins,data di-mensions,and data structures con?rm that the integral his-togram method drastically decreases the amount of compu-tations needed to obtain a multitude of histograms,thus,it signi?cantly improves the speed of search algorithms based on histogram comparison.

In addition,the integral histogram enables construction of advanced histogram features for further feature selection and classi?cation purposes.It can be extended easily to higher dimensional data spaces and other tensor represen-tations.

Several computer vision tasks such as video object de-tection and tracking where the real-time requirement was a bottleneck up to now will bene?t from the integral his-togram method.

References

[1]J.Huang,S.Kumar,M.Mitra,W.J.Zhu,and R.Zabih,“Im-age indexing using color correlograms”,In Proceedings of CVPR ,1997.[2] C.Carson,M.Thomas,S.Belongie,J.M.Hellerstein,and J.

Malik,“Blobworld:A system for region-based image index-ing and retrieval”,In Proceedings of ICVS ,1999.[3] D.A.Forsyth and J.Ponce.“Computer Vision:A Modern

Approach”,Prentice Hall ,2002.[4] C.Papageorgiou,M.Oren,and T.Poggio.A general frame-work for object detection,In Proceedings of ICCV ,1998.

[5]S.Ruiz-Correa,L.G.Shapiro,and M.Meila,“A new

paradigm for recognizing 3-D object shapes from range data”,In Proceedings of CVPR ,2003.[6]P.Viola and M.Jones,“Robust real-time face detection”,In

Proceedings of ICCV ,page II:747,2001.[7] https://www.sodocs.net/doc/a612491192.html,aniciu,V .Ramesh,and P.Meer,“Real-time track-ing of non-rigid objects using mean shift”,In Proceedings of CVPR ,2000.[8]S.Oualline,“Practical C++programming”,O’Reilly &Asso-ciates ,ISBN:1-56592-139-9,1995.[9]J.Mathew,P.Coddington and K.Hawick,“Analysis and de-velopment of java grande benchmarks”,In Proceedings of ACM ,1999.[10]R.Bryant and D.O’Hallaron,“Computer systems:a pro-grammer’s perspective”,Prentice Hall ,ISBN 0-13-034074-1,2003.[11]Y .Moon,F.Luk,H.C.Ho,T.Y .Tang,K.Chan,C.Leung,

“Fixed-point arithmetic for mobile devices;a ?ngerprint ver-i?cation case study”,In Proceedings of SPIE ,2002.