计算机视觉中低延迟该如何检测？

计算机视觉中低延迟检测的相关理论和应用（上）

写在前边

之前在专栏的第一篇文章中介绍了一下关于层模型（layered model）的工作，并给自己挖了几个坑。今天让我来填其中一个坑：视频中的物体低延迟检测。由于这一系列工作目前贡献了一篇cvpr17和一篇iccv19共两篇论文，我将分上下两篇文章分别介绍，希望可以把工作的背景、思路、坑、相关思考和一些不在论文发表内容中的故事说明白。还是和上一篇一样，希望写出来的的不是机械的公式或者吹得天花乱坠神乎其神的PR，而是一些原理性的东西以及背后思考的过程。

低延迟检测是视觉任务工程化落地不可能绕过的一个问题。总体来说，对于任何检测（不只是视觉）任务来说，延迟和误报率大概有这样一个关系：

这个关系不难理解，不只是视觉问题，世间万物，更长的决策过程（delay）往往能带来更高的准确度，但是这个更长的决策过程也会带来更大的延迟。两者之间的平衡，对很多需要在线决策（online process）的系统来说非常重要。例如生物视觉，假定一个动物检测到掠食者就需要逃跑，如果追求低误报率，就要承担高延迟带来的风险，有可能检测到掠食者时为时已晚无法逃脱；如果追求低延迟，虽然相对安全，但是误报率高，有一点风吹草动就犹如惊弓之鸟。

Motivation: Biological Vision

这样的决策过程对自动驾驶的重要性不言而喻。在检测障碍物的过程中，既不可能等到撞到再刹车，也不可能随便看到什么像障碍物的东西就刹车。比如下边这个uber自动驾驶出的致命事故，在车辆撞到行人的那一刻仍然没有准确检测道障碍物，这样的延迟显然不能接受。

对于一般的视觉任务来说，更高的准确度往往可以通过加大模型来达到；但是对于实际应用来说，提高模型准确率难上加难（不少任务涨点1%已经是突破了），但是多从相机抓取一帧几乎没有任何成本。把两帧的结果合并到一起，总体准确率显然比只用一帧要高。所以，一个简单的思路在于，当出现了一个可能的目标，系统需要在“宣布检测到目标”和“多等一帧看看”之间做出决断。这篇专栏介绍的工作，就是要解决这样一个决策过程。

背景理论

幸运的是，现有的信号处理理论中已经对这个问题有了很好的建模（参见Quickest Change Detection Theory [1]）。在这里我不放大段数学，只概括一下大概思路和结论。没有兴趣的话，可以直接跳到下一部分看算法结果。

让我们假设一个系统的初始状态为 ，在某一个未知的时间点转换成 。例如自动驾驶，没有障碍物的情况为，有障碍物的情况为 。而在某个未知的时间 （障碍物突然出现的时刻），系统会从 转换成。这时检测系统的目标，是探测这种状态的转换。假设输入的信号是 （对视觉问题来说，每一帧就是信号），这样一个检测问题就可以由这样如下假设检验来描述：

其中 为当前时刻，分子代表转换已经发生的概率，分母代表转换还未发生的概率。如果在同状态下的 是独立同分布的，这样一个似然比检验（likelihood ratio test）就有如下形式：

这里的数学符号都很简单，不超出本科数理统计的内容，就不多做解释了。在这种概率建模下，似然比可以作为一个用于决策转换是否发生的统计量。当似然比大于某个阈值，即可宣称系统发生了变化（declare a detection），反之则等待新的信号输入。实际操作中，我们对右边的表达取log，连乘变成连加，更加方便。总体来说，决策过程如下边这个框图

这套理论有两个特别好的点。首先，这一个似然比检验可以获得理论上渐进最优的解。也就是说，在同一个误报率下，这个检测方法可以获得理论上最低的延迟；而在同样的延迟下，这个检测方法可以获得理论上最低的误报率。这就给把这套检测方法用在视觉系统中提供了很好的理论保障。其次，这套理论提供了一个递归解。在实际应用中，这个递归解可以让上边公式关于 取max的操作无需遍历所有 ，具体的数学表达比较复杂，建议有兴趣的朋友直接参考[1]。

移动物体检测

这一部分介绍一下17年CVPR的论文《Minimum Delay Moving Object Detection》[2]。在这片论文中，我们把这套低延迟检测的统计理论用在了移动物体的检测上。对于移动物体，我们的核心思路一向是使用光流进行描述。这是因为，光流可以有效带来移动物体的分割信息。比如下边这个海洋生物的例子，如果只通过外观对单帧进行像素级的分割，结果可以说是狗屁不通，但是通过光流分割，就可以准确获得物体边界。

特别地，两帧之间的光流比较不稳定，而将多帧的光流组合到一起，就可以看到非常稳定的分割边界，这也符合上一节所说的，延迟越高越准确，例如下边这个例子：

左：视频；中：帧到帧的光流；右：多帧组合的光流

在我们的建模中，把帧与帧之间像素的对应关系，用以下方法进行描述：

其中 是与视频内容无关的i.i.d.高斯噪声。在这个模型中，如果视频中只有一个整体的背景，则通过一个统一的运动模式 就可以描述两帧之间的对应关系；而如果视频中有背景+移动物体，则需要对背景和移动物体分别取 ， 两种不同的运动模式，才能够描述两帧之间的对应。理论上，我们可以建立无数组 对多个目标同时进行检测。但是由于算力所限，这篇文章只做了前景/背景的二元分割。这样一来，我们就可以建立如下两组概率进行似然比检验。

其中 是robust norm，对信号处理不了解的朋友可以直接无视。当然，这两个公式只是方法的基本原理。工程方面细枝末节的trick在这里就不多说了。总体来说，当视频出现移动物体时，似然比统计量会显著增加，而到达某个阈值后，算法则输出移动物体的探测结果。下边直接放一下结果，还蛮有趣的：

视频链接：https://www.zhihu.com/zvideo/1282335357196140544

通过改变不同的阈值，算法可以自由选择不同水平的误报率和延迟。如果我需要低延迟而可以忍受高误报率，就选择较低的阈值，反之亦然。通过改变阈值，我们就可以画出如下的误报率-延迟曲线。这条曲线的结果还算比较符合理论的。可以看到，在各误报率下，我们的算法都可以达到更低的延迟。

后续和一些感想

首先还是说一下这个工作里的坑。说实话，这样一个工作更大的意义是学理上验证了这套理论在视觉中的应用，距离工程上的应用，还有很大的距离。部分原因在于，由于工作完成的时间是2016年，当时还没有成熟可靠的快速光流算法和分割算法。而这个工作需要大量的帧到帧之间的运算，所以在实际运算时间上可以说是惨不忍睹。第二点，如果仔细看过上边的结果视频，不难发现，composed motion经常出现重影，对分割结果造成影响。这也直接促成了我们用layered model解决移动物体分割的后续工作。关于这种重影，我会将来填“详解移动物体分割、光流和遮挡之间的联系”坑的时候详细介绍。

低延迟的检测是我2015年本科毕业后，零计算机基础入坑视觉做的第一个工作。当时我的博士导师给我扔过来三篇论文，让我挑其中一篇最感兴趣的当科研方向，[1]就是其中一篇。现在回头想想导师也算是看得起我，一上来扔过来的都是这样“硬核”的内容。搞这个工作的时候，其实相当头疼，毕竟作为一个零基础的学生，一上来就要平地起高楼做一个从没有人提出过的问题，从白纸开始写代码，自己收集数据集，找人做的标注，由于没有相关工作，还要从其他方法中创造baseline，总体来说很有挑战性。虽然相比直接从深度学习入坑CV的同学，这让我对采用不同思路决视觉问题有更多想法（这在之后的科研过程中帮了大忙），但是也让我错过了17年之前深度学习“随便做做就能发文章”的爆发期。不过，在之后的专栏中，我会介绍如何把低延迟检测的理论和基于深度学习的检测器进行结合，让这套理论在视觉问题上真正变得可用。

参考资料

[1] V. V. Veeravalli and T. Banerjee. Quickest change detection. Academic press library in signal processing: Array and statistical signal processing, 3:209–256, 2013.

[2] Dong Lao and Ganesh Sundaramoorthi. Minimum delay moving object detection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4250–4259, 2017.

计算机视觉中低延迟检测的相关理论和应用（下）

写在前边

今天接着上一次写的东西，继续聊一下视觉中低延迟检测的相关理论和应用。在介绍自己的具体工作之前，我觉得还是有必要把一些想法放在前边作为一个引子。

近年来AI领域的整体风气，客观上鼓励作者对论文进行商业广告式的包装。论文除学术价值外，还要考虑读者的接受度和吸引眼球程度。这种风气下，诚实写出一些深层次的思考，或者对论文的局限性进行分析，无异于授人以柄的自杀行为。我曾经遇到过，某审稿人直接把论文Discussion章节中的算法局限性无脑写进拒稿意见，也遇到过论文提出的方法冒犯到某些审稿人的情况。这种整体风气，对领域的发展是绝对有害的。

为什么要说这一段话呢？因为今天介绍的就是这样一篇工作，为了照顾审稿人和读者，算法背后有很多的深层次思考却不能开诚布公写在论文里。今天的专栏里，我在介绍工作的同时，也会如实写下这些思考。

前情提要

在上一篇专栏中，我们说过，对于任何检测任务，延迟和误报率大概有这样一个关系：

更长的决策过程往往能带来更高的准确度，但也会带来更大的延迟。我们通过统计学/信号处理中Quickest Change Detection理论 [1] (以下简称QD)，将这个问题建模成似然比检验，通过改变不同阈值，调整延迟和结果准确度之间的平衡。

更详细的背景介绍参见上一篇专栏。先前一篇工作，我们通过光流对移动物体检测进行了建模，但是由于当时光流算法带来的巨大运算负担，这一套算法难以在实际的视觉应用中落地。在我们ICCV2019的工作《Minimum Delay Object Detection from Video》[2]中，我们抛弃掉光流，使用目前已经发展相对成熟的单帧检测器（Fast-RCNN、YOLO等），直接对检测框和物体类别进行概率建模，将已有的单帧检测器无缝对接到视频物体的低延迟检测中。

低延迟检测的思路

在视频物体检测中，如果使用上一帧的检测结果作为先验，将下一帧的检测结果输入贝叶斯框架，输出后验，那么总体来说，这个后验结果融合了两帧的信息，会比单帧更准。在这个思路下，理论上来说使用的帧数越多，检测越准。如以下单帧和多帧的对比：

但是同时更多的帧数会造成更长的延迟（延迟 := 物体被检测到的时刻 - 物体出现的时刻）。如何在保证物体检测精度的情况下，尽量降低延迟呢？我们参照QD理论进行如下建模：

假设一个物体在时刻 出现在视频中，在 离开视频，则这个物体的移动轨迹可以用时序上的一组检测框 表示。这样的一组检测框检测框序列，在目标追踪（Data association / tracking）领域被一些人称作tracklet。简单说，我们的算法目标是以低延迟判断检测框序列内是否含有物体。因此，我们称这样一组检测框序列为一个candidate。在quickest change detection框架下， 可以用如下似然比检验判断 时刻物体是否出现在该candidate内：

其中 代表一个单帧检测器在 上的检测结果， 代表candidate中的内容从背景变为第 类物体（如行人）这一事件发生的时刻， 代表给定类别 的时候，事件 发生的概率。由条件概率的独立性， 与类别 和检测框 独立，继而时序上各时刻检测结果的联合概率变成各时刻概率的连乘：

这里需要明确一下，上边公式中的条件概率并非简单的检测器输出的结果，具体如何计算 需要一套比较复杂的建模。由于这里只介绍低延迟检测的整体思路，关于 的建模待我有空时会附在文末，有兴趣的朋友可以直接去论文查阅。总之，我们可以对这个似然比取阈值，进行检测。阈值越高，结果越准，但是延迟越大，反之同理。由QD理论中递归算法（CuSum算法），我们可以对上述似然比取log，记为W。最终的检测流程可以参照如下框图。

整体流程为：

（1）将已有但似然比未超过阈值的candidate做tracking进入下一帧；

（2）在下一帧进行单帧检测，生成新的检测框，与前一帧tracking后的检测框合并到一起；

（3）对这些candidate进行似然比检验，W超出阈值则输出检测结果，W小于零则去除该检测框，W大于零小于阈值则回到（1），进入下一帧。这样一个检测框架，可以与任何单帧检测器结合。

结果

这篇工作和先前的工作一样，由于是新问题，并没有现成的数据集，于是我们只能对KITTI进行魔改，将KITTI中对物体的第一帧标注作为这个物体出现的时间，计算平均检测延迟。可以看到，无论与哪种检测器相结合，相比单帧检测，这种多帧框架下的检测方法在相同精度下都可以有效降低检测延迟。

更加有趣的是，这些曲线都是由COCO上预训练好的检测器直接得出，根本没有在KITTI上做过任何finetune。即便如此，只要能够接受足够多帧的延迟，这些方法依然可以达到很低的误报率。这其实是一个非常有意思的结果，说明用延迟换精度是一个完全可行的思路。

文章中还有一些其他图表，证明了这样一个多帧的方法不光可以有效降低检测延迟，还可以增加同误报率下被准确检出的物体数量，就不一一罗列了。另外，目前使用神经网络进行检测都是在GPU进行，而该多帧框架则可以在CPU并行执行，执行速度约50fps。两者并行的话，已经有潜力实时应用在真正的系统中了。下边放一个同误报率下，单帧方法和本文方法的对比，注意视频上下两组结果使用的是完全相同的神经网络。

视频链接：https://www.zhihu.com/zvideo/1284627306846834688

后续和一些感想

写这篇论文的时候，我查阅了不少关于“视频物体检测”的文献，加上通过和一些业界大佬交流，发现已有的“视频物体检测”算法，例如基于光流的Feature Aggregation、3D 卷积等技术，目前基本上没法真正落地（如果说的不对请指正）。究其原因，一是不少方法纯炼丹，对数据的依赖强，缺少一个solid的理论框架（这也是深度学习通病）；二是这些方法根本没有考虑真正在工业应用上的部署，比如视频物体检测往往要固定temporal window size，极大限制了算法的落地空间。在我做这一篇工作的同期，斯坦福大学Bill Dally教授组的Huizi Mao同样出品了一篇关于检测延迟和检测精度关系的论文《A Delay Metric for Video Object Detection: What Average Precision Fails to Tell》[3]。在这篇论文中得出结论，同等精度下，目前使用多帧的视频物体检测方法在延迟方面输给单帧检测器。

Mao et al., ICCV 2019.

出于好奇，我在本文框架下，也对已有的视频物体检测算法做了些测试，同样发现同等误报率下，已有方法同样不如单帧（结果未随论文发表）。两篇论文虽然metric不同，但是结论几乎一样。这也就意味着，在真的产品部署中，需要大量运算的视频检测器不但没有提高检测效率，反而帮了倒忙。

另一方面，工业界对于比单帧更稳定的检测器却有着货真价实的需求。比如据说某厂在开发工业探伤算法过程中，发现单帧Fast-RCNN的输出非常noisy。如今在一些产品（例如机器人、自动驾驶、垃圾分拣）中，由于软硬件限制，要想进一步提高单帧的检测精度非常之难。与此同时，相机多抓取一帧，多跑一遍检测算法却并不难。在这样一套可以自由融合多帧的框架下，改变思路，用一定的检测延迟换取更高的精度也许是个有趣的方向。

说实话，对于端到端炼丹在各视频应用上（不只是检测）难以真正有效这件事，大家也只能心照不宣。真正落地往往其实还是逐帧分析再做后处理。我个人看来，对视频这类有着明确时序联系的任务，或者一些具有已知物理模型的任务（如光学成像），完全可以大框架下使用已有的理论完备的模型（如本文介绍的QD），把深度学习留给难以用数学/统计学准确建模的子模块（如单帧检测）。在这个思路下，我估计AI领域会渐渐诞生出两个新的流派：【1】放弃对端到端的执念，将传统模型与深度学习结合，将深度学习作为求解器；【2】将统计模型/物理模型直接融入网络设计，端到端训练出一个带有传统模型性质的新方法。这篇工作坚决贯彻了【1】的思路，而机缘巧合，我之后一篇工作，使用了【2】的思路，有兴趣的朋友可以持续关注本专栏。

参考资料

[1] V. V. Veeravalli and T. Banerjee. Quickest change detection. Academic press library in signal processing: Array and statistical signal processing, 3:209–256, 2013.

[2] Dong Lao and Ganesh Sundaramoorthi. Minimum Delay Object Detection From Video. Proceedings of the IEEE International Conference on Computer Vision, pp. 5097-5106. 2019.

[3] Mao, Huizi, Xiaodong Yang, and William J. Dally. A delay metric for video object detection: What average precision fails to tell. Proceedings of the IEEE International Conference on Computer Vision, pp. 573-582. 2019.