(57)【要約】【課題】色空間変換などに利用可能なデータ変換装置における回路規模を低減する。【解決手段】  データ変換装置において、Ｎ次元データの各成分を上位ビットと下位ビットに分割する分割手段と、Ｎ次元座標空間における位置に対応するデータをルックアップテーブル（ＬＵＴ）として記憶する記憶手段と、入力されたＮ次元データの座標を内部に含むＮ次元超四面体の（Ｎ＋１）個の頂点位置に対応するデータのアドレスを生成するアドレス生成手段と、生成されたアドレスに基づいて記憶手段に対し２回のアクセスを行うことにより記憶手段からデータを読み出す読出手段と、読出手段で読み出したデータと前記下位ビットの値とに基づいて補間演算を行い変換結果のデータとして出力する補間演算手段とを備え、記憶手段は超立方体の各頂点に対応するデータを２Ｎ−２個に分割し記憶していることを特徴とするデータ変換装置。【選択図】図１１
2007174392.tif 000002
【特許請求の範囲】
【請求項１】
各成分が複数ビットで表わされるＮ次元（Ｎは３以上の整数）データを入力し、該Ｎ次元データのＮ次元座標空間内の位置に応じたデータを出力するデータ変換装置であって、
Ｎ次元データの各成分を上位ビットと下位ビットに分割する分割手段と、
前記上位ビットにより取り得るＮ次元座標空間における位置に対応するデータをルックアップテーブル（ＬＵＴ）として記憶する記憶手段と、
入力された前記Ｎ次元データの座標を内部に含むＮ次元超四面体のＮ＋１個の頂点位置に対応するデータを、前記記憶手段に対し２回のアクセスを行うことにより読み出す読出手段と、
前記読出手段で読み出したデータと前記下位ビットの値とに基づいて補間演算を行い変換結果のデータとして出力する補間演算手段と、
を備え、
前記記憶手段は、前記Ｎ次元超四面体を含む超立方体の各頂点間のマンハッタン距離をＤ、前記超立方体の基準となる頂点から等マンハッタン距離にある各頂点の数をＮ、３次の二項分布の係数１、３、３、１で示されるデータ個数を示す要素をＧ（ｉ）（ｉは１〜２Ｎ−３）と定義したとき、
2007174392.tif 000006
となるようにＧ（ｉ）を設定し、Ｇ（ｉ）の第１、第３係数で示される個数の頂点に対応するデータを第（ｉ×２−１）番目のＬＵＴに格納し、Ｇ（ｉ）の第２、第４係数で示される個数の頂点に対応するデータを第（ｉ×２）番目のＬＵＴに格納することにより、前記超立方体の各頂点に対応するデータを２Ｎ−２個に分割し記憶している
ことを特徴とするデータ変換装置。
【請求項２】
前記読出手段は、前記上位ビットによりＮ次元超立方体を特定し、該Ｎ次元超立方体の頂点により構成される前記Ｎ次元超四面体を前記下位ビットにより特定することを特徴とする請求項１に記載のデータ変換装置。
【請求項３】
前記読出手段は、前記記憶手段における前記Ｎ次元超四面体のＮ＋１個の頂点位置に対応するデータが記憶されているアドレスを生成するアドレス生成手段を備えることを特徴とする請求項１または請求項２に記載のデータ変換装置。
【請求項４】
前記アドレス生成手段は、前記読出手段による前記記憶手段に対する２回のアクセスを識別するための情報を有するアドレスを生成することを特徴とする請求項３に記載のデータ変換装置。
【請求項５】
Ｎ次元座標空間における複数の位置に対応するデータをルックアップテーブル（ＬＵＴ）として記憶する記憶手段を備え、各成分が複数ビットで表わされるＮ次元（Ｎは３以上の整数）データを入力し、該Ｎ次元データのＮ次元座標空間内の位置に応じたデータを出力するデータ変換装置の制御方法であって、
Ｎ次元データの各成分を上位ビットと下位ビットに分割する分割工程と、
入力された前記Ｎ次元データの座標を内部に含むＮ次元超四面体のＮ＋１個の頂点位置に対応するデータを、前記記憶手段に対し２回のアクセスを行うことにより読み出す読出工程と、
前記読出工程で読み出したデータと前記下位ビットの値とに基づいて補間演算を行い変換結果のデータとして出力する補間演算工程と、
を備え、
前記記憶手段は、前記Ｎ次元超四面体を含む超立方体の各頂点間のマンハッタン距離をＤ、前記超立方体の基準となる頂点から等マンハッタン距離にある各頂点の数をＮ、３次の二項分布の係数１、３、３、１で示されるデータ個数を示す要素をＧ（ｉ）（ｉは１〜２Ｎ−３）と定義したとき、
2007174392.tif 000007
となるようにＧ（ｉ）を設定し、Ｇ（ｉ）の第１、第３係数で示される個数の頂点に対応するデータを第（ｉ×２−１）番目のＬＵＴに格納し、Ｇ（ｉ）の第２、第４係数で示される個数の頂点に対応するデータを第（ｉ×２）番目のＬＵＴに格納することにより、前記超立方体の各頂点に対応するデータを２Ｎ−２個に分割し記憶している
ことを特徴とするデータ変換装置の制御方法。
【請求項６】
Ｎ次元座標空間における複数の位置に対応するデータをルックアップテーブル（ＬＵＴ）として記憶する記憶手段を備え、各成分が複数ビットで表わされるＮ次元（Ｎは３以上の整数）データを入力し、該Ｎ次元データのＮ次元座標空間内の位置に応じたデータを出力するデータ変換装置の制御プログラムであって、
Ｎ次元データの各成分を上位ビットと下位ビットに分割する分割工程を実行するためのプログラムコードと、
入力された前記Ｎ次元データの座標を内部に含むＮ次元超四面体のＮ＋１個の頂点位置に対応するデータを、前記記憶手段に対し２回のアクセスを行うことにより読み出す読出工程を実行するためのプログラムコードと、
前記読出工程で読み出したデータと前記下位ビットの値とに基づいて補間演算を行い変換結果のデータとして出力する補間演算工程を実行するためのプログラムコードと、
を備え、
前記記憶手段は、前記Ｎ次元超四面体を含む超立方体の各頂点間のマンハッタン距離をＤ、前記超立方体の基準となる頂点から等マンハッタン距離にある各頂点の数をＮ、３次の二項分布の係数１、３、３、１で示されるデータ個数を示す要素をＧ（ｉ）（ｉは１〜２Ｎ−３）と定義したとき、
2007174392.tif 000008
となるようにＧ（ｉ）を設定し、Ｇ（ｉ）の第１、第３係数で示される個数の頂点に対応するデータを第（ｉ×２−１）番目のＬＵＴに格納し、Ｇ（ｉ）の第２、第４係数で示される個数の頂点に対応するデータを第（ｉ×２）番目のＬＵＴに格納することにより、前記超立方体の各頂点に対応するデータを２Ｎ−２個に分割し記憶している
ことを特徴とする制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、色空間変換などに利用可能なデータ変換技術に関するものである。
【背景技術】
【０００２】
近年、入力機器としては、スキャナ、ビデオカメラなどが普及し、一方、出力機器としては、インクジェット、染料熱昇華型あるいは電子写真などの方式を用いた、各種カラープリンタが普及している。ところで、これらのカラー入出力機器は、それぞれが固有の色空間を取り扱うようになっている。そのため、例えばあるスキャナで得たカラー画像データを、そのままカラープリンタに転送して印刷した場合、印刷されたカラー画像の色がスキャナによって読取られたオリジナルのカラー画像の色と一致することはほとんどない。このようなデバイス間での色再現性の問題を解決するため、入力デバイスの色空間を出力デバイスの色空間に変換する処理（以降、色空間変換と呼ぶ）が必要となる。そのため、色空間変換機能が各種入出力機器に搭載されている。
【０００３】
この色空間変換とは、入力γ補正，輝度濃度変換，マスキング，黒生成，ＵＣＲ，出力γ補正等を含む処理を指す。一般的には、入力デバイスの３色（例えば、レッド，ブルー，グリーン）のデジタル画像データを、出力デバイスの３色（例えば、シアン，マゼンタ，イエロー）あるいは４色（例えば、シアン，マゼンタ，イエロー，ブラック）のデジタル画像データに変換することが多い。また、電子写真方式の複写機などの場合、稼働時間とともにプリンタエンジンの色再現特性が変化するため、定期的なキャリブレーションが必要となる。このような場合は、入力デバイスの４色（例えば、ＣＭＹＫ）から出力デバイスの４色（例えば、ＣＭＹＫ）の変換も必要となる。色空間変換の実現方法として、予め入力値に対応する出力値をルックアップ・テーブル（以下、“ＬＵＴ”）としてメモリに記憶しておき、デジタル画像データの各入力画素に対しＬＵＴを参照し出力値を導出する方法がある。なお、このＬＵＴを用いた色空間変換方法では、ＬＵＴの記憶に必要なメモリ容量を削減するため補間演算を併用するのが一般的である。例えば、３色入力のデジタル画像データに対する色空間変換は三次元補間演算を用いて実現する。また、４色入力のデジタル画像データに対する色空間変換は、四次元補間演算を用いて実現する。
【０００４】
図１は、三次元ルックアップ・テーブル（３Ｄ−ＬＵＴ）を用い三次元補間演算を行なう色空間変換装置の機能ブロックを例示的に示す図である。デジタル画像信号（Ｒ、Ｇ、Ｂ）１０１の各成分は、データ分割部１１０により上位ビット１０２と下位ビット１０３に分離される。上位ビット１０２は３Ｄ−ＬＵＴ１２０から参照値ＲＤ１０４を読み出す際に利用される。また、下位ビット１０３は重み係数ｇとして補間演算に使用される。補間演算部１３０は重み係数ｇと参照値ＲＤ１０４との積和演算により出力値Ｘ１０５を導出している。このようにして、入力されたデジタル画像信号（Ｒ、Ｇ、Ｂ）１０１は色空間変換装置により変換され、出力値Ｘ１０５が得られる。
【０００５】
図２は、三次元の色空間（例えば、ＲＧＢ空間）を単位立体により分割した状態を示す図である。３Ｄ−ＬＵＴ１２０には、この単位立体の頂点に対応する色空間変換後のデータである参照値ＲＤ１０４が格納されている。つまり、デジタル画像信号１０１の各成分の上位ビット１０２により決定される色空間の座標に対応する単位立体を選択し（図２の網掛け部分）、この単位立体の頂点に対応する参照値ＲＤ１０４を補間演算に使用するのである。なお、このとき使用される三次元補間演算の方法としては四面体補間法がある。図３は、四面体補間法に用いられる６つのタイプの四面体を示す図である。四面体補間法では、入力されたデジタル画像信号１０１の座標が選択された単位立体内の（１）Ｔｙｐｅ０〜（６）Ｔｙｐｅ５のどの四面体内に属するかを判断し、属すると判断された四面体の頂点座標に対応する４つの参照値ＲＤ１０４を用い補間演算を行う。
【０００６】
さらに、三次元四面体補間法は多次元の場合に拡張可能である。以下に多次元超四面体補間法について説明する。図２に示す三次元直交座標に固定された空間を多次元化し、Ｎ次元直交座標に固定された空間にした場合、単位立体は多次元の単位超立体（Ｎ次元超立体、もしくは超六面体と呼ぶ）に多次元化される。そして、図３に示す三次元四面体補間法で使用された四面体は、この多次元化により超四面体と呼ばれるＮ＋１面体に多次元化される。この超四面体は、単位超立体の基準点と対角点を結ぶ線と、超立体の互いに直交し、かつ連結しているＮ本の稜線によって形成される。そして１つの単位超立体を分割し、Ｎ！個の超四面体を作ることができる。単位超立体から超四面体を切り出す過程で選択したＮ本の稜線は互いに垂直であり、Ｎ次元直交座標の各軸方向にそれぞれ平行であるため、各軸方向の出力変移量の線形和を基準点出力値に加算した値が多次元補間演算の出力となる。したがって、選択された稜線の両端点における参照値の差分値に、各稜線上での基準点からの距離を乗算して、それら乗算値を基準点の参照値に累積加算することで補間演算を行うことが出来る。
【０００７】
ところで、高速に３Ｄ−ＬＵＴから参照値を読み出し補間を実行する技術として、例えば以下の２つの技術が開示されている。双方ともに、多次元ＬＵＴを複数のサブメモリに分割記憶することで、参照値の読み出しを並列化しＮ次元補間演算を高速に処理している。
【０００８】
（ｉ）三次元立方体（トライリニア）補間法を高速に実行する技術（特許文献１）
この技術は、３Ｄ−ＬＵＴを８個の領域に分割記憶し、３Ｄ−ＬＵＴから参照値を並列に読み出すことで高速化を実現している。３Ｄ−ＬＵＴの８分割の方法を図４を用いて説明する。図４は、図２で示したＲＧＢ空間の一部分を切り出したものである。図中の８種のマーク（●、△、◇、▽、○、◆、■、◎）は、それぞれ同一の記憶領域に格納される参照値のＲＧＢ空間上での位置（格子点）を示している。つまり、●印で示されている位置の参照値は０番の記憶領域に格納される。同様に、△印は１番、◇印は２番、▽印は３番、○印は４番、◆印は５番、■印は６番、◎印は７番の記憶領域にそれぞれ格納される。そのため、単位立体の各頂点に対応する参照値がすべて異なるメモリに記憶されていることから、各頂点に対応する参照値を並列に読み出す際にアクセスが競合することはない。なお、各格子点における参照値は重複することなく均等に８個の記憶領域に格納されている。なお、以降では、多次元ＬＵＴを複数の記憶領域に格納する際の、それぞれの記憶領域を“サブメモリ”と呼ぶ。なお、上述の記述を用いて多次元補間演算を行なう際には、多次元ＬＵＴを２Ｎ個のサブメモリに分割記憶すればよい。
【０００９】
（ｉｉ）三次元四面体補間法を高速に実行する技術（特許文献２）
この技術は、３Ｄ−ＬＵＴを４つのサブメモリに分割記憶し、３Ｄ−ＬＵＴから参照値を並列に読み出すことで高速化を実現している。ただし、使用するサブメモリの数が（ｉ）の場合に比較しより少ない。図５は、図４と同じく図２で示したＲＧＢ空間の一部分を切り出したものである。図中の４種のマーク（●、◇、▽、◎）は、それぞれ同一の記憶領域に格納される参照値のＲＧＢ空間上での位置（格子点）を示している。つまり、●印で示されている位置の参照値は０番の記憶領域に格納される。同様に、◇印は１番、▽印は２番、◎印は３番の記憶領域にそれぞれ格納される。三次元四面体補間法の場合、選択された四面体の頂点に対応する４つの参照値を並列に読み出すことにより補間演算を高速化できる。また、（ｉ）の場合と同様、各格子点における参照値は重複することなく均等に４個のサブメモリに格納されている。なお、上述の記述を用いて多次元補間演算を行なう際には、Ｎ次元入力の超四面体（Ｎ＋１面体）補間法に対し、多次元ＬＵＴを（Ｎ＋１）個のサブメモリに分割記憶すればよい。
【００１０】
なお、図５に示した３Ｄ−ＬＵＴの分割においては、任意の四面体について各頂点に対応する参照値がすべて異なるメモリに記憶されていることから、各頂点に対応する参照値を並列に読み出す際にアクセスが競合することはない。このことを、図６を参照して説明する、
図６は、三次元四面体補間法における、基準点から対角点までの単位立体の各頂点を三次元マンハッタン距離Ｄｍを用いて分類した図である。なお、Ｎ次元直交座標に固定された空間上の２点Ａ，Ｂの距離を下記式で定義し、Ｎ次元マンハッタン距離Ｄｍとしている。
【００１１】
Ａの座標を（Ｘ０＜ｉ１＞，Ｘ１＜ｊ１＞，Ｘ２＜ｋ１＞，・・・ＸＮ−２＜ａ１＞，ＸＮ−１＜ｂ１＞）
Ｂの座標を（Ｘ０＜ｉ２＞，Ｘ１＜ｊ２＞，Ｘ２＜ｋ２＞，・・・ＸＮ−２＜ａ２＞，ＸＮ−１＜ｂ２＞）
とした時、
Ｄｍ＝｜Ｘ０＜ｉ１＞−Ｘ０＜ｉ２＞｜＋｜Ｘ１＜ｊ１＞−Ｘ１＜ｊ２＞｜＋｜Ｘ２＜ｋ１＞−Ｘ２＜ｋ２＞｜＋・・・＋｜ＸＮ−２＜ａ１＞−ＸＮ−２＜ａ２＞｜＋｜ＸＮ−１＜ｂ１＞−ＸＮ−１＜ｂ２＞｜
図に示されるように、マンハッタン距離Ｄｍ＝０となる基準点（Ｘ０＜ｉ＞，Ｘ１＜ｊ＞，Ｘ２＜ｋ＞）に対して、
マンハッタン距離Ｄｍ＝１となる点は（Ｘ０＜ｉ＋１＞，Ｘ１＜ｊ＞，Ｘ２＜ｋ＞）、（Ｘ０＜ｉ＞，Ｘ１＜ｊ＋１＞，Ｘ２＜ｋ＞）、（Ｘ０＜ｉ＞，Ｘ１＜ｊ＞，Ｘ２＜ｋ＋１＞）の３点、
マンハッタン距離Ｄｍ＝２となる点は（Ｘ０＜ｉ＋１＞，Ｘ１＜ｊ＋１＞，Ｘ２＜ｋ＞）、（Ｘ０＜ｉ＞，Ｘ１＜ｊ＋１＞，Ｘ２＜ｋ＋１＞）、（Ｘ０＜ｉ＋１＞，Ｘ１＜ｊ＞，Ｘ２＜ｋ＋１＞）の３点、
マンハッタン距離Ｄｍ＝３となる点は対角点である（Ｘ０＜ｉ＋１＞，Ｘ１＜ｊ＋１＞，Ｘ２＜ｋ＋１＞）の１点となる。
【００１２】
ところで、単位超立体から補間演算に使用する超四面体を選択する工程は、基準点からどの頂点を通って対角点に到達するかという経路選択問題と置き換えることが出来る。そのため、マンハッタン距離Ｄｍが同一の頂点群からは常に１つの頂点のみが選択される。つまり、マンハッタン距離が同一の頂点群を同じサブメモリに記憶した場合は、同一のサブメモリから異なる２頂点が同時には読み出されることはないことが分かる。そのため、前述したように同一のサブメモリへアクセスが競合することはないのである。図６において、Ｍｅｍ０，Ｍｅｍ１，…，Ｍｅｍ３と記載された太線で囲まれた頂点がそれぞれサブメモリに記憶されることになるため、三次元四面体補間法では、３Ｄ−ＬＵＴを４個のサブメモリに分割記憶できることが理解できる。
【００１３】
図７は、四次元超四面体補間法における、基準点から対角点までの単位立体の各頂点を四次元マンハッタン距離Ｄｍを用いて分類した図である。図７において、Ｍｅｍ０，Ｍｅｍ１，…，Ｍｅｍ４と記載された太線で囲まれた頂点がそれぞれサブメモリに記憶され、四次元超四面体補間法では、多次元ＬＵＴを５個のサブメモリに分割記憶できることが理解できる。
【特許文献１】米国特許４８３７７２２号明細書
【特許文献２】特開平１０−３０７９１１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、特許文献１に開示されている技術では、多次元四面体補間法を採用する場合、読み出し回路の規模が大きくなるという問題がある。なぜなら、補間演算に必要なＮ＋１個の参照値をサブメモリから並列読み出しするために、メモリインターフェースなどの周辺回路を２Ｎ個持つ必要があるからである。
【００１５】
一方、特許文献２に開示されている技術では、多次元四面体補間法を採用する場合、周辺回路はＮ＋１個に抑えられるため読み出し回路規模は小さい。しかし、Ｎが（２の冪乗−１）で表される数でないときは、サブメモリの個数が２の冪乗にならない。たとえばＮ＝４の場合、サブメモリの個数は５個となる。サブメモリの個数が２の冪乗でない場合、サブメモリをアクセスするためのアドレス生成をシフト演算やビットマスクだけでは実現できず、割り算器などを用いた複雑なアドレス生成回路が必要となる。また、一般的にメモリは２の冪乗のワード数を記憶可能な容量として製品化されているため、これらのメモリ製品を利用してサブメモリを構成する場合、メモリの使用に無駄が生じる。つまり、１ランク容量の大きなメモリ製品を使用する必要がある。さらに、補間演算においては、乗算器、引き算器、加算器が夫々３個づつ必要であり、ハードウエア規模の増大を招いていた。
【００１６】
本発明は上記問題点に鑑みなされたものであり、色空間変換などに利用可能なデータ変換装置における回路規模を低減することを目的としている。
【課題を解決するための手段】
【００１７】
各成分が複数ビットで表わされるＮ次元（Ｎは３以上の整数）データを入力し、Ｎ次元データのＮ次元座標空間内の位置に応じたデータを出力するデータ変換装置において、Ｎ次元データの各成分を上位ビットと下位ビットに分割する分割手段と、上位ビットにより取り得るＮ次元座標空間における位置に対応するデータをルックアップテーブル（ＬＵＴ）として記憶する記憶手段と、入力されたＮ次元データの座標を内部に含むＮ次元超四面体のＮ＋１個の頂点位置に対応するデータを記憶手段に対し２回のアクセスを行うことにより読み出す読出手段と、読出手段で読み出したデータと下位ビットの値とに基づいて補間演算を行い変換結果のデータとして出力する補間演算手段とを備え、記憶手段はＮ次元超四面体を含む超立方体の頂点間のマンハッタン距離をＤ、前記超立方体の基準となる頂点から等マンハッタン距離にある各頂点の数をＮ、３次の二項分布の係数１、３、３、１で示されるデータ個数を示す要素をＧ（ｉ）（ｉは１〜２Ｎ−３）と定義したとき、
2007174392.tif 000003
となるようにＧ（ｉ）を設定し、Ｇ（ｉ）の第１、第３係数で示される個数の頂点に対応するデータを第（ｉ×２−１）番目のＬＵＴに格納し、Ｇ（ｉ）の第２、第４係数で示される個数の頂点に対応するデータを第（ｉ×２）番目のＬＵＴに格納することにより、超立方体の各頂点に対応するデータを２Ｎ−２個に分割し記憶している。
【００１８】
そして、読出手段は、上位ビットによりＮ次元超立方体を特定し、Ｎ次元超立方体の頂点により構成されるＮ次元超四面体を下位ビットにより特定する。
【００１９】
さらに、読出手段は、記憶手段におけるＮ次元超四面体のＮ＋１個の頂点位置に対応するデータが記憶されているアドレスを生成するアドレス生成手段を備える。
【００２０】
そして、アドレス生成手段は、読出手段による記憶手段に対する２回のアクセスを識別するための情報を有するアドレスを生成する。
【００２１】
Ｎ次元座標空間における複数の位置に対応するデータをルックアップテーブル（ＬＵＴ）として記憶する記憶手段を備え、各成分が複数ビットで表わされるＮ次元（Ｎは３以上の整数）データを入力し、Ｎ次元データのＮ次元座標空間内の位置に応じたデータを出力するデータ変換装置の制御方において、Ｎ次元データの各成分を上位ビットと下位ビットに分割する分割工程と、入力されたＮ次元データの座標を内部に含むＮ次元超四面体のＮ＋１個の頂点位置に対応するデータを記憶手段に対し２回のアクセスを行うことにより読み出す読出工程と、読出工程で読み出したデータと下位ビットの値とに基づいて補間演算を行い変換結果のデータとして出力する補間演算工程とを備え、記憶手段はＮ次元超四面体を含む超立方体の頂点間のマンハッタン距離をＤ、前記超立方体の基準となる頂点から等マンハッタン距離にある各頂点の数をＮ、３次の二項分布の係数１、３、３、１で示されるデータ個数を示す要素をＧ（ｉ）（ｉは１〜２Ｎ−３）と定義したとき、
2007174392.tif 000004
となるようにＧ（ｉ）を設定し、Ｇ（ｉ）の第１、第３係数で示される個数の頂点に対応するデータを第（ｉ×２−１）番目のＬＵＴに格納し、Ｇ（ｉ）の第２、第４係数で示される個数の頂点に対応するデータを第（ｉ×２）番目のＬＵＴに格納することにより、超立方体の各頂点に対応するデータを２Ｎ−２個に分割し記憶している。
【００２２】
Ｎ次元座標空間における複数の位置に対応するデータをルックアップテーブル（ＬＵＴ）として記憶する記憶手段を備え、各成分が複数ビットで表わされるＮ次元（Ｎは３以上の整数）データを入力し、Ｎ次元データのＮ次元座標空間内の位置に応じたデータを出力するデータ変換装置の制御プログラムにおいて、Ｎ次元データの各成分を上位ビットと下位ビットに分割する分割工程を実行するためのプログラムコードと、入力されたＮ次元データの座標を内部に含むＮ次元超四面体のＮ＋１個の頂点位置に対応するデータを記憶手段に対し２回のアクセスを行うことにより読み出す読出工程を実行するためのプログラムコードと、読出工程で読み出したデータと下位ビットの値とに基づいて補間演算を行い変換結果のデータとして出力する補間演算工程を実行するためのプログラムコードとを備え、記憶手段はＮ次元超四面体を含む超立方体の頂点間のマンハッタン距離をＤ、前記超立方体の基準となる頂点から等マンハッタン距離にある各頂点の数をＮ、３次の二項分布の係数１、３、３、１で示されるデータ個数を示す要素をＧ（ｉ）（ｉは１〜２Ｎ−３）と定義したとき、
2007174392.tif 000005
となるようにＧ（ｉ）を設定し、Ｇ（ｉ）の第１、第３係数で示される個数の頂点に対応するデータを第（ｉ×２−１）番目のＬＵＴに格納し、Ｇ（ｉ）の第２、第４係数で示される個数の頂点に対応するデータを第（ｉ×２）番目のＬＵＴに格納することにより、超立方体の各頂点に対応するデータを２Ｎ−２個に分割し記憶している。
【発明の効果】
【００２３】
本発明によれば、色空間変換などに利用可能なデータ変換装置における回路規模の低減を可能とする技術を提供することができる。
【発明を実施するための最良の形態】
【００２４】
以下に、図面を参照して、この発明の好適な実施の形態を例示的に詳しく説明する。ただし、この実施の形態に記載されている構成要素はあくまで例示であり、この発明の範囲をそれらのみに限定する趣旨のものではない。
【００２５】
（第１実施形態）
＜概要＞
第１実施形態ではカラー複写機に搭載された３次元（ＲＧＢ）入力の色空間変換装置について説明する。ここでは、補間演算に必要な四面体の４頂点に対応する参照値を２回のルックアップテーブル（ＬＵＴ）参照サイクルにより読み出す。また、四面体の基準頂点からのマンハッタン距離の偶奇に基づきＬＵＴを分割記憶している。このように構成することにより、ＬＵＴの分割数を２個に抑制すると共に、分割個数を２のべき乗に設定可能となり、回路規模の低減が可能となる。
【００２６】
＜装置構成＞
図８は、第１実施形態に係るカラー複写機８００の例示的な内部構成図である。カラー複写機８００は、画像読取部８２０、画像処理部８３０、プリンタ部８４０、および、各部を制御する制御部８１０から構成されている。
【００２７】
画像読取部８２０は、ＣＣＤセンサ８２４、アナログ信号処理部８２６等により構成される。レンズ８２２を介しＣＣＤセンサ８２４に結像された原稿の画像が、ＣＣＤセンサ８２４によりＲ，Ｇ，Ｂのアナログ電気信号に変換される。アナログ電気信号に変換された画像情報は、アナログ信号処理部８２６に入力され、Ｒ，Ｇ，Ｂの各色毎に補正等が行われた後にアナログ・デジタル変換（Ａ／Ｄ変換）される。デジタル化されたフルカラー信号（以下、デジタル画像信号という）は、画像処理部８３０に入力される。
【００２８】
画像処理部８３０は、入力されたデジタル画像信号に対し、入力γ補正、色空間変換、濃度補正、スクリーン処理を施し、プリンタ部８４０へ処理後のデジタル画像信号を出力する。なお、色空間変換処理の詳細については後述する。
【００２９】
プリンタ部８４０は、例えば、不図示の、レーザ等からなる露光制御部、画像形成部、転写紙の搬送制御部等により構成され、入力されたデジタル画像信号により転写紙上に画像を記録する。
【００３０】
制御部８１０は、演算制御用のＣＰＵ８１２、固定データやプログラムを格納するＲＯＭ８１４、データの一時保存やプログラムのロードに使用されるＲＡＭ８１６等により構成される。そして、画像読取部８２０、画像処理部８３０、プリンタ部８４０等を制御し、本装置のシーケンスを統括的に制御する。外部記憶装置８１８は、本装置が使用するパラメータやプログラムを記憶するＨＤＤ等の装置である。ＲＡＭ８１６のデータやプログラム等は、外部記憶装置８１８からロードされる構成としても構わない。
【００３１】
＜色空間変換処理＞
図９は、第１実施形態に係る画像処理部８３０内の色空間変換部のブロック構成図である。以下、図９を参照し画像処理部８３０で行なわれる色空間変換処理について説明する。
【００３２】
画像処理部８３０内の色空間変換部はＮ次元の入力信号に対し、ＬＵＴから読み取った参照値と補間演算とを利用して新たな信号を出力する。
【００３３】
データ分割部９１０には前述のデジタル画像信号９０５が入力される。このデジタル画像信号９０５はＮ本の入力信号である。データ分割部９１０は、デジタル画像信号９０５を上位ビット信号９１２と下位ビット信号９１４に分割する。デジタル画像信号９０５がＮ本の入力信号であるため、データ分割後の上位ビット信号９１２と下位ビット信号９１４はともにＮ本の信号となる。
【００３４】
例えば、上位ビット信号９１２は、補間演算のときに使用される単位超立体の個数に応じてそのビット数（ビット長）が決定される。たとえば、Ｎ次元空間のある軸について単位超立体が２ｘ−１個ある場合、その軸に対応する上位ビット信号９１２のビット数はｘビットとなる。なお、下位ビット信号９１４は、デジタル画像信号９０５のビット数から上位ビット信号９１２のビット数を差し引いた、残りのビット数で表現される。
【００３５】
順序判定部９３０は、Ｎ本の下位ビット信号９１４を受け取り、下位ビット信号９１４の大小関係を判定し、順序信号９３２として出力する。この順序信号９３２は、前述の単位超立体から補間演算に使用する超四面体（Ｎ＋１面体）の稜線を選択する工程に従い、予め定められたＮ！通りの稜線選択パターンを指し示す信号である。
【００３６】
重み係数算出部９４０は、下位ビット信号９１４をもとに補間演算の重み係数信号９４２を算出し、補間演算部９７０に出力する。このとき下位ビット信号９１４から重み係数９４２を算出する方法は、対応表を予めテーブル化し、テーブルから重み係数９４２を読み出すことで変換しても良いし、予め定められた計算式を用いて導出しても良い。
【００３７】
参照値読み出し部９５０は、Ｎ本の上位ビット信号９１２と参照信号９３２とに基づいて多次元ＬＵＴ９６０からＮ＋１個の参照値を２以上のサイクルで読み出し、参照値信号９５２として出力する。多次元ＬＵＴ９６０は複数個のサブメモリで実現されており、参照値読み出し部９５０はサブメモリの個数と等しい本数のアドレス信号９５４を各サブメモリに出力して各サブメモリをアクセスし、各サブメモリからデータ信号９６２を受け取る。
【００３８】
補間演算部９７０は、Ｎ＋１本の参照値信号９５２とＮ本の重み係数信号９４２を受け、前述した補間演算式に従い補間演算を行い、１本以上の出力信号９７５を出力する。
【００３９】
＜多次元ＬＵＴおよび参照値読み出し部＞
次に、多次元ＬＵＴ９６０および参照値読み出し部９５０についてさらに詳しく説明する。第１実施形態では、Ｎ＝３である場合に用いられる三次元ルックアップ・テーブル（以下、“３Ｄ−ＬＵＴ”と呼ぶ）の構成方法について説明する。
【００４０】
図１０は、図２で示したＲＧＢ空間の一部分を切り出したものである。図中の２種のマーク（●、◇）は、それぞれ同一の記憶領域に格納される参照値のＲＧＢ空間上での位置（格子点）を示している。つまり、●印で示されている位置の参照値は０番の記憶領域に格納され、◇印は１番の記憶領域に格納される。例えば、三次元四面体補間法の場合、基準点を頂点１０００とすると、頂点１０００の参照値、およびと、対角点側頂点（頂点２）である３個の頂点１００４，１００５，１００６の計４個の参照値を同一のメモリＭｅｍ０に格納する。また、基準値側頂点（頂点１）である３個の頂点１００１，１００２，１００３の参照値、および、対角点１００７の計４個の参照値を同一のメモリＭｅｍ１に格納する。そして、後述するように、選択された四面体の頂点に対応する４つの参照値を２回の読み出しサイクルにより読み出す。
【００４１】
図１１は、参照値読み出し部１１０１および３Ｄ−ＬＵＴ１１００の内部構成を例示的に示す図である。なお、参照値読み出し部１１０１および３Ｄ−ＬＵＴ１１００はそれぞれ、図９の参照値読み出し部９５０および多次元ＬＵＴ９６０に相当する。
【００４２】
１１０２はアドレス生成回路であり、１１０３，１１０４，１１０５の３個のデジタル画像信号の上位ビット信号Ｒｈ［ｘ−１：０］，Ｇｈ［ｘ−１：０］，Ｂｈ［ｘ−１：０］であり、１１０６は図９の９３２に対応する順序信号である。ここで、ｘは前述のビット数を示している。１１０７，１１０８は３次元補間の基準点又は対角点側頂点（頂点２），基準値側頂点（頂点１）又は対角点のそれぞれの参照値をメモリから読み出すためのアドレス信号ＭＡ０，ＭＡ１である。また、１１０９，１１１０はそれぞれ、アドレス選択回路１１１１，１１１２及び、データ選択回路１１１９，１１２０の選択信号となる、サブメモリ・バンク選択信号ＳＥＬ０，ＳＥＬ１である。
【００４３】
そして、１１１５，１１１６はそれぞれサブメモリ（Ｍｅｍ０），サブメモリ（Ｍｅｍ１）であり、１１１１，１１１２はそれぞれ、サブメモリ１１１５，１１１６のアドレス選択回路である。１１１３，１１１４はそれぞれ、アドレス選択回路１１１１，１１１２から出力されたアドレス信号であり、それぞれサブメモリ１１１５，１１１６に供給される。
【００４４】
また、１１１９，１１２０はそれぞれデータ選択回路である。１１１７，１１１８はそれぞれサブメモリ１１１５，１１１６からの出力データ信号ＭＤ０，ＭＤ１であり、全てのデータ選択回路１１１９，１１２０に供給される。１１２１，１１２２は図９の９５２に対応する信号であり、それぞれ、３次元補間の基準点又は頂点２，頂点１又は対角点の参照値を示す。また、１１２３は図示していない制御部で生成される、メモリの時分割処理のサイクルを制御するための制御信号ＣＳＥＬであり、アドレス生成回路１１０２に入力される。
【００４５】
次に、図１１の動作を説明する。アドレス生成回路１１０２が３個の信号Ｒｈ［ｘ−１：０］，Ｇｈ［ｘ−１：０］，Ｂｈ［ｘ−１：０］を受けて、２組のアドレス信号ＭＡ０，ＭＡ１とサブメモリ・バンク選択信号ＳＥＬ０，ＳＥＬ１［１：０］を出力する。ここで、２本のメモリ・バンク選択信号は、各々が異なる値である。
【００４６】
そして、アドレス信号ＭＡ０，ＭＡ１とサブメモリ・バンク選択信号ＳＥＬ０，ＳＥＬ１が全てのアドレス選択回路１１１１，１１１２に入力される。各アドレス選択回路１１１１，１１１２は各々が異なるサブメモリ・バンクＩＤ“ＳｍＢ＿ＩＤ”を有している。そして、自らが対応するサブメモリ・バンクＩＤ“ＳｍＢ＿ＩＤ”と入力されたサブメモリ・バンク選択信号が等しいアドレス信号を２本の中から１つ選択して出力し、サブメモリにアクセスする。サブメモリ１１１５，１１１６はそれぞれ受け取ったアドレス値１１１３，１１１４の格子点データを出力データ信号１１１７，１１１８として全てのデータ選択回路１１１９，１１２０に供給する。データ選択回路１１１９，１１２０ではそれぞれ入力されているサブメモリ・バンク選択信号ＳＥＬ０，ＳＥＬ１にしたがって、２本のサブメモリの出力から１本を選択して、参照データ１１２１，１１２２として出力する。
【００４７】
＜参照点読み出しおよびアドレスの生成＞
図１２は、参照値読み出し部１１０１が３Ｄ−ＬＵＴ１１００から４個の参照値を２サイクルで読み出す際のタイミングチャートである。
【００４８】
１２００はクロック信号ＣＬＫである。１２０１は制御信号ＣＳＥＬである。１２０２はサブメモリ・バンク選択信号ＳＥＬ０、１２０３はサブメモリ・バンク選択信号ＳＥＬ１である。１２０４はアドレス信号ＭＡ０、１２０５はデータ信号ＭＤ０、１２０６はアドレス信号ＭＡ１、１２０７はデータ信号ＭＤ１である。１２０８は出力信号１１２１、１２０９は出力信号１１２２のタイミングチャートを夫々示す。なお、５１０はタイミングチャートの動作を説明する為に付したサイクル番号を示す。
【００４９】
ここで、図１１で示した参照データ読み出し部及びＬＵＴは、クロック信号ＣＬＫの立ち上がり同期で動作するものとし、１２０１〜１２０９の各信号は、クロック信号ＣＬＫの立ち上がりに同期して変化するものとする。
【００５０】
制御信号ＣＳＥＬは、クロック信号１サイクルごとに変化し、上記２サイクルで参照データをを読み出す動作中で何サイクル目であるかを示している。また、サブメモリ・バンク選択信号ＳＥＬ０及びＳＥＬ１は後述する演算により生成される信号であり、２サイクルごとに値が変化する信号である。アドレス信号ＭＡ０は基準点又は頂点２の参照値をサブメモリから読み出すためのアドレス信号であり、制御信号ＣＳＥＬが’０’のときは、基準点のアドレス値を、’１’の時は頂点２のアドレス値を出力する。一方、アドレス信号ＭＡ１は頂点１又対角点の参照値をサブメモリから読み出すためのアドレス信号であり、制御信号ＣＳＥＬが’０’のときは、対角点のアドレス値を、’１’の時は頂点１のアドレス値を出力する。
【００５１】
まず、サブメモリ・バンク選択信号ＳＥＬ０が’０’（ＳＥＬ１は’１’）の場合に関してサブメモリから参照値を読み出す動作を説明する。
【００５２】
基準点の参照値をサブメモリから読み出す動作に関しては、サイクル番号０において、アドレス信号ＭＡ０は基準点のアドレス値を示しており、かつ、サブメモリ・バンク選択信号ＳＥＬ０が’０’である。その為、アドレス選択回路１１１１にてアドレス信号ＭＡが選択されて、サブメモリ１１１５に入力され、サイクル番号１にてデータ信号ＭＤ０を介して、基準点の参照値が読み出される。その後、データ選択回路１１１９にてデータ信号ＭＤ０が選択されて、出力信号１１２１に基準点の参照値が出力される。同様な動作を、１サイクル遅れて、頂点２に関して行うことにより、頂点２の参照値の読み出しが可能となる。
【００５３】
同様に、対角点の参照値をサブメモリから読み出す動作に関しては、サイクル番号０において、アドレス信号ＭＢ０は対角点のアドレス値を示しており、かつ、サブメモリ・バンク選択信号ＳＥＬ１が’１’である。その為、アドレス選択回路１１１２にてアドレス信号ＭＢが選択されて、サブメモリ１１１６に入力され、サイクル番号１にてデータ信号ＭＤ１を介して、対角点の参照値が読み出される。その後、データ選択回路１１２０にてデータ信号ＭＤ１が選択されて、出力信号１１２２に対角点の参照値が出力される。同様な動作を、１サイクル遅れて、頂点１に関して行うことにより、頂点１の参照値の読み出しが可能となる。
【００５４】
次に、サブメモリ・バンク選択信号ＳＥＬ０が’１’（ＳＥＬ１は’０’）の場合に関してサブメモリから参照値を読み出す動作を説明する。
【００５５】
基準点の参照値をサブメモリから読み出す動作に関しては、サイクル番号２において、アドレス信号ＭＡ０は基準点のアドレス値を示しており、かつ、サブメモリ・バンク選択信号ＳＥＬ０が’１’である。その為、アドレス選択回路１１１２にてアドレス信号ＭＡが選択されて、サブメモリ１１１６に入力され、サイクル番号３にてデータ信号ＭＤ１を介して、基準点の参照値が読み出される。その後、データ選択回路１１１９にてデータ信号ＭＤ１が選択されて、出力信号１１２１に基準点の参照値が出力される。同様な動作を、１サイクル遅れて、頂点２に関して行うことにより、頂点２の参照値の読み出しが可能となる。
【００５６】
同様に、対角点の参照値をサブメモリから読み出す動作に関しては、サイクル番号２において、アドレス信号ＭＢ０は対角点のアドレス値を示しており、かつ、サブメモリ・バンク選択信号ＳＥＬ１が’０’である。その為、アドレス選択回路１１１１にてアドレス信号ＭＢが選択されて、サブメモリ１１１５に入力され、サイクル番号３にてデータ信号ＭＤ０を介して、対角点の参照値が読み出される。その後、データ選択回路１１２０にてデータ信号ＭＤ０が選択されて、出力信号１１２２に対角点の参照値が出力される。同様な動作を、１サイクル遅れて、頂点１に関して行うことにより、頂点１の参照値の読み出しが可能となる。
【００５７】
次に、アドレス生成回路１１０２の動作を説明する。ここでは、Ｒ−Ｇ平面上４×４ブロック単位にメモリへマッピングするものとする。
【００５８】
（１）  基準点用アドレス信号ＭＡ０の算出方法（アドレス信号１１０７として時分割で出力）
基準点の４×４ブロックのアドレスＢＡ０は
ＢＡ０＝Ｂｈ［ｘ−１：０］＆Ｒｈ［ｘ−１：２］＆Ｇｈ［ｘ−１：２］；（ただし、’＆’はビット連結を表す）
また、基準点の４×４ブロック内のアドレスＩＢＡ０は
ＩＢＡ０＝Ｇｈ［１：０］＆Ｒｈ［１：０］；
となるが、４×４ブロック内を４つのメモリに分散するのでいずれか一方の軸のアドレスは不要となる。ここでは、Ｇ軸の連続性を優先するが、但し、頂点２とメモリを共有化するので、Ｒ成分を１ビット残しておく。
【００５９】
ＩＢＡ０’＝Ｒｈ［１］＆Ｇｈ［１：０］；
とする。従って、基準点のメモリのアドレス信号ＭＡ０は、Ｇ軸の連続性を考慮して
ＭＡ０＝Ｂｈ［ｘ−１：０］＆Ｒｈ［ｘ−１：２］＆Ｇｈ［ｘ−１：２］＆Ｒｈ［１］＆Ｇｈ［１：０］
＝Ｂｈ［ｘ−１：０］＆Ｒｈ［ｘ−１：１］＆Ｇｈ［ｘ−１：０］；
と算出する。
【００６０】
サブメモリ・バンク選択信号ＳＥＬ０［１：０］はフルアダー１個で構成され、
ＳＥＬ０＝ＦＡ０（Ｂｈ［０］，Ｒｈ［０］，Ｇｈ［０］）［０］；
と算出する。
【００６１】
（２）  基準側頂点（頂点１）用アドレス信号ＭＡ１の算出（アドレス信号１１０８として時分割で出力）
基準側頂点は１軸を＋１した座標である。そのため、Ｒｈ，Ｇｈ，Ｂｈをインクリメントした値を各々Ｒｈ’，Ｇｈ’，Ｂｈ’、図９の下位ビット信号９１４をＲｌ，Ｇｌ，Ｂｌとすると、Ｒｌ，Ｇｌ，Ｂｌの大小関係を順序信号１１０６にしたがって、基準側頂点のメモリのアドレス信号ＭＡ１は、
ＭＡ１＝Ｂｈ［ｘ−１：０］＆Ｒｈ’［ｘ−１：１］＆Ｇｈ［ｘ−１：０］；（Ｒｌ＞Ｇｌ＞Ｂｌ  ｏｒ  Ｒｌ≧Ｂｌ≧Ｇｌ）
ＭＡ１＝Ｂｈ［ｘ−１：０］＆Ｒｈ［ｘ−１：１］＆Ｇｈ’［ｘ−１：０］；（Ｇｌ＞Ｂｌ＞Ｒｌ  ｏｒ  Ｇｌ≧Ｒｌ≧Ｂｌ）
ＭＡ１＝Ｂｈ’［ｘ−１：０］＆Ｒｈ［ｘ−１：１］＆Ｇｈ［ｘ−１：０］；（Ｂｌ＞Ｒｌ＞Ｇｌ  ｏｒ  Ｂｌ≧Ｇｌ≧Ｒｌ）
と算出する。
【００６２】
サブメモリ・バンク選択信号ＳＥＬ１は
ＳＥＬ１＝ｎｏｔ  ＳＥＬ０；
と算出する。
【００６３】
（３）  対角側頂点（頂点２）用アドレス信号ＭＡ０の算出（アドレス信号１１０７として時分割で出力）
対角側頂点は２軸を＋１した座標であるので、Ｒｌ，Ｇｌ，Ｂｌの大小関係を順序信号４０６にしたがって、対角側頂点のメモリのアドレス信号ＭＡ０は
ＭＡ０＝Ｂｈ［ｘ−１：０］＆Ｒｈ’［ｘ−１：１］＆Ｇｈ’［ｘ−１：０］；（Ｒｌ＞Ｇｌ＞Ｂｌ  ｏｒ  Ｇｌ≧Ｒｌ≧Ｂｌ）
ＭＡ０＝Ｂｈ’［ｘ−１：０］＆Ｒｈ［ｘ−１：１］＆Ｇｈ’［ｘ−１０］；（Ｇｌ＞Ｂｌ＞Ｒｌ  ｏｒ  Ｂｌ≧Ｇｌ≧Ｒｌ）
ＭＡ０＝Ｂｈ’［ｘ−１：０］＆Ｒｈ’［ｘ−１：１］＆Ｇｈ［ｘ−１：０］；（Ｂｌ＞Ｒｌ＞Ｇｌ  ｏｒ  Ｒｌ≧Ｂｌ≧Ｇｌ）
と算出する。
【００６４】
サブメモリ・バンク選択信号はＳＥＬ０である。
（４）  対角点用アドレス信号ＭＡ１の算出（アドレス信号１１０８として時分割で出力）
対角点は３軸を＋１した座標であるので、対角点のメモリのアドレス信号ＭＡ１は
ＭＡ１＝Ｂｈ’［ｘ−１：０］＆Ｒｈ’［ｘ−１：１］＆Ｇｈ’［ｘ−１：０］；
と算出する。
【００６５】
サブメモリ・バンク選択信号はＳＥＬ１である。
【００６６】
＜補間演算動作＞
図１３は、第１実施形態に係る補間演算部における演算を例示的に示す図である。
【００６７】
１３００は、図１１の出力信号１１２１から、基準点又は頂点２の参照値の値が入力される入力信号であり、１３０１は、出力信号１１２２から、頂点１又は対角点の参照値の値が入力される入力信号である。これらは図９の参照値信号９５２に対応している。１３０２，１３０３，１３０４は２入力１出力セレクタであり、制御信号の値が’０’のとき、０側の入力を、’１’の時１側の入力を選択して出力する。１３０５，１３０６はＤフリップフロップ（以下Ｄ−ＦＦと称す）である。１３０７，１３０８は引き算器であり、１３０９，１３１０は乗算器であり、１３１１，１３１２，１３１３は加算器である。１３１４，１３１５は３入力１出力セレクタであり、順序信号１３１７に従って、重み係数ΔＲ，ΔＧ，ΔＢのうちから選択して出力する。１３１６は図１１と同一な制御信号ＣＳＥＬであり、１３１７は図９の順序信号９３２及び図１１の順序信号１１１３と同一な信号である。１３１９は補間演算の結果を出力するための出力信号である。なお、重み係数ΔＲ，ΔＧ，ΔＢは、公知の四面体補間法で用いられる重み係数が利用可能である。
【００６８】
図１４は、第１実施形態に係る補間演算部におけるタイミングチャートである。
【００６９】
１４０１は図１２の１２００と同一のクロック信号ＣＬＫである。１４０２は図５の１２０１と同一な制御信号ＣＳＥＬである。１４０３は入力信号１３００、１４０４は入力信号１３０１である。１４０５はＤ−ＦＦ１３０５の出力である。１４０６は減算器１３０７の出力、１４０７は減算器１３０８の出力である。１４０８は乗算器１３０９の出力、１４０９は乗算器１３１０の出力である。１４１０はＤ−ＦＦ１３０６の出力である。１４１１は加算器１３１１の出力、１４１２は加算器１３１２の出力、１４１３は加算器１３１３の出力のタイミングチャートを夫々示す。ここで、図１１で示した参照値読み出し部及びＬＵＴと同様に、図１３の補間演算部は、クロック信号ＣＬＫの立ち上がり同期で動作するものとし、１４０２〜１４１３の各信号は、クロック信号ＣＬＫの立ち上がりに同期して変化するものとする。
【００７０】
まず、サイクル番号１において、制御信号ＣＳＥＬは’１’であり、入力端子１３００より基準点の参照値が、入力端子１３０１より対角点の参照値が入力される。この時、Ｄ−ＦＦ１３０５にはセレクタ１３０２を介して基準点の参照値が格納される。また、減算器１３０８においては、セレクタ１３０３を通して基準点の参照値が入力されるため、（対角点の参照値  −  基準点の参照値）の演算が行われる。その後、乗算器１３１０においては、セレクタ１３１５にて順序信号１３１７の値により、重み係数が選択される。選択された重み係数をΔａとすると、
（（対角点の参照値  −  基準点の参照値）ｘΔａ）
の演算が行われ、演算結果をＤ−ＦＦ１３０６に格納する。
【００７１】
サイクル番号２において、制御信号ＣＳＥＬは’０’であり、入力端子１３００より頂点２の参照値が、入力端子１３０１より頂点１の参照値が入力される。そして、減算器１３０７において、
（頂点２の参照値  −  基準点の参照値）
の演算が行われる。その後、乗算器１３０９においては、セレクタ１３１４にて順序信号１３１７の値により、重み係数が選択される。選択された重み係数をΔｃとすると、
（（頂点２の参照値  −  基準点の参照値）ｘΔｃ）
の演算が行われ、演算結果が加算器１３１３に入力される。また、減算器１３０８においては、セレクタ１３０３を通してＤ−ＦＦ１３０５の出力である、基準点の参照値が入力されるため、
（頂点１の参照値  −  基準点の参照値）
の演算が行われる。その後、乗算器１３１０においては、セレクタ１３１５にて順序信号１３１７の値により、重み係数が選択される。選択された重み係数をΔｂとすると、
（（頂点１の参照値  −  基準点の参照値）ｘΔｂ）
の演算が行われ、演算結果が加算器１３１２に入力される。加算器１３１２においては、乗算器１３１０の出力と、Ｄ−ＦＦ１３０６の出力の加算である、
（（対角点の参照値  −  基準点の参照値）ｘΔａ  ＋  （頂点１の参照値  −  基準点の参照値）ｘΔｂ）
の演算が行われ、演算結果が加算器１３１３に入力される。その後、加算器１３１３において、加算器１３１１の出力と加算器１３１２の出力の加算である、
（基準点の参照値  ＋  （頂点２の参照値  −  基準点の参照値）ｘΔｃ  ＋  （対角点の参照値  −  基準点の参照値）ｘΔａ  ＋  （頂点１の参照値  −  基準点の参照値）ｘΔｂ）
の演算が行われ、補間演算結果として出力信号１３１９から出力される。
【００７２】
以上説明したとおり、３次元の場合の色空間変換処理である第１実施形態によれば、多次元ＬＵＴ９６０を２つのサブメモリに格納すると共に、２サイクルで参照点を読み出して補間演算する技術について説明した。このように構成することにより、背景技術で述べた２つの特許文献に開示された技術に比較し、より少ないサブメモリとすることが出来、ＬＵＴ読み出しの周辺回路の規模を低減可能とすることが可能となる。また、補間演算回路についても、加算器３個、引き算器２個、乗算器２個で実現可能であり、回路規模の低減に寄与する。
【００７３】
（第２実施形態）
＜概要＞
第２実施形態では色空間変換部への入力値が４次元である場合について説明する。補間演算に必要な４次元超四面体の５頂点に対応する参照値を２回のルックアップテーブル（ＬＵＴ）参照サイクルにより読み出す。第１実施形態で説明した３次元ＬＵＴと同様に、４次元ＬＵＴを超四面体の基準頂点からのマンハッタン距離に基づき分割記憶する。このように構成することにより、ＬＵＴの分割数を４個に抑制すると共に、分割個数を２のべき乗に設定可能となり、回路規模の低減が可能となる。なお、装置構成などは第１実施形態とほぼ同様のため、ここでは多次元ＬＵＴおよび参照値読み出し部について詳細に説明する。
【００７４】
＜多次元ＬＵＴおよび参照値読み出し部＞
図１５は、四次元超四面体補間法における、基準点から対角点までの単位立体の各頂点を四次元マンハッタン距離Ｄｍを用いて分類した図である。まず、四次元の単位超立体を図に示される２つの領域１５００および１５０１に分割する。なお、同一領域内のマンハッタン距離が図に示される関係を維持する限りにおいて、任意の２領域に分割可能である。
【００７５】
まず、四次元の単位超立体の基準点（ｘ０＜ｉ＞，ｘ１＜ｊ＞，ｘ２＜ｋ＞，ｘ３＜ｌ＞）から（ｘ０＜ｉ＋１＞，ｘ１＜ｊ＋１＞，ｘ２＜ｋ＋１＞，ｘ３＜ｌ＞）までの２３個の頂点に対し、三次元四面体補間法のときの３次元ＬＵＴの分割記憶方法を適用する（領域１５００）。
【００７６】
また、残った単位超立体の頂点（ｘ０＜ｉ＞，ｘ１＜ｊ＞，ｘ２＜ｋ＞，ｘ３＜ｌ＋１＞）から（ｘ０＜ｉ＋１＞，ｘ１＜ｊ＋１＞，ｘ２＜ｋ＋１＞，ｘ３＜ｌ＋１＞）までの２３個の頂点に対し、同様に三次元四面体補間法のときの３次元ＬＵＴの分割記憶方法を適用する（図中、領域１５０１）。
【００７７】
その結果、図中Ｍｅｍ０，…Ｍｅｍ３と記載された太線で囲まれた頂点がそれぞれ同一のサブメモリに記憶されることになる。つまり、領域１５００、１５０１夫々において、マンハッタン距離Ｄｍが偶数の頂点と奇数の頂点でメモリ分割を行うことにより、多次元ＬＵＴを２×２個のサブメモリに分割記憶するのである。
【００７８】
図１６は、参照値読み出し部１６０１および多次元ＬＵＴ１６００の内部構成を例示的に示す図である。なお、参照値読み出し部１６０１および多次元ＬＵＴ１６００はそれぞれ、図９の参照値読み出し部９５０および多次元ＬＵＴ９６０に相当する。
【００７９】
１６０２はアドレス生成回路である。１６０３，１６０４，１６０５，１６０６の４個のデジタル画像信号の上位ビット信号Ｃｈ［ｘ−１：０］，Ｍｈ［ｘ−１：０］，Ｙｈ［ｘ−１：０］Ｋｈ［ｘ−１：０］である。１６４６は図９の９３２に対応する順序信号である。ここで、ｘは前述のビット数を示している。１６０７，１６０８，１６０９，１６１０は３次元補間の基準点，基準値側頂点（頂点１），頂点２，対角点側頂点（頂点３），対角点のそれぞれの参照値をメモリから読み出すためのアドレス信号ＭＡ０，ＭＡ１，ＭＡ２，ＭＡ３である。１６１１，１６１２，１６１３，１６１４はそれぞれ、アドレス選択回路１６１５，１６１６，１６１７，１６１８及び、データ選択回路１６３１，１６３２，１６３３，１６３４の選択信号となる、サブメモリ・バンク選択信号ＳＥＬ０［１：０］，ＳＥＬ１［１：０］，ＳＥＬ２［１：０］，ＳＥＬ３［１：０］である。
【００８０】
１６２３，１６２４，１６２５，１６２６はそれぞれサブメモリ（Ｍｅｍ０），サブメモリ（Ｍｅｍ１），サブメモリ（Ｍｅｍ２），サブメモリ（Ｍｅｍ３）である。また、１６１５，１６１６，１６１７，１６１８はそれぞれ、サブメモリ１６２３，１６２４，１６２５，１６２６のアドレス選択回路である。１６１９，１６２０，１６２１，１６２２はそれぞれ、アドレス選択回路１６１５，１６１６，１６１７，１６１８から出力されたアドレス信号であり、それぞれサブメモリ１６２３，１６２４，１６２５，１６２６に供給される。
【００８１】
また、１６３１，１６３２，１６３３，１６３４はそれぞれデータ選択回路である。１６２７，１６２８，１６２９，１６３０はそれぞれサブメモリ１６２３，１６２４，１６２５，１６２６からの出力データ信号である。出力データ信号は全てのデータ選択回路１６３１，１６３２，１６３３，１６３４に供給される。１６３５，１６３６，１６３７はセレクタである。１６３８，１６３９，１６４０の選択信号ＳＥＬ１Ｈ，ＳＥＬ３Ｈ，ＳＥＬ２Ｈにより夫々、データ選択回路１６３１又は１６３２の出力、データ選択回路１６３１又は１６３２の出力、データ選択回路１６３０又は１６３３の出力を選択する。そして、出力信号１６４１，１６４２，１６４３，１６４４，１６４５に出力する。１６４１，１６４２，１６４３，１６４４，１６４５は図９の９５２と同等な参照信号であり、それぞれ、４次元補間の基準点，頂点１，頂点３，頂点２，対角点の参照値を示す。
【００８２】
次に、図１６の動作を説明する。アドレス生成回路９０２がＣＭＹＫの４個の信号Ｃｈ［ｘ−１：０］，Ｍｈ［ｘ−１：０］，Ｙｈ［ｘ−１：０］，Ｋｈ［ｘ−１：０］を受けて、４組のアドレス信号ＭＡ０，ＭＡ１，ＭＡ２，ＭＡ３を出力する。また、サブメモリ・バンク選択信号ＳＥＬ０［１：０］，ＳＥＬ１［１：０］，ＳＥＬ２［１：０］，ＳＥＬ３［１：０］を出力する。ここで、ＭＡ０には基準点と頂点２の参照点を読み出すためのアドレスが多重化されている。同様に、ＭＡ１及びＭＡ２には頂点１と頂点３の参照点を読み出すためのアドレスが多重化されている。また、ＭＡ３には頂点２と対角点の参照点を読み出すためのアドレスが多重化されている。ここで、４本のメモリ・バンク選択信号は、各々が異なる値である。
【００８３】
そして、アドレス信号ＭＡ０，ＭＡ１，ＭＡ２，ＭＡ３とサブメモリ・バンク選択信号ＳＥＬ０［１：０］，ＳＥＬ１［１：０］，ＳＥＬ２［１：０］，ＳＥＬ３［１：０］が全てのアドレス選択回路１６１５，１６１６，１６１７，１６１８に入力される。各アドレス選択回路１６１５，１６１６，１６１７，１６１８は各々が異なるサブメモリ・バンクＩＤ“ＳｍＢ＿ＩＤ”を有している。自らが対応するサブメモリ・バンクＩＤ“ＳｍＢ＿ＩＤ”と入力されたサブメモリ・バンク選択信号が等しいアドレス信号を４本の中から１つ選択して出力し、サブメモリにアクセスする。
【００８４】
サブメモリ１６２３，１６２４，１６２５，１６２６はそれぞれ受け取ったアドレス値１６１９，１６２０，１６２１，１６２２の参照値を出力データ信号１６２７，１６２８，１６２９，１６３０として全てのデータ選択回路１６３１，１６３２，１６３３，１６３４に供給する。データ選択回路１６３１，１６３２，１６３３，１６３４ではそれぞれ入力されているサブメモリ・バンク選択信号ＳＥＬ０，１，２，３にしたがって、４本のサブメモリの出力から１本を選択する。つまり、基準点又は頂点２の参照値として出力信号１６４１及びセレクタ１６３７に出力する。頂点１又は頂点３の参照値としてセレクタ１６３５及び１６３６に出力する。頂点１又は頂点３の参照値としてセレクタ１６３５及び１６３６に出力する。頂点２又は対角点の参照値としてセレクタ１６３７及び出力信号１６４１に出力する。
【００８５】
さらに前述のように、セレクタ１６３５，１６３６，１６３７においては、それぞれ選択信号ＳＥＬ１Ｈ，ＳＥＬ３Ｈ，ＳＥＬ２Ｈにしたがって出力する。つまり、データ選択回路１６３２又は１６３３、データ選択回路１６３２又は１６３３、データ選択回路１６３１又は１６３４の出力を選択して、出力信号１６４２，１６４３，１６４４に出力する。
【００８６】
＜アドレスの生成＞
次にアドレス生成回路１６０２の動作を説明する。ここでは、Ｃ−Ｍ平面上４×４ブロック単位にメモリへマッピングするものとする。
【００８７】
（１）  基準点用アドレス信号ＭＡ０の算出方法（アドレス信号１６０７として時分割で出力）
基準点の４×４ブロックのアドレスＢＡ０は、４次元四面体補間方では、３次元四面体補間法のときに３次元ＬＵＴを２個を２セット用いるため、その選択信号にＫｈ［０］を用いる場合、
ＢＡ０＝Ｋｈ［ｘ−１：１］＆Ｙｈ［ｘ−１：０］＆Ｃｈ［ｘ−１：２］＆Ｍｈ［ｘ−１：２］；（ただし、’＆’はビット連結を表す）
また、基準点の４×４ブロック内のアドレスＩＢＡ０は
ＩＢＡ０＝Ｃｈ［１：０］＆Ｍｈ［１：０］；
となるが、４×４ブロック内を４つのメモリに分散するのでいずれか一方の軸のアドレスは不要となる。但し、頂点２とメモリを共有化するので、Ｃ成分を１ビット残しておく。
【００８８】
従って、基準点のメモリのアドレスＭＡ０は、Ｍ軸の連続性を考慮して
ＭＡ０＝Ｋｈ［ｘ−１：１］＆Ｙｈ［ｘ−１：０］＆Ｃｈ［ｘ−１：２］＆Ｍｈ［ｘ−１：２］＆Ｃｈ［１］＆Ｍｈ［１．：０］
＝Ｋｈ［ｘ−１：０］＆Ｙｈ［ｘ−１：０］＆Ｃｈ［ｘ−１：１］＆Ｍｈ［ｘ−１：０］；
と算出する。
【００８９】
（２）  頂点１用アドレス信号ＭＡ１及びＭＡ２の算出方法（アドレス信号１６０８及び１６０９として時分割で出力）
頂点１は１軸を＋１した座標である。そのため、Ｃｈ，Ｍｈ，Ｙｈ，Ｋｈをインクリメントした値を夫々Ｃｈ’，Ｍｈ’，Ｙｈ’，Ｋｈ’、図９の下位ビット信号９１４をＣｌ，Ｍｌ，Ｙｌ，Ｋｌとすると、Ｃｌ，Ｍｌ，Ｙｌ，Ｋｌの大小関係を順序信号１６４２にしたがって、３次元の場合と同様に考えることにより、頂点１のメモリのアドレスＭＡ１（ＭＡ２）及び１６３７の選択信号ＳＥＬ１Ｈは、
・Ｃｌ＞Ｍｌ＞Ｙｌ＞Ｋｌ  ｏｒ  Ｃｌ＞Ｍｌ＞Ｋｌ≧Ｙｌ  ｏｒ  Ｃｌ＞Ｋｌ≧Ｍｌ＞Ｙｌ  ｏｒ  Ｃｌ＞Ｙｌ≧Ｍｌ＞Ｋｌ  ｏｒ  Ｃｌ＞Ｙｌ＞Ｋｌ≧Ｍｌ    ｏｒ  Ｃｌ＞Ｋｌ≧Ｙｌ≧Ｍｌ  のとき
ＭＡ１（ＭＡ２）＝Ｋｈ［ｘ−１：１］＆Ｙｈ［ｘ−１：０］＆Ｃｈ’［ｘ−１：１］＆Ｍｈ［ｘ−１：０］；
ＳＥＬ１Ｈ＝Ｋｈ［０］；
・Ｍｌ≧Ｃｌ＞Ｙｌ＞Ｋｌ  ｏｒ  Ｍｌ≧Ｃｌ＞Ｋｌ≧Ｙｌ  ｏｒ  Ｍｌ＞Ｋｌ≧Ｃｌ＞Ｙｌ  ｏｒ  Ｍｌ＞Ｙｌ≧Ｃｌ＞Ｋｌ  ｏｒ  Ｍｌ＞Ｙｌ＞Ｋｌ≧Ｃｌ    ｏｒ  Ｍｌ＞Ｋｌ≧Ｙｌ≧Ｃｌ  のとき
ＭＡ１（ＭＡ２）＝Ｋｈ［ｘ−１：１］＆Ｙｈ［ｘ−１：０］＆Ｃｈ［ｘ−１：１］＆Ｍｈ’［ｘ−１：０］；
ＳＥＬ１Ｈ＝Ｋｈ［０］；
・Ｙｌ≧Ｃｌ＞Ｍｌ＞Ｋｌ  ｏｒ  Ｙｌ≧Ｃｌ＞Ｋｌ≧Ｍｌ  ｏｒ  Ｙｌ＞Ｋｌ≧Ｃｌ＞Ｍｌ  ｏｒ  Ｙｌ≧Ｍｌ≧Ｃｌ＞Ｋｌ  ｏｒ  Ｙｌ≧Ｍｌ＞Ｋｌ≧Ｃｌ    ｏｒ  Ｙｌ＞Ｋｌ≧Ｍｌ≧Ｃｌ  のとき
ＭＡ１（ＭＡ２）＝Ｋｈ［ｘ−１：１］＆Ｙｈ’［ｘ−１：０］＆Ｃｈ［ｘ−１：１］＆Ｍｈ［ｘ−１：０］；
ＳＥＬ１Ｈ＝Ｋｈ［０］；
・Ｋｌ≧Ｃｌ＞Ｍｌ＞Ｙｌ  ｏｒ  Ｋｌ≧Ｃｌ＞Ｙｌ≧Ｍｌ  ｏｒ  Ｋｌ≧Ｍｌ≧Ｃｌ＞Ｙｌ  ｏｒ  Ｋｌ≧Ｍｌ＞Ｙｌ≧Ｃｌ  ｏｒ  Ｋｌ≧Ｙｌ≧Ｃｌ＞Ｍｌ    ｏｒ  Ｋｌ≧Ｙｌ≧Ｍｌ≧Ｃｌ  のとき
ＭＡ１（ＭＡ２）＝Ｋｈ’［ｘ−１：１］＆Ｙｈ［ｘ−１：０］＆Ｃｈ［ｘ−１：１］＆Ｍｈ［ｘ−１：０］；
ＳＥＬ１Ｈ＝Ｋｈ’［０］；
と算出する。
【００９０】
（３）  頂点２用アドレス信号ＭＡ０及びＭＡ３の算出方法（アドレス信号１６０７及び１６１０として時分割で出力）
頂点２は２軸を＋１した座標であるので、頂点２のメモリのアドレスＭＡ０（ＭＡ３）及びメモリセレクト信号ＳＥＬ２Ｈは、
・Ｃｌ＞Ｍｌ＞Ｙｌ＞Ｋｌ  ｏｒ  Ｃｌ＞Ｍｌ＞Ｋｌ≧Ｙｌ  ｏｒ  Ｍｌ≧Ｃｌ＞Ｙｌ＞Ｋｌ  ｏｒ  Ｍｌ≧Ｃｌ＞Ｋｌ≧Ｙｌ  のとき
ＭＡ０（ＭＡ３）＝Ｋｈ［ｘ−１：１］＆Ｙｈ［ｘ−１：０］＆Ｃｈ’［ｘ−１：１］＆Ｍｈ’［ｘ−１：０］；
ＳＥＬ２Ｈ＝Ｋｈ［０］；
・Ｃｌ＞Ｙｌ≧Ｍｌ＞Ｋｌ  ｏｒ  Ｃｌ＞Ｙｌ＞Ｋｌ≧Ｍｌ  ｏｒ  Ｙｌ≧Ｃｌ＞Ｍｌ＞Ｋｌ  ｏｒ  Ｙｌ≧Ｃｌ＞Ｋｌ≧Ｍｌ  のとき
ＭＡ０（ＭＡ３）＝Ｋｈ［ｘ−１：１］＆Ｙｈ’［ｘ−１：０］＆Ｃｈ’［ｘ−１：１］＆Ｍｈ［ｘ−１０］；
ＳＥＬ２Ｈ＝Ｋｈ［０］；
・Ｃｌ＞Ｋｌ≧Ｍｌ＞Ｙｌ  ｏｒ  Ｃｌ＞Ｋｌ≧Ｙｌ≧Ｍｌ  ｏｒ  Ｋｌ≧Ｃｌ＞Ｍｌ＞Ｙｌ  ｏｒ  Ｋｌ≧Ｃｌ＞Ｙｌ≧Ｍｌ  のとき
ＭＡ０（ＭＡ３）＝Ｋｈ’［ｘ−１：１］＆Ｙｈ［ｘ−１：０］＆Ｃｈ’［ｘ−１：１］＆Ｍｈ［ｘ−１０］；
ＳＥＬ２Ｈ＝Ｋｈ’［０］；
・Ｍｌ＞Ｙｌ≧Ｃｌ＞Ｋｌ  ｏｒ  Ｍｌ＞Ｙｌ＞Ｋｌ≧Ｃｌ  ｏｒ  Ｙｌ≧Ｍｌ≧Ｃｌ＞Ｋｌ  ｏｒ  Ｙｌ≧Ｍｌ＞Ｋｌ≧Ｃｌ  のとき
ＭＡ０（ＭＡ３）＝Ｋｈ［ｘ−１：１］＆Ｙｈ’［ｘ−１：０］＆Ｃｈ［ｘ−１：１］＆Ｍｈ’［ｘ−１：０］；
ＳＥＬ２Ｈ＝Ｋｈ［０］；
・Ｍｌ＞Ｋｌ≧Ｃｌ＞Ｙｌ  ｏｒ  Ｍｌ＞Ｋｌ≧Ｙｌ≧Ｃｌ  ｏｒ  Ｋｌ≧Ｍｌ≧Ｃｌ＞Ｙｌ  ｏｒ  Ｋｌ≧Ｍｌ＞Ｙｌ≧Ｃｌ  のとき
ＭＡ０（ＭＡ３）＝Ｋｈ’［ｘ−１：１］＆Ｙｈ［ｘ−１：０］＆Ｃｈ［ｘ−１：１］＆Ｍｈ’［ｘ−１：０］；
ＳＥＬ２Ｈ＝Ｋｈ’［０］；
・Ｙｌ＞Ｋｌ≧Ｃｌ＞Ｍｌ  ｏｒ  Ｙｌ＞Ｋｌ≧Ｍｌ≧Ｃｌ  ｏｒ  Ｋｌ≧Ｙｌ≧Ｃｌ＞Ｍｌ  ｏｒ  Ｋｌ≧Ｙｌ≧Ｍｌ≧Ｃｌ  のとき
ＭＡ０（ＭＡ３）＝Ｋｈ’［ｘ−１：１］＆Ｙｈ’［ｘ−１：０］＆Ｃｈ［ｘ−１：１］＆Ｍｈ［ｘ−１：０］；
ＳＥＬ２Ｈ＝Ｋｈ’［０］；
と算出する。
【００９１】
（４）  頂点３用アドレス信号ＭＡ１及びＭＡ２の算出方法（アドレス信号１６０８及び１６０９として時分割で出力）
頂点２は３軸を＋１した座標であるので、頂点３のメモリのアドレスＭＡ１（ＭＡ２）及びメモリセレクト信号ＳＥＬ３Ｈは、
・Ｃｌ＞Ｍｌ＞Ｙｌ＞Ｋｌ  ｏｒ  Ｃｌ＞Ｙｌ≧Ｍｌ＞Ｋｌ  ｏｒ  Ｍｌ≧Ｃｌ＞Ｙｌ＞Ｋｌ  ｏｒ  Ｙｌ≧Ｍｌ≧Ｃｌ＞Ｋｌ  のとき
ＭＡ１（ＭＡ２）＝Ｋｈ［ｘ−１：１］＆Ｙｈ’［ｘ−１：０］＆Ｃｈ’［ｘ−１：１］＆Ｍｈ’［ｘ−１：０］；
ＳＥＬ３Ｈ＝Ｋｈ［０］；
・Ｃｌ＞Ｙｌ＞Ｋｌ≧Ｍｌ  ｏｒ  Ｃｌ＞Ｋｌ≧Ｙｌ≧Ｍｌ  ｏｒ  Ｙｌ＞Ｋｌ≧Ｃｌ＞Ｍｌ  ｏｒ  Ｙｌ≧Ｃｌ＞Ｋｌ≧Ｍｌ  のとき
ＭＡ１（ＭＡ２）＝Ｋｈ’［ｘ−１：１］＆Ｙｈ’［ｘ−１：０］＆Ｃｈ’［ｘ−１：１］＆Ｍｈ［ｘ−１：０］；
ＳＥＬ３Ｈ＝Ｋｈ’［０］；
・Ｃｌ＞Ｋｌ≧Ｍｌ＞Ｙｌ  ｏｒ  Ｃｌ＞Ｍｌ＞Ｋｌ≧Ｙｌ  ｏｒ  Ｍｌ≧Ｃｌ＞Ｋｌ≧Ｙｌ  ｏｒ  Ｋｌ≧Ｃｌ＞Ｍｌ＞Ｙｌ  のとき
ＭＡ１（ＭＡ２）＝Ｋｈ’［ｘ−１：１］＆Ｙｈ［ｘ−１：０］＆Ｃｈ’［ｘ−１：１］＆Ｍｈ’［ｘ−１：０］；
ＳＥＬ３Ｈ＝Ｋｈ’［０］；
・Ｍｌ＞Ｋｌ≧Ｙｌ≧Ｃｌ  ｏｒ  Ｍｌ＞Ｙｌ＞Ｋｌ≧Ｃｌ  ｏｒ  Ｙｌ≧Ｍｌ＞Ｋｌ≧Ｃｌ  ｏｒ  Ｙｌ＞Ｋｌ≧Ｍｌ≧Ｃｌ  のとき
ＭＡ１（ＭＡ２）＝Ｋｈ’［ｘ−１：１］＆Ｙｈ’［ｘ−１：０］＆Ｃｈ［ｘ−１：１］＆Ｍｈ’［ｘ−１：０］；
ＳＥＬ３Ｈ＝Ｋｈ’［０］；
と算出する。
【００９２】
（５）  対角点用アドレス信号ＭＡ３の算出方法（アドレス信号１６１０として時分割で出力）
対角点は全軸を＋１した座標であるので、対角点のメモリのアドレスＭＡ３は、
ＭＡ３＝Ｋｈ’［ｘ−１：１］＆Ｙｈ’［ｘ−１：０］＆Ｃｈ’［ｘ−１：１］＆Ｍｈ’［ｘ−１：０］；
と算出する。
【００９３】
また、サブメモリ・バンク信号ＳＥＬ０［１：０］，ＳＥＬ１［１：０］，ＳＥＬ２［１：０］，ＳＥＬ３［１：０］は、
ＳＥＬ０［０］＝ＦＡ０（Ｙｈ［０］，Ｃｈ［０］，Ｍｈ［０］）［０］；
ＳＥＬ０［１］＝ＦＡ１（Ｙｈ［１］，Ｃｈ［１］，Ｍｈ［１］）［０］  ｘｏｒ  ＦＡ０（Ｙｈ［０］，Ｃｈ［０］，Ｍｈ［０］）［１］；
（ＦＡ０，  ＦＡ１はフルアダーによる演算）
ＳＥＬ１［０］＝  ｎｏｔ  ＳＥＬ０［０］；
ＳＥＬ１［１］＝ＳＥＬ０［１］  ｘｏｒ  ＳＥＬ０［０］；
ＳＥＬ２［０］＝  ｎｏｔ  ＳＥＬ０［０］；
ＳＥＬ２［１］＝  ｎｏｔ  （ＳＥＬ０［１］  ｘｏｒ  ＳＥＬ０［０］）；
ＳＥＬ３［０］＝ＳＥＬ０［０］；
ＳＥＬ３［１］＝  ｎｏｔ  ＳＥＬ０［１］；
と算出する。
【００９４】
＜補間演算動作＞
図１７は、第２実施形態に係る補間演算部における演算を例示的に示す図である。
【００９５】
１７００は、図１６の出力信号１６４１から、基準点の参照値の値が入力される入力信号である。１７０１は、出力信号１６４２から頂点１の参照値の値が入力される入力信号である。１７０２は、１６４４から頂点２の参照値の値が入力される入力信号である。１７０３は、出力信号１６４３から頂点３の参照値の値が入力される入力信号である。１７０４は、出力信号１６４５から対角点の参照値の値が入力される入力信号である。これらは図９の参照値信号９５２に対応している。
【００９６】
１７０５，１７０６，１７０７，１７０８，１７０９，１７１０は２入力１出力セレクタであり、制御信号の値が’０’のとき、０側の入力を、’１’の時１側の入力を選択して出力する。１７１１，１７１２，１７１３はＤ−ＦＦである。１７１４，１７１５は引き算器であり、１７１６，１７１７は乗算器であり、１７１８，１７１９，１７２０，１７２１は加算器である。１７２２，１７２３は４入力１出力セレクタであり、順序信号１７２５に従って、補間演算の重み係数ΔＣ，ΔＭ，ΔＹ，ΔＫを選択出力する。１７２４は図１１と同一な制御信号ＣＳＥＬであり、１７２５は図９の順序信号９３２及び図１６の順序信号１６４６と同一な信号である。１７２７は補間演算の結果を出力するための出力信号である。
【００９７】
図１８は、第２実施形態に係る補間演算部におけるタイミングチャートである。
【００９８】
１８００はタイミングチャートの動作を説明する為のサイクル番号である。１８０１はクロック信号ＣＬＫである。１８０２は制御信号ＣＳＥＬである。１８０３は入力信号１７００、１８０４は入力信号１７０１、１８０５は入力信号１７０２、１８０６は入力信号１７０３、１８０７は入力信号１７０４である。１８０８はＤ−ＦＦ１７１１の出力である。１８０９は減算器１７１４の出力、１８１０は減算器１７１５の出力である。１８１１は乗算器１７１６の出力である。１８１２はＤ−ＦＦ１７１２の出力である。１８１３は乗算器１７１７の出力である。１８１４はＤ−ＦＦ１７１３の出力である。１８１５は加算器１７１８の出力、１８１６は加算器１７１９の出力、１８１７は加算器１７２０の出力、１８１８は加算器１７２１の出力のタイミングチャートを夫々示す。ここで、図１７の補間演算部は、クロック信号ＣＬＫの立ち上がり同期で動作するものとし、１８０２〜１８１８の各信号は、クロック信号ＣＬＫの立ち上がりに同期して変化するものとする。
【００９９】
まず、サイクル番号１において、制御信号ＣＳＥＬは’１’であり、入力信号１７００より基準点の参照値が、入力信号１７０１より頂点１の参照値が、入力信号１７０４より対角点の参照値が入力される。この時、Ｄ−ＦＦ１７１１にはセレクタ１７０５を介して基準点の参照値が格納される。また、減算器１７１４においては、セレクタ１７０６を通して基準点の参照値が入力され、かつセレクタ１７０７を通して対角点の参照値が入力されるため、
（対角点の参照値  −  基準点の参照値）
の演算が行われる。その後、乗算器１７１６においては、セレクタ１７２２にて順序信号１７２５の値により、重み係数が選択される。選択された重み係数をΔａとすると、
（（対角点の参照値  −  基準点の参照値）ｘΔａ）
の演算が行われる。そして演算結果をＤ−ＦＦ１７１２に格納する。同様に、減算器１７１５においては、セレクタ１７０６を通して基準点の参照値が入力され、かつセレクタ１７０８を通して頂点１の参照値が入力されるため、
（頂点１の参照値  −  基準点の参照値）
の演算が行われる。その後、乗算器１７１７においては、セレクタ１７２３にて順序信号１７２５の値により、重み係数が選択される。選択された重み係数をΔｂとすると、
（（頂点１の参照値  −  基準点の参照値）ｘΔｂ）
の演算が行われる。そして演算結果をＤ−ＦＦ１７１３に格納する。
【０１００】
次に、サイクル番号２において、制御信号ＣＳＥＬは’０’であり、入力信号１７０２より頂点２の参照値が、入力信号１７０３より頂点３の参照値が入力される。そして、減算器１７１４において、
（頂点２の参照値  −  基準点の参照値）
の演算が行われる。その後、乗算器１７１６においては、セレクタ１０２２にて順序信号１７２５の値により、重み係数が選択される。選択された重み係数をΔｃとすると、
（（頂点２の参照値  −  基準点の参照値）ｘΔｃ）
の演算が行われる。そして演算結果が加算器１７１８に入力される。また、減算器１０１５においては、
（頂点３の参照値  −  基準点の参照値）
の演算が行われる。その後、乗算器１７１７においては、セレクタ１７２３にて順序信号１７２５の値により、重み係数が選択される。選択された重み係数をΔｄとすると、
（（頂点３の参照値  −  基準点の参照値）ｘΔｄ）
の演算が行われる。そして演算結果が加算器１７１９に入力される。加算器１７１８においては、乗算器１７１６の出力と、Ｄ−ＦＦ１７１２の出力の加算である、
（（対角点の参照値  −  基準点の参照値）ｘΔａ  ＋  （頂点２の参照値  −  基準点の参照値）ｘΔｃ）
の演算が行われ、演算結果が加算器１７２０に入力される。また、加算器１７１９においては、乗算器１７１７の出力と、Ｄ−ＦＦ１７１３の出力の加算である、
（（頂点１の参照値  −  基準点の参照値）ｘΔｂ  ＋  （頂点３の参照値  −  基準点の参照値）ｘΔｄ）
の演算が行われ、演算結果が加算器１７２０に入力される。
【０１０１】
その後、加算器１７２０において、加算器１７１８の出力と加算器１７１９の出力の加算である、
（（対角点の参照値  −  基準点の参照値）ｘΔａ  ＋  （頂点２の参照値  −  基準点の参照値）ｘΔｃ  ＋  （頂点１の参照値  −  基準点の参照値）ｘΔｂ  ＋  （頂点３の参照値  −  基準点の参照値）ｘΔｄ）
の演算が行われ、演算結果が加算器１７２１に入力される。そして、加算器１７２１において、加算器１７２０の出力とＤ−ＦＦ１７１１の出力の加算である、
（基準点の参照値  ＋  （対角点の参照値  −  基準点の参照値）ｘΔａ  ＋  （頂点２の参照値  −  基準点の参照値）ｘΔｃ  ＋  （頂点１の参照値  −  基準点の参照値）ｘΔｂ  ＋  （頂点３の参照値  −  基準点の参照値）ｘΔｄ）
の演算が行われ、補間演算結果として出力信号１７２７から出力される。
【０１０２】
以上説明したとおり、４次元の場合のデータ変換処理である第２実施形態によれば、多次元ＬＵＴ９６０を４つのサブメモリに格納すると共に、２サイクルで参照点を読み出して補間演算する技術について説明した。このように構成することにより、背景技術で述べた２つの特許文献に開示された技術に比較し、より少ないサブメモリとすることが出来、ＬＵＴ読み出しの周辺回路の規模を低減可能とすることが可能となる。また、補間演算回路についても、加算器４個、引き算器２個、乗算器２個で実現可能であり、回路規模の低減に寄与する。
【０１０３】
（第３実施形態）
＜概要＞
第３実施形態では色空間変換部への入力値がＮ次元である場合について説明する。補間演算に必要なＮ次元超四面体のＮ＋１頂点に対応する参照値を２回のルックアップテーブル（ＬＵＴ）参照サイクルにより読み出す。第１実施形態で説明した３次元ＬＵＴと同様に、Ｎ次元ＬＵＴを超四面体の基準頂点からのマンハッタン距離に基づき分割記憶する。このように構成することにより、ＬＵＴの分割数を２Ｎ−２個に抑制すると共に、分割個数を２のべき乗に設定可能となり、回路規模の低減が可能となる。なお、装置構成などは第１実施形態とほぼ同様のため、ここでは多次元ＬＵＴおよび参照値読み出し部について詳細に説明する。
【０１０４】
＜多次元ＬＵＴおよび参照値読み出し部＞
図１９は、Ｎ次元超四面体補間法における、基準点から対角点までの単位立体の各頂点をＮ次元マンハッタン距離Ｄｍを用いて分類した図である。まず、Ｎ次元の単位超立体を図に示される２Ｎ−３個の領域に分割する。なお、同一領域内のマンハッタン距離が図に示される関係を維持する限りにおいて、任意の２Ｎ−３個の領域に分割可能である。
【０１０５】
具体的には、Ｎ次元超四面体補間法において、頂点（ｘ０＜ｉ＞，ｘ１＜ｊ＞，ｘ２＜ｋ＞，…）から（ｘ０＜ｉ＋１＞，ｘ１＜ｊ＋１＞，ｘ２＜ｋ＋１＞，…）までの２３個の頂点ごとに、三次元四面体補間法のときの３次元ＬＵＴの分割記憶方法を適用すればよい。
【０１０６】
分割された領域は２Ｎ−３個あり、１つの領域に対し２個のサブメモリを用いて分割記憶される、そのため、多次元ＬＵＴは全部で２Ｎ−２個のサブメモリに分割記憶されることとなる。以後、これらの個々の領域をクラスタリング単位と呼び、この単位の数だけサブメモリが集まったものをクラスタ・サブメモリと呼び、領域総数（＝２Ｎ−３）をクラスタ数と呼ぶことにする。
【０１０７】
なお、図１９では第２実施形態（Ｎ＝４）における図１５の領域１５００及び１５０１に対応する領域（クラスタ・サブメモリ）を単位矩形で表している。また、クラスタ・サブメモリを示す矩形内には、Ｄｍ＝０，１，２，３におけるそれぞれの頂点の数１，３，３，１が表記してある。
【０１０８】
Ｎ次元の場合は、Ｄｍ＝０〜Ｎに対して、頂点がそれぞれＮＣ０，ＮＣ１，ＮＣ２，…，ＮＣＮ−１，ＮＣＮ個必要である。そこで、図１９に示すように
Ｓ＝Ｎ−３Ｃ０＋Ｎ−３Ｃ１＋…＋Ｎ−３ＣＮ−４＋Ｎ−３ＣＮ−３
と表されるＳ個のクラスタ・サブメモリを、各Ｄｍにおけるサブメモリ上の頂点の数の和が、上述した頂点の数になるようにマッピングすることにより、各Ｄｍにおける所望の数の頂点の参照値をメモリに格納することが可能となる理解できる。そして、それぞれのクラスタ・サブメモリについて基準点からのマンハッタン距離Ｄｍが偶数の頂点と奇数の頂点で別々のサブメモリに参照点を格納することにより、２Ｎ−２個のサブメモリに格納することが出来る。
【０１０９】
なお、図２０は、図１９において、Ｎ＝５，６，７の場合のそれぞれの分類図である。また、図２１は、Ｎ＝３〜７の場合における従来の技術との比較を示す図である。図２１は、多次元ＬＵＴの各軸が１５個の単位超立体（参照値は各軸１６点）により分割されている場合を例にとり、参照値の総数、サブメモリの個数、サブメモリ当たりの参照値の数を示している。図から分かるように、従来例１（特許文献１）では、サブメモリ当たりの参照値の数は２の冪乗の数となっているが、サブメモリへの分割数が２Ｎ個必要である。また、従来例２（特許文献２）では、サブメモリへの分割数はＮ＋１個に低減可能であるが、Ｎが（２の冪乗−１）の値でない場合サブメモリ当たりの参照値の数は２の冪乗の数にならない。一方、本実施形態によれば、サブメモリへの分割数を２Ｎ−２個に低減可能であると共に、サブメモリ１つ当たりに記憶される参照値の数が常に２の冪乗個となる。そのため、サブメモリへのアクセスするためのアドレス生成をＮ個の信号値の分割された上位ビット信号又は上位ビット信号に１加算した値のビット連結により容易に生成することが可能である。つまり、割り算器が不要となり回路規模を抑制可能となる。
【０１１０】
以上説明したように、Ｎ次元の場合のデータ変換処理である第３実施形態によれば、多次元ＬＵＴ９６０を２Ｎ−２個のサブメモリに格納すると共に、２サイクルで参照点を読み出して補間演算する技術について説明した。このように構成することにより、背景技術で述べた２つの特許文献に開示された技術に比較し、より少ないサブメモリとすることが出来、ＬＵＴ読み出しの周辺回路の規模を低減可能とすることが可能となる。また、サブメモリをアクセスするためのアドレス生成が簡易となる。
【０１１１】
（他の実施形態）
以上、本発明の実施形態について詳述したが、本発明は、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【０１１２】
なお、本発明は、前述した実施形態の機能を実現するプログラムを、システム或いは装置に直接或いは遠隔から供給し、そのシステム或いは装置が、供給されたプログラムコードを読み出して実行することによっても達成される。従って、本発明の機能処理をコンピュータで実現するために、コンピュータにインストールされるプログラムコード自体も本発明の技術的範囲に含まれる。
【０１１３】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等、プログラムの形態を問わない。
【０１１４】
プログラムを供給するための記録媒体としては、例えば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−Ｒ）などがある。
【０１１５】
その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、ホームページから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードすることによっても供給できる。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明のクレームに含まれるものである。
【０１１６】
また、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布し、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせ、その鍵情報を使用することにより暗号化されたプログラムを実行してコンピュータにインストールさせて実現することも可能である。
【０１１７】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現され得る。
【０１１８】
さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現される。
【図面の簡単な説明】
【０１１９】
【図１】三次元ルックアップ・テーブル（３Ｄ−ＬＵＴ）を用い三次元補間演算を行なう色空間変換装置の機能ブロックを例示的に示す図である。
【図２】三次元の色空間（例えば、ＲＧＢ空間）を単位立体により分割した状態を示す図である。
【図３】四面体補間法に用いられる６つのタイプの四面体を示す図である。
【図４】ＲＧＢ空間の一部分を切り出したものである（ｉ）。
【図５】ＲＧＢ空間の一部分を切り出したものである（ｉｉ）。
【図６】三次元四面体補間法における、基準点から対角点までの単位立体の各頂点を三次元マンハッタン距離Ｄｍを用いて分類した図である。
【図７】四次元超四面体補間法における、基準点から対角点までの単位立体の各頂点を四次元マンハッタン距離Ｄｍを用いて分類した図である。
【図８】第１実施形態に係るカラー複写機８００の例示的な内部構成図である。
【図９】第１実施形態に係る画像処理部８３０内の色空間変換部のブロック構成図である。
【図１０】ＲＧＢ空間の一部分を切り出したものである（第１実施形態）。
【図１１】第１実施形態に係る参照値読み出し部１１０１および３Ｄ−ＬＵＴ１１００の内部構成を例示的に示す図である。
【図１２】第１実施形態に係る参照値読み出し部１１０１が３Ｄ−ＬＵＴ１１００から４個の参照値を２サイクルで読み出す際のタイミングチャートである。
【図１３】第１実施形態に係る補間演算部における演算を例示的に示す図である。
【図１４】第１実施形態に係る補間演算部におけるタイミングチャートである。
【図１５】四次元超四面体補間法における、基準点から対角点までの単位立体の各頂点を四次元マンハッタン距離Ｄｍを用いて分類した図である。
【図１６】第２実施形態に係る参照値読み出し部１６０１および多次元ＬＵＴ１６００の内部構成を例示的に示す図である。
【図１７】第２実施形態に係る補間演算部における演算を例示的に示す図である。
【図１８】第２実施形態に係る補間演算部におけるタイミングチャートである。
【図１９】Ｎ次元超四面体補間法における、基準点から対角点までの単位立体の各頂点をＮ次元マンハッタン距離Ｄｍを用いて分類した図である。
【図２０】Ｎ＝５，６，７の場合のそれぞれの分類図である。
【図２１】Ｎ＝３〜７の場合における従来の技術との比較を示す図である。
【図１】
2007174392.tif 000009
【図２】
2007174392.tif 000010
【図３】
2007174392.tif 000011
【図４】
2007174392.tif 000012
【図５】
2007174392.tif 000013
【図６】
2007174392.tif 000014
【図７】
2007174392.tif 000015
【図８】
2007174392.tif 000016
【図９】
2007174392.tif 000017
【図１０】
2007174392.tif 000018
【図１１】
2007174392.tif 000019
【図１２】
2007174392.tif 000020
【図１３】
2007174392.tif 000021
【図１４】
2007174392.tif 000022
【図１５】
2007174392.tif 000023
【図１６】
2007174392.tif 000024
【図１７】
2007174392.tif 000025
【図１８】
2007174392.tif 000026
【図１９】
2007174392.tif 000027
【図２０】
2007174392.tif 000028
【図２１】
2007174392.tif 000029