CN104469547B - 一种基于树状运动目标轨迹的视频摘要生成方法 - Google Patents

Abstract

本发明公开了一种基于树状运动目标轨迹的视频摘要生成方法，按照以下步骤实施：步骤1、通过高斯背景建模方法检测并跟踪运动目标，获得运动目标运动轨迹的盒子；步骤2、将运动目标轨迹盒子按照其粘连与否进行聚类，构建目标树；步骤3、对目标树进行描述；步骤4、将目标树按照由大到小的降序进行排序；步骤5、初始化构建生成视频摘要的空容器；步骤6、在容器中排入第一个目标树；步骤7、确定后续的目标树排入容器的起始点位置；步骤8、排入目标树；步骤9、判断是否目标树全部排完；步骤10、输入排入全部目标树的容器为生成的视频摘要。本发明的方法，可保持运动目标在视频摘要中的连续性，视频摘要的浓缩效率高。

Description

一种基于树状运动目标轨迹的视频摘要生成方法

技术领域

本发明属于图像识别技术领域，涉及一种基于树状运动目标轨迹的视频摘要生成方法。

背景技术

视频摘要技术有效的将海量视频数据中的冗余剔除并将剩余的有效信息浓缩起来供人们快速浏览。通过观看视频摘要，人们就可以既不必浏览原始的海量视频数据又能了解海量视频的大致内容。因为视频摘要用于对监控视频中所发生的事件进行快速浏览，同时也需要对浏览时发现的关注事件进行定位回放，所以，视频摘要一般的做法均是将原始视频中的运动目标进行检测跟踪后，将每个运动目标作为一个事件链来生成视频摘要。这种做法存在致命的问题是，视频摘要效果的好坏，取决于原始视频中，运动目标的检测及跟踪效果的好坏。然而，运动目标的检测跟踪算法的准确性，极大程度地受限于视频监控环境是否复杂，运动目标是否密集等因素。为此，也限制了视频摘要的应用推广。

发明内容

本发明的目的是提供一种基于树状运动目标轨迹的视频摘要生成方法，不再要求每个运动目标都能够进行完整的检测与跟踪，而是允许几个发生粘连、交叉、遮挡等多个目标，以目标树的形式进行描述，解决了现有技术因运动目标检测跟踪受限于运动目标密集程度，以及监控环境复杂程度而导致的视频摘要生成受限的问题。

本发明所采用的技术方案是，一种基于树状运动目标轨迹的视频摘要生成方法，按照以下步骤实施：

步骤1、从监控视频中提取运动目标，获得运动目标运动轨迹的盒子

采用混合高斯背景建模方法提取出监控视频中的运动目标，之后，按照相邻帧间重叠面积最大为同一目标的方法进行运动目标跟踪，在每一帧中，跟踪得到的每个运动目标区域用其最小的外接矩形来表示，

每个运动目标的最小外接矩形在一帧图像中，是一个外接矩形，称这个外接矩形所框定的，在本帧图像中的区域为一个团块；这些团块在时间轴上叠加起来，就形成了一个盒子，盒子的起点为发现某个运动目标的帧，终点是运动目标消失在监控视域的前一帧，

假设，对每一个出现在视频监控视域中的运动目标，均采用一个盒子来描述的话，则每个运动目标的描述如式(1)所示：

其中，O_k()表示第k个运动目标，k＝1,2,...,N_s，m_k＝1,2,...,N_k，N_S为检测出的运动目标的总数，N_k表示第k个目标持续的帧数；

表示第k个目标在第m_k帧中外接矩形左上角的坐标，

表示第k个目标在第m_k帧中外接矩形右下角的坐标，

表示第k个目标在第m_k帧中的质心坐标，

本步骤中，在运动目标提取过程中将类似的情况以树状结构的形式进行描述，将其标识为同一个标识，即树状结构给出了一个连续的运动轨迹，不再要求只包括一个运动目标；

步骤2、运动目标盒子聚类

对所检测到的运动目标k＝1,2,...,N_s，m_k＝1,2,...,N_k，判断其目标之间在运动过程中是否存在粘连，将存在粘连的目标盒子全部归为同一类，即称之为归属同一个目标树，并且在每一帧中，每一个运动目标由其最小外接矩形所框定的区域被称为树的一个团块，如果在一帧中存在多个运动目标时，则该帧中存在多个团块；

步骤3、对目标树进行描述；

步骤4、对步骤3聚类得到的N个目标树进行排序

对这N个目标树按照长度由大到小的降序进行排列，为了表示方便，还是设这N个排序后的目标树为Tree_id，id＝1,2,...,N；

步骤5、设计摘要生成容器并对其初始化；

步骤6、排入第一个目标树至容器中；

步骤7、确定目标树排入容器的位置；

步骤8、将确定位置的待排目标树排入容器中；

步骤9、判断是否还存在有需要排入容器里的目标树

如果没有，即id＝N+1则排序完毕退出，转步骤10，

否则，取下一个目标树Tree_id，进入步骤7；

步骤10、将容器的元素值取整，则为生成的视频摘要，即成。

本发明的有益效果是，该方法预先将视频中的运动目标轨迹数据提取出来，然后对这些轨迹重新进行时间轴上的规划，在运动目标轨迹碰撞程度在可接受的情况下尽量压缩视频摘要的总长度，最后将这些运动目标按照已经规划好的新路径重新生成一段摘要视频，具体是：

首先，不丢失运动目标信息，最大限度上保留所有可能的有用信息。其次，通过对运动目标轨迹的重新规划，能够大幅的将时间轴上无运动目标的冗余段去掉，使视频摘要尽可能的短，摘要视频浏览起来自然、流畅，就为人们快速浏览提供了最大的便利。最后，生成的摘要依然是正常的视频播放速度与方式，视觉效果也完全保留了原始视频的视觉效果。

附图说明

图1是本发明方法将一个运动目标外接矩形在时间轴上叠加得到的盒子示意图；

图2是本发明方法视频摘要的运动目标轨迹关系示意图；

图3是本发明方法视频摘要的轨迹融合关系示意图；

图4是本发明方法中的运动目标粘连分离轨迹示意图；

图5是本发明方法中的运动目标质心运动关系示意图；

图6是本发明方法中的树状结构的运动目标模型示意图；

图7是本发明方法中的容器中排进目标树的碰撞关系示意图；

图8是本发明方法中的团块碰撞关系示意图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

本发明的基于树状运动目标轨迹的视频摘要生成方法属于动态视频摘要，即通过从原始监控视频中提取有效信息并将它们融合成一段缩略视频，该缩略视频中包含了监控视域内监控到的运动目标。

本发明的基于树状运动目标轨迹的视频摘要生成方法，按照以下步骤实施：

步骤1、从监控视频中提取运动目标，获得运动目标运动轨迹的盒子

采用混合高斯背景建模方法提取出监控视频中的运动目标，之后，按照相邻帧间重叠面积最大为同一目标的方法进行运动目标跟踪，在每一帧中，跟踪得到的每个运动目标区域用其最小的外接矩形来表示。

(注：该运动目标检测方法以及运动目标的跟踪方法在相关的专业书中，或者相关论文中均有介绍，此处不再重复。)

如图1所示，每个运动目标的最小外接矩形在一帧图像中，是一个外接矩形，称这个外接矩形所框定的，在本帧图像中的区域为一个团块；这些外接团块在时间轴上叠加起来，就形成了一个盒子，盒子的起点为发现某个运动目标的帧，终点是运动目标消失在监控视域的前一帧，

假设，对每一个出现在视频监控视域中的运动目标，均采用一个盒子来描述的话，则每个运动目标的描述如式(1)所示：

其中，O_k()表示第k个运动目标，k＝1,2,...,N_s，m_k＝1,2,...,N_k，N_S为检测出的运动目标的总数，N_k表示第k个目标持续的帧数；

表示第k个目标在第m_k帧中外接矩形左上角的坐标，

表示第k个目标在第m_k帧中外接矩形右下角的坐标，

表示第k个目标在第m_k帧中的质心坐标，(注：质心的计算方法在相关的教材及论文中有提及，这里不再复述。)

如图2和图3所示，是运动目标的轨迹在原始视频，以及经过下面步骤的轨迹融合之后，得到的视频摘要的目标轨迹示意图，该示意图在不妨碍理解的情况下，略去了y轴方向的信息。在图2中，假设有A、B、C、D四个目标，这四个目标相互独立，不存在彼此之间的粘连、遮挡、交叉等情况，因此，消除这四个轨迹间的冗余后，则得到图3的视频摘要就比较容易。

事实上，在实际的监控视频中，运动目标经常会存在遮挡、粘连等情况，这些情况会对运动目标的提取带来影响。例如图4所示，有运动目标1、运动目标2在视场左侧没有粘连，在运动目标跟踪过程中它们得到了正确标识。当该两个目标运动到视场中段时，目标1与目标2粘连到一起，这时它们被识别为运动目标3；当该两个目标运动到视场右段时，两个目标又分开，这时运动目标被标识为目标4、目标5，反映到质心运动上就如图5所示。这样，原始视频中在时间轴上大致处于同时出现过的两个运动目标却被标识为五个运动目标。在后续的运动目标轨迹重新规划过程中会很有可能将它们规划到五个不同的时间段，这就割断了它们本身的连续性，极大的影响最后摘要的视觉效果。

本步骤中，在运动目标提取过程中将类似的情况以树状结构的形式进行描述，将其标识为同一个标识，给出如图6所示的控制结果，换句话说，树状结构给出了一个连续的运动轨迹，不再要求只包括一个运动目标；

步骤2、运动目标盒子聚类

对所检测到的运动目标k＝1,2,...,N_s，m_k＝1,2,...,N_k，判断其目标之间在运动过程中是否存在粘连，如图4和图5所示，将存在粘连的目标盒子全部归为同一类，即称之为归属同一个目标树，并且在每一帧中，每一个运动目标由其最小外接矩形所框定的区域被称为树的一个团块，如果在一帧中存在多个运动目标时，则该帧中存在多个团块；

步骤3、对目标树进行描述

首先，定义目标树唯一标识的参数集Tree_id，该模型如式(2)所示：

其中，id＝1,2,...,N，id是目标树的编号，

N是步骤2得到的目标树的总个数；

是该目标树中的运动目标在原始视频中的起始帧序号，

是其在原始视频中的结束帧序号，

就代表该目标树的长度；

为团块集， 是目标树在第t帧中的团块的个数，即由步骤1检测到的运动目标的个数，是由步骤2得到的归为同一棵目标树的所有运动目标盒子在相应帧中外接矩形所框定的区域构成，

中的每个团块信息描述为：

其中，t＝1,2,...,Δt_id，

是目标树中第t帧的第i_b个团块在原始视频中的帧序号，

是第i_b个团块在原视频中外接矩形的左上角和右下角的坐标，代表了团块在原始视频帧中的区域坐标，

是第i_b个团块的最大外接矩形的长边边长的1/2，

为第i_b个团块区域的像素值；

步骤4、对步骤3聚类得到的N个目标树进行排序

考虑到目标树的长度是影响最终摘要总长度的一个主要因素，因此，首先对这N个目标树按照长度由大到小的降序进行排列，为了表示方便，还是设这N个排序后的目标树为Tree_id，id＝1,2,...,N；

步骤5、设计摘要生成容器并对其初始化

所谓的摘要生成容器，是用来将步骤3生成的全部目标树融合后生成一段视频摘要的三维数组，其中两维表示视频摘要帧图像的大小，与原始视频帧画面大小相同，另外一维表示时间，这样，便构成表达视频是随时间变化的图像帧序列的数据形式，

初始化这个三维数组，称之为构建一个空容器，见式(4)：

其中，c_i,j,l＝0，i＝1,2,...,m，j＝1,2,...,n，l＝1,2,...,Δt_C，数组的大小为m×n×Δt_C，m为视频帧画面的行数，n为视频帧画面的列数，Δt_C为容器的长度，

初始化时，令Δt_C＝Δt_max，Δt_max＝max{Δt_id|id＝1,2,...,N}，即空容器的长度选为最大目标树的长度，经过步骤4排序后，Δt_max＝Δt₁，

令id＝1，将第一个目标树排入容器中，排入的位置为t_start＝1；

步骤6、排入第一个目标树至容器中

要将排在第一的最长目标树Tree₁放入容器中，容器中不为0的元素应该为该目标树的所有团块，则有式(5)：

其中，

之后，令id＝id+1，选出下一个目标树转步骤7确定排入容器的位置；

步骤7、确定目标树排入容器的位置

7.1)求待排目标树与容器中已排目标树的每帧团块碰撞

排进新的目标树时，与已经排在容器中的目标树之间的碰撞检测过程是，如图7中a区域下方的部分是容器中已经排序完毕的目标树，箭头上方的目标树是待排目标树；如图7中b区域所示，在容器的右侧示意的，将待排目标树从容器的最底部开始往上移动，即从容器范围t_start∈[1,Δt_C]内，由t_start＝1开始，计算碰撞，图7中c区域为满足接受程度碰撞状态的目标树排入，

待排目标树与容器中的已排目标树之间在每帧中的团块碰撞过程是，如图8所示，标注“1，2，3”的数字框设为容器内已经排入的目标树在某一帧(设为第t帧)的团块，标注“A、B、C、D”的字母框为待排目标树在这帧的团块，进入时与已排目标树的团块之间的碰撞即为团块在帧图像中的位置两者有部分或者全部相同，即认定产生了碰撞，在图8中，团块D未发生碰撞，团块B、C发生了轻微碰撞，团块A则与数字框2发生了严重的碰撞，轻微碰撞的情况因为其重叠不严重而影响视觉观察效果也轻微，因此被视作允许的碰撞，

设待排目标树在第t_a帧的团块集为已经排在容器中的目标树在第t_a帧的团块集为

假设集中的团块其质心坐标为 集中的团块其质心坐标为

则团块间两两碰撞与否的判断标准如式(6)：

其中，则在第t_a帧中，待排目标树与容器中的已排目标树的碰撞Colli(t_a)与否的判断标准如式(7)：

7.2)求待排目标树与容器中已排目标树的逐帧碰撞

因为待排目标树的长度为Δt_id，因此，在按照步骤7.1)计算每帧的碰撞，容器的已排目标树的位置取为t_start,t_start+1,...,t_start-1+Δt_id，与待排目标树所有帧，即t_a＝1,2,...,Δt_id，逐帧按照步骤7.1)计算得到每帧的团块碰撞Colli(t_a)，t_a＝1,2,...,Δt_id；

7.3)求待排目标树与容器中已排目标树的总体碰撞率

待排目标树起点在t_start位置上与容器中已排目标树的总体碰撞率的计算式如式(8)：

7.4)判断待排目标树可放置的位置

根据式(8)计算得到的碰撞率的取值范围为用户需要根据能够接受的密集程度，以及对视频摘要长度的要求，设置碰撞率阈值ρ_Th，优选经验值为ρ_Th＝1/3，

如果表示待排目标树与容器内的已排目标树不存在碰撞，如果表明碰撞情况属于可接受的程度，这时，将待排目标树排进容器中的t_start的位置上，转步骤8实现将该目标树排入容器中；

如果表明每帧都有碰撞，这时会大大影响视觉效果，如果表明碰撞情况属于不可接受的程度，为此需要改变待排目标树的计算碰撞位置，即令t_start＝t_start+1(即表明待排目标树的位置往后移一帧)，转步骤7.1)再次进行碰撞率的计算，直至找到满足的位置t_start；

步骤8、将确定位置的待排目标树排入容器中

要将该目标树Tree_id按照步骤7确定的起始位置t_start放入容器中，先调整容器的长度，如果t_start+Δt_id＞Δt_C，则有Δt_C＝(Δt_id+t_start)，否则容器长度保持不变，容器里的元素值的计算如式(9)：

其中，

表示求待排目标树的团块像素值与容器中相应位置上的非零值的均值，

排完该目标树之后，令id＝id+1，即表示目标树的序号加1的含义；

步骤9、判断是否还存在有需要排入容器里的目标树

如果没有，即id＝N+1则排序完毕退出，转步骤10，

否则，取下一个目标树Tree_id，进入步骤7；

步骤10、将容器的元素值取整，则为生成的视频摘要，输出，即成。

Claims (6)

1.一种基于树状运动目标轨迹的视频摘要生成方法，其特征在于：按照以下步骤实施：

步骤1、从监控视频中提取运动目标，获得运动目标运动轨迹的盒子

采用混合高斯背景建模方法提取出监控视频中的运动目标，之后，按照相邻帧间重叠面积最大为同一目标的方法进行运动目标跟踪，在每一帧中，跟踪得到的每个运动目标区域用其最小的外接矩形来表示，

每个运动目标的最小外接矩形在一帧图像中，是一个外接矩形，称这个外接矩形所框定的，在本帧图像中的区域为一个团块；这些团块在时间轴上叠加起来，就形成了一个盒子，盒子的起点为发现某个运动目标的帧，终点是运动目标消失在监控视域的前一帧，

假设，对每一个出现在视频监控视域中的运动目标，均采用一个盒子来描述的话，则每个运动目标的描述如式(1)所示：

$O_k({x_L}^{m_k},{y_L}^{m_k};{x_R}^{m_k},{y_R}^{m_k};{x_0}^{m_k},{y_0}^{m_k},N_k),---\left(1\right)$

其中，O_k()表示第k个运动目标，k＝1,2,...,N_s，m_k＝1,2,...,N_k，N_S为检测出的运动目标的总数，N_k表示第k个目标持续的帧数；

表示第k个目标在第m_k帧中外接矩形左上角的坐标，

表示第k个目标在第m_k帧中外接矩形右下角的坐标，

表示第k个目标在第m_k帧中的质心坐标，

本步骤中，在运动目标提取过程中将类似的情况以树状结构的形式进行描述，将其标识为同一个标识，即树状结构给出了一个连续的运动轨迹，不再要求只包括一个运动目标；

步骤2、运动目标盒子聚类

对所检测到的运动目标m_k＝1,2,...,N_k，判断其目标之间在运动过程中是否存在粘连，将存在粘连的目标盒子全部归为同一类，即称之为归属同一个目标树，并且在每一帧中，每一个运动目标由其最小外接矩形所框定的区域被称为树的一个团块，如果在一帧中存在多个运动目标时，则该帧中存在多个团块；

步骤3、对目标树进行描述；

步骤4、对步骤3聚类得到的N个目标树进行排序

对这N个目标树按照长度由大到小的降序进行排列，为了表示方便，还是设这N个排序后的目标树为Tree_id，id＝1,2,...,N；

步骤5、设计摘要生成容器并对其初始化；

步骤6、排入第一个目标树至容器中；

步骤7、确定目标树排入容器的位置；

步骤8、将确定位置的待排目标树排入容器中；

步骤9、判断是否还存在有需要排入容器里的目标树

如果没有，即id＝N+1则排序完毕退出，转步骤10，

否则，取下一个目标树Tree_id，进入步骤7；

步骤10、将容器的元素值取整，则为生成的视频摘要，即成。

2.根据权利要求1所述的基于树状运动目标轨迹的视频摘要生成方法，其特征在于：所述的步骤3中，定义目标树唯一标识的参数集Tree_id，该参数集Tree_id表达式如式(2)所示：

${\mathrm{Tree}}_{id}=(t_{start}^{id},t_{end}^{id},\{{\mathrm{Block}}_t^{id}\},t=1,2,...,{\mathrm{\Δt}}_{id}),---\left(2\right)$

其中，id＝1,2,...,N，id是目标树的编号，

N是步骤2得到的目标树的总个数；

是该目标树中的运动目标在原始视频中的起始帧序号，

是其在原始视频中的结束帧序号，

就代表该目标树的长度；

为团块集， 是目标树在第t帧中的团块的个数，即由步骤1检测到的运动目标的个数，是由步骤2得到的归为同一棵目标树的所有运动目标盒子在相应帧中外接矩形所框定的区域构成，

中的每个团块信息描述为：

${\mathrm{Block}}_t^{i_b}=(s_t^{i_b},{\mathrm{Rect}}_t^{i_b},r_t^{i_b},\{{\mathrm{pixel}}_t^{i_b}\left\}\right),---\left(3\right)$

其中，

是目标树中第t帧的第i_b个团块在原始视频中的帧序号，

是第i_b个团块在原视频中外接矩形的左上角和右下角的坐标，代表了团块在原始视频帧中的区域坐标，

是第i_b个团块的最大外接矩形的长边边长的1/2，

为第i_b个团块区域的像素值。

3.根据权利要求2所述的基于树状运动目标轨迹的视频摘要生成方法，其特征在于：所述的步骤5中，所谓的摘要生成容器，是用来将步骤3生成的全部目标树融合后生成一段视频摘要的三维数组，其中两维表示视频摘要帧图像的大小，与原始视频帧画面大小相同，另外一维表示时间，这样，便构成表达视频是随时间变化的图像帧序列的数据形式，

初始化这个三维数组，称之为构建一个空容器，见式(4)：

$C={\[c_{i,j,l}\]}_{m\×n\×{\mathrm{\Δt}}_C},---\left(4\right)$

其中，c_i,j,l＝0，i＝1,2,...,m，j＝1,2,...,n，l＝1,2,...,Δt_C，数组的大小为m×n×Δt_C，m为视频帧画面的行数，n为视频帧画面的列数，Δt_C为容器的长度，

初始化时，令Δt_C＝Δt_max，Δt_max＝max{Δt_id|id＝1,2,...,N}，即空容器的长度选为最大目标树的长度，经过步骤4排序后，Δt_max＝Δt₁，

令id＝1，将第一个目标树排入容器中，排入的位置为t_start＝1。

4.根据权利要求3所述的基于树状运动目标轨迹的视频摘要生成方法，其特征在于：所述的步骤6中，要将排在第一的最长目标树Tree₁放入容器中，容器中不为0的元素应该为该目标树的所有团块，则有式(5)：

$c_{x,y,l}={\mathrm{pixel}}_l^{i_b},---\left(5\right)$

其中，

之后，令id＝id+1，选出下一个目标树转步骤7确定排入容器的位置。

5.根据权利要求4所述的基于树状运动目标轨迹的视频摘要生成方法，其特征在于：所述的步骤7中，具体包括以下步骤：

7.1)求待排目标树与容器中已排目标树的每帧团块碰撞

排进新的目标树时，与已经排在容器中的目标树之间的碰撞检测过程是，将待排目标树从容器的最底部开始往上移动，即从容器范围t_start∈[1,Δt_C]内，由t_start＝1开始，计算碰撞，即为满足接受程度碰撞状态的目标树排入，

待排目标树与容器中的已排目标树之间在每帧中的团块碰撞过程是，进入时与已排目标树的团块之间的碰撞即为团块在帧图像中的位置两者有部分或者全部相同，即认定产生了碰撞，轻微碰撞的情况因为其重叠不严重而影响视觉观察效果也轻微，因此被视作允许的碰撞，

设待排目标树在第t_a帧的团块集为已经排在容器中的目标树在第t_a帧的团块集为

假设集中的团块其质心坐标为集中的团块其质心坐标为

则团块间两两碰撞与否的判断标准如式(6)：

${\mathrm{Col}}_t(i_a,j_a)=\left\{\begin{array}{ccc}1& if& (\sqrt{{(x_0^{i_a}-x_0^{j_a})}^2+{(y_0^{i_a}-y_0^{j_a})}^2}\≤|r_t^{i_a}-r_t^{j_a}\left|\right)\\ 0& if& (\sqrt{{(x_0^{i_a}-x_0^{j_a})}^2+{(y_0^{i_a}-y_0^{j_a})}^2}>|r_t^{i_a}-r_t^{j_a}\left|\right)\end{array}\right.,---\left(6\right)$

其中，则在第t_a帧中，待排目标树与容器中的已排目标树的碰撞Colli(t_a)与否的判断标准如式(7)：

$Colli\left(t_a\right)=\left\{\begin{array}{ccc}1& if& \underset{k_s=1}{\overset{n_{t_a}^{id}}{\Σ}}\underset{i_s=1}{\overset{n_{t_a}^C}{\Σ}}{\mathrm{Col}}_{t_a}(i_a,j_a)\≥0\\ 0& if& \underset{k_s=1}{\overset{n_{t_a}^{id}}{\Σ}}\underset{i_s=1}{\overset{n_{t_a}^C}{\Σ}}{\mathrm{Col}}_{t_a}(i_a,j_a)=0\end{array}\right.;---\left(7\right)$

7.2)求待排目标树与容器中已排目标树的逐帧碰撞

因为待排目标树的长度为Δt_id，因此，在按照步骤7.1)计算每帧的碰撞，容器的已排目标树的位置取为t_start,t_start+1,...,t_start-1+Δt_id，与待排目标树所有帧，即t_a＝1,2,...,Δt_id，逐帧按照步骤7.1)计算得到每帧的团块碰撞Colli(t_a)，t_a＝1,2,...,Δt_id；

7.3)求待排目标树与容器中已排目标树的总体碰撞率

待排目标树起点在t_start位置上与容器中已排目标树的总体碰撞率的计算式如式(8)：

${\mathrm{\ρ}}_C^{t_{start}}=\frac{\underset{t_a=1}{\overset{{\mathrm{\Δt}}_{id}}{\Σ}}Colli\left(t_a\right)}{{\mathrm{\Δt}}_{id}};---\left(8\right)$

7.4)判断待排目标树可放置的位置

根据式(8)计算得到的碰撞率的取值范围为

用户需要根据能够接受的密集程度，以及对视频摘要长度的要求，设置碰撞率阈值ρ_Th，

如果表示待排目标树与容器内的已排目标树不存在碰撞，如果表明碰撞情况属于可接受的程度，这时，将待排目标树排进容器中的t_start的位置上，转步骤8实现将该目标树排入容器中；

如果表明每帧都有碰撞，这时会大大影响视觉效果，如果表明碰撞情况属于不可接受的程度，为此需要改变待排目标树的计算碰撞位置，即令t_start＝t_start+1，即表明待排目标树的位置往后移一帧，转步骤7.1)再次进行碰撞率的计算，直至找到满足的位置t_start。

6.根据权利要求5所述的基于树状运动目标轨迹的视频摘要生成方法，其特征在于：所述的步骤8中，要将该目标树Tree_id按照步骤7确定的起始位置t_start放入容器中，先调整容器的长度，如果t_start+Δt_id＞Δt_C，则有Δt_C＝(Δt_id+t_start)，否则容器长度保持不变，容器里的元素值的计算如式(9)：

$c_{x_a,y_a,t_a}=\left\{\begin{array}{ccc}{\mathrm{pixel}}_{t_a}^{i_a}& if& c_{x_a,y_a,t_a}=0\\ (c_{x_a,y_a,t_a}+{\mathrm{pixel}}_{t_a}^{i_a})/2& if& c_{x_a,y_a,t_a}\·{\mathrm{pixel}}_{t_a}^{i_a}\≠0\end{array}\right.,---\left(9\right)$

其中，

表示求待排目标树的团块像素值与容器中相应位置上的非零值的均值，

排完该目标树之后，令id＝id+1，即表示目标树的序号加1的含义。