本文共 5933 字,大约阅读时间需要 19 分钟。
目录
查找调色板中与源图像中每个像素最近的颜色的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/