(57)【特許請求の範囲】
【請求項１】
グラフ信号を用いてグラフベース予測を実行する方法であって、
コンテキスト信号を獲得するステップと、
グラフパラメータセットに基づいてグラフ信号を生成するステップと、
前記グラフ信号に基づいてグラフベース変換行列を獲得するステップであって、前記グラフベース変換行列は固有ベクトルを有するステップと、
最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得するステップと、
前記予測ベクトルを用いて予測信号を生成するステップと、を有し、
前記最適化関数は、前記コンテキスト信号、グラフラプラシアン行列の固有値及び前記固有ベクトルを変数として有する、ことを特徴とする方法。
【請求項２】
前記予測ベクトルは、変換ベクトルと前記固有ベクトルとの線形結合に基づいて獲得され、
前記変換ベクトルは、前記グラフラプラシアン行列の固有値の分布に基づくコスト関数を用いて決定される、請求項１に記載の方法。
【請求項３】
前記グラフ信号に基づいてグラフラプラシアン行列を算出するステップをさらに有し、
前記グラフベース変換行列は、前記グラフラプラシアン行列のスペクトル分解を通じて獲得される、請求項１に記載の方法。
【請求項４】
前記最適化関数は、ラグランジュ乗数に基づく非制限最適化関数で表現され、
前記非制限最適化関数は、新たなＭ次元ベクトルにより表現される、請求項１に記載の方法。
【請求項５】
予測エラーをエンコードするステップと、
前記エンコードされた予測エラーを転送するステップと、をさらに有する、請求項１に記載の方法。
【請求項６】
グラフベース予測に基づいてビデオ信号をデコードする方法であって、
グラフパラメータセット及び残差信号を有する前記ビデオ信号を受信するステップと、
前記グラフパラメータセットに基づいて固有ベクトルを有するグラフベース変換行列を獲得するステップと、
最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得するステップと、
前記予測ベクトルを用いて予測信号を生成するステップと、
前記予測信号と前記残差信号とを合せて前記ビデオ信号を復元するステップと、を有し、
前記最適化関数は、コンテキスト信号、グラフラプラシアン行列の固有値及び前記固有ベクトルを変数として有する、ことを特徴とする方法。
【請求項７】
前記予測ベクトルは、変換ベクトルと前記固有ベクトルとの線形結合に基づいて獲得され、
前記変換ベクトルは、前記グラフラプラシアン行列の固有値の分布に基づくコスト関数を用いて決定される、請求項６に記載の方法。
【請求項８】
前記コスト関数は、前記変換ベクトルの凸関数であり、
前記凸関数は、変換ベクトル成分の重み付けされたＰ−ノルム（weighted P-norm of the transform vector components）を有する、請求項７に記載の方法。
【請求項９】
前記最適化関数は、ラグランジュ乗数に基づく非制限最適化関数で表現され、
前記非制限最適化関数は、新たなＭ次元ベクトルにより表現された、請求項８に記載の方法。
【請求項１０】
前記グラフベース変換行列は、グラフラプラシアン行列のスペクトル分解を通じて獲得された、請求項６に記載の方法。
【請求項１１】
グラフ信号を用いてグラフベース予測を実行する装置であって、
グラフパラメータセットに基づいてグラフ信号を生成し、前記グラフ信号に基づいて固有ベクトルを有するグラフベース変換行列を獲得するグラフベース変換部と、
コンテキスト信号を獲得し、最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得し、前記予測ベクトルを用いて予測信号を生成する予測部と、を有し、
前記最適化関数は、前記コンテキスト信号、グラフラプラシアン行列の固有値及び前記固有ベクトルを変数として有する、ことを特徴とする装置。
【請求項１２】
前記予測ベクトルは、変換ベクトルと前記固有ベクトルとの線形結合に基づいて獲得され、
前記変換ベクトルは、前記グラフラプラシアン行列の固有値の分布に基づくコスト関数を用いて決定される、請求項１１に記載の装置。
【請求項１３】
前記グラフベース変換部は、前記グラフ信号に基づいてグラフラプラシアン行列を算出し、
前記グラフベース変換行列は、前記グラフラプラシアン行列のスペクトル分解を通じて獲得される、請求項１１に記載の装置。
【請求項１４】
前記最適化関数は、ラグランジュ乗数に基づく非制限最適化関数で表現され、
前記非制限最適化関数は、新たなＭ次元ベクトルにより表現される、請求項１１に記載の装置。
【請求項１５】
予測エラーをエンコードし、前記エンコードされた予測エラーを転送するエントロピエンコーディング部をさらに有する、請求項１１に記載の装置。
【請求項１６】
グラフベース予測に基づいてビデオ信号をデコードする装置であって、
グラフパラメータセット及び残差信号を有する前記ビデオ信号を受信するエントロピデコーディング部と、
前記グラフパラメータセットに基づいて固有ベクトルを有するグラフベース変換行列を獲得する逆変換部と、
最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得し、前記予測ベクトルを用いて予測信号を生成する予測部と、
前記予測信号と前記残差信号とを合せて前記ビデオ信号を復元する復元部と、を有し、
前記最適化関数は、コンテキスト信号、グラフラプラシアン行列の固有値及び前記固有ベクトルを変数として有する、ことを特徴とする装置。
【請求項１７】
前記予測ベクトルは、変換ベクトルと前記固有ベクトルとの線形結合に基づいて獲得され、
前記変換ベクトルは、前記グラフラプラシアン行列の固有値の分布に基づくコスト関数を用いて決定される、請求項１６に記載の装置。
【請求項１８】
前記コスト関数は、前記変換ベクトルの凸関数であり、
前記凸関数は、変換ベクトル成分の重み付けされたＰ−ノルム（weighted P-norm of the transform vector components）を有する、請求項１７に記載の装置。
【請求項１９】
前記最適化関数は、ラグランジュ乗数に基づく非制限最適化関数で表現され、
前記非制限最適化関数は、新たなＭ次元ベクトルにより表現された、請求項１８に記載の装置。
【請求項２０】
前記グラフベース変換行列は、グラフラプラシアン行列のスペクトル分解を通じて獲得された、請求項１６に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフベース（基盤）の（グラフに基づく）信号処理方法及び装置に関し、より詳しくは、最適化関数を用いてグラフベース予測を実行（遂行）する技術に関する。
【背景技術】
【０００２】
従来の離散時間信号処理技術は、大部分がアナログ信号の処理及びフィルタリングから発展（進化）してきているが、正規に組織されたデータのサンプリングのように幾つかの共通の仮定により制限されてきた。ビデオ圧縮分野は、基本的に同一の仮定に基づいて（基盤して）おり、単に多次元信号の処理に一般化されただけである。
【０００３】
グラフは、多くの応用分野においてデータの幾何学的構造を記述することに有用なデータ表現形態である。このようなグラフに基づいた信号処理は、各信号サンプルが頂点（vertex）を示し、信号の関係が正の重み付け値を有するグラフエッジで示されるグラフを使用して、サンプリング、フィルタリング、フーリエ（Fourier）変換などの概念を一般化することができる。この方式は、信号を獲得する過程と分離することによって、サンプリング及びシーケンス処理においてグラフの特性に置き換え（取り替え）ることができる。したがって、より効率の良いグラフベースの信号処理方法がビデオ圧縮分野だけでなく多くの応用分野で要求される。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
全てのビデオコーディング標準は、その基本要素のうちの１つとして信号予測を含んでおり、その圧縮効率は予測方法の正確性及び信頼性により強い影響を受ける。信号の統計的モデルに基づく信号予測のための多くの異論的なツールがある。しかしながら、オーディオ、イメージ、ビデオなどの複雑な信号にツールを適用するとき、多くの実質的な問題が発生する。例えば、モデルパラメータを信頼性あるように測定することは非常に難しい。なぜならば、モデルパラメータは、他のソース、さらには同一のソースの場合にも相当に変わることができるためである。重要なことは、圧縮において予測の利用は基本であり、他のアプリケーションと重要な差異点を有するということである。しかしながら、信号の圧縮のために実際に用いられる多くの予測方法は、実験的な統計に基づくという問題点がある。
【０００５】
また、信号処理及び圧縮のために新たなグラフモデルが提案されてきた。これは、グラフモデルがエッジ及び不連続性などの一部の局所的な信号特性を、一般的な統計的数値により提供されるものより遥かに簡潔で、圧縮により適合した方式によりモデル化（モデリング）できるためである。例えば、グラフのラプラシアン行列（マトリックス）のスペクトル分解は、グラフモデルに合う信号に適合したフーリエ分析の形態を提供する。
【０００６】
したがって、本発明は、変数間の統計的相関関係をモデル化するグラフが与えられているとき、低い複雑度で、より良い予測子を探すための方法を提供しようとする。
【課題を解決するための手段】
【０００７】
本発明は、最適化関数を用いてグラフベース予測（graph-based prediction）を実行する方法を提供する。
【０００８】
また、本発明は、グラフラプラシアンの固有値（eigenvalues）の分布（distribution）に基づいたコスト（費用）関数と固有ベクトル（eigenvectors）との線形結合に基づいて最適化予測アルゴリズムを定義する方法を提供する。
【０００９】
また、本発明は、凸（コンベックス）最適化公式（convex optimization formulation）を用いて予測値を探す方法及びグラフ特性を用いる方法を提供する。
【発明の効果】
【００１０】
本発明が適用されるグラフベースの信号モデル化は、強力なツール（道具）になることができる。具体的には、本発明は、最適化関数を用いてグラフベース予測を実行する最適化予測アルゴリズムを提供することによって、低複雑度で予測値を獲得することができ、延いては、予測性能を向上させることができる。
【００１１】
また、本発明は、規則的な構造のグラフ信号だけでなく、任意のグラフ信号に対しても適用可能であるので、グラフ信号をエンコードするために必要なビットレートの過度なオーバーヘッドを避けることができる。
【００１２】
また、本発明は、ビデオシーケンスの他の部分で信号の統計的特性を適応的に用いることによって、圧縮効率を向上させることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明が適用される実施形態であって、ビデオ信号のエンコーディング（符号化）が実行されるエンコーダの概略ブロック図である。
【図２】本発明が適用される実施形態であって、ビデオ信号のデコーディング（復号）が実行されるデコーダの概略ブロック図である。
【図３】本発明が適用される一実施形態に従ってビデオフレーム内の８×８ブロック内での統計的関係をモデル化するために使われたグラフの例を示す図である。
【図４】本発明が適用される一実施形態であって、頂点に対する信号ベクトル及びエッジ重み付け値で定義された任意のグラフを示す図である。
【図５】本発明が適用される実施形態であって、グラフベースの信号を処理するエンコーダの概略ブロック図を例示する図である。
【図６】本発明が適用される実施形態であって、グラフベースの信号を処理するデコーダの概略ブロック図を例示する図である。
【図７】本発明が適用される一実施形態であって、グラフベース変換部の内部ブロック図である。
【図８】本発明が適用される一実施形態であって、グラフ信号に基づいて最適化された予測ベクトルを獲得する過程を説明するためのフローチャートである。
【図９】本発明が適用される一実施形態であって、グラフベース予測を用いてビデオ信号をデコードする過程を説明するためのフローチャートである。
【発明を実施するための形態】
【００１４】
本発明は、グラフ信号を用いてグラフベース予測（graph-based prediction）を実行する方法において、コンテキスト信号（context signal）を獲得するステップと、グラフパラメータセット（graph parameter set）に基づいてグラフ信号を生成するステップと、グラフ信号に基づいてグラフベース変換行列（graph-based transform matrix）を獲得するステップであって、グラフベース変換行列は固有ベクトル（eigenvector）を有するステップと、最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得するステップと、予測ベクトルを用いて予測信号を生成するステップと、を有し、最適化関数は、コンテキスト信号、グラフラプラシアン行列の固有値（eigenvalue）及び固有ベクトル（eigenvector）を変数として有することを特徴とする方法を提供する。
【００１５】
また、本発明において、予測ベクトルは、変換ベクトルと固有ベクトル（eigenvectors）との線形結合に基づいて獲得され、変換ベクトルは、グラフラプラシアン行列の固有値（eigenvalue）の分布に基づくコスト関数を用いて決定されることを特徴とする。
【００１６】
また、本発明は、グラフ信号に基づいてグラフラプラシアン行列（graph Laplacian matrix）を算出するステップをさらに有し、グラフベース変換行列（graph-based transform matrix）はグラフラプラシアン行列のスペクトル分解（spectral decomposition）を通じて獲得されることを特徴とする。
【００１７】
また、本発明において、最適化関数はラグランジュ乗数に基づく非制限最適化関数（unconstrained optimization function）で表現され、非制限最適化関数（unconstrained optimization function）は新たなＭ次元ベクトルにより表現されることを特徴とする。
【００１８】
また、本発明は、予測エラーをエンコードするステップと、エンコードされた予測エラーを転送するステップと、をさらに有することを特徴とする。
【００１９】
また、本発明は、グラフベース予測（graph-based prediction）に基づいてビデオ信号をデコードする方法において、グラフパラメータセット（graph parameter set）及び残差（レジデュアル）信号を有するビデオ信号を受信するステップと、グラフパラメータセットに基づいて固有ベクトルを有するグラフベース変換行列を獲得するステップと、最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得するステップと、予測ベクトルを用いて予測信号を生成するステップと、予測信号と残差信号とを合せてビデオ信号を復元するステップと、を有し、最適化関数はコンテキスト信号、グラフラプラシアン行列の固有値（eigenvalue）及び固有ベクトル（eigenvector）を変数として有することを特徴とする方法を提供する。
【００２０】
また、本発明は、グラフ信号を用いてグラフベース予測（graph-based prediction）を実行する装置において、グラフパラメータセット（graph parameter set）に基づいてグラフ信号を生成し、グラフ信号に基づいて固有ベクトル（eigenvector）を有するグラフベース変換行列（graph-based transform matrix）を獲得するグラフベース変換部と、コンテキスト信号（context signal）を獲得し、最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得し、予測ベクトルを用いて予測信号を生成する予測部を有し、最適化関数はコンテキスト信号、グラフラプラシアン行列の固有値（eigenvalue）及び固有ベクトル（eigenvector）を変数として有することを特徴とする装置を提供する。
【００２１】
また、本発明において、グラフベース変換部は、グラフ信号に基づいてグラフラプラシアン行列（graph Laplacian matrix）を算出し、グラフベース変換行列（graph-based transform matrix）はグラフラプラシアン行列のスペクトル分解（spectral decomposition）を通じて獲得されることを特徴とする。
【００２２】
また、本発明は、予測エラーをエンコードし、エンコードされた予測エラーを転送するエントロピエンコーディング部をさらに有することを特徴とする。
【００２３】
また、本発明は、グラフベース予測（graph-based prediction）に基づいてビデオ信号をデコードする装置において、グラフパラメータセット（graph parameter set）及び残差信号を有するビデオ信号を受信するエントロピデコーディング部と、グラフパラメータセットに基づいて固有ベクトルを有するグラフベース変換行列を獲得する逆変換部と、最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得し、予測ベクトルを用いて予測信号を生成する予測部と、予測信号と残差信号とを合せてビデオ信号を復元する復元部と、を有し、最適化関数はコンテキスト信号、グラフラプラシアン行列の固有値（eigenvalue）及び固有ベクトル（eigenvector）を変数として有することを特徴とする装置を提供する。
〔発明の実施のための形態〕
【００２４】
以下、添付した図面を参照して本発明の実施形態の構成とその作用を説明し、図面により説明される本発明の構成及び作用は、１つの実施形態として説明されるものであり、これによって本発明の技術的思想及びその核心の構成及び作用が制限されるものではない。
【００２５】
併せて、本発明で使われる用語はできる限り、現在広く使われる一般的な用語を選択したが、特定の場合は出願人が任意に選定した用語を使用して説明する。そのような場合には該当部分の詳細説明でその意味を明確に記載するので、本発明の説明で使われた用語の名称だけで単純に解析されてはならず、その該当用語の意味まで把握して解析されなければならないことを明らかにする。
【００２６】
また、本明細書で提示された実施形態は、ビデオ信号処理に関するものであるが、本発明は、ビデオ信号処理のみに基づいたものとして推論されてはならず、一般的なグラフベースの信号処理方法にも適用できるものである。
【００２７】
また、本発明で使われる用語は発明を説明するために選択された一般的な用語や、類似の意味を有する他の用語がある場合、より適切な解析のために置き換え可能である。例えば、信号、データ、サンプル、ピクチャ、フレーム、ブロックなどの場合、各コーディング過程で適切に置き換えられて解析できる。
【００２８】
実際に、ビデオのように非常に複雑で、かつ多様な信号の正確な統計的モデルはない。したがって、本明細書では統計モデルを形成する確率分布ｆ（ｘ｜ｙ）又はｆ（ｘ、ｙ）は既に知っているという仮定に基づく。
【００２９】
ビデオ信号の統計的特性は、ビデオタイプによって、又は各フレーム内で格段に変わる。それで、より単純な統計的モデルや自動学習（automatic learning）を用いるときすら、本発明は、継続的に変わるモデルパラメータを信頼性があるように測定するという困難性がある。また、モデルがあまり（非常に）簡単であるか、又はそのパラメータが信号の実際の特性を反映できなければ、予測が正確でないことがある。事実、予測精度（正確度）はモデルの複雑度が増加するほどより低くなる。
【００３０】
したがって、本発明は、予測性能を向上させるためのより強力なアプローチ（接近）を必要とする。
【００３１】
圧縮に適用される予測と関連した更に他の重要な問題は、伝統的な統計的アプローチ（接近）と異なるように、エンコーダがエンコーディングを必要とする全てのデータにアプローチできるということである。エンコーダはデコーダの予測を向上させることができる付加情報を転送できるため、これは非常に重要な差を作ることができる。例えば、エンコーダは用いられるモデルタイプ及びそのパラメータに関する付加情報をエンコードすることができる。
【００３２】
現在ビデオコーディング方法に用いられる予測方法は、付加情報（side information）のエンコーディングに大部分依存しており、統計的モデル、例えば、ピクセル複写（pixel copying）、単純補間（simple interpolation）などに対するほんの少しの仮定のみを用いているということである。その上、エッジのようなビデオ特徴を表現するために、伝統的な統計的分布を用いる代わりに、幾何学的モデルが用いられている。
【００３３】
例えば、ビデオコーディング標準は、均等なピクセル分布モデル又は３３個の方向セットに従う一定のピクセル値の間で選択する、イントラフレーム（フレーム内）予測に対して専ら単純補間を用いる。そして、インターフレーム（フレーム間）予測はフレーム間の動きモデルを仮定し、小数ピクセル動きに対して補間を用いる。
【００３４】
このようなアプローチの主な問題は、幾何学的モデルが非常に制限的で、現在のビデオコーディング標準が直線エッジ又は動きの変化などの特徴を十分に活用しているという点である。
【００３５】
一方、グラフ信号処理は、信号処理に用いられてきた最も基本的な技術を一般化する新たなアプローチ方式である。グラフ信号処理は、イメージの特徴の強力な統合を予測過程で可能にする、幾何学的特徴に基づいた経験的技術を一般化する。統計的分析と結合できるが、完全な統計的モデルを導出（誘導）する必要はない。
【００３６】
適切なグラフエッジ重み付け値を選択する方法は、全ての形態のグラフ信号処理の核心的な部分であることが明確である。しかしながら、本明細書では本発明と直接関連していないので、詳細に議論しない。以下、前述した統計的モデル、幾何学的モデル、及びグラフモデルが有する問題点を解決する、最適化予測方法を説明する。
【００３７】
図１は、本発明が適用される実施形態であって、ビデオ信号のエンコーディングが実行されるエンコーダの概略ブロック図を示す。
【００３８】
図１を参照すると、エンコーダ１００は、映像分割部１１０、変換部１２０、量子化部１３０、逆量子化部１４０、逆変換部１５０、フィルタリング部１６０、復号ピクチャバッファ（ＤＰＢ：Decoded Picture Buffer）１７０、インター予測部１８０、イントラ予測部１８５、及びエントロピエンコーディング部１９０を含んで構成できる。
【００３９】
映像分割部１１０は、エンコーダ１００に入力された入力映像（イメージ）（Input image）（又は、ピクチャ、フレーム）を１つ又は複数の処理ユニットに分割することができる。例えば、上記処理ユニットは、コーディングツリーユニット（ＣＴＵ：Coding Tree Unit）、コーディングユニット（ＣＵ：Coding Unit）、予測ユニット（ＰＵ：Prediction Unit）、又は変換ユニット（ＴＵ：Transform Unit）でありうる。
【００４０】
但し、上記用語は本発明に関する説明の便宜のために使用するだけであり、本発明は該当用語の定義に限定されるものではない。また、本明細書では説明の便宜のために、ビデオ信号をエンコード（符号化）又はデコード（復号）する過程で用いられる単位としてコーディングユニットという用語を使用するが、本発明はそれに限定されず、発明内容によって適切に解析可能である。
【００４１】
エンコーダ１００は、入力映像信号から、インター予測部１８０又はイントラ予測部１８５から出力された予測信号（prediction signal）を減算して残差（残余）信号（residual signal）を生成することができ、生成された残差信号は変換部１２０に転送される。
【００４２】
変換部１２０は、残差信号に変換技法を適用して変換係数（transform coefficient）を生成することができる。変換過程は正四角形の同一のサイズを有するピクセルブロックに適用されることもでき、正四角形でない可変サイズのブロックにも適用できる。
【００４３】
本発明の一実施形態において、上記変換部１２０はグラフパラメータを用いてグラフ信号を獲得することができる。
【００４４】
本発明の他の一実施形態において、上記変換部１２０は頂点パラメータセット及びエッジパラメータセットのうち、少なくとも１つを用いてグラフ信号を獲得することができる。
【００４５】
本発明の他の一実施形態において、上記変換部１２０は最適化関数に基づいて最適化されたグラフベース変換カーネルを獲得することができる。この際、上記最適化関数はラグランジュ乗数を用いて非制限最適化関数（unconstrained optimization function）で表現されることができ、上記非制限最適化関数（unconstrained optimization function）は新たなＭ次元ベクトルにより表現できる。
【００４６】
本発明の他の一実施形態において、上記変換部１２０は、上記最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得することができ、上記予測ベクトルは予測信号を生成するために利用できる。この際、上記予測ベクトルは、上記グラフラプラシアン行列の固有ベクトル（eigenvector）と上記固有値（eigenvalue）の分布に基づくコスト関数との間の線形結合に基づいて獲得できる。
【００４７】
量子化部１３０は、変換係数を量子化してエントロピエンコーディング部１９０に転送し、エントロピエンコーディング部１９０は、量子化された信号（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 Buffer Unit）２５０、インター予測部２６０、及びイントラ予測部２６５を含んで構成できる。
【００５９】
そして、デコーダ２００を通じて出力された復元映像信号（reconstructed video signal）は再生装置を通じて再生できる。
【００６０】
デコーダ２００は、図１のエンコーダ１００から出力された信号を受信することができ、受信した信号はエントロピデコーディング部２１０を通じてエントロピデコードできる。この際、上記出力された信号はグラフパラメータセット（graph parameter set）及び予測ベクトル情報を含むことができる。上記予測ベクトル情報は、上記グラフラプラシアン行列の固有ベクトル（eigenvector）と上記固有値（eigenvalue）の分布に基づくコスト関数との間の線形結合に基づいて決定されたものでありうる。
【００６１】
他の例において、上記予測ベクトル情報は、グラフラプラシアン行列の固有値（eigenvalue）と固有ベクトル（eigenvector）を変数として有する最適化関数とに基づいて決定されたものでありうる。この場合、上記最適化関数は、ラグランジュ乗数を用いて非制限最適化関数（unconstrained optimization function）で表現されることができ、上記非制限最適化関数（unconstrained optimization function）は新たなＭ次元ベクトルにより表現できる。
【００６２】
上記デコーダ２００は、上記予測ベクトル情報に基づいて予測信号を生成することができる。これはインター予測部２６０で実行できるが、本発明はこれに限定されるものではない。
【００６３】
逆量子化部２２０では、量子化ステップサイズ情報を用いてエントロピデコードされた信号から変換係数（transform coefficient）を獲得する。ここで、獲得された変換係数は、上記図１の変換部１２０で説明した多様な実施形態が適用されたものでありうる。
【００６４】
逆変換部２３０では、変換係数を逆変換して残差信号（residual signal）を獲得する。
【００６５】
獲得された残差信号をインター予測部２６０又はイントラ予測部２６５から出力された予測信号（prediction signal）に加えることによって、復元信号（reconstructed signal）が生成される。
【００６６】
フィルタリング部２４０は、復元信号（reconstructed signal）にフィルタリングを適用して、これを再生装置に出力するか、又は復号ピクチャバッファ部２５０に転送する。復号ピクチャバッファ部２５０に転送されたフィルタリングされた信号は、インター予測部２６０で参照ピクチャとして使用できる。
【００６７】
本明細書で、エンコーダ１００のフィルタリング部１６０、インター予測部１８０、及びイントラ予測部１８５で説明された実施形態は、各々、デコーダのフィルタリング部２４０、インター予測部２６０、及びイントラ予測部２６５にも、同一に適用できる。
【００６８】
図３は、本発明が適用される一実施形態に従ってビデオフレーム内の８×８ブロック内での統計的関係をモデル化するために使われたグラフの例を示す。
【００６９】
上記図３は、イメージピクセルの正四角形ブロックで定義されたグラフの例を示す。
【００７０】
図３を参照すると、本発明は、イメージ又はビデオ内の８×８ピクセルブロックの処理のために使用できるグラフタイプの２つの実施形態を提供する。各ピクセルはグラフの頂点に関連し（関連付けられ）、上記ピクセルの値はグラフ頂点の値となる。
【００７１】
グラフエッジは、グラフ頂点を連結する線を意味することができる。上記グラフエッジは、信号内の如何なる形態の統計的依存性をも示すために使われて、この際、正の重み付け値はその強度を示すことができる。例えば、各頂点は全ての他の頂点に連結されることができ、０の重み付け値は互いに関連しないか、又は弱く関連した頂点を連結するエッジに割り当てできる。但し、表現の簡単化のために、０の重み付け値を有するエッジは完全に除去できる。
【００７２】
本発明の他の実施形態において、グラフ頂点を連結するエッジは信号特性によって予め設定できる。例えば、頂点はオーディオ信号に対しては１次元配列上に、イメージに対しては２次元配列上に、またビデオフレームに対しては３次元配列上に配置できる。この際、上記３次元配列の場合には時間軸が３番目の次元になることができる。例えば、図３（ａ）のグラフで、グラフエッジは各々の頂点がそれから最も近い４個の隣接頂点に連結されるように定義できる。但し、ブロック境界の場合は異なるように取扱できる。また、図３（ｂ）のグラフでは各々の頂点がそれから最も近い８個の隣接頂点に連結されるように定義できる。
【００７３】
一方、本発明は如何なるグラフ設定にも適用可能でありうる。
【００７４】
グラフ信号Ｇのラプラシアン行列は、次の＜数式１＞の通りである。
【００７５】
＜数式１＞
【数１】
0006356912.tif 000002
ここで、Ｄは次数行列（Degree matrix）を示し、例えば上記次数行列は各頂点の次数に関する情報を含む対角行列（diagonal matrix）を意味することができる。Ａは、隣接ピクセルとの連結関係（edge）を重み付け値で示す隣接行列（adjacency matrix）を示す。
【００７６】
グラフＧ及びその行列が定義される方法は、本明細書では詳細に説明しない。本明細書では、単にグラフがグラフタイプに対して定義された信号の特性を用いる幾つかの技術により定義できると仮定するだけである。したがって、本発明は、行列Ｄ、Ａを用いて信号のモデル化を実行してグラフを生成すれば、固有分解（eigen-decomposition）過程を通じて次の＜数式２＞のように変換カーネルＵを生成することができる。
【００７７】
＜数式２＞
【数２】
0006356912.tif 000003
【００７８】
【化１】
0006356912.tif 000004
【００７９】
グラフベース変換行列Ｕの行（columns）は、グラフラプラシアン行列（graph Laplacian matrix）Ｌの固有ベクトル（eigenvectors）を含み、対角行列（diagonal matrix）は対応するグラフラプラシアン行列（graph Laplacian matrix）Ｌの固有値（eigenvalues）に対し、次の＜数式３＞のように表現できる。
【００８０】
＜数式３＞
【数３】
0006356912.tif 000005
【００８１】
一般に、固有ベクトル（eigenvectors）は特有の形態で定義されないが、本発明の目的によって、グラフラプラシアン行列（graph Laplacian matrix）Ｌが対称的であるので、全ての固有ベクトル（eigenvectors）は実数値であり、少なくとも１つの分解（decomposition）は存在することができる。グラフ信号Ｇで信号ベクトルｇのグラフベースフーリエ変換は、次の＜数式４＞のように定義できる。
【００８２】
＜数式４＞
【数４】
0006356912.tif 000006
ここで、ｈは変換ベクトルを示し、ＵTはグラフベース変換行列Ｕの転置行列を示し、ｇはグラフ信号Ｇのベクトルを示す。
【００８３】
前述したグラフ信号に対する基本的な定義に基づいて、以下に本発明の実施形態を具体的に説明する。
【００８４】
図４は、本発明が適用される一実施形態であって、頂点に対する信号ベクトル及びエッジ重み付け値で定義された任意のグラフを示す。
【００８５】
本発明の一実施形態では、信号が任意のグラフＧで定義される方法を提供する。例えば、グラフ信号は各グラフ頂点で定義され、Ｇ次元ベクトルｇにより表現できる。グラフ特性は各グラフエッジ上の負でない重み付け値により定義できる。
【００８６】
上記図４の場合、その頂点に定義された信号ベクトルと負でないエッジ重み付け値とにより定義されたグラフ特性を有する任意のグラフを示す。ここで、頂点の値は２つのセットに分割されることができ、ここで、上記２つのセットは予測される信号ｘ及びコンテキスト信号（context signal）ｙを意味することができる。上記図４で、ｘ１，ｘ２，．．．，ｘ６は予測される信号を示し、ｙ１，ｙ２，．．．，ｙ５はコンテキスト信号（context signal）を示す。例えば、以下の図５のように、上記予測される信号ｘは原信号を意味することができ、コンテキスト信号（context signal）ｙはループによって復元された信号を意味することができる。
【００８７】
上記図４で説明したように、本発明がコンテキスト信号ｙから信号ｘを予測しようとすると仮定すれば、グラフモデルでｘ及びｙは信号ｇを形成することができる。
【００８８】
ベクトル表記法によって、本発明は、グラフ信号ｇを＜数式５＞のように分解することができる。
【００８９】
＜数式５＞
【数５】
0006356912.tif 000007
【００９０】
ここで、ｇはグラフ信号を示し、ｘは予測される信号を示し、ｙはコンテキスト信号を示す。
【００９１】
一方、グラフベース変換行列Ｔは、次の＜数式６＞のように示すことができる。
【００９２】
＜数式６＞
【数６】
0006356912.tif 000008
【００９３】
ここで、Ｔはグラフベース変換行列を示し、Ａ及びＭは各々行列を示す。
【００９４】
そして、上記＜数式４＞は上記＜数式５＞及び＜数式６＞に基づいて次の＜数式７＞のように書き換えることができる。
【００９５】
＜数式７＞
【数７】
0006356912.tif 000009
【００９６】
ここで、ｈはＧ（＝Ｍ＋Ｎ）次元を有する。
【００９７】
一方、ＴT＝Ｔ-1であるので、上記＜数式７＞は、次の＜数式８＞のように書かれることができる。
【００９８】
＜数式８＞
【数８】
0006356912.tif 000010
【００９９】
この際、次の＜数式９＞の条件を満たす。
【０１００】
＜数式９＞
【数９】
0006356912.tif 000011
【０１０１】
ここで、Ｉ及び０は、各行列積（算出物）（matrix products）に対応する次元の単位（自己）行列（identity matrix）及びゼロ行列（0 matrix）を示す。
【０１０２】
このような定義に基づいて、以下、本発明の実施形態をより詳細に説明する。
【０１０３】
図５は、本発明が適用される実施形態であって、グラフベースの信号を処理するエンコーダの概略ブロック図を例示する。
【０１０４】
上記図５を説明すると、本発明が適用されるエンコーダ５００は、グラフベース（基盤）変換部５１０、量子化部５２０、逆量子化部５３０、逆変換部５４０、バッファ５５０、予測部５６０、及びエントロピエンコーディング部５７０を含む。
【０１０５】
エンコーダ５００は、ビデオ信号を受信し、上記ビデオ信号から上記予測部５６０で出力された予測された信号を差し引きして予測エラーを生成する。上記生成された予測エラーは上記グラフベース変換部５１０に転送され、上記グラフベース変換部５１０は変換方式を上記予測エラーに適用することによって変換係数を生成する。この際、上記グラフベース変換部５１０はグラフベース変換行列を算出することができ、これを用いて変換を実行することができる。また、上記グラフベース変換部５１０は本明細書に記載された実施形態を実行することができる。
【０１０６】
本発明が適用される他の実施形態において、上記グラフベース変換部５１０は、最適化関数に基づいて最適化されたグラフベース変換カーネルを獲得することができる。この際、上記最適化関数はラグランジュ乗数を用いて非制限最適化関数（unconstrained optimization function）で表現されることができ、上記非制限最適化関数（unconstrained optimization function）は新たなＭ次元ベクトルにより表現できる。
【０１０７】
また、上記グラフベース変換部５１０は、上記最適化関数を通じて算出された最適な変換ベクトルを用いて予測ベクトルを獲得することができ、上記予測ベクトルは予測信号を生成するために利用できる。この際、上記予測ベクトルは、上記グラフラプラシアン行列の固有ベクトル（eigenvector）と上記固有値（eigenvalue）の分布に基づくコスト関数との間の線形結合に基づいて獲得できる。
【０１０８】
上記獲得された予測ベクトルは逆変換部５４０に転送されて逆変換されることができ、逆変換された予測ベクトルは予測部５６０に転送されて予測信号を生成するために利用できる。又は、上記予測ベクトルはエントロピエンコーディング部５７０に転送されてエンコードされることもできる。
【０１０９】
上記グラフベース変換部５１０の実施形態は図１の変換部１２０に含まれて実行されることができ、又は別個の機能ブロックで実行されることもできる。そして、本発明が適用される予測方法も上記グラフベース変換部５１０で実行されると説明しているが、本発明はこれに限定されるものではない。例えば、本発明が適用される予測方法は別個の機能ブロックで実行されるか、又はインター予測部１８０／予測部５６０で実行できる。
【０１１０】
本発明が適用される予測方法の実施形態は、以下でより詳細に説明する。
【０１１１】
グラフベース予測（Graph-based prediction）
グラフのフーリエ変換を定義するために、本発明では、Ｇ（Ｗ）に対応する次数行列（degree matrix）で表現できる。ここで、次数行列（degree matrix）は、各頂点の次数に関する情報を含む対角行列（diagonal matrix）で、以下の＜数式１０＞のように定義できる。例えば、上記次数は一頂点に繋がっている辺の数を意味することができる。
【０１１２】
＜数式１０＞
【数１０】
0006356912.tif 000012
【０１１３】
グラフラプラシアン行列Ｌ＝Ｄ−Ｗであり、したがって、グラフラプラシアン行列Ｌi,jは次の＜数式１１＞の通りである。
【０１１４】
＜数式１１＞
【数１１】
0006356912.tif 000013
【０１１５】
この際、行列Ｔをグラフフーリエ変換として定義すれば、行列Ｔは次の＜数式１２＞の通りである。
【０１１６】
＜数式１２＞
【数１２】
0006356912.tif 000014
【０１１７】
ここで、ＵはＬを対角化する固有行列を示し、Ｌは次の＜数式１３＞の通りである。
【０１１８】
＜数式１３＞
【数１３】
0006356912.tif 000015
【０１１９】
そして、直交行列は次の＜数式１４＞を満たす。
【０１２０】
＜数式１４＞
【数１４】
0006356912.tif 000016
【０１２１】
このような定義に基づいて、固有行列（eigen matrix）Ｕの行（columns）はＬの固有ベクトル（eigenvectors）を含み、Ｌの固有値（eigenvalues）は次の＜数式１５＞のように表現できる。
【０１２２】
＜数式１５＞
【数１５】
0006356912.tif 000017
【０１２３】
一般に、固有ベクトル（eigenvectors）は特有の形態で定義されないが、本発明の目的によって、Ｌが対称的であるので、全ての固有ベクトル（eigenvectors）は実数値であり、少なくとも１つの分解（decomposition）が存在することを考慮しなければならない。これは、＜数式１４＞を満たすいかなる行列にも適用可能である。
【０１２４】
ランダム信号の予測は古典的な統計的問題である。一般的な方式において、本発明では、ベクトル関数を＜数式１６＞のように定義することができる。
【０１２５】
＜数式１６＞
【数１６】
0006356912.tif 000018
【０１２６】
ここで、ｐ（ｙ）はＮ次元ベクトルｙが与えられたとき、Ｍ次元ランダムベクトル（random vector）の予測値（predicted value）を示す。
【０１２７】
条件的確率分布ｆ（ｘ｜ｙ）を知っていると仮定すれば、本発明は、＜数式１７＞のような最適化関数を通じて最適な予測関数ｐ*（ｙ）を探すことができる。
【０１２８】
＜数式１７＞
【数１７】
0006356912.tif 000019
【０１２９】
ここで、ｐ*（ｙ）は最適な予測関数を示し、ｘは原信号を示し、ｐ（ｙ）はＮ次元ベクトルｙが与えられたとき、Ｍ次元ランダムベクトル（random vector）の予測値（predicted value）を示す。そして、Ｅｘ｜ｙ{・｝は条件付き期待演算子（conditional expectation operator）を示す。
【０１３０】
そして、＜数式１８＞は予測エラーを測定する関数（function measuring prediction error）を示す。
【０１３１】
＜数式１８＞
【数１８】
0006356912.tif 000020
【０１３２】
例えば、Ｄがユークリッド距離（Euclidean distance）を測定するとき、本発明は、＜数式１９＞のような最小二乗誤差（エラー）問題（minimum squared error problem）を有する。
【０１３３】
＜数式１９＞
【数１９】
0006356912.tif 000021
【０１３４】
ここで、ｐ*（ｙ）は最適な予測関数を示し、ｘは原信号を示し、ｐ（ｙ）はＮ次元ベクトルｙが与えられたとき、Ｍ次元ランダムベクトル（random vector）の予測値（predicted value）を示す。
【０１３５】
この場合、最適予測値（optimal predictor）は次の＜数式２０＞の通りでありうる。
【０１３６】
＜数式２０＞
【数２０】
0006356912.tif 000022
【０１３７】
線形予測のような特別な場合が適用される場合、本発明は＜数式２１＞のように表現することができる。
【０１３８】
＜数式２１＞
【数２１】
0006356912.tif 000023
【０１３９】
ここで、ＰはＭｘＮ行列を示し、ｙはＮ次元ベクトルを示す。
【０１４０】
二乗誤差測定（squared-error measure）に対する最適な線形予測行列（optimal linear predictor matrix）は、次の＜数式２２＞のように計算できる。
【０１４１】
＜数式２２＞
【数２２】
0006356912.tif 000024
【０１４２】
また、本発明が適用される予測アルゴリズム（prediction algorithm）を説明するために、目的関数（objective function）の定義をさらに仮定する必要がある。
【０１４３】
＜数式２３＞
【数２３】
0006356912.tif 000025
【０１４４】
【化２】
0006356912.tif 000026
【０１４５】
本発明は、確率モデルの実際理論を仮定することではなく、より大きい固有値に対応する高周波数成分が典型的に、より小さなサイズ（lower magnitude）を有するという経験的観察に基づく。
【０１４６】
このような定義によって、本発明は、グラフベース予測を分解する方法（how to decompose the graph-based prediction）を提供する。即ち、ｘからｙを予測するためにグラフ信号Ｇの情報を用いることができる。これは、次のような過程に従う。
【０１４７】
第１に、グラフ信号Ｇのエッジ重み付け値を決定し、グラフラプラシアン行列Ｌを計算することができる。
【０１４８】
第２に、変換行列Ｔ及び固有値（eigenvalue）λを有するベクトルを決定するためにグラフラプラシアン行列Ｌのスペクトル分解（spectral decomposition）を実行することができる。
【０１４９】
第３に、上記スペクトル分解の結果に基づいて、次の＜数式２４＞のように最適な変換ベクトルｈ*（ｙ）を算出することができる。
【０１５０】
＜数式２４＞
【数２４】
0006356912.tif 000027
【０１５１】
第４に、上記＜数式２４＞を用いる次の＜数式２５＞に基づいて予測ベクトルｐ（ｙ）を算出することができる。
【０１５２】
＜数式２５＞
【数２５】
0006356912.tif 000028
【０１５３】
本発明の他の実施形態において、グラフ重み付け値セットを予め定義することも可能である。それで、全ての予測ベクトルに対し、ラプラシアン計算及び変換行列計算と関連した上記の第１ステップ及び第２ステップを反復しないことがある。
【０１５４】
グラフベース変換の最適化（Graph-based transform optimization）
本発明のグラフベース予測アルゴリズムで、次の＜数式２６＞の最適化問題に対するより効率の良い解法を探すために、幾つかの特別な特徴を活用することができる。
【０１５５】
＜数式２６＞
【数２６】
0006356912.tif 000029
【０１５６】
【化３】
0006356912.tif 000030
【０１５７】
＜数式２７＞
【数２７】
0006356912.tif 000031
【０１５８】
しかしながら、行列Ａ及びＭが直交部分空間（orthogonal subspaces）を発生させるため、本発明は、Ｍ次元ベクトルｚを定義し、次の＜数式２８＞を用いて＜数式２９＞を獲得することができる。
【０１５９】
＜数式２８＞
【数２８】
0006356912.tif 000032
【０１６０】
＜数式２９＞
【数２９】
0006356912.tif 000033
【０１６１】
そして、次の＜数式３０＞の非制限最適化問題（unconstrained optimization problem）を解決して＜数式３１＞を獲得することができる。
【０１６２】
＜数式３０＞
【数３０】
0006356912.tif 000034
【０１６３】
＜数式３１＞
【数３１】
0006356912.tif 000035
【０１６４】
上記のようなグラフベース変換最適化過程を通じて最適化された変換ベクトルを獲得できるようになる。
【０１６５】
２次目的関数の定義（Definition of Quadratic objective function）
本発明は、次の＜数式３２＞のような目的関数を２次関数として定義することができる。
【０１６６】
＜数式３２＞
【数３２】
0006356912.tif 000036
【０１６７】
ここで、Ｗはλに基づくセミ−ポジティブ（semi-positive）の行列（半正定値行列）である。例えば、Ｗは次の＜数式３３＞のように簡単に定義することができる。
【０１６８】
＜数式３３＞
【数３３】
0006356912.tif 000037
【０１６９】
表示の単純化のために、本発明は、暗示的にλに基づく行列Ｗの依存性を考慮し、次の＜数式３４＞の解を分析することができる。
【０１７０】
＜数式３４＞
【数３４】
0006356912.tif 000038
【０１７１】
最適な解を探すために、ラグランジュ乗数を用いることができる。２次目的関数の場合に、上記＜数式２７＞に定義された数式は全て線形であり、本発明は次の＜数式３５＞のような行列形態を有することができる。
【０１７２】
＜数式３５＞
【数３５】
0006356912.tif 000039
【０１７３】
仮に、Ｗが単数（singular）でなければ、次の＜数式３６＞及び＜数式３７＞のように表現できる。
【０１７４】
＜数式３６＞
【数３６】
0006356912.tif 000040
【０１７５】
＜数式３７＞
【数３７】
0006356912.tif 000041
【０１７６】
これをｈに対して解けば、本発明は次の＜数式３８＞を獲得することができ、予測値は＜数式３９＞の通りである。
【０１７７】
＜数式３８＞
【数３８】
0006356912.tif 000042
【０１７８】
＜数式３９＞
【数３９】
0006356912.tif 000043
【０１７９】
本発明の他の実施形態において、Ｗが単数（singular）のときの場合を次の通り説明することができる。２次目的関数に対する＜数式３０＞の対応するバージョンは次の＜数式４０＞の通りである。
【０１８０】
＜数式４０＞
【数４０】
0006356912.tif 000044
【０１８１】
最適な解は次の＜数式４１＞及び＜数式４２＞により定義されることができ、結果的に、＜数式４３＞を獲得することができる。
【０１８２】
＜数式４１＞
【数４１】
0006356912.tif 000045
【０１８３】
＜数式４２＞
【数４２】
0006356912.tif 000046
【０１８４】
＜数式４３＞
【数４３】
0006356912.tif 000047
【０１８５】
本発明が適用される他の実施形態において、最適な変換ベクトルを選択するための目的関数を選択する他の方法を提供する。例えば、２次関数は次の＜数式４４＞のような凸関数（convex function）の特別な場合でありうる。
【０１８６】
＜数式４４＞
【数４４】
0006356912.tif 000048
【０１８７】
【化４】
0006356912.tif 000049
【０１８８】
一方、上記量子化部５２０は、上記のような過程を通じて生成された変換係数を量子化して上記量子化された係数をエントロピエンコーディング部５７０に転送する。
【０１８９】
上記エントロピエンコーディング部５７０は、上記量子化された信号に対するエントロピコーディングを実行し、エントロピコーディングされた信号を出力する。
【０１９０】
上記量子化部５２０により出力された上記量子化された信号は、予測信号を生成するために使用できる。例えば、上記エンコーダ５００のループ内の上記逆量子化部５３０及び上記逆変換部５４０は、上記量子化された信号が予測エラーに復元されるように上記量子化された信号に対する逆量子化及び逆変換を実行することができる。復元された信号は上記復元された予測エラーを上記予測部５６０により出力された予測信号に加えることによって生成できる。
【０１９１】
上記バッファ５５０は、予測部５６０の今後の参照のために復元された信号を記憶する。
【０１９２】
上記予測部５６０は、以前に復元されて上記バッファ５５０に記憶された信号を使用して予測信号を生成することができる。このような場合、本発明は、アンカ（anchor）イメージ内の領域を使用して目標イメージ内の領域を効率良く予測することに関連したものである。ここで、上記アンカイメージは、参照イメージ、参照ピクチャ、又は参照フレームを意味することができる。効率はレート歪（率−歪曲）（Rate-Distortion）コスト又は予測エラー内の歪曲を定量化する平均二乗誤差を算出することによって決定できる。
【０１９３】
本発明は、グラフ内の頂点及びエッジを識別し、残差値信号をエンコード又はデコードする方法を提案する。例えば、本発明の実施形態はグラフベース変換部５１０を通じて多様な実施形態を実行することができる。上記グラフベース変換部５１０は、上記エンコーダ５００又は上記デコーダ７００に含まれることができる。
【０１９４】
図６は、本発明が適用される実施形態であって、グラフベースの信号を処理するデコーダの概略ブロック図を例示する。
【０１９５】
図６のデコーダ６００は、図５のエンコーダ５００により出力された信号を受信する。この際、上記出力された信号はグラフパラメータセット（graph parameter set）及び残差信号を含むことができる。上記グラフパラメータセットに基づいてグラフベース変換行列を獲得することができ、上記グラフベース変換行列は固有ベクトルを含むことができる。そして、予測ベクトルは最適な変換ベクトルを用いて獲得されることができ、上記最適な変換ベクトルは最適化関数を通じて算出できる。この際、上記予測ベクトルは変換ベクトルと固有ベクトル（eigenvectors）との線形結合に基づいて獲得されることができ、上記変換ベクトルはグラフラプラシアン行列の固有値（eigenvalue）の分布に基づくコスト関数を用いて決定できる。
【０１９６】
一方、上記最適化関数は、ラグランジュ乗数を用いて非制限最適化関数（unconstrained optimization function）で表現されることができ、上記非制限最適化関数（unconstrained optimization function）は新たなＭ次元ベクトルにより表現できる。
【０１９７】
上記デコーダ６００は、上記予測ベクトル情報に基づいて予測信号を生成することができる。これは、予測部６５０で実行できるが、本発明はこれに限定されるものではない。
【０１９８】
上記エントロピデコーディング部６１０は、受信された信号に対するエントロピデコーディングを実行する。上記逆量子化部６２０は、量子化ステップサイズに関する情報に基づいて上記エントロピデコードされた信号から変換係数を獲得する。
【０１９９】
上記逆変換部６３０は、変換係数に対する逆変換を実行することによって、予測エラーを取得する。この際、上記逆変換は上記エンコーダ５００で獲得されたグラフベース変換に対する逆変換を意味することができる。
【０２００】
復元された信号は、上記獲得された予測エラーを上記予測部６５０により出力された予測信号に加えることによって生成され、これは復元部（図示せず）で実行される。
【０２０１】
上記バッファ６４０は、上記予測部６５０の今後の参照のために上記復元された信号を記憶する。
【０２０２】
上記予測部６５０は、以前に復元されて上記バッファ６４０に記憶された信号と本発明が適用される予測ベクトルとに基づいて予測信号を生成する。
【０２０３】
本発明において、グラフパラメータに基づいて獲得されたグラフベース変換は、上記エンコーダ５００又は上記デコーダ６００で使用できる。
【０２０４】
図７は、本発明が適用される一実施形態であって、グラフベース変換部の内部ブロック図を示す。
【０２０５】
図７を参照すると、グラフベース（基盤）変換部５１０は、グラフパラメータ抽出部５１１、グラフ信号生成部５１２、グラフベース（基盤）変換算出部５１３、変換実行（遂行）部５１４、変換最適化部５１５、及びグラフベース（基盤）予測部５１６を含むことができる。但し、本発明はこれに限定されず、上記グラフベース変換部５１０内の各機能ユニットは別個の機能ユニットとして動作することができ、又は他の機能ユニットに含まれて動作することもできる。
【０２０６】
グラフパラメータ抽出部５１１は、残差信号のターゲットユニットに対応するグラフ内のグラフパラメータを抽出することができる。例えば、上記グラフパラメータは、頂点パラメータ及びエッジパラメータのうち、少なくとも１つを含むことができる。上記頂点パラメータは、頂点の位置及び頂点の個数のうちの少なくとも１つを含み、上記エッジパラメータは、エッジ重み付け値及びエッジ重み付け値の個数のうち、少なくとも１つを含むことができる。また、上記グラフパラメータは一定個数のセット（set）で定義できる。
【０２０７】
グラフ信号生成部５１２は、上記グラフパラメータ抽出部５１１から抽出されたグラフパラメータに基づいてグラフ信号を生成することができる。この際、上記グラフ信号からグラフラプラシアン行列を算出することができる。
【０２０８】
グラフベース変換算出部５１３は、上記グラフパラメータ又はグラフパラメータセットに基づいてグラフベース変換行列（graph-based transform matrix）を獲得することができる。この際、上記グラフベース変換行列は固有ベクトル（eigenvector）を含むことができる。
【０２０９】
また、グラフベース変換算出部５１３は、上記グラフパラメータ又はグラフパラメータセットに基づいてグラフラプラシアン行列を算出することができる。この場合、上記グラフベース変換行列は、上記グラフラプラシアン行列のスペクトル分解（spectral decomposition）を通じて獲得できる。
【０２１０】
変換実行部５１４は、グラフベース変換行列を用いて変換を実行することができる。
【０２１１】
変換最適化部５１５は、最適化関数を通じて最適な変換ベクトルを算出することができる。ここで、上記最適化関数はラグランジュ乗数を用いて非制限最適化関数（unconstrained optimization function）で表現できる。そして、上記非制限最適化関数（unconstrained optimization function）は新たなＭ次元ベクトルにより表現できる。例えば、上記最適化関数に上記＜数式２４＞又は上記＜数式３４＞が用いられることができ、上記最適な変換ベクトルは、上記＜数式１８＞、上記＜数式２５＞、又は上記＜数式３６＞を用いて獲得できる。
【０２１２】
グラフベース予測部５１６は、上記算出された最適な変換ベクトルを用いて予測ベクトルを獲得することができる。上記予測ベクトルは、変換ベクトルと固有ベクトル（eigenvectors）との線形結合に基づいて獲得されることができ、上記変換ベクトルは、グラフラプラシアン行列の固有値（eigenvalue）の分布に基づくコスト関数を用いて決定できる。例えば、上記予測ベクトルは上記＜数式１９＞又は上記＜数式３７＞を用いて獲得できる。
【０２１３】
また、上記予測ベクトルは、エンコードされてデコーダに転送されるか、又はデコーダで導出されることもできる。転送方法には、例えば、ベクトル値を転送するか、又はベクトル値差を転送することもできるが、本発明はこれに限定されるものではない。
【０２１４】
図８は、本発明が適用される一実施形態であって、グラフ信号に基づいて最適化された予測ベクトルを獲得する過程を説明するためのフローチャートである。
【０２１５】
エンコーダは、受信したビデオ信号から予測信号を生成し、ビデオ信号で予測信号を減算して残差信号を生成することができる。上記残差信号に対して変換が実行されるが、この際、グラフベース信号処理技術を適用してグラフベース変換又はグラフベース予測を実行することができる。以下、グラフ信号に基づいてグラフベース予測を実行する方法を説明する。
【０２１６】
まず、エンコーダは、ビデオ信号のターゲットユニットに対応するグラフパラメータセットを決定することができる（Ｓ８１０）。例えば、グラフ信号Ｇの頂点パラメータ及びエッジ重み付け値のうち、少なくとも１つを決定することができる。
【０２１７】
そして、エンコーダは、グラフパラメータセット（graph parameter set）に基づいてグラフ信号を生成することができ、グラフ信号に基づいてグラフラプラシアン行列Ｌを算出することができる（Ｓ８２０）。
【０２１８】
エンコーダは、変換行列Ｔ及び固有値（eigenvalue）λを有するベクトルを決定するためにグラフラプラシアン行列Ｌのスペクトル分解（spectral decomposition）を実行することができ、上記スペクトル分解結果に基づいてグラフベース（基盤）変換行列を獲得することができる（Ｓ８３０）。この際、上記グラフベース変換行列は固有ベクトル（eigenvector）を含むことができる。
【０２１９】
エンコーダは、最適化関数を通じて最適な変換ベクトルを獲得することができる（Ｓ８４０）。この際、上記最適化関数に上記＜数式２４＞又は上記＜数式３４＞が用いられることができ、上記最適な変換ベクトルは、上記＜数式１８＞、上記＜数式２５＞、又は上記＜数式３６＞を用いて獲得できる。ここで、上記最適化関数は、コンテキスト信号、グラフラプラシアン行列の固有値（eigenvalue）及び固有ベクトル（eigenvector）を変数として有することができる。そして、上記最適化関数はラグランジュ乗数に基づく非制限最適化関数（unconstrained optimization function）で表現され、上記非制限最適化関数（unconstrained optimization function）は新たなＭ次元ベクトルにより表現できる。
【０２２０】
そして、エンコーダは上記最適な変換ベクトルを用いて予測ベクトルを算出することができる（Ｓ８５０）。ここで、上記予測ベクトルは、変換ベクトルと上記固有ベクトル（eigenvectors）との線形結合に基づいて獲得され、上記変換ベクトルは、上記グラフラプラシアン行列の固有値（eigenvalue）の分布に基づくコスト関数を用いて決定できる。例えば、予測関数に上記＜数式１９＞又は上記＜数式３７＞が利用できる。
【０２２１】
一方、上記算出された予測ベクトルは予測信号を生成するために利用できる。又は、他の例において、上記予測ベクトルは、エンコードされてデコーダに転送されるか、又はデコーダで導出されることもできる。
【０２２２】
図９は、本発明が適用される一実施形態であって、グラフベース予測を用いてビデオ信号をデコードする過程を説明するためのフローチャートである。
【０２２３】
本発明が適用されるデコーダは、グラフパラメータセット及び残差（レジデュアル）信号を含むビデオ信号を受信することができる（Ｓ９１０）。
【０２２４】
そして、グラフパラメータセットに基づいてグラフベース（基盤）変換行列を獲得することができる（Ｓ９２０）。上記獲得されたグラフベース（基盤）変換行列を用いて残差（レジデュアル）信号を復元することができる（Ｓ９３０）。
【０２２５】
一方、デコーダは最適化関数を通じて最適な変換ベクトルを算出することができる（Ｓ９４０）。この際、上記最適化関数は、コンテキスト信号、グラフラプラシアン行列の固有値（eigenvalue）及び固有ベクトル（eigenvector）を変数として有することができる。そして、上記最適化関数はラグランジュ乗数に基づく非制限最適化関数（unconstrained optimization function）で表現され、上記非制限最適化関数（unconstrained optimization function）は新たなＭ次元ベクトルにより表現できる。
【０２２６】
デコーダは上記最適な変換ベクトルを用いて予測ベクトルを獲得することができる（Ｓ９５０）。これは、デコーダの予測部又は逆変換部で実行できる。上記予測ベクトルは、変換ベクトルと上記固有ベクトル（eigenvectors）との線形結合に基づいて獲得され、上記変換ベクトルは上記グラフラプラシアン行列の固有値（eigenvalue）の分布に基づくコスト関数を用いて決定できる。
【０２２７】
そして、デコーダは上記予測ベクトルに基づいて予測信号を生成することができる（Ｓ９６０）。
【０２２８】
デコーダは、上記生成された予測信号と残差（レジデュアル）信号とを合せてビデオ信号を復元することができる（Ｓ９７０）。
【０２２９】
このように、本発明は、最適化関数を用いてグラフベース予測を実行する最適化予測アルゴリズムを提供することによって、低複雑度で予測値を獲得することができ、延いては、予測性能を向上させることができる。
【０２３０】
上で記述されたように、本発明で説明した実施形態は、プロセッサ、マイクロプロセッサ、コントローラ、又はチップ上で具現されて実行できる。例えば、上記図１、図２、図５、図６、及び図７で図示した機能ユニットは、コンピュータ、プロセッサ、マイクロプロセッサ、コントローラ、又はチップ上で具現されて実行できる。
【０２３１】
また、本発明が適用されるデコーダ及びエンコーダは、マルチメディア放送送受信装置、モバイル通信端末、ホームシネマビデオ装置、デジタルシネマビデオ装置、監視用カメラ、ビデオ対話装置、ビデオ通信などのリアルタイム通信装置、モバイルストリーミング装置、記憶（格納）媒体、カムコーダ、ビデオオンデマンド（注文型ビデオ）（VoD）サービス提供装置、インターネットストリーミングサービス提供装置、３次元（３Ｄ）ビデオ装置、画像電話ビデオ装置、及び医療用ビデオ装置などに含まれることができ、ビデオ信号及びデータ信号を処理するために使用できる。
【０２３２】
また、本発明が適用される処理方法は、コンピュータにより実行されるプログラムの形態で生産されることができ、コンピュータにより読み取ることができる記録媒体に記憶（格納）できる。本発明に従うデータ構造を有するマルチメディアデータもまたコンピュータにより読み取ることができる記録媒体に記憶できる。上記コンピュータにより読み取ることができる記録媒体は、コンピュータにより読み取ることができるデータが記憶される全ての種類の記憶装置を含む。上記コンピュータにより読み取ることができる記録媒体は、例えば、ブルーレイディスク（ＢＤ）、ユニバーサルシリアルバス（汎用直列バス）（ＵＳＢ）、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピ（登録商標）ディスク、及び光学データ記憶装置を含むことができる。また、上記コンピュータにより読み取ることができる記録媒体は、搬送波（例えば、インターネットを通じての転送）の形態で具現された媒体（メディア）を含む。また、エンコーディング方法により生成されたビットストリームがコンピュータにより読み取ることができる記録媒体に記憶されるか、又は有／無線通信ネットワークを介して転送できる。
【産業上の利用可能性】
【０２３３】
以上、前述した本発明の好ましい実施形態は、例示の目的のために開示されたものであって、当業者であれば、以下に添付した特許請求の範囲に開示された本発明の技術的思想とその技術的範囲内で、多様な他の実施形態を改良、変更、置き換え、又は付加などが可能である。
【図１】
0006356912.tif 000050
【図２】
0006356912.tif 000051
【図３（ａ）】
0006356912.tif 000052
【図３（ｂ）】
0006356912.tif 000053
【図４】
0006356912.tif 000054
【図５】
0006356912.tif 000055
【図６】
0006356912.tif 000056
【図７】
0006356912.tif 000057
【図８】
0006356912.tif 000058
【図９】
0006356912.tif 000059