留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种室内人群时空聚集区域识别方法

王培晓 吴升 张恒才 陆锋 王宏恩

王培晓, 吴升, 张恒才, 陆锋, 王宏恩. 一种室内人群时空聚集区域识别方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 790-798. doi: 10.13203/j.whugis20190228
引用本文: 王培晓, 吴升, 张恒才, 陆锋, 王宏恩. 一种室内人群时空聚集区域识别方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 790-798. doi: 10.13203/j.whugis20190228
WANG Peixiao, WU Sheng, ZHANG Hengcai, LU Feng, WANG Hong'en. A Method for Identifying Spatial and Temporal Aggregation Area of Indoor Crowd[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 790-798. doi: 10.13203/j.whugis20190228
Citation: WANG Peixiao, WU Sheng, ZHANG Hengcai, LU Feng, WANG Hong'en. A Method for Identifying Spatial and Temporal Aggregation Area of Indoor Crowd[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 790-798. doi: 10.13203/j.whugis20190228

一种室内人群时空聚集区域识别方法

doi: 10.13203/j.whugis20190228
基金项目: 

国家自然科学基金 41771436

国家自然科学基金 41701521

国家自然科学基金 41771476

国家重点研发计划 2016YFB0502104

国家重点研发计划 2017YFB0503500

数字福建建设项目 [2016]23

详细信息
    作者简介:

    王培晓, 硕士生, 研究方向为地理信息服务与时空数据挖掘。peixiaowang@whu.edu.cn

    通讯作者: 张恒才, 博士, 助理研究员. E-mail: zhanghc@lreis.ac.cn
  • 中图分类号: P208

A Method for Identifying Spatial and Temporal Aggregation Area of Indoor Crowd

Funds: 

The National Natural Science Foundation of China 41771436

The National Natural Science Foundation of China 41701521

The National Natural Science Foundation of China 41771476

the National Key Research and Development Program of China 2016YFB0502104

the National Key Research and Development Program of China 2017YFB0503500

Digital Fujian Program [2016]23

More Information
    Author Bio:

    WANG Peixiao, postgraduate, specializes in geographic information services and spatiotemporal data mining. E-mail: peixiaowang@whu.edu.cn

    Corresponding author: ZHANG Hengcai, PhD, assistant professor. E-mail: zhanghc@lreis.ac.cn
  • 摘要: 现有的人群聚集区域识别算法主要集中于室外空间,与室外空间相比,室内三维空间结构复杂,室内人群聚集更易导致安全事故的产生。提出了一种室内人群聚集区域识别方法——室内简化重构聚集方法(indoor simplification reconstruction cluster,IndoorSRC)。首先,设计了一种新型的室内时空凝聚层次聚类算法(indoor spatial-temporal agglomerative nesting, Indoor-STAGNES)识别室内用户停留点,简化室内用户移动轨迹;然后,构建了一种基于卡尔曼滤波的室内轨迹重构方法,实现了室内用户轨迹的对齐与重采样;最后,提出了一种室内时空密度聚类算法(indoor spatial-temporal ordering points to identify the clustering structure,Indoor-STOPTICS)发现室内三维时空人群聚集区域。采用真实室内轨迹数据进行实验分析,结果表明,与传统的室外识别方法相比,在运行时间差别不大的情况下,IndoorSRC识别的误识率可降低23.7%。
  • 图  1  相关定义

    Figure  1.  Related Definitions

    图  2  Indoor-STAGNES算法简化室内移动轨迹

    Figure  2.  Indoor Trajectory Simplification with Indoor-STAGNES

    图  3  包含缺失轨迹点的简化轨迹

    Figure  3.  Simplified Trajectory Containing Missing Points

    图  4  时空邻域

    Figure  4.  Spatiotemporal Neighborhood

    图  5  时空数据集及其增广簇排序图

    Figure  5.  Spatiotemporal Dataset and Illustration of the Cluster-Ordering

    图  6  室内人群聚集区域识别结果

    Figure  6.  Indoor Crowd Gathering Area Identification Results

    图  7  ST-OPTICS算法识别结果

    Figure  7.  Recognition Result of ST-OPTICS Algorithm

    图  8  IndoorSRC和ST-OPTICS定量对比结果

    Figure  8.  Quantitative Comparison of IndoorSRC and ST-OPTICS

    表  1  室内用户移动轨迹实例

    Table  1.   Indoor User Trajectory Sample

    用户ID 上传时间 X/m Y/m 楼层ID
    8026BC4*** 2017-12-31T10:00:01 130219*** 43903*** 2
    8026BC4*** 2017-12-31T10:00:03 130219*** 43903*** 2
    8026BC4*** 2017-12-31T10:00:04 130219*** 43903*** 2
    8026BC4*** 2017-12-31T14:59:54 130219*** 43903*** 4
    下载: 导出CSV

    表  2  室内人群聚集区域位置时间特征

    Table  2.   Indoor Crowd Gathering Area Location and Time Characteristics

    聚集区域 聚集位置 聚集时间
    聚集区域1 食尚家 11:31:15―11:56:23
    聚集区域2 食尚家 12:07:24―12:34:09
    聚集区域3 中餐厅 12:16:17―13:32:48
    聚集区域4 渔家灯火 12:20:03―13:24:38
    聚集区域5 食尚家 14:14:13―14:17:29
    下载: 导出CSV
  • [1] Klepeis N E, Nelson W C, Ott W R, et al. The National Human Activity Pattern Survey (NHAPS): A Resource for Assessing Exposure to Environmental Pollutants[J]. Journal of Exposure Analysis and Environmental Epidemiology, 2001, 11(3): 231-252 doi:  10.1038/sj.jea.7500165
    [2] 周成虎. 全空间地理信息系统展望[J]. 地理科学进展, 2015, 34(2): 129-131 https://www.cnki.com.cn/Article/CJFDTOTAL-DLKJ201502001.htm

    Zhou Chenghu. Prospects on Pan-Spatial Information System[J]. Progress in Geography, 2015, 34(2): 129-131 https://www.cnki.com.cn/Article/CJFDTOTAL-DLKJ201502001.htm
    [3] 武恩超, 张恒才, 吴升. 基于中轴变换算法的室内外一体化导航路网自动生成方法[J]. 地球信息科学学报, 2018, 20(6): 730-737 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX201806004.htm

    Wu Enchao, Zhang Hengcai, Wu Sheng. Automatic Generation Method of Indoor and Outdoor Integrated Navigation Network Based on Medial Axis Transform Algorithm[J]. Journal of Geo-Information Science, 2018, 20(6): 730-737 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX201806004.htm
    [4] 任常兴, 吴宗之, 刘茂. 城市公共场所人群拥挤踩踏事故分析[J]. 中国安全科学学报, 2005, 15(12): 102-107 doi:  10.3969/j.issn.1003-3033.2005.12.024

    Ren Changxing, Wu Zongzhi, Liu Mao. Analysis of Accident Due to Swarm and Jostlement at Urban Public Place[J]. China Safety Science Journal, 2005, 15(12): 102-107 doi:  10.3969/j.issn.1003-3033.2005.12.024
    [5] 张青松, 刘金兰, 赵国敏. 大型公共场所人群拥挤踩踏事故机理初探[J]. 自然灾害学报, 2009, 18(6): 81-86 https://www.cnki.com.cn/Article/CJFDTOTAL-ZRZH200906014.htm

    Zhang Qingsong, Liu Jinlan, Zhao Guomin. Discussion on Cause Mechanism of Crowd Crushing and Trampling Accident in Large-Scale Public Places[J]. Journal of Natural Disasters, 2009, 18(6): 81-86 https://www.cnki.com.cn/Article/CJFDTOTAL-ZRZH200906014.htm
    [6] Wang P, Wu S, Zhang H, et al. Indoor Location Prediction Method for Shopping Malls Based on Location Sequence Similarity[J]. ISPRS International Journal of Geo-Information, 2019, 8(11): 1-17 http://www.researchgate.net/publication/337303110_Indoor_Location_Prediction_Method_for_Shopping_Malls_Based_on_Location_Sequence_Similarity
    [7] Wang P, Wang H, Zhang H, et al. A Hybrid Markov and LSTM Model for Indoor Location Prediction[J]. IEEE Access, 2019, 7(1): 185 928-185 940 http://ieeexplore.ieee.org/document/8938733/
    [8] Park J K, Woo T G, Kim M, et al. Hadamard Matrix Design for a Low-Cost Indoor Positioning System in Visible Light Communication[J]. IEEE Photonics Journal, 2017, 9(2): 1-10 http://ieeexplore.ieee.org/document/7849219/
    [9] Ayong Y, Jianfei S, Li X, et al. Local HMM for Indoor Positioning Based on Fingerprinting and Displacement Ranging[J]. IET Communications, 2018, 12(10): 1 163-1 170 doi:  10.1049/iet-com.2017.1055
    [10] Simon T, Dejan D, Igor S. Confidence-Interval Fuzzy Model-Based Indoor Localization[J]. IEEE Transactions on Industrial Electronics, 2019, 66(3): 2 015 - 2 024 doi:  10.1109/TIE.2018.2840525
    [11] Guo S, Xiong H, Zheng X, et al. Activity Recognition and Semantic Description for Indoor Mobile Localization[J]. Sensors, 2017, 17(3): 1-24 doi:  10.1109/JSEN.2016.2643838
    [12] Liu Y, Cheng D, Pei T, et al. Inferring Gender and Age of Customers in Shopping Malls Via Indoor Positioning Data[J]. Environment and Planning B: Urban Analytics and City Science, 2020, 47(9): 1 672-1 689 doi:  10.1177/2399808319841910
    [13] 王培晓, 王海波, 傅梦颖, 等. 室内用户语义位置预测研究[J]. 地球信息科学学报, 2018, 20(12): 1 689-1 698 doi:  10.12082/dqxxkx.2018.180411

    Wang Peixiao, Wang Haibo, Fu Mengying, et al. Research on Semantic Location Prediction of Indoor Users[J]. Journal of Geo-Information Science, 2018, 20(12): 1 689-1 698 doi:  10.12082/dqxxkx.2018.180411
    [14] Li H, Lu H, Shou L, et al. In Search of Indoor Dense Regions: An Approach Using Indoor Positioning Data[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30: 1 481-1 495 doi:  10.1109/TKDE.2018.2799215
    [15] 杨喜平, 方志祥, 赵志远, 等. 顾及手机基站分布的核密度估计城市人群时空停留分布[J]. 武汉大学学报∙信息科学版, 2017, 42(1): 49-55 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201701008.htm

    Yang Xiping, Fang Zhixiang, Zhao Zhiyuan, et al. Analyzing Space-Time Variation of Urban Human Stay Using Kernel Density Estimation by Considering Spatial Distribution of Mobile Phone Towers[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 49-55 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201701008.htm
    [16] Li X, Han J, Lee J G, et al. Traffic Density-Based Discovery of Hot Routes in Road Networks: International Symposium on Spatial and Temporal Databases[C]. Berlin, Heidelberg: Springer, 2007
    [17] Chui C K, Chen G. Kalman Filtering with Real-Time Applications[J]. Applied Optics, 1987, 28(3): 217-228 http://www.ams.org/mathscinet-getitem?mr=918140
    [18] Zheng Y, Zhou X. Computing with Spatial Trajectories[M]. New York: Springer, 2011
    [19] Ankerst M M, Breunig M, Kriegel H P, et al. OPTICS: Ordering Points to Identify the Clustering Structure[J]. Sigmod Record, 1999, 28: 49-60
    [20] Agrawal K P, Garg S, Sharma S, et al. Development and Validation of OPTICS Based Spatiotemporal Clustering Technique[J]. Information Sciences, 2016, 369: 388-401 http://www.sciencedirect.com/science/article/pii/S0020025516304765
  • [1] 肖元弼, 彭认灿, 暴景阳, 董箭, 吕程.  利用卡尔曼滤波改正多波束数据声速整体误差 . 武汉大学学报 ● 信息科学版, 2020, 45(9): 1461-1468. doi: 10.13203/j.whugis20180261
    [2] 郭士荦, 吴苗, 许江宁, 李京书.  自适应渐消卡尔曼滤波及其在SINS初始对准中的应用 . 武汉大学学报 ● 信息科学版, 2018, 43(11): 1667-1672, 1680. doi: 10.13203/j.whugis20160548
    [3] 李永明, 归庆明, 顾勇为, 韩松辉.  有偏卡尔曼滤波及其算法 . 武汉大学学报 ● 信息科学版, 2016, 41(7): 946-951. doi: 10.13203/j.whugis20140072
    [4] 张炳先, 王密, 潘俊.  基于卡尔曼滤波的光学遥感影像高精度复原处理 . 武汉大学学报 ● 信息科学版, 2015, 40(7): 964-970. doi: 10.13203/j.whugis20130123
    [5] 柴华, 王勇, 许大欣, 王虎彪.  地固系下四元数和卡尔曼滤波方法的惯导初始精对准研究 . 武汉大学学报 ● 信息科学版, 2012, 37(1): 68-72.
    [6] 乐洋, 何秀凤.  具有区间隶属函数的模糊卡尔曼滤波在组合导航系统中的应用 . 武汉大学学报 ● 信息科学版, 2011, 36(4): 450-452.
    [7] 陆付民, 王尚庆, 李劲, 严学清.  顾及地下水位因子的卡尔曼滤波模型在滑坡变形预测中的应用 . 武汉大学学报 ● 信息科学版, 2010, 35(10): 1184-1187.
    [8] 高书亮, 李锐, 黄智刚.  利用卡尔曼滤波估计导航信号电离层差分改正 . 武汉大学学报 ● 信息科学版, 2010, 35(9): 1021-1023.
    [9] 刘繁明, 钱东, 郭静.  卡尔曼滤波地形反演算法的系统方程建模 . 武汉大学学报 ● 信息科学版, 2010, 35(10): 1179-1183.
    [10] 刘国林, 郝华东, 陶秋香.  卡尔曼滤波相位解缠及其与其他方法的对比分析 . 武汉大学学报 ● 信息科学版, 2010, 35(10): 1174-1178.
    [11] 吴江飞, 黄珹.  非线性自适应抗差滤波定轨算法 . 武汉大学学报 ● 信息科学版, 2008, 33(2): 187-190.
    [12] 赵长胜, 陶本藻.  有色噪声作用下的卡尔曼滤波 . 武汉大学学报 ● 信息科学版, 2008, 33(2): 180-182.
    [13] 孙红星, 付建红, 袁修孝, 唐卫明.  基于多历元递推最小二乘卡尔曼滤波方法的模糊度解算 . 武汉大学学报 ● 信息科学版, 2008, 33(7): 735-739.
    [14] 赵长胜, 陶本藻.  有色噪声作用下的抗差卡尔曼滤波 . 武汉大学学报 ● 信息科学版, 2007, 32(10): 880-882.
    [15] 梅天灿, 李德仁, 秦前清.  基于直线和区域特征的遥感影像线状目标检测 . 武汉大学学报 ● 信息科学版, 2005, 30(8): 689-693.
    [16] 孙红星, 李德仁.  非线性系统中卡尔曼滤波的一种新线性化方法 . 武汉大学学报 ● 信息科学版, 2004, 29(4): 346-348,358.
    [17] 郭杭.  迭代扩展卡尔曼滤波用于实时GPS数据处理 . 武汉大学学报 ● 信息科学版, 1999, 24(2): 112-114,123.
    [18] 柳响林, 刘经南, 杜道生.  卡尔曼滤波可靠性分析及其在动态GPS定位中的应用 . 武汉大学学报 ● 信息科学版, 1997, 22(3): 234-236,244.
    [19] 邵建平, 沈鹤鸣, 宋光普.  抗SA影响的卡尔曼滤波技术 . 武汉大学学报 ● 信息科学版, 1994, 19(3): 274-279.
    [20] 冯延明.  监测水准网的滤波方法 . 武汉大学学报 ● 信息科学版, 1987, 12(1): 14-25.
  • 加载中
图(8) / 表(2)
计量
  • 文章访问数:  487
  • HTML全文浏览量:  124
  • PDF下载量:  74
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-06-04
  • 刊出日期:  2021-05-05

一种室内人群时空聚集区域识别方法

doi: 10.13203/j.whugis20190228
    基金项目:

    国家自然科学基金 41771436

    国家自然科学基金 41701521

    国家自然科学基金 41771476

    国家重点研发计划 2016YFB0502104

    国家重点研发计划 2017YFB0503500

    数字福建建设项目 [2016]23

    作者简介:

    王培晓, 硕士生, 研究方向为地理信息服务与时空数据挖掘。peixiaowang@whu.edu.cn

    通讯作者: 张恒才, 博士, 助理研究员. E-mail: zhanghc@lreis.ac.cn
  • 中图分类号: P208

摘要: 现有的人群聚集区域识别算法主要集中于室外空间,与室外空间相比,室内三维空间结构复杂,室内人群聚集更易导致安全事故的产生。提出了一种室内人群聚集区域识别方法——室内简化重构聚集方法(indoor simplification reconstruction cluster,IndoorSRC)。首先,设计了一种新型的室内时空凝聚层次聚类算法(indoor spatial-temporal agglomerative nesting, Indoor-STAGNES)识别室内用户停留点,简化室内用户移动轨迹;然后,构建了一种基于卡尔曼滤波的室内轨迹重构方法,实现了室内用户轨迹的对齐与重采样;最后,提出了一种室内时空密度聚类算法(indoor spatial-temporal ordering points to identify the clustering structure,Indoor-STOPTICS)发现室内三维时空人群聚集区域。采用真实室内轨迹数据进行实验分析,结果表明,与传统的室外识别方法相比,在运行时间差别不大的情况下,IndoorSRC识别的误识率可降低23.7%。

English Abstract

王培晓, 吴升, 张恒才, 陆锋, 王宏恩. 一种室内人群时空聚集区域识别方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 790-798. doi: 10.13203/j.whugis20190228
引用本文: 王培晓, 吴升, 张恒才, 陆锋, 王宏恩. 一种室内人群时空聚集区域识别方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 790-798. doi: 10.13203/j.whugis20190228
WANG Peixiao, WU Sheng, ZHANG Hengcai, LU Feng, WANG Hong'en. A Method for Identifying Spatial and Temporal Aggregation Area of Indoor Crowd[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 790-798. doi: 10.13203/j.whugis20190228
Citation: WANG Peixiao, WU Sheng, ZHANG Hengcai, LU Feng, WANG Hong'en. A Method for Identifying Spatial and Temporal Aggregation Area of Indoor Crowd[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 790-798. doi: 10.13203/j.whugis20190228
  • 室内空间是人类活动的主要空间,据统计,人类约有87%的时间都在室内空间移动[1-2]。人群聚集是室内外应急安全事故的主要诱因之一,也是室内外安全监控的重点任务。与室外空间相比,室内三维空间结构更复杂[3],人群聚集程度较高,较易发生拥挤、踩踏等安全事故。及时、快速、准确地识别室内空间的人群聚集区域对室内安全事故的提前预警与应急救援都具有重要意义[4-5]

    近年来,随着室内定位技术不断发展,室内位置服务不断增多,移动终端设备不断普及,室内移动用户的轨迹数据呈爆发式增长,为室内相关研究提供了重要的数据源[6-8],如文献[9-10]分别在传统指纹定位的基础上建立了隐式马尔科夫模型与置信区间模糊模型提高室内行人的定位精度;文献[11]结合室内用户轨迹及室内地标推断室内位置的语义信息;文献[12]利用室内WiFi定位数据推断用户的性别和年龄;文献[13]利用室内蓝牙定位数据预测用户下一时刻的位置;文献[14]提出了一种数据驱动的方法寻找室内密集区域。上述与室内有关的研究主要集中于室内位置服务,并未识别室内人群聚集区域。目前,与人群聚集区域识别相关的研究主要集中于室外空间。例如文献[15]使用手机定位数据根据网格聚类探索室外人群聚集与消散模式;文献[16]利用GPS定位数据提出了一种基于密度的聚类算法识别路网级别的人群聚集区域,从而缓解交通拥堵现象。目前,现有的人群聚集区域识别算法集中于室外,相较于室外移动轨迹,室内移动轨迹存在质量差、易缺失、易停留等特点,传统的室外人群聚集区域识别算法难以发现室内人群聚集区域。例如,室内轨迹易缺失的特点将导致一个较大的室内人群聚集区域分裂为若干小区域,从而忽略了某些潜在的人群密集位置;室内轨迹易停留的特点将导致室内用户经常在某个特定区域产生较多轨迹点,从而形成"点聚集"而非"人聚集"区域,这在一定程度上降低了室内人群聚集区域识别的准确率。

    本文提出了一种新的室内人群聚集区域识别方法——室内简化重构聚集方法(indoor simplification reconstruction cluster,IndoorSRC)。该方法主要由3部分组成:室内移动轨迹简化、室内移动轨迹重构及室内人群聚集区域识别。其中,在室内移动轨迹简化阶段,本文提出了一种新的室内轨迹简化算法(indoor spatialtemporal agglomerative nesting,Indoor-STAGNES);在室内移动轨迹重构,卡尔曼滤波算法[20-21]被用于简化轨迹的对齐与重采样;在室内人群聚集区域识别阶段,本文提出了一种新的室内时空密度聚类算法(indoor spatialtemporal ordering points to identify the clustering structure,Indoor-STOPTICS)。

    • 室内人群聚集区域识别流程分为4个部分:(1)室内移动轨迹预处理,去除原始轨迹中异常、错误、无效的数据;(2)室内行人轨迹简化,提出Indoor-STAGNES算法简化室内用户移动轨迹,去除室内用户移动的停留信息;(3)室内行人轨迹重构,根据室内轨迹采样间隔信息及卡尔曼滤波算法重构室内用户,简化轨迹点;(4)室内人群聚集区域提取,提出Indoor-STOPTICS算法为重构轨迹点生成增广簇排序图,依据增广簇排序图辅助提取室内人群高密度区域。相关定义见图 1

      图  1  相关定义

      Figure 1.  Related Definitions

      定义 1  原始轨迹点p=<uidtxyf>,p是移动终端采集的记录信息,uid是用户唯一标识,t代表记录信息采集的时间,(xy)代表该用户在t时刻的坐标信息,f表示该用户在t时刻所处楼层。

      定义 2  原始轨迹T={pi}i=1nT为某用户按时间顺序连接的原始轨迹点序列(见图 1(b)),n为某用户原始轨迹点记录个数。

      定义 3  简化轨迹点psim,若干时间连续且位置移动较小的待简化轨迹点团簇经简化得到psim=<uidtsimxsimysimf>,如图 1(c)所示,tsim为待简化团簇平均记录时间,(xsimysimf)代表简化团簇的位置,(xsimysim)为待简化团簇的中心坐标,f为待简化团簇所在楼层。

      定义 4  简化轨迹Tsim={pisim}i=1kTsim为某用户按时间顺序连接的简化轨迹点序列,k为某用户简化轨迹点记录个数。

      定义 5  重构轨迹点prec=<uidt,$\hat x$,ŷf>,简化轨迹点经重构后得到重构轨迹点prec,如图 1(d)所示,t表示重构轨迹点prec的记录时间,($\hat x$,ŷ) 表示该用户在t时刻重构后的坐标信息,f表示该用户在t时刻所处楼层。

      定义 6  重构轨迹Trec={pirec}i=1mTrec为某用户按时间顺序连接的重构轨迹点序列,m为某用户重构轨迹点记录个数。

      定义 7  重构轨迹点集合D={pirec}i=1ND为用于识别室内人群聚集区域的所有轨迹点组成的集合,N为群体用户所有重构轨迹点的个数。

    • 室内定位轨迹时间间隔存在不均质特性,尤其是当移动目标在特定地方停留一定时间时,将导致移动终端在有限区域内记录较多的轨迹点,从而形成轨迹点簇团,若直接使用原始轨迹识别人群聚集区域,往往得到轨迹点聚集区域而非人群聚集区域。因此,本文提出Indoor-STAGNES算法对用户轨迹进行简化,去除轨迹点停留信息。Indoor-STAGNES算法是传统凝聚层次聚类(agglomerative nesting,AGNES)算法的改进算法。该算法在AGNES算法的基础上引入了时间窗口Δt及楼层约束,通过迭代的方式不断把同楼层时空邻近的轨迹点(簇集)合并,最终将原始轨迹T={pi}i=1n划分为k个不相交顺序簇集{C1C2Ck},簇集Ci内的原始轨迹点集经简化得到pisimk个簇集得到k个简化轨迹点,即Tsim={pisim}i=1k,其中kn。如图 2所示,簇集Ci(p1p2p3p4)迭代为一个簇集,最终将简化为一个简化轨迹点pisim,迭代过程中簇集之间空间距离的计算公式为:

      $$ \begin{array}{l} {f_{{\rm{spatial}}\_{\rm{dist}}}}\left( {{C_i}, {C_j}} \right) = {\left\| {\overline {{p_i}} - \overline {{p_j}} } \right\|_2}, \overline {{p_i}} = \\ \;\;\;\;\;\;\;\;\;\;\;\frac{1}{{{\rm{card}}\left( {{C_i}} \right)}}\mathop \sum \limits_{{p_i} \in {C_i}} {p_i} \end{array} $$ (1)

      图  2  Indoor-STAGNES算法简化室内移动轨迹

      Figure 2.  Indoor Trajectory Simplification with Indoor-STAGNES

      式中,fspatial_dist函数计算簇集CiCj的空间距离;card(Ci)表示簇集Ci包含的轨迹点个数;pipj表示簇集CiCj的均值坐标。

      簇集CiCj的时间距离计算公式为:

      $$ \begin{array}{l} {f_{{\rm{time}}\_{\rm{dist}}}}\left( {{C_i}, {C_j}} \right) = \left| {{C_i}.{t_{{\rm{ave}}}} - {C_j}.{t_{{\rm{ave}}}}} \right|, {C_i}.{t_{{\rm{ave}}}} = \\ \;\;\;\;\;\;\;\;\;\;\frac{1}{{{\rm{card}}\left( {{C_i}} \right)}}\mathop \sum \limits_{{p_i} \in {C_i}} {p_i}.t \end{array} $$ (2)

      式中,ftime_dist函数计算簇集CiCj的时间距离;Ci.taveCj.tave分别表示簇集CiCj中轨迹点的平均记录时间。

      Indoor-STAGNES算法的具体流程如下:

      1) 输入时间连续的室内用户轨迹T= {pi}i=1n,并将每一个轨迹点初始化为一个簇集。

      初始化簇集之间的空间距离矩阵MS及时间距离矩阵MTMijS表示簇集Ci和簇集Cj之间的空间距离,MijT表示簇集Ci和簇集Cj之间的时间距离,若CiCj不属于同一个楼层,则MijSMijT为无穷大。

      3)寻找时间约束Δt下距离矩阵MS中的最小值dmin,如果dmin小于距离阈值dthreh,则将最近两个簇集合并,同时更新空间距离矩阵MS与时间距离矩阵MT,再次寻找dmin;如果dmin大于距离阈值dthreh,则得到最终的簇集,跳转至步骤4)。

      4)按照时间顺序依次将簇集{C1C2Ck}简化为{p1simp2simpksim}。

    • 经简化的轨迹Tsim大体反映了用户的移动骨架,但仍不适合识别室内人群聚集区域。简化轨迹Tsim中包含较多的缺失轨迹点,若直接采用简化轨迹Tsim识别室内人群聚集区域,在一定程度上将会影响室内人群聚集区域识别的准确率。因此,室内移动轨迹重构是室内人群聚集区域识别的重要环节之一。为补齐简化轨迹中缺失的轨迹点,本文采用卡尔曼滤波算法重构室内用户简化轨迹。卡尔曼滤波是一种线性最优估计算法,综合考虑测量数据与物理运动模型,通过迭代的方式依次估计某用户每一个时刻的最优位置,即重构轨迹点prec。使用卡尔曼滤波算法重构室内移动轨迹主要分为如下两个阶段:

      1) 缺失轨迹点确定。依据简化轨迹Tsim的采样间隔确定简化轨迹中缺失轨迹点位置及个数,如图 3所示,将简化轨迹Tsim上相邻轨迹点采样间隔超两倍平均采样间隔的轨迹区间视为存在缺失轨迹区间,当缺失轨迹区间采样间隔小于采样间隔第95百分位数时,缺失轨迹点需补齐。缺失轨迹点个数与时间信息的计算公式为:

      $$ c = f\left( {\frac{{{m_{{\rm{interval}}}}}}{{{a_{{\rm{interval}}}}}}} \right) + 1 $$ (3)
      $$ p_{i + j}^{{\rm{rec}}}.t = p_i^{{\rm{rec}}}.t + j{a_{{\rm{interval}}}}, 1 \le j \le c $$ (4)

      图  3  包含缺失轨迹点的简化轨迹

      Figure 3.  Simplified Trajectory Containing Missing Points

      式中,c表示缺失轨迹点个数;minterval表示缺失轨迹区间的采样间隔;ainterval表示简化轨迹点的平均采样间隔;f(x)表示向下取整函数;pi+jrec.t表示缺失区间第j个缺失轨迹点的时间信息,如pi+1rec.t表示该缺失区间第1个缺失轨迹点的时间信息。

      2) 迭代重构移动轨迹。采用卡尔曼滤波算法迭代求解每一时刻的重构轨迹点的位置,主要分为位置预测与位置更新两个阶段:在位置预测阶段,依据上一时刻的最优位置采用物理运动模型预测下一时刻的预测位置;在位置更新阶段,利用当前时刻的测量数据及误差修正当前时刻的预测位置得到当前时刻的最优位置,最优位置即为当前时刻重构轨迹点的位置。

    • 经重构后的重构轨迹点prec较精确地反映了用户位置随时间的移动,将所有用户的重构轨迹点prec组合在一起即可分析室内群体用户位置随时间的变化,从而识别室内人群聚集区域。本文将重构轨迹点集合D(定义7)中的高密度区域视为室内人群聚集区域,为此提出了基于密度的室内时空聚类算法Indoor-STOPTICS。

      定义 8  时空邻域,对于重构轨迹点pirecD,其时空邻域表示以pirec为中心,以ε1为空间半径、以ε2为时间窗口所围成的圆柱体,如图 4所示,Nε1ε2(pirec)为圆柱体内部所包含的轨迹点子集合,计算公式为:

      $$ \begin{array}{*{20}{l}} {{N_{{\varepsilon _1}, {\varepsilon _2}}}\left( {p_i^{{\rm{rec}}}} \right) = \{ \left. {p_j^{{\rm{rec}}} \in D} \right|{s_d}\left( {p_j^{{\rm{rec}}}, p_i^{{\rm{rec}}}} \right) \le {\varepsilon _1}}\\ {\;\;\;\;\;且\;{t_d}\left( {p_j^{{\rm{rec}}}, p_i^{{\rm{rec}}}} \right) \le {\varepsilon _2}且\;p_j^{{\rm{rec}}} \cdot f = = p_i^{{\rm{rec}}} \cdot f\} } \end{array} $$ (5)

      图  4  时空邻域

      Figure 4.  Spatiotemporal Neighborhood

      式中,sd用于度量两轨迹点的空间距离;td用于度量两轨迹点的时间距离;ε1为空间半径阈值;ε2为时间窗口阈值。轨迹点子集合个数记为|Nε1ε2(pirec)|。

      Indoor-STOPTICS算法是时空密度聚类(spatial-temporal ordering points to identify the clustering structure,ST-OPTICS)[19-20]算法的改进算法,由于室内轨迹具有三维特性,Indoor-STOPTICS算法在ST-OPTICS的基础上添加了楼层约束(定义8)。该算法用于寻找时空约束下同楼层最大密度相连的轨迹点集合。与传统基于密度的时空聚类算法不同,Indoor-STOPTICS算法并不显式地生成数据聚类,而是为聚类分析生成一个有序的对象列表,辅助识别集合D中的高密度区域(室内人群聚集区域)。Indoor-STOPTICS算法的具体流程如下:

      1) 输入重构轨迹点集合D={pirec}i=1N,将每一个重构轨迹点的可达距离设置为空值,并初始化有序轨迹点列表L=Ø。

      2) 从集合D中寻找未处理的轨迹点pirec,若所有轨迹点均已处理,跳转至步骤4),否则跳转至步骤3)。

      3) 获取pirec时间约束下同楼层的邻居点集合Nε1ε2(pirec),并将pirec设置为已处理,添加到列表L,若|Nε1ε2(pirec)|大于最小点个数Mthreh,则将Nε1ε2(pirec)中的轨迹点根据可达距离从小到大依次加入到种子集合Lseeds中。(1)判断Lseeds是否为Ø,若为Ø,跳转到步骤2),否则,从Lseeds中取出第一个轨迹点q,获得其邻居点集合Nε1,ε2(q),并将q设置为已处理,添加到列表L;(2)判断Nε1ε2(q)是否大于Mthreh,若小于,跳转到步骤1),否则将Nε1ε2(q)中的轨迹点根据可达距离从小到大依次加入到种子集合Lseeds中。

      4) 获得集合D的有序轨迹点列表L。如图 5所示,重构轨迹点集合D={pirec}i=1N,经In‐door‐STOPTICS算法得到有序轨迹点列表L={pjrec}j=1N,以L的下标索引j为横轴、pjrec的可达距离为纵轴可绘制集合D的增广簇排序图。从图 5中可得辅助信息如下:

      图  5  时空数据集及其增广簇排序图

      Figure 5.  Spatiotemporal Dataset and Illustration of the Cluster-Ordering

      1) 当Indoor‐STOPTICS算法空间半径ε1= r1时,可从集合D中识别两个簇集AclusterBcluster

      2) 当Indoor‐STOPTICS算法空间半径ε1=r2时,簇集Acluster分裂成3个小簇,即Acluster1Acluster2Acluster3,此时可从集合D中识别4个簇集。

      3) 当Indoor-STOPTICS算法空间半径ε1=r2时,每一个簇集包含的轨迹点可通过对应横轴索引序列得到,如簇集Acluster1所对应的横轴索引序列为XidxArr,簇集Acluster1所包含的轨迹点为{L[i]}iXidxArr

      4) 当Indoor‐STOPTICS算法空间半径ε1=r2时,簇集的大小及密集程度可定量表示。如簇集Bcluster的大小可由w表示,w越宽,簇集越大;Bcluster的密集程度可由h表示,h越低,簇集越紧凑。

    • 实验数据来源于济南市某商场1 d的移动用户WiFi定位数据,数据覆盖商场8个楼层,共采集室内用户移动轨迹约200万条,总轨迹点逾3 000万个,采样间隔为1~5 s的轨迹点占比70%以上,数据定位精度约为3 m,数据字段包括用户唯一标识(identification,ID)、记录上传时间、用户所在位置(投影坐标XY及所在楼层ID),如表 1所示。

      表 1  室内用户移动轨迹实例

      Table 1.  Indoor User Trajectory Sample

      用户ID 上传时间 X/m Y/m 楼层ID
      8026BC4*** 2017-12-31T10:00:01 130219*** 43903*** 2
      8026BC4*** 2017-12-31T10:00:03 130219*** 43903*** 2
      8026BC4*** 2017-12-31T10:00:04 130219*** 43903*** 2
      8026BC4*** 2017-12-31T14:59:54 130219*** 43903*** 4
    • 本文以人群密度、点群密度、误识率及算法运行时间作为室内人群聚集区域识别的定量评价指标。其中人群密度Cd、点群密度Pd和误识率F的计算公式分别为:

      $$ {C_d} = \mathop \sum \limits_i^n \frac{{N_i^{{\rm{crowdNum}}}}}{{{V_i}}} \times \frac{{{\rm{\Delta }}t}}{n} $$ (6)
      $$ {P_d} = \mathop \sum \limits_i^n \frac{{N_i^{{\rm{pointNum}}}}}{{{V_i}}} \times \frac{{{\rm{\Delta }}t}}{n} $$ (7)
      $$ F = \frac{{{G_{{\rm{error}}}}}}{{{G_{{\rm{algorithm}}}}}} $$ (8)

      式中,n表示算法识别的簇集个数;Vi表示某簇集的体积,即三维点集的凸包体积;NicrowdNum表示某簇集中包含用户的数量;Δt表示时间步长,即Cd表示在时间Δt内簇集单位体积中累积的用户数量;NipointNum表示某簇集中包含轨迹点的数量,即Pd表示在时间Δt内簇集单位体积中累积的轨迹点数量;Galgorithm表示算法识别的人群聚集区域个数;Gerror表示算法判断错误的人群聚集区域个数。当聚集区域内的用户数量小于数量阈值或聚集区域的聚集时间小于时间阈值时,区域被标识为识别错误。

      本文采用ST-OPTICS和IndoorSRC算法进行对比,探讨两种算法在不同用户数量下误识率、人群密度、点群密度及算法运行时间的变化情况。ST-OPTICS算法利用预处理后轨迹的点集直接识别室内人群聚集区域,IndoorSRC算法对预处理后点集进行简化和重构,采用Indoor-STOPTICS算法识别室内人群聚集区域。

    • 本文采用定性和定量两种方式分析IndoorSRC算法与ST-OPTICS算法的识别结果,定性方式主要采用图形的方式直观展示两种方法在某楼层的识别结果,定量的方式主要采用相关指标评价两种方法的性能。

      以11时至16时作为研究时段,IndoorSRC方法在某楼层的识别结果如图 6所示,重构轨迹点集合D在不同区域、不同时间呈现明显的聚集模式,绘制集合D的增广簇排序图,可具体识别高密度区域存在的位置及时间。以空间半径ε1=6m为例,集合D将存在8个高密度区域,进一步分析每一个簇集大小与密集程度,最终得到5个室内人群聚集区域。5个室内人群聚集区域位置及时间特征如表 2所示。聚集区域多集中于中午时段且主要位于餐饮地区,如食尚家属于商场内部的小吃区,在中午时段形成3个时间较短的人群聚集区,渔家灯火和中餐厅属于商场内部的饭店,各形成一个时间较长的人群聚集区。

      图  6  室内人群聚集区域识别结果

      Figure 6.  Indoor Crowd Gathering Area Identification Results

      表 2  室内人群聚集区域位置时间特征

      Table 2.  Indoor Crowd Gathering Area Location and Time Characteristics

      聚集区域 聚集位置 聚集时间
      聚集区域1 食尚家 11:31:15―11:56:23
      聚集区域2 食尚家 12:07:24―12:34:09
      聚集区域3 中餐厅 12:16:17―13:32:48
      聚集区域4 渔家灯火 12:20:03―13:24:38
      聚集区域5 食尚家 14:14:13―14:17:29

      ST-OPTICS算法的结果如图 7所示,与IndoorSRC算法识别结果相比:(1)ST-OPTICS算法虽然在不同区域、不同时间发现了较明显的聚集模式,但该聚集模式多为"点聚集"而非"人群聚集",即由于用户购物目的性导致的停留点集合;(2)ST-OPTICS算法识别的簇集中存在较多相邻较近的小簇集,原因是室内轨迹数据质量较差,存在较多缺失数据,直接采用轨迹点信息识别室内人群聚集区域将导致本是一个的簇集分裂成较多个小簇集。

      图  7  ST-OPTICS算法识别结果

      Figure 7.  Recognition Result of ST-OPTICS Algorithm

      IndoorSRC算法与ST-OPTICS算法人群密度、点群密度、误识率和运行时间的对比见图 8。由图 8可知:(1)IndoorSRC算法识别的人群密度远高于ST-OPTICS算法识别的人群密度,而ST-OPTICS算法识别的点群密度略高于IndoorSRC算法的点群密度,原因是ST-OPTICS算法识别的簇集较多为"点聚集"而非"人聚集"区域。(2)当用户量较少时,IndoorSRC算法的运行时间略高于ST-OPTICS算法的运行时间,原因是IndoorSRC算法对预处理后的轨迹做了简化与重构,使得算法的运行时间增加,但随着用户量的增加,预处理后轨迹点数量远大于重构轨迹点数量,使得ST-OPTICS算法的运行时间超过IndoorSRC算法的运行时间。(3)ST-OPTICS算法的误识率随用户数量的增加缓慢提升,原因是随着用户数量的增多,用户的停留区域也逐渐增多,在一定程度上提高了ST-OPTICS算法的误识率。

      图  8  IndoorSRC和ST-OPTICS定量对比结果

      Figure 8.  Quantitative Comparison of IndoorSRC and ST-OPTICS

      4) IndoorSRC算法的误识率较稳定,且远低于ST-OPTICS算法的误识率,误识率最高可降低23.7%,原因是IndoorSRC算法对室内用户轨迹做了简化与重构,降低了用户停留区域和缺失轨迹点对识别结果的影响。

    • 针对传统的室外人群聚集区域识别算法难以应用到室内空间的问题,本文提出了一种室内的人群聚集区域识别框架IndoorSRC。首先,提出了Indoor-STAGNES算法简化室内用户移动轨迹,去除用户停留信息;接着,构建了一种基于卡尔曼滤波的室内轨迹重构方法,补齐缺失轨迹点信息;最后提出了Indoor-STOPTICS算法发现室内三维时空人群聚集区域。实验结果表明,与传统算法运行时间差别不大的情况下,IndoorSRC算法能识别的准确率可提高23.7%。本文能够为室内人群聚集区域识别方法提供有效补充,为室内安全事故的提前预警与应急救援提供技术支持。

      室内人群集聚仅是室内拥挤、踩踏等安全事故产生的必要条件,除此之外,用户移动方向同样在很大程度上影响了室内安全事故的产生,例如,当人群集聚且同方向行走时往往不会发生安全事故,只有当人群集聚且行走方向无序时将较大可能导致安全事故的发生。因此,未来将在IndoorSRC方法的基础上引入方向等其他约束,提高识别的准确率,从而辅助室内安全事故的提前预警与应急救援。

参考文献 (20)

目录

    /

    返回文章
    返回