Palettes, Care and Feeding Thereof


Copyright Dr. William T. Verts April 10, 1996
This document contains some notes on how to handle palette (color tables) for several examples, including monochrome images, VGA 16-color images, and 256 color images. Since file formats such as .GIF have a maximum limit of 256 palette entries, we are going to enforce the same limitations here. Any greater number of colors, and we might as well use the full 24 bit color!


Basic Type Definitions
I don't know how you will set up your data structures, but here are some suggestions for the color type and palette. I decided to bundle the palette array itself (Table) with a value (Top) which indicates how many entries in the array are valid. When the array is empty, Top will be -1. Top has a maximum value of 255 (the biggest value you can get in a byte). Type Color_Type = Record Red : Byte ; Green : Byte ; Blue : Byte ; End ; Palette = Record Table : Array [Byte] Of Color_Type ; Top : Integer ; End ;
Initialization of Palette
This routine clears all entries in the palette, and sets the Top to -1 to indicate that no entries are valid. Technically, you can get away with simply settig Top to -1, and forget about nuking the table entries, but many years of professional paranoia has taught me to never leave a data structure undefined or containing some other routines' leftovers in it! Procedure Clear_Palette (Var P:Palette) ; Var I : Byte ; Begin For I := 0 To 255 Do With P.Table[I] Do Begin Red := 0 ; Green := 0 ; Blue := 0 ; End ; P.Top := -1 ; End ;
Detecting if a Color exists in a Palette.
The routine returns the index of the color, if found, and returns -1 if not. There are a couple of ways to implement this search (which has to be some variant of linear search, since the entries in the table are unordered).

The first version of Find_Color uses "Standard" Pascal, and requires a Boolean flag to stop the loop when an exact match is found. The loop runs from Top down through 0, and on to -1 if no match is found.

Function Find_Color (P:Palette ; R,G,B:Byte) : Integer ; Var I : Integer ; Found : Boolean ; Begin Found := False ; I := P.Top ; While (I >= 0) And Not Found Do If (Table[I].Red = R) And (Table[I].Green = G) And (Table[I].Blue = B) Then Found := True Else I := I - 1 ; Find_Color := I ; End ; The second version of Find_Color is a little more efficient, but depends on the implementation of Pascal having a non-standard "Exit" command which returns immediately from the routine. CodeWarrior Pascal does have an "Exit", but you must also indicate what it is that you are exiting from; in this example it would be Exit(Find_Color). Function Find_Color (P:Palette ; R,G,B:Byte) : Integer ; Var I : Integer ; Begin For I := 0 To Top Do If (Table[I].Red = R) And (Table[I].Green = G) And (Table[I].Blue = B) Then Begin Find_Color := I ; Exit ; End ; Find_Color := -1 ; (* No Match *) End ;
Finding the Index to the Closest Color
If you have a 24 bit color, and you want to find the index into the palette that has the closest color, you are effectively computing the Euclidean distance between your color and each entry in the table. However, you do not have to compute the true distance (square root of the sum of the squares of the differences), but instead you can compute square distances to avoid the expensive square root operation. The other thing to watch out for in this routine is the fact that on some systems, squaring a byte value can return a bad value unless you cast the byte to a large enough integer type. On the PC, for example, the Integer type is 16 bits, which is not big enough for the job. Neither, unfortunately, is the Word data type, which is a 16 bit unsigned integer. The solution as presented here uses the LongInt type, which is a 32 bit signed integer. Plenty big enough. Code below can be optimized to break the loop whenever a distance of zero (exact match) is found. Function Find_Closest_Color (Var P:Palette ; R,G,B:Byte) : Integer ; Var RR, GG, BB : LongInt ; Save_Index : Integer ; Save_Distance : LongInt ; Distance : LongInt ; I : Integer ; Begin RR := LongInt(R) ; (* Type cast (could have been simply RR := R) *) GG := LongInt(G) ; BB := LongInt(B) ; Save_Index := -1 ; Save_Distance := MaxLongInt ; (* Very big value *) With P Do For I := 0 To Top Do Begin Distance := Sqr(LongInt(Table[I].Red ) - RR) + Sqr(LongInt(Table[I].Green) - GG) + Sqr(LongInt(Table[I].Blue ) - BB) ; If Distance < Save_Distance Then Begin Save_Distance := Distance ; Save_Index := I ; End ; End ; Find_Closest_Color := Save_Index ; End ;
Adding a Color to the Palette
If it does not already exist, and if the table is not already full, then the new color is added to the end of the list. Procedure Add_Color (Var P:Palette ; R,G,B:Byte) ; Begin If Find_Color(P, R, G, B) < 0 Then With P Do If Top < 255 Then Begin Top := Top + 1 ; Table[Top].Red := R ; Table[Top].Green := G ; Table[Top].Blue := B ; End ; End ;
Setting a Palette to Monochrome A Monochrome palette with contain two values, one for pure black and one for pure white. Notice that you can reverse the figure and the background of an image by simply switching the palette entries in the table. Procedure Monochrome (Var P:Palette) ; Begin Clear_Palette (P) ; Add_Color (P, 0, 0, 0) ; Add_Color (P, 255, 255, 255) ; End ;
Setting a Palette to VGA (16 Color)
This routine sets up a 16 color palette to match the standard colors and order of colors of the IBM-PC. Procedure VGA_16 (Var P:Palette) ; Begin Clear_Palette (P) ; Add_Color (P, 0, 0, 0) ; (* 0: Black *) Add_Color (P, 0, 0, 192) ; (* 1: Blue *) Add_Color (P, 0, 192, 0) ; (* 2: Green *) Add_Color (P, 0, 192, 192) ; (* 3: Cyan *) Add_Color (P, 192, 0, 0) ; (* 4: Red *) Add_Color (P, 192, 0, 192) ; (* 5: Magenta *) Add_Color (P, 192, 192, 0) ; (* 6: Brown *) Add_Color (P, 192, 192, 192) ; (* 7: LightGray *) Add_Color (P, 128, 128, 128) ; (* 8: DarkGray *) Add_Color (P, 0, 0, 255) ; (* 9: LightBlue *) Add_Color (P, 0, 255, 0) ; (* 10: LightGreen *) Add_Color (P, 0, 255, 255) ; (* 11: LightCyan *) Add_Color (P, 255, 0, 0) ; (* 12: LightRed *) Add_Color (P, 255, 0, 255) ; (* 13: LightMagenta *) Add_Color (P, 255, 255, 0) ; (* 14: Yellow *) Add_Color (P, 255, 255, 255) ; (* 15: White *) End ;
Building a 256 color Palette
This is only one of many methods of constructing a 256 color palette. Here we don't know anything about the structure of the image that we are trying to capture, so we hedge our bets by attempting to make the palette be as general as possible. This means that we will include the VGA colors, try to evenly cover color space, have some extra gray values, and have a cloud of color around the gray diagonal axis. I make no claims that this is the best technique of generating a 256 color palette! Procedure Palette_256 (Var P:Palette) ; Var R, G, B, I : Byte ; Begin (************************************************************) (* Clear P, then load in the first 16 colors in the *) (* first 16 locations of the palette (keeps Windows happy!) *) (************************************************************) VGA_16 (P) ; (************************************************************) (* Add in a 6x6x6 cube of colors, evenly distributed in *) (* the color space. This potentially adds 216 new colors, *) (* but since 8 are already present from VGA_16, we are *) (* adding 208 new colors. We will have 208+16=224 entries *) (* in the palette afterwards. *) (* The 51 is a magic number, such that 5*51 is exactly 255! *) (************************************************************) For R := 0 To 5 Do For G := 0 To 5 Do For B := 0 To 5 Do Add_Color (P, R*51, G*51, B*51) ; (************************************************************) (* We have 31 entries left in the table. This section fills*) (* entries with gray scale levels, again evenly distributed *) (* along the diagonal axis. Of the 18 new gray levels, 2 *) (* already in use (0,0,0) and (255,255,255), so we are *) (* adding 16 new ones, for a total of 240. 16 to go! *) (* The 17 and 15 are magic numbers such that 17*15=255! *) (************************************************************) For I := 0 To 17 Do Add_Color (P, I*15, I*15, I*15) ; (************************************************************) (* In this section we are going to add some colors evenly *) (* distanced from the center (gray) line, but extending into*) (* the colored regions by only a small distance. This is to*) (* approximate the fact that "most" .GIF images I've ever *) (* seen have had all palette entries in a cloud around the *) (* diagonal gray line. This block uses up 15 of the 16 *) (* remaining colors. *) (************************************************************) For I := 1 To 5 Do Begin Add_Color (P, I*42-21, I*42 , I*42 ) ; Add_Color (P, I*42 , I*42-21, I*42 ) ; Add_Color (P, I*42 , I*42 , I*42-21) ; End ; (************************************************************) (* Put the remaining entry somewhere on the gray line! *) (* Your choice! *) (************************************************************) Add_Color (P, 250, 250, 250) ; End ;
Adaptive Palette
Watch this space! I'll try to add some thoughts on how to create an adaptive palette in the near future. This would be a case where you pass all the colors in an image against a filter to determine the 256 "best" palette entries.


Back to the CS 32 Page

Back to Dr. Bill's Page