Rapid Object Detection using a Boosted Cascade of Simple Feature笔记

摘要

本文描述了一种用于视觉目标检测的机器学习方法，该方法能够非常快速地处理图像并实现高检测率。这项工作有三个主要贡献。第一个是 “积分图像”，可以被用来快速计算特征；第二个是基于AdaBoost的学习算法，可以从很大的数据集中筛选出少量的关键视觉特征并形成更加高效的分类器；第三个是以“级联”形式不断合并分类器的方法，该方法使得图像的背景区域被很快丢弃，从而将更多的计算放在可能是目标的区域上。级联可以被看作是一种对象特定的关注焦点机制，与以前的方法不同，它提供了统计保证，即丢弃的区域不太可能包含感兴趣的对象。在人脸检测领域，该系统产生的检测率与以前最好的系统差不多。在实时应用中，检测器以每秒15帧的速度运行，而无需采取图像差分或肤色检测。

积分图像

1、什么是Haar特征？

Harr-like特征是检测图像特征的一种算子，可以将它看做一个定大的卷积核。Haar特征是一种反映图像的灰度变化的，像素分模块求差值的一种特征。它分为三类：边缘特征、线性特征、中心特征。用黑白两种矩形框组合成特征模板，在特征模板内用 黑色矩形像素和 减去 白色矩形像素和来表示这个模版的特征值。

2、积分图

本篇论文第一个创新点就在使用积分图来简化Harr-like特征的计算，


可以通过积分图很快的计算其中某一块的值之和。具体和算法中二位前缀和类似（基于立在一维前缀和的基础上，现在所求是矩阵内一个任意的子矩阵的数的和，这样的问题就可以用二维前缀和进行求解）。
例如上图矩形ABCD，假设Sa为A点积分图的值，Sb为B点积分图的值，以此类推。那么用Sa-Sb-Sc+Sd就可以算出这个区域的面积。一共需要3次加法。如果不使用用积分图，只对原始图进行计算，这个复杂度应该是n²。大大减少了特征点的计算时间。
具体公式如下：

(其中s(x, y)是累计行和，s(x，−1)= 0，和ii(−1,y) = 0)积分图像可以对原始图像进行一次计算。

2、使用AdaBoost训练数据

1、分类

使用很多个特征提取器后可以得到大量的特征值。人工给这些东西打上标签，告诉他们哪些是人脸，哪些不是。先拿这些标签和特征值来简单的分个类。一幅图像矩形特征的数量会十分巨大，如果全部都进行处理，则也是一件很麻烦的事。实验证实了假说：极少数的特征结合起来，也能形成有效的分类器。问题是，如何找到这些特征。为实现这一目标，设计的弱学习算法被用来选择可以使得正例和负例得到最佳分离的单一矩形特征。对于每一个特征，弱学习决定最优阈值分类功能，这样可以使错误分类的数目最少。

j代表第j个分类器，pj保证两边符号相等，seta是一个阀值，fj是特征值。

2、使用AdaBoost算法

AdaBoost是Adaptive Boosting的简称，属于集成算法(Ensemble Method)中Boosting类别中的一种。AdaBoost是非常成功的机器学习算法，由Yoav Freund和RobertSchapire于1995年提出，他们因此获得了2003年的哥德尔奖（Gödel Prize）。本文将从下面几个方面对AdaBoost进行展开：

不同点在于Grandient Boost改变的是本轮训练的样本标签，而AdaBoost 则侧重于调整本轮样本的样本权重，从而改变样本的分布

1. 确定样本集
2. 初始化样本数据的权重，如每个样本的权重为1/n(假设样本个数为n)
3. 进行1，2，…，T轮迭代
   

初始化：其中m和I分别是分类错误和正确的个数,yi=0 时候 w1i=1/m，yi=1 时候w1i=1/l

a. 归一化样本权重

b. 对样本集进行训练，并计算训练误差（使用分类公式得出结果与真实值的差值乘以权重得到总和为误差）

c. 选择误差最小的分类器作为本轮的分类器

d. 根据预测结果更新样本数据的权重：预测错误样本增加权重，预测正确样本降低权重（误差为0，xi被分类成功，否则增加权重）

3、级联

构建级联分类器的算法能减少计算时间改善检测性能。它的主要观点是分类器规模越小就越高效。这种分类器在检测几乎所有正例的同时剔除许多负子窗口（优化调整分类器阈值使得负误视率(fn)接近零）。在调用较复杂的分类器之前，先使用相对简单的分类器来剔除大多数子窗口，以实现低正误视率（fp）。但是是过多的分类器会增加系统的计算量。
检测过程的整体形式是一个退化的决策树，称之为“级联”。

级联中的阶段由使用AdaEioost训练分类器构建，然后调整阈值以最小负误视率（fn）。请注意，默认的AdaEioost阈值被设计为在训练数据上产生低错误率。一般来说，较低的阈值产生较高的检测率和较高的正误视率(fp)。
例如，一个两特征强分类器通过降低阈值，达到最小的负误视后，可以构成一个优秀的第一阶段分类器。测量一个特定的训练集时，阈值可以进行调整，最后达到100%的人脸检测率和40％的正误视率。使用的两个特征如图。

通过级联，尽可能在早的阶段剔除尽可能多的负例。但，后续的分类器所面临的任务要比前一个更难。这些通过第一阶段的例子比典型例子更“难”。这些例子推动ROC特征曲线向下。在给定检测率的情况下，更深层次分类器有着相应较高的正误视率(fp)。

1、训练级联分类器

级联的训练过程有两个方面的权衡。多数情况下，具有更多特征的分类器可以达到较高的检测率和较低的正误视率，但同时也需要更多的时间来计算。原则上，可以定义一个优化框架，其中:i)分类器阶段的数量，ii)每个阶段的特征数量，以及iii)每个阶段的阈值，为了最小化评估特征的预期数量而进行权衡。
实践中可以用一个非常简单的框架产生一个有效的分类器。级联中的每个阶段会降低正误视率（fp）并且减小了检测率，但目标旨在最小化正误视率(fp)和最大化检测率。于是，在训练每个阶段时，不断增加特征，直到检测率和正误视率(fp)的目标实现（这些比率是通过将探测器在验证设置上测试而得的）。同时添加阶段数，直到总体目标的正误视(fp)和检测率得到满足为止。

2、检测器级联讨论

级联的训练过程有两个方面的权衡。多数情况下，具有更多特征的分类器可以达到较高的检测率和较低的正误视率，但同时也需要更多的时间来计算。完整的人脸检测级联已经拥有超过6000个特征的38个阶段。尽管如此，级联结构还是能够缩短平均检测时间。在一个复杂的包含507张人脸和7500万个子窗口的数据集中，人脸检测是每个子窗口由平均10个特征来评估。
Rowley等人描述过一个类似于级联的概念。他们使用了两个检测网络，先用更快但相对不准确的网络筛选图像，这样做是为了使较慢但更准确的网络找到候选区域。虽然这很难准确判断，但是目前速度最快的脸部探测器。
检测过程中的级联结构基本上是退化决策树，因此涉及到了Amit和Geman的工作。，Amit和Geman建议不再使用固定一个探测器的技术，而他们提出一个不寻常的合作共现，即简单的图像特征用于触发评价一个更为复杂的检测过程。完整的检测过程中不需要对潜在的图像位置和范围进行估计。
在最近的工作中Fleuret和Geman已经提交了一种人脸检测技术，它以“链测试”为主调，用来表示在某一特定范围和位置人脸是否存在。由Fleuret和Geman测量的图像属性，细尺度边界的分离，与简单存在于所有尺度且某种程度可辨别的矩阵特征有很大的不同。这两种方法的基本原理也存在根本上的差异。Fleuret和Geman的学习过程的目的是密度估计和密度辨别，而的探测器是单纯的辨别。最后，Fleuret和Geman的方法中的正误视率（fp）似乎也比以前的如Rowley等人的方法中的更高,不幸的是，这篇论文没有报道这类定量结果,所包含的示例图像每个都有2到10个误报。

4、实验结果

训练一个38层级联分类器，用来检测正面直立人脸。为了训练分类器，使用了一系列包含人脸和不包含人脸的图片。人脸训练集由4916个手标的人脸组成，都缩放和对齐成24×24像素的基本块。提取人脸的图片是在使用随机爬虫在万维网上下载。一训练检测器的没有人脸的子窗口来自9544张图片，都已经进行人工检查，确定不包含任何人脸。在这些没有人脸的图片中，子窗口共有大概3.5亿个。
开始五层检测器中特征的数量分别为1、10、25、25和50。剩下的各层包含的特征数量急剧增多。特征总数是6061个。
在级联中的每个分类器都经过4916个受训人脸（加上它们的垂直镜像，一共有9832个受训人脸）和10000个无人脸的子窗口（同样它们的尺寸都是24×24），使用自适应增强训练程序训练。对于最初的含一个特征的分类器，无人脸训练实例从一系列9544张没有人脸的图片中随机选择出子窗口。用来训练随后的层的没有人脸实例是通过扫描部分级联的无人脸图像以及收集正误视率而得的。每一层收集的像这样无人脸的子窗口的最大值是10000。

1、图像处理

所有用来训练的子窗口实例都经过方差标准化达到最小值，尽量减少不同光照条件的影响。因此，在检测中也必须规范化。一个图像子窗口的方差可以使用一对积分图像快速计算。

此处 左边是标准差， m是均值，而 x是在子窗口中的像素值。子窗口的均值可以由积分图像计算得出。像素的平方和可以由一个图像的积分图像的平方得出（即，两个积分图像在扫描进程中使用）。
在扫描图像中，图像的规范化可通过后乘特征值达到，而不是预先乘以像素值。

2、扫描检测器

检测器需要在多尺度和定位下对图像进行扫描。尺度缩放更多是由缩放检测器自身而不是缩放图像得到。这个进程的意义在于特征可以在任意尺度下评估。使用1.25的间隔的可以得到良好结果。
检测器也根据定位扫描。后续位置的获得是通过将窗口平移⊿个像素获得的。这个平移程序受检测器的尺度影响：若当前尺度是s，窗口将移动[s⊿]，这里[]是指取整操作。
⊿的选择不仅影响到检测器的速度还影响到检测精度。展示的结果是取了⊿=1.0。通过设定⊿=1.5，实现一个有意义的加速，而精度只有微弱降低。

3、多检测的整合

因为最终检测器对于传递和扫描中的微小变化都很敏感，在一幅扫描图像中每个人脸通常会得到多检测结果，一些类型的正误视率也是如此。在实际应用中每个人脸返回一个最终检测结果才显得比较有意义。在这些试验中，用非常简便的模式合并检测结果。首先把一系列检测分割成许多不相交的子集。若两个检测结果的边界区重叠了，那么它们就是相同子集的。每个部分产生单个最终检测结果。最后的边界区的角落定义为一个集合中所有检测结果的角落平均值。

5、结论

提出了一种目标检测方法，该方法在实现高检测精度的同时减少了计算时间。该方法被用于构建一个人脸检测系统，其速度比以往任何方法都快约15倍。
本文汇集了新的算法，表示和见解，这些都是相当通用的，很可能在计算机视觉和图像处理中有更广泛的应用。
最后，本文给出了一组详细的实验，该实验是在一个复杂的人脸检测数据集上进行的。该数据集包括在非常广泛的条件下的人脸，包括:照明、比例、姿势和相机变化。在如此庞大和复杂的数据集上进行实验是困难和耗时的。然而，在这些条件下工作的系统不太可能是脆弱的或局限于单一的一组条件。更重要的是，从这个数据集得出的结论不太可能是实验性的人工产物。