多目标跟踪中的目标匹配算法

FunnyWii
FunnyWii
发布于 2024-08-21 / 79 阅读
0
0

多目标跟踪中的目标匹配算法

多目标跟踪算法

自动驾驶领域中的目标跟踪算法都是多目标跟踪算法,即MOT(Multiple Object Tracking),因为在这种场景中要跟踪的目标往往是多个,也有些文献会把MOT称为MTT(Multiple Target Tracking)。

MOT问题中并不是所有目标都会在第一帧出现,也并不是所有目标都会出现在每一帧。那如何对出现的目标进行初始化,可以作为跟踪算法的分类表征。常见的初始化方法分为两类:DBT(Detection-Based-Tracking)和DFT(Detection-Free-Tracking),主要区别在于初始化是使用模型检测到的结果还是手动初始化。

此外,MOT的处理模式也分为两类:Online和Offline。Online Tracking对视频帧进行逐帧处理,当前帧仅利用过去信息;Offline Tracking会利用前后视频帧的信息对当前帧进行目标跟踪,所以这种方法只适用于视频流,而不能用于实时的摄像头。

MOT算法就先简单介绍一下,后面再深入(主要是因为我也刚开始学...

目标匹配算法

当前主流的MOT框架都是DBT框架,这种框架依赖于数据关联算法,即目标间的匹配结果。良好的匹配结果能保证目标ID的连续性,由此可见目标匹配是MOT中的重要环节。当前目标匹配算法以偶图匹配为主。

假设帧中只有一辆车,那么一直进行目标检测是OK的,下图黄色车辆ID会一直为1。

不过当帧中出现第二辆车,这种方法就寄了。

匈牙利算法

利用增广路找最大匹配的算法,就叫做匈牙利算法。匈牙利算法是专门用来求解指派问题的算法,通常用于求解二分图最大匹配。最大匹配即一个图所有匹配中,所含匹配边数最多的匹配。

简单描述一下:每个点从另一个集合里挑对象,没冲突的话就先安排上,要是冲突了就用增广路径重新匹配。重复上述思路,直到所有的点都找到对象,或者找不到对象也找不到增广路[8]

二分图

又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边所关联的两个顶点i和j分别属于这两个不同的顶点集(i∈A, j∈B),则称图G为一个二分图。下图就是一个典型的二分图:

下图乍一看不是一个二分图,其实也是一个二分图,转化一下,就会发现它其实还是一个二分图:

增广路和交替路

  • 交替路:从一个未匹配点出发,依次经过非匹配边->匹配边->非匹配边形成的路径

  • 增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路

增广路的性质:

  1. P的路径长度必定为奇数,第一条边和最后一条边都不属于M,因为两个端点分属两个集合,且未匹配。

  2. P经过取反操作可以得到一个更大的匹配M’。

  3. M为G的最大匹配当且仅当不存在相对于M的增广路径。

算法流程

趣写算法系列之--匈牙利算法_匈牙利算法基本原理-CSDN博客 这篇博客写的非常好,没有公式,只用了几张图片,非常方便理解。

配对流程我们以下面这个二分图为例,图中蓝色连线代表的不是已匹配的边,这是一种初始匹配状态,所以蓝色连线是非匹配边

开始匹配,先给A匹配,A和a会进行匹配,用红线将两者连起来,这条边变成了匹配边。但是接下来,B也想和a匹配,这就产生了冲突,交替路和增广路可以用来解决这个冲突。

找一条交替路,即依次经过非匹配边(蓝线)、匹配边(红线)。那么我们从B出发找交替路:

(非匹配边) (匹配边) (非匹配边)

B-------------------a-------------------A-------------------c

B和c都是未匹配的点,而且它们又是这条交替路的起点和终点。那么这条交替路就是增广路。现在进行一个取反操作,将上面这条增广路的匹配边变成非匹配边,非匹配边变成匹配边

(匹配边) (非匹配边) (匹配边)

B-------------------a-------------------A-------------------c

就得到了下图,A和c匹配,B和a匹配:

增广路最重要的特点是“起点&终点都是非匹配点”,这样就导致非匹配边比匹配边多了一条。由于增广路建立连接时,必须建立在两者有初始匹配的基础上,如果取反,就又得到了一条匹配边。取反的过程就是把原本匹配上的两个人拆散,给第三个人腾位置。

接下来对C进行匹配,C要和c匹配,又产生了冲突,把上述过程再进行一次:

(非) (匹) (非) (匹) (非)

C--------c--------A--------a--------B--------b

取反得到:

(匹) (非) (匹) (非) (匹)

C--------c--------A--------a--------B--------b

得到下图,ABC三个节点全部匹配完成,且找到了最大匹配。

KM(Kuhn-Munkres)算法

相比匈牙利算法,KM算法是带权二分图匹配。权重,可以理解为加了一种约束。KM算法用于求解二分图的最优匹配。如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。完美匹配一定是最大匹配,但并非每个图都存在完美匹配。

KM算法会建立一个图,其中有前一帧和当前帧的Node,然后计算两帧的Node间的距离,这个距离越小,代表两帧Node间更大概率的匹配。下图以Camra和LiDAR融合为例:

距离矩阵

用一个距离矩阵为例:

成本矩阵

  1. 每行减去最小值,第一行减9,第二行减5,第三行减3:

步骤1

  1. 每列减最小值,第一列减1,第二列减6,第三列减0:

步骤 2

  1. 以最少数量的线,划掉所有零:

步骤 3

  1. 若 线数>=矩阵行列数,To Step 5;否则,在矩阵中减去最小值,若有0被交叉,则加上最小值:

步骤 4

上图可以看出,剩下的[3, 7 ; 5, 2]全部减了2,同时线条交叉的部分加了2。再划线:

步骤 4 之二

  1. 线数==矩阵行列数时,找只有一个0的行(按照作者所说,这种方法最终必定只有一行只有一个0),即第二行,WorkerB<->Job3,对应完成后删除该行。最终匹配为:

WorkerA<->Job2

WorkerB<->Job3

WorkerC<->Job1

距离的计算

  1. 欧氏距离,即Bounding Box的中心点距离。但不能处理目标形状发生变化,或目标与其他目标重叠的情况。

欧几里得距离

  1. IOU,交并比。这种方法会让我们要解决的问题从寻找最小Distance变为寻找最大IOU。

借条,

  1. Convolution Cost

使用CNN来查看Bounding Box内的图像,也是DeepSORT使用的算法。但是既然使用了CNN网络,会有更高的计算成本。相比SORT算法,DeepSORT算法会使用BBox内的外观信息。

深

Corner Case

若前帧出现了3个目标,后帧出现了4个目标。也就是从NxN问题,变成了NxM的问题。

解决办法是取整个矩阵最大值,填充新的列:

纳米

最大值和最小值

如果使用IOU,想进行最大IOU匹配;或者有相似性Cost,想进行最大相似性匹配。方法是取矩阵中最大值,并用这个最大值减去当前位置的值。

最大化

参考文章

[1] 多目标跟踪中的数据关联代码实践(上) | 见渊の博客 (huangpiao.tech)

[2] 【小白学习笔记】(一)目标跟踪-匈牙利匹配 - 知乎 (zhihu.com)

[3] 多目标追踪:DBT、DFT、基于Kalman和KM算法的后端优化算法、SORT/DeepSORT、基于多线程的单目标跟踪的多目标跟踪算法KCF_基于检测的跟踪范式(dbt)-CSDN博客

[4] Luo, W., Xing, J., Milan, A., Zhang, X., Liu, W. and Kim, T.K., 2021. Multiple object tracking: A literature review. Artificial intelligence, 293, p.103448.

[5] Exactly how the Hungarian Algorithm Works (Self-Driving Cars Example) (thinkautonomous.ai)

[6] 趣写算法系列之--匈牙利算法_匈牙利算法基本原理-CSDN博客

[7] 【学习总结匈牙利算法到KM算法】_km匈牙利-CSDN博客

[8] 简单理解增广路与匈牙利算法 - 知乎 (zhihu.com)

[9] 匈牙利算法 | Origin of Ray (sunra.top)

[10] 二分图 - CUC ACM-Wiki (cuccs.github.io)


评论