朱敏

摘要：對圖像序列中的運動目標(biāo)進行實時檢測是視頻處理領(lǐng)域一項基礎(chǔ)性工作，背景減除法是主要的運動目標(biāo)檢測方法，有許多的背景模型用于處理不同的問題。提出了一種基于改進的K均值聚類算法的背景建模方法。實驗結(jié)果顯示該方法在復(fù)雜背景環(huán)境下具有有效性和魯棒性，取得了較好的精確度。

關(guān)鍵詞：背景減除法；背景建模；K均值聚類

中圖分類號：TP391 文獻標(biāo)識碼：A 文章編號：1009-3044（2015）28-0141-03

Background Modeling Method Based on Clustering

ZHU Min

（Dept. of Management & Information， Nantong Shipping College， Nantong 226010， China）

Abstract：Real-time moving objects detection in image sequences is a fundamental step in the video processing field. A typical method is background subtraction. Many background models have been introduced to deal with different problems. This paper proposes a improved K means clustering based Background modeling method. The experimental results show that the proposed method is efficient and robust for the dynamic environment and achieves good accuracy.

Keywords： background subtraction； Background modeling； K means clustering

分析和理解視頻序列是一個熱點的研究領(lǐng)域，與此相關(guān)的應(yīng)用很多，如智能視頻監(jiān)控、人機交互的感知接口、醫(yī)療圖像分析、軍事上的導(dǎo)彈制導(dǎo)、雷達視頻圖像分析等。運動目標(biāo)檢測是這類研究的基礎(chǔ)，運動目標(biāo)檢測將運動物體（前景）從靜態(tài)信息（背景）中分離出來。

常用的運動目標(biāo)檢測方法有背景減除法、幀間差分法、光流法等，其中背景減除法因其原理簡單、易于實現(xiàn)、所檢測的運動對象完整等特點，是最常用的一種方法。

1 背景減除法

背景減除法的基本思想是先構(gòu)建一個不包含運動物體的靜態(tài)背景圖像，然后用當(dāng)前圖像與背景圖像對應(yīng)像素點的灰度差值來判斷運動目標(biāo)，如果灰度差值大于設(shè)定的閾值，則判定該像素點屬于運動目標(biāo)；如果灰度差值小于設(shè)定的閾值，則判定該像素點屬于背景。使用背景減除法進行運動目標(biāo)檢測通常包含以下幾個步驟：

1）背景建模：背景減除法首先要確定使用何種方式對背景建模，這是背景減除法的關(guān)鍵所在。

2）背景初始化：最簡單的背景初始化方法是以視頻序列的第一幀作為初始背景。也可以用一段訓(xùn)練視頻通過學(xué)習(xí)得到初始背景。

3）背景更新：背景不是一成不變的，隨著時間的變化，背景場景會發(fā)生變化，與此相適應(yīng)，背景圖像也應(yīng)該及時更新。

4）前景檢測：前景檢測把當(dāng)前圖像與背景圖像進行比較，把當(dāng)前圖像中的每個像素劃分為前景像素或者是背景像素。

背景減除法的基本思路非常簡單，但在實際應(yīng)用中卻面臨一系列的問題。比如在動態(tài)的環(huán)境下，要獲取一個沒有運動物體的靜態(tài)背景圖像是非常困難的。此外，諸如變化的光照條件、攝像機的抖動、波動的水面、晃動的樹木等都對背景圖像的建立構(gòu)成挑戰(zhàn)。為解決這些問題，人們提出了各種各樣的背景建模方法。

Stauffer與Grimson提出了混合高斯模型[1]對動態(tài)背景建模，混合高斯模型使用多個高斯模型來表征圖像中的像素點，通過對每個分布的匹配檢驗，來判斷哪個分布最接近背景分布。能較好地適應(yīng)緩慢變化的動態(tài)場景，如漸變的光照，搖動的樹木等。但它的計算復(fù)雜度較高，無法處理像光照的突變、前景停留或背景移出等情況。Karmann與Brandt建立了基于Kalman濾波[2]的自適應(yīng)模型，該模型較好地隨天氣和光線等的改變調(diào)整背景。Kyungnam Kim 等人提出了碼本算法[3]，通過長時間的采樣對每個像素不同值的出現(xiàn)頻率進行統(tǒng)計，以此區(qū)分背景和前景，同時對于一些動態(tài)的環(huán)境干擾具有一定的抑制能力，但是其計算開銷較大，實現(xiàn)復(fù)雜。Butler等人提出了基于K均值聚類的建模算法[4]，利用最小距離準(zhǔn)則對每個像素分類，該方法的優(yōu)點是計算的復(fù)雜度比較低，但它對初始聚類中心選取的依賴性很大，容易陷入局部最優(yōu)解。

本文提出了一種基于改進的K均值聚類算法的背景建模方法，解決由于初始聚類中心選擇的隨機性而可能導(dǎo)致的局部最優(yōu)解問題。

2 k均值聚類算法介紹

k均值聚類算法是一種基于樣本間某種距離或相似性度量來定義的一種間接聚類方法，其基本思想是：在一個待分類的數(shù)據(jù)樣本集中，隨機選擇k 個對象， 每個對象代表一個聚類中心。對其余的每一個對象， 按該對象與各個聚類中心之間的距離， 把它分配到與之最相似的聚類中， 使得聚類內(nèi)部對象之間的相似度最大， 而聚類之間對象的相似度最小， 其中聚類的相似度是關(guān)于聚類中對象的均值度量， 可看成聚類的質(zhì)心或者重心。然后， 計算每個聚類的新中心。重復(fù)上述過程， 直到準(zhǔn)則函數(shù)收斂。

設(shè)X 是待分類的數(shù)據(jù)樣本集，第i個聚類Ci有Ni個樣本，mi是這些樣本的均值，即

那么所有樣本與其所屬的聚類中心之間的誤差平方和為

通過迭代，不斷調(diào)整樣本所歸屬的聚類使Je極小，使Je極小的聚類C1，C2，…，Ck就是樣本集 X的最優(yōu)劃分。

K均值算法的步驟為：

（1）任意選擇K個對象作為初始聚類中心；

（2）計算每個對象到各個聚類中心的距離，根據(jù)最小距離原則劃分對象所歸屬的聚類；

（3）重新計算各個聚類的均值并將其作為該聚類的中心；

（4）重復(fù)（2）、（3）直到各個聚類不再發(fā)生變化為止。

3 改進的K均值聚類背景建模方法

對上述傳統(tǒng)的K均值聚類算法進行分析，該算法最大的問題在于初始聚類中心的選取是隨機的。選擇不同的初始聚類中心，得到的最終聚類結(jié)果是不同的，導(dǎo)致的后果是容易陷入局部最優(yōu)解。文獻[5]提出一種基于遺傳算法的K均值聚類方法，但這種方法只適用于樣本數(shù)量較小， 類別數(shù)不大的情況， 如果數(shù)據(jù)量大， 類別數(shù)多時，計算量大大增加，而且效果也不如K均值聚類算法。

本文所改進的算法思路是，如果在K均值聚類算法初始化時，所選擇的初始聚類中心與樣本數(shù)據(jù)集本身的分布相一致，就相對容易得到最優(yōu)化的聚類結(jié)果。

設(shè)X 是數(shù)據(jù)樣本集，可以如下方式得到初始的聚類中心。首先計算數(shù)據(jù)集X中任意兩個數(shù)據(jù)點之間的距離。其次找到其中距離最短的兩個數(shù)據(jù)點，把這兩個數(shù)據(jù)點放到集合Ai中，并把這兩個數(shù)據(jù)點從X中刪除。第三步計算Ai中的每一數(shù)據(jù)點與X中的每一數(shù)據(jù)點的距離，找到與Ai距離最近的數(shù)據(jù)點，把它從X中刪除，加到Ai中。重復(fù)第三步直到Ai中的數(shù)據(jù)點數(shù)目達到一個設(shè)定的閾值。然后回到第二步組成另一個數(shù)據(jù)集。如此重復(fù)，直到組成K個數(shù)據(jù)集。最后分別計算這K個數(shù)據(jù)集的均值，就是所要找的初始聚類中心。

假設(shè)，數(shù)據(jù)集X中包含n個數(shù)據(jù)點，我們要將它們分成K個聚類，改進后的算法步驟如下：

（1）令i=1，計算X中任兩個數(shù)據(jù)點間的距離，找到距離最短的兩個數(shù)據(jù)點，把它們放入Ai（1<=i<=k）中，并把它們從X中刪除；

（2）在X找到與Ai中數(shù)據(jù)點最近的點，把它加到Ai中，并從X中刪除；

（3）重復(fù)（2），直到Ai中的數(shù)據(jù)點的數(shù)量達到一個設(shè)定的閾值T；

（4）如果i

（5）對第一個Ai（1<=i<=k）計算其均值，得到每個數(shù)據(jù)集的中心點，這些點就是我們要找的初始聚類中心；

（6）從步驟（2）開始執(zhí)行傳統(tǒng)K均值聚類算法。

4 實驗結(jié)果與分析

為驗證算法的有效性，我們使用了公共數(shù)據(jù)庫中的幾段測試視頻進行了測試實驗，實驗的環(huán)境為Intel Core i3 2.4GHz CPU，4G內(nèi)存，Windows7操作系統(tǒng)。編程環(huán)境為VS2010，Opencv2.7。

在背景減除法中，被檢測圖像每個像素的分類有四種：真陽性（TP），即前景像素被正確分類；假陽性（FP），即背景像素錯分類為前景像素；真陰性（TN），即背景像素被正確分類；假陰性（FN），即前景像素被錯分類為背景像素。

在前景檢測完成后，根據(jù)每個像素的分類結(jié)果，我們可以用靈敏度，精確度，相似度等對算法進行評估，它們的公式如下：

在實驗中我們對本文方法與其他的背景建模方法的效果進行了比較。圖1為對公開數(shù)據(jù)庫中Waving trees序列圖像第247幀的背景模型和前景檢測結(jié)果，表1是本文方法與其他兩種背景建模方法的比較結(jié)果。圖2為對公開數(shù)據(jù)庫中Fountain序列圖像第440幀的背景模型和前景檢測結(jié)果，表2是本文方法與其他兩種背景建模方法的比較結(jié)果。

以上圖、表顯示，本文的背景建模方法取得了較好的效果，在靈敏度、精確度、相似度等多個指標(biāo)上都較另兩種方法有所提高。在動態(tài)的環(huán)境下，具有較好的魯棒性和有效性。

5 結(jié)論

本文提出了一種基于聚類的改進的背景建模方法，針對傳統(tǒng)K均值聚類算法容易陷入局部最優(yōu)解等的缺點，提出了改進的算法，在進行K均值聚類算法之前先對數(shù)據(jù)點進行預(yù)處理。實驗結(jié)果顯示本文方法取得了較好的檢測效果，對動態(tài)、復(fù)雜場景下的背景提取和前景檢測是有效的。

參考文獻：

[1] Stauffer C， Grimson E. Adaptive background mixture models for real-time tracking.IEEE Conference on Computer Vision and Pattern Recognition， CVPR 1999，pages 246–252， 1999.

[2] Kim H， Sakamoto R， Kitahara I， et al. Robust foreground extraction technique using Gaussian family model and multiple thresholds. Asian Conference on Computer Vision， ACCV 2007， pages 758–768， November 2007.

[3] Karmann K， Von Brand A. Moving object recognition using an adaptive background memory. Time-Varying Image Processing and Moving Object Recognition， Elsevier， 1990.

[4] Butler D， Bove D， Shridharan S. Real time adaptive foreground/background segmentation. EURASIP， pages ， 2005：2292-2304.

[5] 王敞，陳增強.基于遺傳算法的K-均值聚類分析[J].計算機科學(xué)，2003，30（2）：163-164.

[6] Klare B， Sarkar S.Background subtraction in varying illuminations using an ensemble based on an enlarged feature set[C].in IEEE Comput. Soc. Conf. on Comput. Vision and Pattern Recognit. Workshops，2009.