Method and apparatus for the compression and decompression of image files using a chaotic system

• US 7,110,547 B2
• Filed: 01/09/2001
• Issued: 09/19/2006
• Est. Priority Date: 06/20/2000
• Status: Expired due to Term

• Current Assignee: University of New Hampshire
• Original Assignee: University of New Hampshire
• Inventors: Short, Kevin M.
• Primary Examiner(s): Song, Hosuk
• Assistant Examiner(s): TRUONG, THANHNGA B
• Application Number:
  US09/756,814
• Publication Number:
  US 20030169940A1
• Time in Patent Office: 2,079 Days
• Field of Search: 380/263, 380/28, 380/46, 380/217, 380/269, 846/03, 382/249, 708/203
• US Class Current: 380/263
• CPC Class Codes: G10H 1/0041 in coded form
• CPC Class Codes: G10H 2250/235 Fourier transform; Discrete Fourier Transform [DFT]; Fast Fourier Transform [FFT]
• CPC Class Codes: G10H 2250/581 Codebook-based waveform compression
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/174 the region being a slice, e.g. a line of blocks or a group of blocks
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

A system for the compression and decompression of image files is provided. A library of basic waveforms is produced by applying selected digital initialization codes to a chaotic system. Each basic waveform is in one-to-one correspondence with an initialization code. A weighted sum of selected basic waveforms is used to approximate each slice of an image. The basic waveforms are then discarded and only the weighting factors and the corresponding initialization codes are stored in a compressed image file. When the compressed image file is decompressed for playback, the stored initialization codes are stripped out and applied to a similar chaotic system to regenerate the basic waveforms, which are recombined according to the stored weighting factors to produce an approximation of the original image slice.

Claims

1. A method of compressing an image file comprising:

choosing an image to be compressed and decomposing the image into slices;

finding a trend line for each slice and calculating trend line information describing the trend line;

calculating for each slice a detrended image slice, by subtracting from each slice its trend line and storing the trend line information describing the trend line;

choosing a chaotic system;

applying selected digital initialization codes to the chaotic system such that each initialization code produces a periodic orbit and stabilizes the otherwise unstable periodic orbit;

generating a basic waveform for each periodic orbit such that the basic waveform is in a one-to-one correspondence to the initialization code for the periodic orbit;

selecting basic waveforms to be used with each detrended image slice and storing their corresponding initialization codes; and

providing a compressed image file, wherein the compressed image file comprises the initialization codes and trend line information for each detrended slice.

2. The method of compressing an image file of claim 1 further comprising:

calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors; and

removing from the weighted sum of the selected basic waveforms any selected basic waveforms not deemed necessary to approximate sufficiently well the image file and of removing the corresponding stored initialized codes.

3. The method of compressing an image file of claim 1 further comprising:

calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors; and

identifying trends over sections of compressed image file and replacing the stored weighting factors for the sections of compressed image file by a suitable function.

4. The method of claim 1, further comprising providing a suitable function to weight the selected basic waveforms.

5. The method of claim 1 further comprising:

choosing a compressed image file;

stripping stored initialization codes out of the compressed image file and applying the stored initialization codes to a chaotic system substantially the same as the chaotic system used in producing the compressed image file to produce the corresponding basic waveforms;

stripping the trend line information out of the compressed image file and using the trend line information to regenerate a trend line to add to the detrended image slice to produce an approximation of an original image slice.

6. The method of claim 1, further comprising:

transforming the detrended image slice and the selected basic waveforms to a proper frequency range and storing frequency information describing the transformation.

7. The method of claim 1, further comprising:

calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors.

8. The method of claim 1, further comprising:

transforming the detrended image slice and the selected basic waveforms to a proper frequency range and storing frequency information describing the transformation; and

calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors.

9. The method of claim 1, further comprising:

transforming the detrended image slice and the selected basic waveforms to a proper frequency range and storing frequency information describing the transformation;

calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors; and

combining the stored trend line information, the stored initialization codes, the stored frequency information and the stored weighting factors for each detrended image slice to comprise a compressed image file.

10. The system of claim 1, further comprising:

transforming the detrended image slice and the selected basic waveforms to a proper frequency range and storing frequency information describing the transformation;

calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors;

providing the weighting factors and the frequency information in the compressed file;

stripping the stored frequency information out of the compressed image file and using the stored frequency information to transfer the basic waveform to the proper frequency range; and

combining the basic waveforms according to the stored weighting factors to produce a detrended image slice.

11. A system of compressing an image file comprising:

means for choosing an image to be compressed and decomposing the image into slices;

means for finding a trend line for each slice and calculating trend line information describing the trend line;

means for calculating for each slice a detrended image slice, by subtracting from each slice its trend line and storing the trend line information describing the trend line;

means for choosing a chaotic system;

means for applying selected digital initialization codes to the chaotic system such that each initialization code produces a periodic orbit and stabilizes the otherwise unstable periodic orbit;

means for generating a basic waveform for each periodic orbit such that the basic waveform is in a one-to-one correspondence to the initialization code for the periodic orbit;

means for selecting basic waveforms to be used with each detrended image slice and storing their corresponding initialization codes;

means for providing a compressed image file, wherein the compressed file comprises the initialization codes and trend line information for each detrended slice.

12. The means for compressing an image file of claim 11 further comprising:

means for calculating weighting factors to weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors; and

means for removing from the weighted sum of the selected basic waveforms any selected basic waveforms not deemed necessary to approximate sufficiently well the image file and the means for removing the corresponding stored initialized codes.

13. The means for compressing an image file of claim 11 further comprising:

means for calculating a suitable function to weight the selected basic waveforms; and

means for identifying trends over sections of compressed image file.

14. The system of claim 11 further comprising:

means for choosing a compressed image file;

means for stripping stored initialization codes out of the compressed image file and applying the stored initialization codes to a chaotic system substantially the same as the chaotic system used in producing the compressed image file to produce the corresponding basic waveforms;

means for stripping the trend line information out of the compressed image file and using the trend line information to regenerate a trend line to add to the detrended image slice to produce an approximation of an original image slice.

15. The system of claim 11 further comprising:

means for transforming the detrended image slice and the selected basic waveforms to a proper frequency range and storing frequency information describing the transformation.

16. The system of claim 11 further comprising:

means for calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors.

17. The system of claim 11 further comprising:

means for transforming the detrended image slice and the selected basic waveforms to a proper frequency range and storing frequency information describing the transformation; and

means for calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors.

18. The system of claim 11 further comprising:

means for transforming the detrended image slice and the selected basic waveforms to a proper frequency range and storing frequency information describing the transformation;

means for calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors; and

means for combining the stored trend line information, the stored initialization codes, the stored frequency information and the stored weighting factors for each detrended image slice to comprise a compressed image file.

19. The system of claim 11 further comprising:

means for transforming the detrended image slice and the selected basic waveforms to a proper frequency range and storing frequency information describing the transformation;

means for calculating weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and storing the weighting factors;

means for providing the weighting factors and the frequency information in the compressed file;

means for stripping the stored frequency information out of the compressed image file and using the stored frequency information to transfer the basic waveform to the proper frequency range; and

means for combining the basic waveforms according to the stored weighting factors to produce a detrended image slice.

20. A system for compressing an image file comprising:

a chaotic system;

a compression controller to apply selected digital initialization codes to the chaotic system to drive it onto periodic orbits and to produce a basic waveform for each periodic orbit that is in a one-to-one correspondence with the initialization code for the periodic orbit;

an image decomposer to decompose an image to be compressed into slices;

a slice data detrender to calculate for each slice a detrended image slice by subtracting from each slice its trend line and to store the trend line information;

a waveform comparator to select the basic waveforms to be used with each detrended image slice and to store their corresponding initialization codes; and

a storage device to combine at least the stored trend line information, and the stored initialization codes for each detrended image slice to comprise a compressed image file.

21. The system of claim 20 further comprising:

a waveform weighter to transform the detrended image slice and the selected basic waveforms to a proper frequency range and to store frequency information describing the transformation.

22. The system of claim 20, further comprising:

a waveform weighter to calculate weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and to store the weighting factors.

23. The system of claim 20 further comprising:

a waveform weighter (i) to transform the detrended image slice and the selected basic waveforms to a proper frequency range and to store frequency information describing the transformation and (ii) to calculate weighting factors to create a weighted sum of the selected basic waveforms to approximate each detrended image slice and to store the weighting factors.

24. The system of claim 20 further comprising:

a waveform weighter (i) to transform the detrended image slice and the selected basic waveforms to a proper frequency range and to store frequency information describing the transformation and (ii) to calculate weighting factors to create a weighted sum of the selected basic waveforms to approximate, each detrended image slice and to store the weighting factors, wherein the storage device combines at least the stored trend line information and the stored initialization codes, the stored frequency information and the stored weighting factors for each detrended image slice to comprise a compressed image file.

25. A method of compressing a data signal, using a chaotic system, comprising:

identifying a trend in the portion of the data signal;

removing the trend from the portion of the data signal to provide detrended data;

causing the chaotic system to assume a periodic orbit by applying an initialization code to the chaotic system;

generating a periodic waveform for the periodic orbit;

weighting the periodic waveform to approximate at least a portion of the detrended data signal; and

merging the initialization code, information about the identified trend, and a representation of the weighting, to compress the portion of the data signal.

26. The method of claim 25, including stabilizing the periodic orbit.

27. The method of claim 25, wherein identifying the trend includes determining a mathematical model for the trend.

28. The method of claim 25, wherein the data signal comprises image data.

29. The method of claim 25, wherein the data signal comprises audio and image data.

30. A method of compressing a data signal, using a chaotic system, comprising:

a. causing the chaotic system to assume a plurality of periodic orbits by applying a plurality of initialization codes to the chaotic system;

b. generating a periodic waveform for each of a subset of the periodic orbits;

c. weighting a subset of the generated periodic waveforms to approximate at least a portion of the data signal; and

d. merging the initialization codes and information representative of the weighting, to compress the portion of the data signal.

31. The method of claim 30, including assigning a zero weight to at least one of the subset of generated periodic waveforms.

32. A method of compressing a slice of image data using a chaotic system, comprising:

a. causing the chaotic system to assume a plurality of periodic orbits by applying a plurality of initialization codes to the chaotic system;

b. generating a periodic waveform for each of the periodic orbits;

c. weighting the periodic waveforms to approximate at least a portion of the slice of image data; and

d. merging the initialization codes and information representative of the weighting, to compress the slice of image data.

33. A method of compressing a slice of image data using a chaotic system, comprising:

a. causing the chaotic system to assume at least one periodic orbit by applying at least one initialization code to the chaotic system;

b. generating a periodic waveform for each of a subset of the at least one periodic orbit;

c. weighting a subset of the generated periodic waveforms to approximate at least a portion of the slice of image data; and

d. merging the at least one initialization code and information representative of the weighting, to compress the slice of image data.

34. A method of compressing a data signal, using a chaotic system, comprising:

a. causing the chaotic system to assume a periodic orbit by applying an initialization code to the chaotic system;

b. generating a periodic waveform for the periodic orbit;

c. weighting the periodic waveform to approximate a first portion of the data signal;

d. identifying a correlation between data in the first portion of the data signal and data in at least one other portion of the data signal;

e. merging the initialization code, a representation of the weighting, and a representation of the correlation, to represent the first portion of the data signal and the at least one other portion of the data signal, to compress the data signal.

35. A method of decompressing a compressed representation of a first data signal, the compressed representation produced using a first chaotic system and containing an initialization code, comprising:

a. causing a second chaotic system, substantially identical to the first chaotic system, to assume a predetermined periodic orbit by applying the initialization code to the second chaotic system;

b. generating a periodic waveform for the periodic orbit; and

c. applying a predetermined weighting to the periodic waveform to produce at least a portion of a second data signal substantially identical to at least a portion of the first data signal.

36. The method of claim 35, including stabilizing the periodic orbit.

37. The method of claim 35, wherein the compressed representation includes trend information for the at least a portion of the first data signal.

38. The method of claim 37, including applying the trend information to the at least a portion of the second data signal, to substantially reproduce the at least a portion of the first data signal.

39. The method of claim 37, wherein the trend information includes a mathematical model of the trend.

40. The method of claim 35, wherein the data signal comprises image data.

41. The method of claim 35, wherein the data signal comprises audio and image data.

42. A method of decompressing a compressed representation of a first slice of image data, the compressed representation produced using a first chaotic system and containing at least one initialization code, comprising:

a. causing a second chaotic system, substantially identical to the first chaotic system, to assume at least one predetermined periodic orbit by applying the at least one initialization code to the second chaotic system;

b. generating a predetermined periodic waveform for each of a subset of the at least one predetermined periodic orbit; and

c. applying a predetermined weighting to at least one generated predetermined periodic waveform to produce at least a portion of a second slice of image data substantially identical to at least a portion of the first slice of image data.

43. A method of decompressing a compressed representation of a first data signal, the compressed representation produced using a first chaotic system and containing a plurality of initialization codes, comprising:

a. causing a second chaotic system, substantially identical to the first chaotic system, to assume a plurality of predetermined periodic orbits by applying the initialization codes to the second chaotic system;

b. generating a predetermined periodic waveform for each of a subset of the predetermined periodic orbits; and

c. applying a predetermined weighting to at least one generated periodic waveform to produce at least a portion of a second data signal substantially identical to at least a portion of the first data signal.

44. A method of decompressing a compressed representation of a first data signal, the compressed representation produced using a first chaotic system and containing a plurality of initialization codes, comprising:

a. causing a second chaotic system, substantially identical to the first chaotic system, to assume a predetermined periodic orbit by applying the initialization codes to the second chaotic system;

b. generating a periodic waveform for the periodic orbit;

c. applying a predetermined weighting to the periodic waveform to produce a first portion of a second data signal substantially identical to a first portion of the first data signal; and

d. applying, to the first portion of the second data signal, a predetermined correlation between data in the first portion of the first data signal and data in at least one other portion of the first data signal, to produce at least one other portion of the second data signal substantially identical to the at least one other portion of the first data signal.