Light detection and ranging (LiDAR)data compression and decompression methods and apparatus

1. A method for compressing three dimensional LiDAR point data, the method comprising:

receiving a dataset to be compressed, the dataset including a plurality of data points in a sequence,

the data points each including at least four types of attribute values,

the attribute value types including an X-coordinate value type, a Y-coordinate value type, a Z-coordinate value type, and at least one associated scalar value type;

applying predictive coding to a sequence of attribute values of a same type from the dataset to generate a sequence of prediction errors for each of the X-coordinate value type and the scalar value type;

applying predictive coding to a sequence of attribute values of a different type from the dataset to generate a sequence of prediction errors for each of the Y-coordinate value type and the Z-coordinate value type;

applying variable length coding to the sequences of prediction errors to generate byte-streams of variable length codes; and

compressing the byte-streams of variable length codes using entropy coding.

2. The method of claim 1 , wherein applying predictive coding for the X-coordinate value type and the scalar value type includes:

receiving the sequence of attribute values of the same type;

determining predicted values for each next attribute value in the sequence; and

calculating the sequence of prediction errors based on a difference between corresponding predicted values and attribute values.

3. The method of claim 2 , wherein determining predicted values includes:

applying one of a plurality of prediction rules to the sequence of attribute values based upon the type of attribute values to be predicted.

4. The method of claim 3 , wherein applying one of a plurality of prediction rules includes:

applying a constant prediction rule where no prediction rule for a given attribute type is prescribed;

applying a linear prediction rule where the attribute value type of the sequence of attribute values includes values that vary linearly;

applying an X prediction rule for x-coordinate value type attribute values;

applying a Y prediction rule for y-coordinate value type attribute values; and

applying a Z prediction rule for z-coordinate value type attribute values.

5. The method of claim 4 , wherein applying a linear prediction rule includes applying a linear prediction rule when the attribute values include at least one of GPS recording time of points; intensity of points; and colors of points.

6. The method of claim 4 , wherein applying a constant prediction rule includes estimating a prediction for a next value in the sequence of attribute values based on a previous value in the sequence of attribute values.

7. The method of claim 4 , wherein applying a linear prediction rule includes estimating a prediction for a next value in the sequence of attribute values based on a linear function of previous values.

8. The method of claim 4 , wherein applying the X prediction rule includes:

estimating a prediction for an x-coordinate attribute value of a next data point based on a mean distance between x-coordinate attribute values of previous data points; and

subtracting a residual of a previous x-coordinate attribute value from the mean distance if a standard deviation between previous values is larger than a predefined threshold.

9. The method of claim 4 , wherein applying the Y prediction rule includes:

searching the sequence of data points for a first pair of successive data points with x-coordinate attribute values that are a distance apart that is less than a predefined amount different than a distance between a current x-coordinate attribute value and a next x-coordinate attribute value;

determining a prediction for the y-coordinate attribute value of a next data point based on a distance between y-coordinate attribute values of the first pair of successive data points if the first pair of successive data points is found; and

determining a prediction for the y-coordinate attribute value of a next data point based on a linear interpolation function of distances between previous data points if the first pair of successive data points is not found.

10. The method of claim 4 , wherein applying the Z prediction rule includes:

searching the sequence of data points for a first pair of successive data points with both:

(a) x-coordinate attribute values that are a distance apart that is less than a predefined amount different than a distance between a current x-coordinate attribute value and a next x-coordinate attribute value, and

(b) y-coordinate attribute values that are a distance apart that is less than a predefined amount different than a distance between a current y-coordinate attribute value and a next y-coordinate attribute value

determining a prediction for the z-coordinate attribute value of a next data point based on a distance between z-coordinate attribute values of the first pair of successive data points if the first pair of successive data points is found; and

determining a prediction for the z-coordinate attribute value of a next data point based on a linear interpolation function of distances between previous data points if the first pair of successive data points is not found.

11. The method of claim 1 , wherein applying variable length coding to the sequence of prediction errors to generate byte-streams of variable length codes includes:

assigning description bytes to each prediction error in the sequence of prediction errors, wherein each prediction error is represented by bits indicating sign and size;

dividing the description bytes into strings of bytes;

removing zero-bytes from the strings of bytes based on a size of the description bytes; and

assembling remaining non-zero bytes into byte-streams.

12. The method of claim 11 , wherein assigning description bytes includes:

storing information indicative of a sign of the prediction error for each prediction error in the sequence of prediction errors; and

storing information indicative of an absolute value of the prediction error for each prediction error in the sequence of prediction errors.

13. The method of claim 11 wherein assembling remaining non-zero bytes into byte-streams includes assembling remaining non-zero bytes into byte-streams based upon a significance of each of the remaining non-zero bytes.

14. The method of claim 1 , wherein applying predictive coding is performed on a plurality of sequences of attribute values in parallel.

15. The method of claim 1 , wherein applying variable length coding is performed on a plurality of sequences of prediction errors in parallel.

16. The method of claim 1 , wherein compressing the byte-streams of variable length codes using entropy coding is performed on a plurality of byte-streams in parallel.

17. The method of claim 1 further comprising storing the compressed byte-streams of variable length codes.

18. The method of claim 1 further comprising transmitting the compressed byte-streams of variable length codes.

19. A medium comprising a non-transitory computer-readable medium including computer-executable instructions adapted to cause a computer to:

receive a dataset to be compressed, the dataset including a plurality of LiDAR data points in a sequence, the data points each including at least four types of attribute values,

the attribute value types including an X-coordinate value type, a Y-coordinate value type, a Z-coordinate value type, and at least one associated scalar value type;

apply predictive coding to a sequence of attribute values of a same type from the dataset to generate a sequence of prediction errors for each of the X-coordinate value type and the scalar value type;

apply predictive coding to a sequence of attribute values of a different type from the dataset to generate a sequence of prediction errors for each of the Y-coordinate value type and the Z-coordinate value type;

apply variable length coding to the sequences of prediction errors to generate byte-streams of variable length codes; and

compress the byte-streams of variable length codes using entropy coding.

20. The medium of claim 19 , wherein apply predictive coding for the X-coordinate value type and the scalar value type includes:

receive the sequence of attribute values of the same type;

determine predicted values for each next attribute value in the sequence; and

calculate the sequence of prediction errors based on a difference between corresponding predicted values and attribute values.

21. The medium of claim 20 , wherein determine predicted values includes:

apply one of a plurality of prediction rules to the sequence of attribute values based upon the type of attribute values to be predicted.

22. The medium of claim 21 , wherein apply one of a plurality of prediction rules includes:

apply a constant prediction rule where no prediction rule for a given attribute type is prescribed;

apply a linear prediction rule where the attribute value type of the sequence of attribute values includes values that vary linearly;

apply an X prediction rule for x-coordinate value type attribute values;

apply a Y prediction rule for y-coordinate value type attribute values; and

apply a Z prediction rule for z-coordinate value type attribute values.

23. The medium of claim 22 , wherein apply a linear prediction rule includes apply a linear prediction rule when the attribute values include at least one of GPS recording time of points; intensity of points; and colors of points.

24. The medium of claim 22 , wherein apply a constant prediction rule includes estimate a prediction for a next value in the sequence of attribute values based on a previous value in the sequence of attribute values.

25. The medium of claim 22 , wherein apply a linear prediction rule includes estimate a prediction for a next value in the sequence of attribute values based on a linear function of previous values.

26. The medium of claim 22 , wherein apply the X prediction rule includes:

estimate a prediction for an x-coordinate attribute value of a next data point based on a mean distance between x-coordinate attribute values of previous data points; and

subtract a residual of a previous x-coordinate attribute value from the mean distance if a standard deviation between previous values is larger than a predefined threshold.

27. The medium of claim 22 , wherein apply the Y prediction rule includes:

search the sequence of data points for a first pair of successive data points with x-coordinate attribute values that are a distance apart that is less than a predefined amount different than a distance between a current x-coordinate attribute value and a next x-coordinate attribute value;

determine a prediction for the y-coordinate attribute value of a next data point based on a distance between y-coordinate attribute values of the first pair of successive data points if the first pair of successive data points is found; and

determine a prediction for the y-coordinate attribute value of a next data point based on a linear interpolation function of distances between previous data points if the first pair of successive data points is not found.

28. The medium of claim 22 , wherein apply the Z prediction rule includes:

search the sequence of data points for a first pair of successive data points with both:

(a) x-coordinate attribute values that are a distance apart that is less than a predefined amount different than a distance between a current x-coordinate attribute value and a next x-coordinate attribute value, and

(b) y-coordinate attribute values that are a distance apart that is less than a predefined amount different than a distance between a current y-coordinate attribute value and a next y-coordinate attribute value

determine a prediction for the z-coordinate attribute value of a next data point based on a distance between z-coordinate attribute values of the first pair of successive data points if the first pair of successive data points is found; and

determine a prediction for the z-coordinate attribute value of a next data point based on a linear interpolation function of distances between previous data points if the first pair of successive data points is not found.

29. The medium of claim 19 , wherein apply variable length coding to the sequence of prediction errors to generate byte-streams of variable length codes includes:

assign description bytes to each prediction error in the sequence of prediction errors, wherein each prediction error is represented by bits indicating sign and size;

divide the description bytes into strings of bytes;

remove zero-bytes from the strings of bytes based on a size of the description bytes; and

assemble remaining non-zero bytes into byte-streams.

30. The medium of claim 29 , wherein assign description bytes includes:

store information indicative of a sign of the prediction error for each prediction error in the sequence of prediction errors; and

store information indicative of an absolute value of the prediction error for each prediction error in the sequence of prediction errors.

31. The medium of claim 29 wherein assemble remaining non-zero bytes into byte-streams includes assemble remaining non-zero bytes into byte-streams based upon a significance of each of the remaining non-zero bytes.

32. The medium of claim 19 , wherein apply predictive coding is performed on a plurality of sequences of attribute values in parallel.

33. The medium of claim 19 , wherein apply variable length coding is performed on a plurality of sequences of prediction errors in parallel.

34. The medium of claim 19 , wherein compress the byte-streams of variable length codes using entropy coding is performed on a plurality of byte-streams in parallel.

35. The medium of claim 19 wherein the computer-executable instructions are further adapted to cause the computer to store the compressed byte-streams of variable length codes.

36. The medium of claim 19 wherein the computer-executable instructions are further adapted to cause the computer to transmit the compressed byte-streams of variable length codes.

37. A computer programmed to compress three dimensional LiDAR point data, the computer comprising:

a processor; and

a memory coupled to the processor and operable to store computer-executable instructions adapted to cause the computer to:

receive a dataset to be compressed, the dataset including a plurality of data points in a sequence,

the data points each including at least four types of attribute values, the attribute value types including an X-coordinate value type, a Y-coordinate value type, a Z-coordinate value type, and at least one associated scalar value type;

apply predictive coding to a sequence of attribute values of a same type from the dataset to generate a sequence of prediction errors for a each of the X-coordinate value type and the scalar value type;

apply predictive coding to a sequence of attribute values of a different type from the dataset to generate a sequence of prediction errors for each of the Y-coordinate value type and the Z-coordinate value type;

apply variable length coding to the sequences of prediction errors to generate byte-streams of variable length codes; and

compress the byte-streams of variable length codes using entropy coding.

38. The computer of claim 37 , wherein apply predictive coding for the X-coordinate value type and the scalar value type includes:

receive the sequence of attribute values of the same type;

determine predicted values for each next attribute value in the sequence; and

calculate the sequence of prediction errors based on a difference between corresponding predicted values and attribute values.

39. The computer of claim 38 , wherein determine predicted values includes:

apply one of a plurality of prediction rules to the sequence of attribute values based upon the type of attribute values to be predicted.

40. The computer of claim 39 , wherein apply one of a plurality of prediction rules includes:

apply a constant prediction rule where no prediction rule for a given attribute type is prescribed;

apply a linear prediction rule where the attribute value type of the sequence of attribute values includes values that vary linearly;

apply an X prediction rule for x-coordinate value type attribute values;

apply a Y prediction rule for y-coordinate value type attribute values; and

apply a Z prediction rule for z-coordinate value type attribute values.

41. The computer of claim 40 , wherein apply a linear prediction rule includes apply a linear prediction rule when the attribute values include at least one of GPS recording time of points; intensity of points; and colors of points.

42. The computer of claim 40 , wherein apply a constant prediction rule includes estimate a prediction for a next value in the sequence of attribute values based on a previous value in the sequence of attribute values.

43. The computer of claim 40 , wherein apply a linear prediction rule includes estimate a prediction for a next value in the sequence of attribute values based on a linear function of previous values.

44. The computer of claim 40 , wherein apply the X prediction rule includes:

estimate a prediction for an x-coordinate attribute value of a next data point based on a mean distance between x-coordinate attribute values of previous data points; and

subtract a residual of a previous x-coordinate attribute value from the mean distance if a standard deviation between previous values is larger than a predefined threshold.

45. The computer of claim 40 , wherein apply the Y prediction rule includes:

search the sequence of data points for a first pair of successive data points with x-coordinate attribute values that are a distance apart that is less than a predefined amount different than a distance between a current x-coordinate attribute value and a next x-coordinate attribute value;

determine a prediction for the y-coordinate attribute value of a next data point based on a distance between y-coordinate attribute values of the first pair of successive data points if the first pair of successive data points is found; and

determine a prediction for the y-coordinate attribute value of a next data point based on a linear interpolation function of distances between previous data points if the first pair of successive data points is not found.

46. The computer of claim 40 , wherein apply the Z prediction rule includes:

search the sequence of data points for a first pair of successive data points with both:

(a) x-coordinate attribute values that are a distance apart that is less than a predefined amount different than a distance between a current x-coordinate attribute value and a next x-coordinate attribute value, and

(b) y-coordinate attribute values that are a distance apart that is less than a predefined amount different than a distance between a current y-coordinate attribute value and a next y-coordinate attribute value

determine a prediction for the z-coordinate attribute value of a next data point based on a distance between z-coordinate attribute values of the first pair of successive data points if the first pair of successive data points is found; and

determine a prediction for the z-coordinate attribute value of a next data point based on a linear interpolation function of distances between previous data points if the first pair of successive data points is not found.

47. The computer of claim 37 , wherein apply variable length coding to the sequence of prediction errors to generate byte-streams of variable length codes includes:

assign description bytes to each prediction error in the sequence of prediction errors, wherein each prediction error is represented by bits indicating sign and size;

divide the description bytes into strings of bytes;

remove zero-bytes from the strings of bytes based on a size of the description bytes; and

assemble remaining non-zero bytes into byte-streams.

48. The computer of claim 47 , wherein assign description bytes includes:

store information indicative of a sign of the prediction error for each prediction error in the sequence of prediction errors; and

store information indicative of an absolute value of the prediction error for each prediction error in the sequence of prediction errors.

49. The computer of claim 47 wherein assemble remaining non-zero bytes into byte-streams includes assemble remaining non-zero bytes into byte-streams based upon a significance of each of the remaining non-zero bytes.

50. The computer of claim 37 , wherein apply predictive coding is performed on a plurality of sequences of attribute values in parallel.

51. The computer of claim 37 , wherein apply variable length coding is performed on a plurality of sequences of prediction errors in parallel.

52. The computer of claim 37 , wherein compress the byte-streams of variable length codes using entropy coding is performed on a plurality of byte-streams in parallel.

53. The computer of claim 37 wherein the computer-executable instructions are further adapted to cause the computer to store the compressed byte-streams of variable length codes.

54. The computer of claim 37 wherein the computer-executable instructions are further adapted to cause the computer to transmit the compressed byte-streams of variable length codes.