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).
<![CDATA[
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!
<![CDATA[
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.
<![CDATA[
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).
<![CDATA[
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.
<![CDATA[
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.
<![CDATA[
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.
<![CDATA[
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.
<![CDATA[
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!
<![CDATA[
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