Rapid tree-based method for vector quantization
First Claim
1. A method for converting a candidate vector signal into a vector quantization (VQ) signal, the candidate vector signal identifying a candidate vector having a plurality of elements, the method comprising the steps of:
- (a) applying the candidate vector signal to circuitry which performs a binary search of a binary tree stored in a memory, wherein the candidate vector signal is a digitized representation, wherein the binary tree has intermediate nodes and leaf nodes, and wherein the applying step (a) comprises the steps of;
(i) selecting one of the elements of the candidate vector and comparing the selected element with a corresponding threshold value for each intermediate node traversed in performing the binary search of the binary tree, and(ii) identifying one of the leaf nodes encountered in the binary search of the binary tree;
(b) identifying, based on the identified leaf node, a set of VQ vectors stored in a memory;
(c) selecting one of the VQ vectors from the identified set of VQ vectors; and
(d) generating the VQ signal identifying the selected VQ vector.
2 Assignments
0 Petitions
Accused Products
Abstract
The branching decision for each node in a vector quantization (VQ) binary tree is made by a simple comparison of a pre-selected element of the candidate vector with a stored threshold resulting in a binary decision for reaching the next lower level. Each node has a preassigned element and threshold value. Conventional centroid distance training techniques (such as LBG and k-means) are used to establish code-book indices corresponding to a set of VQ centroids. The set of training vectors are used a second time to select a vector element and threshold value at each node that approximately splits the data evenly. After processing the training vectors through the binary tree using threshold decisions, a histogram is generated for each code-book index that represents the number of times a training vector belonging to a given index set appeared at each index. The final quantization is accomplished by processing and then selecting the nearest centroid belonging to that histogram. Accuracy comparable to that achieved by conventional binary tree VQ is realized but with almost a full magnitude increase in processing speed.
-
Citations
22 Claims
-
1. A method for converting a candidate vector signal into a vector quantization (VQ) signal, the candidate vector signal identifying a candidate vector having a plurality of elements, the method comprising the steps of:
-
(a) applying the candidate vector signal to circuitry which performs a binary search of a binary tree stored in a memory, wherein the candidate vector signal is a digitized representation, wherein the binary tree has intermediate nodes and leaf nodes, and wherein the applying step (a) comprises the steps of; (i) selecting one of the elements of the candidate vector and comparing the selected element with a corresponding threshold value for each intermediate node traversed in performing the binary search of the binary tree, and (ii) identifying one of the leaf nodes encountered in the binary search of the binary tree; (b) identifying, based on the identified leaf node, a set of VQ vectors stored in a memory; (c) selecting one of the VQ vectors from the identified set of VQ vectors; and (d) generating the VQ signal identifying the selected VQ vector. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for converting a candidate vector signal into a vector quantization (VQ) signal, the candidate vector signal identifying a candidate vector, the method comprising the steps of:
-
(a) generating a binary tree having intermediate nodes and leaf nodes; (b) storing the binary tree in a memory; (c) determining for each intermediate node of the binary tree a corresponding element of each of a plurality of training vectors and a corresponding threshold value; (d) performing a binary search of the binary tree for each training vector, wherein the performing step (d) includes the steps of; (i) comparing the corresponding element of each training vector with the corresponding threshold value for each intermediate node traversed in performing the binary search of the binary tree, and (ii) identifying for each training vector one of the leaf nodes encountered in the binary search of the binary tree; (e) generating a plurality of sets of VQ vectors, wherein each set of VQ vectors corresponds to one of the identified leaf nodes of the binary tree; (f) storing each set of VQ vectors in a memory; (g) applying the candidate vector signal to circuitry which performs a binary search of the binary tree to identify one of the sets of VQ vectors; (h) selecting one of the VQ vectors from the identified set of VQ vectors; and (i) generating the VQ signal identifying the selected VQ vector. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
16. An apparatus for converting a candidate vector signal into a vector quantization (VQ) signal, the candidate vector signal identifying a candidate vector having a plurality of elements, the apparatus comprising:
-
(a) a first memory which stores a binary tree having intermediate nodes and leaf nodes; (b) control circuitry, coupled to the first memory, which performs a binary search of the binary tree, wherein the control circuitry comprises; (i) a selector which receives the candidate vector signal and which selects one of the elements of the candidate vector for each intermediate node traversed in performing the binary search of the binary tree, and (ii) a comparator, coupled to the first memory and to the selector, which compares the selected element with a corresponding threshold value for each intermediate node traversed in performing the binary search of the binary tree, the control circuitry identifying one of the leaf nodes encountered in the binary search of the binary tree; and (c) a second memory, coupled to the control circuitry, which stores a set of VQ vectors corresponding to the identified leaf node; the control circuitry identifying the set of VQ vectors corresponding to the identified leaf node, selecting one of the VQ vectors from the identified set of VQ vectors, and generating the VQ signal identifying the selected VQ vector. - View Dependent Claims (17, 18, 19, 20, 21, 22)
-
Specification