Method and system for compressing a continuous data flow in real-time using recursive hierarchical self-organizing cluster vector quantization (HSOCVQ)

• US 6,798,360 B1
• Filed: 06/27/2003
• Issued: 09/28/2004
• Est. Priority Date: 06/27/2003
• Status: Expired due to Fees

• Current Assignee: Canadian Space Agency (Government of Canada)
• Original Assignee: Canadian Space Agency (Government of Canada)
• Inventors: Qian, Shen-En, Hollinger, Allan B.
• Primary Examiner(s): Tokar, Michael
• Assistant Examiner(s): NGUYEN, LINH V
• Application Number:
  US10/606,761
• Time in Patent Office: 459 Days
• Field of Search: 341/50, 341/51, 341/59, 341/65, 341/67, 341/79, 341/106, 341/107, 375/240.12, 375/240.22, 375/241
• US Class Current: 341/50
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

The present invention relates to a method for compressing a continuous data flow based on lossy compression. In real-time data compression, a series of data subsets acquired in a given period of time are treated as a regional data cube for the purpose of dividing a continuous series of data subsets into a plurality of data cubes. Reuse of existing codevectors is important in achieving high compression performance. For encoding spectral vectors on a subset-by-subset basis in a current region two types of codevectors are used, codevectors that have been newly trained for previous data subsets in the current region and codevectors trained for the previous region. The problem of a visible spatial boundary between two adjacent regions after decompression is overcome by reusing the codevectors trained from a previous region to encode the spectral vectors in the current region in order to attain a seamless conjunction of the two adjacent regions. Experimental results show that the method for compressing a continuous data flow in real-time according to the present invention performs as well as data compression performed in batch mode. Therefore, the method is highly advantageous in, for example, space applications or medical imaging.

Claims

1. A method for compressing a continuous data flow comprising the steps of:

a) receiving a n^th data subset of the continuous data flow, the n^th data subset comprising a plurality of data vectors indicative of a n^th portion of an image of an object;

b) selecting for each data vector of the n^th data subset a codevector from a n−

1^th codebook that approximates the respective data vector, the n−

1^th codebook comprising codevectors for encoding at least a portion of the data vectors of the n−

1^th data subset;

c) determining a fidelity for the approximation of each data vector of the n^th data subset; and

,

d) when the fidelity for the approximation of a data vector of the n^th data subset is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector.

2. A method for compressing a continuous data flow as defined in claim 1 comprising the step of:

e) repeating the steps a) to d) for encoding data vectors of a n+1^th data subset received subsequent to the n^th data subset.

3. A method for compressing a continuous data flow as defined in claim 2 comprising the steps of:

f) determining un-encoded data vectors from at least two data subsets;

g) determining at least a codevector through training for approximating the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;

i) storing the at least a trained codevector in the respective codebook; and

,

j) encoding each of the un-encoded data vectors based on a codevector of the at least a trained codevector.

4. A method for compressing a continuous data flow as defined in claim 3 wherein in step f) the determined un-encoded data vectors are collected until a sufficiently large number of un-encoded data vectors suitable for codevector training is accumulated.

5. A method for compressing a continuous data flow as defined in claim 4 wherein step g) is performed after a predetermined number of data subsets have been processed.

6. A method for compressing a continuous data flow in real-time as defined in claim 5 comprising the steps of:

storing in an index map an index indicative of a codevector'"'"'s location within the respective codebook; and

,

providing the index map and the respective codebook for transmission after the predetermined number of data subsets have been processed.

7. A method for compressing a continuous data flow as defined in claim 6 comprising the steps of:

receiving the first data subset of the continuous data flow, the first data subset comprising a plurality of data vectors indicative of the first portion of the image of an object;

determining a plurality of codevectors through training for approximating the data vectors of the plurality of data vectors of the first data subset with a fidelity above a predetermined threshold based on the plurality of data vectors of the first data subset;

encoding the data vectors based on the plurality of codevectors; and

,

storing the plurality of codevectors in a first codebook and storing in a first index map an index indicative of a codevector'"'"'s location within the first codebook.

8. A method for compressing a continuous data flow as defined in claim 1 comprising the steps of:

e) when the fidelity for the approximation of a data vector of the n^th data subset is below the predetermined threshold performing the step of selecting a second codevector from the n−

2^th codebook that approximates the data vector;

f) determining a fidelity for the second approximation of the data vector; and

,

g) when the fidelity for the second approximation of the data vector is above the predetermined threshold performing the step of encoding the data vector based on the selected second codevector.

9. A method for compressing a continuous data flow as defined in claim 8 comprising the step of:

h) repeating the steps a) to g) for encoding data vectors of data subsets received subsequent to the n^th.

10. A method for compressing a continuous data flow comprising the steps of:

a) receiving a n^th data subset of a m^th region of the continuous data flow, the n^th data subset comprising a plurality of data vectors indicative of a n^th portion of a m^th region of an image of an object;

b) selecting for each data vector of the n^th data subset of the m^th region a codevector from a m^th regional codebook that approximates the respective data vector, the m^th regional codebook being different from the m−

1^th regional codebook, the m^th regional codebook comprising codevectors for encoding at least a portion of the data vectors of at least a data subset of the first to the n−

1^th data subsets of the m^th region;

c) determining a fidelity for the approximation of each data vector of the n^th data subset of the m^th region; and

,

d) when the fidelity for the approximation of a data vector of the n^th data subset of the m^th region is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector.

11. A method for compressing a continuous data flow as defined in claim 10 comprising the step of:

d1) storing in a m^th regional index map an index indicative of the codevector'"'"'s location within the m^th regional codebook.

12. A method for compressing a continuous data flow as defined in claim 11 comprising the steps of:

e) when the fidelity for the approximation of a data vector of the n^th data subset of the m^th region is below the predetermined threshold performing the step of selecting a second codevector from the m−

1^th regional codebook that approximates the data vector;

f) determining a fidelity for the second approximation of the data vector; and

,

g) when the fidelity for the second approximation of the data vector is above the predetermined threshold performing the step of encoding the data vector based on the selected second codevector.

13. A method for compressing a continuous data flow as defined in claim 12 comprising the steps of:

h) providing an index indicative of the second codevector'"'"'s location within the m−

1^th regional codebook for transmission;

i) providing a copy of the second codevector to the m^th regional codebook stored in working memory;

j) storing a copy of the second codevector in the m^th regional codebook; and

,

k) storing in the m^th regional index map an index indicative of the second codevector'"'"'s location within the m^th regional.

14. A method for compressing a continuous data flow as defined in claim 13 comprising the step of:

l) repeating the steps a) to k) for encoding data vectors of a n+1^th data subset received subsequent to the n^th data subset within the m^th region.

15. A method for compressing a continuous data flow as defined in claim 14 comprising the steps of:

m) determining un-encoded data vectors from at least two data subsets;

n) determining at least a codevector through training for approximating the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;

o) storing the at least a trained codevector in the m^th regional codebook; and

,

l) encoding each of the un-encoded data vectors using the respective codevector of the at least a trained codevectors.

16. A method for compressing a continuous data flow as defined in claim 15 wherein in step m) the determined un-encoded data vectors are collected until a sufficiently large number of un-encoded data vectors suitable for codevector training is accumulated.

17. A method for compressing a continuous data flow as defined in claim 16 wherein step n) is performed after a predetermined number of data subsets have been processed.

18. A method for compressing a continuous data flow as defined in claim 17 wherein the predetermined number of data subsets is the number of data subsets within the m^th region.

19. A method for compressing a continuous data flow as defined in claim 15 comprising the step of:

p) storing in the m^th regional index map at least an index indicative of the at least a trained codevector'"'"'s location within the m^th regional codebook.

20. A method for compressing a continuous data flow as defined in claim 18 comprising the step of:

q) providing the m^th regional codebook and the m^th regional index map for transmission.

21. A method for compressing a continuous data flow as defined in claim 20 wherein the steps a) to q) are repeated for subsequent regions.

22. A method for compressing a continuous data flow as defined in claim 21 wherein same codevectors are used for encoding the data vectors in boundary areas connecting two adjacent regions, the boundary areas comprising at least the last data subset of the m^th region and at least the first data subset of the m+1^th region.

23. A method for compressing a continuous data flow as defined in claim 22 comprising the steps of:

receiving the first data subset of the first region of the continuous data flow, the first data subset comprising a plurality of data vectors indicative of the first portion of the first region of the image of an object;

determining a plurality of codevectors through training for approximating the data vectors of the plurality of data vectors of the first data subset with a fidelity above a predetermined threshold based on the plurality of data vectors of the first data subset;

encoding the data vectors based on the plurality of codevectors; and

,

storing the plurality of codevectors in the first regional codebook and storing in the first regional index map an index indicative of a codevector'"'"'s location within the first regional codebook.

24. A method for compressing a continuous data flow as defined in claim 12 wherein the steps b) to g) are implemented using HSOCVQ.

25. A method for compressing a continuous data flow as defined in claim 12 wherein each data vector of the plurality of data vectors comprises imaging data corresponding to a respective image pixel of a plurality of image pixels.

26. A method for compressing a continuous data flow as defined in claim 25 wherein the plurality of image pixels are arranged in a line oriented in across-track direction.

27. A method for compressing a continuous data flow as defined in claim 26 wherein the data vectors comprise hyper-spectral vectors.

28. A storage medium having stored thereon at least an executable command for when executed resulting in performance of the steps of:

a) receiving a n^th data subset of a m^th region of the continuous data flow, the n^th data subset comprising a plurality of data vectors indicative of a n^th portion of a m^th region of an image of an object;

b) selecting for each data vector of the n^th data subset of the m^th region a codevector from a m^th regional codebook that approximates the respective data vector, the m^th regional codebook comprising codevectors for encoding at least a portion of the data vectors of the first to the n−

1^th data subsets of the m^th region;

c) determining a fidelity for the approximation of each data vector of the n^th data subset of the m^th region;

d) when the fidelity for the approximation of a data vector of the n^th data subset of the m^th region is above a predetermined threshold performing the step of encoding the data vector using the selected codevector and storing in a m^th regional index map an index indicative of the selected codevector'"'"'s location within the m^th regional codebook;

e) when the fidelity for the approximation of a data vector of the n^th data subset of the m^th region is below the predetermined threshold performing the step of selecting a second codevector from the m−

1^th regional codebook that approximates the data vector;

f) determining a fidelity for the second approximation of the data vector;

g) when the fidelity for the second approximation of the data vector is above the predetermined threshold performing the step of encoding the data vector based on the selected second codevector, storing a copy of the second codevector in the m^th regional codebook, storing in the m^th regional index map an index indicative of the second codevector'"'"'s location within the m^th regional;

h) repeating the steps a) to g) for encoding data vectors of subsequent data subsets within the m^th region;

i) collecting un-encoded data vectors of subsequent data subsets;

j) determining at least a codevector through training for approximating the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;

k) storing the at least a trained codevector in the m^th regional codebook;

l) encoding each of the un-encoded data vectors based on the respective codevector of the at least a trained codevectors;

n) providing the m^th regional codebook and the m^th regional index map for transmission; and

, repeating the steps a) to n) for subsequent regions.

29. A system for compressing a continuous data flow comprising:

a first port for receiving the continuous data flow;

electronic circuitry in data communication with the first port, the electronic circuitry for performing the steps of;

a) receiving a n^th data subset of a m^th region of the continuous data flow, the n^th data subset comprising a plurality of data vectors indicative of a n^th portion of a m^th region of an image of an object;

b) selecting for each data vector of the n^th data subset of the m^th region a codevector from a m^th regional codebook that approximates the respective data vector, the m^th regional codebook comprising codevectors for encoding at least a portion of the data vectors of the first to the n−

1^th data subsets of the m^th region;

c) determining a fidelity for the approximation of each data vector of the n^th data subset of the m^th region;

d) when the fidelity for the approximation of a data vector of the n^th data subset of the m^th region is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector, and storing in a m^th regional index map an index indicative of the selected codevector'"'"'s location within the m^th regional codebook;

e) when the fidelity for the approximation of a data vector of the n^th data subset of the m^th region is below the predetermined threshold performing the step of selecting a second codevector from the m−

1^th regional codebook that approximates the data vector;

f) determining a fidelity for the second approximation of the data vector;

g) when the fidelity for the second approximation of the data vector is above the predetermined threshold performing the step of encoding the data vector based on the selected second codevector, storing a copy of the second codevector in the m^th regional codebook, storing in the m^th regional index map an index indicative of the second codevector'"'"'s location within the m^th regional;

h) repeating the steps a) to g) for encoding data vectors of subsequent data subsets within the m^th region;

i) collecting un-encoded data vectors of subsequent data subsets;

j) determining at least a codevector through training for approximating the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;

k) storing the at least a trained codevector in the m^th regional codebook;

l) encoding each of the un-encoded data vectors based on the respective codevector of the at least a trained codevectors;

n) providing the m^th regional codebook and the m^th regional index map for transmission; and

, repeating the steps a) to n) for subsequent regions; and

,

a second port in data communication with the electronic circuitry for providing the regional codebook and the regional index map.

30. A storage medium having stored thereon at least an executable command for when executed resulting in performance of the steps of:

a) receiving a n^th data subset of the continuous data flow, the n^th data subset comprising a plurality of data vectors indicative of a n^th portion of an image of an object;

b) selecting for each data vector of the n^th data subset a codevector from a n−

1^th codebook that approximates the respective data vector, the n−

1^th codebook comprising codevectors for encoding at least a portion of the data vectors of the n−

1^th data subset;

c) determining a fidelity for the approximation of each data vector of the n^th data subset;

d) when the fidelity for the approximation of a data vector of the n^th data subset is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector;

e) repeating the steps a) to d) for encoding data vectors of subsequent data subsets;

f) determining un-encoded data vectors from at least two data subsets;

g) determining at least a codevector through training for approximating each of the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;

i) storing the at least a trained codevector in the respective codebook;

j) encoding the un-encoded data vectors based on the at least a trained codevector; and

, storing in an index map an index indicative of a codevector'"'"'s location within the respective codebook.

31. A system for compressing a continuous data flow comprising:

a first port for receiving the continuous data flow;

electronic circuitry in data communication with the first port, the electronic circuitry for performing the steps of;

a) receiving a n^th data subset of the continuous data flow, the n^th data subset comprising a plurality of data vectors indicative of a n^th portion of an image of an object;

b) selecting for each data vector of the n^th data subset a codevector from a n−

1^th codebook that approximates the respective data vector, the n−

1^th codebook comprising codevectors for encoding at least a portion of the data vectors of the n−

1^th data subset;

c) determining a fidelity for the approximation of each data vector of the n^th data subset;

d) when the fidelity for the approximation of a data vector of the n^th data subset is above a predetermined threshold performing the step of encoding the data vector based on the selected codevector;

e) repeating the steps a) to d) for encoding data vectors of subsequent data subsets;

f) determining un-encoded data vectors from at least two data subsets;

g) determining at least a codevector through training for approximating each of the un-encoded data vectors with a fidelity above the predetermined threshold based on the collected un-encoded data vectors;

i) storing the at least a trained codevector in the respective codebook;

j) encoding the un-encoded data vectors based on the at least a trained codevector; and

, storing in an index map an index indicative of a codevector'"'"'s location within the respective codebook; and

,

a second port in data communication with the electronic circuitry for providing the codebook and the index map.