Method to scale inertial location data using directional and/or scale confidence constraints

• US 8,990,014 B2
• Filed: 03/14/2014
• Issued: 03/24/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: TRX Systems, Inc.
• Original Assignee: TRX Systems, Inc.
• Inventors: Funk, Benjamin, Hakim, Dan, Karvounis, John, Teolis, Carole
• Primary Examiner(s): Cheung, Mary
• Assistant Examiner(s): Trivedi, Atul
• Application Number:
  US14/212,529
• Publication Number:
  US 20140278080A1
• Time in Patent Office: 375 Days
• Field of Search: 701411-413, 701500-510
• US Class Current: 701/500
• CPC Class Codes: G01C 21/08 involving use of the magnetic field of the earth
• CPC Class Codes: G01C 21/1654 with electromagnetic compass

Abstract

Methods, systems, and computer readable storage media are presented for directional scaling of inertial path data to satisfy ranging constraints. The presented techniques take into account scaling confidence information. In addition to bounding potential scale corrections based on the reliability of the inertial path and the magnetic heading confidence, the techniques bound potential scale parameters based on constraints and solve for directional scale parameters.

Claims

1. A method for determining a scale used in estimating a path of a computing device in motion, the method comprising:

receiving a plurality of pairs of points along the path based on inertial sensor data from the computer device;

determining which of the plurality of pairs of points along the path are constrained, each constrained pair of points comprising a first point and a second point, the first point being associated with a first constraint having a first radius, the second point being associated with a second constraint having a second radius, the first point and the second point being separated by a distance;

determining for each constrained pair of points a first bound and a second bound based on the first radius, the second radius, and the distance;

determining a first intersection of the first bounds of the plurality of pairs of points and a second intersection of the second bounds of the plurality of pairs of points; and

setting the scale as an intersection of the first intersection and the second intersection.

2. The method of claim 1, wherein the first bound is equal to the division by the distance of the sum of the distance, the first radius, and the second radius.

3. The method of claim 1, wherein the second bound is equal to the division by the distance of the subtraction of the first radius and the second radius from the distance.

4. The method of claim 1, wherein the determining which of the plurality of pairs of points along the path are constrained is based on a minimum distance separation and a maximum time separation for each pair of points among the plurality of pairs of points.

5. The method of claim 1, wherein the determining for each constrained pair of points a first bound and a second bound includes selecting the pair of points among the plurality of pairs of points that has the closest first bound to the second bound.

6. The method of claim 1, wherein the set scale is closest to one in comparison to scales set as intersections associated with the remaining first bounds and second bounds.

7. The method of claim 1, wherein the determining which of the plurality of pairs of points along the path are constrained comprises disregarding a first pair of points from the plurality of pairs of points when the first constraint of the first point in the first pair of points overlaps with or is within some distance of the first constraint of the first point in a second pair of points from the plurality of pairs of points.

8. A method for rescaling a path of a computing device in motion, the path including a plurality of points based on inertial sensor data, a desired endpoint, and a path endpoint, the method comprising:

representing each pair of consecutive points with a segment to generate a plurality of segments;

determining a constraint error based on a comparison of the desired end point and the path endpoint;

determining a contribution of each segment of the plurality of segments to the constraint error; and

adjusting each segment of the plurality of segments based on the corresponding contribution.

9. The method of claim 8, wherein coordinates are associated with each point, the desired endpoint, and the path endpoint.

10. The method of claim 9, wherein the representing each pair of consecutive points with a segment comprises generating a difference vector based on the coordinates of the consecutive points of the pair.

11. The method of claim 10, wherein the determining a constraint error comprises generating an error vector by subtracting the coordinates of the desired endpoint from the coordinates of the path end point.

12. The method of claim 11, wherein the determining a contribution of each segment of the plurality of segments to the constraint error, comprises:

dividing the error vector by the magnitude of the error vector to generate a unit vector;

computing, for each difference vector, a weight as the dot product of the difference vector and the unit vector;

dividing each weight by the sum of absolute values of all the weights to normalize each weight;

computing, for each difference vector, the magnitude of the difference vector;

determining, for each difference vector, an adjustment of the magnitude of the difference vector by multiplying the magnitude of the error vector by the normalized weight of the difference vector; and

determining, for each difference vector, a scale as a function of the adjustment of the magnitude of the difference vector and the magnitude of the difference vector.

13. The method of claim 12, wherein the adjusting each segment of the plurality of segments based on the corresponding contribution comprises:

rescaling the difference vectors based on the scale; and

reconstructing the points by cumulatively summing the rescaled difference vectors.

14. The method of claim 12, wherein the scale is equal to one when the normalized weight of a difference vector is equal to zero and is otherwise equal to the division by the magnitude of the sum of the adjustment of the magnitude of the difference vector and the magnitude of the difference vector.

15. A method for estimating a path of a computing device in motion, the method comprising:

determining a pair of points of the path comprising a first point and a second point, the first point being associated with a first constraint having a first radius, the second point being associated with a second constraint having a second radius, the first point and the second point being separated by a distance, points of the path between the first point and the second point forming step vectors, each step vector connecting two consecutive points;

multiplying each step vector with an adjustable parameter associated with a scale of the path;

summing the multiplied step vectors to generate the path to generate a total step vector;

determining a difference vector between the first point and the second point;

subtracting the total step vector from the difference vector to form a delta vector; and

adjusting the parameters associated with the scale until the magnitude of the delta vector is less than the sum of the first radius and the second radius.

16. The method of claim 15, wherein the scale parameter is initialized to one.

17. A computing system for estimating a path of a computing device in motion, the computing system comprising:

a processor;

a memory communicatively coupled to the processor, the memory bearing instructions that, when executed on the processor, cause the computing system to at least;

determine a plurality of pairs of points along the path that are constrained, each pair of points comprising a first point and a second point, the first point being associated with a first constraint having a first radius, the second point being associated with a second constraint having a second radius, the first point and the second point being separated by a distance;

determine for each pair of points a first bound and a second bound based on the first radius, the second radius, and the distance;

determine a first intersection of the first bounds of the plurality of pair of points and a second intersection of the second bounds of the plurality of pair of points; and

set the scale as an intersection of the first intersection and the second intersection.

18. A map of a path of a computing device in motion, the map being obtained based on the steps of:

determining a pair of points of the path comprising a first point and a second point, the first point being associated with a first constraint having a first radius, the second point being associated with a second constraint having a second radius, the first point and the second point being separated by a distance, points of the path between the first point and the second point forming step vectors, each step vector connecting two consecutive points;

multiplying each step vector with an adjustable parameter associated with a scale of the path;

summing the multiplied step vectors to generate the path to generate a total step vector;

determining a difference vector between the first point and the second point;

subtracting the total step vector from the difference vector to form a path vector;

adjusting the parameters associated with the scale until the magnitude of the path vector is less than the sum of the first radius and the second radius; and

generating the map based at least in part on the points and the adjusted parameters.

19. A computer readable storage medium comprising instructions that, when executed on a system configured to rescale a path of a computing device in motion, the path including a plurality of points, a desired endpoint, and a path endpoint, cause the system to at least:

represent each pair of consecutive points with a segment to generate a plurality of segments;

determine a constraint error based on a comparison of the desired end point and the path endpoint;

determine a contribution of each segment of the plurality of segments to the constraint error; and

adjust each segment of the plurality of segments based on the corresponding contribution.

20. A computing system for presenting a path of a computing device in motion, the computing system comprising:

a processor; and

a memory communicatively coupled to the processor, the memory bearing instructions that, when executed on the processor, cause the computing system to at least;

present a user interface configured to receive input from a user;

determine a pair of points of the path comprising a first point and a second point, the first point being associated with a first constraint having a first radius, the second point being associated with a second constraint having a second radius, the first point and the second point being separated by a distance, points of the path between the first point and the second point forming step vectors, each step vector connecting two consecutive points;

multiply each step vector with an adjustable parameter associated with a scale of the path;

sum the multiplied step vectors to generate the path to generate a total step vector;

determine a difference vector between the first point and the second point;

subtract the total step vector from the difference vector to form a path vector;

adjust the parameters associated with the scale until the magnitude of the path vector is less than the sum of the first radius and the second radius;

generate a visual representation of the path based at least in part on the points and the adjusted parameters; and

present the visual representation at the user interface.