(57)【特許請求の範囲】
【請求項１】
運動行列を用いて映像シーケンスのピクチャを符号化するための映像エンコーダを備え、前記運動行列はデコーダに前記運動行列および参照フレームを用いて前記ピクチャを一意的に再構築させることができるデータを有し、
前記運動行列は、所与の階数を有し、前記運動行列の列を積み上げることにより形成されるベクトルは、辞書と疎な表現との積からなり、
前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを対応するデコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、非ゼロの残差値の数を最小化するために前記映像シーケンスの参照ピクチャの組から形成され、
前記運動行列は、
第１の表現を見出す第１のステップであって、前記辞書と前記第１の表現との積が、初期値が前記ピクチャである第１の行列の列を積み上げることにより形成されるベクトルである、前記第１のステップと、
前記第１の表現の大きい方から所与の数の成分だけを有する第２の表現を生成する第２のステップと、
第２の行列を作成する第３のステップであって、前記第２の行列の列を積み上げることにより形成されるベクトルは前記辞書と前記第２の表現との積である、前記第３のステップと、
前記第２の行列の大きい方から前記所与の階数と同じ数の固有値を有する第３の行列を生成する第４のステップと、
前記第１の表現がある特定のレベルに収束するまで、前記第１の行列を前記第３の行列に置き換えて前記第１のステップから前記第４のステップを繰り返し、前記第１の表現がある特定のレベルに収束したとき、前記第１の行列を前記運動行列とする、第５のステップと、
により見出される、装置。
【請求項２】
前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、請求項１に記載の装置。
【請求項３】
前記映像エンコーダは、埋め込み行列に前記運動行列を埋め込むための埋め込みデバイスと、前記埋め込み行列をサンプリングして前記埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、前記サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、前記量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを備える、請求項１に記載の装置。
【請求項４】
前記埋め込み行列は、前記運動行列を乗じた２つの行列を用いて決定され、前記２つの行列は、前記埋め込み行列のランダムな固有ベクトルの閾値の量を与えるように選択される、請求項３に記載の装置。
【請求項５】
運動行列を用いて映像シーケンスのピクチャを符号化するステップを含み、前記運動行列はデコーダに前記運動行列および参照フレームを用いて前記ピクチャを一意的に再構築させることができるデータを有し、
前記運動行列は、所与の階数を有し、前記運動行列の列を積み上げることにより形成されるベクトルは、辞書と疎な表現との積からなり、
前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを対応するデコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、非ゼロの残差値の数を最小化するために前記映像シーケンスの参照ピクチャの組から形成され、
前記運動行列は、
第１の表現を見出す第１のステップであって、前記辞書と前記第１の表現との積が、初期値が前記ピクチャである第１の行列の列を積み上げることにより形成されるベクトルである、前記第１のステップと、
前記第１の表現の大きい方から所与の数の成分だけを有する第２の表現を生成する第２のステップと、
第２の行列を作成する第３のステップであって、前記第２の行列の列を積み上げることにより形成されるベクトルは前記辞書と前記第２の表現との積である、前記第３のステップと、
前記第２の行列の大きい方から前記所与の階数と同じ数の固有値を有する第３の行列を生成する第４のステップと、
前記第１の表現がある特定のレベルに収束するまで、前記第１の行列を前記第３の行列に置き換えて前記第１のステップから前記第４のステップを繰り返し、前記第１の表現がある特定のレベルに収束したとき、前記第１の行列を前記運動行列とする、第５のステップと、
により見出される、映像エンコーダにおける方法。
【請求項６】
前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、請求項５に記載の方法。
【請求項７】
前記符号化するステップは、
埋め込み行列に前記運動行列を埋め込むステップと、
前記埋め込み行列をサンプリングして前記埋め込み行列からのサンプルのサブセットを提供するステップと、
前記サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するステップと、
前記量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するステップと、
を含む、請求項５に記載の方法。
【請求項８】
前記埋め込み行列は、前記運動行列を乗じた２つの行列を用いて決定され、前記２つの行列は、前記埋め込み行列のランダムな固有ベクトルの閾値の量を与えるように選択される、請求項７に記載の方法。
【請求項９】
前記サンプルのサブセットは、前記埋め込み行列からランダムに選択される、請求項７に記載の方法。
【請求項１０】
前記サンプリングするステップは、前記サンプルのサブセットの前記サンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の部分を破棄するステップを含む、請求項７に記載の方法。
【請求項１１】
運動行列の近似値を用いて映像シーケンスのピクチャを復号するための映像デコーダを備え、前記運動行列は前記映像デコーダに前記運動行列および参照フレームを用いて前記ピクチャを一意的に再構築させることができるデータを有し、
前記運動行列の前記近似値は、所与の階数を有し、前記運動行列の列を積み上げることにより形成されるベクトルは、辞書と疎な表現との積からなり、
前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを前記映像デコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、非ゼロの残差値の数を最小化するために前記映像シーケンスの参照ピクチャの組から形成され、
前記運動行列は、
第１の表現を見出す第１のステップであって、前記辞書と前記第１の表現との積が、初期値が前記ピクチャである第１の行列の列を積み上げることにより形成されるベクトルである、前記第１のステップと、
前記第１の表現の大きい方から所与の数の成分だけを有する第２の表現を生成する第２のステップと、
第２の行列を作成する第３のステップであって、前記第２の行列の列を積み上げることにより形成されるベクトルは前記辞書と前記第２の表現との積である、前記第３のステップと、
前記第２の行列の大きい方から前記所与の階数と同じ数の固有値を有する第３の行列を生成する第４のステップと、
前記第１の表現がある特定のレベルに収束するまで、前記第１の行列を前記第３の行列に置き換えて前記第１のステップから前記第４のステップを繰り返し、前記第１の表現がある特定のレベルに収束したとき、前記第１の行列を前記運動行列とする、第５のステップと、
により見出される、装置。
【請求項１２】
前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、請求項１１に記載の装置。
【請求項１３】
前記映像デコーダは、圧縮されたシンボルをエントロピー復号して、埋め込み行列からの量子化されたサンプルのサブセットを提供するためのエントロピーデコーダと、前記量子化されたサンプルのサブセットを逆量子化して、前記埋め込み行列の復元されたバージョンからのサンプルのサブセットの近似値を提供するための逆量子化器と、前記埋め込み行列の前記復元されたバージョンの欠落した部分を決定して、前記埋め込み行列の完成した復元されたバージョンを提供するための行列完成デバイスと、前記埋め込み行列の前記完成した復元されたバージョンから前記運動行列の前記近似値を再構築するための再構築デバイスと、を備える、請求項１１に記載の装置。
【請求項１４】
前記埋め込み行列の前記復元されたバージョンの前記欠落した部分は、前記サンプルのサブセットの前記サンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の以前に破棄された部分に対応する、請求項１３に記載の装置。
【請求項１５】
運動行列の近似値を用いて映像シーケンスのピクチャを復号するステップを含み、前記運動行列は映像デコーダに前記運動行列および参照フレームを用いて前記ピクチャを一意的に再構築させることができるデータを有し、
前記運動行列の前記近似値は、所与の階数を有し、前記運動行列の列を積み上げることにより形成されるベクトルは、辞書と疎な表現との積からなり、
前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを前記映像デコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、非ゼロの残差値の数を最小化するために前記映像シーケンスの参照ピクチャの組から形成され、
前記運動行列は、
第１の表現を見出す第１のステップであって、前記辞書と前記第１の表現との積が、初期値が前記ピクチャである第１の行列の列を積み上げることにより形成されるベクトルである、前記第１のステップと、
前記第１の表現の大きい方から所与の数の成分だけを有する第２の表現を生成する第２のステップと、
第２の行列を作成する第３のステップであって、前記第２の行列の列を積み上げることにより形成されるベクトルは前記辞書と前記第２の表現との積である、前記第３のステップと、
前記第２の行列の大きい方から前記所与の階数と同じ数の固有値を有する第３の行列を生成する第４のステップと、
前記第１の表現がある特定のレベルに収束するまで、前記第１の行列を前記第３の行列に置き換えて前記第１のステップから前記第４のステップを繰り返し、前記第１の表現がある特定のレベルに収束したとき、前記第１の行列を前記運動行列とする、第５のステップと、
により見出される、前記映像デコーダにおける方法。
【請求項１６】
前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、請求項１５に記載の方法。
【請求項１７】
圧縮されたシンボルをエントロピー復号して、埋め込み行列からの量子化されたサンプルのサブセットを提供するステップと、
前記量子化されたサンプルのサブセットを逆量子化して、前記埋め込み行列の復元されたバージョンからのサンプルのサブセットの近似値を提供するステップと、
前記埋め込み行列の前記復元されたバージョンの欠落した部分を決定して、前記埋め込み行列の完成した復元されたバージョンを提供するステップと、
前記埋め込み行列の前記完成した復元されたバージョンから前記運動行列の前記近似値を再構築するステップと
をさらに含む、請求項１５に記載の方法。
【請求項１８】
前記埋め込み行列の前記復元されたバージョンの前記欠落した部分は、前記サンプルのサブセットの前記サンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の以前に破棄された部分に対応する、請求項１７に記載の方法。
【請求項１９】
前記運動行列の前記近似値は、前記埋め込み行列と、前記埋め込み行列を乗じた２つの行列とを用いて決定される、請求項１７に記載の方法。
【請求項２０】
前記埋め込み行列からの前記サンプルのサブセットの前記サンプルが前記映像デコーダおよび対応する映像エンコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が前記映像デコーダおよび前記対応する映像エンコーダによって使用される、請求項１７に記載の方法。
【請求項２１】
前記運動行列の疎な表現が、前記埋め込み行列の前記復元されたバージョンに対して決定され、前記ピクチャのベクトル化された形態が、前記疎な表現および前記辞書に応じて決定され、前記ベクトル化された形態は、前記ピクチャの再構築されたバージョンを得るために再整形される、請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本出願は、２０１０年１０月１４日に出願した米国仮出願第６１／３９３，１８６号の利益を主張するものであり、この仮出願は、参照によりその全体が本明細書に組み込まれる。
【０００２】
本原理は、概して、映像の符号化および復号に関し、より詳細には、運動行列を用いた映像の符号化および復号のための方法および装置に関する。
【背景技術】
【０００３】
映像コーデックは、デジタル映像に関する映像の圧縮および／または解凍を可能にするデバイスである。映像の品質と、その映像を表すために必要とされるデータの量（ビットレートとしても知られる）と、符号化アルゴリズムおよび復号アルゴリズムの複雑性と、データの損失および誤りに対する堅牢性と、編集の容易さと、ランダムアクセスと、最先端の圧縮アルゴリズムの設計と、エンドツーエンドの遅延と、いくつかのその他の要因との間には、複雑なバランスがある。
【０００４】
映像コーデックは、本来アナログであるデータセットをデジタルフォーマットで表そうとする。アナログ映像信号の設計は、輝度（ｌｕｍａ）の情報と色の情報とを別々に表すので、コーデック設計における画像データ圧縮の通常の最初のステップは、画像をＹＣｂＣｒ色空間で表し、記憶することである。ＹＣｂＣｒへの変換は、以下の２つの利点、すなわち、第１に、この変換が、色信号の相関をなくすことによって圧縮性を高めることと、第２に、この変換が、知覚する上で遥かに重要である輝度信号を、知覚する上で比較的重要でなく、比較的低い解像度で表され得る色差（ｃｈｒｏｍａ）信号から分離してより効率的なデータ圧縮を実現することとをもたらす。
【０００５】
復号プロセスは、符号化プロセスの各段階の逆変換を可能な限り実行することからなる。完全には可逆でない１つの段階は、量子化の段階である。この段階では、逆変換のベストエフォートの近似が行われる。プロセスのこの部分は、「逆量子化」と呼ばれることが多いが、量子化は本質的に非可逆プロセスである。
【０００６】
映像を符号化する従来の方法は、参照における単純な動きおよび何らかの残差に関してフレームを分解することを含む。図１に目を向けると、従来の符号化の方法が、全体的に参照番号１００によって示されている。符号化の方法１００は、符号化されるべきフレーム２（時間ｔ２におけるｆ２）と、（参照）フレーム１（時間ｔ１におけるｆ１）と、何らかの残差とを含む。フレーム２（時間ｔ２におけるｆ２）は、フレーム１（時間ｔ１におけるｆ１）に対する参照と残差とを用いて符号化される。ＩＳＯ／ＩＥＣ（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ  ｆｏｒ  Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ／Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｅｌｅｃｔｒｏｔｅｃｈｎｉｃａｌ  Ｃｏｍｍｉｓｓｉｏｎ）  ＭＰＥＧ−４（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ−４）  Ｐａｒｔ  １０  ＡＶＣ（Ａｄｖａｎｃｅｄ  Ｖｉｄｅｏ  Ｃｏｄｉｎｇ）規格／ＩＴＵ−Ｔ（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｕｎｉｏｎ，Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｅｃｔｏｒ）  Ｈ．２６４勧告（以降、「ＭＰＥＧ−４  ＡＶＣ規格」）などの従来のハイブリッド映像コーデックは、この原理に基づいている。ブロックがイントラ予測またはインター予測され、次いで、典型的な変換のプロセス、量子化、エントロピー符号化、および場合によっては何らかのフィルタリングが適用される。
【０００７】
映像の符号化は非常に幅広い分野であり、この主題に関して数十年に及ぶ研究がある。さまざまな技術が、映像の符号化に適用されてきた。最近登場した圧縮センシングは、この問題で使用するさらに別のツールをもたらした。例えば、１つの従来技術のアプローチにおいては、圧縮センシングが、データブロックを符号化するためのモードとして使用される。しかしながら、このアプローチは、やはり従来の方式に頼っており、圧縮センシングをシステムに付随的な方法として導入する。
【発明の概要】
【０００８】
従来技術のこれらのおよびその他の難点および欠点が、運動行列を用いた映像の符号化および復号のための方法および装置を対象とする本原理によって対処される。
【０００９】
本原理の一態様によれば、装置が提供される。この装置は、運動行列を用いて映像シーケンスのピクチャ（ｐｉｃｔｕｒｅ）を符号化するための映像エンコーダを含む。運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有する。辞書は、ピクチャを表すため、ならびにピクチャを対応するデコーダにおいてアトム（ａｔｏｍ）および基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの組を含む。辞書は、映像シーケンスの参照ピクチャの組から形成される。
【００１０】
本原理の別の態様によれば、映像エンコーダにおける方法が提供される。この方法は、運動行列を用いて映像シーケンスのピクチャを符号化するステップを含む。運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有する。辞書は、ピクチャを表すため、ならびにピクチャを対応するデコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの組を含む。辞書は、映像シーケンスの参照ピクチャの組から形成される。
【００１１】
本原理のさらに別の態様によれば、装置が提供される。この装置は、運動行列の近似値を用いて映像シーケンスのピクチャを復号するための映像デコーダを含む。運動行列の近似値は、所与の閾値未満の階数と、辞書に対する疎な表現とを有する。辞書は、ピクチャを表すため、ならびにピクチャを映像デコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの組を含む。辞書は、映像シーケンスの参照ピクチャの組から形成される。
【００１２】
本原理のさらに別の態様によれば、映像デコーダにおける方法が提供される。方法は、運動行列の近似値を用いて映像シーケンスのピクチャを復号するステップを含む。運動行列の近似値は、所与の閾値未満の階数と、辞書に対する疎な表現とを有する。辞書は、ピクチャを表すため、およびピクチャを映像デコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの組を含む。辞書は、映像シーケンスの参照ピクチャの組から形成される。
【００１３】
本原理のこれらのおよびその他の態様、特徴、および利点は、添付の図面に関連して読まれるべき例示的な実施形態の以下の詳細な説明から明らかになるであろう。
【図面の簡単な説明】
【００１４】
本原理は、以下の例示的な図にしたがってより深く理解され得る。
【図１】従来技術による従来の符号化の方法を示す図である。
【図２】本原理の一実施形態による、本原理が適用され得る例示的な映像エンコーダを示すブロック図である。
【図３】本原理の一実施形態による、本原理が適用され得る例示的な映像デコーダを示すブロック図である。
【図４】本原理の一実施形態による、運動行列のベクトル化の例示的な操作およびベクトル化操作の逆変換を示す図である。
【図５】本原理の一実施形態による、運動行列に基づく映像符号化方式を用いた符号化のための例示的な方法を示す流れ図である。
【図６】本原理の一実施形態による、運動行列に基づく映像符号化方式を用いた復号のための例示的な方法を示す流れ図である。
【図７】本原理の一実施形態による、運動行列を低階数の密行列Ｚに埋め込むための例示的な方法を示す図である。
【図８】本原理の一実施形態による、運動行列からのサンプリングおよび行列の完成のための例示的な方法を示す図である。
【図９】本原理の一実施形態による、対応する固有値が十分にランダムであるときの低階数の行列の完成の例を示す図である。
【図１０】本原理の一実施形態による、対応する固有値が十分にはランダムでないことが原因で失敗する低階数の行列の例を示す図である。
【図１１】本原理の一実施形態による、修正されたフレームｆｑ’の疎な表現の圧縮サンプル（ｃｏｍｐｒｅｓｓｉｖｅ  ｓａｍｐｌｅ）から形成された埋め込み行列（ｅｍｂｅｄｄｅｄ  ｍａｔｒｉｘ）Ｚの例を示す図である。
【発明を実施するための形態】
【００１５】
本原理は、運動行列を用いた映像の符号化および復号のための方法および装置を対象とする。
【００１６】
この説明は、本原理を示す。したがって、当業者が、本明細書においてはっきりと説明されていないかまたは示されていないが本原理を具現化し、本原理の精神および範囲に含まれるさまざまな構成を考案し得ることが理解される。
【００１７】
本明細書に記載のすべての例および条件を表す言い回しは、当技術分野を発展させるために（１人のまたは複数の）発明者によって与えられた本原理および概念を読者が理解することを助けるために教示を目的とするように意図されており、そのような具体的に記載された例および条件に限定されないものと解釈されるべきである。
【００１８】
さらに、本原理の原理、態様、および実施形態ならびにそれらの具体的な例を示す本明細書のすべての記述は、それらの構造的均等物と機能的均等物の両方を包含するように意図される。加えて、そのような均等物は、現在知られている均等物と将来開発された均等物の両方、すなわち、構造に関係なく同じ機能を実行する開発された任意の要素を含むことが意図される。
【００１９】
したがって、例えば、本明細書に示された構成図は、本原理を具現化する例示的な回路の概念図を表すことが当業者によって理解される。同様に、任意のフローチャート、流れ図、状態遷移図、擬似コードなどは、実質的にコンピュータ可読媒体中に表現される可能性があり、したがって、コンピュータまたはプロセッサが明示的に示されているか否かにかかわらずそのようなコンピュータまたはプロセッサによって実行される可能性があるさまざまなプロセスを表すことが理解される。
【００２０】
図に示されたさまざまな要素の機能は、専用のハードウェア、および適切なソフトウェアに関連してソフトウェアを実行することができるハードウェアを使用することによって提供され得る。プロセッサによって提供されるとき、それらの機能は、単一の専用プロセッサによって、単一の共有プロセッサによって、または一部が共有される可能性がある複数の個別的なプロセッサによって提供され得る。さらに、用語「プロセッサ」または「コントローラ」の明示的な使用は、ソフトウェアを実行することができるハードウェアを排他的に指すものと解釈されるべきでなく、デジタル信号プロセッサ（「ＤＳＰ」）ハードウェア、ソフトウェアを記憶するための読み出し専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、および不揮発性ストレージを限定することなしに暗黙的に含み得る。
【００２１】
通常のおよび／またはカスタムのその他のハードウェアも、含まれ得る。同様に、図に示された任意のスイッチは、概念的であるに過ぎない。それらのスイッチの機能は、プログラム論理の動作によって、専用の論理によって、プログラムの制御と専用の論理とのインタラクションによって、またはさらには手動でも実行される可能性があり、具体的な技術は、状況からより具体的に理解されるように実施者によって選択され得る。
【００２２】
本出願の請求項においては、指定された機能を実行するための手段として表された任意の要素は、例えば、ａ）その機能を実行する回路要素の組み合わせ、またはｂ）機能を実行するためにそのソフトウェアを実行するための適切な回路と組み合わされた任意の形態のソフトウェア、したがって、ファームウェア、マイクロコードなどを含むソフトウェアを含む、その機能を実行する任意の方法を包含するように意図される。そのような請求項によって定義される本原理は、さまざまな記載された手段によって提供される機能が、請求項が求めるように組み合わされ、まとめられるという事実に存する。したがって、それらの機能を提供することができる任意の手段は、本明細書に示された手段と均等であると見なされる。
【００２３】
本明細書における本原理の「一実施形態」との言及およびそのその他の変化形は、その実施形態に関連して説明された特定の特徴、構造、特性などが本原理の少なくとも１つの実施形態に含まれることを意味する。したがって、本明細書中のさまざまな場所に現れる表現「一実施形態において」および任意のその他の変化形が現れることは、必ずしもすべてが同じ実施形態に言及しているとは限らない。
【００２４】
例えば、「Ａ／Ｂ」、「Ａおよび／またはＢ」、および「ＡおよびＢのうちの少なくとも１つ」の場合の以下の「／」、「および／または」、および「〜のうちの少なくとも１つ」のいずれかの使用は、１番目に挙げられた選択肢（Ａ）のみの選択、または２番目に挙げられた選択肢（Ｂ）のみの選択、または両方の選択肢（ＡおよびＢ）の選択を包含するように意図されることを理解されたい。さらなる例として、「Ａ、Ｂ、および／またはＣ」および「Ａ、Ｂ、およびＣのうちの少なくとも１つ」の場合、そのような表現法は、１番目に挙げられた選択肢（Ａ）のみの選択、または２番目に挙げられた選択肢（Ｂ）のみの選択、または３番目に挙げられた選択肢（Ｃ）のみの選択、または１番目および２番目に挙げられた選択肢（ＡおよびＢ）のみの選択、または１番目および３番目に挙げられた選択肢（ＡおよびＣ）のみの選択、または２番目および３番目に挙げられた選択肢（ＢおよびＣ）のみの選択、または３つの選択肢のすべて（ＡおよびＢおよびＣ）の選択を包含するように意図される。これは、当業者にはすぐに分かるように、列挙される項目の数に合わせて拡張され得る。
【００２５】
また、本明細書において使用されるとき、語「ピクチャ」および「画像」は交換可能なように使用され、映像シーケンスからの静止画像またはピクチャを指す。知られているように、ピクチャは、フレームまたはフィールドである可能性がある。
【００２６】
図２に目を向けると、本原理が適用され得る例示的な映像エンコーダが、全体的に参照番号２００によって示されている。図２は、発明者の提案する映像の符号化のアプローチの中心的要素のみを含んでおり、デブロッキングフィルタ（ｄｅ−ｂｌｏｃｋｉｎｇ  ｆｉｌｔｅｒ）、予測などブロックによってさらに改善され得ることに留意することが重要である。映像エンコーダ２００は、運動行列生成器２２０の第１の入力に信号通信で接続された出力を有する辞書生成器２１０を含む。運動行列生成器２２０の出力は、行列エンベッダ２３０の入力に信号通信で接続される。行列エンベッダ２３０の出力は、サンプラ２４０の入力に信号通信で接続される。サンプラ２４０の出力は、量子化器２５０の入力に信号通信で接続される。量子化器２５０の出力は、エントロピーエンコーダ２６０の入力に信号通信で接続される。辞書生成器２１０の入力および運動行列生成器２２０の第２の入力は、参照フレームを受信するためのエンコーダ２００の入力として利用可能である。運動行列生成器２２０の第３の入力は、符号化されるべきフレームを受信するためのエンコーダ２００の入力として利用可能である。エントロピーエンコーダ２６０の出力は、符号化されたビットストリームを出力するためのエンコーダ２００の出力として利用可能である。
【００２７】
図３に目を向けると、本原理が適用され得る例示的な映像デコーダが、全体的に参照番号３００によって示されている。図３は、発明者の提案する映像の復号のアプローチの中心的要素のみを含んでおり、デブロッキングフィルタ、予測などブロックによってさらに改善され得ることに留意することが重要である。映像デコーダ３００は、逆量子化器３２０の入力に信号通信で接続された出力を有するエントロピーデコーダ３１０を含む。逆量子化器３２０の出力は、行列完成器３３０の入力に信号通信で接続される。行列完成器３３０の出力は、運動行列復元器３４０の入力に信号通信で接続される。運動行列復元器３４０の出力は、画像リコンストラクタ３５０の第１の入力に信号通信で接続される。辞書生成器３６０の出力は、画像リコンストラクタ３５０の第２の入力に信号通信で接続される。エントロピーデコーダ３１０の入力は、入力ビットストリームを受信するためのデコーダ３００の入力として利用可能である。辞書生成器３６０の入力は、参照フレームを受信するためのデコーダ３００の入力として利用可能である。画像リコンストラクタ３５０の出力は、１つまたは複数の再構築された画像を出力するためのデコーダ３００の出力として利用可能である。画像リコンストラクタ３５０は、参照フレームを受信するための１つまたは複数の追加的な入力を含む可能性がある。
【００２８】
上述のように、本原理は、運動行列を用いた映像の符号化および復号のための方法および装置を対象とする。
【００２９】
高い圧縮効率を実現するために、実質的にすべての映像符号化方式は、以下、すなわち、
（ａ）時間的相関、または連続するフレームの間の相関、および
（ｂ）空間的相関、つまりフレームおよび／またはピクチャ内の隣接するピクセル（もしくはそれ以外の状態で近くにあるピクセル）の間の相関
を利用する。
【００３０】
高い空間的相関は、（位置（ｉ，ｊ）のピクセル値が行列の第（ｉ，ｊ）成分に記憶される）行列の形態のＮ×Ｍピクセルのデジタル画像を考えた場合、その画像のピクセル値が強い相関を有し、独立していないことを意味する。数学的観点から、これは、対応する行列が低い階数または低い独立性を有することを意味する。一方、高い時間的相関は、特定の時間のフレームの多くの部分が、厳密にかまたはおおよそかのどちらかで前のフレームで（おそらく異なる位置で）発見され得ることを意味する。本原理によって、発明者は、圧縮センシングおよび低階数の行列の完成の数学的ツールを利用する新たなシステムを開発した。発明者は、この新しいアプローチを、高い時間的相関および空間的相関を利用して映像シーケンスを符号化するための代替的なアプローチを表す概念、「運動行列」と呼ぶ。
【００３１】
発明者は、運動行列の原理と、運動行列がどのようにして映像エンコーダおよびデコーダで実装されるかを開示し、説明する。さらに、提案される運動行列の例／実施形態が示され、対応するエンコーダ／デコーダのさまざまなコンポーネントが説明される。この方式は、本明細書に記載のいくつかの新たな符号化ブロックを含む。
【００３２】
また、説明を簡単にするために、普遍性を損なうことなく、本原理は１つの参照フレームのみが存在するＰフレームに関連して説明される。明らかに、この考え方は、複数の参照フレームの場合に容易に拡張可能である。
【００３３】
［概要］
本原理によって、発明者は、映像コンテンツを符号化および復号するためのシステムを説明する。説明を明瞭にするために特定の文脈および実施形態で説明されるが、本明細書に記載の同じ原理のうちの１つまたは複数を利用し、したがって本原理の範疇に入ることから除外されてはならないその他の実施形態は、当業者に明らかであろう。例えば、デコーダの圧縮センシングモジュールは、「基底追跡（ｂａｓｉｓ  ｐｕｒｓｕｉｔ）」アルゴリズムを用いて実現され得るが、同じ目的を達成することができる文献中のその他のよくあるアルゴリズム（およびその他の将来開発されたアルゴリズム）が存在し、それらのアルゴリズムは、本発明の包括的原理および範囲に含まれるように意図される。発明者は、基底追跡（ＢＰ）アルゴリズムが凸最適化問題を解くことを伴うことを強調する。より具体的には、ＢＰは、一次方程式の劣決定系ｙ＝Ｐｘに対する最小のＬ１ノルム（絶対値の総和）を用いて解を発見し、ここで、ｙの値および係数Ｐの行列が与えられており、ｘは未知のベクトルである。さらに、一次方程式の劣決定系によって、発明者は、式の数（ここではＰの行列の行の数）が未知数の数（未知のベクトルｘの長さ）未満であることを意味する。数学的形式で、ＢＰは以下の最適化問題を解く。  
ｙ＝ＰｘであるようなＡｒｇｍｉｎ｜｜ｘ｜｜１＝Σ｜ｘｉ｜
特定の条件の下で、ＢＰによって発見される解は最も疎な解、すなわち、最小数の非ゼロの数を有する解であることが証明されている。
【００３４】
映像シーケンスからの時間ｔ１における画像ｆ１を考える。この画像が、例えば図１に示されるように時間ｔ２においてｆ２に変化すると仮定する。大まかに言って、最も古典的な映像符号化方式においては、そのような動きは以下のように分解される。  
ｆ２＝Ｘ（ｆ１）＋Ｒ
ここで、Ｘ（．）は基本関数（ｂａｓｉｃ  ｆｕｎｃｔｉｏｎ）であり、Ｒは何らかの残差である。例えば、図１の例に関して、Ｘ（．）は、画像（ｆ１）を入力として受け取り、次いで、出力のためにその画像（ｆ１）を右に１ピクセルだけシフトする関数であり、Ｒは残差である。圧縮は、Ｘ（．）およびＲを効率的に符号化することによって達せられる。例に戻ると、Ｘ（．）は、動きベクトルとして符号化される可能性があり、Ｒは、離散コサイン変換（ＤＣＴ）などの変換領域でＲを表すことによって効率的に圧縮され得る。この符号化の包括的な枠組み、すなわち、参照フレームにおける何らかの動きおよび何らかの残差に関して画像を分解することは、時間的相関を広く利用して圧縮を行うことに留意されたい。空間的相関は、残差の変換符号化によっても利用される。一方、ＤＣＴ、ウェーブレットなどの利用可能な変換は、残差の代わりに、相関性の高い画像を希薄化する（疎にする）ように設計されている。言い換えると、変換を利用して残差を符号化することは過去うまくいっていたが、映像データを圧縮する能力をよりいっそう高めるために、将来開発される方式においては空間的相関が使用される可能性がある。
【００３５】
一次方程式の劣決定系およびさらに低階数の行列の完成の問題に関して最近生み出された成果を使用する、本発明の原理による、発明者が本明細書で説明する方法および装置は、代替的な符号化および復号方式を設計するために使用される。
【００３６】
［運動行列］
符号化されるべきフレーム（例えば、図１のｆ２）に関する運動行列は、行列Ｙである。デコーダは、運動行列および参照フレーム（例えば、ｆ１）を用いて符号化されたフレームを一意的に再構築することができる。さらに、運動行列は、以下の２つの追加的な重要な性質を有する。  
・運動行列は、低い階数を有する。言い換えると、Ｙの成分は相関性が高い。  
・運動行列は、符号化されるべきフレームの知識を必要とせずにデコーダにおいて導出され得る辞書ψ、すなわち、アトム／基底ベクトルの組（例えば、離散コサイン変換は画像を表現するための辞書である）に対する疎な表現αを有し、つまり、Ｖｅｃ（Ｙ）＝ψαであり、ここで、Ｖｅｃ（．）は、行列の列を積み上げることによって形成される行列のベクトル化された形態（図４参照）を表し、αは、要素のほとんどがゼロである疎なベクトルである。
【００３７】
ここで、発明者は、本明細書で導入された運動行列が、概念と、さらには圧縮を行うために選択されるアプローチとの両方において従来の研究の変位行列（ｄｉｓｐｌａｃｅｍｅｎｔ  ｍａｔｒｉｘ）および運動行列におけるそれから離れることを強調する必要がある。以下で、発明者は、重要な違いのうちのいくつかを明らかにする。  
・変位行列および従来の運動行列は、主として２値行列を利用する。一方、提案される運動行列の成分は、負数および浮動小数点数を含む任意の数を取り得る。  
・従来の研究の変位行列および運動行列の成分は、一部のブロックおよび／またはピクセルにおけるいくつかの種類の動きの存在を示す。一方、提案される運動行列の成分は、一部のブロックにおける動きを示すタスクに制限されない。例えば、提案される運動行列の成分は、フレーム全体におけるいくつかの全体的な動き（フレームにおけるすべての動きに応じて決まる値）を知らせる可能性がある。  
・従来の研究においては、参照フレームが与えられたとして、運動および／または変位行列は、通常、フレームを再構築するために十分でない。例えば、残差行列、またはデコーダ側での望ましい再構築のためのその他のシグナリングなどのオーバーヘッドデータを送信する必要がある可能性がある。発明者の方法は、単独で機能する運動行列を対象としており、参照フレームが与えられるとすれば、運動行列さえあれば、既に符号化されたフレームを妥当な誤差で近似するために十分である。  
・従来の運動行列および／または変位行列は、発明者の定義におけるすべての必要条件に（通常）反するので、それらの従来の運動行列および／または変位行列は、発明者の提案する運動行列の枠組みに入らない。例えば、斜線が数ピクセルだけ右または左にシフトするフレームまたはブロックを考える。そのとき、対応する変位行列はフルランク（最大のあり得る階数）の対角行列になることは容易に理解できる。さらに、そのような対角行列（つまり画像）は、ＤＣＴ、ウェーブレットなどの従来の変換の下では疎でない（これらの種類の行列に適した何らかの方向変換（ｄｉｒｅｃｔｉｏｎａｌ  ｔｒａｎｓｆｏｒｍ）が存在する可能性があるが、しかし、我々は、それらの変換／辞書のパラメータをデコーダに送信する必要があり、これは余計なオーバーヘッドを生じる）。したがって、従来の変位／運動行列は、運動行列に関する２つの必要条件（すなわち、低階数であることおよび希薄化領域（ｓｐａｒｓｉｆｙｉｎｇ  ｄｏｍａｉｎ）の存在）に容易に違反し得る。  
・別の違いが復号段階に現れる。より具体的には、従来の符号化の方法は、予測および残差の符号化を利用して圧縮を行う。一方、発明者は、行列の完成および（圧縮センシングを用いて）一次方程式の劣決定系を解くことなどの最近生み出された／解かれたアルゴリズム／問題を利用して同様の目的を達成する。
【００３８】
最後になるが、従来の変位行列および運動行列は、概して、異なるフレームの間の時間的相関に応じて決まり、フレーム内の隣接するピクセルの間の空間的相関には（反応するにしても）あまり左右されない。しかし、発明者の提案する運動行列は、映像コンテンツを圧縮するために時間的相関と空間的相関とを同時にまとめて考慮する。
【００３９】
図４に目を向けると、運動行列をベクトル化する例示的な操作と、ベクトル化操作の逆の操作とが、全体的に参照番号４００によって示されている。ベクトル化された形態が参照番号４１０によって示され、ベクトル化された形態の逆の形態が参照番号４２０によって示されている。
【００４０】
運動行列は、符号化されるべきフレームの（低階数の行列をもたらす）高い空間的相関と、（希薄化フレーム（ｓｐａｒｓｉｆｙｉｎｇ  ｆｒａｍｅ）の存在につながる）高い時間的相関とを一緒に利用することによって形成され得る。運動行列の形成は、上述のアプローチに限定されず、したがって、運動行列を形成するためのその他のアプローチも、本原理の精神を維持しながら、本明細書において与えられた本原理の教示にしたがって使用され得ることを理解されたい。
【００４１】
次に、運動行列に基づく映像符号化方式のための対応するエンコーダおよびデコーダを示す。
【００４２】
図５に目を向けると、運動行列に基づく映像符号化方式を用いた符号化のための例示的な方法が、全体的に参照番号５００によって示されている。方法５００は、機能ブロック５１０および機能ブロック５１５に制御を渡す開始ブロック５０５を含む。機能ブロック５１０は、参照｛ｆ１，．．．，ｆｑ−１｝フレームを入力し、機能ブロック５２０に制御を渡す。機能ブロック５２０は、符号化されるべきフレームがその辞書に対して疎である辞書を（例えば、参照フレームに基づいて）生成し、機能ブロック５２５に制御を渡す。機能ブロック５１５は、符号化されるべきフレームｆｑを入力し、機能ブロック５２５に制御を渡す。機能ブロック５２５は、運動行列を発見し、機能ブロック５３０に制御を渡す。機能ブロック５３０は、運動行列を、より圧縮しやすい（おそらくはより小さい）行列に埋め込み、機能ブロック５３５に制御を渡す。機能ブロック５３５は、埋め込み行列からサンプリングし（すなわち、成分のサブセットを残し、残りを破棄する）、機能ブロック５４０に制御を渡す。機能ブロック５４０は、埋め込み行列のサンプルを量子化し、機能ブロック５４５に制御を渡す。機能ブロック５４５は、埋め込み行列の量子化されたサンプルをエントロピー符号化し、機能ブロック５５０に制御を渡す。機能ブロック５５０は、埋め込み行列のエントロピー符号化されたサンプルを記憶および／または送信し、終了ブロック５９９に制御を渡す。
【００４３】
説明された運動行列に関する符号化の方法５００は、５つの主要な構成部分を含む。
【００４４】
１．符号化されるべきフレームおよび一連の参照フレームが与えられたとき、（符号化されるべきフレームがその辞書に対して疎である）辞書ψを形成し、運動行列Ｙを発見する。上述のように、運動行列Ｙおよび参照フレーム（および、したがって、希薄化辞書（ｓｐａｒｓｉｆｙｉｎｇ  ｄｉｃｔｉｏｎａｒｙ）ψ）があれば、デコーダは、符号化されたフレームを再構築することができる。
【００４５】
２．運動行列を、埋め込み行列Ｚ＝ｐ１Ｙｐ２に埋め込み、ここで、ｐ１およびｐ２は２つの行列である。設計によって、埋め込み行列Ｚは、さらなる圧縮を実現するために利用され得る運動行列のすべての望ましい性質、すなわち、低階数の性質と、その行列に関する希薄化基底（ｓｐａｒｓｉｆｙｉｎｇ  ｂａｓｉｓ）の存在とを受け継ぐことに留意されたい。配置された行列ｐ１およびｐ２も、我々が圧縮を行うのに役立つ可能性がある。例えば、ｐ１およびｐ２がそれぞれ幅が広い行列および高さが高い行列である場合、埋め込み行列Ｚは、運動行列よりも小さくなり、このことは、レベルの違う圧縮につながる。このステップの目的は、Ｚの多くの成分が支障なく破棄される可能性があり、その一方で、デコーダが破棄された成分を復元することができることを保証することである。さらに、このステップは、以降で示されるように、デコーダのステップ３および４が成功するために極めて重要である。行列ｐ１およびｐ２は、（ａ）Ｚ、ｐ１、およびｐ２があれば、我々が運動行列Ｙを再構築することができ、（ｂ）Ｚの固有ベクトルが十分にランダムであるように選択されることに留意することが重要である。例えば、ｐ１およびｐ２が、それぞれ、幅が広いランダム行列および高さが高いランダム行列である場合、埋め込み行列Ｚが運動行列Ｙよりも小さいとしても、上述の要件の両方が満たされる。行列ｐ１およびｐ２のそのようなランダムな選択は、圧縮の観点からすると最適なアプローチではない可能性がある。
【００４６】
３．サンプリング：埋め込み行列Ｚの成分の（おそらくはランダムな）サブセットＳを残し、残りの成分を破棄する。このステップは、我々が残差（または画像自体）の最も大きなＤＣＴ係数を残し、そのような重要度の大きい成分の値および位置をシグナリングする従来の映像方式の圧縮ステップを思わせると考える人もいるであろう。一方、発明者の方式のこのステップは、完全にランダムであり、埋め込み行列のどの成分もその他の成分と区別しない。結果として、エンコーダおよびデコーダが同じ乱数のシードおよび乱数生成器を使用する場合、それらのエンコーダおよびデコーダは、両方とも、Ｚの成分の位置について一致する。したがって、これらの成分の位置をシグナリングする必要はなく、エンコーダは、サンプル値を記憶／送信するだけである可能性がある。
【００４７】
４．埋め込み行列からのサンプルＳを
【００４８】
【数１】
0005908914.tif 000002
【００４９】
へと量子化する。明らかに、これは非可逆圧縮ステップである。しかし、このステップは、実質的にすべての圧縮技術に必須である。
【００５０】
５．埋め込み行列の量子化されたサンプル
【００５１】
【数２】
0005908914.tif 000003
【００５２】
を圧縮されたシンボルＣへとエントロピー符号化する。これらのシンボルＣは、記憶されるか、またはデコーダに送信される。
【００５３】
図６に目を向けると、運動行列に基づく映像符号化方式を用いた復号のための例示的な方法が、全体的に参照番号６００によって示されている。方法６００は、機能ブロック６１０および機能ブロック６４５に制御を渡す開始ブロック６０５を含む。機能ブロック６１０は、符号化されたシンボルＣを入力し、機能ブロック６１５に制御を渡す。機能ブロック６１５は、受信されたシンボルＣをエントロピー復号し、機能ブロック６２０に制御を渡す。機能ブロック６２０は、復号されたシンボルＣを逆量子化し、機能ブロック６２５に制御を渡す。機能ブロック６２５は、行列の完成を行い、機能ブロック６３０に制御を渡す。機能ブロック６３０は、埋め込み行列から運動行列を復元し、機能ブロック６３５に制御を渡す。機能ブロック６４５は、参照フレーム｛ｆ１，．．．，ｆｑ−１｝を入力し、機能ブロック６５０に制御を渡す。機能ブロック６５０は、辞書を生成し、機能ブロック６３５に制御を渡す。機能ブロック６３５は、運動行列を復号してｆｑを出力し、終了ブロック６９９に制御を渡す。
【００５４】
復号の方法６００は、５つの主要な構成部分を含む。
【００５５】
１．圧縮されたシンボルＣをエントロピー復号して、埋め込み行列Ｚの量子化されたサンプル
【００５６】
【数３】
0005908914.tif 000004
【００５７】
を得る。
【００５８】
２．サンプル
【００５９】
【数４】
0005908914.tif 000005
【００６０】
を逆量子化して、埋め込み行列のサンプルの近似値
【００６１】
【数５】
0005908914.tif 000006
【００６２】
を得る。
【００６３】
３．埋め込み行列Ｚの一部の成分の近似値
【００６４】
【数６】
0005908914.tif 000007
【００６５】
を得たとき、行列の完成を行うことによって、埋め込み行列Ｚの破棄された成分を復元する。このステップは、エンコーダで実行されたサンプリング（ステップ２）の逆の処理であることに留意されたい。非可逆な量子化のステップが原因で、破棄された成分が厳密に復元されないことが十分にあり得る。したがって、発明者は、この段階の出力を
【００６６】
【数７】
0005908914.tif 000008
【００６７】
と表記する。
【００６８】
４．（前のステップで復元された埋め込み行列）
【００６９】
【数９】
0005908914.tif 000009
【００７０】
から運動行列（の近似値）
【００７１】
【数８】
0005908914.tif 000010
【００７２】
を再構築する。運動行列が辞書ψに対して疎な表現αを有する（すなわち、
【００７３】
【数１０】
0005908914.tif 000011
【００７４】
）という事実を利用して一次方程式の（おそらくは劣決定の）系を形成する人もいるであろう。より具体的には、
【００７５】
【数１１】
0005908914.tif 000012
【００７６】
を得たとき、我々は、以下に対する解
【００７７】
【数１２】
0005908914.tif 000013
【００７８】
を見つける。
【００７９】
【数１３】
0005908914.tif 000014
【００８０】
この解は、（基底追跡または直交マッチング追跡（Ｏｒｔｈｏｇｏｎａｌ  Ｍａｔｃｈｉｎｇ  Ｐｕｒｓｕｉｔ）などの）圧縮センシングのデコーダを使用することによって発見され得る。結果として、運動行列（の近似値）は、
【００８１】
【数１４】
0005908914.tif 000015
【００８２】
によって推定可能であり、ここで、Ｖｅｃ−１（．）は、ベクトルを行列の形態に戻すように再整形する（図４参照）。辞書ψは符号化されたフレームとは無関係に決まり、したがって、デコーダ側でオーバーヘッドなしで、または極めて少ないオーバーヘッドで複製され得ることに留意することが重要である。
【００８３】
５．符号化されたフレームｆ２を再構築するためには、運動行列Ｙおよび参照フレームがあれば十分であると考えられる。したがって、我々は、（前のステップからの）元の運動行列の近似値
【００８４】
【数１５】
0005908914.tif 000016
【００８５】
および参照フレームを利用して（符号化されたフレームｆ２の近似値）
【００８６】
【数１６】
0005908914.tif 000017
【００８７】
を再構築することができる。
【００８８】
［エンコーダ］
本節では、運動行列の一実施形態の例が示される。また、そのような運動行列を符号化および復号するための必要とされるステップが、より詳細に与えられる。
【００８９】
［単純な運動行列］
我々は、参照フレームｆ１を利用することによってフレームｆ２を符号化したいものとする。上述のように、提案されるエンコーダの第１の段階は、運動行列Ｙを見つけることである。単純な形態の運動行列は、ｆ２（すなわち、符号化されるべきフレーム）の修正されたバージョンであり、したがって、
【００９０】
【数１７】
0005908914.tif 000018
【００９１】
によって表されるこの修正されたバージョンは、以下の３つの重要な性質を有する。
【００９２】
（ａ）Ｙは低階数である。
【００９３】
（ｂ）Ｙは、参照フレームと、おそらくはＤＣＴまたはウェーブレットなどのいくつかのその他の変換とから構築された過剰決定辞書（ｏｖｅｒ−ｃｏｍｐｌｅｔｅ  ｄｉｃｔｉｏｎａｒｙ）に対する疎な表現αを有する。
【００９４】
（ｃ）Ｙは、ｆ２（符号化されるべきフレーム）の優れた近似であり、すなわち、
【００９５】
【数１８】
0005908914.tif 000019
【００９６】
初めの２つの性質は、運動行列の要件であり、３つ目の性質は、運動行列および参照フレームから符号化されたフレームを推定する（デコーダのステップ５）必要がないことを示している。言い換えると、運動行列自体が、符号化されたフレームに極めて近く、直接表示され得る。
【００９７】
ここで、そのような運動行列を発見するための必要とされるステップについてさらに詳細に検討することにする。そのような運動行列を発見するための第１のステップは、運動行列
【００９８】
【数１９】
0005908914.tif 000020
【００９９】
がその辞書に対して疎になる辞書ψを生成することである。上述のように、この辞書は、参照フレームのみに応じて決まる（かつ符号化されるべきフレームとは無関係に決まる）。したがって、辞書は、デコーダ側で正確に複製され得る。例えば、この辞書は、参照フレームに対してさまざまな動き（さまざまな方向へのさまざまなシフト、回転、拡大など）またはいくつかの予測を計算することによって形成され得る。この辞書を拡張し、さらに、この辞書がすべてのあり得る画像を生成することができることを保証する（すなわち、この辞書がフルランクである）ために、いくつかの変換（例えば、ＤＣＴ、ウェーブレットなど）が辞書に追加され得る。適切に設計される場合、高い時間的相関が、符号化されるべきフレームがこの辞書に対する疎な表現を有することを保証することに留意されたい。
【０１００】
目標の希薄化辞書ψを形成した後、運動行列
【０１０１】
【数２０】
0005908914.tif 000021
【０１０２】
を発見することがまだ残っている。この運動行列は、以下の方法によって計算され得る。
【０１０３】
入力：希薄化辞書ψ、参照フレームｆ１、符号化されるべきフレームｆ２、目標の階数ｒ、および目標の疎性（ｓｐａｒｓｉｔｙ）ｋ
出力：運動行列Ｙ
初期化Ｙ＝ｆ２
ｄｏ｛
・ψに対するＹの表現αを見つける：
Ｖｅｃ（Ｙ）＝ψα
・
【０１０４】
【数２１】
0005908914.tif 000022
【０１０５】
が、αの大きい方からｋ個の成分だけを残し、残りのインデックス（ｉｎｄｅｘ）のところはゼロとすることによって計算されたベクトルであるものとする
・Ｙを
【０１０６】
【数２２】
0005908914.tif 000023
【０１０７】
に更新する。
・Ｙの大きい方からｒ個の固有値を残し、残りの固有値をゼロに設定する
｝収束するか、または誤差が十分に小さくなるまで繰り返す
【０１０８】
基本的に、この方法は、２つの制約、つまり、（ａ）出力行列Ｙが階数ｒを有することと、（ｂ）出力行列Ｙが辞書ψに対する疎性ｋの表現を有することとの間で繰り返される。以下のようないくつかの注意点を強調しておくことが重要である。
・ｋおよびｒを調整することにより、圧縮の量を制御する。具体的には、ｒおよびｋが増加するにつれて、デコーダで再構築される運動行列の品質が高くなり、その代償として圧縮幅は少なくなり、その逆も同様である。
・高い空間的相関は、運動行列
【０１０９】
【数２３】
0005908914.tif 000024
【０１１０】
の品質の急激な落ち込みを招くことなく、符号化されるべきフレームの階数（ｒ）を大幅に低くすることを可能にする。
・高い時間的相関は、符号化されるべきフレームｆ２が辞書ψのほんの数個（ｋ個）のアトムを用いて近似されることを可能にする。
【０１１１】
［行列の埋め込み］
修正されたフレーム（つまり運動行列）
【０１１２】
【数２４】
0005908914.tif 000025
【０１１３】
を得て、行列ｐ１およびｐ２を利用することにより、我々は、ｆ２を
【０１１４】
【数２５】
0005908914.tif 000026
【０１１５】
に埋め込む。ここで、第１の行列ｐ１は幅が広い行列であり、一方、第２の行列ｐ２は高さが高い行列である。さらに、行列ｐ１およびｐ２は、埋め込み行列Ｚ、ｐ１、およびｐ２があれば、我々が
【０１１６】
【数２６】
0005908914.tif 000027
【０１１７】
を復元できるように選択される。例えば、ｐ１およびｐ２はランダム行列である可能性があるが、ただし、そのような選択は最適な選択ではない。図７に目を向けると、運動行列を低階数の密行列Ｚに埋め込むための例示的な方法が、全体的に参照番号７００によって示されている。方法７００は、低階数の運動行列を、別の、低階数であるがよりコンパクトな埋め込み行列Ｚ  ７２０へと圧縮するために使用されるランダムで密な行列ｐ１  ７０５、（低階数の）運動行列７１０、およびランダムで密な行列ｐ２  ７１５を含む。行列の埋め込みの役割と、さらに行列ｐ１およびｐ２の役割とは、デコーダの説明に関連してより詳細に検討される。行列Ｚは、（最高でも運動行列の階数に等しい）低階数であることに留意されたい。さらに重要なことに、行列Ｚは、符号化されるべきフレームｆ２またはフレームｆ２の修正／再構築されたバージョン、つまり
【０１１８】
【数２７】
0005908914.tif 000028
【０１１９】
よりも少ない成分を有する。
【０１２０】
したがって、これは、提案される方法の最初のレベルの圧縮である。明らかに、このステップで実現され得る圧縮のレベルにはいくつかの制限がある。より具体的には、行列Ｚの成分の数は、前のステップのｋおよびｒに直接的に応じて決まる。これらの実施形態においては、ｋおよびｒの異なる値が使用される可能性があり、またはこれらの値がフレームｆ２もしくは行列Ｚの特性に適応的である可能性があることに留意されたい。
【０１２１】
［サンプリング］
埋め込み行列Ｚの比較的小さなランダムなサブセット（Ｓ）のみを残し、残りの成分を破棄することによって、レベルの違う圧縮が実現される。図８に目を向けると、運動行列からのサンプリングおよび行列の完成のための例示的な方法が、全体的に参照番号８００によって示されている。方法８００は、低階数で密な埋め込み行列８０５および低階数で密な埋め込み行列８１０を含む。デコーダおよびエンコーダが同じ乱数のシードおよび乱数生成器を使用する場合、成分の値Ｓのみが送信され、デコーダとエンコーダの両方はこれらの成分の位置が分かり、このことは（インデックスが送信されないので）さらなる圧縮をもたらす。
【０１２２】
［量子化およびエントロピー符号化］
前の段階からの埋め込み行列Ｚの成分のランダムなサブセット（Ｓ）は、量子化され、最終的な圧縮されたシンボルＣを得るためにエントロピーコーダに通される。
【０１２３】
デコーダ
デコーダのさまざまなコンポーネントが、本明細書において既に導入された基本的な運動行列の場合について示され、説明される。
【０１２４】
［逆量子化およびエントロピー復号］
最も古典的な映像符号化方式と同様に、デコーダの第１の段階は、圧縮されたシンボルＣを復号し、復号されたシンボルを逆量子化して、埋め込み行列Ｚの成分のランダムなサブセットの近似値
【０１２５】
【数２８】
0005908914.tif 000029
【０１２６】
を得る。
【０１２７】
［行列の完成］
最近、非常に関心の高い問題、具体的には、「低階数の行列の完成」が、いくつかの条件の下である程度まで解かれた。大まかに言って、この問題は、我々は、低階数の行列があり、その行列の成分のサブセットのみを見ることができるとして、見えない成分を近似することができるのかという疑問に対応する。もちろん、この疑問に対応する答えは、その行列による。図９に目を向けると、対応する固有ベクトルが十分にランダムであるときの低階数の行列の完成の例が、全体的に参照番号９００によって示されている。図１０に目を向けると、対応する固有ベクトルが十分にはランダムでないことが原因で失敗する低階数の行列の例が、全体的に参照番号１０００によって示されている。したがって、例えば、例９００に関して、我々が基礎となる行列が低階数であると確信している場合、欠けている成分は、第２列が第１列の３倍であるので６である。一方、例１０００に関しては、欠けている成分は、任意の数である可能性があり、推定し得ない。いくつかの条件が満たされる場合、例えば、低階数の行列の固有ベクトルが十分にランダムである場合、低階数の行列の完成は容易に解くことができることが示されており、特異値閾値法（Ｓｉｎｇｕｌａｒ  Ｖａｌｕｅ  Ｔｈｒｅｓｈｏｌｄｉｎｇ）（ＳＶＴ）、不動点連続法（Ｆｉｘｅｄ  Ｐｏｉｎｔ  Ｃｏｎｔｉｎｕａｔｉｏｎ）（ＦＰＣ）などのいくつかのアルゴリズムが、この問題を解くために提案されている。
【０１２８】
今や、埋め込みのステップおよび行列ｐ１およびｐ２の役割は、明らかであるに違いない。特に、これらの行列は、埋め込み行列Ｚの固有ベクトルが十分にランダムであることを保証する。したがって、そのような行列の多くの成分が、圧縮を行うために破棄される可能性がある一方、いくつかの行列完成アルゴリズムが、それらの破棄された成分を復元することができる。埋め込み行列（Ｚ）が低階数であるという事実を利用して、サンプルの近似値
【０１２９】
【数２９】
0005908914.tif 000030
【０１３０】
が、Ｚの欠落した成分（図８参照）を復元するために行列完成アルゴリズムに入力として与えられる。復元された行列
【０１３１】
【数３０】
0005908914.tif 000031
【０１３２】
は、埋め込み行列（Ｚ）と等しくない可能性があることに留意されたい。これは、量子化ステップからの誤差の伝播
【０１３３】
【数３１】
0005908914.tif 000032
【０１３４】
が原因である。しかし、推定誤差
【０１３５】
【数３２】
0005908914.tif 000033
【０１３６】
（ここで、｜｜．｜｜Ｆはフロベニウス行列ノルムを表す）は、量子化ステップで生じた誤差に比例する。
【０１３７】
［一次方程式の劣決定系を解く］
運動行列
【０１３８】
【数３３】
0005908914.tif 000034
【０１３９】
、つまり、符号化されるべきフレームの修正されたバージョンは、参照フレームに基づいて構築された辞書ψに対する疎な表現を（近似的に）有し、すなわち、Ｖｅｃ（Ｙ）＝ψαであることを思い出されたい。埋め込み運動行列
【０１４０】
【数３４】
0005908914.tif 000035
【０１４１】
のベクトル化された形態は、以下によって表現し直され得ることにも留意されたい。
【０１４２】
【数３５】
0005908914.tif 000036
【０１４３】
ここで、
【０１４４】
【数３６】
0005908914.tif 000037
【０１４５】
は、クロネッカーテンソル積であり、Ｖｅｃ（．）は、行列のベクトル化された形態を表す（図１１参照）。図１１に目を向けると、修正されたフレームｆｑ’の疎な表現の圧縮サンプルから形成された埋め込み行列Ｚの例が、全体的に参照番号１１００によって示されている。埋め込み行列Ｚは
【０１４６】
【数３７】
0005908914.tif 000038
【０１４７】
に比べて少ない数の成分を有するので、したがって、（１）は、埋め込み行列Ｚの成分が等式であり、αの成分が未知である一次方程式の劣決定系である。最近生み出された圧縮センシング（ＣＳ）の理論は、解が疎であるとき、一次方程式の劣決定系の解が、特定の条件の下で容易に計算され得ることを示した。ここで、行列ｐ１およびｐ２の役割は、これらの条件を満たしやすくすることである。ゆえに、
【０１４８】
【数３８】
0005908914.tif 000039
【０１４９】
（Ｚの近似値）があれば、疎なベクトルαは、通常のＣＳデコーダによって、例えば、「基底追跡」のアルゴリズムを用いることにより復元され得る。その他の実施形態においては、本原理の精神を維持しながら、疎なベクトルを復元するためのその他の方法が使用され得る。
【０１５０】
結果として、運動行列のベクトル化された形態は、以下によって復元され得る。
Ｖｅｃ（Ｙ）＝ψα
運動行列のベクトル化された形態を再整形することにより、我々は運動行列を得る。しかし、この例において、我々は、運動行列が符号化されたフレームの優れた近似であると仮定した。したがって、運動行列および参照フレームから符号化されたフレームを推定する必要はなく、我々は、導出された運動行列をそのまま表示することができる。
【０１５１】
一部が上で説明された本発明に付随する多くの利点／特徴のうちのいくつかが、以下で説明される。例えば、１つの利点／特徴は、運動行列を用いて映像シーケンスのピクチャを符号化するための映像エンコーダを有する装置である。運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有する。辞書は、ピクチャを表すため、およびピクチャがその組のみを用いて対応するデコーダにおいて導出されることを可能にするためのアトムおよび基底ベクトルの組を含む。辞書は、映像シーケンスの参照ピクチャの組から形成される。
【０１５２】
別の利点／特徴は、上述のように映像エンコーダを有する装置であり、辞書は、ピクチャと参照ピクチャの組との間の空間的相関および時間的相関から形成される。
【０１５３】
さらに別の利点／特徴は、上述のように映像エンコーダを有する装置であり、映像エンコーダは、埋め込み行列に運動行列を埋め込むための埋め込みデバイスと、埋め込み行列をサンプリングして埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを含む。
【０１５４】
さらに別の利点／特徴は、上述のように、映像エンコーダが、埋め込み行列に運動行列を埋め込むための埋め込みデバイスと、埋め込み行列をサンプリングして埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを含む、映像エンコーダを有する装置であり、埋め込み行列は、運動行列を乗じた２つの行列を用いて決定され、２つの行列は、埋め込み行列のランダムな固有ベクトルの閾値の量を与えるように選択される。
【０１５５】
さらに、別の利点／特徴は、上述のように、映像エンコーダが、埋め込み行列に運動行列を埋め込むための埋め込みデバイスと、埋め込み行列をサンプリングして埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを含む、映像エンコーダを有する装置であり、サンプルのサブセットは、埋め込み行列からランダムに選択される。
【０１５６】
さらに、別の利点／特徴は、上述のように、サンプルのサブセットが、埋め込み行列からランダムに選択される、映像エンコーダを有する装置であり、埋め込み行列からのサンプルのサブセットのサンプルが映像エンコーダおよび対応する映像デコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が映像エンコーダおよび対応する映像デコーダによって使用される。
【０１５７】
さらに、別の利点／特徴は、上述のように、映像エンコーダが、埋め込み行列に運動行列を埋め込むための埋め込みデバイスと、埋め込み行列をサンプリングして埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを含む、映像エンコーダを有する装置であり、前記サンプラは、サンプルのサブセットのサンプルと異なる埋め込み行列内の位置にある埋め込み行列の部分を破棄する。
【０１５８】
本原理のこれらのおよびその他の特徴および利点は、本明細書の教示に基づいて当業者によって容易に確認され得る。本原理の教示は、さまざまな形態のハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、またはこれらの組み合わせで実装され得ることを理解されたい。
【０１５９】
最も好ましくは、本原理の教示は、ハードウェアとソフトウェアの組み合わせとして実装される。さらに、ソフトウェアは、プログラムストレージユニットに有形で具現化されるアプリケーションプログラムとして実装され得る。アプリケーションプログラムは、任意の好適なアーキテクチャを備える機械にアップロードされ、そのような機械によって実行され得る。好ましくは、機械は、１つまたは複数の中央演算処理装置（「ＣＰＵ」）、ランダムアクセスメモリ（「ＲＡＭ」）、および入力／出力（「Ｉ／Ｏ」）インターフェースなどのハードウェアを有するコンピュータプラットフォーム上に実装される。また、コンピュータプラットフォームは、オペレーティングシステムおよびマイクロ命令コードを含み得る。本明細書において説明されたさまざまなプロセスおよび機能は、ＣＰＵによって実行され得るマイクロ命令コードの一部かもしくはアプリケーションプログラムの一部かのどちらか、またはそれらの任意の組み合わせである可能性がある。加えて、追加的なデータストレージユニットおよび印刷ユニットなどのさまざまなその他の周辺ユニットが、コンピュータプラットフォームに接続され得る。
【０１６０】
添付の図面に示された構成要素のシステムコンポーネントおよび方法の一部はソフトウェアで実装されることが好ましいので、システムコンポーネントまたはプロセスの機能ブロックの間の実際の接続は、本原理がプログラムされる方法によって変わり得ることをさらに理解されたい。本明細書の教示が与えられれば、当業者は、本原理のこれらのおよび同様の実装または構成を考えることができる。
【０１６１】
例示的な実施形態が添付の図面を参照して本明細書において説明されたが、本原理はそれらの厳密な実施形態に限定されず、さまざまな変更および修正が、本原理の範囲または精神を逸脱することなく当業者によってそれらの実施形態で行われ得ることを理解されたい。すべてのそのような変更および修正は、添付の特許請求の範囲に記載された本原理の範囲に入るように意図される。
（付記１）
運動行列を用いて映像シーケンスのピクチャを符号化するための映像エンコーダを備え、
前記運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを対応するデコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、装置。
（付記２）
前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、付記１に記載の装置。
（付記３）
前記映像エンコーダは、埋め込み行列に前記運動行列を埋め込むための埋め込みデバイスと、前記埋め込み行列をサンプリングして前記埋め込み行列からのサンプルのサブセットを提供するためのサンプラと、前記サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するための量子化器と、前記量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するためのエントロピーコーダとを備える、付記１に記載の装置。
（付記４）
前記埋め込み行列は、前記運動行列を乗じた２つの行列を用いて決定され、前記２つの行列は、前記埋め込み行列のランダムな固有ベクトルの閾値の量を与えるように選択される、付記３に記載の装置。
（付記５）
前記サンプルのサブセットは、前記埋め込み行列からランダムに選択される、付記３に記載の装置。
（付記６）
前記埋め込み行列からの前記サンプルのサブセットのサンプルが前記映像エンコーダおよび対応する映像デコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が前記映像エンコーダおよび前記対応する映像デコーダによって使用される、付記５に記載の装置。
（付記７）
前記サンプラは、前記サンプルのサブセットのサンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の部分を破棄する、付記３に記載の装置。
（付記８）
運動行列を用いて映像シーケンスのピクチャを符号化するステップを含み、
前記運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを対応するデコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、映像エンコーダにおける方法。
（付記９）
前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、付記８に記載の方法。
（付記１０）
前記符号化するステップは、埋め込み行列に前記運動行列を埋め込むステップと、
前記埋め込み行列をサンプリングして前記埋め込み行列からのサンプルのサブセットを提供するステップと、前記サンプルのサブセットを量子化して量子化されたサンプルのサブセットを提供するステップと、前記量子化されたサンプルのサブセットを圧縮されたシンボルにエントロピー符号化するステップとを含む、付記８に記載の方法。
（付記１１）
前記埋め込み行列は、前記運動行列を乗じた２つの行列を用いて決定され、前記２つの行列は、前記埋め込み行列のランダムな固有ベクトルの閾値の量を与えるように選択される、付記１０に記載の方法。
（付記１２）
前記サンプルのサブセットは、前記埋め込み行列からランダムに選択される、付記１０に記載の方法。
（付記１３）
前記埋め込み行列からの前記サンプルのサブセットのサンプルが前記映像エンコーダおよび対応する映像デコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が前記映像エンコーダおよび前記対応する映像デコーダによって使用される、付記１２に記載の方法。
（付記１４）
前記サンプリングするステップは、前記サンプルのサブセットのサンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の部分を破棄するステップを含む、付記１０に記載の方法。
（付記１５）
運動行列の近似値を用いて映像シーケンスのピクチャを復号するための映像デコーダを備え、前記運動行列の前記近似値は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを前記映像デコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、装置。
（付記１６）
前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、付記１５に記載の装置。
（付記１７）
前記映像デコーダは、圧縮されたシンボルをエントロピー復号して、埋め込み行列からの量子化されたサンプルのサブセットを提供するためのエントロピーデコーダと、前記量子化されたサンプルのサブセットを逆量子化して、前記埋め込み行列の復元されたバージョンからのサンプルのサブセットの近似値を提供するための逆量子化器と、前記埋め込み行列の前記復元されたバージョンの欠落した部分を決定して、前記埋め込み行列の完成した復元されたバージョンを提供するための行列完成デバイスと、前記埋め込み行列の前記完成した復元されたバージョンから前記運動行列の前記近似値を再構築するための再構築デバイスとを備える、付記１５に記載の装置。
（付記１８）
前記埋め込み行列の前記復元されたバージョンの前記欠落した部分は、前記サンプルのサブセットのサンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の以前に破棄された部分に対応する、付記１７に記載の装置。
（付記１９）
前記運動行列の前記近似値は、前記埋め込み行列と、前記埋め込み行列の行列を乗じた２つの行列とを用いて決定される、付記１７に記載の装置。
（付記２０）
前記埋め込み行列からの前記サンプルのサブセットのサンプルが前記映像デコーダおよび対応する映像エンコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が前記映像デコーダおよび前記対応する映像エンコーダによって使用される、付記１７に記載の装置。
（付記２１）
前記運動行列の疎な表現が、前記埋め込み行列の前記復元されたバージョンに対して決定され、前記ピクチャのベクトル化された形態が、前記疎な表現および前記辞書に応じて決定され、前記ベクトル化された形態は、前記ピクチャの再構築されたバージョンを得るために再整形される、付記１５に記載の装置。
（付記２２）
運動行列の近似値を用いて映像シーケンスのピクチャを復号するステップを含み、
前記運動行列の前記近似値は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを映像デコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、前記映像デコーダにおける方法。
（付記２３）
前記辞書は、前記ピクチャと参照ピクチャの前記組との間の空間的相関および時間的相関から形成される、付記２２に記載の方法。
（付記２４）
圧縮されたシンボルをエントロピー復号して、埋め込み行列からの量子化されたサンプルのサブセットを提供するステップと、
前記量子化されたサンプルのサブセットを逆量子化して、前記埋め込み行列の復元されたバージョンからのサンプルのサブセットの近似値を提供するステップと、
前記埋め込み行列の前記復元されたバージョンの欠落した部分を決定して、前記埋め込み行列の完成した復元されたバージョンを提供するステップと、
前記埋め込み行列の前記完成した復元されたバージョンから前記運動行列の前記近似値を再構築するステップと
をさらに含む、付記２２に記載の方法。
（付記２５）
前記埋め込み行列の前記復元されたバージョンの前記欠落した部分は、前記サンプルのサブセットのサンプルと異なる前記埋め込み行列内の位置にある前記埋め込み行列の以前に破棄された部分に対応する、付記２４に記載の方法。
（付記２６）
前記運動行列の前記近似値は、前記埋め込み行列と、前記埋め込み行列を乗じた２つの行列とを用いて決定される、付記２４に記載の方法。
（付記２７）
前記埋め込み行列からの前記サンプルのサブセットのサンプルが前記映像デコーダおよび対応する映像エンコーダにおいて同じそれぞれの位置にあることを保証するために、同じ乱数のシードおよび同じ乱数生成器が前記映像デコーダおよび前記対応する映像エンコーダによって使用される、付記２４に記載の方法。
（付記２８）
前記運動行列の疎な表現が、前記埋め込み行列の前記復元されたバージョンに対して決定され、前記ピクチャのベクトル化された形態が、前記疎な表現および前記辞書に応じて決定され、前記ベクトル化された形態は、前記ピクチャの再構築されたバージョンを得るために再整形される、付記２２に記載の方法。
（付記２９）
符号化された映像信号データをその中に有するコンピュータ可読ストレージ媒体であって、
運動行列を用いて符号化された、映像シーケンスのピクチャを含み、
前記運動行列は、所与の閾値未満の階数と、辞書に対する疎な表現とを有し、前記辞書は、前記ピクチャを表すため、ならびに前記ピクチャを対応するデコーダにおいてアトムおよび基底ベクトルの組だけを用いて導出することを可能にするためのアトムおよび基底ベクトルの前記組を含み、前記辞書は、前記映像シーケンスの参照ピクチャの組から形成される、コンピュータ可読ストレージ媒体。
【図１】
0005908914.tif 000040
【図２】
0005908914.tif 000041
【図３】
0005908914.tif 000042
【図４】
0005908914.tif 000043
【図５】
0005908914.tif 000044
【図６】
0005908914.tif 000045
【図７】
0005908914.tif 000046
【図８】
0005908914.tif 000047
【図９】
0005908914.tif 000048
【図１０】
0005908914.tif 000049
【図１１】
0005908914.tif 000050