Method and Apparatus for Generating a Map from Landmarks

• US 20120230550A1
• Filed: 03/10/2011
• Published: 09/13/2012
• Est. Priority Date: 03/10/2011
• Status: Abandoned Application

• Current Assignee: Jacob Kraut
• Original Assignee: Jacob Kraut
• Inventors: Kraut, Jacob
• Application Number:
  US13/044,557
• Publication Number:
  US 20120230550A1
• Time in Patent Office: Days
• US Class Current: 382/113
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• 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: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

A method and apparatus for generating a map from landmarks. The method and apparatus may involve the use of a processor circuit. An embodiment may consist of a platform with a processor circuit, and various different sensors for landmark generation that are known to the art such as a plurality of cameras and/or laser rangefinders. Landmarks are stored in a data structure with their past untransformed landmarks. New landmark data is matched using previous stored untransformed landmarks. Generally current position is only used for matching when backtracking or closing the loop. Landmarks are grouped with other landmarks that are visible in the same time interval. In these groups, dynamic landmarks are identified computationally efficiently using binning. Using basis landmarks in a group, a map relative to these basis landmarks is generated that is translation and rotation invariant. These relative maps are linked together to form a global map. Current position is non cumulative and generated by comparing currently observed landmarks to their global positions. The advantages of this method and apparatus is that it is computationally real time, has dynamic landmark detection and has comparable accuracy to other methods known in the art.

Claims

1. A method for generating a map from landmarks, the method comprising:

(a) comparing a current observation of a landmark to stored previously observed untransformed landmarks from past iterations, if there is no match then comparing the landmark by transforming it to global coordinates using current position, comparing the transformed landmark to globally mapped landmarks, and if there is still is no match then adding the landmark as a new entry,

(b) storing the current observation of a landmark with a plurality of past observations of the same landmark that it is matched to for use in later processing,

(c) grouping new landmarks into groups with other landmarks that are visible at the same time interval,

(d) performing dynamic detection to identify dynamic landmarks by using the approximation that landmarks can be placed into bins, and when bins are compared to each other only one landmark is required from each bin for the comparison,

(e) calculating a relative map for each grouping,

(f) linking together the relative maps of all the groups to generate a global map,

(g) calculating current position using the currently seen landmarks compared to their location on the global map.

2. The method claimed in 1 wherein the landmarks consist of three dimensional points.

3. The method claimed in 1 wherein the landmarks consist of planes or surfaces that may be textured.

4. The method claimed in 1 wherein dynamic detection is also performed when calculating the relative map for each group.

5. The method claimed in 1 wherein a mobile platform is used as a platform for a plurality of processors and sensors for generating a map from landmarks, where the map is used for navigation purposes.

6. The method claimed in 1 wherein a stationary platform is used as a platform for a plurality of processors and sensors for generating a map from landmarks, where the map is used to locate and track dynamic objects in the map.

7. The method claimed in 1 wherein dynamic objects are not present and dynamic detection is not required.

8. The method claimed in 1 wherein the map consists of identifying and tracking only dynamic objects.

9. The method claimed in 1, wherein a position sensor or data such as GPS, or a predictive estimate of location, is used in combination with the said method to match landmarks and align the relative map of the groups to the global map.

10. An apparatus for generating a map from landmarks, the apparatus comprising a processor circuit configured to:

(a) comparing a current observation of a landmark to stored previously observed untransformed landmarks from past iterations, if there is no match then comparing the landmark by transforming it to global coordinates using current position, comparing the transformed landmark to globally mapped landmarks, and if there is still is no match then adding the landmark as a new entry,

(b) storing the current observation of a landmark with a plurality of past observations of the same landmark that it is matched to for use in later processing,

(c) grouping new landmarks into groups with other landmarks that are visible at the same time interval,

(d) performing dynamic detection to identify dynamic landmarks by using the approximation that landmarks can be placed into bins, and when bins are compared to each other only one landmark is required from each bin for the comparison,

(e) calculating a relative map for each grouping,

(f) linking together the relative maps of all the groups to generate a global map,

(g) calculating current position using the currently seen observations compared to their location on the global map.

11. The apparatus claimed in 10 wherein said processor circuit is configured to use landmarks consisting of three dimensional points.

12. The apparatus claimed in 10 wherein said processor circuit is configured to use landmarks consisting of planes or surfaces that may be textured.

13. The apparatus claimed in 10 wherein said processor circuit is configured to perform dynamic detection when calculating the relative map for each group.

14. The apparatus claimed in 10 wherein said processor circuit is configured in a platform with a plurality of processors and sensors for generating a map from landmarks, where the map is used for navigation purposes.

15. The apparatus claimed in 10 wherein said processor circuit is configured in a platform with a plurality of processors and sensors for generating a map from landmarks, where the map is used to locate and track dynamic objects in the map.

16. The apparatus claimed in 10 wherein said processor circuit is configured to not perform dynamic detection since dynamic objects are not present.

17. The apparatus claimed in 10 wherein said processor circuit is configured to identify and track only dynamic objects.

18. The apparatus claimed in 10 wherein said processor circuit is configured to use a position sensor or data such as GPS, or a predictive estimate of location, is used in combination with the said apparatus to match landmarks and align the relative map of the groups to the global map.

19. A method for identifying groups of correlated objects through binning, the method comprising:

(a) placing each object into a separate bin,

(b) comparing each bin to every other bin where only one object from each bin is required for the comparison,

(c) merging bins if the comparison is within a threshold,

(d) flagging bins if the comparison is higher than the threshold so they are not compared again,

(e) using a means to prioritize comparisons.

20. The method claimed in 19, wherein a means of ending the comparison loop is used when a desired grouping is achieved.