VJ框架与⼈脸检测物体检测详解
Viola-Jones Object Detection Framework
1. VJ Framework
1.1 Overview
本⽂详细阐述 Viola-Joines ⼈脸检测/物体检测 实时处理框架，主要参考 Robust Real-Time Face Detection 这篇论⽂以及本⼈⼯程实践经验。论⽂中 VJ 总结其主要贡献有三⽅⾯：
Feature: Haar-based feature (wavelet)
Learning algorithm: AdaBoost
Attentional Cascade
其中 AdaBoost 本⼈有专门⼀篇⽂章讲解（”AdaBoost 详解”），这⾥直接跳过，当然，AdaBoost 模型在这⾥的应⽤是相当成功的。本⽂主要展开 Feature 和 Attentional Cascade 这个视觉和⼯程上的内容；这俩个贡献极⼤地提升了算法性能，实现了实时物体检测。
本节会梳理⼀下 VJ 框架的 runtime 检测流程和模型训练流程；之后⼩节展开讨论 Feature 和 Attentional Cascade 话题。
1.2 检测流程
这⾥把物体检测识别流程整体梳理⼀遍。我们的输⼊是⼀个⼀张待识别原始⼤图，输出是使⽤窗⼝框出⼤图中所有被检测到的⽬标（例如最常⽤的⼈脸）
图⽚预处理
降采样，原始⼤图size太⼤处理太慢，例如把 1000*1000 的原始图⽚降为 500*500
像素 intensity 压缩，⼀般的图⽚是3通道（）的RGB，我们会把它压缩到单通道的 intensity()
特征预处理（Feature）
这⾥会根据 Feature 相关思路，计算出待检测图⽚的 Integral Image，VJ 框架通过这项优化，极⼤地加速训练和识别过程
滑窗检测
先以基础检测尺⼨（训练时使⽤的24*24）在待检测图⽚上逐次划过所有位置（x轴+y轴全量遍历，当然 stride 可以设置⼤⼀点），在所有窗⼝上判断其是否为⽬标；并且会逐渐扩⼤检测窗⼝尺度（如每次扩⼤1.5倍）完成各个尺度下图⽚的检测。滑窗⽅式把检测问题转换为了⼆分类识别问题，但是这⾥需要识别的数量级巨⼤，500*500 的⼀张处理后待检测图⽚，轻轻松松包含10万个需要确认的检测窗⼝
图⽚检测（AdaBoost + Cascade ⼆分类器）
滑窗过程中每⼀个检测窗⼝都需要调⽤图⽚检测来确认结果，这⾥实际上利⽤了 Attentional Cascade 结构极⼤加速了判断过程：对于明显不是检测⽬标的窗⼝⽴刻拒绝，⽽对于很像检测⽬标的窗⼝则逐渐地使⽤更多资源判断，并最终确认得到⽬标
另外，检测过程中使⽤的特征，基于之前计算好的 Integral Image，可以通过⼏个加减计算直接得到，⾮常快速；并且 Cascade 基础是 AdaBoost，⽽ AdaBoost 基础是 Decision Stump，所以执⾏效率⾮常⾼
检测结果合并
最后，所有的 positive 检测窗⼝会进⾏合并（同⼀/不同尺度 的滑窗都有可能重复圈定⼀个⽬标），并消除⼀些错误结果。
VJ 论⽂最后有提到⼀个简单的⽅法，就是把 overlapping 的检测结果分到⼀个组⾥，每个组以组内结果的均值输出⼀个最终展⽰结果；false positive 被分配到的组可能只有⼀个检测结果，可以直接⼲掉。当然，实践中肯定可以使⽤更复杂的策略、算法来进⾏合并，且消除⼀些 false positive。
1.3 训练流程
1.2 中的“图⽚检测 ”使⽤的就是我们训练的基于 AdaBoost 的 Cascade 结构模型，这⾥概述⼀下训练过程。这⾥明确⼀下⽬标：输⼊⼀张确定size的⼩图⽚，输出确认这个⼩图⽚描述的是否是检测⽬标（其实这就把检测问题转化为粗略识别⼀类物体的⼆分类问题）。
样本准备
⾸先要确认⼀个检测窗⼝尺⼨，VJ 原⽂是 24*24，这个是之后运⾏时滑窗检测的基础⽬标窗⼝ size，当然训练集需要使⽤这个size。
正样本；⼀般数千到数万张标准 size 的⽬标物体⼩图
负样本；Cascade 结构极其吃负样本，作者之前训练时使⽤了10亿量级的负样本。当然，这么⼤的量级是训练过程中动态⽣成的，原始素材是数千到数万张不包含⽬标物体的⼤图（可以是2000*2000的各种⾃然景⾊图⽚啊什么的）；训练的时候可以从⼤图中动态切出来⼤量的标准 size 的模型使⽤负样
本
训练集和验证集；需要切出⼀个 validation set（例如和 training set 1：1 ⼤⼩）来持续验证集成过程，这个验证集是静态的，但是会直接影响整个 Cascade 结构构建，对于 VJ 这⼀体系⾮常重要（所以感觉还是⼤⼀点好~）
Cascade 训练
逐层训练出 Cascade 结构，每⼀层是⼀个 AdaBoost；每完成⼀层训练之后，都要为下⼀层重新准备已有结构⽆法 reject 的负样本（所以特别吃负样本），具体细节后续展开。
输出整个 Cascade 模型所有参数，供检测流程直接使⽤
2. Feature
特征是 VJ 框架的核⼼，这⾥使⽤ Haar 特征。对于⼀般的机器学习来说，都需要 feature extract 的步骤，从原始数据中，提取出合适的特征来供模型学习，这⾥的 Haar 特征有2个特点以及1个重要的加速计算⽅法，本节依次展开讨论。
2.1 过完备表达 overcomplete representation
数量级暴增
对于我们使⽤的基础 size 24*24，总计有 576 个像素点，如果直接使⽤像素做特征的话只有 576 个整数（0到255的图像 intensity）特征。
但是使⽤ Haar 特征的话，原论⽂中提取出 162,336 个整数特征，这个量级远远⼤于原始像素数量。实际上原始像素能够完整地表达这张图⽚的所有信息，但是我们使⽤了相⽐之下数量多的多 haar 特征去表达图⽚，称为 overcomplete representation。实际上，原⽂使⽤5种经典提取模板，我们其实还可以加⼊其它模板进⼀步扩充特征，更加地 overcomplete。
既有数量，更有价值
当然，overcomplete 光有数量是不够的，如果全部都是⼀些没有意义的特征，再多也⽤。但是，haar 特征有潜能捕捉到重要信息。每个haar 特征可以看作是在图⽚的特定范围提取某⼀特定信号的结果，本质上其实是 ⼩波变换 wavelet。这些特征能够很好的捕捉到边缘、线条、颜⾊以及⼀些简单的图像模式。虽然都是简单、粗糙的模式，但这正好构成了 AdaBoost 中 weak classifier 的基础，充分的 haar 特征表达为后续的模型学习提供更多可能。
Haar 简介
这⾥简单阐述这种特征的提取⽅式。下⾯这张图⽚摘⾃ VJ 原论⽂，展⽰了4种不同模板的 haar 特征提取。提取的时候，会使⽤相关模板在图⽚上滑窗，在任意位置上求取 rectangle 中⽩⾊区域像素和减去⿊⾊区域像素和，所以结果是⼀个整数。另外，各个模板会 scale 到各个可能的尺⼨依次滑窗求特征，所以最后能产出那么多的特征。（注意，这⾥说的特征提取滑窗，是 haar 特征在基础 size 的检测窗⼝上滑动；⽽后续说的检测流程滑窗，是检测窗⼝在待检测图⽚上滑动；是⼆个层次上的东西哦）
Figure 1. Feature Extraction of Haar-like (from VJ)
另外，⼤部分的特征其实是没有意义的，但是 AdaBoost 能够将少数⽜逼的、很有效的、甚⾄我们直接看起来很有解释意义的特征挖掘出来。下图是 VJ 展⽰它们模型挖掘到的最重要特征：
Figure 2. Some Great Haar-like Features for Face-detection (from VJ)
这是很有解释性的 Haar 特征，模型学会了通过眼睛这⼀位置的显著对⽐度，来区分图⽚是否是⼈脸。
validation框架2.2 缩放不变性 scaling invariability
Haar 特征还有⼀个关键特性就是 scaling invariability。当检测窗⼝放⼤时，Haar 模板对应的⽩⾊、⿊
⾊区域是以⼀致的⽐例扩⼤的，所以原 Haar 特征的意义不变；Haar 本⾝求取的就是⼀个相对值。
在实践中，虽然我们整个模型训练只是基于 size 24*24 的检测窗⼝；但是，真正检测时需要对这个基础 size scale up，例如我们需要对24*24、48*48、96*96 的检测窗⼝都要能判定是否为⽬标物体。这对于 Haar 特征太简单了，只要直接对 Haar 的提取窗⼝作同样的scale up，就可以近似表达出任意 size 检测窗⼝在基础 size 检测窗⼝上的特征值；所以我们基于 Haar 特征训练的模型可以⾼效地⽆缝地直接应⽤在各个 scale 的检测窗⼝上。
额外提⼀点，如果没有 scaling invariability 的话，我们只能处理固定 size 的检测窗⼝。按照 VJ 原⽂说法的话需要对待检测图⽚作pyramid（待检测⼤图 scale down 到各个尺度，类似⾦字塔），各尺度上都使⽤基础 size 的检测窗⼝滑窗检测。这种⽅法光是 pyramid 构建就已经造成巨⼤性能消耗。
2.3 计算加速 Integral Image
实际上 VJ 的主要贡献在于 Integral Image，这⼀⽅法使 Haar 特征计算变得⾮常迅速，使整个系统性能⼤幅提升。积分图 Integral Image 由原待检测图⽚⽣成，它们 size ⼀致，积分图每⼀的值为该点在原图上整个左上区域（包括该点）的像素和（ 表⽰ integral image， 表⽰原图）：
积分图本⾝的计算复杂度是 （待检测图⽚ size M*N），计算过程中使⽤了 dynamic planning 的思想，
引⼊另⼀个中间变量 作为cumulative row sum 即按⾏积分；初始化 ，按以下公式在原图上迭代⼀遍，即得到积分图 ：
使⽤积分图计算任意 rectangle 范围的像素和⾮常简单，所以 Haar 特征的计算就很简单，如下图实例：The sum within D can be computed as 4 - 2 - 3 + 1
Figure 3. Calculating the sum of pixels from integral image is so easy (from VJ)
3. Attentional Cascade
这是 VJ 的另⼀重⼤贡献，Attentional Cascade 的核⼼思想在于：对于明显不是检测⽬标的窗⼝⽴刻拒绝，⽽对于很像检测⽬标的窗⼝则逐渐地使⽤更多资源判断，并最终确认得到⽬标。其结构如下图：
Figure 4. Structure of Cascade (from VJ)
3.1 性能提升
按照 VJ 原⽂估计，使⽤上图的 Cascade 结构获得了10倍以上的性能，这⾥的提升可以分为俩个⽅⾯：
层次结构
这⾥使⽤了多个层次的模型，图中的 1、2、3 都是 AdaBoost（Cascade 在 ensemble 的基础上再 ensemble 了⼀次~），只有逐层模型判断都是 True 才最终接受，任何⼀层模型 False 就直接拒绝，不会进⾏进⼀步处理。
越靠前的层次越简单
更重要的是，层次越靠前的 AdaBoost 可以越简单（集成的 weak classifer 数量更少）。原论⽂上述“1”这⼀ AdaBoost 只集成了
2 个 decision stump，但是实践中却能 Reject 约 50% 的检测窗⼝，这对于性能上的贡献，是决定性的！
3.2 重要假设
Cascade 能够⼤幅提升检测性能是因为： 真实检测任务中绝⼤多数的检测窗⼝都不是⽬标。
就⼈脸检测应⽤到门禁系统来说，在现实中运⾏的⼤多数时间，采集到的图⽚根本就不包含⼈脸，⼀张待检测图⽚对应的成千上万检测窗⼝都是⽆效检测。并且，就算真的有⼈脸出现，往往也就⼀个⼈脸，可能也就对应了⼏⼗个检测窗⼝，绝⼤多数的窗⼝还是⽆效的。
所以系统对 negative 结果的⾼效率识别极其重要，Cascade 正是基于此⽬标设计的。其试图尽量⽤最简单（性能消耗最⼩）的⽅法在最初的层次上把 negative 样本 reject。例如，假如我们的系统对着天空，或者某⼀统⼀颜⾊的背景，可能只需要⼀个 Decision Stump 就可以把 99% 以上的检测窗⼝⼲掉，有些窗⼝确实太明显不可能是⼈脸，这可能直接就带来性能成百上千倍的提升了。
另外，其实 Cascade 对 positive 识别的性能消耗反⽽是增加的，因为这⾄少增加了层次间跳转消耗，⽽⾮⼀次计算得到结果；但
是，negative 的性能提升完全抵消了这⼀消耗。所以算法模型根据业务特点作调整很重要。
3.3 额外特性，需要海量 negative 样本
Cascade 除了贡献的⼤幅性能增长外，还有⼀个额外的特点，就是需要使⽤⼤量 negative 样本训练。Cascade 的训练细节（下⼀⼩节详述）上，每个层次的训练集正例是⼀致的，但是负例需要选取上⼀层次的 false positive 数据，这样 Cascade 的 false positive 会随层次逐渐降低（检测越来越精确）。这个特性可以算⼀把双刃剑：
正⾯
整个系统学习过的 negative 样本数量级⼤幅度增长。如果使⽤单个模型，我们 10 thousand 正例 对应
100 thousand 负例 可能已经是极限（太不均衡就没法学了）；但是 Cascade 可以怼出 1 billion 量级的负例。Cascade 每个层次只学习之前层次⽆法正确处理的 negative 样本，所以较深层次能更加专注地去解决⼀些 hard 样本，系统对 negative 的准确处理能⼒应该是提升的。再加上现实中绝⼤多数检测窗⼝是 negative 的，所以这很有意义。
反⾯
这⼀特性也⼤幅提升了训练成本。这么量级的负例必然依赖动态⽣成，所以每当模型训练完成⼀个层次，就需要重新准备下⼀个层次的训练集，准备过程中可能会随机枚举 billion 量级的负例，并且每个负例都要在已有模型上测试⼀下，这⼀准备过程很耗时。并且，每⼀次负例准备完成，由于 AdaBoost 的训练特点，需要提取新负例的特征并对整个训练集重新排序（这属于 AdaBoost 的实现细节了），也很耗时。总之，训练层次很深的 Cascade 结构是⾮常耗时的（完爆单个 AdaBoost），并且数据集不好的话很难训练很深，作者也正在寻更好的数据集~
3.4 算法细节
分层原理
VJ 原⽂的⼀个⼩例⼦⾮常简洁地说明了 Cascade 的实现细节：
即是假设 Cascade 有 10 层，如果每⼀层保证⾄少 0.99 recall 且⾄多 0.3 的 false positive；那么整个 Cascade 的检测能⼒将⾮常可观地达到 0.9 recall 和 0.00001 false positive（即 0.99999 precision）！检测问题很 care precision，这是很不错的结果。
实现细节
Cascade 实现时，每个层次都有⼀个训练⽬标（recall+false positive），这个层次的 AdaBoost 每迭代累加⼀个 decision stump 后，会查看⼀下是否能达到这个⽬标；⼀旦达标就这⼀层次就完成训练了。
这确保各个层次尽量简单，其他进⼀步检测交给下⼀层次。只要每个层次都完成了⾃⼰的⼩⽬标，整个模型就能完成 Cascade ⽰例中叠加的魔法。当然，这⾥有额外的成本（2.5.3 中提到了），即某⼀层次使⽤的负样本是之前所有层次都识别失败（false positive）的负样本。
实践中，每⼀个层次的训练⽬标属于超参数，VJ 原⽂中也提到靠前的⼏个层次（当然越靠前越重要了）训练⽬标是⼿动调试的；后续层次可以设定⼀些固定⽬标（例如 recall 0.9，false positive 0.1）。这是⼀个检测精度与检测性能 tradeoff 的过程，检测精度要求越低则相应层次模型复杂度度越低性能越快，但必须保证每⼀层次的⼩⽬标都到位，才能得到最终符合期望的整体模型。另外，各个层次的⼩⽬标达成，⼀般是⼀个从简到难的过程（因为 negative 样本越来越 hard）；第⼀个层次的 A
daBoost 可能只需要 2 个feature，第⼆个层次可能接近 10 个，到深度的层次可能需要成百上千个 feature。VJ 原作者的最终的 Cascade 包含 38 个层次，总计 6060 个
feature（decision stump）。
Cascade 中 AdaBoost 的训练 trick
Cascade 的各层次训练⼩⽬标是⾮常好的 recall + 有点糟糕的 false positive，这本⾝是不均衡的。但是，AdaBoost 算法本⾝优化的⽬标是均衡的 Accuracy，是完全不⼀样，我们需要对 AdaBoost 作⼀点修改。
每次 AdaBoost 完成⼀次迭代，新加⼊⼀个 decision stump 后，我们会测试其是否满⾜ recall + false positive 的要求，false positive 的要求是很松的，如果这个要求都达不到我们就认为测试失败，应该继续迭代 AdaBoost；但如果只是 recall 不够⾼，我会回引⼊⼀个松弛参数 ，衰减 AdaBoost 的最终判别式：
上式原始 AdaBoost 判别式中 ，这⾥逐渐衰减这个参数，会使 AdaBoost 判定 positive 更容易，所以 recall 上升，false positive 上升。
我们持续调整 （从 1.0 到 0.0），如果当前 AdaBoost 到底是否能达成⼩⽬标，如果发现彻底不能达
成（松弛过程中 false positive 超过⼩⽬标），就认为测试失败，应该继续迭代 AdaBoost。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。