WO2024042909A1 - 復号方法、符号化方法、復号装置及び符号化装置 - Google Patents

復号方法、符号化方法、復号装置及び符号化装置 Download PDF

Info

Publication number
WO2024042909A1
WO2024042909A1 PCT/JP2023/025991 JP2023025991W WO2024042909A1 WO 2024042909 A1 WO2024042909 A1 WO 2024042909A1 JP 2023025991 W JP2023025991 W JP 2023025991W WO 2024042909 A1 WO2024042909 A1 WO 2024042909A1
Authority
WO
WIPO (PCT)
Prior art keywords
node
slice
information
shape
nodes
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2023/025991
Other languages
English (en)
French (fr)
Inventor
敦 伊藤
敏康 杉尾
賀敬 井口
孝啓 西
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Intellectual Property Corp of America
Original Assignee
Panasonic Intellectual Property Corp of America
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Panasonic Intellectual Property Corp of America filed Critical Panasonic Intellectual Property Corp of America
Priority to JP2024542643A priority Critical patent/JPWO2024042909A1/ja
Priority to CN202380060194.1A priority patent/CN119731699A/zh
Priority to KR1020257005085A priority patent/KR20250056900A/ko
Priority to EP23857025.3A priority patent/EP4579597A4/en
Publication of WO2024042909A1 publication Critical patent/WO2024042909A1/ja
Priority to MX2025001645A priority patent/MX2025001645A/es
Priority to US19/056,107 priority patent/US20250191232A1/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/40—Tree coding, e.g. quadtree, octree
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/001—Model-based coding, e.g. wire frame
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/20—Contour coding, e.g. using detection of edges
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
    • H04N19/119—Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
    • H04N19/597—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding specially adapted for multi-view video sequence encoding
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/70—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by syntax aspects related to video coding, e.g. related to compression standards
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/90—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
    • H04N19/96—Tree coding, e.g. quad-tree coding

Definitions

  • the present disclosure relates to a decoding method, an encoding method, a decoding device, and an encoding device.
  • Three-dimensional data is acquired by various methods, such as a distance sensor such as a range finder, a stereo camera, or a combination of multiple monocular cameras.
  • Point cloud represents the shape of a three-dimensional structure using a group of points in three-dimensional space.
  • a point cloud stores the positions and colors of point clouds.
  • Point clouds are expected to become the mainstream method for expressing three-dimensional data, but point clouds require a very large amount of data. Therefore, when storing or transmitting three-dimensional data, it is essential to compress the amount of data through encoding, just as with two-dimensional moving images (an example is MPEG-4 AVC or HEVC standardized by MPEG). Become.
  • point cloud compression is partially supported by a public library (Point Cloud Library) that performs point cloud-related processing.
  • Point Cloud Library a public library that performs point cloud-related processing.
  • Patent Document 1 there is a known technology that uses three-dimensional map data to search for and display facilities located around a vehicle.
  • An object of the present disclosure is to provide a decoding method, an encoding method, a decoding device, or an encoding device that can improve encoding efficiency.
  • a decoding method is a decoding method for decoding a plurality of three-dimensional points, and the method includes acquiring a plurality of nodes having an octree structure and included in a first slice from a bitstream; Information for deriving the shape of a first node among the plurality of nodes is obtained from the bitstream, the first node is decoded according to the information, and the shape is different from other nodes among the plurality of nodes. differs from the prescribed shape of the node.
  • An encoding method is an encoding method that encodes a plurality of three-dimensional points, has an octree structure, and encodes a plurality of nodes included in a first slice. generates a bitstream, and stores information for deriving a shape of a first node among the plurality of nodes in the bitstream, and the shape is a prescribed shape of another node among the plurality of nodes. different from.
  • the present disclosure can provide a decoding method, an encoding method, a decoding device, or an encoding device that can improve encoding efficiency.
  • FIG. 1 is a diagram illustrating an example of a source point group according to an embodiment.
  • FIG. 2 is a diagram illustrating an example of a pruned 8-ary tree according to the embodiment.
  • FIG. 3 is a diagram illustrating a two-dimensional display of leaf nodes according to the embodiment.
  • FIG. 4 is a diagram for explaining a method of generating centroid vertices according to the embodiment.
  • FIG. 5 is a diagram for explaining a method of generating centroid vertices according to the embodiment.
  • FIG. 6 is a diagram illustrating an example of vertex information according to the embodiment.
  • FIG. 7 is a diagram illustrating an example of a trisoap surface according to an embodiment.
  • FIG. 8 is a diagram for explaining point cloud restoration processing according to the embodiment.
  • FIG. 1 is a diagram illustrating an example of a source point group according to an embodiment.
  • FIG. 2 is a diagram illustrating an example of a pruned 8-ary tree according to the embodiment.
  • FIG. 9 is a diagram illustrating an example of slice division according to the embodiment.
  • FIG. 10 is a diagram showing an example of vertices according to the embodiment.
  • FIG. 11 is a diagram illustrating an example of a trisoap surface that should originally be generated according to the embodiment.
  • FIG. 12 is a diagram illustrating an example of a trithorpe surface when no edge vertices are generated according to the embodiment.
  • FIG. 13 is a diagram illustrating an example of a restored point group according to the embodiment.
  • FIG. 14 is a diagram showing an example of vertices according to the embodiment.
  • FIG. 15 is a diagram illustrating an example of a trisoap surface according to an embodiment.
  • FIG. 16 is a diagram illustrating an example of transmission information according to the embodiment.
  • FIG. 17 is a diagram illustrating an example syntax of a GDU header according to the embodiment.
  • FIG. 18 is a diagram illustrating an example of setting the adjustment width of a non-standard width node according to the embodiment.
  • FIG. 19 is a flowchart of encoding processing by the encoding device according to the embodiment.
  • FIG. 20 is a flowchart of decoding processing by the decoding device according to the embodiment.
  • FIG. 21 is a diagram illustrating an example of setting a non-standard width node according to the embodiment.
  • FIG. 22 is a diagram illustrating an example of setting a non-standard width node according to the embodiment.
  • FIG. 23 is a diagram illustrating an example of setting a non-standard width node according to the embodiment.
  • FIG. 24 is a diagram illustrating an example of setting a non-standard width node according to the embodiment.
  • FIG. 25 is a diagram illustrating an example of setting a non-standard width node according to the embodiment.
  • FIG. 26 is a diagram illustrating an example of setting a non-standard width node according to the embodiment.
  • FIG. 27 is a diagram illustrating an example of setting a non-standard width node according to the embodiment.
  • FIG. 28 is a diagram showing the relationship between the node width and the width of the inclusive point coordinates according to the embodiment.
  • FIG. 29 is a diagram illustrating an example of setting a non-standard width node according to the embodiment.
  • FIG. 30 is a diagram illustrating an example of setting a non-standard width node according to the embodiment.
  • FIG. 31 is a diagram illustrating an example syntax of GPS and GDU headers according to the embodiment.
  • FIG. 32 is a diagram illustrating an example of slices and nodes according to the embodiment.
  • FIG. 33 is a diagram illustrating an example of slices and nodes according to the embodiment.
  • FIG. 34 is a diagram illustrating an example of processing when omitting according to the embodiment.
  • FIG. 35 is a diagram illustrating an example syntax of GPS and GDU headers according to the embodiment.
  • FIG. 36 is a flowchart of the omission determination process of the start end adjustment process according to the embodiment.
  • FIG. 37 is a flowchart of the omission determination process of the end end adjustment process according to the embodiment.
  • FIG. 38 is a flowchart of node position determination processing according to the embodiment.
  • FIG. 39 is a flowchart of node width determination processing according to the embodiment.
  • FIG. 40 is a flowchart of decoding processing according to the embodiment.
  • FIG. 41 is a block diagram of a decoding device according to an embodiment.
  • FIG. 42 is a flowchart of encoding processing according to the embodiment.
  • FIG. 43 is a block diagram of a decoding device according to an embodiment.
  • a three-dimensional data decoding method is a decoding method for decoding a plurality of three-dimensional points, and the method decodes a plurality of nodes having an octree structure and included in a first slice from a bitstream. obtain information for deriving the shape of a first node among the plurality of nodes from the bitstream, decode the first node according to the information, and determine the shape of the plurality of nodes. It is different from the prescribed shape of my other nodes. According to this, it is possible to set a node having a shape different from the prescribed shape. Therefore, variable nodes can be set according to the size of the slice or the distribution of the point group. Therefore, there is a possibility that encoding efficiency can be improved.
  • the shape may be a rectangular parallelepiped, and may not be a cube.
  • an edge of the first slice may coincide with an edge of any one of the plurality of nodes. According to this, even if the node end and the slice end do not match, the node end and the slice end can be made to match. Therefore, since it is possible to prevent a vertex from being generated at the end of the node, it is possible to suppress the generation of blank areas at slice boundaries. Therefore, the accuracy of the point cloud to be decoded can be improved.
  • the information may indicate the size of the shape or the positions of both ends of the side of the first node.
  • the decoding device can generate a node having a shape different from the prescribed shape using the information.
  • the information may include adjustment information for adjusting the prescribed shape to the shape.
  • the decoding device can generate a node having a shape different from the prescribed shape using the adjustment information. Furthermore, compared to the case where the absolute amount of position information is sent, there is a possibility that the amount of information can be made smaller.
  • the decoding may be performed according to a compression method in which the plurality of three-dimensional points are approximated by a plane or a curved surface within the first node.
  • the compression method may be a Triangle-Soup compression method.
  • the shape may be determined to generate the plane or the curved surface within the first node. According to this, by setting a node having a shape different from the prescribed shape, a plane or a curved surface can be generated within the first node.
  • the side of the shape may have an apex thereon, and the plane or curved surface may intersect the side at the apex. According to this, by setting a node having a shape different from the prescribed shape, a plane or a curved surface can be generated within the first node.
  • the first node may be provided in contact with a second slice adjacent to the first slice.
  • a node end and a slice end do not match, it is possible to prevent a vertex from being generated at the node end, so it is possible to suppress the generation of blank areas at slice boundaries.
  • the slice boundary may separate the nodes. In that case, the first node cannot be encoded or decoded using the point cloud in the second slice adjacent to the first slice, so the reconstruction accuracy of the three-dimensional point cloud near the slice boundary may deteriorate. There is.
  • the end of the first node can be made to coincide with the end of the first slice, for example.
  • the end of the first node can be made to coincide with the end of the first slice, for example.
  • the information is provided for each slice, and the information of the second slice has an 8-ary tree structure, and is used to derive the shape of the second node among the plurality of nodes included in the second slice. and the shape of the second node may be different from the prescribed shape. According to this, the shape of the node can be set for each slice.
  • the size of the prescribed shape may be expressed as a power of two, and the size of the shape may be different from the size expressed as a power of two.
  • the shape of the first node is defined by a first length along a first direction, a second length along a second direction, and a third length along a third direction.
  • the first direction, the second direction, and the third direction are orthogonal to each other, and only the first length is the first length, the second length, and the third length. is different from the length of the prescribed shape of a node other than the first node, or the first length and the third length are different from the length of the prescribed shape of the nodes other than the first node, or 2 may differ from the length of the defined shape, respectively.
  • the first node is closest to the origin of the first slice among the plurality of nodes in one of a first direction, a second direction, and a third direction;
  • the second direction and the third direction may be orthogonal to each other. According to this, when the start position of the slice does not match the origin, for example, the start position of the node can be adjusted in accordance with the start position of the slice.
  • the plurality of nodes may include a third node having a shape different from the prescribed shape, and the third node may be farthest from the origin in the one direction among the plurality of nodes. According to this, when the end position of a slice does not match the end position of a node, for example, the end position of a node can be adjusted in accordance with the end position of a slice.
  • the bitstream may include the information, and if the starting position of the first slice coincides with the origin, the bitstream may not include the information. good. According to this, the occurrence of processing for adjusting the shape of the node can be reduced. Furthermore, transmission of information for deriving the shape of the node can be omitted. Therefore, it is possible to reduce the amount of processing and the amount of bitstream data.
  • the bitstream includes the information, and the end position of the first slice does not match the end of the first node.
  • the bitstream may not include the information. According to this, the occurrence of processing for adjusting the shape of the node can be reduced. Furthermore, transmission of information for deriving the shape of the node can be omitted. Therefore, it is possible to reduce the amount of processing and the amount of bitstream data.
  • a three-dimensional data encoding method is an encoding method that encodes a plurality of three-dimensional points, has an octree structure, and encodes a plurality of nodes included in a first slice.
  • information for deriving the shape of a first node among the plurality of nodes is stored in the bitstream, and the shape is different from other nodes among the plurality of nodes.
  • the shape differs from the specified shape. According to this, it is possible to set a node having a shape different from the prescribed shape. Therefore, variable nodes can be set according to the size of the slice or the distribution of the point group. Therefore, there is a possibility that encoding efficiency can be improved.
  • a decoding device is a decoding device that decodes a plurality of three-dimensional points, and includes a processor and a memory, and the processor uses the memory to decode a bitstream from a bitstream.
  • an encoding device is an encoding device that encodes a plurality of three-dimensional points, and includes a processor and a memory, and the processor uses the memory to A bitstream is generated by encoding a plurality of nodes included in a first slice, and information for deriving the shape of a first node among the plurality of nodes is added to the bitstream. and the shape is different from the prescribed shape of other nodes among the plurality of nodes.
  • the encoding device generates a bitstream by encoding three-dimensional data.
  • the decoding device generates three-dimensional data by decoding the bitstream.
  • the three-dimensional data is, for example, three-dimensional point group data (also referred to as point group data).
  • a point cloud is a collection of three-dimensional points and indicates the three-dimensional shape of an object.
  • the point cloud data includes position information and attribute information of a plurality of three-dimensional points.
  • the position information indicates the three-dimensional position of each three-dimensional point.
  • the position information may also be referred to as geometry information.
  • position information is expressed in a rectangular coordinate system or a polar coordinate system.
  • the attribute information indicates, for example, color information, reflectance, transmittance, infrared information, normal vector, or time information.
  • One three-dimensional point may have a single attribute information, or may have multiple types of attribute information.
  • the encoding device may also encode and decode attribute information.
  • Tri-soap method The encoding device according to this embodiment encodes position information using a TriSoup (Triangle-Soup) method.
  • the trisoap method is one of the methods for encoding position information of point cloud data, and is an irreversible compression method.
  • the original point group to be processed is replaced with a set of triangles, and the point group is approximated on the plane.
  • the original point group is replaced with vertex information within the node, and the vertices are connected to generate a triangle group.
  • vertex information for generating triangles is stored in a bitstream and sent to the decoding device.
  • FIG. 1 is a diagram showing an example of a group of original points. As shown in FIG. 1, a point group 102 of the object is included in the object space 101 and includes a plurality of points 103.
  • the encoding device divides the original point group into an octree to a predetermined depth.
  • octree division a target space is divided into eight nodes (subspaces), and 8-bit information (occupancy code) indicating whether a point group is included in each node is generated.
  • the node including the point cloud is further divided into eight nodes, and 8-bit information indicating whether or not the point group is included in each of the eight nodes is generated. This process is repeated up to a predetermined hierarchy.
  • 8-ary tree division is performed up to an intermediate layer, but is not performed on layers below that layer.
  • Such an 8-ary tree up to an intermediate level is called a pruned 8-ary tree.
  • FIG. 2 is a diagram showing an example of a pruned 8-ary tree. As shown in FIG. 2, the point cloud 102 is divided into a plurality of leaf nodes 104 (lowest layer nodes) of a pruned 8-ary tree.
  • the encoding device performs the following processing on each leaf node 104 of the pruned 8-ary tree.
  • leaf nodes are also simply referred to as nodes.
  • the encoding device generates a vertex on the edge as a representative point of a point group close to the edge of the node. This vertex is called an edge vertex.
  • edge vertex For example, edge vertices are generated for each of a plurality of edges (eg, four parallel sides).
  • FIG. 3 is an example of a two-dimensional display of the leaf node 104, and is a diagram showing, for example, an xy plane viewed from the z direction shown in FIG. 1. As shown in FIG. 3, edge vertices 112 are generated on the edge based on points near the edge among the plurality of points 111 in the leaf node 104.
  • the dotted line on the outer periphery of the leaf node 104 is an edge.
  • the edge vertex 112 is generated at a position that is a weighted average of the positions of points within 1 distance from the edge (points included in the range 113 in FIG. 3).
  • the unit of distance is, for example, the resolution of a point group, but is not limited thereto.
  • this distance (threshold value) is 1 in this example, it may be other than 1 and may be variable.
  • the encoding device also generates vertices inside the node based on the point group existing in the normal direction of the plane including the plurality of edge vertices. This vertex is called a centroid vertex.
  • FIGS. 4 and 5 are diagrams for explaining the method of generating centroid vertices.
  • the encoding device selects, for example, four points as representative points from a group of edge vertices. In the example shown in FIG. 4, edge vertices v1 to v4 are selected.
  • the encoding device calculates an approximate plane 121 passing through the four points.
  • the encoding device calculates the normal n of the approximate plane 121 and the average coordinate M of the four points.
  • the encoding device converts the centroid vertex C into a weighted average coordinate of one or more points (for example, points included in the range 122 shown in FIG. 5) close to a half-line extending from the average coordinate M in the direction of the normal line n. generate.
  • the encoding device entropy encodes vertex information, which is information on edge vertices and centroid vertices, and converts the encoded vertex information into a geometry data unit (hereinafter referred to as GDU) included in the bitstream. ).
  • GDU geometry data unit
  • the GDU includes information indicating a pruned 8-ary tree in addition to the vertex information.
  • FIG. 6 is a diagram showing an example of vertex information.
  • the point group 102 is converted into vertex information 123, as shown in FIG.
  • the decoding device decodes the GDU from the bitstream and obtains vertex information.
  • the decoding device connects the vertices to generate a TriSoup-Surface, which is a group of triangles.
  • FIG. 7 is a diagram showing an example of a trithorpe surface.
  • four edge vertices v1 to v4 and a centroid vertex C are generated based on the vertex information.
  • a triangle 131 (trisoap surface) having the centroid vertex C and two edge vertices as vertices is generated. For example, pairs of two edge vertices on two adjacent edges are each selected, and a triangle 131 having the selected pair and the centroid vertex as vertices is generated.
  • FIG. 8 is a diagram for explaining the point cloud restoration process.
  • the decoding device restores the position information of the point group 133 by generating points 132 at regular intervals on the surface of the triangle 131.
  • FIG. 9 is a diagram showing an example where a point group extending in the vertical direction is divided into slices.
  • FIG. 10 is a diagram showing an example of vertices generated in this case.
  • the slice is divided from the bottom by nodes having a specified width.
  • node 1 at the top of the slice includes a blank area.
  • edge vertex v2 should be generated at the upper edge, but edge vertex v2 cannot be generated because there is no point group near the edge.
  • the slice boundaries shown in FIGS. 9 and 10 are boundaries of bounding boxes of slices.
  • FIG. 11 is a diagram showing an example of the trisoap surface that should originally be generated.
  • FIG. 12 is a diagram showing an example of a trithorpe surface when no edge vertices are generated as shown in FIG. 10. As shown in FIG. 12, if edge vertices v2 and v3 are not generated on the upper edge, a trisoap surface is generated only with vertices v1 and v4 on the lower edge and the centroid vertex c. As a result, the trithorpe surface that should originally traverse the node is generated only at the bottom of the node.
  • FIG. 13 is a diagram showing an example of the restored point group in this case. As shown in FIG. 13, since points are not restored in areas where there is no trisoap surface, holes are created across the restored point group, as in area 201 shown in FIG.
  • the width of the node located at the edge of the bounding box of a slice is set to a width different from the specified width.
  • FIG. 14 is a diagram showing an example of vertices generated in this case.
  • FIG. 15 is a diagram showing an example of a trisoap surface in this case.
  • a node 1 having an unspecified width is provided at the end of the slice.
  • the blank space within the node 1 can be eliminated and the edge vertex v2 can be generated. Therefore, as shown in FIG. 15, it is possible to generate a tri-thorpe surface that traverses the inside of the node, thereby eliminating the generation of transverse holes in the restored point group.
  • the encoding device stores, for example, information indicating the slice width in the GDU header as adjustment width information that is information for calculating the adjustment width of this non-standard width node.
  • a non-specified width node is a node in which the length of a side along at least one of the length, width, and height is different from the specified length (specified width).
  • the non-specified width node has a rectangular parallelepiped or cubic shape that is different from the cubic shape of the specified width.
  • the adjustment width information is information for adjusting the specified length of the side of the node to an adjustment width of a side length different from the specified width (non-specified width).
  • the adjustment width information may indicate the length of the adjustment width itself, may indicate the difference between the specified width and the adjustment width, or may indicate the ratio between the specified width and the adjustment width.
  • the adjustment width (non-specified width) of a non-specified width node is expressed as min (slice width - node position, specified width).
  • the non-specified width of a certain node is set to the minimum value between (slice width - node position) and the specified width.
  • the node position is the position (coordinates) of the corner of the node that is closest to the origin, as shown in FIG.
  • edge vertices can also be generated at the end nodes of the bounding box of the slice.
  • the trisoap surface can be arranged without interruption, which eliminates the occurrence of holes in the restored point cloud.
  • the point group included in the first slice is also included in the leaf node of the second slice.
  • the first slice and the second slice have overlapping point groups.
  • the point group is divided into slices by matching the boundary coordinates between the first slice and the second slice with the leaf node width. In other words, nodes with blank spaces due to slice division are not generated.
  • Transmission information transmitted from the encoding device to the decoding device in order to implement the above method will be described below.
  • transmission information is stored in a bitstream.
  • FIG. 16 is a diagram showing an example of this transmission information.
  • the GDU header included in the bitstream includes a non-standard width processing flag and slice width information.
  • the non-standard width processing flag is information indicating whether or not to set the above-mentioned non-standard width node. For example, a value of 1 indicates that a non-standard width node is set, and a value of 0 indicates that a non-standard width node is not set.
  • the slice width information indicates the slice width (the width of the bounding box of the slice).
  • FIG. 17 is a diagram showing an example of the syntax of the GDU header (geometry_data_unit_header). As shown in FIG. 17, slice width information is stored in the GDU header only when the non-standard width processing flag has a value of 1 (true). Further, the slice width information includes, for example, information indicating the width of each slice in the x, y, and z axes.
  • the slice width information is information for each slice, and here, the non-standard width processing flag and slice width information are stored in the GDU header, which is a header for each slice.
  • non-standard width processing flag may be information indicating whether slice width information is included in the bitstream.
  • the names of flags, information, etc. shown in this embodiment are merely examples, and any names can be used.
  • these pieces of information may be common to a plurality of slices.
  • these pieces of information may be stored in a header higher than the GDU header, such as SPS or GPS.
  • SPS Sequence Parameter Set
  • GPS Global System Parameter Set
  • GPS is metadata (parameter set) related to encoding of position information. For example, GPS is metadata common to multiple frames.
  • a flag indicating whether this information is stored in the upper header or for each slice may be stored in the SPS or GPS. In this case, the storage location of these pieces of information is switched based on the flag.
  • these pieces of information are for processing specific to the tri-soap method, they may be stored in the bitstream only when the encoding method is the tri-soap method.
  • FIG. 19 is a flowchart of encoding processing by the encoding device.
  • the encoding device generates a pruned 8-ary tree, and stores 8-ary tree information indicating the pruned 8-ary tree in the GDU (S101). For example, the encoding device entropy encodes the octree information and stores the encoded octree information in the GDU.
  • the encoding device performs the following steps S105 to S109 on each of the plurality of leaf nodes of the pruned octtree.
  • the encoding device calculates the adjustment width from the slice width indicated by the slice width information and the node position of the target node, and adjusts the target node to the calculated adjustment width. (S107).
  • the encoding device sets the width of the target node to the standard width ( S108).
  • the encoding device generates edge vertices on the edges of the target node and generates centroid vertices inside the target node based on the point group distribution within the target node (S109). With the above, the loop processing for the target node is completed.
  • the encoding device After the loop processing for all leaf nodes is completed, the encoding device entropy encodes the vertex information indicating the positions of the edge vertices and centroid vertices of the plurality of leaf nodes, and stores the encoded vertex information in the GDU. (S110).
  • the encoding device generates a bitstream including the GDU header and GDU, and outputs the bitstream (S111). That is, the encoding device transmits the bitstream to the decoding device.
  • FIG. 20 is a flowchart of the decoding process by the decoding device.
  • the decoding device obtains the GDU header and GDU from the bitstream (S121).
  • the decoding device obtains octree information from the GDU. For example, the decoding device acquires 8-ary tree information by entropy decoding the encoded 8-ary tree information included in the GDU. Next, the decoding device generates a group of leaf nodes of the pruned 8-ary tree using the 8-ary tree information (S124).
  • the decoding device performs the following steps S125 to S130 on each of the plurality of leaf nodes of the pruned 8-ary tree.
  • the decoding device calculates the adjustment width from the slice width indicated by the slice width information and the node position of the target node, and adjusts the target node to the calculated adjustment width. (S127).
  • the decoding device sets the width of the target node to the specified width (S128). .
  • the decoding device obtains vertex information indicating the positions of edge vertices and centroid vertices from the GDU (S129). For example, the decoding device acquires vertex information by entropy decoding encoded vertex information included in the GDU.
  • the decoding device generates a triangle group by connecting a plurality of vertices indicated by the vertex information (S130). With the above, the loop processing for the target node is completed.
  • the decoding device After completing the loop processing for all leaf nodes, the decoding device generates a decoded point group by generating points at regular intervals on the surfaces of multiple triangles (S131).
  • FIGS. 21 to 24 are diagrams showing examples of setting non-standard width nodes.
  • the position of the non-standard width node may be in the middle of the slice.
  • the position of the non-standard width node may be at the beginning of the slice.
  • a plurality of non-standard width nodes may be set.
  • two non-standard width nodes may be set at both ends of the slice.
  • two non-standard width nodes may be set at the end of the slice and at the middle of the slice.
  • the sum of the widths of the plurality of non-standard width nodes only needs to be the above-mentioned adjustment width.
  • non-standard width node information which is information for non-standard width nodes, that is stored in the bitstream.
  • the non-specified width node information when the non-specified width node is placed at a location other than the end of the slice, the non-specified width node information includes the adjusted width information indicating the adjusted width and the insertion position of the non-specified width node. and insertion position information indicating the insertion position.
  • the insertion position information indicates the bit string "4b0010”.
  • the insertion position information indicates the bit string "4b1000”. Note that the plurality of bits in the bit string each correspond to a node, and the bit corresponding to the non-standard width node is set to 1, and the other bits are set to 0.
  • the insertion position information may indicate information that specifies a non-standard width node.
  • a serial number identifier
  • the insertion position information may indicate a serial number of a non-standard width node.
  • a serial number may be set for each axis within a slice. In this case, in the example shown in FIG. 21, serial numbers 1, 2, 3, and 4 are set in order from the left node, and the insertion position information indicates the value 3.
  • the serial number may be a serial number for all nodes within a slice.
  • the decoding device can use the insertion position information to determine whether the target node is a non-standard width node. Further, the adjustment width can be calculated using the same method as shown in FIG.
  • the insertion position information indicates the individual insertion positions of the multiple non-standard width nodes.
  • the insertion position information indicates the bit string "5b1001".
  • the insertion position information indicates the bit string "5b10010". Note that here we have shown an example in which one bit string is used for one axis (x-axis in this example) (that is, an example in which a different bit string is used for each axis), but one bit string is used for all nodes in the slice. Two bit strings may be used.
  • the adjustment width information indicates the adjustment width of each of the two non-standard width nodes. Specifically, the adjustment width information indicates a value 2, which is the adjustment width of the first non-standard width node, and a value 2, which is the adjustment width of the second non-standard width node.
  • the adjustment width information may indicate the total adjustment width of two non-standard width nodes and the adjustment width of one non-standard width node.
  • the decoding device can calculate the adjustment widths of the two non-standard width nodes from the adjustment width information.
  • the adjustment width information of the last non-standard width node in a row of non-standard width nodes on one axis is omitted, a rule is determined in advance, and the decoding device , the adjustment widths of the two non-standard width nodes may be calculated from the adjustment width information.
  • the non-standard width node information may be composed of individual information of all non-standard width nodes within a slice, instead of information for each axis.
  • FIG. 25 is a diagram showing an example of setting the non-standard width node in this case.
  • the example shown in FIG. 25 is an example in which the node at the end of the slice is set to a non-standard width node.
  • the non-standard width node information includes the amount of offset from the origin coordinates to the start position of the bounding box of the slice.
  • the decoding device can calculate the adjustment width using this offset amount.
  • the non-standard width node information includes information indicating the fractional node width, which is the adjusted width of the node at the end of the slice. The decoding device uses this information to set the adjustment width of the node at the edge of the slice to the fractional node width.
  • FIG. 26 is a diagram showing an example of setting the non-standard width node in this case.
  • the non-specified width may be a value larger than the specified width.
  • the third node and the fourth node may be combined. That is, three nodes whose widths are 32, 32, and 36 from the left may be set.
  • the node may become a cube.
  • the position information of the corner of the node may be transmitted so that the size of the non-standard width node can be restored.
  • the position information may be coordinate information of two corners in the direction of the non-standard width, or may be coordinate information of all eight corners.
  • the encoding device may quantize the above-mentioned non-standard width node information for calculating the adjustment width, and transmit the quantized information to the decoding device.
  • the decoding device may perform the above processing by dequantizing the quantized information and using the obtained non-standard width node information. In this case, a case may occur in which the width of the blank area within the non-standard width node does not become completely zero. On the other hand, by performing quantization, the amount of data to be transmitted can be reduced.
  • the default size of the node is determined depending on the size of the bounding box to be octree encoded (bit depth of the original data) and the depth to which the octree division is to proceed. be done.
  • This specified width is expressed, for example, as a power of two.
  • a non-standard width node is a node in which the length of a side along at least one of the length, width, and height differs from the specified width, but the length in only one direction, or in only two directions.
  • the length may be different from the specified width. That is, the non-standard width node may be a rectangular parallelepiped.
  • edge vertices existing on four parallel edges of a node are found, but the number of edge vertices to be found is not limited to four.
  • the number of edge vertices is not particularly limited as long as an approximate plane is obtained.
  • the method of finding the centroid apex is not limited to the above method. As long as the decoding device can determine the plane of the triangle, the centroid vertices may be determined using other methods.
  • the tri-soap method was used as the compression method, but the method of this embodiment is also effective for compression methods other than the tri-soap method.
  • the method of this embodiment is a compression method that approximates a point group using a plane or curved surface within a node, and is effective for a compression method that requires edge vertices to generate the plane or curved surface. It is.
  • the non-standard length of the side of the non-standard width node is determined, but it is not essential to determine the non-standard length. It is only necessary to find the shape of the non-standard width node; for example, the positions of the two ends of the side with the non-standard length may be found. That is, the position of the non-standard width node may be determined.
  • the origin of the slice is an unspecified offset amount, and the starting position of the bounding box of the slice does not necessarily match the origin. Therefore, there may be a case where the point group of the slice after subtracting this offset amount is distributed away from the origin of the encoding coordinate system. That is, there are cases where the origin of the encoded coordinate system and the origin of the bounding box of the slice are different. Furthermore, in this case, the boundaries of the bounding box of the slice may not coincide with the boundaries of the leaf nodes. In this case, it is necessary to generate non-standard width nodes on both the side of the bounding box of the slice on the origin side and the side of the bounding box on the side far from the origin.
  • the encoding device uses the slice position, which is the start coordinate of the bounding box of the slice, and the width of the bounding box as information for the decoding device to calculate the node position and node width (adjusted width) of these non-standard width nodes.
  • the slice width is transmitted to the decoding device.
  • FIG. 27 is a diagram showing an example of setting the non-standard width node in this case.
  • the encoded coordinate system is expressed one-dimensionally.
  • the shaded area is an area (slice) in which the point group is distributed.
  • the origin shown in FIG. 27 is the origin of the encoding coordinate system.
  • the adjusted node position newNodePos and the adjusted node width newNodeWidth are calculated as follows. .
  • the node position is adjusted to A if nodePos ⁇ A, otherwise it is not adjusted. That is, the node position of node 1, which is the leading node, is changed from P1 to A, and the node positions of the other nodes are not changed.
  • the node widths of other nodes are set to W.
  • the decoding device obtains A and B from the transmission information, and uses the above formula from the initial node position and initial node width of each node. are used to calculate the adjusted node positions and adjusted node widths of nodes 1 and 2.
  • the position of the non-standard width node may be located at the beginning of the slice, in the middle of the slice, at both ends of the slice, or at multiple positions.
  • the total node width may be the above-mentioned adjustment width.
  • the following can be used as the calculation method and the non-standard width node information, which is information for non-standard width nodes, that is stored in the bitstream.
  • FIG. 29 is a diagram showing an example of setting a non-standard width node.
  • the encoding device can calculate the adjusted position and adjustment width of node 1 on the origin side.
  • the decoding device can calculate the adjustment width of the node 2 on the far side from the origin.
  • the non-standard width node information also includes information specifying a non-standard width node and the information for the specified node.
  • Information indicating the adjustment position and adjustment width of the node may be included.
  • the information specifying the non-standard width node indicates, for example, a serial number assigned to the node.
  • FIG. 30 is a diagram showing an example of setting the non-standard width node in this case.
  • 0 to 3 are assigned as node numbers, which are serial numbers of nodes.
  • FIG. 29 a method for determining a non-standard width node and calculating its position and width has been explained, but it is also possible to use any of the methods explained in FIGS. Good too.
  • FIG. 31 is a diagram illustrating an example of the syntax of GPS (geometry_parameter_set) and GDU header.
  • the GPS includes a first non-standard width processing flag and a second non-standard width processing flag.
  • the first non-standard width processing flag is information indicating whether or not to perform the above-described node position and node width adjustment on the node located at the end of the slice closer to the origin. For example, a value of 1 indicates that the adjustment is performed, and a value of 0 indicates that the adjustment is not performed.
  • the second non-standard width processing flag is information indicating whether or not to perform the above-described node width adjustment on the node located at the slice end on the side far from the origin. For example, a value of 1 indicates that the adjustment is performed, and a value of 0 indicates that the adjustment is not performed.
  • the GDU header includes first bit length information, a first quantization parameter, and slice position information.
  • the slice position information indicates the slice position, which is the position (coordinates) of the bounding box of the slice, and for example, indicates the three-dimensional coordinates (x, y, z coordinates) of the corner of the bounding box of the slice that is closest to the origin. .
  • the first bit length information indicates the bit length of slice position information.
  • the first quantization parameter indicates a quantization parameter (quantization value) used for quantizing slice position information.
  • the GDU header includes second bit length information, a second quantization parameter, and slice width information.
  • the slice width information indicates the slice width, which is the width of the bounding box of the slice.
  • the slice width information indicates the width of the bounding box in each of the x, y, and z directions.
  • the second bit length information indicates the bit length of the slice width.
  • the second quantization parameter indicates a quantization parameter used for quantizing slice width information.
  • the slice position is represented by slice position information ⁇ first quantization parameter
  • the slice width is represented by slice width information ⁇ second quantization parameter.
  • these pieces of information are stored for each slice, but if these pieces of information are common to multiple slices, these pieces of information are stored above the GDU header such as SPS or GPS. may be stored in the header of Further, a flag indicating whether this information is stored in the upper header or for each slice may be stored in the SPS or GPS. In this case, the storage location of these pieces of information is switched based on the flag. Furthermore, this information may be provided individually for each axis of x, y, and z.
  • the encoding device does not need to transmit the first non-standard width processing flag and the second non-standard width processing flag shown in FIG. 31.
  • the slice position information and the slice width information are numerical values in the encoded coordinate system, they may be determined to be positive values.
  • the encoding device performs this omission determination and transmits information indicating the determination result to the decoding device.
  • a dedicated flag may be used for this transmission, or the first bit length information and second bit length information described above may be used. Specifically, when the first bit length information indicates 0, it means that transmission of slice position information is omitted, and when the second bit length information indicates 0, it means that transmission of slice width information is omitted. means. This allows the amount of header data to be suppressed and the processing time for encoding processing to be shortened.
  • FIG. 32 is a diagram showing an example of a slice and a node when the starting end of the slice coincides with the origin. In this case, there is no need to adjust the starting end.
  • FIG. 33 is a diagram showing an example of a slice and a node in a case where the start end of the slice coincides with the origin and the end end of the slice coincides with the end end of the node. In this case, adjustment processing is not required for both the start end and the end end.
  • FIG. 34 is a diagram showing an example of processing (syntax) when the above omission is performed.
  • slice_bb_pos_bits shown in the figure is first bit length information indicating the bit length of slice position information.
  • slice_bb_width_bits is second bit length information indicating the bit length of slice width information.
  • A is the slice position
  • B is the slice width
  • nodePos is the node position (node position before adjustment)
  • nodeWidth is the node width (node width before adjustment)
  • newNodeWidth is the node after adjustment.
  • W is the specified width of the node.
  • the adjustment process is performed only when the bit length of the slice position information is a value greater than 0, so the processing time of the encoding process can be reduced. Furthermore, if the start end of a slice coincides with the origin or the end end coincidentally coincides with the end end of a node, the amount of data in the header can be reduced.
  • FIG. 35 is a diagram showing an example of the syntax of the GPS and GDU headers in this case.
  • the syntax shown in FIG. 35 differs from the syntax shown in FIG. 31 in that the first quantization parameter and slice position information are stored in the GDU header only when the first bit length information is greater than 0. and a condition that the second quantization parameter and slice width information are stored in the GDU header only when the second bit length information is greater than 0 are added.
  • the amount of data in the header can be reduced when the start end of the slice matches the origin or the end end matches the end end of the node.
  • FIG. 36 is a flowchart of the omission determination process of the start end adjustment process (slice position transmission).
  • the encoding device determines whether the start position of the slice (coordinates of the start end of the bounding box of the slice) matches the origin (S201).
  • the encoding device transmits slice position information (S203). That is, the encoding device stores slice_bb_pos_bits set to a value greater than 0 and slice position information in the bitstream.
  • FIG. 37 is a flowchart of the omission determination process of the end end adjustment process (slice width transmission).
  • the encoding device determines whether the end position of the slice (coordinates of the end of the bounding box of the slice) matches the end of the node (S211).
  • the encoding device transmits slice width information (S213). That is, the encoding device stores slice_bb_width_bits set to a value greater than 0 and slice width information in the bitstream.
  • FIG. 38 is a flowchart of the node position determination process. For example, the process shown in FIG. 38 is performed for each node.
  • the encoding device determines whether the first bit length information (slice_bb_pos_bits) is greater than 0 (S221).
  • the encoding device determines whether the node position (nodePos) of the target node is smaller than the slice position (S222).
  • the encoding device sets the slice position as the adjusted node position (S223).
  • the encoding device does not change (adjust) the node position (S224).
  • FIG. 39 is a flowchart of the node width determination process. For example, the process shown in FIG. 39 is performed for each node.
  • the encoding device determines whether the first bit length information (slice_bb_pos_bits) is greater than 0 (S231).
  • the encoding device determines whether the node position (nodePos) of the target node is smaller than the slice position (S232).
  • the encoding device sets the specified width (W) - (slice position (A) - node position (nodePos)) as the adjusted node width (nodeWidth). (S233).
  • the encoding device determines whether the second bit length information (slice_bb_width_bits) is greater than 0 (S234).
  • the encoding device converts min(slice position (A) + slice width (B) - node position (nodePos) + 1, specified width (W)) into a node. It is set as the width (nodeWidth) (S235).
  • the encoding device does not change the node width (nodeWidth) (S236). That is, the encoding device sets the node width to the specified width (W).
  • the encoding device determines whether the second bit length information (slice_bb_width_bits) is greater than 0 (S237). Note that the case where the first bit length information is 0 (No in S231) means that the slice position information is not transmitted, and the start end of the slice coincides with the origin.
  • the encoding device sets min(slice width (B) - node position (nodePos) + 1, specified width (W)) as the node width (nodeWidth). (S238).
  • the encoding device does not change the node width (nodeWidth) (S236). That is, the encoding device sets the node width to the specified width (W).
  • the decoding device (three-dimensional data decoding device) according to the embodiment performs the processing shown in FIG. 40.
  • the decoding device is a decoding device that decodes a plurality of three-dimensional points.
  • the decoding device obtains a plurality of nodes having an octree structure and included in the first slice from the bitstream (S301), and derives the shape of the first node among the plurality of nodes from the bitstream. (S302), the first node is decoded according to the information (S303), and the shape of the first node is different from the prescribed shape of other nodes among the plurality of nodes. According to this, it is possible to set a node having a shape different from the prescribed shape. Therefore, variable nodes can be set according to the size of the slice or the distribution of the point group. Therefore, there is a possibility that encoding efficiency can be improved.
  • the shape of the first node is a rectangular parallelepiped, not a cube.
  • the edge of the first slice coincides with the edge of any one of the plurality of nodes. According to this, even if the node end and the slice end do not match, the node end and the slice end can be made to match. Therefore, since it is possible to prevent a vertex from being generated at the end of the node, it is possible to suppress the generation of blank areas at slice boundaries. Therefore, the accuracy of the point cloud to be decoded can be improved.
  • the size of the shape of the first node is different from the prescribed size of the prescribed shape.
  • the length of the side of the shape of the first node is different from the prescribed length (eg, prescribed width) of the side of the prescribed shape.
  • the information for deriving the shape of the first node indicates the size of the shape of the first node or the positions of both ends of the sides of the first node. According to this, the decoding device can generate a node having a shape different from the prescribed shape using the information.
  • the information for deriving the shape of the first node includes adjustment information (for example, slice width information or slice position information) for adjusting the prescribed shape to the shape of the first node.
  • the decoding device can generate a node having a shape different from the prescribed shape using the adjustment information. Furthermore, compared to the case where the absolute amount of position information is sent, there is a possibility that the amount of information can be made smaller.
  • the decoding of the first node is performed according to a compression method in which a plurality of three-dimensional points are approximated by a plane or curved surface within the first node.
  • the compression method is the Triangle-Soup compression method.
  • the shape of the first node is determined in order to generate a plane or a curved surface within the first node. According to this, by setting a node having a shape different from the prescribed shape, a plane or a curved surface can be generated within the first node.
  • the edge of the shape of the first node has a vertex on it, and the plane or curved surface intersects the edge at the vertex.
  • a plane or a curved surface can be generated within the first node.
  • the plurality of three-dimensional points include a first three-dimensional point located near the vertex.
  • the first node is provided in contact with a second slice adjacent to the first slice.
  • a node end and a slice end do not match, it is possible to prevent a vertex from being generated at the node end, so it is possible to suppress the generation of blank areas at slice boundaries.
  • the slice boundary may separate the nodes. In that case, the first node cannot be encoded or decoded using the point cloud in the second slice adjacent to the first slice, so the accuracy of restoring the three-dimensional point cloud near the slice boundary may deteriorate. There is.
  • the end of the first node can be made to coincide with the end of the first slice, for example.
  • the end of the first node can be made to coincide with the end of the first slice, for example.
  • information for deriving the shape of the first node is provided for each slice, and information for the second slice has an 8-ary tree structure, and information for deriving the shape of the first node is provided for each slice. is used to derive the shape of the second node, and the shape of the second node is different from the prescribed shape. According to this, the shape of the node can be set for each slice.
  • the size of the prescribed shape is expressed as a power of two
  • the size of the first node shape is different from the size expressed as a power of two.
  • the shape of the first node is defined by a first length along a first direction, a second length along a second direction, and a third length along a third direction;
  • the first direction, second direction, and third direction are orthogonal to each other, and only the first length among the first length, second length, and third length defines a node other than the first node.
  • the length is different from the length of the shape, or only the first length and the second length among the first length, the second length and the third length are different from the length of the prescribed shape.
  • the first node is closest to the origin of the first slice among the plurality of nodes in one of the first direction, the second direction, and the third direction;
  • the third directions are orthogonal to each other. According to this, when the start position of the slice does not match the origin, for example, the start position of the node can be adjusted in accordance with the start position of the slice.
  • the origin is a position of a slice, a node, a three-dimensional point, or a reference position for defining a shape.
  • the plurality of nodes include a third node having a shape different from the prescribed shape, and the third node is the farthest from the origin in one direction among the plurality of nodes. According to this, when the end position of a slice does not match the end position of a node, for example, the end position of a node can be adjusted in accordance with the end position of a slice.
  • the bitstream contains information for deriving the shape of the first node
  • the bitstream contains the information for deriving the shape of the first node. It does not contain information for deriving the shape of the node. According to this, the occurrence of processing for adjusting the shape of the node can be reduced. Furthermore, transmission of information for deriving the shape of the node can be omitted. Therefore, it is possible to reduce the amount of processing and the amount of bitstream data.
  • start position (starting end) of a slice is the position of the end of the slice closer to the origin
  • end position (end end) of the slice is the position of the end of the slice farther from the origin.
  • starting position (starting edge) of a node is the position of the edge of the node on the side closer to the origin
  • ending position (end edge) of a node is the position of the edge of the node on the side far from the origin.
  • the bitstream includes information for deriving the shape of the first node, and the ending position of the first slice does not match the ending edge of the first node.
  • the bitstream does not contain information for deriving the shape of the first node. According to this, the occurrence of processing for adjusting the shape of the node can be reduced. Furthermore, transmission of information for deriving the shape of the node can be omitted. Therefore, it is possible to reduce the amount of processing and the amount of bitstream data.
  • FIG. 41 is a block diagram of the decoding device 10.
  • the decoding device 10 includes a processor 11 and a memory 12, and the processor 11 uses the memory 12 to perform the above processing.
  • the encoding device (three-dimensional data encoding device) according to the embodiment performs the processing shown in FIG. 42.
  • the encoding device is an encoding device that encodes a plurality of three-dimensional points.
  • the encoding device has an octree structure, generates a bitstream by encoding multiple nodes included in the first slice (S311), and derives the shape of the first node among the multiple nodes.
  • information for the first node is stored in the bitstream (S312), and the shape of the first node is different from the prescribed shape of other nodes among the plurality of nodes.
  • the encoding device may perform the same processing as the decoding device described above.
  • FIG. 43 is a block diagram of the encoding device 20.
  • the encoding device 20 includes a processor 21 and a memory 22, and the processor 21 uses the memory 22 to perform the above processing.
  • the present disclosure is limited to this embodiment. It is not something that will be done.
  • each processing unit included in the encoding device, decoding device, etc. is typically realized as an LSI, which is an integrated circuit. These may be integrated into one chip individually, or may be integrated into one chip including some or all of them.
  • circuit integration is not limited to LSI, and may be realized using a dedicated circuit or a general-purpose processor.
  • An FPGA Field Programmable Gate Array
  • a reconfigurable processor that can reconfigure the connections and settings of circuit cells inside the LSI may be used.
  • each component may be configured with dedicated hardware, or may be realized by executing a software program suitable for each component.
  • Each component may be realized by a program execution unit such as a CPU or a processor reading and executing a software program recorded on a recording medium such as a hard disk or a semiconductor memory.
  • the present disclosure also describes an encoding method (three-dimensional data encoding method) or a decoding method (three-dimensional data decoding method), etc.
  • the present disclosure may be implemented as a program that executes the encoding method or decoding method on a computer, processor, or device. Further, the present disclosure may be implemented as a bitstream generated by the above encoding method. Further, the present disclosure may be realized as a recording medium on which the program or the bitstream is recorded. For example, the present disclosure may be realized as a non-transitory computer-readable recording medium on which the program or the bitstream is recorded.
  • the present disclosure can be applied to encoding devices and decoding devices.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Signal Processing (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

復号方法は、複数の三次元点を復号する復号方法であって、ビットストリームから、８分木構造を有し、第１スライスに含まれる複数のノードを取得し（Ｓ３０１）、ビットストリームから、複数のノードのうちの第１ノードの形状を導出するための情報を取得し（Ｓ３０２）、第１ノードを情報に従い復号し（Ｓ３０３）、第１ノードの形状は、複数のノードのうちの他のノードの規定形状と異なる。例えば、形状は直方体形状であり、立方体形状ではなくてもよい。

Description

復号方法、符号化方法、復号装置及び符号化装置
　本開示は、復号方法、符号化方法、復号装置及び符号化装置に関する。
　自動車或いはロボットが自律的に動作するためのコンピュータビジョン、マップ情報、監視、インフラ点検、又は、映像配信など、幅広い分野において、今後、三次元データを活用した装置又はサービスの普及が見込まれる。三次元データは、レンジファインダなどの距離センサ、ステレオカメラ、又は複数の単眼カメラの組み合わせなど様々な方法で取得される。
　三次元データの表現方法の１つとして、三次元空間内の点群によって三次元構造の形状を表すポイントクラウドと呼ばれる表現方法がある。ポイントクラウドでは、点群の位置と色とが格納される。ポイントクラウドは三次元データの表現方法として主流になると予想されるが、点群はデータ量が非常に大きい。よって、三次元データの蓄積又は伝送においては二次元の動画像（一例として、ＭＰＥＧで規格化されたＭＰＥＧ－４　ＡＶＣ又はＨＥＶＣなどがある）と同様に、符号化によるデータ量の圧縮が必須となる。
　また、ポイントクラウドの圧縮については、ポイントクラウド関連の処理を行う公開のライブラリ（Ｐｏｉｎｔ　Ｃｌｏｕｄ　Ｌｉｂｒａｒｙ）などによって一部サポートされている。
　また、三次元の地図データを用いて、車両周辺に位置する施設を検索し、表示する技術が知られている（例えば、特許文献１参照）。
国際公開第２０１４／０２０６６３号
　このような符号化方法及び復号方法では、符号化効率の向上が望まれている。
　本開示は、符号化効率を向上できる復号方法、符号化方法、復号装置又は符号化装置を提供することを目的とする。
　本開示の一態様に係る復号方法は、複数の三次元点を復号する復号方法であって、ビットストリームから、８分木構造を有し、第１スライスに含まれる複数のノードを取得し、前記ビットストリームから、前記複数のノードのうちの第１ノードの形状を導出するための情報を取得し、前記第１ノードを前記情報に従い復号し、前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる。
　本開示の一態様に係る符号化方法は、複数の三次元点を符号化する符号化方法であって、８分木構造を有し、第１スライスに含まれる複数のノードを符号化することでビットストリームを生成し、前記複数のノードのうちの第１ノードの形状を導出するための情報を前記ビットストリームに格納し、前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる。
　本開示は、符号化効率を向上できる復号方法、符号化方法、復号装置又は符号化装置を提供できる。
図１は、実施の形態に係る元点群の例を示す図である。 図２は、実施の形態に係る剪定８分木の例を示す図である。 図３は、実施の形態に係るリーフノードを二次元表示した例示す図である。 図４は、実施の形態に係るセントロイド頂点の生成方法を説明するための図である。 図５は、実施の形態に係るセントロイド頂点の生成方法を説明するための図である。 図６は、実施の形態に係る頂点情報の例を示す図である。 図７は、実施の形態に係るトライソープ・サーフェスの例を示す図である。 図８は、実施の形態に係る点群の復元処理を説明するための図である。 図９は、実施の形態に係るスライス分割の例を示す図である。 図１０は、実施の形態に係る頂点の例を示す図である。 図１１は、実施の形態に係る本来生成されるべきトライソープ・サーフェスの例を示す図である。 図１２は、実施の形態に係るエッジ頂点が生成されない場合のトライソープ・サーフェスの例を示す図である。 図１３は、実施の形態に係る復元される点群の例を示す図である。 図１４は、実施の形態に係る頂点の例を示す図である。 図１５は、実施の形態に係るトライソープ・サーフェスの例を示す図である。 図１６は、実施の形態に係る伝送情報の例を示す図である。 図１７は、実施の形態に係るＧＤＵヘッダのシンタックス例を示す図である。 図１８は、実施の形態に係る規定外幅ノードの調整幅の設定例を示す図である。 図１９は、実施の形態に係る符号化装置による符号化処理のフローチャートである。 図２０は、実施の形態に係る復号装置による復号処理のフローチャートである。 図２１は、実施の形態に係る規定外幅ノードの設定例を示す図である。 図２２は、実施の形態に係る規定外幅ノードの設定例を示す図である。 図２３は、実施の形態に係る規定外幅ノードの設定例を示す図である。 図２４は、実施の形態に係る規定外幅ノードの設定例を示す図である。 図２５は、実施の形態に係る規定外幅ノードの設定例を示す図である。 図２６は、実施の形態に係る規定外幅ノードの設定例を示す図である。 図２７は、実施の形態に係る規定外幅ノードの設定例を示す図である。 図２８は、実施の形態に係るノード幅と内包点座標の幅との関係を示す図である。 図２９は、実施の形態に係る規定外幅ノードの設定例を示す図である。 図３０は、実施の形態に係る規定外幅ノードの設定例を示す図である。 図３１は、実施の形態に係るＧＰＳ及びＧＤＵヘッダのシンタックス例を示す図である。 図３２は、実施の形態に係るスライス及びノードの例を示す図である。 図３３は、実施の形態に係るスライス及びノードの例を示す図である。 図３４は、実施の形態に係る省略を行う場合の処理の例を示す図である。 図３５は、実施の形態に係るＧＰＳ及びＧＤＵヘッダのシンタックス例を示す図である。 図３６は、実施の形態に係る開始端の調整処理の省略判定処理のフローチャートである。 図３７は、実施の形態に係る終了端の調整処理の省略判定処理のフローチャートである。 図３８は、実施の形態に係るノード位置の決定処理のフローチャートである。 図３９は、実施の形態に係るノード幅の決定処理のフローチャートである。 図４０は、実施の形態に係る復号処理のフローチャートである。 図４１は、実施の形態に係る復号装置のブロック図である。 図４２は、実施の形態に係る符号化処理のフローチャートである。 図４３は、実施の形態に係る復号装置のブロック図である。
　本開示の一態様に係る三次元データ復号方法は、複数の三次元点を復号する復号方法であって、ビットストリームから、８分木構造を有し、第１スライスに含まれる複数のノードを取得し、前記ビットストリームから、前記複数のノードのうちの第１ノードの形状を導出するための情報を取得し、前記第１ノードを前記情報に従い復号し、前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる。これによれば、規定形状とは異なる形状のノードを設定できる。よって、スライスの大きさ又は点群の分布状況に合わせて可変のノードを設定できる。よって、符号化効率を向上できる可能性がある。
　例えば、前記形状は直方体形状であり、立方体形状ではなくてもよい。例えば、前記第１スライスの端は、前記複数のノードのうちのいずれかのノードの端と一致していてもよい。これによれば、ノード端とスライス端とが一致しない場合に、ノード端とスライス端とを一致させることができる。よって、当該ノード端に頂点が生成されないことを抑制できるので、スライス境界における空白領域の発生を抑制できる。よって、復号される点群の精度を向上できる。
　例えば、前記情報は、前記形状のサイズ、又は、前記第１ノードの辺の両端の位置、を示してもよい。これによれば、復号装置は、当該情報を用いて規定形状と異なる形状のノードを生成できる。
　例えば、前記情報は、前記規定形状を前記形状に調整するための調整情報を含んでもよい。これによれば、復号装置は、調整情報を用いて規定形状と異なる形状のノードを生成できる。また、位置の情報の絶対量を送る場合に比べて、情報量を小さくできる可能性がある。
　例えば、前記復号は、前記複数の三次元点が前記第１ノード内の平面又は曲面で近似される圧縮方式に従い実行されてもよい。例えば、前記圧縮方式は、Ｔｒｉａｎｇｌｅ－Ｓｏｕｐ圧縮方式であってもよい。
　例えば、前記平面又は前記曲面を前記第１ノード内に生成するために前記形状が決定されてもよい。これによれば、規定形状とは異なる形状のノードを設定することで、平面又は曲面を第１ノード内に生成できる。
　例えば、前記形状の辺はその上に頂点を持ち、前記平面または前記曲面は、前記頂点で前記辺と交差してもよい。これによれば、規定形状とは異なる形状のノードを設定することで、平面又は曲面を第１ノード内に生成できる。
　例えば、前記第１ノードは、前記第１スライスに隣接する第２スライスと接して設けられてもよい。これによれば、例えば、ノード端とスライス端とが一致しない場合に、当該ノード端に頂点が生成されないことを抑制できるので、スライス境界における空白領域の発生を抑制できる。例えば、スライス境界で規定形状のノードしか設けない場合、スライス境界がノードを区切る場合がある。その場合、第１スライスに隣接する第２スライス内の点群を使って第１ノードの符号化又は復号を行うことができないので、スライス境界付近における三次元点群の復元精度が悪化する可能性がある。そこで、この態様では、規定形状とは異なる形状のノードを設定することで、例えば、第１ノードの端を第１スライスの端と一致させることができる。これにより、スライス境界付近における三次元点群の復元精度の悪化を抑制できる。なお、この態様をトライソープ方式に適用すれば、エッジ頂点が適切に生成されないことを抑制できる。
　例えば、前記情報はスライスごとに設けられ、前記第２スライスの前記情報は、８分木構造を有し、前記第２スライスに含まれる複数のノードのうちの第２ノードの形状を導出するために使用され、前記第２ノードの形状は前記規定形状と異なってもよい。これによれば、スライス毎にノードの形状を設定できる。
　例えば、前記規定形状のサイズは２のべき乗で表され、前記形状のサイズは２のべき乗で表されるサイズとは異なってもよい。
　例えば、前記第１ノードの前記形状は、第１方向に沿った第１の長さ、第２方向に沿った第２の長さ、および第３方向に沿った第３の長さによって定義され、前記第１方向、前記第２方向、および前記第３方向は互いに直交し、前記第１の長さ、前記第２の長さ及び前記第３の長さのうち前記第１の長さだけが前記第１ノード以外のノードの前記規定形状の長さと異なる、又は、前記第１の長さ、前記第２の長さ及び前記第３の長さのうち前記第１の長さ及び前記第２の長さだけが、それぞれ前記規定形状の長さと異なってもよい。
　例えば、前記第１ノードは、第１方向、第２方向及び第３方向のうちの一つの方向において、前記複数のノードのうちで前記第１スライスの原点に最も近く、前記第１方向、前記第２方向、および前記第３方向は互いに直交してもよい。これによれば、スライスの開始位置が原点と一致しない場合において、例えば、スライスの開始位置に合わせてノードの開始位置を調整できる。
　例えば、前記複数のノードは、前記規定形状とは異なる形状を持つ第３ノードを含み、前記第３ノードは、前記複数のノードのうち、前記一つの方向において前記原点から最も遠くてもよい。これによれば、スライスの終了位置がノードの終了位置と一致しない場合において、例えば、スライスの終了位置に合わせてノードの終了位置を調整できる。
　例えば、前記第１スライスの開始位置が原点と一致しない場合、前記ビットストリームは前記情報を含み、前記第１スライスの開始位置が原点と一致する場合、前記ビットストリームは前記情報を含まなくてもよい。これによれば、ノードの形状を調整するための処理の発生を低減できる。また、ノードの形状を導出するための情報の伝送を省略できる。よって、処理量の低減及びビットストリームのデータ量の低減を実現できる。
　例えば、前記第１スライスの終了位置が前記第１ノードの終了端と一致しない場合、前記ビットストリームは、前記情報を含み、前記第１スライスの終了位置が前記第１ノードの終了端と一致する場合、前記ビットストリームは前記情報を含まなくてもよい。これによれば、ノードの形状を調整するための処理の発生を低減できる。また、ノードの形状を導出するための情報の伝送を省略できる。よって、処理量の低減及びビットストリームのデータ量の低減を実現できる。
　本開示の一態様に係る三次元データ符号化方法は、複数の三次元点を符号化する符号化方法であって、８分木構造を有し、第１スライスに含まれる複数のノードを符号化することでビットストリームを生成し、前記複数のノードのうちの第１ノードの形状を導出するための情報を前記ビットストリームに格納し、前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる。これによれば、規定形状とは異なる形状のノードを設定できる。よって、スライスの大きさ又は点群の分布状況に合わせて可変のノードを設定できる。よって、符号化効率を向上できる可能性がある。
　また、本開示の一態様に係る復号装置は、複数の三次元点を復号する復号装置であって、プロセッサと、メモリと、を備え、前記プロセッサは、前記メモリを用いて、ビットストリームから、８分木構造を有し、第１スライスに含まれる複数のノードを取得し、前記ビットストリームから、前記複数のノードのうちの第１ノードの形状を導出するための情報を取得し、前記第１ノードを前記情報に従い復号し、前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる。
　また、本開示の一態様に係る符号化装置は、複数の三次元点を符号化する符号化装置であって、プロセッサと、メモリと、を備え、前記プロセッサは、前記メモリを用いて、８分木構造を有し、第１スライスに含まれる複数のノードを符号化することでビットストリームを生成し、前記複数のノードのうちの第１ノードの形状を導出するための情報を前記ビットストリームに格納し、前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる。
　なお、これらの包括的又は具体的な態様は、システム、方法、集積回路、コンピュータプログラム又はコンピュータ読み取り可能なＣＤ－ＲＯＭ等の記録媒体で実現されてもよく、システム、方法、集積回路、コンピュータプログラム及び記録媒体の任意な組み合わせで実現されてもよい。
　以下、実施の形態について、図面を参照しながら具体的に説明する。なお、以下で説明する実施の形態は、いずれも本開示の一具体例を示すものである。以下の実施の形態で示される数値、形状、材料、構成要素、構成要素の配置位置及び接続形態、ステップ、ステップの順序などは、一例であり、本開示を限定する主旨ではない。また、以下の実施の形態における構成要素のうち、独立請求項に記載されていない構成要素については、任意の構成要素として説明される。
　（実施の形態）
　以下、本実施の形態に係る符号化装置（三次元データ符号化装置）及び復号装置（三次元データ復号装置）について説明する。符号化装置は、三次元データを符号化することでビットストリームを生成する。復号装置は、当該ビットストリームを復号することで三次元データを生成する。
　三次元データは、例えば、三次元点群データ（点群データとも呼ぶ）である。点群は、複数の三次元点が集まったものであり、対象物（オブジェクト）の三次元形状を示す。点群データは、複数の三次元点の位置情報及び属性情報を含む。当該位置情報は、各三次元点の三次元位置を示す。なお、位置情報は、ジオメトリ（ｇｅｏｍｅｔｒｙ）情報とも呼ばれる場合がある。例えば、位置情報は、直交座標系又は極座標系で表される。
　属性情報は、例えば、色情報、反射率、透過率、赤外情報、法線ベクトル、又は時刻情報などを示す。１つの三次元点は、単一の属性情報を持つ場合もあれば、複数種類の属性情報を持つ場合もある。
　なお、以下では、主に位置情報の符号化及び復号について説明するが、符号化装置は、属性情報の符号化及び復号を行ってもよい。
　［トライソープ方式］
　本実施の形態に係る符号化装置は、トライソープ（ＴｒｉＳｏｕｐ：Ｔｒｉａｎｇｌｅ－Ｓｏｕｐ）方式を用いて位置情報を符号化する。
　トライソープ方式は、点群データの位置情報を符号化する方式の一つであり、不可逆圧縮方式である。トライソープ方式では、処理対象の元点群を三角形の集合に置き換え、その平面上に点群を近似する。具体的には、元点群をノード内の頂点情報に置き換え、頂点同士を結んで三角形群を生成する。また、三角形を生成するための頂点情報がビットストリームに格納され、復号装置へ送られる。
　まず、トライソープ方式を用いた符号化処理について説明する。図１は、元点群の例を示す図である。図１に示すように、対象物の点群１０２は、対象空間１０１に含まれ、複数の点１０３を含む。
　初めに、符号化装置は、元点群を所定の深さ（ｄｅｐｔｈ）まで８分木（Ｏｃｔｒｅｅ）分割する。８分木分割では、対象空間が８個のノード（サブ空間）に分割され、各ノードに点群が含まれるか否かを示す８ビットの情報（オキュパンシー符号）が生成される。また、点群が含まれるノードは、さらに、８個のノードに分割され、当該８個のノードの各々に点群が含まれるか否かを示す８ビットの情報が生成される。この処理が、予め定められた階層まで繰り返される。
　ここで、通常の８分木符号化では、例えば、ノードに含まれる点群の数の１つ又は閾値以下になるまで分割が繰り返される。一方、トライソープ方式は、８分木分割は途中の階層まで行われるが、当該階層以下の階層に対しては行われない。このような途中の階層までの８分木を、剪定８分木と呼ぶ。
　図２は、剪定８分木の例を示す図である。図２に示すように、点群１０２は、剪定８分木の複数のリーフノード１０４（最下層のノード）に分割される。
　次に、符号化装置は、剪定８分木のリーフノード１０４の各々に対して以下の処理を行う。なお、以下では、リーフノードを単にノードとも記す。符号化装置は、ノードのエッジ（ｅｄｇｅ）に近い点群の代表点として、エッジ上に頂点を生成する。この頂点をエッジ頂点と呼ぶ。例えば、エッジ頂点は、複数のエッジ（例えば平行な４辺）の各々に対して生成される。
　図３は、リーフノード１０４を二次元表示した例であり、例えば、図１に示すｚ方向から見たｘｙ平面を示す図である。図３に示すように、リーフノード１０４内の複数の点１１１のうちエッジの近接点に基づき、エッジ上にエッジ頂点１１２が生成される。
　なお、図３では、リーフノード１０４の外周の点線がエッジである。また、この例ではエッジとの距離が１以内の点（図３における範囲１１３に含まれる点）の位置の重み付き平均の位置にエッジ頂点１１２が生成される。なお、距離の単位は例えば点群の分解能であるが、これに限らない。また、この距離（閾値）は、この例では１であるが、１以外でもよく、可変であってもよい。
　次に、符号化装置は、複数のエッジ頂点を含む平面の法線方向に存在する点群に基づき、ノードの内部にも頂点を生成する。この頂点をセントロイド（ｃｅｎｔｒｏｉｄ）頂点と呼ぶ。
　図４及び図５は、セントロイド頂点の生成方法を説明するための図である。まず、符号化装置は、エッジ頂点群の中から例えば４点を代表点として選択する。図４に示す例ではエッジ頂点ｖ１～ｖ４が選択される。次に、符号化装置は、４点を通る近似平面１２１を算出する。次に、符号化装置は、近似平面１２１の法線ｎと、４点の平均座標Ｍとを算出する。次に、符号化装置は、平均座標Ｍから法線ｎの方向に延びる半直線に近い１以上の点（例えば図５に示す範囲１２２に含まれる点）の重み付き平均座標にセントロイド頂点Ｃを生成する。
　次に、符号化装置は、エッジ頂点とセントロイド頂点の情報である頂点情報をエントロピー符号化し、符号化された頂点情報を、ビットストリームに含まれるジオメトリデータユニット（Ｇｅｏｍｅｔｒｙ　Ｄａｔａ　Ｕｎｉｔ：以下、ＧＤＵと記す）に格納する。なお、ＧＤＵは、頂点情報に加え、剪定８分木を示す情報を含む。
　図６は、頂点情報の例を示す図である。上記の処理により、図６に示すように、点群１０２は頂点情報１２３に変換される。
　次に、上記で生成されたビットストリームの復号処理について説明する。まず、復号装置は、ビットストリームからＧＤＵを復号し、頂点情報を得る。次に、復号装置は、頂点同士を結び、三角形群であるトライソープ・サーフェス（ＴｒｉＳｏｕｐ－Ｓｕｒｆａｃｅ）を生成する。
　図７は、トライソープ・サーフェスの例を示す図である。図７に示す例では、頂点情報に基づき、４つのエッジ頂点ｖ１～ｖ４と、セントロイド頂点Ｃとが生成される。また、セントロイド頂点Ｃと、２つのエッジ頂点とを頂点とする三角形１３１（トライソープ・サーフェス）が生成される。例えば、隣接する２つエッジ上の２つのエッジ頂点の組がそれぞれ選択され、選択された組とセントロイド頂点とを頂点とする三角形１３１が生成される。
　図８は、点群の復元処理を説明するための図である。上記の処理がリーフノード毎に行われることで、図８に示すように、対象物を複数の三角形１３１で表現した三次元モデルが生成される。
　次に、復号装置は、三角形１３１の表面に一定間隔で点１３２を生成することで、点群１３３の位置情報を復元する。
　［スライス境界処理］
　以下、点群を複数のスライスに分割し、且つ、トライソープ方式を用いて符号化する場合について説明する。このような場合において、スライス幅がリーフノード幅の整数倍に一致しない場合、スライス境界で点が復元されない場合がある。具体的には、隣接する第１スライス及び第２スライスにまたがって点群が存在する場合、第１スライスに属するリーフノードであって第１スライスと第２スライスにまたがるリーフノードは、第２スライスに含まれる点群を含まないため、ノード内部に空白領域が発生するという問題がある。
　空白領域に接するノードのエッジには、空白領域が存在することにより、当該エッジに近い点群が存在しないため、当該エッジにエッジ頂点を生成することができない。または、この状態でエッジ頂点を生成する場合、点群とエッジの距離が離れるので、実際の点群分布を反映しない頂点位置となり、復号される点群の精度が悪くなるという問題がある。
　図９は、点群が上下方向に伸びている箇所をスライスに分割した場合の例を示す図である。図１０は、この場合に生成される頂点の例を示す図である。図１０に示す例では、スライス内を下から規定幅を有するノードで区切っている。この場合、スライス上端のノード１は空白領域を含む。これにより、上辺のエッジにエッジ頂点ｖ２を生成すべきであるが、エッジの近くに点群が無いためエッジ頂点ｖ２を生成できない。なお、図９及び図１０に示すスライス境界とはスライスのバウンディングボックスの境界である。
　図１１は、本来生成されるべきトライソープ・サーフェスの例を示す図である。図１２は、図１０に示すようにエッジ頂点が生成されない場合のトライソープ・サーフェスの例を示す図である。図１２に示すように、上辺のエッジにエッジ頂点ｖ２及びｖ３が生成されない場合、下辺のエッジ上の頂点ｖ１及びｖ４と、セントロイド頂点ｃとのみでトライソープ・サーフェスが生成される。これにより、本来、ノード内を縦断すべきトライソープ・サーフェスがノードの下部のみに生成される。
　図１３は、この場合の復元される点群の例を示す図である。図１３に示すように、トライソープ・サーフェスが無い箇所には点が復元されないので、図１３に示す領域２０１のように、復元される点群に横断的に穴が開いてしまう。
　本実施の形態では、スライスのバウンディングボックスの端に位置するノードの幅を、規定幅と異なる幅に設定する。これにより、ノード内の空白領域の発生を抑制し、上記の課題において生成できないエッジ頂点を生成できる。
　図１４は、この場合に生成される頂点の例を示す図である。図１５は、この場合のトライソープ・サーフェスの例を示す図である。図１４に示すように、スライス端に規定外幅を有するノード１を設ける。これにより、ノード１内の余白を解消し、エッジ頂点ｖ２を生成できる。よって、図１５に示すように、ノード内を縦断するトライソープ・サーフェスを生成できるので、復元された点群に横断的な穴が生成されることを解消できる。
　また、符号化装置は、この規定外幅ノードの調整幅を算出するための情報である調整幅情報として、例えば、スライス幅を示す情報をＧＤＵヘッダに格納する。
　ここで、規定外幅ノードとは、縦横高さのうちの少なくとも１つに沿う辺の長さが規定の長さ（規定幅）と異なるノードである。規定外幅ノードは、規定幅の立方体形状と異なる直方体又は立方体形状である。また、調整幅情報は、ノードの辺の規定の長さを、規定幅と異なる辺の長さ（規定外幅）の調整幅に調整するための情報である。例えば、調整幅情報は、調整幅の長さそのものを示してもよいし、規定幅と調整幅との差分を示してもよいし、規定幅と調整幅との比率を示してもよい。
　例えば、規定外幅ノードの調整幅（規定外幅）は、ｍｉｎ（スライス幅－ノード位置、規定幅）で表される。つまり、あるノードの規定外幅は、（スライス幅－ノード位置）と、規定幅とのうち、最小の値に設定される。ここで、ノード位置は、図１０に示すように、ノードの角のうち原点に最も近い角の位置（座標）である。
　上記により、スライスのバウンディングボックスの端のノードにもエッジ頂点を生成できる。これにより、トライソープ・サーフェスを途切れず配置できるため、復元された点群に穴あきが発生することを解消できる。
　なお、別の方法として、例えば以下の方法が用いられてもよい。なお、ここでは、符号化処理及び規格において課題を解決することに主眼を置く。
　第１スライスに含まれる点群も、第２スライスのリーフノードに含める。つまり、第１スライスと第２スライスとで重複する点群を持つ。
　第１スライスと第２スライスとの境界座標をリーフノード幅に一致させて点群をスライスに分割する。つまり、スライス分割による空白を持ったノードを生成しない。
　［シンタックス］
　以下、上記方式を実現するために、符号化装置から復号装置への送信される伝送情報について説明する。例えば、伝送情報は、ビットストリームに格納される。
　図１６は、この伝送情報の例を示す図である。図１６に示すように、ビットストリームに含まれるＧＤＵヘッダは、規定外幅処理フラグと、スライス幅情報とを含む。規定外幅処理フラグは、上述した規定外幅ノードを設定するか否かを示す情報である。例えば、値１は、規定外幅ノードを設定することを示し、値０は規定外幅ノードを設定しないことを示す。スライス幅情報は、スライス幅（スライスのバウンディングボックスの幅）を示す。
　図１７は、ＧＤＵヘッダ（ｇｅｏｍｅｔｒｙ＿ｄａｔａ＿ｕｎｉｔ＿ｈｅａｄｅｒ）のシンタックス例を示す図である。図１７に示すようにスライス幅情報は、規定外幅処理フラグが値１（ｔｒｕｅ）の場合にのみＧＤＵヘッダに格納される。また、スライス幅情報は、例えば、スライスのｘ、ｙ、ｚ軸のそれぞれの幅を示す情報で構成される。
　スライス幅情報は、スライス単位の情報であり、ここでは、規定外幅処理フラグ及びスライス幅情報が、スライス単位のヘッダであるＧＤＵヘッダに格納される。
　なお、規定外幅処理フラグは、スライス幅情報がビットストリームに含まれるか否かを示す情報であってもよい。また、本実施の形態で示すフラグ及び情報等の名称は一例であり、任意の名称を用いることができる。
　図１８は、規定外幅ノードの調整幅の設定例を示す図である。上述したように調整幅はｍｉｎ（スライス幅－ノード位置、規定幅）で表される。図１８は、ｘ軸方向の調整幅の設定の例を示す。この例では、調整幅＝ｍｉｎ（１００－９６、３２）＝４である。なお、ｙ軸及びｚ軸方向についても同様に算出可能である。
　なお、ここでは、規定外幅処理フラグ及びスライス幅情報がスライス毎に格納される例を述べたが、これらの情報が複数のスライスで共通であってもよい。この場合には、これらの情報は、ＳＰＳ又はＧＰＳなどのＧＤＵヘッダよりも上位のヘッダに格納されてもよい。ＳＰＳ（Ｓｅｑｕｅｎｃｅ　Ｐａｒａｍｅｔｅｒ　Ｓｅｔ）は、複数フレーム共通のメタデータ（パラメータセット）である。ＧＰＳ（Ｇｅｏｍｅｔｒｙ　Ｐａｒａｍｅｔｅｒ　Ｓｅｔ）は、位置情報の符号化に関わるメタデータ（パラメータセット）である。例えば、ＧＰＳは、複数フレームに共通のメタデータである。
　また、これらの情報を、上位のヘッダに格納するか、スライス毎に格納するかを示すフラグがＳＰＳ又はＧＰＳに格納されてもよい。この場合、当該フラグに基づき、これらの情報の格納先が切り替えられる。
　また、これらの情報はトライソープ方式の固有の処理のためのものなので、符号化方式がトライソープ方式である場合にのみ、ビットストリームに格納されてもよい。
　［処理フロー］
　以下、符号化装置及び復号装置における処理の流れを説明する。図１９は、符号化装置による符号化処理のフローチャートである。
　まず、符号化装置は、剪定８分木を生成し、剪定８分木を示す８分木情報をＧＤＵに格納する（Ｓ１０１）。例えば、符号化装置は、８分木情報をエントロピー符号化し、符号化された８分木情報をＧＤＵに格納する。
　次に、符号化装置は、スライス幅（スライスのバウンディングボックスの幅）が規定幅の整数倍であるか否かを判定する（Ｓ１０２）。スライス幅が規定幅の整数倍でない場合（Ｓ１０２でＮｏ）、符号化装置は、規定外幅処理フラグ＝１と、スライス幅情報とをＧＤＵヘッダに格納する（Ｓ１０３）。
　一方、スライス幅が規定幅の整数倍である場合（Ｓ１０２でＹｅｓ）、符号化装置は、規定外幅処理フラグ＝０をＧＤＵヘッダに格納する（Ｓ１０４）。
　次に、符号化装置は、剪定８分木の複数のリーフノードの各々に対して以下のステップＳ１０５～Ｓ１０９の処理を行う。
　まず、符号化装置は、規定外幅処理フラグ＝１であるか否かを判定する（Ｓ１０５）。規定外幅処理フラグ＝１である場合（Ｓ１０５でＹｅｓ）、符号化装置は、対象ノードがスライス端（スライスのバウンディングボックスの端）に存在するか否かを判定する（Ｓ１０６）。例えば、符号化装置は、対象ノードがスライス境界を含む場合、対象ノードがスライス端に存在すると判定し、対象ノードがスライス境界を含まない場合、対象ノードがスライス端に存在しないと判定する。
　対象ノードがスライス端に存在する場合（Ｓ１０６でＹｅｓ）、符号化装置は、スライス幅情報で示されるスライス幅と対象ノードのノード位置とから調整幅を算出し、対象ノードを、算出した調整幅を有する規定外幅ノードに設定する（Ｓ１０７）。
　一方、規定外幅処理フラグ＝０である場合（Ｓ１０５でＮｏ）、又は対象ノードがスライス端に存在しない場合（Ｓ１０６でＮｏ）、符号化装置は、対象ノードの幅を規定幅に設定する（Ｓ１０８）。
　次に、符号化装置は、対象ノード内の点群分布に基づき、対象ノードのエッジ上にエッジ頂点を生成し、対象ノードの内部にセントロイド頂点を生成する（Ｓ１０９）。以上により、対象ノードに対するループ処理が終了する。
　全てのリーフノードに対するループ処理が終了した後、符号化装置は、複数のリーフノードのエッジ頂点及びセントロイド頂点の位置を示す頂点情報をエントロピー符号化し、符号化された頂点情報をＧＤＵに格納する（Ｓ１１０）。
　次に、符号化装置は、ＧＤＵヘッダ及びＧＤＵを含むビットストリームを生成し、当該ビットストリームを出力する（Ｓ１１１）。つまり、符号化装置は、ビットストリームを復号装置へ伝送する。
　図２０は、復号装置による復号処理のフローチャートである。まず、復号装置は、ビットストリームからＧＤＵヘッダ及びＧＤＵを取得する（Ｓ１２１）。次に、復号装置は、ＧＤＵヘッダから規定外幅処理フラグを取得し、規定外幅処理フラグ＝１であるか否かを判定する（Ｓ１２２）。
　規定外幅処理フラグ＝１である場合（Ｓ１２２でＹｅｓ）、復号装置は、ＧＤＵヘッダからスライス幅情報を取得する（Ｓ１２３）。一方、規定外幅処理フラグ＝０である場合（Ｓ１２２でＮｏ）、復号装置は、ＧＤＵヘッダからスライス幅情報を取得しない。
　次に、復号装置は、ＧＤＵから８分木情報を取得する。例えば、復号装置は、ＧＤＵに含まれる符号化された８分木情報をエントロピー復号することで８分木情報を取得する。次に、復号装置は、８分木情報を用いて剪定８分木のリーフノード群を生成する（Ｓ１２４）。
　次に、復号装置は、剪定８分木の複数のリーフノードの各々に対して以下のステップＳ１２５～Ｓ１３０の処理を行う。
　まず、復号装置は、規定外幅処理フラグ＝１であるか否かを判定する（Ｓ１２５）。規定外幅処理フラグ＝１である場合（Ｓ１２５でＹｅｓ）、復号装置は、対象ノードがスライス端（スライスのバウンディングボックスの端）に存在するか否かを判定する（Ｓ１２６）。例えば、復号装置は、対象ノードがスライス境界を含む場合、対象ノードがスライス端に存在すると判定し、対象ノードがスライス境界を含まない場合、対象ノードがスライス端に存在しないと判定する。
　対象ノードがスライス端に存在する場合（Ｓ１２６でＹｅｓ）、復号装置は、スライス幅情報で示されるスライス幅と対象ノードのノード位置とから調整幅を算出し、対象ノードを、算出した調整幅を有する規定外幅ノードに設定する（Ｓ１２７）。
　一方、規定外幅処理フラグ＝１でない場合（Ｓ１２５でＮｏ）、又は対象ノードがスライス端に存在しない場合（Ｓ１２６でＮｏ）、復号装置は、対象ノードの幅を規定幅に設定する（Ｓ１２８）。
　次に、復号装置は、ＧＤＵからエッジ頂点及びセントロイド頂点の位置を示す頂点情報を取得する（Ｓ１２９）。例えば、復号装置は、ＧＤＵに含まれる符号化された頂点情報をエントロピー復号することで頂点情報を取得する。
　次に、復号装置は、頂点情報で示される複数の頂点を接続することで三角形群を生成する（Ｓ１３０）。以上により、対象ノードに対するループ処理が終了する。
　全てのリーフノードに対するループ処理が終了した後、復号装置は、複数の三角形の表面に一定間隔で点を発生させることで復号点群を生成する（Ｓ１３１）。
　［変形例］
　上記説明では、規定外幅ノードが、スライスの末尾（図１８の右端）に生成される例を述べたが、規定外幅ノードが生成される位置はこれに限らない。図２１～図２４は、規定外幅ノードの設定例を示す図である。
　例えば、図２１に示すように、規定外幅ノードの位置は、スライスの中ほどであってもよい。または、図２２に示すように、規定外幅ノードの位置は、スライスの先頭であってもよい。
　また、図２３及び図２４に示すように、複数の規定外幅ノードが設定されてもよい。例えば、図２３に示すように、２つの規定外幅ノードが、スライスの両端に設定されてもよい。または、図２４に示すように、２つの規定外幅ノードが、スライスの端と、スライスの中ほどとに設定されてもよい。
　このように、複数の規定外幅ノードを設定する場合には、複数の規定外幅ノードの幅の合計が上記の調整幅になればよい。
　これらを踏まえると、調整幅の算出方法、及び、ビットストリームに格納される、規定外幅ノードのための情報である規定外幅ノード情報として、以下を用いることができる。
　図２１及び図２２に示すように規定外幅ノードがスライスの終了端以外に配置される場合には、規定外幅ノード情報は、調整幅を示す調整幅情報と、規定外幅ノードの挿入位置を示す挿入位置情報とを含む。例えば、図２１に示す例では、挿入位置情報は、ビット列「４ｂ００１０」を示す。また、図２２に示す例では、挿入位置情報は、ビット列「４ｂ１０００」を示す。なお、ビット列の複数のビットはそれぞれノードに対応し、規定外幅ノードに対応するビットが１に、それ以外が０に設定される。
　なお、別の方法として、挿入位置情報は、規定外幅ノードを特定する情報を示してもよい。例えば、ノードに通し番号（識別子）が付与されており、挿入位置情報は、規定外幅ノードの通し番号を示してもよい。例えば、スライス内の軸毎に通し番号が設定されてもよい。この場合、図２１に示す例では、左のノードから順に１、２、３、４の通し番号が設定され、挿入位置情報は、値３を示す。なお、通し番号は、スライス内の全ノードに対する通し番号でもよい。
　この場合、復号装置は、挿入位置情報を用いて、対象ノードが規定外幅ノードであるか否かを判別できる。また、調整幅を図１８で示す場合と同じ方法で算出できる。
　一方、図２３及び図２４に示すように、規定外幅ノードがスライス内の複数の位置に配置される場合、挿入位置情報は、複数の規定外幅ノードの個々の挿入位置を示す。例えば、図２３に示す例では、挿入位置情報は、ビット列「５ｂ１００１」を示す。図２４に示す例では、挿入位置情報は、ビット列「５ｂ１００１０」を示す。なお、ここでは、１つの軸（この例ではｘ軸）に対して１つのビット列を用いる例（つまり、軸毎に異なるビット列を用いる例）を示したが、スライス内の全ノードに対して１つのビット列が用いられてもよい。
　また、図２３及び図２４に示す例では、調整幅情報は、２つの規定外幅ノードの各々の調整幅を示す。具体的には、調整幅情報は、１つの目の規定外幅ノードの調整幅である値２と、２つの目の規定外幅ノードの調整幅である値２とを示す。
　または、調整幅情報は、２つの規定外幅ノードの調整幅の合計と、１つの規定外幅ノードの調整幅とを示してもよい。この場合でも、復号装置は、調整幅情報から２つの規定外幅ノードの調整幅を算出できる。この場合は、例えば、１つの軸上の規定外幅ノードの並びのうち最後に位置する規定外幅ノードの調整幅の情報が省略されると予めルールが決められ、復号装置は当該ルールに基づき、調整幅情報から２つの規定外幅ノードの調整幅を算出してもよい。また、規定外幅ノード情報は、軸毎の情報ではなく、スライス内の全規定外幅ノードの個別の情報で構成されてもよい。
　例えば、図２４に示す例では、４番目のノードの調整幅情報が省略された場合、４番目のノードの調整幅は、調整幅の合計（４）－１番目のノードの調整幅（２）＝２として求まる。
　また、スライスのバウンディングボックスの開始位置は、スライス境界からオフセットを持ってもよい。図２５は、この場合の規定外幅ノードの設定例を示す図である。図２５に示す例は、スライスの終了端のノードが規定外幅ノードに設定される場合の例である。
　この場合、規定外幅ノード情報は、原点座標からスライスのバウンディングボックスの開始位置までのオフセット量を含む。復号装置は、このオフセット量を用いて調整幅を算出できる。
　具体的には、調整幅は、ｍｉｎ（スライス幅（１００）－ノード位置（１２１）＋オフセット量（２５）、規定幅）＝ｍｉｎ（４、３２）＝４として求まる。
　また、復号装置は、８分木情報を用いて、対象ノードがスライス端に位置するか否かを判定してもよい。例えば、ある座標軸について、深度＝０のルートノードから順に、オキュパンシー符号を参照して、原点に近い側、又は遠い側のみを辿り続けることで、スライス端のノードを判定できる。この場合、規定外幅ノード情報は、スライス端のノードの調整幅である端数ノード幅を示す情報を含む。復号装置は、当該情報を用いて、スライス端のノードの調整幅を端数ノード幅に設定する。
　図２６は、この場合の規定外幅ノードの設定例を示す図である。この例では端数ノード幅＝４であり、復号装置は、対象ノードがスライス端のノードの場合、当該ノードの幅を４に設定し、そうでなければ当該ノードの幅を３２に設定する。
　また、規定外幅は、規定幅より大きい値であってもよい。例えば、図２１に示す例において、３番目のノードと４番目のノードとが結合されてもよい。つまり、ノードの幅が左から順に３２、３２、３６となる３つのノードが設定されてもよい。
　また、あるノードについて、ｘ軸、ｙ軸、ｚ軸の３軸とも規定外幅を採用した結果、そのノードが立方体となっても良い。
　または、スライス幅情報の代わりに、規定外幅ノードのサイズを復元できるような、ノードの角の位置情報が伝送されてもよい。例えば、当該位置情報は、規定外幅の方向の２つの角の座標情報であってもよいし、８つの角全ての座標情報であってもよい。
　符号化装置は、上記の調整幅算出のための規定外幅ノード情報を量子化し、量子化後の情報を復号装置に伝送してもよい。この場合、復号装置は、当該量子化後の情報を逆量子化し、得られた規定外幅ノード情報を用いて、上記の処理を行ってもよい。この場合、規定外幅ノード内の空白領域の幅が完全に０にならないケースが発生する可能性がある。一方で、量子化を行うことで伝送される情報のデータ量を削減できる。
　以上の各々の考え方の組み合わせによって規定外幅ノードの情報が伝送されてもよい。
　なお、８分木符号化の対象のバウンディングボックスの大きさ（元のデータのビット深度）、及び、８分木分割をどの深さまで進めるかに応じて、ノードの規定幅（ｄｅｆａｕｌｔ　ｓｉｚｅ）が決定される。この規定幅は、例えば２のべき乗で表現される。
　また、上記説明では、規定外幅ノードは、縦横高さのうちの少なくとも１つに沿う辺の長さが規定幅と異なるノードであったが、１方向のみの長さ、又は、２方向のみの長さが規定幅と異なってもよい。すなわち、規定外幅ノードは、直方体であってもよい。
　また、上記説明では、ノードの平行な４つのエッジ上に存在する４つのエッジ頂点が求められたが、求められるエッジ頂点は４つに限らない。エッジ頂点の数は、近似平面が求められる限り、特に限定されない。
　また、セントロイド頂点の求め方は、上記の方式に限定されない。復号装置で三角形の平面が求められる限り、他の方式でセントロイド頂点が求められてもよい。
　また、上記説明では、圧縮方式としてトライソープ方式が用いられていたが、本実施の形態の手法は、トライソープ方式以外の圧縮方式に対しても有効である。すなわち、本実施の形態の手法は、ノード内の平面又は曲面で点群を近似する圧縮方式であって、当該平面又は当該曲面の生成のためにエッジ頂点を必要とする圧縮方式に対して有効である。
　また、上記説明では、規定外幅ノードの辺の規定外の長さが求められていたが、規定外の長さを求めることは必須ではない。規定外幅ノードの形状が求められればよく、例えば、規定外の長さの辺の２端の位置が求められてもよい。すなわち、規定外幅ノードの位置が求められてもよい。
　［原点側の調整方法］
　図２５において、スライスのバウンディングボックスの開始位置が原点と一致しない場合について説明した。以下、この場合の詳細について説明する。
　スライスの原点は規定のないオフセット量であり、スライスのバウンディングボックスの開始位置は、原点と必ずしも一致しない。よって、このオフセット量を減算した後のスライスの点群が、符号化座標系の原点から離れて分布するケースもありうる。つまり、符号化座標系の原点とスライスのバウンディングボックスの原点とが異なるケースがある。また、この場合、スライスのバウンディングボックスの境界が、リーフノードの境界と一致しないこともありうる。この場合、スライスのバウンディングボックスの原点側の側面及びバウンディングボックスの原点から遠い側の側面の両方に規定外幅ノードを生成する必要がある。
　符号化装置は、復号装置が、これら規定外幅ノードのノード位置及びノード幅（調整幅）を算出するための情報として、スライスのバウンディングボックスの先頭座標であるスライス位置とバウンディングボックスの幅であるスライス幅とを復号装置へ伝送する。
　図２７は、この場合の規定外幅ノードの設定例を示す図である。図２７では、符号化座標系を一次元的に表記している。また、網掛けの領域は点群が分布している領域（スライス）である。また、図２７に示す原点は、符号化座標系の原点である。
　ここで、ノードの規定幅をＷとし、スライス位置をＡとし、スライス幅をＢとし、元のノード位置をｎｏｄｅＰｏｓとすると、調整後のノード位置ｎｅｗＮｏｄｅＰｏｓと調整後のノード幅ｎｅｗＮｏｄｅＷｉｄｔｈとは以下で求まる。
　ｎｅｗＮｏｄｅＰｏｓ＝（ｎｏｄｅＰｏｓ＜Ａ）？Ａ：ｎｏｄｅＰｏｓ；
　ｎｅｗＮｏｄｅＷｉｄｔｈ＝（ｎｏｄｅＰｏｓ＜Ａ）？（Ｗ－（Ａ－ｎｏｄｅＰｏｓ））：ｍｉｎ（Ａ＋Ｂ－ｎｏｄｅＰｏｓ＋１，Ｗ）
　上記により、ノード位置は、ｎｏｄｅＰｏｓ＜ＡであればＡに調整され、そうでなければ調整されない。つまり、先頭ノードであるノード１のノード位置がＰ１からＡに変更され、その他のノードのノード位置は変更されない。
　また、ノード幅は、ｎｏｄｅＰｏｓ＜Ａであれば（Ｗ－（Ａ－ｎｏｄｅＰｏｓ））に調整され、そうでなければｍｉｎ（Ａ＋Ｂ－ｎｏｄｅＰｏｓ＋１，Ｗ）に設定される。つまり、ノード１のノード幅はＷ１＝Ｗ－（Ａ－ｎｏｄｅＰｏｓ）＝Ｗ－（Ａ－Ｐ１）に調整される。終了端のノードであるノード２のノード幅はＷ２＝ｍｉｎ（Ａ＋Ｂ－ｎｏｄｅＰｏｓ＋１，Ｗ）＝Ａ＋Ｂ－Ｐ２＋１に設定される。それ以外のノードのノード幅はＷに設定される。ここで、「＋１」が用いられている理由は、ノード幅＝内包点座標の幅＋１の関係があるからである。図２８は、ノード幅と内包点座標の幅との関係を示す図である。例えば、Ｗ＝８、Ａ＝０、Ｂ＝５、ｎｏｄｅＰｏｓ＝０の場合、図２８に示すようにｎｅｗＮｏｄｅＷｉｄｔｈ＝６となる。
　また、復号装置は、ビットストリーム内のヘッダに含まれる規定外幅処理フラグ＝１である場合、伝送情報からＡとＢを求め、各ノードの初期のノード位置及び初期のノード幅から、上記式を用いて、ノード１及びノード２の調整後のノード位置と調整後のノード幅を算出する。
　なお、図２１～図２４に示したように、この場合にも、規定外幅ノードの位置は、スライスの先頭、スライスの中ほど、スライスの両端、又は複数位置に位置していてもよい。
　また、規定外幅ノードを同一軸上の複数位置に設ける場合は、それらの合計のノード幅が上記の調整幅になればよい。
　これらを踏まえると、算出方法、及び、ビットストリームに格納される、規定外幅ノードのための情報である規定外幅ノード情報として、以下を用いることができる。
　図２９は、規定外幅ノードの設定例を示す図である。図２９に示すようにスライス境界の枠の中で、スライスのバウンディングボックスの開始位置が原点からオフセットを持ち、かつスライス幅（９５）がノードの規定幅（３２）の倍数でない場合、符号化装置が、原点からバウンディングボックスの開始位置までのオフセット量を復号装置へ伝送すれば、復号装置は、原点側のノード１の調整位置と調整幅を算出できる。
　また、符号化装置が、スライス幅を復号装置へ伝送すれば、復号装置は、原点から遠い側のノード２の調整幅を算出できる。
　具体的には、ここで、図２９に示すように原点側のノード１の調整前のノード位置が３２である場合、ノード１の調整位置＝（３２＜３７）？３７：３２＝３７である。また、ノード１の調整幅＝（３２＜３７）？（３２－（３７－３２））：ｍｉｎ（３７＋９５－３２＋１、３２）＝２７である。
　原点から遠い側のノード２の調整位置＝（１２８＜３７）？（３２－（３７－１２８））：ｍｉｎ（３７＋９５－１２８＋１、３２）＝５である。
　また、規定外幅ノード情報は、上記のノード位置とスライスのバウンディングボックスとの位置関係から算出するための情報に加え、規定外幅ノードを指定する情報と、指定されたノードに対して、そのノードの調整位置及び調整幅を示す情報が含まれてもよい。規定外幅ノードを指定する情報は、例えば、ノードに付与された通し番号を示す。
　図３０は、この場合の規定外幅ノードの設定例を示す図である。図３０に示す例では、ノードの通し番号であるノード番号として０～３が付与される。ノード番号＝０のノードの調整位置と調整幅をＰ０、Ｗ０とし、ノード番号＝３のノードの調整位置と調整幅をＰ１、Ｗ１とすると、図３０に示す例ではＰ０＝３７、Ｗ０＝２７、Ｐ１＝１２８、Ｗ１＝５であり、これらの情報が伝送される。
　なお、図２９では、規定外幅ノードの判別と、その位置及び幅の算出方法を説明したが、規定外幅ノードの判別方法に、図２１～図２６で説明したいずれかの方式を用いてもよい。
　また、本方式の実現のための、符号化装置から復号装置へ伝送する伝送情報を以下に示す。図３１は、ＧＰＳ（ｇｅｏｍｅｔｒｙ＿ｐａｒａｍｅｔｅｒ＿ｓｅｔ）及びＧＤＵヘッダのシンタックス例を示す図である。
　ＧＰＳは、第１規定外幅処理フラグと、第２規定外幅処理フラグとを含む。第１規定外幅処理フラグは、原点に近い側のスライス端に位置するノードに、上述したノード位置及びノード幅の調整を行うか否かを示す情報である。例えば、値１は当該調整を行うことを示し、値０は当該調整を行わないことを示す。
　第２規定外幅処理フラグは、原点から遠い側のスライス端に位置するノードに、上述したノード幅の調整を行うか否かを示す情報である。例えば、値１は当該調整を行うことを示し、値０は当該調整を行わないことを示す。
　ＧＤＵヘッダは、第１規定外幅処理フラグが１の場合、第１ビット長情報と、第１量子化パラメータと、スライス位置情報とを含む。
　スライス位置情報は、スライスのバウンディングボックスの位置（座標）であるスライス位置を示し、例えば、スライスのバウンディングボックスの角のうち原点に最も近い角の三次元座標（ｘ、ｙ、ｚ座標）を示す。
　第１ビット長情報は、スライス位置情報のビット長を示す。第１量子化パラメータは、スライス位置情報の量子化に用いられる量子化パラメータ（量子化値）を示す。
　ＧＤＵヘッダは、第２規定外幅処理フラグが１の場合、第２ビット長情報と、第２量子化パラメータと、スライス幅情報とを含む。
　スライス幅情報は、スライスのバウンディングボックスの幅であるスライス幅を示す。例えば、スライス幅情報は、バウンディングボックスのｘ、ｙ、ｚ方向のそれぞれの幅を示す。
　第２ビット長情報は、スライス幅のビット長を示す。第２量子化パラメータは、スライス幅情報の量子化に用いられる量子化パラメータを示す。
　ここで、スライス位置は、スライス位置情報＜＜第１量子化パラメータで表され、スライス幅は、スライス幅情報＜＜第２量子化パラメータで表される。
　なお、ここでは、これらの情報がスライス毎に格納される例を述べたが、これらの情報が複数のスライスで共通の場合には、これらの情報は、ＳＰＳ又はＧＰＳなどのＧＤＵヘッダよりも上位のヘッダに格納されてもよい。また、これらの情報を、上位のヘッダに格納するか、スライス毎に格納するかを示すフラグがＳＰＳ又はＧＰＳに格納されてもよい。この場合、当該フラグに基づき、これらの情報の格納先が切り替えられる。また、ｘ、ｙ、ｚの各軸毎にこれらの情報が個別に設けられてもよい。
　また、符号化装置は、図３１に示す第１規定外幅処理フラグ及び第２規定外幅処理フラグを伝送しなくてもよい。この場合、復号装置は、第１量子化パラメータ＝０である場合に、原点に近い側のスライス端に位置するノードに、上述したノード位置及びノード幅の調整を行わず、それ以外の場合に、当該調整を行う。また、復号装置は、第２量子化パラメータ＝０である場合に、原点から遠い側のスライス端に位置するノードに、上述したノード幅の調整を行わず、それ以外の場合に、当該調整を行う。
　また、スライス位置情報及びスライス幅情報は、符号化座標系の数値なので正の値であると定められてもよい。
　［伝送及び処理の省略］
　上記説明では、符号化対象の点群について常にスライス幅情報及びスライス位置情報をヘッダに格納し、全スライスの全ノードに対してノードの位置と幅を再計算する必要がある。実際には符号化対象のスライスの開始端が原点に一致、又はスライスの終了端がたまたまノードの終了端に一致している場合がある。この場合は、スライスの開始端のノード又は終了端のノードに対してノード位置又はノード幅の調整処理を行う必要が無いので、この調整処理のための情報の伝送と、ノード位置及びノード幅の再計算処理を省略できる。
　符号化装置は、この省略判定を行い、判定結果を示す情報を復号装置に伝送する。この伝送には専用のフラグが用いられてもよいし、前述の第１ビット長情報及び第２ビット長情報が用いられてもよい。具体的には、第１ビット長情報が０を示す場合、スライス位置情報の伝送を省略することを意味し、第２ビット長情報が０を示す場合、スライス幅情報の伝送を省略することを意味する。これによってヘッダのデータ量を抑制できるとともに、符号化処理の処理時間を短縮できる。
　図３２は、スライスの開始端が原点に一致している場合のスライス及びノードの例を示す図である。この場合、開始端の調整処理は不要である。
　図３３は、スライスの開始端が原点に一致し、かつ、スライスの終了端がノードの終了端に一致している場合のスライス及びノードの例を示す図である。この場合、開始端及び終了端の両方について調整処理が不要である。
　図３４は、上記の省略を行う場合の処理（シンタックス）の例を示す図である。同図に示すｓｌｉｃｅ＿ｂｂ＿ｐｏｓ＿ｂｉｔｓは、スライス位置情報のビット長を示す第１ビット長情報である。ｓｌｉｃｅ＿ｂｂ＿ｗｉｄｔｈ＿ｂｉｔｓは、スライス幅情報のビット長を示す第２ビット長情報である。また、Ａはスライス位置であり、Ｂはスライス幅であり、ｎｏｄｅＰｏｓはノード位置（調整前のノード位置）であり、ｎｏｄｅＷｉｄｔｈはノード幅（調整前のノード幅）であり、ｎｅｗＮｏｄｅＷｉｄｔｈは調整後のノード幅であり、Ｗはノードの規定幅である。
　この処理では、スライス位置情報のビット長が０より大きい値である場合に限定して調整処理が行われるので、符号化処理の処理時間を削減できる。また、スライスの開始端が原点に一致、又は終了端がたまたまノードの終了端に一致している場合に、ヘッダのデータ量を削減できる。
　図３５は、この場合のＧＰＳ及びＧＤＵヘッダのシンタックス例を示す図である。図３５に示すシンタックスは、図３１に示すシンタックスに対して、第１ビット長情報が０より大きい場合にのみ、ＧＤＵヘッダに、第１量子化パラメータ及びスライス位置情報が格納されるという条件と、第２ビット長情報が０より大きい場合にのみ、ＧＤＵヘッダに、第２量子化パラメータ及びスライス幅情報が格納されるという条件と、が追加されている。
　この条件の追加により、スライスの開始端が原点に一致、又は終了端がノードの終了端に一致している場合に、ヘッダのデータ量を削減できる。
　図３６は、開始端の調整処理（スライス位置の伝送）の省略判定処理のフローチャートである。符号化装置は、スライスの開始位置（スライスのバウンディングボックスの開始端の座標）が原点に一致しているか否かを判定する（Ｓ２０１）。
　スライスの開始位置が原点に一致している場合（Ｓ２０１でＹｅｓ）、符号化装置は、スライス位置情報を伝送しない（Ｓ２０２）。つまり、符号化装置は、ｓｌｉｃｅ＿ｂｂ＿ｐｏｓ＿ｂｉｔｓ＝０をビットストリームに格納するとともに、スライス位置情報をビットストリームに格納しない。
　一方、スライスの開始位置が原点に一致していない場合（Ｓ２０１でＮｏ）、符号化装置は、スライス位置情報を伝送する（Ｓ２０３）。つまり、符号化装置は、０より大きい値に設定されたｓｌｉｃｅ＿ｂｂ＿ｐｏｓ＿ｂｉｔｓと、スライス位置情報とをビットストリームに格納する。
　なお、上記の判定は、第１規定外幅処理フラグが１の場合にのみ行われてもよい。また、第１規定外幅処理フラグが０の場合には、スライス位置情報は伝送されない。
　図３７は、終了端の調整処理（スライス幅の伝送）の省略判定処理のフローチャートである。符号化装置は、スライスの終了位置（スライスのバウンディングボックスの終了端の座標）がノードの終了端に一致しているか否かを判定する（Ｓ２１１）。
　スライスの終了位置がノードの終了端に一致している場合（Ｓ２１１でＹｅｓ）、符号化装置は、スライス幅情報を伝送しない（Ｓ２１２）。つまり、符号化装置は、ｓｌｉｃｅ＿ｂｂ＿ｗｉｄｔｈ＿ｂｉｔｓ＝０をビットストリームに格納するとともに、スライス幅情報をビットストリームに格納しない。
　一方、スライスの終了位置がノードの終了端に一致していない場合（Ｓ２１１でＮｏ）、符号化装置は、スライス幅情報を伝送する（Ｓ２１３）。つまり、符号化装置は、０より大きい値に設定されたｓｌｉｃｅ＿ｂｂ＿ｗｉｄｔｈ＿ｂｉｔｓと、スライス幅情報とをビットストリームに格納する。
　なお、上記の判定は、第２規定外幅処理フラグが１の場合にのみ行われてもよい。また、第２規定外幅処理フラグが０の場合には、スライス幅情報は伝送されない。
　図３８は、ノード位置の決定処理のフローチャートである。例えば、図３８に示す処理はノード毎に行われる。
　まず、符号化装置は、第１ビット長情報（ｓｌｉｃｅ＿ｂｂ＿ｐｏｓ＿ｂｉｔｓ）が０より大きいか否かを判定する（Ｓ２２１）。
　第１ビット長情報が０より大きい場合（Ｓ２２１でＹｅｓ）、符号化装置は、対象ノードのノード位置（ｎｏｄｅＰｏｓ）がスライス位置より小さいか否かを判定する（Ｓ２２２）。
　ノード位置がスライス位置より小さい場合（Ｓ２２２でＹｅｓ）、符号化装置は、スライス位置を調整後のノード位置として設定する（Ｓ２２３）。
　一方、第１ビット長情報が０の場合（Ｓ２２１でＮｏ）、又は、ノード位置がスライス位置以上の場合（Ｓ２２２でＮｏ）、符号化装置は、ノード位置を変更（調整）しない（Ｓ２２４）。
　なお、復号装置においても同様の処理が行われる。
　図３９は、ノード幅の決定処理のフローチャートである。例えば、図３９に示す処理はノード毎に行われる。
　まず、符号化装置は、第１ビット長情報（ｓｌｉｃｅ＿ｂｂ＿ｐｏｓ＿ｂｉｔｓ）が０より大きいか否かを判定する（Ｓ２３１）。
　第１ビット長情報が０より大きい場合（Ｓ２３１でＹｅｓ）、符号化装置は、対象ノードのノード位置（ｎｏｄｅＰｏｓ）がスライス位置より小さいか否かを判定する（Ｓ２３２）。
　ノード位置がスライス位置より小さい場合（Ｓ２３２でＹｅｓ）、符号化装置は、規定幅（Ｗ）－（スライス位置（Ａ）－ノード位置（ｎｏｄｅＰｏｓ））を調整後のノード幅（ｎｏｄｅＷｉｄｔｈ）として設定する（Ｓ２３３）。
　一方、ノード位置がスライス位置以上の場合（Ｓ２３２でＮｏ）、符号化装置は、第２ビット長情報（ｓｌｉｃｅ＿ｂｂ＿ｗｉｄｔｈ＿ｂｉｔｓ）が０より大きいか否かを判定する（Ｓ２３４）。
　第２ビット長情報が０より大きい場合（Ｓ２３４でＹｅｓ）、符号化装置は、ｍｉｎ（スライス位置（Ａ）＋スライス幅（Ｂ）－ノード位置（ｎｏｄｅＰｏｓ）＋１、規定幅（Ｗ））をノード幅（ｎｏｄｅＷｉｄｔｈ）として設定する（Ｓ２３５）。
　一方、第２ビット長情報が０である場合（Ｓ２３４でＮｏ）、符号化装置は、ノード幅（ｎｏｄｅＷｉｄｔｈ）を変更しない（Ｓ２３６）。つまり、符号化装置は、ノード幅を規定幅（Ｗ）に設定する。
　また、第１ビット長情報が０である場合（Ｓ２３１でＮｏ）、符号化装置は、第２ビット長情報（ｓｌｉｃｅ＿ｂｂ＿ｗｉｄｔｈ＿ｂｉｔｓ）が０より大きいか否かを判定する（Ｓ２３７）。なお、第１ビット長情報が０である場合（Ｓ２３１でＮｏ）とは、スライス位置情報が伝送されない場合であり、スライスの開始端が原点に一致している場合である。
　第２ビット長情報が０より大きい場合（Ｓ２３７でＹｅｓ）、符号化装置は、ｍｉｎ（スライス幅（Ｂ）－ノード位置（ｎｏｄｅＰｏｓ）＋１、規定幅（Ｗ））をノード幅（ｎｏｄｅＷｉｄｔｈ）として設定する（Ｓ２３８）。
　一方、第２ビット長情報が０である場合（Ｓ２３７でＮｏ）、符号化装置は、ノード幅（ｎｏｄｅＷｉｄｔｈ）を変更しない（Ｓ２３６）。つまり、符号化装置は、ノード幅を規定幅（Ｗ）に設定する。
　［まとめ］
　以上のように、実施の形態に係る復号装置（三次元データ復号装置）は、図４０に示す処理を行う。復号装置は、複数の三次元点を復号する復号装置である。復号装置は、ビットストリームから、８分木構造を有し、第１スライスに含まれる複数のノードを取得し（Ｓ３０１）、ビットストリームから、複数のノードのうちの第１ノードの形状を導出するための情報を取得し（Ｓ３０２）、第１ノードを情報に従い復号し（Ｓ３０３）、第１ノードの形状は、複数のノードのうちの他のノードの規定形状と異なる。これによれば、規定形状とは異なる形状のノードを設定できる。よって、スライスの大きさ又は点群の分布状況に合わせて可変のノードを設定できる。よって、符号化効率を向上できる可能性がある。
　例えば、第１ノードの形状は直方体形状であり、立方体形状ではない。例えば、第１スライスの端は、複数のノードのうちのいずれかのノードの端と一致している。これによれば、ノード端とスライス端とが一致しない場合に、ノード端とスライス端とを一致させることができる。よって、当該ノード端に頂点が生成されないことを抑制できるので、スライス境界における空白領域の発生を抑制できる。よって、復号される点群の精度を向上できる。
　例えば、第１ノードの形状のサイズは、規定形状の規定サイズと異なる。例えば、第１ノードの形状の辺の長さは、規定形状の辺の規定長（例えば規定幅）と異なる。
　例えば、第１ノードの形状を導出するための情報は、第１ノードの形状のサイズ、又は、第１ノードの辺の両端の位置、を示す。これによれば、復号装置は、当該情報を用いて規定形状と異なる形状のノードを生成できる。
　例えば、第１ノードの形状を導出するための情報は、規定形状を第１ノードの形状に調整するための調整情報（例えばスライス幅情報又はスライス位置情報）を含む。これによれば、復号装置は、調整情報を用いて規定形状と異なる形状のノードを生成できる。また、位置の情報の絶対量を送る場合に比べて、情報量を小さくできる可能性がある。
　例えば、第１ノードの復号は、複数の三次元点が第１ノード内の平面又は曲面で近似される圧縮方式に従い実行される。例えば、圧縮方式は、Ｔｒｉａｎｇｌｅ－Ｓｏｕｐ圧縮方式である。
　例えば、平面又は曲面を第１ノード内に生成するために第１ノードの形状が決定される。これによれば、規定形状とは異なる形状のノードを設定することで、平面又は曲面を第１ノード内に生成できる。
　例えば、第１ノードの形状の辺はその上に頂点を持ち、平面または曲面は、頂点で辺と交差する。これによれば、規定形状とは異なる形状のノードを設定することで、平面又は曲面を第１ノード内に生成できる。例えば、複数の三次元点は、頂点の近傍に位置する第１三次元点を含む。
　例えば、第１ノードは、第１スライスに隣接する第２スライスと接して設けられる。これによれば、例えば、ノード端とスライス端とが一致しない場合に、当該ノード端に頂点が生成されないことを抑制できるので、スライス境界における空白領域の発生を抑制できる。例えば、スライス境界で規定形状のノードしか設けない場合、スライス境界がノードを区切る場合がある。その場合、第１スライスに隣接する第２スライス内の点群を使って第１ノードの符号化又は復号を行うことができないので、スライス境界付近における三次元点群の復元精度が悪化する可能性がある。そこで、この態様では、規定形状とは異なる形状のノードを設定することで、例えば、第１ノードの端を第１スライスの端と一致させることができる。これにより、スライス境界付近における三次元点群の復元精度の悪化を抑制できる。なお、この態様をトライソープ方式に適用すれば、エッジ頂点が適切に生成されないことを抑制できる。
　例えば、第１ノードの形状を導出するための情報はスライスごとに設けられ、第２スライスの情報は、８分木構造を有し、第２スライスに含まれる複数のノードのうちの第２ノードの形状を導出するために使用され、第２ノードの形状は規定形状と異なる。これによれば、スライス毎にノードの形状を設定できる。
　例えば、規定形状のサイズは２のべき乗で表され、第１ノードの形状のサイズは２のべき乗で表されるサイズとは異なる。
　例えば、第１ノードの形状は、第１方向に沿った第１の長さ、第２方向に沿った第２の長さ、および第３方向に沿った第３の長さによって定義され、第１方向、第２方向、および第３方向は互いに直交し、第１の長さ、第２の長さ及び第３の長さのうち第１の長さだけが第１ノード以外のノードの規定形状の長さと異なる、又は、第１の長さ、第２の長さ及び第３の長さのうち第１の長さ及び第２の長さだけが、それぞれ規定形状の長さと異なる。
　例えば、第１ノードは、第１方向、第２方向及び第３方向のうちの一つの方向において、複数のノードのうちで第１スライスの原点に最も近く、第１方向、第２方向、および第３方向は互いに直交する。これによれば、スライスの開始位置が原点と一致しない場合において、例えば、スライスの開始位置に合わせてノードの開始位置を調整できる。なお、原点とは、スライス、ノード、三次元点の位置、又は形状を規定するための基準となる位置である。
　例えば、複数のノードは、規定形状とは異なる形状を持つ第３ノードを含み、第３ノードは、複数のノードのうち、一つの方向において原点から最も遠い。これによれば、スライスの終了位置がノードの終了位置と一致しない場合において、例えば、スライスの終了位置に合わせてノードの終了位置を調整できる。
　例えば、第１スライスの開始位置が原点と一致しない場合、ビットストリームは第１ノードの形状を導出するための情報を含み、第１スライスの開始位置が原点と一致する場合、ビットストリームは第１ノードの形状を導出するための情報を含まない。これによれば、ノードの形状を調整するための処理の発生を低減できる。また、ノードの形状を導出するための情報の伝送を省略できる。よって、処理量の低減及びビットストリームのデータ量の低減を実現できる。なお、スライスの開始位置（開始端）とは、原点に近い側のスライスの端の位置であり、スライスの終了位置（終了端）とは、原点から遠い側のスライスの端の位置である。同様に、ノードの開始位置（開始端）とは、原点に近い側のノードの端の位置であり、ノードの終了位置（終了端）とは、原点から遠い側のノードの端の位置である。
　例えば、第１スライスの終了位置が第１ノードの終了端と一致しない場合、ビットストリームは第１ノードの形状を導出するための情報を含み、第１スライスの終了位置が第１ノードの終了端と一致する場合、ビットストリームは第１ノードの形状を導出するための情報を含まない。これによれば、ノードの形状を調整するための処理の発生を低減できる。また、ノードの形状を導出するための情報の伝送を省略できる。よって、処理量の低減及びビットストリームのデータ量の低減を実現できる。
　図４１は、復号装置１０のブロックである。例えば、復号装置１０は、プロセッサ１１と、メモリ１２とを備え、プロセッサ１１は、メモリ１２を用いて、上記処理を行う。
　また、実施の形態に係る符号化装置（三次元データ符号化装置）は、図４２に示す処理を行う。符号化装置は、複数の三次元点を符号化する符号化装置である。符号化装置は、８分木構造を有し、第１スライスに含まれる複数のノードを符号化することでビットストリームを生成し（Ｓ３１１）、複数のノードのうちの第１ノードの形状を導出するための情報をビットストリームに格納し（Ｓ３１２）、第１ノードの形状は、複数のノードのうちの他のノードの規定形状と異なる。これによれば、規定形状とは異なる形状のノードを設定できる。よって、スライスの大きさ又は点群の分布状況に合わせて可変のノードを設定できる。よって、符号化効率を向上できる可能性がある。また、符号化装置は、上記の復号装置と同様の処理を行ってもよい。
　図４３は、符号化装置２０のブロックである。例えば、符号化装置２０は、プロセッサ２１と、メモリ２２とを備え、プロセッサ２１は、メモリ２２を用いて、上記処理を行う。
　以上、本開示の実施の形態及び変形例に係る符号化装置（三次元データ符号化装置）及び復号装置（三次元データ復号装置）等について説明したが、本開示は、この実施の形態に限定されるものではない。
　また、上記実施の形態に係る符号化装置及び復号装置等に含まれる各処理部は典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部又は全てを含むように１チップ化されてもよい。
　また、集積回路化はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後にプログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ　Ｐｒｏｇｒａｍｍａｂｌｅ　Ｇａｔｅ　Ａｒｒａｙ）、又はＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用してもよい。
　また、上記各実施の形態において、各構成要素は、専用のハードウェアで構成されるか、各構成要素に適したソフトウェアプログラムを実行することによって実現されてもよい。各構成要素は、ＣＰＵまたはプロセッサなどのプログラム実行部が、ハードディスクまたは半導体メモリなどの記録媒体に記録されたソフトウェアプログラムを読み出して実行することによって実現されてもよい。
　また、本開示は、符号化装置（三次元データ符号化装置）及び復号装置（三次元データ復号装置）等により実行される符号化方法（三次元データ符号化方法）又は復号方法（三次元データ復号方法）等として実現されてもよい。
　また、本開示は、上記符号化方法又は復号方法をコンピュータ、プロセッサ又は装置に実行されるプログラムとして実現されてもよい。また、本開示は、上記符号化方法により生成されたビットストリームとして実現されてもよい。また、本開示は、当該プログラム又は当該ビットストリームが記録された記録媒体として実現されてもよい。例えば、本開示は、当該プログラム又は当該ビットストリームが記録されている非一時的なコンピュータ読み取り可能な記録媒体として実現されてもよい。
　また、ブロック図における機能ブロックの分割は一例であり、複数の機能ブロックを一つの機能ブロックとして実現したり、一つの機能ブロックを複数に分割したり、一部の機能を他の機能ブロックに移してもよい。また、類似する機能を有する複数の機能ブロックの機能を単一のハードウェア又はソフトウェアが並列又は時分割に処理してもよい。
　また、フローチャートにおける各ステップが実行される順序は、本開示を具体的に説明するために例示するためのものであり、上記以外の順序であってもよい。また、上記ステップの一部が、他のステップと同時（並列）に実行されてもよい。
　以上、一つまたは複数の態様に係る符号化装置及び復号装置等について、実施の形態に基づいて説明したが、本開示は、この実施の形態に限定されるものではない。本開示の趣旨を逸脱しない限り、当業者が思いつく各種変形を本実施の形態に施したものや、異なる実施の形態における構成要素を組み合わせて構築される形態も、一つまたは複数の態様の範囲内に含まれてもよい。
　本開示は、符号化装置及び復号装置に適用できる。
　１０　復号装置
　１１、２１　プロセッサ
　１２、２２　メモリ
　２０　符号化装置
　１０１　対象空間
　１０２、１３３　点群
　１０３、１１１、１３２　点
　１０４　リーフノード
　１１２　エッジ頂点
　１１３、１２２　範囲
　１２１　近似平面
　１２３　頂点情報
　１３１　三角形
　２０１　領域

Claims (20)

  1. 　複数の三次元点を復号する復号方法であって、
    　ビットストリームから、８分木構造を有し、第１スライスに含まれる複数のノードを取得し、
    　前記ビットストリームから、前記複数のノードのうちの第１ノードの形状を導出するための情報を取得し、
    　前記第１ノードを前記情報に従い復号し、
    　前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる
    　復号方法。
  2. 　前記形状は直方体形状であり、立方体形状ではない
    　請求項１記載の復号方法。
  3. 　前記第１スライスの端は、前記複数のノードのうちのいずれかのノードの端と一致している
    　請求項１記載の復号方法。
  4. 　前記情報は、前記形状のサイズ、又は、前記第１ノードの辺の両端の位置、を示す
    　請求項１記載の復号方法。
  5. 　前記情報は、前記規定形状を前記形状に調整するための調整情報を含む
    　請求項１記載の復号方法。
  6. 　前記復号は、前記複数の三次元点が前記第１ノード内の平面又は曲面で近似される圧縮方式に従い実行される
    　請求項１記載の復号方法。
  7. 　前記圧縮方式は、Ｔｒｉａｎｇｌｅ－Ｓｏｕｐ圧縮方式である
    　請求項６記載の復号方法。
  8. 　前記平面又は前記曲面を前記第１ノード内に生成するために前記形状が決定される
    　請求項６記載の復号方法。
  9. 　前記形状の辺はその上に頂点を持ち、
    　前記平面または前記曲面は、前記頂点で前記辺と交差する
    　請求項８記載の復号方法。
  10. 　前記第１ノードは、前記第１スライスに隣接する第２スライスと接して設けられる
    　請求項１記載の復号方法。
  11. 　前記情報はスライスごとに設けられ、
    　前記第２スライスの前記情報は、８分木構造を有し、前記第２スライスに含まれる複数のノードのうちの第２ノードの形状を導出するために使用され、
    　前記第２ノードの形状は前記規定形状と異なる
    　請求項１０記載の復号方法。
  12. 　前記規定形状のサイズは２のべき乗で表され、前記形状のサイズは２のべき乗で表されるサイズとは異なる
    　請求項１記載の復号方法。
  13. 　前記第１ノードの前記形状は、第１方向に沿った第１の長さ、第２方向に沿った第２の長さ、および第３方向に沿った第３の長さによって定義され、前記第１方向、前記第２方向、および前記第３方向は互いに直交し、
    　前記第１の長さ、前記第２の長さ及び前記第３の長さのうち前記第１の長さだけが前記第１ノード以外のノードの前記規定形状の長さと異なる、又は、前記第１の長さ、前記第２の長さ及び前記第３の長さのうち前記第１の長さ及び前記第２の長さだけが、それぞれ前記規定形状の長さと異なる
    　請求項１記載の復号方法。
  14. 　前記第１ノードは、第１方向、第２方向及び第３方向のうちの一つの方向において、前記複数のノードのうちで前記第１スライスの原点に最も近く、前記第１方向、前記第２方向、および前記第３方向は互いに直交する
    　請求項１記載の復号方法。
  15. 　前記複数のノードは、前記規定形状とは異なる形状を持つ第３ノードを含み、
    　前記第３ノードは、前記複数のノードのうち、前記一つの方向において前記原点から最も遠い
    　請求項１４記載の復号方法。
  16. 　前記第１スライスの開始位置が原点と一致しない場合、前記ビットストリームは前記情報を含み、
    　前記第１スライスの開始位置が原点と一致する場合、前記ビットストリームは前記情報を含まない、
    　請求項１記載の復号方法。
  17. 　前記第１スライスの終了位置が前記第１ノードの終了端と一致しない場合、前記ビットストリームは、前記情報を含み、
    　前記第１スライスの終了位置が前記第１ノードの終了端と一致する場合、前記ビットストリームは前記情報を含まない、
    　請求項１記載の復号方法。
  18. 　複数の三次元点を符号化する符号化方法であって、
    　８分木構造を有し、第１スライスに含まれる複数のノードを符号化することでビットストリームを生成し、
    　前記複数のノードのうちの第１ノードの形状を導出するための情報を前記ビットストリームに格納し、
    　前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる
    　符号化方法。
  19. 　複数の三次元点を復号する復号装置であって、
    　プロセッサと、
    　メモリと、を備え、
    　前記プロセッサは、前記メモリを用いて、
    　ビットストリームから、８分木構造を有し、第１スライスに含まれる複数のノードを取得し、
    　前記ビットストリームから、前記複数のノードのうちの第１ノードの形状を導出するための情報を取得し、
    　前記第１ノードを前記情報に従い復号し、
    　前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる
    　復号装置。
  20. 　複数の三次元点を符号化する符号化装置であって、
    　プロセッサと、
    　メモリと、を備え、
    　前記プロセッサは、前記メモリを用いて、
    　８分木構造を有し、第１スライスに含まれる複数のノードを符号化することでビットストリームを生成し、
    　前記複数のノードのうちの第１ノードの形状を導出するための情報を前記ビットストリームに格納し、
    　前記形状は、前記複数のノードのうちの他のノードの規定形状と異なる
    　符号化装置。
PCT/JP2023/025991 2022-08-26 2023-07-14 復号方法、符号化方法、復号装置及び符号化装置 Ceased WO2024042909A1 (ja)

Priority Applications (6)

Application Number Priority Date Filing Date Title
JP2024542643A JPWO2024042909A1 (ja) 2022-08-26 2023-07-14
CN202380060194.1A CN119731699A (zh) 2022-08-26 2023-07-14 解码方法、编码方法、解码装置及编码装置
KR1020257005085A KR20250056900A (ko) 2022-08-26 2023-07-14 복호 방법, 부호화 방법, 복호 장치 및 부호화 장치
EP23857025.3A EP4579597A4 (en) 2022-08-26 2023-07-14 DECODING METHOD, CODING METHOD, DECODING DEVICE AND CODING DEVICE
MX2025001645A MX2025001645A (es) 2022-08-26 2025-02-10 Metodo de decodificacion, metodo de codificacion, dispositivo de decodificacion y dispositivo de codificacion
US19/056,107 US20250191232A1 (en) 2022-08-26 2025-02-18 Decoding method, encoding method, decoding device, and encoding device

Applications Claiming Priority (6)

Application Number Priority Date Filing Date Title
US202263401309P 2022-08-26 2022-08-26
US63/401,309 2022-08-26
US202263426137P 2022-11-17 2022-11-17
US63/426,137 2022-11-17
US202263435635P 2022-12-28 2022-12-28
US63/435,635 2022-12-28

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US19/056,107 Continuation US20250191232A1 (en) 2022-08-26 2025-02-18 Decoding method, encoding method, decoding device, and encoding device

Publications (1)

Publication Number Publication Date
WO2024042909A1 true WO2024042909A1 (ja) 2024-02-29

Family

ID=90013068

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2023/025991 Ceased WO2024042909A1 (ja) 2022-08-26 2023-07-14 復号方法、符号化方法、復号装置及び符号化装置

Country Status (7)

Country Link
US (1) US20250191232A1 (ja)
EP (1) EP4579597A4 (ja)
JP (1) JPWO2024042909A1 (ja)
KR (1) KR20250056900A (ja)
CN (1) CN119731699A (ja)
MX (1) MX2025001645A (ja)
WO (1) WO2024042909A1 (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20240214600A1 (en) * 2022-12-22 2024-06-27 Comcast Cable Communications, Llc Motion Compensation based Neighborhood Configuration for TriSoup Centroid Information
WO2025216171A1 (ja) * 2024-04-11 2025-10-16 パナソニック インテレクチュアル プロパティ コーポレーション オブ アメリカ 符号化方法、復号方法、符号化装置及び復号装置

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2014020663A1 (ja) 2012-07-30 2014-02-06 三菱電機株式会社 地図表示装置
US20210049828A1 (en) * 2019-08-14 2021-02-18 Lg Electronics Inc. Apparatus for transmitting point cloud data, a method for transmitting point cloud data, an apparatus for receiving point cloud data and a method for receiving point cloud data
US20210321139A1 (en) * 2020-04-07 2021-10-14 Qualcomm Incorporated High-level syntax design for geometry-based point cloud compression
WO2021262559A1 (en) * 2020-06-23 2021-12-30 Sony Group Corporation Trisoup node size per slice
JP2022521680A (ja) * 2019-06-26 2022-04-12 テンセント・アメリカ・エルエルシー ポイントクラウドのジオメトリ復号及び符号化のための暗示的な四分木又は二分木ジオメトリ分割

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11172224B2 (en) * 2019-09-03 2021-11-09 Tencent America LLC Techniques and apparatus for generalized Trisoup geometry coding
CN114981842B (zh) * 2020-01-09 2025-08-19 苹果公司 点云的树内几何量化
US11514612B2 (en) * 2020-04-02 2022-11-29 Tencent America LLC Method and apparatus for point cloud coding

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2014020663A1 (ja) 2012-07-30 2014-02-06 三菱電機株式会社 地図表示装置
JP2022521680A (ja) * 2019-06-26 2022-04-12 テンセント・アメリカ・エルエルシー ポイントクラウドのジオメトリ復号及び符号化のための暗示的な四分木又は二分木ジオメトリ分割
US20210049828A1 (en) * 2019-08-14 2021-02-18 Lg Electronics Inc. Apparatus for transmitting point cloud data, a method for transmitting point cloud data, an apparatus for receiving point cloud data and a method for receiving point cloud data
US20210321139A1 (en) * 2020-04-07 2021-10-14 Qualcomm Incorporated High-level syntax design for geometry-based point cloud compression
WO2021262559A1 (en) * 2020-06-23 2021-12-30 Sony Group Corporation Trisoup node size per slice

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP4579597A4

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20240214600A1 (en) * 2022-12-22 2024-06-27 Comcast Cable Communications, Llc Motion Compensation based Neighborhood Configuration for TriSoup Centroid Information
WO2025216171A1 (ja) * 2024-04-11 2025-10-16 パナソニック インテレクチュアル プロパティ コーポレーション オブ アメリカ 符号化方法、復号方法、符号化装置及び復号装置

Also Published As

Publication number Publication date
KR20250056900A (ko) 2025-04-28
US20250191232A1 (en) 2025-06-12
MX2025001645A (es) 2025-03-07
CN119731699A (zh) 2025-03-28
EP4579597A4 (en) 2025-12-17
JPWO2024042909A1 (ja) 2024-02-29
EP4579597A1 (en) 2025-07-02

Similar Documents

Publication Publication Date Title
CN113615181B (zh) 用于点云编解码的方法、装置
WO2024042909A1 (ja) 復号方法、符号化方法、復号装置及び符号化装置
US12165370B2 (en) Context determination for planar mode in octree-based point cloud coding
JP7678138B2 (ja) ポイントクラウドデータ送信装置、ポイントクラウドデータ送信方法、ポイントクラウドデータ受信装置及びポイントクラウドデータ受信方法
BR112021002464A2 (pt) método de codificação de dados tridimensionais, método de decodificação de dados tridimensionais, dispositivo de codificação de dados tridimensionais, e dispositivo de decodificação de dados tridimensionais
JP7723199B2 (ja) 符号化装置、復号装置、符号化方法及び復号方法
US20250371744A1 (en) Encoding method, decoding method, encoding device, and decoding device
CN117223287A (zh) 点云处理方法及装置、编码器、解码器、可读存储介质
CN119366187A (zh) 编解码方法、码流、编码器、解码器以及存储介质
CN118613832A (zh) 三维数据编码方法、三维数据解码方法、三维数据编码装置及三维数据解码装置
KR20250076567A (ko) 포인트 클라우드 데이터 송신 장치, 포인트 클라우드 데이터 송신 방법, 포인트 클라우드 데이터 수신 장치 및 포인트 클라우드 데이터 수신 방법
CN120958485A (zh) 对点云的顶点信息进行写码
US20250024041A1 (en) Method for index determination, decoder, encoder, and bitstream
WO2025205261A1 (ja) 三次元データ符号化方法、三次元データ復号方法、三次元データ符号化装置及び三次元データ復号装置
WO2021108970A1 (zh) 点云处理方法、编码器、解码器及存储介质
KR20250123770A (ko) 정점 정보 코딩을 위한 향상된 에지 이웃
Duch et al. Depth map compression via 3D region-based representation
US20250363675A1 (en) Decoding method and decoding device
WO2024053454A1 (ja) 復号方法、符号化方法、復号装置及び符号化装置
CN121925683A (zh) 解码方法、编码方法及解码装置
US20260024235A1 (en) Decoding method, encoding method, decoding device, and encoding device
RU2846451C2 (ru) Способ и устройство зашифровки геометрической информации о геометрии облака точек в битовый поток и способ и устройство дешифровки геометрической информации о геометрии облака точек из битового потока
US20250330599A1 (en) Method and apparatus for dynamic mesh base geometry coding signaling for lifting parameters
US20260019593A1 (en) Point cloud data transmission device, point cloud data transmission method, point cloud data reception device, and point cloud data reception method
CA3288587A1 (en) Decoding method, encoding method, decoding device, and encoding device

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 23857025

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2024542643

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: MX/A/2025/001645

Country of ref document: MX

WWE Wipo information: entry into national phase

Ref document number: 202547013470

Country of ref document: IN

Ref document number: 202380060194.1

Country of ref document: CN

REG Reference to national code

Ref country code: BR

Ref legal event code: B01A

Ref document number: 112025002577

Country of ref document: BR

WWP Wipo information: published in national office

Ref document number: 202547013470

Country of ref document: IN

WWP Wipo information: published in national office

Ref document number: MX/A/2025/001645

Country of ref document: MX

WWE Wipo information: entry into national phase

Ref document number: 2023857025

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: DE

WWP Wipo information: published in national office

Ref document number: 202380060194.1

Country of ref document: CN

ENP Entry into the national phase

Ref document number: 2023857025

Country of ref document: EP

Effective date: 20250326

WWP Wipo information: published in national office

Ref document number: 1020257005085

Country of ref document: KR

WWP Wipo information: published in national office

Ref document number: 2023857025

Country of ref document: EP

ENP Entry into the national phase

Ref document number: 112025002577

Country of ref document: BR

Kind code of ref document: A2

Effective date: 20250210