通过实时视频动作分析理解视频内容

摘要

描述了一种用于相机运动分析和移动对象分析的方法和集成系统，和主要从没有镜头变化的视频和视频段中的相机运动参数提取语义的方法。这样的视频的典型例子是由数码相机拍摄的家庭视频和专业视频或电影的一个片段或剪辑。提取的语义能够直接地用于多个对视频/图像的理解和管理应用中，例如评注、浏览、编辑、帧增强、关键帧提取、全景生成、打印、检索、汇总。还描述了不依赖于对象的先验知识的检测和跟踪运动对象的自动方法。此方法能够实时地执行。

说明书

背景

视频运动分析，包括相机运动分析和对象运动分析，是理解视频内容的重要部分，并且，内容理解在许多多媒体系统(包括个人计算机PC，数字娱乐系统，相机和甚至打印机)中的视频浏览、检索、编辑、打印等之中扮演着十分重要的角色。

目前，打印机适于表现平面(二维)的媒体内容，诸如文档和图像，但视频打印尚属劳动密集型问题，因为三维(3-D)信号(也就是两个空间维度和一个时间维度)，视频包括更多具有相当大量的冗余的信息，这些不能被诸如纸张的静态媒体简单地表现出来。

视频打印的一个方法是从视频剪辑(video clip)中选择关键帧，并打印这些选中的关键帧。不幸的是，关键帧提取的任务不是微不足道地自动完成的，因为，选取具有最大语义含义的关键帧是困难的计算机视觉和人工智能问题。问题的解决受到限制，因为通常能够令人接受的是仅打印合理数目的关键帧。关键帧可以通过对低层次的内容特征(例如，颜色、纹理、运动等)的分析来进行抽取。

现有的运动分析和内容理解的方法不能够一般性地满足所有类型的视频(例如，家庭视频和专业视频，短视频剪辑和长视频记录等)，或者对于普通处理系统(诸如PC和类似相机的嵌入系统)来说太慢。现有方法通常设计用于专用任务，例如，跟踪人的运动(利用已知面部模型)或者车的运动(利用预定义的汽车模型)，并且，具有相应的简化和有限的能力。

发明内容

在一个方面，本发明是估计在连续图像对之间的相机运动的方法，包括从该对连续图像确定运动向量，和基于运动向量估计相机运动的仿射模型。运动向量的确定包括：将该对连续图像之一分割为多个像素块；选择对应图像中至少一个特征的块；确定对应于各所选块的亮度值；基于亮度值，将所选的块与该对连续图像中另一个图像中的像素块进行匹配；并且确定与该对连续图像中的匹配块相关联的运动向量。估计出的仿射模型确定相机运动参数集合。

在本发明另一个方面，将相机运动参数转换为语义含义的方法包括：从由相机捕获的连续图像对确定运动向量；通过基于运动向量估计仿射模型来确定相应的相机运动参数集合；并且从相机运动参数集合生成语义含义。通过将相机运动参数集合量化为多个幅度和方向；和通过识别被量化为基本相同的幅度和方向的连续的相机运动参数集合，从量化的集合生成至少一个句子，来生成语义含义。

在本发明的又一方面，在被相机捕获的图像中检测对象的方法包括：从连续图像对确定运动向量；基于运动向量估计仿射模型；根据运动向量与仿射模型估计，计算连续图像对中的相应像素块的残差；并基于该残差检测对象。

在本发明的再一方面，用于视频运动理解的设备包括：相机运动估计器，它包括使用亮度图像用于光流分析以便从连续图像对中的像素块生成运动向量的光流分析器，和基于运动向量生成仿射模型估计的仿射模型估计器；和对象检测器，其基于仿射模型估计确定块的残差，基于残差消除局外(outlier)块，对留下的块进行滤波，其中，对象检测器生成识别对象大小和位置的边界框。

附图说明

结合在说明书中并构成说明书一部分的附图，举例说明本发明的实施例，并且和说明一起解释本发明。在附图中，

图1描述用于运动估计的块匹配的实施例；

图2描述三步搜索算法的实施例；

图3描述相机运动的模型；

图4是依照本发明实施例的估计相机运动的方法的流程图；

图5示出用于视频帧序列的仿射模型参数；

图6A，6B，6C描述量化为具有滞后阈值的幅度级别和方向的相机运动量化；

图7描述句子和段落的生成的实施例；

图8是依照本发明实施例将相机运动参数转换为语义含义的方法的流程图；

图9是用于检测对象的设备的实施例的框图；

图10A描述快速扩散(flooding)算法的实施例；

图10B描述边界框；

图11是依照本发明实施例的对象检测方法的流程图；

图12描述对象区域被划分为边际部分和中央部分；和

图13是依照本发明一个实施例的用于视频运动理解的设备的框图。

具体实施方式

参考附图对本发明相关的实施进行描述。在不同的图中，相同的参考数字表示相同或者相似的元件。下文的详细的描述不对本发明进行限制。作为替代，本发明的范围由随附的权利要求进行定义。

描述了用于相机运动分析和运动对象分析的集成系统，和主要从没有镜头转换的视频和视频剪辑中的相机运动参数提取语义的方法。这些视频的典型例子是由数码相机拍摄的家用视频和专业视频或电影的片段和剪辑。提取出的语义能够直接用于对视频/图像的多种理解和管理应用，诸如注释、浏览、编辑、帧增强、关键帧提取、全景生成、打印、检索、汇总。还描述了不依赖于对象的先验知识的、检测运动对象的完全自动的方法。而且，描述了加速处理的措施使得这些方法能够实时执行。

依照本发明一个实施例的实时视频语义分析使用运动信息，基于计算机视觉和统计模式识别的知识来理解视频内容。一般来说，一种分析包括至少两个部分：全局/相机运动估计，和前景/对象运动分析。相机运动估计涉及光流分析、相机运动估计和语义含义提取，语义含义提取进行相机运动量化、句子生成和段落生成。相机运动估计将相机运动的仿射模型表示转换为语义表示。对象运动分析涉及不需要对象先验知识的对象检测和跟踪。为了得到快速和鲁棒的实现，相机运动估计可以包括加速的块选择和块匹配，并且对象跟踪可以使用空间信息增强的彩色柱状图。

因此，可以基于相机运动分析将输入的帧或者图像序列有效划分为组块(chunk)，并且可以用便利的方式为这些组块加索引，例如，从0.1秒到2.0秒，相机具有快速的移向目标的运动；从2.0秒到5.0秒，相机焦距固定，等等。随后，检测该组块中的对象，并跟踪对象的运动，使得每个视频帧进一步由运动对象的参数(例如，位置和大小)来索引。对比以前的系统和方法，本发明的系统和方法能够利用容易得到的处理器完成实时的操作。

相机运动估计

相机(全局)运动指的是由诸如镜头拉近推远(zooming)、摇动(paning)和旋转(rotation)的相机操作导致的运动。物理的相机运动通常是在两个连续帧之间适度的和时间连续的变化。这个效应可以被观测为依照由相机运动定义的仿射变换的、全帧范围内良好调节的光流变化。在实时视频中，这个情况会由于前景运动和其他信号噪声而多少受到损害。相机运动估计基于观测到的噪声光流行为而发现相机运动仿射模型。一般来说，这包括光流分析和仿射模型估计。

光流分析

光流分析涉及帧到帧的运动向量的确定或者运动估计。用于运动估计的基本方法是块匹配。如图1所述，在第k帧中位于位置(m，n)的具有像素维数(W，H)的块与第k-1帧中偏移了运动向量(i，j)的块之间的强度差能够由下式指示：

$>>>E>>k>,>m>,>n>>>>(>i>,>j>)>>=>>1>>W>·>H>>>>\Sigma >>>x>1>>=>m>>>W>+>m>over>>>\Sigma >>>x>2>>=>n>>>H>+>n>over>>e>>(>>I>k>>>(>>x>1>>,>>x>2>>)>>,>>I>>k>->1>>>>(>>x>1>>+>i>,>>x>2>>+>j>)>>)>>->->->Eq>.>1>>>$

其中，I通常是像素的亮度。误差度量E(i，j)可以是方差e(I_k，I_k-1)的和，或者绝对误差e(I_k，I_k-1)的和，后者具有较小的计算代价。与块相关的运动向量被认为是依照下式在搜索范围(M，N)内获得最小失真(distortion)的向量：

$>>V>>(>k>,>m>,>n>)>>=>>>arg>min>>>i>,>j>>>\{>>E>>k>,>m>,>n>>>>(>i>,>j>)>>\}>,>0>\le >|>i>|>\le >M>,>0>\le >|>j>|>\le >N>->->->Eq>.>2>>>$

一个便利的搜索区域是M＝N＝8，尽管能够使用其他搜索区域例如，M＝N＝16。基于8×8块或者像素阵列的运动向量确定是很多普通视频编码算法，包括MPEG-2，MPEG-4和Windows Media的特征。实际上，由这些或者其他编码算法生成的运动向量能够与如下描述的相机运动估计和对象运动分析的其他特征一起使用。然而，应理解，在例如MPEG-2的压缩算法中的运动向量确定旨在在没有显著的失真的情况下优化压缩，而不是确定相机运动。

在一个实施例中，为了找到公式2中给出的运动向量，可以在搜索区域内进行穷尽搜索，并可以提供全局的最优化。取决于处理器，这样的搜索要实时完成可能计算强度过高。因此，在另一个实施例中，可以使用快速搜索算法取代穷尽搜索，诸如二维(2-D)对数(log)搜索方法，其在J.R.Jain等人发表的“替代测量和其在帧间图像编码中的应用”(IEEE Trans.on Communications，vol.COM-29，pp.1799-1808(Dec.1981))中描述，菱形搜索算法，其在J.Y.Tham等人的“用于块运动估计的、新颖的无限制的基于中央的菱形搜索算法”(IEEETrans.On Circuits and Systems for Video Technologyvol.8，pp.369-377(Aug，1998))，和其他已知搜索方法。许多快速搜索算法是基于搜索区域内的失真V是具有小的局部最小值的单调凸表面的假设。

在另一个实施例中，如在T.Koga等人的，“用于视频会议的运动补偿帧间编码”(Proc.Nat’l Telecommunications Conf.pp.G5.3.1-G5.3.5，New Orleans，LA(Dec，1981))中描述的快速三步搜索算法，能够被使用，其能够平衡速度和语义准确性。三步搜索算法在图2中进行描述。令搜索区域为-8到8。在第一步中，在一对连续帧之一中搜索具有9个顶点的16×16像素窗口(对于步骤1，标示为标号1)。如图2中所示，令第一个窗口的中心位于该对连续帧中另一个帧的原点。依照公式2，在9个顶点处的9个失真值被计算出来。在该例子中，该九个顶点中右上方的一个产生在第一步中计算出的9个失真值中的最小值。在第二步中，核对(check)中心位于第一步所识别的给出最小代价函数的顶点的5×5窗口。因而，计算在该5×5窗口(由标号2标示)的九个顶点的又九个失真值。在这个例子中，九个顶点中右下方的一个产生第二步计算的九个失真值中的最小值。在第三步中，核对(check)中心位于第二步所识别的给出最小代价函数的顶点的3×3窗口。因而，计算在该3×3窗口(由标号3标示)的九个顶点的又九个失真值。与该3×3窗口关联的九个失真值中的最小值(在该例子中，是右下方的点)产生最终运动向量。

基于公式2的最小失真的运动向量确定对于视频编码很有效。但是，这个运动向量确定技术可能因为随机噪声(导致搜索区域中失真分布的很小变化)而提供错误结果。这样的小变化，可能在帧的一致部分的块中发生，比如无云的天空。因此，在本发明的一个实施例中，通过确定图像中的多个块的运动向量并且随后除去局外，而对运动向量进行“滤波”。在这个应用中，局外是具有与帧中剩余块或者多个块的集合的运动向量的一致性实质不同的运动向量的块。该一致性有利的是从仿射模型估计确定的，将在下文进行更详细的描述，并且其基于在使用仿射模型预测的运动向量和实际运动向量之间的误差间的变化而获得。局外块是那些具有大于阈值的运动向量预测误差的块，该阈值可以设置为诸如一个标准偏差的值。

一般来说，局外分为两类：因为对象运动导致的局外和因为块的失配导致的局外。因为对象运动导致的局外，包括了对对象检测有用的信息。例如，在前景中包括有河岸线，背景包括河上的船和河的其他岸线的场景中，船(也就是对象)具有与相机运动不同的自身运动。在局外是由于块失配导致的另一个例子中，一场景包括前景中戴帽子的人和背景中具有斜边的建筑物，位于该建筑物的墙壁上的块具有简单的区域纹理，并且随后它们产生搜索区域内小的失真分布变化，其产生的运动向量更易于受到噪声的干扰。局外的其他原因包括亮度的突然变化，相对相机运动幅度有限的搜索区域，和来自快速搜索方法的局部最小值。

局外能够影响仿射模型估计，所以如上所述通过滤波来减少局外块和运动向量的数目是有利的。减少局外数目的另一个方式是通过选择与计算相匹配的块而不是简单的使用从图像任意分割成的所有的块。选择匹配块的一种方式是特征选择，其可以有效的减少局外的数目和块匹配计算量(运动向量确定)。只有与图像中所选择的一个或多个特征相关联或者相对应的块才需要用于块匹配，这对于实时应用当然可能是有利的。

将会理解图像或视频帧包括一组对象(诸如，天空，船，建筑物，人等)。对象可以是静止或者运动的，并且对象可以是不同的颜色、纹理、形状等。信号或者图像或者视频帧的特征通常是从该信号/图像/视频帧中计算得出的某个事物，并且表示数据特性的一个方面。例如，色彩柱状图和色彩布局是图像或视频帧的两类色彩特征，它们源于图像的色彩。不是使用帧中所有块进行运动估计，而是可以采用基于特征的选择方法，也就是，基于图像的一个或者多个特征选择块。这些特征可以是色彩特征、纹理特征和边缘特征等。

特征选择可以通常为基于像素的或者基于块的。前者基于逐像素的估计来选取特征，可以涉及KLT转换或者Moravec算子。基于块的特征选择基于整个块的特性选择特征，并且可以涉及时间纹理分析或者离散余弦变换(DCT)能量统计。

一类基于块的特征选择方法使用边缘检测在图像中选择块。有许多边缘检测方法，诸如Sobel，Laplace和Canny方法，这些方法具有不同的复杂度和边界质量。一般来说，边缘检测是通过计算输入图像的边缘映射(图像的一个特征)完成的，并且边缘映射用作选择块的特征，也就是只有包括足够边缘的那些块才被选中。

基于边缘的特征选择方法的一个特别例子使用如下的2个3×3的1-D Sobel方向算子：

$>>y>=>\begin{array}{}>>>->1>>>->2>>>->1>>>>>0>>>0>>>0>>>>>1>>>2>>>1>>>>>>>$ >>x>=>\begin{array}{}>>>->1>>>0>>>1>>>>>->2>>>0>>>2>>>>>->1>>>0>>>1>>>>>>>\end{array}$\end{array}$

这些算子用于块的像素亮度值，结果的绝对值之和能够被用来提取边缘信息。在一个实施例中，只有那些暴露了一定数目边缘像素的块才在运动补偿中被选中。

用于选中的块的判定阈值可以有利地、动态地依照图形的梯度幅度的统计分布来调整。Canny边缘检测，例如，涉及能够影响检测的边缘的最终结果的两个阈值(一个较高的和一个较低的)。这些阈值可以使用梯度幅度的统计数据来确定。

除了识别和消除局外，可以有利地采用附加措施来进一步减小计算代价并且提高速度，使得能够由较低性能的处理器完成实时操作。这些附加措施包括图像分辨率下采样、块选择下采样和半途终止(halfwaytermination)，并且和消除局外是有效滤波类似，这些附加措施也可以认为是滤波。

在图像分辨率下采样中，运动向量确定过程是对降低了分辨率的图像进行的。例如，输入视频可以被下采样为320×240像素/帧(1/4VGA)或者甚至到160×120像素/帧。下采样到1/4VGA或者更低的分辨率在语义含义提取和运动对象检测的方面实现满意结果，同时显著降低了计算代价。

在块选择下采样中，选择一个块进行处理，并且在假设相邻的块具有相似的运动行为的情况下，对所选块的所有紧邻块不进行处理。

半途终止涉及计算块的补偿残差。如果通过累加块的像素差别产生的块的累积失真V大于当前观测的已经处理过的块的最小失真，则终止计算，并且略过该块。这通过避免不必要的计算也降低了代价。

仿射模型估计

相机运动C可以被建模为4个参数的函数，参数是相机焦距F和分别围绕空间坐标正交轴X，Y，Z的旋转角度α，β，γ。这可以由C＝C(F，α，β，γ)表示，并且由图3描述。空间中的一个任意点P(x，y，z)依照如下的向量变换被投影到相机视野平面中的点Q(u，v)。

$>\left(\begin{array}{}>>>u>>>>>v>>>>>=\left(\begin{array}{}>>>zoom>>>rotation>>>>pan>x>>>>>>rotation>>>zoom>>>>pan>y>>>>>>·\left(\begin{array}{}>>>x>>>>>y>>>>>z>>>>>=>A>·\left(\begin{array}{}>>>x>>>>>y>>>>>z>>>>>->->->Eq>.>3>>>\end{array}\right)\end{array}\right)\end{array}\right)\end{array}\right)$

其中，zoom，rotation，pan_x和pan_y是由相机运动C决定的4个参数。这些参数之间的关系在J.Park等人的“根据基于模型的视频编码的图像序列的相机参数估计(Estimation of Camera Parameters from ImageSequence for Model-Based Video Coding)”(IEEE Trans.OnCircuits and Systems for Video Technology vol.4，pp.288-295(June 1994))中进行了描述。因为不存在用于非立体视频信号的深度映射信息，z＝1。

公式3将被视为列向量(x，y，z)的仿射变换。一般来说，仿射变换是线性变换后跟随平移，例如A(x)＝Mx+v，其中A(x)是向量x的变换，M是矩阵，v是向量。对比典型的在矩阵M中有6个参数的仿射模型，公式3的模型具有4个参数，因为能够处理的更快，所以将更加适合于对于宽的视频范围进行实时语义含义分析。当然，将理解，不需要对4个参数进行化简。

依照如下矩阵表达式，通过使用最小方差(LSE)回归估计仿射模型。

A＝(X^TX)^-1X^TU， $>>X>=\left(\begin{array}{}>>>>x>1>>>>>x>2>>>>·>·>·>>>>x>N>>>>>>>y>1>>>>>y>2>>>>·>·>·>>>>y>N>>>>>>1>>>1>>>·>·>·>>>1>>>>>,>>>$ >>U>=\left(\begin{array}{}>>>>u>1>>>>>u>2>>>>·>·>·>>>>u>N>>>>>>>v>1>>>>>v>2>>>>·>·>·>>>>v>N>>>>>>->->->Eq>.>4>>>\end{array}\right)$\end{array}\right)$

其中，N是样本，也就是所选的特征块的数目。每一个样本包括观测结果(x_i，y_i，1)和输出(u_i，v_i)，其是当前和前一帧中通过运动向量相关联的坐标值。可以采用奇异值分解来解出A。通过LSE回归进行仿射模型估计问题的方面在S.Boyd和L.Vandenberghe，ConvexOptimization，Section 1.2，Cambridge University Press(2004)中进行了描述。

通过反复迭代仿射模型，也就是使用先前计算的结果计算公式4，那些残差大于阈值的块能够被作为局外排除。这也可以认为是对运动向量的滤波，就像基于边缘的特征检测是这样的滤波。阈值可以被预定义，并且可以基于误差的标准差的函数。残差R可以通过如下给出：

$>>>R>k>>>(>m>,>n>)>>=>E>>(>>P>k>>,>A>·>ver>>P>~>>>k>->1>>>)>>>|>\begin{array}{}>>>>P>k>>\in >>B>k>>>(>m>,>n>)>>>>>>ver>>P>~>>>k>->1>>>\in >>B>>k>->1>>>>(>m>+>>v>s>>,>n>+>>v>y>>)>>>>>>>->->->Eq>.>5>>>\end{array}$

其中，P_k，是通过运动向量(u_x，v_y)相关联的块。即使是固定的阈值，在每次迭代中可能会识别出新的局外，并排除它们。该模型的迭代在给定迭代次数之后终止，或者在仿射参数集合变得稳定到希望的程度时终止。为了防止可能的发散，可以定义最大的迭代次数。在一个实施例中，大多数帧的仿射模型估计可以在完成3或4次模型迭代之后，变得满足要求。

图4是如上所述在两个图像间估计相机运动的方法的流程图。在步骤702中，图像中的一个被分割为一个或者多个块，并且在步骤704中，一个或者多个这样的块被选中用于进一步处理。该选择优选地通过在图像中寻找对应于对象的一个或多个边缘的块来执行。确定对应所选择的块的亮度值(步骤706)，并且随后将所选择的块与该两个图像的另一个中的对应块进行匹配(步骤708)。随后(步骤710)为匹配的块确定运动向量，并且根据该图像之间的相机运动的估计的仿射模型确定相机运动参数的集合(步骤712)。

语义含义提取

通过仿射模型估计，为每一个帧确定运动参数集合。每个集合代表在捕获该特定帧的时刻的相机运动。应该理解的是，存在依照相机的兴趣自由度，定义相机仿射模型的不同的方式。在一些例子中，诸如数字可便携式摄像机和监视视频，相机运动参数能够被记录并且已知，因此不需要对相机模型进行估计。在任何情况下，所述集合被汇总用于获取高级别的语义含义。

图5显示用于若干帧的序列的仿射模型参数zoom，rotation，pan_x和pan_y。依照本发明的一个实施例，语义含义被从模型参数中提取出来。例如，对于在图5中显示的帧，相机运动可以更合适的称为“聚焦”，例如关注一个场景或者对象。用于语义含义提取的三个技术，在下文进行更详细地描述，是相机运动量化、“句子”生成、和“段落”生成。依照所需的提取级别，句子和段落生成的一个或者两者可以被使用。

在相机运动量化中，相机运动也就是仿射模型参数首先被量化为若干幅度级别和方向。图6A显示用于对相机摇动参数进行量化的示例性图解。其他参数，诸如拉近推远和旋转可以相似地简单量化。在这个图解中，沿着正交轴(诸如X和Y轴)摇动的幅度被分为四个区域：聚焦，慢，中等，快。运动方向被如图6B中所示进行量化。为了对相机的震动和噪声干扰鲁棒，如图6C中所示，优选地采用滞后阈值来决定平移。应理解可以使用其它量化来代替图6A，6B，6C中描述的那些。

在“句子”生成中，在小时间跨度内(例如，几秒钟)的图像序列基于它们仿射模型的相似性而自然地聚类，生成合理数目的语义区域。换句话说，分享相同的量化的相机运动参数的相邻的帧被融合到一个更长的时间跨度中，在该应用中，这被称为“句子”。这个融合步骤将一个视频剪辑汇总到若干个句子中，在句子中相机运动是一致的，也就是仿射模型参数被量化为相同或者相似的级别。同时，为每一个句子计算平均仿射模型。

“段落”生成构建在句子生成之上，并且因此段落是对更长的(数10秒的)图像序列的提取。如下文中更详细地解释，对相邻(连续)句子持续时间的柱状图进行评估。执行更进一步的融合步骤，将视频汇总到若干由敏感度阈值确定的意义段落中。基于它们的相似性，句子被融合进入一个或者多个段落中，该相似性可以依照仿射模型参数之间的距离度量来进行测量。合适的距离度量是参数之间的欧几里德距离。每一个段落的语义含义使用加权的仿射模型进行重新估计。

图7中描述了仿射模型估计、参数量化、句子生成和段落生成的过程，其通过在视频时间线上进行标记来指示视频剪辑的帧的连续。假设视频剪辑中有N_f个视频帧，并且设每一个帧i(其中i＝1，2，...，N_f-1，N_f)具有持续时间t_fi，估计的仿射模型A_fi，和量化的相机运动S_fi。句子生成产生Ns个句子，在图7中，每一个句子j由相应的量化的相机运动S_sj、仿射模型A_sj、持续时间t_sj表示，其中：

$>>>A>sj>>=>>>>\Sigma >j>>>A>fi>>·>\{>1>|>>S>>f>i>>>=>>S>>f>>(>1>+>i>)>>>>\}>>>>\Sigma >i>>\{>1>|>>S>>f>i>>>=>>S>>f>>(>1>+>i>)>>>>\}>>>,>>>$ >>>t>sj>>=>>\Sigma >i>>>t>fi>>·>\{>1>|>>S>fi>>=>>S>>f>>(>1>+>i>)>>>>\}>,>j>=>1,2>,>.>.>.>,>>N>s>>->->->Eq>.>6>>>$$

在句子生成后，生成持续时间t_sj的柱状图，估计出持续时间t_sj的分布。持续时间容忍阈值T_d被用于将句子融合到N_p个段落中。那些具有持续时间超过T_d的句子作为锚句子S_A，其他句子基于距离测量融合进这些锚句子中，其中距离可以是两个仿射模型之间的欧几里德距离。

每一个段落k的相机运动的语义含义由公式7进行评估：

$>>M>>(>>A>s>>,>>A>>>s>A>>,>k>>>)>>=>\{>1>|>D>(>>A>s>>,>>A>>>s>A>>,>k>+>1>>>)>>>D>(>>A>s>>,>>A>>>s>A>>,>k>>>)>\}>>>$

S_pk＝Q(A_pk)

$>>>t>pk>>=>>\Sigma >j>>>t>>s>j>>>·>M>>(>>A>>s>j>>>,>>A>>>s>A>>,>k>>>)>>->->->Eq>.>7>>>$

其中，Q(A)是从仿射模型参数到语义相机运动的量化映射，D是所选的距离。在这个处理中，阈值T_d设置检测语义相机运动中的变化的敏感度。

图8是如上所述将相机运动参数转换为语义含义的方法的流程图。在步骤102中，运动向量被确定或者被提供，在随后的步骤104中，根据运动向量确定相机运动参数。运动参数的集合被量化(步骤106)，并且相似地量化的集合被识别为句子和(可选地)段落(步骤108)。

对象检测和跟踪

在本应用中，在视频序列中运动对象通常定义为具有感兴趣的运动程度和语义含义的区域。通过在视频序列的每个连续帧中找到对象的位置和大小来有利的对运动对象的运动进行跟踪。对比先前的经常涉及一些简化的运动对象检测和跟踪方法，诸如限制为面部或者预定模型的跟踪，(例如，感兴趣对象的三维模型，诸如汽车)，依照本发明的运动对象检测是仅仅基于运动信息的，不需要先验知识。

对象检测

依照本发明，运动对象检测是基于前景运动行为不同于背景运动行为的假设的，并且运动对象的该区域(也就是前景或者背景)在当依照公式8估计运动补偿残留时，被暴露为局外。

R_k(m，n)＝‖B_k(m，n)-A·B_k-1(m+v_x，n+v_y)‖    Eq.8

其中，R_k(m，n)是从第k帧中，位置(m，n)开始的块的残差；B_k和B_k-1是通过运动向量(v_x，v_y)相关联的块；并且A是仿射模型。应该注意的是，残差R_k的实时估计可能需要降低估计的计算代价。降低代价的一个方式是仿射模型估计过程中，仅在被识别为局外的区域上进行估计。代价被降低，因为其他区域在迭代过程中已经满足LSE准则，也就是说对于符合仿射模型定义的运动参数的块来说，残差将是很小的。

因为局外也可能由背景运动估计中的噪声所导致，运动对象的区域被暴露为局外的假定在实时视频序列中可能不合理。因此，基于运动的对象检测的重要任务是从局外的背景噪声中分辨出实际对象。因此，依照本发明，通过假设兴趣对象具有适度的大小并倾向于位于图像的中心而从背景噪声中分辨出实际对象。适度大小的假设导致暴露足够多的残差并且传递出相当多的语义含义。中央偏置的假设反映这样的理解，就是随着对象位置远离中心，我们对对象的关注降低。应理解，这些假设在方便一般可获得的处理器的实时操作意义上是需要的，但是它们不是必需的。基于这些假设，如下所述通过应用一组权重参数对残差进行滤波。

图9是用于在输入视频序列中检测对象的设备200的框图。应该理解的是，此设备可以被实现为用于执行所述操作的逻辑或者作为一个或多个可编程处理器，或者这些的组合或者其它。

设备200包括如上所述从输入序列中的连续图像对估计相机运动、生成运动向量和仿射模型估计的装置202。模型参数被提供给依照公式8确定残差R_k的装置204。残差，也就是误差图像，被提供给滤波器206，其在滤波了的残差中产生被检测对象的指示。滤波器206有利地包括空间位置滤波器2061、运动幅度滤波器2063、块区域大小和幅度滤波器2065和时间帧滤波器2067中的一个或者多个，这些将在下文进行更详细地描述。

空间位置滤波器2061分配更高的权重给位于帧中央区域附近的块。一个示例性的滤波器函数是指数的，例如：

$>>>f>s>>>(>P>)>>=>>1>>1>->ϵ>>>·>>(>1>->>e>>->\lambda >>(>M>->|>|>P>|>|>)>>>>)>>,>\lambda >=>>>->log>ϵ>>M>>->->->Eq>.>9>>>$

其中，f_s(P)是滤波器的输出，P是被滤波的块；||P||是在块P和图像中央之间的距离；M是预置的值，其权重为零；并且ε和λ是用于标准化滤波器函数的参数，使得其更像一个典型的概率函数。

运动幅度滤波器2063是有用的，因为相机运动幅度越大，倾向于被背景噪声影响的局外就越多。例如，考虑摇动的幅度。一个示例性的运动幅度滤波器函数是基于高斯的，诸如：

$>>>f>m>>>(>|>|>>P>M>>|>|>)>>=>>e>>>->>>|>|>>P>M>>|>|>>2>>>>2>>\sigma >2>>>>>>>$

$>>|>|>>P>M>>|>|>=>sup>>pan>x>2sup>>+sup>>pan>y>2sup>\; >->->->Eq>.>10>>>$

其中，f_m(||P_M||)是滤波器的输出，P是被滤波的块；||P_M||是摇动幅度；并且偏差σ被设置在搜索范围的边界上。

在这些空间位置和运动幅度滤波器之间的差别是它们在帧边界上的行为。空间位置滤波器在帧边界上分配零权重，并且运动幅度滤波器在搜索边界上给定非零权重。这两个滤波器可以通过查表来实现，减少计算权重的计算代价。

在空间位置和运动幅度滤波之后，调节了的残差由公式11给出：

$>>ver>>R>~>>k>>=>>f>s>>>(>P>)>>·>>f>m>>>(>|>|>>P>M>>|>|>)>>·>>R>k>>->->->Eq>.>11>>>$

下文的两个滤波器使用这个调节了的残差。

为了实现块区域大小和幅度滤波器2065，首先将局外块基于它们的连通性聚类进区域。这能够利用如图10A描述的快速扩散算法完成。在图10A中，如果标记有星号的块是连通性搜索的起始种子，则以预定的顺序检查其紧邻的所有块(在图中被指示为编号0-7)。每个被检查的块相应地被合理的标记，使得在随后的搜索中不被再次检查。如果在相邻块中检测到局外块，则为它加标志(在图中，在块4中的菱形标记指示局外)，种子被移入标志的块中，并且在紧邻块中以相同的预定搜索顺序继续搜索。应该注意的是，所有先前检查过的块将被略过，在此例子中，将检查编号2-6的块。

滤波器2065反复地重复这个程序，这对于将所有的局外块连接在一起是一个有效的方法。这个程序能够被考虑为一种基于样本距离的自然聚类算法的简化版本，此算法在P.O.Duda，P.E.Hart，D.G.Stork的Pattern Classification(Wiley，New York(2001))中进行了描述。

一旦所有的局外块被聚类为特定区域，每个区域由边界框(在图10B中)和代表残差幅度有效地表示，代表残差幅度可以被定义为在区域中所有块中残差的最大值。边界框指示一个检测的对象。在一个实施例中，任何大小小于第一个阈值或者幅度小于第二个阈值的区域被滤波除去。如果存在至少一个具有的大小大于第三个阈值的区域，此帧被跳过不用于运动对象检测，因为，可以假设在此帧的仿射模型不可靠。

时间帧滤波器2067可能是有用的，因为不是每一个帧适用于检测运动对象。例如，运动对象的块的残差可能被背景噪声淹没，使得很难检测对象。来自背景块的残差由于复杂的纹理和快速的相机运动而可能是大的。为此，首先将所有或者基本所有的相互连接的块组合到大区域中。时间帧滤波器2067操作来选取具有一个优势(dominant)块区域的帧作为检测对象的候选。因此，只有那些具有优势残差和合适大小的块区域的帧才被保留。这些帧包括检测的对象。其他帧从进一步处理中能够被忽略。

图11是与上述本发明相一致的对象检测方法的流程图。在步骤402中，从连续图像对确定运动向量，并且这些运动向量被用于在步骤404中估计仿射模型。在步骤406中，基于运动向量和仿射模型为图像对的各自的像素块计算残差。在步骤408，基于残差检测对象。

对象跟踪

一旦运动对象被检测到，它的位置和大小(由类似于图10B中描述的像素的边界框表示)能够被提供给运动对象跟踪器，在下文对其进行更详细地描述。依照本发明的运动对象跟踪过程，仅仅需要考虑边界框，而不是运动对象的更精确的轮廓。边界框传达足够的语义含义，并且得到对象的精确轮廓需要更复杂的计算，该计算是当前广泛可获得的处理器不能够轻易实时完成的。

例如，运动对象可以在视频剪辑的开始帧中被检测，并且然后此对象在视频剪辑中的后继帧中可以被跟踪。又例如，运动对象可以被周期性地检测(例如，每100帧一次，或者每2秒一次等)，并且然后运动对象的目标模型可以被更新或者一个更突出的运动对象可能被发现替代当前对象。还又例如，运动对象可以在满足某个准则时(例如，当当前运动对象移出帧时)被检测。

一个被检测到的对象可以有利由其量化的色彩柱状图来表示，色彩柱状图可以被形成于方便的色彩空间中，诸如R-G-B(红-绿-蓝)空间，具有N_RxN_GxN_B个箱(bin)，其中N_R，N_G，N_B分别是用于R，G，B色彩通道的箱的数目。也可以使用R-G-B空间之外的其他色彩空间，诸如YUV空间和洋红-黄-青空间。色彩柱状图的一个优点是对象在经历诸如旋转、缩放甚至非刚性变形的复杂运动时具有鲁棒性。

本发明的另一个实施例中，空间增强的色彩柱状图可以被用于表示检测到的运动对象。边界框500被划分为边际部分502和中央部分504，如图12中所示。在图中，中央部分504(在像素中)的高度和宽度是在边际部分502中高度H和宽度W的一半。每一部分具有其自己的柱状图统计，并且全部的柱状图是这两个区域的柱状图的联合。应该理解的是，能够使用利用空间信息划分色彩柱状图的其他方法。

色彩柱状图优选地标准化为如下的概率形式：

$>>>q>u>>=>>>>\Sigma >>i>=>1>>Nover>>\delta >[>b>>(>>x>i>>)>>->u>]>>N>>->->->Eq>.>12>>>$

其中，δ是Kronecker狄垃克函数；u是柱状图索引；q是柱状图概率；b(x_i)是一个映射函数，它将位于运动对象区域内的像素x_i映射到柱状图的箱的一个入口；N是在对象区域内像素的数目。此处，“入口”意味着箱的索引。例如，如果这里有100个柱状图的箱，数字1-100是定位特定颜色箱的入口(索引)。

在一个实施例中，除了直接使用色彩柱状图，使用一个核函数和为距离中心较远的像素分配较小的权重。这样的基于核函数的跟踪(KBT)在D.Comaniciu，V.Ramesh，P.Meer的“使用平均偏移的非刚性对象的实时跟踪(Real-Time Tracking of Non-Rigid Objects Using MeanShift)”，IEEE Conf.Computer Vision and Pattern Recogniztion(CVPR‘00)，Vol.2，pp.142-149，Hilton Head Island，SC(2000)；和D.Comaniciu，V.Ramesh，P.Meer的“基于核的对象跟踪(Kernel-Based Object Tracking)”，IEEE Trans.Pattern Analysis MachnineIntell.，Vol.25，No.5(2003)中描述。核函数选择的准则是选择具有凸的和单调递减核剖面的函数。Epanechnikov核函数被描述于Comaniciu等人的上述引用的文章中，可以得到显著的计算简化。

利用核函数，目标模型和目标候选被表示为加权的色彩柱状图概率密度函数(PDFs)。接着，找到具有距离目标模型最小距离的目标候选。特别地，给定目标模型和目标候选，在一个实施例中，相似性度量是Bhattacharyya系数，其是发散(divergence)类型测量，具有易懂的几何解释：它是在m维单元向量之间的夹角的余弦。目标模型和目标候选之间的距离是基于Bhattacharyya系数，并且找到目标候选的目标跟踪任务是最小化该距离，等同于寻找Bhattacharyya系数最大化的候选。

对于距离的最小化，能够使用如上引用的Comaniciu的论文中描述的基于梯度的平均位移迭代方法。上述的菱形搜索(DS)和三步搜索(TSS)的组合算法可以被使用。一般来说，在第一步中，DS和TSS算法两者均被应用，其中一个获得成功(在距离最小化方面)后，继续进行处理，另外一个则停止。在第二步中，剩余的算法使用其自身规则继续搜索，直到找到最小化距离。

在对运动对象的跟踪中，目标模型从在对象检测阶段中检测到的对象(也就是滤波器206的输出)获得。目标模型可选地利用对象跟踪阶段中跟踪的对象进行更新。这能够周期性地进行或者判定在目标模型和所选的目标候选之间存在明显差别时进行。模型也能够利用或者不利用存储器进行更新。

示例性结构

用于实时视频运动理解的整个系统结构的一个例子显示在图13中。系统600包括数据准备装置610，相机运动估计器620，运动对象检测器630，和运动对象跟踪器640。如以上结合图9所示，系统600可以通过适当配置的逻辑和/或适当编程的处理器，或者其它来实现。

数据准备装置610可以包括解码器612，其在需要的时候将输入视频信号进行解码并生成图像序列。下采样器614可以接收该图像序列并生成更低分辨率的图像序列，该更低分辨率的图像序列可以通过合适的延迟装置652被提供给对象跟踪器640。数据准备装置可以进一步包括装置616，其从下采样的图像序列中提取出亮度信息。由于如上所述的原因，解码、下采样和亮度提取不是必需的。

相机运动估计器620可以包括光流分析器622，其使用(来自数据准备装置610或者其他来源)亮度图像用于光流分析。分析器622优选地包括合适的存储缓冲器，使得能够如上所述在当前图像和图像序列中缓存的先前的图像上完成分析。并且，分析器622有利地在差分图像上进行操作，这些图像能够通过减法器654和合适的延迟656从连续图像对儿中生成。分析器622从图像序列或者差分图像序列中生成运动向量，并且运动向量被提供给仿射模型估计器624。如上所述，优选使用LSE基于运动向量估计仿射模型。估计出的仿射模型可以随后被提供给语义含义解析器626，如果需要，如上所述基于仿射模型估计的组合生成句子和(可选地)段落。

仿射模型估计被提供给在对象检测器630中的残差计算器632，其接收由延迟装置656进行合理延迟的图像。能够通过开关或者其他合适的决策装置658来控制对象是否被检测到。局外的残差使用仿射模型估计而被确定，并且如上所述，选择局外用于检测运动对象。被选中的像素和块由滤波器634进行处理，其如上述的滤波器106一般操作以定位对象的区域。该信息被传送给对象定位器636，其有利地将对象的位置和大小作为边界框或者等价的信息来传递。标识对象的位置和大小的边界框或者等价的信息被提供给对象跟踪器640。

跟踪器640包括目标模型和概率计算器642和系数最大化器644，其确定目标模型和目标候选PDFs，并且如上所述最大化Bhattacharyya系数来使得距离最小化。最后，输出对跟踪的运动对象的指示，完成对当前帧的处理。跟踪的运动对象指示的特征可以有利地为对象边界区域的位置(例如，如图10B中的边界框的左边，顶部，右边和底部)。

系统600已利用具有1.0GHz处理器和256M字节随机访问存储器的膝上型电脑来实现。在系统的一个示例性用途中，输入视频信号是10秒长的视频序列，每秒30帧，每帧包括352×240像素，依照MPEG-1格式进行编码。视频帧被下采样为1/4大小，也就是176×120。相应地，系统600包括MPEG-1解码器612，其使用2.016秒来对10秒长的输入序列进行解码，该序列是在网球比赛中一个选手的镜头。所有的相机运动估计在1.089秒中完成，在整个序列中的对象检测和跟踪在1.151秒中完成。因此，在此例子中，用于视频运动分析的总共的时间或者代价(2.24秒)可比于解码代价(2.016秒)，并且所有的处理，包括解码、相机运动分析和对象运动分析(检测和跟踪)，以较实时(10秒)更快的速度完成。如上所述，使用图像序列代替编码的视频剪辑可以节省解码代价，并且，能够在此例子中将整体处理速度提速1倍。而且，如果图像序列被以Y-U-V的格式提供，彩色空间转换的代价也可以被节省。

在如上所述的膝上型电脑实现的系统600的另一个示例性用途中，在圣弗兰西斯科的码头的26秒长的视频被作为输入视频信号。视频被以MJPEG格式进行编码，并且每秒包括15帧，每帧包括640×480像素。如上所述，输入帧被折半下采样直到宽度小于或者等于200像素，并且在此例子中，最终的图像大小为160×120。相应地，系统600包括一个MJPEG解码器612，它需要9.263秒对26秒长的输入序列进行解码。所有的相机运动估计在2.373秒内完成，在整个序列中的对象检测和跟踪在1.323秒内完成。因此，视频运动分析的全部代价(3.696秒)在此例子中相对于解码代价(9.263秒)是相当地小，并且，所有的处理，包括解码、相机运动分析和对象运动分析(检测和跟踪)，以较实时(26秒)更快的速度完成。

从这些例子中，能够看出系统600的用途对于典型的视频类型(包括动作视频，商业视频等)是实用的。当图像大小比较大时，解码和下采样的代价能够在整个计算代价中占主导，但是，如果亮度图像序列被提供作为输入信号时，这个代价能够被省略。

本发明能够用于在视频序列中寻找特定帧，例如用于视频打印。并且，本发明能够被用于自动视频编辑和智能视频浏览，使得能够对视频内容有更好的理解并且对视频中的精彩场面进行更精确的捕获。依照本发明的运动对象检测和跟踪，那些具有合适的大小和位置的运动对象的视频帧能够被检测到，不需要的帧能够被忽略或者消除。

可以理解，如上所述的过程在需要的情况下被重复地执行。为了便于理解，本发明的许多特点以动作序列来进行描述，这些能够由(例如)一个可编程的计算机系统完成。将会认识到的是，不同的动作能够由专用的电路(例如，互连以执行特殊功能的离散逻辑门电路，或者专用集成电路)，由一个或者多个处理器执行的程序指令，或者由这两者的组合完成。

而且，本发明另外可以被考虑为嵌入在任意形式的计算机可读存储介质中，这些介质中存储了由指令执行系统、装置或者设备，诸如基于计算机的系统、包括处理器的系统、或者能够从介质读取指令并且执行指令的其他系统使用的指令集合，或者是与这些设备联合使用的指令集合。如此处使用的那样，“计算机可读介质”可以是包括、存储、通信、传播或者运输由指令执行系统、装置或者设备使用的或它们联合使用的程序的任意一种形式。计算机可读介质可以是例如(但是不限于)电子的，磁性的，光学的，电磁的，红外的，半导体系统，设备、装置或者传播介质。计算机可读介质的更明确的例子(一个非详尽的清单)包括具有一个或多个导线的电气连接，便携式计算机磁盘，随机访问存储器(RAM)，只读存储器(ROM)，可擦写可编程只读存储器(EPROM或者闪存)，和光纤。

因此，本发明可以被实例化为许多不同的形式中，并不只是上述那些，并且所有这些形式被认为在本发明的范围之内。对于本发明的每个不同方面，任何这样的形式可以称为配置用于执行所述动作的逻辑，或者是执行所述动作的逻辑。

应该强调的是，本申请中使用的术语“包括”和“包含”，指定所述的特征、整数、步骤或者元件的存在，并且不排除附加的一个或者多个其他特征、整数、步骤、元件或者这些的组合的存在。

对本发明的示例实施例的前述说明提供了举例说明和描述，但是不是旨在将本发明限制在所公开的准确形式。依照上述教义或者从实践中获得的修改和变种都是可行的。随附的权利要求和它们的等价物对本发明的范围进行定义。