Methods and apparatuses for variable dimension vector quantization

• US 20070118370A1
• Filed: 01/16/2007
• Published: 05/24/2007
• Est. Priority Date: 03/04/2003
• Status: Abandoned Application

• Current Assignee: Wai Chu
• Original Assignee: Wai Chu
• Inventors: Chu, Wai
• Application Number:
  US11/654,147
• Publication Number:
  US 20070118370A1
• Time in Patent Office: Days
• US Class Current: 704/230
• CPC Class Codes: G10L 19/08 Determination or coding of the excitation function; Determination or coding of the long-term prediction parameters
• CPC Class Codes: G10L 2019/0004 Design or structure of the codebook

Abstract

Improved variable dimension vector quantization-related (“VDVQ-related”) processes have been developed that provide quality improvements over known coding processes in codebook optimization and the quantization of harmonic magnitudes that can be applied to a broad range of distortion measures, including those that would involve inverting a singular matrix using known centroid computation techniques. The improved VDVQ-related processes improve the way in which actual codevectors are extracted from the codevectors of the codebook by redefining the index relationship and using interpolation to determine the actual codevector elements when the index relationship produces a non-integer value. Additionally, these processes improve the way in which codebooks are optimized using the principles of gradient-descent. These improved VDVQ-related processes can be implemented in various software and hardware implementations.

Claims

1. A method for creating an optimum partition for a codebook, wherein the codebook includes at least one codevector y_i, wherein each of the at least one codevectors y_i includes a codevector dimension N_v and at least one codevector element y_i,m, comprising:

(A) collecting a training data set, wherein the training data set comprises a plurality of input vectors, wherein each input vector is denoted x_k and includes a variable training vector dimension N(T_k);

(B) defining a partition rule;

(C) defining a distortion measure for the partition rule, wherein the distortion measure defines an average distortion; and

(D) finding a nearest codevector for each of the plurality of input vectors using an interpolation index relationship.

2. The method for creating an optimum partition for a codebook, as claimed in claim 1, wherein steps (A), (B), and (C) may be performed in any order.

3. The method for creating an optimum partition for a codebook, as claimed in Claim 1, wherein finding the nearest codevector for each of the plurality of input vectors using the interpolation index relationship, includes for each of the plurality of input vectors:

extracting an actual codevector from each codevector, wherein each actual codevector includes at least one actual codevector element, including for each of the at least one codevectors;

defining an index relationship, including;

calculating a codevector index according to an interpolation index relationship; and

determining whether the codevector index is an integer;

wherein if the codevector index is an integer, defining the index relationship according to a known index relationship, and wherein if the codevector index is not an integer, defining the index relationship according to the interpolation index relationship; and

determining the actual codevector as a function of the index relationship including determining the at least one actual codevector element, wherein if the index relationship is the known index relationship, the at least one actual codevector element is determined as a function of the known index relationship; and

wherein if the index relationship is the interpolation index relationship, the at least one actual codevector element is determined by an interpolation of a first and a second adjacent codevector elements;

computing a distortion according to the distortion measure, between one of the at least one input vectors and every actual codevector, and designating the actual codevector with which one of the one of the at least one input vectors creates the lowest distortion as an optimum actual codevector; and

associating the one of the at least one input vectors with the codevector from which the optimum actual codevector was extracted.

4. A computer readable storage medium storing computer readable program code for creating an optimum partition, the computer readable program code comprising:

data encoding a codebook and a training data set;

wherein the codebook includes the at least one codevector y_i, wherein the at least one codevector y_i includes at least one codevector element y_i,m; and

wherein the training data asset includes a plurality of input vectors; and

a computer code implementing a method for creating an optimum partition in response to the plurality of input vectors, wherein the method for creating an optimum partition includes;

(A) collecting a training data set, wherein the training data set comprises a plurality of input vectors, wherein each input vector is denoted x_k and includes a variable training vector dimension N(T_k);

(B) defining a partition rule;

(C) defining a distortion measure for the partition rule, wherein the distortion measure defines an average distortion; and

(D) finding a nearest codevector for each of the plurality of input vectors using an interpolation index relationship.

5. An optimum partition creation device for a codebook, wherein the codebook includes at least one codevector y_i, wherein each of the at least one codevectors y_i includes a codevector dimension N_v and at least one codevector element y_i,m, comprising:

an interface unit for receiving a training data set, a partition rule, and a distortion measure, wherein the training data set includes a plurality of input vectors, wherein the plurality of input vectors includes a variable training dimension N(T_k); and

wherein the distortion measure defines an average distortion; and

a partition creation unit coupled to the interface unit, wherein the partition creation unit includes a memory and a processor coupled to the memory unit;

wherein the memory stores the at least one codevector y_i, the distortion measure, the partition rule, and a method for creating an optimum partition for the codebook; and

wherein the processor, using the method for creating the optimum partition for the codebook, the at least one codevector y_i, the partition rule and the distortion measure communicated from the memory, finds the nearest codevector for each of the plurality of input vectors using an interpolation index relationship.