Path: utzoo!attcan!uunet!epicb!david From: david@epicb.UUCP (David P. Cook) Newsgroups: comp.graphics Subject: Re: Palette Optimization Message-ID: <571@epicb.UUCP> Date: 20 Dec 88 13:40:37 GMT References: <12745@cup.portal.com> Reply-To: david@epicb.UUCP (David P. Cook) Organization: Truevision Inc., Indianapolis, IN Lines: 41 The simplest method of reducing a 24 bit colored image to a smaller set of colors is to do popularity reduction. This this method, count the number of unique colors in the 24 bit image, keeping track of their frequency (ie.. how many pixels are color #1, how many are color #2 etc..) Now... to reduce to your 56 required colors, only take the 56 most frequent colors from the original image. Scan the image converting each color to the closest color from the list of 56 reduced colors. This method has the drawback that it does not preserve small areas of color. For example, of you have an image which is mostly redish, but has small quantity of other colors (consider a photograph of a person with bright green eyes... the person is primarily redish but the eyes present a small area of green... an area we wish to preserve). To do this, you must go to a more complex method, commonly called Color Cube Compression (devised by Paul Heckbert). In this method, you determine the corners of the color space used by the image in question. This will give you a cube (if you have never seen a RGB color cube, consult Fundamentals Of Interactive Computer Graphics.. or any other computer graphics book) which sits somewhere within total RGB color space. Now, the method consists of subdividing the large color cube into (in your case) 56 sub cubes. This is accomplished by always dividing the cube along the LONGEST AXIES. The division point should be as close to 1/2 the frequency of the axies as possible. For example, if the longest side is the Black-To-Red side, than your first subdivision should be along this side... at the point where approximatly 1/2 of the black-to-red pixels are on the left of the division, and the other half are on the right of the division. This subdivison continues, EACH TIME WITH THE LONGEST AXIES (ie. the longest axies after the last subdivision) until you have 56 (in your case) sub-cubes. Now, average all the colors for each sub-cube such that you end up for an average color per sub-cube. Now... to convert your image, simply read each pixel in the original image... determine which sub-cube they exist in and replace that pixel with the average for the sub-cube. In this way, small areas of vastly differing colors may be preserved. The original article for this method may be found in SigGraph proceedings. -- | David P. Cook Net: uunet!epicb!david | | Truevision Inc. | "Sometimes I cover my mouth with | | Indianapolis, IN | my hand to tell if I'm breathing" | -----------------------------------------------------------