Systems, methods, and devices for geo-localization

• US 10,677,932 B2
• Filed: 09/25/2018
• Issued: 06/09/2020
• Est. Priority Date: 02/19/2016
• Status: Active Grant

• Current Assignee: Ohio State Innovation Foundation (Ohio State University)
• Original Assignee: Ohio State Innovation Foundation (Ohio State University)
• Inventors: Yilmaz, Alper, Gupta, Ashish
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): Thomas, Ana D
• Application Number:
  US16/141,015
• Publication Number:
  US 20190025439A1
• Time in Patent Office: 623 Days
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01S 19/26 involving a sensor measurement for aiding acquisition or tracking
• CPC Class Codes: G01S 19/45 by combining measurements of signals from the satellite radio beacon positioning system with a supplementary measurement
• CPC Class Codes: G01S 19/51 Relative positioning
• CPC Class Codes: G01S 5/16 using electromagnetic waves other than radio waves

Abstract

According to the embodiments provided herein, a trajectory determination device for geo-localization can include one or more relative position sensors, one or more processors, and memory. The one or more processors can execute machine readable instructions to receive the relative position signals from the one or more relative position sensors. The relative position signals can be transformed into a sequence of relative trajectories. Each of the relative trajectories can include a distance and directional information indicative of a change in orientation of the trajectory determination device. A progressive topology can be created based upon the sequence of relative trajectories; this progressive topology can be compared to map data. A geolocation of the trajectory determination device can be determined.

Claims

1. A system, comprising:

memory storing machine readable instructions; and

one or more processors to access the memory and execute the machine readable instructions to;

receive relative position signals generated for a device;

generate relative trajectories comprising directional information based on the relative position signals;

evaluate the directional information to identify a given discrete bin from a plurality of discrete bins for each relative trajectory;

transform each relative trajectory to a trajectory descriptor based on the given discrete bin;

connect each of the trajectory descriptors to define a progressive topology, wherein the progressive topology is a representation of a movement of the device;

compare the progressive topology to map data characterizing a region of interest, wherein the device is located within the region of interest; and

determine a geolocation for the device based on the comparison.

2. The system of claim 1,

further comprising an optical sensor to generate vision-based measurements;

and

wherein the one or more processors execute the machine readable instructions to combine the relative position signals and the vision-based measurements.

3. The system of claim 1, further comprising one or more

relative position sensors to generate a relative position signal for the device at each instance of time and the one or more processors generate the relative trajectories to provide a sequence of relative trajectories.

4. The system of claim 3, wherein the sequence of relative trajectories are quantized according to a sampling distance.

5. The system of claim 4, wherein to quantize the sequence of relative trajectories according to the sampling distance comprises:

determining a distance between a given relative trajectory of the sequence of relative trajectories and another relative trajectory of the sequence of relative trajectories;

comparing the distance relative to the sampling distance; and

transforming the relative position signal into a relative trajectory based on a result of the comparison.

6. The system of claim 1, wherein the device comprises at least one of a smart phone, a tablet, a smartwatch and a wearable device.

7. The system of claim 1 where the vision-based measurements comprise

monocular vision-based measurements.

8. The system of claim 1, wherein the transforming of each relative trajectory to a trajectory descriptor is performed by a fusion algorithm.

9. The system of claim 1, wherein the relative trajectory corresponds to three-dimensional (3D) motion of trajectory determination device, the relative trajectory being quantized into the trajectory descriptor using angle information corresponding to the 3D motion.

10. The system of claim 1, wherein the map data comprises a map graph with features computed as angles between each pair of edges at each node No with its neighbors N={N_i, N₂, N₃}, or computed as rate of change of angles between each pair of edges at each node No with its neighbors N={N_i, N₂, N₃}.

11. The system of claim 1, wherein the relative position signals comprises combining quaternion units and monocular vision-based measurements, the quaternion units represent rotations from global frame G to frame I of measurements of an inertial measurement unit (IMU) which comprises a gyroscope and accelerometer, and the monocular vision-based measurements are measured by an optical sensor based on the Earth-Centered, Earth-Fixed (ECEF) coordinates.

12. A system, comprising:

memory storing machine readable instructions; and

one or more processors to access the memory and execute the machine readable instructions to;

receive relative position signals generated for a device;

generate relative trajectories comprising directional information based on the relative position signals;

evaluate the directional information to identify a given discrete bin from a plurality of discrete bins for each relative trajectory;

transform each relative trajectory to a trajectory descriptor based on the given discrete bin; and

generate motion data characterizing a movement of the device over time based on the trajectory descriptors;

connect each of the trajectory descriptors to define a progressive topology,

wherein the progressive topology is a representation of a movement of the device;

compare the progressive topology to map data characterizing a region of interest, wherein the device is located within the region of interest, wherein the map data comprises a map graph of the region of interest, and the map graph comprises a plurality of graph paths; and

wherein the one or more processors execute the machine readable instructions further to;

generate a trajectory graph based on the progressive topology;

compute a similarity score between the trajectory graph and each of the plurality of graph paths; and

determine a geolocation for the device based on the comparison.

13. The system of claim 12,

wherein the progressive topology comprises a plurality of points separated by a given distance;

and

wherein the one or more processors execute the machine readable instructions further to identify a set of points of the plurality of points as control points and a set of points of the plurality of points between the control points as edges, wherein the trajectory graph is generated based on the control points and the edges.

14. The system of claim 12,

wherein the plurality of graph paths comprise a sequence of quantized edge-orientations and the trajectory graph comprises a sequence of quantized edge-orientations;

and

wherein to compute the similarity score comprises;

comparing the sequence of quantized edge-orientations of the trajectory graph relative to the sequence of quantized edge-orientations of the plurality of graph paths; and

assigning a similarity score to each comparison.

15. The system of claim 12, wherein the one or more processors execute the machine readable instructions further to:

evaluate each similarity score computed for the trajectory graph and a graph path of the plurality of graph paths relative to a score threshold to identify a similarity score with a highest value, determine the geolocation of the device based on the graph path associated with the similarity score with the highest value.

16. The system of claim 12, wherein the trajectory graph is a spline approximation of the progressive topology.

17. The system of claim 12, wherein the map graph is retrieved from one of a geospatial system database, a geographic information system (GIS) database and a building information model database.

18. The system of claim 12, wherein the progressive topology grows in size over time as the device moves about the region of interest;

wherein the trajectory graph grows commensurate in size with the progressive topology; and

wherein a larger trajectory graph at given instance of time relative to a smaller trajectory graph at another instance of time reduces a number of similarity scores computed between the trajectory graph and each of the plurality of graph paths.

19. The system of claim 12, wherein the region of interest

comprises one of a building, a neighborhood within a municipality, a state, a city area, and an entire world.

20. A method, comprising:

receiving relative position signals generated for a device;

generating, with a processor, relative trajectories comprising directional information based on the relative position signals;

evaluating the directional information to identify a given discrete bin from a plurality of discrete bins for each relative trajectory;

transforming each relative trajectory to a trajectory descriptor based on the given discrete bin; and

generating motion data characterizing a movement of the device over time based on the trajectory descriptors.

21. The method of claim 20, further comprising:

connecting each of the trajectory descriptors to define a progressive topology, wherein the progressive topology is a representation of a movement of the device;

comparing the progressive topology to map data characterizing a region of interest, wherein the device is located within the region of interest, wherein the map data comprises a map graph of the region of interest, and the map graph comprises a plurality of graph paths;

generating a trajectory graph based on the progressive topology;

computing a similarity score between the trajectory graph and each of the plurality of graph paths; and

determining a geolocation for the device based on the comparison.

22. The method of claim 21, wherein the map graph comprises a plurality of graph paths representative by the features;

and further comprising;

generating a trajectory graph based on the progressive topology; and

computing a similarity score between the trajectory graph and each of the features of the map graph.

23. The method of claim 21, wherein the plurality of graph paths comprise a sequence of quantized edge-orientations;

wherein the trajectory graph comprises a sequence of quantized edge-orientations; and

wherein the computing the similarity score comprises;

comparing the sequence of quantized edge-orientations of the trajectory graph relative to the sequence of quantized edge-orientations of the plurality of graph paths; and

assigning a similarity score to each comparison.

24. The method of claim 23, further comprising:

identifying one of unique nodes and edges in the map graph; and

weighting the similarity score according to the one of unique nodes and edges.

25. The method of claim 21, wherein the map data comprises a map graph with features computed as angles between each pair of edges at each node N0 with its neighbors N={Ni, N2, N3}, or computed as rate of change of angles between each pair of edges at each node No with its neighbors N={Ni, N2, N3}.

26. The method of claim 20, wherein the transforming of each relative trajectory to a trajectory descriptor is performed by a fusion algorithm.

27. The method of claim 20, wherein the relative trajectory corresponds to three-dimensional (3D) motion of trajectory determination device, the relative trajectory being quantized into the trajectory descriptor using angle information corresponding to the 3D motion.

28. The method of claim 20, wherein the relative position signals comprises combining quaternion units and monocular vision-based measurements, the quaternion units represent rotations from global frame G to frame I of measurements of an inertial measurement unit (IMU) which comprises a gyroscope and accelerometer, and the monocular vision-based measurements are measured by an optical sensor based on Earth-Centered, Earth-Fixed (ECEF) coordinates.