深度学习篇---匈牙利算法与OC-SORT

匈牙利算法与OC-SORT一个是解决“最优匹配”的经典运筹学方法另一个是赋予其动态场景“感知”能力的现代多目标跟踪框架。两者结合解决了一个核心问题如何跨时间将不同的“点”最合理地关联起来。 匈牙利算法高效的“最优分配”工具匈牙利算法是一个用于解决任务分配问题的组合优化算法核心目标是为指向明确的分配问题找到全局最优解。要解决的问题可以想象成有N个司机和N个订单每个司机完成不同订单花的成本时间、距离不同。如何将订单分配给司机才能让总成本最小这就是经典的“指派问题”问题的核心数据是一个N×N的代价或收益矩阵。核心思想通过数学变换找到最优分配。其基础是“效率矩阵变换定理”对代价矩阵的某一行或某一列的所有元素同时减去或加上同一个常数其最优解的分配方案不变。算法通过逐行逐列减去最小值创造“零成本任务”并最终在这些零元素中进行独立的、不冲突的分配。标志性操作寻找“零成本”任务的过程本质上利用了“康尼格Kőnig定理”在代价矩阵中覆盖所有零元素所需的最少直线数恰好等于最多能分配出的独立零元素个数。如果最少直线数等于任务数N就找到了最优解。在目标跟踪中的角色匈牙利算法是多目标跟踪框架如SORT、DeepSORT、OC-SORT中最常用的数据关联方法。具体来说它将前一帧所有“轨迹”的预测位置与当前帧所有物体“检测框”的真实位置进行匹配。这里的代价矩阵不再是人去完成任务的距离而是“预测位置”与“真实检测”的“不匹配度”通常由IoU交并比或马氏距离来衡量。算法的目标是找到一种全局最优的一一对应关系从而为每个轨迹分配一个正确的检测框。 OC-SORT应对复杂场景的“观测中心”跟踪法OC-SORTObservation-Centric SORT是一种为鲁棒性而生的多目标跟踪算法专门解决传统方法在遮挡和非线性运动场景下的脆弱性问题。核心的“观测中心”理念传统的跟踪算法以“预测”为中心高度依赖基于先前运动趋势的预测值。这在物体被短暂遮挡或做出急转弯时预测值会与真实位置产生巨大偏差导致匹配失败。OC-SORT则从“预测中心”转变为“观测中心”它更加信任目标检测器给出的实际检测结果并以此作为修正和恢复轨迹的依据。OC-SORT的三大关键技术以观测为中心的恢复ORU当目标在被遮挡后重新出现传统预测位置可能已经偏离很远。ORU策略会绕过不可靠的预测直接比较目标消失前最后一次“观测”到的位置和重新出现后的“观测”位置。如果它们在空间上足够接近便可以直接将轨迹和检测进行匹配实现快速、准确的轨迹恢复。以观测为中心的动量OCM标准匹配代价通常只看位置IoU距离容易在拥挤场景误匹配。OCM引入了“方向一致性”代价它评估历史“观测”运动方向与新候选“观测”方向是否一致。如果方向不符会给匹配代价增加一个“惩罚项”防止因空间邻近而错误匹配有效应对交叉运动。以观测为中心的重更新ORU/OCR目标被遮挡后其状态估计误差会持续累积。当轨迹被ORU恢复时“重更新”机制会回溯利用丢失期间的“虚拟观测轨迹”由关联前后的真实“观测”插值创建对卡尔曼滤波器的参数进行“事后修正”清除累积误差让轨迹更平滑、稳定。 两者关系与总结框图两者分工明确协同工作。OC-SORT的流程大致如下预测卡尔曼滤波器根据过往轨迹预测目标位置。构建代价矩阵计算预测位置与检测位置的“不匹配度”此时代价矩阵会集成OCM动量信息。匹配求解匈牙利算法出场根据代价矩阵解出最优的匹配方案。后处理对未成功匹配的轨迹和检测利用ORU恢复和OCR重更新等机制进行“补救”性匹配。总结框图如下总结来说匈牙利算法作为一个高效的全局优化器确保了在任意时刻的匹配在数学上都是最优的。而OC-SORT则是在它周围构建了一整套以“观测”为中心的容错和修正机制让整个跟踪系统在面对真实世界的复杂情况时具备了强大的鲁棒性。