(57)【要約】【課題】  LUTと補間演算を用いた色変換装置において、小さな回路規模で高精度名補間を実現する。【解決手段】  入力値の値域を２n単位の間隔で領域分割し、入力値と入力値の含まれる領域の開始値の差分Δを入力値の含まれる領域のサイズで割った比率を求める際に、領域サイズが２nの場合は、Δ÷２nを計算し、計算領域サイズが２n−１の場合は、Δ÷（２n−１）を計算する代わりにΔ÷２n×(1 + 1/２n)によって近似計算する近似計算手段と、前記近似計算手段によって出力された比率の値を入力の次元数分用いて補間演算で使用する補間頂点を選択する補間頂点選択手段と、前記補間頂点選択手段によって得られた選択情報と前記近似計算手段によって出力された比率の値を用いて補間係数を計算する補間係数計算手段とを有する。【選択図】  図１
2006173828.tif 000002
【特許請求の範囲】
【請求項１】
入力値の値域を２n単位の間隔で領域分割し、入力値と入力値の含まれる領域の開始値の差分Δを入力値の含まれる領域のサイズで割った比率を求める際に、領域サイズが２nの場合は、Δ÷２nを計算し、計算領域サイズが２n−１の場合は、Δ÷（２n−１）を計算する代わりにΔ÷２n×(1 + 1/２n)によって近似計算する近似計算手段と、前記近似計算手段によって出力された比率の値を入力の次元数分用いて補間演算で使用する補間頂点を選択する補間頂点選択手段と、多次元入力値が前記分割方法により分割した領域のどの領域に含まれているかを求め、前記補間頂点選択手段によって選択された補間頂点の情報をもとに多次元ルックアップテーブルの参照を行うルックアップテーブル参照手段と、前記補間頂点選択手段によって得られた選択情報と前記近似計算手段によって出力された比率の値を用いて補間係数を計算する補間係数計算手段と、前記ルックアップテーブル参照手段によって得られた補間頂点に対応する出力値と前記補間係数計算手段によって得られた補間係数によって補間演算を実行する補間演算手段とを有することを特徴とする色変換装置。
【請求項２】
前記近似計算手段は、入力値の含まれる領域のサイズが２n−１であるかどうかを判定するための領域位置比較手段と、前記領域位置比較手段の判定結果を元に領域サイズが２nの領域では値0を選択し、領域サイズが２n−１の領域では入力値の下位ビットを選択して出力する選択手段とからなり、前記近似計算手段の出力は入力値の下位ビットと前記選択手段の出力を結合した値であることを特徴とする請求項1記載の色変換装置。
【請求項３】
各次元の入力値が入力値の値域の最大値である場合には、前記Δを入力値の含まれる領域のサイズで割った比率を0に設定するように前記近似計算手段に指示するとともに、前記ルックアップテーブル参照手段に対して、各次元の入力値の最大値に対応する格子位置を基準の頂点とすることを指示する最大値検出手段を有することを特徴とする請求項1または請求項２記載の色変換装置。
【請求項４】
各次元の入力値が入力値の値域の最大値である場合には、前記Δを入力値の含まれる領域のサイズで割った比率を１に設定するように前記近似計算手段に指示する最大値検出手段を有することを特徴とする請求項1または請求項２記載の色変換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データの色変換装置に関するものである。
【背景技術】
【０００２】
プリンタによる画像出力等、画像を扱う様々なシステムにおいて、画像に対する色変換処理が必要となる。色変換処理に対する入力と出力が比較的単純な関係にある場合、マトリクス演算を用いたマスキング処理によって色変換を行うことも可能であるが、一般的には、色変換の入力と出力の関係を単純なマトリクス演算で精度良く近似できるとは限らない。このような場合、3次元ルックアップテーブル(以下、略す場合はLUTと示す)と補間演算（例えば、四面体補間等の多面体補間演算）を用いた色変換方式が用いられることが多い。
【０００３】
ここで、3次元LUTと補間演算を用いた色変換方式の概念について、図3、図4、図5を用いて説明する。
【０００４】
図3は、3次元の入力値の値域を格子状に分割した状態を示す図であり、分割された立方体（あるいは直方体）の各頂点に対応する出力値が、3次元ＬＵＴに格納されている。ある3次元の入力値が与えられた場合、まず、その入力値を含む立方体（あるいは直方体）が選択される。
【０００５】
図4は、その選択された立方体（あるいは直方体）と、入力値に対応する点Pを示した図であり、説明上、各頂点の名前をP000〜P111とする。また、Ｐの座標値（＝入力値）を(x, y, z)、原点に最も近い頂点P000の座標値を(x0,y0,z0)、原点から最も遠い頂点P111の座標値を(x1,y1,z1)とし、入力値Pの原点に最も近い頂点P000からの変位を(Δx,Δy,Δz)とし、各次元における辺の長さに対する前記変位の比率を(Rx, Ry, Rz)とすると、次の式が成り立つ。
【０００６】
Δx = x − x0、Rx = Δx / (x1 − x0) = (x − x0) / (x1 − x0) ... (1)
Δy = y − y0、Ry = Δy / (y1 − y0) = (y − y0) / (y1 − y0) ... (2)
Δz = z − z0、Rx = Δx / (z1 − z0) = (z − z0) / (z1 − z0) ... (3)
点Ｐに対応する出力値は、3次元ＬＵＴを参照して得られる各頂点に対応する出力値と前記座標値によって計算される係数値から、補間演算によって計算される。ここで、補間演算の方式によって、補間に使用される頂点の個数や頂点の選択方法、係数の計算方法は異なっている。
【０００７】
図5は、四面体補間を用いた場合の補間演算を説明する図である。四面体補間は、P000〜P111の中から選択された４つの頂点に対応する出力値を用いて、入力に対する出力値を補間する方式であり、図5では、Rx ＞ Ry ＞ Rｚのときに使用される４つの頂点P000,P100,P110, P111を黒丸で示し、これら４つの頂点を結んでできる四面体を実線で示している。入力値Pは、この四面体の中に含まれており、これも黒丸で示されている。
【０００８】
Ｐに対応する出力値をＶ，頂点P000〜P111に対応する出力値をＶ000〜Ｖ111とすると、この場合のVは次式で計算される。
【０００９】
Ｖ＝(1 − Rx)・V000 + (Rx − Ry)・V100 + (Ry − Rz)・V110 + Rz・V111 ... (4)
図５には1通りしか示していないが、Rx, Ry, Rzの値の大小関係によって、6通りの四面体の選び方が存在し、Rx ＞ Ry ＞ Rｚのとき以外については、次の式で計算を行う。
【００１０】
Rx ＞ Rz ≧ Ryのとき：
Ｖ＝(1 − Rx)・V000 + (Rx − Rz)・V100 + (Rz − Ry)・V101 + Ry・V111 ... (5)
Rz ≧ Rx ＞ Ryのとき：
Ｖ＝(1 − Rz)・V000 + (Rz − Rx)・V001 + (Rx − Ry)・V101 + Ry・V111 ... (6)
Rz ≧ Ry ≧ Rxのとき：
Ｖ＝(1 − Rz)・V000 + (Rz − Ry)・V001 + (Ry − Rx)・V011 + Rx・V111 ... (7)
Ry ＞ Rz ≧ Rxのとき：
Ｖ＝(1 − Ry)・V000 + (Ry − Rz)・V010 + (Rz − Rx)・V011 + Rx・V111 ... (8)
Ry ≧ Rx ＞ Rzのとき：
Ｖ＝(1 − Ry)・V000 + (Ry − Rx)・V010 + (Rx − Rz)・V110 + Rz・V111 ... (9)
次に、3次元ＬＵＴと補間演算を用いた色変換装置の構成例について、図2を用いて説明する。図2は、8ビット3次元の入力値に対して、各次元を16分割して得られる17x17x17要素の3次元ＬＵＴを用いて、出力値を求めるための構成例であり、まず、入力値101, 102, 103は、上位4ビットと下位4ビットに分割される。上位4ビットは、入力の値域を16の倍数を区切りに16分割したときに入力値がどの領域に含まれるかを示しており、下位4ビットは、入力値の含まれる領域において原点に近い頂点からの変位(Δx, Δy, Δz)を示している。ここで、16の倍数を区切りに格子分割がなされているため、Rx, Ry, Rzは次の式で計算できる。
【００１１】
Rx = Δx / 16 = xの下位4ビット / 16 ... (10)
Ry = Δy / 16 = yの下位4ビット / 16 ... (11)
Rz = Δz / 16 = zの下位4ビット / 16 ... (12)
3次元入力値の下位4ビットは補間頂点選択回路108に入力され、下位4ビットの値の大小関係（Rx,Ry,Rzの大小関係と等しい）から、補間に使用する４頂点を選択し、3次元ＬＵＴ参照回路107に指示するとともに、6通りの頂点の選択肢からどの場合が選択されたかを示す情報と、Rx,Ry,Rzの値を補間係数計算回路111に対して出力する。
【００１２】
3次元ＬＵＴ参照回路107は、入力値の上位4ビットから、入力値がどの立方体に含まれるか、すなわち頂点P000の位置を知り、さらに補間頂点選択回路108からどの頂点を補間に使用するかを指示されて、補間に使用する4頂点に対応するテーブルアドレスを生成して、3次元ＬＵＴを参照する。格子点出力値109は、3次元ＬＵＴ参照回路107によって得られた、4頂点に対応する出力値である。
【００１３】
補間係数計算回路111は、補間頂点選択回路108から出力された情報をもとに、式(4)〜(9)のいずれの補間計算式を用いるかを判断し、各頂点の値Ｖ000〜Ｖ111に掛ける係数値を計算して、補間演算回路110に出力する。
【００１４】
補間演算回路110は、4頂点に対応する格子点出力値109各々に対し、補間係数計算回路111によって計算された各係数をそれぞれ掛けた上で加算し、出力のビット精度に合わせて丸め、あるいは切捨てを行って、最終的に、入力値Pに対応する出力値112を出力する。
【００１５】
なお、図2において、出力値については1次元分しか示していないが、複数次元の出力値が必要な場合は、図2の構成を複数並列に用いるか、あるいは、複数回繰り返しで用いることで複数次元の出力値が得られる。
【００１６】
以上の図2の説明では、処理を簡単にするため、入力値の値域を分割して得られる立方体の各辺の長さが全て16であるものとしているが、実際には、入力値の値域0〜255を16の倍数を区切りに分割していくと、図６に示すように、最後の分割領域だけは、立方体（あるいは直方体）の辺の長さが15になってしまう。従って、入力の全ての値に対して、式(10)〜(12)が成り立つわけではなく、入力の値に応じて、次に示すように2通りの計算式を使い分ける必要があり、入力の下位4ビットに対し、1/16を計算するだけで済んでいた前記場合よりも演算量や回路規模が増えてしまう。
【００１７】
Rx = Δx / 16 あるいは Δx / 15 ... (13)
Ry = Δy / 16 あるいは Δy / 15 ... (14)
Rz = Δz / 16 あるいは Δz / 15 ... (15)
そこで、特許文献１に提示された従来の技術では、入力値に対して式(13)〜(15)の値を保持したテーブルを予め作成しておき、実際の色変換処理時には、このテーブルを参照して、補間頂点の選択や補間係数の計算を行うことで、演算量を減らしている。
【特許文献１】特開２０００−２２９７３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１８】
まず、図2の説明のように、式(10)〜(12)を使って計算を行う従来技術では、1辺の長さが15となる最後の分割領域(入力値＝240〜255)において、誤差が発生し、補間精度が落ちてしまう。
【００１９】
次に、式(13)〜(15)の通り計算を行う従来技術では、補間精度の問題は無いが、15による除算が行われるため、除算器が必要で回路規模が大きくなってしまう。
【００２０】
また、特開2000-22973に提示された従来の技術では、予め除算を行った結果をテーブルに格納しておくため、除算器は不要であるが、入力値の値域に対応するだけのテーブルが必要であるため、ハードウェア実装時には使用するメモリが増えてしまう。
【００２１】
本発明は、これらの課題、すなわち、回路規模は小さいが補間精度が落ちる、あるいは補間精度は良いが回路規模が大きくなる、という課題を解決するためのものである。
【課題を解決するための手段】
【００２２】
上記課題を解決するために、本発明の色変換装置は、入力値の値域を２n単位の間隔で領域分割し、入力値と入力値の含まれる領域の開始値の差分Δを入力値の含まれる領域のサイズで割った比率を求める際に、領域サイズが２nの場合は、Δ÷２nを計算し、計算領域サイズが２n−１の場合は、Δ÷（２n−１）を計算する代わりにΔ÷２n×(1 + 1/２n)によって近似計算する近似計算手段と、前記近似計算手段によって出力された比率の値を入力の次元数分用いて補間演算で使用する補間頂点を選択する補間頂点選択手段と、多次元入力値が前記分割方法により分割した領域のどの領域に含まれているかを求め、前記補間頂点選択手段によって選択された補間頂点の情報をもとに多次元ルックアップテーブルの参照を行うルックアップテーブル参照手段と、前記補間頂点選択手段によって得られた選択情報と前記近似計算手段によって出力された比率の値を用いて補間係数を計算する補間係数計算手段と、前記ルックアップテーブル参照手段によって得られた補間頂点に対応する出力値と前記補間係数計算手段によって得られた補間係数によって補間演算を実行する補間演算手段とを有することを特徴とする。
【発明の効果】
【００２３】
本発明によれば、3次元LUTと補間演算を用いた色変換装置において、小さな回路規模で、かつ、格子分割の最終分割位置における補間精度を落とすことなく色変換を行うことができる。
【発明を実施するための最良の形態】
【００２４】
（第1の実施の形態）
本発明の第1の実施の形態の色変換装置について、図１を用いて説明する。
【００２５】
なお、説明の都合上、入力値は各要素8ビット（値域０〜２５５）の3次元とし、格子分割は１６の倍数を区切りになされているものとする。従って、3次元ルックアップテーブルは１７ｘ１７ｘ１７の要素からなっている。
【００２６】
図1において、8ビットの入力値101〜103は、近似回路104〜106によって変換され、Rx, Ry, Rzに相当する８ビットの出力値として出力される。近似回路104〜106は、式(13)〜(15)に相当する演算を行うが、15による除算をそのまま実行すると回路規模が大きくなってしまうため、次の近似・式変形により、処理を簡略化する。
【００２７】
Rx = Δx / 15 = Δx / 16 * (16 / 15) 
≒Δx / 16 * (17 / 16) = Δx / 16 * (1 + 1/16) = Δx / 16 + (Δx / 16) / 16
＝ Δx /16 + (Δx / 16の４ビット右シフト) ... (17)
Ｒy = Δy / 15 ≒ Δy/16 + (Δy/16の４ビット右シフト) ... (18)
Ｒz = Δz / 15 ≒ Δz/16 + (Δz/16の４ビット右シフト) ... (19)
式(17)〜(19)において、Δx,Δy,Δzは4ビットなので、各式の第1項と第2項の有効ビット範囲は重ならず、単に、第1項と第2項のビットを結合するだけで実際に加算を行う必要は無い。
【００２８】
以上をまとめると、近似回路104〜106の動作は次の式で表される。
【００２９】
Rx = Δx / 16 (0≦x＜240のとき), 
Δx /16 + (Δx / 16の４ビット右シフト) (240≦x≦255のとき) ... (20)
Ry = Δy / 16 (0≦y＜240のとき), 
Δy /16 + (Δy / 16の４ビット右シフト) (240≦y≦255のとき) ... (21)
Rz = Δz / 16 (0≦z＜240のとき), 
Δz /16 + (Δz / 16の４ビット右シフト) (240≦z≦255のとき) ... (22)
近似回路104〜106によって式(20)〜(22)の計算を行って得られた出力値は、Rx, Ry, Rzに相当しているため、補間頂点選択回路108に送られ、以下、Rx, Ry,Rzのビット精度が8ビットと多い（下位4ビットが増加）ことを除いて、図2の説明と全く同様に、補間頂点選択回路108、3次元ＬＵＴ参照回路107および、補間係数計算回路111、補間演算回路110によって処理が行われる。
【００３０】
次に、式(20)を実際に計算する近似回路の例を図７に示す。式(21),(22)については、式(20)と使用する変数が異なるだけなので、全く同じ回路で実現可能である。
【００３１】
近似回路701は、8ビット入力値802を式(20)により変換して、8ビット近似出力値705を得る。近似出力値705は、最上位ビットの上に小数点が位置する固定小数点フォーマットであり、値域としては、0〜255/256までの値を表現可能である。
【００３２】
入力値702は、まず上位4ビットと下位4ビットに分割され、上位ビットは15との比較回路703に送られる。15との比較回路703は、入力値xの値が240(=16×15)以上かどうかを判定するための回路で、判定結果は、選択回路704に送られる。
【００３３】
入力値702の下位4ビットは、近似出力値705の上位4ビットにそのまま出力されると共に、選択回路704の一方の入力に入力される。選択回路704のもう一方の入力には値0が入力されており、選択回路704は比較回路703の比較結果に応じて、入力値が240未満の場合は値0の側を、240以上の場合は入力値の下位4ビットの側を出力し、近似出力値705の下位4ビットにその値が設定される。
このように、比較回路703と選択回路704が動作することにより、式(20)の計算が実現できる。
【００３４】
以上、図1、図７を使って説明した第1の実施の形態により、式(13)〜(15)を計算するために除算器を使う従来技術やテーブルを使う従来技術のように回路規模を大きく増やすことなく、また、単純に式(10)〜(12)を使用する従来技術のように補間精度を落とすことなく、精度の維持と小さな回路規模を両立できる。
【００３５】
なお、ここでは、説明の都合上、特定のビット精度をあげて説明したが、任意のビット精度に対して、本発明を適用することが可能である。
【００３６】
また、格子分割方法についても、説明であげた例に限定されるものではなく、分割の間隔が２nと２n−１の混在になるような分割方法であれば、本発明が適用可能であり、例えば、入力の各次元に対して、異なる間隔で分割を行ったとしても、前記条件が満たされていればよい。
【００３７】
また、説明上、四面体補間をとりあげて説明したが、Rx, Ry, Rzの値をもとに補間を行う方式であれば、他の補間方式を使用する場合にも本発明を適用できる。
【００３８】
（第2の実施の形態）
本発明の第2の実施の形態は、第1の実施の形態に対して、各次元の入力値が最大値をとる場合を検出するための最大値検出回路を追加し、最大値検出回路が最大値を検出した場合に、近似回路と3次元ＬＵＴ参照回路に特別な処理を行うよう指示するものである。
【００３９】
最大値検出回路は、入力される各次元の入力値を入力の最大値（8ビット入力時は255）と比較し、入力値が最大値と一致した場合には、一致情報を対応する次元の近似回路と3次元ＬＵＴ参照回路に伝える。
【００４０】
一致情報を受け取った近似回路は、第1の実施の形態で本来出力する値（前記例では255/256）の代わりに0を出力する。
【００４１】
また、一致情報を受け取った3次元ＬＵＴ参照回路は、対応する次元の入力値が格子分割されたどこの領域に含まれるか判定する際に、最後の領域(前記例では240から始まる領域)
ではなく、最後の領域より一つ後ろの仮想的な領域（前記例では255から始まる領域）に含まれるものとして、ＬＵＴ参照アドレスの計算を行う。例えば、各次元を16分割した場合の領域番号を入力値0の側から、0、１、２、...、１５と名づけたとすると、通常、本来なら最後の領域番号１５を用いるところを、領域番号１６を用いてアドレス計算を行うことになる。
【００４２】
以上の構成により、入力値が最大値（前記例では、255,255,255）を取る場合には、必ず3次元ＬＵＴの最後の要素の値が補間演算による補正を受けずにそのまま出力される、という動作を行うようになる。
【００４３】
この第2の実施の形態は、入力値の色空間がRGBで、白色入力値(R=G=B=255)を必ず白色に対応する出力値として出力したい場合に適しており、3次元ＬＵＴの最後の要素の値として、白色に対応する出力値を設定するだけで、この条件を満たすことができる。
【００４４】
（第３の実施の形態）
本発明の第３の実施の形態は、第2の実施の形態と同様に、ＲＧＢ白色入力値を必ず白色に対応する出力値として出力したい場合に適している。
【００４５】
本発明の第３の実施の形態は、第1の実施の形態に対して、各次元の入力値が最大値をとる場合を検出するための最大値検出回路を追加し、最大値検出回路が最大値を検出した場合に、近似回路に特別な処理を行うよう指示するものである。
【００４６】
最大値検出回路は、入力される各次元の入力値を入力の最大値（8ビット入力時は255）と比較し、入力値が最大値と一致した場合には、一致情報を対応する次元の近似回路に伝える。
【００４７】
一致情報を受け取った近似回路は、第1の実施の形態で本来出力する値（前記例では255/256）の代わりに１(=256/256)を出力する。
【００４８】
以上の構成により、入力値が最大値（前記例では、255,255,255）を取る場合には、必ず3次元ＬＵＴの最後の要素の値が補間演算による補正を受けずにそのまま出力される、という動作を行うようになる。
【図面の簡単な説明】
【００４９】
【図１】第1の実施例の構成図。
【図２】従来技術の構成図。
【図３】3次元LUTの説明図。
【図４】入力値と入力値を含む立方体（あるいは直方体）の説明図。
【図５】四面体補間の説明図。
【図６】16の倍数を区切りとした格子分割の説明図。
【図７】近似回路の説明図。
【図１】
2006173828.tif 000003
【図２】
2006173828.tif 000004
【図３】
2006173828.tif 000005
【図４】
2006173828.tif 000006
【図５】
2006173828.tif 000007
【図６】
2006173828.tif 000008
【図７】
2006173828.tif 000009