RU2799041C1 - Method and device for encoding point cloud - Google Patents

Abstract

FIELD: data coding.

SUBSTANCE: method for restoring a point cloud from an encoded point cloud stream is to obtain the encoded busy codes for nodes in an octree structure for the point cloud from an encoded bit stream for a point cloud. The nodes in the octree structure correspond to three-dimensional sections of point cloud space. The node sizes are associated with the sizes of the corresponding 3D partitions. The busy codes for nodes are decoded from the encoded busy codes. At least a first busy code for a child node of the first node is decoded without waiting for decoding of a second busy code for a second node having the same node size as the first node. The octree structure is restored based on the decoded busy codes for the nodes, and the point cloud is restored based on the octree structure.

EFFECT: increase in the efficiency of encoded point cloud recovery.

18 cl, 18 dwg

Description

Inclusion by reference

[1] This application claims priority over U.S. Patent Application No. 17/063411, "METHOD AND DEVICE FOR ENCODING POINT CLOUD", filed Oct. 5, 2020, which claims priority over U.S. Provisional Application No. 62/942,549, HYBRID ENCODING FOR POINT CLOUD ENCODING”, filed December 2, 2019. The entire disclosure of prior applications is incorporated herein by reference in its entirety.

The technical field to which the invention belongs

[2] The present invention describes embodiments mainly related to point cloud encoding.

State of the art

[3] Description of the prior art presented in this document is intended to provide a general presentation of the context of the invention. The work of the currently named inventors, to the extent that it is described in this section of the prior art description, as well as aspects of the description that would not otherwise be considered prior art at the time of filing, are neither expressly nor impliedly recognized in as prior art with respect to the present invention.

[4] Various technologies are being developed to capture and represent the world, such as objects in the world, environments in the world, and the like, in three-dimensional (3D) space. Three-dimensional representations of the world can provide more immersive forms of interaction and communication. Point clouds can be used as a 3D representation of the world. A point cloud is a collection of points in 3D space, each of which has associated attributes such as color, material properties, texture information, intensity attributes, reflectivity attributes, motion-related attributes, modality attributes, and various other attributes. Such point clouds can contain large amounts of data, and their storage and transmission can be time and cost intensive. Disclosure of the essence of the invention.

[5] Aspects of the disclosure provide methods and apparatus for compressing and decompressing a point cloud. In some examples, the device for compressing/decompressing a point cloud includes a processing circuit. In some embodiments, the processing circuit obtains, from the encoded bitstream for the point cloud, the encoded busy codes for the nodes in the octree structure for the point cloud. The nodes in the octree structure correspond to three-dimensional (3D) sections of point cloud space. The node sizes are associated with the sizes of the respective 3D partitions. In addition, the processing circuit decodes, from the encoded occupancy codes, the occupancy codes for the nodes. At least a first busy code for a child node of the first node is decoded without waiting for decoding of a second busy code for a second node having the same node size as the first node. The processing circuit then reconstructs the octree structure based on the decoded busy codes for the nodes, and reconstructs the point cloud based on the octree structure.

[6] In some embodiments, the processing circuit decodes a first set of occupancy codes for a first set of nodes in a first sub-octtree, the first node being the root of the first sub-octtree, and decodes a second set of occupancy codes for a second set of nodes in the second sub-octtree, the second node being the root of the second suboctree. In one embodiment, the processing circuit decodes the first set of busy codes for the first set of nodes in the first sub-octtree in parallel with the second set of busy codes for the second set of nodes in the second sub-octtree.

[7] In another embodiment, the processing circuit decodes, using the first coding mode, the first set of occupancy codes for the first set of nodes in the first sub-octree, and decodes, using the second coding mode, the second set of occupancy codes for the second set of nodes in the second sub-octree. In one example, the processing circuit decodes from the encoded bitstream a first index that indicates the first encoding mode for the first sub-octree, and decodes from the encoded bitstream a second index that indicates the second encoding mode for the second sub-octree.

[8] In some embodiments, the processing circuit decodes the first portion of busy codes for larger nodes in nodes using first order coding. Larger nodes larger than the specific node size to change the encoding order. The processing circuit decodes the second part of the busy codes for the smaller nodes in the nodes using a second coding order that is different from the first coding order. Smaller nodes are equal to or less than a specific node size to change the encoding order. In one example, the first encoding order is the width encoding order and the second encoding order is the depth encoding order. In another example, the first encoding order is depth-encoding order and the second encoding order is width-encoding order.

[9] In some examples, the processing scheme determines a specific node size for reordering the coding based on the signal in the encoded bitstream for the point cloud. In one example, the processing circuit decodes a control signal from an encoded bitstream for a point cloud, and the control signal indicates a change in encoding order. The processing circuit then decodes the signal and determines the specific node size to change the encoding order.

[10] Aspects of the disclosure also provide a non-transitory computer-readable medium storing instructions that, when executed by a computer to encode/decode a point cloud, cause the computer to perform any one or combination of methods to encode/decode a point cloud. Brief description of the drawings.

[11] Additional features, essence and various advantages of the disclosed subject matter will be more apparent from the following detailed description and the accompanying drawings, which show the following:

[12] FIG. 1 is a schematic illustration of a simplified block diagram of a communication system in accordance with an embodiment;

[13] FIG. 2 is a schematic illustration of a simplified block diagram of a streaming system according to an embodiment;

[14] FIG. 3 is a block diagram of an encoder for encoding point cloud frames, in accordance with some embodiments;

[15] FIG. 4 is a block diagram of a decoder for decoding a compressed bitstream corresponding to point cloud frames, in accordance with some embodiments;

[16] FIG. 5 is a schematic illustration of a simplified block diagram of a video decoder in accordance with one embodiment;

[17] FIG. 6 is a schematic illustration of a simplified block diagram of a video encoder according to an embodiment;

[18] FIG. 7 is a block diagram of an encoder for encoding point cloud frames, in accordance with some embodiments;

[19] FIG. 8 is a block diagram of a decoder for decoding a compressed bitstream corresponding to point cloud frames, in accordance with some embodiments;

[20] FIG. 9 is a diagram illustrating cube partitioning based on the octree partitioning technique according to some embodiments of the present disclosure;

[21] FIG. 10 shows an example of an octree split and an octree structure corresponding to an octree split, according to some embodiments of the invention;

[22] FIG. 11 shows an octree structure diagram illustrating a width-encoding order;

[23] FIG. 12 shows an octree structure diagram illustrating a depth-coding order;

[24] FIG. 13 shows an example geometry parameter set syntax according to some embodiments of the invention;

[25] FIG. 14 shows another example of geometry parameter set syntax according to some embodiments of the invention;

[26] FIG. 15 shows an example pseudocode for encoding an octree according to some embodiments of the disclosure;

[27] FIG. 16 shows an example of pseudocode for a depth-coding order according to some embodiments of the disclosure;

[28] FIG. 17 shows a flowchart describing an example of a process in accordance with some embodiments;

[29] FIG. 18 is a schematic illustration of a computer system in accordance with an embodiment.

Implementation of the invention

[30] Aspects of the present disclosure provide methods for point cloud (PCC) encoding. The PCC may be performed according to various schemes such as a geometry based scheme referred to as G-PCC, a video coding based scheme referred to as V-PCC, and the like. According to some aspects of the disclosure, G-PCC encodes 3D geometry directly and is a pure geometry approach without much sharing of video coding, while V-PCC is heavily based on video coding. For example, the V-PCC may map a 3D cloud point to a 2D grid (image) pixel. The V-PCC scheme can use common video codecs to compress the point cloud. The Moving Picture Experts Group (MPEG) is working on the G-PCC standard and the V-PCC standard, which respectively use the G-PCC scheme and the V-PCC scheme.

[31] Aspects of the disclosure provide methods for hybrid coding order that can be used in PCC, such as the G-PCC scheme and the V-PCC scheme. The hybrid encoder may include a depth-jumping scheme and a width-jumping scheme in coding order. The present disclosure also provides methods for signaling an encoding order.

[32] Point clouds can be widely used in many applications. For example, point clouds can be used in autonomous vehicles to detect and localize objects; point clouds can be used in geographic information systems (GIS) to build maps and can be used in cultural heritage to visualize and archive cultural heritage objects and collections, etc.

[33] Hereinafter, a point cloud as a whole may refer to a set of points in 3D space, each of which has associated attributes, such as color, material properties, texture information, intensity attributes, reflectivity attributes, motion-related attributes, modalities and various other attributes. Point clouds can be used to recreate an object or scene as a composition of such points. Points can be captured using multiple cameras, depth sensors or lidar in various settings and can be composed of thousands or billions of points to realistically represent reconstructed scenes. A patch as a whole can refer to a continuous subset of a surface described by a point cloud. In the example, the plot includes points with normal vectors to the surface that deviate from each other by less than a threshold value.

[34] Compression techniques can reduce the amount of data required to represent a point cloud for faster transmission or reduce storage space. Thus, there is a need for lossy point cloud compression technology for use in real-time communications and virtual reality with six degrees of freedom (6 CC). In addition, lossless point cloud compression technology is required in the context of dynamic mapping for autonomous driving, cultural heritage applications, and the like.

[35] According to an aspect of the disclosure, the core philosophy of V-PCC is to use existing video codecs to compress the geometry, occupancy, and texture of a dynamic point cloud into three separate video sequences. The additional metadata required to interpret the three video sequences is compressed separately. A small part of the overall bitstream is metadata, which can be encoded/decoded efficiently by a software implementation. Most of the information is processed by the video codec.

[36] FIG. 1 illustrates a simplified block diagram of a communication system (100) according to an embodiment of the present disclosure. The communication system (100) includes a plurality of terminal devices that can communicate with each other, for example, via a network (150). For example, the communication system (100) includes a pair of terminal devices (110) and (120) interconnected via a network (150). In FIG. 1, the first pair of terminal devices (110) and (120) can perform unidirectional transmission of point cloud data. For example, the terminal device (110) may compress a point cloud (eg, points representing a structure) that is captured by a sensor (105) connected to the terminal device (110). The compressed point cloud may be transmitted, for example, in the form of a bit stream to another terminal device (120) via a network (150). The terminal device (120) may receive the compressed point cloud from the network (150), decompress the bit stream to recover the point cloud, and display the recovered point cloud appropriately. One-way communication may be common in media serving applications and the like.

[37] FIG. 1, terminal devices (110) and (120) may be illustrated as servers and personal computers, but the principles of the present disclosure cannot be limited to this. Embodiments of the present disclosure find application in laptop computers, tablet computers, smartphones, gaming terminals, media players, and/or specialized three-dimensional (3D) equipment. Network (150) represents any number of networks that transmit compressed point cloud between terminal devices (110) and (120). Network (150) may include, for example, wired (wired) and/or wireless communication networks. The network (250) may communicate on circuit-switched and/or packet-switched channels. Typical networks include telecommunications networks, local area networks, wide area networks and/or the Internet. For the purposes of this discussion, the architecture and topology of the network (150) may not be essential to the operation of this disclosure, unless explained herein below.

[38] FIG. 2 illustrates a simplified block diagram of a streaming system (200) in accordance with an embodiment. Fig. The 2 example is an application for an open object for a point cloud. The disclosed subject matter may be equally applicable to other point cloud enabled applications such as a 3D telepresence application, a virtual reality application, and the like.

[39] The streaming system (200) may include a capture subsystem (213). The capture subsystem (213) may include a point cloud source (201), such as detection and distance determination (LIDAR) systems, 3D cameras, 3D scanners, a graphics generation component that generates an uncompressed point cloud in software, etc. P. generates, for example, point clouds (202) that are uncompressed. In one example, point clouds (202) include points captured by 3D cameras. The point clouds (202) are shown with a heavy line to emphasize the large amount of data compared to the compressed point clouds (204) (compressed point cloud bitstream). The compressed point clouds (204) may be generated by an electronic device (220) that includes an encoder (203) coupled to a 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 clouds (204) (or bitstream of compressed point clouds (204)), depicted with a thin line to emphasize the smaller amount of data compared to the point cloud stream (202), can be stored on the streaming server (205) for future use. One or more streaming client subsystems, such as client subsystems (206) and (208) in FIG. 2 can access the streaming server (205) to extract copies (207) and (209) of the compressed point cloud (204). The client subsystem (206) may include a decoder (210), such as in an electronic device (230). The decoder (210) decodes the incoming copy (207) of the compressed point clouds and creates an outgoing stream (211) of the reconstructed point clouds that can be rendered on the rendering device (212).

[40] It should be noted that the electronic devices (220) and (230) may include other components (not shown). For example, electronic device (220) may include a video decoder (not shown), and electronic device (230) may also include a video encoder (not shown).

[41] In some streaming systems, compressed point clouds (204), (207) and (209) (eg, compressed point cloud bitstreams) may be compressed according to certain standards. In some examples, video coding standards are used when compressing point clouds. Examples of these standards include High Efficiency Video Coding (HEVC), Versatile Video Coding (VVC), and the like.

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

[43] The V-PCC encoder (300) receives the point cloud frames as uncompressed input and generates 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 a point cloud source (201) or the like.

[44] In the example of FIG. 3 V-PCC encoder (300) includes a patch generating module (306), a patch packing module (308), a geometry image generating module (310), a texture image generating module (312), a patch information module (304), a module ( 314) occupancy maps, smoothing module (336), image filling modules (316) and (318), group extension module (320), video compression modules (322), (323) and (332), additional compression module (338) plot information, an entropy compression module (334), and a multiplexer (324).

[45] According to an aspect of the disclosure, a V-PCC encoder (300) converts 3D point cloud frames into an image-based representation along with some metadata (eg, occupancy map and parcel information) that is used to convert the compressed point cloud back to a decompressed point cloud. . In some examples, the V-PCC encoder (300) may convert 3D point cloud frames into geometry images, texture images, and occupancy maps, and then use video coding techniques to encode the geometry images, texture images, and occupancy maps into a bitstream. Typically, a geometry image is a 2D image with pixels filled with geometry values associated with points projected onto the pixels, and a pixel filled with geometry value may be referred to as a geometry sample. A texture image is a 2D image with pixels filled with texture values associated with pixels projected onto the pixels, and a pixel filled with a texture value may be referred to as a texture sample. The occupancy map is a 2D image with pixels filled with values that indicate whether they are occupied or not occupied by lots.

[46] The point cloud patch generation module (306) segments the point cloud into a set of patches (e.g., a patch is defined as a continuous subset of the surface described by the point cloud) that may or may not overlap, so that each patch can be described by a depth field with respect to a plane. in two-dimensional space. In some embodiments, the patch generation module (306) aims to decompose the point cloud into a minimum number of patches with smooth boundaries, as well as to minimize the recovery error.

[47] The parcel information module (304) may collect parcel information indicative of the size and shape of the parcels. In some examples, the region information may be packed into an image frame and then encoded by the region side information compression module (338) to generate compressed region information.

[48] The patch packing module (308) is configured to plot the extracted patches onto a two-dimensional (2D) grid while minimizing wasted space and ensuring that each MxM block (eg, 16x16) of the grid is associated with a unique patch. Efficient parcel packing can directly affect compression efficiency, either by minimizing wasted space or by ensuring consistency over time.

[49] The geometry image generating module (310) may generate two-dimensional geometry images associated with point cloud geometry at predetermined parcel locations. The texture image generating module (312) may generate 20 texture images associated with a point cloud texture at predetermined patch locations. The geometry image generation module (310) and the texture image generation module (312) use the 3D to 2D transformation calculated during the packing process to store the geometry and texture of the point cloud as images. To better handle the case where multiple points are projected onto the same sample, each area is projected onto two images, called layers. In one example, the geometry image is represented by a WxH monochromatic frame in YUV420-8bit format. To generate a texture image, the texture generation routine uses the reconstructed/smoothed geometry to calculate the colors to be associated with the resampling points.

[50] The occupancy map module (314) may generate an occupancy map that describes padding information in each block. For example, the busy image includes a binary map that indicates, for each grid cell, whether the cell belongs to empty space or a point cloud. In the example, the occupancy map uses binary information describing, for each pixel, whether the pixel is full or not. In another example, the occupancy map uses binary information describing, for each pixel block, whether the pixel block is full or not.

[51] The occupancy map generated by the occupancy map module (314) may be compressed using lossless coding or lossy coding. When lossless encoding is used, an entropy compression module (334) is used to compress the occupancy map. When lossy coding is used, a video compression module (332) is used to compress the occupancy map.

[52] It should be noted that the section packing module (308) may leave some empty spaces between the two-dimensional sections packed in the image frame. The image padding modules (316) and (318) may fill in empty spaces (padding) to generate an image frame that may be suitable for 2D video and image codecs. Image padding is also called background padding, which can fill unused space with redundant information. In some examples, good background padding minimally increases the data rate, but does not introduce significant coding distortion around segment boundaries.

[53] The video compression modules (322), (323), and (332) can encode 2D images such as geometry augmented images, texture augmented images, and occupancy maps based on a suitable video coding standard such as HEVC, VVC, and the like. . In one example, video compression modules (322), (323), and (332) are separate components that operate separately. It should be noted that the modules (322), (323) and (332) video compression can be implemented as a single component in another example.

[54] In some examples, the smoothing module (336) is configured to create a smoothed image of the restored image image. A smoothed image may be provided to generate (312) a texture image. The texture image generation 312 may then adjust the generation of the texture image based on the reconstructed geometry images. For example, when the shape of the patches (eg, geometry) is slightly distorted during encoding and decoding, the distortion can be taken into account when generating texture images to correct the distortion of the shape of the patches.

[55] In some embodiments, the group expansion (320) is configured to pad pixels around object boundaries with redundant low frequency content to improve the encoding factor as well as the visual quality of the reconstructed point cloud.

[56] The multiplexer (324) may multiplex the compressed geometry image, the compressed texture image, the compressed occupancy map, the compressed section side information into a compressed bit stream.

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

[58] In the example of FIG. 4 V-PCC decoder (400) includes a demultiplexer (432), video decompressor modules (434) and (436), an occupancy map decompressor module (438), a section side information decompressor module (442), a geometry recovery module (444) , a smoothing module (446), a texture recovery module (448), and a color smoothing module (452).

[59] The demultiplexer (432) may receive and separate the compressed bitstream into a compressed texture image, a compressed geometry image, a compressed occupancy map, and compressed patch side information.

[60] The video decompressing modules (434) and (436) may decode the compressed images according to an appropriate standard (eg, HEVC, VVC, etc.) and output the decompressed images. For example, the video decompressor (434) decodes the compressed texture images and outputs the decompressed texture images; and the video decompressor (436) decodes the compressed geometry images and outputs the decompressed geometry images.

[61] The occupancy map decompressor 438 may decode the compressed occupancy maps according to an appropriate standard (eg, HEVC, VVC, etc.) and output the decompressed occupancy maps.

[62] The section side information decompressor (442) may decode the compressed section side information according to an appropriate standard (eg, HEVC, VVC, etc.) and output the decompressed section side information.

[63] The geometry recovery module (444) may receive decompressed geometry images and generate a reconstructed point cloud geometry based on the decompressed occupancy map and the decompressed parcel side information.

[64] The smoothing module (446) can smooth out inconsistencies at the edges of the sections. The smoothing procedure is aimed at eliminating potential inhomogeneities that may occur at the boundaries of the sections due to compression artifacts. In some embodiments, an anti-aliasing filter may be applied to pixels located at the site boundaries to reduce distortion that may be caused by compression/decompression.

[65] The texture recovery module (448) may determine texture information for points in the point cloud based on decompressed texture images and anti-aliasing geometry.

[66] The color smoothing module (452) can smooth out color mismatches. Non-adjacent areas in 3D space are often packed next to each other in 2D video. In some examples, pixel values from non-adjacent areas may be mixed by a block-by-block video codec. The purpose of color smoothing is to reduce the visible artifacts that appear at the boundaries of the plots.

[67] FIG. 5 shows a block diagram of a video decoder (510) according to an embodiment of the present invention. The video decoder (510) may be used in the V-PCC decoder (400). For example, modules (434) and (436) video decompressor module (438) decompress the busy map can be configured similarly to the video decoder (510).

[68] The video decoder (510) may include a parser (520) for recovering symbols (521) from compressed images, such as an encoded video sequence. The categories of these symbols include information used to control the operation of the video decoder (510). A parser (520) may parse/entropy decode the received encoded video sequence. Encoding of the encoded video sequence may be in accordance with a video coding technology or standard, and may follow various principles including variable length coding, Huffman coding, arithmetic coding with or without context sensitivity, and so on. The parser (520) can extract from the encoded video sequence a set of subgroup parameters for at least one of the subgroups of pixels in the video decoder based on at least one parameter corresponding to the group. Subgroups may include groups of pictures (GOPs), pictures, tiles, slices, macroblocks, coding units (CUs), blocks, transform units (TUs), prediction units (PUs), and so on. The parser (520) may also extract information from the encoded video sequence, such as transform coefficients, quantizer parameter values, motion vectors, and so on.

[69] The parser (520) may perform an entropy decoding/parsing operation of the video sequence obtained from the buffer memory to create symbols (521).

[70] Symbol recovery (521) may involve many different modules depending on the type of encoded video image or parts thereof (such as: inter and intra image, inter and intra block) and other factors. Which modules are enabled and how can be controlled by the subgroup control information parsed from the encoded video sequence by the parser (520). The flow of such subgroup control information between the parser (520) and the plurality of modules is not shown below for clarity.

[71] In addition to the functional blocks already mentioned, the video decoder (510) can be conceptually subdivided into a number of functional modules, as described below. In a practical implementation operating under commercial constraints, many of these modules interact closely with each other and can be at least partially integrated into each other. However, for purposes of describing the disclosed subject matter, the conceptual division into functional modules below is appropriate.

[72] The first module is the scaling/inverse transform module (551). The scaling/inverse transform module (551) receives the quantized transform coefficient, as well as control information, including which transform to use, block size, quantization factor, quantization scaling matrices, and so on, in the form of symbol(s) (521) from the parser (520). The scaling/inverse transform module (551) may output blocks containing sample values that may be input to the aggregator (555).

[73] In some cases, the output samples of the scaling/inverse transform module (551) may refer to an intra-coded block; that is, to a block that does not use prediction information from previously restored images, but can use prediction information from previously restored portions of the current image. Such prediction information may be provided by the intra prediction module (5452). In some cases, the intra-prediction module (552) generates a block of the same size and shape as the block being reconstructed, using the already reconstructed surrounding information retrieved from the current image buffer (558). The current picture buffer (558) buffers, for example, a partially restored current picture and/or a fully restored current picture. The aggregator (555) in some cases adds, for each sample, the prediction information generated by the intra-prediction module (552) to the output sample information provided by the scaling/inverse transform module (551).

[74] In other cases, the output samples of the scaling/inverse transform module (551) may refer to a block with intercoding and potentially with motion compensation. In such a case, the motion compensation prediction module (553) may access the reference picture memory (557) to retrieve samples used for prediction. After compensating for motion of the selected samples according to the symbols (521) associated with the block, these samples can be added by the aggregator (555) to the output of the scaling/inverse transform module (551) (in this case called residual samples or residual signal) to generate output information. The addresses in the reference picture memory (557) from where the motion compensation prediction module (553) selects prediction samples may be controlled by the motion vectors available to the motion compensation prediction module (553) in the form of symbols (521), which may have, for example, components X, Y and reference image. Motion compensation may also include interpolation of sample values retrieved from reference picture memory (557) when accurate sub-sample motion vectors are used, motion vector prediction mechanisms, and so on.

[75] The output samples of the aggregator (555) may be subjected to various loop filtering methods in the loop filter module (556). The video compression techniques may include in-loop filtering techniques that are controlled by parameters included in the encoded video sequence (also referred to as the encoded video bitstream) and provided to the loop filtering module (556) as symbols (521) from the parser (520), but may also respond to meta-information received during decoding of the previous (in the order of decoding) parts of the encoded image or encoded video sequence, and also respond to the sample values previously restored and filtered by the loop.

[76] The output of the loop filter module (556) may be a stream of samples that can be output to the renderer (512) and also stored in the reference picture memory (557) for use in future inter-picture prediction.

[77] Certain encoded pictures after full recovery can be used as reference pictures for future prediction. For example, after the encoded picture corresponding to the current picture has been completely restored and the encoded picture has been identified as a reference picture (for example, by the parser (520)), the current picture buffer (558) may become part of the reference picture memory (557), and the buffer of the fresh current picture may be reallocated before starting the reconstruction of the next encoded picture.

[78] The video decoder (510) may perform decoding operations according to a predetermined video compression technology in a standard such as ITU-T Rec. H.265. The encoded video sequence may conform to the syntax specified by the video compression technology or standard being used, in the sense that the encoded video sequence conforms to both the syntax of the video compression technology or standard and to the profiles documented in the video compression technology or standard. In particular, a profile may select certain tools as the only tools available for use in that profile, from among all the tools available in a video compression technology or standard. It may also be necessary for compliance that the complexity of the encoded video sequence be within the boundaries defined by the level of technology or video compression standard. In some cases, levels limit the maximum image size, the maximum frame rate, the maximum recovery sampling rate (measured in megasamples per second, for example), the maximum reference image size, and so on. The limits set by the layers may, in some cases, be further constrained by Hypothetical Reference Decoder (HRD) specifications and metadata for managing the HRD buffer signaled in the encoded video sequence.

[79] FIG. 6 is a block diagram of a video decoder (603) according to an embodiment of the present invention. A video encoder (603) may be used in a V-PCC encoder (300) to compress point clouds. In the example, the video compression modules (322) and (323) and the video compression module (332) are configured similarly to the encoder (603).

[80] The video encoder (603) may receive images such as filled geometry images, filled texture images, and the like, and generate compressed images.

[81] According to an embodiment, the encoder (603) can encode and compress images of the original video sequence (images) into an encoded video sequence (compressed images) in real time or with any other time constraints as required by the application. Providing an appropriate coding rate is one of the functions of the controller (650). In some embodiments, the implementation of the controller (650) controls other functional modules, as described below, and is functionally associated with other functional modules. The connection is not shown for clarity. Parameters set by the controller (650) may include parameters related to speed control (picture skip, quantizer, speed-distortion optimization methods lambda value, ...), image size, group of pictures (GOP) layout, maximum motion vector search range and so on. The controller (650) may be configured to have other suitable functions that are related to the video encoder (603) optimized for a particular system design.

[82] In some embodiments, the video encoder (603) is configured to operate in an coding loop. As a simplified description, in an example, an encoding loop may include a source encoder (630) (e.g., responsible for creating symbols, such as a stream of symbols, based on an input image for encoding, and reference image(s), as well as a (local) a decoder (633) built into the video encoder (603) The decoder (633) decompresses the symbols to create sample data in a manner similar to how a (remote) decoder can also create (because any compression between the symbols and the encoded video bitstream is lossless in compression technologies of the video of the disclosed subject matter.) The reconstructed sample stream (sample data) is entered into the reference picture memory 634. Since the decoding of the symbol stream results in bit-accurate results, regardless of the location of the decoder (local or remote), the content in the memory The reference picture 634 is also bit accurate between the local encoder and the remote encoder In other words, the encoder prediction part "sees" as reference picture samples exactly the same sample values that the decoder would "see" if using prediction during decoding. This fundamental principle of reference picture synchronism (and the resulting drift if synchronism cannot be maintained due to, for example, channel errors) is also used in some related fields of technology.

[83] The operation of the "local" decoder (633) may be the same as that of the "remote" decoder, such as the video decoder (510), which has already been described in detail above in connection with FIG. 5. Briefly referring also to FIG. 5, however, since the symbols are available and encoding/decoding of the symbols into the encoded video sequence by the entropy encoder (645) and the parser (520) can be lossless, the entropy decoding parts of the video decoder (510) including the parser (520) cannot be fully implemented in the local decoder (633).

[84] At this point, it can be observed that any decoding technology other than parsing/entropy decoding that is present in a decoder must also necessarily be present in a substantially identical functional form in the corresponding encoder. For this reason, the disclosed subject matter focuses on the operation of the decoder. The description of encoding technologies can be abbreviated as they are the inverse of fully described decoding technologies. Only in some areas a more detailed description is required, which is given below.

[85] During operation, in some examples, source encoder (630) may perform motion-compensated predictive encoding that predictively encodes an input picture with reference to one or more previously encoded pictures from a video sequence that have been designated "reference pictures". Thus, the coding engine (632) encodes the differences between the pixel blocks of the input image and the pixel blocks of the reference image(s) that can be selected as prediction reference(s) for the input image.

[86] The local video decoder (633) may decode the encoded video data of pictures that can be designated as reference pictures based on the symbols generated by the source encoder (630). The operations of the encoding engine (632) may preferably be lossy processes. When the encoded video data can be decoded in a video decoder (not shown in FIG. 6), the reconstructed video sequence can typically be a copy of the original video sequence with some errors. The local video decoder (633) replicates the decoding processes that may be performed by the video decoder on the reference pictures and may cause the recovered reference pictures to be stored in the reference picture cache (734). Thus, the video encoder (603) can locally store copies of the reconstructed reference pictures that share the same content as the reconstructed reference pictures to be received by the far end video decoder (in the absence of transmission errors).

[87] The predictor (635) may perform predictive searches for the encoding engine (632). That is, for a new picture to be encoded, the predictor (635) may search the reference picture memory (634) for sample data (as reference pixel block candidates) or certain metadata such as reference picture motion vectors, block shapes, and so on. further, which can serve as a suitable prediction reference for new images. The predictor (635) may operate on a block-by-pixel basis of samples to find appropriate prediction references. In some cases, as determined by the search results obtained by the predictor (635), the input picture may have prediction references taken from a plurality of reference pictures stored in the reference picture memory (6734).

[88] The controller (650) may control the encoding operations of the source encoder (630), including, for example, setting parameters and subgroup parameters used to encode video data.

[89] The output signals of all the above functional modules can be entropy encoded in an entropy encoder (645). An entropy encoder (645) translates symbols generated by various functional units into an encoded video sequence by lossless symbol compression according to techniques such as Huffman coding, variable length coding, arithmetic coding, and so on.

[90] The controller (650) may control the operation of the video encoder (603). During encoding, the controller (650) may assign to each encoded picture a certain type of encoded picture, which may affect the encoding methods that can be applied to the corresponding picture. For example, images can often be categorized as one of the following image types:

[91] An intra-picture (I-picture) may be one that can be encoded and decoded without using any other picture in the sequence as a prediction source. Some video codecs allow various types of intra-pictures, including, for example, independent decoder update ("IDR") pictures. The person skilled in the art will be aware of these variants of I-images and their respective uses and features.

[92] A predictive picture (P-picture) may be one that can be encoded and decoded using intra-prediction or inter-prediction using at most one motion vector and a reference index to predict sample values of each block.

[93] A bidirectional predictive picture (B-picture) may be one that can be encoded and decoded using intra-prediction or inter-prediction using at most two motion vectors and reference indices to predict sample values of each block. Similarly, multi-prediction images may use more than two reference images and associated metadata to reconstruct a single block.

[94] Source images can typically be spatially divided into multiple blocks of samples (eg, blocks of 4x4, 8x8, 4x8, or 16x16 samples each) and encoded on a block-by-block basis. The blocks may be predictively encoded with reference to other (already encoded) blocks, as determined by the coding assignment applied to the corresponding block images. For example, 1-picture blocks may be predictively encoded or they may be predictively encoded with reference to already encoded blocks of the same image (spatial prediction or intra prediction). The pixel blocks of P-pictures may be predictively encoded, by spatial prediction, or by temporal prediction with reference to one previously encoded reference picture. Blocks of B-pictures may be predictively coded, spatially predicted, or temporally predicted with reference to one or two previously encoded reference pictures.

[95] The video encoder (603) may perform encoding operations in accordance with a predetermined video coding technology or standard, such as ITU-T Rec. H.265. In operation, the video encoder (603) may perform various compression operations, including predictive coding operations that exploit temporal and spatial redundancy in the input video sequence. The encoded video data may therefore follow the syntax given by the video coding technology or standard being used.

[96] The video may be in the form of a plurality of source images (images) in time sequence. Intra-frame prediction (often abbreviated as intra-prediction) uses the spatial correlation in a given image, while inter-frame prediction uses (temporal or other) correlation between images. In the example, a specific image, when encoding/decoding, which is referred to as the current image, is divided 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 a video, the block in the current picture may be encoded with a vector called a motion vector. The motion vector points to a reference block in the reference picture and may have a third dimension identifying the reference picture if multiple reference pictures are used.

[97] In some embodiments, inter-frame prediction may use a dual prediction technique. According to the double prediction method, two reference pictures, such as a first reference picture and a second reference picture, which both precede in decoding order the current picture in the video (but may be in the past and future, respectively, in display order). A block in the current picture may be encoded with a first motion vector that points to a first reference block in a first reference picture and a second motion vector that points to a second reference block in a second reference picture. The block may be predicted by the combination of the first reference block and the second reference block.

[98] In addition, the merge mode technique can be used in inter-frame prediction to improve coding efficiency.

[99] According to some embodiments of the invention, predictions such as inter-frame predictions and intra-frame predictions are performed in a unit of blocks. For example, according to the HEVC standard, an image in a video sequence is divided into coding tree units (CTUs) for compression, where the CTUs in the image are the same size, such as 64×64 pixels, 32×32 pixels, or 16×16 pixels. In general, the CTU includes three coding tree units (CTBs), which are one luma CTB and two chrominance CTBs. Each CTU may be recursively split into a quadtree into one or multiple coding units (CUs). For example, a CTU of 64x64 pixels can be divided into one CU of 64x64 pixels, or 4 CUs of 32x32 pixels, or 16 CUs of 16x16 pixels. In the example, each CU is parsed to determine a prediction type for the CU, such as an inter-prediction type or an intra-prediction type. The CU is divided into one or more prediction units (PUs) depending on temporal and/or spatial predictability. Typically, each PU includes a Luma Prediction Unit (PB) and two Chroma PBs. In an embodiment, the encoding (encoding/decoding) prediction operation is performed in units of prediction blocks. Using the luminance prediction block as an example of the prediction block, the prediction block includes a matrix of values (e.g., luminance values) for pixels, such as 8x8 pixels, 16x16 pixels, 8x16 pixels, 16x8 pixels, etc. P.

[100] FIG. 7 shows a block diagram of a G-PPC encoder (700) according to an embodiment. The encoder (700) may be configured to receive point cloud data and compress the point cloud data to generate a bit stream carrying the compressed point cloud data. In an embodiment, the encoder (700) may include a position quantization module (710), a duplicate point removal module (712), an octree encoding module (730), an attribute transmission module (720), a level of detail (LOD) generation module (740) , an attribute prediction module (750), a residual quantization module (760), an arithmetic encoding module (770), an inverse residual quantization module (780), an addition module (781), and a memory (790) for storing the recovered attribute values.

[101] As shown, the input point cloud (701) can be obtained in the encoder (700). The positions (eg, 3D coordinates) of the point cloud (701) are provided to the quantization module (710). The quantization module (710) is configured to quantize coordinates to generate quantized positions. The duplicate point removal module (712) is configured to receive the quantized positions and perform a filtering process to identify and remove the duplicate points. The octree encoding module (730) is configured to receive the filtered positions from the duplicate point removal module (712) and perform an octree-based encoding process to generate a sequence of busy codes that describe a three-dimensional grid of voxels. The busy codes are passed to the arithmetic coding module (770).

[102] The attribute transfer module (720) is configured to receive attributes of the input point cloud and perform an attribute transfer process to determine an attribute value for each voxel when multiple attribute values are associated with a corresponding voxel. The attribute transfer process may be performed on the reordered points output from the octree encoding module (730). The attributes after the transfer operations are provided to the attribute prediction module (750). The LOD generation module (740) is configured to work with the reordered points output from the octree encoding module (730) and reorganize the points in different LODs. The LOD information is provided to the attribute prediction module (750).

[103] The attribute prediction module (750) processes the points in accordance with the LOD-based order indicated by the LOD information from the LOD generation module (740). The attribute prediction module (750) generates an attribute prediction for the current point based on the restored attributes of the set of neighboring points of the current point stored in the memory (790). The prediction residuals may subsequently be obtained based on the original attribute values received from the attribute transmission module (720) and the locally generated attribute predictions. When candidate indexes are used in a corresponding attribute prediction process, an index corresponding to the selected prediction candidate may be provided to the arithmetic encoding unit (770).

[104] The residual quantization module (760) is configured to receive prediction residuals from the attribute prediction module (750) and perform quantization to generate quantized residuals. The quantized residuals are provided to the arithmetic coding module (770).

[105] The inverse quantization module (780) is configured to receive quantized residuals from the residual quantization module (760) and generate reconstructed prediction residuals by performing the inverse operations of the quantization operations performed in the residual quantization module (760). The adder (781) is configured to receive the reconstructed prediction residuals from the residual inverse quantizer (780) and corresponding attribute predictions from the attribute predictor (750). By combining the recovered prediction residuals and the attribute predictions, the recovered attribute values are generated and stored in memory (790).

[106] The arithmetic encoding module (770) is configured to receive occupancy codes, candidate indices (if used), quantized residuals (if generated), and other information, and perform entropy encoding to further compress the received values or information. As a result, a compressed bit stream (702) carrying compressed information can be generated. The bitstream (702) may be transmitted to or otherwise provided to a decoder that decodes the compressed bitstream, or may be stored in a storage device.

[107] FIG. 8 shows a block diagram of a G-PCC decoder (800) according to an embodiment. The decoder (800) may be configured to receive the compressed bitstream and perform decompression of the point cloud data to decompress the bitstream to generate decoded point cloud data. In an embodiment, the decoder (800) may include an arithmetic decoding module (810), a residual inverse quantization module (820), an octree decoding module (830), a LOD generation module (840), an attribute prediction module (850), and a memory (860). ) to store the restored attribute values.

[108] As shown, the compressed bitstream (801) can be obtained in the module (810) arithmetic decoding. The arithmetic decoding module (810) is configured to decode the compressed bitstream (801) to obtain quantized residuals (if generated) and point cloud occupancy codes. The octree decoding module (830) is configured to determine the recovered point cloud positions in accordance with the busy codes. The LOD generation module (840) is configured to reorganize points in different LODs based on the recovered positions and to determine an order based on the LOD. The residual inverse quantization module (820) is configured to generate reconstructed residuals based on the quantized residuals received from the arithmetic decoding module (810).

[109] The attribute prediction module (850) is configured to perform an attribute prediction process to determine attribute predictions for points according to LOD-based order. For example, the current point attribute prediction may be determined based on the recovered point attribute values of the current point's neighbors stored in memory (860). An attribute prediction module (850) may combine the attribute prediction with the corresponding reconstructed residual to generate a reconstructed attribute for the current point.

[110] The sequence of recovered attributes generated from the attribute prediction module (850), together with the recovered positions generated from the octree decoding module (830), corresponds to the decoded point cloud (802) that is output from the decoder (800) in one example. In addition, the recovered attributes are also stored in memory (860) and can later be used to derive attribute predictions for subsequent points.

[111] In various embodiments, the encoder (300), decoder (400), encoder (700), and/or decoder (800) may be implemented in hardware, software, or a combination thereof. For example, the encoder (300), decoder (400), encoder (700), and/or decoder (800) may be implemented with a processing circuit, such as one or more integrated circuits (ICs), that operate with or without software. such as application specific integrated circuit (ASIC), field programmable gate array (FPGA), and the like. In another example, encoder (300), decoder (400), encoder (700), and/or decoder (800) may be implemented as software or firmware, including instructions stored in a non-volatile (or non-transitory) computer-readable storage medium. The instructions, when executed by a processing circuit, such as one or more processors, cause the processing circuit to perform the functions of an encoder (300), decoder (400), encoder (700), and/or decoder (800).

[112] It should be noted that attribute prediction modules (750) and (850) configured to implement the attribute prediction methods disclosed herein may be included in other decoders or encoders, which may have a structure similar or different from that shown in fig. 7 and FIG. 8. In addition, the encoder (700) and decoder (800) may be included in the same device or in separate devices in different examples.

[113] According to some aspects of the disclosure, a geometry octree structure may be used in the PCC. In some related examples, the geometry octree structure is viewed in widthwise order. According to breadth-first order, octree nodes at the current level can be visited after visiting octree nodes at the top level. According to an aspect of the present disclosure, the width-to-width ordering scheme is not suitable for parallel processing because the current layer must wait for the top layer encoding. The present disclosure provides methods for adding depth-encoding order to encoding order methods for a geometry octree structure. Depth-coding order may be combined with depth-coding order in some embodiments, or may be used by itself in some embodiments. Encoding orders (eg, depth-encoding order, combination of depth-encoding order and width-encoding order, etc.) may be referred to as hybrid coding orders for PCC in the present disclosure.

[114] The proposed methods can be used individually or combined in any order. In addition, each of the encoder and decoder methods (or embodiments) may be implemented by processing circuits (eg, one or more processors or one or more integrated circuits). In one example, one or more processors execute a program that is stored on a non-transitory computer-readable medium.

[115] According to some aspects of the disclosure, geometry information and associated point cloud attributes such as color, reflectance, and the like, may be compressed separately (eg, in Test Model 13 (TMC13)). The point cloud geometry information, which includes the 3D coordinates of the points in the point cloud, may be encoded by partitioning an octree with partition occupancy information. The attributes may be compressed based on the reconstructed geometry using, for example, prediction, lifting, and adaptive area hierarchical transformation techniques.

[116] According to some aspects of the disclosure, three-dimensional space can be partitioned using octree partitioning. Octrees are the 3D analog of quadtrees in 2D. The octree splitting technique refers to a splitting technique that recursively divides three-dimensional space into eight octants, and the octree structure refers to a tree structure that represents partitions. In the example, each node in the octree structure corresponds to a 3D space, and the node can be a leaf node (no split, also called a leaf node in some examples) or an optional split node. The division at a node can divide the three-dimensional space represented by the node into eight octants. In some examples, nodes corresponding to sections of a particular node may be referred to as child nodes of the particular node.

[117] FIG. 9 is a diagram illustrating partitioning of a 3D cube (900) (corresponding to a node) based on an octree partitioning technique according to some embodiments of the present disclosure. The partition may divide the 3D cube (900) into eight smaller 0-7 cubes of equal size, as shown in FIG. 9.

[118] An octree partitioning technique (eg, in TMC13) can recursively partition the original 3D space into smaller units, and the occupancy information of each subspace can be encoded to represent geometry positions.

[119] In some embodiments (eg, TMC13), a geometry octree codec is used. The geometry octree codec can perform geometry encoding. In some examples, geometry encoding is performed on a cubic rectangle. For example, a cubic rectangle could be an axis-aligned B bounding box that is defined by two points (0,0,0) and (2 ^M-1 , 2 ^M-1 , 2 ^M-1 ), where 2 ^M-1 specifies the size of the bounding box. rectangles B and M can be specified in the bitstream.

[120] The octree structure is then built by recursively dividing the cubic block. For example, a cubic block defined by two points (0,0,0), (2 ^M-1 , 2 ^M-1 , 2 ^M-1 ) is divided into 8 sub-cubic blocks, then an 8-bit code called a busy code is generated. Each bit of the busy code is associated with a subcube block, and the value of this bit is used to indicate whether the associated subcube block contains any point cloud points. For example, a bit value of 1 indicates that the subcube block associated with the bit contains one or more point cloud points; and a bit value of 0 indicates that the subcube block associated with the bit does not contain a point cloud point.

[121] In addition, in the case of an empty subcubic block (eg, the value of the bit associated with the subcubic block is 0), division is no longer applied to the subcubic block. When a subcube block has one or more point cloud points (e.g., the value of a bit associated with the subcube block is 1), the subcube block is further divided into 8 smaller subcube blocks, and an occupancy code may be generated for the subcube block to indicate the occupancy of the smaller subcube blocks. blocks. In some examples, sub-division operations may be repeatedly performed on non-empty sub-cube blocks until the size of the sub-cubic blocks becomes equal to a predetermined threshold, for example, the size is 1. In some examples, sub-cubic blocks of size 1 are called voxels, and sub-cubic blocks whose size exceeds the size of voxels, may be called non-voxels.

[122] FIG. 10 shows an example of an octree split (1010) and an octree structure (1020) corresponding to an octree split (1010), according to some embodiments of the invention. Fig. 10 shows two levels of division in division (1010) of the octree. The octree structure (1020) includes a node (N0) corresponding to a cube block for dividing (1010) the octree. At the first level, the cubic block is divided into 8 subcubic blocks, which are numbered from 0 to 7 according to the numbering method shown in FIG. 9. The occupancy code for the partition of node N0 is "10000001" in binary, indicating that the first subcubic block represented by node N0-0 and the eighth subcubic block represented by node N0-7 include points in the point cloud, and the other subcubic boxes are empty.

[123] Then, in the second partitioning level, the first subcubic block (represented by node N0-0) and the eighth subcubic block (represented by node N0-7) are further subdivided into eight octants, respectively. For example, the first subcubic block (represented by node N0-0) is divided into 8 smaller subcubic blocks that are numbered 0 to 7 according to the numbering method shown in FIG. 9. The busy code for the section of node N0-0 is "00011000" in binary, indicating that the fourth smaller subcubic block (represented by node N0-0-3) and the fifth smaller subcubic block (represented by node N0-0-3) 4) include points in the point cloud, and other smaller subcubic rectangles are empty. At the second level, the seventh subcubic block (represented by node N0-7) is likewise divided into 8 smaller subcubic blocks, as shown in FIG. 10.

[124] FIG. 10, nodes corresponding to a non-empty cubic space (eg, a cubic box, subcubic blocks, smaller subcubic blocks, etc.) are colored gray and are referred to as shaded nodes.

[125] According to some aspects of the disclosure, busy codes may be appropriately compressed using suitable encoding techniques. In some embodiments, an arithmetic encoder is used to compress the current node's busy code into an octree structure. The busy code can be denoted as S, which is an 8-bit integer, and each bit in S indicates the busy status of a child node of the current node. In an embodiment, the busy code is encoded using bit coding. In another embodiment, the busy code is encoded using byte coding. In some examples (eg TMC13) bit encoding is enabled by default. Both bit coding and byte coding can perform context modeling arithmetic coding to encode the busy code. The context status may be initialized at the start of the entire encoding process for busy codes and updated during the encoding process for busy codes.

[126] In a bitwise encoding embodiment for encoding a busy code for the current node, the eight bins in S for the current node are encoded in a certain order. Each bin in S is encoded by referring to the occupancy status of neighboring nodes of the current code and/or children of neighboring nodes. Neighbor nodes are at the same level as the current node and may be referred to as sibling nodes of the current node.

[127] In a byte-by-byte encoding embodiment for encoding the current node's busy code, the busy code S (one byte) can be encoded by referring to: (1) an adaptive lookup table (A-LUT) that keeps track of P (e.g., 32) most frequently employment codes used; and (2) a cache that keeps track of the last different observed Q (eg, 16) busy codes.

[128] In some examples of byte coding, a binary flag is encoded indicating whether S is in the A-LUT or not. If S is in A-LUT, the index in A-LUT is encoded using a binary arithmetic encoder. If S is not in the A-LUT, then a binary flag is encoded indicating whether S is in the cache or not. If S is in the cache, then the binary representation of its cache index is encoded using a binary arithmetic encoder. Otherwise, if S is not in the cache, the binary representation of S is encoded using a binary arithmetic encoder.

[129] In some embodiments, at the decoder side, the decoding process may begin by parsing the dimensions of the bounding box from the bitstream. The bounding box points to a cubic rectangle corresponding to a root node in the octree structure to partition the cubic rectangle according to point cloud geometry information (eg, occupancy information for points in the point cloud). Then, an octree structure is built by dividing the cube block according to the decoded occupancy codes.

[130] In some related examples (eg, in the TMC13 version), the octree structure is looked up in widthwise order to encode busy codes. According to breadth-first order, octree nodes (nodes in the octree structure) in a level can be visited after visiting all nodes of the top-level octree. In an example implementation, a first-in-first-out (FIFO) data structure may be used.

[131] FIG. 11 shows an octree structure diagram (1100) illustrating a width-encoding order. Shaded nodes in the octree structure (1100) are nodes corresponding to cubic spaces that are not empty. The busy codes for the shaded nodes may be encoded in a width-coding order from 0 to 8, as shown in FIG. 11. In width-encoding order, the nodes of the octree are visited incrementally. The width-encoding order by itself is not suitable for parallel processing because the current layer must wait for the top-level encoding.

[132] Some aspects of the disclosure provide for a hybrid coding order that includes at least one layer that is encoded using a depth-encoding order instead of a width-encoding order. Thus, in some embodiments, a node at a depth-encoding level and descendant nodes of that node may form a sub-octree structure within an octree structure. When the first depth-encoding level includes multiple nodes corresponding to non-empty cubic spaces, the multiple nodes and their respective descendant nodes may form multiple sub-octree structures. Multiple sub-octree structures may be encoded in parallel in some embodiments.

[133] FIG. 12 shows an octree structure diagram (1200) illustrating the depth-coding order. Shaded nodes in the octree structure (1200) are nodes corresponding to cubic spaces that are not empty. The octree structure (1200) may correspond to the same point cloud occupancy geometry as the octree structure (1100). The busy codes for the shaded nodes may be coded in depth-coding order from 0 to 8, as shown in FIG. 12.

[134] In the example of FIG. 12, node "0" may be at any suitable split depth such as PD0, node "0"'s children are at split depth PD0+1, and node "0"'s children are at split depth PD0+2. In the example of FIG. 12, nodes with a separation depth of PD0+1 may be encoded in depth-coding order. The nodes at section depth PD0+1 include two nodes that correspond to non-empty space. The two nodes and their descendant nodes, respectively, may form a first suboctree structure (1210) and a second suboctree structure (1220), these two nodes may respectively be referred to as the root nodes of the two suboctree structures.

[135] The depth-coding order in FIG. 12 is referred to as the preorder version for the depth-coding order. In the depth-coding order preorder version, for each suboctree structure, the root node of the suboctree is visited first before visiting the child nodes of the suboctree structure. In addition, the deepest node is visited first, and then the parent node's siblings are fed back.

[136] FIG. 12, the first suboctree structure (1210) and the second suboctree structure (1220) may be coded in parallel processing in some implementations. For example, node 1 and node 5 can be visited at the same time. In some examples, recursive programming or a stack data structure may be used to implement a depth-coding order.

[137] In some embodiments, the implementation of the hybrid order of coding begins with a width-traversal (coding), and after several levels of width-traversal, depth-traversal (coding) may be allowed.

[138] It should be noted that the hybrid coding order can be used in any suitable PCC system, such as a TMC13 PCC system, an MPEG-PCC PCC system, and the like.

[139] According to an aspect of the disclosure, a hybrid coding order may include both a width coding order and a depth coding order for encoding point cloud geometry information. In an embodiment, the node size of the nodes in the octree structure can be set to change from width-encoding order to depth-encoding order. In the example, during PCC, the encoding of the octree structure starts from the width encoding order, and at the level where the node size is equal to the specified node size for encoding order change, the encoding order may change to the depth encoding order. It should be noted that in some examples the size of the node is associated with the depth of the section.

[140] In another embodiment, a node size for nodes in the octree structure can be specified to change from depth-encoding order to width-encoding order. In the example, during PCC, the encoding of the octree structure starts from the depth-coding order, and at the level where the node size is equal to the specified node size for encoding order change, the encoding order may change to the width-coding order. It should be noted that in some examples the size of the node is associated with the depth of the section.

[141] More specifically, in an embodiment, starting from a width-encoding order, the size of a node can be represented in log2 scale and denoted as d=0.1,..., M-1, where M-1 is the size of the root node and M is the maximum number of octree split depths (also referred to as levels in some examples). In addition, a parameter d _t , which is called the coding reorder size, can be defined. For example, the specified parameter d _t (1≤d _t ≤M-1) is used to specify that the width order applies to nodes from size M-1 to d _t , and the depth order applies to nodes from size d _t -1 to 0. When d _t =M-1, the depth-scheme is applied to all nodes of the octree from the root node. When d _t =1, the octree structure is only encoded using a width-encoding order.

[142] In some embodiments, the encoding order for the octree structure may start with the width encoding order, then at a particular depth (corresponding to a particular node size), each node at a particular depth, and descendant nodes of that node form a separate point cloud sub-octree structure. Thus, multiple sub-octree structures are formed at a specific depth. The sub-octree structures may be separately encoded using any suitable encoding mode. For example, a sub-octree structure may be encoded using a depth-encoding order. In another example, the sub-octree structure may be encoded using a width-encoding order. In another example, the sub-octree structure may be encoded using a hybrid encoding order. In another example, the busy codes in the sub-octree structure may be encoded using a bitwise encoding scheme. In another example, the busy codes in the sub-octree structure may be encoded using a byte-by-byte encoding scheme. In another example, the sub-octree structure may be encoded using a geometry predictive encoding method, which is an alternative encoding mode to the octree depth-encoding mode. The geometry predictive coding technique can predict points based on previously coded neighbor points with coded correction vectors in some examples.

[143] In some embodiments, at the encoder side, for each sub-octree structure, the encoder may select an encoding mode from a plurality of encoding modes based on encoding efficiency. For example, the selected encoding mode for the sub-octree structure may provide the best encoding efficiency for the sub-octree structure. The encoder may then use the appropriately selected encoding modes for the sub-octree structures to encode the sub-octree structures accordingly. In some embodiments, the encoder may signal an index for the sub-octree structure in the bitstream, and this index indicates the selected encoding mode for the sub-octree structure. On the decoder side, the decoder may determine the encoding mode for the sub-octree structure based on the index in the bitstream, and then decode the sub-octree structure according to the encoding mode.

[144] Aspects of the present disclosure also provide signaling techniques for hybrid coding order. According to an aspect of the disclosure, the control parameters to be used in the hybrid coding order may be signaled in high level syntax such as sequence parameter set (SPS), slice header, bitstream geometry parameter set, and the like. It should be noted that the following description provides specific examples. The disclosed methods, illustrated with specific examples, are not limited to specific examples, and may be adjusted accordingly and used in other examples.

[145] In one embodiment, the parameter d _t (encoding reorder size) is indicated in the high-level syntax.

[146] FIG. 13 shows an example syntax (1300) of a set of geometry parameters according to some embodiments of the invention. As shown (1310), gps_depth_first_node_size_log2_minus_1 is specified in the geometry parameter set. The parameter d _t may be determined based on gps_depth_first_node_size_log2_minus_1, for example, according to (Eq. 1).

[147] It should be noted that when gps_depth_first_node_size_log2_minus_1 is equal to 0, depth-coding order is disabled.

[148] In another embodiment, a control flag is explicitly signaled to indicate whether a hybrid coding order is used.

[149] FIG. 14 shows another example (1400) of geometry parameter set syntax according to some embodiments of the invention. As shown at (1410), a control flag designated gps_hybrid_coding_order_flag is used. When the gps_hybrid_coding_order_flag control flag is true (eg, has a value of 1), the hybrid coding order scheme is enabled; when gps_hybrid_coding_order_flag is false (eg, set to 0), the hybrid coding order scheme is disabled. When gps_hybrid_coding_order_flag is true (for example, has the value 1), the parameter d _t can be determined based on gps depth_first_node_size_log2_minus_2, for example, according to (Eq. 2):

When gps_hybrid_coding_order_flag is false (eg, has a value of 0), d _t defaults to 1 to indicate that depth-coding order is disabled, and only width-coding order is applied in the example.

[150] In one embodiment, when hybrid coding order is enabled, widthwise order applies to nodes from size M-1 to d _t , and depth order applies to nodes from size d _t -1 to 0.

[151] FIG. 15 shows an example (1500) of pseudocode for encoding an octree according to some embodiments of the disclosure. As shown in (1510), when depth>=MaxGeometryOctreeDepth - d _t , depth-encoding order can be used. In FIG. 15, for example, the pseudo-code "geometry_node_depth_first" may be applied to the depth-coding order.

[152] FIG. 16 shows an example (1600) of pseudocode for a depth-coding order according to some embodiments of the disclosure. The pseudocode "geometry_node_depth_first" is a recursive function. In the recursive function, the "geometry_node" function is first called to get the busy code for the current octree node, and then the "geometry_node_depth_first" pseudo-code is called by itself to encode each child node until the leaf nodes are reached, for example, when depth >=MaxGeometryOctreeDepth-1.

[153] FIG. 17 illustrates a flowchart describing a process (1700) according to an embodiment of the invention. Process (1700) may be used in a point cloud encoding process. In various embodiments, the process (1700) is performed by a processing circuit, such as a processing circuit in terminal devices (110), a processing circuit that performs the functions of an encoder (203) and/or a decoder (201), a processing circuit that performs the functions of an encoder (300 ), a decoder (400), an encoder (700), and/or a decoder (800), and the like. In some embodiments, the process (1700) is implemented in program instructions, such that when the processing circuit executes the program instructions, the processing circuit executes the process (1700). The process starts at (S1701) and proceeds to (S1710).

[154] In step (S1710), an encoded bitstream for the point cloud is obtained. The encoded bitstream includes geometry information in the form of encoded busy codes for the nodes in the octree structure for the point cloud. The nodes in the octree structure correspond to three-dimensional (3D) divisions of point cloud space. The node sizes are associated with the sizes of the respective 3D partitions.

[155] In step (S1720), the busy codes for the nodes are decoded from the encoded busy codes. At least a first busy code for a child node of the first node is decoded without waiting for decoding of a second busy code for a second node having the same node size as the first node.

[156] In one embodiment, the child node is among the first set of nodes (first child nodes) in the first sub-octtree, the first node being the root node of the first sub-octtree. The first node and the second node are sibling nodes with the same node size. The second node is the root node of the second sub-octree, which includes the second set of nodes (the second child nodes). Then, in some examples, the first set of busy codes for the first set of nodes and the second set of busy codes for the second set of nodes may be separately decoded. In one example, the first set of busy codes for the first set of nodes and the second set of busy codes for the second set of nodes may be decoded in parallel. In another example, a first set of busy codes for a first node set is decoded using a first coding mode, and a second set of busy codes for a second node set is decoded using a second coding mode.

[157] The first coding mode and the second coding mode may use any of a depth coding order, a width coding order, a geometry predictive coding method, and the like. In some examples, the encoded bitstream includes a first index that indicates a first encoding mode for the first sub-octree and a second index that indicates a second encoding mode for the second sub-octree.

[158] In another embodiment, the first node and the second node have a specific node size to change the encoding order. In some examples, larger knots in knots are encoded using a first encoding order, and smaller knots in knots are encoded using a second encoding order. The node sizes of larger nodes are larger than the specific node size to change the encoding order. The node sizes of the smaller nodes are equal to or smaller than the specific node size to change the encoding order. In one example, the first encoding order is the width encoding order and the second encoding order is the depth encoding order. In another example, the first encoding order is depth-encoding order and the second encoding order is width-encoding order.

[159] In some examples, a specific node size for reordering the coding is determined based on the signal in the encoded bitstream for the point cloud. In some examples, a signal is provided when the control signal indicates a change in coding order.

[160] In step (S1730), the octree structure can be reconstructed based on the decoded busy codes for the nodes.

[161] In step (S1740), the point cloud is reconstructed based on the octree structure. Then, the process proceeds to (S1799) and ends.

[162] The methods described above may be implemented in computer software using computer-readable instructions and physically stored on one or more computer-readable media. For example, in FIG. 18 shows a computer system (1800) suitable for implementing certain embodiments of the disclosed subject matter.

[163] Computer software may be coded using any suitable machine code or computer language, which may be the object of assembly, compilation, linking, or similar mechanisms to produce code containing instructions that can be executed directly or through interpretation, execution of microcode, etc. .p., one or more computer central processing units (CPUs), graphics processing units (CPUs), and the like.

[164] The instructions may be executed on various types of computers or components thereof, including, for example, personal computers, tablet computers, servers, smartphones, gaming devices, IoT devices, and the like.

[165] The components shown in FIG. 18 for a 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 invention. The configuration of the components is also not to be interpreted as having any dependency or requirement relating to any one or combination of the components illustrated in the exemplary embodiment of the computer system (1800).

[166] The computer system (1800) may include certain human-machine interface input devices. Such a human-machine interface input device may respond to input from one or more human users through, for example, tactile input (e.g., keystrokes, swipes, movement of a control glove), audio input (e.g., voice, handclaps), visual input (for example: gestures), olfactory input (not shown). HMI devices can also be used to capture certain media not necessarily directly related to conscious human input, such as sound (e.g. speech, music, ambient sound), images (e.g. scanned images, photographic images taken from a camera for still images), video (eg 2D video, 3D video including stereoscopic video).

[167] Human interface input devices may include one or more of the following (only one of each is shown): keyboard (1801), mouse (1802), trackpad (1803), touch screen (1810), control glove (not shown), joystick (1805), microphone (1806), scanner (1807), camera (1808).

[168] The computer system (1800) may also include certain human-machine interface output devices. Such human interface output devices can stimulate the senses of one or more human users through, for example, tactile output, sound, light, and smell/taste. Such human interface output devices may include tactile output devices (e.g., tactile feedback from a touch screen (1810), operating glove (not shown), or joystick (1805), but there may also be tactile feedback devices that do not serve as input devices), audio output devices (for example: speakers (1809), headphones (not shown)), image output devices (for example, screens (1810), including CRT screens, LCD screens, plasma screens, OLED - screens, each with or without touchscreen input capability, each with or without tactile feedback capability - some of which may be capable of outputting 2D visual output or more than 3D output by means such as stereographic output ; virtual reality goggles (not shown), holographic displays and smoke tanks (not shown)) and printers (not shown).

[169] The computer system (1800) may also include human accessible storage devices and associated media such as optical media including CD/DVD ROM/RW (1820) with CD/DVD or similar media (1821), flash drive (1822), removable hard drive or solid state drive (1823), legacy magnetic media such as tape and floppy disk (not shown), specialized ROM/ASIC/PLD based devices such as dongles (not shown), and etc.

[170] 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 time signals.

[171] The computer system (1800) may also include an interface to one or more communication networks. Networks can be, for example, wireless, wired, optical. In addition, networks can be local, wide area, metropolitan, automotive, industrial, real-time, latency tolerant, and so on. Example networks include local area networks such as Ethernet, wireless LANs, cellular networks including GSM, 3G, 4G, 5G, LTE, etc., wired television or wireless digital wide area networks including cable television, satellite television and terrestrial TV broadcasting, automotive and industrial equipment, including CAN bus, etc. Some networks typically require external network interface adapters that are connected to certain general purpose data ports or peripheral buses (1849) (for example, computer system USB ports (1800)); others are typically integrated into the computer system core (1800) by being attached 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 can be unidirectional, receive-only (for example, broadcast television), unidirectional, send-only (for example, CAN bus to certain CAN-bus devices), or bidirectional, for example, to other computer systems using a local or wide area digital network. . Each of these networks and network interfaces may use specific protocols and protocol stacks as described above.

[172] The aforementioned human-machine interface devices, human-accessible storage devices, and network interfaces may be attached to the core (1840) of the computer system (1800).

[173] The core (1840) may include one or more central processing units (CPUs) (1841), graphics processing units (GPUs) (1842), custom field programmable gate array (FPGA) processors (1843), hardware accelerators (1844) for certain tasks, etc. These devices, along with Read Only Memory (ROM) (1845), Random Access Memory (1846), internal storage devices such as internal non-user hard drives, solid state drives, and the like. (1847) can be connected via the system bus (1848). In some computer systems, the system bus (1848) may be available as one or more physical connectors to allow expansion with additional CPUs, GPUs, or the like. Peripherals can be connected either directly to the system bus (1848) of the kernel, or via a peripheral bus (1849). Peripheral bus architecture includes PCI, USB, etc.

[174] CPUs (1841), GPUs (1842), FGPAs (1843), and accelerators (1844) may execute certain instructions, which in combination may constitute the aforementioned computer code. This computer code can be stored in ROM (1845) or RAM (1846). Transient data may also be stored in RAM (1846), while permanent data may be stored, for example, in an internal mass storage (1847). Fast storage and retrieval to any of the storage devices can be enabled through the use of cache memory, which can be tightly coupled to one or more CPU (1841), GPU (1842), storage device (1847), ROM (1845), RAM (1846) and the like.

[175] The computer-readable medium may contain computer code for performing various computer-implemented operations. The media and computer code may be specially designed and constructed for the purposes of the present invention, or they may be well known and available to those skilled in the art of computer software.

[176] By way of example, and not limitation, a computer system having an architecture (1800), and in particular a core (1840), may provide functionality through processor(s) (including CPUs, GPUs, FPGAs, accelerators, etc.) executing software embodied on one or more tangible machine-readable media. Such computer-readable media may be media associated with user accessible mass storage as described above, as well as certain kernel storage (1840) that is non-transitory in nature, such as internal kernel mass storage (1847) or ROM (1845). Software implementing various embodiments of the present disclosure may be stored on such devices and executed by the kernel (1840). The computer-readable medium may include one or more memory devices or microchips, as appropriate. The software may direct the core (1840), and in particular the processors within it (including CPUs, GPUs, FPGAs, and the like), to execute certain processes or certain portions of specific processes described herein, including defining data structures stored in RAM (1846), and modifying such data structures according to software defined processes. In addition or alternatively, a computer system may provide functionality as a result of logic embedded in, or otherwise embodied in, circuitry (e.g., an accelerator (1844)) that may operate in place of or in conjunction with software to perform certain processes or individual parts of the specific processes described in this document. The link to the software may include logic and vice versa where applicable. A reference to a computer-readable medium may include circuitry (eg, an integrated circuit (IC)) storing software to execute, circuitry implementing logic to execute, or both, where applicable. The present invention includes any suitable combination of hardware and software.

[177] Although this description discloses several exemplary embodiments, there are variations, permutations, and various replacement equivalents that fall within the scope of the invention. Thus, it will be appreciated that those skilled in the art will be able to develop numerous systems and methods that, although not explicitly shown or described herein, embody the principles of the invention and thus are within its spirit and scope.

Claims (51)

1. A method for restoring a point cloud from an encoded point cloud stream, comprising: deriving, by the processor, from the encoded bitstream for the point cloud, encoded occupancy codes for nodes in the octree structure for the point cloud, the nodes in the octree structure corresponding to three-dimensional (3D) sections of the point cloud space, the sizes of the nodes being associated with the sizes of the corresponding 3D sections ; decoding, by the processor, from the encoded busy codes, the busy codes for the nodes, wherein at least a first busy code for a child node of the first node is decoded without waiting for a second busy code to be decoded for a second node having the same node size as the first node; restoring, by the processor, the octree structure based on the decoded busy codes for the nodes; And restoring, by the processor, a point cloud based on the octree structure; And additionally containing: decoding a first part of busy codes for larger nodes in nodes using a first coding order, with larger nodes larger than a specific node size, to change the coding order; And decoding the second part of the busy codes for the smaller nodes in the nodes using a second coding order that is different from the first coding order, wherein the smaller nodes are equal to or less than a specific node size to change the coding order. 2. The method according to p. 1, further comprising: decoding a first set of busy codes for a first set of nodes in the first sub-octtree, the first node being the root of the first sub-octtree; And decoding the second set of busy codes for the second set of nodes in the second sub-octtree, the second node being the root of the second sub-octtree. 3. The method of claim 2, further comprising: decoding the first set of busy codes for the first set of nodes in the first sub-octtree, in parallel with decoding the second set of busy codes for the second set of nodes in the second sub-octtree. 4. The method according to p. 2, further comprising: decoding, using the first coding mode, the first set of busy codes for the first set of nodes in the first sub-octree; And decoding, using the second encoding mode, the second set of busy codes for the second set of nodes in the second sub-octree. 5. The method of claim 4, further comprising: decoding, from the encoded bitstream, a first index indicating a first encoding mode for the first sub-octree; And decoding, from the encoded bitstream, a second index indicating a second encoding mode for the second sub-octree. 6. The method of claim 1, wherein the first encoding order is a width encoding order and the second encoding order is a depth encoding order. 7. The method of claim 1, wherein the first encoding order is a depth-encoding order and the second encoding order is a width-encoding order. 8. The method according to p. 1, also containing: determining a specific node size for reordering an encoding based on a signal in the encoded bitstream for the point cloud. 9. The method of claim 8, further comprising: decoding a control signal from the encoded bitstream for the point cloud, the control signal indicating a change in coding order. 10. A device for recovering a point cloud from an encoded point cloud stream, comprising: processing scheme configured for: deriving, from the encoded bitstream for the point cloud, encoded occupancy codes for nodes in the octree structure for the point cloud, the nodes in the octree structure corresponding to three-dimensional (3D) partitions of the point cloud space, the sizes of the nodes being associated with the sizes of the respective 3D partitions; decoding, from the encoded occupancy codes, occupancy codes for the nodes, wherein at least a first occupancy code for a child node of the first node is decoded without waiting for a second occupancy code to be decoded for a second node having the same node size as the first node; restoring the octree structure based on the decoded busy codes for the nodes; And restoring the point cloud based on the octree structure, wherein the processing circuit is configured to: decoding the first part of the busy codes for the larger nodes in the nodes using the first coding order, with the larger nodes larger than the specific node size to change the coding order; And decoding the second part of the busy codes for the smaller nodes in the nodes using a second coding order that is different from the first coding order, wherein the smaller nodes are equal to or less than a specific node size to change the coding order. 11. The apparatus of claim 10, wherein the processing circuitry is configured to: decoding a first set of busy codes for a first set of nodes in the first sub-octtree, the first node being the root of the first sub-octtree; And decoding the second set of busy codes for the second set of nodes in the second sub-octtree, the second node being the root of the second sub-octtree. 12. The apparatus of claim 11, wherein the processing circuitry is configured to: decoding the first set of busy codes for the first set of nodes in the first sub-octtree in parallel with the second set of busy codes for the second set of nodes in the second sub-octtree. 13. The apparatus of claim 11, wherein the processing circuitry is configured to: decoding, using the first encoding mode, the first set of busy codes for the first set of nodes in the first sub-octree; And decoding, using the second encoding mode, the second set of busy codes for the second set of nodes in the second sub-octree. 14. The apparatus of claim 13, wherein the processing circuitry is configured to: decoding, from the encoded bitstream, a first index indicating a first encoding mode for the first sub-octree; And decoding, from the encoded bitstream, a second index indicating a second encoding mode for the second sub-octree. 15. The apparatus of claim 10, wherein the first encoding order is a width encoding order and the second encoding order is a depth encoding order. 16. The apparatus of claim 10, wherein the first encoding order is a depth encoding order and the second encoding order is a width encoding order. 17. The apparatus of claim 10, wherein the processing circuitry is configured to: determining a specific node size to reorder encoding based on a signal in the encoded bitstream for the point cloud. 18. The apparatus of claim 17, wherein the processing circuitry is configured to: decoding a control signal from the encoded bitstream for the point cloud, the control signal indicating a change in coding order.

Images