Fast search method for nearest neighbor vector quantization

• US 20040108944A1
• Filed: 09/26/2003
• Published: 06/10/2004
• Est. Priority Date: 09/27/2002
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kang, Sang-Won, Chi, Sang-Hyun, Hwang, Seong-Kyu, Kim, Yong-Serk, Lee, Nam-Il
• Granted Patent: US 6,836,225 B2
• Time in Patent Office: Days
• US Class Current: 341/50
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A fast search method for searching for an optimum codeword for nearest neighbor vector quantization. An upper boundary value and a lower boundary value between which an optimum codeword will exist in a codebook are calculated using a distortion of a designated element in an input vector and an experimentally determined threshold. Further, a start point and an end point for codebook search are determined using a binary search method from a codebook rearranged in descending order, and a full search scheme is applied only within a search range calculated by the determined start point and end point, thereby determining an optimum codeword for nearest neighbor vector quantization.

Claims

1. A method for searching a codebook having a plurality of codewords for an optimum codeword for quantizing an input vector, comprising the steps of:

calculating a lower boundary value and an upper boundary value by subtracting and adding a predetermined threshold from/to an element value corresponding to a particular position among a plurality of elements constituting the input vector;

designating, as search object codewords, codewords having element values existing between the lower boundary value and the upper boundary value among element values corresponding to the particular position in the respective codewords constituting the codebook; and

determining optimum codewords having a minimum quantization error value through full search for calculating a quantization error value with the input vector for the search object codewords.

2. The method of claim 1, wherein the threshold is previously determined by a maximum value among MSE (Mean Squared Error) values for training vectors and a control element determined by experiment so as to minimize the number of the search object codewords.

3. The method of claim 2, wherein the control element is determined as a value between 0 and 1.

4. The method of claim 1, wherein the step of designating search object codewords comprises the steps of:

rearranging the codewords in the codebook in descending order by a size of element values corresponding to the particular position in the respective codewords constituting the codebook;

determining a point first corresponding to an element value smaller than the upper boundary value as a start point by comparing the upper boundary value with element values corresponding to the particular position in the rearranged codewords;

determining a point first corresponding to an element value larger than an element value that is smaller than the lower boundary value as an end point by comparing the lower boundary value with element values corresponding to the particular position in the rearranged codewords; and

designating codewords existing between the start point and the end point as the search codewords.

5. The method of claim 1, wherein the step of designating search object codewords comprises the steps of:

rearranging the codewords in the codebook in ascending order by a size of element values corresponding to the particular position in the respective codewords constituting the codebook;

determining a point first corresponding to an element value larger than the lower boundary value as a start point by comparing the lower boundary value with element values corresponding to the particular position in the rearranged codewords;

determining a point first corresponding to an element value smaller than an element value that is larger than the lower boundary value by comparing the upper boundary value with element values corresponding to the particular position in the rearranged codewords; and

designating codewords existing between the start point and the end point as the search codewords.

6. A computer-readable medium of instructions for searching a codebook having a plurality of codewords for an optimum codeword for quantizing an input vector, the instructions comprising:

a first set of instructions for calculating a lower boundary value and an upper boundary value by subtracting and adding a predetermined threshold from/to an element value corresponding to a particular position among a plurality of elements constituting the input vector;

a second set of instructions for designating, as search object codewords, codewords having element values existing between the lower boundary value and the upper boundary value among element values corresponding to the particular position in the respective codewords constituting the codebook; and

a third set of instructions for determining optimum codewords having a minimum quantization error value through full search for calculating a quantization error value with the input vector for the search object codewords.

7. The computer-readable medium of instructions of claim 6, wherein the threshold is previously determined by a maximum value among MSE (Mean Squared Error) values for training vectors and a control element determined by experiment so as to minimize the number of the search object codewords.

8. The computer-readable medium of instructions of claim 7, wherein the control element is determined as a value between 0 and 1.

9. The computer-readable medium of instructions of claim 6, wherein the second set of instructions includes instructions for:

rearranging the codewords in the codebook in descending order by a size of element values corresponding to the particular position in the respective codewords constituting the codebook;

determining a point first corresponding to an element value smaller than the upper boundary value as a start point by comparing the upper boundary value with element values corresponding to the particular position in the rearranged codewords;

determining a point first corresponding to an element value larger than an element value that is smaller than the lower boundary value as an end point by comparing the lower boundary value with element values corresponding to the particular position in the rearranged codewords; and

designating codewords existing between the start point and the end point as the search codewords.

10. The computer-readable medium of instructions of claim 6, wherein the second set of instructions includes instructions for:

rearranging the codewords in the codebook in ascending order by a size of element values corresponding to the particular position in the respective codewords constituting the codebook;

determining a point first corresponding to an element value larger than the lower boundary value as a start point by comparing the lower boundary value with element values corresponding to the particular position in the rearranged codewords;

determining a point first corresponding to an element value smaller than an element value that is larger than the lower boundary value by comparing the upper boundary value with element values corresponding to the particular position in the rearranged codewords; and

designating codewords existing between the start point and the end point as the search codewords.