System and method for tracking objects

• US 8,565,481 B1
• Filed: 05/26/2011
• Issued: 10/22/2013
• Est. Priority Date: 05/26/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Smith, Russell Leigh
• Primary Examiner(s): BHATNAGAR, ANAND P
• Application Number:
  US13/116,553
• Time in Patent Office: 880 Days
• Field of Search: 382/100, 382/103, 382/106, 382/107, 348169-172, 702/127, 702/142, 702/143, 702/150, 702/152, 702/153, 701/23, 701/300, 701/400
• US Class Current: 382/103
• CPC Class Codes: G01S 11/12 using electromagnetic waves other than radio waves
• CPC Class Codes: G01S 13/726 Multiple target tracking
• CPC Class Codes: G01S 13/865 Combination of radar systems with lidar systems
• CPC Class Codes: G01S 13/867 Combination of radar systems with cameras
• CPC Class Codes: G01S 17/86 Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
• CPC Class Codes: G06F 18/256 of results relating to different input data, e.g. multimodal recognition
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/811 the classifiers operating on different input data, e.g. multi-modal recognition
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces

Abstract

Embodiments of a system and method for tracking objects are described herein. Aspects of this disclosure efficiently update object “belief” data by creating a bitmap representation of object locations and velocities. The bitmap provides a three-dimensional representation of the object as viewed by one or more sensors. The bitmap representations are blended with sensor data over time to determine a current object belief state which can accurately account for asynchronous sensor data. Peaks in the belief data, which may be represented by pixels with an intensity value above a threshold value, are identified as likely objects. Additional sensor data is used to detect longitudinal velocities located at one or more of the peaks.

Claims

1. A computer-implemented method for tracking objects, the method comprising:

receiving a first set of input from at least one of one or more sensors to perceive an environment;

generating, with a processor, a first three-dimensional bitmap corresponding to an environmental state as perceived by the one or more sensors, from the first set of input, the first three-dimensional bitmap being comprised of a plurality of pixels; and

determining an object position using the first three-dimensional bitmap using a processor;

wherein the three dimensions of the first three-dimensional bitmap correspond to a first environmental position along an x axis, a second environmental position along a y axis, and a lateral velocity, and wherein an intensity of each pixel at a particular coordinate of the bitmap represents a likelihood that an object is at a location within the environment corresponding to the particular coordinate of the three-dimensional bitmap.

2. The method of claim 1, further comprising modifying the first set of input received from the at least one of the one or more sensors from a four-dimensional representation to a three-dimensional representation by eliminating a longitudinal velocity from the received input.

3. The method of claim 2, further comprising:

identifying a peak of intensity within the first three-dimensional bitmap; and

determining longitudinal velocity of an object located at the intensity peak.

4. The method of claim 3, wherein the longitudinal velocity is determined using a radar sensor.

5. The method of claim 1, further comprising providing the determined object positions to an autonomous vehicle.

6. The method of claim 1, wherein the sensors comprise at least one of a camera, a laser scanner, and a radar detector.

7. The method of claim 1, further comprising:

receiving a second set of input from at least one of the one or more sensors;

and

generating a new environmental state by painting the first set of input and the second set of input into a second three-dimensional bitmap, wherein the second three-dimensional bitmap represents an updated environmental state incorporating the second set of input.

8. A processing system for tracking objects comprising:

at least one sensor for perceiving an environment and providing a first set of input describing the environment;

an object tracking module;

a processor for management of the object tracking module; and

a memory coupled to the processor, for storing a first three-dimensional bitmap representing an environmental state as perceived by the at least one sensor;

wherein the object tracking module is configured to generate the first three-dimensional bitmap from the first set of input, the bitmap comprised of a plurality of pixels, and to determine an object position using the first three-dimensional bitmap.

9. The processing system of claim 8, wherein the three dimensions of the first three-dimensional bitmap correspond to a first position along an x axis, a second position along a y axis, and a lateral velocity, and wherein an intensity of each pixel at a particular coordinate within the bitmap represents a likelihood that an object is at a location within an environment, as perceived by the at least one sensor corresponding to the particular coordinate.

10. The processing system of claim 8, further comprising a graphics processing unit configured to generate the first three dimensional bitmap.

11. The processing system of claim 10, wherein the graphics processing unit is further configured to perform a blending operation between the first set of input and a second set of input to generate a second three-dimensional bitmap corresponding to a new environmental state as perceived by the at least one sensor.

12. The processing system of claim 10, wherein the at least one sensor comprises at least one radar sensor, and the object tracking module is further configured to identify one or more intensity peaks within the three-dimensional bitmap and to determine a longitudinal velocity at each intensity peak using the at least one radar detector.

13. The processing system of claim 8, wherein the processor is further configured to store the first set of input for use in conjunction with a second set of input to generate a new environmental state by painting each set of input into a three-dimensional bitmap.

14. A tangible, non-transitory, computer-readable storage medium comprising instructions that, when executed by a processor, perform a method comprising:

receiving a first set of input from at least one of one or more sensors to perceive an environment;

generating, with a processor, a first three-dimensional bitmap corresponding to an environmental state as perceived by the one or more sensors, from the first set of input, the first three-dimensional bitmap being comprised of a plurality of pixels; and

determining an object position using the first three-dimensional bitmap using a processor;

wherein the three dimensions of the first three-dimensional bitmap correspond to a first environmental position along an x axis, a second environmental position along a y axis, and a lateral velocity, and wherein an intensity of each pixel at a particular coordinate of the bitmap represents a likelihood that an object is at a location within the environment corresponding to the particular coordinate of the three-dimensional bitmap.

15. The non-transitory computer-readable storage medium of claim 14, further comprising:

modifying the first set of input received from the sensors from a four-dimensional representation to a three-dimensional representation by eliminating a longitudinal velocity from the received input.

16. The non-transitory computer-readable storage medium of claim 15, further comprising:

identifying a peak of intensity within the first three-dimensional bitmap; and

determining a longitudinal velocity of an object at an environmental position corresponding to the peak.

17. The non-transitory computer-readable storage medium of claim 16, wherein the longitudinal velocity is determined using a radar sensor.

18. The non-transitory computer-readable storage medium of claim 15, wherein the sensors comprise at least one of a camera, a laser scanner, and a radar detector.

19. The non-transitory computer-readable storage medium of claim 14, further comprising:

providing the determined object positions to an autonomous driving system.

20. The non-transitory computer-readable storage medium of claim 14, further comprising:

receiving a second set of input from at least one of the one or more sensors; and

generating a new environmental state by blending the first set of input with the second set of input by painting each set of input into a second three-dimensional bitmap.