(57)【要約】  例えば、カラープリンタの色域を向上するために使用する追加インクを有するCMYKカラープリンタなど、多数の入力チャネルを有するカラーデバイスに有用な色変換方法および装置に関する。色変換は、n次元の色空間を低次元の部分空間の集合に階層化するルックアップテーブル(LUT)の階層集合体を用いて実行される。低次元の部分空間に関連するLUTは閉じていてもよく、高次元の部分空間に関連するLUTは、LUTによって囲まれない部分空間にギャップを残した状態で開いていてもよい。色変換に階層集合体を用いる色管理モジュール(CMM)は、ギャップにはまる色値の色変換かを判定する。そのような色値の色変換の場合、CMMは相対的に複雑な補間処理を用い、そうではない場合、CMMは相対的に簡単な補間処理を用いる。ある補間処理において、入力値を囲む単位超立方体は、LUTの値に基づき生成される。そして、境界条件の集合が単位超立方体に課される。実際の補間を行うため、単位超立方体の選択された頂点から入力値を介して単位超立方体の境界へ、最初の重心投影が行われる。投影が境界条件の一つを満たす場合、その投影を用いる後退代入により、補間値が計算される。最初の投影が境界条件を満たさない場合、投影が境界条件の一つを満たすまで、前の投影から中間値が生成され、単位超立方体の異なる頂点を使用し、中間値を介して単位超立方体の境界へ、引き続き重心投影が行われる。そして、最初の投影と続く投影を用いる後退代入により、補間値が生成される。
2008533764.tif 000002
【特許請求の範囲】
【請求項１】
色空間の補間値を決定する方法であって、
入力値を包囲する単位超立方体を生成し、
前記単位超立方体に境界条件の集合を与え、
投影が前記境界条件の一つを満たすまで、前記単位超立方体の異なる頂点から前記入力値を介して前記超立方体の境界へ重心投影を行い、
前記重心投影を用る後退代入によって前記補間値を決定する方法。
【請求項２】
前記境界条件は離散境界条件を含む請求項1に記載された方法。
【請求項３】
前記離散境界条件は前記単位超立方体の頂点に関連する請求項2に記載された方法。
【請求項４】
前記境界条件は連続境界条件を含む請求項1に記載された方法。
【請求項５】
前記連続境界条件は前記超立方体の面に関連する請求項4に記載された方法。
【請求項６】
前記境界条件は、前記単位超立方体の一つ目の面に関連する一つ目の連続境界条件と、前記単位超立方体の二つ目の面に関連する二つ目の連続境界条件を含み、
前記連続境界条件は、前記一つ目の面と前記二つ目の面の交差において一致する請求項1に記載された方法。
【請求項７】
さらに、前記入力値を囲む単体を決定し、
前記単体は前記超立方体により包囲され、
前記単体の頂点を使用して重心投影を行う請求項1に記載された方法。
【請求項８】
さらに、前記単位超立方体の異なる頂点から中間の値を介して前記単位超立方体の境界へ重心投影を行い、前記中間の値は前の重心投影から決定される請求項1に記載された方法。
【請求項９】
コンピュータが読み取り可能な媒体に記憶され、かつ、色空間の補間値を決定するために実行可能なコンピュータが実行可能な命令であって、
入力値を包囲する単位超立方体を生成し、
前記単位超立方体に境界条件の集合を与え、
投影が前記境界条件の一つを満たすまで、前記単位超立方体の異なる頂点から前記入力値を介して前記超立方体の境界へ重心投影を行い、
前記重心投影を用いる後退代入によって前記補間値を決定するコンピュータが実行可能な命令。
【請求項１０】
色空間の補間値を決定する装置であって、
入力値を囲む単位超立方体を生成する生成手段と、
前記単位超立方体に境界条件の集合を与える手段と、
投影が前記境界条件の一つを満たすまで、前記単位超立方体のそれぞれ異なる頂点から前記入力値を介して前記超立方体の境界へ重心投影を行う実行手段と、
前記重心投影を用いる後退代入により前記補間値を決定する決定手段とを有する装置。
【請求項１１】
n次元の色空間における単位超立方体に亘り、かつ、各LUTは前記n次元の色空間から第二の色空間へ写像する、LUTの集合を生成する方法であって、
k=3からnである各次元kについて、n個からk個を選択するLUTの階層集合体を定義し、各LUTはk個の入力を有し、少なくとも幾つかのLUTは他のLUTと異なる格子の構造を有し、高次元のLUTの前記格子の構造の密度を低次元のLUTよりも低くして、前記n次元の色空間における階層集合体の集合を定義し、
前記第二の色空間の値を使用して、前記LUTを表す方法。
【請求項１２】
k=3の場合、各LUTは閉じている請求項11に記載された方法。
【請求項１３】
前記各LUTの格子の構造は均一である請求項12に記載された方法。
【請求項１４】
k＝4の場合、少なくとも一つのLUTは閉じており、他のすべてのLUTは開いている請求項11に記載された方法。
【請求項１５】
閉じた前記各LUTの格子の構造は均一であり、開いた前記各LUTの格子の構造は不均一である請求項14に記載された方法。
【請求項１６】
前記不均一な格子の構造におけるノードの配置は、予め定義されたテーブルにより決定される請求項15に記載された方法。
【請求項１７】
前記不均一な格子の構造におけるノードの配置は、ユーザが指定する前記n次元の色空間における値の配列により決定される請求項15に記載された方法。
【請求項１８】
k＞4の場合、すべてのLUTは開いている請求項11に記載された方法。
【請求項１９】
閉じた前記各LUTの格子の構造は均一であり、開いた前記各LUTの格子の構造は不均一である請求項18に記載された方法。
【請求項２０】
前記不均一な格子の構造におけるノードの配置は、予め定義されたテーブルにより決定される請求項19に記載された方法。
【請求項２１】
前記不均一な格子の構造におけるノードの配置は、ユーザが指定する前記n次元の色空間における値の配列により決定される請求項19に記載された方法。
【請求項２２】
さらに、前記階層集合体を使用する色変換を行い、
前記色変換は、任意の閉じたLUTと開いたLUTの内部において、一つ目の補間処理を用いて入力色値に対する出力色値を補間し、
開いたLUTと低次元の部分空間の間の空間において、前記一つ目の補間処理より計算が複雑な二つ目の補間処理を用いて入力色値に対する出力色値を補間する請求項11に記載された方法。
【請求項２３】
n次元の色空間における単位超立方体に亘り、かつ、各LUTは前記n次元の色空間から第二の色空間へ写像するLUTの集合を生成するために実行可能な、コンピュータが読み取り可能な媒体に記憶されたコンピュータが実行可能な命令であって、
k=3からnである各次元kについて、n個からk個を選択するLUTの階層集合体を定義し、各LUTはk個の入力を有し、少なくとも幾つかのLUTは他のLUTと異なる格子の構造を有し、高次元のLUTの前記格子の構造の密度を低次元のLUTよりも低くして、前記n次元の色空間における階層集合体の集合を定義し、
前記第二の色空間の値を使用して、前記LUTを表す命令。
【請求項２４】
n次元の色空間における単位超立方体に亘り、かつ、各LUTは前記n次元の色空間から第二の色空間へ写像するLUTの集合を生成する装置であって、
k=3からnである各次元kについて、n個からk個を選択するLUTの階層集合体を定義し、各LUTはk個の入力を有し、少なくとも幾つかのLUTは他のLUTと異なる格子の構造を有し、高次元のLUTの前記格子の構造の密度を低次元のLUTよりも低くして、前記n次元の色空間における階層集合体の集合を定義する定義手段と、
前記第二の色空間の値を使用して、前記LUTを表す手段とを有する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、色変換に関し、とくに、ルックアップテーブルを用いて値を補間する高次元色空間における色変換に関する。
【背景技術】
【０００２】
従来のカラープリンタシステムは、シアン、マゼンタ、イエローおよび黒（CMYK）のインクを利用する。カラープリンタが生成可能な色の範囲を拡張するため、つまり、カラープリンタが生成可能な色域を拡張するために、システムに新しいインクを加える方法が採用される。通常追加されるインクは、CMYKインクによる再現が難しい色である。一般的な選択肢は、オレンジ、グリーン、レッド、ブルーなどである。その一方で、カラープリンタの「見掛けの解像度」を向上するために、淡シアンおよび淡マゼンタなど、異なる色合いのインクが使用されている。実際、その結果得られるカラープリンタは四以上のチャネルを有する。十年に亘る「高忠実(high fidelity)」印刷の開発後、追加インクにより機能強化されたCMYKシステムなどの多チャネルシステムを使用する印刷は周知であり、現在では、四以上のチャネルを有するプリンタに出会うことは、よくあることである。
【０００３】
カラープリンタはしばしば最終出力装置であるにも関わらず、人々がカラープリンタの色空間から別のカラー装置の色空間への色変換に関心をもつという点において、カラープリンタは特別である。CMYKカラープリンタの場合、この変換の一つは、カラープリンタの「順方向モデル」として知られるCMYKからXYZへの変換である。順方向モデルと他の変換を組み合わせることにより、別の装置上でCMYK印刷をエミュレートすることができる。例えば、CMYKプリンタからレッド、グリーン、ブルー（RGB）モニタへの変換は、CMYKプリンタの出力のプルーフをRGBモニタ上で可能にする。これは、同様に、高忠実プリンタにも当てはまる。CMYK、オレンジ、グリーン（CMYKOG）からRGBへの変換は、CMYKOG出力のプルーフをRGBモニタ上で可能にする。
【０００４】
このような色変換を効率的に実現する従来のアプローチは、均一なルックアップテーブル(LUT)を経る。例えば、CMYKOGプリンタ用のInternational Color Consortium (ICC)プロファイルにおけるICC規格は、A2B1タグを規定する。A2B1タグは、CMYKOGからICC「プロファイル接続空間（CIELABまたはCIEXYZ）」に向かう順方向モデルのCMYKOGデバイス空間における均一なサンプリングを表す均一なLUTを格納する。また、ICCリンクプロファイルは、CMYKOG空間において均一にサンプリングされたLUT形式においても、CMYKOGデバイス空間からデバイス空間を含む任意の色空間への直接変換を可能にする。さらに、結果として得られるLUTのサイズが大きいため、モノクロ装置（1チャネル）を除き、多数のレベルでサンプリングを行うことはない。その代わり、通常は9レベル、17レベルまたは33レベルから選択される、少数のレベルのサンプリングを用いる。各チャネルが少数のレベルで、要求されたレベルが二つのサンプリングレベルの間にある場合、LUTは、補間アルゴリズムとともに使用されて、結果を生成する。つまり、変換のソース色空間において均一にサンプリングされ、補間にフォローされるLUTは、ICC規格に規定され、業界標準と考えられる。
【０００５】
均一なLUTのICCのアプローチのほかに、他の変換ストラクチャが提案されていることに注目すべきである。連続線形補間(Sequential Linear Interpolation: SLI)ストラクチャにおいて、LUTのノードは均一に離間されずに、戦略的に配置される。つまり、変換が急激に変動する場所に多数のノードを配置し、変換が緩慢に変動する場所には少数のノードを配置する。その結果得られる格子は、根本的な変換(underlying transformation)の特徴に従い、補間誤差を最小にする。可変直線補間(Variable Rectilinear Interpolation: VRI)ストラクチャと呼ばれる別のアプローチにおいては、補間誤差を最小にするSLIと同一目的により、不均一な格子が構築される。しかし、VRIのノード配置は、矩形セルの逐次細分化という考えを用いる。つまり、根本的な変換が急激に変動する場所は多数回細分化し、変換が緩慢に変動する場所は少数回細分化する。
【０００６】
均一なLUTは概念的に単純で実現が容易で、均一なLUTによる補間は、通常、非常に効果的であるとは言え、LUTサイズは入力次元とともに指数関数的に増加する。実際、均一なLUTにおいて使用するステップ数をd、ソース色空間のチャネル数をnとすると、LUT内のノード数はdnである。記憶装置/メモリにおいて、ノード数はすぐに演算負荷になり、演算リソースの逼迫は明らかである。六または八つのチャネルを有する高忠実装置おけるデバイスプロファイルのICC実装には、LUTにより少数のステップを使用することが現実的に必要である。プロファイルサイズをギガバイトではなくメガバイトに留めるために、A2B1テーブルを5ステップまで下げることがある。少数のステップを使用すれば、少数のサンプリングステップにより、補間誤差の増加は明らかである。さらに、LUTは均一が要求されるから色空間全体に亘って精度の劣化も一律であり、デバイス値の小さな変化によって重要な色差が発生する空間内の領域においても精度が劣化する。デバイス空間全体の幾つかの部分空間が他の部分空間よりも重要であるという事実も、高忠実装置に特有のことである。例えば、CMYKOG空間において、シアンインクとグリーンインクの色相は大きく重なり、それらインクが一緒に使用されることは稀である。同じことが、イエローインクとオレンジインクにも当て嵌まる。ステップ数の均一な減少は色空間全体に亘る品質を全体的に悪化させと考えられる。これは、ありそうもないインクの組み合わせについては許容することができるが、ありそうな/重要なインクの組み合わせに関しては許容することができない。
【０００７】
SLIまたはVRIの何れのアプローチにおいても、その目的は、補間誤差を最小にすることであり、LUTにおいて使用するノードの総数を制御することではない。これらアプローチは、RGB、CMYKまたはCIELABのような四つ以下のチャネルを有する従来の色空間において主に使用される。実際、均一なLUTが使用されたからよりも、補間誤差を最小にする目的がLUTの肥大化をもたらすかもしれない。
【０００８】
図1は一つの色空間から別の色空間へ写像する、カラーデバイスによるLUTの使用を示すブロック図である。この例において、コンピュータ100のようなデータ処理システムは、カラースキャナ99のような第一のカラーデバイスの色値を、カラープリンタ101のような第二のカラーデバイスの色値に写像する。例えば、データ処理システムは、カラースキャナが生成したRGB色値102を、カラープリンタが使用するCMYK色値104に写像する。データ処理システムは、LUT106、108、110および112の一つを使用して上記処理を行う。補間アルゴリズムの選択は、サンプル点の幾何的配置に依存する。全くまとまりがない、または、「点雲(point cloud)」106として知られる点群の場合、散乱したデータに適した補間方法が使用される。一般に、このようは方法は遅く、サンプリング位置を整列させることができない状況においてのみ採用される。
【０００９】
点雲と正反対は、サンプル点が矩形格子108に収まる場合である。矩形格子の最も単純な状態は、チャネルごとに均一にサンプリングされた状態である。一つの入力点を与えると、その入力点を囲む包囲セルの位置を効率よく突き止めることができ、包囲セル内で補間を行うために、四面体補間のような補間アルゴリズムを用いることができる。
【００１０】
もう少し複雑な状態は、チャネルごとに不均一にサンプリングされた矩形格子110である。不均一にサンプリングされた矩形格子の場合、均一な場合ほど効率的ではないが、かなり容易に包囲セルを決定することができる。包囲セルが決定すると、そのセル内の補間は、均一な場合と同様に実行される。
【００１１】
点雲の全くまとまりがない構成と、矩形格子の完全に構造的な構成の間に「適応的矩形格子」112がある。適応的矩形格子は、やはり、部分空間上で（多分、不均一にサンプリングされる）矩形格子を採用するが、これら格子は全体として互換性がない。適応的サンプリングは、色空間の重要度が低い領域におけるサンプリングレートの減少、つまり、記憶効率の向上に有用である。例えば、CMYKプリンタのIT8.7/3標準ターゲットにおいて、固定されたKに対するCMY「平面」それぞれのサンプリングは均一な矩形になる。しかし、色が暗くなり、かつ、変化が小さくなると高いサンプリングレートが無駄になり、Kの増加に連れてサンプリングレートは連続的に減少される。
【００１２】
適応的矩形格子において補間を行う伝統的なアプローチはSLIを使用する。一つのステップにおいて、n次元補間は、二つの(n-1)次元補間と、一つの一次元補間にまとめられ、同様の手順を(n-1)次元補間の問題(problem)それぞれに適用できるため、これを「連続的(sequential)」と呼ぶ。
【００１３】
SLIに関して望ましくない点が幾つかある。
【００１４】
1. SLIは、すべての対称性を保存するわけではない。実際、格子が均一な矩形で、SLIが次元1まで完全に適用されると仮定する。この場合、多線形補間（通常、三次元の場合は立体補間と呼ぶ）と同様の結果になる。主要な対角線上の点群は、立方体の全頂点を使用して補間される。これは、主要な対角線が（RGB空間における）グレー軸だと望ましくはなく、グレーは、グレー軸上のサンプル点のみを使用して補間されるのが好ましい。
【００１５】
2. SLIステップは、サンドウイッチされた平面(sandwiching planes)で用いられる補間と互換性がある必要はない。例えば、サンドウイッチされた平面それぞれで四面体補間が用いられる場合、SLIは、それら平面それぞれにおいて線形、かつ、それら平面の間を縦断する方向に線形な「ハイブリッド」つまり「双線形(bilinear)」を生成する。次元全体で真の四面体補間は、細分した四面体それぞれにおいても線形である。
【００１６】
3. SLIは、二つのサンドウイッチされた線形超平面(sandwiching linear hyperplane)を有する基本的な幾何学的構成を扱う。超平面は、n-1個の座標と、残りの座標から与えられる超平面の縦断方向から与えられる。SLIが扱えない、または、扱いに困るより複雑な幾何学的状況が他にもある。一つの例(scenario)は、異なる次元における非互換の格子の間の「ギャップ補間問題」である。図2はx1x2空間における単純な二次元の状態を示す図である。この空間内部は矩形格子でカバーされ、x1軸およびx2軸はそれぞれ異なる一次元(1-D)格子によってカバーされ、これら格子には互換性がない。ギャップ空間において補間する、三つの入力点P1、P2、P3を考える。図示されるように、P1およびP2はSLIにより扱えるが、P3を扱う自然な方法はない。一つの可能性は、x1方向にSLIの適用を試みて、A3とB3の間で補間を行うことである。ただし、B3自体がまず補間される必要がある。別の可能性は、他の方向にSLIを適用し、C3とD3の間の補間の最後である。最悪の場合、各アプローチから異なる結果を得ることがある。サンドウイッチされた幾何学的対象が線形超平面より複雑な場合、SLIは理想的なツールではないことは明らかである。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
従って、演算が扱い易く、さらに、幾何学的に複雑なLUTを管理して、正確な色変換をもたらす、多数の入力チャネルを有するカラープリンタ用の色変換システムが要求される。本発明の様々な面は、このような要求を満たす。本発明の様々な面は、このような要求を満たす。
【課題を解決するための手段】
【００１８】
例えばカラープリンタの色域を拡張するために使用される追加インクを有するCMYKカラープリンタなどの、多数の入力チャネルを有するカラーデバイスに有用な色変換装置および方法が提供される。色変換は、n次元の色空間を低次元の部分空間の集合群(sets)に階層化するLUTの階層集合体(strata collection)を使用する。低次元の部分空間に対して、関連するLUTは、閉じていて、かつ、均一な格子ストラクチャを有してもよい。高次元の部分空間に対して、関連するLUTは、LUTに囲まれない部分空間のギャップを残して開いていてもよく、不均一な格子ストラクチャを有してもよい。色変換に階層集合体を用いる色管理モジュールは、色変換がギャップにはまる(fall within)色値用かを判定してもよい。そのような色値用の色変換であれば、色管理モジュールは、相対的に複雑な補間処理を用いてもよい。そのような色値用の色変換ではなければ、色管理モジュールは、相対的に簡単な補間処理を用いてもよい。
【００１９】
本発明の一つの面において、n次元の色空間における単位立方体は、その単位立方体の範囲に及ぶLUTの集合(set)に階層化され、各LUTは、n次元の色空間から第二の色空間へ写像する。この方法において、一組の階層集合体はn次元の色空間について定義され、k=3〜n次元である各次元kについてn〜選択〜k LUTを有する階層集合体が定義される。各LUTはk個の入力を有し、少なくとも幾つかのLUTは他のLUTと異なる格子ストラクチャを有する。さらに、高次元LUTに対する格子ストラクチャは、低次元LUTより密度が低い。一組の階層集合体のLUTは、第二の色空間の色値を使用して表現される(populated)。
【００２０】
本発明の別の面において、次元3の各部分空間に関して、各LUTは閉じていて、各LUTの格子ストラクチャは均一である。
【００２１】
本発明の別の面において、次元4の各部分空間に関して、少なくとも一つのLUTは閉じていて、他のすべてのLUTは開いている。
【００２２】
本発明の別の面において、閉じた各LUTの格子ストラクチャは均一であり、開いた各LUTの格子ストラクチャは不均一である。
【００２３】
本発明の別の面において、不均一な格子ストラクチャは、指定されたデバイス値の配列に基づく。
【００２４】
本発明の別の面において、四つよりも多い次元を有する部分空間に関して、すべてのLUTは開いている。
【００２５】
本発明の別の面において、一組の階層集合体は色管理モジュールに使用される。色管理モジュールの色変換処理は、閉じたLUTと、開いたLUTの内部に対して第一の補間処理を用い、開いたLUTと低次元の部分空間の間の空間に対して第二の補間処理を用いる。本発明のこの実施例において、第二の補間処理の演算は、第一の補間処理の演算よりも複雑である。
【００２６】
本発明の別の面において、「超格子(super-grid)」アプローチは、上述した事態(scenario)1および2の逆向きの影響(adverse affects)を改善するために使用されてもよい。しかし、このようなアプローチは、CMY空間のアプリケーションにおいて「補助次元1」空間に矩形格子がある場合に最適である。本発明は超格子アプローチに関するとは言え、超格子を使用しない。本発明は、上述した事態(scenario)3を容易に扱う。そのために、本発明は、補間ステップ（以下「重心投影(barycentric projection)」と呼ぶ）を伴い、「連続四面体補間(sequential tetrahedral interpolation)」(STI)と呼ぶ補間方式をもたらすために「連続化(sequentialized)」されることが可能である。
【００２７】
本発明の別の面において、入力値を囲む単位超立方体(hypercube)は、LUTの値に基づき生成される。そして、境界条件の集合が単位超立方体に課される。実際の補間を行うために、単位超立方体の選択された頂点から入力値を介して単位超立方体の境界へ、初期の重心投影が行われる。この投影が境界条件の一つを満たす場合、補間値は、この投影を用いて後退代入(back substitution)により計算される。初期の投影が境界条件を満たさない場合は、中間値(intermediate value)が前の投影から生成されて、投影が境界条件の一つを満たすまで、単位超立方体の異なる頂点をそれぞれ使用し、中間値を介して単位超立方体の境界上へ、引き続き重心投影が行われる。そして、補間値は、初期および後続する投影を用いて後退代入により生成される。
【００２８】
本発明の別の面において、色空間に対する補間値の決定方法が提供される。この方法は、入力値を囲む単位超立方体の生成を含む。そして、境界条件の集合が単位超立方体に課される。投影が境界条件の一つを満たすまで、単位超立方体の各頂点から入力値または中間値を介して単位立方体の境界上へ、一連の重心投影が行われる。一つの境界条件を満たすと、一連の重心投影を用いる後退代入により、補間値が生成される。
【００２９】
本発明の別の面において、境界条件は離散境界条件を含む。離散境界条件は単位超立方体の頂点に関連してもよい。
【００３０】
本発明の別の面において、境界条件は連続境界条件を含む。連続境界条件は超立方体の面(facet)に関連してもよい。
【００３１】
本発明の別の面において、境界条件は、単位超立方体の第一の面(facet)に関連する第一の連続境界条件、および、単位超立方体の第二の面に関連する第二の連続境界条件を含み、第一の面と第二の面の交差面(intersection)において一致する。
【００３２】
本発明の別の面において、入力値を囲む単体(simplex)が決定される。本発明の本実施例において、単体は超立方体に囲まれ、単体の頂点を使用して重心投影を行う。
【００３３】
本発明の別の面において、重心投影に使用する中間値は、前の重心投影から決定される。
【００３４】
この簡潔な概要は、本発明の特徴を速やかに理解するためのものである。本発明のより完全な理解は、添付図面に関連する以下の詳細な説明の参照から得られるだろう。
【発明を実施するための最良の形態】
【００３５】
本発明は、任意のn次元の色空間においてLUTを使用する補間方法に関連する。詳細な説明において、二次元および三次元空間の例が与えられるが、補間処理は、任意のn次元色空間において行われるだろうことが理解される。従って、以下の用語は、補間処理において実行される操作を表す幾何物体の種類を識別するために使用される。
【００３６】
超立方体とは、三次元立方体など、n次元の測定多胞体(measure polytope)の一般形である。低次元の超立方体は特定の名称を有する。例えば、一次元の超立方体は線分、二次元の超立方体は正方形、三次元の超立方体は立方体、四次元の超立方体は正八胞体(tesseract)である。
【００３７】
単体(simplex)とは、n次元の空間の四面体領域(tetrahedral region)の一般形である。任意の空間において可能な多胞体のうち最も単純なものを示すため、単体と呼ばれる。例えば、二次元の単体は正三角形、三次元の単体は四面体、四次元の単体は四次元立法体(pentatope)などである。
【００３８】
他の一般形は、下表に示される。
──────────┬──────┬───────┬──────
2-D         │    3-D     │    4-D       │    総称
──────────┼──────┼───────┼──────
円                  │球体        │四次元超球体  │超球体
circle              │sphere      │glome         │hypersphere
──────────┼──────┼───────┼──────
正方形              │立方体      │四次元立方体  │超立方体
square              │cube        │tesseract     │hypercube
──────────┼──────┼───────┼──────
正三角形            │四面体      │五胞体        │単体
equilateral triangle│tetrahedron │pentatope     │simplex
──────────┼──────┼───────┼──────
多角形              │多面体      │多胞体        │多胞体
polygon             │polyhedron  │polychoron    │polytope
──────────┼──────┼───────┼──────
線分                │平面        │超平面        │超平面
line segment        │plane       │hyperplane    │hyperplane
──────────┼──────┼───────┼──────
正方形              │八面体      │十六胞体      │多胞体
square              │octahedron  │16-cell cross │polytope
──────────┼──────┼───────┼──────
多角形辺            │面          │面            │面
polygon edge        │face        │facet         │facet
──────────┼──────┼───────┼──────
面積                │体積        │容積          │容積
area                │volume      │content       │content
──────────┴──────┴───────┴──────
【００３９】
図3は本発明の代表的な実施例における、高忠実色空間と別の色空間の間の色値の変換を示す図である。本発明は、高忠実色空間から、別の高忠実色空間または低次元の色空間への色変換に適用されるだろう。従って、高忠実色空間の入力色値300を第二の高忠実色空間の第二の色値302に変換可能である。あるいは、入力色値300を低次元色空間の色値310に変換可能である。この変換を行うために、データ処理システムは、補間モジュール304を使用する。補間モジュール304は、第一の色値を受信し、LUT312の集合（階層集合体と呼ぶ）を使用し、補間を介して第二の色値を生成する補間処理306を含む。
【００４０】
上述した例(scenario)において、階層集合体の代わりに、均一にサンプリングされたLUT（以下、均一LUT）が補間処理に使用されてもよい。均一LUTによって単純かつ効率的な補間処理になるとは言え、このような方法は、色空間の次元数が増えて大きなメモリが必要になり、しばしば「次元の呪い(curse of dimensionality)」と呼ばれる。現実には、カラーデバイスは六または八つのチャネルを有するとは言え、例えばインクの範囲(coverage)の問題により、これらチャネルが同時に使用されることは滅多にない。従って、多くの場合、入力色値の色値変換には「アクティブな」色材が数種しかなく、実際に、変換は低次元色空間に帰するという簡潔な前提がある。これは、使用する色空間が低次元ほど補間が速くなることから、低次元の色空間において、より効率的に補間を行えることを意味する。
【００４１】
従って、本発明の種々の実施例は、デバイス色空間全体を様々な次元の部分空間に階層化する。色空間の階層化により、低次元（大抵は三または四つの色材の組み合わせ）はより重要である。そこで、例えば、低次元部のサンプリングレートを増やし、高次元部のサンプリングレートを減らすように、階層化された色空間の異なる部分に異なるサンプリングレート（例えば異なるステップ数）を使用可能である。
【００４２】
本発明の代表的な実施例による変換を説明するために、ここでは、以下の記号を使用する。nは、色変換のソース色空間においてサンプリングしたいチャネル数である。また、nを単純に入力次元とすることも可能で、特に指定しない限りn≧5である。
【００４３】
階層集合体の基本構成ブロックは、入力次元がnの均一LUTに代わる、様々な入力次元とサイズの複数のLUTである。正確には、ここで使用されるように、「LUT」は単位超立方体上に課される矩形格子であり、全色空間座標は[0, 1]の範囲に正規化される。νがLUTの入力次元（なお、νは通常nに等しい必要はなく、すべてのνはν≦nである）の場合、LUTは、下式で表されるν個の一次元サンプリング格子から構成される。
Sampi: x1, x2, …, xd(i)
ここで、全xjは範囲[0, 1]に位置し、厳密に、jの増加に伴い増加する、
d(i)（≧1）はi番目のチャネルをサンプリングするステップ数、
xd(i)は1、他方、x1は0である必要はない
【００４４】
ここで使用されるように、LUTには、以下に定義するような二つの特別な場合がある。
【００４５】
「閉LUT」は、各Sampiについてx1=0とd(i)≧1という追加条件を有するLUTである。つまり、このLUTは、単位超立方体の全境界面上で少なくとも定義される。さらに、均一の閉LUTは、チャネルごとに同一のステップ数d(i)を有する閉LUTで、0と1の間に均一に離間されたノードをもつ。
【００４６】
「開LUT」は、各Sampiについてx1＞0という追加条件を有するLUTである。つまり、開LUTは、単位超立方体の原点を含む境界面上には定義されない。さらに、一つのステップのみを有することが許され、すなわち、d(i)=1である。
【００４７】
本発明の一実施例において、単位超立方体[0, 1]nは、LUTの全集合体が単位超立方体をカバーするように、閉LUTと開LUTの集合体に階層化される。これら「LUT階層」を、それらの次元により構成することが、概念上、より簡単であり、その最上レベルは下式で書くことができる。
[0, 1]n = ∪k=3nΣk
ここで、Σkは「k次元の階層集合体」を表す、
∪k=3nはΣ3からΣnの和集合を表す
【００４８】
なお、階層次元kは0の代わりに、点に対応する3から始まる。何故ならば、三色材の組み合わせの補間は、メモリの必要量が大きくなり過ぎず、非常に効率的に扱えるからである。しかし、より低次元の階層集合体が可能であることは理解されるべきだ。
【００４９】
本発明の一実施例において、Σ3は、三入力を有する閉LUTから構成され、各LUTは、n個の色材から選択される三色材の可能な組み合わせの一つである。Σ4は、CMYK（または、最初の四色材）の組み合わせに対する一つの閉LUTと、四色材の他の全組み合わせに対する(n, 4)-1個の開LUTから構成される。何故ならば、CMYKの組み合わせは、ほとんどのカラープリンタの基本であり、重要な組み合わせだからである。最後に、k=5, …, nの場合、Σkは(n, k)個の開LUTから構成され、各LUTは、全n個の色材から選択されるk個の色材の可能な組み合わせの一つである。なお、(n, k)は選択候補の数nから、k個を選ぶ組み合わせの数を表す。
【００５０】
LUTの性質を設定した後、LUTのサイズの特定が残る。開LUTと閉LUTの間の一つの違いは、開LUTは互いに重なり合わないが、閉LUTは境界面において互いに重なり合ってもよい。開LUTにおける1-Dサンプリングが「0」を含まないことは、開LUTが境界表面の抜けた半分(missing half)であることを本質的に意味し、それで「開」と呼ばれる。二つのLUTが重なり合わない場合、一方のLUTは、チャネルごとに異なるステップ数とノード位置を自由に使用することができる。これは、二つのLUTが重なり合う場合には当て嵌まらない。この場合、ステップ数および/またはノード位置が異なると、二つのLUTの交差部分に位置する点は、補間に使用されるLUTによって異なる補間値を受け取るだろう。本発明の一実施例において、二つのLUTが重なり合う場合は必ず、同一のステップ数を使用する均一サンプリングが使用される。
【００５１】
要約すると、すべての閉LUT（本実施例における三色材のLUTすべてとCMYK LUT）は均一であり、dで示される同一のステップ数を有する。
【００５２】
図4は本発明において、閉LUTのステップ数d、並びに、開LUTのステップ数およびノード位置を決定するために使用する処理の処理フロー図である。処理400において、ユーザがサンプル点を与えるか否かにより、二つの異なる処理モードがある。処理400は、ユーザがサンプル点404を与えるか否かを判定する(402)。与えない場合、表1に代表的な内容が示されるテーブル408に記述されたステップ数dを有する均一LUTとして閉LUTを生成する(406)。
表1
──────┬─────┬─────┬─────
│校正モード│通常モード│最良モード
──────┼─────┼─────┼─────
ステップ数d│     9    │    17    │    33
──────┴─────┴─────┴─────
【００５３】
k次元の全ての開LUTは、入力チャネルごとに同一のステップ数d(k)を有し、ノードは均一に離間される。つまり、i=1, 2, …, kについて、1-Dサンプリング格子は下式で表される。
Sampi: 1/d(k), 2/d(k), …, (d(k)-1)/d(k), 1
【００５４】
処理のこの工程において、テーブル408の一部においてd(k)が指定され、その代表的な内容は表2に示される。
表2
─────────┬─────┬─────┬─────
│校正モード│通常モード│最良モード
─────────┼─────┼─────┼─────
4チャネル用の    │          │          │
ステップ数d(4)   │     5    │     7    │     9
─────────┼─────┼─────┼─────
5チャネル用の    │          │          │
ステップ数d(5)   │     2    │     3    │     3
─────────┼─────┼─────┼─────
6チャネル用の    │          │          │
ステップ数d(6)   │     2    │     3    │     3
─────────┼─────┼─────┼─────
7チャネル用の    │          │          │
ステップ数d(7)   │     2    │     2    │     2
─────────┼─────┼─────┼─────
8以上のチャネル用│          │          │
のステップ数d(k) │     2    │     2    │     2
─────────┴─────┴─────┴─────
【００５５】
三つのモード「校正」「通常」「最良」は品質設定であり、通常、ユーザの用途に基づく品質選択を許容する色管理モジュール(CMM)ソフトウェアに存在する。本発明の代表的な実施例において、校正モードのメモリ占有量(footprint)は最小であり、最良モードのメモリ占有量は最大である。
【００５６】
処理400は、ユーザがサンプル点を与えると判定すると、「重要」なサンプリング位置のリストの形式の外部入力を使用して、LUTを生成する(410)。処理400のこの工程は、テーブル駆動の工程よりも適応性があり、さらに、メモリ空間を節約することができる。
【００５７】
外部入力は、ユーザによって与えられたデバイス値の配列である。これらデバイス値は、デバイス色空間の重要な領域、つまり、高密度または高レートでサンプリングされるべきデバイス色空間の領域を示す。
【００５８】
上述したように、処理400のこの工程によって生成される全ての閉LUTは、上記の表1に記述されたステップ数dで均一である。しかし、各開LUTは、入力チャネルごとに異なるステップ数を有することが可能であり、サンプリング位置が均一に離間している必要はない。
【００５９】
図5は本発明の代表的な実施例における、ユーザが指定するサンプリング位置を使用してLUTを生成するために使用される処理を示す図である。任意の開LUTの階層に関連する色材の組み合わせ、例えば、ciが1とnの間の別個の整数であるc1, …, ckがある。これらは、その階層において「アクティブ」な色材に対応するチャネル指標である。
【００６０】
LUT生成処理410は、次元kの階層ごとに繰り返して(500から512)、つまり、i=1, 2, …, kによって索引されるアクティブなチャネルごとに、以下のステップを実行する。
【００６１】
処理410は、ユーザが指定するサンプル点の入力配列から、処理する階層に含まれない全デバイス値を除去する(502)。他の全チャネルが0の場合のみ、デバイス値(x1, x2, …, xn)は階層に含まれる。フィルタを通過した集合がNエントリィを有する場合、dtentative=min(d(k), max(1, int(N1/k)))とする。ここで、d(k)は上記の表2から与えられる。d(k)はLUTのサイズに上限を課すから、Nが大きい場合、つまり、その階層に多数のサンプルがある場合でもLUTのサイズが制御不能になることはない。これに対し、N=0の場合は1ステップLUTを使用する。
【００６２】
処理410は、dtentative=1の場合、Sampiが一点のみを有すると判定して(504)、Sampiに1.0に設定する。処理410は、この判定の場合は次の階層に進み、そうでなければ処理を継続する。
【００６３】
処理410は、ci番目のチャネルにおいて、フィルタを通過したサンプルを昇順にソートする(506)。
【００６４】
処理410は、フィルタを通過したサンプルのソート後、下式で表されるノードを使用して、i番目のアクティブなチャネル（全デバイス空間においてci番目）用の「暫定」サンプリング格子を定義する(508)。
xj = (j - 1)・100/(dtentative - 1)パーセンタイル
ここで、j = 1, 2, …, dtentative
【００６５】
処理410は、暫定格子を正規化し(510)、格子が厳密な単調性(monotonicity)であること、および、格子が1.0で終了することを確認する。フィルタを通過したサンプルはci番目のチャネルにおいて既にソートされているから、暫定格子のノードは単調非減少(monotonic decreasing)である。しかし、隣接するノード同士は同一の可能性がある。必要に応じて、同一ノードを除去して、これを補正することができる。この手続きの後、最後に、終了点が1.0よりも小さい場合は、終了点を1.0で置き換える。
【００６６】
なお、正規化後、チャネルのステップ数はdtentativeより小さくてもよく、正規化処理したLUT階層は、チャネルごとに異なるステップ数を有してもよい。
【００６７】
階層化処理の最後に、テーブル値またはユーザが与える値の何れかを用いて、単位超立方体は、開LUTおよび閉LUT階層を有する階層集合体によって階層化される。
【００６８】
図6は本発明の代表的な実施例における、補間モジュールのブロック図である。補間モジュール600は、階層集合体を使用して、入力デバイス値604から出力色値602を生成する。出力色値602を生成するために、補間モジュール600は、チャネル値の集合、つまり(x1, x2, …, xn)により与えられる入力デバイス値604を受信する。補間モジュール600は、階層セレクタ604を使用して、階層集合体から入力デバイス値604を含む階層606を選択する。補間回路608は、含有階層(containing stratum)606および入力デバイス値604を使用して、出力色値602を生成する。
【００６９】
図7は本発明の代表的な実施例における、階層セレクタのブロック図である。階層セレクタ604は、「アクティブ」なチャネル数を計算する(700)。これは、単純に、入力デバイス色の非ゼロチャネルの数である。これによって、階層セレクタ604による含有階層の検索における階層次元kを決定する。より正確には、階層セレクタ604は、アクティブなチャネル数≦3の場合は階層次元に3を設定し、それ以外の場合は階層次元をアクティブなチャネル数に等しく設定する(702)。そして、階層セレクタ604は、k次元階層セレクタ704を使用して、補間に使用する個々の階層を選択する。
【００７０】
図8は本発明の代表的な実施例における、k次元階層セレクタのブロック図である。k次元階層セレクタ704は、階層集合体Σkから入力デバイス値を含む階層を検索する。階層に対応する全チャネルの値が0ではなく、かつ、他の全チャネルが0であれば、デバイス値は開いた階層に含まれる。階層の非アクティブな全チャネルにおいてデバイス値が0であれば、デバイス値は閉じた階層に含まれる。k次元階層セレクタ704は、デバイス値が第一の階層S1800内にあるかを判定する。デバイス値が第一の階層800にない場合、k次元階層セレクタ704は、含有階層606を見付けるまで連続して、各階層Si802の判定を試みる。含有階層606が見付からない場合、k次元階層セレクタ704は検索を中止し、検索失敗を報告する。含有階層606が見付かった場合、補間出力値を入力デバイス値604と含有階層606から生成することができる。
【００７１】
図9は本発明の代表的な実施例における、補間部が用いる補間処理の処理フロー図である。（図6の）補間部608は、補間処理900を用いて、入力デバイス値604と含有階層606から出力色値602を生成する。補間部608は、含有階層606が閉じているかを判定する(902)。含有階層606が閉じていれば、超立方体のノードに対してうまく働く従来の補間処理により、含有階層606内の補間を実行することができる。本発明の一実施例は、四面体補間部904を使用する。補間部608は、含有階層606が開いていて、デバイス値が厳密に階層内に位置する、すなわち、デバイス値が階層のアクティブなチャネルに対応するすべての指標iに対するi番目のチャネルにおける第一のノードの値である、と判定した場合(906)、同様の標準的な補間処理（四面体補間部904が使用する処理など）を使用することができる。
【００７２】
一方、xiが、あるアクティブなチャネル指標iに対するi番目のチャネルの第一のノードの値より小さい場合、そのデバイス値は、その階層と低次元部分空間の間の「ギャップ」にはまっている。好ましいギャップ補間部は、以下に説明する超限(transfinite)補間アルゴリズムを使用するけれども、キャップ補間部908が使用するギャップ処理など、ギャップ内での補間が可能な任意の処理が使用可能である。通常、このような補間を実行可能な処理は、四面体補間アルゴリズムを使用する補間処理のような、如何なる従来の補間処理よりも複雑である。
【００７３】
高忠実色用の色変換処理における単位超立方体に亘る階層集合体の使用は、単一の均一LUTの使用と比較して、幾つかの利点がある。上述したように、結果として得られる低密度のLUT構造は、LUTが必要とする合計サイズのチェックを維持しながら、色材の重要な組み合わせを含むデバイス空間の領域を合理的な密度でサンプリングすることを達成する。下の表3は、（上述したテーブル駆動のLUT生成処理を用いる）低密度のLUTの実現に必要なノード数と、対応する均一LUTの実現に必要なノード数の比較を示す。表からわかるように、低密度のLUTシステムを使用することで、より小さく、従って、より管理し易いLUTサイズが得られる。
───────┬───────┬───────
入力チャネル数│低密度LUT構造 │    均一LUT
│（通常モード）│（17ステップ）
───────┼───────┼───────
5      │    142498    │     1419857
6      │    217582    │    24137569
7      │    347444    │   410338673
8      │    559618    │  6975757441
───────┴───────┴───────
【００７４】
図10は本発明の代表的な実施例における、カラーデバイスに接続され、かつ、色管理モジュールを有するコンピュータのような、補間モジュールのホストを務めるだろうデータ処理システムのブロック図である。
【００７５】
データ処理システム1000は、システムバス1006を介してメモリ1004に接続されたプロセッサ1002を含む。プロセッサ1002は、システムバス1006および入出力(I/O)バス1008を介して、さらに、外部の入出力(I/O)装置に接続される。コンピュータシステムが読み取り可能な媒体を有する記憶装置1010は、記憶装置コントローラ1012、I/Oバス1008およびシステムバス1006を介してプロセッサ1002に接続される。記憶装置1010は、上述した補間処理を実現するために使用するデータ1014およびプログラム命令1016を記憶し、また、読み出すためにプロセッサ1002によって使用される。プロセッサ1002は、I/Oバス1008に接続された出力装置コントローラ1019を介して、さらに、コンピュータディスプレイ1017およびカラープリンタ1018などのカラー出力装置に接続してもよい。プロセッサ1002は、入力装置コントローラ1022を介して、さらに、カラースキャナ1020などのカラー入力装置に接続してもよい。
【００７６】
動作時、プロセッサ1002は、記憶装置1010からメモリ1004へプログラム命令をロードする。次に、プロセッサ1002は、ロードしたプログラム命令を実行して、カラープリンタの使用を意図する色値のような、第一の色空間の入力色値を受信する。そして、プロセッサ1002は、プログラム命令を実行して、上述したように、表示装置が使用するための色値のような、第二の色空間の出力色値を生成する。
【００７７】
LUTとして矩形格子を使用する際の基本的なステップは、包囲セル内の補間である。任意の入力値の包囲セルは容易に決定される。矩形格子の場合、包囲セルの各頂点（コーナ点）の出力値が特定される。これら点は、補間曲線(interpolant)が満たさなければならない唯一の境界条件(boundary condition: BC)であり、つまり、補間曲線はこれら点の間を貫通しなければならない。なお、これら境界条件は「離散的」な点に対するもので、nを色空間の次元とすれば、ここではセルの2n個のコーナ点に対するものである。
【００７８】
境界条件は、以下のように定形化される。ここで、n次元における単位超立方体として捉えられる包囲セルの境界の任意の部分集合Sに対する境界条件は、mを出力次元とすると、関数BC: S→Rmという仕様である。言い換えると、Interp: [0, 1]n→Rmと表示してもよい補間曲線は、部分集合S内のすべてのxについてInterp(x)=BC(x)を満たす必要がある。単位超立方体における補間の標準例(standard scenario)において、部分集合Sは、超立方体の2n個の頂点である離散点の集合である。
【００７９】
下記の境界条件の一般化は、上述した問題を解決することができる、単位超立方体内の新しい補間アルゴリズムである。離散境界点のみを許容する代わりに、超立方体の境界面(boundary facet)全体に境界条件が課されてもよい。正確な前提は以下のとおりである。
(a) 点vn=(1, 1, …, 1)は特殊で、離散境界条件のみが許される。言い換えると、n個の境界面xi=1(i=1, …, n)に対して連続境界条件が課されることはない。
(b) 残るn個の境界面xi=0(i=1, …, n)それぞれについて、二つの面が交差する場合は、それら面の境界条件が交差部で一致するという互換性条件を用いて、面全体に境界条件が課されてもよい。
(c) 境界条件を有する面に含まれない任意の頂点は、個別（離散）境界条件を有する。
【００８０】
ここで使用されるように、離散境界条件は「有限データ」と呼ばれ、連続境界条件は「超限データ」と呼ばれる。従って、ここで説明する補間手順は、有限および超限データの補間である。
【００８１】
下記の四面体補間、単体、補間の説明は、本発明の説明に使用する表記法の設定に役く立つ。単位超立方体[0, 1]nが、n個のシンボルの順列(permutation)の集合によって媒介(parameterize)されるn!個の単体に細分化可能なことは、よく知られている。つまり、各単体は、不等式xσ(1)≧xσ(2)≧…≧xσ(n)の集合によって定義される。ここで、σ: {1, 2, …, n}→{1, 2, …, n}は、「シンボル」1, 2, …, nの順列であり、つまり、n個のシンボルの集合の全単射像(bijective mapping)である。例えば、n=3とし、σ(1)=3、σ(2)=2、σ(3)=1を意味する簡略表記σ=＜3, 2, 1＞を使用すれば、対応する単体はz≧y≧xによって定義される。ここで、x1、x2、x3に対して共通の表記法x、y、zを使用する。なお、これら単体は互いに素(disjoint)ではないが、補間目的のため、補間に使用される単体かに関わらず、二つの異なる単体の共通面(common facet)上に位置する点は同一の補間値をもつものとする。
【００８２】
従来の有限点の補間処理は、まず、別の単体によりある単体の不等式をチェックすることで、任意の入力点(x1, …, xn)について、入力点が存在する単体、または同等の、対応する順列σを決定する。単体補間曲線(simplex interpolant)は下式で定義される。
Interp(x) = BC(v0) + Σi=1nxi[BC(vi) - BC(vi-1)]
ここで、v0 = 0、
vi = Σj=1ieσ(j), i = 1, …, n、
e1, …, enは標準基底(standard basis)ベクトル、
v0, v1, …, vnは単体の頂点、
1-xσ(1), xσ(1)-xσ(2), xσ(2)-xσ(3), …, xσ(n)は頂点の「重心座標」、
Σk=xyはk=xからk=yの総和演算を表す
【００８３】
しかし、このような従来の四面体補間処理は、境界条件が離散的ではなく連続する場合を取り扱えない。これに対して、本発明は、離散および連続する境界条件が混在する場合を取り扱い可能な四面体補間の一般形を利用する。その結果生じる処理を、すべての離散境界条件を利用する補間に適用すれば、従来のアプローチが与える答えと同一結果になる一連の重心投影および後退代入が得られる。
【００８４】
図11は本発明の代表的な実施例において、ある色空間の入力色値を別の色空間の出力色値に写像するためにカラーデバイスが用いる補間処理の処理フロー図である。処理1100は、単位超立方体の境界面における通常の境界条件用の重心投影を使用する。まず、補間処理1100は、任意の入力値(x1, …, xn)について、入力値が存在する単体、または同等の、対応する順列σを決定する(1110)。そして、補間処理1100は、以下の一連の重心投影を行う(1120)。
【００８５】
最初の投影BProj1(x)は、入力値が既に頂点ではない、または、x=vnではない限り、入力値を平面xσ(1)=0へ送る。入力値が既に頂点、または、x=vnの場合は入力値は変更されない。写像BProjkの正確な定義は下式のとおりである。
x ≠ pkの場合  BProjk(x) = pk + (x - pk)/(1 - xσ(k))
x = pkの場合   BProjk(x) = x
ここで、pk = vn - Σi=1k-1eσ(n+1-i), k = 1, 2, …, n
【００８６】
x≠vnの場合、BProj1(x)がσ(1)番目の成分を消滅(annihilate)させることは明らかだ。言い換えると、投影点または中間色値は、ある境界面上にある。次に、補間処理1100は、境界条件が定義された面上に投影点があるかを判定し(1150)、その面上に投影点があれば投影を停止することができる。その面上に投影点がない場合、補間処理1100は、x'=BProj1(x)とするとBProj2(x')である別の重心投影を行う(1160)。次の投影点が頂点または境界条件が定義された面上にあれば、投影を停止することができる。それらの上に投影点がない場合、補間処理1100は、さらに別の投影を行う。各投影は一つの成分を消滅させるため、有効な次元が減少し、補間処理1100はやがて停止する。最悪の場合、補間処理1100は、次元0に下がるまでn回の投影を行うだろう。つまり、上記(c)の前提によれば、超立方体の頂点は、頂点に定義された境界条件を有することになる。
【００８７】
入力点x(k)=BProjk(x(k-1)), k=1, …, K, x(0)=xによりK回の投影が行われ、境界条件がx(k)において定義されると仮定する。そうすると、補間処理1100は、一連の出力ベクトルを定義することで、後退代入を介して投影をアンワインド(unwind)することができる(1170)。
y(k-1) = xσ(k)(k-1)BC(pk) + (1 - xσ(k)(k-1))y(k)
ここで、k = K, K-1, …, 1、
y(K) = BC(x(K))、
最終的に得られる答えはInterp(x) = y(0)
【００８８】
図12は本発明の代表的な実施例における、補間例を示す図である。この例において、n=3、m=1であり、単位超立方体1200には下記の境界条件がある。
(a) 頂点の四つの離散境界条件
(0, 0, 1): β001
(0, 1, 1): β011
(1, 0, 1): β101
(1, 1, 1): β111
(b) 面x3=0の連続境界条件はF(x1, x2)
【００８９】
入力値1210 x=(0.8, 0.5, 0.2)について、包囲単体は順列＜1, 2, 3＞に関連する。第一の投影1220は下式で表される。
p1 = (1, 1, 1), x(1) = p1 + (x - p1)/(1 - 0.2) = (0.75, 0.375, 0)
【００９０】
第一の投影は面x3=0上にあり、補間処理を停止することができる。そして、後退代入は、答えであるy(0)=0.2β111+0.8F(0.75, 0.375, 0)を与える。
【００９１】
図13から図15は本発明の代表的な実施例における、補間例を示す図である。この例において、超立方体1200は前の例と同じであるが、入力点1300はx=(0.2, 0.5, 0.8)である。包囲単体は、順列に関連する。
第一の投影1310はp1 = (1, 1, 1)、x(1) = p1 + (x - p1)/(1 - 0.2) = (0, 0.375, 0.75)
第二の投影1320はp2 = (0, 1, 1)、x(2) = p2 + (x(1) - p2)/(1 - 0.375) = (0, 0, 0.6)
第三の投影1330はp3 = (0, 0, 1)、x(3) = p3 + (x(2) - p3)/(1 - 0.6) = (0, 0, 0)、これは面700 x3=0上にある
【００９２】
後退代入は下記の最終的な答えを与える。
y(1) = 0.375β011 + 0.625y(2) = 0.375β011 + 0.375β001 + 0.25F(0, 0)
【００９３】
なお、これは、四点(1, 1, 1)(0, 1, 1)(0, 0, 1)および(0, 0, 0)における四面体補間に等しく、この補間処理が確かに四面体補間処理の一般化であることが裏付けられる。
【００９４】
図16は本発明の代表的な実施例において、補間処理が非互換の格子を有する二つの超平面1600と1602の間の補間を管理する方法例を示す図である。この例において、ある点1604を囲むセルが図示される。セルの「トップ」頂点1606、1608、1610および1612はトップ面の格子から直接得られる。「ボトム」面(facet)1614の頂点はボトム平面の格子と非互換であり、そのため、補間処理は、ボトム平面の格子上の補間によって得られる値を有する境界条件を持つものとして、面(facet)全体を扱う。この設定が上述した前提(a)(b)および(c)を満たすことは明らかであり、補間処理を首尾よく実行することができる。
【００９５】
また、結果は、上部格子(upper grid)の頂点の値と、下部平面(lower plane)の補間値の線形結合であって一つ少ない次元を有するから、補間処理が補間問題の次元を一つ減らすことも明らかである。類似するサンドウイッチされた平面構造が下部平面に存在する場合、補間処理は、この手順を下部平面に順に適用することができ、さらに次元を一つ減らす。この処理は、補間処理が次元0に達するまで継続することができる。この一連(cascade)の投影と補間を「連続四面体補間」と呼ぶ。
【００９６】
図17は本発明の代表的な実施例における、「ギャップ」にはまる入力値の補間処理を示す図である。この例において、正の象限の内側に厳密に位置する超立方体1700に格子が課される。超立方体1700自体は格子1702を有する。座標超平面1704、1706および1708それぞれが有する格子は、互いに、または、超立方体1702の格子に対して互換性を必要としない。超立方体1700と座標平面1704、1706および1708の間の「ギャップ」は「L字型」の断面を有し、SLI（連続線形補間）のような標準的な技術に従順(amenable)ではない。しかし、ここで説明する補間処理により、入力値1709を囲むセル1710のようなセルを導入すれば、セルはギャップを容易にカバーする。座標平面上の格子は、セルの下部のボトム面すべてに必要な境界条件を提供する補間をサポートする一方、一つ残る頂点1712の境界条件は、超立方体1700の下部コーナによって提供される。
【００９７】
実際のアプリケーションにおいて、ここで説明される補間処理の基本的な設定である「単位超立方体」は、より大きな格子から抽出され、頂点の値の計算には高い計算コストを必要とする。他方、四面体補間は、単位超立方体の全頂点の部分集合である単体の頂点の値のみを必要とすることが明らかである。従って、「据置き評価(deferred evaluation)」を実現することが、より効果的であり、幾つかの状況においては必須である。詳しくは、補間処理のソフトウェア実装においては、通常、単位超立方体とその頂点の値を入力とするサブルーチンを有する。据置き評価により評価を実行せず、頂点の値を渡す代わりに、頂点の値を評価するために必要な情報を単に渡すことができる。サブルーチン内部では、包囲単体の決定後、包囲単体に属する頂点に対してのみ、値の実際の評価が実行される。
【００９８】
図18は本発明の代表的な実施例における、上述した補間処理のホストを務めるだろう、カラーデバイスのようなデータ処理システムのブロック図である。
【００９９】
データ処理システム1800は、システムバス1806を介してメモリ1804に接続されたプロセッサ1802を含む。プロセッサ1802は、システムバス1806および入出力(I/O)バス1808を介して、さらに、外部の入出力(I/O)装置に接続される。コンピュータシステムが読み取り可能な媒体を有する記憶装置1810は、記憶装置コントローラ1812、I/Oバス1808およびシステムバス1806を介してプロセッサ1802に接続される。記憶装置1810は、上述した補間処理を実現するために使用するデータ1814およびプログラム命令1816を記憶し、また、読み出すためにプロセッサ1802によって使用される。プロセッサ1812は、I/Oバス1808に接続された出力装置コントローラ1818を介して、さらに、カラー出力装置1817などの出力装置に接続してもよい。
【０１００】
動作時、プロセッサ1802は、記憶装置1810からメモリ1804へプログラム命令をロードする。次に、プロセッサ1802は、ロードしたプログラム命令を実行して、第一の色空間の入力色値を受信する。そして、プロセッサ1802は、プログラム命令を実行して、上述したように、第二の色空間の出力色値を生成する。
【０１０１】
特定の実施例に関連して、本発明を説明した。本発明は、上述した実施例に制限されず、本発明の主旨の範囲から逸脱せずに、当業者により種々の変更および変形が行われるだろうことが理解される。
【図面の簡単な説明】
【０１０２】
【図１】ある色空間から別の色空間へ写像する、カラーデバイスによるLUTの使用を示すブロック図、
【図２】空間内部が矩形格子でカバーされ、x1、x2軸それぞれが異なる1-D格子によりカバーされ、さらに、これら格子に互換性がないx1x2空間における単純な二次元状態を示す図、
【図３】本発明の代表的な実施例に関連する、高次元色空間と他の色空間の間の色値の変換を示す図、
【図４】本発明において、閉LUTのステップ数d、並びに、開LUTのステップ数およびノード位置を決定するために使用する処理の処理フロー図、
【図５】本発明の代表的な実施例における、ユーザが指定するサンプリング位置を使用してLUTを生成する処理を示す図、
【図６】本発明の代表的な実施例における、補間モジュールを示すブロック図、
【図７】本発明の代表的な実施例における、階層セレクタを示すブロック図、
【図８】本発明の代表的な実施例における、k次元の階層セレクタを示すブロック図、
【図９】本発明の代表的な実施例における、補間部が用いる補間処理の処理フロー図、
【図１０】本発明の代表的な実施例における、カラーデバイスに接続され、かつ、色管理モジュールを有するコンピュータのような、補間モジュールのホストを務めるだろうデータ処理システムのブロック図、
【図１１】本発明の代表的な実施例における、ある色空間の入力色値を別の色空間の出力色値へ写像する、カラーデバイスが使用する補間処理の処理フロー図、
【図１２】本発明の代表的な実施例における、補間例を示す図、
【図１３】本発明の代表的な実施例における、補間例を示す図、
【図１４】本発明の代表的な実施例における、補間例を示す図、
【図１５】本発明の代表的な実施例における、補間例を示す図、
【図１６】本発明の代表的な実施例における、非互換の格子を有する二つの超平面間の補間を補間処理が管理する方法の一例を示す図、
【図１７】本発明の代表的な実施例における、「ギャップ」にはまる入力値用の補間処理を示す図、
【図１８】本発明の代表的な実施例における、補間処理のホストを務めるだろう、カラーデバイスのようなデータ処理システムのブロック図である。
【図１】
2008533764.tif 000003
【図２】
2008533764.tif 000004
【図３】
2008533764.tif 000005
【図４】
2008533764.tif 000006
【図５】
2008533764.tif 000007
【図６】
2008533764.tif 000008
【図７】
2008533764.tif 000009
【図８】
2008533764.tif 000010
【図９】
2008533764.tif 000011
【図１０】
2008533764.tif 000012
【図１１】
2008533764.tif 000013
【図１２】
2008533764.tif 000014
【図１３】
2008533764.tif 000015
【図１４】
2008533764.tif 000016
【図１５】
2008533764.tif 000017
【図１６】
2008533764.tif 000018
【図１７】
2008533764.tif 000019
【図１８】
2008533764.tif 000020