开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算：视频场景分割与语义分段（上）】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/811/detail/15702
视频场景分割与语义分段（上）
内容介绍：
一、 什么是视频聚类
二、 聚类的基本概念
三、 聚类方法分类
四、 K-均值法
五、 层次聚类法
前面的课，我们已经把一段连续的视频分成了一个一个的镜头，并且在每个镜头里边，选取了特定数量的关键帧，那么今天课的内容是我们怎么样把语义上相关的多个镜头能够把它聚类成场景，那什么是视频聚类？
一、什么是视频聚类
它是指把相似的原始视频数据，按照确定的相似度的度量准则来进行聚类，聚类的输入是镜头，那么它形成一个更高层次的视频语义的层次，比如说场景，故事单元或者情节等等。它可以便于对视频进行组织浏览，建立索引、查询或者摘要等。
视频聚类是基于内容的检索的基础，尤其是高层语义的这种检索，就用到了视频聚类，它也是我们视频理解的一个关键。
二、聚类的基本概念
聚类是机器学习一个非常简单的算法，英文叫 Cluster，它是指将数据对象分成多个类或者多个簇，在同一个这个簇中，对象具有较高的相似度，而不同簇中对象差别很大，就是它的相似度很小，这类分析方法，是一种无监督的学习方法，它可以将一些未知的模式分成若干类，从而可以把一些将未知模式通过一个无监督的、反复的一个迭代，就可以把它本身里边有的一些规则、一些类别自动地分出来。
根据特征向量的差别，或者是特征差的这个距离，在一定的误差范围内，我们就把它认为是在同一个簇内，如果大于某一个阈值，就认为它是不同的聚类，这就是它的判定的依据。
三、聚类方法分类
根据的聚类方法不同，可以分成这样几个，比如说基于划分的方法，基于层次的方法，密度的方法，网络的方法，以及特定模型的方法。这个大家感兴趣的可以去了解我们机器学习里面这一个算法。
四、K-均值法
它是指一种基于划分的方法，基本的原理是：给定一个 N 个对象组成的这种数据集合或者是数据库，构建数据的 K 个划分，每个划分表示一个聚类里面的簇，并且 K 小于等于 N， N 个数据最多分成N 个簇，每一个数据自己是一组，这是上限，然后将数据划分成 K 个组，同时满足的条件是什么？每个组至少要有一个对象，不能有个组是空的，每个对象只能属于并且必须属于一个组，不能有一个没分，有的元素既不属于这个 K 个的任何一个，这就没有全部分完。
它是以K作为参数，把 N 个对象分成 K 个簇，使这个每一个簇内具有较高的相似度，而簇间的这个相似度较低。
步骤是随机的选取 K 个对象，每个对象就代表簇里面它的均值叫做簇中心，剩余的N减K对象就根据这个对象与其各个簇中心的距离，将它赋予最近的簇，剩下的N减K的元素中的每一个都跟那个 K 个这个中心值去求差值，距离哪个差值最小，就把这个元素放到簇里去，原来是一个，现在可能又进来一个，就要计算新的均值，计算均值以后，再把那所有的元素，剩下的每一个对象都与 K 的中心值求距离，然后再去找到最小的距离。比如本来某一个像素属于第二组，来了一个对象以后，它的均值发生改变了，再求差的时候可能离它最近的不是它这一组，可能是隔壁的第三组，或者是第五组，这个时候簇内的元素就发生了改变，循环往复，继续计算，直到对象不再动了，我们就叫做它已经收敛了为止。
此时我们就把 N 个对象，把它稳定地分到了 K 的值。特点是事先给一个 K 值，就是说明到底分出多少类，但是对于大多数视频来讲，我们并不知道里面有多少个场景，除非你提前是知道的，那么你 K 就知道，如果不知道，那我们就无法拥有 K 均值了。我们前面讲搜索的时候说过 K 要么提前知道它的值，要么 K 如果取得足够大，那么K多一点少一点都无所谓，比如说在进行图像分类的时候，也用 K 均值法，那 K 就只取个大点，比如十万二十万，此时是200001还是200008，都无所谓。
如何巧妙的使用 K 均值法来聚类对于我们的视频内容是很重要的，它有很好的方法，尤其是我们在特征聚类的时候，有的时候也用 K 均值法。
五、层次聚类法
就是对给定的数据对象集合进行分层的计算，根据层次的分解是如何形成的，我们可以分成凝聚和什么和分裂，如果是你从一个完整的把它分成分细，那说明是分裂的，如果是从细小的把它聚集成一个大的结合，那就是凝聚。
1、凝聚的方式
是自底向上的，将每个对象一开始都分成一个簇，然后合并原子簇越来越大的簇，直到所有的对象都在一个簇中，合并的依据是它们的距离，就把距离近的进行合并，比如说我们一开始有 ABCD 五个元素，那我们第一步就找近的，比如说 ab 挨着近，就放这一组，第二步把其他的 de 分成一组再合并，c 和 de 还可以合并直到这个两个集合之间的差值已经足够大了为止。这是凝聚的方法，它的终极目标可以合并成一个，而我们真正用的时候要么是全部分，各分各的，要么是聚成中间某一个层次。
2、分裂的方式
它是自底向下与凝聚的层次聚类恰恰相反，先将所有的对象置于一个簇中，然后逐渐细分成越来越小的簇，直到每个对象成为一个簇，或者达到某一个终止的条件为止。例如达到希望的数目就停或者两个最近簇之间的这种差值已经超过了某个阈值。
例如：第一步，全都是在一个簇里面进行分列，把 abcde 先分成两个 ab 和 de，接着把ab再分成两个 a 和 b，把 cde 分成 c 和 de 下面再继续分，以此类推，分裂的方式，逐渐分析。
我们的视频聚类里面，如果说你是从镜头开始分的，镜头已经切分好了，那我们一定是采用凝聚的方式，先有 abcde；如果镜头没有切分，反向去找场景的话，那一定是分裂的方式。
