"運動行列を用いて映像シーケンスのピクチャを符号化するための映像エンコーダを備え、前記運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを対応するデコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、装置。前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、請求項1に記載の装置。前記映像エンコーダは、埋め込み行列に前記運動行列を埋め込むための埋め込みデバイスと、前記埋め込み行列をサンプリングして前記埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、前記サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、前記量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを備える、請求項1に記載の装置。前記埋め込み行列は、前記運動行列を乗じた2つの行列を用いて決定され、前記2つの行列は、前記埋め込み行列のランダムな固有ベクトルの閾値の量を与えるように選択される、請求項3に記載の装置。前記サンプルのサブセットは、前記埋め込み行列からランダムに選択される、請求項3に記載の装置。前記埋め込み行列からの前記サンプルのサブセットのサンプルが前記映像エンコーダおよび対応する映像デコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が前記映像エンコーダおよび前記対応する映像デコーダによって使用される、請求項5に記載の装置。前記サンプラは、前記サンプルのサブセットのサンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の部分を破棄する、請求項3に記載の装置。運動行列を用いて映像シーケンスのピクチャを符号化するステップを含み、前記運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを対応するデコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、映像エンコーダにおける方法。前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、請求項8に記載の方法。前記符号化するステップは、埋め込み行列に前記運動行列を埋め込むステップと、前記埋め込み行列をサンプリングして前記埋め込み行列からのサンプルのサブセットを提供するステップと、前記サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するステップと、前記量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するステップとを含む、請求項8に記載の方法。前記埋め込み行列は、前記運動行列を乗じた2つの行列を用いて決定され、前記2つの行列は、前記埋め込み行列のランダムな固有ベクトルの閾値の量を与えるように選択される、請求項10に記載の方法。前記サンプルのサブセットは、前記埋め込み行列からランダムに選択される、請求項10に記載の方法。前記埋め込み行列からの前記サンプルのサブセットのサンプルが前記映像エンコーダおよび対応する映像デコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が前記映像エンコーダおよび前記対応する映像デコーダによって使用される、請求項12に記載の方法。前記サンプリングするステップは、前記サンプルのサブセットのサンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の部分を破棄するステップを含む、請求項10に記載の方法。運動行列の近似値を用いて映像シーケンスのピクチャを復号するための映像デコーダを備え、前記運動行列の前記近似値は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを前記映像デコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、装置。前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、請求項15に記載の装置。前記映像デコーダは、圧縮されたシンボルをエントロピー復号して、埋め込み行列からの量子化されたサンプルのサブセットを提供するためのエントロピーデコーダと、前記量子化されたサンプルのサブセットを逆量子化して、前記埋め込み行列の復元されたバージョンからのサンプルのサブセットの近似値を提供するための逆量子化器と、前記埋め込み行列の前記復元されたバージョンの欠落した部分を決定して、前記埋め込み行列の完成した復元されたバージョンを提供するための行列完成デバイスと、前記埋め込み行列の前記完成した復元されたバージョンから前記運動行列の前記近似値を再構築するための再構築デバイスとを備える、請求項15に記載の装置。前記埋め込み行列の前記復元されたバージョンの前記欠落した部分は、前記サンプルのサブセットのサンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の以前に破棄された部分に対応する、請求項17に記載の装置。前記運動行列の前記近似値は、前記埋め込み行列と、前記埋め込み行列の行列を乗じた2つの行列とを用いて決定される、請求項17に記載の装置。前記埋め込み行列からの前記サンプルのサブセットのサンプルが前記映像デコーダおよび対応する映像エンコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が前記映像デコーダおよび前記対応する映像エンコーダによって使用される、請求項17に記載の装置。前記運動行列の疎な表現が、前記埋め込み行列の前記復元されたバージョンに対して決定され、前記ピクチャのベクトル化された形態が、前記疎な表現および前記辞書に応じて決定され、前記ベクトル化された形態は、前記ピクチャの再構築されたバージョンを得るために再整形される、請求項15に記載の装置。運動行列の近似値を用いて映像シーケンスのピクチャを復号するステップを含み、前記運動行列の前記近似値は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを映像デコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、前記映像デコーダにおける方法。前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、請求項22に記載の方法。圧縮されたシンボルをエントロピー復号して、埋め込み行列からの量子化されたサンプルのサブセットを提供するステップと、前記量子化されたサンプルのサブセットを逆量子化して、前記埋め込み行列の復元されたバージョンからのサンプルのサブセットの近似値を提供するステップと、前記埋め込み行列の前記復元されたバージョンの欠落した部分を決定して、前記埋め込み行列の完成した復元されたバージョンを提供するステップと、前記埋め込み行列の前記完成した復元されたバージョンから前記運動行列の前記近似値を再構築するステップとをさらに含む、請求項22に記載の方法。前記埋め込み行列の前記復元されたバージョンの前記欠落した部分は、前記サンプルのサブセットのサンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の以前に破棄された部分に対応する、請求項24に記載の方法。前記運動行列の前記近似値は、前記埋め込み行列と、前記埋め込み行列を乗じた2つの行列とを用いて決定される、請求項24に記載の方法。前記埋め込み行列からの前記サンプルのサブセットのサンプルが前記映像デコーダおよび対応する映像エンコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が前記映像デコーダおよび前記対応する映像エンコーダによって使用される、請求項24に記載の方法。前記運動行列の疎な表現が、前記埋め込み行列の前記復元されたバージョンに対して決定され、前記ピクチャのベクトル化された形態が、前記疎な表現および前記辞書に応じて決定され、前記ベクトル化された形態は、前記ピクチャの再構築されたバージョンを得るために再整形される、請求項22に記載の方法。符号化された映像信号データをその中に有するコンピュータ可読ストレージ媒体であって、運動行列を用いて符号化された、映像シーケンスのピクチャを含み、前記運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを対応するデコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、コンピュータ可読ストレージ媒体。本原理は、運動行列を用いた映像の符号化および復号のための方法および装置を対象とする。この説明は、本原理を示す。したがって、当業者が、本明細書においてはっきりと説明されていないかまたは示されていないが本原理を具現化し、本原理の精神および範囲に含まれるさまざまな構成を考案し得ることが理解される。本明細書に記載のすべての例および条件を表す言い回しは、当技術分野を発展させるために1人のまたは複数の発明者によって与えられた本原理および概念を読者が理解することを助けるために教示を目的とするように意図されており、そのような具体的に記載された例および条件に限定されないものと解釈されるべきである。さらに、本原理の原理、態様、および実施形態ならびにそれらの具体的な例を示す本明細書のすべての記述は、それらの構造的均等物と機能的均等物の両方を包含するように意図される。加えて、そのような均等物は、現在知られている均等物と将来開発された均等物の両方、すなわち、構造に関係なく同じ機能を実行する開発された任意の要素を含むことが意図される。したがって、例えば、本明細書に示された構成図は、本原理を具現化する例示的な回路の概念図を表すことが当業者によって理解される。同様に、任意のフローチャート、流れ図、状態遷移図、擬似コードなどは、実質的にコンピュータ可読媒体中に表現される可能性があり、したがって、コンピュータまたはプロセッサが明示的に示されているか否かにかかわらずそのようなコンピュータまたはプロセッサによって実行される可能性があるさまざまなプロセスを表すことが理解される。図に示されたさまざまな要素の機能は、専用のハードウェア、および適切なソフトウェアに関連してソフトウェアを実行することができるハードウェアを使用することによって提供され得る。プロセッサによって提供されるとき、それらの機能は、単一の専用プロセッサによって、単一の共有プロセッサによって、または一部が共有される可能性がある複数の個別的なプロセッサによって提供され得る。さらに、用語プロセッサまたはコントローラの明示的な使用は、ソフトウェアを実行することができるハードウェアを排他的に指すものと解釈されるべきでなく、デジタル信号プロセッサDSPハードウェア、ソフトウェアを記憶するための読み出し専用メモリROM、ランダムアクセスメモリRAM、および不揮発性ストレージを限定することなしに暗黙的に含み得る。通常のおよび/またはカスタムのその他のハードウェアも、含まれ得る。同様に、図に示された任意のスイッチは、概念的であるに過ぎない。それらのスイッチの機能は、プログラム論理の動作によって、専用の論理によって、プログラムの制御と専用の論理とのインタラクションによって、またはさらには手動でも実行される可能性があり、具体的な技術は、状況からより具体的に理解されるように実施者によって選択され得る。本出願の請求項においては、指定された機能を実行するための手段として表された任意の要素は、例えば、aその機能を実行する回路要素の組み合わせ、またはb機能を実行するためにそのソフトウェアを実行するための適切な回路と組み合わされた任意の形態のソフトウェア、したがって、ファームウェア、マイクロコードなどを含むソフトウェアを含む、その機能を実行する任意の方法を包含するように意図される。そのような請求項によって定義される本原理は、さまざまな記載された手段によって提供される機能が、請求項が求めるように組み合わされ、まとめられるという事実に存する。したがって、それらの機能を提供することができる任意の手段は、本明細書に示された手段と均等であると見なされる。本明細書における本原理の一実施形態との言及およびそのその他の変化形は、その実施形態に関連して説明された特定の特徴、構造、特性などが本原理の少なくとも1つの実施形態に含まれることを意味する。したがって、本明細書中のさまざまな場所に現れる表現一実施形態においておよび任意のその他の変化形が現れることは、必ずしもすべてが同じ実施形態に言及しているとは限らない。例えば、A/B、Aおよび/またはB、およびAおよびBのうちの少なくとも1つの場合の以下の/、および/または、および~のうちの少なくとも1つのいずれかの使用は、1番目に挙げられた選択肢Aのみの選択、または2番目に挙げられた選択肢Bのみの選択、または両方の選択肢AおよびBの選択を包含するように意図されることを理解されたい。さらなる例として、A、B、および/またはCおよびA、B、およびCのうちの少なくとも1つの場合、そのような表現法は、1番目に挙げられた選択肢Aのみの選択、または2番目に挙げられた選択肢Bのみの選択、または3番目に挙げられた選択肢Cのみの選択、または1番目および2番目に挙げられた選択肢AおよびBのみの選択、または1番目および3番目に挙げられた選択肢AおよびCのみの選択、または2番目および3番目に挙げられた選択肢BおよびCのみの選択、または3つの選択肢のすべてAおよびBおよびCの選択を包含するように意図される。これは、当業者にはすぐに分かるように、列挙される項目の数に合わせて拡張され得る。また、本明細書において使用されるとき、語ピクチャおよび画像は交換可能なように使用され、映像シーケンスからの静止画像またはピクチャを指す。知られているように、ピクチャは、フレームまたはフィールドである可能性がある。図2に目を向けると、本原理が適用され得る例示的な映像エンコーダが、全体的に参照番号200によって示されている。図2は、発明者の提案する映像の符号化のアプローチの中心的要素のみを含んでおり、デブロッキングフィルタde-blockingfilter、予測などブロックによってさらに改善され得ることに留意することが重要である。映像エンコーダ200は、運動行列生成器220の第1の入力に信号通信で接続された出力を有する辞書生成器210を含む。運動行列生成器220の出力は、行列エンベッダ230の入力に信号通信で接続される。行列エンベッダ230の出力は、サンプラ240の入力に信号通信で接続される。サンプラ240の出力は、量子化器250の入力に信号通信で接続される。量子化器250の出力は、エントロピーエンコーダ260の入力に信号通信で接続される。辞書生成器210の入力および運動行列生成器220の第2の入力は、参照フレームを受信するためのエンコーダ200の入力として利用可能である。運動行列生成器220の第3の入力は、符号化されるべきフレームを受信するためのエンコーダ200の入力として利用可能である。エントロピーエンコーダ260の出力は、符号化されたビットストリームを出力するためのエンコーダ200の出力として利用可能である。図3に目を向けると、本原理が適用され得る例示的な映像デコーダが、全体的に参照番号300によって示されている。図3は、発明者の提案する映像の復号のアプローチの中心的要素のみを含んでおり、デブロッキングフィルタ、予測などブロックによってさらに改善され得ることに留意することが重要である。映像デコーダ300は、逆量子化器320の入力に信号通信で接続された出力を有するエントロピーデコーダ310を含む。逆量子化器320の出力は、行列完成器330の入力に信号通信で接続される。行列完成器330の出力は、運動行列復元器340の入力に信号通信で接続される。運動行列復元器340の出力は、画像リコンストラクタ350の第1の入力に信号通信で接続される。辞書生成器360の出力は、画像リコンストラクタ350の第2の入力に信号通信で接続される。エントロピーデコーダ310の入力は、入力ビットストリームを受信するためのデコーダ300の入力として利用可能である。辞書生成器360の入力は、参照フレームを受信するためのデコーダ300の入力として利用可能である。画像リコンストラクタ350の出力は、1つまたは複数の再構築された画像を出力するためのデコーダ300の出力として利用可能である。画像リコンストラクタ350は、参照フレームを受信するための1つまたは複数の追加的な入力を含む可能性がある。上述のように、本原理は、運動行列を用いた映像の符号化および復号のための方法および装置を対象とする。高い圧縮効率を実現するために、実質的にすべての映像符号化方式は、以下、すなわち、a時間的相関、または連続するフレームの間の相関、およびb空間的相関、つまりフレームおよび/またはピクチャ内の隣接するピクセルもしくはそれ以外の状態で近くにあるピクセルの間の相関を利用する。高い空間的相関は、位置i,jのピクセル値が行列の第i,j成分に記憶される行列の形態のN×Mピクセルのデジタル画像を考えた場合、その画像のピクセル値が強い相関を有し、独立していないことを意味する。数学的観点から、これは、対応する行列が低い階数または低い独立性を有することを意味する。一方、高い時間的相関は、特定の時間のフレームの多くの部分が、厳密にかまたはおおよそかのどちらかで前のフレームでおそらく異なる位置で発見され得ることを意味する。本原理によって、発明者は、圧縮センシングおよび低階数の行列の完成の数学的ツールを利用する新たなシステムを開発した。発明者は、この新しいアプローチを、高い時間的相関および空間的相関を利用して映像シーケンスを符号化するための代替的なアプローチを表す概念、運動行列と呼ぶ。発明者は、運動行列の原理と、運動行列がどのようにして映像エンコーダおよびデコーダで実装されるかを開示し、説明する。さらに、提案される運動行列の例/実施形態が示され、対応するエンコーダ/デコーダのさまざまなコンポーネントが説明される。この方式は、本明細書に記載のいくつかの新たな符号化ブロックを含む。また、説明を簡単にするために、普遍性を損なうことなく、本原理は1つの参照フレームのみが存在するPフレームに関連して説明される。明らかに、この考え方は、複数の参照フレームの場合に容易に拡張可能である。[概要]本原理によって、発明者は、映像コンテンツを符号化および復号するためのシステムを説明する。説明を明瞭にするために特定の文脈および実施形態で説明されるが、本明細書に記載の同じ原理のうちの1つまたは複数を利用し、したがって本原理の範疇に入ることから除外されてはならないその他の実施形態は、当業者に明らかであろう。例えば、デコーダの圧縮センシングモジュールは、基底追跡basispursuitアルゴリズムを用いて実現され得るが、同じ目的を達成することができる文献中のその他のよくあるアルゴリズムおよびその他の将来開発されたアルゴリズムが存在し、それらのアルゴリズムは、本発明の包括的原理および範囲に含まれるように意図される。発明者は、基底追跡BPアルゴリズムが凸最適化問題を解くことを伴うことを強調する。より具体的には、BPは、一次方程式の劣決定系y=Pxに対する最小のL1ノルム絶対値の総和を用いて解を発見し、ここで、yの値および係数Pの行列が与えられており、xは未知のベクトルである。さらに、一次方程式の劣決定系によって、発明者は、式の数ここではPの行列の行の数が未知数の数未知のベクトルxの長さ未満であることを意味する。数学的形式で、BPは以下の最適化問題を解く。y=PxであるようなArgmin||x||1=Σ|xi|特定の条件の下で、BPによって発見される解は最も疎な解、すなわち、最小数の非ゼロの数を有する解であることが証明されている。映像シーケンスからの時間t1における画像f1を考える。この画像が、例えば図1に示されるように時間t2においてf2に変化すると仮定する。大まかに言って、最も古典的な映像符号化方式においては、そのような動きは以下のように分解される。f2=Xf1Rここで、X.は基本関数basicfunctionであり、Rは何らかの残差である。例えば、図1の例に関して、X.は、画像f1を入力として受け取り、次いで、出力のためにその画像f1を右に1ピクセルだけシフトする関数であり、Rは残差である。圧縮は、X.およびRを効率的に符号化することによって達せられる。例に戻ると、X.は、動きベクトルとして符号化される可能性があり、Rは、離散コサイン変換DCTなどの変換領域でRを表すことによって効率的に圧縮され得る。この符号化の包括的な枠組み、すなわち、参照フレームにおける何らかの動きおよび何らかの残差に関して画像を分解することは、時間的相関を広く利用して圧縮を行うことに留意されたい。空間的相関は、残差の変換符号化によっても利用される。一方、DCT、ウェーブレットなどの利用可能な変換は、残差の代わりに、相関性の高い画像を希薄化する疎にするように設計されている。言い換えると、変換を利用して残差を符号化することは過去うまくいっていたが、映像データを圧縮する能力をよりいっそう高めるために、将来開発される方式においては空間的相関が使用される可能性がある。一次方程式の劣決定系およびさらに低階数の行列の完成の問題に関して最近生み出された成果を使用する、本発明の原理による、発明者が本明細書で説明する方法および装置は、代替的な符号化および復号方式を設計するために使用される。[運動行列]符号化されるべきフレーム例えば、図1のf2に関する運動行列は、行列Yである。デコーダは、運動行列および参照フレーム例えば、f1を用いて符号化されたフレームを一意的に再構築することができる。さらに、運動行列は、以下の2つの追加的な重要な性質を有する。運動行列は、低い階数を有する。言い換えると、Yの成分は相関性が高い。運動行列は、符号化されるべきフレームの知識を必要とせずにデコーダにおいて導出され得る辞書ψ、すなわち、アトム/基底ベクトルの組例えば、離散コサイン変換は画像を表現するための辞書であるに対する疎な表現αを有し、つまり、VecY=ψαであり、ここで、Vec.は、行列の列を積み上げることによって形成される行列のベクトル化された形態図4参照を表し、αは、要素のほとんどがゼロである疎なベクトルである。ここで、発明者は、本明細書で導入された運動行列が、概念と、さらには圧縮を行うために選択されるアプローチとの両方において従来の研究の変位行列displacementmatrixおよび運動行列におけるそれから離れることを強調する必要がある。以下で、発明者は、重要な違いのうちのいくつかを明らかにする。変位行列および従来の運動行列は、主として2値行列を利用する。一方、提案される運動行列の成分は、負数および浮動小数点数を含む任意の数を取り得る。従来の研究の変位行列および運動行列の成分は、一部のブロックおよび/またはピクセルにおけるいくつかの種類の動きの存在を示す。一方、提案される運動行列の成分は、一部のブロックにおける動きを示すタスクに制限されない。例えば、提案される運動行列の成分は、フレーム全体におけるいくつかの全体的な動きフレームにおけるすべての動きに応じて決まる値を知らせる可能性がある。従来の研究においては、参照フレームが与えられたとして、運動および/または変位行列は、通常、フレームを再構築するために十分でない。例えば、残差行列、またはデコーダ側での望ましい再構築のためのその他のシグナリングなどのオーバーヘッドデータを送信する必要がある可能性がある。発明者の方法は、単独で機能する運動行列を対象としており、参照フレームが与えられるとすれば、運動行列さえあれば、既に符号化されたフレームを妥当な誤差で近似するために十分である。従来の運動行列および/または変位行列は、発明者の定義におけるすべての必要条件に通常反するので、それらの従来の運動行列および/または変位行列は、発明者の提案する運動行列の枠組みに入らない。例えば、斜線が数ピクセルだけ右または左にシフトするフレームまたはブロックを考える。そのとき、対応する変位行列はフルランク最大のあり得る階数の対角行列になることは容易に理解できる。さらに、そのような対角行列つまり画像は、DCT、ウェーブレットなどの従来の変換の下では疎でないこれらの種類の行列に適した何らかの方向変換directionaltransformが存在する可能性があるが、しかし、我々は、それらの変換/辞書のパラメータをデコーダに送信する必要があり、これは余計なオーバーヘッドを生じる。したがって、従来の変位/運動行列は、運動行列に関する2つの必要条件すなわち、低階数であることおよび希薄化領域sparsifyingdomainの存在に容易に違反し得る。別の違いが復号段階に現れる。より具体的には、従来の符号化の方法は、予測および残差の符号化を利用して圧縮を行う。一方、発明者は、行列の完成および圧縮センシングを用いて一次方程式の劣決定系を解くことなどの最近生み出された/解かれたアルゴリズム/問題を利用して同様の目的を達成する。最後になるが、従来の変位行列および運動行列は、概して、異なるフレームの間の時間的相関に応じて決まり、フレーム内の隣接するピクセルの間の空間的相関には反応するにしてもあまり左右されない。しかし、発明者の提案する運動行列は、映像コンテンツを圧縮するために時間的相関と空間的相関とを同時にまとめて考慮する。図4に目を向けると、運動行列をベクトル化する例示的な操作と、ベクトル化操作の逆の操作とが、全体的に参照番号400によって示されている。ベクトル化された形態が参照番号410によって示され、ベクトル化された形態の逆の形態が参照番号420によって示されている。運動行列は、符号化されるべきフレームの低階数の行列をもたらす高い空間的相関と、希薄化フレームsparsifyingframeの存在につながる高い時間的相関とを一緒に利用することによって形成され得る。運動行列の形成は、上述のアプローチに限定されず、したがって、運動行列を形成するためのその他のアプローチも、本原理の精神を維持しながら、本明細書において与えられた本原理の教示にしたがって使用され得ることを理解されたい。次に、運動行列に基づく映像符号化方式のための対応するエンコーダおよびデコーダを示す。図5に目を向けると、運動行列に基づく映像符号化方式を用いた符号化のための例示的な方法が、全体的に参照番号500によって示されている。方法500は、機能ブロック510および機能ブロック515に制御を渡す開始ブロック505を含む。機能ブロック510は、参照{f1,...,fq-1}フレームを入力し、機能ブロック520に制御を渡す。機能ブロック520は、符号化されるべきフレームがその辞書に対して疎である辞書を例えば、参照フレームに基づいて生成し、機能ブロック525に制御を渡す。機能ブロック515は、符号化されるべきフレームfqを入力し、機能ブロック525に制御を渡す。機能ブロック525は、運動行列を発見し、機能ブロック530に制御を渡す。機能ブロック530は、運動行列を、より圧縮しやすいおそらくはより小さい行列に埋め込み、機能ブロック535に制御を渡す。機能ブロック535は、埋め込み行列からサンプリングしすなわち、成分のサブセットを残し、残りを破棄する、機能ブロック540に制御を渡す。機能ブロック540は、埋め込み行列のサンプルを量子化し、機能ブロック545に制御を渡す。機能ブロック545は、埋め込み行列の量子化されたサンプルをエントロピー符号化し、機能ブロック550に制御を渡す。機能ブロック550は、埋め込み行列のエントロピー符号化されたサンプルを記憶および/または送信し、終了ブロック599に制御を渡す。説明された運動行列に関する符号化の方法500は、5つの主要な構成部分を含む。1.符号化されるべきフレームおよび一連の参照フレームが与えられたとき、符号化されるべきフレームがその辞書に対して疎である辞書ψを形成し、運動行列Yを発見する。上述のように、運動行列Yおよび参照フレームおよび、したがって、希薄化辞書sparsifyingdictionaryψがあれば、デコーダは、符号化されたフレームを再構築することができる。2.運動行列を、埋め込み行列Z=p1Yp2に埋め込み、ここで、p1およびp2は2つの行列である。設計によって、埋め込み行列Zは、さらなる圧縮を実現するために利用され得る運動行列のすべての望ましい性質、すなわち、低階数の性質と、その行列に関する希薄化基底sparsifyingbasisの存在とを受け継ぐことに留意されたい。配置された行列p1およびp2も、我々が圧縮を行うのに役立つ可能性がある。例えば、p1およびp2がそれぞれ幅が広い行列および高さが高い行列である場合、埋め込み行列Zは、運動行列よりも小さくなり、このことは、レベルの違う圧縮につながる。このステップの目的は、Zの多くの成分が支障なく破棄される可能性があり、その一方で、デコーダが破棄された成分を復元することができることを保証することである。さらに、このステップは、以降で示されるように、デコーダのステップ3および4が成功するために極めて重要である。行列p1およびp2は、aZ、p1、およびp2があれば、我々が運動行列Yを再構築することができ、bZの固有ベクトルが十分にランダムであるように選択されることに留意することが重要である。例えば、p1およびp2が、それぞれ、幅が広いランダム行列および高さが高いランダム行列である場合、埋め込み行列Zが運動行列Yよりも小さいとしても、上述の要件の両方が満たされる。行列p1およびp2のそのようなランダムな選択は、圧縮の観点からすると最適なアプローチではない可能性がある。3.サンプリング:埋め込み行列Zの成分のおそらくはランダムなサブセットSを残し、残りの成分を破棄する。このステップは、我々が残差または画像自体の最も大きなDCT係数を残し、そのような重要度の大きい成分の値および位置をシグナリングする従来の映像方式の圧縮ステップを思わせると考える人もいるであろう。一方、発明者の方式のこのステップは、完全にランダムであり、埋め込み行列のどの成分もその他の成分と区別しない。結果として、エンコーダおよびデコーダが同じ乱数のシードおよび乱数生成器を使用する場合、それらのエンコーダおよびデコーダは、両方とも、Zの成分の位置について一致する。したがって、これらの成分の位置をシグナリングする必要はなく、エンコーダは、サンプル値を記憶/送信するだけである可能性がある。4.埋め込み行列からのサンプルSをへと量子化する。明らかに、これは非可逆圧縮ステップである。しかし、このステップは、実質的にすべての圧縮技術に必須である。5.埋め込み行列の量子化されたサンプルを圧縮されたシンボルCへとエントロピー符号化する。これらのシンボルCは、記憶されるか、またはデコーダに送信される。図6に目を向けると、運動行列に基づく映像符号化方式を用いた復号のための例示的な方法が、全体的に参照番号600によって示されている。方法600は、機能ブロック610および機能ブロック645に制御を渡す開始ブロック605を含む。機能ブロック610は、符号化されたシンボルCを入力し、機能ブロック615に制御を渡す。機能ブロック615は、受信されたシンボルCをエントロピー復号し、機能ブロック620に制御を渡す。機能ブロック620は、復号されたシンボルCを逆量子化し、機能ブロック625に制御を渡す。機能ブロック625は、行列の完成を行い、機能ブロック630に制御を渡す。機能ブロック630は、埋め込み行列から運動行列を復元し、機能ブロック635に制御を渡す。機能ブロック645は、参照フレーム{f1,...,fq-1}を入力し、機能ブロック650に制御を渡す。機能ブロック650は、辞書を生成し、機能ブロック635に制御を渡す。機能ブロック635は、運動行列を復号してfqを出力し、終了ブロック699に制御を渡す。復号の方法600は、5つの主要な構成部分を含む。1.圧縮されたシンボルCをエントロピー復号して、埋め込み行列Zの量子化されたサンプルを得る。2.サンプルを逆量子化して、埋め込み行列のサンプルの近似値を得る。3.埋め込み行列Zの一部の成分の近似値を得たとき、行列の完成を行うことによって、埋め込み行列Zの破棄された成分を復元する。このステップは、エンコーダで実行されたサンプリングステップ2の逆の処理であることに留意されたい。非可逆な量子化のステップが原因で、破棄された成分が厳密に復元されないことが十分にあり得る。したがって、発明者は、この段階の出力をと表記する。4.前のステップで復元された埋め込み行列から運動行列の近似値を再構築する。運動行列が辞書ψに対して疎な表現αを有するすなわち、という事実を利用して一次方程式のおそらくは劣決定の系を形成する人もいるであろう。より具体的には、を得たとき、我々は、以下に対する解を見つける。この解は、基底追跡または直交マッチング追跡OrthogonalMatchingPursuitなどの圧縮センシングのデコーダを使用することによって発見され得る。結果として、運動行列の近似値は、によって推定可能であり、ここで、Vec-1.は、ベクトルを行列の形態に戻すように再整形する図4参照。辞書ψは符号化されたフレームとは無関係に決まり、したがって、デコーダ側でオーバーヘッドなしで、または極めて少ないオーバーヘッドで複製され得ることに留意することが重要である。5.符号化されたフレームf2を再構築するためには、運動行列Yおよび参照フレームがあれば十分であると考えられる。したがって、我々は、前のステップからの元の運動行列の近似値および参照フレームを利用して符号化されたフレームf2の近似値を再構築することができる。[エンコーダ]本節では、運動行列の一実施形態の例が示される。また、そのような運動行列を符号化および復号するための必要とされるステップが、より詳細に与えられる。[単純な運動行列]我々は、参照フレームf1を利用することによってフレームf2を符号化したいものとする。上述のように、提案されるエンコーダの第1の段階は、運動行列Yを見つけることである。単純な形態の運動行列は、f2すなわち、符号化されるべきフレームの修正されたバージョンであり、したがって、によって表されるこの修正されたバージョンは、以下の3つの重要な性質を有する。aYは低階数である。bYは、参照フレームと、おそらくはDCTまたはウェーブレットなどのいくつかのその他の変換とから構築された過剰決定辞書over-completedictionaryに対する疎な表現αを有する。cYは、f2符号化されるべきフレームの優れた近似であり、すなわち、初めの2つの性質は、運動行列の要件であり、3つ目の性質は、運動行列および参照フレームから符号化されたフレームを推定するデコーダのステップ5必要がないことを示している。言い換えると、運動行列自体が、符号化されたフレームに極めて近く、直接表示され得る。ここで、そのような運動行列を発見するための必要とされるステップについてさらに詳細に検討することにする。そのような運動行列を発見するための第1のステップは、運動行列がその辞書に対して疎になる辞書ψを生成することである。上述のように、この辞書は、参照フレームのみに応じて決まるかつ符号化されるべきフレームとは無関係に決まる。したがって、辞書は、デコーダ側で正確に複製され得る。例えば、この辞書は、参照フレームに対してさまざまな動きさまざまな方向へのさまざまなシフト、回転、拡大などまたはいくつかの予測を計算することによって形成され得る。この辞書を拡張し、さらに、この辞書がすべてのあり得る画像を生成することができることを保証するすなわち、この辞書がフルランクであるために、いくつかの変換例えば、DCT、ウェーブレットなどが辞書に追加され得る。適切に設計される場合、高い時間的相関が、符号化されるべきフレームがこの辞書に対する疎な表現を有することを保証することに留意されたい。目標の希薄化辞書ψを形成した後、運動行列を発見することがまだ残っている。この運動行列は、以下の方法によって計算され得る。入力:希薄化辞書ψ、参照フレームf1、符号化されるべきフレームf2、目標の階数r、および目標の疎性sparsityk出力:運動行列Y初期化Y=f2do{ψに対するYの表現αを見つける:VecY=ψαが、αの大きい方からk個の成分だけを残し、残りのインデックスindexのところはゼロとすることによって計算されたベクトルであるものとするYをに更新する。Yの大きい方からr個の固有値を残し、残りの固有値をゼロに設定する}収束するか、または誤差が十分に小さくなるまで繰り返す基本的に、この方法は、2つの制約、つまり、a出力行列Yが階数rを有することと、b出力行列Yが辞書ψに対する疎性kの表現を有することとの間で繰り返される。以下のようないくつかの注意点を強調しておくことが重要である。kおよびrを調整することにより、圧縮の量を制御する。具体的には、rおよびkが増加するにつれて、デコーダで再構築される運動行列の品質が高くなり、その代償として圧縮幅は少なくなり、その逆も同様である。高い空間的相関は、運動行列の品質の急激な落ち込みを招くことなく、符号化されるべきフレームの階数rを大幅に低くすることを可能にする。高い時間的相関は、符号化されるべきフレームf2が辞書ψのほんの数個k個のアトムを用いて近似されることを可能にする。[行列の埋め込み]修正されたフレームつまり運動行列を得て、行列p1およびp2を利用することにより、我々は、f2をに埋め込む。ここで、第1の行列p1は幅が広い行列であり、一方、第2の行列p2は高さが高い行列である。さらに、行列p1およびp2は、埋め込み行列Z、p1、およびp2があれば、我々がを復元できるように選択される。例えば、p1およびp2はランダム行列である可能性があるが、ただし、そのような選択は最適な選択ではない。図7に目を向けると、運動行列を低階数の密行列Zに埋め込むための例示的な方法が、全体的に参照番号700によって示されている。方法700は、低階数の運動行列を、別の、低階数であるがよりコンパクトな埋め込み行列Z720へと圧縮するために使用されるランダムで密な行列p1705、低階数の運動行列710、およびランダムで密な行列p2715を含む。行列の埋め込みの役割と、さらに行列p1およびp2の役割とは、デコーダの説明に関連してより詳細に検討される。行列Zは、最高でも運動行列の階数に等しい低階数であることに留意されたい。さらに重要なことに、行列Zは、符号化されるべきフレームf2またはフレームf2の修正/再構築されたバージョン、つまりよりも少ない成分を有する。したがって、これは、提案される方法の最初のレベルの圧縮である。明らかに、このステップで実現され得る圧縮のレベルにはいくつかの制限がある。より具体的には、行列Zの成分の数は、前のステップのkおよびrに直接的に応じて決まる。これらの実施形態においては、kおよびrの異なる値が使用される可能性があり、またはこれらの値がフレームf2もしくは行列Zの特性に適応的である可能性があることに留意されたい。[サンプリング]埋め込み行列Zの比較的小さなランダムなサブセットSのみを残し、残りの成分を破棄することによって、レベルの違う圧縮が実現される。図8に目を向けると、運動行列からのサンプリングおよび行列の完成のための例示的な方法が、全体的に参照番号800によって示されている。方法800は、低階数で密な埋め込み行列805および低階数で密な埋め込み行列810を含む。デコーダおよびエンコーダが同じ乱数のシードおよび乱数生成器を使用する場合、成分の値Sのみが送信され、デコーダとエンコーダの両方はこれらの成分の位置が分かり、このことはインデックスが送信されないのでさらなる圧縮をもたらす。[量子化およびエントロピー符号化]前の段階からの埋め込み行列Zの成分のランダムなサブセットSは、量子化され、最終的な圧縮されたシンボルCを得るためにエントロピーコーダに通される。デコーダデコーダのさまざまなコンポーネントが、本明細書において既に導入された基本的な運動行列の場合について示され、説明される。[逆量子化およびエントロピー復号]最も古典的な映像符号化方式と同様に、デコーダの第1の段階は、圧縮されたシンボルCを復号し、復号されたシンボルを逆量子化して、埋め込み行列Zの成分のランダムなサブセットの近似値を得る。[行列の完成]最近、非常に関心の高い問題、具体的には、低階数の行列の完成が、いくつかの条件の下である程度まで解かれた。大まかに言って、この問題は、我々は、低階数の行列があり、その行列の成分のサブセットのみを見ることができるとして、見えない成分を近似することができるのかという疑問に対応する。もちろん、この疑問に対応する答えは、その行列による。図9に目を向けると、対応する固有ベクトルが十分にランダムであるときの低階数の行列の完成の例が、全体的に参照番号900によって示されている。図10に目を向けると、対応する固有ベクトルが十分にはランダムでないことが原因で失敗する低階数の行列の例が、全体的に参照番号1000によって示されている。したがって、例えば、例900に関して、我々が基礎となる行列が低階数であると確信している場合、欠けている成分は、第2列が第1列の3倍であるので6である。一方、例1000に関しては、欠けている成分は、任意の数である可能性があり、推定し得ない。いくつかの条件が満たされる場合、例えば、低階数の行列の固有ベクトルが十分にランダムである場合、低階数の行列の完成は容易に解くことができることが示されており、特異値閾値法SingularValueThresholdingSVT、不動点連続法FixedPointContinuationFPCなどのいくつかのアルゴリズムが、この問題を解くために提案されている。今や、埋め込みのステップおよび行列p1およびp2の役割は、明らかであるに違いない。特に、これらの行列は、埋め込み行列Zの固有ベクトルが十分にランダムであることを保証する。したがって、そのような行列の多くの成分が、圧縮を行うために破棄される可能性がある一方、いくつかの行列完成アルゴリズムが、それらの破棄された成分を復元することができる。埋め込み行列Zが低階数であるという事実を利用して、サンプルの近似値が、Zの欠落した成分図8参照を復元するために行列完成アルゴリズムに入力として与えられる。復元された行列は、埋め込み行列Zと等しくない可能性があることに留意されたい。これは、量子化ステップからの誤差の伝播が原因である。しかし、推定誤差ここで、||.||Fはフロベニウス行列ノルムを表すは、量子化ステップで生じた誤差に比例する。[一次方程式の劣決定系を解く]運動行列、つまり、符号化されるべきフレームの修正されたバージョンは、参照フレームに基づいて構築された辞書ψに対する疎な表現を近似的に有し、すなわち、VecY=ψαであることを思い出されたい。埋め込み運動行列のベクトル化された形態は、以下によって表現し直され得ることにも留意されたい。ここで、は、クロネッカーテンソル積であり、Vec.は、行列のベクトル化された形態を表す図11参照。図11に目を向けると、修正されたフレームfq’の疎な表現の圧縮サンプルから形成された埋め込み行列Zの例が、全体的に参照番号1100によって示されている。埋め込み行列Zはに比べて少ない数の成分を有するので、したがって、1は、埋め込み行列Zの成分が等式であり、αの成分が未知である一次方程式の劣決定系である。最近生み出された圧縮センシングCSの理論は、解が疎であるとき、一次方程式の劣決定系の解が、特定の条件の下で容易に計算され得ることを示した。ここで、行列p1およびp2の役割は、これらの条件を満たしやすくすることである。ゆえに、Zの近似値があれば、疎なベクトルαは、通常のCSデコーダによって、例えば、基底追跡のアルゴリズムを用いることにより復元され得る。その他の実施形態においては、本原理の精神を維持しながら、疎なベクトルを復元するためのその他の方法が使用され得る。結果として、運動行列のベクトル化された形態は、以下によって復元され得る。VecY=ψα運動行列のベクトル化された形態を再整形することにより、我々は運動行列を得る。しかし、この例において、我々は、運動行列が符号化されたフレームの優れた近似であると仮定した。したがって、運動行列および参照フレームから符号化されたフレームを推定する必要はなく、我々は、導出された運動行列をそのまま表示することができる。一部が上で説明された本発明に付随する多くの利点/特徴のうちのいくつかが、以下で説明される。例えば、1つの利点/特徴は、運動行列を用いて映像シーケンスのピクチャを符号化するための映像エンコーダを有する装置である。運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有する。辞書は、ピクチャを表すため、およびピクチャがその組のみを用いて対応するデコーダにおいて導出されることを可能にするためのアトムおよび基底ベクトルの組を含む。辞書は、映像シーケンスの参照ピクチャの組から形成される。別の利点/特徴は、上述のように映像エンコーダを有する装置であり、辞書は、ピクチャと参照ピクチャの組との間の空間的相関および時間的相関から形成される。さらに別の利点/特徴は、上述のように映像エンコーダを有する装置であり、映像エンコーダは、埋め込み行列に運動行列を埋め込むための埋め込みデバイスと、埋め込み行列をサンプリングして埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを含む。さらに別の利点/特徴は、上述のように、映像エンコーダが、埋め込み行列に運動行列を埋め込むための埋め込みデバイスと、埋め込み行列をサンプリングして埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを含む、映像エンコーダを有する装置であり、埋め込み行列は、運動行列を乗じた2つの行列を用いて決定され、2つの行列は、埋め込み行列のランダムな固有ベクトルの閾値の量を与えるように選択される。さらに、別の利点/特徴は、上述のように、映像エンコーダが、埋め込み行列に運動行列を埋め込むための埋め込みデバイスと、埋め込み行列をサンプリングして埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを含む、映像エンコーダを有する装置であり、サンプルのサブセットは、埋め込み行列からランダムに選択される。さらに、別の利点/特徴は、上述のように、サンプルのサブセットが、埋め込み行列からランダムに選択される、映像エンコーダを有する装置であり、埋め込み行列からのサンプルのサブセットのサンプルが映像エンコーダおよび対応する映像デコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が映像エンコーダおよび対応する映像デコーダによって使用される。さらに、別の利点/特徴は、上述のように、映像エンコーダが、埋め込み行列に運動行列を埋め込むための埋め込みデバイスと、埋め込み行列をサンプリングして埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを含む、映像エンコーダを有する装置であり、前記サンプラは、サンプルのサブセットのサンプルと異なる埋め込み行列内の位置にある埋め込み行列の部分を破棄する。本原理のこれらのおよびその他の特徴および利点は、本明細書の教示に基づいて当業者によって容易に確認され得る。本原理の教示は、さまざまな形態のハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、またはこれらの組み合わせで実装され得ることを理解されたい。最も好ましくは、本原理の教示は、ハードウェアとソフトウェアの組み合わせとして実装される。さらに、ソフトウェアは、プログラムストレージユニットに有形で具現化されるアプリケーションプログラムとして実装され得る。アプリケーションプログラムは、任意の好適なアーキテクチャを備える機械にアップロードされ、そのような機械によって実行され得る。好ましくは、機械は、1つまたは複数の中央演算処理装置CPU、ランダムアクセスメモリRAM、および入力/出力I/Oインターフェースなどのハードウェアを有するコンピュータプラットフォーム上に実装される。また、コンピュータプラットフォームは、オペレーティングシステムおよびマイクロ命令コードを含み得る。本明細書において説明されたさまざまなプロセスおよび機能は、CPUによって実行され得るマイクロ命令コードの一部かもしくはアプリケーションプログラムの一部かのどちらか、またはそれらの任意の組み合わせである可能性がある。加えて、追加的なデータストレージユニットおよび印刷ユニットなどのさまざまなその他の周辺ユニットが、コンピュータプラットフォームに接続され得る。添付の図面に示された構成要素のシステムコンポーネントおよび方法の一部はソフトウェアで実装されることが好ましいので、システムコンポーネントまたはプロセスの機能ブロックの間の実際の接続は、本原理がプログラムされる方法によって変わり得ることをさらに理解されたい。本明細書の教示が与えられれば、当業者は、本原理のこれらのおよび同様の実装または構成を考えることができる。例示的な実施形態が添付の図面を参照して本明細書において説明されたが、本原理はそれらの厳密な実施形態に限定されず、さまざまな変更および修正が、本原理の範囲または精神を逸脱することなく当業者によってそれらの実施形態で行われ得ることを理解されたい。すべてのそのような変更および修正は、添付の特許請求の範囲に記載された本原理の範囲に入るように意図される。"