蒲寶明, 霍　紅, 楊東升, 李相澤

(1. 中國科學院 沈陽計算技術研究所, 遼寧 沈陽　110870;2. 東北大學 計算機科學與工程學院, 遼寧 沈陽　110819)

?

交互式分割算法的可變形目標檢測

蒲寶明1, 霍紅1, 楊東升1, 李相澤2

(1. 中國科學院 沈陽計算技術研究所, 遼寧 沈陽110870;2. 東北大學 計算機科學與工程學院, 遼寧 沈陽110819)

針對現(xiàn)有高檢測精度算法效率較低的問題,提出一種利用基于水平集的交互式目標分割算法對圖像進行預分割的方法,提高了對可變形目標檢測的效率.算法首先使用交互式目標分割算法對圖像進行初步分割,然后根據(jù)分割區(qū)域進行部件檢測.對于部件模型,使用傳統(tǒng)的梯度向量直方圖來進行描述.預先對圖像進行分割,可以減少檢測窗口的檢測范圍,對于像素較高的圖片尤其重要.實驗結果發(fā)現(xiàn),與窮舉搜索的滑動窗口相比,交互式分割算法在速度方面有明顯的提高.

目標檢測; 圖像分割; 交互式分割; 梯度向量直方圖; 可變形部件模型

隨著計算機技術的飛速發(fā)展,計算機視覺得到了廣泛的應用.目前,在智能監(jiān)控系統(tǒng)、軍事目標檢測及醫(yī)學導航手術等方面,目標檢測技術具有很高的應用價值[1-2].

目標檢測領域中最具有代表性的算法大概分成三類:第一類是基于整體特征的算法.第二類稱為基于多部位的方法[3].第三類是基于多視角的方法[4-5].這三類方法有一個共同需求就是需要一個檢測窗口來處理圖像中的該區(qū)域特征并進行評價.那么,由于圖像中有大量的像素點,而且檢測窗口不宜過大,這就使得檢測窗口在圖像中的遍歷順序變得很重要.目前,使用最多的是滑動窗口(Sliding window methods)[6-8].這種方法能夠將目標檢測結合分類器來判斷矩形窗口下的圖像區(qū)域是否為檢測對象.

滑動窗口的一個主要檢測方式就是將檢測窗口置于不同尺度的圖像中的每個像素點上,然后判斷窗口覆蓋區(qū)域是否為目標.這種窮舉搜索方式的優(yōu)點是保證準確率. 但是它的缺點也十分明顯,主要就是計算量過大,檢測效率比較低.

針對以上問題,本文基于傳統(tǒng)的可變形部件檢測模型,在描述圖像特征之前預先將圖像分割成若干區(qū)域,以減少滑動窗口的遍歷時間.本文使用的分割方法是傳統(tǒng)水平集方法的改進,提高了原方法的收斂速度.本文主要從兩方面來介紹:①對圖像進行預處理時使用的分割算法----交互式目標分割算法.②檢測圖像時用來描述圖像特征的可變形部件模型.

1　基于水平集方法的交互式目標分割算法

交互式目標分割算法需要用戶輸入最初的輪廓作為初始信息.因此,模型應該既包含初期輸入輪廓特征,又包含圖像中目標的特征.

不管動態(tài)輪廓的形態(tài)怎么樣,模型應該使現(xiàn)在的動態(tài)輪廓向目標輪廓盡快逼近[9].這樣,該模型要包含目標輪廓的信息.可以利用基于像素值的梯度向量使附近目標盡快移動其動態(tài)輪廓.為了克服動態(tài)輪廓在靠近目標輪廓時收斂性很低的問題,本文利用GVF(Gradient Vector Flow)模型,圖像上每個點的GVF方向都指向目標輪廓.如果像素點逼近目標輪廓的位置,那么GVF的幅值就會變大,而在像素值變化不大的區(qū)域中幅值相對較小.在圖像中,給定目標的狀態(tài)具有多樣性.例如,假設目標的輪廓是模糊的,那么,在不考慮圖像區(qū)域信息的情況下(也就是說,只有上述目標輪廓的信息),得到的結果會產(chǎn)生收縮現(xiàn)象,甚至被收縮到一個點[10].所以,圖像區(qū)域信息是非常有價值的,這樣得到正確的目標輪廓會變得比較容易.需要導入Heaviside函數(shù).Heaviside函數(shù)定義可用式(1)表示.

(1)

包含圖像區(qū)域信息的速度函數(shù)式為

(2)

高斯概率密度函數(shù)p(I(x,y))的具體展開式,可用式(3)表示:

(3)

結合輪廓信息項和區(qū)域信息項,總體的速度函數(shù)如式(4)所示.

(4)

式中,α和β隨著圖像的狀態(tài)不同而取不同的值,圖像內(nèi)噪聲越多越大.α和β之間的關系是α+β=1.

交互式目標分割過程,就是使用由用戶輸入的初期輪廓到目標的實際邊緣進化輪廓的迭代過程.輪廓進化的正確性跟它的速度函數(shù)有關.該方法提出的速度函數(shù)有式(4)的形式.在具體實現(xiàn)過程中,使用近似函數(shù)Hε代替Heaviside函數(shù)H(φ),近似函數(shù)Hε的具體形式如下:

(5)

式中,跟CV模型一樣ε=1.另外,Hε的微分δε(φ)的具體的形式如下:

(6)

2　可變形部件模型

可變形部件模型是對滑動窗口方法比較經(jīng)典的應用.在可變形部件模型中,可以通過部件模型對分割出來的各個子區(qū)域進行單獨判斷并對該子區(qū)域評估分類.模型中的特征是用HOG來描述的.

2.1HOG算法

經(jīng)典的梯度方向直方圖(Histogram of Oriented Gradients,簡稱HOG)[11]通過描述目標特征,最終形成特征集.

文獻[3]給出了圖片的HOG特征表示方法.首先圖片被分割成比較小的塊,邊長在4～8像素效果比較好.我們稱這樣的塊為cell,并且各個cell之間是不重疊的.針對每個cell來統(tǒng)計該區(qū)域內(nèi)的像素梯度,并把每個像素的梯度值離散化到9個方向中,加到每個方向中的權重是根據(jù)梯度大小決定的.這樣,直方圖可以捕獲目標的形狀屬性,但是忽略了細小的形變.為了減少光照等背景因素的影響,HOG算法把多個cell,比如2×2,組成一個block.block之間通過相互重疊來弱化光照對梯度的影響.

通過構建HOG特征金字塔來解決圖像尺度不同的問題.金字塔的頂層用來捕獲目標的粗糙特征集,比如根濾波器檢測目標整體.金字塔的下面幾層用來捕獲比較精細的特征集,比如部件濾波器對部件的評分.

2.2可變形部件模型

可變形部件模型包含一個全局根濾波器和幾個部件濾波器.檢測窗口的評分(score)是通過根濾波器的評分與部件濾波器在候選點區(qū)域的綜合評分得到的.根濾波器和部件濾波器評分方式都是通過計算預先訓練的一組權值與窗口區(qū)域中的HOG之間的點積(dot product)而得到的.每一個樣本x用式(7)來計算評分:

(7)

式中:β是一個模型參數(shù)變量;z是待檢測區(qū)域;H表示特征金字塔;p=(x,y,l)表示金字塔的第l層的cell;φ(H,p,w,h)表示金字塔中的w×h子窗口,這個子窗口左上角的坐標為p[12].為了方便表述,不影響理解的情況下,后文用φ(H,p)來代替φ(H,p,w,h).

假設目標模型含有n個部件,那么需要定義一個根濾波器F0和一組包含n個部件的模型(P1,…,Pn),其中Pi=(Fi,vi,si,ai,bi),Fi是第i個部件的濾波器;vi是二維向量,用來表示第i個部件候選區(qū)域的起始坐標;si給出了這個候選區(qū)域的大小;ai和bi是用來確定二次方程系數(shù)的二維向量,這個方程用于計算第i個部件在這個候選區(qū)域的評分.候選區(qū)域用z=(p0,…,pi)表示,其中pi=(xi,yi,li),當i=0時表示根濾波器的位置,當i>0時表示第i個部件的位置[13].檢測的評分由根濾波器的評分加上與根相關的每個部件放置點的評分,如式(8)所示:

(8)

通過上面的介紹看出,可變形部件模型可以對目標進行分散的多部位描述.這樣就方便針對分割后的比較零散的區(qū)域進行部件檢測.但是,這樣的檢測比較依賴于分割的結果,如果分割結果不理想,檢測結果也會比較差.

3　基于交互式分割的目標檢測算法

這里主要介紹算法的整體流程.本文的算法主要分成兩個部分:訓練部分和檢測部分.目前,數(shù)據(jù)集變得越來越復雜,使用簡單的訓練方法往往就可以達到比較好的效果,而且訓練速度也比較快.綜合考慮,本文使用線性支持向量機(SVM)來進行二元分類.檢測部分使用的就是預分割算法和可變形部件模型.

3.1樣本訓練

傳統(tǒng)的HOG算法使用線性支持向量機作為分類判別器[14].它的學習過程主要分為兩個階段:第一階段是通過正樣本訓練(包含待檢測目標的圖片)和負樣本訓練(不包含待檢測目標的圖片)進行學習,得到初步的分類判別器.第二階段使用已經(jīng)得到的初步分類器對負的訓練圖像進行掃描,把掃描結果有誤的圖片作為誤測樣本,然后用正樣本、負樣本和誤測樣本組成集合,再次學習得到最終的分類判別器.我們可以使用得到的分類判別器對待檢測圖像進行分類.

3.2檢測過程

得到分類器之后,就進入到了檢測階段.本文檢測的方法是在可變形目標檢測模型的基礎上,對圖像預先進行交互式目標分割.

圖1提供了一組圖片的分割.通過這組圖片可以發(fā)現(xiàn),每幅圖片在分割后都會得到很多區(qū)域,由于后面的檢測主要針對這些區(qū)域,所以本文稱其為候選區(qū)域.對于一個圖像,可能有很多的候選區(qū)域,有些是與目標相關的,而有些是無關的.而且,這些區(qū)域可能分布在圖像的各個位置,本文優(yōu)先檢測分割面積較大的區(qū)域.

圖1　利用交互式分割算法對圖像進行的分割結果Fig.1　The result of interactive segmentation

通過對圖1的觀察統(tǒng)計可以發(fā)現(xiàn),分割出的候選區(qū)域中,屬于真實目標的區(qū)域相對比較緊湊.而且,這些區(qū)域在被檢測出來之后可以被范圍較大的根濾波器覆蓋.例如,對于圖1a,由于背景比較單一,所以分割效果比較好.而對于圖1b而言,由于背景很復雜,分割效果不好.

對于一張分割好的圖片,首先用訓練好的部件模型對每一個候選區(qū)域進行匹配,并且選出每個模板評分較高的一個區(qū)域.這樣,如果感興趣的目標在圖片中,就將會得到一個評分較高而且位置相對緊湊的較大區(qū)域.這時,可以使用根濾波器進行目標的整體檢測,并通過式(8)計算檢測的總體評分.如果該評分達到了確定的閾值,就可以認為檢測到了目標.

通過以上的描述可以發(fā)現(xiàn),本文的方法在檢測上比較依賴于分割的結果.在分割的效果比較好的情況下,算法準確度與窮舉法相比不會有影響,而檢測速度可以得到提高.

4　實驗結果與分析

為了驗證基于分割的目標檢測算法的性能,我們對算法進行了測試,并提供各個環(huán)節(jié)的結果.

測試環(huán)境選擇為PASCAL VOC 2007數(shù)據(jù)集.該數(shù)據(jù)集包括9 963張圖片,共分成20個目標類.程序的運行環(huán)境是Windows 10操作系統(tǒng)下的Matlab R2013a.

圖2給出了3組圖片的實驗結果.每組包含圖片處理的3個階段的結果,分別標記為(a)、(b)、(c).

圖2　目標檢測結果Fig.2　The result of object detection (a)—原始圖像; (b)—預處理后的結果; (c)—最終的檢測結果.

通過實驗可以看出,前2組的圖片背景顏色相對簡單和平滑,這對分割算法來說是比較有利的.而第3組圖片由于其背景比較復雜,分割結果較不理想,這樣可能導致檢測失敗.

表1給出了本文算法與文獻[8]中算法的平均準確度(Average precision,AP)對比.AP的計算方法是首先把識別率所有值分成10等份,這樣就可以得到11個邊界點.然后選取11個精確度,使得它們對應的識別率分別等于這些邊界點.最后,這11個精確度的平均值就是AP.對于AP的

表1　平均準確率對比

具體計算方法,可以參見官方VOCdevkit Matlab文件VOCevaldet.m.

通過表中的結果可以看出,本文算法對于背景比較簡單的分類,如飛機、轎車和船的效果比較好,而對于背景比較復雜的分類,如狗、花等的檢測效果比較差.這充分說明了本文算法對于分割結果的依賴是比較大的.如果背景比較利于分割,本文的檢測結果會高于文獻[8]中的算法.

為了分析算法的效率,表2給出了算法幾個主要步驟的運行時間.

表2　各個步驟的運行時間

通過表2可以看出,算法的預處理部分在總時間中占有較大的比例.這說明了分割的速度是算法的主要瓶頸.表3給出了本文算法與文獻[8]算法進行的時間對比.

表3　運行時間對比

從表3中可以看出,圖像在分割之前的檢測速度與文獻[8]中的算法在速度上沒有明顯提升.但是在已經(jīng)分割好的情況下,本文算法在速度上有明顯優(yōu)勢.造成這種現(xiàn)象的主要原因就是,分割算法消耗時間比較多,使本文算法喪失了速度優(yōu)勢.

雖然分割比較耗時,但是由于本文圖像分割與檢測是分開的,這樣如果完成了分割,結果就可以反復使用.如果需要調整檢測方法,就無需再次分割.比如,如果需要迭代訓練或多次調整測試時,本文方法由于只需要一次分割,速度優(yōu)勢就會逐漸體現(xiàn)出來.

5　結　　語

本文通過對圖像進行分割,獲得了一些目標概率比較大的區(qū)域.由于算法只針對這些大概率區(qū)域進行檢測,使檢測速度得到了比較大的提升.對于算法的特征描述部分,本文仍然使用HOG特征描述器結合可變形部件模型進行表述.通過樣本實驗可以發(fā)現(xiàn),文獻[8]算法的平均使用時間為4.79 s,而本文的平均算法在分割前為4.85 s,分割后為2.25 s.這可以證明,對于分割后的圖像,本文算法有明顯的速度提升.所以,本文算法為一些可復用的圖像檢測提供了一種比較快速的方法.并且如果分割速度能夠得到提高,本文算法可以期待更加明顯的特點.

[ 1 ] 孫銳,侯能干,陳軍. 基于特征融合和交叉核SVM的快速行人檢測方法[J]. 光電工程, 2014,41(2):53-62.

(SUN R,HOU N G,CHEN J. Fast pedestrian detection method based on features fusion and intersection kernel SVM[J]. Opto-Electronic Engineering, 2014,41(2):53-62.)

[ 2 ] DALAL N,TRIGGSB. Histograms of oriented gradients for human detection[C]∥IEEE Conference on Computer Vision and Pattern Recognition, 2005.

[ 3 ] FELZENSZWALB P,MCALLESTER D,RAMANAND. Object detection with discriminatively trained part-based models[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010,32(9):1627-1645.

[ 4 ] LEIBE B,SEEMANN E,SCHIELE B. Pedestrian detection in crowded scenes[C]∥IEEE Computer Society Conference on Computer Vision and Pattern Recognition, June 20-25, 2005:878-885,

[ 5 ] 魏巖,涂錚錚,鄭愛華,等. 結合RGB顏色特征和紋理特征的消影算法[J]. 計算機技術與發(fā)展, 2013,23(10):72-74,79.

(WEI Y,TU Z Z,ZHENG A H. Shadow elimination algorithm of combination of RGB color feature and texture feature[J]. Computer Technology and Development, 2013,23(10):72-74,79.)

[ 6 ] WUB,NEVATIA R. Cluster boosted tree classifier for multi-view,multi-pose object detection[C]∥IEEE International Conference on Computer Vision, 2007.

[ 7 ] LAMPERT C H,BLASCHKO M B,HOFMANN T. Beyond sliding windows:object localization by efficient subwindow search[C]∥Proceedings of the 23rd IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, USA, 2010:1-8.

[ 8 ] FELZENSZWALB P,MCALLESTER D,RAMANAN D. A discriminatively trained,multiscale,deformable part model[C]∥IEEE Conference on Computer Vision and Pattern Recognition, 2008.

[ 9 ] CHAN T F,VESEL A. Active contours without edges[J]. IEEE Transactions on Image Processing, 2001,10(2):266-277.

[10] OSHER S,PARAGIOS N. Geometric level set methods in imaging, vision,and graphics[M]. New York:Springer, 2003.

[11] 劉威,段成偉,遇冰,等. 基于后驗HOG特征的多姿態(tài)行人檢測[J]. 電子學報, 2015,43(2):217-224.

(LIU W,DUAN C W,YU B,et al. Multi-pose pedestrian detection based on posterior HOG feature[J]. Acta Electronica Sinica, 2015,43(2):217-224.)

[12] MEHNERT A,JACKWAY P. An improved seeded region growing algorithm[J]. Pattern Recognition Letters, 1997(18):1065-1071.

[13] 姚雪琴,李曉華,周激流. 基于邊緣對稱性和HOG的行人檢測算法方法[J]. 計算機工程, 2012,8(5):179-182.

(YAO X Q,LI X H,ZHOU J L. Pedestrian detection method baesd on edge symmetry and HOG[J]. Computer Engineering, 2012,8(5):179-182.)

[14] VIJAYANARASIMHAN S,GRAUMAN K. Efficient region search for object detection[C]∥CVPR’11 Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Washington:IEEE Computer Society, 2011:1401-1408.

【責任編輯: 祝穎】

Deformable Object Detection Based on Interactive Segmentation Algorithm

PuBaoming1,HuoHong1,YangDongsheng1,LiXiangze2

(1. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110004, China; 2. School of Information Science and Engineering, Northeastern University, Shenyang 110819, China)

As low efficiency in algorithm of detection with high precision, a kind of interactive object segmentation based level-set is proposed to improve efficiency. The proposed algorithm firstly applies interactive object segmentation to preprocessing the image, and then detects every area with part-based model. Traditional histogram of oriented gradients is used to describe a component model. It’s particularly important for high resolution image to segment image in advance for reducing detecting range of the detection window. The results show that, the proposed method has obvious improvement in efficiency comparing with the exhaustive search by sliding window.

object detection; image segmentation; interactive segmentation; histogram of gradients vector; deformable part-based model

2016-01-30

國家科技重大專項資助項目(2013ZX04007031; 2012ZX01029001-002).

蒲寶明(1966-),男,遼寧沈陽人,中國科學院沈陽計算技術研究所研究員,博士生導師,博士.

2095-5456(2016)04-0296-06

TP 391.4

A