Fast OctTree-Based Nearest Color Search

Introduction

The go-to method for finding the nearest color in a palette to each pixel in a source image is to check the distance from each pixel to each palette entry, and use the entry with the smallest distance. This can be sped up using little tricks like pre-calculating distances and caching search results, but, in the end, the result is still rather slow. You can take another step by subdividing the palette colors or only checking the highest n bits. While both of these options are faster, the results are less precise. Subdividing will exclude colors in a neighboring space, and checking only the highest n bits is less precise by nature. For this tip, I've chosen to go with the method of subdivision. But for it to be as precise as possible without being slow, we must make the smallest subdivision as small as possible--one bit per color channel.

Background

Luckily, the oct-tree has been around for quite some time and is designed to subdivide colors down to a space of 1 bit per color channel. Because of this design, it's really quick to get to all the colors contained within it that share the same first (highest) n bits of each color channel. For example, the colors 255,240,249 and 254,241,249 share the same 7 high bits, meaning they will be both found in the same level 7 node. So let's say 255,240,249 exists as a leaf of that node and we are searching for the nearest color to 254,241,249. However, the color we are searching for doesn't exist as a leaf. Now we must search for the nearest color amongst all the leaves. Fortunately, the maximum number of leaves this node can have is 8, and we know that our color isn't one of them, that means the highest number of comparisons we'll have to make for our color is 7. But what if we're looking for a different color and only the first 4 bits matched any in our palette? Then we'd have to search through all the leaves contained in that node's children. But if we're talking about searching a 256-color palette for the nearest color, and our color clearly isn't one of them (because the tree would have led us right to it), we will only have to perform up to 255 comparisons instead of potential thousands. So what we're really doing is the same old precision distance check, but using the oct-tree to minimize the number of them (and of possible neighbor exclusions) as much as possible.

Using the Code

Using the following class is pretty straightforward. Simply instantiate the class with a list of source colors, and start searching:

// Get a list of the nearest colors in sourceColors to those in imageColors.
public Color[] GetNearestColors(Color[] sourceColors, Color[] imageColors) {
   Color[] ret = new Color[imageColors.Length];
   ColorFinder clfTmp = new ColorFinder(sourceColors);
   for(int i = 0; i < imageColors.Length; i++) {
      int iNearestColorIndex_i = clfTmp.GetNearestColorIndex(imageColors[i]);
      ret[i] = sourceColors[iNearestColorIndex_i];
   }
   return ret;
}

Here is the class itself:

public class ColorFinder {
    // Declare a root node to contain all of the source colors.
    private Node _nodRoot;

    public ColorFinder(Color[] sourceColors) {
        // Create the root node.
        _nodRoot = new Node(0, sourceColors);
        // Add all source colors to it.
        for(int i = 0; i < sourceColors.Length; i++) {
            _nodRoot.AddColor(i);
        }
    }

    public int GetNearestColorIndex(Color color) {
        int iTmp;
        return _nodRoot.GetNearestColorIndex(color, out iTmp);
    }

    private class Node {
        private int _iLevel;
        private Color[] _aclSourceColors;
        private Node[] _anodChildren = new Node[8];
        private int _iColorIndex = -1;

        // Cached distance calculations.
        private static int[,] Distance = new int[256, 256];

        // Cached bit masks.
        private static int[] Mask = { 128, 64, 32, 16, 8, 4, 2, 1 };

        static Node() {
            // precalculate every possible distance
            for(int i = 0; i < 256; i++) {
                for(int ii = 0; ii < 256; ii++) {
                    Distance[i, ii] = ((i - ii) * (i - ii));
                }
            }
        }

        public Node(int level, Color[] sourceColors) {
            _iLevel = level;
            _aclSourceColors = sourceColors;
        }

        public void AddColor(int colorIndex) {
            if(_iLevel == 7) {
                // LEAF MODE.
                // The deepest level contains the color index and no children.
                _iColorIndex = colorIndex;
            } else {
                // BRANCH MODE.
                // Get the oct index for the specified source color at this level.
                int iIndex = _GetOctIndex(_aclSourceColors[colorIndex], _iLevel);
                // If the necessary child node doesn't exist, create it.
                if(_anodChildren[iIndex] == null) {
                    _anodChildren[iIndex] = new Node((_iLevel + 1), _aclSourceColors);
                }
                // Pass the color along to the proper child node.
                _anodChildren[iIndex].AddColor(colorIndex);
            }
        }

        public int GetNearestColorIndex(Color color, out int distance) {
            int ret = -1;
            if(_iLevel == 7) {
                // LEAF MODE.
                // Return our color index.
                ret = _iColorIndex;
                // Output the distance in case the caller is comparing distances.
                distance = ( Distance[color.R, _aclSourceColors[ret].R] +
                             Distance[color.G, _aclSourceColors[ret].G] +
                             Distance[color.B, _aclSourceColors[ret].B] );
            } else {
                // BRANCH MODE.
                // Get the oct index for the specified color at this level.
                int iIndex = _GetOctIndex(color, _iLevel);
                if(_anodChildren[iIndex] == null) {
                    // NO DIRECT CHILD EXISTS.
                    // Return the child containing the closeset color.
                    int iMinDistance = int.MaxValue;
                    int iMinColor = -1;
                    foreach(Node nod in _anodChildren) {
                        if(nod != null) {
                            // Get the closeset color contained in the child node 
                            // and its distance.
                            int iDistance_nod;
                            int iColor_nod = 
                                nod.GetNearestColorIndex(color, out iDistance_nod);
                            // If the return color is the closest color found so far, 
                            // remember it.
                            if(iDistance_nod < iMinDistance) {
                                iMinDistance = iDistance_nod;
                                iMinColor = iColor_nod;
                            }
                        }
                    }
                    // Return the closest color index found and output its distance.
                    ret = iMinColor;
                    distance = iMinDistance;
                } else {
                    // DIRECT CHILD EXISTS.
                    // Return its closest color and distance.
                    ret = _anodChildren[iIndex].GetNearestColorIndex(color, out distance);
                }
            }
            return ret;
        }

        private int _GetOctIndex(Color color, int level) {
            // Take 1 bit from each color channel 
            // to return a 3-bit value ranging from 0 to 7.
            // Level 0 uses the highest bit, level 1 uses the second-highest bit, etc.
            int iShift = (7 - level);
            return ( ((color.R & Mask[level]) >> iShift     ) |
                     ((color.G & Mask[level]) << 1 >> iShift) |
                     ((color.B & Mask[level]) << 2 >> iShift) );
        }
    }
}

History

• 26^th May, 2019: Initial version