A fast search algorithm for vector quantization using L/sub 2/-norm pyramid of codewords
Byung Cheol Song, Jong Beom Ra · IEEE Transactions on Image Processing · 2002
Vector quantization for image compression requires expensive encoding time to find the closest codeword to the input vector. This paper presents a fast algorithm to speed up the closest codeword search process in vector quantization encoding. By using an appropriate topological structure of the codebook, we first derive a condition to eliminate unnecessary matching operations from the search procedure. Then, based on this elimination condition, a fast search algorithm is suggested. Simulation results show that with little preprocessing and memory cost, the proposed search algorithm significantly reduces the encoding complexity while maintaining the same encoding quality as that of the full search algorithm. It is also found that the proposed algorithm outperforms the existing search algorithms.
Cited by 41 works. doi:10.1109/83.977878
Authors
References
- The Laplacian Pyramid as a Compact Image Code
- Vector Quantization and Signal Compression
- An Algorithm for Vector Quantizer Design
- Vector Quantization
- An improvement of the minimum distortion encoding algorithm for vector quantization
- A new vector quantization clustering algorithm
- A fast nearest-neighbor search algorithm
- Fast full search equivalent encoding algorithms for image compression using vector quantization
- A fast mean-distance-ordered partial codebook search algorithm for image vector quantization
- A fast search algorithm for vector quantization using mean pyramids of codewords