Patent Description:
Data compression is used in communications and computer networking to store, transmit, and reproduce information efficiently. There is an increasing interest in representations of three-dimensional objects or spaces, which can involve large datasets and for which efficient and effective compression would be highly useful and valued. In some cases, three-dimensional objects or spaces may be represented using a point cloud, which is a set of points each having a three coordinate location (X, Y, Z) and, in some cases, other attributes like color data (e.g. luminance and chrominance), transparency, reflectance, normal vector, etc. Point clouds can be static (a stationary object or a snapshot of an environment/object at a single point in time) or dynamic (a time-ordered sequence of point clouds).

Example applications for point clouds include topography and mapping applications. Autonomous vehicle and other machine-vision applications may rely on point cloud sensor data in the form of 3D scans of an environment, such as from a LiDAR scanner. Virtual reality simulations may rely on point clouds.

It will be appreciated that point clouds can involve large quantities of data and compressing (encoding and decoding) that data quickly and accurately is of significant interest. Accordingly, it would be advantageous to provide for methods and devices that more efficiently and/or effectively compress data for point clouds. Such methods may result in savings in storage requirements (memory) through improved compression, or savings in bandwidth for transmission of compressed data, thereby resulting in improved operation of 3D vision systems, such as for automotive applications, or improved speed of operation and rendering of virtual reality systems, as examples.

The standard contribution with reference m50642 published on <NUM>-<NUM>-<NUM>, "[GPCC][CE <NUM> related] An improvement of the planar coding mode" by Lasserre et Al, discloses the use of a context model using a vertical laser angle for entropy coding of the z plane position of the planar mode.

The standard contribution with reference m48906 published on <NUM>-<NUM>-<NUM>, "[GPCC][new input] Planar mode in octree-based geometry coding" by Lasserre et Al, discloses the inferring of the most significant bit of the relative z-position for IDCM coding using the z plane position of the planar mode.

The present application describes methods of encoding and decoding point clouds, and encoders and decoders for encoding and decoding point clouds.

Any feature described in relation to one aspect or embodiment of the invention may also be used in respect of one or more other aspects/embodiments. These and other aspects of the present invention will be apparent from, and elucidated with reference to, the embodiments described herein.

At times in the description below, the terms "node", "volume" and "sub-volume" may be used interchangeably. It will be appreciated that a node is associated with a volume or sub-volume. The node is a particular point on the tree that may be an internal node or a leaf node. The volume or sub-volume is the bounded physical space that the node represents. The term "volume" may, in some cases, be used to refer to the largest bounded space defined for containing the point cloud. A volume may be recursively divided into sub-volumes for the purpose of building out a tree-structure of interconnected nodes for coding the point cloud data. The tree-like structure of partitioning of volumes into sub-volumes may be referred to as a "parent" and "child" relationship, where the sub-volumes are child nodes or child sub-volumes to the parent node or parent volume. Sub-volumes within the same volume may be referred to as sibling nodes or sibling sub-volumes.

A point cloud is a set of points in a three-dimensional coordinate system. The points are often intended to represent the external surface of one or more objects. Each point has a location (position) in the three-dimensional coordinate system. The position may be represented by three coordinates (X, Y, Z), which can be Cartesian or any other coordinate system. The points may have other associated attributes, such as color, which may also be a three components value in some cases, such as R, G, B or Y, Cb, Cr. Other associated attributes may include transparency, reflectance, a normal vector, etc., depending on the desired application for the point cloud data.

Point clouds can be static or dynamic. For example, a detailed scan or mapping of an object or topography may be static point cloud data. The LiDAR-based scanning of an environment for machine-vision purposes may be dynamic in that the point cloud (at least potentially) changes over time, e.g. with each successive scan of a volume. The dynamic point cloud is therefore a time-ordered sequence of point clouds.

Point cloud data may be used in a number of applications, including conservation (scanning of historical or cultural objects), mapping, machine vision (such as autonomous or semiautonomous cars), and virtual reality systems, to give some examples. Dynamic point cloud data for applications like machine vision can be quite different from static point cloud data like that for conservation purposes. Automotive vision, for example, typically involves relatively small resolution, non-colored, highly dynamic point clouds obtained through LiDAR (or similar) sensors with a high frequency of capture. The objective of such point clouds is not for human consumption or viewing but rather for machine object detection/classification in a decision process. As an example, typical LiDAR frames contain on the order of tens of thousands of points, whereas high quality virtual reality applications require several millions of points. It may be expected that there will be a demand for higher resolution data over time as computational speed increases and new applications are found.

While point cloud data is useful, a lack of effective and efficient compression, i.e. encoding and decoding processes, may hamper adoption and deployment. A particular challenge in coding point clouds that does not arise in the case of other data compression, like audio or video, is the coding of the geometry of the point cloud. Point clouds tend to be sparsely populated, which makes efficiently coding the location of the points that much more challenging.

One of the more common mechanisms for coding point cloud data is through using tree-based structures. In a tree-based structure, the bounding three-dimensional volume for the point cloud is recursively divided into sub-volumes. Nodes of the tree correspond to sub-volumes. The decision of whether or not to further divide a sub-volume may be based on resolution of the tree and/or whether there are any points contained in the sub-volume. A node may have an occupancy flag that indicates whether its associated sub-volume contains a point or not. Splitting flags may signal whether a node has child nodes (i.e. whether a current volume has been further split into sub-volumes). These flags may be entropy coded in some cases and in some cases predictive coding may be used.

The three-dimensional volume for the point cloud can also be define by using a bounding box. A quad-tree plus binary-tree (QTBT) structure for the bounding box allow to partition the point-cloud in non-cubic volumes which may better represent the overall shape of the point cloud or objects within the point-cloud. A quad-tree (QT) partitioning splits a volume into four sub-volumes, for example by splitting the volume using two planes cutting the volume into four parts. A binary tree (BT) partitioning splits a volume into two sub-volumes, for example by splitting the volume using one plane cutting the volume into two parts.

A commonly-used tree structure is an octree. In this structure, the volumes/sub-volumes are all cubes (or more generally cuboids) and each split of a sub-volume results in eight further sub-volumes/sub-cubes. Another commonly-used tree structure is a KD-tree, in which a volume (cube or rectangular cuboid) is recursively divided in two by a plane orthogonal to one of the axes. Octrees are a special case of KD-trees, where the volume is divided by three planes, each being orthogonal to one of the three axes. A KD-tree may typically be obtained by applying recursively a Binary Tree (BT) partitioning.

The partitioning of a volume is not necessarily into two sub-volumes (KD-tree) or eight sub-volumes (octree), but could involve other partitions, including division into non-cuboid shapes or involving non-adjacent sub-volumes.

The present application may refer to octrees for ease of explanation and because they are a popular candidate tree structure for automotive applications, but it will be understood that the methods and devices described herein may be implemented using other tree structures.

Reference is now made to <FIG>, which shows a simplified block diagram of a point cloud encoder <NUM> in accordance with aspects of the present application. The point cloud encoder <NUM> includes a tree building module <NUM> for receiving point cloud data and producing a tree (in this example, an octree) representing the geometry of the volumetric space containing the point cloud and indicating the location or position of points from the point cloud in that geometry.

In the case of a uniformly partitioned tree structure, like an octree, each node may be represented by a sequence of occupancy bits, where each occupancy bit corresponds to one of the sub-volumes in the node and signals whether than sub-volume contains at least one point or not. Occupied sub-volumes are recursively split up to a maximum depth of the tree. This may be termed the serialization or binarization of the tree. As shown in <FIG>, in this example, the point cloud encoder <NUM> includes a binarizer <NUM> for binarizing the octree to produce a bitstream of binarized data representing the tree.

This sequence of bits may then be encoded using an entropy encoder <NUM> to produce a compressed bitstream. The entropy encoder <NUM> may encode the sequence of bits using a context model <NUM> that specifies probabilities for coding bits based on a context determination by the entropy encoder <NUM>. The context model <NUM> may be adaptively updated after coding of each bit or defined set of bits. The entropy encoder <NUM> may, in some cases, be a binary arithmetic encoder. The binary arithmetic encoder may, in some implementations, employ context-adaptive binary arithmetic coding (CABAC). In some implementations, coders other than arithmetic coders may be used.

In some cases, the entropy encoder <NUM> may not be a binary coder, but instead may operate on non-binary data. The output octree data from the tree building module <NUM> may not be evaluated in binary form but instead may be encoded as non-binary data. For example, in the case of an octree, the eight flags within a sub-volume (e.g. occupancy flags) in their scan order may be considered a <NUM><NUM>-<NUM> bit number (e.g. an integer having a value between <NUM> and <NUM> since the value <NUM> is not possible for a split sub-volume, i.e. it would not have been split if it was entirely unoccupied). This number may be encoded by the entropy encoder using a multi-symbol arithmetic coder in some implementations. Within a sub-volume, e.g. a cube, the sequence of flags that defines this integer may be termed a "pattern".

A convention that is typically used in point cloud compression is that an occupancy bit value of <NUM> signals that the associated node or volume is "occupied", i.e. that it contains at least one point, and an occupancy bit value of <NUM> signals that the associated node or volume is "unoccupied", i.e. that it contains no points. More generally, an occupancy bit may have a value indicating occupied or a value indicating unoccupied. In the description below for ease of explanation, example embodiments may be described in which the convention of <NUM> = occupied and <NUM> = unoccupied is used; however it will be understood that the present application is not limited to this convention.

A block diagram of an example point cloud decoder <NUM> that corresponds to the encoder <NUM> is shown in <FIG>. The point cloud decoder <NUM> includes an entropy decoder <NUM> using the same context model <NUM> used by the encoder <NUM>. The entropy decoder <NUM> receives the input bitstream of compressed data and entropy decodes the data to produce an output sequence of decompressed bits. The sequence is then converted into reconstructed point cloud data by a tree reconstructor <NUM>. The tree reconstructor <NUM> rebuilds the tree structure from the decompressed data and knowledge of the scanning order in which the tree data was binarized. The tree reconstructor <NUM> is thus able to reconstruct the location of the points from the point cloud (subject to the resolution of the tree coding).

In <CIT>, the present applicants described methods and devices for selecting among available pattern distributions to be used in coding a particular node's pattern of occupancy based on some occupancy information from previously-coded nodes near the particular node. In one example implementation, the occupancy information is obtained from the pattern of occupancy of the parent to the particular node. In another example implementation, the occupancy information is obtained from one or more nodes neighboring the particular node. This is referred to as determining a "neighbor configuration" and selecting a context (i.e. a pattern distribution) at least partly based on the neighbor configuration.

In <CIT>, the present applicants described methods and devices for binary entropy coding occupancy patterns.

One of the problems with compressing point cloud data in a tree-structure is that it does not necessarily deal with isolated points very well. The recursive splitting of the sub-volume and the location of points within the split sub-volumes involves computational burden and time, and the signaling of recursive splitting of sub-volumes to pinpoint the location of one or a few isolated points can be costly in terms of bandwidths/memory storage, as well as computational time and resources. Furthermore, isolated points "pollute" the distribution of patterns, inducing many patterns with only one occupied child, thus changing the balance of the distribution and penalizing the coding of other patterns.

Therefore, the direct coding of positional information for isolated points has been proposed. The direct coding of a point's position, e.g. coordinates within a volume or sub-volume, may be termed Direct Coding Mode (DCM). As it would be highly inefficient to use DCM for all points, one option is to signal, for each occupied node, using a dedicated flag, whether DCM will be used for any points within that node; however, this option may result in excessive overhead cost in signaling, thereby producing worse compression performance.

Another option is to determine the eligibility to use DCM for an occupied node based on occupancy information from other nodes. If the occupied node is eligible to use DCM, then a flag is inserted in the bitstream to signal whether DCM is applied or not. This approach may be termed Inferred Direct Coding Mode (IDCM).

The eligibility conditions for IDCM for a tree whose volumes are made of adjacent cuboids may be: A) none of the six neighboring cuboids (top, bottom, forward, back, left, right) are occupied; or in the case where the neighboring cuboids' occupancy is unknown, B) the number of occupied nodes in the parent pattern is equal to one, ie. the current node is isolated at the parent level. In some cases it may be beneficial to apply either conditions A) and B) with condition C) the number of occupied nodes in the grand-parent pattern is equal to one, ie. the current node is also isolated at the grand-parent level. Furthermore, the threshold for the number of occupied parent or grand-parent nodes may be other than one.

If a node is eligible for DCM, then a flag is coded to signal whether DCM is applied or not. This flag may be determined by an encoder based upon the number of points belonging to the volume attached to the node. If this number is less than or equal to a threshold, DCM is activated, and otherwise it is not.

Therefore, in accordance with another aspect of the present application, the eligibility to use DCM for an occupied node is determined based on occupancy information from other nodes. If the occupied node is eligible to use DCM, then a flag is inserted in the bitstream to signal whether DCM is applied or not.

When DCM is applied, the coding of points may be performed by coding the number of points using a truncated unary binarizer followed by a binary entropy coder, but other binarizations may be used depending on the threshold selected for eligibility, and by coding the X, Y, and Z coordinates of each point independently, relative to the volume associated with the node. For example, if a cube has sides of size <NUM>D, then D bits will be needed for each coordinate of each point.

The value of the threshold should be known by the decoder, either implicitly or as a coded parameter.

Certain types of point cloud data tend to have strong directionality. Non-natural environments in particular exhibit strong directionality as those environments tend to feature uniform surfaces. For example, in the case of LiDAR the roadway and the walls of adjacent buildings are generally horizontally or vertically planar. In the case of interior scans within rooms, the floor, ceiling and walls are all planar. LiDAR for the purpose of automotive vision and similar applications tends to be lower resolution and also needs to be compressed quickly and efficiently.

Octrees are efficient tree structures because they are based around a uniform partitioning process of equal division of a cube into eight sub-cubes using three orthogonal planes in every case, so signaling their structure is efficient. However, octrees using current signaling processes are not able to exploit the efficiencies available from recognizing the planar nature of some non-natural environments. KD-trees, however, are able to better tailor the partitioning to the directionality of the point cloud. This makes them a more efficient and effective structure for these types of environments. The downside to KD-trees is that the signaling of their structure requires significantly more data than octrees. The fact that KD-trees are non-uniform means that some of the techniques used to improve octree compression are unavailable to KD-trees or would be computationally difficult to implement.

Accordingly, it is advantageous to have a mechanism for representing non-natural environments using a uniform partitioning-based tree structure in a manner that improves compression by exploiting horizontal and/or vertical directionality.

In some cases, point cloud compression can be improved by a planar coding mode. The planar mode is used to indicate that a volume meets certain requirements for planarity in terms of its occupancy. In particular, a volume is planar if all of its occupied sub-volumes are positioned or located in a common plane. The syntax for signaling may indicate whether a volume is planar and, if so, the position of the common plane. Through exploiting this knowledge of planarity, gains in compression may be achieved. Applying criteria for eligibility to enable the planar mode and mechanisms for context-adaptive coding of the planar mode signaling help improve compression performance.

Planarity is generally presumed to be with respect to a Cartesian axis aligned with the structure of the volumes and sub-volumes. That is a volume is planar if all its occupied sub-volumes are positioned in a common plane orthogonal to one of the axes. As a convention, the z-axis is vertical, meaning that the (horizontal) plane is orthogonal to the z-axis.

For an eligible node, a flag, referred to herein as isPlanar, may be added to signal whether the node is planar. The flag may be entropy coded using prediction techniques. In view of generalizing to x-planar and y-planar modes, the syntax may be composed of <NUM> flags: isZPlanar, isXPlanar, and isYplanar.

In some embodiments, a node is said to be planar if all its occupied child nodes belong to the same horizontal plane. In the case of octrees, such a plane consists of four child nodes, one of which is necessarily occupied. As shown in <FIG>, the horizontal plane can be located at the bottom of the current node, corresponding to a first value of a flag planePosition, e.g. <NUM>, as shown by block <NUM>, or at the top of the current node, corresponding to a second value of planePosition, e.g. <NUM>, as shown by block <NUM>.

Therefore, if the current node is planar, an extra bit planePosition is added to the syntax to indicate the plane position. This bit is also entropy coded.

The knowledge of the planar status of the current node helps coding the occupancy pattern. For example, if the node is z-planar, the four occupancy bits associated with the child nodes belonging to the empty horizontal plane need not be coded. Similarly, if the current node is not planar, it can be assumed that there is at least one occupied child per horizontal plane, and this knowledge can be used to better compress the bitstream.

Various occupancy examples for the case where the planePosition is the bottom is shown in <FIG> as blocks <NUM>, <NUM>, <NUM>, and <NUM>. Similarly, various occupancy examples for the case where the planePosition is the top is shown in <FIG> as blocks <NUM>, <NUM>, <NUM>, and <NUM>.

A method for encoding a node in planar mode is shown with respect to <FIG>. The method of <FIG> reflects the process for encoding occupancy information for a volume. In this example, the volume is uniformly partitioned into eight sub-volumes, each having an occupancy bit, in accordance with octree-based coding. For simplicity, the present example assumes only one (e.g. horizontal) planar mode is used.

In operation <NUM>, the encoder assesses whether the volume is eligible for planar coding mode. Eligibility may be based on cloud density in one example, which may be assessed using mean number of occupied child nodes. To improve local adaptation, eligibility may be based on probability factor tracking. If planar coding mode is not eligible, then the occupancy pattern for the volume is encoded without using planar coding mode, as indicted by operation <NUM>.

If planar mode is enabled, then in operation <NUM>, the encoder assesses whether the volume is planar. If not, then in operation <NUM> it encodes the planar mode flag, e.g. isPlanar = <NUM>. In operation <NUM>, the encoder then encodes the occupancy pattern based on there being at least one occupied sub-volume per plane. That is, the occupancy pattern is encoded and if the first three bits coded for either plane (upper or lower) are zero then the last (fourth) bit for that plane is not coded and is inferred to be one since the corresponding sub-volume must be occupied.

If planar mode is enabled and the volume is planar, then in operation <NUM> the planar mode flag is encoded, e.g. isPlanar = <NUM>. Because the volume is planar, the encoder then also encodes the plane position flag, planePosition. The plane position flag signals whether the planar occupied sub-volumes are in the upper half or lower half of the volume. For example, planePosition = <NUM> may correspond to the lower half (i.e. lower z-axis position) and planePosition = <NUM> may correspond to the upper half. The plane position flag is then encoded at operation <NUM>. The occupancy bits are then encoded based on knowledge of the planarity of the volume and the position of the occupied sub-volumes at operation <NUM>. That is, up to four bits are encoded since four may be inferred to be zero, and the fourth bit may be inferred to be one if the first three encoded are zero.

Typically, LiDAR-acquired point clouds are acquired by a set of spinning lasers. An exemplary LiDAR device is shown with respect to <FIG>.

As seen in <FIG>, the LiDAR device <NUM> comprises a vertically arranged array of lasers <NUM> mounted on a spinning head, such that each laser rotates around the head axis <NUM>. Each laser emits a laser beam <NUM>.

Reference is now made to <FIG>, which illustrates a single laser <NUM> rotating around a head axis <NUM> and having an angle θ with respect to the plane <NUM>. The plane <NUM> is perpendicular to the head axis <NUM>. Naturally, points acquired by the laser will have an angle of acquisition which will be very close to θ, due to noise and measurement precision.

<FIG> illustrates points of a LiDAR-acquired point cloud on a diagram where the vertical axis represents tan(θ), or z / r, and the horizontal axis represents r. By definition and as shown in <FIG>, r is the horizontal distance of a point from the LiDAR's head (or beam assembly in general), and the tangent of the vertical angle tan(θ) is defined as the ratio z/r where z is the vertical elevation of the point <NUM> relative to the LiDAR's head.

Somewhat fixed laser angles tan(θ) can be clearly observed in the diagram. Positive angles signify that the lasers are pointed above the horizontal plane (i.e., towards the sky), while negative angles signify that the lasers are pointed below the horizontal plane (i.e., to the ground). Notably, lasers of the LiDAR are deliberately oriented at different angles - e.g., so that different lasers pick up different parts of the same tall object, like buildings, poles, trees, etc..

As can be seen from <FIG>, the points of the point cloud can be represented in a "quasi" 2D space. For example, a representation is theoretically possible in the 2D space (x,y) and a finite set of vertical angles θ corresponding to the laser beams. Or equivalently in the 2D polar space (φ, r), where φ is the azimuthal angle, and the finite set of vertical angles θ. In other words, one may represent the points in spherical coordinates (φ, r, θ) where θ can take only a finite number of values. This is a consequence of occlusions, which lead to only at most one point per (φ, θ). This quasi 2D space is theoretical but, practically, measurement noise/precision and time integration does not lead to a strictly finite set of possible θ, which is a consequence of the mechanical mounting of the lasers. Instead, it is observed that the values of θ are spread around a finite number of values θlaser and one must deal with the issue of "noise" around these values.

The aforementioned quasi-2D structure depends mainly on the position/orientation of one or more LiDARs (or beam assemblies in general) and the intrinsic characteristics of the LiDAR(s). As will be described in more detail below, it can be thus advantageous to include syntax elements (e.g., parameters, flags) into the bitstream that described characteristics of the LiDAR(s) (or beam assembly/assemblies in general). These syntax elements may indicate at least one of a reference location of the beam assembly, origin locations of specific beams, or beam angles of specific beams. Including these syntax elements into the bitstream can be done at a frame or sequence level. In any case, this data should be present as close as possible to the compressed data bitstream to ensure decodability of the bitstream and minimize the risk of losing data needed for decodability.

Taking note of the above, some embodiments of the application seek to use knowledge obtained from LiDAR characteristics (or characteristics of the relevant beam assemblies), of vertical laser angles θlaser in an efficient representation of the point cloud such that the compression is improved.

Let (xLidar, yLidar, zLidar) be the location of a LiDAR's head (or beam assembly in general), oriented vertically along the z axis in the three-dimensional space XYZ (volumetric space) to which the points of the point cloud belong. The tangent tan(θ) of the vertical angle θ of a point (x,y,z) is the ratio of the elevation z - zLidar and the distance r of the point relatively to the head. This is shown, for example, in Equation <NUM>.

As can be seen from the diagram of <FIG>, which shows detailed views relative to <FIG>, the angle tan(θ) is somewhat constant, but not strictly constant, for the points probed by the same beam. In fact, there exists for each beam a respective envelope in the (r, tan(θ)) diagram that contains the points acquired by this beam. The width of this envelope (in the tan(θ) direction) clearly depends on the distance r. The width of this envelope is due to noise and acquisition precision, and widens for lower r. Notably, the envelopes for adjacent beams do not intersect with each other.

A corrected angle θcorr that exhibits a more stable value through a wide range of r can be obtained by adding a correction term to the position of each laser relative to the head position.

<FIG> schematically illustrates a location of a beam emitter <NUM> relative to the reference location of the beam assembly, for explaining an example method of correcting the angle θ to obtain a corrected angle θcorr. In particular, the position of a beam emitter <NUM> is corrected by a shift <NUM> defined by coordinates (rL, zL) relative to the reference position of the beam assembly such that the beam <NUM> is emitted from the vertical location zLidar + zL and the distance of a point to the beam emitter <NUM> is corrected to become r - rL, where L is the beam emitter index. As such, the corrected location of the beam emitter <NUM> may be referred to as an origin location or beam origin location for the beam <NUM>. The corrected angle θcorr depends on the beam emitter index L and is provided by equation <NUM> below.

For points not too close to the beam assembly, i.e. for not too small values of the distance r, this angle can be approximated as shown in equation <NUM>.

Only the vertical correction zL is needed while the radial correction rL may be neglected. As such, the beam origin position may be determined, starting from the reference location of the beam assembly, based on a relative displacement that can be expressed in terms of (rL, zL) or only in terms of zL.

<FIG> shows the effect of the vertical correction zL on the angle θ. Panel (a) corresponds to panel (b) in <FIG> and panel (b) corresponds to panel (c) in <FIG>. The upper envelope in panel (a) and the lower envelope in panel (b) relate to uncorrected (i.e., initial) angles θ. The lower envelope in panel (a) and the upper envelope in panel (b) relate to corrected angles θcorr. As can be clearly seen, the corrected angles exhibit a mean constant behavior substantially independent on the distance r. The angle θL of the respective beam or beam emitter L is defined as this constant.

To enable a correction of angles θ both at the encoder side and the decoder side, the following values may be determined by or provided to the encoder, and encoded into the bitstream such that the decoding process can use the same beam assembly information as the encoding process:.

Examples of syntax elements describing characteristics of the beam assembly or beam assemblies that have been used for acquiring point clouds that are to be coded will be described in more details below.

As an example, the reference location of the beam assembly may be provided by a user, and the relative positions and corrected angles of the beam emitters of the beam assembly may be found algorithmically. In one example, this may be performed as follows:.

As will be appreciated, if a node corresponds to a volume which can be intersected by more than one laser beam, it becomes unclear which laser beam was used to acquire points within the node. This introduces the concept of eligibility of a node for angular coding.

In one example, the angular eligibility of a volume (or its associated node) is determined as follows:.

<FIG> shows examples of an angular eligible volume and a volume that is not angular eligible. Namely, the size of volume <NUM> and its distance from the beam assembly <NUM> is such that it is sampled by multiple beams <NUM> from multiple beam emitters <NUM>. On the other hand, the size of volume <NUM> and its distance from the beam assembly is such that it is at most sampled by a single beam <NUM>.

In general, determining angular eligibility of a volume (or its associated node) may proceed by first determining a measure of an angular size of the volume as seen from a reference location of the beam assembly. The reference location may be the head's location, as noted above. The measure of angular size may relate to an angle under which an edge of the volume is seen from the reference location, and may be determined, for example, based on a length of the edge of the volume and a distance of (the reference location of) the volume to the reference location of the beam assembly. As such, the measure of angular size may be the angular size Δθ defined above, for example. Then, the measure of the angular size is compared to a measure of a difference angle between adjacent beams of the beam assembly, such as the difference angle Δθmin defined above. That is, the difference angle may be the difference angle between the closest adjacent beams of the beam assembly. Finally, it is determined whether or not the volume is angular eligible based on a result of the comparison. For instance, determining angular eligibility may be based on whether the angular size is smaller than half the difference angle (or any other suitable fraction of the difference angle, to provide for a suitable safety margin).

Once angular eligibility has been determined, the beam L to which an angular eligible volume belongs can be determined, for example, by the following approach:.

Once the beam L has been determined, the corrected angle may be computed by the formula of equation <NUM>. <MAT>
or equation <NUM>: <MAT>.

The second equality may be practically useful as it avoids computing another inverse square root.

In general, the following approach may be followed for determining the corrected angle θcorr for a volume associated with a node. Initially, a first angle (e.g., elevation angle) is determined for a reference location within the volume, relative to a reference location of the beam assembly. The reference location within the volume may be the center of the volume, for example. The reference location of the beam assembly may be the center location of the beam assembly, for example. Based on the first elevation angle, a specific beam (or the corresponding beam emitter) L that is assumed to have acquired (or that has actually acquired) the points within the volume is determined. Next, an origin location (beam origin location) for that specific beam is determined or acquired. This may be done by any suitable approach described above. Having available the origin location of the specific beam, corrected elevation angles for sub-volumes or groups of sub-volumes (e.g., planes within the volume) can be determined relative to the origin location for the specific beam.

The angular coding mode has been introduced to profit from the characteristics of LiDAR-acquired point and obtain gains of compression. It may be used to enhance or replace the predictive information of the planeZPosition discussed above, by using the knowledge of tan(θcorr,L) for angular eligible nodes.

Specifically, the angular coding mode uses angular information to select a context for improved compression. One method of angular coding is illustrated with respect to <FIG>.

As seen in <FIG>, an eligible node <NUM> is divided in a top horizontal plane <NUM> and a bottom horizontal plane <NUM>, comprising the volume of the top four child nodes and the volume of the bottom four child nodes, respectively. At the middle of each of the top horizontal plane <NUM> and the bottom horizontal plane <NUM> are virtual planes <NUM> and <NUM>. Top virtual plane and bottom virtual plane do not occupy the full volume of the child nodes, but are instead mere twodimensional surfaces positioned at the middle of the child nodes.

Angles θtop,L and θbottom,L are defined respectively as the corrected angles from a beam <NUM> emitted by laser <NUM> to the centers of the top virtual plane and the bottom virtual planes, respective to horizontal plane <NUM>. The angle θL is the corrected angle for the laser L that is assumed to have acquired (or that has actually acquired) the points within the eligible node. Corrected angles are understood as angles respective to the horizontal plane <NUM> passing by location of the beam emitter possibly corrected from the reference location of the beam assembly by zL and or rL. In some embodiments, the uncorrected angle may be used, however that may lead to worst compression results. Uncorrected angles are understood as angles respective to the horizontal plane <NUM> passing by the reference location of the beam assembly. A context may then be determined from these angles, as described below.

The context is determined based on the following conditions:.

From the above, condition <NUM> allows for two possibilities, condition <NUM> allows two possibilities, and condition <NUM> allows for four possibilities. Therefore the angular context may take one of <NUM> x <NUM> x <NUM> = <NUM> possible values.

The angular context determined as described above may be used independently or in combination with a planar context to select a context for the entropy encoder (or decoder).

A predicted-point tree is illustrated with respect to <FIG>. Each node of the tree is illustrated by a circle, such as circles <NUM>, <NUM>, or <NUM> and is associated with a point of the point cloud. Each arrow <NUM> corresponds to a predictive branch of the tree, with the arrow pointing towards a parent node. In this example, the root node of the tree is node <NUM>, as it has no parent node. Node <NUM> is an internal node of the tree, as it has a parent and at least one child node. Node <NUM> is a leaf node, as it has no children.

Points associated with the nodes of the predicted-point tree belong to a part of the point cloud contained in volume <NUM>. The structure of the predicted-point tree is determined by the encoding process, in order to obtain an optimal structure in terms of maximum compression of the point cloud within volume <NUM>.

The (x,y,z) coordinates of a point associated with a node of the predicted-point tree are coded using the predicted-point tree coding structure by first determining predictive coordinates (xp,yp,zp) obtained from at least one point associated with an ancestor node or a sibling node, then subtracting the predictive coordinates from the coordinates to obtain residual coordinates, and finally coding the residual coordinates. Residual coordinates may be coded using an entropy coder.

Predictive coordinates (xp,yp,zp) may be obtained using a linear combination of the coordinates of points associated with ancestors or sibling nodes. The coefficients of the linear combinations may be selected from a set of possible linear combinations, and a selection index may be signaled. For instance, if p<NUM> is the coordinate of the point associated with the parent node, p<NUM> is the coordinate of the point associated with the grand-parent node, and p<NUM> is the coordinate of the point associated with the great-grand-parent node, some embodiments may use the following linear combinations. <MAT> <MAT> <MAT> <MAT>.

The point associated with the root node, herein called root point, cannot be coded using predictive coordinates, and its coordinates are coded directly relative to volume <NUM>.

A Golomb Rice coding, an exp-Golomb coding, or another variable length coding approach can be used as an entropy coder for coding the residual coordinates. Alternatively, contextual arithmetic coding can also be used. Parameters of the entropy coder can be chosen depending on the linear combination or the distance between ancestors, such as for example, the average distance between parent and grand-parent, or the average distance between grand-parent and great-grand-parent.

The construction of the predicted point tree for a set of points may be performed as follows. In one embodiment, the encoder first selects one point from the set of points to be associated with the root node of the predicted point tree. This single root node is first considered as a leaf node because it has no child node yet. The selected point is removed from the set of points to be processed. Then, the encoder recursively selects a point from the set of points, associates the selected point with a node of the predicted point tree, and removes the selected point from the set of points to be processed. The recursive process ends when the set of points becomes empty.

In a variant, the encoder first identifies clusters of points and builds a predicted point tree for each cluster of points by taking the closest point to the center of the cluster as the root point and associating the other points of the cluster as its children. Then, the set of root points is considered as a new set of points to be clustered, and the process is applied recursively until the set of root points contains only one point. This variant is a bottom-up process that constructs the tree from the leaf nodes up to the root node.

The predictive structure of a predicted point tree is entirely determined by the prediction selection index associated with each node and the number of child nodes for each node. Point coordinates can then be obtained by the decoder from the predictive structure and the residual coordinates of each point. Thus, a bitstream signaling a predicted point tree is composed of the number of child nodes per node, the prediction selection index, and the residual coordinates for each node.

The scanning order of the tree may be performed following a predetermined coding order. For example, the scanning order of the predicted point tree may be performed following a depth-first traversal of the nodes. In another example, the scanning order of the predicted pont tree may be following a breadth-first traversal of the nodes.

In a variant, the number N of child nodes for a node is less than or equal to a maximum bound. The number N may be coded in the bitstream for each node, knowing the maximum bound, using a Golomb Rice coding, for example. The maximum bound may also be coded in the bitstream.

In another variant, the number of points being associated with child nodes of a node is fixed or deduced algorithmically from information available to the decoder. In such a case, there is no need to signal the number of child nodes for each node.

The present disclosure seeks to provide solutions for improved compression of point cloud data, as measured in compression rate and decoding time.

When IDCM is used, the tree is pruned at a node and no entropy coding of the points located in the node is performed. Specifically, in a pruned branch, the angular mode described above can not be used and does not provide compression benefits.

When an IDCM activation parameter is introduced, it is observed that the more IDCM is used, the faster the runtimes become, at the cost of less compression due to less use of the angular mode. In some cases, the angular mode coding described above has provided gains of more than <NUM>% compression on LiDAR-acquired point clouds, however such gains are accompanied by a <NUM>% increase in decoding time. Therefore, there is a need for an improved method of angular coding which maintains the compression gains while improving runtimes.

In a tree made of nodes associated with volumes, it is understood that the complexity is proportional to the product of the number of processed nodes, and the complexity per node. Therefore, the complexity may be reduced by reducing the number of nodes to be processed while using the angular method, or by simplifying the algorithm for processing a node.

In a first solution, a simple version of the angular mode is used along with IDCM, in order to profit from most of the pruning of the tree provided by IDCM while also benefiting from the compression provided by the angular mode for all points, including those belonging to pruned branches of the tree, in the point cloud.

Furthermore, an additional condition is introduced for IDCM eligibility. Specifically, in prior approaches described above, IDCM was used only for nodes which contained points which were sufficiently isolated. In this solution, IDCM will be used for nodes which are sufficiently isolated, and which are eligible for the angular mode. As described above, in general terms a node is eligible for the angular mode if it can be determined with certainty which laser acquired the points within the volume associated with the node.

According to at least one embodiment of the present disclosure, a node will be subject to IDCM if both these conditions are met. In other words, a node which is sufficiently isolated but which is not eligible for the angular mode will not be subject to IDCM.

Consequently, IDCM is applied less frequently than otherwise, leading to slightly more nodes to process. However, this increase in nodes is small when dealing with very sparse point clouds as are typically obtained by LiDAR acquisition.

According to a first embodiment of the present disclosure, it is assumed that the main axis of the LiDAR device is vertical, and therefore parallel to the z axis. The more general case will be described below.

Furthermore, it will be appreciated from the above discussion that once IDCM is activated for a node, the laser index L associated with the node is known, as well as tan(θL) for the laser associated with the laser index L. In at least some embodiments, the corrected position of the laser (xLidar, yLidar, zLidar + zL) is also known.

This solution is illustrated with respect to <FIG>. Specifically, the method illustrated in <FIG> shows the decoding of a point according to at least one embodiment of the present disclosure.

At operation <NUM>, the x and y coordinates of the point are decoded. The x and y coordinates may be encoded and decoded in a variety of ways known to persons skilled in the art. Typically, the x and y coordinates may be encoded and decoded as for non-angular IDCM.

At operation <NUM>, the inverse of the azimuthal radius is computed from the x and y coordinates decoded at <NUM>, using the following equation <NUM>. Advantageously, this operation need only be performed once per point to be decoded.

Then, the corrected angle tan(θcorr,L) is computed as described above at operation <NUM>. This step may be omitted in some embodiments and the value of tan(θL) may be used instead, however this should lead to lower gains in compression. In at least one embodiment, tan(θcorr,L) is computed as shown in equation <NUM>: <MAT>.

The correction term +zLrinv is the opposite of the term that should be applied to non-corrected angles tan(θbottom) and tan(θtop), which will be described below, to obtain corrected angles tan(θbottom,L) and tan(θtop,L). Because this correction term is fixed, thanks to the knowledge of the coordinates x and y, for any given point, it is more efficient to correct the laser angle once, instead of correcting both the bottom and top angles multiple times.

At operation <NUM>, a z interval is initialized. In at least one embodiment, the z interval is initialized as [zmin, zmax], where zmin corresponds to the lowest possible value of z within the volume associated with the current node, and zmax to the highest possible value of z within the volume associated with the current node.

At operation <NUM>, it is determined whether the coordinate z is completely decoded, i.e. whether there is no remaining bit to decode. A halting criterion may be the z interval having minimal length, e.g. its length is equal to <NUM> or equivalently zmin = zmax. If yes, the method proceeds to the next point. Otherwise, the method proceeds to operation <NUM> to determine tan(θbottom) and tan(θtop). Angles θbottom and θtop are illustrated with respect to <FIG>. In at least one embodiment, the computation may be performed with the following equations <NUM> and <NUM>: <MAT> <MAT>.

The values zbottom and ztop are computed to correspond to one quarter of the way through the z interval and three quarters of the way through the z interval, respectively.

From the (tangent) values of θbottom and θtop, the angular context for entropy decoding may be determined at operation <NUM>, the higher order remaining bit (i.e. the higher bit not yet decoded) for z may be decoded at operation <NUM> using this angular context for entropy decoding.

According to at least one embodiment, the context is determined from a possibility of <NUM> different contexts as a combination of the following:.

However, other methods of selecting the context may be possible, for example by using a subset of the combination described above. Once the angular context is determined, it may be used to decode the next bit for z, or it may be combined with other types of contextual information prior to decoding the next bit for z.

Once the next bit for z is decoded, the z interval is updated based on the value of this decoded bit. For example, if the bit indicates that the z coordinate is in the upper half of the z interval (e.g., the bit is equal to <NUM>), the new z interval is selected as the upper half of the previous z interval. In general terms, the z interval is updated to the interval where the z coordinate is found, based on the information decoded so far. An example of an updated z interval is illustrated with respect to <FIG> in which the z interval of <FIG> is updated by using the example of the decoded bit being equal to <NUM>. Bounds zmin, zmax, and angles θbottom, θtop are updated accordingly.

After the z interval has been updated, the method returns to operation <NUM> to determine whether the z coordinate in completely decoded.

The encoding process is similar to the decoding process illustrated in <FIG>, and is illustrated with respect to <FIG>.

At operation <NUM>, the x and y coordinates of the point are encoded. The x and y coordinates may be encoded and decoded in a variety of ways known to persons skilled in the art. Typically, the x and y coordinates may be encoded and decoded as for non-angular IDCM.

At operation <NUM>, the inverse of the azimuthal radius is computed from the x and y coordinates, using the following equation <NUM>. Advantageously, this operation need only be performed once per point to be encoded.

Then, the corrected angle tan(θcorr,L) is computed as described above at operation <NUM>. This step may be omitted in some embodiments and the value of tan(θL) may be used instead, however this should lead to lower gains in compression. In at least one embodiment, tan(θcorr,L) is computed as shown in equation <NUM>.

At operation <NUM>, it is determined whether the coordinate z is completely encoded, i.e. whether there is no remaining bit to decode. A halting criterion may be the z interval having minimal length, e.g. its length is equal to <NUM> or equivalently zmin = zmax. If yes, the method proceeds to the next point. Otherwise, the method proceeds to operation <NUM> to determine tan(θbottom) and tan(θtop). Angles θbottom and θtop are illustrated with respect to <FIG>. In at least one embodiment, the computation may be performed with the following equations <NUM> and <NUM>: <MAT> <MAT>.

From the (tangent) values of θbottom and θtop, the angular context for entropy coding may be determined at operation <NUM>, the higher order remaining bit (i.e. the higher bit not yet encoded) for z may be encoded at operation <NUM> using this angular context for entropy coding.

However, other methods of selecting the context may be possible, for example by using a subset of the combination described above. Once the angular context is determined, it may be used to encode the next bit for z, or it may be combined with other types of contextual information prior to encoding the next bit for z.

Once the next bit for z is encoded, the z interval is updated based on the value of the last encoded bit. For example, if the bit indicates that the z coordinate is in the upper half of the z interval (e.g., the bit is equal to <NUM>), the new z interval is selected as the upper half of the previous z interval. In general terms, the z interval is updated to the interval where the z coordinate is found, based on the information encoded so far. An example of an updated z interval is illustrated with respect to <FIG> in which the z interval of <FIG> is updated by using the example of the encoded bit being equal to <NUM>. Bounds zmin, zmax, and angles θbottom, θtop are updated accordingly.

After the z interval has been updated, the method returns to operation <NUM> to determine whether the z coordinate in completely encoded.

The above methods for encoding and decoding a node of a tree representing a point cloud are applicable when the axis of the LiDAR head used to acquire the point cloud is vertical. The following methods are applicable more generally, regardless of the orientation of the LiDAR head.

Such a situation is illustrated with respect to <FIG>. A laser <NUM> on a LiDAR head <NUM> which is oriented with respect to axis <NUM> sends a beam <NUM>. Point <NUM> having coordinates (xp, yp) corresponds to the x and y coordinates of a point which is being either decoded or encoded. Once coordinates (xp, yp) are known, for example by a preceding encoding or decoding of these coordinates of the point, the full coordinates (x,y,z) of the point to be encoded or decoded are restricted to be on vertical line <NUM>.

In this embodiment, the angle tan(θcorr,L) is computed from the coordinates of point <NUM> as well as from tan(θL) and the location of the laser <NUM>. Specifically, the angle to be computed is the elevation angle, along the z axis, of the laser when pointing towards line <NUM>.

When rotating, the LiDAR's head <NUM> makes the laser <NUM> rotate and the beam <NUM> describes an open cone <NUM>. The vertical line <NUM> passing by the point <NUM> having azimuthal coordinates (xp, yp) relative to origin <NUM> corresponding to the center of LiDAR head <NUM>, intersects cone <NUM> at a unique point <NUM>. Point <NUM> corresponds to a unique laser position (during rotation of the head) leading to a unique laser beam <NUM> intersecting the vertical line <NUM> to which the point belongs.

To calculate tan(θcorr,L), the origin <NUM> is moved to the laser <NUM> emitting position, for example by a translation of zL along the head axis <NUM>, and every coordinate (x,y,z) is changed to (x',y',z') by a 3D translation. In particular, point <NUM> is translated from (xp, yp, zp) to (x'p, y'p, z'p), and a new radius r' may be computed from equation <NUM>.

The corrected laser angle may be computed from equation <NUM>.

Once this angle is computed, the method for decoding and encoding is as illustrated in <FIG> and <FIG>, respectively, where the radius used is r' instead of r.

Reference is made to <FIG> which shows a method of decoding a predicted-point tree with the angular mode.

At operation <NUM>, it is determined if there are still nodes to decode. If yes, operation <NUM> determines the prediction coordinates (xpred, ypred, zpred) for x, y, and z. At operation <NUM>, the residual coordinates xres and yres for x and y are decoded, and at operation <NUM>, the prediction coordinates for x and y, and the residual coordinates for x and y, are combined to obtain the decoded coordinates xdec = xpred + xres and ydec = ypred + yres for x and y.

At operation <NUM>, the decoded xdec and ydec coordinates are used to compute the inverse radius, and at operation <NUM> the corrected angle is computed using equation <NUM>. This requires knowledge of which laser captured the point to obtain values θL and zL. These values may be decoded from a dedicated information coded into the bitstream received by the decoder.

At operation <NUM> the z interval is initialized. According to at least one embodiment, the z interval is initialized based on the predicted z coordinate zpred and the number of bits used to code the residual coordinate zres. For example, if the predicted z coordinate zpred is <NUM>, and <NUM> bits are used to encode the residual coordinates, the residual coordinate zres may take any value between [-<NUM>,<NUM>], and the z interval is [<NUM>-<NUM>,<NUM>+<NUM>] = [<NUM>,<NUM>].

At operation <NUM>, it is determined whether the residual z coordinate zres has been completely decoded, i.e. whether there is no remaining bit of zres to decode. A halting criterion may be the z interval having minimal length, e.g. its length is equal to <NUM>. If yes, the decoded z coordinate is computed by zdec = zpred + zres , i.e. by adding the decoded zres coordinate residual value to the predicted zpred coordinate value, at operation <NUM> and the method returns to operation <NUM>. If no, the method proceeds to operation <NUM> where the top and bottom angles are determined. The top and bottom angles may be selected at ¾ and ¼ of the z interval, respectively. Therefore, in the example above, where the z interval is [<NUM>,<NUM>], the top and bottom angles may be computed based on z coordinates <NUM> and <NUM>, respectively.

Once the top and bottom angles are determined, an angular context may be selected at operation <NUM>. The angular context may be selected as described with respect to the method illustrated in <FIG>. Alternative methods of selecting an angular context are also possible.

Then, at operation <NUM>, the highest order remaining bit for the z residual coordinate is decoded, and the z interval is updated at operation <NUM>. Specifically, the z interval is updated to the possible range of values for z given the already decoded bits. The method then returns to operation <NUM>.

A syntax signaling the number of bits for the coding of residual z coordinates may be coded in the bitstream. This syntax is decoded and the length of the initial z interval can be deduced from this number, as discussed above. This syntax may be coded using a unary variable length and/or an entropy coder.

More specifically, the residual z coordinate may be coded by an exp-Golomb-like variable length code where the prefix signals the number of bits of the suffix. The suffix itself signals the value of the residual zres. When initializing the z interval, the prefix may be decoded, and the length of the interval may be deduced from the decoded prefix. The center of the interval may be provided by the predicted z coordinate zpred. The suffix is decoded by the iterative process on the z interval.

For example, if z = <NUM> and zpred = <NUM>, then zres = <NUM> - <NUM> = -<NUM> is coded in the bitstream. The residual -<NUM> belongs to the interval [-<NUM>,<NUM>], which has <NUM> = <NUM><NUM> values, and can be coded using <NUM> bits. The encoder thus encodes the prefix <NUM> using a unary code, where each bit of the unary code is coded by a CABAC entropy coder. The bits of the suffix signal to which sub-interval the residual belongs to. For example, a first bit of <NUM> narrows the interval to [-<NUM>,<NUM>], a second bit of <NUM> narrows the interval to [-<NUM>,-<NUM>], a third bit of <NUM> narrows the interval to [-<NUM>,-<NUM>], a fourth bit <NUM> narrows the interval to [-<NUM>,-<NUM>], and a fifth bit of <NUM> finally narrows the interval to [-<NUM>,-<NUM>] that fulfills the halting criterion of the interval having a length equal to <NUM>, and the coded value for zres is -<NUM>.

These five bits are coded by an entropy coder such as CABAC that uses the angular context determined during the methods of <FIG> and <FIG>.

During the decoding process discussed above, the second bit of the suffix may be inferred. For example, based on the example above, one may assume that the residual value for z does not belong to the [-<NUM>,<NUM>] because otherwise the number of bits signaled by the prefix would be <NUM> or less. This inference of the second bit may be performed regardless of the sign of the residual to code, and so this bit is not encoded.

Because the sign of the residual value is usually unpredictable, it is common to signal by a flag if the residual is zero, to code the sign by bypass coding and then to code the value of the magnitude |zres - <NUM>| of the residual. The encoding process for the residual zres then becomes:.

Reference is made to <FIG> illustrating a method for encoding corresponding to the decoding method illustrated in <FIG>.

At operation <NUM>, it is determined if there are still nodes to encode. If yes, operation <NUM> determines the prediction coordinates (xpred, ypred, zpred) for x, y, and z. At operation <NUM>, the residual coordinates xres and yres for x and y are computed, and at operation <NUM> the residual coordinates xres and yres for x and y are encoded.

At operation <NUM>, the coded x and y coordinates are used to compute the inverse radius, and at operation <NUM> the corrected angle is computed using equation <NUM>. This requires knowledge of which laser captured the point to obtain values θL and zL. These values may be decoded from a dedicated information coded into the bitstream received by the decoder.

At operation <NUM> the z interval is initialized. According to at least one embodiment, the z interval is initialized based on the predicted z coordinate zpred and the number of bits used to encode the residual coordinate zres. For example, if the predicted z coordinate zpred is <NUM>, and <NUM> bits are used to encode the residual coordinate zres , the residual coordinate zres may take any value between [-<NUM>,<NUM>], and the z interval is [<NUM>-<NUM>,<NUM>+<NUM>] = [<NUM>,<NUM>].

At operation <NUM>, it is determined whether the residual z coordinates have been encoded, i.e. whether there is no remaining bit of zres to encode. A halting criterion may be the z interval having minimal length, e.g. its length is equal to <NUM>. If yes, the method returns to operation <NUM>. If no, the method proceeds to operation <NUM> where the top and bottom angles are determined. The top and bottom angles may be selected at ¾ and ¼ of the z interval, respectively. Therefore, in the example above, where the z interval is [<NUM>,<NUM>], the top and bottom angles may be computed based on z coordinates <NUM> and <NUM>, respectively.

Then, at operation <NUM>, the highest order remaining bit for the z residual coordinate is encoded, and the z interval is updated at operation <NUM>. Specifically, the z interval is updated to the possible range of values for z given the already encoded bits. The method then returns to operation <NUM>.

Reference is now made to <FIG>, which shows a simplified block diagram of an example embodiment of an encoder <NUM>. The encoder <NUM> includes a processor <NUM>, memory <NUM>, and an encoding application <NUM>. The encoding application <NUM> may include a computer program or application stored in memory <NUM> and containing instructions that, when executed, cause the processor <NUM> to perform operations such as those described herein. For example, the encoding application <NUM> may encode and output bitstreams encoded in accordance with the processes described herein. It will be understood that the encoding application <NUM> may be stored on a non-transitory computer-readable medium, such as a compact disc, flash memory device, random access memory, hard drive, etc. When the instructions are executed, the processor <NUM> carries out the operations and functions specified in the instructions so as to operate as a special-purpose processor that implements the described process(es). Such a processor may be referred to as a "processor circuit" or "processor circuitry" in some examples.

Reference is now also made to <FIG>, which shows a simplified block diagram of an example embodiment of a decoder <NUM>. The decoder <NUM> includes a processor <NUM>, a memory <NUM>, and a decoding application <NUM>. The decoding application <NUM> may include a computer program or application stored in memory <NUM> and containing instructions that, when executed, cause the processor <NUM> to perform operations such as those described herein. It will be understood that the decoding application <NUM> may be stored on a computer-readable medium, such as a compact disc, flash memory device, random access memory, hard drive, etc. When the instructions are executed, the processor <NUM> carries out the operations and functions specified in the instructions so as to operate as a special-purpose processor that implements the described process(es). Such a processor may be referred to as a "processor circuit" or "processor circuitry" in some examples.

It will be appreciated that the decoder and/or encoder according to the present application may be implemented in a number of computing devices, including, without limitation, servers, suitably-programmed general purpose computers, machine vision systems, and mobile devices. The decoder or encoder may be implemented by way of software containing instructions for configuring a processor or processors to carry out the functions described herein. The software instructions may be stored on any suitable non-transitory computer-readable memory, including CDs, RAM, ROM, Flash memory, etc..

It will be understood that the decoder and/or encoder described herein and the module, routine, process, thread, or other software component implementing the described method/process for configuring the encoder or decoder may be realized using standard computer programming techniques and languages. The present application is not limited to particular processors, computer languages, computer programming conventions, data structures, other such implementation details. Those skilled in the art will recognize that the described processes may be implemented as a part of computer-executable code stored in volatile or non-volatile memory, as part of an application-specific integrated chip (ASIC), etc..

The present application also provides for a computer-readable signal encoding the data produced through application of an encoding process in accordance with the present application.

Claim 1:
A method of encoding a point cloud to generate a bitstream of compressed point cloud data representing a three-dimensional location of an object, the point cloud being represented by a tree and being generated by a plurality of beam emitters, the method comprising:
prior to step a) determining that the current node is eligible for Inferred Direct Coding Mode, IDCM, and that the current node is associated with the probing beam emitter
characterized by
a) determining a first coordinate and a second coordinate of a point belonging to a current node of the tree, and computing a radius from the first and second coordinates;
b) determining a beam angle of a probing beam emitter, among the plurality of beam emitters, assumed to have acquired the point;
c) initializing a range of values to all possible values for a third coordinate of the point;
d) selecting a lower value and an upper value within the range of values, the lower value being selected from the lower half of the range and the upper value being selected from the upper half of the range;
e) computing a lower angle based on the lower value and the radius, and computing an upper angle based on the upper value and the radius;
f) selecting an angular context based on the lower angle, the upper angle and the beam angle; and
g) entropy encoding information representative of the third coordinate of the point based on the angular context to generate the bitstream of compressed point cloud .