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

傅紅普,鄒北驥

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

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

傅紅普1,2,鄒北驥1

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

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

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

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

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

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

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

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

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

在HOG中,按角度和所在位置,將像素梯度值分配到各cell區(qū)域的各方向項(xiàng).為降低方向量化走樣,在相鄰的直方圖方向項(xiàng)之間對(duì)梯度值進(jìn)行了線性插值.為避免由cell和block劃分帶來的區(qū)域量化走樣,首先,在縱橫相鄰的cell之間對(duì)梯度值進(jìn)行線性插值,其與前述角度項(xiàng)的插值一起形成三線性插值;其次,block采取部分重疊的方式覆蓋檢測(cè)窗口.圖1示意了這2個(gè)措施的細(xì)節(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ū)域插值的詳細(xì)示意.對(duì)于原HOG的提取,只有在block中的像素梯度值才會(huì)參與cell之間的線性插值.插值時(shí),cell從概念上被分成4個(gè)子區(qū)域.位于block 4個(gè)頂點(diǎn)處的子區(qū)域不對(duì)其他cell插值;處于block中心區(qū)域的4個(gè)子區(qū)域?qū)?個(gè)cell都進(jìn)行插值;其他子區(qū)域在其自身和與其緊鄰的cell上進(jìn)行插值.具體來說,提取HOG時(shí),直方圖按式(1)累加得到.

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

|x-xi|

(1)

其中,hθ(xi,yi)為第i個(gè)cell在方向角度θ上的HOG分量,i=0,1,2,3;Mθ(x,y)為像素(x,y)在方向角度θ的梯度值;(xi,yi)為第i個(gè)cell的中心位置坐標(biāo);dx和dy分別為2個(gè)相鄰cell在x和y軸方向的距離,原HOG中dx和dy都是8個(gè)像素.

如圖1(b)所示，對(duì)block重疊一半的面積進(jìn)行了高斯平滑，以減弱像素對(duì)block邊緣區(qū)域的影響.高斯核設(shè)置為block邊長(zhǎng)的一半，高斯平滑減弱了重疊帶來的負(fù)面影響.

2 無block重疊的方法

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

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

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

2.1 擴(kuò)展線性插值范圍

除block內(nèi)的像素外,緊鄰block的cell中的像素梯度也參與到cell位置的雙線性插值,按照HOG的cell雙線性插值方法,只需包含額外的0.5個(gè)cell寬度即可.這樣,檢測(cè)窗口由無相互重疊的block直接覆蓋.

此方式,只有block之外的參與插值的cell被重疊,覆蓋一個(gè)64×128的檢測(cè)窗口只需32個(gè)block,而不是原本的105個(gè).一個(gè)檢測(cè)窗口中的特征維度由7×15×36=3 780降為4×8×36=1 152.圖2為本文給出的block中cell位置雙線性插值示意圖.

在原HOG提取方法中,有4個(gè)cell的像素梯度參與cell間的雙線性插值.增加0.5個(gè)cell寬度的額外面積后,參與線性插值的面積增加到了7個(gè)cell,即參與雙線性插值的像素個(gè)數(shù)是原HOG的1.75倍.像素梯度的計(jì)算量沒有增加,單純的插值計(jì)算量增加亦不多，可完全由block數(shù)量減少降低的計(jì)算量抵消.圖2為左上角額外區(qū)域線性插值的情況.插值方法與block之內(nèi)像素方法一致，只在相鄰cell之間插值,見式(2).

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

|x-xi|

(2)

其中各符號(hào)的含義同式(1).

圖2 本文方法給出的cell位置雙線性插值示意圖Fig. 2 Cell position interpolation of the proposed method

2.2 重新考量block的高斯權(quán)重

有更多像素給予了block的特征,現(xiàn)需重新考慮高斯平滑，以給block之外像素適當(dāng)權(quán)重.若簡(jiǎn)單地給block之內(nèi)和之外一致的權(quán)重,全部使用0.5個(gè)block寬度的高斯核,則block之外區(qū)域像素的權(quán)重會(huì)顯得太小.

本文,在block之內(nèi)、之外的像素的高斯權(quán)重分別按式(3)和(4)設(shè)置.圖3給出了block之內(nèi)和之外的高斯權(quán)重分布示意圖，這種分別設(shè)置權(quán)重的方式增加了靈活性.

ω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中心的坐標(biāo),(bx,by)是對(duì)block之外像素的偏移補(bǔ)償.該補(bǔ)償可防止block之外參與插值像素的權(quán)重過小.實(shí)驗(yàn)發(fā)現(xiàn),當(dāng)block高斯權(quán)重的設(shè)置與原HOG相同時(shí)性能最好.

圖3 block之內(nèi)及之外像素權(quán)重示意圖Fig.3 Pixel gradient weight in and outside the block

此方法稱為擴(kuò)展cell位置線性插值范圍、無block重疊HOG(EL-HOG),將原HOG稱為標(biāo)準(zhǔn)HOG(S-HOG).

3 實(shí)驗(yàn)及結(jié)果

在INRIA行人數(shù)據(jù)集上,將本文方法(稱為EL-HOG)、原標(biāo)準(zhǔn)HOG(稱為S-HOG)及取消block部分重疊的原HOG(稱為NL-HOG, NL-HOG, N?ve Lower dimension standard HOG)進(jìn)行了性能對(duì)比.提取NL-HOG特征時(shí),除了block不重疊外,其他所有參數(shù)設(shè)置都同S-HOG, 64×128尺寸的檢測(cè)窗口上得到的NL-HOG特征的維度也為1 152.

3.1 實(shí) 驗(yàn)

3.1.1 3種HOG比較

直接通過OpenCV 2.3.1中HOG的實(shí)現(xiàn)來提取S-HOG特征,其他2個(gè)是通過修改OpenCV2.3.1中HOG的實(shí)現(xiàn)得到的.將檢測(cè)窗口中block的滑動(dòng)步長(zhǎng)設(shè)置為block的邊長(zhǎng)就得到了NL-HOG. EL-HOG默認(rèn)的高斯權(quán)重設(shè)置如下:高斯核大小為block的1/4,偏移補(bǔ)償為1/2 cell長(zhǎng)度,即

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

(5)

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

(6)

檢測(cè)窗口的大小仍設(shè)置為64×128.在使用S-HOG檢測(cè)行人時(shí),檢測(cè)窗口在行人樣本的周圍包含了約16個(gè)像素的周圍環(huán)境圖像,這些邊界為檢測(cè)提供了重要的上下文信息[1].提取EL-HOG時(shí),在檢測(cè)窗口上增加了額外0.5個(gè)cell寬度的邊界,但是將這些像素的值都設(shè)置為0.否則,EL-HOG檢測(cè)窗口使用的額外邊界寬度為24個(gè)像素,造成EL-HOG、S-HOG及NL-HOG使用信息不一致.

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

3.1.2 EL-HOG中高斯權(quán)重的影響

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

3.2 結(jié) 果

3.2.1 檢測(cè)精度

同文獻(xiàn)[1],仍采用檢測(cè)錯(cuò)誤平衡(DET)曲線，即漏檢率VS每窗口假正數(shù)曲線來衡量性能.該曲線對(duì)水平軸圍的面積越小，表明性能越好.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略差,原因如下：首先是維度因素,高維度能將信息表達(dá)得更離散一些,因此,SVM更容易找到其中最具鑒別性的成分.其次,對(duì)人這種由多個(gè)相對(duì)獨(dú)立的部分(如頭、手、軀干等)構(gòu)成的對(duì)象而言,S-HOG對(duì)cell和block的尺寸進(jìn)行了精挑細(xì)選,從而最大限度地獲取了各部分的語義信息.而在同樣的cell和block尺寸下,EL-HOG在一定程度上有所弱化.

圖5顯示了高斯權(quán)重的影響.由圖5知,偏移補(bǔ)償達(dá)到一定閾值后,EL-HOG的性能就很穩(wěn)定了.說明只要block之外像素的權(quán)重不是特別低,其影響就很小,表明EL-HOG對(duì)高斯權(quán)重具有一定的魯棒性.如果偏移補(bǔ)償設(shè)置為0,EL-HOG就退化為NL-HOG.

圖5 高斯權(quán)重的影響Fig. 5 Effect of Gaussian weight

3.2.2 計(jì)算代價(jià)

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

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

表1 單個(gè)檢測(cè)窗口消耗的平均時(shí)間

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

4 結(jié) 論

通過對(duì)cell位置線性插值的挖掘,設(shè)計(jì)了一種替代block部分重疊的降維方法.該方法在64×128尺寸檢測(cè)窗口中，HOG的維度由3 780降為1 152.與已有方法相比,本文方法降低了特征計(jì)算量,且不依賴于特定的應(yīng)用.與原HOG一樣,EL-HOG方法仍然不能使用積分圖進(jìn)行計(jì)算，但已經(jīng)取消了block部分重疊.若能進(jìn)一步找到線性插值的替代方法,則可通過積分圖極大加速HOG的提取,這也是一個(gè)很有意義的課題.

[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.

國家自然科學(xué)基金資助項(xiàng)目(61573380);湖南省重點(diǎn)實(shí)驗(yàn)室培育基地項(xiàng)目(2015TP1017).

傅紅普(1973-)，ORCID:http://orcid.org/0000-0002-6376-4716，男，博士生，主要從事計(jì)算機(jī)視覺研究,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