System and method for near-lossless universal data compression using correlated data sequences

Patent metadata

Field	Value
Publication number	US-10958293-B1
Application number	US-202016806569-A
Country	US
Kind code	B1
Filing date	Mar 2, 2020
Priority date	Mar 2, 2020
Publication date	Mar 23, 2021
Grant date	Mar 23, 2021

Abstract

A method of near-lossless universal data compression using correlated data sequences includes detecting first target surroundings via a first sensor, encoding a first data sequence indicative of the detected target surroundings, and communicating to an electronic controller, the encoded first data sequence. The method additionally includes detecting the first target surroundings via a second sensor, and encoding a second data sequence indicative of the target surroundings detected by the second sensor. The method also includes communicating the encoded second data sequence to the controller. The method additionally includes decoding, via the controller, the encoded first and second data sequences. The method also includes, via the controller, determining a statistical correlation between the decoded first and second data sequences and formulating a mapping function having reduced cardinality and indicative of the determined statistical correlation. Furthermore, the method includes feeding back the mapping function by the controller to the first processor.

First claim

What is claimed is:

1. A method of near-lossless universal data compression using correlated data sequences generated by multiple sensors, the method comprising:
detecting first target surroundings, via a first sensor;
encoding, via a first processor, a first data sequence indicative of the first target surroundings detected by the first sensor;
communicating, via the first processor, the encoded first data sequence to an electronic controller;
detecting the first target surroundings via a second sensor;
encoding a second data sequence, via a second processor, indicative of the first target surroundings detected by the second sensor;
communicating, via the second processor, the encoded second data sequence to the electronic controller;
decoding, via the electronic controller, the encoded first data sequence and the encoded second data sequence;
determining, via the electronic controller, a statistical correlation between the decoded first data sequence and the decoded second data sequence and formulating, via the electronic controller, a mapping function having reduced cardinality and indicative of the determined statistical correlation; and
feeding back, via the electronic controller, the mapping function to the first processor.

2. The method according to claim 1 , further comprising:
detecting second target surroundings via the first sensor;
transforming, via the first processor, a third data sequence indicative of the detected second target surroundings using the mapping function; and
encoding, via the first processor, the transformed third data sequence.

3. The method according to claim 2 , wherein the transformed third data sequence is at a lower data cardinality as compared to the third data sequence, and thereby a size of the encoded transformed third data sequence is smaller than a size of encoded third data sequence.

4. The method according to claim 2 , further comprising:
communicating, via the first processor, the encoded transformed third data sequence to the electronic controller;
detecting the second target surroundings via the second sensor;
encoding a fourth data sequence, via the second processor, indicative of the second target surroundings detected by the second sensor;
communicating, via the second processor, the encoded fourth data sequence to the electronic controller;
decoding, via the electronic controller, the encoded transformed third data sequence and the encoded fourth data sequence; and
determining, via the electronic controller, the third data sequence using the transformed third data sequence and the decoded fourth data sequence.

5. The method according to claim 4 , wherein:
encoding via the first processor includes using a context tree weighted (CTW) compression algorithm to construct an encoding primary context tree data structure;
decoding via the electronic controller includes using the CTW compression algorithm to construct a decoding primary context tree data structure; and
determining the statistical correlation between the decoded first data sequence and the decoded second data sequence includes constructing, via the electronic controller, a decoding secondary context tree data structure from each leaf of the decoding primary context tree data structure.

6. The method according to claim 5 , wherein:
encoding each of the first data sequence and the third data sequence includes constructing respective first and third encoding primary context tree data structures;
encoding the first data sequence is configured to generate a conditional likelihood ratio for each data symbol in the first data sequence;
transforming the third data sequence uses, at each leaf of the third encoding primary context tree data structure, the respective mapping function, which transforms the symbols of the third data sequence; and
encoding the transformed third data sequence is configured to generate a conditional likelihood ratio for each data symbol in the transformed third data sequence using the third encoding primary context tree data structure.

7. The method according to claim 5 , wherein:
decoding the encoded transformed third data sequence includes using the CTW compression algorithm to construct the decoding primary context tree data structure; and
determining the third data sequence includes using the constructed decoding primary context tree data structure and the constructed decoding secondary context tree data structure for each leaf of the decoding primary context tree data structure.

8. The method according to claim 7 , wherein:
formulating the mapping function includes enumerating a number of appearances of a current data symbol in the first data sequence for a context of the first data sequence and a context of the second data sequence in a decoding secondary context tree data structure; and
formulating the mapping function includes using the decoding secondary context tree data structure to achieve a target error probability, and thereby facilitating mapping multiple input symbols into a common bin, when, using each of the primary and secondary context tree data structures, the multiple input symbols are distinct from each other within an average, over the entire first data sequence, error probability that is less than or equal to the target error probability.

9. The method according to claim 7 , wherein:
decoding the encoded transformed third data sequence includes constructing the decoding primary context tree data structure; and
determining the third data sequence additionally includes using the decoded fourth data sequence and the decoding secondary context tree data structure.

10. The method according to claim 9 , wherein determining the third data sequence additionally includes descending through the decoding primary context tree data structure to reach a leaf having the mapping function for mapping each data symbol in the third data sequence to a respective bin value in the transformed third data sequence, the method further comprising descending through the secondary context tree data structure according to the current context of the decoded fourth data sequence to establish a value of a current data symbol in the third data sequence.

11. A system for near-lossless universal data compression using correlated data sequences generated by multiple sensors, the system comprising:
a first sensor configured to detect first target surroundings;
a first processor configured to encode a first data sequence indicative of the first target surroundings detected by the first sensor and communicate the encoded first data sequence to an electronic controller;
a second sensor configured to detect the first target surroundings; and
a second processor configured to encode a second data sequence indicative of the first target surroundings detected by the second sensor and communicate the encoded second data sequence to the electronic controller;
wherein the electronic controller is configured to:
decode the encoded first data sequence and the encoded second data sequence;
determine a statistical correlation between the decoded first data sequence and the decoded second data sequence;
formulate a mapping function having reduced cardinality and indicative of the determined statistical correlation; and
feed back the mapping function to the first processor.

12. The system according to claim 11 , wherein:
the first sensor is further configured to detect second target surroundings; and
the first processor is further configured to:
transform a third data sequence indicative of the detected second target surroundings using the mapping function; and
encode the transformed third data sequence.

Assignees

• Gm Global Tech Operations Llc

Inventors

• Bustin Ronit

Classifications

• H03M13/31 Primary

  combining coding for error detection or correction and efficient use of the spectrum (without error detection or correction H03M5/14 {, H03M5/145}) · CPC title

• H03M7/3059 Primary

  Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression · CPC title

• G06V10/803

  of input or preprocessed data · CPC title

• G06F18/251

  of input or preprocessed data · CPC title

• H03M7/40 Primary

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title