algorithm - 反转 LUT（查找表）

Question

我正在编写一些颜色管理代码，并且正在处理 LUT（查找表）。

我可以读取颜色配置文件 LUT 并转换我的值......但是，我该如何进行逆运算？也许，是否有一种很好的算法来生成 LUT 的“逆”？

Answer 1

如果您的 LUT 是给定的，最简单的方法是找到最接近任何给定颜色值的条目。您可以通过多种方法加速此计算；例如，您可以从 LUT 条目中构建一个 kd 树，并使用它来消除详尽检查所需的大部分比较。

但是，这往往会导致“分色”图像，因为图像中的平滑区域会突然从一个条目转移到下一个条目。您可以通过（准）随机顺序获取像素，从 LUT 中选择最适合的像素，并将像素值与所选条目之间的差异推回尚未选择的附近像素上，从而避免这种情况。

最后有多种方法可以做到这一点，但它们都会产生抖动效果，通常比简单的逐像素操作更好地利用可用的 LUT 条目（用于成像目的）。

Answer 2

是的，假设函数是双射，您通常可以有效地反转查找表（线性时间）。如果您的查找表将两个不同的键映射到相同的值，则没有直接的方法来反转表，因为您最终需要一个映射到两个不同键的值。如果您对此感到满意，那很好，尽管它可能会质疑您为什么要尝试构建反向地图。

如果您知道每个值都是唯一的，您可以构建一个逆向查找表，如下所示。首先，创建一个数据结构来保存从值到键的映射——如果值是小整数，可能是哈希表、平衡二叉树或原始数组。接下来，遍历查找表中的每个键/值对，然后将映射值 → 键插入到新的查找表中。这可以在线性时间加上将值插入新容器所需的时间完成。