領域記述子の作成方法およびその装置
【目的】 領域境界点を任意の方向に沿って定義する方法を提供すること。
【構成】 装置に依存しない独立色空間における所定のパターンの領域から領域境界信号を選択し、これに対する信号を装置依存色空間において決定する。信号の選択にあたっては、領域を所定の間隔で平行な平面に分割し、その平面ごとに、所定の角度をおいた単位ベクトルを選択し、この単位ベクトルと領域境界との交点信号を決定する。
【構成】 装置に依存しない独立色空間における所定のパターンの領域から領域境界信号を選択し、これに対する信号を装置依存色空間において決定する。信号の選択にあたっては、領域を所定の間隔で平行な平面に分割し、その平面ごとに、所定の角度をおいた単位ベクトルを選択し、この単位ベクトルと領域境界との交点信号を決定する。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、１つの色空間からの色データを他の色空間へ変換するために使用される領域記述子を作成する方法および装置に関し、より詳しくは、装置に依存しない独立した色空間における領域境界点の中から注意深く選択した点の集合を用いて高速で色較正を可能にするシステムに関する。
【０００２】
【従来の技術】ＣＲＴやプリンタなどのカラー装置は、３本もしくは４本の色信号に基づいて動作し、色を生成、表示する。ＣＲＴには、Ｒ（赤）、Ｇ（緑）、Ｂ（青）といった色信号が使用され、プリンタには、Ｃ（シアン）、Ｍ（マゼンタ）、Ｙ（黄）、付随的にＫ（黒）といった色信号を使用する。ＲＧＢやＣＭＹ信号を使用する色空間は装置依存色空間（ＤＤＣＳ）と呼ばれる。Ｒ，Ｇ，ＢやＣ，Ｍ，Ｙの各信号は、通常は０から２５５の整数で規定される。プリンタの場合をとれば、Ｃ，Ｍ，Ｙの信号範囲は、装置の色範囲立方体つまり図１の色立方体１０によって形成される。この立方体１０の中には、合計２５６×２５６×２５６（約１６６０万個）通りのコード値または信号の組合わせが存在し、したがってプリンタは２５６×２５６×２５６種類の色を発生させることができる。プリンタが発生させた色を測定するには、発生する色の色パッチを物理的に測定する測定器が用いられ、測定の結果が、標準ＣＩＥＸＹＺ色空間つまり独立色空間（ＤＩＣＳ）における位置（点）または色信号を決定する。続いて従来では、位置（点）または色信号は、標準ＣＩＥＬ＊ａ＊ｂ＊空間またはＣＩＥＬＵＶ空間といった、独立色空間（ＤＩＣＳ）内の点（あるいは色信号）に変換されることもある。２５６×２５６×２５６個の点からなる色立方体１０に占められる範囲（体積）は、ＣＩＥＬ＊ａ＊ｂ＊空間内の信号に変換されると、その装置の領域（ｇａｍｕｔ）１２と呼ばれる。装置の領域とは、その装置が（ＣＩＥＬ＊ａ＊ｂ＊空間内で）発生させることのできる全ての色を意味する。ＣＩＥＬ＊ａ＊ｂ＊空間つまり独立色空間に属する領域１２の境界に存在する色は、ＣＭＹつまり装置依存色空間に属する色立方体１０の表面を形作る信号値によって発生する。
【０００３】
【発明が解決しようとする課題】上記方法によれば、任意のプリンタの領域を正確に決定することができる。しかし、この方法では、約１６６０万個もの色パッチを測定する必要があり、実施は不可能に近い。少数の色パッチ（例えば５１２個）を測定して、それらを独立色空間（ＣＩＥＬ＊ａ＊ｂ＊）の点または信号に変換する方がより実用的である。通常、これらの色パッチに対する信号値が、立方体１０の全範囲を占める格子点として選択されると都合がよい。図２は、ＣＭＹおよびＣＩＥＬ＊ａ＊ｂ＊空間内の色パッチに対する色立方体格子点の分布を例示している。これらの点をテーブルの形で格納することにより、ＣＭＹからＣＩＥＬ＊ａ＊ｂ＊への、いわゆる参照テーブル（look-up table ）が得られる。この参照テーブルＬＵＴに基づき、補間法を使用して、任意に指定された点をこれらの２つの空間の間で写像することができる。
【０００４】図２からもわかるように、立方体１０に含まれる格子点は、規則正しく分布しているが、これらに対応する領域１２の点はばらばらに分布している。参照テーブルＬＵＴを使用すれば、高速かつ容易に、任意の位置にある色信号をＣＭＹからＣＩＥＬ＊ａ＊ｂ＊へ写像することができる。なぜなら、補間が行われる参照テーブルＬＵＴの点が格子点だからである。しかし、ＣＩＥＬ＊ａ＊ｂ＊からＣＭＹへの逆変換となるとそうはいかない。なぜなら、補間の出発点であるＣＩＥＬ＊ａ＊ｂ＊空間の点が格子点ではないからである。この逆変換を効率よく行うには、ＣＩＥＬ＊ａ＊ｂ＊格子点を出発点とした逆参照テーブルが必要とされる。逆参照テーブルを効率よく作成するには、領域境界を決定する必要があり、そして決定された領域境界が凝縮されれば、ＣＩＥＬ＊ａ＊ｂ＊空間に属するが領域１２の外部にある点を領域１２内の点に効率的に変換できるようになる。
【０００５】本発明は、上記実情に鑑みてなされたもので、領域境界点を任意の方向に沿って定義する方法を提供することを目的とする。
【０００６】また、本発明は、任意の装置の領域境界を記述する、領域記述子、つまり領域境界を簡略に表現したものを作成し使用することを目的とする。
【０００７】さらに、本発明は、ＣＭＹからＣＩＥＬ＊ａ＊ｂ＊への参照テーブルを使用して、領域記述子を作成する方法を提供することを目的とする。
【０００８】さらにまた、本発明は、与えられたベクトルが、ｄ次元ベクトル空間Ｒｄ内の凸多面錐（ＣＰＣ）によって包囲されているかどうかを判断する方法を提供することを目的とする。
【０００９】さらにまた、本発明は、３点で形成された平面と、その３点で形成された凸多面錐によって囲まれる線との交点を判定するための方法を提供することを目的とする。
【００１０】さらにまた、本発明は、２つの三次元空間内の２つの三角形の間における一対一の可逆補間方法を提供することを目的とする。
【００１１】さらにまた、本発明は、与えられた参照テーブルに基づき、三角形（平面）の集合を使用して領域境界を定義し構築する方法を提供することを目的とする。
【００１２】さらにまた、本発明は、与えられた点あるいは信号が領域内に入っているかどうかを判断するための方法を提供することを目的とする。
【００１３】
【課題を解決するための手段】上記目的を達成するために、本発明に係る方法は、領域記述子の作成方法であって、装置に依存しない独立色空間における所定のパターンの領域から領域境界信号を選択する段階と、これに対応する信号を装置依存色空間において決定する段階とを備えることを第１の特徴とする。
【００１４】また、本発明に係る方法は、上記特徴に加えて、前記選択する段階は、前記領域を、少なくとも所定の間隔で平行な平面に分割する過程と、前記平面ごとに、少なくとも所定の角度で間隔をおいた単位ベクトルを選択する過程と、前記単位ベクトルと領域境界との交点信号を決定する過程とを備えることを第２の特徴とする。
【００１５】さらに、本発明に係る装置は、領域記述子の作成装置であって、装置に特有の装置依存色空間から、装置に依存しない独立色空間に信号を変換するために、参照テーブルを読む入力手段と、境界三角形が列挙されている領域境界テーブルを上記参照テーブルから作成するためのテーブル作成手段と、上記三角形に囲まれた領域境界信号を選択するための境界手段と、各々の境界点に対して三角形補間を実行して領域記述子リストを作成するための補間手段とを有することを第３の特徴とする。
【００１６】
【実施例】以下、添付図面を参照して本発明の一実施例を説明する。
【００１７】本発明は、装置領域記述子を高速に作成するための方法を提供する。領域識別子を使用して逆参照テーブルＩＬＵＴを作成する。このテーブルは、装置に依存しない独立色空間ＤＩＣＳの点または信号を、装置依存色空間ＤＤＣＳの点に写像する。また、装置領域記述子は、逆参照テーブルＩＬＵＴが利用できないとき、独立色空間ＤＩＣＳから装置依存色空間ＤＤＣＳへの写像を高速化するために使用することができる。領域記述子は、独立色空間ＤＩＣＳ内の注意深く選択された装置領域境界点あるいは信号の小さな集合である。これらの点は、領域境界上に均一に分布し、領域の全ての範囲をカバーする。記述子点は、選択された装置独立空間がＣＩＥＬ＊ａ＊ｂ＊空間またはＣＩＥＬＵＶ空間であれば、軸Ｌ＊に対して垂直であって等間隔をおいた複数の平面内に位置し、各々の平面に対して等しい角度で位置することが好ましい。領域記述子における領域境界点のこのような分布パターンは、独立色空間ＤＩＣＳから装置依存色空間ＤＤＣＳへ高速で写像する際に有用な情報である。
【００１８】適用されるものによって、数百点から数千点の間で領域記述子の大きさを選択できる。画像や逆参照テーブルＩＬＵＴの大きさと比較し、領域記述子は小さな集合である。後述するように、領域記述子の計算にはあまり時間がかからない。
【００１９】図３に示されているように、本発明の実施例に係る装置は、サンワークステーションやアップルマッキントッシュのようなコンピュータ２０と、２台の出力装置としての第１及び第２の装置２２、２４とを備える。これらの出力装置は、製造者の異なるプリンタやＣＲＴであってもよい。このコンピュータには、画像、つまり、第１の装置２２で印刷あるいは表示する画像を作成するのに使用される色信号２８が記憶される。この画像に対する色信号は、第１の装置の装置依存色空間に属する色信号である。本発明装置は、このような画像を、第２の装置２４に対する装置依存色空間信号に変換するように設計される。この変換方法では、装置依存色空間内の色信号２８を独立色空間の色信号３０に変換する際に、従来の前進補間と第１の装置２２の参照テーブル３２とを使用する。後進補間を適用すれば、通常、第２の装置２４の色信号３４を独立色空間の色信号３０に変換する際に使用される参照テーブル３６を用いて、第２の装置２４に関する独立色空間の色信号３０を装置依存色空間の色信号に変換することができる。しかし、逆参照テーブル４０と前進補間とを使用して写像を行えば、変換ははるかに高速になる。逆参照テーブル４０を作成するには、第２の装置２４の参照テーブル３６と領域記述子３８とを使用する。逆参照テーブルＩＬＵＴ４０を効率的に作成する方法に関しては、１９９３年５月２８日に出願された米国特許出願第６８，９４１号といった関連出願において詳述され、また、色信号を独立空間から装置依存空間へ効率よく変換する方法については、１９９３年５月２８日に出願された米国特許出願第６８，８２３号といった関連出願において詳述される。もちろん、第２の装置２４のために記録された画像をプリンタ２２の画像へ変換する際に、本発明に係る領域記述子４２を使用してもよい。
【００２０】上記の領域記述子を作成するための手法を説明する前に、今後登場するいくつかのアルゴリズムについて説明する。
【００２１】Ｙ＝｛ｙ1 、ｙ2 、．．．、ｙn ｝を、ｄ次元のユークリッド空間Ｒｄにおける点の集合と仮定する。ＣＰＣ（Ｙ）として示されるＹの凸多面錐は、次式で定義されるＲｄ内の集合である。
【００２２】
【数１】
ＣＨ（Ｙ）として示されるＹの凸包は、次式で定義されるＲｄ内の集合である。
【数２】
ベクトルｙは、次式のようなｎ個の係数α1 、α2 、．．．、αn が存在すれば、錐体ＣＰＣ（Ｙ）によって囲まれる。
【００２３】
【数３】
図４は、ベクトルｙを囲む３点ｙ1 、ｙ2 、ｙ3 で定義された凸多面錐の一部を示す。他の部分は、点ｙ1 、ｙ2 、ｙ3 に関連付けられた３個のベクトルを無限に拡大することによって得られる無限範囲の部分である。ＣＰＣ（ｙ1 、ｙ2 、ｙ3 ）は、ベクトルｙ’をも囲む。
【００２４】任意のベクトルｙが、Ｒｄに含まれるＹ＝｛ｙ1 、ｙ2 、．．．、ｙn ｝によって定義される凸多面錐によって囲まれるかどうかは、次の手順１によって判定することができる。
【００２５】（１）手順１ｙがＣＰＣ（Ｙ）に含まれるかどうかを判定する。まず、ｙn+1 ＝（１、０、．．．、０）T ，．．．、ｙn+d ＝（０、０、．．．、１）T をｙ1 、ｙ2 、．．．、ｙn に加える。ここで、Ｔはベクトルの転置を示し、ｙn+1 、．．．ｙn+d は単位ベクトルである。
【００２６】次に、次の線形プログラミングを解く。即ち、
【数４】
を最小化する。但し、以下のことが条件とされる。
【００２７】
【数５】
最小化した値がゼロより大きければ、ｙはＣＰＣ（Ｙ）に含まれる（ｙは錐体によって囲まれない）。それ以外の場合には、ｙはＣＰＣ（Ｙ）に含まれないこととなり、この場合、手順１は上式（３）を満足するｎ個の係数α1 、α2 、．．．、αn を返す。
【００２８】手順１は、凸多面錐包含問題を解くための一般的な方法である。本発明で問題となるのは、ｄ＝ｎ＝３で、かつ錐体が三角形によって定義されるような特別な場合である。後述するように、この場合に必要となるのは、ベクトルによって定義された線と３点ｙ1 、ｙ2 、ｙ3 で形成された平面との交点を見つけることである。図４に示されるように、ｙがＣＰＣ（ｙ1 、ｙ2 、ｙ3 ）で囲まれていれば、次式を満足する３個の係数α1 、α2 、α3 を呼び戻す。
【００２９】
【数６】
式（４）の係数をα＝α1 ＋α2 ＋α3 で正規化すると、次式が得られる。
【００３０】
【数７】
式（５）は、点ｙが、３点ｙ1 、ｙ2 、ｙ3 の凸包で囲まれていることを示す。ｙ1 、ｙ2 、ｙ3 の凸包は三角形であるから、ｙ’はｙ1 、ｙ2 、ｙ3 で形成される平面内にあることとなる。交点の計算を次の手順２によって説明する。
【００３１】（２）手順２ｙで定義される線と、ｙ1 、ｙ2 、ｙ3 で形成される平面との交点を判定する。ここで、ｙはＣＰＣ（ｙ1 、ｙ2 、ｙ3 ）に含まれる。即ち、まず、手順１を適用して、式（４）を満足する３個の係数α1 、α2 、α3 を求める。次に、式（５）によって交点ｙ’を算出する。
【００３２】上記関連出願において、色較正のための凸補間方法が記述されている。以下に、Ｒ３の中に３個の点が存在する凸補間の特殊な場合について説明する。この場合、凸補間は、「三角形」補間と呼ばれる。図５に示されるように、ｙ1 、ｙ2、ｙ3 を独立空間ＣＩＥＬ＊ａ＊ｂ＊内の３点とし、これらに対応する装置依存空間ＣＭＹ内の三角形２４の点をｘ1 、ｘ2 、ｘ3 とする。ＣＩＥＬ＊ａ＊ｂ＊において、ｙ1 、ｙ2 、ｙ3 （三角形）の凸包内に存在する、つまりＣＨ（ｙ1、ｙ2 、ｙ3 ）に含まれる任意の点をｙとする。このシステムで必要となるのは、ＣＭＹ空間で対応する点ｘを補間によって計算することである。関連出願に詳述されている凸包包含手順を適用することにより、３個の係数α1 、α2 、α3が得られ、次式を満足する。
【００３３】
【数８】
つぎに、このシステムは次の三角形補間公式に従って補間を行う。
【００３４】
【数９】
以下の手順３では、ＣＩＥＬ＊ａ＊ｂ＊空間からＣＭＹ空間への三角形補間を詳述する。
【００３５】（３）手順３三角形補間により、ＣＨ（ｙ1 、ｙ2 、ｙ3 ）に含まれる任意の点ｙを補間する。まず、単位ベクトルｙ4 ＝（１、０、０）T 、ｙ5 ＝（０、１、０）T 、ｙ6 ＝（０、０、１）T をｙ1 、ｙ2 、ｙ3 に加える。次に、以下の既知の線形プログラミングを解く。
【００３６】
【数１０】
を最小化する。但し、
【数１１】
が条件とされる。
【００３７】続いて、ＣＨ（ｙ1 、ｙ2 、ｙ3 ）にｙが含まれることから、この手順は、式（６）を満足する３個の係数α1 、α2 、α3 を返すこととなる。
【００３８】最後に、式（７）により、ｘを算出する。
【００３９】三角形補間は、三角形ＣＨ（ｙ1 、ｙ2 、ｙ3 ）から三角形ＣＨ（ｘ1 、ｘ2、ｘ3 ）への一対一写像である。この写像は可逆である。つまり、ｙを三角形補間してｘが得られたならば、同じ手順でｘを補間すれば、ｙが得られる。
【００４０】つぎに領域境界について説明する。図２に示されるように、装置領域に対して使用可能な情報は、Ｎ3 個の入力項目を有する参照テーブルＬＵＴである（通常、Ｎは８から１１の範囲の値である）。ＣＭＹ空間における立方体１０の表面には、（６Ｎ2 −１２Ｎ＋８）個の入力項目が存在し、これと同数の点がＣＩＥＬ＊ａ＊ｂ＊空間における領域１２に存在する。このシステムで必要なことは、（６Ｎ2 −１２Ｎ＋８）個の点に基づいて領域境界を見積もり、領域記述子を作成することである。まず、領域境界の定義の方法について説明し、つぎに、領域記述子の算出方法について説明する。
【００４１】参照テーブルＬＵＴに属するＮ3 個の点は、ＣＭＹ空間における格子点であるから、立方体１０の６個の面の各々にはＮ2 個の点が存在する。これらの点は、各々の面を（Ｎ−１）2 個の正方形に区分けする（図７参照）。合計６（Ｎ−１）2 個の正方形が存在することになる。図６に示されるように、ＣＭＹ空間における正方形２６の四隅の点をｘ1 、．．．、ｘ4 とし、ｙ1 、．．．、ｙ4 をこれらに対応するＣＩＥＬ＊ａ＊ｂ＊空間における多角形２７の４点とする。図６に示されるように、正方形２６は、Ａ型またはＢ型の方法により、２つの三角形２８と３０、または三角形３２と３４とに分割される。４個の点ｙ1 、．．．、ｙ4 が１つの平面内に存在しない場合（通常の場合、曲面の領域境界を考えたとき）、領域境界において４点ｙ1 、．．．、ｙ4 で形成される部分は、一方の区画方法では凸形に導かれ、他方の区画方法では凹形に導かれる。ｙ1 とｙ3 の中点ｙ13と、ｙ2 とｙ4 の中点ｙ24とを算出し、これら中点から軸Ｌ＊への距離を比較すれば、凹形を形成する区画を決定できる。これらの正方形を三角形に分割するには、図６に示されるような通常の分割方法を使用すると便利であり、高速でもある。ＣＩＥＬ＊ａ＊ｂ＊空間における対応三角形は、平面と、その平面の外周部分とを画成し、これらにより領域が定義される。また、領域境界面を、小さな曲面の集合として把握してもよい。しかし、この場合、領域境界点を算出するにしても、任意の信号が領域内にあるかどうかを判断するにしても複雑さが増してしまう。
【００４２】このシステムで、６（Ｎ−１）2 個の正方形の各々を２つの三角形に分割するには、上記の通常の分割方法を使用することが好ましい。ＣＭＹ空間において合計１２（Ｎ−１）2 個の三角形、ＣＩＥＬ＊ａ＊ｂ＊空間においても同数の三角形を得る。ＣＭＹ空間における三角形を全て合わせると、図７に示される立方体１０の表面になり、ＣＩＥＬ＊ａ＊ｂ＊空間における三角形を全て合わせると、図８に示されている領域１２の境界になる。ここで、陰影の付いている三角形はそれぞれ両図において互いに対応している。これらの三角形は、つぎのように、三角形テーブル（表１）に格納することができる。
【００４３】
【表１】
上記のような方法で領域境界を定義することの利点は、ＣＭＹ空間における立体１０の表面上の点と、ＣＩＥＬ＊ａ＊ｂ＊空間における領域境界１２上の点との間に、１対１の対応関係が存在することである。後述するように、このような１対１の対応関係を判定することは容易である。手順４に、上記の説明を要約する。
【００４４】（４）手順４参照テーブルＬＵＴに基づき、三角形を使用して領域境界を構築する。まず、Ｎ3 個の入力項目を有する参照テーブルＬＵＴを読み込む。次に、６（Ｎ−１）2 個の参照テーブルＬＵＴの正方形の各々を２個の三角形に分割する。続いて、１２（Ｎ−１）2 対の三角形をテーブル（表１）に格納する。
【００４５】これで領域境界の定義が行われた。つぎに、ＣＩＥＬ＊ａ＊ｂ＊空間における任意の点ｙ＝（１，ａ，ｂ）が領域１２内に存在するかどうかを判定する方法について説明する。図９に示されるように、表１の各々の三角形ＣＨ（ｙi1，ｙi2，ｙi3）につき、原点Ｏ＝（０、０、０）を次式によりＯ´＝（１、０、０）に変換する。
【００４６】
【数１２】
つぎに、手順１を使用して、三角形ＣＨ（ｙ´i1，ｙ´i2，ｙ´i3）を求める。この三角形の凸多面錐はｙ´を囲む、つまりｙ´はＣＰＣ（ｙ´i1，ｙ´i2，ｙ´i3）に含まれる。続いて、手順２を適用して、線ｏ´ｙ´と、３点ｙ´i1，ｙ´i2，ｙ´i3で定義される平面との交点ｙ／ｉｎｔを求める。ＣＨ（ｙ´i1，ｙ´i2，ｙ´i3）＝ＣＨ（ｙi1，ｙi2，ｙi3）であるから、点ｙ（または信号）が領域の内部に存在するかどうかは、ｏ´ｙ／ｉｎｔ間の距離とｏ´ｙ´間の距離とを比較することで判断することができる。これを下記の手順５で説明する。
【００４７】（５）手順５任意の点ｙ＝（１、ａ，ｂ）が領域内に存在するかどうかを判定する。まず、手順４を適用して表１を算出する。次に、手順１を使用して、ｙ´がＣＰＣ（ｙ´i1，ｙ´i2，ｙ´i3）に含まれることを条件として、三角形ｙ´i1，ｙ´i2，ｙ´i3を表１から求める（式（８）はｙとｙ´との関係およびその他のベクトルとの関係を記述する）。続いて、手順２を使用して、線ｏ´ｙ´と三角形ｙ´i1，ｙ´i2，ｙ´i3との交点ｙ／ｉｎｔを求める。｜ｏ´−ｙ／ｉｎｔ｜＜｜ｏ´−ｙ´｜なら、ｙは領域の外に存在する。さもなければ、ｙは領域の中に存在する。
【００４８】つぎに、任意の装置に対して領域記述子を作成する方法について説明する。前述したように、装置の領域記述子は、ＣＩＥＬ＊ａ＊ｂ＊において注意深く選択された領域境界点の集合である。これらの点は、予め決められたパターンで分布する。例えば、軸Ｌ＊に対して垂直な複数の平面内に位置する場合もあり、各平面内の点を決められた数に固定する場合もあり、また平面内で隣接する２つの点の間の角度が一定の場合もある。以下に、一例をあげる。
【００４９】領域記述子を作成するには、図１０に示されるように、軸Ｌ＊に垂直なｋ個の平面Ｌ＊＝Ｌ1 、Ｌ2 、．．．、Ｌk を用いて領域１２の軸Ｌ＊を分割する。領域１２と平面Ｌ＊＝Ｌi との交わる部分は、図１１R>１に示されるように、規則性のない頂角を有する多角形５０になる。つぎに、この多角形の境界上で等しい中心角で点ｕ1 ，．．．，ｕs を選択する（もし、これらの点が多角形の境界から少し外れていれば、よりよい結果が得られるであろう）。ｕj の角度は、θj ＝（ｊ−１）×３６０／ｓ（度）で与えられ、ｊ＝１、２、．．．、ｓである。ｓ個の点により、平面Ｌ＊＝Ｌｉにおける領域境界がほぼ描かれる。このシステムによってこの手順が各々の平面に適用されると、合計ｋ×ｓ個の領域境界点が得られる。これらの点あるいは信号の各々につき、三角形補間（手順３）を使用し、ＣＭＹ空間に属する立体の表面においてこれらが対応する点あるいは信号を算出する。次のようなテーブル（表２）に全てのデータが格納される。
【００５０】
【表２】
要求される精度によってこの領域記述子の大きさが決まる。通常の適用では、ｋを２０前後に設定し、ｓを１８０前後に設定する。上記を手順６に要約する。
【００５１】（６）手順６参照テーブルＬＵＴに基づき、領域記述子（表２）を作成する。まず、手順４を適用して表１を得る。次に、平面の数ｋと、各々の平面における領域境界点の個数ｓを読み込む。続いて、各々の平面Ｌ＊＝Ｌi と、その平面内の各々の単位ベクトルｕ´j （ｕ´j の角度は［（ｊ−１）×３６０／ｓ］度である）につき、手順５を使用して、ｕ´j で定義された方向に沿った領域境界点ｕj を求める。このとき、手順５は次式を満足する３個の係数α1 、α2 、α3 を返す。
【００５２】
【数１３】
ここで、ｙt1、ｙt2、ｙt3は表１のｔ番目の三角形に対応する。ｕj を次式により補間する。
【００５３】
【数１４】
ここで、ｘt1、ｘt2、ｘt3は、ｙt1、ｙt2、ｙt3の対応点である。ｕj とｖj との対を表２に格納する。最後に、領域記述子テーブル（表２）を出力する。
【００５４】図１２から図１５は、領域記述子を作成するにあたって、前述した手順１ないし６の動作を１つの流れに結合して示したものである。図１２に示されるように、第１ステップ６０で、ＣＭＹ空間といった装置依存空間からＣＩＥＬ＊ａ＊ｂ＊空間といった、装置に依存しない独立空間へ点を変換するために、参照テーブルを読み出す。次のステップ６２で、要求される領域記述子の大きさを読み出す。ステップ６４で、領域境界に属する三角形テーブルを作成する。この作成の詳細な流れは図１３により説明される。三角形テーブルが作成されると、ステップ６５で１つの平面が選択され、ステップ６６で平面の中から単位ベクトルが選択され、ステップ６８でこの単位ベクトルに沿った領域境界点が補間係数とともに決定される。この動作の流れは、図１４に詳細に示されている。つぎに、システムは、ステップ７０で三角形補間を実行し、境界点に対するＣＭＹ空間における対応値を求める。対応値が決定されると、ステップ７２で、この一対の点が領域記述子テーブルに格納される。これ以上の平面および単位ベクトルを処理する必要がなければ、ステップ７６において領域記述子テーブルを出力する。
【００５５】領域境界テーブルの作成は、図１３に示されるように、ステップ９０において、分割する必要のある正方形を選択することから開始される。この選択は逐次的に行うことができる。この正方形は、ステップ９２において、前述したように２つの三角形に分割され、領域境界三角形テーブルに格納される。正方形がすべて処理されると、領域境界三角形テーブルは、ステップ９８において出力される。
【００５６】領域境界点を求めるために、システムは、図１４に示されるように、まず、ステップ１１０において、単位ベクトルを囲む領域境界テーブルに属する任意の三角形によって定義される凸多面錐を求める。この動作の流れは、図１５に詳細に示される。三角形が決定されると、ステップ１１２において、単位ベクトルと領域境界との交点を求めるのは容易である。
【００５７】図１５に示されている手順に従って、単位ベクトルを囲む三角形を求めるとき、三角形テーブル（表１）を検索して、包囲条件を満足できる三角形の候補を見つける必要がある。この検索を容易にするため、以下に示す三角形範囲テーブル（表３）を、前述の三角形テーブルの作成と同時に作成する。この表３は、必要に応じて、表１と結合することができる。
【００５８】
【表３】
このテーブルを使用する上で注意しなければならないことは、図９に示されるように平行移動される単位ベクトルは、Ｌ＊（明度）軸方向の値に結び付いていることである。このＬ＊値は、三角形範囲テーブルを走査するのに使用され、この単位ベクトルのＬ＊値が最小値および最大値間の三角形の範囲（Ｌ＊の範囲）に収まるといった条件を満たす三角形が選択される。また、単位ベクトルは、図１０に示されるように角度θにも関連付けられている。この角度は、三角形の中から最初の走査で見つかった候補を走査して、適当な角度範囲を有する三角形を最終候補として選択するのに使用される。最終候補の三角形が選択されると、３個の単位ベクトルがその三角形に加えられ、ステップ１２４において、従来の線形プログラミング方程式を解いて、正しい係数を求める。ステップ１２６において、線形プログラミング方程式に対する解が検証され、対象の関数が０に最小化されたかどうかが判定される。最小化された場合、ステップ１２８において、求められた係数が格納される。最小化されなかった場合、次の最終候補が三角形テーブル（表３）から読みだされ検査される。
【００５９】上記発明の詳細な説明により、本発明の多数の特徴が明らかになったと思う。加えて特許請求の範囲には、本発明の趣旨と範囲に含まれる本発明の特長がすべて記述されている。さらに、本発明には多数の変更が可能なことは当業者には明白なことから、本発明は上記の構成と動作に限定されものではなく、したがって、本発明の範囲内であれば、すべての適当な変更を加えることが可能である。
【００６０】
【発明の効果】以上のように本発明の第１の特徴によれば、装置に依存しない独立色空間の領域境界を決定して、独立色空間から装置依存色空間への前進補間に供する逆参照テーブルを容易に提供することができる。したがって、補間を用いて高速かつ容易に任意の位置にある色信号を独立色空間から装置依存色空間へと写像することができる。
【００６１】また、本発明の第２の特徴によれば、簡単な方法で領域境界を決定することができる。
【００６２】さらに、本発明の第３の特徴によれば、装置に依存しない独立色空間の領域境界を決定して、独立色空間から装置依存色空間への前進補間に供する逆参照テーブルを容易に提供することができる。したがって、補間を用いて高速かつ容易に任意の位置にある色信号を独立色空間から装置依存色空間へと写像することができる。
【図面の簡単な説明】
【図１】装置依存空間の色立方体と、これに対応する独立空間の領域とを示す図である。
【図２】立方体の格子点と、領域を形成する独立空間内の不規則に分布した、格子点に対応する点とを示す図である。
【図３】本発明のハードウェア構成要素を示す図である。
【図４】３つのベクトルｙ1 、ｙ2 、ｙ3 が形成する凸多面錐を示す図である。
【図５】装置依存空間の三角形と独立空間の三角形との対応を示す図である。
【図６】色立体表面の正方形を分割する方法を示す図である。
【図７】色立方体における任意の三角形を示す図である。
【図８】図７の三角形に対応した領域の三角形を示す図である。
【図９】三角形における境界点を示す図である。
【図１０】Ｌ＊に沿ってＫ個の平面で分割した領域を示す図である。
【図１１】単位ベクトルｕj ´と、単位ベクトルｕj ´の方向に沿った平面Ｌ上の領域境界点ｕj とを示す図である。
【図１２】本発明の動作を説明するためのフローチャートである。
【図１３】領域境界テーブルを作成する動作を説明するためのフローチャートである。
【図１４】領域境界点を見つけ出す動作を説明するためのフローチャートである。
【図１５】単位ベクトルを含む三角形を見つけ出す動作を説明するためのフローチャートである。
【符号の説明】
１０ 色立方体
１２ 領域
Ｌ 平面
【０００１】
【産業上の利用分野】本発明は、１つの色空間からの色データを他の色空間へ変換するために使用される領域記述子を作成する方法および装置に関し、より詳しくは、装置に依存しない独立した色空間における領域境界点の中から注意深く選択した点の集合を用いて高速で色較正を可能にするシステムに関する。
【０００２】
【従来の技術】ＣＲＴやプリンタなどのカラー装置は、３本もしくは４本の色信号に基づいて動作し、色を生成、表示する。ＣＲＴには、Ｒ（赤）、Ｇ（緑）、Ｂ（青）といった色信号が使用され、プリンタには、Ｃ（シアン）、Ｍ（マゼンタ）、Ｙ（黄）、付随的にＫ（黒）といった色信号を使用する。ＲＧＢやＣＭＹ信号を使用する色空間は装置依存色空間（ＤＤＣＳ）と呼ばれる。Ｒ，Ｇ，ＢやＣ，Ｍ，Ｙの各信号は、通常は０から２５５の整数で規定される。プリンタの場合をとれば、Ｃ，Ｍ，Ｙの信号範囲は、装置の色範囲立方体つまり図１の色立方体１０によって形成される。この立方体１０の中には、合計２５６×２５６×２５６（約１６６０万個）通りのコード値または信号の組合わせが存在し、したがってプリンタは２５６×２５６×２５６種類の色を発生させることができる。プリンタが発生させた色を測定するには、発生する色の色パッチを物理的に測定する測定器が用いられ、測定の結果が、標準ＣＩＥＸＹＺ色空間つまり独立色空間（ＤＩＣＳ）における位置（点）または色信号を決定する。続いて従来では、位置（点）または色信号は、標準ＣＩＥＬ＊ａ＊ｂ＊空間またはＣＩＥＬＵＶ空間といった、独立色空間（ＤＩＣＳ）内の点（あるいは色信号）に変換されることもある。２５６×２５６×２５６個の点からなる色立方体１０に占められる範囲（体積）は、ＣＩＥＬ＊ａ＊ｂ＊空間内の信号に変換されると、その装置の領域（ｇａｍｕｔ）１２と呼ばれる。装置の領域とは、その装置が（ＣＩＥＬ＊ａ＊ｂ＊空間内で）発生させることのできる全ての色を意味する。ＣＩＥＬ＊ａ＊ｂ＊空間つまり独立色空間に属する領域１２の境界に存在する色は、ＣＭＹつまり装置依存色空間に属する色立方体１０の表面を形作る信号値によって発生する。
【０００３】
【発明が解決しようとする課題】上記方法によれば、任意のプリンタの領域を正確に決定することができる。しかし、この方法では、約１６６０万個もの色パッチを測定する必要があり、実施は不可能に近い。少数の色パッチ（例えば５１２個）を測定して、それらを独立色空間（ＣＩＥＬ＊ａ＊ｂ＊）の点または信号に変換する方がより実用的である。通常、これらの色パッチに対する信号値が、立方体１０の全範囲を占める格子点として選択されると都合がよい。図２は、ＣＭＹおよびＣＩＥＬ＊ａ＊ｂ＊空間内の色パッチに対する色立方体格子点の分布を例示している。これらの点をテーブルの形で格納することにより、ＣＭＹからＣＩＥＬ＊ａ＊ｂ＊への、いわゆる参照テーブル（look-up table ）が得られる。この参照テーブルＬＵＴに基づき、補間法を使用して、任意に指定された点をこれらの２つの空間の間で写像することができる。
【０００４】図２からもわかるように、立方体１０に含まれる格子点は、規則正しく分布しているが、これらに対応する領域１２の点はばらばらに分布している。参照テーブルＬＵＴを使用すれば、高速かつ容易に、任意の位置にある色信号をＣＭＹからＣＩＥＬ＊ａ＊ｂ＊へ写像することができる。なぜなら、補間が行われる参照テーブルＬＵＴの点が格子点だからである。しかし、ＣＩＥＬ＊ａ＊ｂ＊からＣＭＹへの逆変換となるとそうはいかない。なぜなら、補間の出発点であるＣＩＥＬ＊ａ＊ｂ＊空間の点が格子点ではないからである。この逆変換を効率よく行うには、ＣＩＥＬ＊ａ＊ｂ＊格子点を出発点とした逆参照テーブルが必要とされる。逆参照テーブルを効率よく作成するには、領域境界を決定する必要があり、そして決定された領域境界が凝縮されれば、ＣＩＥＬ＊ａ＊ｂ＊空間に属するが領域１２の外部にある点を領域１２内の点に効率的に変換できるようになる。
【０００５】本発明は、上記実情に鑑みてなされたもので、領域境界点を任意の方向に沿って定義する方法を提供することを目的とする。
【０００６】また、本発明は、任意の装置の領域境界を記述する、領域記述子、つまり領域境界を簡略に表現したものを作成し使用することを目的とする。
【０００７】さらに、本発明は、ＣＭＹからＣＩＥＬ＊ａ＊ｂ＊への参照テーブルを使用して、領域記述子を作成する方法を提供することを目的とする。
【０００８】さらにまた、本発明は、与えられたベクトルが、ｄ次元ベクトル空間Ｒｄ内の凸多面錐（ＣＰＣ）によって包囲されているかどうかを判断する方法を提供することを目的とする。
【０００９】さらにまた、本発明は、３点で形成された平面と、その３点で形成された凸多面錐によって囲まれる線との交点を判定するための方法を提供することを目的とする。
【００１０】さらにまた、本発明は、２つの三次元空間内の２つの三角形の間における一対一の可逆補間方法を提供することを目的とする。
【００１１】さらにまた、本発明は、与えられた参照テーブルに基づき、三角形（平面）の集合を使用して領域境界を定義し構築する方法を提供することを目的とする。
【００１２】さらにまた、本発明は、与えられた点あるいは信号が領域内に入っているかどうかを判断するための方法を提供することを目的とする。
【００１３】
【課題を解決するための手段】上記目的を達成するために、本発明に係る方法は、領域記述子の作成方法であって、装置に依存しない独立色空間における所定のパターンの領域から領域境界信号を選択する段階と、これに対応する信号を装置依存色空間において決定する段階とを備えることを第１の特徴とする。
【００１４】また、本発明に係る方法は、上記特徴に加えて、前記選択する段階は、前記領域を、少なくとも所定の間隔で平行な平面に分割する過程と、前記平面ごとに、少なくとも所定の角度で間隔をおいた単位ベクトルを選択する過程と、前記単位ベクトルと領域境界との交点信号を決定する過程とを備えることを第２の特徴とする。
【００１５】さらに、本発明に係る装置は、領域記述子の作成装置であって、装置に特有の装置依存色空間から、装置に依存しない独立色空間に信号を変換するために、参照テーブルを読む入力手段と、境界三角形が列挙されている領域境界テーブルを上記参照テーブルから作成するためのテーブル作成手段と、上記三角形に囲まれた領域境界信号を選択するための境界手段と、各々の境界点に対して三角形補間を実行して領域記述子リストを作成するための補間手段とを有することを第３の特徴とする。
【００１６】
【実施例】以下、添付図面を参照して本発明の一実施例を説明する。
【００１７】本発明は、装置領域記述子を高速に作成するための方法を提供する。領域識別子を使用して逆参照テーブルＩＬＵＴを作成する。このテーブルは、装置に依存しない独立色空間ＤＩＣＳの点または信号を、装置依存色空間ＤＤＣＳの点に写像する。また、装置領域記述子は、逆参照テーブルＩＬＵＴが利用できないとき、独立色空間ＤＩＣＳから装置依存色空間ＤＤＣＳへの写像を高速化するために使用することができる。領域記述子は、独立色空間ＤＩＣＳ内の注意深く選択された装置領域境界点あるいは信号の小さな集合である。これらの点は、領域境界上に均一に分布し、領域の全ての範囲をカバーする。記述子点は、選択された装置独立空間がＣＩＥＬ＊ａ＊ｂ＊空間またはＣＩＥＬＵＶ空間であれば、軸Ｌ＊に対して垂直であって等間隔をおいた複数の平面内に位置し、各々の平面に対して等しい角度で位置することが好ましい。領域記述子における領域境界点のこのような分布パターンは、独立色空間ＤＩＣＳから装置依存色空間ＤＤＣＳへ高速で写像する際に有用な情報である。
【００１８】適用されるものによって、数百点から数千点の間で領域記述子の大きさを選択できる。画像や逆参照テーブルＩＬＵＴの大きさと比較し、領域記述子は小さな集合である。後述するように、領域記述子の計算にはあまり時間がかからない。
【００１９】図３に示されているように、本発明の実施例に係る装置は、サンワークステーションやアップルマッキントッシュのようなコンピュータ２０と、２台の出力装置としての第１及び第２の装置２２、２４とを備える。これらの出力装置は、製造者の異なるプリンタやＣＲＴであってもよい。このコンピュータには、画像、つまり、第１の装置２２で印刷あるいは表示する画像を作成するのに使用される色信号２８が記憶される。この画像に対する色信号は、第１の装置の装置依存色空間に属する色信号である。本発明装置は、このような画像を、第２の装置２４に対する装置依存色空間信号に変換するように設計される。この変換方法では、装置依存色空間内の色信号２８を独立色空間の色信号３０に変換する際に、従来の前進補間と第１の装置２２の参照テーブル３２とを使用する。後進補間を適用すれば、通常、第２の装置２４の色信号３４を独立色空間の色信号３０に変換する際に使用される参照テーブル３６を用いて、第２の装置２４に関する独立色空間の色信号３０を装置依存色空間の色信号に変換することができる。しかし、逆参照テーブル４０と前進補間とを使用して写像を行えば、変換ははるかに高速になる。逆参照テーブル４０を作成するには、第２の装置２４の参照テーブル３６と領域記述子３８とを使用する。逆参照テーブルＩＬＵＴ４０を効率的に作成する方法に関しては、１９９３年５月２８日に出願された米国特許出願第６８，９４１号といった関連出願において詳述され、また、色信号を独立空間から装置依存空間へ効率よく変換する方法については、１９９３年５月２８日に出願された米国特許出願第６８，８２３号といった関連出願において詳述される。もちろん、第２の装置２４のために記録された画像をプリンタ２２の画像へ変換する際に、本発明に係る領域記述子４２を使用してもよい。
【００２０】上記の領域記述子を作成するための手法を説明する前に、今後登場するいくつかのアルゴリズムについて説明する。
【００２１】Ｙ＝｛ｙ1 、ｙ2 、．．．、ｙn ｝を、ｄ次元のユークリッド空間Ｒｄにおける点の集合と仮定する。ＣＰＣ（Ｙ）として示されるＹの凸多面錐は、次式で定義されるＲｄ内の集合である。
【００２２】
【数１】
ＣＨ（Ｙ）として示されるＹの凸包は、次式で定義されるＲｄ内の集合である。
【数２】
ベクトルｙは、次式のようなｎ個の係数α1 、α2 、．．．、αn が存在すれば、錐体ＣＰＣ（Ｙ）によって囲まれる。
【００２３】
【数３】
図４は、ベクトルｙを囲む３点ｙ1 、ｙ2 、ｙ3 で定義された凸多面錐の一部を示す。他の部分は、点ｙ1 、ｙ2 、ｙ3 に関連付けられた３個のベクトルを無限に拡大することによって得られる無限範囲の部分である。ＣＰＣ（ｙ1 、ｙ2 、ｙ3 ）は、ベクトルｙ’をも囲む。
【００２４】任意のベクトルｙが、Ｒｄに含まれるＹ＝｛ｙ1 、ｙ2 、．．．、ｙn ｝によって定義される凸多面錐によって囲まれるかどうかは、次の手順１によって判定することができる。
【００２５】（１）手順１ｙがＣＰＣ（Ｙ）に含まれるかどうかを判定する。まず、ｙn+1 ＝（１、０、．．．、０）T ，．．．、ｙn+d ＝（０、０、．．．、１）T をｙ1 、ｙ2 、．．．、ｙn に加える。ここで、Ｔはベクトルの転置を示し、ｙn+1 、．．．ｙn+d は単位ベクトルである。
【００２６】次に、次の線形プログラミングを解く。即ち、
【数４】
を最小化する。但し、以下のことが条件とされる。
【００２７】
【数５】
最小化した値がゼロより大きければ、ｙはＣＰＣ（Ｙ）に含まれる（ｙは錐体によって囲まれない）。それ以外の場合には、ｙはＣＰＣ（Ｙ）に含まれないこととなり、この場合、手順１は上式（３）を満足するｎ個の係数α1 、α2 、．．．、αn を返す。
【００２８】手順１は、凸多面錐包含問題を解くための一般的な方法である。本発明で問題となるのは、ｄ＝ｎ＝３で、かつ錐体が三角形によって定義されるような特別な場合である。後述するように、この場合に必要となるのは、ベクトルによって定義された線と３点ｙ1 、ｙ2 、ｙ3 で形成された平面との交点を見つけることである。図４に示されるように、ｙがＣＰＣ（ｙ1 、ｙ2 、ｙ3 ）で囲まれていれば、次式を満足する３個の係数α1 、α2 、α3 を呼び戻す。
【００２９】
【数６】
式（４）の係数をα＝α1 ＋α2 ＋α3 で正規化すると、次式が得られる。
【００３０】
【数７】
式（５）は、点ｙが、３点ｙ1 、ｙ2 、ｙ3 の凸包で囲まれていることを示す。ｙ1 、ｙ2 、ｙ3 の凸包は三角形であるから、ｙ’はｙ1 、ｙ2 、ｙ3 で形成される平面内にあることとなる。交点の計算を次の手順２によって説明する。
【００３１】（２）手順２ｙで定義される線と、ｙ1 、ｙ2 、ｙ3 で形成される平面との交点を判定する。ここで、ｙはＣＰＣ（ｙ1 、ｙ2 、ｙ3 ）に含まれる。即ち、まず、手順１を適用して、式（４）を満足する３個の係数α1 、α2 、α3 を求める。次に、式（５）によって交点ｙ’を算出する。
【００３２】上記関連出願において、色較正のための凸補間方法が記述されている。以下に、Ｒ３の中に３個の点が存在する凸補間の特殊な場合について説明する。この場合、凸補間は、「三角形」補間と呼ばれる。図５に示されるように、ｙ1 、ｙ2、ｙ3 を独立空間ＣＩＥＬ＊ａ＊ｂ＊内の３点とし、これらに対応する装置依存空間ＣＭＹ内の三角形２４の点をｘ1 、ｘ2 、ｘ3 とする。ＣＩＥＬ＊ａ＊ｂ＊において、ｙ1 、ｙ2 、ｙ3 （三角形）の凸包内に存在する、つまりＣＨ（ｙ1、ｙ2 、ｙ3 ）に含まれる任意の点をｙとする。このシステムで必要となるのは、ＣＭＹ空間で対応する点ｘを補間によって計算することである。関連出願に詳述されている凸包包含手順を適用することにより、３個の係数α1 、α2 、α3が得られ、次式を満足する。
【００３３】
【数８】
つぎに、このシステムは次の三角形補間公式に従って補間を行う。
【００３４】
【数９】
以下の手順３では、ＣＩＥＬ＊ａ＊ｂ＊空間からＣＭＹ空間への三角形補間を詳述する。
【００３５】（３）手順３三角形補間により、ＣＨ（ｙ1 、ｙ2 、ｙ3 ）に含まれる任意の点ｙを補間する。まず、単位ベクトルｙ4 ＝（１、０、０）T 、ｙ5 ＝（０、１、０）T 、ｙ6 ＝（０、０、１）T をｙ1 、ｙ2 、ｙ3 に加える。次に、以下の既知の線形プログラミングを解く。
【００３６】
【数１０】
を最小化する。但し、
【数１１】
が条件とされる。
【００３７】続いて、ＣＨ（ｙ1 、ｙ2 、ｙ3 ）にｙが含まれることから、この手順は、式（６）を満足する３個の係数α1 、α2 、α3 を返すこととなる。
【００３８】最後に、式（７）により、ｘを算出する。
【００３９】三角形補間は、三角形ＣＨ（ｙ1 、ｙ2 、ｙ3 ）から三角形ＣＨ（ｘ1 、ｘ2、ｘ3 ）への一対一写像である。この写像は可逆である。つまり、ｙを三角形補間してｘが得られたならば、同じ手順でｘを補間すれば、ｙが得られる。
【００４０】つぎに領域境界について説明する。図２に示されるように、装置領域に対して使用可能な情報は、Ｎ3 個の入力項目を有する参照テーブルＬＵＴである（通常、Ｎは８から１１の範囲の値である）。ＣＭＹ空間における立方体１０の表面には、（６Ｎ2 −１２Ｎ＋８）個の入力項目が存在し、これと同数の点がＣＩＥＬ＊ａ＊ｂ＊空間における領域１２に存在する。このシステムで必要なことは、（６Ｎ2 −１２Ｎ＋８）個の点に基づいて領域境界を見積もり、領域記述子を作成することである。まず、領域境界の定義の方法について説明し、つぎに、領域記述子の算出方法について説明する。
【００４１】参照テーブルＬＵＴに属するＮ3 個の点は、ＣＭＹ空間における格子点であるから、立方体１０の６個の面の各々にはＮ2 個の点が存在する。これらの点は、各々の面を（Ｎ−１）2 個の正方形に区分けする（図７参照）。合計６（Ｎ−１）2 個の正方形が存在することになる。図６に示されるように、ＣＭＹ空間における正方形２６の四隅の点をｘ1 、．．．、ｘ4 とし、ｙ1 、．．．、ｙ4 をこれらに対応するＣＩＥＬ＊ａ＊ｂ＊空間における多角形２７の４点とする。図６に示されるように、正方形２６は、Ａ型またはＢ型の方法により、２つの三角形２８と３０、または三角形３２と３４とに分割される。４個の点ｙ1 、．．．、ｙ4 が１つの平面内に存在しない場合（通常の場合、曲面の領域境界を考えたとき）、領域境界において４点ｙ1 、．．．、ｙ4 で形成される部分は、一方の区画方法では凸形に導かれ、他方の区画方法では凹形に導かれる。ｙ1 とｙ3 の中点ｙ13と、ｙ2 とｙ4 の中点ｙ24とを算出し、これら中点から軸Ｌ＊への距離を比較すれば、凹形を形成する区画を決定できる。これらの正方形を三角形に分割するには、図６に示されるような通常の分割方法を使用すると便利であり、高速でもある。ＣＩＥＬ＊ａ＊ｂ＊空間における対応三角形は、平面と、その平面の外周部分とを画成し、これらにより領域が定義される。また、領域境界面を、小さな曲面の集合として把握してもよい。しかし、この場合、領域境界点を算出するにしても、任意の信号が領域内にあるかどうかを判断するにしても複雑さが増してしまう。
【００４２】このシステムで、６（Ｎ−１）2 個の正方形の各々を２つの三角形に分割するには、上記の通常の分割方法を使用することが好ましい。ＣＭＹ空間において合計１２（Ｎ−１）2 個の三角形、ＣＩＥＬ＊ａ＊ｂ＊空間においても同数の三角形を得る。ＣＭＹ空間における三角形を全て合わせると、図７に示される立方体１０の表面になり、ＣＩＥＬ＊ａ＊ｂ＊空間における三角形を全て合わせると、図８に示されている領域１２の境界になる。ここで、陰影の付いている三角形はそれぞれ両図において互いに対応している。これらの三角形は、つぎのように、三角形テーブル（表１）に格納することができる。
【００４３】
【表１】
上記のような方法で領域境界を定義することの利点は、ＣＭＹ空間における立体１０の表面上の点と、ＣＩＥＬ＊ａ＊ｂ＊空間における領域境界１２上の点との間に、１対１の対応関係が存在することである。後述するように、このような１対１の対応関係を判定することは容易である。手順４に、上記の説明を要約する。
【００４４】（４）手順４参照テーブルＬＵＴに基づき、三角形を使用して領域境界を構築する。まず、Ｎ3 個の入力項目を有する参照テーブルＬＵＴを読み込む。次に、６（Ｎ−１）2 個の参照テーブルＬＵＴの正方形の各々を２個の三角形に分割する。続いて、１２（Ｎ−１）2 対の三角形をテーブル（表１）に格納する。
【００４５】これで領域境界の定義が行われた。つぎに、ＣＩＥＬ＊ａ＊ｂ＊空間における任意の点ｙ＝（１，ａ，ｂ）が領域１２内に存在するかどうかを判定する方法について説明する。図９に示されるように、表１の各々の三角形ＣＨ（ｙi1，ｙi2，ｙi3）につき、原点Ｏ＝（０、０、０）を次式によりＯ´＝（１、０、０）に変換する。
【００４６】
【数１２】
つぎに、手順１を使用して、三角形ＣＨ（ｙ´i1，ｙ´i2，ｙ´i3）を求める。この三角形の凸多面錐はｙ´を囲む、つまりｙ´はＣＰＣ（ｙ´i1，ｙ´i2，ｙ´i3）に含まれる。続いて、手順２を適用して、線ｏ´ｙ´と、３点ｙ´i1，ｙ´i2，ｙ´i3で定義される平面との交点ｙ／ｉｎｔを求める。ＣＨ（ｙ´i1，ｙ´i2，ｙ´i3）＝ＣＨ（ｙi1，ｙi2，ｙi3）であるから、点ｙ（または信号）が領域の内部に存在するかどうかは、ｏ´ｙ／ｉｎｔ間の距離とｏ´ｙ´間の距離とを比較することで判断することができる。これを下記の手順５で説明する。
【００４７】（５）手順５任意の点ｙ＝（１、ａ，ｂ）が領域内に存在するかどうかを判定する。まず、手順４を適用して表１を算出する。次に、手順１を使用して、ｙ´がＣＰＣ（ｙ´i1，ｙ´i2，ｙ´i3）に含まれることを条件として、三角形ｙ´i1，ｙ´i2，ｙ´i3を表１から求める（式（８）はｙとｙ´との関係およびその他のベクトルとの関係を記述する）。続いて、手順２を使用して、線ｏ´ｙ´と三角形ｙ´i1，ｙ´i2，ｙ´i3との交点ｙ／ｉｎｔを求める。｜ｏ´−ｙ／ｉｎｔ｜＜｜ｏ´−ｙ´｜なら、ｙは領域の外に存在する。さもなければ、ｙは領域の中に存在する。
【００４８】つぎに、任意の装置に対して領域記述子を作成する方法について説明する。前述したように、装置の領域記述子は、ＣＩＥＬ＊ａ＊ｂ＊において注意深く選択された領域境界点の集合である。これらの点は、予め決められたパターンで分布する。例えば、軸Ｌ＊に対して垂直な複数の平面内に位置する場合もあり、各平面内の点を決められた数に固定する場合もあり、また平面内で隣接する２つの点の間の角度が一定の場合もある。以下に、一例をあげる。
【００４９】領域記述子を作成するには、図１０に示されるように、軸Ｌ＊に垂直なｋ個の平面Ｌ＊＝Ｌ1 、Ｌ2 、．．．、Ｌk を用いて領域１２の軸Ｌ＊を分割する。領域１２と平面Ｌ＊＝Ｌi との交わる部分は、図１１R>１に示されるように、規則性のない頂角を有する多角形５０になる。つぎに、この多角形の境界上で等しい中心角で点ｕ1 ，．．．，ｕs を選択する（もし、これらの点が多角形の境界から少し外れていれば、よりよい結果が得られるであろう）。ｕj の角度は、θj ＝（ｊ−１）×３６０／ｓ（度）で与えられ、ｊ＝１、２、．．．、ｓである。ｓ個の点により、平面Ｌ＊＝Ｌｉにおける領域境界がほぼ描かれる。このシステムによってこの手順が各々の平面に適用されると、合計ｋ×ｓ個の領域境界点が得られる。これらの点あるいは信号の各々につき、三角形補間（手順３）を使用し、ＣＭＹ空間に属する立体の表面においてこれらが対応する点あるいは信号を算出する。次のようなテーブル（表２）に全てのデータが格納される。
【００５０】
【表２】
要求される精度によってこの領域記述子の大きさが決まる。通常の適用では、ｋを２０前後に設定し、ｓを１８０前後に設定する。上記を手順６に要約する。
【００５１】（６）手順６参照テーブルＬＵＴに基づき、領域記述子（表２）を作成する。まず、手順４を適用して表１を得る。次に、平面の数ｋと、各々の平面における領域境界点の個数ｓを読み込む。続いて、各々の平面Ｌ＊＝Ｌi と、その平面内の各々の単位ベクトルｕ´j （ｕ´j の角度は［（ｊ−１）×３６０／ｓ］度である）につき、手順５を使用して、ｕ´j で定義された方向に沿った領域境界点ｕj を求める。このとき、手順５は次式を満足する３個の係数α1 、α2 、α3 を返す。
【００５２】
【数１３】
ここで、ｙt1、ｙt2、ｙt3は表１のｔ番目の三角形に対応する。ｕj を次式により補間する。
【００５３】
【数１４】
ここで、ｘt1、ｘt2、ｘt3は、ｙt1、ｙt2、ｙt3の対応点である。ｕj とｖj との対を表２に格納する。最後に、領域記述子テーブル（表２）を出力する。
【００５４】図１２から図１５は、領域記述子を作成するにあたって、前述した手順１ないし６の動作を１つの流れに結合して示したものである。図１２に示されるように、第１ステップ６０で、ＣＭＹ空間といった装置依存空間からＣＩＥＬ＊ａ＊ｂ＊空間といった、装置に依存しない独立空間へ点を変換するために、参照テーブルを読み出す。次のステップ６２で、要求される領域記述子の大きさを読み出す。ステップ６４で、領域境界に属する三角形テーブルを作成する。この作成の詳細な流れは図１３により説明される。三角形テーブルが作成されると、ステップ６５で１つの平面が選択され、ステップ６６で平面の中から単位ベクトルが選択され、ステップ６８でこの単位ベクトルに沿った領域境界点が補間係数とともに決定される。この動作の流れは、図１４に詳細に示されている。つぎに、システムは、ステップ７０で三角形補間を実行し、境界点に対するＣＭＹ空間における対応値を求める。対応値が決定されると、ステップ７２で、この一対の点が領域記述子テーブルに格納される。これ以上の平面および単位ベクトルを処理する必要がなければ、ステップ７６において領域記述子テーブルを出力する。
【００５５】領域境界テーブルの作成は、図１３に示されるように、ステップ９０において、分割する必要のある正方形を選択することから開始される。この選択は逐次的に行うことができる。この正方形は、ステップ９２において、前述したように２つの三角形に分割され、領域境界三角形テーブルに格納される。正方形がすべて処理されると、領域境界三角形テーブルは、ステップ９８において出力される。
【００５６】領域境界点を求めるために、システムは、図１４に示されるように、まず、ステップ１１０において、単位ベクトルを囲む領域境界テーブルに属する任意の三角形によって定義される凸多面錐を求める。この動作の流れは、図１５に詳細に示される。三角形が決定されると、ステップ１１２において、単位ベクトルと領域境界との交点を求めるのは容易である。
【００５７】図１５に示されている手順に従って、単位ベクトルを囲む三角形を求めるとき、三角形テーブル（表１）を検索して、包囲条件を満足できる三角形の候補を見つける必要がある。この検索を容易にするため、以下に示す三角形範囲テーブル（表３）を、前述の三角形テーブルの作成と同時に作成する。この表３は、必要に応じて、表１と結合することができる。
【００５８】
【表３】
このテーブルを使用する上で注意しなければならないことは、図９に示されるように平行移動される単位ベクトルは、Ｌ＊（明度）軸方向の値に結び付いていることである。このＬ＊値は、三角形範囲テーブルを走査するのに使用され、この単位ベクトルのＬ＊値が最小値および最大値間の三角形の範囲（Ｌ＊の範囲）に収まるといった条件を満たす三角形が選択される。また、単位ベクトルは、図１０に示されるように角度θにも関連付けられている。この角度は、三角形の中から最初の走査で見つかった候補を走査して、適当な角度範囲を有する三角形を最終候補として選択するのに使用される。最終候補の三角形が選択されると、３個の単位ベクトルがその三角形に加えられ、ステップ１２４において、従来の線形プログラミング方程式を解いて、正しい係数を求める。ステップ１２６において、線形プログラミング方程式に対する解が検証され、対象の関数が０に最小化されたかどうかが判定される。最小化された場合、ステップ１２８において、求められた係数が格納される。最小化されなかった場合、次の最終候補が三角形テーブル（表３）から読みだされ検査される。
【００５９】上記発明の詳細な説明により、本発明の多数の特徴が明らかになったと思う。加えて特許請求の範囲には、本発明の趣旨と範囲に含まれる本発明の特長がすべて記述されている。さらに、本発明には多数の変更が可能なことは当業者には明白なことから、本発明は上記の構成と動作に限定されものではなく、したがって、本発明の範囲内であれば、すべての適当な変更を加えることが可能である。
【００６０】
【発明の効果】以上のように本発明の第１の特徴によれば、装置に依存しない独立色空間の領域境界を決定して、独立色空間から装置依存色空間への前進補間に供する逆参照テーブルを容易に提供することができる。したがって、補間を用いて高速かつ容易に任意の位置にある色信号を独立色空間から装置依存色空間へと写像することができる。
【００６１】また、本発明の第２の特徴によれば、簡単な方法で領域境界を決定することができる。
【００６２】さらに、本発明の第３の特徴によれば、装置に依存しない独立色空間の領域境界を決定して、独立色空間から装置依存色空間への前進補間に供する逆参照テーブルを容易に提供することができる。したがって、補間を用いて高速かつ容易に任意の位置にある色信号を独立色空間から装置依存色空間へと写像することができる。
【図面の簡単な説明】
【図１】装置依存空間の色立方体と、これに対応する独立空間の領域とを示す図である。
【図２】立方体の格子点と、領域を形成する独立空間内の不規則に分布した、格子点に対応する点とを示す図である。
【図３】本発明のハードウェア構成要素を示す図である。
【図４】３つのベクトルｙ1 、ｙ2 、ｙ3 が形成する凸多面錐を示す図である。
【図５】装置依存空間の三角形と独立空間の三角形との対応を示す図である。
【図６】色立体表面の正方形を分割する方法を示す図である。
【図７】色立方体における任意の三角形を示す図である。
【図８】図７の三角形に対応した領域の三角形を示す図である。
【図９】三角形における境界点を示す図である。
【図１０】Ｌ＊に沿ってＫ個の平面で分割した領域を示す図である。
【図１１】単位ベクトルｕj ´と、単位ベクトルｕj ´の方向に沿った平面Ｌ上の領域境界点ｕj とを示す図である。
【図１２】本発明の動作を説明するためのフローチャートである。
【図１３】領域境界テーブルを作成する動作を説明するためのフローチャートである。
【図１４】領域境界点を見つけ出す動作を説明するためのフローチャートである。
【図１５】単位ベクトルを含む三角形を見つけ出す動作を説明するためのフローチャートである。
【符号の説明】
１０ 色立方体
１２ 領域
Ｌ 平面
【特許請求の範囲】
【請求項１】 領域記述子の作成方法であって、装置に依存しない独立色空間における所定のパターンの領域から領域境界信号を選択する段階と、これに対応する信号を装置依存色空間において決定する段階と、を備えることを特徴とする領域記述子の作成方法。
【請求項２】 請求項１記載の方法であって、前記選択する段階は、前記領域を、少なくとも所定の間隔で平行な平面に分割する過程と、前記平面ごとに、少なくとも所定の角度で間隔をおいた単位ベクトルを選択する過程と、前記単位ベクトルと領域境界との交点信号を決定する過程と、を備えることを特徴とする領域記述子の作成方法。
【請求項３】 領域記述子の作成装置であって、装置に特有の装置依存色空間から、装置に依存しない独立色空間に信号を変換するために、参照テーブルを読む入力手段と、境界三角形が列挙されている領域境界テーブルを上記参照テーブルから作成するためのテーブル作成手段と、上記三角形に囲まれた領域境界信号を選択するための境界手段と、各々の境界点に対して三角形補間を実行して領域記述子リストを作成するための補間手段と、を有することを特徴とする領域記述子の作成装置。
【請求項１】 領域記述子の作成方法であって、装置に依存しない独立色空間における所定のパターンの領域から領域境界信号を選択する段階と、これに対応する信号を装置依存色空間において決定する段階と、を備えることを特徴とする領域記述子の作成方法。
【請求項２】 請求項１記載の方法であって、前記選択する段階は、前記領域を、少なくとも所定の間隔で平行な平面に分割する過程と、前記平面ごとに、少なくとも所定の角度で間隔をおいた単位ベクトルを選択する過程と、前記単位ベクトルと領域境界との交点信号を決定する過程と、を備えることを特徴とする領域記述子の作成方法。
【請求項３】 領域記述子の作成装置であって、装置に特有の装置依存色空間から、装置に依存しない独立色空間に信号を変換するために、参照テーブルを読む入力手段と、境界三角形が列挙されている領域境界テーブルを上記参照テーブルから作成するためのテーブル作成手段と、上記三角形に囲まれた領域境界信号を選択するための境界手段と、各々の境界点に対して三角形補間を実行して領域記述子リストを作成するための補間手段と、を有することを特徴とする領域記述子の作成装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１３】
【図１２】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１３】
【図１２】
【図１４】
【図１５】
【公開番号】特開平７−３０７７４
【公開日】平成７年（１９９５）１月３１日
【国際特許分類】
【出願番号】特願平６−１１７２６１
【出願日】平成６年（１９９４）５月３０日
【出願人】（５９１２６４５４４）イーストマン・コダツク・カンパニー (2)
【公開日】平成７年（１９９５）１月３１日
【国際特許分類】
【出願日】平成６年（１９９４）５月３０日
【出願人】（５９１２６４５４４）イーストマン・コダツク・カンパニー (2)
[ Back to top ]