LUT（ルックアップテーブル）を反転する

Question

私はいくつかのカラーマネージメントコードを書いており、LUT（ルックアップテーブル）を扱っています。

私はカラープロファイルLUTを読んで値を変換することができます...しかし、逆の操作はどうすればできますか？多分、LUTの 'inverse'を生成する良いアルゴリズムはありますか？

Answer 1

はい、通常、関数がバイジェクションであると仮定して、ルックアップテーブルを効率的に（直線時間）反転することができます。ルックアップテーブルが2つの異なるキーを同じ値にマッピングする場合、2つの異なるキーにマップする値を持つ必要があるため、テーブルを反転する直接的な方法はありません。あなたがこれで大丈夫ならそれは問題ありませんが、逆マップを構築しようとしている理由は疑問です。

すべての値が一意であることがわかっている場合は、次のように逆ルックアップテーブルを作成できます。まず、ハッシュテーブル、バランスのとれたバイナリツリー、値が小さい整数の場合は生の配列など、値からキーへのマッピングを保持するデータ構造を作成します。次に、ルックアップテーブルから各キーと値のペアを繰り返し、マッピング値→を新しいルックアップテーブルに挿入します。これは、新しいコンテナに値を挿入するのに必要な時間を加えた線形時間で実行できます。

Answer 2

LUTが指定されている場合、最も簡単な方法は、任意の色の値に最も近いエントリを見つけることです。この計算は、さまざまな方法で高速化できます。たとえば、LUTのエントリからk-dツリーを構築し、これを使用して徹底的なチェックに必要な比較のほとんどを排除することができます。

しかし、イメージのスムーズな領域があるエントリから次のエントリへと突然シフトするため、これは「ポスタリゼーション」画像になりがちです。これを避けるには、ピクセルを（擬似）ランダムな順序で取得し、LUTから最適なものを選び、ピクセル値と選択されたエントリの差を、まだ選択されていない近くのピクセルに戻します。

これを行うにはさまざまな方法がありますが、ピクセル単位の単純な操作よりも一般的に使用可能なLUTエントリを（イメージングの目的で）使いやすくするディザリング効果があります。