A novel approach for fast codebook re-quantization
| Autor: | Jim Z. C. Lai, Chih-Tang Chang, Yi-Ching Liaw |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Linde–Buzo–Gray algorithm
Computational complexity theory Quantization (signal processing) ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION Vector quantization Code word Codebook Data_CODINGANDINFORMATIONTHEORY Computer Science::Sound Artificial Intelligence Search algorithm Computer Science::Computer Vision and Pattern Recognition Signal Processing Computer Vision and Pattern Recognition Algorithm Software Computer Science::Information Theory Data compression Mathematics |
| Zdroj: | Pattern Recognition. 41:2956-2963 |
| ISSN: | 0031-3203 |
| DOI: | 10.1016/j.patcog.2008.02.008 |
| Popis: | In this paper, we present a fast codebook re-quantization algorithm (FCRA) using codewords of a codebook being re-quantized as the training vectors to generate the re-quantized codebook. Our method is different from the available approach, which uses the original training set to generate a re-quantized codebook. Compared to the traditional approach, our method can reduce the computing time dramatically, since the number of codewords of a codebook being re-quantized is usually much smaller than the number of original training vectors. Our method first classifies codewords of a re-quantized codebook into static and active groups. This approach uses the information of codeword displacements between successive partitions to reject impossible candidates in the partition process of codebook re-quantization. By implementing a fast search algorithm used for vector quantization encoding (MFAUPI) in the partition step of FCRA, the computational complexity of codebook re-quantization can be further reduced significantly. Using MFAUPI, the computing time of FCRA can be reduced by a factor of 1.55-3.78. Compared with the available approach OARC (optimization algorithm for re-quantization codebook), our proposed method can reduce the codebook re-quantization time by a factor of about 8005 using a training set of six real images. This reduction factor is increased when the re-quantized codebook size and/or training set size are increased. It is noted that our proposed algorithm can generate the same re-quantized codebook as that produced by the OARC. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect