Apple Patent | Geometry encoding using octrees and predictive trees

Patent: Geometry encoding using octrees and predictive trees

Drawings: Click to check drawins

Publication Number: 20210217206

Publication Date: 20210715

Applicant: Apple

Assignee: Apple Inc.

Abstract

An encoder is configured to compress point cloud geometry information using an octree/predictive tree combination geometric compression technique that embeds predictive trees in leaf nodes of an octree instead of encoding additional octree occupancy symbols for the leaf nodes. Alternatively an encoder may be configured to embed octrees in leaf nodes of a predictive tree structure. Similarly a decoder is configured to generate a reconstructed three-dimensional geometry from a bit stream including combined octree and predictive tree encoding information.

Claims

1. A non-transitory, computer readable, medium storing program instructions, that when executed by one or more processors, cause the one or more processors to: partition a plurality of points of three-dimensional (3D) volumetric content into an octree comprising a plurality of cubes and sub-cubes at different levels of the octree; and for a set of occupied cubes, occupied with two or more points, at a given octree level: determine whether respective ones of the occupied cubes are to be further partitioned or whether the two or more points of the respective cubes are to be defined using a predictive tree structure; determine occupancy symbols indicating occupancy states of the sub-cubes of the cubes at the given octree level that are to be further partitioned; determine predictive tree structures for other ones of the respective occupied cubes corresponding to nodes of the octree that are not to be further partitioned; and encode the occupancy symbols and the predictive tree structures in an encoded bit stream for the 3D volumetric content.

2. The non-transitory, computer-readable, medium of claim 1, wherein to determine the occupancy symbols, determine the predictive tree structures, and encode the occupancy symbols and the predictive tree structures in the encoded bit stream, the program instructions, when executed by the one or more processors, cause the one or more processors to: traverse the octree in a breadth-first order for a plurality of levels of the octree; encode the occupancy symbols determined for the plurality of levels of the octree; and encode the predictive tree structures determined for the other ones of the respective occupied nodes of the octree that are not to be further partitioned.

3. The non-transitory, computer-readable, medium of claim 1, wherein to determine the occupancy symbols, determine the predictive tree structures, and encode the occupancy symbols and the predictive tree structures in the encoded bit stream, the program instructions, when executed by the one or more processors, cause the one or more processors to: traverse the octree in a breadth-first order for a given level of the octree; encode occupancy symbols determined for sub-cubes of the given level of the octree that are to be further partitioned; encode predictive tree structures determined for other ones of the occupied nodes of the given level of the octree that are not to be further partitioned; and repeat said traversing, said encoding the occupancy symbols, and said encoding the predictive tree structures for one or more additional levels of the octree.

4. The non-transitory, computer-readable, medium of claim 1, wherein to encode the occupancy symbols and the predictive tree structures in the encoded bit stream, the program instructions, when executed by the one or more processors, cause the one or more processors to: encode a flag value for the nodes of the octree that are not to be further partitioned for which a predictive tree structure is being encoded.

5. The non-transitory, computer-readable, medium of claim 4, wherein to encode the occupancy symbols and the predictive tree structures in the encoded bit stream, the program instructions, when executed by the one or more processors, further cause the one or more processors to: determine respective contexts for respective ones of the nodes of the octree that are not to be further partitioned; and determine whether or not to encode a flag value indicating an associated encoded predictive tree structure for the nodes that are not to be further partitioned based on determined contexts for one or more neighboring nodes of a given one of the nodes that is not to be further partitioned that is being evaluated.

6. The non-transitory, computer-readable, medium of claim 1, wherein the determined predictive tree structures comprise one or more of: a prediction tree structure that indicates prediction is to be performed based on a position of the node that is not to be further partitioned; a prediction tree structure that indicates prediction is to be performed based on a position of a parent node in the octree corresponding to the node that is not to be further partitioned; or a prediction tree structure that indicates prediction is to be performed based on a position of a parent node and grand-parent node in the octree corresponding to the node that is not to be further partitioned.

7. The non-transitory, computer-readable, medium of claim 1, wherein, the program instructions, when executed by the one or more processors, further cause the one or more processors to: encode residual values to be used to corrected predicted locations predicted using the predictive tree-structures signaled in the bit stream.

8. The non-transitory, computer-readable, medium of claim 1, wherein for a given one of the nodes that is not to be further partitioned, a given predictive tree structure for the given node is contained within a volume of the sub-cube corresponding to the given node.

9. The non-transitory, computer-readable, medium of claim 1, wherein for a given one of the nodes that is not to be further partitioned, a given predictive tree structure for the given node extends at least partially beyond a volume of the sub-cube corresponding to the given node.

10. The non-transitory, computer-readable, medium of claim 1, wherein for at least one of the occupied sub-cubes of the octree that is not to be further partitioned in the octree, the program instructions, when executed by the one or more processors, cause the one or more processors to: perform said determining the predictive tree structure; and for at least one branch of the predictive tree structure: determine an additional octree for a set of points in the at least one occupied sub-cube, wherein a leaf node of the at least one branch of the predictive tree serves as a seed node for the additional octree; and encode the additional octree in the bit stream.

11. The non-transitory, computer-readable, medium of claim 10, wherein the program instructions, when executed by the one or more processors, cause the one or more processors to: determine another predictive tree structure for at least one node of the additional octree that is not to be further partitioned; and encode the additional predictive tree in the bit stream.

12. A non-transitory, computer readable, medium storing program instructions, that when executed by one or more processors, cause the one or more processors to: receive a bit stream comprising encoded octree occupancy symbols and encoded indicators of predictive tree structures for use in recreating a 3D representation of compressed volumetric content; and reconstruct the 3D representation of compressed volumetric content, wherein to reconstruct the 3D representation of compressed volumetric content, the program instructions, when executed by the one or more processors, cause the one or more processors to: decode the encoded occupancy symbols to re-create an octree structure; predict locations of points included in the predictive tree structures; and spatially locate the points predicted via the predictive tree structures in a set of points whose locations are indicated by the re-created octree structure.

13. The non-transitory, computer readable, medium of claim 12, wherein to spatially locate the points predicted via the predictive tree structures the program instructions, when executed by one or more processors, cause the one or more processors to: determine a local origin point for the predictive tree, wherein the local origin point is associated with a sub-cube of the reconstructed octree and a corresponding node of the reconstructed octree with which the predictive tree structure is associated; predict locations of points of the predictive tree structure from a global origin point; determine a transfer function that translates global origin to the local origin such that the points of the predictive tree structure are relocated from a position relative to the global origin point to new locations relative to the local origin point in the sub-cube corresponding to the node of the octree with which the predictive tree structure is associated; and apply the transfer function to the predicted locations of the points of the predictive tree to move the points of the predicted tree.

14. The non-transitory, computer readable, medium of claim 12, wherein to spatially locate the points predicted via the predictive tree structures the program instructions, when executed by one or more processors, cause the one or more processors to: determine a local origin point for the predictive tree, wherein the local origin point is associated with a sub-cube of the reconstructed octree and a corresponding node of the reconstructed octree with which the predictive tree structure is associated; and predict locations of points of the predictive tree structure from the local origin point.

15. The non-transitory, computer readable, medium of claim 12, wherein the local origin point is one or more of the following: a corner of the sub-cube corresponding to the node of the octree with which the predictive tree structure is associated; a center points of the sub-cube corresponding to the node of the octree with which the predictive tree structure is associated; or a point defined by a function that uses a location of the sub-cube corresponding to the node of the octree with which the predictive tree structure is associated is an input to the function.

16. The non-transitory, computer-readable, medium of claim 12, wherein the received encoded bit stream further comprises residual values for the predictive tree, and wherein the program instructions, when executed by the one or more processors, further cause the one or more processors to: adjust the predicted locations of the points included in the predictive tree structures based on the residual values included in the bit stream for the predictive tree structures.

17. A non-transitory, computer readable, medium storing program instructions, that when executed by one or more processors, cause the one or more processors to: determine a predictive tree-structure for use in predicting locations of a plurality of points included in three-dimensional (3D) volumetric content; and for at least one branch of the predictive tree-structure: partition a plurality of points of the 3D volumetric content associated with the at least one branch into an octree comprising a plurality of cubes and sub-cubes at different levels of the octree; determine occupancy symbols indicating occupancy states of the sub-cubes of the cubes; and encode the predictive tree structure and the occupancy symbols an encoded bit stream for the 3D volumetric content.

18. The non-transitory, computer-readable, medium of claim 17, wherein the program instructions, when executed by the one or more processors, further cause the one or more processors to: for a set of occupied cubes, occupied with two or more points, at a given octree level of the octree associated with the at least one branch of the predictive tree structure: determine whether respective ones of the occupied cubes are to be further partitioned or whether the two or more points of the respective cubes are to be defined using an additional predictive tree structure; determine occupancy symbols indicating occupancy states of the sub-cubes of the cubes at the given octree level that are to be further partitioned; determine one or more additional predictive tree structures for other ones of the respective occupied cubes corresponding to nodes of the octree that are not to be further partitioned; and encode the predictive tree structure, the occupancy symbols for the octree structure for the at least one branch of the predictive tree structure, and the one or more additional predictive tree structures in the encoded bit stream for the 3D volumetric content.

19. The non-transitory, computer-readable, medium of claim 17, wherein the at least one branch of the predictive tree structure that includes the octree comprises a portion of the 3D volumetric content that comprises densely populated points and that is adjacent to one or more other portions of the 3D volumetric content that is sparsely populated with points.

20. The non-transitory, computer-readable, medium of claim 19, wherein the program instructions, when executed by the one or more processors, further cause the one or more processors to: determine respective point densities for portions of the 3D volumetric content associated with respective branches of the predictive tree structure; for a branch having a point density greater than a threshold density, generate an octree for the points associated with the branch; and for another branch having a point density less than the threshold density, generate an additional predictive tree branch for the points associated with the branch.

21. The non-transitory, computer-readable, medium of claim 17, wherein the 3D volumetric content is a point cloud comprising a plurality of points, wherein respective ones of the points comprise spatial information for the point and/or attribute information for the point.

Description

PRIORITY CLAIM

[0001] This application claims benefit of priority to U.S. Provisional Application Ser. No. 62/959,099, entitled “GEOMETRY ENCODING USING OCTREES AND PREDICTIVE TREES”, filed Jan. 9, 2020, and which is incorporated herein by reference in its entirety.

BACKGROUND

Technical Field

[0002] This disclosure relates generally to compression and decompression of volumetric data, such as point cloud data, comprising a plurality of points, each having associated spatial and/or attribute information.

Description of the Related Art

[0003] Various types of sensors, such as light detection and ranging (LIDAR) systems, 3-D-cameras, 3-D scanners, etc. may capture data indicating positions of points in three dimensional space, for example positions in the X, Y, and Z planes. Also, such systems may further capture attribute information in addition to spatial information for the respective points, such as color information (e.g. RGB values), intensity attributes, reflectivity attributes, motion related attributes, modality attributes, or various other attributes. In some circumstances, additional attributes may be assigned to the respective points, such as a time-stamp when the point was captured. Points captured by such sensors may make up a “point cloud” or other type of volumetric data comprising a set of points each having associated spatial information and/or one or more associated attributes. In some circumstances, a point cloud may include thousands of points, hundreds of thousands of points, millions of points, or even more points. Also, in some circumstances, volumetric data may be generated, for example in software, as opposed to being captured by one or more sensors. In either case, such volumetric data may include large amounts of data and may be costly and time-consuming to store and transmit.

SUMMARY OF EMBODIMENTS

[0004] In some embodiments, a system includes one or more sensors configured to capture points that collectively make up a volumetric data set, such as a point cloud, wherein each of the points comprises spatial information identifying a spatial location of the respective point and/or attribute information defining one or more attributes associated with the respective point. The system also include an encoder configured to compress the spatial and/or attribute information for the points. The encoder is configured to partition the plurality of points of the point cloud into an octree comprising a plurality of cubes and sub-cubes at different levels of the octree, wherein respective ones of the cubes comprises eight sub-cubes. Additionally, the encoder is configured to, for at least some of the nodes of the octree further encode spatial information for the at least some nodes using a predictive tree structure. Alternatively, the encoder may be configured to organize points using a predictive tree structure that includes one or more octrees stemming from nodes of the predictive tree. For example, a point cloud comprising points in three dimensional space may be encoded as a predictive tree that joins a plurality of octrees into a structure that collectively represents the spatial information of the point cloud. Also, in some embodiments, adaptive octree models may be used that permit coding of non-cubic volumes, which may result in some nodes of the octree having four or two sub-volumes (e.g. cuboids).

[0005] In some embodiments, an encoder as described above may further encode duplicate points that reside at a same or similar spatial location in 3D space. In some embodiments, in order to encode duplicate points, an encoder may signal a number of duplicate points for a respective node of a predictive tree, a node of an octree, or a node of a structure that incorporates both octree(s) and predictive tree(s). For example, instead of encoding multiple predictive trees to define two points that share the same spatial location in 3D space, an encoder may encode a single predictive tree that defines the location of the node and may further signal a number of points that reside at the spatial location (e.g. two points, three points, etc.). In some embodiments, it may be more efficient from a compression and signaling perspective to signal a quantity of duplicate points at a given node as opposed to signaling an additional predictive tree or additional octree nodes that have the same spatial location as another point of a signaled predictive tree or octree node.

[0006] In some embodiments, a method may include signaling spatial information for volumetric data, such as that of a point cloud, using a combination of predictive trees and octrees, as discussed above and herein. Also the method may include signaling duplicative points for nodes of the predictive tree or octree, as discussed above and herein. In some embodiments, a method may include a decoder receiving compressed volumetric data that has been compressed using a combination octree and predictive tree structure and/or signaled duplicate points as discussed above and herein, wherein the decoder uses the compressed volumetric data to reconstruct a three-dimensional geometry of the volumetric data, such as a geometry of a point cloud.

[0007] In some embodiments, a non-transitory computer readable medium stores program instructions, that when executed by one or more processors, cause the one or more processor to encode or decode volumetric data using a combination of predictive trees and octrees and/or signaled duplicate points, as described herein.

[0008] Various examples are described herein in terms of a point cloud. However, the encoder/encoding techniques and the decoder/decoding techniques described herein may be applied to various other types of 3D volumetric content representations, including meshes, three-degree of freedom plus (3DOF+) scenes or as alternatively referred to in some contexts as MPEG MIV material, lightfields, or other types of six-degree of freedom (6DOF) content.

BRIEF DESCRIPTION OF THE DRAWINGS

[0009] FIG. 1A illustrates a system comprising a sensor that captures information for points of a point cloud and an encoder that compresses attribute information and/or spatial information of the point cloud, where the compressed point cloud information is sent to a decoder, according to some embodiments.

[0010] FIG. 1B illustrates a process for encoding spatial information of a point cloud using an octree-predictive tree combination structure, according to some embodiments.

[0011] FIG. 2 illustrates an example octree structure, according to some embodiments.

[0012] FIG. 3 illustrates an example octree-predictive tree combination structure, according to some embodiments.

[0013] FIG. 4 illustrates an example octree-predictive tree combination structure that allows the predictive tree to encode a point outside the boundaries of an octree cube in which the predictive tree resides, according to some embodiments.

[0014] FIG. 5A illustrates an example set of points that span three occupied octree nodes, according to some embodiments.

[0015] FIG. 5B illustrates an example embodiment wherein a predictive tree is constrained to its respective octree cube and three predictive trees are illustrated for the three occupied octree nodes, according to some embodiments.

[0016] FIG. 5C illustrates example embodiment wherein a predictive tree is not constrained to its respective octree cube and a single predictive tree encodes the points spanning the three occupied octree nodes, according to some embodiments.

[0017] FIG. 6A illustrates components of an encoder, according to some embodiments.

[0018] FIG. 6B illustrates components of a decoder, according to some embodiments.

[0019] FIG. 7 illustrates compressed point cloud information being used in a 3-D application, according to some embodiments.

[0020] FIG. 8 illustrates compressed point cloud information being used in a virtual reality application, according to some embodiments.

[0021] FIG. 9 illustrates an example computer system that may implement an encoder or decoder, according to some embodiments.

[0022] This specification includes references to “one embodiment” or “an embodiment.” The appearances of the phrases “in one embodiment” or “in an embodiment” do not necessarily refer to the same embodiment. Particular features, structures, or characteristics may be combined in any suitable manner consistent with this disclosure.

[0023] “Comprising.” This term is open-ended. As used in the appended claims, this term does not foreclose additional structure or steps. Consider a claim that recites: “An apparatus comprising one or more processor units … . ” Such a claim does not foreclose the apparatus from including additional components (e.g., a network interface unit, graphics circuitry, etc.).

[0024] “Configured To.” Various units, circuits, or other components may be described or claimed as “configured to” perform a task or tasks. In such contexts, “configured to” is used to connote structure by indicating that the units/circuits/components include structure (e.g., circuitry) that performs those task or tasks during operation. As such, the unit/circuit/component can be said to be configured to perform the task even when the specified unit/circuit/component is not currently operational (e.g., is not on). The units/circuits/components used with the “configured to” language include hardware–for example, circuits, memory storing program instructions executable to implement the operation, etc. Reciting that a unit/circuit/component is “configured to” perform one or more tasks is expressly intended not to invoke 35 U.S.C. .sctn. 112(f), for that unit/circuit/component. Additionally, “configured to” can include generic structure (e.g., generic circuitry) that is manipulated by software and/or firmware (e.g., an FPGA or a general-purpose processor executing software) to operate in manner that is capable of performing the task(s) at issue. “Configure to” may also include adapting a manufacturing process (e.g., a semiconductor fabrication facility) to fabricate devices (e.g., integrated circuits) that are adapted to implement or perform one or more tasks.

[0025] “First,” “Second,” etc. As used herein, these terms are used as labels for nouns that they precede, and do not imply any type of ordering (e.g., spatial, temporal, logical, etc.). For example, a buffer circuit may be described herein as performing write operations for “first” and “second” values. The terms “first” and “second” do not necessarily imply that the first value must be written before the second value.

[0026] “Based On.” As used herein, this term is used to describe one or more factors that affect a determination. This term does not foreclose additional factors that may affect a determination. That is, a determination may be solely based on those factors or based, at least in part, on those factors. Consider the phrase “determine A based on B.” While in this case, B is a factor that affects the determination of A, such a phrase does not foreclose the determination of A from also being based on C. In other instances, A may be determined based solely on B.

DETAILED DESCRIPTION

[0027] As data acquisition and display technologies have become more advanced, the ability to capture volumetric data, such as point clouds, comprising thousands or millions of points in 2-D or 3-D space, such as via LIDAR systems, has increased. Also, the development of advanced display technologies, such as virtual reality or augmented reality systems, has increased potential uses for volumetric data, such as point clouds. However, point cloud files are often very large and may be costly and time-consuming to store and transmit. For example, communication of point clouds over private or public networks, such as the Internet, may require considerable amounts of time and/or network resources, such that some uses of point cloud data, such as real-time uses, may be limited. Also, storage requirements of point cloud files may consume a significant amount of storage capacity of devices storing the point cloud files, which may also limit potential applications for using point cloud data.

[0028] In some embodiments, an encoder may be used to generate a compressed point cloud to reduce costs and time associated with storing and transmitting large point cloud files. In some embodiments, a system may include an encoder that compresses attribute information and/or spatial information (also referred to herein as geometry information) of a point cloud file such that the point cloud file may be stored and transmitted more quickly than non-compressed point clouds and in a manner such that the point cloud file may occupy less storage space than non-compressed point clouds. In some embodiments, compression of spatial information and/or attributes of points in a point cloud may enable a point cloud to be communicated over a network in real-time or in near real-time. For example, a system may include a sensor that captures spatial information and/or attribute information about points in an environment where the sensor is located, wherein the captured points and corresponding attributes make up a point cloud. The system may also include an encoder that compresses the captured point cloud spatial and attribute information. The compressed spatial and attribute information of the point cloud may be sent over a network in real-time or near real-time to a decoder that decompresses the compressed spatial and attribute information of the point cloud. The decompressed point cloud may be further processed, for example to make a control decision based on the surrounding environment at the location of the sensor. The control decision may then be communicated back to a device at or near the location of the sensor, wherein the device receiving the control decision implements the control decision in real-time or near real-time. In some embodiments, the decoder may be associated with an augmented reality system and the decompressed spatial and/or attribute information may be displayed or otherwise used by the augmented reality system. In some embodiments, compressed attribute information for a point cloud may be sent with compressed spatial information for points of the point cloud. In other embodiments, spatial information and attribute information may be separately encoded and/or separately transmitted to a decoder.

[0029] In some embodiments, a system may include a decoder that receives one or more point cloud files comprising compressed attribute information via a network from a remote server or other storage device that stores the one or more point cloud files. For example, a 3-D display, a holographic display, or a head-mounted display may be manipulated in real-time or near real-time to show different portions of a virtual world represented by point clouds. In order to update the 3-D display, the holographic display, or the head-mounted display, a system associated with the decoder may request point cloud files from the remote server based on user manipulations of the displays, and the point cloud files may be transmitted from the remote server to the decoder and decoded by the decoder in real-time or near real-time. The displays may then be updated with updated point cloud data responsive to the user manipulations, such as updated point attributes.

[0030] In some embodiments, a system, may include one or more LIDAR systems, 3-D cameras, 3-D scanners, etc., and such sensor devices may capture spatial information, such as X, Y, and Z coordinates for points in a view of the sensor devices. In some embodiments, the spatial information may be relative to a local coordinate system or may be relative to a global coordinate system (for example, a Cartesian coordinate system may have a fixed reference point, such as a fixed point on the earth, or may have a non-fixed local reference point, such as a sensor location).

[0031] In some embodiments, such sensors may also capture attribute information for one or more points, such as color attributes, reflectivity attributes, velocity attributes, acceleration attributes, time attributes, modalities, and/or various other attributes. In some embodiments, other sensors, in addition to LIDAR systems, 3-D cameras, 3-D scanners, etc., may capture attribute information to be included in a point cloud. For example, in some embodiments, a gyroscope or accelerometer, may capture motion information to be included in a point cloud as an attribute associated with one or more points of the point cloud. For example, a vehicle equipped with a LIDAR system, a 3-D camera, or a 3-D scanner may include the vehicle’s direction and speed in a point cloud captured by the LIDAR system, the 3-D camera, or the 3-D scanner. For example, when points in a view of the vehicle are captured they may be included in a point cloud, wherein the point cloud includes the captured points and associated motion information corresponding to a state of the vehicle when the points were captured.

[0032] In some embodiments, attribute information may comprise string values, such as different modalities. For example attribute information may include string values indicating a modality such as “walking”, “running”, “driving”, etc. In some embodiments, an encoder may comprise a “string-value” to integer index, wherein certain strings are associated with certain corresponding integer values. In some embodiments, a point cloud may indicate a string value for a point by including an integer associated with the string value as an attribute of the point. The encoder and decoder may both store a common string value to integer index, such that the decoder can determine string values for points based on looking up the integer value of the string attribute of the point in a string value to integer index of the decoder that matches or is similar to the string value to integer index of the encoder.

[0033] In some embodiments, an encoder compresses and encodes spatial information of a point cloud in addition to compressing attribute information for attributes of the points of the point cloud. For example, to compress spatial information a combination predictive tree and octree may be generated wherein, respective occupied/non-occupied states of each cube and/or sub-cube of the octree are encoded. For some nodes instead of encoding additional lower level octree sub-cubes, a predictive tree may be encoded for the node. Alternatively a predictive tree may predict a set of occupied nodes of the predictive tree and points that occupy respective ones of the nodes may further be defined in 3D space by respective octrees corresponding to respective ones of the occupied nodes of the predictive tree. Additionally, in some embodiments, an encoder may signal a number of duplicate points for a given point. This may be more efficient than generating redundant octree and/or predictive tree structures to define two points that have the same or similar spatial locations in 3D space.

[0034] In some embodiments, an encoder and/or decoder may determine a neighborhood occupancy configuration for a given cube of an octree that is being encoded or decoded. The neighborhood occupancy configuration may indicate occupancy states of neighboring cubes that neighbor the given cube being encoded. For example, a cube with for which neighboring cubes are occupied is more likely to also include occupied sub-cubes than a cube for which neighboring cubes are un-occupied.

[0035] FIG. 1A illustrates a system comprising a sensor that captures information for points of a point cloud and an encoder that compresses spatial and/or attribute information of the point cloud, where the compressed spatial and/or attribute information is sent to a decoder, according to some embodiments.

[0036] System 100 includes sensor 102 and encoder 104. Sensor 102 captures a point cloud 110 comprising points representing structure 106 in view 108 of sensor 102. For example, in some embodiments, structure 106 may be a mountain range, a building, a sign, an environment surrounding a street, or any other type of structure. In some embodiments, a captured point cloud, such as captured point cloud 110, may include spatial and attribute information for the points included in the point cloud. For example, point A of captured point cloud 110 comprises X, Y, Z coordinates and attributes 1, 2, and 3. In some embodiments, attributes of a point may include attributes such as R, G, B color values, a velocity at the point, an acceleration at the point, a reflectance of the structure at the point, a time stamp indicating when the point was captured, a string-value indicating a modality when the point was captured, for example “walking”, or other attributes. The captured point cloud 110 may be provided to encoder 104, wherein encoder 104 generates a compressed version of the point cloud (compressed point cloud information 112) that is transmitted via network 114 to decoder 116. In some embodiments, a compressed version of the point cloud, such as compressed point cloud information 112, may be included in a common compressed point cloud that also includes compressed spatial information for the points of the point cloud or, in some embodiments, compressed spatial information and compressed attribute information may be communicated as separate files.

[0037] In some embodiments, encoder 104 may be integrated with sensor 102. For example, encoder 104 may be implemented in hardware or software included in a sensor device, such as sensor 102. In other embodiments, encoder 104 may be implemented on a separate computing device that is proximate to sensor 102.

[0038] FIG. 1B illustrates a process for encoding spatial information of a point cloud using an octree-predictive tree combination structure, according to some embodiments.

[0039] At 150, a volumetric data set, such as a point cloud, is partitioned into an octree comprising cubes and sub-cubes for at least a first level of the octree.

[0040] At 152, it is determined whether occupied ones of the cubes are to be further partitioned into sub-cubes, for example each cube may be partitioned into eight child sub-cubes. In some embodiments, each cube or sub-cube of an octree may be referred to herein as a node or sub-node of the octree. Also relationships between nodes and sub-nodes may be referred to herein as child nodes, parent nodes, grandparent nodes etc. For example a parent node (e.g. cube) may be partitioned into eight child nodes (e.g. sub-cubes). Also each child node may be further partitioned into eight grandchild nodes, etc. However, not every node occupied by two or more points may be further partitioned. For example for some nodes it may be determined that better coding efficiency may be achieved by defining the positions of the points in the occupied node using a predictive tree instead of using further octree nodes. Thus, at 154, it is determined whether respective ones of the occupied nodes or sub-nodes of the octree are to have their points encoded using a predictive tree.

[0041] At 156, occupancy information is generated for the occupied sub-cubes determined to be further partitioned. Also at 156, predictive tree information is generated for the occupied sub-cubes for which it was determined to define the location of the points of the occupied sub-cubes using a predictive tree structure.

[0042] At 158, it is determined if there are additional octree levels to encode, if so the process reverts to 152 and repeats for the next octree level. If not, at 160, the generated octree occupancy information and the generated predictive tree structures are encoded, for example using an arithmetic encoder or a Golomb encoder, as a few examples. At 162, the encoded geometry information is sent or stored for later use in reconstructing the geometry of the compressed point cloud.

[0043] Octree coding is a method that represents a sparse geometry by encoding the structure of an octree. The octree has a known depth, and therefore represents a cube of a known volume, e.g. (2{circumflex over ( )}d){circumflex over ( )}3. By construction, each octree node has between one and eight child nodes (e.g. sub-cubes). The position of a point is encoded as the path through the octree. Each node of the tree contains a bitmap representing which child nodes are present. This bitmap is called the occupancy map, or occupancy information for a node.

[0044] Since the occupied state of a child node (e.g. sub-cube) is binary (present vs not present), it is not possible to predict occupancy by subtraction of a prediction. Instead, the occupancy map is encoded in a bit-serial manner using a context adaptive arithmetic entropy coder. Contexts may be selected by the following means: [0045] Selected based on the occupancy state of the 6-neighbours of the node. This may permit crude detection of the local surface orientation. [0046] Selected based on the occupancy state of the 12 adjacent child neighbors of previously coded nodes. This may allow greater accuracy in differentiating local geometry. [0047] Selected based on predicted child occupancy for 26 neighbors. This may assist in differentiating finer local geometry and dense occupancy.

[0048] For example, FIG. 2 illustrates an example octree structure, according to some embodiments.

[0049] In sparse regions, octree coding may not efficiently encode geometry. For example, for nodes (e.g. cubes or sub-cubes of an octree) with only a single occupied child, instead of coding an 8 bin occupancy map, a three bin child index may be coded instead. If a point is isolated, it may be preferable to directly code the remaining position since compression efficiency may be low (since there is no means to select contexts) and processing costs may be significantly reduced by early termination of the subtree.

[0050] In order to avoid signaling a termination flag in every node, a node may only contain an early termination flag if it is suitably isolated as determined by the 6-neighbours and parent occupancy. Such a node may be said to use an Inferred Direct Coding Mode (IDCM).

[0051] A predictive tree geometry coder that encodes spatial information using a predictive tree structure may represent point locations as nodes in a tree. The tree may be traversed depth-first, with each node having the following properties: [0052] A prediction mode (e.g. delta from parent); [0053] A residual that is combined with the prediction to generate the position of a single point; and [0054] A maximum of three child nodes.

[0055] For example, prediction modes of a predictive tree geometry coder may include: [0056] PCM (pulse code modulation) mode, wherein the “residual” is a displacement from (0,0,0); [0057] Delta mode, wherein the “residual” is the displacement from the parent node’s reconstructed position; [0058] Linear-2 mode, wherein the residual is the displacement from a prediction involving the parent and grandparent nodes’ reconstructed position; or [0059] Linear-3 mode, wherein the residual is the displacement from a prediction involving the parent, grandparent, and great grandparent nodes’ reconstructed position.

[0060] However, in some embodiments, to improve encoding efficiency and/or latency of encoding/decoding spatial information for a point cloud, the octree method and the predictive tree method may be combined.

[0061] For example, in some embodiments, one or more predictive trees may be used to refine an octree leaf node, irrespective of how the leaf mode is selected.

[0062] For an octree with maximum depth (height) H, each octree node represents a cube volume of size (2{circumflex over ( )}(H-D)){circumflex over ( )}3, where D is the tree depth (level) at which the node resides. The root node represents a volume of (2{circumflex over ( )}H){circumflex over ( )}3. A leaf node is a node that, for whatever reason, is not further subdivided. Depending upon the exact octree representation, a leaf node may appear at any depth of the octree. By construction, the existence of an octree node implies that it is occupied (e.g. at least one point is present within its volume).

[0063] In some embodiments, an octree encoding method and a predictive tree encoding method may be combined such that predictive coding is performed to generate one or more predictive trees within (or associated with) one or more octree leaf nodes. In some embodiments, all or only some leaf nodes of an octree may be further refined by a predictive tree coding scheme. For example, FIG. 3 illustrates one occupied node of an octree that is further refined using a predictive tree and another occupied node of the octree (e.g. the lower node in FIG. 3) that is further refined by partitioning the volume of the node into sub-cubes and encoding occupancy states of the sub-cubes. In some embodiments, only leaf nodes greater than a threshold size may be further refined by a predictive tree coding scheme.

……
……
……