一种方向梯度直方图的降维方法

傅红普,邹北骥

(1.中南大学 信息科学与工程学院 “移动医疗”教育部-中国移动联合实验室， 湖南 长沙 410083;2.湖南第一师范学院 信息科学与工程学院, 湖南 长沙 410205)

一种方向梯度直方图的降维方法

傅红普1,2,邹北骥1

(1.中南大学 信息科学与工程学院 “移动医疗”教育部-中国移动联合实验室， 湖南 长沙 410083;2.湖南第一师范学院 信息科学与工程学院, 湖南 长沙 410205)

为描述对象的局部外观和形状,方向梯度直方图首先将图像划分成小区域(被称为cell),然后在其上累加像素梯度方向的一维直方图.在被称为block的较大区域(由数个相邻的cell组成)上连接cell的直方图，经归一化处理形成特征向量.为减弱由block引起的区域量化走样,在计算检测窗口的特征时，采取部分重叠block的措施，从而大大增加了特征维度以及目标检测时的计算量.通过扩大参与相邻cell之间像素梯度插值的面积,并设置适当的高斯平滑核尺度,可消除block重叠,从而将64×128尺寸的窗口的方向梯度直方图特征维度由3 780降低为1 152.INRIA的行人数据集实验表明,该方法也可减弱区域量化走样,且其性能与原方向梯度直方图几乎相当,而检测速度却显著提高.

方向梯度直方图;降维;线性插值;重叠采样;行人检测

方向梯度直方图特征(histograms of oriented gradients，HOG)[1]在计算机视觉领域颇受关注.首先,视觉相似性可以通过HOG的余弦距离度量;其次,它是人类视觉相似性的合适模型，使用的是像素梯度而非像素强度,对全局对比度比较鲁棒;而且,在梯度角度和小区域(cell)位置上的三线性插值以及block部分重叠极大消除了量化走样[1-2].

HOG首先被用于行人检测,再被应用到各种类别对象的检测和识别上,包括汽车等刚体和马等可形变体.HOG亦被广泛应用于图像检索[3]、理解[4]、分类[5]等.近来,为获得良好的性能目标，检测领域亦采用HOG或类HOG特征[6-8].因此,研究如何提高HOG性能很有价值.

人们试图提高HOG特征的鉴别能力.DOERSCH等[2]以很小的额外计算量获得了较高的HOG边界和条带状纹理处理能力，并试图提高其鉴别能力.DANG等[9]通过在三层图像金字塔上提取HOG,然后串接成特征向量，将行人检测的性能提高了3%,其代价是更长的特征维数和随之而来的额外计算量.文献[10]通过将HOG和其他特征频道相混合的方法提高鉴别能力.

对HOG进行降维的尝试也很重要.针对某些目标检测问题,FELZENSZWALB等[11]收集了block(由4个相邻的cell构成，相当于cell的大区域)上的36维特征,对其进行PCA分析发现，前11维几乎能表达所有特征信息.利用PCA特征向量生成子空间的特殊结构,其点积运算能将block上的HOG从36维降为13维.文献[9]通过省略检测窗口中信息量较少区域的特征来减少HOG向量的维度，提高检测速度.现有降维工作对特定问题的先验知识具有一定的依赖性.

1 HOG中的三线性插值和block部分重叠的窗口覆盖

为描述对象的局部外观和形状,文献[1]用局部像素强度梯度的直方图作为特征表达,称该特征为方向梯度直方图.为保留位置信息,图像窗口被分成多个小区域(被称为cell),累加cell中每个像素的梯度构成1维梯度方向直方图.为了使光照不变性更好,将4个相邻cell组成一个名为block的更大区域;然后,使用block上的直方图“能量”对4个cell上的直方图进行归一化.以像素为中心计算梯度,按梯度方向根据权重将梯度值分配到直方图的对应项.使用HOG特征进行行人检测.

在HOG中,按角度和所在位置,将像素梯度值分配到各cell区域的各方向项.为降低方向量化走样,在相邻的直方图方向项之间对梯度值进行了线性插值.为避免由cell和block划分带来的区域量化走样,首先,在纵横相邻的cell之间对梯度值进行线性插值,其与前述角度项的插值一起形成三线性插值;其次,block采取部分重叠的方式覆盖检测窗口.图1示意了这2个措施的细节.

图1 cell位置双线性插值(a)与block部分重叠(b)Fig.1 Interpolate pixel gradient between cell position centers (a) and partly overlap blocks (b)

图1(a)给出了block左上角cell区域插值的详细示意.对于原HOG的提取,只有在block中的像素梯度值才会参与cell之间的线性插值.插值时,cell从概念上被分成4个子区域.位于block 4个顶点处的子区域不对其他cell插值;处于block中心区域的4个子区域对4个cell都进行插值;其他子区域在其自身和与其紧邻的cell上进行插值.具体来说,提取HOG时,直方图按式(1)累加得到.

hθ(xi,yi)=hθ(xi,yi)+Mθ(x,y)×

|x-xi|

(1)

其中,hθ(xi,yi)为第i个cell在方向角度θ上的HOG分量,i=0,1,2,3;Mθ(x,y)为像素(x,y)在方向角度θ的梯度值;(xi,yi)为第i个cell的中心位置坐标;dx和dy分别为2个相邻cell在x和y轴方向的距离,原HOG中dx和dy都是8个像素.

如图1(b)所示，对block重叠一半的面积进行了高斯平滑，以减弱像素对block边缘区域的影响.高斯核设置为block边长的一半，高斯平滑减弱了重叠带来的负面影响.

2 无block重叠的方法

提取HOG时,因有block部分重叠,在64×128大小的检测窗口上需要计算105个block的特征.若直接依次覆盖,则只需32个block.本文给出的替代方法无须block重叠就可减弱由block分割带来的区域量化走样.这样,一个检测窗口的特征维度大大降低,特征提取的计算量却没有增加,而且检测速度大大提高了.

当采样频率不够时,因为低频和高频混在一起,重构信号将与原信号有极大不同,就会出现走样.当高频成分不能被采样设备析出时,就应该在采样之前或之后先行移除以避免走样.比如，对图像的低通平滑滤波显然会丢失很多原始信息.因此,防止走样的最好方法是提高采样频率,如重叠采样[12]，计算HOG时block部分重叠就是重叠采样的一个例子.

注意到HOG中在相邻cell之间的双线性插值也是为了获得cell空间采样的连续性.但是,刻意将参与双线性插值的像素限制在block之内，未能获得block采样的连续性.换个角度来看,block部分重叠正是为了获得block空间采样的连续性.鉴于此,本文给出了一个减弱block空间量化的方案，不必采取block部分重叠的方式来覆盖检测窗口,而是让block之外紧邻block的cell也参与线性插值，从而获得block空间的连续性.

2.1 扩展线性插值范围

除block内的像素外,紧邻block的cell中的像素梯度也参与到cell位置的双线性插值,按照HOG的cell双线性插值方法,只需包含额外的0.5个cell宽度即可.这样,检测窗口由无相互重叠的block直接覆盖.

此方式,只有block之外的参与插值的cell被重叠,覆盖一个64×128的检测窗口只需32个block,而不是原本的105个.一个检测窗口中的特征维度由7×15×36=3 780降为4×8×36=1 152.图2为本文给出的block中cell位置双线性插值示意图.

在原HOG提取方法中,有4个cell的像素梯度参与cell间的双线性插值.增加0.5个cell宽度的额外面积后,参与线性插值的面积增加到了7个cell,即参与双线性插值的像素个数是原HOG的1.75倍.像素梯度的计算量没有增加,单纯的插值计算量增加亦不多，可完全由block数量减少降低的计算量抵消.图2为左上角额外区域线性插值的情况.插值方法与block之内像素方法一致，只在相邻cell之间插值,见式(2).

hθ(xi,yi)=hθ(xi,yi)+Mθ(x,y)×

|x-xi|

(2)

其中各符号的含义同式(1).

图2 本文方法给出的cell位置双线性插值示意图Fig. 2 Cell position interpolation of the proposed method

2.2 重新考量block的高斯权重

有更多像素给予了block的特征,现需重新考虑高斯平滑，以给block之外像素适当权重.若简单地给block之内和之外一致的权重,全部使用0.5个block宽度的高斯核,则block之外区域像素的权重会显得太小.

本文,在block之内、之外的像素的高斯权重分别按式(3)和(4)设置.图3给出了block之内和之外的高斯权重分布示意图，这种分别设置权重的方式增加了灵活性.

ωb(x,y)=exp(((x-xc)2+(y-yc)2)/2σ2)，

(3)

ωe(x,y)=exp(((|x-xc|-bx)2+(|y-yc|-by)2)/2σ2)，

(4)

其中,(xc,yc)是block中心的坐标,(bx,by)是对block之外像素的偏移补偿.该补偿可防止block之外参与插值像素的权重过小.实验发现,当block高斯权重的设置与原HOG相同时性能最好.

图3 block之内及之外像素权重示意图Fig.3 Pixel gradient weight in and outside the block

此方法称为扩展cell位置线性插值范围、无block重叠HOG(EL-HOG),将原HOG称为标准HOG(S-HOG).

3 实验及结果

在INRIA行人数据集上,将本文方法(称为EL-HOG)、原标准HOG(称为S-HOG)及取消block部分重叠的原HOG(称为NL-HOG, NL-HOG, Näve Lower dimension standard HOG)进行了性能对比.提取NL-HOG特征时,除了block不重叠外,其他所有参数设置都同S-HOG, 64×128尺寸的检测窗口上得到的NL-HOG特征的维度也为1 152.

3.1 实 验

3.1.1 3种HOG比较

直接通过OpenCV 2.3.1中HOG的实现来提取S-HOG特征,其他2个是通过修改OpenCV2.3.1中HOG的实现得到的.将检测窗口中block的滑动步长设置为block的边长就得到了NL-HOG. EL-HOG默认的高斯权重设置如下:高斯核大小为block的1/4,偏移补偿为1/2 cell长度,即

σ=(blocksize,width+blocksize，height)/8，

(5)

(bx,by)←(cellsize,width/2,cellsize,height/2).

(6)

检测窗口的大小仍设置为64×128.在使用S-HOG检测行人时,检测窗口在行人样本的周围包含了约16个像素的周围环境图像,这些边界为检测提供了重要的上下文信息[1].提取EL-HOG时,在检测窗口上增加了额外0.5个cell宽度的边界,但是将这些像素的值都设置为0.否则,EL-HOG检测窗口使用的额外边界宽度为24个像素,造成EL-HOG、S-HOG及NL-HOG使用信息不一致.

分别使用3个HOG的LIBSVM[14]训练线性SVM分类器、使用5折交叉验证以确定最优训练参数.

3.1.2 EL-HOG中高斯权重的影响

测试了不同高斯权重对EL-HOG性能的影响.使用2种权重设置方式：(1)block之内和block之外其权重分别由式(5)和式(6)设置;(2)统一设置权重,即将式(6)的偏移补偿设置为0.

3.2 结 果

3.2.1 检测精度

同文献[1],仍采用检测错误平衡(DET)曲线，即漏检率VS每窗口假正数曲线来衡量性能.该曲线对水平轴围的面积越小，表明性能越好.S-HOG、NL-HOG和EL-HOG的DET曲线如图4所示,NL-HOG性能比其他2种HOG差很多,EL-HOG和S-HOG性能相近.

图4 各HOG的性能比较Fig. 4 Performances of different HOG

从提高空间采样频率的角度看,EL-HOG与S-HOG一样.然而,由图4可见,在FPPW曲线的最高精度处,EL-HOG性能比S-HOG略差,原因如下：首先是维度因素,高维度能将信息表达得更离散一些,因此,SVM更容易找到其中最具鉴别性的成分.其次,对人这种由多个相对独立的部分(如头、手、躯干等)构成的对象而言,S-HOG对cell和block的尺寸进行了精挑细选,从而最大限度地获取了各部分的语义信息.而在同样的cell和block尺寸下,EL-HOG在一定程度上有所弱化.

图5显示了高斯权重的影响.由图5知,偏移补偿达到一定阈值后,EL-HOG的性能就很稳定了.说明只要block之外像素的权重不是特别低,其影响就很小,表明EL-HOG对高斯权重具有一定的鲁棒性.如果偏移补偿设置为0,EL-HOG就退化为NL-HOG.

图5 高斯权重的影响Fig. 5 Effect of Gaussian weight

3.2.2 计算代价

当采用滑动窗口策略,使用HOG进行目标检测时,检测算法在一个图像尺度上有4重循环:1)滑动窗口在图像上的滑动；2)block在每个窗口上的滑动；3)cell在每个block上的滑动；4)cell对每个像素的遍历.EL-HOG将第2个循环的执行次数由105降为32(假设窗口尺寸为64×128).在一个block中,EL-HOG方法参与线性插值的像素个数是S-HOG的1.75倍,因此,在该循环中,EL-HOG的计算量为S-HOG的32×1.75/105=0.53倍.

表1给出了在单个检测窗口上3种HOG花费的平均时间,实验使用配置为Intel i3-380M CPU、4G内存的笔记本电脑.可以看到EL-HOG耗费的时间超过了S-HOG的0.53倍.这主要是因为有一些常数时间的任务，如图像的载入、为比较性能将检测结果写入text文件的操作以及计算像素梯度等是无法通过EL-HOG加速的.另外,OpenCV采用特殊的数据结构加速S-HOG计算,而EL-HOG并没有.

表1 单个检测窗口消耗的平均时间

在分类器训练方面,S-HOG耗费3 h,而EL-HOG只用了不到1 h.两者的比值几乎与两者维度的比值一致.训练分类器的时间包括五折交叉验证寻找最佳训练参数的时间.

4 结 论

通过对cell位置线性插值的挖掘,设计了一种替代block部分重叠的降维方法.该方法在64×128尺寸检测窗口中，HOG的维度由3 780降为1 152.与已有方法相比,本文方法降低了特征计算量,且不依赖于特定的应用.与原HOG一样,EL-HOG方法仍然不能使用积分图进行计算，但已经取消了block部分重叠.若能进一步找到线性插值的替代方法,则可通过积分图极大加速HOG的提取,这也是一个很有意义的课题.

[1] DALAL N, TRIGGS B. Histograms of oriented gradients for Human detection[C]// The IEEE Conference on Computer and Pattern Recognition.Washington D C: IEEE Computer Society，2005：886-893.

[2] DOERSCH C, EFROS A. Improving the HOG descriptor[J/OL][2016-04-09]. http://www.cs.cmu.edu/～cdoersch/projects/hogimprove/hogimprove.pdf.

[3] QUATTONI A, CARRERAS X，TORRALBA A. A latent variable ranking model for content-based retrieval[C]// 34th European Conference on Information Retrieval.Berlin: Springer，2012.

[4] AVIDAN S， SHAMIR A. Seam carving for content-aware image resizing[C]//Proceeding of ACM SIGGRAPH. New York: ACM Transactions on Graphics，2007.

[5] BOSH A, ZISSERMAN A, MUNOZ X. Image classification using random forests and ferns[C]// IEEE International Conference on Computer Vision. Rio de Janeiro: IEEE Computer Society，2007:1-8.

[6] NAM W, DOLL′AR P, HAN J H. Local decorrelation for improved pedestrian detection[C]// NIPS2014 Montreal: Advances in Neural Information Processing Systems,2014:424-432.

[7] YANG B, YAN J, LEI Z, et al. Convolutional channel features[C]// ICCV2015. Santiago: Computer Science,2015:82-90.

[8] CAI Z, SABERIAN M, VASCONCELOS N. Learning complexity-Aware cascades for deep pedestrian detection[C]// ICCV2015. Santiago: Computer Science,2015:3361-3369.

[9] DANG L, BUI B, VO P D, et al. Improved HOG Descriptors[C]//In the Third International Conference on Knowledge and Systems Engineering. Washington DC: IEEE Computer Society，2011：186-189.

[10] DOLLAR P, TU Z, PERONA P, et al. Integral channel features[C]// BMVC. Belongie: BMVC 2009 London England，2009:1-11.

[11] FELZENSZWALB P F, GIRSHICK R B, MCALLESTER D, et al. Object detection with discriminatively trained part-based models[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(9):1627-1645.

[12] FRYER J, MCINTOSH K. Enhancement of image resolution in digital photogrammetry[J].Photogrammetric Engineering & Remote Sensing, 2001, 67(6): 741-749.

[13] VIOLA P, JONES M J. Robust real-time face detection[J]. International Journal of Computer Vision, 2004, 57(20):137-154.

[14] CHANG C, LIN C. LIBSVM: A library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 1-27. Software available at http://www.csie.ntu.edu.tw/～cjlin/libsvm

FU Hongpu1,2, ZOU Beiji1

(1.MinistryofEducation-ChinaMobileJointLaboratoryforMobileHealth，SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China; 2.DepartmentofInformationScienceandEngineering,HunanFirstNormalUniversity,Changsha410205,China)

To characterize the local object appearance and shape, histograms of oriented gradients (HOG) divide an image window into small spatial regions (cells), and accumulate a local 1-D histogram of gradient directions over the pixels of the cell. The normalized combined histogram entering of a larger spatial region (blocks, are consisted of several cells) forms the representation. In order to weaken regional quantization aliasing, blocks are partly overlapped when HOG is computed in detection windows. Yet, it will increase the dimension vastly. So, it will bring extra computation for object detection application. By expanding the area (spatial region) where pixel gradients are interpolated between neighbor cells’ centers, and setting the scale of block Gaussian weights properly, the overlapped area between blocks is cancelled. Then, the dimension of HOG feature in a 64×128 detection window reduces from 3 780 to 1 152, and region quantized errors are decreased. Experiment results on INRIA pedestrian dataset show that the performance of the 1 152-dimensional HOG and that of the original HOG are almost the same, however, its detecting speed is significantly improved.

histograms of oriented gradients; dimension reduction; linear interpolation; overlapping sampling; pedestrian detection

2016-07-25.

国家自然科学基金资助项目(61573380);湖南省重点实验室培育基地项目(2015TP1017).

傅红普(1973-)，ORCID:http://orcid.org/0000-0002-6376-4716，男，博士生，主要从事计算机视觉研究,E-mail：fuhpi@126.com.

10.3785/j.issn.1008-9497.2017.02.002

TP 391.41

A

1008-9497(2017)02-134-05

A dimension reduction method of the histogram of oriented gradients. Journal of Zhejiang University(Science Edition), 2017,44(2):134-138