第13课数据有关联 课件(共20张PPT)-2023-2024学年浙教版（2023）四年级上册同步教学

(课件网) 浙教版四年级上册 第13课 数据有关联 CONTENTS 目录 匈牙利算法的数据关联应用 02 总结回顾 04 匈牙利算法的数据关联概念 01 作业布置 03 匈牙利算法的数据关联概念 01 匈牙利算法的数据关联概念 依次进行数据关联是局部最优解，并不能代表全局最优解。而匈牙利算法则在追求全局最优，是一种在多项式时间内求解分配问题的组合优化算法。多目标跟踪数据关联问题可以转化为有权二分图最小权匹配问题，匈牙利算法就是解决数据关联问题的图算法。 匈牙利算法的数据关联应用 02 图（Graph，G），是由顶点集合（Vertices，V）和边集合（Edges，E）组成的二元组，表征了不同顶点间的拓扑连接关系，图中的边是否具有单向性可将图分为有向图和无向图，根据图中的边是否具有不同的权重可将图分为有权图和无权图。 二分图（Bipartite Graph）是一种特殊的图，又称二部图。二分图的顶点集可以被划分为两个互不相交的独立子集U和V。二分图边集合 E 中的每一条边分别连接了顶点子集 U 和 V 中的一个顶点，但 U 和 V 内部的顶点互不相连。 二分图的结构与多目标跟踪任务的结构很相像，可以把U与V看成是多目标跟踪任务中的前一帧与当前帧的检测框集合，U与V之间的关联视为前一帧与当前帧的同一id目标的检测框的关联，我们需要做的就是将相邻两帧的目标检测框尽可能准确的两两匹配。 匹配： 给定图G=(U，V，E)，一个匹配表示多个U和多个V之间的关联M。M是E的一部分，即子集。匹配不仅仅是两个点一条线，而是多个关联的组合。匹配是一种关联的方案。匹配中的线是一一对应的，是一个点链接另外一个点的，在目标检测中就是当前帧的检测框一一对应到上一帧的检测框。如下图的U5和V4，U3和V3，U2和V1共同组成一个匹配。匹配上的边叫匹配边，未匹配上的边叫未匹配边。同样的，匹配上的点叫匹配点，未匹配上的点叫未匹配点。 最大匹配（Maximum-Cardinality Matching）表示图的所有匹配中边数最多的匹配方案，最大匹配不唯一。匹配边数最大值就是一个集合点的个数。 01 大权匹配：对于有权图而言，最大权匹配（Maximum-Weight Matching）表示的是有权图的所有匹配中边的权重之和最大的那些匹配。 02 最小权匹配：对于有权图而言，最小权匹配（Minimum-Weight Matching）表示的是有权图的所有匹配中边的权重之和最小的那些匹配。 03 多目标跟踪数据关联问题 多目标跟踪数据关联问题可以转化为有权二分图最小权匹配问题。跟踪过程中的上一帧目标可以看成U，下一帧目标可以看做V，边的权重可以看作是上一帧目标和下一帧目标通过某种方式计算得到的匹配距离，这个匹配距离我们称之为代价（Cost），所有的匹配距离构成了代价矩阵（Cost Matrix），我们要找到匹配关系使得总的匹配距离最小（代价最低）。 交替路 从某个未匹配点出发，交替经过未匹配边和匹配边形成的路径。 增广路（Augmenting Path）是一条特殊的交替路，增广路从图中的某个未匹配点起始，交替经过未匹配边和匹配边，并终止于不同于起始点的另一个未匹配点。 性质： Berge 定理：对于给定的图G和它的一个匹配M，M是G的最大匹配的充要条件是G中不存在匹配M的增广路。增广路上的边个数一定是奇数，是奇数就意味着是一边的点到另外一个的点。这样增广路上的边未匹配的边一定比匹配边多1。 如何找到最大权匹配？ 对于一个给定的二分图 G=(U,V,E)和初始为空的匹配M，只要反复搜索增广路就能逐渐扩展匹配的大小，最终当我们找不到增广路时就得到了一个最大匹配。利用增广路找最大匹配的算法，就叫做匈牙利算法。 总结回顾 03 总结回顾 通过今天的学习有哪些收获？请分享一下。 作业布置 04 作业 继续查找有关数据关联的资料，我 ... ...