Colormap: A Color Image Quantizert Adam Rosen 87-845 June 1987 Department of Computer Science Cornell University Ithaca, New York 14853-7501 tThis work was supported in part by the National Science Foundation under grants DMC-8312096 and DCR-8502568 and the Office of Naval Research under contract N- 00014-86-K-0281. Colormap - A Color Image Quantizer "A picture is worth 1024 words. - Don Greenberg ABSTRACT This paper describes the Colormap program, designed and implemented for use in Cornell University's Computer Science Department. The purpose of Colormap is to quantize arbitrary 24-bit per pixel color images down to only 8 or 9 bits per pixel with minimal perceived image degradation. Uses for this include quantizing arbitrary pictures, mathematically generated images, ana images wnicn contain too many colors for display as a result of anti-aliasing. Uniform and adaptive techniques for generating the new color table are described, and then a 4-phase adaptive procedure for quantizing an image is presented. Factors including speed, accuracy, and complexity are examined in each phase, especially the construction of the color table and the mapping of these "representative" colors back upon the origal image. These factors are presented in the context of a main k-d tree data structure and the various color space dissimilarity measures employed. Dithering the resulting image is an option for reducing any noticeable contouring. Finally, some initial results are presented along with a comparison between the uniform and adaptive methods implemented. Specific information on running and modff?ring the Colormap program is contained in the appendices. 1. INTflODUCTION Color image quantization is the process by which color images (say those taken with a camera) are converted into a digital representation capable of being stored in a computer for later manipulation and display. It is helpful to think of the original image as consisting of an infinite number of points, each any possible colon Then the quantized image will consist of a fixed number of points, or pbcets, each with its color represented numerically jior image quantlzauon Is tfle Engineers way oi playing "color from a finite set of values. (`r by numbers." For the purposes of this paper and most discussions on the subject, it is assumed that the images are already originally quantized to 24 bits of color information per pixel - one 8-bit byte for each of the red, green, and blue (rgb) phosphors of the graphic display terminals. It is aiso assumed that there is no perceptible error in this original quantization. Color image quantization therefore usually refers to shrinkng the bits needed for each pixel by reducing the set of possible colors in the quantized Image. why would we want to decrease the bits/pixel if we already have a digitized image? The main reason for doing this is a hardware constraint: often the graphics screens can only hold 8 or 9 bits of color information per pixel. The goal of color image quantization is thus to take this input image and shrink the memory by about two-thirds to the mximum number of bits/pixel, allowing the image to be displayed. If the algorithms are chosen thoughtfully this quantized image can look almost identical to the original. (There are also the benefits of smaller memory requirements, especially if run-length encoding is used, and faster data transfer.) The resulting colors which are used in the quantized image are called the color representatives, since they are algorithm's choice of the Thest" subset of colors to represent the original image. Since there is no fast optimal solution to the color image quantization problem known (or multi?dimensional quantization problem), heuristic techniques are used to approximate the optimal Ill. The two general approaches use un(form and adaptive quantization methods. The uniform technique, as its nsme implies, uniformly truncates an apprmmnately equal number of bits from each of the three color components in the original pixel. This always results in a uniform spread of color component values, each separated by equal increments. For example, to quantize a 24-bit pixel down to 9 bits, 5 bits would be lopped off each of the red, green, and blue components. Note that since this is done inclepenclenuy of the color composition of the original image, it may perform particularly poorly if these colors are not uniformly distributed. If the colors occur in concentrated groups (a frequent possibility due to image/object coherence) many of the calculated color representatives will be unused! Uniform quantization has the advantage, however, of being conceptually simple and is straightforward to implement. Colormap can perform uniform quantization, useful as a basis for comparison with other quantization methods. Maptive quantizatiwi ?c:ch?nquc?, unlike uniform, attempt to somehow adapt the representative colors to the color distribution of the original image. Two important adaptive methods are the popularity algorithm and the median-cut algorithm [11. The popularity algorithm scans through all the image pixels and picks the N most often occurring or "popular" colors to be the representatives for the image. If one imagines the colors charted in a hist??gram form?t by ritirriber nf ocriirn?.nc? fnr each distinct color, then the popularity algorithm has the effect of choosing the colors from the densest regions of the distribution. Although this works well for many images, it functions poorly on images with a wide range of colors or when quantizing to a relatively small number of representatives because it ignores colors in sparse regions of the color space. 2 What is needed then is a method of considering all the colors m the orii?al image. The ?medlan-cut algorithm, developed by Paul Heckbert at NYIT, performs well in this regard because it chooses representative colors which vary widely in adapting to the input color distribution [11. Geometrically, the median-cut algorithm ftrst maps pixels into 3?llznensionaI color space along the red, green, and blue axes. Each axis extends from 0 to 255, as that is the range of the corresponding rgb component in a color potriL All of these color points are then enclosed in a 1)ox". which is shrunk to insure a snug fit against the outermost contained points. The box is then cut in half at the median along its greatest dimension (hence the name of the algorithm), these two boxes are shrunk to tightly enclose their points, each of these boxes is further split into two approximately equal sized smaller boxes. and so on recursively until we have 2n little boxes where n is the number of splits. The color points inside these boxes are then averaged to give tile desired 2" renresentative colors, which all the original pixels will be mapped to. Colormap uses the median-cut algorithm as part of the process of quanuzing an image. The total process is logically separated into four phases: sampling the image for color statistics. choosing the color representatives (median-cut), mapping the pixels to their closest renresentatives, and I?allv auantii:ng and redrawing the image. One faial concept should be discussed here. and that is the image data format and the graphics terminals the images are targeted for. A frame buffer is the hardware memory attached to graphics termirLals which holds the picture (frame) to be displayed. There are two types of frame buffers we wish to distinguish between: segregated and tritegrated. A segregated frame buffer is composed of three independent, segregated memories for the red, green, and blue components of the pixels. Each memory is usually about 8 bits deep. Thus, the composite values at each pixel make up a 24-bit color. An integrated frame buffer consists of a single memory array of pixels and a coloanap. Each pixel is no longer the color itself but rather an index into a lookup table of color values - the colormap (hence the clever name of the program). On a Vectrix terminal, for example. each pixel is 9 bits so the colormap may hold up to 512 colors. With n bits/pixel we can access any one of 2n colors in the colormap, and these 2n colors (24bit rgb) make up the entire, quantized image. Since every pixel now points to its representative color, we can instantly alter the entire image lust by cnanging tile corresnonding colors in the colormap. In either case, whether the colors are directly or indirectly specified. the resolution of the frame buffer in hx w pixels must be at least that of the image, while the depth in bits determines the number of colors to quantize to. Colormap takes as input a 24-bit/pixel rgb image and quantizes it down to n index bits/pixel (4.. 12, usually 8 or 9) with a 2? color colormap intended for an integrated frame buffen The image produced is in a generic data format, and an additional routine is used to encode it for the desired graphics terininal. 3 The remainder of this report is devoted to the relevant algorithms, data structures, cuinputational issues, and perceptual factors irwolved. The implementation of Colormap is based on work done by Heckbert [11, following his suggestion to use a k-d tree for untf?? the different phases of ule quantization process. Colormap also differs in that the initial prequantization is to 18 bits/pixel (rather than 15) for greater color resolution. To compensate for the resulting increase in comnutation. phases III and TV are combined so that the nearest neighbor search is only performed once for each distinct color used in the quantized image. The mathematical formulation of the color image quantization problem is discussed in Heckbert. The motivation for using k-d trees and iniormation on constructing, searching, and empirically analyzing them can be found in Friedman, Bentley, and Finkel 121. An analysis of various data structures for range searching can be found in Bentley and Friedman [31. Information on running the Colormap program is contained in the appendices. 2. THE QUANTIZATION PROCESS The two main steps in quantizing a color image are to choose the ?est" colors to be used, and to map all the different pixels to these colors. The total process is divided into three phases: I. II. III. Sample the input image to determine its color disributio? Determine the colormap based on this distribution. Redraw (quantize) the image by mapping the original 24-bit pixel colors to thefr closest color representatives (nearest neighbors) in the colormap. Perform dithering, if requested. The underlying data structure used to implement this is a K-D tree, or ?-th ?imensional binary search tree. A thorough explanation of k-d trees is presented in Friedman et al. [21, along with algorithms to build and search the trees and an analysis of thefr asymptotic complexity. The essential difference between a regular binary tree (i-dim.) and our k-dimensional k? tree is that the partition value stored at each node is now for any one of the k dimensions (here 3 dimensions - red, green, and blue). For example, mapping a pixel to its nearest representative in the color table (phase III) is now equivalert to searching the k-:l tree by comparing at each level in the tree the node's split dimension and value to the relevant red, green, or blue component of the query pixel. 4 The three quanuzation phases may now be thought of in terms of k-d trees: I. Sample the image to determine the color points to be indexed by the k-d tree. II. The leaves of the tree III. Construct an optimal" k-d tree based on these color points. point to the boxes which contain the color points. The points within each box are then averaged to deterline the corresponding color representative for that bo? Quantize the image by simply looking up each pixel in a mapping to iind the index of its color representative. If that particular pixel color has not yet been mapped. search the k-d tree for its nearest neI?bor in the color table. Phase I: Sampling th? Imag. In one pass over the input image. each pixel is prequantized to 18 bits by truncating the color components to 6 bits red. 6 bits green. and 6 bits blue. and the corresnonding slot in a color bit-vector is set to ?IRUE. As discussed in the sections on Dissimilarity Measures and Future Considerations, no "pixel count" is kept because all colors are weighted the same regardless of how many times they occur in the image. thereby not favoring popular colors over the more sparse ones. The prequantizatlon reduces the number of different colors to consider. and increases the frequency of use of the remainIng ones. This is important in that memory usage and processing time is proportional to the number of distinct colors that must be considered. With 18 bits the number of distinct colors will be under 256K (262.144). Note that the image itself has not yet been altered. only sampled. and the color sampling only takes into account 18 of the 24 bits of each pixel. If we were using uniform quanuzauon. we would merely prequantize" down to the desired bits/pixel and be finished. We will assume that the initial transformation from video signal to 24 bit/pixel image yields no perceptible quantization erto? such as contouring. off-colors. and the like. Empirical data also suggests that the prequantization to 15 bits results in mrnal image degradation if the colors in the colormap are chosen correctly 111. so the results for 18 bits should be as good if not better. This prequantized image will now be referred to as the o+original" image. In what follows we let Np = total number of pixels in the image. and Nc = number of distincL colors upon prequalitization. Processing time for phase I is then O(N?. 5 Phase II: Building the Color Table what is now desired is to find a Thest subset of colors to represent the colors in the original image, accordtng to some chosen dissimilarity measure D (discussed under Dissimilarity Measures). In the Colormap program D(ci.c? is the maximum coordinate distance function between the two color points ciand C2 Le. the absolute distance along the coorclinate of greatest range. We minimize quanUzation error by reducing this distance. The resulting subset of colors - the color representatives - is stored in the color table. Quan?ng to n bits/pixel allows us to access up to 2?dis??ct representatives. All the color points determined in phase I are mapped into 3-dimensional color space along the red, green and blue axes. The median-cut algorithm is then used to choose representative colors which adapt greatly to these color points. By enclosing all the points in a box, shrinking the box to tightly enclose them. splitting it into two along the median of the greatest dimension, shrinkg each one of those boxes and so on we cut in half the dimension of greatest quantization error each time [21. The data structures built in this phase and used throughout the quantization process are fflustrated on the following page. 6 main data structures used bu Colormap TheK-DTree Red n levels Red Green ?? colorbits) Re lu d leaves _________ (2" boxes) Internal ke?=RED _________ Nod. u?ition Boxes&theirColorPoints next 0 1 2 218?1 Colorpoint[OiIIII??..?11 012 + 218?1 colorpointlillIIII?I?? count Color start L.af keLEAF Nod. box fl (No child pointers needed since it?s a heap) bin 0 1 j 26?1 bin(j) = beginning of the thread of points ?hose rgb sorting component = With 6 bits in a component, 64 different values are possible. Box i: start - index of 1st colorpoint count - number of points y Boxillo+o+?(13) a Color consists of 3 by tes ColorTable . . (red, green, blue) O 1 I Tab ize--H1 ColorTable(i) = representative color for Box i TableSize = 2" different colors possible ?ith n colorbits Each Box points to a contiguous sequence of color points This represents a geometric "box" in 3D color space. 7 Perhaps this requires some ?cplanation! For starters, the motivation for these data structures is to provide both time and especially space efficiency in representing and manipulating the image data. Colorpoint consists of two identical arrays of 256K elements each, for holding and sorting all colors possible by the prequantization to 18 bits. Having two arrays allows a fast, simple bin sort since we need not copy the color points into bin queues - just thread them in place and copy groups of points bin by bin to the alternate array. Each color point consists of a red, green, and blue byte and has a slot associated with it in the next vector. The next vector is basically an array of indices which link related color points, although it serves different functions depending on which quantizatwn phase we are in. when sampling the image, these slots are used as boolean elements of a bit vector indicattng whether or not the color point represented by that index occurs in the image. When partitioning color space into finer and finer boxes, the next fields are used in conjunction with the bin array to implement an efficient 0(n) bin sort. When mapping pixels to thefr nearest representatives these slots contain the indices of the representatives in the colormap. Each record in the Box array represents one of the current boxes in rgb color space. It consists of a startng index and a count of the number of points in the box. As color points in a box are stored in contiguous memory locations, all we need to know is the box index number to have access to all the points contained therein. To split a box at its median we do the following. The longest dimension of the box is determined in one pass through its points by finding the maximum and minimum components along each of the red, gree?? and blue ax?. The points in the box are then sorted along this dimension. (The median is simply the middle element in the sorted sequence.) Splitting the box at its median is equivalent to dividing the sequence into two at this middle element: we add a corresponding record to the Box array to represent the latter half of the sequence, and adjust the count of the original Box record to represent only the first half of the sequence. The new" boxes each contain about half the points of the parent and are mutually exclusive of each other. To implement an efficient O(count) bin sort, the bin array and next vector are used to thread together (in one pass) points with identical components along the sorting dimension. Since each color component has been prequantized to 6 bits, an array of 64 bins will suffice. Once the points in the box are threaded, they are "sewn" (copied) bin by bin into the other Colorpotnt "run". The points in the box are now sorted along the desired dimension. In this manner each time the color space is recursively partitioned into twice as many boxes, 8 the color points physically alternate between the two coloipont runs. Thus we have a straightforward O(Nc) algorithm for determining the median of an array and rearranging the elements around it. Other time-efficient methods considered either required too much thought of the author [8i. or only gave approximations of the median 171 and further processing was required to rearmnge the elements. How does the k-d tree fit in to the picture (no pun intended)? in essence the k? tree is a history of the partitioning of color space, and the leaf nodes represent the current conflguratio? Each node in the tree contains a dimension key and a partition value along that dimension to record how a box is split. when a box is split in two. the split dimension (`RED'. `GREEN'. or `BLUEl and its value (the median) are stored as the node's key and partition value, respectively. These two smaller boxes are then the roots of the node's left and right subtrees. If the node is a leaf (no more splitting the box). the key equals `IZAF' and the partition value contains the index of the corresponding Box record. Since every internal node has 2 sons, the k-d tree is a complete binary tree and child pointers can be elinnnated via a hean renresentation. Friedman et al. refers to this as an optimized k-d tree, where the discriminating key is the dimension of greatest range, and the partition value is the median [21. The bucket size or number of points per box is determined indirectly by the user through the number of colorbits specified: number of points in a box = (number of color points Nc) I (2Colorbits) So, for exa?ple, with 9 colortits and Nc = a maximum 218 colors, we have at most 512 pixels perboL Spec!f?ing n bits per pixel means we recursively partition color space n times, resulting in 2fl boxes and n levels in the k-d tree. The points within each box are then averaged to give that box's color representative, stored in the ColorTable slot of the same index as the Box record. Every box therefore has an associated color representative which represents an equal number of Custirict pixels in the original image. This representative will be a full 24 bits long, but only 18 bits are s?gri1ficant as that was the degree of accuracy of the sampling in phase I. At each successive level in the tree, the color points are moved to alternating runs during the bin sort. Thus, the current and final runs are completely determined by whatever level we are at in the tree. It may be apparent at this point that the k-d tree is not really needed to partition up color space and determine the color representatives. However, in phase Ill the tree becomes a very efficient and convenient mechanism for mapping pixel colors to thefr nearest representatives in the color table. Gtven a color point, we can search down through the tree 9 and find the point's representative color in O(log Nc) time. Additionally, the overhead required to build the tree is minmal since the same processing must be pefformed to split up color space regaddless. let us, for fun, analyze the time and storage complexity required in phase II for the k? tree. At each level in the tree we must scan through and sort all points in every box, for O(Nc) time. Since there are at most log Nc levels, total asymptotic time to build the tree is 0(Nc10?c) In practice the number of boxes 2n is determined by the number of colorbits n, so construction time is bounded by O(n Nc) where n is usually around 8 or 9 (versus 18). This corresponds to the fact that each leaf represents a box containing many color points, not Just one, so fewer tree levels need to be built. Also. on many images the colors are not distributed across the entire spectrum, so Nc will often be it 218 Hence. simpler images are processed faster. The storage required for the k-d tree is O(number of boxes). Since every leaf corresponds to a box, there are B leaf nodes where B is the number of boxes. Then there are B- 1 internal nodes, for a total of 2B-1 nodes. As B = 2n (or Nc if there are fewer colors), storage for the tree is o(2fl+l). Pha? III: Quantizing Th? Image (Mapping pixels to the color table) In this final phase we map all the pixels in I Lg? the color table. ii'i9 effectively quantizes the image, our goal. the ? to thefrclosest renresentatives in To speed things up, after finding the nearest representative for a pixel we store its color table index in some kind of mapping. This way, future occurrences of that same pixel need not entail another search. The only cost of this is the memory required to hold a mapping of 218 possible pixel colors, a cost we avoid by using the (suspiciously) convenient next vector to hold these indices. Our upper bound for the number of searches is then the number of distinct colors in the image, N? where Nc ? Np depending on the resolution and color composition of the image. Total processing time for phase m is O(Np pixels + Nc searches a cost/search). The height x width array of pixel indices and 2fl entT? x 24-btt color table represent the image quantized to n bits per pixel, and will be passed to the integrated frame buffer for display. 10 TheNeaw?stN?hborSear?h How do we actually search the kd tree for a pixel's closest color representative (nearest neighbofl in the colormap, and what is the cost? Basically, we search the k? tree according to the red, green, and blue components of the pixel. At each successive level in the tree, the new node's partition value is compared to the pixel component corresponding to the dimension of split, and the appronriate subtree is recursivelv searched. It is useful to think of the accumulation of these partitions along the red, green, and blue axes as geometrically fonning the current tox?. Upon reaching a leaf, we know which box in color space contains the pixel. But merely using the color representative of the box containing the search color point is insufficient, as there may be closer representatives in other boxes! Geometrically the problem can be conceptualized as a ball (sphere) centered at the query point, with radius equaA w tne a1????W Detween trie query pomt anci me ciosest coior representative louna so far. If this ball is totally enclosed by the current box, then no other color renresentative can possibly be closer, and we are done. However, if the ball does not lit within the current box there may be a color representative in another box whose dissimilarity from the query point is smaller. The Bail W?thtri Box test [21 determines the dissimilarity from the query point to the closest side of the current box and compares it to the ball's radius. If the radius is greater, the Ball Within Box test fails and we must backtrack through the tree and search neighboring boxes. At any given node during the search we keep a record of the geometric boundaries delimited by that node. When searching a child node these boundaries are adjusted accordingly. If the Ball Within Box test fails for the closer child, we then test the further child before searching it to see if it can possibly contain a nearer color representative. This Box Ovedaps Bail test is done by calculating the distance to the closest side of that box. If this distance is less than the dissimilarity between the query color point and its nearest color representattve fotind so far, then the farther child may contain a closer representative and it is searched. When that is done the Ball Within Box test is again performed to see if we must back up still further in the tree. of course, the brute force way to do this ("laimbo" method) would be to search all the color representatives in the table each time and then to choose the one with the smallest dissimilarity from the query color point. This will work, but it is O(2n representatives) per search, for O(Nc2n) - O(Nc2) total. Friedman et al. has shown that for optimized k-d trees the amount ofbacktracking is independent of ille size Nc, so that at O(1ogN? per search the total pixel search time would be O(N?logN?). This is much better than exhaustive search, particularly since Nc may be on the order of 218 = 256K colors. 11 D(ss(milar(ty Measures mie shortest distance between two points) An important concept largely ignored thus far has been the actual dissimilarity measure employed - what it means for one 3-dimensional color point to be near another. Common mathematical metric distances to be considered are of the form [21: Dp(X1,X2)= [? 1x1(i)-x2(i)IP jlip i?1 [vector spece p-normsl of these, the most common are p = 1: taxicab or city block distance p =2: Euclidean distance p=oo: maximumcoordinatedistance=maxIx?(i)-x2(i)I f?r1??k The p = oo maximum coordinate distance function is used in Colormap, based on Derceptual Lactors and ease oL implementation, while the p=2 euclidean distance metric was used in Heckbert's implementation. Ideally we would like a perceptually based quantizer to determine the partitioning of color space, resulting color representatives, and nearest neighbors chosen. The maximum coordinate distance function approximates this by selecting the color coordinate of maximum dissimilarity. Reducing distance along this dimension gains the most color resolution, even though the resulting colors may be slightly off from the original. It is these relative color differences between pixels rather than the absolute color differences between images that we are more likely to perceive. While accounting for multiple occurrences of the same color point might make the color representatives closer to the original colors, this tends towards the popularity algorithm in that it doesn't give much weight to colors in sparse areas of the color space, decreasing color resolution in the quantized image. The maximum coordinate distance function is also straightforward to implement. Calculating Dp=co(Xi?2) entails choosing the maximum linear distance between xi and x2 along the three coordinate axes. Since Dp=oo ? Dp=2 (euclidean distance), a ball with radius determined by this dissimilarity measure wili in general be smaller than a ball with radius determined by euclidean distance. This results in fewer boxes searched. Tests conducted by Friedman et al. confirm this for database applications, and sinilar results are expected for the analogous nearest neighbor search in color space 121. The section on Future Considerations discusses other possible dissirrilarity measures. 12 When quantizing to only a few representative colors or with a poorly chosen colormap, contouring (color banding) in the resulting image can be quite noticeable. Such images can often be improved by dithering. Dithering attempts to compensate for the quantization error introduced at a pixel by trading its intensity resolution for neighboring spatial resolution. In the Floyd-Steinberg dithering method the quantization error at the current pixel is propagated to neighboring ptxels below and to its right (see Iii. [51, and 161). This allows us to quantize and dither the image in one top to bottom pass, with 3/8 of the quantization error distributed to the right pixel, 3/8 to the lower pixel, and 1/4 to the lower right pixel: ?tj 3/st 3/st p P 1+1, j i+1, j+1 t --H (r,g,b) quantization error at pixel Pjj --H [original pixel co1or1?? --H [color rePreSentabve]1? Since dithering alters the colors of successive pixels in the image, it is now possible that there are new colors which were not in the original image. In this case we have additional pixel colors to perform nearest neighbor searches on (Nc is effectively increased). Dithering will therefore somewhat lengthen the search time required in phase HI by that required to search for these additional colors. Conversely, depending on the color distribution of the image dithering may actually reduce the number of distinct colors in the quantized image. This would result in fewer searches. In any event, there is still the added 0(10 N? time to propagate pixel error. In practice this along with the additional nearest neighbor searching approxmately doubles the total processing time. Also note that even if every box contains exacUy one color point (the ideal partitioning of color space), the representative colors in the color table may not be identical to the -original colors of the image, because the sampling in phase I was only significant to 18 bits/pixel. Dithering against the original 24 bit/pixel image will therefore always have some effect, and may in some cases even hide contouring in the original image. 13 3. COMPLEXITY ANALYSIS number ofbits/pixel to quantize to (usually about 8 or 9). Then 2n is the number of boxes and hence the size of the color table. Np = number of pixels inthe image (eg. 322,560 fora 480x 672 screen). Nc = number of colors in the image after prequantization (max 218 = 262,144). The asymptotic time complexity of phase I is bounded by the pixel sampling, for O(Np). Constructing the k-d tree is incorporated into the cost of building the color table, which calculated to its full extent is 0(N?l0gN?) to index Nc color points. However, the tree is not actually built to that fine an indexing. only to the first n levels to give 2n boxes. Thus the time to build the k-d tree is 0(n Nc). Mapping pixels to their nearest representatives is proportional to logN? time per k-d tree search, for 0(Nclog?c). The time spent translating a pixel color to a color table index is constant, so in addition to the searches performed phase ffl also requires 0(1) time per pixel. Total processing time to quantize an image is therefore 0(N? + 0(nNc) + O(Np + Ncl0gNc) =0(2 Np + flNc + N?logN?) - O(max(Np. N?l0gN?)). Using typical values for n and N? this means that the time to quantize an image is 0(NIogN) with the number of (prequantized) colors in the image - a respectable speed considering the sorting and searching involved. Images with a narrow color distribution have an even faster processing time, proportional with the number of pixels (the best we could hope fofl. If dithering is performed, the constant factor here is somewhat increased due to the additional computation at each pixel but the asymptotic running time remains the same. in analyzug the space complexity of the given data structures, we ignore the minimum O(Np) memory necessasy to hold the image. The two most important structures in respect to size are the Colorpont I next arrays and the k-d tree heap. Since the Colorpoint runs and next vector are used to hold and manipulate the points, they require O(Nc) space. The Box array and CoLoil'oble each require 0(number of boxes B = 2fi) space, while the k- <# coloibits> Quantizes the input rgb tmagefile from 24 bits/pixel down to n colorbits per pixel using up to 2? colors. Outputs resulting pixel index and color table to the file tnc?geJUe.map in a generic format intended for an integrated frame buffen Options: ?u Unifo thetinec itis rm quan?auon. rgb color components of a pixel. Calculates the color table by uniformly truncating each of The resulting picture quality will usually be poor since the color table entries are calculated independently of the actual color distribution of the image. Mostly for comparison and debugging purposes; default auantization method is the median-cut algorithm. Dither image. Dithering attempts to compensate for the quantizatlon error introduced at a pixel by distributing it to neighboring pixels. Works best for a poorly chosen colormap (i.e. by uniform quantization), or when quantizing to only a few colors. -x Display status messages and color space statistics. Useful for debugging information and evaluating the quanLization. Inputfile: irnageftie Outputfile: imagefilamap Header Header Screen PixelIndex Arra? height, width must be preset TableSize must be zero Color ScreenArra? [height][width] (24 bit/pixel image) colors?sed is set b? program Tablesize = 2colorbits short PixelIndex(height](width] (indices into the ColorTable) ColorTable Color ColorTable[TableSize1 (colors in the quantized image) 18 The first co1ors?used slots in the CotorTable contain valid colors; the remaining [TableStze - colors?used) slots are set to black (0.0.0). See appendix B for relevant data structures Header and Color. The Header determines the status of Imagefile: file contains rgb ScreenArray. file contains Pixelindex and ColorTable. TableSize =0 on input: TableSize >0 on output: TableSize = -1 if error. On an input or processing error, the colormap program prints an appropriate message and halts. The output file is not created until the quantieed image is finished and about to be written to dis? If an 1/0 error occurs at this point, the write is halted (but TableSize is not currently set to -1 due to implementation difficulties). 19 Annendix B: Imniementatlon details The Quintintion Proce- Cai?ra [Initial Quantj Screen y = x Input ile 2? bits4izel Pro?rae to ?enerute i--Hge, Program configuration colormap.h - * * PIn?? * ? * Co lor?b 10 rorv-t Coloriap q?ntiz.r ?U?tiPtU???iil:i ;;:??j?? C?:P:ini:5i 2? ?olors ter1ina1 Global constants and data structures. Constants usually represent pa?ameter boundary condluons, and can be modified somewhat. ex: MINB? s n S MAXB? /0 number ofbits allowed per pixel0I The rel?ant data structures Header and Color of the ffle interface (app. A) are the following: typedef struct ( /0 Color components of a pixel 0/ uns?gried char red, green, blue; color; typedef struct height. width; unusedI4l; TableSize; colors?used; short char short short char reserved[41; char padli 121; Header; 20 /0 File header 0/ /0 of graphics screen 0/ /0 of resulting ColorTable 0/ /0 will be ? TableSize 0/ /0torna? 128byte50/ color favortttsm In uniform quantization, if the number of bits to quantize to is not a multiple of three, red gets the flrst ertra bit and green gets the next. For example, with 10 colorbits the rgb allocation will be (4,3,3), while with 11 bits it will be (4,4,3). For a fixed number of bits, this will affect the quality of quantization depending cloinnant color component?sj in Le original image, In median-cut, a tie on the tI?. for greatest dimension also favors red, then green, then blue. It may be desirable to alter these for perceptual reasons. MacMne De??endencies & Memory U??? An integer must contain at least 19 bits, to represent positive array indices o.,21&1 and ML (-1). Although MAxB? is currently set to 12 bits/pixel, it can be increased to allow the user up to 15 bits/pixel. Of concern are the large data structures and arrays which must be declared up to their mwdrnum possible sizes in relation to the program constants mentioned above. The memory requirements are the following: screerrrrray: 512 x 672 x 4 bytes each (aligned) - 1.3 M Colorpoint: next: Box: ColorTable: K-D ?e: 256Kx2x4bytes - 2M 25GKx4bytes- 1M 212x8bytes - 32K 212x4bytes - 16K 2(B=212)x4bytes - 32K The total runAime memory requirement is about 4.3 MB. iiixellndex is mapped onto sCreenA:rray, saving about 600K. 21 Relevant Terms adaptive partitioning - the partitioning of color space adapts to the input color distribution. box. hyperrectar?gLe - k-dimensional ab?uaction of the basic rectangle (here k = 3). Every (final) box in color space contains Nc I 2colorbits points, and has an associated color representative in the color table. colormap. coLor table - the 2colorbits x 2?bit table containing the color representatives for the image. This is the -best" subset of colors as determined by the median-cut algorithm. component the individual red. green, or blue values in a color point coordinate. With 6 bits a component can have 64 distinct values. The longest dimension of a box is equtvalent to the component of greatest range. coordinate - the (r, g. bi triple which represents a point in color space. An 18-bit (prequantized) triple will have 6 bits in each component. With 18 bits there are 256K different color points possible. dittweeg - averaging intensities of neighboring pixels to reduce visual contouring. frame buffer - hardware memory buffer connected to the graphics screen which holds the image being displayed. It is this limitation on the bit capacity per pixel?that necessitates color image quantization. k-;l u'? - k?? dimensional bmaiy search tree; dimensions (here red. green, and blue). partition at each node is along one of the k nearest neighbor, range searching - search for the closest representative color in color space. quantization - color by numbers. - red, green. and blue. Refers to the components of a pixel and the corresponding phosphors in a graphics screen. 22