7

寻找一个速度足够快且记忆犹新的。该图像是 24bpp System.Drawing.Bitmap。

4

10 回答 10

14

如果您需要一个确切的数字，那么您将不得不遍历所有像素。由于颜色的稀疏性，可能将颜色和计数存储在哈希中是最好的方法。

在散列中使用 Color.ToArgb() 而不是颜色对象可能也是一个好主意。

此外，如果速度是一个主要问题，您不想使用 GetPixel(x, y) 之类的函数——而是尝试一次处理块（一次行）。如果可以，请获取指向图像内存开头的指针并使其不安全。

于 2008-09-24T11:57:11.953 回答
11

以前从未实现过这样的东西，但正如我所见，这是一个原始的实现：

对于 24 位图像，图像可能具有的最大颜色数是（2^24，图像的像素数）的最小值。

您只需要记录一种特定的颜色是否被计数，而不是它被计数了多少次。这意味着您需要 1 位来记录是否计算每种颜色。那是2MB的内存。遍历像素，在 2MB 颜色集图中设置相关位。最后遍历颜色集映射，计算设置位（如果幸运的话，您将有一个 POPCNT 指令来帮助完成此操作）。

对于较小的图像和当然较低的颜色深度，您最好保留一个颜色表并计算图像中的每种颜色。

于 2008-09-24T12:00:23.130 回答
6

这里的大多数人都提出了可能会很快的解决方案（实际上，仅使用 2 MB 的解决方案在内存使用方面可能是可以接受的并且非常快；带有哈希的解决方案可能更快，但它肯定会使用超过 2 MB 的记忆）。编程总是在内存使用和 CPU 时间之间进行权衡。如果您愿意“浪费”更多内存，您通常可以更快地获得结果，或者您可以通过“浪费”更多计算时间来更慢地获得结果，但这通常可以为您节省大量内存。

这是迄今为止没有人提出的一种解决方案。它可能是内存消耗最少的那个（您可以对其进行优化，因此它几乎不会使用比将图像保存在内存中所需的更多内存，但是，图像将被更改，尽管您可能必须先复制它）。我怀疑它能否在速度上击败散列或位掩码解决方案，如果内存是您最关心的问题，那就太有趣了。

  1. 按颜色对图像中的像素进行排序。您可以轻松地将每个像素转换为 32 位数字，并且可以将 32 位数字相互比较，一个数字小于另一个数字，大于或等于。如果使用快速排序，则排序不需要额外的存储空间，除了额外的堆栈空间。如果您使用 Shellsort，则根本不需要额外的内存（尽管 Shellsort 会比 Quicksort 慢得多）。

    int num = (RED << 16) + (GREEN << 8) + 蓝色；

  2. 一旦你像这样对像素进行了排序（这意味着你在图像中重新排列了它们），所有相同颜色的像素总是彼此相邻。因此，您只需对图像进行一次迭代，即可查看颜色变化的频率。例如，您将像素的当前颜色存储在 (0, 0) 并使用值 1 初始化一个计数器。下一步是转到 (0, 1)。如果是和之前一样的颜色，什么都不做，继续下一个像素（0, 2）。但是，如果不相同，则将计数器加一并记住该像素的颜色以供下一次迭代。

  3. 一旦您查看了最后一个像素（并且可能再次增加计数器，如果它与倒数第二个像素不同），计数器将包含唯一颜色的数量。

无论解决方案如何，在任何情况下都必须至少迭代所有像素一次，因此它不会影响此解决方案比其他解决方案更慢或更快。该算法的速度取决于您可以多快按颜色对图像的像素进行排序。

正如我所说，当速度是你的主要音乐会时，这个算法很容易被击败（这里的其他解决方案可能都更快），但我怀疑当内存使用是你的主要关注点时它可以被击败，因为除了计数器之外，还有足够的存储空间来存储一种颜色和图像本身的存储空间，如果您选择的排序算法需要，它只需要额外的内存。

于 2008-09-24T16:03:23.653 回答
4 
var cnt = new HashSet<System.Drawing.Color>();

foreach (Color pixel in image)
    cnt.Add(pixel);

Console.WriteLine("The image has {0} distinct colours.", cnt.Count);

/ EDIT：正如Lou所说，由于实现的方式，使用而.GetArgb()不是Color值本身可能会稍微快一些。ColorGetHashCode

于 2008-09-24T12:01:47.760 回答
3

这里的大多数其他实现都会很慢。为了快速，您需要直接扫描线访问和某种稀疏矩阵来存储颜色数据。

首先我将描述 32bpp 的情况，它要容易得多：

  • HashSet：颜色的稀疏矩阵
  • ImageData：使用 BitmapData对象直接访问底层内存
  • PixelAccess：使用 int* 将内存引用为可以迭代的整数

对于每次迭代，只需对该整数执行 hashset.add 即可。最后看看 HashSet 中有多少个键，这就是颜色的总数。需要注意的是，调整 HashSet 的大小确实很痛苦（O(n)，其中 n 是集合中的项目数），因此您可能希望从构造一个合理大小的 HashSet 开始，可能类似于 imageHeight*imageWidth/ 4会很好。

在 24bpp 的情况下，PixelAccess 需要是一个字节*，并且您需要为每种颜色迭代 3 个字节才能构造一个 int。对于 3 组中的每个字节，首先向左移动 8 位（一个字节）并将其添加到整数。你现在有一个由 32 位 int 表示的 24bpp 颜色，其余的都是一样的。

于 2008-09-24T16:06:26.953 回答
2

您没有准确定义独特的颜色。如果您实际上是指真正唯一的代码值（而不是在视觉上相同），那么唯一确切的解决方案是使用其他答案中描述的技术之一实际计算它们。

如果您正在寻找视觉上相似的颜色，这确实很快会归结为调色板映射问题，您正在寻找 256 种最佳独特颜色来最接近地表示原始全动态颜色范围图像。对于大多数图像来说，当 256 种颜色选择得当时，一张从 24 位和多达 1600 万种不同颜色开始缩小的图像可以映射到只有 256 种独特颜色的图像，这真是令人惊讶。这些正确的 256 种颜色（对于本示例）的最佳选择已被证明是 NP 完全的，但也有一些实用的解决方案可以非常接近。搜索一个名叫万世杰的人的论文和基于他的工作的东西。

如果您正在寻找图像中代码值颜色数量的近似值，我会使用无损压缩方案来压缩图像。压缩率将直接与图像中唯一代码值的数量相关。您甚至不必保留压缩输出，只需沿途累积字节数并丢弃实际输出数据即可。使用一组示例图像作为参考，您可以在图像中的压缩比和不同代码值的数量之间建立一个查找表。同样，这最后一种技术虽然相当快，但肯定是一个近似值，但它应该具有相当好的相关性。

于 2008-09-24T12:28:35.683 回答
1

在现代显卡之前，当大多数机器以 256 调色板模式运行时，这是一个相当有趣的领域。处理能力和内存的限制只强加了一种可能对您有用的约束——因此搜索处理调色板的算法可能会发现一些有用的东西。

于 2008-09-24T11:59:42.897 回答
1

这取决于您要分析的图像类型。对于 24 位图像，您最多需要 2MB 内存（因为在最坏的情况下您必须处理每种颜色）。为此，最好使用位图（您有一个 2 MB 的位图，其中每个位对应于一种颜色）。对于可以在 O(#pixels) 中实现的高颜色计数的图片，这将是一个很好的解决方案。对于 16 位图像，使用此技术的位图只需要 8 kB。

但是，如果您的图片颜色不多，则最好使用其他颜色。但是你需要某种检查来指示你应该使用哪种算法......

于 2008-09-24T12:00:12.570 回答
1

图像中唯一颜色的最大数量等于像素数，因此从过程一开始就可以预测。使用 Konrad 提出的 HashSet 方法似乎是一个合理的解决方案，因为散列的大小不应大于像素数，而使用 JeeBee 建议的位图方法需要 512 MB 的 32 位图像（如果有 Alpha 通道，并且确定这有助于颜色的唯一性）

但是，HashSet 方法的性能可能比“每颜色位”方法的性能差 - 您可能想同时尝试这两种方法并使用许多不同的图像进行一些基准测试

于 2008-09-24T12:12:37.267 回答
0

现代流行的颜色量化实现使用八叉树数据结构。注意维基百科页面，内容非常好。八叉树的优点是内存有限，因此您可以对整个图像进行采样并决定您的调色板，而无需太多额外的内存。一旦您理解了这个概念，请点击1996 年 Dobb 博士的期刊文章源代码的链接。

由于这是一个 C# 问题，请参阅 2003 年 5 月的 MSDN 文章Optimizing Color Quantization for ASP.NET Images，其中包括一些源代码。

于 2008-10-31T15:27:15.627 回答