第２８卷第１２期２０１１年１２月
计算机应用研究
ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ
Ｖｏｌ畅２８Ｎｏ畅１２Ｄｅｃ畅２０１１
基于分水岭和改进的模糊聚类图像分割
龚 劬，姚玉敏
（重庆大学数学与统计学院，重庆４０１３３１）
倡
摘 要：针对模糊Ｃ唱均值聚类算法需预先给出初始聚类中心、未考虑邻域信息、计算复杂度高等缺点，提出了一种基于分水岭和改进的模糊聚类图像分割方法。该方法首先利用分水岭分割方法对原图像进行预分割，然后利用粒子群的全局寻优能力从预分割的小区域中搜索出较为准确的初始聚类中心；最后，在对小区域进行模糊聚类时，建立了包含邻域信息的聚类目标函数。实验表明，该方法分割速度快、抗噪能力强，实现了图像的较优分割。
关键词：分水岭算法；粒子群算法；模糊聚类；图像分割
中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１００１唱３６９５（２０１１）１２唱４７７３唱０３ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．１２．１００
ＩｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎｂａｓｅｄｏｎｗａｔｅｒｓｈｅｄａｎｄｉｍｐｒｏｖｅｄｆｕｚｚｙＣ唱ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇ
（ＣｏｌｌｅｇｅｏｆＭａｔｈｅｍａｔｉｃｓ＆Ｓｔａｔｉｓｔｉｃｓ，ＣｈｏｎｇｑｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ４０１３３１，Ｃｈｉｎａ）
ＧＯＮＧＱｕ，ＹＡＯＹｕ唱ｍｉｎ
Ａｂｓｔｒａｃｔ：ＩｎｏｒｄｅｒｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｓｉｎＦＣＭ（ｆｕｚｚｙＣ唱ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇ）ｓｕｃｈａｓｔｈｅｏｒｉｇｉｎａｌｃｌｕｓｔｅｒｃｅｎｔｅｒｓｔｏｂｅｇｉｖｅｎｉｎａｄｖａｎｃｅ，ｎｏｔｃｏｎｓｉｄｅｒｉｎｇｎｅｉｇｈｂｏｒｉｎｆｏｒｍａｔｉｏｎａｎｄｈｉｇｈｃｏｍｐｌｅｘｉｔｙ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｎｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎｂａｓｅｄｏｎｗａ唱ｔｅｒｓｈｅｄａｎｄｉｍｐｒｏｖｅｄＦＣＭ．Ｄｉｖｉｄｉｎｇｉｍａｇｅｗｉｔｈｔｈｅｈｅｌｐｏｆｗａｔｅｒｓｈｅｄａｌｇｏｒｉｔｈｍ，ａｎｄｇａｉｎｅｄｔｈｅｐｒｉｍａｒｙｒｅｓｕｌｔｓ．ＩｔｍａｄｅｆｕｌｌｕｓｅｏｆｔｈｅａｂｉｌｉｔｙｏｆｇｌｏｂａｌｏｐｔｉｍｉｚａｔｉｏｎＰＳＯ（ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ）ｔｏｏｂｔａｉｎｔｈｅａｃｃｕｒａｔｅｏｒｉｇｉｎａｌｃｌｕｓｔｅｒｃｅｎｔｅｒｓｏｆＦＣＭ．Ｉｔｈａｄｂｅｅｎｅｓｔａｂｌｉｓｈｅｄａｎｏｖｅｌｏｂｊｅｃｔｉｖｅｆｕｎｃｔｉｏｎｗｈｉｃｈｃｏｎｔａｉｎｅｄｎｅｉｇｈｂｏｒｉｎｆｏｒｍａｔｉｏｎ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｉｓｍｅｔｈｏｄｈａｓｈｉｇｈｅｒｓｅｇｍｅｎｔａｔｉｏｎｓｐｅｅｄａｎｄｓｔｒｏｎｇｅｒａｎｔｉ唱ｎｏｉｓｅｐｒｏｐｅｒｔｙ，ａｎｄｉｔｒｅａｌｉｚｅｓｓｉｇｎｉｆｉｃａｎｔｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：ｗａｔｅｒｓｈｅｄａｌｇｏｒｉｔｈｍ；ＰＳＯａｌｇｏｒｉｔｈｍ；ｆｕｚｚｙｃｌｕｓｔｅｒｉｎｇ；ｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ
０ 引言
图像分割
［１］
图像进行预分割；然后利用粒子群的全局寻优能力
［４］
从预分
割的小区域中搜索出较为准确的初始聚类中心；最后利用改进
是模式识别和计算机视觉中的重要研究课
目标函数的模糊聚类算法对分水岭分割后的小区域聚类，减少了迭代次数，提高了分割速度，实现了图像的较优分割。
题，也是图像处理的经典难题之一，近几十年来涌现出了大量不同的图像分割方法，但是至今仍然没有一个通用且有效的图像分割方法能满足不同的需求。分水岭分割
［２］
是一种基于区
１ 分水岭变换算法
分水岭算法是一种区域提取算法，最早由Ｂｅｕｃｈｅｒ和Ｍｅｙｅｒ将其引入到图像分割领域，由于算法实现过程简单有效，现已成为广泛使用的图像分割工具。分水岭算法是一种数学扑地貌，图像中每一点像素值都表示该点的海拔高度，每一个局部极小值及其影响区域均称为集水盆，而集水盆的边界则形成分水岭
［５］
域的图像分割方法，它以快速、有效、准确的分割结果越来越得到人们的重视，但是它本身存在严重的过分割现象。目前主要有两类方法解决分水岭的过分割问题，第一类属于预处理，它是基于标记提取的分水岭分割算法；第二类属于后处理，针对分水岭分割后的结果，根据某种准则进行区域合并。本文主要是研究第二类方法，利用模糊Ｃ唱均值聚类算法对过分割的图像进行后续处理。由Ｄｕｎｎ提出后经Ｂｅｚｄｅｋ推广的模糊Ｃ唱均值（ＦＣＭ）聚类算法
［３］
形态学上的分割方法，其基本思想是把图像看做测地学上的拓
。分水岭算法具有区域增长算法的优势，区域边
作为一种无监督聚类算法已成功应用于界形成了一个封闭、连接的集合，并且具有空间一致性，同时充分利用了梯度操作捕获的边缘信息。其具体算法如下：的变化情况，在灰度值变化较大的边缘具有较大的梯度值，而在灰度值均匀的区域内部具有较小的梯度值。一幅图像ｆ的形态梯度图像定义为膨胀变换减去腐蚀变换：
ｇｒａｄｆ＝ｆ⊕ｂ－ｆΘｂ
（１）
图像分析、医疗诊断、目标识别和图像分割等领域。基于ＦＣＭ聚类的图像分割算法比原始的硬分割算法能保留更多的原始图像信息，但是传统的ＦＣＭ算法没有考虑邻域信息，并且在聚类前必须人为指定初始聚类中心，如果初始聚类中心选择不当，容易使该算法陷入局部最优，传统的ＦＣＭ算法计算量较大。为了弥补上述不足，本文提出一种基于分水岭和改进的模糊聚类图像分割算法。该方法首先利用分水岭分割方法对原
ａ）计算形态梯度图像。形态梯度图像反映了图像中灰度
其中：⊕表示膨胀运算；Θ表示腐蚀运算；ｂ为结构元素，结构
收稿日期：２０１１唱０５唱１３；修回日期：２０１１唱０６唱１７ 基金项目：中央高校基金资助项目（ＣＤＪＸＳ１１１０００３２）
作者简介：龚劬（１９６３唱），女，四川人，教授，硕导，博士，主要研究方向为图论、小波分析和图像分析；姚玉敏（１９８２唱），女，山东菏泽人，硕士研究生，主要研究方向为图像处理（ｌｄｙｙｍｈ＠１２６．ｃｏｍ）．
元素不能取太大，否则会将灰度变化剧烈的小区域过滤掉。
法中的梯度操作对噪声敏感ｂ）将梯度图像输入分水岭算法产生分割结果，容易对图像产生过分割。分水岭算
，并且不能将图像中有意义的区域表示出来。所以，必须对过分割结果进行合并，模糊Ｃ唱均值聚类算法是解决这一问题的有效方法。
２ ＦＣＭ算法对过分割图像的处理
２畅１ 传统的ＦＣＭ算法
设Ｉ＝｛ｆ（ｉ，ｊ），０≤ｉ＜Ｍ，０≤ｊ＜Ｎ｝为数据集，ｃ为聚类数
目，则聚类目标函数可写成
Ｊ（Ｕ，Ｖ）＝∑∑ｃ
（ｕｋｍ
２
ｉ，ｊｋ＝１
（ｉ，ｊ））（ｄｋ（ｉ，ｊ））
（２）
其中：Ｕ＝［ｕｋ（ｉ，ｊ）］为模糊分类矩阵，ｕｋ（ｉ，ｊ）是ｆ（ｉ，ｊ）对于第ｋ类的隶属度函数，且满足０≤ｕｃ
ｋ（ｉ，ｊ）≤１和ｋ∑＝１ｕｋ（ｉ，ｊ）＝１；Ｖ＝［ｖ１，ｖ２，…，ｖｃ］为聚类中心集合；ｍ∈［１，∞）是一个控制聚类结果的权指数；ｄｋ（ｉ，ｊ）为ｆ（ｉ，ｊ）到聚类中心ｖｋ的距离，ｄｋ（ｉ，ｊ）＝‖ｆ（ｉ，ｊ）－ｖｋ‖。ＦＣＭ算法就是通过迭代确定隶属度函数和聚类中心，使目标函数取最小。利用拉格朗日乘数法求解，可获得隶属度函数和聚类中心的迭代公式
［６］
为
ｕｋ（ｉ，ｊ）＝１
ｃ
（３）
ｐ∑＝１
（ｄｋ（ｉ，ｊ）／
ｄｐ（ｉ，ｊ））２／（ｍ－１）
ｖ∑ｋ＝
ｉ，ｊ
（ｕｋ（ｉ，ｊ））ｍｆ（ｉ，ｊ）
∑（４）
ｉ，ｊ
（ｕｋ（ｉ，ｊ））ｍ
２畅２ 初始聚类中心的确定
始聚类中心ＰＳＯ算法的全局寻优ＦＣＭ算法的核心是最优初始聚类中心的确定。
、快速收敛的优点
［７］
来确定模糊聚类的初
，本文利用
设经过分水岭分割之后，整幅图像被分成Ｍ个大小不同的小区域Ｒｉｉ＝１，２，…，Ｍ，ｍｉ，ｊ表示区域Ｒｉ的均值，在利用ＰＳＯ算法寻找初始聚类中心时，将聚类中心作为ＰＳＯ算法中的粒子进行编码
［８］
。粒子由ｃ个聚类中心组成，即ｃ个聚类中心按顺序排列构成一个粒子，对任一粒子编码如下：ｘｉ＝ｘｉ１，ｘｉ２，ｘｉ３，…，ｘｉｃ，其中ｘｉｊ表示第ｉ种聚类方式中的第ｊ个聚类中心。其适应值用ｆｘｉ表示，它经历过的最佳位置表示为Ｐｂｅｓｔｐｉ１，ｐｉ２，…，ｐｉｋ，粒子ｘｉ的速度用Ｖｉｖｉ１，ｖｉ２，…，ｖｉｋ表示。当前组成群体的所有粒子经历过的最佳位置用符号Ｇｂｅｓｔ表示，则ＧｂｅｓｔｇＢ１，ｇＢ２，…，ｇＢｋ，对每一次迭代，粒子ｘｉ在ｄ维（１≤ｄ≤ｋ）空间的运动遵循如下方程进行变化：
ｖｉｄｔ＋１＝ｗｖｉｄｔ＋ｃ１ｒ１ｐｉｄｔ－ｘｉｄｔ
＋
ｃ２ｒ２ｇＢｄｔ－ｘｉｄｔ（５）ｘｉｄｔ＋
１＝ｘｉｄｔ＋ｖｉｄｔ＋１（６）
如果粒子的规模为ｎ就代表有ｎ种聚类方式，对每个粒子的评价，本文定义了新的适应度函数为
Ｍｆｘ∑∑Ｃ
ｕ２ｉ
＝
ｊｉｊ
Ｍ
ｉ（７）
如果聚类效果越好，则粒子适应度ｆｘｉ就越高，最后从中找到一种最好的聚类方式，即为模糊聚类的初始聚类中心。２畅３ 改进的ＦＣＭ聚类图像分割
经过分水岭分割之后，整幅图像被分成Ｍ个大小不同的
小区域Ｒｉｉ＝
１，２，…，Ｍ，ｍｉ，ｊ表示区域Ｒｉ的均值，样本点ｍｉ，ｊ到聚类中心ｖｊ的距离定义为
ｄ倡ｋ
ｉ，ｊ＝Ａｓｉ
ｉ
×ｍｉ，ｊ－ｖｊ（８）
其中：ｓｉ表示第ｉ个小区域的方差，Ａｉ表示第ｉ个小区域的面积。如果第ｉ个小区域的方差越大，并且面积越小，则它聚合其他小区域的可能性就越小。此距离充分考虑了每一个小区域的空间信息和邻域信息，利用新的距离计算方法，构造改进的聚类目标函数，即为
Ｊ倡（Ｕ，Ｖ）＝∑∑ｃ
＝１
（ｕｋ（ｉ，ｊ））ｍ２
ｉ，ｊｋ（ｄ倡ｋ（ｉ，ｊ））
（９）
根据新定义的目标函数和约束条件∑ｃ
ｋ＝１
ｕｋ（ｉ，ｊ）＝１，０≤ｕｋ
（ｉ，ｊ）≤１，由拉格朗日条件极值法可以得到隶属度矩阵和聚类中心的迭代公式为
ｕｋ（ｉ，ｊ）＝１
（１０）
ｐ∑ｃ
＝１
（ｄ倡ｋ（ｉ，ｊ）／ｄ倡ｐ（ｉ，ｊ））
２／（ｍ－１）
ｖ∑（ｕｋ（ｉ，ｊ））ｍｋ＝
ｉ，ｊｍ（ｉ，ｊ）∑（ｕｋ（ｉ，ｊ））ｍ
（１１）
ｉ，ｊ
算法实现的具体步骤如下：
重ｗ，ａ最大迭代次数）给出模糊指数Ｔ，ｍ迭代终止阈值，群体规模Ｎ，、ｃ２，惯性权ε学习因子＞０；
ｃ１的Ｍｂ个小区域）对原图像的梯度图像进行分水岭分割，计算每个小区域的灰度平均值，ｍ得到初分割后
（ｉ，ｊ），将每个小区域的均值ｍ（ｉ，ｊ）作为该区域的特征数据；
把每一种聚类方式作为一个粒子ｃ）从Ｍ个小区域的特征数据中初始化出，每个粒子含有Ｎ种聚类方式ｃ种属性，对，
Ｎ个粒子用粒子群优化算法进行寻优，得到最优的一个粒子，
即为模糊聚类的初始聚类中心；
ｄｅ）根据式ｆ））计算更新前后目标函数的改变量根据式（１０）（１１）更新隶属度矩阵更新聚类中心；
；ε，或者迭代次数大于最大迭代次数，则停止迭代，如果‖，Ｊｎｅｗ倡
－Ｊｏｌｄ倡
‖＜
否则转ｄ）。
３ 实验结果与分析
为了验证本文算法的有效性，选择了模拟脑图像和Ｌｅｎａ图像进行仿真实验。实验参数作如下设置：在粒子群算法的参数中惯性权重ｗ的设置通常是从０畅９线性减小到０畅２，学习因子ｃ１＝
２，ｃ２＝２，最大迭代次数为２００。在模糊Ｃ唱均值聚类算法的参数中模糊指数ｍ＝２，迭代终止阈值ε＝１×１０
－５
，最大
迭代次数Ｔ＝１００。其中，图１为模拟脑图分割结果对比，其聚类数目ｃ＝４；图２为Ｌｅｎａ图分割结果对比，其聚类数目ｃ＝５，（ａ）为原始图像，（ｂ）为传统ＦＣＭ分割结果，（ｃ）为本文算法分割结果，由（ｂ）（ｃ）两种分割结果明显看出本文分割算法优于传统ＦＣＭ分割算法。
为了验证本文算法的鲁棒性，下面对组合图像添加噪声，并分别用传统ＦＣＭ和本文的方法分割加噪声的组合图像，然后对两者的分割效果进行对比（其中本文方法的实验参数的选择如上所述）。从图３的分割效果可以看出，本文算法对噪声图像的分割效果明显优于传统ＦＣＭ分割方法。
另外，由于本文算法运用了微粒群优化算法来寻找较为准
分割的速度。
确的初始聚类中心，减少了迭代次数，提高了运算速度。表１为传统ＦＣＭ算法与本文算法的运行时间对比。
４ 结束语
本文综合利用了梯度分水岭算法、粒子群算法和基于区域的ＦＣＭ聚类算法。先用分水岭分割方法将图像分为Ｍ个小区域，用粒子群算法从中寻找最优的初始聚类中心，最后用改进目标函数的ＦＣＭ聚类方法对相似区域进行合并，充分考虑了空间邻域信息，减少了迭代次数，提高了运算速度，增强了分割的鲁棒性。本算法充分利用了先分后聚的思想，实现了图像的较优分割。参考文献：
［１］李艳灵，沈铁．基于空间邻域信息的ＦＣＭ图像分割算法［Ｊ］．华中
科技大学学报：自然科学版，２００９，３７（６）：５６唱５９．
［２］李春月，李峰，曹鹏，等．基于分水岭变换和ＦＣＭ的图像分割［Ｊ］．
计算机工程与科学，２００９，３１（１２）：５６唱５７．
［３］王士龙，万磊，唐旭东．一种基于直方图改进的ＦＣＭ聚类水下图
像分割算法［Ｃ］／／第２９届中国控制会议．２０１０：２９唱３１．
［４］ＹＡＮＧＷｅｎ唱ｌｉ，ＺＥＮＧＺｈｉ唱ｙｕａｎ，ＺＨＡＮＧＳｉ唱ｚｈｉ．Ａｐｐｌｉｃａｔｉｏｎｏｆｃｏｍ唱
ｂｉｎｉｎｇｗａｔｅｒｓｈｅｄａｎｄｆａｓｔｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｉｎｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ
表１ 传统ＦＣＭ与本文算法的运行时间
算法本文算法ＦＣＭ
模拟脑图运行时间／ｓ
０．５７８０１．１２５０
Ｌｅｎａ图运行时间／ｓ
１．５６３０５．９０６０
噪声图运行时间／ｓ
０．７８２０１．１７２０
［Ｃ］／／Ｐｒｏｃｏｆｔｈｅ２ｎｄＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｕｔｅｒＭｏｄｅ唱ｌｉｎｇａｎｄＳｉｍｕｌａｔｉｏｎ．ＷａｓｈｉｎｇｔｏｎＤＣ：ＩＥＥＥＣｏｍｐｕｔｅｒＳｏｃｉｅｔｙ，２０１０：
１７０唱１７４．
［５］黄展鹏，易法令，周苏娟，等．基于数学形态学和区域合并的医学
ＣＴ图像分割［Ｊ］．计算机应用研究，２０１０，２７（１１）：１１９唱１２１．
从实验结果可以看出，本文提出的算法具有如下优点：ａ）利用粒子群优化算法从分水岭分割出的小区域中找出满足新的适应度函数的最优粒子，从而实现了初始聚类中心的较优选取；ｂ）改进了模糊聚类的目标函数，综合考虑了每个小区域的波动和面积，使算法具有较强的鲁棒性。由于在进行模糊聚类时并不是对每个像素进行聚类，而是对分水岭分割后的每个小区域进行聚类，大大减少了模糊聚类的迭代次数，提高了图像
（上接第４７７２页）
［６］ＷＡＮＧＹａｎｇ唱ｘｉａｎｇ，ＢＵＪｕａｎ．Ａｆａｓｔａｎｄｒｏｂｕｓｔｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ
ｕｓｉｎｇＦＣＭｗｉｔｈｓｐａｔｉａｌｉｎｆｏｒｍａｔｉｏｎ［Ｊ］．ＤｉｇｉｔａｌＳｉｇｎａｌＰｒｏｃｅｓｓｉｎｇ，
２００９，１１（７）：１唱１０．
［７］蒲蓬勃，王鸽，刘太安．基于粒子群优化的模糊Ｃ唱均值聚类改进
算法［Ｊ］．计算机工程与设计，２００８，２９（１６）：４２７７唱４２７９．［８］朱敏琛，魏祯．一种基于粒子群的模糊聚类图像分割算法［Ｊ］．福
州大学学报：自然科学版，２０１０，３８（１）：３２唱３５．
ｈｕｍａｎｍｏｔｉｏｎ［Ｊ］．ＡＣＭＴｒａｎｏｎＧｒａｐｈｉｃｓ，２００６，２５（３）：８８９．［Ｃ］／／ＰｒｏｃｏｆＷＳＣＧ．［Ｓ．ｌ．］：ＣｉｔｅＳｅｅｒ，２００２：２０３唱２０８．
［５］ＧＵＳＫＯＶＩ，ＫＬＩＢＡＮＯＶＳ，ＢＲＹＡＮＴＢ．Ｔｒａｃｋａｂｌｅｓｕｒｆａｃｅｓ［Ｃ］／／
ｍａｔｉｏｎ．Ｓｗｉｔｚｅｒｌａｎｄ：ＥｕｒｏｇｒａｐｈｉｃｓＡｓｓｏｃｉａｔｉｏｎＡｉｒｅｌａＶｏｌｌｅ，２００３：ＰｒｏｃｏｆＡＣＭＳＩＧＧＲＡＰＨ／ＥｕｒｏｇｒａｐｈｉｃｓＳｙｍｐｏｓｉｕｍｏｎＣｏｍｐｕｔｅｒＡｎｉ唱
３ 结束语
本文提出了基于块匹配的动态变形表面三维重建的方法。模拟实验和真实数据实验都验证了该方法的性能和有效性。该方法具有较强的鲁棒性。首先，将变形表面分为多个小的图像块，每个图像块单独进行处理，可以避免一个块的错误影响到其他块；另外，采用局部三维拓扑结构和ＮＣＣ两种方法进行错误检测，可检测出自遮挡和匹配错误的块，并对匹配错误的块重新优化，从而减少错误的发生。但是本文没有研究如何解决自遮挡问题，只能丢弃这类块。下一步研究如何解决自遮挡问题，以及如何扩展到多个相机的情况下。参考文献：
［１］ＳＩＦＡＫＩＳＥ，ＮＮＥＥＲＯＶＩ，ＦＥＤＫＩＷＲ．Ａｕｔｏｍａｔｉｃｄｅｔｅｒｍｉｎａｔｉｏｎｏｆ
ｆａｃｉａｌｍｕｓｃｌｅａｃｔｉｖａｔｉｏｎｓｆｒｏｍｓｐａｒｓｅｍｏｔｉｏｎｃａｐｔｕｒｅｍａｒｋｅｒｄａｔａ［Ｊ］．ＡＣＭＴｒａｎｓｏｎＧｒａｐｈｉｃｓ，２００５，２４（３）：４１７唱４２５．
［４］ＧＵＳＫＯＶＩ，ＺＨＵＫＯＶＬ．Ｄｉｒｅｃｔｐａｔｔｅｒｎｔｒａｃｋｉｎｇｏｎｆｌｅｘｉｂｌｅｇｅｏｍｅｔｒｙ
２５１唱２５７．
［６］ＳＣＨＯＬＺＶ，ＭＡＧＮＯＲＭ．Ｍｕｌｔｉ唱ｖｉｅｗｖｉｄｅｏｃａｐｔｕｒｅｏｆｇａｒｍｅｎｔｍｏ唱
ｔｉｏｎ［Ｃ］／／ＰｒｏｃｏｆＩＥＥＥＷｏｒｋｓｈｏｐｏｎＣｏｎｔｅｎｔＧｅｎｅｒａｔｉｏｎａｎｄＣｏｄｉｎｇ２００６：１唱４．
ｆｏｒ３ＤＴｅｌｅｖｉｓｉｏｎ．Ｎｅｔｈｅｒｌａｎｄｓ：ＴｅｃｈｎｉｓｏｈｅＵｎｉｖｅｒｓｉｔｅｉｔＥｉｎｄｈｏｖｅｎ，
［７］ＷＨＩＴＥＲ，ＣＲＡＮＥＫ，ＦＯＲＳＹＴＨＤ．Ｃａｐｔｕｒｉｎｇａｎｄａｎｉｍａｔｉｎｇｏｃ唱
ｃｌｕｄｅｄｃｌｏｔｈ［Ｊ］．ＡＣＭＴｒａｎｓｏｎＧｒａｐｈｉｃｓ，２００７，２６（３）：３４．
［８］ＢＲＯＸＴ，ＢＲＵＨＮＡ，ＰＡＰＥＮＢＲＧＮ，ｅｔａｌ．Ｈｉｇｈａｃｃｕｒａｃｙｏｐｔｉｃａｌ
ｆｌｏｗｅｓｔｉｍａｔｉｏｎｂａｓｅｄｏｎａｔｈｅｏｒｙｆｏｒｗａｒｐｉｎｇ［Ｃ］／／ＰｒｏｃｏｆＥＣＣＶ．［９］
Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ唱Ｖｅｒｌａｇ，２００４：２５唱３６．
ＯＧＡＬＥＡ，ＡＬＯＩＭＯＮＯＳＹ．Ａｒｏａｄｍａｐｔｏｔｈｅｉｎｔｅｇｒａｔｉｏｎｏｆｅａｒｌｙ
［２］ＢＩＣＫＥＬＢ，Ｂ橃ＣＨＥＲＭ，ＯＴＡＤＵＹＭ，ｅｔａｌ．Ｃａｐｔｕｒｅａｎｄｍｏｄｅｌｉｎｇ
ｏｆｎｏｎ唱ｌｉｎｅａｒｈｅｔｅｒｏｇｅｎｅｏｕｓｓｏｆｔｔｉｓｓｕｅ［Ｊ］．ＡＣＭＴｒａｎｏｎＧｒａｐｈｉｃｓ，２００９，２８（３）：１唱９．
［３］ＰＡＲＫＳ，ＨＯＤＧＩＮＳＪ．Ｃａｐｔｕｒｉｎｇａｎｄａｎｉｍａｔｉｎｇｓｋｉｎｄｅｆｏｒｍａｔｉｏｎｉｎ
２００７，７２（１）：９唱２５．
ｖｉｓｕａｌｍｏｄｕｌｅｓ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＶｉｓｉｏｎ，
［１０］呼艳，耿国华，王小凤，等．一种用于未标定图像三维重建的立体
匹配算法［Ｊ］．计算机应用研究，２０１０，２７（１０）：３９６４唱３９６７．
第２８卷第１２期２０１１年１２月
计算机应用研究
ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ
Ｖｏｌ畅２８Ｎｏ畅１２Ｄｅｃ畅２０１１
基于分水岭和改进的模糊聚类图像分割
龚 劬，姚玉敏
（重庆大学数学与统计学院，重庆４０１３３１）
倡
摘 要：针对模糊Ｃ唱均值聚类算法需预先给出初始聚类中心、未考虑邻域信息、计算复杂度高等缺点，提出了一种基于分水岭和改进的模糊聚类图像分割方法。该方法首先利用分水岭分割方法对原图像进行预分割，然后利用粒子群的全局寻优能力从预分割的小区域中搜索出较为准确的初始聚类中心；最后，在对小区域进行模糊聚类时，建立了包含邻域信息的聚类目标函数。实验表明，该方法分割速度快、抗噪能力强，实现了图像的较优分割。
关键词：分水岭算法；粒子群算法；模糊聚类；图像分割
中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１００１唱３６９５（２０１１）１２唱４７７３唱０３ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．１２．１００
ＩｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎｂａｓｅｄｏｎｗａｔｅｒｓｈｅｄａｎｄｉｍｐｒｏｖｅｄｆｕｚｚｙＣ唱ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇ
（ＣｏｌｌｅｇｅｏｆＭａｔｈｅｍａｔｉｃｓ＆Ｓｔａｔｉｓｔｉｃｓ，ＣｈｏｎｇｑｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ４０１３３１，Ｃｈｉｎａ）
ＧＯＮＧＱｕ，ＹＡＯＹｕ唱ｍｉｎ
Ａｂｓｔｒａｃｔ：ＩｎｏｒｄｅｒｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｓｉｎＦＣＭ（ｆｕｚｚｙＣ唱ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇ）ｓｕｃｈａｓｔｈｅｏｒｉｇｉｎａｌｃｌｕｓｔｅｒｃｅｎｔｅｒｓｔｏｂｅｇｉｖｅｎｉｎａｄｖａｎｃｅ，ｎｏｔｃｏｎｓｉｄｅｒｉｎｇｎｅｉｇｈｂｏｒｉｎｆｏｒｍａｔｉｏｎａｎｄｈｉｇｈｃｏｍｐｌｅｘｉｔｙ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｎｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎｂａｓｅｄｏｎｗａ唱ｔｅｒｓｈｅｄａｎｄｉｍｐｒｏｖｅｄＦＣＭ．Ｄｉｖｉｄｉｎｇｉｍａｇｅｗｉｔｈｔｈｅｈｅｌｐｏｆｗａｔｅｒｓｈｅｄａｌｇｏｒｉｔｈｍ，ａｎｄｇａｉｎｅｄｔｈｅｐｒｉｍａｒｙｒｅｓｕｌｔｓ．ＩｔｍａｄｅｆｕｌｌｕｓｅｏｆｔｈｅａｂｉｌｉｔｙｏｆｇｌｏｂａｌｏｐｔｉｍｉｚａｔｉｏｎＰＳＯ（ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ）ｔｏｏｂｔａｉｎｔｈｅａｃｃｕｒａｔｅｏｒｉｇｉｎａｌｃｌｕｓｔｅｒｃｅｎｔｅｒｓｏｆＦＣＭ．Ｉｔｈａｄｂｅｅｎｅｓｔａｂｌｉｓｈｅｄａｎｏｖｅｌｏｂｊｅｃｔｉｖｅｆｕｎｃｔｉｏｎｗｈｉｃｈｃｏｎｔａｉｎｅｄｎｅｉｇｈｂｏｒｉｎｆｏｒｍａｔｉｏｎ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｉｓｍｅｔｈｏｄｈａｓｈｉｇｈｅｒｓｅｇｍｅｎｔａｔｉｏｎｓｐｅｅｄａｎｄｓｔｒｏｎｇｅｒａｎｔｉ唱ｎｏｉｓｅｐｒｏｐｅｒｔｙ，ａｎｄｉｔｒｅａｌｉｚｅｓｓｉｇｎｉｆｉｃａｎｔｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：ｗａｔｅｒｓｈｅｄａｌｇｏｒｉｔｈｍ；ＰＳＯａｌｇｏｒｉｔｈｍ；ｆｕｚｚｙｃｌｕｓｔｅｒｉｎｇ；ｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ
０ 引言
图像分割
［１］
图像进行预分割；然后利用粒子群的全局寻优能力
［４］
从预分
割的小区域中搜索出较为准确的初始聚类中心；最后利用改进
是模式识别和计算机视觉中的重要研究课
目标函数的模糊聚类算法对分水岭分割后的小区域聚类，减少了迭代次数，提高了分割速度，实现了图像的较优分割。
题，也是图像处理的经典难题之一，近几十年来涌现出了大量不同的图像分割方法，但是至今仍然没有一个通用且有效的图像分割方法能满足不同的需求。分水岭分割
［２］
是一种基于区
１ 分水岭变换算法
分水岭算法是一种区域提取算法，最早由Ｂｅｕｃｈｅｒ和Ｍｅｙｅｒ将其引入到图像分割领域，由于算法实现过程简单有效，现已成为广泛使用的图像分割工具。分水岭算法是一种数学扑地貌，图像中每一点像素值都表示该点的海拔高度，每一个局部极小值及其影响区域均称为集水盆，而集水盆的边界则形成分水岭
［５］
域的图像分割方法，它以快速、有效、准确的分割结果越来越得到人们的重视，但是它本身存在严重的过分割现象。目前主要有两类方法解决分水岭的过分割问题，第一类属于预处理，它是基于标记提取的分水岭分割算法；第二类属于后处理，针对分水岭分割后的结果，根据某种准则进行区域合并。本文主要是研究第二类方法，利用模糊Ｃ唱均值聚类算法对过分割的图像进行后续处理。由Ｄｕｎｎ提出后经Ｂｅｚｄｅｋ推广的模糊Ｃ唱均值（ＦＣＭ）聚类算法
［３］
形态学上的分割方法，其基本思想是把图像看做测地学上的拓
。分水岭算法具有区域增长算法的优势，区域边
作为一种无监督聚类算法已成功应用于界形成了一个封闭、连接的集合，并且具有空间一致性，同时充分利用了梯度操作捕获的边缘信息。其具体算法如下：的变化情况，在灰度值变化较大的边缘具有较大的梯度值，而在灰度值均匀的区域内部具有较小的梯度值。一幅图像ｆ的形态梯度图像定义为膨胀变换减去腐蚀变换：
ｇｒａｄｆ＝ｆ⊕ｂ－ｆΘｂ
（１）
图像分析、医疗诊断、目标识别和图像分割等领域。基于ＦＣＭ聚类的图像分割算法比原始的硬分割算法能保留更多的原始图像信息，但是传统的ＦＣＭ算法没有考虑邻域信息，并且在聚类前必须人为指定初始聚类中心，如果初始聚类中心选择不当，容易使该算法陷入局部最优，传统的ＦＣＭ算法计算量较大。为了弥补上述不足，本文提出一种基于分水岭和改进的模糊聚类图像分割算法。该方法首先利用分水岭分割方法对原
ａ）计算形态梯度图像。形态梯度图像反映了图像中灰度
其中：⊕表示膨胀运算；Θ表示腐蚀运算；ｂ为结构元素，结构
收稿日期：２０１１唱０５唱１３；修回日期：２０１１唱０６唱１７ 基金项目：中央高校基金资助项目（ＣＤＪＸＳ１１１０００３２）
作者简介：龚劬（１９６３唱），女，四川人，教授，硕导，博士，主要研究方向为图论、小波分析和图像分析；姚玉敏（１９８２唱），女，山东菏泽人，硕士研究生，主要研究方向为图像处理（ｌｄｙｙｍｈ＠１２６．ｃｏｍ）．
元素不能取太大，否则会将灰度变化剧烈的小区域过滤掉。
法中的梯度操作对噪声敏感ｂ）将梯度图像输入分水岭算法产生分割结果，容易对图像产生过分割。分水岭算
，并且不能将图像中有意义的区域表示出来。所以，必须对过分割结果进行合并，模糊Ｃ唱均值聚类算法是解决这一问题的有效方法。
２ ＦＣＭ算法对过分割图像的处理
２畅１ 传统的ＦＣＭ算法
设Ｉ＝｛ｆ（ｉ，ｊ），０≤ｉ＜Ｍ，０≤ｊ＜Ｎ｝为数据集，ｃ为聚类数
目，则聚类目标函数可写成
Ｊ（Ｕ，Ｖ）＝∑∑ｃ
（ｕｋｍ
２
ｉ，ｊｋ＝１
（ｉ，ｊ））（ｄｋ（ｉ，ｊ））
（２）
其中：Ｕ＝［ｕｋ（ｉ，ｊ）］为模糊分类矩阵，ｕｋ（ｉ，ｊ）是ｆ（ｉ，ｊ）对于第ｋ类的隶属度函数，且满足０≤ｕｃ
ｋ（ｉ，ｊ）≤１和ｋ∑＝１ｕｋ（ｉ，ｊ）＝１；Ｖ＝［ｖ１，ｖ２，…，ｖｃ］为聚类中心集合；ｍ∈［１，∞）是一个控制聚类结果的权指数；ｄｋ（ｉ，ｊ）为ｆ（ｉ，ｊ）到聚类中心ｖｋ的距离，ｄｋ（ｉ，ｊ）＝‖ｆ（ｉ，ｊ）－ｖｋ‖。ＦＣＭ算法就是通过迭代确定隶属度函数和聚类中心，使目标函数取最小。利用拉格朗日乘数法求解，可获得隶属度函数和聚类中心的迭代公式
［６］
为
ｕｋ（ｉ，ｊ）＝１
ｃ
（３）
ｐ∑＝１
（ｄｋ（ｉ，ｊ）／
ｄｐ（ｉ，ｊ））２／（ｍ－１）
ｖ∑ｋ＝
ｉ，ｊ
（ｕｋ（ｉ，ｊ））ｍｆ（ｉ，ｊ）
∑（４）
ｉ，ｊ
（ｕｋ（ｉ，ｊ））ｍ
２畅２ 初始聚类中心的确定
始聚类中心ＰＳＯ算法的全局寻优ＦＣＭ算法的核心是最优初始聚类中心的确定。
、快速收敛的优点
［７］
来确定模糊聚类的初
，本文利用
设经过分水岭分割之后，整幅图像被分成Ｍ个大小不同的小区域Ｒｉｉ＝１，２，…，Ｍ，ｍｉ，ｊ表示区域Ｒｉ的均值，在利用ＰＳＯ算法寻找初始聚类中心时，将聚类中心作为ＰＳＯ算法中的粒子进行编码
［８］
。粒子由ｃ个聚类中心组成，即ｃ个聚类中心按顺序排列构成一个粒子，对任一粒子编码如下：ｘｉ＝ｘｉ１，ｘｉ２，ｘｉ３，…，ｘｉｃ，其中ｘｉｊ表示第ｉ种聚类方式中的第ｊ个聚类中心。其适应值用ｆｘｉ表示，它经历过的最佳位置表示为Ｐｂｅｓｔｐｉ１，ｐｉ２，…，ｐｉｋ，粒子ｘｉ的速度用Ｖｉｖｉ１，ｖｉ２，…，ｖｉｋ表示。当前组成群体的所有粒子经历过的最佳位置用符号Ｇｂｅｓｔ表示，则ＧｂｅｓｔｇＢ１，ｇＢ２，…，ｇＢｋ，对每一次迭代，粒子ｘｉ在ｄ维（１≤ｄ≤ｋ）空间的运动遵循如下方程进行变化：
ｖｉｄｔ＋１＝ｗｖｉｄｔ＋ｃ１ｒ１ｐｉｄｔ－ｘｉｄｔ
＋
ｃ２ｒ２ｇＢｄｔ－ｘｉｄｔ（５）ｘｉｄｔ＋
１＝ｘｉｄｔ＋ｖｉｄｔ＋１（６）
如果粒子的规模为ｎ就代表有ｎ种聚类方式，对每个粒子的评价，本文定义了新的适应度函数为
Ｍｆｘ∑∑Ｃ
ｕ２ｉ
＝
ｊｉｊ
Ｍ
ｉ（７）
如果聚类效果越好，则粒子适应度ｆｘｉ就越高，最后从中找到一种最好的聚类方式，即为模糊聚类的初始聚类中心。２畅３ 改进的ＦＣＭ聚类图像分割
经过分水岭分割之后，整幅图像被分成Ｍ个大小不同的
小区域Ｒｉｉ＝
１，２，…，Ｍ，ｍｉ，ｊ表示区域Ｒｉ的均值，样本点ｍｉ，ｊ到聚类中心ｖｊ的距离定义为
ｄ倡ｋ
ｉ，ｊ＝Ａｓｉ
ｉ
×ｍｉ，ｊ－ｖｊ（８）
其中：ｓｉ表示第ｉ个小区域的方差，Ａｉ表示第ｉ个小区域的面积。如果第ｉ个小区域的方差越大，并且面积越小，则它聚合其他小区域的可能性就越小。此距离充分考虑了每一个小区域的空间信息和邻域信息，利用新的距离计算方法，构造改进的聚类目标函数，即为
Ｊ倡（Ｕ，Ｖ）＝∑∑ｃ
＝１
（ｕｋ（ｉ，ｊ））ｍ２
ｉ，ｊｋ（ｄ倡ｋ（ｉ，ｊ））
（９）
根据新定义的目标函数和约束条件∑ｃ
ｋ＝１
ｕｋ（ｉ，ｊ）＝１，０≤ｕｋ
（ｉ，ｊ）≤１，由拉格朗日条件极值法可以得到隶属度矩阵和聚类中心的迭代公式为
ｕｋ（ｉ，ｊ）＝１
（１０）
ｐ∑ｃ
＝１
（ｄ倡ｋ（ｉ，ｊ）／ｄ倡ｐ（ｉ，ｊ））
２／（ｍ－１）
ｖ∑（ｕｋ（ｉ，ｊ））ｍｋ＝
ｉ，ｊｍ（ｉ，ｊ）∑（ｕｋ（ｉ，ｊ））ｍ
（１１）
ｉ，ｊ
算法实现的具体步骤如下：
重ｗ，ａ最大迭代次数）给出模糊指数Ｔ，ｍ迭代终止阈值，群体规模Ｎ，、ｃ２，惯性权ε学习因子＞０；
ｃ１的Ｍｂ个小区域）对原图像的梯度图像进行分水岭分割，计算每个小区域的灰度平均值，ｍ得到初分割后
（ｉ，ｊ），将每个小区域的均值ｍ（ｉ，ｊ）作为该区域的特征数据；
把每一种聚类方式作为一个粒子ｃ）从Ｍ个小区域的特征数据中初始化出，每个粒子含有Ｎ种聚类方式ｃ种属性，对，
Ｎ个粒子用粒子群优化算法进行寻优，得到最优的一个粒子，
即为模糊聚类的初始聚类中心；
ｄｅ）根据式ｆ））计算更新前后目标函数的改变量根据式（１０）（１１）更新隶属度矩阵更新聚类中心；
；ε，或者迭代次数大于最大迭代次数，则停止迭代，如果‖，Ｊｎｅｗ倡
－Ｊｏｌｄ倡
‖＜
否则转ｄ）。
３ 实验结果与分析
为了验证本文算法的有效性，选择了模拟脑图像和Ｌｅｎａ图像进行仿真实验。实验参数作如下设置：在粒子群算法的参数中惯性权重ｗ的设置通常是从０畅９线性减小到０畅２，学习因子ｃ１＝
２，ｃ２＝２，最大迭代次数为２００。在模糊Ｃ唱均值聚类算法的参数中模糊指数ｍ＝２，迭代终止阈值ε＝１×１０
－５
，最大
迭代次数Ｔ＝１００。其中，图１为模拟脑图分割结果对比，其聚类数目ｃ＝４；图２为Ｌｅｎａ图分割结果对比，其聚类数目ｃ＝５，（ａ）为原始图像，（ｂ）为传统ＦＣＭ分割结果，（ｃ）为本文算法分割结果，由（ｂ）（ｃ）两种分割结果明显看出本文分割算法优于传统ＦＣＭ分割算法。
为了验证本文算法的鲁棒性，下面对组合图像添加噪声，并分别用传统ＦＣＭ和本文的方法分割加噪声的组合图像，然后对两者的分割效果进行对比（其中本文方法的实验参数的选择如上所述）。从图３的分割效果可以看出，本文算法对噪声图像的分割效果明显优于传统ＦＣＭ分割方法。
另外，由于本文算法运用了微粒群优化算法来寻找较为准
分割的速度。
确的初始聚类中心，减少了迭代次数，提高了运算速度。表１为传统ＦＣＭ算法与本文算法的运行时间对比。
４ 结束语
本文综合利用了梯度分水岭算法、粒子群算法和基于区域的ＦＣＭ聚类算法。先用分水岭分割方法将图像分为Ｍ个小区域，用粒子群算法从中寻找最优的初始聚类中心，最后用改进目标函数的ＦＣＭ聚类方法对相似区域进行合并，充分考虑了空间邻域信息，减少了迭代次数，提高了运算速度，增强了分割的鲁棒性。本算法充分利用了先分后聚的思想，实现了图像的较优分割。参考文献：
［１］李艳灵，沈铁．基于空间邻域信息的ＦＣＭ图像分割算法［Ｊ］．华中
科技大学学报：自然科学版，２００９，３７（６）：５６唱５９．
［２］李春月，李峰，曹鹏，等．基于分水岭变换和ＦＣＭ的图像分割［Ｊ］．
计算机工程与科学，２００９，３１（１２）：５６唱５７．
［３］王士龙，万磊，唐旭东．一种基于直方图改进的ＦＣＭ聚类水下图
像分割算法［Ｃ］／／第２９届中国控制会议．２０１０：２９唱３１．
［４］ＹＡＮＧＷｅｎ唱ｌｉ，ＺＥＮＧＺｈｉ唱ｙｕａｎ，ＺＨＡＮＧＳｉ唱ｚｈｉ．Ａｐｐｌｉｃａｔｉｏｎｏｆｃｏｍ唱
ｂｉｎｉｎｇｗａｔｅｒｓｈｅｄａｎｄｆａｓｔｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｉｎｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ
表１ 传统ＦＣＭ与本文算法的运行时间
算法本文算法ＦＣＭ
模拟脑图运行时间／ｓ
０．５７８０１．１２５０
Ｌｅｎａ图运行时间／ｓ
１．５６３０５．９０６０
噪声图运行时间／ｓ
０．７８２０１．１７２０
［Ｃ］／／Ｐｒｏｃｏｆｔｈｅ２ｎｄＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｕｔｅｒＭｏｄｅ唱ｌｉｎｇａｎｄＳｉｍｕｌａｔｉｏｎ．ＷａｓｈｉｎｇｔｏｎＤＣ：ＩＥＥＥＣｏｍｐｕｔｅｒＳｏｃｉｅｔｙ，２０１０：
１７０唱１７４．
［５］黄展鹏，易法令，周苏娟，等．基于数学形态学和区域合并的医学
ＣＴ图像分割［Ｊ］．计算机应用研究，２０１０，２７（１１）：１１９唱１２１．
从实验结果可以看出，本文提出的算法具有如下优点：ａ）利用粒子群优化算法从分水岭分割出的小区域中找出满足新的适应度函数的最优粒子，从而实现了初始聚类中心的较优选取；ｂ）改进了模糊聚类的目标函数，综合考虑了每个小区域的波动和面积，使算法具有较强的鲁棒性。由于在进行模糊聚类时并不是对每个像素进行聚类，而是对分水岭分割后的每个小区域进行聚类，大大减少了模糊聚类的迭代次数，提高了图像
（上接第４７７２页）
［６］ＷＡＮＧＹａｎｇ唱ｘｉａｎｇ，ＢＵＪｕａｎ．Ａｆａｓｔａｎｄｒｏｂｕｓｔｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ
ｕｓｉｎｇＦＣＭｗｉｔｈｓｐａｔｉａｌｉｎｆｏｒｍａｔｉｏｎ［Ｊ］．ＤｉｇｉｔａｌＳｉｇｎａｌＰｒｏｃｅｓｓｉｎｇ，
２００９，１１（７）：１唱１０．
［７］蒲蓬勃，王鸽，刘太安．基于粒子群优化的模糊Ｃ唱均值聚类改进
算法［Ｊ］．计算机工程与设计，２００８，２９（１６）：４２７７唱４２７９．［８］朱敏琛，魏祯．一种基于粒子群的模糊聚类图像分割算法［Ｊ］．福
州大学学报：自然科学版，２０１０，３８（１）：３２唱３５．
ｈｕｍａｎｍｏｔｉｏｎ［Ｊ］．ＡＣＭＴｒａｎｏｎＧｒａｐｈｉｃｓ，２００６，２５（３）：８８９．［Ｃ］／／ＰｒｏｃｏｆＷＳＣＧ．［Ｓ．ｌ．］：ＣｉｔｅＳｅｅｒ，２００２：２０３唱２０８．
［５］ＧＵＳＫＯＶＩ，ＫＬＩＢＡＮＯＶＳ，ＢＲＹＡＮＴＢ．Ｔｒａｃｋａｂｌｅｓｕｒｆａｃｅｓ［Ｃ］／／
ｍａｔｉｏｎ．Ｓｗｉｔｚｅｒｌａｎｄ：ＥｕｒｏｇｒａｐｈｉｃｓＡｓｓｏｃｉａｔｉｏｎＡｉｒｅｌａＶｏｌｌｅ，２００３：ＰｒｏｃｏｆＡＣＭＳＩＧＧＲＡＰＨ／ＥｕｒｏｇｒａｐｈｉｃｓＳｙｍｐｏｓｉｕｍｏｎＣｏｍｐｕｔｅｒＡｎｉ唱
３ 结束语
本文提出了基于块匹配的动态变形表面三维重建的方法。模拟实验和真实数据实验都验证了该方法的性能和有效性。该方法具有较强的鲁棒性。首先，将变形表面分为多个小的图像块，每个图像块单独进行处理，可以避免一个块的错误影响到其他块；另外，采用局部三维拓扑结构和ＮＣＣ两种方法进行错误检测，可检测出自遮挡和匹配错误的块，并对匹配错误的块重新优化，从而减少错误的发生。但是本文没有研究如何解决自遮挡问题，只能丢弃这类块。下一步研究如何解决自遮挡问题，以及如何扩展到多个相机的情况下。参考文献：
［１］ＳＩＦＡＫＩＳＥ，ＮＮＥＥＲＯＶＩ，ＦＥＤＫＩＷＲ．Ａｕｔｏｍａｔｉｃｄｅｔｅｒｍｉｎａｔｉｏｎｏｆ
ｆａｃｉａｌｍｕｓｃｌｅａｃｔｉｖａｔｉｏｎｓｆｒｏｍｓｐａｒｓｅｍｏｔｉｏｎｃａｐｔｕｒｅｍａｒｋｅｒｄａｔａ［Ｊ］．ＡＣＭＴｒａｎｓｏｎＧｒａｐｈｉｃｓ，２００５，２４（３）：４１７唱４２５．
［４］ＧＵＳＫＯＶＩ，ＺＨＵＫＯＶＬ．Ｄｉｒｅｃｔｐａｔｔｅｒｎｔｒａｃｋｉｎｇｏｎｆｌｅｘｉｂｌｅｇｅｏｍｅｔｒｙ
２５１唱２５７．
［６］ＳＣＨＯＬＺＶ，ＭＡＧＮＯＲＭ．Ｍｕｌｔｉ唱ｖｉｅｗｖｉｄｅｏｃａｐｔｕｒｅｏｆｇａｒｍｅｎｔｍｏ唱
ｔｉｏｎ［Ｃ］／／ＰｒｏｃｏｆＩＥＥＥＷｏｒｋｓｈｏｐｏｎＣｏｎｔｅｎｔＧｅｎｅｒａｔｉｏｎａｎｄＣｏｄｉｎｇ２００６：１唱４．
ｆｏｒ３ＤＴｅｌｅｖｉｓｉｏｎ．Ｎｅｔｈｅｒｌａｎｄｓ：ＴｅｃｈｎｉｓｏｈｅＵｎｉｖｅｒｓｉｔｅｉｔＥｉｎｄｈｏｖｅｎ，
［７］ＷＨＩＴＥＲ，ＣＲＡＮＥＫ，ＦＯＲＳＹＴＨＤ．Ｃａｐｔｕｒｉｎｇａｎｄａｎｉｍａｔｉｎｇｏｃ唱
ｃｌｕｄｅｄｃｌｏｔｈ［Ｊ］．ＡＣＭＴｒａｎｓｏｎＧｒａｐｈｉｃｓ，２００７，２６（３）：３４．
［８］ＢＲＯＸＴ，ＢＲＵＨＮＡ，ＰＡＰＥＮＢＲＧＮ，ｅｔａｌ．Ｈｉｇｈａｃｃｕｒａｃｙｏｐｔｉｃａｌ
ｆｌｏｗｅｓｔｉｍａｔｉｏｎｂａｓｅｄｏｎａｔｈｅｏｒｙｆｏｒｗａｒｐｉｎｇ［Ｃ］／／ＰｒｏｃｏｆＥＣＣＶ．［９］
Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ唱Ｖｅｒｌａｇ，２００４：２５唱３６．
ＯＧＡＬＥＡ，ＡＬＯＩＭＯＮＯＳＹ．Ａｒｏａｄｍａｐｔｏｔｈｅｉｎｔｅｇｒａｔｉｏｎｏｆｅａｒｌｙ
［２］ＢＩＣＫＥＬＢ，Ｂ橃ＣＨＥＲＭ，ＯＴＡＤＵＹＭ，ｅｔａｌ．Ｃａｐｔｕｒｅａｎｄｍｏｄｅｌｉｎｇ
ｏｆｎｏｎ唱ｌｉｎｅａｒｈｅｔｅｒｏｇｅｎｅｏｕｓｓｏｆｔｔｉｓｓｕｅ［Ｊ］．ＡＣＭＴｒａｎｏｎＧｒａｐｈｉｃｓ，２００９，２８（３）：１唱９．
［３］ＰＡＲＫＳ，ＨＯＤＧＩＮＳＪ．Ｃａｐｔｕｒｉｎｇａｎｄａｎｉｍａｔｉｎｇｓｋｉｎｄｅｆｏｒｍａｔｉｏｎｉｎ
２００７，７２（１）：９唱２５．
ｖｉｓｕａｌｍｏｄｕｌｅｓ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＶｉｓｉｏｎ，
［１０］呼艳，耿国华，王小凤，等．一种用于未标定图像三维重建的立体
匹配算法［Ｊ］．计算机应用研究，２０１０，２７（１０）：３９６４唱３９６７．