(57)【特許請求の範囲】
【請求項１】
外部メモリ及びキャッシュメモリに接続される画像処理装置において、
所定の実行順に従って変換後座標を決定するカウンタと、
前記変換後座標に位置する変換後画素の変換後画素値を計算するための変換前座標を計算する座標計算部と、
前記変換前画素を参照して前記変換後画素値を計算することを要求する変換要求を生成するタグチェッカと、
前記変換要求に基づいて、前記変換前座標に位置する変換前画素が前記キャッシュメモリに記憶されている場合に、前記変換前画素を前記キャッシュメモリから読み出す画素参照部と、
前記読み出された変換前画素を参照して、前記変換後画素値を計算する画素値計算部と、
前記変換後画素値を有する変換後画素を前記外部メモリに書き込む出力部と、
を備え、
前記タグチェッカは、前記キャッシュメモリのタグに基づいて、前記変換前画素が前記キャッシュメモリに記憶されているか否かを判定し、前記変換前画素が前記キャッシュメモリに記憶されている場合に、前記変換要求を生成し、前記変換前画素が前記キャッシュメモリに記憶されていない場合に、前記キャッシュメモリのキャッシュライン情報に基づいて、前記キャッシュラインがフェッチ中であるか否かを判定し、前記キャッシュラインがフェッチ中でない場合に第１フェッチ要求を発行する画像処理装置。
【請求項２】
外部メモリ及びキャッシュメモリに接続される画像処理装置において、
所定の実行順に従って変換後座標を決定するカウンタと、
前記変換後座標に位置する変換後画素の変換後画素値を計算するための変換前座標を計算する座標計算部と、
前記変換前画素を参照して前記変換後画素値を計算することを要求する変換要求を生成するタグチェッカと、
前記変換要求に基づいて、前記変換前座標に位置する変換前画素が前記キャッシュメモリに記憶されている場合に、前記変換前画素を前記キャッシュメモリから読み出す画素参照部と、
前記読み出された変換前画素を参照して、前記変換後画素値を計算する画素値計算部と、
前記変換後画素値を有する変換後画素を前記外部メモリに書き込む出力部と、
前記変換要求を保持するバッファと、を備え、
前記カウンタは、前記バッファがフルでない場合に、前記変換後座標を決定する画像処理装置。
【請求項３】
外部メモリ及びキャッシュメモリに接続される画像処理装置において、
所定の実行順に従って変換後座標を決定するカウンタと、
前記変換後座標に位置する変換後画素の変換後画素値を計算するための変換前座標を計算する座標計算部と、
前記変換前画素を参照して前記変換後画素値を計算することを要求する変換要求を生成するタグチェッカと、
前記変換要求に基づいて、前記変換前座標に位置する変換前画素が前記キャッシュメモリに記憶されている場合に、前記変換前画素を前記キャッシュメモリから読み出す画素参照部と、
前記読み出された変換前画素を参照して、前記変換後画素値を計算する画素値計算部と、
前記変換後画素値を有する変換後画素を前記外部メモリに書き込む出力部と、を備え、
前記カウンタは、複数の座標計算アルゴリズムを記憶し、取得した変換パターンに対応する座標計算アルゴリズム示す実行順に従って前記変換後座標を決定し、前記取得した変換パターンに対応する座標計算アルゴリズムを記憶していない場合には、前記取得した変換パターンに最も近い変換パターンに対応する座標計算アルゴリズムを選択する画像処理装置。
【請求項４】
前記画素参照部は、前記キャッシュメモリのタグに基づいて、前記変換前画素が前記キャッシュメモリに記憶されているか否かを判定し、前記キャッシュメモリのキャッシュライン情報に基づいて、前記キャッシュラインがフェッチ中か否であるかを判定し、前記キャッシュラインがフェッチ中でない場合には、第２フェッチ要求を発行する、請求項１乃至３のいずれかに記載の画像処理装置。
【請求項５】
複数の画素を含む画像データを記憶する外部メモリと、
変換前画素を記憶するキャッシュメモリと、
所定の実行順に従って変換後座標を決定するカウンタと、
前記変換後座標に位置する変換後画素の変換後画素値を計算するための変換前座標を計算する座標計算部と、
前記変換前画素を参照して前記変換後画素値を計算することを要求する変換要求を生成するタグチェッカと、
前記変換要求に基づいて、前記変換前座標に位置する変換前画素が前記キャッシュメモリに記憶されている場合に、前記変換前画素を前記キャッシュメモリから読み出す画素参照部と、
前記読み出された前記変換前画素を参照して、前記変換後画素値を計算する画素値計算部と、
前記変換後画素値を有する変換後画素を前記外部メモリに書き込む出力部と、
を備え、
前記タグチェッカは、前記キャッシュメモリのタグに基づいて、前記変換前画素が前記キャッシュメモリに記憶されているか否かを判定し、前記変換前画素が前記キャッシュメモリに記憶されている場合に、前記変換要求を生成し、前記変換前画素が前記キャッシュメモリに記憶されていない場合に、前記キャッシュメモリのキャッシュライン情報に基づいて、前記キャッシュラインがフェッチ中であるか否かを判定し、前記キャッシュラインがフェッチ中でない場合に第１フェッチ要求を発行する画像処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、画像処理装置及び画像処理システムに関する。
【背景技術】
【０００２】
一般的な画像を変換する画像処理装置は、変換された画像（以下、「変換後画像」という）のある座標（以下、「変換後座標」という）に位置する画素（以下、「変換後画素」という）の画素値（以下、「変換後画素値」という）を、変換される前の画像（以下、「変換前画像」という）の座標（以下、「変換前座標」という）のうち、変換後座標に対応する変換前座標に位置する画素（以下、「変換前画素」という）の画素値（以下、「変換前画素値」という）を参照して計算する。
【０００３】
従来の画像処理装置は、外部メモリに接続され、キャッシュメモリを備える。外部メモリには、画像データが記憶される。このような画像処理装置は、外部メモリ上の変換前画素を参照し、変換後画素値を計算し、計算した変換後画素を外部メモリに書き込む。このような画像処理装置は、外部メモリへのアクセス回数を低減するために、変換前画素値を参照する時に、まずキャッシュメモリ上に変換前画素が格納されているかを確認する。格納されている場合は、キャッシュメモリ上に格納されている変換前画素の画素値を用いて、変換後画素値を計算する。キャッシュメモリ上に変換前画素が格納されていない場合には、外部メモリから変換前画像を読み出す。このときに参照される変換前画素に加えて、当該変換前画素の周辺に位置する変換前画素をキャッシュメモリに書き込む。
【０００４】
しかしながら、画像変換のパターンによっては、変換後画素値を計算するのにキャッシュメモリに記憶された変換前画素の一部のみが参照され、キャッシュメモリの利用効率が低下する。
【０００５】
一方、変換後画素値を計算するのに必要な変換前画素がキャッシュメモリに記憶されていない場合には、外部メモリに記憶された変換前画素をキャッシュメモリに転送することを要求するフェッチ要求が発行されるので、外部メモリへのアクセスレイテンシが増加するという問題がある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−２５９８７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明が解決しようとする課題は、キャッシュメモリの利用効率及び外部メモリへのアクセスレイテンシを改善することである。
【課題を解決するための手段】
【０００８】
本発明の実施形態に係る画像処理装置は、外部メモリ及びキャッシュメモリに接続される。画像処理装置は、カウンタと、座標計算部と、タグチェッカと、画素参照部と、画素値計算部と、出力部と、を備える。カウンタは、所定の実行順に従って変換後座標を決定する。座標計算部は、前記変換後座標に位置する変換後画素の変換後画素値を計算するための変換前座標を計算する。タグチェッカは、前記変換前画素を参照して前記変換後画素値を計算することを要求する変換要求を生成する。画素参照部は、前記変換要求に基づいて、前記変換前座標に位置する変換前画素が前記キャッシュメモリに記憶されている場合に、前記変換前画素を前記キャッシュメモリから読み出す。画素値計算部は、前記読み出された変換前画素を参照して、前記変換後画素値を計算する。出力部は、前記変換後画素値を有する変換後画素を前記外部メモリに書き込む。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施形態に係る画像処理システム１の構成を示すブロック図。
【図２】本発明の実施形態に係る画像データのデータ構造を示す概略図。
【図３】本発明の実施形態に係る画像処理装置１０の構成を示すブロック図。
【図４】本発明の実施形態に係るキャッシュラインＣＬｉに格納される変換前画素を説明する概略図。
【図５】第１実施形態に係る画像処理の手順を示すフローチャート。
【図６】第１実施形態に係る変換要求発行の手順を示すフローチャート。
【図７】第１実施形態に係る第１キャッシュ保証の手順を示すフローチャート。
【図８】第１実施形態に係る画像変換の手順を示すフローチャート。
【図９】第１実施形態に係る第２キャッシュ保証の手順を示すフローチャート。
【図１０】第２実施形態に係る変換後座標決定の手順を示すフローチャート。
【図１１】第２実施形態に係る変換パターン毎の実行順を示す概略図。
【図１２】第３実施形態に係る変換後座標決定の手順を示すフローチャート。
【図１３】第３実施形態に係るブロック領域の概略図。
【図１４】第３実施形態の作用効果を説明する概略図。
【発明を実施するための形態】
【００１０】
本発明の実施形態に係る画像処理システムの構成について説明する。図１は、本発明の実施形態に係る画像処理システム１の構成を示すブロック図である。図２は、本発明の実施形態に係る画像データのデータ構造を示す概略図である。
【００１１】
図１の画像処理システム１は、画像処理装置１０と、キャッシュメモリ２０と、外部メモリ３０と、入出力インタフェース４０と、外部バス５１と、内部バス５２と、画像生成装置６０と、ネットワーク７０と、を備える。画像処理装置１０は、複数の画素を有する画像データに所定の画像処理を施す半導体集積回路である。画像処理装置１０は、外部バス５１を介して、外部メモリ３０及び入出力インタフェース４０に接続され、内部バス５２を介して、キャッシュメモリ２０に接続される。変換パターンは、画像生成装置６０のユーザ又は画像生成装置６０の機能を実現するアプリケーションによって決められる。キャッシュメモリ２０は、変換前画素をキャッシュライン単位で記憶するモジュールである。外部メモリ３０は、画像データを記憶するモジュールである。入出力インタフェース４０は、画像生成装置６０と、ネットワーク７０と、に接続される。に接続される。画像生成装置６０は、画像データを生成する半導体集積回路（例えば車載カメラ）である。ネットワーク７０は、例えば有線ネットワーク又は無線ネットワークである。
【００１２】
画像データは、画素値を有する複数の画素を含む。画素値は、画素の色情報（例えば、色調及び階調を表す情報）である。画像処理は、所定の変換パターン（例えば、回転、左右反転、上下反転、拡大、縮小、及び歪み補正）に基づいて、画像の形状を変換する処理である（図２（Ｂ））。図２（Ｂ）は、変換前画像データを時計回りに９０°回転させる変換パターンを示す。変換前画素の位置（変換前座標）は、変換後画像データでは変換後画素の位置（変換後座標）に変わる。
【００１３】
本発明の実施形態に係る画像処理装置の構成について説明する。図３は、本発明の実施形態に係る画像処理装置１０の構成を示すブロック図である。画像処理装置１０は、カウンタ１１と、座標計算部１２と、タグチェッカ１３と、バッファ１４と、画素参照部１５と、画素値計算部１６と、出力部１７と、を備える。キャッシュメモリ２０は、複数のキャッシュラインＣＬｉ（ｉ＝１〜ｎ（ｎは２以上の整数））と、複数のタグ領域Ｔｉと、を備える。各キャッシュラインＣＬｉは、キャッシュラインサイズ分の変換前画素が格納される領域である。各タグ領域Ｔｉは、タグと、キャッシュライン情報と、が格納される領域であり、各キャッシュラインＣＬｉに関連付けられる。タグは、キャッシュラインＣＬｉに格納される変換前画素を特定する情報である。キャッシュライン情報は、キャッシュラインＣＬｉの状態を表す情報である。例えば、キャッシュライン情報は、キャッシュラインＣＬｉがフェッチ中であるか否かと、キャッシュラインＣＬｉに格納される変換前画素が有効であるか否かと、を表す。外部メモリ３０は、変換前画像データが記憶される第１領域ＭＡ１と、変換後画像データが記憶される第２領域ＭＡ２と、を有する。
【００１４】
カウンタ１１は、変換後座標を決定するモジュールである。変換後座標は、第２領域ＭＡ２のアドレスと１対１に対応する。座標計算部１２は、変換前座標を計算するモジュールである。変換前座標は、第１領域ＭＡ１のアドレスと１対１に対応する。タグチェッカ１３は、タグ領域Ｔｉをチェックして、変換要求をバッファ１４に書き込むモジュールである。変換要求は、変換前画素を参照して変換後画素値を計算することを要求するデータである。バッファ１４は、変換要求を一時的に保持するモジュールである。画素参照部１５は、タグ領域Ｔｉをチェックして、対応するキャッシュラインＣＬｉに格納された変換前画素をキャッシュメモリ２０から読み出すモジュールである。画素値計算部１６は、変換後画素値を計算するモジュールである。出力部１７は、第２領域ＭＡ２に変換後画素を書き込むモジュールである。
【００１５】
本発明の実施形態に係るキャッシュラインに格納される変換前画素について説明する。図４は、本発明の実施形態に係るキャッシュラインＣＬｉに格納される変換前画素を説明する概略図である。第１領域ＭＡ１には、キャッシュラインサイズ分の変換前画素（以下、「画素パッケージＰＡＣｊ（ｊ＝１〜ｍ（ｍは２以上の整数））」という）が格納される。各変換前画素は、各画素パッケージＰＡＣｊ内においてラスタスキャン順に配列される。画像処理装置１０によりフェッチ要求が発行されると、画素パッケージＰＡＣｊは、第１領域ＭＡ１からキャッシュラインＣＬｉに転送される。キャッシュラインＣＬｉに画素パッケージＰＡＣｊが格納されると、画素パッケージＰＡＣｊを特定するタグ（例えば、“ｊ”の値）がタグ領域Ｔｉに格納される。
【００１６】
なお、キャッシュラインの数ｎが画素パッケージの数ｍより少ない場合には、１つのキャッシュラインＣＬｉに複数の画素パッケージＰＡＣｊが格納され得る。例えば、“ｎ＝５”且つ“ｍ＝１０”の場合には、キャッシュラインＣＬ１には、画素パッケージＰＡＣ１又はＰＡＣ６が格納され、キャッシュラインＣＬ２には、画素パッケージＰＡＣ２又はＰＡＣ７のどちらかが格納される。すなわち、１つのキャッシュラインＣＬｉには２種類の画素パッケージが格納され得る。
【００１７】
（第１実施形態）
本発明の第１実施形態について説明する。第１実施形態は、変換後画素値を計算する前に、変換後画素値を計算するのに参照される変換前画素をキャッシュメモリに記憶する例である。
【００１８】
第１実施形態に係る画像処理装置の動作について説明する。図５は、第１実施形態に係る画像処理の手順を示すフローチャートである。画像処理装置１０は、変換要求発行（Ｓ５０２）と、画像変換（Ｓ５１２）と、を並行して実行する。Ｓ５０２は、Ｓ５１２に対して、所定の画素数の分だけ先行して実行される。この所定の画素数は、１キャッシュラインに格納される画素数とほぼ同数であるが、これに限られるものではなく、１画素〜ｋ（ｋは、バッファ１４に格納可能な画素の数）画素である。Ｓ５０２及びＳ５１２は、全ての変換前画素についてＳ５１２が完了するまで繰り返し実行される（Ｓ５０４−ＮＯ）。全ての変換前画素についてＳ５１２が完了すると（Ｓ５０４−ＹＥＳ）、画像処理が終了する。
【００１９】
第１実施形態に係る変換要求発行について説明する。図６は、第１実施形態に係る変換要求発行の手順を示すフローチャートである。図７は、第１実施形態に係る第１キャッシュ保証の手順を示すフローチャートである。変換要求発行は、変換前座標及び変換後座標を含む変換要求を発行する処理である。第１キャッシュ保証は、変換要求発行において、変換後画素値を計算するのに参照される変換前画素がキャッシュメモリ２０に記憶されていること、又はキャッシュラインＣＬｉがフェッチ中であることを保証する処理である。
【００２０】
＜Ｓ６０１＞  カウンタ１１は、バッファ１４がフルであるか否かを判定する。バッファ１４がフルでない場合には（Ｓ６０１−ＮＯ）、Ｓ６０２へ進む。バッファ１４がフルである場合には（Ｓ６０１−ＹＥＳ）、バッファに空きができるまで待機する。すなわち、バッファ１４に空き領域がある場合に、Ｓ６０２へ進む。
【００２１】
＜変換後座標決定（Ｓ６０２）＞  カウンタ１１は、所定の実行順に従って変換後座標を決定する。変換後座標は、第２領域ＭＡ２のアドレスに１対１に対応するので、変換後座標が決定すると、決定した変換後座標に位置する変換後画素が格納されるべき第２領域ＭＡ２のアドレスが決定する。実行順は、変換パターンにより決まる。具体的には、カウンタ１１は、入出力インタフェース４０を介して変換パターンを取得し、取得した変換パターンに対応する座標決定アルゴリズムを用いて、変換後座標の値を更新する。すなわち、変換後座標を変換パターンにより決まる実行順（図１１（Ａ）〜（Ｈ））に従ってシフトさせる。
【００２２】
＜変換前座標計算（Ｓ６０３）＞  座標計算部１２は、Ｓ６０２で決定した変換後座標に位置する変換後画素値を計算するための変換前座標を計算する。座標計算部１２は、変換パターンに応じた変換後座標から変換前座標を求める変換式を使う。例えば、回転、縮小、拡大、及び並行移動等の変換パターンの場合には、座標計算部１２は、各変換パターンに応じた変換式（式１を参照）と、変換後座標、と、を用いて変換前座標を計算する。式１において、Ｘ１及びＹ１は変換前座標であり、Ｘ２及びＹ２は変換後座標であり、Ａ〜Ｆは変換パラメータである。式１に示すように、変換後座標（Ｘ２，Ｙ２）が決まると、変換前座標（Ｘ１，Ｙ１）が決まる。
【数１】
0005606341.tif 000002
【００２３】
＜第１キャッシュ保証（Ｓ６０４）＞  タグチェッカ１３は、Ｓ６０３で計算された変換前座標に位置する変換前画素がキャッシュメモリ２０に記憶されているか否かを確認する。変換前画素が記憶されていない場合には、フェッチ要求を発行する。次いで、タグチェッカ１３は、変換前画素を参照して変換後画素値を計算することを要求する変換要求を発行する。
第１キャッシュ保証は、図７の手順に従って実行される。
【００２４】
＜Ｓ７０２＞  タグチェッカ１３は、タグ領域Ｔｉのタグに基づいて、変換後画素値を計算するための変換前画素がキャッシュメモリ２０に記憶されているか否かを判定する。具体的には、タグにより特定される画素パッケージＰＡＣｊの先頭画素の座標（以下、「先頭座標」という）と終端画素の座標（以下、「終端座標」という）との間に、Ｓ６０３で計算された変換前座標が含まれていない場合には、変換後画素値を計算するための変換前画素がキャッシュメモリ２０に記憶されていないと判定され（Ｓ７０２−ＮＯ）、Ｓ７０４へ進む。先頭座標と終端座標との間に変換前座標が含まれている場合には、変換前画素がキャッシュメモリ２０に記憶されていると判定され（Ｓ７０２−ＹＥＳ）、Ｓ７１６へ進む。
【００２５】
例えば、タグチェッカ１３は、式２〜式６を用いてＳ７０２を実行する。式２〜式６において、ｎは１つの画素パッケージＰＡＣに含まれる画素数を示し、ｗは変換前画像領域の横方向の画素数を示す。タグチェッカ１３は、式２及び式３を用いて、ある画素パッケージＰＡＣｊの先頭座標（Ｘｂ，Ｙｂ）を算出し、式４及び式５を用いて、ある画素パッケージＰＡＣｊの終端座標（Ｘｅ，Ｙｅ）を算出する。式２は、Ｘｂが、（ｊ−１）×ｎをｗで割ったときの余りであることを意味する。式４は、Ｘｅが、ｊ×ｎをｗで割ったときの余りであることを意味する。式３及び式５では、右辺は切り捨てられる（すなわち、左辺は整数である）。次いで、タグチェッカ１３は、式６が成立する場合に、変換前画素がキャッシュメモリ２０に記憶されていると判定する。
【数２】
0005606341.tif 000003
【数３】
0005606341.tif 000004
【数４】
0005606341.tif 000005
【数５】
0005606341.tif 000006
【数６】
0005606341.tif 000007
【００２６】
＜Ｓ７０４＞  タグチェッカ１３は、タグ領域Ｔｉのキャッシュライン情報に基づいて、キャッシュラインＣＬｉがフェッチ中か否であるかを判定する。キャッシュラインＣＬｉがフェッチ中でない場合には（Ｓ７０４−ＮＯ）、Ｓ７０６へ進む。キャッシュラインＣＬｉがフェッチ中である場合には（Ｓ７０４−ＹＥＳ）、Ｓ７１６へ進む。
【００２７】
＜第１フェッチ要求発行（Ｓ７０６）＞  タグチェッカ１３は、第１フェッチ要求を発行する。第１フェッチ要求は、キャッシュラインをフェッチ中の状態に更新すると同時に、外部メモリ３０に対して、第１領域ＭＡ１に格納された画素パッケージＰＡＣｊをキャッシュメモリ２０へ転送することを要求する。これにより、新しい変換前画素は、外部メモリ３０へのアクセスの終了後にキャッシュメモリに格納される。タグチェッカ１３は、要求を発行すると、外部メモリ３０へのアクセスの終了を待たずに、Ｓ７１６を実行する。
【００２８】
＜変換要求発行（Ｓ７１６）＞  タグチェッカ１３は、変換要求を発行する。変換要求は、Ｓ６０２で決定された変換後座標と、Ｓ６０３で計算された変換前座標と、を含む。変換要求は、変換前座標を参照して、変換後座標に位置する変換後画素値を計算することを要求する。次いで、タグチェッカ１３は、発行した変換要求をバッファ１４に書き込む。バッファ１４は、画素参照部１５により読み出されるまで変換要求を保持する。Ｓ７１６が終了すると、第１キャッシュ保証が終了し、Ｓ６０５へ進む。
【００２９】
＜Ｓ６０５＞  全ての変換前画素について第１キャッシュ保証が完了するまで（Ｓ６０５−ＮＯ）、Ｓ６０１〜Ｓ６０４は繰り返し実行される。全ての変換前画素について第１キャッシュ保証が完了すると（Ｓ６０５−ＹＥＳ）、変換要求発行が終了し、Ｓ５０４へ進む。
【００３０】
次に、第１実施形態に係る画像変換について説明する。図８は、第１実施形態に係る画像変換の手順を示すフローチャートである。図９は、第１実施形態に係る第２キャッシュ保証の手順を示すフローチャートである。画像変換は、キャッシュメモリ２０に記憶された変換前画素を参照して、変換後画素値を計算する処理である。第２キャッシュ保証は、画像変換において、変換後画素値を計算するための変換前画素がキャッシュメモリ２０に記憶されていることを保証する処理である。
【００３１】
＜Ｓ８０１＞  バッファ１４が空ではない（つまり、バッファ１４に要求がある）場合には（Ｓ８０１−ＮＯ）、Ｓ８０２へ進む。バッファ１４が空である（つまり、バッファ１４に要求がない）場合には（Ｓ８０１−ＮＯ）、バッファが空ではなくなった後に、Ｓ８０２へ進む。すなわち、バッファ１４に少なくとも１つの要求がある場合に、Ｓ８０２へ進む。
【００３２】
＜第２キャッシュ保証（Ｓ８０２）＞  画素参照部１５は、第１キャッシュ保証でバッファ１４に保持された変換要求の変換前座標に位置する変換前画素がキャッシュメモリ２０に記憶されている場合に、変換前画素をキャッシュメモリ２０から読み出す。第２キャッシュ保証は、図９の手順に従って実行される。
【００３３】
＜Ｓ９０２＞  画素参照部１５は、タグに基づいて、第１キャッシュ保証でバッファ１４に保持された変換要求の変換前座標に位置する変換前画素がキャッシュメモリ２０に記憶されているか否かを判定する。具体的には、先頭座標と終端座標との間に変換要求の変換前座標が含まれていない場合には、変換前座標に位置する変換前画素がキャッシュメモリ２０に記憶されていないと判定され（Ｓ９０２−ＮＯ）、Ｓ９０４へ進む。先頭座標と終端座標との間に変換前座標が含まれている場合には、変換前座標に位置する変換前画素がキャッシュメモリ２０に記憶されていると判定され（Ｓ９０２−ＹＥＳ）、Ｓ９１６へ進む。
【００３４】
＜Ｓ９０４＞  画素参照部１５は、キャッシュライン情報に基づいて、キャッシュラインＣＬｉがフェッチ中か否であるかを判定する。キャッシュラインＣＬｉがフェッチ中でない場合には（Ｓ９０６−ＮＯ）、Ｓ９０６へ進む。キャッシュラインＣＬｉがフェッチ中である場合には（Ｓ９０６−ＹＥＳ）、Ｓ９０２へ戻る。
【００３５】
＜第２フェッチ要求（Ｓ９０６）＞  画素参照部１５は、第２フェッチ要求を発行する。第２フェッチ要求は、外部メモリ３０に対して、第１領域ＭＡ１に格納された画素パッケージＰＡＣｊをキャッシュメモリ２０へ転送することを要求する。これにより、新しい変換前画素がキャッシュメモリ２０に記憶される。Ｓ９０６が終了すると、Ｓ９０２へ戻る。
【００３６】
＜画素読み出し（Ｓ９１６）＞  画素参照部１５は、キャッシュメモリ２０から変換前画素を読み出す。具体的には、画素参照部１５は、キャッシュラインＣＬｉに記憶された画素パッケージＰＡＣｊのうち、変換要求の変換前座標に位置する変換前画素を読み出す。Ｓ９１６が終了すると、第２キャッシュ保証が終了し、Ｓ８０３へ進む。
【００３７】
＜変換後画素値計算（Ｓ８０３）＞  画素値計算部１６は、キャッシュメモリ２０から読み出された変換前画素を参照して、変換後画素値を計算する。具体的には、画素値計算部１６は、入出力インタフェース４０を介して変換パターンを取得し、取得した変換パターンに対応する画素値計算アルゴリズムを用いて、読み出された変換前画素を参照して、変換後画素値を計算する。
【００３８】
＜変換後画素出力（Ｓ８０４）＞  出力部１７は、Ｓ８０３で計算された変換後画素値を有する変換後画素を外部メモリ３０に書き込む。具体的には、出力部１７は、バッファ１４に保持された変換要求の変換後座標に対応する第２領域ＭＡ２のアドレスに変換後画素を書き込む。
【００３９】
＜Ｓ８０５＞  全ての変換前画素について第２キャッシュ保証が完了するまで（Ｓ８０５−ＮＯ）、Ｓ８０１〜Ｓ８０４は繰り返し実行される。全ての変換前画素について第２キャッシュ保証が完了すると（Ｓ８０５−ＹＥＳ）、画像変換が終了し、Ｓ５０４へ進む。
【００４０】
第１実施形態によれば、画素変換において変換後画素値を計算する前に、変換後画素値を計算するのに参照される変換前画素をキャッシュメモリに記憶する。その結果、外部メモリ３０へのアクセスが不要になる。これにより、キャッシュメモリ２０の利用効率及び外部メモリ３０へのアクセスレイテンシを改善することができる。
【００４１】
（第２実施形態）
本発明の第２実施形態について説明する。第２実施形態は、変換後座標を決定するときに、変換パターンに応じて変換後座標を決定する例である。なお、第１実施形態と同様の説明は省略する。
【００４２】
第２実施形態に係る画像処理装置の動作について説明する。図１０は、第２実施形態に係る変換後座標決定の手順を示すフローチャートである。図１１は、変換パターン毎の実行順を示す概略図である。第２実施形態に係る変換後座標決定は、カウンタ１１により実行される処理である。すなわち、第２実施形態に係る変換後座標決定は、バッファ１４に空きがある場合に実行される。
【００４３】
＜変換パターン取得（Ｓ１００２）＞  カウンタ１１は、入出力インタフェース４０を介して画像生成装置６０から供給される変換パターンを取得する。変換パターンは、例えば任意の角度で画像を回転させるパターンを示す情報であって、例えば画像生成装置６０のユーザ又は画像生成装置６０の機能を実現するアプリケーションによって決められる。
【００４４】
＜Ｓ１００４＞  カウンタ１１は、取得した変換パターンに対応する座標計算アルゴリズムの有無を判定する。カウンタ１１の内部メモリには、例えば複数の座標計算アルゴリズムが記憶されている。各座標計算アルゴリズムは、図１１に示すような所定の変換パターンの実行順を示す。図１１（Ａ）はラスタスキャンの、図１１（Ｂ）は４５°回転の、図１１（Ｃ）は９０°回転の、図１１（Ｄ）は１３５°回転の、図１１（Ｅ）は１８０°回転の、図１１（Ｆ）は２２５°回転の、図１１（Ｇ）は２７０°回転の、図１１（Ｈ）は３１５°回転の、実行順を示す。取得した変換パターンに対応する座標計算アルゴリズムがある場合には（Ｓ１００４−ＹＥＳ）、Ｓ１００６へ進む。取得した変換パターンに対応する座標計算アルゴリズムがない場合には（Ｓ１００４−ＮＯ）、Ｓ１０１６へ進む。
【００４５】
＜アルゴリズム選択（Ｓ１００６）＞  カウンタ１１は、複数の座標計算アルゴリズムの中から、取得した変換パターンに対応する座標計算アルゴリズムを選択する。例えば、取得した変換パターンが４５°回転の場合には、図１１（Ｂ）の４５°回転の実行順を示す座標計算アルゴリズムが選択される。
【００４６】
＜近似アルゴリズム選択（Ｓ１０１６）＞  カウンタ１１は、複数の座標計算アルゴリズムの中から、取得した変換パターンに最も近い変換パターンに対応する座標計算アルゴリズム（すなわち、取得した変換パターンの実行順に最も近い実行順を示す座標計算アルゴリズム）を選択する。例えば、取得した変換パターンが１００°回転の場合には、図１１（Ｃ）の９０°回転の実行順を示す座標計算アルゴリズムが選択される。
【００４７】
＜変換後座標シフト（Ｓ１００８）＞  カウンタ１１は、Ｓ１００６又はＳ１０１６で選択された座標計算アルゴリズムに従って変換後座標を決定する。具体的には、カウンタ１１は、選択された座標決定アルゴリズムを用いて、変換後座標の値を更新する。変換後座標は、変換パターンに一致する又は変換パターンに近似する実行順に従ってシフトする。
【００４８】
＜Ｓ１００９＞  全ての変換後座標についてＳ１００８が完了するまで（Ｓ１００９−ＮＯ）、Ｓ１００８は繰り返し実行される。全ての変換後座標についてＳ１００８が完了すると（Ｓ１００９−ＹＥＳ）、Ｓ６０３へ進む。Ｓ６０３〜Ｓ６０５は、第１実施形態と同様である。
【００４９】
なお、第２実施形態では、画像生成装置６０が座標計算アルゴリズムを選択しても良い。この場合には、複数の座標計算アルゴリズムを画像生成装置６０の内部メモリに予め記憶させておく。画像生成装置６０は、変換パターンに対応する座標計算アルゴリズムを選択し、画像データとともに画像処理装置１０に供給する。カウンタ１１は、Ｓ１００２において、入出力インタフェース４０を介して画像生成装置６０から供給される変換パターンに加えて、座標計算アルゴリズムを取得する。この場合には、Ｓ１００４、Ｓ１００６、及びＳ１０１６は省略される。
【００５０】
第２実施形態によれば、変換パターンに応じて選択された座標計算アルゴリズムを用いて変換後座標が決定される。このため、変換パターンと一致する又は変換パターンに近似する実行順に従い、変換前画素がキャッシュメモリ２０に記憶される。その結果、ある変換後画素を計算するための変換前画素が、それ以前の変換後画素を計算するときに、すでにキャッシュメモリ２０上に記憶されている可能性が高くなる。これにより、キャッシュメモリ２０の利用効率及び外部メモリ３０へのアクセスレイテンシを第１実施形態よりも改善することができる。周辺画素を含む複数の変換前画素を参照して変換後画素値を計算する必要がある場合（例えば、１００°回転の場合）には、第２実施形態が特に有効である。
【００５１】
（第３実施形態）
本発明の第３実施形態について説明する。第３実施形態は、変換後座標を決定するときに、所定のブロック単位で変換後座標を決定する例である。なお、上述の実施形態と同様の説明は省略する。
【００５２】
第３実施形態に係る画像処理装置の動作について説明する。図１２は、第３実施形態に係る変換後座標決定の手順を示すフローチャートである。図１３は、第３実施形態に係るブロック領域の概略図である。
【００５３】
＜ブロック領域設定（Ｓ１２０２）＞  カウンタ１１は、第２領域ＭＡ２に複数のブロック領域を設定する。各ブロック領域は、第２領域ＭＡ２の任意の一点を始点とし、キャッシュメモリ２０のキャッシュラインサイズに相当する縦及び横の大きさを持つ矩形状の領域内に位置する変換後画素が格納される領域である。ブロック領域は、図１３に示すように、例えば点（０，０）を始点として、キャッシュラインサイズ１００に相当する１００×１００の矩形状の領域内に位置するような変換後画素を格納する第２領域ＭＡ２の一部である。
【００５４】
＜変換後座標更新（Ｓ１２０４）＞  カウンタ１１は、Ｓ１２０２で設定されたブロック領域毎に、所定の実行順に従って変換後座標を決定する。すなわち、カウンタ１１は、画像データ全体ではなく、ブロック領域毎に、変換後座標を所定の実行順に従って決定する。
【００５５】
＜Ｓ１２０６＞  設定された全てのブロック領域について変換後座標更新が完了するまで（Ｓ１２０６−ＮＯ）、Ｓ１２０４は繰り返し実行される。設定された全てのブロック領域について変換後座標更新が完了すると（Ｓ１２０６−ＹＥＳ）、Ｓ６０３へ進む。Ｓ６０３〜Ｓ６０５は、ブロック領域毎に実行される。
【００５６】
第３実施形態の作用効果について説明する。図１４は、第３実施形態の作用効果を説明する概略図である。図１４は、図１１の実行順に対応する変換パターンと一致しない回転角度（８０°）で画像を回転させる例を示す。図１４（Ａ）は、ブロック領域に限らず連続する２５画素を図１１（Ｃ）の実行順で変換する例であり、図１４（Ｂ）は、連続する２５画素をブロック領域において変換する例である。
【００５７】
従来技術では、変換前画素は、キャッシュラインサイズ単位（すなわち、画素パッケージ単位）でキャッシュメモリ２０に転送される。しかしながら、図１４（Ａ）に示すような８０°回転の場合には、変換後画素値を計算するときに、変換前画素の一部（画素ＰＸ１及びＰＸ２）のみが図１４（Ａ）の連続する２５画素を変換するために参照される。
【００５８】
一方、第３実施形態では、変換前画素のパック中の画素は、ブロック中の連続する25画素の変換において多く参照される（画素ＰＸ１からＰＸ5）。すなわち、第3実施形態（図１４（Ｂ））は、従来（図１４（Ａ））に比べて、キャッシュメモリ２０に記憶されたキャッシュラインサイズ単位のデータの利用効率が高いことを示す。
【００５９】
第３実施形態によれば、ブロック領域毎に変換後座標が決定され、変換後座標決定後の処理はブロック領域毎に実行される。その結果、変換後画素値を計算するのに参照される変換前画素がキャッシュメモリ２０に記憶されている間（すなわち、キャッシュメモリ２０に記憶された変換前画素が削除される前）に、変換後画素値計算が実行される。これにより、キャッシュメモリ２０の利用効率及び外部メモリ３０へのアクセスレイテンシが第１実施形態よりも改善する。複数の変換前画素を参照して変換後画素値を計算する場合には、第３実施形態が特に有効である。
【００６０】
また、第３実施形態は、第２実施形態と組み合わせても良い。この場合には、Ｓ１２０２と、Ｓ１００２〜Ｓ１００６及びＳ１０１６と、が順不動に実行される。これにより、キャッシュメモリ２０の利用効率及び外部メモリ３０へのアクセスレイテンシを第２実施形態よりも改善することができる。
【００６１】
また、第２及び第３実施形態は、それぞれ、第１実施形態から独立しても良い。この場合には、図１０又は図１２の変換後座標決定が終了した後に、従来と同様に、変換前画素を参照して変換後画素値が計算される。
【００６２】
また、第２又は第３実施形態では、変換後座標決定が終了した後の第１キャッシュ保証が省略されても良い。すなわち、図１０又は図１２の変換後座標決定が完了した後に、変換前座標計算を実行する。この場合には、タグチェッカ１３及びバッファ１４は不要である。
【００６３】
本実施形態に係る画像処理システム１の少なくとも一部は、ハードウェアで構成しても良いし、ソフトウェアで構成しても良い。ソフトウェアで構成する場合には、画像処理システム１の少なくとも一部の機能を実現するプログラムをフレキシブルディスクやＣＤ−ＲＯＭ等の記録媒体に収納し、コンピュータに読み込ませて実行させても良い。記録媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記録媒体でも良い。
【００６４】
また、本実施形態に係る画像処理システム１の少なくとも一部の機能を実現するプログラムを、インターネット等の通信回線（無線通信も含む）を介して頒布しても良い。さらに、同プログラムを暗号化したり、変調をかけたり、圧縮した状態で、インターネット等の有線回線や無線回線を介して、あるいは記録媒体に収納して頒布しても良い。
【００６５】
なお、本発明は、上述した実施形態に限定されるものではなく、その要旨を逸脱しない範囲で構成要素を変形して具体化される。また、上述した実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明が形成可能である。例えば、上述した実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００６６】
１  画像処理システム
１０  画像処理装置
１１  カウンタ
１２  座標計算部
１３  タグチェッカ
１４  バッファ
１５  画素参照部
１６  画素値計算部
１７  出力部
２０  キャッシュメモリ
３０  外部メモリ
４０  入出力インタフェース
５１  外部バス
５２  内部バス
６０  画像生成装置
７０  ネットワーク
【図１】
0005606341.tif 000008
【図２】
0005606341.tif 000009
【図３】
0005606341.tif 000010
【図４】
0005606341.tif 000011
【図５】
0005606341.tif 000012
【図６】
0005606341.tif 000013
【図７】
0005606341.tif 000014
【図８】
0005606341.tif 000015
【図９】
0005606341.tif 000016
【図１０】
0005606341.tif 000017
【図１１】
0005606341.tif 000018
【図１２】
0005606341.tif 000019
【図１３】
0005606341.tif 000020
【図１４】
0005606341.tif 000021