# US 2024/0205430 A1 · Block-Based Predictive Coding For Point Cloud Compression

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0205430 A1
- Document ID: US20240205430A1
- Status: Published application
- Kind: A1
- Application number: 18/397,737
- Filed: 2023-12-27
- Published: 2024-06-20
- Earliest claimed: 2019-10-04
- Assignees: Apple Inc.
- Applicants: Apple Inc.
- Inventors: Khaled Mammou; David Flynn; Alexandros Tourapis; Jungsun Kim
- Web page: https://patentgrep.com/patent/US20240205430A1

## CPC

- H04N 19/20: using video object coding
- H04N 19/593: involving spatial prediction techniques
- G06T 9/001: {Model-based coding, e.g. wire frame}
- G06T 9/40: Tree coding, e.g. quadtree, octree
- H04N 19/11: among a plurality of spatial predictive coding modes
- H04N 19/119: Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
- H04N 19/12: Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
- H04N 19/124: Quantisation
- H04N 19/136: Incoming video signal characteristics or properties
- H04N 19/176: the region being a block, e.g. a macroblock
- H04N 19/189: characterised by the adaptation method, adaptation tool or adaptation type used for the adaptive coding
- H04N 19/50: using predictive coding (H04N19/61 takes precedence)
- H04N 19/597: specially adapted for multi-view video sequence encoding
- H04N 19/61: in combination with predictive coding
- H04N 19/647: {using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]}
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

An encoder is configured to compress point cloud information using a blocks of nodes determined from a prediction tree. A prediction tree is generated for a point cloud. Segments of the prediction tree are identified. The segments are divided into blocks that are predicted by predecessor blocks within the segments. The blocks of the prediction tree may then be encoded and may be provided for transmission to a decoder that can regenerate the point cloud from the blocks of the prediction tree.

## Claims

### Claim at position 1

-20. (canceled)

### Claim 21

One or more non-transitory, computer-readable storage media, storing program instructions that when executed on or across one or more computing devices cause the one or more computing devices to:
generate a prediction tree comprising a plurality of nodes that correspond to a plurality of points, wherein to generate the prediction tree, the program instructions cause the one or more computing devices to determine respective nodes values for at least a portion of the plurality of nodes using one or more prediction techniques applied to one or more ancestor nodes of respective nodes of the portion;
identify different segments of the prediction tree;
divide the segments into respective blocks, wherein node values of nodes included in the respective blocks are predicted based on node values of nodes included in one or more predecessor blocks in the segment;
encode the blocks of the prediction tree; and
send or store the encoded blocks.

### Claim 22 (depends on 21)

The one or more non-transitory, computer-readable storage media of claim 21, wherein the one or more prediction techniques comprise:
a delta prediction technique, wherein a node value for a child node is predicted as a difference from a node value of a parent node;
a linear prediction technique, wherein a node value for a child node is predicted based on a relationship between a parent node and a grandparent node of the child node; or
a parallelogram prediction technique, wherein a node value for a child node is determined based on a relationship between a parent node, a grandparent node, and a great grandparent node of the child node.

### Claim 23 (depends on 21)

The one or more non-transitory, computer-readable storage media of claim 21, wherein, to generate the prediction tree, the program instructions cause the one or more computing devices to:
determine respective nodes values for another portion of the plurality of nodes, wherein the respective node values for the other portion of the plurality of nodes are not predicted.

### Claim 24 (depends on 21)

The one or more non-transitory, computer-readable storage media of claim 21, wherein the one or more ancestor nodes comprise one or more parent, grandparent, or great-grandparent nodes.

### Claim 25 (depends on 21)

The one or more non-transitory, computer-readable storage media of claim 21, wherein, to encode the blocks of the prediction tree, the program instructions cause the one or more computing devices to:
apply a transform to residual values of the blocks of the prediction tree; and
apply quantization to coefficients generated from the transformed residual values of the blocks of the prediction tree.

### Claim 26 (depends on 21)

The one or more non-transitory, computer-readable storage media of claim 21, wherein, to identify the different segments of the prediction tree according to a graph traversal technique, the program instructions cause the one or more computing devices to:
traverse nodes of the prediction tree from a root node of the prediction tree to a first leaf node of the prediction tree to identify a first segment of the segments; and
iteratively traverse other nodes of the prediction tree from next nodes identified according to the graph traversal technique to other leaf nodes until remaining nodes in the prediction tree are included in another one of the segments.

### Claim 27 (depends on 21)

The one or more non-transitory, computer-readable storage media of claim 21, wherein the program instructions cause the one or more computing devices to:
apply a transform to residual attribute values for nodes of a block, wherein the transform transforms the residual attribute values of the nodes of the block into transfer function coefficients, and wherein the transform determines the transform function coefficients based on:
relationships between the block and other blocks of the prediction tree; and
geometry relationships between the nodes of the block in a geometry of a point cloud, wherein the point cloud comprises the plurality of points.

### Claim 28 (depends on 21)

The one or more non-transitory, computer-readable storage media of claim 21, wherein a respective prediction technique for predicting node values of one of the blocks is different than a respective prediction technique for predicting node values of another one of the blocks.

### Claim 29

A method, comprising:
generating a prediction tree comprising a plurality of nodes, wherein:
respective ones of the plurality of nodes correspond to respective points that make up a point cloud, wherein generating the prediction tree comprises determining respective nodes values for at least a portion of the plurality of nodes using one or more prediction techniques applied to one or more ancestor nodes of respective nodes of the portion;
identifying different segments of the prediction tree;
dividing the segments into respective blocks, wherein node values of nodes included in the respective blocks are predicted based on node values of nodes included in one or more predecessor blocks in the segment;
encoding the blocks of the prediction tree; and
sending or store the encoded blocks.

### Claim 30 (depends on 29)

The method of claim 29, wherein different prediction techniques of the one or more prediction techniques are signaled for different nodes included in a same block.

### Claim 31 (depends on 30)

The method of claim 30, further comprising:
applying a transform selected for a block to residual values calculated based on predictions that use different prediction techniques for two or more nodes of the block; and
signaling the transform selected for the block at a block-level.

### Claim 32 (depends on 31)

The method of claim 31, wherein:
a first transform is signaled at the block-level for decompressing attribute values of the plurality of nodes; and
a different transform is signaled at the block-level for decompressing geometry values of the plurality of nodes.

### Claim 33 (depends on 31)

The method of claim 31, wherein a quantization parameter to be applied to coefficients resulting from the transform being applied to the residual values is signaled at a block-level.

### Claim 34 (depends on 29)

The method of claim 29, further comprising:
performing a rate distortion optimization (RDO) analysis to determine a number of nodes to be included in the blocks.

### Claim 35 (depends on 29)

The method of claim 29, further comprising:
applying a transform to residual attribute values for nodes of a block, wherein the transform is selected from a set of supported transforms, comprising:
a one-dimensional discrete cosine transform;
a wavelet transform;
a discrete wavelet transform;
a Haar transform;
a Hadamard transform;
a graph transform; or
a lifting scheme.

### Claim 36

One or more non-transitory, computer-readable storage media, storing program instructions that, when executed on or across one or more computing devices, cause the one or more computing devices to:
receive a plurality of encoded blocks of a prediction tree for a plurality of points, wherein the encoded blocks comprise encoded node values;
decode the blocks of the prediction tree, wherein, in decoding the prediction tree, the program instructions cause the one or more computing devices to further:
decode individual ones of the blocks according to respectively determined prediction techniques for the blocks to decode points associated with the blocks; and
store or render the plurality of points decoded from the blocks of the prediction tree.

### Claim 37 (depends on 36)

The one or more non-transitory, computer-readable storage media of claim 36, wherein to decode an individual one of the blocks, the program instructions cause the one or more computing devices to:
apply an inverse transform to coefficient values signaled for the block to determine residual values for nodes of the block,
wherein the inverse transform to be applied is indicated at a block-level.

### Claim 38 (depends on 37)

The one or more non-transitory, computer-readable storage media of claim 37, wherein to decode an individual one of the blocks, the program instructions further cause the one or more computing devices to:
apply an inverse quantization to coefficient values signaled for the block prior to applying the inverse transform,
wherein the inverse quantization to be applied is indicated at the block-level.

### Claim 39 (depends on 37)

The one or more non-transitory, computer-readable storage media of claim 37, wherein to decode an individual one of the blocks, the program instructions further cause the one or more computing devices to:
predict node values for the nodes of a block based on prediction techniques indicated in the encoded blocks; and
apply the residual values to the predicted node values to determine reconstructed node values for the nodes of the block.

### Claim 40 (depends on 36)

The one or more non-transitory, computer-readable storage media of claim 36, wherein the prediction techniques are signaled at a block-level in the encoded blocks.
