algorithm - LUT (ルックアップ テーブル) を反転する

Question

私はいくつかのカラー管理コードを書いており、LUT (ルックアップ テーブル) を扱っています。

カラー プロファイル LUT を読み取って値を変換することはできますが、逆の操作を行うにはどうすればよいですか? たぶん、LUT の「逆」を生成するための良いアルゴリズムはありますか?

Answer 1

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

ただし、画像内の滑らかな領域がエントリ間で突然移動するため、これは「ポスタリゼーション」画像になる傾向があります。これを回避するには、ピクセルを (準) ランダムな順序で取得し、LUT から最適なものを選択し、ピクセル値と選択したエントリの差を、まだ選択されていない近くのピクセルに押し戻します。

これを最後に行うにはさまざまな方法がありますが、それらはすべて、単純なピクセルごとの操作よりも、一般的に利用可能な LUT エントリを (画像化の目的で) より有効に使用するディザリング効果をもたらします。

Answer 2

はい、通常、関数が全単射であると仮定すると、ルックアップ テーブルを効率的に (線形時間で) 逆変換できます。ルックアップ テーブルが 2 つの異なるキーを同じ値にマップする場合、2 つの異なるキーにマップする値が必要になるため、テーブルを逆にする直接的な方法はありません。これで問題ない場合は問題ありませんが、逆マップを構築しようとしている理由が疑問視される可能性があります。

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