【多传感器融合】匈牙利算法

匈牙利匹配算法

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。
匈牙利算法（Hungarian Algorithm）采用了二分图法的思想，具体来说，Hungarian Algorithm 是一个递归过程，尽可能找到让上一帧与当前帧目标一对一的匹配。该算法对红线连接的准确率要求很高，也就是对运动模型和表观模型要求较高，需要将置信度较高的对象匈牙利算法进行匹配，才能得到比较好的结果。
（1）初始化二分图 即将当前帧中可能与上一帧中目标匹配的检测框确认，如图 3-9（a）；
（2）按照 ID 顺序依次进行匹配 首先将可能与上一帧目标 1 相匹配的当前帧的目标 1 进行匹配（红色代表已经匹配）。如图 3-9（b）；
（3）对目标 2 进行匹配 如图 3-9（c）；
（4）对目标 3 进行匹配 这时发现当前帧中可以与目标 3 进行匹配的目标 1,2 已经被匹配过了，为了使目标 3 可以匹配到目标，尝试将之前 U 中匹配到目标 1 的目标与另一个目标匹配（黄色代表取消匹配），如图 3-9（d），这时发现 U 中的目标 1 可以匹配到的 V 中的目标 2 也已经被 U 中的目标 2 匹配到了，那么同理，在将 U 中的目标 2 更换匹配目标，如图 3-9（e），这时再返回上一步，即可将 U 中的目标 1，2，3 均匹配到目标，如图 3-9（f）；
（5）对目标 4 进行匹配 与上述步骤相同，但是最后并没有找到能够符合要求的匹配方法，所以 U 中的目标 4 在这一帧中消失，同时当前帧中的目标4 被视为新出现的目标。

bool find(int x){
	int j;
	for (j=1;j<=m;j++){   
		if (line[x][j]==true && used[j]==false){
			used[j]=1;
			if (girl[j]==0 || find(girl[j])){ 
				girl[j]=x;
				return true;
			}
		}
	}
	return false;
}
//下面是主程序

for (i=1;i<=n;i++)
{
	memset(used,0,sizeof(used));    //这个在每一步中清空
	if find(i) all+=1;
}

2. 自动驾驶结合

   在自动驾驶中，不同传感器每一个周期返回不同的目标，相互之间如何匹配呢，对于同一个传感器而言，一般都有不同目标对应的ID，但是在夸传感器之间就没有这么幸运的事，另外融合了所有传感器的目标之后我们自己的输出，也需要目标和目标之间的配准，这中间都可以应用匈牙利匹配的方法实现。

   之前的文章中有介绍多目标的融合方法：传感器数据融合，当时只是把融合的方法进行分类，并没有介绍一种行之有效的操作手册，那这里我来阐述一下我的一个思路：

我们有一个目标模型：，其中 u 和 v 分别代表目标中心的水平和垂直像素位置，而 s 和 r 分别代表目标边界框的比例（面积）和纵横比，这里是和一个固定尺度进行比较，一般选最大的区间，使得归一化到统一的模型中。后面的是通过kalman滤波进行跟踪之后的结果。
采用匈牙利匹配对这些目标进行匹配，这中间不同目标之间的好感度，我们采用预测边界框之间的交并比（IoU）来计算，当然我们也不会一位的进行配对，需要设计最小交并比（IoU），也就是说交并比太小我们没有必要强行匹配。
文章发现边界框的 IoU 距离隐式处理由目标经过引起的短时遮挡。具体地说，当遮挡物盖过目标时，只检测到遮挡物。尽管隐藏目标离检测框中心更近，但 IoU 距离更倾向于具有相似比例的检测。这使得可以在不影响覆盖目标的情况下，通过检测对遮挡目标进行校正。
当目标进入和离开图像时，需要相应地创建或销毁唯一标识。对于创建跟踪程序，文中认为任何重叠小于 IoUmin 的检测都表示存在未跟踪的目标。使用速度设置为零的边界框信息初始化跟踪器。由于此时无法观测到速度，因此速度分量的协方差用较大的值初始化，反映出这种不确定性。此外，新的跟踪器将经历一个试用期，其中目标需要与检测相关联以积累足够的证据以防止误报的跟踪。
最后的最后，我们对于一个对象的建立和销毁，需要加入延时判断，这样才不会让我们的目标来回跳动，增加目标融合的稳定性。

参考文献
https://blog.csdn.net/zhouyy858/article/details/103830741
https://blog.csdn.net/dark_scope/article/details/8880547