用于计算图像中唯一颜色数的算法

寻找一个足够快但仍然优雅的记忆.该图像是一个24bpp的System.Drawing.Bitmap.

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

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

此外,如果速度是一个主要问题,您不希望使用像GetPixel(x,y)这样的函数 - 而是尝试一次处理块(一次一行).如果可以,请获取指向图像内存开头的指针并使其不安全.

从来没有实现过这样的东西,但正如我所看到的,一个原始的实现:

对于24位图像,图像可能具有的最大颜色数是(2 ^ 24,图像的像素数)的最小值.

您只需记录是否已计算特定颜色,而不记录计数的次数.这意味着您需要1位来记录是否计算每种颜色.这是2MB的内存.遍历像素,在2MB颜色集映射中设置相关位.最后迭代颜色集映射计数设置位(如果你很幸运,你将有一个POPCNT指令来帮助这个).

对于较小的图像和较低的颜色深度,最好保留颜色表并计算图像中的每种颜色.

这里的大多数人都提出了可能会很快的解决方案(实际上只使用2 MB的内存可能是可以接受的,并且非常快;带散列的那个可能更快,但肯定会使用超过2 MB的记忆).编程总是在内存使用和CPU时间之间进行权衡.如果你愿意"浪费"更多内存,或者你可以通过"浪费"更多的计算时间来减慢结果,你通常可以更快地获得结果,但这通常可以保护你很多内存.

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

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

int num =(RED << 16)+(GREEN << 8)+ BLUE;

一旦你像这样排序像素(这意味着你已经在图像中重新排列它们),所有相同颜色的像素总是彼此相邻.因此,您可以只对图像进行一次迭代,并查看颜色变化的频率.例如,您将像素的当前颜色存储在(0,0),并启动一个值为1的计数器.下一步是转到(0,1).如果它与以前颜色相同,则无需执行任何操作,继续下一个像素(0,2).但是,如果不相同,请将计数器增加1并记住下一次迭代时该像素的颜色.

一旦你查看了最后一个像素(并且可能再次增加了计数器,如果它与第二个最后一个像素不同),则计数器包含唯一颜色的数量.

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

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