Click here to Skip to main content
14,271,826 members

Fast OctTree-Based Nearest Color Search

Rate this:
5.00 (5 votes)
Please Sign up or sign in to vote.
5.00 (5 votes)
25 May 2019CPOL
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:

// 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

  • 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)

Share

About the Author

dynamichael
United States United States
No Biography provided

Comments and Discussions

 
QuestionSomething to consider Pin
Gary R. Wheeler27-May-19 9:23
memberGary R. Wheeler27-May-19 9:23 
GeneralMy vote of 5 Pin
LightTempler26-May-19 1:58
memberLightTempler26-May-19 1:58 
PraiseCool! Pin
Member 1077716429-Nov-17 12:12
memberMember 1077716429-Nov-17 12:12 
GeneralMy vote of 5 Pin
PVX0076-Nov-15 14:55
memberPVX0076-Nov-15 14:55 
GeneralRe: My vote of 5 Pin
dynamichael7-Nov-15 19:44
memberdynamichael7-Nov-15 19:44 
Thanks! I'm glad you like it. The idea came to me while reworking some old oct tree quantization code of mine. It just dawned on me that since the oct tree can quickly navigate to colors within itself (which it attempts every time you add a color), and is arranged so that similar colors are near each other, that finding the closest color already in the tree would be fairly simple and fast... and it is! Smile | :)

Ha! While writing this reply, I just thought of something else that might speed it up: Have each parental node (levels 0 through 6) cache its own comparison results in order to minimize the number of times it needs to compare the distances of all its children. I'll have to think that through...

modified 25-May-19 21:42pm.

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.

Tip/Trick
Posted 4 Nov 2015

Stats

10.3K views
7 bookmarked