在模式識别領域，Haar特征是大家非常熟悉的一種圖像特征了，它可以應用于許多目标檢測的算法中。與Haar相似，圖像的局部矩形内像素的和、平方和、均值、方差等特征也可以用類似Haar特征的計算方法來計算。這些特征有時會頻繁的在某些算法中使用，是以對它的優化勢在必行。Boxfilter就是這樣一種優化方法，它可以使複雜度為O(MN)的求和，求方差等運算降低到O(1)或近似于O(1)的複雜度，它的缺點是不支援多尺度。
第一個提出Haar特征快速計算方法的是CVPR2001上的那篇經典論文Rapid Object Detection using a Boosted Cascade of Simple Features ，它提出了integral 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、将矩形模闆（紫色）從左上角（0，0）開始，逐像素向右滑動，到達行末時，矩形移動到下一行的開頭（0，1），如此反複，每移動到一個新位置時，計算矩形内的像素和，儲存在數組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的C++示例代碼，謹供參考
.h代碼
#pragma once
typedef unsigned char uchar;
class Boxfilter
{
public:
Boxfilter(void);
~Boxfilter(void);
void init(int width, int height, int mwidth=5, int mheight=5);
void boxfilter(unsigned char* img);
public:
float getMean(int x, int y); //以x,y為中心點，mwidth,mheight為直徑的局部區域,下同
float getVar(int x, int y);
int getSum(int x, int y);
int getSquareSum(int x, int y);
int getLocalSize();
private:
int mwidth ;
int mheight ;
unsigned char* img;
int width;
int height;
int* f_sum;
int* f_sum2;
};
.cpp代碼
#include "Boxfilter.h"
#include <assert.h>
#include <string>
int* buff = 0;
int* buff2 = 0;
int boxwidth;
int boxheight;
Boxfilter::Boxfilter(void)
{
f_sum = 0;
f_sum2 = 0;
}
Boxfilter::~Boxfilter(void)
{
if(f_sum) delete[] f_sum;
if(f_sum2) delete[] f_sum2;
if(buff) delete[] buff;
if(buff2) delete[] buff2;
}
void Boxfilter::init(int width, int height, int mwidth, int mheight)
{
this->mwidth = mwidth;
this->mheight = mheight;
this->width = width;
this->height = height;
boxwidth = width - mwidth;
boxheight = height - mheight;
f_sum = new int[boxwidth *boxheight];
f_sum2 = new int[boxwidth *boxheight];
buff = new int[width];
buff2= new int[width];
}
void Boxfilter::boxfilter (unsigned char* img)
{
int j,x,y;
memset(buff, 0, width *sizeof(int));
memset(buff2, 0, width *sizeof(int));
memset(f_sum, 0, boxwidth *boxheight);
memset(f_sum2, 0, boxwidth *boxheight);
for(y=0; y<mheight; y++)
{
for(x=0; x<width; x++)
{
uchar pixel = img[y *width + x];
buff[x] += pixel;
buff2[x] += pixel*pixel;
}
}
for(y=0; y<height - mheight;y++)
{
int Xsum=0;
int Xsum2=0;
for(j=0; j<mwidth; j++)
{
Xsum += buff[j];
Xsum2 += buff2[j];
}
for(x=0; x<width - mwidth; x++)
{
if(x!=0)
{
Xsum = Xsum-buff[x-1]+buff[mwidth-1+x];
Xsum2 = Xsum2-buff2[x-1]+buff2[mwidth-1+x];
}
f_sum[y*(width - mwidth)+x] = (float) Xsum ;
f_sum2[y*(width - mwidth)+x] = Xsum2;
}
for(x=0; x<width; x++)
{
uchar pixel = img[y *width + x];
uchar pixel2 = img[(y+mheight) *width + x];
buff[x] = buff[x] - pixel + pixel2;
buff2[x] = buff2[x] - pixel*pixel + pixel2*pixel2;
}
}
}
float Boxfilter::getMean(int x, int y)
{
return getSum(x,y) / (float)(mwidth*mheight);
}
float Boxfilter::getVar(int x, int y)
{
float mean = getMean(x, y);
return (float)getSquareSum(x, y)/(mwidth *mheight) - mean*mean;
}
int Boxfilter::getSquareSum(int x, int y)
{
if(y>mheight/2 && y<height - mheight/2 && x>mwidth/2 && x<width - mwidth/2)
return f_sum2[(y - mheight/2) *boxwidth + (x - mwidth/2)];
else
return -1;
}
int Boxfilter::getSum(int x, int y)
{
if(y>mheight/2 && y<height - mheight/2 && x>mwidth/2 && x<width - mwidth/2)
return f_sum[(y - mheight/2) *boxwidth + (x - mwidth/2)];
else
return -1;
}
int Boxfilter::getLocalSize()
{
return mwidth > mheight ? mwidth : mheight;
}
測試
// cv2.4 test.cpp : 定義控制台應用程式的入口點。
//
#include "stdafx.h"
#include "opencv2/opencv.hpp"
#include "Boxfilter.h"
#include <iostream>
using namespace cv;
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
Mat src = imread("C:\\Documents and Settings\\Administrator\\桌面\\img1.png",0);
Boxfilter box;
box.init(src.cols, src.rows, 5, 5);
box.boxfilter((uchar*)src.data);
int x = 50, y = 50;
float a = box.getMean(x, y); //求出以(x,y)為中心的矩形的均值
float b = box.getVar(x, y);
int c = box.getSum(x, y);
int d = box.getSquareSum(x, y);
int e = box.getLocalSize();
cout<<"mean: " <<a<<endl;
cout<<"var: " <<b<<endl;
cout<<"sum: " <<c<<endl;
cout<<"squaresum: " <<d<<endl;
cout<<"size: " <<e<<endl;
getchar();
return 0;
}
以上來自博文http://www.cnblogs.com/easymind223/archive/2012/11/13/2768680.html
下面是boxfilter的MATLAB代碼
function imDst = boxfilter(imSrc, r)
% BOXFILTER O(1) time box filtering using cumulative sum
%
% - Definition imDst(x, y)=sum(sum(imSrc(x-r:x+r,y-r:y+r)));
% - Running time independent of r;
% - Equivalent to the function: colfilt(imSrc, [2*r+1, 2*r+1], 'sliding', @sum);
% - But much faster.
[hei, wid] = size(imSrc);
imDst = zeros(size(imSrc));
%cumulative sum over Y axis
imCum = cumsum(imSrc, 1);
%difference over Y axis
imDst(1:r+1, :) = imCum(1+r:2*r+1, :);
imDst(r+2:hei-r, :) = imCum(2*r+2:hei, :) - imCum(1:hei-2*r-1, :);
imDst(hei-r+1:hei, :) = repmat(imCum(hei, :), [r, 1]) - imCum(hei-2*r:hei-r-1, :);
%cumulative sum over X axis
imCum = cumsum(imDst, 2);
%difference over Y axis
imDst(:, 1:r+1) = imCum(:, 1+r:2*r+1);
imDst(:, r+2:wid-r) = imCum(:, 2*r+2:wid) - imCum(:, 1:wid-2*r-1);
imDst(:, wid-r+1:wid) = repmat(imCum(:, wid), [1, r]) - imCum(:, wid-2*r:wid-r-1);
end