一种自适应分裂与合并的运动目标聚类分割算法

张琨王翠荣



一种自适应分裂与合并的运动目标聚类分割算法

张 琨*①②王翠荣②

①(东北大学信息科学与工程学院 沈阳 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