JP7325534B2 - Method and apparatus for point cloud encoding - Google Patents

Description

INCORPORATION BY REFERENCE This application claims the benefit of priority to U.S. patent application Ser. Claims priority benefit to U.S. Provisional Application No. 63/004,304, "METHOD AND APPARATUS FOR FLEXIBLE QUAD-TREE AND BINARY-TREE PARTITIONING FOR GEOMETRY CODING," filed Jan. 2. The entire disclosure of the prior application is incorporated herein by reference in its entirety.

This disclosure describes embodiments generally related to point cloud encoding.

The background description provided herein is for the purpose of generally presenting the context of the present disclosure. Our work, to the extent set forth in this Background Section, as well as aspects of the description that may otherwise not be admitted as prior art at the time of filing, are expressly identified as prior art to the present disclosure. is not allowed either implicitly or

Various techniques have been developed to capture and represent the world, such as world objects, world environments, etc., in three-dimensional (3D) space. A 3D representation of the world can enable more immersive interaction and communication. A point cloud can be used as a 3D representation of the world. A point cloud is a set of points in 3D space, each having attributes such as color, material properties, texture information, intensity attributes, reflectance attributes, motion-related attributes, modality attributes, and/or various other attributes. Has associated attributes. Such point clouds can contain large amounts of data and can be costly and time consuming to store and transmit.

Aspects of the present disclosure provide methods and apparatus for point cloud compression and decompression. According to one aspect of the present disclosure, a method of point cloud geometry decoding in a point cloud decoder is provided. In this method, first signaling information may be received from an encoded bitstream of a point cloud that includes a set of points in three-dimensional (3D) space. The first signaling information may indicate segmentation information of the point cloud. The second signaling information can be determined based on the first signaling information indicating the first value. The second signaling information may indicate the partitioning mode of the set of points in 3D space. Additionally, a partitioning mode for a set of points in 3D space can be determined based on the second signaling information. The point cloud can then be reconstructed based on segmentation modes.

In some embodiments, the partitioning mode can be determined to be a predetermined quadtree and binary tree (QtBt) partition based on second signaling information indicative of a second value.

The method may receive third signaling information indicating that the 3D space is an asymmetric cuboid. The dimensions of the 3D space signaled along the x, y, and z directions can be determined based on third signaling information indicative of the first value.

In some embodiments, 3-bit signaling information can be determined for each of the multiple partitioning levels in the partitioning mode based on the second signaling information indicative of the first value. The 3-bit signaling information for each of the multiple partitioning levels can indicate partitioning directions along the x, y, and z directions for the respective partitioning level in partitioning mode.

In some embodiments, the 3-bit signaling information can be determined based on the dimensionality of the 3D space.

In this method, the partitioning mode can be determined based on the first signaling information indicative of the second value, the partitioning mode including a respective octree partition at each of the plurality of partitioning levels in the partitioning mode. be able to.

According to one aspect of the present disclosure, a method of point cloud geometry decoding in a point cloud decoder is provided. In this method, first signaling information may be received from an encoded bitstream of a point cloud that includes a set of points in three-dimensional (3D) space. The first signaling information may indicate segmentation information of the point cloud. A partitioning mode for the set of points in 3D space may be determined based on the first signaling information, and the partitioning mode may include multiple partitioning levels. The point cloud can then be reconstructed based on segmentation modes.

In some embodiments, the 3-bit signaling information for each of the multiple partitioning levels in the partitioning mode can be determined based on the first signaling information indicating the first value, The 3-bit signaling information for each can indicate the partition direction along the x, y, and z directions for each partition level in partition mode.

In some embodiments, the 3-bit signaling information can be determined based on the dimensionality of the 3D space.

In some embodiments, the partitioning mode can be determined to include a respective octree partition in each of the plurality of partitioning levels in the partitioning mode based on the first signaling information indicative of the second value. can.

The method may further receive second signaling information from the encoded bitstream for the point cloud. The second signaling information is such that when the second signaling information is the first value, the 3D space is an asymmetric rectangular parallelepiped, and when the second signaling information is the second value, the 3D space is a symmetrical rectangular parallelepiped It can be shown that

In some embodiments, based on the first signal information indicative of the second value and the second signal information indicative of the first value, the partition mode determines the first partition at the plurality of partition levels of the partition mode. Each of the levels can be determined to contain a respective octree partition. The partition type and partition direction of the last partition level among the multiple partition levels of the partition mode must meet the following conditions:

where d _x , d _y , and d _z are the log2 sizes of 3D space in the x, y, and z directions, respectively.

In the method, the second signaling information can be determined based on the first signaling information indicative of the first value. The second signaling information indicates that the 3D space is an asymmetric cuboid when the second signaling information indicates the first value, and the 3D space is a symmetric cuboid when the second signaling information indicates the second value It can be shown that Additionally, the dimensions of the 3D space signaled along the x, y, and z directions can be determined based on second signaling information indicative of the first value.

In some examples, an apparatus for processing point cloud data includes receiving circuitry and processing circuitry configured to perform one or more of the methods described above.

Further features, properties and various advantages of the disclosed subject matter will become more apparent from the following detailed description and accompanying drawings.

1 is a schematic illustration of a simplified block diagram of a communication system in accordance with one embodiment; FIG. 1 is a schematic illustration of a simplified block diagram of a streaming system according to one embodiment; FIG. 1 is a block diagram of an encoder for encoding point cloud frames, according to some embodiments; FIG. FIG. 4 is a block diagram of a decoder for decoding compressed bitstreams corresponding to point cloud frames, according to some embodiments; 1 is a schematic diagram of a simplified block diagram of a video decoder according to one embodiment; FIG. 1 is a schematic diagram of a simplified block diagram of a video encoder according to one embodiment; FIG. FIG. 4 is a block diagram of a decoder for decoding compressed bitstreams corresponding to point cloud frames, according to some embodiments; 1 is a block diagram of an encoder for encoding point cloud frames, according to some embodiments; FIG. [0014] FIG. 4 illustrates partitioning a cube based on the octree partitioning technique, according to some embodiments of the present disclosure; [0014] Figure 4 illustrates an example of an octree partition and an octree structure corresponding to the octree partition, according to some embodiments of the present disclosure; FIG. 10 illustrates a point cloud with a shorter bounding box in the z-direction, according to some embodiments of the present disclosure; FIG. 4 illustrates partitioning a cube based on the octree partitioning technique along the xy, xz, and yz axes, according to some embodiments of the present disclosure; [0014] FIG. 4 illustrates sectioning a cube based on the binary sectioning technique along the x, y, and z axes, according to some embodiments of the present disclosure; 1 is a first flowchart outlining a first example process, according to some embodiments; 4 is a second flowchart outlining a second example process, according to some embodiments; 1 is a schematic diagram of a computer system according to one embodiment; FIG.

Advanced 3D representations of the world enable more immersive interaction and communication, and also enable machines to understand, interpret and navigate the world. 3D point clouds have emerged as a way to express such information. Several application cases related to point cloud data have been identified and corresponding requirements for point cloud representation and compression have been developed. For example, 3D point clouds can be used in autonomous driving for object detection and localization. 3D point clouds can also be used in geographic information systems (GIS) for cartography and in cultural heritage sites to visualize and archive cultural heritage objects and collections.

A point cloud can generally refer to a set of points in 3D space, each with associated attributes. Attributes may include color, material properties, texture information, intensity attributes, reflectance attributes, motion-related attributes, modality attributes, and/or various other attributes. A point cloud can be used to reconstruct an object or scene as a composition of such points. Points can be captured using multiple cameras, depth sensors, and/or lidar in various settings, ranging from thousands up to billions of points for a realistic representation of the reconstructed scene. can be configured with

Compression techniques can reduce the amount of data required to represent the point cloud for faster transmission or reduced storage. Therefore, there is a need for techniques for lossy compression of point clouds for use in real-time communications and six degrees of freedom (6 DoF) virtual reality. Moreover, there is a need for techniques for reversible point cloud compression in the context of dynamic mapping, such as for autonomous driving and cultural heritage applications. ISO/IEC MPEG (JTC 1/SC 29/WG 11) therefore requires compression of geometric shapes and attributes such as color and reflectance, scalable/progressive coding, and processing of sequences of point clouds captured over time. Work has begun on a standard to address encoding and random access to subsets of point clouds.

FIG. 1 shows a simplified block diagram of a communication system (100) according to embodiments of the present disclosure. A communication system (100) includes, for example, a plurality of terminal devices capable of communicating with each other via a network (150). For example, a communication system (100) includes a pair of terminals (110) and (120) interconnected via a network (150). In the example of FIG. 1, a first pair of terminals (110) and (120) may perform unidirectional transmission of point cloud data. For example, the terminal (110) can compress a cloud of points (eg, points representing structures) captured by a sensor (105) connected to the terminal (110). The compressed point cloud can be transmitted over the network (150) to another terminal device (120), eg in the form of a bitstream. The terminal device (120) can receive the compressed point cloud from the network (150), decompress the bitstream to reconstruct the point cloud, and display the reconstructed point cloud appropriately. One-way data transmission may be common in media serving applications and the like.

In the example of FIG. 1, terminals (110) and (120) may be shown as servers and personal computers, but the principles of the disclosure may not be so limited. Embodiments of the present disclosure apply to laptop computers, tablet computers, smart phones, gaming consoles, media players, and/or dedicated three-dimensional (3D) equipment. Network (150) represents any number of networks that transmit compressed point clouds between terminals (110) and (120). Network (150) may include, for example, wired (wired) and/or wireless communication networks. The network (150) may exchange data over circuit-switched channels and/or packet-switched channels. Typical networks include telecommunications networks, local area networks, wide area networks and/or the Internet. For purposes of this discussion, the architecture and topology of network (150) may not be critical to the operation of the present disclosure unless otherwise described herein.

FIG. 2 shows a simplified block diagram of a streaming system (200) according to one embodiment. The example of FIG. 2 is an application of the disclosed subject matter to point clouds. The disclosed subject matter may be equally applicable to other point cloud enabled applications such as 3D telepresence applications, virtual reality applications.

The streaming system (200) can include a capture subsystem (213). The capture subsystem (213) is a point cloud source (201), such as a light detection and ranging (LIDAR) system, 3D camera, 3D scanner, e.g. It can include graphics generation components and the like that generate point clouds. In one example, the point cloud (202) includes points captured by a 3D camera. The point cloud (202) is shown as a bold line to emphasize the high data volume compared to the compressed point cloud (204) (compressed point cloud bitstream). The compressed point cloud (204) can be generated by an electronic device (220) including an encoder (203) coupled to the point cloud source (201). The encoder (203) may include hardware, software, or a combination thereof to enable or implement aspects of the disclosed subject matter, as described in more detail below. Compressed point cloud (204) (or compressed point cloud (204) bitstream), shown as a thin line to highlight the lower amount of data compared to the stream of point cloud (202), is , can be stored on the streaming server (205) for future use. One or more streaming client subsystems, such as the client subsystems (206) and (208) in Figure 2, access the streaming server (205) to replicate (207) and (209) can be obtained. The client subsystem (206) may include the decoder (210) in the electronic device (230), for example. The decoder (210) decodes the incoming replica (207) of the compressed point cloud and produces an outgoing stream of reconstructed point cloud (211) that can be rendered on the rendering device (212). Generate.

Note that electronic devices (220) and (230) may include other components (not shown). For example, the electronic device (220) may include a decoder (not shown) and the electronic device (230) may also include an encoder (not shown).

In some streaming systems, the compressed point clouds (204), (207), and (209) (eg, compressed point cloud bitstreams) can be compressed according to a particular standard. In some examples, video coding standards are used to compress the point cloud. Such standards include, for example, HEVC (High Efficiency Video Coding) (HEVC) and VVC (Versatile Video Coding) (VVC).

FIG. 3 shows a block diagram of a V-PCC encoder (300) for encoding point cloud frames, according to some embodiments. In some embodiments, the V-PCC encoder (300) can be used in communication systems (100) and streaming systems (200). For example, the encoder (203) can be configured and operate similarly to the V-PCC encoder (300).

The V-PCC encoder (300) receives point cloud frames as uncompressed input and produces a bitstream corresponding to the compressed point cloud frames. In some embodiments, the V-PCC encoder (300) may receive point cloud frames from a point cloud source, such as the point cloud source (201).

In the example of FIG. 3, the V-PCC encoder (300) includes a patch generation module (306), a patch packing module (308), a geometry image generation module (310), and a texture image generation module (312). , a patch information module (304), an occupancy map module (314), a smoothing module (336), an image padding module (316) and (318), a group expansion module (320), and a video compression module (322). ), (323) and (332), an auxiliary patch information compression module (338), an entropy compression module (334), and a multiplexer (324).

According to one aspect of the present disclosure, the V-PCC encoder (300) stores some metadata (e.g., occupancy map and patch information) to transform the 3D point cloud frame into an image-based representation. In some examples, the V-PCC encoder (300) converts the 3D point cloud frame into geometry images, texture images and occupancy maps, and then uses video encoding techniques to convert the geometry images, texture images and occupancy maps. A map can be encoded into a bitstream. In general, a geometry image is a 2D image that has pixels filled with geometry values associated with points projected onto the pixels, and the pixels filled with geometry values can be referred to as geometry samples. A texture image is a 2D image that has pixels filled with texture values associated with points projected onto the pixels, and the pixels filled with texture values can be referred to as texture samples. An occupancy map is a 2D image with pixels filled with values indicating whether they are occupied or not occupied by patches.

A patch can generally refer to a contiguous subset of the surface described by the point cloud. In one example, a patch includes points that have surface normal vectors that are offset from each other by less than a threshold amount. A patch generation module (306) segments the point cloud into sets of patches that may or may not overlap, such that each patch can be described by a depth field for a plane in 2D space. In some embodiments, the patch generation module (306) aims to decompose the point cloud into a minimal number of patches with smooth boundaries while minimizing reconstruction errors.

A patch information module (304) can collect patch information that indicates the size and shape of the patch. In some examples, patch information may be packed into image frames and then encoded by the auxiliary patch information compression module (338) to produce compressed auxiliary patch information.

The patch packing module (308) maps the extracted patches onto a two-dimensional (2D) grid while minimizing the unused space and packing all MxM (e.g. 16x16 ) blocks are associated with unique patches. Efficient patch packing can directly impact compression efficiency by minimizing unused space or ensuring temporal consistency.

A geometry image generation module (310) can generate a 2D geometry image associated with the geometry of the point cloud at a given patch location. A texture image generation module (312) can generate a 2D texture image associated with the point cloud texture at a given patch location. Geometry image generation module (310) and texture image generation module (312) utilize the 3D to 2D mapping computed during the packing process to store point cloud geometry and texture as images. To better handle the case where multiple points are projected onto the same sample, each patch is projected into two images called layers. In one example, the geometry image is represented by a WxH monochrome frame in YUV420-8 bit format. To generate the texture image, the texture generation procedure utilizes the reconstructed/smoothed geometry to compute the colors associated with the resampled points.

The occupancy map module (314) can generate an occupancy map that describes padding information for each unit. For example, the occupancy image contains a binary map indicating for each cell of the grid whether the cell belongs to the empty space or to the point cloud. In one example, the occupancy map uses binary information that describes for each pixel whether the pixel is padded or not. In another example, the occupancy map uses binary information that describes for each block of pixels whether the block of pixels is padded or not.

The occupancy map generated by the occupancy map module (314) can be compressed using lossless or lossy encoding. The entropy compression module (334) is used to compress the occupancy map when lossless encoding is used. If lossy encoding is used, a video compression module (332) is used to compress the occupancy map.

Note that the patch packing module (308) may leave some empty space between the 2D patches packed in the image frame. Image padding modules (316) and (318) can fill empty space (called padding) to generate image frames that may be suitable for 2D video and image codecs. Image padding is also called background filling, which allows unused space to be filled with redundant information. In some instances, good background fill increases bitrate minimally and does not introduce significant coding distortion around patch boundaries.

The Video Compression Modules (322), (323) and (332) provide 2D compression such as padded geometry images, padded texture images and occupancy maps based on the appropriate video coding standard such as HEVC, VVC. Images can be encoded. In one example, the video compression modules (322), (323), and (332) are individual components that operate separately. Note that in another example, the video compression modules (322), (323) and (332) can be implemented as a single component.

In some examples, the smoothing module (336) is configured to generate a smoothed image of the reconstructed geometry image. The smoothed image can be provided to texture image generation (312). A texture image generator (312) can then adjust the texture image generation based on the reconstructed geometry image. For example, if there is some distortion in the patch shape (eg, geometric shape) during encoding or decoding, the distortion is taken into consideration when generating a texture image to correct the distortion of the patch shape. may

In some embodiments, the group extension (320) is designed to pad pixels around object boundaries with redundant low-frequency content to improve the coding gain as well as the visual quality of the reconstructed point cloud. configured to

A multiplexer (324) can multiplex compressed geometry images, compressed texture images, compressed occupancy maps, and/or compressed auxiliary patch information into the compressed bitstream.

FIG. 4 shows a block diagram of a V-PCC decoder (400) for decoding compressed bitstreams corresponding to point cloud frames, according to some embodiments. In some embodiments, the V-PCC decoder (400) can be used in communication systems (100) and streaming systems (200). For example, the decoder (210) can be configured to operate similarly to the V-PCC decoder (400). The V-PCC decoder (400) receives the compressed bitstream and produces a reconstructed point cloud based on the compressed bitstream.

In the example of Figure 4, the V-PCC decoder (400) includes a demultiplexer (432), video decompression modules (434) and (436), an occupancy map decompression module (438), and an auxiliary patch information decompression module ( 442), a geometry reconstruction module (444), a smoothing module (446), a texture reconstruction module (448) and a color smoothing module (452).

A demultiplexer (432) can receive the compressed bitstream and separate it into a compressed texture image, a compressed geometry image, a compressed occupancy map, and compressed auxiliary patch information.

Video decompression modules (434) and (436) can decode compressed images according to a suitable standard (eg, HEVC, VVC, etc.) and output decompressed images. For example, the video decompression module (434) decodes compressed texture images and outputs decompressed texture images. A video decompression module (436) decodes the compressed geometry image and outputs said decompressed geometry image.

The occupancy map decompression module (438) can decode the compressed occupancy map according to a suitable standard (eg, HEVC, VVC, etc.) and output the decompressed occupancy map.

The auxiliary patch information decompression module (442) can decode auxiliary patch information compressed according to a suitable standard (eg, HEVC, VVC, etc.) and output decompressed auxiliary patch information.

A geometry reconstruction module (444) can receive the decompressed geometry image and generate a reconstructed point cloud geometry based on the decompressed occupancy map and the decompressed auxiliary patch information.

A smoothing module (446) may smooth discrepancies in the edges of the patches. The smoothing procedure aims to mitigate potential discontinuities that can occur at patch boundaries due to compression artifacts. In some embodiments, a smoothing filter may be applied to pixels located on patch boundaries to mitigate distortion that may be caused by compression/decompression.

A texture reconstruction module (448) can determine texture information for points in the point cloud based on the decompressed texture image and the smoothed geometry.

A color smoothing module (452) can smooth color discrepancies. Non-adjacent patches in 3D space are often packed next to each other in 2D video. In some examples, pixel values from non-adjacent patches may be blended by a block-based video codec. The purpose of color smoothing is to reduce visible artifacts that appear at patch boundaries.

FIG. 5 shows a block diagram of a video decoder (510) according to one embodiment of this disclosure. The video decoder (510) can be used with the V-PCC decoder (400). For example, the video decompression modules (434) and (436), the occupancy map decompression module (438) can be configured similarly to the video decoder (510).

A video decoder (510) may include an analyzer (520) for reconstructing symbols (521) from a compressed image, such as an encoded video sequence. These symbol categories contain information used to manage the operation of the video decoder (510). The analyzer (520) can parse/entropy decode the received encoded video sequence. Encoding of an encoded video sequence can follow a video coding technique or standard and can follow various principles including variable length coding, Huffman coding, arithmetic coding with or without context dependence, etc. can. The analyzer (520) extracts from the encoded video sequence a set of at least one subgroup parameter of the subgroups of pixels in the video decoder based on at least one parameter corresponding to the group. be able to. Subgroups can include groups of pictures (GOPs), pictures, tiles, slices, macroblocks, coding units (CUs), blocks, transform units (TUs), prediction units (PUs), and so on. The analyzer (520) can also extract from encoded video sequence information such as transform coefficients, quantization parameter values, motion vectors, and the like.

The analyzer (520) can perform entropy decoding/analysis operations on the video sequence received from the buffer memory to produce symbols (521).

Reconstruction of the symbol (521) can be divided into several different units, depending on the format of the encoded video picture or parts thereof (e.g., inter and intra pictures, inter and intra blocks), and other factors. can contain. Which units are involved and how can be controlled by subgroup control information parsed from the encoded video sequence by the analyzer (520). Such subgroup control information flow between the analyzer (520) and the following units is not shown for clarity.

In addition to the functional blocks already mentioned, the video decoder (510) can be conceptually subdivided into a number of functional units, as described below. In practical implementations operating under commercial constraints, many of these units interact closely with each other and can be at least partially integrated with each other. However, to describe the disclosed subject matter, the following conceptual breakdown into functional units is adequate.

The first unit is the Scaler/Inverse Transform Unit (551). The scaler/inverse transform unit (551) stores the quantized transform coefficients and control information including which transform to use, block size, quantized coefficients, quantized scaling matrix, etc. as symbol(s) (521), Receive from the analyzer (520). The scaler/inverse transform unit (551) may output a block comprising sample values that may be input to the aggregator (555).

In some cases, the output samples of the scaler/inverse transform (551) are intra-coded blocks, i.e., not using prediction information from previously reconstructed pictures, but previously reconstructed of the current picture. Blocks that can use prediction information from other parts. Such prediction information can be provided by an intra-picture prediction unit (552). In some cases, the intra-picture prediction unit (552) uses surrounding already-reconstructed information retrieved from the current picture buffer (558) to generate a block of the same size and shape as the block being reconstructed. do. A current picture buffer (558) buffers, for example, a partially reconstructed current picture and/or a fully reconstructed current picture. The aggregator (555) optionally appends the prediction information generated by the intra prediction unit (552) to the output sample information from the scaler/inverse transform unit (551) on a sample-by-sample basis.

In other cases, the output samples of the scaler/inverse transform unit (551) may relate to inter-coded, potentially motion compensated blocks. In such cases, the motion compensated prediction unit (553) can access the reference picture memory (557) to fetch the samples used for prediction. After motion compensating the samples fetched according to the symbols (521) associated with the block, these samples are converted by the aggregator (555) to the output of the scaler/inverse transform unit (551) (this case, called residual samples or residual signal). The address in the reference picture memory (557) from which the motion compensated prediction unit (553) fetches the prediction samples is the address of the symbol (521) where the motion compensated prediction unit (553) may have, for example, the X, Y, and reference picture components. It can be controlled by the motion vectors available in the mod. Motion compensation may also include interpolation of sample values fetched from reference picture memory (557) when sub-sample accurate motion vectors are used, motion vector prediction mechanisms, and the like.

The output samples of the aggregator (555) may be subject to various loop filtering techniques in a loop filter unit (556). Video compression techniques include the following parameters, controlled by parameters contained in the encoded video sequence (also called encoded video bitstream) and made available to the loop filter unit (556) as symbols (521) from the analyzer (520): In-loop filtering techniques may be included, but may be responsive to meta-information obtained during decoding of earlier (in decoding order) portions of coded pictures or coded video sequences, or previously reconstructed and loop-filtered. It is also possible to respond to sampled values that have been sent.

The output of the loop filter unit (556) can be a sample stream that can be output to the rendering device and stored in the reference picture memory (557) for use in future inter-picture prediction. .

A particular coded picture, once fully reconstructed, can be used as a reference picture for future prediction. For example, when the coded picture corresponding to the current picture is fully reconstructed and the coded picture is identified (eg, by the analyzer (520)) as a reference picture, the current picture buffer (558) stores the reference picture. It can be part of the memory (557) and can reallocate a new current picture buffer before starting reconstruction of the next coded picture.

A video decoder (510) may perform decoding operations according to predetermined video compression techniques in standards such as ITU-T Rec. H.265. An encoded video sequence is defined by the video compression technology being used in the sense that the encoded video sequence conforms to both the syntax of the video compression technology or standard and the profile documented in the video compression technology or standard. or conform to the syntax specified by the standard. Specifically, a profile can select a particular tool from all available tools for a video compression technology or standard as the only tool available under that profile. A requirement for compliance may also be that the complexity of the encoded video sequence is within bounds defined by the level of the video compression technique or standard. In some cases, the level limits the maximum picture size, maximum frame rate, maximum reconstructed sample rate (eg, measured in megasamples per second), maximum reference picture size, and the like. Limits set by a level may in some cases be further constrained by the specification of a hypothetical reference decoder (HRD) and HRD buffer management metadata signaled in the encoded video sequence.

FIG. 6 shows a block diagram of a video encoder (603) according to one embodiment of this disclosure. The video encoder (603) can be used with the V-PCC encoder (300) to compress the point cloud. In one example, the video compression modules (322) and (323) and the video compression module (332) are configured similarly to the encoder (603).

A video encoder (603) can receive images, such as padded geometry images, padded texture images, and produce compressed images.

According to one embodiment, the video encoder (603) encodes the pictures of the source video sequence in real-time or under any other time constraint required by the application to produce an encoded video sequence (compressed images). ). Enforcing the proper encoding rate is a function of the controller (650). In some embodiments, the controller (650) controls and is functionally coupled to other functional units as described below. Couplings are not shown for clarity. Parameters set by the controller (650) include rate control related parameters (picture skip, quantizer, lambda value for rate-distortion optimization techniques, ...), picture size, group of pictures (GOP) layout, maximum motion It can include vector search ranges and the like. The controller (650) may be configured with other suitable functionality for the video encoder (603) optimized for a particular system design.

In some embodiments, the video encoder (603) is configured to operate in an encoding loop. As an oversimplified description, in one example, an encoding loop generates a symbol, such as a symbol stream, based on a source encoder (630) (e.g., input pictures to be encoded and reference pictures). and a (local) decoder (633) embedded in the video encoder (603). The decoder (633) reconstructs the symbols to produce sample data in a manner similar to that which also produces the (remote) decoder (in the video compression techniques considered in the disclosed subject matter, symbols and codes (because any compression to or from the encoded video bitstream is lossless). The reconstructed sample stream (sample data) is input to the reference picture memory (634). Since symbol stream decoding yields bit-accurate results regardless of decoder position (local or remote), the content in the reference picture memory (634) is also bit-accurate between local and remote encoders. Accurate. In other words, the predictor of the encoder "sees" as reference picture samples exactly the same sample values that the decoder "sees" when using prediction during decoding. This basic principle of reference picture synchrony (eg drift resulting when synchrony cannot be maintained due to channel error) is also used in some related techniques.

The operation of the 'local' decoder (633) may be the same as that of a 'remote' decoder, such as the video decoder (510) already described in detail in connection with FIG. However, referring also briefly to FIG. 5, the symbols are available and the encoding/decoding of the symbols into the encoded video sequence by the entropy encoder (645) and analyzer (520) is lossless. Therefore, the entropy decoding part of the video decoder (510) including, and the analyzer (520) may not be fully implemented in the local decoder (633).

The observation that can be made at this point is that any decoder technique other than parsing/entropy decoding present in the decoder must also be present in the corresponding encoder in substantially the same functional form. That is. For this reason, the disclosed subject matter focuses on decoder operations. A description of the encoder techniques can be omitted as they are the inverse of the generically described decoder techniques. Only certain areas require more detailed explanation and are provided below.

In operation, in some examples, the source encoder (630) predictively encodes an input picture with reference to one or more previously encoded pictures from a video sequence, designated as "reference pictures." Encoding motion compensated predictive encoding can be performed. In this way, the encoding engine (632) encodes the difference between the pixelblocks of the input picture and the pixelblocks of the reference pictures that can be selected as prediction references for the input picture.

A local video decoder (633) may decode encoded video data for pictures that may be designated as reference pictures based on the symbols generated by the source encoder (630). The operation of the encoding engine (632) may advantageously be a lossy process. When the encoded video data can be decoded with a video decoder (not shown in FIG. 6), the reconstructed video sequence will usually be a replica of the source video sequence with some errors. The local video decoder (633) may replicate the decoding process that may be performed by the video decoder on the reference pictures and store the reconstructed reference pictures in the reference picture cache (634). In this way, the video encoder (603) locally stores duplicates of reconstructed reference pictures with common content as the reconstructed reference pictures to be retrieved by the far-end video decoder. (no transmission errors).

A predictor (635) can perform a predictive search for the encoding engine (632). That is, for a new picture to be encoded, the predictor (635) uses sample data (as candidate reference pixel blocks) or motion vectors of reference pictures that can serve as good predictive references for the new picture, block shape The reference picture memory (634) can be searched for specific metadata such as. The predictor (635) can operate on a sample block by sample block to find a suitable prediction reference. In some cases, the input picture may have prediction references drawn from multiple reference pictures stored in the reference picture memory (634), as determined by the search results obtained by the predictor (635). can.

The controller (650) can manage the encoding operations of the source encoder (630), including, for example, setting parameters and subgroup parameters used to encode the video data.

The outputs of all the functional units mentioned above may undergo entropy encoding in an entropy encoder (645). An entropy encoder (645) encodes the symbols produced by the various functional units by losslessly compressing the symbols producing a compressed image 643 according to techniques such as Huffman coding, variable length coding, arithmetic coding. converted to a formatted video sequence.

A controller (650) may manage the operation of the video encoder (603). During encoding, the controller (650) can assign each coded picture a particular coded picture format, which can affect the coding technique that can be applied to each picture. For example, pictures are often assigned as one of the following picture types.

Intra pictures (I pictures) may be coded and decoded without using other pictures in the sequence as prediction sources. Some video encodings allow different types of intra pictures, including independent decoder refresh (“IDR”) pictures, for example. Those skilled in the art are aware of these variations of I-pictures and their respective uses and characteristics.

Predicted pictures (P-pictures) may be those that can be coded and decoded using intra-prediction or inter-prediction, which uses at most one motion vector and reference indices to predict the sample values of each block. .

A bi-predictive picture (B-picture) can be coded and decoded using intra- or inter-prediction, which uses at most two motion vectors and reference indices to predict the sample values of each block. could be. Similarly, multiple predicted pictures can use more than two reference pictures and associated metadata for reconstruction of a single block.

A source picture is typically spatially subdivided into multiple sample blocks (e.g., blocks of 4x4, 8x8, 4x8, or 16x16 samples each) and coded block by block. obtain. A block may be predictively coded with reference to other (already coded) blocks, as determined by the coding assignment applied to the block's respective picture. For example, blocks of an I picture may be coded non-predictively or predictively (spatial prediction or intra prediction) with reference to already coded blocks of the same picture. Pixel blocks of P pictures may be predictively coded via spatial prediction or via temporal prediction with reference to one previously coded reference picture. Blocks of B pictures may be predictively coded via spatial prediction or via temporal prediction with reference to one or two previously coded reference pictures.

The video encoder (603) may perform encoding operations according to a predetermined video encoding technique or standard, such as ITU-T Rec.H.265. In its operation, the video encoder (603) can perform various compression operations, including predictive encoding operations that exploit temporal and spatial redundancies within the input video sequence. The encoded video data can thus conform to the syntax specified by the video encoding technique or standard being used.

A video may be in the form of multiple source pictures (images) in time series. Intra-picture prediction (often abbreviated as intra-prediction) exploits spatial correlations in a given picture, while inter-picture prediction exploits (temporal or other) correlations between pictures. In one example, a particular picture being encoded/decoded, called the current picture, is partitioned into blocks. When a block in the current picture is similar to a reference block in a previously encoded and still buffered reference picture in the video, the block in the current picture is coded by a vector called a motion vector. can do. A motion vector refers to a reference block within a reference picture and can have a third dimension that identifies the reference picture if multiple reference pictures are used.

In some embodiments, bi-prediction techniques may be used for inter-picture prediction. According to bi-prediction techniques, two reference pictures are used, such as a first reference picture and a second reference picture, both of which precede the current picture in the video in decoding order (but display order). may be past and future, respectively). A block in the current picture is coded by a first motion vector pointing to a first reference block in a first reference picture and a second motion vector pointing to a second reference block in a second reference picture. can be A block can be predicted by a combination of a first reference block and a second reference block.

In addition, merge mode techniques can be used for inter-picture prediction to improve coding efficiency.

According to some embodiments of the present disclosure, prediction, such as inter-picture prediction and intra-picture prediction, is performed on a block-by-block basis. For example, according to the HEVC standard, pictures in a sequence of video pictures are partitioned into Coding Tree Units (CTUs) for compression, and a CTU within a picture can be 64x64 pixels, 32x32 pixels, or 16 pixels. have the same size, such as x16 pixels. In general, a CTU contains three coding treeblocks (CTBs), one luma CTB and two chroma CTBs. Each CTU can be recursively quadtree split into one or more coding units (CUs). For example, a CTU of 64x64 pixels can be divided into one CU of 64x64 pixels, or four CUs of 32x32 pixels, or 16 CUs of 16x16 pixels. In one example, each CU is analyzed to determine the CU's prediction type, such as an inter-prediction type or an intra-prediction type. A CU is divided into one or more prediction units (PUs) according to temporal and/or spatial predictability. In general, each PU contains a luma prediction block (PB) and two chroma PBs. In one embodiment, a prediction operation in encoding (encoding/decoding) is performed in units of prediction blocks. Using a luminance prediction block as an example of a prediction block, the prediction block contains a matrix of pixel values (e.g., luminance values) such as 8x8 pixels, 16x16 pixels, 8x16 pixels, 16x8 pixels, etc. .

A G-PCC model can separately compress geometric information and associated attributes such as color or reflectance. Geometry information, which is the 3D coordinates of a point cloud, can be encoded by an octree decomposition of its occupancy information. Attributes, on the other hand, can be compressed based on the reconstructed geometry using predictive and lifting techniques. The octree partitioning process will be explained with reference to FIGS. 7 to 13, for example.

FIG. 7 shows a block diagram of a G-PCC decoder (800) applied during the G-PCC decomposition process according to one embodiment. The decoder (800) can be configured to receive the compressed bitstream and perform point cloud data decompression to decompress the bitstream and generate decoded point cloud data. In one embodiment, the decoder (800) includes an arithmetic decoding module (810), an inverse quantization module (820), an octree decoding module (830), an LOD generation module (840), an inverse quantization module (850). , and an inverse interpolation-based prediction module (860).

As shown, a compressed bitstream (801) may be received at an arithmetic decoding module (810). The arithmetic decoding module (810) is configured to decode the compressed bitstream (801) to obtain quantized prediction residuals (if generated) and occupancy codes (or symbols) for the point cloud. . The octree decoding module (830) is configured to generate quantized positions of points in the point cloud according to the occupancy code. The inverse quantization module (850) is configured to generate reconstructed positions of points in the point cloud based on the quantized positions provided by the octree decoding module (830).

The LOD generation module (840) is configured to reconstruct the points into different LODs based on the reconstructed positions and determine the LOD-based order. The inverse quantization module (820) is configured to generate a reconstructed prediction residual based on the quantized prediction residual received from the arithmetic decoding module (810). The Inverse Interpolation Based Prediction module (860) performs attribute prediction processing to obtain the reconstructed prediction residuals received from the Inverse Quantization module (820) and the LOD based order received from the LOD Generation module (840). is configured to generate reconstructed attributes of points in the point cloud based on .

Further, the reconstructed attributes generated from the inverse interpolation-based prediction module (860), along with the reconstructed positions generated from the inverse quantization module (850), in one example, are output from the decoder (800). corresponding to the decoded point cloud (or reconstructed point cloud) (802).

FIG. 8 shows a block diagram of a G-PPC encoder (700) according to one embodiment. The encoder (700) may be configured to receive point cloud data, compress the point cloud data, and generate a bitstream carrying the compressed point cloud data. In one embodiment, the encoder (700) includes a position quantization module (710), a duplicate point removal module (712), an octree encoding module (730), an attribute transfer module (720), a level of detail (LOD ) generation module (740), interpolation-based prediction module (750), residual quantization module (760), and arithmetic coding module (770).

As shown, an input point cloud (701) can be received at an encoder (700). The positions (eg, 3D coordinates) of the point cloud (701) are provided to the quantization module (710). A quantization module (710) is configured to quantize the coordinates to generate quantized positions. A duplicate point removal module (712) is configured to receive the quantized positions and perform filtering to identify and remove duplicate points. An octree encoding module (730) receives the filtered positions from the remove duplicate points module (712) and performs an octree-based encoding process to generate a sequence of occupancy describing a 3D grid of voxels. Configured to generate code (or symbols). Occupancy codes are provided to the arithmetic coding module (770).

An attribute transfer module (720) receives attributes of the input point cloud and performs an attribute transfer process to determine attribute values for each voxel when multiple attribute values are associated with each voxel. Configured. Attribute transfer processing can be performed on the reordered points output from the octree encoding module (730). Post-transfer attributes are provided to an interpolation-based prediction module (750). The LOD generation module (740) is configured to operate on the reordered points output from the octree encoding module (730) and reorganize the points into different LODs. LOD information is provided to an interpolation-based prediction module (750).

The interpolation-based prediction module (750) processes the points according to the LOD-based order indicated by the LOD information from the LOD generation module (740) and the transferred attributes received from the attribute transfer module (720) to generate prediction residuals to generate The residual quantization module (760) is configured to receive prediction residuals from the interpolation-based prediction module (750) and perform quantization to produce quantized prediction residuals. Quantized prediction residuals are provided to the arithmetic coding module (770). The arithmetic coding module (770) receives the occupied codes, the candidate indices (if used) from the octree coding module (730), the quantized prediction residuals from the interpolation-based prediction module (750), and It is configured to receive other information and perform entropy coding to further compress the received value or information. This can generate a compressed bitstream (702) that carries the compressed information. The bitstream (702) may be transmitted or otherwise provided to a decoder that decodes the compressed bitstream, or may be stored in a storage device.

Interpolation-based prediction module (750) and inverse interpolation-based prediction module (860) configured to implement the attribute prediction techniques disclosed herein are similar to those shown in FIGS. or included in other decoders or encoders that may have a different structure. Further, the encoder (700) and decoder (800) may be included in the same device or, in various examples, separate devices.

In various embodiments, the encoder (300), decoder (400), encoder (700), and/or decoder (800) can be implemented in hardware, software, or a combination thereof. can. For example, the encoder (300), decoder (400), encoder (700), and/or decoder (800) may be application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), etc. It can be implemented using processing circuitry such as one or more integrated circuits (ICs) that operate with or without software. In another example, the encoder (300), decoder (400), encoder (700), and/or decoder (800) are stored in a non-volatile (or non-transitory) computer-readable storage medium. It can be implemented as software or firmware containing instructions. The instructions, when executed by a processing circuit, such as one or more processors, instruct the processing circuit to operate the encoder (300), decoder (400), encoder (700), and/or decoder (800). ) functions.

A point cloud partition defined by a 3D cube symmetrically along all axes (e.g., x, y and z axes) is known as an Octree (OT) partition in point cloud compression (PCC). Can yield 8 subcubes. OT partitioning is similar to binary tree (BT) partitioning in one-dimensional space and quadtree (QT) partitioning in two-dimensional space. The concept of OT partitioning can be illustrated in Figure 9, where a solid 3D cube (900) can be partitioned into 8 smaller equal sized cubes with dashed lines. As shown in Figure 9, the octree partitioning technique can divide a 3D cube (900) into eight smaller, equal-sized cubes 0-7.

In an octree partitioning technique (eg, in TMC13), if an octree geometry codec is used, geometry encoding proceeds as follows. First, a bounding box B aligned with the cube axes can be defined by its two endpoints (0,0,0) and ( ^2d , ^2d , ^2d ), where ^2d is the bounding box B , and d can be encoded into the bitstream. Therefore, all points inside the defined bounding box B can be compressed.

An octree structure can then be constructed by subdividing the bounding box B recursively. At each stage, the cube can be subdivided into eight subcubes. The size of the subcube after k (k≦d) iterative subdivisions can be (2 ^d−k , 2 ^d−k , 2 ^d−k ). Then, an occupancy code such as 8 A bitcode can be generated by associating a 1-bit value with each subcube. Only filled subcubes with a size greater than 1 (ie non-voxels) can be further subdivided. The occupancy code for each cube can then be compressed by an arithmetic encoder.

The decoding process can begin by reading from the bitstream dimension of the bounding box B. The same octree structure can then be constructed by subdividing the bounding box B according to the decoded occupation code. An example of a two-level OT partition and corresponding occupancy code can be shown in FIG. 10, where the shaded cubes and nodes indicate that the cubes and nodes are occupied by points.

FIG. 10 shows an example of an octree partition (1010) and an octree structure (1020) corresponding to the octree partition (1010), according to some embodiments of the present disclosure. FIG. 10 shows two levels of partitioning in an octree partitioning (1010). The octree structure (1020) includes nodes (N0) corresponding to the cubic boxes for the octree partition (1010). At the first level, the cubic box is partitioned into eight sub-cubic boxes numbered 0-7 according to the numbering technique shown in FIG. The occupancy code for the partition of node N0 is "10000001" in binary, which means that the first sub-cubic box represented by nodes N0-0 and the eighth sub-cubic box represented by nodes N0-7 point Including the points in the group and indicating that the other subcubic boxes are empty.

Then, in the second level partitioning, the first sub-cubic box (represented by nodes N0-0) and the eighth sub-cubic box (represented by nodes N0-7) are each divided into eight octahedral boxes. further subdivided into subdivisions. For example, the first sub-cubic box (represented by nodes N0-0) is partitioned into eight smaller sub-cubic boxes numbered 0-7 according to the numbering technique shown in FIG. The occupancy code for the partition of node N0-0 is "00011000" in binary, which corresponds to the fourth smaller subcubic box (represented by nodes N0-0-3) and the fifth smaller subcubic box ( represented by nodes N0-0-4) contain points in the point cloud and other smaller subcubic boxes are empty. At the second level, the seventh sub-cubic box (represented by nodes N0-7) is similarly partitioned into eight smaller sub-cubic boxes, as shown in FIG.

In the example of Figure 10, nodes corresponding to non-empty cubic spaces (e.g., cubic boxes, subcubic boxes, smaller subcubic boxes, etc.) are shaded in gray and referred to as shaded nodes.

In the original TMC13 design, for example, as mentioned above, the bounding box B could be constrained to be a cube with the same size for all dimensions, so the OT partition was such that the subcubes were all It can be done for all subcubes with each node being half the size for the dimension. OT partitioning can be performed recursively until the size of the subcube reaches one. However, segmentation in such a manner is not efficient in all cases, especially if the points are unevenly distributed in the 3D scene (or 3D space).

One extreme case could be a 2D plane in 3D space, where all points can be placed on the xy plane in 3D space, and the z-axis variation can be zero. In such cases, the OT partitioning performed on cube B as a starting point may waste a large amount of bits to represent the occupancy information in the z direction, which is redundant and not useful. In practical applications, the worst case may not occur often. However, it is common to have point clouds with less variance in one direction compared to other directions. As shown in Figure 11, the point cloud sequence named "ford_01_vox1mm" in TMC13 can have principal components in the x and y directions. In fact, many point cloud data generated from lidar systems can have the same properties.

For quadtree and binary tree (QtBt) partitions, the bounding box B may not be restricted to a cube, instead the bounding box B may be an arbitrary size rectangular cuboid that better fits the shape of the 3D scene or object be able to. In implementations, the size of the bounding box B can be expressed as a power of 2, eg, ( ^2dx , ^2dy , ^2dz ).

Since the bounding box B may not be a perfect cube, in some cases the nodes may not (or may not) be partitioned along all directions. A partition is a typical OT partition if the partition is performed in all three directions. A segmentation is a 3D QT segmentation if segmentation is performed in two of the three directions. If the segmentation is performed in only one direction, the segmentation is a 3D BT segmentation. Examples of QT and BT in 3D are shown in Figures 12 and 13, respectively.

As shown in FIG. 12, a 3D cube 1201 can be partitioned into four subcubes 0, 2, 4, and 6 along the xy axes. The 3D cube 1202 can be partitioned into four subcubes 0, 1, 4 and 5 along the xz axis. The 3D cube 1203 can be partitioned into four subcubes 0, 1, 2 and 3 along the yz axis. In FIG. 13, a 3D cube 1301 can be partitioned into two sub-cubes 0 and 4 along the x-axis. The 3D cube 1302 can be partitioned into two sub-cubes 0 and 2. The 3D cube 1303 can be partitioned into two sub-cubes 0 and 1.

Two parameters (ie, K and M) can be applied to define the conditions for implicit QT and BT compartments in TMC13. The first parameter K (0≤K≤max( _dx , _dy , _dz )-min( _dx , _dy , _dz )) is the implicit QT segmentation that can be performed before the OT segmentation. and maximum time for BT segment can be defined. The second parameter M (0 ≤ M ≤ min(d _x , d _y , d _z )) can define the minimum size of the implied QT and BT segments, if all dimensions are greater than M only indicates that implicit QT and BT divisions are allowed.

More specifically, the first K partitions can follow the rules of Table I, and the partitions after the first K partitions can follow the rules of Table II. If none of the conditions listed in the table are met, an OT division can be performed.

In one embodiment, the bounding box B is

can have a size of Without loss of generality, we can apply the condition 0<d _x ≦d _y ≦d _z to the bounding box B. Based on the conditions, at the first K ( _K≤dz - _dx ) depths, an implicit BT segmentation can be performed along the z-axis and an implicit QT segmentation can be performed along the y-z-axis. can be performed according to Table I. The subnode size is

and the values of δ _y and δ _z (δ _z ≧δ _y ≧0) can depend on the value of K. Furthermore, the OT partition can be run d _x −M times, so that the remaining subnodes are

can have a size of Then, according to Table II, implicit BT segments can be performed δ _z -δ _y times along the z axis, followed by δ _y implicit QT segments along the yz axis. be able to. Therefore, the remaining nodes can have a size of 2 ^(M,M,M) . Therefore, the OT partition can be performed M times to arrive at the smallest unit.

QtBt partitioning provides implicit rules for how to apply the partitioning of a given cuboid by switching between octree, quadtree, and binary tree at each level of node decomposition. After the initial decomposition of K levels via QtBt partitioning according to a rule (eg, Table I), another round of QtBt partitioning can be performed according to another rule (eg, Table II). In the above process, if none of the conditions in the rules are met, octree decomposition (or octree partitioning) can be applied.

Implicit rules can affect the validity of QtBt as follows. (1) For point cloud data with roughly symmetric cuboidal bounding boxes along the x, y, and z dimensions, the QtBt partition is performing an Ot (octree) decomposition at all levels with a related method (e.g., the implied QtBt partition) and (2) for point cloud data with highly asymmetric cuboidal bounding boxes along the x, y, and z dimensions, the QtBt partition is It shows the coding gain by skipping the transmission of unnecessary occupation information during decomposition.

In the current QtBt division, specific restrictions can be placed as follows. First, the QtBt partition can always force the use of asymmetric bounding boxes, which may not be useful or even counterproductive if the point cloud has nearly symmetrical bounding boxes. be. Second, Table I with parameter K can be reduced to a larger dimensionality according to the rule by implementing Qt/Bt partitioning instead of Ot partitioning. However, when the bounding box is symmetrical, Table I with parameter K may initially not allow Qt or Bt partitions. Third, Table II can be applied after K divisions and activations above, once the minimum dimension of the subbox reaches M. Therefore, Table II can be reduced by rule to larger dimensions until all dimensions are equal to M. Fourth, the current implicit rule (or implicit QtBt partition) can always require octree decomposition after the first (maximum) K levels until the current QtBt partition reaches level M. . In other words, the current QtBt partition may not allow choosing any Qt/Bt/Ot partition between two level points.

Multiple methods are provided in the present disclosure. The method provides a simplification of QtBt design (eg, implicit QtBt partitioning) in TMC13 for typical use cases, eg, based on the discussion above. The method also allows a more flexible partitioning method, for example by explicitly signaling the node decomposition type at each level.

In one embodiment, a first partitioning method (or simplified QtBt partitioning) can be provided. The first partitioning method can be a special case of implicit QtBt partitioning, which can be applied to datasets with highly asymmetric bounding boxes by setting K=0 & M=0. can be done. The first partitioning method can simplify the QtBt design (eg, QtBt partitioning) and can also provide typical case coding benefits as described above.

Compared to the QtBt partition within TMC13, the first partition method may include the following features: (1) the implicit enable flag (e.g., implicit_qtbt_enabled_flag) within the QtBt partition within TMC13 may be removed; can. (2) An asymmetric bounding box flag (eg, asymmetric_bbox_enabled_flag) can be introduced to enable the use of asymmetric bounding boxes. In one example, the asymmetric bounding box flag is set to a value such as 0 (also referred to as the secondary value) for symmetric or nearly symmetric bounding box data, and a value such as 1 (also referred to as the secondary value) for highly asymmetric bounding box data. (also called a value of 1). (3) If the asymmetric bounding box flag is the first value, the implicit QtBt rule with K = 0 & M = 0 (e.g., Table I and Table II) can be applied. Otherwise, if the asymmetric bounding box flag is the second value, the first partitioning method may perform octree decomposition (or octree partitioning).

According to the first partitioning method, apply the implicit QtBt rule shown in Table II with M=0 to skip transmitting unnecessary occupancy information along some dimensions as shown in Table III. can do.

In one embodiment, a second partitioning method (or explicit QtBt partitioning) may be provided to send explicit signaling of splitting decisions. Explicit signaling can be provided in contrast to the use of fixed implicit rules in the current QtBt division.

A second partitioning method can include the following features: (1) while an explicit QtBt enabled flag (e.g., explicit_qtbt_enabled_flag) can be introduced to enable/disable explicit split decision signaling; , we can still introduce the asymmetric bounding box flag from the first partitioning method. (2) When the Explicit QtBt Valid Flag is set to a value such as 0 (or a second value), the second partitioning method reverts to (or may be equal to) the first partitioning method described above. Therefore, if the asymmetric bounding box flag (e.g. is asymmetric_bbox_enabled_flag) is a value (or the first value) such as 1, then when the node decomposition level reaches 0 (or the last level), K=0 & Implicit QtBt rules with M=0 (eg, Tables I and II) can be applied. If the asymmetric bounding box flag is a second value, the second partitioning method may perform octree decomposition (or octree partitioning). In one embodiment, when the asymmetric bounding box flag is not used and the explicit QtBt valid flag is set to a second value (e.g., 0), the second partitioning method uses octet for all levels. Tree decomposition (or octree partitioning) can be applied. (4) When the explicit QtBt valid flag is set to the first value (e.g. 1), always octree until the level reaches 0 (or the last level) as mentioned in the first partitioning method Instead of performing splitting, a 3-bit signal can be sent at each octree level to indicate whether to split along each of the x, y, and z axes. Thus, a 3-bit signal can indicate whether Bt partitioning, Qt partitioning, or Ot partitioning can be applied at each of the octree levels. In some embodiments, implicit QtBt rules within TMC13 (eg, Tables I and II) can be applied to determine the 3-bit signal at each octree level.

When the explicit QtBt valid flag is set to the first value in the second partitioning method, Ot/Qt/Bt partitioning is allowed in any way along the way, so the maximum possible total number of partitions is the maximum node Note that it can be three times the difference between the depth and the minimum node depth.

In one embodiment of the present disclosure, a third partitioning method (or explicit QtBt type 2 partitioning) may be provided to send explicit signaling of splitting decisions. Explicit signaling can be provided in contrast to the use of fixed implicit rules in the current QtBt division (eg Tables I and II). A third partitioning method may include the following features compared to the current QtBt partitioning: (1) An explicit QtBt enabled flag (e.g., explicit_qtbt_enabled_flag) enables/disables explicit split decision signaling; To do so, the implicit QtBt enabled flag (eg, implicit_qtbt_enabled_flag) in the QtBt partition within TMC13 can be replaced. (2) To enable/disable the use of asymmetric bounding boxes, set the asymmetric bounding box flag (e.g. asymmetric_bbox_enabled_flag) additionally only when the explicit QtBt enabled flag has a value such as 1 (or the first value) can be signaled. When the asymmetric bounding box flag is the first value, the dimensions (i.e. size) of the asymmetric bounding box along x, y, and z can be further signaled as opposed to the maximum of the three . Therefore, the asymmetric bounding box flag can be 0 (e.g., second value) for symmetric or nearly symmetric bounding box data, first value (e.g., 1) for highly asymmetric bounding box data, and so on. can be set to a value. (3) When the explicit QtBt valid flag is set to the first value, a 3-bit signal at the octree level to indicate whether to split along each of the x-, y-, and z-axes. (or octree partition level). In one embodiment, implicit QtBt rules within TMC 13 (eg, Tables I and II) may be applied to determine the 3-bit signal for each octree level. In another embodiment, other splitting rules can be applied to determine the 3-bit signal for each octree level. Other splitting rules facilitate the encoding of octatree occupation information and may further take into account characteristics of the data (eg, octatree occupation information) or date acquisition mechanisms. (4) when the explicit QtBt valid flag is set to a second value (e.g. 0), the third partitioning method applies octree decomposition (octree partitioning) for all levels can do.

When the explicit QtBt valid flag is set to the first value in the third partitioning method, Ot/Qt/Bt partitioning is allowed in any way along the way, so the maximum possible total number of partitions is the maximum node Note that it can be three times the difference between the depth and the minimum node depth.

In one embodiment of the present disclosure, a fourth partitioning method (or flexible QtBt division) can be provided. In contrast to the use of fixed implicit rules in the current QtBt division, additional signaling can be provided (eg Tables I and II).

A fourth segmentation method may include: (1) A QtBt enabled flag (e.g., qtbt_enabled_flag) can be applied to replace the implicit QtBt enabled flag within the QtBt partition within TMC13 to indicate the use of the QtBt partition with greater flexibility. (2) When the QtBt valid flag is set to a value such as 1, a QtBt type flag (eg, qtbt_type_flag) can be additionally signaled. (3) If the QtBt type flag is set to a value such as 0, the current implicit QtBt scheme (eg, Tables I and II) can be applied. Additionally, an asymmetric bounding box flag (eg, asymmetric_bbox_enabled_flag) can be further signaled to selectively enable/disable the use of asymmetric bounding boxes. In one embodiment, when the asymmetric bounding box flag is set to a value such as 1, the dimensions (i.e., size) of the asymmetric bounding box along x, y, and z are set to can be signaled. In another embodiment, if the asymmetric bounding box flag is not signaled, the asymmetric bounding box can always be used.

A fourth segmentation method can also include: (4) If the QtBt type flag is a value such as 1, a 3-bit signal may be sent to each of the octree levels to indicate whether to split along each of the x, y, and z axes. can. In one embodiment, implicit QtBt rules within TMC 13 (eg, Tables I and II) may be applied to determine the 3-bit signal for each octree level. In another embodiment, other splitting rules can be applied to determine the 3-bit signal for each octree level. Other splitting rules facilitate the encoding of octatree occupation information and may further take into account characteristics of the data (eg, octatree occupation information) or date acquisition mechanisms. In one embodiment, an asymmetric bounding box flag can be further signaled to selectively enable/disable the use of asymmetric bounding boxes. When the asymmetric bounding box flag is a value such as 1, the dimensions (ie, size) of the asymmetric bounding box along x, y, and z can be signaled as opposed to the maximum of the three values. In another embodiment, the asymmetric bounding box flag may not be signaled and the asymmetric bounding box may always be used. (5) If the QtBt valid flag is set to a value such as 0, the fourth partitioning method can apply octree decomposition (or octree partitioning) for all levels.

When the explicit QtBt valid flag is set to a value such as 1 in the fourth partitioning method, Ot/Qt/Bt partitioning is allowed in any way along the way, so the maximum possible total number of partitions is the maximum node Note that it can be three times the difference between the depth and the minimum node depth.

The above techniques can be implemented in a video encoder or decoder adapted for point cloud compression/decompression. The encoder/decoder may be implemented in hardware, software, or any combination thereof, and the software, if present, may be stored in one or more non-transitory computer-readable media. . For example, each of the method (or embodiments), encoder, and decoder may be implemented by processing circuitry (eg, one or more processors or one or more integrated circuits). In one example, one or more processors execute a program stored on a non-transitory computer-readable medium.

Figures 14 and 15 are flowcharts outlining processes (1400) and (1500) according to embodiments of the present disclosure. Processes (1400) and (1500) can be used during the point cloud decoding process. In various embodiments, the processes (1400) and (1500) are processing circuits in the terminal device (110), processing circuits that perform the functions of the encoder (203) and/or the decoder (201), encoding processing circuitry, such as processing circuitry that performs the functions of the detector (300), the decoder (400), the encoder (700), and/or the decoder (800). In some embodiments, the processes (1400) and (1500) can be implemented in software instructions such that when the processing circuitry executes the software instructions, the processing circuitry executes the processes (1400) and (1500) respectively. Execute.

As shown in FIG. 14, the process (1400) starts from (S1401) and proceeds to (S1410).

At (S1410), first signaling information may be received from an encoded bitstream for a point cloud that includes a set of points in three-dimensional (3D) space. The first signaling information may indicate segmentation information of the point cloud.

At (S1420), the second signaling information can be determined based on the first signaling information indicating the first value. The second signaling information may indicate the partitioning mode of the set of points in 3D space.

At (S1430), a partitioning mode of the set of points in 3D space may be determined based on the second signaling information. The process (1400) can then proceed to (S1440) and the point cloud can then be reconstructed based on the segmentation mode.

In some embodiments, the partitioning mode can be determined to be a predetermined quadtree and binary tree (QtBt) partition based on second signaling information that is a second value.

The process (1400) may receive third signaling information indicating that the 3D space is an asymmetric cuboid. The dimensions of the 3D space signaled along the x, y, and z directions can be determined based on the first value, the third signaling information.

In some embodiments, 3-bit signaling information can be determined for each of the multiple partitioning levels in the partitioning mode based on the second signaling information being the first value. The 3-bit signaling information for each of the multiple partitioning levels can indicate partitioning directions along the x, y, and z directions for the respective partitioning level in partitioning mode.

In some embodiments, the 3-bit signaling information can be determined based on the dimensionality of the 3D space.

In the process (1400), a partitioning mode can be determined based on the second value of the first signaling information, the partitioning mode is determined based on the respective octree partitioning for each of the plurality of partitioning levels in the partitioning mode. can include

As shown in FIG. 15, the process (1500) starts from (S1501) and proceeds to (S1510).

At (S1510), first signaling information may be received from an encoded bitstream for a point cloud that includes a set of points in three-dimensional (3D) space. The first signaling information may indicate segmentation information of the point cloud.

At (S1520), a partitioning mode of the set of points in 3D space may be determined based on the first signaling information, and the partitioning mode may include multiple partitioning levels.

At (S1530), the point cloud may then be reconstructed based on the segmentation mode.

In some embodiments, the 3-bit signaling information for each of the multiple partitioning levels in the partitioning mode can be determined based on a first value of the first signaling information, and The 3-bit signaling information for each can indicate the partition direction along the x, y, and z directions for each partition level in partition mode.

In some embodiments, the 3-bit signaling information can be determined based on the dimensionality of the 3D space.

In some embodiments, the partitioning mode determines each of the plurality of partitioning levels in the partitioning mode to include a respective octree partition based on the first signaling information being the second value. be able to.

The process (1500) may further receive second signaling information from the encoded bitstream for the point cloud. The second signaling information is such that when the second signaling information is the first value, the 3D space is an asymmetric rectangular parallelepiped, and when the second signaling information is the second value, the 3D space is a symmetrical rectangular parallelepiped It can be shown that

In some embodiments, based on the first signal information indicative of the second value and the second signal information indicative of the first value, the partition mode determines the first partition at the plurality of partition levels of the partition mode. Each of the levels can be determined to contain a respective octree partition. The partition type and partition direction for the last partition level of the multiple partition levels in the partition mode are shown in the table below.

where d _x , d _y , and d _z are the log2 sizes of 3D space in the x, y, and z directions, respectively.

The process (1500) can determine second signaling information based on first signaling information indicative of a first value. The second signaling information indicates that the 3D space is an asymmetric cuboid when the second signaling information indicates the first value, and the 3D space is a symmetric cuboid when the second signaling information indicates the second value It can be shown that Additionally, the dimensions of the 3D space signaled along the x, y, and z directions can be determined based on second signaling information indicative of the first value.

As noted above, the techniques described above may be implemented as computer software using computer-readable instructions and physically stored on one or more computer-readable media. For example, FIG. 16 illustrates a computer system (1800) suitable for implementing certain embodiments of the disclosed subject matter.

Computer software may be encoded using any suitable machine code or computer language, is subject to assembly, compilation, linking, or similar mechanisms, and is processed by one or more computer central processing units (CPUs), graphics processing, and so on. Create code containing instructions that can be executed directly by a device such as a GPU, or through interpretation, microcode execution, etc.

The instructions can be executed on various types of computers or components thereof including, for example, personal computers, tablet computers, servers, smart phones, gaming devices, Internet of Things devices, and the like.

The components shown in FIG. 16 for computer system (1800) are exemplary in nature and are not intended to suggest any limitation as to the scope of use or functionality of the computer software implementing embodiments of the present disclosure. No configuration of components should be interpreted as having any dependency or requirement relating to any or combination of components illustrated in the exemplary embodiment of computer system (1800).

The computer system (1800) may include certain human interface input devices. Such human interface input devices include, for example, tactile input (e.g. keystrokes, swipes, data glove movements), audio input (e.g. voice, clapping), visual input (e.g. gestures), olfactory input (e.g. (not shown)). Audio (speech, music, environmental sounds, etc.), images (scanned images, photographic images obtained from still image cameras, etc.), video (2D video, 3D video including 3D video, etc.) using human interface devices ), etc., that are not necessarily directly related to conscious human input.

Input human interface devices include keyboard (1801), mouse (1802), trackpad (1803), touch screen (1810), data glove (not shown), joystick (1805), microphone (1806), scanner (1807). , may include one or more (only one of each) of the cameras (1808).

The computer system (1800) may also include certain human interface output devices. Such human interface output devices can stimulate the senses of one or more human users by, for example, tactile output, sound, light, and smell/taste. Such a human interface output device may be a tactile output device such as a touch screen (1810), a data glove (not shown), or haptic feedback via a joystick (1805), but a haptic feedback device that does not function as an input device. audio output devices (e.g. speakers (1809), headphones (not shown)), visual output devices (e.g. screens (1810) including CRT screens, LCD screens, plasma screens, OLED screens). , each with or without touch screen input capability, each with or without tactile feedback capability, some of which may provide two-dimensional visual output or three-dimensional output via means such as stereo output. May be capable of outputting super power; may include virtual reality glasses (not shown), holographic displays, and smoke tanks (not shown), and printers (not shown).

The computer system (1800) also includes optical media (1821) including CD/DVD ROM/RW (1820) having media such as human accessible storage devices and their associated media, such as CD/DVD, thumb drives (1822), removable hard drives or solid state drives (1823), legacy magnetic media such as tapes and floppy disks (not shown), dedicated ROM/ASIC/PLD-based devices such as security dongles (not shown) and so on.

Those skilled in the art should also understand that the term "computer-readable medium" as used in connection with the subject matter disclosed herein does not encompass transmission media, carrier waves, or other transitory signals.

Computer system (1800) may also include interfaces to one or more communication networks. Networks can be, for example, wireless, wired, or optical. Networks can also be local, wide area, metropolitan, vehicular and industrial, real-time, delay tolerant, and the like. Examples of networks include local area networks such as Ethernet and WLAN; cellular networks including GSM, 3G, 4G, 5G, LTE, etc.; Networks, vehicles including CANBus and industrial use. A particular network generally requires an external network interface adapter attached to a particular general purpose data port or peripheral bus (1849), such as the USB port of a computer system (1800). Others are generally integrated into the core of the computer system (1800) by attachment to a system bus as described below (eg, an Ethernet interface to a PC computer system or a cellular network interface to a smartphone computer system). Using any of these networks, the computer system (1800) can communicate with other entities. Such communication may be, for example, unidirectional, receive only (e.g. broadcast TV), or unidirectional transmit only (e.g. CANbus to a particular CANbus device) to other computer systems using local or wide area digital networks. ), or bi-directional. Specific protocols and protocol stacks may be used on each of those networks and network interfaces, as described above.

The aforementioned human interface devices, human access storage devices, and network interfaces can be attached to the core (1840) of the computer system (1800).

The core (1840) includes one or more Central Processing Units (CPUs) (1841), Graphics Processing Units (GPUs) (1842), Field Programmable Gate Areas (FPGAs) (1843), Special programmable processing units in the form of hardware accelerators (1844) can be included. These devices include read-only memory (ROM) (1845), random-access memory (1846), internal mass storage such as internal non-user-accessible hard drives, SSDs, etc. (1847), along with the system bus (1848). may be connected via In some computer systems, the system bus (1848) may be accessible in the form of one or more physical plugs to allow expansion by additional CPUs, GPUs, etc. Peripherals can be attached directly to the core's system bus (1848) or through a peripheral bus (1849). Peripheral bus architectures include PCI, USB, and the like.

The CPU (1841), GPU (1842), FPGA (1843), and accelerator (1844) are capable of executing specific instructions that can be combined to form the computer code described above. The computer code can be stored in ROM (1845) or RAM (1846). Migration data can also be stored in RAM (1846), while persistent data can be stored, for example, in internal mass storage (1847). Fast storage and retrieval to any of the memory devices should be closely associated with one or more CPU (1841), GPU (1842), mass storage (1847), ROM (1845), RAM (1846), etc. can be made possible through the use of cache memory that allows

The computer-readable medium can have computer code for performing various computer-implemented operations. The media and computer code may be those specially designed and constructed for the purposes of the present disclosure, or they may be of the types well known and available to those having skill in the computer software arts.

By way of example, and not limitation, a computer system (1800) having an architecture, particularly a core (1840), is a processor (CPU, GPU, FPGA, (including accelerators, etc.). Such computer-readable media include user-accessible mass storage as described above, as well as core (1840) specific storage of a non-transitory nature such as core internal mass storage (1847) or ROM (1845). can be a medium associated with Software implementing various embodiments of the present disclosure may be stored in such devices and executed by the core (1840). A computer-readable medium may include one or more memory devices or chips, depending on particular needs. The software asks the core (1840), and specifically the processors (including CPU, GPU, FPGA, etc.) within it, to define data structures stored in RAM (1846) and to perform software-defined operations. Certain processes or portions of certain processes described herein may be performed, including modifying such data structures in accordance with. Additionally or alternatively, the computer system may provide functionality as a result of logic embodied in hard-wired or otherwise circuits (e.g., Accelerator (1844)), instead of software. or in conjunction with software to perform certain processes or certain portions of certain processes described herein. References to software can encompass logic, and vice versa, where appropriate. References to computer readable media may optionally include circuits (such as integrated circuits (ICs)) that store software for execution, circuits embodying logic for execution, or both. can. This disclosure encompasses any suitable combination of hardware and software.

Although this disclosure has described several exemplary embodiments, there are alterations, permutations, and various alternative equivalents that fall within the scope of this disclosure. Accordingly, one skilled in the art may devise numerous systems and methods not expressly shown or described herein that embody the principles of the present disclosure and thus fall within its spirit and scope. Understand what you can do.

100 communication systems
105 Networks, Sensors
110 terminal equipment
120 terminal equipment
150 networks
200 streaming system
201 point cloud source, decoder
202 point cloud
203 Encoder
204 point cloud
205 Streaming Server
206 Client Subsystem
207 point cloud
209 point cloud
210 Decoder
211 point cloud
212 Rendering Equipment
213 Acquisition Subsystem
220 Electronics
230 Electronics
300 encoder
304 patch information module
306 patch generation module
308 patch packing module
310 Geometry Image Generation Module
312 Texture Image Generation Module
314 Occupancy Map Module
316 Image Padding Module
320 group expansion module
322 video compression module
323 video compression module
324 multiplexer
332 video compression module
334 Entropy Compression Module
336 Smoothing Module
338 Auxiliary Patch Information Compression Module
400 Decoder
432 Demultiplexer
434 video decompression module
436 video decompression module
438 Occupancy map decompression module
442 Auxiliary patch information decompression module
444 Geometry Reconstruction Module
446 Smoothing Module
448 Texture Reconstruction Module
452 color smoothing module
510 video decoder
520 Analyzer
521 symbols
551 Inverse Transform Unit
552 intra picture prediction unit, intra prediction unit
553 Motion Compensated Prediction Unit
555 Aggregator
556 loop filter unit
557 Reference Picture Memory
558 image buffers
603 video encoder, encoder
630 Source Encoder
632 encoding engine
633 decoder, local video decoder
633 Local Decoder
634 reference picture memory, reference picture cache
635 Predictor
643 compressed images
645 Entropy Encoder
650 controller
700 encoder
701 point cloud
701 Input point cloud
702 bitstream, compressed bitstream
710 position quantization module, quantization module
712 Duplicate Removal Module
720 Attribute Transfer Module
730 Octtree Encoding Module
740 LOD generation module
750 Forecast Module
760 residual quantization module
770 Arithmetic Coding Module
800 Decoder
801 compressed bitstream
802 point cloud
810 Arithmetic Decoding Module
820 Inverse Quantization Module
830 octree decoding module
840 LOD generation module
850 Inverse Quantization Module
860 Forecast Module
900 3D cubes
1010 Octree partition
1020 octatree structure
1201 3D Cube
1202 3D Cube
1203 3D Cube
1301 3D Cube
1302 3D Cube
1303 3D Cube
1400 treatments
1500 processed
1800 computer system
1801 keyboard
1802 mouse
1803 trackpad
1805 joystick
1806 microphone
1807 Scanner
1808 camera
1809 speaker
1810 screen, touch screen
1821 optical media
1822 thumb drive
1823 solid state drive
1840 cores
1841 central processor
1842 GPUs
1843 FPGA
1844 accelerator, hardware accelerator
1845 ROMs
1846 RAM
1847 mass storage
1848 system bus
1849 Peripheral Bus

Claims (15)

A method of point cloud geometry decoding in a point cloud decoder, comprising:
receiving, by a processing circuit, first signaling information indicative of segmentation information for a point cloud from an encoded bitstream of a point cloud comprising a set of points in a three-dimensional (3D) space;
determining, by the processing circuit, second signaling information from the encoded bitstream of the point cloud based on the first signaling information indicative of a first value; signaling information indicates a partitioning mode of the set of points in the 3D space;
determining, by the processing circuit, the partitioning mode for the set of points in the 3D space based on the second signaling information;
reconstructing, by the processing circuit, the point cloud based on the segmentation mode;
including
The step of determining the partitioning mode comprises:
receiving 3-bit signaling information for each of a plurality of partitioning levels in the partitioning mode based on the second signaling information indicative of the first value, for each of the plurality of partitioning levels; the 3-bit signaling information of indicates a partitioning direction along x, y, and z directions for the respective partitioning level in the partitioning mode;
Method. The step of determining the partitioning mode comprises:
further comprising determining the partitioning mode to be a predefined quadtree and binary tree (QtBt) partition based on the second signaling information indicative of a second value;
The method of Claim 1. receiving third signaling information indicating that the 3D space is an asymmetric cuboid;
determining dimensions of the 3D space signaled along x, y, and z directions based on the third signaling information indicative of the first value;
3. The method of claim 1 or 2, further comprising: 4. The method of claim 3 , wherein the 3-bit signaling information is determined based on the dimensionality of the 3D space. determining said partitioning mode based on said first signaling information indicative of a second value, said partitioning mode comprising a respective octree partition for each of a plurality of partitioning levels in said partitioning mode; , further comprising the step of
5. A method according to any one of claims 1-4 . A method of point cloud geometry decoding in a point cloud decoder, comprising:
receiving, by a processing circuit, first signaling information indicative of segmentation information for a point cloud from an encoded bitstream of a point cloud comprising a set of points in a three-dimensional (3D) space;
determining, by the processing circuit, a partitioning mode for the set of points in the 3D space based on the first signaling information, the partitioning mode comprising a plurality of partitioning levels;
reconstructing, by the processing circuit, the point cloud based on the segmentation mode;
including
The step of determining the partitioning mode comprises:
receiving 3-bit signaling information for each of the plurality of partitioning levels in the partitioning mode based on the first signaling information indicative of a first value, for each of the plurality of partitioning levels; the 3-bit signaling information of indicates a partitioning direction along x, y, and z directions for the respective partitioning level in the partitioning mode;
Method. 7. The method of claim 6 , wherein the 3-bit signaling information is determined based on the dimensionality of the 3D space. The step of determining the partitioning mode comprises:
6. Further comprising, based on said first signaling information indicative of a second value, determining said partitioning mode including a respective octree partition for each of said plurality of partitioning levels in said partitioning mode. Or the method described in 7 . receiving second signaling information from the encoded bitstream for the point cloud, wherein the second signaling information indicates the 3D space when the second signaling information is a first value; is an asymmetrical cuboid and the second signaling information is a second value, the second signaling information indicating the 3D space is a symmetrical cuboid, from claim 6 , further comprising: 9. The method of any one of paragraphs 8 . The step of determining the partitioning mode comprises:
each of a first partition level of the plurality of partition levels of the partition mode based on the first signaling information indicative of the second value and the second signaling information indicative of the first value; determining the partition mode to include each octree partition in
the following conditions
determining a partition type and partition direction at a last partition level of said plurality of partition levels of said partition mode according to, where d _x , d _y and d _z are x, y , and a step, which is the log2 size in 3D space in the z direction, and
10. The method of claim 9 , further comprising: determining second signaling information based on said first signaling information indicative of a first value, said second signaling information being indicative of said first value when said second signaling information is indicative of said first value; indicates that the 3D space is an asymmetric cuboid, and when the second signaling information indicates a second value, the second signaling information indicates that the 3D space is a symmetric cuboid;
determining dimensions of the 3D space signaled along x, y, and z directions based on the second signaling information indicative of the first value;
11. The method of any one of claims 6-10 , further comprising Apparatus configured to carry out the method according to any one of claims 1-5 . Apparatus arranged to carry out the method according to any one of claims 6 to 10 . A program for causing a computer to execute the method according to any one of claims 1 to 5. A program for causing a computer to execute the method according to any one of claims 6 to 11 .

Images