Strip histogram grid for efficient segmentation of 3D point clouds from urban environments
First Claim
1. A method of recognizing features 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, a 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, and wherein the z dimension is divided into a plurality of dz portions of the z dimension, so that each strip is divided into a plurality of cells, each cell having a dimension of dx, dy, and dz, 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, and assigning each sensed data point to one of the plurality of dz portions of the z dimension,initializing a ground support variable for each cell of the plurality of cells to zero;
incrementing the ground support variable associated with a respective cell by 1 each time a sensed data point is assigned to that respective cell or a sensed data point is assigned to a cell in a surrounding strip having a same z dimension as the respective cell and being within a set distance of the respective cell; and
estimating the local ground plane for the respective strip as being the lowest z level corresponding to a cell within the respective strip with a respective ground support variable greater than a threshold.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of recognizing features in a 3D environment includes using a sensor that collects a plurality of sensed data points, populating a strip histogram grid having a plurality of strips, each strip having a dx dimension and a dy dimension, 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, and estimating the local ground plane for a strip in the strip histogram grid by using information on each sensed data point assigned to that strip and surrounding strips in the strip histogram grid. Further methods include extracting smooth surfaces, building segmentation, top down segmentation and bottom up segmentation.
35 Citations
31 Claims
-
1. A method of recognizing features 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, a 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, and wherein the z dimension is divided into a plurality of dz portions of the z dimension, so that each strip is divided into a plurality of cells, each cell having a dimension of dx, dy, and dz, 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, and assigning each sensed data point to one of the plurality of dz portions of the z dimension, initializing a ground support variable for each cell of the plurality of cells to zero; incrementing the ground support variable associated with a respective cell by 1 each time a sensed data point is assigned to that respective cell or a sensed data point is assigned to a cell in a surrounding strip having a same z dimension as the respective cell and being within a set distance of the respective cell; and estimating the local ground plane for the respective strip as being the lowest z level corresponding to a cell within the respective strip with a respective ground support variable greater than a threshold. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A method of recognizing features 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, a 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, and wherein the z dimension is divided into a plurality of dz portions of the z dimension, so that each strip is divided into a plurality of cells, each cell having a dimension of dx, dy, and dz, 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, and assigning each sensed data point to one of the plurality of dz portions of the z dimension; estimating the local ground plane for a respective strip as being a z dimension corresponding to a respective cell within the respective strip by using a first number of sensed data points assigned to the respective cell and a second number of sensed data points assigned to cells having the same z dimension in strips surrounding the respective strip in the strip histogram grid and being within a set distance of the respective cell; wherein the local ground plane for a respective strip corresponds to the z dimension of the lowest cell in the respective strip for which the sum of the first number and the second number exceeds a threshold value. - View Dependent Claims (26, 27, 28, 29, 30)
-
-
31. A method of recognizing features 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, a 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, and wherein the z dimension is divided into a plurality of dz portions of the z dimension, so that each strip is divided into a plurality of cells, each cell having a dimension of dx, dy, and dz, 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, and assigning each sensed data point to one of the plurality of dz portions of the z dimension; incrementing a ground support variable associated with a respective cell by 1 each time a sensed data point is assigned to that respective cell or a sensed data point is assigned to a cell in a surrounding strip having a same z dimension as the respective cell and being within a set distance of the respective cell; and estimating the local ground plane for the respective strip as being the lowest z level corresponding to a cell within the respective strip with a respective ground support variable greater than a threshold; estimating a plurality of features for each respective strip in the strip histogram grid; and performing segmentation of the strip histogram grid using the local ground plane estimate for each respective strip and the plurality of features for the strips in the strip histogram grid.
-
Specification