Source: http://www.google.com/patents/US7693709?dq=5,889,522
Timestamp: 2017-10-17 03:25:29
Document Index: 375540734

Matched Legal Cases: ['art 7', 'art 7', 'Application No. 06', 'art 1', 'art 2', 'art 2']

Patent US7693709 - Reordering coefficients for waveform coding or decoding - Google Patents
Techniques and tools for reordering of spectral coefficients in encoding and decoding are described herein. For certain types and patterns of content, coefficient reordering reduces redundancy that is due to periodic patterns in the spectral coefficients, making subsequent entropy encoding more efficient....http://www.google.com/patents/US7693709?utm_source=gb-gplus-sharePatent US7693709 - Reordering coefficients for waveform coding or decoding
Publication number US7693709 B2
Application number US 11/183,297
Also published as US20070016406
Publication number 11183297, 183297, US 7693709 B2, US 7693709B2, US-B2-7693709, US7693709 B2, US7693709B2
Inventors Naveen Thumpudi, Wei-ge Chen, Chao He
Patent Citations (162), Non-Patent Citations (38), Referenced by (23), Classifications (12), Legal Events (3)
Reordering coefficients for waveform coding or decoding
US 7693709 B2
Techniques and tools for reordering of spectral coefficients in encoding and decoding are described herein. For certain types and patterns of content, coefficient reordering reduces redundancy that is due to periodic patterns in the spectral coefficients, making subsequent entropy encoding more efficient. For example, an audio encoder receives spectral coefficients logically organized along one dimension such as frequency, reorders at least some of the spectral coefficients, and entropy encodes the spectral coefficients after the reordering. Or, an audio decoder receives entropy encoded information for such spectral coefficients, entropy decodes the information, and reverses reordering of at least some of the spectral coefficients.
1. A computer-implemented method of encoding media content using an encoder, the method comprising:
with the encoder, encoding media content, including:
receiving plural spectral coefficients logically organized along one dimension;
identifying a periodic pattern in the plural spectral coefficients by analyzing coefficient values of the plural spectral coefficients, including identifying a period length that depends at least in part on the coefficient values of the plural spectral coefficients;
reordering at least some of the plural spectral coefficients based at least in part upon the periodic pattern; and
entropy encoding the plural spectral coefficients after the reordering; and
outputting the encoded media content in a bit stream, including signaling reordering information that indicates the periodic pattern, wherein the reordering information describes the reordering to facilitate reversal of the reordering during decoding.
receiving one or more blocks of time domain audio samples; and
as part of the encoding the media content:
frequency transforming at least some of the one or more blocks of time domain audio samples to produce the plural spectral coefficients, wherein the one dimension is frequency across a spectral band;
performing a multi-channel transform on the plural spectral coefficients, thereby putting the plural spectral coefficients in coded channels; and
quantizing the plural spectral coefficients, wherein the reordering occurs before the quantizing or after the quantizing.
3. The method of claim 1 wherein the one dimension is frequency across a spectral band for the plural spectral coefficients within a block for a single sub-frame or other window, such that the reordering selectively reorders the at least some of the plural spectral coefficients in the spectral band within the block.
4. The method of claim 1 wherein the reordering is based at least in part upon at least one non-integer period length of the periodic pattern among the plural spectral coefficients.
5. The method of claim 1 wherein the periodic pattern describes plural periods among the plural spectral coefficients, the method further comprising adjusting a starting position and/or ending position of at least one of the plural periods.
6. The method of claim 1 wherein the periodic pattern describes plural periods among the plural spectral coefficients, the method further comprising determining a preroll for at least one of the plural periods, wherein the preroll indicates preroll coefficients which are reordered relative to other coefficients but are not reordered relative to each other.
7. The method of claim 1 wherein the signaled information comprises one or more period length values that parameterize the periodic pattern and one or more position adjustment values.
8. The method of claim 1 wherein the reordering information includes a preroll value that indicates a number of preroll coefficients in a period among the plural spectral coefficients, wherein the preroll coefficients are treated as a group during the reordering.
9. The method of claim 1 wherein the reordering information includes a first length value that indicates an integer part of the period length and a second length value that indicates a fractional part of the period length.
10. The method of claim 1 wherein the reordering information includes a first period identifier that indicates, among the plural spectral coefficients, a first period for which coefficients are reordered, and wherein the reordering information further includes a last period identifier that indicates, among the plural spectral coefficients, a last period for which coefficients are reordered.
11. A computer-implemented method of decoding media content using a decoder, the method comprising:
receiving encoded information in a bit stream, including:
receiving reordering information from the bit stream, wherein the reordering information indicates a periodic pattern among plural spectral coefficients; and
receiving entropy encoded information for the plural spectral coefficients, wherein the plural spectral coefficients are logically organized along one dimension, and wherein at least some of the plural spectral coefficients have been reordered along the one dimension; and
with the decoder, reconstructing media content using the encoded information, including:
entropy decoding the entropy encoded information; and
reversing reordering of the at least some of the plural spectral coefficients based at least in part on the periodic pattern indicated with the reordering information.
12. The method of claim 11 wherein the plural spectral coefficients are for multi-channel audio, and wherein the plural spectral coefficients are quantized and in multi-channel transform coded channels, the method further comprising during the reconstructing:
performing an inverse multi-channel transform on the plural spectral coefficients;
performing inverse quantization on the plural spectral coefficients; and
performing an inverse frequency transform to produce plural time domain audio samples.
13. The method of claim 11 wherein the one dimension is frequency across a spectral band for the plural spectral coefficients within a block for a single sub-frame or other window, such that the reversing selectively reorders the at least some of the plural spectral coefficients in the spectral band within the block.
14. The method of claim 11 wherein the reordering information further indicates a non-integer period length of the periodic pattern among the plural spectral coefficients.
15. The method of claim 11 wherein the reordering information further indicates an adjustment to starting position and/or ending position of at least one of plural periods in the plural spectral coefficients.
16. The method of claim 11 wherein the reordering information further indicates a preroll for at least one of plural periods in the plural spectral coefficients, wherein the preroll indicates preroll coefficients which are reordered relative to other coefficients but are not reordered relative to each other.
17. The method of claim 11 wherein the reordering information includes a preroll value that indicates a number of preroll coefficients in a period among the plural spectral coefficients, wherein the preroll coefficients are treated as a group during the reversing.
18. The method of claim 11 wherein the reordering information includes a first length value that indicates an integer part of a period length for the periodic pattern and a second length value that indicates a fractional part of the period length for the periodic pattern.
19. The method of claim 11 wherein the reordering information includes a first period identifier that indicates, among the plural spectral coefficients, a first period for which coefficients have reordering reversed, and wherein the reordering information further includes a last period identifier that indicates, among the plural spectral coefficients, a last period for which coefficients have reordering reversed.
one or more storage media storing computer-executable instructions for controlling the processor to provide:
means for parsing, from a bitstream, reordering information descriptive of selective reordering of plural spectral audio coefficients, wherein the reordering information indicates a periodic pattern among the plural spectral audio coefficients;
means for entropy decoding the plural spectral audio coefficients as selectively reordered; and
means for reversing the selective reordering in results of the entropy decoding based at least in part upon the periodic pattern indicated with the reordering information.
means for performing an inverse multi-channel transform;
means for performing an inverse frequency transform.
22. The system of claim 20 wherein the parsed information includes:
period length information that indicates a period length of the periodic pattern;
preroll information that indicates a number of preroll coefficients, wherein the preroll coefficients are treated as a group during the selective reordering;
first period identifier information that indicates, among the plural spectral audio coefficients, a first period for which coefficients have reordering reversed; and
last period identifier information that indicates, among the plural spectral audio coefficients, a last period for which coefficients have reordering reversed.
I. Representing Audio Information in a Computer
Sample Sampling Raw Bit
Depth Rate Rate
(bits/ (samples/ Channel (bits/
sample) second) Mode second)
Techniques and tools for reordering of spectral coefficients are described herein. In general, coefficient reordering improves the efficiency of subsequent entropy encoding for certain types and patterns of content. For example, for some audio signals, reordering of quantized spectral coefficients reduces redundancy that is due to periodic patterns in the time domain audio signal, making subsequent entropy coding more efficient.
According to a first set of techniques and tools, a tool such as an encoder receives multiple spectral coefficients logically organized along one dimension (e.g., frequency). The tool reorders at least some of the multiple spectral coefficients and entropy encodes the multiple spectral coefficients after the reordering. The tool can determine a periodic pattern among the multiple spectral coefficients, where the reordering is based at least in part on the periodic pattern.
According to a second set of techniques and tools, a tool such as a decoder receives entropy encoded information for multiple spectral coefficients. The multiple spectral coefficients are logically organized along one dimension (e.g., frequency), and at least some of the multiple spectral coefficients have been reordered along that dimension. The tool entropy decodes the entropy encoded information and reverses reordering of the at least some of the multiple spectral coefficients.
According to a third set of techniques and tools, a tool such as a decoder entropy decodes multiple spectral audio coefficients as selectively reordered and reverses selective reordering in results of the entropy decoding.
To start, the encoder computes (1310) a prediction factor for a segment of audio. In general, the encoder computes the prediction factor using any of several techniques. For example, for a first-order predictor, the encoder performs an exhaustive search of possible prediction factors to find the final prediction factor (e.g., the prediction factor that results in fewest entropy coded bits). Or, the encoder computes a correlation constant for the quantized spectral coefficients of the segment (namely, E{×[i−1]×[i]}/E{×[i]×[i]}) to derive the prediction factor. Or, for a higher order predictor, the encoder uses a linear prediction coefficient algorithm (e.g., involving computation of autocorrelation and autocovariance) and stability is not required. Or, if the order and precision of the filter are flexible, the encoder computes the predictor order (first, second, third, etc.) and prediction factor values and precision for the segment. Alternatively, the encoder uses some other mechanism to compute the prediction factor.
Prediction factor Binary representation
−1.00 1000
−0.75 1001
−0.50 1010
−0.25 1011
0.25 1100
0.50 1101
0.75 1110
1.00 1111
D. Example Techniques for Coefficient Prediction During Decoding
Returning to FIG. 18 a, the encoder determines (1860) whether or not coefficient reordering is used. If not, the encoder simply entropy encodes (1880) the quantized spectral coefficients of the segment using vector variable length coding, run-level coding, or some other entropy coding. On the other hand, if coefficient reordering is used, the encoder reorders (1870) at least some of the coefficients of the segment and entropy encodes (1880) the coefficients as (selectively) reordered using vector variable length coding, run-level coding, or some other entropy coding. For example, the encoder performs the reordering (1870) as follows, for reordering information computed as shown in FIG. 18 b and signaled as shown in FIG. 18 c.
In summary, the encoder reorders coefficients and outputs the coefficients to a new coefficient buffer (or directly to an entropy coder so that the reordering process does not use extra resources for buffering). The encoder browses a table (described above) that indicates the starting positions and/or ending positions of periods for which coefficients will be reordered. Generally, the encoder loops from the first such period to the last such period.
The decoder also determines (1960) whether or not coefficient reordering is used during decoding. If coefficient reordering is used during decoding, the decoder reorders (1970) at least some of the coefficients of the segment as entropy decoded. For example, the decoder performs the reordering (1970) as follows, for reordering information retrieved as shown in FIG. 19 b.
The decoder generates (1972) a period position table from reordering information for the segment (for example, period length, first reordered period, last reordered period) and applies (1974) period adjustments to the table. The table stores the starting positions and/or ending positions of periods for use in the reordering. Alternatively, the decoder skips the table generation process or uses some other table structure.
PS indicates the probability distributions for the states, with PS(j) being the probability that the state is S(j). PS(j),X indicates the probability distribution for the symbol values when in state S(j), with PS(j),X(i) being the probability that a symbol has value X(i) when in state S(j). Out of the M symbol values, L symbol values are designated as being more probable, and M-L symbol values are designated as being less probable. The set of the L more probable symbol values is set Q, and the set of the M-L less probable symbol values is set R.
PS(0) PS(1) PS(1)
X(0) X(1) X(2) X(3) X(4)
PS(0),X(i) 0.09 0.4 0.04 0.4 0.07
PS(1),X(i) 0.055 0.7 0.03 0.2 0.015
PS(2),X(i) 0.165 0.1 0.09 0.6 0.045
X(0) X(2) X(4)
PS(0),X(i),R 0.45 0.2 0.35
PS(1),X(i),R 0.55 0.3 0.15
PS(2),X(i),R 0.55 0.3 0.15
P S ( j ) , X ( i ) , R ′ = ∑ S ( j ) = S ( 0 ) S ( N - 1 ) P S ( j ) * P S ( j ) , X ( i ) , R . ( 1 )
P′S(j),X(i),R 0.5 0.25 0.25
Table 6. Approximate condition distribution for symbol values in set R.
P S ( j ) , X ( i ) ′ = { P S ( j ) , X ( i ) , R ′ * ∑ X ( i ) ∈ R P S ( j ) , X ( i ) if X ( i ) ∈ R P S ( j ) , X ( i ) if X ( i ) ∈ Q . ( 2 )
PS(0),X(i) 0.1 0.4 0.05 0.4 0.05
PS(1),X(i) 0.05 0.7 0.025 0.2 0.025
PS(2),X(i) 0.15 0.1 0.075 0.6 0.075
Huffman code Huffman code Huffman code
for S(0) for S(1) for S(2)
X(0) 11 0 11 0 10 0
X(1) 0 0 11
X(2) 11 10 11 10 10 10
X(3) 10 10 0
X(4) 11 11 11 11 10 11
for S(0) for S(0) for S(2)
X(0), X(2), X(4) 11 11 10
X(0) 0
X(2) 10
X(4) 11
X(1) X(3) X(0), X(2), X(4)
PS(0),X(i) 0.4 0.4 0.2
PS(1),X(i) 0.7 0.2 0.1
PS(2),X(i) 0.1 0.6 0.3
- ∑ k training_vector k * log 2 ( cluster k ) , ( 3 )
where k indicates points in the training vector and cluster. Less formally, the relative entropy indicates a bit rate penalty due to mismatch between the training vector and cluster. The tool classifies a training vector with the cluster against which the training vector has the lowest MSE, lowest relative entropy, etc.
If the desired number of clusters has not been reached, the tool splits (2560) some or all of the current clusters. For example, the tool uses principal component analysis or some other analysis to split a cluster into two clusters. Suppose the tool seeks G final clusters and currently has F current clusters, where F<G. If splitting each of the F current clusters would result in too many clusters, the tool can split each of the G-F top current clusters (e.g., “top” in terms of how many training vectors are classified to the current clusters) into two clusters. Or, the tool can simply split the top cluster in each iteration or use some other rule for splitting. The tool then classifies (2530) the training vectors between current clusters (as split (2560)) according to the cost metric.
n t + 1 , i = arg min k ( b t , k + r t , i + s t , i , k ) b t + 1 , i = min k ( b t , k + r t , i + s t , i , k ) . ( 4 )
US6038536 * Jan 30, 1998 Mar 14, 2000 Texas Instruments Incorporated Data compression using bit change statistics
US20020009145 * Dec 18, 2000 Jan 24, 2002 Equator Technologies, Inc. Circuit and method for decoding an encoded verssion of an image having a first resolution directly into a decoded version of the image having a second resolution
GB2388502A * Title not available
3 "ISO/IEC 13818-7, Information Technology-Generic Coding of Moving Pictures and Associated Audio Information-Part 7: Advanced Audio Coding (AAC)," 174 pp. (1997).
4 "ISO/IEC 13818-7, Information Technology—Generic Coding of Moving Pictures and Associated Audio Information—Part 7: Advanced Audio Coding (AAC)," 174 pp. (1997).
6 Bell et al., "Text Compression," Prentice Hall, pp. 105-107 (Feb. 1990).
8 Brandenburg, "ASPEC Coding", AES 10th International Conference, pp. 81-90 (1991).
9 Chung et al., "A Novel Memory-efficient Huffman Decoding Algorithm and its Implementation," Signal Processing 62, pp. 207-213 (1997).
10 Costa et al., "Efficient Run-Length Encoding of Binary Sources with Unknown Statistics", Technical Report No. MSR-TR-2003-95, pp. 1-10, Microsoft Research, Microsoft Corporation (Dec. 2003).
11 Cui et al., "A novel VLC based on second-run-level coding and dynamic truncation," Proc. SPIE, vol. 6077, pp. 607726-1 to 607726-9 (2006).
12 Davis, "The AC-3 Multichannel Coder," Dolby Laboratories Inc., Audio Engineering Study, Inc., 6 pp. (Oct. 1993).
13 De Agostino et al., "Parallel Algorithms for Optimal Compression using Dictionaries with the Prefix Property," in Proc. Data Compression Conference '92, IEEE Computer Society Press, pp. 52-62 (1992).
14 European Search Report (Supplemental), Application No. 06 787 173.1, 11 pages, Jul. 24, 2009.
15 Gailly, "comp.compression Frequently Asked Questions (part 1/3)," 64 pp., document marked Sep. 5, 1999 [Downloaded from the World Wide Web on Sep. 5, 2007].
16 Gersho et al., "Vector Quantization and Signal Compression," pp. 259-305 (1992).
17 Gibson et al., Digital Compression for Multimedia, "Chapter 2: Lossless Source Coding," Morgan Kaufmann Publishers, Inc., pp. 17-61 (1998).
18 Gibson et al., Digital Compression for Multimedia, "Chapter 7: Frequency Domain Coding," Morgan Kaufmann Publishers, Inc., pp. 227-262 (1998).
19 Gill et al., "Creating High-Quality Content with Microsoft Windows Media Encoder 7," 4 pp. (2000) [ Downloaded from the World Wide Web on May 1, 2002].
20 Hui et al., "Matsushita Algorithm for Coding of Moving Picture Information," ISO/IEC-JTC1/SC29/WG11, MPEG91/217, 76 pp. (Nov. 1991).
21 Ishii et al., "Parallel Variable Length Decoding with Inverse Quantization for Software MPEG-2 Decoders," IEEE Signal Processing Systems, pp. 500-509 (1997).
22 ISO/IEC 14496-2, "Coding of Audio-Visual Object-Part 2: Visual," Third Edition, pp. 1-727 (Jun. 2004).
23 ISO/IEC 14496-2, "Coding of Audio-Visual Object—Part 2: Visual," Third Edition, pp. 1-727 (Jun. 2004).
24 ITU-T Recommendation H.264, "Series H: Audiovisual and Multimedia Systems, Infrastructure of Audiovisual Services-Coding of Moving Video," International Telecommunication Union, pp. 1-262 (May 2003).
25 ITU-T Recommendation H.264, "Series H: Audiovisual and Multimedia Systems, Infrastructure of Audiovisual Services—Coding of Moving Video," International Telecommunication Union, pp. 1-262 (May 2003).
26 ITU-T Recommendation T.800, "Series T: Terminals for Telematic Services," International Telecommunication Union, pp. 1-194 (Aug. 2002).
27 Jeong et al., "Adaptive Huffman Coding of 2-D DCT Coefficients for Image Sequence Compression," Signal Processing: Image Communication, vol. 7, 11 pp. (1995).
28 Malvar, "Fast Progressive Image Coding without Wavelets", IEEE Data Compression Conference, Snowbird, Utah, 10 pp. (Mar. 2000).
29 Najafzadeh-Azghandi, "Perceptual Coding of Narrowband Audio Signals," Thesis, 139 pp. (Apr. 2000).
30 Nelson, "The Data Compression Book," M&T Books, pp. 123-165 (1992).
31 Reader, "History of MPEG Video Compression-Ver. 4.0," 99 pp., document marked Dec. 16, 2003.
32 Reader, "History of MPEG Video Compression—Ver. 4.0," 99 pp., document marked Dec. 16, 2003.
33 Shamoon et al., "A Rapidly Adaptive Lossless Compression Algorithm for High Fidelity Audio Coding," IEEE Data Compression Conf. 1994, pp. 430-439 (Mar. 1994).
34 Sullivan et al., "The H.264/AVC Advanced Video Coding Standard: Overview and Introduction to the Fidelity Range Extensions," 21 pp. (Aug. 2004).
35 Tu et al., "Context-Based Entropy Coding of Block Transform Coefficients for Image Compression," IEEE Transactions on Image Processing, vol. 11, No. 11, pp. 1271-1283 (Nov. 2002).
36 U.S. Appl. No. 60/341,674, filed Dec. 17, 2001, Lee et al.
37 U.S. Appl. No. 60/488,710, filed Jul. 18, 2003, Srinivasan et al.
38 Wien, "Variable Block-Size Transforms for Hybrid Video Coding," Dissertation, 182 pp. (Feb. 2004).
US8103516 * Nov 29, 2006 Jan 24, 2012 Panasonic Corporation Subband coding apparatus and method of coding subband
US8218882 * Mar 13, 2008 Jul 10, 2012 Ricoh Company, Ltd. Image coding method, image coding apparatus, image coding circuit, information recording medium, and computer program
US8788277 * Sep 13, 2010 Jul 22, 2014 The Trustees Of Columbia University In The City Of New York Apparatus and methods for processing a signal using a fixed-point operation
US9570085 * Apr 8, 2015 Feb 14, 2017 Fraunhofer-Gesellschaft Zur Foerderung Der Angewandten Forschung E.V. Apparatus and method for efficient synthesis of sinusoids and sweeps by employing spectral patterns
US9736609 Feb 6, 2014 Aug 15, 2017 Qualcomm Incorporated Determining renderers for spherical harmonic coefficients
US20080226187 * Mar 13, 2008 Sep 18, 2008 Yutaka Sato Image coding method, image coding apparatus, image coding circuit, information recording medium, and computer program
US20100228541 * Nov 29, 2006 Sep 9, 2010 Matsushita Electric Industrial Co., Ltd. Subband coding apparatus and method of coding subband
US20110116551 * Sep 13, 2010 May 19, 2011 The Trustees Of Columbia University In The City Of New York Apparatus and methods for processing compression encoded signals
US20150213808 * Apr 8, 2015 Jul 30, 2015 Fraunhofer-Gesellschaft Zur Foerderung Der Angewandten Forschung E.V. Apparatus and method for efficient synthesis of sinusoids and sweeps by employing spectral patterns
U.S. Classification 704/205, 704/500, 704/229
International Classification G10L19/00, G10L19/14, G10L19/02
Cooperative Classification G10L19/0212, G10L19/008, G10L19/022
European Classification G10L19/022, G10L19/008, G10L19/02T
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:THUMPUDI, NAVEEN;CHEN, WEI-GE;HE, CHAO;REEL/FRAME:016387/0877