这种颜色量化算法的复杂性是多少？
几年前，当我写大学论文时，我开始考虑这个想法。这个想法是这样的 - 完美颜色量化算法将采用任意真彩色图片并将颜色数量减少到尽可能少的数量，同时保持新图像与原始图像完全无法区分肉眼。
基本上设置很简单 - RGB 立方体中有一组点（每个轴上有 0 到 255 个整数值）。您必须将这些点中的每一个点替换为另一个点，方式如下：
- 操作后的点总数尽可能小；
- 从原始点到替换点的距离不大于红、绿、蓝轴上的一些预定义常数 R、G 和 B（这些常数取自人眼的敏感度，通常可以由用户）。
我知道有许多颜色量化算法具有不同的效率，但它们主要针对将颜色减少到一定数量，而不是“在不违反这些限制的情况下尽可能减少颜色”。
另外，我希望算法能够真正产生绝对最小值，而不仅仅是“非常接近最小值”。
这是否可能无需耗时地全面搜索所有组合（对于任何真实图片都不可行）？我的直觉告诉我这是一个 NP 完全问题或更糟，但我无法证明这一点。
额外设置：将限制从常量 R,G,B 更改为函数 F(Rsource, Gsource, Bsource 、Rtarget、Gtarget、Btarget），如果映射正常则返回 TRUE，如果映射正常则返回 FALSE超出范围。
I started toying with this idea some years ago when I wrote my university papers. The idea is this - the perfect color quantization algorithm would take an arbitrary true-color picture and reduce the number of colors to the minimum possible, while maintaining that the new image is completely indistinguishable from the original with a naked eye.
Basically the setting is simple - you have a set of points in the RGB cube (from 0 to 255 integer values on each axis). You have to replace each of these points with another point in such a way that:
- The total number of points after the operation is as small as possible;
- The distance from an original point to the replaced point is no larger than some predefined constants R, G and B on each of the red, green and blue axis (these are taken from the sensitivity of the human eye and are in general configurable by the user).
I know that there are many color quantization algorithms out there that work with different efficiencies, but they are mostly targeted at reducing colors to a certain number, not "the minimum possible without violating these constraints".
Also, I would like the algorithm to produce really absolute minimum possible, not just something that is "pretty close to minimum".
Is this possible without a time consuming full search of all combinations (infeasible for any real picture)? My instincts tell me that this is a NP-complete problem or worse, but I cannot prove it.
Bonus setting: Change the limit from constants R,G,B to a function F(Rsource, Gsource, Bsource, Rtarget, Gtarget, Btarget) which returns TRUE if the mapping would be OK, and FALSE if it was out of range.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
根据您的定义，图片的结构（即像素如何组织）根本不重要，唯一重要的是 RGB 三元组的子集，它们作为像素值在图片中至少出现一次。设该子集为 S。您想要找到 RGB 三元组 E（编码）的另一个子集，使得对于 S 中的每个 s，E 中都存在一个对应的 e，使得 diff(s,e) <= 阈值，其中阈值是您对可接受的差异施加的限制和 diff(...) 将三元组距离减少为单个数字。
此外，您希望找到大小最小的 E，即对于任何 E' st |E'|<|E|，至少有一对 (s,e) 违反差异约束。
这个特定问题无法进行渐近复杂性评估，因为它只有有限的实例集。通过预先计算每个子集 S 的最小集合 E，可以在恒定时间内（理论上）解决它。子集 S 数量巨大，但数量有限，因此该问题不能归类为 NP 完全优化问题或任何问题。 因此，针对这个特定问题的算法的实际运行时间完全取决于您愿意容忍的预处理量。为了获得渐近复杂性评估，您需要首先概括问题，以便问题实例的集合严格无限。
Given your definitions the structure of the picture (i.e. how the pixels are organized) does not matter at all, the only thing that matters is the subset of RGB triplets that appear at least once in the picture as a pixel value. Let that subset be S. You want to find then another subset of RGB triplets E (the encoding) such that for every s in S there exists a counterpart e in E such that diff(s,e) <= threshold where threshold is the limit you impose on the acceptable difference and diff(...) reduces the triplet distance into a single number.
Additionally, you want to find E that is minimal in size i.e. for any E' s.t. |E'|<|E|, there is at least one (s,e) pair violating the difference constraint.
This particular problem cannot be given an asymptotic complexity assessment because it has only a finite set of instances. It can be solved in constant time (theoretically) by precalculating the minimum set E for every subset S. There is a huge amount of subsets S but yet only a finite number, so the problem cannot be e.g. classified as NP-complete optimization problem or anything. The actual run-time of your algorithm for this parcticular problem hence depends completely on the amount of preprocessing you are willing to tolerate. In order to get an asymptotic complexity assessment you need to generalize the problem first so that the set of problem instances is strictly infinite.
最优量化是一个 NP 难题（Son H. Nguyen，Andrzej Skowron — 实值属性的量化，1995）。
当您拥有比球体大的点簇，但点之间的距离小于球体半径时，预定义的最大距离并不会让事情变得更容易 - 那么您就有很多组合（因为每个选择球体的放置可能会取代所有其他球体）。不幸的是，这种情况在具有梯度的真实图像上经常发生（整个直方图成为一个巨大的簇并不罕见）。
您可以修改许多量化算法来选择簇的数量，直到满足一定的质量为止，例如，在 Median Cut 和 Linde–Buzo–Gray 中，当您达到质量限制时，您可以简单地停止细分空间。它不能保证它是全局最小值（即 NP 困难），但在 LBG 中你至少会知道你处于局部最小值。
Optimal quantization is an NP-hard problem (Son H. Nguyen, Andrzej Skowron — Quantization Of Real Value Attributes, 1995).
Predefined maximum distance doesn't make things easier when you have clusters of points which are larger than your sphere, but distances between points are less than sphere radius — then you have a lot of combinations (as each choice of placement of a sphere may displace all other spheres). And unfortunately this is going to happen quite often on real images with gradients (it's not unusual for entire histogram to be one huge cluster).
You can modify many quantization algorithms to pick number of clusters until certain quality is satisfied, e.g. in Median Cut and Linde–Buzo–Gray you can simply stop subdividing space when you reach your quality limit. It won't be guarantee that it's global minimum (that is NP-hard), but in LBG you'll at least know you're at local minimum.
以下是我如何解决这个问题的想法 - 不幸的是，这可能需要大量内存并且速度非常慢：
您创建一个 256x256x256 立方数据结构，其中包含一个计数器和一个“邻居”颜色列表。对于图像中发现的每种独特颜色，您都会增加该颜色周围球体半径内每个单元的计数器。球体的半径是您最初定义的最大可接受距离。您还可以将颜色添加到每个单元格的邻居列表中。
添加完所有独特的颜色后，您将循环遍历立方体并找到具有最大计数器值的单元格。将此颜色添加到您的结果列表中。现在再次循环遍历您的立方体，并从所有单元格中删除该颜色以及该颜色的邻居列表中的所有颜色，并在删除颜色时减少每个单元格的计数器。然后重复搜索最大计数器并删除，直到立方体中不再有颜色为止。
或者，如果相同的颜色在图像中出现的频率更高，也可以多次添加相同的颜色。不确定这是否会改善视觉效果。
Here's an idea how I'd go about this - unfortunately this will probably need a lot of memory and be very slow:
You create a 256x256x256 cubic data structure that contains a counter and a "neighbors" list of colors. For every unique color that you find in your image you increase the counter of each cell which is within the radius of a sphere around that color. The radius of the sphere is the maximum acceptable distance that you have defined originally. You also add the color to the neighbors list of each cell.
Once you have added all unique colors you loop through the cube and find the cell with the maximum counter value. Add this color to your result list. Now loop through your cube again and remove this color and all colors that are in the neighbors list of that color from all cells and decrease each cell's counter whenever you remove a color. Then repeat searching for the maximum counter and removing until no more colors are in the cube.
Alternatively once could also add the same color multiple times if it occurs more often in the image. Not sure if that would improve the visual result.