K-D tree encoding for point clouds using deviations

Patent metadata

Field	Value
Publication number	US-10496336-B2
Application number	US-201615354669-A
Country	US
Kind code	B2
Filing date	Nov 17, 2016
Priority date	Nov 17, 2016
Publication date	Dec 3, 2019
Grant date	Dec 3, 2019

Abstract

An encoder includes a processor, a buffer, and a memory. The memory includes code as instructions that cause the processor to perform a number of steps. The steps include quantizing geometric data associated with a geometric construct, partitioning the geometric construct, determining a number of points in the partition, generating a deviation value based on the number of points in the partition, storing the deviation value in the buffer, and entropy encoding the deviation value.

First claim

What is claimed is:

1. An encoder comprising:
a processor;
a buffer; and
a memory, the memory including code as instructions that cause the processor to:
quantize geometric data associated with a geometric construct,
partition the geometric construct into a plurality of blocks,
determine a number of points in a block of the plurality of blocks,
generate a deviation value based on the number of points in the block,
store the deviation value in the buffer,
entropy encode the deviation value, and
wherein the deviation value based on the number of points is determined based at least on a number of points in the geometric construct.

2. The encoder of claim 1 , wherein the quantizing of the geometric data includes converting a float or double precision value associated with the geometric data into a b-bit integer representation.

3. The encoder of claim 1 , wherein the geometric data represents a point cloud and the geometric construct is a two or more dimensional shape encompassing the point cloud.

4. The encoder of claim 1 , wherein the partitioning of the geometric construct includes recursively partitioning the geometric construct using a k-D tree.

5. The encoder of claim 1 , wherein
the partitioning of the geometric construct includes partitioning the geometric construct using a k-D tree,
determining whether the block includes more than a threshold number of points,
upon determining the block includes more than the threshold number of points:
store the number of points in the buffer, and
further partition the block including more than the threshold number of points, and

upon determining the block includes less than the threshold number of points:
determine whether the block includes at least one point,
upon determining the block includes at least one point:
the buffer is a first buffer,
the encoder further includes a second buffer, and
store a value representing a position of a point in the second buffer.

6. The encoder of claim 1 , wherein the partitioning of the geometric construct includes partitioning the geometric construct using a k-D tree into a first block and a second block,
the first block includes a third block and a fourth block, and
the deviation value corresponding to the number of points in the third block is determined based on a number of points in the first block.

7. A method comprising:
quantizing geometric data associated with a geometric construct,
partitioning the geometric construct into a plurality of blocks,
determining a number of points in a block of the plurality of blocks,
generate a deviation value based on the number of points in the block,
storing the deviation value in a buffer,
entropy encoding the deviation value, and
wherein the deviation value based on the number of points is determined based at least on a number of points in the geometric construct.

8. The method of claim 7 , wherein the quantizing of the geometric data includes converting a float or double precision value associated with the geometric data into a b-bit integer representation.

9. The method of claim 7 , wherein the geometric data represents a point cloud and the geometric construct is a two or more dimensional shape encompassing the point cloud.

10. The method of claim 7 , wherein the partitioning of the geometric construct includes recursively partitioning the geometric construct using a k-D tree.

11. The method of claim 7 , wherein
the partitioning of the geometric construct includes partitioning the geometric construct using a k-D tree,
determining whether the block includes more than a threshold number of points,
upon determining the block includes more than the threshold number of points:
store the number of points in the buffer, and
further partition the block including more than the threshold number of points, and

upon determining the block includes less than the threshold number of points:
determine whether the block includes at least one point,
upon determining the block includes at least one point:
the buffer is a first buffer,
the encoder further includes a second buffer, and
store a value representing a position of a point in the second buffer.

12. The method of claim 7 , wherein
the partitioning of the geometric construct includes partitioning the geometric construct using a k-D tree into a first block and a second block,
the first block includes a third block and a fourth block, and
the deviation value corresponding to the number of points in the third block is determined based on a number of points in the first block.

13. A decoder comprising:
a processor;
a first buffer;
a second buffer; and
a memory, the memory including code as instructions that cause the processor to:
load the first buffer using data from an encoded geometric data file,
load the second buffer using data from the encoded geometric data file,
entropy decode the first buffer,
determine a first partition in a geometric construct to insert data from the first buffer,
insert a first number of points based on the data from the first buffer into the partition,
determine whether the first number of points is greater than a threshold value,
upon determining the first number of points is greater than the threshold value,
divide the first partition into a second partition and third partition, and
move a subset of the first number of points to one of the second partition or the third partition based on the data from the first buffer,

upon determining the first number of points is less than or equal to the threshold value,
position a point in the first partition based on data in the second buffer, and

repeat the determining whether the first number of points is greater than the threshold value on the second partition or the third partition replacing the first number of points with the subset of the first number of points and until each partition in the geometric construct includes a number of points less than or equal to the threshold value.

14. The decoder of claim 13 , wherein the entropy decoding of the first buffer includes converting a deviation value corresponding to a number of points in the second partition.

15. The decoder of claim 13 , wherein the geometric data file includes geometric data representing a point cloud and the geometric construct is a two or more dimensional shape encompassing the point cloud.

16. The decoder of claim 13 , wherein determining the first partition and determining the second partition includes building a k-D tree based on the first buffer and the second buffer.

17. The decoder of claim 13 , wherein
the entropy decoding of the first buffer includes converting a deviation value corresponding to a number of points in the second partition, and
the deviation value corresponding to the number of points is determined based on a number of points in a larger partition including the partition.

18. The decoder of claim 13 , wherein the second buffer includes data representing a position of a point in the geometric construct.

Assignees

• Google Inc
• Google Llc

Inventors

• Hemmer Michael
• Stava Ondrej

Classifications

• H03M7/24

  Conversion to or from floating-point codes · CPC title

• H03M7/405

  Tree adaptation · CPC title

• G06F3/0673 Primary

  Single storage device · CPC title

• G06T9/40

  Tree coding, e.g. quadtree, octree · CPC title

• H03M7/40 Primary

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title