Data compression method and apparatus

• US 6,091,773 A
• Filed: 11/12/1997
• Issued: 07/18/2000
• Est. Priority Date: 11/12/1997
• Status: Expired due to Term

• Current Assignee: Mark R. Sydorenko
• Original Assignee: Mark R. Sydorenko
• Inventors: Sydorenko, Mark R.
• Primary Examiner(s): BRITTON, HOWARD W
• Application Number:
  US08/968,644
• Time in Patent Office: 979 Days
• Field of Search: 348/398, 348/405, 375/240, 704/500, 704/202, 704/222
• US Class Current: 375/240.03
• CPC Class Codes: G06T 9/002 using neural networks
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence

Abstract

A method and apparatus for measuring the "perceptual distance" between an approximate, reconstructed representation of a sensory signal (such as an audio or video signal) and the original sensory signal is provided. The perceptual distance in this context is a direct quantitative measure of the likelihood that a human observer can distinguish the original audio or video signal from the reconstructed approximation to the original audio or video signal. The method described herein applies to noisy compression techniques; the method provides the ability to predict the likelihood that the reconstructed noisy representation of the original signal will be distinguishable by a human observer from the original input representation. The method can be used to allocate bits in audio and video compression algorithms such that the signal reconstructed from compressed representation is perceptually similar to the original input signal when judged by a human observer. The method is based on a theory of the neurophysiological limitations of human sensory perception. Specifically, a "neural encoding model" (NEM) summarizes the manner in which sensory signals are represented in the human brain. The NEM is analyzed in the context of detection theory which provides a mathematical framework for statistically quantifying the detectability of differences in the neural representation arising from differences in sensory input. This NEM approach has been validated by demonstrating its ability to predict a variety of published psychoacoustic data, including masking and many other phenomenon.

Claims

1. A method for calculating a perceptual distance between a data signal and a first representation of said data signal, comprising the steps of:

partitioning a time ordered representation of said data signal using a windowing processor;

decomposing said partitioned data into multiple channels using a filter bank, each channel representing partitioned data components of respective frequency bands;

quantizing said decomposed data in a quantization engine;

reconstructing said decomposed data from said quantized data using a decoder;

determining an energy difference between said quantized data and said reconstructed data in a difference energy processor; and

adjusting said quantization engine based upon a comparison between a predetermined threshold and said energy difference.

2. The method of claim 1 wherein said data signal is chosen from the group consisting of audio and video data signals.

3. A method for calculating a perceptual distance between a data signal and a first representation of said data signal, comprising the steps of:

partitioning a time ordered representation of said data signal using a windowing processor;

decomposing said partitioned data into vector coefficients of uniformly distributed frequency components using a discrete frequency transform;

quantizing said decomposed data in a quantization engine;

reconstructing said decomposed data from said quantized data using a decoder;

determining an energy difference between said quantized data and said reconstructed data in a difference energy processor; and

adjusting said quantization engine based upon a comparison between a predetermined threshold and said energy difference.

4. The method of claim 3 wherein said data signal is chosen from the group consisting of audio and video data signals.

5. A compression system providing an intermediate, compressed representation of an original signal from which a final reconstruction of said original signal is to be generated, comprising:

a lossy coder for receiving said original signal and for generating said compressed representation based upon perceptual distance data calculated between a neural encoding model representation of an intermediate reconstruction of said original signal and a neural encoding model representation of said original signal.

6. The compression system of claim 5, further comprising a complimentary lossy decoder for receiving said compressed representation and for generating said final reconstruction therefrom.

7. The compression system of claim 6, further comprising a signal medium intermediate said lossy coder and said complimentary lossy decoder.

8. The compression system of claim 7, wherein said signal medium is selected from the group consisting of a transmission medium and a storage medium.

9. The compression system of claim 7, further comprising:

a lossless coder in communication with said lossy coder for receiving said compressed representation from said lossy coder, and for generating an entropy-encoded, compressed representation in response thereto; and

a lossless decoder in communication with said complimentary lossy decoder for receiving said entropy-encoded, compressed representation, and for recovering said intermediate, compressed representation.

10. The compression system of claim 5, wherein said coder is implemented in elements selected from the group consisting of a digital signal processor, a programmable computer, and VLSI circuitry.

11. The compression system of claim 5, wherein said original signal is selected from the group consisting of an audio signal and a video signal.

12. The compression system of claim 5, wherein said original signal is one of plural signal channels collectively comprising a multi-channel original signal, and wherein said lossy coder is replicated for each channel of said multi-channel original signal.

13. The compression system of claim 5, wherein said lossy coder further comprises a representational transformer and requantizer for allocating a reduced number of bits required to represent said original signal according to said perceptual distance data.

14. The compression system of claim 13, further comprising a lossless coder in communication with said lossy coder for receiving said compressed representation from said lossy coder, and for generating an entropy-encoded, compressed representation in response thereto comprised of said reduced number of bits.

15. The compression system of claim 14, wherein said allocation minimizes the number of bits required to represent said original signal while not allowing said perceptual distance to exceed a pre-determined perceptual distance threshold.

16. The compression system of claim 14, wherein said allocation minimizes said perceptual distance using a pre-determined number of bits to represent said original signal.

17. The compression system of claim 13, wherein said lossy coder further comprises a reconstruction element in communication with said representational transformer and requantizer for substantially reversing said representational transformation and selective reduction in the number of bits required to represent said original signal, introduced by said representation transformer and requantizer, and for generating said intermediate reconstruction of said original signal.

18. The compression system of claim 17, wherein said lossy coder further comprises a first neural encoding modeler in communication with said reconstruction element for generating said neural encoding model representation of said intermediate reconstruction.

19. The compression system of claim 18, wherein said lossy coder further comprises a second neural encoding modeler for receiving said original signal and for generating said neural encoding model representation of said original signal.

20. The compression system of claim 19, wherein said lossy coder further comprises a perceptual distance calculation unit in communication with said first and second neural encoding modelers for receiving said neural encoding model representation of said intermediate reconstruction and said neural encoding model representation of said original signal, for generating said perceptual distance data, and for providing said perceptual distance data to said representational transformer and requantizer for use by said representational transformer and requantizer in said selective reduction in the number of bits required to represent said original signal.

21. The compression system of claim 5, wherein said lossy coder comprises a neural encoder for generating a neural encoding model representation of said original signal.

22. The compression system of claim 21, wherein said lossy coder further comprises a requantizer for selectively reducing a number of bits required to represent said neural encoding model representation of said original signal according to said perceptual distance data.

23. The compression system of claim 22, further comprising a lossless coder in communication with said requantizer for receiving said compressed representation from said requantizer, and for generating an entropy-encoded, compressed representation in response thereto comprised of said reduced number of bits.

24. The compression system of claim 23, wherein said requantization minimizes the number of bits required to represent said original signal while not allowing said perceptual distance to exceed a pre-determined perceptual distance threshold.

25. The compression system of claim 23, wherein said requantization minimizes said perceptual distance using a pre-determined number of bits to represent said original signal.

26. The compression system of claim 22, wherein said lossy coder further comprises a reconstruction element in communication with said requantizer for substantially reversing said selective reduction in the number of bits required to represent said neural encoding model representation of said original signal, introduced by said requantizer, and for generating a neural encoding model representation of said intermediate reconstruction of said original signal.

27. The compression system of claim 26, wherein said lossy coder further comprises a perceptual distance calculation unit in communication with said neural encoder and said reconstruction element for receiving said neural encoding model representation of said original signal and said neural encoding model representation of said intermediate reconstruction, for generating said perceptual distance data, and for providing said perceptual distance data to said requantizer for use by said requantizer in said selective reduction in the number of bits required to represent said original signal.

28. The compression system of claim 5, wherein said lossy coder further comprises a data windowing element for temporally windowing successive blocks of data from said original signal.

29. The compression system of claim 28, wherein said windowed successive blocks overlap in time.

30. The compression system of claim 28, wherein each of said windowed successive blocks has a duration substantially in the range of 100 to 400 milliseconds.

31. The compression system of claim 28, wherein said data windowing element is further for subdividing said windowed successive blocks into temporally overlapping subwindows each of duration less than each of said windowed successive blocks.

32. The compression system of claim 28, wherein said lossy coder further comprises a bandpass filter bank in communication with said data windowing element for decomposing said windowed successive blocks into multiple, consecutive frequency band channels.

33. The compression system of claim 32, wherein said filter bank comprises an element selected from the group consisting of a finite impulse response filter, an infinite impulse response filter, a polynomial filter, a discrete fourier transform element, a fast fourier transform element, a discrete cosine transform element, a quadrature mirror filter, and a discrete sine transform element.

34. The compression system of claim 32, wherein said filter bank comprises a sub-critical sampling element in conjunction with a frequency domain alias cancelling element.

35. The compression system of claim 32, wherein the bandwidth of each filter in said bandpass filter bank is substantially in the range of 100 to 400 Hertz.

36. The compression system of claim 32, wherein said lossy coder further comprises compressive nonlinearity processors in communication with said bandpass filter bank for introducing a compressive instantaneous non-linearity into the output of said consecutive frequency band channels.

37. The compression system of claim 32, wherein said lossy coder further comprises an envelope detector processor in communication with said bandpass filter bank for generating the envelope representations for the outputs of said consecutive frequency band channels, and for critically re-sampling said envelope representations to reduce the sample rate.

38. The compression system of claim 37, wherein said lossy coder further comprises compressive nonlinearity processors in communication with said envelope detector for introducing a compressive instantaneous non-linearity into the output of said envelope detector processor.

39. The compression system of claim 32, wherein said requantizer receives said consecutive frequency band channels and computes, for groups of one or more of said channels, a group scale factor or quantization level for each group required to approximately represent said consecutive frequency band channels.

40. The compression system of claim 27, wherein said perceptual distance calculation unit further comprises a difference energy processor for determining a value representative of the energy difference per frequency band between said neural encoding model representation of said original signal and said neural encoding model of said intermediate reconstruction as a measure of said perceptual distance data.

41. The compression system of claim 40, wherein said lossy coder further comprises a perceptual threshold comparator in communication with said perceptual distance calculation unit and said requantizer for comparing said perceptual distance data against a perceptual distance threshold for each frequency band.

42. The compression system of claim 40, wherein said perceptual distance calculation unit further comprises a band energy processor for determining the total energy per frequency band from said neural encoding model of said original signal.

43. The compression system of claim 42, wherein said perceptual distance calculation unit further comprises a perceptual distance processor for calculating a perceptual distance metric based upon said energy difference value per frequency band and said total energy per frequency band.

44. The compression system of claim 43, wherein said perceptual distance processor is further for determining an adjacent band noise energy contribution to said total energy per band in calculating said perceptual distance metric.

45. The compression system of claim 28, wherein said lossy coder further comprises a transform element for transforming said windowed successive blocks into plural bands of frequency domain coefficients.

46. The compression system of claim 45, wherein said transform element further comprises an element selected from the group consisting of a discrete frequency transform element, a fast fourier transform element, a discrete cosine transform element, and a discrete sine transform element.

47. The compression system of claim 45, wherein said transform element further comprises a sub-critical sampling element in conjunction with a time domain alias cancellation processor for performing said transformation.

48. The compression system of claim 45, wherein each of said plural bands of frequency domain coefficients encompasses substantially a 100 to 400 Hertz range.

49. The compression system of claim 45, wherein said lossy coder further comprises compressive nonlinearity processors in communication with said discrete frequency transform element for introducing a compressive instantaneous non-linearity into said plural bands of frequency domain coefficients.

50. The compression system of claim 45, wherein said requantizer receives said plural bands of frequency domain coefficients and computes, for groups of one or more of said bands, a group scale factor or quantization level for each group required to approximately represent said consecutive frequency bands.

51. The compression system of claim 28, wherein said lossy coder further comprises a two-dimensional filter for processing said windowed successive blocks as discrete time representations of a two-dimensional image raster.

52. The compression system of claim 51, wherein said two-dimensional filter is a Gabor filter.

53. The compression system of claim 51, wherein said lossy coder further comprises a compressive non-linearity processor for introducing a compressive instantaneous non-linearity into said windowed successive blocks prior to processing by said two-dimensional filter.

54. The compression system of claim 51, wherein said lossy coder further comprises a grid array filter for segregating said filtered two-dimensional image raster into plural tiles, collectively defining said filtered, two-dimensional image raster.

55. A data compression method for providing an intermediate, compressed representation of an original signal from which a final reconstruction of said original signal is to be generated, comprising:

receiving said original signal by a lossy coder;

generating a neural encoding model representation of an intermediate reconstruction of said original signal by said lossy coder;

generating a neural encoding model representation of said original signal by said lossy coder;

calculating, by said lossy coder, a perceptual distance between said neural encoding model representation of an intermediate reconstruction of said original signal and said neural encoding model representation of said original signal; and

requantizing, by said lossy coder, said original signal to form said intermediate, compressed representation of said original signal, based upon said perceptual distance.

56. The compression method of claim 55, further comprising:

substantially reversing said requantization of said original signal by a complimentary lossy decoder to generate said final reconstruction therefrom.

57. The compression method of claim 56, further comprising:

transmission of said intermediate, compressed representation, by said lossy coder, to a signal medium intermediate said lossy coder and said complimentary lossy decoder.

58. The compression method of claim 56, further comprising:

receiving, by a lossless coder, said intermediate, compressed representation from said lossy coder;

generating, by said lossless coder, an entropy-encoded, compressed representation of said intermediate, compressed representation;

receiving said entropy-encoded, compressed representation by a lossless decoder; and

recovering, by said lossless decoder, said intermediate, compressed representation.

59. The compression method of claim 55, further comprising:

representationally transforming and requantizing said original signal, by said lossy coder, to allocate a reduced number of bits required to represent said original signal according to said perceptual distance data.

60. The compression method of claim 59, further comprising generating, by a lossless coder, an entropy-encoded, compressed representation of said intermediate, compressed representation of said reduced number of bits.

61. The compression method of claim 60 wherein said requantizing minimizes the number of bits required to represent said original signal while not allowing said perceptual distance to exceed a pre-determined perceptual distance threshold.

62. The compression method of claim 60, wherein said requantizing minimizes said perceptual distance using a pre-determined number of bits to represent said original signal.

63. The compression method of claim 59, further comprising:

substantially reversing said representational transformation and selective reduction in the number of bits required to represent said original signal, by said lossy coder, for generating said intermediate reconstruction of said original signal.

64. The compression method of claim 55, further comprising:

requantizing said original signal, by said lossy coder, to selectively reduce a number of bits required to represent said neural encoding model representation of said original signal according to said perceptual distance data.

65. The compression method of claim 64, further comprising generating, by a lossless coder, an entropy-encoded, compressed representation of said intermediate, compressed representation of said reduced number of bits.

66. The compression method of claim 65, wherein said requantizing minimizes the number of bits required to represent said original signal while not allowing said perceptual distance to exceed a pre-determined perceptual distance threshold.

67. The compression method of claim 65, wherein said requantizing minimizes said perceptual distance using a pre-determined number of bits to represent said original signal.

68. The compression method of claim 64, further comprising:

substantially reversing said selective reduction in the number of bits required to represent said neural encoding model representation of said original signal, introduced by said requantizing, in generating said neural encoding model representation of said intermediate reconstruction of said original signal.

69. The compression method of claim 55, wherein said generating a neural encoding model representation of said original signal further comprises:

temporally windowing successive blocks of data from said original signal.

70. The compression method of claim 69, wherein said temporally windowing windows successive blocks that overlap in time.

71. The compression method of claim 69, wherein said temporally windowing windows successive blocks of a duration substantially in the range of 100 to 400 milliseconds.

72. The compression method of claim 69, wherein said generating a neural encoding model representation of said original signal further comprises:

decomposing said windowed successive blocks into multiple, consecutive frequency band channels using a bandpass filter bank.

73. The compression method of claim 72, wherein said each filter in said bandpass filter bank used in said decomposing has a bandwidth substantially in the range of 100 to 400 Hertz.

74. The compression method of claim 72, wherein said generating a neural encoding model representation of said original signal further comprises:

introducing a compressive instantaneous non-linearity into the output of said consecutive frequency band channels.

75. The compression method of claim 72, wherein said generating a neural encoding model representation of said original signal further comprises:

envelope detecting the outputs of said consecutive frequency band channels for generating envelope representations, and for critically re-sampling said envelope representations to reduce the sample rate.

76. The compression method of claim 75, wherein said generating a neural encoding model representation of said original signal further comprises:

introducing a compressive instantaneous non-linearity into the output of said envelope detector processor.

77. The compression method of claim 72, wherein said requantizing said original signal further comprises:

receiving said consecutive frequency band channels; and

computing, for groups of one or more of said channels, a group scale factor or quantization level for each group required to approximately represent said consecutive frequency band channels.

78. The compression method of claim 55, wherein said calculating a perceptual distance further comprises:

determining a value representative of the energy difference per frequency band between said neural encoding model representation of said original signal and said neural encoding model of said intermediate reconstruction as a measure of said perceptual distance data.

79. The compression method of claim 78, wherein said calculating a perceptual distance further comprises:

comparing said perceptual distance data against a perceptual distance threshold for each frequency band.

80. The compression method of claim 78, wherein said calculating a perceptual distance further comprises:

determining the total energy per frequency band from said neural encoding model of said original signal.

81. The compression method of claim 80, wherein said calculating a perceptual distance further comprises:

calculating a perceptual distance metric based upon said energy difference value per frequency band and said total energy per frequency band.

82. The compression system of claim 81, wherein said calculating a perceptual distance further comprises:

determining an adjacent band noise energy contribution to said total energy per band in calculating said perceptual distance metric.

83. The compression method of claim 55, wherein said generating a neural encoding model further comprises:

transforming said windowed successive blocks into plural bands of frequency domain coefficients.

84. The compression method of claim 83, wherein said transforming comprises:

time domain alias cancelling said windowed successive blocks into plural bands of frequency domain coefficients.

85. The compression method of claim 83, wherein said transforming further comprises:

transforming said windowed successive blocks into said plural bands of frequency domain coefficients, each encompassing substantially a 100 to 400 Hertz range.

86. The compression method of claim 83, wherein said generating a neural encoding model representation of said original signal further comprises:

for introducing a compressive instantaneous non-linearity into said plural bands of frequency domain coefficients.

87. The compression method of claim 83, wherein said requantizing said original signal further comprises:

receiving said plural bands of frequency domain coefficients; and

computing, for groups of one or more of said bands, a group scale factor or quantization level for each group required to approximately represent said consecutive frequency bands.

88. The compression method of claim 55, wherein said generating a neural encoding model further comprises:

processing said windowed successive blocks as discrete time representations of a two-dimensional image raster using a two-dimensional filter.

89. The compression method of claim 88, wherein said processing further comprises using a Gabor filter as said two-dimensional filter.

90. The compression system of claim 88, wherein said generating neural encoding model further comprises:

introducing a compressive instantaneous non-linearity into said windowed successive blocks prior to processing using said two-dimensional filter.

91. The compression system of claim 88, wherein said generating a neural encoding model further comprises:

segregating said filtered two-dimensional image raster into plural tiles, collectively defining said filtered, two-dimensional image raster, using a grid array filter.