Compression of point clouds via a novel hybrid coder

1. A method for compressing a point cloud, the method comprising:

defining a volume that comprises a plurality of points of the point cloud;

determining an estimated efficiency of each respective sub-division technique of a set of possible sub-division techniques based on an estimated entropy in a distribution of points in the volume when the respective sub-division technique is performed;

selecting a given sub-division technique from the set of possible sub-division techniques upon determining that the estimated efficiency of the given sub-division technique is higher than estimated efficiencies of one or more other sub-division techniques in the set of possible sub-division techniques, wherein each respective sub-division technique of the set of possible sub-division techniques is associated with a respective control code of a plurality of control codes;

dividing the volume into a number of sub-volumes according to the given sub-division technique;

determining whether each sub-volume of the sub-volumes is occupied by at least one point; and

generating a bit sequence for the volume comprising: a given control code of the plurality of control codes that is associated with the given sub-division technique and indicates that the given sub-division technique was used to divide the volume; and an occupancy indicator that indicates whether or not each sub-volume is occupied by at least one point.

2. The method of claim 1 , wherein the set of possible sub-division techniques comprises a default subdivision technique.

3. The method of claim 2 , further comprising:

determining a sub-division technique for a sub-volume of the sub-volumes based on one or more numbers derived from a distribution of points in the sub-volume;

dividing the sub-volume into a number of second sub-volumes according to the sub-division technique for the sub-volume;

generating a second bit sequence for the sub-volume comprising: a second control code that is based on the sub-division technique for the sub-volume; and a set of uniform quantization components comprising a sequence of bits that uniformly quantize a residual vertex location within the sub-volume for a plurality of dimensions, wherein the sub-division technique for the volume comprises OctTree encoding, and wherein the sub-division technique for the sub-volume comprises uniform quantization.

4. The method of claim 3 , wherein determining the sub-division technique for the sub-volume comprises choosing between a default sub-division technique and uniform quantization so as to minimize a number of bits in a bit sequence for the sub-volume based on one or more parameters, wherein the one or more parameters include one or more of the following:

a desired precision for compressing the point cloud;

a level of the sub-volume determined based on how many sub-divisions have been performed to derive the sub-volume;

a number of points in the sub-volume; and

a number of bits in a control code corresponding to a default sub-division technique; and

a number of bits in a control code corresponding to an alternative sub-division technique.

5. The method of claim 3 , wherein determining the sub-division technique for the sub-volume comprises:

determining a first number of bits for using a first sub-division technique by:

determining a level of the sub-volume based on how many sub-divisions have been performed to derive the sub-volume;

determining a desired precision for compressing the point cloud;

calculating the first number of bits by subtracting the level of the sub-volume from the desired precision and multiplying the remainder by a sum of a number of bits required to encode the sub-volume into an occupancy indicator according to the first subdivision technique and a number of bits required to represent the first sub-division technique using a control code;

determining a second number of bits for using a second sub-division technique by calculating a sum of:

a number of bits required to encode the sub-volume into an occupancy indicator according to the second subdivision technique;

a number of bits required to represent the second sub-division technique using a control code; and

a product of:

a number of points in the sub-volume; and

a remainder determined by subtracting the level of the sub-volume from the desired precision; and

choosing either the first sub-division technique or the second sub-division technique as the sub-division technique for the sub-volume based on which of the first number of bits and the second number of bits is smaller.

6. The method of claim 1 , wherein the control code is associated with a decoding technique, and wherein a decoding component selects a decoding technique for the volume based on the control code of the volume.

7. The method of claim 1 , wherein a length of the control code is chosen such as to minimize a bit overhead used for control information encoding in a scene comprising the point cloud.

8. The method of claim 7 , wherein a plurality of sub-division techniques are ranked according to their prevalence in the scene, and wherein shorter control codes are used to describe sub-division techniques that are more prevalent in the scene.

9. The method of claim 7 , wherein a default sub-division technique is OctTree sub-division, and wherein the default sub-division technique corresponds to a control code comprising one bit.

10. A computer system, comprising:

a processor configured to perform a method for compressing a point cloud, the method comprising:

defining a volume that comprises a plurality of points of the point cloud;

determining an estimated efficiency of each respective sub-division technique of a set of possible sub-division techniques based on an estimated entropy in a distribution of points in the volume when the respective sub-division technique is performed,

selecting a given sub-division technique from the set of possible sub-division techniques upon determining that the estimated efficiency of the given sub-division technique is higher than estimated efficiencies of one or more other sub-division techniques in the set of possible sub-division techniques, wherein each respective sub-division technique of the set of possible sub-division techniques is associated with a respective control code of a plurality of control codes;

dividing the volume into a number of sub-volumes according to the given sub-division technique;

determining whether each sub-volume of the sub-volumes is occupied by at least one point; and

generating a bit sequence for the volume comprising: a given control code of the plurality of control codes that is associated with the given sub-division technique and indicates that the given sub-division technique was used to divide the volume; and an occupancy indicator that indicates whether or not each sub-volume is occupied by at least one point.

11. The computer system of claim 10 , wherein the set of possible sub-division techniques comprises a default subdivision technique.

12. The computer system of claim 11 , wherein the method further comprises:

determining a sub-division technique for a sub-volume of the sub-volumes based on one or more numbers derived from a distribution of points in the sub-volume;

dividing the sub-volume into a number of second sub-volumes according to the sub-division technique for the sub-volume;

determining whether each second sub-volume of the second sub-volumes is occupied by at least one point;

generating a second bit sequence for the sub-volume comprising: a second control code that is based on the sub-division technique for the sub-volume; and a set of uniform quantization components comprising a sequence of bits that uniformly quantize a residual vertex location within the sub-volume for a plurality of dimensions,

wherein the sub-division technique for the volume comprises OctTree encoding, and wherein the sub-division technique for the sub-volume comprises uniform quantization.

13. The computer system of claim 12 , wherein determining the sub-division technique for the sub-volume comprises choosing between a default sub-division technique and uniform quantization so as to minimize a number of bits in a bit sequence for the sub-volume based on one or more parameters, wherein the one or more parameters include one or more of the following:

a desired precision for compressing the point cloud;

a level of the sub-volume determined based on how many sub-divisions have been performed to derive the sub-volume;

a number of points in the sub-volume; and

a number of bits in a control code corresponding to a default sub-division technique; and

a number of bits in a control code corresponding to an alternate sub-division technique.

14. The computer system of claim 12 , wherein determining the sub-division technique for the sub-volume comprises:

determining a first number of bits for using a first sub-division technique by:

determining a level of the sub-volume based on how many sub-divisions have been performed to derive the sub-volume;

determining a desired precision for compressing the point cloud;

calculating the first number of bits by subtracting the level of the sub-volume from the desired precision and multiplying the remainder by a sum of a number of bits required to encode the sub-volume into an occupancy indicator according to the first subdivision technique and a number of bits required to represent the first sub-division technique using a control code;

determining a second number of bits for using a second sub-division technique by calculating a sum of:

a number of bits required to encode the sub-volume into an occupancy indicator according to the second subdivision technique;

a number of bits required to represent the second sub-division technique using a control code; and

a product of:

a number of points in the sub-volume; and

a remainder determined by subtracting the level of the sub-volume from the desired precision; and

choosing either the first sub-division technique or the second sub-division technique as the sub-division technique for the sub-volume based on which of the first number of bits and the second number of bits is smaller.

15. The computer system of claim 12 , wherein the occupancy indicator for the volume comprises a sequence of bits equal to the number of sub-volumes, and wherein the occupancy indicator for the sub-volume comprises a sequence of bits that uniformly quantize a residual vertex location.

16. The computer system of claim 10 , wherein the control code is associated with a decoding technique, and wherein a decoding component selects a decoding technique for the volume based on the control code of the volume.

17. The computer system of claim 10 , wherein a length of the control code is chosen such as to minimize a bit overhead used for control information encoding in a scene comprising the point cloud.

18. The computer system of claim 17 , wherein a plurality of sub-division techniques are ranked according to their prevalence in the scene, and wherein shorter control codes are used to describe sub-division techniques that are more prevalent in the scene.

19. The computer system of claim 17 , wherein a default sub-division technique is OctTree sub-division, and wherein the default sub-division technique corresponds to a control code comprising one bit.

20. A non-transitory computer readable medium having instructions stored thereon for compressing a point cloud, wherein execution of the instructions by a computing system causes the computing system to carry out the steps of:

defining a volume that comprises a plurality of points of the point cloud;

determining an estimated efficiency of each respective sub-division technique of a set of possible sub-division techniques based on an estimated entropy in a distribution of points in the volume when the respective sub-division technique is performed;

selecting a given sub-division technique from the set of possible sub-division techniques upon determining that the estimated efficiency of the given sub-division technique is higher than estimated efficiencies of one or more other sub-division techniques in the set of possible sub-division techniques, wherein the given sub-division technique is selected from: OctTree sub-division or uniform quantization;

dividing the volume into a number of sub-volumes according to the given sub-division technique;

generating a bit sequence for the volume such that:

if the given sub-division technique for the volume is OctTree sub-division, the bit sequence comprises an occupancy indicator that indicates whether or not each sub-volume is occupied by at least one node;

if the given sub-division technique for the volume is uniform quantization, the bit sequence comprises an escape code.