Rapid tree-based method for vector quantization
US5734791A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Dec 31, 1992 |
| Grant date | Mar 31, 1998 |
| Priority date | — |
| Expiry date | Dec 31, 2012 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG10L19/038
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.