A Colour Image Quantization Algorithm for Time-Constrained Applications



Many techniques have been proposed to quantize a digital colour image in order to reduce the representative number of colours to be suitable for presenting on different types of display screens. In addition, the techniques have been used to significantly reduce the amount of image data required to transfer over a communication network. Most of the published techniques are targetted for implementing on a general purpose multitasking computer with low restriction on time and resource utilizations. The drawback of these techniques relies on the fact that they cannot fulfill the requirement of some applications for real-time constraint and limited resources. In addition, most of the techniques are too complex for hardware realization. In this paper, an algorithm which is more suitable for time critical applications with an additional feature of simplicity to implement on FPGA (Field Programmable Gate Array) platforms is proposed and the details of its implementation and experimentation are presented. The dominate point of the proposed algorithm relies on the fact that it utilizes the weighted sum of the nearest distance along the axis under consideration, which is nontrivial to calculate, instead of the squared Euclidean distance to find the axis to split during. Also, the proposed algorithm has proved that by reducing the number of subspaces to be considered during the variance representative value calculation from 8 to 2 subspaces, the quality of quantized images are comparable to the previously proposed approaches. This makes it possible to further speed up the computational time of the quantization algorithm.


Image quantization, Image compression, Dynamic programming

Full Text:



Kurdthongmee W. Design and Implementation of an FPGA-Based Multiple-Colour LED Display Board. J of Microprocessors and Microsystems 2004; 29(7): 327-36.

Scheunders P. A Comparison of Clustering Algorithms Applied to Colour Image Quantization. Pattern Recognition Letters, 18 (1997), p. 1379-84.

Sirisathikula Y Auwatanamongkola S Uyyanonvara B. Colour Image Quantization Using Adjacent Colours> Line Segment. Pattern Recognition Letters 2004; 25(9): 1025-43.

Cheng SC Tang CK. A Fast and Novel Technique for Colour Quantization Using Reduction of Colour Space Dimensionality. Pattern Recognition Letters 2001; 22: 845-56.

Kanjanawanishkul K Uyyanonvara B. Novel Fast Colour Reduction Algorithm for Time-Constrained Applications. J of Visual Communication and Image Reconstruction, 2005; 16(3): p.311-32.

Hsieh IS Fan KC. An Adaptive Clustering Algorithm for Colour Quantization. Pattern Recognition Letters 2000; 21: 337-46.

Wu X. Colour Quantization by Dynamic Programming and Principle Analysis. ACM Transaction on Graphics, 1992; 11: 348-72.

Heckbert P. Colour Image Quantization for Frame Buffer Displays. J of Computer and Graphics 1982; 16(3): 297-307.


  • There are currently no refbacks.


Online ISSN: 2228-835X


Last updated: 2 August 2017