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

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

• 批准号: RGPIN-2020-05351
• 负责人: Durocher, Stephane
• 金额: $ 3.5万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=716909
• 关键词: 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的设备和运动跟踪传感器的成本和尺寸的降低导致了用于记录运动的设备的数量和使用的巨大增加，通过各种应用迅速产生对处理和分析轨迹集的广泛需求：动物的迁徙模式；商用车辆车队；步道上的自行车、徒步和跑步路线；分析商场内顾客行为的商业利益用于制作视频游戏或电脑动画的动作捕捉数据；政府对手机用户收到紧急信息后的行动进行分析；运动员跟踪数据的体育分析；等。支持这些任务的有效算法的发展是必不可少的，并且将代表一个重大的贡献，将直接受益于涉及运动的广泛应用。