熊　林　張小鋒　夏鵬飛

(南昌航空大學(xué)信息工程學(xué)院　南昌　330063)

?

一種基于梯度規(guī)范化的目標(biāo)檢測算法*

熊林張小鋒夏鵬飛

(南昌航空大學(xué)信息工程學(xué)院南昌330063)

針對傳統(tǒng)的目標(biāo)檢測任務(wù)都是基于滑動窗口模型來提取特征的,由于產(chǎn)生過多冗余的窗口會顯著增加計(jì)算量并且對后續(xù)的特征提取和分類任務(wù)造成影響,提出一種選擇性搜索結(jié)合梯度規(guī)范化的特征提取算法,首先利用選擇性搜索算法產(chǎn)生一組目標(biāo)區(qū)域集,該算法能夠大幅度降低搜索空間并產(chǎn)生較少的目標(biāo)區(qū)域,然后利用梯度規(guī)范化對目標(biāo)區(qū)域進(jìn)行特征映射,通過對這些特征向量分類能夠提高檢測精度

選擇性搜索; 規(guī)范化梯度; 特征映射; 目標(biāo)檢測

Class NumberTP301.6

1　引言

選擇性搜索(Selective Search)[8]算法綜合了蠻力搜索[1～3](Exhaustive Search)和分割(Segmentation)[4～5]的方法,既有分割方法的從底至上的層級結(jié)構(gòu),也有密集搜索能夠找到所有可能位置的優(yōu)點(diǎn)。該算法能夠顯著減少搜索空間并減少計(jì)算量,本文使用選擇性搜索算法來提取目標(biāo)區(qū)域,該算法能夠獲取圖像中目標(biāo)所有可能出現(xiàn)的位置并將目標(biāo)分割出來形成一組目標(biāo)區(qū)域集,首先將這組目標(biāo)區(qū)域集中所有的元素二值化,然后將這些二值化的目標(biāo)區(qū)域梯度規(guī)范化并提取其特征向量,總的來說,選擇性搜索結(jié)合梯度規(guī)范化算法進(jìn)行目標(biāo)檢測具有以下優(yōu)點(diǎn),利用自下而上的聚合算法生成一組類獨(dú)立的目標(biāo)位置,再利用梯度規(guī)范化算法結(jié)合以上兩點(diǎn)可以顯著地減少檢測算法的計(jì)算量且能夠以足夠高的精度提取出圖像中的目標(biāo)。

2　相關(guān)工作

傳統(tǒng)的目標(biāo)提取算法都是基于逐窗口模型,該類算法會產(chǎn)生大量的特征窗口,使得后續(xù)分類器的計(jì)算量過大,不利于實(shí)際應(yīng)用,為了解決這個(gè)問題本文提出使用選擇性搜索算法進(jìn)行目標(biāo)提取,選擇性搜索算法充分結(jié)合了蠻力搜索和自下而上的圖像分割的優(yōu)勢,在產(chǎn)生較少目標(biāo)區(qū)域的前提下,能夠搜索到幾乎所有目標(biāo)的準(zhǔn)確區(qū)域。圖1是利用選擇性搜索算法對兩幅圖像進(jìn)行目標(biāo)檢測的實(shí)例圖,可以看出算法有效地找出各種尺度的所有可能目標(biāo)的區(qū)域。選擇性搜索算法主要是利用了基于圖的圖像分割,使用貪心算法迭代地將每一個(gè)區(qū)域聚合,當(dāng)合并區(qū)域?yàn)檎麖垐D片則終止合并,具體流程見算法1:

圖1　所有尺度的預(yù)選區(qū)域

算法1:基于圖的選擇性搜索算法流程

1) 輸入:RGB圖像

2) 利用[7]中算法獲取一組初始區(qū)域

R={r1,…,rn}

3) 初始化相似度集合S=?

4) foreach每對區(qū)域pair(r1,r2)do

統(tǒng)計(jì)相似度s(ri,rj)

更新相似度集合S=S∪S(ri,rj)

5) whileS≠?do

得到最高相似度s(ri,rj)=max(S)

合并相似度最高的區(qū)域tt=ri∪rj

刪除集合S中與ri有關(guān)的元素:S=S/s(ri,r*)

刪除集合S中與rj有關(guān)的元素:S=S/s(r*,rj)

計(jì)算區(qū)域rt及其相鄰區(qū)域的相似度集合St:S=S∪St,R=R∪rt

6) 輸出: 一組從圖像中提取的目標(biāo)集

這樣算法1便在圖像中提取出了一組目標(biāo)集,記作Setfeatures(S),使用選擇性搜索算法在每一張圖像里面大約能提取出2000個(gè)目標(biāo)區(qū)域,這顯然有大量非目標(biāo)區(qū)域被提取出來。

3　梯度規(guī)范化提取目標(biāo)區(qū)域特征

根據(jù)文獻(xiàn)[9～10],實(shí)際上圖片中的每個(gè)目標(biāo)都是獨(dú)立的并且具有確切的邊界框和中心點(diǎn),普通目標(biāo)的邊界框與其規(guī)范化梯度具有很強(qiáng)的相關(guān)性,各個(gè)不同目標(biāo)區(qū)域的梯度有明顯的區(qū)別,其次,每一個(gè)目標(biāo)區(qū)域都可以用一組特征向量和混合特征值來表示,基于上述觀點(diǎn)提出梯度規(guī)范化特征對目標(biāo)進(jìn)行特征提取,

首先將目標(biāo)集Setfeature(S)所有區(qū)域目標(biāo)窗口的尺寸歸一化為8*8,如圖2,并計(jì)算歸一化后每個(gè)窗口的特征,將這個(gè)64維特征向量稱為梯度規(guī)范化特征,將每一個(gè)特征歸一化到[0,255]之間,利用目標(biāo)與非目標(biāo)之間的梯度規(guī)范化特征具有明顯的區(qū)別[11],梯度規(guī)范化算法將每一個(gè)特征向量輸入到一個(gè)級聯(lián)支持向量機(jī)中進(jìn)行分類,首先將原圖縮放到固定尺寸的大小(W0,H0)∈{10,20,40,80,160,320},如圖2所示,并以此計(jì)算其梯度特征,然后利用8*8的出窗口模型掃描縮放后的圖像。

圖2　梯度規(guī)范化算法示意圖

(1)

l=(i,x,y)

(2)

上式中:sl為濾波分?jǐn)?shù)；ω為權(quán)值矩陣,gl為梯度規(guī)范化特征,l為窗口位置,i為預(yù)定義尺度；(x,y)為窗口內(nèi)任意點(diǎn)坐標(biāo)。使用非最大化抑制算法選擇一部分尺寸為i的窗口并用SVM線性模型計(jì)算其目標(biāo)分?jǐn)?shù):

ol=υi·sl+ti

(3)

其中:i為預(yù)定義尺寸；υi為線性模型；ti為偏差。為減少計(jì)算量,二值化模型w[12,13],即用一組基向量的線性組合表示w

(4)

其中:w∈R64,αj∈{-1,1}64為基向量,βj∈R為相關(guān)系數(shù)。

算法2:二值化模型w

輸入:w,Nw

初始化余項(xiàng):ε=w

forj=1toNwdo

αj=sign(ε)

ε←ε-βjαj

endfor

基向量可由二值向量和它的補(bǔ)向量表示

(5)

(6)

其中:b為64維二進(jìn)制數(shù)。這樣就將一個(gè)區(qū)域目標(biāo)映射為一個(gè)二值梯度規(guī)范化特征了。我們考慮將這兩種算法進(jìn)行融合。首先對原圖像使用選擇性搜索算法提取目標(biāo)區(qū)域集,然后利用梯度規(guī)范化算法對所有目標(biāo)區(qū)域進(jìn)行特征映射,最后用訓(xùn)練好的級聯(lián)支持向量機(jī)對這些梯度規(guī)范化特征分類,算法流程如圖3所示。

圖3　特征提取流程

4　實(shí)驗(yàn)與算法評估

所有實(shí)驗(yàn)均在同一平臺上進(jìn)行,CPU:Inteli7-4720HQ2.6GHz,內(nèi)存:8GB,顯卡:NvidiaGTX960,OS:UbuntuLinux14.04LTS,數(shù)據(jù)集:VOC2007。為了評估算法提取的區(qū)域的好壞,定義ABO(AverageBestOverlap)和MABO(MeanAverageBestOverlap)[5],ABO表征的是已標(biāo)定數(shù)據(jù)和數(shù)據(jù)集中產(chǎn)生的目標(biāo)區(qū)域L之間的最佳重疊率,由下式計(jì)算:

(7)

根據(jù)文獻(xiàn)[14]有:

(8)

即MABO表征所有類的平均ABO。

這一節(jié)利用MABO-#WIN來評估算法的MABO和目標(biāo)區(qū)域數(shù)量,將本文提出的算法與其他集中具有代表性的算法比較,這些算法都是基于滑動窗口模型。

從表1可以看出,在提取出同樣數(shù)量的目標(biāo)區(qū)域前提下,本文提出的算法MABO達(dá)到了0.885,下圖展示了一組MABO介于0.855～0.876之間的檢測精度效果圖。

表1　實(shí)驗(yàn)中各目標(biāo)檢測算法的檢測指標(biāo)

圖4　一組MABO介于0.855-0.876之間的檢測例子

另外,表1中的偏差表征了算法的泛化能力,本文提出的算法偏差為0.046是最低的,這表明算法對于不同的檢測目標(biāo)依然具有很高的魯棒性(泛化能力強(qiáng))。這主要是因?yàn)閷δ繕?biāo)區(qū)域的二值化處理,使得算發(fā)對目標(biāo)的旋轉(zhuǎn),縮放不敏感。

由于選擇性搜索具有密集搜索的特點(diǎn),在每張圖片中大概能夠提取2000個(gè)預(yù)選區(qū)域,顯然在一般的圖片中不可能具有這么多的待檢測目標(biāo),另一方面由于目標(biāo)可能以任何尺度出現(xiàn)在圖片中,這就要求算法必須能夠在預(yù)選目標(biāo)的數(shù)量和質(zhì)量中做出一個(gè)權(quán)衡,即算法應(yīng)該能夠在盡可能少的預(yù)選目標(biāo)中以足夠高的精度檢測出圖片中的每個(gè)目標(biāo),圖5是本文提出的算法與其他算法的召回率(Recall)比較,從圖中可以看出本文提出的算法在目標(biāo)區(qū)域數(shù)量為1000之后較其他算法有顯著提高。

圖5　召回率

5　結(jié)語

本文提出了一種選擇性搜索結(jié)合梯度規(guī)范化的目標(biāo)檢測算法,對比傳統(tǒng)的滑動窗口模型,選擇性搜索能顯著的減少搜索空間,由于這兩種算法在利用圖像信息上具有互補(bǔ)性,本文提出的算法較其他達(dá)到相同召回率時(shí)能減少約1500個(gè)目標(biāo)區(qū)域窗口。

[1] Dalal N, Triggs B. Histograms of Oriented Gradients for Human Detection[C]//IEEE Conference on Computer Vision & Pattern Recognition,2005:886-893.

[2] Harzallah H, Jurie F, Schmid C. Combining efficient object localization and image classification[C]//IEEE International Conference on Computer Vision,2009:237-244.

[3] P. Viola, M. J. Jones. Robust real-time face detection[C]//IJCV,2004,57:137-154.

[4] Viola P, Jones M J. Robust Real-Time Face Detection[J]. International Journal of Computer Vision,2004,57(2):137-154.

[5] Endres I, Hoiem D. Category independent object proposals[C]//Computer Vision-ECCV 2010. Springer Berlin Heidelberg,2010:575-588.

[6] Browet A, Absil P A, Dooren P V. Contour detection and hierarchical image segmentation[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence,2011,33(5):898-916.

[7] Felzenszwalb P F, Huttenlocher D P. Efficient Graph-Based Image Segmentation[J]. International Journal of Computer Vision,2004,59(2):167-181.

[8] Uijlings J R R, Sande K E A V D, Gevers T, et al. Selective Search for Object Recognition[J]. International Journal of Computer Vision,2013,104(2):154-171.

[9] Bogdan A, Thomas D, Vittorio F. Measuring the objectness of image windows[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence,2012,34(11):2189-2202.

[10] Heitz G, Koller D. Learning Spatial Context: Using Stuff to Find Things[C]//European Conference on Computer Vision. Springer-Verlag,2008:30-43.

[11] Cheng M M, Zhang Z, Lin W Y, et al. BING: Binarized Normed Gradients for Objectness Estimation at 300fps[C]//Computer Vision and Pattern Recognition(CVPR), 2014 IEEE Conference on. IEEE,2014:3286-3293.

[12] Hare S. Efficient online structured output learning for keypoint-based object tracking[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2012:1894-1901.

[13] Zheng S, Sturgess P, Torr P H S. Approximate structured output learning for Constrained Local Models with application to real-time facial feature detection and tracking on low-power devices[M]. IEEE,2013:1-8.

[14] Everingham M, Gool L V, Williams C K I, et al. The Pascal Visual Object Classes (VOC) Challenge[J]. International Journal of Computer Vision,2010,88(2):303-338.

[15] Bogdan A, Thomas D, Vittorio F. Measuring the objectness of image windows[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence,2012,34(11):2189-2202.

[16] Ian E, Derek H. Category-independent object proposals with diverse ranking[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence,2014,36(2):222-234.

An Object Detection Algorithm Based on Normalize Gradients

XIONG LinZHANG XiaofengXIA Pengfei

(School of Information Engineering, Nanchang Hangkong University, Nanchang330063)

In view of the fact that the traditional object detection task is based on sliding window model to extract the features, which may produce so many redundant windows that will significantly increase the amount of calculation and affect the subsequent feature extraction and classification task. In order to present an extraction algorithm which combines selective search and gradient standardization. First, selective search algorithm is used to produce a set of the object areas, which can greatly reduce the search space and produce fewer object areas. Then the object areas are mapped by exploiting the gradient feature normalize. The detection accuracy will be improved by classifying these feature vectors

selective search, normalize gradient, feature mapping, object detection

2016年4月6日,

2016年5月11日

國家自然科學(xué)基金(編號：61272077)；江西省自然科學(xué)基金(編號：2014BAB207012)；江西省重點(diǎn)實(shí)驗(yàn)室開放基金(編號：TX201204005)；南昌航空大學(xué)研究生創(chuàng)新專項(xiàng)資金資助項(xiàng)目(編號：YC2015037)資助。

熊林，男，碩士研究生，研究方向：圖像處理，深度學(xué)習(xí)，目標(biāo)跟蹤。張小鋒，男，博士研究生，副教授，碩士生導(dǎo)師，研究方向：計(jì)算機(jī)視覺，目標(biāo)檢測，圖像處理。夏鵬飛，男，碩士研究生，研究方向：圖像處理，計(jì)算機(jī)視覺。

TP301.6

10.3969/j.issn.1672-9722.2016.10.009