algorithm - 这种颜色量化算法的复杂度是多少？

Question

几年前，当我写大学论文时，我开始考虑这个想法。这个想法是这样的 - 完美 颜色量化算法将采用任意真彩色图片并将颜色数量减少到尽可能少，同时保持新图像与原始图像完全无法区分肉眼观察。

基本上设置很简单——您在 RGB 立方体中有一组点(每个轴上从 0 到 255 个整数值)。您必须用以下方式用另一个点替换这些点中的每一个:

• 运算后的总点数越少越好；
• 从原始点到替换点的距离不大于红、绿、蓝轴上的一些预定义常量 R、G 和 B(这些取自人眼的灵敏度，通常为可由用户配置)。

我知道有许多不同效率的颜色量化算法，但它们主要针对将颜色减少到一定数量，而不是“在不违反这些约束的情况下可能的最小数量”。

此外，我希望该算法能够产生真正绝对最小值的可能性，而不仅仅是“非常接近最小值”的东西。

如果不耗时地全面搜索所有组合(对任何真实图片都不可行)，这是否可能？我的直觉告诉我这是一个 NP 完全问题或更糟的问题，但我无法证明这一点。

奖励设置:将常数 R、G、B 的极限更改为函数 F(R_source, G_source, B< sub>source, R_target, G_target, B_target) 如果映射正常则返回 TRUE，否则返回 FALSE如果超出范围。

Answer 1

根据您的定义，图片的结构(即像素的组织方式)根本不重要，唯一重要的是作为像素值在图片中至少出现一次的 RGB 三元组的子集。设该子集为 S。您想要找到 RGB 三元组 E(编码)的另一个子集，使得对于 S 中的每个 s，在 E 中存在对应的 e，使得 diff(s,e) <= threshold 其中 threshold 是限制您对可接受的差异施加限制，并且 diff(...) 将三元组距离减少为单个数字。此外，您想找到最小尺寸的 E，即对于任何 E' s.t. |E'|<|E|，至少有一对(s,e)违反差分约束。

这个特殊问题无法进行渐近复杂性评估，因为它只有有限的实例集。它可以通过为每个子集 S 预先计算最小集合 E 在恒定时间内(理论上)解决. 有大量的子集 S 但只有有限的数量，所以问题不能是例如归类为 NP 完全优化问题或任何问题。 您的算法针对这个特定问题的实际运行时间因此完全取决于您愿意容忍的预处理量。为了获得渐近复杂性评估，您需要首先概括问题，以便问题实例集严格无限。