Plan-view projections of depth image data for object tracking

• US 7,003,136 B1
• Filed: 04/26/2002
• Issued: 02/21/2006
• Est. Priority Date: 04/26/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Harville, Michael
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US10/133,151
• Time in Patent Office: 1,397 Days
• Field of Search: 382/103, 382/118, 382/173, 382/154, 382/199, 382/209, 382/217, 382/276, 382/285, 382/294, 382/312, 382/243, 348/169
• US Class Current: 382/103
• CPC Class Codes: G06T 7/285 using a sequence of stereo image pairs
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: G06V 40/103 Static body considered as a whole, e.g. static pedestrian or occupant recognition

Abstract

Object tracking systems and methods are described. In one aspect, a three-dimensional point cloud is generated from a time series of video frames and partitioned into a set of vertically-oriented bins. The point cloud is mapped into one or more plan-view images each containing for each vertically-oriented bin a corresponding pixel having one or more values computed based upon one or more attributes of the point cloud members occupying the corresponding vertically-oriented bin. The object is tracked based at least in part upon one or more of the plan-view images. In another aspect, one or more original object templates are extracted from at least one of the one or more plan-view images, and the object is tracked based at least in part upon a comparison of at least one of the object templates with regions of the corresponding plan-view images. In another aspect, the point cloud may be discretized along the vertical axis into two or more horizontal partitions.

Claims

1. A method of tracking an object observable in a time series of video frames representative of a visual scene, comprising:

generating a three-dimensional point cloud having members with one or more associated attributes obtained from the time series of video frames and representing selected image pixels in a three-dimensional coordinate system spanned by a ground plane and a vertical axis orthogonal to the ground plane;

partitioning the three-dimensional point cloud into a set of vertically-oriented bins;

mapping the partitioned three-dimensional point cloud into one or more plan-view images each containing for each vertically-oriented bin a corresponding pixel having one or more values computed based upon one or more attributes of the three-dimensional point cloud members occupying the corresponding vertically-oriented bin; and

tracking the object based at least in part upon one or more of the plan-view images.

2. The method of claim 1, wherein pixel values in the one or more plan-view images correspond to a height statistic computed from vertical axis coordinate attributes of three-dimensional point cloud members occupying corresponding vertically-oriented bins.

3. The method of claim 2, wherein the vertical axis coordinate attributes of the three-dimensional point cloud members correspond to heights of the three-dimensional point cloud members relative to the ground plane.

4. The method of claim 3, wherein the height statistic corresponds to a measure summarizing a distributional aspect of the heights of the three-dimensional point cloud members in a vertically-oriented bin.

5. The method of claim 4, wherein the height statistic corresponds to one of a maximum height, a minimum height, a median height, a prescribed percentile height, or a height exceeding heights of a prescribed percentage of other three-dimensional point cloud members in a corresponding vertically-oriented bin.

6. The method of claim 1, further comprising mapping the partitioned three-dimensional point cloud into an occupancy map containing for each vertically-oriented bin a pixel having a value corresponding to a weighted count of the three-dimensional point cloud members occupying the corresponding vertically-oriented bin.

7. The method of claim 6, further comprising smoothing at least one of the one or more plan-view images and the occupancy map.

8. The method of claim 6, further comprising masking at least one of the one or more plan-view images based upon the occupancy map.

9. The method of claim 8, wherein masking comprises removing plan-view image pixels when values of corresponding occupancy map pixels are below a prescribed threshold.

10. The method of claim 9, wherein removing plan-view image pixels comprises setting values of plan-view image pixels to zero.

11. The method of claim 9, further comprising computing the prescribed threshold based upon a measure of three-dimensional point cloud partition resolution and a prescribed maximum height value.

12. The method of claim 6, wherein tracking the object comprises detecting a location in the visual scene likely to contain the object.

13. The method of claim 12, wherein detecting the likely location comprises convolving a box filter with the occupancy map.

14. The method of claim 13, wherein the box filter has a size proportional to an estimate of a physical size of the object.

15. The method of claim 12, wherein detecting comprises performing one or more object classification tests based at least in part on image data from one or more plan view images near locations likely to contain the object.

16. The method of claim 6, wherein tracking the object comprises computing an object template based at least in part upon one or more of the selected plan-view images.

17. The method of claim 16, wherein computing the object template comprises masking one or more of the selected plan-view images based upon the occupancy map and copying a sub-region of the masked plan-view image centered at a location in the visual scene likely to contain the object.

18. The method of claim 16, wherein tracking the object further comprises computing an occupancy map template based at least in part upon the occupancy map.

19. The method of claim 18, wherein computing the object shape template comprises copying a sub-region of the occupancy map centered at a location in the visual scene likely to contain the object.

20. The method of claim 18, further comprising tracking the position and velocity of the object in the one or more selected plan-view images.

21. The method of claim 1, wherein generating the three-dimensional point cloud comprises labeling point cloud members with one or more non-positional attribute values obtained from one or more video streams registered with the time series of video frames of depth image pixels, and pixel values of one or more selected plan-view images are computed based upon one or more non-positional attribute values of the three-dimensional point cloud members occupying corresponding vertically-oriented bins.

22. The method of claim 21, wherein three-dimensional point cloud members are labeled with color attribute values.

23. The method of claim 22, wherein pixel values in the one or more selected plan-view images correspond to a color statistic computed from color attributes of three-dimensional point cloud members occupying corresponding vertically-oriented bins.

24. The method of claim 23, wherein the color statistic corresponds to one of average color, brightest color, or most saturated color.

25. The method of claim 21, wherein pixel values in the one or more selected plan-view images correspond to non-positional attribute values selected based upon a height statistic computed from vertical axis coordinate attributes of three-dimensional point cloud members occupying corresponding vertically-oriented bins.

26. The method of claim 25, wherein pixel values in the one or more selected plan-view images correspond to color values of three-dimensional point cloud members selected based upon the height statistic.

27. The method of claim 21, wherein non-positional attribute values correspond to one or more of infrared sensor reading values, vectors showing estimates of scene motion, and vectors representing local visual texture in the visual scene.

28. The method of claim 1, further comprising segmenting foreground pixels from background pixels before generating the three-dimensional point cloud based at least in part upon one or more of the registered video streams.

29. The method of claim 28, wherein segmenting foreground pixels comprises:

maintaining one or more pixel-level historical models of spatially local pixel observations;

segmenting pixels into two or more labeled groups based at least in part upon comparison of pixel-level video input with the one or more pixel-level historical models; and

updating the one or more pixel-level historical models based at least in part upon one or more feedback maps identifying pixels respectively segmented into the one or more labeled groups in conformity with a spatially non-local segmentation model.

30. The method of claim 1, wherein each plan-view image pixel is associated with multiple values computed based upon multiple attributes of the three-dimensional point cloud members occupying the corresponding vertically-oriented bin.

31. The method of claim 1, wherein partitioning the three-dimensional point cloud further comprises discretizing the three-dimensional point cloud along the vertical axis into two or more horizontal partitions.

32. The method of claim 31, wherein mapping the partitioned three-dimensional point cloud comprises constructing at least one selected plan-view image containing for each vertically-oriented bin a corresponding pixel having one or more values computed based upon one or more attributes of the three-dimensional point cloud members occupying a selected horizontal partition of the corresponding vertically-oriented bin.

33. The method of claim 32, wherein pixel values in the selected plan-view image correspond to a height statistic computed from vertical axis coordinate attributes of three-dimensional point cloud members occupying the selected horizontal partition of the corresponding vertically-oriented bins.

34. The method of claim 32, wherein pixel values in the selected plan-view image correspond to a statistic computed from non-positional attribute values of three-dimensional point cloud members occupying the selected horizontal partition of the corresponding vertically-oriented bins.

35. The method of claim 32, wherein the selected horizontal partition of the corresponding vertically-oriented bins is separated from the ground plane.

36. The method of claim 31, further comprising mapping the partitioned three-dimensional point cloud into an occupancy map containing for each vertically-oriented bin a pixel having a value corresponding to a count of the three-dimensional point cloud members occupying a horizontal partition of the corresponding vertically-oriented bin.

37. The method of claim 31, wherein the three-dimensional point cloud is discretized into horizontal partitions selected based upon a height estimate of the object to be tracked.

38. The method of claim 31, further comprising tracking the object in plan-view images corresponding to multiple horizontal partitions.

39. The method of claim 38, wherein tracking the object comprises combining results of tracking the object in plan-view images corresponding to multiple horizontal partitions.

40. The method of claim 39, wherein combining tracking results comprises detecting plan-view alignment in the results of tracking the object in plan-view images corresponding to multiple horizontal partitions.

41. A system for tracking an object observable in a time series of video frames representative of a visual scene, comprising one or more processing modules operable to:

generate a three-dimensional point cloud having members with one or more associated attributes obtained from the time series of video frames and representing selected image pixels in a three-dimensional coordinate system spanned by a ground plane and a vertical axis orthogonal to the ground plane;

partition the three-dimensional point cloud into a set of vertically-oriented bins;

map the partitioned three-dimensional point cloud into one or more plan-view images each containing for each vertically-oriented bin a corresponding pixel having one or more values computed based upon one or more attributes of the three-dimensional point cloud members occupying the corresponding vertically-oriented bin; and

track the object based at least in part upon one or more of the plan-view images.

42. A method of tracking an object observable in a time series of video frames representative of a visual scene, comprising:

generating a three-dimensional point cloud having members with one or more associated attributes obtained from the time series of video frames and representing selected pixels in a three-dimensional coordinate system spanned by a ground plane and a vertical axis orthogonal to the ground plane;

partitioning the three-dimensional point cloud into a set of vertically-oriented bins;

mapping the partitioned three-dimensional point cloud into one or more plan-view images each containing for each vertically-oriented bin a corresponding pixel having one or more values computed based upon the three-dimensional point cloud members occupying the corresponding vertically-oriented bin;

extracting one or more object templates from at least one of the one or more plan-view images; and

tracking the object based at least in part upon a comparison of at least one of the object templates with regions of the corresponding plan-view images.

43. The method of claim 42, further comprising extracting a re-centered object template based upon a determination that an object template has slipped off the tracked object.

44. The method of claim 43, wherein a re-centered object template is extracted based upon an analysis of pixels within the corresponding object template.

45. The method of claim 44, wherein a re-centered object template is extracted based upon a spatial distribution analysis of pixels within the corresponding object template.

46. The method of claim 45, wherein the spatial distribution analysis comprises analyzing a count of non-zero pixels within the corresponding object template.

47. The method of claim 42, wherein pixel values of one or more selected plan-view images are computed based upon one or more attributes of the three-dimensional point cloud members.

48. The method of claim 47, wherein pixel values of at least one of the one or more selected plan-view images correspond to a height statistic computed from vertical axis coordinate attributes of three-dimensional point cloud members occupying corresponding vertically-oriented bins.

49. The method of claim 47, wherein pixel values of at least one of the one or more selected plan-view images correspond to a statistic computed from non-positional attribute values of three-dimensional point cloud members occupying corresponding vertically-oriented bins.

50. The method of claim 42, wherein of at least one of the one or more selected plan-view images corresponds to an occupancy map containing for each vertically-oriented bin a pixel having a value corresponding to a weighted count of the three-dimensional point cloud members occupying the corresponding vertically-oriented bin.

51. The method of claim 42, wherein partitioning the three-dimensional point cloud further comprises discretizing the three-dimensional point cloud along the vertical axis into two or more horizontal partitions.

52. The method of claim 51, wherein mapping the partitioned three-dimensional point cloud comprises constructing at least one selected plan-view image containing for each vertically-oriented bin a corresponding pixel having one or more values computed based upon one or more attributes of the three-dimensional point cloud members occupying a selected horizontal partition of the corresponding vertically-oriented bin.

53. The method of claim 51, further comprising tracking the object in plan-view images corresponding to multiple horizontal partitions.

54. The method of claim 53, wherein tracking the object comprises combining results of tracking the object in plan-view images corresponding to multiple horizontal partitions.

55. The method of claim 54, wherein combining tracking results comprises detecting plan-view alignment in the results of tracking the object in plan-view images corresponding to multiple horizontal partitions.

56. The method of claim 42, further comprising mapping the partitioned three-dimensional point cloud into an occupancy map containing for each vertically-oriented bin a pixel having a value corresponding to a weighted count of the three-dimensional point cloud members occupying the corresponding vertically-oriented bin.

57. The method of claim 56, wherein computing an object template comprises masking one or more of the selected plan-view images based upon the occupancy map and copying a sub-region of the masked plan-view image centered at a location in the visual scene likely to contain the object.

58. The method of claim 56, wherein tracking the object further comprises computing an occupancy map template based at least in part upon the occupancy map.

59. The method of claim 58, wherein computing an object template comprises copying a sub-region of the occupancy map centered at a location in the visual scene likely to contain the object.

60. The method of claim 58, further comprising tracking the position and velocity of the object in the one or more selected plan-view images.

61. A system for tracking an object observable in a time series of video frames representative of a visual scene, comprising one or more processing modules operable to:

generate a three-dimensional point cloud having members with one or more associated attributes obtained from the time series of video frames and representing selected pixels in a three-dimensional coordinate system spanned by a ground plane and a vertical axis orthogonal to the ground plane;

partition the three-dimensional point cloud into a set of vertically-oriented bins;

map the partitioned three-dimensional point cloud into one or more plan-view images each containing for each vertically-oriented bin a corresponding pixel having one or more values computed based upon the three-dimensional point cloud members occupying the corresponding vertically-oriented bin;

extract one or more original object templates from at least one of the one or more plan-view images;

track the object based at least in part upon a comparison of at least one of object templates with regions of the corresponding plan-view images.

62. A method of tracking an object observable in a time series of video frames representative of a visual scene, comprising:

generating a three-dimensional point cloud having members with one or more associated attributes obtained from the time series of video frames and representing selected image pixels in a three-dimensional coordinate system spanned by a ground plane and a vertical axis orthogonal to the ground plane;

partitioning the three-dimensional point cloud into a set of vertically-oriented bins;

discretizing the three-dimensional point cloud along the vertical axis into two or more horizontal partitions;

mapping the partitioned three-dimensional point cloud into two or more plan-view images each containing for each vertically-oriented bin a corresponding pixel having one or more values computed based upon the three-dimensional point cloud members occupying a respective horizontal partition of the corresponding vertically-oriented bin; and

tracking the object based at least in part upon one or more of the plan-view images.

63. The method of claim 62, wherein pixel values of one or more selected plan-view images are computed based upon one or more attributes of the three-dimensional point cloud members.

64. The method of claim 63, wherein pixel values of the one or more selected plan-view images correspond to a height statistic computed from vertical axis coordinate attributes of three-dimensional point cloud members occupying corresponding vertically-oriented bins.

65. The method of claim 62, wherein pixel values of the one or more selected plan-view images correspond to a statistic computed from non-positional attribute values of three-dimensional point cloud members occupying corresponding vertically-oriented bins.

66. The method of claim 62, wherein at least one of the plan-view images corresponds to an occupancy map containing for each vertically-oriented bin a pixel having a value corresponding to a weighted count of the three-dimensional point cloud members occupying the corresponding vertically-oriented bin.

67. The method of claim 66, further comprising masking at least one of the plan-view images based upon the occupancy map.

68. The method of claim 62, further comprising tracking the object in plan-view images corresponding to multiple horizontal partitions.