毕业论文整理（五）：Haar像素值特征
Haar特征是我用得最多的一个特征了。Haar特征的鲁棒性并不好，它常常用于颜色或者轮廓较为明显的、波动不大的图像，比如人脸识别中识别眼睛、鼻子的位置。尽管如此，用Haar特征处理一般图像分割已经足够使用了。
Haar特征设计思想
Haar特征(Haar-like Feature)的名称来源于Haar小波(Haar Wavelet)变换，最早由Papageorgiou在论文《A General Framework for Object Detection》中提出。那个时期，用RGB图像像素值来处理特征会产生很大的计算量，Papageorgiou等人就提出了用Haar小波变换来处理特征的想法。在2001年，Viola和Jones在论文《Rapid Object Detection using a Boosted Cascade of Simple Features》中基于这个想法进一步提出Haar特征，产生了很大的影响。他们注意到人的面部是可以用一些矩形特征进行描述的，比如对于浅色皮肤的人来说，鼻梁两侧的颜色比鼻梁的颜色要深一些，眼睛、嘴巴等地方的颜色都比周围面部皮肤的颜色要深。因此，可以用矩形像素变化来表现颜色深浅，这就是Haar特征的来源。
Haar特征描述
Haar特征主要分为4大类，分别是边缘特征、线性特征、中心特征和对角线特征，本质就是用下图的各类特征模板中黑色矩形的所有像素值减去白色矩形的所有像素值的和（为了像素数目平衡，颜色块少的一项将乘以系数），能够反映出不同方向上一些物体轮廓、灰度变化的情况。
Haar特征计算方法
很简单，黑色区域像素值和减去白色像素值的和，如果色块数目不一样，用加权保持一致：
$$ Haar = \frac{LCM(W, B)}{B} \times \sum{Pixel_B} - \frac{LCM(W, B)}{W} \times \sum{Pixel_W} $$
例如白-黑-白模板，Haar=2*黑-1*白。然而由于Haar特征可以更改模板类型、模板大小、模板位置，仅一幅图像就有不计其数的Haar特征，比如Viola提出的基本特征模板，在24×24像素的窗口中任意排列可以产生180000个特征。如果要从头开始逐一计算，性能代价将是巨大的。Viola和Jones提出了快速计算Haar特征的方法：积分图(Integral Image，II)，解决了这个难题，将Haar特征计算的时间复杂度降低到了常数。
积分图算法
积分图算法其实是动态规划，只需要遍历一次图像，遍历过程中保存图像上每个点左上角所有点像素值的和的矩阵，当计算特征的时候，通过简单的容斥加减运算就能够以O(1)的时间复杂度得到Haar特征值。
先举个实际的例子：
- 第一个矩阵原始图像像素值；
- 第二个矩阵是行累加和s矩阵，最左边是辅助的0保证不越界，保存从左到右扫描的像素值和，例如11=3+1+7；
- 第三个矩阵是积分图，保存着左上角的像素值和，计算方式是上一行+s矩阵值，例如46=35+11=(3+8+9+6+7+2)+3+1+7，黑色线框部分是Haar模板区域，这里使用白-黑模板；
- 第四个矩阵中阴影部分是“黑色矩形像素”周围的积分图点。
如果要计算黑色阴影的像素和，只需要进行简单的容差计算：
$$ \begin{aligned} \sum{Pixel_B} & = II(C) - II(B) - II(D) + II(A) \\ & = (红+蓝+绿+黄) - (红+绿) - (红+蓝) + (红) \\ & = 黄 \\ & = 92 - 30 - 66 + 21 \\ & = 17 \\ & = 4 + 3 + 3 + 2 + 3 + 2 \\ \end{aligned} $$
这样，任意要求解的区域像素值和都可以通过加减得到。积分图算法描述如下：
- 用s(i,j)表示行方向累加和，初始化s(i,-1) = 0
- 用ii(i,j)表示积分图，初始化(-1,i)=0
- 从上到下，从左到右，逐行扫描图像，递归计算每个像素(i,j)行方向的累加和，s(i,j)和积分图像ii(i,j)的值，直到扫描到右下角停止：
$$ \begin{aligned} s(i, j) & = s(i, j-1) + Pixel(i, j) \\ ii(i, j) & = ii(i-1, j) + s(i, j) \end{aligned} $$
- 设原始图像如图所示，需要计算D区域的像素和，则计算公式为：Sum = II(4)-II(2)-II(3)+II(1)
如何选择Haar特征
那么多Haar特征，该如何选择有效的特征呢？官方的做法是使用Adaboost。但是如果你的算法具有随机特性，可以直接随机选择模板大小、模板位置、模板类型。例如NAFs就是一个非常好的具有随机特性的算法。
总结
Haar特征还有很多变种，例如倾斜45°、任意旋转等模板，但是其实得不偿失，这本来就是一个简单的特征，弄得再复杂对模型的精确度提升都不大，还不如直接考虑高级的SIFT等强特征。
毕业论文整理（五）：Haar像素值特征
