Apparatus and method for encoding and decoding digital signals

• US 5,497,435 A
• Filed: 02/23/1993
• Issued: 03/05/1996
• Est. Priority Date: 02/07/1993
• Status: Expired due to Term

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Image Compression Technology Ltd.
• Inventors: Berger, Marc A.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Kelley, Christopher S.
• Application Number:
  US08/021,084
• Time in Patent Office: 1,106 Days
• Field of Search: 382/56, 348/397-399, 348/437, 348/438
• US Class Current: 382/249
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/99 involving fractal coding

Abstract

A digital signal encoding method including the steps of defining first and second components of an original digital signal on each of two scales, fractal-processing the two first components by conducting a comparison therebetween and generating an encoded digital signal including a representation of at least one of the smooth components and a representation of the result of the fractal-processing step.

Claims

1. A digital signal encoding method for image compression followed by at least one of storage and transmission thereof, comprising the step of:

defining relatively high frequency and relatively low frequency components of an original digital signal representing an image comprised of segments on each of two scales, said components being defined for each segment;

fractal-processing the two relatively high frequency components by conducting a comparison therebetween;

generating an encoded digital signal comprising a representation of at least one of the relatively low frequency components and a representation of a result of the fractal-processing step for each segment;

utilizing said encoded digital signal to provide at least one of storage and transmission of a compressed image.

2. A method according to claim 1 wherein said step of defining comprises the step of:

defining a relatively high frequency component on one of the two scales as the difference between the original signal and the relatively low frequency component on said scale.

3. A method according to claim 1 wherein said step of defining comprises the step of:

segmenting the original digital signal by defining coarse and fine grids corresponding to first and second ones of the two scales, respectively.

4. A method according to claim 3 wherein said step of defining comprises the following steps:

computing an average value for the original digital signal in each segment from among two pluralities of segments defined by the coarse and fine grids respectively; and

for each plurality of segments, passing functions through the average values, thereby defining the relatively low frequency components for each of the two scales.

5. A method according to claim 3 wherein said step of defining comprises the step of:

low-pass filtering the original digital signal with first and second cut-off frequencies determined respectively by the coarse and fine grids, thereby defining the relatively low frequency components.

6. A method according to claim 5 wherein said step of low-pass filtering comprises the steps of:

computing a Discrete Fourier Transform of the original digital signal;

truncating the Discrete Fourier Transform at the first and second cut-off frequencies, thereby defining truncated signals; and

performing an inverse Discrete Fourier Transform on the truncated signals.

7. A method according to claim 5 wherein said step of low-pass filtering comprises the steps of:

computing a Discrete Cosine Transform of the original digital signal;

truncating the Discrete Cosine Transform at the first and second cut-off frequencies, thereby defining truncated signals; and

performing an inverse Discrete Cosine Transform on the truncated signals.

8. A method according to claim 1 wherein the original signal comprises a video signal including a plurality of frames and wherein the step of defining comprises for each frame of the video signal, the steps of:

defining first relatively high frequency and relatively low frequency components of the current frame on a first scale; and

defining second relatively high frequency and relatively low frequency components on a frame following the current frame on a second scale.

9. A method according to claim 1 wherein the original signal comprises and audio signal sampled digitally, and wherein the sampled signal is segmented into windows which are adaptively clipped as the signal is generated, and the steps of defining, fractal-processing and generating are carried out separately for each clipped window of the sampled signal.

10. A method according to claim 1 wherein the original signal comprises a greyscale image.

11. A method according to claim 1 wherein the original signal comprises a color image defining a plurality of color component images.

12. A method according to claim 11 wherein the steps of defining, fractal-processing and generating are performed on each of the plurality of color component images.

13. A method according to claim 1 wherein the original signal comprises a color image defined by a color palette.

14. A method according to claim 11 and also comprising a palette selection step in which the plurality of color component images are compressed into a color values palette comprising a multiplicity of color palette values and wherein the original digital signal processed in said steps of defining, fractal-processing and generating comprises the multiplicity of color palette values.

15. A method according to claim 3 wherein the step of fractal-processing comprises the steps of:

shrinking a portion of the relatively high frequency component of the original digital signal contained in each coarse grid segment so as to fit the size of a fine grid segment;

for each fine grid segment, performing the step of;

searching among the shrunk relatively high frequency component portions for a shrunk relatively high frequency component portion which matches well with a portion of the relatively high frequency component contained in the fine grid segment.

16. A method according to claim 15 and also comprising the step of:

storing a result of the searching step comprising a shrunk relatively high frequency component portion index and a matching operation.

17. A method according to claim 15 wherein said shrinking comprises, for each fine grid pixel, the step of:

averaging pixel values of the relatively high frequency component defined in the coarse scale, over a region corresponding to the fine grid pixel position.

18. A method according to claim 16 wherein said matching operation comprises a scale factor by which the shrunk relatively high frequency portion is multiplied, and wherein said well-matching portion is identified using a sum of squares error criterion.

19. A method according to claim 1 and also comprising the step of providing a packed encoded digital signal, the step of providing comprising the steps of:

quantizing the encoded digital signal, thereby defining a quantized encoded digital signal;

storing the quantized encoded digital signal in byte form, thereby defining a stored quantized encoded digital signal; and

compressing the stored quantized encoded digital signal.

20. A method according to claim 19 wherein the step of compressing comprises the step of operating at least one of the following compression algorithms on the stored quantized encoded digital signal:

a Lempel-Ziv compression algorithm; and

a Huffman compression algorithm.

21. A method according to claim 1 and also comprising the step of generating the original digital signal by transforming a precursor digital signal to a frequency domain.

22. A method according to claim 21 wherein the step of generating an original digital signal comprises the step of performing a Discrete Fourier Transform on the precursor digital signal.

23. A method according to claim 21 wherein the step of generating an original digital signal comprises the step of performing a Discrete Cosine Transform on the precursor digital signal.

42. A method according to claim 1 and also comprising the steps of:

transmitting the encoded signal along a telecommunication channel;

receiving the encoded signal from the telecommunication channel; and

decoding the received encoded signal.

43. A method according to claim 42 wherein said step of decoding comprises the steps of:

extracting a coarse relatively low frequency signal component, a fine relatively low frequency signal component and fractal information from the received encoded digital signal;

computing a difference between a reference digital signal and the coarse relatively low frequency signal component, thereby defining a difference signal;

performing a plurality of linear shrinking and scaling Operations on a plurality of portions of said difference signal contained in respective coarse grid segments using the fractal information, thereby defining a modified difference signal; and

adding the fine relatively low frequency signal component with the modified difference signal, thereby defining a decoded digital signal which substantially reconstructs the original signal.

44. A method according to claim 43 whereby the original signal comprises a video signal including a plurality of frames, and wherein the step of extracting comprises, for each current frame of the video signal, the steps of:

defining first relatively high frequency and relatively low frequency components of the current frame on a first scale;

defining second relatively high frequency and relatively low frequency components of a frame following the current frame on a second scale;

and wherein the step of extracting comprises, for each frame of the video signal, the step of;

defining a coarse relatively low frequency signal component and a fine relatively low frequency signal component from a frame preceding the current frame and from the current frame, respectively.

45. A method according to claim 43 wherein the original signal is an audio signal sampled digitally, and the sampled signal is segmented into windows which are adaptively clipped as the signal is generated, and the steps of defining, fractal-processing, generating, transmitting, receiving, extracting, computing, performing and adding are carried out separately for each clipped window of the sampled signal.

46. A method according to claim 43 wherein the original signal comprises a greyscale image.

47. A method according to claim 43 wherein the original signal comprises a color image defining a plurality of color component images.

48. A method according to claim 47 wherein the steps of defining, fractal-processing, generating, transmitting, receiving, extracting, computing, performing and adding are performed on each of the plurality of color component images.

49. A method according to claim 43 wherein the original signal comprises a color image defined by a color palette.

50. A method according to claim 47 and also comprising a palette selection step in which the plurality of color component images are compressed into a color palette comprising a multiplicity of color palette values and wherein the original digital signal processed in said steps of defining, fractal-processing and generating comprises the multiplicity of color palette values, and wherein the decoded signal is further processed by a table look-up through the color palette.

51. A method according to claim 43 wherein said step of defining comprises the step of:

defining a relatively high frequency component on one of the two scales as the difference between the original signal and the relatively low frequency component on said scale.

52. A method according to claim 43 wherein said step of defining comprises the step of:

segmenting the original digital signal by defining coarse and fine grids corresponding to first and second ones of the two scales, respectively.

53. A method according to claim 52 wherein said step of defining comprises the following steps:

computing an average value for the original digital signal in each segment from among two pluralities of segments defined by the coarse and fine grids respectively; and

for each plurality of segments, passing functions through the average values, thereby defining the relatively low frequency components for each of the two scales.

54. A method according to claim 52 wherein said step of defining comprises the step of:

low-pass filtering the original digital signal with first and second cut-off frequencies determined respectively by the coarse and fine grids, thereby defining the relatively low frequency components.

55. A method according to claim 54 wherein said step of low-pass filtering comprises the steps of:

computing a Discrete Fourier Transform of the original digital signal;

truncating the Discrete Fourier Transform at the first and second cut-off frequencies, thereby defining truncated signals; and

performing an inverse Discrete Fourier Transform on the truncated signals.

56. A method according to claim 54 wherein said step of low-pass filtering comprises the steps of:

computing a Discrete Cosine Transform of the original digital signal;

truncating the Discrete Cosine Transform at the first and second cut-off frequencies, thereby defining truncated signals; and

performing an inverse Discrete Cosine Transform on the truncated signals.

57. A method according to claim 43 wherein the step of fractal-processing comprises the steps of:

shrinking a portion of the relatively high frequency component of the original digital signal contained in each coarse grid segment so as to fit the size of a fine grid segment;

for each fine grid segment, performing the step of;

searching among the shrunk relatively high frequency component portions for a shrunk relatively high frequency component portion which matches well with a portion of the relatively high frequency component contained in the fine grid segment.

58. A method according to claim 57 and also comprising the step of:

storing a result of the searching step comprising a shrunk relatively high frequency component portion index and a matching operation.

59. A method according to claim 57 wherein said shrinking step comprises, for each fine grid pixel, the step of:

averaging pixel values of the relatively high frequency component defined in the coarse scale, over a region corresponding to the fine grid pixel position.

60. A method according to claim 58 wherein said matching operation comprises a scale factor by which the shrunk relatively high frequency portion is multiplied, and wherein said well-matching portion is identified using a sum of squares error criterion.

61. A method according to claim 43 and also comprising the steps of:

generating the encoded signal by packing a precursor encoded signal for transmission along the channel, the step of packing comprising the steps of;

quantizing the precursor encoded digital signal, thereby defining a quantized encoded digital signal;

storing the quantized encoded digital signal in byte form, thereby defining a stored quantized encoded digital signal; and

compressing the stored quantized encoded digital signal; and

unpacking the packed encoded signal after it is received, the step of unpacking comprising the steps of;

decompressing the packed encoded digital signal into a plurality of bytes;

reconstructing the quantized encoded digital signal from the plurality of bytes; and

performing inverse quantization on the quantized encoded digital signal, thereby generating the received encoded digital signal.

62. A method according to claim 61 wherein the step of compressing comprises the step of:

operating at least one of the following compression algorithmsaon the stored quantized encoded digital signal;

Lempel-Ziv compression algorithm; and

a Huffman compression algorithm.

63. A method according to claim 61 wherein the step of decompressing comprises the step of:

operating at least one of the following decompression algorithmsaon the packed encoded digital signal;

Lempel-Ziv decompression algorithm; and

a Huffman decompression algorithm.

64. A method according to claim 43 and also comprising the steps of:

generating the original digital signal by transforming a precursor digital signal to a frequency domain; and

transforming the decoded signal out of the frequency domain.

65. A method according to claim 64 wherein the step of generating the original digital signal comprises the step of:

performing a Discrete Fourier Transform on the precursor digital signal.

66. A method according to claim 64 wherein the step of generating the original digital signal comprises the step of:

performing a Discrete Cosine Transform on the precursor digital signal.

67. A method according to claim 64 wherein the step of transforming out of a frequency domain comprises the step of:

performing an inverse Discrete Fourier Transform on the decoded signal.

68. A method according to claim 64 wherein the step of transforming out of a frequency domain comprises the step of:

performing an inverse Discrete Cosine Transform on the decoded signal.

69. A method according to claim 43 wherein the step of performing comprises, for each fine grid segment, the following steps:

deriving an index and a matching operation from the fractal information;

shrinking the portion of the difference signal contained in a coarse grid segment corresponding to the index so as to fit the size of a fine grid segment; and

applying the matching operation to the shrunk portion of the difference signal, thereby to define the modified difference signal within the fine grid segment.

70. A method according to claim 69 wherein said shrinking step comprises, for each fine grid pixel, the step of:

averaging pixel values of the difference signal over a region corresponding to the fine grid pixel position.

71. A method according to claim 69 wherein said matching operation comprises a multiplication of the shrunk relatively high frequency portion by a scale factor.

72. A method according to claim 1 and also comprising the steps of:

archiving the encoded signal into a digital storage medium;

retrieving the encoded signal from the digital storage medium; and

decoding the retrieved encoded signal.

73. A method according to claim 72 wherein said step of decoding comprises the steps of:

extracting a coarse relatively low frequency signal component, a fine relatively low frequency signal component and fractal information from the received encoded digital signal;

computing a difference between a reference digital signal and the coarse relatively low frequency signal component, thereby defining a difference signal;

performing a plurality of linear shrinking and scaling operations on a plurality of portions of said difference signal contained in respective coarse grid segments using the fractal information, thereby defining a modified difference signal; and

adding the fine relatively low frequency Signal component with the modified difference signal, thereby defining a decoded digital signal which substantially reconstructs the original signal.

74. A method according to claim 73 whereby the original signal comprises a video signal including a plurality of frames, and wherein the step of extracting comprises, for each current frame of the video signal, the steps of:

defining first relatively high frequency and relatively low frequency components of the current frame on a first scale; and

defining second relatively high frequency and relatively low frequency components of a frame following the current frame on a second scale;

and wherein the step of extracting comprises, for each frame of the video signal, the step of;

defining a coarse relatively low frequency signal component and a fine relatively low frequency signal component from a frame preceding the current frame and from the current frame, respectively.

75. A method according to claim 73 wherein the original signal is an audio signal sampled digitally, and the sampled signal is segmented into windows which are adaptively clipped as the signal is generated, and the steps of defining, fractal-processing, generating, archiving, retrieving, extracting, computing, performing and adding are carried out separately for each clipped window of the sampled signal.

76. A method according to claim 73 wherein the original signal comprises a greyscale image.

77. A method according to claim 73 wherein the original signal comprises a color image defining a plurality of color component images.

78. A method according to claim 77 wherein the steps of defining, fractal-processing, generating, archiving, retrieving, extracting, computing, performing and adding are performed on each of the plurality of color component images.

79. A method according to claim 73 wherein the original signal comprises a color image defined by a color palette.

80. A method according to claim 77 and also comprising a palette selection step in which the plurality of color component images are compressed into a color palette comprising a multitude of color palette values and wherein the original digital signal processed in said steps of defining, fractal-processing and generating comprises the color palette values, and wherein the decoded signal is further processed by a table look-up through the color palette.

81. A method according to claim 73 wherein said step of defining comprises the step of:

defining a relatively high frequency component on one of the two scales as the difference between the original signal and the relatively low frequency component on said scale.

82. A method according to claim 73 wherein said step of defining comprises the step of:

segmenting the original digital signal by defining coarse and fine grids corresponding to first and second ones of the two scales, respectively.

83. A method according to claim 82 wherein said step of defining comprises the following steps:

computing an average value for the original digital signal in each segment from among two pluralities of segments defined by the coarse and fine grids respectively; and

for each plurality of segments, passing functions through the average values, thereby defining the relatively low frequency components for each of the two scales.

84. A method according to claim 82 wherein said step of defining comprises the step of:

low-pass filtering the original digital signal with first and second cut-off frequencies determined respectively by the coarse and fine grids, thereby defining the smooth components.

85. A method according to claim 84 wherein said step of low-pass filtering comprises the steps of:

computing a Discrete Fourier Transform of the original digital signal;

truncating the Discrete Fourier Transform at the first and second cut-off frequencies, thereby defining truncated signals; and

performing an inverse Discrete Fourier Transform on the truncated signals.

86. A method according to claim 84 wherein said step of low-pass filtering comprises the steps of:

computing a Discrete Cosine Transform of the original digital signal;

truncating the Discrete Cosine Transform at the first and second cut-off frequencies, thereby defining truncated signals; and

performing an inverse Discrete Cosine Transform on the truncated signals.

87. A method according to claim 73 wherein the step of fractal-processing comprises the steps of:

shrinking a portion of the rough component of the original digital signal contained in each coarse grid segment so as to fit the size of a fine grid segment;

for each fine grid segment, performing the step of;

searching among the shrunk rough component portions for a shrunk rough component portion which matches well with a portion of the rough component contained in the fine grid segment.

88. A method according to claim 87 and also comprising the step of:

storing a result of the searching step comprising a shrunk rough component portion index and a matching operation.

89. A method according to claim 87 wherein said shrinking step comprises, for each fine grid pixel, the step of:

averaging pixel values of the rough component defined in the coarse scale, over a region corresponding to the fine grid pixel position.

90. A method according to claim 88 wherein said matching operation comprises a scale factor by which the shrunk rough portion is multiplied, and wherein said optimal matching is based on a sum of squares error criterion.

91. A method according to claim 73 and also comprising the steps of:

generating an encoded signal by packing a precursor encoded signal prior to archiving, the step of packing comprising the steps of;

quantizing the encoded digital signal, thereby defining a quantized encoded digital signal;

storing the quantized encoded digital signal in byte form, thereby defining a stored quantized encoded digital signal; and

compressing the stored quantized encoded digital signal; and

unpacking the packed encoded signal after retrieving, the step of unpacking comprising the steps of;

decompressing the packed encoded digital signal into a plurality of bytes;

reconstructing the quantized encoded digital signal from the plurality of bytes; and

performing inverse quantization on the quantized encoded digital signal, thereby generating the retrieved encoded digital signal.

92. A method according to claim 91 wherein the step of compressing comprises the step of:

operating at least one of the following compression algorithmsaon the stored quantized encoded digital signal;

Lempel-Ziv compression algorithm; and

a Huffman compression algorithm.

93. A method according to claim 91 wherein the step of decompressing comprises the step of:

operating at least one of the following decompression algorithms on the stored quantized encoded digital signal;

a Lempel-Ziv decompression algorithm; and

a Huffman decompression algorithm.

94. A method according to claim 73 and also comprising the steps of:

generating the original digital signal by transforming a precursor digital signal to a frequency domain; and

transforming the decoded signal out of the frequency domain.

95. A method according to claim 94 wherein the step of generating an original digital signal comprises the step of:

performing a Discrete Fourier Transform on the precursor digital signal.

96. A method according to claim 94 wherein the step of generating an original digital signal comprises the step of:

performing a Discrete Cosine Transform on the precursor digital signal.

97. A method according to claim 94 wherein the step of transforming out of a frequency domain comprises the step of:

performing an inverse Discrete Fourier Transform on the decoded signal.

98. A method according to claim 94 wherein the step of transforming out of a frequency domain comprises the step of:

performing an inverse Discrete Cosine Transform on the decoded signal.

99. A method according to claim 73 wherein the step of performing comprises, for each fine grid segment, the following steps:

deriving an index and optimal matching operation from the fractal information;

shrinking the portion of the difference signal contained in the coarse grid segment corresponding to the index so as to fit the size of a fine grid segment; and

applying the optimal matching operation to the shrunk portion of the difference signal, thereby to define the portion of the modified difference signal for the fine grid segment.

100. A method according to claim 99 wherein said shrinking comprises, for each fine grid pixel, the step of:

averaging the difference signal pixel values over a neighborhood region of the fine grid pixel position.

101. A method according to claim 99 wherein said matching operation comprises the step of:

multiplying the shrunk rough portion by a scale factor.

102. A method according to claim 1 wherein the relatively low frequency components comprise first and second decoded JPEG compressions based on image box size dimensions on respective ones of the two scales and wherein the representation of at least one of the relatively low frequency components comprises a JPEG representation.

104. A method according to claim 1 wherein the relatively low frequency components comprise first and second decoded wavelet compressions based on grid dimensions on respective ones of the two scales, and wherein the representation of at least one of the relatively low frequency components comprises a wavelet representation based on a Discrete Wavelet Transform.

106. A method according to claim 8 wherein the two relatively low frequency components of the plurality of frames comprise decoded MPEG compressions based on image box size dimensions on each of the two scales, and wherein the representation of each of the relatively low frequency Components comprises an MPEG representation.

108. A method according to claim 8 wherein the two relatively low frequency components of the plurality of frames comprise decoded CCITT compressions based on the H.261 (p*64) standard and based on image box size dimensions on each of the two scales, and wherein the representation of each of the relatively low frequency components comprises an H.261 representation.

110. A method according to claim 1 wherein the relatively low frequency components of the original digital signal are not orthogonal projections thereof.

24. A method for decoding a received digital signal representing an encoded image comprised of segments, the method comprising the steps of:

extracting for each segment a coarse relatively low frequency signal component, a fine relatively low frequency signal component and fractal information from the received encoded digital signal;

computing for each segment a difference between a reference digital signal and the coarse relatively low frequency signal component, thereby defining a difference signal;

performing a plurality of linear shrinking and scaling operations on a plurality of portions of said difference signal contained in respective coarse grid segments using the fractal information, thereby defining a modified difference signal; and

adding for each segment the fine relatively low frequency signal component with the modified difference signal, thereby defining a decoded digital signal which substantially reconstructs each segment of the original signal.

25. A method according to claim 24 wherein the received signal comprises an encoded video signal including a plurality of frames and wherein the step of extracting comprises, for each frame of the video signal, the step of:

defining said coarse relatively low frequency signal component and said fine relatively low frequency signal component from frame preceding the current frame and from the current frame, respectively.

26. A method according to claim 24 wherein a plurality of signals are received and decoded, each received signal comprising a window of an encoded audio signal sampled digitally which is segmented into windows as it is generated.

27. A method according to claim 24 wherein the received signal comprises an encoded greyscale image.

28. A method according to claim 24 wherein a plurality of signals are received, each received signal comprising an encoded color component image from a color image.

29. A method according to claim 28 wherein said of extracting, computing, performing and adding are performed on each of the plurality of encoded color component images.

30. A method according to claim 24 wherein the received signal comprises an encoded color image defined by a color palette, and wherein the decoded signal is further processed by a table look-up through the color palette.

31. A method according to claim 24 wherein said steps of extracting, computing, performing and adding are repeated at least once, wherein for each repetition the reference signal comprises the decoded signal from a previous repetition.

32. A method according to claim 24 wherein the steps of extracting, computing, performing and adding are repeated until the decoded signal remains substantially unchanged over repetition.

33. A method according to claim 24 wherein the steps of extracting, computing, performing and adding are repeated a predetermined number of times.

34. A method according to claim 24 wherein the received encoded digital signal comprises a received packed encoded digital signal, and the method also comprises, prior to the step of extracting, the steps of:

decompressing the packed encoded digital signal into a plurality of bytes;

reconstructing a quantized encoded digital signal from the plurality of bytes; and

performing inverse quantization on the quantized encoded digital signal, thereby to generate the encoded digital signal.

35. A method according to claim 34 wherein the step of decompressing comprises the step of operating at least one of the following decompression algorithms on the packed encoded digital signal;

a Lempel-Ziv decompression algorithm; and

Huffman decompression algorithm.

36. A method according to claim 24 wherein the step of performing comprises, for each fine grid segment, the following steps:

deriving an index and a matching operation from the fractal information;

shrinking the portion of the difference signal contained in a coarse grid segment corresponding to the index so as to fit the size of a fine grid segment; and

applying the matching operation to the shrunk portion of the difference signal, thereby to define the modified difference signal within the fine grid segment.

37. A method according to claim 36 wherein said shrinking step comprises, for each fine grid pixel, the step of:

averaging pixel values of the difference signal over a region corresponding to the fine grid pixel position.

38. A method according to claim 36 wherein said matching operation comprises a multiplication of the shrunk rough portion by a scale factor.

39. A method according to claim 24 and also comprising the step of:

transforming the decoded signal out of a frequency domain.

40. A method according to claim 39 wherein the step of transforming out of a frequency domain comprises the step of:

performing an inverse Discrete Fourier Transform on the decoded signal.

41. A method according to claim 39 wherein the step of transforming out of a frequency domain comprises the step of:

performing an inverse Discrete Cosine Transform on the decoded signal.

103. A method according to claim 24 wherein the step of extracting comprises the step of decompressing a JPEG encoded file.

105. A method according to claim 24 wherein the coarse relatively low frequency signal component and the fine relatively low frequency signal component are each extracted by performing the step of:

expanding a wavelet representation using an inverse Discrete Wavelet Transform.

107. A method according to claim 25 wherein the step of defining the coarse relatively low frequency signal component and the fine relatively low frequency signal component comprises the step of:

decompressing an MPEG encoded file.

109. A method according to claim 25 wherein the step of defining the coarse relatively low frequency signal component and the fine relatively low frequency signal component comprises the step of:

decompressing an H.261 encoded file.

111. Apparatus for decoding a received digital signal representing an encoded image comprised of segments, the apparatus comprising:

a difference computation unit operative in each segment to compute a difference between a reference digital signal and a coarse relatively low frequency signal component extracted from the received digital signal, thereby defining a difference signal;

a linear shrink and scale processor operative to perform a plurality of linear shrink and scale operations on a plurality of portions of said difference signal respectively contained in a plurality of coarse grid segments using fractal information extracted from the received digital signal, thereby defining a modified difference signal; and

a signal addition unit operative in each segment to add a fine relatively low frequency signal component extracted from the received digital signal with the modified difference signal, thereby defining a decoded digital signal which substantially reconstructs each segment of the original signal.

112. An image compression method comprising:

providing a digital signal representing an image comprised of segments;

for each segment, separating the digital signal into relatively high frequency and relatively low frequency components;

applying fractal compression processing only to the relatively high frequency component;

applying non-fractal compression processing to the relatively low frequency component; and

utilizing the relatively high frequency component following fractal processing thereof and the relatively low frequency component following non-fractal processing thereof to produce a compressed image representation for each segment.

113. Image compression apparatus operative on a digital signal representing an image comprised of segment, the apparatus comprising:

a frequency separator for separating for each segment the digital signal into relatively high frequency and relatively low frequency components;

a fractal processor operating only on the relatively high frequency component;

a non-fractal processor operating on the relatively low frequency component; and

a compressed signal generator utilizing the relatively high frequency component following fractal processing thereof and the relatively low frequency component following non-fractal processing thereof to produce a compressed image representation for each segment.

114. An image retrieval method comprising:

retrieving from storage or a transmission link a digital signal representing an encoded image comprised of segments and having at each segment an encoded relatively high frequency signal component and an encoded relatively low frequency signal component;

applying fractal decompression processing to the encoded relatively high frequency signal component, thereby producing for each segment a decompressed relatively high frequency signal component;

applying non-fractal decompression processing to the encoded relatively low frequency signal component, thereby producing for each segment a decompressed relatively low frequency signal component;

combining for each segment said decompressed relatively high frequency signal component with said decompressed relatively low frequency signal component, thereby producing each segment of a reconstructed image signal; and

employing said reconstructed image signal to produce a visible image.

115. An image retrieval system comprising:

a receiver, retrieving from storage or a transmission link a digital signal representing an encoded image comprised of segments and having at each segment an encoded relatively high frequency signal component and an encoded relatively low frequency signal component;

a fractal decoder, applying fractal decompression processing to the encoded relatively high frequency signal component, thereby producing for each segment a decompressed relatively high frequency signal component;

a non-fractal decoder, applying non-fractal decompression processing to the encoded relatively low frequency signal component, thereby producing for each segment a decompressed relatively low frequency signal component;

a signal combiner, combining for each segment said decompressed relatively high frequency signal component with said decompressed relatively low frequency signal component, thereby producing each segment of a reconstructed image signal; and

a visible image generator, employing said reconstructed image signal to produce a visible image.