20 October 1993 Fast algorithm for color vector quantization
Author Affiliations +
Abstract
Color vector quantization is a very important technique to display a color image with N2, typically N equals 256, colors in a personal computer and workstation or print a color image with K, typically K equals 256, colors without too much color degradation. The LBG algorithm is a popular suboptimal algorithm to solve the color vector quantization. However, it is very slow. Several fast algorithms such as the popularity algorithm, the median cut algorithm have been proposed. In this paper, we propose a new fast algorithm for color vector quantization. The proposed algorithm has been implemented in a tree structure. Assume that n is the number of pixels in the image and m is the dimension of the color space. In the tree structure, there is n leaves in the tree in the worst case, where n is the total pixel numbers in the original color image. The storage complexity of the proposed algorithm is O(n) and the time complexity if O(n log2 N). It is much faster than the median cut algorithm. In the same space complexity O(mn) our algorithm has time complexity O(n log2 K) while the median cut algorithm requires O(m log2 Kn log2 n), where m equals 3 is the dimensionality of the color space. Also, our algorithm finds the centroid of a compact cube instead of a rectangular shape in the median cut algorithm. Therefore, it produces better color images after vector quantization.
© (1993) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Long-Wen Chang, Long-Wen Chang, Her-Hsing Chang, Her-Hsing Chang, } "Fast algorithm for color vector quantization", Proc. SPIE 2028, Applications of Digital Image Processing XVI, (20 October 1993); doi: 10.1117/12.158621; https://doi.org/10.1117/12.158621
PROCEEDINGS
10 PAGES


SHARE
RELATED CONTENT

Subband image coding using entropy-coded quantization
Proceedings of SPIE (June 01 1990)
Selection of the SPOT5 image compression algorithm
Proceedings of SPIE (October 03 1998)
Finite-state residual vector quantizer for image coding
Proceedings of SPIE (October 22 1993)
Improved block-matching algorithm considering edge components
Proceedings of SPIE (November 01 1990)
Lapped block decoding for vector quantization of images
Proceedings of SPIE (November 01 1992)

Back to Top