一種自適應分裂與合并的運動目標聚類分割算法

張琨王翠榮

?

一種自適應分裂與合并的運動目標聚類分割算法

張 琨*①②王翠榮②

①(東北大學信息科學與工程學院 沈陽 110819)②(國家985工程下一代網絡技術實驗室 秦皇島 066004)

針對智能監控系統中多個運動目標進行圖像分割這一問題，該文提出一種自適應分裂與合并的多運動目標聚類分割算法。該算法首先利用視頻圖像的時域信息，通過樣本方差進行背景建模，分割出包含多個運動目標的前景圖像。然后定義了像素點的空間連通率，并設計一種利用中垂線分割法，對初始聚類進行自適應分裂與合并。在無需事先設定聚類分割數目的條件下，自組織迭代聚類算法能完成多運動目標的分割。實驗結果證明該算法對多運動目標分割效果好，分割結果與人眼視覺的判斷一致。利用空間連通信息使得算法迭代收斂速度快，具有良好的實時性。

圖像處理；聚類分割算法；背景建模；空間連通率；中垂線分割

1 引言

聚類算法是一種能將某一特征空間的特征點自動分類到不同的類或是簇的過程，是一種能快速、準確實現多運動目標智能分割的有效方法。本文考慮利用聚類算法來研究多運動目標分割問題。目前常用的聚類法包括K-means聚類法[15]、迭代自組織數據分析技術算法[16](Iterative Self-Organizing Data Analysis Techniques Algorithm, ISODATA)、模糊聚類法[17]等。K-means算法優點是計算簡單，快速高效，缺點是聚類數K必須提前設定。ISODATA算法優點是聚類的數量從數據中自動產生，算法效率高，適用于識別致密聚類，缺點是初始聚類中心的選擇影響聚類效果和聚類時間。模糊聚類算法優點是模糊化的聚類結果比確定性的聚類結果包含更多的信息，缺點是模糊聚類數目不能在動態聚類完成時確定。本文選擇對ISODATA算法進行改進，提出了一種自適應分裂與合并的多運動目標聚類分割算法。算法利用運動目標的空間連通信息，給出像素點空間連通距離，像素點空間連通度，連通率概念，用來描述像素點的空間特征。將ISODATA聚類算法中的樣本點間相似性度量標準，由原來采用的歐氏距離改為用像素點連通率作為自適應分裂與合并的聚類相似性度量，并引入中垂線分裂方法，使得ISODATA算法中的隨機分裂改為有標準分裂，聚類分裂與合并更快速，提高算法整體的收斂速度。算法在保證多運動目標分割準確率的同時，還解決了聚類分割時產生不連通分割區域的問題。

2 多運動目標聚類分割算法

2.1 像素點的空間連通率

圖1 像素點空間連通距離和空間T連通度

2.2 基于樣本方差的背景建模算法

在監控視頻中，不難發現監控畫面中存在很多區域是顯著背景區域，在這些區域中不經常出現甚至不出現運動目標，例如天空，街道的死角，建筑物外觀等。針對這一特點，本文利用基于樣本方差的背景建模算法，對那些背景或前景特征顯著的像素點進行快速判別，具體描述算法如下：

2.3 自適應分裂與合并的運動目標聚類分割算法

在定義了像素點的空間連通率和基于樣本方差的背景建模法基礎上，本文提出了一種自適應分裂與合并的運動目標聚類分割算法。算法具體描述如下：

(1)利用基于樣本方差的背景建模算法，從視頻圖像中分割出含有多個運動目標的前景灰度圖像。

如果，則將聚類與合并，得到新的聚類中心。

本文提出的算法既利用了樣本方差進行背景建模，提取包含多個運動目標的前景圖像，又利用視頻圖像中像素點之間的空間連通信息，定義像素點的空間連通(Spatial Connectivity)率，并在此基礎上設計了一種自適應分裂與合并，自組織迭代聚類(Clustering)的多目標圖像分割(Segmentation)算法，是一種時空域聯合的運動目標聚類分割算法，簡稱為SCCS算法。

3 實驗結果與分析

為了驗證本文提出的SCCS算法，下面從算法的可行性，像素點連通率的統計規律，算法的收斂性，聚類分割實驗結果的比較與分析及相關算法比較與分析這5個方面進行SCCS算法的驗證與分析。使用Intel(R) Core(TM)2 6300 CPU, 1.86 GHz, 1 GB內存的PC機，利用Java語言進行編程，在Eclipse開發平臺上對分辨率為336×448的交通路口監控視頻進行算法實驗。

3.1 算法的可行性驗證

選取20幀序列圖像并不斷更新到80幀序列監控視頻圖像，利用基于樣本方差背景建模算法得到對應的實時背景圖像如圖3所示。從圖3中可以看出，隨著實時幀圖像的不斷更新，背景建模能適應目標從靜止到運動狀態的改變，能得到對應的實時性背景圖像。在實時背景圖像基礎上，圖4列舉了連續視頻幀圖像利用SCCS算法得到的對應前景運動目標分割圖像。從圖4中可以看出，運動目標檢測與分割結果大多是包含多個運動目標的前景圖像，并且在一定時段內分割出的序列多運動目標的特征具有一定相似性。在不同時間段內的序列前景圖像中，選取了5張包含運動目標數量較多的前景圖像進行聚類分割實驗。

圖3 背景圖像

圖4 幀圖像與運動目標分割圖像

3.2 像素點連通率的統計規律

為了分析像素點連通率在本文提出的SCCS算法中起到的作用，統計和比較了算法中像素點連通率的變化規律。隨著迭代次數的增加，每個聚類中像素點連通率的平均值和中間值的變化趨勢是逐漸調整初始聚類中的像素點，使得每個聚類中像素點與聚類中心的連通率達到迭代收斂條件。對前景圖像2中的多運動目標共進行了3次迭代聚類分割，每次迭代后各個聚類中像素點連通率的平均值與中間值的變化趨勢如圖6所示。從圖6中可以看出，第1次迭代與第2次迭代相比，不同聚類中像素點連通率平均值和中間值都產生了較大變化，而第2次與第3次迭代后所得聚類中像素點連通率的變化較小，已經趨于穩定。可見SCCS算法中聚類分裂與合并的效果明顯，并隨著迭代次數的增加，聚類分裂與合并趨于穩定。

3.3 算法的收斂性驗證

本文提出的聚類分割方法改進了ISODATA聚類算法中的樣本點間相似性度量標準，將原來采用的歐氏距離改為用像素點連通率作為自適應分裂與合并的聚類相似性度量，并引入中垂線分裂方法，使得ISODATA算法中的聚類分裂更快速，由原來的隨機分裂改為有標準分裂，提高算法整體的收斂速度。上述兩種改進從根本上沒有改變ISODATA算法的迭代方式，并沒有影響到算法整體的收斂性。總之算法收斂性實驗和分析可以證明利用像素點連通率進行自組織迭代分裂和合并的聚類分割算法是收斂的。

圖5 多目標聚類分割結果

圖6 聚類分割迭代收斂圖

圖7 聚類分割迭代收斂圖

3.4 多運動目標分割實驗結果的比較與分析

為了比較本文算法中多運動目標分割的有效性，選取K-means算法及ISODATA算法作為比較算法，對相同的前景圖像進行多目標聚類分割實驗。選擇包含多個復雜目標的前景圖像作為實驗圖像，本文算法的實驗結果以及K-means算法，ISODATA算法多目標分割結果如圖8所示。從圖8中可以看出，目標距離較近時，K-means算法進行圖像分割的效果較差，把應該分為一類的目標分裂為兩類，對其它目標的聚類分割造成影響，如圖8(a)所示。ISODATA算法的目標分割效果有一定提高，但還是存在分割誤差，如圖8(b)所示。本文提出的目標分割效果最好，如圖8(c)所示，不僅目標聚類數與人眼判斷一致，且不存在將同一目標劃分在不同聚類中的現象，即每個聚類中樣本點之間有良好的空間聯通性。

本文提出的SCCS算法與ISODATA算法都需要進行自適應聚類分裂與合并運算，而K-means算法不進行聚類的分裂與合并運算，因此選擇與ISODATA算法做更進一步的分析和比較。分析比較算法的收斂迭代數，每次迭代時產生的聚類分裂與合并數的變化情況如圖9所示，圖9中的數據是這兩種算法對前景圖像3進行運動目標聚類分割時的實驗數據。從圖9中可以看出，SCCS算法的迭代次數為8，明顯少于ISODATA算法的迭代次數15。SCCS算法迭代收斂速度快，具有良好的實時性。如圖9(a)所示，ISODATA算法在迭代6次后其分裂次數出現快速減少下降的變化趨勢。如圖9(b)所示，SCCS算法在迭代過程中，其聚類分裂次數有逐漸增加和減少的變化規律，同時SCCS算法聚類合并次數的變化與對應的聚類分割次數之間有一定的關聯性，而ISODATA算法合并的次數變化關聯性較弱。因此，SCCS算法的聚類分裂與合并具有一定優勢。

3.5 相關方法的比較與分析

若不利用視頻圖像的時域信息，僅利用視頻圖像的空域信息對單幀圖像中出現的目標進行分割，那些基于時域信息的運動目標檢測方法(如幀差法、背景建模法等)沒有被利用，無法判斷幀圖像中出現的是運動目標還是靜止目標。利用基于空域信息的圖像分割算法(如閾值分割法、聚類分割法等)將圖像劃分為在空間上互不重疊的區域，這些方法會分割出許多冗余目標，例如建筑物、斑馬線、道路兩旁的植物等，付出不必要的計算代價。因此針對多運動目標檢測和多目標區域分割這一問題，本文提出的SCCS算法同時利用幀圖像時域與空域信息，具有一定優勢。與盧志茂等人[12]提出的一種基于數據競爭的高分辨率圖像的聚類分割算法和袁罡等人[13]提出的一種蟻群聚類檢測算法相比，前者與mean shift 聚類算法結合應用于靜態彩色圖像分割問題，后者實現了對靜止目標的檢測，相比之下本文提出的SCCS算法能夠檢測出運動目標，并進一步得到目標整體分割圖像，計算復雜度小，適用于對視頻幀圖像進行實時處理。與葉有時等人[14]提出的一種基于行掃描點線目標聚類合并的快速實時多目標檢測算法相比，該聚類算法針對的是二值圖像，對單幀目標進行全視場檢測并編號標記，而SCCS算法針對的是連續幀圖像，并能實現灰度圖像和彩色圖像中的多運動目標分割，得到的結果不是位置點的檢測和標定，而是運動目標的完整分割圖像，適用于更進一步的目標識別與跟蹤，實際應用價值高。

圖8 3種不同聚類算法目標分割效果比較圖

圖9 不同聚類算法迭代分裂與合并比較圖

4 結束語

本文提出的SCCS算法利用樣本方差背景建模進行運動目標檢測，利用像素點空間連通率提出一種中垂線分割方法，設計了一種新的自組織聚類分裂與合并的圖像聚類多運動目標分割算法。在大量的實驗數據基礎上，通過對算法目標函數的收斂性進行分析，對聚類中心的迭代收斂性進行分析，分析結果證明了SCCS算法是收斂的，可行的。與K-means算法及ISODATA算法進行圖像聚類分割效果比較，本文提出的算法目標聚類分割效果理想，對相同的圖像進行聚類分割時，其聚類迭代次數少于ISODATA算法，進一步證明了SCCS算法的目標聚類分割是快速迭代和有效的。關于SCCS算法，下一步的研究工作的重點是：研究有遮擋時的多運動目標分割，及如何在Mapreduce開發平臺上實現迭代自適應分裂與合并聚類算法，使得算法更加適應于大量視頻幀圖像數據下的多運動目標圖像分割。

[1] 任明藝. 時空聯合的視頻運動目標分割技術研究[D]. [博士論文]. 電子科技大學, 2010: 3-13.

[2] Wang Ru, Zhao Chun-jiang, and Guo Xin-yu. Improved cam-shift algorithm based on frame-difference method for video's auto tracking[J]., 2012, 6(19): 137-144.

[3] Chen Kang-lin and Lorenz D A. Image sequence interpolation based on optical flow, segmentation, and optimal control[J]., 2012, 21(3): 1020-1030.

[4] Liu Hong-hai and Hou Xiang-hua. Moving detection research of background frame difference based on Gaussian model[C]. 2012 International Conference on Computer Science and Service System (CSSS),Nanjing, 2012: 258-261.

[5] Verma1 O P, Hanmandlu M, Susan S,.. A simple single seeded region growing algorithm for color image segmentation using adaptive thresholding[C]. 2011 International Conference on Communication Systems and Network Technologies, Katra, Jammu, 2011: 500-503.

[6] Saraswathi S and Allirani A. Survey on image segmentation via clustering[C]. 2013 International Conference on Information Communication and Embedded Systems (ICICES), Chennai, 2013: 331-335.

[7] Qin A K and David A. Multivariate image segmentation using semantic region growing with adaptive edge penalty [J]., 2010, 19(8): 2157-2170.

[8] 甘明剛, 陳杰, 劉勁, 等. 一種基于三幀差分和邊緣信息的運動目標檢測方法[J]. 電子與信息學報, 2010, 32(4): 894-897.

Gan Ming-gang, Chen Jie, Liu Jin.. Moving object detection algorithm based on three-frame-differencing and edge information[J].&, 2010, 32(4): 894-897.

[9] Zhuang Hua-liang, Low Kay-soon, and Yau Wei-yun. Multichannel pulse-coupled-neural-network-based color image segmentation for object detection[J]., 2012, 59(8): 3299-3308.

[10] Sheikh Y and Shah M. Bayesian modeling of dynamic scenes for object detection[J]., 2005, 27(11): 1778-1792.

[11] 鄧廷權, 王占江, 汪培培. 基于區間值模糊集熵的水下目標動態閾值檢測[J]. 哈爾濱工程大學學報, 2011, 32(2): 246-250.

Deng Ting-quan, Wang Zhan-jiang, and Wang Pei-pei. An interval valued fuzzy entropy approach to object detection with dynamic thresholding for underwater images[J]., 2011, 32(2): 246-250.

[12] 盧志茂, 范冬梅, 陳炳才, 等. 一種基于數據競爭的高分辨率圖像的聚類分割算法[J]. 中國科學F輯: 信息科學, 2012, 42(9): 1147-1157.

Lu Zhi-mao, Fan Dong-mei, Chen Bing-cai,.. A data competition based clustering algorithm for large image segmentation[J]., 2012, 42(9): 1147-1157.

[13] 袁罡, 陳鯨. 無源時差定位系統的靜止目標聚類檢測算法[J]. 電子與信息學報, 2010, 32(3): 728-731.

Yuan Gang and Chen Jing. A clustering detection algorithm of stationary target for passive time difference location system[J].&, 2010, 32(3): 728-731.

[14] 葉有時, 唐林波, 趙保軍. 一種基于聚類的深空紅外多目標快速檢測算法[J]. 電子與信息學報, 2011, 33(1): 77-84.

Ye You-shi, Tang Lin-bo, and Zhao Bao-jun. A fast deep-space infrared multi-target detection algorithm based on clustering[J].&, 2011, 33(1): 77-84.

[15] Mignotte Max. A de-texturing and spatially constrained K-means approach for image segmentation[J]., 2011, 32(2): 359-367.

[16] Takahashi K Abe. Color image segmentation using ISODATA clustering algorithm[J]., 1999, J82D-D-2(4): 751-762.

[17] Ji Ze-xuan, Xia Yong, Chen Qiang,.. Fuzzy c-means clustering with weighted image patch for image segmentation [J]., 2012, 12(6): 1659-1667.

張 琨： 女，1978年生，博士生，講師，研究方向為數字圖像處理、視頻運動目標檢測、模式識別.

王翠榮： 女，1963年生，博士，教授，研究方向為物聯網數據挖掘、數字圖像處理.

An Adaptive Splitting and Merging Clustering Algorithm of the Moving Target Segmentation

Zhang Kun①②Wang Cui-rong②

①(,,110819,)②(985,066004,)

For the issue of multiple moving targets’ segmentation in intelligent monitoring system, an adaptive splitting and merging clustering algorithm of the moving target segmentation is proposed. First, it uses the time-domain information for foreground image segmentation through the sample variance background modeling algorithm, thus obtains the foreground image containing multiple moving targets. It defines pixel space connectivity rate and designs a perpendicular split method for the initial cluster adaptive splitting and merging. Without pre-set number of initial cluster, the self-organized iterative clustering segmentation algorithm can complete multiple moving targets segmentation. Experimental results show that the proposed algorithm is suitable for multiple moving targets’ segmentation, and the segmentation results are consistent with the human visual judgment. The use of space connectivity information improves the iterative algorithm convergence speed, thus it has good real-time.

Image processing; Cluster segmentation algorithm; Background modeling; Spatial-connectivity rate; Perpendicular segmentation

TP391.41

A

1009-5896(2014)03-0601-09

10.3724/SP.J.1146.2013.00652

2013-05-10收到，2013-07-18改回

國家自然科學基金(61070162)，河北省自然科學基金(F2012501014)和河北省科學技術研究與發展計劃項目(112135122)資助課題

張琨 zkhbqhd@163.com