Vector quantizing apparatus

• US 5,677,986 A
• Filed: 05/26/1995
• Issued: 10/14/1997
• Est. Priority Date: 05/27/1994
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Oshikiri, Masahiro, Miseki, Kimio, Akamine, Masami, Amada, Tadashi
• Primary Examiner(s): Safourek, Benedict V.
• Application Number:
  US08/451,174
• Time in Patent Office: 872 Days
• Field of Search: 395/2.1, 395/2.28, 395/2.3, 395/2.31, 395/2.38, 395/2.91, 395/2.92, 395/2.71, 375/240, 348/417, 348/418, 348/422
• US Class Current: 704/222
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

A vector quantizing apparatus includes a first search section for obtaining an approximate vector X1 which is approximated to a desired vector R, a residual vector calculator for calculating a residual vector Rv from the desired vector R and the approximate vector X1, a weighting section for obtaining weighted vectors X2 to XN of code vectors x2 to xN, and a second search section for calculating an estimation value which is the magnitude of a projection vector of the residual vector Rv with respect to the vector space formed by the approximate vector X1 and the weighted vectors X2 to XN, and searching a code vector which maximizes this estimation value.

Claims

1. A vector quantizing apparatus comprising:

means for receiving a set of first basis vectors corresponding to a pre-stage output;

means for receiving a target vector;

means for calculating an approximate vector approximate to a target on the basis of the set of first basis vectors and the target, and calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

code vector means for outputting a set of code vectors;

selecting means for selecting at least one code vector from the set of code vectors;

means for producing a set of second basis vectors on the basis of the code vector selected by said selecting means and the set of first basis vectors;

searching means for searching, from the set of code vectors, for the code vectors which allow to increase a magnitude of a projection vector obtained by projecting the residual vector in a vector space formed by the set of second basis vectors; and

means for outputting information specifying the code vectors searched by said searching means.

2. An apparatus according to claim 1, wherein said searching means comprises:

projection vector means for receiving the set of second basis vectors and the residual vector and

calculating a combination of code vectors which allows to increase the magnitude of the projection vector obtained by projecting the residual vector in the vector space formed by the second basis vectors; and

estimating means for searching, from the set of code vectors, for a code vector by which the projection vector is maximized.

3. An apparatus according to claim 1, further comprising:

weighting means for weighting the code vector selected from the set of code vectors, and

wherein said means for obtaining a set of second basis vectors calculates the second basis vectors from the weighted code vector and the set of first basis vectors.

4. An apparatus according to claim 3, wherein said searching means comprises:

projection vector means for receiving the set of second basis vectors and the residual vector and calculating the code vectors which allow to increase the magnitude of the projection vector obtained by projecting the residual vector in a vector space formed by the second basis vectors; and

estimating means for searching for a code vector by which the projection vector is maximized.

5. An apparatus according to claim 3, wherein said searching means has a codebook which stores a large number of code vectors and means for searching for an optimum code vector from said codebook.

6. A vector quantizing apparatus according to claim 1, which includes pre-selecting means for selecting, from the set of code vectors, code vectors which allow to increase the magnitude of an estimation value increasing the projection vector.

7. A vector quantizing apparatus according to claim 6, wherein said pre-selecting means selects a code vector which allows to increase the magnitude of an estimation value based on an inner product of the code vector selected by said selecting means and the residual vector.

8. A vector quantizing apparatus comprising:

means for receiving a set of first basis vectors corresponding to a pre-stage output;

means for receiving a target vector;

means for calculating an approximate vector approximate to a target on the basis of the set of first basis vectors and the target, and calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

code vector means for outputting a set of code vectors;

selecting means for selecting at least one code vector from the set of code vectors;

searching means for searching, from the set of code vectors, for at least one code vector which allows a maximization of an estimation value corresponding to an inner product of the code vector selected by said selecting means and the residual vector; and

means for outputting information specifying the code vector searched by said searching means.

9. An apparatus according to claim 8, wherein said searching means comprises:

inner product calculating means for calculating the inner product of the residual vector and the selected code vector; and

searching means for searching, from the set of code vectors, for the code vector by which the estimation value based an the inner product is maximized.

10. An apparatus according to claim 9, further comprising weighting means for weighting the code vector, and

wherein said inner product calculating means calculates an inner product of the weighted code vector and the residual vector.

11. An apparatus according to claim 8, wherein said searching means searches for a code vector which allows a maximization of the inner product of the code vector and the residual vector.

12. A vector quantizing apparatus comprising:

means for receiving a set of first basis vectors corresponding to a pre-stage output;

means for receiving a target vector;

means for calculating an approximate vector approximate to a target on the basis of the set of first basis vectors and the target, and calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

code vector means for outputting set of code vectors;

selecting means for 1 at least one code vector from the set of code vectors;

first searching means for searching, from the set of code vectors, as pre-selected candidates, a plurality of code vectors which allows an increase of an estimation value based on an inner product of the code vector selected by said selecting means and the residual vector;

means for producing a set of second basis vectors on the basis of the code vectors selected as the preselected candidates by said first searching means and the set of first basis vectors;

second searching means for searching, from the set of code vectors, for an optimum code vector which allows an increase of a projection vector obtained by projecting the residual vector in a vector space formed by the set of second basis vectors; and

means for outputting information specifying the optimum code vector.

13. An apparatus according to claim 12, wherein said first searching means comprises:

inner product calculating means for calculating the inner product of the residual vector and the code vector; and

searching means for searching for the code vector which allows an increase of the estimation value based on the inner product.

14. An apparatus according to claim 12, further comprising weighting means for weighting the code vector selected from the set of code vectors, and

wherein said first searching means selects a plurality of weighted code vectors, as pre-selection candidates, from a set of weighted code vectors, and said means for obtaining a set of second basis vectors calculates the second basis vectors from a vector space formed by the weighted code vectors and the set of first basis vectors.

15. An apparatus according to claim 12, wherein said second searching means comprises:

projection vector means for receiving the set of second basis vectors and the residual vector and calculating a code vector which allows an increase of the projection vector obtained by projecting the residual vector in a vector space formed by the second basis vectors; and

estimating means for searching for a code vector by which the projection vector is maximized.

16. A vector quantizing apparatus comprising:

means for receiving a set of first basis vectors corresponding to a pre-stage output;

means for receiving a target vector;

means for calculating an approximate vector approximate to a target on the basis of the set of first basis vectors and the target, and calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

code vector means for outputting a set of code vectors;

selecting means for selecting at least one code vector from the set of code vectors;

pre-selecting means for selecting, from a set of code vectors, code code vectors which allow an increase of an estimation value based on an inner product of the code vector selected by said selecting means and the residual vector; and

main-selecting means including means for producing a set of second basis vectors on the basis of the code vector selected by said pre-selecting means and the set of first basis vectors, and means for searching, from the set of code vectors, for a code vector which allows to increase a magnitude of a projection vector obtained by projecting the residual vector in a vector space formed by the set of second basis vectors; and

means for outputting information specifying the optimum code vector.

17. An apparatus according to claim 16, wherein

said main-selecting means includes means for selecting, from the pre-selected candidates, for an optimum code vector which allows a maximization of a value calculated by dividing the inner product used in said pre-selecting means by a magnitude of a code vector orthogonalized in a vector space formed by the set of first basis vectors.

18. An apparatus according to claim 16, wherein said pre-selecting means selects a code vector which allows an increase of a value obtained by weighting the inner product of a code vector and the residual vector with a weighting coefficient based on the code vector.

19. An apparatus according to claim 16, wherein said pre-selecting means comprises means for calculating the inner product by using an inner product of the code vector and a backward filtered vector of the residual vector.

20. A vector quantizing apparatus comprising:

means for receiving a set of first basis vectors corresponding to a pre-stage output;

means for receiving a target vector;

means for calculating an approximate vector approximate to a target on the basis of the set of first basis vectors and the target, and calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

code vector means for outputting a set of code vectors;

selecting means for selecting at least one code vector from the set of code vectors;

searching means for searching, from the set of code vectors, for a code vector which allows a maximization of an estimation value based on an inner product of the code vector selected by said selecting means and the residual vector, said searching means including means for calculating a value corresponding to the inner product by using an inner product obtained by the code vector and a backward filtered vector of the residual vector; and

means for outputting information specifying the code vector searched by said searching games.

21. An apparatus according to claim 20, wherein said searching means comprises a plurality of codebooks storing code vectors and a weighted synthesis filter which are provided externally, and a backward filtering section for backward-filtering the residual vector.

22. An apparatus according to claim 20, wherein said searching means comprises a weighting coefficient calculator for calculating the code vector, a weighting section for multiplying the inner product by a weighting coefficient corresponding to the reciprocal of the square of the code vector, to obtain an estimation value by which a stochastic codebook is searched.

23. An apparatus according to claim 20, wherein said searching means comprises a pre-selector for selecting several vector candidates by an approximate calculation and a main-selector for calculating the value of the denominator for each of the pre-selected candidates, thereby constituting an estimate expression for main selection, and then searching for a candidate by which this estimate expression is maximized and outputting information indicating an optimum candidate.

24. An apparatus according to claim 20, which includes backward filtering means for obtaining the backward filtered vector of the residual vector and wherein said searching means comprises means for calculating the inner product from the code vector and the backward filtered vector of the residual vector.

25. An apparatus according claim 20, which includes backward filtering means for obtaining the backward filtered vector of the residual vector and wherein said searching means comprises a pre-selector for selecting several vector candidates by an approximate calculation and a main-selector for searching, from said set of code vectors, the code vector which allows an increase of the projection vector obtained by projecting the residual vector in a vector space formed by the vector candidates and basis vectors.

26. An apparatus according to claim 20, which comprises a plurality of codebooks storing code vectors and a weighted synthesis filter which are provided externally, and a backward filtering section for backward-filtering the residual vector and wherein said searching means comprises a pre-selector for selecting several vector candidates by an approximate calculation and a main-selector for searching, from a set of code vectors of said codebooks, for a code vector which allows an increase of the projection vector obtained by projecting the residual vector in a vector space formed by the vector candidates and basis vectors.

27. A vector quantizing method comprising:

receiving a set of first basis vectors corresponding to a pre-stage output;

calculating an approximate vector approximate to a target on the basis of the set of first basis vectors and the target;

calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

producing a set of code vectors;

selecting at least one code vector from the set of code vectors;

producing a set of second basis vectors on the basis of the at least one code vector selected in said selecting step and the set of first basis vectors;

searching, from the set of code vectors, for the code vectors which allow to increase a magnitude of a projection vector obtained by projecting the residual vector in a vector space formed by the set of second basis vectors; and

outputting information specifying the code vector searched by said searching.

28. A vector quantizing method comprising:

receiving a set of first basis vectors corresponding to a pre-stage output;

calculating an approximate vector approximate to a target on the basic of the set of first basis vectors and the target;

calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

producing a set of code vectors;

selecting at least one code vector from the set of code vectors;

searching, from the set of code vectors, for a combination of code vectors which allows a maximization of an estimation value corresponding to an inner product of the code vector selected by said selecting and the residual vector; and

outputting information specifying the code vector searched.

29. A vector quantizing method comprising:

receiving a set of first basis vectors corresponding to a pre-stage output;

calculating an approximate vector approximate to a target on the basis of the set of first basis vectors and the target;

calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

producing a set of code vectors;

selecting at least one code vector from the set of code vectors;

searching, from the set of code vectors, as preselected candidates, for a plurality of code vectors which allows an increase of an estimation value based on an inner product of the code vector selected by said selecting and the residual vector;

producing a set of second basis vectors on the basis of the code vectors selected as the pre-selected candidates by said searching and the set of first basis vectors;

searching, from the set of code vectors, for an optimum code vector which allows to increase a magnitude of a projection vector obtained by projecting the residual vector in a vector space formed by the set of second basis vectors; and

outputting information specifying the optimum code vector.

30. A vector quantizing method comprising:

receiving a set of first basis vectors corresponding to a pre-stage output;

calculating an approximate vector approximate to a target on the basis of the set of first basis vectors and the target, and calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

outputting a set of code vectors;

selecting at least one code vector from the set of code vectors;

searching, from a set of code vectors, at least one code vector which allows an increase of an estimation value based on an inner product of the code vector selected by said selecting and the residual vector; and

producing a set of second basis vectors on the basis of the code vector selected by said selecting and the set of first basis vectors and searching, from the set of code vectors, for a code vector which allows to increase a magnitude of a projection vector obtained by projecting the residual vector in a vector space formed by the set of second basis vectors; and

outputting information specifying the optimum code vector.

31. A vector quantizing method comprising:

receiving a set of first basis vectors corresponding to a pre-stage output;

calculating an approximate vector approximate to a target on the basis of the set of first basis vectors and the target, and calculating a residual vector corresponding to a difference between the target vector and the approximate vector;

producing a set of code vectors;

selecting at least one code vector from the set of code vectors;

searching, from the set of code vectors, for a code vector which allows a maximization of an estimation value based on an inner product of the code vector selected by said selecting and the residual vector, said searching including calculating a value corresponding to the inner product by using an inner product obtained by the code vector and a backward filtered vector of the residual vector; and

outputting information specifying the code vector searched by said searching.