(57)【特許請求の範囲】
【請求項１】
グラフ基盤変換を用いてビデオ信号をデコーディングする方法であって、
前記ビデオ信号から、ターゲットユニットに対するテンプレートインデックスを受信するステップであって、前記テンプレートインデックスは前記ターゲットユニットに適用されるグラフ基盤変換テンプレートを指す、ステップと、
前記テンプレートインデックスに対応する前記ターゲットユニットのグラフ基盤変換行列を誘導するステップと、
前記グラフ基盤変換行列に基づいて前記ターゲットユニットをデコーディングするステップと、を含む、方法。
【請求項２】
前記テンプレートインデックスは、既に設定されたテンプレートグラフセットのうちの１つのテンプレートグラフに対応する、請求項１に記載の方法。
【請求項３】
前記既に設定されたテンプレートグラフセットは複数個のテンプレートグラフを含み、前記複数個のテンプレートグラフは前記ターゲットユニットのコーナー領域が他の領域より小さなエッジ重み付け値を有するパターンを有する、請求項２に記載の方法。
【請求項４】
前記既に設定されたテンプレートグラフセットは、前記ターゲットユニットのサンプルパターンに基づいて決定された、請求項２に記載の方法。
【請求項５】
前記テンプレートインデックスは、複数個のテンプレートグラフの各々に対して設定される、請求項１に記載の方法。
【請求項６】
グラフ基盤変換を用いてビデオ信号をエンコーディングする方法であって、
頂点パラメータセット及びエッジパラメータセットのうち、少なくとも１つを含むグラフパラメータを抽出するステップと、
前記グラフパラメータに基づいて基本テンプレートグラフを生成するステップと、
前記基本テンプレートグラフのエッジ重み付け値を調整して、テンプレートグラフセットを生成するステップと、
前記テンプレートグラフセットからターゲットユニットに対応するテンプレートグラフを決定するステップと、
前記テンプレートグラフのスペクトル分解を通じてグラフ基盤変換カーネルを獲得するステップと、を含む、方法。
【請求項７】
前記テンプレートグラフセットに含まれた複数個のテンプレートグラフの各々に対応するテンプレートインデックスを生成するステップをさらに含む、請求項６に記載の方法。
【請求項８】
前記テンプレートグラフセットは複数個のテンプレートグラフを含み、前記複数個のテンプレートグラフは前記ターゲットユニットのコーナー領域が他の領域より小さなエッジ重み付け値を有するパターンを有する、請求項６に記載の方法。
【請求項９】
前記テンプレートグラフセットは、前記ターゲットユニットのサンプルパターンに基づいて生成される、請求項６に記載の方法。
【請求項１０】
前記テンプレートグラフセットに対応するテンプレートインデックスを生成するステップをさらに含む、請求項６に記載の方法。
【請求項１１】
グラフ基盤変換を用いてビデオ信号をデコーディングする装置であって、
前記ビデオ信号からターゲットユニットに対するテンプレートインデックスを受信するエントロピーデコーディング部と、
前記テンプレートインデックスに対応する前記ターゲットユニットのグラフ基盤変換行列を誘導し、前記グラフ基盤変換行列に基づいて前記ターゲットユニットに対して逆変換を遂行する逆変換部と、を含み、
前記テンプレートインデックスは、前記ターゲットユニットに適用されるグラフ基盤変換テンプレートを指す、装置。
【請求項１２】
前記テンプレートインデックスは、既に設定されたテンプレートグラフセットのうちの１つのテンプレートグラフに対応する、請求項１１に記載の装置。
【請求項１３】
前記既に設定されたテンプレートグラフセットは複数個のテンプレートグラフを含み、前記複数個のテンプレートグラフは前記ターゲットユニットのコーナー領域が他の領域より小さなエッジ重み付け値を有するパターンを有する、請求項１２に記載の装置。
【請求項１４】
前記既に設定されたテンプレートグラフセットは、前記ターゲットユニットのサンプルパターンに基づいて決定された、請求項１２に記載の装置。
【請求項１５】
前記テンプレートインデックスは、複数個のテンプレートグラフの各々に対して設定される、請求項１１に記載の装置。
【請求項１６】
グラフ基盤変換を用いてビデオ信号をエンコーディングする装置であって、
頂点パラメータセット及びエッジパラメータセットのうちの少なくとも１つを含むグラフパラメータに基づいて基本テンプレートグラフを生成し、前記基本テンプレートグラフのエッジ重み付け値を調整してテンプレートグラフセットを生成するグラフ信号生成部と、
前記テンプレートグラフセットからターゲットユニットに対応するテンプレートグラフを決定するグラフ基盤変換テンプレート決定部と、
前記テンプレートグラフのスペクトル分解を通じてグラフ基盤変換カーネルを獲得するグラフ基盤変換算出部と、を含む、装置。
【請求項１７】
前記テンプレートグラフセットに含まれた複数個のテンプレートグラフの各々に対応するテンプレートインデックスを生成するテンプレートインデックス生成部をさらに含む、請求項１６に記載の装置。
【請求項１８】
前記テンプレートグラフセットは複数個のテンプレートグラフを含み、前記複数個のテンプレートグラフは前記ターゲットユニットのコーナー領域が他の領域より小さなエッジ重み付け値を有するパターンを有する、請求項１６に記載の装置。
【請求項１９】
前記テンプレートグラフセットは、前記ターゲットユニットのサンプルパターンに基づいて生成される、請求項１６に記載の装置。
【請求項２０】
前記テンプレートグラフセットに対応するテンプレートインデックスを生成するテンプレートインデックス生成部をさらに含む、請求項１６に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はグラフ基盤変換（graph-based transform）を用いてビデオ信号をエンコーディング、デコーディングする方法及び装置に関し、より詳しくは、グラフテンプレートに基づいて適応的な変換を遂行する技術に関する。
【背景技術】
【０００２】
次世代のビデオコンテンツは、高解像度（high spatial resolution）、高フレーム率（high frame rate）、及び映像表現の高次元化（high dimensionality of scene representation）という特徴を有するようになる。そのようなコンテンツを処理するためには、メモリ格納（memory storage）、メモリアクセス率（memory access rate）、及び処理電力（processing power）の面でおびただしい増加をもたらす。したがって、次世代のビデオコンテンツをより効率良く処理するためのコーディングツールをデザインする必要がある。
【０００３】
特に、グラフはピクセル間の関係情報を記述することに有用なデータ表現形態であって、このようなピクセル間の関係情報をグラフで表現して処理するグラフ基盤信号処理方式が活用されている。このようなグラフ基盤信号処理は、各信号サンプルが頂点（vertex）を示し、信号の関係が正の重み付け値を有するグラフエッジで示されるグラフを使用してサンプリング、フィルタリング、変換などの概念を一般化することができる。
【０００４】
したがって、より効率の良いグラフ基盤の信号処理方法がビデオ圧縮分野だけでなく、多くの応用分野で求められる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ビデオコーディング方法は、圧縮向上のためにビデオデータに対する幾つかの形態の線形変換を用いる。従来は計算的な複雑度の制限により、ビデオコーディング方法はＤＣＴ、ＤＷＴ、またはハダマード変換のような唯１つの変換のみを用いた。しかしながら、ビデオシーケンスの他の部分で信号の特定統計的特性に適合するように、より多い一般的な線形変換を用いることによって、より良いビデオ圧縮を遂行することができる。一般に、直交変換を用いるコーディングの場合、それを表現するためのビット費用が高く、変換係数を転送するビットレートオーバーヘッドが遥かに大きいという問題点がある。
【０００６】
したがって、本発明ではグラフ基盤信号処理技術を用いて間接的に直交変換を定義することによって、この問題を解決しようとする。
【０００７】
本発明は、グラフ基盤変換に対するテンプレートを定義し、これをシグナリングする方法を提供しようとする。
【０００８】
そして、本発明は、変換係数を転送する代わりに、各フレームに対してテンプレートグラフセットをエンコーディングすることによって、グラフの特性を用いる効率の良いコーディング方法を提供しようとする。
【０００９】
また、本発明は、各コーディングされたブロックに対して最適の変換を指すテンプレートインデックスを転送することによって、より効率の良いコーディング方法を提供しようとする。
【課題を解決するための手段】
【００１０】
本発明は、グラフテンプレートから誘導された変換を用いてビデオ信号をコーディングする方法を提供する。
【００１１】
本発明は、グラフテンプレートを定義し、これをシグナリングする方法を提供する。
【００１２】
本発明は、各フレームに対してテンプレートグラフセットをエンコーディングすることによって、グラフの特性を用いるコーディング方法を提供する。
【００１３】
本発明は、各コーディングされたブロックに対して最適の変換を指すテンプレートインデックスを転送する、より効率の良いコーディング方法を提供する。
【発明の効果】
【００１４】
本発明は、グラフ基盤変換テンプレートを用いることによって、インター予測されたレジデュアルブロックの効率の良い圧縮を可能にする。
【００１５】
また、グラフ基盤変換テンプレートは適応的な変換選択を可能にするので、より良いコーディングゲインを獲得することができる。
【００１６】
また、本発明はグラフ基盤変換テンプレートまたはテンプレートインデックスを定義することによって、低複雑度のコーディング遂行が可能であり、デコーダに転送するビット数を格段に減少させることができる。
【図面の簡単な説明】
【００１７】
【図１】本発明が適用される実施形態であって、ビデオ信号のエンコーディングが遂行されるエンコーダの概略的なブロック図を示す。
【図２】本発明が適用される実施形態であって、ビデオ信号のデコーディングが遂行されるデコーダの概略的なブロック図を示す。
【図３】本発明が適用される実施形態であって、コーディングユニットの分割構造を説明するための図である。
【図４】本発明が適用される一実施形態であって、１次元グラフと２次元グラフに基づいてグラフ基盤変換マトリックスを獲得する過程を説明するための図である。
【図５】本発明が適用される実施形態であって、グラフ基盤信号を処理するエンコーダの概略的ブロック図を例示する。
【図６】本発明が適用される実施形態であって、グラフ基盤信号を処理するデコーダの概略的ブロック図を例示する。
【図７】本発明が適用される実施形態であって、サンプル分散（sample variances）と関連した２種類のビデオシーケンスの統計的特性を示す。図７は２種類のビデオシーケンスに対して４ｘ４変換ブロック内の残余信号のサンプル分散（sample variances）を示し、図８は２種類のビデオシーケンスに対して８ｘ８変換ブロック内の残余信号のサンプル分散（sample variances）を示す。
【図８】本発明が適用される実施形態であって、サンプル分散（sample variances）と関連した２種類のビデオシーケンスの統計的特性を示す。図７は２種類のビデオシーケンスに対して４ｘ４変換ブロック内の残余信号のサンプル分散（sample variances）を示し、図８は２種類のビデオシーケンスに対して８ｘ８変換ブロック内の残余信号のサンプル分散（sample variances）を示す。
【図９】本発明が適用される実施形態であって、４ｘ４ブロックに対する１５個のテンプレートグラフセットを示す。
【図１０】本発明が適用される実施形態であって、８ｘ８ブロックに対する１５個のテンプレートグラフセットを示す。
【図１１】本発明が適用される実施形態であって、８ｘ８ブロックに対する１５個のテンプレートグラフセットを示す。
【図１２】本発明が適用される一実施形態であって、グラフ基盤変換部の内部ブロック図を示す。
【図１３】本発明が適用される一実施形態であって、テンプレートグラフセットに基づいてグラフ基盤変換カーネルを獲得する過程を説明するためのフローチャートである。
【図１４】本発明が適用される一実施形態であって、テンプレートインデックスを用いてグラフ基盤変換を遂行する過程を説明するためのフローチャートである。
【発明を実施するための形態】
【００１８】
本発明は、グラフ基盤変換を用いてビデオ信号をデコーディングする方法であって、前記ビデオ信号からターゲットユニットに対するテンプレートインデックス（template index）を受信するステップであって、前記テンプレートインデックスは前記ターゲットユニットに適用されるグラフ基盤変換テンプレートを指す、ステップと、前記テンプレートインデックスに対応する前記ターゲットユニットのグラフ基盤変換行列を誘導するステップと、前記グラフ基盤変換行列に基づいて前記ターゲットユニットをデコーディングするステップと、を含むことを特徴とする方法を提供する。
【００１９】
また、本発明は、前記テンプレートインデックス（template index）は既に設定されたテンプレートグラフセット（template graph set）のうちの１つのテンプレートグラフに対応することを特徴とする。
【００２０】
また、本発明は、前記既に設定されたテンプレートグラフセット（template graph set）は複数個のテンプレートグラフを含み、前記複数個のテンプレートグラフは前記ターゲットユニットのコーナー領域が他の領域より小さなエッジ重み付け値を有するパターンを有することを特徴とする。
【００２１】
また、本発明は、前記既に設定されたテンプレートグラフセット（template graph set）は、前記ターゲットユニットのサンプルパターンに基づいて決定されたことを特徴とする。
【００２２】
また、本発明は、前記テンプレートインデックス（template index）は、複数個のテンプレートグラフの各々に対して設定されることを特徴とする。
【００２３】
また、本発明は、グラフ基盤変換を用いてビデオ信号をエンコーディングする方法であって、頂点パラメータセット及びエッジパラメータセットのうち、少なくとも１つを含むグラフパラメータを抽出するステップと、前記グラフパラメータに基づいて基本テンプレートグラフ（base template graph）を生成するステップと、前記基本テンプレートグラフ（base template graph）のエッジ重み付け値（edge weight）を調整して、テンプレートグラフセット（template graph set）を生成するステップと、前記テンプレートグラフセット（template graph set）からターゲットユニットに対応するテンプレートグラフを決定するステップと、前記テンプレートグラフのスペクトル分解（spectral decomposition）を通じてグラフ基盤変換カーネルを獲得するステップと、を含むことを特徴とする方法を提供する。
【００２４】
また、本発明は、前記テンプレートグラフセットに含まれた複数個のテンプレートグラフの各々に対応するテンプレートインデックスを生成するステップをさらに含むことを特徴とする。
【００２５】
また、本発明は、前記テンプレートグラフセット（template graph set）に対応するテンプレートインデックスを生成するステップをさらに含むことを特徴とする。
【００２６】
また、本発明は、グラフ基盤変換を用いてビデオ信号をデコーディングする装置であって、前記ビデオ信号からターゲットユニットに対するテンプレートインデックス（template index）を受信するエントロピーデコーディング部と、前記テンプレートインデックスに対応する前記ターゲットユニットのグラフ基盤変換行列を誘導し、前記グラフ基盤変換行列に基づいて前記ターゲットユニットに対して逆変換を遂行する逆変換部と、を含み、前記テンプレートインデックスは、前記ターゲットユニットに適用されるグラフ基盤変換テンプレートを指すことを特徴とする装置を提供する。
【００２７】
また、本発明は、グラフ基盤変換を用いてビデオ信号をエンコーディングする装置であって、頂点パラメータセット及びエッジパラメータセットのうちの少なくとも１つを含むグラフパラメータに基づいて基本テンプレートグラフ（base template graph）を生成し、前記基本テンプレートグラフ（base template graph）のエッジ重み付け値（edge weight）を調整してテンプレートグラフセット（template graph set）を生成するグラフ信号生成部と、前記テンプレートグラフセット（template graph set）からターゲットユニットに対応するテンプレートグラフを決定するグラフ基盤変換テンプレート決定部と、前記テンプレートグラフのスペクトル分解（spectral decomposition）を通じてグラフ基盤変換カーネルを獲得するグラフ基盤変換算出部と、を含むことを特徴とする装置を提供する。
【００２８】
また、本発明は、前記テンプレートグラフセットに含まれた複数個のテンプレートグラフの各々に対応するテンプレートインデックスを生成するテンプレートインデックス生成部をさらに含むことを特徴とする。
【００２９】
また、本発明は、前記テンプレートグラフセット（template graph set）に対応するテンプレートインデックスを生成するテンプレートインデックス生成部をさらに含むことを特徴とする。
【００３０】
以下、添付した図面を参照して本発明の実施形態の構成とその作用を説明し、図面により説明される本発明の構成と作用は１つの実施形態として説明されるものであり、これによって本発明の技術的思想とその核心構成及び作用が制限されるものではない。
【００３１】
併せて、本発明で使われる用語はできる限り、現在広く使われる一般的な用語を選択したが、特定の場合は出願人が任意に選定した用語を使用して説明する。そのような場合には該当部分の詳細説明でその意味を明確に記載するので、本発明の説明で使われた用語の名称だけで単純解析されてはならず、その該当用語の意味まで把握して解析されなければならないことを明らかにしようとする。
【００３２】
また、本明細書で提示された実施形態はビデオ信号処理に関するものであるが、本発明はビデオ信号処理のみに基盤したものとして推論されてはならず、一般的なグラフ基盤の信号処理方法にも適用できるものである。
【００３３】
また、本発明で使われる用語は発明を説明するために選択された一般的な用語や、類似の意味を有する他の用語がある場合、より適切な解析のために取替え可能である。例えば、信号、データ、サンプル、ピクチャ、フレーム、ブロックなどの場合、各コーディング過程で適切に取り替えられて解析できる。また、パーティショニング（partitioning）、分解（decomposition）、スプリッティング（splitting）、及び分割（division）などの場合にも各コーディング過程で適切に代替されて解析できる。
【００３４】
ビデオコーディング方法は、圧縮を向上させるために、そのデータに対する幾つかの形態の線形変換を用いる。過去、計算的な複雑度の制限に順応するために、ビデオコーディング方法は、ＤＣＴ、ＤＷＴ、またはハダマード変換（Hardmard Transform）のような唯１つの変換のみを用いた。しかしながら、ビデオシーケンスの他の部分での信号の特定の統計的特性に適合するように変更する、より多い一般的な線形変換を用いることによって、より良いビデオ圧縮を遂行することができる。これは、直交変換を用いる場合は他の場合に比べてビット消耗が非常に高く、変換係数を転送するビットレートオーバーヘッドが遥かに大きいためである。
【００３５】
したがって、本発明ではグラフ基盤信号処理技術を用いて間接的に直交変換を定義することによって、この問題を解決しようとする。エンコーダは、変換係数を転送する代わりに、各フレームに対し、特にモーション補償されたレジデュアル信号をコーディングするためにデザインされたグラフの特性を用いてテンプレートグラフセットをエンコーディングすることができる。そして、各コーディングされたブロックに対して最適の変換を指すテンプレートインデックスをエントロピーエンコーディングして転送することができる。以下、より具体的な実施形態を説明する。
【００３６】
図１は本発明が適用される実施形態であって、ビデオ信号のエンコーディングが遂行されるエンコーダの概略的なブロック図を示す。
【００３７】
図１を参照すると、エンコーダ１００は、映像分割部１１０、変換部１２０、量子化部１３０、逆量子化部１４０、逆変換部１５０、フィルタリング部１６０、復号ピクチャバッファ（ＤＰＢ：Decoded Picture Buffer）１７０、インター予測部１８０、イントラ予測部１８５、及びエントロピーエンコーディング部１９０を含んで構成できる。
【００３８】
映像分割部１１０は、エンコーダ１００に入力された入力映像（Input image）（または、ピクチャ、フレーム）を１つ以上の処理ユニットに分割することができる。例えば、前記処理ユニットは、コーディングツリーユニット（ＣＴＵ：Coding Tree Unit）、コーディングユニット（ＣＵ：Coding Unit）、予測ユニット（ＰＵ：Prediction Unit）、または変換ユニット（ＴＵ：Transform Unit）でありうる。
【００３９】
但し、前記用語は本発明に対する説明の便宜のために使用するだけであり、本発明は該当用語の定義に限定されるものではない。また、本明細書では説明の便宜のために、ビデオ信号をエンコーディングまたはデコーディングする過程で用いられる単位としてコーディングユニットという用語を使用するが、本発明はそれに限定されず、発明内容によって適切に解析可能である。
【００４０】
エンコーダ１００は、入力映像信号でインター予測部１８０またはイントラ予測部１８５から出力された予測信号（prediction signal）を減算して残余信号（residual signal）を生成することができ、生成された残余信号は変換部１２０に転送される。
【００４１】
変換部１２０は、残余信号に変換技法を適用して変換係数（transform coefficient）を生成することができる。変換過程は正四角形の同一なサイズを有するピクセルブロックに適用されることもでき、正四角形でない可変サイズのブロックにも適用できる。前記変換部１２０は、ピクセル間の関係情報をグラフで表現して処理するグラフ基盤信号処理方式を用いることができる。例えば、前記変換部１２０はグラフ基盤変換部を含むことができ、前記グラフ基盤変換部は頂点パラメータセット及びエッジパラメータセットのうちの少なくとも１つを含むグラフパラメータを抽出し、前記グラフパラメータに基づいて基本テンプレートグラフ（base template graph）を生成し、前記基本テンプレートグラフ（base template graph）のエッジ重み付け値（edge weight）を調整してテンプレートグラフセット（template graph set）を生成することができる。そして、前記テンプレートグラフセット（template graph set）からターゲットユニットに対応するテンプレートグラフを決定した後、前記テンプレートグラフのスペクトル分解（spectral decomposition）を通じてグラフ基盤変換カーネルを獲得することができる。
【００４２】
また、本発明の一実施形態で、前記グラフ基盤変換部はテンプレートグラフセットに含まれた複数個のテンプレートグラフの各々に対応するテンプレートインデックスを生成することができる。
【００４３】
他の実施形態では、前記グラフ基盤変換部は前記テンプレートグラフセット（template graph set）に対応するテンプレートインデックスを生成することができる。
【００４４】
本発明が適用されるグラフ基盤変換部は別個の機能ユニットとして存在することができ、この場合、前記グラフ基盤変換部は前記変換部１２０の前に位置することができるが、本発明はこれに限定されるものではない。
【００４５】
量子化部１３０は変換係数を量子化してエントロピーエンコーディング部１９０に転送し、エントロピーエンコーディング部１９０は量子化された信号（quantized signal）をエントロピーコーディングしてビットストリームで出力することができる。
【００４６】
量子化部１３０から出力された量子化された信号（quantized signal）は、予測信号を生成するために利用できる。例えば、量子化された信号（quantized signal）はループ内の逆量子化部１４０及び逆変換部１５０を通じて逆量子化及び逆変換を適用することによって、残余信号を復元することができる。復元された残余信号をインター予測部１８０またはイントラ予測部１８５から出力された予測信号（prediction signal）に加えることによって、復元信号（reconstructed signal）が生成できる。
【００４７】
一方、前記のような圧縮過程で隣接したブロックが互いに異なる量子化パラメータにより量子化されることによって、ブロック境界が見える劣化が発生できる。このような現象をブロッキング劣化（blocking artifacts）といい、これは画質を評価する重要な要素の１つである。このような劣化を減らすために、フィルタリング過程を遂行することができる。このようなフィルタリング過程を通じてブロッキング劣化を除去すると共に、現在ピクチャに対する誤差を減らすことによって、画質を向上させることができるようになる。
【００４８】
フィルタリング部１６０は、復元信号にフィルタリングを適用して、これを再生装置に出力するか、または復号ピクチャバッファ１７０に転送する。復号ピクチャバッファ１７０に転送されたフィルタリングされた信号は、インター予測部１８０で参照ピクチャとして使用できる。このように、フィルタリングされたピクチャを画面間予測モードで参照ピクチャとして用いることによって、画質だけでなく、符号化効率も向上させることができる。
【００４９】
復号ピクチャバッファ１７０は、フィルタリングされたピクチャをインター予測部１８０での参照ピクチャとして使用するために格納することができる。
【００５０】
インター予測部１８０は、復元ピクチャ（reconstructed picture）を参照して時間的重複性及び／又は空間的重複性を除去するために、時間的予測及び／又は空間的予測を遂行する。ここで、予測を遂行するために用いられる参照ピクチャは以前の時間に符号化／復号化時、ブロック単位で量子化と逆量子化を経た変換された信号であるので、ブロッキングアーティファクト（blocking artifact）やリンギングアーティファクト（ringing artifact）が存在できる。
【００５１】
したがって、インター予測部１８０はこのような信号の不連続や量子化による性能の低下を解決するために、ローパスフィルタ（low pass filter）を適用することによって、ピクセル間の信号をサブピクセル単位で補間することができる。ここで、サブピクセルは補間フィルタを適用して生成された仮想の画素を意味し、整数ピクセルは復元されたピクチャに存在する実際の画素を意味する。補間方法には、線形補間、両線形補間（bi-linear interpolation）、ウィナーフィルタ（wiener filter）などが適用できる。
【００５２】
補間フィルタは復元ピクチャ（reconstructed picture）に適用されて予測の精度を向上させることができる。例えば、インター予測部１８０は整数ピクセルに補間フィルタを適用して補間ピクセルを生成し、補間ピクセル（interpolated pixels）で構成された補間ブロック（interpolated block）を予測ブロック（prediction block）に使用して予測を遂行することができる。
【００５３】
イントラ予測部１８５は、現在符号化を進行しようとするブロックの周辺にあるサンプルを参照して現在ブロックを予測することができる。前記イントラ予測部１８５は、イントラ予測を遂行するために、次のような過程を遂行することができる。まず、予測信号を生成するために必要な参照サンプルを準備することができる。そして、準備した参照サンプルを用いて予測信号を生成することができる。以後、予測モードを符号化するようになる。この際、参照サンプルは参照サンプルパッディング及び／又は参照サンプルフィルタリングを通じて準備できる。参照サンプルは、予測及び復元過程を経たため、量子化エラーが存在することがある。したがって、このようなエラーを減らすために、イントラ予測に用いられる各予測モードに対して参照サンプルフィルタリング過程が遂行できる。
【００５４】
前記インター予測部１８０または前記イントラ予測部１８５を通じて生成された予測信号（prediction signal）は、復元信号を生成するために用いられるか、または 残余信号を生成するために用いられることができる。
【００５５】
図２は本発明が適用される実施形態であって、ビデオ信号のデコーディングが遂行されるデコーダの概略的なブロック図を示す。
【００５６】
図２を参照すると、デコーダ２００は、エントロピーデコーディング部２１０、逆量子化部２２０、逆変換部２３０、フィルタリング部２４０、復号ピクチャバッファ（ＤＰＢ：Decoded Picture BufferUnit）２５０、インター予測部２６０、及びイントラ予測部２６５を含んで構成できる。
【００５７】
そして、デコーダ２００を通じて出力された復元映像信号（reconstructed video signal）は再生装置を通じて再生できる。
【００５８】
デコーダ２００は図１のエンコーダ１００から出力された信号を受信することができ、受信された信号はエントロピーデコーディング部２１０を通じてエントロピーデコーディングできる。
【００５９】
本発明の一実施形態で、前記デコーダまたは前記エントロピーデコーディング部２１０はテンプレートインデックスを受信することができる。この際、前記テンプレートインデックスはテンプレートグラフセットに含まれた複数個のテンプレートグラフの各々に対応できる。または、前記テンプレートインデックスは前記テンプレートグラフセット（template graph set）に対応されることもできる。エントロピーデコーディングされたテンプレートインデックスは逆量子化部２２０に転送されて逆量子化され、逆変換部２３０に転送されて利用できる。
【００６０】
逆量子化部２２０では量子化ステップサイズ情報を用いてエントロピーデコーディングされた信号から変換係数（transform coefficient）を獲得する。ここで、獲得された変換係数は、前記図１の変換部１２０で説明した多様な実施形態が適用されたものでありうる。
【００６１】
逆変換部２３０では、変換係数を逆変換して残余信号（residual signal）を獲得するようになる。
【００６２】
本発明の一実施形態で、前記逆変換部２３０はテンプレートインデックスに対応する前記ターゲットユニットのグラフ基盤変換行列を獲得し、それから誘導された逆変換行列を用いてターゲットユニットに対して逆変換を遂行することができる。
【００６３】
獲得された残余信号をインター予測部２６０またはイントラ予測部２６５から出力された予測信号（prediction signal）に加えることによって復元信号（reconstructed signal）が生成される。
【００６４】
フィルタリング部２４０は、復元信号（reconstructed signal）にフィルタリングを適用して、これを再生装置に出力するか、または復号ピクチャバッファ部２５０に転送する。復号ピクチャバッファ部２５０に転送されたフィルタリングされた信号はインター予測部２６０で参照ピクチャとして使用できる。
【００６５】
本明細書で、エンコーダ１００のフィルタリング部１６０、インター予測部１８０、及びイントラ予測部１８５で説明された実施形態は、各々デコーダのフィルタリング部２４０、インター予測部２６０、及びイントラ予測部２６５にも同一に適用できる。
【００６６】
図３は本発明が適用される実施形態であって、コーディングユニットの分割構造を説明するための図である。
【００６７】
エンコーダは、１つの映像（または、ピクチャ）を四角形形態のコーディングツリーユニット（ＣＴＵ：Coding Tree Unit）単位で分割することができる。そして、ラスタースキャン順序（raster scan order）に従って１つのＣＴＵずつ順次にエンコーディングする。
【００６８】
例えば、ＣＴＵのサイズは６４ｘ６４、３２ｘ３２、１６ｘ１６のうち、いずれか１つに定まることができるが、本発明はこれに限定されるものではない。エンコーダは、入力された映像の解像度または入力された映像の特性などによってＣＴＵのサイズを選択して使用することができる。ＣＴＵは、輝度（luma）成分に対するコーディングツリーブロック（ＣＴＢ：Coding Tree Block）とこれに対応する２つの色差（chroma）成分に対するコーディングツリーブロック（ＣＴＢ：Coding Tree Block）を含むことができる。
【００６９】
１つのＣＴＵは四分木（quad tree；以下、‘ＱＴ’という）構造で分解できる。例えば、１つのＣＴＵは正四角形形態を有し、かつ各辺の長さが半分ずつ減少する４個のユニットに分割できる。このようなＱＴ構造の分解は再帰的に遂行できる。
【００７０】
図３を参照すると、ＱＴのルートノード（root node）はＣＴＵと関連できる。ＱＴはリーフノード（leaf node）に到達するまで分割されることができ、この際、前記リーフノードはコーディングユニット（ＣＵ：Coding Unit）と称されることができる。
【００７１】
ＣＵは入力映像の処理過程、例えばイントラ（intra）／インター（inter）予測が遂行されるコーディングの基本単位を意味することができる。ＣＵは、輝度（luma）成分に対するコーディングブロック（ＣＢ：Coding Block）とこれに対応する２つの色差（chroma）成分に対するＣＢを含むことができる。例えば、ＣＵのサイズは６４ｘ６４、３２ｘ３２、１６ｘ１６、８ｘ８のうち、いずれか１つに定まることができるが、本発明はこれに限定されず、高解像度映像の場合、ＣＵのサイズはより大きくなるか、または多様になることができる。
【００７２】
図３を参照すると、ＣＴＵはルートノード（root node）に該当し、最も小さな深さ（depth）（即ち、レベル０）値を有する。入力映像の特性によってＣＴＵが分割されないこともあり、この場合、ＣＴＵはＣＵに該当する。
【００７３】
ＣＴＵはＱＴ形態に分解されることができ、その結果、レベル１の深さを有する下位ノードが生成できる。そして、レベル１の深さを有する下位ノードでこれ以上分割されないノード（即ち、リーフノード）はＣＵに該当する。例えば、図３（ｂ）でノードａ、ｂ、及びｊに対応するＣＵ（ａ）、ＣＵ（ｂ）、ＣＵ（ｊ）は、ＣＴＵで１回分割されたものであり、レベル１の深さを有する。
【００７４】
レベル１の深さを有するノードのうち、少なくともいずれか１つはまたＱＴ形態に分割できる。そして、レベル２の深さを有する下位ノードで、これ以上分割されないノード（即ち、リーフノード）はＣＵに該当する。例えば、図３（ｂ）でノードｃ、ｈ、及びｉに対応するＣＵ（ｃ）、ＣＵ（ｈ）、ＣＵ（ｉ）は、ＣＴＵで２回分割されたものであり、レベル２の深さを有する。
【００７５】
また、レベル２の深さを有するノードのうち、少なくともいずれか１つは、またＱＴ形態に分割できる。そして、レベル３の深さを有する下位ノードでこれ以上分割されないノード（即ち、リーフノード）はＣＵに該当する。例えば、図３（ｂ）で、ノードｄ、ｅ、ｆ、ｇに対応するＣＵ（ｄ）、ＣＵ（ｅ）、ＣＵ（ｆ）、ＣＵ（ｇ）はＣＴＵで３回分割されたものであり、レベル３の深さを有する。
【００７６】
エンコーダではビデオ映像の特性（例えば、解像度）によって、または符号化の効率を考慮してＣＵの最大サイズまたは最小サイズを決定することができる。そして、これに対する情報またはこれを誘導することができる情報がビットストリームに含まれることができる。最大サイズを有するＣＵを最大コーディングユニット（ＬＣＵ：Largest Coding Unit）と称し、最小サイズを有するＣＵを最小コーディングユニット（ＳＣＵ：Smallest Coding Unit）と称することができる。
【００７７】
また、ツリー構造を有するＣＵは予め定まった最大深さ情報（または、最大レベル情報）を有して階層的に分割できる。そして、各々の分割されたＣＵは深さ情報を有することができる。深さ情報は、ＣＵの分割された回数及び／又は程度を示すので、ＣＵのサイズに関する情報を含むこともできる。
【００７８】
ＬＣＵがＱＴ形態に分割されるので、ＬＣＵのサイズ及び最大深さ情報を利用すれば、ＳＣＵのサイズが求められる。または逆に、ＳＣＵのサイズ及びツリーの最大深さ情報を利用すれば、ＬＣＵのサイズが求められる。
【００７９】
１つのＣＵに対し、該当ＣＵが分割されるか否かを示す情報がデコーダに伝達できる。例えば、前記情報は分割フラッグとして定義されることができ、シンタックスエレメント“split_cu_flag”と表現できる。前記分割フラッグはＳＣＵを除外した全てのＣＵに含まれることができる。例えば、前記分割フラッグの値が‘１’であれば、該当ＣＵはまた４個のＣＵに分けられ、前記分割フラッグの値が‘０’であれば該当ＣＵはこれ以上分けられず、該当ＣＵに対するコーディング過程が遂行できる。
【００８０】
前述した図３の実施形態ではＣＵの分割過程に対して例に挙げて説明したが、変換を遂行する基本単位である変換ユニット（ＴＵ：Transform Unit）の分割過程に対しても前述したＱＴ構造を適用することができる。
【００８１】
ＴＵはコーディングしようとするＣＵからＱＴ構造で階層的に分割できる。例えば、ＣＵは変換ユニット（ＴＵ）に対するツリーのルートノート（root node）に該当できる。
【００８２】
ＴＵはＱＴ構造で分割されるので、ＣＵから分割されたＴＵはまた一層小さな下位ＴＵに分割できる。例えば、ＴＵのサイズは３２ｘ３２、１６ｘ１６、８ｘ８、４ｘ４のうち、いずれか１つに定まることができるが、本発明はこれに限定されず、高解像度映像の場合、ＴＵのサイズはより大きくなるか、または多様になることができる。
【００８３】
１つのＴＵに対し、該当ＴＵが分割されるか否かを示す情報がデコーダに伝達できる。例えば、前記情報は分割変換フラッグと定義されることができ、シンタックスエレメント“split_transform_flag”と表現できる。
【００８４】
前記分割変換フラッグは最小サイズのＴＵを除外した全てのＴＵに含まれることができる。例えば、前記分割変換フラッグの値が‘１’であれば該当ＴＵはまた４個のＴＵに分けられ、前記分割変換フラッグの値が‘０’であれば該当ＴＵはこれ以上分けられない。
【００８５】
前述したように、ＣＵはイントラ予測またはインター予測が遂行されるコーディングの基本単位である。入力映像をより効果的にコーディングするためにＣＵを予測ユニット（ＰＵ：Prediction Unit）単位で分割することができる。
【００８６】
ＰＵは予測ブロックを生成する基本単位であって、１つのＣＵ内でもＰＵ単位で互いに異なるように予測ブロックを生成することができる。ＰＵはＰＵが属するＣＵのコーディングモードにイントラ予測モードが使われるか、またはインター予測モードが使われるかによって異なるように分割できる。
【００８７】
図４は本発明が適用される一実施形態であって、１次元グラフと２次元グラフに基づいてグラフ基盤変換マトリックスを獲得する過程を説明するための図である。
【００８８】
本発明の一実施形態で、イメージ内のピクセルブロックの処理のために使用できるグラフタイプは、図４を通じて説明できる。例えば、図４（ａ）はピクセルブロックの各ラインに対応する１次元グラフを示し、図４（ｂ）はピクセルブロックに対応する２次元グラフを示すことができる。
【００８９】
グラフ頂点（vertex）はピクセルブロックの各ピクセルに関連し、グラフ頂点の値はピクセル値で表現できる。そして、グラフエッジ（graph edge）はグラフ頂点を連結する線を意味することができる。前記グラフエッジは信号内の如何なる形態の統計的依存性を示すために使われ、その強度を示す値をエッジ重み付け値（edge weight）ということができる。
【００９０】
例えば、図４（ａ）を見ると、１次元グラフを示し、０、１、２、３は各頂点の位置を示し、ｗ０、ｗ１、ｗ２は各頂点間のエッジ重み付け値を示す。図４（ｂ）を見ると、２次元グラフを示し、ａｉｊ（ｉ＝０、１、２、３、ｊ＝０、１、２）、ｂｋｌ（ｋ＝０、１、２、ｌ＝０、１、２、３）は各頂点間のエッジ重み付け値を示す。
【００９１】
各頂点は全ての異なる頂点に連結されることができ、０のエッジ重み付け値は互いに関連しないか、または弱く関連した頂点を連結するエッジに割り当てできる。但し、表現の簡単化のために、０のエッジ重み付け値を有するエッジは完全に除去できる。
【００９２】
本発明が適用される一実施形態で、グラフ信号から獲得される変換をグラフ基盤変換（Graph-Based transform；以下、‘ＧＢＴ’という）と定義することができる。例えば、ＴＵを構成するピクセル間の関係情報をグラフで表現するとする時、このグラフから得られた変換をＧＢＴということができる。
【００９３】
ピクセル間の関係情報は多様な方法により表現できる。例えば、ピクセル値の間の類似性、同一なＰＵに属しているか否か、同一なオブジェクトに属しているか否かなどに基づいてピクセル間の関係情報を表現することができる。前記ピクセル間の関係情報は、各ピクセルをグラフの頂点に対応させた時、ピクセルの間のエッジ有無及びエッジ重み付け値（edge weight）値で表現できる。
【００９４】
この場合、前記ＧＢＴは次のような過程を通じて獲得できる。例えば、エンコーダまたはデコーダはビデオ信号のターゲットブロックからグラフ情報を獲得することができる。前記獲得されたグラフ情報から次の＜数式１＞のようにラプラシアン行列（Laplacian matrix）Ｌを獲得することができる。
【００９５】
＜数式１＞
【数１】
0006356913.tif 000002
【００９６】
前記＜数式１＞で、Ｄは対角行列（diagonal matrix）を示し、Ａは隣接行列（adjacency matrix）を示す。
【００９７】
そして、前記ラプラシアン行列（Laplacian matrix）Ｌに対し、以下の＜数式２＞のように固有分解（eigen decomposition）を遂行することによって、ＧＢＴカーネルを獲得することができる。
【００９８】
＜数式２＞
【数２】
0006356913.tif 000003
【００９９】
前記＜数式２＞で、Ｌはラプラシアン行列（Laplacian matrix）、Ｕは固有行列（eigen matrix）、ＵＴはＵの転置行列（transpose matrix）を意味する。前記＜数式２＞で、前記固有行列（eigen matrix）Ｕは該当グラフモデルに合う信号に対して特化したグラフ基盤フーリエ（Fourier）変換を提供することができる。例えば、前記＜数式２＞を満たす固有行列（eigen matrix）ＵはＧＢＴカーネルを意味することができる。
【０１００】
図５は本発明が適用される実施形態であって、グラフ基盤信号を処理するエンコーダの概略的ブロック図を例示する。
【０１０１】
信号特性によって変わる変換としてよく知られた方法は、ＫＬＴを用いるものである。しかしながら、ＫＬＴ変換を遂行する直交マトリックスは多いビットを必要とし、ＫＬＴ変換は信号特性によく合わされた方式なので、一時的にアップデートされないと、実質的に圧縮効率は減少するという問題点がある。
【０１０２】
したがって、本発明ではグラフ信号処理を通じてこれを解決しようとする。ここで、ビデオ信号はサンプル間信号関係を示すグラフで表現できる。
【０１０３】
また、前記問題を解決するためにエッジ適応的変換（edge-adaptive transform；以下、‘ＥＡＴ’という）が利用できるが、これもまたデコーダでのエッジ信号に対するシグナリングがあまり複雑であるという問題がある。したがって、本発明はレジデュアル信号の一部の統計的特性を用いるテンプレートグラフセットを定義することによって、この問題を解決しようとする。
【０１０４】
前記図１及び図２のようなビデオコーディング構造では、ＤＣＴのような固定された変換が利用できる。これは、暗黙的に全てのレジデュアル信号が同一な等方性の統計特性を有しているという仮定下に遂行されるものである。
【０１０５】
しかしながら、現実的にビデオタイプとピクセルブロック予測で、あまり異なる分布を有することを確認することができる。したがって、本発明では、適応性及び複雑度に対する最適化を解決するために、次のような仮定に基づくことができるが、本発明はこれに限定されるものではない。
【０１０６】
第１に、本発明は統計的特性にマッチングされる各ビデオブロックに適応的に適用されるように特定線形変換を選択することができる。
【０１０７】
第２に、変換マトリックスデータを転送し、変換を選択するためのオーバーヘッドは全てのコーディングゲインに比べて比較的小さい。
【０１０８】
このような仮定に基づいて、本発明はグラフ基盤変換テンプレートに基づいて低複雑度の適応的変換を提案することによって、適応性及び複雑度に対する最適化を解決しようとする。例えば、本発明が適用されるグラフ基盤変換テンプレートはインター予測されたレジデュアル信号の統計的特性を考慮することによってデザインできる。
【０１０９】
一方、前記図５を説明すると、本発明が適用されるエンコーダ５１０は、グラフ基盤変換部５１０、量子化部５２０、逆量子化部５３０、逆変換部５４０、バッファ５５０、予測部５６０、及びエントロピーエンコーディング部５７０を含む。
【０１１０】
エンコーダ５１０はビデオ信号を受信し、前記ビデオ信号から前記予測部５６０で出力された予測された信号を差し引きしてレジデュアル信号を生成する。前記生成されたレジデュアル信号は前記グラフ基盤変換部５１０に転送され、前記グラフ基盤変換部５１０は変換方式を前記レジデュアル信号に適用することによって変換係数を生成する。
【０１１１】
ここで、本発明は、レジデュアル信号の統計的特性を活用するために、適応的で、かつ低複雑度のＧＢＴテンプレートセットを用いる方法を提案する。本明細書で使われるＧＢＴテンプレート（GBT template）、グラフテンプレート（graph template）、テンプレートグラフ（template graph）、ＧＢＴテンプレートセット（GBT template set）、グラフテンプレートセット（graph template set）、またはテンプレートグラフセット（template graph set）などの用語は、本発明を説明するために選択された一般的な用語であるので、各コーディング過程で適切に代替解析できる。
【０１１２】
前記グラフ基盤変換部５１０は、レジデュアル信号のターゲットユニットに対応するグラフ内のグラフパラメータを抽出することができる。例えば、前記グラフパラメータは、頂点パラメータ及びエッジパラメータのうち、少なくとも１つを含むことができる。前記頂点パラメータは、頂点位置及び頂点個数のうちの少なくとも１つを含み、前記エッジパラメータはエッジ重み付け値及びエッジ重み付け値の個数のうちの少なくとも１つを含むことができる。また、前記グラフパラメータは一定個数のセット（set）に定義できる。例えば、前記エッジパラメータセット（edge parameter set）は重み付け値行列（weight matrix）として定義できる。
【０１１３】
前記グラフ基盤変換部５１０は、前記抽出されたグラフパラメータに基づいてグラフ信号を生成することができる。
【０１１４】
本発明は、前記生成されたグラフ信号に対して基本テンプレート（base template）に設定することができる。以下、これを基本テンプレートグラフ（base template graph）という。例えば、前記基本テンプレートグラフは均一重み付け値が適用されたグラフ（uniformly weighted graph）であって、この場合、Ｇｕｎｉと表現できる。前記グラフ信号のノードはターゲットユニットのピクセルに対応し、ターゲットユニットの全てのエッジ重み付け値（edge weight）はＷｕｎｉに設定できる。
【０１１５】
また、本発明は、前記基本テンプレートグラフのエッジ重み付け値セットを調整することによって、Ｔ個の互いに異なるグラフを生成することができる。以下、これをテンプレートグラフセット（template graph set）といい、次の＜数式３＞のように表現することができる。
【０１１６】
＜数式３＞
【数３】
0006356913.tif 000004
【０１１７】
また、本発明は、変換ブロック内のコーナー周辺のエッジの重み付け値を減少させることによって、ブロック適応的テンプレートグラフ（block-adaptive template graph）を生成することができる。例えば、前記変換ブロック内のコーナー周辺のエッジは前記Ｗｕｎｉより小さなエッジ重み付け値であるＷｗｅａｋに設定できる。ここで、Ｗｗｅａｋは弱いエッジ重み付け値（weak edge weight）という。
【０１１８】
また、本発明は、前記変換ブロック内のコーナー周辺のエッジが同一の前記弱いエッジ重み付け値（weak edge weight）Ｗｗｅａｋ値を有するようにすることによって、複雑度を減少させることができる。
【０１１９】
また、本発明は、レジデュアルブロックの異なる位置によって適応的に信号特性を反映するために、Ｔ個の異なるグラフをテンプレートグラフセット（template graph set）として選択する方法を提供する。そして、本発明は、前記選択されたテンプレートグラフセット（template graph set）のスペクトル分解（spectral decomposition）を通じてＧＢＴを獲得することができる。
【０１２０】
前記量子化部５２０は、前記生成された変換係数を量子化して前記量子化された係数をエントロピーエンコーディング部５７０に転送する。
【０１２１】
前記エントロピーエンコーディング部５７０は、前記量子化された信号に対するエントロピーコーディングを遂行し、エントロピーコーディングされた信号を出力する。
【０１２２】
前記量子化部５２０により出力された前記量子化された信号は、予測信号を生成するために使用できる。例えば、前記エンコーダ５１０のループ内の前記逆量子化部５３０及び前記逆変換部５４０は、前記量子化された信号がレジデュアル信号に復元されるように前記量子化された信号に対する逆量子化及び逆変換を遂行することができる。復元された信号は、前記復元されたレジデュアル信号を前記予測部５６０により出力された予測信号に加えることによって生成できる。
【０１２３】
前記バッファ５５０は、予測部５６０の今後の参照のために復元された信号を格納する。
【０１２４】
前記予測部５６０は、以前に復元されて前記バッファ５５０に格納された信号を使用して予測信号を生成することができる。このような場合、本発明はアンカー（anchor）イメージ内の領域を使用して目標イメージ内の領域を効率良く予測することに関連したものである。ここで、前記アンカーイメージは、参照イメージ、参照ピクチャ、または参照フレームを意味することができる。効率は率−歪曲（Rate-Distortion）費用またはレジデュアル信号内の歪曲を定量化する平均二乗エラーを算出することによって決定できる。
【０１２５】
本発明はグラフ内の頂点とエッジを識別し、残余値信号をエンコーディングまたはデコーディングする方法を提案する。例えば、本発明の実施形態はグラフ基盤変換部５１０を通じて多様な実施形態を遂行することができる。前記グラフ基盤変換部５１０は、前記エンコーダ５１０または前記デコーダ７００に含まれることができる。
【０１２６】
図６は本発明が適用される実施形態であって、グラフ基盤信号を処理するデコーダの概略的ブロック図を例示する。
【０１２７】
図６のデコーダ６００は、図５のエンコーダ５１０により出力された信号を受信する。
【０１２８】
前記エントロピーデコーディング部６１０は、受信された信号に対するエントロピーデコーディングを遂行する。前記逆量子化部６２０は、量子化ステップサイズに対する情報に基づいて前記エントロピーデコーディングされた信号から変換係数を獲得する。
【０１２９】
前記逆変換部６３０は、変換係数に対する逆変換を遂行することによって、レジデュアル信号を取得する。この際、前記逆変換は前記エンコーダ５１０で獲得されたグラフ基盤変換に対する逆変換を意味することができる。
【０１３０】
本発明の一実施形態で、前記逆変換部６３０は、グラフ基盤変換テンプレートを示すテンプレートインデックスを受信し、前記テンプレートインデックスに対応するグラフ基盤変換カーネルを獲得することができる。前記獲得されたグラフ基盤カーネルを用いて変換ユニットを復元することができる。
【０１３１】
前記レジデュアル信号を前記予測部６５０により出力された予測信号に加えることによって復元信号が生成できる。
【０１３２】
前記バッファ６４０は、前記予測部６５０の今後の参照のために前記復元信号を格納する。
【０１３３】
前記予測部６５０は、以前に復元されて前記バッファ６４０に格納された信号に基づいて予測信号を生成する。
【０１３４】
図７及び図８は本発明が適用される実施形態であって、サンプル分散（sample variances）と関連した２種類のビデオシーケンスの統計的特性を示す。
【０１３５】
図７は２種類のビデオシーケンスに対して４ｘ４変換ブロック内の残余信号のサンプル分散（sample variances）を示し、図８は２種類のビデオシーケンスに対して８ｘ８変換ブロック内の残余信号のサンプル分散（sample variances）を示す。
【０１３６】
前記図７及び図８を説明すると、４ｘ４変換ブロック及び８ｘ８変換ブロックのコーナー部分が他の部分よりサンプル分散（sample variances）がより大きいことを確認することができる。これは、インター予測時、予測されたブロックと参照ブロックとの間の不一致（mismatch）ためである。例えば、全体ブロック内に不一致（mismatch）があれば、イントラ予測が選択される傾向がある一方、ブロック内のコーナー部分に限定された不一致（mismatch）があれば、インター予測が選択される傾向がある。
【０１３７】
したがって、本発明は、変換ブロックのコーナー部分でサンプル分散（sample variances）が大きいという点に基づいて、変換ブロックのコーナー部分をカバーするテンプレートグラフセットを定義しようとする。以下、図９から図１１では、テンプレートグラフセットの具体的な実施形態を説明する。
【０１３８】
図９は本発明が適用される実施形態であって、４ｘ４ブロックに対する１５個のテンプレートグラフセット（template graph set）を示す。
【０１３９】
前記図９で説明する本発明の一実施形態は４ｘ４ブロックに対する１５個のテンプレートグラフセット（template graph set）を示しているが、本発明はそれに限定されず、より多いテンプレートグラフセット（template graph set）として定義することもでき、より少ないテンプレートグラフセット（template graph set）として定義することもできる。即ち、テンプレートグラフセット（template graph set）を定義する基準を何とするかによってテンプレートグラフセット（template graph set）の個数が変わる。例えば、前記基準はエッジ重み付け値パターン、ピクセル値パターン、ノード連結パターンのうち、少なくとも１つを含むことができる。具体的な例として、エッジ重み付け値パターンの場合、変換ブロック内の弱いエッジ重み付け値を有する部分に対して特定パターンを形成することができる。
【０１４０】
前記図９の実施形態は、弱いエッジ重み付け値を有する部分に対する特定パターンを示す。例えば、変換ブロックのコーナーが４箇所に存在すると仮定する時、テンプレートグラフセット（template graph set）は４個のコーナー部分の多様な組み合わせに基づいて定義できる。
【０１４１】
具体的な例として、図９（ａ）は１つのコーナー部分が相対的に弱いエッジ重み付け値を有する場合に該当するテンプレートグラフセット（template graph set）を示す。即ち、テンプレート１は左上側コーナー部分の弱いエッジ重み付け値を有する場合であり、テンプレート２は左下側コーナー部分の弱いエッジ重み付け値を有する場合であり、テンプレート３は右下側コーナー部分の弱いエッジ重み付け値を有する場合であり、テンプレート４は右上側コーナー部分の弱いエッジ重み付け値を有する場合に対応する。
【０１４２】
図９（ｂ）は、２つのコーナー部分が相対的に弱いエッジ重み付け値を有する場合に該当するテンプレートグラフセット（template graph set）を示す。前記図９（ａ）と同様に、２つのコーナー部分の可能な全ての組み合わせは、図９（ｂ）の６個のテンプレート（テンプレート５〜１０）として定義できる。
【０１４３】
図９（ｃ）は、３個のコーナー部分が相対的に弱いエッジ重み付け値を有する場合に該当するテンプレートグラフセット（template graph set）を示す。前記図９（ａ）及び図９（ｂ）と同様に、３個のコーナー部分の可能な全ての組み合わせは図９（ｃ）の４個のテンプレート（テンプレート１１〜１４）として定義できる。
【０１４４】
図９（ｄ）は、４個のコーナー部分が相対的に弱いエッジ重み付け値を有する場合に該当するテンプレートグラフセット（template graph set）を示す。４個のコーナー部分の可能な全ての組み合わせは図９（ｄ）の１つのテンプレート（テンプレート１５）として定義できる。
【０１４５】
図９（ａ）から図９（ｄ）では、コーナー部分の組み合わせ個数によって区分して説明したが、本発明はこれに限定されず、図９（ａ）から図９（ｄ）の各実施形態を組み合わせることも可能である。
【０１４６】
図１０及び図１１は本発明が適用される実施形態であって、８ｘ８ブロックに対する１５個のテンプレートグラフセットを示す。
【０１４７】
前記図１０及び図１１で説明する本発明の一実施形態は、８ｘ８ブロックに対する１５個のテンプレートグラフセット（template graph set）を示しているが、本発明はそれに限定されず、前記図９の実施形態のように多様な方法が適用できる。但し、前記図１０及び図１１の場合、８ｘ８ブロックであるので、弱いエッジ重み付け値が適用されるコーナーをどこまで定義するかによって、より多い実施形態が発生することができる。
【０１４８】
前記図１０及び図１１では、弱いエッジ重み付け値が適用されるコーナーが図面に描かれた形態のようなパターンに形成される場合を示す。仮に、弱いエッジ重み付け値が適用されるコーナーが異なるパターンに形成される場合であれば、異なる形態のテンプレートが定義されることができ、またより多い数のテンプレートが定義できる。
【０１４９】
前記図９と同様に、図１０（ａ）は１つのコーナー部分が相対的に弱いエッジ重み付け値を有する場合に該当するテンプレートグラフセット（template graph set）を示し、図１０（ｂ）は２つのコーナー部分が相対的に弱いエッジ重み付け値を有する場合に該当するテンプレートグラフセット（template graph set）を示す。
【０１５０】
そして、図１１（ａ）は３個のコーナー部分が相対的に弱いエッジ重み付け値を有する場合に該当するテンプレートグラフセット（template graph set）を示し、図１１（ｂ）は４個のコーナー部分が相対的に弱いエッジ重み付け値を有する場合に該当するテンプレートグラフセット（template graph set）を示す。
【０１５１】
図１０から図１１でも、コーナー部分の組み合わせ個数によって区分して説明したが、本発明はこれに限定されず、図９から図１１の各実施形態を組み合わせることも可能である。
【０１５２】
図１２は本発明が適用される一実施形態であって、グラフ基盤変換部の内部ブロック図を示す。
【０１５３】
図１２を参照すると、グラフ基盤変換部５１０は、グラフパラメータ抽出部５１１、グラフ信号生成部５１２、グラフ基盤変換算出部５１３、変換遂行部５１４、グラフ基盤変換テンプレート決定部５１５、及びテンプレートインデックス生成部５１６を含むことができる。
【０１５４】
グラフパラメータ抽出部５１１は、残余信号のターゲットユニットに対応するグラフ内のグラフパラメータを抽出することができる。例えば、前記グラフパラメータは、頂点パラメータ及びエッジパラメータのうち、少なくとも１つを含むことができる。前記頂点パラメータは、頂点位置及び頂点個数のうちの少なくとも１つを含み、前記エッジパラメータはエッジ重み付け値及びエッジ重み付け値の個数のうち、少なくとも１つを含むことができる。また、前記グラフパラメータは一定個数のセット（set）として定義できる。
【０１５５】
グラフ信号生成部５１２は、前記グラフパラメータ抽出部５１１から抽出されたグラフパラメータに基づいてグラフ信号を生成することができる。
【０１５６】
前記生成されたグラフ信号は基本テンプレート（base template）に設定されることができ、これを基本テンプレートグラフ（base template graph）という。例えば、前記基本テンプレートグラフは均一重み付け値が適用されたグラフ（uniformly weighted graph）であって、この場合、Ｇｕｎｉと表現できる。前記グラフ信号のノードはターゲットユニットのピクセルに対応し、ターゲットユニットの全てのエッジ重み付け値（edge weight）はＷｕｎｉに設定できる。
【０１５７】
【化１】
0006356913.tif 000005
【０１５８】
前記グラフ信号生成部５１２は、変換ブロック内のコーナー周辺のエッジの重み付け値を減少させることによって、ブロック適応的テンプレートグラフ（block-adaptive template graph）を生成することができる。例えば、前記変換ブロック内のコーナー周辺のエッジは前記Ｗｕｎｉより小さなエッジ重み付け値であるＷｗｅａｋに設定できる。ここで、Ｗｗｅａｋは弱いエッジ重み付け値（weak edge weight）という。この際、前記変換ブロック内のコーナー周辺のエッジは同一な前記弱いエッジ重み付け値（weak edge weight）Ｗｗｅａｋ値を有することができる。
【０１５９】
グラフ基盤変換テンプレート決定部５１５は、レジデュアルブロックの異なる位置によって適応的に信号特性を反映するために、Ｔ個の異なるグラフをテンプレートグラフセット（template graph set）に決定することができる。
【０１６０】
グラフ基盤変換算出部５１３は、前記決定されたテンプレートグラフセット（template graph set）のスペクトル分解（spectral decomposition）を通じてグラフ基盤変換カーネルを獲得することができる。
【０１６１】
変換遂行部５１４は、前記獲得されたグラフ基盤変換カーネルを用いて変換を遂行することができる。
【０１６２】
一方、テンプレートインデックス生成部５１６は、前記グラフ基盤変換テンプレート決定部５１５から決定されたテンプレートグラフセット（template graph set）に対してテンプレートインデックスを与えることができる。または、前記テンプレートグラフセット（template graph set）に含まれたＴ個の異なるグラフの各々に対して別個のテンプレートインデックスを設定することもできる。この場合、前記テンプレートグラフセット（template graph set）にはテンプレートグループインデックスを別個に設定することもできる。
【０１６３】
前記設定されたテンプレートインデックスは、エントロピーエンコーディング部に転送されてエントロピーエンコーディングされ、以後、デコーダに転送できる。
【０１６４】
図１３は本発明が適用される一実施形態であって、テンプレートグラフセットに基づいてグラフ基盤変換カーネルを獲得する過程を説明するためのフローチャートである。
【０１６５】
エンコーダは受信されたビデオ信号から予測信号を生成し、ビデオ信号で予測信号を減算して残余信号を生成することができる。前記残余信号に対して変換が遂行されるが、この際、グラフ基盤信号処理技術を適用してグラフ基盤変換を遂行することができる。
【０１６６】
エンコーダは、残余信号のターゲットユニット（例えば、変換ユニット）に対応するグラフ内のグラフパラメータを抽出することができる（Ｓ１３１０）。この際、前記グラフパラメータは頂点パラメータセット及びエッジパラメータセットのうち、少なくとも１つを含むことができる。
【０１６７】
前記エンコーダは、前記グラフパラメータに基づいて基本テンプレートグラフを生成することができる（Ｓ１３２０）。例えば、前記基本テンプレートグラフは均一重み付け値が適用されたグラフ（uniformly weighted graph）であって、この場合、Ｇｕｎｉと表現できる。前記グラフ信号のノードは、ターゲットユニットのピクセルに対応し、ターゲットユニットの全てのエッジ重み付け値（edge weight）はＷｕｎｉに設定できる。
【０１６８】
前記エンコーダは、前記基本テンプレートグラフのエッジ重み付け値セットを調整することによって、テンプレートグラフセット（template graph set）を生成することができる（Ｓ１３３０）。ここで、前記テンプレートグラフセット（template graph set）をブロック適応的テンプレートグラフ（block-adaptive template graph）ということができる。例えば、前記変換ブロック内のコーナー周辺のエッジは、前記Ｗｕｎｉより小さなエッジ重み付け値であるＷｗｅａｋに設定できる。ここで、Ｗｗｅａｋは弱いエッジ重み付け値（weak edge weight）を示す。この際、前記変換ブロック内のコーナー周辺のエッジは同一な前記弱いエッジ重み付け値（weak edge weight）Ｗｗｅａｋ値を有することができる。
【０１６９】
前記エンコーダは、前記テンプレートグラフセット（template graph set）からターゲットユニットに対応するテンプレートグラフを決定することができる（Ｓ１３４０）。この場合、前記決定されたテンプレートグラフセット（template graph set）に対してテンプレートインデックスを設定することができる。または、前記テンプレートグラフセット（template graph set）に含まれたＴ個の異なるグラフの各々に対して別個のテンプレートインデックスを設定することもできる。この場合、前記テンプレートグラフセット（template graph set）にはテンプレートグループインデックスを別個に設定することもできる。
【０１７０】
前記エンコーダは、前記テンプレートグラフのスペクトル分解を通じてグラフ基盤変換カーネルを獲得することができる。（Ｓ１３５０）。前記獲得されたグラフ基盤変換カーネルに基づいてターゲットユニットに対して変換を遂行することができる。
【０１７１】
図１４は本発明が適用される一実施形態であって、テンプレートインデックスを用いてグラフ基盤変換を遂行する過程を説明するためのフローチャートである。
【０１７２】
本発明が適用されるデコーダは、ビデオ信号からターゲットユニットに対するテンプレートインデックス（template index）を受信することができる（Ｓ１４１０）。ここで、前記テンプレートインデックスはテンプレートグラフセット（template graph set）に対して設定できる。または、前記テンプレートグラフセット（template graph set）に含まれたＴ個の異なるグラフの各々に対して別個のテンプレートインデックスが設定されることもできる。
【０１７３】
前記デコーダは、前記テンプレートインデックスに対応する前記ターゲットユニットの変換行列を誘導することができる（Ｓ１４２０）。例えば、前記変換行列は前記テンプレートインデックスに対応するグラフ基盤変換カーネルを含むことができる。
【０１７４】
前記変換行列に基づいて前記ターゲットユニットをデコーディングすることができる（Ｓ１４３０）。
【０１７５】
このように、グラフ基盤変換テンプレートを用いることによって、インター予測されたレジデュアルブロックの効率の良い圧縮が可能であり、適応的な変換選択が可能であるので、より良いコーディングゲインを獲得することができる。また、テンプレートインデックスを定義することによって、低複雑度のコーディング遂行が可能であり、デコーダに転送するビット数を格段に減少させることができる。
【０１７６】
前記記述されたように、本発明で説明した実施形態は、プロセッサ、マイクロプロセッサ、コントローラ、またはチップ上で具現されて遂行できる。例えば、前記図１、図２、 図５、 及び図６で図示した機能ユニットは、コンピュータ、プロセッサ、マイクロプロセッサ、コントローラ、またはチップ上で具現されて遂行できる。
【０１７７】
また、本発明が適用されるデコーダ及びエンコーダは、マルチメディア放送送受信装置、モバイル通信端末、ホームシネマビデオ装置、デジタルシネマビデオ装置、監視用カメラ、ビデオ対話装置、ビデオ通信などのリアルタイム通信装置、モバイルストリーミング装置、格納媒体、カムコーダ、注文型ビデオ（ＶｏＤ）サービス提供装置、インターネットストリーミングサービス提供装置、３次元（３Ｄ）ビデオ装置、画像電話ビデオ装置、及び医療用ビデオ装置などに含まれることができ、ビデオ信号及びデータ信号を処理するために使用できる。
【０１７８】
また、本発明が適用される処理方法はコンピュータにより実行されるプログラムの形態に生産されることができ、コンピュータにより読み取ることができる記録媒体に格納できる。本発明に従うデータ構造を有するマルチメディアデータもまたコンピュータにより読み取ることができる記録媒体に格納できる。前記コンピュータにより読み取ることができる記録媒体はコンピュータにより読み取ることができるデータが格納される全ての種類の格納装置を含む。前記コンピュータにより読み取ることができる記録媒体は、例えば、ブルーレイディスク（ＢＤ）、汎用直列バス（ＵＳＢ）、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピーディスク、及び光学的データ格納装置を含むことができる。また、前記コンピュータにより読み取ることができる記録媒体は、搬送波（例えば、インターネットを通じての転送）の形態に具現されたメディアを含む。また、エンコーディング方法により生成されたビットストリームがコンピュータにより読み取ることができる記録媒体に格納されるか、または有無線通信ネットワークを介して転送できる。
【産業上の利用可能性】
【０１７９】
以上、前述した本発明の好ましい実施形態は、例示の目的のために開示されたものであって、当業者であれば、以下に添付した特許請求の範囲に開示された本発明の技術的思想とその技術的範囲内で、多様な他の実施形態を改良、変更、取替、または付加などが可能である。
【図１】
0006356913.tif 000006
【図２】
0006356913.tif 000007
【図３】
0006356913.tif 000008
【図４（ａ）】
0006356913.tif 000009
【図４（ｂ）】
0006356913.tif 000010
【図５】
0006356913.tif 000011
【図６】
0006356913.tif 000012
【図７】
0006356913.tif 000013
【図８】
0006356913.tif 000014
【図９】
0006356913.tif 000015
【図１０】
0006356913.tif 000016
【図１１】
0006356913.tif 000017
【図１２】
0006356913.tif 000018
【図１３】
0006356913.tif 000019
【図１４】
0006356913.tif 000020