Computing a similarity measure over moving object trajectories

Patent metadata

Field	Value
Publication number	US-9747805-B2
Application number	US-201313955146-A
Country	US
Kind code	B2
Filing date	Jul 31, 2013
Priority date	Jul 31, 2013
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

Methods and arrangements for measuring similarity with respect to moving object trajectories. First and second moving object trajectories are input, each trajectory being defined by at least two spatial dimensions and a temporal dimension. At least one segment is defined with respect to each trajectory, each segment being defined between two defining points. At least one segment from the first trajectory is matched with at least one segment from the second trajectory. A spatial distance and temporal distance are each computed between the at least one segment from the first trajectory and the at least one segment from the second trajectory. The spatial distance and temporal distance are combined to provide a measure of a spatio-temporal distance between the at least one segment from the first trajectory and the at least one segment from the second trajectory. Other variants and embodiments are broadly contemplated herein.

First claim

What is claimed is:

1. A method of measuring similarity with respect to moving object trajectories, said method comprising:
inputting, using a processor, first and second moving object trajectories, each trajectory being defined by at least two spatial dimensions and a temporal dimension, each trajectory including at least two defining points;
defining, using a processor, at least one segment with respect to each trajectory, each segment being defined by a spatial measure and by a temporal measure between two defining points;
matching, using a processor, at least one segment from the first trajectory with at least one segment from the second trajectory;
computing, using a processor, a spatial distance between the at least one segment from the first trajectory and the at least one segment from the second trajectory, based on the spatial measure between the two defining points of each of the at least one segment from the first trajectory and the at least one segment from the second trajectory;
computing, using a processor, a temporal distance between the at least one segment from the first trajectory and the at least one segment from the second trajectory, based on the temporal measure between the two defining points of each of the at least one segment from the first trajectory and the at least one segment from the second trajectory;
combining, using a processor, the spatial distance and temporal distance to provide a measure of a spatio-temporal distance between the at least one segment from the first trajectory and the at least one segment from the second trajectory;
determining a similarity between the first trajectory and the second trajectory based upon the spatio-temporal distance between each of the at least one segment from the first trajectory and the at least one segment from the second trajectory; and
identifying and tracking, based upon a similarity between the first trajectory and the second trajectory exceeding a predetermined threshold, a location of one of: the first moving object and the second moving object.

2. The method according to claim 1 , wherein the at least two defining points comprise at least two sampled points.

3. The method according to claim 1 , comprising projecting a defining point of a segment in the first trajectory to create a new defining point in the second trajectory.

4. The method according to claim 3 , wherein said projecting comprises projecting a defining point of a segment in the first trajectory to a closest point in the second trajectory.

5. The method according to claim 1 , wherein:
at least one of the first and second trajectories comprises at least three defining points; and
said defining comprises defining at least two segments with respect to the at least one of the first and second trajectories.

6. The method according to claim 1 , wherein said matching comprises undertaking a one-to-one matching of at least one segment from the first trajectory with at least one segment from the second trajectory.

7. The method according to claim 1 , wherein said matching comprises undertaking a one-to-one matching of a plurality of segments from the first trajectory with a plurality of segments from the second trajectory.

8. The method according to claim 7 , comprising projecting a defining point of a segment in the first trajectory to create a new defining point in the second trajectory.

9. The method according to claim 8 , wherein said projecting comprises projecting a defining point in the first trajectory to a closest point in the second trajectory.

10. The method according to claim 8 , wherein said matching comprises matching two segments from the first trajectory with two segments from the second trajectory, each of the two segments from the second trajectory being defined between the new defining point and another defining point.

11. An apparatus comprising:
at least one processor; and
a non-transitory computer readable storage medium having computer readable program code embodied therewith and executable by the at least one processor, the computer readable program code comprising:
computer readable program code configured to input first and second moving object trajectories, each trajectory being defined by at least two spatial dimensions and a temporal dimension, each trajectory including at least two defining points;
computer readable program code configured to define at least one segment with respect to each trajectory, each segment being defined by a spatial measure and by a temporal measure between two defining points;
computer readable program code configured to match at least one segment from the first trajectory with at least one segment from the second trajectory;
computer readable program code configured to compute a spatial distance between the at least one segment from the first trajectory and the at least one segment from the second trajectory, based on the spatial measure between the two defining points of each of the at least one segment from the first trajectory and the at least one segment from the second trajectory;
computer readable program code configured to compute a temporal distance between the at least one segment from the first trajectory and the at least one segment from the second trajectory, based on the temporal measure between the two defining points of each of the at least one segment from the first trajectory and the at least one segment from the second trajectory;
computer readable program code configured to combine the spatial distance and temporal distance to provide a measure of a spatio-temporal distance between the at least one segment from the first trajectory and the at least one segment from the second trajectory;
computer readable program code configured to determine a similarity between the first trajectory and the second trajectory based upon the spatio-temporal distance between each of the at least one segment from the first trajectory and the at least one segment from the second trajectory; and
computer readable program code configured to identify and track, based upon a similarity between the first trajectory and the second trajectory exceeding a predetermined threshold, a location of one of: the first moving object and the second moving object.

12. A computer program product comprising:
a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
computer readable program code configured to input first and second moving object trajectories, each trajectory being defined by at least two spatial dimensions and a temporal dimension, each trajectory including at least two defining points;
computer readable program code configured to define at least one segment with respect to each trajectory, each segment being defined by a spatial measure and by a temporal measure between two defining points;
computer readable program code configured to match at least one segment from the first trajectory with at least one segment from the second trajectory;
computer readable program code configured to compute a spatial distance between the at least one segment from the first trajectory and the at least one segment from the second trajectory, based on the spatial measure between the two defining points of each of the at least one segment from the first trajectory and the at least one segment from the second trajectory;
computer readable program code configured to compute a temporal distance between the at least one segment from the first trajectory and the at least one segment from the second trajectory, based on the temporal measure between the two defining points of each of the at least one se

Assignees

• IBM

Inventors

• Deshpande Prasad M
• Padmanabhan Deepak S
• Raghavan Sriram
• Ranu Sayan
• Telang Aditya D

Classifications

• G08G1/20 Primary

  Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles · CPC title

• G01C21/26 Primary

  specially adapted for navigation in a road network · CPC title

• G01S5/0294

  Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering · CPC title

• G01S5/02

  using radio waves (using satellite radio beacon systems for determining position G01S19/00) · CPC title