JP7573555B2 - Point group decoding device, point group decoding method and program - Google Patents

Description

The present invention relates to a point cloud decoding device, a point cloud decoding method, and a program.

Non-Patent Document 1 discloses a technique for reconstructing a decoded point cloud using a method called Trisoup for one predetermined type of node size.

G-PCC Future Enhancement, ISO/IEC JTC1/SC29/WG11 N19328

However, the method in Non-Patent Document 1 has only one type of node size (fixed node size), and there is room for improvement in terms of coding efficiency.

The present invention has been made in consideration of the above-mentioned problems, and aims to provide a point cloud decoding device, a point cloud decoding method, and a program that can improve the encoding efficiency without compromising the subjective image quality of the decoded point cloud.

The first feature of the present invention is a point cloud decoding device that includes an approximate surface synthesis unit configured to perform vertex decoding processing for each of a plurality of node sizes and to perform point reconstruction processing based on the vertices for a single node size.

The second feature of the present invention is a point cloud decoding method that includes a step of performing a vertex decoding process for each of a plurality of node sizes, and a step of performing a point reconstruction process based on the vertices for a single node size.

The third feature of the present invention is a program for causing a computer to function as a point cloud decoding device, the point cloud decoding device comprising an approximate surface synthesis unit configured to execute vertex decoding processing for each of a plurality of node sizes, and execute point reconstruction processing based on the vertices for a single node size.

The present invention provides a point cloud decoding device, a point cloud decoding method, and a program that can improve the encoding efficiency without compromising the subjective image quality of the decoded point cloud.

FIG. 1 is a diagram illustrating an example of the configuration of a point cloud processing system 10 according to an embodiment. FIG. 2 is a diagram illustrating an example of functional blocks of a point group decoding device 200 according to an embodiment. FIG. 3 is a diagram showing an example of the configuration of encoded data (bit stream) received by the geometric information decoding unit 2010 of the point cloud decoding device 200 according to an embodiment. FIG. 4 is a diagram showing an example of the syntax configuration of GPS2011. FIG. 5 is a diagram showing an example of the syntax configuration of GSH2012. FIG. 6 is a flowchart illustrating an example of a process in the tree synthesis unit 2020 of the point group decoding device 200 according to an embodiment. FIG. 7 is a flowchart showing an example of a decoding process of an occupancy code for each node by the tree synthesis unit 2020 of the point group decoding device 200 according to an embodiment. FIG. 8 is a flowchart showing an example of a process of selecting one of four types of contexts (no pred/pred0/pred1/predL) using inter prediction by the tree synthesis unit 2020 of the point group decoding device 200 according to an embodiment. FIG. 9 is a flowchart showing an example of processing by the approximate surface synthesis unit 2030 of the point cloud decoding device 200 according to an embodiment. FIG. 10 is a flowchart showing an example of a decoding process of the vertex positions of Trisoup by the approximate surface synthesis unit 2030 of the point cloud decoding device 200 according to an embodiment. FIG. 11 is a diagram for explaining an example of the process in step S1006 in FIG. FIG. 12 is a diagram for explaining an example of the process of step S1006 in FIG. FIG. 13 is a diagram for explaining another example of the process in step S1006 in FIG. FIG. 14 is a diagram for explaining another example of the process in step S1006 in FIG. FIG. 15 is a diagram for explaining an example of the process of step S902 in FIG. FIG. 16 is a diagram for explaining an example of the process of step S902 in FIG. FIG. 17 is a diagram for explaining another example of the process in step S902 in FIG. FIG. 18 is a diagram for explaining another example of the process in step S902 in FIG. FIG. 19 is a diagram for explaining another example of the process in step S902 in FIG. FIG. 20 is a diagram for explaining another example of the process in step S902 in FIG. FIG. 21 is a diagram illustrating an example of functional blocks of a point cloud encoding device 100 according to an embodiment. FIG. 22 is a diagram for explaining an example of the process of step S902 in FIG.

The following describes embodiments of the present invention with reference to the drawings. Note that the components in the following embodiments can be replaced with existing components as appropriate, and various variations, including combinations with other existing components, are possible. Therefore, the description of the following embodiments does not limit the content of the invention described in the claims.

First Embodiment
A point cloud processing system 10 according to a first embodiment of the present invention will be described below with reference to Figures 1 to 22. Figure 1 is a diagram showing a point cloud processing system 10 according to the present embodiment.

As shown in FIG. 1, the point cloud processing system 10 has a point cloud encoding device 100 and a point cloud decoding device 200.

The point cloud encoding device 100 is configured to generate encoded data (bit stream) by encoding an input point cloud signal. The point cloud decoding device 200 is configured to generate an output point cloud signal by decoding the bit stream.

The input point cloud signal and the output point cloud signal are composed of position information and attribute information of each point in the point cloud. The attribute information is, for example, color information and reflectance of each point.

Here, such a bit stream may be transmitted from the point cloud encoding device 100 to the point cloud decoding device 200 via a transmission path. Also, the bit stream may be stored in a storage medium and then provided from the point cloud encoding device 100 to the point cloud decoding device 200.

(Point Cloud Decoding Device 200)
Hereinafter, the point group decoding device 200 according to this embodiment will be described with reference to Fig. 2. Fig. 2 is a diagram showing an example of functional blocks of the point group decoding device 200 according to this embodiment.

As shown in FIG. 2, the point cloud decoding device 200 includes a geometric information decoding unit 2010, a tree synthesis unit 2020, an approximate surface synthesis unit 2030, a geometric information reconstruction unit 2040, an inverse coordinate transformation unit 2050, an attribute information decoding unit 2060, an inverse quantization unit 2070, a RAHT unit 2080, an LoD calculation unit 2090, an inverse lifting unit 2100, an inverse color transformation unit 2110, and a frame buffer 2120.

The geometric information decoding unit 2010 is configured to receive as input a bit stream related to geometric information (geometric information bit stream) from the bit streams output from the point cloud encoding device 100, and to decode the syntax.

The decoding process is, for example, a context-adaptive binary arithmetic decoding process. Here, for example, the syntax includes control data (flags and parameters) for controlling the decoding process of the position information.

The tree synthesis unit 2020 is configured to receive as input the control data decoded by the geometric information decoding unit 2010 and an occurrence code indicating at which node in the tree (described later) the point group exists, and generate tree information indicating in which area in the decoding target space the point exists.

The decoding process of the occasion code may be configured to be performed within the tree synthesis unit 2020.

This process divides the space to be decoded into rectangular parallelepipeds, refers to the occupancy code to determine whether a point exists in each rectangular parallelepiped, divides the rectangular parallelepiped in which the point exists into multiple rectangular parallelepipeds, and then refers to the occupancy code. This process is repeated recursively to generate tree information.

Here, when decoding such an occasion code, inter prediction, which will be described later, may be used.

In this embodiment, a method called "Octree" can be used, which recursively performs octree division on the above-mentioned rectangular parallelepiped, always treating it as a cube, and a method called "QtBt" can be used, which performs quadtree division and binary tree division in addition to octree division. Whether or not to use "QtBt" is transmitted as control data from the point cloud encoding device 100.

Alternatively, when the control data specifies that predictive coding is to be used, the tree synthesis unit 2020 is configured to decode the coordinates of each point based on an arbitrary tree configuration determined by the point cloud encoding device 100.

The approximate surface synthesis unit 2030 is configured to generate approximate surface information using the tree information generated by the tree synthesis unit 2020, and to decode the point cloud based on the approximate surface information.

When decoding three-dimensional point cloud data of an object, for example, if the points are densely distributed on the object's surface, approximate surface information is used to represent the area in which the points exist by approximating the area using a small plane, rather than decoding each point individually.

Specifically, the approximate surface synthesis unit 2030 can generate approximate surface information and decode the point cloud using, for example, a method called "Trisoup." A specific processing example of "Trisoup" will be described later. Also, when decoding a sparse point cloud acquired by Lidar or the like, this processing can be omitted.

The geometric information reconstruction unit 2040 is configured to reconstruct the geometric information (position information in the coordinate system assumed by the decoding process) of each point of the point cloud data to be decoded based on the tree information generated by the tree synthesis unit 2020 and the approximate surface information generated by the approximate surface synthesis unit 2030.

The inverse coordinate transformation unit 2050 is configured to receive the geometric information reconstructed by the geometric information reconstruction unit 2040 as input, transform it from the coordinate system assumed by the decoding process to the coordinate system of the output point cloud signal, and output position information.

The frame buffer 2120 is configured to receive the geometric information reconstructed by the geometric information reconstruction unit 2040 as an input and store it as a reference frame. The stored reference frame is read out from the frame buffer 2120 and used as the reference frame when the tree synthesis unit 2020 performs inter-prediction of temporally different frames.

Here, which reference frame to use for each frame may be determined based on, for example, control data transmitted as a bit stream from the point cloud encoding device 100.

The attribute information decoding unit 2060 is configured to receive as input a bit stream relating to attribute information (attribute information bit stream) from the bit streams output from the point cloud encoding device 100, and to decode the syntax.

The decoding process is, for example, a context-adaptive binary arithmetic decoding process. Here, for example, the syntax includes control data (flags and parameters) for controlling the decoding process of the attribute information.

The attribute information decoding unit 2060 is also configured to decode the quantized residual information from the decoded syntax.

The inverse quantization unit 2070 is configured to perform an inverse quantization process based on the quantized residual information decoded by the attribute information decoding unit 2060 and the quantization parameter, which is one of the control data decoded by the attribute information decoding unit 2060, to generate inverse quantized residual information.

The dequantized residual information is output to either the RAHT unit 2080 or the LoD calculation unit 2090 depending on the characteristics of the point group to be decoded. The control data decoded by the attribute information decoding unit 2060 specifies which unit the information is output to.

The RAHT unit 2080 is configured to receive the inverse quantized residual information generated by the inverse quantization unit 2070 and the geometric information generated by the geometric information reconstruction unit 2040 as input, and to decode the attribute information of each point using a type of Haar transform (inverse Haar transform in the decoding process) called RAHT (Region Adaptive Hierarchical Transform). As a specific example of the RAHT process, the method described in Document 1 ([PCC] An exploratory model for inter geometry-based PCC, ISO/IEC JTC1/SC29/WG11 m44754) can be used.

The LoD calculation unit 2090 is configured to receive the geometric information generated by the geometric information reconstruction unit 2040 as input and generate the LoD (Level of Detail).

LoD is information for defining a reference relationship (a referencing point and a referenced point) to realize predictive coding, such as predicting attribute information of a certain point from attribute information of another point and encoding or decoding the prediction residual.

In other words, LoD is information that defines a hierarchical structure in which each point contained in the geometric information is classified into multiple levels, and the attributes of points belonging to lower levels are encoded or decoded using attribute information of points belonging to higher levels.

As a specific method for determining LoD, for example, the method described in the above-mentioned literature 1 may be used.

The inverse lifting unit 2100 is configured to decode attribute information of each point based on the hierarchical structure defined by the LoD, using the LoD generated by the LoD calculation unit 2090 and the inverse quantized residual information generated by the inverse quantization unit 2070. As a specific example of the inverse lifting process, the method described in the above-mentioned literature 1 can be used.

The inverse color conversion unit 2110 is configured to perform inverse color conversion processing on the attribute information output from the RAHT unit 2080 or the inverse lifting unit 2100 when the attribute information to be decoded is color information and color conversion has been performed on the point cloud encoding device 100 side. Whether or not such inverse color conversion processing is performed is determined by the control data decoded by the attribute information decoding unit 2060.

The point cloud decoding device 200 is configured to decode and output attribute information for each point in the point cloud through the above processing.

(Geometric information decoding unit 2010)
The control data decoded by the geometric information decoding unit 2010 will be described below with reference to FIGS.

Figure 3 shows an example of the structure of the encoded data (bit stream) received by the geometric information decoding unit 2010.

First, the bit stream may include a GPS2011. A GPS2011 is also called a geometry parameter set, and is a collection of control data related to decoding of geometric information. A specific example will be described later. Each GPS2011 includes at least GPS id information for identifying each GPS2011 when multiple GPS2011 exist.

Secondly, the bit stream may include GSH2012A/2012B. GSH2012A/2012B is also called a geometry slice header or geometry data unit header, and is a collection of control data corresponding to a slice, which will be described later. In the following description, the term "slice" will be used, but slice can also be read as data unit. Specific examples will be described later. GSH2012A/2012B includes at least GPS id information for specifying the GPS2011 corresponding to each GSH2012A/2012B.

Thirdly, the bit stream may include slice data 2013A/2013B following GSH 2012A/2012B. Slice data 2013A/2013B includes data that encodes geometric information. An example of slice data 2013A/2013B is an occasion code, which will be described later.

As described above, the bit stream is structured so that each slice data 2013A/2013B corresponds to one GSH 2012A/2012B and one GPS 2011.

As described above, the GPS ID information is used to specify which GPS 2011 to refer to in GSH 2012A/2012B, so a common GPS 2011 can be used for multiple slice data 2013A/2013B.

In other words, GPS2011 does not necessarily need to be transmitted for each slice. For example, as shown in FIG. 3, the bit stream can be configured so that GPS2011 is not encoded immediately before GSH2012B and slice data 2013B.

Note that the configuration in FIG. 3 is merely an example. As long as GSH 2012A/2012B and GPS 2011 correspond to each slice data 2013A/2013B, elements other than those described above may be added as components of the bit stream.

For example, as shown in FIG. 3, the bitstream may include a sequence parameter set (SPS) 2001. Similarly, when transmitted, the bitstream may be shaped into a configuration different from that shown in FIG. 3. Furthermore, the bitstream may be combined with a bitstream decoded by an attribute information decoding unit 2060 (described later) and transmitted as a single bitstream.

Figure 4 is an example of the syntax configuration of GPS2011.

Note that the syntax names explained below are merely examples. If the syntax functions explained below are similar, the syntax names may be different.

GPS2011 may include GPS ID information (gsps_geom_parameter_set_id) for identifying each GPS2011.

The Descriptor column in Figure 4 indicates how each syntax is coded. ue(v) indicates an unsigned zeroth-order exponential Golomb code, and u(1) indicates a 1-bit flag.

GPS2011 may include a flag (interprediction_enabled_flag) that controls whether or not inter prediction is performed in the tree synthesis unit 2020.

For example, it may be defined that when the value of interprediction_enabled_flag is "0", inter prediction is not performed, and when the value of interprediction_enabled_flag is "1", inter prediction is performed.

Note that interpretation_enabled_flag may be included in SPS2001 instead of GPS2011.

GPS2011 may include a flag (trisoup_enabled_flag) that controls whether or not Trisoup is used in the approximate surface synthesis unit 2030.

For example, it may be defined that Trisoup is not used when the value of trisoup_enabled_flag is "0", and that Trisoup is used when the value of trisoup_enabled_flag is "1".

The geometric information decoding unit 2020 may be configured to additionally decode the following syntax when Trisoup is used, i.e., when the value of trisoup_enabled_flag is "1".

Note that trisoup_enabled_flag may be included in SPS2001 instead of GPS2011.

GPS2011 may include a flag (trisoup_multilevel_enabled_flag, first flag) that controls whether or not trisoup is allowed at multiple levels.

For example, when the value of trisoup_multilevel_enabled_flag is "0", multi-level trisoup is not allowed, i.e., trisoup is performed at a single level, and when the value of trisoup_multilevel_enabled_flag is "1", multi-level trisoup is allowed.

If this syntax is not included in GPS2011, the value of this syntax may be considered to be the value when performing a trisoup at a single level, i.e., "0".

Note that trisoup_multilevel_enabled_flag may be defined to be included in SPS2001 instead of GPS2011. In this case, if trisoup_multilevel_enabled_flag is not included in SPS2001, the value of the syntax may be considered to be the value for performing trisoup at a single level, i.e., "0".

Figure 5 shows an example of the syntax configuration of GSH2012. As mentioned above, GSH is also called GDUH (Geometry Data Unit Header).

The geometric information decoding unit 2020 may be configured to additionally decode the following syntax when Trisoup at multiple levels is permitted, i.e., when the value of trisoup_multilevel_enabled_flag is "1".

GSH2012 may include syntax (log2_trisoup_max_node_size_minus2) to specify the maximum Trisoup node size when multi-level Trisoup is allowed.

The syntax may be expressed as a value obtained by converting the actual maximum Trisoup node size to a logarithm with base 2. Furthermore, the syntax may be expressed as a value obtained by subtracting 2 from the logarithm with base 2, for the actual maximum Trisoup node size.

GSH2012 may include syntax (log2_trisoup_min_node_size_minus2) to specify a minimum Trisoup node size when multi-level Trisoup is allowed.

The syntax may be expressed as a value obtained by converting the actual minimum Trisoup node size to a logarithm with base 2. Furthermore, the syntax may be expressed as a value obtained by subtracting 2 from the logarithm with base 2 for the actual minimum Trisoup node size.

The value of this syntax may also be constrained to be greater than or equal to 0 and less than or equal to log2_trisoup_max_node_size_minus2.

In this case, trisoup_depth may be defined as trisoup_depth = log2_trisoup_max_node_size_minus2 - log2_trisoup_min_node_size_minus2 + 1, as shown in Figure 5.

The geometric information decoding unit 2020 may be configured to additionally decode the following syntax when multi-level Trisoup is not permitted, i.e., when the value of trisoup_multilevel_enabled_flag is "0".

GSH2012 may include syntax (log2_trisoup_node_size_minus2) to specify the Trisoup node size when multi-level Trisoup is not allowed and when Trisoup is used.

The syntax may be expressed as a value obtained by converting the actual Trisoup node size to a logarithm with base 2. Furthermore, the syntax may be expressed as a value obtained by subtracting 2 from the logarithm with base 2 for the actual Trisoup node size.

In this case, trisoup_depth may be defined as trisoup_depth = 1, as shown in Figure 5.

When using Trisoup, GSH2012 may include a syntax (trisoup_sampling_value_minus1) that controls the sampling interval of the decoding point. The specific definition of the syntax may be the same as that described in the above-mentioned literature 1, for example.

When GSH2012 uses Trisoup and allows Trisoup at multiple levels, it may include a flag (unique_segments_exist_flag[i]) for each hierarchical level i (i = 0, ..., trisoup_depth-1) indicating whether a unique segment exists in the target hierarchical level. For example, if the value of unique_segments_exist_flag[i] is "1", this means that at least one unique segment exists in hierarchical level i. Also, if the value of unique_segments_exist_flag[i] is "0", this means that no unique segments exist in hierarchical level i.

For each hierarchical layer i (i = 0, ..., trisoup_depth-1), if a unique segment exists in the target hierarchical layer, i.e., if the value of unique_segments_exist_flag[i] is "1", GSH2012 may additionally include syntax (num_unique_segments_bits_minus1[i]) indicating the number of bits of the syntax indicating the number of unique segments in the target hierarchical layer and syntax (num_unique_segments_minus1[i]) indicating the number of unique segments in the target hierarchical layer.

Here, for both num_unique_segments_bits_minus1[i] and num_unique_segments_minus1[i], the original value minus "1" may be encoded as the syntax value.

(Tree synthesis unit 2020)
The processing of the tree merging unit 2020 will be described below with reference to Fig. 6 to Fig. 8. Fig. 6 is a flowchart showing an example of the processing in the tree merging unit 2020. Note that the following describes an example in which trees are merged using "Octree".

In step S601, the tree synthesis unit 2020 checks whether processing for all depths has been completed. Note that the depth number may be included as control data in the bit stream transmitted from the point cloud encoding device 100 to the point cloud decoding device 200.

The tree synthesis unit 2020 calculates the node size of the target depth. In the case of "Octree", the node size of the first depth may be defined as "2 to the power of the depth number". In other words, if the depth number is N, the node size of the first depth may be defined as 2 to the power of N.

In addition, the node size at the second and subsequent depths may be defined by decrementing the number N by one. That is, the node size at the second depth may be defined as "2 to the power of (N-1)", the node size at the third depth may be defined as "2 to the power of (N-2)", and so on.

Alternatively, because node sizes are always defined as powers of 2, you can simply think of the exponent part (N, N-1, N-2, etc.) as the node size. In the following explanation, node size refers to the exponent part.

If processing of all depths has been completed, the tree synthesis unit 2020 proceeds to step S609; if processing of all depths has not been completed, the tree synthesis unit 2020 proceeds to step S602.

In other words, when the target depth is the nth depth, if (N-n)=0, the tree synthesis unit 2020 proceeds to step S609, and if (N-n)>0, the tree synthesis unit 2020 proceeds to step S602.

Here, when the flag (trisoup_enabled_flag) that controls whether or not to use Trisoup indicates that Trisoup is to be used, that is, when the value of trisoup_enabled_flag is "1", the tree synthesis unit 2020 may change the number of Depths to be processed based on the value of the syntax (log2_trisoup_min_node_size_minus2) that specifies the minimum value of the Trisoup node size or the syntax (log2_trisoup_node_size_minus2) that specifies the Trisoup node size. In such a case, for example, it may be defined as follows.

Processing Depth Number=Total Depth Number−(Minimum) Trisoup Node Size Here, the minimum Trisoup node size can be defined as, for example, (log2_trisoup_min_node_size_minus2+2). Similarly, the Trisoup node size can be defined as (log2_trisoup_node_size_minus2+2).

In this case, if processing for all processing depth numbers is completed, the tree synthesis unit 2020 proceeds to step S609, otherwise, the tree synthesis unit 2020 proceeds to step S602.

In other words, if (processing depth number - n) = 0, the tree synthesis unit 2020 proceeds to step S609, and if (processing depth number - n) > 0, the tree synthesis unit 2020 proceeds to step S602.

The tree synthesis unit 2020 may also determine that Trisoup is applied to all nodes having the node size (N-processing depth number) when proceeding to step S609.

In step S602, the tree synthesis unit 2020 determines whether or not it is necessary to decode the Trisoup_applied_flag described below at the target depth.

For example, if "Trisoups at multiple levels are permitted (the value of trisoup_multilevel_enabled_flag is "1")" and "the node size (N-n) of the target depth is equal to or smaller than the maximum trisoup node size," the tree synthesis unit 2020 may determine that "decoding of trisoup_applied_flag is necessary."

In addition, if the above conditions are not met, the tree synthesis unit 2020 may determine that "decoding of Trisoup_applied_flag is not necessary."

Here, the maximum Trisoup node size can be defined as, for example, (log2_trisoup_max_node_size_minus3+2).

Once the above-mentioned determination is completed, the tree synthesis unit 2020 proceeds to step S703.

In step S603, the tree synthesis unit 2020 determines whether processing of all nodes included in the target Depth has been completed.

If it is determined that processing of all nodes at the target Depth has been completed, the tree synthesis unit 2020 proceeds to step S601 and processes the next Depth.

On the other hand, if processing of all nodes at the target Depth has not been completed, the tree synthesis unit 2020 proceeds to step S604.

In step S604, the tree synthesis unit 2020 checks whether or not it is necessary to decode the Trisoup_applied_flag determined in step S602.

If it is determined that decoding of Trisoup_applied_flag is necessary, the tree synthesis unit 2020 proceeds to step S605, and if it is determined that decoding of Trisoup_applied_flag is not necessary, the tree synthesis unit 2020 proceeds to step S608.

In step S605, the tree synthesis unit 2020 decodes Trisoup_applied_flag.

Trisoup_applied_flag is a 1-bit flag (second flag) that indicates whether Trisoup is applied to the target node. For example, it may be defined that Trisoup is applied to the target node when the value of this flag is "1", and that Trisoup is not applied to the target node when the value of this flag is "0".

After the tree synthesis unit 2020 decodes Trisoup_applied_flag, it proceeds to step S606.

In step S606, the tree synthesis unit 2020 checks the value of Trisoup_applied_flag decoded in step S605.

If Trisoup is to be applied to the target node, i.e., if the value of Trisoup_applied_flag is "1", the tree synthesis unit 2020 proceeds to step S607.

If Trisoup is not applied to the target node, i.e., if the value of Trisoup_applied_flag is "0", the tree synthesis unit 2020 proceeds to step S608.

In step S607, the tree synthesis unit 2020 stores the target node as a node to which Trisoup is applied, i.e., as a Trisoup node. No further node splitting by "Octree" is applied to the target node. The tree synthesis unit 2020 then proceeds to step S603 and moves on to processing the next node.

In step S608, the tree synthesis unit 2020 decodes information called the occupancy code.

In the case of "Octree", the occupancy code is information that indicates whether the point to be decoded is included in each of the child nodes when the target node is divided in half in each of the x, y, and z axis directions and divided into eight nodes (called child nodes).

For example, the occupancy code may assign one bit of information to each child node, and if the one bit of information is "1", it may be defined that the point to be decoded is included in the child node, and if the one bit of information is "0", it may be defined that the point to be decoded is not included in the child node.

When decoding such an occurrence code, the tree synthesis unit 2020 may estimate in advance the probability that the point to be decoded exists in each child node, and entropy decode the bits corresponding to each child node based on that probability.

Similarly, in the point cloud coding device 100, entropy coding may be performed. Furthermore, inter prediction may be used to estimate such probability. As a specific method of inter prediction, for example, the method described in the above-mentioned literature 1 may be applied. Furthermore, an upsampled point cloud may be used as a reference point cloud when performing inter prediction.

A specific example of the decoding process of an occurrence code when inter prediction is used will be described using Figures 7 and 8.

Figure 7 is a flowchart showing a specific example of the process of decoding the occupancy code for each node. In other words, Figure 7 is a flowchart showing a specific example of the process of step S608 in Figure 6.

As shown in FIG. 7, in step S701, the tree synthesis unit 2020 selects a context. The context corresponds to a probability distribution to be used in entropy decoding during subsequent occupancy information decoding.

Figure 8 is an example of a flowchart for selecting one of four types of contexts (no pred/pred0/pred1/predL) using inter prediction.

An example of context selection will be described below with reference to FIG. 8. Note that, although FIG. 8 describes an example in which there are four types of context, the number of types of context does not have to be four.

As shown in FIG. 8, in step S801, the tree synthesis unit 2020 determines the accuracy of inter prediction.

The accuracy of inter prediction can be determined, for example, by the presence or absence of the selected context and actual points for the child nodes (eight child nodes in the case of Octree) of the parent node of the target node.

For example, for a child node that selects the context of pred0, if a point does not actually exist, it is considered a correct answer, and if a point actually exists, it is considered an incorrect answer. On the other hand, for a child node that selects pred1 or predL, if a point actually exists, it is considered a correct answer, and if a point does not actually exist, it is considered an incorrect answer.

Here, when the number of child nodes belonging to a parent node that are correct is greater than a predetermined threshold, the accuracy of inter prediction can be determined to be "good." On the other hand, when the number of child nodes belonging to a parent node that are correct is equal to or less than a predetermined threshold, the accuracy of inter prediction can be determined to be "poor."

If the accuracy of inter prediction is determined to be "good", the tree synthesis unit 2020 proceeds to step S802. If the accuracy of inter prediction is determined to be "poor", the tree synthesis unit 2020 proceeds to step S805, sets the context for all child nodes belonging to the target node to "no pred", and ends the process.

In step S802, the tree synthesis unit 2020 checks whether at least one reference point exists in the same area as the target node in the motion-compensated reference frame.

If there is at least one reference point in the area in the same position as the target node, the tree merging unit 2020 proceeds to step S803. On the other hand, if there is no reference point in the area in the same position as the target node, the tree merging unit 2020 proceeds to step S805, sets the context for all child nodes belonging to the target node to "no pred", and ends the process.

From step S803 onwards, the tree synthesis unit 2020 performs a determination for each child node belonging to the target node.

In step S803, the tree synthesis unit 2020 checks whether at least one reference point exists in the area in the motion-compensated reference frame that is in the same position as the target child node.

If there is at least one reference point in the area at the same position as the target child node, the tree merging unit 2020 proceeds to step S804. On the other hand, if there is no reference point in the area at the same position as the target child node, the tree merging unit 2020 proceeds to step S806 and sets the context of the target child node to "pred0".

If context selection has not been completed for all child nodes of the target node, the tree synthesis unit 2020 returns to step S803 and performs the same process for the next child node.

When context selection has been completed for all child nodes of the target node, the tree synthesis unit 2020 terminates the process.

In step S804, the tree synthesis unit 2020 checks whether there are a number of reference points equal to or greater than a predetermined threshold in the area in the motion-compensated reference frame that is in the same position as the target child node.

If there are a number of reference points equal to or greater than a predetermined threshold in the area at the same position as the target child node, the tree synthesis unit 2020 proceeds to step S808 and sets the context of the target child node to "predL".

On the other hand, if there are only a number of reference points less than the predetermined threshold in the area at the same position as the target child node, the tree synthesis unit 2020 proceeds to step S807 and sets the context of the target child node to "pred1".

If, after the processing of step S807 or S808, context selection has not been completed for all child nodes of the target node, the tree synthesis unit 2020 returns to step S804 and performs the same processing for the next child node.

When context selection has been completed for all child nodes of the target node, the tree synthesis unit 2020 terminates the process.

After selecting the context as described above, the tree synthesis unit 2020 proceeds to step S702.

In step S702, the tree synthesis unit 2020 decodes the occupancy information, i.e., the occupancy code, of each child node of the target node based on the context selected in step S701.

Here, each context corresponds to an independent probability distribution. By updating the context in step S703, which will be described later, the probability that the point to be decoded exists is learned for each context.

The initial value of the probability distribution in each context can be defined as, for example, a 50% probability that a point exists (= a 50% probability that it does not exist).

In step S702, the tree synthesis unit 2020 performs entropy decoding based on the probability distribution corresponding to the context, and decodes whether a point exists in each child node (whether the value is "1") or not (whether the value is "0"). After completing the decoding of the occupancy code, the tree synthesis unit 2020 proceeds to step S703.

In step S703, the tree synthesis unit 2020 updates the context.

For example, in step S703, if a point exists in each context as a result of decoding the occupancy information, the tree synthesis unit 2020 updates the probability distribution associated with each context so that the probability that the point exists becomes higher.

On the other hand, in step S703, if the point does not exist in each context as a result of decoding the occupancy information, the tree synthesis unit 2020 updates the probability distribution associated with each context so that the probability that a point exists is lowered.

Once the context update is complete, the tree synthesis unit 2020 proceeds to step S704 and terminates the process.

After decoding the occupancy code, the tree synthesis unit 2020 proceeds to step S603 and moves on to processing the next node.

(Approximate surface synthesis unit 2030)
The approximate surface synthesis unit 2030 is configured to perform a decoding process for each node determined to be a Trisoup node by the tree synthesis unit 2020 as described with reference to FIG.

Below, an example of the processing performed by the approximate surface synthesis unit 2030 is explained using Figures 9 to 20.

Figure 9 is a flowchart showing an example of processing by the approximate surface synthesis unit 2030.

As shown in FIG. 9, in step S901, the approximate surface synthesis unit 2030 decodes the vertex positions for each node.

Here, when Trisoup at multiple levels is permitted, i.e., when the value of trisoup_multilevel_enabled_flag is "1", the approximate surface synthesis unit 2030 decodes the vertex positions for each node in the minimum Trisoup node size.

On the other hand, when Trisoup at multiple levels is not permitted, i.e., when the value of trisoup_multilevel_enabled_flag is "0", the approximate surface synthesis unit 2030 decodes the vertex positions for each node in the Trisoup node size. The specific processing will be described later.

After decoding of the vertex positions is complete, the approximate surface synthesis unit 2030 proceeds to step S902.

In step S902, the approximate surface synthesis unit 2030 determines a projection surface for each node whose vertex position has been decoded (the minimum Trisoup node size, or each node in the Trisoup node size).

For example, when there are three axes, x-axis, y-axis, and z-axis, a plane with one of the axes degenerated is called a projection plane.

In step S902, the approximate surface synthesis unit 2030 determines which of the above-mentioned axes to degenerate, i.e., which of the x-y plane, x-z plane, and y-z plane to use as the projection plane. The specific processing will be described later.

After determining the projection surface, the approximate surface synthesis unit 2030 proceeds to step S903.

In step S903, the approximate surface synthesis unit 2030 sorts the vertices projected onto the projection surface, for example in a counterclockwise order, and assigns indices according to the order.

After assigning the index, the approximate surface synthesis unit 2030 proceeds to step S904.

In step S904, the approximate surface synthesis unit 2030 generates triangles based on the above-mentioned index and the number of vertices present in the target node.

For example, the approximate surface synthesis unit 2030 can generate triangles by creating a table that defines which index to generate for each number of vertices and referencing the table. A specific example of the table can be the one described in the above-mentioned literature 1.

After generating the triangles, the approximate surface synthesis unit 2030 proceeds to step S905.

In step S905, the approximate surface synthesis unit 2030 generates points based on the triangles generated in step S904. A specific method for generating points can be, for example, the method described in the above-mentioned literature 1.

After point generation has been completed for all nodes, the approximate surface synthesis unit 2030 proceeds to step S906 and ends the process.

Next, a specific example of the process of decoding the vertex positions in step S901 will be described. Figure 10 is a flowchart showing an example of the process of decoding the vertex positions of Trisoup.

As shown in FIG. 10, in step S1001, the approximate surface synthesis unit 2030 determines whether processing of all Trisoup hierarchies has been completed. Here, the number of all Trisoup hierarchies can be defined as follows:

When multi-level trisoup is allowed, i.e. when the value of trisoup_multilevel_enabled_flag is "1", the total number of trisoup hierarchies can be defined as (maximum trisoup node size - minimum trisoup node size + 1).

In other words, in this case, the total number of Trisoup hierarchies can be defined as (log2_trisoup_max_node_size_minus2 - log2_trisoup_min_node_size_minus2 + 1).

When multi-level Trisoup is not allowed, i.e., when the value of trisoup_multilevel_enabled_flag is "0", the total number of Trisoup hierarchies is 1.

If processing of all Trisoup hierarchies is complete, the approximate surface synthesis unit 2030 proceeds to step S1007. If processing of all Trisoup hierarchies is not complete, the approximate surface synthesis unit 2030 proceeds to step S1002.

In step S1002, the approximate surface synthesis unit 2030 checks the number of unique segments belonging to the target Trisoup hierarchy.

If the number of unique segments is "0", i.e., if the target Trisoup hierarchy does not contain any Trisoup nodes, the approximate surface synthesis unit 2030 proceeds to step S1001 and moves on to processing the next Trisoup hierarchy.

If the number of unique segments is greater than "0", the approximate surface synthesis unit 2030 proceeds to step S1003.

In step S1003, the approximate surface synthesis unit 2030 decodes whether each unique segment contains a vertex to be used in the Trisoup process.

The number of vertices that can exist for each unique segment may be limited to one. In this case, the number of unique segments in which a vertex exists can be interpreted as being equal to the number of vertices.

After the approximate surface synthesis unit 2030 decodes the presence or absence of vertices for all unique segments in the target Trisoup hierarchy, it proceeds to step S1004.

In step S1004, the approximate surface synthesis unit 2030 decodes position information indicating where on each unique segment the vertex is located for each unique segment in which it was determined in step S1003 that a vertex exists.

The location information may be encoded with an L-bit equal-length code, for example, if the Trisoup node size in the target Trisoup hierarchy is L (the Lth power of 2).

After the approximate surface synthesis unit 2030 decodes the vertex positions for all unique segments in which vertices exist in the target Trisoup hierarchy, it proceeds to step S1006.

In step S1006, if the node size in the target Trisoup hierarchy is the minimum Trisoup node size, the approximate surface synthesis unit 2030 proceeds to S1001 without performing any processing.

Similarly, if multi-level trisoup is not permitted, the approximate surface synthesis unit 2030 does not perform any processing and proceeds to step S1001.

Otherwise, that is, if multi-level Trisoup is permitted and the node size in the target Trisoup hierarchy is larger than the minimum Trisoup node size, the approximate surface synthesis unit 2030 generates vertex positions in the minimum Trisoup node size based on the vertex positions in the node size corresponding to the target Trisoup hierarchy decoded in step S1004. A specific processing example will be described later.

After vertex position generation for the minimum node size is completed, the approximate surface synthesis unit 2030 proceeds to step S1001.

In step S1007, the approximate surface synthesis unit 2030 integrates the vertex positions.

For example, when the approximate surface synthesis unit 2030 generates vertex positions at the minimum Trisoup node size from vertex positions at a large node size in step S1006, there is a possibility that two or more vertices will be generated on each side of the node.

If there is an edge for which two or more vertices have been generated, the approximate surface synthesis unit 2030 merges them into one vertex so that each edge has one vertex.

For example, the approximate surface synthesis unit 2030 can combine multiple points into one point by taking the average value of the coordinates of the vertices on an edge.

As another example, if the number of vertices is odd, the approximate surface synthesis unit 2030 can narrow down the number of vertices to one by selecting the point with the median coordinate value.

In addition, if the number of vertices is even, the approximate surface synthesis unit 2030 can narrow down the number of vertices to one by extracting two points with the median coordinate values and then averaging the coordinate values of these two points.

After merging all the vertices for each edge into one, the approximate surface synthesis unit 2030 proceeds to step S1008 and ends the process.

Next, we will explain a specific example of the processing in step S1006.

Below, an example of the processing of step S1006 described above will be explained using Figures 11 and 12.

Figure 12 shows an example in which the node size corresponding to the target Trisoup layer decrypted in step S1004 is N (the length of one side of the node is the Nth power of 2) and the minimum Trisoup node size is N-1.

The purpose of the processing in step S1006 is to generate vertices (9 points in FIG. 12) at the minimum Trisoup node size (N-1 in FIG. 12) shown in FIG. 12-3 from vertices (4 points in FIG. 12) at the node size (N in FIG. 12) corresponding to the target Trisoup hierarchy shown in FIG. 12-1.

Figure 11 is a flowchart showing an example of the processing of step S1006 described above.

As shown in FIG. 11, the approximate surface synthesis unit 2030 performs steps S1101 to S1104 using as input the vertex positions at the node size corresponding to the target Trisoup hierarchy decoded in step S1004.

The processing of steps S1101 to S1104 can be achieved in a similar manner to steps S902 to S905 in Figure 9.

Here, FIG. 12-1 shows an example of the processing result of step S1103 (i.e., an example of input data of step S1104), and FIG. 12-2 shows an example of the processing result of step S1104.

As shown in FIG. 12-1, in step S1104, the approximate surface synthesis unit 2030 generates points at all intersections between the triangular faces shown in FIG. 12-1 and integer coordinate positions.

The approximate surface synthesis unit 2030 converts the triangle shown in FIG. 12-1 into points as shown in FIG. 12-2, and then proceeds to step S1105.

In step S1105, the approximate surface synthesis unit 2030 determines the vertex positions at the minimum Trisoup node size from the points generated in step S1104.

Specifically, the approximate surface synthesis unit 2030 can determine the vertex positions for each edge by, for example, extracting points adjacent to the edges of each node corresponding to the smallest Trisoup node size from among the points generated in step S1104 and calculating the average value of the coordinates of the extracted points.

For example, when the position of an edge is along the x-axis direction, for example, when the edge is located at a position that satisfies (x, y, z) = (a to a + 2 ^(N-1) , b, c), the approximate surface synthesis unit 2030 can extract points that exist in the area (a to a + 2 ^(N-1) , b-1 to b, c-1 to c) and calculate the average value e of the x-axis coordinates of those points to determine (e, b, c) as the vertex position.

The approximate surface synthesis unit 2030 can perform calculations similar to those described above even when the edges are aligned along the y-axis and z-axis directions.

Note that if there are no points in the area adjacent to an edge, the approximate surface synthesis unit 2030 will not generate a vertex on that edge.

In this way, the approximate surface synthesis unit 2030 can generate vertex positions at the minimum Trisoup node size, for example, as shown in Figure 12-3.

Next, another specific example of the processing of step S1106 will be described with reference to Figures 13 and 14.

Figure 13 is a flowchart showing an example of the processing of step S1006.

As shown in FIG. 13, the approximate surface synthesis unit 2030 performs steps S1301 to S1303 using as input the vertex positions at the node size corresponding to the target Trisoup hierarchy decoded in step S1004.

The processing of steps S1301 to S1303 can be achieved in a similar manner to steps S902 to S904 in FIG. 9.

Figure 14-1 shows an example of the processing result of step S1303. As can be seen from Figure 14-1, the processing result of step S1303 and the processing result of step S1103 are similar.

After generating the triangles, the approximate surface synthesis unit 2030 proceeds to step S1304, as shown in FIG. 14-1.

In step S1304, the approximate surface synthesis unit 2030 generates points at the intersections between the faces of each triangle generated in step S1303 and each side of the node corresponding to the minimum Trisoup node size.

Figure 14-2 shows an example of the processing result of step S1304. After the approximate surface synthesis unit 2030 generates points on each side, the process proceeds to step S1305.

In step S1305, the approximate surface synthesis unit 2030 integrates the points generated on each edge corresponding to the minimum Trisoup node size in step S1304.

The processing in step S1304 generates points at the intersections of each triangular face and an edge, so for example, if two or more triangular faces intersect a single edge, it is possible that two or more vertices will be generated on the same edge.

In this case, the approximate surface synthesis unit 2030 may process the points that exist on the same side to have one vertex per side.

Specifically, for example, multiple points can be merged into one point by taking the average value of the coordinates of the vertices on an edge.

As another example, if the number of vertices is odd, the approximate surface synthesis unit 2030 can narrow down the number of vertices to one by selecting the point with the median coordinate value.

In addition, if the number of vertices is even, the approximate surface synthesis unit 2030 can narrow down the number of vertices to one by extracting two points with the median coordinate values and then averaging the coordinate values of these two points.

After integrating the points on each side as described above, the approximate surface synthesis unit 2030 proceeds to step S1306 and ends the process.

As described above, when Trisoup at multiple levels is allowed, the approximate surface synthesis unit 2030 of the present invention may be configured to decode the vertex positions for each Trisoup node size as shown in step S1004 of FIG. 10, generate vertex positions at the minimum Trisoup node size from the above-mentioned vertex positions as shown in step S1005, and generate points at the minimum Trisoup node size as shown in step S905.

In other words, the approximate surface synthesis unit 2030 may be configured to perform vertex decoding processing for each of multiple node sizes and to perform vertex-based point reconstruction processing for a single node size.

Furthermore, as described above, the approximate surface synthesis unit 2030 is configured to perform vertex decoding processing at each node size between the maximum and minimum based on the maximum node size and the minimum node size decoded from the control data, and if such node size is not the minimum node size, is configured to generate vertex positions at the minimum node size based on the decoded vertices, is configured to set a single node size as the minimum node size, and may be configured to perform point reconstruction processing based on the vertex positions at the minimum node size.
With this configuration, the decoding unit of the vertex positions can be made variable, thereby reducing the amount of coding for information related to the vertices according to the geometric characteristics of the point cloud, while the reconstruction of points is performed using a single, small node size, thereby improving the subjective quality of the decoded point cloud.

Furthermore, as described above, the approximate surface synthesis unit 2030 may be configured to generate points based on the decoded vertices when the node size is not the minimum node size, and generate vertex positions at the minimum node size based on the coordinate values of points that exist near each side when the node of that node size is divided by the minimum node size among the generated points.

In this way, by reusing part of the point reconstruction processing in the approximate surface synthesis unit 2030 to generate vertex positions at the minimum node size, the processing circuits and processing functions can be reused, reducing design costs.

As described above, when the node size is not the minimum node size, the approximate surface synthesis unit 2030 may be configured to generate points based on the decoded vertices only on each side when the node of that node size is divided by the minimum node size when generating points based on the decoded vertices. In this way, by minimizing the number of points generated, the amount of memory and processing required for the process can be reduced.

As described above, when the node size is not the minimum node size, the approximate surface synthesis unit 2030 may be configured to, when generating points based on the decoded vertices, integrate those points and generate vertex positions at the minimum node size so that there is one vertex on each side when a node of such node size is divided by the minimum node size, if multiple points exist on each side as a result of the node being divided. In this way, by limiting the number of vertices to one on each side, the point reconstruction process can be simplified.

As described above, the approximate surface synthesis unit 2030 may be configured to integrate multiple vertices on an edge that are generated from nodes of different node sizes adjacent to the edge, and generate vertex positions such that there is one vertex on each edge. This configuration can simplify the point reconstruction process.

As described above, the approximate surface synthesis unit 2030 may be configured to set the vertex generated by the node with the smallest node size among the adjacent nodes as the vertex position of the edge when there are multiple vertices on the edge that are generated from nodes of different node sizes adjacent to the edge. In this way, by using the vertex positions of the smallest node size, it becomes possible to reconstruct a point cloud that reproduces more local features, improving the subjective quality.

Next, we will explain a specific example of the processing in step S902 in Figure 9.

An example of the process of step S902 in FIG. 9 will be described below with reference to FIGS.
FIG. 15 is a flowchart showing an example of the process of step S902.

As shown in FIG. 15, in step S1501, the approximate surface synthesis unit 2030 calculates the area of each polygon formed by the vertices when the vertices are projected onto each projection surface.

Figure 16 shows a specific example of the processing in step S1501.

For example, consider the case where the target node has five vertices, A through E, as shown in Figure 16-1.

Figures 16-2 to 16-4 show the vertices shown in Figure 16-1 projected onto their respective projection planes.

Here, the approximate surface synthesis unit 2030 calculates the area of the polygon on each projection surface (the area of the shaded parts in Figures 16-2 to 16-4).

Specifically, the approximate surface synthesis unit 2030 sets the center of the square on each projection surface as the origin O, and calculates the area S of a triangle formed by three points, the origin O and the two vertices adjacent to the origin O (for example, points E and D in Figure 16-2), using the following formula.

S = |E x D|/2
Here, E and D represent vectors indicating the three-dimensional coordinates of points E and D relative to the origin O, the × symbol represents an operator for calculating the cross product of vectors, and |·| represents the L2 norm of a vector.

The approximate surface synthesis unit 2030 applies the above-mentioned points to sort the vertices on each projection surface, for example in counterclockwise order, in a manner similar to step S903, and calculates the areas of the triangles formed by all adjacent vertices and the origin using a method similar to that described above, and then adds them up, thereby calculating the areas of the shaded portions in Figures 16-2 to 16-4.

The above describes the case where the origin O is defined as the center of the square on each projection surface, but the origin O can be defined at another position on the plane of each projection surface and the area of the polygon can be calculated in a similar manner to that described above.

For example, the approximate surface synthesis unit 2030 may position the origin O on a side of a square on the projection surface. Also, for example, the approximate surface synthesis unit 2030 may define one of the vertices projected onto each projection surface as the origin O. For example, the approximate surface synthesis unit 2030 may sort the vertices projected onto each projection surface in counterclockwise order, and then use the first vertex as the origin O.

After calculating the area of the polygon on each projection surface as described above, the approximate surface synthesis unit 2030 proceeds to step S1502.

In step S1502, the approximate surface synthesis unit 2030 determines the projection surface that has the largest area of the polygon found in step S1501 as the projection surface.

After determining the projection surface, the approximate surface synthesis unit 2030 proceeds to step S1503 and ends the process.

When the approximate surface synthesis unit 2030 determines the projection surface using the method shown in FIG. 15, the vertices have already been sorted in step S1501, so the processing of step S903 can be omitted.

As described above, the approximate surface synthesis unit 2030 may be configured to select, as the above-mentioned projection surface, a projection surface that maximizes the area of the polygon defined by multiple vertices present on each side of a node when the multiple vertices are projected onto each of multiple projection surface candidates.

This configuration allows the selection of a projection plane with the largest two-dimensional spread on the projection surface. This prevents the subjective image quality of the decoded point cloud from deteriorating due to the selection of an inappropriate projection plane.

As described above, the approximate surface synthesis unit 2030 may be configured to calculate the area of the above-mentioned polygon (triangle) by calculating the area of a triangle formed by three points, namely, a predetermined origin, one of the vertices projected onto the above-mentioned projection surface candidate (first vertex), and the second vertex adjacent to the first vertex, for all pairs of adjacent vertices.

In this way, by dividing a polygon into small regions and calculating their area, the area calculation process for each small region can be performed in parallel, improving processing speed.

As described above, the approximate surface synthesis unit 2030 may be configured to define a first vector pointing from the origin to the first vertex and a second vector pointing from the origin to the second vertex, and to calculate the area of the triangle using the cross product of the first and second vectors. In this way, by performing calculations using the cross product of vectors, when cross product processing is performed in other processing, the design can be simplified by sharing the processing circuit or processing function.

As described above, the approximate surface synthesis unit 2030 may rearrange the vertices projected onto the above-mentioned projection surface candidate in a counterclockwise or clockwise direction, and set two consecutive vertices in the rearranged order as the first vertex and the second vertex. In this way, by performing sorting in a similar manner to the subsequent step S903, it is possible to standardize the processing and prevent an increase in the amount of processing.

As described above, the approximate surface synthesis unit 2030 may be configured to set one of the vertices (the third vertex) projected onto the above-mentioned projection surface candidate as a predetermined origin. With this configuration, the number of triangles that need to be calculated to calculate the area of the polygon is reduced by one compared to when the predetermined origin is set at a position other than a vertex, thereby preventing an increase in the amount of calculations.

Next, another example of the processing in step S902 will be described using Figures 17 to 20.

Figure 17 is a flowchart showing an example of the processing of step S902.

As shown in FIG. 17, in step S1701, the approximate surface synthesis unit 2030 calculates the difference between the maximum and minimum values of the vertex coordinates in the x-axis, y-axis, and z-axis directions.

For example, as shown in FIG. 19-1, if the target node has a total of five vertices, A through E, the approximate surface synthesis unit 2030 calculates xmax-xmin (the difference between the maximum and minimum coordinate values in the x-axis direction) shown in FIG. 19-2, ymax-ymin (the difference between the maximum and minimum coordinate values in the y-axis direction) and zmax-zmin (the difference between the maximum and minimum coordinate values in the z-axis direction) shown in FIG. 19-3, and proceeds to step S1702.

In step S1702, the approximate surface synthesis unit 2030 checks how many axial directions have the smallest difference between the "difference between the maximum value and the minimum value" calculated in step S1701.

For example, if the relationship is zmax-zmin<xmax-xmin<ymax-ymin (or if the relationship is zmax-zmin<xmax-xmin=ymax-ymin), there is only one axis direction that has the smallest value for the "difference between the maximum and minimum values." In this case, the approximate surface synthesis unit 2030 proceeds to step S1703.

On the other hand, if the relationship is zmax-zmin=xmax-xmin<ymax-ymin, for example, then there are two axis directions with the smallest value of the "difference between the maximum value and the minimum value." In this case, the approximate surface synthesis unit 2030 proceeds to step S1704.

Step S1703 is a process corresponding to the case where there is only one axis direction with the minimum difference. In this case, the approximate surface synthesis unit 2030 determines the projection plane by degenerating the axis with the minimum difference.

For example, if zmax-zmin<xmax-xmin<ymax-ymin as in the example above, the z-axis is degenerated and the x-y plane is determined as the projection plane.

After determining the projection surface, the approximate surface synthesis unit 2030 proceeds to step S1706 and ends the process.

In step S1704, the approximate surface synthesis unit 2030 counts the number of vertices on the edges in each axis direction.

For example, if the target node has a total of five vertices, A through E, as shown in Figure 20-1, the only vertex on the edge in the x-axis direction is point A, as shown in Figure 20-2, there are zero vertices on the edge in the y-axis direction, as shown in Figure 20-3, and there are four vertices on the edge in the z-axis direction, B through E, as shown in Figure 20-4.

This process may be performed on all of the x, y, and z axes, or on only the axis direction with the smallest "difference between the maximum and minimum values" calculated in step S1701.

For example, if the relationship is zmax-zmin=xmax-xmin<ymax-ymin, the processing target of this step may be only the z-axis and x-axis.

After counting the number of vertices as described above, the approximate surface synthesis unit 2030 proceeds to step S1705.

In step S1705, the approximate surface synthesis unit 2030 determines the projection surface by degenerating the axis with the largest number of vertices in each axis direction calculated in step S1704.

For example, in the example of Figure 20, since the most vertices exist on the sides in the z-axis direction, the approximate surface synthesis unit 2030 degenerates the z-axis and determines the x-y plane as the projection surface.

After determining the projection surface, the approximate surface synthesis unit 2030 proceeds to step S1706 and ends the process.

As described above, the approximate surface synthesis unit 2030 may be configured to classify each edge of a node according to which coordinate axis of a three-dimensional coordinate system it is parallel to, count the number of vertices on the edges classified into each coordinate axis, and use the counted value (number of vertices) to determine the above-mentioned projection surface from among multiple projection surface candidates.

Furthermore, as described above, the approximate surface synthesis unit 2030 may be configured to determine the surface defined by degenerating the axis having the largest number of vertices as the projection surface.

This configuration makes it possible to determine a projection plane that takes into account the two-dimensional spread of the vertex positions with less computational effort than the method described using Figures 15 and 16.

As described above, the approximate surface synthesis unit 2030 may be configured to calculate the difference between the maximum and minimum coordinate values of each vertex for each coordinate axis of the above-mentioned three-dimensional coordinates, and if there are two or more axes among such coordinate axes that have the minimum difference value, to define a surface as the above-mentioned projection surface by degenerating the axis that has the largest number of vertices on its edge classified into each coordinate axis.

As described above, when there are two or more axes with the largest number of vertices on the edges classified into each coordinate axis, the approximate surface synthesis unit 2030 may be configured to calculate the difference between the maximum and minimum coordinate values of each vertex for each coordinate axis of the three-dimensional coordinate system, and to define the surface as the above-mentioned projection surface by degenerating the axis among the coordinate axes with the smallest difference value.

In FIG. 17, the approximate surface synthesis unit 2030 first evaluates the "difference between the maximum value and the minimum value" in steps S1701 and S1702, and then evaluates the number of vertices on the edges in each axis direction as necessary in steps S1704 and S1705. This order can also be reversed, for example, as shown in FIG. 18.

For example, as shown in the example of FIG. 18, the approximate surface synthesis unit 2030 may evaluate the number of vertices on the edges in each axis direction in steps S1801 and S1802, and then evaluate the "difference between the maximum value and the minimum value" as necessary in steps S1804 and S1805.

In the example of Figure 18, step S1801 can be achieved by processing similar to that of step S1704.

In step S1802, if there is only one axis among the x-axis, y-axis, and z-axis directions that has the maximum number of vertices, the approximate surface synthesis unit 2030 proceeds to step S1803, where it determines the projection surface by degenerating the axis with the maximum number of vertices.

If not (if there are two or more axes with the maximum number of vertices), the approximate surface synthesis unit 2030 proceeds to step S1804.

Step S1804 can be achieved by processing similar to that of step S1701.

Here, the processing target of step S1804 may be all of the x-axis, y-axis, and z-axis, or only the axis direction in which the number of vertices is maximum in step S1802 may be processed.
In step S1805, the approximate surface synthesis unit 2030 determines a projection plane by degenerating the axis having the smallest difference value among the axes processed in step S1804.

Next, another example of the process of step S902 will be described with reference to FIG. 22. FIG. 22 is a flowchart showing an example of the process of step S902.

As shown in FIG. 22, in step S2201, the approximate surface synthesis unit 2030 performs a 2×2 orthogonal transformation on the coordinates of each vertex when projected onto each projection surface.

The following describes an example in which the Hadamard transform is used as the orthogonal transform. For example, when a vertex P with coordinate values (Px, Py, Pz) is projected onto the xy plane, its coordinates become (Px, Py). The coordinates (Ha, Hb) after the orthogonal transform obtained by performing a 2x2 Hadamard transform on this can be calculated using the following formula.

ここで、１/√２は、ノルムを正規化するための係数であるが、後述のように、本処理では、各頂点の直交変換後の座標値をその大小関係を比較するために用いるため、正規化係数１/√２は省略してもよい。すなわち、近似表面合成部２０３０は、以下の式によって、（Ｈａ、Ｈｂ）を算出してもよい。

Here, 1/√2 is a coefficient for normalizing the norm, but as described later, in this process, the normalization coefficient 1/√2 may be omitted because the coordinate values after orthogonal transformation of each vertex are used to compare their magnitude relationship. In other words, the approximate surface synthesis unit 2030 may calculate (Ha, Hb) by the following formula.

上述のように、近似表面合成部２０３０は、直交変換としてアダマール変換を使用し、正規化係数を省略した場合、座標値ＰxとＰyの加減算のみで直交変換後の座標（Ｈａ、Ｈｂ）を算出できる。

As described above, the approximate surface synthesis unit 2030 uses the Hadamard transform as the orthogonal transform. When the normalization coefficient is omitted, the coordinates (Ha, Hb) after the orthogonal transform can be calculated by adding and subtracting only the coordinate values Px and Py.

In this way, the approximate surface synthesis unit 2030 first applies an orthogonal transformation to the coordinates of each vertex (1 to n) when projected onto the xy plane to obtain n pairs of coordinates (Ha1, Hb1), ..., (Han, Hbn), and then detects the maximum coordinate values Hamax, Hbmax and the minimum coordinate values Hamin, Hbmin on each coordinate axis (here, the a-axis and b-axis) after the orthogonal transformation.

Then, calculate the difference between the maximum and minimum values on each axis: Had = Hamax - Hamin, Hbd = Hbmax - Hbmin.

Finally, the approximate surface synthesis unit 2030 uses the above-mentioned Had and Hbd to calculate the variable Axy, which represents the extent of the spread of the vertex coordinates when projected onto the xy plane.

The approximate surface synthesis unit 2030 may calculate Axy by adding up the difference between the maximum and minimum values on each axis of the coordinate values after the orthogonal transformation, for example, Axy = Had + Hbd.

The approximate surface synthesis unit 2030 may also calculate Axy by multiplying the difference between the maximum and minimum values on each axis of the coordinate values after orthogonal transformation, for example, Axy = Had x Hbd.

As described above, the approximate surface synthesis unit 2030 calculates Ayz corresponding to the y-z plane and Axz corresponding to the x-z plane, which are other projection plane candidates, and then proceeds to step S2202.

In step S2202, the approximate surface synthesis unit 2030 determines the projection surface based on Axy, Ayz, and Axz calculated in step S2201.

For example, the approximate surface synthesis unit 2030 can determine the projection plane to be the one that corresponds to the largest value among Axy, Ayz, and Axz. Specifically, for example, if Ayz>Axz>Axz, the approximate surface synthesis unit 2030 can determine the projection plane to be the y-z plane.

As described above, after determining the projection surface, the approximate surface synthesis unit 2030 proceeds to step S2203 and ends the process.

As described above, the approximate surface synthesis unit 2030 may be configured to determine the projection surface using coordinate values after orthogonal transformation obtained by applying an orthogonal transformation to the vertex coordinate values when projected onto each projection surface.

As described above, the approximate surface synthesis unit 2030 may be configured to calculate the difference between the maximum and minimum coordinate values on each coordinate axis after the orthogonal transformation, and determine the projection surface based on such difference values.

As described above, the approximate surface synthesis unit 2030 may be configured to calculate the above-mentioned difference values for all coordinate axes after the orthogonal transformation for each projection surface candidate, and determine the projection surface by the sum or product of these values.

By using the coordinate values after rotating the coordinate axes using an orthogonal transformation in this way, it becomes easier to evaluate the two-dimensional spread of the vertices.

Furthermore, as described above, the approximate surface synthesis unit 2030 may be configured to use the Hadamard transform as the orthogonal transform.

Furthermore, as described above, the approximate surface synthesis unit 2030 may be configured to omit the normalization coefficient during the orthogonal transformation.

By configuring in this way, the coordinate values after the orthogonal transformation can be obtained by simply adding and subtracting the coordinate values before the orthogonal transformation, preventing an increase in the amount of calculations.

(Point cloud encoding device 100)
Hereinafter, the point cloud encoding device 100 according to this embodiment will be described with reference to Fig. 21. Fig. 21 is a diagram showing an example of functional blocks of the point cloud encoding device 100 according to this embodiment.

As shown in FIG. 21, the point cloud encoding device 100 has a coordinate transformation unit 1010, a geometric information quantization unit 1020, a tree analysis unit 1030, an approximate surface analysis unit 1040, a geometric information encoding unit 1050, a geometric information reconstruction unit 1060, a color conversion unit 1070, an attribute transfer unit 1080, a RAHT unit 1090, an LoD calculation unit 1100, a lifting unit 1110, an attribute information quantization unit 1120, an attribute information encoding unit 1130, and a frame buffer 1140.

The coordinate conversion unit 1010 is configured to perform a conversion process from the three-dimensional coordinate system of the input point cloud to any different coordinate system. The coordinate conversion may, for example, convert the x, y, and z coordinates of the input point cloud into any s, t, and u coordinates by rotating the input point cloud. In addition, as one variation of the conversion, the coordinate system of the input point cloud may be used as is.

The geometric information quantization unit 1020 is configured to quantize the position information of the input point group after coordinate transformation and remove points with overlapping coordinates. Note that when the quantization step size is 1, the position information of the input point group and the position information after quantization match. In other words, when the quantization step size is 1, it is equivalent to not performing quantization.

The tree analysis unit 1030 is configured to receive position information of the quantized point group as input, and generate an occurrence code that indicates at which node in the encoding target space the point exists, based on the tree structure described below.

In this process, the tree analysis unit 1030 is configured to generate a tree structure by recursively dividing the encoding target space into rectangular parallelepipeds.

If a point exists within a certain rectangular parallelepiped, a tree structure can be generated by recursively dividing the rectangular parallelepiped into multiple rectangular parallelepipeds until the rectangular parallelepiped reaches a specified size. Each such rectangular parallelepiped is called a node. Each rectangular parallelepiped generated by dividing a node is called a child node, and the occurrence code is expressed as 0 or 1 to indicate whether or not a point is contained within a child node.

As described above, the tree analysis unit 1030 is configured to generate an occupancy code while recursively splitting the node until it reaches a predetermined size.

In this embodiment, a method called "Octree" can be used, which recursively performs octree division on the above-mentioned rectangular parallelepiped, always treating it as a cube, and a method called "QtBt" can be used, which performs quadtree division and binary tree division in addition to octree division.

Here, whether or not to use "QtBt" is transmitted to the point cloud decoding device 200 as control data.

Alternatively, predictive coding using an arbitrary tree structure may be specified. In such a case, the tree analysis unit 1030 determines the tree structure, and the determined tree structure is transmitted to the point cloud decoding device 200 as control data.

For example, the tree-structured control data may be configured so that it can be decoded using the procedure described in FIG. 6.

The approximate surface analysis unit 1040 is configured to generate approximate surface information using the tree information generated by the tree analysis unit 1030.

When decoding three-dimensional point cloud data of an object, for example, if the points are densely distributed on the object's surface, approximate surface information is used to represent the area in which the points exist by approximating the area using a small plane, rather than decoding each point individually.

Specifically, the approximate surface analysis unit 1040 may be configured to generate approximate surface information using, for example, a method called "Trisoup." In addition, when decoding a sparse point cloud acquired by Lidar or the like, this process can be omitted.

The geometric information encoding unit 1050 is configured to generate a bit stream (geometric information bit stream) by encoding syntax such as the occupancy code generated by the tree analysis unit 1030 and the approximate surface information generated by the approximate surface analysis unit 1040. Here, the bit stream may include, for example, the syntax described in Figures 4 and 5.

The encoding process is, for example, a context-adaptive binary arithmetic encoding process. Here, for example, the syntax includes control data (flags and parameters) for controlling the decoding process of the position information.

The geometric information reconstruction unit 1060 is configured to reconstruct the geometric information of each point of the point cloud data to be encoded (the coordinate system assumed by the encoding process, i.e., the position information after the coordinate transformation in the coordinate transformation unit 1010) based on the tree information generated by the tree analysis unit 1030 and the approximate surface information generated by the approximate surface analysis unit 1040.

The frame buffer 1140 is configured to receive the geometric information reconstructed by the geometric information reconstruction unit 1060 and store it as a reference frame.

The stored reference frame is read from the frame buffer 1140 and used as a reference frame when the tree analysis unit 1030 performs inter-prediction of temporally different frames.

Here, which reference frame to use for each frame may be determined based on, for example, the value of a cost function representing the encoding efficiency, and information on the reference frame to be used may be transmitted to the point cloud decoding device 200 as control data.

The color conversion unit 1070 is configured to perform color conversion when the input attribute information is color information. It is not necessary to perform color conversion, and whether or not to perform color conversion processing is coded as part of the control data and transmitted to the point cloud decoding device 200.

The attribute transfer unit 1080 is configured to correct attribute values so as to minimize distortion of attribute information based on the position information of the input point cloud, the position information of the point cloud after reconstruction in the geometric information reconstruction unit 1060, and the attribute information after color change in the color conversion unit 1070. A specific correction method that can be applied is, for example, the method described in Document 2 (Text of ISO/IEC 23090-9 DIS Geometry-based PCC, ISO/IEC JTC1/SC29/WG11 N19088).

The RAHT unit 1090 is configured to receive the attribute information transferred by the attribute transfer unit 1080 and the geometric information generated by the geometric information reconstruction unit 1060 as input, and to generate residual information for each point using a type of Haar transform called RAHT (Region Adaptive Hierarchical Transform). As a specific example of the RAHT process, the method described in the above-mentioned literature 2 can be used.

The LoD calculation unit 1100 is configured to receive the geometric information generated by the geometric information reconstruction unit 1060 as input and generate the LoD (Level of Detail).

LoD is information for defining a reference relationship (a referencing point and a referenced point) to realize predictive coding, such as predicting attribute information of a certain point from attribute information of another point and encoding or decoding the prediction residual.

In other words, LoD is information that defines a hierarchical structure in which each point contained in the geometric information is classified into multiple levels, and the attributes of points belonging to lower levels are encoded or decoded using attribute information of points belonging to higher levels.

As a specific method for determining LoD, for example, the method described in the above-mentioned literature 2 may be used.

The lifting unit 1110 is configured to generate residual information by a lifting process using the LoD generated by the LoD calculation unit 1100 and the attribute information after attribute transfer in the attribute transfer unit 1080.

Specific lifting processing may be performed, for example, using the method described in the above-mentioned document 2.

The attribute information quantization unit 1120 is configured to quantize the residual information output from the RAHT unit 1090 or the lifting unit 1110. Here, a quantization step size of 1 is equivalent to no quantization being performed.

The attribute information encoding unit 1130 is configured to perform encoding processing using the quantized residual information, etc. output from the attribute information quantization unit 1120 as syntax, and generate a bit stream related to the attribute information (attribute information bit stream).

The encoding process is, for example, a context-adaptive binary arithmetic encoding process. Here, for example, the syntax includes control data (flags and parameters) for controlling the decoding process of the attribute information.

Through the above process, the point cloud encoding device 100 is configured to perform encoding processing using the position information and attribute information of each point in the point cloud as input, and to output a geometric information bit stream and an attribute information bit stream.

Furthermore, the above-mentioned point cloud encoding device 100 and point cloud decoding device 200 may be realized as a program that causes a computer to execute each function (each process).

In each of the above embodiments, the present invention has been described using the point cloud encoding device 100 and the point cloud decoding device 200 as examples, but the present invention is not limited to such examples and can be similarly applied to a point cloud encoding/decoding system having the functions of the point cloud encoding device 100 and the point cloud decoding device 200.

In addition, according to this embodiment, for example, it is possible to realize an improvement in the overall service quality in video communication, which makes it possible to contribute to Goal 9 of the Sustainable Development Goals (SDGs) led by the United Nations, which is to "build resilient infrastructure, promote sustainable industrialization and foster innovation."

10... Point cloud processing system 100... Point cloud encoding device 1010... Coordinate conversion unit 1020... Geometric information quantization unit 1030... Tree analysis unit 1040... Approximate surface analysis unit 1050... Geometric information encoding unit 1060... Geometric information reconstruction unit 1070... Color conversion unit 1080... Attribute transfer unit 1090... RAHT unit 1100... LoD calculation unit 1110... Lifting unit 1120... Attribute information quantization unit 1130... Attribute Information encoding unit 1140...frame buffer 200...point cloud decoding device 2010...geometric information decoding unit 2020...tree synthesis unit 2030...approximate surface synthesis unit 2040...geometric information reconstruction unit 2050...inverse coordinate transformation unit 2060...attribute information decoding unit 2070...inverse quantization unit 2080...RAHT unit 2090...LoD calculation unit 2100...inverse lifting unit 2110...inverse color transformation unit 2120...frame buffer

Claims (4)

A point cloud decoding device, comprising:
an approximation surface synthesis unit configured to select, from among a plurality of projection plane candidates, a projection plane that maximizes the area of a polygon defined by a plurality of vertices present on each side of a node when the vertices are projected onto each of the projection plane candidates;
The point cloud decoding device is characterized in that the approximate surface synthesis unit is configured to calculate the area of the polygon by calculating the area of a triangle formed by three points: a predetermined origin, a first vertex that is one of the vertices projected onto the projection surface candidate, and a second vertex adjacent to the first vertex, for all pairs of adjacent vertices. The point cloud decoding device according to claim 1, wherein the approximate surface synthesis unit is configured to rearrange the vertices projected onto the projection surface candidate in a counterclockwise or clockwise direction, and to set two consecutive vertices in the rearranged order as the first vertex and the second vertex. 1. A point cloud decoding method, comprising:
selecting, from among a plurality of projection plane candidates, a projection plane which maximizes the area of a polygon defined by a plurality of vertices present on each side of the node when the plurality of vertices are projected onto each of the projection plane candidates;
A point cloud decoding method characterized in that in the above process, the area of the polygon is calculated by calculating the area of a triangle formed by three points: a predetermined origin, a first vertex that is one of the vertices projected onto the candidate projection plane, and a second vertex adjacent to the first vertex, for all pairs of adjacent vertices. A program for causing a computer to function as a point group decoding device,
The point cloud decoding device includes an approximation surface synthesis unit configured to select, from among a plurality of projection plane candidates, a projection plane that maximizes an area of a polygon defined by a plurality of vertices present on each side of a node when the vertices are projected onto each of the projection plane candidates;
The program is configured to calculate the area of the polygon by calculating the area of a triangle formed by three points: a predetermined origin, a first vertex that is one of the vertices projected onto the projection surface candidate, and a second vertex adjacent to the first vertex, for all pairs of adjacent vertices.

Images