一种面向海洋监控视频的索引机制∗

田赤英

（中国大洋矿产资源研究开发协会 北京 100860）

一种面向海洋监控视频的索引机制∗

田赤英

（中国大洋矿产资源研究开发协会 北京 100860）

数据作为一种资产其蕴含的价值越来越重要，把收集到的数据存储下来用于后续的数据分析与挖掘具有重要意义。论文针对海量的海洋监控视频，提出一种存储方案来满足查询需求。在此基础上，文中提出一种索引结构RB-Tree，使得基于该索引可实现海量数据的快速检索。此外，文章从理论层面对索引查询的时间代价进行分析，并与基于传统B+Tree、R-Tree索引的查询时间代价进行对比，说明RB-Tree在海量视频数据管理上的优势。

海量视频数据；监控视频；B+Tree索引；R-Tree索引；RB-Tree索引

1 引言

海洋调查船是用于海洋科学考察、应用技术研究以及测量或勘探等船舶的统称［1］。大洋综合资源调查船是集多学科、多功能、多技术手段为一体、满足以大洋资源为主同时兼顾相关深海多学科交叉研究需求的全球级现代化海洋调查船，承载海洋地质、海洋地球物理、海洋化学、海洋生物、物理海洋、海洋气象、海洋声学等综合调查任务［2］。在该船的信息化系统中，数据可分为实时采集数据、人工上传数据和实时视频数据三大类，其中实时视频数据包含卫星电视、海底摄像等各种制式的视频信息。对于各种不同制式的视频数据，现有系统聚焦于如何将视频信息实时发送给远程用户进行观看。然而，随着存储设备成本的下降，人们更倾向于将所有获取到的数据存储下来用于挖掘和分析。

对于海量视频数据，其价值的完整体现需要多种技术的协同。文件系统提供最底层存储能力的支持；为了便于数据管理，需要在文件系统之上建立数据库系统；通过索引等的构建，对外提供高效的数据查询等常用功能；最终通过数据分析技术从数据库中的大数据提取出有益的知识［3］。在底层文件系统层，可以借助GFS文件系统［4］实现视频类大文件的存储。在文件系统之上，为支持海量数据，采用 NoSQL 方式管理数据［5～6］。典型的 NoSQL数据库包括基于键值对模型、列式存储模型、文档模型和图模型四种类型的数据库［7～9］，由于视频文件属于非结构化数据，查询并不涉及视频内容，故可采用键值对模型对海量视频数据进行建模。在利用键值对进行建模存储时，面临以下挑战：

1）实时监控产生的视频数据具有时间段、地理位置等属性，如何定义视频数据的键，以支持基于时间段、地理位置的查询；

2）对于海量视频数据，需要构建索引来加快查询，如何设计索引结构。

2 数据建模与查询

实时视频本身具有时间、地点的属性，在对这些视频数据进行查询时，需要查询某个时间段内某个区域的视频。在以键值对方式存储文件时，为支持基于地理区域和时间区间的查询，定义键时需要将这两种因素考虑在内。此外，由于同一时间可能有多个设备对同一区域进行监控，因此若仅考虑地理区域和时间因素设计的键不具有唯一性，此时，需另外考虑设备ID号。因此本文对视频数据以键值对方式进行建模，具体如下：

＜key，value＞=＜设备ID号+地理区域+时间区间，视频文件的物理存放地址＞

其中，设备ID号是把各种不同设备的标识号映射为长度固定的标识号；地理区域为矩形区域对角点的坐标，即（(x1，y1)，(x2，y2)）；时间区间为［起始时间，结束时间］，时间以“年月日时分秒”来表示。

例1。对于某设备，假定其映射后得到的设备标识号为000001，其在2016年8月8日的16：00：00到 16：10：00分之间对区域（（385，691），（387，689））进行拍摄，所形成的视频文件的key表示为“000001385691387689201608081600002016080816 1000”。

由例1可以看到，该key的长度较长，为提高查询效率，需对key进行压缩，缩短其长度。对于接收的监控视频，当缓存中视频流达到规定的最大长度限制k时，会创建一个文件将其写入硬盘。因此，每个视频文件的时长较短。假定一个视频文件的时长不超过10min，则时间区间可表示为（起始时间，时间长度），其中时间长度位数为三位，最大取值为600（10min×60s/min）。例1中视频文件的key经压缩后可表示为“00000138569138768920160808160000600”，缩短了11位。

基于定义的存储模型，面向海洋监控视频的查询定义为：给定一个地理区域s，查询该区域内包含时间段（t1，t2］之间监控内容的视频文件。

在查询某个时间段内某个区域的视频文件时，要从key中抽取出表示地理区域和时间区间的子串，判断是否与查询条件中的区域和时间段有重叠。假定一个查询，查找时间段2016年8月8日15：45：00到2016年8月8日16：05：00之间在区域（（386，690），（389，688））内拍摄的视频文件。首先判断区域（（386，690），（389，688））与key中第7到18位所代表的区域（（385，691），（387，689））是否有重叠；若重叠，则继续判断时间区间［2016-08-08 15：45：00，2016-08-08 16：05：00］与key中第19到35位所代表的时间区间是否有重叠。若时间区间也重叠，则返回该视频文件作为结果。

3 RB-Tree索引

在本文所定义的查询中，若视频文件的最大和最小时间点至少有一个位于查询声明的时间区间中，且视频对应矩形监测区域的四个顶点坐标中至少有一个位于查询声明的地理区域中，则属于满足条件的查询结果。在传统的键值对＜key，value＞存储模型中，为了加快key的查找，常常在key上构建B+Tree索引。在B+Tree中，叶子节点中对象取值为其父节点定义的取值范围内的值。在本文中，每个视频文件对应一个时间区间，因此要对B+Tree进行修改，构建类B+Tree，其与B+Tree的区别在于叶子节点中对象的值是一个时间区间。对于地理区域的查询，属于空间查询，B+Tree并不适用。此时需考虑利用R-Tree来构建索引。在R-Tree中，每个节点对应存储一个矩形地理区域中所有对象的指针，若某非叶结点的孩子节点是非叶节点，则其所有孩子节点代表的矩形地理区域均包含在该节点对应的地理区域中。

对于海量视频数据来说，单纯考虑修改B+Tree对时间范围进行索引或利用R-Tree对地理区域进行索引，虽然在一定程度上可以提高查询效率，但仍有提升空间。因此，本文提出一种混合索引树RB-Tree，使得其可以对时间范围和地理区域同时进行索引，提高查询效率。

3.1 RB-Tree索引的构建

由于地理区域是固定不变的，可以考虑把地图以面积为s的矩形进行划分，每个矩形块对应的区域称之为单位地理区域。在构建RB-Tree时，以单位地理区域为最小矩阵区域，构建R-Tree。与传统R-Tree不同的地方在于，每个视频文件并不直接作为矩阵区域中的对象。为支持基于时间区间的快速查询，对每个单位地理区域，为区域内所有视频文件构建类B+Tree，R-Tree中各节点仅包含对应地理区域中类B+Tree根节点的指针。构建类B+Tree时，把若干连续时间的视频文件作为对象集，并以这些视频所在的时间区间作为标识创建叶子节点，然后自底向上依次创建上层节点。至此，完成RB-Tree的构建。下面给出RB-Tree的定义：

定义 1（RB-Tree）：一棵树是 RB-Tree，需具有以下特征：

1）树中节点包含的对象是一棵类B+Tree；

2）类B+Tree中每个节点对应一个时间区间，非叶子节点包含时间区间内的n个时间点，存在指针分别指向每个时间点之前和之后的时间区间对应的节点；

3）类B+Tree中每个叶子节点包含一个对象集，对应位于指定时间区间的所有视频文件的key及其物理地址。

RB-Tree的具体构建算法如下：

1）把视频文件分组，位于相同单位地理区域的视频文件分为一组，当某视频文件的地理区域跨越多个单位地理区域时，将其放入多个对应分组中；

2）对步骤1）得到的每个分组中视频文件再次进行分组，使得每组包含m个视频文件（最后一组包含小于等于m个）；

3）为每组视频文件创建叶子节点，节点把能够包含组内视频文件对应时间区间的最小时间区间作为标识，节点中包含指向各视频文件的指针；

4）叶子节点根据时间先后顺序用指针进行关联；

5）把节点按其时间范围排序，以相邻m个为一组进行分组，对应每组创建一个父亲节点，把包含分组内节点对应时间区间的最小时间区间作为父亲节点的标识，以各孩子节点时间区间的最大边界值形成时间点集合T；

6）在集合T中任意两个相邻时间点之间创建一个指针，指向时间区间在两个时间点之间的孩子节点；

7）对于集合T最邻近所属节点时间区间最大和最小边界值的两个时间点，分别创建指向时间区间在边界值和相邻时间点之间的节点的指针；

8）以5）中创建的节点为孩子，构建上层父节点，使得每个父节点的孩子个数为m（同一层中最后一个节点的孩子数小于等于m），若新创建的节点个数大于1，转5），否则，转9）；

9）为每个单位地理区域创建一个节点，节点中包含指向该区域中的类B+Tree根节点的指针，并记录每个根节点对应的时间区间。

10）以存在公共交点的相邻m′个单位地理区域为单元，创建上层节点，直至完成R-Tree的构建。其中，非叶节点包含指向孩子节点的指针及其对应的地理区域。

值得注意的是，在查询某地理区域内位于某时间区间的视频文件时，既可以先基于地理区域进行条件过滤，也可以先基于时间区间进行条件过滤。由RB-Tree的构建可以看到，本文倾向于先基于地理区域进行条件过滤。这样做是因为地理区域是固定不变的，而时间是一直变化的。若先基于时间区间构建类B+Tree，再对叶子节点中包含的对象构建R-tree，则需频繁构建新的R-Tree。而先基于地理区域构建R-Tree，则每次只需对若干个B+Tree进行插入节点的操作，而对多个B+Tree进行插入操作更易并行化，从而加快更新速度。

在RB-Tree中，类B+Tree的每一层之所以都仅有一个节点包含的指向孩子节点或视频文件的指针数量小于等于m，是因为在RB-Tree中不存在修改和删除操作，仅随时间推移而不断插入新的对象，在后续章节会详细介绍RB-Tree的更新。

3.2 RB-Tree索引的查询

在进行查询时，由于不关心设备ID号，仅以地理区域和时间区间为查询条件，且在RB-Tree构建过程中，地理区域是基于单位地理区域进行划分的，因此，构建树的过程中仅需考虑key中时间区间相关的部分。基于RB-Tree的查询算法具体如下：

1）根据查询条件中给定的地理区域s，从RB-Tree根节点开始，逐层向下，寻找与s有重叠的子节点，直至叶子节点为止；

2）检索叶子节点中记录的各个类B+Tree的时间区间，根据指向类B+Tree的指针获取特定的类B+Tree的根节点；

3）对于查询条件中给定的时间区间（t1，t2］，依次把t1、t2与节点包含的时间点集中各时间点进行比较，找出所有与时间区间（t1，t2］有重叠的下层孩子节点，若孩子节点是非叶节点，转3），否则，转4）；

4）顺序读取节点中包含的key，判断该key对应的时间区间是否与（t1，t2］有重叠，若重叠，则根据key对应的value返回视频文件。

3.3 RB-Tree索引的更新

监控视频文件随时间不断增加，不存在修改或删除，因此只需考虑增加新的视频文件后如何进行RB-Tree的更新。RB-Tree包含R-Tree和类B+Tree，插入新的视频文件会引起类B+Tree叶子节点的更新，该更新会逐层向上传递，直至类B+Tree的根节点。

在RB-Tree中，类B+Tree的非叶节点至多包含m个孩子，当某节点随时间推移插入的孩子节点达到m时，在此插入会导致新的非叶节点的创建。RB-Tree索引的更新算法如下：

1）新增一个视频文件时，根据其所属单位地理区域找到相应的类B+Tree；

2）找到类B+Tree中与插入的视频文件时间区间最接近的叶子节点i；

3）若节点i中对象个数小于m，则更新对应叶子节点信息，插入该视频文件的指针；

（1）更新其父节点中对应该节点的时间区间，若父节点为根节点，转2），否则，以其父节点作为当前节点，转1）；

（2）更新RB-Tree中指向该类B+Tree根节点的叶子节点中对应的时间区间，停止；

4）若节点i中对象个数等于m，创建新的叶子节点o，记录指向新增的视频文件的指针，并令其时间区间为新增视频文件对应的时间区间；

（1）在上层节点中寻找时间区间与节点o最接近的节点p；

（2）若节点p中孩子节点个数小于m，则为其添加指向节点o的指针，把p的时间区间最大边界值作为新的时间点插入现有时间点集中并更新p时间区间，令o的时间区间最大边界值作为p的时间区间的最大边界值，否则，转（3）；

（3）创建新的节点q，添加指向o的指针，并更新q的时间区间为o的时间区间；

（4）若p不是根节点，转（1），否则，创建新的根节点r，令p、q为其孩子节点，添加时间区间和时间点集，并更新RB-Tree叶子节点中指向被更新的类B+Tree的时间区间和地址指针，停止。

4 RB-Tree索引查询代价分析

为了便于进行查询代价的分析，本节首先定义如表1所示符号。

表1

在RB-Tree中，叶子节点仅包含指向类B+Tree根节点的指针，磁盘中每次获取节点需要读取至少一页的数据，故当叶子节点中指针数量为「Spage/（ST+Sadd）⏋时，可以最大程度减少I/O次数。对于非叶节点，除了包含指向其孩子节点的指针外，还包含表示各孩子节点对应的地理区域，因此，当非叶节点包含的孩子节点数量为「Spage/（Sarea+Sadd）⏋时，可以最大程度减少I/O次数。假定总的叶子节点数量为n，当仅需访问一个目标叶子节点时，从RB-Tree的根节点开始查找叶子节点，树中每层均需访问一个节点，需要I/O的次数为

对于RB-Tree叶子节点所指向的类B+Tree，其叶子节点包含指向视频文件的指针以及对应视频文件的key，故当叶子节点中指针数量为「Spage/（Skey+Sadd）⏋时，可以最大程度减少I/O次数。对于非叶节点，除了包含指向其孩子节点的指针外，还包含一个覆盖全部孩子节点时间区间的时间区间以及一个时间区间内的时间点集合，时间点集合中时间点的数量为孩子节点数量减一，故当非叶节点包含的孩子节点数量为「（Spage-ST-Sadd）/（St+Sadd）⏋时，可以最大程度减少I/O次数。在RB-Tree的叶子节点中，假定一棵类B+Tree的叶子节点数量为n′，顺序读取每棵类B+Tree对应的时间区间，当仅需访问一个类B+Tree中的叶子节点时，从类B+Tree的根节点开始查找叶子节点，树中每层均需访问一个节点，需要I/O的次数为

因此，一次查询需要的I/O的次数为

在上述RB-Tree中，一棵类B+Tree中包含的视频文件最多有n′×「Spage/（Skey+Sadd）⏋个，一个RB-Tree中包含的类B+Tree最多有n×「Spage/（ST+Sadd）⏋个，故一棵RB-Tree中总的视频文件最多有N=n′×「Spage/（Skey+Sadd）⏋×n×「Spage/（ST+Sadd）⏋个。

在最坏情况下，每个RB-Tree叶子节点均包含指向同一时间区间的类B+Tree。若仅用类B+Tree对数据进行索引，叶子节点对应的视频文件数为n×n′×「Spage/（Skey+Sadd）⏋，共有N′=「N/（n×n′×「Spage/（Skey+Sadd）⏋）⏋个叶子节点，则需要I/O的次数为

根据RB-Tree中叶子节点包含的类B+Tree的数量「Spage/（ST+Sadd）⏋、每个类B+Tree中包含的视频文件数量「Spage/（Skey+Sadd）⏋以及叶子节点的数量n′，

若仅用R-Tree对数据进行索引，共有N′=「N/（「Spage/（ST+Sadd）⏋×「Spage/（Skey+Sadd）⏋×n′）⏋个叶子节点。若访问某个叶子节点中的视频文件，则需要I/O的次数为可知RB-Tree中每个叶子节点对应包含的视频文件数量为

在进行查询时，由于需要同时考虑地理区域和时间区间两个条件，在利用类B+Tree进行检索时，若位于同一时间区间内的视频文件数过多，会使得获取一个叶子节点中所有数据需要多次I/O操作，使得查询效率下降。在利用R-Tree进行检索时，若位于同一地理区域内的视频文件数过多，也会使得获取一个叶子节点中所有数据需要多次I/O操作，使得查询效率下降。通过本章节提出的I/O代价计算公式，可以算出当视频数据数量多大规模时，利用RB-Tree可以显著提高查询效率。

5 结语

本文讨论了海量海洋监控视频的建模存储，并提出一种索引结构RB-Tree来提高视频检索的效率。文中对RB-Tree的查询复杂度进行深入分析，在此基础上，对在何种情况下利用该索引可以有效提高查询效率进行了探讨。

本文主要从理论层面分析了利用RB-Tree进行索引查询的复杂度，下一步，将结合具体的硬件对其查询效率进行深入的分析。

［1］李尉尉，王慧祺，夏登文，等.中国海洋调查船现状及发展思考［J］.海洋开发与管理，2012，29（5）：41-43.LI Weiwei，WANG Huiqi，XIA Dengwen，et al.Reflections on the Status Quo and Development of Chinese Marine Survey Vessels［J］.Ocean Development and Management，2012，29（5）：41-43.

［2］刘健中，管义锋.大洋综合资源调查船全船结构强度有限元分析［C］//船舶与海洋结构学术会议暨中国钢结构协会海洋钢结构分会成立三十周年纪念学术会议.长沙：中国造船工程学会，中国钢结构协会，2015：178-185.LIU Jianzhong，GUAN Yifeng.Whole Structure Strength Analysis of Oceanographic Research Vessel［C］//Conference on Ship and Ocean Structure and the 30th Anniversary Conference of China Steel Structure Association.Changsha：China Shipbuilding Engineering Society，China Steel Construction Society，2015：178-185.

［3］孟小峰，慈祥.大数据管理：概念、技术与挑战［J］.计算机研究与发展，2013，50（1）：146-169.MENG Xiaofeng，CI Xiang.Big Data Management Concepts，Techniques and Challenges［J］.Journal of Computer Research&Development，2013，50（1）：146-169.

［4］Ghemawat S，Gobioff H，Leung S T.The Google file system［C］//ACM Symposium on Operating Systems Principles.New York：ACM，2003：29-43.

［5］Li Y，Manoharan S.A performance comparison of SQL and NoSQL databases［C］//Pacific Rim Conference on Communications，Computers and Signal Processing.Washington D C：IEEE Computer Society，2013：15-19.

［6］Chen M，Mao S，Liu Y.Big data：a survey［J］.Mobile Networks and Applications，2014，19（2）：171-209.

［7］Han J，Haihong E，Le G，et al.Survey on NoSQL database［C］//International Conference on Pervasive computing and applications.Washington D C：IEEE Computer Society，2011：363-366.

［8］He C.Survey on NoSQL Database Technology［J］.Journal of Applied Science and Engineering Innovation，2015，2（2）：50-54.

［9］Sharma V，Dave M.SQL and NoSQLDatabases［J］.International Journal of Advanced Research in Computer Science and Software Engineering，2012，2（8）：20-27.

［10］Hadjieleftheriou M，Manolopoulos Y，Theodoridis Y，et al.Encyclopedia of GIS［M］.US：Springer，2008：993-1002.

［11］Chen S，Gibbons P B，Mowry T C，et al.Fractal prefetching B+-Trees：optimizing both cache and disk performance［C］//ACM SIGMOD International Conference on Management of Data.New York：ACM，2002：157-168.

An Index for Ocean Surveillance Video

TIAN Chiying
（China Ocean Mineral Resources Research and Development，Beijing 100860）

The value of data which is considered as a kind of asset has become more and more important.Storing collected data for subsequent analysis and mining has great significance.In this paper，a storage scheme to meet the query requirement for massive ocean surveillance video is proposed.Propose the index RB-Tree to realize fast query over massive data is also proposed.Besides，the paper theoretically analyzes the time cost of query.The query cost of the RB-Tree with the traditional B+Tree and R-Tree to indicate our advantage on massive ocean video data is furtherly compared.

massive ocean video data，surveillance video，B+Tree index，R-Tree index，RB-Tree index

X85

10.3969/j.issn.1672-9722.2017.11.032

Class Number X85

2017年5月21日，

2017年6月27日

田赤英，女，研究员，研究方向：船载信息系统。