积分图及其应用

时间:2024-04-14 21:30:47

  Paul Viola提出一种利用积分图快速计算Haar特征的方法(《Rapid object detection using a boosted cascade of simple features》)。Haar特征是什么就不多做介绍,总之Haar特征的计算需要重复计算目标区域的像素值,使用积分图能大大减少计算量,达到实时计算Haar特征的目的。简单来说,就是先构造一张“积分图”(integral image),也叫Summed Area Table,之后任何一个Haar矩形特征都可以通过查表的方法(Look Up Table)和有限次简单运算得到,大大减少了运算次数。所以但凡需要重复计算目标区域内像素值和的场合,积分图都能派上用场。下面开始介绍积分图原理,并给出其的几个应用。

1、积分图原理

  将矩形表示为:

  其中,x,y表示坐标,w,h表示宽、高,a表示角度。

  积分图像中,每个点存储的是其左上方所有像素之和:

           

 

其中I(x,y)表示图像(x,y)位置的像素值。积分图像可以采用增量的方式计算:

初始边界:SAT(-1,y)=SAT(x,-1)=SAT(-1,-1)=0

为了更好地说明这个等式的缘由,下面我用几幅图来说明:

     

          图1.坐标(x,y)处在原图像中示例                 图2.坐标(x,y-1)处的积分图像SAT(x,y-1)示例

   

 图3.坐标(x-1,y)处的积分图像SAT(x,y-1)示例     图4.坐标(x-1,y-1)处的积分图像SAT(x-1,y-1)示例  

 

 可以看到,SAT(x,y-1)+SAT(x,y-1)后,有一部分重合的区域,即SAT(x-1,y-1),所以需减掉,最后还需要将当前坐标(x,y)的像素值I(x,y)包含进来。

定义了积分图的概念,就可以很方便的计算任意区域内的像素和,如下图所示:

所以,

点1的积分SAT1=Sum(Ra),

点2的积分SAT2=Sum(Ra)+Sum(Rb),

点3的积分SAT3=Sum(Ra)+Sum(Rc),

点4的积分SAT4=Sum(Ra)+Sum(Rb)+Sum(Rc)+Sum(Rd)

那么,区域Rd内所有点的像素值之和(积分)可以表示为:

Sum(Rd)=SAT1+SAT4-SAT2-SAT3

所以无论矩形的尺寸大小,只需查找积分图像4次就可以求得任意矩形内像素值的和。

 

2、积分图应用

(1)Haar-like特征值计算

  以如下一种Haar-like边缘特征为例

                       

  假设需要计算的这种Haar-like特征在图中的位置如下所示:

       

  那么,A,B区域所构成的Haar-like边缘特征是:

  显然,对一个灰度图而言,事先将其积分图构建好,当需要计算灰度图某个区域内所有像素点的像素值之和的时候,利用积分图,通过查表运算,可以迅速得到结果。

 

(2)使用积分图像实现自适应阈值化

自适应阈值是一种局部方法。它的原理是根据每个像素的邻域(如5x5)计算阈值,如将每个像素的值与指定的邻域的平均值进行比较,如果某像素的值与它的局部平均值差别很大,就会被当作异常值在阈值化过程中被分离。

如若不采用积分图像,则每个像素比较时,都需要进行5x5次加法运算;而采用积分图像,运算复杂度不随邻域大小而改变,每次只需计算2次加法和2次减法。

(3)

我本人在做车牌字符分割时,设计了一个动态模板在车牌图像上滑动,并且每次滑动都计算一次模板内包含的非零像素点个数,没用积分图的时候,每次计算都要遍历,效率真的太低,滑动1000多次,计算耗时竟达到了几百ms,这在实时处理中是不能容忍的。而后去补了积分图的知识,使用积分图来计算每次滑动后区域内的非零像素点个数,效率不要太高,只耗费了几ms就完事了。深深感叹算法的博大精深!

以上。