JP5034738B2 - データ処理装置及びデータ処理プログラム - Google Patents

Description

本発明は、データ処理装置またはデータ処理プログラムに関する。

下記特許文献１には、画像データに対し、ＬＵＴ（ルックアップテーブル）を用いた色変換処理を行う技術が開示されている。この技術では、大容量低速メモリに格納されたＬＵＴの一部を、小容量高速メモリに記憶させて変換に使用する。そして、参照したいデータが小容量高速メモリにない場合は、小容量高速メモリのデータの書き換えを行う。

下記特許文献２にも、画像データに対し、ＬＵＴを用いた色変換処理を行う技術が開示されている。この技術では、ミスヒットがあったときには、ＦＩＦＯ（ＦｉｒｓｔＩｎＦｉｒｓｔＯｕｔ）を用いて処理を遅延させ、その間にＬＵＴを更新している。

特開２００５−１５７５３０号公報 特開２００６−１５７２５２号公報

本発明の目的は、部分参照表を用いたデータ処理の効率を高めることにある。

本発明のデータ処理装置の一態様においては、処理対象データを入力する入力手段と、前記処理対象データがとり得るすべてのデータ値の各々について当該データ値に対応する参照データが登録された表である参照表を記憶する第１の記憶手段と、参照表を構成する複数の参照データの部分集合である部分参照表を複数記憶する第２の記憶手段であって、前記第２の記憶手段の容量は前記参照表全体のデータ量よりも小さいため前記第２の記憶手段に記憶された複数の部分参照表は前記参照表全体のうちの一部しかカバーしておらず、かつ前記第２の記憶手段に記憶された複数の部分参照表は、それぞれ当該部分参照表に含まれる参照データに対応する前記データ値の範囲であるデータ範囲が互いに異なっていることを特徴とする第２の記憶手段と、入力した処理対象データの前記データ値に応じて、前記第２の記憶手段に記憶された前記複数の部分参照表の中に当該データ値に対応する前記データ範囲を持つ部分参照表がある場合には、当該部分参照表を選択部分参照表として選択し、前記第２の記憶手段に記憶された前記複数の部分参照表の中に当該データ値に対応するデータ範囲を持つ部分参照表がない場合には、当該データ値に対応するデータ範囲を持つ部分参照表を前記参照表から取得し、前記第２の記憶手段に記憶されている前記複数の部分参照表のうちのいずれかを当該取得した部分参照表に変更してから、前記第２の記憶手段内にある当該変更された部分参照表を選択部分参照表として選択し、選択した当該選択部分参照表から当該データ値に対応する参照データを参照する参照手段と、前記入力した処理対象データの前記データ値に応じて前記参照手段が前記第２の記憶手段内の前記選択部分参照表から参照した前記参照データを用いて、前記処理対象データに対するデータ処理を行うデータ処理手段と、前記入力した処理対象データのデータ値から、今後入力される処理対象データの前記データ値を予測する予測手段と、前記予測手段が予測した前記今後入力される処理対象データの前記データ値が、前記第２の記憶手段に記憶された前記複数の部分参照表のいずれの前記データ範囲にも含まれない場合に、前記今後入力される処理対象データの前記データ値を含んだ前記データ範囲に対応する部分参照表を前記参照表から取得し、前記第２の記憶手段に記憶された前記複数の部分参照表のうち、前記選択部分参照表以外の一又は二以上の部分参照表を、当該取得した部分参照表に変更する変更手段と、論理仕様を再構成可能な再構成可能回路と、前記再構成可能回路の論理仕様を再構成する再構成手段と、を備え、前記参照手段、前記データ処理手段、及び前記変更手段による各処理の少なくとも一部は、前記再構成可能回路に設定された論理に基づいて行われ、前記再構成手段は、前記予測手段が予測した前記今後入力される処理対象データの前記データ値が、前記記憶手段に記憶された前記複数の部分参照表のいずれの前記データ範囲にも含まれない場合に、前記再構成可能回路を再構成して、変更対象となった前記部分参照表を前記変更手段が変更する論理を設定し、かつ、前記部分参照表が変更された後に前記再構成可能回路を再構成して、変更された前記部分参照表を前記参照手段が参照する論理、及び、変更された前記部分参照表の参照結果に基づいて前記データ処理手段がデータ処理を行う論理を設定する。

参考例においては、前記参照手段または前記データ処理手段による処理の実行と、前記変更手段による処理の実行とは、少なくともその一部が並列的に行われる。

本発明のデータ処理装置の一態様においては、前記再構成可能回路は、論理仕様を変更可能な複数の記憶回路を備え、前記記憶手段は、二以上の前記論理回路に一又は二以上の前記部分参照表を記憶し、前記変更手段は、前記選択部分参照表が記憶されていない前記論理回路に記憶された一又は二以上の前記部分参照表を変更する。

本発明のデータ処理装置の一態様においては、前記記憶回路の容量は前記参照表の大きさに比べて小さい。

本発明のデータ処理装置の一態様においては、前記参照手段により選択されるべき部分参照表が前記記憶手段により記憶されていない場合に、前記予測手段による前記処理対象データの予測態様を変更する予測態様変更手段を備える。

本発明のデータ処理装置の一態様においては、前記処理対象データは、画像を構成する複数の画素データであり、前記データ値は、前記画素データの画素値である。

参考例のデータプログラムの一態様においては、コンピュータを、処理対象データを入力する入力手段と、参照表を構成する複数の参照データの部分集合である部分参照表を複数記憶する記憶手段であって、前記参照表は、前記処理対象データがとり得るすべてのデータ値の各々について当該データ値に対応する参照データが登録された表であり、前記記憶手段の容量は前記参照表全体のデータ量よりも小さいため前記記憶手段に記憶された複数の部分参照表は前記参照表全体のうちの一部しかカバーしておらず、かつ前記記憶手段に記憶された複数の部分参照表は、それぞれ当該部分参照表に含まれる参照データに対応する前記データ値の範囲であるデータ範囲が互いに異なっていることを特徴とする記憶手段と、入力した処理対象データの前記データ値に応じて、前記記憶手段に記憶された前記複数の部分参照表の中に当該データ値に対応する前記データ範囲を持つ部分参照表がある場合には、当該部分参照表を選択部分参照表として選択し、前記記憶手段に記憶された前記複数の部分参照表の中に当該データ値に対応するデータ範囲を持つ部分参照表がない場合には、当該データ値に対応するデータ範囲を持つ部分参照表を前記参照表から取得し、前記記憶手段に記憶されている前記複数の部分参照表のうちのいずれかを当該取得した部分参照表に変更してから、前記記憶手段内にある当該変更された部分参照表を選択部分参照表として選択し、選択した当該選択部分参照表から当該データ値に対応する参照データを参照する参照手段と、前記入力した処理対象データの前記データ値に応じて前記参照手段が前記記憶手段内の前記選択部分参照表から参照した前記参照データを用いて、前記処理対象データに対するデータ処理を行うデータ処理手段と、前記入力した処理対象データとの関連性に基づいて、今後入力される処理対象データの前記データ値を予測する予測手段と、前記予測手段が予測した前記今後入力される処理対象データの前記データ値が、前記記憶手段に記憶された前記複数の部分参照表のいずれの前記データ範囲にも含まれない場合に、前記今後入力される処理対象データの前記データ値を含んだ前記データ範囲に対応する部分参照表を前記参照表から取得し、前記記憶手段に記憶された前記複数の部分参照表のうち、前記選択部分参照表以外の一又は二以上の部分参照表を、当該取得した部分参照表に変更する変更手段、として機能させる。

請求項１に記載の発明によれば、部分参照表を用いたデータ処理において、参照される蓋然性が高い部分参照表が用意されるため、データ処理の効率を高めることが可能となる。また、部分参照表を参照する過程と、部分参照表を変更する過程とが、再構成により切り換えられて実行されるため、データ処理の効率を高めることが可能となる。

参考例によれば、参照データの参照あるいは処理対象データに対するデータ処理が行われている間を利用して、参照されていない部分参照表の変更が行われるため、データ処理の効率を高めることができる。

請求項２に記載の発明によれば、部分参照表の参照と、部分参照表の変更とにおいて、同一の記憶回路の競合が発生することを防止できる。

請求項３に記載の発明によれば、記憶回路が参照表を記憶する容量を有しない場合においても、効率を高めたデータ処理が可能となる。

請求項４に記載の発明によれば、予測が精度よく行われていない場合に、予測態様を変更して予測精度の向上を試みることが可能となる。

請求項５に記載の発明によれば、画像データに対する処理効率を向上させることが可能となる。

参考例によれば、参照される蓋然性が高い部分参照表が用意され、データ処理の効率を高めることが可能なデータ処理プログラムが提供される。

［用語等の説明］ ここでは、特許請求の範囲、明細書、または図面において用いられる用語や概念等について説明する。

データ処理装置は、コンピュータハードウエアと、その動作を規定するプログラム（ソフトウエア）を用いて構築される装置である。コンピュータハードウエアは、プログラムの制御によって、入力手段、記憶手段、参照手段、データ処理手段、予測手段、変更手段、予測態様変更手段などの各手段として機能することになる。データ処理装置は、単体のコンピュータハードウエアを利用した集中処理システムとして構築されてもよいし、通信可能な複数のコンピュータハードウエアを利用した分散処理システムとして構築されてもよい。

入力手段は、複数の処理対象データを入力する手段である。処理対象データは、１自由度（１ビット）からなるデータであっても、複数自由度（複数ビット）からなるデータであってもよい。また、処理対象データは、例えば、一つの要素をもつもの（１次元データ）であってもよいし、複数の要素をもつもの（多次元データ）であってもよい。入力される複数の処理対象データの間には、データ特性になんらかの関連性がある。データ特性の例としては、その処理対象データ自体がもつ絶対的な特性（例えばデータ値の大きさ）、他の処理対象データとの比較により求められる相対的な特性（例えばデータ分布）、あるいは、処理対象データに対し適当な演算を施すことにより判別可能な特性（例えばデータ変換後のデータ値の大きさ）などを挙げることができる。また、関連性とは、例えば、全体として意味あるデータ群を構成する（例えば全体として画像を構成したり、全体として時系列データを構成したりする）ものや、相互に相関をもつもの（相互に対比対象となる実験・観測データなど）などを例示することができる。

記憶手段は、半導体メモリなどの記憶装置に、参照表の一部である部分参照表を複数記憶する手段である。ここで、参照表は全参照データによって構成されるデータ構造であり、部分参照表は全参照データの部分集合によって構成されるデータ構造である。参照表は、所望のデータを参照（読み出し）できるようにデータ構造が設定されたデータ群を指す。参照表には、しばしばハッシュやツリーなどの探索アルゴリズムが用いられる。参照表の典型例としては、ルックアップテーブル（ＬＵＴ）を挙げることができる。なお、参照表自体は、当該データ処理装置内に別途記憶されてもよいし、外部から取得されてもよい。

参照手段は、入力した処理対象データのデータ特性に応じた参照データを参照する。この参照過程では、複数ある部分参照表の中から、参照に用いる部分参照表（選択部分参照表と呼ぶ）を選択し、この選択部分参照表の中から参照データを参照する。

データ処理手段は、入力した処理対象データに対してデータ処理を行う手段である。データ処理の例としては、データ変換処理、フィルタ処理、統計処理などを挙げることができる。データ処理は、例えば、入力した各処理対象データに対して行われてもよいし、選択された一部の処理対象データに対して行われてもよい。また、二以上の処理対象データをひとまとまりとして行われてもよい。データ処理は、部分参照表の中から処理対象データのデータ特性に応じた参照データを参照して行われる。参照データは、例えば、処理対象データの置き換え、処理対象データとの対比、実行する演算のパラメータなどに用いられる。なお、データ処理においては、参照手段により行われる参照データを参照するための演算結果が使用されてもよい。

予測手段は、予測を開始する時点ではまだ入力されていない処理対象データ、つまり、まだデータ特性を吟味することのできない処理対象データについて、そのデータ特性を予測する。データ特性の予測は、入力が完了した（処理済みても、未処理でも、その両方であってもよい）一または二以上の処理対象データとのデータ特性が関連することを利用して行われる。予測は、例えば、補間処理、確率・統計処理など様々な態様で行うことが可能である。

予測態様変更手段は、予測の精度が悪く、参照に必要となる部分参照表が前記記憶手段により記憶されていない場合、つまりミスヒットが発生する場合に、予測手段による予測態様を変更する。予測態様の変更は、ミスヒットが発生した場合に直ちに行うようにしてもよいし、ミスヒットの発生が許容範囲以上発生した場合に行うようにしてもよい。予測態様の変更の例としては、時間間隔を短くする（予測頻度を高める）、予測アルゴリズム（補間関数など）の精度を上げる、遠未来から近未来と予測時間を短縮するなどの態様を挙げることができる。

変更手段は、予測結果に応じて、記憶手段により記憶された部分参照表を変更（更新）する。変更される部分参照表は、選択部分参照表に含まれないものの中から選ばれる。なお、参照手段による択部分参照表の参照あるいはデータ処理手段による参照結果を利用したデータ処理と、変更手段による部分参照表の変更は、並列的に実行することができる。ここで、並列的とは、少なくとも一部が同時刻帯に実行されることをいう。

コンピュータハードウエアとしては、典型的には、その論理仕様が固定されたものが用いられる。しかし、例えば、そのコンピュータハードウエアが備える演算装置の一部または全部を、論理仕様を再構成可能な再構成可能回路（リコンフィギュラブル回路）によって構築することも可能である。再構成可能回路は、典型的には、主として演算処理を行う算術論理演算部（ＡＬＵ）などの演算回路と、主としてデータの記憶を行うランダムアクセスメモリ（ＲＡＭ）などの記憶回路とを含んでいる。そして、再構成論理回路では、ハードウエア的に規定された論理仕様をソフトウエア的（プログラム的に）に変更することが可能である。特に、論理仕様を数サイクル以内に切り換えることができる場合には、一連の処理の最中に論理仕様を変更する動的再構成が可能となる。

切り換え対象となる論理仕様には、例えば、演算回路で行われる演算処理の態様を定めた演算論理仕様、再構成論理回路内の配線の態様を定めた結線論理仕様、再構成論理回路と外部装置との配線の態様を定めた入出力論理仕様などが含まれる。なお、記憶回路では、典型的には内部的な論理仕様が固定され、結線論理仕様あるいは入出力論理仕様などが再構成可能に構築されるが、例えば、内部的な論理仕様を再構成可能とされてもよい。

再構成可能回路は、典型的には、分散配置（例えばチップ上に２次元アレイ状に配置）された複数の要素（エレメント）からなる。具体的には、演算回路を複数の演算要素によって構築したり、記憶回路を複数の記憶要素によって構築したりする例が挙げられる。再構成のためのプログラミングが、こうした演算要素や記憶要素を単位として行われることも多い。

再構成手段は、再構成可能回路の論理仕様を再構成し、データ処理手段の機能の一部または全部を実現するデータ処理論理、あるいは、変更手段の機能の一部または全部を実現する変更論理などを設定する。再構成にあたっては、記憶回路に記憶されているデータ、あるいは、演算回路のレジスタに記憶されているデータを初期化してもよいし、保全して（破壊しないで）再構成後に再利用するようにしてもよい。

［実施の形態］ 以下に本発明の実施の形態を例示する。

図１は、本実施の形態にかかる画像処理装置１０の構成例を示す概略図である。画像処理装置１０は、データ処理装置の一種であり、図示した例においては単体の筐体をもつ装置として構成されている。画像処理装置１０の内部には、内部通信路としての内部バス１１が設けられている。そして、内部バス１１には、ＣＰＵ（中央処理装置）１２、ＲＯＭ（ＲｅａｄＯｎｌｙＭｅｍｏｒｙ）１４、ＲＡＭ（ＲａｎｄｏｍＡｃｃｅｓｓＭｅｍｏｒｙ）１６、ＨＤＤ（ＨａｒｄＤｉｓｃＤｒｉｖｅ）１８、再構成可能システム２０、ＵＩ（ＵｓｅｒＩｎｔｅｒｆａｃｅ）２１、スキャナ２２、プリンタ２４、ＣＤＤ（ＣｏｍｐａｃｔＤｉｓｃＤｒｉｖｅ）２６、及びネットワークインタフェース２８の各構成装置が接続されている。

ＣＰＵ１２は、ＲＯＭ１４などに格納されたプログラムに従って、画像処理装置１０の各構成装置の制御や、画像処理等を行う装置である。ＲＯＭ１４は長期的な記憶が可能な半導体メモリ（記憶装置）であり、各種のプログラムや設定情報などを記憶する。ＲＡＭ１６は主として短期的な記憶に用いられる半導体メモリである。ＤＲＡＭ（ダイナミックＲＡＭ）を用いた場合には、比較的大容量だがランダムアクセス読み出しがやや遅い記憶装置となり、ＳＲＡＭ（スタティックＲＡＭ）を用いた場合には、比較的小容量だがランダムアクセス読み出しがやや早い記憶装置となる。ＲＡＭ１６には、処理対象となる画像データなどが記憶される。ＲＡＭ１６と再構成可能システム２０との入出力を高速化するために、内部バス１１を介さずに両者を直結したり、ＤＤＲ（ダブルデータレート）方式を用いたりする場合もある。ＨＤＤ１８は磁気ディスクなどを用いて構成された大容量の記憶装置であり、画像データの長期的な記憶などに用いられる。

再構成可能システム２０は、コンフィグメモリ３２とリコンフィギュラブルプロセッサ３４とを含む装置であり、典型的には、同一のチップ上にこうした装置を設置されている。コンフィグメモリ３２は、リコンフィギュラブルプロセッサ３４の論理仕様を規定する論理仕様データが入力される記憶装置である。コンフィグメモリ３２は、例えば、選択可能な複数の論理仕様データをスイッチで切り替えることで、採用する論理仕様データを数サイクル（例えば１サイクル）で選択できるように設定されている。

リコンフィギュラブルプロセッサ３４は、再構成可能回路としての装置であり、アレイ状に配置された複数のプロセッサエレメント（ＰＥ）を備えている。プロセッサエレメントは、リコンフィギュラブルプロセッサ３４を構成する小回路であり、例えば、演算要素としてのＡＬＵエレメント、あるいは、記憶要素としてのＲＡＭエレメントなどからなる。このうち、ＡＬＵエレメントは、再構成された論理仕様に基づいて、データに対する演算処理を行う小回路であり、ＲＡＭエレメントは、データの入出力及び記憶が行われる小回路であり、例えば、高速な入出力が可能なＳＲＡＭを用いて構築される。ＲＡＭエレメントは、外部設置されるＲＯＭ１４やＲＡＭ１６などに比べて容量が小さいことが多い。ＡＬＵエレメントの内部的な論理仕様である演算論理仕様や、他のＡＬＵエレメントやＲＡＭエレメントとの接続を規定する結線論理仕様、外部装置との接続を規定する入出力論理仕様などは、コンフィグメモリ３２に設定された論理仕様データに基づいて再構成される。なお、リコンフィギュラブルプロセッサ３４には、外部装置との入出力を高速に行う専用入出力Ｉ／Ｆ（インタフェース）や、論理仕様が固定された（再構成不可能な）小演算回路などが設けられることも多い。再構成可能システム２０は、論理仕様データの選択や再構成時期などを制御する制御部を自装置内に備えて自らの動作を制御するものであってもよいし、ＣＰＵ１２などの外部装置によって動作を制御されるものであってもよい。こうした制御部あるいはＣＰＵ１２は、プログラムに従って、コンフィグメモリ３２にコンフィグデータを入力してリコンフィギュラブルプロセッサ３４に画像処理論理などのコンフィギュレーションを設定し、それを実行させる。コンフィグデータは、ＲＯＭ１４、ＲＡＭ１６、ＨＤＤ１８などに格納されている。

ＵＩ２１は、液晶ディスプレイや発光ダイオードなどの表示装置、及び、タッチパネルやキーボードなどの入力装置を備え、画像処理装置１０のユーザにデータを表示したり、ユーザから操作命令を受け付けたりする。スキャナ２２は、用紙表面の画像を読み取って画像データを生成する読取装置である。プリンタ２４は、画像データに基づいて用紙に印刷を行う印刷装置である。ＣＤＤ２６は、記録媒体としてのＣＤ（コンパクトディスク）に記録されたデータを読み取る装置であり、例えば、ＣＰＵ１２や再構成可能システム２０を制御するためのプログラムがＣＤＤ２６により提供された場合にこのプログラムを読み取るために用いられる。ネットワークインタフェース２８は、インターネットなどのネットワーク３０に接続してデータを入出力するためのインタフェースであり、例えば、ＣＰＵ１２や再構成可能システム２０を制御するためのプログラムがネットワーク３０を通じて提供される場合、このプログラムのデータ信号を受信するために用いられる。

続いて、図２乃至図４を参照して、図１に示した画像処理装置１０を用いて行う画像処理の概要について説明する。

図２は、画像処理（データ処理）の一例である色変換処理の流れを説明する図であり、Ｌ^*ａ^*ｂ^*表色系で表現された画像データを、ＣＭＹＫ表色系に変換する処理の例を示している。この例では、画像データを構成する各画素データのＬ^*成分、ａ^*成分、ｂ^*成分が順次入力され、アドレス変換処理部４０でＬ^*ａ^*ｂ^*値に対応したアドレスに変換される。変換により与えられるアドレスは、データメモリ４２，４４，４６，４８に格納されたＣＭＹＫ色変換用の各ルックアップテーブル（それぞれ、Ｃ−ＬＵＴ，Ｍ−ＬＵＴ，Ｙ−ＬＵＴ，Ｋ−ＬＵＴと呼ぶ）の格納位置に対応したものである。すなわち、アドレス変換処理部４０が与えるアドレスに従ってデータメモリ４２〜４８を参照すると、入力した画素値の近傍におけるＣＭＹＫの各成分の値が得られる。そして、得られた値を基に補間処理部５０，５２，５４，５６で補間処理を行うことで、入力した画素値に対応したＣ成分、Ｍ成分、Ｙ成分、Ｋ成分の値が出力される。

図３は、図２で説明したＣ−ＬＵＴの例を模式的に示す図である。Ｃ−ＬＵＴは、３次元空間（Ｌ^*，ａ^*，ｂ^*）上で定義されており、Ｌ^*成分、ａ^*成分、ｂ^*成分の値と、Ｃ成分との関係を表している。図には、入力済みの画素データＩＮ３，ＩＮ２，ＩＮ１，ＩＮ０と、これから入力される画素データＩＮａ，ＩＮｂ，ＩＮｃ，ＩＮｄ，ＩＮｅが図示されている。これらの各画素データに対しては、そのＣ−ＬＵＴを用いて変換を行うことで、近傍のＣの値を求めることができる。しかし、Ｃ−ＬＵＴは一般にサイズが大きく、全てをメモリに格納するのは困難であることが多い。そこで、Ｃ−ＬＵＴの部分集合である部分ＬＵＴ（これは部分参照表の例である）が用いられる。例えば、図３の例では、入力済みの画素データＩＮ３，ＩＮ２，ＩＮ１，ＩＮ０に対しては、Ｃ−ＬＵＴ１を用いて変換が行われる。

ところが、入力がなされていない画素データＩＮａ，ＩＮｂ，ＩＮｃ，ＩＮｄ，ＩＮｅに対しては、どの部分ＬＵＴを用いればよいかは自明ではない。すなわち、画素データＩＮａ，ＩＮｂ，ＩＮｃに対してはＣ−ＬＵＴ２を適用すればよいことや、画素データＩＮｃ，ＩＮｄ，ＩＮｅに対してはＣ−ＬＵＴ３を適用すればよいことは、これらが未入力の段階ではまだわからない。

図４に図示したグラフは、未入力の画素データに必要な部分ＬＵＴの予測態様を説明するものである。グラフの横軸は時間（サイクル）を表し、縦軸は、Ｌ^*の値を表している。そして、グラフ中には、図３に示した画素データＩＮ３，ＩＮ２，ＩＮ１と、これから線形補間（線形補外）した予測画素データＭ１，Ｍ２，Ｍ３が図示されている。すなわち、ある時刻に入力されたＩＮ３、それからｓサイクル後に入力されたＩＮ２、さらにｓサイクル後に入力されたＩＮ３の各Ｌ^*成分を基に３点補間を行って、未来に入力される予測画素データＭ１，Ｍ２，Ｍ３のＬ^*成分値を予測している。図示した例では、画素データＭ１，Ｍ２，Ｍ３はＩＮ１から３ｓ，４ｓ，５ｓサイクル後にそれぞれ入力され、その値は形式的には、次式で表される。
Ｍ１＝（（ＩＮ１−ＩＮ２）＋（ＩＮ２−ＩＮ３））／２ｓ × ４ｓ ＋ ＩＮ２
Ｍ２＝（（ＩＮ１−ＩＮ２）＋（ＩＮ２−ＩＮ３））／２ｓ × ５ｓ ＋ ＩＮ２
Ｍ３＝（（ＩＮ１−ＩＮ２）＋（ＩＮ２−ＩＮ３））／２ｓ × ６ｓ ＋ ＩＮ２

画像データにおいては、各画素の色や輝度は、近傍の画素間で類似する傾向にあり、距離とともに比較的滑らかに変化することが多い。ここでは、このデータ特性を利用して、予測画素データＭ１，Ｍ２，Ｍ３の入力を予測し、これらの予測画素を範囲に含む部分ＬＵＴを対応する時刻に用意することとした。図示した例では、画素データＩＮ３，ＩＮ２，ＩＮ１などの変換に用いている部分ＬＵＴ６０を備えていると仮定している。そこで、更新する部分ＬＵＴ６２は、予測画素データＭ１，Ｍ２，Ｍ３の両側にバランスよく拡がるような範囲に設定されている。このため、部分ＬＵＴ６０と部分ＬＵＴ６２は一部の範囲が重複している。なお、予測画素データＭ１，Ｍ２，Ｍ３の値によっては、部分ＬＵＴ６０と部分ＬＵＴ６２とが重複することも接することもなく、ジャンプする可能性もある。このような時には、例えば、画像の連続性を考慮してジャンプを作らないことを優先してもよいし、予測結果を優先するようにしてもよい。なお、同様の処理は、ａ^*成分及びｂ^*成分に対しても行われる。

続いて、図５〜図８を用いて、以上に説明した処理を行うための構成について説明する。図５は、リコンフィギュラブルプロセッサ３４に設定した論理について説明する図である。リコンフィギュラブルプロセッサ３４には、参照処理部７０、参照部７６、及び画像処理部７８が設けられている。

参照処理部７０は、参照手段として機能する処理部であり、参照部７６のデータを参照するための処理を行っている。具体的には、入力される画素データを順次シフトして出力するシフトレジスタ７２、シフトレジスタ７２からデータを入力し、先入れ先出し方式で出力するＦＩＦＯ７４、部分ＬＵＴの選択を行う部分ＬＵＴ選択制御部８０、及び、部分ＬＵＴの変更（更新）についての処理を行う部分ＬＵＴ予測部８２を備えている。

参照部７６は、部分参照表を記憶する記憶手段としての構成要素であり、部分参照表の例である色変換用の部分ＬＵＴを記憶し管理する。ここでは、リコンフィギュラブルプロセッサ３４に設けられているＲＡＭエレメントの容量が小さく、全ＬＵＴ（現在一般的に用いられているものは１色につき４０キロバイト、４色で１６０キロバイト程度である）を格納できないことを想定しており、参照部７６では、ＲＡＭエレメントの容量に応じた部分ＬＵＴ（例えば１色につき４キロバイト、４色で１６キロバイトのもの）を管理している。参照部７６には、ＲＡＭエレメントとしての２つのデータメモリ８６，８８と、このデータメモリ８６，８８からの出力切り換えを行うＳＥＬ（選択部）９０が設けられている。そして、データメモリ８６，８８には、それぞれ部分ＬＵＴであるＬＵＴ−Ａ８７と、ＬＵＴ−Ｂ８９が設定されている。

画像処理部７８は、データ処理手段の例であり、参照部７６から、部分ＬＵＴの参照結果（参照データ）を入力し、補間処理などの画像処理を行って、その結果を出力する。なお、部分ＬＵＴとして入力するＬＵＴ９２は、ＲＡＭ１６に格納されている。そして、ＬＵＴ９２からの参照データ出力は、ＣＰＵ１２あるいはＤＭＡ（直接メモリアクセス）コントローラなどを利用したＤＲＡＭ（ダイナミックＲＡＭ）制御部８４によって制御されている。

図６は、部分ＬＵＴ選択制御部８０の構成を説明するブロック図である。部分ＬＵＴ選択制御部８０には、指示処理部１００、適合判定部１０２、タグデータ変更部１０４、及びタグデータ１０６が設けられている。指示処理部１００は、ＦＩＦＯ７４に対し画素データの読み出しを開始あるいは停止させる指示、部分ＬＵＴ予測部８２に対しＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９のいずれを更新用とするかの指示、ＳＥＬ９０に対しＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９のいずれの出力を採用するかの指示などを行う。適合判定部１０２は、ＦＩＦＯ７４から出力される画素データが、ＬＵＴ−Ａ８７またはＬＵＴ−Ｂ８９に適合しているか（変換可能な範囲に含まれるか）を判定する。タグデータ１０６は、部分ＬＵＴの更新を行った場合に、タグデータ１０６を対応する値に変更する処理を行う。タグデータ１０６は、部分ＬＵＴに含まれる範囲の情報を与えるデータである。適合判定部１０２における適合性の判定は、画素データに対応するタグデータを参照して行われる。

図７は、部分ＬＵＴ選択制御部８０の選択動作を説明する表である。列１１０と列１１２は、適合判定部１０２によるＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９の適合結果を表している。部分ＬＵＴ選択制御部８０は、この適合結果に基づいて処理を行うものであり、列１１４は部分ＬＵＴに対する処理を示しており、列１１６はＦＩＦＯに対する処理態様を示している。

例えば、色変換対象となる画素データがＬＵＴ−Ａ８７に適合、ＬＵＴ−Ｂ８９には不適合である場合には、ＬＵＴ−Ａ８７が参照対象と採用され、その旨の指令が指示処理部１００からＳＥＬ９０に送られる。そして、ＬＵＴ−Ｂ８９は更新用となり、ＬＵＴ−Ａ８７よりも優先的に更新されるべき旨の指令が部分ＬＵＴ予測部８２に送られる。また、ＦＩＦＯ７４に対しては、通過の指令、つまり読み出しを継続する指令が行われる。なお、入力された画素データが、ＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９の両方に適合した場合にも、ここに示した場合と同様の処理が行われる。他方、入力された画素データが、ＬＵＴ−Ａ８７に不適合、ＬＵＴ−Ｂ８９に適合する場合には、これとは逆の態様で処理が行われる。

これに対し、ＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９の両方に不適合であった場合には、ＬＵＴ−Ｂ８９を直ちに更新する指令が部分ＬＵＴ予測部８２を経由してＤＲＡＭ制御部８４に送られる。そして、ＬＵＴ−Ａ８７は更新対象となり、次回以降にＬＵＴ−Ｂ８９よりも優先的に更新されるべき旨の指令が部分ＬＵＴ予測部８２に送られる。また、ＦＩＦＯ７４に対しては、ＬＵＴ−Ｂ８９の更新が終了するまでは、一旦読み出しを中止するべき旨の指令がなされる。

図８は、予測手段としての部分ＬＵＴ予測部８２の構成を説明するブロック図である。部分ＬＵＴ予測部８２は、予測画素データ演算部１２０、予測時間変更部１２２、ヒット率評価部１２６、及び更新処理部１２４が設けられている。予測画素データ演算部１２０は、図４を用いて説明したように、入力済みの複数の画素データを基に線形補間を行って、適当な時間後に入力される画素データである予測画素データを求める。予測時間変更部１２２は、予測画素データ演算部１２０がどれだけ先の予測画疎データを求めるかを決める予測時間の変更を行う。更新処理部１２４は、予測画素データ演算部１２０の予測結果に基づいて、部分ＬＵＴを更新するか否か、ＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９のいずれを更新するか、どの範囲をカバーする部分ＬＵＴに更新するかなどを決定する。そして、変更手段としてのＤＲＡＭ制御部８４に対し指示を行う。また、ヒット率評価部１２６は、部分ＬＵＴ選択制御部８０からの情報に基づいて、入力された画素データが参照部７６に設定された部分ＬＵＴに適合した度合い（これをヒット率と呼ぶ）を評価する。そして、ヒット率に基づいて、予測時間変更部１２２に予測時間の変更を行わせるか否か決定する。ヒット率評価部１２６及び予測時間変更部１２２は、予測態様変更手段の例である。

続いて、図５〜図８に示した構成の動作について説明する。リコンフィギュラブルプロセッサ３４の参照処理部７０に対しては、ＲＡＭ１６などから画像を構成する画素データが順次入力される。シフトレジスタ７２では、その時点で最も新しい（後から入力された）画素データＩＮ０をＦＩＦＯに出力する。画素データＩＮ０は、参照部７６に入力され、部分ＬＵＴに対応するアドレスに変換されて、ＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９に入力される。そして、ＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９は、入力されたアドレスに対応するＣＭＹＫの各成分のデータをＳＥＬ９０に出力する。そして、ＳＥＬ９０で選択されたデータは画像処理部７８に出力され、必要な補間処理を受けた後に、ＲＡＭ１６などに出力される。

ここで、この過程における部分ＬＵＴ選択制御部８０の制御について、図９を用いて説明する。部分ＬＵＴ選択制御部８０では、ＦＩＦＯ７４による画素データＩＮ０の入力（及び出力）が開始されると（Ｓ１０）、タグデータ１０６を参照した上で、適合判定部１０２が部分ＬＵＴの適合性を判定する。図９の例では、ＬＵＴ−Ｂ８９が更新用の部分ＬＵＴに設定されていることを過程しており、まず、画素データＩＮ０がＬＵＴ−Ａ８７に適合するか否かが判定される（Ｓ１２）。その結果、ＬＵＴ−Ａ８７に適合する場合には、ＬＵＴ−Ａ８７が採用される（Ｓ１４）。そして、指示処理部１００は、図７の表に示したように、ＳＥＬ９０に対しＬＵＴ−Ａ８７の出力を選択するように指示し、ＦＩＦＯ７４に対しては読み込みの継続を指示する。なお、更新用の部分ＬＵＴはＬＵＴ−Ｂ８９に設定されたまま変更されない。

他方、ＬＵＴ−Ａ８７に適合しない場合には、ＬＵＴ−Ｂ８９に適合するか否かが判定される（Ｓ１６）。そして、ＬＵＴ−Ｂ８９に適合した場合には、ＬＵＴ−Ｂ８９が採用され（Ｓ１８）、ＳＥＬ９０に対してはＬＵＴ−Ｂ８９からの出力を選択する指示がなされる。また、部分ＬＵＴ予測部８２に対しては、ＬＵＴ−Ａ８７を更新用に設定する旨の指示が送られる（Ｓ２０）。

ＬＵＴ−Ｂ８９にも適合しなかった場合には、ＳＥＬ９０に対しては、ＬＵＴ−Ｂ８９からの出力を選択するよう指示がなされる一方、ＦＩＦＯ７４に対して読み込みの停止が指示される（Ｓ２４）。そして、部分ＬＵＴ予測部８２を通じてＬＵＴ−Ｂ８９の更新が行われ（Ｓ２６）、更新が完了するとＦＩＦＯ７４に対し読み込み再開が指示される（Ｓ２８）。最後に、ＬＵＴ−Ａ８７が更新用に設定される（Ｓ３０）。

続いて、図１０を用いて、部分ＬＵＴ予測部８２の動作について説明する。画素データが参照処理部７０に入力されると（Ｓ４０）、シフトレジスタ７２は、画素データＩＮ０よりも前に入力された三つの画素データＩＮ３，ＩＮ２，ＩＮ１（これらは連続して入力されたものでも、何個か置きに選択されたものでもよい）を生成し、部分ＬＵＴ予測部８２に入力する（Ｓ４２）。予測画素データ演算部１２０では、画素データＩＮ３，ＩＮ２，ＩＮ１を用いて、線形補間を行い、予測画素データＭ１〜Ｍ３を順次生成する（Ｓ４４）。次いで、更新処理部１２４は、まずＭ１を選択して（Ｓ４６）、更新用の部分ＬＵＴとＭ１との適合性を調べ、更新用ＬＵＴを更新する必要があるか否かを確認する（Ｓ４８，Ｓ５０）。その結果、更新の必要性がないと判定された場合には、Ｍ２，Ｍ３の順で同様の処理を繰り返す（Ｓ５２，Ｓ５４，Ｓ４６）。そして、Ｍ３に対しても更新の必要性がないと判断されたときは、次の画素データの組を対象として同様の処理を繰り返す（Ｓ５４，Ｓ４２）。他方、更新の必要があると判定された場合には、更新処理部１２４は、どの範囲の部分ＬＵＴへと更新するかを決定し（Ｓ５６）、ＤＲＡＭ制御部８４に更新用の部分ＬＵＴを更新させる（Ｓ５８）。なお、更新処理部１２４では、部分ＬＵＴ選択制御部８０から、適合する部分ＬＵＴがない旨の連絡を受けると、更新用の部分ＬＵＴに対する更新を行い、処理中の画素データＩＮ０の値に適合するデータを設定する。

次に、図１１と図１２を用いて、部分ＬＵＴ予測部８２の予測時間変更部１２２及びヒット率評価部１２６の動作について説明する。図１１は、動作の流れを表すフローチャートであり、図１２は、図４に対応する模式的な説明図である。

図１１に示すように、予測時間変更部１２２は、はじめ、予測時間をＴαサイクル（制御信号のサイクルで時間を表現している）に設定して予測を行う。予測時間のＴαサイクルは、予測の結果、部分ＬＵＴの更新を行うことになった場合に必要となる所要時間に基づいて決められているおり、例えば所要時間と同じサイクル数（部分ＬＵＴの大きさにもよるが１０００サイクル程度）に設定される。図１２に示した例では、画素データＩＮ３，ＩＮ２，ＩＮ１の線形補間の結果、予測時間をＴαサイクルの後には、予測画素データＭαが入力されると予測されている。この予測結果は、実際に入力される画素データＩＮαとは大きく相違している。このため、画素データＩＮαは、その時点で参照部７６に設定されているＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９のいずれにも適合せず、ミスヒットが発生することになる。予測時間変更部１２２は、このようなミスヒットがＹ回中Ｘ回以上発生するまでは、予測時間をＴαにサイクル維持する（Ｓ６２）。そして、ミスヒットがＹ回中Ｘ回以上発生した場合には、予測時間変更部１２２は、予測画素データ演算部１２０における予測時間をＴαサイクルよりも短いＴβサイクルに変更する（Ｓ６４）。これは、図１２に示した例では、画素データＩＮ３，ＩＮ２，ＩＮ１を線形補間してＴβ時間後に予測画素データＭβが入力されると予測することに相当する。これにより、一般的には、実際に入力される画素データＩＮβとの差（予測誤差）が減少する。

その後、Ｙ回連続してヒットに成功（ミスヒットがない）場合には（Ｓ６６）、再び予測時間をＴαに設定し、予測に要する時間の節約が図られる。他方、Ｙ回中Ｘ回以上ミスヒットが発生しない場合には、予測時間Ｔβが維持され（Ｓ６８）、再びＹ回中Ｘ回以上ミスヒットが発生した場合には、予測時間変更部１２２は、予測画素データ演算部１２０における予測時間をＴβよりも短いＴγサイクルに変更する（Ｓ７０）。図１２に示したように、一般に、予測時間がＴγサイクルの場合における予測画素データＭγと実際に入力される画素データＩＮγとの差は、予測時間がＴβサイクルの場合に比べてさらに小さくなり、ミスヒットも減少する。そして、Ｙ回連続してヒットに成功した場合には、予測時間がＴβサイクルに戻される（Ｓ７２）。予測時間をどの程度に変更するか、また、どのような条件を満たしたときに変更するかは、全体の所要時間を短縮化することを考えて決定される。

最後に、図１３を用いて、リコンフィギュラブルプロセッサ３４を再構成して、部分ＬＵＴの更新を行う例について説明する。図１３（ａ）は、図５のリコンフィギュラブルプロセッサ３４に対応する図である。すなわち、参照処理部７０、参照部７６、及び画像処理部７８が設けられ、参照部７６には部分ＬＵＴとしてのＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９が構築されている。ここで、部分ＬＵＴ予測部８２によって、ＬＵＴ−Ｂ８９を更新すべき旨の判定が下されたとする。このとき、図５に示した例では、リコンフィギュラブルプロセッサ３４の外部にあるＤＲＡＭ制御部８４によって、ＲＡＭ１６に格納されたＬＵＴ９２の一部が読み出され、データメモリ８６，８８の所定のアドレスに格納された。これに対し、図１３に示した例では、リコンフィギュラブルプロセッサ３４の再構成が行われ、図１３（ｂ）に示す論理が設定される。具体的には、図１３（ｂ）では、参照処理部７０と画像処理部７８とが、図１３（ａ）と同じ位置に設けられている。また、参照部７６中のＬＵＴ−Ａ８７は、再構成後まで値が保全されている。そして、参照処理部７０によってＬＵＴ−Ａ８７を参照し、参照結果を画像処理部７８に出力する結線論理も図１３（ａ）と同様にして設定されている。しかし、参照処理部７０によってＬＵＴ−Ｂ８９を参照し、参照結果を画像処理部７８に出力する結線論理は、図１３（ｂ）では設定されていない。

代わりに、図１３（ｂ）では、リコンフィギュラブルプロセッサ３４中の未使用のＡＬＵエレメントの論理仕様を変更することにより、部分ＬＵＴセット部１３０が設定されている。この部分ＬＵＴセット部１３０は、図５に示したＲＡＭ１６からＬＵＴ９２の一部のデータを入力し、適当なアドレスを設定してＬＵＴ−Ｂ８９を更新するものである。部分ＬＵＴセット部１３０は、その論理をハードウエア的に構築されているため、ソフトウエア的な処理に比べて高速に（例えば書き込み時間が１／１０００程度になる）ＬＵＴ−Ｂ８９の更新を行う。そして、これと並列的に、参照処理部７０によるＬＵＴ−Ａ８７の参照と、画像処理部７８による参照結果を利用した色変換処理が行われる。やがて、ＬＵＴ−Ｂ８９の更新が完了すると、再び図１３（ａ）に示す論理が設定され、ＬＵＴ−Ａ８７とＬＵＴ−Ｂ８９を選択した色変換処理が行われる。

本実施の形態にかかる画像処理装置の構成例を示す概略図である。 ＬＵＴを用いた色変換の例を説明する図である。 ＬＵＴと入力される画素データとの関係を例示する模式図である。 入力される画素データのデータ特性の予測原理を例示する図である。 リコンフィギュラブルプロセッサに設定される論理の例を示す図である。 部分ＬＵＴ選択制御部の構成例を説明する図である。 部分ＬＵＴ選択制御部で行われる判定結果と処理態様を示す表である。 部分ＬＵＴ予測部の構成例を説明する図である。 部分ＬＵＴ選択制御部における処理の流れを示すフローチャートである。 部分ＬＵＴ予測部における処理の流れを示すフローチャートである。 予測時間を変更する制御について説明するフローチャートである。 予測時間の変更について説明する模式図である。 リコンフィギュラブルプロセッサの再構成例について説明する図である。

符号の説明

１０ 画像処理装置、１１ 内部バス、１２ ＣＰＵ、１４ ＲＯＭ、１６ ＲＡＭ、１８ ＨＤＤ、２０ 再構成可能システム、２１ ＵＩ、２２ スキャナ、２４ プリンタ、２６ ＣＤＤ、２８ ネットワークインタフェース、３０ ネットワーク、３２ コンフィグメモリ、３４ リコンフィギュラブルプロセッサ、４０ アドレス変換処理部、４２〜４８，８６，８８ データメモリ、５０〜５６ 補間処理部、７０ 参照処理部、７２ シフトレジスタ、７６ 参照部、７８ 画像処理部、８０ 部分ＬＵＴ選択制御部、８２ 部分ＬＵＴ予測部、８４ ＤＲＡＭ制御部、８７ ＬＵＴ−Ａ、８９ ＬＵＴ−Ｂ、９０ ＳＥＬ、１００ 指示処理部、１０２ 適合判定部、１０４ タグデータ変更部、１０６ タグデータ、１２０ 予測画素データ演算部、１２２ 予測時間変更部、１２４ 更新処理部、１２６ ヒット率評価部、１３０ 部分ＬＵＴセット部。

Claims (5)

1. 処理対象データを入力する入力手段と、
   前記処理対象データがとり得るすべてのデータ値の各々について当該データ値に対応する参照データが登録された表である参照表を記憶する第１の記憶手段と、
   参照表を構成する複数の参照データの部分集合である部分参照表を複数記憶する第２の記憶手段であって、前記第２の記憶手段の容量は前記参照表全体のデータ量よりも小さいため前記第２の記憶手段に記憶された複数の部分参照表は前記参照表全体のうちの一部しかカバーしておらず、かつ前記第２の記憶手段に記憶された複数の部分参照表は、それぞれ当該部分参照表に含まれる参照データに対応する前記データ値の範囲であるデータ範囲が互いに異なっていることを特徴とする第２の記憶手段と、
   入力した処理対象データの前記データ値に応じて、前記第２の記憶手段に記憶された前記複数の部分参照表の中に当該データ値に対応する前記データ範囲を持つ部分参照表がある場合には、当該部分参照表を選択部分参照表として選択し、前記第２の記憶手段に記憶された前記複数の部分参照表の中に当該データ値に対応するデータ範囲を持つ部分参照表がない場合には、当該データ値に対応するデータ範囲を持つ部分参照表を前記参照表から取得し、前記第２の記憶手段に記憶されている前記複数の部分参照表のうちのいずれかを当該取得した部分参照表に変更してから、前記第２の記憶手段内にある当該変更された部分参照表を選択部分参照表として選択し、選択した当該選択部分参照表から当該データ値に対応する参照データを参照する参照手段と、
   前記入力した処理対象データの前記データ値に応じて前記参照手段が前記第２の記憶手段内の前記選択部分参照表から参照した前記参照データを用いて、前記処理対象データに対するデータ処理を行うデータ処理手段と、
   前記入力した処理対象データのデータ値から、今後入力される処理対象データの前記データ値を予測する予測手段と、
   前記予測手段が予測した前記今後入力される処理対象データの前記データ値が、前記第２の記憶手段に記憶された前記複数の部分参照表のいずれの前記データ範囲にも含まれない場合に、前記今後入力される処理対象データの前記データ値を含んだ前記データ範囲に対応する部分参照表を前記参照表から取得し、前記第２の記憶手段に記憶された前記複数の部分参照表のうち、前記選択部分参照表以外の一又は二以上の部分参照表を、当該取得した部分参照表に変更する変更手段と、
   論理仕様を再構成可能な再構成可能回路と、
   前記再構成可能回路の論理仕様を再構成する再構成手段と、
   を備え、
   前記参照手段、前記データ処理手段、及び前記変更手段による各処理の少なくとも一部は、前記再構成可能回路に設定された論理に基づいて行われ、
   前記再構成手段は、前記予測手段が予測した前記今後入力される処理対象データの前記データ値が、前記記憶手段に記憶された前記複数の部分参照表のいずれの前記データ範囲にも含まれない場合に、前記再構成可能回路を再構成して、変更対象となった前記部分参照表を前記変更手段が変更する論理を設定し、かつ、前記部分参照表が変更された後に前記再構成可能回路を再構成して、変更された前記部分参照表を前記参照手段が参照する論理、及び、変更された前記部分参照表の参照結果に基づいて前記データ処理手段がデータ処理を行う論理を設定する、
   ことを特徴とするデータ処理装置。
2. 請求項１に記載のデータ処理装置において、
   前記再構成可能回路は、論理仕様を変更可能な複数の記憶回路を備え、
   前記第２の記憶手段は、二以上の前記論理回路に一又は二以上の前記部分参照表を記憶し、
   前記変更手段は、前記選択部分参照表が記憶されていない前記論理回路に記憶された一又は二以上の前記部分参照表を変更する、
   ことを特徴とするデータ処理装置。
3. 請求項２に記載のデータ処理装置において、
   前記記憶回路の容量は前記参照表の大きさに比べて小さい、ことを特徴とするデータ処理装置。
4. 請求項１に記載のデータ処理装置において、
   前記参照手段により選択されるべき部分参照表が前記第２の記憶手段により記憶されていない場合に、前記予測手段による前記処理対象データの予測態様を変更する予測態様変更手段を備える、ことを特徴とするデータ処理装置。
5. 請求項１乃至４のいずれか１項に記載のデータ処理装置において
   前記処理対象データは、画像を構成する画素データであり、
   前記データ値は、前記画素データの画素値である、ことを特徴とするデータ処理装置。

Images