Systems and Methods for Optimizing N Dimensional Volume Data for Transmission

• US 20170091959A1
• Filed: 12/09/2016
• Published: 03/30/2017
• Est. Priority Date: 02/18/2014
• Status: Active Grant

• Current Assignee: Par Technology Corporation
• Original Assignee: Par Technology Corporation
• Inventors: Kozak, Mark, Wu, Jimmy, Downs, Jeffrey
• Granted Patent: US 10,176,598 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: H04N 1/64 Systems for the transmission or the storage of the colour picture signal; Details therefor, e.g. coding or decoding means therefor H04N19/00 takes precedence

Abstract

A method and system for optimizing N dimensional volume data for transmission is disclosed. The device and method including organizing points based on XYZ location, into volumes, which are recursively divided by N into smaller volumes, where N is greater than 1, and decompressing each volume, by encoding a reference volume then encoding the remaining volumes as a distance from the reference cuboid or the most recently recorded cuboid.

Claims

1. A method of preparing a plurality of data points for transmission, comprising:

receiving a plurality of data points defining an N dimensional volume, such that each data point exists within a location in the volume;

parsing the N dimensional volume into a plurality of parent cuboids of a first predetermined dimension;

parsing each parent cuboid into a plurality of child cuboids of a second predetermined dimension, wherein the second predetermined dimension is a factor of the first predetermined dimension; and

mapping each data point to the child cuboid containing the location of the data point in the N dimensional volume.

2. The method of claim 1, further comprising the steps of:

encoding the origin of at least one parent cuboid as a first reference cuboid;

encoding the distance from the first reference cuboid to another parent cuboid containing a data point;

encoding each remaining parent cuboid containing a data point as a distance from the most recently encoded parent cuboid;

encoding, for each encoded parent cuboid, the origin of a child reference cuboid;

encoding the distance from the child reference cuboid to another child cuboid containing a data point for each encoded parent cuboid; and

encoding each remaining child cuboid containing a data point as a distance from the most recently encoded child cuboid.

3. The method of claim 2, wherein the origin of the second reference cuboid is encoded as a distance from the origin of the parent cuboid.

4. The method of claim 2, wherein each remaining parent cuboid is encoded in ascending order according to its position in the N dimensional volume.

5. The method of claim 2, wherein each remaining child cuboid is encoded in ascending order according to its position in the parent cuboid.

6. The method of claim 2, further comprising the step of transmitting the encoded data.

7. The method of claim 2, wherein for each encoded child cuboid having a negative distance from the previously encoded cuboid is encoded as a distance from a predetermined position having a positive distance value.

8. The method of claim 2, further comprising the step of encoding, for each data point, remaining location data in the child cuboid wherein the data point is mapped.

9. The method of claim 8, further comprising the step of further encoding the intensity of the data point, the number of returns of the data point, and the scan angle of the data point.

10. A method of preparing a plurality of data points for transmission, comprising:

receiving a plurality of data points defining an N dimensional volume, such that each data point exists within a location in the volume;

ordering the received data points into a data structure dividing the N dimensional volume into a plurality of parent cuboids, wherein each parent cuboid further contains a plurality of child cuboids;

encoding the origin of at least one parent cuboid as a first reference cuboid;

encoding the distance from the first reference cuboid to another parent cuboid containing a data point;

encoding each remaining parent cuboid containing a data point as a distance from the most recently encoded parent cuboid;

encoding, for each encoded parent cuboid, the origin of a child reference cuboid;

encoding the distance from the child reference cuboid to another child cuboid containing a data point for each encoded parent cuboid; and

encoding each remaining child cuboid containing a data point as a distance from the most recently encoded child cuboid.

11. The method of claim 10, wherein the step of ordering the received data points, comprises the steps of:

parsing the N dimensional volume into a plurality of parent cuboids of a first predetermined dimension;

parsing each parent cuboid into a plurality of child cuboids of a second predetermined dimension, wherein the second predetermined dimension is a factor of the first predetermined dimension; and

mapping each data point to the child cuboid containing the location of the data point in the N dimensional volume.

12. The method of claim 10, wherein the data structure is an octree data structure.

13. The method of claim 10, wherein the origin of the second reference cuboid is encoded as a distance from the origin of the parent cuboid.

14. The method of claim 10, wherein each remaining parent cuboid is encoded in ascending order according to its position in the N dimensional volume.

15. The method of claim 10, wherein each remaining child cuboid is encoded in ascending order according to its position in the parent cuboid.

16. The method of claim 10, further comprising the step of transmitting the recorded data.

17. The method of claim 10, wherein for each encoded child cuboid having a negative distance from the previously encoded cuboid is encoded as a distance from a predetermined position having a positive distance value.

18. The method of claim 17, further comprising the step of encoding, for each data point, remaining location data in the child cuboid wherein the data point is mapped.

19. The method of claim 10, further comprising the step of further encoding the intensity of the data point, the number of returns of the data point, and the scan angle of the data point.

20. A nontransitory storage medium storing program code configured to prepare a plurality of data points for transmission, comprising:

program code for receiving a plurality of data points defining an N dimensional volume, such that each data point exists within a location in the volume;

program code for parsing the N dimensional volume into a plurality of parent cuboids of a first predetermined dimension;

program code for parsing each parent cuboid into a plurality of child cuboids of a second predetermined dimension, wherein the second predetermined dimension is a factor of the first predetermined dimension;

program code for mapping each data point to the child cuboid containing the location of the data point in the N dimensional volume;

program code for encoding the origin of at least one parent cuboid as a first reference cuboid;

program code for encoding the distance from the first reference cuboid to another parent cuboid containing a data point;

program code for encoding each remaining parent cuboid containing a data point as a distance from the most recently encoded parent cuboid;

program code for encoding, for each encoded parent cuboid, the origin of a child reference cuboid;

program code for encoding the distance from the child reference cuboid to another child cuboid containing a data point for each encoded parent cuboid; and

program code for encoding each remaining child cuboid containing a data point as a distance from the most recently encoded child cuboid.