【项目总结（二）】–关键帧Matlab提取 K-Means聚类算法算法总结与实现

1:”中兴产学研视频摘要项目演示程序”的基于聚类的算法如何理解，算法流程图如何表示？（论文要求严格画图）

程序中的基本思路：

1.以第一帧图像的R，G，B直方图为初始质心，获取第一幅图像的R，G，B三幅图像的直方图，为1*256的矩阵.

2.对比第二帧与第一个聚类质心（开始为第一帧的RGB直方图），若第二帧类似于第一帧(这里比较两个图像的RGB三种质心的距离，根据预先设定的阈值进行判断)，第二帧加入第一帧的聚类，同在新加入的图像与初试质心的基础上，生成新的质心，作为与新帧比较的基础。若不类似，则生成新的聚类。下次比较时新的帧将会与所有的聚类的质心进行比较，选择归属的聚类或者生成新的聚类。如此往复，将会生成几个聚类，同时每个帧都会有所归属。

3.将每一帧与所属聚类的质心进行比较，求出聚类中与聚类质心最近的一帧，作为关键帧，即求出了关键帧

算法流程图：

流程图这是大题框架，若是论文需要更加严格具体

————————————————————————————————–

补充知识点：

KMeans算法的基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。
K-Means聚类算法主要分为三个步骤：
(1)第一步是为待聚类的点寻找聚类中心
(2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去
(3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心
反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止

下图展示了对n个样本点进行K-means聚类的效果，这里k取2：
(a)未聚类的初始点集
(b)随机选取两个点作为聚类中心
(c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去
(d)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心
(e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去
(f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心

在聚类问题中，给我们的训练样本是，每个，没有了y。

K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下：

1、随机选取k个聚类质心点（cluster centroids）为。

2、重复下面过程直到收敛 {

对于每一个样例i，计算其应该属于的类

对于每一个类j，重新计算该类的质心

}

K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。