CN113868465B - 一种基于二维时间格网的可定位视频检索方法 - Google Patents

Abstract

本发明提供一种基于二维时间格网的可定位视频检索方法。该方法包括：根据所有可定位视频片段中的最早开始时间T_s、最晚结束时间T_e以及时间分辨率，结合每个可定位视频片段的开始时间与结束时间，计算每个可定位视频片段的行列号信息，得到二维时间格网；根据每个可定位视频片段在二维时间格网中的行列号信息，为每个可定位视频片段生成其对应的空间点，最终得到空间点集P；利用R树空间索引方法生成空间点集P对应的R树空间索引结构；根据可定位视频检索条件定义的开始时间和结束时间定位到二维时间格网中的对应时间栅格，根据该时间栅格的行列号信息生成对应的空间点，在R树空间索引结构中查找得到该空间点，即得到该空间点对应的可定位视频。

Description

一种基于二维时间格网的可定位视频检索方法

技术领域

本发明涉及地理信息和视频检索技术领域，尤其涉及一种基于二维时间格网的可定位视频检索方法，可用于海量可定位视频数据管理及分析领域。

背景技术

当前，公共安全成为各级政府关注的焦点问题之一；建设针对公共空间的视频监控系统，成为保障公共安全、威慑犯罪行为的关键环节。随着我国平安城市的不断推进，全国各地均积累了海量的视频数据；这些视频均为包含拍摄时段与空间位置的可定位视频。如何高效检索相应时间的可定位视频数据，成为大规模监控视频管理与分析的基础性问题。可定位视频是包含时空信息的视频，目前其检索方式主要包括下述三种：基于空间位置的检索、基于时间信息的检索以及基于语义标签的检索。基于空间位置的检索主要依据视频拍摄位置或视频场景位置，应用空间关系谓词进行判断；基于时间信息的检索主要依据视频拍摄时刻或时段进行检索；基于语义标签的检索主要是结合视频内容进行标注，定义相应标签文本进行视频检索。其中，目前基于时间信息的检索存在以下问题：(1)主要采用时间戳进行直接比较，由于时间戳数据类型的复杂性导致检索效率低下；(2)主要采用一维时间线方式，应用绝对时间进行判断，未能充分利用二维空间语义进行可定位视频的时间信息检索；(3) 检索方式单一，缺少图形化的基于时间的视频检索操作方法。

发明内容

为了解决上述的目前基于时间信息的可定位视频检索方法所存在的至少部分问题，本发明主要针对基于时间信息的可定位视频检索进行改进，提供了一种基于二维时间格网的可定位视频检索方法，通过定义二维时间格网能够实现可定位视频高效查询与检索。

本发明提供的一种基于二维时间格网的可定位视频检索方法，包括：

步骤1：根据所有可定位视频片段中的最早开始时间Ts、最晚结束时间Te以及时间分辨率，结合每个可定位视频片段的开始时间与结束时间，计算每个可定位视频片段的行列号信息，从而将一维连续的时间区间信息按照相应的时间分辨率映射到二维栅格空间得到二维时间格网；

步骤2：根据每个可定位视频片段在二维时间格网中的行列号信息，为每个可定位视频片段生成其对应的空间点，最终所有可定位视频片段的空间点构成空间点集P；

步骤3：利用R树空间索引方法生成空间点集P对应的R树空间索引结构；

步骤4：根据可定位视频检索条件定义的开始时间和结束时间定位到二维时间格网中的对应时间栅格，根据该时间栅格的行列号信息生成对应的空间点，在已生成的R树空间索引结构中查找得到该空间点，即得到该空间点对应的可定位视频。

进一步地，步骤1中，所述计算每个可定位视频片段的行列号信息，具体包括：

步骤A1：利用公式(1)计算第k个可定位视频片段在时间分辨率ct下的原始列号信息u与行号信息v：

其中，

和

分别表示第k个可定位视频片段的开始时间和结束时间，T_s分别表示所有可定位视频片段中的最早开始时间，

k＝1,2,3…,K,K表示可定位视频片段的总个数；

步骤A2：将原始行列号信息表示为矢量形式(u,v,1)，然后按照预设规则计算得到可定位视频片段在二维时间格网中的新列号信息j和新行号信息i；

其中，所述预设规则具体为：

当1≤u<(N+1)/2,1<v≤(N+1)/2时，则j＝u,i＝v；

当u>v+(N+1)/2,1≤u≤(N+1)/2,(N+1)/2<v≤N时，利用公式 (2)将矢量(u,v,1)转换为(j,i,1)：

当(N+1)/2<v≤u+(N+1)/2≤N,1≤u≤(N+1)/2时，利用公式(3) 将矢量(u,v,1)转换为(j,i,1)：

当(N+1)/2<u≤N,(N+1)/2≤v≤N时，利用公式(4)将矢量(u,v,1) 转换为(j,i,1)：

其中，N表示二维时间格网的列，N＝(T_e-T_s-c_t)/ct，T_e分别表示所有视频片段中的最晚结束时间，

进一步地，步骤2中，所述为每个可定位视频片段生成其对应的空间点具体包括：

将第k个可定位视频片段在二维时间格网中的列号信息j作为x，将第k个可定位视频片段在二维时间格网中的行号信息i作为y，从而生成第k个可定位视频片段的空间点p_k(x,y)，k＝1,2,3…,K,K表示可定位视频片段的总个数。

进一步地，步骤3中具体包括：

对空间点集P所处空间范围进行分割，划分为多个矩形区域，将每个矩形称作目录矩形并作为树结构的中间节点，然后将各空间点按照空间位置分配到不同矩形区域内，生成相应中间节点的子节点。

进一步地，步骤4中，所述在已生成的R树空间索引结构中查找得到该空间点具体包括：首先搜索满足查询条件的目录矩形并定位到相应中间节点；然后搜索该中间节点的下级子节点，以查找满足检索条件的空间点对象。

本发明的有益效果：

(1)本发明应用二维栅格行列值描述可定位视频拍摄的起始时间与结束时间，基于整型数据类型进行处理，降低了时间信息运算复杂度；

(2)本发明在二维图形空间上进行时间信息检索与时间信息操作，突破了传统以一维时间轴与时间戳为主的时间信息检索方式；

(3)通过按照本发明的方法进行可定位视频检索与查询，测试结果显示本发明能够显著提升查询效率，降低查询响应时间。

附图说明

图1为本发明实施例提供的一种基于二维时间格网的可定位视频检索方法的流程示意图；

图2为本发明实施例提供的二维时间格网的示意图；

图3为本发明实施例提供的可定位视频片段的空间点对象的生成示意图；

图4为本发明实施例提供的R树空间索引结构的生成示意图；

图5为本发明实施例提供的基于二维时间格网的可定位视频检索过程示意图；

图6为本发明实施例提供的可定位视频检索效率测试结果示意图。

具体实施方式

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

如图1所示，本发明实施例提供一种基于二维时间格网的可定位视频检索方法，包括以下步骤：

S101：根据所有可定位视频片段中的最早开始时间T_s、最晚结束时间T_e以及时间分辨率，结合每个可定位视频片段的开始时间与结束时间，计算每个可定位视频片段的行列号信息，从而将一维连续的时间区间信息按照相应的时间分辨率映射到二维栅格空间得到二维时间格网；

具体地，本步骤主要是结合时间分辨率及时间范围，基于栅格结构定义二维时间格网。

一般而言，利用摄像机或智能手机拍摄的视频片段，均拍摄于特定时刻并具备一定的拍摄时长，其时间间隔可以表示为[t_s,t_e]，其中t_s和t_e分别为视频片段的开始时间和结束时间，设定第k个视频片段的开始时间和结束时间分别为

和

且

作为一种可实施方式，计算第k个可定位视频片段的行列号信息，具体包括：

步骤A1：利用公式(1)计算第k个可定位视频片段在时间分辨率ct下的原始列号信息u与行号信息v：

其中，

和

分别表示第k个可定位视频片段的开始时间和结束时间，T_s分别表示所有可定位视频片段中的最早开始时间，

k＝1,2,3…,K,K表示可定位视频片段的总个数；时间分辨率可以用小时、分钟、秒或其他不同时长来衡量。

步骤A2：将原始行列号信息表示为矢量形式(u,v,1)，然后按照预设规则计算得到可定位视频片段在二维时间格网中的新列号信息j和新行号信息i；

其中，所述预设规则具体为：

当1≤u<(N+1)/2,1<v≤(N+1)/2时，则j＝u,i＝v；

当u>v+(N+1)/2,1≤u≤(N+1)/2,(N+1)/2<v≤N时，利用公式 (2)将矢量(u,v,1)转换为(j,i,1)：

当(N+1)/2<v≤u+(N+1)/2≤N,1≤u≤(N+1)/2时，利用公式(3) 将矢量(u,v,1)转换为(j,i,1)：

当(N+1)/2<u≤N,(N+1)/2≤v≤N时，利用公式(4)将矢量(u,v,1) 转换为(j,i,1)：

其中，N表示二维时间格网的列，N＝(T_e-T_s-ct)/ct，T_e分别表示所有视频片段中的最晚结束时间，

按照上述步骤计算得到所有可定位视频片段的行列号信息，最终可以得到一个M行N列的二维时间格网，其中，M＝(N+1)/2。

从上述实施方式中可以看出：二维时间格网由若干个时间栅格组成，每个时间栅格的位置信息表示对应的可定位视频片段的时段信息；如图2所示，二维时间格网的列信息表示可定位视频片段的开始时间，二维时间格网的行信息表示可定位视频片段的结束时间，每个时间栅格可以用于存储可定位视频片段标识码 ID。仍以图2为例，假定第k个可定位视频片段位于二维时间格网的第i行、第j列，其时间栅格为C_k(j,i)，其时间语义定义如下：

(1)在R1子区域，即当1≤j<M,1<i≤M,j<i时，单元格(j,i)的时间语义为开始于j、终止于i。

(2)在R2子区域，即当M<j≤N,1≤i<M,j≥i+M时，单元格(j,i)的时间语义为开始于i时刻、终止于j+1时刻。

(3)在R3子区域，即当M<j≤N,1<i≤M,j<i+M时，单元格(j,i)的时间语义为开始于j时刻、终止于i+M时刻。

(4)在R4子区域，即当1≤j≤M,1≤i≤M,j≥i时，单元格(j,i)的时间语义为开始于j时刻、终止于i+M时刻。

S102：根据每个可定位视频片段在二维时间格网中的行列号信息，为每个可定位视频片段生成其对应的空间点，最终所有可定位视频片段的空间点构成空间点集P；

作为一种可实施方式，如图3所示，所述为每个可定位视频片段生成其对应的空间点具体包括：将第k个可定位视频片段在二维时间格网中的列号信息j作为x，将第k个可定位视频片段在二维时间格网中的行号信息i作为y，从而生成第k个可定位视频片段的空间点p_k(x,y)，k＝1,2,3…,K,K表示可定位视频片段的总个数。

S103：利用R树空间索引方法生成空间点集P对应的R树空间索引结构；

作为一种可实施方式，本步骤具体包括：对空间点集P所处空间范围进行分割，划分为多个矩形区域，将每个矩形称作目录矩形并作为树结构的中间节点，然后将各空间点按照空间位置分配到不同矩形区域内，生成相应中间节点的子节点。如图4所示。

S104：根据可定位视频检索条件定义的开始时间和结束时间定位到二维时间格网中的对应时间栅格，根据该时间栅格的行列号信息生成对应的空间点，在已生成的R树空间索引结构中查找得到该空间点，即得到该空间点对应的可定位视频。

作为一种可实施方式，所述在已生成的R树空间索引结构中查找得到该空间点具体包括：首先搜索满足查询条件的目录矩形并定位到相应中间节点；然后搜索该中间节点的下级子节点，以查找满足检索条件的空间点对象。如图5所示，点q为定义的时间检索条件，根据R树索引，点q位于目录矩形内，符合条件的视频片段仅可能存在于目录矩形R2，从而仅与R2下级子节点gv7，gv8，gv9 进行比较，进而提高了检索效率。

本发明结合海量视频检索需求，从二维格网的角度，结合可定位视频的拍摄开始时间与结束时间，按照相应的时间分辨率定义二维时间格网，采用格网单元的行列信息表达可定位视频时间信息，并将格网单元转换为空间点对象，应用空间索引方法构建基于二维时间格网的时间索引，能够以图形化的方式进行基于时间的可定位视频查询，降低了可定位视频时间信息处理复杂度，显著提升了查询效率。

为了测试本发明提供的可定位视频检索方法的检索效率，本发明还提供有下述实验数据。

按照本发明提供的可定位视频检索方法，应用从10万到100万条记录的6 个可定位视频数据集，对其检索的响应时间进行了测试，并与传统基于时间戳的 B树索引的检索方法进行了比较。如图6所示，在不同数据量的情况下，基于二维时间格网的可定位视频检索方法均能显著提升检索效率，其中，在80万条记录时提升幅度最大，缩短响应时间43.34毫秒。尽管随着数据量的增加，检索效率略有下降，但在100万条记录时仍缩短响应时间29.62毫秒。在实际应用中，如采用缓存大小优化等查询优化方法，将进一步提升检索效率。

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

Claims (4)

1.一种基于二维时间格网的可定位视频检索方法，其特征在于，包括：

步骤1：根据所有可定位视频片段中的最早开始时间

、最晚结束时间

以及时间分辨率，结合每个可定位视频片段的开始时间与结束时间，计算每个可定位视频片段的行列号信息，从而将一维连续的时间区间信息按照相应的时间分辨率映射到二维栅格空间得到二维时间格网；步骤1中，所述计算每个可定位视频片段的行列号信息，具体包括：

步骤A1：利用公式（1）计算第k个可定位视频片段在时间分辨率ct下的原始列号信息u与行号信息v：

其中，

分别表示第k个可定位视频片段的开始时间和结束时间，

表示所有可定位视频片段中的最早开始时间，

，k=1,2,3…,K, K表示可定位视频片段的总个数；

步骤A2：将原始行列号信息表示为矢量形式(u,v,1)，然后按照预设规则计算得到可定位视频片段在二维时间格网中的新列号信息j和新行号信息i；

其中，所述预设规则具体为：

当

时，则j=u, i=v；

当

时，利用公式（2）将矢量(u,v,1)转换为(j,i,1)：

当

时，利用公式（3）将矢量(u,v,1)转换为(j,i,1)：

当

时，利用公式（4）将矢量(u,v,1)转换为(j,i,1)：

其中，N表示二维时间格网的列，

，

表示所有视频片段中的最晚结束时间，

；

步骤2：根据每个可定位视频片段在二维时间格网中的行列号信息，为每个可定位视频片段生成其对应的空间点，最终所有可定位视频片段的空间点构成空间点集P；

步骤3：利用R树空间索引方法生成空间点集P对应的R树空间索引结构；

步骤4：根据可定位视频检索条件定义的开始时间和结束时间，将其定位到二维时间格网中的对应时间栅格，根据相关时间栅格的行列号信息生成对应的空间点，在已生成的R树空间索引结构中查找得到该空间点，即得到该空间点对应的可定位视频。

2.根据权利要求1所述的一种基于二维时间格网的可定位视频检索方法，其特征在于，步骤2中，所述为每个可定位视频片段生成其对应的空间点具体包括：

将第k个可定位视频片段在二维时间格网中的列号信息j作为x，将第k个可定位视频片段在二维时间格网中的行号信息i作为y，从而生成第k个可定位视频片段的空间点

，k=1,2,3…,K, K表示可定位视频片段的总个数。

3.根据权利要求1所述的一种基于二维时间格网的可定位视频检索方法，其特征在于，步骤3中具体包括：

对空间点集P所处空间范围进行分割，划分为多个矩形区域，将每个矩形称作目录矩形并作为树结构的中间节点，然后将各空间点按照空间位置分配到不同矩形区域内，生成相应中间节点的子节点。

4.根据权利要求3所述的一种基于二维时间格网的可定位视频检索方法，其特征在于，步骤4中，所述在已生成的R树空间索引结构中查找得到该空间点具体包括：首先搜索满足查询条件的目录矩形并定位到相应中间节点；然后搜索该中间节点的下级子节点，以查找满足检索条件的空间点对象。

Images