(57)【特許請求の範囲】
【請求項１】
幾何要素を用いてイメージを処理する方法であって、
前記イメージ内のターゲットブロックのエッジ重み付け値を算出するために用いられる幾何要素を特定するステップであって、前記ターゲットブロックは、前記イメージの残差データを示すステップと、
前記幾何要素の各々に対するパラメータを獲得するステップと、
前記パラメータに基づいて前記イメージ内の前記ターゲットブロックのエッジの各々に対するエッジ重み付け値を算出するステップであって、前記ターゲットブロックのエッジは、前記ターゲットブロックの頂点を連結する線を示し、前記エッジ重み付け値は、前記頂点間の相関強度を示す値であるステップと、
前記エッジ重み付け値に基づいて変換ブロックを生成するステップと、を有し、
前記変換ブロックは、変換行列によって生成され、前記変換行列の各行及び列は、前記エッジ重み付け値に設定される、方法。
【請求項２】
前記ターゲットブロックのエッジに対する最小距離を算出するステップであって、前記最小距離は、前記エッジの中心から前記幾何要素までの距離を示すステップと、
距離対重み付け値関数に前記最小距離を適用するステップと、をさらに有し、
前記エッジ重み付け値は、前記距離対重み付け値関数に基づいて算出される、請求項１に記載の方法。
【請求項３】
前記パラメータは、タイプ情報、位置情報、又は長さ情報のうち、少なくとも一つを有する、請求項１に記載の方法。
【請求項４】
前記タイプ情報がデフォルトタイプと異なるか否かを確認するステップと、
前記タイプ情報が前記デフォルトタイプと異なる場合、前記距離対重み付け値関数のパラメータをエンコードするステップと、をさらに有する、請求項３に記載の方法。
【請求項５】
前記幾何要素の前記タイプ情報は、前記幾何要素の予め決定されたセットのうちの一つを示す、請求項３に記載の方法。
【請求項６】
前記幾何要素の各々は、互いに異なる距離対重み付け値関数を用いる、請求項３に記載の方法。
【請求項７】
前記エッジ重み付け値は、互いに異なる関数を用いることによって算出される、請求項６に記載の方法。
【請求項８】
前記幾何要素は、正規化された空間座標を用いることによって識別される、請求項１に記載の方法。
【請求項９】
イメージを処理する方法であって、
前記イメージ内のターゲットブロックのエッジ重み付け値を受信するステップであって、前記ターゲットブロックは、前記イメージの残差データを示し、前記ターゲットブロックのエッジは、前記ターゲットブロックの頂点を連結する線を示し、前記エッジ重み付け値は、前記頂点間の相関強度を示す値であるステップと、
前記エッジ重み付け値に基づいて変換行列を生成するステップであって、前記変換行列の各行及び列は、前記エッジ重み付け値に設定されるステップと、
前記変換行列を用いて前記ターゲットブロックに対して逆変換を行うステップと、
前記逆変換されたターゲットブロックに基づいて前記イメージの残差データを復元するステップと、を有する、方法。
【請求項１０】
前記エッジ重み付け値は、前記ターゲットブロックの幾何要素を用いて算出された、請求項９に記載の方法。
【請求項１１】
前記エッジ重み付け値は、前記ターゲットブロックのエッジと前記幾何要素との間の最小距離に基づいて算出され、
前記最小距離は、前記エッジの中心から前記幾何要素までの距離を示す、請求項１０に記載の方法。
【請求項１２】
前記エッジ重み付け値は、前記幾何要素のパラメータに基づいて算出された、請求項１０に記載の方法。
【請求項１３】
幾何要素を用いてイメージをエンコードする装置であって、
前記イメージ内のターゲットブロックのエッジ重み付け値を算出するために用いられる幾何要素を特定し、前記ターゲットブロックは、前記イメージの残差データを示し、
前記幾何要素の各々に対するパラメータを獲得し、
前記パラメータに基づいて前記イメージ内の前記ターゲットブロックのエッジの各々に対するエッジ重み付け値を算出し、前記ターゲットブロックのエッジは、前記ターゲットブロックの頂点を連結する線を示し、前記エッジ重み付け値は、前記頂点間の相関強度を示す値であり、
前記エッジ重み付け値に基づいて変換ブロックを生成する、よう構成されるプロセッサを有し、
前記変換ブロックは、変換行列によって生成され、前記変換行列の各行及び列は、前記エッジ重み付け値に設定される、装置。
【請求項１４】
イメージをデコードする装置であって、
前記イメージ内のターゲットブロックのエッジ重み付け値を受信し、前記ターゲットブロックは、前記イメージの残差データを示し、前記ターゲットブロックのエッジは、前記ターゲットブロックの頂点を連結する線を示し、前記エッジ重み付け値は、前記頂点間の相関強度を示す値であり、
前記エッジ重み付け値に基づいて変換行列を生成し、前記変換行列の各行及び列は、前記エッジ重み付け値に設定され、
前記変換行列を用いて前記ターゲットブロックに対して逆変換を行い、
前記逆変換されたターゲットブロックに基づいて前記イメージの残差データを復元するよう構成される、プロセッサを有する、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はグラフに基づく（基盤の、ベースの）信号処理方法及び装置に関し、より詳しくは、グラフに基づく信号上のエッジ重み付け値をコーディング（符号化）するための技術に関する。
【背景技術】
【０００２】
従来の離散時間信号処理技術は、大部分アナログ信号の処理及びフィルタリングから進化してきているが、正規に組織されたデータのサンプリングのように幾つかの共通の仮定により制限されてきた。ビデオ圧縮分野は、基本的に同一の仮定に基づいて（基盤して）おり、単に多次元信号の処理に一般化されただけである。
【０００３】
グラフは多くの応用分野においてデータの幾何学的構造を記述することに有用なデータ表現形態である。このようなグラフに基づいた信号処理は各信号サンプルが頂点（vertex）を示し、信号の関係が正の重み付け値を有するグラフエッジで示されるグラフを使用してサンプリング、フィルタリング、フーリエ（Fourier）変換などの概念を一般化することができる。この方式は、信号を獲得する処理（過程）と分離することによってサンプリング及びシーケンス処理においてグラフの特性に置き換え（取り替え）ることができる。したがって、より効率良いグラフに基づく信号処理方法がビデオ圧縮分野だけでなく多くの応用分野で要求される。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
グラフに基づく信号処理は、信号処理のさまざまな技術及びモデルを一般化する新たな技術分野であり、多くの応用分野で有望な結果を見せたことがある。但し、信号圧縮時、グラフに基づく信号処理方式を適用する（ようになる）場合、より良い信号変換又は予測を導出するためにはエンコーダとデコーダ（とが）全て同一のグラフ（例えば、 頂点、エッジ、及びエッジ重み付け値）を使用する必要がある。より向上した信号圧縮が複雑で、かつ適応的なグラフ構造で成就できるが、このようなグラフに関する情報をコーディングするオーバーヘッドが相対的に大きくなることによって、これらが提供する利得よりも大きくなることがあるという問題がある。したがって、本発明ではこのような問題を解決しようとする。
【課題を解決するための手段】
【０００５】
本発明は、ビデオコーディングのためのグラフトポロジ（topology）が固定されたグリッド（頂点がピクセルに該当するため、普通は平面）であり、エッジ重み付け値のみ変更されるという事実を用いてグラフ情報をコーディングするための解決策を提供する。そして、本発明の目的は、予測残差（残余）値のより良いコーディング集合のためのグラフに基づくツール（道具）を開発することにある。
【０００６】
このような場合のために設計されたグラフ上のエッジ重み付け値をコーディングするために、本発明は、一つ又は複数の幾何要素（点、線、円、曲線など）の集合を使用することができ、このような個体上の点までの距離に対する特定関数を使用して重み付け値を定義することができる。
【０００７】
また、本発明は、このような幾何要素を定義するパラメータ及び距離をエッジ重み付け値に変える（換える）関数のパラメータをコーディングすることによって、グラフ重み付け値の全体集合がグラフのサイズ及び複雑度に関わらず転送できる。また、互いに異なる幾何要素及び距離−重み付け値関数（distance-to-weight function）の集合は、より好ましいグラフ特性を示すことができるようにする。
【発明の効果】
【０００８】
本発明が適用されるグラフに基づく信号のモデル化は強力なツール（道具）になることができる。即ち、本発明は、グラフのエッジ重み付け値を適応的に変更し、スペクトル分解から得られた行列を使用することによって、より改善された信号表現、変換、及び予測を実行（遂行）することができる。
【０００９】
また、本発明は、データ圧縮で必要とし、圧縮応用分野のためのツールを使用することに有用（応用、適用）することができるより一般的なモデルに対する要求を扱う。
【００１０】
また、本発明は、より圧縮されたグラフ表現を使用することによって、個別のグラフのエッジ重み付け値をエンコードするために必要なビットレートの過度なオーバーヘッドを避けることができる。
【図面の簡単な説明】
【００１１】
【図１】本発明が適用される実施形態に従ってグラフに基づく信号を処理するエンコーダ及びデコーダの概略ブロック図を例示する図である。
【図２】本発明が適用される実施形態に従ってグラフに基づく信号を処理するエンコーダ及びデコーダの概略ブロック図を例示する図である。
【図３】本発明が適用される一実施形態に従ってビデオフレーム内の８×８ブロック内での統計的関係をモデル化するために使われたグラフの例を示す図である。
【図４】本発明が適用される一実施形態であって、重み付け値分布を示す２つの形態のグラフを示す図である。
【図５】本発明が適用される実施形態に従って個体の境界の周囲に集まる傾向がある残差（残余）信号の特性を例示する図である。
【図６】本発明が適用される一実施形態に従うグラフに基づく信号モデル化ユニットの概略ブロック図を例示する図である。
【図７】本発明が適用される一実施形態に従って多様なタイプの幾何要素を含むビデオフレームの例を示す図である。
【図８】本発明が適用される一実施形態に従って幾何要素を用いてビデオセグメント内のブロックのエッジをコーディングする方法を例示する図である。
【図９】本発明が適用される一実施形態に従って幾何要素を用いてビデオセグメント内のブロックのエッジをコーディングする処理を例示するフローチャートである。
【図１０】本発明が適用される一実施形態に従って距離−重み付け値関数（distance-to-weight function）に基づいてグラフに基づく信号をコーディングする処理を例示するフローチャートである。
【図１１】本発明が適用される一実施形態であって、グラフに基づく信号のエッジ重み付け値を用いてビデオ信号をデコードする処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１２】
本発明は、幾何要素（プリミティブ）（geometric primitive）を用いてグラフベース（に基づく）信号（グラフ基盤信号）を処理する方法であって、エッジ重み付け値（edge weight）を算出するために用いられる幾何要素を特定するステップと、幾何要素の各々に対するパラメータを獲得するステップと、パラメータに基づいてイメージ内のエッジの各々に対するエッジ重み付け値を算出するステップと、エッジ重み付け値に基づいてイメージをエンコードするステップと、を有することを特徴とする方法を提供する。
【００１３】
また、本発明は、ターゲットブロックに対応するグラフ内のエッジ（edge）に対する最小距離（minimum distance）を算出するステップと、距離対重み付け値関数（距離−重み付け値関数）に最小距離を適用するステップと、をさらに有し、エッジ重み付け値は距離対重み付け値関数に基づいて算出されることを特徴とする。
【００１４】
また、本発明で、最小距離は、エッジの中心から幾何要素までの距離を示すことを特徴とする。
【００１５】
また、本発明で、パラメータは、タイプ情報、位置情報、又は長さ情報のうち、少なくとも一つを有することを特徴とする。
【００１６】
また、本発明は、タイプ情報がデフォルトタイプと異なるか否かを確認するステップと、タイプ情報がデフォルトタイプと異なる場合、距離対重み付け値関数のパラメータをエンコードするステップと、をさらに有することを特徴とする。
【００１７】
また、本発明で、幾何要素のタイプ情報は、幾何要素の既に決定された３個のうちの一つを示すことを特徴とする。
【００１８】
また、本発明で、幾何要素の各々は、互いに異なる距離対重み付け値関数を用いることを特徴とする。
【００１９】
また、本発明で、エッジ重み付け値は、互いに異なる関数を用いることによって算出されることを特徴とする。
【００２０】
また、本発明で、イメージは、残差信号に対応することを特徴とする。
【００２１】
また、本発明で、幾何要素は、正規化された空間座標を用いることによって識別されることを特徴とする。
【００２２】
本発明は、グラフベースビデオ信号（グラフ基盤ビデオ信号）を処理する方法であって、エッジ重み付け値（edge weight）を受信するステップと、エッジ重み付け値を用いて変換行列を生成するステップであって、変換行列はターゲットブロック内のエッジのエッジ重み付け値に基づいてマッピングされるステップと、変換行列を用いて変換係数を獲得するステップと、獲得された変換係数に基づいてグラフベースビデオ信号を復元するステップと、を有することを特徴とする方法を提供する。
【００２３】
本発明は、幾何要素（geometric primitive）を用いてグラフベース信号（グラフ基盤信号）をエンコードする装置であって、エッジ重み付け値（edge weight）を算出するために用いられる幾何要素を特定し、幾何要素の各々に対するパラメータを獲得し、パラメータに基づいてイメージ内のエッジの各々に対するエッジ重み付け値を算出し、エッジ重み付け値に基づいてイメージをエンコードするプロセッサを有することを特徴とする装置を提供する。
【００２４】
本発明は、グラフベースビデオ信号をデコードする装置であって、グラフベースビデオ信号からエッジ重み付け値（edge weight）を受信し、エッジ重み付け値を残差信号に適用することによって変更された残差信号を獲得し、変更された残差信号に基づいてグラフベースビデオ信号を復元するプロセッサを有し、変換行列は、ターゲットブロック内のエッジのエッジ重み付け値に基づいてマッピングされることを特徴とする装置を提供する。
〔発明の実施のための形態〕
【００２５】
以下、添付した図面を参照して本発明の実施形態の構成とその作用とを説明するが、図面により説明される本発明の構成及び作用は、一つの実施形態として説明されるものであり、これによって本発明の技術的思想とその核心構成及び作用が制限されるものではない。
【００２６】
併せて、本発明で使われる用語は、できる限り現在広く使われる一般的な用語を選択したが、特定の場合は出願人が任意に選定した用語を使用して説明する。そのような場合には該当部分の詳細説明でその意味を明確に記載するので、本発明の説明で使われた用語の名称だけで単純に解析されてはならず、その該当用語の意味まで把握して解析されなければならないことを明らかにしようとする。
【００２７】
また、本明細書で提示された実施形態はビデオ信号処理に関するものであるが、本発明は、ビデオ信号処理のみに基づいたものとして推論されてはならず、一般的なグラフに基づく信号処理方法にも適用できるものである。
【００２８】
また、本発明で使われる用語は、発明を説明するために選択された一般的な用語や、類似の意味を有する他の用語がある場合、より適切な解析のために置き換え可能である。例えば、信号、データ、サンプル、ピクチャ、フレーム、ブロックなどの場合、各コーディング処理において適切に置き換えられて解析できる。
【００２９】
図１及び２は、本発明が適用される実施形態に従ってグラフに基づく信号を処理するエンコーダ及びデコーダの概略ブロック図を例示する。
【００３０】
図１のエンコーダ１００は、変換ユニット１１０、量子化ユニット１２０、逆量子化ユニット１３０、逆変換ユニット１４０、バッファ１５０、予測ユニット１６０、及びエントロピエンコードユニット１７０を含む。
【００３１】
上記エンコーダ１００は、ビデオ信号を受信し、上記ビデオ信号から上記予測ユニット１６０で出力された予測された信号を差し引いて予測エラーを生成する。
【００３２】
上記生成された予測エラーは、上記変換ユニット１１０に転送される。
【００３３】
上記変換ユニット１１０は、変換方式を上記予測エラーに適用することによって変換係数を生成する。
【００３４】
上記量子化ユニット１２０は、上記生成された変換係数を量子化して上記量子化された係数をエントロピエンコードユニット１７０に転送する。
【００３５】
上記エントロピエンコードユニット１７０は、上記量子化された信号に対するエントロピコーディングを実行し、エントロピコーディングされた信号を出力する。
【００３６】
一方、上記量子化ユニット１２０により出力された上記量子化された信号は、予測信号を生成するために使用できる。例えば、上記エンコーダ１００のループ内の上記逆量子化ユニット１３０及び上記逆変換ユニット１４０は、上記量子化された信号が予測エラーに復元されるように上記量子化された信号に対する逆量子化及び逆変換を実行することができる。復元された信号は上記復元された予測エラーを上記予測ユニット１６０により出力された予測信号に加えることによって生成できる。
【００３７】
上記バッファ１５０は、予測ユニット１６０の今後の参照のために復元された信号を記憶する。
【００３８】
上記予測ユニット１６０は、以前に復元されて上記バッファ１５０に記憶された信号を使用して予測信号を生成することができる。このような場合、本発明は、アンカ（anchor）イメージ内の領域を使用して目標（対象）イメージ内の領域を効率良く予測することに関連したものである。ここで、上記アンカイメージは、参照イメージ、参照ピクチャ、又は参照フレームを意味することができる。効率は率（レート）−歪み（Rate-Distortion）コスト（費用）又は予測エラー内の歪みを定量化する平均二乗（自乗）エラーを算出することによって決定できる。
【００３９】
より良い信号表現、変換、及び予測を実行するために、本発明は、幾何要素を使用し、幾何要素までの距離を重み付け値でマッピングさせる関数を用いてグラフに基づく信号をモデル化する方法を提案する。また、本発明はグラフ内の頂点とエッジとを識別し、残差値信号をエンコード又はデコードする方法を提案する。例えば、本発明の実施形態は、グラフに基づく信号モデル化ユニット（グラフ基盤信号モデリングユニット）６００を通じて多様な実施形態を実行することができる。上記グラフに基づく信号モデル化ユニットは、上記エンコーダ１００又は上記デコーダ２００に含まれることができる。
【００４０】
図２のデコーダ２００は、エントロピデコードユニット２１０、逆量子化ユニット２２０、逆変換ユニット２３０、バッファ２４０、及び予測ユニット２５０を含む。
【００４１】
図２のデコーダ２００は、図１のエンコーダ１００により出力された信号を受信する。
【００４２】
上記エントロピデコードユニット２１０は、受信した信号に対するエントロピデコードを実行する。上記逆量子化ユニット２２０は、量子化ステップのサイズに関する情報に基づいて上記エントロピデコードされた信号から変換係数を獲得する。上記逆変換ユニット２３０は、変換係数に対する逆変換を実行することによって予測エラーを取得する。復元された信号は、上記獲得された（取得した）予測エラーを上記予測ユニット２５０により出力された予測信号に加えることによって生成される。
【００４３】
上記バッファ２４０は、上記予測ユニット２５０の今後の参照のために上記復元された信号を記憶する。
【００４４】
上記予測ユニット２５０は、以前に復元されて上記バッファ２４０に記憶された信号に基づいて予測信号を生成する。
【００４５】
本発明が適用される上記グラフに基づく信号モデル化方法は、上記エンコーダ１００及び上記デコーダ２００の全てで使われる。
【００４６】
図３は、本発明が適用される一実施形態に従ってビデオフレーム内の８×８ブロック内での統計的関係をモデル化するために使われたグラフの例を示す。
【００４７】
図３を参照すると、本発明は、イメージ又はビデオ内の８×８ピクセルブロックの処理のために使用できるグラフタイプの２つ実施形態を提供する。各ピクセルはグラフの頂点に関連し（関連付けられ）、上記ピクセルの値はグラフ頂点の値となる。
【００４８】
グラフエッジは、グラフ頂点を連結する線を意味することができる。上記グラフエッジは、信号内の如何なる（任意の）形態の統計的依存性を示すために使われて、この際、正の重み付け値はその強度を示すことができる。例えば、各頂点は全ての他の頂点に連結されることができ、０の重み付け値は互いに関連しないか、又は弱く関連した頂点を連結するエッジに割り当てることができる。但し、表現の簡単化の（表現を簡単にする）ために、０の重み付け値を有するエッジは完全に除去できる。
【００４９】
本発明の他の実施形態において、グラフ頂点を連結するエッジは信号特性によって予め設定できる。例えば、頂点は、オーディオ信号に対しては１次元配列上に、イメージに対しては２次元配列上に、またビデオフレームに対しては３次元配列上に配置できる。この際、上記３次元配列の場合には時間軸が３番目の次元になることができる。例えば、図３（ａ）のグラフで、グラフエッジは各々の頂点がそれから最も近い４個の隣接頂点に連結されるように定義できる。但し、ブロック境界の場合は異なって（異に）取り扱うことができる。また、図３（ｂ）のグラフでは各々の頂点がそれから最も近い８個の隣接頂点に連結されるように定義できる。
【００５０】
図４は、本発明が適用される一実施形態であって、重み付け値の分布を示す２つの形態のグラフを示す。
【００５１】
グラフの頂点値は、信号測定（通常任意の変数にモデル化される）に基づく独立変数であるが、一部信号の特性と合致するグラフのエッジ重み付け値を選択することが必要である。図４において、グラフエッジに対する線の色相（濃淡、太さ）が互いに異なるエッジ重み付け値を示すグラフの２つの例が提供される。例えば、濃い色の線（太線）はｗ＝１の重み付け値を示し、薄い色の線（細線）はｗ＝０．２の重み付け値を示すことができる。
【００５２】
図４（ａ）のグラフは、直線に沿って“弱いリンク”を有している場合を示し、２つのエッジ重み付け値のみを有している場合を示す。ここで、上記“弱いリンク”は相対的に小さなエッジ重み付け値を有していることを意味する。
【００５３】
これは事実上、グラフに基づくイメージ処理で通常使われるものであり、このような構成は、イメージ内のエッジと他の辺との間のピクセル統計の差を示すことができる。
【００５４】
グラフに基づく信号処理のために使われる基本ツールは＜数式１＞のようにグラフのラプラシアン行列から導出できる。
【００５５】
＜数式１＞
【数１】
0006392453.tif 000002
【００５６】
＜数式１＞で、Ｄは次数対角行列であり、Ａは隣接行列である。
【００５７】
グラフに基づく信号処理のための多くのツールが＜数式２＞のような行列Ｌのスペクトル分解に基づく（基盤する）ことができる。
【００５８】
＜数式２＞
【数２】
0006392453.tif 000003
【００５９】
＜数式２＞において、上記直交行列Ｕは、該当グラフモデルに適う（適合する）信号に対する特殊化されたグラフに基づくフーリエ（Fourier）変換形態を提供する。
【００６０】
図４（ｂ）のグラフは、不規則な領域をカバーするエッジ重み付け値の分布を示し、本発明ではこのようなエッジ重み付け値の分布グラフを用いて信号を処理する方法を提供しようとする。
【００６１】
図５は、本発明が適用される実施形態に従って個体の境界周囲に集まる傾向がある残差信号の特性を例示するための図面を示す。
【００６２】
本発明は、データ圧縮のために要求されるより一般的なモデルに対する要求を扱う。例えば、コーディングの応用において、処理対象信号は元ピクセルの値でない残差信号でありうる。例えば、元信号から予測された値を差し引いた予測残差値でありうる。図５（ａ）はビデオフレームを図示し、図５（ｂ）は残差信号値の分布を図示する。例えば、図５（ｂ）で白色は０値を示し、黒色は残差信号値を示し、黒色の濃度が濃いほど残差信号値が大きく、相対的に黒色の濃度が薄いほど残差信号値が小さいことを示す。
【００６３】
このようなタイプの信号に対し、上記グラフは、明確に定義されたエッジのような特性を有するのではないが、代わりに特定領域に集まっているノイズサンプルを有することを示す。このような場合、上記図４（ｂ）の例に図示されたように、不均一な領域をカバーする重み付け値分布を有するグラフに対する処理方法が必要でありうる。
【００６４】
図６は、本発明が適用される一実施形態に従うグラフに基づく信号モデル化ユニット（グラフ基盤信号モデリングユニット）の概略ブロック図を例示する。
【００６５】
本発明が適用されるグラフに基づく信号モデル化を通じてビデオ信号をより効率良く処理することができる。エッジ重み付け値（edge weight）を適応的に変更し、グラフの行列Ｌのスペクトル分解から得られた行列を使用することによって、より改善された信号表現、変換、及び予測を得ることができる。
【００６６】
本発明の実施形態をより柔軟に適用するためには、エッジ重み付け値（edge weight）を適応的に変更させる必要がある。エンコーダは、入力信号のデータセットを使用してグラフに基づく信号をエンコードすることができ、デコーダは、上記データセットの一部又は全部を定めた順序に基づいて受信することができ、これを用いてデコードすることができる。
【００６７】
本発明の一実施形態で、エンコーダは、エッジ重み付け値（edge weight）に対する（関する）データセットの一部又は全部をエンコードすることができ、それによってデコーダは、上記データセットの一部又は全部をデコードすることによって行列Ｌの新たな値を計算することができる。
【００６８】
上記図３のような簡単なグラフの場合にも頂点毎に複数のグラフエッジを有することができるので、効率良いコーディングを実行することが容易でないことがある。例えば、Ｎ×Ｎブロックに対してピクセル４個の連結された頂点を有するグラフは、２Ｎ（Ｎ−１）≒２Ｎ2個のグラフエッジを有し、図３（ｂ）のようにピクセル８個の連結された頂点を有するグラフは２（Ｎ−１）（２Ｎ−１）≒４Ｎ2個のグラフエッジを有する（ようになる）。
【００６９】
一方、全てのエッジ重み付け値（edge weight）をエンコードするためには、頂点又はピクセル毎に２、４、又はそれ以上のグラフエッジを必要とすることがある。この場合、エッジ重み付け値（edge weight）をコーディング（符号化）するために多数のビットを必要とするため、効率良い圧縮コーディングを実行し難いことがある。
【００７０】
本発明の一実施形態で、グラフエッジをコーディングするために２つの互いに異なるエッジ重み付け値（edge weight）（例えば、０．１及び１）を用いることができる。例えば、重み付け値のうちの一つの確率がｐであり、本発明が最適な０の順次（次数）を有するエントロピエンコーダを使用することができると仮定する。このような場合、グラフエッジのビットレートは＜数式３＞のように示すことができる。
【００７１】
＜数式３＞
【数３】
0006392453.tif 000004
【００７２】
この場合、上記＜数式３＞を用いて、グラフベース信号処理により得ることができるコーディングの利得は０．１ビット／ピクセル、又は０．０１ビット／ピクセルより大きくなることができない。したがって、本発明では、グラフ重み付け値に対するより精巧なコーディング方法を使用することによって、過度なオーバーヘッドを緩和させることができる新たな方法を提供する。
【００７３】
エッジ重み付け値（edge weight）を個別にエンコードするためには、ビットレートオーバーヘッドが要求される。本発明ではこれを解決するために複数のグラフエッジに関する情報を一度に提供する方法を提供する。例えば、複数のグラフエッジに対する共通情報を、定めた単位によってコーディングすることができる。ここで、上記定まった単位は、グラフ単位、フレームピクチャ単位、ブロック単位、ピクセル単位、及びビデオ信号コーディングのために用いられる多様な単位を含むことができる。上記方式を用いる場合、たとえコーディングのためのビットがさらに必要であっても、エッジ当たり又はピクセル当たりの平均ビットレートは小さく維持できる。
【００７４】
本発明は、次のようなビデオコーディングの特別な性質に基づくことができる。
【００７５】
第１に、ピクセル集合を処理するために用いられるグラフは、規則的な（標準的な）フォーマット（regular format）で生成できる。例えば、イメージの場合には平面（planar）で生成されることができ、又は多次元空間（multi-dimensional space）の場合には四角格子（rectangular lattice）で生成できる。この場合、エッジ重み付け値（edge weight）のみ変更できる。
【００７６】
第２に、ランダムな残差信号（random residual signal）はビデオ個体（人、壁など）の境界に集まる傾向があり、これは普通２次元曲線で定義できるが、それに限定されず、１次元直線や点などで定義されることもできる。一方、残差信号が小さな領域では概してこれらの値が互いに類似することがある。
【００７７】
第３に、残差信号は相互間で正確な境界を有せず、したがって、エッジ重み付け値（edge weight）が変化する正確な位置をエンコード又はデコードするためにビットを消費する必要がない。
【００７８】
本発明の一実施形態は、一般的なフレーム座標を使用して統計上の変化を特定信号に転送することによって上記第１の特性を用いることができる。
【００７９】
例えば、本発明は、ビデオフレーム又は全体フレームの特定部分で正規化された空間Ｓ＝［０，１］×［０，１］を使用することによって、全てのグラフ内の頂点とエッジを識別することができる。例えば、本発明は＜数式４＞のようにグラフエッジの重み付け値関数を定義することができる。
【００８０】
＜数式４＞
【数４】
0006392453.tif 000005
【００８１】
この場合、各々の位置ｘ∈Ｓに対する重み付け値ｗ（ｘ）が獲得できる。
【００８２】
Ｗ×Ｈピクセルの集合を仮定すると、Ｓ内のピクセル（ｉ、ｊ）の位置は＜数式５＞のように定義できる。
【００８３】
＜数式５＞
【数５】
0006392453.tif 000006
【００８４】
ここで、Ｗはグラフ又はフレームの幅を示し、Ｈはグラフ又はフレームの高さを示す。
【００８５】
本発明の更に他の実施形態で、ピクセル（ｉ、ｊ）と（ｋ、ｌ）との間のエッジ重み付け値（edge weight）は、＜数式６＞のようにグラフエッジの中間点を用いて定義できる。
【００８６】
＜数式６＞
【数６】
0006392453.tif 000007
【００８７】
ここで、ｗ（）はグラフエッジの重み付け値関数を示し、（ｉ、ｊ）及び（ｋ、ｌ）は任意のピクセル位置を示す。そして、Ｗ×Ｈピクセルの集合を仮定すると、ｉ、ｋは０，１，…，Ｗ−１の値を示し、ｊ、ｌは０，１，…，Ｈ−１の値を示すことができる。
【００８８】
このような接近（近似、アプローチ）方式を通じて、全てのグラフエッジの重み付け値をコーディングするためのオーバーヘッドがグラフエッジの個数との関係がなくなり、全てのｘ∈Ｓに対してｗ（ｘ）を計算するための情報を効率良くコーディングすることに依存できる（ようになる）。
【００８９】
本発明の更に他の実施形態は、上記第２の特性を用いて重み付け値関数ｗ（ｘ）を計算する方法を提案することによって、効率良いコーディングを実行することができる。例えば、本発明は、大きい値を有する残差信号が集まって幾何学的要素（geometric primitive）を構成するという特徴を用いることができる。
【００９０】
このような場合、本発明は、点（point）、線（line）、線分（線セグメント）（line segment）、円（circle）、キュービックスプライン（３次式近似）を用いる線（lines using cubic splines）、及びベジェ（ビジェ）曲線（Bezier curves）などの少なくとも一つの幾何要素を含む幾何要素集合を使用して効率良いコーディングを実行することができる。
【００９１】
例えば、図７は、分離された点、直線、及び曲線などの一部の幾何要素を有するビデオフレームの例を示す。
【００９２】
本発明の更に他の実施形態は、上記第３の特性に基づいて、ｗ（ｘ）2の定義を完成するために幾何要素までの距離を重み付け値でマッピングする関数Φ（ｄ、Ｐ１、Ｐ２）（以下、“距離−重み付け値関数（distance-to-weight function）”という）を使用する。例えば、上記距離−重み付け値関数（distance-to-weight function）は＜数式７＞及び＜数式８＞のように定義できる。
【００９３】
＜数式７＞
【数７】
0006392453.tif 000008
【００９４】
この際、ｄはターゲットユニットから幾何要素までの距離であり、μ、ηは追加パラメータ（additional parameter）を示す。例えば、上記ターゲットユニットはエッジ重み付け値（edge weight）を測定するための処理単位を意味することができ、上記ターゲットユニットは、頂点（vertex）、ピクセル（pixel）、エッジ（edge）、ブロック（block）、又はフレーム（frame）のうち、少なくとも一つを含むことができる。また、距離ｄを測定するための基準点には、例えば、 頂点、ピクセル、又はエッジなどを挙げることができる。一方、上記追加パラメータは、スケールパラメータ（scale parameter）及び変更パラメータ（change parameter）のうち、少なくとも一つを含むことができ、具体的な例において、μはスケールパラメータ（scale parameter）を示し、ηは変更パラメータ（change parameter）を示すことができる。
【００９５】
＜数式８＞
【数８】
0006392453.tif 000009
【００９６】
この場合、＜数式８＞は＜数式７＞の補数（complement）（補関数）を示す。
【００９７】
例えば、距離−重み付け値関数（distance-to-weight function）のグラフの形態は、変更パラメータ（change parameter）ηにより変更できる。また、上記距離ｄは上記スケールパラメータ（scale parameter）μによりサイズが調整できる。また、上記距離−重み付け値関数（distance-to-weight function）は他のタイプの幾何要素及び距離尺度に対しても定義できる。
【００９８】
一方、図６を参照すると、グラフに基づく信号モデル化ユニット（グラフ基盤信号モデリングユニット）６００は、グラフ生成ユニット６１０、幾何要素エンコードユニット（幾何学要素エンコーディングユニット）６２０、及びエッジ重み付け値エンコードユニット（エッジ重み付け値エンコーディングユニット）６３０を含むことができる。
【００９９】
本発明が適用される上記グラフに基づく信号モデル化ユニット６００は、上記距離−重み付け値関数（distance-to-weight function）に基づいてエッジ重み付け値（edge weight）をコーディングすることができる。また、上記グラフに基づく信号モデル化ユニット６００は、ターゲットブロックに該当するグラフ内の少なくとも一つの参照幾何要素の集合をコーディングすることができる。上記少なくとも一つの参照幾何要素の集合は、エッジ重み付け値（edge weight）を決定するために使用できる。
【０１００】
上記グラフ生成ユニット６１０は、ターゲットイメージに該当するグラフを生成することができる。例えば、上記＜数式１＞のような上記グラフのラプラシアン行列がグラフに基づく信号処理のために使用できる。
【０１０１】
上記幾何要素エンコードユニット６２０は、生成されたグラフ内の幾何要素をエンコードすることができる。このような場合、上記幾何要素はさまざまなパラメータにより定義できる。例えば、上記幾何要素は、幾何要素のタイプ情報及び位置情報のうち、少なくとも一つを用いて定義できる。上記タイプ情報は、点タイプ、線タイプ、円タイプ、キュービックスプラインを使用する線タイプ（line type using cubic splines）、又はベジェ曲線タイプ（Bezier curve type）のうち、少なくとも一つを含むことができる。
【０１０２】
また、上記幾何要素エンコードユニット６２０は、ビデオフレーム内の幾何要素の個数をエンコードすることができる。このような場合、上記ビデオフレームは残差信号成分でありうる。幾何要素の個数によって、上記幾何要素エンコードユニット６２０は、幾何要素の各々のタイプ情報及びそのパラメータ情報を獲得することができる。
【０１０３】
上記エッジ重み付け値エンコードユニット６３０は、上記距離−重み付け値関数（distance-to-weight function）に基づいてエッジ重み付け値をエンコードすることができる。例えば、本発明は、ターゲットユニットの基準点から幾何要素までの距離に基づいて上記ターゲットユニットのエッジに対する重み付け値を算出することができ、この際、上記距離−重み付け値関数（distance-to-weight function）が利用できる。
【０１０４】
具体的な実施形態において、上記エッジ重み付け値エンコードユニット６３０は、エッジの中心から各々の幾何要素までの最小距離を算出することができる。上記エッジ重み付け値エンコードユニット６３０は、上記算出された最小距離に基づいてエッジ重み付け値を算出することができる。この際、上記距離−重み付け値関数（distance-to-weight function）が利用できる。上記エッジ重み付け値は、エンコードされてデコーダに転送できる。
【０１０５】
また、上記エッジ重み付け値エンコードユニット６３０は、上記距離−重み付け値関数（distance-to-weight function）を各々の最小距離に適用し、その結果に基づいて最終的なエッジ重み付け値を算出することができる。上記処理はビデオ信号のターゲットユニットに対して実行できる。
【０１０６】
上記エッジ重み付け値エンコードユニット６３０は、上記距離−重み付け値関数（distance-to-weight function）に基づいてブロック内の全てのピクセルの値をエンコードすることができる。
【０１０７】
図７は、本発明が適用される一実施形態に従って多様なタイプの幾何要素を含むビデオフレームの例を示す。
【０１０８】
本発明の一実施形態は、幾何学的要素（geometric primitive）が大きい値を有する残差信号で構成できるという特徴に基づいて、距離−重み付け値関数（distance-to-weight function）を算出する方法を提案する。本発明は、少なくとも一つの幾何要素を含む幾何要素集合を用いることによって、このような特性をより効率良くエンコード又はデコードすることができる。例えば、図７は単独点（isolated point）、直線、及び曲線などの幾何要素を含むビデオフレームの例を示す。
【０１０９】
図７において、上記幾何要素はタイプ情報により定義できる。例えば、上記タイプ情報は、点（point）、線（line）、線分（line segment）、円（circle）、キュービックスプラインを用いる線（lines using cubic splines）、及びベジェ曲線（Bezier curves）のうち、少なくとも一つを含むことができる。
【０１１０】
例えば、図７を参照すると、タイプ情報ＧＰ１（Geometric Primitive １；以下、‘ＧＰ１’という）はキュービックスプラインを用いる線（lines using cubic splines）を示し、タイプ情報ＧＰ２（Geometric Primitive ２；以下、‘ＧＰ２’という）、及びＧＰ３（Geometric Primitive ３；以下、‘ＧＰ３’という）は線分を示し、タイプ情報ＧＰ４（Geometric Primitive ４；以下、‘ＧＰ４’という）は連結された線分を示し、ＧＰ Ｎ（Geometric Primitive N；以下、‘ＧＰ Ｎ’という）は点を示す。
【０１１１】
図７で、細い灰色の線は、ビデオフレーム処理のためのコーディングユニット又はエッジ重み付け値を算出するためのターゲットユニットを意味することができ、幾何要素の多様な色相はエッジ重み付け値の分布が識別できるように定義できる。
【０１１２】
本発明が適用される他の実施形態において、幾何要素は位置情報により定義できる。例えば、ビデオフレーム内の座標情報又はピクセルの位置情報を用いて上記幾何要素を定義することができる。又は、上記幾何要素は２進データにより定義されることもできる。
【０１１３】
本発明が適用される他の実施形態において、幾何要素はタイプ情報に基づいて他の方式により定義できる。例えば、点（point）タイプの場合、座標情報により定義されることができ、線（line）タイプ、線分（line segment）タイプ、円（circle）タイプ、キュービックスプラインを用いる線（lines using cubic splines）タイプ、及びベジェ曲線（Bezier curves）タイプの場合には座標関数により定義できる。
【０１１４】
図８は、本発明が適用される一実施形態に従って幾何要素を用いてビデオセグメント内のブロックのエッジをコーディングする方法を例示する図面を示す。
【０１１５】
図８のブロックは一部の幾何要素を有しているビデオセグメントの部分を示し、太線で示されたブロックはターゲットブロックを示す。
【０１１６】
図８を参照すると、上記ビデオセグメントは点（ＧＰ４）、２つの線分（ＧＰ１、ＧＰ３）、及びキュービックスプラインを使用する線（ＧＰ２）を含む４個の幾何要素を有する。
【０１１７】
まず、エンコーダは、幾何要素の個数情報をエンコードすることができる。例えば、図８のビデオセグメントは４個の幾何要素を含んでいるので、それに対応する値を幾何要素の個数情報としてエンコードすることができる。
【０１１８】
また、上記４個の幾何要素の各々に対し、上記エンコーダは、上記幾何要素のタイプ情報をエンコードすることができる。例えば、ＧＰ１の場合に、上記エンコーダは、ＧＰ１のタイプ情報を長い線のセグメントとしてエンコードすることができる。
【０１１９】
上記‘長い線のセグメント’のタイプがデフォルトタイプでない場合、上記エンコーダは、ＧＰ１に対して使われる距離−重み付け値関数（distance-to-weight function）のパラメータをエンコードすることができる。
【０１２０】
次に、上記エンコーダは、上記距離−重み付け値関数（distance-to-weight function）に基づいてエッジ重み付け値をエンコードすることができる。上記エッジ重み付け値は、エッジの中心から幾何要素の各々までの最小距離に基づいて決定できる。
【０１２１】
例えば、図８を参照すると、太線で示されたブロックをターゲットユニットということができ、上記ターゲットユニットは、エッジ１、エッジ２、エッジ３、及びエッジ４のように４個のエッジを含んでいる。したがって、上記ターゲットユニットのエッジ重み付け値を算出するために、上記４個のエッジ各々の中心から幾何要素までの最小距離を算出することができる。例えば、エッジ１の場合、最小距離ｄ１、ｄ２、ｄ３、及びｄ４（点線）は、上記エッジ１の中心から各幾何要素までの距離を測定することによって算出できる。このように算出された最小距離に基づいて上記エッジ１のエッジ重み付け値を獲得することができる。この際、上記距離−重み付け値関数（distance-to-weight function）が利用できる。
【０１２２】
上記エンコーダは、上記エッジ１に対するエッジ重み付け値を獲得する処理を、上記エッジ２乃至エッジ４に対しても繰り返して実行することができる。このような処理を経て算出されたエッジ重み付け値を用いて上記ターゲットユニット内のピクセル値をエンコードすることができる。例えば、上記エッジ重み付け値を用いて上記ターゲットユニットに対する変換又は予測を実行することができ、これを通じて上記ターゲットユニットをエンコードすることができる。ここで、上記ターゲットユニットは、元データ（original data）、予測データ（predicted data）、又は残差データ（residual data）を含むことができる。
【０１２３】
本発明が適用される他の実施形態において、エッジ重み付け値を決定するためにビデオフレーム内の一部の幾何要素のみを用いることができる。例えば、ターゲットエッジに最も近い幾何要素のみを用いてエッジ重み付け値を決定することができる。具体的な例において、図８を参照すると、エッジ１の場合、エッジ１に最も近い幾何要素ＧＰ１を選択することができ、上記エッジ１の中心から上記最も近い幾何要素ＧＰ１までの最小距離ｄ１を算出することができる。このように算出された最小距離ｄ１に基づいて上記エッジ１のエッジ重み付け値を獲得することができる。この際、上記距離−重み付け値関数（distance-to-weight function）が利用できる。
【０１２４】
本発明が適用される他の実施形態において、エッジ重み付け値を決定するために、以前に決定されたエッジのエッジ重み付け値を用いることができる。例えば、上記以前に決定されたエッジは、現在ターゲットユニットのエッジ、又は他のユニットのエッジでありうる。ここで、他のユニットということはビデオフレーム内の上記現在ターゲットユニットを除外した（以外の）ユニットを意味することができる。具体的には、現在エッジに隣り合うエッジのエッジ重み付け値を用いて上記エッジ重み付け値を決定することができる。例えば、図８を参照すると、エッジ重み付け値が、エッジ１、エッジ２、エッジ３、そしてエッジ４の順に決定されると仮定する。この際、エッジ４のエッジ重み付け値を決定しようとする場合、現在ターゲットユニットの他のエッジであるエッジ１、エッジ２、及びエッジ３のうち、少なくとも一つを用いることができる。例えば、エッジ１、エッジ２、又はエッジ３のうち、いずれか一つのエッジ重み付け値をエッジ４のエッジ重み付け値に用いることができる。又は、エッジ１、エッジ２、又はエッジ３のうち、いずれか２つを用いることもでき、３個の中間値を用いることもできる。
【０１２５】
更に他の例において、上記エッジ１に隣接した他のユニットのエッジを用いてエッジ重み付け値を予測することができる。例えば、エッジ１の場合、エッジ１に隣接した上側ブロック、左上側ブロック、右上側ブロック、左下側ブロック、又は右下側ブロックのエッジのうち、少なくとも一つを用いて上記エッジ１のエッジ重み付け値を予測することができる。
【０１２６】
更に他の例において、エッジ重み付け値を予測するために、現在フレームだけでなく、他のフレーム内のブロックのエッジのエッジ重み付け値を用いることもできる。
【０１２７】
図９は、本発明が適用される一実施形態に従って幾何要素を用いてビデオセグメント内のブロックのエッジをコーディングする処理を例示するフローチャートである。
【０１２８】
本発明が適用されるエンコード方法には、次のようなアルゴリズムが適用できる。例えば、本発明は、コーディングブロック、フレーム、又はそのセットなどのビデオセグメントの各々に対して上記エンコード方法を繰り返して実行することができる。
【０１２９】
上記エンコーダは、ターゲットユニットに対して用いられる幾何要素の個数Ｎをエンコードすることができる（Ｓ９１０）。
【０１３０】
各々の幾何要素ｎ＝１，２，．．．，Ｎに対し、上記エンコーダは幾何要素のタイプ情報及び追加パラメータをエンコードすることができる（Ｓ９２０）。例えば、幾何要素のタイプ情報がデフォルトタイプと異なる場合、上記エンコーダは上記幾何要素に対して使われる距離−重み付け値関数（distance-to-weight function）のパラメータをエンコードすることができる。例えば、上記追加パラメータは、スケールパラメータ（scale parameter）及び変更パラメータ（change parameter）のうち、少なくとも一つを含むことができる。
【０１３１】
具体的な例において、距離−重み付け値関数（distance-to-weight function）のグラフ形態は変更パラメータ（change parameter）により変更できる。また、上記距離−重み付け値関数（distance-to-weight function）の変数である距離ｄは、スケールパラメータ（scale parameter）によりサイズを調整できる。
【０１３２】
また、ビデオセグメント内のブロックの各々に対して次のような処理を実行できる。
【０１３３】
グラフ内のターゲットユニットの各エッジに対し、上記エンコーダはエッジの中心から各々の幾何要素までの最小距離を算出し、上記算出された最小距離に基づいてエッジ重み付け値を獲得することができる（Ｓ９３０）。
【０１３４】
この後、エンコーダは上記ターゲットユニットのエッジ重み付け値を用いてターゲットユニット内のピクセル値をエンコードすることができる（Ｓ９４０）。ここで、上記ターゲットユニットは元データ（original data）、予測データ（predicted data）、又は残差データ（residual data）を含むことができる。
【０１３５】
図１０は、本発明が適用される一実施形態に従って距離−重み付け値関数（distance-to-weight function）に基づいてグラフに基づく信号をコーディングする処理を例示するフローチャートである。
【０１３６】
上記グラフに基づく信号モデル化ユニット６００は、距離−重み付け値関数（distance-to-weight function）に基づいてグラフに基づく信号をコーディングすることができる。
【０１３７】
例えば、上記エッジ重み付け値エンコードユニット６３０は、エッジの中心から幾何要素までの最小距離を計算することができる（Ｓ１０１０）。
【０１３８】
また、上記エッジ重み付け値エンコードユニット６３０は、上記距離−重み付け値関数（distance-to-weight function）に上記最小距離を適用することができ（Ｓ１０２０）、その結果値に基づいて最終的なエッジ重み付け値を算出することができる（Ｓ１０３０）。上記処理は、ビデオセグメント内の各ターゲットユニットに対して実行できる。
【０１３９】
そして、上記エッジ重み付け値エンコードユニット６３０は、ターゲットユニット内のピクセル値をエンコードするために上記ターゲットユニットのグラフ情報を用いることができる（Ｓ１０４０）。ここで、グラフ情報はエッジ重み付け値、幾何要素のタイプ情報、及び追加パラメータのうち、少なくとも一つを含むことができる。
【０１４０】
本発明の他の実施形態において、幾何要素は予め定義された幾何要素の集合でありうる。上記距離−重み付け値関数（distance-to-weight function）は、幾何要素までの最も近い距離を重み付け値でマッピングすることができる。
【０１４１】
本発明の実施形態の更に他の実施形態で、本発明は、互いに異なる幾何要素からの重み付け値を結合する方法を提供する。
【０１４２】
例えば、単一関数が他の幾何要素からの重み付け値を結合するために使用できる。上記単一関数は最も近い要素までの最小距離である単一値のｄを有する。
【０１４３】
本発明の更に他の実施形態で、互いに異なる関数を幾何要素の各々に対して割り当てることができる。例えば、＜数式９＞及び＜数式１０＞のように互いに異なる関数をエッジ重み付け値を算出するために活用できる。
【０１４４】
＜数式９＞
【数９】
0006392453.tif 000010
【０１４５】
＜数式１０＞
【数１０】
0006392453.tif 000011
【０１４６】
上記＜数式９＞及び＜数式１０＞で、Φｎ（ｄ，．．．）（ｎ＝１，２，．．．，Ｎ）は、各幾何要素に対するＮ個の異なる距離−重み付け値関数を示す。上記＜数式９＞の場合はＮ個の互いに異なる距離−重み付け値関数に基づいて算出されたエッジ重み付け値のうちの最大値を示し、上記＜数式１０＞の場合はＮ個の互いに異なる距離−重み付け値関数に基づいて算出されたエッジ重み付け値のうちの中間値を示す。
【０１４７】
本発明の更に他の実施形態で、上記実施形態は、フレーム内の予測により獲得された（ような）固定されたブロックに適用できる。また、幾何要素のパラメータはモーション補償を用いてコーディングできる。
【０１４８】
また、上記実施形態はより高次元空間に拡張できる。例えば、本発明は［０，１］D空間の内部に含まれた幾何要素を定義することができ、関数ｗ（ｘ）を使用することができ、この際、ｘ∈［０，１］Dである。
【０１４９】
図１１は、本発明が適用される一実施形態であって、グラフに基づく信号のエッジ重み付け値を用いてビデオ信号をデコードする処理を説明するためのフローチャートである。
【０１５０】
デコーダは、エンコーダからグラフに基づく信号のエッジ重み付け値をシンタックス構成要素として受信することができる（Ｓ１１１０）。例えば、上記エッジ重み付け値は、シーケンス情報、ピクチャ情報、スライスヘッダ、スライスデータ、コーディングユニット、変換ユニット、残差信号コーディングシンタックス、及びブロックユニットのうち、少なくとも一つに含まれて転送できる。又は、上記エッジ重み付け値は、デコーダ内の他の情報から類推することができ、例えば上記エッジ重み付け値は幾何要素に対するパラメータから導出できる。
【０１５１】
本発明の一実施形態において、デコーダは、エッジ重み付け値を獲得し、変換ブロックを生成するために上記エッジ重み付け値を用いることができる（Ｓ１１２０）。例えば、上記変換ブロックは変換行列で表現されることができ、上記変換行列の各行及び列はターゲットユニット内の各エッジのエッジ重み付け値に設定できる。
【０１５２】
そして、上記変換ブロックに基づいて変換係数をデコードすることができる（Ｓ１１３０）。
【０１５３】
上記変換係数に基づいて残差信号を復元し、上記残差信号を予測信号に加えることによって復元信号を生成できる（ようになる）（Ｓ１１４０）。
【０１５４】
本発明の他の実施形態において、デコーダは、エッジ重み付け値を獲得し、残差信号を補正するために上記エッジ重み付け値を用いることができる。例えば、上記残差信号に上記エッジ重み付け値を適用することによって、変更された残差信号を獲得することができる。
【０１５５】
上記処理を通じて獲得された変更された残差信号を予測信号に加えることによって復元信号を生成できる（ようになる）。
【０１５６】
本発明の他の実施形態において、デコーダは、エッジ重み付け値を獲得し、上記エッジ重み付け値を予測信号を生成するために用いることができる。
【０１５７】
本発明の他の実施形態において、エンコーダは、上記エッジ重み付け値を変換ブロック信号を生成するために用いるか、又は予測信号を生成するために用いることができる。
【０１５８】
本発明の他の実施形態において、エンコーダは、残差信号を生成し、上記生成された残差信号にエッジ重み付け値を適用することによって、上記残差信号を補正することができる。即ち、残差信号にエッジ重み付け値を適用することによって、変更された残差信号を生成することができる。この場合、デコーダは既に変更された残差信号を受信する（ようになる）ので、デコーダではエッジ重み付け値を受信する必要がないか、又は予測信号を生成するためにエッジ重み付け値を用いることができる。
【０１５９】
本発明の他の実施形態において、デコーダは、エンコーダからグラフに基づく信号の幾何要素に対するパラメータをシンタックス構成要素として受信することができる。例えば、上記パラメータは、幾何要素のタイプ情報、個数情報、及び追加パラメータのうち、少なくとも一つを含むことができ、これは先の本明細書で説明した内容が適用できる。デコーダは、上記パラメータに基づいてエッジ重み付け値を類推することができる。
【０１６０】
上記のような処理を通じて、デコーダは、エッジ重み付け値を類推することができ、残差信号を補正するために上記エッジ重み付け値を用いることができる。例えば、上記残差信号に上記エッジ重み付け値を適用することによって、変更された残差信号を獲得することができる。そして、変更された残差信号を予測信号に加えることによって、復元信号を生成できる（ようになる）。
【０１６１】
上記記述されたように、本発明で説明した実施形態は、プロセッサ、マイクロプロセッサ、コントローラ、又はチップ上で具現されて実行できる。例えば、上記図１、図２、及び図６で図示した機能ユニットは、コンピュータ、プロセッサ、マイクロプロセッサ、コントローラ、又はチップ上で具現されて実行できる。
【０１６２】
また、本発明が適用されるデコーダ及びエンコーダは、マルチメディア放送送受信装置、モバイル通信端末、ホームシネマビデオ装置、デジタルシネマビデオ装置、監視用カメラ、ビデオ対話装置、ビデオ通信などのリアルタイム通信装置、モバイルストリーミング装置、記憶媒体、カムコーダ（キャムコーダ）、注文型ビデオ（ＶｏＤ）サービス提供装置、インターネットストリーミングサービス提供装置、３次元（３Ｄ）ビデオ装置、画像電話ビデオ装置、及び医療用ビデオ装置などに含まれることができ、ビデオ信号及びデータ信号を処理するために使用できる。
【０１６３】
また、本発明が適用される処理方法は、コンピュータにより実行されるプログラムの形態で生産（作成）されることができ、コンピュータにより読み取ることができる記録（記憶）媒体に記憶できる。本発明に従うデータ構造を有するマルチメディアデータもまたコンピュータにより読み取ることができる記録媒体に記憶できる。上記コンピュータにより読み取ることができる記録媒体は、コンピュータにより読み取ることができるデータが記憶される全ての種類の記憶装置を含む。上記コンピュータにより読み取ることができる記録媒体は、例えば、ブルーレイディスク（ＢＤ）、ユニバーサルシリアル（汎用直列）バス（ＵＳＢ）、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピ（登録商標）ディスク、及び光学データ記憶装置を含むことができる。また、上記コンピュータにより読み取ることができる記録媒体は、搬送波（例えば、インターネットを通じての転送）の形態で具現されたメディアを含む。また、エンコード方法により生成されたビットストリームは、コンピュータにより読み取ることができる記録媒体に記憶されるか、又は有線／無線通信ネットワークを介して転送できる。
【産業上の利用可能性】
【０１６４】
以上、前述した本発明の好ましい実施形態は、例示の目的のために開示されたものであって、当業者であれば、以下に添付した特許請求範囲に開示された本発明の技術的思想とその技術的範囲内で、多様な他の実施形態を改良、変更、取替、又は付加などが可能である。
【図１】
0006392453.tif 000012
【図２】
0006392453.tif 000013
【図３（ａ）】
0006392453.tif 000014
【図３（ｂ）】
0006392453.tif 000015
【図４（ａ）】
0006392453.tif 000016
【図４（ｂ）】
0006392453.tif 000017
【図５（ａ）】
0006392453.tif 000018
【図５（ｂ）】
0006392453.tif 000019
【図６】
0006392453.tif 000020
【図７】
0006392453.tif 000021
【図８】
0006392453.tif 000022
【図９】
0006392453.tif 000023
【図１０】
0006392453.tif 000024
【図１１】
0006392453.tif 000025