Share Email Print

Proceedings Paper

Fast algorithm for color vector quantization
Author(s): Long-Wen Chang; Her-Hsing Chang
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 20 October 1993
PDF: 10 pages
Proc. SPIE 2028, Applications of Digital Image Processing XVI, (20 October 1993); doi: 10.1117/12.158621
Show Author Affiliations
Long-Wen Chang, National Tsing Hua Univ. (Taiwan)
Her-Hsing Chang, National Tsing Hua Univ. (Taiwan)

Published in SPIE Proceedings Vol. 2028:
Applications of Digital Image Processing XVI
Andrew G. Tescher, Editor(s)

© SPIE. Terms of Use
Back to Top