马氏距离+匈牙利算法+卡尔曼滤波-by wilson

这一篇文章主要讲解马氏距离、匈牙利匹配算法、卡尔曼滤波等三个部分，是为了后续讲解Deep Sort多目标跟踪提供先验知识。

一、马氏距离

　　参考博文：https://www.jianshu.com/p/5706a108a0c6
　　1⃣️ 马氏距离定义：
　　马氏距离是由印度统计学家马哈拉诺比斯（P. C. Mahalanobis）提出的，表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法或者计算一个样本点与一个分布的距离。与欧氏距离不同的是它考虑到各种特性之间的联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的）并且是尺度无关的（scale-invariant），即独立于测量尺度。
　　马氏距离可以衡量一个随机变量和一个分布之间的距离：
　　对于一个均值为、协方差矩阵为的多维随机变量：

　　马氏距离为：

　　马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量X与Y的差异程度：

　　如果协方差矩阵为单位矩阵，则马氏距离简化为欧式距离；如果协方差矩阵为对角矩阵，也称为正规化的马氏距离。
　　2⃣️ 马氏距离的重要意义
　　（1）为什么要使变量去掉单位尺度？
　　（2）为什么马氏距离是与尺度无关的？
　　（3）协方差矩阵在马氏距离中的作用，为什么要使变量间线性无关？

二、匈牙利算法——解决二分图匹配问题
　　参考博文：匈牙利算法和带权重的匈牙利算法：https://zhuanlan.zhihu.com/p/62981901

　　
　　二分图：对于无向图G=(V,E)，如果存在一个划分使V中的顶点分为两个互不相交的子集，且每个子集中任意两点间不存在边 ϵ∈E,则称图G为一个二分图。

　　二分图如上图所示，黑线代表初步匹配的连线，因为需要1对1匹配，后续采用匈牙利匹配算法得到红线。
　　1⃣️ 简介
　　匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。
　　2⃣️ 匈牙利算法
　　每次执行得到的结果不一样，和顺序有关，得到的解不一定是最优解。下面以一个简单的例子作为说明：

　　（1）给左1号分配女生，先从右1 开始，右1仍是单身，所以匹配上
　　（2）给2号分配女生，从右2开始，能匹配上
　　（3）给3号分配女生，从右1开始，右1被占，问右2，右2也被占，那就先问问右1能否换人，左1说我和右2有连接，我可以让给你，但是我先问问右2肯不肯和我匹配，右2被占，那右2说我问问左2，左2可以和右3进行匹配，那问题就迎刃而解，2-3，1-2，3-1匹配上。
　　（4）给4号分配女生，从右3开始，依据上面的流程，发现1，2，3实在不能换人，所以4号就没法进行匹配。
　　示意图如下：