Granted Patent B2

US 12,192,538 · App. 17/765,015 · Granted Jan 7, 2025

Inventors: Sébastien Lasserre (Thorigné-Fouillard, FR); Jonathan Taquet (Talensac, FR)

Assignee: BlackBerry Limited

H04N19/96H04N19/105H04N19/124H04N19/13H04N19/136H04N19/167H04N19/184H04N19/463

Abstract

Claims (94)

1. A method of encoding the geometry of a point cloud acquired by means of a beam assembly comprising a set of beams, to generate a bitstream of compressed point cloud data, the geometry of the point cloud being defined in a tree structure having a plurality of nodes having parent-child relationships and representing a three-dimensional location of an object, the point cloud being located within a volumetric space recursively split into sub-volumes and containing points of the point cloud, wherein a volume is partitioned into a set of child sub-volumes, and wherein an occupancy bit associated with each respective child sub-volume indicates whether that respective child sub-volume contains at least one of the points, the method comprising,

for a current node associated with a volume split into child sub-volumes:

determining an occupancy pattern for the volume based on occupancy statuses of the child sub-volumes of the volume, wherein the occupancy pattern is a sequence of occupancy bits associated with the volume; and

context-adaptively entropy encoding a representation of the occupancy pattern into the bitstream,

wherein context-adaptively entropy encoding the occupancy pattern comprises:

determining angular information for child sub-volumes or groups of child sub-volumes of the volume, the angular information being indicative of one or more elevation angles relative to a location associated with the beam assembly within the volumetric space;

determining a context for encoding the representation of the occupancy pattern based on the angular information, wherein the context tracks an internal probability to be used in context-adaptive coding; and

entropy encoding the representation of the occupancy pattern using the determined context.

2. The method according to claim 1 , wherein determining the angular information comprises:

determining a first elevation angle for a reference location within the volume relative to a reference location of the beam assembly;

determining a specific beam that is assumed to have acquired the points within the volume, based on the first elevation angle;

determining an origin location of the specific beam; and

determining the one or more elevation angles for child sub-volumes or groups of child sub-volumes of the volume relative to the origin location of the specific beam.

3. The method according to claim 2 , wherein, if the volume is determined to be a planar volume, which is a volume, partitioned into a plurality of sets of child sub-volumes in respective parallel planes, for which all child sub-volumes containing at least one point are positioned in the same plane:

determining the context for coding the representation of the occupancy pattern comprises determining a context for coding a plane position flag based on the angular information, the plane position flag signaling a position of the plane in which the child sub-volumes containing at least one point are positioned; and

entropy coding the representation of the occupancy pattern comprises entropy coding the plane position flag using the determined context.

4. The method according to claim 3 ,

wherein determining the angular information comprises determining respective elevation angles for each of the plurality of parallel planes, relative to the origin location of the specific beam; and

determining the context for coding the plane position flag comprises:

comparing the respective elevation angles for each of the plurality of parallel planes to a beam angle of the specific beam; and

determining the context for coding the plane position flag based on results of respective comparisons.

5. The method according to claim 4 , wherein determining the context for coding the plane position flag based on results of respective comparisons comprises at least one of:

differences between the beam angle of the specific beam and respective elevation angles for each of the plurality of parallel planes;

magnitudes of differences between the beam angle of the specific beam and respective elevation angles for each of the plurality of parallel planes; and

a quantization result of a difference between a largest one among magnitudes of differences between the beam angle of the specific beam and respective elevation angles for each of the plurality of parallel planes and a smallest one among magnitudes of differences between the beam angle of the specific beam and respective elevation angles for each of the plurality of parallel planes.

6. The method according to claim 2 , wherein

determining the context for coding the representation of the occupancy pattern comprises determining contexts for coding occupancy bits for child sub-volumes of the volume; and

entropy coding the representation of the occupancy pattern comprises entropy coding the occupancy bits using the determined contexts.

7. The method according to claim 1 , further comprising first determining that the volume is eligible for determining the context based on the angular information by:

determining a measure of an angular size of the volume as seen from a reference location of the beam assembly;

comparing the measure of the angular size to a measure of a difference angle between adjacent beams of the beam assembly; and

determining that the volume is eligible for determining the context based on the angular information based on a result of the comparison.

8. A method of decoding a bitstream of compressed point cloud data to generate a reconstructed geometry of the point cloud, the point cloud having been acquired by means of a beam assembly comprising a set of beams, the geometry of the point cloud being defined in a tree structure having a plurality of nodes having parent-child relationships and representing a three-dimensional location of an object, the point cloud being located within a volumetric space recursively split into sub-volumes and containing points of the point cloud, wherein a volume is partitioned into a set of child sub-volumes, and wherein an occupancy bit associated with each respective child sub-volume indicates whether that respective child sub-volume contains at least one of the points, the method comprising,

for a current node associated with a volume split into child sub-volumes:

determining angular information for child sub-volumes or groups of child sub-volumes of the volume, the angular information being indicative of one or more elevation angles relative to a location associated with the beam assembly within the volumetric space;

determining a context for decoding a representation of an occupancy pattern of the volume based on the angular information, the occupancy pattern indicating occupancy statuses of the child sub-volumes of the volume, wherein the occupancy pattern is a sequence of occupancy bits associated with the volume, wherein the context tracks an internal probability to be used in context-adaptive coding; and

context-adaptively entropy decoding the bitstream to generate a reconstructed representation of the occupancy pattern using the determined context.

9. The method according to claim 8 , wherein determining the angular information comprises:

determining a first elevation angle for a reference location within the volume relative to a reference location of the beam assembly;

determining a specific beam that is assumed to have acquired the points within the volume, based on the first elevation angle;

determining an origin location of the specific beam; and

determining the one or more elevation angles for child sub-volumes or groups of child sub-volumes of the volume relative to the origin location of the specific beam.

10. The method according to claim 9 , wherein, if the volume is determined to be a planar volume, which is a volume, partitioned into a plurality of sets of child sub-volumes in respective parallel planes, for which all child sub-volumes containing at least one point are positioned in the same plane:

determining the context for coding the representation of the occupancy pattern comprises determining a context for coding a plane position flag based on the angular information, the plane position flag signaling a position of the plane in which the child sub-volumes containing at least one point are positioned; and

entropy coding the representation of the occupancy pattern comprises entropy coding the plane position flag using the determined context.

11. The method according to claim 10 ,

wherein determining the angular information comprises determining respective elevation angles for each of the plurality of parallel planes, relative to the origin location of the specific beam; and

determining the context for coding the plane position flag comprises:

comparing the respective elevation angles for each of the plurality of parallel planes to a beam angle of the specific beam; and

determining the context for coding the plane position flag based on results of respective comparisons.

12. The method according to claim 11 , wherein determining the context for coding the plane position flag based on results of respective comparisons comprises at least one of:

differences between the beam angle of the specific beam and respective elevation angles for each of the plurality of parallel planes;

magnitudes of differences between the beam angle of the specific beam and respective elevation angles for each of the plurality of parallel planes; and

a quantization result of a difference between a largest one among magnitudes of differences between the beam angle of the specific beam and respective elevation angles for each of the plurality of parallel planes and a smallest one among magnitudes of differences between the beam angle of the specific beam and respective elevation angles for each of the plurality of parallel planes.

13. The method according to claim 9 , wherein

determining the context for coding the representation of the occupancy pattern comprises determining contexts for coding occupancy bits for child sub-volumes of the volume; and

entropy coding the representation of the occupancy pattern comprises entropy coding the occupancy bits using the determined contexts.

14. The method according to claim 13 ,

wherein determining the angular information comprises determining respective elevation angles for each of the child sub-volumes of the volume, relative to the origin location of the specific beam; and

determining the contexts for coding occupancy bits for child sub-volumes of the volume comprises:

comparing the respective elevation angles for each of the child sub-volumes of the volume to a beam angle of the specific beam; and

determining the contexts for coding occupancy bits for child sub-volumes of the volume based on results of respective comparisons.

15. The method according to claim 8 , further comprising first determining that the volume is eligible for determining the context based on the angular information by:

determining a measure of an angular size of the volume as seen from a reference location of the beam assembly;

comparing the measure of the angular size to a measure of a difference angle between adjacent beams of the beam assembly; and

determining that the volume is eligible for determining the context based on the angular information based on a result of the comparison.

16. The method according to claim 8 ,

wherein the beam assembly is a rotating beam assembly; and

the point cloud is defined with respect to a Cartesian axis in the volumetric space, the Cartesian axis having a vertically oriented z-axis normal to a horizontal plane and substantially parallel to an axis of rotation of the rotating beam assembly.

17. The method according to claim 8 , wherein the bitstream includes one or more parameters describing characteristics of the beam assembly.

18. An encoder for encoding the geometry of a point cloud acquired by means of a beam assembly comprising a set of beams, to generate a bitstream of compressed point cloud data, the geometry of the point cloud being defined in a tree structure having a plurality of nodes having parent-child relationships and representing a three-dimensional location of an object, the point cloud being located within a volumetric space recursively split into sub-volumes and containing points of the point cloud, wherein a volume is partitioned into a set of child sub-volumes, and wherein an occupancy bit associated with each respective child sub-volume indicates whether that respective child sub-volume contains at least one of the points, the encoder comprising:

a processor;

a memory; and

an encoding application containing instructions executable by the processor that, when executed, cause the processor to:

for a current node associated with a volume split into child sub-volumes:

determine an occupancy pattern for the volume based on occupancy statuses of the child sub-volumes of the volume, wherein the occupancy pattern is a sequence of occupancy bits associated with the volume; and

context-adaptively entropy encode a representation of the occupancy pattern into the bitstream,

wherein to context-adaptively entropy encode the occupancy pattern is to:

determine angular information for child sub-volumes or groups of child sub-volumes of the volume, the angular information being indicative of one or more elevation angles relative to a location associated with the beam assembly within the volumetric space;

determine a context for encoding the representation of the occupancy pattern based on the angular information, wherein the context tracks an internal probability to be used in context-adaptive coding; and

entropy encode the representation of the occupancy pattern using the determined context.

19. A decoder for decoding a bitstream of compressed point cloud data to generate a reconstructed geometry of the point cloud, the point cloud having been acquired by means of a beam assembly comprising a set of beams, the geometry of the point cloud being defined in a tree structure having a plurality of nodes having parent-child relationships and representing a three-dimensional location of an object, the point cloud being located within a volumetric space recursively split into sub-volumes and containing points of the point cloud, wherein a volume is partitioned into a set of child sub-volumes, and wherein an occupancy bit associated with each respective child sub-volume indicates whether that respective child sub-volume contains at least one of the points, the decoder comprising:

a processor;

a memory; and

a decoding application containing instructions executable by the processor that, when executed, cause the processor to:

for a current node associated with a volume split into child sub-volumes:

determine angular information for child sub-volumes or groups of child sub-volumes of the volume, the angular information being indicative of one or more elevation angles relative to a location associated with the beam assembly within the volumetric space;

determine a context for decoding a representation of an occupancy pattern of the volume based on the angular information, the occupancy pattern indicating occupancy statuses of the child sub-volumes of the volume, wherein the occupancy pattern is a sequence of occupancy bits associated with the volume, wherein the context tracks an internal probability to be used in context-adaptive coding; and

context-adaptively entropy decode the bitstream to generate a reconstructed representation of the occupancy pattern using the determined context.

20. A non-transitory processor-readable medium storing processor-executable instructions for decoding a bitstream of compressed point cloud data to generate a reconstructed geometry of the point cloud, the point cloud having been acquired by means of a beam assembly comprising a set of beams, the geometry of the point cloud being defined in a tree structure having a plurality of nodes having parent-child relationships and representing a three-dimensional location of an object, the point cloud being located within a volumetric space recursively split into sub-volumes and containing points of the point cloud, wherein a volume is partitioned into a set of child sub-volumes, and wherein an occupancy bit associated with each respective child sub-volume indicates whether that respective child sub-volume contains at least one of the points, wherein the instructions, when executed by a processor, cause the processor to:

for a current node associated with a volume split into child sub-volumes:

determine angular information for child sub-volumes or groups of child sub-volumes of the volume, the angular information being indicative of one or more elevation angles relative to a location associated with the beam assembly within the volumetric space;

determine a context for decoding a representation of an occupancy pattern of the volume based on the angular information, the occupancy pattern indicating occupancy statuses of the child sub-volumes of the volume, wherein the occupancy pattern is a sequence of occupancy bits associated with the volume, wherein the context tracks an internal probability to be used in context-adaptive coding; and

context-adaptively entropy decode the bitstream to generate a reconstructed representation of the occupancy pattern using the determined context.

Assignments (3)

Priority Claims (1)

Continuity (1)

References Cited (40)

Cited By (1)

US 12,579,696