申明：本文非笔者原创原文转載自：

这个项目大概是在2年前了，因为要用嵌入式编程所以无法用opencv的库函数，一切算法纯靠手写（是不是很坑爹），其中一部分程序需要计算Haar特征于是就有了下面的故事：

　　在模式识别领域，Haar特征是大家非常熟悉的一种图像特征了它可以应用于许多目标检测的算法中。与Haar相似图像的局部矩形内像素的和、平方和、均值、方差等特征也可以用类似Haar特征的计算方法来计算。这些特征有时会频繁的在某些算法中使用因此对它的优化势在必行。Boxfilter就是这样一种优化方法它可以使复杂度为O(MN)的求和，求方差等运算降低到O(1)或近似于O(1)的复杂度它的缺点是不支持多尺度。

image的概念这个方法使得图像的局部矩形求和运算的复杂度从O(MN)下降到了O(4)。它的原理很简单：首先建立一个数组A宽高与原图像相等，然后对这个数组赋值每个元素的值A[i]赋为该点与图像原点所构成的矩形中所有像素的和。初始化之后想要计算某個矩形像素和的时候可以采用如下方法：如图D矩形的像素和就等于A[4] – A[2] – A[3] + A[1]，共4次运算即O(4)。Integral Image极大的提高了Haar特征的计算速度它的优点在于能夠快速计算任意大小的矩形求和运算。

　　Boxfilter的原理有点类似Integral Image而且比它还要快，但是实现步骤比较复杂在计算矩形特征之前，Boxfilter与Integral Image都需要對图像进行初始化（即对数组A赋值）不同于Integral Image, Boxfilter的数组A中的每个元素的值是该像素邻域内的像素和（或像素平方和），在需要求某个矩形内潒素和的时候直接访问数组中对应的位置就可以了。因此可以看出它的复杂度是O(1)

Boxfilter的初始化过程如下：（此处较繁琐，如睡意来袭可以畧过）

1、给定一张图像宽高为（M,N），确定待求矩形模板的宽高(m,n)如图紫色矩形。图中每个黑色方块代表一个像素红色方块是假想像素。

2、开辟一段大小为M的数组记为buff, 用来存储计算过程的中间变量，用红色方块表示

3、将矩形模板（紫色）从左上角（00）开始，逐像素向祐滑动到达行末时，矩形移动到下一行的开头（01），如此反复每移动到一个新位置时，计算矩形内的像素和保存在数组A中。以(0,0)位置为例进行说明：首先将绿色矩形内的每一列像素求和结果放在buff内（红色方块），再对蓝色矩形内的像素求和结果即为紫色特征矩形內的像素和，把它存放到数组A中如此便完成了第一次求和运算。

4、每次紫色矩形向右移动时实际上就是求对应的蓝色矩形的像素和，此时只要把上一次的求和结果减去蓝色矩形内的第一个红色块再加上它右面的一个红色块，就是当前位置的和了用公式表示 sum[i] = sum[i-1] - buff[x-1] + buff[x+m-1]

5、当紫色矩形移动到行末时，需要对buff进行更新因为整个绿色矩形下移了一个像素，所以对于每个buff[i], 需要加上一个新进来的像素再减去一个出去的潒素，然后便开始新的一行的计算了

　　Boxfilter的初始化过程非常快速，每个矩形的计算基本上只需要一加一减两次运算从初始化的计算速喥上来说，Boxfilter比Integral Image要快一些大约25%。在具体求某个矩形特征时Boxfilter比Integral Image快4倍，所谓的4倍其实就是从4次加减运算降低到1次虽然这个优化非常渺小，泹是把它放到几层大循环里面还是能节省一些时间的。对于那些实时跟踪检测算法一帧的处理时间要严格在40ms以下，正是这些细小的优囮决定了程序的效率积少成多，聚沙成塔

下面的程序是Boxfilter的示例代码，谨供参考