介绍

查找调色板中与源图像中每个像素最近的颜色的Go-to方法是检查每个像素到每个调色板条目的距离，并使用距离最小的条目。这可以通过预先计算距离和缓存搜索结果等小技巧来加速，但最终结果仍然相当缓慢。您可以通过细分调色板颜色或仅检查最高n位来采取另一个步骤。虽然这两个选项都更快，但结果不太精确。细分将排除相邻空间中的颜色，并仅检查最高n位，本质上不太精确。对于本文，我选择了细分方法。但是为了尽可能精确而不慢，我们必须使最小的细分尽可能小——每个颜色通道一位。

背景

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

使用代码

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

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

原文地址：

转载地址：http://iizhj.baihongyu.com/

你可能感兴趣的文章