US7003136B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Plan-view projections of depth image data for object tracking
Assignee: Qualcomm Inc
•
Filing: 2002-04-26
•
Granted: 2006-02-21
•
Expires: 2022-04-26
Abstract
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.
Inventors
- 👤 Michael Harville
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 16:37
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/20; G06T7/285; G06V; G06V10/00; G06V10/40; G06V10/50; G06V10/507; G06V20/00; G06V20/60; G06V20/64; G06V40/00; G06V40/10; G06V40/103
Claims Analysis
Total Claims: 73
Claim 1
Independent Claim
137 words
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.
Claim 2
Independent Claim
137 words
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.
Claim 3
Dependent Claim
36 words
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.
Claim 4
Dependent Claim
32 words
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.
Claim 5
Dependent Claim
31 words
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.
Claim 6
Dependent Claim
47 words
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.
Claim 7
Dependent Claim
44 words
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.
Claim 8
Dependent Claim
23 words
The method of claim 6 , further comprising smoothing at least one of the one or more plan-view images and the occupancy map.
Claim 9
Dependent Claim
24 words
The method of claim 6 , further comprising masking at least one of the one or more plan-view images based upon the occupancy map.
Claim 10
Dependent Claim
25 words
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.
Claim 11
Dependent Claim
20 words
The method of claim 9 , wherein removing plan-view image pixels comprises setting values of plan-view image pixels to zero.
Claim 12
Dependent Claim
28 words
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.
Claim 13
Dependent Claim
23 words
The method of claim 6 , wherein tracking the object comprises detecting a location in the visual scene likely to contain the object.
Claim 14
Dependent Claim
20 words
The method of claim 12 , wherein detecting the likely location comprises convolving a box filter with the occupancy map.
Claim 15
Dependent Claim
24 words
The method of claim 13 , wherein the box filter has a size proportional to an estimate of a physical size of the object.
Claim 16
Dependent Claim
38 words
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.
Claim 17
Dependent Claim
29 words
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.
Claim 18
Dependent Claim
48 words
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.
Claim 19
Dependent Claim
26 words
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.
Claim 20
Dependent Claim
33 words
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.
Claim 21
Dependent Claim
24 words
The method of claim 18 , further comprising tracking the position and velocity of the object in the one or more selected plan-view images.
Claim 22
Dependent Claim
73 words
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.
Claim 23
Dependent Claim
17 words
The method of claim 21 , wherein three-dimensional point cloud members are labeled with color attribute values.
Claim 24
Dependent Claim
35 words
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.
Claim 25
Dependent Claim
22 words
The method of claim 23 , wherein the color statistic corresponds to one of average color, brightest color, or most saturated color.
Claim 26
Dependent Claim
43 words
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.
Claim 27
Dependent Claim
32 words
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.
Claim 28
Dependent Claim
36 words
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.
Claim 29
Dependent Claim
34 words
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.
Claim 30
Dependent Claim
89 words
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.
Claim 31
Dependent Claim
32 words
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.
Claim 32
Dependent Claim
29 words
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.
Claim 33
Dependent Claim
57 words
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.
Claim 34
Dependent Claim
40 words
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.
Claim 35
Dependent Claim
38 words
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.
Claim 36
Dependent Claim
22 words
The method of claim 32 , wherein the selected horizontal partition of the corresponding vertically-oriented bins is separated from the ground plane.
Claim 37
Dependent Claim
47 words
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.
Claim 38
Dependent Claim
28 words
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.
Claim 39
Dependent Claim
19 words
The method of claim 31 , further comprising tracking the object in plan-view images corresponding to multiple horizontal partitions.
Claim 40
Dependent Claim
25 words
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.
Claim 41
Dependent Claim
29 words
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.
Claim 42
Independent Claim
144 words
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.
Claim 43
Independent Claim
144 words
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.
Claim 44
Independent Claim
158 words
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.
Claim 45
Independent Claim
158 words
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.
Claim 46
Dependent Claim
27 words
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.
Claim 47
Dependent Claim
24 words
The method of claim 43 , wherein a re-centered object template is extracted based upon an analysis of pixels within the corresponding object template.
Claim 48
Dependent Claim
26 words
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.
Claim 49
Dependent Claim
23 words
The method of claim 45 , wherein the spatial distribution analysis comprises analyzing a count of non-zero pixels within the corresponding object template.
Claim 50
Dependent Claim
30 words
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.
Claim 51
Dependent Claim
41 words
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.
Claim 52
Dependent Claim
39 words
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.
Claim 53
Dependent Claim
50 words
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.
Claim 54
Dependent Claim
29 words
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.
Claim 55
Dependent Claim
57 words
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.
Claim 56
Dependent Claim
19 words
The method of claim 51 , further comprising tracking the object in plan-view images corresponding to multiple horizontal partitions.
Claim 57
Dependent Claim
25 words
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.
Claim 58
Dependent Claim
29 words
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.
Claim 59
Dependent Claim
44 words
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.
Claim 60
Dependent Claim
48 words
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.
Claim 61
Dependent Claim
26 words
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.
Claim 62
Dependent Claim
32 words
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.
Claim 63
Dependent Claim
24 words
The method of claim 58 , further comprising tracking the position and velocity of the object in the one or more selected plan-view images.
Claim 64
Independent Claim
164 words
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.
Claim 65
Independent Claim
164 words
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.
Claim 66
Independent Claim
152 words
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.
Claim 67
Independent Claim
152 words
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.
Claim 68
Dependent Claim
30 words
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.
Claim 69
Dependent Claim
37 words
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.
Claim 70
Dependent Claim
35 words
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.
Claim 71
Dependent Claim
45 words
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.
Claim 72
Dependent Claim
21 words
The method of claim 66 , further comprising masking at least one of the plan-view images based upon the occupancy map.
Claim 73
Dependent Claim
19 words
The method of claim 62 , further comprising tracking the object in plan-view images corresponding to multiple horizontal partitions.
References Cited (Backward Citations)
US5293580A
Cited
US5960097A
Cited
WO1999006940A1
Cited
US6188777B1
Cited
US6421451B2
Cited
US6837432B2
Cited
US6697502B2
Cited
US6829384B2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-02-20 | 2009-08-22 | 2010-02-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-02-20 | 2013-08-22 | 2014-02-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-02-20 | 2017-08-22 | 2018-02-21 | $7700.00 | Window Closed / Lapsed |