VGA Palette Mapping Using BSP Trees

A multidimensional cousin of the binary tree

Mark is a software engineer and C++ consultant for Semaphore Training in North Andover, Massachusetts. His interests include graphics, computer-game design and programming, and object-oriented technology. He can be reached at 76605,2346 on CompuServe, where he is a founding member of the Game Design SIG in the GAMERS forum, and can also be found inhabiting the C++ Study Group in DDJFORUM.

VGA and RGB Review

Color, as you know, is an analog phenomenon in nature that is only approximated by computer representations. The most popular digital representation uses the RGB color model, which specifies colors as a combination of three components: red, green, and blue. The classic RGB model uses the three axes of the Cartesian coordinate system to define a cube-shaped color space that contains all representable colors. Any given shade is located in this space via its RGB value, which serves as its coordinate, specifying a particular point location within the color cube. Figure 1 illustrates this space as inhabited by two sample points.

The VGA hardware on a PC directly makes use of an RGB representation. It uses 6 bits per R, G, and B component, forming a triplet of 18 bits total. A VGA palette consists of 256 18-bit registers. The bit width means each component has a range of 0 to 63, and thus determines a 3-D space of 262,144 (633) possible colors, of which any 256 are contained in a given palette.

Because the RGB model maps color values to a 3-D geometric space, we can speak of the "distance" between any two colors. This distance is calculated using the classic Euclidean formula, substituting RGB notation in place of the traditional XYZ values, as in Example 1. If the formula yields a result of 0, then two shades are the same. Otherwise, the smaller the result, the closer the two colors.

Mapping a given image's palette over to that of another image is straightforward: Step through each color in the source image and find the closest entry in the target image's palette by calculating the distance from each source element to every element in the target palette. This strategy works fine, but may prove computationally expensive for some applications. An easy first step in improving performance is to always use the squared values for comparison, rather than deriving the square roots. Still, more improvement is needed. If the set of target values is somehow ordered, then you can quickly reject points that are obviously not candidates, and avoid numerous distance calculations. Working with ordered sets takes us into the realm of range-searching algorithms.

Range Searching in Various Dimensions

A BSP tree is a binary tree in which the child nodes are sorted to the left and right of the parent based on their spatial relationship with the parent. If we apply a simple binary tree to the one-dimensional problem outlined above, then the result is a structure that should be familiar to anyone who has worked with binary trees in the past. The tree is constructed from the set by picking a middle value for the root node, and inserting the others to left and right based on a value comparison. When traversing a node in the tree, values lower than the current node's value go left, while those greater than or equal to it go right. Figure 2 shows the tree resulting from a hypothetical data set.

Locating the points in the tree that lie within the search interval requires a simple recursive traversal, recording nodes which fall within the interval, and discarding those that don't. At each node, if its value lies outside the search interval to the left, we travel down the tree to the right. Likewise, if it is outside the interval to the right, we move left. If the point lies within the interval we record it, and search both subtrees (since points on either side may lie within the interval as well). In general, a one-dimensional search using a structure of this type requires O(N logN) steps for preprocessing, and O(R+logN) for range searching, with R representing the number of data points actually falling within the range.

We can extend this approach for two-dimensional searches. As in the one-dimensional case, you insert all the points in the set into a tree, but this time you must maintain spatial relationships on two axes--simply by alternating the keys in strict sequence. For example, at level 0 of the tree (the level of the root node) compare points on the x axis, traversing the tree to the left for points to the right of the x axis range, and to the right for points to the left of it, exactly as before. At level 1 of the tree, follow the same rules, but compare points on the y axis, and so on, alternating the compare key with each level of the tree. Figure 3 shows what a typical 2-D BSP tree might look like after construction.

BSP Trees and the Color Cube

The Implementation

Listing One (page 94) presents the declaration of RGBBinTree, a class written in Borland C++ that builds and searches a three-dimensional BSP tree of RGB colors. In addition to its two constructors, the public interface of the class consists of three member functions. The first is the RGBBinTree::rgbMatch() function. Its arguments are the R, G, and B primaries of the color we're searching for, and an integer threshold value T which specifies the range in which we're going to look. The function returns the palette index of the best match found.

The second public-member function is the RGBBinTree::build() function. This function takes a set of RGB palette values as a parameter, and builds them into the BSP tree. It may be called at any time to create a new tree in the structure, but must be called at least once prior to performing a search. It is called by one of the constructors for this class.

The third public-member function is RGBBinTree::nodesVisited(), provided for analytical purposes. It returns the total number of nodes searched during the last lookup.

The complete code for this article (along with programmer notes) is not printed here but is available in electronic form; see "Availability," page 5.

Data Structures

The Algorithm

Now for the fun part: the implementation of the BSP tree algorithm. Listing Two (page 94) presents the file RGBTREE.CPP, which contains the member-function definitions for the RGBBinTree class. The first member function is the RGBBinTree::build() function, called by the application to construct a tree for a given instance. It first initializes the HEAD and TAIL nodes, which anchor the tree in the array. After the tree is built, HEAD's right child will point to the root node, and all leaf nodes will point to TAIL. RGBBinTree::build() then calls RGBBinTree::getMid() to find the palette register closest to the center of the color space (in this case, it looks for a palette register with RGB values of 31, 31, and 31). The midpoint color gets inserted into the tree as the root node, ensuring that subsequent node insertions will branch out as nicely as possible--a bushier, better balanced structure.

The function then inserts the rest of the palette colors into the tree. This is done in two For loops, which call RGBBinTree::insertNode() to link the node into the tree. The insertNode() function is passed a reference to a new pnode to be inserted, and an array index specifying an available slot in the array. As in any binary tree, insertion into a BSP tree is a matter of first conducting an unsuccessful search for the node to be inserted. Such a search terminates at a leaf node, and it is here that the new node is placed. In some cases nodes will match exactly, and for those instances I've adhered to the rule that exact matches go to the right child. The search for the insert location is performed in the single While loop in insertNode(), which continues until the current node being examined is TAIL, at which point it falls through to the actual linking in of the new node in the next block. Inside the While loop is the sequential key compare that is at the heart of the structure.

To control the alternating sequence of comparison keys in both insertNode() and rgbMatch(), I use a flag called colorf. This flag is incremented whenever the algorithm moves down a level in the tree, wrapping around to 0 when it exceeds 2. The value of this flag is used to index into the array of RGB color values in each node (a 3-byte array), so that it determines at each level which two colors will be compared. On entry into either function, the flag is set to --1, so that the first increment results in the starting state of 0.

At each node, the insertion loop compares the two colors selected from the RGB arrays in the nodes by the colorf flag, and applies the rules previously discussed: If the value of the node to be inserted is greater than or equal to the current node's value, then we traverse the tree to the right; otherwise, we traverse the tree to the left. In order to "remember" from which direction it arrived at the current node, the algorithm uses another flag called dirflag. This flag is 0 if the traversal was to the right, and 1 if it was to the left. After encountering the TAIL node (meaning the search was unsuccessful) the While loop falls through to the block which handles inserting the new node into the tree.

The next member function, RGBBinTree::rgbMatch(), is the most important of the class-interface functions. It is passed the RGB value to be searched for and an integer value specifying the search cube size, and returns the palette index of the best match for that color. The basic strategy is simple, even if the implementation appears complex. The algorithm performs a ranged search of the tree, exactly as described previously for one- and two-dimensional problems. Whenever a node is encountered which falls within the comparison interval, two things happen: First, the node index and the state of the colorf flag are pushed onto n_stack[], so that this point in the tree can be revisited later; second, the distance calculation is performed to determine the point-to-point distance of this RGB value from the desired one. If the results of this calculation are better (smaller) than the current best match, then the old match is replaced with the new.

The function first sets up an array of upper and lower boundaries for the compare interval. This array is arranged such that the colorf flag can select the appropriate range value for comparison automatically. Next, the function prepares for the tree traversal by pushing the starting node and colorf flag state onto n_stack[]. In this case the node pushed is HEAD, and the colorf value is --1.

We now arrive at the two nested While loops, which are the heart of the search algorithm. Again, the general idea is fairly simple: The outer While loop positions the algorithm at the top of a subtree (in the case of the first iteration, the subtree is the whole BSP tree) and runs until the stack is empty, indicating that all subtrees have been searched. The inner While loop traverses each subtree in turn and exits when a leaf node (TAIL) is encountered. Within the inner loop, the alternating key sequence is compared and distances are calculated for nodes encountered that fall within the search interval. All pushes of nodes onto the stack take place in the inner loop; all pops from the stack take place in the outer. Pushing a node is the inner loop's way of letting the outer loop know that there's an interesting subtree to be searched later.

How Well Does This Work?

Figure 1: The RGB color space, showing two points and the distance between them.

Example 1: The Euclidean distance formula in RGB space. D is the distance between points; R1 and R0 are R coordinates, G1 and G0 are G coordinates, and B1 and B0 are B coordinates of the two points, respectively.

Figure 2: Insertion of a one-dimensional set into a binary tree. Solid squares are null pointers.

Figure 3: Insertion of a two-dimensional set into a BSP tree. Color lines on the plane show the spatial partitioning resulting from alternating the comparison key. Symbols next to nodes in the tree diagram show which comparison key was used at that level.

[LISTING ONE]


/**********************************************************************
* RGBTREE.H -- header file for rgb palette sort and search functions
*  Copyright (c) 1993, Mark Betz, Derry NH. (603) 898-8214.
\**********************************************************************/

const PAL_SIZE = 768;                // number of bytes in palette
const DAC_SIZE = PAL_SIZE/3;         // size of DAC assuming 3 bytes/reg
const HEAD = 0;                      // index of the head node in tree
const TAIL = (PAL_SIZE/3) + 1;       // index of the tail node in tree
const ZIDX = -1;                     // invalid index

const R = 1;     // These consts control the order of
const G = 0;     // comparisons in the tree build and sort routines.
const B = 2;     // Default sequence is G, R, then B.

typedef unsigned char DACTBL[PAL_SIZE];  // generic array for palette values

class RGBBinTree                // the BSP tree class for sorting RGB values
{
   friend class ViewTree;       // ViewTree is a browser-like utility function
public:
   RGBBinTree();
   RGBBinTree( const DACTBL dacs ) { build( dacs ); }
   int rgbMatch( unsigned char r, unsigned char g, unsigned char b,int thold);
   void build( const DACTBL dacs );
   int nodesVisited() { return visitCnt; }
protected:
   struct pnode
   {  unsigned char c[3];
      int index, left, right;
   };
   RGBBinTree( const RGBBinTree& ) {};
   RGBBinTree& operator =(const RGBBinTree& ) {};
   int getMid( const DACTBL dacs ) const;
   void insertNode( const struct pnode& newn, int elem );
private:
   pnode pn[ DAC_SIZE+2 ];

   static int n_stack[ DAC_SIZE*2 ];
   static int n_sp;
   int treeBuilt;
   int visitCnt;
};

[LISTING TWO]

/**********************************************************************\
* RGBTREE.CPP -- implementation of RGBBinTree, a BSP tree for RGB space
* Copyright (c) 1993, Mark Betz, Derry NH. (603) 898-8214.
\**********************************************************************/

#include <stdlib.h>
#include <mem.h>
#include "rgbtree.h"

int RGBBinTree::n_stack[];      // definition of static members
int RGBBinTree::n_sp = 0;

// the default constructor does nothing but initialize member data
RGBBinTree::RGBBinTree() : treeBuilt(0), visitCnt(0) {}

//----------------------------------------------------------------------
void RGBBinTree::build( const DACTBL dacs )
{  struct pnode newn;                    // local node for insertions
   int i, j, di;                         // color index, generic counters
   int node = 1;                         // counts tree array elements

   pn[HEAD].index = ZIDX;                // initialize the head and tail...
   pn[HEAD].left  = TAIL;                //  nodes in the array
   pn[HEAD].right = TAIL;                // indices = -1, child nodes set...
   pn[TAIL].index = ZIDX;                //  to point to TAIL
   pn[TAIL].left  = pn[TAIL].right = TAIL;
   newn.left = 0;                        // don't use these, so zero them
   newn.right = 0;

   i = getMid(dacs);                     // find the color nearest the center
   j = i+1;                              // point j to the next color
   for (;i > ZIDX; i--)                  // insert the lower half of the dacs
   {  di = i*3;                          // color index = dac index * 3
      newn.c[R] = dacs[di];              // load the primaries into the node
      newn.c[G] = dacs[di+1];
      newn.c[B] = dacs[di+2];
      newn.index = i;                    // load the dac index into the node

      insertNode( newn, node );          // insert it into the tree
      node++;                            // increment to next node
   }
   for (;j < DAC_SIZE; j++)              // insert the upper half of the dacs
   {  di = j*3;                          // same procedure as above
      newn.c[R] = dacs[di];
      newn.c[G] = dacs[di+1];
      newn.c[B] = dacs[di+2];
      newn.index = j;
      insertNode( newn, node );
      node++;
   }
   treeBuilt = 1;                        // set treeBuilt to true
}
//----------------------------------------------------------------------
void RGBBinTree::insertNode( const struct pnode& newn, int elem )
{  int par = HEAD;                       // HEAD is the first parent node
   int cur = pn[HEAD].right;             // current node is HEAD's right chi.
   int colorf = -1;                      // color flag will be 0 on entry
   int dirflag = 1;                      // tracks direction of traversal

   pn[elem].c[R] = newn.c[R];            // load the data from the new node...
   pn[elem].c[G] = newn.c[G];            //  into the array at elem
   pn[elem].c[B] = newn.c[B];
   pn[elem].index = newn.index;
   pn[elem].left  = pn[elem].right = TAIL;

   while (cur != TAIL)                   // looking for first leaf node
   {
      par = cur;                         // the current node is new parent
      colorf == 2 ? colorf = 0 : colorf++;      // roll the color flag
      dirflag = 0;                              // clear the direction flag
      if (newn.c[colorf] >= pn[cur].c[colorf])  // if search color greater...
      {                                         // or equal...
         cur = pn[cur].right;            // go right, and set the dirflag
         dirflag++;
      } else cur = pn[cur].left;         // else go left, leave dirflag = 0
   }
   if (!dirflag)                         // based on dirflag, insert the...
      pn[par].left = elem;               //  new node as either the right...
   else                                  //  or left child of the parent
      pn[par].right = elem;
   return;
}
//----------------------------------------------------------------------
int RGBBinTree::rgbMatch( unsigned char r, unsigned char g,
                          unsigned char b, int thold )
{  int cur;                              // current node being visited
   register int dx = 3*63*63;            // best distance between colors
   int best = TAIL;                      // saves the current best match
   int t, rx, gx, bx;                    // used in distance calculation
   int colorf = -1;                      // color key compare flag
   int rng[3][2];                        // search range for each primary
   int key;                              // used in range comparisons
   if (!treeBuilt) return -1;            // bail if no tree built

   visitCnt = 0;                         // track nodes visited
   rng[0][0] = g-thold;                  // set up the comparison windows...
   rng[0][1] = g+thold;                  //  for the three primaries
   rng[1][0] = r-thold;
   rng[1][1] = r+thold;
   rng[2][0] = b-thold;
   rng[2][1] = b+thold;

   n_stack[n_sp++] = colorf;             // push the starting node and the...
   n_stack[n_sp++] = HEAD;               //  color compare flag

   while ((n_sp) && (dx))                // subtree loop runs until stack...
   {                                     //  empty or distance (dx) = 0
      cur = pn[n_stack[--n_sp]].right;   // pop the next node and compare flag
      colorf = n_stack[--n_sp];

      while ((cur != TAIL) && (dx))      // nodewalk loop runs till TAIL is...
      {                                  // hit or distance (dx) = 0
         visitCnt++;                     // increment nodes visited counter
         colorf == 2 ? colorf = 0 : colorf++;  // roll the compare flag
         key = pn[cur].c[colorf];        // get the current compare color
         if (key > rng[colorf][0])       // test against lower range
         {
            if (key <= rng[colorf][1])   // now test against upper range
            {
               n_stack[n_sp++] = colorf; // it's in the window, so push the...
               n_stack[n_sp++] = cur;    //  node and color flag

               rx = pn[cur].c[R];        // get the primaries from the node
               gx = pn[cur].c[G];
               bx = pn[cur].c[B];       // and calculate the point distance
               t = (rx-r)*(rx-r) + (gx-g)*(gx-g) + (bx-b)*(bx-b);
               if (t < dx)
               {                        // if it's smaller than the...
                  dx = t;               //  current best distance, save it.
                  best = cur;
               }
            }
            cur = pn[cur].left;          // node outside range to right...
         }                               //  or inside range
         else cur = pn[cur].right;       // node outside range to left
      }
   }
   return pn[best].index;                // return the best match
}
//----------------------------------------------------------------------
int RGBBinTree::getMid( const DACTBL dacs ) const
{  int i, rx, gx, bx;                    // counter, distance calc vars
   int t, best = 0, dx = 512;            // counter, best match, distance

   for (i = 0; i < PAL_SIZE; i+=3)       // look through the dac palette
   {
      rx = dacs[i];                      // get the currect set of primaries
      gx = dacs[i+1];                    // and see how far they are from ctr.
      bx = dacs[i+2];

      t = (rx-31)*(rx-31) + (gx-31)*(gx-31) + (bx-31)*(bx-31);
      if (t < dx)
      {                                  // if less than the current best...
         dx = t;                         //  distance, save the distance...
         best = i/3;                     //  and color index
      }
   }
   return best;                          // return the best match
}
End Listings