Trajectory matching using ambient signals

• US 10,466,056 B2
• Filed: 12/15/2014
• Issued: 11/05/2019
• Est. Priority Date: 04/25/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jiang, Yifei, Mori, Koichi, Sidhu, Shalinder S.
• Primary Examiner(s): Charioui, Mohamed
• Assistant Examiner(s): Hagos, Eyob
• Application Number:
  US14/571,166
• Publication Number:
  US 20150308839A1
• Time in Patent Office: 1,786 Days
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/383 Indoor data
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G01S 19/12 wherein the cooperating elements are telecommunication base stations

Abstract

A technique to automatically determine a shape of a path based on crowdsourced trajectory data is disclosed. Trajectory data is collected for a plurality of crowdsourced paths. The trajectory data for each of the plurality of crowdsourced paths is associated with at least one uniquely identifiable ambient signal. Anchor points may be identified corresponding to a transition in a characteristic of trajectory data of an individual crowdsourced path. Matching may be performed based on analyzing matching patterns of anchor points and evaluating the matches. Various embodiments involve using a linked node structure to represent one or more traces and/or indicate routes in a particular geographical area.

Claims

1. A computer implemented method, comprising:

receiving, by a computer, collected trajectory data from a plurality of mobile devices on a plurality of crowdsourced paths, wherein the trajectory data for each path of the plurality of crowdsourced paths has associated therewith an ambient signal;

processing, by the computer, the collected trajectory data by;

identifying, by the computer, a set of anchor points in the trajectory data for each path of the plurality of crowdsourced paths respectively,

generating a set of permutations of each set of anchor points from each path of the plurality of crowdsourced paths respectively, and

selecting, by the computer, a best match of paths among the plurality of crowdsourced paths, the best match of paths selected at least partially based on (a) evaluating the set of permutations of each set of anchor points from each path to provide best matching sets of anchor points and (b) determining a signal similarity score between the associated ambient signal for each path of the plurality of crowdsourced paths respectively;

generating, by the computer, a shape of a path in a geographic area based on the best match of paths and providing a linked-node structure corresponding to a path map of the geographical area; and

storing the shape of the path in the geographic area and the linked-node structure in a memory accessible by the computer.

2. The method of claim 1, wherein, for each path of the plurality of crowdsourced paths, each anchor point in each identified set of anchor points corresponds to a transition in a characteristic of the trajectory data respectively.

3. The method of claim 2, wherein the transition corresponds to at least one of a turn, a user activity, and a vehicle use pattern.

4. The method of claim 2, wherein selecting the best match comprises identifying matching patterns of sets of anchor points from two or more paths.

5. The method of claim 4, wherein identifying matching patterns of anchor points comprises identifying a turn.

6. The method of claim 5, wherein identify a turn comprises selecting a sub-trajectory step length and determining whether a threshold angle condition is satisfied.

7. The method of claim 6, wherein the step length is selected to detect a mild turn.

8. The method of claim 6, wherein the step length is selected to detect a sharp turn.

9. The method of claim 6, wherein a step length is adjusted to detect both mild turns and sharp turns.

10. The method of claim 9, further comprising identifying significant turns by selecting a mild turn and an end turn from a combination of sharp turns.

11. The method of claim 1, wherein selecting the best match further comprises:

identifying possible pairs of crowdsourced paths among the plurality of crowdsourced paths;

scoring each of the possible pairs of crowdsourced paths based on a distance between their anchor points respectively; and

selecting the best match of paths based on the scoring for each of the possible pairs of crowdsourced paths.

12. The method of claim 11, wherein each possible pair of individual crowdsourced paths is further based at least in part on a similarity score of their associated ambient signals respectively.

13. The method of claim 12, wherein the similarity score is determined based on calculating an ambient signal similarity and dividing the ambient signal similarity by a distance factor.

14. The method of claim 5, wherein matches of trajectory data of two crowdsourced paths have trajectory data translated and rotated to adjust the trajectory data into an alignment.

15. The method of claim 1, wherein the associated ambient signal comprises at least one member from the group consisting of a Wi-Fi signal, a Bluetooth signal, sound, an image signal, a magnetic signal, and an optical signal.

16. The method of claim 1, wherein each mobile device includes at least one sensor to generate trajectory data.

17. A system comprising:

a processor;

a memory;

a trajectory merging and correction unit;

a trajectory matching unit; and

a mapping unit;

wherein the trajectory merging and correction unit, the trajectory matching unit and the mapping unit are implemented using one or more software modules arranged to be executed by the processor and stored in the memory;

the system configured to receive trajectory data from a plurality of mobile devices on a plurality of crowdsourced paths, wherein the trajectory data for each path of the plurality of paths is associated with at least one ambient signal; and

the processor configured to;

identify, by the trajectory merging and correction unit, a set of anchor points in the trajectory data for each path of the plurality of crowdsourced paths respectively,

generate a set of permutations of each set of anchor points from each path of the plurality of crowdsourced paths respectively,

select, by the trajectory matching unit, a best match of paths among the plurality of crowdsourced paths, the best match of paths selected at least partially based on (a) an evaluation of the set of permutations of each set of anchor points from each path to provide best matching sets of anchor points and (b) a determination of a signal similarity score between the associated ambient signal for each path of the plurality of crowdsourced paths respectfully,

determine a shape of a path in a geographic area based on the best match of paths, and

store the shape of the path in the geographic area in the memory.