Fast search method for vector quantizer communication and pattern recognition systems

• US 4,907,276 A
• Filed: 04/05/1988
• Issued: 03/06/1990
• Est. Priority Date: 04/05/1988
• Status: Expired due to Fees

• Current Assignee: DSP Group Limited The 5 Ussishkin Street Ramat Hasharon Israel
• Original Assignee: DSP Group Ltd. (Synaptics Incorporated)
• Inventors: Aldersberg, Shabtai
• Primary Examiner(s): Kemeny, Emanuel S.
• Application Number:
  US07/177,981
• Time in Patent Office: 700 Days
• Field of Search: 381/31, 381/35, 381/36, 381/43, 364/725
• US Class Current: 704/222
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: G10L 19/038 Vector quantisation, e.g. TwinVQ audio
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

An encoder apparatus for communication and pattern recognition systems employing a nearest neighbor search method for signal and data compression, based on a vector encoding quantization technique which optimizes systems performance with substantially reduced computational complexity using a fast geometrically-oriented search procedure. The apparatus comprises pre-procesing apparatus for providing off-line reorganization of a codebook having a set of reference vector patterns constituting codevectors with which the input vector is to be compared in a search procedure, and on-line apparatus for encoding the random input vector through quantization in accordance with the search procedure in the codebook. The on-line encoding apparatus comprises: apparatus for providing a transform domain vector having a set of eigenvectors associated therewith; apparatus for determining a surface vector nearest to the transform domain vector on the axis having the largest variance; apparatus for determining a distance value providing the distortion between the transform domain vector and the surface vector, defined by the Euclidean distance; apparatus for determining a codebook contiguous sub-group range having contained therewithin codevectors and being bounded by a hypersphere having a k-dimensional radius defined as the square root of the distance value; and apparatus for performing a full search over the contiguous sub-group range within the hypersphere to select the one of the codevectors nearest to the transform domain vector for encoding it in accordance with the one selected codevector.

Claims

1. An apparatus for encoding speech signals represented by a random input vector having k components, said apparatus comprising:

pre-processing means for providing off-line reorganization of a codebook having a set of reference vector patterns constituting codevectors with which the input vector is to be compared in a search procedure, said pre-processing means comprising;

means for transforming each of said codebook codevectors to provide a transform domain representation of said codebook;

means for determining a principal axis p having the largest variance in said codebook transform domain representation; and

means for re-ordering said codebook codevectors according to their descending value on the p axis; and

on-line means for encoding the random input vector through quantization in accordance with said search procedure in the codebook.

2. The apparatus of claim 1 and wherein said on-line means for encoding comprise:

on-line means for encoding the random input vector through quantization in accordance with said search procedure in the codebook, said on-line encoding means comprising;

means for transforming the input vector to provide a transform domain vector having a set of eigenvectors associated therewith;

means for determining a surface vector nearest to said transform domain vector on said principal axis;

means for determining a distance value providing the distortion between said transform domain vector and said surface vector, said distance value being defined as the Euclidean distance between said vectors and being the Minimum Mean Square Error (MMSE) distortion criteria;

means for determining a codebook contiguous sub-group range having contained therewithin codevectors and being bounded by a hypersphere having a k-dimensional radius defined as the square root of said distance value;

means for performing a full search over said contiguous sub-group range within said hypersphere to select the one of said codevectors nearest to said transform domain vector by determining the distortion therebetween in accordance with said MMSE criteria; and

means for encoding said transform domain vector in accordance with said one selected codevector.

3. The apparatus of claim 2 wherein said means for transforming the input vector to provide said transform domain vector is provided by a Karhunen-Loewe Transform (KLT).

4. The apparatus of claim 2 wherein said means for transforming the input vector to provide said transform domain vector is provided by a discrete cosine transform (DCT).

5. The apparatus of claim 1 wherein said search procedure is conducted over said contiguous sub-group range in said codebook by comparison between the input vector and the codevector to determine the proper coding.

6. The apparatus of claim 2 wherein said hypersphere is defined as a relatively small k-dimensional sub-space centered around the input vector and containing the best matching codevector.

7. The apparatus of claim 2 wherein said means for determining said surface vector nearest to said transform domain vector on the principal axis p operates in accordance with the following relation:

space="preserve" listing-type="equation">Z.sub.s =(Z.sub.tp -Z.sub.sp).sup.2 ≦

(Z.sub.tp -Z.sub.np).sup.2 1≦

n≦

N

where Z_s is the surface vector and Z_t is the transform domain vector.

8. The apparatus of claim 7 wherein said principal axis search for said surface vector is by means of a binary search of the order of Log₂ N.

9. The apparatus of claim 2 wherein said means for determining the distance value providing the distortion between said transform domain vector Z_t and said surface vector Z_s applies the Euclidean distance in accordance with the relation:

##EQU2##

10. The apparatus of claim 2 wherein said means for determining said codebook contiguous sub-group range operates such that codevectors Z_j contained therewithin are bounded by high and low bounds determined by Zh, Zl where:

space="preserve" listing-type="equation">Z.sub.hp <

Z.sub.tp +r.sub.p <

Z.sub.(h+1)p ;

space="preserve" listing-type="equation">and

space="preserve" listing-type="equation">Z.sub.(l-1)p <

Z.sub.tp -r.sub.p <

Z.sub.lp

thereby defining a hypersphere having a k-dimensional radius r_p defined as;

space="preserve" listing-type="equation">r.sub.p =SQRT (d(Z.sub.t, Z.sub.s)).

11. The apparatus of claim 2 wherein there is provided, in recursive fashion, a combined operation of the plurality of said means for determining said surface vector, means for determining said distance value, means for determining said codebook subgroup range in the hypersphere and means for performing said full search over the sub-group range within the hypersphere, such that each determination of a nearer codevector establishes it as the new nearest codevector, and initiates the repetition of said combined operation of the plurality of said means for determining the new hypersphere for the subsequent full search, wherein said means for determining said surface vector operates by substitution of the current surface vector for the new nearest codevector.

12. A method for encoding speech represented by a random input vector having k components, said method comprising the steps of:

pre-processing to provide off-line reorganization of a codebook having a set of reference vector patterns constituting codevectors with which the input vector is to be compared in a search procedure, said pre-processing step comprising the steps of;

transforming each of said codebook codevectors to provide a transform domain representation of said codebook;

determining a principal axis p having the largest variance in said codebook transform domain representation; and

re-ordering said codebook codevectors according to their descending value on the p axis; and

encoding the random input vector through on-line quantization in accordance with said search procedure in the codebook, said on-line encoding step comprising the steps of;

transforming the input vector to provide a transform domain vector having a set of eigenvectors associated therewith;

determining a surface vector nearest to said transform domain vector on said principal axis;

determining a distance value providing the distortion between said transform domain vector and said surface vector, said distance value being defined as the Euclidean distance between said vectors and being the Minimum Mean Square Error (MMSE) distortion criteria;

determining a codebook contiguous sub-group range having contained therewithin codevectors and being bounded by a hypersphere having a k-dimensional radius defined as the square root of said distance value;

performing a full search over said contiguous sub-group range within said hypersphere to select the one of said codevectors nearest to said transform domain vector by determining the distortion therebetween in accordance with said MMSE criteria; and

encoding said transform domain vector in accordance with said one selected codevector.

13. The method of claim 12 wherein said on-line encoding step is performed by a source coder in a communication system providing optimal vector quantization and reducing computational complexity.

14. The method of claim 12 wherein said step of transforming the input vector to provide said transform domain vector is performed by a Karhunen-Loewe Transform (KLT).

15. The method of claim 12 wherein said step of transforming the input vector to provide said transform domain vector is performed by a discrete cosine transform (DCT).

16. The method of claim 12 wherein said search procedure is conducted over said contiguous sub-group range in said codebook by comparison between the input vector and the codevector to determine the proper coding.

17. The method of claim 12 wherein said hypersphere is defined as a relatively small k-dimensional sub-space centered around the input vector and containing the best matching codevector.

18. The method of claim 12 wherein said surface vector determination nearest to said transform domain vector on the principal axis p is performed in accordance with the following relation:

space="preserve" listing-type="equation">Z.sub.s =(Z.sub.tp -Z.sub.sp).sup.2 ≦

(Z.sub.tp -Z.sub.np).sup.2 1≦

n≦

N

where Z_s is the surface vector and Z_t is the transform domain vector.

19. The method of claim 18 wherein said principal axis search for said surface vector is performed as a binary search of the order of Log₂ N.

20. The method of claim 12 wherein said distance value determination providing the distortion between said transform domain vector Z_t and said surface vector Z_s applies the Euclidean distance in accordance with the relation:

##EQU3##

21. The method of claim 12 wherein said codebook contiguous sub-group range determination defines codevectors Z_j contained therewithin which are bounded by high and low bounds determined by Zh, Zl where:

space="preserve" listing-type="equation">Z.sub.hp <

Z.sub.tp +r.sub.p <

Z.sub.(h+1)p ;

space="preserve" listing-type="equation">and

space="preserve" listing-type="equation">Z.sub.(l-1)p <

Z.sub.tp -r.sub.p <

Z.sub.lp

thereby defining a hypersphere having a k-dimensional radius r_p defined as;

space="preserve" listing-type="equation">r.sub.p =SQRT (d(Z.sub.t, Z.sub.s)).

22. The method of claim 12 wherein there is provided, in recursive fashion, a combined operation of the plurality of said steps of determining said surface vector, determining said distance value, determining said codebook sub-group range in the hypersphere and performing said full search over the sub-group range within the hypersphere, such that each determination of a nearer codevector establishes it as the new nearest codevector, and initiates the repetition of said combined operation of the plurality of said steps for determining the new hypersphere for the subsequent full search, wherein said step of determining said surface vector is performed by substitution of the current surface vector for the new nearest codevector.