Recognizing geometrically salient objects from segmented point clouds using strip grid histograms

• US 8,396,293 B1
• Filed: 12/22/2009
• Issued: 03/12/2013
• Est. Priority Date: 12/22/2009
• Status: Active Grant

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Korah, Thommen, Medasani, Swarup S., Owechko, Yuri
• Primary Examiner(s): Wu, Jingge
• Application Number:
  US12/644,751
• Time in Patent Office: 1,176 Days
• Field of Search: 382168-171
• US Class Current: 382/171
• CPC Class Codes: G06V 20/13 Satellite images

Abstract

A method of recognizing geometrically salient objects from sensed data points collected in a 3D environment includes using a sensor that collects a plurality of sensed data points each having spatial coordinate information in three dimensions x, y and z, populating a strip histogram grid having a plurality of strips, each strip having a z, dx and dy dimensions, wherein dx is a portion of an x dimension and dy is a portion of a y dimension of the strip histogram grid, by assigning each sensed data point to a strip that has x, y and z dimensions that encompass the spatial coordinate information of the respective assigned sensed data point, and segmenting the strip histogram grid into a plurality of segmented regions, each segmented region comprising one strip or a group of neighboring strips having similar attributes.

Claims

1. A method of recognizing geometrically salient objects from sensed data points collected in a 3D environment comprising:

sensing the 3D environment using a sensor that collects a plurality of sensed data points from the 3D environment, each sensed data point having spatial coordinate information in three dimensions x, y and z;

populating a strip histogram grid having a plurality of strips, each strip having a z, an dx dimension and a dy dimension, wherein dx is a portion of an x dimension of the strip histogram grid and dy is a portion of a y dimension of the strip histogram grid, by assigning each sensed data point to a strip in the strip histogram grid that has x, y and z dimensions that encompass the spatial coordinate information of the respective assigned sensed data point;

segmenting the strip histogram grid into a plurality of segmented regions, each segmented region comprising one strip or a group of neighboring strips having similar attributes; and

determining for each strip in the strip histogram grid whether the respective strip has a smoothness S^sm property;

wherein the respective strip is determined as having the smoothness S^sm property if a range in local height gradient S^zslope for strips within a strip neighborhood of the respective strip is less than a threshold T_z.

2. The method of claim 1 further comprising:

labeling a segmented region as woods or a forested region if a respective segmented region has a segmented region height greater than a height threshold, a segmented region area greater than an area threshold, and the segmented region has no strip within the segmented region having the S^sm smoothness property.

3. The method of claim 1 wherein determining for each strip in the strip histogram grid whether the respective strip has a smoothness S^sm property comprises:

computing partial derivatives of strip height S^H, wherein strip height is a maximum z dimension S^max for an assigned sensed data point in a respective strip, along x and y axes for strips in a 3×

3 strip neighborhood of the respective strip;

estimating a local height gradient S^zslope for the respective strip from the partial derivatives; and

labeling the respective strip as smoothness S^sm=true if a range in local height gradient S^zslope for the strips within the 3×

3 strip neighborhood of the respective strip is less than a threshold T.

4. The method of claim 3 wherein:

dx and dy are each equal to 32 cm; and

the threshold T_z is less than 10.

5. The method of claim 3 wherein only 5 out of 8 of the strips within the 3×

3 strip neighborhood of the respective strip have a threshold T_z less than 10.

6. The method of claim 2 wherein the height threshold is 10 meters and the area threshold is 200 square meters.

7. A method of recognizing geometrically salient objects from sensed data points collected in a 3D environment comprising:

sensing the 3D environment using a sensor that collects a plurality of sensed data points from the 3D environment, each sensed data point having spatial coordinate information in three dimensions x, y and z;

populating a strip histogram grid having a plurality of strips, each strip having a z, an dx dimension and a dy dimension, wherein dx is a portion of an x dimension of the strip histogram grid and dy is a portion of a y dimension of the strip histogram grid, by assigning each sensed data point to a strip in the strip histogram grid that has x, y and z dimensions that encompass the spatial coordinate information of the respective assigned sensed data point;

segmenting the strip histogram grid into a plurality of segmented regions, each segmented region comprising one strip or a group of neighboring strips having similar attributes; and

labeling a segmented region as merged cars if a respective segmented region has a segmented region height less than a height threshold, a segmented region moment width greater or equal to a first width threshold and less than or equal to a second width threshold, a segmented region moment length greater than a length threshold, and a segmented region area divided by the segmented region moment length times the segmented region moment width greater than a ratio threshold.

8. The method of claim 7 wherein the merged cars are labeled as parallel parked cars if:

the height threshold is 3.6 meters;

the first width threshold is 2.0 meters;

the second width threshold is 2.9 meters;

the length threshold is 8.0 meters; and

the ratio threshold is 0.8.

9. The method of claim 7 wherein the merged cars are labeled as cars parked side to side in a parking lot if:

the height threshold is 3.6 meters;

the first width threshold is 4.1 meters;

the second width threshold is 6.5 meters;

the length threshold is 5.0 meters; and

the ratio threshold is 0.65.

10. A method of recognizing geometrically salient objects from sensed data points collected in a 3D environment comprising:

sensing the 3D environment using a sensor that collects a plurality of sensed data points from the 3D environment, each sensed data point having spatial coordinate information in three dimensions x, y and z;

populating a strip histogram grid having a plurality of strips, each strip having a z, an dx dimension and a dy dimension, wherein dx is a portion of an x dimension of the strip histogram grid and dy is a portion of a y dimension of the strip histogram grid, by assigning each sensed data point to a strip in the strip histogram grid that has x, y and z dimensions that encompass the spatial coordinate information of the respective assigned sensed data point;

segmenting the strip histogram grid into a plurality of segmented regions, each segmented region comprising one strip or a group of neighboring strips having similar attributes;

performing bottom up segmentation to form segmented regions R_bup having populated strips projecting up from a local ground plane estimate;

determining for each strip a longest array of consecutively populated cells from the local ground plane estimate for the strip to compute a bottom-up height S^C, wherein each strip is divided into a plurality of cells, each cell having a dimension of dx, dy, and dz; and

labeling a R_bup segmented region as a pole if the respective R_bup segmented region contains no more than a threshold number of strips and the bottom-up height S^C for a strip in the respective R_bup segmented region is greater than a height threshold.

11. The method of claim 10 wherein:

dx and dy are each equal to 32 cm;

the threshold number of strips is 2; and

the height threshold is 7 meters.

12. The method of claim 10 wherein:

a cell is considered populated if a vertical Gaussian weighted population of the cell and neighboring cells in the strip is greater than a population threshold.

13. The method of claim 10 wherein:

the population threshold is 5.

14. A method of recognizing geometrically salient objects from sensed data points collected in a 3D environment comprising:

sensing the 3D environment using a sensor that collects a plurality of sensed data points from the 3D environment, each sensed data point having spatial coordinate information in three dimensions x, y and z;

populating a strip histogram grid having a plurality of strips, each strip having a z, an dx dimension and a dy dimension, wherein dx is a portion of an x dimension of the strip histogram grid and dy is a portion of a y dimension of the strip histogram grid, by assigning each sensed data point to a strip in the strip histogram grid that has x, y and z dimensions that encompass the spatial coordinate information of the respective assigned sensed data point;

segmenting the strip histogram grid into a plurality of segmented regions, each segmented region comprising one strip or a group of neighboring strips having similar attributes;

labeling a segmented region as a construction crane if the respective segmented region contains at least one strip having a height above a ground plane estimate for the strip greater than a height threshold, an area for the respective segmented region is greater than an area threshold, the respective segmented region has not been identified as a building, and no adjacent strip S_i to the respective segmented region belongs to a building.

15. The method of claim 14 wherein:

the height threshold is 35 meters; and

the area threshold is 5 square meters.

16. A method of recognizing geometrically salient objects from sensed data points collected in a 3D environment comprising:

sensing the 3D environment using a sensor that collects a plurality of sensed data points from the 3D environment, each sensed data point having spatial coordinate information in three dimensions x, y and z;

populating a strip histogram grid having a plurality of strips, each strip having a z, an dx dimension and a dy dimension, wherein dx is a portion of an x dimension of the strip histogram grid and dy is a portion of a y dimension of the strip histogram grid, by assigning each sensed data point to a strip in the strip histogram grid that has x, y and z dimensions that encompass the spatial coordinate information of the respective assigned sensed data point;

determining a height S^H=maximum z for each strip in the strip histogram grid and storing the height S^H for each strip in computer readable memory; and

marking a respective strip in the strip histogram grid as a potential power line strip if there are a threshold number of unpopulated cells below the height S^H for the respective strip and the height S^H for the respective strip is greater than a height threshold;

wherein each strip is divided into a plurality of cells, each cell having a dimension of dx, dy, and dz.

17. The method of claim 16 wherein:

dx, dy and dz are each equal to 32 cm;

the threshold number of unpopulated cells is 4; and

the height threshold is 4 meters.

18. The method of claim 16 further comprising:

forming a 3D image I_pl having token strips having a resolution of dx, dy equal to strips in the strip histogram grid in the x and y dimensions, and token strip heights in the Z dimension set equal to the height S^H for each respective strip in the strip histogram grid marked as a potential power line;

identifying lines of token strips having height S^H greater than zero in the 3D image I_pl;

removing from the 3D image I_pl any lines of token strips having a length less than a length threshold; and

labeling any strip in the strip histogram grid that corresponds to a token strip in the 3D image I_pl as a power line strip.

19. The method of claim 18 wherein:

dx and dy are each equal to 32 cm; and

the length threshold is 20.

20. The method of claim 18 wherein identifying lines of token strips comprises:

using a Hough transform.

21. A method of recognizing geometrically salient objects from sensed data points collected in a 3D environment comprising:

sensing the 3D environment using a sensor that collects a plurality of sensed data points from the 3D environment, each sensed data point having spatial coordinate information in three dimensions x, y and z;

populating a strip histogram grid having a plurality of strips, each strip having a z, an dx dimension and a dy dimension, wherein dx is a portion of an x dimension of the strip histogram grid and dy is a portion of a y dimension of the strip histogram grid, by assigning each sensed data point to a strip in the strip histogram grid that has x, y and z dimensions that encompass the spatial coordinate information of the respective assigned sensed data point;

determining for each strip a longest array of consecutively populated cells from a local ground plane estimate for the strip to compute a bottom-up height S^C, wherein each strip is divided into a plurality of cells, each cell having a dimension of dx, dy, and dz; and

labeling a respective strip as a potential post if the bottom-up height S^C for the respective strip is less than or equal to a height threshold, the cells for the respective strip are unpopulated for a distance threshold above the bottom-up height S^C, and the cells up to the bottom-up height S^C for the respective strip are populated with at least a population threshold number of sensed data points.

22. The method of claim 21 wherein:

the height threshold is 1.5 meters;

the distance threshold is 1.5 meters; and

the population threshold number is 40.

23. The method of claim 21 further comprising:

merging adjacent potential post strips into a segmented post region if the adjacent potential post strips is less than a merge threshold number.

24. The method of claim 23 wherein:

dx, dy and dz are each equal to 32 cm; and

the merge threshold number is 4.