Processing unordered point cloud

Patent metadata

Field	Value
Publication number	US-9536339-B1
Application number	US-201313916639-A
Country	US
Kind code	B1
Filing date	Jun 13, 2013
Priority date	Jun 13, 2013
Publication date	Jan 3, 2017
Grant date	Jan 3, 2017

Abstract

Described are methods and systems of processing three-dimensional (“3D”) data by generating an edge map, a depth map, or both. Data points are placed into a bin array based their respective image coordinates. The data points in each bin are processed to determine edge data. An edge map may be generated from this edge data. A bin value may be generated based on the data points in each bin, and a depth map generated using these bin values. The edge data and the edge map may be processed using one or more filter functions. Measurements based on the edge map may be provided at a resolution greater than that available with the depth map.

First claim

What is claimed is:

1. A system comprising:
a memory storing computer-executable instructions; and
at least one processor configured to couple to a three-dimensional sensor device, access the memory, and execute the computer-executable instructions to:
access three-dimensional (“3D”) data comprising a plurality of data points, each data point of the plurality of data points comprising a two-dimensional (“2D”) image coordinate and a distance value;
associate each data point of the plurality of data points, using the 2D image coordinate, with at least one bin of a plurality of non-overlapping bins, the plurality of non-overlapping bins forming a bin array of data points comprising the 2D image coordinate and the distance value for each data point;
determine an edge threshold including a designation of one or more conditions used to determine a presence of an edge; and
for the bin of the plurality of non-overlapping bins:
obtain information about a first set of data points and information about a second set of data points, wherein each data point of the first set and each data point of the second set was associated with the bin of the plurality of non-overlapping bins;
compare, using the edge threshold, the information about the first set of data points with the information about the second set of data points;
determine, based at least in part on the comparison, edge segments from edge data, the edge segments indicative of a characterized edge associated with data points having the distance value exceeding the edge threshold by a predetermined amount;
store the edge segments from the edge data, the edge segments indicative of the characterized edge in an edge characterization data table, the edge data including an edge identifier referring to an edge shape and an edge position within the bin; and
generate an edge map using the characterized edge by applying a smoothing function to the edge data to join the edge segments in the plurality of non-overlapping bins to form a continuous edge across the plurality of non-overlapping bins based on the relative position of the plurality of non-overlapping bins in the bin array and the edge data.

2. The system of claim 1 , the computer-executable instructions further configured to generate the edge map by:
accessing a plurality of characterized edges; and
generating a smoothed edge based at least in part on the plurality of characterized edges.

3. The system of claim 1 , wherein the plurality of data points are unordered.

4. The system of claim 1 , the computer-executable instructions further configured to:
determine a depth value for the bin using a portion of the plurality of data points; and
generate a pixelated depth map using the depth value for the bin.

5. A computer-implemented method comprising:
accessing three-dimensional (“3D”) data comprising a plurality of data points, each data point comprising a two-dimensional (“2D”) image coordinate and a distance value;
associating, based at least in part on the 2D image coordinate, each data point of the plurality of data points with at least one bin of a plurality of non-overlapping bins forming a bin array of data points comprising the 2D image coordinate and the distance value for each data point;
comparing an edge threshold to the distance value for each data point of the plurality of data points in each of the plurality of non-overlapping bins to identify an edge in each of the plurality of non-overlapping bins associated with data points having a distance value exceeding the edge threshold by a predetermined amount;
based at least in part on the comparison, determining, from the identified edge, edge data representing edge segments, the edge segments indicative of a characterized edge in an edge characterization data table for each of the plurality of non-overlapping bins;
storing the edge data representing the edge segments in each of the plurality of non-overlapping bins indicative of the characterized edge in the edge characterization data table, the edge data including an edge identifier referring to an edge shape and an edge position; and
generating an edge map using the edge data by applying a smoothing function to the edge data to join the edge segments in each of the plurality of non-overlapping bins to form a continuous edge across the plurality of non-overlapping bins based on a relative position of the plurality of non-overlapping bins in the bin array of data points and the edge data.

6. The computer-implemented method of claim 5 , wherein the generating the edge map is based on a position of the plurality of non-overlapping bins.

7. The computer-implemented method of claim 5 , wherein the generating the edge map is based on a real-world position indicated by the data points in the plurality of non-overlapping bins.

8. The computer-implemented method of claim 5 , further comprising:
generating the 3D data using one or more of:
an optical time-of-flight sensor,
a structured light sensor,
a stereovision sensor,
an interferometer, or
a coded aperture camera.

9. The computer-implemented method of claim 5 , further comprising:
processing the edge map with a classifier to identify one or more objects.

10. The computer-implemented method of claim 5 , the determining the edge data representing the edge segments for each of the plurality of non-overlapping bins comprising:
obtaining information about a first set of data points and information about a second set of data points, wherein each data point of the first set and each data point of the second set is associated with one of the plurality of non-overlapping bins;
comparing, using the edge threshold, the information about the first set of data points with the information about the second set of data points;
determining, based at least in part on the comparison, the edge segments indicative of the characterized edge associated with the data points having the distance value exceeding the edge threshold by the predetermined amount;
determining an edge shape corresponding to the edge segments by comparing the determined edge segments with the edge shapes in the edge characterization data table;
determining edge coordinates of the edge shapes, relative to the one of the plurality of non-overlapping bins including an edge center used to determine placement within a bounded area defined by sub-bin coordinates; and
determining the characterized edge based on the edge shape and the edge coordinates.

11. The computer-implemented method of claim 5 , further comprising:
determining a distance between a first point on a first edge and a second point on a second edge; and
storing the distance.

12. The computer-implemented method of claim 5 , further comprising:
analyzing at least a portion of the data points in one of the bins to determine an average bin depth; and
generate a depth map wherein each pixel corresponds to a bin, and a depth value of each pixel is based on the average bin depth.

13. The computer-implemented method of claim 12 , wherein the edge data is specified to a position within the bin, such that the edge map comprises data at a resolution greater than the depth map.

14. A non-transitory computer readable medium storing instructions, which when executed by a processor, cause the processor to perform actions comprising:
accessing a plurality of data points comprising a two-dimensional (“2D”) image coordinate and a distance value associated with a three-dimensional object, wherein each data point of the plurality of data points is associated with at least one bin of a plurality of non-overlapping bins forming a bin array of data

Assignees

• Amazon Tech Inc

Inventors

• Worley Connor Spencer Blue
• Pauley Devin Bertrum

Classifications

• G06T17/00 Primary

  Three-dimensional [3D] modelling for computer graphics · CPC title

• G06T15/00 Primary

  Three-dimensional [3D] image rendering · CPC title