一种基于动态图着的在线视频浓缩方案

一种基于动态图着的在线视频浓缩方案

技术领域

本方法提供一种基于动态图着的在线视频浓缩方案，属于视频信号处理、图像处理、安全监控领域。

背景技术

由于当前社会中，监控摄像头被广泛用于世界上的各个角落，尤其是安装之后角度固定不变的静态摄像头，其使用数量在十年间成指数爆炸型增长。IDC的2025数据纪元研究报告指出，2016年的人工数据生成总量，即全球数据网的数据储备总量是16.1ZB，而这个量每年都在激增，预计在2025年将上升到163ZB。在这些天文数字中，诸如监控视频等非娱乐作用的视频和图像数据占据了一个很大的比例。另有文献指出，当前世界上存储的最大量的数据，就是监控视频。大量的数据带来的最明显的问题，就是其存储、分析、浏览和检索都成为了巨大的挑战。为了解决这些问题，分布式存储和分布式计算被广泛应用于工业界和学术界。然而，在处理监控视频方面，绝大部分的分布式技术将监控视频作为原子对象进行操作，也就是将一个视频作为一个整体，而忽略了视频内部的相关性以及信息冗余。由此，一系列视频处理技术针对于视频内部的信息挖掘而被开发出来，旨在去除视频信息冗余，提炼有效信息，减少存储空间的消耗和信息精确检索的时间消耗。

一般来说，监控视频绝大多数是静态视频，也即拍摄此视频的摄像头在启动录像之前和录像过程中，摄像头都处于固定状态，不进行角度调整、变焦、平移等能够使背景区域产生剧烈变化的操作；与其相对的动态视频则没有这些限制。监控视频信息提炼的技术基本是处理静态视频的，其大致可以分为视频摘要(Video Abstraction)、视频蒙太奇(Video Montage)、视频压缩(Video Condensation)和视频浓缩(Video Synopsis)四类。

视频摘要的最小处理单位是一个视频帧。此类方法挑选出视频中的若干帧，并认为这些帧能够代表整一个视频所包含的关键信息，以此达到压缩视频的目的。根据保留的帧是否连续，视频摘要又被进一步分为视频概要(Video Summary)和视频浏览(VideoSkimming)。前者把每一帧都看作是独立的，将这些帧提取出来，能够得到一个静态画面组成的故事板。类似于电影图解，使用者能够通过查看这个故事板得知整个监控视屏中发生了哪些重要事件。这种方案有一个明显的缺点，其将所有的动作信息忽略了，导致了大量的动态信息损失。在绝大多数情况下，监控查看者需要根据一个人的连续动作，才能判断出其是否有异常行为。视频浏览就是为了缓解这一缺点而被提出的。它仍旧提取关键帧，但是是连续提取的。即视频浏览提取若干视频段，用总长度远远小于原视频的视频段集合来表示整个视频。但此类方法仍然有动态信息丢失的缺点：小目标，或者快速运动的目标常常被忽略。因此，视频蒙太奇和视频压缩进一步被提出。视频蒙太奇将一个视频平行于时间轴进行切分，即将一段视频中的每一帧按照某一种子区域划分，分成若干碎片帧，然后将同一子区域不同时间的碎片帧按照时间顺序组合起来，得到若干碎片视频段，最后从这些碎片视频段中选出包含关键信息的段进行重组，得到输出视频。相比于视频摘要，这种方法虽然能够保留更多的动作信息，但是其算法十分复杂，处理时间极长，并且会留下明显的拼接裂缝，不利于人工查阅。视频压缩对其进行改善，利用动态规划算法，将无用的背景像素点信息删去，直接得到最后的压缩后视频。虽然这种方法十分快速，并且在运动目标提取正确的情况下能够保留所有的动态信息，然而灵活性十分局限，且冗余信息删除的效率低下，另外，其仍具有明显的影响二次查阅的拼接裂缝。

近几年，一种称为“视频浓缩”的技术正广泛受到关注。其能够折中视频蒙太奇和视频压缩，同时保留两者各自的优点，诸如计算快速、方法简单、能够保留所有的动态信息，并且良好地克服了两者的缺点，生成的视频拥有较高的压缩率而几乎没有接缝感，拥有良好的视觉效果。视频浓缩的结果能够帮助使用者花费更少的时间、更精确地出目标信息。视频浓缩的直接目的是，将视频中所有运动的目标单独提取出来(这个阶段称为“管道提取”)，而后在保证一些约束的情况下，将这些目标的出现时间重新安排，而不改变其出现的空间位置(这个阶段称为“管道重排”)。例如，目标1原来出现在视频的第10帧，经过视频浓缩以后，其可能从第一帧就开始出现了。一方面，视频浓缩通过运动目标检测和提取将原始视频中的所有动态信息进行保留；另一方面，将活动物体聚集在一段远远短于原始视频的时间段内，形成一个新的，信息密度更大的浓缩视频，达到压缩原始视频的目的。特别地，单独提取出来的每一个物体，都称为一个“管道”；一个管道包含的某一时刻的物体空间位置以及动作状态，称为一个“管道帧”。

视频浓缩的难点在于，管道重排问题是一个NP难的问题，其计算复杂度随着管道数量呈指数趋势上升。于是，现有的视频浓缩方法都致力于在合适的时间内，到一个局部最优的管道安排方法，使得原始视频能够尽可能压缩，同时丢失的动态信息达到最少。传统的视频浓缩分流为两条技术路线：离线视频浓缩和在线视频浓缩。离线视频浓缩将管道重排过程看作是一个Gibbs能量函数优化的问题。此能量函数衡量所有管道安排方式的好坏，能量函数值越低，管道的安排方案越优秀。其中衡量的标准包括管道的信息保留程度、管道之间的交互信息保留程度、管道之间的遮挡程度等等。如前所述，直接解此能量函数是NP难的，于是传统的离线方法首先利用预处理保留可以预先计算的信息，然后使用模拟退火算法来到一个局部最优解。然而这种方法十分消耗内存，在预处理和模拟退火迭代的部分也十分费时，并且需要等到所有管道提取完毕之后才能进行模拟退火优化。虽然这种方法通常能够到一个令人满意的解，但有时候也会陷入一个较差的局部最优，导致整体算法不稳定。在线的视频浓缩方法消耗内存少，计算速度能够达到实时要求，可以在得到一个管道的同时就立刻开始对其进行处理，但通常在压缩率相同的情况下，得到的重排结果要远远差于离线方法。

显然，这两类方法还有很大的提升空间。一个合理的思路是权衡结合离线方法和在线方法的优点，在保留相同压缩能力的情况下，能够保留更多的动态信息。其中的技术难点在于：一是：如何在尽可能少的内存使用情况下，明确地表现出管道之间的交互关系；二是：如何在保证实时性的情况下，到一个更优的局部解。更优的含义是，压缩率保持不变或者更高的情况下，保留更多的动态信息；三是：如何建立一个通用模型，使得这个模型能够解决难点一，并且基于这个模型开发的算法能够在离线性能和在线性能之间自由权衡，而保证模型不变；四是：基于三中提出的模型，如何设计一种管道重排算法，使得其能够尽可能解决难点二，使其性能远超于当前的管道重排算法。

发明内容

本发明的目的就是提供一套解决上述四个技术难点的视频浓缩方案。此方案不包括视频浓缩过程中的管道提取部分的优化，仅针对管道重排操作。本发明通过将管道之间的空间关系建模为混合图模型，再以一种动态图着方法对此模型的每个顶点进行着，最终以着结果来安排管道在浓缩视频后的位置。本项目主要实现的目标是，在满足较少的运行时内存消耗以及实时处理的需求下，达到比现存方法更高的压缩率，以及保留更多的动态信息。

本发明是通过如下技术方案实现的。一种基于动态图着理论的在线视频浓缩方案包括以下内容：

1.基于管道帧之间的空间关系，对已获取的管道建立一个混合图模型。不同于传统方法以整个管道作为最小单位进行处理，本发明提出的模型将一个管道帧作为最小单位。这种方式能够使管道重排过程中，两个管道之间的安排方式达到最紧凑的状态。另外，为了保证稳定的运行时内存使用，以及实时的计算性能。此混合图模型是动态更改的，其顶点能够动态增加和删除。

2.利用内容1中得到的混合图模型，本发明进一步将管道重排问题建模为一个动态图着的组合优化问题。此组合优化问题所定义的是：对于一个动态改变的图，其每一次的结构改变都会伴随着着算法对其进行重新着。最终期望到一个近似解，使得图中所用到的最大颜和最小颜的差值最小，并且满足优化问题给出的约束(例如相邻结点不能同)。本发明结合管道之间关系的特点，设计了一种适配于管道重排问题的动态图着优化问题，理论上能够比传统方法更快地收敛于最优解。

3.利用内容1中定义的模型，以及内容2中定义的组合优化问题，本发明最终提出一种适配于管道重排问题的在线动态图着算法。此算法适用于流视频数据，保证实时处理和低内存消耗，并且能够稳定地到一个近似解，使得此解对应的重排方案满足高压缩率和低信息丢失率，最终使得视频浓缩结果优于现存的视频浓缩方案产生的结果。

和传统的视频浓缩算法相比，本发明的重要区别在于：一方面，用新的模型和优化问题定义了视频浓缩中管道重排的解决方案，并且提出了解这个模型的对应方案，使得其效果优于现存方案；另一方面，本发明提出的模型统一了离线视频浓缩和在线视频浓缩的模型形式。在传统方法中，在线模型和离线模型相差很大，适配于一种算法的模型，很难与另一种算法适配。然而，本发明提出的模型，可以用离线方法求解，也可以用在线方法求解，而保持模型本身不变。这意味着，在实际的工业使用中，可以对管道用同样的方式建模，但可以根据平台计算能力、信息保留需求程度选择任意的方式对模型进行求解。因此，本发明提供的解决方案具有高度可扩展、高度松耦合的特性，更加满足于实际生产需求。下面，对本发明的具体内容进行详细说明。

内容1：实时获取视频流，从中提取活动物体对应的管道，对获取完毕的管道进行混合图建模。

当获取到视频流的某一帧时，默认的管道提取算法检测这一帧中出现的所有活动物体，将矩形活动区域提取出来，然后对于提取出的每一个活动区域，将其与当前未提取完全的管道进行匹配。如果匹配成功，这一活动区域就做为匹配管道在当前时刻的管道帧，添加到这个管道的管道帧列表中；如果匹配失败，这一活动区域就被认为是新管道的第一个管道帧。系统在所有活动区域匹配完毕之后，凭借管道未被更新时长检测是否有管道完成。对于完成的管道，将其加入到混合图中，完成对其建模。

所谓混合图，就是同时存在有向边和无向边的图结构。对于将要加入混合图的管道，本发明将每一管道帧抽象为一个混合图结点。对于同属一个管道的结点，用有向边相互连接，连接的方式为前一个管道帧指向后一个相邻的管道帧。对于不属于同一管道的两个结点，如果它们对应的两个活动区域在空间上有重叠，就用无向边连接这两个结点。混合图结构的示意图如附图1所示。

内容2：利用内容1中得到的混合图模型，将管道重排问题建模为一个动态图着的组合优化问题。

之所以要用动态图描述管道之间的关系，而不是将所有的管道建模成一个图一次性进行处理，原因有两点：一是为了保证能够及时处理流视频，需要获取一个管道之后立刻进行处理。对应内容1中的混合图模型，其直观表现就是每当有新管道生成时，将其所有的管道帧抽象为结点按照内容1的方式插入到当前的图中；二是由于需要保证稳定的运行时内存消耗，以及保证在视频流的下一帧到来之前，能够完成新图的更新，混合图是有结点数量限制的。每当混合图中的结点所属管道的数量超过一个限制，就会选择出一个当前混合图中最早结束的管道对应的所有结点，然后将它们从图中删除，它们将根据自身的颜，永远固定在浓缩视频的对应位置，不再参与建模和更新。在删除完毕之后，为了不让后续的管道影响前面已经被删除的管道，后续管道能够着的最小颜也需要被限制。在本发明中，每当有管道被删除，就比较最小可着颜与管道第一个管道帧的颜，最小可着颜被更新为两者中的较大者。

因此，在每一次删除和插入完毕之后，原图就会被更新为一个新图。在一个视频流的处理过程中，会有许多混合图产生。动态图指的就是这样的一组图。对于每一个图，我们都能够用同样的优化式定义这个图的优化目标。这就是内容2所要阐述的核心内容。本发明中定义了一种通用的混合图着优化目标，描述如下：在无向边连接的两个顶点不能着同一颜，有向边连接的头顶点和尾顶点的颜之差必须为1的限制下，使得整个混合图中最大颜和最小颜之差最小化。显然，如果一对无向边连接的顶点着不同颜，那么在浓缩视频中，此两顶点对应的两个在空间中有重叠的活动区域，其出现时间会被交错开，两者就避免了相互重叠引起的信息损失。所以，本发明定义的优化目标能够保证完整的动态信息保留情况下，获得一个尽可能高的压缩率。

内容3：实现动态图着的在线近似求解。

内容2中定义的动态图着问题和传统的图着问题一样，仍然是一个NP难的问题。为了保证实时处理的性能，本发明提出一种新的在线求解过程来求解这个问题。在这个在线求解过程中，为了进一步提高压缩率，我们允许部分的信息损失出现，即允许一部分的无向边两端的结点着同一种颜。此时，原来的着目标被松弛为如下的着目标：在有向边连接的头顶点和尾顶点的颜之差必须为1的限制下，使得整个混合图中最大颜和最小颜之差，以及两端顶点颜相同的无向边数量之和最小化。并且在每次着新图的时候，会利用新图和前一个图的共同信息来指导新图的着。接下来描述这个在线着目标的具体求解方法。

我们以管道为单位进行一次着，称为“对一个管道的着”。对于每一个需要被着的管道，遍历其所有的管道帧对应的顶点。对于每一个顶点，在不小于最小可着颜的范围内，到一个最小颜，使得其无向边连接的，具有同一颜的邻居数量不超过一个阈值T。最终，选取一个顶点，其着能够使此管道的起始颜最小，并以这个顶点的颜为基准，调整同属一个管道的其他顶点的颜，使它们满足有向边的约束。说明书附图3描述了这个算法的执行流程。

每当新完成一个管道，这个管道将以内容1给出的方式进行抽象，并加入到当前的混合图中，之后如果混合图的结点数量超过内容2中描述的顶点数量限制，就按照内容2的删除方式进行顶点删除，并更新最小可着颜。经过顶点插入和删除之后，得到一个新图。此新图中，除了新加入的顶点没有被着之外，其余的顶点均被着。接下来，考虑两种新图的更新方案。第一种方案是直接按照“对一个管道的着”方案，对新管道进行着。第二种方案是将新来的管道的第一个管道帧对应的顶点染为最小可着颜。然后将所有和新管道的管道帧有无向边连接关系的管道所属顶点全部置为未着状态，再依次对这些管道所对应的结点运用“对一个管道的着”方案进行重新着，着的顺序为先添加的管道先着。最后对比两种方案，选择使得整个混合图中最大颜和最小颜之差更小的方案作为最终更新方案。

附图说明

图1混合图结构示意图；

图2整体流程图；

图3“对一个管道的着”算法流程图。