聚类算法Kmeans与梯度算法Meanshift

《聚类算法Kmeans与梯度算法Meanshift》由会员分享，可在线阅读，更多相关《聚类算法Kmeans与梯度算法Meanshift（17页珍藏版）》请在金锄头文库上搜索。

1、Kmeans 与 Meanshift、EM 算法的关系Kmeans算法是一种经典的聚类算法，在模式识别中得到了广泛的应用，基于Kmeans的变种算法也有 很多，模糊Kmeans、分层Kmeans等。Kmeans和应用于混合高斯模型的受限EM算法是一致的。高斯混合模型广泛用于数据挖掘、模式识别、 机器学习、统计分析。Kmeans的迭代步骤可以看成E步和M步，E：固定参数类别中心向量重新标记样本， M：固定标记样本调整类别中心向量。K均值只考虑（估计）了均值，而没有估计类别的方差，所以聚类的 结构比较适合于特征协方差相等的类别。Kmeans在某种程度也可以看成Meanshitf的特殊版本,Mean

2、shift是一种概率密度梯度估计方法（优 点：无需求解出具体的概率密度，直接求解概率密度梯度。），所以 Meanshift 可以用于寻找数据的多个 模态（类别），利用的是梯度上升法。在06年的一篇CVPR文章上，证明了 Meanshift方法是牛顿拉夫逊 算法的变种。Kmeans和EM算法相似是指混合密度的形式已知（参数形式已知）情况下，利用迭代方法， 在参数空间中搜索解。而 Kmeans 和 Meanshift 相似是指都是一种概率密度梯度估计的方法，不过是 Kmean 选用的是特殊的核函数（uniform kernel），而与混合概率密度形式是否已知无关，是一种梯度求解方式。 PS：两种K

3、means的计算方法是不同的。Vector quantization也称矢量量化:指一个向量用一个符号K来代替。比如有10000个数据，用Kmeans 聚成100类即最有表征数据意义的向量，使得数据得到了压缩，以后加入的数据都是用数据的类别来表示 存储，节约了空间，这是有损数据压缩。数据压缩是数据聚类的一个重要应用，也是数据挖掘的主要方法 混 合高斯模型是一系列不同的高斯模型分量的线性组合。在最大似然函数求极值时，直接求导存在 奇异点的问题，即有时一个分量只有一个样本点，无法估计其协方 差，导致其似然函数趋于无穷，无法求 解。另一个问题是，用代数法求得的解是不闭合的，即求解的参数依赖于参数本身

4、的值，变成一个鸡生蛋 蛋生鸡的问题。这些问题看似无解，但是可以使用迭代的方法如EM，k均值等，预先设置一些参数，然后 迭代求解。PS：也有用基于梯度的方法求解的。在求解混合模型时，有一个重要的概念即模型的可辨识性 （如果无论样本的数量为多少都无法求出模型参数的唯一解，则称模型是不可辨识的），这是EM算法的前 提。在实际应用时，由于EM算法的复杂度比K均值高，所以一般先用K均值大致收敛到一些点，然后用 EM 算法。 EM 算法求解混合模型的固然有效，但不能保证找到最大使然函数的最大值。EM算法是求解具有隐变量的概率模型的最大似然函数的解的常用方法。当样本集是样本与隐变量一 一对应时，数据集称为完

5、整数据集，可以直接求解模型参数，但很多时候只知道样本，不知道其对应的隐 变量，这是非完整数据集。所以求解模型参数的关键是隐变量的后验概率，由后验概率可以推出完整数据 集用于求解参数。增量式的EM算法，每次只更新一个点，收敛速度更快。上述方法可以看成是无监督学 习。PS： EM是一个似然函数下界最大化解法，保证了解法的收敛性。Opencv 之 KMEANS 篇Opencv中的K-means适用于数据预处理，但图像分割的消耗的时间太长并且效果不怎么好，使用空 间信息后，图像的分割后受空间的影响很大（同一类的数据如果分布较远，不是高斯型的，就会错分）， 因为图像分割本身要求数据是呈超球体（高斯类）分

6、布。K-means得到的是线性判决面，因为算法使用的准 则函数是最小均方误差，相当于不同类别间求最小二乘直线拟合。这是一个局限点，而且类别数的选择也 很重要，但实际情况是，往往很难确定图片中的类别数。在 OPENCV 里判断聚类误差是由类别中心点的两次 迭代结果的差决定的，即当类别中心点都变化不大时或者说不变时，聚类结束。多次运行程序会发现不同 的结果，因为程序可能会陷入不同的局部极值，所以如果要找到全局最优，可以多次运行找出误差最小值。 在 opencv 的 kmeans 函数内有关于运行次数的选择变量，除了输出类别标记外，还可以输出类别中心等。 输入图片：输出图片：类别间的分界基本呈线性。

7、在使用K-means函数时，注意输入和输出矩阵的数据类型，是32FC1。输入矩阵的每一行是一个输入 向量。 OPENCV 矩阵的特点是，矩阵的元素本身可以是个向量，即元素的数据通道，这样方便图像处理。所 以一个样本向量可以用矩阵的一行表示即单通道多数据，也可以用一个多数据通道的矩阵元素表示。PS：在使用空间信息作分类时，其实向量是由不同的域组成，空间域和颜色域，不满足欧几里德空间的约 束，这里用了近似的。只使用 RGB 颜色，未添加空间信息的分割结果：OPENCV之EM算法篇EM 算法是求解最大似然函数极值的一种解法，使用的是迭代求解的方法，并且保证收敛。 EM 算法的 应用相当广泛，包括混合

8、高斯模型的求解，隐马尔科夫模型的求解，最大后验概率模型的求解等。最常用 的是混合高斯模型的求解，把混合概率密度分解为一系列的高斯分量之和。关于EM算法的具体流程可参考 网上，个人推荐一个介绍的不错的，pattern recognition and machine learning有一章专门介绍这 个，通俗易懂，介绍了 KMEANS与EM算法的关系，还介绍了一搬（general） EM算法的流程。在我博客里 还会有另一篇文章专门介绍Kmeans和EM算法和MEANSHIFT算法的关系。Opencv里的CVEM函数是用于专门求解混合高斯模型的，输入和输出都与CVkmeans2函数的输入输出 兼容，

9、都是输入矩阵一行代表一个样本。可以选择两种模式，一种是普通的方差矩阵，一种是对角的方差 矩阵。对角的方差矩阵计算相对简单，可以减少计算量，而且很多情况下效果和普通的方差矩阵差不多。 由于EM算法的计算复杂度要高于Kmeans，所以在实际使用时一般先用Kmeans选定类别中心，再用EM算 法调整，可以提高计算速度。在CVEM类里有KMEANS的成员函数，实现预处理功能。Opencv里的EM算法 有个和Kmeans 一样的缺点就是类别数无法确定，并且数据如果不服从高斯分布，用于图片分割的效果不好, 耗时也很长。所以EM算法还是比较适合于大数据量的样本聚类或学习。下面是一个图片分割的例子：输入图像：

10、输出图像：PS：在右图中发现，每个形状的周围都存在一些黑色的类别，这是由于左图中每个形状的边缘部分是模糊 的即（颜色值递减的），所以出现错分割或者说过分割。Opencv 之 meanshift 篇本文主要是介绍了 OPENCV里的meanshift分割函数cvPyrMeanShiftFiltering函数。关于算法的详 细叙述可参考 Mean shift: a robust approach toward feature space analysisD,comaniciu 2003. 该函数基本参照上文所描述的算法流程编写的。在opencv实现里加入了金字塔分层分割的概念oMeanshift

11、分割可供选择的只有一个参数即分割的精细度，也就是选择的核宽。 cvPyrMeanShiftFiltering 函数只能 输入8位三通道的RGB图像，输出时分割结果，没有提供分割的具体信息如类别数，模态等。该函数采用 的是UNIFORM核，选择的矩形区域为核覆盖区。Meanshift算法在每个样本上都执行一次确定类别，所以 复杂度比较高0 （N*W）, w是操作系数，处理一幅320*240图片需要2, 3秒的时间。函数在实现时也没有 考虑消除一些小的类别（数量较少的）。使得这个函数更像是discontinuity preserve smoothing.有很多图片经过这个函数处理后很难感觉出输入输

12、出有什么大区别，其实是被平滑了。观察仔细点 可以看出来。输入图片：输出图像：在 opencv 里面关于 meanshift 算法的应用还有两个函数 CVmeanshift 和 CVCAMshift 函数，都是用于跟踪的，效果还不错。现在在视频跟踪里，meanshift方法+卡尔曼滤波还是挺流行的。SURF: speed up robust featureSURF特点：1.使用积分图像完成图像卷积（相关）操作，2,使用Hessian矩阵检测特征值；3,使用基于 分布的描述符（局部信息）。兴趣点检测相关研究：1998 Lindberg介绍自动尺度选择的概念，允许检测图像中的兴趣点在它们的特征尺度上

13、。他实验了 Hessian 矩阵的行列式和Laplacian（和矩阵的迹一致）检测团状结构。1998 Lowe 提出用 DOG 近似 LOG。2001 Mikolajczyk 和 Schmid 重新定义了这个方法，名为 Harris-Laplace 和 Hessian-Laplace。使用 Harris 或 Hessian 矩阵的行列式来选择特征点的闻之，使用 Laplacian 选择尺度。此外Mikolajczyk（2005, 2006）还做了一些算子的比较工作。从中可知：基于Hessian检测器比基于Harris 检测器更稳定，重复检测性更好。此外，使用Hessian矩阵的行列式比使用它的

14、迹更有优势。同时也发现 使用类似于 DOG 的近似方法可以提高速度但只损失很小的精度。描述符的相关研究 图像特征点的描述符一个共同点是表达了兴趣点邻域内小尺度的特征分布。使得描述符的描述性更好，识 别性更高。SIFT的特点正是掌握了空间域亮度模式的大量信息（基于直方图方法：8个方向的箱格，4*4 像素）。描述了特征点邻域内点的梯度方向信息，共128维。PCA-SIFT： 36维，匹配速度更快，但区分度下降，并且延长了特征的计算时间。GLOH:区分度更高但是数据压缩花销时间太长。2006 Grabner使用积分图像近似SIFT。可以达到和我们同样的速度。但是相比SIFT质量有所下降。（为 SUR

15、F提供了重要信息积分图像）。匹配算法： BBF（k-d tree） ,balltrees, vocabulary trees, locality sensitine hashing 本文补充 提出了，使用Hessian矩阵的迹来显著提高匹配速度。在低维描述符下，任何算法的匹配速度都很快 二兴趣点检测。使用 HESSIAN 矩阵的近似检测兴趣点。使用积分图像加快计算。2001 Viola and Jones 提出积分图像的概念。1998 Simard 提出的盒形计算框架使用积分图像。本文的创新点：使用近似的Hessian矩阵来求特征点。D0G近似LOG,盒形滤波近似不同的二次微分。在3*3*3的

16、邻域范围内寻找Hessian矩阵的行列式最大值。9*9盒形滤波器相当于方差1.2的高斯函数。 图像尺度的改变是通过改变盒形滤波器尺寸实现的。尺度空间的分组时，相邻组首尺度滤波器大小之差 相差2倍。如第一二组差6，则二三组差12.为了减少计算时间，第一组采样间隔1像素，第二组2像素， 以此倍增。特征点的精确定位即实现亚像素描述，通过LOWE文章中提出的泰勒级数展开，可求得。 三特征点描述与匹配本文提出的是，建立一阶Haar小波在x和y上的响应的分布（局部信息整合），使用积分图像提高计算速 度，并且只有64维。使用Laplacian （迹）的符号来索引特征点，方便匹配。小波变换的重要用途是图像压缩。在图像识别等应用中主要应用于人脸识别和行人识别。2002 haar-like features2001矩形特征与Adabo