一.卡尔曼滤波
追踪算法中一个重要的方法叫卡尔曼滤波。追踪任务中既要检测到每一帧检测结果，还要看是否还是原来的人，如果是的话，id不变。
观测值一般是发生观测到的值(例如传感器测到的值);估计值是数学模型预测出的值;这二个值都会有误差。卡尔曼滤波最终就是在这二个都有误差值之间求出最优结果来。
二.任务本质分析
(1)先举个数学上的例子
已知一辆小车在行走，当前初始状态向量有二个,一个是位置x,另外一个是速度v;现在要预测下一时刻的位置x1与速度v1。
解：设两个时刻的时间差为t，设小车的加速度是u,所以有公式：
公式1：x1=x+vt+(1/2)ut的平方;其中公式中的vt+(1/2)ut的平方表示在加速度为u的情况下驾驶时间为t的加速度距离，x是开始的距离
公式2：v1=v+ut
对这二个公式转为矩阵表达式为：
[x1 =[1 t [x +[(1/2)*t的平方 *u
v1] 0 1] v] t ]
对这个矩阵公式中的 f=[1 t ; b=[ (1/2)*t的平方
0 1] t ]
其中f与b叫状态转移矩阵，如果先定义好这二个矩阵，以后化简公式时就比较方便了，我们下一时刻的状态更新以转移矩阵决定的。
这个例子的小车也可以换成人或其它动物。
任何状态都会受外部环境的影响(例如车压到石头<噪声>，即会出现误差)，它的状态通常呈正态分布。受误差影响后的两个状态公式变成：x2=x1+w ,v2=v1+j ,其中w与j分别表示距离与速度误差。
这时我们把x2与v2是观测值(例GPS等传感器预测的数据)，x1与v1是数学模型预测出来的估计值<卡尔曼滤波公式算出>。但观测值与估计值都会有误差，那现在怎么做呢？答案就是这二个值中分别乘以权重求和，这也是卡尔曼滤波的本质，其本质是基于估计值与观测值进行综合(如下一帧帧检测与下一预测值)。
三。基于观测值进行最优估计
(1)估计值不可能指定一个具体值，只能指定某个均值构成的正态分布的图表示，如果不确定性越大，方差(正态分布图中与X轴平行的线段)将越大; 观测值(例如GPS传感器预测的数据)也服从正态分布;这时要求求出更准确值，那就是等以这两个分布的乘积(像是取交集)作为最优估计值。这里的最优化估计值也是会服从正态分布。
(2)假设z1为先验估计, z2为后验估计(用观测值进行修正)。这里的先验估计z1就是类似数学模型中算出来的估计值,然后存在一个y的观测值(例如GPS传感器预测的数据),因为先验值与观测值y都有误差,所以现在用预测值更新先验值z1后就得到后验估计值(最优估计)，后验估计是指对预测值与估计值优化后的最后结果。
公式为：z2=z1+k(y-c*z1) ,这里z1就类似等以前面的x1或x2,y是预测值,k是卡尔曼滤波的增益(权重)。由公式可知k将决定观测值对数学模型出来的先验值更新的分量，例如当k=0时，说明不用预测值y进行更新先验值。
四。预测与更新操作
(1)两大核心模块
1）第一个核心模块就是前面求解x1与v1的公式(其中用到的状态转移矩阵)，即x1=x+vt+(1/2)ut,v1=v+ut转为通用矩阵形式 g=Ax+Bu，另外一个是其协方差,公式即p1=fp0(f的转置)+q,其中p0表示前一时刻的协方差矩阵，q是高斯分布的噪声矩阵<不可控的因素>。p1是协方差矩阵。这二个公式分别告诉我们状态变了，同时联系<关系>也在变化，所以都会在不断地更新。
例如一个人的坐标点为x,y,框的大小是w,h，那预测下一时刻时的状态，它的坐标变化肯定会与w,h有关吧，不可能下一时刻w,h就突然变大或变小吧，这就是告诉我们这二组变量之间是有联系的，这些联系<关系>我们就用协方差矩阵。协方差矩阵我们一般是用对角矩阵表示，对角线上的值是方差,非对角线的值就是自己<行向量>与自己<列向量>的关系。协方差矩阵就是表示各个变量之间的关系变化情况。
预测阶段：预测状态估计值及其协方差<预测下一状态间的关系>。
在单状态中,协方差矩阵就是其方差。
第一个核心中的二个公式(g的计算与p1的计算)是预测阶段的，预测状态与状态间的关系是卡尔曼滤波的第一步。第二个核心公式就是更新阶段的。
2)第二核心模块是更新状态与状态间的关系。其公式包括k=(p1c的转置)/cp1c的转置+r, g1=g+k(y-cg)，p2=(i-k*c)*p1 三个公式，其中r是噪声矩阵，c是状态转移矩阵。这三个公式都要每一帧更新的。g1与p2都会与k相关,k又与p1与c相关。
第二步是基于预测值更新参数，预测完需要根据观测值来修正，修正后的状态值去估计下一帧。
五。追踪中的状态量
(1)卡尔曼增益公式 k=(p1c的转置)/cp1*c的转置+r ,它的目的就是让最优估计值(后验估计)的方差(不确定性)更小，k相当于一个权重项,该怎么利用先验估计与传感器返回的预测结果(观测值)共同决定实际的最优结果。卡尔曼增益决定了卡尔曼滤波的核心作用。
对k进行化简：当观测没有噪声时(即传感器返回的值是百分之百时),也就是用观测值付给先验值，这时观测值就等以后验值(最优估计)了。化简步骤：当噪声r趋近0时，取k的极限，分子与分母约分后，得到的值是c的倒数(即c分之1)，c是状态矩阵(单状态,匀速)。实际中噪声都是会存在的。
(2)追踪例子：
1)追踪问题需要考虑的状态：<1>均值(Mean):8维向量表示为 x=[cx,cy,r,h,vx,vy,vr,vh]
<2>中心坐标(cx,cy)，宽高比r，高h,以及各自的速度变化值组成。
<3>协方差矩阵:表示目标位置信息的不确定性,由88的矩阵表示，88就是对应<1>中构成的8行8列。因为有<1>中的8维向量，所以肯定是8*8的矩阵，即每一个与自己的(如1行1列,2行2列,3行3列,4行4列.......)，每一个与其它7个。
<4>追踪过程也要分为两个阶段：1>每一个track(跟踪，路线，踪迹等意思)都要预测下一时刻的状态,并基于检测到的结果来修正(匀速,线性,咱们追踪通常都是一帧一帧<这样才线性与匀速，不能一下3帧一下8帧>处理的)。
<5>初始化的状态转移矩阵(8*8)上的对角线值都是1
六。匈牙利匹配算法概述
(1)卡尔曼滤波只是给到我们估计。假设知道当前一个人A的状态，那下一帧在前面出现2个人时，到底是那一个人才是A呢？这就关系到匹配问题了，这里用的匹配算法叫匈牙利匹配。
(2)目标检测算法detr中也会用到匈牙利匹配算法。匈牙利匹配算法有如下几点：完成匹配的同时最小化代价矩阵(类似田忌赛马)，当前帧检测到的目标该匹配到前面那一个移动路径(track)呢？感觉有时候并不是最优分配，而是尽可能多(广)的分配。
(3)规则:如果代价矩阵的某一行或某一列同时加上或减去某个数，则这个新的代价矩阵的最优分配仍是原代价矩阵的最优分配。按这条规则得到5个小法则:1)对于矩阵的每一行，减去其中最小的元素。2)对于矩阵的每一列，减去其中最小的元素。3)用最少的水平线或垂直线覆盖矩阵中所有的0，这里不一定行或列的所有元素都为0才能画水平线或垂直线(有一个0就可以画了)，但满足最最少方法画完(例能二条画完就别3条来画)。4)如果满足3)的所有线的数量=n，则找到了最优分配，算法结束，否则(例是3行3列矩阵，但满足的线只有2，则3不等以2)进入5)。5)找到没有被任何线覆盖的最小元素，每个没被线覆盖的行的所有元素减去这个元素，每个被线覆盖的列的所有元素加上这个元素，返回步聚3)
(3)匈牙利算法小例子。
例子:给3个人分配3个任务，就可列出3行3列的代价矩阵，现在得到那个人做那个任务能使得代价矩阵最小呢？(就比较花的时间最少吧)，例人a做任务1，2，3的时间分别为15，40，45;人b做任务1，2，3的时间分别是20，60，35;人c的时间分别是20，40，24。这个例子就先构成一个三行三列矩阵后，然后可以用(2)中的5法则来画，得出0对应的独立行或列元素即可。
(4)代码中可直接调用。sklearn中:linear_assignment();
scipy中:linear_sum_assignment();
即只要构建出代价矩阵后，就可调用这二个方法了。
(5)如何构建出代价矩阵呢？主要是这三个方法:运动信息匹配(卡尔曼估计);外观匹配(reid);iou匹配(bbox)。其中reid是deepsort中最核心的内容，redi主要是对特征向量之间做余弦相似度(余弦距离)计算。余弦距离是计算向量间的夹角，余弦距离的取值范围是[0，2]，两个完全相同的向量余弦距离是1，完全不同就是0。iou匹配就是后验结果与检测出来的结果取交，并集得出更符合的检测结果。
七。reid特征
人行重识别模型(reid)做人的特征提取效果是很好的，当输入的bbox经过这模型提取特征后，返回128维向量。这个模型适合人的，像想对汽车提取的适就不适合，需自己重做一个。
特征有如下几点:
(1)据当前检测的所有bbox与当前所有track，先得到其所有reid特征(2)当前每个track圴存了一个特征序列(每次匹配都会保留一份特征)(3)track保存的特征数量是有上限的，默认100个。
八。sort与deepsort建模流程分析
(1)追踪任务的基本流程
目标检测+追踪(对检测的bbox提取各项特征后进行匹配)
(2)sort算法只用到运动信息与iou匹配，没有用最关键的reid，所以容易搞错。
(3)deepsort中用到matching cascade(级联匹配)。它原理是下一帧检测的多张图像会优先分别与前面的丢失帧数最少的track进行匹配。
九。预测与匹配流程解读
级联匹配:代价函数由运动特征(卡尔曼估计）与reid特征计算的距离组成的。匀速模型才能用deepsort，因为卡尔曼预测是基于匀速模型的。
级联匹配的条件是某个track只有连续3帧匹配上(即进入确认状态)的才进行级联匹配的<与detections匹配>，匹配完才进行iou匹配;如果小于3(非确认状态）就直接iou匹配。
级联匹配参数中默认上限是70。
十。追踪任务流程折解
(1)第一帧:检测得到10个bbox(bounding box的缩写)，此时没有track。(对每一帧的目标检测结果，都会经过nms与置信度阈值来筛选);不会执行任何deepsort追踪操作;对当前10个检测结果分别初始化track。前面说的bbox就是有x,y,宽与高四个值组成的矩形框(边界框)，分为初始bbox，跟踪bbox(跟踪算法后预测后续帧的结果)，物体检测的bbox
(2)第二帧:检测得到11个bbox，如何跟上一帧初始化的track匹配呢？进行iou匹配(级联匹配需要对确认状态的track，但现在还没有);此时匹配到10个track，注意匹配到的别忘了更新其卡尔曼参数;还有一个bbox没匹配上，此时为其新建一个track
(3)第三帧:检测到12个bbox，当前还没有确认的track;前面创建了11个track需继续与12个bbox进行iou匹配;其中一个track没有匹配上(此时它是非确认的，将直删除);有10个track已经命中3次了，将其状态更新"确认"。
(4)第四帧:检测到14个bbox，不仅需要做iou还要做级联匹配;对前面10个确认状态的track进行级联匹配(优先)，然后再iou;只有确认状态的track才会可视化在输出结果中;注意每次匹配到的track一定要更新其卡尔曼参数
总结:<1>检测得到当前帧的bbox(其实追踪的好坏主要取决于检测结果)。<2>track分为确认与非确认二种。<3>对于确认状态的要先进行级联匹配，它们优先级高，连续70帧没有匹配上会删除。<4>代价矩阵包括reid特征构建的余弦距离与运动信息构成的马氏距离。<5>对于级联匹配玩剩下的和当前是非确认与剩下的bbox进行匹配<6>经过级联与iou匹配后就得到了所有匹配结果，别忘了更新track的卡尔曼参数。注意这里所说的卡尔曼参数是指卡尔曼滤波的两大核心中的更新内容(上面所说的k，g1，p2三个值)。
版权归原作者 weixin_58351028 所有， 如有侵权，请联系我们删除。