(57)【要約】【課題】本発明は多次元補間装置に関し、ハードウェア資源の節約と演算速度の高速化を図ることができる多次元補間装置を提供することを目的としている。【解決手段】カラーＬＵＴを用いて、Ｎ（Ｎ≧３）次元及び補間間隔Ｍの補間を行なう補間装置であって、Ｎ次元体の各対角線を含み、補間対象となる入力値が内部に存在する各三角錐の各頂点に関する重み係数を各頂点毎に足し合わせるとともに、各頂点に対応するカラーＬＵＴの値を乗算し、それぞれ求められた値を足し合わせて得られた値をＭ×２N-1で除算することにより、前記入力値に対する補間値を求める手段を設けて構成される。【選択図】図１
2006203885.tif 000002
【特許請求の範囲】
【請求項１】
カラーＬＵＴを用いて、Ｎ（Ｎ≧３）次元及び補間間隔Ｍの補間を行なう補間装置であって、
Ｎ次元体の各対角線を含み、補間対象となる入力値が内部に存在する各三角錐の各頂点に関する重み係数を各頂点毎に足し合わせるとともに、各頂点に対応するカラーＬＵＴの値を乗算し、それぞれ求められた値を足し合わせて得られた値をＭ×２N-1で除算することにより、前記入力値に対する補間値を求める手段を設けたことを特徴とする多次元補間装置。
【請求項２】
前記Ｍ×２N-1が２のべき乗にならない時、カラーＬＵＴに格納するデータを予め割り算し、２のべき乗倍して格納することを特徴とする請求項１記載の多次元補間装置。
【請求項３】
Ｎ個のデータを少なくとも１個のアドレス生成器に入力し、該アドレス生成器の出力でカラーＬＵＴと重み係数発生器にアクセスし、該ＬＵＴと重み係数発生器の出力を乗算器で乗算し、乗算した結果に所定のデータ処理を行なって補間されたデータを出力する多次元補間装置において、
補間対象となる入力値近傍の２N点のＬＵＴの値を用いて補間を行なう場合において、重み係数を、補間間隔Ｍに対して（Ｍ＋１）／２のアドレスに対して発生し、多次元補間を行なう手段を設けたことを特徴とする多次元補間装置。
【請求項４】
Ｎ次元のＬＵＴの補間演算を行なうに際し、ＬＵＴの３色乃至４色の値のうち、複数の色データに対して同時に重み係数を乗算することを特徴とする請求項１乃至３の何れかに記載の多次元補間装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は多次元補間装置に関する。
【背景技術】
【０００２】
カラー画像印刷装置等においては、印刷された画像の視覚特性を向上させるために、読み取ったカラー画像データに色変換を行なって別の色系統に変換することが行われている。この色変換装置としては、ＬＵＴ（ルックアップテーブル）と補間演算装置を用いるものがある。この装置は、入力画像データをアドレスとしてＬＵＴをアクセスして変換画像データを出力し、ＬＵＴに記憶されていない画像データについては、格子点位置のＬＵＴの出力に、補間演算装置である重み係数を乗算する処理を行なって補間を行なうものである。
【０００３】
従来の色変換装置としては、以下のようなものがある（例えば特許文献１参照）。
（ａ）立方体補間（８点補間。英国特許１３６９７０２号）
図６は立方体補間の説明図である。（ａ）は元の空間、（ｂ）は変換先の空間である。元の空間はＲ，Ｇ，Ｂ空間、変換先の空間はＹ，Ｍ，Ｃ空間である。まず、（ａ）に示す立方体内の任意の１点Ｐを軸として図に示すように８個の直方体に分割する。分割されたそれぞれの空間の体積をＶｉ（ｉ＝０〜７）とする。この時、変換先の空間に写像される点Ｐ’の補間値は次式で与えられる。
【０００４】
【数１】
2006203885.tif 000003
【０００５】
ここで、Ｐｉは既に求まっている元の空間の値、Ｖｉは点Ｐにより分割された立方体Ｖを構成する８個の直方体の体積、Ｖは元の直方体の体積である。
また、以下のようなものがある（例えば特許文献２参照）。
（ｂ）三角錐補間（４点補間。特開昭５３−１２３２０１号）
図７は三角錐補間の説明図である。三角錐補間は、３次元の画像データ入力に対応するデータが蓄積されたメモリ空間に対して、画像データを入力して変換データを求めるに際し、前記メモリ空間アドレスを構成する立方体を複数個の三角錐に分割し、画像データ入力に対して当該入力値に対応する点が分割された三角錐のいずれに含まれているか判別し、次に判別された三角錐の各頂点における値（４個）を用いて、その内部の点を補間により求めるものである。
【０００６】
図７において、（ａ）は１辺の長さＬの立方体を原点ａから各頂点を結ぶ軸によって６個の三角錐に分割した状態を示し、（ｂ）はそれを分解した図である。この時の、任意の三角錐内の点の補間値Ｐ’は次式で与えられる。
Ｐ’＝（Ｌ−Ａ）×Ｐ１＋（Ａ−Ｂ）×Ｐ２＋（Ｂ−Ｃ）×Ｐ３＋Ｃ  （２）
ここで、Ａ，Ｂ，Ｃは入力データの下位桁を示し、Ａ＞Ｂ＞Ｃの関係にあるものとし、Ｐｉは既に求まっている相手の空間の値（３次元座標値）である。
【０００７】
また、以下のようなものがある（例えば被特許文献１）。
（ｃ）三角柱補間（６点補間。文献
Ｋ．Ｋａｎａｍｏｒｉ，Ｈ．Ｋｏｔｅｒａ，Ｏ．Ｙａｍａｄａ，Ｈ．Ｍｏｔｏｍｕｒａ，Ｒ．Ｉｉｋａｗａ，Ｔ．Ｆｕｍｏｔｏ，Ｆａｓｔ  ｃｏｌｏｒ  ｐｒｏｃｅｓｓｏｒ  ｗｉｔｈ  ｐｒｏｇｒａｍｍａｂｌｅ  ｉｎｔｅｒｐｏｌａｔｉｏｎ  ｂｙ  ｓｍａｌｌ  ｍｅｍｏｒｙ（ＰＲＩＳＭ），Ｊｏｕｒｎａｌ  ｏｆＥｌｅｃｔｒｏｎｉｃ  Ｉｍａｇｉｎｇ，２（３），２１３−２２４（１９９３））
この補間方法は、（ｂ）で示した三角錐３個を一つにして三角柱とし、計６点のデータから補間するようにしたものである。
【０００８】
また、以下のようなものがある（例えば被特許文献１）。
（ｄ）パラレル処理による補間（米国特許４８３７７２２号）
カラーＬＵＴをパラレルに配置する時、ＬＵＴ毎に互い違いに必要な点だけのポジションで持ち、トータルのＬＵＴのサイズは、単独のＬＵＴで持つ時と同じにしたものである。また、重み係数全てをＲＯＭで記憶して保持している。
【特許文献１】英国特許１３６９７０２号
【特許文献２】特開昭５３−１２３２０１号公報
【特許文献３】米国特許４８３７７２２号
【非特許文献１】Ｋ．Ｋａｎａｍｏｒｉ，Ｈ．Ｋｏｔｅｒａ，Ｏ．Ｙａｍａｄａ，Ｈ．Ｍｏｔｏｍｕｒａ，Ｒ．Ｉｉｋａｗａ，Ｔ．Ｆｕｍｏｔｏ，Ｆａｓｔ  ｃｏｌｏｒ  ｐｒｏｃｅｓｓｏｒ  ｗｉｔｈ  ｐｒｏｇｒａｍｍａｂｌｅ  ｉｎｔｅｒｐｏｌａｔｉｏｎ  ｂｙ  ｓｍａｌｌ  ｍｅｍｏｒｙ（ＰＲＩＳＭ），Ｊｏｕｒｎａｌ  ｏｆＥｌｅｃｔｒｏｎｉｃ  Ｉｍａｇｉｎｇ，２（３），２１３−２２４（１９９３））
【発明の開示】
【発明が解決しようとする課題】
【０００９】
前記立方体補間の場合、重み係数を求めたい点が区切る点の反対側の直方体の体積を用いるため、最大補間間隔をＭとした時Ｍ3 で計算される重み係数を発生する必要があった。例えば、Ｍ＝１７の場合、４９１３となりハードウェアで構成する場合には、１３ビットものデータ線が必要となり、また乗算器のビット幅を広げなくてはならなかったため、コストやハードウェア規模の点で不利であった。更に、補間演算する場合、１色を８ビットとすると、（８＋１３）ビット必要で、６４ビットのレジスタで４色を同時に演算することはできなかった。
【００１０】
前記三角錐補間の場合、重み係数の最大値はＭ（補間間隔）となり、データ線の数は大幅に節約できる。しかしながら、補間係数の算出のために、純粋に演算で行なう場合、単位立方体を５個乃至６個に分割するための判別を行なう必要があり、この判断が複雑になる。このような不具合を避けるために、予めＬＵＴの形で計算して記憶しておく方法もあるが、この場合、補間間隔をＭとした時にＭ3となり、例えばＭ＝１７の場合には４９１３ワードのデータを記憶する必要があった。また、補間点数が少ないため（４点）、精度の点で問題があった。
【００１１】
前記三角柱補間の場合、異方性が高く、補間方向に応じては、誤差が大きくなるという問題があった。
前記パラレル処理補間の場合、重み係数をＬＵＴとして持っているため、格子間隔Ｍが増大すると、ＬＵＴサイズが増大するという問題があった。
【００１２】
更に、これら従来技術に共通する問題として、補間間隔Ｍが２のべき乗の時は、最終段での割算の代わりにビットシフトを用いることができるが、Ｍが２のべき乗でない場合は、ビットシフトは行えず最終段で割算を行なう必要があり、このため回路規模が増大したり、演算時間の増大を招いていた。
【００１３】
本発明はこのような課題に鑑みてなされたものであって、ハードウェア資源の節約と演算速度の高速化を図ることができる多次元補間装置を提供することを目的としている。
【課題を解決するための手段】
【００１４】
（１）請求項１記載の発明は、カラーＬＵＴを用いて、Ｎ（Ｎ≧３）次元及び補間間隔Ｍの補間を行なう補間装置であって、Ｎ次元体の各対角線を含み、補間対象となる入力値が内部に存在する各三角錐の各頂点に関する重み係数を各頂点毎に足し合わせるとともに、各頂点に対応するカラーＬＵＴの値を乗算し、それぞれ求められた値を足し合わせて得られた値をＭ×２N-1で除算することにより、前記入力値に対する補間値を求める手段を設けたことを特徴とする。
（２）請求項２記載の発明は、前記Ｍ×２N-1が２のべき乗にならない時、カラーＬＵＴに格納するデータを予め割り算し、２のべき乗倍して格納することを特徴とする。
（３）請求項３記載の発明は、Ｎ個のデータを少なくとも１個のアドレス生成器に入力し、該アドレス生成器の出力でカラーＬＵＴと重み係数発生器にアクセスし、該ＬＵＴと重み係数発生器の出力を乗算器で乗算し、乗算した結果に所定のデータ処理を行なって補間されたデータを出力する多次元補間装置において、補間対象となる入力値近傍の２N点のＬＵＴの値を用いて補間を行なう場合において、重み係数を、補間間隔Ｍに対して（Ｍ＋１）／２のアドレスに対して発生し、多次元補間を行なう手段を設けたことを特徴とする。
（４）請求項４記載の発明は、Ｎ次元のＬＵＴの補間演算を行なうに際し、ＬＵＴの３色乃至４色の値のうち、複数の色データに対して同時に重み係数を乗算することを特徴とする。
【発明の効果】
【００１５】
（１）請求項１記載の発明によれば、ハードウェア資源の節約と演算速度の高速化を図ることができる多次元補間装置を提供することができる。
（２）請求項２記載の発明によれば、補間演算の最後で行なう重み係数による割算が単にデータのシフト（右シフト）のみで行えることになり、演算時間を高速化することができる。
（３）請求項３記載の発明によれば、重み係数を、補間間隔Ｍに対して（Ｍ＋１）／２のアドレスに対して発生し、多次元補間を行なうことにより、重み係数発生用のメモリ容量を削減し、ハードウェア資源を節約することができる。
（４）請求項４記載の発明によれば、ＬＵＴの３色乃至４色の値のうち、複数の色データに対して同時に重み係数を乗算する手段を設けているので、ハードウェア資源を節約し、補間演算を高速化することができる。
【発明を実施するための最良の形態】
【００１６】
〔本発明の作用〕
本発明の第１の形態では、補間に対する重み係数の最大値を、補間間隔Ｍの時、Ｍ×２N-1 で与えるようにして、重み係数の最大値を抑制するようにした。これにより、ハードウェア資源の節約を図ることができ、演算時間の高速化を図ることができる。
【００１７】
ここで、Ｍ×２N-1 は、以下のようにして求めた。
本発明は、前記三角錐補間を拡張したものである。図７の（ａ）では、立方体の対角を軸として６個の三角錐に分割しているが、この軸について全ての組み合わせを作る。つまり、図のａ−ｇ，ｂ−ｈ，ｃ−ｅ，ｄ−ｆそれぞれの軸を変えた時の三角錐補間での重み係数を全部計算して平均をとると、前記した
Ｍ×２N-1 が得られる。本発明によれば、全方向の軸について重み係数を求めて平均している結果、軸の方向性の影響がなくなる。
【００１８】
この場合において、Ｎ次元のＬＵＴの補間演算を行なうに際し、ＬＵＴの３色乃至４色の値のうち、複数の色データに対して同時に重み係数を乗算することにより、ハードウェア資源を節約し、補間演算を高速化することができる。
【００１９】
本発明の第２の形態では、Ｎ次元の補間を行なう場合において、重み係数を、補間間隔Ｍに対して（Ｍ＋１）／２のアドレスに対して発生し、多次元補間を行なうことにより、重み係数発生用のメモリ容量を削減し、ハードウェア資源を節約することができる。
【００２０】
重み係数は、小空間内において格子点に対して、どの方向にも線対称になるという性質がある。このことを図で説明する。図８は重み係数の性質の説明図（１次元の場合）である。縦軸は重み係数、横軸は格子点Ｑ１，Ｑ２間の距離を示している。図において、ｆ１はＱ１に対する重み特性、ｆ２はＱ２に対する重み特性である。この時の距離を補間間隔Ｍとする。このＭの中心（Ｍ／２）を通る軸Ｓを考えると、重み係数はこの軸Ｓに関して線対称になっている。
【００２１】
つまり、特性ｆ１の右半分は、軸Ｓに関して折り返せば特性ｆ２の左半分に重なり、特性ｆ２の右半分は、軸Ｓに関して折り返せば特性ｆ１の左半分に重なる。例えば、特性ｆ１の右半分の重み係数Ｗ１，Ｗ２，Ｗ３はそれぞれ特性ｆ２の左半分の重み係数Ｗ１’，Ｗ２’，Ｗ３’と等しくなり、特性ｆ２の右半分の重み係数Ｗ４，Ｗ５はそれぞれ特性ｆ１の左半分の重み係数Ｗ４’，Ｗ５’と等しくなる。アドレスは、図に示すようにＭのところまでくるが、Ｓを超えたらＱ１とＱ２を切り替えるようにする。例えば、アドレスに応じて特性ｆ１の重み係数を順次発生していき、アドレスがＭ／２を超えたら特性をそれまでのｆ１からｆ２に切り替え、ｆ２の左半分の重み係数を用いるのである。
【００２２】
従って、重み係数のデータとしては、軸Ｓより左側のデータのみ持てばよく、軸Ｓより右側のデータは持つ必要はないことになる。このようにして、重み係数発生の数を減らすことができる。必要な重み係数のデータ量は、１次元の場合で１／２，２次元の場合で１／４，３次元の場合で１／８となる。このように、本来必要な重み係数データよりも少ないデータ量ですませることができる。
【００２３】
なお、発生するアドレスとしては、軸Ｓ上の値Ｗ０も含ませる必要があるので、Ｍが偶数である場合を考慮して（Ｍ＋１）／２のアドレスまでとしたものである。
この発明によれば、重み係数の数を減らすことができ、ハードウェア資源を節約することができる。
【００２４】
この場合において、Ｎ次元のＬＵＴの補間演算を行なうに際し、ＬＵＴの３色乃至４色の値のうち、複数の色データに対して同時に重み係数を乗算することにより、ハードウェア資源を節約し、補間演算を高速化することができる。
【００２５】
本発明の第３の形態では、最大重み係数が２のべき乗にならない時、カラーＬＵＴに格納するデータを予め割算し、２のべき乗倍して格納することようにした。これにより、補間演算の最後で行なう重み係数による割算が単にデータのシフト（右シフト）のみで行えることにより、演算時間を高速化することができる。
【００２６】
本発明の第４の形態では、補間に対する重み係数の最大値を、補間間隔Ｍの時、Ｍ×２N-1 で与える手段を設け、重み係数の最大値を抑制するようにした。これにより、ハードウェア資源の節約を図ることができ、演算時間の高速化を図ることができる。
【００２７】
この場合において、Ｎ次元のＬＵＴの補間演算を行なうに際し、ＬＵＴの３色乃至４色の値のうち、複数の色データに対して同時に重み係数を乗算する手段を設けることにより、ハードウェア資源を節約し、補間演算を高速化することができる。
【００２８】
本発明の第５の形態では、Ｎ次元の補間を行なう場合において、重み係数を、補間間隔Ｍに対して（Ｍ＋１）／２のアドレスに対して発生する手段を設けた。その理由は、前記第２の発明の場合と同じである。これにより、重み係数の数を減らすことができ、ハードウェア資源を節約することができる。
【００２９】
この場合において、Ｎ次元のＬＵＴの補間演算を行なうに際し、ＬＵＴの３色乃至４色の値のうち、複数の色データに対して同時に重み係数を乗算する手段を設けることにより、ハードウェア資源を節約し、補間演算を高速化することができる。
【００３０】
本発明の第６の形態では、最大重み係数が２のべき乗にならない時、カラーＬＵＴに格納するデータを予め割算し、２のべき乗倍して格納する手段を設けた。その理由は、前記第３の発明の場合と同じである。これにより、補間演算の最後で行なう重み係数による割算が単にデータのシフト（右シフト）のみで行えることにより、演算時間を高速化することができる。
【００３１】
以下、図面を参照して本発明の実施の形態例を詳細に説明する。
図１は本発明の一実施例を示す構成ブロック図で、Ｎ＝３、即ち３次元の補間の場合を示す。この実施例は、Ｒ，Ｇ，Ｂデータを受けて、これらデータを新たなＲｎｅｗ，Ｇｎｅｗ，Ｂｎｅｗデータに変換するものである。図中のデータ線中の数字はビット数を示す。
【００３２】
図において、１はＲ（Ｒｅｄ）データ及びカウンタ出力を受けて対応したアドレスを発生するＲアドレス生成器、２はＧ（Ｇｒｅｅｎ）データ及びカウンタ出力を受けて対応したアドレスを発生するＧアドレス生成器、３はＢ（Ｂｌｕｅ）データを受けて対応したアドレスを発生するＢアドレス生成器である。４はクロックＣＬＫをカウントする２ビット出力の４進カウンタである。このカウンタ４の出力の上位ビットをＣ１、下位ビットをＣ０とすると、Ｃ０はＲアドレス生成器１に、Ｃ１はＧアドレス生成器２にそれぞれ入力される。Ｒアドレス生成器１とＧアドレス生成器２は８ビットの出力を発生し、Ｂアドレス生成器３はＢ軸に関してパラレル処理するため、上位アドレスとして４ビットの２種類のアドレスを発生している。その他のＲ軸，Ｇ軸は時系列的に演算される。
【００３３】
５はＲアドレス生成器１の下位４ビット，Ｇアドレス生成器２の下位４ビット，Ｂアドレス生成器３の下位４ビット及び４進カウンタ４の出力を受けて７ビットの重み係数を発生する近傍用の重み発生器、６は同様にＲアドレス生成器１の下位４ビット，Ｇアドレス生成器２の下位４ビット，Ｂアドレス生成器３の下位４ビット及び４進カウンタ４の出力を受けて７ビットの重み係数を発生する遠方用の重み発生器である。近傍用，遠方用とは、重み係数空間を２分割し、一方を近傍用、他方を遠方用としたものである。本発明では、重み係数の空間領域における線対称性を利用している結果、この実施例の場合、３次元空間であるので必要な重み発生器は、本来の容量の１／（２3）＝１／８ですむ。従って、メモリの容量が大幅に減少し、ハードウェア資源の節約が図れる。
【００３４】
１０はＲアドレス生成器１の上位４ビット，Ｇアドレス生成器２の上位４ビット，Ｂアドレス生成器３の２種類の上位４ビット及び重み発生器５，６の出力を受けて新しいＲデータＲｎｅｗを発生するＲ処理部、２０はＲアドレス生成器１の上位４ビット，Ｇアドレス生成器２の上位４ビット，Ｂアドレス生成器３の２種類の上位４ビット及び重み発生器５，６の出力を受けて新しいＧデータＧｎｅｗを発生するＧ処理部、３０はＲアドレス生成器１の上位４ビット，Ｇアドレス生成器２の上位４ビット，Ｂアドレス生成器３の２種類の上位４ビット及び重み発生器５，６の出力を受けて新しいＢデータＢｎｅｗを発生するＢ処理部である。Ｇ処理部２０，Ｂ処理部３０の構成は図示されていないが、カラーＬＵＴに記憶されるデータが異なるのみで、Ｒ処理部１０の構成と同一である。
【００３５】
Ｒ処理部１０において、１１はＲアドレス生成器１の上位４ビット，Ｇアドレス生成器２の上位４ビット，Ｂアドレス生成器３の一方の上位４ビットを受けるＢ近傍用のカラーＬＵＴ、１２はＲアドレス生成器１の上位４ビット，Ｇアドレス生成器２の上位４ビット，Ｂアドレス生成器３の他方の上位４ビットを受けるＢ遠方用のカラーＬＵＴである。これらカラーＬＵＴ１１，１２は、例えば上下とも同じデータが格納されるメモリで構成される。例えば同時に２個のデータを読み出せるデュアルポートＲＡＭが用いられる。これらＬＵＴ１１，１２はＲ，Ｇ，Ｂデータの入力０，１７，３４，…２３８，２５５の組み合わせに対応する１６×１６×１６×１０個のデータが格納される。そして、出力１０ビットのうち、１ビットは符号を、１ビットは２５５を超える値を示す。
【００３６】
１３はカラーＬＵＴ１１の出力及び重み発生器５の出力を乗算する乗算器、１４はカラーＬＵＴ１２の出力及び重み発生器６の出力を乗算する乗算器である。これら乗算器１３，１４は、カラーＬＵＴ１１，１２の出力１０ビット、重み発生器５，６の出力７ビットを受け、１６ビット出力（このうち１ビットは符号）のものが用いられる。１５は乗算器１３，１４の出力を加算する加算器である。該加算器１５は、乗算器１３，１４の各１６ビットを受けて１６ビット（このうち１ビットは符号）のデータを出力する。
【００３７】
１６は加算器１５の出力を積算する積算器である。この積算器１６は、４進カウンタの出力の値だけの、つまり４回の演算結果を積算する。１７は積算器１６の出力を重み係数で割算するための割算器である。該割算器１７は、積算器１６の出力１６ビットを受けて８ビットのデータを出力する。この割算器１７の出力が変換された新しいＲデータＲｎｅｗになる。このように構成された回路の動作を説明すれば、以下のとおりである。
【００３８】
画像データＲ，Ｇ，Ｂはそれぞれのアドレス生成器１，２，３に入力され、各アドレス生成器１〜３は、以下のアルゴリズムに従ったアドレスデータを生成する。
１）Ｒアドレス生成器
入力をＡ（０〜２５５）とし、出力の上位桁をＸ（０〜１５）、下位桁をＹ（０〜８）とし、カウンタ４の入力の上位をＣ０（０，１）、下位をＣ１（０，１）とする。Ｃ言語で表したアルゴリズムは以下のとおりである。Ｌｉ（ｉ＝１〜８）はライン番号を示す。
ｉｆ（Ａ％１７＜＝８）｛              Ｌ１
Ｙ＝Ａ％１７；                      Ｌ２
Ｘ＝Ａ／１７＋Ｃ０；                Ｌ３
ｉｆ（Ｘ＞１５）Ｘ＝１５；          Ｌ４
｝ｅｌｓｅ｛                          Ｌ５
Ｙ＝１７−Ａ％１７；                Ｌ６
Ｘ＝Ａ／１７＋（１−Ｃ０）；        Ｌ７
ｉｆ（Ｘ＞１５）Ｘ＝１５；          Ｌ８
｝
上記アルゴリズムにおいて、
Ｌ１：Ａを１７で割った時の余り（Ａ％１７）が８以下の時、
Ｌ２：Ａを１７で割った時の余りをＹの値とする。
Ｌ３：Ａを１７で割った時の商にＣ０を加えたものをＸの値とする。
Ｌ４：この時において、Ｘが１５よりも大きくなる時は、Ｘの値を１５に固定する。
Ｌ５：Ｌ１の条件が満たされない時、つまりＡを１７で割った時の余りが９以上の時、
Ｌ６：１７からＡを１７で割った時の余りを引いたものをＹの値とする。
Ｌ７：入力Ａを１７で割った値と（１−Ｃ０）を加えたものをＸの値とする。
Ｌ８：この時において、Ｘが１５よりも大きくなる時は、Ｘの値を１５に固定する。
【００３９】
このようなアルゴリズムにより、Ｒデータが入力される度にＲアドレス生成器１の上位４ビットからＸの値が出力され、下位４ビットからＹの値が出力される。
２）Ｇアドレス生成器
その動作はＲアドレス生成器１と同様である。つまり、入力をＡ（０〜２５５）とし、出力の上位桁をＸ（０〜１５）、下位桁をＹ（０〜８）とし、カウンタ４の入力の上位をＣ０（０，１）、下位をＣ１（０，１）とする。Ｃ言語で表したアルゴリズムは以下のとおりである。
ｉｆ（Ａ％１７＜＝８）｛
Ｙ＝Ａ％１７；
Ｘ＝Ａ／１７＋Ｃ１；
ｉｆ（Ｘ＞１５）Ｘ＝１５；
｝ｅｌｓｅ｛
Ｙ＝１７−Ａ％１７；
Ｘ＝Ａ／１７＋（１−Ｃ１）；
ｉｆ（Ｘ＞１５）Ｘ＝１５；
｝
３）Ｂアドレス生成器
この場合は、Ｂに関してパラレル処理になるため、一度に上位４ビットの２系統のアドレスを出力する。しかも、切り分けの必要がないので、４進カウンタ４の出力は入力されない。上位桁の近傍用をＸ０、上位桁の遠方用をＸ１とすると、そのアドレス生成アルゴリズムは以下のとおりである。
ｉｆ（Ａ％１７＜＝８）｛              Ｌ１
Ｙ＝Ａ％１７；                      Ｌ２
Ｘ０＝Ａ／１７；                    Ｌ３
Ｘ１＝Ａ／１７＋１；                Ｌ４
ｉｆ（Ｘ０＞１５）Ｘ０＝１５；      Ｌ５
ｉｆ（Ｘ１＞１５）Ｘ１＝１５；      Ｌ６
｝ｅｌｓｅ｛                          Ｌ７
Ｙ＝１７−Ａ％１７；                Ｌ８
Ｘ０＝Ａ／１７＋１；                Ｌ９
Ｘ１＝Ａ／１７；                    Ｌ１０
ｉｆ（Ｘ０＞１５）Ｘ０＝１５；      Ｌ１１
ｉｆ（Ｘ１＞１５）Ｘ１＝１５；      Ｌ１２
｝
上記アルゴリズムにおいて、
Ｌ１：入力Ａを１７で割った時の余り（Ａ％１７）が８以下の時、
Ｌ２：入力Ａを１７で割った時の余りをＹの値とする。
Ｌ３：入力Ａを１７で割った時の商をＸ０とする。
Ｌ４：入力Ａを１７で割ったものに１を加えたものをＸ１とする。
Ｌ５：この時において、Ｘ０が１５よりも大きくなる時は、Ｘ０の値を１５に固定する。
Ｌ６：この時において、Ｘ１が１５よりも大きくなる時は、Ｘ１の値を１５に固定する。
Ｌ７：Ｌ１の条件が満たされない時、つまりＡを１７で割った時の余りが９以上の時、
Ｌ８：１７からＡを１７で割った時の余りを引いたものをＹの値とする。
Ｌ９：入力Ａを１７で割った商に１を加えたものをＸ０の値とする。
Ｌ１０：入力Ａを１７で割った値をＸ１の値とする。
Ｌ１１：この時において、Ｘ０が１５よりも大きくなる時は、Ｘ０の値を１５に固定する。
Ｌ１２：この時において、Ｘ１が１５よりも大きくなる時は、Ｘ１の値を１５に固定する。
【００４０】
このようなアルゴリズムにより、Ｂデータが入力される度にＢアドレス生成器３の上位４ビットから２系統の値Ｘ０，Ｘ１の値が出力され、下位４ビットからＹの値が出力される。
【００４１】
このようにして発生される各アドレス生成器１〜３の出力のうち、上位データはカラーＬＵＴ１１，１２に入り、下位データは重み発生器５，６に入る。このうち、Ｂアドレス発生器３の一方の上位データは、カラーＬＵＴ１１に入り、他方の上位データはカラーＬＵＴ１２に入る。
【００４２】
ここで、重み発生器５，６の動作について詳細に説明する。重み発生器５，６には、重み係数の線対称性により、本来の１／８の容量のデータしか記憶されておらず、この１／８の容量のデータで全範囲をカバーしている。このために、各アドレス生成器１〜は以下のようにアドレスを発生する。
【００４３】
例えば重み間隔Ｍ＝１７の時には、本来の下位データを０，１，２，３，４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，１６と発生するのに対して、本発明では０，１，２，３，４，５，６，７，８，８，７，６，５，４，３，２，１と発生する。つまり、間隔Ｍの中点までアドレスを発生したら、中点からアドレスを折り返して発生する。この結果、アドレス生成器から発生される下位データは（Ｍ＋１）／２の種類となる。例えば、Ｍ＝１７の時には、
（１７＋１）／２＝９通りの値を持ち、０から８の範囲のデータを持つ。ちなみに、Ｍ＝１６の時には（１６＋１）／２＝８．５となるが、小数点は無視され、８通りの値を持つことになる。
【００４４】
同時に、下位データが格子間隔の中点より大きい場合には、上位データの出力を基準格子点に対して＋０，＋１の順ではなく、＋１，＋０の順になるように逆転して発生させる。これにより、近傍の格子点には近傍用の重み係数が与えられ、遠方の格子点には遠方用の重み係数が与えられるようになる。なお、Ｂ用のアドレス生成器３は、遠方用，近傍用の２種類のアドレスを固定で内蔵しており、入力に応じたアドレスを発生する。
【００４５】
このようなアドレスを受ける重み発生器５，６は、上記の変換されたアドレス（下位データ）に従い、表１，表２で計算される重み係数を発生する。表１は重み計算のための係数（近傍用）、表２は重み計算のための係数（遠方用）である。
【００４６】
【表１】
2006203885.tif 000004
【００４７】
【表２】
2006203885.tif 000005
【００４８】
これら表において、ｒ，ｇ，ｂは下位アドレス（アドレス生成器１〜３から発生される下位データであり、ｒはＲアドレス生成器から、ｇはＧアドレス生成器から、ｂはＢアドレス生成器から発生される）で、０〜８の値をとる。Ｃ，Ｒ，Ｇ，Ｂは重み係数を計算するための係数である。これら係数Ｃ，Ｒ，Ｇ，Ｂはｒ，ｇ，ｂの大小関係に応じて、４進カウンタ４の値に応じて、表に示すような値をとる。図２は、ｒ，ｇ，ｂの大小関係に応じて適用される三角錐を示している（図７参照）。発生すべき重み係数は、次式で表される。
【００４９】
Ｗ＝Ｍ×Ｃ＋ｒ×Ｒ＋ｇ×Ｇ＋ｂ×Ｂ                    （３）
例えば、表１の最初の組み合わせｒ＞ｇ＞ｂでは、カウンタ値＝［００］の時、発生すべき重み係数は、（３）式より
Ｗ＝４×１７＋（−４）×ｒ＋（−２）×ｇ＋（−１）×ｂ
で計算される。これから分かるように、重み係数Ｗは、整数で０〜６８の値をとり、８回の掛け合わせ（８点で補間して空間の１点の値を求めるため）の際の重み係数の総和は６８となる。
【００５０】
カラーＬＵＴ１１，１２は、前記したアドレス生成器１〜３の出力をアドレスとして受けて、アドレスに応じた値を出力する。カラーＬＵＴ１１の出力は乗算器１３に入り、カラーＬＵＴ１２の出力は乗算器１４に入る。一方、これら乗算器１３，１４の他方の入力には、前記重み発生器５，６の出力が入っている。これら乗算器１３，１４は、カラーＬＵＴの出力と重み発生器の出力を同時に乗算する。本発明によれば、同時乗算することにより、重み係数の総和が２５５以下となるため、従来の直方体の重み係数では６４ビットのＣＰＵではできなかった８点補間での３色同時処理が可能となる。これにより、演算速度を大幅に高速化することができる。
【００５１】
これら乗算器１３，１４の出力は、加算器１５に入って加算される。該加算器１５の出力は積算器１６に入って積算される。以上の動作をカウンタ４の出力である００，０１，１０，１１の４回繰り返して８点の補間演算を行なう。積算器１６はこの８点の補間演算の総和を計算する。この積算器１６で積算された値は、（結果×重み係数の総和）であるため、続く割算器１７で重み係数（この場合６８）で除算する。割算器１７からは、補間演算を行なって変換されたＲの新しいデータＲｎｅｗが出力される。
【００５２】
この場合において、割算器１７の重み係数が２のべき乗でない時（前述の６８もそうである）、割算器による割算が必要である。ところが、重み係数が２のべき乗である時には、単純にべき乗分右シフトするだけですむので、実質的に割算器は不要になる。そこで、カラーＬＵＴ１１，１２に格納するデータを予め重み係数６８で割算し、２のべき乗倍して格納しておけば、割算器１７は不要となる。なお、カラーＬＵＴにリニアなデータが保持されていれば、割算器を用いた最終結果と前記動作による最終結果とには差異は生じない。
【００５３】
以上、Ｒデータを求める場合について説明したが、Ｇデータ，Ｂデータを求める場合についても同様である。
なお、重み発生器による重み係数発生の方法は、種々の形態が考えられる。前記（３）式を全て予め行ない、その結果をＲＯＭの形で格納するか、又は実際の演算をその都度行なうか、その中間的な方法をとるかは、ハードウェアの構成に依存する。以下に実現方法をいくつか示す。
（ａ）全てＲＯＭ化する方法
図３に示すように、入力アドレスとして各色４ビットずつ１６ＫＢのＲＯＭを用いるものである。ＲＯＭには、予め計算された重み係数が格納されている。そして、ｒ，ｇ，ｂ各４ビットのアドレスとカウンタの２ビット出力を受けて、対応する番地に記憶されている７ビットの重み係数データを出力する。
（ｂ）エンコーダを利用する方法
図４はエンコーダを利用して重み係数を発生するものである。下位桁の範囲が０〜８であることに着目し、８ビット入力７ビット出力の第１のエンコーダ４１でｒ，ｇの入力に対応するデータを出力して７ビットの１個のデータにまとめる。第１のエンコーダ４１としては、例えばＬＵＴが用いられる。この第１のエンコーダ４１の出力は、０〜８０の値をとる。次に、この第１のエンコーダ４１の出力とｂ入力とを入力とする第２のエンコーダ４２でエンコードして１個のデータにまとめる。最後に、この第２のエンコーダ４２の出力とカウンタ出力を受けるＲＯＭ４３に入力して、７ビットの重み係数データを出力する。このようにエンコードを２段行ない、０〜７２８の値を出力範囲とすることにより、２段目のエンコード出力は１０ビットであるので、ＲＯＭ４３としては、４ＫＢのサイズですむ。エンコーダを用いることにより、図３に示す例では、ＲＯＭの容量が１６ＫＢであるのに比較して、ＲＯＭ容量は１／４ですむ。
（ｃ）全て計算で求める方法
この方法は、（３）式をその都度演算するものである。ＲＯＭが不要となる代わりに、演算時間がかかるので、高速化には向かない。
【００５４】
図５は本発明の他の実施例を示す構成図で、中央演算装置を用いて補間を行なうようにしたものである。この場合も、３次元補間を示す。Ｒ，Ｇ，Ｂデータを受けてアドレス発生手段５０は、６０に示すような３次元のカラーＬＵＴアドレスを発生する。カラーＬＵＴには、６１に示すようなＹ，Ｍ，Ｃ，Ｋの４種類のデータが記憶されている。ここで、補間演算における最後のシーケンスである割算をシフトのみで行なうため、カラーＬＵＴに記憶されているデータは、６４／６８倍されて記憶されている。従って、この時の最大値は２５５ではなく、２４０となる。
【００５５】
直方体の体積の最大値は１３ビット程度（Ｍ＝１７の時、１７3 ）になる。元のデータの８ビットに対して１３ビットを足すと２１ビットの計算の幅が必要となる。この場合に４色を同時に計算しようとすると極めて大きいビット数のＣＰＵが必要となる。本発明の場合は最大で７ビットであるから、８ビットと７ビットを乗算しても１６ビットを超えることがない。従って、１６×３（３色の場合）であり、６４ビットのＣＰＵを用いれば、十分に８点補間での３色同時補間が可能である。
【００５６】
Ｒ，Ｇ，Ｂ画像データがアドレス発生手段５０に入力すると、アドレス発生手段５０は、前記実施例の場合と同様に上位桁と下位桁が計算され、出力される。上位桁はカラーＬＵＴを選び、下位桁は重み係数発生手段５１に入り、重み係数を発生させる。カラーＬＵＴから読み出されたＹ，Ｍ，Ｃ，Ｋデータは、６４ビットレジスタ５２に図に示すように再配置される。
【００５７】
８回の乗算累積に必要なカラーＬＵＴデータがレジスタ５２に呼び込まれ、一方、対応する重み係数データが与えられる。この重み係数の計算は、表１，表２により与えられるもので、また、必要なカラーＬＵＴの位置は下位ビットに依存し、アドレス発生手段５０の出力により変化する。
【００５８】
ｉ番目のＬＵＴデータとｉ番目の重み係数Ｗｉが累算器（又はＡＬＵ）５３により乗算される。この乗算結果は、積算用レジスタ５４に送られる。この演算を８回行ない、積算用レジスタ５４で積算する。８回の積算が終了したら、６ビット右シフトする。これで等価的に１／６４倍されたことになる。このシフトされた変換後のデータを所定の画像フォーマットに修正するために再配置する。
【００５９】
次に、本発明の変形・応用例について説明する。
１）重み発生手段として、従来の格子点を区切る反対側の直方体の体積を用いることもできる。但し、この場合、厳密には重み係数の発生ビット数は実施例の７ビットから１３ビットに増大し、同時に乗算器，加算器等もコストの高いビット幅の広いものを使用しなくてはならなくなる。
２）重み係数が格子点に対称であることを利用して節減しない方法も可能である。但し、この場合、アドレス発生器にカウンタ入力が不要となるため、ＲＯＭで構成する場合にはメモリ容量が半分（実施例の５１２バイトから２５６バイトへ）、また計算が単純になる利点がある。しかしながら、重み発生器をＲＯＭで作成する場合、実施例では２９１６（＝９3 ×４）ワードから１９６５２（＝１７3 ×４）ワードへ増大するため、トータルのメモリ容量は増大することになる。
３）実施例では、パラレル処理とシリアル処理（時系列処理）の組み合わせで構成したが、完全なパラレル処理も、また、シリアル処理（図５の例）も可能である。
４）実施例では、Ｎ＝３、つまり３次元の補間の場合について示したが、本発明は４次元以上の場合についても同様にして容易に拡張することができる。４次元の場合、重み係数の場合分けは２４通りになる。但し、重み係数をＲＯＭで構成した時は１／１６に削減可能である。
５）中央演算装置で同時に補間演算を実行する時、一度に６４ビットで行わず、３２ビットレジスタを２回用いて行なうことも可能である。
【００６０】
以上、詳細に説明したように、本発明によれば、補間に対する重み係数の最大値を、補間間隔Ｍの時、Ｍ×２N-1で与えるようにして、重み係数の最大値を抑制するようにした。これにより、ハードウェア資源の節約を図ることができ、演算時間の高速化を図ることができる。
【００６１】
この場合において、最大重み係数が２のべき乗にならない時、カラーＬＵＴに格納するデータを予め割算し、２のべき乗倍して格納することようにした。これにより、補間演算の最後で行なう重み係数による割算が単にデータのシフト（右シフト）のみで行えることにより、演算時間を高速化することができる。。
【００６２】
また、本発明によれば、Ｎ次元の補間を行なう場合において、重み係数を、補間間隔Ｍに対して（Ｍ＋１）／２のアドレスに対して発生し、多次元補間を行なうことにより、重み係数発生用のメモリ容量を削減することができ、ハードウェア資源を節約することができる。
【００６３】
この場合において、Ｎ次元のＬＵＴの補間演算を行なうに際し、ＬＵＴの３色乃至４色の値のうち、複数の色データに対して同時に重み係数を乗算することにより、ハードウェア資源を節約し、補間演算を高速化することができる。
【００６４】
このように、本発明によれば、ハードウェア資源の節約と演算速度の高速化を図ることができる多次元補間装置を提供することができ、実用上の効果が極めて大きい。
【図面の簡単な説明】
【００６５】
【図１】本発明の一実施例を示す構成ブロック図である。
【図２】ｒ，ｇ，ｂの大小関係に応じて適用される三角錐を示す図である。
【図３】重み発生器としてＲＯＭを用いた時の構成図である。
【図４】重み発生器としてエンコーダを利用する時の構成図である。
【図５】本発明の他の実施例を示す構成図である。
【図６】立方体補間の説明図である。
【図７】三角錐補間の説明図である。
【図８】重み係数の性質の説明図である。
【符号の説明】
【００６６】
１  Ｒアドレス生成器
２  Ｇアドレス生成器
３  Ｂアドレス生成器
４  ４進カウンタ
５  重み発生器
６  重み発生器
１０  Ｒ処理部
１１  カラーＬＵＴ
１２  カラーＬＵＴ
１３  乗算器
１４  乗算器
１５  加算器
１６  積算器
１７  割算器
２０  Ｇ処理部
３０  Ｂ処理部
【図１】
2006203885.tif 000006
【図２】
2006203885.tif 000007
【図３】
2006203885.tif 000008
【図４】
2006203885.tif 000009
【図５】
2006203885.tif 000010
【図６】
2006203885.tif 000011
【図７】
2006203885.tif 000012
【図８】
2006203885.tif 000013