(57)【特許請求の範囲】
【請求項１】
行及び列からなるマトリックスのデータ項目へのアクセスが行方向に順次的に走査するよう移動される窓に制限され、各走査は列方向に順次的な位置で行われるようプログラムされたプロセッサと、
データ項目の行の束からデータ項目をキャッシュするよう配置され、最先にキャッシュされた束の中の行からの第１のデータ項目に対し使用された格納場所が再使用のため利用できるようにされ、最新にキャッシュされた行からの第２のデータ項目を取り込むよう構成されたキャッシュメモリとを含む装置であって、
上記最先の行及び上記最新の行は上記窓の最先の行及び最新の行であり、
上記マトリックスの行方向における上記第１のデータ項目の位置は、上記マトリックスの行方向における上記第２のデータ項目の位置の後に続き、
上記プロセッサが直接的に順次の走査間で上記窓を移動させるとき、上記プロセッサは上記窓を少なくとも２行に亘るブロックずつ列方向に移動させ、
上記窓を移動する方法は、上記行の束のうち少なくとも２つのキャッシュされた行の最先の群の第１のデータ項目に対し使用された第１の群の格納場所が再使用のため利用できるようにされ、上記少なくとも２つのキャッシュされた行の最新の群の第２のデータ項目を上記キャッシュメモリ中に取り込み、このとき上記最先の群及び上記最新の群は、夫々ブロックの寸法を有し上記窓の上部及び底部から互いに向かって延在することを特徴とする装置。
【請求項２】
上記第２のデータ項目は上記第１のデータ項目を上記キャッシュメモリ中で置換する請求項１記載の装置。
【請求項３】
上記窓の高さは上記ブロックの高さの整数倍でない請求項１記載の装置。
【請求項４】
各走査が列方向に順次的な位置で行なわれるよう窓を行方向に順次的に走査し、
キャッシュメモリ中のデータ項目の行の束からデータ項目をキャッシュし、
上記窓が行方向に移動するとき、上記行の束の最先にキャッシュされた行からの第１のデータ項目に対し使用された格納場所が再使用のため利用できるようにされる段階と、最新にキャッシュされた行からの第２のデータ項目を上記キャッシュメモリ中に取り込む段階とを有し、アクセスが二次元マトリクスのデータ項目の移動される窓に制限される上記データ項目をキャッシュする方法であって、
上記最先の行及び上記最新の行は上記窓の最先及び最新の行であり、
上記マトリクスの行方向における第１のデータ項目は、上記マトリクスの行方向における第２のデータ項目の位置の後に続き、
上記窓を直接的に順次の走査間で移動させるとき、上記窓を少なくとも２行に亘るブロックずつ列方向に移動させ、
上記窓を移動する方法は、上記行の束のうち少なくとも２つのキャッシュされた行の最先の群の第１のデータ項目に対し使用された第１の群の格納場所が再使用のため利用できるようにし、上記少なくとも２つのキャッシュされた行の最新の群の第２のデータ項目を上記キャッシュメモリ中に取り込み、このとき上記最先の群及び上記最新の群は、夫々ブロックの寸法を有し上記窓の上部及び底部から互いに向かって延在させることを特徴とする方法。
【発明の詳細な説明】
【０００１】
本発明は、移動窓にアクセスするためにデータ項目をキャッシュする方法に関する。更に、本発明は、上記方法を適用する装置に関する。
【０００２】
米国特許第５，６０２，９８４号は、カメラ画像からピクセルデータをキャッシュするキャッシュメモリを具備する装置を開示する。この装置は、画像全体を記憶するメインメモリと、画像の小さいサブセットを記憶するキャッシュメモリとを含む。プロセッサは、ピクセルの行列（Ｘ，Ｙ）アドレスを用いてキャッシュメモリをアドレス指定する。キャッシュメモリは、（Ｘ，Ｙ）アドレスをキャッシュメモリ中のアドレスに変換し、アドレス指定されたデータにアクセスする。キャッシュメモリ中に存在しない（Ｘ，Ｙ）格納場所にデータが読み込まれた場合、データはプロセッサに戻される前にキャッシュメモリから取り込まれる。
【０００３】
一例によると、（Ｘ，Ｙ）アドレスをキャッシュメモリ中のアドレスに変換することは、Ｘアドレスを得てＹアドレスの最下位部分と混合することを伴う。アドレス指定されたデータがキャッシャメモリ中に存在するか否かの確認は、Ｘアドレスのために記憶されたタグを含むＹアドレスの最上位部分とＹアドレスの最下位部分とを比較することで実施される。
【０００４】
画像処理中、画像におけるピクセルへのアクセスは、画像中の移動窓のピクセルにしばしば制限される。このような窓は、何回かに亘って行（Ｘ）方向に段々に走査され、各走査は異なる列（Ｙ）位置に対して行なわれる。キャッシュは、幾つかの行のピクセルのためにピクセルデータを記憶する。窓が行方向にある幾つかのＸ位置に沿って移動するとき、最新の行のＸ位置におけるピクセルデータのみがキャッシュメモリの中に記憶されない。このデータは取り込まれ、キャッシュメモリ中の最先の行のＸ位置と同じＸ位置におけるデータと置換される。従って、行方向の各走査では、メインメモリから全てのデータを新しく取り込む必要はない。
【０００５】
本発明は、多数の目的の中でもとりわけ、画像中の移動窓にアクセスが制限されるときデータを記憶するために必要なキャッシュメモリの量を減少することを目的とする。
【０００６】
本発明による方法は、請求項１に記載される。第１の位置が第２位置の後に続くところで最新の行の第２のＸ位置におけるデータがキャッシュメモリ中に取り込まれるとき、最先の行の第１のＸ位置に対するキャッシュアドレスが再使用のため利用できるようにされることにより、最先の行及び最新の行が夫々同じ窓中にあってもよい。これは、新しいデータが取り込まれたＸ位置においてデータが置換されるため、最先の行は窓の外側にあるべきであるといった米国特許第５，６０２，９８４号において開示することと対比し、このＸ位置はまだ窓のＸ位置の範囲の一部である。
【０００７】
一実施例では、第２のＸ位置におけるデータは、第１のＸ位置におけるデータに対して使用されたキャッシュアドレスに記憶される。従って、最小限度のキャッシュメモリは窓によって影響を与えられる。しかしながら、この直接的な置換は必要なく、キャッシュメモリが窓中のデータ以外の他のデータをキャッシュするためにも使用される場合、再使用のため利用できるようにすることでこれら他の目的のためにも場所を提供し得る。この場合、本発明は、窓に必要なデータがキャッシュの最小部分を占めることを確実にする。連想キャッシュメモリ、セット連想キャッシュメモリ、又は、直接マップされたキャッシュメモリがこの目的のために使用され得る。直接マップされたキャッシュメモリの場合、当然のことながら他の目的とまだキャッシュメモリ関して衝突し得るが、本発明はこれらの衝突を最小化する。
【０００８】
本発明の一実施例において、窓は、行方向の順次の走査間で少なくとも２行に亘る大きさのブロックづつ移動する。この場合、第１の行の群上にある第１のデータ項目の群が再使用のため利用できるようにされ、第２の行の群上にある第２のデータ項目の群が取り込まれ、このとき第１のデータ項目の群及び第２のデータ項目の群は、夫々ブロックの大きさを有し窓の上部及び底部から互いに向かって延在する。
【０００９】
窓が列（Ｙ）方向に整数分のブロックだけ延在しないとき、第１のデータ項目の群は異なる第２の群の一部として異なる時に取り込まれる。
【００１０】
本発明の上記及び他の利点は、幾つかの図面を使用して以下に説明される。
【００１１】
図１は、キャッシュメモリ１０と、プロセッサ１６と、メインメモリ１８とを有する装置を示す図である。キャッシュメモリ１０は、キャッシュ制御ユニット１４及びメモリユニット１２を含む。プロセッサ１６は、アドレス出力及びデータ入力／出力を有する。アドレス出力は、キャッシュ制御ユニット１４に結合される。キャッシュ制御ユニット１４は、メモリユニット１２に結合されたローカルアドレス出力、及び、メインメモリ１８に結合されたアドレス出力及び制御出力を有する。メモリユニット１２は、プロセッサ１６のデータ入力／出力に結合された第１のデータ入力／出力と、メインメモリ１８に結合された第２のデータ入力／出力とを有する。
【００１２】
動作中、画像（例えば、テレビジョン装置中で受信されたカメラ画像）のためのピクセルデータは、メインメモリ１８中に記憶される。プロセッサ１６は、このピクセルデータを処理する。プロセッサ１６がピクセルデータを読み込まなければならない場合、プロセッサ１６はピクセルデータをアドレス指定するメモリアドレスを生成する。キャッシュ制御ユニット１４は、これらのメモリアドレスを受信し、データがキャッシュメモリユニット１２中で記憶されるアドレスを決定し、その決定されたアドレスをメモリユニット１２に与え、このメモリユニット１２はピクセルデータをプロセッサ１６に供給する。
【００１３】
アドレス指定されたデータがメモリユニット１２中に記憶されていない場合、キャッシュ制御ユニット１４はメインメモリ１８をアドレス指定し、このメインメモリ１８はメモリユニット１２にデータを戻し、メモリユニット１２はデータをプロセッサ１６に送りキャッシュ制御ユニット１４によって指定されたアドレスにデータを記憶する。このデータをメモリユニット１２中に記憶した後、メモリユニット中にこのアドレスで予め記憶されたデータはもはやメモリユニット１２から利用できなくされる。
【００１４】
画像はメモリ中で、対応する（ｘ，ｙ）座標と関連するピクセルデータの集まりとして表わされる。一般的に座標（ｘ，ｙ）と関連するピクセルデータが記憶されるアドレスＡは、
A=A0+F*(x+LX*y)
として表わされ得、このときＡ０はベースアドレス、ＬＸは画像のＸ方向の寸法、Ｆは一つのピクセルが占めるアドレス位置の数である。
【００１５】
多くの画像処理プログラムが、ピクセルの移動窓のピクセルデータにアクセスする。このような窓は、例えば、垂直方向（ｙ方向）に８ピクセル、水平方向（ｘ方向）に８ピクセルの寸法を有する。プログラム中の一つの特定の目的のための画像へのアクセスは、常に窓中のピクセルに制限される。処理中、窓は、一般的に画像上を左から右へ順次的な水平走査によって走査され、窓のｙ位置は走査毎に増進する。
【００１６】
図２は、画像２１中の窓２０の例を示す図である。窓２０は、幅がｘ方向にＮＸピクセル、高さがＹ方向にＮＹピクセルの寸法を有する。各走査を完了する度（窓が画像の右の境界に到達するとき）、窓はＹ方向にＭピクセルだけ下がる。
【００１７】
画像の圧縮に対する動作ベクトルを見つけるためのアルゴリズムの例では、アルゴリズムは４対８（Ｂｘ＝４、Ｂｙ＝８）ピクセルのブロックにおけるピクセルと、５６対１０ピクセル（Ｎｘ＝５６、Ｎｙ＝１０）の窓におけるピクセルとを比較する。従って、４×８ブロックの所与の位置において、画像へのアクセスは１０×５６の窓に制限される。一つの４×８ブロックを考慮した後、新しいブロック、即ち、古いブロックからｘ方向に右に８位置移動したブロックが考慮される。このとき、古い窓から右に８位置移動した窓中のピクセルへのアクセスを伴う。これは、窓がｘ方向に走査されるよう何回か繰り返される。各走査後、窓はＭ＝４のブロックだけ下に移動され処理は繰り返される。
【００１８】
装置では、ピクセルデータにおけるＮＹ行のピクセルデータは、キャッシュメモリ１２中に効果的に記憶されるが、これらの行の数はキャッシュメモリ１２中に完全に記憶されない。つまり、キャッシュメモリ１２は、画像２１中から窓２０中の行の数、即ち窓２０中の最先の行２０から窓２０中の最新の行までの数、と同じ数の行のピクセルから有効なピクセルデータを記憶する。
【００１９】
窓がｘ方向に移動するとき、窓２０の右下コーナー２６のピクセルデータのみがキャッシュメモリ１２中に存在しない。これは、画像からＭ行のデータ、即ち、２つの水平走査の間で窓が下に移動する行の数に関連する。窓２０の右側におけるｘ位置のこの行のピクセルデータは、窓が移動すると取り込まれる。同時に、窓の左上コーナー２８におけるＭ行のデータが今後アクセスされないことは既知である。従って、左上コーナーの行のデータに使用されるキャッシュ１０のメモリユニット１２中のメモリ格納場所は、メインメモリ１８からの他のデータを記憶するために利用できるようにされ得る。
【００２０】
従って、画像の同じ列の行の数からのピクセルデータを記憶するために使用されたアドレスは再使用のため利用できるようにされる。先行する行のピクセルデータに使用された全てのキャッシュアドレスが再使用のため利用できるようにされる前に、上の行以外の全ての行のためにこのアドレスが再使用のため利用できるようにされることに注意すべきである。
【００２１】
キャッシュメモリ１０中にロードされた左下コーナーのデータは、窓２０が画像の（ＮＹ−Ｍ）行だけ下に、又、ＮＸ列だけ右に移動した後、もはや必要なくなる。このとき、メモリユニット１２中のメモリアドレスは、他のデータを記憶するよう再使用のため再び利用できるようにされる。
【００２２】
（ＮＹ−Ｍ）がＭ（各水平走査後に窓２０が下に移動するブロックの大きさ）の整数倍でない場合、右下コーナーの異なる行のデータをロードする同じ走査中に使用される異なるキャッシュアドレスの第１の部分が第１の水平走査中に再使用のため利用できるようにされる。これら異なるキャッシュアドレスの第２の部分は、第１の走査に後続する第２の走査中に利用できるようにされる。特に、ｉ＊Ｍ＜ＮＹ−Ｍ＜（ｉ＋１）＊Ｍ（ｉは整数）のとき、窓２０の右下コーナーにおける上のＮＹ−Ｍ−ｉ＊Ｍピクセルに使用されたアドレスは、ロードしたｉ走査後に再使用するために利用できるようにされ、残りの行のために使用されたアドレスはそれらがロードされたｉ＋１走査後に再使用のために利用できるようにされる。
【００２３】
利用できるようにされた位置（窓の左上コーナー２８のデータに使用された位置）は、窓の右下コーナー２６のデータのために使用される位置であることが好ましい。つまり、ベクトル（ＮＸ，ＮＹ）によって互いから移動するピクセルデータは、キャッシュメモリ１０中の同じアドレスに記憶される。この場合、キャッシュ制御ユニット１４は、この位置のためにメインメモリアドレスをメモリユニット１２中の適当なアドレスに変換しなくてはならない。キャッシュ制御ユニット１４は、例えば、画像中のピクセルのＸ、Ｙ座標からキャッシュアドレスＡを
Acache=B0+F*{(X+LX*Y)mod(NX+(NY-M)*LX)}
に基づいて計算し得、このとき、（Ｂ０はベースアドレス、“ｍｏｄ”はモジュロ関数であり、ａ＝ｎｍｏｄｍの場合、ｎ＝ａ＋ｍ＊ｉとなるようａはゼロ以上ｍ未満の数であり、ｉは整数である）。このようなアドレス計算を用いると、窓２０の左上におけるＭピクセルの列に対するキャッシュアドレスは、窓２０の右下におけるＭピクセルの列に対するキャッシュアドレスと同じになる。
【００２４】
ピクセルデータのメインメモリアドレスＡｍａｉｎ（Ａｍａｉｎ＝Ａ０＋Ｆ（Ｘ＋ＬＸ＊Ｙ））に関して、キャッシュ制御ユニット１４は、
Acache=B0+(Amain-A0)modF*(NX+(NY-M)*LX)
に基づいてキャッシュアドレスを計算し得る。
【００２５】
しかしながら、窓２０が徐々に走査されることが既知であるため、キャッシュ制御ユニットは毎回“ｍｏｄ”関数を改めて計算する必要がない。窓２０の左上コーナーのピクセルデータのメインメモリアドレスＡｍａｉｎ（ＵＬ）が
Amain(UL)-A0=C0(Amain(UL)-A0modF*(NX+(NY-M)*LX)
から得られることが既知である場合、窓中の他のピクセル座標ＸＹのためのキャッシュアドレスＡｃａｃｈｅ（ＸＹ）は、
Acache(XY)=(Amain(XY)-A0)+D
から得られ、このとき
Amain(XY)-A0<C0+F*(NX+(NY-M)*LX)の場合
D=C0であり、
その他の場合
D=C0-F*(NX+(NY-M)*LX)であり、
Ｆ＊（ＮＸ＋（ＮＹ−Ｍ）＊ＬＸ）は、全てのピクセルに対して固定された数である。結果として、Ａｃａｃｈｅは加算、及び／又は、減算と、Ｄに対して第１の値か第２の値かのいずれかを使用するべきかの試験を使用して計算され得る。窓２０が移動する度、Ｃ０は予め決定されるべきだが、これも加算、及び／又は、減算と試験のみを要求する。その結果、キャッシュ制御ユニット１４中のＡｃａｃｈｅの計算は、簡単な算術回路を用いて実行され得る。
【００２６】
画像２１に沿って窓２０を走査する際、プロセッサ１６は画像の寸法、窓の寸法（ＮＸ，ＮＹ）、及び、窓２０が順次の走査間で移動するブロックの寸法（Ｍ）に関する情報をキャッシュ制御ユニット１４に送る。例えば、プロセッサは、ベースアドレスＡ０に関する情報と併せてＦ＊（ＮＸ＋（ＮＹ−Ｍ）＊ＬＸ）をキャッシュ制御ユニット１４に送り得る。キャッシュ制御ユニット１４は、この情報を用いてキャッシュメモリ中のアドレスの再使用を制御する。当然のことながら、これらの数が常に等しい専用のプロセッサでは、キャッシュ制御ユニット１４のプログラミングは事前に設定され得る。
【００２７】
アドレスをメモリユニット１２のアドレスに変換することは、キャッシュ制御ユニット１４の代わりにプロセッサ１６によって実施され得る。
【００２８】
プロセッサ１６は、窓２０中のピクセルをそれらのメモリアドレスを用いてアドレス指定する代わりに、窓に対するピクセルの位置を用いてピクセルをアドレス指定し得る。この場合、アドレスの計算は同じであるが、オフセットが異なる。
【００２９】
一実施例では、プロセッサ１６は窓２０の動きをキャッシュ制御ユニットに明確にシグナルし、キャッシュ制御ユニットはピクセルデータを右下コーナー２６に取り込み得、左上コーナー２８のアドレスを再使用のため利用できるようにし得る。選択的に、キャッシュ制御ユニット１４は、右下コーナー２６のピクセルのアドレス指定を検知し得、この検知に対して左上コーナーのアドレスを再使用のために利用できるようにしこのアドレスにデータを取り込むことで応答する。別の選択肢では、キャッシュ制御ユニット１４は、右下コーナー２６のピクセルのアドレス指定を検知した際に、若しくは、窓２０の動きに対する明確なシグナリングの際に、右下コーナー２６の右側のピクセルデータを予め取り込んでもよい。従って、プロセッサ１６はキャッシュ中で間違いをすることはない。
【００３０】
右下コーナー２６のデータを左上コーナーのアドレスでメモリユニット１２中に記憶する代わりに、キャッシュ制御ユニット１４は、これらのアドレスが他のデータ（例えば、画像以外からのデータ）をキャッシュするため、又は、窓を使用する処理と平行に行う他の処理のために使用されてもよいようこれらのアドレスを単に「再使用のため利用できる」とマークし得る。この場合、連想キャッシュ又はｎ通りのセット連想キャッシュを使用することが好ましい。本発明は、窓を用いてキャッシュメモリ中で最小の空間を占めることを可能にする。
【００３１】
当然のことながら、本発明は図２に示す特定の窓及びブロックの寸法、又は、画像を左から右に走査し次に下から上へ走査するといったことに限定されない。これは、再使用のため利用できるようにされたデータに明らかに影響を与える。例えば、メモリからのピクセルデータを画像中の右から左にロードする走査が用いられ得（右上コーナーにおける垂直ブロックからのピクセルのためのアドレスが再使用のため利用できるようにされる）、又は、右から左へと互いから移動され下から上への走査が用いられ得る（左上コーナーにおける水平ブロックからのピクセルのためのアドレスが再使用のため利用できるようにされる）。
【００３２】
本発明は、キャッシュメモリ１０から読取るために説明されたが、本発明は、プロセッサ１６がキャッシュメモリに書き込む場合にも使用され得る。プロセッサ１６がキャッシュメモリ１０中に書込むとき、キャッシュ制御ユニット１４は“コピーバック”方法を取り得、つまり、キャッシュ制御ユニット１４は、アドレスを再使用のために利用できるようにするとき、特に、そのアドレスがプロセッサ１６によってオーバーライトされた場合、キャッシュメモリユニット１２中のアドレスからのデータをメインメモリ１８に書き換えし得る。窓２０が移動するとき、キャッシュ制御ユニット１４は、例えば、このアドレスを窓２０の右下コーナーのピクセルのために再使用する前に、窓２０の左上コーナー中の行２８の数のピクセルデータを書き換える。
【図面の簡単な説明】
【図１】  キャッシュメモリを含む装置を示す図である。
【図２】  窓の例を示す図である。
【図１】
0004440477.tif 000002
【図２】
0004440477.tif 000003