Systems and methods for correlating reduced evidence grids

• US 9,157,743 B2
• Filed: 07/18/2012
• Issued: 10/13/2015
• Est. Priority Date: 07/18/2012
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Ma, Yunqian, Elgersma, Michael Ray
• Primary Examiner(s): TSAI, CAROL S W
• Application Number:
  US13/552,174
• Publication Number:
  US 20140025331A1
• Time in Patent Office: 1,182 Days
• Field of Search: 702/141, 702/150, 701/445, 701/510, 701/221, 701/209, 701/400, 701/409, 701/408, 345/420, 345/419, 345/427, 345/629, 345/325, 345/424, 382/154
• US Class Current: 1/1
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 17/931 of land vehicles

Abstract

A system is provided for correlating evidence grids. In certain embodiments, the system includes a sensor that generates signals describing a current section of an environment; a memory configured to store measurements of historical sections of the environment; and a processor coupled to the sensor and configured to calculate navigation parameters based on signals received from the sensor. Further, the processor converts the signals received from the sensor into a current evidence grid and removes data from the current evidence grid to form a reduced evidence grid; converts the measurements of historical sections into a historical evidence grid; and correlates the reduced evidence grid with the historical evidence grid by adjusting position and orientation of the reduced evidence grid and the historical evidence grid in relation to one another and calculating correlative values, and searching for a highest correlative value.

Claims

1. A method for correlating evidence grids, the method comprising:

acquiring measurements from a sensor, wherein the sensor generates signals describing a current section of an environment relative to the system;

creating an evidence grid from the measurements, wherein the evidence grid describes the probability that a location within the section of the environment is occupied by an object;

creating a reduced evidence grid from the evidence grid, wherein the reduced evidence grid describes a surface of at least one object within the current section;

correlating the reduced evidence grid with a reduced historical evidence grid by performing a sequential search for a highest correlative value, wherein the sequential search comprises adjusting positions and orientations of the reduced evidence grid and the reduced historical evidence grid in relation to one another and calculating correlative values for the positions and orientations, wherein the adjusted positions and orientations comprises translations and rotations, wherein the translations and the rotations performed in the adjusted positions and orientations are performed to identify the highest correlative value along an individual degree of freedom; and

determining navigational parameters for a navigation system based on the adjusted positions and orientations.

2. The method of claim 1, wherein correlating the reduced evidence grid with a reduced historical evidence grid further comprises limiting the magnitude of the translations and the rotations within an error range for a starting location of the sensor at the time the sensor generated the signals.

3. The method of claim 2, further comprising performing a global search when the sequential search is unable to correlate the reduced evidence grid with the reduced historical evidence grid, wherein the global search compares the reduced evidence grid and the reduced historical evidence grid across the possible rotations and translations in relation to one another.

4. The method of claim 1, further comprising:

dividing the reduced evidence grid into a plurality of evidence grid segments;

dividing the reduced historical evidence grid into at least one historical evidence grid segment,

performing a segmented sequential search to correlate at least one evidence grid segment in the plurality of evidence grid segments against the at least one historical grid segment.

5. The method of claim 1, further comprising checking whether the sequential search found the highest correlative value for the possible relative positions between the reduced evidence grid and the reduced historical evidence grid.

6. The method of claim 5, wherein checking whether the sequential search found the highest correlative value comprises comparing the highest correlative value encountered during the sequential search with correlative values associated with neighboring relative positions, wherein neighboring relative positions are within a translational and rotational range of the relative position that produced the highest correlative value during the sequential search.

7. The method of claim 1, further comprising segmenting the reduced historical evidence grid based on an orientation of a plurality of objects describe in the reduced historical evidence grid.

8. A system comprising:

a sensor configured to generate signals describing a current section of an environment relative to the system;

a memory configured to store measurements of historical sections of the environment relative to the system; and

a processor coupled to the sensor and configured to calculate navigation parameters based on signals received from the sensor;

wherein the processor is configured to convert the signals received from the sensor into a current evidence grid and remove data from the current evidence grid to form a reduced evidence grid;

wherein the processor is configured to convert the measurements of historical sections into a historical evidence grid;

wherein the processor is configured to correlate the reduced evidence grid with the historical evidence grid by performing a sequential search for a highest correlative value, wherein the sequential search comprises finding adjusted positions and orientations of the reduced evidence grid and the historical evidence grid in relation to one another and calculating correlative values for the adjusted positions and orientations, wherein translations and orientations performed in the adjusted positions and orientations are performed to identify the highest correlative value along an individual degree of freedom, and wherein the navigation parameters are calculated based on the adjusted positions and orientations.

9. The system of claim 8, wherein the adjusted position and orientation comprises translations and rotations, wherein the translations are performed sequentially along individual axes in the coordinate space and rotations are performed sequentially about the individual axes.

10. The system of claim 9, wherein the magnitude of the translations and rotations correspond to an error range for a starting location of the system at the time the sensor generated the signals.

11. The system of claim 8, wherein the historical evidence grid comprises a reduced historical evidence grid, wherein the reduced historical evidence grid is the historical evidence grid where data has been removed.

12. The system of claim 8, wherein the processor calculates at least one of a Jacobian and a Hessian for the reduced evidence grid and uses the at least one of the Jacobian, the Hessian, and a simulated annealing method when searching for the highest correlative value.

13. The system of claim 8, wherein the processor is configured to perform a global search for the highest correlative value, wherein the global search compares the reduced evidence grid and the historical evidence grid across possible rotations and translations of the reduced evidence grid and historical evidence grid in relation to one another.

14. The system of claim 8, wherein the processor is configured to perform a segmented sequential search wherein, the processor divides the reduced evidence grid into a plurality of evidence grid segments and divides the historical evidence grid into at least one historical grid segment, wherein the processor correlates at least one evidence grid segment in the plurality of evidence grid segments with the at least one historical grid segment.

15. The system of claim 8, further comprising an inertial sensor configured to provide inertial measurements of the system, wherein the processor calculates a navigation solution for the system based on the inertial measurements and the navigation information.

16. The system of claim 8, wherein the reduced evidence grid contains data for pixels that have an associated probability of occupancy greater than an occupancy threshold.

17. The system of claim 8, wherein the reduced evidence grid contains data for pixels, wherein the difference between the data and information associated with at least one neighboring pixel is greater than a difference threshold.

18. A program product comprising a non-transitory processor-readable medium on which program instructions are embodied, wherein the program instructions cause at least one programmable processor to:

acquire measurements from a sensor, wherein the sensor generates signals describing a current section of an environment relative to the system;

create an evidence grid from the measurements, wherein the evidence grid describes the probability that a location within the section of the environment is occupied by an object;

create a historical evidence grid from historical measurements representing historical sections of the environment;

create a reduced evidence grid from the evidence grid, wherein the reduced evidence grid describes a surface of at least one object within the current section;

create a reduced historical evidence grid from the historical evidence grid, wherein the reduced historical evidence grid describes the surface of the at least one object within the historical sections; and

correlate the reduced evidence grid with the historical evidence grid by adjusting position and orientation of the reduced evidence grid and the historical evidence grid in relation to one another and calculating correlative values for each adjusted position and orientation, and searching for a highest correlative value; and

determine navigational parameters for a navigation system based on the adjusted positions and orientations associated with the highest correlative value.

19. The program product of claim 18, wherein the program instructions are further configured to cause the at least one programmable processor to sequentially adjusts the position and the orientation of the reduced evidence grid by sequentially translating the position of the reduced evidence grid along individual axes in a coordinate space containing the reduced evidence grid and sequentially rotating the reduced evidence grid about the individual axes in the coordinate space.

20. The program product of claim 18, wherein the program instructions are further configured to cause the at least one programmable processor to perform a global search of possible relative positions between the reduced evidence grid and the reduced historical evidence grid.