Click here to Skip to main content
15,867,308 members
Articles / Multimedia / Image Processing
Tip/Trick

Fast OctTree-Based Nearest Color Search

Rate me:
Please Sign up or sign in to vote.
5.00/5 (5 votes)
25 May 2019CPOL2 min read 24.3K   8   11
Build an oct-tree from a color palette for a fast 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:

C#
// 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:

C#
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

  • 26th May, 2019: Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionWhose Color? Pin
sbarnes23-Jun-21 2:28
sbarnes23-Jun-21 2:28 
AnswerRe: Whose Color? Pin
dynamichael23-Jun-21 16:20
dynamichael23-Jun-21 16:20 
QuestionHaving trouble with a line of code. Pin
larry11821-Sep-19 13:05
larry11821-Sep-19 13:05 
AnswerRe: Having trouble with a line of code. Pin
dynamichael22-Aug-20 5:38
dynamichael22-Aug-20 5:38 
QuestionHaving trouble with a line of code. Pin
larry11821-Sep-19 13:05
larry11821-Sep-19 13:05 
QuestionSomething to consider Pin
Gary R. Wheeler27-May-19 9:23
Gary R. Wheeler27-May-19 9:23 
AnswerRe: Something to consider Pin
dynamichael22-Aug-20 5:42
dynamichael22-Aug-20 5:42 
GeneralMy vote of 5 Pin
LightTempler26-May-19 1:58
LightTempler26-May-19 1:58 
PraiseCool! Pin
Member 1077716429-Nov-17 12:12
Member 1077716429-Nov-17 12:12 
GeneralMy vote of 5 Pin
PVX0076-Nov-15 14:55
PVX0076-Nov-15 14:55 
This is amazing...Utterly amazing!! Thank you for publishing the article.
GeneralRe: My vote of 5 Pin
dynamichael7-Nov-15 19:44
dynamichael7-Nov-15 19:44 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.