(57)【特許請求の範囲】
【請求項１】
プロセッサが、フレームレートを変換するためビデオファイルのフレーム間の動きを推定するのに使用される大きく疎な連立一次方程式を表すマトリックスと、前記連立一次方程式の解の第１ベクトル推定値であって、第１の空間的順序により配置された複数の成分を有するベクトルとを乗算するステップと、
前記プロセッサが、前記連立一次方程式の解の第２ベクトル推定値であって、前記乗算の積である第２ベクトル推定値を生成するステップと、
前記プロセッサが、前記第１ベクトル推定値と前記第２ベクトル推定値とが所定量未満しか異なっていないとき、前記連立一次方程式の解の設定するステップと、
を有する方法であって、
前記マトリックスは、前記ベクトルの各成分が前記ベクトルにおいて空間的に配置される前記第１の空間的順序と異なる第２の空間的順序により前記各成分と乗算され、前記ベクトルの複数の成分がパラレルに乗算される方法。
【請求項２】
前記プロセッサが、前記複数の成分を、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令セットを使用して乗算する、請求項１記載の方法。
【請求項３】
前記連立一次方程式の解は、前記第２ベクトル推定値に設定される、請求項１記載の方法。
【請求項４】
前記プロセッサが、前記ベクトルの各成分を、前記第１の空間的順序と空間的に異なる前記第２の空間的順序を生成するよう再配置するステップをさらに有する、請求項１記載の方法。
【請求項５】
前記プロセッサが、ビデオファイルを入力フレームレートから出力フレームレートに変換中、前記連立一次方程式の解を用いて補間された画像フレームを生成するステップをさらに有する、請求項１記載の方法。
【請求項６】
前記プロセッサが、ディスプレイの出力フレームレートを用いてディスプレイ上に前記ビデオファイルを表示するステップをさらに有する、請求項５記載の方法。
【請求項７】
前記第１の空間的順序と異なる前記第２の空間的順序は、前記ベクトルのマッピングマトリックスへのマッピングに対応し、
前記プロセッサが、前記マッピングマトリックスの近傍成分が再配置されたマッピングマトリックスにおいて非近傍となるように、前記マッピングマトリックスを前記再配置されたマッピングマトリックスに再配置するステップをさらに有する、請求項１記載の方法。
【請求項８】
フレームレートを変換するためビデオファイルのフレーム間の動きを推定するのに使用される大きく疎な連立一次方程式を表すマトリックスと、前記連立一次方程式の解の第１ベクトル推定値であって、第１の空間的順序により配置された複数の成分を有するベクトルとを乗算する処理を実行する実行ユニットを有するシステムであって、
前記実行ユニットは、前記連立一次方程式の解の第２ベクトル推定値であって、前記乗算の積である第２ベクトル推定値を生成し、前記第１ベクトル推定値と前記第２ベクトル推定値とが所定量未満しか異なっていないとき、前記連立一次方程式の解を設定する処理を実行し、
前記マトリックスは、前記ベクトルの各成分が前記ベクトルにおいて空間的に配置される前記第１の空間的順序と空間的に異なる第２の空間的順序により前記各成分と乗算され、前記ベクトルの複数の成分がパラレルに乗算されるシステム。
【請求項９】
前記実行ユニットは、メモリからのＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令セットを使用して前記複数の成分をパラレルに乗算する処理を実行する、請求項８記載のシステム。
【請求項１０】
前記実行ユニットは、前記ベクトルの順序付けされた各成分を、前記第１の空間的順序と空間的に異なる第２の空間的順序を生成するよう再配置する、請求項８記載のシステム。
【請求項１１】
前記実行ユニットは、前記ビデオファイルを入力フレームレートから出力フレームレートに変換中、前記連立一次方程式の解を用いて補間された画像フレームを生成する、請求項８記載のシステム。
【請求項１２】
前記出力フレームレートを用いて前記ビデオファイルを表示するよう動作するディスプレイをさらに有する、請求項１１記載のシステム。
【請求項１３】
前記出力フレームレートを有する前記ビデオファイルを格納するメモリをさらに有する、請求項１１記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、フレームレートを変換するためビデオファイルのフレーム間の動きを推定するのに利用可能な連立一次方程式を解くための繰り返し方法に関する。
【背景技術】
【０００２】
ビデオ入力ファイルは、固有のフレームレートを有するかもしれない。ファイルを出力（再生など）する装置は、異なるフレームレートを有するかもしれない。例えば、５０Ｈｚのビデオファイルが、１００Ｈｚのフレームレートによりビデオを再生するテレビに入力されるかもしれない。入力ファイルのフレームレートが出力ファイルのフレームレートと異なるとき、フレームレートを両立させる必要が存在するかもしれない。
【０００３】
フレームの表示レートを変更するため、フレームレート変換アルゴリズムが開発されてきた。フレームレート変換アルゴリズムは、例えば、ビデオ表示のための合計時間や近くスピードを変更することなく、入力フレームレートをスピードアップ又はダウンするため、期間後とのフレーム数を増減するかもしれない。一部の基本的アルゴリズムは、単にフレームを複製又は削除するだけかもしれない。他のものは、例えば、動き補償アルゴリズムなどを利用して、フレーム間の動きを補間するかもしれない。
【０００４】
ビデオにおける動き推定は、例えば、（偏）微分方程式（ＰＤＥ）などによりモデル化されるかもしれない。離散化スキーム（有限差分処理など）が、ＰＤＥに対してその数値解を求めるため適用されてもよい。この離散化は、大きく疎である連立一次方程式（ＬＳＳＬＥ）などの連立一次方程式を生成するかもしれない。各ＬＳＳＬＥは、フレームのペアの各フレーム間の変化又は動きを記述するかもしれない。フレームレート変換アルゴリズムは、例えば、フレームレート変換などを実行するため、ＬＳＳＬＥの数値解を利用するかもしれない。ＬＳＳＬＥは、電子エンジニアリング、流体力学、コンピュータビジョン／グラフィックス、光フロー推定、超解像度処理、画像ノイズ低減などの多数の科学及びエンジニアリング分野において知られている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＬＳＳＬＥを解くことは、計算量の大きなものであるかもしれない。例えば、フレームセットのフレームレートを変換するためＬＳＳＬＥを解くことは、フレームの再生時間より長くかかるかもしれない。再生装置が変換されたフレームを待機している間に、再生レートのラグが生じるかもしれない。このラグを補償するため、フレームレート変換アルゴリズムは、低下された動き推定を有するよりフレーム及び／又はより少数のフレームを生成することによって、ビデオの品質を低下させるかもしれない。これは、よりぎくしゃくしたビデオを生じさせるかもしれない。
【０００６】
本発明の課題は、上記問題点に鑑み、フレームレートを変換するためビデオファイルのフレーム間の動きを推定するのに利用可能な連立一次方程式を効率的に解くための技術に関する。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、本発明の一特徴は、フレームレートを変換するためビデオファイルのフレーム間の動きを推定するのに使用される大きく疎な連立一次方程式を表すマトリックスと、前記連立一次方程式の解の第１ベクトル推定値であって、ある順序に構成された複数の成分を有するベクトルとを乗算するステップと、前記連立一次方程式の解の第２ベクトル推定値であって、前記乗算の積である第２ベクトル推定値を生成するステップと、前記第１ベクトル推定値と前記第２ベクトル推定値とが所定量未満しか異なっていないとき、前記連立一次方程式の解の設定するステップと、を有する方法であって、前記マトリックスは、前記ベクトルの各成分が前記ベクトルにおいて構成される順序と異なる順序により前記各成分と乗算され、前記ベクトルの複数の成分がパラレルに乗算される方法に関する。
【発明の効果】
【０００８】
本発明によると、フレームレートを変換するためビデオファイルのフレーム間の動きを推定するのに利用可能な連立一次方程式を効率的に解くことができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、本発明の一実施例によるシステムの概略図である。
【図２】図２は、本発明の一実施例によるプロセッサパイプラインの概略図である。
【図３】図３は、本発明の一実施例による初期的なオーダリングを有するベクトルｘから新たなオーダリングを有するベクトルｘ’へのエントリの再配置の概略図である。
【図４】図４Ａ及び４Ｂは、本発明の一実施例による初期的なオーダリングを有するベクトルｘと新たなオーダリングを有するベクトルｘ’とを表すマトリックスを示す。
【図５】図５は、本発明の一実施例による方法のフローチャートである。
【発明を実施するための形態】
【００１０】
以下の詳細な説明では、本発明の各実施例の完全な理解を提供するため、多数の具体的詳細が与えられる。しかしながら、本発明の各実施例はこれらの具体的な詳細なしに実現可能であることが、当業者により理解されるであろう。他の例では、説明を不明りょうにしないため、周知の方法、処理、コンポーネント及び回路は、詳細には説明されていない。
【００１１】
特段の断りがない場合、以下の説明から明らかなように、明細書を通じて、“処理”、“計算”、“算出”、“決定”などの用語を用いた説明は、計算システムのレジスタ及び／又はメモリ内の電子量などの物理量として表現されるデータを、計算システムのメモリ、レジスタ又は他の情報ストレージ、送信装置又は表示装置内の物理量として同様に表現される他のデータに処理及び／又は変換するコンピュータ、計算システム又は同様の電子計算装置のアクション及び／又は処理を表す。さらに、“複数”という用語は、明細書を通じて２以上のコンポーネント、装置、要素、パラメータなどを記載するのに利用されるかもしれない。
【００１２】
本発明の各実施例は、様々なアプリケーションに利用可能である。本発明はこれに限定されるものでないが、ここに開示される回路及び技術は、パーソナルコンピュータ（ＰＣ）、画像若しくはビデオ再生装置、デジタルビデオディスク（ＤＶＤ）プレーヤー、無線装置若しくはステーション、ビデオ若しくはデジタルゲーム装置若しくはシステム、画像収集システム、処理システム、可視化若しくは表示システム、デジタル表示システム、通信システムなどの多数の装置に利用されるかもしれない。
【００１３】
本発明の各実施例は、例えば、第１フレームレートによりビデオを入力し、第２フレームレートによりビデオを出力するシステムなどにおいて利用されるかもしれない。再生時間又は認知される再生時間は同じままであるが、単位時間毎に表示されるフレーム数は変化するかもしれない。フレームレート変換は、例えば、ＬＳＳＬＥを解くなどによって、中間フレームを補間することを含むかもしれない。本発明の各実施例は、例えば、図１に示されるようなＰａｃｋｅｄ命令を実行するため、コンピュータシステム上で実行されるかもしれない。
【００１４】
本発明の一実施例によるコンピュータシステムを概略的に示す図１が参照される。コンピュータシステム１００は、本発明の各実施例により利用可能な１つのタイプのコンピュータシステムの一例である。図示されない異なる構成の他のタイプのコンピュータシステムがまた、本発明の実施例により利用可能である。コンピュータシステム１００は、１以上のバス１０１及び／若しくはポイント・ツー・ポイントインターコネクション、若しくは情報を伝送するための他の内部通信ハードウェア及びソフトウェア、並びに情報を処理するためバス１０１若しくはポイント・ツー・ポイントインターコネクションに接続されるプロセッサ１０９を有してもよい。プロセッサ１０９は、シングルコア、マルチコア又はシステマティックマルチプロセッシングアーキテクチャを有してもよい。
【００１５】
プロセッサ１０９は、例えば、何れか適切なアーキテクチャを有する中央処理ユニット（ＣＰＵ）又はマルチプロセッサなどであってもよい。一実施例では、アーキテクチャは、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令セットの拡張であるストリーミングＳＩＭＤ拡張（ＳＳＥ）（２００７年４月に公表され、インテル（登録商標）ＳＳＥ４  Ｐｒｏｇｒａｍｍｉｎｇ  Ｒｅｆｅｒｅｎｃｅに記載されるようなＳＳＥ４．２又は他のＳＳＥ４命令セットなど）を含むかもしれない。ＳＳＥアーキテクチャは、複数の（４つなど）データポイントに対してパラレルにＰａｃｋｅｄ命令を実行するかもしれない。他の実施例では、ＳＳＥアーキテクチャに対するインテル（登録商標）Ａｄｖａｎｃｅｄ  Ｖｅｃｔｏｒ  Ｅｘｔｅｎｓｉｏｎ（ＡＶＸ）（２００８年３月に公表されたインテル（登録商標）Ａｄｖａｎｃｅｄ  Ｖｅｃｔｏｒ  Ｅｘｔｅｎｓｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｒｅｆｅｒｅｎｃｅに記載されるような）が、他の個数のデータポイント（８又は１６個のなどのデータポイント）に対してパラレルにＰａｃｋｅｄ命令を実行するのに利用されるかもしれない。プロセッサ１０９は、ＣＩＳＣ（Ｃｏｍｐｌｅｘ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｉｎｇ）アーキテクチャ又はＲＩＳＣ（Ｒｅｄｕｃｅｄ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｉｎｇ）アーキテクチャを有してもよい。
【００１６】
プロセッサ１０９は、実行ユニット１３０と、レジスタファイル１５０と、キャッシュ階層１６０と、デコーダ１６５と、内部バス１７０とを有してもよい。レジスタファイル１５０は、複数のアーキテクチャレジスタを含む単一のレジスタファイルを有してもよいし、又はそれぞれが複数のアーキテクチャレジスタを有する複数のレジスタファイルを有してもよい。他のレジスタが利用されてもよい。
【００１７】
コンピュータシステム１００は、プロセッサ１０９により実行される命令及び情報を格納するため、バス１０１に接続されるメインメモリ１０４にＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ  ＲＡＭ）又は他のダイナミックストレージ装置を含むかもしれない。メインメモリ１０４は、プロセッサ１０９による命令の実行中に一時的な変数又は他の中間情報を格納するのに利用されてもよい。コンピュータシステム１００は、プロセッサ１０９に対する静的情報及び命令を格納するため、バス１０１に接続されるＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１０６又は他の静的ストレージ装置を有してもよい。
【００１８】
磁気ディスク又は光ディスク及び対応するディスクドライブなどのデータストレージ装置１０７が、バス１０１に接続されてもよい。コンピュータシステム１００は、コンピュータシステム１００のユーザに情報を表示するため、バス１０１を介し表示装置１２１に接続されるかもしれない。表示装置１２１は、フレームバッファ、特殊なグラフィックスレンダリング装置、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）又はフラットパネルディスプレイを含みうるが、これに限定されるものでない。英数字と他のキーを含むキーボードなどの英数字入力装置１２２が、プロセッサ１０９に情報及びコマンド選択を通信するため、バス１０１に接続されてもよい。方向情報及びコマンド選択をプロセッサ１０９に通信し、表示装置１２１上のカーソルの動きを制御するためのマウス、トラックボール、ペン、タッチ画面又はカーソル方向キーを含むカーソルコントローラ１２３が含まれてもよい。コンピュータシステム１００は、音声記録再生装置１２５に接続可能である。音声記録は、例えば、マイクロフォンに接続されるオーディオデジタル装置などを用いて実現されてもよく、音声再生は、デジタル化された音声を再生するため、Ｄ／Ａ（Ｄｉｇｉｔａｌ  ｔｏ  Ａｎａｌｏｇ）変換手段に接続されるヘッドフォンやスピーカーなどを用いて実現されてもよいが、本発明はこれに限定されるものでない。
【００１９】
コンピュータシステム１００は、コンピュータネットワークのコンピュータサブシステムとなるコンピュータネットワークのターミナルとして機能しうるが、本発明はこれに限定されるものでない。コンピュータシステム１００はさらに、ビデオデジタル化装置１２６を有してもよい。ビデオデジタル化装置１２６は、コンピュータネットワークに接続される他のコンピュータシステムに送信可能なビデオ画像をキャプチャするのに利用可能である。
【００２０】
一実施例では、プロセッサ１０９は、カリフォルニア州サンタクララのインテルコーポレイションにより製造されているインテル（登録商標）ＣｏｒｅＴＭ２  Ｄｕｏプロセッサなどのマイクロプロセッサにより使用されるｘ８６及び／又はｘ８７命令セットと互換する命令セットをサポートしてもよい。一実施例では、プロセッサ１０９は、インテルコーポレイションにより規定されるようなＩｎｔｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＡ．ＴＭ．）にサポートされるすべての処理をサポートする。例えば、２００５年４月に公表されたＭｉｃｒｏｐｒｏｃｅｓｓｏｒ，ＩＡ−３２  Ｉｎｔｅｌ（登録商標）Ａｒｃｈｉｔｅｃｔｕｒｅ  Ｓｏｆｔｗａｒｅ  Ｄｅｖｅｌｏｐｅｒ‘ｓ  Ｍａｎｕａｌ（Ｖｏｌｕｍｅ  ３：Ｓｙｓｔｅｍ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｇｕｉｄｅ）を参照されたい。この結果、プロセッサ１０９は、他の処理に加えて既存のｘ８６及び／又はｘ８７処理をサポートしてもよい。本発明の各実施例は、他の命令セットを利用してもよいし、又はそれに搭載されてもよい。
【００２１】
実行ユニット１３０は、プロセッサ１０９により受け付けされた命令を実行するため利用されるかもしれない。汎用プロセッサにおいて実現可能な命令を認識するのに加えて、実行ユニット１３０は、Ｐａｃｋｅｄ  データフォーマットに対して処理を実行するため、Ｐａｃｋｅｄ命令セット１４０などのＳＩＭＤ、Ｐａｃｋｅｄ又は他の命令を認識するかもしれない。一実施例では、Ｐａｃｋｅｄ命令セット１４０は、Ｐａｃｋｅｄ加算演算、Ｐａｃｋｅｄ減算演算、Ｐａｃｋｅｄ乗算演算、Ｐａｃｋｅｄシフト演算、Ｐａｃｋｅｄ比較演算、乗算加算演算、乗算減算演算、集合計数演算及びＰａｃｋｅｄ論理演算セットなどのＰａｃｋｅｄ及び／若しくはスカラー演算若しくは浮動小数点命令をサポートする各命令を含みうる。一実施例のＰａｃｋｅｄデータ論理演算セットは、例えば、ＡＮＤＰＳ、ＯＲＰＳ、ＸＯＲＰＳ及びＡＮＤＮＰＳなどを含むかもしれないが、本発明はこれに限定されるものでない。一実施例のＰａｃｋｅｄ算術演算セットは、例えば、ＡＤＤＰＳ、ＳＵＢＰＳ、ＭＵＬＰＳ、ＤＩＶＰＳ、ＲＣＰＰＳ、ＳＱＲＴＰＳ、ＭＡＸＰＳ、ＭＩＮＰＳ及びＲＳＱＲＴＰＳなどを含むかもしれないが、本発明はこれに限定されるものでない。一実施例のＰａｃｋｅｄデータ移動演算セットは、例えば、Ｐａｃｋｅｄ  ＭＯＶＰＳ、ＭＯＶＡＰＳ、ＭＯＶＵＰＳ、ＭＯＶＬＰＳ、ＭＯＶＨＰＳ、ＭＯＶＬＨＰＳ及びＭＯＶＨＬＰＳなどを含むが、本発明はこれに限定されるものでない。Ｐａｃｋｅｄ命令セット１４０がこれらの命令を含む一実施例が説明されるが、他の実施例は、これらの命令のサブセット又はスーパーセットを含むかもしれない。
【００２２】
上記命令は、Ｐａｃｋｅｄデータを用いるマルチメディアアプリケーションにおいて利用されるアルゴリズムの多くにより要求される演算の実行を提供する。このため、これらのアルゴリズムは、ある時点における１つのデータ要素に対して１以上の演算を実行するため、Ｐａｃｋｅｄデータをアンパックすることを必要とせず、必要なデータをパック処理し、Ｐａｃｋｅｄデータに対して必要な演算を実行するため記述されるかもしれない。実行ユニット１３０は、例えば、内部バス１７０などを使用して、レジスタファイル１５０に接続されてもよい。ポイント・ツー・ポイントシステムなどの他のタイプのバス処理又はデータ伝送システムが、利用されてもよい。レジスタファイル１５０は、データを含む情報を格納するためのプロセッサ１０９上の格納エリアを表す。さらに、実行ユニット１３０は、キャッシュ階層１６０とデコーダ１６５とに接続されてもよい。キャッシュ階層１６０は、メインメモリ１０４などからのデータ及び制御信号をキャッシュするのに利用される。デコーダ１６５は、プロセッサ１０９により受け付けされた命令を制御信号及びマイクロコードエントリポイントに復号化するのに利用される。これらの制御信号及びマイクロコードエントリポイントに応答して、実行ユニット１３０は、適切な処理を実行する。例えば、加算命令が受け付けされた場合、デコーダ１６５は、実行ユニット１３０に要求される加算を実行させる。減算命令が受け付けされた場合、デコーダ１６５は、実行ユニット１３０に要求される減算を実行させる。このため、デコーダ１６５及び実行ユニット１３０による各種命令の実行はｉｆ／ｔｈｅｎステートメント系列により表されるが、一実施例の命令の実行は、これらのｉｆ／ｔｈｅｎステートメントの逐次的処理を必要としない。
【００２３】
レジスタファイル１５０は、制御及びステータス情報、スカラーデータ、整数データ、Ｐａｃｋｅｄ整数データ、Ｐａｃｋｅｄ浮動小数点データを含む情報を格納するため利用されるかもしれない。一実施例では、レジスタファイル１５０は、内部バス１７０に接続される、メモリレジスタ、制御及びステータスレジスタ、スカラー整数レジスタ、スカラー浮動小数点レジスタ、Ｐａｃｋｅｄシングル精度浮動小数点レジスタ、Ｐａｃｋｅｄ整数レジスタ及び命令ポインタレジスタを含むかもしれない。
【００２４】
一実施例では、スカラー整数レジスタは３２ビットレジスタであり、Ｐａｃｋｅｄシングル精度浮動小数点レジスタは１２８ビットレジスタであり、Ｐａｃｋｅｄ整数レジスタは６４ビットレジスタであるが、本発明はこれに限定されるものでない。ＳＳＥ命令セットは、例えば、ｘｍｍ０〜ｘｍｍ７として知られる８つの１２８ビットレジスタなどを利用してもよい。ｘｍｍ８〜ｘｍｍ１５として知られるさらなる８つの１２８ビットレジスタが、ＳＳＥ命令セットのため利用されてもよい。例えば、ｘｍｍ０はベクトルｂについて４つのエントリを保持し、ｘｍｍ１〜ｘｍｍ４はベクトルｘの４つのデータポイントのそれぞれについて４つのエントリを保持し、ｘｍｍ５〜ｘｍｍ８のそれぞれはマトリックスＡの４つの対応する係数項を保持するかもしれない。ＳＳＥ命令セットは、マトリックスＡの係数項を同時に乗算することによって、パラレルにベクトルｘの複数の（４つなど）データポイントを処理してもよい。例えば、８つのｘｍｍレジスタ（ｘｍｍ０〜ｘｍｍ７など）が利用されてもよく（３２ビットプラットフォーム上など）、及び／又は１６個のｘｍｍレジスタ（ｘｍｍ０〜ｘｍｍ１５など）が利用されてもよい（６４ビットプラットフォーム上など）。ＭＸＣＳＲなどのさらなる３２ビット制御／ステータスレジスタが利用されてもよい。各レジスタは、４つの３２ビットシングル精度浮動小数点数を一緒にパック処理するかもしれない。整数ＳＩＭＤ演算は、８つの６４ビットＭＭＸレジスタにより実行されてもよい。他の命令セット及びレジスタサイズが利用されてもよい。８つのデータポイントをパラレルに実行するための他の命令セット（ＳＳＥ  ＡＶＸ命令セットなど）が利用されてもよい。命令セットは、例えば、ｙｍｍ０〜ｙｍｍ１０及びＥＲＲ＿ＹＭＭなどを介し呼び出される１２個の２５６ビットレジスタなどを利用してもよい。より大きな（２５６ビットなど）のレジスタは、例えば、ｙｍｍ０がベクトルｂの８つのエントリを保持し、ｙｍｍ４〜ｙｍｍ７がベクトルｘの８つのデータポイントのそれぞれの８つのエントリを保持し、ｙｍｍ４〜ｙｍｍ７のそれぞれがマトリックスＡの８つの対応する係数項を保持することを可能にするかもしれない。例えば、１２個のｙｍｍレジスタ（ｙｍｍ０〜ｙｍｍ１０及びＥＲＲ＿ＹＭＭなど）が利用されてもよい。他のレジスタ、個数、サイズ及びタイプが利用されてもよい。
【００２５】
一実施例では、Ｐａｃｋｅｄ整数レジスタは、スカラー浮動小数点レジスタと同じメモリスペースにエイリアスされる。Ｐａｃｋｅｄ浮動小数点データに対して、個別のレジスタが使用される。レジスタファイル１５０のレジスタの使用では、プロセッサ１０９は、何れかの時点において、これらのレジスタをスタック参照浮動小数点レジスタ又は非スタック参照Ｐａｃｋｅｄ整数レジスタとして扱う。本実施例では、プロセッサ１０９がスタック参照浮動小数点レジスタ及び非スタック参照Ｐａｃｋｅｄデータレジスタとしてのレジスタ上の実行の間でスイッチすることを可能にするための機構が含まれる。他の実施例では、プロセッサ１０９は、非スタック参照浮動小数点及びＰａｃｋｅｄデータレジスタとしてレジスタ上で同時に実行してもよい。さらに、他の実施例では、同一のレジスタがスカラー整数データを格納するため利用されてもよい。
【００２６】
他の実施例は、異なるレジスタセットを含むかもしれない。例えば、他の実施例は、Ｐａｃｋｅｄ整数レジスタとスカラーデータレジスタのための別々のレジスタを含むかもしれない。他の実施例は、制御及びステータス情報を格納するための第１レジスタセットと、スカラー整数、Ｐａｃｋｅｄ整数及びＰａｃｋｅｄ浮動小数点データを格納可能な第２レジスタセットとを含むかもしれない。
【００２７】
さらに、特定タイプのプロセッサ及び命令セットアーキテクチャが説明されるが、本発明の実施例は、他のタイプのプロセッサ、アーキテクチャ及び命令セットと共に機能するかもしれない。
【００２８】
レジスタファイル１５０のレジスタは、異なる個数のレジスタと異なるサイズのレジスタを含むよう実現可能である。例えば、一実施例では、整数レジスタは３２ビットを格納するよう実現可能であり、他のレジスタは１２８ビットを格納するよう実現可能である。ここでは、１２８ビット全てが浮動小数点データを格納するのに利用され、６４ビットのみがＰａｃｋｅｄデータに対して使用される。他の実施例では、整数レジスタはそれぞれ３２又は６４ビットを含む。
【００２９】
本発明の各実施例は、プロセッサ１０９による１以上のＰａｃｋｅｄ命令セット１４０における命令を実行する実行ユニット１３０を有してもよい（例えば、４，８及び／又は１６個のデータポイントをパラレルに実行するためなど）。命令セット１４０は、ＬＳＳＬＥなどの１以上の方程式に対する解を求めるのに利用されるかもしれない。ＬＳＳＬＥに対する解は、例えば、出力ファイル、ストレージ装置、ストレージフォーマット又は表示装置のフレームレートに互換するよう入力ファイルのフレームレートを変更するためのフレームレート変換などに利用されてもよい。入力ファイルは、メインメモリ１０４、ＲＯＭ１０６、データストレージ１０７、音声記録再生装置１２５及び／又は入力装置１２２などの入力装置からバス１０１を介し受付及び／又は格納されてもよい。出力ファイルは、音声記録再生装置１２５又は表示装置１２１などの出力装置により利用又は配信されてもよい。
【００３０】
本発明の一実施例によるプロセッサパイプライン２００を概略的に示す図２が参照される。プロセッサパイプライン２００は、Ｕパイプ２０２とＶパイプ２０４を含むデュアルデータパイプラインを含むかもしれない。他の実施例では、プロセッサパイプライン２００は、１以上のパイプラインを有してもよい。ＳＩＭＤ命令を利用して、プロセッサパイプライン２００は、各データパイプラインを利用して、複数の（４，８及び／又は１６個など）データポイント（連立一次方程式のベクトル解の各成分など）をパラレルに処理するかもしれない。与えられた命令の復号化中（複数のデータポイントを処理するためなど）、次の２つの命令がチェックされ、可能である場合には、第１の命令がＵパイプ２０２により実行され、第２の命令がＶパイプ２０４により実行されるように、これらが発行される。２つの命令をペアにすることができない場合、次の命令はＵパイプ２０２に発行されてもよく、典型的には、Ｖパイプ２０４には命令が発行されない（又はその反対など）。命令がＵパイプ２０２とＶパイプ２０４において実行されると、それらの動作は、あたかも逐次的に実行される場合と同じになるかもしれない。プロセッサ１０９（図１）のマイクロアーキテクチャは、命令プリフェッチ２１０、命令フェッチ２１２、命令復号化、ペアリング、ディスパッチ２１４、アドレス生成２１６、オペランドリード及び実行２１８、ワイとバック２２０などの各ステージを含むかもしれない。命令復号化ロジックは、クロックサイクル毎に２つまでの命令のレートでこれらの命令を復号化、スケジューリング及び発行し、他の実施例では、異なるレートが使用されるかもしれない。
【００３１】
ＬＳＳＬＥは、例えば、マトリックス形式により表されてもよい（例えば、Ａｘ＝ｂなどによって（ここで、Ａはｎ×ｎ行列であり、ｂとｘはｎ×１ベクトルである）。ＬＳＳＬＥが離散化（ＰＤＥなどの）により生成されるとき、マトリックスＡの次元は使用される離散化ポイントの個数に依存するかもしれない。離散化ポイントの個数は、ａ）数値スキームの固有の精度、ｂ）要求される精度、及びｃ）ＬＳＳＬＥを解くのに利用される数値処理の収束に依存するかもしれない。
【００３２】
ＬＳＳＬＥを表すマトリックスＡは、典型的には、ＰＤＥの微分演算子の離散化によって、典型的には疎である（多数のゼロのエントリを有するなど）。例えば、ポワソン方程式
【００３３】
【数１】
0005026464.tif 000002
に適用される中心差分離散化機構は、行単位で４つの非ゼロエントリしか有さないマトリックスを生成するかもしれない。動き推定を記述するＰＤＥは、例えば、
【００３４】
【数２】
0005026464.tif 000003
であるかもしれない（ただし、ｕ及びｖはそれぞれｘ及びｙ方向の動きである）。動き推定ＰＤＥに適用される同じ離散化機構は、例えば、
【００３５】
【数３】
0005026464.tif 000004
を与えるかもしれない。ただし、Ｎ（ｉ）はｉの空間近傍である。この離散化を表すマトリックスＬＳＳＬＥは、行毎に６つの非ゼロエントリしか有しないかもしれない。
【００３６】
ＬＳＳＬＥの数値解を求めることは、Ａｘ＝ｂ（ただし、Ａはｎ×ｎマトリックスであり、ｂ及びｘはｎ×１ベクトルである）などの線形方程式を解くことを含む。この線形方程式は、因数分解機構及び繰り返し機構を含む各種機構によって解かれるかもしれない。しかしながら、ＬＳＳＬＥを解く際、因数分解機構は、典型的には、繰り返し機構よりかなり大きな計算労力と時間を要する。このため、繰り返し方法が、典型的には好まれる。因数分解機構及び／又は因数分解機構と繰り返し機構の組み合わせがまた、本発明の実施例によるＬＳＳＬＥを解くのに利用されてもよいことが理解されるかもしれない。
【００３７】
繰り返し機構は、線形方程式Ａｘ＝ｂを解くのに利用されてもよい。マトリックスＡのエントリは、ａｉｊ（１≦ｉ，ｊ≦ｎ）により表され、ｘ及びｂのエントリはｘｒ及びｂｒ（１≦ｒ≦ｎ）によりそれぞれ示される。マトリックスＡは、図１では、メインメモリ１０４、ＲＯＭ１０６及び／又はデータストレージ１０７などへのそれの効率的な格納のため符号化されるかもしれないが、他の何れに格納されてもよい。
【００３８】
“疎”及び“大きな”という用語により意図される非限定的な例を示すため、ｎ×ｎのマトリックスＡ（ｎは６５，５３６に等しい）により表されるＬＳＳＬＥにより定義されるフレームレート変換問題を考える。マトリックスＡは、４，２９４，９６７，２９６個のシングル精度（３２ビットなど）のエントリ（約１７，０００メガバイトなど）に対応する６５，５３６×６５，５３６のサイズを有してもよい。このようなマトリックスは、“大きい”ものとみなされるかもしれない。マトリックスＡは、（６５，５３６個などの）各行が少数の非ゼロエントリしか有さないとき、“疎”であるとみなされるかもしれない（例えば、動き推定ＰＤＥに対して６又は他の少数個の非ゼロエントリなど）。このため、効率的に符号化されるマトリックスＡは、例えば、３２７，６８０個の非ゼロエントリなどを有するかもしれない（例えば、約１．３メガバイトなど）。他の個数及びサイズが利用されてもよい。
【００３９】
プロセッサ１０９（図１）は、例えば、ｘｒ（０）により示されるエントリを有する解ｘに対する初期的な推定値ｘ（０）からスタートすることによる繰り返し機構を用いてＬＳＳＬＥを解いてもよい。連続する各繰り返し（ｋ＋１）において、新たな解推定値ｘ（ｋ＋１）が、前の解推定値ｘ（ｋ）から再帰的に求められてもよい。この繰り返しプロセスは、推定値の収束が観察されたときに終了されてもよい。例えば、（ｘ（ｋ＋１）−ｘ（ｋ））のＬ２ノルムなどの指標が所定の閾値より小さくなったとき、収束が観察されたとしてもよい。例えば、Ｌ２ノルムは、
【００４０】
【数４】
0005026464.tif 000005
として定義されるかもしれない。ただし、ｎはベクトルｘの長さである。プロセスを終了させる方法及び／又は収束の他の指標が使用されてもよい。
【００４１】
ＬＳＳＬＥを解くためのそのような１つの繰り返し機構は、ヤコビ（Ｊａｃｏｂｉ）法である。ヤコビ法では、解推定値ｘｉ（ｋ＋１）は、例えば、以下の式（１）などによって、
【００４２】
【数５】
0005026464.tif 000006
再帰的に定義されるかもしれない。
【００４３】
ヤコビ法では、ｎ×ｎのマトリックスＡが、新たなｎ×１の解推定値ベクトルｘ（ｋ＋１）を生成するため、ｎ×１の解推定値ベクトルｘ（ｋ）と乗算されるかもしれない。この乗算処理は、典型的には、新たな推定値と古い推定値との収束が観察されるまで、新たな各解推定値ベクトルにより繰り返される。例えば、所定の小さなε＞０に対して、Ｌ２＿ＮＯＲＭ（ｘ（ｋ＋１）−ｘ（ｋ））＜εになると、収束したとされてもよい。収束した解推定値ベクトルが、ＬＳＳＬＥに対する解ベクトルであるかもしれない。ヤコビ法を用いてＬＳＳＬＥを解くための計算コストは、ｉｔｅｒａｔｉｏｎｓ＊ｎ２（γ）であるかもしれない。ただし、ｉｔｅｒａｔｉｏｎｓは繰り返し回数であり、γはヤコビ法の乗算及び加算の計算コストである。ヤコビ法はＬＳＳＬＥを解くのに利用可能であるが、この方法は、典型的には、所望の精度（実質的に小さなε＞０などに対して）の収束を実現するため、比較的多数の繰り返しを要する。
【００４４】
Ｇａｕｓｓ−Ｓｅｉｄｅｌ（ＧＳ）法及びその変形やＳＯＲ（Ｓｕｃｃｅｓｓｉｖｅ  Ｏｖｅｒ  Ｒｅｌａｘａｔｉｏｎ）などの他の方法が、同じ精度によりヤコビ法と比較して相対的により少ない繰り返しによりＬＳＳＬＥを解くため開発された。
【００４５】
ＧＳ法は、推定値の収束が達成されるまで、ｎ×ｎのマトリックスＡとｎ×１の解推定値ベクトルｘ（ｋ）とを繰り返し乗算することによって、ヤコビ法のプロセスに部分的に従う。しかしながら、ＧＳ機構は、解推定値ベクトルの定義の仕方に関してヤコビ法と異なる。ＧＳ機構は、ベクトルの直近に計算されたエントリ又は座標値を用いて、解推定値ベクトルｘ（ｋ）を再帰的に定義する。例えば、ｘｉ（ｋ＋１）は、ｘｊ（ｋ＋１）（ｊ＝１，２，．．．，（ｉ−１））と、ｘｊ（ｋ）（ｊ＝ｉ，ｉ＋１，．．．，ｎ）に関して定義されるかもしれない。典型的には、この関係は、ヤコビ法と他の同様の方法と比較して収束レートを改善する。ＧＳ法は、典型的には、例えば、以下の式（２）
【００４６】
【数６】
0005026464.tif 000007
などによって推定値ｘｉ（ｋ＋１）を再帰的に定義する。マトリックスＡはほとんどがゼロのａｉｊの有した疎であるため、各和
【００４７】
【数７】
0005026464.tif 000008
は、典型的には、少数の項しか伴わない。
【００４８】
ヤコビ法と比較して、ＧＳ法とＳＯＲ法は、典型的には、解推定値の収束をスピードアップするが、ＧＳ法とＳＯＲ法は他の問題を引き起こすかもしれない。例えば、ＧＳ法とＳＯＲ法は、ｘの直近に計算されたエントリを用いて現在の解推定値を更新するが、このため、“連続的”と呼ばれるかもしれない。例えば、式（２）では、ｘｉ（ｋ＋１）は、同じ繰り返しにおいて計算されたｘの値に依存する（例えば、ｊ＜ｉの和の項などにおいて）。このため、ｘｉ（ｋ＋１）の値は、同じ繰り返し（ｋ＋１など）中に計算されるベクトルｘにおけるそれの“近傍エントリ（ｘｉ−１（ｋ＋１）など）に依存する。ＧＳ法におけるこのような依存性は、ベクトルｘの各成分のパラレルな計算を不可能にし、ＬＳＳＬＥを解くスピードを大きく制限する。例えば、ベクトルｘにおいてエントリ（ｘｉ（ｋ＋１）など）を生成するため、典型的には、ベクトルｘの前の項又は近傍の項（ｘｉ−１（ｋ＋１）など）の生成が完了する前、完了後又は完了に応答して、アプリケーションは待機する。例えば、ＧＳ法は、ｘの連続する項（ｘｉとｘｉ＋１など）に同時には適用されないかもしれない。
【００４９】
本発明の各実施例は、座標成分がベクトルにおいて配置される順序とは異なる順序によって、同一ベクトルの他のエントリ（現在の繰り返しｋにおいて計算されたものなど）によるｘの順序付けされた各座標成分又はエントリｘｉ（ｋ）を繰り返し又は再帰的に定義することを含むかもしれない。その他のエントリは、ベクトルの順序において“非近傍”エントリｘｉ（ｋ）であるかもしれない。このため、ｘの各エントリｘｉ（ｋ）の値は、座標成分がベクトルにおいて配置される順序と異なる順序により更新されてもよい。ＧＳ機構（式（２）などに定義される）によると、エントリｘｉ（ｋ）は、その他の非近傍エントリから独立している。このため、エントリｘｉ（ｋ）とそれの他の非近傍エントリは、パラレルに同時に更新される。従って、本発明の実施例によると、エントリの更新は（ＧＳ機構などを用いた）、ベクトルの連続的に順序付けされた又は近傍エントリの更新を待機することを要求しない。
【００５０】
本発明の各実施例は、ｘの各エントリに対して、当初の順序付けにおけるそれの初期的な近傍エントリが新たな順序付けにおける異なる非近傍位置に移動されるように、新たなベクトルｘ’を生成するため、ベクトルｘの各エントリの順序付けを再構成するための機構を提供する。このため、当初の連続するエントリ（ベクトルｘのｘｉ及びｘｉ＋１など）は、ベクトルｘ’において別々にされる（非近傍位置に現在あるなど）。ＧＳ機構では（式（２）などによる）、ベクトルの各座標エントリを解くことは、当初の近傍のエントリを非近傍位置に移動させることによって、それの近傍エントリに依存するため、新たなベクトルｘ’における各エントリはもはや現在の近傍に依存しない。このため、ベクトルｘ’のエントリ（ｘ’ｉ（ｋ＋１）など）や新たな近傍の項（ｘ’ｉ−１（ｋ＋１）など）など、新たなベクトルの２以上の近傍エントリのそれぞれは、再帰的に定義される移動された各非近傍エントリを用いて、それの再帰的定義を更新することによって、同時に又はパラレルに解かれるかもしれない。
【００５１】
例えば、従来のＧＳ法は（式（２）などによる）、ベクトルｘのエントリ（ｘ４など）に適用されてもよい。この結果は、典型的には、ｘの直近に計算されたエントリ（ｘ３など）に依存し、このため、前の近傍項の処理を待機しなければならない。再配置アルゴリズムは、初期的に近傍のエントリ（ｘ３，ｘ４，ｘ５など）を分離するのに利用されてもよい。一実施例では、ｘのエントリ（ｘ４など）に初期的に近傍にあるエントリ（ｘ３及びｘ４など）が、ｘ’における非近傍エントリとなるよう再配置される。新たなベクトルｘ’におけるエントリ（ｘ４など）は、エントリ（ｘ４など）が依存しない（式（２）などにより）新たな近傍値（再配置されたベクトルｘ’のシーケンスｘ１，ｘ４，ｘ８におけるｘ１及びｘ８など）を有してもよい。このため、ＧＳ機構（式（２）などにより定義された）が、ｘ’の新たな近傍エントリ（ｘ１，ｘ４，ｘ８など）に同時に適用されてもよい。ｘ’の再配置された各近傍エントリ（ｘ１，ｘ４，ｘ８など）は、ｘ’の直近に計算されたエントリ（ｘ０，ｘ３，ｘ７など）に依存して解かれるかもしれない（式（２）などにより）。エントリの再配置から、ｘ’の直近に計算されたエントリ（ｘ０，ｘ３，ｘ７など）は、もはやそれに依存したエントリ（ｘ１，ｘ４，ｘ８など）の近傍とはならない。従って、近傍エントリ（ｘ１，ｘ４，ｘ８など）のそれぞれを解くため、解機構は他の近傍エントリの解を待機する必要はない。
【００５２】
一実施例では（図３などに示される）、ベクトルｘは、マッピングマトリックスと呼ばれるかもしれない対応する第１グリッド又はマトリックス（図３のマトリックス３１０など）に変換される。第１グリッド又はマトリックスの各成分は、新たなベクトルｘ’に対応する第２グリッド又はマトリックス（図３のマトリックス３４０など）に再構成される。この再構成は、第１グリッド又はマトリックスの各エントリに対して、当初の順序付けにおけるそれの初期的な近傍エントリが異なる非近傍位置に移動されるように、実行されてもよい。
【００５３】
一実施例では、ベクトルの各成分の処理の順序は、ベクトルのマッピングマトリックスへのマッピングと、マッピングマトリックスの近傍成分が再構成されたマッピングマトリックスにおいて近傍とならない再構成される、マッピングマトリックスの再構成されたマッピングマトリックスへの再構成とに対応する方法と異なるかもしれない。
【００５４】
第１順序による各成分を有するベクトルｘ’と、第２順序による各成分を有するベクトルｘ’とに対して、ベクトルｘ’の連続する各成分に対する処理は第２順序によるベクトルｘの各成分に対する処理に等しいかもしれないということは、当業者に理解されるかもしれない。ベクトルｘは、近傍成分を使用又は参照することなく再順序付けされてもよい。例えば、各エントリの再構成は、エントリへの自明でないマップ又はリファレンスを定義することに等しいかもしれない。例えば、不連続な又は交互の順序によるベクトルエントリの処理又は計算は、再構成に等しいかもしれない。例えば、これらのエントリは、移動又は再構成される必要はない。このため、一部の実施例では、ベクトルの各成分は、これらの成分がベクトルにおいて現れる順序以外の順序によって、このベクトル順序の順序通りには処理されないかもしれない。成分のいくつかのグループが、同時に処理されてもよい。
【００５５】
当初の順序を有するベクトルｘから新たな順序を有するベクトルｘ’へのエントリの再構成を概略的に示す図３が参照される。データ構造又はマトリックス３１０は、当初の順序を有するベクトルｘを表す。例えば、ベクトルｘのエントリは、行毎（図示されるような）、列毎又は他の順序を用いて、マトリックス３１０の座標を充填するかもしれない。マトリックス３１０のエントリ３００（ベクトルｘのｘ１０又は１０番目のエントリなど）は、例えば、４つの向き合ったエントリ３２０（隣接し、エントリ３００と同じ行の又は列などにおける）と、４つの対角エントリ３３０（エントリ３００と隣接するが異なる行及び列などにおける）とを含む８つの近傍エントリを有してもよい。あるいは、向かい合う対角のエントリ３２０と３３０以外のエントリは、“近傍”とみなされてもよい。
【００５６】
データ構造又はマトリックス３４０は、再構成された順序を有するベクトルｘ’を表す又は対応するかもしれない。再構成された順序によると、マトリックス３４０のエントリ３００（マトリックス３１０の１０番目のエントリなどに対応する）は、当初の近傍エントリと分けられるかもしれない。例えば、マトリックス３１０の当初の順序におけるエントリ（６，９，１１及び１４番目及び５，７，１３及び１５番目など）は、マトリックス３４０の新たな順序におけるエントリ３００の非近傍ではないかもしれない。当初の順序の近傍エントリは、再構成された順序におけるエントリ３００から移動又はある距離だけ離間されてもよい（再構成式（３）を参照してここに記載されるパラメータＳなどにより定義される）。マトリックス３４０のエントリ３００は、向かい合うエントリ３２０及び／又は対角エントリ３３０と異なる向かい合うエントリ３５０及び対角エントリ３６０などの新たな近傍エントリを有してもよい。
【００５７】
例えば、各エントリ３００がそれの当初の近傍エントリ（向かい合うエントリ３２０及び／又は対角エントリ３３０など）から分離されるように、ベクトルがマトリックス３４０において再構成されると、ＧＳ機構が、再構成されたベクトルｘ’の新たな近傍エントリ（例えば、向かい合うエントリ３２０及び／又は対角エントリ３３０など）にパラレルに適用されてもよい。例えば、方程式Ａｘ’＝ｂのＬＳＳＬＥを解くため、ｎ×ｎのマトリックスＡが再構成されたｎ×１のベクトルｘ’（又はベクトルｘ’を表すｎ×ｍのマトリックス３４０など）と乗算されてもよい。このＬＳＳＬＥを解くための計算ステップは、ヤコビ法のステップと同様であるかもしれないが（マトリックス乗算によるベクトルの複数のエントリの同時処理など）、これらの解の収束レートはＧＳ法にかかるものと同様である（例えば、直近の計算に基づく解の値など）。このため、ヤコビ法とＧＳ法のそれぞれの効果が実現されるかもしれない。他のベクトル、他のマトリックス又は他のタイプのデータ構造が利用されてもよい。他の再順序付けスキームが利用されてもよい。
【００５８】
各エントリは他の個数又は定義の近傍エントリを有してもよいことが理解されるであろう。例えば、マトリックス３１０と３４０の対角上のコーナーに沿って配置されたエントリは、２つの向かい合うエントリ３２０と、１つの対角エントリ３３０とを有してもよい。マトリックス３１０と３４０のエッジ（及びコーナーでない）に沿って配置されたエントリは、３つの向かい合うエントリ３２０と、２つの対角エントリ３３０とを有してもよい。他の実施例では、ベクトルのマトリックス表現は使用される必要はない。その代わりに、当初のベクトルｘと再構成されたベクトルｘ’自体が使用され、マトリックス３１０と３４０は１次元とみなされるかもしれない（ベクトルｘ及びｘ’に等価など）。この例では、１×ｎのベクトルに対して、ベクトルのエッジのエントリ（ｘ０，ｘｎ−１など）は１つの近傍エントリを有し、他のすべてのエントリ（ｘ１，ｘ２など）は２つの近傍エントリを有するかもしれない。
【００５９】
エントリの再構成又は移動が説明されたが、本発明の実施例はエントリの微分の再構成又は移動を含むことが理解されるかもしれない。例えば、再構成されたベクトルを表すマトリックスは、低減された行階層形式とされ、正規化され、上方三角形、下方三角形、対角化及び又は他の変更に分離されるかもしれない。再構成又は移動されたエントリは、当初のエントリから導かれた項であるかもしれない（複製でないなど）。
【００６０】
図３において、当初の順序から再構成された順序へのベクトルのエントリの移動が、矢印により示される。この移動は、数学的な抽象化であり、マッピング、アルゴリズム又は方程式（ここに記載される再構成式（３）など）により定義されてもよいということが留意されてもよい。他の実施例では、エントリの再構成は、各エントリの他のマッピング又は参照を定義することに等しいかもしれない。例えば、各エントリは、それ自体は移動又は再構成される必要はない。例えば、ベクトルのエントリの処理又は計算の順序の決定は、再構成と等しいかもしれない。
【００６１】
各成分が処理される順序は、プロセッサ１０９（図１）により決定され、実行ユニット１３０（図１）により実行され、及び／又はコマンド若しくは命令セットとして（キャッシュ階層１６０、メインメモリ１０４、ＲＯＭ１０６、データストレージ装置又は図１のこれらの組み合わせなどに）格納されてもよい。あるいは、ベクトルの各成分の再順序付け又は各成分が処理される順序は、実行のため格納及び抽出される命令セットに固有のものであってもよい。例えば、各成分がベクトルにおいて配置される順序に当該順序が対応していない場合、あるプロセスは、まず特定のエントリ（エントリのグループなど）に対して実行され、その後他のものに実行されるよう予め設定されてもよい。例えば、互いに不連続な複数のエントリの第１セットが第１命令にパックされ、その後、互いに不連続な複数（４又は８など）のエントリの第２セットが第２命令にパックされるなどしてもよい。
【００６２】
アルゴリズムは、新たなベクトルｘ’を形成するため、それのエントリを再構成するのにベクトルｘに適用されるかもしれない。例えば、このような１つのアルゴリズムは、以下のように進行するかもしれない（例えば、ＳＳＥ変形に示されるなど）。ベクトルｘは、Ｒ個の行とＣ個の列とを有するマトリックス３１０として格納されてもよい。サイズＲ＊ＣのベクトルＸをエントリｘ’（ｊ）（ただし、０≦ｊ≦Ｒ＊Ｃ−１）を有する新たな又は再構成されたベクトルｘ’に再構成するための再構成式は、例えば、
【００６３】
【数８】
0005026464.tif 000009
であるかもしれない。パラメータＳは、当初のベクトルｘのエントリｘ（ｊ）とｘ（ｊ＋１）との間の距離（ｘ’などにおける）であってもよい。パラメータＳの選択は、プロセッサ１０９（図１）（ＳＩＭＤなど）のパイプライン効率及びスループットに影響を与えるかもしれず、これらの特性を最適化するよう選択されるかもしれない。例えば、Ｓのパラメータ値は８であってもよい。例えば、十分大きなマトリックス３１０に対して、４のパラメータＳの値は、フルスループットのためシステム１００（図１）のパイプラインを充填するのに十分であるかもしれない。他の値が使用されてもよい。
【００６４】
ベクトルのマトリックス表現は使用される必要はないことが当業者に理解されるかもしれない。代わりに、ベクトル自体が使用されてもよい。
【００６５】
当初の順序を有するベクトルｘを表すマトリックス４００と、新たな順序を有するベクトルｘ’を表すマトリックス４１０とをそれぞれ示す図４Ａ及び４Ｂが参照される。このエントリの再構成は、ここに記載される再構成式に従って実行されてもよい。本例では、パラメータＳは３である。
【００６６】
新たなベクトルｘ’における各エントリを再構成することによって、各エントリは、それから独立した近傍エントリを有してもよく、これらとパラレルに処理されてもよい。一実施例では、エントリｘｉに対して、ベクトルｘの当初の近傍にあるエントリｘｉと、再構成されたベクトルｘ’の非近傍にあるエントリｘｉの個数は、エントリｘｉとパラレルに処理可能なエントリの個数である（ＧＳ機構などを用いて）。
【００６７】
一実施例では、パラレル処理アルゴリズム及び／又はハードウェアは、パラレルに近傍エントリを処理するのに利用されてもよい。例えば、プロセッサ１０９（図１）は、例えば、ＳＩＭＤ演算などを利用して、再構成されたベクトルｘ’の２以上の近傍エントリをパラレルに処理してもよい。
【００６８】
ｎ×ｎのマトリックスＡと再構成されたｎ×１のベクトルｘ’とを乗算することによってＡｘ＝ｂにより定義されるＬＳＳＬＥを解くため、パラレル処理アルゴリズムが利用されてもよい。例えば、一実施例は、４つのデータポイントをパラレルに実行するためＳＳＥ命令セット１４０（図１）を使用し、他の実施例は、８つのデータポイントをパラレルに実行するためＡＶＸ命令セット１４０（図１）を使用してもよい。他の適切なＰａｃｋｅｄ  ＳＩＭＤ又はパラレル処理命令セット若しくは方法が利用されてもよい。例えば、１６のデータポイントをパラレルに実行するための命令セット１４０（図１）が使用されてもよい。一実施例では、ベクトルｘ’は、各エントリについてｘの少なくとも４つの当初の近傍エントリが４つの独立したデータポイントをパラレルに実行するため、ｘ’において非近傍となるように再構成されてもよい。他の実施例では、ベクトルｘ’は、各エントリについて、ｘの少なくとも８つの当初の近傍エントリが、８つの独立したデータポイントをパラレルに実行するためｘ’における非近傍となるように再構成されるかもしれない。
【００６９】
各実施例が、擬似コードを用いて説明される。他のプログラミングコード、ステップ、順序若しくはステップ、プログラミング言語、命令セットのタイプ及び／又は非近傍エントリの最小数が使用されてもよい。
【００７０】
以下の擬似コードは、複数の（４つなど）近傍値を用いることによって、再構成されたベクトルｘ’の複数の（４つなど）データポイントのそれぞれ（ｘｍｍ１〜ｘｍｍ４に保持される４×４＝１６のエントリなど）をパラレルに処理するため、ＳＳＥ命令を用いた実施例を説明する。ベクトルｘ’は、各エントリ（ｘｍｍ１〜ｘｍｍ４に保持されるデータポイントなど）の複数の（４つなど）近傍値が互いに独立した順序を有してもよい。“カーネル”となるＫＥＲＮＥＬ−ＳＳＥは、ベクトルｘ’の複数の（４つなど）独立したエントリのパラレル処理を記述する。このカーネルは、例えば、Ａｘ’＝ｂの式などに従って、“マトリックス×ベクトル”の乗算を実行するため、ｎ／４回呼び出されるかもしれない。データポイント（ｘｍｍ５〜ｘｍｍ８に保持される４×４＝１６のエントリなど）に対応するマトリックスＡの係数項が使用されてもよい。このカーネルは、ポワソン方程式を解くのに使用されてもよい（マトリックスの各行が４つの非ゼロエントリを有する可能性がある場合など）。他の実施例では、４個以外のエントリがパラレルに処理されてもよい。
【００７１】
擬似コードは、例えば、以下のように進められるかもしれない。
【００７２】
【表１】
0005026464.tif 000010
もちろん、これらの命令は単なる具体例として与えられている。他の命令の具体例が本発明の実施例により使用されてもよい。ＫＥＲＮＥＬ−ＳＳＥがｎ／４回呼び出された後、ベクトルｘ’のすべてのエントリが現在の繰り返しに対して計算されており、ＥＲＲ＿ＸＭＭは、前の繰り返しからの差分のＬ２ノルムを保持している。Ｌ２ノルムの値が予め計算された値又は閾値より小さい場合、当該処理は中止される。直近の繰り返しにおいて計算されたｘ’の値が、最終結果として使用されてもよい。あるいは、ｘ’の直近の繰り返しの値に対応するｘの値が（反転された再構成式を適用することによって、ｘ’のｘへの“非再構成”又は逆マッピングなどによって決定される）、最終結果として使用されてもよい。
【００７３】
ベクトルの再順序付けは、他のステップ、プロセス及び／又は機構を用いて方程式が解かれるシステムにおいて使用されてもよい。
【００７４】
一実施例の各繰り返し又はＫＥＲＮＥＬ−ＳＳＥの計算コストは、例えば、１０のロード、１つのストア、５つのＭＵＬＰＳ、６つのＡＤＤＰＳなどのようにまとめられるかもしれない。
【００７５】
同様のカーネルが、動き推定式を解くのに利用されてもよいが、典型的には、ベクトルの８つのエントリをパラレルに処理する必要がある（例えば、“スムースな品質のビデオ”を生成するのに十分な速さの解を求めるためなど）。対応する動き推定カーネルを実行するための計算コストは（例えば、ベクトルの同数のエントリなどに対して）、１１のロード、１つのストア、６つのＭＵＬＰＳ、７つのＡＤＤＰＳなどのようにまとめられるかもしれない。
【００７６】
以下の擬似コードは、複数の（８つなど）近傍値を用いることによって再構成されたベクトルの複数の（８つなど）データポイントのそれぞれ（ｙｍｍ１〜ｙｍｍ４に保持される８×８＝６４のエントリなど）をパラレルに処理するため、（ＡＶＸなどの）命令を用いた実施例を記述する。ベクトルｘ’は、各エントリの複数の（８つなど）近傍値（ｙｍｍ１〜ｙｍｍ４に保持されるデータポイントなど）が、互いに独立している順序を有してもよい。“カーネル”であるＫＥＲＮＥＬ−ＡＶＸは、ベクトルｘ’の複数の（８つなど）の独立したエントリのパラレル処理を記述するかもしれない。このカーネルは、例えば、式Ａｘ’＝ｂなどに従って、“マトリックス×ベクトル”の乗算を実行するため、ｎ＝８回呼び出されるかもしれない。データポイント（ｙｍｍ５〜ｙｍｍ８に保持される８×８＝６４のエントリなど）に対応するマトリックスＡの係数項が、使用されてもよい。
【００７７】
擬似コードは、例えば、以下のように進められるかもしれない。
【００７８】
【表２】
0005026464.tif 000011
ＫＥＲＮＥＬ−ＡＶＸがｎ／８回呼び出された後、ベクトルｘ’のすべてのエントリが現在の繰り返しに対して計算されてもよく、ｘｍｍ９が前の繰り返しからの差分のＬ２ノルムを保持するかもしれない。Ｌ２ノルムの値が予め計算された値又は閾値より小さい場合、当該処理は中止され、直近の繰り返しで計算されたｘ’の値（又はそれに対応するｘの値など）が、最終結果として使用されてもよい。
【００７９】
一実施例の各繰り返し又はＫＥＲＮＥＬ−ＡＶＸの計算コストは、例えば、１０のロードと、１つのストアと、５つのＭＵＬＰＳと、６つのＡＤＤＰＳとなどのようにまとめられるかもしれない。
【００８０】
ＳＳＥ命令セット（図１）（４つのデータポイントのパラレル処理など）の代わりに、８つのデータポイントをパラレルに処理するために命令セット１４０（図１）を用いることによって、プロセッサ１０９（図１）は、同数の命令（及び遅延など）を用いて約２倍のデータを処理するかもしれない。
【００８１】
本発明の各実施例は、フレームレートを変換するための動きを推定するのにＬＳＳＬＥを解くために使用されてもよい。例えば、あるリフレッシュレート（６０ｆｐｓ（ｆｒａｍｅｓ  ｐｅｒ  ｓｅｃｏｎｄ）など）のモニタ又はスクリーンに当初のレート（２４ｆｐｓなど）によりビデオファイルを再生又は出力するビデオプレーヤー又はコンピュータを考える。同じ経過時間内に、装置が第１レートにより出力し、スクリーンが第２レートにより出力するように、上記リフレッシュレートにより再生するファイルを変換するため、フレーム変換アプリケーション（動き推定手段など）がさらなるｆｐｓ（４８ｆｐｓなど）を生成するようにしてもよい。例えば、１秒間の各期間に対して、２４のフレームが本発明の実施例による処理に入力され、６０フレームが出力される。例えば、新たなフレームの一部が古いフレームのコピーであるため、６０未満のさらなるｆｐｓが生成されるかもしれない。例えば、各フレームがｎ２のピクセル（ただし、ｎ＝２５６）を有する場合、アプリケーションは、毎秒平均して４８のＬＳＳＬＥに対する解を生成するかもしれない。一実施例では、ＬＳＳＬＥはマトリックス形式として構成されるかもしれない（Ａｘ＝ｂなど）。
【００８２】
従来のＧＳ機構では、ＬＳＳＬＥの各解は、一回に又は順々に１つのエントリについて、マトリックスＡとベクトルｘの各エントリとを乗算することによって生成されるかもしれない。本発明の各実施例は、マトリックスＡとベクトルｘ’の２以上の（例えば、独立した）エントリをパラレルに又は同時に乗算することによって、ＬＳＳＬＥの各解を生成するかもしれない。
【００８３】
各ＬＳＳＬＥの解は、解（ｘ又はｘ’など）に対する収束が達成されるまで生成されるかもしれない。たとえ名、ＧＳ機構の１０回以内の繰り返しで収束が達成される場合、アプリケーションは、１０回の“マトリックス×ベクトル”の乗算を実行し、これは、１０＊６ｎ２＝３９３２１６０の乗算と、１０＊４ｎ２＝２６２１４４０の加算とを毎秒要する（例えば、マトリックスＡが６つの非ゼロエントリを有し、各フレームにｎ２＝２５６２ピクセルが存在する場合など）。フレーム変換アプリケーションは、例えば、マトリックスＳを用意するため、さらなる計算コストを有するかもしれない（例えば、各マトリックスを対角成分により除することなどにより）。本発明の各実施例によると、複数の（４又は８など）データポイントをパラレルに解くことによって、ＬＳＳＬＥに対する解が従来の機構より迅速に生成されるかもしれない。本発明の各実施例に従って動作するプレーヤーは、他の又は異なる効果が実現されるかもしれないが、従来の方法より“スムース”なビデオを再生するかもしれない。
【００８４】
本発明の各実施例は、当該分野において知られるような、“レッド・ブラック”ＧＳ法、“ジグザグスキャニング”法、“ゼブララインリラクゼーション”法など、ＬＳＳＬＥを解くための他の従来の機構より効果的であるかもしれない。例えば、レッド・ブラック法は、典型的には、標準的なＧＳ法より２〜３倍の繰り返しを使用する。さらに、レッド・ブラック法は、典型的には、各繰り返し前後においてパック及び／又はアンパック処理を実行し、このため、光フロー又はマルチグリッドフレームワークに容易には統合できない。例えば、ジグザグスキャニング法は、レッド・ブラック法と同様に、典型的には、各繰り返し前後においてパック及び／又はアンパック処理を実行し、このため、大きなオーバヘッドを伴い、実現するのが困難であるかもしれない。ジグザグスキャニング法は、典型的には、マルチスケールフレームワークに適していない。例えば、ゼブララインリラクゼーション法は、レッド・ブラック法と同様に、典型的には、ＧＳ法より２〜３倍の繰り返しを使用する。
【００８５】
他方、本発明の各実施例は、ＧＳ法と同数の繰り返しを使用し、このため、上述した従来の方法の１／２の繰り返ししか使用しないかもしれない。本発明の各実施例は、例えば、各繰り返し前後において、パック及び／又はアンパック処理を実現する必要はない。このため、本発明の各実施例は、光フロー、マルチグリッド又はマルチスケールフレームワークに容易に統合されるかもしれない。本発明の各実施例は、はるかに少ない前処理及び／又は後処理の労力又はコスト（ジグザグスキャニング法などと比較して）しか使用しないかもしれない。例えば、本発明の各実施例は、マルチスケール及び／又はマルチグリッドフレームワークに対して１つの前処理ステップしか使用しないかもしれない。４又は８つのデータポイントをパラレルに処理するための命令セットを用いた本発明の各実施例は、標準的なＧＳ機構より、例えば、３．５及び７倍高速に方程式に対する解を提供するかもしれない。
【００８６】
他の又は異なる効果が実現されるかもしれない。
【００８７】
ヤコビ機構とＧＳ機構がここでは説明されたが、本発明の各実施例は、何れかの繰り返し機構により利用されてもよい。繰り返し機構は、初期的な推測及び／又は推定から始めて、解への連続的な近似を求めることによって問題（方程式又は連立方程式など）を解く機構である。例えば、ニュートン法、不動点法、ここに記載されたヤコビ機構若しくはＧＳ機構又はこれらの変形などの定常的繰り返し法、Ｋｒｙｌｏｖ部分空間法、共役勾配法（ＣＧ）、一般化最小剰余法（ＧＭＲＥＳ）、双共役勾配法（ＢｉＣＧ）などがあげられる。他の機構が使用されてもよい。
【００８８】
本発明の一実施例による方法のフローチャートである図５が参照される。本方法の各実施例が、図１の計算システム１００又は他の適切なシステムなどにより使用又は実現されてもよい。
【００８９】
処理５００において、システム（図１のシステム１００など）は、出力装置（図１の表示装置１２１など）にビデオファイルを出力するため、異なるフレームレートの入力装置（図１の入力装置１２２など）から、あるフレームレートを有するビデオ入力ファイルを受け付けるかもしれない。
【００９０】
処理５０５において、実行ユニット（図１の実行ユニット１３０など）は、方程式Ａｘ＝ｂにより規定される連立一次方程式（ＬＳＳＬＥなど）を解くことを開始するかもしれない。連立一次方程式は、入力フレームレートから出力フレームレートにビデオファイルを変換するため、中間フレームを規定するかもしれない。
【００９１】
処理５１０において、プロセッサ（図１のプロセッサ１０９など）は、連立一次方程式の係数を表すマトリックスＡと、連立一次方程式の解の最初の推定値を表すベクトルｘと、連立一次方程式のスカラー値を表すベクトルｂとを生成するかもしれない。ベクトルｘは、ある順序で構成された複数の成分（ｘ１，ｘ２，ｘ３，ｘ４，．．．など）を含むかもしれない。
【００９２】
処理５１５において、プロセッサは、ベクトルｘの各成分がベクトルにおいて構成される順序と異なる順序（ｘ１，ｘ９，ｘ１７，ｘ２５，．．．など）により乗算されるように、マトリックスＡとベクトルｘとを乗算するようにしてもよい。乗算される連続する各エントリは、近傍成分とは独立又は分離される。例えば、ｘ１は、ＧＳ法によりｘ９，ｘ１７，ｘ２５から独立する。このため、ベクトルの複数の独立した成分はパラレルに乗算されるかもしれない。一実施例では、プロセッサは、ＳＩＭＤ命令を用いて複数の連続する成分をパラレルに乗算するかもしれない。
【００９３】
一実施例では、プロセッサは、異なる順序（ｘ１，ｘ９，ｘ１７，ｘ２５，．．．など）を生成するため、各成分がベクトルにおいて構成される順序を実際に再構成するかもしれない。一実施例では、ベクトルの各成分は、マトリックス形式により再構成されるかもしれない（図３のマトリックス３１０から３４０など）。他の実施例では、プロセッサは、単にベクトルの成分を順序に従わずに計算するかもしれない。
【００９４】
処理５２０において、プロセッサは、連立一次方程式に対する解の第２のベクトル推定値を生成するかもしれない。ここで、第２のベクトル推定値は、処理５１５における乗算の積である。
【００９５】
処理５２５において、プロセッサは、第１ベクトル推定値と第２ベクトル推定値との差分を決定又は評価するかもしれない。第１及び第２ベクトル推定値が所定量未満しか異なっていないとき、処理５３０に移行する。そうでない場合、処理５１５に移行して、第１ベクトル推定値が第２ベクトル推定値に置換される。
【００９６】
処理５３０において、プロセッサは、ＬＳＳＬＥに対する解を設定するかもしれない。連立一次方程式に対する解は、第２ベクトル推定値に設定されてもよい。あるいは、連立一次方程式に対する解は、第１ベクトル推定値に設定されてもよい。あるいは、連立一次方程式に対する解は、第１及び第２ベクトル推定値の平均値に設定されてもよい。
【００９７】
処理５３５において、プロセッサは、ビデオファイルの少なくともセグメントを入力フレームレートから出力フレームレートに変換するため、ＬＳＳＬＥに対する解を用いて補間されたフレームを生成してもよい。一実施例では、既知のフレームの各ペアの間で補間された各フレームは、別のＬＳＳＬＥにより記述されてもよい。他の実施例では、補間された複数のフレームは同一のＬＳＳＬＥにより記述されてもよい。補間された各フレームがそれを表すＬＳＳＬＥを用いて生成されるまで、処理５０５〜５３５が繰り返されてもよい。補間された各フレームがビデオファイルの少なくともセグメントを入力フレームレートから出力フレームレートに変換するのに生成されると、処理５４０に移行する。
【００９８】
処理５４０において、出力装置（モニタなどの図１の表示装置１２１など）は、適切な出力フレームレートによりビデオファイルを出力するかもしれない。
【００９９】
処理５４５において、メモリユニット（メインメモリ１０４、ＲＯＭ１０６、図１のＤＲＡＭなどのデータストレージ装置１０７など）が、出力フレームレートによりビデオファイルを格納してもよい。メモリユニットは、マトリックスＡとベクトルｘとを乗算した結果（処理５１５などにおける）を格納してもよい。
【０１００】
他の処理又は処理系列が使用されてもよい。
【０１０１】
本発明の各実施例は、例えば、メモリ、ディスクドライブ、ＵＳＢフラッシュメモリなど、プロセッサ又はコントローラによる実行時に、ここに開示された方法を実行する命令を含む又は格納するコンピュータ若しくはプロセッサ可読媒体、コンピュータ若しくはプロセッサ記憶媒体などの物品を有してもよい。
【０１０２】
ビデオ解釈のため、方程式の各解法を用いた各実施例が説明された。しかしながら、他の実施例は、電気エンジニアリング、流体力学、他のコンピュータビジョン／グラフィックスシステムなどの他の分野において、光フロー推定、超解像度及び画像ノイズ低減などの解法を利用してもよい。
【０１０３】
本発明が限られた個数の実施例に関して説明されたが、本発明の多数の変形、改良及び他の適用が可能であることが理解されるであろう。本発明の各実施例は、ここでの処理を実行するための他の装置を含むかもしれない。このような装置は、記載された各要素を一体化してもよいし、又は同一の目的を実行する他のコンポーネントを有してもよい。添付した請求項は、本発明の真の趣旨の範囲内にあるこのようなすべての改良及び変更をカバーすることを意図していることは、当業者に理解されるであろう。
【符号の説明】
【０１０４】
１００  コンピュータシステム
１０１  バス
１０９  プロセッサ
１２１  表示装置
１２２  入力装置
１３０  実行ユニット
１４０  Ｐａｃｋｅｄ命令セット
１５０  レジスタファイル
１６０  キャッシュ階層
１６５  デコーダ
１７０  内部バス
【図１】
0005026464.tif 000012
【図２】
0005026464.tif 000013
【図３】
0005026464.tif 000014
【図４】
0005026464.tif 000015
【図５】
0005026464.tif 000016