Rapid lidar image correlation for ground navigation

• US 8,818,722 B2
• Filed: 11/22/2011
• Issued: 08/26/2014
• Est. Priority Date: 11/22/2011
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Elgersma, Michael R., Ma, Yunqian
• Primary Examiner(s): Algahaim, Helal A
• Assistant Examiner(s): Han, Charles J
• Application Number:
  US13/302,831
• Publication Number:
  US 20130131984A1
• Time in Patent Office: 1,008 Days
• Field of Search: 701/514, 382/232, 382/199
• US Class Current: 701/514
• CPC Class Codes: G01C 21/1652 with ranging devices, e.g. LIDAR or RADAR
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01S 17/42 Simultaneous measurement of distance and other co-ordinates indirect measurement G01S17/46
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 17/93 for anti-collision purposes
• CPC Class Codes: G01S 7/4802 using analysis of echo signal for target characterisation; Target signature; Target cross-section
• CPC Class Codes: G01S 7/4808 Evaluating distance, position or velocity data
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0278 using satellite positioning signals, e.g. GPS
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/10044 Radar image
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/30181 Earth observation
• CPC Class Codes: G06T 7/74 involving reference images or patches

Abstract

A method includes generating current coarse edge count representation based on current fine grid representation of current section, correlating current edge quantity values of current coarse pixels with historical edge quantity values of historical coarse pixels of historical coarse edge count representation of environment, and identifying first subsection of historical coarse edge count representation with highest correlation to current coarse edge count representation. Each current coarse pixel in current coarse edge count representation represents current fine pixels from current fine grid representation. Fine grid representation of current section of environment is based on data from range and attitude sensor. Each current coarse pixel within current coarse edge count representation includes current edge quantity value that represents quantity of current fine pixels represented by current coarse pixel that include edge. Each historical coarse pixel corresponds to historical fine pixels in historical fine grid representation of environment.

Claims

1. A system comprising:

a range and attitude sensor configured to generate signals relating to a geographic location of at least one object in a current section of an environment relative to the system;

at least one processor coupled to the range and attitude sensor and configured to calculate a navigation solution based on signals received from the range and attitude sensor;

wherein the at least one processor is configured to generate a current coarse edge count representation of the current section of an environment based on a current fine edge representation of the current section of the environment;

wherein the current fine edge representation is based on the signals received from the sensor and includes a plurality of current fine edge pixels, wherein each current fine edge pixel represents a separate current fine edge pixel area of the current section of the environment, wherein each current fine edge pixel indicates whether an edge is present in the respective separate current fine edge pixel area associated with the respective current fine edge pixel;

wherein the current coarse edge count representation includes a plurality of current coarse pixels, wherein each current coarse pixel represents a separate current coarse area of the current section of the environment, wherein the separate current coarse area is larger than the separate current fine edge pixel area and contains a plurality of separate current fine edge pixel areas;

wherein each current coarse pixel in the current coarse edge count representation corresponds to a plurality of current fine grid pixels in a current fine grid representation;

wherein each current coarse pixel in the current coarse edge count representation includes a current edge quantity value that indicates the quantity of the plurality of current fine edge pixels from the current fine edge representation corresponding to the current coarse pixel that include an edge;

wherein the processor is configured to correlate the current edge quantity values of the current coarse pixels of the current coarse edge count representation with historical edge quantity values of historical coarse pixels of a historical coarse edge count representation of the environment, wherein each historical coarse pixel in the historical coarse edge count representation corresponds to a plurality of historical fine pixels in a historical fine grid representation of the environment;

wherein the processor is configured to identify a first subsection of the historical coarse edge count representation that has the highest correlation to the current coarse edge count representation; and

wherein the processor is configured to correlate the current fine edge pixels of the current fine edge representation with a first subsection of the historical fine pixels of the historical fine grid representation that matches the first subsection of the historical coarse edge count representation to identify a geographic location of the range and attitude sensor within the first subsection of the historical fine pixels of the historical fine grid representation.

2. The system of claim 1, wherein the sensor is a LIDAR sensor.

3. The system of claim 1, wherein each current fine grid representation pixel includes a value representing a height of an object in the respective separate current fine edge pixel area of the current section of the environment.

4. The system of claim 3, wherein an edge is indicated in the current fine edge representation when two adjacent current fine grid pixels in the current fine grid representation have heights that differ by more than a threshold.

5. The system of claim 1, wherein the at least one processor is further configured to generate the current fine grid representation of the current section of the environment based on the signals relating to the geographic location of at least one object in the current section of the environment generated by the range and attitude sensor.

6. The system of claim 1, wherein the at least one processor is further configured to generate the current fine edge representation of the current section of the environment by performing edge detection between adjacent current fine grid pixels in the current fine grid representation of the current section.

7. The system of claim 1, wherein the processor is further configured to update the historical fine grid representation based on the current fine grid representation.

8. The system of claim 1, wherein the processor is further configured to generate the historical fine grid representation of the environment based on the signals relating to the geographic location of at least one object in the current section of the environment generated by the range and attitude sensor;

wherein the processor is further configured to generate the historical fine edge representation of the environment based on a comparison of adjacent historical fine grid pixels in the historical fine grid representation of the environment; and

wherein the processor is further configured to generate the historical coarse edge count representation of the environment based on the historical fine edge representation of the environment.

9. A method comprising:

generating, by at least one processor, a current coarse edge count representation of a current section of an environment based on a current fine grid representation of the current section of the environment, wherein each current coarse pixel in the current coarse edge count representation represents a plurality of current fine pixels from the current fine grid representation, wherein the fine grid representation of the current section of the environment is based on data from a range and attitude sensor capable of generating signals relating to a geographic location of at least one object in a current section of the environment;

wherein each current coarse pixel within the current coarse edge count representation includes a current edge quantity value that represents the quantity of the plurality of current fine pixels from the current fine grid representation represented by the current coarse pixel that include an edge;

correlating, by the at least one processor, the current edge quantity values of the current coarse pixels of the current coarse edge count representation with historical edge quantity values of historical coarse pixels of a historical coarse edge count representation of the environment, wherein each historical coarse pixel in the historical coarse edge count representation corresponds to a plurality of historical fine pixels in a historical fine grid representation of the environment;

identifying, by the at least one processor, a first subsection of the historical coarse edge count representation that has the highest correlation to the current coarse edge count representation; and

correlating the current fine pixels of the current fine grid representation with a first subsection of the historical fine pixels of the historical fine grid representation that matches the first subsection of the historical coarse edge count representation to identify a geographic location of the range and attitude sensor within the first subsection of the historical fine pixels of the historical fine grid representation.

11. The method of claim 9, wherein an edge is indicated in the current fine edge representation when two adjacent current fine grid pixels in the current fine grid representation have heights that differ by more than a threshold.

12. The method of claim 9, further comprising:

generating, by the at least one processor, the current fine grid representation of the current section of the environment based on the signals relating to the geographic location of at least one object in the current section of the environment generated by the range and attitude sensor.

13. The method of claim 9, further comprising:

generating, by the at least one processor, the current fine edge representation of the current section of the environment by performing edge detection between adjacent current fine grid pixels in the current fine grid representation of the current section.

14. The method of claim 9, wherein correlating the current edge quantity values with the historical edge quantity values is only impacted by the presence of edges in current coarse pixels that are not in historical coarse pixels.

15. The method of claim 9, further comprising:

generating, by the at least one processor, the historical fine grid representation of the environment based on the signals relating to the geographic location of at least one object in the current section of the environment generated by the range and attitude sensor;

generating, by the at least one processor, the historical fine edge representation of the environment based on a comparison of adjacent historical fine grid pixels in the historical fine grid representation of the environment; and

generating, by the at least one processor, the historical coarse edge count representation of the environment based on the historical fine edge representation of the environment.

19. The system of claim 9, wherein the processor is configured to correlate the current edge quantity values with the historical edge quantity values only based on the presence of edges in current coarse pixels that are not in historical coarse pixels.

10. The method of 9, wherein each current fine grid representation pixel includes a value representing a height of an object in the respective separate current fine edge pixel area of the current section of the environment.

16. A system comprising:

a LIDAR sensor configured to generate signals relating to a geographic location of at least one object in a current section of an environment relative to the system;

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

wherein the processor is configured to generate a current fine grid representation of the current section of the environment based on the signals relating to the geographic location of the at least one object in the current section of the environment generated by the LIDAR sensor, wherein the current fine grid representation includes a plurality of current fine grid pixels, wherein each current fine grid representation pixel includes a value representing a height of an object in a separate current fine edge pixel area of the current section of the environment;

wherein the processor is configured to generate a current fine edge representation of the current section of the environment by performing edge detection between adjacent current fine grid pixels in the current fine grid representation of the current section;

wherein the current fine edge representation includes a plurality of current fine edge pixels, wherein each current fine edge pixel represents the respective separate current fine edge pixel area of the current section of the environment, wherein each current fine edge pixel indicates whether an edge is present in the respective separate current fine edge pixel area associated with the respective current fine edge pixel;

wherein the processor is configured to generate a current coarse edge count representation of the current section of the environment based on the current fine edge representation of the current section of the environment;

wherein the current coarse edge count representation includes a plurality of current coarse pixels, wherein each current coarse pixel represents a separate current coarse area of the current section of the environment, wherein the separate current coarse area is larger than the separate current fine edge pixel area and contains a plurality of separate current fine edge pixel areas;

wherein each current coarse pixel in the current coarse edge count representation corresponds to a plurality of current fine grid pixels in a current fine grid representation;

wherein each current coarse pixel in the current coarse edge count representation includes a current edge quantity value that indicates the quantity of the plurality of current fine edge pixels from the current fine edge representation corresponding to the current coarse pixel that include an edge;

wherein the processor is configured to correlate the current edge quantity values of the current coarse pixels of the current coarse edge count representation with historical edge quantity values of historical coarse pixels of a historical coarse edge count representation of the environment, wherein each historical coarse pixel in the historical coarse edge count representation corresponds to a plurality of historical fine pixels in a historical fine grid representation of the environment;

wherein the processor is configured to identify a first subsection of the historical coarse edge count representation that has the highest correlation to the current coarse edge count representation; and

wherein the processor is configured to correlate the current fine edge pixels of the current fine edge representation with a first subsection of the historical fine pixels of the historical fine grid representation that matches the first subsection of the historical coarse edge count representation to identify a geographic location of the LIDAR sensor within the first subsection of the historical fine pixels of the historical fine grid representation.

17. The system of claim 16, wherein each current fine grid representation pixel includes a value representing a height of an object in the respective separate current fine edge pixel area of the current section of the environment.

18. The system of claim 16, wherein an edge is indicated in the current fine edge representation when two adjacent current fine grid pixels in the current fine grid representation have heights that differ by more than a threshold.

20. The system of claim 16, wherein the processor is further configured to generate the historical fine grid representation of the environment based on the signals relating to the geographic location of at least one object in the current section of the environment generated by the range and attitude sensor;

wherein the processor is further configured to generate the historical fine edge representation of the environment based on a comparison of adjacent historical fine grid pixels in the historical fine grid representation of the environment; and

wherein the processor is further configured to generate the historical coarse edge count representation of the environment based on the historical fine edge representation of the environment.