用于检测和跟踪视频中的一个或多个感兴趣对象的方法和设备

摘要

本发明涉及一种用于在视频序列中自动检测和跟踪一个或多个感兴趣对象的方法，该视频序列包括使用移动相机捕获的若干个连续帧(1)，该方法包括以下步骤：-依据颜色将该帧(1)分割(32)成区域并产生分割的图像(1′)；-从该分割的图像(1′)中推演出(34)包括节点和边的区域邻近图形(11)，其中每个节点定义区域且每个边连接邻近区域的两个节点；其中从所述若干个连续帧(1)的被分割的图像(1′)推演出的区域邻近图形(11)形成区域邻近图形集合；-从所述区域邻近图形集合提取(36)频繁时空图案(13)；-确定(38)连续帧(1)之间的被提取的频繁时空图案(13)的轨迹之间的不相似度；以及-根据被确定的该轨迹的不相似度聚集(39)该频繁时空图案(13)以产生对应于所述一个或多个感兴趣对象中的一个感兴趣对象的至少一个群集(25，26，27)。

说明书

技术领域

本发明涉及应用于视频的图像处理领域。更特别地，本发明关于在使 用移动相机获取的视频序列中检测和跟踪一个或多个感兴趣对象。

下面的术语“移动相机”用于指在稳定景象中移动的相机以及获取变 化景象的相机，即，其中背景或环境从一个景象或帧移动到另一个景象或 帧。

背景技术

视频序列中感兴趣对象的检测和跟踪，像电影中的主要人物或直播足 球赛中最重要的动作，考虑了了解视频中这些对象的位置和轨迹。这种了 解对视频的自动概要是基本的。视频概要有一些目的，例如在视频监控应 用中、视频索引中、或需要视频内容的管理的其他交互多媒体应用中。

当处理使用不移动相机获取的视频时，能够使用背景减去技术来检测 感兴趣对象。这样的技术的示例公开在S.Conseil等人的“Suivi TridimensionnelenStéréovision”，GRETSI，2005中，其中背景被作为从 所有帧中减去的参考图像以检测人手。

但是，背景减去方法不适用于使用移动相机获取的视频序列的情况， 因为背景易于在景象或帧之间变化且不可以用作参考。存在一些用于跟踪 使用移动相机获取的视频中的对象的可替换方法和设备。下面描述其中的 一些示例。

根据第一技术，用户标记感兴趣对象，即用户经由图形用户界面(GUI) 手动选择帧中的目标感兴趣对象。然后使用运动和外观模型来跟踪穿过视 频序列的被选择的对象以知道其轨迹。

第二种方式能够自动跟踪使用移动相机获取的视频序列中的对象，公 开在US5867584中，其需要用户指定包括该对象的窗口。该窗口然后与 后续帧中的测试窗口进行比较以找到与包含该对象的指定窗口最相似的最 匹配窗口。

在第三种方式中，需要跟踪对象的在先知识，例如以包含与对象相关 联的特征的数据库的形式。系统提前知道感兴趣对象的模型，由此使其能 够在视频的帧内检测相似的对象。系统的数据库包括多个训练样本，例如 不同种类的人脸，以找到视频中的脸。之后执行数据关联步骤以将对跨视 频帧的相同对象的检测关联到轨迹或轨道。该第三方式的示例可以在T. Ma,L.J.Latecki,“MaximumWrightCliqueswithmutexConstraintsfor ObjectSegmentation”,IEEEConferenceonComputerVisionandPattern Recognition(CVPR),June2012中找到。

使用上述技术，需要用户交互和/或感兴趣对象的在先知识，或可以被 检测的对象类型被限制了，例如被限制到系统已经被训练的对象类型。

根据以上描述，需要不用输入在先知识并独立于知道模型所需的数据 库的情况下的改进的自动检测和跟踪使用移动相机获取的视频中的感兴趣 对象。

发明内容

本发明的实施方式提供用于检测使用移动相机获取的视频中的感兴趣 对象的赶紧的方法和改进的设备，其解决上述问题。

根据第一方面，提供用于自动检测和跟踪包括使用移动相机获取的若 干个连续帧的视频序列中的一个或多个感兴趣对象的方法，该方法包括步 骤：

针对该视频序列中的每个帧：

依据颜色将该帧分割成多个区域并产生分割的图像，

从该分割的图像推演出区域邻近图形，包括节点和边界，其中每个 节点定义区域且每个边界连接该分割的图形的邻近区域的两个节点，

其中针对所述若干个连续帧的从分割的图形推演出的区域邻近图形形 成区域邻近图形集合，

从该区域邻近图形的集合提取频繁时空图案，

确定连续帧之间的该提取的频繁时空图案的轨迹之间的不相似度，以 及

根据所确定的该轨迹的不相似度聚集(cluster)该频繁时空图案以产 生对应于所述一个或多个感兴趣对象中的一个感兴趣对象的至少一个群 集。

在一些实施方式中，该提取步骤可以包括提取在该区域邻近图形集合 中的预定数量的区域邻近图形中出现至少一次的时空图案。

在一些实施方式中，该提取步骤可以包括：

针对每个时空图案确定两个不同区域邻近图形中间隔两次连续出现的 时空图案的欧几里得距离，以及

提取确定的欧几里得距离低于空间阈值的时空图案。

在一些实施方式中，该提取步骤可以包括：

针对每个时空图案，确定两个不同区域邻近图形中间隔时空图案的两 次连续出现的区域邻近图形的数量，以及

提取确定的区域邻近图形的数量低于时间阈值的时空图案。

在一些实施方式中，确定轨迹的不相似度的步骤可以包括：

确定区域邻近图形中每个时空图案的图心(centroid)，

确定对应于每个区域邻近图形中两个不同时空图案的两个不同图形之 间的欧几里得距离，以及

计算若干个区域邻近图形上的两个不同图形之间的欧几里得距离的平 均。

优选地，确定轨迹的不相似度的步骤还可以包括：

针对在两个不同区域邻近图形中间隔时空图案中的每一个时空图案的 两次连续出现的一个或多个区域邻近图形插入图心，以及

计算所有区域邻近图形的两个图心之间的欧几里得距离的平均值。

在一些实施方式中，聚集步骤可以包括聚集计算的两个不同图形之间 的欧几里得距离的平均低于不相似阈值的时空图案。

有利地，聚集步骤还可以包括：

聚集频繁时空图案以产生对应于多个感兴趣对象的分等级的群集集 合，以及

在该分等级的群集集合中仅选择不相似度低于预定阈值的群集。

上述方面的任意还可以包括使用在视频序列中被检测和跟踪的一个或 多个感兴趣对象概括视频序列以得到视频概要。

优选地，该概括步骤包括基于其轨迹的空间重叠来确定交互感兴趣对 象。

根据第二方面，提供了用于自动检测和跟踪包括使用移动相机获取的 若干个连续帧的视频序列中的一个或多个感兴趣对象的设备，该设备包括：

帧提取器，被配置成依据颜色将视频序列的每一个帧分割成区域，并 产生每个帧的分割的图形，

图形引擎，被配置成从该分割的图像推演出包括节点和边界的区域邻 近图形，其中每个节点定义区域且每个边界连接该分割的图形的邻近区域 的两个节点，

其中针对所述若干个连续帧的从分割的图形推演出的区域邻近图形形 成区域邻近图形集合，

数据挖掘引擎，被配置成从区域邻近图形的集合中提取频繁时空图案， 以及

聚集引擎，被配置成：

确定连续帧之间的提取的频繁时空图案的轨迹之间的不相似度，以 及

根据所确定的该轨迹的不相似度聚集该频繁时空图案以产生对应于 所述一个或多个感兴趣对象中的一个感兴趣对象的至少一个群集。

有利地，该设备还可以包括概括引擎，被配置成使用在视频序列中被 检测和跟踪的一个或多个感兴趣对象概况视频序列以得到视频概要。

根据第三方面，提供了计算机可读介质，包括用于控制计算机系统执 行根据本申请的第一方面的用于在包括使用移动相机获取的若干个连续帧 的视频序列中自动检测和跟踪一个或多个感兴趣对象的方法的指令。

根据第四方面，提供了计算机程序产品，包括计算机可执行指令，用 于在程序在计算机上被运行时执行根据本申请的第一方面的用于在包括使 用移动相机获取的若干个连续帧的视频序列中自动检测和跟踪一个或多个 感兴趣对象的方法的指令。

根据这里公开的实施方式的方法和设备的另外方面和优点将在具体实 施方式、附图和任意权利要求中部分提出，并部分从具体实施方式中得出。 可以理解之前的概述和下面的详细描述仅是示意性而不限制要求保护的发 明。

附图说明

参考附图描述方法和设备的示意性实施方式，其中：

图1示意性示出了根据本公开的实施方式的方法的流程图；

图2A示出了分割视频帧的示例；

图2B示意性示出了根据图2A的分割视频帧构建的区域邻近图的示 例；

图2C示出了包含图案的区域邻近图集合的示例；

图2D示出了在图2C的区域邻近图集合中出现三次的图案；

图3A示意性示出了包含图2B的图案的多个视频帧；

图3B示出了对应于图3A中示出的图案出现的出现图；

图4A示出了根据本公开的实施方式的用于执行该方法的聚集步骤的 不相似测量；

图4B示意性示出了从根据本公开的实施方式的方法的聚集步骤得到 的提取的频繁时空图案的群集的集合的示例；以及

图5示意性示出了根据本公开的实施方式的用于自动检测和跟踪视频 中一个或多个感兴趣对象的设备。

具体实施方式

附图和以下描述示出了示意性实施方式。在不同附图中，具有相似结 构和/或功能的元件可以用相同附图标记来表示。

图1示出了示出用于自动检测和跟踪视频序列中一个或多个感兴趣对 象的方法的流程图。在第一个步骤30中接收的视频或视频序列包括在时间 上彼此连续的一些帧1或图像。使用移动相机获取帧1。在第二个步骤32 中，该视频序列的每个帧1或图像被分割成区域，由此产生多个分割帧1′ 或图像。每个帧1根据该帧的像素的颜色被分割。因此，分割的帧1′的每 个区域对应于一种颜色。为了执行该分割步骤32，可以使用颜色分割算法。 一种分割的视频帧1′的示例在图2A中示出。这里，分割的帧1包括四个 区域3、5、7、9，其中每个区域代表一种颜色。

参考图1，在第三个步骤34中，针对每个分割的帧1′建立图形11。 该图像11也称为区域邻近图像，因为其代表根据邻近区域对的分割的帧 1′。图2B示意性示出了从图2A的分割的视频帧1′推演出的区域邻近图形 11的示例。该区域邻近图形11包括节点12和边12′，其中每个节点12定 义区域3、5、7、9且每个边12′连接分割的图像1′的邻近区域3、5、7、9 的两个节点12。每个区域中的节点可以位于该区域的质心中。每个节点12 被赋予代表该节点位于的区域的颜色的标签。从一些或所有连续帧1的分 段图像1′推演出的区域邻近图形11形成区域邻近图形集合。

图2C示出了三个区域邻近图形11、11′、11″的集合的示例。这三个 图形11、11′、11″的每一个对应于视频序列的一个分割的帧。视频的分割 的帧或图像以区域邻近图形形式的表示允许图像的拓扑的建模。

仍然参考图1，在第四个步骤36中，从区域邻近图形集合中提取频繁 图案13。该提取步骤36也可以称为数据挖掘步骤。此外，提取的图案可 以称为频繁时空图案。

例如，频繁时空图案13以及其他时空图案是在区域邻近图形的集合中 预定数量的区域邻近图形11中出现至少一次的图案。相同的图案还可以在 一个区域邻近图形11中出现多次。这在图2C中被示出，显示了示例区域 邻近图形11、11′、11″集合，其中的两个图形包含图案13，由此在该图中， 第一图形11包含图案13两次，最后一个图形11″包含图案13一次。在该 示例中，图案13可以被认为是频繁的，因为其出现在三个图形中的两个中。 图2D示出了在图2C的区域邻近图形集合中出现三次的频繁时空图案13。

在一些实施方式中，为了执行提取步骤36，针对每个时空图案13确 定间隔两个不同区域邻近图形11中两次连续出现时空图案13的欧几里得 距离。确定的欧几里得距离低于空间阈值的时空图案13然后被提取。示出 这种处理方式的示例在图3A中示出。在图3A中，示出了5个连续帧1， 其中的一些或全部包括两个时空图案13、13″的一个或两个。图案13、13″ 被包含在区域邻近图形中，为了容易辨认在图3A中省略了该图形。图案 13总共出现6次，图案13″总共出现5次。标记为“A”的图案13的出现 可以被认为满足空间阈值的约束，因为它们从一个帧到另一个帧彼此接近， 即图案13分别在帧t₁和t₃、帧t₃和t₄、以及帧t₄和t₅之间没有移动太远。 这同样适用于标记为“D”的图案13的出现和标记为“C”的图案13″的 出现。欧几里得距离低于空间阈值的图案在图3A中用箭头连接。例如， 对于图案13，帧t₁中的出现“A”没有连接到帧t₃中的出现“D”，因为 它们彼此太远。

根据这些实施方式中，在提取步骤36中可能丢弃其出现在区域邻近图 形集合中空间上离得太远的图案。实际上，空间上接近的图案更可能代表 同一感兴趣对象的部分。

在一些实施方式中，为了执行提步骤36，针对每个时空图案13确定 在两个不同区域邻近图形11中间隔时空图案13的两个连续出现的区域邻 近图形11的数量。该数量可以称为中间图形(或中间帧，因为一个图形对 应于一个帧)。确定的区域邻近图形11的数量低于时间阈值的时空图案 13然后被提取。再次参考图3A，标记为“C”的图案13″的出现可以被认 为满足时间阈值的约束，因为在帧t₂的区域邻近图形和t₃的区域邻近图形 中间隔图案13″的两次连续出现的区域邻近图形11(即帧)的数量为0。 这同样适用于帧t₃和t₄中的出现“C”。类似地，在帧t₁的区域邻近图形 和t₃的区域邻近图形中间隔图案13的两次连续出现的区域邻近图形11(即 帧)的数量为1，这可以被认为满足时间约束。确定的中间帧数量(或图 形数量)低于时间阈值的图案在图3A中用箭头连接。例如，帧t₁中标记 为“B”的出现没有连接到帧t₅中标记为“E”的出现，因为它们在时间上 彼此间隔。

根据这些实施方式，在提取步骤36中可能丢弃其出现在时间上在区域 邻近图形集合中离得太远的图案。时间上，时间上接近的图案更可能代表 同一感兴趣对象的部分。

此外，可能的是以出现图形代表频繁时空图案，如图3B中所示。在 出现图形17中，每个节点(A-E)对应于频繁图案的出现。边由连接频繁 图案的箭头表示，如果它们复合上述的时间和空间约束，即如果它们在空 间和时间上足够接近。因此，在出现图形17中，频发时空图案由连接的节 点示出。频繁时空图案(图3B中的A、D和C)的每个代表感兴趣对象 的部分。

再次参考图1，在第五个步骤38中，确定在连续帧1之间的提取的频 繁时空图案13的轨迹之间的不相似度。在一些实施方式中，确定轨迹的不 相似度的步骤38包括以下步骤。

第一，确定区域邻近图形中的每个时空图案13、13′的图心。图4A示 出了两个帧1、1′，对应于两个区域邻近图形(未示出)，每个包括两个 频繁时空图案13、13′。图案的图心由黑点15、15′指示。帧(或图形)中 的时空图案的图心对应于该帧(或图形)中的该图案的所有出现的质心。 在图4A中示出的示例中，为了容易辨认仅示出了图案13、13′的每个的一 个出现。

第二，确定对应于每个区域邻近图形中两个不同时空图案13、13′的 两个不同图心15、15′之间的欧几里得距离x_t(图4A中t＝1,2)。

第三，计算在一些区域邻近图形上的两个不同图形15、15′之间的欧 几里得距离x_i的平均值。

由此，在上述的实施方式中，使用以下公式计算轨迹的不相似度dis：

$dis=\frac{{\Sigma }_{t=1}^n{x}_t}{n},---\left(1\right)$

其中x_t对应于帧t中的两个时空图案的图心之间的欧几里得距离，且 n是被考虑的的帧数量。

在一些实施方式中，为了执行步骤38的确定轨迹的不相似度，针对在 两个不同区域邻近图形中间隔时空图案的每一个的两次连续出现的一个或 一些区域邻近图形插入图心。实际上，一些频繁时空图案在连续帧(或区 域邻近图形)的每一个中可以不出现，即它们可以符合上述空间和时间约 束，即使在它们的出现之间有一些帧。在该情况中，针对频繁时空图案不 出现的帧插入图心以能够计算帧(即区域邻近图形)的每一个中的图心之 间的欧几里得距离。然后可以计算所有区域邻近图形的两个不同图心之间 的欧几里得距离。

再次参考图1，在第六个步骤39中，频繁时空图案13根据确定的轨 迹的不相似度被聚集以产生对应于所述一个或多个感兴趣对象中的一个感 兴趣对象的至少一个群集。

在一些实施方式中，聚集步骤39可以有利地包括聚集计算出的两个不 同图心之间的欧几里得距离的平均值低于不相似性阈值的时空图案。可以 使用等式(1)来计算两个不同图心之间的欧几里得距离的平均值。

在一些实施方式中，聚集步骤39包括以下步骤。

第一，频繁时空图案被聚集以产生对应于多个感兴趣对象的分级的群 集集合。图4B示出了提取的频繁时空图案F、G、H、K、L、M、N的这 样的群集25、26、27的集合200的示例。坐标21表示该频繁时空图案F、 G、H、K、L、M、N的轨迹之间的不相似度。对于给定的不相似度，两 个频繁时空图案一起被分组在一个群集中。得到的群集可以然后随着不相 似度增加与另一群集或另一频繁时空图案分组在一起。按照这样进行直到 所有的频繁时空图案被包含在单个群集中。在图4B的示例中，针对第一 不相似度群集图案G和H，然后针对比第一个不相似度大的第二不相似度 将群集G、H与图案F进行聚集，以得到群集25。

第二，在分级的群集集合200中仅选择不相似度低于预定阈值的群集。 仍然参考图4B，群集25、26、27被选择。群集25包含三个频繁时空图案 F、G、H，群集26、27的每个包含两个频繁时空图案，K、L和M、N。 在该示例中，虚线23表示预定阈值，在该线23以下的所有群集被选择。

根据这些实施方式，由于有了步骤38的确定频繁时空图案的轨迹的不 相似度和聚集步骤39，重组在提取步骤中找到的具有相似轨迹的对象部分 是可行的。因此，可以以完全自动的方式找到整个感兴趣对象。

有利地，可以使用称为群集的寿命的量来设定图案轨迹的不相似度的 阈值。群集的寿命是形成群集的不相似度与该群集与另一群集或频繁时空 图案组合的不相似度之间的差。在图4B中，示意性示出了群集27的寿命 29。然后可能的是考虑寿命最长的群集并选择在低于被考虑的群集与另一 群集或图案组合的不相似度的不相似度形成的群集。在图4B的示例中， 群集26可以被认为是具有最长寿命。

再次参考图1，根据这里公开的实施方式的上述方法的任意还可以包 括步骤40：使用在视频序列中检测和跟踪的一个或多个感兴趣对象来概括 视频序列以得到视频概要42。优选地，该概括步骤40可以包括基于其轨 迹的空间重叠确定交互的感兴趣对象。概要42可以例如包括视频序列集， 显示在视频或电影中涉及的主要对象及其交互。概要42还可以包括文本、 可扩展标记语言(XML)文件等。

视频概括是根据本公开的实施方式的方法的一种可能的实施示例。另 一示例是视频编辑，其中可以使用编辑器来检测和跟踪视频后期制作过程 中的主要对象及其关系。

本公开的一些实施方式还提供用于在视频序列中自动检测和跟踪一个 或多个感兴趣对象的设备，该视频序列包括使用移动相机获取的若干个连 续帧。图5是这种设备的示意性示出。

设备100包括用于执行根据上述实施方式的方法的装置。特别地，设 备100包括帧提取器103，被配置成依据颜色将视频序列的每个帧分割成 区域并针对每个帧产生分割的图像。设备100还包括图形引擎105，被配 置成从每个分割的图像推演出包括节点和边的区域邻近图形。如之前所示， 每个节点定义区域且每个边连接分割的图像的邻近区域的两个节点，以及 从所述若干个连续帧的分割的图像推演出的区域邻近图形形成区域邻近图 形集合。设备的数据挖掘引擎107被配置成从该区域邻近图形集合提取频 繁时空图案。

仍然参考图5，设备100还包括聚集引擎109。该聚集引擎109被配置 成确定连续帧之间的提取的频繁时空图案的轨迹之间的不相似度。聚集引 擎109还被配置成根据确定的轨迹的不相似度聚集频繁时空图案以产生对 应于所述一个或多个感兴趣对象中的一个感兴趣对象的至少一个群集。

根据本公开的实施方式，用于自动检测和跟踪感兴趣对象的设备100 还可以包括概括引擎111，被配置成使用在视频序列中检测和跟踪的一个 或多个感兴趣对象概括该视频序列以得到视频概要。

有利地，根据这里公开的实施方式的设备100还可以包括界面装置 113、115、117，被配置成将设备与用户或应用对接。例如，界面装置可以 包括视频平台应用编程接口(API)113，使得视频平台(例如YouTube) 能够使用设备100的对象检测和跟踪和/或概括功能，即识别可以在没有来 自用户的交互的情况下被处理。可替换地，界面装置可以包括GUI，例如 被配置成允许用户上传其对其视频概要感兴趣的视频。视频可以例如从用 户的本地计算机硬盘119或从在线视频平台118被上传。界面装置还可以 包括开放API117，其可以基于网页服务。开放API117实现从任意应用 (例如RESFTful(表述性状态转移)网页服务允许其他应用使用GET和 POST请求方法发送超文本传输协议请求到网页服务)对接设备100。

本领域技术人员可以容易知道上述方法的实施方式的步骤能够由编程 计算机来执行。这里，一些实施方式用于包括程序存储设备，例如数字数 据存储介质，其是机器可执行的并编码机器可执行或计算机可执行的指令 程序，其中所述指令执行这里所述的方法的一些或所有步骤。程序存储设 备可以例如是数字存储器、磁存储介质，例如磁盘或磁带、硬盘，或光学 可读数字存储介质。实施方式还用于包括被编程以执行这里所述的方法的 所述步骤的计算机。本领域技术人员可以理解附图的流程图和示意图表示 过程的实施方式可以基本上在计算机可读介质中被表述并因此由计算机或 处理器执行，即使没有明确示出这样的计算机或处理器。

虽然本发明的一些实施方式已经在附图中示出和之前的具体实施方式 中描述，应当理解本发明不限于公开的实施方式，而是能够在不背离权利 要求书提出并定义的本发明的情况下有许多重新排列、修改和替代。