JP4724413B2 - データ分類方法 - Google Patents

Description

本発明は、データ分類方法に関し、特に、Ｎ次元ベクトル信号を補間するために用いて好適なものである。

近年、入力機器としては、スキャナ、ビデオカメラなどが普及している。一方、出力機器としては、インクジェット、染料熱昇華型あるいは電子写真などの方式を用いた、各種カラープリンタが普及している。これらのカラー入力機器及び出力機器は、それぞれ固有の色空間を有しており、例えばあるスキャナで得たカラー画像をそのまま別のカラープリンタに転送して印刷した場合、印刷されたカラー画像の色がスキャナによって読み取られたオリジナルのカラー画像の色と一致することはほとんどない。

このようなカラー画像等に対するデバイス間での色再現性の問題を解決するためには、入力機器の色空間を出力機器の色空間に変換する処理（"色空間変換"と呼ぶ）が必要となり、入力機器及び出力機器の色彩再現性能を高めるために、色空間変換機能が入力機器及び出力機器に搭載されている。

ここで色空間変換とは、具体的には入力γ補正，輝度濃度変換，マスキング，黒生成，ＵＣＲ，出力γ補正等の一連の画像処理全体、もしくはその中の一定の処理を指す。一般的には、入力機器の３色（例えば、レッド，ブルー，グリーンの３色、以下、"ＲＧＢ"と略称する）のデジタル画像信号を同時に参照して、出力機器の３色（例えば、シアン，マゼンタ，イエローの３色、以下、"ＣＭＹ"と略称する）あるいは４色（例えば、シアン，マゼンタ，イエロー，ブラックの４色、以下、"ＣＭＹＫ"と略称する）のデジタル画像信号に変換することが多い。また電子写真方式の複写機の場合、稼働時間とともにプリンタのエンジン特性が変化するため、定期的なキャリブレーションが必要となる。このような場合は、入力機器の４色（例えば、"ＣＭＹＫ"）から出力機器の４色（例えば、"ＣＭＹＫ"）への変換も必要となる。

以上のような色空間変換方法を実現するための第１の従来技術として、色変換の結果が記憶された３Ｄ-ＬＵＴ（３次元ルックアップ・テーブル）を８個のメモリに分けて記憶し、この３Ｄ-ＬＵＴから参照値を並列に読み出すことで、三次元立方体[トライリニア]補間法や三次元四面体補間法を高速に実行する技術が開示されている（特許文献１を参照）。

かかる技術では、補間に使用する単位超立体の各頂点に対応する参照値がすべて異なるメモリに記憶されるようにすることで、メモリから参照値を読み出すときにアクセスが競合することはなくなるようにしている。また、３Ｄ−ＬＵＴを重複することなく均等に８個のメモリに分割して記憶している（以後、多次元ＬＵＴから参照値を並列に読み出すために多次元ＬＵＴを複数のメモリに分割して記憶した場合、それら複数のメモリをそれぞれ"サブメモリ"と呼ぶことにする）。なお、第１の従来技術では、三次元補間法に限定した記載しかなされていないが、第１の従来技術を用いて多次元補間演算を行なう場合には、多次元ＬＵＴを２^N個のサブメモリに分割して記憶すればよいことになる。

また、３Ｄ-ＬＵＴを重複することなく４つのサブメモリに分割して記憶し、参照値を並列に読み出すことで三次元四面体補間法を高速に実行する第２の従来技術が開示されている（特許文献２を参照）。
かかる技術では、三次元四面体補間法の場合、選択された四面体の頂点に対応する４つの参照値を並列に読み出して、補間演算を高速化できるようにしている。また、第２の従来技術においても、前述した第１の従来技術と同様に、３Ｄ-ＬＵＴを重複することなく均等に４個のサブメモリに分割して記憶しており、各サブメモリから参照値を読み出すときにアクセスが競合することはない。
さらに、第２の従来技術におけるＬＵＴを多次元化して分割している。したがって、Ｎ次元入力の超四面体（Ｎ＋１面体）補間法を行なう場合、多次元（Ｎ次元）ＬＵＴを（Ｎ＋１）個のサブメモリに分割して記憶できる。
このように、第２の従来技術は、使用するサブメモリの個数が少ないという点で、前述した第１の従来技術よりは優位である。

米国特許４８３７７２２号明細書 特開平１０-３０７９１１号公報

前述した第１の従来技術では、単位超立体の頂点に対応するＮ個の参照値をそれぞれ独立したＮ個のサブメモリに記憶し、多次元ＬＵＴを２^N個に分割している。そのため、多次元四面体補間法以外の補間法（例えば、多次元立体[トライリニア]補間法、多次元三角柱［プリズム］補間法など）を用いても実現することが可能であるという利点を持っている。
しかしながら、多次元四面体補間法を採用することが前提になっている場合、補間演算に必要な（Ｎ＋１）個の参照値をサブメモリから並列に読み出すために、メモリインターフェースなどのメモリ周辺回路を２^N個持つ必要があり、余剰回路が多くなるという問題がある。

また、前述した第２の従来技術では、多次元四面体補間法のみに限定することで、多次元（Ｎ次元）ＬＵＴを最小限の個数（（Ｎ＋１）個）のサブメモリに分割して記憶している。そのため、メモリ周辺回路も最適な規模であるという利点を持っている。
しかしながら、Ｎが（２の冪乗−１）でないときには、サブメモリの個数も２の冪乗にならない。例えば、Ｎが４の場合には、サブメモリの個数は５個となる。そして、第２の従来技術をハードウェア化する場合には、２進法で取り扱うことができない。そのため、Ｎが（２の冪乗−１）でないときには、サブメモリをアクセスするためのアドレスを生成するときに割り算器が必要となり、シフト演算やビットマスクだけでアドレス生成できないという問題が生じる。また、一般的にメモリは、２の冪乗のワード数で製品化されているため、市場に流通しているメモリを利用してサブメモリを構成する場合、第２の従来技術ではワード数が余剰なメモリを採用しなければならないという問題が生じる。

本発明は、以上のような問題に鑑みてなされたものであり、色空間の変換などにおいて行われる単位超立方体の頂点の分類を高速に行なえるようにすることが、小さな回路規模で実現できるようにすることを目的とする。

本発明のデータ分類方法は、Ｎ次元直交座標（Ｎは４以上の整数）上の各単位超立体の頂点に対応するデータを格納した（Ｍ＋１）×２ ^(N-M) 個のサブメモリ（ＭはＮより小さい整数）のいずれかから前記対応するデータを読み出すために、前記Ｎ次元直交座標上の各単位超立体の頂点を（Ｍ＋１）×２^(N-M)通りのいずれかに分類する方法であって、それぞれが複数のビットで表わされるＮ個の成分からなる頂点の座標値のうちのＭ個の成分を選択する選択工程と、前記選択工程により選択されたＭ個の成分の総和を算出する第１の算出工程と、前記第１の算出工程により算出された総和を、（Ｍ＋１）で割った余りを算出する第２の算出工程と、前記選択工程により選択されなかった（Ｎ−Ｍ）個の成分のそれぞれの所定のビット位置の値によりなる整数を（Ｍ＋１）倍した結果を、前記第２の算出工程により算出された余りに加算して、前記頂点を（Ｍ＋１）×２^(N-M)個のグループのいずれかに分類するための指標値を算出する第３の算出工程と、前記第３の算出工程により算出された指標値が示すグループに前記頂点を分類する分類工程とを有することを特徴とする。
また、本発明の他の態様例では、Ｎ次元直交座標（Ｎは４以上の整数）上の各単位超立体の頂点に対応するデータを格納した（Ｍ＋１）×２ ^(N-M) 個のサブメモリ（ＭはＮより小さい整数）のいずれかから前記対応するデータを読み出すために、前記Ｎ次元直交座標上の各単位超立体の頂点を（Ｍ＋１）×２^(N-M)通りのいずれかに分類する方法であって、それぞれがＮ個の成分からなる頂点の座標値のうちのＭ個の成分を選択する選択工程と、前記選択工程により選択されたＭ個の成分の総和を算出する第１の算出工程と、前記第１の算出工程により算出された総和を、（Ｍ＋１）で割った余りを算出する第２の算出工程と、前記選択工程により選択されなかった（Ｎ−Ｍ）個の成分のそれぞれが奇数か偶数かを示す値によりなる整数を（Ｍ＋１）倍した結果を、前記第２の算出工程により算出された余りに加算して、前記頂点を（Ｍ＋１）×２^(N-M)個のグループのいずれかに分類するための指標値を算出する第３の算出工程と、前記第３の算出工程により算出された指標値が示すグループに、前記頂点を分類する分類工程とを有することを特徴とする。
また、本発明のその他の態様例では、Ｎ次元直交座標（Ｎは４以上の整数）上の各単位超立体の頂点に対応するデータを格納した（Ｍ＋１）×２ ^(N-M) 個のサブメモリ（ＭはＮより小さい整数）のいずれかから前記対応するデータを読み出すために、前記Ｎ次元直交座標上の各単位超立体の頂点を（Ｍ＋１）×２^(N-M)通りのいずれかに分類する方法であって、それぞれが複数のビットで表わされるＮ個の成分からなる頂点の座標値のうちのＭ個の成分を選択する選択工程と、前記選択工程により選択されたＭ個の成分の総和と、前記選択工程により選択されなかった（Ｎ−Ｍ）個の成分のそれぞれの所定のビット位置の値によりなる整数を（Ｍ＋１）倍した結果とを加算する第１の算出工程と、前記第１の算出工程による加算の結果を、（Ｍ＋１）×２^(M-N)で割った余りを算出する第２の算出工程と、前記第２の算出工程により算出された余りを、前記頂点を（Ｍ＋１）×２^(N-M)個のグループのいずれかに分類するための指標値として用いて、前記頂点を前記指標値が示すグループに分類する分類工程とを有することを特徴とする。
また、本発明のその他の態様例では、Ｎ次元直交座標（Ｎは４以上の整数）上の各単位超立体の頂点に対応するデータを格納した（Ｍ＋１）×２ ^(N-M) 個のサブメモリ（ＭはＮより小さい整数）のいずれかから前記対応するデータを読み出すために、前記Ｎ次元直交座標上の各単位超立体の頂点を（Ｍ＋１）×２^(N-M)通りのいずれかに分類する方法であって、それぞれがＮ個の成分からなる頂点の座標値のうちのＭ個の成分を選択する選択工程と、前記選択工程により選択されたＭ個の成分の総和と、前記選択工程により選択されなかった（Ｎ−Ｍ）個の成分のそれぞれが奇数か偶数かを示す値によりなる整数を（Ｍ＋１）倍した結果とを加算する第１の算出工程と、前記第１の算出工程による加算の結果を、（Ｍ＋１）×２^(M-N)で割った余りを算出する第２の算出工程と、前記第２の算出工程により算出された余りを、前記頂点を（Ｍ＋１）×２^(N-M)個のグループのいずれかに分類するための指標値として用いて、前記頂点を前記指標値が示すグループに分類する分類工程とを有することを特徴とする。

本発明によれば、Ｎ次元超四面体（Ｎ+１面体）上の単位超立方体の頂点の分類を高速に行なえるようにすることが、小さな回路規模で実現できる。

以下に説明する本発明の実施形態では、色空間の変換を実現する方法として、色空間を変換した結果をルックアップ・テーブル（ＬＵＴ）としてメモリに予め記憶しておき、入力されたデジタル画像信号に対して、そのＬＵＴを用いて色空間を変換し、その変換結果を出力する。

そして、このＬＵＴを用いた色空間の変換方法において、ＬＵＴのメモリを削減するため補間演算を併用する。３色入力のデジタル画像信号に対する色空間変換は、三次元補間演算を用いて実現される。また、４色入力のデジタル画像信号に対する色空間変換は、四次元補間演算を用いて実現される。

そこで、まず、３色入力のデジタル画像信号に対して、三次元ルックアップ・テーブル（３Ｄ−ＬＵＴ）と、三次元補間演算とを併用した色空間変換方法について説明する。
入力デジタル画像信号（Ｒ、Ｇ、Ｂ）は、上位ビットと下位ビットとに分離される。上位ビットは、３Ｄ−ＬＵＴを用いて行なう補間演算に必要な複数の参照値を取り出すときに使用される。また、下位ビットは、重み係数ｇとして補間演算に使用される。そして、重み係数ｇと３Ｄ−ＬＵＴから取り出された参照値との積和演算により補間値を計算する。

図１３は、三次元入力の色空間（ＲＧＢ空間）を、各軸方向に限定数で分割することで、単位立体に分割した状態を示している。この単位立体の頂点における色空間変換後の色データが、参照値として３Ｄ−ＬＵＴに記憶されている。３つのデジタル画像信号の上位ビットを色空間の座標と考え、補間演算に使用する単位立体を選択し（例えば、図１３に示す単位立体１３０１）、単位立体の頂点に対応する参照値を補間演算に使用する。

このときに使用される三次元補間演算の方法として四面体補間法がある。
この補間法は、図１４（ｂ）〜（ｇ）に示すように、単位立体（例えば、図１３に示す単位立体１３０１）を６つの四面体に分割して（以下、分割した６つの四面体をそれぞれType０〜Type５と称する）、入力座標がどの四面体に属するかによって、以下の（１式）〜（６式）を用いて補間演算する。なお、以下の（１式）〜（６式）では、図１４（ａ）に示す単位立体の頂点に対応する参照値を、それぞれＰ０〜Ｐ７とし、重み係数ｇをΔＲ、ΔＧ、ΔＢとしている。また、Type０からType５の四面体のうち、どの四面体を選択するかは、これら重み係数ΔＲ、ΔＧ、ΔＢの大小関係により決定される。

Type０のとき（ΔＲ＞ΔＧ＞ΔＢ）
Ｘ＝Ｐ０＋（Ｐ１−Ｐ０）×ΔＲ＋（Ｐ３−Ｐ０）×ΔＧ＋（Ｐ７−Ｐ０）×ΔＢ ・・・（１式）
Type１のとき（ΔＲ＞ΔＢ＞ΔＧ）
Ｘ＝Ｐ０＋（Ｐ１−Ｐ０）×ΔＲ＋（Ｐ７−Ｐ０）×ΔＧ＋（Ｐ５−Ｐ０）×ΔＢ ・・・（２式）
Type２のとき（ΔＧ＞ΔＲ＞ΔＢ）
Ｘ＝Ｐ０＋（Ｐ３−Ｐ０）×ΔＲ＋（Ｐ２−Ｐ０）×ΔＧ＋（Ｐ７−Ｐ０）×ΔＢ ・・・（３式）
Type３のとき（ΔＧ＞ΔＢ＞ΔＲ）
Ｘ＝Ｐ０＋（Ｐ７−Ｐ０）×ΔＲ＋（Ｐ２−Ｐ０）×ΔＧ＋（Ｐ６−Ｐ０）×ΔＢ ・・・（４式）
Type４のとき（ΔＢ＞ΔＲ＞ΔＧ）
Ｘ＝Ｐ０＋（Ｐ５−Ｐ０）×ΔＲ＋（Ｐ７−Ｐ０）×ΔＧ＋（Ｐ４−Ｐ０）×ΔＢ ・・・（５式）
Type５のとき（ΔＢ＞ΔＧ＞ΔＲ）
Ｘ＝Ｐ０＋（Ｐ７−Ｐ０）×ΔＲ＋（Ｐ６−Ｐ０）×ΔＧ＋（Ｐ４−Ｐ０）×ΔＢ ・・・（６式）

また、これまで説明した三次元四面体補間法を多次元化することも可能である。以下に、多次元超四面体補間法について説明する。
図１３に示す三次元直交座標に固定された空間を多次元化して、Ｎ次元直交座標に固定された空間にした場合、図１３に示す単位立体は、多次元の単位超立体（Ｎ次元超立体、もしくは超六面体と呼ぶ）に多次元化される。そして、三次元四面体補間法で使用された四面体は、この多次元化により超四面体と呼ばれる（Ｎ＋１）面体に多次元化される。

この超四面体は、単位超立体の基準点と対角点とを結ぶ線と、超立体の互いに直交し、且つ連結しているＮ本の稜線とによって形成される。そして、１つの単位超立体を分割してＮ！個の超四面体を作ることができる。単位超立体から超四面体を切り出す過程で選択したＮ本の稜線は、互いに垂直であり、且つＮ次元直交座標の各軸方向にそれぞれ平行である。このため、各軸方向の出力変移量の線形和を基準点出力値に加算した値が多次元補間演算の出力となる。したがって、選択された稜線の両端点における参照値の差分値に、各稜線上での基準点からの距離を乗算して、それら乗算値を基準点の参照値に累積加算することで補間演算を行なえる。

次に、四次元空間（X₀,X₁,X₂,X₃）を例に挙げて、四次元超四面体補間法のおける稜線の選択方法を説明する。図１５は、入力座標を（X₀<i>+ΔX₀,X₁<j>+ΔX₁,X₂<k>+ΔX₂,X₃<l>+ΔX₃）とし、この入力座標と基準点座標（X₀<i>,X₁<j>,X₂<k>,X₃<l>）との差（ΔX₀,ΔX₁,ΔX₂,ΔX₃）の大小関係が、｛ΔX₀>ΔX₁>ΔX₂>ΔX₃｝の場合において、稜線を選択する方法を示している。

まず、図１５（ｂ）に示すように、入力座標と基準点座標との変移量が最も大きいΔX₀に対応するX₀軸と平行で、且つ基準点を端点にもつ稜線、つまり点（X₀<i>,X₁<j>,X₂<k>,X₃<l>）と点（X₀<i+1>,X₁<j>,X₂<k>,X₃<l>）とを両端点に持つ稜線が選択される。
次に、図１５（ｃ）に示すように、入力座標と基準点座標との変移量が２番目に大きいΔX₁に対応するX₁軸と平行で、且つ点（X₀<i+1>,X₁<j>,X₂<k>,X₃<l>）を端点にもつ稜線、つまり、点（X₀<i+1>,X₁<j>,X₂<k>,X₃<l>）と点（X₀<i+1>,X₁<j+1>,X₂<k>,X₃<l>）とを両端点に持つ稜線が選択される。

次に、図１５（ｄ）に示すように、入力座標と基準点座標との変移量が３番目に大きいΔX₂に対応するX₂軸と平行で、且つ点（X₀<i+1>,X₁<j+1>,X₂<k>,X₃<l>）を端点にもつ稜線、つまり、点（X₀<i+1>,X₁<j+1>,X₂<k>,X₃<l>）と点（X₀<i+1>,X₁<j+1>,X₂<k+1>,X₃<l>）とを両端点に持つ稜線が選択される。
最後に、図１５（ｅ）に示すように、入力座標と基準点座標との変移量が最も小さいΔX₃に対応するX₃軸と平行で、且つ点（X₀<i+1>,X₁<j+1>,X₂<k+1>,X₃<l>）を端点にもつ稜線、つまり、点（X₀<i+1>,X₁<j+1>,X₂<k+1>,X₃<l>）と点（X₀<i+1>,X₁<j+1>,X₂<k+1>,X₃<l+1>）とを両端点に持つ稜線が選択される。

最終的に、点（X₀<i>,X₁<j>,X₂<k>,X₃<l>）、（X₀<i+1>,X₁<j>,X₂<k>,X₃<l>）、（X₀<i+1>,X₁<j+1>,X₂<k>, X₃<l>）、（X₀<i+1>,X₁<j+1>,X₂<k+1>,X₃<l>）、（X₀<i+1>,X₁<j+1>,X₂<k+1>,X₃<l+1>）の５つの頂点で構成される超四面体（５面体）が決定される。このとき、基準点（X₀<i>,X₁<j>,X₂<k>,X₃<l>）から最も遠い点（X₀<i+1>,X₁<j+1>,X₂<k+1>,X₃<l+1>）を対角点と呼び、基準点と対角点とを結ぶ線を対角線と呼ぶことにする。

多次元超四面体補間法は、基準点と対角点とが、入力座標と基準点座標との差（ΔX₀,ΔX₁,ΔX₂,ΔX₃）の大小関係にかかわらず、必ず超四面体の頂点として選択されるという特徴を持つ。そこで、単位超立体から入力座標に対応する超四面体を選択する工程は、基準点をスタート、対角点をゴール、各稜線をスタートからゴールまでの経路と見立てれば、基準点から対角点までの経路を選択する経路選択問題と考えることができる。
この場合、経路の採り得る"場合の数"は、２４（＝４！＝４×３×２×１）通りになり、四次元補間演算では単位超立体を２４個の超四面体に分割できることが分かる。同様に、Ｎ次元補間演算の場合、単位超立体をＮ！個の超四面体に分割できることが分かる。

次に、Ｎ次元補間演算について説明する。Ｎ次元直交座標に固定された空間（X₀,X₁,・・・,X_N-1）上の座標（X₀<i>,X₁<j>,X₂<k>,…X_N-2<a>,X_N-1<b>）の参照値を、Ｐ<i,j,k,…,a,b>とする。また、ある入力座標によって選択された超立体の基準点の座標を（X₀<i>,X₁<j>,X₂<k>,…X_N-2<a>,X_N-1<b>）とし、入力座標と基準点座標との差を（ΔX₀,ΔX₁,ΔX₂,…,ΔX_N-2,ΔX_N-1）とする。そして、｛ΔX₀>ΔX₁>ΔX₂>…>ΔX_N-2>ΔX_N-1｝の関係が成り立つ場合、以下の（７式）を用いて補間値Ｘを求めることができる。

（第１の実施形態）
次に、本発明の第１の実施形態について説明する。
図１に、カラー複写機の全体構成の一例を示す。
図１において、画像読み取り部１２０は、レンズ１２２、ＣＣＤセンサ１２４、及びアナログ信号処理部１２６等を備えて構成される。レンズ１２２を介しＣＣＤセンサ１２４に結像された原稿１００の画像が、ＣＣＤセンサ１２４によりＲ（Red），Ｇ（Green），Ｂ （Blue）のアナログ電気信号に変換される。

アナログ信号に変換された画像情報は、アナログ信号処理部１２６に入力され、Ｒ，Ｇ，Ｂの各色毎に補正等が行われた後にアナログ・デジタル変換（Ａ／Ｄ変換）される。デジタル化されたフルカラー信号（以下、デジタル画像信号という）は、画像処理部１３０に入力される。画像処理部１３０は、デジタル画像信号に対し、入力γ補正、色空間変換、濃度補正、及びスクリーン処理を施し、これらの処理が施された後のデジタル画像信号をプリンタ部１４０へ出力する。

プリンタ部１４０は、例えば、レーザ等からなる露光制御部（図示せず）、画像形成部（図示せず）、及び転写紙の搬送制御部（図示せず）等により構成され、入力されたデジタル画像信号により転写紙上に画像を記録する。
また、ＣＰＵ回路部１１０は、演算制御用のＣＰＵ１１２、固定データやプログラムを格納するＲＯＭ１１４、データの一時保存やプログラムのロードに使用されるＲＡＭ１１６、及び外部記憶装置１１８等を備えて構成され、画像読み取り部１２０、画像処理部１３０、及びプリンタ部１４０等を制御し、カラー複写機のシーケンスを統括的に制御する。外部記憶装置１１８は、カラー複写機が使用するパラメータやプログラムを記憶するディスク等の媒体であり、ＲＡＭ１１６のデータやプログラム等は、外部記憶装置１１８からロードされる構成としても構わない。

本実施形態の多次元補間装置は、例えば画像処理部１３０で行なわれる色空間変換を実現している。なお、本発明は、図１に示したようなカラー複写機に限定されるものではなく、プリンタやＰＣ（パーソナルコンピュータ）に実施することもできる。以下、図２を用いて、本実施形態の多次元補間装置の回路構成と処理の流れについて詳しく説明する。
本実施形態の多次元補間装置は、Ｎ次元の入力信号に対し補間演算を行い、新たな信号を出力する。まず、デジタル画像信号２０５が多次元補間装置に入力される。このデジタル画像信号２０５は、Ｎ入力の信号である。デジタル画像信号２０５は、データ分割部２１０で上位ビット信号２１２と下位ビット信号２１４とに分割される。

デジタル画像信号２０５がＮ入力の信号であるため、デジタル画像信号２０５を分割して得られた上位ビット信号２１２と下位ビット信号２１４は、ともにＮ本の信号となる。一般的に、上位ビット信号２１２は、補間演算のときに使用される単位超立体の個数に応じてそのビット深度が決定される。例えば、Ｎ次元空間のある軸について単位超立体が（２^x-１）個ある場合、その軸に対応する上位ビット信号２１２のビット深度はｘビットとなる。また、一般的に、下位ビット信号２１４は、デジタル画像信号２０５のビット深度から上位ビット信号２１２のビット深度を差し引いた、残りのビット深度で表現される。

次に、順序判定部２３０は、Ｎ本の下位ビット信号２１４を受け取り、下位ビット信号２１４の大小関係を判定し、判定した結果を順序信号２３２として出力する。この順序信号２３２は、前述した単位超立体から補間演算に使用する超四面体（Ｎ＋１面体）の稜線を選択する工程に従って予め定められたＮ！通りの稜線選択パターンを指し示す信号である。

参照座標選択部２２０は、順序判定部２３０の判定結果である順序信号２３２に従い、補間演算に必要となる（Ｎ＋１）個の参照値２５２を多次元ＬＵＴ２６０から読み出すための座標を決定し、決定した座標を、(Ｎ＋１)本の参照座標信号２２２として出力する。

また同様に、重み係数算出部２４０は、下位ビット信号２１４をもとに、補間演算の重み係数信号２４２を算出し、補間演算部２７０に出力する。なお、下位ビット信号２１４をもとに、補間演算の重み係数信号２４２を算出する方法としては、例えば、対応表となるテーブルを予めＲＯＭに格納しておき、該当する補間演算の重み係数信号２４２をＲＯＭから読み出すことで、下位ビット信号２１４を補間演算の重み係数信号２４２に変換する方法や、予め定められた計算式により算出する方法などが挙げられる。

また、参照値読み出し部２５０は、（Ｎ＋１）本の参照座標信号２２２を用いて多次元ＬＵＴ２６０から（Ｎ＋１）個の参照値を読み出し、読み出した参照値を参照値信号２５２として出力する。多次元ＬＵＴ２６０は、複数個のサブメモリで実現されている。参照値読み出し部２５０は、サブメモリの個数と等しい数のアドレス信号２５４を各サブメモリに出力して各サブメモリにアクセスし、各サブメモリからデータ信号２６２を受け取る。
補間演算部２７０は、（Ｎ＋１）本の参照値信号２５２と、Ｎ本の補間演算の重み係数信号２４２とを受け、前述した補間演算式に従い補間演算を行い、１本の出力信号２７５を出力する。

次に、Ｎ次元超四面体補間法において、多次元ＬＵＴ２６０の参照値を重複することなく、２^N-1個のサブメモリに分割して記憶する方法の一例について説明する。
図３に、四次元超四面体補間法に従って、基準点から対角点までの単位立体の各頂点を、四次元マンハッタン距離を用いて分類した結果を示す。

ここで、Ｎ次元マンハッタン距離Ｄｍは、Ｎ次元直交座標に固定された空間上の２点Ａ(Ｘ₀<i₁>,Ｘ₁<j₁>,Ｘ₂<k₁>,…,Ｘ_N-2<a₁>,Ｘ_N-1<b₁>)と、Ｂ(Ｘ₀<i₂>,Ｘ₁<j₂>,Ｘ₂<k₂>,…,Ｘ_N-2<a₂>,Ｘ_N-1<b₂>)との距離であり、以下の（８式）で定義されるものである。
Ｄｍ＝｜X₀<i₁>−X₀<i₂>｜＋｜X₁<j₁>−X₁<j₂>｜＋｜X₂<k₁>−X₂<k₂>｜＋・・・＋｜X_N-2<a₁>−X_N-2<a₂>｜＋｜X_N-1<b₁>−X_N-1<b₂>｜ ・・・（８式）

そして、三次元四面体補間法では、多次元ＬＵＴを２²個のサブメモリに分割して記憶することを利用し、四次元の単位超立体の基準点（X₀<i>,X₁<j>,X₂<k>,X₃<l>）から点（X₀<i+1>,X₁<j+1>,X₂<k+1>,X₃<l>）までの２³個の頂点に対し、三次元四面体補間法における多次元ＬＵＴの分割記憶方法を適用する（図３の領域８１０）。

単位超立体から補間演算に使用する超四面体を選択する工程は、基準点からどの頂点を通って対角点に到達するかという経路選択問題と考えられるため、マンハッタン距離Ｄｍが同一の頂点群からは常に１つの頂点のみが選択される。つまり、マンハッタン距離Ｄｍが同一の頂点群を同じサブメモリに記憶した場合は、そのサブメモリから異なる２つの頂点は同時には読み出されることはない。そのため、サブメモリへのアクセスが競合することはない。
図３においては、Ｍｅｍ０、Ｍｅｍ１、Ｍｅｍ２、Ｍｅｍ３と記載された太線で囲まれた頂点が同一のサブメモリに記憶され、三次元四面体補間法では、各頂点が４個のサブメモリに分割して記憶されることが理解できる。

また、残った単位超立体の２³個の頂点（X₀<i>,X₁<j>,X₂<k>,X₃<l+1>）〜（X₀<i+1>,X₁<j+1>,X₂<k+1>,X₃<l+1>）に対し、さらに三次元四面体補間法における多次元ＬＵＴの分割記憶方法を適用する（図３の領域８２０）。

最終的には、図３に示すＭｅｍ０，・・・，Ｍｅｍ７と記載された太線で囲まれた頂点が同一のサブメモリに記憶され、多次元ＬＵＴ２６０は、（２×２²）個のサブメモリに分割される。同様に、Ｎ次元超四面体補間法においても、２³個の頂点（X₀<i>,X₁<j>,X₂<k>,…）〜（X₀<i+1>,X₁<j+1>,X₂<k+1>,…）ごとに、三次元四面体補間法における多次元ＬＵＴの分割記憶方法を適用すればよい。

前記２³個の頂点は、２^N-3組あり、１つの組が２²個のサブメモリに記憶されるので、多次元ＬＵＴ２６０は、全部で２^N-1個のサブメモリに分割されることとなる。このように常に２²個のサブメモリを単位としてサブメモリの数が増加していく。以後、増加の単位をクラスタリング単位と呼び、この単位の数だけサブメモリが集まったものをクラスタ・サブメモリと呼び、前記２^N-3組をクラスタ数と呼ぶことにする。また、１つのクラスタ・サブメモリを当てはめる入力次元数をベースｍ（第１の実施の形態の場合、"ｍ＝３"）と呼ぶことにする。

次に、図４を用いて、参照値読み出し部２５０と多次元ＬＵＴ２６０について詳細に説明する。
図４において、（Ｎ＋１）個のアドレス生成回路３１０が、（Ｎ＋１）個の参照座標信号２２２をそれぞれ受けて、アドレス信号３１２と、サブメモリ・バンク選択信号３１４とを算出する。参照値読み出し部２５０には、各サブメモリに対応するアドレス選択回路３２０があり、各アドレス選択回路３２０は、（Ｎ＋１）組のアドレス信号３１２と、サブメモリ・バンク選択信号３１４とを受ける。

各アドレス選択回路３２０は、自身に対応付けられているサブメモリ・バンクＩＤ"ＳｍＢ＿ＩＤ"と、入力されたサブメモリ・バンク選択信号３１４とが等しいアドレス信号２５４を、（Ｎ＋１）本のアドレス信号３１２の中から１つ選択し、選択したアドレス信号２５４を用いて、サブメモリ３３０にアクセスする。

次に、（Ｎ＋１）個のデータ選択回路３４０は、サブメモリ３３０から出力されたサブメモリの個数と等しい数のデータ信号２６２と、対応するアドレス生成回路３１０から出力されたサブメモリ・バンク選択信号３１４とを受け取り、サブメモリ・バンク選択信号３１４と等しいサブメモリ・バンクＩＤ"ＳｍＢ＿ＩＤ"を有するサブメモリ３３０から出力されたデータ信号２６２のみを選択し、選択したデータ信号２６２を参照値２５２として出力する。

次に、アドレスを生成する方法の一例を説明する。図５に、アドレス生成回路３１０の構成の一例を示す。
図５において、アドレス生成回路３１０は、ビット操作部４１０、サブメモリ・バンク生成回路４２０、及びサブメモリ・アドレス生成回路４３０を備えて構成され、Ｎ次元参照座標信号２２２（｛Ｓ₀,Ｓ₁,…,Ｓ_t,…,Ｓ_N-1｝）が参照座標選択部２２０から入力される。

図６に、ビット操作部４１０がＮ次元参照座標信号２２２のビットを操作する方法の一例を示す。
図６において、それぞれがｗビットのビット深度を有するＮ個のＮ次元参照座標信号２２２を、ビット操作部４１０が、下位ビットから所定の形式に並べ替え、（Ｎ×ｗ）ビットの信号５１５を作る。図６に示す例では、まず、ビット操作部４１０は、Ｎ個の参照座標信号２２２の下位１ビット目だけを取り出し、Ｎビットの信号［Ｓ_N-1［０］,・・・,Ｓ_t［０］,・・・,Ｓ₁［０］,Ｓ₀［０］］を作る。

次に、ビット操作部４１０は、Ｎ個のＮ次元参照座標信号２２２の下位２ビット目だけを取り出し、Ｎビットの信号［Ｓ_N-1［１］,・・・,Ｓ_t［１］,・・・,Ｓ₁［１］,Ｓ₀［１］］を作る。さらに、ビット操作部４１０は、Ｎ個の参照座標信号２２２の下位ｕビット目だけを取り出し、Ｎビットの信号［Ｓ_N-1［ｕ］,・・・,Ｓ_t［ｕ］,・・・,Ｓ₁［ｕ］,Ｓ₀［ｕ］］を作る。こうして、Ｎ個の参照座標信号２２２の最上位のＮビットの信号［Ｓ_N-1［ｗ-１］,・・・,Ｓ_t［ｗ-１］,・・・,Ｓ₁［ｗ-１］,Ｓ₀［ｗ-１］］まで同様の操作を行い、図６に示すように各Ｎビットの信号を連結して（Ｎ×ｗ）ビットの信号５１５を作る。

このように、Ｎ個のＮ次元参照座標信号２２２のビットを操作（ビット操作）することで、多次元ＬＵＴ２６０の単位超立体の個数を容易に増やすことができる。例えば、サブメモリ３３０の容量が大きくてもよい多次元補間装置で多次元ＬＵＴ２６０を拡張する場合には、Ｎ次元参照座標信号２２２のビット深度をｗビットから（ｗ+１）ビットに変更し、ビット操作部４１０の出力の上位にＮビットの信号［Ｓ_N-1［ｗ］,・・・,Ｓ_t［ｗ］,・・・,Ｓ₁［ｗ］,Ｓ₀［ｗ］］を連結すればよい。しかも、拡張されたビットは、拡張前のアドレスの上位に連結されるので（アドレスの生成方法については後述する）、拡張前の多次元補間装置と拡張後の多次元補間装置とで、アドレスとデータとの関係に互換性を持たせることができる。

次に、図７を用いて、サブメモリ・バンク生成回路４２０の詳細について説明する。
図７において、ビット操作部４１０から出力された（Ｎ×ｗ）ビットの信号５１５の下位（３＋Ｎ）ビットの信号６０５が、サブメモリ・バンク生成回路４２０に入力される。この信号６０５の下位３ビットの信号６０８は、加算器６３０にて加算処理される。加算処理された値（Ｓ₂[０]＋Ｓ₁[０]＋Ｓ₀[０]）は、信号６３２として出力される。

同様に、上位３ビットの信号６０６は、加算器６１０にて加算処理される。加算処理された値（Ｓ₂[１]＋Ｓ₁[１]＋Ｓ₀[１]）６１２は、左シフタ６４０により１ビットだけ左シフトされ（加算処理された値６１２＜＜１）、シフトされた値が信号６４２として出力される。
また、クラスタ数生成回路６２０は、１を入力値６０７だけ左シフトし（１＜＜入力値６０７）、シフトした値を信号６２２として出力する。
さらに、前記信号６２２、６３２、６４２は、加算器６５０にて加算された後、サブメモリ・バンク選択信号生成回路６６０にて下位（Ｎ−１）ビットのみが取り出され、取り出された信号は、サブメモリ・バンク選択信号３１４として出力される。

次に、図８を用いて、サブメモリ・アドレス生成回路４３０の詳細について説明する。
サブメモリ・アドレス生成回路４３０は、ビット操作部４１０から出力された（Ｎ×ｗ）ビットの信号５１５をもとに、サブメモリ３３０にアクセスするためのアドレス信号３１２を生成する。
ビット操作部４１０から出力された（Ｎ×ｗ）ビットの信号５１５の下位（３＋Ｎ）ビットのうち、６ビットの信号７０９が、下位アドレス生成回路７１０に入力され、４ビットのアドレス下位信号７１２が作成される。なお、残りのビットは、サブメモリ・バンク信号３１４を生成するために使用され、サブメモリ・アドレス生成回路４３０では使用されない。
最後に、ビット連結器７２０を用いて、アドレス上位信号７０８と、４ビットのアドレス下位信号７１２とをビット連結し、連結した信号をアドレス信号３１２として出力する。

ここで、下位アドレス生成回路７１０についてさらに詳細に説明する。
下位アドレス生成回路７１０に入力される６ビットの信号７０９は、３次元入力信号｛Ｓ₀,Ｓ₁,Ｓ₂｝の下位２ビットの信号により形成されており、３Ｄ−ＬＵＴの座標に対応している。これまで説明してきたように、この４×４×４の３Ｄ−ＬＵＴが、４つのサブメモリ３３０に分割されるため、この６ビットの信号７０９は４つのサブメモリ３３０における参照値のすべてに対応している。

しかしながら、必要とするアドレス下位信号７１２は、サブメモリ３３０ごとの下位４ビットのアドレス信号であるため、この６ビットをそのまま使用することはできない。表１に、サブメモリ３３０ごとに分類した６ビットの入力信号７０９と、出力となる４ビットのアドレス下位信号７１２との対応関係を示す。

図９は、４×４×４の３Ｄ−ＬＵＴ内で、サブメモリ・バンクＩＤ（"ＳｍＢ＿ＩＤ=０"）に対応する参照値の位置を、アドレスが小さい順にマークして示した図である（図９の丸付き数字０〜１５）。図９（ａ）において、マークされていない箇所の参照値は、他のサブメモリ３３０に記憶されていることを意味する。

表１のようなテーブルを作成し、４×４×４の３Ｄ−ＬＵＴを回路内にテーブルＲＯＭとして実装することで、６ビットの入力信号７０９を４ビットのアドレス下位信号７１２に容易に変換できる。

また、４×４×４の３Ｄ−ＬＵＴ内の点在する参照点を予め整理し、図９（ｂ）及び図９（ｃ）に示すように、４×４の参照点にまとめれば、テーブルＲＯＭは不要となる。図９（ｂ）に示すようにして参照点を整理した場合には、アドレス下位信号７１２は、［Ｓ₂［１］,Ｓ₂［０］,Ｓ₁［１］,Ｓ₁［０］］の順でビット連結した信号となる。また、図９（ｃ）に示すようにして参照点を整理した場合には、アドレス下位信号７１２は、［Ｓ₂［１］,Ｓ₁［１］,Ｓ₂［０］,Ｓ₁［０］］の順でビット連結した信号となる。

ここで、表２に、前述した第１の従来技術及び第２の従来技術と、本実施形態とを比較した結果を示す。

表２から分かるように、本実施形態では、サブメモリの数を、第１の従来技術の半分にすることができる。また、第２の従来技術と違い、本実施形態では、分割後のサブメモリ１つ当たりに記憶される参照値の数を常に２の冪乗個にすることができる。さらに、Ｎ次元入力（Ｎは４以上の整数）の超四面体補間法において、基本となる３次元入力からアドレスの下位４ビットが常に決定されることになる。そのため、アドレスの下位４ビットを生成する回路は、Ｎの値が変っても同一の回路となる。

また、第２の従来技術では、アドレス生成のために割り算器が必要になるため、アドレス生成回路を小規模化するためにはＮの値ごとにテーブルＲＯＭの内容を変えるなどの工夫が必要となり、Ｎの値ごとにアドレス生成回路を再設計する必要がある。これに対して、前述したように、本実施形態では、Ｎの値が変ってもアドレス生成回路を再利用でき、容易に多次元化に対応できる。さらに、多次元ＬＵＴの単位超立体の個数の増加に伴い、Ｎ次元入力信号のビット深度が増加した場合でも、アドレス生成時のビット操作を行なうことで容易に対応できる。すなわち、本実施形態では、Ｎ次元入力信号の入力数とビット深度との両方に対し拡張性のある多次元補間装置を実現することができる。

以上のように、本実施形態によれば、Ｎ次元入力（Ｎは４以上の整数）の超四面体補間法において、基本となる３次元入力からアドレスの下位４ビットが常に決定され、アドレスの下位４ビットを生成する回路はＮの値が変っても同一の回路となる。そのため、アドレス生成回路を再利用でき、容易に多次元化に対応できる。また、多次元ＬＵＴの単位超立体の個数が増加することに伴って、Ｎ次元入力信号のビット深度が増加した場合でも、アドレス生成時のビット操作を行なうだけで、Ｎ次元入力信号のビット深度の増加に容易に対応することができる。すなわち、本実施形態によれば、Ｎ次元入力信号の入力数とビット深度との両方に対し拡張性のある多次元補間装置を提供することができる。特に、四次元超四面体（５面体）補間法に対して、本実施形態の多次元補間装置を適用する場合、サブメモリ３３０の個数は、必須となる５個よりは多いが、最も小さい２の冪乗数（＝２³個）となるため効果が高い。

（第２の実施形態）
次に、本発明の第２の実施形態について説明する。前述した第１の実施形態では、基本となる３次元入力（ベースｍ＝３）に対し、サブメモリを２²個単位（クラスタリング単位＝２²）で当てはめることで、多次元ＬＵＴを分割して記憶するようにした。四次元超四面体補間法に適用する場合には、前記単位のサブメモリ（クラスタ・サブメモリ）が２組（クラスタ数＝２^4-3）必要となる。多次元ＬＵＴにサブメモリを分割して記憶する方法は、第１の実施形態で説明した方法に限るわけではなく、アドレス生成回路が複雑になるという問題はあるが、一般化することができる。なお、本実施形態の説明において、前述した第１の実施形態と同一の部分については、図１〜図９に付した符号と同一の符号を付すなどして詳細な説明を省略する。

基本となる入力次元数であるベースｍに対してクラスタリング単位は、（ｍ＋１）となる。Ｎ次元超四面体補間法に適用する場合、クラスタ数は２^N-mとなる。Ｎ次元超四面体補間法に必要となるサブメモリの総数ＮＳｍＢは、Ｎ＞ｍが成立する場合、以下の（９式）のようになる。
ＮＳｍＢ＝（ｍ＋１）×２^N-m ・・・（９式）

基本となる入力次元数であるベースｍと、Ｎ次元超四面体補間法を用いた場合のサブメモリの総数との対応関係は、表３に示したようになる。

また、多次元ＬＵＴにサブメモリを分割して記憶することを一般化する方法を、ハードウェア化することも可能である。
図１０は、一般化したサブメモリ・バンク生成回路１４２０を示している。
図１０において、ビット操作部４１０から出力された（Ｎ×ｗ）ビットの信号５１５の下位（ｍ＋Ｎ×ｕ）ビットの信号１６０５を入力する。ここで、ｕは、（ｍ＋1）を２進法で表現することができるビット深度を示す。つまり、log₂（m＋１）以上の最小の整数である。この信号１６０５の下位ｍビットの信号１６０８は、加算器１６３０にて加算処理される。加算処理された値（Ｓ_m-1[０]＋・・・＋Ｓ₁[０]＋Ｓ₀[０]）は、信号１６３２として出力される。

同様に、上位ｍビットの信号１６０６は、加算器１６１０にて加算処理される。加算処理された値（Ｓ_m-1[１]＋・・・＋Ｓ₁[１]＋Ｓ₀[１]）は、左シフタ１６４０により１ビットだけ左シフトされ、シフトされた値が信号１６４２として出力される。そして、図１０に示す通り、同様の操作を（（Ｓ_m-1[ｕ−１]＋・・・＋Ｓ₁[ｕ−１]＋Ｓ₀[ｕ−１]）<<ｕ）となるまで行なう。

さらに、前述した加算処理により得られた信号１６３２と、シフトされた信号１６４２は、後述する加算器１６５０で加算される。これは、入力されたＮ個の参照座標信号（Ｓ₀,Ｓ₁,…,Ｓ_t,…,Ｓ_N-1）のうち、基本となる入力次元数であるベースｍに対応する信号（Ｓ₀,Ｓ₁,…,Ｓ_m-1）の下位ｕビットのみを取り出し、その合計を求めていることを意味する。図１０に示すサブメモリ・バンク生成回路１４２０の例では、ビット操作部４１０の出力に対して処理されるため、加算処理とシフト処理とを行なっている。

また、クラスタ数生成回路１６２０は、クラスタリング単位（ｍ＋１）を入力値１６０７だけ整数倍した値を信号１６２２として出力する。
さらに、前記信号１６３２、１６２２、１６４２は、加算器１６５０にて加算され信号１６５２として出力される。そして、サブメモリ・バンク選択信号生成回路１６６０は、（ｍ＋１）×２^N-mで信号１６５２を割り、その余りがサブメモリ・バンク選択信号１３１４として出力される。

以上のように、本実施形態のサブメモリ・バンク生成回路１４２０では、以下の（１０式）に基づく演算を行なってサブメモリ・バンク選択信号１３１４を生成する回路である。

ただし、＜＜は、ビットの左シフトを表し、％は、割り算の余りを表す（例えばａ％ｂは、ａをｂで割った余りを表す）。
（１０式）の第１項"ΣX_j%(M+1)"では、0〜MのIDを作り、（１０式）の第２項"(M+1)Σ[(X%2)<<(j-M)]で、(M+1)*0,(M+1)*1,(M+1)*2,・・・とオフセットを加算する。
図１０において、クラスタ数生成回路１６２０は、選択されなかった（Ｎ−Ｍ）個の成分について、各々奇数か偶数かを判定し、前記判定結果に基づき（Ｍ＋１）の倍数を前記余りに加算することによって得られる値を指標値とし、前記指標値に基づいて前記頂点を分類する。第２の実施形態では、クラスタリング単位"ｍ+１"を整数倍する値として、ｎ次元入力（S₀, S₁, …, S_m-1, S_m, S_m+1, …, S_n-1）信号のうち、（S_m, S_m+1, …, S_n-1）の信号に着目し、そのＬＳＢである（S_m[0], S_m+1[0], …, S_n-1[0]）を使用しているので、結局、（S_m, S_m+1, …, S_n-1）の信号の奇数か偶数かを判定していることになる。
なお、第２の実施形態では上記着目した信号のLSBにてバンク信号のオフセットの加算の有無を判断しているが、LSBである必要はなく、
（S_m[1], S_m+1[1], …, S_n-1[1]）
（S_m[2], S_m+1[2], …, S_n-1[2]）
・・・
（S_m[w-1], S_m+1[w-1], …, S_n-1[w-1]）
のように、ＬＳＢの代わりに、（S_m, S_m+1, …, S_n-1）のうち定められたビット位置のオン／オフを元にクラスタリング単位（ｍ＋１）を整数倍した値を信号１６２２として出力すればよい。

次に、図１１を用いて、一般化したサブメモリ・アドレス生成回路１４３０について説明する。
図１１（ａ）に示すように、サブメモリ・アドレス生成回路１４３０は、ビット操作部４１０から出力された（Ｎ×ｗ）ビットの信号１５１５をもとに、サブメモリ３３０をアクセスするためのアドレス信号１３１２を生成する。

ビット操作部４１０から出力された（Ｎ×ｗ）ビットの信号１５１５の下位（ｍ＋Ｎ×ｕ）ビットのうち、（ｍ×ｕ）ビットの信号１７０９が、下位アドレス生成回路１７１０に入力され、｛（ｍ−１）×ｕ｝ビットのアドレス下位信号１７１２が生成される。なお、残りのビットは、サブメモリ・バンク信号１３１４を生成するために使用され、サブメモリ・アドレス生成回路１４３０では使用されない。
最後に、ビット連結器１７２０を用いてアドレス上位信号１７０８と、｛（ｍ−１）×ｕ｝ビットのアドレス下位信号１７１２とをビット連結し、連結した信号をアドレス信号１３１２として出力する。

下位アドレス生成回路１７１０は、図１１（ｂ）に示すように、テーブルＲＯＭ１７１０ａを用いてアドレス下位信号１７１２を生成する。このようにした場合、ベースｍが大きくなるにつれて、必要となるテーブルＲＯＭの大きさは大きくなる。
そこで、ベースｍが２の冪乗−１の値（例えば、表３において、ベースｍが３及び７）の場合には、下位アドレス生成回路１７１０を、図１１（ｃ）に示すように、ビット操作のみを行なう回路１７１０ｂを用いて実現できる。表３から分かるように、８次元超四面体補間法の場合、ベースｍが７の構成を用いれば、アドレスの生成が容易となり、且つサブメモリの総数が少ない８次元超四面体補間装置（多次元補間装置）を実現できる。

以上のように、本実施形態によれば、Ｎ次元入力（Ｎは３以上の整数）の超四面体補間法において、基本となる入力次元数であるベースｍを（Ｎ−１）とすれば、クラスタリング単位（ｍ＋１）は常にＮとなる。したがって、クラスタ数は、２^N-m＝２¹となり、多次元ＬＵＴを、（Ｎ×２）個のサブメモリに分割して記憶することができる。

（第３の実施形態）
次に、本発明の第３の実施形態について説明する。本実施形態では、前述した第１の実施形態における多次元ＬＵＴ２６０を、外部メモリとキャッシュ機構とを用いて実現するようにしている。また、本実施形態における多次元ＬＵＴの参照値のビット深度を、８ビットとしている。なお、本実施形態の説明において、前述した第１及び第２の実施形態と同一の部分については、図１〜図１１に付した符号と同一の符号を付して詳細な説明を省略する。

本実施の形態のキャッシュ機構は、外部メモリをバースト・アクセスすることで、データ更新を高速に行なうことを可能とする。ここで、バースト・アクセスとは、１ワードずつ外部メモリからデータを読み出すのではなく、ある連続する複数のアドレスに対応するデータを一括して読み出す方法である。一般に、ＳＤＲＡＭやＤＤＲ−ＳＤＲＡＭなどの汎用メモリは、１６バイト（１２８ビット）単位のバースト・アクセスに対応しており、本実施形態でも、バースト・アクセスの単位を１６バイトとする。

よって、キャッシュ機構は、８ビット（参照値のビット深度）×１６ワードのデータを１つの単位として外部メモリへアクセスする。図８から分かるように、アドレス上位信号７０８が、外部メモリへアクセスするためのアドレス信号となり、アドレス下位信号７１２が、バースト・アクセスによって得られた１６バイトのデータの何バイト目のデータかを指し示す信号となる。以降、アドレス上位信号とアドレス下位信号という言葉で、両者を区別することとする。

図１２に、本実施形態における多次元ＬＵＴの構成の一例を示し、この図１２を用いて、本実施形態の回路動作について説明する。
アドレス信号２５４が入力されると、そのアドレス信号２５４に含まれるアドレス上位信号７０８をもとに、ミスヒット判定回路９２０でキャッシュにヒットしたかどうかが判定される。ミスヒット判定回路９２０は、データバッファ９５０に記憶されているデータに対応するアドレスの上位値をタグＲＡＭ９３０に記憶している。

ミスヒット判定回路９２０は、外部から入力されるアドレス信号２５４に含まれるアドレス上位信号７０８が、タグＲＡＭ９３０に記憶されているアドレス上位値の１つと同じであれば、キャッシュにヒットしたと判定する。一方、アドレス上位信号７０８が、どのアドレス上位値とも異なっている場合には、キャッシュにミスヒットしたと判定する。ミスヒットしたと判定した場合、ミスヒット判定回路９２０は、タグＲＡＭ９３０内の任意のタグ番号に記憶されているアドレス上位値を、外部から入力された上位アドレス信号７０８に上書きし、そのタグ番号に対応するデータバッファ９５０内のデータを外部メモリから更新したデータに置き換える。

このデータの置き換え処理を行なうために、まずミスヒット判定回路９２０は、アドレス信号２５４に含まれているアドレス上位信号７０８を、アドレス信号９２２として調停回路９７５に送り、調停回路９７５、バス９７０、及びメモリコントローラ９６５を介して外部メモリ９６０にデータを要求する。調停回路９７５は、各サブメモリに接続されているキャッシュ機構から出力される各アドレス信号９２２を調停し、順番にメモリコントローラ９６５へ送る。

また、メモリコントローラ９６５から送られてきたデータを、アドレス信号９２２を送った順番で、各サブメモリ９１０ａ〜９１０ｎに接続されているキャッシュ機構に返す。次に、ミスヒット判定回路９２０は、キャッシュにミスヒットしたか否かの判定結果に係わらず、その判定結果を示すフラグと、キャッシュのタグ番号と、アドレス信号２５４に含まれる下位アドレス信号７１２とを、まとめてコマンド信号９４２として遅延回路９４０に送る。なお、サブメモリ９１０の個数は、図１２に示したものに限定されるものではない。

遅延回路９４０は、ＦＩＦＯ（First-In First-Out）で実現されており、ある程度の数のコマンド信号９４２を蓄えることができる。そのため、ミスヒット判定回路９２０は、ＦＩＦＯに空き領域がある間は連続して外部メモリ９６０にアドレス信号９２２を先出しする。キャッシュコントローラ９４５は、遅延回路９４０からコマンド信号９４２を受け取り、判定結果がヒットならタグ番号に対応するデータバッファ９５０から１６バイトのデータ９５２を取り出す。次に、アドレス下位信号７１２により出力する１バイトのデータを選択し、選択したデータを、データ信号２６２として出力する。

キャッシュコントローラ９４５は、判定結果がミスヒットなら、調停回路９７５からデータ９７８が送られるまで待機する。データ９７８が送られてきた時点で、データ９７８からアドレス下位信号７１２により出力する１バイトのデータを選択し、データ信号２６２として出力しつつ、タグ番号に従ってデータ９７８をデータバッファ９５０に書き込んで、データバッファ９５０を更新する。

なお、アドレス上位信号７０８は、図６で説明したビット操作が行なわれている。このため、Ｎ次元参照座標信号（Ｓ₀,Ｓ₁,…,Ｓ_t,…,Ｓ_N-1）のどの信号の変化に対しても、キャッシュのミスヒット率は、ほぼ均一となる。

このように、本実施形態によれば、Ｎ次元入力の超四面体補間装置（Ｎは４以上の整数）において、Ｎの値が変化してもアドレス下位信号７１２は常に４ビットとなり、そのためＮの値が変化してもキャッシュ機構を変える必要がなく、同一の回路を再利用できる。したがって、Ｎの値に係わらず、多次元ＬＵＴを外部メモリとキャッシュ機構とを用いて容易に実現できる。

（本発明の他の実施形態）
上述した実施形態の機能を実現するべく各種のデバイスを動作させるように、該各種デバイスと接続された装置あるいはシステム内のコンピュータに対し、前記実施形態の機能を実現するためのソフトウェアのプログラムコードを供給し、そのシステムあるいは装置のコンピュータ（ＣＰＵあるいはＭＰＵ）に格納されたプログラムに従って前記各種デバイスを動作させることによって実施したものも、本発明の範疇に含まれる。

また、この場合、前記ソフトウェアのプログラムコード自体が上述した実施形態の機能を実現することになり、そのプログラムコード自体、及びそのプログラムコードをコンピュータに供給するための手段、例えば、かかるプログラムコードを格納した記録媒体は本発明を構成する。かかるプログラムコードを記憶する記録媒体としては、例えばフレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。

また、コンピュータが供給されたプログラムコードを実行することにより、上述の実施形態の機能が実現されるだけでなく、そのプログラムコードがコンピュータにおいて稼働しているＯＳ（オペレーティングシステム）あるいは他のアプリケーションソフト等と共同して上述の実施形態の機能が実現される場合にもかかるプログラムコードは本発明の実施形態に含まれることは言うまでもない。

さらに、供給されたプログラムコードがコンピュータの機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに格納された後、そのプログラムコードの指示に基づいてその機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって上述した実施形態の機能が実現される場合にも本発明に含まれることは言うまでもない。

これまで述べてきたように、本発明の各実施形態では、Ｎ次元のデジタル画像信号２０５を上位ビット信号２０５と下位ビット信号２１４とに分割し、分割した上位ビットの信号すべての組み合わせに対応する参照値を重複することなく２^N-1個のサブメモリ３３０（多次元ＬＵＴ２６０）に分割記憶するとともに、補間演算に必要な（Ｎ＋１）個の参照値を同時に読み出すようにすることにより、補間演算を高速化することができるとともに、割り算器がなくてもサブメモリ３３０へアクセスするためのアドレスを生成することができるようにして、色空間の変換などの補間演算を高速に行なえるようにすることが、可及的に小さな回路規模で容易に実現できるようにした。さらに、多次元に拡張するに際して、アドレス生成回路やキャッシュ機構の再設計が不要であり、入力数とビット深度との両方に対し拡張性の高い多次元補間装置を提供することができる。

本発明の第１の実施形態を示し、カラー複写機の全体構成の一例を示すブロック図である。 本発明の第１の実施形態を示し、多次元補間装置の回路構成の一例を示すブロック図である。 本発明の第１の実施形態を示し、基準点から対角点までの単位立体の各頂点を、四次元マンハッタン距離を用いて分類した結果を示す図である。 本発明の第１の実施形態を示し、参照値読み出し部と多次元ＬＵＴの回路構成の一例を示すブロック図である。 本発明の第１の実施形態を示し、アドレス生成回路の構成の一例を示すブロック図である。 本発明の第１の実施形態を示し、ビット操作部がＮ次元参照座標信号のビットを操作する方法の一例を説明する図である。 本発明の第１の実施形態を示し、サブメモリ・バンク生成回路の構成の一例を示す図である。 本発明の第１の実施形態を示し、サブメモリ・アドレス生成回路の構成の一例を示す図である。 本発明の第１の実施形態を示し、サブメモリ・バンクＩＤに対応する参照値の位置を、アドレスが小さい順にマークして示した図である。 本発明の第２の実施形態を示し、一般化したサブメモリ・バンク生成回路の構成の一例を示す図である。 本発明の第２の実施形態を示し、一般化したサブメモリ・アドレス生成回路の構成の一例を示す図である。 本発明の第３の実施形態を示し、キャッシュ機構をもった多次元ＬＵＴの構成の一例を示す図である。 本発明の実施形態を示し、３Ｄ-ＬＵＴを用いて三次元補間演算を行なう場合の機能ブロック図である。 本発明の実施形態を示し、三次元入力の色空間（ＲＧＢ空間）を単位立体に分割した状態を示す図である。 本発明の実施形態を示し、四次元超四面体補間法のおける稜線の選択方法を説明する図である。

符号の説明

１００ 原稿
１１０ ＣＰＵ回路部
１２０ 画像読み取り部
１３０ 画像処理部
１４０ プリンタ部
２１０ データ分割部
２２０ 参照座標選択部
２３０ 順序判定部
２４０ 重み係数算出部
２５０ 参照点読み出し部
２６０ 多次元ＬＵＴ
２７０ 補間演算部

Claims (7)

1. Ｎ次元直交座標（Ｎは４以上の整数）上の各単位超立体の頂点に対応するデータを格納した（Ｍ＋１）×２ ^(N-M) 個のサブメモリ（ＭはＮより小さい整数）のいずれかから前記対応するデータを読み出すために、前記Ｎ次元直交座標上の各単位超立体の頂点を（Ｍ＋１）×２^(N-M)通りのいずれかに分類する方法であって、
   それぞれが複数のビットで表わされるＮ個の成分からなる頂点の座標値のうちのＭ個の成分を選択する選択工程と、
   前記選択工程により選択されたＭ個の成分の総和を算出する第１の算出工程と、
   前記第１の算出工程により算出された総和を、（Ｍ＋１）で割った余りを算出する第２の算出工程と、
   前記選択工程により選択されなかった（Ｎ−Ｍ）個の成分のそれぞれの所定のビット位置の値によりなる整数を（Ｍ＋１）倍した結果を、前記第２の算出工程により算出された余りに加算して、前記頂点を（Ｍ＋１）×２^(N-M)個のグループのいずれかに分類するための指標値を算出する第３の算出工程と、
   前記第３の算出工程により算出された指標値が示すグループに前記頂点を分類する分類工程とを有することを特徴とするデータ分類方法。
2. Ｎ次元直交座標（Ｎは４以上の整数）上の各単位超立体の頂点に対応するデータを格納した（Ｍ＋１）×２ ^(N-M) 個のサブメモリ（ＭはＮより小さい整数）のいずれかから前記対応するデータを読み出すために、前記Ｎ次元直交座標上の各単位超立体の頂点を（Ｍ＋１）×２^(N-M)通りのいずれかに分類する方法であって、
   それぞれがＮ個の成分からなる頂点の座標値のうちのＭ個の成分を選択する選択工程と、
   前記選択工程により選択されたＭ個の成分の総和を算出する第１の算出工程と、
   前記第１の算出工程により算出された総和を、（Ｍ＋１）で割った余りを算出する第２の算出工程と、
   前記選択工程により選択されなかった（Ｎ−Ｍ）個の成分のそれぞれが奇数か偶数かを示す値によりなる整数を（Ｍ＋１）倍した結果を、前記第２の算出工程により算出された余りに加算して、前記頂点を（Ｍ＋１）×２^(N-M)個のグループのいずれかに分類するための指標値を算出する第３の算出工程と、
   前記第３の算出工程により算出された指標値が示すグループに、前記頂点を分類する分類工程とを有することを特徴とするデータ分類方法。
3. 前記第３の算出工程は、以下の式を用いて指標値ｉｄを算出することを特徴とする請求項１又は２に記載のデータ分類方法。ここで、前記式は、
   

   

   である。
   ただし、％は、割り算の余りであることを表す。
4. 前記Ｍは３であり、
   前記分類工程は、前記頂点を、２^N-1個のグループに分類することを特徴とする請求項１又は２に記載のデータ分類方法。
5. 前記Ｍは（Ｎ−１）であり、
   前記分類工程は、前記頂点を、（Ｎ×２）個のグループに分類することを特徴とする請求項１又は２に記載のデータ分類方法。
6. Ｎ次元直交座標（Ｎは４以上の整数）上の各単位超立体の頂点に対応するデータを格納した（Ｍ＋１）×２ ^(N-M) 個のサブメモリ（ＭはＮより小さい整数）のいずれかから前記対応するデータを読み出すために、前記Ｎ次元直交座標上の各単位超立体の頂点を（Ｍ＋１）×２^(N-M)通りのいずれかに分類する方法であって、
   それぞれが複数のビットで表わされるＮ個の成分からなる頂点の座標値のうちのＭ個の成分を選択する選択工程と、
   前記選択工程により選択されたＭ個の成分の総和と、前記選択工程により選択されなかった（Ｎ−Ｍ）個の成分のそれぞれの所定のビット位置の値によりなる整数を（Ｍ＋１）倍した結果とを加算する第１の算出工程と、
   前記第１の算出工程による加算の結果を、（Ｍ＋１）×２^(M-N)で割った余りを算出する第２の算出工程と、
   前記第２の算出工程により算出された余りを、前記頂点を（Ｍ＋１）×２^(N-M)個のグループのいずれかに分類するための指標値として用いて、前記頂点を前記指標値が示すグループに分類する分類工程とを有することを特徴とするデータ分類方法。
7. Ｎ次元直交座標（Ｎは４以上の整数）上の各単位超立体の頂点に対応するデータを格納した（Ｍ＋１）×２ ^(N-M) 個のサブメモリ（ＭはＮより小さい整数）のいずれかから前記対応するデータを読み出すために、前記Ｎ次元直交座標上の各単位超立体の頂点を（Ｍ＋１）×２^(N-M)通りのいずれかに分類する方法であって、
   それぞれがＮ個の成分からなる頂点の座標値のうちのＭ個の成分を選択する選択工程と、
   前記選択工程により選択されたＭ個の成分の総和と、前記選択工程により選択されなかった（Ｎ−Ｍ）個の成分のそれぞれが奇数か偶数かを示す値によりなる整数を（Ｍ＋１）倍した結果とを加算する第１の算出工程と、
   前記第１の算出工程による加算の結果を、（Ｍ＋１）×２^(M-N)で割った余りを算出する第２の算出工程と、
   前記第２の算出工程により算出された余りを、前記頂点を（Ｍ＋１）×２^(N-M)個のグループのいずれかに分類するための指標値として用いて、前記頂点を前記指標値が示すグループに分類する分類工程とを有することを特徴とするデータ分類方法。

Images