Systems and methods for optimizing N dimensional volume data for transmission

• US 10,176,598 B2
• Filed: 12/09/2016
• Issued: 01/08/2019
• 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
• Primary Examiner(s): Shah, Utpal D
• Application Number:
  US15/374,544
• Publication Number:
  US 20170091959A1
• Time in Patent Office: 760 Days
• 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;

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

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

consecutively 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, for each encoded parent cuboid, a distance from the child reference cuboid to another child cuboid containing a data point; and

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

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

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

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

5. The method of claim 1, further comprising the step of transmitting the encoded data.

6. The method of claim 1, 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.

7. The method of claim 1, further comprising the step of encoding, for each data point, remaining location data in the child cuboid in which the data point is mapped.

8. The method of claim 7, 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.

9. 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 a distance from the first reference cuboid to a second reference cuboid, the second reference cuboid being another parent cuboid containing a data point;

consecutively 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, for each encoded parent cuboid, a distance from the child reference cuboid to another child cuboid containing a data point; and

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

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

11. The method of claim 9, wherein the origin of the second reference cuboid is encoded as a distance from the origin of the first reference cuboid.

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

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

14. The method of claim 9, further comprising the step of transmitting the recorded data.

15. The method of claim 9, 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.

16. The method of claim 15, further comprising the step of encoding, for each data point, remaining location data in the child cuboid in which the data point is mapped.

17. The method of claim 9, 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.

18. 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 a distance from the first reference cuboid to another parent cuboid containing a data point;

program code for consecutively 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, for each encoded parent cuboid, a distance from the child reference cuboid to another child cuboid containing a data point; and

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