Graphics Lab New York Institute of Technology ABSTRACT Algorithms for adaptive, tapered quant- ization of color images are described. The research is motivated by the desire to display high-quality reproductions of color images with small frame buffers. It is demonstrated that many color images which would normally require a frame buffer having 15 bits per pixel can be qua ntized to 8 or fewer bits per pixel with little subjective degradation. In most cases, the resulting images look significantly better than those made with uniform quant- ization. The color image quantization task is broken into four phases: i) Sampling the original image for color statistics 2) Choosing a colormap based on the color statistics 3) Mapping original colors to their nearest neighbors in the colormap 4) Quantizing and redrawing the original image (with optional dither). Several algorithms for each of phases 2-4 are described, and images created by each given. CR CATEGORIES: II.3.3 (Information Stor- age and Retrieval): Information Search and Retrieval - clustering; search process; 1.3.3 (Computer Graphics): Picture/Image Generation - digitization and scanning; display algorithms; 1.4.1 (Image Process- ing) : Digitization - quantization. General Terms: Algorithms. Additional Key Words and Phrases: dither. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 1982 ACM 0-89791-076-1/82/007/0297 $00.75 INTRODUCTION The power and versatility of frame buffers has created an increasing demand for them in industry, education, and the home. Most of these frame buffers are capable of displaying a static color image, yet many of them do not contain the amount of memory necessary to match the spatial and color resolution of the human eye. The eye is capable of distinguishing at least fifty thousand colors [15]. There- fore, it would take a frame buffer with at least ]5 bits per pixel to reproduce and display a color image with no noticeable contouring. On smaller frame buffers, contouring effects can become objectionable. One way to eliminate some of this quant- ization error is to employ the method of tapered quantization. The purpose of this paper is to explore techniques for color image quantization with the goal of high-quality image display on frame buffers. The Original Image Our input data are the red, green, and blue separations of a digitized color image. A typical form for the input image is a rectangular array of pixels each hav- ing 24 bits (8 bits per component). The color components are usually represented by numbers in the range [0,255]. If the original image is in this form, then strictly speaking it has already been quantized (when it was digitized from a video signal, for instance). We will assume that this initial quantization does not cause perceptible quantization errors. This will be the case if (a) the full gamut of RGB space is used, that is, if the digitization equipment is set up so that black is quantized to (r,g,b)=(0,0,0), white to (255,255,255), red to (255,0,0), etc. and (b) the 256 levels are approx- imately equally spaced perceptually. Given these conditions, we can regard the 24-bit original image as the "true" image. We will try to approximate it as closely as possible when we quantize. fig. 14:24 bit original image of "Surface" (the surface of the RGB color cube unrolled). fig. 15: popularity algorithm, 256 colors. fig. 16: median cut, 256 colors. fig. 17: median cut with dither, 256 colors. fig. 18: exploded view of 16 tapered quantization cells in the RGB cube. I’ve found the original paper describing algorithm used in pngquant, and worked on improving it.
kornel
oracle4engineer
mizdra
miu_crescent
tacck
ryder472
kakehashi
kitsuya0828
sansantech
abemii
niwatakeru
imai448
aki_iinuma
irinanazarova
csswizardry
tammyeverts
jonrohan
colly
morganepeng
pedronauck
chriscoyier
lara
aleyda
geoffreycrofte
