(57)【要約】【課題】本発明は３次元ルックアップテーブルと４面体補間によるデータ変換に適した命令を使用する。これによって、特開２０００ー１９６９０３の方法を補完し、入力データを所定の位置に配置する手段においても条件分岐命令を必要としないような、ソフトウェアによるデータ変換方法と装置を提供するものである。このようなデータ変換はたとえば、ＲＧＢ色空間からＣＭＹＫ色空間への変換に利用できる。【解決手段】本発明による方法では、マイクロプロセッサに３個の入力値を比較するための命令を用意する。３個の整数値の入力から、そのうちの最大値、中央値、最小値を得る命令を使用することで、４面体補間に必要な情報を簡単に求めることができるようになる。【選択図】        図１
2004341765.tif 000002
【特許請求の範囲】
【請求項１】
３次元ルックアップテーブル（以下ＬＵＴ）を参照し、ソフトウェアによる４面体補間処理によって３次元ベクトルの入力値に対して出力値を求めるデータ変換方法で、入力値の各要素についてＬＵＴの参照点との距離を比較するために３値の大小関係を比較する命令を使用することを特徴とする方法。
【請求項２】
請求項１のデータ変換方法で、請求項１の命令が、３値の大小比較に加えて、補間のための重み係数を算出する機能を有することを特徴とする方法。
【請求項３】
請求項１ないし請求項２の命令を有することを特徴とするマイクロプロセッサ。
【請求項４】
３次元ルックアップテーブル（以下ＬＵＴ）を参照し、４面体補間処理によって３次元ベクトルの入力値に対して出力値を求めるデータ変換手段として、請求項３のマイクロプロセッサを有することを特徴とするデータ変換装置。
【請求項５】
３次元ルックアップテーブル（以下ＬＵＴ）を参照し、４面体補間処理によって３次元ベクトルの入力値に対して出力値を求める請求項３のマイクロプロセッサのソフトウェアを記録した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
３次元ベクトルの入力に対してルックアップテーブル（以下ＬＵＴ）と４面体補間を適用して出力値を求めるデータ変換方法、たとえばＲＧＢ色空間からＣＭＹＫ色空間への変換方法などに関する。
【０００２】
【従来の技術】
特開平５−１４１４８９ではＬＵＴを用いたデータ変換装置が提案されている。また、特開２０００−１９６９０３ではソフトウェアによる高速な変換方法が提案されている。
【０００３】
【発明が解決しようとする課題】
特開２０００−１９６９０３では、大小関係によって決まる所定の位置に配置することで、以後の条件分岐処理を必要としない処理方法が提案されているが、前提である入力データを所定の位置に配置する手段が必要である。ソフトウェアによる処理では、従来は図３のように、場合分けのための条件分岐命令を使用する方法が一般的であった。
【０００４】
一般にソフトウェアの処理では条件分岐命令の実行は比較的時間がかかるので、条件分岐命令を使用せずに補間に必要な情報を生成することが望ましい。
【０００５】
本発明は３次元ルックアップテーブルと４面体補間によるデータ変換に適した命令を使用する。これによって、特開２０００−１９６９０３の方法を補完し、入力データを所定の位置に配置する手段においても条件分岐命令を必要としないような、ソフトウェアによるデータ変換方法と装置を提供するものである。このようなデータ変換はたとえば、ＲＧＢ色空間からＣＭＹＫ色空間への変換に利用できる。
【０００６】
近年では機器の小型化と省電力化に対応するために、特定用途向けの命令追加が可能なプロセッサが提供されている。こうしたプロセッサを利用すれば比較的簡単に本発明で利用する命令を持つプロセッサを得ることができる。
【０００７】
【課題を解決するための手段】
本発明による方法では、マイクロプロセッサに３個の入力値を比較するための命令を用意する。３個の整数値の入力から、そのうちの最大値、中央値、最小値を得る命令を使用することで、４面体補間に必要な情報を簡単に求めることができるようになる。
【０００８】
【発明の実施の形態】
本発明の第１実施例として、図１のように入力値に対して、区間幅が入力値の要素ごと、また、区間ごとに異なる可変間隔の格子点における値を格納したＬＵＴを使用した４面体補間を以下に示す。まず、ここで用いる４面体補間の手順は以下に説明する。
【０００９】
最初に、入力値Ｘ，Ｙ，Ｚが何番目の区間に属するかを求め、それぞれＸｈ，Ｙｈ，Ｚｈとし、おのおのの区間幅をＭＸ（Ｘｈ），ＭＹ（Ｙｈ），ＭＺ（Ｚｈ）、区間開始点をＮＸ（Ｘｈ），ＮＹ（Ｙｈ），ＮＺ（Ｚｈ）とする。
【００１０】
次に、各軸上で区間開始点からの距離Ｘ−ＮＸ（Ｘｈ），Ｙ−ＮＹ（Ｙｈ），Ｚ−ＮＺ（Ｚｈ）それぞれの、区間幅ＭＸ（Ｘｈ），ＭＹ（Ｙｈ），ＭＺ（Ｚｈ）に対する割合Ｘｆ，Ｙｆ，Ｚｆを求める。
【００１１】
Ｘｆ＝（Ｘ−ＮＸ（Ｘｈ））／ＭＸ（Ｘｈ）…（１−１）
Ｙｆ＝（Ｙ−ＮＹ（Ｙｈ））／ＭＹ（Ｙｈ）…（１−２）
Ｚｆ＝（Ｚ−ＮＺ（Ｚｈ））／ＭＺ（Ｚｈ）…（１−３）
図２は図１の一部分を拡大したものであり、図２に示すとおり入力値に対応する点Ｐ（Ｘ，Ｙ，Ｚ）は、８個の頂点Ａ（ＮＸ（Ｘｈ），ＮＹ（Ｙｈ），ＮＺ（Ｚｈ）），Ｂ（ＮＸ（Ｘｈ＋１），ＮＹ（Ｙｈ），ＮＺ（Ｚｈ）），Ｃ（ＮＸ（Ｘｈ），ＮＹ（Ｙｈ＋１），ＮＺ（Ｚｈ）），Ｄ（ＮＸ（Ｘｈ＋１），ＮＹ（Ｙｈ＋１），ＮＺ（Ｚｈ）），Ｅ（ＮＸ（Ｘｈ），ＮＹ（Ｙｈ），ＮＺ（Ｚｈ＋１）），Ｆ（ＮＸ（Ｘｈ＋１），ＮＹ（Ｙｈ），ＮＺ（Ｚｈ＋１）），Ｇ（ＮＸ（Ｘｈ），ＮＹ（Ｙｈ＋１），ＮＺ（Ｚｈ＋１）），Ｈ（ＮＸ（Ｘｈ＋１），ＮＹ（Ｙｈ＋１），ＮＺ（Ｚｈ＋１））からなる立方体ＡＢＣＤＥＦＧＨ（境界を含む）の内部に存在することになる。
【００１２】
また、立方体ＡＢＣＤＥＦＧＨは、４面体ＡＢＤＨ，ＡＢＦＨ，ＡＣＤＨ，ＡＣＧＨ，ＡＥＦＨ，ＡＥＧＨのように６個の４面体に分割することが可能である。
【００１３】
点Ｐがどの４面体に属するかは余りＸｆ，Ｙｆ，Ｚｆの大小関係によって決まり、そのときの補間式は以下のようになる。式中でＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈは各頂点におけるＬＵＴのデータ、Ｐは補間演算結果を表す。なお、等号が成立する場合は、条件を満たす式すべてで同じ結果になるので、それらのうちから任意の式を選んでよい。
【００１４】
Ｘｆ≧Ｙｆ≧Ｚｆの場合、
2004341765.tif 000003
Ｘｆ≧Ｚｆ≧Ｙｆの場合、
2004341765.tif 000004
Ｚｆ≧Ｘｆ≧Ｙｆの場合、
2004341765.tif 000005
Ｚｆ≧Ｙｆ≧Ｘｆの場合、
2004341765.tif 000006
Ｙｆ≧Ｚｆ≧Ｘｆの場合、
2004341765.tif 000007
Ｙｆ≧Ｘｆ≧Ｚｆの場合、
2004341765.tif 000008
ここで、Ｘｆ，Ｙｆ，Ｚｆの最大値をｍａｘ，中央値をｍｅｄ，最小値をｍｉｎとおくと、式１−４ないし式１−９は以下のようにまとめることが可能である。
【００１５】
2004341765.tif 000009
ただし、頂点ＱはＸｆ，Ｙｆ，Ｚｆのうちどの値が最大値かによって以下のように決まるものとする。
【００１６】
Ｘｆが最大値の場合、Ｑ＝Ｂ
Ｙｆが最大値の場合、Ｑ＝Ｃ
Ｚｆが最大値の場合、Ｑ＝Ｅ
また、頂点ＲはＸｆ，Ｙｆ，Ｚｆのうちどの値が最小値かによって以下のように決まるものとする。
【００１７】
Ｘｆが最小値の場合、Ｒ＝Ｇ
Ｙｆが最小値の場合、Ｒ＝Ｆ
Ｚｆが最小値の場合、Ｒ＝Ｄ
最大値が複数同値の場合にはＱの係数（ｍａｘ−ｍｅｄ）が０となるので、同値のうちどれを最大値とみなしても結果には影響しない。同様に、最小値が複数同値の場合にはＲの係数（ｍｅｄ−ｍｉｎ）が０となるので、同値のうちどれを最小値とみなしても結果には影響しない。
【００１８】
本実施例では除算を避けるために、Ｘｆ，Ｙｆ，Ｚｆのかわりに区間幅ＭＸ（Ｘｈ）とＭＹ（Ｙｈ）とＭＺ（Ｚｈ）との積ｄｅｎｏｍを分母としたときの分子の値Ｘｆｎ，Ｙｆｎ，Ｚｆｎの大小関係を比較する。すなわち、
Ｘｆｎ＝（Ｘ−ＮＸ（Ｘｈ））・ＦＹ（Ｙｈ）・ＦＺ（Ｚｈ）…（１−１１）
Ｙｆｎ＝（Ｙ−ＮＹ（Ｙｈ））・ＦＸ（Ｘｈ）・ＦＺ（Ｚｈ）…（１−１２）
Ｚｆｎ＝（Ｚ−ＮＺ（Ｚｈ））・ＦＸ（Ｘｈ）・ＦＹ（Ｙｈ）…（１−１３）
この場合、Ｘｆｎ，Ｙｆｎ，Ｚｆｎの最大値、中央値、最小値であるｍａｘ，ｍｅｄ，ｍｉｎもｄｅｎｏｍを分母とした分子の値となるので、式１−１０は次のようになる。
【００１９】
2004341765.tif 000010
式１−１４を整理すると次式（１−１５）になる。
【００２０】
2004341765.tif 000011
図４はこのような４面体補間処理の流れ図である。このうちステップＳ４０３で本発明に特徴的な命令を使用している。
【００２１】
ステップＳ４０１では、一般に知られた分類アルゴリズムを利用して入力値Ｘ，Ｙ，Ｚがどの区間に属するかを求める。ＳＥＣＴＩＯＮＸ（ｘ），ＳＥＣＴＩＯＮＹ（ｙ），ＳＥＣＴＩＯＮＺ（ｚ）はｘ，ｙ，ｚがそれぞれ何番目の区間に属するかを表すものとする。このような分類アルゴリズムとしては、ハッシュ法、２分探索法などがある。
【００２２】
ステップＳ４０２では、各軸上で入力値の区間開始点からの距離Ｘ−ＮＸ（Ｘｈ），Ｙ−ＮＹ（Ｙｈ），Ｚ−ＮＺ（Ｚｈ）が、区間幅ＭＸ（Ｘｈ），ＭＹ（Ｙｈ），ＭＺ（Ｚｈ）に占める割合を求めている。ここでは除算を避けるために、区間幅ＭＸ（Ｘｈ）とＭＹ（Ｙｈ）とＭＺ（Ｚｈ）との積を分母としたときの分子の値を区間割合Ｘｆｎ，Ｙｆｎ，Ｚｆｎとしている。
【００２３】
ステップＳ４０３からステップＳ４０５までが従来例のステップＳ３０１に相当する部分である。
【００２４】
ステップＳ４０３では、Ｃｏｍｐａｒｅ３という命令を使用して、Ｘｆｎ，Ｙｆｎ，Ｚｆｎの最大値ｍａｘ、中央値ｍｅｄ、および、最小値ｍｉｎを求める。この命令は、例えば図６のように、いわゆるＳＩＭＤ命令でひとつのレジスタの中に複数のデータが入っているもとして入出力を取り扱うものである。ただし、ＭＡＸ（ａ，ｂ）はａとｂのうち大きい値、また、ＭＩＮ（ａ，ｂ）はａとｂのうち小さい値を意味するものである。
【００２５】
このＣｏｍｐａｒｅ３命令の結果は、最大値、中央値、最小値のほかに、後にステップＳ４０５で使用するフラグ情報を含んでいる。
【００２６】
ステップＳ４０４では、頂点Ａと頂点ＨのＬＵＴ内のアドレスを求めている。ｂａｓｅは頂点Ａの原点Ｏからの相対アドレスであり、ａ３は頂点Ｈの頂点Ａからの相対アドレスである。式中のｄＸ，ｄＹ，ｄＺはそれぞれ、Ｘ軸方向、Ｙ軸方向、Ｚ軸方向に対応したＬＵＴでのアドレスの増分を示す定数である。
【００２７】
ステップＳ４０５では、頂点Ｑ，頂点ＲのＬＵＴ内のアドレスを求めている。ａ１は頂点Ｑの、ａ２は頂点Ｒのそれぞれ頂点Ａからの相対アドレスである。
【００２８】
ここで、ＳＥＬＥＣＴ（ａ，ｂ，ｃ）は条件ａが真の場合にｂ、偽の場合にｃの値となる命令である。
【００２９】
ａ１については、最初に、Ｙｆｎ、または、Ｚｆｎのどちらかが最大値であると仮定して仮のａ１を求め、次に、仮定に反してＸｆｎが最大値だった場合に、仮のａ１を正しい値に書き換える。
【００３０】
また、ａ２については、最初に、Ｘｆｎ、または、Ｙｆｎのどちらかが最小値であると仮定して仮のａ２を求め、次に、仮定に反してＺｆｎが最小値だった場合に、仮のａ２を正しい値に書き換える。
【００３１】
以上の手順でａ１，ａ２を求めることができる。
【００３２】
ステップＳ４０６では頂点Ａ，頂点Ｑ，頂点Ｒ，頂点ＨそれぞれにおいてＬＵＴを参照して格子点の値を得る。
【００３３】
ステップＳ４０７では式１−１５による補間演算で出力値を求める。
【００３４】
以上のように本発明を利用すれば処理に時間のかかる分岐命令を使用せずに、４面体補間を実行することが可能となる。
【００３５】
本発明の第２実施例として、区間幅が入力値によらず、入力のどの要素についても一定のＭであり、それが２の冪（Ｍ＝２ｍ，ｍは非負の整数）である場合を以下に示す。本実施例では入力値Ｘ，Ｙ，Ｚはどれも整数であるものとする。入力値を整数として、区間を２の冪にそろえることで、第１実施例の場合よりも途中の演算を簡略化することが可能になる。
【００３６】
本実施例では、入力値は電算機での色表現としてよく用いられる赤、青、緑の各成分量で、ＬＵＴ内のデータはカラー印刷機で使用するインクの色に対応して、シアン、マゼンタ、イエロー、ブラックの各成分からなる整数のベクトル量とする。
【００３７】
入力値Ｘ，Ｙ，Ｚが何番目の区間に属するかは、以下のように求めることができる。ただし、Ｑｕｏｔｉｅｎｔ（ａ，ｂ）はａ／ｂの商とする。
【００３８】
Ｘｈ＝Ｑｕｏｔｉｅｎｔ（Ｘ，２ｍ）…（２−１）
Ｙｈ＝Ｑｕｏｔｉｅｎｔ（Ｙ，２ｍ）…（２−２）
Ｚｈ＝Ｑｕｏｔｉｅｎｔ（Ｚ，２ｍ）…（２−３）
また、入力値Ｘ，Ｙ，Ｚと区間の開始点との距離が区間幅２ｍに占める割合は以下のようになる。
【００３９】
Ｘｆ＝（Ｘ−Ｘｈ＊２ｍ）／２ｍ…（２−４）
Ｙｆ＝（Ｙ−Ｙｈ＊２ｍ）／２ｍ…（２−５）
Ｚｆ＝（Ｚ−Ｚｈ＊２ｍ）／２ｍ…（２−６）
本実施例でも、第１実施例と同様に式２−４ないし式２−６のＸｆ，Ｙｆ，Ｚｆにかえて、２ｍを分母とした分子Ｘｆｎ，Ｙｆｎ，Ｚｆｎの比較をすることにする。
【００４０】
Ｘｆｎ＝Ｘ−Ｘｈ＊２ｍ＝Ｒｅｍａｉｎｄｅｒ（Ｘ，２ｍ）…（２−７）
Ｙｆｎ＝Ｙ−Ｙｈ＊２ｍ＝Ｒｅｍａｉｎｄｅｒ（Ｙ，２ｍ）…（２−８）
Ｚｆｎ＝Ｚ−Ｚｈ＊２ｍ＝Ｒｅｍａｉｎｄｅｒ（Ｚ，２ｍ）…（２−９）
ただし、Ｒｅｍａｉｎｄｅｒ（ａ，ｂ）はａ／ｂの余りとする。
【００４１】
よく知られているように、ソフトウェアによる処理では２ｍによる除算の商と余りはシフト演算や論理積演算を利用することで簡単にできる。
【００４２】
Ｘｆｎ，Ｙｆｎ，Ｚｆｎの最大値、中央値、最小値であるｍａｘ，ｍｅｄ，ｍｉｎも２ｍを分母とした分子の値となるので、式１−１０は次のようになる。
【００４３】
2004341765.tif 000012
式２−１０を整理すると次式（２−１１）になる。
【００４４】
2004341765.tif 000013
本実施例では次式（２−１２）のようにＰを４捨５入処理をして整数に丸めたものを出力値Ｐ’とする。
【００４５】
2004341765.tif 000014
式２−１２で、ｅは単位ベクトルで、また、割り算において小数以下の端数は切り捨てるものとする。ここでも商はシフト演算で簡単に求めることができる。
【００４６】
図５はこのような４面体補間処理の流れ図である。このうちステップＳ５０２で本発明に特徴的な命令を使用している。
【００４７】
ステップＳ５０１では、式２−１ないし式２−３による格子点Ａの座標（Ｘｈ，Ｙｈ，Ｚｈ）、および、式２−７ないし式２−９による入力値の格子点Ａからの距離（Ｘｆｎ，Ｙｆｎ，Ｚｆｎ）を求めている。
【００４８】
ステップＳ５０２からステップＳ５０４までが、従来例のＳ３０１に相当する部分である。
【００４９】
ステップＳ５０２では、後のステップＳ５０６で使用する補間重み係数（ｗ０，ｗ１，ｗ２，ｗ３）と、ステップＳ５０４で使用するフラグ情報（ｆ０，ｆ１，ｆ２，ｆ３）を求めている。ここでは図７のようなＷｅｉｇｈｔ命令を使用している。ただし、ＭＡＸ（ａ，ｂ）はａとｂのうち大きい値、また、ＭＩＮ（ａ，ｂ）はａとｂのうち小さい値を意味するものである。
【００５０】
このＷｅｉｇｈｔ命令の結果のうち、フラグ情報は特別のフラグレジスタに保存されるものとする。
【００５１】
ステップＳ５０３は、第１実施例におけるステップＳ４０４と同様である。
【００５２】
ステップＳ５０４は、第１実施例におけるステップＳ４０５と同様であるが、ここでは専用のＡｄｄｒｅｓｓ１，Ａｄｄｒｅｓｓ２命令を用いている。以下の表のように、Ａｄｄｒｅｓｓ１命令は、フラグｆ０，ｆ１の組み合わせによって、Ａｄｄｒｅｓｓ２命令はフラグｆ２とｆ３の組み合わせによって頂点Ｑ，Ｒの頂点Ａからの相対アドレス値を生成するものである。
【００５３】
【表１】
2004341765.tif 000015
【００５４】
ステップＳ５０５は、第１実施例におけるステップＳ４０６と同様である。
【００５５】
ステップＳ５０６では、式２−１２のとおり補間演算結果を計算している。ここでは、ステップＳ５０２の結果のｗ０，ｗ１，ｗ２，ｗ３をＡ，Ｐ，Ｑ，Ｈの重み係数として使用している。
【００５６】
【発明の効果】
以上のように本発明によれば実行に比較的時間のかかる条件分岐命令を使用せずに、４面体補間を実行することが可能となり、４面体補間処理において性能の向上が実現する。
【図面の簡単な説明】
【図１】３次元ルックアップテーブルの格子点
【図２】４面体補間の単位格子
【図３】４面体補間流れ図（従来例）
【図４】４面体補間流れ図（第１実施例）
【図５】４面体補間流れ図（第２実施例）
【図６】Ｃｏｍｐａｒｅ３命令
【図７】Ｗｅｉｇｈｔ命令
【符号の説明】
Ｓ３０１  従来の４面体補間準備処理ステップ
Ｓ４０１，Ｓ４０２，Ｓ４０３，ｓ４０４，Ｓ４０５，Ｓ４０６，Ｓ４０７  第１実施例による４面体補間処理を構成する各ステップ
Ｓ５０１，Ｓ５０２，Ｓ５０３，Ｓ５０４，Ｓ５０５，Ｓ５０６  第２実施例による４面体補間処理を構成する各ステップ
【図１】
2004341765.tif 000016
【図２】
2004341765.tif 000017
【図３】
2004341765.tif 000018
【図４】
2004341765.tif 000019
【図５】
2004341765.tif 000020
【図６】
2004341765.tif 000021
【図７】
2004341765.tif 000022