POINT CLOUD OCCUPANCY MAP COMPRESSION

• US 20190156520A1
• Filed: 11/21/2018
• Published: 05/23/2019
• Est. Priority Date: 11/22/2017
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Mammou, Khaled, Su, Yeping, Singer, David W., Tourapis, Alexandros, Robinet, Fabrice A., Wu, Hsi-Jung
• Granted Patent: US 10,699,444 B2
• Time in Patent Office: Days
• CPC Class Codes: A01C 3/02 Storage places for manure, e.g. cisterns for liquid manure; Installations for fermenting manure
• CPC Class Codes: G06T 1/00 General purpose image data processing
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2213/00 Indexing scheme for animation
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/50 Depth or shape recovery
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G08B 1/00 Systems for signalling characterised solely by the form of transmission of the signal
• CPC Class Codes: G09B 1/00 Manually or mechanically operated educational appliances using elements forming, or bearing, symbols, signs, pictures, or the like which are arranged or adapted to be arranged in one or more particular ways puzzle-games A63F9/00; advertising or displaying in general G09F
• CPC Class Codes: G11B 7/002 Recording, reproducing or erasing systems characterised by the shape or form of the carrier

Abstract

A system comprises an encoder configured to compress attribute information and/or spatial for a point cloud and/or a decoder configured to decompress compressed attribute and/or spatial information for the point cloud. To compress the attribute and/or spatial information, the encoder is configured to convert a point cloud into an image based representation. Also, the decoder is configured to generate a decompressed point cloud based on an image based representation of a point cloud. A block/sub-block organization scheme is used to encode blocks and sub-blocks of an occupancy map used in compressing the point cloud. Binary values are assigned to blocks/sub-blocks based on whether they contain patches projected on the point cloud. A traversal path is chosen that takes advantage of run-length encoding strategies to reduce a size of an encoded occupancy map. Also, auxiliary information is used to further improve occupancy map compression.

Claims

1. A system comprising:

an encoder configured to compress a point cloud, wherein to compress the point cloud, the encoder is configured to;

determine, for the point cloud, a plurality of patches each corresponding to portions of the point cloud;

generate, for each patch, a patch image;

pack the generated patch images for each of the patches into one or more image frames;

generate an occupancy map for each of the one or more image frames, wherein the occupancy map indicates pixels of the image frame that are occupied by one of the patches and pixels of the image frame that are un-occupied;

encode the respective one or more occupancy maps, wherein to encode a given one of the one or more occupancy maps the encoder is configured to;

indicate empty blocks of the given occupancy map that include only un-occupied pixels;

assign binary values to sub-blocks of each non-empty block of the given occupancy map, wherein occupied sub-blocks and non-occupied sub-blocks are assigned different binary values;

select a traversal order for encoding the sub-blocks of the given occupancy map such that sub-blocks with similar binary values are traversed sequentially; and

encode the traversal order and sequential binary values for the sub-blocks of the given occupancy map traversed according to the traversal order, wherein the encoded traversal order indicates the selected traversal order to a decoder; and

encode the one or more image frames.

2. The system of claim 1, wherein the encoder is further configured to:

generate for each block of a given image frame a candidate patch list, wherein the candidate patch list includes patches that contain at least one pixel in the block.

3. The system of claim 2, wherein the generated patch images are packed into the given image frame according to patch bounding box size, from largest bounding box to smallest bounding box, and wherein the respective candidate patch lists for each of the blocks of the given image frame are organized according to patch bounding box size, from smallest bounding box to largest bounding box.

4. The system of claim 3, wherein the encoder is configured to:

for each block of the of the given image frame, encode an index of the candidate patch list using an arithmetic encoder or an entropy encoder.

5. The system of claim 4, wherein the encoder is configured to:

assign a particular index value to one or more empty blocks of the given image frame indicating the one or more blocks include only un-occupied pixels.

6. The system of claim 5, wherein the particular index value is used to indicate the one or more empty blocks of the given occupancy map.

7. The system of claim 3, wherein the encoder is further configured to encode auxiliary patch information, wherein the auxiliary patch information comprises, for each patch, a location of the patch in an image frame and a bounding box for the patch.

8. A method for compressing an occupancy map for an image frame comprising packed patches, the method comprising:

indicating empty blocks of the occupancy map that correspond to respective portions of the image frame that include only un-occupied pixels;

assigning binary values to sub-blocks of each non-empty block of the occupancy map, wherein occupied sub-blocks and non-occupied sub-blocks are assigned different binary values;

selecting a traversal order for encoding the sub-blocks of the occupancy map such that sub-blocks with similar binary values are traversed sequentially; and

encoding the traversal order and sequential binary values for the sub-blocks of the occupancy map traversed according to the traversal order.

9. The method of claim 8 wherein the traversal order comprises:

a diagonal traversal order across the sub-blocks of a given block;

a top-to-bottom traversal order across the sub-blocks of a given block;

a bottom-to-top traversal order across the sub-blocks of a given block;

or a side-to-side traversal order across the sub-blocks of a given block.

10. The method of claim 8, wherein encoding the sequential binary values for the sub-blocks of the given occupancy map traversed according to the traversal order comprises:

detecting continuous sequential runs of the binary values; and

encoding a number of detected continuous sequential runs and respective lengths of the detected continuous sequential runs.

11. The method of claim 10, wherein the number of the detected continuous sequential runs and the respective lengths of the detected continuous sequential runs are encoded using:

a fixed length encoder;

or

a universal variable length encoder.

12. The method of claim 10, wherein the number of the detected continuous sequential runs and the respective lengths of the detected continuous sequential runs are encoded using a context adaptive binary arithmetic encoder.

13. The method of claim 8, further comprising compressing an occupancy map for a subsequent image frame comprising packed patches, wherein the occupancy map for the subsequent image frame is predicted using the earlier encoded occupancy map for the image frame as a reference frame.

14. The method of claim 13, wherein the method comprises:

determining a motion vector for one or more of the blocks, wherein the motion vector indicates motion relative to the reference frame.

15. The method of claim 14, further comprising compressing an occupancy map for an additional subsequent image frame comprising packed patches, wherein motion vectors are determined for one or more blocks of the occupancy map for the additional subsequent image frame based on the motion vectors determined for the occupancy map for the subsequent image frame.

16. The method of claim 8, wherein encoding the sequential binary values for the sub-blocks of the occupancy map comprises grouping the binary values into multi-bit words and encoding the multi-bit words.

17. The method of claim 8, wherein at least some of the blocks of the occupancy map have different sizes.

20. The method of claim 8, wherein the method further comprises receiving information from a video decoder about the image frame, wherein the information indicates portions of the image likely to include non-occupied blocks, wherein said determining the non-empty blocks of the occupancy map is determined based, at least in part, on the received information from the video decoder.

18. A method for decompressing an occupancy map for an image frame comprising packed patches, the method comprising:

determining non-empty blocks of the occupancy map; and

for each non-empty block;

determining a traversal order for traversing sub-blocks of the non-empty block;

assigning sequential binary values from a set of encoded binary values to the sub-blocks according to the traversal order to indicate whether the sub-blocks are occupied or non-occupied sub-blocks.

19. The method of claim 18, wherein each block has an associated candidate patch list, wherein a particular index value is used for empty blocks, and wherein said determining the non-empty blocks of the occupancy map is determined based on whether a given block includes the particular index value.