快速基于八叉树的最近颜色搜索

引言

寻找源图像中每个像素在调色板中最接近颜色的常用方法是检查每个像素到每个调色板条目的距离，并使用距离最小的条目。 可以使用一些技巧来加快速度，例如预先计算距离和缓存搜索结果，但最终结果仍然相当慢。 您可以更进一步，细分调色板颜色或仅检查最高的 *n* 位。 虽然这两个选项都更快，但结果精度较低。 细分将排除相邻空间中的颜色，而仅检查最高的 *n* 位本质上精度较低。 对于此提示，我选择使用细分方法。 但为了使其尽可能精确且不慢，我们必须使最小的细分尽可能小——每个颜色通道一位。

背景

幸运的是，八叉树已经存在了很长时间，并且旨在将颜色细分到每个颜色通道 1 位的空间。 由于这种设计，可以快速获取其中包含的共享每个颜色通道的相同前（最高）*n* 位的颜色。 例如，颜色 255,240,249 和 254,241,249 共享相同的 7 个高位，这意味着它们都将在同一级别 7 节点中找到。 假设 255,240,249 作为该节点的叶子存在，并且我们正在搜索最接近 254,241,249 的颜色。 然而，我们正在搜索的颜色并不作为叶子存在。 现在我们必须在所有叶子中搜索最接近的颜色。 幸运的是，该节点可以拥有的叶子的最大数量是 8，并且我们知道我们的颜色不是其中之一，这意味着我们必须对我们的颜色进行的比较次数最多为 7 次。 但是，如果我们正在寻找不同的颜色，并且只有前 4 位与调色板中的任何颜色匹配呢？ 那么我们必须搜索该节点子节点中包含的所有叶子。 但是，如果我们讨论的是搜索一个 256 色的调色板以找到最接近的颜色，并且我们的颜色显然不是其中之一（因为树会直接引导我们找到它），我们只需执行最多 255 次比较，而不是潜在的数千次。 所以我们真正做的是同样老的精度距离检查，但是使用八叉树来最大限度地减少它们的数量（以及可能的邻居排除）。

Using the Code

使用以下类非常简单。只需用源颜色的列表实例化该类，然后开始搜索

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

这是该类本身

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) );
        }
    }
}

历史

• 2019 年 5 月 26 日：初始版本