Algorithms for Summarizing, Representing, and Analyzing Trajectories of Moving Objects

总结、表示和分析运动物体轨迹的算法

• 批准号: RGPIN-2020-05351
• 负责人: Durocher, Stephane
• 金额: $ 3.5万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=739796
• 关键词: Algorithms; Summarizing; Representing; Analyzing; Trajectories

The analysis of spatio-temporal trajectory data for sets of moving objects is quickly becoming an important area of research for which efficient geometric algorithms are necessary. The decreased cost and size of GPS-enabled devices and motion-tracking sensors has led to a tremendous increase in the number and use of devices for recording motion, quickly creating extensive demand for processing and analysis of sets of trajectories by a variety of applications: migratory patterns of animals; fleets of commercial vehicles; routes of cyclists, hikers, and runners on trails; commercial interests in analyzing the motion of shoppers in malls; motion-capture data used in the creation of video games or computer animation; government analysis of the movement of cell-phone users upon receiving an emergency message; sports analytics of player tracking data; etc. The development of efficient algorithms for supporting these tasks is essential, and would represent a significant contribution that would directly benefit a wide range of applications that involve motion. Most existing geometric optimization algorithms operate on static input, e.g., on a given set of points, line segments, polyhedra, etc. The same holds for most existing notions of centrality, data depth, location estimators, and clustering objective functions. Motivated by the multitude of present-day applications involving motion, and the ease, prevalence, and variety of methods for recording motion, the proposed research seeks to develop efficient algorithms for simplifying, summarizing, representing, and analyzing moving input. Specifically, the algorithms operate on sets of spatio-temporal trajectories representing the positions of objects moving through space over time. The proposed research program's objectives include: 1.Identifying good location estimators and summary statistics for spatio-temporal trajectory data, including defining new measures of centrality and data depth that effectively summarize and represent the input set of motions, along with efficient algorithms for computing these, and 2.Defining appropriate objective functions for partitioning sets of moving objects into clusters based on the similarities of their spatio-temporal trajectories, along with efficient algorithms for computation. The broader goal is to develop new ideas and new techniques to efficiently summarize, represent, and analyze motion and the trajectories of groups of moving objects. The proposed research will involve training approximately 15 HQP who will develop expertise relevant to the large variety of Canadian industries whose business involves trajectory data and motion.

运动目标集的时空轨迹数据分析正迅速成为一个重要的研究领域，需要高效的几何算法。支持gps的设备和运动跟踪传感器的成本和尺寸的降低导致了用于记录运动的设备的数量和使用的巨大增加，通过各种应用迅速产生对处理和分析轨迹集的广泛需求：动物的迁徙模式；商用车辆车队；步道上的自行车、徒步和跑步路线；分析商场内顾客行为的商业利益用于制作视频游戏或电脑动画的动作捕捉数据；政府对手机用户收到紧急信息后的行动进行分析；运动员跟踪数据的体育分析；等。支持这些任务的有效算法的发展是必不可少的，并且将代表一个重大的贡献，将直接受益于涉及运动的广泛应用。大多数现有的几何优化算法在静态输入上运行，例如，在给定的点、线段、多面体等集合上运行。这同样适用于大多数现有的中心性、数据深度、位置估计器和聚类目标函数的概念。由于当前涉及运动的大量应用，以及记录运动的简单、流行和多种方法，所提出的研究旨在开发有效的算法来简化、总结、表示和分析运动输入。具体来说，这些算法对时空轨迹集进行操作，这些轨迹集表示物体在空间中随时间移动的位置。拟建的研究项目的目标包括：1。确定良好的位置估计器和时空轨迹数据的汇总统计，包括定义有效总结和表示运动输入集的中心性和数据深度的新度量，以及计算这些数据的有效算法；定义适当的目标函数，根据运动物体的时空轨迹相似性将其划分为簇，并提供有效的计算算法。更广泛的目标是发展新思想和新技术，以有效地总结，表示和分析运动和运动对象组的轨迹。拟议的研究将涉及培训大约15名HQP，他们将开发与各种加拿大工业相关的专业知识，这些工业的业务涉及轨迹数据和运动。