(57)【要約】【課題】  従来のＮ次元超四面体（Ｎ+１面体）補間演算においては、演算に必要なN+1個の参照値を並列に読み出すのに、多次元ＬＵＴを２N個のサブメモリに分割して用いていたため、メモリインターフェースの周辺回路も２N個用意する必要があり、回路規模の増大を招いていた。また、別の手法では、サブメモリの数はN+1個という最小個数を用いる方法があるが、各サブメモリの容量が２のべき乗でないため、メモリのアドレス生成に割り算器が必要となり、回路規模の増大を招いていた。【解決手段】  本発明のＮ次元データ変換装置は、３次元では前記サブメモリの容量が２のべき乗となることに着目し、３次元LUTをベースにマッピングを行うことで、前記サブメモリの容量を２のべき乗とする。  また、補間演算において、同時に参照されない点を纏めて１つのメモリに格納することにより、サブメモリの個数を削減する。【選択図】  図１
2010103912.tif 000002
【特許請求の範囲】
【請求項１】
入力したＮ次元ベクトル信号値から新たなスカラ信号値を出力する多次元データ変換装置であって、前記ベクトル信号値の各成分を各々上位データと下位データに分割する分割手段と、分割された前記上位データのすべての組み合わせに対応する参照値を記憶したメモリ手段と、前記参照値を読み出す手段と、前記参照値と前記下位データに基づき補間演算を行なう補間演算手段とを具備し、前記メモリ手段は参照値を重複することなく２のべき乗個のサブメモリに分割記憶することを特徴とする多次元データ変換装置。
【請求項２】
前記、サブメモリのアドレス数は、２のべき乗であることを特徴とする、請求項1に記載の多次元データ変換装置。
【請求項３】
前記、各サブメモリのアドレス数は、最も小さいサブメモリのアドレス数の整数倍であることを特徴とする、請求項1に記載の多次元データ変換装置。
【請求項４】
前記サブメモリのアドレスは、前記ベクトル信号の上位データ又は、前記ベクトル信号の上位データに1加算された値を、全成分分ビット連結させて生成することを特徴とする、請求項1に記載の多次元データ変換装置。
【請求項５】
前記サブメモリのアドレスの生成において、各成分の各ベクトル成分の上位データに1加算するか否かの判定は、前記N個のベクトル信号の下位データの大小関係により判定することを特徴とする、請求項４に記載の多次元データ変換装置。
【請求項６】
入力したＮ次元ベクトル信号値から新たなスカラ信号値を出力する多次元データ変換装置であって、前記ベクトル信号値の各成分を各々上位データと下位データに分割する分割手段と、分割された前記上位データのすべての組み合わせに対応する参照値を記憶したメモリ手段と、前記参照値を読み出す手段と、前記参照値と前記下位データに基づき補間演算を行なう補間演算手段とを具備し、前記メモリ手段は参照値を重複することなく4の倍数個のサブメモリに分割記憶することを特徴とする多次元データ変換装置。
【請求項７】
前記、サブメモリのアドレス数は、２のべき乗であることを特徴とする、請求項６に記載の多次元データ変換装置。
【請求項８】
前記、各サブメモリのアドレス数（エントリ数）が、全て等しいことを特徴とする、請求項６に記載の多次元データ変換装置。
【請求項９】
前記サブメモリのアドレスは、前記ベクトル信号の上位データ又は、前記ベクトル信号の上位データに1加算された値を、全成分分ビット連結させて生成することを特徴とする、請求項６に記載の多次元データ変換装置。
【請求項１０】
前記サブメモリのアドレスの生成において、各成分の各ベクトル成分の上位データに1加算するか否かの判定は、前記N個のベクトル信号の下位データの大小関係により判定することを特徴とする、請求項９に記載の多次元データ変換装置。
【請求項１１】
前記サブメモリの語長は、前記参照値のビット幅の整数倍であることを特徴とする、請求項６に記載の多次元データ変換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力デジタル画像信号の色空間変換に応用できる、多次元データ変換装置及び方法に関するものである。
【背景技術】
【０００２】
近年、入力機器としては、スキャナ、ビデオカメラなどが普及している。一方、出力機器としては、インクジェット、染料熱昇華型あるいは電子写真などの方式を用いた、各種カラープリンタが普及している。これらのカラー入，出力機器は、それぞれ固有の色空間を有しており、例えばあるスキャナで得たカラー画像をそのまま別のカラープリンタに転送して印刷した場合、印刷されたカラー画像の色がスキャナによって読取られたオリジナルのカラー画像の色と一致することはほとんどない。
【０００３】
このようなカラー画像等に対するデバイス間での色再現性の問題を解決するためには、入力デバイスの色空間を出力デバイスの色空間に変換する処理（“色空間変換”と呼ぶ）が必要となり、入,出力機器の色彩再現性能を高めるために、色空間変換機能が入,出力機器に搭載されている。
【０００４】
この色空間変換とは、具体的には入力γ補正，輝度濃度変換，マスキング，黒生成，ＵＣＲ，出力γ補正等の一連の画像処理全体、もしくはその中の一定の処理を指す。一般的には、入力デバイスの３色（例えば、レッド，ブルー，グリーンの３色、以下、“ＲＧＢ”と略す）のデジタル画像信号を同時に参照して、出力デバイスの３色（例えば、シアン，マゼンタ，イエローの３色、以下、“CMY”）あるいは４色（例えば、シアン，マゼンタ，イエロー，ブラックの４色、以下、“CMYK”）のデジタル画像信号に変換することが多い。また電子写真方式の複写機の場合、稼働時間とともにプリンタのエンジン特性が変化するため、定期的なキャリブレーションが必要となる。このような場合は、入力デバイスの４色（例えば、“CMYK”）から出力デバイスの４色（例えば、“C'M'Y'K'”）の変換も必要となる。
【０００５】
色空間変換の実現方法として、予め変換結果をルックアップ・テーブル（以下、“ＬＵＴ”）としてメモリに記憶しておき、入力されたデジタル画像信号に対してそのＬＵＴから変換結果を出力する方法がある。このＬＵＴを用いた色空間変換方法では、ＬＵＴのメモリを削減するため補間演算を併用するのが一般的である。上記例にある、３色入力のデジタル画像信号に対する色空間変換は、三次元補間演算を用いて実現する。また、４色入力のデジタル画像信号に対する色空間変換は、四次元補間演算を用いて実現する。
【０００６】
以下、３色入力のデジタル画像信号に対して、三次元ルックアップ・テーブル（以下、“３Ｄ-ＬＵＴ”）と三次元補間演算を併用した色空間変換方法について説明する。
【０００７】
図１０は、３Ｄ-ＬＵＴを用いて三次元補間演算を行なう場合の機能ブロックである。入力デジタル画像信号（Ｒ、Ｇ、Ｂ）1００５に対し補間値Ｘ １０３５を得る。入力デジタル画像信号（Ｒ、Ｇ、Ｂ）1００５はデータ分割部１０１０によって上位ビット１０１５と下位ビット１０１８に分離される。上位ビット１０１５は３Ｄ-ＬＵＴ１０２０から補間演算に必要な複数の参照値ＲＤ１０２５を取り出すときに使用される。また、下位ビット１０１８は重み係数ｇ として補間演算に使用される。補間演算部１０３０は重み係数ｇ と３Ｄ-ＬＵＴ１０２０からの参照値ＲＤ１０２５との積和演算により補間値Ｘ １０３５を計算している。
【０００８】
図１１は三次元入力の色空間（ＲＧＢ空間）を各軸方向に限定数で分割することで、単位立体に分割した状態を示している。この単位立体の頂点における色空間変換後の色データを参照値ＲＤ１０２５として３Ｄ-ＬＵＴ１０２０に記憶している。３つのデジタル画像信号の上位ビット１０１５を色空間の座標と考え、補間演算に使用する単位立体を選択し（図１１中の塗りつぶし部分）、単位立体の頂点に対応する参照値ＲＤ１０２５を補間演算に使用する。
【０００９】
また、このとき使用される三次元補間演算の方法として四面体補間法がある。この補間法は図１２（１）〜図１２（６）のType０からType５に示すように上記単位立体を６つの四面体に分割して、入力座標がどの四面体に属するかによって下記式を用い補間演算する。下記式では、図１２（７）の単位立体の頂点に対応する参照値ＲＤ１０２５の値をＰ０〜Ｐ７とし、重み係数ｇ をΔＲ、ΔＧ、ΔＢとしている。Type０からType５のどの四面体を選択するかは、ΔＲ、ΔＧ、ΔＢの大小関係により決定される。
【００１０】
【数１】
2010103912.tif 000003
【００１１】
また、これまで説明した三次元四面体補間法は多次元化可能である。以下に多次元超四面体補間法について説明する。図１１に示す三次元直交座標に固定された空間を多次元化し、Ｎ次元直交座標に固定された空間にした場合、図１１に示す単位立体は多次元の単位超立体（Ｎ次元超立体、もしくは超六面体と呼ぶ）に多次元化される。そして三次元四面体補間法で使用された四面体は、この多次元化により超四面体と呼ばれるＮ+１面体に多次元化される。この超四面体は、単位超立体の基準点と対角点を結ぶ線と、超立体の互いに直交し、かつ連結しているＮ本の稜線によって形成される。そして１つの単位超立体を分割し、Ｎ！個の超四面体を作ることができる（後述）。単位超立体から超四面体を切り出す過程で選択したＮ本の稜線は互いに垂直であり、Ｎ次元直交座標の各軸方向にそれぞれ平行であるため、各軸方向の出力変移量の線形和を基準点出力値に加算した値が多次元補間演算の出力となる。したがって、選択された稜線の両端点における参照値の差分値に、各稜線上での基準点からの距離を乗算して、それら乗算値を基準点の参照値に累積加算することで補間演算を行なえる。
【００１２】
次に四次元空間（X0,X1,X2,X3）を例に、四次元超四面体補間法の稜線選択のし方を図１５にて説明する。図１５は入力座標を（X0<i>+ΔX0,X1<j>+ΔX1,X2<k>+ΔX2,X3<l>+ΔX3）とし、基準点座標（X0<i>,X1<j>,X2<k>,X3<l>）との差（ΔX0,ΔX1,ΔX2,ΔX3）の大小関係が、｛ΔX0>ΔX1>ΔX2>ΔX3｝の場合の稜線選択を示している。まず図１５（１）に示すように最も変移量の大きいΔX0に対応するX0軸と平行で、かつ基準点を端点にもつ稜線、つまり（X0<i>,X1<j>,X2<k>,X3<l>）と（X0<i+1>,X1<j>,X2<k>,X3<l>）とを両端点に持つ稜線が選択される。次に図１５（２）に示すように２番目に変移量の大きいΔX1に対応するX1軸と平行で、かつ（X0<i+1>,X1<j>,X2<k>,X3<l>）を端点にもつ稜線、つまり（X0<i+1>,X1<j>,X2<k>,X3<l>）と（X0<i+1>,X1<j+1>,X2<k>,X3<l>）とを両端点に持つ稜線が選択される。次に図１５（３）に示すように３番目に変移量の大きいΔX2に対応するX2軸と平行で、かつ（X0<i+1>,X1<j+1>,X2<k>,X3<l>）を端点にもつ稜線、つまり（X0<i+1>,X1<j+1>,X2<k>,X3<l>）と（X0<i+1>,X1<j+1>,X2<k+1>,X3<l>）とを両端点に持つ稜線が選択される。最後に、図１５（４）に示すように最も変移量の少ないΔX3に対応するX3軸と平行で、かつ（X0<i+1>,X1<j+1>,X2<k+1>,X3<l>）を端点にもつ稜線、つまり（X0<i+1>,X1<j+1>,X2<k+1>,X3<l>）と（X0<i+1>,X1<j+1>,X2<k+1>,X3<l+1>）とを両端点に持つ稜線が選択される。
【００１３】
最終的に、（X0<i>,X1<j>,X2<k>,X3<l>）、（X0<i+1>,X1<j>,X2<k>,X3<l>）、（X0<i+1>,X1<j+1>,X2<k>, X3<l>）、（X0<i+1>,X1<j+1>,X2<k+1>,X3<l>）、（X0<i+1>,X1<j+1>,X2<k+1>,X3<l+1>）の５頂点で構成される超四面体（５面体）が決定される。このとき基準点（X0<i>,X1<j>,X2<k>,X3<l>）から最も遠い点（X0<i+1>,X1<j+1>,X2<k+1>,X3<l+1>）を対角点と呼び、基準点と対角点を結ぶ線を対角線と呼ぶことにする。多次元超四面体補間法は、基準点と対角点は入力座標と基準点座標との差（ΔX0,ΔX1,ΔX2,ΔX3）の大小関係にかかわらず、必ず超四面体の頂点として選択されるという特徴を持つ。そこで、単位超立体から入力座標に対応する超四面体を選択する工程は、基準点をスタート、対角点をゴール、各稜線をスタートからゴールまでの経路と見立てれば、基準点から対角点までの経路選択問題と考えることができる。この場合経路の採り得る“場合の数”は、４！=４×３×２×１=２４通りになり、四次元補間演算では単位超立体から２４個の超四面体が分割できることが分かる。同様にＮ次元補間演算の場合、単位超立体からＮ！個の超四面体が分割できることが分かる。
【００１４】
次にＮ次元補間演算について説明する。Ｎ次元直交座標に固定された空間（Ｘ0, Ｘ1,・・・,ＸN-1）上の座標（X0<i>,X1<j>,X2<k>,…XN-2<a>,XN-1<b>）の参照値をＰ<i,j,k,...,a,b>とする。また、ある入力座標によって選択された超立体の基準点の座標を（X0<i>,X1<j>,X2<k>,…XN-2<a>,XN-1<b>）とし、入力座標と基準点座標との差を（ΔX0,ΔX1,ΔX2,...,ΔXN-2,ΔXN-1）とする。｛ΔX0>ΔX1>ΔX2>...>ΔXN-2>ΔXN-1｝の関係が成り立つ場合、補間値Ｘは下記式を用いて求めることができる。
【００１５】
【数２】
2010103912.tif 000004
さらに、他の従来の技術について説明する。三次元立方体[トライリニア]補間法を高速に実行するためのハードウェアが米国特許４８３７７２２号明細書に記載されている。また、三次元四面体補間法の場合にも有効であることが記載されている。この特許を従来例１として説明する。この従来例１では３Ｄ-ＬＵＴを８個のメモリに分けて記憶し、３Ｄ-ＬＵＴから参照値を並列に読み出すことで高速化している。３Ｄ-ＬＵＴの８分割の方法を図１３を用いて説明する。図１３は、図１１で示したＲＧＢ空間の一部分を切り出したものである。図中の８個のマーク（●、△、◇、塗りつぶし三角、○、◆、■、◎）は同一のメモリに記憶される参照値のＲＧＢ空間上での位置を示している。●印で示されている位置の参照値は、０番のメモリに記憶される。同様に、△印で示されている位置の参照値は１番のメモリに、◇印で示されている位置の参照値は２番のメモリに、塗りつぶし三角印で示されている位置の参照値は３番のメモリに、○印で示されている位置の参照値は４番のメモリに、◆印で示されている位置の参照値は５番のメモリに、■印で示されている位置の参照値は６番のメモリに、◎印で示されている位置の参照値は７番のメモリに記憶される。このように、補間に使用する単位立体の各頂点に対応する参照値がすべて異なるメモリに記憶されているため、メモリから参照値を読み出すときにアクセスが競合することはない。また、従来例１では、重複することなく、３Ｄ-ＬＵＴを均等に８個のメモリに分割記憶している（以後、多次元ＬＵＴから参照値を並列に読み出すために多次元ＬＵＴを複数のメモリに分割記憶したとき、この分けられたメモリを“サブメモリ”と呼ぶことにする）。従来例１は、三次元補間法に限定した記載しかなされていないが、従来例１の方法を用いて多次元補間演算を行なう場合、多次元ＬＵＴを２N個のサブメモリに分割記憶すればよいことは容易に理解できる。
【００１６】
また、３Ｄ-ＬＵＴを重複なく４つのサブメモリに分割記憶し、参照値を並列に読み出すことで三次元四面体補間法を高速に実行するハードウェアが、特開平１０-３０７９１１号公報に記載されており、この出願を従来例２として説明する。使用するサブメモリの個数が少ないという点で、従来例１より従来例２は優位である。図１４を用い、３Ｄ-ＬＵＴの４分割のし方を説明する。図１４は、図１１で示したＲＧＢ空間の一部分を切り出したものである。図中の４個のマーク（●、◇、塗りつぶし三角、◎）は同一のサブメモリに記憶される参照値のＲＧＢ空間上での位置を示している。●印で示されている位置の参照値は、０番のサブメモリに記憶される。同様に、◇印で示されている位置の参照値は１番のサブメモリに、塗りつぶし三角印で示されている位置の参照値は２番のサブメモリに、◎印で示されている位置の参照値は３番のサブメモリに記憶される。三次元四面体補間法の場合、選択された四面体の頂点に対応する４つの参照値を並列に読み出すことができれば、補間演算を高速化できる。また従来例２も従来例１同様に、重複することなく、３Ｄ-ＬＵＴを均等に４個のサブメモリに分割記憶している。さらに従来例２のＬＵＴの分割方法は多次元化されており、Ｎ次元入力の超四面体（Ｎ+１面体）補間法に対し、多次元ＬＵＴをＮ+１個のサブメモリに分割記憶できる。
【００１７】
従来例２の図１４に示す３Ｄ-ＬＵＴの分割方法では、図１２（１）から図１２（６）のＴｙｐｅ０からＴｙｐｅ５の６種の四面体を選択した場合に、各サブメモリから参照値を読み出すときにアクセスが競合することはない。図１６と下記式を用いてさらに詳細説明する。まず、Ｎ次元直交座標に固定された空間上の２点 A(Ｘ0<i1>,Ｘ1<j1>,Ｘ2<k1>,…,ＸN-2<a1>,ＸN-1<b1>)とB(Ｘ0<i2>,Ｘ1<j2>,Ｘ2<k2>,…,ＸN-2<a2>,ＸN-1<b2>)の距離を下記式で定義し、Ｎ次元マンハッタン距離Ｄｍとする。
【００１８】
【数３】
2010103912.tif 000005
図１６は従来例２の三次元四面体補間法における、基準点から対角点までの各単位立体の頂点を三次元マンハッタン距離Ｄｍを用いて分類した図である。基準点(Ｘ0<i>,Ｘ1<j>,Ｘ2<k>)はマンハッタン距離Ｄｍ=０となり、(Ｘ0<i+1>,Ｘ1<j>,Ｘ2<k>)、(Ｘ0<i>,Ｘ1<j+1>,Ｘ2<k>)、(Ｘ0<i>,Ｘ1<j>,Ｘ2<k+1>)の３点はマンハッタン距離Ｄｍ=１となり、(Ｘ0<i+1>,Ｘ1<j+1>,Ｘ2<k>)、(Ｘ0<i>,Ｘ1<j+1>,Ｘ2<k+1>)、(Ｘ0<i+1>,Ｘ1<j>,Ｘ2<k+1>)の３点はマンハッタン距離Ｄｍ=２となり、対角点(Ｘ0<i+1>,Ｘ1<j+1>,Ｘ2<k+1>)はマンハッタン距離Ｄｍ=３となる。単位超立体から補間演算に使用する超四面体を選択する工程は、基準点からどの頂点を通って対角点に到達するかという経路選択問題と考えられるため、マンハッタン距離Ｄｍが同一の頂点群からは常に１つの頂点のみが選択される。つまりマンハッタン距離が同一の頂点群を同じサブメモリに記憶した場合は、そのサブメモリから異なる２頂点は同時には読み出されることはない。そのためそのサブメモリへのアクセスが競合することはない。図１６中、Mem０,Mem１,…,Mem３と記載された太線で囲まれた頂点が同一のサブメモリに記憶され、三次元四面体補間法では、３Ｄ-ＬＵＴを４個のサブメモリに分割記憶できることが理解できる。さらに図１７に四次元超四面体補間法における、基準点から対角点までの単位立体の各頂点を四次元マンハッタン距離Ｄｍを用いて分類した結果を示す。図１７中、Mem０,Mem１,…,Mem４と記載された太線で囲まれた頂点は同一のサブメモリに記憶され、四次元超四面体補間法では、多次元ＬＵＴを５個のサブメモリに分割記憶できることが理解できる。
【００１９】
また、Ｎ=３,４,５,６の場合の従来例１と従来例２の比較を図９の表に示す。図９は多次元ＬＵＴの各軸が、１５個の単位超立体により分割されている（各軸の参照値は１６点となる）場合を例にとり、参照値の総数、サブメモリの個数、サブメモリ当たりの参照値の数を示している。表から分かるように、従来例１では参照値が２N個のサブメモリに分割記憶されるため、サブメモリ当たりの参照値の数も２の冪乗の数となっている。従来例２ではＮ+１個のサブメモリに分割記憶されるため、Ｎが２の冪乗-１の値でない場合、サブメモリ当たりの参照値の数も２の冪乗の数にならないことが分かる（従来例２でもＮ=３のときは、サブメモリが２２個に分割記憶されるため、サブメモリ当たりの参照値の数も２の冪乗の数になる）。
【００２０】
【特許文献１】米国特許４８３７７２２号明細書
【特許文献２】特開平１０-３０７９１１号公報
【発明の開示】
【発明が解決しようとする課題】
【００２１】
前述した従来例１および従来例２ともに、多次元ＬＵＴを複数のサブメモリに分割記憶することで、参照値の読み出しを並列化でき、Ｎ次元補間演算を高速に処理するハードウェアを実現している。
【００２２】
従来例１は、単位超立体の頂点に対応するＮ個の参照値をそれぞれ独立したＮ個のサブメモリに記憶し、多次元ＬＵＴを２Ｎ個に分割している。そのため多次元四面体補間法以外の補間法（たとえば、多次元立体[トライリニア]補間法、多次元三角柱［プリズム］補間法など）も実現可能であるという利点を持っている。しかしながら、多次元四面体補間法を採用することが前提になっている場合、補間演算に必要なＮ+１個の参照値をサブメモリから並列読み出しするために、メモリインターフェースなどのメモリ周辺回路を２Ｎ個持つことになり、回路が大きくなるという問題点がある。
【００２３】
逆に、従来例２は多次元四面体補間法のみに限定することで、多次元ＬＵＴをＮ+１個という最小限の個数のサブメモリに分割記憶している。そのためメモリ周辺回路も最適な規模であるという利点を持っている。しかしながら、従来例２はＮが２の冪乗-1でないときは、サブメモリの個数が２の冪乗にならない。たとえばＮ=４の場合、従来例２ではサブメモリの個数が５個となる。従来例２の手法ではサブメモリをアクセスするためのアドレスを生成するときに割り算器が必要となり、シフト演算やビットマスクだけでアドレス生成できないという問題が生じる。また、一般的にメモリは２の冪乗のワード数で製品化されているため市場に流通しているメモリを利用してサブメモリを構成する場合、従来例２ではワード数が余剰なメモリを採用しなければならないという問題が生じる。
【００２４】
本発明の目的は、Ｎ次元超四面体（Ｎ+１面体）補間演算を高速に処理するために、補間演算に必要なＮ+１個の参照値を並列に読み出すことが可能で、前記参照値を記憶するサブメモリが２Ｎ個より少なく、サブメモリをアクセスするためのアドレス生成が簡易である、多次元補間装置を提供することである。
【課題を解決するための手段】
【００２５】
本発明のＮ次元データ変換装置は、３次元では前記サブメモリの容量が２のべき乗となることに着目し、３Ｄ−ＬＵＴをベースにマッピングを行うことで、前記サブメモリの容量を２のべき乗とすることを特徴とする。
【発明の効果】
【００２６】
本発明のＮ次元データ変換装置は、入力したＮ個の信号値の分割された上位ビット信号すべての組み合わせに対応する参照値を重複することなく２のべき乗個のサブメモリに分割記憶することが可能で、また補間演算に必要なＮ+１個の参照値を同時に読み出すことができるため補間演算を高速化可能で、またサブメモリへのアクセスするためのアドレス生成を前記Ｎ個の信号値の分割された上位ビット信号又は上位ビット信号に１加算した値のビット連結により容易に生成することが可能であるため、割り算器が不要となり、高速かつコンパクトな多次元データ変換が実現できる。
【発明を実施するための最良の形態】
【００２７】
次に、本発明の詳細を実施例の記述に従って説明する。
【００２８】
次に、本発明の実施の形態について図面を参照して説明する。図１に、一般的なカラー複写機の全体構成例を示す。画像読取り部１２０は、ＣＣＤセンサ１２４、アナログ信号処理部１２６等により構成され、レンズ１２２を介しＣＣＤセンサ１２４に結像された原稿１００の画像が、ＣＣＤセンサ１２４によりＲ,Ｇ,Ｂのアナログ電気信号に変換される。変換された画像情報は、アナログ信号処理部１２６に入力され、Ｒ,Ｇ,Ｂの各色毎に補正等が行われた後にアナログ・デジタル変換（Ａ／Ｄ変換）される。デジタル化されたフルカラー信号（以下、デジタル画像信号という）は、画像処理部１３０に入力される。画像処理部１３０はデジタル画像信号に対し、入力γ補正、色空間変換、濃度補正、スクリーン処理を施し、プリンタ部１４０へ処理後のデジタル画像信号を出力する。プリンタ部１４０は、例えば、レーザ等からなる露光制御部（図示せず）、画像形成部（図示せず）、転写紙の搬送制御部（図示せず）等により構成され、入力されたデジタル画像信号により転写紙上に画像を記録する。また、ＣＰＵ回路部１１０は、演算制御用のＣＰＵ１１２、固定データやプログラムを格納するＲＯＭ１１４、データの一時保存やプログラムのロードに使用されるＲＡＭ１１６等により構成され、画像読み取り部１２０、画像処理部１３０、プリンタ部１４０等を制御し、本装置のシーケンスを統括的に制御する。外部記憶装置１１８は、本装置が使用するパラメータやプログラムを記憶するディスク等の媒体であり、ＲＡＭ１１６のデータやプログラム等は、外部記憶装置１１８からロードされる構成としても構わない。
【００２９】
本発明で開示されている多次元データ変換装置は、前記の画像処理部１３０で行なわれる色空間変換を実現している。以下、図２を用いて多次元補間装置の回路構成と処理の流れについて詳しく説明する。本発明の多次元データ変換装置はＮ次元の入力信号に対し補間演算を行ない、新たな信号を出力する。まず、前述のデジタル画像信号２０５が多次元データ変換装置に入力される。このデジタル画像信号２０５はＮ入力の信号である。デジタル画像信号２０５はデータ分割部２１０で上位ビット信号２１２と下位ビット信号２１４に分割される。デジタル画像信号２０５がＮ入力の信号であったため、データ分割後の上位ビット信号２１２と下位ビット信号２１４はともにＮ本の信号となる。一般的に上位ビット信号２１２は、補間演算のときに使用される単位超立体の個数に応じてそのビット数が決定される。たとえば、Ｎ次元空間のある軸について単位超立体が２ｘ-１個ある場合、その軸に対応する上位ビット信号２１２のビット数はｘビットとなる。また、一般的に下位ビット信号２１４は、デジタル画像信号２０５のビット数から上位ビット信号２１２のビット数を差し引いた、残りのビット数で表現される。次に順序判定部２３０は、Ｎ本の下位ビット信号２１４を受け取り、下位ビット信号２１４の大小関係を判定し、順序信号２３２として出力する。この順序信号２３２は、前述の単位超立体から補間演算に使用する超四面体（Ｎ+１面体）の稜線を選択する工程に従い、予め定められたＮ！通りの稜線選択パターンを指し示す信号である。重み係数算出部２４０は下位ビット信号２１４をもとに、補間演算の重み係数信号２４２を算出し、補間演算部２７０に出力する。このとき下位ビット信号２１４から重み係数２４２を算出する方法は、対応表を予めテーブルＲＯＭ化し、ＲＯＭから重み係数２４２を読み出すことで変換しても良いし、予め定められた計算式により算出しても良い。また、参照値読み出し部２５０は、Ｎ本の上位ビット信号２１２と参照信号２３２を用いて多次元ＬＵＴ２６０からＮ+１個の参照値を読み出し、参照値信号２５２として出力する。多次元ＬＵＴ２６０は複数個のサブメモリで実現されており、参照値読み出し部２５０はサブメモリの個数と等しい本数のアドレス信号２５４を各サブメモリに出力して各サブメモリをアクセスし、各サブメモリからデータ信号２６２を受け取る。補間演算部２７０はＮ+１本の参照値信号２５２とＮ本の重み係数信号２４２を受け、前述した補間演算式に従い補間演算を行い、１本の出力信号２７５を出力する。
【実施例１】
【００３０】
次にＮ次元超四面体補間法において多次元ＬＵＴ２６０の参照値を重複することなく、２のべき乗個のサブメモリに分割記憶する方法について説明する。
【００３１】
まず図３を用いて３次元の場合に関して、参照値読み出し部２５０と多次元ＬＵＴ２６０を詳細説明する。300の点線で囲まれた部分は図２の260と同等な多次元LUTであり、301の点線で囲まれた部分は図２の250と同等な参照値読み出し部である。302はアドレス生成回路であり、303, 304, 305の3個のデジタル画像信号の上位ビット信号Rh[x-1:0],  Gh[x-1:0],  Bh[x-1:0]であり、306は図２の232と同等な順序信号である。ここで、xは前述のビット数を示している。３０7, ３０８，３０９，３１０は３次元補間の基準点,  基準値側頂点（頂点1）, 対角点側頂点（頂点２）, 対角点のそれぞれの参照値をメモリから読み出すためのアドレス信号MA0, MA1, MA2, MA3であり、311, 312, 313, 314はそれぞれ、アドレス選択回路３１５，３１６，３１７，３１８及び、データ選択回路３３１，３３２，３３３，３３４の選択信号となる、サブメモリ・バンク選択信号SEL0[1:0], SEL1[1:0], SEL2[1:0], SEL3[1:0]である。323, 324, 325, 326はそれぞれサブメモリ３２３, サブメモリ３２４, サブメモリ３２５, サブメモリ３２６であり、315, 316, 317, 318はそれぞれ、サブメモリ３２３，３２４，３２５，３２６のアドレス選択回路である。319, 320, 321, 322はそれぞれ、アドレス選択回路315, 316, 317, 318から出力されたアドレス信号であり、それぞれサブメモリ３２３，３２４，３２５，３２６に供給される。また、331, 332, 333, 334はそれぞれデータ選択回路0, 1, 2, 3であり、327, 328, 329, 330はそれぞれサブメモリ323,324, 325, 326からの出力データ信号であり、全てのデータ選択回路331, 332, 333, 334に供給される。335, 336, 337, 338は図2の252と同等な参照信号であり、それぞれ、３次元補間の基準点,  頂点1, 頂点２, 対角点の参照値を示す。
【００３２】
次に、図３の動作を説明する。アドレス生成回路302が3個の信号Rh[x-1:0],  Gh[x-1:0],  Bh[x-1:0]を受けて、4組のアドレス信号MA0, MA1, MA2, MA3とサブメモリ・バンク選択信号SEL0[1:0], SEL1[1:0], SEL2[1:0], SEL3[1:0]を出力する。ここで、4本のメモリ・バンク選択信号は、各々が異なる値である。そして、アドレス信号MA0, MA1, MA2, MA3とサブメモリ・バンク選択信号SEL0[1:0], SEL1[1:0], SEL2[1:0], SEL3[1:0]が全てのアドレス選択回路３１５，３１６，３１７，３１８に入力される。各アドレス選択回路３１５，３１６，３１７，３１８は各々が異なるサブメモリ・バンクＩＤ “ＳｍＢ_ID"を有しており、自らが対応するサブメモリ・バンクＩＤ “ＳｍＢ_ID"と入力されたサブメモリ・バンク選択信号が等しいアドレス信号を4本の中から１つ選択して出力し、サブメモリにアクセスする。サブメモリ３２３，３２４，３２５，３２６はそれぞれ受け取ったアドレス値319, 320, 321, 322の格子点データを出力データ信号327, 328,  329, 330として全てのデータ選択回路331, 332, 333, 334に供給する。データ選択回路331, 332, 333, 334ではそれぞれ入力されているサブメモリ・バンク選択信号SEL0, 1, 2, 3にしたがって、４本のサブメモリの出力から１本を選択して、参照データ335, 336, 337, 338として出力する。
【００３３】
次にアドレス生成回路302の動作を説明する。ここでは、R−G平面上４×４ブロック単位にメモリへマッピングするものとする。
（１）基準点用アドレス信号MA0の算出方法
基準点の４×４ブロックのアドレスBA0は
BA0 = Bh[x-1:0] & Rh[x-1:2] & Gh[x-1:2] ; （'&'はビット連結を表す）
また、基準点の４×４ブロック内のアドレスIBA0は
IBA0 = Gh[1:0] & Rh[1:0] ; 
となるが、４×４ブロック内を４つのメモリに分散するのでいずれか一方の軸のアドレスは不要となる。ここでは、G軸の連続性を優先して
IBA0’ = Gh[1:0]  ; 
とする。従って、基準点のメモリのアドレス信号MA0は、G軸の連続性を考慮して
MA0 = Bh[x-1:0] & Rh[x-1:2] & Gh[x-1:2] & Gh[1:0] = Bh[x-1:0] & Rh[x-1:2] & Gh[x-1:0] ;
と算出する。
【００３４】
サブメモリ・バンク選択信号SEL0[1:0]はフルアダー２個（FA0、FA1）とEXOR１個で構成され、
SEL0[0] = FA0(Bh[0], Rh[0], Gh[0] )[0] ;
SEL0[1] = FA1(Bh[1], Rh[1], Gh[1] )[0] xor FA0(Bh[0], Rh[0], Gh[0] )[1]  ;
と算出する。
（２）基準側頂点（頂点１）用アドレス信号MA1の算出
基準側頂点は１軸を＋１した座標であるので、Rh,Gh,Bhをインクリメントした値を各々Rh',Gh',Bh'、図２の下位ビット信号214をRl, Gl, Blとすると、Rl, Gl, Blの大小関係を順序信号306にしたがって、数２と同等に考えることにより、基準側頂点のメモリのアドレス信号MA1は
MA1 = Bh[x-1:0] & Rh'[x-1:2] & Gh[x-1:0] ;（Rl＞Gl＞Bl or Rl≧Bl≧Gl ）
MA1 = Bh[x-1:0] & Rh[x-1:2] & Gh'[x-1:0] ;（Gl＞Bl＞Rl or Gl≧Rl≧Bl ）
MA1 = Bh'[x-1:0] & Rh[x-1:2] & Gh[x-1:0] ;（Bl＞Rl＞Gl or Bl≧Gl≧Rl ）
と算出する。
【００３５】
サブメモリ・バンク選択信号SEL1[1:0]は
SEL1[0] = not SEL0[0] ;
SEL1[1] = SEL0[1] xor SEL0[0]  ;
と算出する。
（３）対角側頂点（頂点２）用アドレス信号MA2の算出
対角側頂点は２軸を＋１した座標であるので、Rl, Gl, Blの大小関係を順序信号306にしたがって、数１と同等に考えることにより、  対角側頂点のメモリのアドレス信号MA2は
MA2 = Bh[x-1:0] & Rh'[x-1:2] & Gh'[x-1:0] ;（Rl＞Gl＞Bl or Gl≧Rl≧Bl ）
MA2 = Bh'[x-1:0] & Rh[x-1:2] & Gh'[x-10] ;（Gl＞Bl＞Rl or Bl≧Gl≧Rl ）
MA2 = Bh'[x-1:0] & Rh'[x-1:2] & Gh[x-1:0] ;（Bl＞Rl＞Gl or Rl≧Bl≧Gl ）
と算出する。
【００３６】
サブメモリ・バンク選択信号SEL2[1:0]は
SEL2[0] = SEL0[0] ;
SEL2[1] = not SEL0[1] ;
と算出する。
（４）対角点用アドレス信号MA3の算出
対角点は３軸を＋１した座標であるので、数２と同等に考えることにより、対角点のメモリのアドレス信号MA3は
MA3 = Bh'[x-1..0] & Rh'[x-1..2] & Gh'[x-1..0] ;
と算出する。
【００３７】
サブメモリ・バンク選択信号SEL3は
SEL3[0] = not SEL0[0] ;
SEL3[1] = not ( SEL0[1] xor SEL0[0] ) ;
と算出する。
【００３８】
以上説明したように、３次元の場合は、多次元ＬＵＴ２６０の参照値を重複することなく、４個(2のべき乗個)のサブメモリに分割することが可能である。
【００３９】
次に、図４に四次元超四面体補間法における、基準点から対角点までの単位立体の各頂点を四次元マンハッタン距離Ｄｍを用いて分類した図を示す。三次元四面体補間法のときに３次元ＬＵＴを２2個のサブメモリに分割記憶できたことを利用し、四次元の単位超立体の基準点（X0<i>,X1<j>,X2<k>,X3<l>）から（X0<i+1>,X1<j+1>,X2<k+1>,X3<l>）までの２3個の頂点に対し三次元四面体補間法のときの３次元ＬＵＴの分割記憶方法を適用する（図中、領域４００）。また残った単位超立体の頂点（X0<i>,X1<j>,X2<k>,X3<l+1>）から（X0<i+1>,X1<j+1>,X2<k+1>,X3<l+1>）までの２3個の頂点に対し、さらに三次元四面体補間法のときの３次元ＬＵＴの分割記憶方法を適用する（図中、領域４０１）。最終的には、図中Mem０,…Mem７と記載された太線で囲まれた頂点が同一のサブメモリに記憶され、多次元ＬＵＴは２×２2個のサブメモリに分割記憶される。
【００４０】
同様に、Ｎ次元超四面体補間法において頂点（X0<i>,X1<j>,X2<k>,…）から（X0<i+1>,X1<j+1>,X2<k+1>,…）までの２3個の頂点ごとに、三次元四面体補間法のときの３次元ＬＵＴの分割記憶方法を適用すればよい。前記２3個の頂点は２N-3組あり、１つの組が２2個のサブメモリに分割記憶されるので、多次元ＬＵＴは全部で２N-1個のサブメモリに分割記憶されることとなる。このように常に２2個のサブメモリを単位としてサブメモリ数が増加していく。以後、増加の単位をクラスタリング単位と呼び、この単位の数だけサブメモリが集まったものをクラスタ・サブメモリと呼び、前記２N-3組をクラスタ数と呼ぶことにする。
【００４１】
図５に５、６、７及びＮ次元の場合の基準点から対角点までの単位立体の各頂点を次元マンハッタン距離Ｄｍを用いて分類した図を示す。ここで図４の領域400及び401つまりクラスタ・サブメモリを500の単位矩形で表ししている。また、クラスタ・サブメモリ500には、Dm = 0, 1, 2, 3におけるそれぞれの頂点の数1, 3, 3, 1を表記してある。５次元の場合は、Dm=0〜5に対して、頂点がそれぞれ5C0, 5C1, 5C2, 5C3, 5C4, 5C5個必要であるため、図に示すように４つのクラスタ・サブメモリを各Dmにおけるサブメモリ上の頂点の数の和が、所望の頂点の数になるようにマッピングすることにより、各Dmにおける所望の数の頂点の参照値をメモリに格納することが可能となる。６次元の場合は、Dm=0〜６に対して、頂点がそれぞれ6C0, 6C1, 6C2, 6C3, 6C4, 6C5, 6C6個必要であるため、図に示すように8つのクラスタ・サブメモリを各Dmにおけるサブメモリ上の頂点の数の和が、所望の頂点の数になるようにマッピングすることにより、各Dmにおける所望の数の頂点の参照値をメモリに格納することが可能となる。7次元の場合は、Dm=0〜7に対して、頂点がそれぞれ7C0, 7C1, 7C2, 7C3, 7C4, 7C5, 7C6, 7C7個必要であるため、図に示すように16個のクラスタ・サブメモリを各Dmにおけるサブメモリ上の頂点の数の和が、所望の頂点の数になるようにマッピングすることにより、各Dmにおける所望の数の頂点の参照値をメモリに格納することが可能となる。
【００４２】
同様に、N次元の場合は、Dm=0〜Nに対して、頂点がそれぞれNC0, NC1, NC2, NC3,... NCN-3, NCN-2, NCN-1, NCN個必要であるため、図に示すようにN-3C0+ N-3C1+ N-3C2+ N-3C3+ N-3C4+...+ N-3CN-3=S個のクラスタ・サブメモリを各Dmにおけるサブメモリ上の頂点の数の和が、所望の頂点の数になるようにマッピングすることにより、各Dmにおける所望の数の頂点の参照値をメモリに格納することが可能となる。
【００４３】
以上説明したように、N次元の場合においても、多次元ＬＵＴ２６０の参照値を重複することなく、クラスタ・サブメモリ単位（２のべき乗容量単位）に分割可能である。
【００４４】
ここで、任意のDm上の頂点の参照値が格納されているサブメモリに関しては、アクセスが競合することなく、いずれか一つのサブメモリが選択され、参照値が読み出されるため、一つのメモリに纏めることが可能である。図５の500〜514は全体のメモリの個数が２のべき乗個になるように２のべき乗単位でクラスタ・サブメモリを纏めた例である。以下、複数個のクラスタ・サブメモリを纏めたものを'拡張クラスタ・サブメモリ'と呼び、拡張クラスタ・サブメモリを構成する４個のメモリを'拡張サブメモリ'と呼ぶこととする。このようにして拡張サブメモリの個数を２にべき乗個を保ちながら、メモリ数を削減することにより、アドレス生成の容易性を保ちながら、メモリ制御回路の数を減らすことによる回路規模の削減が可能となる。
【００４５】
次に、図６を用いて5次元の場合に関して、参照値読み出し部２５０と多次元ＬＵＴ２６０を詳細説明する。600と602の点線で囲まれた部分は、図２の260と同等な多次元LUTであり、603の点線で囲まれた部分は図２の250と同等な参照値読み出し部である。ここで、600及び602はそれぞれ図５の500及び502に相当するのクラスタ・サブメモリであり、601は図５の501に相当する、拡張クラスタ・サブメモリであり、サブメモリの２倍の容量のメモリ４つで構成されている。
【００４６】
604はアドレス生成回路であり、605〜609は、図２の212に相当する5個のデジタル画像信号の上位ビット信号Sh0[x-1:0],  Sh1[x-1:0],  Sh2[x-1:0], Sh3[x-1:0], Sh4[x-1:0]であり、610は図２の232と同等な順序信号である。ここで、xは前述のビット数を示している。611は5次元補間の基準点,  頂点1, 頂点2, 頂点3, 頂点4, 対角点のそれぞれの参照値をメモリから読み出すためのアドレス信号MA0, MA1, MA2, MA3, MA4, MA5を束ねて表したバス信号であり、612は、アドレス信号MA0, MA1, MA2, MA3, MA4, MA5それぞれに対応するサブメモリ・バンク選択信号SEL0[3:0], SEL1[3:0], SEL2[3:0], SEL3[3:0], SEL4[3:0], SEL5[3:0]を束ねて表したバス信号である。645〜648及び653〜656はサブメモリであり、648〜652はサブメモリの２倍の容量をもつ拡張サブメモリである。613〜616及び、621〜624はそれぞれ、サブメモリ645〜648及び653〜656のアドレス選択回路である。また、617〜620はそれぞれ、拡張サブメモリ649〜652のアドレス選択回路である。625は拡張サブメモリ649〜652の通常のサブメモリの2倍の容量にあわせて、アドレス信号MA0, MA1, MA2, MA3, MA4, MA5をそれぞれ１ビット拡張するためのアドレス拡張回路であり、拡張後のアドレス信号MA0', MA1',MA2', MA3', MA4', MA5'を束ねてバス信号626として出力する。633〜636及び641〜644はそれぞれ、アドレス選択回路613〜616及び621〜624から出力されたアドレス信号であり、それぞれサブメモリ645〜648及び653〜656に供給される。63７〜640はそれぞれ、アドレス選択回路617〜620から出力されたアドレス信号であり、それぞれ拡張サブメモリ649〜652に供給される。また、657〜660及び665〜668はそれぞれサブメモリ645〜648及び653〜656からの出力データ信号であり、669は出力データ657〜660及び665〜668を束ねて表したバス信号であり、661〜664はそれぞれ拡張サブメモリ649〜652からの出力データ信号であり、670は出力データ649〜652を束ねて表したバス信号である。671はバス信号669及び670を束ねて表したバス信号であり、672〜677はそれぞれデータ選択回路0〜5であり、678〜683は図2の252と同等な参照信号であり、それぞれ、5次元補間の基準点,  頂点1, 頂点２, 頂点3, 頂点4, 対角点の参照値を示す。
【００４７】
次に、図6の動作を説明する。アドレス生成回路604が5個の信号Sh0[x-1:0],  Sh1[x-1:0],  Sh2[x-1:0], Sh3[x-1:0], Sh4[x-1:0]を受けて、6本のアドレス信号MA0, MA1, MA2, MA3, MA4, MA5をバス信号611に束ねて出力し、また、6本のサブメモリ・バンク選択信号SEL0[3:0], SEL1[3:0], SEL2[3:0], SEL3[3:0] , SEL4[3:0] , SEL5[3:0]をバス信号612に束ねて出力する。ここで、6本のサブメモリ・バンク選択信号は、各々が異なる値である。また、サブメモリ645〜648とアドレス選択回路613〜616、拡張サブメモリ649〜652とアドレス選択回路617〜620、サブメモリ653〜656とアドレス選択回路621〜624はそれぞれ、３次元の場合と同等であるため、サブメモリ・バンク選択信号の下位２ビットは、３次元の場合と同等に生成し、上位２ビットで、２つクラスタ・サブメモリと１つの拡張クラスタ・サブメモリを切り替える。
【００４８】
そして、アドレスのバス信号611及びサブメモリ・バンク選択信号のバス信号612がアドレス選択回路613〜616及び621〜624とアドレス拡張回路625に入力される。また、バス信号612はアドレス選択回路617〜620にも直接入力される。アドレス拡張回路625においては、下記に示す数４にしたがって、拡張後のアドレス信号MA0', MA1',MA2', MA3', MA4', MA5'を生成し、バス信号626としてアドレス選択回路617〜620に出力する。
【００４９】
【数４】
2010103912.tif 000006
また、各アドレス選択回路は各々が異なるサブメモリ・バンクＩＤ “ＳｍＢ_ID"を有しており、図６の例ではアドレス選択回路613〜616及び621〜624に対してはそれぞれSmB_ID=0000〜0011及び1100〜1111のサブメモリ・バンクIDが付加されている。アドレス選択回路617に対してはSmB_ID=0100及び1000、アドレス選択回路618に対してはSmB_ID=0101及び1001、アドレス選択回路619に対してはSmB_ID=0110及び1010、アドレス選択回路620に対してはSmB_ID=0111及び1011のそれぞれ２つのサブメモリ・バンクIDが付加されている。そして、各アドレス選択回路は自らが対応するサブメモリ・バンクＩＤ “ＳｍＢ_ID"と入力されたサブメモリ・バンク選択信号が等しいアドレス信号を６本の中から１つ選択して出力し、サブメモリにアクセスする。サブメモリ645〜648及び653〜656はそれぞれ受け取ったアドレス信号633〜636及び641〜644のアドレス値のデータをそれぞれ出力データ信号657〜660及び665〜668に出力し、出力データのバス信号669及び671を介して全てのデータ選択回路に供給する。また、拡張サブメモリ649〜652はそれぞれ受け取ったアドレス信号637〜640のアドレス値のデータをそれぞれ出力データ信号661〜664に出力し、出力データのバス信号670及び671を介して全てのデータ選択回路に供給する。
【００５０】
その後、データ選択回路0〜5において、それぞれ入力されているサブメモリ・バンク選択信号SEL0〜SEL5を受け取り、サブメモリ・バンク選択信号と値の等しいサブメモリ・バンクIDのメモリから出力されたデータ出力信号を選択して、参照信号678〜683にそれぞれ出力する。
【００５１】
尚、アドレス信号MA0, MA1, MA2, MA3, MA4, MA5は、アドレス生成回路604において、図３の302と同様に順序信号610の値に応じて、上位ビット信号Sh0[x-1:0], Sh1[x-1:2], Sh2[x-1:0], Sh3[x-1:1], Sh4[x-1:1]に対して、所望の軸に+1し、MSB側からSh4, Sh3, Sh2, Sh1, Sh0の順に連結することにより生成される。ここで、Sh1[1:0]は上記１つのクラスタ・サブメモリ又は拡張クラスタ・サブメモリが４つのメモリに分割されているため省略されている。また、Sh3[0]及びSh4[0]はサブメモリ・バンク選択信号の上位２ビットに用いられるため省略されている。さらに、サブメモリ・バンク選択信号SEL1[3:0], SEL2[3:0], SEL3[3:0] , SEL4[3:0] , SEL5[3:0]の生成は、前述のように下位2ビットは３次元の場合と同一であり、上位２ビットは、Sh4[0]&Sh3[0] (&はビット連結)より求められる。
【００５２】
以上説明したように、図５の501のように 2つのクラスタ・サブメモリを纏めて、図６の拡張クラスタ・サブメモリ601を構成することにより、本来必要であった、8つのアドレス選択回路を、図6の617〜620の４つに削減することが可能となり、アドレス生成の容易性と回路規模の削減の両立が可能となる。図５に示したように、この削減の効果は、５次元以上の場合において有効である。
【実施例２】
【００５３】
図７に、６,７及びＮ次元の場合の基準点から対角点までの単位立体の各頂点を次元マンハッタン距離Ｄｍを用いて分類した図を示す。図５と同等な部分に関しては説明を省略する。700〜714の太枠は全体のメモリ個数が最小になるように、クラスタ・サブメモリの整数倍で分割した拡張クラスタ・サブメモリであり、図５でのメモリの数より小さくなっている。但し、拡張クラスタ・サブメモリ701及び702においては、纏められるクラスタ・サブメモリの数が3つであり、サブメモリ数が２のべき乗にならない。また、拡張クラスタ・サブメモリ706においては、纏められるクラスタ・サブメモリの数が6個であるため、同様にサブメモリ数が２のべき乗にならない。これら、サブメモリの数が２のべき乗にならない拡張クラスタ・サブメモリに関しては、拡張クラスタ・サブメモリ701,702に関しては、メモリデータのワード幅を３倍にすることにより、拡張サブメモリを形成し、クラスタ・サブメモリと同等な４個のサブメモリで実現可能である。同様に、拡張クラスタ・サブメモリ706に関しては、メモリデータのワード幅を6倍にすることにより、拡張サブメモリを形成し、クラスタ・サブメモリと同等な４個のサブメモリで実現可能である。このようにしてサブメモリのエントリ数（アドレス数）を２のべき乗個を保ちながら、第1の実施例よりサブメモリ数を削減することにより、アドレス生成の容易性を保ちながら、メモリ制御回路の数を減らすことによる回路規模の削減がよりいっそう可能となる。
【００５４】
次に、図８を用いて6次元の場合に関して、参照値読み出し部２５０と多次元ＬＵＴ２６０を詳細説明する。800〜803の点線で囲まれた部分は、図２の260と同等な多次元LUTであり、804の点線で囲まれた部分は図２の250と同等な参照値読み出し部である。ここで、800, 802はそれぞれ図７の700, 703に相当するのクラスタ・サブメモリである。801, 802はそれぞれ図７の701, 702に相当する、拡張クラスタ・サブメモリであり、サブメモリの3倍の容量のメモリ４つで構成されている。
【００５５】
805はアドレス生成回路であり、806〜811は、図２の212に相当する6個のデジタル画像信号の上位ビット信号Sh0[x-1:0],  Sh1[x-1:0],  Sh2[x-1:0], Sh3[x-1:0], Sh4[x-1:0] , Sh5[x-1:0]であり、6812は図２の232と同等な順序信号である。ここで、xは前述のビット数を示している。813は6次元補間の基準点,  頂点1, 頂点2, 頂点3, 頂点4, 頂点5, 対角点のそれぞれの参照値をメモリから読み出すためのアドレス信号MA0, MA1, MA2, MA3, MA4, MA5, MA6を束ねて表したバス信号であり、814は、アドレス信号MA0, MA1,MA2, MA3, MA4, MA5, MA6それぞれに対応するサブメモリ・バンク選択信号SEL0[4:0], SEL1[4:0], SEL2[4:0], SEL3[4:0], SEL4[4:0], SEL5[4:0] , SEL6[4:0]を束ねて表したバス信号である。847〜850及び859〜862はサブメモリであり、851〜858はサブメモリの3倍の容量をもつ拡張サブメモリである。815〜818及び、827〜830はそれぞれ、サブメモリ847〜850及び859〜862のアドレス選択回路である。また、819〜826はそれぞれ、拡張サブメモリ851〜858のアドレス選択回路である。831〜834及び843〜846はそれぞれ、アドレス選択回路815〜818及び827〜830から出力されたアドレス信号であり、それぞれサブメモリ847〜850及び859〜862に供給される。835〜842はそれぞれ、アドレス選択回路819〜826から出力されたアドレス信号であり、それぞれ拡張サブメモリ851〜858に供給される。また、863〜866及び875〜878はそれぞれサブメモリ847〜850及び859〜862からの出力データ信号であり、879は出力データ863〜866及び875〜878を束ねて表したバス信号であり、867〜874はそれぞれ拡張サブメモリ851〜858からの出力データ信号であり、880は出力データ867〜874を束ねて表したバス信号である。881はバス信号879及び880を束ねて表したバス信号であり、882〜888はそれぞれデータ選択回路0〜5であり、889〜895は図2の252と同等な参照信号であり、それぞれ、6次元補間の基準点,  頂点1, 頂点２, 頂点3, 頂点4, 頂点5, 対角点の参照値を示す。
【００５６】
次に、図８の動作を説明する。アドレス生成回路805が6個の信号Sh0[x-1:0],  Sh1[x-1:0],  Sh2[x-1:0], Sh3[x-1:0], Sh4[x-1:0] , Sh5[x-1:0]受けて、7本のアドレス信号MA0, MA1, MA2, MA3, MA4, MA5, MA6をバス信号813に束ねて出力し、また、7本のサブメモリ・バンク選択信号SEL0[4:0], SEL1[4:0], SEL2[4:0], SEL3[4:0] , SEL4[4:0] , SEL5[4:0] , SEL6[4:0]をバス信号814に束ねて出力する。ここで、7本のサブメモリ・バンク選択信号は、アクセスを競合させないように、各々が異なる値である。また、サブメモリ847〜850とアドレス選択回路815〜818、拡張サブメモリ851〜854とアドレス選択回路819〜822、拡張サブメモリ855〜858とアドレス選択回路823〜826、サブメモリ859〜862とアドレス選択回路827〜830はそれぞれ、３次元の場合と同等であるため、サブメモリ・バンク選択信号の下位２ビットは、３次元の場合と同等に生成し、上位3ビットで、2つのクラスタ・サブメモリと2つの拡張クラスタ・サブメモリを切り替える。また、各アドレス選択回路は各々が異なるサブメモリ・バンクＩＤ “ＳｍＢ_ID"を有しており、図8の例ではアドレス選択回路815〜818及び827〜830に対してはそれぞれSmB_ID=00000〜00011及び11100〜11111のサブメモリ・バンクIDが付加されている。アドレス選択回路819に対してはSmB_ID=00100及び01000及び01100、アドレス選択回路820に対してはSmB_ID=00101及び01001及び01101、アドレス選択回路821に対してはSmB_ID=00110及び01010及び01101、アドレス選択回路822に対してはSmB_ID=00111及び01011及び01111のそれぞれ3つのサブメモリ・バンクIDが付加されている。そして、各アドレス選択回路は自らが対応するサブメモリ・バンクＩＤ “ＳｍＢ_ID"と入力されたサブメモリ・バンク選択信号が等しいアドレス信号を7本の中から１つ選択して出力し、サブメモリにアクセスする。サブメモリ847〜850及び859〜862はそれぞれ受け取ったアドレス信号831〜834及び843〜846のアドレス値のデータをそれぞれ出力データ信号863〜866及び875〜878に出力し、出力データのバス信号879及び881を介して全てのデータ選択回路に供給する。また、拡張サブメモリ819〜826はそれぞれ受け取ったアドレス信号835〜842のアドレス値のデータをそれぞれ出力データ信号867〜874に出力し、出力データのバス信号880及び881を介して全てのデータ選択回路に供給する。その後、データ選択回路0〜6において、それぞれ入力されているサブメモリ・バンク選択信号SEL0〜SEL6を受け取り、サブメモリ・バンク選択信号と値の等しいサブメモリ・バンクIDのメモリから出力されたデータ出力信号を選択して、参照信号889〜895にそれぞれ出力する。ここで、データ選択回路においては、サブメモリ・バンク選択信号が00000〜00011又は11100〜11111の場合は、サブメモリ・バンクIDが等しいメモリから出力されたデータ信号を選択する。また、補間に用いる参照値のビット数をyビットとするとデータ出力信号867は3*yビットとなるため、サブメモリ・バンク信号が00100又は01000又は01100の場合は、それぞれデータ出力信号867の下位yビット、中位ｙビット、上位ｙビットが選択されて出力される。同様に、サブメモリ・バンク信号が00101又は01001又は01101の場合は、それぞれデータ出力信号868の下位yビット、中位ｙビット、上位ｙビットが選択されて出力される。同様に、サブメモリ・バンク信号が00110又は01010又は01110の場合は、それぞれデータ出力信号869の下位yビット、中位ｙビ��ト、上位ｙビットが選択されて出力される。同様に、サブメモリ・バンク信号が00111又は01011又は01111の場合は、それぞれデータ出力信号870の下位yビット、中位ｙビット、上位ｙビットが選択されて出力される。同様に、サブメモリ・バンク信号が10000又は10100又は11000の場合は、それぞれデータ出力信号871の下位yビット、中位ｙビット、上位ｙビットが選択されて出力される。同様に、サブメモリ・バンク信号が10001又は10101又は11001の場合は、それぞれデータ出力信号872の下位yビット、中位ｙビット、上位ｙビットが選択されて出力される。同様に、サブメモリ・バンク信号が10010又は10110又は11010の場合は、それぞれデータ出力信号873の下位yビット、中位ｙビット、上位ｙビットが選択されて出力される。同様に、サブメモリ・バンク信号が10011又は10111又は11011の場合は、それぞれデータ出力信号874の下位yビット、中位ｙビット、上位ｙビットが選択されて出力される。
【００５７】
尚、アドレス信号MA0, MA1, MA2, MA3, MA4, MA5, MA6は、アドレス生成回路805において、図３の302と同様に順序信号812の値に応じて、上位ビット信号Sh0[x-1:0], Sh1[x-1:2], Sh2[x-1:0], Sh3[x-1:1], Sh4[x-1:1],  Sh5[x-1:1]に対して、所望の軸に+1し、MSB側からSh5, Sh4, Sh3, Sh2, Sh1, Sh0の順に連結することにより生成される。ここで、Sh1[1:0]は上記１つのクラスタ・サブメモリ又は拡張クラスタ・サブメモリが４つのメモリに分割されているため省略されている。また、Sh3[0]及びSh4[0]及びSh5[0]はサブメモリ・バンク選択信号の上位3ビットに用いられるため省略されている。さらに、サブメモリ・バンク選択信号SEL1[3:0], SEL2[3:0], SEL3[3:0] , SEL4[3:0] , SEL5[3:0], SEL6[3:0]の生成は、前述のように下位2ビットは３次元の場合と同一であり、上位3ビットは、Sh5[0]&Sh4[0]&Sh3[0] (&はビット連結)より求められる。
【００５８】
以上説明したように、図７の701及び702の様に3つのクラスタ・サブメモリを纏めて、図８の拡張クラスタ・サブメモリ801及び802を構成することにより、本来必要であった、18つのアドレス選択回路を、図８の819〜826の8つに削減することが可能となり、アドレス生成の容易性と回路規模の削減の両立が可能となる。図7に示したように、この削減の効果は、6次元以上の場合において有効である。
【００５９】
以上を踏まえ、従来例１、従来例２と本発明の実施例1, 実施例２比較を図９に示す。実施例１、実施例２共に、多次元ＬＵＴを従来例１のサブメモリの個数に対して、少ない個数のサブメモリに分割記憶できる。また従来例２と違い、分割後のサブメモリ１つ当たりに記憶される参照値の数は、実施例１においては常に２の冪乗個となっている。また、実施例２において、拡張サブメモリ一つあたりの参照値の数が、２のべき乗になっていない場合があるが、前述のように、メモリのワード幅を拡張する個により、アドレス数をサブメモリと同等にしているため、アドレス生成はサブメモリの場合と同等に行うことができる。
【００６０】
これまで述べてきたように本発明のＮ次元補間装置は、入力したＮ個の信号値の分割された上位ビット信号すべての組み合わせに対応する参照値を重複することなく２のべき乗個のサブメモリに分割記憶することが可能で、また補間演算に必要なＮ+１個の参照値を同時に読み出すことができるため補間演算を高速化可能で、またサブメモリへのアクセスするためのアドレス生成も割り算器が不要でかつ、前記Ｎ個の信号値の分割された上位ビット信号のビット連結により容易に生成することが可能な多次元データ変換装置である。
【００６１】
［他の実施形態］
前述した実施形態の機能（または機能の一部）を実現するソフトウエアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、本願発明の目的が達成される。
【００６２】
この場合、記憶媒体から読み出されたプログラムコード自体が本願発明の新規な機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本願発明を構成することになる。
【００６３】
プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ，ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。
【００６４】
また、コンピュータが読み出したプログラムコードを実行することによって、前述した実施形態の機能が実現される他、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施形態の機能が実現され得る。
【００６５】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施形態の機能が実現され得る。
【００６６】
なお、本願発明は、前述した実施形態の機能を実現するソフトウエアのプログラムコードを記録した記憶媒体から、そのプログラムを、パソコン通信など通信ラインを介して要求者にそのプログラムを配信する場合にも適用できる。
【図面の簡単な説明】
【００６７】
【図１】カラー複写機の全体構成例を示すブロック図である。
【図２】本実施例の多次元補間装置の回路構成を示すブロック図である。
【図３】本実施例の参照値読み出し部と3次元ＬＵＴの回路構成を示すブロック図である。
【図４】本実施例の四次元超四面体補間における、基準点から対角点までの各単位立体の頂点を四次元マンハッタン距離Ｄｍを用いて分類した図である。
【図５】第1の実施例の5,6,7,N次元超四面体補間における、メモリ分割方法を説明する図である。
【図６】第１の実施例の参照値読み出し部と5次元ＬＵＴの回路構成を示すブロック図である。
【図７】第２の実施例の5,6,7,N次元超四面体補間における、メモリ分割方法を説明する図である。
【図８】第２の実施例の参照値読み出し部と６次元ＬＵＴの回路構成を示すブロック図である。
【図９】従来例と本発明を比較する表である。
【図１０】３Ｄ-ＬＵＴを用いて三次元補間演算を行なう場合の機能ブロックである。
【図１１】三次元入力の色空間（ＲＧＢ空間）を各軸方向に限定数で単位立体に分割した状態を示す図である。
【図１２】三次元四面体補間法を説明する図である。
【図１３】従来例１における、３Ｄ-ＬＵＴをサブメモリごとに分割した図である。
【図１４】従来例２における、３Ｄ-ＬＵＴをサブメモリごとに分割した図である。
【図１５】四次元超四面体補間法のための超四面体の稜線選択を説明する図である。
【図１６】従来例２の三次元四面体補間における、基準点から対角点までの各単位立体の頂点を三次元マンハッタン距離Ｄｍを用いて分類した図である。
【図１７】従来例２の四次元超四面体補間における、基準点から対角点までの各単位立体の頂点を四次元マンハッタン距離Ｄｍを用いて分類した図である。
【符号の説明】
【００６８】
２０５  デジタル画像信号
２１０  データ分割部
２１２  データ分割後のデジタル画像信号205の上位ビット
２１４  データ分割後のデジタル画像信号205の下位ビット
２３０  順序判定部
２３２  順序信号
２４０  重み係数算出部
２４２  重み係数信号
２５０  参照点読み出し部
２５２  参照値信号
２５４  アドレス信号
２６０  多次元LUT
２７０  補間演算部
２７５  出力信号
【図１】
2010103912.tif 000007
【図２】
2010103912.tif 000008
【図３】
2010103912.tif 000009
【図４】
2010103912.tif 000010
【図５】
2010103912.tif 000011
【図６】
2010103912.tif 000012
【図７】
2010103912.tif 000013
【図８】
2010103912.tif 000014
【図９】
2010103912.tif 000015
【図１０】
2010103912.tif 000016
【図１１】
2010103912.tif 000017
【図１２】
2010103912.tif 000018
【図１３】
2010103912.tif 000019
【図１４】
2010103912.tif 000020
【図１５】
2010103912.tif 000021
【図１６】
2010103912.tif 000022
【図１７】
2010103912.tif 000023