(57)【要約】  本発明は、2次元データ構造アレイを蛇行的に順次供給するデータ・バッファリング装置（６００）（データ処理装置（７００）における利用に特に適している）に関する。データ・バッファリング装置（６００）は、いくつかのメモリ場所と、ポインタ値組からの書き込みポインタ値を現在の入力データ構造の指数対に周期的に割り当てるよう適合させたバッファ制御装置とを有するサーキュラー・バッファを備え、一書き込みポインタ割り当て期間は、第１の指数が第１の指数値組を第１の蛇行方向において段階的に横断し、書き込みポインタが、ポインタ値組内で規定された第１の回転方向におけるポインタ値を段階的に横断する第１の書き込みポインタ割り当て段階と、第１の指数が第１の指数値組を第２の蛇行方向において段階的に横断し、書き込みポインタが第１の回転方向においてポインタ値を段階的に横断する第２の書き込みポインタ割り当て段階と、第１の指数が第１の蛇行方向において第１の指数値組を段階的に横断し、書き込みポインタが、第１の回転方向と逆の第２の回転方向においてポインタ値を段階的に横断する第３の書き込みポインタ割り当て段階と、第１の指数値が第２の蛇行方向において第１の指数組を段階的に横断し、書き込みポインタ値が第２の回転方向においてポインタ値を段階的に横断する第４の書き込みポインタ割り当て段階とを有する。本発明は、非蛇行走査順序を有する動き補償器によって用いられる2次元ベクトル・アレイを動き推定器が蛇行的に供給するビデオ処理の分野において特に有用である。
2008537620.tif 000002
【特許請求の範囲】
【請求項１】
データ・バッファリング装置であって、
第１の蛇行方向及び第２の蛇行方向によって規定される蛇行するやり方で第１の指数値を段階的に横断する第１の指数を有する指数対によって編成された2次元データ構造アレイを順次受け取るよう適合させた入力装置と、
順序付けられたポインタ値組によってアドレス指定可能な所定数のメモリ場所を有するサーキュラー・バッファ・メモリと、
前記サーキュラー・バッファ・メモリ及び前記入力装置に接続され、前記ポインタ値組からの書き込みポインタ値を現在の入力データ構造の指数対に周期的に割り当て、前記現在の入力データ構造を、対応するメモリ場所に書き込むよう適合させたバッファ制御装置とを備え、一書き込みポインタ割り当て期間は、
前記第１の指数が前記第１の指数値組を前記第１の蛇行方向において段階的に横断し、書き込みポインタが、前記ポインタ値組内で規定されたポインタ値を第１の回転方向において段階的に横断する第１の書き込みポインタ割り当て段階と、
第１の指数値が前記第１の指数値組を前記第２の蛇行方向において段階的に横断し、前記書き込みポインタが前記第１の回転方向においてポインタ値を段階的に横断する第２の書き込みポインタ割り当て段階と、
前記第１の指数が前記第１の蛇行方向において前記第１の指数値組を段階的に横断し、前記書き込みポインタが、前記第１の回転方向と逆の第２の回転方向においてポインタ値を段階的に横断する第３の書き込みポインタ割り当て段階と、
前記第１の指数値が前記第２の蛇行方向において前記第１の指数組を段階的に横断し、前記書き込みポインタ値が前記第２の回転方向においてポインタ値を段階的に横断する第４の書き込みポインタ割り当て段階とを有するデータ・バッファリング装置。 
【請求項２】
請求項１記載のデータ・バッファリング装置であって、前記第１の指数が固定読み出し方向において前記第１の指数値組を繰り返し横断するような非蛇行読み出しパターンによって2次元アレイのデータ構造の、前記サーキュラー・バッファ・メモリに対する読み出し要求を受け取るよう前記バッファ制御装置を適合させたデータ・バッファリング装置。
【請求項３】
請求項２記載のデータ・バッファリング装置であって、読み出し要求の対象のデータ構造の各指数対に読み出しポインタ値を割り当てるよう前記バッファ制御装置を適合させ、前記読み出しポインタ値は、対応するデータ構造を前記サーキュラー・バッファ・メモリに記憶する時点で、個別の指数対に割り当てられる前記書き込みポインタ値に等しいデータ・バッファリング装置。
【請求項４】
請求項3記載のデータ・バッファリング装置であって、前記サーキュラー・バッファ・メモリのアドレス指定可能なメモリ場所の数は第１の指数値の数を１だけ上回り、
前記ポインタ値組からの読み出しポインタ値を現在の入力読み出し要求の指数対に周期的に割り当てるよう前記バッファ制御装置を適合させ、一読み出しポインタ割り当て期間は、
前記第２の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、前記第１の回転方向においてポインタ値を段階的に横断し、前記書き込みポインタに対して、前記第１の回転方向において１ステップのポインタ値オフセットを有し、最後の割り当てステップにおいて前記第１の回転方向から前記第２の回転方向に変わる第１の読み出しポインタ割り当て段階と、
前記第３の書き込みポインタ割り当て段階と同時であり、前記読み出しポインタが、前記第２の回転方向におけるポインタ値を段階的に横断し、前記書き込みポインタに対して、前記第２の回転方向における１ステップのポインタ値オフセットを有する第２の読み出しポインタ割り当て段階と、
前記第４の書き込みポインタ割り当て段階と同時であり、前記読み出しポインタが、前記第２の回転方向においてポインタ値を段階的に横断し、前記書き込みポインタに対して、前記第２の回転方向において１ステップのポインタ値オフセットを有し、最後の割り当てステップにおいて前記第２の回転方向から前記第１の回転方向に変える第３の読み出しポインタ割り当て段階と、次の書き込みポインタ割り当て期間の前記第１の書き込みポインタ割り当て段階と同時であり、前記読み出しポインタが、前記第１の回転方向においてポインタ値を段階的に横断し、前記書き込みポインタに対して、前記第１の回転方向において１ステップのポインタ値オフセットを有する第４の読み出しポインタ割り当て段階とを有するデータ・バッファリング装置。 
【請求項５】
データ処理装置であって、
２つの指数によって編成されるデータ構造の2次元アレイを供給するよう適合させた第１の処理装置であって、各指数は、個別の順序付けられた指数値組からの指数値を呈し、供給されるデータ構造それぞれについて、第１の指数は、第１の蛇行方向及び第２の蛇行方向によって規定される蛇行的なやり方で第１の指数値組からの第１の指数値を段階的に横断する第１の処理装置と、
前記第１の処理装置に接続された、請求項１記載のデータ・バッファリング装置とを備えたデータ処理装置。
【請求項６】
請求項５記載のデータ処理装置であって、前記データ・バッファリング装置に接続され、前記第１の指数が、固定された読み出し方向において前記第１の指数値組を繰り返し横断するような非蛇行読み出しパターンによって前記2次元アレイのデータ構造の読み出し要求を前記サーキュラー・バッファ・メモリに順次供給するよう適合させた第２の処理装置を有するデータ処理装置。
【請求項７】
請求項５記載のデータ処理装置であって、ビデオ画像のサブアレイを形成する、対応する2次元画素データ・ブロック・アレイに割り当てられた2次元動きベクトル・アレイを前記サーキュラー・バッファ・メモリに順次供給する動き推定アルゴリズムを行うよう前記第１の処理装置を適合させたデータ処理装置。
【請求項８】
請求項７記載のデータ処理装置であって、前記アレイの第１の行を前記第１の蛇行方向において横断し、前記アレイの後続行を前記第２の蛇行方向において横断し、次の後続行を前記第１の蛇行方向において横断する水平蛇行順序で前記2次元動きベクトル・アレイを供給するよう前記第１の処理装置を適合させたデータ処理装置。
【請求項９】
請求項７記載のデータ処理装置であって、動き補償アルゴリズムを行い、前記2次元動きベクトル・アレイを前記サーキュラー・バッファ・メモリから順次読み出すよう第２の処理装置を適合させたデータ処理装置。
【請求項１０】
請求項９記載のデータ処理装置であって、前記第１の処理装置に接続され、個別の画素ブロックに割り当てられ、前記2次元画素データ・ブロック・アレイのサブアレイを形成する現在のスライディング・サーチ領域を保持するよう適合させた低レベル・キャッシュ・メモリを備えるデータ処理装置。
【請求項１１】
請求項１０記載のデータ処理装置であって、前記低レベル・キャッシュ・メモリに接続され、外部メモリに接続可能であり、いくつかの連続したスライディング・サーチ領域に及ぶ前記2次元画素データ・ブロック・アレイの領域を保持するよう適合させた高レベル・キャッシュ・メモリを備えるデータ処理装置。
【請求項１２】
請求項９記載のデータ処理装置であって、前記2次元動きベクトル・アレイを行単位で読み出し、各行を左から右に読み出すよう前記第２の処理装置を適合させたデータ処理装置。
【請求項１３】
データ・バッファリング方法であって、
２つの指数によって編成されるデータ構造の2次元アレイを受け取る工程を備え、各指数は、個別の順序付けられた指数値組からの指数値を呈し、供給されるデータ構造それぞれについて、第１の指数は、第１の蛇行方向及び第２の蛇行方向によって規定される蛇行的なやり方で第１の指数値組からの第１の指数値を段階的に横断し、
順序付けられたポインタ値組によってアドレス指定可能な所定数のメモリ場所を有するサーキュラー・バッファ・メモリに、受け取られた前記データ構造を順次記憶する工程と、
受け取られた個別のデータ構造の指数対に、前記ポインタ値組からの書き込みポインタ値を周期的に割り当てる工程とを備え、一書き込みポインタ割り当て期間は、
前記第１の指数が前記第１の蛇行方向において前記第１の指数値組を段階的に横断し、書き込みポインタが、前記ポインタ値組内に規定されたポインタ値を第１の回転方向において横断する第１の書き込みポインタ割り当て段階と、
前記第１の指数値が前記第２の蛇行方向において変わり、前記書き込みポインタが前記第１の回転方向においてポインタ値を段階的に横断する第２の書き込みポインタ割り当て段階と、
前記第１の指数が前記第１の蛇行方向において前記第１の指数値組を段階的に横断し、前記書き込みポインタが、前記第１の回転方向と逆の第２の回転方向においてポインタ値を段階的に横断する第３の書き込みポインタ割り当て段階と、
前記第１の指数値が前記第２の蛇行方向において変わり、前記書き込みポインタが前記第２の回転方向においてポインタ値を段階的に横断する第４の書き込みポインタ割り当て段階とを有するデータ・バッファリング方法。
【請求項１４】
データ処理方法であって、第１の処理は、２つの指数によって編成される2次元データ構造アレイを供給し、各指数は、個別の順序付けられた指数値組からの指数値を呈し、供給されたデータ構造それぞれについて、第１の指数は、第１の蛇行方向及び第２の蛇行方向によって規定された蛇行的なやり方で第１の指数値組からの第１の指数値を段階的に横断し、請求項１１記載のデータ・バッファリング方法が行われるデータ処理方法。
【請求項１５】
請求項14記載のデータ処理方法であって、第２の処理は、前記第１の指数が固定読み出し方向において前記第１の指数値組を繰り返し横断するような非蛇行読み出しパターンによって前記2次元データ構造アレイの読み出し要求を前記サーキュラー・バッファ・メモリに順次供給するデータ処理方法。
【請求項１６】
請求項15記載のデータ処理方法であって、前記サーキュラー・バッファ・メモリのアドレス指定可能なメモリ場所の数は、前記第１の指数値の数を１だけ上回り、前記ポインタ値組からの読み出しポインタ値を、前記サーキュラー・バッファ・メモリに対する現在の入力読み出し要求の指数対に周期的に割り当てる工程を備え、一読み出しポインタ割り当て期間は、
前記第２の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、前記第１の回転方向においてポインタ値を段階的に横断し、前記書き込みポインタに対して、前記第１の回転方向において１ステップのポインタ値オフセットを有し、最後の割り当てステップにおいて前記第１の回転方向から前記第２の回転方向に変わる第１の読み出しポインタ割り当て段階と、
前記第３の書き込みポインタ割り当て段階と同時であり、前記読み出しポインタが、前記第２の回転方向におけるポインタ値を段階的に横断し、前記書き込みポインタに対して、前記第２の回転方向における１ステップのポインタ値オフセットを有する第２の読み出しポインタ割り当て段階と、
前記第４の書き込みポインタ割り当て段階と同時であり、前記読み出しポインタが、前記第２の回転方向においてポインタ値を段階的に横断し、前記書き込みポインタに対して、前記第２の回転方向において１ステップのポインタ値オフセットを有し、前記最後の割り当てステップにおいて前記第２の回転方向から前記第１の回転方向に変わる第３の読み出しポインタ割り当て段階と、
次の書き込みポインタ割り当て期間の前記第１の書き込みポインタ割り当て段階と同時であり、前記読み出しポインタが、前記第１の回転方向においてポインタ値を段階的に横断し、前記書き込みポインタに対して、前記第１の回転方向において１ステップのポインタ値オフセットを有する第４の読み出しポインタ割り当て段階とを有するデータ処理方法。 
【請求項１７】
請求項15記載のデータ処理方法であって、
前記サーキュラー・バッファ・メモリに現在記憶されているデータ構造に対応する各指数対に、前記書き込みポインタ値として前記指数対に割り当てられた個別のポインタ値を割り当てるポインタ割り当てテーブルを保持する工程と、
前記ポインタ割り当てテーブルにおける現在の読み出し要求に含まれた個別の指数対に割り当てられた前記個別のポインタ値を調べる工程と、
前記個別のポインタ値を有する前記メモリ場所に前記読み出し要求を送り出す工程と、
個別のメモリ場所に記憶された前記データ構造を第２の処理部に供給する工程とを備えるデータ処理方法。
【請求項１８】
請求項１５記載のデータ処理方法であって、前記第１の処理は、ビデオ画像のサブアレイを形成する対応する2次元画素データ・ブロック・アレイに割り当てられた2次元動きベクトル・アレイを前記サーキュラー・バッファ・メモリに順次供給する動き推定アルゴリズムであるデータ処理方法。
【請求項１９】
請求項15記載のデータ処理方法であって、前記第１の処理は、前記2次元動きベクトル・アレイを、前記アレイの第１の行を第１の蛇行方向において横断し、前記アレイの後続行を前記第２の蛇行方向において横断し、次の後続行を前記第１の蛇行方向において横断する水平蛇行順序で供給するデータ処理方法。 
【請求項２０】
請求項15記載のデータ処理方法であって、前記第２の処理は、動き補償アルゴリズムを行い、前記2次元動きベクトル・アレイを前記サーキュラー・バッファ・メモリから順次読み出すデータ処理方法。
【請求項２１】
請求項15記載のデータ処理方法であって、前記第２の処理は、前記2次元動きベクトル・アレイを行単位で読み出し、各行を左から右に読み出すデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、第１の蛇行方向及び第２の蛇行方向によって規定された蛇行したやり方で第１指数値を段階的に横断する第１の指数を有する指数対によって編成された2次元のデータ構造アレイを順次受け取るよう適合させた入力装置を備えるデータ・バッファリング装置に関する。本発明は、データ・バッファリング方法、並びに、データ処理の方法及び装置に更に関する。
【背景技術】
【０００２】
2次元のデータ構造アレイの処理は、いたるところで見られるタスクである。これは、画像処理及びビデオ処理において特に重要である。高品位テレビジョン（HDTV）のような新たなディジタル・テレビジョン信号標準の登場や、ビデオ会議用のCIFなどのローエンドのビデオ・フォーマットの普及によって、異なるビデオ標準間の変換は、放送連鎖におけるプロフェッショナル・スタジオのタスクになっただけでなく、消費者向電子装置のタスクにもなった。例えば、画像レート変換は現在、最大100Hzのフィールド・レートを有する拡張テレビジョン・ディスプレイ、コンピュータ・ワークステーション及びDVDプレイヤによって行われている。
【０００３】
画像レート変換手法の一派生例は、動き補償手法を用いる。既知の動き補償手法は、連続した２つのビデオ画像間の画像データの補間が、ビデオ系列におけるオブジェクトの動きの知識によって可能になるという原理に基づいている。補間された画像データは、表示するために中間画像を生成し、よって、画像レートを増加させるために用いられる。ビデオ系列におけるオブジェクトの動きは、動き推定手法によって確かめられる。通常の動き推定アルゴリズム（米国特許出願公開第2003/0103567号明細書記載など）は、選択された画像ブロック（例えば、8×8画素を含む）について、後続画像における画素ブロックを取り囲むサーチ領域が規定されるブロック・ベースの手法を施す。選択された画素ブロックはその中心に配置される。動き推定アルゴリズムの出力は２次元の動きベクトル・アレイである。各動きベクトルは、個別の画素ブロックに割り当てられる。動きベクトルは、画像平面上の動き軌跡の投影である。動き軌跡は、ビデオ画像系列における同一の画像部分をつなぐ線である。
【０００４】
ビデオ画像の画素ブロックに割り当てられた動きベクトル組が、よって、2次元のデータ構造アレイを形成する。動き補償処理は、個別の画素ブロックに割り当てられた動きベクトルを入力として用いる。ディスプレイ装置は全て、左から右に、かつ上から下に画像を走査するので、動き補償手法は、この所定の標準走査順序に従う。
【０００５】
米国特許出願公開第2003/0161403号明細書には、動き推定器が動きベクトルを動き補償器に供給する、走査フォーマットを変換する装置が開示されている。動き推定器は、動き補償器によって読み取られる動きベクトルを記憶するバッファ・メモリを備える。
【０００６】
動き推定処理において蛇行走査順序を用いることによって、補間されたビデオ画像の画像品質が向上することが最近明らかになった。蛇行走査順序を用いるにあたって、動き推定処理は、連続した画素ブロック行を逆方向に（例えば、第１の画素ブロック行を左から右に、近接する第２の画素ブロック行を右から左に、後続の第３の画素ブロック行を左から右に、等）走査する。同様に、蛇行走査順序は、列ベースでもあり得る。例えば、ビデオ画像の第１の画素ブロック列が上から下に走査される一方、近接の第２の画素ブロック列は下から上に走査され、連続した第３の画素ブロック列がやはり上から下に走査される、等である。一般的には、蛇行走査順序は、画素ブロックの構成を表す指数対のうちの一方の指数が、順序付けられた指数値組を第１の方向及び逆の第２の方向に交互に段階的に横断し、所定の境界指数値が変向点を示すことを示唆している。各変向点では、第２の指数は、所定の方向で１ステップだけ変わる。
【０００７】
動き推定及び動き補償のアルゴリズムにおいて、異なる走査順序を用いることによって、動き推定器の出力のバッファリングがより難しくなる。種々の動きベクトルは、別々の期間中、動き補償器によって読み取られる対象の順序にある状態になるまでバッファに留まっていなければならない。この問題は、動きベクトルの完全な蛇行期間を格納するのに容量が十分大きなバッファ・メモリを備えることによって明らかに解決することが可能である。しかし、異なる走査順序を補償する、より大容量のバッファ・メモリを供給することは、チップ面積及びエネルギ消費の点でコストがかかる。更に、動きベクトル数の増加によって、動き推定器及び動き補償器の２つの処理間のレーテンシが増加する。動き補償器は、動き推定器の後ろの、完全な蛇行期間（例えば、２画素ブロック行）である。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、第１の処理によって蛇行順序で供給される2次元アレイを形成するデータ構造の記憶容量を削減し、非蛇行走査順序を有する第２の処理によって読み出すことを可能にするデータ・バッファリング方法及び装置を提供することである。
【０００９】
本発明の更なる目的は、2次元のデータ構造アレイを蛇行的に順次供給する第１の処理装置を有する第１の処理装置と、非蛇行走査順序を有する第２の処理装置による読み出しアクセスのためにバッファ・メモリの記憶容量を削減することを可能にするデータ・バッファリング装置とを有するデータ処理装置を提供することである。
【課題を解決するための手段】
【００１０】
本発明の第１の局面によれば、
第１の蛇行方向及び第２の蛇行方向によって規定される蛇行するやり方で第１指数値を段階的に横断する第１の指数を有する指数対によって編成された2次元データ構造アレイを順次受け取るよう適合させた入力装置と、
順序付けられたポインタ値組によってアドレス指定可能な所定数のメモリ場所を有するサーキュラー・バッファ・メモリと、
サーキュラー・バッファ・メモリ及び入力装置に接続され、ポインタ値組からの書き込みポインタ値を現在の入力データ構造の指数対に周期的に割り当て、現在の入力データ構造を、対応するメモリ場所に書き込むよう適合させたバッファ制御装置とを備え、一書き込みポインタ割り当て期間は、
第１の指数が第１の指数値組を第１の蛇行方向において段階的に横断し、書き込みポインタが、ポインタ値組内で規定された第１の回転方向においてポインタ値を段階的に横断する第１の書き込みポインタ割り当て段階と、
第１の指数値が第２の蛇行方向において変わり、書き込みポインタが第１の回転方向においてポインタ値を段階的に横断する第２の書き込みポインタ割り当て段階と、
第１の指数が第１の蛇行方向において第１の指数値組を段階的に横断し、書き込みポインタが、第１の回転方向と逆の第２の回転方向においてポインタ値を段階的に横断する第３の書き込みポインタ割り当て段階と、
第１の指数値が第２の蛇行方向において変わり、書き込みポインタ値が第２の回転方向においてポインタ値を段階的に横断する第４の書き込みポインタ割り当て段階とを有するデータ・バッファリング装置が提供される。
【００１１】
本発明のデータ・バッファリング装置は、所定数のメモリ場所を有するサーキュラー・バッファ・メモリを利用する。サーキュラー・バッファは、順次供給されたデータを一時的に記憶する目的で周知のメモリ構造である。有限数のメモリ場所しか有しないが、サーキュラー・バッファは、それ自体にループバックするので、無限の容量を有するように思われる。データが、サーキュラー・バッファ内の連続したメモリ場所に記憶されるにつれ、最終的には、バッファの終端に達する。この状態では、バッファは、その他方の終端で始めて、データを受取り、記憶し続ける。
【００１２】
サーキュラー・バッファの基本動作を例によって示す。入力データ構造を順次記憶するサーキュラー・バッファのバッファ制御装置は、そのそれぞれのメモリ場所に対する書き込みポインタ値を新たなデータ構造毎に増やす。書き込みポインタは最終的には、ポインタ値組の上限に達する。その時点で、この例のサーキュラー・バッファは、書き込みポインタを用いて、最低ポインタ値から始め、次いで、ポインタ値を更に増やして、更なる入力データ構造を記憶し続けることができる。先行して前述のメモリ場所に記憶されたデータは上書きされる。よって、バッファ制御装置によって行われるメモリ場所のアドレス指定は、円によって視覚化することが可能な無限の周期パターンをたどる。ポインタ値の増加又は減少は、逆の回転方向におけるポインタ値の変更として表す。
【００１３】
本発明のサーキュラー・バッファ・メモリ内のメモリ場所の容量は、サーキュラー・バッファ・メモリに記憶する対象のデータ構造の容量に応じて選ぶことが可能である。メモリ場所は少なくとも、受け取られる完全な一データ構造を記憶するための容量を有していることを必要とする。したがって、メモリ場所は通常、複数のメモリ・セルを有する。特定のポインタ値に基づいてサーキュラー・バッファ・メモリの個々のメモリ・セルをアドレス指定するやり方は当該技術分野において周知である。
【００１４】
本発明のデータ・バッファリング装置のバッファ制御装置は、周期的な書き込みポインタ割り当てを行う。ポインタ割り当ての周期性は、バッファリング装置の入力において受け取られた2次元アレイの個々のデータ構造に割り当てられた指数値の変動に結びつけられる。一書き込みポインタ割り当て期間は、４つの書き込みポインタ割り当て段階を有する。４つの段階それぞれでは、入力データ構造に割り当てられた指数対の一方の指数は、その指数の特定の指数値組を段階的に横断する。各入力データとともに変わる指数は、2次元アレイのデータ構造が行単位で受け取られるか、又は列単位で受け取られるかによって変わってくる。通常、指数は、各書き込みポインタ割り当て段階における所定の範囲の指数値をカバーする。しかし、各段階で、方向が変更され、それによって、2次元アレイに対する、入力装置における蛇行した受取りパターンが生じる。
【００１５】
第１の書き込みポインタ割り当て段階は、指数が第１の蛇行方向において変わり、書き込みポインタが、ポインタ値組内に規定された第１の回転方向においてポインタ値を段階的に横断することを特徴とする。第２の書き込みポインタ割り当て段階では、第１の指数値は蛇行方向を変えるが、書き込みポインタ割り当ての回転方向は一定に維持される。第３の書き込みポインタ割り当て段階では、蛇行方向はやはり変わり、書き込みポインタ割り当ての回転方向も変わる。最後に、第４の書き込みポインタ割り当て段階では、ポインタ割り当ての回転方向が一定状態に留まる一方、蛇行方向は再度変わっている。
【００１６】
例証の目的で、入力データ構造は、ビデオ画像を形成する画素ブロックから動き推定器を利用して算出された動きベクトル組を構成することができる。対応する動きベクトル行列が、本発明のデータ・バッファリング装置に行単位で供給されるとすると、完全な書き込み割り当て期間は動きベクトルの4行をカバーする。入力装置において受け取られたデータ構造の蛇行方向が行毎に変わる一方、バッファ制御装置によって行われる書き込みポインタの割り当ての回転方向は1行おきに変わる。
【００１７】
本発明のデータ・バッファリング装置により、最小メモリ空間によって、記憶されたデータへのアクセスを付与することが可能になる。サーキュラー・バッファを用いることによって、非蛇行処理がデータ構造への読み出しアクセスを有することが可能な状態になる前に、データ構造の完全な蛇行期間をバッファに記憶する必要性がなくなる。これは、書き込みポインタ値の割り当てに用いる回転方向を変えることが可能なバッファ制御装置を提供することによって達成される。前述の蛇行方向及び回転方向の連係された変更を利用することによって、メモリ場所は、読み出される前に上書きされないことになる。本発明のデータ・バッファリング装置における蛇行方向と書き込みポインタ割り当てとの間の結合によって、バッファへの書き込みとバッファからの読み出しとの間のレ―テンシも削減される。このようにして、本発明のデータ・バッファリング装置は、データ処理装置における処理速度の増加に寄与する。
【００１８】
本発明のデータ・バッファリング装置の更なる利点は、ME処理及びMC処理によって共用される、ビデオ・データを保持するオンチップ・キャッシュ・メモリの容量も削減することが可能である。これは、図７に示す好ましい実施例を参照して更に詳細に説明する。
【発明を実施するための最良の形態】
【００１９】
以下では、本発明のバッファリング装置の好ましい実施例を説明する。
【００２０】
好ましい実施例では、第１の指数が固定読み出し方向において第１の指数値組を繰り返し横断するような非蛇行読み出しパタ―ンによる、2次元アレイのデータ構造の、サーキュラー・バッファ・メモリに対する読み出し要求を受け取るようバッファ制御装置を適合させる。非蛇行読み出しパターンは、各行又は列それぞれの第１の指数値の変更の同じ方向を用いる。
【００２１】
好ましくは、読み出し要求が送り出されるデータ構造の各指数対に読み出しポインタ値を割り当てるようバッファ制御装置を適合させる。書き込みポインタ値に対応する読み出しポインタ値は、対応するデータ構造をサーキュラー・バッファ・メモリに記憶する時点で、個別の指数対に割り当てられる。
【００２２】
更なる好ましい実施例では、サーキュラー・バッファ・メモリのアドレス指定可能なメモリ場所の数は、第１の指数値の数を１だけ上回り、ポインタ値組からの読み出しポインタ値を、現在の入力読み出し要求の指数対に周期的に割り当てるようバッファ制御装置を適合させる。一読み出しポインタ割り当て期間は、
第２の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、第１の回転方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、第１の回転方向において１ステップのポインタ値オフセットを有し、最後の割り当てステップにおいて第１の回転方向から第２の回転方向に変わる第１の読み出しポインタ割り当て段階と、
第３の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、第２の回転方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、第２の回転方向において１ステップのポインタ値オフセットを有する第２の読み出しポインタ割り当て段階と、
第４の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、第２の回転方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、第２の回転方向において１ステップのポインタ値オフセットを有し、最後の割り当てステップにおいて第２の回転方向から第１の回転方向に変わる第３の読み出しポインタ割り当て段階と、
次の書き込みポインタ割り当て期間の第１の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、第１の回転方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、第１の回転方向において１ステップのポインタ値オフセットを有する第４の読み出しポインタ割り当て段階とを有する。
【００２３】
この実施例では、バッファ制御装置が、サーキュラー・バッファ・メモリへの書き込みアクセス及び読み取りアクセスを付与する。これによって、バッファへの書き込みとバッファからの読み出しとの間のレーテンシが事実上最小にされる。更に、書き込みポインタ割り当て段階及び読み出しポインタ割り当て段階を協調させることによってサーキュラー・バッファ・メモリの容量を小さい状態に留めることが可能である。その結果、読み出しアクセスは、書き込みよりも一ポインタ割り当て段階だけ後になる。この実施例は、特定のデータ構造の書き込みと読み出しとの間のレーテンシがわずかで同時に行うことが可能であるように読み出しポインタ割り当て段階及び書き込みポインタ割り当て段階を協調させる。以下に示す図を参照して詳細に説明するように、入力データ構造が供給される蛇行走査順序が理由で、読み出しと書き込みとの間のレーテンシがある程度変動する。同じメモリ場所に読み出し要求及び書き込み要求が送り出されるアクセス競合は、読み出しポインタ割り当て段階及び書き込みポインタ割り当て段階の特定の協調によって避けられる。
【００２４】
更なる実施例では、バッファ制御装置は、
サーキュラー・バッファ・メモリに現在記憶されているデータ構造に対応する各指数対に、書き込みポインタ値として指数対に割り当てられた個別のポインタ値を割り当てるポインタ割り当てテーブルを保持し、
ポインタ割り当てテーブルにおける現在の読み出し要求に含まれた個別の指数対に割り当てられた個別のポインタ値を調べ、
個別のポインタ値を有するメモリ場所に読み出し要求を送り出し、
個別のメモリ場所に記憶されたデータ構造を第２の処理部に供給するよう適合させる。
【００２５】
この実施例は、読み出し要求においてその指数値によって識別することが可能な、2次元アレイの特定のデータ構造のメモリ場所のポインタを調べるために用いられるポインタ割り当てテーブルを利用する。この実施例は、サーキュラー・バッファの容量を小さく留めることが可能であり、バッファ・アドレスの再計算に必要な時間に対してメモリ場所のポインタの高速ルックアップが可能になる場合に有用である。
【００２６】
本発明の第２の局面によれば、データ処理装置が提供される。データ処理装置は、２つの指数によって編成されるデータ構造の2次元アレイを備えるよう適合させた第１の処理装置を備える。各指数は、個別の順序付けられた指数値組からの指数値を呈する。供給されるデータ構造それぞれについて、第１の指数は、第１の蛇行方向及び第２の蛇行方向によって規定される蛇行的なやり方で第１の指数値組からの第１の指数値を段階的に横断する。本発明のデータ処理装置は、本発明の第１の局面によるか、又は本明細書記載のデ―タ・バッファリング装置の実施例の１つによるデータ・バッファリング装置を備える。 
本発明の第２の局面のデ―タ処理装置は、蛇行的に2次元アレイを形成するデータ構造を備える第１の処理装置を有する。データ処理装置における本発明の第１の局面のデ―タ・バッファリング装置を用いることによって、ハードウェア実現形態におけるチップ面積を最小にすることが可能になる。このことは、サーキュラー・バッファを用いることによって、小さい状態にバッファ空間を留めることが可能になるという前述の説明に従っている。
【００２７】
以下に、本発明のデータ処理装置の好ましい実施例を記載する。
【００２８】
本発明のデータ処理装置によって、バッファリングされたデータ構造を非蛇行的に読み出す第２の処理装置との通信において特に小さなレーテンシを達成することが可能になる。第１の好ましい実施例によれば、データ処理装置は、よって、データ・バッファリング装置に接続され、第１の指数が、固定された読み出し方向において第１の指数値組を繰り返し横断するような非蛇行読み出しパターンによって2次元アレイのデータ構造の読み出し要求をサーキュラー・バッファ・メモリに順次供給するよう適合させた第２の処理装置を有する。第２の処理装置は、第１の処理装置と、単一のハードウェア装置に一体化させることが可能である。当然、本発明は、物理的に互いに分離された処理装置でもうまく機能する。
【００２９】
一般に、本明細書及び特許請求の範囲記載の「処理装置」の語は、純粋に機能的な意味合いで理解するものとする。処理装置は、回路部、特定用途向集積回路（ASIC）（マイクロチップの形態など）、マイクロチップの適切な組み合わせ（コンピュータ内など）や、コンピュータ・アレイの形態を呈し得る。本発明による処理装置は、第１の処理装置を備える。前述の限定を念頭におけば、処理装置は、処理装置の実現形態において前述の形態の何れか１つを呈することができるのはもっともである。
【００３０】
本願の最も好ましい実施例において、本発明のデータ処理装置では、ビデオ画像のサブアレイを形成する対応する2次元画素データ・ブロック・アレイに割り当てられた2次元動きベクトル・アレイをサーキュラー・バッファ・メモリに順次供給する動き推定アルゴリズムを行うよう第１の処理装置を適合させる。この実施例により、レーテンシ及び計算処理量を低い状態に留めながら、蛇行走査順序でベクトルを出力する最近の動き推定アルゴリズムを第１の処理装置において実現することが可能になる。
【００３１】
一実施例では、動き推定器を実現する第１の処理装置は、第１のアレイ行を第１の蛇行方向において横断し、後続アレイ行を第２の蛇行方向において横断し、次の後続行を第１の蛇行方向において横断する等の水平蛇行順序で2次元動きベクトル・アレイを供給するよう適合させる。
【００３２】
最も好ましくは、第２の処理装置は、動き補償アルゴリズムを行い、サーキュラー・バッファ・メモリから2次元動きベクトル・アレイを順次読み出すよう適合させる。この実施例のデータ処理装置は、効率的な高品質ピクチャレート・アップコンバータに含めることが可能である。前述のアップコンバータでは、動き推定器を実現する第１の処理装置及び動き補償器を実現する第２の処理装置を単一のASICに含めることが可能である。
【００３３】
本発明のデータ処理装置の更に好ましい実施例は、第１の処理装置に接続された低レベル・キャッシュ・メモリと、個別の画素ブロックに割り当てられ、ビデオ・フレームを形成する完全な2次元画素データ・ブロック・アレイのサブアレイを形成する現在のスライディング・サーチ領域を保持するよう適合させた低レベル・キャッシュ・メモリを備える。ブロック・ベースの動き推定アルゴリズムでは、現在処理されている画素ブロックそれぞれ周辺の規定された拡張部のサーチ領域を、現在の画素ブロックの動きベクトルの確認に用いる。動き推定が、次の画素ブロックを処理し始めると、動き推定アルゴリズムの蛇行走査順序に適合させた置換手法によって特定の画素ブロックが上書きされるという点でサーチ領域が更新される。好ましくは、この実施例では、低レベル・キャッシュ・メモリに接続されたキャッシュ・コントローラは、現在処理されている個別の画素ブロックについて更新されたサーチ領域を維持することが必要な画素データ・ブロックを低レベルのキャッシュ・メモリにロードするよう適合させる。
【００３４】
この実施例によって、主メモリへのアクセス頻度の削減が可能になる。したがって、低レベル・キャッシュ・メモリを導入することによって、フレーム・メモリと処理装置との間のデータ通信の帯域幅要件が緩和される。フレーム・メモリが通常、動き推定器と同じチップ上にない一方、低レベル・キャッシュ・メモリは通常、動き推定器と同じチップ上にあるので、動き推定器によって必要な画素ブロックへのアクセスのレーテンシが削減される。
【００３５】
前述の効果は、低レベル・キャッシュ・メモリに接続され、少なくとも現在処理されているビデオ・フレームを含む外部メモリに接続可能な高レベル・キャッシュ・メモリを導入することによって更に拡充することが可能である。高レベル・キャッシュ・メモリは、低レベル・キャッシュ・メモリよりも容量が大きい。高レベル・キャッシュ・メモリは、いくつかの連続したスライディング・サーチ領域に及ぶ2次元画素データ・ブロック・アレイの領域を保持するよう適合させる。好ましくは、キャッシュ制御装置は、領域の更新を維持するために必要な画素データ・ブロックのフェッチ動作を制御するよう適合させる。 
好ましくは、キャッシュ・コントローラによって、高レベル・キャッシュ・メモリへのアクセスが、両方の処理装置（すなわち、動き推定器及び動き補償器）に可能になる。従来技術の装置では、蛇行動き推定器及び非蛇行動き補償器の異なる走査順序に対応するために、高レベル・キャッシュ・メモリの幾分大きな容量オーバヘッドが必要であった。対照的に、本発明の第１の局面のデ―タ・バッファリング装置を組み入れることによって、高レベル・キャッシュ・メモリの所要容量を削減することが可能である。
【００３６】
例えば、一画素ブロック行に一画素ブロックを加えたものから得られる動きベクトルのサーキュラー・バッファ容量は、動き推定（ME）及び動き補償（MC）の異なる走査タイプに対応するための最小値である。これは、MEとMCとの間で共有されたビデオ・データの高レベル・キャッシュ・メモリの容量も最小にされることを示唆している。高レベル・キャッシュ・メモリは少なくとも、サーチ領域の高さに対処するためにいくつかのビデオ・データ・ブロック行（通常、SD系列の場合、５ブロック行）を保持する必要がある。よって、ME及びMCの異なる走査方向に対応するために必要なオーバヘッド・メモリ容量は、一画素ブロック行と一画素ブロックとを足したものである。SDビデオ系列の特定例では、共有高レベル・キャッシュ・メモリには７ブロック行しか必要でない。
【００３７】
水平蛇行走査を行う動き推定器と組み合わせた更なる好ましい実施例では、第２の処理装置は、2次元動きベクトル・アレイを行単位で読み出し、各行を左から右に読み出すよう適合させる。
【００３８】
本発明の第３の局面によれば、
個別の順序付けられた指数値組からの指数値をそれぞれの指数が呈する２つの指数によって編成される2次元データ構造アレイを受け取る工程を備え、供給されるデータ構造それぞれについて、第１の蛇行方向及び第２の蛇行方向によって規定された蛇行的なやり方で第１の指数値組からの第１の指数値を第１の指数が段階的に横断するデータ・バッファリング方法が提供される。このデータ処理方法は、
順序付けられたポインタ値組によってアドレス指定可能な所定数のメモリ場所を有するサーキュラー・バッファ・メモリに、第１の処理によって供給されるデータ構造を順次記憶する工程と、
第１の処理によって供給される現行データ構造の指数対に、ポインタ対組からの書き込みポインタ値を周期的に割り当てる工程とを備える。一書き込みポインタ割り当て期間は、
第１の指数が第１の蛇行方向において第１の指数値組を段階的に横断し、書き込みポインタが、ポインタ値組内に規定されたそれぞれの現行ポインタ値を第１の回転方向において横断する第１の書き込みポインタ割り当て段階と、
第１の指数値が第２の蛇行方向において変わり、書き込みポインタが第１の回転方向においてそれぞれの現行ポインタ値を段階的に横断する第２の書き込みポインタ割り当て段階と、
第１の指数が第１の蛇行方向において第１の指数値組を段階的に横断し、書き込みポインタが、第１の回転方向と逆の第２の回転方向においてそれぞれの現行ポインタ値を段階的に横断する第３の書き込みポインタ割り当て段階と、
第１の指数値が第２の蛇行方向において変わり、書き込みポインタが第２の回転方向においてそれぞれの現行ポインタ値を段階的に横断する第４の書き込みポインタ割り当て段階とを有する。
【００３９】
本発明の第３の局面のデータ・バッファリング方法は、本発明の第１の局面のデータ・バッファリング装置によって行われる方法工程を備える。この説明を簡潔に留めるために、この方法及びその利点の詳細な説明についてデータ・バッファリング装置の上記説明を参照されたい。更に、本発明の第３の局面の方法の規定に用いる語は、本発明の第１の局面のデータ・バッファリング装置の説明の意味合いで記載されたと解されるものとする。
【００４０】
本発明の第４の局面によれば、第１の処理は、２つの指数によって編成される2次元データ構造アレイを供給し、各指数は、個別の順序付けられた指数値組からの指数値を呈し、供給されたデータ構造それぞれについて、第１の指数は、第１の蛇行方向及び第２の蛇行方向によって規定された蛇行的なやり方で第１の指数値組からの第１の指数値を段階的に横断するデータ処理方法が提供される。本発明の第４の局面のデータ処理方法では、本発明の第３の局面によるデータ・バッファリング方法が行われる。
【００４１】
本発明の第４の局面のデータ処理方法は、本発明の第２の局面によるデータ処理装置によって行われる方法工程を備える。やはり、前述の説明を参照されたい。
【００４２】
データ処理方法の好ましい実施例を以下に記載する。この実施例の利点は、本発明の第２の局面のデータ処理装置の対応する実施例の説明で記載されたものである。
【００４３】
本発明のデータ処理方法の更なる実施例では、第２の処理は、第１の指数が固定読み出し方向において第１の指数値組を繰り返し横断するような非蛇行読み出しパターンによって2次元アレイのデータ構造の読み出し要求をサーキュラー・バッファ・メモリに順次供給する。
【００４４】
本発明のデータ処理方法の更なる実施例では、サーキュラー・バッファ・メモリのアドレス指定可能なメモリ場所の数は、第１の指数値の数を１だけ上回り、
ポインタ値組からの読み出しポインタ値を、データ・バッファに対する現在の入力読み出し要求の指数対に周期的に割り当てる工程を備え、一読み出しポインタ割り当て期間は、
第２の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、第１の回転方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、第１の回転方向において１ステップのポインタ値オフセットを有し、最後の割り当てステップにおいて第１の回転方向から第２の回転方向に変わる第１の読み出しポインタ割り当て段階と、
第３の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、第２の回転方向におけるそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、第２の回転方向における１ステップのポインタ値オフセットを有する第２の読み出しポインタ割り当て段階と、
第４の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、第２の回転方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、第２の回転方向において１ステップのポインタ値オフセットを有し、最後の割り当てステップにおいて第２の回転方向から第１の回転方向に変わる第３の読み出しポインタ割り当て段階と、
次の書き込みポインタ割り当て期間の第１の書き込みポインタ割り当て段階と同時であり、読み出しポインタが、第１の回転方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、第１の回転方向において１ステップのポインタ値オフセットを有する第４の読み出しポインタ割り当て段階とを有する。
【００４５】
本発明のデータ処理方法の更なる実施例は、
サーキュラー・バッファ・メモリに現在記憶されているデータ構造に対応する各指数対に、書き込みポインタ値として指数対に割り当てられた個別のポインタ値を割り当てるポインタ割り当てテーブルを保持する工程と、
ポインタ割り当てテーブルにおける現在の読み出し要求に含まれた個別の指数対に割り当てられた個別のポインタ値を調べる工程と、
個別のポインタ値を有するメモリ場所に読み出し要求を送り出す工程と、
個別のメモリ場所に記憶されたデータ構造を第２の処理部に供給する工程とを備える。
【００４６】
本発明のデータ処理方法の更なる実施例では、第１の処理は、ビデオ画像のサブアレイを形成する対応する2次元画素データ・ブロック・アレイに割り当てられた2次元動きベクトル・アレイをサーキュラー・バッファ・メモリに順次供給する動き推定アルゴリズムである。
【００４７】
本発明のデータ処理方法の更なる実施例では、第１の処理装置は、アレイの第１の行を第１の蛇行方向において横断し、アレイの後続行を第２の蛇行方向において横断し、次の後続行を第１の蛇行方向において横断する水平蛇行順序で2次元動きベクトル・アレイを供給するよう適合させる。
【００４８】
本発明のデータ処理装置の更なる実施例では、第２の処理は、動き補償アルゴリズムを行い、サーキュラー・バッファ・メモリから2次元動きベクトル・アレイを順次読み出すよう適合させる。
【００４９】
本発明のデータ処理方法の更なる実施例では、第２の処理は、2次元動きベクトル・アレイを行単位で読み出し、各行を左から右に読み出す。
【００５０】
以下では、更なる実施例を図を参照して説明する。
【実施例】
【００５１】
図１はビデオ・フレーム１００を示す。当該技術分野において周知であるように、画像又はビデオのフレームは2次元画素データ・アレイによって表すことが可能である。画素データは通常、光強度（例えば、画素が画面上に表示される際にディスプレイ装置によって放出される）に対する３つの色の寄与度を規定する。画素データは、行列に似た2次元データ構造アレイについて周知であるように指数対の値によって編成される。この実施例の目的では、ビデオ・フレーム１００の画素は、ビデオ・フレームの2次元サブアレイを形成する画素ブロックにビデオ・フレームを区分するグリッドによって示されるように画素ブロックにグループ化される。画素ブロックの一例を参照番号102によって示す。以下の説明の目的で、ビデオ・フレーム100の画素ブロックは、ビデオ・フレーム100の左境界及び上境界に沿って示す指数対(i,j)によって識別される。ビデオ・フレーム１００は、７つの画素ブロック行及び７つの画素ブロック列を含んでいることが分かる。
【００５２】
蛇行パターンでビデオ・フレーム１００の画素ブロックを横断する矢印実線１０４は、第１のビデオ処理アルゴリズムの走査順序を表す。処理装置において実現される第１の処理アルゴリズムは、現在処理されている画素ブロックに割り当てられるデータ構造をその出力において供給する。第１のビデオ処理アルゴリズムは、処理される画素ブロック毎に動きベクトルを供給する動き推定アルゴリズムであり得る。矢印線１０４の蛇行パターンから分かり得るように、第１のビデオ処理アルゴリズムは、第１の画素ブロック行を画素ブロック(1,1)から画素ブロック(1,7)に（すなわち、左から右に）処理する。次いで、第２の画素ブロック行が画素ブロック(2,7)から画素ブロック(2,1)に（すなわち、右から左に）処理される。最初の２つの画素ブロック行においてたどる走査順序は周期的に繰り返され、画素ブロック行i=7の左から右への処理で終了する。次のビデオ・フレームは、同じパターンによって（やはり、画素ブロック(1,1)で始め、第１の画素ブロック行を左から右に処理して）処理される。
【００５３】
図１には、動き補償アルゴリズムなどの第２のデータ処理アルゴリズムがたどる走査順序を表す矢印破線１０６も示す。第２のデータ処理アルゴリズムは、出力を生成するために第１のデータ処理アルゴリズムの出力を読み取る。しかし、動き補償アルゴリズムがたどる走査順序は、動き推定アルゴリズムの走査順序とは異なる。画素ブロック行i=1.2.,,,.7は左から右に処理される。最右の画素ブロック(i,7)における現行画素ブロック行の処理の完了後、動き補償アルゴリズムは、後続画素ブロック行の最左画素ブロック（i+1,1）に続く。
【００５４】
動き推定アルゴリズム及び動き補償アルゴリズムの異なる走査順序によって、特定の画素ブロックの動きベクトルの供給と、動き補償の目的での動きベクトルの処理との間に可変の遅延が生じる。これは、動き推定アルゴリズムによって供給される動きベクトルを、特定時間の間、バッファリングすることを必要とする。
【００５５】
矢印線１０４及び１０６によって示す走査順序は例としての役目を担う。第１のデータ処理アルゴリズム及び第２のデータ処理アルゴリズムの走査順序の更なる組み合わせが可能である。第２の例を図２に示す。ビデオ・フレーム２００のグラフィック表現は、図１のビデオ・フレーム１００のグラフィック表現に対応する。矢印実線２０４は、第１のデータ処理アルゴリズムがたどる走査順序を示す。処理は画素ブロック(1,7)から始まり、最右列(i,7)を上から下にたどる。画素ブロック(7,7)を処理した後、処理は画素ブロック列(i,6)において、下の画素ブロック(7,6)に続き、その列を、上の画素ブロック(1,6)までたどる。この走査パターンは、ビデオ・フレーム２００の画素ブロック全てが処理されるまで周期的に繰り返される。第２の矢印行２０６は、第２のデータ処理アルゴリズムがたどる走査順序を示す。やはり、第２のデータ処理アルゴリズムは、第１のデータ処理アルゴリズムの出力の読み出しによって変わってくる。第２の処理アルゴリズムも、画素ブロック(1.7)から始まり、その画素ブロック列をブロック(7,7)までたどる。第２のデータ処理アルゴリズムは次いで、近傍列(i,6)を上から下まで処理することによって続く。よって、画素ブロック列は全て、完全なビデオ・フレームが処理された状態になるまで、上から下に処理される。
【００５６】
ビデオ・フレームを処理する２つのデータ処理アルゴリズムがたどる走査順序の他の組み合わせが可能であることが図１及び図２の説明から明らかになる。例えば、図１に示す例は、第１のデータ処理アルゴリズムが下の行において最右の画素ブロック(7.7)から始め、ビデオ・フレーム１００の画素ブロック全てにわたって蛇行パターンをたどるように修正することが可能である。第１のデータ処理アルゴリズムの出力を用いる第２のデータ処理アルゴリズムも、画素ブロック(7,7)から始め、第１のデータ処理アルゴリズムの走査順序を第１の画素ブロックの行又は列においてたどり、この走査順序を後続画素ブロックの行又は列について維持する。
【００５７】
図１及び図３乃至図５を併せて参照して、本発明のデータ・バッファリング方法及び装置の実施例を次に説明する。以下の説明のために、やはり、動き推定器（ME）が、ビデオ・フレーム１００を処理し、本発明のデータ・バッファリング方法及びデータ・バッファリング装置による一時記憶のために動きベクトルの形態でデータ構造を順次供給するものとする。動き推定器の走査順序は図１の矢印線104によって示す走査順序に対応する。更に、動き補償器（MC）は動きベクトルをデータ・バッファリング装置から読み出す。動き補償器の走査順序は、図１における矢印線１０６に示す走査順序に対応する。本発明のデータ・バッファリング方法及びバッファリング装置は、第１及び第２のデータ処理装置又はアルゴリズムの特定の性質とは無関係に動作させることが可能である。
【００５８】
図３は行列３００を表す。行列３００の構造は、図１のビデオ・フレーム１００の構造に対応する。行列３００は、本願の説明における視覚化の目的でのみ用いる。図4a)乃至図4h)は、ビデオ・フレーム１００の処理中の異なる時点におけるサーキュラー・バッファ４００を示す。図5a)乃至図5h)は、ビデオ・フレーム100に関する別々の動作段階に対応する、サーキュラー・バッファ４００の別々の動作段階間の書き込みポインタ（図５a）、c)、e)、g))及び読み出しポインタ（図５b）、d)、f)、h))の動きを示す。
【００５９】
図３の行列３００は、矢印線１０４及び１０６によって示す走査順序による、別々の動作段階における、ビデオ・フレーム１００におけるMEアルゴリズム及びMCアルゴリズムの走査処理の視覚化の役目を担う。行列３００におけるいくつかの行列セルには、タイプRn、Wm又はRn/Wmのエントリによってマーキングされている。前述のエントリは、ビデオ・フレーム100の処理中にバッファ装置の別々の動作段階において行われる書き込み（W）動作又は読み出し（R）動作を示す。特定の動作段階は、下付きの指数m又はnそれぞれによって示す。下付の指数が大きいほど、対応する動作段階は後になる。特定の行列セル(i,j)における特定のエントリWm又はRnの配置は、行列セルと同じ指数対(i,j)を有する画素ブロックに割り当てられた動きベクトルが、下付きの指数m又はnによって表す動作段階においてサーキュラー・バッファ400に書き込まれる（W）か、又はサーキュラー・バッファ400から読み出される（R）ことを示す。エントリWm及びRmは、対応する動作段階における書き込みポインタ値及び読み出しポインタ値に対する参照符号として図４及び図５においても用いている。
【００６０】
読み出し動作及び書き込み動作、又はそれぞれのポインタ割り当て工程が同じ動作段階において行われることを、指数m及びnが等しいことは示す。同じ動作段階において（すなわち、同時に）行われる書き込み動作及び読み出し動作は、実際は同じ時点で行われなくてよい。むしろ、動作段階は、一書き込み動作及び一読み出し動作を別々の時点で行う特定の時間間隔にも及び得る。サーキュラー・バッファの一動作段階中の読み出し動作及び書き込み動作の順序は重要でない。しかし、本発明のこの実施例では、同じ動作段階xにおける一読み出し動作Rx及び一書き込み動作Wxはともに、次の書き込み動作Wx+1が行われる前に行われる。それによって、読み出される前にメモリ・セルが上書きされることが妨げられる。
【００６１】
動き推定器は、サーキュラー・バッファ４００における一時記憶のために特定のビット容量の動きベクトルを供給する。サーキュラー・バッファ４００は８つのメモリ場所（それぞれは、サーキュラー・バッファ４００の一部分によって表され、対応するアドレス1,2,3,…,8によってマーキングされる）を有する。各メモリ場所は、一動きベクトルの記憶容量を有する。8個のメモリ場所という数をここでは選んでいる。画素ブロック行毎に７つの動きベクトルが存在しているからである。一般に、サーキュラー・バッファのメモリ場所の数は好ましくは、半蛇行周期毎に動き推定器によって処理される画素ブロック数を１だけ上回る。このようにして、バッファ容量をできる限り小さくしながら、読み出し前にメモリ場所が上書きされることが避けられる。更なるメモリ場所は任意であり、必須でない。その追加には、本明細書で前述したポインタ割り当てパターンと異なるポインタ割り当てパターンが必要になる。
【００６２】
図４及び図５では、色の濃い小さな丸がそれぞれのメモリ場所に描かれている。これは、図３に応じて用いる参照符号によって識別することが可能な特定の動作段階におけるポインタ位置を表している。図５では、ポインタは、サーキュラー・バッファ４００のメモリ場所に沿ったポインタ割り当ての回転運動を視覚化するためにらせん状の矢印線５０２乃至５１６によって結ばれている。
【００６３】
図4a)乃至図4h)は、サーキュラー・バッファ４００のメモリ場所にわたって分布する、メモリ場所１乃至８に現在記憶されているそれぞれの動きベクトル、及びそれぞれの現在の読み出しポインタ値及び書き込みポインタ値を識別する指数対を示す。図３のそれぞれの行列セルに示す読み出し動作段階及び書き込み動作段階、並びに、図4a）乃至図4h)に示す、別々のポインタ割り当て段階、及び、よって、バッファ動作は互いに対応している。 
図4a)は、第１の動作段階におけるサーキュラー・バッファ４００の状態を示す。ビデオ・フレーム１００の画素ブロック(1,1)を処理した後にMEアルゴリズムによって供給される動きベクトル(1,1)はメモリ場所１に記憶される。他のメモリ場所2乃至７はこの段階では用いられていない。更に、動きベクトルの最初の行が完了する前に、読み出しアクセスは行われない。書き込みポインタW0は、メモリ場所1の外端上に描かれた濃い色の丸によって表す。一般に、参照符号Wmによってマーキングされた濃い色の丸の位置は、書き込みポインタが、対応するメモリ・セルに現時に指し示すことを示し、現行動作段階は指数mによって示す。ポインタ位置を表す濃い色の丸はそれぞれ、サーキュラー・バッファ４００を表す丸の輪郭に沿った考えられる２つの方向の一方を指し示す矢印に結ばれる。前述の矢印は、サーキュラー・バッファ４００のバッファ制御装置が、次の書き込みポインタを割り当てるメモリ・セルを示す。ポインタ割り当ての回転方向は、サーキュラー・バッファのメモリ場所に対して時計回り又は反時計回りであり得るか、又は、すなわち、より大きなアドレス値に向かう方向又はより小さいアドレス値に向かう方向であり得る。本発明によれば、ポインタ割り当ての方向は、後述するように、明確に規定された動作段階において変わる。
【００６４】
図4b)は、第２の動作段階におけるサーキュラー・バッファ４００の現時の状態を示す。書き込みポインタW1は、メモリ場所8を指し示すよう示されている。動き推定器は、第１の画素ブロック行の処理を終えており、次に、第２の画素ブロック行の第１の動きベクトルを供給する。これは、画素ブロック(2,7)に割り当てられる。サーキュラー・バッファ４００は、動きベクトルの完全な第１の行をメモリ場所１乃至７に保持する。図5a)から分かるように、書き込みポインタ割り当ての時計回りの回転は、第２の動作段階まで続いている。読み出しポインタR1をメモリ場所１に示す。この第２の動作段階では、MCアルゴリズムは、動きベクトルの第１の行を、指数対(1,1)から始めて読み始める（図１及び図３参照）。何れのポインタも、後続処理工程において時計回りに回転させる。
【００６５】
図5a)は、図4a)、図4b)及び図4c)に示すものの間の動作段階を要約して、書き込みポインタの、メモリ場所1におけるその当初位置W0からメモリ位置8における位置W1への時計回りの回転を示す。書き込みポインタ割り当ては、メモリ場所７（ポインタW2）に2度目に達するまで時計回りで続く。図4c)に示すこの処理段階では、動き推定処理は、ビデオ・フレーム３００の第２の画素ブロック行の処理、画素ブロック(3.1)の動きベクトルの処理・記憶を終えており、蛇行走査順序の第２の期間を開始している。同時に、動き補償器は、第１の画素ブロック行(i=1)に対応する動きベクトルの処理を終えており、画素ブロック(2,1)を読み出し、処理する。
【００６６】
図5a)及び図5b)の比較から分かるように、読み出しポインタは当初、メモリ・セルに沿ったその時計回り回転運動において書き込みポインタよりも１メモリ場所、先行している。
【００６７】
メモリ・セル７では、読み出しポインタは、図5b)の読み出しポインタR2に示すように次のステップでメモリ場所６に進んで、回転方向を変えて、メモリ場所6、5、4、3、2、1において画素ブロック行i=2から得られる動きベクトルを読み出し続ける（図４ｃ）参照）。このステップでは、書き込みポインタ及び読み出しポインタはそれらの回転運動において互いに交差し、それによって、画素ブロック(3,1)から算出された動きベクトルによってメモリ・セル７を、動き補償器が画素ブロック(1,7)の動きベクトルを同じメモリ場所から読み出した後、直ちに上書きすることが可能になる。
【００６８】
４つの書き込みポインタ割り当て段階をよって識別することが可能である。
【００６９】
a)供給された動きベクトルの行指数が行列３００の行列行を左から右に段階的に横断する第１の書き込みポインタ割り当て段階（W0乃至W1）。同時に、書き込みポインタは、時計回り方向にポインタ値を段階的に横断する。この段階は、図4a)及び図4b)、並びに図5a)に示す。この段階は、図4e)及び図4f)、並びに図5e)に示すように後の段階に、第２の書き込みポインタ割り当て期間において通る。
【００７０】
b)供給された動きベクトルの行指数が、次の行列行を右から左に横断する第２の書き込みポインタ割り当て段階（W1乃至W2）。同時に、書き込みポインタは、時計回りの回転方向にポインタ値を段階的に横断する。この段階は、図4b)及び図4c)、並びに図5a)に示す。この段階は部分的にやはり、図4g)及び図4h)、並びに図5g)に示すように第２の書き込みポインタ割り当て期間において通る。
【００７１】
c)供給された動きベクトルの行指数が、次の行列行を左から右に段階的に横断する第３の書き込みポインタ割り当て段階（W2乃至W3）。同時に、書き込みポインタは、反時計回り方向にポインタ値を段階的に横断する。この段階は、図4c)及び図4d)、並びに図5c)に示す。
【００７２】
d)供給された動きベクトルが、次の行列行を右から左に横断する第４の書き込みポインタ割り当て段階(W3乃至W4)。同時に、書き込みポインタ値は、反時計回り方向にポインタ値を段階的に横断する。この段階は、図4d)及び図4e)、並びに図5c)に示す。
【００７３】
ポインタW0とポインタW4との間で、１つの完全な書き込みポインタ割り当て段階が過ぎている。
【００７４】
同時に、４つの読み出しポインタ割り当て段階が行われる。これらは、
e)第２の書き込みポインタ割り当て段階（W1乃至W2）と同時であり、読み取りポインタが時計回り方向にそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、時計回り方向において１ステップのポインタ値オフセットを有し、最後の割り当て工程において第１の回転方向から第２の回転方向に変わる第１の読み出しポインタ割り当て段階（R1乃至R2）。この段階は、図4b)及び図4c)、並びに図5d)に示す。
【００７５】
f)第３の書き込みポインタ割り当て段階（W2乃至W3）と同時であり、読み出しポインタは反時計回り方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、反時計回り回転方向に1ステップのポインタ値オフセットを有する第２の読み出しポインタ割り当て段階（R2乃至R3）。この段階は、図4c)及び図4d)、並びに図5d)に示す。
【００７６】
g)第４の書き込みポインタ割り当て段階（W3乃至W4）と同時であり、読み出しポインタは反時計回り回転方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、反時計回り回転方向に1ステップのポインタ値オフセットを有し、時計回り回転方向に最後の割り当てステップにおいて変わる第３の読み出しポインタ割り当て段階（R3乃至R4）。この段階は、図4d)及び図4e)、並びに図5f)に示す。
【００７７】
h)次の書き込みポインタ割り当て期間の第１の書き込みポインタ割り当て段階（W4乃至W5）と同時であり、読み出しポインタは時計回り回転方向においてそれぞれの現行ポインタ値を段階的に横断し、書き込みポインタに対して、時計回り回転方向に1ステップのポインタ値オフセットを有する第４の読み出しポインタ割り当て段階（R4乃至R5）
として識別することが可能である。
【００７８】
画像の最後の動きベクトルが書き込まれると、最後の読み出しポインタ割り当て段階は好ましくは、次の画像の第１の書き込みポインタ割り当て段階と同時である。すなわち、ポインタ割り当て手順は、新たな画像の最初で続けられる。あるいは、ビデオ系列の画像全部について同一のポインタで割り当てを始めるようにリセットを行うことが可能である。しかし、いくつかの画像にわたる連続した割り当てはより単純であり、よって、リセットを導入するよりも高速である。
【００７９】
図6は、本発明によるデータ・バッファリング装置６００の実施例のブロック図を示す。データ・バッファリング装置は、サーキュラー・バッファ６０２及びバッファ制御装置６０４を有する。第１の入力部６０６は、第１の外部処理装置（例として、動き推定器MEとする）から、2次元データ構造アレイを記憶する旨の書き込み要求を順次受け取るよう適合させる。第２の入力部６０８は、第２の外部処理装置（例として、動き補償器MCとする）から、サーキュラー・バッファ６０２に記憶されたデータ構造に対する読み出し要求を受け取るよう適合させる。
【００８０】
書き込み要求及び読み出し要求は、外部処理装置からの指数値とともに、又は外部処理装置からの指数値なしで受け取ることができる。一実施例では、指数対が書き込み要求に備えられ、入力部６０６は、指数値をバッファ制御装置６０４に、かつ、実際のデータ構造値をサーキュラー・バッファ６０２に別個に転送するよう適合させる。指数対が動き推定器によって供給されない場合、入力装置６０６は、バッファ制御装置６０８による内部的な使用のために適切な指数対を生成するよう更に適合させる。この第２の代替策は、処理されるビデオ・フレームの走査順序及び画素ブロック構造が規定されているので、所定の割り当て規則に応じて入力データ構造に割り当てる入力値を入力装置が分かっているコンスタレーションにおいて用いられる。
【００８１】
バッファ制御装置604は、サーキュラー・バッファ６０２への書き込みアクセス及び読み出しアクセスを制御し、指数値を入力装置６０４及び６０６から受け取る。書き込み要求又は読み出し要求の入力データ構造の指数対(i,j)の現行値に応じて、バッファ制御装置は、前述の一般的な方法による４つのそれぞれのポインタ割り当て段階を有する周期的な書き込みポインタ及び読み出しポインタの割り当てを行う。ポインタ割り当て方法は、ハードウェア又はソフトウェアで実現することが可能である。
【００８２】
割り当てられた書き込みポインタに基づいて、バッファ制御装置６０４は、バッファ・メモリ６０２の対応するメモリ場所にアドレス指定し、受け取られた動きベクトルをその場所下に記憶する。読み出し要求の場合、バッファ制御装置６０４は、バッファ・メモリ６０２の対応するメモリ場所に、現行読み出しポインタ値を割り当てた後、アドレス指定する。
【００８３】
一実施例では、バッファ・メモリ６０２は、容量がより大きなメモリの一部を構成する。いくつかのメモリ場所を、2次元アレイの半蛇行周期毎に受け取る対象のデータ構造の数に応じて、サーキュラー・バッファ・メモリに対して割り当てることが可能である。更に、メモリ場所の容量は、個々のデータ構造のビット・サイズに応じて変わり得る。バッファ制御装置６０４は、前述の本発明の実施例によって、協調された書き込みポインタ割り当て及び読み出しポインタ割り当てを行うために必要なメモリ場所の数を確かめ、割り当て、適切なポインタ数を管理するよう適合させる。バッファ制御装置６０４は、第１の処理装置及び第２の処理装置によって用いられる異なる走査順序に適合可能でもあり得る。
【００８４】
図７は、本発明のデータ処理装置の実施例を構成するビデオ処理装置７００の簡略ブロック図を示す。ビデオ処理装置７００は、ピクチャレート・アップコンバータであり、以下では手短にアップコンバータとして表す。前述の装置は例えば、本明細書の冒頭の部分で記載したように、テレビジョン（TV）受像機によって表示されるために、異なったビデオ走査形式を互いに変換する消費者向電子装置の分野で用いられている。例として、アップコンバータは、毎秒100フィールドのフィールド・レートをサポートするTV受像機の場合に、毎秒５０フィールドのTV伝送のフィールド間の更なる移動段階を含む中間フィールドを生成することができる。
【００８５】
図７のブロック図は、本発明に関するビデオ処理装置７００の機能ブロックのみを示す。通常、ビデオ処理装置７００は、ハードウェアで（例えば、シリコン上に集積回路として）実現される。ソフトウェアの実現形態も考えられるが、性能的に遅く、よって、消費者向電子装置における使用には好ましくない。
【００８６】
２つの処理装置（動き推定器７０２及び動き補償器７０４）を提供する。動き推定器７０２は、動き推定アルゴリズムを行う。動き推定アルゴリズムは当該技術分野において知られている。動き推定器７０２は、画像を画素ブロックに分割し、各画素ブロックに動きベクトルを割り当てるブロック・マッチング・アルゴリズムを行うよう適合させる。好ましくは、周知の3次元再帰サーチ（３DRS）アルゴリズムを用いる。
【００８７】
２つの連続した画像、フィールド又はビデオ・フレームの画素ブロックは、外部メモリから、高レベル(L1)キャッシュ・メモリ706及び低レベル(L0)キャッシュ・メモリ708（連続した画像の個別の１つについて２つの部分706.1、706.2、及び708.1、708.2をそれぞれが含む）によって得られる。L0キャッシュ・メモリ708は、２つの連続した画像それぞれの完全なスライディング・サーチ領域を保持する。各サーチ領域は、個別の画像のサブアレイを構成し、現在処理されている画素ブロックを取り囲む。L0キャッシュ・メモリ７０８の内容は、処理された画素ブロック全てによって、通常、連続した画像それぞれの領域（いくつかの画素ブロック行を含み、いくつかの連続したサーチ領域をカバーする）を保持するL1キャッシュ・メモリ７０６を介して更新される。
【００８８】
動き推定器７０２は、図１乃至図５を参照して前述したように、動きベクトルをその出力において蛇行走査順序に応じて供給する。動きベクトルは、図６を参照して更に詳細に説明されたデータ・バッファ６００にバッファリングされる。動き補償器７０４は、中間画像を生成するために、データ・バッファ６００から動きベクトルを読み出す。
【００８９】
標準品位（SD）形式を有するビデオ系列の場合、サーチ領域は通常、５ブロック行の高さを有する。動き補償走査方向と無関係に動き推定器７０２の別の走査方向に対処するのに必要なオーバヘッド・メモリは、一画素ブロック行に一画素ブロックを加えたものである（図３乃至図５を参照して記載した例を参照）。したがって、実際に、動き推定器７０２及び動き補償器７０４による共有アクセスのためには、７つのブロック行がL1キャッシュ・メモリ７０８におけるSD系列に必要である。したがって、本発明によるデータ・バッファリングはこのオーバヘッドを最小にし、従来の解決策と比較して、L1キャッシュ・メモリの容量の削減を可能にする。
【図面の簡単な説明】
【００９０】
【図１】別々の２つの処理アルゴリズムによって施される異なる走査順序の第１の例を視覚化するビデオ・フレームを示す図である。
【図２】別々の２つの処理アルゴリズムによって施される異なる走査順序の第２の例を視覚化するビデオ・フレームを示す図である。
【図３】データ・バッファリング方法及びデータ処理方法の第１の実施例を視覚化するビデオ・フレームを示す図である。
【図４ａ】図３のデータ・バッファリング及びデータ処理方法におけるサーキュラー・バッファの動作段階を示す図である。
【図４ｂ】図３のデータ・バッファリング及びデータ処理方法におけるサーキュラー・バッファの動作段階を示す図である。
【図４ｃ】図３のデータ・バッファリング及びデータ処理方法におけるサーキュラー・バッファの動作段階を示す図である。
【図４ｄ】図３のデータ・バッファリング及びデータ処理方法におけるサーキュラー・バッファの動作段階を示す図である。
【図４ｅ】図３のデータ・バッファリング及びデータ処理方法におけるサーキュラー・バッファの動作段階を示す図である。
【図４ｆ】図３のデータ・バッファリング及びデータ処理方法におけるサーキュラー・バッファの動作段階を示す図である。
【図４ｇ】図３のデータ・バッファリング及びデータ処理方法におけるサーキュラー・バッファの動作段階を示す図である。
【図４ｈ】図３のデータ・バッファリング及びデータ処理方法におけるサーキュラー・バッファの動作段階を示す図である。
【図５ａ】図３及び図４の実施例における書き込みポインタ及び読み出しポインタの周期性を視覚化する図である。
【図５ｂ】図３及び図４の実施例における書き込みポインタ及び読み出しポインタの周期性を視覚化する図である。
【図５ｃ】図３及び図４の実施例における書き込みポインタ及び読み出しポインタの周期性を視覚化する図である。
【図５ｄ】図３及び図４の実施例における書き込みポインタ及び読み出しポインタの周期性を視覚化する図である。
【図５ｅ】図３及び図４の実施例における書き込みポインタ及び読み出しポインタの周期性を視覚化する図である。
【図５ｆ】図３及び図４の実施例における書き込みポインタ及び読み出しポインタの周期性を視覚化する図である。
【図５ｇ】図３及び図４の実施例における書き込みポインタ及び読み出しポインタの周期性を視覚化する図である。
【図５ｈ】図３及び図４の実施例における書き込みポインタ及び読み出しポインタの周期性を視覚化する図である。
【図６】本発明のデータ・バッファリング装置の実施例を示すブロック図である。
【図７】本発明のデータ処理装置の実施例を示すブロック図である。
【図１】
2008537620.tif 000003
【図２】
2008537620.tif 000004
【図３】
2008537620.tif 000005
【図４ａ】
2008537620.tif 000006
【図４ｂ】
2008537620.tif 000007
【図４ｃ】
2008537620.tif 000008
【図４ｄ】
2008537620.tif 000009
【図４ｅ】
2008537620.tif 000010
【図４ｆ】
2008537620.tif 000011
【図４ｇ】
2008537620.tif 000012
【図４ｈ】
2008537620.tif 000013
【図５ａ】
2008537620.tif 000014
【図５ｂ】
2008537620.tif 000015
【図５ｃ】
2008537620.tif 000016
【図５ｄ】
2008537620.tif 000017
【図５ｅ】
2008537620.tif 000018
【図５ｆ】
2008537620.tif 000019
【図５ｇ】
2008537620.tif 000020
【図５ｈ】
2008537620.tif 000021
【図６】
2008537620.tif 000022
【図７】
2008537620.tif 000023
【国際調査報告】
2008537620.tif 000024
2008537620.tif 000025
2008537620.tif 000026