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

doi:10.11772/j.issn.1001-9081.2022101566

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (8): 2330-2337.DOI: 10.11772/j.issn.1001-9081.2022101566

• The 19th International Conference on Web Information Systems and Applications (WISA 2022) • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP391.3

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.

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

Figures/Tables 16

Fig. 1 Transforming video data into structured relationships

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

Fig.3 Video frame index of the same video window

Fig.4 Example of sliding window

Fig.5 Schematic diagram of triple index structure

Fig. 6 Frames and corresponding windows that meet query conditions

Fig. 7 Complete graph pruning

Fig.8 Clue prefix tree

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

Fig.10 Some query results of real dataset result M1

Fig.11 Some query results of synthetic dataset V1

Fig. 12 Influence of frame number on mining efficiency

Fig. 13 Influence of window size on mining efficiency

Fig. 14 Influence of video object duration on mining efficiency

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

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

References 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]	Jianwen GAN, Yan CHEN, Peng ZHOU, Liang DU. Clustering ensemble algorithm with high-order consistency learning [J]. Journal of Computer Applications, 2023, 43(9): 2665-2672.
[2]	Xiao LYU, Huihui SONG, Jiaqing FAN. Semi-supervised video object segmentation via deep and shallow representations fusion [J]. Journal of Computer Applications, 2022, 42(12): 3884-3890.
[3]	Yazhou HUA, Linlin DING, Ze CHEN, Junlu WANG, Zhu ZHU. Blockchain construction and query method for spatio‑temporal data [J]. Journal of Computer Applications, 2022, 42(11): 3429-3437.
[4]	ZHANG En, HOU Yingying, LI Gongli, LI Huimin, LI Yu. Adaptive hierarchical searchable encryption scheme based on learning with errors [J]. Journal of Computer Applications, 2020, 40(1): 148-156.
[5]	JIANG Sihao, SONG Huihui, ZHANG Kaihua, TANG Runfa. Video object segmentation method based on dual pyramid network [J]. Journal of Computer Applications, 2019, 39(8): 2242-2246.
[6]	ZHANG Haiqing, LI Daiwei, LIU Yintian, GONG Cheng, YU Xi. Mining algorithm of maximal fuzzy frequent patterns [J]. Journal of Computer Applications, 2017, 37(5): 1424-1429.
[7]	XU Guoyan, LUO Zhangxuan, SONG Jian, LYU Xin. Provenance graph query method based on double layer index structure [J]. Journal of Computer Applications, 2017, 37(1): 48-53.
[8]	LIU Huiting, SHEN Shengxia, ZHAO Peng, YAO Sheng. Frequent closed itemset mining algorithm over uncertain data [J]. Journal of Computer Applications, 2015, 35(10): 2911-2914.
[9]	FANG Junhua WANG Hanhu CHEN Mei MA Dan. Index structure with self-adaptive mechanism in flash-based database system [J]. Journal of Computer Applications, 2013, 33(02): 563-566.
[10]	Ma Li-sheng YAO Guang-shun YANG Chuan-jian. Mining algorithm for maximal frequent itemsets based on improved FP-tree [J]. Journal of Computer Applications, 2012, 32(02): 326-329.
[11]	. Moving object segmentation algorithm for river surveillance video [J]. Journal of Computer Applications, 2011, 31(01): 263-265.
[12]	. Improvement for lower store structure of Hypertable system [J]. Journal of Computer Applications, 2009, 29(06): 1748-1750.
[13]	Guo-qiang Xiao . Kalman filtering for tracking video objects based on motion estimation [J]. Journal of Computer Applications, 2008, 28(8): 2052-2054.
[14]	. Tracking video object based on regional-centroid and vector-direction [J]. Journal of Computer Applications, 2007, 27(6): 1502-1504.
[15]	REN Jian-feng,GUO Lei,SHEN Yu-li. Motion segmentation based on multi-model robust estimation [J]. Journal of Computer Applications, 2005, 25(04): 778-780.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 27

Related Articles 15

Recommended Articles

Metrics