"ビデオ処理の方法であって、受信したビデオ信号からビデオのパッチを抽出するステップと、前記パッチをグループにクラスタ化するステップと、元のビデオをダウンサイズするステップと、前記グループの代表的パッチをパッチフレームにパッケージングするステップと、前記ダウンサイズした元のビデオを、前記パッチフレームと共に、デコーダに送信するステップとを有する、方法。前記パッチフレームのデータを、前記受信したビデオ信号に連結するステップをさらに有する、請求項1に記載の方法。前記連結するステップは、通常フレームのデータを前記パッチフレームのデータに組み入れることにより行う、請求項2に記載の方法。抽出するステップを前記ビデオの特徴に基づき行う、請求項1に記載の方法。クラスタ化するステップを修正k-meansアルゴリズムに基づき行う、請求項1に記載の方法。クラスタかするステップをインクリメンタルクラスタ化を用いて行う、請求項1に記載の方法。前記パッチフレームはブロックに分割することによりダウンサイズされる、請求項1に記載の方法。前記パッチフレームはスタガリングサンプリングを用いることによりダウンサイズされる、請求項1に記載の方法。前記パッチフレームにおけるパッチの位置を、空間的及び時間的に平滑化するように、最適化する、請求項2に記載の方法。フレームがパッチフレームか、前記受信したビデオ信号のフレームかを示すフラグを用いる、請求項2に記載の方法。ビデオ処理装置であって、受信したビデオ信号からビデオのパッチを抽出して、前記パッチをグループにクラスタ化する手段と、前記受信したビデオ信号のサイズを小さくするダウンサイズ器と、前記グループの代表的パッチをパッチフレームにパッケージングする回路と、前記パッチフレームとダウンサイズされたビデオ信号とをデコーダに送信する回路とを有する、装置。前記回路は、前記パッチフレームのデータを、前記受信したビデオ信号に連結する、請求項11に記載の装置。前記回路は、前記受信したビデオ信号のデータを、パッチフレームのデータに組み込む、請求項11に記載の方法。受信したビデオ信号からビデオのパッチを抽出して、前記パッチをグループにクラスタ化する手段は、前記ビデオの特徴に基づいて抽出を行う、請求項11に記載の装置。前記クラスタ化手段は、修正k-meansアルゴリズムに基づきクラスタ化を行う、請求項11に記載の装置。前記クラスタ化手段は、インクリメンタルクラスタ化を用いてクラスタ化を行う、請求項11に記載の装置。前記回路は、パッチフレームをブロックに分割することによりダウンサイズする、請求項11に記載の装置。前記パッチフレームはスタガリングサンプリングを用いることによりダウンサイズされる、請求項11に記載の装置。前記パッチフレームにおけるパッチの位置を、空間的及び時間的に平滑化するように、最適化する、請求項12に記載の装置。フレームがパッチフレームか、前記受信したビデオ信号のフレームかを示すフラグを用いる、請求項12に記載の装置。ビデオ信号処理の方法であって、パッチフレームからビデオのパッチを抽出するステップと、抽出したパッチからパッチライブラリを生成するステップと、ビデオの通常フレームのサイズを大きくするステップと、サイズを大きくした通常ビデオフレームの低解像度のビデオ部分を、前記低解像度部分をキーワードとして用いて前記パッチライブラリからサーチしたパッチで置き換えるステップと、その結果得られたビデオに後処理を行うステップと、を有する方法。抽出はブロックベースで行われる、請求項21に記載の方法。生成するステップは、さらに、対応するパッチ中の高周波の詳細のレベルを示すフラグを、前記抽出されたパッチに付加するステップを有する、請求項21に記載の方法。パッチライブラリを生成するステップは、さらに、前記抽出されたパッチのサイズを小さくするステップを有する、請求項21に記載の方法。サイズが小さいパッチをアップサンプリング及び補間して、リサイズされたパッチとそれに対応する元のパッチとの間の距離を、所定の閾値と比較することにより、前記フラグを生成する、請求項23に記載の方法。前記抽出するステップはブロックベースで行われる、請求項21に記載の方法。前記置き換えるステップにおけるサーチは、バイナリツリーサーチを用いて行われる、請求項21に記載の方法。前記置き換えるステップで前記フラグを用いて、パッチを前記パッチライブラリのものと置き換えるか決定する、請求項23に記載の方法。前記置き換えるステップは、コスト関数の最小化に基づく、請求項21に記載の方法。前記コスト関数は空間的及び時間的な平滑性に基づく、請求項29に記載の方法。ビデオ処理装置であって、パッチフレームからビデオのパッチを抽出し、抽出したパッチからパッチライブラリを生成する手段と、通常のビデオフレームのサイズを大きくするリサイズ回路と、通常のビデオフレームの低解像のビデオ部分をキーワードとして用いて、前記パッチライブラリをサーチするパッチサーチ回路と、サイズを大きくした通常ビデオフレームの低解像度のビデオ部分を、前記パッチライブラリからサーチしたパッチで置き換えるパッチ置き換え回路と、前記パッチ置き換え回路からのビデオに後処理を行うポストプロセッサとを有する、装置。前記手段はパッチ抽出プロセッサである、請求項31に記載の装置。前記パッチ抽出器は、さらに、対応するパッチ中の高周波の詳細のレベルを示すフラグを、前記抽出されたパッチに付加する回路を有する、請求項31に記載の装置。前記パッチ抽出手段は、さらに、前記抽出されたパッチのサイズを小さくする回路を有する、請求項31に記載の装置。前記パッチ抽出手段は、さらに、サイズが小さいパッチをアップサンプリング及び補間して、リサイズされたパッチとそれに対応する元のパッチとの間の距離を、所定の閾値と比較することにより、フラグを生成する回路を有する、請求項33に記載の装置。前記パッチ置き換え回路はブロックベースで動作する、請求項31に記載の装置。前記パッチサーチ回路はバイナリツリーサーチを行う、請求項31に記載の装置。前記パッチ置き換え回路は、前記フラグから、前記サイズを大きくした通常のビデオフレームの低解像度のパッチを、前記パッチライブラリからのパッチで置き換えるか決定する、請求項33に記載の装置。前記パッチ置き換え回路は、コスト関数の最小化によりパッチを置き換える、請求項31に記載の装置。前記コスト関数は、空間的及び時間的な平滑性を測るコスト関数を最小化する、請求項39に記載の装置。本原理は、Examplebased超解像を用いたビデオ圧縮のためのデータプルーニングをする方法と装置とに関する。本原理の一態様により、ビデオ圧縮のためにデータプルーニングを用いてビデオ処理する方法が提供される。前記方法は、受信したビデオ信号からビデオのパッチ又は一部分を抽出するステップと、前記パッチをグループにクラスタ化するステップと、前記グループの代表的パッチをパッチフレームにパッケージングするステップと、デコーダに送信するステップとを有する。本原理の他の一態様により、ビデオ圧縮のためにデータプルーニングを用いてビデオ処理する装置が提供される。前記装置は、ビデオ信号からビデオのパッチを抽出して、前記パッチをグループにクラスタ化する手段と、前記グループの代表的パッチをパッチフレームにパッケージングする回路と、前記データをエンコーダに送信する回路とを有する。本原理の他の一態様により、ビデオ圧縮のためにデータプルーニングを用いてビデオ処理する装置が提供される。前記装置は、ビデオ信号からビデオのパッチを抽出して、前記パッチをグループにクラスタ化するパッチ抽出及びクラスタ化手段と、前記グループの代表的パッチをパッチフレームにパッケージングする回路と、前記データをエンコーダに送信する回路とを有する。本原理の他の一態様により、ビデオ処理方法が提供される。該方法は、パッチフレームからビデオのパッチを抽出するステップと、パッチからパッチライブラリを生成するステップと、通常のビデオフレームのサイズを大きくするステップと、通常ビデオフレームの低解像度のビデオ部分を、前記低解像度部分をキーワードとして用いて前記パッチライブラリからサーチしたパッチで置き換えるステップと、その結果得られたビデオに後処理を行うステップと、を有する。本原理の他の一態様により、ビデオ処理装置が提供される。該装置は、前記パッチフレームからパッチを抽出し、パッチライブラリを生成する手段と、通常のビデオフレームのサイズを大きくするリサイズ回路と、通常のビデオフレームの低解像度のビデオ部分をキーワードとして用いて、前記パッチライブラリをサーチするパッチサーチ回路と、前記低解像度部分を、前記パッチライブラリからサーチしたパッチで置き換えるパッチ置き換え回路と、前記パッチ置き換え回路からのビデオに後処理を行うポストプロセッサとを有する。本原理の他の一態様により、ビデオ処理装置が提供される。該装置は、前記パッチフレームからパッチを抽出し、パッチライブラリを生成するパッチ抽出プロセッサと、通常のビデオフレームのサイズを大きくするリサイズ回路と、通常のビデオフレームの低解像度のビデオ部分をキーワードとして用いて、前記パッチライブラリをサーチするパッチサーチ回路と、前記低解像度部分を、前記パッチライブラリからサーチしたパッチで置き換えるパッチ置き換え回路と、前記パッチ置き換え回路からのビデオに後処理を行うポストプロセッサとを有する。本原理の上記その他の態様、特徴、及び有利性は、添付した図面を参照して読むと、実施形態の詳細な説明から明らかとなるであろう。ここに記載する原理は、Examplebased超解像を用いた新規のデータプルーニングフレームワークを提供する。データプルーニングdatapruningは、符号化前に、入力ビデオデータの一部を削除することにより、ビデオ符号化効率をよくするビデオ前処理技術である。削除されたビデオデータは、デコーダサイドで、復号されたデータから推論することにより回復される。データプルーニングの一例は画像ライン削除である。これは入力ビデオ中の水平又は垂直のスキャンラインを削除するものである。Examplebased超解像は、入力画像中の低解像度パッチを検索キーワードとして用いてパッチライブラリ中の高解像度パッチを探し、低解像度入力画像中の低解像度パッチを、読み出した高解像度パッチで置き換えることにより、低解像度画像を高解像度画像に変換する、超解像技術である。言い換えると、低解像度パッチがパッチライブラリへのインデックスのように機能して、対応する高解像度パッチを読み出す。Examplebased超解像は、最初に、WilliamTFreemanThouisRJonesandEgonCPasztor著ExamplebasedsuperresolutionIEEEComputerGraphicsandApplicationsMarchApril2002で提案され、低解像度画像を高解像度画像に変換するのに用いられた。ここに説明された原理は、Examplebased超解像技術に基づくデータプルーニング法を表す。説明されたフレームワークでは、トランスミッタサイドにおいて、高解像度パッチをグループ化し、代表的な高解像度パッチを入力ビデオから抽出する。代表的な高解像度パッチは、一連の合成フレームパッチフレームにパッキングされる。元のビデオの解像度を下げ、パッチフレームと共にレシーバに送る。レシーバサイドでは、パッチフレームから高解像度パッチを読み出し、パッチライブラリを作る。受信され拡大されたビデオ中の低解像度パッチは、それをキーワードとして用いて、ライブラリ中の対応する高解像度パッチを検索することにより、パッチライブラリ中の高解像度パッチと置き換えられる。Examplebased超解像方法をデータプルーニングに適用するため、パッチの抽出、クラスタリング、パッチのフレームへのパッキング、及びロバストリカバリrobustrecoveryなどを含む、さらに別の問題を解決しなければならない。上記の通り、データプルーニングの既存のアプローチと比較して、本方法には多くの利点がある。第1に、入力ビデオは、ビデオ中のすべてのフレームが単純に、一様に小さいサイズにリサイズされるため、アダプティブラインアプローチやブロックリムーバルアプローチのような偽の動きの問題がない。第2に、高解像度情報は、パッチフレームで代表的なパッチを送信することにより、保存されるので、情報損失の問題は大幅に緩和される。第3に、ライン/ブロック位置や全射マップなどのメタデータをサイドチャネルにより追加的に送信する必要がほとんど又はまったく無い。ここに説明される原理は、符号化して送信する前に、入力ビデオデータをプルーニングし、復号後に、プルーニングされたビデオデータを回復する方法を提供する。データプルーニングの目的は、符号化効率を高め、所定のビデオビットレートの要求を満たすことである。本システムの一実施形態を図1に示す。エンコーダサイドでは、入力ビデオからパッチを抽出extractedして、クラスタリングアルゴリズムを用いてグループ化する。代表的なパッチを選択し、パッチフレームにパッキングする。他の経路において、アプリケーションの要請に応じて、元のビデオをあるサイズにダウンサイズする。パッチフレームは、ダウンサイズされたレギュラーフレームに付加してデコーダに送信でき、又は別のビデオとして送信できる。デコーダサイドでは、パッチはパッチフレームから抽出され、サーチアンドリプレースプロセスを最適化するように処理される。プロセスは、検索と置換のためにパッチライブラリを生成する。復号されたレギュラーフレームregularframesは、まずアップサンプリングと補間例えば、双三次補間を用いて、元のサイズにアップサイズされる。アップサイズされたフレームの低解像度パッチは、復号されたレギュラーフレーム中のパッチをキーワードとして用いて、対応する高解像度パッチを検索することにより、パッチライブラリ中のパッチと置き換えられる。ライブラリ中に高解像度パッチが見つからなければ、アップサイズされたフレーム中のパッチは置き換えられない。最後に、後処理手順を行い、回復されたビデオの時間的空間的に滑らかにする。後処理手順は、最適化ベースの方法を用いて、サーチアンドリプレースプロセスと一体化することもできる。1.パッチ抽出とクラスタリングパッチ抽出は、ビデオフレームを一組のブロックに分割して行う。本原理の一実施形態では、パッチは16×16ピクセル又は8×8ピクセルなどの四角形のブロックと定義される。各パッチは、対応するブロック画像RGBやYUVなどフォーマットは異なってもよいをベクトルに変換、すなわち平坦化flatteningすることにより、パッチベクトルとして表される。それゆえ、パッチベクトルに対応するブロック画像は、パッチベクトルを行列に変形することにより回復できる。ブロック画像を平坦化flatteningする他に、パッチベクトルは、ブロック画像から特徴例えば、カラーヒストグラムを抽出することによっても、抽出できる。パッチは一連のフレームから抽出される。長いビデオの場合には、ビデオをグループオブピクチャGOPに分割する。各GOPでクラスタリングアルゴリズムを実行できる。パッチクラスタリングの目的は、同じに見える、又は視覚的特性が類似しているパッチをグループ化することである。クラスタの代表的なパッチのみをパッチフレームにパッキングするので、クラスタ内のパッチ間の冗長性を除去できる。一実施形態では、各クラスタの代表的なパッチは、そのクラスタのパッチの平均である。クラスタリングアルゴリズムの入力は、ブロック画像の平坦化により、又は特徴抽出により抽出されたパッチベクトルである本実施例では、ブロック画像平坦化を用いる。1.1パッチクラスタリングアルゴリズムk-meansアルゴリズムLloyd’sアルゴリズムとも呼ばれるや階層化クラスタリングアルゴリズムなどの既存の多くのクラスタリングアルゴリズムをパッチクラスタリングに用いられる。我々のパッチクラスタリングアルゴリズムの要件は、クラスタ内のパッチの外観的バリエーションが大き過ぎないということである。しかし、k-meansアルゴリズムなどの通常のクラスタリングアルゴリズムは、このような要件を保証できない。そのため、本実施形態では、上記の要件を満たすstrictlyenforces修正k-meansアルゴリズムを用いる。通常のk-meansアルゴリズムは、収束するまで次の2つのステップを反復する:1.各データポイントに対して、それとクラスタ中心との間の距離が最も近いクラスタを見つける。そのデータポイントをその最も近いクラスタに割り当てる。2.すべてのデータポイントを割り当ててから、そのクラスタに割り当てられたデータポイントの平均を再計算することにより、各クラスタの中心をアップデートする。我々の修正k-meansアルゴリズムはこれと同様であるが、アウトライアーリジェクションプロセスを含む:1.各データポイントに対して、それとクラスタ中心との間の距離が最も近いクラスタを見つける。距離が指定閾値βより大きいとき、そのデータポイントはリジェクトされる。そうでなければ、そのデータポイントはそのクラスタに割り当てられる。2.すべてのデータポイントを割り当ててから、そのクラスタに割り当てられたデータポイントの平均を再計算することにより、各クラスタの中心をアップデートする。修正k-meansアルゴリズムは、クラスタ中の任意のデータポイントと、そのクラスタの中心との間の距離が、常に指定閾値βより小さいことを保証する。閾値βは、クラスタリング結果を見て値をマニュアル的に調整することにより、経験的に決定できる。従来のk-meansアルゴリズムの他の問題は、クラスタ数kをアプリオリに決定しなければならないことである。本システムでは、すべてのデータポイントが最小数のクラスタでカバーされることを要求するので、クラスタリングプロセスの前には、kは未知である。この問題を解くため、我々のクラスタリングアルゴリズムは、1つのクラスタから始めて、収束するまで修正k-meansアルゴリズムを実行し、他のクラスを加え、すべてのデータポイントがクラスタに割り当てられるまでこのプロセスを繰り返す。新しく加えられる各クラスタの中心は、既存のクラスタのどれにも割り当てられていないランダムに選択されたデータポイントで初期化される。このクラスタリングアルゴリズムの全体を図2のフローチャートに示した。1.2より効率的なパッチクラスタリングクラスタリングプロセスは一度に一つのクラスタを加え、各クラスタに対して修正k-meansアルゴリズムを実行しなければならないので、クラスタリングプロセスは遅くなりがちである。クラスタリングプロセスを速くするため、2つの方式を開発した。第1の方式は2レベルクラスタリングであり、第2の方式はインクリメンタルクラスタリングである。2レベルクラスタリングプロセス図3は、最初に、大きい閾値βを用いてクラスタリングプロセスを実行する。そのクラスタリングプロセスが完了してから、小さい閾値を用いて、第1のクラスタリングプロセスで得られた各クラスタにおいて、クラスタリングアルゴリズムを実行する。このような階層的クラスタリング方式により、速くなるが、トレードオフtradeoffとしてクラスタリング結果の精度が低下する。インクリメンタルクラスタリング方式は、最初のフレームに対してだけ、2レベルクラスタリングプロセスを実行する。その後のフレームに対しては、クラスタを再利用して、各フレームのクラスタリングプロセスを、前のフレームから受け継いだクラスタ中心で初期化する。残りのプロセスは、図2に示した基本的なクラスタリングアルゴリズムと同じである。各フレームのクラスタリングプロセスを完了してから、そのフレームのパッチを破棄してメモリ空間を節約する。また、本クラスタリングプロセスでは、クラスタ中心と、そのクラスタ中のデータポイント数のみを保持する。クラスタを更新するため、M個のデータポイントがクラスタに割り当てられているとすると、クラスタ中心は次の式を用いて更新される:ここで、Ciは更新前のi番目のクラスタ中心であり、Ciは更新されたクラスタ中心であり、Djはクラスタに割り当てられたデータポイントパッチベクトルである。Niは更新前のクラスタ中のデータポイント数である。インクリメンタルクラスタリングの利点は、クラスタリングプロセスの計算時間とメモリ空間とを両方とも節約できることである。長いビデオの場合、非インクリメンタルクラスタリングを使うと、必要な計算時間と記憶容量が非常に大きくなる。1.3グループオブピクチャGroupofPicturesパッチが多くなればなるほどクラスタも多くなる。パッチ数が大きすぎるとき、計算が遅くなりすぎ現実的ではない。そのため、長いビデオの場合、それをグループオブピクチャGOPに分割し、クラスタリングアルゴリズムが各GOP内で実行されるようにする必要がある。GOP中のフレーム数は可変でも固定でもよい。フレキシブルGOPを求める一方法は、ショット検出アルゴリズムを用いて、ビデオを複数のショットに切り分け、各ショットをGOPとすることである。GOPの長さを決定してから、パッチフレームを各GOPに連結する。GOPの長さやパッチフレーム数が可変であるとき、サイドチャネルを用いて、フレームが通常のフレームregularframeかパッチフレームかを示すメタデータ例えば、バイナリフラグを送信しなければならない。1.4クラスタ選択クラスタ選択プロセスを実行して、デコーダ側に送信するクラスタの一部を破棄するが、これはデコーダ側ではすべてのクラスタは必要ないからである。例えば、クラスタに細かいことのパッチのみが含まれる場合、そのクラスタは必要ない。高解像度のフラットパッチflatpatchesと低解像度のものとはほとんど同じだからである。一実施形態では、すべてのクラスタが保持される。その理由は、フラットパッチに追加情報が含まれていなくても、フラットパッチを破棄すると、サーチアンドリプレースプロセス中に、フラットパッチの一部が他のクラスタに引き寄せられて、目に見えるアーティファクトが生じるからである。そのため、フラットパッチクラスタをダミークラスタとして保持すれば、アーティファクトの低減という利益になる。2.パッチのパッチフレームへのパッキングGOPにおけるクラスタリングプロセスが完了してから、クラスタ中心を、各クラスタの代表的パッチとして求める。代表的なパッチをパッチフレームにパッキングする。パッチフレームとダウンサイズされた通常フレームとを連結して、デコーダ側に送信する。2.1パッチフレームの生成一実施形態では、最初に、元のビデオシーケンス中のビデオフレームと同じサイズのフレームにパッチをパッキングする。その後、大きなパッチフレームは、ダウンサイズされたビデオと同じサイズのフレームに分割される。これはいろいろな方法で実現することができる:一方法は、単に、フレームをブロックに分割することである。他の方法は、スタガリングサンプリングプロセスstaggeringsamplingprocessを用いて、サイズリダクション後、フレームがダウンサイズされた通常ビデオのように見えるようにすることである。こうすることの利益は、符号化効率が高くなることである。サンプリングされたフレームは連結された通常フレームと同じように見え、時間的空間的な平滑性が保存されるからである。スタガリングサンプリングプロセスstaggeringsamplingprocessは、画像をサンプリングして、ロケーションが異なる入力画像のサンプルを出力画像にコピーすることにより、複数の画像にする。例えば、ファクタ2のダウンサンプリングの場合、座標1,1、1,3、3,1のピクセルを第1の出力画像にコピーし、座標1,2、1,4、3,2のピクセルを第2の出力画像にコピーし、以下同様である図4に示した。留意点として、スタガリングサンプリングは、ピクセルに加えて、ブロックを基本的単位として実行することもできる。2.2パッチの位置の最適化異なる多くの方法でパッチをフレームにパッキングできる。しかし、エンコーダによりパッチフレームが効率的に圧縮できるような方法で、パッチをパッキングすべきである。これには、パッチフレームが空間的及び時間的に平滑であることを要する。パッチフレームの空間的な及び時間的な平滑性smoothnessを調整するトータルコスト関数を定義できる。しかし、かかるコスト関数を最適化するのは非常に困難である。コスト関数の入力空間はパッチの全順列だからである。それゆえ、本システムでは異なるアプローチを用いる。本システムのアプローチの背後にある根拠は、すべてのパッチは元と同じ位置にあるべきだということである。これにより、パッチフレームが元のフレームに類似し、そのため元のフレームの空間的構造が保存されることになる。これを実現するため、クラスタリングプロセス中に、各クラスタ内のパッチのフレームIDと位置とが保持される。この情報はパッチパッキングプロセス中に使われる。クラスタリングプロセスが終わると、各クラスタには、そのクラスタ内のすべてのパッチの位置情報が付加される。クラスタの代表的パッチをパッチフレーム中の対応する位置に配布する。例えば、座標1,2、2,2のタグを有する2つのパッチがクラスタに含まれているとき、そのクラスタの代表的パッチをパッチフレームの1,2ブロックと2,2ブロックに割り当てる。このプロセスを図5に示した。結果として、パッチフレームの各ブロックに複数の候補パッチを割り当ててもよい各パッチがクラスタを表す。最適化プロセスにより、ある基準例えば、空間的平滑性により、候補パッチから1つのパッチを選択する。一実施形態では、パッチフレームの各ブロック位置に対して、パッチ候補のどのブロック位置にも割り当てられていない第1のパッチを選択する。しかし、割り当てしても、ブロック位置にはまだカラemptyのものがあり、パッチにはまだ割り当てられていないものがある。すでにパッチに割り当てられた隣接ブロックとのパッチの互換性を表す尺度により、まだ割り当てられていないパッチをカラemptyのブロックに割り当てる。互換性の尺度は、隣接ブロックとのパッチの平均距離と定義される。フィルインプロセスは、隣接ブロックとの互換性の尺度が最もよいカラemptyのブロックを選択する。パッチフレーム中のカラemptyのブロックが完全には満たされていない場合、そのブロックは一定のカラーで満たされる。この一定のカラーは、一実施形態では、隣接するブロックの平均カラーである。カラのブロックがすべて満たされているが、まだ割り当てられていないパッチが残っている場合、他のパッチフレームを生成し、同じプロセスを繰り返し、まだ割り当てられていないパッチを受け入れるaccommodate。このプロセスを図6に示した。ここで説明したデータプルーニング方法は、他のビデオ符号化方法とは独立して、又は共に用いることができる。3.パッチフレームからパッチの抽出と処理パッチフレームがデコーダ側で受信されると、そのパッチフレーム中の高解像度パッチがブロック分割により抽出される。データが送信前に何らかの符号化方法で符号化されている場合、実行しなければならない復号に加えて、この抽出を行う。抽出されたパッチは、サーチテーブルすなわち、パッチライブラリを生成するのに使われ、フラットパッチ又は非フラットパッチのラベルやフラグを付加される。高解像度パッチのサイズをより小さくすることにより、サーチテーブルを生成する。そのリサイズ比はビデオフレームのリサイズ比と等しい。ダウンサイズしたパッチは、サーチアンドリプレースプロセスにおける高解像度パッチのキーワードとみなされる。タギングプロセスを行い、パッチにフラットパッチ又は非フラットパッチのマーク付けをする。フラットパッチは高周波の細部がほとんど又はまったく無いパッチである。サーチアンドリプレースプロセスはフラットパッチをスキップして、置き換えない。フラットパッチは視覚的なアーティファクトを低減するのに有用である。そのようなメカニズムを用いない場合、回復する細部をほとんど含まないパッチは、パッチライブラリ中の他のパッチに引き寄せられ、パッチの置き換えを間違ったり、視覚的なアーティファクトを生じることになるだろう。フラットパッチの分類は、最初に、アップサンプリングと補間例えば、双三次補間により、キーワードが小さいパッチを高解像度パッチと同じサイズにリサイズすることにより行う。その後、リサイズされたパッチと高解像度パッチとの間の距離を計算する。その距離が所定閾値より小さいとき、高解像度パッチにフラットパッチとマーク付けする。4.パッチサーチアンドリプレースメントパッチサーチテーブルを生成してから、パッチサーチアンドリプレースメントプロセスを実行し、低解像度入力フレームを高解像度フレームに変換する。ダウンサイズされた入力フレームは、最初にアップサンプリングと例えば、双三次補間を用いた補間とをされる。次に、サーチアンドリプレースメントプロセスを、ブロックごとに実行する。サーチアンドリプレースメントプロセスにおいて、アップサイズされたフレーム中のブロックではなく、ダウンサイズされた入力フレーム中の対応するブロックをクエリーパッチとして用いることができる。アップサイズされたものは、アップサンプリングと補間のプロセスにより歪んでおり、サーチに小さいパッチを用いる方がいくらか効率的だからである。サーチプロセスはリニアサーチ手順として実行できるが、より高度な、高速なサーチアルゴリズム例えば、バイナリツリーサーチを用いることもできる。サーチテーブル中に最も近いキーワードパッチが見つかると、アルゴリズムはそのパッチのフラットパッチタグを見る。テーブル中のパッチがフラットパッチである場合、アップサイズされたフレーム中の対応する低解像度パッチには失われた部分がないままである。さもなければ、低解像度パッチは、特定されたキーワードパッチに対応する高解像度パッチにより置き換えられる。このプロセスを図7に示した。5.サーチアンドリプレースメントプロセスの最適化サーチアンドリプレースプロセスの一問題は、空間的な及び時間的な平滑性を考慮していないことである。結果として、低解像度フレーム中のパッチがパッチテーブル中の間違ったパッチで置き換えられると、視覚的なアーティファクトが生じるおそれがある。この問題を解決する一アプローチは、後処理の利用である。一アプローチは、システムに潜在的なパッチ置き換えエラーを検出させ、そのパッチを平滑化して隣接するパッチと一貫性をもたせることである。しかし、パッチ置き換えエラーを正しく検出するのは困難であり、平滑化によりビデオフレームがぼける可能性がある。他の一アプローチは、先行技術で用いられる方法、すなわちサーチアンドリプレースメントプロセスを空間的な及び時間的な平滑性を考慮したコスト関数最小化問題として定式化する方法と同様の方法を用いることである。N個のパッチがサーチテーブルにあり、M個のパッチが高解像度パッチと置き換える必要がある低解像度フレームにあると仮定すると、低解像度フレームの各ブロック一には、7通りのパッチ置き換え方法がある。そのため、コスト関数は次の通り定義できる:ここで、Piはパッチテーブル中のパッチの選択であり、1からNまでの範囲である。λは重み付け係数である。C1は、クエリーパッチと、パッチテーブル中のPiに対応するキーワードパッチとの間の距離を測るコスト関数である。例えば、置き換える低解像度パッチに対応するダウンサイズされたパッチがIiであり、インデックスPiに対応するパッチテーブル中のキーワードパッチがGPiであるとすると、<外1>を定義することができる。C2は隣接するパッチの平滑性smoothnessを測るコスト関数であり、<外2>と定義できる。C2は、事前に計算してN×N行列として保存しておいてもよい。上記の定式化は空間的な平滑性のみに適応したものである。時間的平滑性は、他の項を加えることにより容易に組み込むことができる。例えば、<外3>ここで、C3は時間的一貫性を強制するコスト関数である。ここで、Jiは、カレントフレーム中のパッチIiに対応する、前のフレーム中のパッチである。動きを考えなければ、Jiは、単にIiと同じロケーションにある、前のフレーム中のパッチである。動きを考慮し、かつ前のフレーム中のk番目のパッチがIiに対応することが動き推定アルゴリズムにより示された場合、JiをJkに変更すべきである。μはキーワード一致コストと時間的平滑性コストとの間をバランスさせる重み付け係数である。式2の最適化を解くことは、コンピュータビジョンにおける標準的な問題である。また、例えば、BeliefPropagationアルゴリズム、GraphCutsアルゴリズム、又はモンテカルロシミュレーションなどの、異なる方法で解くこともできる。図8は、ビデオ圧縮用のデータプルーニングを用いてビデオ符号化する方法800の一実施形態を示す図である。ビデオシーケンスがプロセスに入力される。このプロセスは、ステップ810のパッチ抽出とクラスタリングで始まる。並行して、ステップ830でビデオがダウンサイズされる。ステップ810でビデオから抽出されたパッチは、ステップ820でパッチフレームにパッケージングされる。パッチフレームと、ダウンサイズされたビデオの通常フレームとは、ステップ840で、別々に、又は結合されて、デコーダに送信される。図9は、ビデオ圧縮用のデータプルーニングを用いてビデオ符号化する装置900の一実施形態を示す図である。ビデオシーケンスは、パッチ抽出クラスタ化器910に入力される。これは、ビデオからパッチを抽出して、クラスタにグループ分けする。パッチ抽出クラスタ化器910の出力は、パッチフレームビデオパッケージング回路920と信号通信している。これは、代表的なパッチを見つけてパッチフレームにパッケージングする。入力ビデオシーケンスは、小さいフレームを生成するダウンサイザ930にも入力される。パッチフレームビデオパッケージング回路920の出力は、送信回路940に入力される。送信回路940は、ダウンサイザ930の出力も入力される。図10は、ビデオを復号する方法1000の一実施形態を示す図である。本方法は、ステップ1010で、受信したビデオからパッチを抽出するパッチ抽出及び処理で始まる。受信したビデオは通常のビデオフレームとパッチフレームとから構成されている。ステップ1010と並行して、入力された通常のビデオは、ステップ1020でアップサンプリングと補間とがなされる。ステップ101でパッチが抽出されると、ステップ1030でパッチライブラリにオーガナイズされる。アップサンプリングする前のビデオの通常フレームビデオの部分、すなわち低解像度部分を用いて、ステップ1040で、ライブラリをサーチする。キーワードはパッチライブラリへのインデックス又はアドレスとして機能する。パッチ置き換えはステップ1050で行われる。ステップ1040のサーチで見つかったパッチを用いて、アップサンプリングされた通常のビデオフレームのうちの対応するビデオパッチを置き換える。次に、ステップ1060で後処理を行い、回復したビデオの空間的時間的平滑性を改善する。図11は、ビデオを復号する装置1100の一実施形態を示す図である。本装置は、受信ビデオ信号からパッチを抽出し、パッチライブラリを生成するパッチ抽出プロセッサ1110を有する。エンコーダからの入力ビデオは、入力ビデオ信号の一部として、又は入力ビデオ信号と共に受信したビデオの通常フレームをアップサンプリング及び補間するリサイジング回路1125の入力にも送られる。パッチ抽出プロセッサ1110の出力は、パッチサーチ回路1120の入力と信号通信している。このパッチサーチ回路1120は、アップサンプリング前の通常フレームの、キーワードと呼ばれるビデオの一部分を用いて、パッチライブラリをサーチして、好適な置き換えパッチを探す。パッチサーチ回路1120の出力は、パッチ置き換え回路1130の第1の入力と信号通信している。このパッチ置き換え回路1130は、リサイジング回路1120の出力も、第2の入力として受け取る。パッチ置き換え回路1130は、ビデオのアップサンプリングされた通常フレーム中のビデオの低解像度部分を、パッチサーチ回路1120により見つけられたパッチライブラリからのパッチで置き換える。パッチ置き換え回路1130の出力は、ポストプロセッサ1140の入力と信号通信している。このポストプロセッサ1140は、回復されたビデオの空間的及び時間的平滑性を改善する。このように、具体的な特徴と態様を有する1つ以上の実施形態を提供する。しかし、説明した実施形態の特徴と態様は、他の実施形態にも適合できる。例えば、これらの実施形態と特徴をビデオ及び/又はその他のタイプのデータの符号化のコンテクストで用いることができる。また、これらの実施形態と特徴は、標準のコンテクストで用いても、標準のコンテクストで用いるように構成してもよい。かかる標準には、AVC、マルチビューコーディングMVC用のAVCの拡張、スケーラブルビデオコーディングSVC用のAVCの拡張、提案されている3Dビデオコーディング3DVとハイパフォーマンスビデオコーディングHVC用のPEG/JVT標準、その他の標準既存のもの又は将来のものを用いることができる。もちろん、実施形態と特徴は、必ずしも標準で用いる必要はない。明細書において、本原理の一実施形態等と言う場合、本発明の少なくとも1つの実施形態に含まれるその実施形態に関して説明する具体的な特徴、構造、特性などを意味する。それゆえ、本明細書を通していろいろなところに記載した一実施形態において等と言った場合、必ずしもすべてが同じ実施形態を参照するものではない。ここで説明した実施形態は、方法またはプロセス、装置、またはソフトウェアプログラム、データストリーム、又は信号として実施できる。1つの形式の実施形態の場合で説明した例えば、方法としてのみ説明した場合であっても、説明した機能の実施形態は他の形式例えば、装置やプログラムでも実施できる。装置は例えば適切なハードウェア、ソフトウェア、及びファームウェアで実施可能である。上記の方法は、例えばプロセッサ等の装置で実施可能である。プロセッサとは、処理装置一般を指し、例えばコンピュータ、マイクロプロセッサ、集積回路、プログラマブル論理デバイスなどを指す。プロセッサは、エンドユーザ間での情報通信を行う、コンピュータ、セルラー電話、ポータブル/パーソナルデジタルアシスタントPDAなどのデバイス、及びその他の通信デバイスも含む。ここに説明した様々なプロセスや機能の実施形態は、様々な機器やアプリケーションに化体でき、特にデータの符号化と復号に関連する機器やアプリケーションに化体できる。かかる装置の例には、エンコーダ、デコーダ、デコーダからの出力を処理するポストプロセッサ、エンコーダに入力を供給するプリプロセッサ、ビデオコーダ、ビデオデコーダ、ビデオコーデック、ウェブサーバ、セットトップボックス、ラップトップ、パーソナルコンピュータ、セルラー電話、PDA、その他の通信デバイスが含まれる。言うまでもなく、上記の機器は可動なものであってもよいし、移動体に組み込まれていてもよい。また、上記の方法は、プロセッサによって実行される命令で実施することができる。かかる命令及び/又は、一実施形態で生成されるデータ値は、例えば集積回路、ソフトウェア担体その他の記憶デバイス、例えば、ハードディスク、コンパクトディスク、ランダムアクセスメモリRAM、リードオンリーメモリROMに記憶できる。上記の命令は、プロセッサ読み取り可能媒体上に化体されたアプリケーションプログラムであってもよい。命令は、例えば、ハードウェア、ファームウェア、ソフトウェア、又はこれらの組み合わせであってもよい。命令は、例えば、オペレーティングシステム、アプリケーション、又はこれらの組み合わせに見いだすことができる。それゆえ、プロセッサは、プロセスを実行するように構成されたデバイス、及びプロセスを実行する命令を記憶したプロセッサ読み取り可能媒体記憶デバイスなどを含むデバイスの両方として特徴付けられる。さらに、プロセッサ読み取り可能媒体は、命令に加えて、又は命令の替わりに、実施形態により生成されたデータ値を記憶することができる。当業者には言うまでもないが、実施形態は、例えば記憶または送信され得る情報を担うようフォーマットされた種々の信号を生成することもできる。情報には、例えば、方法を実行する命令や、説明した実施形態により生成されるデータが含まれ得る。かかる信号は、例えば、無線周波数のスペクトルを用いた電磁波やベースバンド信号などとしてフォーマットし得る。フォーマット化には、例えば、データストリームの符号化、符号化したデータストリームによるキャリアの変調が含まれる。信号が担う情報は例えばアナログ情報やデジタル情報であってもよい。知られているように、信号は様々な異なる有線リンクまたは無線リンクで送信できる。信号はプロセッサ読み取り可能媒体に記憶してもよい。ここで、本原理に付随する多くの有利性/特徴の一部を説明する。一部は上ですでに述べたことである。例えば、本原理の一利点は、すべてのフレームにおいて、入力ビデオがより小さいサイズに一様にリサイズされており、偽の動きアーティファクトが生じないことである。他の一利点は、パッチフレームで代表的なパッチを送信することにより、高解像度情報が保存されるので、情報損失が最小化されることである。さらに別の一利点は、本原理により、ライン又はブロック位置や全射マップなどの追加的メタデータを、サイドチャネルにより送信する必要が無いことである。実施形態を説明した。しかし、言うまでもなく様々な修正を行うことができる。例えば、別の実施形態の要素を組み合わせ、補充し、修正し、または削除して、他の実施形態を形成してもよい。また、当業者には言うまでもないが、開示した構成やプロセスを他の構成やプロセスで置き換えてもよく、その結果の実施形態が少なくとも実質的に同じ機能を果たし、少なくとも実質的に同じように、開示した実施形態と実質的に同じ結果を達成する。したがって、これらの実施形態やその他の実施形態が本開示では想定されており、本開示の範囲に入る。"