METHOD AND APPARATUS FOR NEAR-LOSSLESS COMPRESSION AND DECOMPRESSION OF 3D MESHES AND POINT CLOUDS

• US 20160086353A1
• Filed: 09/24/2014
• Published: 03/24/2016
• Est. Priority Date: 09/24/2014
• Status: Active Grant

• Current Assignee: University of Maribor
• Original Assignee: University of Maribor
• Inventors: Zalik, Borut, Lukac, Niko
• Granted Patent: US 9,734,595 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• 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

Abstract

Fast near-lossless compression includes four steps: voxelization of the 3D geometry, decomposing the 3D voxel space into consecutive slices, encoding each slice with chain codes, and compressing the chain code with entropy coding. The decompression works by applying the aforementioned steps in inverse order. Smoothing over the voxels'"'"' centers is applied afterwards in order to reconstruct the input 3D points. Optionally 3D mesh is reconstructed over the approximate point cloud in order to obtain the original geometric object. The quality of the compression/decompression is controlled by resolution of the 3D voxel grid.

Claims

1. A computer-implemented method of data compression, the method comprising:

identifying a dataset representing one or more images, wherein the dataset comprises at least one of point cloud data or points from a 3D mesh;

determining a set of voxels for the dataset;

determining a set of 2D slices from the set of voxels of the dataset;

determining a set of segments for each slice in the set of 2D slices;

wherein a segment comprises one or more connected pixels in a 2D slice;

compressing, by one or more processors, each segment in the set of segments to form a compressed set of 2D slices; and

applying entropy coding to the compressed set of 2D slices.

2. The computer-implemented method of claim 1, wherein determining a set of voxels comprises:

creating a voxel grid over the dataset; and

wherein determining a set of 2D slices from the set of voxels of the dataset comprises;

estimating one or more points that are associated with a voxel in the voxel grid; and

slicing the voxel grid into 2D binary rasters.

3. The computer-implemented method of claim 1, wherein compressing each segment in the set of segments comprises:

applying chain code encoding over each contour of each segment to form a chain code;

efficiently storing, for each segment, a starting position of the chain code encoding; and

compressing the chain code.

4. The computer-implemented method of claim 3, wherein efficiently storing, for each segment, a starting position comprises:

coding the starting position based on distances to other positions on a raster grid; and

using variable length encoding to store an offset of the position based on the distances.

5. The computer-implemented method of claim 1, wherein determining a set of segments for each slice in the set of 2D slices comprises:

locating the set of segments based on a flood fill algorithm.

6. The computer-implemented method of claim 1, the method further comprising:

decompressing the compressed set of 2D slices to form a decompressed set of 2D slices; and

performing point cloud reconstruction of the decompressed set of 2D slices.

7. The computer-implemented method of claim 6, the method further comprising:

performing surface reconstruction of the decompressed set of 2D slices.

8. The computer-implemented method of claim 6, wherein performing point cloud reconstruction comprises:

constructing points from each non-empty voxel'"'"'s center to form an approximate point cloud; and

applying smoothing over the approximate point cloud.

9. The computer-implemented method of claim 1, wherein decompression comprises at least one of:

entropy decoding;

chain code decoding; and

voxel space reconstruction

10. An apparatus, comprising:

one or more memory devices storing instructions; and

one or more processors coupled to the one or more memory devices, wherein the one or more processors execute the instructions to perform a method comprising;

identifying a dataset representing one or more images, wherein the dataset comprises at least one of point cloud data or points from a 3D mesh;

determining a set of voxels for the dataset;

determining a set of 2D slices from the set of voxels of the dataset;

determining a set of segments for each slice in the set of 2D slices;

wherein a segment comprises one or more connected pixels in a 2D slice;

compressing each segment in the set of segments to form a compressed set of 2D slices; and

applying entropy coding to the compressed set of 2D slices.

11. The apparatus of claim 10, wherein determining a set of voxels comprises:

creating a voxel grid over the dataset; and

wherein determining a set of 2D slices from the set of voxels of the dataset comprises;

estimating one or more points that are associated with a voxel in the voxel grid; and

slicing the voxel grid into 2D binary rasters.

12. The apparatus of claim 10, wherein compressing each segment in the set of segments comprises:

applying chain code encoding over each contour of each segment to form a chain code;

efficiently storing, for each segment, a starting position of the chain code encoding; and

compressing the chain code.

13. The apparatus of claim 12, wherein efficiently storing, for each segment, a starting position comprises:

coding the starting position based on distances to other positions on a raster grid; and

using variable length encoding to store an offset of the position based on the distances.

14. The apparatus of claim 10, wherein determining a set of segments for each slice in the set of 2D slices comprises:

locating the set of segments based on a flood fill algorithm.

15. The apparatus of claim 10, wherein the one or more processors execute the instructions to perform the method further comprising:

decompressing the compressed set of 2D slices to form a decompressed set of 2D slices; and

performing point cloud reconstruction of the decompressed set of 2D slices.

16. A computer readable storage medium comprising instructions for causing one or more processors to perform a method comprising:

identifying a dataset representing one or more images, wherein the dataset comprises at least one of point cloud data or points from a 3D mesh;

determining a set of voxels for the dataset;

determining a set of 2D slices from the set of voxels of the dataset;

determining a set of segments for each slice in the set of 2D slices;

wherein a segment comprises one or more connected pixels in a 2D slice;

compressing, by one or more processors, each segment in the set of segments to form a compressed set of 2D slices; and

applying entropy coding to the compressed set of 2D slices.

17. The computer readable storage medium of claim 16, wherein determining a set of voxels comprises:

creating a voxel grid over the dataset; and

wherein determining a set of 2D slices from the set of voxels of the dataset comprises;

estimating one or more points that are associated with a voxel in the voxel grid; and

slicing the voxel grid into 2D binary rasters.

18. The computer readable storage medium of claim 16, wherein compressing each segment in the set of segments comprises:

applying chain code encoding over each contour of each segment to form a chain code;

efficiently storing, for each segment, a starting position of the chain code encoding; and

compressing the chain code.

19. The computer readable storage medium of claim 18, wherein efficiently storing, for each segment, a starting position comprises:

coding the starting position based on distances to other positions on a raster grid; and

using variable length encoding to store an offset of the position based on the distances.

20. The computer readable storage medium of claim 16, wherein determining a set of segments for each slice in the set of 2D slices comprises:

locating the set of segments based on a flood fill algorithm.

21. The computer readable storage medium of claim 16, the method further comprising:

decompressing the compressed set of 2D slices to form a decompressed set of 2D slices; and

performing point cloud reconstruction of the decompressed set of 2D slices.