(57)【特許請求の範囲】
【請求項１】
Ｐビットの２進法表記で表現される入力デジタル信号を２M−１（０＜Ｍ≦Ｐ）階調のデジタル信号である正規化値に正規化する正規化方法であって、
連結手段が、入力デジタル信号の上位ＭビットをＰビットになるまで繰り返し連結する連結工程と、
判別手段が、前記入力デジタル信号と、前記連結工程での連結の結果として得られた連結信号との大小を判別する判別工程と、
正規化値決定手段が、前記判別工程での判別結果に応じて前記正規化値を決定する工程であって、前記入力デジタル信号が前記連結信号と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記正規化値とし、前記入力デジタル信号が前記連結信号より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記正規化値とする正規化値決定工程と
を備えることを特徴とする正規化方法。
【請求項２】
生成手段が、前記正規化値をＰビットになるまで繰り返し連結することにより第２の連結信号を生成する生成工程と、
小数座標決定手段が、前記入力デジタル信号から該第２の連結信号を減算した値を多次元補間演算の小数座標とする小数座標決定工程と、を更に備え、
前記正規化値決定工程で決定した正規化値を、多次元補間演算の整数座標に対応する参照値を前記小数座標決定工程で決定した小数座標に応じた重みで多次元補間演算するための整数座標とすることを特徴とする請求項１に記載の正規化方法。
【請求項３】
Ｐビットの２進法表記で表現される入力デジタル信号を２M−１（０＜Ｍ≦Ｐ）階調のデジタル信号である正規化値に正規化する正規化方法であって、
連結手段が、入力デジタル信号の上位ＭビットをＰビット以上になるまで整数Ｌ回繰り返し連結してＭ×Ｌビットの比較信号を得て、前記入力デジタル信号の上位Ｍ×Ｌ−Ｐビットを、前記入力デジタル信号の下位に連結してＭ×Ｌビットの伸張デジタル信号を得る連結工程と、
判別手段が、前記連結工程で得られた伸張デジタル信号と比較信号との大小を判別する判別工程と、
正規化値決定手段が、前記判別工程での判別結果に応じて前記正規化値を決定する工程であって、前記伸張デジタル信号が前記比較信号と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記正規化値とし、前記伸張デジタル信号が前記比較信号より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記正規化値とする正規化値決定工程と
を備えることを特徴とする正規化方法。
【請求項４】
小数座標決定手段が、前記判別工程での判別結果に応じて多次元補間演算の小数座標を決定する工程であって、前記伸張デジタル信号が前記比較信号と同等もしくは大きい場合には、前記伸張デジタル信号と前記比較信号の差を前記小数座標とし、前記伸張デジタル信号が前記比較信号より小さい場合には、１を表すＭビットの値をＬ回繰り返し連結した値から前記伸張デジタル信号と前記比較信号の差を減算した値を、前記小数座標とする小数座標決定工程を更に備え、
前記正規化値決定工程で決定した正規化値を、多次元補間演算の整数座標に対応する参照値を前記小数座標決定工程で決定した小数座標に応じた重みで多次元補間演算するための整数座標とすることを特徴とする請求項３に記載の正規化方法。
【請求項５】
Ｐビットの２進法表記で表現される入力デジタル画像信号を２M−１（０＜Ｍ≦Ｐ）階調のデジタル信号に量子化することで得られた量子化値を前記入力デジタル画像信号の色空間における整数座標とし、色空間変換のために前記整数座標に対応する参照値を前記入力デジタル画像信号の色空間における小数座標に応じた重みで多次元補間演算を行う多次元補間装置であって、
入力デジタル画像信号の上位ＭビットをＰビットになるまで繰り返し連結する連結手段と、
前記入力デジタル画像信号と、前記連結手段での連結の結果として得られた連結信号との大小を判別する判別手段と、
前記判別手段での判別の結果、前記入力デジタル画像信号が前記連結信号と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記量子化値とし、前記入力デジタル画像信号が前記連結信号より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記量子化値とする量子化値決定手段と
を備えることを特徴とする多次元補間装置。
【請求項６】
前記量子化値をＰビットになるまで繰り返し連結することにより第２の連結信号を生成する生成手段と、
前記入力デジタル画像信号から該第２の連結信号を減算した値を前記色空間における小数座標とする小数座標決定手段と
を更に備えることを特徴とする請求項５に記載の多次元補間装置。
【請求項７】
Ｐビットの２進法表記で表現される入力デジタル画像信号を２M−１（０＜Ｍ≦Ｐ）階調のデジタル信号である量子化値に量子化することで、色空間変換のための多次元補間演算を行う多次元補間装置であって、
入力デジタル画像信号の上位ＭビットをＰビット以上になるまで整数Ｌ回繰り返し連結する第１連結手段と、
前記入力デジタル画像信号の上位Ｍ×Ｌ−Ｐビットを、前記入力デジタル画像信号の下位に連結する第２連結手段と、
前記第１および第２連結手段での連結結果の大小を判別する判別手段と、
前記判別手段での判別の結果、前記第２連結手段での連結結果が前記第１連結手段での連結結果と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記量子化値とし、前記第２連結手段での連結結果が前記第１連結手段での連結結果より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記量子化値とする量子化値決定手段と
を備えることを特徴とする多次元補間装置。
【請求項８】
前記判別手段での判別の結果、前記第２連結手段での連結結果が前記第１連結手段での連結結果と同等もしくは大きい場合には、前記第１および第２連結手段での連結結果の差を色空間の小数座標とし、前記第２連結手段での連結結果が前記第１連結手段での連結結果より小さい場合には、１を表すＭビットの値を整数Ｌ回繰り返し連結した値から前記第１および第２連結手段での連結結果の差を減算した値を、色空間の小数座標とする小数座標決定手段を更に備えることを特徴とする請求項７に記載の多次元補間装置。
【請求項９】
Ｐビットの２進法表記で表現される入力デジタル画像信号を２M−１（０＜Ｍ≦Ｐ）階調のデジタル信号に量子化することで得られた量子化値を前記入力デジタル画像信号の色空間における整数座標とし、色空間変換のために前記整数座標に対応する参照値を前記入力デジタル画像信号の色空間における小数座標に応じた重みで多次元補間演算を行う多次元補間装置における多次元補間手順をコンピュータに実行させるためのプログラムであって、
入力デジタル画像信号の上位ＭビットをＰビットになるまで繰り返し連結する連結手順と、
前記入力デジタル画像信号と、前記連結手順での連結の結果として得られた連結信号との大小を判別する判別手順と、
前記判別手順での判別の結果、前記入力デジタル画像信号が前記連結信号と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記量子化値とし、前記入力デジタル画像信号が前記連結信号より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記量子化値とする量子化値決定手順とをコンピュータに実行させるためのプログラム。
【請求項１０】
Ｐビットの２進法表記で表現される入力デジタル画像信号を２M−１（０＜Ｍ≦Ｐ）階調のデジタル信号である量子化値に量子化することで、色空間変換のための多次元補間演算を行う多次元補間装置における多次元補間手順をコンピュータに実行させるためのプログラムであって、
入力デジタル画像信号の上位ＭビットをＰビット以上になるまで整数Ｌ回繰り返し連結する第１連結手順と、
前記入力デジタル画像信号の上位Ｍ×Ｌ−Ｐビットを、前記入力デジタル画像信号の下位に連結する第２連結手順と、
前記第１及び第２の連結手順での連結結果の大小を判別する判別手順と、
前記判別手順での判別の結果、前記第２連結手順での連結結果が前記第１連結手順での連結結果と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記量子化値とし、前記第２連結手順での連結結果が前記第１連結手順での連結結果より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記量子化値とする量子化値決定手順とをコンピュータに実行させるためのプログラム。
【請求項１１】
テクスチャ画像が記憶されたメモリから前記テクスチャ画像を読み出すためのＭビットのアドレスとして用いられる正規化値を求める正規化方法であって、
連結手段が、前記メモリから読み出された前記テクスチャ画像が表示される位置を表わすＰ（０＜Ｍ≦Ｐ）ビットのデジタル信号の上位ＭビットをＰビットになるまで繰り返し連結する連結工程と、
判別手段が、前記Ｐビットのデジタル信号と、前記連結工程での連結の結果として得られた連結信号との大小を判別する判別工程と、
正規化値決定手段が、前記判別工程での判別結果に応じて前記正規化値を決定する工程であって、前記Ｐビットのデジタル信号が前記連結信号と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記正規化値とし、前記Ｐビットのデジタル信号が前記連結信号より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記正規化値とする正規化値決定工程と
を備えることを特徴とする正規化方法。
【請求項１２】
テクスチャ画像が記憶されたメモリから前記テクスチャ画像を読み出すためのＭビットのアドレスとして用いられる正規化値を求める正規化方法であって、
連結手段が、前記メモリから読み出された前記テクスチャ画像が表示される位置を表わすＰ（０＜Ｍ≦Ｐ）ビットのデジタル信号の上位ＭビットをＰビット以上になるまで整数Ｌ回繰り返し連結してＭ×Ｌビットの比較信号を得て、前記Ｐビットのデジタル信号の上位Ｍ×Ｌ−Ｐビットを、前記Ｐビットのデジタル信号の下位に連結してＭ×Ｌビットの伸張デジタル信号を得る連結工程と、
判別手段が、前記連結工程で得られた伸張デジタル信号と比較信号との大小を判別する判別工程と、
正規化値決定手段が、前記判別工程での判別結果に応じて前記正規化値を決定する工程であって、前記伸張デジタル信号が前記比較信号と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記正規化値とし、前記伸張デジタル信号が前記比較信号より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記正規化値とする正規化値決定工程と
を備えることを特徴とする正規化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、正規化方法および多次元補間装置に関するものである。
【背景技術】
【０００２】
■入／出力デバイス間での色再現
近年、入力デバイスとして、スキャナ、ビデオカメラなどが普及してきている。また、出力デバイスとして、インクジェット、染料熱昇華型あるいは電子写真などの方式を用いた、各種カラープリンタが普及してきている。一般に、これらのカラー入／出力デバイスは、それぞれ固有の色空間を有している。このため、例えば、あるスキャナで得られたカラー画像をそのまま別のカラープリンタに転送して印刷しても、印刷されたカラー画像の色がスキャナによって読み取られたオリジナルのカラー画像の色と一致することはほとんどない。
【０００３】
カラー画像等に対するこのようなデバイス間での色再現性に関する問題を解決するには、入力デバイスの色空間を出力デバイスの色空間に変換する処理（以下、「色空間変換」と呼ぶ）が必要である。このため、通常、入／出力デバイス間の色再現性能を高めるために入／出力デバイスには色空間変換機能が搭載されている。
【０００４】
なお色空間変換とは、具体的には入力γ補正、輝度濃度変換、マスキング、黒生成、ＵＣＲ、出力γ補正等の一連の画像処理全体のことを指す場合と、その中の一定の処理のみを指す場合とがある。
【０００５】
また、色空間変換の方法としては、一般的には、入力デバイスの３色のデジタル画像信号を同時に参照して、出力デバイスの３色あるいは４色のデジタル画像信号に変換することが多い。
【０００６】
ここで、入力デバイスの３色とは、例えば、レッド、ブルー、グリーンの３色（以下、「ＲＧＢ」と略す）を指す。また、出力デバイスの３色とは、例えば、シアン、マゼンタ、イエローの３色を指す（以下、「ＣＭＹ」と称す）。また、出力デバイスの４色とは、例えば、シアン、マゼンタ、イエロー、ブラックの４色（以下、「ＣＭＹＫ」と称す）を指す。また電子写真方式の複写機の場合、稼働時間とともにプリンタのエンジン特性が変化するため、定期的なキャリブレーションが必要となる。このため、このような場合には、出力デバイスの４色（例えば、「ＣＭＹＫ」）から出力デバイスの４色（例えば、「ＣＭＹＫ」）への変換も必要となる。
【０００７】
■色空間変換方法の概要
上記色空間変換を実現する手段として、予め変換結果をルックアップ・テーブル（以下、「ＬＵＴ」）としてメモリに記憶しておき、入力されたデジタル画像信号に対してそのＬＵＴから変換結果を出力する方法がある。
【０００８】
このＬＵＴを用いた色空間変換方法では、ＬＵＴのメモリを削減するため補間演算を併用するのが一般的である。上記例にある、３色入力のデジタル画像信号に対する色空間変換は、三次元補間演算を用いて実現される。また、４色入力のデジタル画像信号に対する色空間変換は、四次元補間演算を用いて実現される。
【０００９】
以下、３色入力のデジタル画像信号に対して、三次元ルックアップ・テーブル（以下、「３Ｄ-ＬＵＴ」）と三次元補間演算とを併用する色空間変換について説明する。
【００１０】
■色空間変換方法の詳細
図１２に３Ｄ−ＬＵＴを用いた三次元補間演算により色空間変換を実現する機能ブロックを示す。この機能ブロックを用いることにより、入力デジタル画像信号（Ｒ，Ｇ，Ｂ）１２０５に対し、補間値Ｘ１２３５を得ることができる。
【００１１】
補間値Ｘ１２３５を取得するにあたり、まず、入力デジタル画像信号（Ｒ，Ｇ，Ｂ）１２０５はデータ分割部１２１０によって上位信号１２１５と下位信号１２１８とに分離される。３つのデジタル画像信号の上位信号１２１５を色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄと考え、三次元補間演算に使用する単位立体を選択する。
【００１２】
ここで、三次元入力の色空間（ＲＧＢ空間）を各軸方向に限定数で分割することで、該色空間が単位立体に分割された様子を図１３に示す。同図において、塗りつぶし部分は、三次元補間演算に使用するために選択された単位立体である。
【００１３】
なお、図１３の単位立体の各頂点（ＲＤ０〜ＲＤ７）に対応する色空間変換後のデータは、図１２の３Ｄ−ＬＵＴ１２２０に予め記憶されているものとする。そして、このデータを以下、参照値ＲＤ１２２５と呼ぶ（図１２記載）。
【００１４】
選択された単位立体の各頂点に対応する参照値ＲＤ１２２５が３Ｄ−ＬＵＴ１２２０から読み出されると、該参照値１２２５は、補間演算部１２３０に入力される。
【００１５】
一方、３つのデジタル画像信号の下位信号１２１８は色空間の小数座標ｆｒａｃ＿ｃｏｏｒｄと考え、三次元補間演算の重み係数（補間係数）ｇを算出するために使用する。図１２記載の機能ブロックでは小数座標ｆｒａｃ＿ｃｏｏｒｄそのものを重み係数（補間係数）ｇとしている。
【００１６】
そして、補間演算部１２３０では、参照値ＲＤ１２２５と重み係数（補間係数）ｇとの補間演算（ほとんどの場合が積和演算）により、図１２の機能ブロックの出力である補間値Ｘ１２３５が算出される。立方体補間演算の場合の補間演算式を下式に示す（図１３（ｂ）参照）。
【００１７】
【数１】
0004468270.tif 000002
【００１８】
■整数座標、小数座標、および重み係数の算出方法の概要
ここで、前述の上位信号１２１５から色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄを算出する方法と下位信号１２１８から色空間の小数座標ｆｒａｃ＿ｃｏｏｒｄ、及び重み係数（補間係数）ｇを算出する方法には、大きく分けて２種類の従来技術がある。２種類の従来技術の相違点は、図１３で示した色空間の各軸（Ｒ，Ｇ，Ｂ）上に存在する参照値ＲＤ１２２５を２M点で構成するか、２M＋１点で構成するかの違いである。
【００１９】
参照値ＲＤ１２２５を２M点で構成した場合を従来例１とし、参照値ＲＤ１０２５を２M＋１点で構成した場合を従来例２として以下で具体的に従来例を説明する。なお、話を簡単にするため、図１４（ａ）、（ｂ）に示すように三次元補間演算ではなく一次元補間演算を例にとり説明する。Ｎ次元補間演算の各入力軸それぞれについて以下で説明することが成立するため、一次元補間演算の説明で差し支えない。
【００２０】
■従来例１による算出方法（参照値を２M点で構成した場合）
まず、従来例１について図１４（ａ）を用いて説明する。従来例１の利点は、軸に沿って２M点の参照値ＲＤが配置されるためＬＵＴに格納される参照値ＲＤの総数が必ず２のべき乗の数になることである。
【００２１】
一般的にＬＵＴはメモリとして実現される。そもそもメモリはそのエントリ数が２のべき乗の数であるときに最も効率的な回路となるため、従来例１のＬＵＴはその点でハードウェア化しやすいと言え、従来例１の利点となっている。また逆に従来例１は以下のような欠点を持っている。
【００２２】
入力デジタル画像信号（Ｒ，Ｇ，Ｂ）１２０５のそれぞれが入力階調Ｐ［ｂｉｔ］のとき、入力デジタル画像信号（Ｒ，Ｇ，Ｂ）１２０５は０〜２P−１の階調を持ち、最大階調は２P−１となる。図１４（ａ）記載の入力デジタル画像信号ｄａｔａ＿ｉｎは上記入力デジタル画像信号（Ｒ，Ｇ，Ｂ）１２０５のうち１つの軸に対する入力デジタル画像信号を示す。
【００２３】
従来例１では、軸に沿って２M点の参照値ＲＤがほぼ均等に０〜２P−１の階調に配置されるため、隣接する参照値ＲＤの間隔（区間と呼ぶ）は２M−１箇所できる。当然１つの区間の長さ（区間幅Ｓ）は最大階調２P−１を区間数２M−１で除算した値となる。
【００２４】
入力デジタル画像信号ｄａｔａ＿ｉｎが図１４（ａ）に示す通り、境界値２Ｓと境界値３Ｓに間（区間番号「３」で示す）にあるなら、一次元補間演算に必要な参照点はＲＤ［２Ｓ］とＲＤ［３Ｓ］であることが理解できる。
【００２５】
このとき色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄは境界値２Ｓとなり、色空間の小数座標ｆｒａｃ＿ｃｏｏｒｄは入力デジタル画像信号ｄａｔａ＿ｉｎから境界値２Ｓを減算した値（すなわち上記除算の剰余値）となる。
【００２６】
なお、従来例１の方法では、区間数２M−１が常に奇数であるため、単純なビット操作で色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄを求めることはできない。そこで従来例１では一般的に、入力デジタル画像信号ｄａｔａ＿ｉｎを区間幅Ｓで除算して、除算結果の商を色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄとし、除算結果の剰余を小数座標ｆｒａｃ＿ｃｏｏｒｄとする。これにより、色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄと小数座標ｆｒａｃ＿ｃｏｏｒｄを算出する。
【００２７】
そのため従来例１では、補間演算に必要な色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄと小数座標ｆｒａｃ＿ｃｏｏｒｄを算出するのに除算器が必要となる。また、入力デジタル画像信号ｄａｔａ＿ｉｎのビット深度Ｐ［ｂｉｔ］と各軸の参照値ＲＤの数２Mの組み合わせによっては図１５に示すような問題点がある。
【００２８】
すなわち、最大階調２P−１を区間数２M−１で除算したときに割り切れる（剰余が‘０'の）場合、区間幅Ｓはすべての区間で等しくなる。しかし、割り切れない場合には、図１５でハッチングされた区間のように、他の区間とは区間幅Ｓが異なる区間ができてしまう。そのため、各区間の境界値と区間幅をレジスタなどの記憶手段に予め記憶し、入力デジタル画像信号ｄａｔａ＿ｉｎとすべての境界値とを比較して、その大小関係で色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄを算出する必要がある。この結果、各軸の参照値の数が増加するにつれ、当然この境界値との比較処理は演算負荷が重くなってしまう。
【００２９】
■従来例２による算出方法（参照値を２M＋１点で構成した場合）
次に従来例２について図１４（ｂ）を用いて説明する。従来例２の利点は、補間演算に必要な色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄと小数座標ｆｒａｃ＿ｃｏｏｒｄとを算出するのに、前述の従来例１のように除算器が必要にならない点にある。また、従来例１と違い、入力デジタル画像信号ｄａｔａ＿ｉｎとすべての境界値とを比較する処理を行う必要がない点にある。
【００３０】
図１４（ｂ）に示す通り、従来例２では軸に沿って２M＋１点の参照値ＲＤが均等に０〜２P−１の階調に配置される。このため、隣接する参照値ＲＤの間隔（区間）は２M箇所となる。当然１つの区間の長さ（区間幅Ｓ）は最大階調２P−１を区間数２Mで除算した値となる。しかし、入力デジタル画像信号をＰ−Ｍビットだけ右にシフト演算するだけで色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄを求めることができる。このとき色空間の小数座標ｆｒａｃ＿ｃｏｏｒｄは入力デジタル画像信号の下位Ｐ−Ｍビットとなる。
【００３１】
ただし、従来例２における色空間の小数座標ｆｒａｃ＿ｃｏｏｒｄの算出には注意が必要である。最大階調が２Pではなく２P−１であるため、最初「１」から「２M−１」番目の区間では、区間幅Ｓが２P-Mとなる。そして、小数座標ｆｒａｃ＿ｃｏｏｒｄの階調が２P-M階調となる。しかし、最後の「２M」番目の区間では、区間幅Ｓが２P-M−１となり、小数座標ｆｒａｃ＿ｃｏｏｒｄの階調は２P-M−１階調となってしまう。
【００３２】
そのため、最後の「２M」番目の区間では小数座標ｆｒａｃ＿ｃｏｏｒｄを２P-M／（２P-M−１）倍して他の区間に揃える必要がある。また、従来例２では、軸に沿って２M＋１点の参照値ＲＤが配置されるため、ＬＵＴに格納される参照値ＲＤの総数が必ず２のべき乗の数にならない。そのため従来例１と違いＬＵＴをメモリで構成する場合、ＬＵＴは効率的な回路とならない。
【００３３】
なおＮ次元補間装置では、参照値ＲＤの総数が入力デジタル画像信号の次元数Ｎの増加に伴ってＬＵＴの回路規模は指数的に増加するので、各軸に必要となる参照値ＲＤの数はなるべく少ない方が望ましい。参照値ＲＤの総数は従来例１が（２M）Nとなるのに対し、従来例２は（２M＋１）Nとなる。このため、従来例１に比べ従来例２はＬＵＴの回路規模が大きくなってしまう。また、従来例１は従来例２のように単純なビットシフト演算でなく除算器が必要となるが、３次元補間装置や４次元補間装置ではメモリで構成するＬＵＴの回路規模が装置全体の回路規模の大半を占めている。このため、演算内容は複雑であるが従来例１の方が回路規模は小さくなる。
【特許文献１】特開平８−２０２５３３号公報
【特許文献２】特開２００４−２５２６１６号公報
【発明の開示】
【発明が解決しようとする課題】
【００３４】
以上、説明してきたように従来例１および従来例２はともに相反する利点と欠点とを持っている。このため、ＬＵＴの回路規模を小さくしたい場合には、従来例１により多次元補間装置を実現し、演算処理を簡略化したい場合には、従来例２により多次元補間装置を実現しているのが実状である。このため、従来例１と従来例２の両方の利点を併せ持った多次元補間装置の実現が望まれている。
【００３５】
本発明は、このような事情に鑑みてなされたもので、従来例１と従来例２の下記利点を併せ持つ多次元補間装置および多次元補間方法を提供することを目的とするものである。
・Ｎ次元補間演算において参照値の総数が（２M）N点となりＬＵＴがメモリを用いて効率的にハードウェア化することが可能。
・色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄと小数座標ｆｒａｃ＿ｃｏｏｒｄを算出するときに、除算器や剰余器を用いることなく単純なビットシフト演算と加減演算のみで算出可能。
・重み係数（補間係数）ｇを近似演算により除算器を用いることなく単純なビットシフト演算と加減演算のみで算出可能。
【課題を解決するための手段】
【００３６】
上記の目的を達成するために本発明に係る正規化方法は、例えば、以下のような構成を備える。即ち、
Ｐビットの２進法表記で表現される入力デジタル信号を２M−１（０＜Ｍ≦Ｐ）階調のデジタル信号である正規化値に正規化する正規化方法であって、
連結手段が、入力デジタル信号の上位ＭビットをＰビットになるまで繰り返し連結する連結工程と、
判別手段が、前記入力デジタル信号と、前記連結工程での連結の結果として得られた連結信号との大小を判別する判別工程と、
正規化値決定手段が、前記判別工程での判別結果に応じて前記正規化値を決定する工程であって、前記入力デジタル信号が前記連結信号と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記正規化値とし、前記入力デジタル信号が前記連結信号より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記正規化値とする正規化値決定工程とを備える。
上記の目的を達成するために本発明に係る多次元補間装置は、例えば、以下のような構成を備える。即ち、
Ｐビットの２進法表記で表現される入力デジタル画像信号を２M−１（０＜Ｍ≦Ｐ）階調のデジタル信号に量子化することで得られた量子化値を前記入力デジタル画像信号の色空間における整数座標とし、色空間変換のために前記整数座標に対応する参照値を前記入力デジタル画像信号の色空間における小数座標に応じた重みで多次元補間演算を行う多次元補間装置であって、
入力デジタル画像信号の上位ＭビットをＰビットになるまで繰り返し連結する連結手段と、
前記入力デジタル画像信号と、前記連結手段での連結の結果として得られた連結信号との大小を判別する判別手段と、
前記判別手段での判別の結果、前記入力デジタル画像信号が前記連結信号と同等もしくは大きい場合には、前記上位Ｍビットが示す値を前記量子化値とし、前記入力デジタル画像信号が前記連結信号より小さい場合には、前記上位Ｍビットが示す値から１を差し引いた値を前記量子化値とする量子化値決定手段とを備える。
【発明の効果】
【００３７】
本発明によれば、従来例１と従来例２の下記利点を併せ持つ多次元補間装置および多次元補間方法を提供することが可能となる。
・Ｎ次元補間演算において参照値の総数が（２M）N点となりＬＵＴがメモリを用いて効率的にハードウェア化することが可能。
・色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄと小数座標ｆｒａｃ＿ｃｏｏｒｄを算出するときに、除算器や剰余器を用いることなく単純なビットシフト演算と加減演算のみで算出可能。
・重み係数（補間係数）ｇを近似演算により除算器を用いることなく単純なビットシフト演算と加減演算のみで算出可能。
【発明を実施するための最良の形態】
【００３８】
以下、必要に応じて添付図面を参照しながら本発明の実施形態を詳細に説明する。
【００３９】
［実施形態１］
＜カラー複写機の構成＞
図１に、本発明の一実施形態にかかる多次元補間装置を備えるカラー複写機の全体構成例を示す。画像読み取り部１２０は、ＣＣＤセンサ１２４、アナログ信号処理部１２６等により構成され、レンズ１２２を介しＣＣＤセンサ１２４に結像された原稿１００の画像が、ＣＣＤセンサ１２４によりＲ、Ｇ、Ｂのアナログ電気信号に変換される。
【００４０】
変換された画像は、アナログ信号処理部１２６に入力され、Ｒ、Ｇ、Ｂの各色毎に補正等が行われた後に、アナログ・デジタル変換（Ａ／Ｄ変換）される。デジタル化されたフルカラー信号（以下、デジタル画像信号という）は、画像処理部１３０に入力される。
【００４１】
画像処理部１３０ではデジタル画像信号に対し、入力γ補正、色空間変換、濃度補正、スクリーン処理を施し、プリンタ部１４０へ処理後のデジタル画像信号を出力する。プリンタ部１４０は、例えば、レーザ等からなる露光制御部（図示せず）、画像形成部（図示せず）、転写紙の搬送制御部（図示せず）等により構成され、入力されたデジタル画像信号により転写紙上に画像を記録する。
【００４２】
また、ＣＰＵ回路部１１０は、演算制御用のＣＰＵ１１２、固定データやプログラムを格納するＲＯＭ１１４、データの一時保存やプログラムのロードに使用されるＲＡＭ１１６等により構成される。そして、画像読み取り部１２０、画像処理部１３０、プリンタ部１４０等を制御し、カラー複写機のシーケンスを統括的に制御する。外部記憶装置１１８は、カラー複写機が使用するパラメータやプログラムを記憶するディスク等の媒体であり、ＲＡＭ１１６のデータやプログラム等は、外部記憶装置１１８からロードされる構成としても構わない。
【００４３】
なお、上述のカラー複写機において、本発明の一実施形態にかかる多次元補間装置は、画像処理部１３０の一機能として実現され、色空間変換を実行するものとする。以下、図２を用いて多次元補間装置の回路構成と処理の流れについて詳しく説明する。
【００４４】
＜多次元補間装置の回路構成ならびに全体処理の流れ＞
図２は、本実施形態にかかる多次元補間装置の回路構成ならびに処理の流れを説明するための図である。本実施形態にかかる多次元補間装置はＮ次元の入力デジタル画像信号に対し補間演算を行い、補間値として新たな信号を出力する。
【００４５】
まず、デジタル画像信号２０５が多次元補間装置２００に入力される。このデジタル画像信号２０５はＮ次元の信号である。デジタル画像信号２０５はデータ分割部２１０で整数座標信号２１２と小数座標信号２１４とに分割される。デジタル画像信号２０５がＮ次元の信号であるため、データ分割後の整数座標信号２１２と小数座標信号２１４はともにＮ本の信号となる。
【００４６】
一般的に整数座標信号２１２は、補間演算のときに使用される単位立体の個数に応じてそのビット深度が決定される。たとえば、Ｎ次元空間のある軸について単位立体が２M−１個ある場合、その軸に対応する整数座標信号２１２のビット深度はＭビットとなる。
【００４７】
また、一般的に小数座標信号２１４は、デジタル画像信号２０５のビット深度から整数座標信号２１２のビット深度を差し引いた、残りのビット深度で表現されるが、本実施形態では後述するように予め定められた内部演算精度まで拡張される。このため、内部演算精度Ｗビットと等しくなる。
【００４８】
参照座標選択部２２０は補間演算に必要となる参照値２５２を多次元ＬＵＴ２６０から読み出すための座標を決定し、参照座標信号２２２として出力する。また同様に重み係数算出部２４０は小数座標信号２１４をもとに補間演算の重み係数（補間係数）信号２４２を算出して補間演算部２７０に出力する。
【００４９】
なお、小数座標信号２１４から重み係数（補間係数）２４２を算出する方法については後述する。また、参照値読み出し部２５０は参照座標信号２２２を用いて多次元ＬＵＴ２６０から必要な個数の参照値を読み出して参照値信号２５２として出力する。
【００５０】
多次元ＬＵＴ２６０は複数個のサブメモリで実現されており、参照値読み出し部２５０はサブメモリの個数と等しい本数のアドレス信号２５４を各サブメモリに出力し、各サブメモリをアクセスし、各サブメモリからデータ信号２６２を受け取る。補間演算部２７０は必要な個数の参照値信号２５２と重み係数信号２４２とを受けて、予め定められた補間演算を行い、１本の出力信号２７５（補間値）を出力する。
【００５１】
＜データ分割部２１０および重み係数算出部２４０における処理の流れ＞
図３は、本実施形態にかかる多次元補間装置のデータ分割部２１０と重み係数算出部２４０の処理の流れを示すフローチャートである。図３の“ｐｒｅｐａｒａｔｉｏｎ”処理と“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理は補間演算に必要な色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄと小数座標ｆｒａｃ＿ｃｏｏｒｄとを算出する処理である。
【００５２】
また、図３の“ｃｏｒｒｅｃｔｉｏｎ”処理（ステップＳ３０４）は前記小数座標ｆｒａｃ＿ｃｏｏｒｄを正規化して重み係数（補間係数）ｇを算出する処理である。図３のフローチャートより明らかなように、“ｐｒｅｐａｒａｔｉｏｎ”処理、“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理、“ｃｏｒｒｅｃｔｉｏｎ”処理の一連の処理が入力デジタル画像信号の次元数分（Ｎ回）実行される（ステップＳ３０１、Ｓ３０５）。
【００５３】
ハードウェア化する場合は、上記一連の処理に相当する数（Ｎセット）のハードウェアをＮセット実装することで容易に並列化させることが可能であり、本発明の方法がＮ次元の多次元補間装置に容易に拡張できることがわかる。上記一連の処理について以下で詳細に説明する。
【００５４】
図４の４０１は“ｐｒｅｐａｒａｔｉｏｎ”処理（ステップＳ３０２）の具体的な処理内容を示す説明図である。図中‘［ｉ］'はＮ次元の入力デジタル画像信号のうちｉ番目の信号を示す。
【００５５】
まず、入力階調Ｐビットの入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]の上位Ｍビットを抜き出し、繰り返し信号ｒｐｂ[ｉ]とする（図４の４０１の工程（Ａ））。
【００５６】
次に、Ｍビットの繰り返し信号ｒｐｂ[ｉ]をＰビットになるまでＬ回繰り返し（Ｌは整数）、連結する。このとき繰り返し信号ｒｐｂ［ｉ］をＬ回繰り返してできた信号はＬ×Ｍビットとなるが、この信号がＰビットより大きいならば、Ｌ×Ｍ−Ｐビットは切り捨てられる。このようにして生成された信号を比較信号ｂｏｕｎｄａｒｙ[ｉ]とする（図４の４０１の工程（Ｂ））。
【００５７】
また、工程（Ｂ）と同様の処理を繰り返し信号ｒｐｂ［ｉ］から１だけ減算した信号についても行い、比較信号ｂｏｕｎｄａｒｙ＿ｍ[ｉ]とする（図４の４０１の工程（Ｂ’））。
【００５８】
さらに、工程（Ｂ）と同様の処理を繰り返し信号ｒｐｂ［ｉ］から１だけ加算した信号についても行い、比較信号ｂｏｕｎｄａｒｙ＿ｐ[ｉ]とする（図４の４０１の工程（Ｂ”））。
【００５９】
図４の４０２に上記処理について具体的な数値を代入した一例を示す。参照値の数が２3の場合、入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]の上位３ビットが抜き出される。入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]のビット深度１０ビットより長くなるためには、４回繰り返す必要があるので、抜き出した上位３ビット値が‘０１１'のとき、４回連結された信号は‘０１１  ０１１  ０１１  ０１１'となる。
【００６０】
このとき下位２ビットは余分であるため除外され、比較信号ｂｏｕｎｄａｒｙ[ｉ]は‘０１１  ０１１  ０１１  ０'となる。また、繰り返し信号ｒｐｂ［ｉ］から１だけ減算した信号は‘０１０'となるため、ｂｏｕｎｄａｒｙ＿ｍ［ｉ］は‘０１０  ０１０  ０１０  ０'となる。さらに、繰り返し信号ｒｐｂ［ｉ］から１だけ加算した信号は‘１００'となるため、ｂｏｕｎｄａｒｙ＿ｐ[ｉ]は‘１００  １００  １００  １'となる。
【００６１】
次に、図５を用いて“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理（ステップＳ３０３）の具体的な処理内容について説明する。なお、“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理（ステップＳ３０３）の概要を説明するための模式図を図６に示す。
【００６２】
色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄ[ｉ]と小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]とを算出するにあたっては、“ｐｒｅｐａｒａｔｉｏｎ”処理（ステップＳ３０２）で算出した繰り返し信号ｒｐｂ[ｉ]、ｒｐｂ[ｉ]−1、ｒｐｂ[ｉ]＋１を使用する。また、あわせて比較信号ｂｏｕｎｄａｒｙ[ｉ]、ｂｏｕｎｄａｒｙ＿ｍ[ｉ]、ｂｏｕｎｄａｒｙ＿ｐ[ｉ]と入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]を使用する。
【００６３】
図６の左から右に向く矢印は図１４と同様に入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]の大きさを示しており、左から右に進むにつれて入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]は大きくなる。図６には‘ｒｐｂ[ｉ]−１’、‘ｒｐｂ[ｉ]’、‘ｒｐｂ[ｉ]＋１’の３つの量子化値が記載され、その量子化値に挟まれる２つの区間が存在する。
【００６４】
それぞれの量子化値に対応する境界値が比較信号ｂｏｕｎｄａｒｙ[ｉ]、ｂｏｕｎｄａｒｙ＿ｍ[ｉ]、ｂｏｕｎｄａｒｙ＿ｐ[ｉ]となる。入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]がｂｏｕｎｄａｒｙ[ｉ]と同等もしくは大きい場合（ステップＳ５０１→Ｓ５０２で「ＮＯ」の場合）、ステップＳ５０４に進む。その結果、図６の（ａ）に示すように色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄ[ｉ]はｒｐｂ[ｉ]となる。
【００６５】
そして、入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]から比較信号ｂｏｕｎｄａｒｙ[ｉ]を減算した値が色空間の小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]となる。また、比較信号ｂｏｕｎｄａｒｙ＿ｐ[ｉ]から比較信号ｂｏｕｎｄａｒｙ[ｉ]を減算した値が区間幅ｓｅｃｔｉｏｎ[ｉ]となる。
【００６６】
逆に入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]がｂｏｕｎｄａｒｙ[ｉ]より小さい場合（ステップＳ５０１→Ｓ５０２で「ＹＥＳ」の場合）、ステップＳ５０３に進む。その結果、図６の（ｂ）に示すように、色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄ[ｉ]は‘ｒｐｂ［ｉ］−１'の値となる。
【００６７】
そして、色空間の小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]は入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]からｂｏｕｎｄａｒｙ＿ｍ[ｉ]を減算した値となる。また、比較信号ｂｏｕｎｄａｒｙ[ｉ]から比較信号ｂｏｕｎｄａｒｙ＿ｍ[ｉ]を減算した値が区間幅ｓｅｃｔｉｏｎ[ｉ]となる。
【００６８】
以上説明したように本実施形態にかかる多次元補間装置によれば、色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄ[ｉ]と小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]を算出するにあたり、除算器や剰余器を使用する必要がない。
【００６９】
また、従来例１のように最大階調２P−１を区間数２M−１で除算したときに割り切れない場合（図１５でハッチングされた区間のように他の区間と区間幅Ｓが異なる区間が発生するような場合）であっても、対応可能である。すなわち、区間幅ｓｅｃｔｉｏｎ[ｉ]を容易に求めることができる。したがって、従来例１のように、各区間の境界値と区間幅を予め記憶し、入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]とすべての境界値とを比較して、その大小関係で色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄ[ｉ]を算出する処理を行う必要がない。
【００７０】
［第２の実施形態］
上記第１の実施形態の場合、２種類の区間幅を持つ条件が存在していた。このため、重み係数（補間係数）ｇを求めるにあたり、“ｃｏｒｒｅｃｔｉｏｎ”処理（ステップＳ３０４）にて小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]を区間幅ｓｅｃｔｉｏｎ[ｉ]で除算しなければならなかった。つまり、任意の入力階調Ｐビットと任意のＭに対して対応しようとすると、重み係数算出部には除算器を配する必要があった。
【００７１】
しかし、最大階調２P−１を区間数２M−1で除算したときに割り切れる場合は、区間幅ｓｅｃｔｉｏｎ[ｉ]はどの区間でも同じ値に統一される。このため、近似式を用いることにより上記除算器を使用しないようにすることが可能である。そこで本実施形態では、近似式を用いた手法について説明する。
【００７２】
図７の７０１に本実施形態の“ｐｒｅｐａｒａｔｉｏｎ”処理（ステップＳ３０２）の具体的な処理内容を示す。まず、入力階調Ｐビットの入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]の上位Ｍビットを抜き出し、繰り返し信号ｒｐｂ[ｉ]とする（図７の７０１の工程（Ａ））。
【００７３】
次に、Ｍビットの繰り返し信号ｒｐｂ[ｉ]をＰビット以上になるまでＬ回繰り返し（Ｌは整数）、連結する。このとき繰り返し信号ｒｐｂ［ｉ］をＬ回繰り返してできた信号はＬ×Ｍビットとなる（このビット深度をｂｗ[ｉ]とする）。
【００７４】
このようにして生成された信号を比較信号ｂｏｕｎｄａｒｙ[ｉ]とする（図７の７０１の工程（Ｂ））。なお、上記第１の実施形態と異なり、繰り返し信号ｒｐｂ[ｉ]をＬ回繰り返し連結することによりできたＬ×Ｍビットの信号がＰビットより大きくとも、Ｌ×Ｍ−Ｐビットは切り捨てない。
【００７５】
次に、“１”を示すＭビットの信号（ＬＳＢのみ１であるＭビットの信号）を図７の７０１の工程（Ｂ）と同じ回数（Ｌ回）だけ繰り返し連結することにより、Ｌ×Ｍビットの区間幅信号ｓｅｃｔｉｏｎ[ｉ]を生成する（図７の７０１の工程（Ｃ）の工程）。
【００７６】
最後に入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]をＬ×Ｍ−Ｐビットだけ伸張して比較信号ｂｏｕｎｄａｒｙ[ｉ]と同じビット深度にする。
【００７７】
入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]の上位Ｌ×Ｍ−Ｐビットを抜き出し、入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]の下位に連結してｅｘ＿ｄａｔａ[ｉ]とする（図７の７０１の工程（Ｄ））。
【００７８】
図７の７０２に上記処理について具体的な数値を代入した一例を示す。参照値の数が２3の場合、入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]の上位３ビットが抜き出される。入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]のビット深度１０ビットより長くなるためには、４回繰り返す必要がある。つまり、抜き出した上位３ビット値が‘０１１'のとき、４回連結された信号は‘０１１  ０１１  ０１１  ０１１'となり、この信号が比較信号ｂｏｕｎｄａｒｙ[ｉ]となる。
【００７９】
‘１'を示す３ビットの値‘００１'が同様に４回繰り返して連結され‘００１  ００１  ００１  ００１'となり、区間幅信号ｓｅｃｔｉｏｎ[ｉ]となる。
【００８０】
入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]は比較信号ｂｏｕｎｄａｒｙ[ｉ]のビット深度より２ビットだけ小さい。そこで、これを補填するために入力デジタル画像信号ｄａｔａ＿ｉｎ[ｉ]の上位２ビットの値‘１０'を下位に連結して１２ビットの伸張された入力デジタル画像信号ｅｘ＿ｄａｔａ[ｉ]とする。
【００８１】
次に図８を用いて本実施形態の“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理（ステップＳ３０３）の具体的な処理内容について説明する。なお、“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理（ステップＳ３０３）の処理を説明するための模式図を図９に示す。色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄ[ｉ]と小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]を算出するにあたっては、“ｐｅｒｅｐａｒａｔｉｏｎ”処理（ステップＳ３０２）で算出した繰り返し信号ｒｐｂ[ｉ]を使用する。また、あわせて比較信号ｂｏｕｎｄａｒｙ[ｉ]と区間幅信号ｓｅｃｔｉｏｎ[ｉ]、伸張された入力デジタル画像信号ｅｘ＿ｄａｔａ[ｉ]を使用する。
【００８２】
図９には‘ｒｐｂ[ｉ]−１'、‘ｒｐｂ[ｉ]'、‘ｒｐｂ[ｉ]＋１'の３つの量子化値が記載され、その量子化値に挟まれる２つの区間が存在する。それぞれの量子化値に対応する境界値が比較信号ｂｏｕｎｄａｒｙ[ｉ]、ｂｏｕｎｄａｒｙ＿ｍ[ｉ]、ｂｏｕｎｄａｒｙ＿ｐ[ｉ]となるのは上記第１の実施形態と同様である。
【００８３】
伸張された入力デジタル画像信号ｅｘ＿ｄａｔａ[ｉ]がｂｏｕｎｄａｒｙ[ｉ]と同等もしくは大きい場合（ステップＳ８０１→Ｓ８０２で「ＮＯ」の場合、ステップＳ８０４に進む。その結果、図９の（ａ）に示すように色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄ[ｉ]はｒｐｂ[ｉ]となる。入力デジタル画像信号ｅｘ＿ｄａｔａ[ｉ]から比較信号ｂｏｕｎｄａｒｙ[ｉ]を減算した値（図８の‘ｔｍｐ'）が色空間の小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]となる。
【００８４】
逆に入力デジタル画像信号ｅｘ＿ｄａｔａ[ｉ]がｂｏｕｎｄａｒｙ[ｉ]より小さい場合（ステップＳ８０１→Ｓ８０２で「ＹＥＳ」の場合）、ステップＳ８０３に進む。その結果、図９（ｂ）に示すように、色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄ[ｉ]は‘ｒｐｂ［ｉ］−１'となる。このとき色空間の小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]は区間幅ｓｅｃｔｉｏｎ[ｉ]から、伸張された入力デジタル画像信号ｅｘ＿ｄａｔａ[ｉ]から比較信号ｂｏｕｎｄａｒｙ[ｉ]を減算した値（図８の‘ｔｍｐ'）を減算して求めることができる。
【００８５】
このとき比較信号ｂｏｕｎｄａｒｙ[ｉ]はＭビットの整数倍なので、最大階調２M*L−１を区間数２M−1で除算したときに必ず割り切れ、区間幅ｓｅｃｔｉｏｎ[ｉ]はどの区間でも同じ値であり、Ｍ値によって定まる固定値となる。上記第１の実施形態のように‘ｒｐｂ［ｉ］−１'、‘ｒｐｂ［ｉ］＋１'の境界値を求める必要はない。
【００８６】
以上の説明から明らかなように、本実施形態にかかる多次元補間装置によれば、色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄ[ｉ]と小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]を算出するにあたり除算器や剰余器を使用する必要がない。また、最大階調２M*L−１を区間数２M−1で除算したとき必ず割り切れ、図１５でハッチングされた区間のように他の区間と区間幅Ｓが異なる区間が決して発生しない。
【００８７】
なお、本実施形態においても、“ｃｏｒｒｅｃｔｉｏｎ”処理（ステップＳ３０４）にて小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]を区間幅ｓｅｃｔｉｏｎ[ｉ]で除算し、除算結果より重み係数（補間係数）ｇを求めなければならない。しかし、区間幅ｓｅｃｔｉｏｎ[ｉ]が固定値であるため上記除算を近似することが可能である。以下、“ｃｏｒｒｅｃｔｉｏｎ”処理（ステップＳ３０４）について説明する。
【００８８】
図１０（ａ）に３次元補間演算における単位直方体を示す。入力デジタル画像信号Ｒ、Ｇ、Ｂのそれぞれの信号が各２MR、２MG、２MB点の参照値を各軸に持っている場合、参照値の総数は、２(MR+MG+MB)となる。
【００８９】
このとき図１３（ａ）に示した単位立体は、ＭＲ＝ＭＧ＝ＭＢのとき立方体となるが、ＭＲ＝ＭＧ＝ＭＢでないときは直方体となる。以下では、Ｒ、Ｇ、Ｂの識別をｉで表現している。補間演算を正しく行うためには、区間幅ｓｅｃｔｉｏｎ[ｉ]によって小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]を除算して、各軸の小数座標ｆｒａｃ＿ｃｏｏｒｄ[ｉ]を図１０（ｂ）のように正規化した値ｇ[ｉ]にする必要がある。
【００９０】
最大階調は“ｐｒｅｐａｒａｔｉｏｎ”処理（ステップＳ３０２）で算出した比較信号のビット深度ｂｗ[ｉ]から２bw[i]−１となるため、区間幅ｓｅｃｔｉｏｎ[ｉ]は（２bw[i]−１）／（２Mi−１）となる。下式に示すようにｇ[ｉ]の式に（２bw[i]−１）／（２Mi−１）を代入して展開する。そしてビットシフト演算と減算演算によって計算できるＦＴＭＰを下式に示すように定めると、ｇ［ｉ］は以下のようになる。
【００９１】
【数２】
0004468270.tif 000003
【００９２】
比較信号のビット深度ｂｗ[ｉ]は各軸によって異なるため統一しなければ正規化できない。そこで最も大きいｂｗ[ｉ]以上の数値Ｗを正規化のためのビット深度とし、各軸の重み係数（補間係数）ｇをＷビットの精度に変換する。これにより補間演算の内部演算精度はＷビットとなる。
【００９３】
ｂｗ[ｉ]が十分大きい場合、下式に示すような近似が可能となり、ビットシフト演算と加減演算のみで正規化演算が実現できる。
【００９４】
【数３】
0004468270.tif 000004
【００９５】
なお、上式記載のＷビットだけ右シフトする演算処理は、演算精度を保証するために、図１２の補間演算部１２３０の中で式１を一例とする補間演算を行った最後に行われる。そのため本実施形態の“ｃｏｒｒｅｃｔｉｏｎ”処理（ステップＳ３０４）の演算内容は、下式となる。
【００９６】
【数４】
0004468270.tif 000005
【００９７】
図１１に本実施形態のデータ分割部と重み係数算出部をハードウェア化したときの回路例を示す。
【００９８】
本実施形態では、任意の入力階調Ｐビットと任意のＭに対して上記近似によって除算器を使用することなく多次元補間演算を行うことが可能である。
【００９９】
以上説明したように、本実施形態によれば、Ｎ次元補間演算において参照値ＲＤの総数が（２M）N点となりＬＵＴがメモリを用いて効率的にハードウェア化できる。また、色空間の整数座標ｉｎｔｇ＿ｃｏｏｒｄと小数座標ｆｒａｃ＿ｃｏｏｒｄを算出するときに除算器や剰余器を用いることなく単純なビットシフト演算と加減演算のみで算出できる。
【０１００】
また、任意の入力階調Ｐビットと任意のＭに対してＮ次元に拡張可能である。このように本実施形態では、ＬＵＴを構成する記憶手段においても、補間演算のための演算手段においても、回路規模が小さい多次元補間装置を提供することができる。
【０１０１】
また、本実施形態にかかる多次元補間装置は、任意の入力階調Ｐビットと任意のＭに対してすべての境界値をレジスタなどの記憶手段に予め記憶することとした。このため、入力デジタル画像信号とすべての境界値とを比較することなく、整数座標ｉｎｔｇ＿ｃｏｏｒｄを算出することが可能となった。さらに、入力デジタル画像信号をＭの倍数のビット深度に伸張することで、小数点以下の桁まで考慮し、必ず均等な２M−１区間に入力デジタル画像信号を量子化して整数座標ｉｎｔｇ＿ｃｏｏｒｄを算出することが可能となった。
【０１０２】
［他の実施形態］
なお、本発明はディスプレイの表示面の矩形領域Ａ−Ｂ（斜線部）に２の冪乗の大きさのテクスチャ画像を表示する場合にも適用することが可能である。以下、図１６を用いて説明する。通常グラフィック・システムでは、ＣＰＵから矩形領域Ａ−Ｂ（斜線部）の頂点である、点Ａと点Ｂの座標を入力し、レンダラＬＳＩ（レンダリング・ハードウェア）が矩形領域Ａ−Ｂを構成する画素をラスタライズにより生成する。次に、生成した各画素に対応するテクスチャ画像をメモリから参照して、ディスプレイの表示面に表示するカラー値とし、表示面に描画する。
【０１０３】
本発明を用いることで、メモリ上のテクスチャ画像から参照するカラー値を容易に読み出すことができる。まず、以下の式のように、２P-1に対する比率Δｘ、Δｙを求め、Δｘ、ΔｙをＰビット値で表現する。
【０１０４】
【数５】
0004468270.tif 000006
【０１０５】
このデジタル信号Δｘ（Δｙ）の上位Ｍビットを抜き出し、該抜き出したＭビットをＰビットになるまで繰り返し連結することによりＰビットの比較信号を生成し、前記デジタル信号Δｘ（Δｙ）と前記比較信号との大小関係を判別し、前記デジタル信号Δｘ（Δｙ）が前記比較信号と同等もしくは大きい場合には、前記抜き出したＭビットが示す値を正規化値とし、前記デジタル信号Δｘ（Δｙ）が前記比較信号より小さい場合には前記抜き出したＭビットが示す値から１を差し引いた値を正規化値とする。
【０１０６】
もしくは、このデジタル信号Δｘ（Δｙ）の上位Ｍビットを抜き出し、該抜き出したＭビットをＰビット以上になるまでＬ回繰り返し（Ｌは整数）、連結してＭ×Ｌビットの比較信号を生成し、前記デジタル信号Δｘ（Δｙ）の上位Ｍ×Ｌ−Ｐビットを抜き出し、前記デジタル信号Δｘ（Δｙ）の下位に連結することにより、前記デジタル信号Δｘ（Δｙ）をＭ×Ｌビットに伸張し、前記伸張後のデジタル信号Δｘ（Δｙ）と前記比較信号との大小関係を判別し、前記伸張後のデジタル信号Δｘ（Δｙ）が前記比較信号と同等もしくは大きい場合には、前記抜き出したＭビットが示す値を正規化とし、前記伸張後のデジタル信号Δｘ（Δｙ）が前記比較信号より小さい場合には、前記抜き出したＭビットが示す値から１を差し引いた値を正規化とする。
【０１０７】
上記過程で算出した正規化値は、テクスチャ画像から参照する、カラー値（テクスチャ画素値）を指し示すテクスチャ座標を表しており、前記正規化値に従ってメモリのテクスチャ画像を読み出しディスプレイの表示面に描画すればよい。
【０１０８】
以上のように、本発明の正規化方法は色空間変換に利用するだけでなく、メモリ上の２のべき乗の大きさをもつテクスチャ画像を参照するために正規化されたテクスチャ座標を算出する目的でも利用可能である。つまり本発明により、メモリ上に蓄積されたデータのエントリ数が２のべき乗個であれば、入力デジタル信号を正規化してメモリから参照するための正規化されたエントリ番号に変換し、入力デジタル信号に応じたデータを参照することができる。
【０１０９】
なお、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給するよう構成することによっても達成されることはいうまでもない。この場合、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することにより、上記機能が実現されることとなる。なお、この場合、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【０１１０】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピ（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。
【０１１１】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現される場合に限られない。例えば、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１１２】
さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、前述した実施形態の機能が実現される場合も含まれる。つまり、プログラムコードがメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって実現される場合も含まれる。
【図面の簡単な説明】
【０１１３】
【図１】カラー複写機の全体構成例を示すブロック図である。
【図２】本発明の一実施形態にかかる多次元補間装置の回路構成を示すブロック図である。
【図３】本発明の一実施形態にかかる多次元補間装置のデータ分割部と重み係数算出部の処理を示すフローチャートである。
【図４】本発明の第１の実施形態にかかる多次元補間装置における“ｐｒｅｐａｒａｔｉｏｎ”処理の説明図である。
【図５】本発明の第１の実施形態にかかる多次元補間装置における“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理を示すフローチャートである。
【図６】本発明の第１の実施形態にかかる多次元補間装置における“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理の説明図である。
【図７】本発明の第１の実施形態にかかる多次元補間装置における“ｐｒｅｐａｒａｔｉｏｎ”処理の説明図である。
【図８】本発明の第２の実施形態にかかる多次元補間装置における“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理を示すフローチャートである。
【図９】本発明の第２の実施形態にかかる多次元補間装置における“ｃｌａｓｓｉｆｉｃａｔｉｏｎ”処理の説明図である。
【図１０】各軸の参照点数が異なるときの正規化を示す説明図である。
【図１１】本発明の第２の実施形態にかかる多次元補間装置におけるデータ分割部と重み係数算出部の回路例を示す図である。
【図１２】３Ｄ−ＬＵＴを用いて三次元補間演算を行うときの機能ブロック図である。
【図１３】三次元入力の色空間（ＲＧＢ空間）を各軸方向に限定数で単位立体に分割した状態を示す図と選択された単位立体を示す図である。
【図１４】従来例１及び従来例２の多次元補間装置の説明図である。
【図１５】従来例１の区間幅を示す図である。
【図１６】他の実施形態にかかるテクスチャマッピングの説明図である。
【図１】
0004468270.tif 000007
【図２】
0004468270.tif 000008
【図３】
0004468270.tif 000009
【図４】
0004468270.tif 000010
【図５】
0004468270.tif 000011
【図６】
0004468270.tif 000012
【図７】
0004468270.tif 000013
【図８】
0004468270.tif 000014
【図９】
0004468270.tif 000015
【図１０】
0004468270.tif 000016
【図１１】
0004468270.tif 000017
【図１２】
0004468270.tif 000018
【図１３】
0004468270.tif 000019
【図１４】
0004468270.tif 000020
【図１５】
0004468270.tif 000021
【図１６】
0004468270.tif 000022