Point cloud geometry compression using octrees with multiple scan orders

Patent metadata

Field	Value
Publication number	US-11620768-B2
Application number	US-202117355830-A
Country	US
Kind code	B2
Filing date	Jun 23, 2021
Priority date	Jun 24, 2020
Publication date	Apr 4, 2023
Grant date	Apr 4, 2023

Abstract

An encoder is configured to compress point cloud geometry information using an octree geometric compression technique that utilizes node groups. Nodes within a node group are scanned according to a breadth first scan order. Sequential node groups to evaluate may be selected according to a breadth first scan order or a depth first scan order based on whether or not the breadth first scan order or the depth first scan order is indicated in a flag in a preceding node group evaluated. In some embodiments, evaluation orders for node groups may be implicit without being signaled via flags. A decoder is configured to reconstruct a point cloud based on a bit stream encoded by the encoder.

First claim

What is claimed is:

1. A non-transitory computer-readable medium storing program instructions that, when executed by one or more processors, cause the one or more processors to:
receive a bit stream comprising:
a plurality of node groups of nodes of an octree structure for a point cloud, wherein the nodes of the octree structure define spatial locations of points of the point cloud, and wherein each node group comprises a sub-set of a set of the nodes of the octree structure for the point cloud; and

reconstruct a geometry of the point cloud based on the nodes included in the respective node groups of the bit stream, wherein to reconstruct the geometry the program instructions cause the one or more processors to:
scan the nodes within a given node group according to a breadth first scan order; and
select a next subsequent node group to evaluate according to a depth first scan order.

2. The non-transitory computer-readable medium of claim 1 , wherein the program instructions, when executed by the one or more processors, cause the one or more processors to:
select the next subsequent node group to evaluate according to the depth first scan based on a flag in the given node group indicating to select the next subsequent node group to evaluate according to the depth first scan order.

3. The non-transitory computer-readable medium of claim 2 , wherein to reconstruct the geometry of the point cloud, the program instructions, cause the one or more processors to:
select a following subsequent node group to evaluate, that follows the next subsequent node group, according to a breadth first scan order, wherein the next subsequent node group does not include a flag indicating to select the following subsequent node group according to the depth first scan order.

4. The non-transitory computer-readable medium of claim 1 , wherein to scan the nodes within a given node group according to the breadth first scan order, the program instructions, cause the one or more processors to:
scan sequential nodes in the node group at a same level of the octree structure, and if an end of the nodes in the same level of the octree structure is reached before an end of the node group is reached, proceed to scan sequential nodes in the node group for a next lower level of the octree structure.

5. The non-transitory computer-readable medium of claim 1 , wherein to select the next subsequent node group to evaluate according to the depth first scan order, the program instructions, cause the one or more processors to:
select a next node group that comprises child nodes at a lower level of the octree structure than parent nodes included in a current node group being evaluated, wherein if the octree structure does not include child nodes at a lower level of the octree structure for the nodes included in the current node group being evaluated, the depth first scan order reverts to a node group comprising parent nodes of the nodes of the current node group being evaluated, wherein the parent nodes are at a higher level of the octree structure than the nodes of the current node group being evaluated and then the depth first scan order proceeds back down to a node group comprising sibling nodes of the nodes of the current node group being evaluated at a same level of the octree structure, if the node group comprising the parent nodes has already been evaluated.

6. The non-transitory computer-readable medium of claim 1 , wherein each of the plurality of node groups represents a spatial volume comprising a plurality of octet cubes of the octree structure at a given octree level of the octree structure.

7. The non-transitory computer-readable medium of claim 6 , wherein the bit stream further comprises:
a slice header for a slice comprising a sub-set of the node groups, and
wherein the slice header indicates a node group size for the sub-set of the node groups included in the slice.

8. The non-transitory computer-readable medium of claim 1 , wherein occupancy information for the nodes of the octree structure included in the plurality of node groups have been encoded using an entropy encoder, and
wherein the program instructions, when executed by the one or more processors, cause the one or more processors to:
determine an encoding context for decoding the occupancy information for respective ones of the nodes, based on occupancy information for neighboring nodes of a given node for which the entropy encoded occupancy information is being decoded,
wherein the neighboring nodes considered for determining the encoding context for a given node are limited to other nodes included in a same node group as the given node.

9. A non-transitory computer-readable medium storing program instructions that, when executed by one or more processors, cause the one or more processors to:
receive a point cloud to be compressed, wherein the point cloud comprises a plurality of points in three-dimensional space;
generate an octree structure that comprises occupancy information for nodes of the octree structure, wherein the occupancy information indicates whether cubes or sub-cubes at a given level of the octree structure are occupied or non-occupied by one or more points of the point cloud;
group the nodes of the octree into a plurality of node groups, wherein each node group comprises a sub-set of the nodes of the octree structure; and
generate a bit stream comprising:
encoded occupancy information for nodes of the octree included in the node groups, wherein the nodes within a given node group are organized according to a breadth first scan order; and
wherein occupancy information for nodes of a subsequent node group to be evaluated are selected according to a depth first scan order between node groups.

10. The non-transitory computer-readable medium of claim 9 , wherein the program instructions, when executed by the one or more processors, cause the one or more processors to:
include a flag in the bit stream indicating the subsequent node group is to be selected for evaluation according to the depth first scan order, wherein otherwise the subsequent node group is selected for evaluation according to a breadth first scan order.

11. The non-transitory computer-readable medium of claim 9 , wherein the program instructions, when executed by the one or more processors, cause the one or more processors to:
select each subsequent node group to be evaluated according to the depth first scanning order for selecting subsequent node groups to be evaluated, wherein nodes within a given node group are entropy decoded according to the breadth first scanning order.

12. The non-transitory computer-readable medium of claim 9 , wherein the program instructions, when executed by the one or more processors, cause the one or more processors to:
select a set of node groups based on a depth first scanning order or a breadth first scanning order such that the set of node groups comprise a quantity of nodes that corresponds to a size of a slice used to transmit a portion of the bit stream.

13. The non-transitory computer-readable medium of claim 9 , wherein the program instructions, when executed by the one or more processors, cause the one or more processors to:
signal in the bit stream for a given slice, a flag indicating a last node group of the slice, wherein a slice comprises a plurality of node groups and a header comprising information for the node groups of the given slice.

14. The non-transitory computer-readable medium of claim 13 , wherein the program instructions, when executed by the one or more processors, cause the one or more processors to:
signal in the slice header for the giv

Assignees

• Apple Inc

Inventors

• Flynn David

Classifications

• G06T9/001

  Model-based coding, e.g. wire frame · CPC title

• H04N19/46

  Embedding additional information in the video signal during the compression process (H04N19/517, H04N19/68, H04N19/70 take precedence) · CPC title

• H04N19/157

  Assigned coding mode, i.e. the coding mode being predefined or preselected to be further used for selection of another element or parameter · CPC title

• G06T9/40 Primary

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

• H04N19/597

  specially adapted for multi-view video sequence encoding · CPC title