基于隨機(jī)游走和混合高斯模型的運(yùn)動(dòng)目標(biāo)檢測(cè)

李 強(qiáng)，陳光化，余 淵

(1.上海大學(xué) 機(jī)電工程與自動(dòng)化學(xué)院，上海 200070； 2.上海電器科學(xué)研究所(集團(tuán))有限公司，上海 200333)

基于隨機(jī)游走和混合高斯模型的運(yùn)動(dòng)目標(biāo)檢測(cè)

李 強(qiáng)1，陳光化1，余 淵2

(1.上海大學(xué) 機(jī)電工程與自動(dòng)化學(xué)院，上海 200070； 2.上海電器科學(xué)研究所(集團(tuán))有限公司，上海 200333)

針對(duì)傳統(tǒng)的混合高斯背景建模算法未考慮同一幀內(nèi)相鄰像素之間的聯(lián)系而導(dǎo)致無法準(zhǔn)確地捕捉到運(yùn)動(dòng)物體輪廓的問題，提出了一種將隨機(jī)游走和混合高斯模型相結(jié)合的前景目標(biāo)檢測(cè)算法。該算法利用混合高斯模型對(duì)視頻源圖像進(jìn)行背景建模，從而獲得初始運(yùn)動(dòng)目標(biāo)，應(yīng)用隨機(jī)游走算法的分割效果及處理時(shí)間來確定種子點(diǎn)數(shù)量，結(jié)合初始運(yùn)動(dòng)目標(biāo)對(duì)種子點(diǎn)進(jìn)行標(biāo)記，采用隨機(jī)游走算法對(duì)視頻源圖像進(jìn)行分割，將所得到的分割目標(biāo)再與初始運(yùn)動(dòng)目標(biāo)進(jìn)行“與”運(yùn)算，通過形態(tài)學(xué)處理得到作為結(jié)果的運(yùn)動(dòng)目標(biāo)。為驗(yàn)證所提出算法的有效性，基于Matlab對(duì)所選取的4段視頻進(jìn)行了仿真檢測(cè)。驗(yàn)證實(shí)驗(yàn)結(jié)果表明，所提出的前景目標(biāo)檢測(cè)算法較好地解決了混合高斯算法所產(chǎn)生的邊緣模糊問題，同時(shí)也明顯降低了前景噪聲。

混合高斯模型；隨機(jī)游走；運(yùn)動(dòng)目標(biāo)檢測(cè)；種子點(diǎn)

0 引 言

運(yùn)動(dòng)目標(biāo)檢測(cè)是分析視頻過程中一個(gè)基礎(chǔ)而又關(guān)鍵的任務(wù)[1]。而背景建模作為目標(biāo)跟蹤檢測(cè)的基礎(chǔ)，其結(jié)果的好壞將直接影響到后期處理的效果。迄今，人們己經(jīng)設(shè)計(jì)了很多背景建模的算法。常用的有：幀差法、碼本法、混合高斯模型法等[2-4]。其中最經(jīng)典的是混合高斯模型算法。

近年來，有文獻(xiàn)提出了改進(jìn)的混合高斯模型算法。例如，Zoran Zivkovic[5]提出將對(duì)每個(gè)像素的高斯個(gè)數(shù)進(jìn)行在線選擇，從而更好地適應(yīng)不同的場(chǎng)景，同時(shí)縮短了建模時(shí)間；Dar-Shyang Lee[6]則提出使用自適應(yīng)學(xué)習(xí)算法來改善收斂速度和檢測(cè)精度。然而，這些改進(jìn)方法并未考慮相鄰像素點(diǎn)之間的聯(lián)系，這會(huì)導(dǎo)致運(yùn)動(dòng)目標(biāo)的檢測(cè)產(chǎn)生邊緣模糊的問題。也有部分文獻(xiàn)對(duì)這方面提出了相應(yīng)改進(jìn)。印勇等[7]通過重新定義Markov隨機(jī)場(chǎng)(MRF)的勢(shì)能函數(shù)來融入空間鄰域的相關(guān)性信息，從而對(duì)混合高斯算法進(jìn)行改進(jìn)；李菊等[8]采用Markov隨機(jī)場(chǎng)(MRF)構(gòu)造的間斷點(diǎn)分布模型來檢測(cè)運(yùn)動(dòng)目標(biāo)的邊緣。但這些改進(jìn)算法實(shí)現(xiàn)起來較為繁瑣。因此，結(jié)合了實(shí)現(xiàn)相對(duì)簡(jiǎn)單的隨機(jī)游走算法，來補(bǔ)充相鄰像素點(diǎn)之間的聯(lián)系。

隨機(jī)游走圖像分割算法是根據(jù)相鄰像素間的關(guān)聯(lián)程度對(duì)圖像進(jìn)行分割處理，對(duì)微弱邊緣具有良好的響應(yīng)。為此，提出了將隨機(jī)游走算法和基于混合高斯模型相結(jié)合的運(yùn)動(dòng)目標(biāo)檢測(cè)算法，并進(jìn)行了實(shí)驗(yàn)。

1 相關(guān)算法研究

1.1 混合高斯背景建模算法

Grimson和Stauffer提出，使用K(一般為3～5)個(gè)相互獨(dú)立的高斯分布函數(shù)來描述圖像幀中的每一個(gè)像素點(diǎn)[3]。

(1)

其中，xN表示N時(shí)刻的某一像素值；wk表示第k個(gè)高斯分布的權(quán)重值；η(x;θk)表示第k個(gè)高斯分布函數(shù)：

(2)

其中，μk表示均值；Σk=σ2I表示第k個(gè)高斯分布的方差。

將K個(gè)高斯分布按照wk/σk的優(yōu)先級(jí)進(jìn)行降序排列，排序后從中挑選出比值最大的前B個(gè)高斯進(jìn)行建模。wk/σk值越大，表明當(dāng)前像素有較小的方差和較高的出現(xiàn)概率，即該像素在前后幀的時(shí)間內(nèi)變化不大，體現(xiàn)了背景像素的特性，所以該像素呈現(xiàn)為背景像素的概率大于呈現(xiàn)為前景像素的概率。

(3)

其中，T是給定的閾值。

P.Kaewtrakulpong和R. Bowden提出可將前L幀圖像當(dāng)成訓(xùn)練樣本，更新公式如下[4]：

(4)

(5)

(6)

L幀樣本更新完后，按照如下方式更新：

(7)

(8)

(9)

1.2 隨機(jī)游走圖像分割算法

隨機(jī)游走是一種基于圖論的半監(jiān)督圖像分割方法，具有分割速度快，無需迭代，對(duì)噪聲具有魯棒性，對(duì)弱邊緣具有較好的響應(yīng)等優(yōu)點(diǎn)，且易于擴(kuò)展到多維空間[9]。該算法主要采用灰度差計(jì)算相鄰節(jié)點(diǎn)間的相似度[10]。其分割思想為：將圖像映射為一幅無向圖，以圖像的像素為無向圖的頂點(diǎn)，相鄰像素之間的四鄰域或八鄰域關(guān)系為邊，并根據(jù)相鄰像素之間特征的相似性定義各邊的權(quán)值。然后由用戶指定前景和背景標(biāo)記，即前景物體和背景物體的種子像素，以邊上的權(quán)重為轉(zhuǎn)移概率，未標(biāo)記像素節(jié)點(diǎn)為初始點(diǎn)，計(jì)算每個(gè)未標(biāo)記節(jié)點(diǎn)首次到達(dá)已標(biāo)記節(jié)點(diǎn)(即種子節(jié)點(diǎn))的概率，根據(jù)概率大小，劃分未標(biāo)記節(jié)點(diǎn)，得到最終分割結(jié)果[11-13]。

無向圖定義為G=(V,E,W)，其中V表示節(jié)點(diǎn)集合，E表示邊集合，W表示權(quán)值集合。權(quán)值由高斯權(quán)函數(shù)來描述節(jié)點(diǎn)間的相似性，即

wi,j=exp(-β1(Ii-Ij)2)

(10)

其中，Ii表示節(jié)點(diǎn)vi的灰度值；Ij表示與節(jié)點(diǎn)vi相鄰的節(jié)點(diǎn)vj的灰度值；β1>0表示自由度參數(shù)。

隨機(jī)游走求解概率問題與Dirichlet積分求解有相同的解法。通過對(duì)圖像中目標(biāo)區(qū)域與背景區(qū)域進(jìn)行標(biāo)記，將圖像中的節(jié)點(diǎn)分成兩類，標(biāo)記點(diǎn)集合VM和未標(biāo)記點(diǎn)集合VU，VM∪VU=V且VM∩VU=?。

定義拉普拉斯矩陣的元素為：

(11)

其中，dRi=∑wRi,Rj稱為節(jié)點(diǎn)vRi的度，未標(biāo)記節(jié)點(diǎn)vRi∈VU，標(biāo)記節(jié)點(diǎn)vRj∈VM。

離散Dirichlet積分公式定義為：

(12)

根據(jù)節(jié)點(diǎn)所屬不同集合，將拉普拉斯矩陣分解成對(duì)角分塊矩陣形式。

(13)

其中，xM和xU分別表示對(duì)應(yīng)種子點(diǎn)和非種子點(diǎn)的隨機(jī)游走概率值。

對(duì)D[xU]針對(duì)xU求微分，可以得到該方法極小值的解。

LUxU=-BTxM

(14)

(15)

應(yīng)用Dirichlet邊界條件，計(jì)算所有未標(biāo)記點(diǎn)到標(biāo)記為s的種子點(diǎn)概率值。計(jì)算：

LUX=-BTM

(16)

將每個(gè)未標(biāo)記點(diǎn)歸并到概率最大值所屬的類中，實(shí)現(xiàn)圖像分割。

2 基于隨機(jī)游走和混合高斯模型的運(yùn)動(dòng)目標(biāo)檢測(cè)算法

傳統(tǒng)的混合高斯背景建模是對(duì)圖像幀中每一個(gè)像素點(diǎn)進(jìn)行建模，前后幀的像素點(diǎn)相互關(guān)聯(lián)，但并未考慮相鄰像素點(diǎn)之間的聯(lián)系，這會(huì)導(dǎo)致運(yùn)動(dòng)目標(biāo)的檢測(cè)產(chǎn)生邊緣模糊的問題，從而無法準(zhǔn)確獲得運(yùn)動(dòng)目標(biāo)的輪廓。因此，提出將隨機(jī)游走算法引入混合高斯模型算法，從而考慮了相鄰像素點(diǎn)之間的關(guān)聯(lián)性。

2.1 算法介紹

混合高斯背景建模算法保證了相鄰幀之間像素的關(guān)聯(lián)性，隨機(jī)游走分割算法則計(jì)算了同一幀里相鄰像素之間的相似性，將這二者結(jié)合能更準(zhǔn)確地描述視頻序列中的前景和背景。實(shí)現(xiàn)過程如下：

(1)對(duì)當(dāng)前幀圖像采用混合高斯模型進(jìn)行背景建模，提取初步運(yùn)動(dòng)目標(biāo)。高斯模型數(shù)目N一般設(shè)為3～5，閾值T一般設(shè)為0.7。

(2)根據(jù)式(4)～(9)對(duì)背景模型進(jìn)行更新。

(3)隨機(jī)選取一定數(shù)量的圖像像素作為種子點(diǎn)。種子點(diǎn)的數(shù)量直接影響到隨機(jī)游走分割算法的分割效果，關(guān)于種子點(diǎn)的選取問題，將在下一節(jié)討論。

(4)根據(jù)混合高斯背景建模得到的初始運(yùn)動(dòng)目標(biāo)給這些種子點(diǎn)定義相應(yīng)的標(biāo)簽，背景種子點(diǎn)標(biāo)簽為0，前景種子點(diǎn)標(biāo)簽為1，然后采用隨機(jī)游走分割算法對(duì)原視頻幀圖像進(jìn)行處理，得到前景目標(biāo)。

(5)將混合高斯背景建模所得到的初始運(yùn)動(dòng)目標(biāo)(二值圖像)與通過隨機(jī)游走分割得到的前景目標(biāo)(二值圖像)進(jìn)行“與”運(yùn)算。

(6)進(jìn)行形態(tài)學(xué)處理。

流程圖如圖1所示。

圖1 算法流程圖

2.2 隨機(jī)游走種子點(diǎn)的選取

由于隨機(jī)游走是一種交互式的圖像分割算法，因此要預(yù)先指定一定數(shù)量的種子點(diǎn)。種子點(diǎn)的數(shù)量會(huì)直接影響分割效果。

種子點(diǎn)太少，導(dǎo)致圖像分割不準(zhǔn)確；種子點(diǎn)過多，使分割結(jié)果過分依賴于混合高斯背景建模所得到的初始運(yùn)動(dòng)目標(biāo)(由于這些種子點(diǎn)會(huì)根據(jù)初始運(yùn)動(dòng)目標(biāo)來定義標(biāo)簽)，影響優(yōu)化效果。所以，分別隨機(jī)選取0.1%～50%的圖像像素作為種子點(diǎn)，對(duì)分割結(jié)果進(jìn)行對(duì)比，如圖2所示。

圖2 隨機(jī)選取各百分比的圖像像素作為種子點(diǎn)得到的圖像分割效果

從實(shí)驗(yàn)結(jié)果可以看出，隨機(jī)選取5%以下的圖像像素作種子點(diǎn)時(shí)，圖像分割效果并不好；隨機(jī)選取5%～20%的像素時(shí)，分割出的主體基本完整，但在細(xì)節(jié)上表現(xiàn)較差(如圖2(f)～(h)中間兩個(gè)小孩的輪廓不準(zhǔn)確)；隨機(jī)選取20%以上的像素時(shí)，分割出的主體更為準(zhǔn)確，而且差異也越來越小。總結(jié)起來，隨著種子點(diǎn)數(shù)量的增加，隨機(jī)游走算法的分割效果越好，分割出的主體更為準(zhǔn)確和完整。

根據(jù)1.2節(jié)的理論可知，隨機(jī)游走算法計(jì)算的是所有未標(biāo)記點(diǎn)到達(dá)已標(biāo)記的種子點(diǎn)概率值，當(dāng)種子點(diǎn)數(shù)量越多時(shí)，算法的處理速度越快，如圖3所示。

從圖3可以看出，當(dāng)種子點(diǎn)數(shù)量在0%～20%時(shí)，算法處理時(shí)間縮短明顯；20%～40%時(shí)，算法平均處理時(shí)間減少緩慢；40%之后變化更小。結(jié)合圖2所示的分割效果，選取大于20%的像素作為種子點(diǎn)較為理想。

圖3 種子點(diǎn)數(shù)量與隨機(jī)游走算法處理時(shí)間的關(guān)系

然而當(dāng)種子點(diǎn)數(shù)量過多時(shí)，隨機(jī)游走算法的分割效果會(huì)過分依賴于混合高斯背景建模所得到的初始運(yùn)動(dòng)目標(biāo)，這樣會(huì)使改進(jìn)算法失去意義。綜上所述，選取了20%的像素點(diǎn)作為種子點(diǎn)，然后對(duì)圖像進(jìn)行分割。

2.3 形態(tài)學(xué)處理

經(jīng)過隨機(jī)游走分割算法處理后，噪聲已經(jīng)得到進(jìn)一步的削弱，然而仍會(huì)有一些“空洞”或是孤立的小區(qū)域，這里采用形態(tài)學(xué)方法來去除二值圖像中孤立的小區(qū)域，同時(shí)將小間隙填充。基于形態(tài)學(xué)后處理方法，進(jìn)行閉運(yùn)算，即先進(jìn)行“膨脹”操作，使目標(biāo)區(qū)域的連通塊盡量少，接著進(jìn)行“腐蝕”操作消除毛刺，使邊界向內(nèi)部收縮。對(duì)二值圖像進(jìn)行形態(tài)學(xué)處理后，實(shí)現(xiàn)了消除噪聲、平滑圖像的目的，檢測(cè)出完整的運(yùn)動(dòng)目標(biāo)。

3 仿真結(jié)果及分析

提出算法在Matlab R2015b下編程實(shí)現(xiàn)，選用的計(jì)算機(jī)配置為Intel Core i3 370M雙核處理器，內(nèi)存4 GB，Windows 10操作系統(tǒng)。為了驗(yàn)證提出算法的有效性，選取了4段視頻進(jìn)行檢測(cè)，如圖4所示。

通過觀察和比較可以發(fā)現(xiàn)，單純使用混合高斯模型所得到的前景目標(biāo)會(huì)出現(xiàn)輪廓虛化的現(xiàn)象，如圖4(b)列第一幅圖中兩邊人的腿輪廓出現(xiàn)了一些模糊；(b)列的其他運(yùn)動(dòng)目標(biāo)也均出現(xiàn)了不同程度的輪廓模糊現(xiàn)象。此外，(b)列第二幅、第三幅圖像還出現(xiàn)了明顯的噪聲。而采用提出的方法，不僅能獲得較完整的目標(biāo)輪廓，邊緣毛刺被消除，而且噪聲也得到了較大改善，如(c)列所示。同時(shí)，可以發(fā)現(xiàn)(c)列圖像相比(b)列圖像，前景目標(biāo)內(nèi)部的微小“空洞”被大量填充，使整個(gè)目標(biāo)看起來更完整。

通過實(shí)驗(yàn)可以看出，提出的改進(jìn)算法較好地改善了前景目標(biāo)輪廓模糊的現(xiàn)象，這得益于隨機(jī)游走算法對(duì)微邊緣的良好響應(yīng)。而隨機(jī)選取一定數(shù)量的種子點(diǎn)，也能夠幫助剔除部分噪聲點(diǎn)，同時(shí)使隨機(jī)游走分割效果更好。最后的形態(tài)學(xué)處理則幫助消除了大量的微小“空洞”和邊緣毛刺。

4 結(jié)束語

針對(duì)傳統(tǒng)的混合高斯背景建模算法無法準(zhǔn)確地捕捉到運(yùn)動(dòng)物體輪廓的問題，提出了將隨機(jī)游走圖像分割算法與混合高斯模型算法相結(jié)合的新算法。該算法根據(jù)混合高斯模型算法所得到的初始運(yùn)動(dòng)目標(biāo)，隨機(jī)選取一定數(shù)量的種子點(diǎn)并標(biāo)記，并采用隨機(jī)游走圖像分割算法對(duì)視頻圖像進(jìn)行分割，并將兩種算法得到的前景目標(biāo)進(jìn)行“與”運(yùn)算，經(jīng)形態(tài)學(xué)處理得到完整的運(yùn)動(dòng)目標(biāo)。由于種子點(diǎn)的數(shù)量會(huì)直接影響隨機(jī)游走算法的分割效果，因而通過對(duì)比不同數(shù)量的種子點(diǎn)對(duì)圖像的分割效果以及算法的處理時(shí)間，發(fā)現(xiàn)選取20%的像素作為種子點(diǎn)較為合理。該方法在保證前后幀像素的關(guān)聯(lián)性的同時(shí)，還考慮了同一幀內(nèi)相鄰像素的聯(lián)系，使得檢測(cè)出的運(yùn)動(dòng)目標(biāo)輪廓更為完整和準(zhǔn)確。實(shí)驗(yàn)結(jié)果表明，提出的目標(biāo)前景檢測(cè)算法較原有的混合高斯模型算法具有更好的檢測(cè)效果，同時(shí)還具有一定的降噪效果。

[1] 焦 波,李國(guó)輝,涂 丹,等.一種用于運(yùn)動(dòng)目標(biāo)檢測(cè)的快速收斂混合高斯模型[J].中國(guó)圖象圖形學(xué)報(bào),2008,13(11):2139-2143.

[2] Guo Jingming,Liu Yunfu,Hsia Chih-Hsien.Hierarchical me-thod for foreground detection using codebook model[J].IEEE Transactions on Circuits and Systems for Video Technology,2011,21(6):804-815.

[3] Stauffer C,Grimson W E L.Adaptive background mixture mo-dels for real-time tracking[C]//IEEE conference on computer vision and pattern recognition.[s.l.]:IEEE,1999.

[4] Kaewtrakulpong P, Bowden R. An improved adaptive background mixture model for realtime tracking with shadow detection[M]//Video-based surveillance systems.US:Springer,2002:135-144.

[5] Zivkovic Z. Improved adaptive Gaussian mixture model for background subtraction[C]//International conference on pattern recognition.[s.l.]:IEEE Computer Society,2004:28-31.

[6] Lee Dar-Shyang.Effective Gaussian mixture learning for video background subtraction[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2005,27(5):827-832.

[7] 印 勇,王亞飛.基于空間鄰域相關(guān)性的運(yùn)動(dòng)目標(biāo)檢測(cè)方法[J].光電工程,2009,36(2):1-5.

[8] 李 菊,李克清,蘇勇剛.Markov隨機(jī)游走和高斯混合模型相結(jié)合的運(yùn)動(dòng)目標(biāo)檢測(cè)算法[J].電子測(cè)量與儀器學(xué)報(bào),2014,28(5):533-537.

[9] 徐曉華.圖上的隨機(jī)游走學(xué)習(xí)[D].南京:南京航空航天大學(xué),2008.

[10] 依玉峰，高立群，郭 麗． 基于Mean Shift隨機(jī)游走圖像分割算法[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2011,23(11):1875-1881．

[11] Grady L． Random walks for image segmentation[J]．IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(11)：1768-1783．

[12] Grady L． Minimal surfaces extend shortest path segmentation methods to 3D[J]．IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(2)：321-334．

[13] Grady L,Sinop A K.Fast approximate random walker segmentation using eigenvector precomputation[C]//IEEE conference on computer vision and pattern recognition.[s.l.]:IEEE,2008:1-8.

Moving Target Detection Based on Random Walk and Gaussian Mixture Model

LI Qiang1，CHEN Guang-hua1，YU Yuan2

(1.School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200070,China; 2.Shanghai Electrical Apparatus Research Institute (Group) Co.,Ltd.,Shanghai 200333,China)

Since the conventional Gaussian mixture background modeling algorithm does not consider the correlation between adjacent pixels in the same frame,which cannot accurately capture the contour of moving objects,a foreground target detection method combined with random walk and Gaussian mixture model has been proposed.The background of the video source image has been modeled with the mixed Gauss model firstly,and the initial moving object has been obtained.Then,the number of seed points is determined by analyzing the segmentation result and the processing time of the random walk algorithm.The seed points have been labeled with the initial moving object,and the video source image is segmented by random walk algorithm.The obtained segmentation target and the initial moving object have been computed with logic AND operation.The morphological processing has been carried out to get the final moving target. In order to verify the effectiveness of the proposed algorithm, the four selected sequences of videos have been tested by Matlab.The test results show that the proposed method has solved the edge blurring problem of Gaussian mixture algorithm,and reduced the foreground noise.

mixed Gauss model;random walk;moving target detection;seed points

2016-08-10

2016-11-17 網(wǎng)絡(luò)出版時(shí)間：2017-04-28

上海市科技成果轉(zhuǎn)化和產(chǎn)業(yè)化項(xiàng)目基金(14DZ1100600)

李 強(qiáng)(1991-)，男，碩士研究生，研究方向?yàn)閿?shù)字圖像處理；陳光化，副教授，研究方向?yàn)橐曨l編解碼關(guān)鍵技術(shù)及其VLSI實(shí)現(xiàn)、嵌入式系統(tǒng)設(shè)計(jì)等。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1704.094.html

TP301.6

A

1673-629X(2017)06-0011-06

10.3969/j.issn.1673-629X.2017.06.003