Subtract row minima（减去行最小值）：对于每一行，找到该行的最小值，然后该行的数都减去这个最小值。
Subtract column minima（减去列最小值）：对于每一列，找到该列的最小值，然后该列的数都减去这个最小值。
Cover all zeros with a minimum number of lines（用最少的线覆盖所有的0）：用最少的水平线和垂直线覆盖掉矩阵的所有0元素。
如果线的数量等于N，则找到了最优分配，算法结束，否则进入步骤5
Create additional zeros（创建额外的0元素）：找到没有被任何线覆盖的最小元素，所有未覆盖的元素中减去这个数字，并将其添加到所有被覆盖两次的元素中，返回步骤3

举个实例：假设有3个工人和3个任务，每个工人可以完成每项任务的不同工作量。我们的目标是将工人分配到任务上，使得总工作量最小。

4.有三条线段才能覆盖所有的0，即符合=N，算法停止。

5.对应到原始矩阵，得到的匹配为 [工人1-任务2，工人2-任务1，工人3-任务3]，工作总量为：2+2+1=5.

二、DeepSort算法

流程图：

算法步骤：

第一帧：进行初始化，使用目标检测模型检测出当前帧中目标，并进行预测，每个track中包含id、检测框、feature、预测框），并且每个预测框的状态为unconfirmed。

第二帧：目标框与Tracks里的预测框进行IOU匹配，之后进行连续三帧的IOU匹配。匹配成功后，使预测框的状态由unconfirmed转变为confirmed，然后进行级联匹配。如果三次IOU匹配没有成功，有两种可能：一种是Unmatched Tracks（检测器漏检）；一种是Unmatched Detections（出现新目标或者是目标被长时间遮挡），更新轨迹。如果是第一种就要先检查状态，状态为Unconfirmed，即超过30次（max_age)匹配都没有成功，就直接删除（默认该目标已经消失）。剩下的帧进行循环操作。

必备知识：

级联匹配：

相比于Sort算法，DeepSort算法还利用了级联匹配，也就是添加了feature 匹配，利用reid模型进行特征提取。主要思想是通过利用目标的特征向量相似度和位置信息，将当前帧中的目标与已跟踪的目标进行匹配，从而实现准确的目标跟踪。

级联匹配流程图里上半部分就是特征提取和相似度估计，也就是算这个分配问题的代价函数。主要由两部分组成：代表外观模型的Re-ID特征和代表运动模型的马氏距离。

级联匹配流程图里下半部分匈牙利算法数据关联作为流程的主体。也就是说，对于没有丢失过的轨迹赋予优先匹配的权利，而丢失的最久的轨迹最后匹配。

第一步：使用目标检测器（如YOLO、SSD等）检测当前帧中的目标，并提取其特征向量（如使用卷积神经网络提取的特征向量）；使用卡尔曼滤波器对每个已跟踪的目标进行位置预测，将检测框和预测框内的结果对应的图像送到REID网络中，计算当前帧中每个目标的特征向量与已跟踪目标的特征向量之间的相似度，常用的度量方式是余弦相似度或欧氏距离，用于衡量目标之间的相似程度，用代价矩阵来表示，这里记为C。
再去计算检测和预测结果的马氏距离，然后根据统计学和实验所得的阈值，去除掉不符合马氏距离和余弦距离阈值的匹配项。（这里马氏距离仅仅作为去除不符合的匹配项而已）
第二步：根据矩阵C的结果使用匈牙利算法进行检测框和预测框的匹配，目标是找到使总相似度最大化的最佳匹配。
进行更新。

三、 ByteTrack算法

主要思想：

ByteTrack算法与DeepSort算法相比，没有了级联匹配（feature匹配），只有IOU匹配，并保留所有的检测框（因遮挡存在的低分的目标框也会保留并作匹配）。目的是利用低分框和未匹配上的框进行再次匹配，来减缓遮挡导致目标丢失的问题。同样也是使用卡尔曼滤波算法进行预测。

该算法主要分为两个阶段：检测阶段与跟踪阶段。在检测阶段，使用一个特殊的CNN模型来识别图像中的目标，该模型可以同时输出目标的类别和位置信息。在跟踪阶段，提出了一种名为BYTE的数据关联方法，利用每个检测框与轨迹的相似性来恢复真实目标并过滤掉背景检测，并且将目标框分为低分框和高分框，利用低分框和跟踪轨迹之间的相似性，从低分框中挖掘出真正的物体，过滤掉背景。