机器视觉原理与应用 课件 第11、12章 主动轮廓与跟踪运动、聚类分析1

第11章主动轮廓与跟踪运动11.1主动轮廓模型11.2弹性形状模型11.3高斯混合模型 11.3.1高斯混合模型分布特征 11.3.2高斯混合模型的参数极大似然估计 11.3.3随机梯度算法 11.3.4EM算法11.4跟踪运行特征 11.4.1基于高斯混合模型的背景建模 11.4.2基于核函数的跟踪第11章主动轮廓与跟踪运动11.5基于视觉的运动特征提取与描述 11.5.1运动形状描述 11.5.2运动形状检测11.1主动轮廓模型主动轮廓也称蛇模型（activecontourorsnakes）是与特征提取完全不同的方法。主动轮廓是将目标特征，即待提取特征包围起来的一组点。类似于用一个气球找出形状：气球放在形状外部，将形状包围在内。然后把气球中的空气放出，使它慢慢变小，当气球停止缩小时，即找出了形状，此时气球与形状完全拟合。通过这种方式，主动轮廓对一组点进行排列，将目标形状包围在内以便对其进行描述。11.1主动轮廓模型在目标特征的外部设置一个初始轮廓，然后对其进行演变并将目标特征包围在内。主动轮廓模型采用能量最小化方法进行处理。目标特征是能量泛函的最小值。该能量泛函不只包含边界信息，还包括控制轮廓伸缩和弯曲的特性。通过这种方式蛇模型表示其自身特性(比如弯曲和拉伸能力)与图像特性(比如边缘强度)之间的一种折中。因此，能量泛函是轮廓内部能量

、约束能量

以及图像能量

的相加函数，它们是组成蛇模型

的一组点，即蛇模型中所有点的x和y坐标。假设

是蛇模型的正规化长度，那么能量泛函是该蛇模型的所有函数的积分。因此，能量泛函

为（11-1）11.1主动轮廓模型上式中，

，

和

分别是轮廓点的x和y坐标，

，内部能量

决定蛇模型的自然变化，从而决定蛇模型所有点的排列；图像能量

引导蛇模型选择低层次特征(如边缘点)；约束能量

给出高层次信息以控制蛇模型的演变。蛇模型的目标就是通过式(11-1)的最小化来进行求解。新的蛇模型轮廓是指那些比初始点能量更低并与目标特征匹配更好的点，蛇模型就是从这些初始点演变而来的。通过这种方式，选择一组点

满足式（11-2）

(11-2)11.1主动轮廓模型能量泛函

表示为蛇模型函数以及图像的形式。根据各自所选的权重系数，这些函数构成蛇模型能量。通过这种方式，曲线内部能量

定义为轮廓周围一阶和二阶导数的加权和，如式（11-3）所示。

(11-3)一阶微分

表示由伸缩而产生的弹性能量，由于该微分的值越大意味着这个轮廓区域内的变化率越大。二阶微分

表示因弯曲而产生的能量，即曲率能量。由于受点间隔影响，使用权值

控制弹性能量贡献；受点变动影响，使用权值

控制曲率能量贡献。α和β的取值决定蛇模型最终形状。α取低值表示点的间隔变化幅度大，而取高值则表明蛇模型得到均匀分隔的轮廓点。β取低值意味着曲率不是最小值，并且轮廓在其边界上形成角点，而取高值表示预先设定蛇模型为光滑的轮廓。上述情形是轮廓自身的特性，它只是蛇模型自身特征与图像检测特征之间的部分折中。11.1主动轮廓模型图像能量

引导蛇模型提取低层次特征，比如亮度或边缘数据，目的是选取具有最小贡献的特征。式（11-1）表明线、边缘和端点可以作用于能量函数，这些能量分别标记为

，

和

，并且分别通过权重系数

，和

来控制。因此，图像能量如式（11-4）所示。

(11-4)线能量可以设为特定点的图像亮度。如果黑色比白色取值低，那么将暗特征提取为蛇模型。改变

的符号可以将蛇模变成较亮的特征。边缘能量

利用边缘检测算子来计算，比如Sobel边缘检测算子输出的强度。端点能量包括层次图像轮廊的曲率，但是很少用到。最常用的是边缘能量。11.2弹性形状模型分析形状的方法主要关注的是图像数据的匹配。通常关注一个模型（即一个可以变形的模板或可以演变的形状）与单幅图像之间的匹配。主动轮廓是弹性的，但其演变实质上受局部曲率或边缘强度等局部特性的限制。那些泛函所赋予的参数值或可能范围可以通过学习所应用的同类图像数据库进行多方面测试，或根据经验进行选取。一个与此完全不同的方法是，考虑图像库中是否包含该形状的所有可能变化，比如外观或姿势，图像库可以形成一个该形状可能变化的模型。因此，如果把该模型作为一个整体约束条件，同时引导与最可能形状的匹配，那么可以得到一个可变形方法，通过对形状的可能变化进行统计来实现。上述方法称为弹性模板，利用从训练数据样例形成的整体形状约束。11.2弹性形状模型其中的主要新方法称为主动形状建模。该方法实质上是由点组成的形状模型：这些点的变化称为点分布模型。所选地标点在训练图像中进行标记，这组训练图像旨在得到形状的所有可能变化。每个点描述边界上的一个特定点，因此其顺序在标记过程中非常重要。这些样点的选择包括曲率高的位置（如眼睛角点）或弧长顶点，这样的地方对比度比较高（如眼睑上方）。对这些点的位置所产生的形状变化进行统计，可以描述形状的外观。实例应用包括在图像中找出人脸（如：自动人脸识别中的人脸检测）。脸部可以获得不同模型的唯一部位是虹膜上的圆圈，除非分辨率非常高，否则该部位区域非常小。脸部的其余部分由一些未知的形状组成，而这些形状随脸部表情的变化而变化。由此可见，由于我们得到一组形状和一个固定的相互关系，它们非常适合于将形状与分布结合在一起的方法，不过有些细节可能发生变化。这些细节变化正是主动形状模型所要得到的。11.2弹性形状模型如果选择的点非常多而且要用到很多训练图像，那么这样处理数据量非常大，即将有大量的点要处理，主成分分析可以将数据压缩成最重要项。主成分分析是一个非常成熟的数学工具。实质上，它对坐标系进行了旋转以便得到最大辨别能力：如果从两个不同的点观察一个事物，或许无法看到，但是如果从其中一个点进行观察，则可以看得非常清楚。此处要做的是：旋转坐标系以便从一堆杂乱的数据找出最重要的变化。已知N个训练样本的集合，每个样本为n个点的集合，对于第i个训练样本xi，有（11-5）11.2弹性形状模型式中，xki表示第i个训练样本中的第k个变量。如果将其应用于形状，每个元素取每个点的两个坐标。然后，对整个训练样本集合计算平均值，如式（11-6）所示。（11-6）于是根据平均值计算每个样本的偏差（11-7）这个差值说明每个样本与某点均值的距离。

协方差矩阵S表示所有差值与均值之间的距离，如式（11-8）所示。（11-8）11.2弹性形状模型该协方差矩阵的主成分分许显示这些样本数量，即其形状可能发生多少变化。事实上，形状的任何一个样例都可以近似为（11-9）式中，

表示第t个特征矢量矩阵，

表示相对应的权值失量，其中每个权值控制一个特征矢量的贡献。w的不同值给出不同的模型或形状。如假设这些变化在一个设定的范围内，新的模型或形状将与基础（平均）形状类似。这是因为变化模式是由（单位）特征矢量来表示的，如（11-10）式中，表示特征值，特征矢量具有正交性，因而（11-11）11.2弹性形状模型而且这些特征值是有序的，因而

。式中，最大特征值对应数据中的最重要变化模式。训练数据中的变化部分对应每个特征矢量，与相应的特征值成正比。由此可见，一组数量有限的特征值和特征矢量可以用来包括大部分数据。其余特征值和特征矢量对应数据中那些几乎不出现的变化模式（如高频率部分对图像的贡献，主要根据低频率分量对图像进行重构，同图像编码）。需要注意的是，为了对应用于新形状的训练集中贴有地标标记的点的统计进行检查，需要对这些点进行排序，从而得到确定的程序。11.2弹性形状模型应用过程（如找出被建模形状的实例）是利用迭代方法使模型和图像中相匹配点不断增多。这可以通过检测模型点周围区域以确定最佳近邻匹配来实现。该方法对数据的最佳拟合模型计算适当的平移、缩放、旋转和特征矢量。不断重复以上处理直到模型对数据收敛，这时参数几乎没有变化。由于只改变形状以便更好地拟合数据，并且形状受所期望的形状外观控制，所以这种模型被称为主动形状模型。将主动形状模型应用于找出脸部特征。该方法可以利用由粗到细的方式进行处理，即以低分辨率开始处理（使其快速进行），逐渐提高分辨率直到处理结果没有改进，即最终收敛。很显然，这样的方法不受特殊情形或背景中的其他特征所误导。它可以用来注册（自动找出人脸）或自动人脸识别（找出或描述人脸的特征）。该方法无法处理太粗劣的初始化，其初始位置并不需要非常靠近人脸。11.2弹性形状模型主动形状模型（ActiveShapeModel，ASM）已经应用于人险识别、医学图像分析，以及工业检查。相似理论被用来开发一种与纹理相关的新方法，称为主动外观模型（ActiveAppearancemodel，AAM）。主动外观模型也是将形状表示为一组地标点，并利用一组训练数据确定形状变化的可能范围。一个主要区别在于AAM显然包括纹理，并通过重复搜索处理对纹理进行匹配来更新模型参数，使地标点向图像点靠近。ASM和AAM的实质区别包括：●ASM利用的是点局部的纹理信息，而AAM利用的是整个区域的纹理信息。●ASM想要得到模型点与相应图像点之间的最小距离，而AAM想要得到合成模型与目标图像之间的最小距离。●ASM在当前点附近，尤其在垂直于边界的轮廓上进行搜索，而AAM只考虑当前位置的图像。11.2弹性形状模型研究表明，虽然ASM比AAM实现更快，但是AAM需要的地标点更少，而且收敛得到更好的效果，尤其以纹理的形式。我们期待弹性形状建模方面的这些方法得到进一步的发展。近来的研究关注的是处理遮挡的能力，改变三维（3D）朝向或姿势时都会出现遮挡。11.3.1高斯混合模型分布特征如果一个类中的模式分布在不同的聚类中，通过一个高斯模型去近似类条件分布是不合适的。比如说，图11-1a所示的情形，通过一个高斯模型去近似单峰模型分布，其结果是准确的估计。但是如图11-1b所示，如果用一个高斯模型去近似多峰模型分布，即使在训练样本足够多的情况下，其表现依旧会很差。定义高斯混合模型为：（11-12）高斯混合模型很适合这样的多峰模型分布。这里，

表示一个期望为

和方差协方差矩阵为

的高斯模型：（11-13）11.3.1高斯混合模型分布特征图11-1高斯模型的极大似然估计11.3.1高斯混合模型分布特征所以，高斯混合模型是m个高斯模型根据

加权线性组合而成。高斯混合模型的参数为：

高斯混合模型

如果要成为一个概率密度函数，就应该满足下面的条件：

同时

需要满足：（11-14）如图11-2所示的高斯混合模型的例子，通过多个高斯模型的线性组合，高斯混合模型能够表示一个多峰模型分布。11.3.1高斯混合模型分布特征 a)每个高斯分量b)高斯混合模型图11-2高斯混合模型11.3.1高斯混合模型分布特征mu=[12;-3-5];sigma=cat(3,[20;0.5],[10;01]);p=ones(1,2)/2;obj=gmdistribution(mu,sigma,p);ezsurf(@(x,y)pdf(obj,[xy]),[-1010],[-1010])

#Python调用MATLAB的m文件，高斯混合模型importmatlabimportmatlab.engine#importnumpyasnpeng=matlab.engine.start_matlab()eng.gmdistribution(nargout=0)input()#使图像保持

图11-3高斯混合模型的Python和Matla程序11.3.1高斯混合模型分布特征图11-4高斯混合模型三维图11.3.2高斯混合模型的参数极大似然估计高斯混合模型的参数可以用极大似然进行估计，似然公式为：（11-15）并且极大似然估计找到使其最大化的参数。当上述高斯混合模型的似然被最大化时，应该满足等式（11-16）的约束：（11-16）由于以上约束，的最大值不能通过简单的对似然求导并令导数等于0来得到。这里

被重新参数化为：（11-17）11.3.2高斯混合模型的参数极大似然估计其中

自动满足等式（11-14）的约束，它可以被学习得到。对于

最大似然解满足下面似然等式：（11-18）其中：表示d-维零向量，

表示d*d零矩阵。把等式（11-17）代入等式（11-15）中，对数似然被表示为：（11-19）11.3.2高斯混合模型的参数极大似然估计对上述的对数似然求关于

的偏导，得：（11-20）其中

被定义为

11.3.2高斯混合模型的参数极大似然估计同理，对上述的对数似然求关于

和

的偏导，可得：（11-21）（11-22）11.3.2高斯混合模型的参数极大似然估计令上述导数为零，最大似然解

，和满足(11-23)11.3.2高斯混合模型的参数极大似然估计其中

是样本

的第组成部分的决定因素（responsibility）:

（11-24）上述似然等式中的变量用很混乱和复杂的方式被定义和使用，目前还没有比较有效的方法能解决这个问题。下面，介绍了两种方法来找到数值解：一个是梯度方法，一个是算法。11.3.3随机梯度算法梯度方法是一种比较通用和简单的优化方法，如图11-5所示，它通过不停的迭代更新参数的方法来使得目标函数的梯度升高或者降低（在最小化的情况下）。如图11-6所示，详细描述了梯度上升算法执行过程。在宽松的假设条件下，梯度上升的解能保证是局部最优的，就好比一个局部山峰的峰顶，任何局部参数的更新，目标值也不会增加。梯度方法的一种随机变种是，随机选择一个样本，然后根据这个被选择的样本更新参数来上升梯度。这种随机方法被称作随机梯度算法，该算法也能找到局部最优解。注意（随机）梯度方法不仅要给出全局最优解而且还要给出一个局部最优解，如图11-5所示。此外，算法的性能依赖于步长的选择，且步长的大小在实际使用中很难选择。如果步长设置较大，那么梯度在刚开始的时候上升很快，但是可能会翻过最高点，如图11-7a所示。另一方面，如果步长设置减少，那么虽然能够找到最高点，但是在刚开始11.3.3随机梯度算法的时候梯度上升的速度会很慢，如图11-7b所示。为了克服这个问题，我们开始把步长设置较大，随后慢慢减少步长，这是比较有效果的，这就是模拟退火。但是，在实际使用的时候，初始步长的选择和步长的下降因子是不能直接确定的。为了减轻只能找到一个局部最优解的问题，实际上，设置不同的初始值多次运行梯度算法，根据最好的解来选择一个初始值是很有用的。图11-5梯度下降原理图11.3.3随机梯度算法图11-6梯度下降法给解

以适当的初值。对于选定的初值，计算出对数似然

的梯度：3.采用梯度上升的方式，对参数进行更新：4.重复上述

步计算，直到解

达到收敛精度为止。11.3.3随机梯度算法 a）太大 b）太小图11-7梯度下降过程步长设置11.3.4EM算法在梯度方法中调整步长的困难能够被算法克服.算法是在当输入仅仅部分可观察的情况下为了得到极大似然估计解而发展出来的。高斯混合模型的极大似然估计实际上也能被视为从不完全的数据中学习而来，并且EM算法能给出一种有效的方式来得到一个局部最优解。如图11-8描述的一样，EM算法是由E步和M步两部分组成。11.3.4EM算法对参数

进行初始化。

步：根据当前的参数

，可以计算出后验概率

：

步：从当前的后验概率

，对参数

进行更新：重复上述2-3步的计算。

图11-8EM算法11.3.4EM算法

E步和M步解释如下：

E步：当解为时，似然

的下界的等号能被取得：（11-25）注意：下界

需要通过不可观察的变量来计算期望得到，这也是为什么把这一步叫做（expectation）步。

M步：使下界

最大的可得：（11-26）如图11-9所示，通过E步和M步的迭代，对数似然的值增加了（准确说是对数似然是单调不减的）。11.3.4EM算法E步的下界是基于

不等式得到的：对于

，有（11-27）对于m=2，如图11-10所示，通过对数函数的凸性，我们可以很直观的理解式（11-27），

不等式被简化为：（11-28）11.3.4EM算法11.3.4EM算法对数似然

可以使用式（11-24）

来表达：（11-29）把公式（11-29）中的

和

不等式（11-27）联系起来，对数似然

的下界

可以表示为：（11-30）11.3.4EM算法当

时，式（11-30）等号成立，由式（11-24）得下界

为：（11-31）使下界

最大的在M步中应该满足：（11-32）11.3.4EM算法根据最大

可得：

（11-33）上述解释说明对数似然通过E步和M步迭代的时候是单调不减的。此外，EM算法被证明是可以找到一个局部最优解的。11.4.1基于高斯混合模型的背景建模为了快速和准确地提取背景，当图像中人物的衣服与背景类似、阴影的效果与fragmentary形态等检测时所出现的现象。通过对一系列图像进行处理来估计背景图像，即对每一幅新图像更新得到一个估计，如式（11-34）所示。（11-34）假定

，α为学习因子（

）。通过这种方式，一部分新图像被添加到背景图像中。这样，只需要恢复单一的背景图像。通过这个过程，他们走入或者走出，都会被检测到。但如果一个人准备走进一个场景然后停下来，他们将不会被检测到（学习因子所指的时刻），因为当他们停止时，将变为背景的一部分。因此，实际上人物确实有可能与背景混合。当新的物体出现在图像中时，它们可以被标记为背景（这种情况下它们被添加到背景图像中）或者前景（此时，对背景图像没有贡献）。使用高斯混合模型对背景进行建模，将运动对象从背景中分离出来11.4.1基于高斯混合模型的背景建模将背景建模为一个系统时，每个像素均有一个概率分布。许多运动的图像，因为有很多一致的背景，其概率分布会出现峰值，背景模型将会出现多个因子。因此，我们可以将其建模为混合概率分布。如图11-13所示，图11-13（a）是单一的高斯分布的情况，图11-13（b）显示了3个高斯分布（点线），概率分布是它们加在一起（实线）。很明显，由多个分布得到的分布具有更好的建模复杂背景的能力。11.4.1基于高斯混合模型的背景建模（a）单一的（高斯）分布

（b）多个分布图11-13高斯和混合高斯分布11.4.1基于高斯混合模型的背景建模单变量x的中心高斯分布g是均值和标准偏差的函数：（11-35）对于d维，多元高斯分布（multi-variateGaussiandistribution）G标记为（11-36）其中，为一般矩阵，d是多维x中变量的数目，是变量的均值，是d*d的协方差矩阵。给定一个假设：协方差矩阵缩减为一个对角阵（假设变量独立，那些反映相关性的反对角线元素为0），此时多元高斯模型简化为11.4.1基于高斯混合模型的背景建模（11-37）将k个高斯多元分布加起来为（11-38）其中，

是第j个分布的权值或者重要度。如果像素与任何的背景分布匹配，那么认为它是背景像素。背景模型是从B分布形成的，它按照排序满足：（11-39）其中，阈值T的值控制背景模型的分布数量。减少T值则增加分布能够形成部分背景模型的机会。11.4.1基于高斯混合模型的背景建模通过使用权值与方差的比率（

），将分布进行排序。选择具有高权值和小方差的分布。如果像素与前景分布匹配，或者不与背景分布匹配，则认为该像素是一个前景像素，属于运动目标。对于权值

，首先它们被设置为一个低的值，而每个分布的方差

则设置为一个大的值。然后，进行像素比较，并且在第一次迭代时像素不与任何分布匹配，因此变为一个新的分布。在第二次和后续的迭代时，更新第k个分布的权值（其中，

是它的先前的值）为（11-40）11.4.1基于高斯混合模型的背景建模其中，α控制学习率，即该方法适应背景数据变化的速度。对于匹配的分布，

。对于其余的分布，

。在该过程后，权值被归一化。然后，对于匹配的分布，更新均值

和方差

的值为（11-41）（11-42）其中（11-43）式（11-39）-式（11-43）中参数和T性能分析。首先，学习率α，它控制适应背景时迭代的次数。其次，阈值T，

，并且T值越大，它对于多模背景的适应能力越强。最后，每个混合的高斯分布的数量，以及选择的初始方差值。很自然地，高斯分布的个数少，对于计算量来说具有吸引力。11.4.1基于高斯混合模型的背景建模但是，复杂的背景需要较多的高斯分布个数。如果初始方差过大，当运动对象的颜色与背景类似时，这会增加它被标记为背景的机会。直到方差的估计收敛时。并且，方差值大，它要求更多的迭代。考虑到这种方法受到欢迎，自然出现了一些方法，对它的性能进行改进。一种明显的变化是采用不同的颜色空间：使用色调、饱和度、值/强度（HIS/HSV），而不是RGB颜色模型，受阴影的影响较小。11.4.2基于核函数的跟踪背景建模可以简化物体跟踪，如果不需要对背景做任何特殊处理，将会更有价值。由于现在的视频序列的帧率都很高，所以都能满足相邻两帧间变化很小。在满足了这个要求的基础上，可以完成基于梯度的物体定位和跟踪。基于核函数的跟踪是一种非常高效的实时跟踪方法，该方法基于如下过程：使用一个各向同性核函数来对物体在空间上施加一个掩膜，然后施加一个平滑相似函数，这样就将跟踪问题简化为在其前一帧的临近位置搜索最大相似度的问题，以下为基于核函数的物体跟踪。11.4.2基于核函数的跟踪首先，必须事先确定想要跟踪的目标特性，比如，从图像数据中估计出一个概率密度函数q。对于真实环境下的视频跟踪，一般情况都是彩色的，所以通常利用颜置于局部坐标系的中心，然后当前帧的目标候选置于y处。目标候选的特征描述可以使用一个概率密度函数

来刻画，它是从当前图像帧数据中估计出来的。为了使计算更高效，采用离散化的概率密函数，用m个区间的直方图表示。因此，目标模型

和目标候选

概率密度函数定义如下：（11-44）（11-45）11.4.2基于核函数的跟踪其中

；是和之间的相似度函数（11-46）对于一个跟踪任务，相似度函数与在前一帧已经确定了位置的目标出现在当前帧的位置y处的可能性相符。因此，对于待分析的帧序列，

的局部最优值就对应着目标在当前帧出现的位置。目标模型（targetmodel）从一个椭圆形的区域中导出，这个椭圆形区域首先被规范化到一个单位圆中来去除目标尺度的影响，包括n个像素的目标区域由规范化后的像素坐标表示；规范化使用单位圆的中心作为原点。然后使用一个单调递减的凸核函数K和一个轮廓函数k(x)来记录目标区域

满足

（11-47）11.4.2基于核函数的跟踪Comaniciu等人推荐使用Epanechnikov核函数。在处的每一个目标模型像素必须与其在量化后的特征空间上的一个索引

相关联，其索引函数是

。特征

的概率通过如下方式计算（11-48）其中是Kroneckerdelta函数（

for ；

其他），C是一个规范化常量（11-49）11.4.2基于核函数的跟踪在当前帧以y为中心的目标候选(targetcandidate)用规范化的像素位置集合

，

来表示，其中h表示具有与目标模型相同轮廊函数k(x)的核函数K的带宽。规范化过程是从包含目标模型的帧中继承来的。带宽定义了目标候选的尺度，因此也决定了当前帧在定位过程中需要分析的像素数目。特征

的概率

是（11-50）其中规范化常量为（11-51）11.4.2基于核函数的跟踪由于Ch不依赖于y，所以对于给定的核函数和带宽，它可以被事先计算出来。式（11-46）的相似度函数继承了所用核函数K的特性。选用一个平滑可微的核函数并利用爬山法来优化相似度函数。很明显，相似度函数是对目标和每个候选之间距离的一个度量指标。这两个分布之间的距离

可以通过巴氏（Bhattacharyya）系数评估p和q之间的相似度来估计（11-52）其中（11-53）11.4.2基于核函数的跟踪为了在当前帧找到目标最可能的位置，将式（11-52）的距离最小化，并且将式（11-53）的巴氏系数最大化。这个优化过程从目标在前一帧的位置出发，然后使用基于梯度的均值移位方法。当前帧中每一个独立跟踪步骤从目标模型在前一帧确定的位置y0处开始。模型本身是从跟踪序列的初始帧估计出来的。由于随着时间可能会发生变化，必须有一个可以更新的目标模型机制。为了初始化每一个跟踪过程，需要计算y0处于

处目标候选

的概率。在

附近的泰勒展开可以用式（11-54）近似。（11-54）11.4.2基于核函数的跟踪只要后续序列中目标候选

在初始

处不剧烈变化，上面就可以得到一个合理且紧凑的近似结果。注意

（或者大于一个小数）这个要求除了一些不符合的特征外，对于所有的

都是可以的。跟踪过程根据式（11-50）优化目标候选的位置。通过使用式（11-54），必须最大化式（11-55）右边的第二项，因为第一项和y无关。

（11-55）其中（11-56）11.4.2基于核函数的跟踪最大化第二项反映了在当前帧y处由核轮廓函数k(x)计算的作为权重的密度估计。使用式（11-57）均值移位过程可以以迭代的方式从

处开始找到最大值的位置。（11-57）其中

在

除了有限个点外均可微。11.4.2基于核函数的跟踪11.4.2基于核函数的跟踪11.4.2基于核函数的跟踪11.4.2基于核函数的跟踪11.5.1运动形状描述11.5.1运动形状描述11.5.1运动形状描述在行为识别领域，有相当多的(持续的)研究，并且伴随着标准数据集及评价标准。在运动分析与识别中，从图像序列中恢复人的姿态与运动可以被视为复原/跟踪问题。其中，行为的识别是一个分类问题。在人运动的全局表示中，行为被描述为一个整体,并且通过背景减/跟踪方法得到。另一种方法是使用局部特征，它通常采用学习的方法。通过使用的数据，行为通常被预先分割，尽管行为检测有一些应急的方法。因此，这些方法很少关注计算机视觉中的特征提取与描述，本节将就此展开阐述。我们应该通过将特征提取技术扩展应用到图像序列，并考虑那些致力于从图像序列中分割和描述运动对象的方法。11.5.2运动形状检测11.5.2运动形状检测11.5.2运动形状检测11.5.2运动形状检测11.5.2运动形状检测11.5.2运动形状检测11.5.2运动形状检测11.5.2运动形状检测11.5.2运动形状检测11.5.2运动形状检测思考与练习11-1主动轮廓模型包含哪几部分？各部分怎样计算？11-2编程实现图11-2的Python程序。11-3试说明随机梯度算法和EM算法的工作过程，并说明他们之间的优缺点？11-4试说明基于核函数算法跟踪的工作过程。第12章聚类分析12.1K-Means聚类 12.1.1目标函数 12.1.2K-Means聚类算法流程 12.1.3K-Means聚类模块库代码 12.1.4Python中基于OpenCV的K-Means聚类12.2FCM聚类 12.2.1FCM聚类目标函数 12.2.2FCM聚类算法 12.2.3基于Python与OpenCV的FCM聚类12.3SCM聚类 12.3.1

SCM聚类算法 12.3.2SCM聚类工业应用第12章聚类分析

聚类分析是一种无监督学习，用于对未知类别的样本进行划分，将他们按照一定的规则划分成若干个类簇，把相似的样本聚集在同一个类簇中。与有监督的分类算法不同，聚类算法没有训练过程，直接完成对一组样本的划分。常用的聚类方法有K-Means聚类、FCM（Fuzzyc-Means）聚类和SCM（SubtractiveClusteringMethod）聚类。

12.1K-Means聚类

K-Means聚类算法由Steinhaus（1955年）、Lloyd（1957年）、Ball&Hall（1965年）、McQueen（1967年）分别在各自不同的领域内独立提出的。尽管K-Means聚类算法被提出有50多年了，但仍是目前应用最广泛的聚类算法之一。12.1.1目标函数

对于给定的

维数据点的数据集

，其中

，数据子集的数目是K，K-Means聚类将数据对象分为K个划分，具体划分为

。每个划分代表一个类

，每个类

的中心为

。取欧氏距离作为相似性和距离判断的准则，计算该类各个点到聚类中心

的距离平方和。

（11-1）

（11-2）

聚类的目标是使各类总的距离平方和

最小。12.1.1目标函数

其中：

K-Means聚类算法从一个初始的K类别划分开始，然后将各数据点指派到各个类别中，以减少总的距离平方和。由于K-Means聚类算法中总的距离平方和随着类别的个数K的增加而趋向于减小，当时

，

。因此，总的距离平方和只能在某个确定的类别个数K下取得最小值。12.1.2K-Means聚类算法流程

K-Means聚类算法的核心思想是把n个数据对象划分为k个聚类，使每个聚类中的数据点到该聚类中心的平方和最小。输入聚类个数k，数据集中的数据对象的个数n。算法如下所示。⑴从n个数据对象中任意选取k个对象作为初始的聚类中心种子点；⑵分别计算每个对象到各个聚类中心的距离，把对象分配到距离最近的聚类中心种子群；⑶所有对象分配完成后，重新计算k个聚类的中心；⑷重复上述步骤（2）至步骤（3）的过程，本周期计算的结果与上一周期计算得到的各个聚类中心比较，如果聚类中心发生变化，转至步骤（2），否则转至步骤（5）；⑸输出聚类中心结果。12.1.3K-Means聚类模块库代码K-Means聚类在机器学习库Scikit-learn中，相应的函数sklearn.cluster.KMeans。sklearn.cluster.KMeans(n_clusters=8,

init='k-means++',

n_init=10,

max_iter=300,

tol=0.0001,

precompute_distances='auto',

verbose=0,

random_state=None,

copy_x=True,

n_jobs=1,

algorithm='auto')12.1.3K-Means聚类模块库代码sklearn.cluster.KMeans参数的意义：n_clusters：分类簇的个数；init:初始簇中心的获取方法；n_init:获取初始簇中心的更迭次数，为了弥补初始质心的影响，算法默认会初始10次质心，实现算法，然后返回最好的结果；max_iter:最大迭代次数（因为kmeans算法的实现需要迭代）；tol:算法收敛的阈值，即kmeans运行准则收敛的条件；precompute_distances：有3种选择{‘auto’、‘True’、‘False’}，是否需要提前计算距离，这个参数会在空间和时间之间做权衡。如果选择True，预12.1.3K-Means聚类模块库代码计算距离，会把整个距离矩阵都放到内存中；选择auto，在数据维度featurs*samples的数量大于12×106时不预计算距离；如果选择False，不预计算距离。verbose：默认是0，不输出日志信息，值越大，打印的细节越多；random_state:随机生成簇中心的状态条件，一般默认即可（随机种子）；copy_x:布尔值，标记是否修改数据，主要用于precompute_distances=True的情况。如果True，预计算距离，不修改原来的数据；如果False，预计算距离，修改原来的数据用于节省内存；n_jobs:指定计算所需的进程数；algorithm：K-Means的实现算法，有：‘auto’,‘full’,‘elkan’,其中'full’表示用EM方式实现。12.1.3K-Means聚类模块库代码12.1.3K-Means聚类模块库代码12.1.3K-Means聚类模块库代码12.1.4Python中基于OpenCV的K-Means聚类

在OpenCV中，提供了cv2.kmeans()函数实现K均值聚类，其一般格式为：retval,bestLabels,centers=cv2.kmeans（data，K，bestLabels，criteria,attempts,flags）返回值各参数的含义：retval：距离值（也称密度值或紧密度），返回每个点到相应中心点距离的平方和；bestLabels：各个数据点的最终分类标签（索引）；centers：每个分类的中心点数据。12.1.4Python中基于OpenCV的K-Means聚类函数体内各参数的含义：data：输入待处理数据集合，每个特征放在单独的一列中；K：要分出的簇的个数，即分类的数目，最常见的是K=2，表示二分类；bestLabels：表示计算之后各个数据点的最终分类标签（索引）。实际调用时，参数bestLabels的值设置为None；

criteria：算法迭代的终止条件。当达到最大循环数目或者指定的精度阈值时，算法停止继续分类迭代计算。该参数由3个子参数构成，分别为：type、max_iter和eps，其中max_iter代表最大迭代次数；eps表示精确度的阈值；type表示终止的类型，分别为：cv2.TERM_CITERIA_EPS（表示精度满足eps时，停止迭代）,cv2.TERM_CITERIA_MAX_ITER（表示迭代次数超过阈值max_iter时，停止迭代）和12.1.4Python中基于OpenCV的K-Means聚类cv2.TERM_CITERIA_EPS+cv2.TERM_CITERIA_MAX_ITER（上述两个条件中的任意一个满足时，停止迭代）。attempts：在具体实现时，为了获得最佳分类效果，可能需要使用不同的初始分类值进行多次尝试，指定attempts的值，可以让算法使用不同的初始值进行多次尝试。flags：表示选择初始中心点的方法，主要有3种，分别为：cv2.KMEANS_RANDOM_CENTERS（表示随机选取中心点），cv2.KMEANS_PP_CENTERS（表示基于中心化算法选取中心点），cv2.KMEANS_USE_INITIAL_LABELS（表示使用用户输入的数据作为第一次分类中心点，若果算法需要多次尝试（attempts值大于1时），后续尝试都是使用随机值或者半随机值作为第一次分类中心点）。12.1.4Python中基于OpenCV的K-Means聚类12.1.4Python中基于OpenCV的K-Means聚类12.1.4Python中基于OpenCV的K-Means聚类12.1.4Python中基于OpenCV的K-Means聚类12.2FCM聚类Ruspini率先提出了模糊划分的概念。以此为基础，模糊聚类理论和方法迅速发展起来。实际中，最受欢迎的是基于目标函数的模糊聚类方法，即把聚类归结成一个带有约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类。在基于目标函数的聚类算法中模糊c均值（FCM，Fuzzyc-Means）类型算法的理论最为完善、应用最为广泛。12.2.1FCM聚类目标函数Bezdek给出了基于目标函数模糊聚类的一般描述：

（11-3）其中，表示由c个子集的特征函数值构成的矩阵，m称为加权指数，又称为平滑参数。表示样本与第i类的聚类原型之间的距离度量，如式（11-4）所示。（11-4）其中，A为阶的对称正定矩阵，聚类的准则为取的极小值，如式（11-5）所示。（11-5）12.2.1FCM聚类目标函数由于矩阵U中各列都是独立的，因此

（11-6）

式（11-6）采用拉格朗日乘数法来求解。

（11-7）

最优化的一阶必要条件为

（11-8）

（11-9）12.2.1FCM聚类目标函数由式（11-9）得（11-10）使得为最小的值为(11-11）用类似的方法可以获得

为最小的

的值，令

（11-12）12.2.1FCM聚类目标函数得到（11-13）（11-14）若数据集、聚类类别数c和权重m值已知，由式（11-11）和式（11-14）确定最佳模糊分类矩阵和聚类中心。12.2.2FCM聚类算法为了优化聚类分析的目标函数，现在广泛流行的模糊c均值（FCM，Fuzzyc-means）聚类算法得到广泛使用。该算法从硬c均值（HCM，Hardc-means）聚类算法发展而来。FCM聚类算法如下所示。初始化：给定聚类类别数，，是数据个数，设定迭代停止阈值，初始化聚类原型模式，设置迭代计数器 ；步骤一：用式（11-15）计算或更新划分矩阵：对于，如果，则有

（11-15）12.2.2FCM聚类算法如果使得，则有，且对（11-16）步骤二：使用式（11-17）更新聚类模式矩阵：（11-17）步骤三：如果，则停止计算，输出矩阵和聚类原型；否则令 ，转至步骤一。12.2.3基于Python与OpenCV的FCM聚类

例12-3在Python中编程实现FCM聚类算法。importnumpyasnpimportmatplotlib.pyplotaspltimporttimestar=time.time()#计时image=plt.imread("D:\Python\pic\smalldog52.jpg")#读取图片，存储在三维数组中row=image.shape[0]col=image.shape[1]plt.figure(1)#plt.subplot(221)plt.imshow(image)deffcm(data,threshold,k,m):12.2.3基于Python与OpenCV的FCM聚类

#0.初始化data=data.reshape(-1,3)cluster_center=np.zeros([k,3])#簇心distance=np.zeros([k,row*col])#欧氏距离times=0#迭代次数goal_j=np.array([])#迭代终止条件：目标函数goal_u=np.array([])#迭代终止条件：隶属度矩阵元素最大变化量

#1.初始化Uu=np.random.dirichlet(np.ones(k),row*col).T#形状（k,col*rol），任意一列元素和=1#forsinrange(50):12.2.3基于Python与OpenCV的FCM聚类

while1:times+=1print('循环：',times)#2.簇心updateforiinrange(k):cluster_center[i]=np.sum((np.tile(u[i]**m,(3,1))).T*data,axis=0)/np.sum(u[i]**m)#update#欧拉距离foriinrange(k):distance[i]=np.sqrt(np.sum((data-np.tile(cluster_center[i],(row*col,1)))**2,axis=1))12.2.3基于Python与OpenCV的FCM聚类

#目标函数goal_j=np.append(goal_j,np.sum((u**m)*distance**2))#更新隶属度矩阵oldu=u.copy()#记录上一次隶属度矩阵u=np.zeros([k,row*col])foriinrange(k):forjinrange(k):u[i]+=(distance[i]/distance[j])**(2/(m-1))u[i]=1/u[i]goal_u=np.append(goal_u,np.max(u-oldu))#隶属度元素最大变化量print('隶属度元素最大变化量',np.max(u-oldu),'目标函数',np.sum((u**m)*distance**2))12.2.3基于Python与OpenCV的FCM聚类

#判断：隶属度矩阵元素最大变化量是否小于阈值ifnp.max(u-oldu)<=threshold:breakreturnu,goal_j,goal_uif__name__=='__main__':img_show,goal1_j,goal2_u=fcm(image,1e-09,5,2)img_show=np.argmax(img_show,axis=0)plt.figure(2)#plt.subplot(223)plt.plot(goal1_j)plt.rcParams['font.sans-serif']=['SimHei']plt.rcParams['axes.unicode_minus']=False12.2.3基于Python与OpenCV的FCM聚类

#plt.title('目标函数变化曲线')plt.xlabel('迭代次数')plt.ylabel('目标函数')plt.figure(3)#plt.subplot(224)plt.plot(goal2_u)#plt.title('隶属度矩阵相邻两次迭代的元素最大变化量变化曲线')plt.xlabel('迭代次数')plt.ylabel('隶属度矩阵相邻两次迭代的元素最大变化量')plt.figure(4)12.2.3基于Python与OpenCV的FCM聚类

#plt.subplot(222)plt.imshow(img_show.reshape([row,col]))end=time.time()print('用时：',end-star)plt.show()程序运行结果如图11-3所示。12.2.3基于Python与OpenCV的FCM聚类

12.3.1SCM聚类算法由于采用FCM聚类方法确定规则的数时，需要事先知道聚类中心的个数。因此，在应用上受到很大影响。减法聚类（SCM，Subtractiveclusteringmethod）可以有效克服FCM对初始化敏感及容易陷入局部极值点的缺点，减法聚类是一种密度聚类，将每个数据点都作为一个潜在的聚类中心，按照如下步骤来确定：Step1:假定每个数据点都是聚类中心的候选者，则数据点

处的密度指标定义为

，其中

为样本数据集，

；这里

是一个正数，定义了该点的一个邻域，半径以外的数据点对该点的密度指标贡献非常小，取

；12.3.1SCM聚类算法Step2:计算最大密度值 ，选择具有最大密度指标的数据点为第1个聚类中心，即；Step3:选取

，按照下式修改密度指标：

，

；计算最大密度值

，选择具有最高密度指标的数据点为第2个聚类中心，即

；Step4:重复Step3，当新聚类中心

对应的密度指标

与满足

时,则聚类过程结束，否则进入Step3，取

。12.3.2

SCM聚类工业应用基于上述分析，以新型干法水泥熟料生产过程生料分解率目标值设定为例，如图11-4所示。

图11-4易煅烧生料或难煅烧生料智能控制结构简图12.3.2

SCM聚类工业应用采用ANFIS建立生料分解率目标值设定模型。由于采用FCM聚类方法确定规则数量时，需要事先知道聚类中心的个数。因此，在应用上受到很大影响。采用减法聚类方法确定隶属函数中心及规则数量。减法聚类可以有效克服FCM对初始化敏感及容易陷入局部极值点的缺点，结构如图11-5所示。12.3.2

SCM聚类工业应用

图11-5基于减法聚类和ANFIS的生料分解率目标值设定模型12.3.2

SCM聚类工业应用图11-5中，生料分解率目标值设定模型由易煅烧生料的生料分解率目标值设定模型、难煅烧生料的生料分解率目标值设定模型和切换机制组成。为了描述方便，生料分解率目标值设定模型中的输入变量集，简写为。图11-5中，A部分内每一个块和节点描述如下。在切换机制中，易煅烧性识别模块通过易煅烧生料游离氧化钙含量最大值、生料煅烧指数、难煅烧生料游离氧化钙含量最大值判断生料的煅烧性。如果，那么代表易煅烧生料；如果，那么代表难煅烧生料。目标值选择模块根据式（11-18）选择相应的目标值设定模型。（11-18）

12.3.2

SCM聚类工业应用在A部分的第1层，每个节点是一个方形，并且可以表示为：