傅紅普,鄒北驥

(1.中南大學 信息科學與工程學院 “移動醫(yī)療”教育部-中國移動聯(lián)合實驗室， 湖南 長沙 410083;2.湖南第一師范學院 信息科學與工程學院, 湖南 長沙 410205)

一種方向梯度直方圖的降維方法

傅紅普1,2,鄒北驥1

(1.中南大學 信息科學與工程學院 “移動醫(yī)療”教育部-中國移動聯(lián)合實驗室， 湖南 長沙 410083;2.湖南第一師范學院 信息科學與工程學院, 湖南 長沙 410205)

為描述對象的局部外觀和形狀,方向梯度直方圖首先將圖像劃分成小區(qū)域(被稱為cell),然后在其上累加像素梯度方向的一維直方圖.在被稱為block的較大區(qū)域(由數(shù)個相鄰的cell組成)上連接cell的直方圖，經歸一化處理形成特征向量.為減弱由block引起的區(qū)域量化走樣,在計算檢測窗口的特征時，采取部分重疊block的措施，從而大大增加了特征維度以及目標檢測時的計算量.通過擴大參與相鄰cell之間像素梯度插值的面積,并設置適當?shù)母咚蛊交顺叨?可消除block重疊,從而將64×128尺寸的窗口的方向梯度直方圖特征維度由3 780降低為1 152.INRIA的行人數(shù)據(jù)集實驗表明,該方法也可減弱區(qū)域量化走樣,且其性能與原方向梯度直方圖幾乎相當,而檢測速度卻顯著提高.

方向梯度直方圖;降維;線性插值;重疊采樣;行人檢測

方向梯度直方圖特征(histograms of oriented gradients，HOG)[1]在計算機視覺領域頗受關注.首先,視覺相似性可以通過HOG的余弦距離度量;其次,它是人類視覺相似性的合適模型，使用的是像素梯度而非像素強度,對全局對比度比較魯棒;而且,在梯度角度和小區(qū)域(cell)位置上的三線性插值以及block部分重疊極大消除了量化走樣[1-2].

HOG首先被用于行人檢測,再被應用到各種類別對象的檢測和識別上,包括汽車等剛體和馬等可形變體.HOG亦被廣泛應用于圖像檢索[3]、理解[4]、分類[5]等.近來,為獲得良好的性能目標，檢測領域亦采用HOG或類HOG特征[6-8].因此,研究如何提高HOG性能很有價值.

人們試圖提高HOG特征的鑒別能力.DOERSCH等[2]以很小的額外計算量獲得了較高的HOG邊界和條帶狀紋理處理能力，并試圖提高其鑒別能力.DANG等[9]通過在三層圖像金字塔上提取HOG,然后串接成特征向量，將行人檢測的性能提高了3%,其代價是更長的特征維數(shù)和隨之而來的額外計算量.文獻[10]通過將HOG和其他特征頻道相混合的方法提高鑒別能力.

對HOG進行降維的嘗試也很重要.針對某些目標檢測問題,FELZENSZWALB等[11]收集了block(由4個相鄰的cell構成，相當于cell的大區(qū)域)上的36維特征,對其進行PCA分析發(fā)現(xiàn)，前11維幾乎能表達所有特征信息.利用PCA特征向量生成子空間的特殊結構,其點積運算能將block上的HOG從36維降為13維.文獻[9]通過省略檢測窗口中信息量較少區(qū)域的特征來減少HOG向量的維度，提高檢測速度.現(xiàn)有降維工作對特定問題的先驗知識具有一定的依賴性.

1 HOG中的三線性插值和block部分重疊的窗口覆蓋

為描述對象的局部外觀和形狀,文獻[1]用局部像素強度梯度的直方圖作為特征表達,稱該特征為方向梯度直方圖.為保留位置信息,圖像窗口被分成多個小區(qū)域(被稱為cell),累加cell中每個像素的梯度構成1維梯度方向直方圖.為了使光照不變性更好,將4個相鄰cell組成一個名為block的更大區(qū)域;然后,使用block上的直方圖“能量”對4個cell上的直方圖進行歸一化.以像素為中心計算梯度,按梯度方向根據(jù)權重將梯度值分配到直方圖的對應項.使用HOG特征進行行人檢測.

在HOG中,按角度和所在位置,將像素梯度值分配到各cell區(qū)域的各方向項.為降低方向量化走樣,在相鄰的直方圖方向項之間對梯度值進行了線性插值.為避免由cell和block劃分帶來的區(qū)域量化走樣,首先,在縱橫相鄰的cell之間對梯度值進行線性插值,其與前述角度項的插值一起形成三線性插值;其次,block采取部分重疊的方式覆蓋檢測窗口.圖1示意了這2個措施的細節(jié).

圖1 cell位置雙線性插值(a)與block部分重疊(b)Fig.1 Interpolate pixel gradient between cell position centers (a) and partly overlap blocks (b)

圖1(a)給出了block左上角cell區(qū)域插值的詳細示意.對于原HOG的提取,只有在block中的像素梯度值才會參與cell之間的線性插值.插值時,cell從概念上被分成4個子區(qū)域.位于block 4個頂點處的子區(qū)域不對其他cell插值;處于block中心區(qū)域的4個子區(qū)域對4個cell都進行插值;其他子區(qū)域在其自身和與其緊鄰的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邊緣區(qū)域的影響.高斯核設置為block邊長的一半，高斯平滑減弱了重疊帶來的負面影響.

2 無block重疊的方法

提取HOG時,因有block部分重疊,在64×128大小的檢測窗口上需要計算105個block的特征.若直接依次覆蓋,則只需32個block.本文給出的替代方法無須block重疊就可減弱由block分割帶來的區(qū)域量化走樣.這樣,一個檢測窗口的特征維度大大降低,特征提取的計算量卻沒有增加,而且檢測速度大大提高了.

當采樣頻率不夠時,因為低頻和高頻混在一起,重構信號將與原信號有極大不同,就會出現(xiàn)走樣.當高頻成分不能被采樣設備析出時,就應該在采樣之前或之后先行移除以避免走樣.比如，對圖像的低通平滑濾波顯然會丟失很多原始信息.因此,防止走樣的最好方法是提高采樣頻率,如重疊采樣[12]，計算HOG時block部分重疊就是重疊采樣的一個例子.

注意到HOG中在相鄰cell之間的雙線性插值也是為了獲得cell空間采樣的連續(xù)性.但是,刻意將參與雙線性插值的像素限制在block之內，未能獲得block采樣的連續(xù)性.換個角度來看,block部分重疊正是為了獲得block空間采樣的連續(xù)性.鑒于此,本文給出了一個減弱block空間量化的方案，不必采取block部分重疊的方式來覆蓋檢測窗口,而是讓block之外緊鄰block的cell也參與線性插值，從而獲得block空間的連續(xù)性.

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,即參與雙線性插值的像素個數(shù)是原HOG的1.75倍.像素梯度的計算量沒有增加,單純的插值計算量增加亦不多，可完全由block數(shù)量減少降低的計算量抵消.圖2為左上角額外區(qū)域線性插值的情況.插值方法與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的特征,現(xiàn)需重新考慮高斯平滑，以給block之外像素適當權重.若簡單地給block之內和之外一致的權重,全部使用0.5個block寬度的高斯核,則block之外區(qū)域像素的權重會顯得太小.

本文,在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之外參與插值像素的權重過小.實驗發(fā)現(xiàn),當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行人數(shù)據(jù)集上,將本文方法(稱為EL-HOG)、原標準HOG(稱為S-HOG)及取消block部分重疊的原HOG(稱為NL-HOG, NL-HOG, N?ve Lower dimension standard HOG)進行了性能對比.提取NL-HOG特征時,除了block不重疊外,其他所有參數(shù)設置都同S-HOG, 64×128尺寸的檢測窗口上得到的NL-HOG特征的維度也為1 152.

3.1 實 驗

3.1.1 3種HOG比較

直接通過OpenCV 2.3.1中HOG的實現(xiàn)來提取S-HOG特征,其他2個是通過修改OpenCV2.3.1中HOG的實現(xiàn)得到的.將檢測窗口中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個像素的周圍環(huán)境圖像,這些邊界為檢測提供了重要的上下文信息[1].提取EL-HOG時,在檢測窗口上增加了額外0.5個cell寬度的邊界,但是將這些像素的值都設置為0.否則,EL-HOG檢測窗口使用的額外邊界寬度為24個像素,造成EL-HOG、S-HOG及NL-HOG使用信息不一致.

分別使用3個HOG的LIBSVM[14]訓練線性SVM分類器、使用5折交叉驗證以確定最優(yōu)訓練參數(shù).

3.1.2 EL-HOG中高斯權重的影響

測試了不同高斯權重對EL-HOG性能的影響.使用2種權重設置方式：(1)block之內和block之外其權重分別由式(5)和式(6)設置;(2)統(tǒng)一設置權重,即將式(6)的偏移補償設置為0.

3.2 結 果

3.2.1 檢測精度

同文獻[1],仍采用檢測錯誤平衡(DET)曲線，即漏檢率VS每窗口假正數(shù)曲線來衡量性能.該曲線對水平軸圍的面積越小，表明性能越好.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的性能就很穩(wěn)定了.說明只要block之外像素的權重不是特別低,其影響就很小,表明EL-HOG對高斯權重具有一定的魯棒性.如果偏移補償設置為0,EL-HOG就退化為NL-HOG.

圖5 高斯權重的影響Fig. 5 Effect of Gaussian weight

3.2.2 計算代價

當采用滑動窗口策略,使用HOG進行目標檢測時,檢測算法在一個圖像尺度上有4重循環(huán):1)滑動窗口在圖像上的滑動；2)block在每個窗口上的滑動；3)cell在每個block上的滑動；4)cell對每個像素的遍歷.EL-HOG將第2個循環(huán)的執(zhí)行次數(shù)由105降為32(假設窗口尺寸為64×128).在一個block中,EL-HOG方法參與線性插值的像素個數(shù)是S-HOG的1.75倍,因此,在該循環(huán)中,EL-HOG的計算量為S-HOG的32×1.75/105=0.53倍.

表1給出了在單個檢測窗口上3種HOG花費的平均時間,實驗使用配置為Intel i3-380M CPU、4G內存的筆記本電腦.可以看到EL-HOG耗費的時間超過了S-HOG的0.53倍.這主要是因為有一些常數(shù)時間的任務，如圖像的載入、為比較性能將檢測結果寫入text文件的操作以及計算像素梯度等是無法通過EL-HOG加速的.另外,OpenCV采用特殊的數(shù)據(jù)結構加速S-HOG計算,而EL-HOG并沒有.

表1 單個檢測窗口消耗的平均時間

在分類器訓練方面,S-HOG耗費3 h,而EL-HOG只用了不到1 h.兩者的比值幾乎與兩者維度的比值一致.訓練分類器的時間包括五折交叉驗證尋找最佳訓練參數(shù)的時間.

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