PHOTOPIX: A color image quantization system

PHOTOPIX: A color image quantization system
Alisson Augusto Souza Sol
Arnaldo de Albuquerque Araújo
DCC - Departamento de Ciência da Computação
UFMG - Universidade Federal de Minas Gerais
Caixa Postal 702
30.161-970 Belo Horizonte, MG, Brazil
{alisson|arnaldo}@dcc.ufmg.br
Abstract
This paper presents the results of some algorithms for color image quantization and the
system that implements them, using the "C++" language and the Microsoft Windows
application programming interface.
Keywords
Picture coding, color quantization, dithering, implementation, systems and applications.
Introduction
The right choice of spatial and spectral resolution is of primary importance for achieving
good quality in digitized images. Modern frame grabbers and scanners have made high
resolution, in both spatial and spectral spaces, available at very low cost, when compared to
the yet high prices of storage devices needed for big digital image databases.
Sampling a square photograph, with dimensions of 20 cm, using a 600 dpi (dots per inch)
scanner will result in more than 22 million pixels to deal with. Choosing to store a single byte
of spectral information about each pixel will generate a file greater than 22 Megabytes.
Professional systems, as those used in newspapers and magazines, require far greater spectral
resolution, usually 8 bits for each component of the RGB space. Therefore, there is an
increasing need of systems that can reduce the size of digital image files, with none or little
degradation of the image quality.
Compression algorithms
Traditional methods of digital file compression have been applied to image files, with very
different results, depending on the original image and the used algorithm.
Searching for correlation between adjacent bytes in the image file (corresponding to
adjacent pixels in the digital image) can produce high levels of file compression. This is
specially true for images with big areas showing the same color, or slow gradients between
extreme colors. However, the same technique can result in little or no compression at all, for
images where color changes abruptly. A big problem with this method is that the compressed
file can not be used without a decompression step.
Another approach to reduce the digital image file sizes is subsampling of the available
data. A common method of doing this is to reduce spatial resolution, storing only a single
spectral value for a set of N pixels in the original digital image. This method can produce
images with the aliasing effect, although antialiasing techniques can greatly reduce the
degradation in image quality [Newman (1981)]. However, for presenting the antialiased
image there is a need of devices with large spectral resolution.
Subsampling in the spectral space consists in reducing the number of bits used to store
data for each pixel. This method has predictable compression ratios and, using special
techniques, can lead to little image quality degradation. Thus, it becomes very interesting to
have a system that can reduce image file size by one or more of the known algorithms for
spectral quantization.
System description
The PHOTOPIX system implements uniform quantization, the popularity algorithm and the
median cut algorithm, all of which are fully described in [Heckbert (1982)].
Uniform quantization uses only the most significant bits of each color component to form
an index in a palette. At the palette, each component is represented by the value formed by
using that same bits in the most significant positions. The algorithm is very fast but can leads
to false-contour effects in the resultant images.
The popularity algorithm contructs the palette by serching the most frequent colors at the
original image. Then, the color at each pixel is mapped to the most similar palette color. This
method performs poorly on images were the original range of colors is much greater than the
size of the final palette. The performance is not very good when compared to uniform
quantization and editions at the original image can invalidate the previously constructed
palette, leading to the need of reapplying the method from the scratch to generate another
quantized representation of the original image.
In the median cut algorithm, the palette is formed by repeatedly subdividing the color
space into smaller rectangular boxes, with the criteria that each subdivision leads to two
boxes that encloses the same number of colors. After that, the color at each pixel is mapped to
the average of all the colors at the box were it is enclosed. The resultant image can be visually
very near the original one, specially when using dithering [Newman (1981)] to reduce the
average error. These same considerations about performance and editions at the original
image made for the popularity algorithm apply here.
Due to the vast hardware options available nowadays for image presentation, it has been
chosen to write a system that could be used in the broader possible range, without having to
be modified for each new video board. This leads to the search of an API (Application
Programming Interface). Among the options available, it has been chosen the Microsoft
Windows API, considering mainly hardware base and international support [Petzold (1990)].
Taking into account the programming tools, it was used the "C++" language for coding the
system [Dewhurst et al. (1989), Microsoft (1991)]. The use of MDI (Multiple Document
Interface) [Microsoft (1992)], makes possible simultaneous image display, easing
comparisons. The modular structure of the system will ease future migration to other APIs.
References
DEWHURST, S.C. & STARK, K.T., Programming in C++, Prentice-Hall, Inc., 1989
HECKBERT, P., Color image quantization for frame buffer display, ACM SIGGRAPH' 82
Proceedings
MICROSOFT CO., Class Libraries User's Guide, Microsoft C/C++ 7.0 manual, 1991
MICROSOFT, CO., The Windows Interface - An Application Design Guide, Microsoft Press,
1992
NEWMAN, W.M. & SPROULL, R.F., Principles of Interactive Computer Graphics, McGraw
Hill, 1981
PETZOLD, C., Programming Windows, 2nd. Ed., Microsoft Press, 1990