面向视频数据的时空伴随模式挖掘算法.pdf

2023 08 10计算机应用,Journal of Computer Applications2023,43(8):2330-2337ISSN 10019081CODEN JYIIDUhttp：/面向视频数据的时空伴随模式挖掘算法张潇誉1，于自强1，2*，刘承栋1，李博涵3，靖常峰4（1.烟台大学 计算机与控制工程学院，山东 烟台 264005；2.自然资源部城市国土资源监测与仿真重点实验室，广东 深圳 518034；3.南京航空航天大学 计算机科学与技术学院，南京 211106；4.中国地质大学（北京）信息工程学院，北京 100083）（通信作者电子邮箱）摘要：时空伴随模式是具有时空伴随关系的视频对象组合。为了从海量视频数据中快速发现符合查询条件的时空伴随模式，提出一种基于三重剪枝匹配策略的时空伴随模式发现算法MPA。首先，利用已有的视频对象识别和跟踪模型对视频对象进行结构化提取；然后，对提取的连续帧中大量重复出现的视频对象进行压缩存储并构建索引；最后，设计基于前缀树的时空伴随模式发现算法，以快速发现符合查询条件的时空伴随模式。在真实数据集和合成数据集上的实验结果表明，与暴力搜索算法（BFA）相比，所提算法的效率提高了30%左右，且数据量越大，效率提高越明显。因此，所提算法能够快速发现海量视频数据中满足查询条件的时空伴随模式。关键词：视频对象；结构化；时空伴随模式；索引结构；剪枝策略中图分类号：TP391.3 文献标志码：ASpatial-temporal co-occurrence pattern mining algorithm for video dataZHANG Xiaoyu1，YU Ziqiang1，2*，LIU Chengdong1，LI Bohan3，JING Changfeng4（1.School of Computer and Control Engineering，Yantai University，Yantai Shandong 264005，China；2.Key Laboratory of Urban Land Resources Monitoring and Simulation，Ministry of Natural Resources，Shenzhen Guangdong 518034，China；3.College of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing Jiangsu 211106，China；4.School of Information Engineering，China University of Geosciences，Beijing，Beijing 100083，China）Abstract:Spatial-temporal co-occurrence patterns refer to the video object combinations with spatial-temporal correlations.In order to mine the spatial-temporal co-occurrence patterns meeting the query conditions from a huge volume of video data quickly，a spatial-temporal co-occurrence pattern mining algorithm with a triple-pruning matching strategy Multi-Pruning Algorithm（MPA）was proposed.Firstly，the video objects were extracted in a structured way by the existing video object detection and tracking models.Secondly，the repeated occurred video objects extracted from a sequence of frames were stored and compressed，and an index of the objects was created.Finally，a spatial-temporal co-occurrence pattern mining algorithm based on the prefix tree was proposed to discover the spatial-temporal co-occurrence patterns that meet query conditions.Experimental results on real and synthetic datasets show that the proposed algorithm improves the efficiency by about 30%compared with Brute Force Algorithm（BFA），and the greater the data volume，the more obvious the efficiency improvement.Therefore，the proposed algorithm can discover the spatial-temporal co-occurrence patterns satisfying the query conditions from a large volume of video data quickly.Key words:video object;structuration;spatial-temporal co-occurrence pattern;index structure;pruning strategy0 引言 当前，海量视频数据蕴含丰富的时空信息，快速查找一段视频中满足用户指定时空伴随关系的视频对象组合对于若干视频查询具有重要意义。例如，办案人员根据已知案情线索，急需在案发地周围监控视频中查找“2个黑衣男子在某银行周边多个地点结伴行走的视频片段”；又如，自动驾驶研发人员需要从视频库中快速查找“自动驾驶车辆与前方车辆距离小于10 m且持续行驶5 s以上的视频片段”用于自主导航模型调优。本文将这种满足用户指定时空伴随关系的视频对象组合称为时空伴随模式，并研究基于结构化查询思想的视频数据时空伴随模式发现算法。当前，计算机视觉和机器学习领域对视频内容检索问题进行了大量研究。其中，基于自然语言查询语义的视频内容检索问题1-7与本文研究问题较为相似，即给出自然语言描述的查询语义，从给定的视频中查找满足查询语义的视频片段。例如，给定查询文本“一个人在打篮球”时，现有检索系统将根据整个查询文本的视频特征，或者关注于文本与视频中所表现的实体（如“人”“篮球”）来计算合适的视频片段6；然而，该类方法的相关工作并不能直接用来解决本文要研究的问题，文章编号：1001-9081（2023）08-2330-08DOI：10.11772/j.issn.1001-9081.2022101566收稿日期：20220926；修回日期：20221108；录用日期：20221111。基金项目：国家自然科学基金资助项目（62172351）。作者简介：张潇誉（1999），女，山东枣庄人，硕士研究生，主要研究方向：视频数据处理；于自强（1984），男，山东青岛人，副教授，博士，CCF会员，主要研究方向：数据库、数据挖掘；刘承栋（2000），男，山东淄博人，硕士研究生，主要研究方向：视频数据结构化查询；李博涵（1979），男，副教授，博士，CCF高级会员，主要研究方向：时空数据库、知识图谱、自然语言处理；靖常峰（1979），男，山东济南人，教授，博士，主要研究方向：城市运行管理物联网技术、城市时空大数据建模、时空分析与挖掘。第 8 期张潇誉等：面向视频数据的时空伴随模式挖掘算法因为此类模型大多基于深度神经网络的端到端的学习框架，模型所能应对的查询类型与标注的训练数据紧密相关。现实中，受限于标注的训练数据的类型及数量，此类模型不足以支持面向视频数据复杂变化的查询需求。考虑到上述原因，本文拟采用结构化查询思想设计视频数据的时空伴随模式发现算法。当前，视频数据中的视频对象检测和跟踪算法8-15取得了良好效果，能较准确地从视频数据中识别并提取不同视频对象的位置、属性等信息，这为本文从视频数据中提取和识别视频对象及属性，并量化视频对象之间的时空关系提供了必要的技术条件。因此，本文利用已有的视频对象识别和跟踪模型，对视频中每一帧的所有视频对象进行结构化提取，获取每个视频对象的标识、属性以及其在对应视频帧中的位置，从而实现视频数据时空伴随模式查询问题的结构化查询语义表述。例如，一个要求至少有一个人和一辆车同时出现的查询可以表示为：SELECT*OVER（ORDER BY FIDRANGE BETWEEN INTERVAL 4 FRAMESPRECEDING AND CURRENT ROW）FROM VR WHERECOEVAL（person 1 car 1，duration=3，a，b OID：distance(a，b)5，angle(a，b)30）在这个例子中，假设该查询是基于一个由4帧组成的滑动窗口进行的，并且要求视频对象共同出现的帧数至少为3，要求共同出现的视频对象之间距离小于5 m且两两之间方位角度要在30内。为了能够快速得到满足结构化查询语义的时空伴随模式，本文提出了基于滑动窗口策略的视频对象 3 层索引（Video Objects Triple Index，VOTI）结构和视频对象剪枝匹配算法。首先采用滑动窗口策略将整个视频划分为多个滑动窗口，每个窗口大小固定，且每个查询所涉及的时空伴随模式出现的连续帧数不超过视频滑动窗口的大小。VOTI的第一层是视频窗口，每个窗口记录该窗口中每一类视频对象的属性及其数量；第二层为每个视频窗口的视频帧，每个视频帧中同样记录该帧中所包含的视频对象的属性及其数量；第三层是每个视频帧所对应的完全图，该完全图中每个视频对象表示为一个顶点，任意两个顶点之间存在一条边，边的权重为两个对应视频对象的距离和相对位置。基于该索引结构，本文提出基于三重剪枝匹配策略的时空伴随模式发现算法MPA（Multi-Pruning Algorithm）。该算法首先根据待查询的时空伴随模式中视频对象的属性、数量和出现的视频帧数对无效视频窗口进行剪枝，并将剩余可能包含时空伴随模式的视频窗口称为候选视频窗口；然后，根据待查询的视频对象数、属性对每个候选视频窗口中的视频帧进行剪枝，得到候选视频帧；最后，再根据每个候选视频帧所对应的完全图对视频对象的距离和相对位置等时空信息进行比对，最终找到满足条件的时空伴随模式。本文的主要工作如下：1）提出了一种面向视频数据的时空伴随模式发现问题，在对视频对象时空关系进行量化的基础上，充分考虑视频对象时空关系在时间维度上的演变特性，提出了针对该问题的高效查询策略。2）在对视频对象属性结构化提取和对视频对象之间时空关系量化表示的基础上，提出了一种面向视频窗口、视频帧和视频对象的三重索引结构，实现对视频窗口、视频帧和视频对象的隶属关系、海量视频对象属性信息，以及视频对象之间时空关系的融合索引。3）基于三重索引结构，提出了一种面向视频窗口、视频帧和视频对象的多级剪枝策略，实现了搜索空间的快速剪枝；然后提出了一种基于Prefix Tree的时空伴随模式的查找匹配算法，实现视频数据时空伴随模式的快速发现。4）在合成数据集和真实数据集上开展了大量的实验，测试了不同参数对算法性能的影响，验证了算法的有效性。1 相关工作 视频内容检索是计算机视觉领域的一个重要问题。早期视频检索工作通常采用视频划分（Video Segmentation）或特征提取方法（Feature Extraction）对视频内容进行检索16-19，基本思想是提取视频的底层视觉特征（Low Level Visual Feature）并构建视觉特征索引，然后基于特征索引查找与给定场景较为相似的视频片段。近年来，基于自然语言查询语义的特定视频场景搜索（Ad-hoc Video Search，AVS）问题被深入研究1-7。Awad 等1在TRECVID2016中首先提出AVS问题，将它作为测试任务之一，并给出了这一问题的测试数据集、测试方法和评价准则。针对AVS问题，Markatopoulou等2提出一种仅利用自然语言查询语义的特定视频场景搜索算法；Lu等3为支持视频事件的关键字查询，构建一个巨大的概念库用于记录视频中对视频对象、场景、行为、活动等进行标注的概念，以减小文本查询语义与视觉标注概念映射到同一语义空间时的距离；Gordon等4提出面向移动视频的交互式问答问题，并提出一种多级交互记忆网络；Das等5提出一种面向动态场景虚拟视频的呈现式问答问题，帮助智能体对周围环境进行感知；陈卓等6提出基于视觉-文本关系对齐的图卷积框架，分别构建文本关系图与视觉关系图表示查询文本与视频片段中的语义关系，然后通过跨模态对齐的图卷积网络评估文本关系与视觉关系的相似度，从而更加精准地检索视频片段；王美珍等7提出一种视频时空检索方法，通过检索最少数量的视频画面检索视频对象包括时间、空间和方向在内的时空信息。上述视频检索模型能够根据自然语言描述的查询条件从视频中查找相关的视频片段，但是难以直接解决本文提出的视频数据时空伴随模式发现问题；因为此类模型大多是采用端到端的学习框架，所能应对的查询类型与标注的训练数据紧密相关，而对于现实中复杂多变的查询问题，不会有大量标注的训练数据集与其一一对应，解决实际问题范围有限。近期一些有关视频查询处理的相关工作主要集中在对视频数据进行声明式查询处理的不同方面20-24。例如，Kang等20提出一种使用低成本过滤器过滤帧的方法，以达到查询处理目的。随后，他们21-22提出了针对视频数据上特定类型聚合的查询处理技术。Bastani等23提出将查询处理与对象跟踪相结合以提高效率。Chen等24考虑了在视频数据上评估合取范式（Conjunctive Normal Form，CNF）时间查询的问题，引入了标记帧集（Marked Frame Set）和稀疏状态图（Sparse State Graph）方法维护上下文，旨在减少处理新帧的开销并促进CNF查询评估。但在视频查询处理中，并没有对视频对象模式匹配算法的研究，因此本文拟采用结构化查询思想设计2331第 43 卷计算机应用视频数据的时空伴随模式发现算法，充分考虑视频对象时空关系在时间维度上的演变特性，提出针对该问题的高效查询策略。另外，随着对目标检测问题的深入研究，视频中多目标跟踪问题的研究11-15成果显著。这些研究工作充分利用深度卷积神经网络在目标检测方面的优势，先对视频进行目标检测，然后根据时间和空间关系建立目标之间的联系，实现目标追踪过程11-12。为了简化目标追踪过程，一些工作13-15将目标检测和跟踪两个过程同时进行，能够有效降低多目标跟踪问题的计算复杂性。这为本文从视频数据中提取和识别视频对象及其属性，并量化视频对象之间的时空关系提供了必要的技术条件。2 相关定义 本文提出一种面向视频数据的时空伴随模式发现问题，针对查询在给定一段时间内同时出现的对象集合，下面将对相关概念和时空伴随模式发现的问题加以形式化说明。定义1 视频帧。将一段视频V看作一个有限的帧序列，V=f0，f1，fi-1，fi，fN-1表示视频V由N帧组成，即N是视频的总长度，视频V的第i+1帧所对应的编号为fi。定义2 视频对象。应用目标检测和追踪算法14，25从每一帧fi中提取一组对象Oi，并为每一个oi Oi提取其所在帧的 编 号（FID）、自 身 编 号（OID）、类 别（Class）、相 关 属 性（Attribute）、边框（Border）等信息，本文将这种从视频中提取的对象（oi）定义为视频对象。这样就在视频V中获得了一个结构化关系VR。如图1所示，在#4帧中，应用对象检测和跟踪算法，获得了两个唯一的对象，OID为1和3。之后将这样的信息存储为VR关系中的两行：一行用于类“car”的对象1，另一行用于类“person”的对象3，这两行都是在帧FID=4时生成的。图1视频数据转化为结构化关系Fig.1Transforming video data into structured relationships定义3 视频窗口。本文采用滑动窗口策略将整个视频划分为多个滑动窗口，每个窗口大小固定，用I表示，每个窗口Ij包含w帧f0，f1，fw-1。定 义 4 时 空 伴 随 模 式。给 定 视 频V=f0，f1，fi，fN-1，若O满足以下条件，那么视频对象组合O就称为时空伴随模式。1）o O，o在帧序列F=fi，fi+1，fi+m每一帧都出现，m不小于用户指定数值。2）oi，oj O，在 帧 序 列F任 意 一 帧 中 满 足dist(oi，oj)d，angle(oi，oj)，其中dist(oi，oj)表示视频对象oi，oj间的欧氏距离，angle(oi，oj)表示视频对象oi，oj间的夹角（以水平方向为基准），d、为用户指定数值。3 视频数据结构化索引 本文以视频对象为基本存储单元，从“视频对象-视频帧-视频窗口”3个层面，对提取的连续帧中大量重复出现的视频对象进行压缩存储并构建索引，从而支撑上层查询算法对视频对象及其时空关系的快速访问。3.1构建同一帧中视频对象空间关系索引首先获取视频每一帧的数据，将同一帧中的每个视频对象看作一个顶点，所有顶点构成一个完全图。完全图是表示为G=(O，E)的无向完全图，其中O为所有顶点集合，E为所有边的集合，两个视频对象之间的空间位置关系表示两个对应顶点之间边的信息。对于任意视频对象oi和oj（oi，oj O），edge(oi，oj)E包含两个属性：一是“权重”，表示oi与oj的相对距离；二是“夹角”（），表示oi与oj的空间相对位置。对于图2（a）中的3辆车和1个人，根据视频中坐标位置来确定视频对象之间的相对位置：car-3在car-1的左前方大约143 位 置，则 图 2（b）中 顶 点 car-3 与 顶 点 car-1 的 夹 角=143，d表示两车之间的距离。根据上述规则，图2（a）中视频对象的相对空间关系可由图2（b）的无向完全图表示。3.2同一视频窗口的视频帧索引几个连续的视频帧组成一个视频窗口，每个窗口大小固定，假设每个窗口Ij包含w帧f0，f1，fw-1且对窗口中的每一帧建立索引，每一帧的索引中记录了该帧所包含的视频对象的属性及数量。如图3所示，帧f1中所包含的视频对象类别为人，数量为2；帧f2中包含的视频对象类别有人和车，数量分别为2和1，其中车的属性又分为颜色与品牌，颜色为白色，品牌为大众；帧f3与f4同理。由此对图3中同一个视频窗口里的所有视频帧建立了索引。图2视频对象空间关系的量化表示图Fig.2Quantitative representation graph of spatial relationship of video objects2332第 8 期张潇誉等：面向视频数据的时空伴随模式挖掘算法3.3视频滑动窗口索引本文采用滑动窗口策略，整个视频划分为多个滑动窗口，每个窗口大小固定且每个查询所涉及的时空伴随模式出现的连续帧数不超过视频滑动窗口的大小。每个窗口记录该窗口中每一类视频对象的属性及数量，例如图4中给出了滑动窗口及索引结构示例，视频窗口I1中包含人和车两类视频对象，其中人数为3，最多出现4帧；车数为6，最多出现4帧，同时车还包含其他属性，例如图中所示颜色与品牌，括号内第1个数字表示属性出现次数，第2个数字表示属性最多出现了多少帧。视频滑动窗口索引的建立方便从窗口层面查找符合条件的视频对象。上述对于视频数据中各个层面的索引组成VOTI索引结构，实现了对视频窗口、视频帧和视频对象的隶属关系、海量视频对象属性信息，以及视频对象之间时空关系的融合索引。VOTI索引结构如图5所示。设候选视频V长度为p，视频窗口集合的窗口数量为k，一个视频帧中平均包含的视频对象数为m。视频窗口和视频帧及其索引用一维帧数组存储，所需空间为S(2(p+k)。某一视频帧中的视频对象可由无向完全图来表示，采用邻接表的存储方式，所需空间为S(m+C2m)。因此，索引结构空间复杂度是O(n+m2)。图3同一视频窗口的视频帧索引Fig.3Video frame index of the same video window图4滑动窗口的示例Fig.4Example of sliding window图5三重索引结构示意图Fig.5Schematic diagram of triple index structure2333第 43 卷计算机应用4 视频结构化查询算法 一个视频可分为若干视频窗口，给定一个视频查询，通常只有少量视频窗口的部分视频帧包含部分满足查询条件的视频对象。本章将研究基于视频对象三重索引结构的多级剪枝策略，在视频窗口、视频帧和视频对象三个层面对视频数据进行快速剪枝，减小目标视频对象集合的查询代价。4.1设计基于三重索引结构的多级剪枝策略基于上述三重索引结构，以视频对象属性和时空关系为双重剪枝条件，提出一种面向视频对象、视频窗口和视频帧的多级剪枝策略。算法1给出多级剪枝匹配策略的伪代码。首先将给定视频V进行处理，得到视频窗口集合I，根据查询条件Q中有关视频对象的属性、数量和出现的视频帧数对无效视频窗口进行剪枝，得到候选视频窗口集合Ic；然后对Ic中每个候选视频窗口Ij中的视频帧进行处理，若满足查询条件则被选定为候选视频帧。假设fi为Ij窗口中符合条件的视频帧，帧fi对应的完全图为Gi=(Oi，Ei)，判断任意视频对象oi和oj（oi，oj Oi）之间是否满足时空关系查询条件，若不全满足时空关系查询条件的话，则删除oi，oj之间的边，循环遍历所有顶点，处理两个顶点之间边的信息，最后剩下的图即为符合条件的一组视频对象。算法1 多级剪枝匹配算法。输入 一段视频数据V，一个查询条件Q；输出 满足查询的对象集合S。m=1将V划分固定大小的视频窗口集合Ifor Ii in I：if Ii满足查询条件Q：将 Ii加入候选视频窗口集合Icend forfor Ii in Ic：if fi满足查询条件Q：for om in Oi：k=m+1for ok in Oi：if edge(om，ok)不满足条件Q：delete edge(om，ok)renew Giend forend for更新集合S，Si=(Ij，fi，Gi)end forreturn S算法1中，给定视频V，确定候选视频窗口集合的所需时间为T(n)。设候选视频窗口集合的窗口数量为k，一个视频帧中平均包含的视频对象数量为m，确定候选视频窗口中符合查询条件的一组视频对象所需时间为T(kC2m)，因此，算法1的时间复杂度是O(n+km2)。通过以下示例解释多级剪枝策略的原理。假设用户查询“白色大众轿车和两个行人一起出现不少于3帧且距离小于5 m，行人在车辆前方30左右的范围”的视频片段，该查询涉及视频对象的类别、颜色、品牌三个属性。多级剪枝策略首先根据视频对象的类别数量、颜色和品牌数量，查找可能存在的视频窗口，即“car：1”“person：2”“白色：1”“大众：1”，对于不符合条件的视频窗口进行剪枝。如果视频窗口满足上述数量条件，则为候选视频窗口集合。假设图6（a）中I1被确定为候选视频窗口。下一步则需要在窗口I1对应的所有帧中，根据待查询的视频对象数、属性对视频帧进行剪枝，得到候选视频帧；假设图6（b）中f1，f3被确定为候选视频帧集合，下一步则根据视频对象的距离和相对位置等时空信息进行比对，最终找到满足条件的时空伴随模式。如图7所示，假设通过剪枝得到了编号为C1的车辆与编号为P3、P4、P5的行人符合查询条件，则将图7（b）中所示剪枝后 的 图 中 所 有 满 足 条 件 的 顶 点 序 列 构 成 集 合f1：C1，P3，P4，C1，P3，P5，C1，P4，P5。4.2基于前缀树的时空伴随模式发现算法算法2给出基于前缀树的时空伴随模式发现算法的伪代码。通过上述多级剪枝匹配算法，得到满足查询条件的对象集合S，从Si中可以获得符合条件的视频窗口Ij，窗口中符合条件的视频帧fi，以及fi对应的符合条件视频对象时空关系图Gi。为了提高查找效率，本文采用前缀树的思想来进一步挖掘符合时空查询条件的视频对象组合。对于每一帧fi，首先将图Gi中视频对象集合Oi根据时空关系要求将集合划分为有 限 数 量 符 合 查 询 条 件 的 小 集 合Omi(Oi=)Om1，Om2，Omi，Omn；之后统计Oi各集合中各视频对象出现次数，出现次数最多的元素作为前缀树根节点，在此基础上遍历集合Oi，生成前缀树；之后继续处理下一个窗口。算法2 基于前缀树的时空伴随模式发现算法。输入 一个满足条件的时空伴随模式集合Oi；输出 所有满足时空伴随模式的对象帧集合S。c为新建节点，cur为当前处理节点，root为根节点，R为根节点集合，virtual为虚拟叶节点用来存储视频对象所在帧将Gi中Oi划分成符合条件的最小集合OmiCount_Element（Omi）/*Count_Element（）函数功能是统计不同集合中相同元素出现次数*/root=Max_Element（Oi）/*Max_Element（）函数功能是获取一组集合中出现次数最多的元素*/cur=root图6符合查询条件的帧及对应窗口Fig.6Frames and corresponding windows that meet query conditions图7完全图剪枝Fig.7Complete graph pruning2334第 8 期张潇誉等：面向视频数据的时空伴随模式挖掘算法for Omi in Oi：Sort_Element（Omi）/*Sort_Element（）函数功能是对集合按照元素出现次数进行排序*/if cur not in R：root=First_Element（Omi）/*First_Element（）函数的功能是获取集合第一个元素*/cur=root将root加入集合Rfor c in Omi：if cur does not have a child c：cur.children c =new Trie node cur=cur.children c virtual(cur)=fiend forcur=nullend forif sum（virtual）符合条件：S=Reverse_DFS（virtual）/*Reverse_DFS（）函数为逆向深度搜索算法，从虚拟叶节点向根节点深度搜索*/return S算法2中，根据查询条件建立前缀树所需时间为T(n2)，设符合条件视频对象数量为m，根据虚拟叶节点查找所有满足条件的视频帧集合为深度优先搜索，所需时间为T(m)。因此，算法2的时间复杂度为O(n2+m)。通过以下示例解释基于前缀树的时空伴随模式发现算法。假设同一窗口中符合条件的集合如下：f1：C1，P3，P4，C1，P3，P5，C1，P4，P5f3：C1，P3，P5f4：C1，P3，P5，C1，P4，P5 选择出现次数最多的C1作为根节点来创建前缀树。从帧f1开始建立前缀查找树，先处理集合C1，P3，P4，C1为根节点，若无后继节点则依次处理集合中元素，使其成为新的孩子节点。第一个集合处理完，在叶节点之后的虚拟节点存储该集合所在的帧，之后继续处理f1中下一个集合C1，P3，P5，依从根节点遍历前缀树，可发现此集合中C1，P3节点已存在，不存在P5节点，因此将在P3节点后新建分支P5节点，剩余集合同理。处理完所有视频帧的集合后，形成了一棵如图8所示的前缀树。本文给每个节点添加了指向父节点的索引（图8中虚线），当需要查询符合条件的视频对象集合时，从叶节点开始，根据节点索引向上回溯，记录符合查询条件的一组视频对象以及获取符合查询条件的一组视频对象所在帧，从而得到某一帧中所有符合查询条件的视频对象集合。5 实验与结果分析 本文使用TensorFlow框架实现，该模型在一台配备Intel i5-8265U CPU、GeForce GTX 1070 GPU和8 GB RAM的机器上进行的。实验采用 YOLO（You Only Look Once）目标检测算法25和Deep SORT多目标跟踪算法14来实现对目标视频对象的检测和跟踪，对于这两种算法，利用开源项目实现。5.1实验数据集为了评估本文模型的性能，在合成数据集和真实数据集上开展了大量的实验，测试不同参数对算法性能的影响，验证算法的有效性。实验选择 MOT16（Multiple Object Tracking challenge 16）26作为真实数据集，选择使用由VisualRoad基准生成的视频27作为合成数据集。多目标跟踪数据集MOT16是在2016年提出来的用于衡量多目标跟踪检测和跟踪方法标准的数据集，常用于行人跟踪，数据集中视频以每秒25帧（fps）的速度录制，分辨率为960540 像素。Visual Road是一个评估视频数据库管理系统（Video Data Base Management Systems，VDBMS）性能的基准。Visual Road带有一个数据集生成器和一套针对位于模拟大都市环境中的摄像头的基准查询。Visual Road的视频数据自动生成，具有高度的真实性，并使用现代模拟和可视化引擎进行注释。这允许在扩大输入数据大小的同时进行 VDBMS 性能评估。实验选择 MOT16-13作为真实数据集，该视频为移动摄像头所拍摄，视频中为晴天且交通流量较大，视频长度为30 s。实验选择visualroad1作为合成数据集，该视频为固定摄像头拍摄，视频为下雨天且交通流量较小，视频长度为71 s。两视频均包含车辆和行人等视频对象。真实数据集中的道路视频如图9（a）所示；合成数据集中的视频如图9（b）所示。实验中只识别了车辆和行人，在5.2节使用M1表示使用的真实视频，V1表示合成视频。5.2结果分析实验中引入暴力搜索算法（Brute Force Algorithm，BFA）作为基准算法。在该算法中，首先统计每一帧中目标视频对象出现次数，若不满足查询条件，则对视频帧剪枝，之后根据每一帧中视频对象时空关系继续剪枝，最后得到满足条件的时空伴随模式。该算法中在整个视频的层面对符合时空查询条件的视频对象进行检索，在数据量较大的问题下性能较差。实验中默认视频帧的总长为600，改变持续时间（默认值为6）。现给定查询条件为至少有一辆车和一个人同时出现，且两者间距离不大于 200 像素，两个数据集的查询结果如图10和图11所示。图10真实数据集结果M1部分查询结果Fig.10Some query results of real dataset result M1图8线索前缀树Fig.8Clue prefix tree图9真实数据集M1片段和合成数据集V1片段Fig.9Real dataset M1 fragment and Synthetic dataset V1 fragment2335第 43 卷计算机应用首先改变数据集大小，即视频长度。如图12所示，两个方法的性能都表现出类似趋势：当帧数增加时，总时间也增加，帧数越多，MPA 性能表现更优。在图 12（a）真实数据集中，相同的帧数两方法处理时间比在图12（b）稍长，这是因为真实数据集M1中视频中每帧包含的视频对象比V1中平均每帧包含的对象多，因此实验中处理时间会更长。接下来改变窗口大小w和持续时间参数d，结果如图13和图14所示，随着窗口大小的增加，两个方法的计算时间都随之增加，总体趋势保持不变。数据集M1是由移动相机捕捉；这意味着每个物体在可见屏幕中的持续时间较小，而且新的物体被频繁地引入可视屏幕，从而导致更多的不一样的状态，耗费时间更多。相比之下，BFA由于无法处理复杂的交通流数据从而处理时间更长。改变时空关系查询条件距离和角度，实验结果如图15和图16所示，随着限定距离的扩大，两算法的所需时间都随之减少，总体趋势保持不变。角度的改变对于查询时间来说影响较小，但是MPA普遍比BFA耗时少，因为MPA算法的三重剪枝匹配策略有效减少了无效查询次数，进而提高效率。在真实数据集和合成数据集上的实验结果表明，与BFA相比，MPA效率提高30%左右，且数据量越大，效率提高越明显。6 结语 本文提出一套支持视频数据时空关系结构化查询以及伴随模式发现的算法，用于快速发现符合查询条件的伴随模式。采用已有的视频对象识别和跟踪模型，对视频中的视频对象进行结构化提取，然后对提取的视频对象建立索引结构，设计多层剪枝算法，使得能够更快发现符合查询条件的伴随模式。最后，在真实数据集和合成数据集上的实验结果表明，本文提出的算法能够快速发现海量视频数据中满足查询条件的时空伴随模式。下一步将继续研究改进伴随模式算法以及如何在跨视频数据上实现伴随模式发现，尝试解决目标视频对象集合跨视频重识别问题，从而提高时空伴随模式挖掘效率，扩大视频数据查询范围。参考文献（References）1 AWAD G，FISCUS J，JOY D，et al.TRECVID 2016：evaluating video search，video event detection，localization，and hyperlinkingC/OL/Proceedings of the 2016 TREC Video Retrieval Evaluation Workshop 2022-04-12.https：/www-nlpir.nist.gov/projects/tvpubs/tv16.papers/tv16overview.pdf.2 MARKATOPOULOU F，GALANOPOULOS D，MEZARIS V，et al.Query and keyframe representations for ad-hoc video searchC/Proceedings of the 2017 ACM International Conference on Multimedia Retrieval.New York：ACM，2017：407-411.3 LU Y J，ZHANG H，DE BOER M，et al.Event detection with zero example：select the right and suppress the wrong conceptsC/Proceedings of the 2016 ACM International Conference on Multimedia Retrieval.New York：ACM，2016：127-136.4 GORDON D，KEMBHAVI A，RASTEGARI M，et al.IQA：visual question answering in interactive environments C/Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition.Piscataway：IEEE，2018：4089-4098.5 DAS A，DATTA S，GKIOXARI G，et al.Embodied question answering C/Proceedings of the 2018 IEEE/CVF Conference on 图1