Systems and methods for optimizing N dimensional volume data for transmission

• US 9,530,226 B2
• Filed: 02/18/2015
• Issued: 12/27/2016
• 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:
  US14/625,587
• Publication Number:
  US 20150235385A1
• Time in Patent Office: 678 Days
• Field of Search: None
• 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;

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 a first parent cuboid, of the plurality of parent cuboids, as a first reference cuboid;

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

encoding each remaining parent cuboid, of the plurality of parent cuboids, 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, wherein 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.

2. The method of claim 1, wherein the origin of the second parent cuboid is encoded as a distance from the origin of the first parent 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, further comprising the step of encoding, for each data point, remaining location data in the child cuboid wherein the data point is mapped.

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

8. 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 a first parent cuboid, of the plurality of parent cuboids, as a first reference cuboid;

encoding a distance from the first reference cuboid to a second parent cuboid, of the plurality of parent cuboids, 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;

encoding, for each data point, the intensity of the data point, the number of returns of the data point, and the scan angle of the data point.

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

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

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

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

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

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

15. The method of claim 8, 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 8, further comprising the step of encoding, for each data point, remaining location data in the child cuboid wherein the data point is mapped.

17. 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 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;

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

program code for encoding a distance from the first reference cuboid to a second parent cuboid, of the plurality of parent cuboids, 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, wherein 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. 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 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;

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

program code for encoding a distance from the first reference cuboid to a second parent cuboid, of the plurality of parent cuboids, 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;

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

program code for encoding, for each data point, the intensity of the data point, the number of returns of the data point, and the scan angle of the data point.