Method and apparatus for accurate compression and decompression of three-dimensional point cloud data
This invention relates to a method and apparatus for accurate compression and decompression of data. More specifically, this invention relates to a method and apparatus for compressing three dimensional spatial points (so called “point cloud”) and decompressing such data to produce an accurate point cloud. In one embodiment of the present invention, a level set based method is used to reconstruct a surface to approximate the surface of the point cloud. This reconstructed surface is defined implicitly as the zero level set of a function, which can be computed on a regular three-dimensional rectangular grid. Furthermore, the three-dimensional grid may be rearranged into a two-dimensional grid where the data are compressed and stored in a form of gradient. In order to recover the point cloud, the three-dimensional grid is rebuilt from the two-dimensional data and an interpolating algorithm on the implicit function is utilized to compute the points on the surface.
1. A method for compressing and decompressing three-dimensional point cloud data comprises the steps of:
receiving the point cloud data;
managing said point cloud data to transform said point cloud data into a regular data set;
storing said regular data set in a three-dimensional grid of size M×N×P, wherein M, N, P each represents size of each dimension of said three-dimensional grid;
rearranging the three-dimensional grid into a two-dimensional grid which includes said regular data set, wherein the two-dimensional grid includes M×N×P grids therein;
compressing said regular data set in the two-dimensional grid by transforming said regular data set to a compressed data set; and
retrieving the point cloud data by utilizing a decompression method, said method comprising the steps of:
transforming said compressed data set to said regular data set;
rebuilding the three-dimensional grid which includes the regular data set, from the two-dimensional grid; and
according to data in the regular data set, computing a plurality of points which approximate the point cloud data.
2. The method of claim 1 , wherein the step of managing the point cloud data includes the steps of determining an implicit function to construct a surface of the point cloud data; and computing said implicit function on a three-dimensional grid to transform the point cloud data to a regular data set.
3. The method of claim 2 , wherein the implicit function is a level set function and the surface is result of zero level set.
4. The method of claim 2 , wherein the step of computing said implicit function on a three-dimensional grid to transform the point cloud set to a regular data set includes the steps of finding a closest grid point corresponding to each point cloud data point; computing an exact distance value from the grid point to each point cloud data point; using the exact distance values as fixed boundary values for the Eikonal equation; and solving the Eikonal equation to create a regular data set including said distance values represented by a distance function.
5. The method of claim 1 , wherein the compressed data set includes gradient data.
6. The method of claim 4 , wherein the step of computing a plurality of points which approximate the point cloud data includes the step of interpolating the data in the regular data set represented by the distance function.
7. A system for compressing and decompressing three-dimensional point cloud data comprises:
means for receiving the point cloud data;
a compression device for compressing the point cloud data, comprising:
means for managing said point cloud data to transform said point cloud data into a regular data set;
means for storing said regular data set in a three-dimensional grid of size M×N×P, wherein M, N, P each represents size of each dimension of said three-dimensional grid;
means for rearranging the three-dimensional grid into a two-dimensional grid which includes said regular data set, wherein the two-dimensional grid includes M×N×P grids therein;
means for compressing said regular data set in the two-dimensional grid by transforming said regular data set to a compressed data set; and
a decompression device configured for retrieving the point cloud data, comprising:
means for transforming said compressed data set to said regular data set;
means for rebuilding the three-dimensional grid including the regular data set, from the two-dimensional grid; and
means for computing a plurality of points which approximate the point cloud data, according to data in the regular data set.
8. The system of claim 7 , wherein said means for managing the point cloud data includes means for determining an implicit function to construct a surface of the point cloud data; and means for computing said implicit function on a three-dimensional grid to transform the point cloud data to a regular data set.
9. The system of claim 8 , wherein said implicit function is a level set function and the surface is result of zero level set.
10. The system of claim 8 , wherein said means for computing said function on a three-dimensional grid to transform the point cloud data to a regular data set includes means for finding a closest grid point corresponding to each point cloud data point; means for computing an exact distance value from the grid point to each point cloud data point; means for using the exact distance values as fixed boundary values for the Eikonal equation; and means for solving the Eikonal equation to create a regular data set including said distance values represented by a distance function.
11. The system of claim 7 , wherein the compressed regular data set includes gradient data.
12. The system of claim 10 , wherein said means for computing a plurality of points which approximate the point cloud data includes means for interpolating the data in the regular data set represented by the distance function.
13. A system comprising a computer-readable storage device that stores computer-executable instructions which, when executed by a processor, perform operations comprising:
receiving the point cloud data;
managing said point cloud data to transform said point cloud data into a regular data set;
storing said regular data set in a three-dimensional grid of size M×N×P, wherein M, N, P each represents size of each dimension of said three-dimensional grid;
rearranging the three-dimensional grid into a two-dimensional grid that includes said regular data set, wherein the two-dimensional grid includes M×N×P grids therein;
compressing said regular data set in the two-dimensional grid by transforming said regular data set to a compressed data set; and
retrieving the point cloud data by utilizing a decompression method, said method comprising the steps of:
transforming said compressed data set to said regular data set;
rebuilding the three-dimensional grid which includes the regular data set, from the two-dimensional grid; and
according to data in the regular data set, computing a plurality of points which approximate the point cloud data.
14. The system of claim 13 , wherein managing the point cloud data includes determining an implicit function to construct a surface of the point cloud data; and computing said implicit function on a three-dimensional grid to transform the point cloud data to a regular data set.
15. The system in claim 14 , wherein the implicit function is a level set function and the surface is result of zero level set.
16. The system of claim 14 , wherein computing said implicit function on a three-dimensional grid to transform the point cloud set to a regular data set includes the steps of finding a closest grid point corresponding to each point cloud data point; computing an exact distance value from the grid point to each point cloud data point; using the exact distance values as fixed boundary values for the Eikonal equation; and solving the Eikonal equation to create a regular data set including said distance values represented by a distance function.
17. The system of claim 13 , wherein the compressed data set includes gradient data.
18. The system of claim 16 , wherein computing a plurality of points which approximate the point cloud data includes interpolating the data in the regular data set represented by the distance function.
19. The method of claim 3 , wherein the step of computing said implicit function on a three-dimensional grid to transform the point cloud set to a regular data set includes the steps of finding a closest grid point corresponding to each point cloud data point; computing an exact distance value from the grid point to each point cloud data point; using the exact distance values as fixed boundary values for the Eikonal equation; and solving the Eikonal equation to create a regular data set including said distance values represented by a distance function.
20. The system of claim 9 , wherein said means for computing said function on a three-dimensional grid to transform the point cloud data to a regular data set includes means for finding a closest grid point corresponding to each point cloud data point; means for computing an exact distance value from the grid point to each point cloud data point; means for using the exact distance values as fixed boundary values for the Eikonal equation; and means for solving the Eikonal equation to create a regular data set including said distance values represented by a distance function.