(57)【要約】長方形状動き検索のための方法が開示される。当該方法のある実施形態は、長方形の検索領域をなす複数の動き検索点に対して動き測定を実行し、前記動き測定の結果に基づいて動き検索点のうちで最小動き検索点を見出し、該最小動き検索点が当該長方形検索領域の内部領域にあれば当該ピクセルブロックの第一のビデオフレームから第二のビデオフレームへの相対的な移動に対応する動きベクトルを見出すことを含む。
2007507987.tif 000002
【特許請求の範囲】
【請求項１】
入力ビデオデータに対して参照ビデオフレームを基準とする、長方形動き検索を含む動き検索を実行し、複数の動きベクトルを生成する動き推定器と、
前記動きベクトルを使って前記入力ビデオデータを圧縮する可変長符号化器、
とを有することを特徴とするビデオエンコーダ。
【請求項２】
前記入力ビデオデータを実領域で変換する変換器と、
前記変換済みビデオデータを量子化する量子化ユニット、
とをさらに有することを特徴とする、請求項１記載のビデオエンコーダ。
【請求項３】
前記参照フレームを保存するための前記動き推定器に結合されたフレームメモリをさらに有することを特徴とする、請求項１記載のビデオエンコーダ。
【請求項４】
入力ビデオデータに対して参照ビデオフレームを基準とする、長方形動き検索を含む動き検索を実行し、複数の動きベクトルを生成し、
前記動きベクトルを使って前記入力ビデオデータを圧縮する、
ことを含むことを特徴とする方法。
【請求項５】
前記入力ビデオデータを実領域で変換し、
前記変換済みビデオデータを量子化する、
ことをさらに含むことを特徴とする、請求項４記載の方法。
【請求項６】
前記参照フレームを保存することをさらに含むことを特徴とする、請求項４記載の方法。
【請求項７】
あるピクセルブロックの、第一のビデオフレームから第二のビデオフレームへの相対的な移動を決定する方法であって：
長方形検索領域をなす複数の動き検索点に対して動き測定を実行し、
前記動き測定の結果に基づいて前記複数の動き検索点のうちの最小動き検索点を見出し、
前記最小動き検索点が前記長方形検索領域の内部領域にある場合に、当該ピクセルブロックの、前記第一のビデオフレームから前記第二のビデオフレームへの相対的な移動に対応する動きベクトルを見出す、
ことを含むことを特徴とする方法。
【請求項８】
請求項７記載の方法であって：
前記最小動き検索点が前記長方形検索領域の辺上または角にある場合に、前記最小動き検索点が実質中心になり、かつもとの長方形検索領域と重なりがあるよう前記長方形検索領域の位置を変え、位置を変えた長方形検索領域が第二の複数の動き検索点を含んでいるものとし、
前記第二の複数の動き検索点に対して動き測定を実行する、
ことをさらに含むことを特徴とする、請求項７記載の方法。
【請求項９】
前記第二の複数の動き検索点に対する動き測定が、前記複数の動き検索点のうち前記長方形検索領域と位置を変えた長方形検索領域との両方の範囲内にはいる一つまたは複数を除外することを特徴とする、請求項８記載の方法。
【請求項１０】
請求項７記載の方法であって、
前記長方形検索領域を複数のデータ単位に分割して該複数のデータ単位のそれぞれが実質同じ大きさをもち、前記複数の動き検索点の相異なる部分集合をもつようにし、前記動き測定が前記複数のデータ単位のそれぞれにおいて一つずつ実行される、
ことをさらに含むことを特徴とする方法。
【請求項１１】
前記長方形検索領域が１６の動き検索点をもつ正方形検索領域であることを特徴とする、請求項１０記載の方法。
【請求項１２】
前記正方形領域が４つのデータ単位に分割され、該４つのデータ単位のそれぞれが４つの相異なる動き検索点をもつことを特徴とする、請求項１１記載の方法。
【請求項１３】
請求項７記載の方法であって、前記最小動き検索点が前記長方形検索領域の内部領域にあった場合に前記長方形検索領域を縮小することを含む精細化動き検索を実行することをさらに含むことを特徴とする方法。
【請求項１４】
請求項７記載の方法であって、前記最小動き検索点が前記長方形検索領域の内部領域にあった場合に前記最小点のまわりでサブピクセル動き検索を実行することをさらに含むことを特徴とする方法。
【請求項１５】
ビデオデータを圧縮する方法であって：
第一のビデオフレームを参照ビデオフレームとして定義し、
前記参照ビデオフレームを基準としてある第二のビデオフレームに対して動き検索を実行し、前記参照ビデオフレームを基準とした前記第二のビデオフレームの複数の動きベクトルを決定し、
当該ビデオデータを前記参照ビデオフレームと前記第二のビデオフレームの前記複数の動きベクトルに還元する、
ことを含んでおり、前記動き検索が、
あるピクセルブロック内に長方形検索領域をなす複数の動き検索点に対する動き測定を実行し、
前記動き測定の結果に基づいて前記複数の動き検索点のうちで最小動き検索点を見出し、
前記最小動き検索点が前記長方形検索領域の内部領域にある場合には当該ピクセルブロックの前記第一のビデオフレームから前記第二のビデオフレームへの相対的な移動に対応する動きベクトルを見出す、
ことを含むことを特徴とする方法。
【請求項１６】
請求項１５記載の方法であって、前記動き検索の実行がさらに：
前記最小動き検索点が前記長方形検索領域の辺上または角にある場合に、前記最小動き検索点が実質中心になり、かつもとの長方形検索領域と重なりがあるよう前記長方形検索領域の位置を変え、位置を変えた前記長方形検索領域が第二の複数の動き検索点を含んでいるものとし、
前記第二の複数の動き検索点に対して動き測定を実行する、
ことをさらに含むことを特徴とする、請求項１５記載の方法。
【請求項１７】
前記第二の複数の動き検索点に対する動き測定が、前記複数の動き検索点のうち前記長方形検索領域と位置を変えた長方形検索領域との両方の範囲内にはいる一つまたは複数を除外することを特徴とする、請求項１６記載の方法。
【請求項１８】
請求項１５記載の方法であって、前記動き検索を実行することがさらに：
前記長方形検索領域を複数のデータ単位に分割して該複数のデータ単位のそれぞれが実質同じ大きさをもち、前記複数の動き検索点の相異なる部分集合をもつようにし、前記動き測定が前記複数のデータ単位のそれぞれにおいて一つずつ実行される、
ことを含む特徴とする方法。
【請求項１９】
プロセッサによって実行された場合に該プロセッサをして、あるピクセルブロックの第一のビデオフレームから第二のビデオフレームへの相対的な移動を決定する処理を実行せしめる命令を提供する機械アクセス可能媒体であって、前記処理が：
当該ピクセルブロック内の長方形検索領域をなす複数の動き検索点に対して動き測定を実行し、
前記動き測定の結果に基づいて前記複数の動き検索点のうちの最小動き検索点を見出し、
前記最小動き検索点が前記長方形検索領域の内部領域にある場合に、当該ピクセルブロックの、前記第一のビデオフレームから前記第二のビデオフレームへの相対的な移動に対応する動きベクトルを見出す、
ことを含むことを特徴とする媒体。
【請求項２０】
請求項１９記載の機械アクセス可能媒体であって、前記処理がさらに：
前記最小動き検索点が前記長方形検索領域の辺上または角にある場合に、前記最小動き検索点が実質中心になり、かつもとの長方形検索領域と重なりがあるよう前記長方形検索領域の位置を変え、位置を変えた長方形検索領域が第二の複数の動き検索点を含んでいるものとし、
前記第二の複数の動き検索点に対して動き測定を実行する、
ことをさらに含むことを特徴とする媒体。
【請求項２１】
請求項２０記載の機械アクセス可能媒体であって、前記第二の複数の動き検索点に対する動き測定が、前記複数の動き検索点のうち前記長方形検索領域と位置を変えた長方形検索領域との両方の範囲内にはいる一つまたは複数を除外することを特徴とする、請求項２０記載の媒体。
【請求項２２】
請求項１９記載の機械アクセス可能媒体であって、前記処理がさらに：
前記長方形検索領域を複数のデータ単位に分割して該複数のデータ単位のそれぞれが実質同じ大きさをもち、前記複数の動き検索点の相異なる部分集合をもつようにし、前記動き測定が前記複数のデータ単位のそれぞれにおいて一つずつ実行される、
ことを含むことを特徴とする媒体。
【請求項２３】
前記長方形検索領域が１６の動き検索点をもつ正方形検索領域であることを特徴とする、請求項２２記載の機械アクセス可能媒体。
【請求項２４】
前記正方形領域が４つのデータ単位に分割され、該４つのデータ単位のそれぞれが４つの相異なる動き検索点をもつことを特徴とする、請求項２３記載の機械アクセス可能媒体。
【請求項２５】
ダイナミックランダムアクセスメモリ（DRAM）デバイスと、
前記DRAMデバイスに結合されたメモリコントローラと、
レジスタファイルを定義する複数のレジスタ、および、
前記複数のレジスタに結合された並列プロセッサであって、あるピクセルブロックの、第一のビデオフレームから第二のビデオフレームへの相対的な移動を決定する処理を実行するよう動作しうる並列プロセッサ、
を有する前記メモリコントローラに結合された並列プロセッサチップ、
とを有するシステムであって、前記処理が：
当該ピクセルブロック内の長方形検索領域をなす複数の動き検索点に対して動き測定を実行し、
前記動き測定の結果に基づいて前記複数の動き検索点のうちの最小動き検索点を見出し、
前記最小動き検索点が前記長方形検索領域の内部領域にある場合に、当該ピクセルブロックの、前記第一のビデオフレームから前記第二のビデオフレームへの相対的な移動に対応する動きベクトルを見出す、
ことを含むことを特徴とするシステム。
【請求項２６】
請求項２５記載のシステムであって、前記処理がさらに：
前記最小動き検索点が前記長方形検索領域の辺上または角にある場合に、前記最小動き検索点が実質中心になり、かつもとの長方形検索領域と重なりがあるよう前記長方形検索領域の位置を変え、位置を変えた長方形検索領域が第二の複数の動き検索点を含んでいるものとし、
前記第二の複数の動き検索点に対して動き測定を実行する、
ことを含むことを特徴とする、請求項２５記載のシステム。
【請求項２７】
前記第二の複数の動き検索点に対する動き測定が、前記複数の動き検索点のうち前記長方形検索領域と位置を変えた長方形検索領域との両方の範囲内にはいる一つまたは複数を除外することを特徴とする、請求項２６記載のシステム。
【請求項２８】
請求項２５記載のシステムであって、前記並列プロセッサが複数のデータ要素を前記レジスタファイル内において前記長方形検索領域に対応する長方形領域にロードすることを特徴とする、請求項２５記載のシステム。
【請求項２９】
前記メモリコントローラに結合されたマイクロプロセッサをさらに有することを特徴とする、請求項２５記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はビデオおよびグラフィック信号処理に、より詳細にはビデオフレーム内での動き検索の実行に関する。
【背景技術】
【０００２】
ビデオデータ圧縮は、記憶スペースや伝送帯域幅を減らすため、容易に復元できる冗長データを除去する。典型的には、ビデオデータは一連のフレームの形であり、画像の多くの内容はビデオフレーム内のオブジェクトがフィールド内で動いても実質同様である。動いているオブジェクトを追跡することによって、記録されるデータの量をあるフレームと別のフレームとの間の変化分にまで減らすことができる。残りのデータは以前のフレームについて記録されたデータで代用できるのである。
【０００３】
ビデオフレーム内のピクセルのブロックがその後のフレームにおいてどのように動くかを推定するための既存の勾配降下法は、一般にフルピクセル菱形検索と称される。フルピクセル菱形検索は図１Ａおよび図１Ｂに示すような二つのレベルを使って動き検索を実行する。図１Ａを参照すると、ピクセルの測定値は、動き検索の第一レベルにおいては菱形検索パターン内の９つの検索点１０３において集められる。動き検索点における測定値は互いに比較され、参照フレーム内のピクセルブロックの各検索点が、現在のフレームのピクセルブロックにどのくらい近いかが判定される。参照フレームはビデオデータにおける以前のフレームでありうる。最も近い点が菱形検索パターン内の外側の８つの点の一つであれば、検索パターンはその点を中心とする新たな位置にシフトされる。そのような場合、新しい検索パターンは古い検索パターンとは４つの検索点を共有し、５つの新規の検索点をもつ。したがって、菱形検索パターンが右にグリッド線２本分シフトしたときには５つの新しい測定が実行される。両方の検索パターンに共通の検索点については、先の測定からのデータが再利用できるので、測定は必要ない。
【０００４】
最良測定が中心点にあれば、図１Ｂに示されるように次のレベルの検索が実行される。このレベルでは、４つの新しい動き検索点１１０が測定され、以前の測定からの中心にある点１０５のデータは再利用される。測定値が最も小さい動き検索点がフルピクセル検索位置である。
【０００５】
菱形検索は、パターンを２グリッドシフトするのに対して５つ以上の測定しか必要とされないので、高速なアルゴリズムである。しかし、菱形検索パターンの不規則な形状のため、登録ファイル内に保存される測定データに対する処理が複雑になっている。菱形検索の問題のいくつかには、データのアドレスオフセットを追跡すること、記憶スペースの不十分な使用、疎なサンプリングパターンのために真の最小を逃す可能性が含まれる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
膨大な必要計算量のため、動き検索は通例並列プロセッサによって実行される。そのような並列プロセッサの一つは単一命令多重データ（SIMD:  Single  Instruction  Multiple  Data）の演算を使用する。たとえば、動き検索の一つの測定値は差分絶対値和（SAD）、すなわち現在フレームのブロックと参照フレームのブロックとの間の差分のＬ１ノルムの測度である。動き検索のもう一つの測定値は差分平方和（SSD）、すなわち現在フレームのブロックと参照フレームのブロックとの間の差分のＬ２ノルム（ユークリッドノルム）の二乗の測度である。複数のデータ項目に対するSADまたはSSD測定値はSIMD演算によって実行されうる。典型的な並列プロセッサはメモリ階層へのデータアクセス数を減らすために大きなレジスタファイルをもつ。検索領域内の菱形検索のデータは通例そのレジスタファイルに保存される。並列プロセッサはレジスタファイル内の複数のデータ項目に、並列演算でアクセスでき、たとえばSAD演算の場合、いくつかの相続く列のデータ項目の差分絶対値和が計算される。レジスタファイル内の菱形領域の行は列数が異なるので、行内で項目のSADを計算するためにアクセスされる列の数も異なってくる。その結果、並列プロセッサは異なるアドレスオフセットをさまざまな行および列について追跡しなければならず、そのため並列演算の実行を複雑にしている。
【０００７】
本発明は、以下の詳細な記述から、そして付属の図面からより完全に理解されるであろう。ただし、それらは単に説明と理解のためであって、付属の特許請求の範囲を示されている特定の実施形態に限定するものと解釈してはならない。
【課題を解決するための手段】
【０００８】
長方形状動き検索のための方法が開示される。長方形状ブロック動き検索を実行するための方法のある実施形態は、長方形の検索領域内のいくつかの動き検索点に対して動き測定を実行し、前記動き測定の結果に従って動き検索点のうちで最小動き検索点を見出し、該最小動き検索点が当該長方形検索領域の内部領域にあれば当該長方形検索領域を前記最小動き検索点に収束させて当該ピクセルブロックの第一のビデオフレームから第二のビデオフレームへの相対的な移動を表す動きベクトルを見出すことを含む。
【０００９】
以下の記述において、数多くの特定的な詳細が述べられるが、本発明の実施形態はそうした特定的な詳細なしでも実施しうることは理解されるものである。他方、よく知られたモジュール、構造および技術は、本記載の理解を埋没させないために詳細には示していない。
【００１０】
以下の詳細な記述のいくつかの部分はアルゴリズムおよびコンピュータメモリ内のデータビットに対する演算の記号表現を用いて呈示されている。これらのアルゴリズム的記述および表現は、データ処理分野の当業者が自らの仕事の内容を他の当業者に最も効率的に伝達するために使っている手段である。アルゴリズムとはここでは、そして一般にも、所望の結果に導く一連の自己完結的な処理の系列であると考えられる。前記処理は物理量の物理的な操作を要求するものである。必須ではないが通例、そうした量は、保存、転送、組み合わせおよびその他の操作ができる電気信号または磁気信号の形をとる。時には主として慣用のため、これらの信号をビット、値、要素、文字、項目、数などと称することが便利であることがわかっている。
【００１１】
しかし、これらの、そして同様の用語はすべて適切な物理量と関連しており、単にそれらの量に適用される便利なラベルにすぎないことを留意すべきである。以下の議論から明らかなように、特別に断らない限り、本記載を通じて、「処理」または「計算」または「計数」または「決定」または「表示」などといった用語を用いた議論は、コンピュータシステムのレジスタおよびメモリ内の物理的な（電子的な）量として表現されているデータを操作し、コンピュータシステムメモリまたはレジスタまたはその他のそのような情報記憶、伝送もしくは表示装置内の物理的な量として同様に表現される他のデータに変換する
コンピュータシステムまたは同様の電子計算装置の動作およびプロセスを言っていることが了解される。
【００１２】
本発明はまた、ここに記載される動作を実行するための装置にも関する。この装置は必要とされる目的のために特別に構築されたものでもよいし、あるいは汎用コンピュータであって該コンピュータ内に保存されるコンピュータプログラムによって選択的に活性化もしくは再構成設定されるのでもよい。そのようなコンピュータプログラムはコンピュータ可読記憶媒体に保存されうる。そのような媒体としては、これに限定されるものではないが、任意の種類のフロッピー（登録商標）ディスク、光ディスク、CD-ROM、光磁気ディスク、読み出し専用メモリ（ROM）、ランダムアクセスメモリ、EPROM、EEPROM、磁気もしくは光カードまたは電子的な命令を保存するのに好適な任意の種類の媒体であってそれぞれコンピュータシステムバスに結合されているものがある。
【００１３】
ここに呈示される動作および表示はいかなる特定のコンピュータまたはその他の装置に本来的に関係しているものでもない。さまざまな汎用システムがここに記載される思想に従ったプログラムとともに使用されうるし、あるいは前記動作を実行するためにより特化した装置を構築することが便利であると判明することもありうる。多様なこれらのシステムのための必要とされる構造は以下の記述から明らかとなろう。さらに、本発明はいかなる特定のプログラミング言語との関連で記載されているのでもない。ここに記載される本発明の思想を実現するためには多様なプログラミング言語が使用されうることは理解されるであろう。
【００１４】
機械可読媒体とは機械（たとえばコンピュータ）によって読める形で情報を保存または伝送するためのいかなる機構をも含む。たとえば、機械可読媒体には、読み出し専用メモリ（「ROM」）；ランダムアクセスメモリ（「RAM」）；磁気ディスク記憶媒体；光記憶媒体；フラッシュメモリ素子；電気的、光学的、音響学的もしくはその他の形の伝搬信号（たとえば搬送波、赤外線信号、デジタル信号など）；などが含まれる。
【発明を実施するための最良の形態】
【００１５】
ある実施形態では、長方形検索パターンが、あるビデオフレームから別のビデオフレームにかけてのあるピクセルブロックの相対的な移動を決定するための検索領域を定義するために使われる。ビデオフレームは複数のピクセルブロックを含みうる。図２は参照窓２００内の検索領域のある実施形態を示す。図２を参照すると、参照窓２００は１６×１６のグリッドである。検索領域２０１は４×４の正方形で領域内に１６の動き検索点を含んでいる。周知のとおり、正方形とはすべての辺が等しい一種の長方形である。ここで４×４の正方形を使っているのは解説のためであることを了解しておくべきである。他の実施形態では、たとえば４×８、１６×８、１６×１６など、縦横の大きさが異なる長方形の検索領域を使うこともできることは明らかであろう。図２を参照すると、検索領域は４つの内側検索点（たとえば点２２０）と正方形領域２０１の辺に沿った１２の検索点（たとえば点２１０）をもつ。この１２個の検索点は４つの内側点との対比で外側点と称される。ある実施形態では、内側点と外側点のそれぞれは、参照フレーム内の一つのピクセルブロックに対応する。
【００１６】
ある実施形態では、現在のビデオフレーム内において、参照ビデオフレーム内の別のピクセルブロックに一致するピクセルブロックを見出すために、一つまたは複数のピクセル属性の測定が検索領域２０１内の各動き検索点においてなされる。該属性はピクセル強度、ピクセル色などを含みうる。ある実施形態では、各検索点でのピクセルブロックの測定値は、参照ビデオフレーム内のピクセルブロックと所定の基準に基づいて比較される。ある実施形態では、二つのフレーム内のピクセルブロックにおけるピクセルの間でのピクセル強度の差分絶対値和（SAD:  sum  of  the  absolute  difference）が計算される。ある実施形態では、最小SADをもつ検索点（最小点とも称される）が選択される。
【００１７】
ある実施形態では、参照ビデオフレームから現在のビデオフレームにかけてのあるピクセルブロックの相対的な移動を見出すために検索が実行される。最小点が正方形検索領域内の内側点の一つである場合には、参照フレーム内で前記最小点を中心とするブロックが現在のフレーム内のピクセルブロックの最も近い一致相手となる。ひとたび当該ピクセルブロックの最も近い一致相手が参照フレーム内にみつかれば、参照フレームから現在フレームにかけての当該ピクセルブロックの相対的な移動を表す動きベクトルが決定できる。
【００１８】
ある実施形態では、一組のビデオフレームをもつビデオデータは、圧縮フォーマットにおいて最初のフレームを参照フレームとして保存し、後続のフレームをさまざまなピクセルブロックの以前のフレームからの動きベクトルおよび動き予測残差として保存することによって圧縮される。変換符号化およびエントロピー符号化といった道具が前記の最初のフレームおよび後続のフレームを圧縮および／または保存するために使うことができる。圧縮ビデオデータの嵩は圧縮しないビデオデータよりも小さくなり、よってそのビデオデータを伝送するのに使われる帯域幅とそのビデオデータを保存するのに使われる記憶スペースが節減される。
【００１９】
ある実施形態では、前記最小点が外側点のうちのいずれか一つであった場合には検索は継続される。検索領域がシフトされ、見出された最小点が新しい検索領域の実質中心となるようにされる。たとえば、図２を参照すると、８つの可能な移動方向がある。すなわち、４つの角方向の場合と、４つの辺方向の場合である。新しい検索位置は、長方形検索領域の各辺上の角でない２つの外側辺位置については共通である。新しい検索領域のいくつかの例が図２に示してある。すなわち、左上角方向の場合２０３、右シフトの場合２０５、下シフトの場合２０７である。
【００２０】
ある実施形態では、二つの検索パターンに共通な動き検索点の測定値は、時間節約のため再利用される。図２を参照すると、角方向の場合２０３には４つの共通な動き検索点、すなわち、動き検索点２２３がある。したがって、そのシフト検索パターンにおいては、１２の共通でない検索点について測定が実行される。右シフトの場合２０５または下シフトの場合２０７のような辺方向の場合、８つの共通する検索点がある。したがって、このシフト検索パターンにおいては、８つの共通でない検索点について測定が実行される。換言すれば、検索パターンが２グリッドシフトしたとき、８つまたはそれ以上の測定が実行される。
【００２１】
ある実施形態では、４×４の検索領域はさらに４つの２×２ウォーク・パターン（タイルともいう）に区画される。動き測定はそれぞれの２×２タイルごとに一つずつ実行される。
【００２２】
図３は長方形検索パターンを用いた動き検索を実行するためのプロセスのある実施形態のフロー図である。このプロセスは、ハードウェア（たとえば回路、専用論理素子など）、ソフトウェア（汎用コンピュータシステムまたは専用機において実行されるようなもの）または両者の組み合わせを有しうる処理論理によって実行される。図３に戻ると、処理論理は、現在のフレームのピクセルブロックのために、参照ビデオフレームにおけるある選ばれた出発検索位置を中心とする参照窓をロードする（処理ブロック３１０）。ある実施形態では、参照窓は３２×３２ピクセル配列を含んでおり、長方形検索領域は４×４の正方形である。ある実施形態では、４×４の正方形検索領域はさらに４つの２×２のデータ単位に分割される。このデータ単位はタイルとも称される。ある実施形態では、処理論理は、この正方形の検索領域の４つのタイルのそれぞれにおける動き測定をオンにするためにある４ビットマスクを「１１１１」にセットする（処理ブロック３２０）。ここで、マスクの各ビットが前記正方形検索領域における相異なるタイルに対応している。
【００２３】
ある実施形態では、処理論理は各タイルにおいて動き測定を実行する（処理ブロック３３０）。処理論理は一つのタイルにおける動き測定を完了させてから別のタイルに進んでもよい。これはタイル・ウォーキングともいう。ある実施形態では、処理論理は、当該検索領域中のある検索点にあるピクセルの一つまたは複数の属性を測定する。属性の例としては、ピクセル強度、ピクセル色などが含まれる。ある実施形態では、処理論理は測定された属性のSADを計算して、１６の動き検索点のうちで最小のSADをもつ点を見出す（処理ブロック３４０）その点は最小点とも称される。
【００２４】
ある実施形態では、処理論理は、最小点が当該検索領域における内側点の一つであれば検索を終了する（処理ブロック３９０）。最小点が当該検索領域の外側点の一つであれば、その場合は処理論理は正方形検索領域をシフトさせ、当該最小点が実質中心にくるようにする（処理ブロック３６０）。現在の検索領域とシフトされた検索領域とは重なり合うので、重なり合った範囲内の動き検索点にあるピクセルを測定する必要はない。ある実施形態では、処理論理は、最小点が現在の検索領域の角にある場合には両方の検索領域に共通の４つの検索点のSAD値を、最小点が現在の検索領域の角ではない現在の検索領域の辺上にある場合には両方の検索領域に共通の８つの動き検索点のSAD値をコピーする。ある実施形態では、処理論理は、前記マスクを２つの１または３つの１を用いてセットし、シフトされた検索領域内のタイルの２つまたは３つにおいて動き検索測定をオンにする。２つまたは３つのいずれにするかは、前記最小点が正方形検索領域の角にあるかどうかに依存する（処理ブロック３７０）。
【００２５】
ある実施形態では、処理論理は、シフトされた検索領域のピクセルブロック内にあるピクセルのいずれかが参照窓の外であれば、別のピクセルブロックをロードし、該ブロックを中心合わせをしなおす（処理ブロック３８０）。次いで処理論理は処理ブロック３３０〜３８０を反復する。ある実施例では、動き検索は、あるビデオフレームから別のビデオフレームにかけてのあるピクセルブロックの相対的な移動を判定するために実行される。ある実施例では、処理論理は、ビデオフレーム全体を保存するのではなく、あるビデオフレームから別のビデオフレームにかけてのピクセルブロックの相対的な移動を表す動きベクトルを保存することによってビデオデータを圧縮する。
【００２６】
ある実施形態では、８×８、４×８、１６×４などのより大きな長方形検索パターンが使われる。最小点が長方形検索領域の辺上でなく、角でもなければ、その検索は検索領域を縮小することによって収束する。ある実施形態では、サブピクセルの動きベクトルがサポートされており、したがって、整数の動き検索の最小点が当該検索領域の内側点の一つであるとき、検索はサブピクセルレベルで継続される。図４は長方形の検索パターンを用いた２レベルの階層的動き検索の一つの実施例を示している。図４を参照すると、第一のレベルの長方形検索パターンは４×４＝１６の検索点を含んでいる。隣り合う検索点は２ピクセル離れている。第一のレベルの検索後、検索が内側の検索点４２０に収束した場合、第二のレベルの整数点動き検索が点４２０のまわりで実行される。具体的には、最小点４２０の近傍の８つの新たな標本位置４１０（図４では星で示している）が第二レベルの検索で測定される。９つの位置のうちで最小値をもつ位置が収束した整数位置である。ある実施形態では、サブピクセル動きは半ピクセルの解像度である。前記８つの標本位置４１０によって形成される形に似た形の、前記収束した整数位置の近傍の半ピクセル位置にある新しい８つの標本位置が測定される。９つの位置（８つの半ピクセル位置と収束した整数位置）のうちで最小値をもつ位置が収束した半ピクセル位置となる。
【００２７】
図５は、並列プロセッサチップ５００のある実施形態を示している。並列プロセッサチップ５００は並列プロセッサ５４２および一組のレジスタ５４４を含んでいる。前記一組のレジスタはレジスタファイルとも称される。並列プロセッサ５４２はエンコーダ５５１およびデコーダ５５３を含んでいる。あるエンコーダの実施例の詳細は、のちに図７を参照しつつ議論する。並列プロセッサはレジスタファイル５４４にデータを書き込んだり、レジスタファイル５４４からデータを読んだりする。ある実施形態では、レジスタファイル５４４内に保存されているデータは、列と行の形に配列されている。
【００２８】
ある実施形態では、並列プロセッサ５４２は単一命令多重データ（SIMD）アーキテクチャを採用し、レジスタファイル５４４への行ベースおよび列ベースでのアクセスをサポートしている。並列プロセッサ５４２は、ビデオフレーム内の当該長方形検索領域に対応する測定データをレジスタファイルにロードする。ある実施形態では、レジスタファイル５４４は論理的に長方形状に配列され、したがってビデオフレーム内の長方形検索領域はレジスタファイル内の領域に便利な形で対応付けられる。ピクセルデータをレジスタファイル内の諸長方形領域内に保存することにより、並列プロセッサ５４２が諸検索領域のピクセルデータにアクセスし、これに演算を行うことが可能になる。そのような並列アクセス機能は、並列プロセッサ５４２のスループットを増加させる。
【００２９】
図６はレジスタファイル６００の実施例を示している。正方形６１０内のレジスタは、ビデオフレーム内の正方形の検索領域の検索点のデータを保存する。当該検索領域の最小点が正方形の右の辺上にあるとすると、並列プロセッサはこの正方形の検索領域を右にシフトさせる。新しい検索領域に対応するデータは、レジスタファイル６００内の正方形６２０内のレジスタ内にある。ある実施形態では、レジスタファイル内のデータの位置は検索点の位置に対応する。したがって、並列プロセッサ５４２は、時間節約のため重なり合う検索領域を処理する際にはすでにレジスタファイル内に保存されているデータを再利用する。さらに、重なり合う範囲内の検索点のデータをレジスタファイル内の別の位置にコピーすることは不要である。データが保存されている位置が検索点の位置に対応しているからである。
【００３０】
さらに、長方形検索パターンの使用により、該長方形パターンはダイヤ型検索パターンすなわち菱形検索パターンと違って長方形内に論理的に配列されているので、並列プロセッサはレジスタファイル内の長方形パターンに対するアドレスオフセットをすぐ検索でき、このためレジスタファイル内のデータの再利用がより容易になる。さらに、並列プロセッサ５４２は、データが検索領域に対応する長方形領域内に保存されているときにはより多くのデータを再利用できる。
【００３１】
図７は、ビデオエンコーダのある実施例を示している。ビデオエンコーダ７００はMPEGビデオエンコーダでありうる。エンコーダ７００は離散コサイン変換器（DCT:  discrete  cosine  transformer）７１０、動き補償器７２０、動き推定器７３０、フレームメモリ７４０、クリッピングを実行する論理回路７５０、可変長符号化器（VLC:  variable  length  coder）７６０、逆離散コサイン変換器（IDCT:  inverse  discrete  cosine  transformer）７７０、量子化ユニット７８０、量子化解除ユニット７９０、走査ユニット７９２および逆走査ユニット７９４を含む。
【００３２】
ある実施例では、入力ビデオデータは動き推定器７３０に与えられる。該動き推定器７３０は現在のビデオフレームを参照ビデオフレームと比較するために長方形動き検索を実行する。動き推定器は前記長方形動き検索に加えて菱形状動き検索のような他の種類の動き検索を実行してもよい。出力はVLC７６０のほか動き補償器７２０にも与えられる。動き補償器はフレームメモリ７４０からも入力を受け取り、入力データに対する動き補償を決定する。この動き補償が現在のビデオフレームから減算器７０５によって引き算される。補償されたビデオデータはDCT７１０に入力される。DCT７１０は変換済みビデオデータを量子化ユニット７８０に出力する。量子化ユニット７８０は量子化されたビデオデータを走査ユニット７９２に出力する。
【００３３】
ある実施例では、走査ユニット７９２はデータをデータ要素のストリームに編成する。たとえば、走査ユニット７９２はデータ要素のストリームを、８×８の量子化された変換済みビデオデータのブロックを走査するジグザグによって出力する。量子化後のデータ要素の多くは０なので、データは２つの変数、すなわちRUNおよびLEVELの組み合わせとしてフォーマットされる。RUNは、０でない値LEVELに先行する０の数である。したがって、量子化ユニットの出力は(RUN,LEVEL)というシンボルのシーケンスからなりうる。さらに、量子化ユニットは、MPEG-2エンコードのようにデータ圧縮が非可逆の場合、一部の情報を棄てることもある。走査ユニット７９２は次いで量子化されたデータをVLC７６０に出力する。ある実施例では、量子化されたデータはデータ要素のストリームとして編成される。ある実施例では、VLC７６０は各(RUN,LEVEL)対を、ビットパターンに対して割り当てられるハフマン探索表の組を通じて渡す。前記ビットパターンは異なる(RUN,LEVEL)シンボルに対しては異なるビット数を有していてもよい。すなわち、ビットパターンは可変長でもよい。
【００３４】
VLC７６０のほか、走査ユニット７９２はまた逆走査ユニット７９４にもデータを出力する。逆走査ユニット７９４はビデオデータのストリームを８×８の量子化された変換済みビデオデータに逆に戻す。逆走査ユニット７９４はデータを量子化解除ユニット７９０に出力する。量子化解除ユニット７９０はデータに対してなされた量子化を逆転させ、データを逆DCT７７０に出力する。逆DCT７７０の出力は、フレームメモリ７４０からのデータに加算される。ある実施例ではその和は８ビットより大きい、すなわち０から２５５の範囲を超えるので、その和はクリッピングを実行するための論理回路７５０に入力される。論理回路７５０はピクセルごとの入力を、０から２５５の範囲に収まるよう打ち切る。ある実施例では、０より小さいいかなる入力値も０とされ、２５５より大きいいかなる入力値も２５５とされ、０から２５５の範囲のいかなる入力値も不変とされる。クリッピングの結果は次いでフレームメモリ７４０に保存される。フレームメモリに保存された結果はその後、将来のビデオフレームのための参照フレームとして使われうる。
【００３５】
図８は、コンピュータシステム８００の実施例を示している。システム８００はプロセッサ８１０、ダイナミックランダムアクセスメモリ（DRAM）８３０、メモリコントローラ（MCH）８２０およびグラフィックチップ８４０を含んでいる。プロセッサ８１０、DRAM８３０およびグラフィックチップ８４０はMCH８２０に結合されている。
【００３６】
ある実施例では、グラフィックプロセッサ８４０はビデオエンコードを実行できる並列プロセッサである。グラフィックチップ８４０はレジスタの集合８４４およびグラフィックプロセッサ８４２を含む。レジスタの集合８４４はレジスタファイルと称される。ある実施例では、レジスタファイルは列および行の形に配列されている。グラフィックプロセッサ８４２は前記レジスタの集合８４４に結合されている。
【００３７】
ある実施例では、グラフィックプロセッサ８４２は、長方形検索パターンを使ってビデオフレーム内での動き検索を実行する。ピクセルブロックに対して長方形検索パターン内にはいくつかの動き検索点がある。グラフィックプロセッサ８４２は動き検索点のそれぞれに対して動き測定を実行して、前記動き検索点のそれぞれについてのSAD値を計算する。ある実施形態では、最小のSAD値をもつ動き検索点が最小点として同定される。最小点が長方形検索領域の外側点であれば、グラフィックプロセッサ８４２はその最小点が中心になるよう検索領域をシフトさせ、シフトされた検索領域内の動き検索点に対して動き測定を反復する。外側点でない場合には、グラフィックプロセッサ８４２は検索を終了し、当該ピクセルブロックの動きベクトルを計算する。グラフィックプロセッサ８４２は測定データ、SAD値または動きベクトルをレジスタ８４４に保存しうる。ビデオフレームそのものではなくビデオフレームの動き検索データを保存することによって、グラフィックプロセッサ８４２はビデオデータを圧縮する。
【００３８】
上記の議論は単に本発明の代表例となる実施形態を述べるものである。そのような議論、付属の図面および請求項から当業者は、付属の特許請求の精神および範囲から外れることなくさまざまな修正がなし得ることをすぐにも認識するであろう。よって前記の記載は限定的なものではなく解説のためのものであると見なされるべきものである。
【図面の簡単な説明】
【００３９】
【図１Ａ】菱形検索の第一レベルにおける動き検索点を示す図である。
【図１Ｂ】菱形検索の第二レベルにおける動き検索点を示す図である。
【図２】検索領域のある実施形態を示す図である。
【図３】長方形検索パターンを用いた動き検索を実行するためのプロセスのある実施形態のフロー図である。
【図４】長方形検索パターンのある実施形態を示す図である。
【図５】並列プロセッサチップのある実施形態を示す図である。
【図６】レジスタファイルの実施例を示す図である。
【図７】ビデオエンコーダのある実施形態を示す図である。
【図８】コンピュータシステムの実施例を示す図である。
【図１Ａ】
2007507987.tif 000003
【図１Ｂ】
2007507987.tif 000004
【図２】
2007507987.tif 000005
【図３】
2007507987.tif 000006
【図４】
2007507987.tif 000007
【図５】
2007507987.tif 000008
【図６】
2007507987.tif 000009
【図７】
2007507987.tif 000010
【図８】
2007507987.tif 000011
【国際調査報告】
2007507987.tif 000012
2007507987.tif 000013