Strip histogram grid for efficient segmentation of 3D point clouds from urban environments

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.

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.