Three-dimensional data encoding and decoding methods and devices for N-ary tree structures

Patent metadata

Field	Value
Publication number	US-12167013-B2
Application number	US-202217687846-A
Country	US
Kind code	B2
Filing date	Mar 7, 2022
Priority date	Nov 22, 2017
Publication date	Dec 10, 2024
Grant date	Dec 10, 2024

Abstract

A three-dimensional data encoding method includes: generating first information in which an N-ary tree structure of a plurality of three-dimensional points included in three-dimensional data is expressed using a first formula, where N is an integer of 2 or higher; and generating a bitstream including the first information. The first information includes pieces of three-dimensional point information each associated with a corresponding one of the plurality of three-dimensional points. The pieces of three-dimensional point information each include indexes each associated with a corresponding one of a plurality of levels in the N-ary tree structure. The indexes each indicate a subblock, among N subblocks belonging to a corresponding one of the plurality of levels, to which a corresponding one of the plurality of three-dimensional points belongs.

First claim

What is claimed is:

1. A method for encoding three-dimensional data, comprising:
generating data including position information, with respect to a plurality of three-dimensional points, represented by an N-ary tree structure, where N is an integer of 2 or higher; and
generating a bitstream including the data, wherein
in the generating the data,
determining whether to use a first mode or a second mode to encode each node corresponding to an element of the N-ary tree structure,
encoding each node using the determined mode, wherein in the generating the data,
when determining to use the first mode for encoding a current node, encoding N bit information each indicating an existence of a child node at a particular position in the current node,
when determining to use the second mode for encoding a current node, encoding 3 bit information corresponding to a position of a child node, having a point, of the current node, one of 8 child nodes of the current node being identified by a combination of 3 bits included in the 3 bit information, the 8 child nodes each being the child node.

2. The method according to claim 1 , wherein
in the generating the data,
generating at least part of the data with respect to one or more of the three-dimensional points using both a first node encoded by the first mode and a second node encoded by the second mode, wherein
the first node corresponds to an upper level node or lower level node of the second node.

3. The method according to claim 1 , wherein
in the generating the data,
encoding a first node by the first mode; and
encoding a second node by the second mode, wherein
the first node corresponds to an upper level node or lower level node of the second node.

4. The method according to claim 3 , wherein
the first node includes N sub blocks,
the second node corresponds to a child node of the first node and one coordinate of the N sub blocks.

5. The method according to claim 1 , wherein
the first mode corresponds to an occupancy coding,
the second mode corresponds to a direct coding.

6. A method for decoding three-dimensional data, comprising:
obtaining a bitstream; and
decoding, from the bitstream, data including position information, with respect to a plurality of three-dimensional points, represented by an N-ary tree structure, where N is an integer of 2 or higher, wherein
in the decoding the data,
determining whether to use a first mode or a second mode to decode each node corresponding to an element of the N-ary tree structure,
decoding each node using the determined mode, wherein
in the decoding the data,
when determining to use the first mode for decoding a current node, decoding N bit information each indicating an existence of a child node at a particular position in the current node,

when determining to use the second mode for decoding a current node, decoding 3 bit information corresponding to a position of a child node, having a point, of the current node, one of 8 child nodes of the current node being identified by a combination of 3 bits included in the 3 bit information, the 8 child nodes each being the child node.

7. The method according to claim 6 , wherein
in the decoding the data,
decoding at least part of the data with respect to one or more of the three-dimensional points using both the first mode to decode a first node and the second mode to decode a second node, wherein
the first node corresponds to an upper level node or lower level node of the second node.

8. The method according to claim 6 , wherein
in the decoding the data,
decoding a first node by the first mode; and
decoding a second node by the second mode, wherein
the first node corresponds to an upper level node or lower level node of the second node.

9. The method according to claim 8 , wherein
the first node includes N sub blocks,
the second node corresponds to a child node of the first node and one coordinate of the N sub blocks.

10. The method according to claim 6 , wherein
the first mode corresponds to an occupancy decoding,
the second mode corresponds to a direct decoding.

11. A device for encoding three-dimensional data, comprising:
memory that stores instructions;
a processor that, when executing the instructions stored in the memory, performs a process comprising:
generating data including position information, with respect to a plurality of three-dimensional points, expressed by an N-ary tree structure, where N is an integer of 2 or higher; and
generating a bitstream including the data, wherein
in the generating the data,
determining whether to set a first mode or a second mode to encode each node corresponding to an element of the N-ary tree structure,
encoding each node using the determined mode, wherein
in the generating the data,
when determining to use the first mode for encoding a current node, encoding N bit information each indicating an existence of a child node at a particular position in the current node,

when determining to use the second mode for encoding a current node, encoding 3 bit information corresponding to a position of a child node, having a point, of the current node, one of 8 child nodes of the current node being identified by a combination of 3 bits included in the 3 bit information, the 8 child nodes each being the child node.

12. A device for decoding three-dimensional data, comprising:
memory that stores instructions;
a processor that, when executing the instructions stored in the memory, performs a process comprising:
obtaining a bitstream; and
decoding, from the bitstream, data including position information, with respect to a plurality of three-dimensional points, expressed by an N-ary tree structure, where N is an integer of 2 or higher, wherein
in the decoding the data,
determining whether to use a first mode or a second mode to decode each node corresponding to an element of the N-ary tree structure,
decoding each node using the determined mode, wherein
in the decoding the data,
when determining to use the first mode for decoding a current node, decoding N bit information each indicating an existence of a child node at a particular position in the current node,

when determining to use the second mode for decoding a current node, decoding 3 bit information corresponding to a position of a child node, having a point, of the current node one of 8 child nodes of the current node being identified by a combination of 3 bits included in the 3 bit information, the 8 child nodes each being the child node.

Assignees

• Panasonic Ip Corp America

Inventors

• Wang Chi
• Lasang Pongsak
• Sugio Toshiyasu
• Koyama Tatsuya

Classifications

• G06T9/40 Primary

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

• H04N19/96

  Tree coding, e.g. quad-tree coding · CPC title

• H04N19/597 Primary

  specially adapted for multi-view video sequence encoding · 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

• H04N19/176

  the region being a block, e.g. a macroblock · CPC title