(57)【要約】【課題】色空間変換において、補間演算に使用する格子点データのアクセスを高速に行うことを目的とする。【解決手段】格子点８点によって作られるキューブ分のデータを連続アドレスに配置することによって少ない回数のキャッシュライン読み込みによってキャッシュメモリにデータをとりこみ、プロセサの遅延を削減する。【選択図】        図１
2005018694.tif 000002
【特許請求の範囲】
【請求項１】
３次元ＬＵＴテーブルに記憶された格子点データをもちいて補間演算を行って出力値をえる系において、格子点で構成される各キューブの８点分のデータを連続アドレスに保持することを特徴とする色空間変換方法。
【請求項２】
請求項１の色空間変換方法であって、各キューブのデータにプロセサのキャッシュラインのバイト数の整数倍となるようにダミーデータを付加して構成することを特徴とする色空間変換方法。
【請求項３】
請求項１の色空間変換方法であって、キューブ確定直後にキャッシュのプリフェッチを行い、その後に補間に用いる点の選択を行うことを特徴とする４点補間の色空間変換方式。
【請求項４】
請求項２の色空間変換方法であって、キューブ確定直後にキャッシュのプリフェッチを行い、その後に補間に用いる点の選択を行うことを特徴とする４点補間の色空間方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像処理方法に閲し、特に色空間変換処理を汎用プロセサを用いて高速に行うためのものである。
【０００２】
【従来の技術】
従来、３次元ＬＵＴを用いる色空間変換等、高次元、高精度の入力値を処理する色空間変換においては、空間をいくつかの格子上に区切りその頂点のデータを用いて補間演算を行って算出されている。これらに関してはさまざまな補間方法が開示されている（特開昭６３−１６２２４８号公報、特開平５−４６７５０号公報、特公昭５８−１６１８０号公報）。
【０００３】
汎用プロセサを用いてこれらの補間演算を行う場合、汎用プロセサの処理能力は、近年、著しく向上し、演算処理そのものは高速に行われるようになった。しかし、より高精度の色空間変換を行うために格子点数を増加させると、これらのデータのキャッシュヒット率が低下し、メモリアクセスが処理時間の遅延の主な原因となっている。
【０００４】
【発明が解決しようとする課題】
（１）ＬＵＴを用いる場合、図３で示すようにアクセスするメモリはとびとびになり、メモリアクセスの効率は悪い。ＣＭＹＫ４色を各色８ビットの格子点データから補間して出力する系をキャッシュライン３２バイトのプロセサで構成した場合、８点補間ではキャッシュにヒットしなかった場合、少なくて４回、最大８回のキャッシュへの読み込みが発生する。４点補間の場合には少なくて３回、最大４回発生する。この読み込みの時間によって、処理時間は長くなる。
【０００５】
（２）図５で示すように、出力する色数によっては、キャッシュラインの幅との関係でキューブによっては効率よくアクセス出来ないことがある。ＣＭＹ３色を各色８ビットの格子点データから補間して出力する系をキャッシュライン３２バイトのプロセサで構成した場合、１点分のデータは３バイト、８点分のデータは２４バイトとなりこれを連続アドレスに各キューブ分順次すると、キャッシュラインにアラインしているキューブは１回のキャッシュライン読み込みによってキャッシュに読み込めるが、キャッシュラインにアラインしていないキューブのデータは２回読み込みが必要となり遅延を生じる。
【０００６】
４点補間等、キューブを構成するデータを全て使用しない補間方式の場合、入力値によってどのキューブを使用するかが決定し、さらにそのキューブ内のどの点をのデータを使用するかを決定する。上述（１）（２）のように少ない回数のキャッシュ読み込みで８点分のデータをキャッシュ持ってくることが可能である構成とした場合、キューブが決定した時点でキャッシュへのプリフェッチを行い、その間にどの点のデータを使用するかを決定することによって高速に処理を行うことが可能になる。
【０００７】
【課題を解決するための手段】
（１）図４で示すように各格子点で囲まれるキューブを構成する８点でのデータを連続アドレスに保持する。
（２）図６で示すように各キューブのデータにプロセサのキャッシュラインのバイト数の整数倍となるようにダミーデータを付加してデータを構成する。
（３）４点補間等、格子点データ全てを使わない補間方式を採用している場合において、図４で示すように各格子点で囲まれるキューブを構成する８点でのデータを連続アドレスに保持し、補間演算に使用するキューブが確定した時点でキャッシュのプリフェッチを行い、その動作中に補間に用いる点の選択処理を行う。
（４）４点補間等、格子点データ全てを使わない補間方式を採用している場合において、図６で示すように各キューブのデータにプロセサのキャッシュラインのバイト数の整数倍となるようにダミーデータを付加してデータを構成し、補間演算に使用するキューブが確定した時点でキャッシュのプリフェッチを行い、その動作中に補間に用いる点の選択処理を行う。
【０００８】
（作用）
（１）図４で示すように各格子点で囲まれるキューブを構成する８点でのデータを連続アドレスに保持することによって、キャッシュへの読み込み回数が減少する。ＣＭＹＫ４色を各色８ビットの格子点データから補間して出力する系をキャッシュライン３２バイトのプロセサで構成した場合、１点分のデータは４バイト、８点分のデータは３２バイトとなりこれを連続アドレスに格納することによって、１回のキャッシュライン読み込みによって格子点データをキャッシュに読み込むことが可能になる。
（２）図６で示すように各キューブのデータにプロセサのキャッシュラインのバイト数の整数倍となるようにダミーデータを付加してデータを構成することによって、キャッシュへの読み込みの回数を削減することが可能となる。ＣＭＹ３色を各色８ビットの格子点データから補間して出力する系をキャッシュライン３２バイトのプロセサで構成した場合、ｌ点分のデータは３バイト、８点分のデータは２４バイトとなりこれにダミーデータ８バイトを付加し３２バイトとし連続アドレスに格納することによって、１回のキャッシュライン読み込みによって格子点データをキャッシュに読み込むことが可能になる。
（３）キャッシュのプリフェッチ動作中に補間に用いる点の選択処理を行うことによって処理時間を短縮することが可能となる。
（４）キャッシュのプリフェッチ動作中に補間に用いる点の選択処理を行うことによって処理時間を短縮することが可能となる。
【０００９】
【発明の実施の形態】
（実施例）
以下、図面を参照して本発明の実施例を詳細に説明する。図１は本発明の第１の実施例の動作を示すフローチャートである。入力値はどのキューブに属する点であるかによって、キューブの先頭アドレスを算出する。（１０）これには、入力値の範囲分のエントリを持った１ＤＬＵＴを入力値の次元数もち、これらの値の加算によって求める等の方法がある。ＲＧＢ各々８ビットを入力値とする場合には、２５６エントリのテーブルを３個用意し、これらの加算値によってアドレスを得ることができる。次に入力値は、格子点であるかの判定（１１）を行い、格子点であれば、Ｌ（ｌ，Ｊ，Ｋ）を出力値とする（１２）。格子点でなければ、キューブのデータＬ（ｌ，Ｊ，Ｋ）〜Ｌ（ｌ＋１，Ｊ＋１，Ｋ＋１）を用いて補間演算を行い（１４）これを出力値とする（１５）。ここでキューブデータ８点分を図４で示すように連続アドレスに配置する。したがって、キャッシュラインが３２ビットのプロセサでＣＭＹＫの４色の８ビットデータを用いて補間を行う場合には、Ｌ（０，０，０）をキャッシュライン境界にアラインしておけば、キャッシュへの読み込みは、キューブ内のデータを最初にフェッチした時、１度となる。第２の実施例では、キューブデータ８点分を図６で示すように連続アドレスに配置し、キャッシュラインのサイズの整数倍になるようにダミーを付加する。したがって、キャッシュラインが３２ビットのプロセサでＣＭＹの３色の８ビットデータを用いて補間を行う場合には、２４バイト分のデータに８バイトのダミーを付加する。Ｌ（０，０，０）をキャッシュライン境界にアラインしておけば、キャッシュへの読み込みは、キューブ内のデータを最初にフェッチした時、１度となる。図３は本発明の第３の実施例の動作を示すフローチャートである。入力値はどのキューブに属する点であるかによって、キューブの先頭アドレスを算出し、（３０）キューブのデータのキャッシュへの読み込みを開始する。（３１）通常、この種の命令をサポートするプロセサは、キャッシュへの読み込み動作と演算処理あるいは、キャッシュ内からのデータのロードに関しては、並列に動作する。入力値は、格子点であるかの判定（３２）を行い、格子点であれば、Ｌ（ｌ，Ｊ，Ｋ）を出力値とする（３３）。格子点でなければ、補間に用いる点の選択処理を行い（３４）キューブのデータＬ（ｌ，Ｊ，Ｋ）〜Ｌ（ｌ＋１，Ｊ＋１，Ｋ＋１）から選択したデータを用いて補間演算を行い（３６）これを出力値とする（３７）。ここでキューブデータ８点分を図４で示すように連続アドレスに配置する。したがって、キャッシュラインが３２ビットのプロセサでＣＭＹＫの４色の８ビットデータを用いて補間を行う場合には、Ｌ（０，０，０）をキャッシュライン境界にアラインしておけば、キャッシュへの読み込みは、キュ−ブ内のデータを最初にアクセスした時（レジスタにロードしたとき、あるいは演算のオペランドに出現したとき）１度となる。出力色が４色以上あるいはデータが８ビット長以上の場合、キャッシュへの読み込みは１回で完了しない。したがって、３２、３４の処理の中に適時埋め込んで行う。
【００１０】
第４の実施例では、キューブデータ８点分を図６で示すように連続アドレスに配置し、キャッシュラインのサイズの整数倍になるようにダミーを付加する。
【００１１】
したがって、キャッシュラインが３２ビットのプロセサでＣＭＹの３色の８ビットデータを用いて補間を行う場合には、２４バイト分のデータに８バイトのダミーを付加する。Ｌ（０，０，０）をキャッシュライン境界にアラインしておけば、キャッシュへの読み込みは、キューブ内のデータを最初にアクセスした時（レジスタにロードしたとき、あるいは演算のオペランドに出現したとき）１度となる。
【００１２】
【発明の効果】
以上説明したように、第１の発明を実施すれば、色空間変換の際にキャッシュへの読み込みの回数が減少し、高速処理が可能となる。第２の発明を実施すれば、補間に用いる８点分のデータの総和がキャッシュラインのサイズの整数倍にならない場合にもキャッシュラインへの読み込みを低減することができ高速な処理が可能となる。第３の発明を実施すれば、キャッシュへのプリフェッチ命令を備えるプロセサを用いた系においてより高速な処理が可能となる。第４の発明を実施すれば、キャッシュへのプリフェッチ命令を備えるプロセサを用いた系において補間に用いる８点分のデータの総和がキャッシュラインのサイズの整数倍にならない場合により高速な処理が可能となる。
【図面の簡単な説明】
【図１】本発明の第１、２の実施例の動作を示すフローチャート。
【図２】本発明の第３、４の実施例の動作を示すフローチャート。
【図３】第１、第３の発明のデータ構造を示す図。
【図４】第１、第３の発明のデータ構造を示す図。
【図５】第２、第４の発明のデータ構造を示す図。
【図６】第２、第４の発明のデータ構造を示す図。
【図１】
2005018694.tif 000003
【図２】
2005018694.tif 000004
【図３】
2005018694.tif 000005
【図４】
2005018694.tif 000006
【図５】
2005018694.tif 000007
【図６】
2005018694.tif 000008