ビデオシーケンス中のピクチャのプルーニングされたバージョンを複数の重なり合わないブロックに分割する分割器115と、前記ピクチャの前記プルーニングされたバージョンを回復する際に使用されるメタデータを復号するメタデータデコーダ125と、前記ピクチャの再構築バージョンからパッチライブラリを作成するパッチライブラリ作成器130であって、前記パッチライブラリは、前記ピクチャの前記プルーニングされたバージョンの回復中に前記1つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含んでいる前記パッチライブラリ作成器と、前記メタデータを用いた探索プロセスを実行して、前記複数の重なり合わないブロックのうちの前記1つまたは複数のプルーニングされたブロックのそれぞれ1つに対応するパッチを見つけ、前記1つまたは複数のプルーニングされたブロックの前記それぞれ1つを前記対応するパッチで置換する探索及び置換装置120と、を含む装置。前記1つまたは複数のプルーニングされたブロック中の全ての画素が、同じ色値または低解像度の一方を有する、請求項1に記載の装置。前記1つまたは複数のプルーニングされたブロックのうちの特定の1つに関する前記同じ色値が、前記1つまたは複数のプルーニングされたブロックのうちの前記特定の1つの中の前記画素の色値の平均に等しい、請求項2に記載の装置。前記パッチライブラリに含まれる前記複数の高解像度パッチの各々について、前記複数の高解像度パッチのそれぞれ1つの平均色を含む特徴ベクトルをそれぞれ生成することによって、署名をそれぞれ作成する、請求項1に記載の装置。前記複数の高解像度パッチの前記それぞれ1つの前記特徴ベクトルに含まれる前記平均色は、さらに、前記複数の高解像度パッチの前記それぞれ1つに対する周囲画素の平均色である、請求項4に記載の装置。前記署名は、前記1つまたは複数のプルーニングされたブロックの各々について作成され、前記ピクチャの前記プルーニングされたバージョンは、前記複数の高解像度パッチの各々の署名から前記1つまたは複数のプルーニングされたブロックの各々の署名までのそれぞれの距離メトリクスを比較し、前記それぞれの距離メトリクスを分類して前記1つまたは複数のプルーニングされたブロックの各々についてのランクリストを取得することによって回復され、前記1つまたは複数のプルーニングされたブロックのうちの特定の1つについての前記ランクリスト中のランク番号が、前記1つまたは複数のプルーニングされたブロックのうちの前記特定の1つを置換するために使用される、前記パッチライブラリ中の前記複数の高解像度パッチのうちの対応する1つを取り出すことに使用される、請求項1に記載の装置。前記複数の重なり合うブロックのうちの前記対応する1つに対して同じ位置にあるパッチより先行するパッチのみが、前記比較に使用される、請求項6に記載の装置。複数のノードおよび複数のエッジを有するパッチ依存性グラフを使用して前記ピクチャの前記プルーニングされたバージョンを回復し、前記複数のノードの各々が前記複数の重なり合わないブロックのそれぞれ1つを表し、前記複数のエッジの各々が前記複数の重なり合わないブロックの少なくとも前記それぞれ1つのそれぞれの依存性を表している、請求項6に記載の装置。前記メタデータは、前記複数の重なり合わないブロックの各々についてのベストマッチングパッチを識別するパッチ指標と、前記複数の重なり合わないブロックのうちの1つまたは複数のプルーニングされたブロックを識別するブロック識別子とを含む、請求項1に記載の装置。ビデオシーケンス中のピクチャのプルーニングされたバージョンを複数の重なり合わないブロックに分割するステップ2105と、前記ピクチャの前記プルーニングされたバージョンを回復する際に使用されるメタデータを復号するステップ2115と、前記ピクチャの再構築バージョンからパッチライブラリを作成するステップ130であって、前記パッチライブラリは、前記ピクチャの前記プルーニングされたバージョンの回復中に前記1つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含んでいる前記ステップと、前記メタデータを用いた探索プロセスを実行して、前記複数の重なり合わないブロックのうちの前記1つまたは複数のプルーニングされたブロックのそれぞれ1つに対応するパッチを見つけ、前記1つまたは複数のプルーニングされたブロックの前記それぞれ1つを前記対応するパッチで置換するステップ2110と、を含む方法。前記1つまたは複数のプルーニングされたブロック中の全ての画素が、同じ色値または低解像度の一方を有する、請求項10に記載の方法。前記1つまたは複数のプルーニングされたブロックのうちの特定の1つに関する前記同じ色値が、前記1つまたは複数のプルーニングされたブロックのうちの前記特定の1つの中の前記画素の色値の平均に等しい、請求項11に記載の方法。前記パッチライブラリに含まれる前記複数の高解像度パッチの各々について、前記複数の高解像度パッチのそれぞれ1つの平均色を含む特徴ベクトルをそれぞれ生成することによって、署名をそれぞれ作成する、請求項10に記載の方法。前記複数の高解像度パッチの前記それぞれ1つの前記特徴ベクトルに含まれる前記平均色は、さらに、前記複数の高解像度パッチの前記それぞれ1つに対する周囲画素の平均色である、請求項13に記載の方法。前記署名は、前記1つまたは複数のプルーニングされたブロックの各々について作成され、前記ピクチャの前記プルーニングされたバージョンは、前記複数の高解像度パッチの各々の署名から前記1つまたは複数のプルーニングされたブロックの各々の署名までのそれぞれの距離メトリクスを比較し、前記それぞれの距離メトリクスを分類して前記1つまたは複数のプルーニングされたブロックの各々についてのランクリストを取得することによって回復され、前記1つまたは複数のプルーニングされたブロックのうちの特定の1つについての前記ランクリスト中のランク番号が、前記1つまたは複数のプルーニングされたブロックのうちの前記特定の1つを置換するために使用される、前記パッチライブラリ中の前記複数の高解像度パッチのうちの対応する1つを取り出すことに使用される、請求項10に記載の方法。前記複数の重なり合うブロックのうちの前記対応する1つに対して同じ位置にあるパッチより先行するパッチのみが、前記比較に使用される、請求項15に記載の方法。複数のノードおよび複数のエッジを有するパッチ依存性グラフを使用して前記ピクチャの前記プルーニングされたバージョンを回復し、前記複数のノードの各々が前記複数の重なり合わないブロックのそれぞれ1つを表し、前記複数のエッジの各々が前記複数の重なり合わないブロックの少なくとも前記それぞれ1つのそれぞれの依存性を表している、請求項15に記載の方法。前記メタデータは、前記複数の重なり合わないブロックの各々についてのベストマッチンぐパッチを識別するパッチ指標と、前記複数の重なり合わないブロックのうちの1つまたは複数のプルーニングされたブロックを識別するブロック識別子とを含む、請求項10に記載の方法。ビデオシーケンス中のピクチャのプルーニングされたバージョンを複数の重なり合わないブロックに分割する手段115と、前記ピクチャの前記プルーニングされたバージョンを回復する際に使用されるメタデータを復号する手段125と、前記ピクチャの再構築バージョンからパッチライブラリを作成する手段130であって、前記パッチライブラリは、前記ピクチャの前記プルーニングされたバージョンの回復中に前記1つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含んでいる前記手段と、前記メタデータを用いた探索プロセスを実行して、前記複数の重なり合わないブロックのうちの前記1つまたは複数のプルーニングされたブロックのそれぞれ1つに対応するパッチを見つけ、前記1つまたは複数のプルーニングされたブロックの前記それぞれ1つを前記対応するパッチで置換する手段120と、を含む装置。前記1つまたは複数のプルーニングされたブロック中の全ての画素が、同じ色値または低解像度の一方を有する、請求項19に記載の装置。前記1つまたは複数のプルーニングされたブロックのうちの特定の1つに関する前記同じ色値が、前記1つまたは複数のプルーニングされたブロックのうちの前記特定の1つの中の前記画素の色値の平均に等しい、請求項20に記載の装置。前記パッチライブラリに含まれる前記複数の高解像度パッチの各々について、前記複数の高解像度パッチのそれぞれ1つの平均色を含む特徴ベクトルをそれぞれ生成することによって、署名をそれぞれ作成する、請求項19に記載の装置。前記複数の高解像度パッチの前記それぞれ1つの前記特徴ベクトルに含まれる前記平均色は、さらに、前記複数の高解像度パッチの前記それぞれ1つに対する周囲画素の平均色である、請求項22に記載の装置。前記署名は、前記1つまたは複数のプルーニングされたブロックの各々について作成され、前記ピクチャの前記プルーニングされたバージョンは、前記複数の高解像度パッチの各々の署名から前記1つまたは複数のプルーニングされたブロックの各々の署名までのそれぞれの距離メトリクスを比較し、前記それぞれの距離メトリクスを分類して前記1つまたは複数のプルーニングされたブロックの各々についてのランクリストを取得することによって回復され、前記1つまたは複数のプルーニングされたブロックのうちの特定の1つについての前記ランクリスト中のランク番号が、前記1つまたは複数のプルーニングされたブロックのうちの前記特定の1つを置換するために使用される、前記パッチライブラリ中の前記複数の高解像度パッチのうちの対応する1つを取り出すことに使用される、請求項19に記載の装置。前記複数の重なり合うブロックのうちの前記対応する1つに対して同じ位置にあるパッチより先行するパッチのみが、前記比較に使用される、請求項24に記載の装置。複数のノードおよび複数のエッジを有するパッチ依存性グラフを使用して前記ピクチャの前記プルーニングされたバージョンを回復し、前記複数のノードの各々が前記複数の重なり合うブロックのそれぞれ1つを表し、前記複数のエッジの各々が前記複数の重なり合うブロックの少なくとも前記それぞれ1つのそれぞれの依存性を表している、請求項24に記載の装置。前記メタデータは、前記複数の重なり合わないブロックの各々についてのベストマッチングパッチを識別するパッチ指標と、前記複数の重なり合わないブロックのうちの1つまたは複数のプルーニングされたブロックを識別するブロック識別子とを含む、請求項19に記載の装置。本発明の原理は、ビデオ圧縮効率を改善するための事例ベースのデータプルーニングを行う方法および装置を対象としている。本明細書は、本発明の原理を例示するものである。従って、本明細書に明示的に記述または図示していなくても、本発明の原理を具体化し、本発明の原理の趣旨および範囲に含まれる様々な構成を、当業者なら考案することができることを理解されたい。本明細書に記載された全ての例および条件に関する表現は、本発明の原理と、当技術分野をさらに進歩させるために発明者等が与える概念とを、読者が理解するのを助けるという教授的な目的を有するものであって、これらの具体的に記載された例および条件に限定されないものと解釈されたい。さらに、本発明の原理の原理、態様および実施形態、ならびにその具体的な例について本明細書で記載する全ての記述は、その構造的な均等物および機能的な均等物の両方を含むものとする。さらに、これらの均等物には、現在既知の均等物だけでなく、将来開発されるであろう均等物も含まれる、すなわち、構造に関わらず、同じ機能を実行する開発される任意の要素も含まれるものとする。従って、例えば、当業者なら、本明細書に示すブロック図が本発明の原理を具体化する例示的な回路の概念図を表していることを理解するであろう。同様に、任意のフローチャート、流れ図、状態遷移図、擬似コードなどが、コンピュータ可読媒体中に実質的に表現され、明示してある場合もしていない場合もあるコンピュータまたはプロセッサによって実質的に実行され得る様々なプロセスを表すことも理解されたい。図面に示す様々な要素の機能は、専用のハードウェアを使用することによって、またソフトウェアを実行することができるハードウェアを適当なソフトウェアと関連付けて使用することによって、実現することができる。プロセッサによってそれらの機能を実現するときには、単一の専用プロセッサで実現することも、単一の共用プロセッサで実現することも、あるいはその一部を共用することもできる複数の個別プロセッサで実現することもできる。さらに、プロセッサまたは制御装置という用語を明示的に用いていても、ソフトウェアを実行することができるハードウェアのみを指していると解釈すべきではなく、ディジタル信号プロセッサDSPハードウェア、ソフトウェアを記憶するための読取り専用メモリROM、ランダムアクセスメモリRAMおよび不揮発性記憶装置ただしこれらに限定されないを黙示的に含むことがある。従来の、且つ/または特注のその他ハードウェアも含まれることがある。同様に、図面に示す任意のスイッチも、概念的なものに過ぎない。それらの機能は、プログラム論理の動作によっても、専用論理によっても、プログラム制御と専用論理の相互作用によっても、あるいは手作業でも実施することができ、実施者が、前後関係から適宜判断して特定の技術を選択することができる。本明細書の特許請求の範囲において、特定の機能を実行する手段として表現されている任意の要素は、当該機能を実行する任意の形態を含むものとする。例えば、a当該機能を実行する回路素子の組合せや、bファームウェア、マイクロコードなども含めた任意の形態のソフトウェアを、当該ソフトウェアを実行して当該機能を実行する適当な回路と組み合わせたものなども含むものとする。特許請求の範囲によって定義される本発明の原理は、記載された様々な手段が実施する機能を、特許請求の範囲が要求する形式で組み合わせ、まとめることにある。従って、これらの機能を実施することができる任意の手段を、本明細書に示す手段の均等物とみなすものとする。本明細書において、本発明の原理の1つの実施形態または一実施形態、ならびにその他の変形表現に言及している場合、それは、当該実施形態に関連して述べられる特定の特性、構造、特徴などが、本発明の原理の少なくとも1つの実施形態に含まれるという意味である。従って、本明細書の様々な箇所に見られる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を選択することを含むということである。当技術分野および関連技術分野の当業者には容易に分かるように、このことは、列挙されている項目の数に応じて拡張することができる。また、本明細書で使用するピクチャおよび画像という用語は入れ替えて使用してもよく、ビデオシーケンスの静止画像またはピクチャを指している。既知の通り、ピクチャは、フレームであってもフィールドであってもよい。図1を参照すると、例示的な事例ベースのデータプルーニングシステムの全体が、参照番号100で示されている。プルーニングシステム100は、ビデオエンコーダ110の入力部およびメタデータ生成器/エンコーダ135の第1の入力部に信号通信で接続された出力部を有するプルナpruner105を含む。ビデオエンコーダの出力部は、ビデオデコーダ115の入力部およびパッチライブラリ作成器140の入力部に信号通信で接続されている。ビデオデコーダ115の出力部は、回復装置120の第1の入力部に信号通信で接続されている。パッチライブラリ作成器130の出力部は、回復装置120の第2の入力部に信号通信で接続されている。メタデータ生成器/エンコーダ135の出力部は、メタデータデコーダ125の入力部に信号通信で接続されている。メタデータデコーダ125の出力部は、回復装置120の第3の入力部に信号通信で接続されている。パッチライブラリ作成器140の出力部は、メタデータ生成器/エンコーダ135の第2の入力部に信号通信で接続されている。クラスタリング装置/パッチライブラリ作成器145の出力部は、プルナ105の第2の入力部に信号通信で接続されている。プルナ105の入力部およびクラスタリング装置/パッチライブラリ作成器145の入力部は、プルーニングシステム100の、入力ビデオを受信する入力部として利用することができる。回復装置の出力部は、プルーニングシステム100の、ビデオを出力する出力部として利用することができる。図2を参照すると、本発明の原理を適用することができる例示的なビデオエンコーダの全体が、参照番号200で示されている。ビデオエンコーダ200は、結合器285の非反転入力部と信号通信する出力部を有するフレーム順序付けバッファ210を含む。結合器285の出力部は、変換器/量子化器225の第1の入力部に信号通信で接続されている。変換器/量子化器225の出力部は、エントロピコーダ245の第1の入力部および逆変換器/逆量子化器250の第1の入力部に信号通信で接続されている。エントロピコーダ245の出力部は、結合器290の第1の非反転入力部に信号通信で接続されている。結合器290の出力部は、出力バッファ235の第1の入力部に信号通信で接続されている。エンコーダ制御装置205の第1の出力部は、フレーム順序付けバッファ210の第2の入力部、逆変換器/逆量子化器250の第2の入力部、ピクチャタイプ判断モジュール215の入力部、マクロブロックタイプMBタイプ判断モジュール220の第1の入力部、イントラ予測モジュール260の第2の入力部、デブロッキングフィルタ265の第2の入力部、動き補償器270の第1の入力部、動き推定器275の第1の入力部、および参照ピクチャバッファ280の第2の入力部に信号通信で接続されている。エンコーダ制御装置205の第2の出力部は、付加拡張情報SEI挿入器230の第1の入力部、変換器/量子化器225の第2の入力部、エントロピコーダ245の第2の入力部、出力バッファ235の第2の入力部、およびシーケンスパラメータセットSPS/ピクチャパラメータセットPPS挿入器240の入力部に信号通信で接続されている。SEI挿入器230の出力部は、結合器290の第2の非反転入力部に信号通信で接続されている。ピクチャタイプ判断モジュール215の第1の出力部は、フレーム順序付けバッファ210の第3の入力部に信号通信で接続されている。ピクチャタイプ判断モジュール215の第2の出力部は、マクロブロックタイプ判断モジュール220の第2の入力部に信号通信で接続されている。シーケンスパラメータセットSPS/ピクチャパラメータセットPPS挿入器240の出力部は、結合器290の第3の非反転入力部に信号通信で接続されている。逆量子化器/逆変換器250の出力部は、結合器219の第1の非反転入力部に信号通信で接続されている。結合器219の出力部は、イントラ予測モジュール260の第1の入力部およびデブロッキングフィルタ265の第1の入力部に信号通信で接続されている。デブロッキングフィルタ265の出力部は、参照ピクチャバッファ280の第1の入力部に信号通信で接続されている。参照ピクチャバッファ280の出力部は、動き推定器275の第2の入力部および動き補償器270の第3の入力部に信号通信で接続されている。動き推定器275の第1の出力部は、動き補償器270の第2の入力部に信号通信で接続されている。動き推定器275の第2の出力部は、エントロピコーダ245の第3の入力部に信号通信で接続されている。動き補償器270の出力部は、スイッチ297の第1の入力部に信号通信で接続されている。イントラ予測モジュール260の出力部は、スイッチ297の第2の入力部に信号通信で接続されている。マクロブロックタイプ判断モジュール220の出力部は、スイッチ297の第3の入力部に信号通信で接続されている。スイッチ297の第3の入力部は、スイッチのデータ入力データ入力とは、制御入力すなわち第3の入力に対する呼称が、動き補償器270またはイントラ予測モジュール260によって与えられるか否かを判定するものである。スイッチ297の出力部は、結合器219の第2の非反転入力部および結合器285の反転入力部に信号通信で接続されている。フレーム順序付けバッファ210の第1の入力部およびエンコーダ制御装置205の入力部は、エンコーダ200の、入力ピクチャを受信する入力部として利用することができる。さらに、付加拡張情報SEI挿入器230の第2の入力部は、エンコーダ200の、メタデータを受信する入力部として利用することができる。出力バッファ235の出力部は、エンコーダ200の、ビットストリームを出力する出力部として利用することができる。図3を参照すると、本発明の原理を適用することができる例示的なビデオデコーダの全体が、参照番号300で示されている。ビデオデコーダ300は、エントロピデコーダ345の第1の入力部に信号通信で接続された出力部を有する入力バッファ310を含む。エントロピデコーダ345の第1の出力部は、逆変換器/逆量子化器350の第1の入力部に信号通信で接続されている。逆変換器/逆量子化器350の出力部は、結合器325の第2の非反転入力部に信号通信で接続されている。結合器325の出力部は、デブロッキングフィルタ365の第2の入力部およびイントラ予測モジュール360の第1の入力部に信号通信で接続されている。デブロッキングフィルタ365の第2の出力部は、参照ピクチャバッファ380の第1の入力部に信号通信で接続されている。参照ピクチャバッファ380の出力部は、動き補償器370の第2の入力部に信号通信で接続されている。エントロピデコーダ345の第2の出力部は、動き補償器370の第3の入力部、デブロッキングフィルタ365の第1の入力部、およびイントラ予測器360の第3の入力部に信号通信で接続されている。エントロピデコーダ345の第3の出力部は、デコーダ制御装置305の入力部に信号通信で接続されている。デコーダ制御装置305の第1の出力部は、エントロピデコーダ345の第2の入力部に信号通信で接続されている。デコーダ制御装置305の第2の出力部は、逆変換器/逆量子化器350の第2の入力部に信号通信で接続されている。デコーダ制御装置305の第3の出力部は、デブロッキングフィルタ365の第3の入力部に信号通信で接続されている。デコーダ制御装置305の第4の出力部は、イントラ予測モジュール360の第2の入力部、動き補償器370の第1の入力部、および参照ピクチャバッファ380の第2の入力部に信号通信で接続されている。動き補償器370の出力部は、スイッチ397の第1の入力部に信号通信で接続されている。イントラ予測モジュール360の出力部は、スイッチ397の第2の入力部に信号通信で接続されている。スイッチ397の出力部は、結合器325の第1の非反転入力部に信号通信で接続されている。入力バッファ310の入力部は、デコーダ300の、入力ビットストリームを受信する入力部として利用することができる。デブロッキングフィルタ365の第1の出力部は、デコーダ300の、出力ピクチャを出力する出力部として利用することができる。上述のように、本発明の原理は、ビデオ圧縮効率を改善するための事例ベースのデータプルーニングを行う方法および装置を対象としている。本発明の原理は、前述の第7の手法に対して改善をもたらすので有利である。すなわち、本願は、第7の手法のように通信チャネルを介してパッチライブラリを送信するのではなく、以前に送信されたフレームまたは既存のフレームを用いてデコーダ側においてパッチライブラリをトレーニングするという概念を開示する。また、データプルーニングは、入力フレーム中のいくつかのブロックをフラット領域flatregionで置換して混合解像度フレームを作成することによって実現される。一実施形態では、本発明の原理は、トレーニング画像/フレームのプールからトレーニングしたパッチ例ライブラリを使用してビデオをプルーニングし、プルーニングされたビデオを回復することを実現するので有利である。パッチ例ライブラリは、参照フレームの概念を拡張したものと考えることができる。従って、パッチ例ライブラリの考えは、従来のビデオ符号化方法でも使用することができる。一実施形態では、本発明の原理は、ライブラリで効率的にパッチを探索するために誤差限界error-boundedクラスタリング例えば修正K平均クラスタリングを使用する。さらに、一実施形態では、本発明の原理は、複数のブロックをフラットブロックflatblockで置換して高周波信号を低減して圧縮効率を向上させる、混合解像度データプルーニング方式を提供するので有利である。メタデータライブラリ中のベストマッチパッチ位置符号化の効率を向上させるために、本発明の原理は、パッチ署名マッチング、マッチングランクリストおよびランク番号符号化を使用する。さらに、一実施形態では、本発明の原理は、色の変化に基づくフラットブロック識別方式を用いてプルーニングされたブロックIDを符号化するストラテジを提供するので有利である。このように、本発明の原理によれば、入力ビデオをビデオエンコーダがより効率的に符号化することができるように入力ビデオをプルーニングするための、本明細書で事例ベースのデータプルーニングと呼ぶ、新規の方法が提供される。一実施形態では、この方法は、例としてのパッチのライブラリを作成し、このパッチライブラリを使用して、その中の一部のブロックが低解像度ブロックまたはフラットブロックで置換されたビデオフレームを回復することを含む。この枠組みは、パッチライブラリを作成し、ビデオをプルーニングし、ビデオを回復し、ならびに回復に必要なメタデータを符号化する方法を含む。図1を参照すると、エンコーダ側の処理は、基本的に、2つの部分、すなわちパッチライブラリ作成およびプルーニングを含む。パッチライブラリは、既にデコーダ側に送信されている以前のフレームオリジナルのビデオフレームまたは符号化され復号されたフレームを使用して、あるいはエンコーダ側とデコーダ側の両方で共有している、またはエンコーダ側とデコーダ側の両方がアクセスすることができるいくつかのビデオ例えばYOUTUBE.COMのビデオを使用して、作成することができる。本明細書に開示する好ましい実施形態では、以前から存在しているフレームを使用して、パッチライブラリを作成する。パッチライブラリは、デコーダ側でも、以前に復号されたフレームを用いて生成される。エンコーダ側では、2つのパッチライブラリが生成される。1つのライブラリは、オリジナルのフレームから生成され、もう1つのライブラリは、再構築されたフレームすなわち符号化された後に復号されたフレームから生成される。後者のライブラリ再構築フレームから生成されたライブラリは、デコーダ側で作成されたパッチライブラリと全く同じであるが、これは、これらのパッチライブラリを生成するのに全く同じフレームすなわち再構築フレームが使用されているからである。エンコーダ側では、オリジナルのフレームから作成したパッチライブラリを使用してブロックをプルーニングし、再構築フレームから作成したパッチライブラリを使用してメタデータを符号化する。再構築フレームから作成したパッチライブラリを使用する理由は、メタデータを符号化および復号するパッチライブラリが、エンコーダ側とデコーダ側とで同一になることを保証するためである。オリジナルのフレームを使用して作成したパッチライブラリについて、クラスタリングアルゴリズムを実行して、プルーニング中のパッチ探索プロセスを効率的に実行することができるようにパッチをグループ化する。プルーニングは、デコーダ側に送信されるビット数が少なくなるように、パッチライブラリを用いてソースビデオを修正するプロセスである。プルーニングは、ビデオフレームを複数のブロックに分割し、それらのブロックの一部を低解像度ブロックまたはフラットブロックで置換することによって実現される。その後、プルーニングされたフレームを、ビデオエンコーダへの入力として用いる。本発明の原理を適用することができる例示的なビデオエンコーダは、上述した図2に示されている。再度図1を参照すると、プルーニングシステム100のデコーダ側処理の構成要素も、2つの部分、すなわちパッチライブラリ作成部および回復部を含むものと考えることができる。デコーダ側でのパッチライブラリ作成は、エンコーダ側とデコーダ側の両方で同じであるものとする、以前に復号されたフレームを用いてパッチライブラリを作成するプロセスである。エンコーダ側の処理と異なり、デコーダ側でのパッチライブラリ作成では、クラスタリングを用いない。回復構成要素は、エンコーダ側から送信された復号されたプルーニングされたフレームにおいて、プルーニングされたコンテンツを回復するプロセスである。この復号されたプルーニングされたフレームが、ビデオデコーダの出力である。本発明の原理を適用することができる例示的なビデオデコーダは、上述した図3に示されている。パッチライブラリ作成図4を参照すると、事例ベースのデータプルーニングシステムのエンコーダ側処理を実行する例示的な第1の部分の全体が、参照番号400で示されている。第1の部分400は、クラスタリング装置420の入力部に信号通信された出力部を有する分割器410を含む。分割器の入力部は、第1の部分400の、トレーニングフレームを受信する入力部として利用することができる。クラスタリング装置420の出力部は、第1の部分400の、クラスタおよびパッチライブラリを出力する出力部として利用することができる。図5を参照すると、クラスタリングおよびパッチライブラリ作成を行う例示的な方法の全体が、参照番号500で示されている。ステップ505で、トレーニングビデオフレームを入力する。ステップ510で、トレーニングビデオフレームを、分割器410によって重なり合う複数のブロックに分割する。ステップ515で、高周波数の細部を含まないブロックをクラスタリング装置420によって除去する。ステップ520で、これらのブロックをクラスタリング装置420によってクラスタリングする。ステップ525で、クラスタおよびパッチライブラリを出力する。パッチライブラリは、プルーニングされた画像ブロックを回復するために使用することができる高解像度パッチのプールである。図6を参照すると、例示的なパッチライブラリおよび対応するクラスタの全体が、参照番号600で示されている。詳細には、パッチライブラリは、参照番号610で示してあり、署名部分611および高解像度パッチ部分612を含む。エンコーダ側処理では、2つのパッチライブラリが生成され、1つはプルーニング用のパッチライブラリ、もう1つはメタデータ符号化用のパッチライブラリである。プルーニング用のパッチライブラリはオリジナルのフレームを用いて生成され、メタデータ符号化用のパッチライブラリは再構築フレームを用いて生成される。プルーニング用のパッチライブラリでは、プルーニング探索プロセスを効率的に実行することができるように、ライブラリ中のパッチを複数のクラスタにグループ化する。ライブラリ作成に用いられるビデオフレームを、重なり合う複数のブロックに分割して、トレーニングデータセットを形成する。最初に、高周波数の細部を含まない全てのブロックを除去することによって、トレーニングデータをクリーンアップする。修正K平均クラスタリングアルゴリズム2010年1月22日に同じ所有者の米国仮特許出願第61/336516号Technicolor整理番号PU100014として出願された、Dong-QingZhang、SitaramBhagavathyおよびJoanLlachによるDatapruningforvideocompressionusingexample-basedsuper-resolutionに記載を使用して、トレーニングデータセット中のパッチを複数のクラスタにグループ化する。各クラスタで、クラスタ中心は、当該クラスタ中のパッチの平均であり、プルーニングプロセス中にマッチングおよび入来クエリに使用される。修正K平均クラスタリングアルゴリズムは、クラスタ内の任意のパッチとそのクラスタ中心との間の誤差が指定されたしきい値より小さくなることを保証する。修正K平均クラスタリングアルゴリズムの代わりに、クラスタ中の誤差限界を保証する任意の同様のクラスタリングアルゴリズムを用いることも可能である。計算速度を上げるために、トレーニングフレームの水平寸法および垂直寸法を、元のサイズの4分の1に縮小する。また、これらのダウンサイズされたフレーム中のパッチに対して、クラスタリングプロセスを実行する。1つの例示的な実施形態では、高解像度パッチのサイズは16×16画素で、ダウンサイズされたパッチのサイズが4×4画素である。従って、ダウンサイズ率は4である。もちろん、本発明の原理の趣旨を維持しながら、その他のサイズを使用することができる。メタデータ符号化用のパッチライブラリでは、クラスタリングプロセスおよびクリーンアッププロセスを実行しない。従って、このパッチライブラリは、再構築フレームの全ての可能性のあるパッチを含む。ただし、元のフレームから作成したパッチライブラリ中のあらゆるパッチについて、それらのパッチの座標を用いて再構築フレームから作成したパッチライブラリ中に対応するパッチを見つけることができる。こうすれば、確実に、メタデータ符号化を正しく実行することができる。デコーダ側では、メタデータ復号およびプルーニングされたブロックの回復に同じ復号ビデオフレームを用いて、クラスタリングを用いない同じパッチライブラリを作成する。エンコーダ側とデコーダ側の両方で復号フレームを用いて作成されるパッチライブラリについて、別のプロセスを実行して、パッチの署名を作成する。パッチの署名は、当該パッチおよび当該パッチの周囲の画素の平均色を含む特徴ベクトルである。パッチ署名をメタデータ符号化プロセスに使用して、さらに効率的にメタデータを符号化し、また、デコーダ側での回復プロセスで使用して、ベストマッチパッチを発見し、より高い信頼性でプルーニングされたコンテンツを回復する。図7を参照すると、例示的な署名ベクトルの全体が、参照番号700で示されている。署名ベクトル700は、平均色701および周囲画素702を含む。メタデータ符号化プロセスについて、以下に述べる。プルーニングされたフレームでは、時に、回復またはメタデータ符号化のためにプルーニングされるブロックの隣接するブロックもプルーニングされることがある。この場合、パッチライブラリ探索用の署名として使用される周囲画素のセットは、プルーニングされていないブロックの画素しか含んでいない。隣接する全てのブロックがプルーニングされた場合には、平均色701のみが署名として使用される。この場合、パッチマッチングに用いられる情報が少なすぎるので、パッチマッチングがうまくいかない可能性があり、これが、隣接するプルーニングされない画素702が重要である理由である。プルーニングプロセス標準的なビデオ符号化アルゴリズムと同様に、入力ビデオフレームを複数のグループオブピクチャGOPに分割する。プルーニングプロセスは、GOPの第1のフレームに対して行われる。プルーニングの結果は、その後、GOPの残りのフレームに伝えられる。GOPの第1のフレームに対するプルーニングプロセス図8を参照すると、事例ベースのデータプルーニングシステムのエンコーダ側処理を実行する例示的な第2の部分の全体が、参照番号800で示されている。第2の部分800は、パッチライブラリ探索器810の入力部と信号通信する出力部を有する分割器805を含む。パッチライブラリ探索器810の出力部は、ビデオエンコーダ815の入力部、メタデータ生成器820の第1の入力部、およびメタデータエンコーダ825の第1の入力部に信号通信で接続されている。メタデータ生成器820の出力部は、メタデータエンコーダ825の第2の入力部に信号通信で接続されている。ビデオエンコーダ815の第1の出力部は、メタデータ生成器820の第2の入力部に信号通信で接続されている。分割器805の入力部は、第2の部分800の、入力フレームを受信する入力部として利用することができる。ビデオエンコーダ815の出力部は、第2の部分800の、符号化ビデオフレームを出力する出力部として利用することができる。メタデータエンコーダ825の出力部は、第2の部分800の、符号化メタデータを出力する出力部として利用することができる。図9を参照すると、ビデオフレームをプルーニングする例示的な方法の全体が、参照番号900で示されている。ステップ905で、ビデオフレームを入力する。ステップ910で、ビデオフレームを、重なり合わない複数のブロックに分割する。ステップ915で、各ブロックについてループを実行する。ステップ920で、パッチライブラリの探索を実行する。ステップ925で、パッチが見つかったか否かを判定する。パッチが見つかった場合には、この方法は、ステップ930に進む。そうでない場合には、この方法は、ステップ915に戻る。ステップ930で、ブロックをプルーニングする。ステップ935で、全てのブロックが終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ940に進む。そうでない場合には、この方法は、ステップ915に戻る。ステップ940で、プルーニングされたフレームおよび対応するメタデータを出力する。このように、最初にステップ910で、入力フレームを、重なり合わない複数のブロックに分割する。ブロックのサイズは、標準的な圧縮アルゴリズムで使用されるマクロブロックのサイズと同じである。すなわち、本明細書に開示する例示的な実施態様では、16×16画素のサイズを利用する。次いで、ステップ920で、探索プロセスを行い、パッチライブラリ中のベストマッチパッチを見つける。この探索プロセスを、図10に示す。図10を参照すると、プルーニング中に実行されるパッチ探索プロセスの全体が、参照番号1000で示されている。パッチ探索プロセス1000では、パッチライブラリ1010を用い、パッチライブラリ1010は、署名部分1011および高解像度パッチ部分1012を含む。最初に、ユークリッド距離を計算し、上位K個のマッチングするクラスタを見つけることにより、ブロックをクラスタの中心とマッチングする。現在のところ、Kは経験的に決定される。原則的には、Kは、クラスタの誤差限界によって決定される。もちろん、本発明の原理の教示に従って、Kを計算するその他の手法を使用することもできる。候補クラスタを識別した後で、これらのクラスタ内でベストマッチパッチが見つかるまで、これらのクラスタ内で探索プロセスを実行する。ベストマッチパッチとクエリブロックとの間の差が所定のしきい値未満である場合には、そのブロックをプルーニングすることになる。そうでない場合には、そのブロックはそのままに保たれる。プルーニングされたブロックのIDおよび各ブロックのベストマッチパッチの指標はメタデータとして保存され、このメタデータが、メタデータ符号化構成要素で符号化され、デコーダ側に送信されることになる。プルーニングを行うブロックを識別した後で、ブロックをプルーニングするプロセスを行う。プルーニングする必要があるブロックについて、例えば、高解像度ブロックを低解像度ブロックで置換するなど、様々なプルーニングストラテジが考えられる。ただし、この手法で有意な圧縮効率の向上を実現することは困難である可能性もあることが分かっている。従って、本明細書に開示する好ましい実施形態では、単に、高解像度ブロックを、全ての画素が同じ色値すなわちオリジナルのブロックの画素の色値の平均を有するフラットブロックで置換する。ブロック置換プロセスでは、フレームのいくつかの部分が高解像度を有し、いくつかの他の部分が低解像度を有するビデオフレームを作成する。従って、このようなフレームは、混合解像度フレームと呼ばれる混合解像度プルーニング方式に関する詳細については、2011年3月XX日出願のMETHODSANDAPPARATUSFORENCODINGVIDEOSIGNALSFORBLOCK-BASEDMIXED-RESOLUTIONDATAPRUNINGFORIMPROVINGVIDEOCOMPRESSIONEFFICIENCYと題する同時係属の所有者が同じ国際PCT特許出願第XXXX号Technicolor整理番号PU100194を参照されたい。図11を参照すると、例示的な混合解像度フレームの全体が、参照番号1100で示されている。上述のフラットブロック置換方式は、望ましい圧縮効率を得るのに極めて効果的であることが分かっている。フラットブロック置換方式の代わりに、プルーニングするブロックをその低解像度バージョンで置換する、低解像度ブロック置換方式を用いることも可能である。メタデータの符号化および復号メタデータ符号化は、2つの構成要素図12参照を含み、1つはプルーニングされたブロックIDの符号化図13参照で、もう1つはパッチ指標の符号化図14である。これらは、プルーニングプロセス中に各ブロック毎にパッチライブラリを探索した結果である。図12を参照すると、メタデータを符号化する例示的な方法の全体が、参照番号1200で示されている。ステップ1205で、復号されたプルーニングされたビデオフレーム、プルーニングされたブロックIDおよび各ブロックのパッチ指標を入力する。ステップ1210で、プルーニングされたブロックIDを符号化する。ステップ1215で、パッチ指標を符号化する。ステップ1220で、符号化メタデータを出力する。図13を参照すると、プルーニングされたブロックIDを符号化する例示的な方法の全体が、参照番号1300で示されている。ステップ1305で、プルーニングされたフレームおよびプルーニングされたブロックIDを入力する。ステップ1310で、低解像度ブロック識別を実行する。ステップ1320で、ミスがあるか否かを判定する。ミスがないと判定された場合には、この方法は、ステップ1325に進む。そうでない場合には、この方法は、ステップ1315に進む。ステップ1325で、誤検出の数がプルーニングされたブロックの数より多いか否かを判定する。誤検出の数がプルーニングされたブロックの数より多い場合には、この方法は、ステップ1330に進む。そうでない場合には、制御はステップ1335に進む。ステップ1330で、プルーニングされたブロックのシーケンスを用い、フラグをゼロにセットする。ステップ1340で、差分計算differentiationを実行する。ステップ1345で、可逆符号化を実行する。ステップ1350で、符号化メタデータを出力する。ステップ1315で、しきい値を調節する。ステップ1335で、誤検出シーケンスを用い、フラグを1にセットする。図14を参照すると、パッチ指標を符号化する例示的な方法の全体が、参照番号1400で示されている。ステップ1405で、復号されたプルーニングされたビデオフレームおよび各ブロックのパッチ指標を入力する。ステップ1410で、各々のプルーニングされたブロック毎にループを実行する。ステップ1415で、署名を取得する。ステップ1420で、パッチライブラリ中の各パッチまでの距離を計算する。ステップ1425で、これらのパッチを分類して、ランクリストを取得する。ステップ1430で、ランク番号を取得する。ステップ1435で、ランク番号をエントロピ符号化する。ステップ1440で、全てのブロックの処理が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ1445に進む。そうでない場合には、この方法は、ステップ1410に戻る。ステップ1445で、符号化されたパッチ指標を出力する。プルーニングプロセス中に、各ブロック毎に、システムはベストマッチパッチを探してパッチライブラリを探索し、見つかったパッチのパッチライブラリ中でのパッチ指標を、その歪みがしきい値未満であれば出力する。各パッチは、その署名すなわちそのパッチの色に復号したフレーム中での周囲の画素を加えたものと関連付けられる。デコーダ側処理における回復プロセス中に、プルーニングされたブロックの色およびその周囲の画素を署名として用いて、ライブラリ中の正しい高解像度パッチを見つける。ただし、ノイズにより、署名を用いた探索プロセスは信頼性が低く、信頼性を確保するために回復プロセスを補助するメタデータが必要である。従って、プルーニングプロセスの後で、システムは回復を補助するためのメタデータを生成することになる。各々のプルーニングされたブロック毎に、上述の探索プロセスは、ライブラリ中の対応するパッチを既に識別している。メタデータ符号化構成要素では、クエリベクトルプルーニングされたブロックの平均色および周囲画素を使用してパッチライブラリ復号フレームを用いて作成されたライブラリ中のパッチの署名のマッチングを行うことにより、回復プロセスをシミュレートする。このプロセスを、図14に示す。再度図14を参照すると、各ブロック毎に、ブロックに対応するクエリベクトルとライブラリ中のパッチの署名との間の距離例えばユークリッド距離、ただしもちろんその他の距離メトリクスを用いてもよいを計算する。この距離に従ってパッチを分類し、ランクリストを得る。理想的なケースでは、ベストマッチの高解像度パッチがランクリストの最上位に来なければならない。しかし、丸め演算および圧縮によるノイズによって、ベストマッチパッチがランクリストの最初のパッチにならないことも多い。正しいパッチがランクリストのn番目のパッチであると仮定する。この数字nは、このブロックのメタデータとして保存される。なお、ほとんどの場合、ベストマッチパッチはランクリストの最上位に近いので、nは1または非常に小さな数字であることに留意されたい。従って、この乱数のエントロピは、最大エントロピを有する一様分布であるはずのライブラリ中のベストマッチパッチの指標よりもかなり小さい。従って、この順位番号は、エントロピ符号化で効率的に符号化することができる。全てのプルーニングされたブロックのランク番号で、デコーダ側に送信されるメタデータの一部としてのランク番号シーケンスが形成される。実際に行われた実験により、ランク番号の分布が幾何学的分布に近いことが分かっている。従って、現在は、ランク番号シーケンスをさらに符号化するために、ゴロム符号が用いられている。ゴロム符号は、幾何学的分布を有する乱数に最適である。もちろん、本発明の原理の教示に従って、本発明の原理の趣旨を維持しながら、その他のタイプの符号を使用することもできる。復号図15参照のために、デコーダ側は、復号フレームを用いて作成された、エンコーダ側と全く同じパッチライブラリを有していなければならない。プルーニングされたブロックの署名を使用して、パッチライブラリ中の署名とのマッチングを行い、ランクリスト分類済みパッチライブラリを得る。ランク番号を使用して、分類済みパッチライブラリから正しいパッチを取り出す。パッチライブラリが以前のフレームから作成されている場合には、エンコーダ側およびデコーダ側が確実に全く同じパッチライブラリを有するようにするために、エンコーダ側でのメタデータ符号化プロセスで、ビデオデコーダから得た復号フレームも使用しなければならない。これは、デコーダ側では復号フレームしか利用できないからである。図15を参照すると、パッチ指標を復号する例示的な方法の全体が、参照番号1500で示されている。ステップ1505で、復号されたプルーニングされたビデオフレーム、符号化されたパッチ指標およびプルーニングされたブロックIDを入力する。ステップ1510で、各々のプルーニングされたブロック毎にループを実行する。ステップ1515で、署名を取得する。ステップ1520で、パッチライブラリ中の各パッチまでの距離を計算する。ステップ1525で、これらのパッチを分類して、ランクリストを取得する。ステップ1530で、符号化ランク番号をエントロピ復号する。ステップ1535で、ランク番号を用いて、パッチライブラリからパッチ指標を取り出す。ステップ1540で、全てのブロックの処理が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ1545に進む。そうでない場合には、この方法は、ステップ1510に戻る。ステップ1545で、復号されたパッチ指標を出力する。ランク番号メタデータの他に、プルーニングされたブロックの位置もデコーダ側に送信する必要がある。これは、ブロックIDの符号化図13参照によって行われる。1つの簡単な方法としては、単にブロックIDシーケンスをデコーダ側に送信するだけでもよい。ブロックのIDは、フレーム上での当該ブロックの座標を示す。図16を参照すると、例示的なブロックIDの全体が、参照番号1600で示されている。プルーニングされたブロックのIDシーケンスをさらに効率的に符号化することが可能である場合もある。プルーニングされたブロックはフラットであり、高周波数成分を含まないので、ブロック内の色変動を計算することによってプルーニングされたブロックを検出することができる。色変動がしきい値より小さければ、そのブロックはプルーニングされたブロックであると識別される。ただし、この識別プロセスは信頼性が低い場合があるので、識別プロセスを容易にするために、依然としてメタデータが必要である。最初に、高いしきい値から始めることにより分散しきい値を求める。このアルゴリズムでは、その後、この識別手順で全てのプルーニングされたブロックを識別することができるように分散しきい値をゆっくりと小さくしていくが、誤検出ブロックが識別結果に存在する可能性もある。その後、誤検出の数がプルーニングされたブロックの数より大きい場合には、プルーニングされたブロックのIDを保存し、デコーダに送信する。そうでない場合には、誤検出のIDを、デコーダ側に送信する。フラットブロックを識別するための分散しきい値も、同じ識別手順を実行するためにデコーダ側に送信する。IDシーケンスは、番号が大きくなるように分類することができる。冗長性をさらに低下させるために、差分符号化方式を利用して、ID番号とその前のID番号との間の差を最初に計算し、その差分シーケンスを符号化する。例えば、IDシーケンスが3、4、5、8、13、14であると仮定すると、その差分シーケンスは、3、1、1、3、5、1となる。この差分プロセスにより、各数字が1に近づくので、よりエントロピの小さな数字分布が得られる。次いで、この差分シーケンスを、エントロピ符号化例えば現在の実施態様ではハフマン符号化によってさらに符号化することができる。従って、最終的なメタデータのフォーマットは以下に示すようになる。ここで、フラグは、当該ブロックIDシーケンスが誤検出IDシーケンスであるか否かを示すシグナリングsignalingフラグである。しきい値は、フラットブロック識別のための分散しきい値である。符号化ブロックIDシーケンスは、プルーニングされたブロックIDまたは誤検出ブロックIDの符号化ビットストリームである。符号化ランク番号シーケンスは、ブロック回復に使用されるランク番号の符号化ビットストリームである。残りのフレームに対するプルーニングプロセスGOP中の残りのフレームについては、それらのフレーム内のブロックの一部は、やはりフラットブロックで置換される。第1のフレーム中のプルーニングされたブロックの位置は、動きトラッキングによって残りのフレームに伝えることができる。プルーニングされたブロックの位置を伝えるための様々なストラテジがテストされている。1つの手法は、ブロックマッチングによって複数のフレームをまたいでプルーニングされたブロックをトラッキングし、後続のフレーム内の対応するブロックをプルーニングするすなわちトラッキングしたブロックをフラットブロックで置換するものである。ただし、この手法は、一般に、トラッキングしたブロックの境界が符号化するマクロブロックと位置合わせされないので、良好な圧縮効率の向上は得られない。その結果として、トラッキングしたブロックの境界は、マクロブロック中で高周波数信号を生じる。従って、現在では、後続フレームの全てのブロック位置を第1のフレームと同じ位置にセットするという、より簡単な代替手法が用いられている。すなわち、後続フレーム中の全てのプルーニングされたブロックが、第1のフレーム中のプルーニングされたブロックと同じ位置にある。その結果として、後続フレームの全てのプルーニングされたブロックが、マクロブロックの位置と位置合わせされる。ただし、この手法は、プルーニングされたブロック内に動きがある場合には、うまくいかないこともある。従って、この問題を解決する1つの解決策は、ブロックの動き強度を計算するものである図17参照。図17を参照すると、後続フレームのプルーニングを行う例示的な方法の全体が、参照番号1700で示されている。ステップ1705で、ビデオフレームおよびプルーニングされたブロックIDを入力する。ステップ1710で、同じ位置にあるブロックのプルーニングを行う。ステップ1715で、各ブロック毎にループを実行する。ステップ1720で、以前のフレームまでの動きベクトルを計算する。ステップ1725で、これらの動きベクトルをメタデータとして保存する。ステップ1730で、全てのブロックの処理が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ1735に進む。そうでない場合には、この方法は、ステップ1715に戻る。動き強度がしきい値より大きい場合には、そのブロックのプルーニングを行わない。本明細書に開示する例示的な実施態様である別のさらに洗練された解決策では、以前のフレーム中の対応するブロックを探索することによって、オリジナルのビデオ内のプルーニングされたブロックの動きベクトルを計算する図18参照。図18を参照すると、プルーニングされたブロックの例示的な動きベクトルの全体が、参照番号1800で示されている。動きベクトル1800は、i番目のフレーム内のプルーニングされたブロックおよびi-1番目のフレーム内の同じ位置にあるブロックに関係する。プルーニングされたブロックの動きベクトルは、回復のためにデコーダ側に送信される。以前のフレームは既に完全に回復されているので、現在のフレーム中のプルーニングされたブロックも、これらの動きベクトルを使用して回復することができる。アーチファクトを避けるために、現在のフレーム内のブロックと動き推定によって計算した以前のフレーム内の対応するブロックとの間の差が大きすぎる場合には、現在のフレーム内のブロックのプルーニングを行わない。さらに、現在は、サブピクセルsub-pixel動き推定を利用して、動きベクトルに基づく回復の精度を高めている。実験によって、サブピクセルに基づく動きベクトル推定を用いて得られた視覚的品質は、整数ピクセルintegerpixelに基づく動きベクトル推定を用いて得られる視覚的品質よりはるかに良好であることが分かっている。回復プロセス回復プロセスは、デコーダ側で行われる。回復プロセスの前に、パッチライブラリを作成しなければならない。映画などの長いビデオの場合には、これは、デコーダ側に既に送信されている以前のフレームを用いることによって行うことができる。エンコーダ側は、パッチライブラリ作成にどのフレームを使用すべきかを示すメタデータフレームIDを送信することができる。デコーダ側でのパッチライブラリは、エンコーダ側でのパッチライブラリと全く同じでなければならない。GOP内の第1のフレームに対しては、回復プロセスは、ブロックIDシーケンスの復号図20参照およびランク順位シーケンスの復号図19参照を含むメタデータを復号すること図19参照から開始する。図19を参照すると、メタデータを復号する例示的な方法の全体が、参照番号1900で示されている。ステップ1905で、符号化メタデータを入力する。ステップ1910で、プルーニングされたブロックIDを復号する。ステップ1915で、パッチ指標を復号する。ステップ1920で、復号メタデータを出力する。図20を参照すると、プルーニングされたブロックIDを復号する例示的な方法の全体が、参照番号2000で示されている。ステップ2005で、符号化メタデータを入力する。ステップ2010で、可逆復号を実行する。ステップ2015で、逆差分計算reversedifferentiationを実行する。ステップ2020で、フラグがゼロであるか否かを判定する。フラグがゼロである場合には、この方法は、ステップ2025に進む。そうでない場合には、この方法は、ステップ2030に進む。ステップ2025で、ブロックIDを出力する。ステップ2030で、低解像度ブロック識別を実行する。ステップ2035で、誤検出を除去する。ステップ2040で、ブロックIDを出力する。ブロックIDシーケンスが利用可能になった後で、各々のプルーニングされたブロック毎に、このブロックの平均色および周囲画素を署名ベクトルとして、パッチライブラリ中の署名とのマッチングを行う。ただし、回復するブロックの隣接するブロックもプルーニングされている場合には、探索のためのみの署名として用いられる周囲画素のセットは、プルーニングされていないブロックの画素を含む。隣接する全てのブロックがプルーニングされている場合には、平均色のみを署名として使用する。このマッチングプロセスは、クエリブロックの署名とライブラリ中の各パッチの署名との間のユークリッド距離を計算することによって実現される。全ての距離を計算した後で、その距離に従ってリストを分類して、ランクリストを得る。次いで、プルーニングされたブロックに対応するランク番号を使用して、ランクリストから正しい高解像度ブロックを取り出す。図21を参照すると、事例ベースのデータプルーニングのデコーダ側処理を実行する例示的な装置の全体が、参照番号2100で示されている。装置2100は、探索パッチライブラリ/ブロック置換装置2110の第1の入力部に信号通信で接続された出力部を有する分割器2105を含む。メタデータデコーダ2115の出力部は、探索パッチライブラリ/ブロック置換装置2110の第2の入力部に信号通信で接続されている。分割器2105の入力部は、装置2100の、プルーニングされたビデオを受信する入力部として利用することができる。メタデータデコーダ2115の入力部は、装置2100の、符号化メタデータを受信する入力部として利用することができる。探索パッチライブラリ/ブロック置換装置2110の出力部は、この装置の、回復ビデオを出力する出力部として利用することができる。図22を参照すると、プルーニングされたフレームを回復する例示的な方法の全体が、参照番号2200で示されている。ステップ2205で、プルーニングされたフレームおよび対応するメタデータを入力する。ステップ2210で、プルーニングされたフレームを、重なり合わない複数のブロックに分割する。ステップ2215で、各ブロック毎にループを実行する。ステップ2220で、現在のブロックがプルーニングされたブロックであるか否かを判定する。現在のブロックがプルーニングされたブロックである場合には、この方法は、ステップ2225に進む。そうでない場合には、この方法は、ステップ2215に戻る。ステップ2225で、ライブラリ中でパッチを見つける。ステップ2230で、現在のブロックを、この見つかったパッチで置換する。ステップ2235で、全てのブロックの処理が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ2240に進む。そうでない場合には、この方法は、ステップ2215に戻る。ステップ2240で、回復フレームを出力する。エグザンプルパッチを用いたブロック回復の代わりに、従来のインペインティングおよびテクスチャ合成に基づく方法を行うこともできることを理解されたい。GOP中の残りのフレームに対しては、各々のプルーニングされたブロック毎に、動きベクトルが利用できない場合には、ブロックのコンテンツを以前のフレーム中の同じ位置にあるブロックからコピーすることができる。動きベクトルが利用できる場合には、動きベクトルを使用して、以前のフレーム中の対応するブロックを見つけ、この対応するブロックをコピーして、プルーニングされたブロックを埋めることができる図23参照。図23を参照すると、後続フレームを回復する例示的な方法の全体が、参照番号2300で示されている。ステップ2305で、ビデオフレームおよびプルーニングされたブロックIDを入力する。ステップ2310で、各ブロック毎にループを実行する。ステップ2315で、動きベクトルを使用して、以前のフレーム中のパッチを見つける。ステップ2320で、この見つかったパッチを用いて、プルーニングされたブロックを置換する。ステップ2325で、全てのブロックの処理が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ2330に進む。そうでない場合には、この方法は、ステップ2310に戻る。この回復プロセスはブロックに基づくので、ブロックアーチファクトが見えることもある。AVCエンコーダで用いられるインループデブロッキングフィルタなどのデブロッキングフィルタを適用して、ブロックアーチファクトを低減することができる。本発明の原理の上記その他の特徴および利点は、当業者であれば、本明細書の教示に基づいて容易に確認することができる。これらの本発明の原理の教示は、ハードウェア、ソフトウェア、ファームウェア、特殊目的プロセッサ、またはそれらの組合せの様々な形態で実施することができることを理解されたい。本発明の原理の教示は、ハードウェアとソフトウェアの組合せとして実施されることが最も好ましい。さらに、ソフトウェアは、プログラム記憶装置に有形に具体化されたアプリケーションプログラムとして実施することができる。アプリケーションプログラムは、任意の適当なアーキテクチャを含む機械にアップロードし、この機械によって実行することができる。この機械は、1つまたは複数の中央処理装置CPU、ランダムアクセスメモリRAMおよび入出力I/Oインタフェースなどのハードウェアを有するコンピュータプラットフォームで実施されることが好ましい。コンピュータプラットフォームは、オペレーティングシステムおよびマイクロ命令コードも含むことができる。本明細書に記載する様々なプロセスおよび機能は、CPUによって実行することができる、マイクロ命令コードの一部またはアプリケーションプログラムの一部あるいはそれらの任意の組合せの何れかにすることができる。さらに、追加のデータ記憶装置や印刷装置などの、その他の様々な周辺装置をコンピュータプラットフォームに接続することもできる。さらに、添付の図面に示すシステム構成要素および方法の一部はソフトウェアで実施することが好ましいので、システム構成要素間またはプロセス機能ブロック間の実際の接続は、本発明の原理をプログラミングする方法によって異なっていてもよいことも理解されたい。本明細書の教示があれば、当業者なら、本発明の原理の上記の実施態様または構成およびそれらと同様の実施態様または構成を思いつくことができるであろう。本明細書では、添付の図面を参照して例示的な実施形態について述べたが、本発明の原理は、これらの具体的な実施形態に限定されるわけではなく、当業者なら、本発明の原理の範囲または趣旨を逸脱することなく様々な変更および修正をそれらの実施形態に加えることができることを理解されたい。そうした変更および修正は全て、添付の特許請求の範囲に記載する本発明の原理の範囲に含まれるものとする。