(57)【要約】ビデオ・グラフィックデータを圧縮するシステムおよび方法が提供される。  このシステムおよび方法は、グラフィックス・パイプラインにおいて、オブジェクトをモデル化するビデオ・グラフィックデータから、このオブジェクトに対応する頂点データを生成すること、頂点データに基づいて、ピクセル・データで構成される現在のフレームおよびピクセル・データで構成される参照フレームを生成するためにビデオ・グラフィックデータをレンダリングすること、現在のフレーム内のピクセル・データで構成されるブロックの動きベクトルを計算するため、参照フレーム内の探索エリアを定義すること、を含む。それから現在のフレームは動きベクトルを使用して圧縮される。探索エリアを定義するためにグラフィックス・パイプラインからの頂点データを使用することは、動きベクトルを生成し、データ圧縮を実行するのに必要な探索量を実質的に減らす。
2005523541.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトをモデル化するビデオ・グラフィックデータから、グラフィックス・パイプラインによってそのオブジェクトに対応する頂点データを生成するステップと、
ピクセル・データで構成される現在のフレームおよびピクセル・データで構成される参照フレームを生成すべく、前記ビデオ・グラフィックデータをレンダリングするステップと、
前記現在のフレーム内のピクセル・データで構成されるブロックについての動きベクトルを計算すべく、前記頂点データに基づいて、前記参照フレーム内の探索エリアを定めるステップと、を含む、
ビデオデータの圧縮方法。
【請求項２】
前記オブジェクトは、移動可能なオブジェクトを含む、請求項１記載の方法。
【請求項３】
前記ブロックは、前記オブジェクトのうちの１つの、少なくとも一部を含む、請求項２記載の方法。
【請求項４】
前記参照フレーム内の前記１つの移動可能なオブジェクトに対応する頂点のビューポート座標に基づいて、前記探索エリアを定めるステップをさらに含む、請求項３記載の方法。
【請求項５】
前記探索エリアは、前記参照フレーム内の前記１つの移動可能なオブジェクトを取り囲むものである、請求項３記載の方法。
【請求項６】
前記探索エリアは、その形が矩形である、請求項５記載の方法。
【請求項７】
前記動きベクトルに基づいて、前記現在のフレームを圧縮するステップをさらに含む、請求項１記載の方法。
【請求項８】
前記圧縮するステップは、ＭＰＥＧフォーマットに従って前記現在のフレームを圧縮するステップをさらに含む、請求項７記載の方法。
【請求項９】
前記現在のフレーム内のピクセル・データで構成され、移動可能なオブジェクトを含まない第２ブロックについての動きベクトルを計算するため、前記頂点データと無関係に定められる第２探索エリアを定めるステップをさらに含む、請求項２記載の方法。
【請求項１０】
前記グラフィックス・パイプラインで、前記ビデオ・グラフィックデータについて幾何学的変換を行うステップと、
前記ビデオ・グラフィックデータをビューボリュームにクリッピングするステップと、
投影平面に前記ビデオ・グラフィックデータを投影するステップと、
前記ビデオ・グラフィックデータをビューポートに変形するステップと、をさらに含む、請求項１記載の方法。
【請求項１１】
前記ビデオ・グラフィックデータは、ビデオゲームに関連する、請求項１記載の方法。
【請求項１２】
前記現在のフレームおよび前記参照フレームを、ネットワークを通じて送信するステップをさらに含む、請求項１記載の方法。
【請求項１３】
前記ネットワークは、インターネットを含む、請求項１２記載の方法。
【請求項１４】
オブジェクトをモデル化するビデオ・グラフィックデータから、グラフィックス・パイプラインによってそのオブジェクトに対応する頂点データを生成する頂点データ生成手段と、
ピクセル・データで構成される現在のフレームおよびピクセル・データで構成される参照フレームを生成すべく、前記ビデオ・グラフィックデータをレンダリングするレンダリング手段と、
前記現在のフレーム内のピクセル・データで構成されるブロックについての動きベクトルを計算するため、前記頂点データに基づいて、前記参照フレーム内の探索エリアを定める探索エリア画定手段と、を含む、
ビデオデータを圧縮するシステム。
【請求項１５】
前記オブジェクトは、移動可能なオブジェクトを含む、請求項１４記載のシステム。
【請求項１６】
前記ブロックは、前記オブジェクトのうちの１つの、少なくとも一部を含む、請求項１５記載のシステム。
【請求項１７】
前記参照フレーム内の前記１つの移動可能なオブジェクトに対応する頂点のビューポート座標に基づいて、前記探索エリアを定める画定手段をさらに含む、請求項１６記載のシステム。
【請求項１８】
前記探索エリアは、前記参照フレーム内の前記１つの移動可能なオブジェクトを取り囲むものである、請求項１６記載のシステム。
【請求項１９】
前記探索エリアは、その形が矩形である、請求項１８記載のシステム。
【請求項２０】
前記動きベクトルに基づいて、前記現在のフレームを圧縮する圧縮手段をさらに含む、請求項１４記載のシステム。
【請求項２１】
前記圧縮手段は、ＭＰＥＧフォーマットに従って前記現在のフレームを圧縮する圧縮手段をさらに含む、請求項２０記載のシステム。
【請求項２２】
前記現在のフレーム内のピクセル・データで構成される、移動可能なオブジェクトを含まない第２ブロックについての動きベクトルを計算するため、前記頂点データと無関係に定める第２探索エリアを定める第２探索エリア画定手段をさらに含む、請求項１５記載のシステム。
【請求項２３】
前記グラフィックス・パイプライン内で、前記ビデオ・グラフィックデータについて幾何学的変換を行う変換手段と、
前記ビデオ・グラフィックデータをビューボリュームにクリッピングするクリッピング手段と、
投影平面に前記ビデオ・グラフィックデータを投影する投影手段と、
前記ビデオ・グラフィックデータをビューポートに変形する変形手段と、をさらに含む、請求項１４記載のシステム。
【請求項２４】
前記ビデオ・グラフィックデータは、ビデオゲームに関連する、請求項１４記載のシステム。
【請求項２５】
前記現在のフレームおよび前記参照フレームを、ネットワークを通じて送信する送信手段をさらに含む、請求項１４記載のシステム。
【請求項２６】
前記ネットワークは、インターネットを含む、請求項２５記載のシステム。
【請求項２７】
オブジェクトをモデル化するビデオ・グラフィックデータから、グラフィックス・パイプラインによってそのオブジェクトに対応する頂点データを生成すると共に、ピクセル・データで構成される現在のフレームおよびピクセル・データで構成される参照フレームを生成すべく、前記ビデオ・グラフィックデータをレンダリングするように構成される、第１プロセッサと、
前記現在のフレーム内のピクセル・データで構成されるブロックについての動きベクトルを計算するため、前記頂点データに基づいて、前記参照フレーム内の探索エリアを定めるように構成される、第２プロセッサと、
を含む、ビデオデータを圧縮するシステム。
【請求項２８】
前記オブジェクトは、移動可能なオブジェクトを含む、請求項２７記載のシステム。
【請求項２９】
前記ブロックは、前記オブジェクトのうちの１つの、少なくとも一部を含む、請求項２８記載のシステム。
【請求項３０】
前記第２プロセッサは、さらに、前記参照フレーム内の前記１つの移動可能なオブジェクトに対応する頂点のビューポート座標に基づいて、前記探索エリアを定めるように構成される、請求項２９記載のシステム。
【請求項３１】
前記探索エリアは、前記参照フレーム内の前記１つの移動可能なオブジェクトを取り囲むものである、請求項２９記載のシステム。
【請求項３２】
前記探索エリアは、その形が矩形である、請求項３１記載のシステム。
【請求項３３】
前記第２プロセッサは、さらに、前記動きベクトルに基づいて、前記現在のフレームを圧縮するように構成される、請求項２７記載のシステム。
【請求項３４】
前記第２プロセッサは、さらに、ＭＰＥＧフォーマットに従って前記現在のフレームを圧縮するように構成される、請求項３３記載のシステム。
【請求項３５】
前記第２プロセッサは、さらに、前記現在のフレーム内のピクセル・データで構成され、移動可能なオブジェクトを含まない第２ブロックについての動きベクトルを計算するため、前記頂点データと無関係に定められる第２探索エリアを定めるように構成される、請求項２８記載のシステム。
【請求項３６】
前記第１プロセッサは、さらに、前記グラフィックス・パイプラインで前記ビデオ・グラフィックデータについて幾何学的変換を行い、
前記グラフィックス・パイプラインにおいて、前記ビデオ・グラフィックデータをビューボリュームにクリッピングし、前記グラフィックス・パイプラインにおいて、投影平面に前記ビデオ・グラフィックデータを投影し、前記グラフィックス・パイプラインにおいて、前記ビデオ・グラフィックデータをビューポートに変形するように構成される、請求項２７記載のシステム。
【請求項３７】
前記ビデオ・グラフィックデータは、ビデオゲームに関連する、請求項２７記載のシステム。
【請求項３８】
前記第２プロセッサは、さらに、前記現在のフレームおよび前記参照フレームを、ネットワークを通じて送信するように構成される、請求項２７記載のシステム。
【請求項３９】
前記ネットワークは、インターネットを含む、請求項３８記載のシステム。
【請求項４０】
前記第１プロセッサおよび前記第２プロセッサは、記憶メディアに格納されたソフトウェアを実行するようにプログラムされたプロセッサを含む、請求項２７記載のシステム。
【請求項４１】
前記第１プロセッサおよび前記第２プロセッサは、特定用途向け集積回路を含む、請求項２７記載のシステム。
【請求項４２】
前記第１プロセッサおよび前記第２プロセッサは、ゲーム装置に組み入れられる、請求項２７記載のシステム。
【請求項４３】
前記第２プロセッサは、ＭＰＥＧエンコーダを含む、請求項２７記載のシステム。
【請求項４４】
前記第１プロセッサは、記憶メディアに格納されたソフトウェアを実行するようにプログラムされたプロセッサを含む、請求項４３記載のシステム。
【請求項４５】
グラフィックス・パイプラインから、ピクセル・データで構成される現在のフレームと、ピクセル・データで構成される参照フレームと、前記グラフィックス・パイプラインによってレンダリングされたオブジェクトに対応する頂点データとを受信するように構成されるプロセッサを含み、
前記プロセッサは、さらに、前記頂点データに基づいて前記参照フレーム内の探索エリアを定め、前記現在のフレーム内のピクセル・データで構成されるブロックについての動きベクトルを計算し、前記動きベクトルに基づいて、前記現在のフレームを圧縮するように構成される、
ビデオデータを圧縮するためのシステム。
【請求項４６】
前記オブジェクトは、移動可能なオブジェクトを含む、請求項４５記載のシステム。
【請求項４７】
前記ブロックは、前記移動可能なオブジェクトのうちの１つの、少なくとも一部を含む、請求項４６記載のシステム。
【請求項４８】
前記プロセッサは、さらに、前記参照フレーム内の前記１つの移動可能なオブジェクトに対応する頂点のビューポート座標に基づいて、前記探索エリアを定めるように構成される、請求項４７記載のシステム。
【請求項４９】
前記探索エリアは、前記参照フレーム内の前記１つの移動可能なオブジェクトを取り囲むものである、請求項４７記載のシステム。
【請求項５０】
前記探索エリアは、その形が矩形である、請求項４９記載のシステム。
【請求項５１】
前記プロセッサは、さらに、ＭＰＥＧフォーマットに従って前記現在のフレームを圧縮するように構成される、請求項４５記載のシステム。
【請求項５２】
前記プロセッサは、さらに、前記現在のフレーム内のピクセル・データで構成され、移動可能なオブジェクトを含まない第２ブロックについての動きベクトルを計算するため、前記頂点データと無関係に定められる第２探索エリアを定めるように構成される、
請求項４６記載のシステム。
【請求項５３】
前記ビデオデータは、ビデオゲームに関連する、
請求項４５記載のシステム。
【請求項５４】
前記プロセッサは、さらに、前記現在のフレームおよび前記参照フレームを、ネットワークを通じて送信するように構成される、
請求項４５記載のシステム。
【請求項５５】
前記ネットワークは、インターネットを含む、
請求項５４記載のシステム。
【請求項５６】
前記プロセッサは、記憶メディアに格納されたソフトウェアを実行するようにプログラムされたプロセッサを含む、
請求項４５記載のシステム。
【請求項５７】
前記プロセッサは、特定用途向け集積回路を含む、
請求項４５記載のシステム。
【請求項５８】
前記プロセッサは、ゲーム機に組み込まれている、
請求項４５記載のシステム。
【請求項５９】
前記プロセッサは、ＭＰＥＧエンコーダを含む、
請求項４５記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを圧縮するためのシステムおよび方法に関し、より詳しくは、コンピュータによって生成されたグラフィックデータを圧縮するシステムおよび方法に関する。
【背景技術】
【０００２】
ビデオデータ、特に、コンピュータによって生成されるビデオ・グラフィックデータ（例えばコンピュータ・ゲーム用のビデオ・グラフィックデータ）の準備、蓄積および送信には、大規模なコンピュータ資源と広帯域のネットワーク接続が必要である。
インターネットのようなローカル・エリア・ネットワークまたは広域ネットワークを通じて接続される個々のユーザにより構成されるグループの間で、このようなデータがリアル・タイムに送信される場合、これらは特に必要とされる。このような送信は、例えばインターネットを通じてビデオゲームをプレイする場合に起こる。しかも、このような遊び方はますます普及しつつある。
【０００３】
ビデオデータの送信に必要とされるネットワークのキャパシティおよびコンピュータ資源の量を少なくするため、データを圧縮する様々なエンコード方式が使用される。
これらのデータ圧縮方式としては、ＭＰＥＧ（Motion Picture Experts Group）エンコード標準の様々なバージョン（例えばＭＰＥＧ１、ＭＰＥＧ２、ＭＰＥＧ４およびその他）が挙げられる。
これらのデータ圧縮方式は、動画シーケンスを送信し再生するのに必要なイメージ情報量を、シーケンス中の余分で非本質的な情報を排除することにより、減らす。
【０００４】
例えば、動画シーケンスの２つの隣接フレーム間では、ピクセルで構成されるいくつかのブロックが僅かにシフトしているという違いしかない場合が多い。
ピクセルで構成される大きなブロック、例えば空、壁その他の静止オブジェクトの領域を表わすブロックは、多くの場合、連続フレーム間で全く変化しない。
ＭＰＥＧのような圧縮アルゴリズムは、それぞれのフレーム用に送信または格納されるデータ量を減らすため、この一時的な冗長性を利用する。
【０００５】
例えば、ＭＰＥＧ標準では、３タイプのフレーム、すなわち、フレーム内符号化フレーム（Ｉフレーム）（intra frames）、順方向予測符号化フレーム（Ｐフレーム）（predicted frames）、および双方向予測符号化フレーム（Ｂフレーム）（bi-directionally interpolated frames ）が定義される。
図１に示されるように、Ｉフレームは、ＢフレームおよびＰフレームの参照フレーム（reference frames）であり、中程度にしか圧縮されていない。Ｐフレームは前のフレームを参照してエンコードされる。この前のフレームは、ＩフレームまたはＰフレームのいずれかであり得る。Ｂフレームは、前のフレームおよび後のフレームの両方に関連してエンコードされる。Ｂフレームの参照フレームもまた、ＩフレームまたはＰフレームのいずれかであり得る。Ｂフレームは参照フレームとして使用されない。
【０００６】
参照フレームからＰフレームおよびＢフレームをエンコードするため、ＭＰＥＧ方式は、様々な動き予測アルゴリズム（motion estimation algorithms）を使用する。
これらの動き予測アルゴリズムには、フルサーチ・アルゴリズム、階層的な探索アルゴリズム（hierarchical searching algorithms）、およびテレスコピック・アルゴリズム（telescopic algorithms）が含まれる。
図２に示すように、ＭＰＥＧ標準の下では、各フレームは典型的に、マクロブロックと呼ばれる１６×１６ピクセルのブロックに分割される。
現在のフレームのマクロブロックは、マクロブロックが現在のフレームにおけるそのブロックの位置から現在のフレーム内を移動する距離を予測することによって、参照フレームを使用してエンコードされる。
動き予測アルゴリズムは、参照フレーム中の最も一致するブロックを探知するため、現在のフレームの各マクロブロックをその参照フレームの探索エリア内の複数のマクロブロックと比較することによって、この予測を行なう。
例えば、現在のフレーム２０７のマクロブロック２０１については、参照フレーム中の最も一致するブロックを探知するために、参照フレーム２０９の探索エリア２０３内で比較が行われる。この比較は、現在のフレームのマクロブロック２０１と参照フレームの各マクロブロック２０５との間で行われる。
参照フレーム内におけるこの最も一致するマクロブロックの位置は、それから現在のフレームのマクロブロック２０１の動きベクトルを計算するのに使用される。
現在のフレーム２０７については、マクロブロック２０１に対応するすべてのビデオデータを送信するのではなく、このブロックに関しては動きベクトルだけが送信される。このように、現在のブロックについてのビデオデータが圧縮される。
【０００７】
しかしながら、動き予測アルゴリズムを実行することは、さらに相当なコンピュータ資源を必要とする。
現在のフレームの各マクロブロックを１つ以上の参照フレームの多数のマクロブロックと比較しなければならないので、莫大な計算が必要となる。
例えば、３ステップ・サーチ・アルゴリズム（ＴＳＳ）（階層アルゴリズム）は、探索エリアの中心位置およびその周囲の８つの位置における一致を評価する。
それから、探索エリアを半分に縮小すべく、最も小さな差異を示す位置が、次の探索エリアの中心になる。この手順が三度繰り返される。
【０００８】
このように、特にインターネットおよび他のネットワークを通じてリアル・タイムにビデオゲームをすることができるシステムの需要の増加を考慮して、ビデオ・グラフィックデータを圧縮する、より効率的でより有効な方法が必要とされる。
【発明の開示】
【０００９】
ＭＰＥＧエンコーダのようなデータ圧縮エンコーダでは、ビデオデータのソースに関わらず同じ方法でビデオデータを圧縮している。
したがって、デジタルカメラによってレコードされた実際の動画からのビデオデータ、およびコンピュータによって生成された、シミュレートされたビデオデータは、いずれも同じデータ圧縮形式および動き予測アルゴリズムに従って圧縮される。
しかし、ビデオデータがコンピュータによって生成される場合、オブジェクトの性質および動きに関する情報は、データの符号化および圧縮より前に把握されている。
現在のデータ圧縮エンコーダと異なり、本発明はこの情報を、データ圧縮を行なうのに必要な計算上のステップを縮小するために利用する。
【００１０】
本発明はその一態様において、ビデオデータを圧縮する方法を提供する。
本発明の方法は、オブジェクトをモデル化するビデオ・グラフィックデータから、グラフィックス・パイプラインによってそのオブジェクトに対応する頂点データを生成することを含む。
この方法は、ピクセル・データで構成される現在のフレームおよびピクセル・データで構成される参照フレームを生成すべく、ビデオ・グラフィックデータをレンダリングすることをさらに含む。
この方法はまた、現在のフレーム内のピクセル・データで構成されるブロックにおける動きベクトルを計算するため、頂点データに基づいて、参照フレーム内の探索エリアを定義することを含む。
【００１１】
オブジェクトは、好ましくは、移動可能なオブジェクトを含み、ブロックは、好ましくは、移動可能なオブジェクトのうちの１つの、少なくとも一部を含む。
本発明の方法は、好ましくは、参照フレーム内の１つの移動可能なオブジェクトに対応する頂点のビューポート座標に基づいて探索エリアを画定あるいは定めることをさらに含む。
この探索エリアは、参照フレーム内の１つの移動可能なオブジェクトを取り囲み、その形は矩形であることが好ましい。
本発明の方法はまた、好ましくは、動きベクトルに基づいて、現在のフレームをＭＰＥＧフォーマットに圧縮することを含む。
【００１２】
本発明の方法はまた、好ましくは、頂点データと無関係に、現在のフレーム内のピクセル・データで構成される第２ブロックについての動きベクトルを計算するため、第２探索エリアを定めることを含む。このピクセル・データで構成される第２ブロックは、移動可能なオブジェクトを含まない。
さらに、本発明の方法はまた、好ましくは、グラフィックス・パイプラインでビデオ・グラフィックデータについて幾何学的変換を行うこと、ビデオ・グラフィックデータをビューボリューム（視体積）にクリッピングすること、投影平面にビデオ・グラフィックデータを投影すること、およびビデオ・グラフィックデータをビューポートに変形することを含む。
ビデオ・グラフィックデータは、好ましくは、ビデオゲームに関連する。そして、現在のフレームおよび参照フレームの両方は、好ましくは、インターネットのようなネットワークを通じて送信される。
【００１３】
別の態様においては、本発明は、ビデオデータを圧縮するシステムを提供する。
このシステムは、オブジェクトをモデル化するビデオ・グラフィックデータから、グラフィックス・パイプラインによってそのオブジェクトに対応する頂点データを生成し、ピクセル・データで構成される現在のフレームおよびピクセル・データで構成される参照フレームを生成するビデオ・グラフィックデータをレンダリングするように構成される、第１プロセッサを含む。
このシステムは、頂点データに基づいて参照フレーム内の探索エリアを定義し、現在のフレーム内のピクセル・データで構成されるブロックについての動きベクトルを計算するように構成される、第２プロセッサをさらに含む。
【発明を実施するための最良の形態】
【００１４】
図３は、ビデオゲームのコンピュータ・シミュレーション中に表示されるようなビデオ・グラフィックデータのフレームを生成する、グラフィックス・パイプラインの概略図である。
このグラフィックス・パイプラインの機能は、ハードウェア、ソフトウェア、またはこの２つを組み合わせたものによって実現できる。
例えば、これらの機能は、マイクロプロセッサ、ハードワイヤードのデジタル回路、特定用途向け集積回路（ＡＳＩＣ）、またはその他のデジタル回路のようなプログラムされたプロセッサによって実行されてもよいし、ソフトウェアによって実行されてもよい。
これらの装置は、１つ以上の半導体チップ上の集積回路として実装されてもよい。ソフトウェアは、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気ディスク、光ディスク、またはその他の適切な記憶メディアに格納されていてもよい。
ハードウェアとソフトウェアは、ゲーム装置、サーバ・コンピュータ、デスクトップ・コンピュータ、ハンドヘルド・コンピュータ、ポータブル・コンピュータ、セットトップボックス、またはその他の計算装置の一部でもよい。
コンピュータ・システムはスタンドアロンの装置であってもよいし、インターネットのようなネットワークに接続されていてもよい。
【００１５】
図３に記載されたグラフィックス・パイプラインは、ワールド座標系として知られている、デカルト座標系（ｘ、ｙ、ｚ）において移動可能なオブジェクトおよび静止オブジェクトをモデル化するグラフィックデータのデータベース（図示しない）を含む。
移動可能なオブジェクトには、キャラクタ、自動車、発射体、その他コンピュータ・シミュレーションの間に移動可能なオブジェクトの全てまたは一部が含まれる。
静止オブジェクトには、地面、建物、その他シミュレーションの間、ワールド座標系における固定位置にとどまるオブジェクトの全てまたは一部が含まれる。
この移動可能なオブジェクトおよび静止オブジェクトの世界は、コンピュータ・シミュレーションが達成されるグラフィックス・パイプラインに生データを供給する。
モデル化においては、プリミティブとして知られている基本となる構築ブロックのグループを使用して、そのデータベースにおいて各オブジェクトを表すことが含まれる。
これらのプリミティブは、一般に三角形、矩形およびその他の多角形を含む。
このデータベースは、各オブジェクトに対応するプリミティブの頂点のデカルト座標と、ライティング、シェーディング、色およびテクスチャのような各頂点に関連する情報とを含む。  
【００１６】
データベースのグラフィックデータに基づくコンピュータ・ビデオシミュレーション、例えばビデオゲーム、を行う間、シミュレーションプログラムの進行およびユーザからの入力によって、ワールド座標系内にモデル化された移動可能なオブジェクトが移動され、オブジェクトに対するユーザの視線の方向および距離が変化する。
ディスプレイ・スクリーンを通じてユーザにオブジェクトを適切に表示するために、グラフィックス・パイプラインのステップを実行するコンピュータ・システムは、機能ブロック３０１で、リアル・タイムにオブジェクトについての幾何学的変換を実行する。
これらの幾何学的変換は、移動（translation）、スケーリングおよび回転を含み、ほとんどの場合、２つのＭマトリックスをかけることで実行することができる。
【００１７】
移動には、オブジェクトの各頂点のｘ、ｙおよびｚ座標に値を加算することが含まれる。その結果、そのオブジェクトは回転することなくワールド座標系内に移動される。
スケーリングには、オブジェクトの位置または向きを変更せずに、オブジェクトのサイズを変更することが含まれる。オブジェクトの頂点とあらかじめ定められた中心点との間の距離を計るため、例えば各オブジェクトの頂点にファクタを適用することによって、オブジェクトのサイズを変化することができる。
回転では、オブジェクトをスライドさせることなく、回転軸の周りにオブジェクトの各頂点が回る。
【００１８】
機能ブロック３０３において、コンピュータシステムは、ビューボリュームに関して幾何学的に変換されたプリミティブをクリッピングする。
このビューボリュームは一般的に、水平視野（horizontal field of view）を定義する左側面および右側面、垂直視野（vertical field of view）を定義する上側面および下側面、最も近い位置と最も遠い位置の視覚的な隔たりを定義する近い方の側面および遠い方の側面を備えた六面を有する錐台（frustum）である。
ビューボリューム内にないオブジェクトまたはオブジェクトの一部は、廃棄（discard）される。
【００１９】
機能ブロック３０５において、コンピュータシステムは、二次元の投影平面にビューボリューム内のオブジェクトを投影する。
この投影平面は、ワールド座標系を見る人の視線方向に垂直であり、それゆえ、投影面（view plane）と呼ばれる。
このステップは、透視投影または平行投影の技術を使用して、二次元の投影平面上に三次元のオブジェクトの各頂点をマッピングすることを含む。
例えば、ｘ’、ｙ’、ｚ’が変換されたワールド座標系（このワールド座標系においては、ｚ’は投影平面に垂直であり、ｘ’とｙ’は投影平面内にある。）の座標を表わす場合、このステップは、各オブジェクトの頂点に対するｘ’とｙ’の値を、ｚ’の値で割ることを含む。
そうすることによって、オブジェクトは投影平面上で平らになるので、遠くのオブジェクトはより小さく見え、近いオブジェクトはより大きく見える。
【００２０】
機能ブロック３０７においては、コンピュータシステムは、オブジェクトをビューポート内に変換する。
ビューポートとは、コンピュータ・シミュレーションを視認するのに使用されるコンピュータ・スクリーン、テレビ・スクリーンまたはその他のディスプレイ装置（図示されない）の物理的な領域である。
この変換は、オブジェクトの投影平面のｘ’、ｙ’座標系とビューポートのｘ”、ｙ”座標系との間の最終的なスケーリングを含む。
【００２１】
最後に、機能ブロック３０９において、コンピュータシステムは、ピクセル・データで構成されるビデオフレームを生成するためにオブジェクトのラスタ化およびレンダリングを実行する。
オブジェクトのラスタ化およびレンダリングは、各オブジェクトの各プリミティブ内にある各走査ラインの最初と最後のピクセルを定義すること、これらの最初のピクセルと最後のピクセルの間でピクセルを定義すること、これらの全てのピクセルに対するライティング情報、色情報、シェーディング情報、テクスチャ情報、混合情報を生成することを含む。
最終的なピクセル・データは、ディスプレイ・スクリーンにビデオフレームを表示する際の使用に備えてフレーム・バッファ（図示しない）に格納される。
最終的なピクセル・データはまた、圧縮されて格納されるか、またはディスプレイ用の別のコンピュータシステムにネットワークを通じて送信されてもよい。
【００２２】
図３のグラフィックス・パイプラインにおいて実行されたステップの結果、三次元のワールド座標系中の各オブジェクトに対応するプリミティブの各頂点ｘ、ｙ、ｚは、ディスプレイ・スクリーンの二次元の座標系の頂点ｘ”、ｙ”に変換される。また、これらのプリミティブに対応するピクセルが、ラスタ化およびレンダリングされる。
【００２３】
図４に、ラスタ化およびレンダリングされたピクセル・データを圧縮して送信する本発明の具体例を示す。
現在のフレーム４１３および参照フレーム４１５は、コンピュータ・シミュレーションからのピクセル・データで構成される２つのフレームである。
現在のフレーム４１３は、データ圧縮方式（例えば、ＭＰＥＧ標準）に従って、参照フレーム４１５に基づいて圧縮されることになっている。
現在のフレーム４１３および参照フレーム４１５内のピクセルの位置は、ビューポートのｘ”、ｙ”座標によって識別される。
図４に示すように、移動可能なオブジェクト４０１は、現在のフレーム４１３の右下部分に位置し、マクロブロック４０５、４０７、４０９および４１１内に位置する。
他方、参照フレーム４１５においては、移動可能なオブジェクト４０１は、フレームの左上部分に位置する。
したがって、参照フレーム４１５の生成から、現在のフレーム４１３が生成されるまでの間に、オブジェクト４０１はシミュレーションの結果、ビューポートの左上部分からビューポートの右下部分まで移動している。
それゆえ、オブジェクト４０１の一部を含んだマクロブロック４０５、４０７、４０９および４１１の各々もまた、この間にビューポートの左上部分からビューポートの右下部分まで移動している。
【００２４】
マクロブロック４０５、４０７、４０９および４１１の動きベクトルを計算するために従来方式を使用する動き予測アルゴリズムが使用される場合には、参照フレーム４１５内の最も一致するブロックを見つけるために、現在のフレーム４１３内のこれらのブロックの位置を取り囲む非常に広い探索エリアが必要となる。
このように広い探索エリア内において、このような動き予測アルゴリズムを実行することは、かなりのコンピュータ資源を消費する。
【００２５】
しかしながら、本発明によれば、オブジェクト４０１の位置を取り囲む領域をずっと少なくすべく、参照フレーム４１５内の移動可能なオブジェクト４０１の位置が確認されると共に、この位置がブロック４０５、４０７、４０９および４１１の探索エリアを制限する基準（reference）として使用される。
この位置を確認するために、現在のフレーム４１３および参照フレーム４１５をレンダリングする前の、グラフィックス・パイプラインからのオブジェクトのプリミティブについての頂点データが使用される。
【００２６】
図４に示すように、オブジェクト４０１の頂点４１７、４１９、４２１および４２３のビューポート座標は、外側の境界（outer boundary）およびオブジェクト４０１を含む参照フレーム４１５内の矩形の領域４２５の頂点を定義する。
頂点４１７は、領域４２５におけるｙ”座標の最大値を定義し、頂点４１９は、領域４２５におけるｘ”座標の最小値を定義し、頂点４２１は、領域４２５におけるｙ”座標の最小値を定義し、また頂点４２３は、領域４２５におけるｘ”座標の最大値を定義する。
したがって、領域４２３の頂点についてのビューポート座標は、最大値をmax、最小値をminとして、（minｘ”、maxｙ”）、（minｘ”、minｙ”）、（maxｘ”、minｙ”）、（maxｘ”、maxｙ”）である。
【００２７】
領域４２５の上述の境界を均一に拡張することで、探索エリア４０３が定められる。
現在のフレーム４１３においてオブジェクト４０１の全てまたは一部を含む全てのマクロブロックについて、従来の動き予測アルゴリズムを、その探索エリアを探索エリア４０３に制限するように修正する。
したがって、マクロブロック４０５、４０７、４０９および４１１について、動き予測アルゴリズムはその探索エリアをエリア４０３に制限する。
現在のフレーム４１３において移動可能なオブジェクトを含んでいないマクロブロックについては、動き予測アルゴリズムは、現在のフレーム４１３内のそのマクロブロックの位置を取り囲む従来の探索エリアを使用して、動きベクトルを計算する。
ピクセル・データのラスタ化およびレンダリングより前のグラフィックス・パイプラインによって生成されたオブジェクトに対応するプリミティブの頂点データから、現在のフレームおよび参照フレーム内の移動可能なオブジェクトを同定でき、またこのオブジェクトの位置を得ることができる。
これらの頂点データには、オブジェクトのプリミティブの頂点についてのワールド座標、オブジェクトのプリミティブの頂点についての予測平面座標、およびオブジェクトのプリミティブの頂点についてのビューポート座標が含まれる。
【００２８】
本発明に従ってビデオ・グラフィックデータをエンコードし圧縮するシステムの一実施形態のブロック図を、図５に示す。
グラフィックス・パイプラインの機能ブロック３０１、３０３、３０５、３０７および３０９は、図３において記載されたものと同一のものであり、同一の機能を実行する。
ビデオエンコーダ５１３は、ＭＰＥＧ１エンコーダ、ＭＰＥＧ２エンコーダ、ＭＰＥＧ４エンコーダまたはその他の一時的な冗長性を利用するデータ圧縮エンコーダとすることができる。
【００２９】
動き推定器（motion estimator）５１１は、機能ブロック３０９からレンダリングされたピクセル・データのフレーム、機能ブロック３０７からこれらのフレーム内に描かれた移動可能なオブジェクトの頂点についてのビューポート座標、および探索エリア検知器５０９から参照フレーム内の探索エリアのビューポート座標を受信する。
動き推定器５１１は、この情報を使用して参照フレームに関する個々の現在のフレームのマクロブロックの動きベクトルを計算すると共に、現在のビデオフレームを圧縮する際に使用されるビデオエンコーダ５１３にこれらの動きベクトルを送信する。
動き推定器５１１は、これらの動きベクトルを計算すべく、以下に記載の方法により修正された、フルサーチ・アルゴリズム、階層的な探索アルゴリズム（hierarchical searching algorithms）、およびテレスコピック・アルゴリズム（telescopic algorithms）のような、動き予測アルゴリズムを実行する。
ビデオエンコーダ５１３は、これらの動きベクトルおよび機能ブロック３０９からレンダリングされたビデオフレームを受信し、ローカル・エリア・ネットワークまたは広域ネットワーク（例えばインターネット）、あるいはその他の伝送ネットワークのようなネットワークを通じて送信するための圧縮ビデオデータのビットストリームを生成する。
【００３０】
動き推定器５１１は、圧縮されることになっている現在のフレームの各マクロブロック、および機能ブロック３０７からの移動可能なオブジェクトの頂点についてのビューポート座標を調査する。
あるマクロブロック内に、動いているオブジェクトの全てまたは一部が描かれることを頂点データが示す場合、そのマクロブロックについての参照フレーム内の探索エリアは、探索エリア検知器５０９からの情報に基づいて定められる。
他方、機能ブロック３０７からの頂点データが、動いているオブジェクトがそのマクロブロック内に描かれないことを示す場合には、動き推定器５１１は、従来の方式に基づいて、参照フレーム内の探索エリアを現在のフレーム内のそのマクロブロックの位置を取り囲む領域として定義する。
【００３１】
探索エリア検知器５０９は、ビデオシミュレーションを生成するのに使用されるグラフィックデータのデータベース内にモデル化されたすべてのオブジェクトの頂点についての変形された三次元のワールド座標、これらのオブジェクトの二次元の投影平面座標およびこれらのオブジェクトの二次元のビューポート座標を、それぞれ機能ブロック３０１、機能ブロック３０５および機能ブロック３０７から、受信する。
探索エリア検知器５０９はこれらのデータを使用して、上述したような個々の移動可能なオブジェクトを取り囲む適切な探索エリアの頂点についてのビューポート座標を生成する。
【００３２】
探索エリア検知器５０９、動き推定器５１１およびビデオエンコーダ５１３は、ハードウェア、ソフトウェアまたはこの２つを任意に組み合わせて実装されてもよい。
例えば、探索エリア検知器５０９、動き推定器５１１およびビデオエンコーダ５１３の機能は、マイクロプロセッサ、ハードワイヤードのデジタル回路、特定用途向け集積回路（ＡＳＩＣ）またはその他のデジタル回路のようなプログラムされたプロセッサによって実装されてもよいし、ソフトウェアによって実装されてもよい。
これらの装置は、１つ以上の半導体チップ上の集積回路として実装されてもよい。ソフトウェアは、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気ディスク、光ディスク、またはその他の適切な記憶メディアに格納されていてもよい。
ハードウェアとソフトウェアは、ゲーム装置、サーバ・コンピュータ、デスクトップ・コンピュータ、ハンドヘルド・コンピュータ、ポータブル・コンピュータ、セットトップボックス、またはその他の計算装置の一部でもよい。
コンピュータ・システムはスタンド・アロンの装置であってもよいし、インターネットのようなネットワークに接続されていてもよい。
【００３３】
上述した好ましい具体例は、発明の趣旨および範囲内にある多数の変形例および組み合わせを含む。
その結果、好ましい具体例についてのこの記載は、発明の単なる例示であって、これに制限されるものではないことが理解される。
本発明の範囲は、以下に添付された請求項によって、次のように記載される。
【図面の簡単な説明】
【００３４】
【図１】ＭＰＥＧ圧縮方式の、Ｉフレーム、Ｂフレーム、およびＰフレームの概略図。
【図２】参照フレームからの現在のフレームを予測する、動き予測アルゴリズムの探索ステップの概略図。
【図３】ビデオ・グラフィックデータを生成する際にコンピュータシステムによって実行される、グラフィックス・パイプラインのステップの概略図。
【図４】本発明による、動き予測アルゴリズムの探索ステップの概略図。
【図５】本発明による、ビデオ・グラフィックデータをエンコードするためのシステムのブロック図。
【図１】
2005523541.tif 000003
【図２】
2005523541.tif 000004
【図３】
2005523541.tif 000005
【図４】
2005523541.tif 000006
【図５】
2005523541.tif 000007
【国際調査報告】
2005523541.tif 000008
2005523541.tif 000009
2005523541.tif 000010