Get best of the week

什么时候停止视频序列识别过程？

哈勃！今天，我们想告诉您一个自从我们开始研究视频流中的文件识别以来我们一直在处理的一项非常有趣的任务-找到最佳停止时间的问题。



图。 1.在视频序列帧上的ID文档的文本字段图像。

众所周知，Smart Engines的主要产品是识别身份证件的系统，即Smart IDReader，可同时应用于服务器和台式机以及移动设备上。在很多情况下，手机上的文件识别必须离线进行，通常我们无法控制拍摄的条件和质量，识别错误的成本非常高，尤其是在识别身份证件时。同时，我们还有一个重要的优势-我们不能使用一个图像，而是使用一系列捕获的帧（见图1）来提高识别精度。

当使用文本字段的多个图像时，出现两个重要的问题。第一个问题是如何结合观察结果？是否值得将源帧组合在一起以获得一个图像，更高的“质量”，或选择一个更好的帧（然后在哪里保证会有一个好的帧）？或者，也许，首先识别每个帧上的字段，然后选择最“可信”的结果（根据什么标准？），或者组合逐帧识别结果，等等。我们坚持使用后一种方法（逐帧识别和帧间结果组合），但是最佳方法可能会有所不同，这取决于所使用的识别引擎和其他任务参数。

与第一个问题无关的第二个问题是何时停止观察过程？换句话说，根据什么标准，您决定可以停止捕获过程并将当前时刻累积的结果识别为最终结果？如何将这些标准相互比较，是否存在最佳标准？

这是关于寻找停止观察过程的时刻的问题，本文将对此进行讨论。

我们想要实现的目标


识别视频序列中的文本字符串，其中捕获了另一观察结果后，结果会以一种或另一种方式改善，可以看作是Anytime算法 -一种具有顺序改进结果的算法，可以随时停止计算。可视化此类算法的质量的便捷工具是“ 预期性能概况 ”-表示结果质量的依赖性的图形，以一种或另一种形式衡量，取决于计算时间。


图。 2.视频序列中文本行识别效率的概况（越低越好）。黑色虚线表示逐帧质量，黑色实线表示帧间合并的结果。橙色线是我们从“良好”停止规则中获得的结果。

在图。图2显示了用于识别文本字符串的效率曲线-平均错误（根据Levenshtein到正确答案的距离）对已处理帧数的依赖性。使用Tesseract v4.0.0在MIDV-500数据集的文本字段上获得黑色图形。可以看出，使用识别结果的帧间组合可以实现一个低得多的误差值（通常这并不奇怪）。

从“好的”停止规则中我们想要什么？由于我们非常合理地期望继续执行此过程的时间越长，平均结果越好，因此，如果在某些视频序列上停止的规则被认为“更长”，如果有机会将错误最小化，并且在某些视频上将停止，则将是很好的选择如果结果已经不错，或者没有机会改善它，那就早些。因此，在合并结果的平均质量相同的情况下，平均而言，可以处理的帧数更少，反之，在平均帧数相同的情况下，平均结果更好。换句话说，重要的是要理解停止规则不仅是关于最小化时间，还是关于在相同（平均）时间上最大化质量。

让我们以以下形式查找停止规则：在处理下一帧并接收到组合的识别结果之后，我们考虑一些特征并切断其阈值-如果，例如，它低于阈值，则我们停止，否则继续。然后，使用固定的停止规则，但改变阈值，我们还将获得效率曲线，但水平轴将不包含已处理帧的确切数量，而是平均值（请参见图2中的橙色图）。该图表越低，我们可以考虑止损规则越有效。我们可以将“合并结果”的初始配置文件视为微不足道的停止规则有效性的配置文件-在该配置文件中，我们仅将阈值处理的帧数减少了。

理论怎么说


在数学统计中，找到最佳停止时间的问题是众所周知的，并且已经进行了长期研究。此类中最著名的任务可能是挑剔新娘的任务（例如，鲍里斯·阿布拉莫维奇·别列佐夫斯基（Boris Abramovich Berezovsky）参与其中），卖房的任务等。在不深入理论的情况下，让我们简要介绍一下视频序列中的识别问题作为最佳停止问题。

我们ñ在过程的第i步将合并结果的误差表示为\ epsilon（R_n）。我们假设，如果我们停止在ñ第i个步骤中，我们将承担以下形式：，损失L_n = \ epsilon（R_n）+ c \ cdot n在那里C-每个观察值的一些预定相对成本。寻找最佳停止时间的任务可以公式化为对随机变量的搜索ñ-停止时间，其分布取决于输入的观测值（在某些文献中，该值ñ称为马尔可夫矩），并且在该时间点，预期损失最小化\ mathrm {E}（L_N）。

单调的问题


在某些情况下，在此类问题中，可以明确表达最佳停止规则。一个例子是所谓的单调问题。问题单调性的标准是：如果某个步骤的ñ损失L_n未超过下一步的预期损失，则将在所有后续步骤中执行。换句话说，从L_n \ le \ mathrm {E}（L_ {n + 1} | \文本{接收}〜n〜\文本{frames}）事件发生之后，事件将发生L_ {n + 1} \ le \ mathrm {E}（L_ {n + 2} | \文本{接收}〜n + 1〜\文本{frames}）。对于单调问题，所谓的“近视”停止规则是最佳的：在满足条件的第一步就停止L_n \ le \ mathrm {E}（L_ {n + 1} | \文本{接收}〜n〜\文本{frames}）。

假设我们的任务是单调的。根据功能编写了近视规则后，L_n我们得到满足以下条件时需要停止的信息：

\ epsilon（R_n）-\ mathrm {E}（\ epsilon（R_ {n + 1}）| \ text {received}〜n〜\ text {frames}）\ le c。

当然，这很好，但是要实现此规则，我们不仅需要能够在运行时评估当前结果的“正确性”，而且还可以评估下一个结果的预期正确性，这并不是那么简单（更不用说我们对任务的迫切要求了）单调）。我们可以以某种方式应用此规则而不直接评估结果的“正确性”吗？..您可以尝试从上方评估不等式的左侧。

近视规则如何使用？


假设函数\ epsilon（R_n）是\ rho（R_n，R ^ *）从组合识别结果R_n到“正确答案”的R ^ *距离，并且像任何尊重自己的距离一样，三角形不等式成立。上面提到的Levenshtein距离满足三角不等式，并且满足“对/错”形式的简单函数（如果我们假设\ rho（R_n，R ^ *）正确答案为零，错误答案为常数）。根据三角形不等式，我们的停止准则的左侧不超过\ mathrm {E}（\ rho（R_n，R_ {n + 1}）| \ text {received}〜n〜\ text {frames}）-从当前合并结果到下一个合并结果的预期距离。

让我们还对帧间组合识别结果的算法提出要求，以使相邻组合结果之间的平均距离不会随时间增加（也就是说，我们将组合结果的顺序视为某种“收敛”过程，尽管不一定要获得正确答案）。然后，如果从当前结果到下一个结果的预期距离小于阈值c，则立即完成两件事。首先，满足近视停止标准（因为它的左侧部分从上方被该相同距离限制）。其次，任务变得单调：在下一步中，到下一个答案的预期距离不会增加，这意味着它将继续小于阈值c，并且将再次满足近视标准。

这意味着如果我们预期相邻合并结果之间的距离不会平均增加，那么我们需要从当前结果到下一个结果的预期距离的阈值截止处停止，从而逼近最佳规则。您需要了解，这样的规则不再是最佳规则（因为“实际”最佳规则可能会更早停止），但是至少我们不会比必要时更早停止。

有几种方法可以评估从当前组合结果到下一个组合结果的预期距离。例如，如果将Levenshtein距离用作结果的度量，则即使仅布局的最后两个结果之间的距离也是一个很好的近似值。另一种可能的方法是模拟可能的下一个观察结果（例如，基于已经获得的观察结果），进行“空闲”组合，并计算与所获得的预测的平均距离。


图。 3.比较几个停止规则的性能配置文件。

在图。图3显示了几个停止规则的性能概况。N_K-相同的“上述”“琐碎”规则-阈值截止了已处理观测值的数量。N_ {CX}和N_ {CR}-相同的逐帧（N_ {CX}）和组合（N_ {CR}）结果的最大群集大小的阈值截止。ñ-本文中描述的规则，使用建模和“空闲”组合估算到下一个结果的预期距离。

而不是结论


本文的目的是表明，在视频序列帧上的文档识别系统中，存在许多有趣的问题，不仅直接来自计算机视觉，还来自其他有趣的领域。尽管我们展示了仅以最简单的形式找到最佳停止时间的问题，但最有趣的部分始于（例如）我们不仅要考虑模型中的帧数，还要考虑实际执行时间。我们希望您对此感兴趣，并感谢您的关注！

-根据

有关视频流中文本识别的最佳停止策略的文章（K.Bulatov，N.Razumnyi，VV Arlazarov，IJDAR 22，303-314（2019）10.1007 / s10032-019-00333-0）编写出版物。

如果读者对最佳停止时间的理论感兴趣，特别是对单调问题近视规则的最优性的证明，我们强烈建议出版已出版的“ 最佳停止和应用”课程（Thomas Ferguson，UCLA）。

有关此主题的其他一些有趣的资料来源：
Chow YS，Siegmund D. 很高的期望：最优停止理论，Houghton Mifflin，1971，139页。
别列佐夫斯基（Berezovsky B.A.），格尼丁（Gnedin A.V.）最佳选择问题，《科学》，1984年，200页。
Ferguson TS，Hardwick TS 停止校对规则，应用概率杂志，第26卷，第2期，1989年，第1页。 303-313。
弗格森TS数理统计：一种决策理论方法。学术出版社，1967年，396页。

More articles:


All Articles