Fixed, variable and adaptive bit rate data source encoding (compression) method

• US 7,236,640 B2
• Filed: 08/17/2001
• Issued: 06/26/2007
• Est. Priority Date: 08/18/2000
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Subramaniam, Anand D., Rao, Bhaskar D.
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): Hung; Yubin
• Application Number:
  US10/344,586
• Publication Number:
  US 20040049384A1
• Time in Patent Office: 2,139 Days
• Field of Search: 382/232, 382/239, 382/251, 382/253, 348/420.1, 348/422.1, 704/222
• US Class Current: 382/253
• CPC Class Codes: G10L 19/008 Multichannel audio signal coding or decoding using interchannel correlation to reduce redundancy, e.g. joint-stereo, intensity-coding or matrixing
• CPC Class Codes: G10L 19/038 Vector quantisation, e.g. TwinVQ audio
• CPC Class Codes: G10L 19/06 Determination or coding of the spectral characteristics, e.g. of the short-term prediction coefficients
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

According to the invention, quantization encoding is conducted using the probability density function of the source, enabling fixed, variable and adaptive rate encoding. To achieve adaptive encoding, an update is conducted with a new observation of the data source, preferably with each new observation of the data source, preferably with each new observation of the data source. The current probability density function of the source is then estimated to produce codepoints to vector quantize the observation of the data source.

Claims

1. A method for vector encoding a data source, the method comprising:

taking an observation of the data source;

estimating the probability density function from the data observation;

determining codepoints for vector encoding the data source based upon the estimated probability density function from the data source.

2. The method for encoding according to claim 1, further comprising a step of transmitting an index of a determined codepoint to a receiver.

3. The method for encoding according to claim 2, further comprising a step of repeating said steps of estimating, determining with each observation of current data from the data source.

4. The method for encoding according to claim 1, wherein said step of estimating comprises:

quantizing an observation of current data from the data source using all data clusters of the current data to obtain m prospective candidates;

choosing a codepoint from among the m prospective candidates that minimizes relevant distortion; and

transmitting an index of the codepoint to the receiver.

5. The method for encoding according to claim 1, wherein said step of estimating comprises:

quantizing an observation of current data from the data source using all data clusters of the current data to obtain m prospective candidates;

choosing a codepoint from among the m prospective candidates that minimizes relevant distortion;

then

identifying the cluster which is used to quantize the observation and using the number of bits allocated to the cluster to obtain the index in the variable-rate case.

6. The method according to claim 1, further comprising a preliminary step of decorrelating output of the data source.

7. The method for encoding according to claim 1, further comprising a step of transmitting the set of model parameters to a receiver.

8. A method for encoding a non-stationary data source, the method comprising steps of:

upon arrival of new data from the data source, determining a current estimate of probability density function model parameters of the data source by applying a re-estimation algorithm to a previous estimate of the model parameters and the new data; and

updating a set of codepoints using the model parameters.

9. A method for encoding a non-stationary data source, the method comprising steps of:

taking an observation Ω

_k of a p-dimensional non-stationary random data source at time instant k;

modelling Ω

_k as an independent and identically distributed realization of a parametric density, according to;

$\begin{array}{c}f<br><br>\left({\mathrm{\Omega <br><br>}}_k❘<br><br>\mathrm{\Phi <br><br>}\right)=\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_i<br><br>f_i<br><br>\left({\mathrm{\Omega <br><br>}}_k❘<br><br>{\mathrm{\Phi <br><br>}}_i\right)<br><br>\\ \mathrm{\Phi <br><br>}=\left[m,{\mathrm{\alpha <br><br>}}_1,<br><br>\mathrm{\dots <br><br>}<br><br>,{\mathrm{\alpha <br><br>}}_m,{\mathrm{\Phi <br><br>}}_1,<br><br>\mathrm{\dots <br><br>}<br><br>,{\mathrm{\Phi <br><br>}}_m\right]\end{array}$

where, α

₁ are non-negative constants and

$\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_i=1<br><br><br><br>f_i<br><br>\left(·<br><br>❘<br><br>{\mathrm{\Phi <br><br>}}_i\right)$

is referred to as cluster i and is an individual parameteric density parameterized by Φ

_i, m is the number of clusters, Φ

is the parameter set which defines a parametric model, Ω

_k may be assumed to have been generated by one of the m clusters, and the probablity that a given obervation has been generated by cluster i is α

_I;

estimating, by a density estimation algorithm, parametric model parameters of the parametric model from the current observation of the data source;

designing a separate codebook for each of the m clusters, allocating bits to clusters according to one of a fixed or variable rate;

then, upon each arrival of new data resulting in a new observation Ω

_k-new, updating the codebook for each of the m clusters by

determining a current estimate of parametric model parameters of the data source by applying a re-estimation algorithm to a previous estimate of the model parameters and the new data; and

updating the separate codebook for each of the m clusters using the model parameters.

10. The method according to claim 9, wherein an observation Ω

_k is quantized by identifying an appropriate cluster among the m clusters and quantizing it using the codebook of that cluster.

11. The method according to claim 10, further comprising steps to fixed rate encode the new data, wherein b_tot represent the total number of bits used to quantize the parametric model density and D_i(b_i) represent the mean square distortion of an optimal b_i bit quantizer of cluster i, the steps to fix rate encode comprising:

allocating bits in said step of designing by minimizing total average distortion given that a total number of codepoints used for quantizing parametric model density is fixed, according to;

$\underset{b<br><br><br><br>i}{\min }<br><br>D_{t<br><br><br><br>o<br><br><br><br>t}=\sum <br><br>{\mathrm{\alpha <br><br>}}_i<br><br>D_i<br><br>\left(b_i\right),\mathrm{subject}<br><br><br><br>\mathrm{to}<br><br><br><br>2^{b_{\mathrm{tot}}}=\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>2^{b_i}$

and, then, quantizing the observation Ω

_k using all clusters to obtain m prospective candidates;

choosing a codepoint that minimizes relevant distortion is chosen from amongst the m probables; and

updating the codebook of all clusters.

12. The method according to claim 10, further comprising steps to variable rate encode the new data, wherein b_tot represent the total number of bits used to quantize the parametric model density and D_i(b_i) represent the mean square distortion of an optimal b_i bit quantizer of cluster i, the steps to fix rate encode comprising:

allocating bits allocation for a variable rate codebook by minimizing total average distortion according to;

$\underset{b<br><br><br><br>i}{\min }<br><br>D_{t<br><br><br><br>o<br><br><br><br>t}=\sum <br><br>{\mathrm{\alpha <br><br>}}_i<br><br>D_i<br><br>\left(b_i\right),\mathrm{subject}<br><br><br><br>\mathrm{to}<br><br><br><br>b_q=\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_i<br><br>b_i$

where b_q=b_tot−

b_c is a total number of bits less a number of bits required to identify a particular cluster (b_c);

and, then, quantizing the observation Ω

_k using all clusters to obtain m prospective candidates;

choosing a codepoint that minimizes relevant distortion is chosen from amongst the m probables; and

updating the codebook of all clusters.

13. The method according to claim 11, wherein b_c=log₂ m.

14. The method according to claim 12, wherein

$b_c\approx$

∑

l = 1 m ⁢

⁢

- α

l ⁢

log 2 ⁡

( α

l ) .