2005年由Navneet Dalal和Bill Triggs的发表的<<Histograms of Oriented Gradients for Human Detection>>是pedestrian detection的最著名的经典算法，必须仔细拜读：

摘要

该文主要研究用于visual object recognition的feature set，并采用基于linear SVM的human detection作为test case。通过review现有的基于edge和gradient的descriptors，我们实验性的证明了Histogram of Oriented Gradients(HOG) descriptor极大地outperform现有的用于human detection的feature set（experimentally，significantly）。我们研究了每个阶段的计算对性能的影响，其结论是fine-scale gradient, fine orientation binning，relative coarse spatial binning，和high-quality local contrast normalization in overlapping descriptor是产生好的结果的重要因素。这个新的方法在MIT pedestrian database上给出接近完美的separation。因此我们引入了一个更具有挑战的dataset，该测试集包含1800个标记过的背景和姿势不同的human images (anotated，标记过的)。

简介

由于variable appearance和a wide range of poses，detecting humans 是一个 challenging task. 第一个需求是robust feature set，允许在difficult illumination和clutterred background情况下，human form可以被清晰地discriminated。我们研究用于human detection的featue set，显示locally normalized histogram of oriented gradient(HOG) descriptor比其他existing feature set，提供了excellent performance。该descriptor 让我们联想起edge orientation histogram，SIFT descriptor and shape context。但是他们在a dense grid of uniformly spaced cells进行计算，并且使用overlapping local contrast normalization来改进性能。我们给出了一个不同的implementation choice对detector performance产生影响的detailed study， 并把pedestrian detection作为test case。（pedestrian detection refer to the detection of mostly visible people in more or less upright pose）。为了simplicity and speed，我们采用linear SVM 作为baseline classifier。这个新的detector本质上在pedestrian test set上，可以获得perfect results。因此我们create了一个更具有挑战的data set，包含了超过1800个不同背景与姿势的pedestrian images。Ongoing work显示我们的feature set对其他shape-based object classes，表现良好。我们在section 2briefly讨论了human detection有关的其他工作，在section 3给出本方法的overview，在section 4主要介绍我们自己的dataset，在section 5-6给出每个阶段的detailed description和experimental evaluation。

Previous Work

对于Object detection已经有了extensive literature，但是我们只mention少量和human detection有关的论文。papageorgiou描述了基于polynomial SVM和rectified Haar wavelet的描述子的pedestrian dector，并在另外一篇论文中给出了一个part based variant。Depoortere给出了一个该方法的optimized version。Gavrila and Philomen给出了一个更直接的approach，提取edge images，然后和a set of learned exemplar进行match。这已经应用在practical real-time pedestran detection system。Viola 构建了一个有效的moving person detector，使用AdaBoost来训练基于Haar-like wavelet和space-time difference的a chain of progressively more complex region rejection rules。Ronfard通过limb classifier构建了一个articulated body detector。Mikolajczyk使用orientation position histogram和binary-thresholded gradient magnitude来构建parts based method，包含用于faces，heads，front和side profile of upper body parts的detector。相反，我们的方法使用simpler architecture，只有一个single detection window，但是在pedestrian image上获得了significantly higher performance。

overview of the method

这个section给出了一个feature extraction chain的overview，implementation则要postpone到section 6。这个方法是基于在dense grid上evaluate well-normalized local histogram of image gradient orientation。Similar feature已经在过去decade不断的应用。Basic idea is that local object appearance and shape can often be characterized rather well by the distribution of local intensity gradients or edge direction，even without precise knowledge of the corresponding gradient or edge position。事实上，这通过divide the image window into small spatial regions，或者叫cell。对每个cell累积一个gradient orientation的local 1-D histogram。The combined histogram entries 形成了这种representation。为了更好的invariance to illumination and shading，通常需要在使用之前contrast-normalize the local response。这通过accumulate在更大的spatial region量测local histogram，使用这个结果来normalize所有的cell in the block。我们refer to这个归一化的descriptor block，称为histogram of oriented gradient descrptor。The detection with a dense grid of HOG descriptor 以及 a conventional SVM based window classifier 构成了human detection chain。Orientation histogram的使用有很多precursors，但是它只在SIFT中结合local spatial histogramming和normalization 之后reach maturity，这提供给underlying image patch descriptor来matching scale-invariant keypoint。SIFT-Style在这些application表现的remarkably well。Shape context研究了alternative cell和block shapes，尽管initially只使用edge pixel被计算， 而不是orientation histogramming。这些基于sparse feature的representation已经一定程度上overshadow了dense image descriptor的HOG。特别的，我们的informal experiment表明尽管最好的keypoint based approach有可能拥有1-2 orders of magnitude的false positive rate高于dense grid approach。因为没有keypoint detector可以可靠的detect human body，HOG/SIFT representation拥有很多advantage。它capture 那些非常characteristic的反应local shape的edge和gradient structure。这种structue拥有local representation，其local geometric and photometric transformation是invariance的。Translation和rotation区别很小。对于human detection，fine orientation sampling和strong local photometric normalization是一个最好的策略。只要保持roughly upright orientation，它允许limb和body segment改变appearance，并且move from one side to side。

DataSet and Methodology

我们在两个不同的dataset上测试detector。第一个是well-established MIT pedestrian database，包含了 509 training pedestrian images 和 200个 test pedestrian images。它包含了具有limited range of pose的front或back view。我们的best detector在这个数据集上给出了perfect result。因此我们制作了一个新的并且明显更有挑战的dataset，叫做INRIA，BAOHAN 1805个 64*128个从a varied set of personal phots获得的human images。这些people通常是standing，但是拥有不同的orientation，针对于不同的background image。很多都是从image background中提取的bystander，因此并没有对pose的特别的bias。

Methodology. 我们选择了1239个image作为positive training examples，以及left-right reflections。从1218个person-free training photo中，随机的抽取12180个patches，作为initial negative set。这个方法 通过一个retrained process明显的改进了每个detector的性能，但是additional round of retraining并没有太大的差别。

为了quatify detector performance，我们在一个log-log scale上，绘制detection error tradeoff curves，也就是miss rate versus FPPW。更低的value会更好。DET plot在speech和NIST evaluation上广泛的使用。他们呈现了和Receiver Operating Characteristic同样的information，但是允许small probabilities更容易去区分。我们通常使用miss rate作为reference points作为结果。在一个multiscale detector，它对应一个raw error rate，大约每个测试的640*480的0.8 false positive。这个full detector由于non-maximum suppression，已经拥有一个更小的false positive rate。我们的DET curves通常非常shallow，所以尽管very small improvement in miss rate等同于large gain in FPPW。尽管1%的absolute reduction in miss rate等同于减少FPPW。

Overview of Results

在presenting详细的implementation和性能分析之前，我们与一些现存方法来比较final HOG detector的overall performance。基于rectangular或者circular log-polar block以及linear SVM的detector会与其它implementation，比如Harr wavelet，PCA-SIFT，和Shape context approaches进行比较。简明的，这些方法如下：

Generalized Haar Wavelet：这是一个oriented harr-like wavelet的扩展集。这些feature是对9*9和12*12的oriented derivative box filte所采取的rectified response。PCA-SIFT：这些descriptor基于projecting gradient images到basis，这个basis是从training images中获得的。Sukthankar发现这种方法outperform用于keypoint based matching的SIFT。 我们的implementation 使用了16*16与 HOG descriptor 具有同样derivative scale的block。这种PCA basis通过positive training imasge进行计算。Shape Contexts：原始的shape context使用binary edge-presence，这些binary edge-presence vote into log-polar spaced bins，而与edge orientation无关。我们使用 C-HOG descriptor在一个orientation bin进行仿真。16 angular和3 个radial interval，其中inner radius是2 pixel和outer radius是8 pixels，给出了最佳的result。gradient-strength和edge-presence 基于的voting可以被测试。其edge threshold自动的选择，从而maximize detection performance。

Results：Fig 3给出了various detector在MIT dataset和INRIA dataset上的性能。HOG based detector极大地outperform其他的dector，包括wavelet, PCA-SIFT和Shape Context。我们的Haar-like wavelets比MIT wavelet要超出很多，因为我同时使用2nd order derivative和contrast normalize输出vector。MIT的 最佳的parts based和monolithic detector，但是注意exact comparison是不可能的，因为我们不知道如何database可以分为training part和test part。并且使用的 negative images 是不太可能的。 最终的 retangular detector和circular detector是非常类似的， 而C-HOG拥有slight edge。Augment R-HOG with primitive bar detector双倍了feature dimension，但是further提升了performance。Replacing the linear SVM with Gaussian Kernel 增强了3% 的 performance，其成本拥有更高的运行时间。使用Binary Edge voting，而不是gradient magnitude weighted voting减少了5%的performance。PCA-SIFT表现更加poorly。一个理由是，更多的principal vector必须被retained，来capture the same proportion of the variance。这是因为spatial registration在没有keypoint detector的时候，会更加的weaker。

Implementation and Performance Study

我们给出了HOG implementation，并且系统性的研究了various choice对detector performance产生的影响。通过这一section，我们refer我们的result到default detector拥有following properties。拥有Gamma correction的RGB colour space，[-1,0,1]的Gradient filter没有平滑，linear gradient voting into 9 orientation bins；16*16的pixel block以及4个8*8的pixel cell；Gaussian Spatial window with 8 pixel；block normalization；block spacing stride of 8 pixels；64*128大小的 detection window；Linear SVM classifier。

图4给出了various HOG parameter对overall detection performance的影响。（the effects of .... on... ) 主要的结论是想获得good performance，需要使用fine scale derivative，很多orientation bins，并且 moderately sized, strong normalized, overlapping descriptor blocks。

Gamma/Colour Normalization

我们评估不同的input pixel representation，包括grayscale，RGB和LAB colour space。可选进行power law equalization。这些normalization拥有一个modest effect，也许因为subsequent descriptor normalization实现类似的result。我们使用color information。RBG和LAB colour space给出了比较性的结果，但是限制grayscale会减少性能到1.5%。在每个colour channel进行Square root gamma compression会提升1%的性能，但是Log compression会太显强大，并且会降低2%的性能。

Gradient Computation

Dector performance对如何计算gradient是敏感的，但是最简单的方法turn out to be best。我们使用不同参数模板Gaussian smooth测试梯度。很多不同的smooth scale被测试，包括scale是0的情况。Mask包括various 1-D point derivative，包括uncentred，centred，cubic-corrected,以及3*3 Sobel mask和2*2 diagonal one（compact centred  2-d derivative mask）。简单的1-D mask [-1，0，1] 在scale =0 的时候工作最好。使用larger mask会降低performance，而smooth会damage it significantly。对于Gaussian Derivative， 从scale=0到scale=2可以减少recall rate到89%。对于scale=0，cubic corrected 1-d width 5 filter 会有1%的性能降低，而2*2 diagonal mask有1.5%的性能降低。使用uncentred [-1，1] derivative mask同时会有1.5%的性能降低。

Spatial Orientation Binning

下一步是对描述子的fundamental nonlinearity。每个pixel都为edge orientation histogram计算weighted vote。这些vote都被累计到orientation bins over local spatial region。这就是所谓的cell。每个cell既可以是 retangular也可以是radial。这个orientation bins可以是spaced over 0-180 或者 0-360。为了减少了aliasing，vote是双线性的插值in both orientation and position。The vote是gradient magnitude的函数，可能是magnitude itself，也可能是square，或者square root，或者一个clipped form of magnitude代表soft presence在每个像素的边缘。在实践中，使用magnitude会给出最好的结果。Taking the square root会轻微的减少performance。而使用binary edge presence voting会有5%的性能减低。

Fine orientation coding呈现的更加重要，而spatial binning是相当的coarse。增加number of orientation bin可以增强性能，最高达到9bins。但是beyond this，却很少有区别。这是对那些space over 0-180的bin，the sign of gradient is ignored。包含signed gradient(也就是说orientation range from 0 to 360，就像SIFT descriptor）反而减低性能，尽管the number of bins也是double来preserve之前的orientation resolution。对于human，大范围的clothing以及background colors会让the sign of contrast uninformative。Note that 包含sign information 确实有significantly帮助，对其他object recognition tasks。

Normalization and descriptor block

由于local variation in illumination 和 foreground-background contrast，Gradient strength在一个广大的范围内变化。所以有效地local contrast normalization对于系统性能有至关重要的作用。我们评估了不同的normalization schemes。但是大多数的是基于group cells变成更大的spatial block然后contrast normalizing每个block。最后的descriptor是vector of all component of the normalized cell response。事实上，我们通常overlap the block，以至于each scalar cell response贡献于final descriptor vector的several component。每一个都是根据不同的block进行normalized。这看起来有些redundant，但是好的normalization至关重要，并且引入overlap明显的改进了系统性能。Fig 4 显示系统性能增加4%，当我们增加overlap，从non到16-fold area。我们评估two classes的block geometries，一个是square和retangular one，分割成grid of square或者retangular spatial cell的retangular one，另外一个是分割成log-polar fashion的circular block。这两种arrangement分别被称为R-HOG和C-HOG。（retangular HOG 和 Circular HOG)。

R-HOG

R-HOG拥有和SIFT descriptor极大地相似性，但是使用起来有极大地不同。R-HOG在一个dense grid at a single scale上计算，而没有dominant orientation alignment，并且使用做为larger code vector的一部分，从而相对于detection window隐含的解码spatial position。相反，SIFT在一个Sparse set的scale-invariant key point，旋转来align dominant orientation，并且使用individually。SIFT最优于Sparse wide baseline matching，而R-HOG用于spatial form的dense robust coding。图5绘制了miss rate over cell size and block size。对于Human detection，3*3 cell block of 6*6 pixel cell表现最好，拥有10.4% miss rate at FPPW。我们的标准的2*2 cell block 以及8*8 pixel per cell，有着第二位的miss rate。In fact，6-8 pixel wide cell表现最好，这是一个有趣的巧合，因为human limbs大概有6-8个像素accross the image。2*2和3*3 cell block 工作最好。local imaging condition的适应性是非常弱的，特别是当block变得非常大，或者非常小。（1*1 cell block，就是normalization over orientation) 有价值的spatial information是抑制的。这是有用的去downweight接近block edge的pixel，从而应用Gaussian Spatial Window到每个pixel，在accumulate orientation vote到每个cell之前。这会改进1%的性能。

我们也会尝试在整个descriptor上，包含具有不同的cell和block size的multiple block types。这会轻微的提升4%的性能，其成本是不断增加的descriptor size。

除了square R-HOG blocks，我们也测试了vertical block和horizontal block，和一个包含vertical and horizontal pair的combined descriptor。Vertical和Vertical+Horizontal pair明显的比horizontal pair更好。但是还是不如2*2 cell block和3*3 cell block。

C-HOG

我们的circular block（C-HOG）描述子让我们想起（are reminiscent of) shape context，除了每个spatial cell包含a stack of gradient-weighted orientation cells 而不是single orientation-independent edge-presence count。这个log-polar grid初始由idea产生，这就是fine coding of nearby structure可以与coarser coding of wider context相结合。但是小的descriptor拥有非常少的radial bin给出了最佳的性能，而在实践中少量的inhomogeneity或者context。把C-HOG简单的看成高级形式的centre-surround coding可能会更好。

我们评估了两种C-HOG geometry的variant，其中一个只有一个single circular central cell，另外一个的central cell可以分为4个angular sectors。我们只呈现circular-centre varian，这是因为fewer spatial cells比把central cell划分为4份的拥有更好的性能。一个技术报告会给出一个细节。C-HOG layout拥有四个参数，angular和radial bin的数量，central bin中的radius的大小，和4个angular bin的扩展系数。至少两个radial bins和4个angular bin是良好性能所需的。包括additional radius bins并不会改变太多的心能，反而增加angular bins会减少系统的性能。4个像素是best radius for central bin，而3到5个给出了类似的result。增加扩展因子从2到3并没有让心能有任何的提升。这些值假设了fine orientation sampling。而Shape context需要更细致的spatial subdivision。

Detector window and Context

我们的64*128的detection window在四周包含了大概16个像素的margin。Fig 4显示了这个宽度提供了大量的context来帮助detection。减少到16或者8像素，会降低4%的性能。而保持64*128 window，但是在窗内增加person size，也会产生类似的性能的loss，尽管the resolution of the person会不断增加。

Classifier

默认我们采用soft linear SVM，而使用Gaussian Kernel SVM会增加3%的系统性能，但是代价是更高的run time。总体上，这篇文章有很多notable finding。事实上，HOG极大地outperform了wavelet，并且任何程度的smoothing在计算梯度之前，会破坏HOG结果。强调太多的available image information来自于abrupt edges at fine scale。Bluring 以期待减少sensitivity to spatial position是一个错误。相反，gradient应在finest available scale计算，rectified或者用于orientation voting，然后才能在空间上blur。相对coarse spatial quantization满足的。相反，至少对于human detection，它pay to sample orientation相当精细，而wavelets和shape context在这个地方有所不如。第二，strong local contrast normalization对于好的结果只管重要，传统的centre-surround style并不是最佳的结果。更好的记过可以通过normalize每个element多次，针对不同的local supports，并且把这些结果作为independent signals。对于我们的标准的detector，每个HOG对出现 4次 不同的normalization。

Summary and Conclusion

我们表明使用locally normalized histogram of gradient orientation类似于SIFT descriptor，在一个dense overlapping grid上给出了一个很好的结果for person detection，减少了false positive rate，比基于best wavelet的detector，超过了an order of magnitude。我们研究了不同descriptor parameter，给出的结论是fine-scale gradient, fine orientation binning, 相对coarse spatial binning, 和high-quality的local contrast normalization in overlapping descriptor block都对性能有重要的影响。我们同时给出了一个新的更具挑战的pedestrian database。

Reference

http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1467360&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D1467360