基于隨機游走和混合高斯模型的運動目標檢測

李 強，陳光化，余 淵

(1.上海大學 機電工程與自動化學院，上海 200070； 2.上海電器科學研究所(集團)有限公司，上海 200333)

基于隨機游走和混合高斯模型的運動目標檢測

李 強1，陳光化1，余 淵2

(1.上海大學 機電工程與自動化學院，上海 200070； 2.上海電器科學研究所(集團)有限公司，上海 200333)

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

混合高斯模型；隨機游走；運動目標檢測；種子點

0 引 言

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

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

隨機游走圖像分割算法是根據(jù)相鄰像素間的關聯(lián)程度對圖像進行分割處理，對微弱邊緣具有良好的響應。為此，提出了將隨機游走算法和基于混合高斯模型相結合的運動目標檢測算法，并進行了實驗。

1 相關算法研究

1.1 混合高斯背景建模算法

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

(1)

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

(2)

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

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

(3)

其中，T是給定的閾值。

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

(4)

(5)

(6)

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

(7)

(8)

(9)

1.2 隨機游走圖像分割算法

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

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

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

(10)

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

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

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

(11)

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

離散Dirichlet積分公式定義為：

(12)

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

(13)

其中，xM和xU分別表示對應種子點和非種子點的隨機游走概率值。

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

LUxU=-BTxM

(14)

(15)

應用Dirichlet邊界條件，計算所有未標記點到標記為s的種子點概率值。計算：

LUX=-BTM

(16)

將每個未標記點歸并到概率最大值所屬的類中，實現(xiàn)圖像分割。

2 基于隨機游走和混合高斯模型的運動目標檢測算法

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

2.1 算法介紹

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

(1)對當前幀圖像采用混合高斯模型進行背景建模，提取初步運動目標。高斯模型數(shù)目N一般設為3～5，閾值T一般設為0.7。

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

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

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

(5)將混合高斯背景建模所得到的初始運動目標(二值圖像)與通過隨機游走分割得到的前景目標(二值圖像)進行“與”運算。

(6)進行形態(tài)學處理。

流程圖如圖1所示。

圖1 算法流程圖

2.2 隨機游走種子點的選取

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

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

圖2 隨機選取各百分比的圖像像素作為種子點得到的圖像分割效果

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

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

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

圖3 種子點數(shù)量與隨機游走算法處理時間的關系

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

2.3 形態(tài)學處理

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

3 仿真結果及分析

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

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

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

4 結束語

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

[1] 焦 波,李國輝,涂 丹,等.一種用于運動目標檢測的快速收斂混合高斯模型[J].中國圖象圖形學報,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] 印 勇,王亞飛.基于空間鄰域相關性的運動目標檢測方法[J].光電工程,2009,36(2):1-5.

[8] 李 菊,李克清,蘇勇剛.Markov隨機游走和高斯混合模型相結合的運動目標檢測算法[J].電子測量與儀器學報,2014,28(5):533-537.

[9] 徐曉華.圖上的隨機游走學習[D].南京:南京航空航天大學,2008.

[10] 依玉峰，高立群，郭 麗． 基于Mean Shift隨機游走圖像分割算法[J]．計算機輔助設計與圖形學學報，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)絡出版時間：2017-04-28

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

李 強(1991-)，男，碩士研究生，研究方向為數(shù)字圖像處理；陳光化，副教授，研究方向為視頻編解碼關鍵技術及其VLSI實現(xiàn)、嵌入式系統(tǒng)設計等。

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