首页 > 代码库 > Histogram of Oriented Gradients for Human Detection 翻译
Histogram of Oriented Gradients for Human Detection 翻译
Navneet Dalal，Bill Triggs
摘要
我们研究了视觉目标检测的特征集问题，并用线性SVM方法进行人体检测来测试，通过与当前的基于边缘和梯度的描述子进行实验对比，得出方向梯度直方图(Histograms of Oriented Gradient,HOG)描述子在行人检测方面表现更加突出。我们研究了计算过程中每一阶段的影响，得出小尺度梯度(fine-scale gradients)、精细方向采样(fine orientation binning)、粗糙空域抽样(coarse spatial binning)以及重叠描述子块的局部对比度归一化(local contrastnormalization in overlapping descriptor blocks)都对最终结果有重要作用。这种方法在最初的MIT行人数据库上表现近乎完美，所以我们引入了一个更具挑战性的包含1800个不同姿势和背景的已标注人体数据集。
1 引言
由于人体姿势和外表的多变，在图像中检测人体是一项具有挑战性的工作。首先需要的就是一个强壮的特征集，使得在不同光照和背景下都能清晰地分辨出人体。我们研究了人体检测的特征集问题，局部归一化的HOG描述子相比于现存的特征集(包括小波[17,22])有更好的表现。相比于边缘方向直方图(EdgeOrientation Histograms[4,5])、SIFT([12])、形状上下文(Shape Contexts[1])，HOG是在网格密集的大小统一的细胞单元(dense grid of uniformlyspaced cells)上进行计算，而且为了提高性能，还采用了重叠的局部对比度归一化(overlapping local contrastnormalizations)。我们用行人检测(人体是大部分可见的并且基本上是直立的)进行测试，为了保证速度和简洁性，使用线性SVM作为分类器。HOG检测器在MIT的行人数据集([17,18])上表现相当好，所以我们又引入了一个更具挑战性的包含1800个不同姿势和背景的已标注人体数据集。正在进行的工作表明，我们的特征集对于其他基于形状的目标检测也同样好。
第2节中简要介绍了在人体检测上前人的研究工作，第3节是HOG方法的总体介绍，第4节介绍了我们使用的数据集，第5-6节是HOG方法的详细介绍以及不同处理阶段的实验结果，第7节是结论和总结。
2 前人的研究工作
在目标检测方向上有大量的文献，这里只列举与人体检测有关的论文[18,17,22,16,20]。[6]是一篇综述。Papageorgiou等[18]提出了一种使用纠正哈尔小波(rectified Haarwavelet)作为特征的多项式SVM行人检测方法，以及[17]中基于子窗口的改进方法。Depoortere等给出了论文[2]中方法的一个最优化版本。Gavrila和Philomen[8]采用一种更直接的方法，提取边缘图并将其与样本进行匹配，使用chamfer距离作为评判标准，这种方法已被用在一个实时行人检测系统中[7]。Viola等[22]提出了一种高效的运动人体检测器，使用AdaBoost来训练一串渐进复杂的基于类Haar小波和时空差的区域拒绝规则。Ronfard等[19]提出了一种关节式的身体检测器，他通过将基于SVM的肢体分类器合并到动态规划框架中的一阶和二阶高斯滤波来实现，与Felzenszwalb和Huttenlocher[3]，以及Ioffe和Forsyth[9]的方法相似。
Mikolajczyk等[16]提出了一种方向位置直方图和二值梯度幅值相结合的身体部位检测器，能够检测脸、头、以及身体上部或下部的前视或侧视轮廓。相比之下，我们的检测器结构更简单，使用单一检测窗口，但行人检测的效果更好。
3 算法概述
此节是HOG特征提取方法的概述，实现细节在第6节。此方法基于对稠密网格中归一化的局部方向梯度直方图的计算。相似的特征在过去十年中越来越多的被使用[4,5,12,15]。此类方法的基本观点是：局部目标的外表和形状可以被局部梯度或边缘方向的分布很好的描述，即使我们不知道对应的梯度和边缘的位置。在实际操作中，将图像分为小的细胞单元(cells)，每个细胞单元计算一个梯度方向(或边缘方向)直方图。为了对光照和阴影有更好的不变性，需要对直方图进行对比度归一化，可以通过将细胞单元组成更大的块(blocks)并归一化块内的所有细胞单元来实现。我们将归一化的块描述符叫做HOG描述子。将检测窗口中的所有块的HOG描述子组合起来就形成了最终的特征向量，然后使用SVM分类器进行人体检测，见图1。
图1
图1描述了我们的特征提取和目标检测流程。检测窗口划分为重叠的块，在块中计算HOG描述子，形成的特征向量放到线性SVM中进行目标/非目标的分类。检测窗口在整个图像的所有位置和尺度上进行扫描，并在输出的用来检测目标的金字塔上进行非极大值抑制，本文主要讲特征提取的过程。
方向直方图的使用已有很多先例[13,4,5]，但是直到Lowe的SIFT尺度不变特征点提取[12]，才算达到成熟。SIFT类型的方法在[12,14]的程序中表现相当出色。形状上下文[1]方法研究单元和块的形状，最初只使用边缘像素个数而不是方向直方图，就已经获得不错的结果。这些稀疏特征的成功，不禁使得作为稠密特征的HOG方法的效果和简易性黯然失色，我们希望我们的研究可以改变这一情况。特别地，我们的非正式实验表明，即使现在最好的基于特征点的方法，在人体检测方面比我们方法的错检率也要高上至少1-2个数量级，主要是因为这些基于特征点的检测器不能可靠地检测人体结构。
HOG和SIFT特征有个优点，它们提取的边缘和梯度特征能很好的抓住局部形状的特点，并且由于是在局部进行提取，所以对几何和光学变化都有很好的不变性：变换或旋转对于足够小的区域影响很小。对于人体检测，在粗糙的空域采样(coarse spatial sampling)、精细的方向采样(fine orientationsampling)和较强的局部光学归一化(stronglocal photometric normalization)这些条件下，只要行人大体上能够保持直立的姿势，就容许有一些细微的肢体动作，这些细微的动作可以被忽略而不影响检测效果。
4 数据集和研究方法
数据集
我们在两个不同的数据集上进行了测试，第一个是MIT的行人数据库[18]，包含城市场景中的509个训练图和200个测试图(加上这些图片的左右翻转图)，此数据集只包含正面和背面两种视角，并且人体的动作有限。我们的检测器在此数据集上表现近乎完美，所以我们制作了一个新的更具挑战性的数据集，“INRIA”，包含从各种人体照片中剪切得到1805个64*128的行人图片。这些人体大多数是站立的，但朝向各异并且背景多变，有些背景中还有人群。
研究方法
我们选择了1239个行人图片以及他们的左右翻转图作为训练的正样本，所以总共2478个正样本。从1218个没有行人的图片中随机截取12180个检测窗口大小的子图作为初始的负样本。用正负样本训练一个初始的分类器，然后用初始分类器在负样本原图上进行行人检测，检测出来的矩形区域自然都是分类错误的负样本，这就是所谓的难例(hard examples）。然后，把误报的负样本(难例)集加入到初始的负样本集中，重新训练，生成最终的分类器，最终的SVM分类器文件大约1.7GB。这种二次训练的处理过程显著提高了每个检测器的表现(在我们的默认检测器中使每个窗口的误报率(FPPWFalse Positives Per Window)下降了5%)。
为了量化检测器的性能，我们提出了一个在双对数坐标上的评价曲线Detection ErrorTradeoff(DET)，即纵坐标是漏检率(miss rate，可以是1-recall rate(查全率、命中率)或者
5 结果综述
我们在此节比较HOG检测器与已存在的一些方法的总体表现。我们的HOG检测器基于矩形块(R-HOG)或环形极坐标块(C-HOG)以及线性或核函数SVM，与Haar小波、PCA-SIFT或形状上下文方法进行对比，这些方法的简要介绍如下：
广义Haar小波
这种方法是定向类Haar小波(oriented Haar-like wavelets)的扩展，与论文[17]中使用的方法类似(更优于)。这种特征是从9*9和12*12定向一阶和二阶45度微分滤波器以及对应的二阶微分xy滤波器改进得来。
PCA-SIFT
此描述子基于用PCA算法将梯度图投影到从训练图片中获得的基底上[11]。Ke和Sukthankar表明此描述子在基于特征点的图像匹配上要优于SIFT，但此说法有争议[14]。我们对此算法的实现使用16*16的块，以及和我们的HOG描述子同样的设定，PCA投影基底从正样本图片计算得到。
形状上下文ShapeContexts
最初的形状上下文[1]使用二值边缘投票在极坐标中统计bin，与边缘方向无关。我们用1个方向bin的HOG描述子模拟了这一方法。使用内径2个像素，外径8个像素的16个角向和3个径向间隔获得最好结果。我们测试了基于梯度和边缘投票的方法，边缘阈值进行自动选择来最优化检测结果。
结果
图3是不同的检测器在MIT和INRIA测试集上的实验结果。
图3(a)
图3(b)
结果表明，HOG检测器要显著优于小波、PCA-SIFT、形状上下文方法，在MIT数据集上相比于其他方法有非常明显性能提升，在INRIA数据集上FPPW值有至少一个数量级的下降。我们的类Haar小波检测器比MIT的小波检测器效果好，因为我们使用了2阶微分并对输出向量进行了对比度归一化。图3(a)同样显示了MIT的最优方法及其集成的检测器的结果(从[17]的实验结果中插值计算得来)，然而由于我们不知道[17]中的数据集如何划分为训练集和测试集，所以无法进行精确的对比。矩形块(R-HOG)和环形块(C-HOG)检测器表现相似，C-HOG有轻微的边缘信息。原始条形(定向2阶微分)扩展R-HOG检测器的特征维数增加了一倍，同时性能也有较大提升(在10-4FPPW时降低2%的漏检率)。如果将线性SVM替换为高斯核函数SVM，在10-4FPPW时有大约3%的性能提升，但以更高的运行时间为代价。以二值边缘投票(EC-HOG)代替梯度幅值权重投票(C-HOG)会在10-4FPPW时降低大约5%的性能，如果忽略方向信息性能下降会更多，即使增加更多的空间或径向bin也不管用。PCA-SIFT的表现很差劲，原因之一是，相比于[11]，为了保留住同样的变化信息，需要更多的主向量，这可能是由于没有特征点检测器后空间配准能力变得更弱了。
6 算法实现和性能研究
在次节中我们会给出HOG算法的详细实现，并系统地分析不同的参数对性能的影响。检测器参数如下：无伽马校正的RGB颜色空间；梯度算子为[-1,0,1]并且无平滑；梯度方向离散化(投票)到0-180间的9个bin中；块(block)大小为16*16，细胞单元(cell)大小为8*8；高斯滤波参数σ为8；L2-Hys块归一化；块移动步长为8个像素；检测窗口为64*128；线性SVM分类器。
图4总结了不同的HOG参数对总体检测效果的影响，这些接下来我们会详细讨论，得出的结论是：要想检测器性能好，需要精细尺度的微分(不需要平滑)，梯度方向直方图的bin尽量多，尺寸适度的、归一化的、重叠的描述子块。
6.1 伽马/颜色规范化
我们用不同的幂值(gamma参数)评价了几种颜色空间，有灰度空间、RGB、LAB，结果表明，这些规范化对结果影响很小，可能是由于随后的描述子归一化能达到相似的效果。如果颜色信息可用，我们的特征提取会使用颜色信息，RGB和LAB颜色空间的结果相似，但如果使用灰度空间，在10-4FPPW时有1.5%的性能下降。对每个颜色通道进行平方根gamma压缩(即gamma参数为1/2)，会在10-4FPPW时有1%的性能提升；如果将gamma参数改为对数，则会造成2%的性能下降。
6.2 梯度计算
不同的梯度计算方法对检测器性能有很大影响，但事实证明最简单的梯度算子结果是最好的。我们先进行高斯平滑，然后应用几种离散的微分模版来计算梯度。我们测试了不同平滑尺度(包括σ=0即不平滑)的高斯平滑，也测试了不同的梯度模版，包括一维模版([-1,1]、[-1,0,1]、[1,-8,0,8,-1])，3*3的Sobel模版，以及2*2的对角线模版
对于带颜色的图像，分别计算每个颜色通道的梯度，以范数最大者作为该点的梯度向量。
图4(a)
6.3 空间/方向bin统计
计算细胞单元(cell)内每个像素的梯度，为某个基于方向的bin投票(vote)，从而形成方向梯度直方图。细胞单元可以是矩形的或者环形(极坐标中的扇形)的。直方图的方向bin在0度-180度(无符号梯度)或者0度-360度(有符号梯度)之间均分。为了减少混叠现象，梯度投票在相邻bin的中心之间需要进行方向和位置上的双线性插值。投票的权重根据梯度幅值进行计算，可以取幅值本身、幅值的平方或者幅值的平方根。实践表明，使用梯度本身作为投票权重效果最好。
精细的方向编码对取得好的结果至关重要，然而空间采样可以做的相当粗糙。如图4(b)所示，增加方向bin的个数可以显著提高检测器的性能，直到大约9个bin为止，这里所用的是无符号梯度的0度-180度均分方向直方图。如果包括梯度符号信息(方向范围为0度-360度，类似SIFT描述子中使用的方向直方图)会导致性能下降，即使bin的个数加倍来保存原始方向信息也不行。对于人体检测来说，衣服和背景颜色的多变可能使得梯度符号信息无意义，但对于其他目标检测，例如汽车、摩托车，梯度符号信息是有用的。
图4(b)
6.4 归一化和描述子块
由于局部光照的变化，以及前景背景对比度的变化，使得梯度强度的变化范围非常大，这就需要对梯度做局部对比度归一化。我们测试了多种不同的归一化策略，大多数都是将细胞单元组成更大的空间块(block)，然后针对每个块进行对比度归一化。最终的描述子是检测窗口内所有块内的细胞单元的直方图构成的向量。事实上，块之间是有重叠的，也就是说，每个细胞单元的直方图都会被多次用于最终的描述子的计算。此方法看起来有冗余，但可以显著的提升性能。图4(d)显示了将重叠区域从0增加到重叠3/4块时，10-4FPPW下有4%的性能提升。
图4(d)
我们测试了两种几何形状的块，一种是矩形的块，称为R-HOG；一种是极坐标中的环形块，称为C-HOG。
R-HOG
R-HOG块与SIFT[12]描述子中使用的块很相似，但用法不同。R-HOG块描述子在单一尺度的稠密网格空间中进行计算，无主方向，并且作为更大的检测窗口描述子的一部分被使用，检测窗口描述子中明确含有块之间的相对位置信息。而SIFT特征点描述子在多尺度空间下计算，具有尺度不变性，并需要旋转到其主方向上，而且SIFT描述子是独立使用的。SIFT描述子适合稀疏、宽基线的匹配，R-HOG描述子适合表示稠密空间的编码。其他的先例包括Freeman和Roth[4]的边缘方向直方图。R-HOG块可以用三个参数表示：ζ,η,β，块大小为ζ*ζ，细胞单元大小为η*η，每个细胞单元有β个方向bin。
图5显示了在10-4FPPW时漏检率随不同的细胞单元和块尺寸的变化情况。对于人体检测，每个块内含3*3个细胞单元，每个细胞单元含6*6个像素时最优，此时漏检率大约为10.4%。事实上，无论块尺寸为多大，细胞单元为6-8个像素宽时性能最优——巧合的是，我们的测试图片中人体大约也是6-8个像素宽。每个块内含2*2或3*3个细胞单元时最优。除此之外，结果不好：当块过大时，对局部图像的适应性变差；当块过小时，有价值的空间信息减少。
图5，10-4FPPW时漏检率随细胞单元和块尺寸的变化情况。块步长(块重叠区域)固定在块尺寸的一半(即重叠区域为1/2)，细胞单元为6*6个像素，每个块内含3*3个细胞单元时性能最优，漏检率大约为10.4%
就像SIFT论文[12]中描述的，在统计直方图bin之前用高斯加权使得块边缘的像素的权重降低是有很用的。经试验，在10-4FPPW时使用σ = 0.5 *block_width的二维高斯核进行加权可使性能提升1%左右。
我们还测试了在描述子中使用不同的细胞单元尺寸和不同的块尺寸，性能有稍微的提高(在10-4FPPW时提高3%)，但同时会大幅增加描述子尺寸。
此外，我们还测试了垂直块(含2*1个细胞单元)、水平块(含1*2个细胞单元)以及既有垂直块又有水平块的描述子。垂直块和垂直+水平块明显比只有水平块要好，但还是不如2*2的方形块好。
C-HOG
我们的环形块描述子与形状上下文[1]类似，只不过，每个细胞单元包含一个以梯度为权重的方向栈，而不是单纯的方向无关的边缘计数。极坐标网格的想法源于允许精细的相邻结构编码与粗糙的广域上下文编码相结合的思想，以及信号由视觉向人类大脑皮层的转换是对数级的这一事实[21]。实时证明，含有很少的半径bin的描述子结果最好，所以实际中几乎不会有不均匀的情况出现。可以将C-HOG简单看做中心环绕编码的一种高级形式。
C-HOG的块有两种形式，一种是中间有一个完整细胞单元的形式(类似[14]中的GLOH特征)，另一种是中心单元被分为四个90度扇形的形式，类似形状上下文方法，如下图所示。
我们只提供中心有完整细胞单元的C-HOG的结果，相比于中心被分割的C-HOG，这种方法有更少的空间划分，但实际效果却是相同的。C-HOG可以用四个参数表示：角度bin的个数，半径bin的个数，中心圆的半径(以像素为单位)，子半径的伸展因子。要想保证好的性能，至少需要两个半径bin(一个中心半径、一个周围的半径)，四个角度bin。增加额外的半径bin并不能改善多少性能，如果增加角度bin的个数反而会降低性能(从4个增加到12个会在10-4FPPW时降低1.3%的性能)。中心圆的半径为4个像素时最好，但3或5像素结果相似。将伸展因子从2增加到3性能不会变化。为细胞单元的投票加上高斯权重或逆高斯权重不会改变性能。形状上下文方向(只含一个方向bin)需要更精细的空间子划分才能表现良好。
块归一化策略
我们对上面介绍的每种几何形状的块都测试了四种归一化方法。
假设v是未经归一化的描述子向量。
‖v‖k是v的k范数，k=1,2，
(L2 norm就是平方和开方，即欧氏距离；L1 norm就是绝对值相加，又称曼哈顿距离)
(a)L2-norm(L2范数)：
(b)L2-Hys：先计算L2范数，然后进行限幅(限制v的最大值为0.2)和再归一化，[12]中有描述。
(c)L1-norm(L1范数)：
(d)L1-sqrt：L1范数取平方根，即
如图4(c)所示，L2-Hys、L2-norm、L1-sqrt的表现差不多一样好，简单的L1-norm会使性能下降5%，如果完全不进行归一化会导致性能下降27%(都是指10-4FPPW时)。我们还调整参数的值进行测试，但结果表明检测器性能对于值的变化并不敏感。
图4(c)
中心环绕归一化
我们研究了中心环绕式的细胞单元归一化方法，利用每个细胞单元和环绕其周围的细胞单元(利用二维高斯权重进行加权)的能量对该细胞单元进行归一化，然而结果如图4(c)中的”Window norm”曲线所示，这种方法相比于基于块的归一化方法会使性能下降(在10-4FPPW时降低2%)。其中一个原因是由于没有重叠的块，每个细胞单元仅在最终的描述子中被使用一次。改变高斯加权的参数也并不会引起结果的变化。
为了阐明这点，考虑有重叠块的R-HOG检测器。训练好的线性SVM分类器的参数会衡量每个块中的每个细胞单元在最终的判定决策中起多少作用。图6(b,f)表明最重要的细胞单元是包含主要的人体轮廓(特别是头部、肩部和足部)的那些，用这些细胞单元相对于轮廓外的块进行归一化。也就是说，不管训练图片中的背景如何复杂，检测器检测的主要是人体轮廓相对于背景的差异，而不是内部的边缘或轮廓相对于前景的差异。衣服上的图案和身体姿势的变化使得人体轮廓内部的区域不适合作为可靠的检测特征，而且前景到轮廓的过度可能由于平滑阴影而混淆。图6(c,g)表明人体轮廓内部的梯度(尤其是垂直梯度)一般都是有害的特征，可能是因为这些特征会引起误报，在这些误报中长的垂直条纹会被当做头部或腿。
图6，HOG描述子最有用的信息来自于人体轮廓周围(尤其是头部、肩部、足部)，最有效的块是以人体轮廓外沿的背景为中心的那些块。(a)训练样本的平均梯度图，(b)每个像素表示块中以此像素为中心的最大正SVM权重，(c)与(b)类似，负SVM权重，(d)一张测试图，(e)计算得到的R-HOG描述子，(f)正SVM权重支持的R-HOG描述子，(g)负SVM权重支持的R-HOG描述子
6.5 检测窗口和上下文
我们用的64*128大小的检测窗口在人体周围会产生大约16个像素的空白边缘。图4(e)表明此空白边缘增加了有助于检测的上下文信息。将空白边缘从16像素减少到8像素(48*112大小的检测窗口)会在10-4FPPW时导致6%的性能下降。保持窗口大小为64*128不变，增加人体的尺寸(同样会使空白边缘减少)，虽然使得人体的解析度变高，但也会导致性能下降。
图4(e)
6.6 分类器
我们默认使用带有松弛变量(C=0.01)的线性SVM分类器SVMLight[10](在原版SVM上稍作改动使得处理大规模特征向量时可减少内存占用)。如果使用高斯核函数SVM可以在10-4FPPW时提高大约3%的性能，但需要以更多的运行时间为代价。
6.7 讨论
总体来说，此篇论文中有几个重要发现。HOG特征表现远好于小波，计算梯度前任何大尺度的平滑都会导致性能下降，大多数可用的图像信息都来自精细尺度中的陡峭边缘，为了减少对空间位置的敏感度而模糊陡峭边缘的做法都是错误的。相反，梯度应该在最精细尺度的金字塔层中计算，然后进行校正或用于方向bin的投票，只有在投票时才需要进行模糊。据此，相对粗糙的空间采样(8*8的细胞单元)也足够用，但方向采样需要相当精细，小波和形状上下文正是输在这点上。
另外，较强的局部对比度归一化对于取得好的结果至关重要，传统的中心环绕式归一化方法并不太好。要想取得更好的结果，可在不同的局部区域对每个元素(边、细胞单元)归一化多次。在我们的标准HOG检测器中，每个细胞单元在不同的归一化中出现4次，这种“冗余”的方法可在10-4FPPW时将性能由84%提高到89%。
7 总结和结论
在稠密重叠网格中使用类似SIFT描述子[12]的局部归一化的梯度方向直方图特征对于行人检测效果非常好，相比基于Haar小波特征的最好的检测器(来自[17])可以将误报率降低一个多数量级。我们研究了各种描述子参数对结果的影响，得出结论：小尺度梯度(fine-scale gradients)，精细的方向采样(fine orientation binning)，相对粗糙的空间采样(relatively coarse spatialbinning)，和重叠描述子块中高质量的局部对比度归一化(high-quality localcontrast normalization in overlapping descriptor blocks)都对好的检测效果至关重要。我们还引入了一个新的更具挑战性的行人检测数据集，已公开下载。
今后的工作
虽然我们当前使用的线性SVM分类器已相当高效——处理一个320*240的尺度空间图像(4000个检测窗口)的时间少于1秒钟，但仍然有优化的空间。为了更深层次的加快检测速度，需要一个由粗到细的或者拒绝链式的基于HOG的检测器。我们也在研究基于HOG的，并同时包含基于块匹配或光流的运动信息的检测器。最后，虽然当前的固定模版检测器在全身可见的行人检测方面有不可比拟的优势，但由于人体是高度关节型的，所以我们相信具有更好的局部空间不变性的基于身体部分的模型可以在更一般的场景中改善行人检测效果。
致谢
此研究得到了欧洲联合研究项目组ACEMEDIA和PASCAL的支持。感谢Cordelia Schmid的大量有用建议。SVM-Light[10]保证了大规模样本训练的可靠性。
Histogram of Oriented Gradients for Human Detection 翻译