基于改進(jìn)K均值的運(yùn)動目標(biāo)檢測算法研究

柯尊海 劉 勇 徐義春 雷幫軍

（三峽大學(xué) 智能視覺與圖像信息研究所，湖北 宜昌 443002）

前景提取是計算機(jī)視覺應(yīng)用的重要環(huán)節(jié)，是目標(biāo)跟蹤、目標(biāo)識別、場景分析與理解等高級處理的基礎(chǔ)，在行人檢測與跟蹤、智能交通、社會安防等領(lǐng)域得到了高度的重視.如何針對當(dāng)前的場景建立一個盡可能完善的背景模型，并進(jìn)行前景信息的提取是計算機(jī)視覺領(lǐng)域的研究熱點和難點.

近年來，國內(nèi)外大量學(xué)者對其進(jìn)行了深入的研究，并取得了大量的成果.目前，背景建模算法已有十幾種，如Kim等提出的Codebook背景建模算法，許雪梅等在Kim的基礎(chǔ)上提出了局部更新的分層碼本目標(biāo)檢測算法［1－2］，P.KadewTraKuPong等人提出的高斯混合模型背景建模算法，黃鑫娟等在其基礎(chǔ)上提出了自適應(yīng)混合高斯背景模型的運(yùn)動目標(biāo)檢測方法［3－5］等，背景建模算法的綜述性論文也頻頻見刊［6－8］.除此以外，新的背景建模算法也不斷地被提出，如Hanzi Wang和David Suter提出的SACON算法［9］、Olivier Barnich和 Marc Van Droogenbroeck提出的 VIBE算法［10］以及Lucia Maddalena和 Al－fredo Petrosino提出的SOBS自組織背景建模方法［11］等.K均值聚類算法是一種基于樣本間某種距離或相似性來定義的一種間接聚類方法，由于實際場景是動態(tài)變化（如搖曳的樹葉等），能夠很好地用K均值聚類來分析，因此K均值聚類算法在目標(biāo)檢測中的研究引起了一些學(xué)者的注意.楊會鋒，曹潔等人提出了一種基于改進(jìn)K－均值聚類的背景建模方法，通過比較任意樣本與像素位置處子類中心的距離，對各個像素的觀察值進(jìn)行聚類.經(jīng)過一段時間的學(xué)習(xí)，樣本數(shù)最多的就構(gòu)成了背景模型，但是對于背景模型的更新沒有進(jìn)一步的深入研究［12］.查成東等人也提出了一種基于改進(jìn)K－均值聚類算法的背景提取方法，并且對每個像素用3個動態(tài)的元組進(jìn)行建模，實現(xiàn)原始背景的提取.但是該算法固定了K＝3，而且只是針對單通道灰度視頻序列進(jìn)行建模，不能很好地對實際場景進(jìn)行建模［13］.張運(yùn)楚等人提出了一種基于C－均值聚類的視覺監(jiān)控背景圖像構(gòu)建算法，選擇樣本點數(shù)量最大的類別的均值作為背景模型.該算法不能對動態(tài)場景進(jìn)行處理，并且采用了一種在線更新的形式，內(nèi)存消耗比較大［14］.Charoenpong T等人提出了一種采用混合高斯模型和K均值的自適應(yīng)背景建模方法，將捕獲的幀轉(zhuǎn)換為單通道的灰度圖像，并進(jìn)行累加，通過K均值方法來確定高斯分布的聚類數(shù)目，然后將平滑聚類結(jié)果中最大的類作為背景模型.該算法只能處理單運(yùn)動目標(biāo)的場景，并且不能適應(yīng)場景的動態(tài)變化［15］.

綜上所述，盡管目前前景提取的算法有很多，并且對于某些特定的場合能取得比較好的結(jié)果，但是在一些實際應(yīng)用中，這些算法卻不盡人意，因此有必要進(jìn)一步對其進(jìn)行研究.本文在文獻(xiàn)［14］的基礎(chǔ)上，采用其K均值背景圖像構(gòu)建算法的思路，又進(jìn)行了一些補(bǔ)充.主要補(bǔ)充的內(nèi)容有：

4）本文的運(yùn)動目標(biāo)提取算法，可以根據(jù)陰影的特點，實現(xiàn)陰影、背景、前景的分離，使算法具有很大的通用性.

1 算 法

算法在HSV顏色空間，通過K均值聚類算法對視頻流的前N幀每個像素樣本進(jìn)行聚類學(xué)習(xí)，K均值聚類的結(jié)果用來表示對應(yīng)像素的背景模型.然后輸入的視頻流與背景模型進(jìn)行比較，進(jìn)行背景、可能前景和陰影的分離處理，引入TOM方法來消除鬼影現(xiàn)象，算法采用了一種選擇性的背景更新策略來進(jìn)行背景更新.

1.1 K均值聚類算法介紹

K均值聚類算法是一種基于樣本間某種距離或相似性度量來定義的一種間接聚類方法，其基本思想是通過迭代尋找K個聚類的一種劃分方案，使用這K個聚類的均值來代表相應(yīng)各類樣本時所得的總體誤差最小［16］.

令y是待分類的數(shù)據(jù)樣本集，Ni是第i類聚類Γi中樣本的數(shù)目，mi是這些樣本的均值，即

把Γi中的各樣本y與均值mi間的誤差平方和對所有類相加作為判別準(zhǔn)則：

通過迭代，不斷地調(diào)整樣本的歸屬類使Je極小，Je極小的聚類Γ1，Γ2，…，Γk即待分類樣本集y的最優(yōu)劃分.

K均值算法的步驟為：

1）初始劃分k個聚類，Γi，i＝1，2，…，k，根據(jù)式（1）和式（2）計算mi（i＝1，…，k）和Je；

2）任取一個樣本y，設(shè)y?Γi；

3）若Ni＝1，則轉(zhuǎn)2），否則繼續(xù)；

4）計算ρj

5）考察ρj中的最小者ρk，若ρk＜ρj，?j，則把y從Γi移到Γk中；

6）重新計算mi（i＝1，…，k）和Je；

7）若連續(xù)N次迭代Je不改變（變化很小），則停止；否則轉(zhuǎn)2）.

1.2 改進(jìn)K均值背景建模

設(shè)｛f0，…，ft，…｝表示視頻序列的幀，Xt＝（，）表示t時刻圖像幀ft中的像素（x，y）的 HSV彩色向量，Kt表示在0～t之間像素（x，y）出現(xiàn)的灰度的類別數(shù)量，表示t時刻像素（x，y）灰度值的第k個類別中樣本數(shù)量，表示像素（x，y）在時刻t第k個聚類的灰度均值.

文中采用了K均值聚類的思想，對文獻(xiàn)［14］的建模算法做了些修改，修改后的K均值背景建模算法描述如下：

1）初始化t＝0，令C0＝1＝1＝X0；

2）在時刻t，將圖像幀ft中的每一個像素Xt＝（）根據(jù)灰度值大小對其進(jìn)行分類.對于第k（k≤Kt－1）類別，分類準(zhǔn)則如下：

那么對第k個聚類，對相關(guān)變量做如下更新：

如果不滿足式（5），即該像素不屬于任何已有的類別，那么則將其歸為一個新的類別：

3）對于每一個像素進(jìn)行像素值與聚類處理后，選擇聚類類別的均值向量為該像素的背景模型，即

從式（9）可以看出，修改后的K均值聚類算法建立的背景模型是一種混合模型，對于比較穩(wěn)定的場景中的像素位置，在聚類的時候?qū)⑿纬梢粋€穩(wěn)定的類別，該類別的均值就為該像素的背景模型；而對于具有動態(tài)變化的場景，則可能形成多個聚類類別，將聚類形成的多類別的多個均值作為該像素的背景模型，這樣建立起來的背景模型相對于文獻(xiàn)［14］具有更強(qiáng)的環(huán)境適應(yīng)性，可以較好地適應(yīng)動態(tài)場景的變化.

1.3 像素分類

對于每一個新來的像素，其可能為背景、前景、陰影或者其他成分.根據(jù)HSV顏色空間的特點，本文引入色度差和亮度差的表達(dá)形式：

這里τ≥ξ，這樣就能在背景建模階段，將背景像素盡可能地聚類在合理的類別中，ξ越小，聚類的類別數(shù)愈少，反之越多.

按照高光和陰影的顏色表現(xiàn)原理，如果當(dāng)前像素與背景像素的色度變化比較多，則認(rèn)為有目標(biāo)進(jìn)入，判為前景像素；當(dāng)色度變化不大，而亮度比背景要低得多時，則判為陰影像素；當(dāng)像素變化不大，而亮度比背景要大很多時，則判為高光像素.根據(jù)以上描述，則有如下像素所屬類別判斷準(zhǔn)則：

其中，M（i）表示掩膜圖像，F(xiàn)、B、S、H 分別表示前景、背景、陰影和高光，τt，τv1，τv2是表示當(dāng)前像素與對應(yīng)背景模型中的色度和亮度相似度.如果只關(guān)心前景，則上式可以簡化為

1.4 背景更新

本文采用一種全新選擇性機(jī)制來進(jìn)行背景模型的更新，對于判為背景像素的點，按式（13）進(jìn)行背景更新：

1.5 鬼影消除

鬼影也稱為虛背景，它的產(chǎn)生有兩種情況，一種情況是背景物體的移出，即背景中停止的物體，運(yùn)動移出了背景區(qū)域，導(dǎo)致在檢測時出現(xiàn)永久不動的前景；另一種情況是運(yùn)動物體的移入，即運(yùn)動的目標(biāo)進(jìn)入檢測區(qū)域后，停止在場景中，導(dǎo)致檢測時出現(xiàn)虛假前景.本文引入文獻(xiàn)中介紹的TOM（Time Out Map）方法來消除鬼影的影響，TOMt（pt）表示t時刻像素pt的TOM值，其表示如下：

其中Bt（pt）＝1表示為前景，如果 TOMt（pt）大于某一閾值，則將該像素判為鬼影，采用背景更新機(jī)制將其融入到背景模型中.

2 實驗與分析

實驗是在Intel Quad CPU Q9500硬件平臺、以及Visual C＋＋6.0結(jié)合opencv1.0庫下進(jìn)行的.在本文提出的算法中主要有兩個參數(shù)ξ和τ，分別表示學(xué)習(xí)時像素間色度差的度量和前景檢測時色度差的度量，不同的場景的取值有一定的差異.在本文通過多次試驗得出ξ＝24.0，τ＝32.0可以取得較好的檢測結(jié)果，另外，算法學(xué)習(xí)幀數(shù)N＝300.

1）實驗1：該視頻序列是公路上對行駛汽車進(jìn)行監(jiān)控的一段視頻runningcar.avi，該視頻序列伴隨有光照的變換，并且視頻序列的一開始就有汽車在行駛.實驗結(jié)果如圖1所示.

2）實驗2：該實驗是在一棟教學(xué)樓大門前采集的一段視頻buildingperson.avi，視頻序列伴隨有光照的變化以及輕微的陰影，且視頻在一開始就有大量的行人來來往往.

圖3 視頻源幀

圖4 檢測的前景

通過實驗1和實驗2可以看到，本文提出的算法能夠較精確地提取出運(yùn)動目標(biāo)的信息，并且對光照的變化具有一定的魯棒性.另外，這兩個實驗都是在一開始有運(yùn)動目標(biāo)的場景中進(jìn)行的，視頻能夠較好地對初始有運(yùn)動目標(biāo)的場景進(jìn)行處理，消除由于場景中運(yùn)動目標(biāo)的移入移出形成的虛背景.

3 結(jié) 論

本文分析了背景建模的相關(guān)技術(shù)，并針對其中的不足，提出了基于改進(jìn)K均值運(yùn)動目標(biāo)檢測算法.該算法引入修正的K均值聚類算法對視頻序列進(jìn)行學(xué)習(xí)并建立背景模型，并提出了一種像素相關(guān)的選擇性背景更新機(jī)制.經(jīng)過多個實驗驗證，表明該算法是有效的，并能夠較為準(zhǔn)確地提取出運(yùn)動目標(biāo)的信息，對光照具有較強(qiáng)的魯棒性，并且能夠較好地處理由于目標(biāo)在場景中移入移出形成的虛背景.但算法也存在一些不足，針對黑色或白色的運(yùn)動目標(biāo)可能會出現(xiàn)漏檢的現(xiàn)象，將在后續(xù)工作中進(jìn)行深入研究.

［1］ Kim K，Chalidabhongse T H，Hardwood D，et al.Real－time Foreground－background Segmentation Using Codebook model［J］.Real－Time Imaging，2005，11（3）：172－185.

［2］ 許雪梅，墨 芹，倪 蘭，等.基于局部更新的分層碼本目標(biāo)檢測算法［J］.計算機(jī)應(yīng)用，2011，31（12）：3399－3402.

［3］ P.Kadew Tra Ku Pong，R.Bowden.An Improved A－daptive Background Mixture Model for Real－time Tracking with Shadow Detection［C］.2001proc.2nd European Workshop on Advanced Video－Based Surveillance Systems，2001：149－158.

［4］ 黃鑫娟，周潔敏，劉伯揚(yáng).自適應(yīng)混合高斯背景模型的運(yùn)動目標(biāo)檢測方法［J］.計算機(jī)應(yīng)用，2010，30（1）：71－74.

［5］ 謝勤嵐，李圓雙，喻 該.基于高速球形攝像機(jī)的運(yùn)動目標(biāo)檢測與實時跟蹤系統(tǒng)［J］.中南民族大學(xué)學(xué)報：自然科學(xué)版，2010，29（2）：82－83，112.

［6］ Brutzer S，Hoferlin B，Heidemann G.Evaluation of Background Subtraction Techniques for Video Surveillance［C］.2011IEEE conference on Computer vision and pattern recognition，2011：1937－1944.

［7］ Benezeth Y，Jodoin PM，Emile B，et al.Review and E－valuation of Commonly－implemented Background Subtraction Algorithm－ms［C］.19th International Conference on Pattern Recognition，2008：1－4.

［8］ Juan C，SanMiguel，Jose＇M，et al.On the Evaluation of Background Subtraction Algorithms Without Groundtruth［C］.2010Seventh IEEE International Conference on Advanced Video and Signal Based Surveillance，2010：180－187.

［9］ Hanzi Wang，David Suter.Background Subtraction Based on a Robust Consensus Method［C］.Proceedings of the 18th International Conference on Pattern Recognition，2006：223－236.

［10］Olivier Barnich，Marc Van Droogenbroeck.VIBE：A Powerful Random Technique to Estimate the Background in Video Sequences［C］.International Conference on Acoustics，Speech and Signal Processing，2009：945－948.

［11］Lucia Maddalena，Alfredo Petrosino.A Self－organizing Approach to Background Subtraction for Visual Surveillance Applications［J］.IEEE Transactions on Image Processing，2008，17（7）：1168－1177.

［12］楊會鋒，曹 潔，帥立國.基于改進(jìn)K－均值聚類算法的背景建模方法［J］.電子測量與儀器學(xué)報，2010，24（12）：1114－1118.

［13］查成東，王長松，鞏憲鋒，等.基于改進(jìn)K－均值聚類算法的背景提取方法［J］.計算機(jī)工程與設(shè)計，2007，28（21）：5141－5143.

［14］張運(yùn)楚，梁自澤，李 恩，等.基于C－均值聚類的視頻監(jiān)控背景圖像構(gòu)建算法［J］.計算機(jī)工程與應(yīng)用，2006：45－47.

［15］Charoenpong T，Supasuteekul A，Nuthong C.Adaptive Background Modeling from an Image Sequence by Using K－Means Clustering［C］.2010International Conference on ECTI－COM，2010：880－883.

［16］張學(xué)工.模式識別［M］.3版.北京：清華大學(xué)出版社，2010，192：195.