Audio codec using adaptive sparse vector quantization with subband vector classification

• US 6,006,179 A
• Filed: 10/28/1997
• Issued: 12/21/1999
• Est. Priority Date: 10/28/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: America Online Inc. (Warner Bros. Discovery, Inc.)
• Inventors: Mantegna, John, Wu, Shuwu
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): Smits, Talivaldis Ivars
• Application Number:
  US08/958,567
• Time in Patent Office: 784 Days
• Field of Search: 704/205, 704/222, 704/229
• US Class Current: 704/222
• CPC Class Codes: G10L 19/26 Pre-filtering or post-filtering
• CPC Class Codes: G10L 25/18 the extracted parameters being spectral information of each sub-band

Abstract

An audio coder/decoder ("codec") that is suitable for real-time applications due to reduced computational complexity, and a novel adaptive sparse vector quantization (ASVQ) scheme and algorithms for general purpose data quantization. The codec provides low bit-rate compression for music and speech, while being applicable to higher bit-rate audio compression. The codec includes an in-path implementation of psychoacoustic spectral masking, and frequency domain quantization using the novel ASVQ scheme and algorithms specific to audio compression. More particularly, the inventive audio codec employs frequency domain quantization with critically sampled subband filter banks to maintain time domain continuity across frame boundaries. The input audio signal is transformed into the frequency domain in which in-path spectral masking can be directly applied. This in-path spectral masking usually results in sparse vectors. The ASVQ scheme is a vector quantization algorithm that is particularly effective for quantizing sparse signal vectors. In the preferred embodiment, ASVQ adaptively classifies signal vectors into six different types of sparse vector quantization, and performs quantization accordingly. The ASVQ technique applies to general purpose data quantization as well as to quantization in the context of audio compression. The invention also includes a "soft clipping" algorithm in the decoder as a post-processing stage. The soft clipping algorithm preserves the waveform shapes of the reconstructed time domain audio signal in a frame- or block-oriented stateless manner while maintaining continuity across frame or block boundaries. The invention includes related methods, apparatus, and computer programs.

Claims

1. A method for compressing a digitized time-domain audio input signal, including the steps of:

(a) filtering the input signal into a plurality of subbands sufficient to provide a frequency domain representation of the input signal;

(b) spectrally masking the plurality of subbands using an in-path psychoacoustic model to generate masked subbands;

(c) classifying the masked subbands into one of a plurality of quantization vector types;

(d) computing vector quantization indices for each quantization vector type;

(e) formatting the vector quantization indices for each quantization vector type as an output bit-stream.

2. The method of claim 1, wherein at least one quantization vector type is a sparse vector quantization type.

3. The method of claim 1, further including decompressing the output bit-stream by the steps of:

(a) decoding the output bit stream into vector quantization indices;

(b) reconstructing the masked subbands from the vector quantization indices;

(c) synthesizing a digitized time-domain audio output signal from the reconstructed masked subbands.

4. The method of claim 3, further including the step of soft clipping the output signal to be within a specified dynamic range.

5. The method of claim 4, wherein the output signal is formatted in frames, and the step of soft clipping includes the steps of:

(a) detecting if any part of the output signal within a frame is saturated;

(b) if saturation is detected, then dividing the output signal within the frame into regions of saturation;

(c) scaling each region of saturation while maintaining continuity across frame boundaries to produce a clipped output signal.

6. The method of claim 1, wherein the number of subbands is greater than or equal to 64.

7. A computer program, residing on a computer-readable medium, for compressing a digitized time-domain audio input signal, including instructions for causing a computer to:

(a) filter the input signal into a plurality of subbands sufficient to provide a frequency domain representation of the input signal;

(b) spectrally mask the plurality of subbands using an in-path psychoacoustic model to generate masked subbands;

(c) classify the masked subbands into one of a plurality of quantization vector types;

(d) compute vector quantization indices for each quantization vector type;

(e) format the vector quantization indices for each quantization vector type as an output bit-stream.

8. The computer program of claim 7, wherein at least one quantization vector type is a sparse vector quantization type.

9. The computer program of claim 7, further including instructions for decompressing the output bit-stream by causing the computer to:

(a) decode the output bit stream into vector quantization indices;

(b) reconstruct the masked subbands from the vector quantization indices;

(c) synthesize a digitized time-domain audio output signal from the reconstructed masked subbands.

10. The computer program of claim 9, further including instructions for causing the computer to soft clip the output signal to be within a specified dynamic range.

11. The computer program of claim 10, wherein the instructions for causing the computer to soft clip the output signal include instructions for causing the computer to:

(a) detect if any part of the output signal within a frame is saturated;

(b) if saturation is detected, then divide the output signal within the frame into regions of saturation;

(c) scale each region of saturation while maintaining continuity across frame boundaries to produce a clipped output signal.

12. The computer program of claim 7, wherein the number of subbands is greater than or equal to 64.

13. An apparatus for compressing a digitized time-domain audio input signal, including:

(a) means for filtering the input signal into a plurality of subbands sufficient to provide a frequency domain representation of the input signal;

(b) means for spectrally masking the plurality of subbands using an in-path psychoacoustic model to generate masked subbands;

(c) means for classifying the masked subbands into one of a plurality of quantization vector types;

(d) means for computing vector quantization indices for each quantization vector type;

(e) means for formatting the vector quantization indices for each quantization vector type as an output bit-stream.

14. The apparatus of claim 13, wherein at least one quantization vector type is a sparse vector quantization type.

15. The apparatus of claim 13, further including means for decompressing the output bitstream by:

(a) decoding the output bit stream into vector quantization indices;

(b) reconstructing the masked subbands from the vector quantization indices;

(c) synthesizing a digitized time-domain audio output signal from the reconstructed masked subbands.

16. The apparatus of claim 15, further including means for soft clipping the output signal to be within a specified dynamic range.

17. The apparatus of claim 16, wherein the output signal is formatted in frames, and further including soft clipping means for:

(a) detecting if any part of the output signal within a frame is saturated;

(b) if saturation is detected, then dividing the output signal within the frame into regions of saturation;

(c) scaling each region of saturation while maintaining continuity across frame boundaries to produce a clipped output signal.

18. The apparatus of claim 13, wherein the number of subbands is greater than or equal to 64.

19. A method for decompressing a bitstream including vector quantization indices for a plurality of vector types, the vector quantization indices representing a digitized time-domain audio input signal compressed using adaptive sparse vector quantization applied to masked subbands generated from the digitized time-domain audio input signal, including the steps of:

(a) decoding the output bit stream into vector quantization indices;

(b) reconstructing masked subbands from the vector quantization indices;

(c) synthesizing the digitized time-domain audio output signal from the reconstructed masked subbands.

20. The method of claim 19, wherein the step of reconstructing masked subbands includes the step of reconstructing sparse vectors from at least some of the vector quantization indices.

21. A computer program, residing on a computer-readable medium, for decompressing a bitstream including vector quantization indices for a plurality of vector types, the vector quantization indices representing a digitized time-domain audio input signal compressed using adaptive sparse vector quantization applied to masked subbands generated from the digitized time-domain audio input signal, including instructions for causing a computer to:

(a) decode the output bit stream into vector quantization indices;

(b) reconstruct masked subbands from the vector quantization indices;

(c) synthesize the digitized time-domain audio output signal from the reconstructed masked subbands.

22. The computer program of claim 21, wherein the instructions for causing a computer to reconstruct masked subbands further include instructions for causing the computer to reconstruct sparse vectors from at least some of the vector quantization indices.

23. An apparatus for decompressing a bitstream including vector quantization indices for a plurality of vector types, the vector quantization indices representing a digitized time-domain audio input signal compressed using adaptive sparse vector quantization applied to masked subbands generated from the digitized time-domain audio input signal, including:

(a) means for decoding the output bit stream into vector quantization indices;

(b) means for reconstructing masked subbands from the vector quantization indices;

(c) means for synthesizing the digitized time-domain audio output signal from the reconstructed masked subbands.

24. The apparatus of claim 23, wherein the means for reconstructing masked subbands includes means for reconstructing sparse vectors from at least some of the vector quantization indices.

25. A method for compressing a digitized time-domain input signal, including the steps of:

(a) filtering the input signal into a plurality of subbands sufficient to provide a frequency domain representation of the input signal;

(b) classifying the subbands into one of a plurality of quantization vector types, at least one of such quantization vector types being a sparse vector type;

(c) computing vector quantization indices for each quantization vector type;

(d) formatting the vector quantization indices for each vector type as an output bitstream.

27. The method of claims 25 or 26, wherein the step of computing vector quantization indices includes computing vector quantization indices for a quantization vector type based on the degree of sparseness of such quantization vector type.

28. The method of claims 25 or 26, wherein the input signal is an audio signal.

29. The method of claim 28, further including the step of spectrally masking the subbands using an in-path psychoacoustic model to generate masked subbands before computing the vector quantization indices.

26. A method for transforming and compressing signals representing a digitized time-domain input signal, the input signal being filtered into a plurality of subbands sufficient to provide a frequency domain representation of the input signal, including the steps of:

(a) classifying the subbands into one of a plurality of quantization vector types, at least one of such quantization vector types being a sparse vector type;

(b) computing vector quantization indices for each quantization vector type;

(c) outputting vector quantization indices for each vector type as a bit-stream representing a transformed and compressed version of the digitized time-domain input signal.

30. A method for decompressing a bitstream including vector quantization indices for a plurality of vector types, the vector quantization indices representing a digitized time-domain input signal compressed using adaptive sparse vector quantization applied to subbands generated from the digitized time-domain input signal, including the steps of:

(a) decoding the output bit stream into vector quantization indices;

(b) reconstructing subbands from the vector quantization indices;

(c) synthesizing the digitized time-domain output signal from the reconstructed subbands.

31. A computer program, residing on a computer-readable medium, for compressing a digitized time-domain input signal, including instructions for causing a computer to:

(a) filter the input signal into a plurality of subbands sufficient to provide a frequency domain representation of the input signal;

(b) classify the subbands into one of a plurality of quantization vector types, at least one of such quantization vector types being a sparse vector type;

(c) compute vector quantization indices for each quantization vector type;

(d) format the vector quantization indices for each vector type as an output bit-stream.

33. The computer program of claims 31 or 32, wherein the instructions for causing a computer to compute vector quantization indices includes instructions for causing the computer to compute vector quantization indices for a quantization vector type based on the degree of sparseness of such quantization vector type.

34. The computer program of claims 31 or 32, wherein the input signal is an audio signal.

35. The method of claim 34, further including instruction s for causing the computer to spectrally mask the subbands using an in-path psychoacoustic model to generate masked subbands before computing the vector quantization indices.

32. A computer program, residing on a computer-readable medium, for transforming and compressing signals representing a digitized time-domain input signal, the input signal being filtered into a plurality of subbands sufficient to provide a frequency domain representation of the input signal, including instructions for causing a computer to:

(a) classify the subbands into one of a plurality of quantization vector types, at least one of such quantization vector types being a sparse vector type;

(b) compute vector quantization indices for each quantization vector type;

(c) output vector quantization indices for each vector type as a bit-stream representing a transformed and compressed version of the digitized time-domain input signal.

36. A computer program, residing on a computer-readable medium, for decompressing a bitstream including vector quantization indices for a plurality of vector types, the vector quantization indices representing a digitized time-domain input signal compressed using adaptive sparse vector quantization applied to subbands generated from the digitized time-domain input signal, including instructions for causing a computer to:

(a) decode the output bit stream into vector quantization indices;

(b) reconstruct subbands from the vector quantization indices;

(c) synthesize the digitized time-domain output signal from the reconstructed subbands.

37. An apparatus for compressing a digitized time-domain input signal, including:

(a) means for filtering the input signal into a plurality of subbands sufficient to provide a frequency domain representation of the input signal;

(b) means for classifying the subbands into one of a plurality of quantization vector types, at least one of such quantization vector types being a sparse vector type;

(c) means for computing vector quantization indices for each quantization vector type;

(d) means for formatting the vector quantization indices for each vector type as an output bit-stream.

39. The apparatus of claims 37 or 38, wherein the means for computing vector quantization indices includes means for computing vector quantization indices for a quantization vector type based on the degree of sparseness of such quantization vector type.

40. The apparatus of claims 37 or 38, wherein the input signal is an audio signal.

41. The apparatus of claim 40, further including means for spectrally masking the subbands using an in-path psychoacoustic model to generate masked subbands before computing the vector quantization indices.

38. An apparatus for transforming and compressing signals representing a digitized time-domain input signal, the input signal being filtered into a plurality of subbands sufficient to provide a frequency domain representation of the input signal, including:

(a) means for classifying the subbands into one of a plurality of quantization vector types, at least one of such quantization vector types being a sparse vector type;

(b) means for computing vector quantization indices for each quantization vector type;

(c) means for outputting vector quantization indices for each vector type as a bit-stream representing a transformed and compressed version of the digitized time-domain input signal.

42. An apparatus for decompressing a bitstream including vector quantization indices for a plurality of vector types, the vector quantization indices representing a digitized time-domain input signal compressed using adaptive sparse vector quantization applied to subbands generated from the digitized time-domain input signal, including:

(a) means for decoding the output bit stream into vector quantization indices;

(b) means for reconstructing subbands from the vector quantization indices;

(c) means for synthesizing the digitized time-domain output signal from the reconstructed subbands.

43. A method for quantization of arbitrary data, input into a computer, by adaptive sparse vector quantization including the steps of:

(a) grouping consecutive points of the original data into vectors;

(b) adaptively classifying the vectors into one of a plurality of vector types, including at least one sparse vector type;

(c) collapsing each sparse vector into a corresponding compact form;

(d) computing a plurality of vector quantization indices for each compact vector; and

(e) formatting the vector quantization indices for each vector type as an output bit-stream.

44. The method of claim 43, wherein the step of adaptively classifying vectors includes the steps of:

(a) analyzing each vector;

(b) classifying each analyzed vector with all zero elements as a first vector type;

(c) classifying each analyzed vector with local clustering as a second vector type;

(d) classifying each analyzed vector with amplitude similarity in non-zero elements as a third vector type;

(e) classifying each analyzed vector with dense vectors as a fourth vector type;

(f) classifying each analyzed vector with vectors to which a pre-vector splitting scheme should be applied as a fifth vector type;

(g) classifying each analyzed vector with vectors to which a post-vector splitting scheme should be applied as a sixth vector type.

45. The method of claim 43, wherein the step of collapsing sparse vectors includes the steps of:

(a) determining locations of non-zero elements in each sparse vector;

(b) computing lengths of regions consisting of consecutive zero elements in each sparse vector;

(c) computing an index representation for the computed lengths of regions for each sparse vector;

(d) deriving a compact vector from each sparse vector by removing all zero elements.

46. The method of claim 45, wherein the step of computing an index representation includes the step of applying recursive enumeration to each vector containing non-negative integer components.

47. A computer program, residing on a computer-readable medium, for quantization of arbitrary data, input into a computer, by adaptive sparse vector quantization, including instructions for causing the computer to:

(a) group consecutive points of the original data into vectors;

(b) adaptively classify the vectors into one of a plurality of vector types, including at least one sparse vector type;

(c) collapse each sparse vector into a corresponding compact form;

(d) compute a plurality of vector quantization indices for each compact vector; and

(e) format the vector quantization indices for each vector type as an output bit-stream.

48. The computer program of claim 47, wherein the instructions for causing a computer to adaptively classify vectors includes instructions for causing a computer to:

(a) analyze each vector;

(b) classify each analyzed vector with all zero elements as a first vector type;

(c) classify each analyzed vector with local clustering as a second vector type;

(d) classify each analyzed vector with amplitude similarity in non-zero elements as a third vector type;

(e) classify each analyzed vector with dense vectors as a fourth vector type;

(f) classify each analyzed vector with vectors to which a pre-vector splitting scheme should be applied as a fifth vector type;

(g) classify each analyzed vector with vectors to which a post-vector splitting scheme should be applied as a sixth vector type.

49. The computer program of claim 47, wherein the instructions for causing a computer to collapse sparse vectors includes the steps of:

(a) determine locations of non-zero elements in each sparse vector;

(b) compute lengths of regions consisting of consecutive zero elements in each sparse vector;

(c) compute an index representation for the computed lengths of regions for each sparse vector;

(d) derive a compact vector from each sparse vector by removing all zero elements.

50. The computer program of claim 49, wherein the instructions for causing a computer to compute an index representation includes instructions for causing a computer to apply recursive enumeration to each vector containing non-negative integer components.

51. An apparatus for quantization of arbitrary data, input into a computer, by adaptive sparse vector quantization including:

(a) means for grouping consecutive points of the original data into vectors;

(b) means for adaptively classifying the vectors into one of a plurality of vector types, including at least one sparse vector type;

(c) means for collapsing each sparse vector into a corresponding compact form;

(d) means for computing a plurality of vector quantization indices for each compact vector; and

(e) means for formatting the vector quantization indices for each vector type as an output bit-stream.

52. The apparatus of claim 51, wherein the means for adaptively classifying vectors includes:

(a) means for analyzing each vector;

(b) means for classifying each analyzed vector with all zero elements as a first vector type;

(c) means for classifying each analyzed vector with local clustering as a second vector type;

(d) means for classifying each analyzed vector with amplitude similarity in non-zero elements as a third vector type;

(e) means for classifying each analyzed vector with dense vectors as a fourth vector type;

(f) means for classifying each analyzed vector with vectors to which a pre-vector splitting scheme should be applied as a fifth vector type;

(g) means for classifying each analyzed vector with vectors to which a post-vector splitting scheme should be applied as a sixth vector type.

53. The apparatus of claim 51, wherein the means for collapsing sparse vectors includes:

(a) means for determining locations of non-zero elements in each sparse vector;

(b) means for computing lengths of regions consisting of consecutive zero elements in each sparse vector;

(c) means for computing an index representation for the computed lengths of regions for each sparse vector;

(d) means for deriving a compact vector from each sparse vector by removing all zero elements.

54. The apparatus of claim 53, wherein the means for computing an index representation includes means for applying recursive enumeration to each vector containing non-negative integer components.

55. A method for de-quantization of compressed input bitstream data, input into a computer, by adaptive sparse vector de-quantization, including the steps of:

(a) decoding the input bitstream data into a plurality of vector quantization indices, at least one type of such vector quantization indices defining a sparse vector type;

(b) reconstructing compact vectors from the vector quantization indices;

(c) expanding each compact vector into sparse vector form for each sparse vector type;

(d) assembling sparse vectors into transcoded data.

56. The method of claim 55, wherein the step of expanding compact vectors includes the steps of:

(1) computing lengths of regions consisting of consecutive zero elements from the vector quantization indices;

(2) determining locations of non-zero elements from the computed lengths of regions;

(3) creating a corresponding sparse vector consisting of all zero elements; and

(4) reconstructing each sparse vector by inserting compact vector components in the determined locations.

57. The method of claim 56, wherein the step of computing lengths of regions includes the step of applying recursive reconstruction of vectors containing non-negative integer components from the vector quantization indices.

58. A computer program, residing on a computer-readable medium, for de-quantization of compressed input bitstream data, input into a computer, by adaptive sparse vector de-quantization, including instructions for causing the computer to:

(a) decode the input bitstream data into a plurality of vector quantization indices, at least one type of such vector quantization indices defining a sparse vector type;

(b) reconstruct compact vectors from the vector quantization indices;

(c) expand each compact vector into sparse vector form for each sparse vector type;

(d) assemble sparse vectors into transcoded data.

59. The computer program of claim 58, wherein the instructions for causing a computer to expand compact vectors includes instructions for causing the computer to:

(1) compute lengths of regions consisting of consecutive zero elements from the vector quantization indices;

(2) determine locations of non-zero elements from the computed lengths of regions;

(3) create a corresponding sparse vector consisting of all zero elements; and

(4) reconstruct each sparse vector by inserting compact vector components in the determined locations.

60. The computer program of claim 59, wherein the instructions for causing a computer to compute lengths of regions includes instructions for causing the computer to apply recursive reconstruction of vectors containing non-negative integer components from the vector quantization indices.

61. An apparatus for de-quantization of compressed input bitstream data, input into a computer, by adaptive sparse vector de-quantization, including:

(a) means for decoding the input bitstream data into a plurality of vector quantization indices, at least one type of such vector quantization indices defining a sparse vector type;

(b) means for reconstructing compact vectors from the vector quantization indices;

(c) means for expanding each compact vector into sparse vector form for each sparse vector type;

(d) means for assembling sparse vectors into transcoded data.

62. The apparatus of claim 61, wherein the means for expanding compact vectors includes:

(1) means for computing lengths of regions consisting of consecutive zero elements from the vector quantization indices;

(2) means for determining locations of non-zero elements from the computed lengths of regions;

(3) means for creating a corresponding sparse vector consisting of all zero elements; and

(4) means for reconstructing each sparse vector by inserting compact vector components in the determined locations.

63. The apparatus of claim 62, wherein the means for computing lengths of regions includes means for applying recursive reconstruction of vectors containing non-negative integer components from the vector quantization indices.