(57)【特許請求の範囲】
【請求項１】
ビデオ・シーケンス中のピクチャのオリジナルのバージョンから第１のパッチ・ライブラリを作成し、前記ビデオ・シーケンス中の前記ピクチャの再構築バージョンから第２のパッチ・ライブラリを作成するパッチ・ライブラリ作成器であって、前記第１のパッチ・ライブラリおよび前記第２のパッチ・ライブラリは、それぞれ、前記ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含んでいる、前記パッチ・ライブラリ作成器と、
前記第１のパッチ・ライブラリから前記ピクチャの前記プルーニングされたバージョンを生成するプルナと、
前記ピクチャの前記プルーニングされたバージョンを回復する際に使用するために、前記第２のパッチ・ライブラリからメタデータを生成するメタデータ生成器と、
前記ピクチャの前記プルーニングされたバージョンおよび前記メタデータを符号化するエンコーダと、
を含む装置。
【請求項２】
前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数のブロックに分割し、前記複数のブロックの少なくとも１つを、全ての画素が同じ色値を有するフラットブロックまたは低解像度ブロックでそれぞれ置換することによって生成される、請求項１に記載の装置。
【請求項３】
前記同じ色値は、前記複数のブロックの前記少なくとも１つの中の前記画素の色値の平均に等しい、請求項２に記載の装置。
【請求項４】
前記第１のパッチ・ライブラリは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合うブロックに分割してトレーニング・データ・セットを形成し、前記トレーニング・データ・セットから、前記複数の重なり合うブロックのうち、既定のしきい値を超える高周波数成分を有さないブロックを除去し、前記複数の重なり合うブロックの残りのブロックを複数のクラスタにクラスタリングすることによって作成され、前記複数の重なり合うブロックの前記残りのブロックのそれぞれが、前記複数の高解像度置換パッチのそれぞれ１つを形成する、請求項１に記載の装置。
【請求項５】
前記複数のクラスタのそれぞれ１つの各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数の重なり合うブロックの前記残りのブロックの平均に対応する、請求項４に記載の装置。
【請求項６】
前記複数の重なり合うブロックの前記残りのブロックを、前記クラスタリングの前にダウンサイズして、複数のダウンサイズされた重なり合うブロックを取得し、前記クラスタリングを、前記複数のダウンサイズされた重なり合うブロックに対して実行し、前記複数のクラスタの前記それぞれ１つの前記各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数のダウンサイズされた重なり合うブロックの前記平均に対応する、請求項５に記載の装置。
【請求項７】
前記第２のパッチ・ライブラリに含まれる前記複数の高解像度置換パッチの各々について、前記複数の高解像度置換パッチのそれぞれ１つの平均色を含む特徴ベクトルを生成することによって、署名をそれぞれ作成する、請求項１に記載の装置。
【請求項８】
前記複数の高解像度置換パッチの前記それぞれ１つの前記特徴ベクトルに含まれる前記平均色は、さらに、前記複数の高解像度置換パッチの前記それぞれ１つに対する周囲画素の平均色である、請求項７に記載の装置。
【請求項９】
前記第１のパッチ・ライブラリは複数のパッチ・クラスタを含み、前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合わないブロックに分割し、前記複数の重なり合わないブロックの各々から前記複数のパッチ・クラスタの各々の各中心までのそれぞれの距離メトリクスに基づいて、前記複数の重なり合わないブロックのそれぞれについて、前記複数のパッチ・クラスタの中から候補パッチ・クラスタを探索し、１つまたは複数の基準に基づいて前記候補パッチ・クラスタからベスト・マッチング・パッチを識別し、前記複数の重なり合わないブロックのうちの対応する１つと前記ベスト・マッチング・パッチとの間の差がしきい値差未満であるときに、前記複数の重なり合わないブロックのうちの前記対応する１つをプルーニングして、プルーニングされたブロックを取得することによって生成される、請求項１に記載の装置。
【請求項１０】
前記複数の重なり合わないブロックのうちの前記対応する１つと前記ベスト・マッチング・パッチとの間の前記差が前記しきい値差未満であるときに、前記メタデータは、前記ベスト・マッチング・パッチに関するパッチ指標を含み、前記メタデータは、前記プルーニングされたブロックのブロック識別子をさらに含む、請求項９に記載の装置。
【請求項１１】
ビデオ・シーケンス中のピクチャのオリジナルのバージョンから第１のパッチ・ライブラリを作成し、前記ビデオ・シーケンス中の前記ピクチャの再構築バージョンから第２のパッチ・ライブラリを作成するステップであって、前記第１のパッチ・ライブラリおよび前記第２のパッチ・ライブラリは、それぞれ、前記ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含んでいる、前記ステップと、
前記第１のパッチ・ライブラリから前記ピクチャの前記プルーニングされたバージョンを生成するステップと、
前記ピクチャの前記プルーニングされたバージョンを回復する際に使用するために、前記第２のパッチ・ライブラリからメタデータを生成するステップと、
前記ピクチャの前記プルーニングされたバージョンおよび前記メタデータを符号化するステップと、
を含む方法。
【請求項１２】
前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数のブロックに分割し、前記複数のブロックの少なくとも１つを全ての画素が同じ色値を有するフラットブロックまたは低解像度ブロックでそれぞれ置換することによって生成される、請求項１１に記載の方法。
【請求項１３】
前記同じ色値は、前記複数のブロックの前記少なくとも１つの中の前記画素の色値の平均に等しい、請求項１２に記載の方法。
【請求項１４】
前記第１のパッチ・ライブラリは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合うブロックに分割してトレーニング・データ・セットを形成し、前記トレーニング・データ・セットから、前記複数の重なり合うブロックのうち、既定のしきい値を超える高周波数成分を有さないブロックを除去し、前記複数の重なり合うブロックの残りのブロックを複数のクラスタにクラスタリングすることによって作成され、前記複数の重なり合うブロックの前記残りのブロックのそれぞれが、前記複数の高解像度置換パッチのそれぞれ１つを形成する、請求項１１に記載の方法。
【請求項１５】
前記複数のクラスタのそれぞれ１つの各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数の重なり合うブロックの前記残りのブロックの平均に対応する、請求項１４に記載の方法。
【請求項１６】
前記複数の重なり合うブロックの前記残りのブロックを、前記クラスタリングの前にダウンサイズして、複数のダウンサイズされた重なり合うブロックを取得し、前記クラスタリングを、前記複数のダウンサイズされた重なり合うブロックに対して実行し、前記複数のクラスタの前記それぞれ１つの前記各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数のダウンサイズされた重なり合うブロックの前記平均に対応する、請求項１５に記載の方法。
【請求項１７】
前記第２のパッチ・ライブラリに含まれる前記複数の高解像度置換パッチの各々について、前記複数の高解像度置換パッチのそれぞれ１つの平均色を含む特徴ベクトルを生成することによって、署名をそれぞれ作成する、請求項１１に記載の方法。
【請求項１８】
前記複数の高解像度置換パッチの前記それぞれ１つの前記特徴ベクトルに含まれる前記平均色は、さらに、前記複数の高解像度置換パッチの前記それぞれ１つに対する周囲画素の平均色である、請求項１７に記載の方法。
【請求項１９】
前記第１のパッチ・ライブラリは複数のパッチ・クラスタを含み、前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合わないブロックに分割し、前記複数の重なり合わないブロックの各々から前記複数のパッチ・クラスタの各々の各中心までのそれぞれの距離メトリクスに基づいて、前記複数の重なり合わないブロックのそれぞれについて、前記複数のパッチ・クラスタの中から候補パッチ・クラスタを探索し、１つまたは複数の基準に基づいて前記候補パッチ・クラスタからベスト・マッチング・パッチを識別し、前記複数の重なり合わないブロックのうちの対応する１つと前記ベスト・マッチング・パッチとの間の差がしきい値差未満であるときに、前記複数の重なり合わないブロックのうちの前記対応する１つをプルーニングして、プルーニングされたブロックを取得することによって生成される、請求項１１に記載の方法。
【請求項２０】
前記複数の重なり合わないブロックのうちの前記対応する１つと前記ベスト・マッチング・パッチとの間の前記差が前記しきい値差未満であるときに、前記メタデータは、前記ベスト・マッチング・パッチに関するパッチ指標を含み、前記メタデータは、前記プルーニングされたブロックのブロック識別子をさらに含む、請求項１９に記載の方法。
【請求項２１】
ビデオ・シーケンス中のピクチャのオリジナルのバージョンから第１のパッチ・ライブラリを作成し、前記ビデオ・シーケンス中の前記ピクチャの再構築バージョンから第２のパッチ・ライブラリを作成する手段であって、前記第１のパッチ・ライブラリおよび前記第２のパッチ・ライブラリは、それぞれ、前記ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換するための複数の高解像度置換パッチを含んでいる、前記手段と、
前記第１のパッチ・ライブラリから前記ピクチャの前記プルーニングされたバージョンを生成する手段と、
前記ピクチャの前記プルーニングされたバージョンを回復する際に使用するために、前記第２のパッチ・ライブラリからメタデータを生成する手段と、
前記ピクチャの前記プルーニングされたバージョンおよび前記メタデータを符号化する手段と、
を含む装置。
【請求項２２】
前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数のブロックに分割し、前記複数のブロックの少なくとも１つを全ての画素が同じ色値を有するフラットブロックまたは低解像度ブロックでそれぞれ置換することによって生成される、請求項２１に記載の装置。
【請求項２３】
前記同じ色値は、前記複数のブロックの前記少なくとも１つの中の前記画素の色値の平均に等しい、請求項２２に記載の装置。
【請求項２４】
前記第１のパッチ・ライブラリは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合うブロックに分割してトレーニング・データ・セットを形成し、前記トレーニング・データ・セットから、前記複数の重なり合うブロックのうち、既定のしきい値を超える高周波数成分を有さないブロックを除去し、前記複数の重なり合うブロックの残りのブロックを複数のクラスタにクラスタリングすることによって作成され、前記複数の重なり合うブロックの前記残りのブロックのそれぞれが、前記複数の高解像度置換パッチのそれぞれ１つを形成する、請求項２１に記載の装置。
【請求項２５】
前記複数のクラスタのそれぞれ１つの中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数の重なり合うブロックの前記残りのブロックの平均に対応する、請求項２４に記載の装置。
【請求項２６】
前記複数の重なり合うブロックの前記残りのブロックを、前記クラスタリングの前にダウンサイズして、複数のダウンサイズされた重なり合うブロックを取得し、前記クラスタリングを、前記複数のダウンサイズされた重なり合うブロックに対して実行し、前記複数のクラスタの前記それぞれ１つの前記各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数のダウンサイズされた重なり合うブロックの前記平均に対応する、請求項２５に記載の装置。
【請求項２７】
前記第２のパッチ・ライブラリに含まれる前記複数の高解像度置換パッチの各々について、前記複数の高解像度置換パッチのそれぞれ１つの平均色を含む特徴ベクトルを生成することによって、署名をそれぞれ作成する、請求項２１に記載の装置。
【請求項２８】
前記複数の高解像度置換パッチの前記それぞれ１つの前記特徴ベクトルに含まれる前記平均色は、さらに、前記複数の高解像度置換パッチの前記それぞれ１つに対する周囲画素の平均色である、請求項２７に記載の装置。
【請求項２９】
前記第１のパッチ・ライブラリは複数のパッチ・クラスタを含み、前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合わないブロックに分割し、前記複数の重なり合わないブロックの各々から前記複数のパッチ・クラスタの各々の各中心までのそれぞれの距離メトリクスに基づいて、前記複数の重なり合わないブロックのそれぞれについて、前記複数のパッチ・クラスタの中から候補パッチ・クラスタを探索し、１つまたは複数の基準に基づいて前記候補パッチ・クラスタからベスト・マッチング・パッチを識別し、前記複数の重なり合わないブロックのうちの対応する１つと前記ベスト・マッチング・パッチとの間の差がしきい値差未満であるときに、前記複数の重なり合わないブロックのうちの前記対応する１つをプルーニングして、プルーニングされたブロックを取得することによって生成される、請求項２１に記載の装置。
【請求項３０】
前記複数の重なり合わないブロックのうちの前記対応する１つと前記ベスト・マッチング・パッチとの間の前記差が前記しきい値差未満であるときに、前記メタデータは、前記ベスト・マッチング・パッチに関するパッチ指標を含み、前記メタデータは、前記プルーニングされたブロックのブロック識別子をさらに含む、請求項２９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２０１０年９月１０日出願の「ＥＸＡＭＰＬＥ−ＢＡＳＥＤ  ＤＡＴＡ  ＰＲＵＮＩＮＧ  ＦＯＲ  ＩＭＰＲＯＶＩＮＧ  ＶＩＤＥＯ  ＣＯＭＰＲＥＳＳＩＯＮ  ＥＦＦＩＣＩＥＮＣＹ」と題する米国仮出願第６１／４０３１０８号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００１９３）の利益を主張するものである。
【０００２】
本願は、以下の同時係属の同じ所有者の特許出願に関する。
（１）２０１１年１月２０日出願の「Ａ  ＳＡＭＰＬＩＮＧ−ＢＡＳＥＤ  ＳＵＰＥＲ−ＲＥＳＯＬＵＴＩＯＮ  ＡＰＰＲＯＡＣＨ  ＦＯＲ  ＥＦＦＩＣＥＮＴ  ＶＩＤＥＯ  ＣＯＭＰＲＥＳＳＩＯＮ」と題する国際（ＰＣＴ）特許出願第ＰＣＴ／ＵＳ１１／０００１０７号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００００４）。
（２）２０１１年１月２１日出願の「ＤＡＴＡ  ＰＲＵＮＩＮＧ  ＦＯＲ  ＶＩＤＥＯ  ＣＯＭＰＲＥＳＳＩＯＮ  ＵＳＩＮＧ  ＥＸＡＭＰＬＥ−ＢＡＳＥＤ  ＳＵＰＥＲ−ＲＥＳＯＬＵＴＩＯＮ」と題する国際（ＰＣＴ）特許出願第ＰＣＴ／ＵＳ１１／０００１１７号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１０００１４）。
（３）２０１１年９月ＸＸ日出願の「ＭＥＴＨＯＤＳ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＥＮＣＯＤＩＮＧ  ＶＩＤＥＯ  ＳＩＧＮＡＬＳ  ＵＳＩＮＧ  ＭＯＴＩＯＮ  ＣＯＭＰＥＮＳＡＴＥＤ  ＥＸＡＭＰＬＥＤ−ＢＡＳＥＤ  ＳＵＰＥＲ−ＲＥＳＯＬＵＴＩＯＮ  ＦＯＲ  ＶＩＤＥＯ  ＣＯＭＰＲＥＳＳＩＯＮ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００１９０）。
（４）２０１１年９月ＸＸ日出願の「ＭＥＴＨＯＤＳ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＤＥＣＯＤＩＮＧ  ＶＩＤＥＯ  ＳＩＧＮＡＬＳ  ＵＳＩＮＧ  ＭＯＴＩＯＮ  ＣＯＭＰＥＮＳＡＴＥＤ  ＥＸＡＭＰＬＥ−ＢＡＳＥＤ  ＳＵＰＥＲ−ＲＥＳＯＬＵＴＩＯＮ  ＦＯＲ  ＶＩＤＥＯ  ＣＯＭＰＲＥＳＳＩＯＮ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００２６６）。
（５）２０１１年９月ＸＸ日出願の「ＭＥＴＨＯＤＳ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＤＥＣＯＤＩＮＧ  ＶＩＤＥＯ  ＳＩＧＮＡＬＳ  ＵＳＩＮＧ  ＥＸＡＭＰＬＥ−ＢＡＳＥＤ  ＤＡＴＡ  ＰＲＵＮＩＮＧ  ＦＯＲ  ＩＭＰＲＯＶＥＤ  ＶＩＤＥＯ  ＣＯＭＰＲＥＳＳＩＯＮ  ＥＦＦＩＣＩＥＮＣＹ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００２６７）。
（６）２０１１年９月ＸＸ日出願の「ＭＥＴＨＯＤＳ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＥＮＣＯＤＩＮＧ  ＶＩＤＥＯ  ＳＩＧＮＡＬＳ  ＦＯＲ  ＢＬＯＣＫ−ＢＡＳＥＤ  ＭＩＸＥＤ−ＲＥＳＯＬＵＴＩＯＮ  ＤＡＴＡ  ＰＲＵＮＩＮＧ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００１９４）。
（７）２０１１年９月ＸＸ日出願の「ＭＥＴＨＯＤＳ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＤＥＣＯＤＩＮＧ  ＶＩＤＥＯ  ＳＩＧＮＡＬＳ  ＦＯＲ  ＢＬＯＣＫ−ＢＡＳＥＤ  ＭＩＸＥＤ−ＲＥＳＯＬＵＴＩＯＮ  ＤＡＴＡ  ＰＲＵＮＩＮＧ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００２６８）。
（８）２０１１年９月ＸＸ日出願の「ＭＥＴＨＯＤＳ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＥＦＦＩＣＩＥＮＴ  ＲＥＦＥＲＥＮＣＥ  ＤＡＴＡ  ＥＮＣＯＤＩＮＧ  ＦＯＲ  ＶＩＤＥＯ  ＣＯＭＰＲＥＳＳＩＯＮ  ＢＹ  ＩＭＡＧＥ  ＣＯＮＴＥＮＴ  ＢＡＳＥＤ  ＳＥＡＲＣＨ  ＡＮＤ  ＲＡＮＫＩＮＧ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００１９５）。
（９）２０１１年９月ＸＸ日出願の「ＭＥＴＨＯＤ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＥＦＦＩＣＩＥＮＴ  ＲＥＦＥＲＥＮＣＥ  ＤＡＴＡ  ＤＥＣＯＤＩＮＧ  ＦＯＲ  ＶＩＤＥＯ  ＣＯＭＰＲＥＳＳＩＯＮ  ＢＹ  ＩＭＡＧＥ  ＣＯＮＴＥＮＴ  ＢＡＳＥＤ  ＳＥＡＲＣＨ  ＡＮＤ  ＲＡＮＫＩＮＧ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１１０１０６）。
（１０）２０１１年９月ＸＸ日出願の「ＭＥＴＨＯＤ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＥＮＣＯＤＩＮＧ  ＶＩＤＥＯ  ＳＩＧＮＡＬＳ  ＦＯＲ  ＥＸＡＭＰＬＥ−ＢＡＳＥＤ  ＤＡＴＡ  ＰＲＵＮＩＮＧ  ＵＳＩＮＧ  ＩＮＴＲＡ−ＦＲＡＭＥ  ＰＡＴＣＨ  ＳＩＭＩＬＡＲＩＴＹ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００１９６）。
（１１）２０１１年９月ＸＸ日出願の「ＭＥＴＨＯＤ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＤＥＣＯＤＩＮＧ  ＶＩＤＥＯ  ＳＩＧＮＡＬＳ  ＷＩＴＨ  ＥＸＡＭＰＬＥ−ＢＡＳＥＤ  ＤＡＴＡ  ＰＲＵＮＩＮＧ  ＵＳＩＮＧ  ＩＮＴＲＡ−ＦＲＡＭＥ  ＰＡＴＣＨ  ＳＩＭＩＬＡＲＩＴＹ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００２６９）。
（１２）２０１１年９月ＸＸ日出願の「ＰＲＵＮＩＮＧ  ＤＥＣＩＳＩＯＮ  ＯＰＴＩＭＩＺＡＴＩＯＮ  ＩＮ  ＥＸＡＭＰＬＥ−ＢＡＳＥＤ  ＤＡＴＡ  ＰＲＵＮＩＮＧ  ＣＯＭＰＲＥＳＳＩＯＮ」と題する国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１０１９７）。
【０００３】
本原理は、概ねビデオの符号化および復号に関し、より詳細には、ビデオ圧縮効率を改善する事例ベース（ｅｘａｍｐｌｅ−ｂａｓｅｄ）のデータ・プルーニング（ｐｒｕｎｉｎｇ）を行う方法および装置に関する。
【背景技術】
【０００４】
データ・プルーニングは、入力ビデオ・データを符号化する前にそのビデオ・データの一部分を除去することによってより高いビデオ符号化効率を達成するビデオ前処理技術である。除去されたビデオ・データは、デコーダ側で、復号データから除去されたビデオ・データを推測することによって回復される。データ・プルーニングを用いて圧縮効率を高めることに関しては、従来いくつかの努力がなされている。例えば、第１の手法（Ａ．ＤｕｍｉｔｒａｓおよびＢ．Ｇ．Ｈａｓｋｅｌｌによる「Ａ  Ｔｅｘｔｕｒｅ  Ｒｅｐｌａｃｅｍｅｎｔ  Ｍｅｔｈｏｄ  ａｔ  ｔｈｅ  Ｅｎｃｏｄｅｒ  ｆｏｒ  Ｂｉｔ  Ｒａｔｅ  Ｒｅｄｕｃｔｉｏｎ  ｏｆ  Ｃｏｍｐｒｅｓｓｅｄ  Ｖｉｄｅｏ」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙ、Ｖｏｌ．１３、Ｎｏ．２、２００３年２月、ｐ．１６３〜１７５に記載）および第２の手法（Ａ．ＤｕｍｉｔｒａｓおよびＢ．Ｇ．Ｈａｓｋｅｌｌによる「Ａｎ  ｅｎｃｏｄｅｒ−ｄｅｃｏｄｅｒ  ｔｅｘｔｕｒｅ  ｒｅｐｌａｃｅｍｅｎｔ  ｍｅｔｈｏｄ  ｗｉｔｈ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｃｏｎｔｅｎｔ−ｂａｓｅｄ  ｍｏｖｉｅ  ｃｏｄｉｎｇ」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙ、Ｖｏｌ．１４、ｉｓｓｕｅ  ６、２００４年６月、ｐ．８２５〜８４０に記載）では、テクスチャ置換に基づく方法を使用して、エンコーダ側で複数のテクスチャ領域を除去し、デコーダ側でそれらのテクスチャ領域を再合成する。通常の変換係数よりデータ量の少ない合成パラメータだけがデコーダに送信されるので、圧縮効率が高くなる。
【０００５】
第３の手法（Ｃ．Ｚｈｕ、Ｘ．Ｓｕｎ、Ｆ．ＷｕおよびＨ．Ｌｉによる「Ｖｉｄｅｏ  Ｃｏｄｉｎｇ  ｗｉｔｈ  Ｓｐａｔｉｏ−Ｔｅｍｐｏｒａｌ  Ｔｅｘｔｕｒｅ  Ｓｙｎｔｈｅｓｉｓ」、ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  ａｎｄ  Ｅｘｐｏ（ＩＣＭＥ）、２００７年に記載）および第４の手法（Ｃ．Ｚｈｕ、Ｘ．Ｓｕｎ、Ｆ．ＷｕおよびＨ．Ｌｉによる「Ｖｉｄｅｏ  ｃｏｄｉｎｇ  ｗｉｔｈ  ｓｐａｔｉｏ−ｔｅｍｐｏｒａｌ  ｔｅｘｔｕｒｅ  ｓｙｎｔｈｅｓｉｓ  ａｎｄ  ｅｄｇｅ−ｂａｓｅｄ  ｉｎｐａｉｎｔｉｎｇ」、ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  ａｎｄ  Ｅｘｐｏ（ＩＣＭＥ）、２００８年に記載）では、エンコーダ側で、空間時間的テクスチャ合成およびエッジに基づくインペインティング（ｉｎｐａｉｎｔｉｎｇ）を用いて領域の一部を除去し、デコーダ側で、領域マスクなどのメタデータを援用して除去されたコンテンツを回復する。ただし、第３の手法および第４の手法では、エンコーダ／デコーダが領域マスクを用いて一部の領域について選択的に符号化／復号を実行することができるように、エンコーダおよびデコーダを修正する必要がある。従って、第３の手法および第４の手法を実行することができるようになるにはエンコーダおよびデコーダを修正する必要があるので、これは厳密にはアウト・オブ・ループ（ｏｕｔ−ｏｆ−ｌｏｏｐ）な手法ではない。第５の手法（Ｄｕｎｇ  Ｔ．Ｖｏ、Ｊｏｅｌ  Ｓｏｌｅ、Ｐｅｎｇ  Ｙｉｎ、Ｃｒｉｓｔｉｎａ  ＧｏｍｉｌａおよびＴｒｕｏｎｇ  Ｑ．Ｎｇｕｙｅｎによる「Ｄａｔａ  Ｐｒｕｎｉｎｇ−Ｂａｓｅｄ  Ｃｏｍｐｒｅｓｓｉｏｎ  ｕｓｉｎｇ  Ｈｉｇｈ  Ｏｒｄｅｒ  Ｅｄｇｅ−Ｄｉｒｅｃｔｅｄ  Ｉｎｔｅｒｐｏｌａｔｉｏｎ」、ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｃｏｕｓｔｉｃｓ、Ｓｐｅｅｃｈ  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ、Ｔａｉｗａｎ、Ｒ．Ｏ．Ｃ．、２００９年に記載）では、最小二乗最小化フレームワークを用いてビデオ中の水平線または垂直線の一部を選択的に除去することによってより小さなサイズにビデオを倍率変更する、線除去に基づく方法が提案されている。第５の手法は、アウト・オブ・ループな手法であり、エンコーダ／デコーダの修正を必要としない。ただし、一部の水平線および垂直線を完全に除去してしまうと、ビデオによっては情報または細部が失われることになる可能性がある。
【０００６】
さらに、ビデオ圧縮のためのデータ・プルーニングに関しては、いくつかの予備研究が行われている。例えば、第６の手法（２０１０年２月８日にＩＣＩＰ  ２０１０に提出され、２０１０年１月２２日に同時係属の同じ所有者の米国仮特許出願（第６１／２９７３２０号）（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００００４）として出願された、Ｓｉｔａｒａｍ  Ｂｈａｇａｖａｔｈｙ、Ｄｏｎｇ−Ｑｉｎｇ  ＺｈａｎｇおよびＭｉｔｈｕｎ  Ｊａｃｏｂによる「Ａ  Ｄａｔａ  Ｐｒｕｎｉｎｇ  Ａｐｐｒｏａｃｈ  ｆｏｒ  Ｖｉｄｅｏ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｕｓｉｎｇ  Ｍｏｔｉｏｎ−Ｇｕｉｄｅｄ  Ｄｏｗｎ−ｓａｍｐｌｉｎｇ  ａｎｄ  Ｓｕｐｅｒ−ｒｅｓｏｌｕｔｉｏｎ」に記載）では、サンプリングに基づく超解像度を用いたデータ・プルーニング方法が提示されている。フル解像度フレームをサンプリングして、それより小さなサイズのいくつかのフレームにすることにより、オリジナルのビデオの空間的サイズを縮小する。デコーダ側では、エンコーダ側から受信したメタデータを援用して、ダウン・サンプリングされたフレームから高解像度フレームを再合成する。第７の手法（２０１０年１月２２日に同時係属の同じ所有者の米国仮特許出願（第６１／３３６５１６号）（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１０００１４）として出願された、Ｄｏｎｇ−Ｑｉｎｇ  Ｚｈａｎｇ、Ｓｉｔａｒａｍ  ＢｈａｇａｖａｔｈｙおよびＪｏａｎ  Ｌｌａｃｈによる「Ｄａｔａ  ｐｒｕｎｉｎｇ  ｆｏｒ  ｖｉｄｅｏ  ｃｏｍｐｒｅｓｓｉｏｎ  ｕｓｉｎｇ  ｅｘａｍｐｌｅ−ｂａｓｅｄ  ｓｕｐｅｒ−ｒｅｓｏｌｕｔｉｏｎ」に記載）では、事例ベースの超解像度に基づくデータ・プルーニング方法が提示されている。オリジナルのビデオから代表パッチ・ライブラリをトレーニングする。その後、ビデオをそれより小さなサイズにダウンサイズする。ダウンサイズされたビデオおよびパッチ・ライブラリを、デコーダ側に送信する。デコーダ側での回復プロセスでは、パッチ・ライブラリを用いて事例ベースの超解像度によってダウンサイズされたビデオの超解像度化（ｓｕｐｅｒ−ｒｅｓｏｌｖｅ）を行う。ただし、パッチ・ライブラリとダウンサイズされたフレームとの間にかなりの冗長性があるので、第７の手法では、高いレベルの圧縮の向上が容易には得られないこともあることが分かっている。
【０００７】
本願は、ビデオ圧縮効率を改善する事例ベースのデータ・プルーニングを行う方法および装置を開示するものである。
【０００８】
本発明の原理の一態様によれば、ビデオ・シーケンス中のピクチャを符号化する装置が提供される。この装置は、ピクチャのオリジナルのバージョンから第１のパッチ・ライブラリを作成し、ピクチャの再構築バージョンから第２のパッチ・ライブラリを作成するパッチ・ライブラリ作成器を含む。第１のパッチ・ライブラリおよび第２のパッチ・ライブラリは、それぞれ、ピクチャのプルーニングされた（ｐｒｕｎｅｄ）バージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含む。この装置は、第１のパッチ・ライブラリからピクチャのプルーニングされたバージョンを生成するプルナ（ｐｒｕｎｅｒ）、および、第２のパッチ・ライブラリからメタデータを生成するメタデータ生成器も含む。メタデータは、ピクチャのプルーニングされたバージョンを回復するためのものである。この装置は、ピクチャのプルーニングされたバージョンおよびメタデータを符号化するエンコーダをさらに含む。
【０００９】
本発明の原理の別の態様によれば、ビデオ・シーケンス中のピクチャを符号化する方法が提供される。この方法は、ピクチャのオリジナルのバージョンから第１のパッチ・ライブラリを作成し、ピクチャの再構築バージョンから第２のパッチ・ライブラリを作成するステップを含む。第１のパッチ・ライブラリおよび第２のパッチ・ライブラリは、それぞれ、ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含む。この方法は、第１のパッチ・ライブラリからピクチャのプルーニングされたバージョンを生成するステップ、および、第２のパッチ・ライブラリからメタデータを生成するステップも含む。メタデータは、ピクチャのプルーニングされたバージョンを回復するためのものである。この方法は、ピクチャのプルーニングされたバージョンおよびメタデータを符号化するステップをさらに含む。
【００１０】
本発明の原理のさらに別の態様によれば、ビデオ・シーケンス中のピクチャのプルーニングされたバージョンを回復する装置が提供される。この装置は、ピクチャのプルーニングされたバージョンを複数の重なり合わないブロックに分割する分割器と、ピクチャのプルーニングされたバージョンを回復する際に使用されるメタデータを復号するメタデータ・デコーダとを含む。この装置は、ピクチャの再構築バージョンからパッチ・ライブラリを作成するパッチ・ライブラリ作成器も含む。パッチ・ライブラリは、ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含む。この装置は、メタデータを用いた探索プロセスを実行して、上記の複数の重なり合わないブロックのうちの１つまたは複数のプルーニングされたブロックのそれぞれに対応するパッチを見つけ、これらの１つまたは複数のプルーニングされたブロックのそれぞれを対応するパッチで置換する探索／置換装置をさらに含む。
【００１１】
本発明の原理のさらなる態様によれば、ビデオ・シーケンス中のピクチャのプルーニングされたバージョンを回復する方法が提供される。この方法は、ピクチャのプルーニングされたバージョンを複数の重なり合わないブロックに分割するステップと、ピクチャのプルーニングされたバージョンを回復する際に使用されるメタデータを復号するステップとを含む。この方法は、ピクチャの再構築バージョンからパッチ・ライブラリを作成するステップも含む。パッチ・ライブラリは、ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含む。この方法は、メタデータを用いた探索プロセスを実行して、上記の複数の重なり合わないブロックのうちの１つまたは複数のプルーニングされたブロックのそれぞれに対応するパッチを見つけ、これらの１つまたは複数のプルーニングされたブロックのそれぞれを対応するパッチで置換するステップをさらに含む。
【００１２】
本発明の原理の別のさらなる態様によれば、ビデオ・シーケンス中のピクチャを符号化する装置が提供される。この装置は、ピクチャのオリジナルのバージョンから第１のパッチ・ライブラリを作成し、ピクチャの再構築バージョンから第２のパッチ・ライブラリを作成する手段を含む。第１のパッチ・ライブラリおよび第２のパッチ・ライブラリは、それぞれ、ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含む。この装置は、第１のパッチ・ライブラリからピクチャのプルーニングされたバージョンを生成する手段、および、第２のパッチ・ライブラリからメタデータを生成する手段も含み、メタデータは、ピクチャのプルーニングされたバージョンを回復するためのものである。この装置は、ピクチャのプルーニングされたバージョンおよびメタデータを符号化する手段をさらに含む。
【００１３】
本発明の原理の追加の態様によれば、ビデオ・シーケンス中のピクチャのプルーニングされたバージョンを回復する装置が提供される。この装置は、ピクチャのプルーニングされたバージョンを複数の重なり合わないブロックに分割する手段と、ピクチャのプルーニングされたバージョンを回復する際に使用されるメタデータを復号する手段とを含む。この装置は、ピクチャの再構築バージョンからパッチ・ライブラリを作成する手段も含む。パッチ・ライブラリは、ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含む。この装置は、メタデータを用いた探索プロセスを実行して、上記の複数の重なり合わないブロックのうちの１つまたは複数のプルーニングされたブロックのそれぞれに対応するパッチを見つけ、これらの１つまたは複数のプルーニングされたブロックのそれぞれを対応するパッチで置換する手段をさらに含む。
【００１４】
本発明の原理の上記その他の態様、特徴および利点は、以下の例示的な実施形態の詳細な説明を添付の図面と関連付けて読めば明らかになるであろう。
【００１５】
本発明の原理は、以下の例示的な図面によってよりよく理解することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の原理の一実施形態による、パッチ類似性を用いる例示的な事例ベースのデータ・プルーニング・システムを示すブロック図である。
【図２】本発明の原理の一実施形態による、本発明の原理を適用することができる例示的なビデオ・エンコーダを示すブロック図である。
【図３】本発明の原理の一実施形態による、本発明の原理を適用することができる例示的なビデオ・デコーダを示すブロック図である。
【図４】本発明の原理の一実施形態による、事例ベースのデータ・プルーニング・システムのエンコーダ側処理を実行する例示的な第１の部分を示すブロック図である。
【図５】本発明の原理の一実施形態による、クラスタリングおよびパッチ・ライブラリ作成の例示的な方法を示す流れ図である。
【図６】本発明の原理の一実施形態による、例示的なパッチ・ライブラリおよび対応するクラスタを示す図である。
【図７】本発明の原理の一実施形態による、例示的な署名ベクトルを示す図である。
【図８】本発明の原理の一実施形態による、パッチ類似性を用いる事例ベースのデータ・プルーニング・システムのエンコーダ側処理を実行する例示的な第２の部分を示すブロック図である。
【図９】本発明の原理の一実施形態による、ビデオ・フレーム・プルーニングの例示的な方法を示す流れ図である。
【図１０】本発明の原理の一実施形態による、パッチ探索プロセスを示す図である。
【図１１】本発明の原理の一実施形態による、例示的な混合解像度フレームを示す画像である。
【図１２】本発明の原理の一実施形態による、メタデータを符号化する例示的な方法を示す流れ図である。
【図１３】本発明の原理の一実施形態による、プルーニングされたブロックＩＤを符号化する例示的な方法を示す流れ図である。
【図１４】本発明の原理の一実施形態による、パッチ指標を符号化する例示的な方法を示す流れ図である。
【図１５】本発明の原理の一実施形態による、パッチ指標を復号する例示的な方法を示す流れ図である。
【図１６】本発明の原理の一実施形態による、例示的なブロックＩＤを示す図である。
【図１７】本発明の原理の一実施形態による、後続フレームをプルーニングする例示的な方法を示す流れ図である。
【図１８】本発明の原理の一実施形態による、プルーニングされたブロックの例示的な動きベクトルを示す図である。
【図１９】本発明の原理の一実施形態による、メタデータを復号する例示的な方法を示す流れ図である。
【図２０】本発明の原理の一実施形態による、プルーニングされたブロックＩＤを復号する例示的な方法を示す流れ図である。
【図２１】本発明の原理の一実施形態による、事例ベースのデータ・プルーニングのデコーダ側処理を実行する例示的な装置を示すブロック図である。
【図２２】本発明の原理の一実施形態による、プルーニングされたフレームを回復する例示的な方法を示す流れ図である。
【図２３】本発明の原理の一実施形態による、後続フレームを回復する例示的な方法を示す流れ図である。
【発明を実施するための形態】
【００１７】
本発明の原理は、ビデオ圧縮効率を改善するための事例ベースのデータ・プルーニングを行う方法および装置を対象としている。
【００１８】
本明細書は、本発明の原理を例示するものである。従って、本明細書に明示的に記述または図示していなくても、本発明の原理を具体化し、本発明の原理の趣旨および範囲に含まれる様々な構成を、当業者なら考案することができることを理解されたい。
【００１９】
本明細書に記載された全ての例および条件に関する表現は、本発明の原理と、当技術分野をさらに進歩させるために発明者（等）が与える概念とを、読者が理解するのを助けるという教授的な目的を有するものであって、これらの具体的に記載された例および条件に限定されないものと解釈されたい。
【００２０】
さらに、本発明の原理の原理、態様および実施形態、ならびにその具体的な例について本明細書で記載する全ての記述は、その構造的な均等物および機能的な均等物の両方を含むものとする。さらに、これらの均等物には、現在既知の均等物だけでなく、将来開発されるであろう均等物も含まれる、すなわち、構造に関わらず、同じ機能を実行する開発される任意の要素も含まれるものとする。
【００２１】
従って、例えば、当業者なら、本明細書に示すブロック図が本発明の原理を具体化する例示的な回路の概念図を表していることを理解するであろう。同様に、任意のフローチャート、流れ図、状態遷移図、擬似コードなどが、コンピュータ可読媒体中に実質的に表現され、明示してある場合もしていない場合もあるコンピュータまたはプロセッサによって実質的に実行され得る様々なプロセスを表すことも理解されたい。
【００２２】
図面に示す様々な要素の機能は、専用のハードウェアを使用することによって、またソフトウェアを実行することができるハードウェアを適当なソフトウェアと関連付けて使用することによって、実現することができる。プロセッサによってそれらの機能を実現するときには、単一の専用プロセッサで実現することも、単一の共用プロセッサで実現することも、あるいはその一部を共用することもできる複数の個別プロセッサで実現することもできる。さらに、「プロセッサ」または「制御装置」という用語を明示的に用いていても、ソフトウェアを実行することができるハードウェアのみを指していると解釈すべきではなく、ディジタル信号プロセッサ（「ＤＳＰ」）ハードウェア、ソフトウェアを記憶するための読取り専用メモリ（「ＲＯＭ」）、ランダム・アクセス・メモリ（「ＲＡＭ」）および不揮発性記憶装置（ただしこれらに限定されない）を黙示的に含むことがある。
【００２３】
従来の、且つ／または特注のその他ハードウェアも含まれることがある。同様に、図面に示す任意のスイッチも、概念的なものに過ぎない。それらの機能は、プログラム論理の動作によっても、専用論理によっても、プログラム制御と専用論理の相互作用によっても、あるいは手作業でも実施することができ、実施者が、前後関係から適宜判断して特定の技術を選択することができる。
【００２４】
本明細書の特許請求の範囲において、特定の機能を実行する手段として表現されている任意の要素は、当該機能を実行する任意の形態を含むものとする。例えば、（ａ）当該機能を実行する回路素子の組合せや、（ｂ）ファームウェア、マイクロコードなども含めた任意の形態のソフトウェアを、当該ソフトウェアを実行して当該機能を実行する適当な回路と組み合わせたものなども含むものとする。特許請求の範囲によって定義される本発明の原理は、記載された様々な手段が実施する機能を、特許請求の範囲が要求する形式で組み合わせ、まとめることにある。従って、これらの機能を実施することができる任意の手段を、本明細書に示す手段の均等物とみなすものとする。
【００２５】
本明細書において、本発明の原理の「１つの実施形態」または「一実施形態」、ならびにその他の変形表現に言及している場合、それは、当該実施形態に関連して述べられる特定の特性、構造、特徴などが、本発明の原理の少なくとも１つの実施形態に含まれるという意味である。従って、本明細書の様々な箇所に見られる「１つの実施形態において」または「一実施形態において」という表現、ならびに任意の他の変形表現は、その全てが必ずしも同じ実施形態のことを指しているわけではない。
【００２６】
例えば、「Ａ／Ｂ」、「Ａおよび／またはＢ」ならびに「ＡおよびＢの少なくとも１つ」の場合など、「／」、「および／または」ならびに「の少なくとも１つ」の何れかを使用している場合、それは、１番目に挙げた選択肢（Ａ）のみを選択すること、または２番目に挙げた選択肢（Ｂ）のみを選択すること、または両方の選択肢（ＡおよびＢ）を選択することを含むということであることを理解されたい。さらなる例として、「Ａ、Ｂおよび／またはＣ」ならびに「Ａ、ＢおよびＣの少なくとも１つ」の場合には、この表現は、１番目に挙げた選択肢（Ａ）のみを選択すること、または２番目に挙げた選択肢（Ｂ）のみを選択すること、または３番目に挙げた選択肢（Ｃ）のみを選択すること、または１番目と２番目に挙げた選択肢（ＡおよびＢ）のみを選択すること、または１番目と３番目に挙げた選択肢（ＡおよびＣ）のみを選択すること、または２番目と３番目に挙げた選択肢（ＢおよびＣ）のみを選択すること、または３つ全ての選択肢（ＡおよびＢおよびＣ）を選択することを含むということである。当技術分野および関連技術分野の当業者には容易に分かるように、このことは、列挙されている項目の数に応じて拡張することができる。
【００２７】
また、本明細書で使用する「ピクチャ」および「画像」という用語は入れ替えて使用してもよく、ビデオ・シーケンスの静止画像またはピクチャを指している。既知の通り、ピクチャは、フレームであってもフィールドであってもよい。
【００２８】
図１を参照すると、例示的な事例ベースのデータ・プルーニング・システムの全体が、参照番号１００で示されている。プルーニング・システム１００は、ビデオ・エンコーダ１１０の入力部およびメタデータ生成器／エンコーダ１３５の第１の入力部に信号通信で接続された出力部を有するプルナ（ｐｒｕｎｅｒ）１０５を含む。ビデオ・エンコーダの出力部は、ビデオ・デコーダ１１５の入力部およびパッチ・ライブラリ作成器１４０の入力部に信号通信で接続されている。ビデオ・デコーダ１１５の出力部は、回復装置１２０の第１の入力部に信号通信で接続されている。パッチ・ライブラリ作成器１３０の出力部は、回復装置１２０の第２の入力部に信号通信で接続されている。メタデータ生成器／エンコーダ１３５の出力部は、メタデータ・デコーダ１２５の入力部に信号通信で接続されている。メタデータ・デコーダ１２５の出力部は、回復装置１２０の第３の入力部に信号通信で接続されている。パッチ・ライブラリ作成器１４０の出力部は、メタデータ生成器／エンコーダ１３５の第２の入力部に信号通信で接続されている。クラスタリング装置／パッチ・ライブラリ作成器１４５の出力部は、プルナ１０５の第２の入力部に信号通信で接続されている。プルナ１０５の入力部およびクラスタリング装置／パッチ・ライブラリ作成器１４５の入力部は、プルーニング・システム１００の、入力ビデオを受信する入力部として利用することができる。回復装置の出力部は、プルーニング・システム１００の、ビデオを出力する出力部として利用することができる。
【００２９】
図２を参照すると、本発明の原理を適用することができる例示的なビデオ・エンコーダの全体が、参照番号２００で示されている。ビデオ・エンコーダ２００は、結合器２８５の非反転入力部と信号通信する出力部を有するフレーム順序付けバッファ２１０を含む。結合器２８５の出力部は、変換器／量子化器２２５の第１の入力部に信号通信で接続されている。変換器／量子化器２２５の出力部は、エントロピ・コーダ２４５の第１の入力部および逆変換器／逆量子化器２５０の第１の入力部に信号通信で接続されている。エントロピ・コーダ２４５の出力部は、結合器２９０の第１の非反転入力部に信号通信で接続されている。結合器２９０の出力部は、出力バッファ２３５の第１の入力部に信号通信で接続されている。
【００３０】
エンコーダ制御装置２０５の第１の出力部は、フレーム順序付けバッファ２１０の第２の入力部、逆変換器／逆量子化器２５０の第２の入力部、ピクチャ・タイプ判断モジュール２１５の入力部、マクロブロック・タイプ（ＭＢタイプ）判断モジュール２２０の第１の入力部、イントラ予測モジュール２６０の第２の入力部、デブロッキング・フィルタ２６５の第２の入力部、動き補償器２７０の第１の入力部、動き推定器２７５の第１の入力部、および参照ピクチャ・バッファ２８０の第２の入力部に信号通信で接続されている。
【００３１】
エンコーダ制御装置２０５の第２の出力部は、付加拡張情報（ＳＥＩ）挿入器２３０の第１の入力部、変換器／量子化器２２５の第２の入力部、エントロピ・コーダ２４５の第２の入力部、出力バッファ２３５の第２の入力部、およびシーケンス・パラメータ・セット（ＳＰＳ）／ピクチャ・パラメータ・セット（ＰＰＳ）挿入器２４０の入力部に信号通信で接続されている。
【００３２】
ＳＥＩ挿入器２３０の出力部は、結合器２９０の第２の非反転入力部に信号通信で接続されている。
【００３３】
ピクチャ・タイプ判断モジュール２１５の第１の出力部は、フレーム順序付けバッファ２１０の第３の入力部に信号通信で接続されている。ピクチャ・タイプ判断モジュール２１５の第２の出力部は、マクロブロック・タイプ判断モジュール２２０の第２の入力部に信号通信で接続されている。
【００３４】
シーケンス・パラメータ・セット（ＳＰＳ）／ピクチャ・パラメータ・セット（ＰＰＳ）挿入器２４０の出力部は、結合器２９０の第３の非反転入力部に信号通信で接続されている。
【００３５】
逆量子化器／逆変換器２５０の出力部は、結合器２１９の第１の非反転入力部に信号通信で接続されている。結合器２１９の出力部は、イントラ予測モジュール２６０の第１の入力部およびデブロッキング・フィルタ２６５の第１の入力部に信号通信で接続されている。デブロッキング・フィルタ２６５の出力部は、参照ピクチャ・バッファ２８０の第１の入力部に信号通信で接続されている。参照ピクチャ・バッファ２８０の出力部は、動き推定器２７５の第２の入力部および動き補償器２７０の第３の入力部に信号通信で接続されている。動き推定器２７５の第１の出力部は、動き補償器２７０の第２の入力部に信号通信で接続されている。動き推定器２７５の第２の出力部は、エントロピ・コーダ２４５の第３の入力部に信号通信で接続されている。
【００３６】
動き補償器２７０の出力部は、スイッチ２９７の第１の入力部に信号通信で接続されている。イントラ予測モジュール２６０の出力部は、スイッチ２９７の第２の入力部に信号通信で接続されている。マクロブロック・タイプ判断モジュール２２０の出力部は、スイッチ２９７の第３の入力部に信号通信で接続されている。スイッチ２９７の第３の入力部は、スイッチの「データ」入力（「データ」入力とは、制御入力すなわち第３の入力に対する呼称）が、動き補償器２７０またはイントラ予測モジュール２６０によって与えられるか否かを判定するものである。スイッチ２９７の出力部は、結合器２１９の第２の非反転入力部および結合器２８５の反転入力部に信号通信で接続されている。
【００３７】
フレーム順序付けバッファ２１０の第１の入力部およびエンコーダ制御装置２０５の入力部は、エンコーダ２００の、入力ピクチャを受信する入力部として利用することができる。さらに、付加拡張情報（ＳＥＩ）挿入器２３０の第２の入力部は、エンコーダ２００の、メタデータを受信する入力部として利用することができる。出力バッファ２３５の出力部は、エンコーダ２００の、ビットストリームを出力する出力部として利用することができる。
【００３８】
図３を参照すると、本発明の原理を適用することができる例示的なビデオ・デコーダの全体が、参照番号３００で示されている。ビデオ・デコーダ３００は、エントロピ・デコーダ３４５の第１の入力部に信号通信で接続された出力部を有する入力バッファ３１０を含む。エントロピ・デコーダ３４５の第１の出力部は、逆変換器／逆量子化器３５０の第１の入力部に信号通信で接続されている。逆変換器／逆量子化器３５０の出力部は、結合器３２５の第２の非反転入力部に信号通信で接続されている。結合器３２５の出力部は、デブロッキング・フィルタ３６５の第２の入力部およびイントラ予測モジュール３６０の第１の入力部に信号通信で接続されている。デブロッキング・フィルタ３６５の第２の出力部は、参照ピクチャ・バッファ３８０の第１の入力部に信号通信で接続されている。参照ピクチャ・バッファ３８０の出力部は、動き補償器３７０の第２の入力部に信号通信で接続されている。
【００３９】
エントロピ・デコーダ３４５の第２の出力部は、動き補償器３７０の第３の入力部、デブロッキング・フィルタ３６５の第１の入力部、およびイントラ予測器３６０の第３の入力部に信号通信で接続されている。エントロピ・デコーダ３４５の第３の出力部は、デコーダ制御装置３０５の入力部に信号通信で接続されている。デコーダ制御装置３０５の第１の出力部は、エントロピ・デコーダ３４５の第２の入力部に信号通信で接続されている。デコーダ制御装置３０５の第２の出力部は、逆変換器／逆量子化器３５０の第２の入力部に信号通信で接続されている。デコーダ制御装置３０５の第３の出力部は、デブロッキング・フィルタ３６５の第３の入力部に信号通信で接続されている。デコーダ制御装置３０５の第４の出力部は、イントラ予測モジュール３６０の第２の入力部、動き補償器３７０の第１の入力部、および参照ピクチャ・バッファ３８０の第２の入力部に信号通信で接続されている。
【００４０】
動き補償器３７０の出力部は、スイッチ３９７の第１の入力部に信号通信で接続されている。イントラ予測モジュール３６０の出力部は、スイッチ３９７の第２の入力部に信号通信で接続されている。スイッチ３９７の出力部は、結合器３２５の第１の非反転入力部に信号通信で接続されている。
【００４１】
入力バッファ３１０の入力部は、デコーダ３００の、入力ビットストリームを受信する入力部として利用することができる。デブロッキング・フィルタ３６５の第１の出力部は、デコーダ３００の、出力ピクチャを出力する出力部として利用することができる。
【００４２】
上述のように、本発明の原理は、ビデオ圧縮効率を改善するための事例ベースのデータ・プルーニングを行う方法および装置を対象としている。本発明の原理は、前述の第７の手法に対して改善をもたらすので有利である。すなわち、本願は、第７の手法のように通信チャネルを介してパッチ・ライブラリを送信するのではなく、以前に送信されたフレームまたは既存のフレームを用いてデコーダ側においてパッチ・ライブラリをトレーニングするという概念を開示する。また、データ・プルーニングは、入力フレーム中のいくつかのブロックをフラット領域（ｆｌａｔ  ｒｅｇｉｏｎ）で置換して「混合解像度」フレームを作成することによって実現される。
【００４３】
一実施形態では、本発明の原理は、トレーニング画像／フレームのプールからトレーニングしたパッチ例ライブラリを使用してビデオをプルーニングし、プルーニングされたビデオを回復することを実現するので有利である。パッチ例ライブラリは、参照フレームの概念を拡張したものと考えることができる。従って、パッチ例ライブラリの考えは、従来のビデオ符号化方法でも使用することができる。一実施形態では、本発明の原理は、ライブラリで効率的にパッチを探索するために誤差限界（ｅｒｒｏｒ−ｂｏｕｎｄｅｄ）クラスタリング（例えば修正Ｋ平均クラスタリング）を使用する。
【００４４】
さらに、一実施形態では、本発明の原理は、複数のブロックをフラット・ブロック（ｆｌａｔ  ｂｌｏｃｋ）で置換して高周波信号を低減して圧縮効率を向上させる、混合解像度データ・プルーニング方式を提供するので有利である。メタデータ（ライブラリ中のベスト・マッチ・パッチ位置）符号化の効率を向上させるために、本発明の原理は、パッチ署名マッチング、マッチング・ランク・リストおよびランク番号符号化を使用する。
【００４５】
さらに、一実施形態では、本発明の原理は、色の変化に基づくフラット・ブロック識別方式を用いてプルーニングされたブロックＩＤを符号化するストラテジを提供するので有利である。
【００４６】
このように、本発明の原理によれば、入力ビデオをビデオ・エンコーダがより効率的に符号化することができるように入力ビデオをプルーニングするための、本明細書で事例ベースのデータ・プルーニングと呼ぶ、新規の方法が提供される。一実施形態では、この方法は、例としてのパッチのライブラリを作成し、このパッチ・ライブラリを使用して、その中の一部のブロックが低解像度ブロックまたはフラット・ブロックで置換されたビデオ・フレームを回復することを含む。この枠組みは、パッチ・ライブラリを作成し、ビデオをプルーニングし、ビデオを回復し、ならびに回復に必要なメタデータを符号化する方法を含む。
【００４７】
図１を参照すると、エンコーダ側の処理は、基本的に、２つの部分、すなわちパッチ・ライブラリ作成およびプルーニングを含む。パッチ・ライブラリは、既にデコーダ側に送信されている以前のフレーム（オリジナルのビデオ・フレームまたは符号化され復号されたフレーム）を使用して、あるいはエンコーダ側とデコーダ側の両方で共有している、またはエンコーダ側とデコーダ側の両方がアクセスすることができるいくつかのビデオ（例えばＹＯＵＴＵＢＥ．ＣＯＭのビデオ）を使用して、作成することができる。本明細書に開示する好ましい実施形態では、以前から存在しているフレームを使用して、パッチ・ライブラリを作成する。パッチ・ライブラリは、デコーダ側でも、以前に復号されたフレームを用いて生成される。エンコーダ側では、２つのパッチ・ライブラリが生成される。１つのライブラリは、オリジナルのフレームから生成され、もう１つのライブラリは、再構築されたフレーム（すなわち符号化された後に復号されたフレーム）から生成される。後者のライブラリ（再構築フレームから生成されたライブラリ）は、デコーダ側で作成されたパッチ・ライブラリと全く同じであるが、これは、これらのパッチ・ライブラリを生成するのに全く同じフレーム（すなわち再構築フレーム）が使用されているからである。
【００４８】
エンコーダ側では、オリジナルのフレームから作成したパッチ・ライブラリを使用してブロックをプルーニングし、再構築フレームから作成したパッチ・ライブラリを使用してメタデータを符号化する。再構築フレームから作成したパッチ・ライブラリを使用する理由は、メタデータを符号化および復号するパッチ・ライブラリが、エンコーダ側とデコーダ側とで同一になることを保証するためである。
【００４９】
オリジナルのフレームを使用して作成したパッチ・ライブラリについて、クラスタリング・アルゴリズムを実行して、プルーニング中のパッチ探索プロセスを効率的に実行することができるようにパッチをグループ化する。プルーニングは、デコーダ側に送信されるビット数が少なくなるように、パッチ・ライブラリを用いてソース・ビデオを修正するプロセスである。プルーニングは、ビデオ・フレームを複数のブロックに分割し、それらのブロックの一部を低解像度ブロックまたはフラット・ブロックで置換することによって実現される。その後、プルーニングされたフレームを、ビデオ・エンコーダへの入力として用いる。本発明の原理を適用することができる例示的なビデオ・エンコーダは、上述した図２に示されている。
【００５０】
再度図１を参照すると、プルーニング・システム１００のデコーダ側処理の構成要素も、２つの部分、すなわちパッチ・ライブラリ作成部および回復部を含むものと考えることができる。デコーダ側でのパッチ・ライブラリ作成は、エンコーダ側とデコーダ側の両方で同じであるものとする、以前に復号されたフレームを用いてパッチ・ライブラリを作成するプロセスである。エンコーダ側の処理と異なり、デコーダ側でのパッチ・ライブラリ作成では、クラスタリングを用いない。回復構成要素は、エンコーダ側から送信された復号されたプルーニングされたフレームにおいて、プルーニングされたコンテンツを回復するプロセスである。この復号されたプルーニングされたフレームが、ビデオ・デコーダの出力である。本発明の原理を適用することができる例示的なビデオ・デコーダは、上述した図３に示されている。
【００５１】
パッチ・ライブラリ作成
図４を参照すると、事例ベースのデータ・プルーニング・システムのエンコーダ側処理を実行する例示的な第１の部分の全体が、参照番号４００で示されている。第１の部分４００は、クラスタリング装置４２０の入力部に信号通信された出力部を有する分割器４１０を含む。分割器の入力部は、第１の部分４００の、トレーニング・フレームを受信する入力部として利用することができる。クラスタリング装置４２０の出力部は、第１の部分４００の、クラスタおよびパッチ・ライブラリを出力する出力部として利用することができる。
【００５２】
図５を参照すると、クラスタリングおよびパッチ・ライブラリ作成を行う例示的な方法の全体が、参照番号５００で示されている。ステップ５０５で、トレーニング・ビデオ・フレームを入力する。ステップ５１０で、トレーニング・ビデオ・フレームを、（分割器４１０によって）重なり合う複数のブロックに分割する。ステップ５１５で、高周波数の細部を含まないブロックを（クラスタリング装置４２０によって）除去する。ステップ５２０で、これらのブロックを（クラスタリング装置４２０によって）クラスタリングする。ステップ５２５で、クラスタおよびパッチ・ライブラリを出力する。
【００５３】
パッチ・ライブラリは、プルーニングされた画像ブロックを回復するために使用することができる高解像度パッチのプールである。図６を参照すると、例示的なパッチ・ライブラリおよび対応するクラスタの全体が、参照番号６００で示されている。詳細には、パッチ・ライブラリは、参照番号６１０で示してあり、署名部分６１１および高解像度パッチ部分６１２を含む。エンコーダ側処理では、２つのパッチ・ライブラリが生成され、１つはプルーニング用のパッチ・ライブラリ、もう１つはメタデータ符号化用のパッチ・ライブラリである。プルーニング用のパッチ・ライブラリはオリジナルのフレームを用いて生成され、メタデータ符号化用のパッチ・ライブラリは再構築フレームを用いて生成される。プルーニング用のパッチ・ライブラリでは、プルーニング探索プロセスを効率的に実行することができるように、ライブラリ中のパッチを複数のクラスタにグループ化する。ライブラリ作成に用いられるビデオ・フレームを、重なり合う複数のブロックに分割して、トレーニング・データ・セットを形成する。最初に、高周波数の細部を含まない全てのブロックを除去することによって、トレーニング・データをクリーンアップする。修正Ｋ平均クラスタリング・アルゴリズム（２０１０年１月２２日に同じ所有者の米国仮特許出願（第６１／３３６５１６号）（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１０００１４）として出願された、Ｄｏｎｇ−Ｑｉｎｇ  Ｚｈａｎｇ、Ｓｉｔａｒａｍ  ＢｈａｇａｖａｔｈｙおよびＪｏａｎ  Ｌｌａｃｈによる「Ｄａｔａ  ｐｒｕｎｉｎｇ  ｆｏｒ  ｖｉｄｅｏ  ｃｏｍｐｒｅｓｓｉｏｎ  ｕｓｉｎｇ  ｅｘａｍｐｌｅ−ｂａｓｅｄ  ｓｕｐｅｒ−ｒｅｓｏｌｕｔｉｏｎ」に記載）を使用して、トレーニング・データ・セット中のパッチを複数のクラスタにグループ化する。各クラスタで、クラスタ中心は、当該クラスタ中のパッチの平均であり、プルーニング・プロセス中に着信クエリをマッチングするために使用される。修正Ｋ平均クラスタリング・アルゴリズムは、クラスタ内の任意のパッチとそのクラスタ中心との間の誤差が指定されたしきい値より小さくなることを保証する。修正Ｋ平均クラスタリング・アルゴリズムの代わりに、クラスタ中の誤差限界を保証する任意の同様のクラスタリング・アルゴリズムを用いることも可能である。
【００５４】
計算速度を上げるために、トレーニング・フレームの水平寸法および垂直寸法を、元のサイズの４分の１に縮小する。また、これらのダウンサイズされたフレーム中のパッチに対して、クラスタリング・プロセスを実行する。１つの例示的な実施形態では、高解像度パッチのサイズは１６×１６画素で、ダウンサイズされたパッチのサイズが４×４画素である。従って、ダウンサイズ率は４である。もちろん、本発明の原理の趣旨を維持しながら、その他のサイズを使用することができる。
【００５５】
メタデータ符号化用のパッチ・ライブラリでは、クラスタリング・プロセスおよびクリーンアップ・プロセスを実行しない。従って、このパッチ・ライブラリは、再構築フレームの全ての可能性のあるパッチを含む。ただし、元のフレームから作成したパッチ・ライブラリ中のあらゆるパッチについて、それらのパッチの座標を用いて再構築フレームから作成したパッチ・ライブラリ中に対応するパッチを見つけることができる。こうすれば、確実に、メタデータ符号化を正しく実行することができる。デコーダ側では、メタデータ復号およびプルーニングされたブロックの回復に同じ復号ビデオ・フレームを用いて、クラスタリングを用いない同じパッチ・ライブラリを作成する。
【００５６】
エンコーダ側とデコーダ側の両方で復号フレームを用いて作成されるパッチ・ライブラリについて、別のプロセスを実行して、パッチの署名を作成する。パッチの署名は、当該パッチおよび当該パッチの周囲の画素の平均色を含む特徴ベクトルである。パッチ署名をメタデータ符号化プロセスに使用して、さらに効率的にメタデータを符号化し、また、デコーダ側での回復プロセスで使用して、ベスト・マッチ・パッチを発見し、より高い信頼性でプルーニングされたコンテンツを回復する。図７を参照すると、例示的な署名ベクトルの全体が、参照番号７００で示されている。署名ベクトル７００は、平均色７０１および周囲画素７０２を含む。
【００５７】
メタデータ符号化プロセスについて、以下に述べる。プルーニングされたフレームでは、時に、回復またはメタデータ符号化のためにプルーニングされるブロックの隣接するブロックもプルーニングされることがある。この場合、パッチ・ライブラリ探索用の署名として使用される周囲画素のセットは、プルーニングされていないブロックの画素しか含んでいない。隣接する全てのブロックがプルーニングされた場合には、平均色７０１のみが署名として使用される。この場合、パッチ・マッチングに用いられる情報が少なすぎるので、パッチ・マッチングがうまくいかない可能性があり、これが、隣接するプルーニングされない画素７０２が重要である理由である。
【００５８】
プルーニング・プロセス
標準的なビデオ符号化アルゴリズムと同様に、入力ビデオ・フレームを複数のグループ・オブ・ピクチャ（ＧＯＰ）に分割する。プルーニング・プロセスは、ＧＯＰの第１のフレームに対して行われる。プルーニングの結果は、その後、ＧＯＰの残りのフレームに伝えられる。
【００５９】
ＧＯＰの第１のフレームに対するプルーニング・プロセス
図８を参照すると、事例ベースのデータ・プルーニング・システムのエンコーダ側処理を実行する例示的な第２の部分の全体が、参照番号８００で示されている。第２の部分８００は、パッチ・ライブラリ探索器８１０の入力部と信号通信する出力部を有する分割器８０５を含む。パッチ・ライブラリ探索器８１０の出力部は、ビデオ・エンコーダ８１５の入力部、メタデータ生成器８２０の第１の入力部、およびメタデータ・エンコーダ８２５の第１の入力部に信号通信で接続されている。メタデータ生成器８２０の出力部は、メタデータ・エンコーダ８２５の第２の入力部に信号通信で接続されている。ビデオ・エンコーダ８１５の第１の出力部は、メタデータ生成器８２０の第２の入力部に信号通信で接続されている。分割器８０５の入力部は、第２の部分８００の、入力フレームを受信する入力部として利用することができる。ビデオ・エンコーダ８１５の出力部は、第２の部分８００の、符号化ビデオ・フレームを出力する出力部として利用することができる。メタデータ・エンコーダ８２５の出力部は、第２の部分８００の、符号化メタデータを出力する出力部として利用することができる。
【００６０】
図９を参照すると、ビデオ・フレームをプルーニングする例示的な方法の全体が、参照番号９００で示されている。ステップ９０５で、ビデオ・フレームを入力する。ステップ９１０で、ビデオ・フレームを、重なり合わない複数のブロックに分割する。ステップ９１５で、各ブロックについてループを実行する。ステップ９２０で、パッチ・ライブラリの探索を実行する。ステップ９２５で、パッチが見つかったか否かを判定する。パッチが見つかった場合には、この方法は、ステップ９３０に進む。そうでない場合には、この方法は、ステップ９１５に戻る。ステップ９３０で、ブロックをプルーニングする。ステップ９３５で、全てのブロックが終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ９４０に進む。そうでない場合には、この方法は、ステップ９１５に戻る。ステップ９４０で、プルーニングされたフレームおよび対応するメタデータを出力する。
【００６１】
このように、最初にステップ９１０で、入力フレームを、重なり合わない複数のブロックに分割する。ブロックのサイズは、標準的な圧縮アルゴリズムで使用されるマクロブロックのサイズと同じである。すなわち、本明細書に開示する例示的な実施態様では、１６×１６画素のサイズを利用する。次いで、ステップ９２０で、探索プロセスを行い、パッチ・ライブラリ中のベスト・マッチ・パッチを見つける。この探索プロセスを、図１０に示す。図１０を参照すると、プルーニング中に実行されるパッチ探索プロセスの全体が、参照番号１０００で示されている。パッチ探索プロセス１０００では、パッチ・ライブラリ１０１０を用い、パッチ・ライブラリ１０１０は、署名部分１０１１および高解像度パッチ部分１０１２を含む。最初に、ユークリッド距離を計算し、上位Ｋ個のマッチングするクラスタを見つけることにより、ブロックをクラスタの中心とマッチングする。現在のところ、Ｋは経験的に決定される。原則的には、Ｋは、クラスタの誤差限界によって決定される。もちろん、本発明の原理の教示に従って、Ｋを計算するその他の手法を使用することもできる。候補クラスタを識別した後で、これらのクラスタ内でベスト・マッチ・パッチが見つかるまで、これらのクラスタ内で探索プロセスを実行する。ベスト・マッチ・パッチとクエリ・ブロックとの間の差が所定のしきい値未満である場合には、そのブロックをプルーニングすることになる。そうでない場合には、そのブロックはそのままに保たれる。プルーニングされたブロックのＩＤおよび各ブロックのベスト・マッチ・パッチの指標はメタデータとして保存され、このメタデータが、メタデータ符号化構成要素で符号化され、デコーダ側に送信されることになる。
【００６２】
プルーニングを行うブロックを識別した後で、ブロックをプルーニングするプロセスを行う。プルーニングする必要があるブロックについて、例えば、高解像度ブロックを低解像度ブロックで置換するなど、様々なプルーニング・ストラテジが考えられる。ただし、この手法で有意な圧縮効率の向上を実現することは困難である可能性もあることが分かっている。従って、本明細書に開示する好ましい実施形態では、単に、高解像度ブロックを、全ての画素が同じ色値（すなわちオリジナルのブロックの画素の色値の平均）を有するフラット・ブロックで置換する。ブロック置換プロセスでは、フレームのいくつかの部分が高解像度を有し、いくつかの他の部分が低解像度を有するビデオ・フレームを作成する。従って、このようなフレームは、「混合解像度」フレームと呼ばれる（混合解像度プルーニング方式に関する詳細については、２０１１年３月ＸＸ日出願の「ＭＥＴＨＯＤＳ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＥＮＣＯＤＩＮＧ  ＶＩＤＥＯ  ＳＩＧＮＡＬＳ  ＦＯＲ  ＢＬＯＣＫ−ＢＡＳＥＤ  ＭＩＸＥＤ−ＲＥＳＯＬＵＴＩＯＮ  ＤＡＴＡ  ＰＲＵＮＩＮＧ  ＦＯＲ  ＩＭＰＲＯＶＩＮＧ  ＶＩＤＥＯ  ＣＯＭＰＲＥＳＳＩＯＮ  ＥＦＦＩＣＩＥＮＣＹ」と題する同時係属の所有者が同じ国際（ＰＣＴ）特許出願第ＸＸＸＸ号（Ｔｅｃｈｎｉｃｏｌｏｒ  整理番号ＰＵ１００１９４を参照されたい））。図１１を参照すると、例示的な混合解像度フレームの全体が、参照番号１１００で示されている。上述のフラット・ブロック置換方式は、望ましい圧縮効率を得るのに極めて効果的であることが分かっている。フラット・ブロック置換方式の代わりに、プルーニングするブロックをその低解像度バージョンで置換する、低解像度ブロック置換方式を用いることも可能である。
【００６３】
メタデータの符号化および復号
メタデータ符号化は、２つの構成要素（図１２参照）を含み、１つはプルーニングされたブロックＩＤの符号化（図１３参照）で、もう１つはパッチ指標の符号化（図１４）である。これらは、プルーニング・プロセス中に各ブロック毎にパッチ・ライブラリを探索した結果である。
【００６４】
図１２を参照すると、メタデータを符号化する例示的な方法の全体が、参照番号１２００で示されている。ステップ１２０５で、復号されたプルーニングされたビデオ・フレーム、プルーニングされたブロックＩＤおよび各ブロックのパッチ指標を入力する。ステップ１２１０で、プルーニングされたブロックＩＤを符号化する。ステップ１２１５で、パッチ指標を符号化する。ステップ１２２０で、符号化メタデータを出力する。
【００６５】
図１３を参照すると、プルーニングされたブロックＩＤを符号化する例示的な方法の全体が、参照番号１３００で示されている。ステップ１３０５で、プルーニングされたフレームおよびプルーニングされたブロックＩＤを入力する。ステップ１３１０で、低解像度ブロック識別を実行する。ステップ１３２０で、ミスがあるか否かを判定する。ミスがないと判定された場合には、この方法は、ステップ１３２５に進む。そうでない場合には、この方法は、ステップ１３１５に進む。ステップ１３２５で、誤検出の数がプルーニングされたブロックの数より多いか否かを判定する。誤検出の数がプルーニングされたブロックの数より多い場合には、この方法は、ステップ１３３０に進む。そうでない場合には、制御はステップ１３３５に進む。ステップ１３３０で、プルーニングされたブロックのシーケンスを用い、フラグをゼロにセットする。ステップ１３４０で、差分計算（ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ）を実行する。ステップ１３４５で、可逆符号化を実行する。ステップ１３５０で、符号化メタデータを出力する。ステップ１３１５で、しきい値を調節する。ステップ１３３５で、誤検出シーケンスを用い、フラグを１にセットする。
【００６６】
図１４を参照すると、パッチ指標を符号化する例示的な方法の全体が、参照番号１４００で示されている。ステップ１４０５で、復号されたプルーニングされたビデオ・フレームおよび各ブロックのパッチ指標を入力する。ステップ１４１０で、各々のプルーニングされたブロック毎にループを実行する。ステップ１４１５で、署名を取得する。ステップ１４２０で、パッチ・ライブラリ中の各パッチまでの距離を計算する。ステップ１４２５で、これらのパッチを分類して、ランク・リストを取得する。ステップ１４３０で、ランク番号を取得する。ステップ１４３５で、ランク番号をエントロピ符号化する。ステップ１４４０で、全てのブロック（の処理）が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ１４４５に進む。そうでない場合には、この方法は、ステップ１４１０に戻る。ステップ１４４５で、符号化されたパッチ指標を出力する。
【００６７】
プルーニング・プロセス中に、各ブロック毎に、システムはベスト・マッチ・パッチを探してパッチ・ライブラリを探索し、見つかったパッチのパッチ・ライブラリ中でのパッチ指標を、その歪みがしきい値未満であれば出力する。各パッチは、その署名（すなわちそのパッチの色に復号したフレーム中での周囲の画素を加えたもの）と関連付けられる。デコーダ側処理における回復プロセス中に、プルーニングされたブロックの色およびその周囲の画素を署名として用いて、ライブラリ中の正しい高解像度パッチを見つける。
【００６８】
ただし、ノイズにより、署名を用いた探索プロセスは信頼性が低く、信頼性を確保するために回復プロセスを補助するメタデータが必要である。従って、プルーニング・プロセスの後で、システムは回復を補助するためのメタデータを生成することになる。各々のプルーニングされたブロック毎に、上述の探索プロセスは、ライブラリ中の対応するパッチを既に識別している。メタデータ符号化構成要素では、クエリ・ベクトル（プルーニングされたブロックの平均色および周囲画素）を使用してパッチ・ライブラリ（復号フレームを用いて作成されたライブラリ）中のパッチの署名のマッチングを行うことにより、回復プロセスをシミュレートする。このプロセスを、図１４に示す。再度図１４を参照すると、各ブロック毎に、ブロックに対応するクエリ・ベクトルとライブラリ中のパッチの署名との間の距離（例えばユークリッド距離、ただしもちろんその他の距離メトリクスを用いてもよい）を計算する。この距離に従ってパッチを分類し、ランク・リストを得る。理想的なケースでは、ベスト・マッチの高解像度パッチがランク・リストの最上位に来なければならない。しかし、丸め演算および圧縮によるノイズによって、ベスト・マッチ・パッチがランク・リストの最初のパッチにならないことも多い。正しいパッチがランク・リストのｎ番目のパッチであると仮定する。この数字ｎは、このブロックのメタデータとして保存される。なお、ほとんどの場合、ベスト・マッチ・パッチはランク・リストの最上位に近いので、ｎは１または非常に小さな数字であることに留意されたい。従って、この乱数のエントロピは、最大エントロピを有する一様分布であるはずのライブラリ中のベスト・マッチ・パッチの指標よりもかなり小さい。従って、この順位番号は、エントロピ符号化で効率的に符号化することができる。全てのプルーニングされたブロックのランク番号で、デコーダ側に送信されるメタデータの一部としてのランク番号シーケンスが形成される。実際に行われた実験により、ランク番号の分布が幾何学的分布に近いことが分かっている。従って、現在は、ランク番号シーケンスをさらに符号化するために、ゴロム符号が用いられている。ゴロム符号は、幾何学的分布を有する乱数に最適である。もちろん、本発明の原理の教示に従って、本発明の原理の趣旨を維持しながら、その他のタイプの符号を使用することもできる。
【００６９】
復号（図１５参照）のために、デコーダ側は、復号フレームを用いて作成された、エンコーダ側と全く同じパッチ・ライブラリを有していなければならない。プルーニングされたブロックの署名を使用して、パッチ・ライブラリ中の署名とのマッチングを行い、ランク・リスト（分類済みパッチ・ライブラリ）を得る。ランク番号を使用して、分類済みパッチ・ライブラリから正しいパッチを取り出す。パッチ・ライブラリが以前のフレームから作成されている場合には、エンコーダ側およびデコーダ側が確実に全く同じパッチ・ライブラリを有するようにするために、エンコーダ側でのメタデータ符号化プロセスで、ビデオ・デコーダから得た復号フレームも使用しなければならない。これは、デコーダ側では復号フレームしか利用できないからである。
【００７０】
図１５を参照すると、パッチ指標を復号する例示的な方法の全体が、参照番号１５００で示されている。ステップ１５０５で、復号されたプルーニングされたビデオ・フレーム、符号化されたパッチ指標およびプルーニングされたブロックＩＤを入力する。ステップ１５１０で、各々のプルーニングされたブロック毎にループを実行する。ステップ１５１５で、署名を取得する。ステップ１５２０で、パッチ・ライブラリ中の各パッチまでの距離を計算する。ステップ１５２５で、これらのパッチを分類して、ランク・リストを取得する。ステップ１５３０で、符号化ランク番号をエントロピ復号する。ステップ１５３５で、ランク番号を用いて、パッチ・ライブラリからパッチ指標を取り出す。ステップ１５４０で、全てのブロック（の処理）が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ１５４５に進む。そうでない場合には、この方法は、ステップ１５１０に戻る。ステップ１５４５で、復号されたパッチ指標を出力する。
【００７１】
ランク番号メタデータの他に、プルーニングされたブロックの位置もデコーダ側に送信する必要がある。これは、ブロックＩＤの符号化（図１３参照）によって行われる。１つの簡単な方法としては、単にブロックＩＤシーケンスをデコーダ側に送信するだけでもよい。ブロックのＩＤは、フレーム上での当該ブロックの座標を示す。図１６を参照すると、例示的なブロックＩＤの全体が、参照番号１６００で示されている。プルーニングされたブロックのＩＤシーケンスをさらに効率的に符号化することが可能である場合もある。プルーニングされたブロックはフラットであり、高周波数成分を含まないので、ブロック内の色変動を計算することによってプルーニングされたブロックを検出することができる。色変動がしきい値より小さければ、そのブロックはプルーニングされたブロックであると識別される。ただし、この識別プロセスは信頼性が低い場合があるので、識別プロセスを容易にするために、依然としてメタデータが必要である。最初に、高いしきい値から始めることにより分散しきい値を求める。このアルゴリズムでは、その後、この識別手順で全てのプルーニングされたブロックを識別することができるように分散しきい値をゆっくりと小さくしていくが、誤検出ブロックが識別結果に存在する可能性もある。その後、誤検出の数がプルーニングされたブロックの数より大きい場合には、プルーニングされたブロックのＩＤを保存し、デコーダに送信する。そうでない場合には、誤検出のＩＤを、デコーダ側に送信する。フラット・ブロックを識別するための分散しきい値も、同じ識別手順を実行するためにデコーダ側に送信する。ＩＤシーケンスは、番号が大きくなるように分類することができる。
【００７２】
冗長性をさらに低下させるために、差分符号化方式を利用して、ＩＤ番号とその前のＩＤ番号との間の差を最初に計算し、その差分シーケンスを符号化する。例えば、ＩＤシーケンスが３、４、５、８、１３、１４であると仮定すると、その差分シーケンスは、３、１、１、３、５、１となる。この差分プロセスにより、各数字が１に近づくので、よりエントロピの小さな数字分布が得られる。次いで、この差分シーケンスを、エントロピ符号化（例えば現在の実施態様ではハフマン符号化）によってさらに符号化することができる。従って、最終的なメタデータのフォーマットは以下に示すようになる。
【表１】
0005905889.tif 000002
ここで、フラグは、当該ブロックＩＤシーケンスが誤検出ＩＤシーケンスであるか否かを示すシグナリング（ｓｉｇｎａｌｉｎｇ）フラグである。しきい値は、フラット・ブロック識別のための分散しきい値である。符号化ブロックＩＤシーケンスは、プルーニングされたブロックＩＤまたは誤検出ブロックＩＤの符号化ビットストリームである。符号化ランク番号シーケンスは、ブロック回復に使用されるランク番号の符号化ビットストリームである。
【００７３】
残りのフレームに対するプルーニング・プロセス
ＧＯＰ中の残りのフレームについては、それらのフレーム内のブロックの一部は、やはりフラット・ブロックで置換される。第１のフレーム中のプルーニングされたブロックの位置は、動きトラッキングによって残りのフレームに伝えることができる。プルーニングされたブロックの位置を伝えるための様々なストラテジがテストされている。１つの手法は、ブロック・マッチングによって複数のフレームをまたいでプルーニングされたブロックをトラッキングし、後続のフレーム内の対応するブロックをプルーニングする（すなわちトラッキングしたブロックをフラット・ブロックで置換する）ものである。ただし、この手法は、一般に、トラッキングしたブロックの境界が符号化するマクロブロックと位置合わせされないので、良好な圧縮効率の向上は得られない。その結果として、トラッキングしたブロックの境界は、マクロブロック中で高周波数信号を生じる。従って、現在では、後続フレームの全てのブロック位置を第１のフレームと同じ位置にセットするという、より簡単な代替手法が用いられている。すなわち、後続フレーム中の全てのプルーニングされたブロックが、第１のフレーム中のプルーニングされたブロックと同じ位置にある。その結果として、後続フレームの全てのプルーニングされたブロックが、マクロブロックの位置と位置合わせされる。
【００７４】
ただし、この手法は、プルーニングされたブロック内に動きがある場合には、うまくいかないこともある。従って、この問題を解決する１つの解決策は、ブロックの動き強度を計算するものである（図１７参照）。図１７を参照すると、後続フレームのプルーニングを行う例示的な方法の全体が、参照番号１７００で示されている。ステップ１７０５で、ビデオ・フレームおよびプルーニングされたブロックＩＤを入力する。ステップ１７１０で、同じ位置にあるブロックのプルーニングを行う。ステップ１７１５で、各ブロック毎にループを実行する。ステップ１７２０で、以前のフレームまでの動きベクトルを計算する。ステップ１７２５で、これらの動きベクトルをメタデータとして保存する。ステップ１７３０で、全てのブロック（の処理）が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ１７３５に進む。そうでない場合には、この方法は、ステップ１７１５に戻る。
【００７５】
動き強度がしきい値より大きい場合には、そのブロックのプルーニングを行わない。本明細書に開示する例示的な実施態様である別のさらに洗練された解決策では、以前のフレーム中の対応するブロックを探索することによって、オリジナルのビデオ内のプルーニングされたブロックの動きベクトルを計算する（図１８参照）。図１８を参照すると、プルーニングされたブロックの例示的な動きベクトルの全体が、参照番号１８００で示されている。動きベクトル１８００は、ｉ番目のフレーム内のプルーニングされたブロックおよび（ｉ−１）番目のフレーム内の同じ位置にあるブロックに関係する。プルーニングされたブロックの動きベクトルは、回復のためにデコーダ側に送信される。以前のフレームは既に完全に回復されているので、現在のフレーム中のプルーニングされたブロックも、これらの動きベクトルを使用して回復することができる。アーチファクトを避けるために、現在のフレーム内のブロックと動き推定によって計算した以前のフレーム内の対応するブロックとの間の差が大きすぎる場合には、現在のフレーム内のブロックのプルーニングを行わない。さらに、現在は、サブピクセル（ｓｕｂ−ｐｉｘｅｌ）動き推定を利用して、動きベクトルに基づく回復の精度を高めている。実験によって、サブピクセルに基づく動きベクトル推定を用いて得られた視覚的品質は、整数ピクセル（ｉｎｔｅｇｅｒ  ｐｉｘｅｌ）に基づく動きベクトル推定を用いて得られる視覚的品質よりはるかに良好であることが分かっている。
【００７６】
回復プロセス
回復プロセスは、デコーダ側で行われる。回復プロセスの前に、パッチ・ライブラリを作成しなければならない。映画などの長いビデオの場合には、これは、デコーダ側に既に送信されている以前のフレームを用いることによって行うことができる。エンコーダ側は、パッチ・ライブラリ作成にどのフレームを使用すべきかを示すメタデータ（フレームＩＤ）を送信することができる。デコーダ側でのパッチ・ライブラリは、エンコーダ側でのパッチ・ライブラリと全く同じでなければならない。
【００７７】
ＧＯＰ内の第１のフレームに対しては、回復プロセスは、ブロックＩＤシーケンスの復号（図２０参照）およびランク順位シーケンスの復号（図１９参照）を含むメタデータを復号すること（図１９参照）から開始する。図１９を参照すると、メタデータを復号する例示的な方法の全体が、参照番号１９００で示されている。ステップ１９０５で、符号化メタデータを入力する。ステップ１９１０で、プルーニングされたブロックＩＤを復号する。ステップ１９１５で、パッチ指標を復号する。ステップ１９２０で、復号メタデータを出力する。
【００７８】
図２０を参照すると、プルーニングされたブロックＩＤを復号する例示的な方法の全体が、参照番号２０００で示されている。ステップ２００５で、符号化メタデータを入力する。ステップ２０１０で、可逆復号を実行する。ステップ２０１５で、逆差分計算（ｒｅｖｅｒｓｅ  ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ）を実行する。ステップ２０２０で、フラグがゼロであるか否かを判定する。フラグがゼロである場合には、この方法は、ステップ２０２５に進む。そうでない場合には、この方法は、ステップ２０３０に進む。ステップ２０２５で、ブロックＩＤを出力する。ステップ２０３０で、低解像度ブロック識別を実行する。ステップ２０３５で、誤検出を除去する。ステップ２０４０で、ブロックＩＤを出力する。
【００７９】
ブロックＩＤシーケンスが利用可能になった後で、各々のプルーニングされたブロック毎に、このブロックの平均色および周囲画素を署名ベクトルとして、パッチ・ライブラリ中の署名とのマッチングを行う。ただし、回復するブロックの隣接するブロックもプルーニングされている場合には、探索のためのみの署名として用いられる周囲画素のセットは、プルーニングされていないブロックの画素を含む。隣接する全てのブロックがプルーニングされている場合には、平均色のみを署名として使用する。このマッチング・プロセスは、クエリ・ブロックの署名とライブラリ中の各パッチの署名との間のユークリッド距離を計算することによって実現される。全ての距離を計算した後で、その距離に従ってリストを分類して、ランク・リストを得る。次いで、プルーニングされたブロックに対応するランク番号を使用して、ランク・リストから正しい高解像度ブロックを取り出す。
【００８０】
図２１を参照すると、事例ベースのデータ・プルーニングのデコーダ側処理を実行する例示的な装置の全体が、参照番号２１００で示されている。装置２１００は、探索パッチ・ライブラリ／ブロック置換装置２１１０の第１の入力部に信号通信で接続された出力部を有する分割器２１０５を含む。メタデータ・デコーダ２１１５の出力部は、探索パッチ・ライブラリ／ブロック置換装置２１１０の第２の入力部に信号通信で接続されている。分割器２１０５の入力部は、装置２１００の、プルーニングされたビデオを受信する入力部として利用することができる。メタデータ・デコーダ２１１５の入力部は、装置２１００の、符号化メタデータを受信する入力部として利用することができる。探索パッチ・ライブラリ／ブロック置換装置２１１０の出力部は、この装置の、回復ビデオを出力する出力部として利用することができる。
【００８１】
図２２を参照すると、プルーニングされたフレームを回復する例示的な方法の全体が、参照番号２２００で示されている。ステップ２２０５で、プルーニングされたフレームおよび対応するメタデータを入力する。ステップ２２１０で、プルーニングされたフレームを、重なり合わない複数のブロックに分割する。ステップ２２１５で、各ブロック毎にループを実行する。ステップ２２２０で、現在のブロックがプルーニングされたブロックであるか否かを判定する。現在のブロックがプルーニングされたブロックである場合には、この方法は、ステップ２２２５に進む。そうでない場合には、この方法は、ステップ２２１５に戻る。ステップ２２２５で、ライブラリ中でパッチを見つける。ステップ２２３０で、現在のブロックを、この見つかったパッチで置換する。ステップ２２３５で、全てのブロック（の処理）が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ２２４０に進む。そうでない場合には、この方法は、ステップ２２１５に戻る。ステップ２２４０で、回復フレームを出力する。
【００８２】
エグザンプル・パッチを用いたブロック回復の代わりに、従来のインペインティングおよびテクスチャ合成に基づく方法を行うこともできることを理解されたい。
【００８３】
ＧＯＰ中の残りのフレームに対しては、各々のプルーニングされたブロック毎に、動きベクトルが利用できない場合には、ブロックのコンテンツを以前のフレーム中の同じ位置にあるブロックからコピーすることができる。動きベクトルが利用できる場合には、動きベクトルを使用して、以前のフレーム中の対応するブロックを見つけ、この対応するブロックをコピーして、プルーニングされたブロックを埋めることができる（図２３参照）。図２３を参照すると、後続フレームを回復する例示的な方法の全体が、参照番号２３００で示されている。ステップ２３０５で、ビデオ・フレームおよびプルーニングされたブロックＩＤを入力する。ステップ２３１０で、各ブロック毎にループを実行する。ステップ２３１５で、動きベクトルを使用して、以前のフレーム中のパッチを見つける。ステップ２３２０で、この見つかったパッチを用いて、プルーニングされたブロックを置換する。ステップ２３２５で、全てのブロック（の処理）が終了したか否かを判定する。全てのブロックが終了している場合には、この方法は、ステップ２３３０に進む。そうでない場合には、この方法は、ステップ２３１０に戻る。
【００８４】
この回復プロセスはブロックに基づくので、ブロック・アーチファクトが見えることもある。ＡＶＣエンコーダで用いられるインループ・デブロッキング・フィルタなどのデブロッキング・フィルタを適用して、ブロック・アーチファクトを低減することができる。
【００８５】
本発明の原理の上記その他の特徴および利点は、当業者であれば、本明細書の教示に基づいて容易に確認することができる。これらの本発明の原理の教示は、ハードウェア、ソフトウェア、ファームウェア、特殊目的プロセッサ、またはそれらの組合せの様々な形態で実施することができることを理解されたい。
【００８６】
本発明の原理の教示は、ハードウェアとソフトウェアの組合せとして実施されることが最も好ましい。さらに、ソフトウェアは、プログラム記憶装置に有形に具体化されたアプリケーション・プログラムとして実施することができる。アプリケーション・プログラムは、任意の適当なアーキテクチャを含む機械にアップロードし、この機械によって実行することができる。この機械は、１つまたは複数の中央処理装置（「ＣＰＵ」）、ランダム・アクセス・メモリ（「ＲＡＭ」）および入出力（Ｉ／Ｏ）インタフェースなどのハードウェアを有するコンピュータ・プラットフォームで実施されることが好ましい。コンピュータ・プラットフォームは、オペレーティング・システムおよびマイクロ命令コードも含むことができる。本明細書に記載する様々なプロセスおよび機能は、ＣＰＵによって実行することができる、マイクロ命令コードの一部またはアプリケーション・プログラムの一部あるいはそれらの任意の組合せの何れかにすることができる。さらに、追加のデータ記憶装置や印刷装置などの、その他の様々な周辺装置をコンピュータ・プラットフォームに接続することもできる。
【００８７】
さらに、添付の図面に示すシステム構成要素および方法の一部はソフトウェアで実施することが好ましいので、システム構成要素間またはプロセス機能ブロック間の実際の接続は、本発明の原理をプログラミングする方法によって異なっていてもよいことも理解されたい。本明細書の教示があれば、当業者なら、本発明の原理の上記の実施態様または構成およびそれらと同様の実施態様または構成を思いつくことができるであろう。
【００８８】
本明細書では、添付の図面を参照して例示的な実施形態について述べたが、本発明の原理は、これらの具体的な実施形態に限定されるわけではなく、当業者なら、本発明の原理の範囲または趣旨を逸脱することなく様々な変更および修正をそれらの実施形態に加えることができることを理解されたい。そうした変更および修正は全て、添付の特許請求の範囲に記載する本発明の原理の範囲に含まれるものとする。
［付記１］
ビデオ・シーケンス中のピクチャのオリジナルのバージョンから第１のパッチ・ライブラリを作成し、前記ビデオ・シーケンス中の前記ピクチャの再構築バージョンから第２のパッチ・ライブラリを作成するパッチ・ライブラリ作成器（１４５）であって、前記第１のパッチ・ライブラリおよび前記第２のパッチ・ライブラリは、それぞれ、前記ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含んでいる前記パッチ・ライブラリ作成器と、
前記第１のパッチ・ライブラリから前記ピクチャの前記プルーニングされたバージョンを生成するプルナ（１０５）と、
前記ピクチャの前記プルーニングされたバージョンを回復する際に使用するために、前記第２のパッチ・ライブラリからメタデータを生成するメタデータ生成器（１３５）と、
前記ピクチャの前記プルーニングされたバージョンおよび前記メタデータを符号化するエンコーダ（１１０，１３５）と、
を含む装置。
［付記２］
前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数のブロックに分割し、前記複数のブロックの少なくとも１つを置換パッチでそれぞれ置換することによって生成され、前記置換パッチ内の全ての画素が、同じ色値または低解像度の一方を有する、付記１に記載の装置。
［付記３］
前記同じ色値は、前記複数のブロックの前記少なくとも１つの中の前記画素の色値の平均に等しい、付記２に記載の装置。
［付記４］
前記第１のパッチ・ライブラリは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合うブロックに分割してトレーニング・データ・セットを形成し、前記トレーニング・セットから、前記複数の重なり合うブロックのうち、既定のしきい値を超える高周波数成分を有するブロックを除去し、前記複数の重なり合うブロックの残りのブロックを複数のクラスタにクラスタリングすることによって作成され、前記複数の重なり合うブロックの前記残りの各ブロックが、前記複数の高解像度置換パッチのそれぞれ１つを形成する、付記１に記載の装置。
［付記５］
前記複数のクラスタのそれぞれ１つの各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数の重なり合うブロックの前記残りのブロックの平均に対応する、付記４に記載の装置。
［付記６］
前記複数の重なり合うブロックの前記残りのブロックを、前記クラスタリングの前にダウンサイズして、複数のダウンサイズされた重なり合うブロックを取得し、前記クラスタリングを、前記複数のダウンサイズされた重なり合うブロックに対して実行し、前記複数のクラスタの前記それぞれ１つの前記各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数のダウンサイズされた重なり合うブロックの前記平均に対応する、付記５に記載の装置。
［付記７］
前記第２のパッチ・ライブラリに含まれる前記複数の高解像度パッチの各々について、前記複数の高解像度パッチのそれぞれ１つの平均色を含む特徴ベクトルを生成することによって、署名をそれぞれ作成する、付記１に記載の装置。
［付記８］
前記複数の高解像度パッチの前記それぞれ１つの前記特徴ベクトルに含まれる前記平均色は、さらに、前記複数の高解像度パッチの前記それぞれ１つに対する周囲画素の平均色である、付記７に記載の装置。
［付記９］
前記第１のパッチ・ライブラリは複数のパッチ・クラスタを含み、前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合わないブロックに分割し、前記複数の重なり合わないブロックの各々から前記複数のパッチ・クラスタの各々の各中心までのそれぞれの距離メトリクスに基づいて、前記複数の重なり合わないブロックのそれぞれについて、前記複数のパッチ・クラスタから候補パッチ・クラスタを探索し、１つまたは複数の基準に基づいて前記候補パッチ・クラスタからベスト・マッチング・パッチを識別し、前記複数の重なり合わないブロックのうちの対応する１つと前記ベスト・マッチング・パッチとの間の差がしきい値差未満であるときに、前記複数の重なり合わないブロックのうちの前記対応する１つをプルーニングして、プルーニングされたブロックを取得することによって生成される、付記１に記載の装置。
［付記１０］
前記複数の重なり合わないブロックのうちの前記対応する１つと前記ベスト・マッチング・パッチとの間の前記差が前記しきい値差未満であるときに、前記メタデータは、前記ベスト・マッチング・パッチに関するパッチ指標を含み、前記メタデータは、前記プルーニングされたブロックのブロック識別子をさらに含む、付記９に記載の装置。
［付記１１］
ビデオ・シーケンス中のピクチャのオリジナルのバージョンから第１のパッチ・ライブラリを作成し、前記ビデオ・シーケンス中の前記ピクチャの再構築バージョンから第２のパッチ・ライブラリを作成するステップ（５２５）であって、前記第１のパッチ・ライブラリおよび前記第２のパッチ・ライブラリは、それぞれ、前記ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換する複数の高解像度置換パッチを含んでいる前記ステップと、
前記第１のパッチ・ライブラリから前記ピクチャの前記プルーニングされたバージョンを生成するステップ（８１０）と、
前記ピクチャの前記プルーニングされたバージョンを回復する際に使用するために、前記第２のパッチ・ライブラリからメタデータを生成するステップ（８２０）と、
前記ピクチャの前記プルーニングされたバージョンおよび前記メタデータを符号化するステップ（８１５，８２５）と、
を含む方法。
［付記１２］
前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数のブロックに分割し（４１０）、前記複数のブロックの少なくとも１つを置換パッチでそれぞれ置換することによって生成され、前記置換パッチ内の全ての画素が、同じ色値または低解像度の一方を有する、付記１１に記載の方法。
［付記１３］
前記同じ色値は、前記複数のブロックの前記少なくとも１つの中の前記画素の色値の平均に等しい、付記１２に記載の方法。
［付記１４］
前記第１のパッチ・ライブラリは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合うブロックに分割してトレーニング・データ・セットを形成し、前記トレーニング・セットから、前記複数の重なり合うブロックのうち、既定のしきい値を超える高周波数成分を有するブロックを除去し、前記複数の重なり合うブロックの残りのブロックを複数のクラスタにクラスタリングすることによって作成され、前記複数の重なり合うブロックの前記残りの各ブロックが、前記複数の高解像度置換パッチのそれぞれ１つを形成する、付記１１に記載の方法。
［付記１５］
前記複数のクラスタのそれぞれ１つの各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数の重なり合うブロックの前記残りのブロックの平均に対応する、付記１３に記載の方法。
［付記１６］
前記複数の重なり合うブロックの前記残りのブロックを、前記クラスタリングの前にダウンサイズして、複数のダウンサイズされた重なり合うブロックを取得し、前記クラスタリングを、前記複数のダウンサイズされた重なり合うブロックに対して実行し、前記複数のクラスタの前記それぞれ１つの前記各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数のダウンサイズされた重なり合うブロックの前記平均に対応する、付記１４に記載の方法。
［付記１７］
前記第２のパッチ・ライブラリに含まれる前記複数の高解像度パッチの各々について、前記複数の高解像度パッチのそれぞれ１つの平均色を含む特徴ベクトルを生成することによって、署名をそれぞれ作成する、付記１１に記載の方法。
［付記１８］
前記複数の高解像度パッチの前記それぞれ１つの前記特徴ベクトルに含まれる前記平均色は、さらに、前記複数の高解像度パッチの前記それぞれ１つに対する周囲画素の平均色である、付記１７に記載の方法。
［付記１９］
前記第１のパッチ・ライブラリは複数のパッチ・クラスタを含み、前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合わないブロックに分割し、前記複数の重なり合わないブロックの各々から前記複数のパッチ・クラスタの各々の各中心までのそれぞれの距離メトリクスに基づいて、前記複数の重なり合わないブロックのそれぞれについて、前記複数のパッチ・クラスタから候補パッチ・クラスタを探索し、１つまたは複数の基準に基づいて前記候補パッチ・クラスタからベスト・マッチング・パッチを識別し、前記複数の重なり合わないブロックのうちの対応する１つと前記ベスト・マッチング・パッチとの間の差がしきい値差未満であるときに、前記複数の重なり合わないブロックのうちの前記対応する１つをプルーニングして、プルーニングされたブロックを取得することによって生成される、付記１１に記載の方法。
［付記２０］
前記複数の重なり合わないブロックのうちの前記対応する１つと前記ベスト・マッチング・パッチとの間の前記差が前記しきい値差未満であるときに、前記メタデータは、前記ベスト・マッチング・パッチに関するパッチ指標を含み、前記メタデータは、前記プルーニングされたブロックのブロック識別子をさらに含む、付記１９に記載の装置。
［付記２１］
ビデオ・シーケンス中のピクチャのオリジナルのバージョンから第１のパッチ・ライブラリを作成し、前記ビデオ・シーケンス中の前記ピクチャの再構築バージョンから第２のパッチ・ライブラリを作成する手段（１４５）であって、前記第１のパッチ・ライブラリおよび前記第２のパッチ・ライブラリは、それぞれ、前記ピクチャのプルーニングされたバージョンの回復中に１つまたは複数のプルーニングされたブロックを置換するための複数の高解像度置換パッチを含んでいる前記手段と、
前記第１のパッチ・ライブラリから前記ピクチャの前記プルーニングされたバージョンを生成する手段（１０５）と、
前記ピクチャの前記プルーニングされたバージョンを回復する際に使用するために、前記第２のパッチ・ライブラリからメタデータを生成する手段（１３５）と、
前記ピクチャの前記プルーニングされたバージョンおよび前記メタデータを符号化する手段（１１０，１３５）と、
を含む装置。
［付記２２］
前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数のブロックに分割し、前記複数のブロックの少なくとも１つを置換パッチでそれぞれ置換することによって生成され、前記置換パッチ内の全ての画素が、同じ色値または低解像度の一方を有する、付記２１に記載の装置。
［付記２３］
前記同じ色値は、前記複数のブロックの前記少なくとも１つの中の前記画素の色値の平均に等しい、付記２２に記載の装置。
［付記２４］
前記第１のパッチ・ライブラリは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合うブロックに分割してトレーニング・データ・セットを形成し、前記トレーニング・セットから、前記複数の重なり合うブロックのうち、既定のしきい値を超える高周波数成分を有するブロックを除去し、前記複数の重なり合うブロックの残りのブロックを複数のクラスタにクラスタリングすることによって作成され、前記複数の重なり合うブロックの前記残りの各ブロックが、前記複数の高解像度置換用パッチのそれぞれ１つを形成する、付記２１に記載の装置。
［付記２５］
前記複数のクラスタのそれぞれ１つの中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数の重なり合うブロックの前記残りのブロックの平均に対応する、付記２４に記載の装置。
［付記２６］
前記複数の重なり合うブロックの前記残りのブロックを、前記クラスタリングの前にダウンサイズして、複数のダウンサイズされた重なり合うブロックを取得し、前記クラスタリングを、前記複数のダウンサイズされた重なり合うブロックに対して実行し、前記複数のクラスタの前記それぞれ１つの前記各中心が、前記複数のクラスタの前記それぞれ１つに含まれる前記複数のダウンサイズされた重なり合うブロックの前記平均に対応する、付記２５に記載の装置。
［付記２７］
前記第２のパッチ・ライブラリに含まれる前記複数の高解像度パッチの各々について、前記複数の高解像度パッチのそれぞれ１つの平均色を含む特徴ベクトルを生成することによって、署名をそれぞれ作成する、付記２１に記載の装置。
［付記２８］
前記複数の高解像度パッチの前記それぞれ１つの前記特徴ベクトルに含まれる前記平均色は、さらに、前記複数の高解像度パッチの前記それぞれ１つに対する周囲画素の平均色である、付記２７に記載の装置。
［付記２９］
前記第１のパッチ・ライブラリは複数のパッチ・クラスタを含み、前記ピクチャの前記プルーニングされたバージョンは、前記ピクチャの前記オリジナルのバージョンを複数の重なり合わないブロックに分割し、前記複数の重なり合わないブロックの各々から前記複数のパッチ・クラスタの各々の各中心までのそれぞれの距離メトリクスに基づいて、前記複数の重なり合わないブロックのそれぞれについて、前記複数のパッチ・クラスタから候補パッチ・クラスタを探索し、１つまたは複数の基準に基づいて前記候補パッチ・クラスタからベスト・マッチング・パッチを識別し、前記複数の重なり合わないブロックのうちの対応する１つと前記ベスト・マッチング・パッチとの間の差がしきい値差未満であるときに、前記複数の重なり合わないブロックのうちの前記対応する１つをプルーニングして、プルーニングされたブロックを取得することによって生成される、付記２１に記載の装置。
［付記３０］
前記複数の重なり合わないブロックのうちの前記対応する１つと前記ベスト・マッチング・パッチとの間の前記差が前記しきい値差未満であるときに、前記メタデータは、前記ベスト・マッチング・パッチに関するパッチ指標を含み、前記メタデータは、前記プルーニングされたブロックのブロック識別子をさらに含む、付記２９に記載の装置。
【図１】
0005905889.tif 000003
【図２】
0005905889.tif 000004
【図３】
0005905889.tif 000005
【図４】
0005905889.tif 000006
【図５】
0005905889.tif 000007
【図６】
0005905889.tif 000008
【図７】
0005905889.tif 000009
【図８】
0005905889.tif 000010
【図９】
0005905889.tif 000011
【図１０】
0005905889.tif 000012
【図１１】
0005905889.tif 000013
【図１２】
0005905889.tif 000014
【図１３】
0005905889.tif 000015
【図１４】
0005905889.tif 000016
【図１５】
0005905889.tif 000017
【図１６】
0005905889.tif 000018
【図１７】
0005905889.tif 000019
【図１８】
0005905889.tif 000020
【図１９】
0005905889.tif 000021
【図２０】
0005905889.tif 000022
【図２１】
0005905889.tif 000023
【図２２】
0005905889.tif 000024
【図２３】
0005905889.tif 000025