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

doi:10.11772/j.issn.1001-9081.2022101566

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (8): 2330-2337.DOI: 10.11772/j.issn.1001-9081.2022101566

• 第十九届CCF中国信息系统及应用大会 • 上一篇

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

张潇誉¹, 于自强¹^,²(), 刘承栋¹, 李博涵³, 靖常峰⁴

^1.烟台大学计算机与控制工程学院, 山东烟台 264005
^2.自然资源部城市国土资源监测与仿真重点实验室, 广东深圳 518034
^3.南京航空航天大学计算机科学与技术学院, 南京 211106
^4.中国地质大学(北京) 信息工程学院, 北京 100083

收稿日期:2022-09-26 修回日期:2022-11-08 接受日期:2022-11-11 发布日期:2023-02-14 出版日期:2023-08-10
通讯作者: 于自强
作者简介:张潇誉（1999—），女，山东枣庄人，硕士研究生，主要研究方向：视频数据处理
刘承栋（2000—），男，山东淄博人，硕士研究生，主要研究方向：视频数据结构化查询
李博涵（1979—），男，副教授，博士，CCF高级会员，主要研究方向：时空数据库、知识图谱、自然语言处理
靖常峰（1979—），男，山东济南人，教授，博士，主要研究方向：城市运行管理物联网技术、城市时空大数据建模、时空分析与挖掘。
基金资助:
国家自然科学基金资助项目(62172351)

Spatial-temporal co-occurrence pattern mining algorithm for video data

Xiaoyu ZHANG¹, Ziqiang YU¹^,²(), Chengdong LIU¹, Bohan LI³, Changfeng JING⁴

^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

Received:2022-09-26 Revised:2022-11-08 Accepted:2022-11-11 Online:2023-02-14 Published:2023-08-10
Contact: Ziqiang YU
About author:ZHANG Xiaoyu，born in 1999， M. S. candidate. Her research interests include video data processing.
LIU Chengdong， born in 2000， M. S. candidate. His research interests include structured querying of video data.
LI Bohan， born in 1979， Ph. D.， associate professor. His research interests include spatial-temporal database， knowledge graph， natural language processing.
JING Changfeng， born in 1979， Ph. D.， professor. His research interests include internet of things technology for urban operation and management， urban spatial-temporal big data modeling， spatial-temporal analysis and mining.
Supported by:
National Natural Science Foundation of China(62172351)

摘要/Abstract

摘要：

时空伴随模式是具有时空伴随关系的视频对象组合。为了从海量视频数据中快速发现符合查询条件的时空伴随模式，提出一种基于三重剪枝匹配策略的时空伴随模式发现算法——MPA。首先，利用已有的视频对象识别和跟踪模型对视频对象进行结构化提取；然后，对提取的连续帧中大量重复出现的视频对象进行压缩存储并构建索引；最后，设计基于前缀树的时空伴随模式发现算法，以快速发现符合查询条件的时空伴随模式。在真实数据集和合成数据集上的实验结果表明，与暴力搜索算法（BFA）相比，所提算法的效率提高了30%左右，且数据量越大，效率提高越明显。因此，所提算法能够快速发现海量视频数据中满足查询条件的时空伴随模式。

关键词: 视频对象, 结构化, 时空伴随模式, 索引结构, 剪枝策略

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 strategy

中图分类号:

TP391.3

张潇誉, 于自强, 刘承栋, 李博涵, 靖常峰. 面向视频数据的时空伴随模式挖掘算法[J]. 计算机应用, 2023, 43(8): 2330-2337.

Xiaoyu ZHANG, Ziqiang YU, Chengdong LIU, Bohan LI, Changfeng JING. Spatial-temporal co-occurrence pattern mining algorithm for video data[J]. Journal of Computer Applications, 2023, 43(8): 2330-2337.

图/表 16

图1 视频数据转化为结构化关系

Fig. 1 Transforming video data into structured relationships

图2 视频对象空间关系的量化表示图

Fig. 2 Quantitative representation graph of spatial relationship of video objects

图3 同一视频窗口的视频帧索引

Fig.3 Video frame index of the same video window

图4 滑动窗口的示例

Fig.4 Example of sliding window

图5 三重索引结构示意图

Fig.5 Schematic diagram of triple index structure

图6 符合查询条件的帧及对应窗口

Fig. 6 Frames and corresponding windows that meet query conditions

图7 完全图剪枝

Fig. 7 Complete graph pruning

图8 线索前缀树

Fig.8 Clue prefix tree

图9 真实数据集M1片段和合成数据集V1片段

Fig.9 Real dataset M1 fragment and Synthetic dataset V1 fragment

图10 真实数据集结果M1部分查询结果

Fig.10 Some query results of real dataset result M1

图11 合成数据集V1部分查询结果

Fig.11 Some query results of synthetic dataset V1

图12 帧数对挖掘效率的影响

Fig. 12 Influence of frame number on mining efficiency

图13 窗口大小对挖掘效率的影响

Fig. 13 Influence of window size on mining efficiency

图14 视频对象持续时间对挖掘效率的影响

Fig. 14 Influence of video object duration on mining efficiency

图15 视频对象间距离对挖掘效率的影响

Fig.15 Influence of distance between video objects on mining efficiency

图16 视频对象间角度对挖掘效率的影响

Fig.16 Influence of angle between video objects on mining efficiency

参考文献 27

1	AWAD G， FISCUS J， JOY D， et al. TRECVID 2016： evaluating video search， video event detection， localization， and hyperlinking［C/OL］// Proceedings of the 2016 TREC Video Retrieval Evaluation Workshop ［2022-04-12］..
2	MARKATOPOULOU F， GALANOPOULOS D， MEZARIS V， et al. Query and keyframe representations for ad-hoc video search［C］// Proceedings of the 2017 ACM International Conference on Multimedia Retrieval. New York： ACM， 2017： 407-411. 10.1145/3078971.3079041
3	LU Y J， ZHANG H， DE BOER M， et al. Event detection with zero example： select the right and suppress the wrong concepts［C］// Proceedings of the 2016 ACM International Conference on Multimedia Retrieval. New York： ACM， 2016： 127-136. 10.1145/2911996.2912015
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. 10.1109/cvpr.2018.00430
5	DAS A， DATTA S， GKIOXARI G， et al. Embodied question answering［C］// Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2018： 1-10. 10.1109/cvpr.2018.00008
6	陈卓，杜昊，吴雨菲，等. 基于视觉-文本关系对齐的跨模态视频片段检索［J］. 中国科学：信息科学， 2020， 50（6）： 862-876. 10.1360/ssi-2019-0292
	CHEN Z， DU H， WU Y F， et al. Cross-modal video moment retrieval based on visual-textual relationship alignment［J］. SCIENTIA SINICA Informationis， 2020， 50（6）： 862-876. 10.1360/ssi-2019-0292
7	王美珍，刘学军，孙开新，等. 最优视频子集与视频时空检索［J］. 计算机学报， 2019， 42（9）： 2004-2023. 10.11897/SP.J.1016.2019.02004
	WANG M Z， LIU X J， SUN K X， et al. Optimum video subset and spatial-temporal video retrieval［J］. Chinese Journal of Computers， 2019， 42（9）： 2004-2023. 10.11897/SP.J.1016.2019.02004
8	HOWARD A G， ZHU M L， CHEN B， et al. MobileNets： efficient convolutional neural networks for mobile vision applications［EB/OL］. （2017-04-17）［2022-03-22］.. 10.48550/arXiv.1704.04861
9	REDMON J， FARHADI A. YOLO9000： better， faster， stronger［C］// Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2017： 6517-6525. 10.1109/cvpr.2017.690
10	HSIEH K， ANANTHANARAYANAN G， BODIK P， et al. Focus： querying large video datasets with low latency and low cost［C］// Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation. Berkeley： USENIX Association， 2018： 269-286.
11	TANG S Y， ANDRILUKA M， ANDRES B， et al. Multiple people tracking by lifted multicut and person re-identification［C］// Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2017： 3701-3710. 10.1109/cvpr.2017.394
12	XU J R， CAO Y， ZHANG Z， et al. Spatial-temporal relation networks for multi-object tracking［C］// Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision. Piscataway： IEEE， 2019： 3987-3997. 10.1109/iccv.2019.00409
13	ZHOU X Y， VKOLTUN V， KRÄHENBÜHL P. Tracking objects as points［C］// Proceedings of the 2020 European Conference on Computer Vision， LNCS 12349. Cham： Springer， 2020： 474-490.
14	WOJKE N， BEWLEY A， PAULUS D. Simple online and realtime tracking with a deep association metric［C］// Proceedings of the 2017 IEEE International Conference on Image Processing. Piscataway： IEEE， 2017： 3645-3649. 10.1109/icip.2017.8296962
15	BERGMANN P， MEINHARDT T， LEAL-TAIXÉ L. Tracking without bells and whistles［C］// Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision. Piscataway： IEEE， 2019： 941-951. 10.1109/iccv.2019.00103
16	YEO C H， ZHU Y W， SUN Q B， et al. A framework for sub-window shot detection［C］// Proceedings of the 11th International Multimedia Modeling Conference. Piscataway： IEEE， 2005： 84-91.
17	彭宇新， NGO C W，董庆杰，等. 一种通过视频片段进行视频检索的方法［J］. 软件学报， 2003， 14（8）： 1409-1417.
	PENG Y X， NGO C W， DONG Q J， et al. An approach for video retrieval by video clip［J］. Journal of Software， 2003， 14（8）： 1409-1417.
18	SenGUPTA A， THOUNAOJAM D M， SINGH K M， et al. Video shot boundary detection： a review［C］// Proceedings of the 2015 IEEE International Conference on Electrical， Computer and Communication Technologies. Piscataway： IEEE， 2015： 1-6. 10.1109/icecct.2015.7226084
19	YAJIMA C， NAKANISHI Y， TANAKA K. Querying video data by spatiotemporal relationships of moving object traces［C］// Proceedings of the 2002 Working Conference on Visual Database Systems， IFIPAICT 88. New York： Springer， 2002： 357-371. 10.1007/978-0-387-35592-4_25
20	KANG D， EMMONS J， ABUZAID F， et al. NoScope： optimizing neural network queries over video at scale［J］. Proceedings of the VLDB Endowment， 2017， 10（11）： 1586-1597. 10.14778/3137628.3137664
21	KANG D， BAILIS P， ZAHARIA M. BlazeIt： fast exploratory video queries using neural networks［EB/OL］. （2018-05-02）［2022-04-20］.. 10.14778/3372716.3372725
22	KANG D， BAILIS P， ZAHARIA M. Challenges and opportunities in DNN-based video analytics： a demonstration of the BlazeIt video query engine［C/OL］// Proceedings of the 9th Biennial Conference on Innovative Data Systems Research ［2022-03-15］.. 10.14778/3372716.3372725
23	BASTANI F， HE S T， BALASINGAM A， et al. MIRIS： fast object track queries in video［C］// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2020： 1907-1921. 10.1145/3318464.3389692
24	CHEN Y T， YU X H， KOUDAS N， et al. Evaluating temporal queries over video feeds［C］// Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2021： 287-299. 10.1145/3448016.3452803
25	REDMON J， DIVVALA S， GIRSHICK R， et al. You only look once： unified， real-time object detection［C］// Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2016： 779-788. 10.1109/cvpr.2016.91
26	MILAN A， LEAL-TAIXÉ L， REID I， et al. MOT16： a benchmark for multi-object tracking［EB/OL］. （2016-05-03）［2022-03-05］..
27	HAYNES B， MAZUMDAR A， BALAZINSKA M， et al. Visual Road： a video data management benchmark［C］// Proceedings of the 2019 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2019： 972-987. 10.1145/3299869.3324955

[1]	刘耀, 童昕, 陈一风. 面向业务需求的算法路径自组配模型[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1768-1778.
[2]	杨东, 王以松. 析取回答集程序设计结构化测试方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 215-220.
[3]	华亚洲, 丁琳琳, 陈泽, 王俊陆, 朱珠. 面向时空数据的区块链构建及查询方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3429-3437.
[4]	张恩, 侯缨盈, 李功丽, 李会敏, 李钰. 基于错误学习的自适应等级可搜索加密方案[J]. 计算机应用, 2020, 40(1): 148-156.
[5]	张芳艳, 王新, 许新征. 基于结构化遮挡编码和极限学习机的局部遮挡人脸识别[J]. 计算机应用, 2019, 39(10): 2893-2898.
[6]	王新晴, 孟凡杰, 吕高旺, 任国亭. 基于PCA-SVM准则改进区域生长的非结构化道路识别[J]. 计算机应用, 2017, 37(6): 1782-1786.
[7]	王泽宇, 吴艳霞, 张国印, 布树辉. 面向RGB-D场景解析的三维空间结构化编码深度网络[J]. 计算机应用, 2017, 37(12): 3458-3466.
[8]	许国艳, 罗章璇, 宋健, 吕鑫. 基于双层索引结构的起源图查询方法[J]. 计算机应用, 2017, 37(1): 48-53.
[9]	钟艳如, 梁毅芳, 许本胜, 曾聪文, 卢宏成, 吴帆, 赵争君. 基于网络本体语言的三维计算机辅助设计主模型相似性计算方法[J]. 计算机应用, 2016, 36(6): 1599-1604.
[10]	刘超, 胡成玉, 姚宏, 梁庆中, 颜雪松. 面向海量非结构化数据的非关系型存储管理机制[J]. 计算机应用, 2016, 36(3): 670-674.
[11]	朱苏阳, 惠浩添, 钱龙华, 张民. 基于自监督学习的维基百科家庭关系抽取[J]. 计算机应用, 2015, 35(4): 1013-1016.
[12]	国冰磊, 于炯, 廖彬, 杨德先. 结构化查询语言动态功耗解析及建模[J]. 计算机应用, 2015, 35(12): 3362-3367.
[13]	刘慧婷, 沈盛霞, 赵鹏, 姚晟. 不确定数据频繁闭项集挖掘算法[J]. 计算机应用, 2015, 35(10): 2911-2914.
[14]	李新叶, 孙智华, 陈明宇. 基于二值特征和结构化输出支持向量机的目标快速跟踪算法[J]. 计算机应用, 2015, 35(10): 2980-2984.
[15]	王畅谢永华袁复兴. 基于结构化粒子模型的云可视化应用[J]. 计算机应用, 2013, 33(11): 2013-01.

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

Spatial-temporal co-occurrence pattern mining algorithm for video data

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 27

相关文章 15

编辑推荐

Metrics