CN106446820B - 动态视频编辑中的背景特征点识别方法及装置 - Google Patents

Abstract

本发明公开一种动态视频编辑中的背景特征点识别方法及装置，能够在高度动态的情景中，准确识别出视频中的背景特征点。所述方法包括：S1、将视频划分为多个重叠的时间窗口，对每个时间窗口内的特征点进行基于运动特征的分类；S2、通过将每个时间窗口内的特征点类视为一个图节点，在相邻时间窗口中具有的相同特征点的数量不小于第一数值的图节点之间加入边构建加权有向图，并通过动态规划算法在图模型找到一条边权重之和最小的全局最优路径，其中，所述加权有向图的边的权重取决于运动轨迹矩阵的秩和相同特征点的数目；S3、根据颜色和空间特征，对非背景点再分类，将与已有背景点运动一致的点添加至背景点集中。

Description

动态视频编辑中的背景特征点识别方法及装置

技术领域

本发明涉及动态视频编辑领域，具体涉及一种动态视频编辑中的背景特征点识别方法及装置。

背景技术

通过视频序列估算相机的移动路径，是许多视频编辑和视频增强应用中的基本任务。例如，手提式摄像机拍摄出的视频经常会有不稳定、不定向的相机移动，让视频的观看体验很差，视频稳像(video stabilization)旨在解决这一问题。为了估算原相机路径而提取稀疏特征点，是当前视频稳像方法中重要的第一步，也是视频快速编辑传播中的重要步骤。例如，若想在移动相机拍摄出的视频背景中插入新物体，一旦估算出可靠的相机路径，用户就可以简单地将物体置于第一帧，然后自动传播到余下的视频序列中。

在之前的研究中，相机路径常常通过提取稀疏特征点来估算，并用来计算相邻帧间的转换关系，例如单应矩阵(homography)。之前的研究有一个普遍的假设，即提取出的特征点主要都位于视频中的静态背景区域中，它们在帧间的位移仅仅源于相机移动。为了提高鲁棒性，RANSAC方法经常用于过滤掉一些异常的特征点，然而这种简单的筛选方法不足以处理包含大量移动物体的动态视频。在这类视频中，背景被严重遮挡，因此特征点反而主要位于移动的物体中。此外，如果物体和相机都剧烈运动，视频中的背景部分将不断改变，这使得背景追踪不可能长时间的实现。由于没有更鲁棒的特征筛选方法，当前的视频编辑应用都不能在此类场景中正确估算出相机路径。

发明内容

针对现有技术存在的不足和缺陷，本发明提供一种动态视频编辑中的背景特征点识别方法及装置。

一方面，本发明实施例提出一种动态视频编辑中的背景特征点识别方法，包括：

S1、将视频划分为多个重叠的时间窗口，对每个时间窗口内的特征点进行基于运动特征的分类；

S2、通过将每个时间窗口内的特征点类视为一个图节点，在相邻时间窗口中具有的相同特征点的数量不小于第一数值的图节点之间加入边构建加权有向图，并通过动态规划算法在图模型找到一条边权重之和最小的全局最优路径，其中，所述加权有向图的边的权重取决于运动轨迹矩阵的秩和相同特征点的数目；

S3、根据颜色和空间特征，对非背景点再分类，将与已有背景点运动一致的点添加至背景点集中。

另一方面，本发明实施例提出一种动态视频编辑中的背景特征点识别装置，包括：

分类单元，用于将视频划分为多个重叠的时间窗口，对每个时间窗口内的特征点进行基于运动特征的分类；

寻找单元，用于通过将每个时间窗口内的特征点类视为一个图节点，在相邻时间窗口中具有的相同特征点的数量不小于第一数值的图节点之间加入边构建加权有向图，并通过动态规划算法在图模型找到一条边权重之和最小的全局最优路径，其中，所述加权有向图的边的权重取决于运动轨迹矩阵的秩和相同特征点的数目；

添加单元，用于根据颜色和空间特征，对非背景点再分类，将与已有背景点运动一致的点添加至背景点集中。

传统的背景提取和运动分析方法提出了许多理想化的假设，如相机静止，长时间大量特征点可被追踪，移动物体很少且很小等。与传统方法不同的是，本发明基于真实场景提出了两点平凡假设：一、背景在视频中始终有部分可见；二、在短时间内，一些背景特征点可以被提取并追踪。本发明基于计算机视觉领域的一个著名理论，即不同移动状态的特征点可以视作位于不同的线性子空间，主要分为两个阶段：局部运动分析和全局最优化，最后还会有背景标注的细化。根据前述假设，在利用已有的视频特征点提取与跟踪方法得到的特征点序列上，本发明经过三个阶段完成特征点中属于背景特征点的识别过程：在局部运动分析阶段，将长动态视频划分为相互重叠的多个时间窗口，在每个窗口内进行局部运动分析，对局部窗口中包含的特征点进行分类：在全局最优化阶段，每一个划分的窗口中的特征点子类别被视作一个图节点，然后通过时空图优化得到包含有贯穿整段视频的背景特征点序列，该序列具有所包含的特征点内在运动复杂度最低的特点；在背景标注的细化阶段，对剩余特征点再分类，将与已有背景点运动一致的点添加至背景点集中，以解决因背景特征点可能存在不同的运动，导致被分开到不同类别中，将只有部分背景特征点被正确标注的问题。作为一种先进的特征筛选工具，本发明可以直接更鲁棒地估算相机路径，并大大提高现有视频编辑方法在复杂场景中的性能，可以应用于许多重要任务中，例如视频去抖动(stabilization)、背景重构(background reconstruction)和视频物体合成(videoobject composition)。

附图说明

图1为本发明动态视频编辑中的背景特征点识别方法一实施例的流程示意图；

图2为本发明动态视频编辑中的背景特征点识别方法另一实施例的部分流程示意图；

图3为本发明动态视频编辑中的背景特征点识别装置一实施例的结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

参看图1，本实施例公开一种动态视频编辑中的背景特征点识别方法，包括：

S1、将视频划分为多个重叠的时间窗口，对每个时间窗口内的特征点进行基于运动特征的分类；

本方法发明关注于找到特征点中的背景部分，任何可靠的特征点检测和跟踪算法都可以用于初始化，比如可以选用较为成熟的KLT方法作为特征点提取与跟踪的基本方法。从而得到了每个特征点在每一帧对应的二维坐标。对于长动态视频，特征点经常消失，并且不断有新的特征点出现。在没有出现的帧的对应位置，可以设定特殊值，如-1，来表示其无效性。

在特征点追踪之后，视频被切分为K个重叠的时间窗口(如图2所示)，每个时长W帧，重叠帧数为W/2。对于帧率为30的视频，W固定取值可以为40。对于在第k个窗口中出现时长超过0.5W帧的特征点，将其添加到特征点集中，特征点集中的点将参与之后的运动分析。由于过短的特征点可靠性不足，这样就能将它们排除掉。

如图2所示，在时间窗口切分后，需要对每个时间窗口内的特征点进行分类，得到特征点类。对于将特征点基于运动特征进行分类，可以采用现有的方法，此处不再赘述。

S2、通过将每个时间窗口内的特征点类视为一个图节点，在相邻时间窗口中具有的相同特征点的数量不小于第一数值的图节点之间加入边构建加权有向图，并通过动态规划算法在图模型找到一条边权重之和最小的全局最优路径，其中，所述加权有向图的边的权重取决于运动轨迹矩阵的秩和相同特征点的数目；

对于第k个窗口，局部运动分析得到了个特征点类。运动的摄像机拍摄出的动态视频中，背景点轨迹矩阵的秩将小于其他的前景特征点，基于两点原因：(1)背景运动可近似为单应变换，它比典型的前景物体运动简单；(2)背景运动仅仅由摄像机运动造成，而前景运动包含相机运动和物体运动两部分。本方法通过检测每个图节点的运动轨迹矩阵的秩，来分析局部运动的复杂性。为了识别其中的背景部分，如图2所示，在得到特征点类后，本方法对整个视频构建了一个加权有向图。将每个窗口中的特征点定义为节点，每个节点代表一个特征点类。若相邻窗口的两个类中具有的相同特征点的数量不小于第一数值，则在两个对应节点间添加箭头。从第k个时间窗口的图节点i指向第k+1个时间窗口的图节点j的边的权重的计算公式可以为

其中，α为常数，一般取值为0.5或1，为图节点i和图节点j中相同特征点的数量，为图节点i和图节点j中相同特征点构成的运动轨迹矩阵的秩。需要说明的是，所述运动轨迹矩阵Γ为

其中，x_tm为第m帧图像上第t个特征点的坐标(如果第t个特征点在第m帧图像上未出现，则取值-1)，p为视频总帧数，

对于运动轨迹矩阵Γ的秩的计算，可以通过对运动轨迹矩阵Γ进行SVD分解，统计得到的对角矩阵的对角线上非零元素的数量得到。

边的权重越大，内在的运动就越复杂。上述权重的计算公式包含相同特征点数目的指数项，这意味着，若矩阵秩相同，则相同特征点越多，权重越小。

有向图被构建之后，目标是找到一条基于背景衡量标准的连续最优路径。为了找到一条边权重之和最小的最优路径，本方法采用动态规划算法，枚举从头到尾的所有不同组合，找到最优路径(如图2中间的路径所示)，该路径上的所有节点将被标注为背景。每个节点所包含的特征点序列，将作为该时间窗口中的背景点序列。这样就找到了整个长视频中所有时间窗口的背景点。

S3、根据颜色和空间特征，对非背景点再分类，将与已有背景点运动一致的点添加至背景点集中。

上述最优化过程后，每个时间窗口内将有一类特征点被标注为背景。然而，虽然背景特征点遵从相同的单应变换，但还是可能存在不同的运动，从而被分开到不同类别中。这种情况下，将只有部分背景特征点被正确标注。下面将介绍一种背景标注细化的方法来解决这一问题。

在每个时间窗口中，首先排除已被标注为背景的特征点，然后根据颜色和空间信息将剩余特征点再分类。对于颜色特征，使用特征点周围的平均Luv颜色值。对于空间特征，使用从初始帧到终止帧里该特征点在所有帧上归一化后的空间位置求平均得到。特征点的分类方法采用manifold mean shift cluster。可以看到，再分类方法和之前仅使用运动信息的分类法不同。

接着，检测每个特征点类的运动和背景特征点是否一致。通过背景特征点集估算出单应矩阵，根据单应矩阵再计算出该窗口中的平均映射误差。然后计算每一个特征点类的平均误差，若误差小于平均映射误差，便将该类中的特征点添加至该特征点集中。该过程循环进行，直到没有任何特征点可以被添加到该特征点集中。

本发明提供的动态视频编辑中的背景特征点识别方法，基于计算机视觉领域的一个著名理论，即不同移动状态的特征点可以视作位于不同的线性子空间，主要分为两个阶段：局部运动分析和全局最优化，最后还会有背景标注的细化。根据前述假设，在利用已有的视频特征点提取与跟踪方法得到的特征点序列上，本发明经过三个阶段完成特征点中属于背景特征点的识别过程：在局部运动分析阶段，将长动态视频划分为相互重叠的多个时间窗口，在每个窗口内进行局部运动分析，对局部窗口中包含的特征点进行分类：在全局最优化阶段，每一个划分的窗口中的特征点子类别被视作一个图节点，然后通过时空图优化得到包含有贯穿整段视频的背景特征点序列，该序列具有所包含的特征点内在运动复杂度最低的特点；在背景标注的细化阶段，对剩余特征点再分类，将与已有背景点运动一致的点添加至背景点集中，以解决因背景特征点可能存在不同的运动，导致被分开到不同类别中，将只有部分背景特征点被正确标注的问题。

参看图3，本实施例公开一种动态视频编辑中的背景特征点识别装置，包括：

分类单元1，用于将视频划分为多个重叠的时间窗口，对每个时间窗口内的特征点进行基于运动特征的分类；

寻找单元2，用于通过将每个时间窗口内的特征点类视为一个图节点，在相邻时间窗口中具有的相同特征点的数量不小于第一数值的图节点之间加入边构建加权有向图，并通过动态规划算法在图模型找到一条边权重之和最小的全局最优路径，其中，所述加权有向图的边的权重取决于运动轨迹矩阵的秩和相同特征点的数目；

在具体应用中，从第k个时间窗口的图节点i指向第k+1个时间窗口的图节点j的边的权重的计算公式为

其中，α为常数，为图节点i和图节点j中相同特征点的数量，为图节点i和图节点j中相同特征点构成的运动轨迹矩阵的秩。

添加单元3，用于根据颜色和空间特征，对非背景点再分类，将与已有背景点运动一致的点添加至背景点集中。

本实施例中，所述添加单元3，具体可以用于：

对于每个时间窗口，排除该时间窗口中存在于所述全局最优路径中的特征点，并根据颜色特征和空间特征采用manifold mean shift cluster方法将剩余特征点再分类，其中，所述颜色特征使用该时间窗口被排除的特征点周围邻域的平均Luv颜色值，所述空间特征，使用该时间窗口从初始帧到终止帧里该被排除的特征点在所有帧上归一化后的空间位置求平均得到；

对于每个时间窗口，根据该时间窗口被排除的特征点集估算出单应矩阵，再根据所述单应矩阵计算出该时间窗口中的平均映射误差，然后对于该时间窗口剩余每一个特征点类，计算该特征点类的平均误差，若判断获知该平均误差小于所述平均映射误差，则将该类中的特征点添加至该被排除的特征点集中。

本发明提供的动态视频编辑中的背景特征点识别装置，基于计算机视觉领域的一个著名理论，即不同移动状态的特征点可以视作位于不同的线性子空间，主要分为两个阶段：局部运动分析和全局最优化，最后还会有背景标注的细化。根据前述假设，在利用已有的视频特征点提取与跟踪方法得到的特征点序列上，本发明经过三个阶段完成特征点中属于背景特征点的识别过程：在局部运动分析阶段，将长动态视频划分为相互重叠的多个时间窗口，在每个窗口内进行局部运动分析，对局部窗口中包含的特征点进行分类：在全局最优化阶段，每一个划分的窗口中的特征点子类别被视作一个图节点，然后通过时空图优化得到包含有贯穿整段视频的背景特征点序列，该序列具有所包含的特征点内在运动复杂度最低的特点；在背景标注的细化阶段，对剩余特征点再分类，将与已有背景点运动一致的点添加至背景点集中，以解决因背景特征点可能存在不同的运动，导致被分开到不同类别中，将只有部分背景特征点被正确标注的问题。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。术语“上”、“下”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

本发明的说明书中，说明了大量具体细节。然而能够理解的是，本发明的实施例可以在没有这些具体细节的情况下实践。在一些实例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。类似地，应当理解，为了精简本发明公开并帮助理解各个发明方面中的一个或多个，在上面对本发明的示例性实施例的描述中，本发明的各个特征有时被一起分组到单个实施例、图、或者对其的描述中。然而，并不应将该公开的方法解释呈反映如下意图：即所要求保护的本发明要求比在每个权利要求中所明确记载的特征更多的特征。更确切地说，如权利要求书所反映的那样，发明方面在于少于前面公开的单个实施例的所有特征。因此，遵循具体实施方式的权利要求书由此明确地并入该具体实施方式，其中每个权利要求本身都作为本发明的单独实施例。需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。本发明并不局限于任何单一的方面，也不局限于任何单一的实施例，也不局限于这些方面和/或实施例的任意组合和/或置换。而且，可以单独使用本发明的每个方面和/或实施例或者与一个或更多其他方面和/或其实施例结合使用。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围，其均应涵盖在本发明的权利要求和说明书的范围当中。

Claims (10)

1.一种动态视频编辑中的背景特征点识别方法，其特征在于，包括：

S1、将视频划分为多个重叠的时间窗口，对每个时间窗口内的特征点进行基于运动特征的分类；

S2、通过将每个时间窗口内的特征点类视为一个图节点，在相邻时间窗口中具有的相同特征点的数量不小于第一数值的图节点之间加入边构建加权有向图，并通过动态规划算法在图模型找到一条边权重之和最小的全局最优路径，其中，所述加权有向图的边的权重取决于运动轨迹矩阵的秩和相同特征点的数目；

S3、根据颜色和空间特征，对非背景点再分类，将与已有背景点运动一致的点添加至背景点集中。

2.根据权利要求1所述的方法，其特征在于，在所述对每个时间窗口内的特征点进行基于运动特征的分类之前，还包括：

采用KLT方法提取所述视频中的特征点；

对于每一个时间窗口，将该时间窗口中出现时长超过0.5W帧的特征点添加到该时间窗口的特征点集中，其中，每个时间窗口时长W帧，重叠帧数为W/2。

3.根据权利要求2所述的方法，其特征在于，所述第一数值为10个。

4.根据权利要求2所述的方法，其特征在于，从第k个时间窗口的图节点i指向第k+1个时间窗口的图节点j的边的权重的计算公式为

其中，α为常数，为图节点i和图节点j中相同特征点的数量，为图节点i和图节点j中相同特征点构成的运动轨迹矩阵的秩。

5.根据权利要求1所述的方法，其特征在于，所述根据颜色和空间特征，对非背景点再分类，包括：

对于每个时间窗口，排除该时间窗口中存在于所述全局最优路径中的特征点，并根据颜色特征和空间特征采用manifold mean shift cluster方法将剩余特征点再分类，其中，所述颜色特征使用该时间窗口被排除的特征点周围邻域的平均Luv颜色值，所述空间特征，使用该时间窗口从初始帧到终止帧里该被排除的特征点在所有帧上归一化后的空间位置求平均得到。

6.根据权利要求1所述的方法，其特征在于，所述将与已有背景点运动一致的点添加至背景点集中，包括：

对于每个时间窗口，根据该时间窗口被排除的特征点集估算出单应矩阵，再根据所述单应矩阵计算出该时间窗口中的平均映射误差，然后对于该时间窗口剩余每一个特征点类，计算该特征点类的平均误差，若判断获知该平均误差小于所述平均映射误差，则将该类中的特征点添加至该被排除的特征点集中。

7.一种动态视频编辑中的背景特征点识别装置，其特征在于，包括：

分类单元，用于将视频划分为多个重叠的时间窗口，对每个时间窗口内的特征点进行基于运动特征的分类；

寻找单元，用于通过将每个时间窗口内的特征点类视为一个图节点，在相邻时间窗口中具有的相同特征点的数量不小于第一数值的图节点之间加入边构建加权有向图，并通过动态规划算法在图模型找到一条边权重之和最小的全局最优路径，其中，所述加权有向图的边的权重取决于运动轨迹矩阵的秩和相同特征点的数目；

添加单元，用于根据颜色和空间特征，对非背景点再分类，将与已有背景点运动一致的点添加至背景点集中。

8.根据权利要求7所述的装置，其特征在于，从第k个时间窗口的图节点i指向第k+1个时间窗口的图节点j的边的权重的计算公式为

其中，α为常数，为图节点i和图节点j中相同特征点的数量，为图节点i和图节点j中相同特征点构成的运动轨迹矩阵的秩。

9.根据权利要求7所述的装置，其特征在于，所述添加单元，用于：

对于每个时间窗口，排除该时间窗口中存在于所述全局最优路径中的特征点，并根据颜色特征和空间特征采用manifold mean shift cluster方法将剩余特征点再分类，其中，所述颜色特征使用该时间窗口被排除的特征点周围邻域的平均Luv颜色值，所述空间特征，使用该时间窗口从初始帧到终止帧里该被排除的特征点在所有帧上归一化后的空间位置求平均得到。

10.根据权利要求7所述的装置，其特征在于，所述添加单元，用于：

对于每个时间窗口，根据该时间窗口被排除的特征点集估算出单应矩阵，再根据所述单应矩阵计算出该时间窗口中的平均映射误差，然后对于该时间窗口剩余每一个特征点类，计算该特征点类的平均误差，若判断获知该平均误差小于所述平均映射误差，则将该类中的特征点添加至该被排除的特征点集中。