# US 12,191,887 B2 · 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 12,191,887 B2 - Document ID: US12191887B2 - Status: Granted - Kind: B2 - Application number: 17/952,682 - Filed: 2022-09-26 - Published: 2023-01-19 - Granted: 2025-01-07 - 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/US12191887B2 ## 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 method for encoding there-dimensional data, comprising: encoding a first node, using a first encoding process, included in one of levels in an N-ary tree representing three-dimensional points, where N is greater than or equal to 2; encoding a second node, using a second encoding process, included in one of levels in the N-ary tree; and generating a bitstream including the first node encoded and the second node encoded, wherein the first encoding process is different from the second encoding process, a total number of one or more point positions in the first node is less than a predetermined threshold value, one or more point positions in the first node are expressed using a first formula, and one or more point positions in the second node are expressed using a second formula different from the first formula. ### Claim 2 (depends on 1) The method according to claim 1, wherein a total number of point positions in the second node is greater than the predetermined threshold value. ### Claim 3 (depends on 1) The method according to claim 1, wherein the first node indicates each position in each level corresponding to a point, the second node includes N child nodes, and the second node indicates child nodes, including a point, out of the N child nodes. ### Claim 4 (depends on 1) The 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 5 (depends on 1) The method according to claim 1, wherein the N is eight. ### Claim 6 (depends on 1) The method according to claim 1, further comprising: determining an integer of N from two, four or eight. ### Claim 7 A method for decoding three-dimensional data, comprising: obtaining an N-ary tree representing three-dimensional points, where N is greater than or equal to 2; when the N-ary tree includes a first node, decoding the first node using a first decoding process; when the N-ary tree includes a second node, decoding the second node using a second decoding process; and decoding positions of the three-dimensional points using the first node decoded and the second node decoded, wherein the first decoding process is different from the second decoding process, a total number of point positions in the first node is less than a predetermined threshold value, one or more point positions in the first node are expressed using a first formula, and one or more point positions in the second node are expressed using a second formula different from the first formula. ### Claim 8 (depends on 7) The method according to claim 7, wherein a total number of point positions in the second node is greater than the predetermined threshold value. ### Claim 9 (depends on 7) The method according to claim 7, wherein the first node indicates each position in each level corresponding to a point, the second node includes N child nodes, and the second node indicates child nodes, including a point, out of the N child nodes. ### Claim 10 (depends on 7) The method according to claim 7, wherein a quantization parameter used in the second decoding process is different from a quantization parameter used in the first decoding process. ### Claim 11 (depends on 7) The method according to claim 7, wherein the N is eight. ### Claim 12 (depends on 7) The method according to claim 7, further comprising: determining an integer of N from two, four or eight. ### Claim 13 A device for encoding three-dimensional data, comprising: a processor; and memory, wherein using the memory, the processor: encodes a first node, using a first encoding process, included in one of levels in an N-ary tree representing three-dimensional points, where N is greater than or equal to 2; encodes a second node, using a second encoding process, included in one of levels in the N-ary tree; and generates a bitstream including the first node encoded and the second node encoded, wherein the first encoding process is different from the second encoding process, a total number of one or more point positions in the first node is less than a predetermined threshold value, one or more point positions in the first node are expressed using a first formula, and one or more point positions in the second node are expressed using a second formula different from the first formula. ### Claim 14 A device for decoding three-dimensional data, comprising: a processor; and memory, wherein using the memory, the processor: obtains an N-ary tree representing three-dimensional points, where N is greater than or equal to 2; when the N-ary tree includes a first node, decodes the first node using a first decoding process; when the N-ary tree includes a second node, decodes the second node using a second decoding process; and decodes positions of the three-dimensional points using the first node decoded and the second node decoded, wherein the first decoding process is different from the second decoding process, a total number of point positions in the first node is less than a predetermined threshold value, one or more point positions in the first node are expressed using a first formula, and one or more point positions in the second node are expressed using a second formula different from the first formula.