# US 2020/0349742 A1 · Three-dimensional data encoding method, three-dimensional data decoding method, three-dimensional data encoding device, and three-dimensional data decoding device

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

- Number: US 2020/0349742 A1
- Document ID: US20200349742A1
- Status: Published application
- Kind: A1
- Application number: 16/932,155
- Filed: 2020-07-17
- Published: 2020-11-05
- Earliest claimed: 2018-01-19
- Assignees: Panasonic Intellectual Property Corporation of America
- Applicants: Panasonic Intellectual Property Corporation of America
- Inventors: Chi WANG; Pongsak LASANG; Toshiyasu SUGIO; Tatsuya KOYAMA
- Web page: https://patentgrep.com/patent/US20200349742A1

## CPC

- H03M 13/658: {Scaling by multiplication or division}
- G06F 8/43: {Checking; Contextual analysis}
- G06F 40/146: Coding or compression of tree-structured data
- G06T 9/40: Tree coding, e.g. quadtree, octree
- G06T 15/08: Volume rendering
- G06T 17/00: Three-dimensional [3D] modelling for computer graphics
- H03M 7/3059: {Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression}
- H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A three-dimensional data encoding method includes: generating an N-ary tree structure of three-dimensional points included in three-dimensional data, where N is an integer greater than or equal to 2; generating first encoded data by encoding a first branch using a first encoding process, the first branch having, as a root, a first node included in a first layer that is one of layers included in the N-ary tree structure; generating second encoded data by encoding a second branch using a second encoding process different from the first encoding process, the second branch having, as a root, a second node included in the first layer and different from the first node; and generating a bitstream including the first encoded data and the second encoded data.

## Claims

### Claim 1

A three-dimensional data encoding method, comprising:
generating an N-ary tree structure of three-dimensional points included in three-dimensional data, where N is an integer greater than or equal to 2;
generating first encoded data by encoding a first branch using a first encoding process, the first branch having, as a root, a first node included in a first layer that is one of layers included in the N-ary tree structure;
generating second encoded data by encoding a second branch using a second encoding process different from the first encoding process, the second branch having, as a root, a second node included in the first layer and different from the first node; and
generating a bitstream including the first encoded data and the second encoded data.

### Claim 2 (depends on 1)

The three-dimensional data encoding method according to claim 1,
wherein a total number of three-dimensional points included in the first branch is less than a predetermined threshold value, and
a total number of three-dimensional points included in the second branch is greater than the predetermined threshold value.

### Claim 3 (depends on 2)

The three-dimensional data encoding method according to claim 2,
wherein the first encoded data includes first information in which a first N-ary tree structure of first three-dimensional points included in the first branch is expressed using a first formula, and
the second encoded data includes second information in which a second N-ary tree structure of second three-dimensional points included in the second branch is expressed using a second formula.

### Claim 4 (depends on 3)

The three-dimensional data encoding method according to claim 3,
wherein the first information includes pieces of three-dimensional information each associated with a corresponding one of the first three-dimensional points,
each of the pieces of three-dimensional information includes indexes each associated with a corresponding one of layers in the first N-ary tree structure,
each of the indexes indicates, among N sub-blocks belonging to the corresponding one of the layers in the first N-ary tree structure, a sub-block to which the corresponding one of the first three-dimensional points belongs, and
the second information includes pieces of 1-bit information each of which (i) is associated with a corresponding one of sub-blocks belonging to layers in the second N-ary tree structure, and (ii) indicates whether a three-dimensional point is present in the corresponding one of the sub-blocks.

### Claim 5 (depends on 1)

The three-dimensional data encoding method according to claim 1,
wherein a quantization parameter used in the second encoding process is different from a quantization parameter used in the first encoding process.

### Claim 6 (depends on 1)

The three-dimensional data encoding method according to claim 1,
wherein in the encoding of the first branch, a tree structure including (i) a tree structure from a root of the N-ary tree structure to the first node and (ii) the first branch is encoded using the first encoding process, and
in the encoding of the second branch, a tree structure including (i) a tree structure from the root of the N-ary tree structure to the second node and (ii) the second branch is encoded using the second encoding process.

### Claim 7 (depends on 1)

The three-dimensional data encoding method according to claim 1,
wherein the first encoded data includes encoded data of the first branch, and third information indicating a position of the first node in the N-ary tree structure, and
the second encoded data includes encoded data of the second branch, and fourth information indicating a position of the second node in the N-ary tree structure.

### Claim 8 (depends on 7)

The three-dimensional data encoding method according to claim 7,
wherein the third information includes information indicating the first layer, and information indicating which node included in the first layer the first node is, and
the fourth information includes the information indicating the first layer, and information indicating which node included in the first layer the second node is.

### Claim 9 (depends on 1)

The three-dimensional data encoding method according to claim 1,
wherein the first encoded data includes information indicating a total number of three-dimensional points included in the first branch, and
the second encoded data includes information indicating a total number of three-dimensional points included in the second branch.

### Claim 10

A three-dimensional data decoding method, comprising:
obtaining, from a bitstream, first encoded data and second encoded data, the first encoded data being generated by encoding a first branch having, as a root, a first node included in a first layer that is one of layers included in an N-ary tree structure of three-dimensional points, where N is an integer greater than or equal to 2, the second encoded data being generated by encoding a second branch having, as a root, a second node included in the first layer and different from the first node;
generating first decoded data of the first branch by decoding the first encoded data using a first decoding process;
generating second decoded data of the second branch by decoding the second encoded data using a second decoding process different from the first decoding process; and
restoring the three-dimensional points using the first decoded data and the second decoded data.

### Claim 11 (depends on 10)

The three-dimensional data decoding method according to claim 10,
wherein a total number of three-dimensional points included in the first branch is less than a predetermined threshold value, and
a total number of three-dimensional points included in the second branch is greater than the predetermined threshold value.

### Claim 12 (depends on 11)

The three-dimensional data decoding method according to claim 11,
wherein the first encoded data includes first information in which a first N-ary tree structure of first three-dimensional points included in the first branch is expressed using a first formula, and
the second encoded data includes second information in which a second N-ary tree structure of second three-dimensional points included in the second branch is expressed using a second formula.

### Claim 13 (depends on 12)

The three-dimensional data decoding method according to claim 12,
wherein the first information includes pieces of three-dimensional information each associated with a corresponding one of the first three-dimensional points,
each of the pieces of three-dimensional information includes indexes each associated with a corresponding one of layers in the first N-ary tree structure,
each of the indexes indicates, among N sub-blocks belonging to a corresponding one of the layers in the first N-ary tree structure, a sub-block to which a corresponding one of the first three-dimensional points belongs, and
the second information includes pieces of 1-bit information each of which (i) is associated with a corresponding one of sub-blocks belonging to layers in the second N-ary tree structure, and (ii) indicates whether a three-dimensional point is present in the corresponding one of the sub-blocks.

### Claim 14 (depends on 10)

The three-dimensional data decoding method according to claim 10,
wherein a quantization parameter used in the second decoding process is different from a quantization parameter used in the first decoding process.

### Claim 15 (depends on 10)

The three-dimensional data decoding method according to claim 10,
wherein in the decoding of the first branch, a tree structure including (i) a tree structure from a root of the N-ary tree structure to the first node and (ii) the first branch is decoded using the first decoding process, and
in the decoding of the second branch, a tree structure including (i) a tree structure from the root of the N-ary tree structure to the second node and (ii) the second branch is decoded using the second decoding process.

### Claim 16 (depends on 10)

The three-dimensional data decoding method according to claim 10,
wherein the first encoded data includes encoded data of the first branch, and third information indicating a position of the first node in the N-ary tree structure, and
the second encoded data includes encoded data of the second branch, and fourth information indicating a position of the second node in the N-ary tree structure.

### Claim 17 (depends on 16)

The three-dimensional data decoding method according to claim 16,
wherein the third information includes information indicating the first layer, and information indicating which node included in the first layer the first node is, and
the fourth information includes the information indicating the first layer, and information indicating which node included in the first layer the second node is.

### Claim 18 (depends on 10)

The three-dimensional data decoding method according to claim 10,
wherein the first encoded data includes information indicating a total number of three-dimensional points included in the first branch, and
the second encoded data includes information indicating a total number of three-dimensional points included in the second branch.

### Claim 19

A three-dimensional data encoding device, comprising:
a processor; and
memory,
wherein using the memory, the processor:
generates an N-ary tree structure of three-dimensional points included in three-dimensional data, where N is an integer greater than or equal to 2;
generates first encoded data by encoding a first branch using a first encoding process, the first branch having, as a root, a first node included in a first layer that is one of layers included in the N-ary tree structure;
generates second encoded data by encoding a second branch using a second encoding process different from the first encoding process, the second branch having, as a root, a second node included in the first layer and different from the first node; and
generates a bitstream including the first encoded data and the second encoded data.

### Claim 20

A three-dimensional data decoding device, comprising:
a processor; and
memory,
wherein using the memory, the processor:
obtains, from a bitstream, first encoded data and second encoded data, the first encoded data being generated by encoding a first branch having, as a root, a first node included in a first layer that is one of layers included in an N-ary tree structure of three-dimensional points, where N is an integer greater than or equal to 2, the second encoded data being generated by encoding a second branch having, as a root, a second node included in the first layer and different from the first node;
generates first decoded data of the first branch by decoding the first encoded data using a first decoding process;
generates second decoded data of the second branch by decoding the second encoded data using a second decoding process different from the first decoding process; and
restores the three-dimensional points using the first decoded data and the second decoded data.
