(57)【要約】【課題】スケーラビリテイを保障するとともに利用する、タイムコンシステントな３次元メッシュシーケンスを予測的に圧縮する方法が提供される。【解決手段】本方法によると、メッシュシーケンスの各フレームは複数の階層に分割され、これにより、タイムコンシステントな多解像度表現が得られる。予測符号化のパラダイムに従って、階層ごとの圧縮のために、階層間及びフレーム間における局所的な時間的空間的な依存性が用いられる。現在の頂点位置を予測するために、符号化済みの近傍の頂点の動きを利用して、頂点ごとに粗な階層から密な階層へと予測が行われる。したがって、階層ごとに順次復号化することによって、精度を向上させつつフレームを再構成することができる。【選択図】図２
2010527523.tif 000002
【特許請求の範囲】
【請求項１】
タイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスを、スケーラブルな符号化を用いて符号化する方法であって、
３次元メッシュシーケンスの連続フレームを受信する工程を含み、
フレームは関連付けられた接続性（Κ）を伴う頂点の集合（Ｖ）（ｓｅｔ  ｏｆ  ｖｅｒｔｉｃｅｓ（Ｖ）  ｗｉｔｈ  ａｓｓｏｃｉａｔｅｄ  ｃｏｎｎｅｃｔｉｖｉｔｙ（Ｋ））を含み、
前記接続性（Ｋ）は３次元メッシュシーケンスのすべてのフレームについて同一であり、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する工程と、
符号化器を用いて前記階層に含まれる頂点を符号化する工程とを含むことを特徴とする符号化方法。
【請求項２】
前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算し、且つ／又は、
スケーラブルな予測符号化を用いることを特徴とする、請求項１に記載の符号化方法。
【請求項３】
前記シーケンスの第１のフレームについて、前記３次元メッシュシーケンスの接続性（Ｋ）を符号化する工程と、
各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から、１の圧縮方法を選択する工程とをさらに含むことを特徴とする、請求項１又は２に記載の符号化方法。
【請求項４】
前記３次元メッシュシーケンスを多解像度表現に分解する工程は、
ｎｕｍｂｅｒＯｆＤｅｃｏｍｐｏｓｅｄＬａｙｅｒｓの値を、分解の階層数（Ｌ）に設定する工程と、
前記設定された分解の階層数（Ｌ）を符号化する工程と、
１つの中間の頂点を共有する３角形の集合を含む１以上のパッチを選択する工程とを含み、
前記中間の頂点（ｍｉｄｄｌｅ  ｖｅｒｔｅｘ）は所定の数以下、特に、６以下の価数（ｖａｌｅｎｃｅ）を有し、
前記価数は前記中間の頂点に直接隣接する頂点の数によって定義され、
前記１以上の選択されたパッチの中間の頂点を削除し、関連付けられた接続性（ＫＬ）を伴う該削除された中間の頂点によって定義される分解された階層（ＶＬ）を生成する工程と、
残りの頂点の集合に関連する単純化された接続性を決定する工程と、
１以上のパッチを選択する工程、中間の頂点を削除する工程、及び、単純化された接続性を決定する工程を、残りの単純化された接続性を伴う頂点の集合について、設定された階層数よりも２少ない反復回数（Ｌ−２）に亘って、繰り返すことにより、関連付けられた接続性（ＫＬ−１，…，Ｋ２）を伴う分解された階層（ＶＬ−１，…，Ｖ２）を生成する工程と、
残りの関連付けられた接続性Ｋ１を伴う頂点の集合（Ｖ１）を基底階層（ｂａｓｅ  ｌａｙｅｒ）として定義する工程とを含むことを特徴とする、請求項１乃至３のいずれか１項に記載の符号化方法。
【請求項５】
前記残りの頂点の集合に関連する単純化された接続性を決定する工程は、削除された頂点の以前の最近接（１−ｒｉｎｇ  ｎｅｉｇｈｂｏｒｈｏｏｄ）の頂点を３角形分割する工程を含み、
前記最近接（頂点）は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、該３角形分割及び前記階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数（ｖａｌｅｎｃｅ）に対する、削除された頂点の最近接の頂点の価数の平均絶対偏差に基いて選択されることを特徴とする、請求項４に記載の符号化方法。
【請求項６】
予測符号化器を用いて前記階層に含まれる頂点を符号化する工程は、
選択された各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から１の圧縮方法を選択する工程と、
Ｉ−フレーム予測子、Ｐ−フレーム予測子、又は、Ｂ−フレーム予測子をそれぞれ用いて、予測誤差を生成する工程と、を含むことを特徴とする、請求項１乃至５のいずれか１項に記載の符号化方法。
【請求項７】
現フレームの現頂点についてのＩ−フレーム圧縮は、該現フレームの該現頂点の符号化済みの最近接（頂点）の位置の平均としてＩ−フレーム予測子を計算することを含むことを特徴とする、請求項６に記載の符号化方法。
【請求項８】
現フレームの現頂点についてのＰ−フレーム圧縮は、符号化済みのフレームを参照フレームとみなし、請求項６に従って計算された現フレームの現頂点のＩ−フレーム予測子と、参照フレームにおける現頂点の位置と請求項６に従って計算された該参照フレームの現頂点のＩ−フレーム予測子との間の差とを足し合わせることによって、Ｐ−フレーム予測子を計算することを含むことを特徴とする、請求項６又は７に記載の符号化方法。
【請求項９】
前記差は、回転行列（Ｒｏｔａｔｉｏｎ  Ｍａｔｒｉｘ）（Ａ）と掛け合わされることを特徴とする、請求項８に記載の符号化方法。
【請求項１０】
現フレームの現頂点についてのＢ−フレーム圧縮は、符号化済みの２つのフレームをそれぞれ第１の参照フレーム及び第２の参照フレームとみなし、該第１の参照フレームを考慮した請求項８又は９によるＰ−フレーム予測子と、該第２の参照フレームを考慮した請求項８又は９によるＰ−フレーム予測子との平均、特に、重み付き平均を計算することによって、Ｂ−フレーム予測子を計算することを含むことを特徴とする、請求項６乃至９のいずれか１項に記載の符号化方法。
【請求項１１】
前記選択された予測子を示す情報を符号化し、それによって、予測子は、フレームごと又は階層ごとに、特に、所定の個数のビットを用いて符号化されることを特徴とする、請求項６乃至１０のいずれか１項に記載の符号化方法。
【請求項１２】
予測符号化器を用いて前記階層に含まれる頂点を符号化する工程は、
前記予測誤差を量子化する工程と、
前記量子化された予測誤差を符号化する工程と、をさらに含むことを特徴とする、請求項１乃至１１のいずれか１項に記載の符号化方法。
【請求項１３】
前記予測誤差は、量子化ビンのサイズ（Δ）として、特に、ｃｏｏｒｄｓＱｕａｎｔｉｚａｔｉｏｂｎＳｔｅｐの値を用いて、均一に量子化されることを特徴とする、請求項１２に記載の符号化方法。
【請求項１４】
前記量子化された予測誤差の各成分は、エントロピー符号化を用いて個別に符号化されることを特徴とする、請求項１２又は１３に記載の符号化方法。
【請求項１５】
所定の範囲、特に、−３から＋３までの所定の範囲の整数値に含まれる値に対して算術符号化を用い、該所定の範囲の整数値以外の値に対してゴロム（Ｇｏｌｏｍｂ）符号を用いて、前記量子化された予測誤差の成分をエントロピー符号化することを特徴とする、請求項１４に記載の符号化方法。
【請求項１６】
各階層について個別の算術符号化器を用い、
各算術符号化器は、符号化済みのフレームから得られた量子化予測誤差の統計的分布を用いるように構成されていることを特徴とする、請求項１４又は１５に記載の符号化方法。
【請求項１７】
予測精度を向上させるために最適な参照フレームを決定し、
決定した参照フレームを識別する付加情報を符号化し、且つ／又は、参照フレーム番号を、現フレームのフレーム番号に対するオフセットをそれぞれ表すｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０、又は、ｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０及びｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ１の値として、参照フレーム番号を現フレームにおいて符号化することを特徴とする、請求項１乃至１６のいずれか１項に記載の符号化方法。
【請求項１８】
タイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスをスケーラブルな予測符号化を用いて符号化する符号化器であって、
フレームが関連付けられた接続性（ｃｏｎｎｅｃｔｉｖｉｔｙ）（Ｋ）を伴う頂点の集合（Ｖ）を含み、該接続性（Ｋ）が３次元メッシュシーケンスのすべてのフレームについて同一である、３次元メッシュシーケンスの連続フレームを受信する受信手段と、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する分解手段と、
予測符号化器を用いて前記階層に含まれる頂点を符号化する符号化手段とを備えていることを特徴とする符号化器。
【請求項１９】
前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算することを特徴とする、請求項１８に記載の符号化器。
【請求項２０】
前記シーケンスの第１のフレームについて、前記３次元メッシュシーケンスの接続性（Ｋ）を符号化する接続性符号化手段と、
各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から、１の圧縮法方法を選択する選択手段とをさらに備えていることを特徴とする、請求項１８又は１９に記載の符号化器。
【請求項２１】
削除された頂点の以前の最近接（１−ｒｉｎｇ  ｎｅｉｇｈｂｏｒｈｏｏｄ）の頂点を３角形分割する３角形分割手段をさらに備え、
前記最近接は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、削除された頂点の最近接の頂点の価数の、該３角形分割及び現在の階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数からの平均絶対偏差に基いて選択され、
前記価数は、頂点に直接隣接する頂点の数によって定義されることを特徴とする、請求項１８乃至２０のいずれか１項に記載の符号化器。
【請求項２２】
各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群から１の圧縮方法を選択する選択手段をさらに備え、
前記符号化器は、Ｉ−フレーム予測子、Ｐ−フレーム予測子、又は、Ｂ−フレーム予測子をそれぞれ用いて、予測誤差を生成するように構成されていることを特徴とする、請求項１８乃至２１のいずれか１項に記載の符号化器。
【請求項２３】
前記選択された予測子を特定して符号化する情報符号化手段を備え、それによって、該予測子は、フレームごと又は階層ごとに、特に、所定の個数のビットを用いて、符号化されることを特徴とする、請求項２２に記載の符号化器。
【請求項２４】
前記予測誤差を、特に、量子化ビンのサイズ（Δ）としてｃｏｏｒｄｓＱｕａｎｔｉｚａｔｉｏｎＳｔｅｐの値を用いて、量子化する量子化手段と、
前記量子化された予測誤差を符号化する誤差符号化手段、及び／又は、
所定の範囲、特に、−３から＋３までの範囲の整数値に含まれる値に対して算術符号化を用い、該所定の範囲の整数値以外の値に対してゴロム（Ｇｏｌｏｍｂ）符号を用いて、前記量子化された予測誤差の成分を符号化するエントロピー符号化手段と、を備えていることを特徴とする、請求項１８乃至２３のいずれか１項に記載の符号化器。
【請求項２５】
決定した参照フレームを識別する付加情報を符号化する付加情報符号化手段を有し、特に、該付加情報符号化手段は、現フレームのフレーム番号に対するオフセットをそれぞれ表すｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０、又は、ｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０及びｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ１の値として、参照フレーム番号を現フレームにおいて符号化するように構成されていることを特徴とする、請求項１８乃至２４のいずれか１項に記載の符号化器。
【請求項２６】
タイムコンシステントな３次元メッシュシーケンスを符号化する符号化器であって、
特に、請求項１乃至１７のいずれか１項に記載の符号化方法を実施する際に、
一のフレームは頂点の集合（Ｖ）及びその接続性（Ｋ）を含み、該接続性（Ｋ）は３次元メッシュシーケンスのすべてのフレームについて同一である、３次元メッシュシーケンスの連続フレームを受信する３次元メッシュシーケンスブロックと、
前記シーケンスの第１フレームに対する３次元メッシュシーケンスの接続性（Ｋ）を符号化する接続性符号化ブロックと、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する階層設計ブロックとを備え、
前記分解は前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から計算され、
各フレームについて、Ｉ−フレーム圧縮、Ｐ−フレーム圧縮及びＢ−フレーム圧縮を含む一群の圧縮方法から、１の圧縮方法を選択するフレーム順序制御ブロックと、
予測符号化器を用いて、前記階層に含まれる頂点を符号化するＤＰＣＭ符号化ブロックと、
前記符号化を制御するとともに、ＤＰＣＭ符号化ブロックにおける頂点を予測する予測子を選択する階層圧縮制御ブロックと、を備えていることを特徴とする符号化器。
【請求項２７】
請求項１乃至１７のいずれか１項に記載の符号化方法を実行するように構成されていることを特徴とする、タイムコンシステントな３次元メッシュシーケンスを符号化する符号化器。
【請求項２８】
各フレームが関連付けられた接続性（Ｋ）を伴う頂点の集合（Ｖ）を含み、該接続性（Ｋ）がスケーラブルな符号化によって符号化される３次元メッシュシーケンスのすべてのフレームについて同一である、複数のフレームによって定義される、符号化されたタイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスを表すデータ信号を復号化する方法であって、
前記データ信号を受信する工程と、
前記３次元メッシュシーケンスの接続性（Ｋ）を復号化する工程と、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンス又はその接続性を分解する工程と、
復号化器を用いて前記複数の階層に含まれる頂点を復号化する工程とを含むことを特徴とする復号化方法。
【請求項２９】
前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算し、且つ／又は、
スケーラブルな予測的復号化を用いることを特徴とする、請求項２８に記載の復号化方法。
【請求項３０】
各フレーム、及び／又は、各階層について、符号化器によって用いられる圧縮方法を示す情報を復号化し、特に、参照フレームの番号を表す参照フレーム番号を復号化する工程をさらに含むことを特徴とする、請求項２８又は２９に記載の復号化方法。
【請求項３１】
使用する圧縮法を、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から選択することを特徴とする、請求項３０に記載の復号化方法。
【請求項３２】
前記３次元メッシュシーケンスを多解像度表現に分解する工程は、
符号化器から受信した、階層数（Ｌ）を示すｎｕｍｂｅｒＯｆＤｅｃｏｍｐｏｓｅｄＬａｙｅｒｓの値を復号化する工程と、
１以上のパッチを選択し、且つ／又は、１つの中間の頂点を共有する３角形の集合を含む１以上のパッチを識別する情報を復号化する工程とを含み、
前記中間の頂点は所定の数以下、特に、６以下の価数を有し、
前記価数は前記中間の頂点に直接隣接する頂点の数によって定義され、
前記１以上の選択されたパッチの中間の頂点を削除し、関連付けられた接続性（ＫＬ）を伴う該削除された中間の頂点によって定義される分解された階層（ＶＬ）を生成する工程と、
残りの頂点の集合に関連する単純化された接続性を決定する工程と、
１以上のパッチを選択する工程、中間の頂点を削除する工程、及び、単純化された接続性を決定する工程を、残りの単純化された接続性を伴う頂点の集合について、復号化された階層数よりも２少ない反復回数（Ｌ−２）に亘って、繰り返すことにより、関連付けられた接続性（ＫＬ−１，…，Ｋ２）を伴う分解された階層（ＶＬ−１，…，Ｖ２）を生成する工程と、
残りの関連付けられた接続性Ｋ１を伴う頂点の集合（Ｖ１）を基底階層（ｂａｓｅ  ｌａｙｅｒ）として定義する工程とを含むことを特徴とする、請求項２８乃至３１のいずれか１項に記載の復号化方法。
【請求項３３】
前記残りの頂点の集合に関連する単純化された接続性を決定する工程は、削除された頂点の以前の最近接の頂点を３角形分割する工程を含み、
前記際近接（頂点）は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、該３角形分割及び前記階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数に対する、削除された頂点の最近接の頂点の価数の平均絶対偏差に基いて選択されることを特徴とする、請求項３２に記載の復号化方法。
【請求項３４】
指定された圧縮方法に従って予測子を決定する工程と、
予測誤差を復号化する工程と、
特定された予測子及び復号化された予測誤差に基いて、対応する頂点の予測値、及び／又は、位置データを計算する工程とを含み、
これらの工程は、好ましくは各階層において行われることを特徴とする、請求項２８乃至３３のいずれか１項に記載の復号化方法。
【請求項３５】
基底階層の頂点の位置データを復号化する工程を含むことを特徴とする、請求項２８乃至３４のいずれか１項に記載の復号化方法。
【請求項３６】
現フレームの現頂点についてＩ−フレームを圧縮する場合に、該現フレームの該現頂点の復号化済みの最近接（頂点）の位置の平均としてＩ−フレーム予測子を計算することを含むことを特徴とする、請求項３０乃至３５のいずれか１項に記載の復号化方法。
【請求項３７】
現フレームの現頂点のＰ−フレームを圧縮する場合に、復号化済みのフレームを参照フレームとみなし、請求項３６に従って計算された現フレームの現頂点のＩ−フレーム予測子と、参照フレームの現頂点の位置と請求項３６に従って計算された該参照フレームの現頂点のＩ−フレーム予測子との間の差とを足し合わせることによって、Ｐ−フレーム予測子を計算することを含むことを特徴とする、請求項３０乃至３６のいずれか１項に記載の復号化方法。
【請求項３８】
前記差は、回転行列（Ｒｏｔａｔｉｏｎ  Ｍａｔｒｉｘ）（Ａ）と掛け合わされることを特徴とする、請求項３７に記載の復号化方法。
【請求項３９】
現フレームの現頂点のＢ−フレームを圧縮する場合に、符号化済みの２つのフレームをそれぞれ第１の参照フレーム及び第２の参照フレームとみなし、該第１の参照フレームを考慮した請求項３７又は３８によるＰ−フレーム予測子と、該第２の参照フレームを考慮した請求項３７又は３８によるＰ−フレーム予測子との平均、特に、重み付き平均を計算することによって、Ｂ−フレーム予測子を計算することを含むことを特徴とする、請求項３０乃至３８のいずれか１項に記載の復号化方法。
【請求項４０】
前記選択された予測子を示す情報は、フレームごと又は階層ごとに、特に、所定の個数のビットを用いて復号化されることを特徴とする、請求項２８乃至３９のいずれか１項に記載の復号化方法。
【請求項４１】
エントロピー符号化を用いることを特徴とする、請求項２８乃至４０のいずれか１項に記載の復号化方法。
【請求項４２】
前記エントロピー復号化は、所定の範囲、特に、−３から＋３までの所定の範囲の整数地に含まれる値に対して算術符号化を用い、該所定の範囲の整数値以外の値に対してゴロム符号を用い、特に、各階層について個別の算術符号化器を用い、
各算術復号化器は、特に、復号化済みのフレームから得られた量子化ビンのサイズ（Δ）として、ｃｏｏｒｄｓＱｕａｎｔｉｚａｔｉｏｎＳｔｅｐの値を用いて量子化された、量子化予測誤差の統計的分布を用いるように構成されていることを特徴とする、請求項４１に記載の復号化方法。
【請求項４３】
請求項１乃至１７のいずれか１項に記載の符号化方法により、且つ／又は、請求項１８乃至２７のいずれか１項に記載の符号化器により、符号化されたデータ信号を復号化するように構成されていることを特徴とする、請求項２８乃至４２のいずれか１項に記載の復号化方法。
【請求項４４】
各フレームが関連付けられた接続性（Ｋ）を伴う頂点の集合（Ｖ）を含み、該接続性（Ｋ）がスケーラブルな予測符号化を用いて符号化される３次元メッシュシーケンスのすべてのフレームについて同一である、複数のフレームによって定義される、符号化されたタイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスを表すデータ信号を復号化する復号化器であって、
前記データ信号を受信する受信手段と、
前記３次元メッシュシーケンスの接続性（Ｋ）を復号化する復号化手段と、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する分解手段と、
予測復号化器を用いて前記階層に含まれる頂点を復号化する手段と、を備えていることを特徴とする復号化器。
【請求項４５】
前記分解手段は、前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算するように構成されていることを特徴とする、請求項４４に記載の復号化器。
【請求項４６】
各フレームについて、符号化器によって用いられる圧縮方法を示す情報を復号化する復号化手段を備えていることを特徴とする、請求項４４又は４５に記載の復号化器。
【請求項４７】
使用する圧縮方法を、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から選択することを特徴とする、請求項４６に記載の復号化器。
【請求項４８】
前記３次元メッシュシーケンスを多解像度表現に分解する分解手段は、
符号化器から受信した、階層数（Ｌ）を示すｎｕｍｂｅｒＯｆＤｅｃｏｍｐｏｓｅｄＬａｙｅｒｓの値を復号化する工程と、
１つの中間の頂点を共有する３角形の集合を含む１以上のパッチ選択する工程とを含み、
前記中間の頂点は所定の数以下、特に、６以下の価数を有し、
前記価数は前記中間の頂点に直接隣接する頂点の数によって定義され、
前記１以上の選択されたパッチの中間の頂点を削除し、関連付けられた接続性（ＫＬ）を伴う該削除された中間の頂点によって定義される分解された階層（ＶＬ）を生成する工程と、
残りの頂点の集合に関連する単純化された接続性を決定する工程と、
１以上のパッチを選択する工程、中間の頂点を削除する工程、及び、単純化された接続性を決定する工程を、残りの単純化された接続性を伴う頂点の集合について、階層数よりも２少ない反復回数（Ｌ−２）に亘って、繰り返すことにより、関連付けられた接続性（ＫＬ−１，…，Ｋ２）を伴う分解された階層（ＶＬ−１，…，Ｖ２）を生成する工程と、
残りの関連付けられた接続性Ｋ１を伴う頂点の集合（Ｖ１）を基底階層（ｂａｓｅ  ｌａｙｅｒ）として定義する工程とを実行するように構成されていることを特徴とする、請求項４４乃至４７のいずれか１項に記載の復号化器。
【請求項４９】
前記復号化器は、削除された頂点の以前の最近接の頂点を３角形分割する工程を実行することによって、残りの頂点の集合に関連する単純化された接続性を決定するように構成され、
前記際近接（頂点）は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、該３角形分割及び前記階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数に対する、削除された頂点の最近接の頂点の価数の平均絶対偏差に基いて選択されることを特徴とする、請求項４８に記載の復号化器。
【請求項５０】
指定された圧縮法に従って予測子を決定する予測子決定手段を備えていることにより、
前記復号化器は、予測誤差を復号化するとともに、特定された予測子及び復号化された予測誤差に基いて、対応する頂点の位置データを計算するように構成されていることを特徴とする、請求項４５乃至４９のいずれか１項に記載の復号化器。
【請求項５１】
復号化のためのエントロピー復号化手段を備えていることを特徴とする、請求項４４乃至５０のいずれか１項に記載の復号化器。
【請求項５２】
前記エントロピー復号化手段は、所定の範囲、特に、−３から＋３までの所定の範囲の整数地に含まれる値に対して算術符号化を用い、該所定の範囲の整数値以外の値に対してゴロム符号を用い、特に、各階層について個別の算術符号化器を用い、
各算術復号化器は、特に、復号化済みのフレームから得られた量子化ビンのサイズ（Δ）として、ｃｏｏｒｄｓＱｕａｎｔｉｚａｔｉｏｎＳｔｅｐの値を用いて量子化された、量子化予測誤差の統計的分布を用いるように構成されていることを特徴とする、請求項５１に記載の復号化器。
【請求項５３】
タイムコンシステントな３次元メッシュシーケンスを表すデータ信号を復号化する、特に、請求項４４乃至５２のいずれか１項に記載の復号化器であって、
前記３次元メッシュシーケンスの符号化された接続性（Ｋ）を復号化するとともに、３次元メッシュシーケンスブロックに該接続性（Ｋ）を保存する接続性復号化ブロックと、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する階層設計ブロックとを備え、
前記分解は前記３次元メッシュシーケンス接続性（Ｋ）のみから計算され、
各フレームについて、圧縮方法を制御する制御手段と、
予測復号化器を用いて、前記階層に含まれる頂点を復号化するＤＰＣＭ復号化ブロックと、
前記復号化を制御するとともに、前記ＤＰＣＭ復号化ブロックにおいて頂点を予測するための予測子を選択する階層圧縮制御ブロックと、を備えていることを特徴とする復号化器。
【請求項５４】
各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から、１の圧縮法を選択するフレーム順序制御ブロックとして、前記制御手段が設計されていることを特徴とする、請求項５３に記載の復号化器。
【請求項５５】
復号化器は、請求項２８乃至４３のいずれか１項に記載の復号化方法を実行するように構成され、
請求項１乃至１７のいずれか１項に記載の符号化方法によって符号化されたデータ信号を復号化し、且つ／又は、
請求項１８乃至２７のいずれか１項に記載の符号化器によって符号化されたデータ信号を復号化することを特徴とする、請求項４４乃至５４のいずれか１項に記載の復号化器。
【請求項５６】
タイムコンシステントな３次元メッシュシーケンスを符号化するコンピュータプログラムであって、
請求項１８乃至２７のいずれか１項に記載の符号化器を制御するコンピュータ上で、前記コンピュータプログラムを動作させた場合に、請求項１乃至１６のいずれか１項に記載の符号化方法の各工程を、該符号化器に実行させるプログラムコード手段を含むことを特徴とするコンピュータプログラム。
【請求項５７】
符号化されたタイムコンシステントな３次元メッシュシーケンスを表すデータ信号を復号化するコンピュータプログラムであって、
請求項４４乃至５３のいずれか１項に記載の復号化器を制御するコンピュータ上で、前記コンピュータプログラムを動作させた場合に、請求項２８乃至４３のいずれか１項に記載の復号化方法の各工程を、該復号化器に実行させるプログラムコード手段を含むことを特徴とするコンピュータプログラム。
【請求項５８】
請求項１乃至１７のいずれか１項に記載の符号化方法によって符号化された、符号化されたタイムコンシステントな３次元メッシュシーケンスを表すことを特徴とする符号化信号。
【請求項５９】
スケーラブルな符号化を用いて、テクスチャ座標又は法線ベクトルのタイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）シーケンスを符号化する方法であって、
テクスチャ座標又は法線ベクトルのシーケンスの連続フレームを受信する工程を含み、
フレームは関連付けられた接続性（Ｋ）を伴うテクスチャ座標又は法線ベクトルの集合を含み、
前記接続性（Ｋ）は対応するテクスチャ座標又は法線ベクトルのシーケンスのすべてのフレームについて同一であり、
関連付けられた接続性（Ｋｌ）を伴うテクスチャ座標又は法線ベクトルの素集合によって表される２以上の空間的階層を含む多解像度表現に、テクスチャ座標又は法線ベクトルのシーケンスを分解する工程と、
符号化器を用いて前記階層に含まれるテクスチャ座標又は法線ベクトルを符号化する工程とを含むことを特徴とする符号化方法。
【請求項６０】
請求項２乃至１７のいずれか１項に記載のタイムコンシステントなシーケンスの符号化の特徴をさらに備えていることを特徴とする、請求項５９に記載の符号化方法。
【請求項６１】
スケーラブルな符号化を用いて符号化された、テクスチャ座標又は法線ベクトルのタイムコンシステントなシーケンスを表すデータ信号を復号化する方法であって、
請求項５９に記載の符号化方法によって符号化されたデータ信号を復号化することを特徴とする復号化方法。
【請求項６２】
請求項５９又は６０に記載の符号化方法を実行するように構成されていることを特徴とする符号化器。
【請求項６３】
請求項６１に記載の復号化方法を実行するように構成されていることを特徴とする復号化器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スケーラブルな予測符号化を用いて、タイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ、時間的一貫性を有する）シーケンス、特に、３次元メッシュシーケンスを符号化する方法に関する。また、本発明は、スケーラブルな予測符号化を用いて、タイムコンシステントなシーケンス、特に、３次元メッシュシーケンスを符号化する符号化器に関する。さらに、本発明は、符号化されたタイムコンシステントなシーケンス、特に、３次元メッシュシーケンスを表すデータ信号を復号化する方法に関するとともに、符号化されたタイムコンシステントなシーケンス、特に、３次元メッシュシーケンスを表すデータ信号を復号化するための復号化器に関する。また、本発明は、対応するコンピュータプログラム、及び、対応するデータ信号に関する。
【背景技術】
【０００２】
［はじめに］
マルチメディアハードウエアは、ますます強力になり、価格も手頃となってきている。このような発展によると、３次元テレビ、没入型の（ｉｍｍｅｒｓｉｖｅ）遠隔医療又は没入型のコンピュータゲームのような時間的に変化する３次元コンテンツに基く、既存のアプリケーションの永続的な改良、或いは、新たなアプリケーションの開発が可能となる。これに関連して、時間的に変化する３次元コンテンツを効率的に圧縮することが、決定的に重要となっている。
【０００３】
インターネット、ローカルエリアネットワーク、携帯ネットワーク等のような、アクセスネットワークの範囲の広がりにより、圧縮された時間的に変化する３次元コンテンツのビットレートを、ネットワークの伝送レート及びエンドユーザ装置に適合させる必要が生じている。この要求を満たすために、本発明者らは、スケーラブルな圧縮方式を開発した。この手法によると、３次元コンテンツは一度だけ符号化すればよいのに対し、復号化は、ネットワーク及びエンドユーザ装置の能力に合せた品質で、種々の装置において行うことができる。このことは、品質を向上させつつ、階層ごとの復号化、及び、３次元コンテンツの逐次再構成を可能とする構造化された（ｓｔｒｕｃｔｕｒｅｄ）ビットストリームの創作によって達成される。
【０００４】
［関連研究］
近年、タイムコンシステントな３次元メッシュシーケンスを圧縮するためのいくつかのアプローチが提案されている。Ｋａｒｎｉ及びＧｏｔｓｍａｎ（“Ｃｏｍｐｒｅｓｓｉｏｎ  ｏｆ  ｓｏｆｔ−ｂｏｄｙ  ａｎｉｍａｔｉｏｎ  ｓｅｑｕｅｎｃｅｓ”，Ｃｏｍｐｕｔｅｒ＆Ｇｒａｐｈｉｃｓ，Ｖｏｌ．２８，Ｎｏ．１，２００４）、並びに、Ｓａｔｔｌｅｒ等（“Ｓｉｍｐｌｅ  ａｎｄ  ｅｆｆｉｃｉｅｎｔ  ｃｏｍｐｒｅｓｓｉｏｎ  ｏｆ  ａｎｉｍａｔｉｏｎ  ｓｅｑｕｅｎｃｅｓ”  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ／ＥＧ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｎｉｍａｔｉｏｎ，  Ｌｏｓ  Ａｎｇｅｌｅｓ，ＣＡ，ＵＳＡ，２００５）によると、主要素分析（ＰＣＡ）を用いてメッシュシーケンスを変換することにより、符号化データの量が削減される。Ｇｕｓｋｏｖ及びＫｈｏｄａｋｏｖｓｋｙ（“Ｗａｖｅｌｅｔ  ｃｏｍｐｒｅｓｓｉｏｎ  ｏｆ  ｐａｒａｍｅｔｒｉｃａｌｌｙ  ｃｏｈｅｒｅｎｔ  ｍｅｓｈ  ｓｅｑｕｅｎｃｅｓ”，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ／ＥＧ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｎｉｍａｔｉｏｎ，Ｇｒｅｎｏｂｌｅ，Ｆｒａｎｃｅ，２００４）、並びに、Ｐａｙａｎ及びＡｎｔｏｎｉｏｎｉ（“Ｔｅｍｐｏｒａｌ  ｗａｖｅｌｅｔ−ｂａｓｅｄ  ｇｅｏｍｅｔｒｙ  ｃｏｄｅｒ  ｆｏｒ  ３Ｄ  ａｎｉｍａｔｉｏｎｓ”，Ｃｏｍｐｕｔｅｒ＆Ｇｒａｐｈｉｃｓ，Ｖｏｌ．３１，Ｎｐ．１，２００７）は、圧縮のためのウエーブレットベースのアプローチを提案している。Ｇｕｓｋｏｖ及びＫｈｏｄａｋｏｖｓｋｙは、各フレームに個別にウエーブレット変換を適用し、後にウエーブレット係数間の時間的コヒーレンスを利用するのに対し、Ｐａｙａｎ及びＡｎｔｏｎｉｏｎｉは、頂点の軌跡に時間方向のウエーブレット変換を施し、エントロピー圧縮のために、モデルベースのエントロピー符号化器を使用する。Ｍｕｅｌｌｅｒ等（“Ｐｒｅｄｉｃｔｉｖｅ  ｃｏｍｐｒｅｓｓｉｏｎ  ｏｆ  ｄｙｎａｍｉｃ  ３Ｄ  ｍｅｓｈｅｓ”  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，Ｇｅｎｏｖａ，Ｉｔａｌｙ，２００５）は、八分木（ｏｃｔｒｅｅ）ベースの動きベクトルクラスタリングと各クラスタのための圧縮モードの最適な選択とを組合わせることによって、動きベクトル間のコヒーレンスを利用する、レート歪み最適化圧縮方式を提案した。最近、Ｍａｍｏｕ等（“Ａ  ｓｋｉｎｎｉｎｇ  ａｐｐｒｏａｃｈ  ｆｏｒ  ｄｙｎａｍｉｃ  ３Ｄ  ｍｅｓｈ  ｃｏｍｐｒｅｓｓｉｏｎ：Ｒｅｓｅａｒｃｈ  ａｒｔｉｃｌｅｓ，“Ｃｏｍｐｕｔｅｒ  Ａｎｉｍａｔｉｏｎ  ａｎｄ  Ｖｉｒｔｕａｌ  Ｗｏｒｌｄｓ”，Ｖｏｌ．１７，Ｎｏ．３−４，２００６）は、スキニングアニメーション（ｓｋｉｎｎｉｎｇ  ａｎｉｍａｔｉｏｎ）手法に基く、新規なメッシュアニメーションの圧縮手法を提案している。彼等は、予測のためにクラスタ内及びクラスタ間の依存性を利用するために、頂点クラスタリングを使用するとともに、重み付きアフィン変換を提案している。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、タイムコンシステントなシーケンス、特に、タイムコンシステントな３次元メッシュシーケンスを符号化及び復号化するための、さらなる解決策、特に、改良された解決策を提供することにある。
【課題を解決するための手段】
【０００６】
本発明によると、
タイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスを、スケーラブルな符号化を用いて符号化する方法であって、
フレームが関連付けられた接続性（Κ）を伴う頂点の集合（Ｖ）（ｓｅｔ  ｏｆ  ｖｅｒｔｉｃｅｓ（Ｖ）  ｗｉｔｈ  ａｓｓｏｃｉａｔｅｄ  ｃｏｎｎｅｃｔｉｖｉｔｙ（Ｋ））を含み、該接続性（Ｋ）が３次元メッシュシーケンスのすべてのフレームについて同一である、３次元メッシュシーケンスの連続フレームを受信する工程と、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する工程と、
符号化器を用いて前記階層に含まれる頂点を符号化する工程とを含む、符号化方法が提供される。
【０００７】
本発明の他の形態によると、
前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算し、且つ／又は、
スケーラブルな予測符号化を用いる符号化方法が提供される。
【０００８】
本発明の他の形態によると、
前記シーケンスの第１のフレームについて、前記３次元メッシュシーケンスの接続性（Ｋ）を符号化する工程と、
各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から、１の圧縮方法を選択する工程とをさらに含む、符号化方法が提供される。
【０００９】
本発明の他の形態によると、
前記３次元メッシュシーケンスを多解像度表現に分解する工程は、
ｎｕｍｂｅｒＯｆＤｅｃｏｍｐｏｓｅｄＬａｙｅｒｓの値を、分解の階層数（Ｌ）に設定する工程と、
前記設定された分解の階層数（Ｌ）を符号化する工程と、
１つの中間の頂点を共有する３角形の集合を含む１以上のパッチを選択する工程とを含み、
前記中間の頂点（ｍｉｄｄｌｅ  ｖｅｒｔｅｘ）は所定の数以下、特に、６以下の価数（ｖａｌｅｎｃｅ）を有し、
前記価数は前記中間の頂点に直接隣接する頂点の数によって定義され、
前記１以上の選択されたパッチの中間の頂点を削除し、関連付けられた接続性（ＫＬ）を伴う該削除された中間の頂点によって定義される分解された階層（ＶＬ）を生成する工程と、
残りの頂点の集合に関連する単純化された接続性を決定する工程と、
１以上のパッチを選択する工程、中間の頂点を削除する工程、及び、単純化された接続性を決定する工程を、残りの単純化された接続性を伴う頂点の集合について、設定された階層数よりも２少ない反復回数（Ｌ−２）に亘って、繰り返すことにより、関連付けられた接続性（ＫＬ−１，…，Ｋ２）を伴う分解された階層（ＶＬ−１，…，Ｖ２）を生成する工程と、
残りの関連付けられた接続性Ｋ１を伴う頂点の集合（Ｖ１）を基底階層（ｂａｓｅ  ｌａｙｅｒ）として定義する工程とを含む、符号化方法が提供される。
【００１０】
本発明の他の形態によると、
前記残りの頂点の集合に関連する単純化された接続性を決定する工程は、削除された頂点の以前の最近接（１−ｒｉｎｇ  ｎｅｉｇｈｂｏｒｈｏｏｄ）の頂点を３角形分割する工程を含み、
前記最近接（頂点）は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、該３角形分割及び前記階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数（ｖａｌｅｎｃｅ）に対する、削除された頂点の最近接の頂点の価数の平均絶対偏差に基いて選択される、符号化方法が提供される。
【００１１】
本発明の他の形態によると、
予測符号化器を用いて前記階層に含まれる頂点を符号化する工程は、
選択された各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から１の圧縮方法を選択する工程と、
Ｉ−フレーム予測子、Ｐ−フレーム予測子、又は、Ｂ−フレーム予測子をそれぞれ用いて、予測誤差を生成する工程とを含む、符号化方法が提供される。
【００１２】
本発明の他の形態によると、
現フレームの現頂点についてのＩ−フレーム圧縮は、該現フレームの該現頂点の符号化済みの最近接（頂点）の位置の平均としてＩ−フレーム予測子を計算することを含む、符号化方法が提供される。
【００１３】
本発明の他の形態によると、現フレームの現頂点についてのＰ−フレーム圧縮は、符号化済みのフレームを参照フレームとみなし、上記形態に従って計算された現フレームの現頂点のＩ−フレーム予測子と、参照フレームにおける現頂点の位置と該上記形態に従って計算された該参照フレームの現頂点のＩ−フレーム予測子との間の差とを足し合わせることによって、Ｐ−フレーム予測子を計算することを含む、符号化方法が提供される。
【００１４】
本発明の他の形態によると、
前記差は、回転行列（Ｒｏｔａｔｉｏｎ  Ｍａｔｒｉｘ）（Ａ）と掛け合わされる、符号化方法が提供される。
【００１５】
本発明の他の形態によると、現フレームの現頂点についてのＢ−フレーム圧縮は、符号化済みの２つのフレームをそれぞれ第１の参照フレーム及び第２の参照フレームとみなし、該第１の参照フレームを考慮した請求項８又は９によるＰ−フレーム予測子と、該第２の参照フレームを考慮した請求項８又は９によるＰ−フレーム予測子との平均、特に、重み付き平均を計算することによって、Ｂ−フレーム予測子を計算することを含む、符号化方法が提供される。
【００１６】
本発明の他の形態によると、
前記選択された予測子を示す情報を符号化し、それによって、予測子は、フレームごと又は階層ごとに、特に、所定の個数のビットを用いて符号化される、符号化方法が提供される。
【００１７】
本発明の他の形態によると、
予測符号化器を用いて前記階層に含まれる頂点を符号化する工程は、
前記予測誤差を量子化する工程と、
前記量子化された予測誤差を符号化する工程と、をさらに含む、符号化方法が提供される。
【００１８】
本発明の他の形態によると、前記予測誤差は、量子化ビンのサイズ（Δ）として、特に、ｃｏｏｒｄｓＱｕａｎｔｉｚａｔｉｏｂｎＳｔｅｐの値を用いて、均一に量子化される、符号化方法が提供される。
【００１９】
本発明の他の形態によると、
前記量子化された予測誤差の各成分は、エントロピー符号化を用いて個別に符号化される、符号化方法が提供される。
【００２０】
本発明の他の形態によると、所定の範囲、特に、−３から＋３までの所定の範囲の整数値に含まれる値に対して算術符号化を用い、該所定の範囲の整数値以外の値に対してゴロム（Ｇｏｌｏｍｂ）符号を用いて、前記量子化された予測誤差の成分をエントロピー符号化する、符号化方法が提供される。
【００２１】
本発明の他の形態によると、
各階層について個別の算術符号化器を用い、
各算術符号化器は、符号化済みのフレームから得られた量子化予測誤差の統計的分布を用いるように構成されている、符号化方法が提供される。
【００２２】
本発明の他の形態によると、
予測精度を向上させるために最適な参照フレームを決定し、
決定した参照フレームを識別する付加情報を符号化し、且つ／又は、参照フレーム番号を、現フレームのフレーム番号に対するオフセットをそれぞれ表すｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０、又は、ｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０及びｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ１の値として、参照フレーム番号を現フレームにおいて符号化する、符号化方法が提供される。
【００２３】
本発明によると、
タイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスをスケーラブルな予測符号化を用いて符号化する符号化器であって、
フレームが関連付けられた接続性（ｃｏｎｎｅｃｔｉｖｉｔｙ）（Ｋ）を伴う頂点の集合（Ｖ）を含み、該接続性（Ｋ）が３次元メッシュシーケンスのすべてのフレームについて同一である、３次元メッシュシーケンスの連続フレームを受信する受信手段と、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する分解手段と、
予測符号化器を用いて前記階層に含まれる頂点を符号化する符号化手段とを備えている、符号化器が提供される。
【００２４】
本発明の他の形態によると、
前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算する、符号化器が提供される。
【００２５】
本発明の他の形態によると、
前記シーケンスの第１のフレームについて、前記３次元メッシュシーケンスの接続性（Ｋ）を符号化する接続性符号化手段と、
各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から、１の圧縮法方法を選択する選択手段とをさらに備えている、符号化器が提供される。
【００２６】
本発明の他の形態によると、
削除された頂点の以前の最近接（１−ｒｉｎｇ  ｎｅｉｇｈｂｏｒｈｏｏｄ）の頂点を３角形分割する３角形分割手段をさらに備え、
前記最近接は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、削除された頂点の最近接の頂点の価数の、該３角形分割及び現在の階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数からの平均絶対偏差に基いて選択され、
前記価数は、頂点に直接隣接する頂点の数によって定義される、符号化器が提供される。
【００２７】
本発明の他の形態によると、
各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群から１の圧縮方法を選択する選択手段をさらに備え、
前記符号化器は、Ｉ−フレーム予測子、Ｐ−フレーム予測子、又は、Ｂ−フレーム予測子をそれぞれ用いて、予測誤差を生成するように構成されている、符号化器が提供される。
【００２８】
本発明の他の形態によると、
前記選択された予測子を特定して符号化する情報符号化手段を備え、それによって、該予測子は、フレームごと又は階層ごとに、特に、所定の個数のビットを用いて、符号化される、符号化器が提供される。
【００２９】
本発明の他の形態によると、
前記予測誤差を、特に、量子化ビンのサイズ（Δ）としてｃｏｏｒｄｓＱｕａｎｔｉｚａｔｉｏｎＳｔｅｐの値を用いて、量子化する量子化手段と、
前記量子化された予測誤差を符号化する誤差符号化手段、及び／又は、
所定の範囲、特に、−３から＋３までの範囲の整数値に含まれる値に対して算術符号化を用い、該所定の範囲の整数値以外の値に対してゴロム（Ｇｏｌｏｍｂ）符号を用いて、前記量子化された予測誤差の成分を符号化するエントロピー符号化手段と、を備えている、符号化器が提供される。
【００３０】
本発明の他の形態によると、
決定した参照フレームを識別する付加情報を符号化する付加情報符号化手段を有し、特に、該付加情報符号化手段は、現フレームのフレーム番号に対するオフセットをそれぞれ表すｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０、又は、ｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０及びｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ１の値として、参照フレーム番号を現フレームにおいて符号化するように構成されている、符号化器が提供される。
【００３１】
また、本発明によると、
タイムコンシステントな３次元メッシュシーケンスを符号化する符号化器であって、
特に、請求項１乃至１７のいずれか１項に記載の符号化方法を実施する際に、
一のフレームは頂点の集合（Ｖ）及びその接続性（Ｋ）を含み、該接続性（Ｋ）は３次元メッシュシーケンスのすべてのフレームについて同一である、３次元メッシュシーケンスの連続フレームを受信する３次元メッシュシーケンスブロックと、
前記シーケンスの第１フレームに対する３次元メッシュシーケンスの接続性（Ｋ）を符号化する接続性符号化ブロックと、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する階層設計ブロックとを備え、
前記分解は前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から計算され、
各フレームについて、Ｉ−フレーム圧縮、Ｐ−フレーム圧縮及びＢ−フレーム圧縮を含む一群の圧縮方法から、１の圧縮方法を選択するフレーム順序制御ブロックと、
予測符号化器を用いて、前記階層に含まれる頂点を符号化するＤＰＣＭ符号化ブロックと、
前記符号化を制御するとともに、ＤＰＣＭ符号化ブロックにおける頂点を予測する予測子を選択する階層圧縮制御ブロックと、を備えている符号化器が提供される。
【００３２】
さらに、本発明によると、上記形態のいずれかによる符号化方法を実行するように構成されている、タイムコンシステントな３次元メッシュシーケンスを符号化する符号化器が提供される。
【００３３】
本発明によると、
各フレームが関連付けられた接続性（Ｋ）を伴う頂点の集合（Ｖ）を含み、該接続性（Ｋ）がスケーラブルな符号化によって符号化される３次元メッシュシーケンスのすべてのフレームについて同一である、複数のフレームによって定義される、符号化されたタイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスを表すデータ信号を復号化する方法であって、
前記データ信号を受信する工程と、
前記３次元メッシュシーケンスの接続性（Ｋ）を復号化する工程と、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンス又はその接続性を分解する工程と、
復号化器を用いて前記複数の階層に含まれる頂点を復号化する工程とを含む、復号化方法が提供される。
【００３４】
本発明の他の形態によると、
前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算し、且つ／又は、
スケーラブルな予測的復号化を用いる、復号化方法が提供される。
【００３５】
本発明の他の形態によると、
各フレーム、及び／又は、各階層について、符号化器によって用いられる圧縮方法を示す情報を復号化し、特に、参照フレームの番号を表す参照フレーム番号を復号化する工程をさらに含む、復号化方法が提供される。
【００３６】
本発明の他の形態によると、
使用する圧縮法を、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から選択する、復号化方法が提供される。
【００３７】
本発明の他の形態によると、
前記３次元メッシュシーケンスを多解像度表現に分解する工程は、
符号化器から受信した、階層数（Ｌ）を示すｎｕｍｂｅｒＯｆＤｅｃｏｍｐｏｓｅｄＬａｙｅｒｓの値を復号化する工程と、
１以上のパッチを選択し、且つ／又は、１つの中間の頂点を共有する３角形の集合を含む１以上のパッチを識別する情報を復号化する工程とを含み、
前記中間の頂点は所定の数以下、特に、６以下の価数を有し、
前記価数は前記中間の頂点に直接隣接する頂点の数によって定義され、
前記１以上の選択されたパッチの中間の頂点を削除し、関連付けられた接続性（ＫＬ）を伴う該削除された中間の頂点によって定義される分解された階層（ＶＬ）を生成する工程と、
残りの頂点の集合に関連する単純化された接続性を決定する工程と、
１以上のパッチを選択する工程、中間の頂点を削除する工程、及び、単純化された接続性を決定する工程を、残りの単純化された接続性を伴う頂点の集合について、復号化された階層数よりも２少ない反復回数（Ｌ−２）に亘って、繰り返すことにより、関連付けられた接続性（ＫＬ−１，…，Ｋ２）を伴う分解された階層（ＶＬ−１，…，Ｖ２）を生成する工程と、
残りの関連付けられた接続性Ｋ１を伴う頂点の集合（Ｖ１）を基底階層（ｂａｓｅ  ｌａｙｅｒ）として定義する工程とを含む、復号化方法が提供される。
【００３８】
本発明の他の形態によると、
前記残りの頂点の集合に関連する単純化された接続性を決定する工程は、削除された頂点の以前の最近接の頂点を３角形分割する工程を含み、
前記際近接（頂点）は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、該３角形分割及び前記階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数に対する、削除された頂点の最近接の頂点の価数の平均絶対偏差に基いて選択される、復号化方法が提供される。
【００３９】
本発明の他の形態によると、
指定された圧縮方法に従って予測子を決定する工程と、
予測誤差を復号化する工程と、
特定された予測子及び復号化された予測誤差に基いて、対応する頂点の予測値、及び／又は、位置データを計算する工程とを含み、
これらの工程は、好ましくは各階層において行われる、復号化方法が提供される。
【００４０】
本発明の他の形態によると、基底階層の頂点の位置データを復号化する工程を含む、復号化方法が提供される。
【００４１】
本発明の他の形態によると、現フレームの現頂点についてＩ−フレームを圧縮する場合に、該現フレームの該現頂点の復号化済みの最近接（頂点）の位置の平均としてＩ−フレーム予測子を計算することを含む、復号化方法が提供される。
【００４２】
本発明の他の形態によると、現フレームの現頂点のＰ−フレームを圧縮する場合に、復号化済みのフレームを参照フレームとみなし、上記形態に従って計算された現フレームの現頂点のＩ−フレーム予測子と、参照フレームの現頂点の位置と該上記形態に従って計算された該参照フレームの現頂点のＩ−フレーム予測子との間の差とを足し合わせることによって、Ｐ−フレーム予測子を計算することを含む、復号化方法が提供される。
【００４３】
本発明の他の形態によると、前記差は、回転行列（Ｒｏｔａｔｉｏｎ  Ｍａｔｒｉｘ）（Ａ）と掛け合わされる、復号化方法が提供される。
【００４４】
本発明の他の形態によると、現フレームの現頂点のＢ−フレームを圧縮する場合に、符号化済みの２つのフレームをそれぞれ第１の参照フレーム及び第２の参照フレームとみなし、該第１の参照フレームを考慮した対応する上記形態のいずれかによるＰ−フレーム予測子と、該第２の参照フレームを考慮した該上記形態のいずれかによるＰ−フレーム予測子との平均、特に、重み付き平均を計算することによって、Ｂ−フレーム予測子を計算することを含む、復号化方法が提供される。
【００４５】
本発明の他の形態によると、前記選択された予測子を示す情報は、フレームごと又は階層ごとに、特に、所定の個数のビットを用いて復号化される、復号化方法が提供される。
【００４６】
本発明の他の形態によると、
エントロピー符号化を用いる、復号化方法が提供される。
【００４７】
本発明の他の形態によると、
前記エントロピー復号化は、所定の範囲、特に、−３から＋３までの所定の範囲の整数地に含まれる値に対して算術符号化を用い、該所定の範囲の整数値以外の値に対してゴロム符号を用い、特に、各階層について個別の算術符号化器を用い、
各算術復号化器は、特に、復号化済みのフレームから得られた量子化ビンのサイズ（Δ）として、ｃｏｏｒｄｓＱｕａｎｔｉｚａｔｉｏｎＳｔｅｐの値を用いて量子化された、量子化予測誤差の統計的分布を用いるように構成されている、復号化方法が提供される。
【００４８】
本発明の他の形態によると、符号化方法に関する上記形態のいずれかに記載の符号化方法により、且つ／又は、符号化器に関する上記形態のいずれかに記載の符号化器により、符号化されたデータ信号を復号化するように構成されている、復号化方法が提供される。
【００４９】
本発明によると、
各フレームが関連付けられた接続性（Ｋ）を伴う頂点の集合（Ｖ）を含み、該接続性（Ｋ）がスケーラブルな予測符号化を用いて符号化される３次元メッシュシーケンスのすべてのフレームについて同一である、複数のフレームによって定義される、符号化されたタイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスを表すデータ信号を復号化する復号化器であって、
前記データ信号を受信する受信手段と、
前記３次元メッシュシーケンスの接続性（Ｋ）を復号化する復号化手段と、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する分解手段と、
予測復号化器を用いて前記階層に含まれる頂点を復号化する手段と、を備えている、復号化器が提供される。
【００５０】
本発明の他の形態によると、前記分解手段は、前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算するように構成されていることを特徴とする、請求項４４に記載の復号化器が提供される。
【００５１】
本発明の他の形態によると、各フレームについて、符号化器によって用いられる圧縮方法を示す情報を復号化する復号化手段を備えている、復号化器が提供される。
【００５２】
本発明の他の形態によると、使用する圧縮方法を、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から選択する、復号化器が提供される。
【００５３】
本発明の他の形態によると、
前記３次元メッシュシーケンスを多解像度表現に分解する分解手段は、
符号化器から受信した、階層数（Ｌ）を示すｎｕｍｂｅｒＯｆＤｅｃｏｍｐｏｓｅｄＬａｙｅｒｓの値を復号化する工程と、
１つの中間の頂点を共有する３角形の集合を含む１以上のパッチ選択する工程とを含み、
前記中間の頂点は所定の数以下、特に、６以下の価数を有し、
前記価数は前記中間の頂点に直接隣接する頂点の数によって定義され、
前記１以上の選択されたパッチの中間の頂点を削除し、関連付けられた接続性（ＫＬ）を伴う該削除された中間の頂点によって定義される分解された階層（ＶＬ）を生成する工程と、
残りの頂点の集合に関連する単純化された接続性を決定する工程と、
１以上のパッチを選択する工程、中間の頂点を削除する工程、及び、単純化された接続性を決定する工程を、残りの単純化された接続性を伴う頂点の集合について、階層数よりも２少ない反復回数（Ｌ−２）に亘って、繰り返すことにより、関連付けられた接続性（ＫＬ−１，…，Ｋ２）を伴う分解された階層（ＶＬ−１，…，Ｖ２）を生成する工程と、
残りの関連付けられた接続性Ｋ１を伴う頂点の集合（Ｖ１）を基底階層（ｂａｓｅ  ｌａｙｅｒ）として定義する工程とを実行するように構成されている、復号化器が提供される。
【００５４】
本発明の他の形態によると、
前記復号化器は、削除された頂点の以前の最近接の頂点を３角形分割する工程を実行することによって、残りの頂点の集合に関連する単純化された接続性を決定するように構成され、
前記際近接（頂点）は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、該３角形分割及び前記階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数に対する、削除された頂点の最近接の頂点の価数の平均絶対偏差に基いて選択される、復号化器が提供される。
【００５５】
本発明の他の形態によると、
指定された圧縮法に従って予測子を決定する予測子決定手段を備えていることにより、
前記復号化器は、予測誤差を復号化するとともに、特定された予測子及び復号化された予測誤差に基いて、対応する頂点の位置データを計算するように構成されている、復号化器が提供される。
【００５６】
本発明の他の形態によると、復号化のためのエントロピー復号化手段を備えている、復号化器が提供される。
【００５７】
本発明の他の形態によると、
前記エントロピー復号化手段は、所定の範囲、特に、−３から＋３までの所定の範囲の整数地に含まれる値に対して算術符号化を用い、該所定の範囲の整数値以外の値に対してゴロム符号を用い、特に、各階層について個別の算術符号化器を用い、
各算術復号化器は、特に、復号化済みのフレームから得られた量子化ビンのサイズ（Δ）として、ｃｏｏｒｄｓＱｕａｎｔｉｚａｔｉｏｎＳｔｅｐの値を用いて量子化された、量子化予測誤差の統計的分布を用いるように構成されている、復号化器が提供される。
【００５８】
本発明によると、
タイムコンシステントな３次元メッシュシーケンスを表すデータ信号を復号化する、特に、請求項４４乃至５２のいずれか１項に記載の復号化器であって、
前記３次元メッシュシーケンスの符号化された接続性（Ｋ）を復号化するとともに、３次元メッシュシーケンスブロックに該接続性（Ｋ）を保存する接続性復号化ブロックと、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する階層設計ブロックとを備え、
前記分解は前記３次元メッシュシーケンス接続性（Ｋ）のみから計算され、
各フレームについて、圧縮方法を制御する制御手段と、
予測復号化器を用いて、前記階層に含まれる頂点を復号化するＤＰＣＭ復号化ブロックと、
前記復号化を制御するとともに、前記ＤＰＣＭ復号化ブロックにおいて頂点を予測するための予測子を選択する階層圧縮制御ブロックとを備えている、復号化器が提供される。
【００５９】
本発明の他の形態によると、各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から、１の圧縮法を選択するフレーム順序制御ブロックとして、前記制御手段が設計されている、復号化器が提供される。
【００６０】
本発明の他の形態によると、
復号化器は、復号化方法に関する上記形態のいずれかに記載の復号化方法を実行するように構成され、
符号化方法に関する上記形態のいずれかに記載の符号化方法によって符号化されたデータ信号を復号化し、且つ／又は、
符号化器に関する上記形態のいずれかに記載の符号化器によって符号化されたデータ信号を復号化する、復号化器が提供される。
【００６１】
本発明によると、
タイムコンシステントな３次元メッシュシーケンスを符号化するコンピュータプログラムであって、
符号化器を制御するコンピュータ上で、前記コンピュータプログラムを動作させた場合に、本発明に係る符号化方法の各工程を、該符号化器に実行させるプログラムコード手段を含む、コンピュータプログラムが提供される。
【００６２】
本発明によると、
符号化されたタイムコンシステントな３次元メッシュシーケンスを表すデータ信号を復号化するコンピュータプログラムであって、
復号化器を制御するコンピュータ上で、前記コンピュータプログラムを動作させた場合に、本発明に係る復号化方法の各工程を、該復号化器に実行させるプログラムコード手段を含む、コンピュータプログラムが提供される。
【００６３】
本発明によると、本発明に係る符号化方法によって符号化された、符号化されたタイムコンシステントな３次元メッシュシーケンスを表す符号化信号が提供される。
【００６４】
本発明によると、
スケーラブルな符号化を用いて、テクスチャ座標又は法線ベクトルのタイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）シーケンスを符号化する方法であって、
テクスチャ座標又は法線ベクトルのシーケンスの連続フレームを受信する工程を含み、
フレームは関連付けられた接続性（Ｋ）を伴うテクスチャ座標又は法線ベクトルの集合を含み、
前記接続性（Ｋ）は対応するテクスチャ座標又は法線ベクトルのシーケンスのすべてのフレームについて同一であり、
関連付けられた接続性（Ｋｌ）を伴うテクスチャ座標又は法線ベクトルの素集合によって表される２以上の空間的階層を含む多解像度表現に、テクスチャ座標又は法線ベクトルのシーケンスを分解する工程と、
符号化器を用いて前記階層に含まれるテクスチャ座標又は法線ベクトルを符号化する工程とを含む、符号化方法が提供される。
【００６５】
本発明の他の形態によると、
テクスチャ座標又は法線ベクトルのタイムコンシステントなシーケンスを符号化する方法であって、
タイムコンシステントな３次元メッシュシーケンスを符号化する符号化方法に関する上記記載による、タイムコンシステントなシーケンスの符号化の特徴を備えている、符号化方法が提供される。
【００６６】
本発明によると、
スケーラブルな符号化を用いて符号化された、テクスチャ座標又は法線ベクトルのタイムコンシステントなシーケンスを表すデータ信号を復号化する方法であって、
タイムコンシステントな３次元メッシュシーケンスを符号化する符号化方法に関する上記記載による方法に従って符号化されたデータ信号を復号化する、復号化方法が提供される。
【００６７】
本発明によると、本発明に係る符号化方法を実行するように構成されている、テクスチャ座標又は法線ベクトルのタイムコンシステントなシーケンスを符号化する符号化器が提供される。
【００６８】
本発明によると、本発明に係る復号化方法を実行するように構成されている、テクスチャ座標又は法線ベクトルの、符号化されたタイムコンシステントなシーケンスを表すデータ信号を復号化する、復号化器が提供される。
【００６９】
共通して、用語ｎｕｍｂｅｒＯｆＤｅｃｏｍｐｏｓｅｄＬａｙｅｒｓは、分解のための階層数（Ｌ）を表すために用いられ、用語ｃｏｏｒｄｓＱｕａｎｔｉｚａｔｉｏｎＳｔｅｐは、量子化ビンのサイズを表すために用いられ、用語ｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０は、Ｐ−フレームの参照フレーム番号オフセットを表すために用いられ、用語ｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ０及びｒｅｆＦｒａｍｅＮｕｍｂｅｒＯｆｆｓｅｔ１は、Ｂ−フレームの参照フレーム番号オフセットを表すために用いられる。
【図面の簡単な説明】
【００７０】
本発明のこれらの視点及び他の視点は、以下において次の図面を参照して記載される実施態様によって明らかとなるとともに、これらを参照することによって説明される。
【図１】２つのフレームの３つの階層への分解を示す。
【図２】タイムコンシステントな３次元メッシュシーケンスに対するスケーラブルな符号化器のブロック図を示す。
【図３】頂点位置に対するＤＰＣＭ符号化器のブロック図を示す。
【図４】階層的なＢ−フレームの予測順序を示す。
【図５】タイムコンシステントな３次元メッシュシーケンスに対するスケーラブルな復号化器のブロック図を示す。
【図６】頂点位置に対するＤＰＣＭ復号化器のブロック図を示す。
【図７】パッチベースの頂点除去を示す。図７ａは中間の頂点ｗｋを有する自由度６のパッチ、図７ｂはｗｋの削除後のパッチ、図７ｃは再３角形分割されたパッチを示す。
【図８】メッシュ接続性の自由度≦６のパッチへの分解を示す。
【図９】ｄ＝４、５、６について、可能な３角形分割Ｔｄを示す。
【図１０】フレームｆｒ及びｆにおける
【数１】
2010527523.tif 000003
及び近傍頂点
【数２】
2010527523.tif 000004
の位置に基づく、階層ｌにおける位置
【数３】
2010527523.tif 000005
のP−フレーム予測を示す。
【図１１】フレームｆｒ及びｆにおける
【数４】
2010527523.tif 000006
及び近傍頂点
【数５】
2010527523.tif 000007
の位置に基づく、階層ｌにおける位置
【数６】
2010527523.tif 000008
のP−フレーム予測を示す。
【図１２】ｌ＝８階層を用いて符号化されたシーケンス「Ｃｈｉｃｋｅｎ」を示す。
【図１３】ｌ＝６階層を用いて符号化したシーケンス「Ｃｏｗ」を示す。
【発明を実施するための形態】
【００７１】
［スケーラブルな圧縮］
一般的な形態によると、時間的に変化する３次元コンテンツは、フレームと呼ばれる３次元メッシュのシーケンスによって表される。各フレームは、２つの型のデータ、すなわち、接続性（ｃｏｎｎｅｃｔｉｖｉｔｙ）と、ジオメトリ（ｇｅｏｍｅｔｒｙ）、すなわち、３次元の頂点位置とから成る。ここでは、タイムコンシステントな（ｔｉｍｅ  ｃｏｎｓｉｓｔｅｎｔ、時間的一貫性を有する）接続性を備えたフレームを扱うものとし、すべてのフレームは、同一の接続性を有するものとする。接続性は、Ｔｏｕｍａ及びＧｏｔｓｍａｎ（“Ｔｒｉａｎｇｌｅ  ｍｅｓｈ  ｃｏｍｐｒｅｓｓｉｏｎ”，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｇｒａｐｈｉｃｓ  Ｉｎｔｅｒｆａｃｅ  Ｃｏｎｆｅｒｅｎｃｅ，Ｖａｎｃｏｕｖｅｒ，Ｃａｎａｄａ，１９９８）のアプローチを用いて、符号化過程の最初に圧縮される。したがって、接続性は、圧縮過程の最初から、頂点位置を圧縮するために、符号化器及び復号化器によって利用することができる。任意の他の接続性圧縮アルゴリズムを用いて、接続性を符号化するようにしてもよい。接続性は一度だけ符号化されることから、符号化されたメッシュシーケンスの大半は、符号化された頂点位置から成る。
【００７２】
この節では、スケーラブルな符号化器及び復号化器の概要を示し、主な構成要素については、後に詳細に説明する。まず、いくつかの表記上の取り決めを導入する。
【００７３】
［表記法］
１フレーム当りＶ個の頂点を有するＦ個のフレームと接続性Ｋとから成る、タイムコンシステントな３次元メッシュシーケンスが入力されるものとする。メッシュの接続性Ｋにおけるノードに関する頂点の表記ν∈Ｋを、これに関連する、Ｒ３における頂点位置と区別するものとする。一般に、特定の頂点νの頂点位置は、フレームｆ＝１，…，Ｆに依存して変化するため、フレームｆにおける頂点νの頂点位置をｐνｆによって表す。
【００７４】
ここで、接続性Ｋは、すべての隣接情報を含む、抽象的単体的複体（ａｂｓｔｒａｃｔ  ｓｉｍｐｌｉｃａｌ  ｃｏｍｐｌｅｘ）によって表される（Ｌｅｅ  ｅｔ  ａｌ．，  ｉｎ  “Ｍａｐｓ：  Ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ  ａｄａｐｔｉｖｅ  ｐａｒａｍｅｔｒｉｚａｔｉｏｎ  ｏｆ  ｓｕｒｆａｃｅｓ，”  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  ＳＩＧＧＲＡＰＨ，Ｏｒｌａｎｄｏ，ＦＬ，ＵＳＡ，１９９８）。これは、頂点インデックスの集合｛１，・・・，Ｖ｝の部分集合から成る。部分集合には、３つの型、すなわち、頂点（ｖｅｒｔｅｘ）ν＝｛ｉ｝∈Ｋと、辺（ｅｄｇｅ）ｅ＝｛ｉ，ｊ｝∈Ｋと、面（ｆａｃｅ）ｔ＝｛ｉ，ｊ、ｋ｝∈Ｋとがある。したがって、｛ｉ，ｊ｝∈Ｋであるならば、２つの頂点｛ｉ｝と｛ｊ｝は隣り合っている。接続性Ｋに対する頂点ν＝｛ｉ｝の最近接頂点（１−ｒｉｎｇ  ｎｅｉｇｈｂｏｒｈｏｏｄ）を、
ＮＫ（ν）＝｛｛ｊ｝∈Ｋ｜｛ｉ，ｊ｝∈Ｋ｝
と表す。
【００７５】
すべての頂点の集合をＶ＝｛｛ｉ｝∈Ｋ｝と表す。図１を参照すると、∪ｌ＝１ＬＶｌ＝Ｖの性質を有する、１≦ｌ≦Ｌに対する頂点Ｖｌの素集合を、階層という。∪ｋ＝１ｌＶｋ＝Ｋｌ∩Ｖｋを満たすＫｌによって表される接続性を、各階層Ｖ１に関連付ける。すなわち、Ｋｌは、最初のｌ階層に含まれるすべての頂点の隣接情報を記述する接続性である。図１は、３次元メッシュシーケンスの２つのフレームｆ＝０及びｆ＝２８０を、３つの階層Ｖ１，Ｋ１，Ｖ１∪Ｖ２，Ｋ２及びＶ１∪Ｖ２∪Ｖ３，Ｋ３に分解する様子を示す。
【００７６】
［符号化器の概要］
本節では、符号化器及び復号化器の構成要素の概要を提示し、これらの間における主要なデータフローについて説明する。
【００７７】
符号化器（ｃｏｄｅｒ）は、予測符合化パラダイムに従って頂点位置を符号化し、スケーラビリテイを保証する。符号化器をその構成要素とともに記載したブロック図が、図２に示されている。符号化器（ｃｏｄｅｒ）、すなわち、符号化器（ｅｎｃｏｄｅｒ）は、図２においてＳＥＮＣとする。符号化器は、１フレーム当りＶ個の頂点を有するＦ個のフレームと接続性（ｃｏｎｎｅｃｔｉｖｉｔｙ）Ｋとから成る、タイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュのシーケンスを入力とする。タイムコンシステントな３次元メッシュのシーケンスは、図２において３ＤＭＳとする。まず、接続性（ｃｏｎｎｅｃｔｉｖｉｔｙ）Ｋを符号化する。接続性は、図２においてＣＥＮＣと表された、接続性符号化器（Ｃｏｎｎｅｃｔｉｖｉｔｙ  Ｅｎｃｏｄｅｒ）によって符号化される。接続性符号化器Ｃｏｎｎｅｃｔｉｖｉｔｙ  Ｅｎｃｏｄｅｒの出力は、符号化された接続性であり、図２においてＥＣとする。次に、構成要素である階層設計部（Ｌａｙｅｒ  Ｄｅｓｉｇｎｅｒ）は、接続性Ｋｌを伴う階層Ｖｌを決定するために、接続性Ｋを用いる。階層設計部（Ｌａｙｅｒ  Ｄｅｓｉｇｎｅｒ）は、図２においてＬＤとする。
【００７８】
符号化プロセス全体は、フレーム順序制御部（Ｆｒａｍｅ  Ｏｒｄｅｒ  Ｃｏｎｔｒｏｌｌｅｒ）によって制御される。フレーム順序制御部は、図２においてＦＯＣとする。各フレームは、ｆ＝１、２、３、・・・のように順に表示されるが、フレーム間の圧縮についての依存性をより良く利用することを可能にする他のフレーム順序がある場合には、表示の順に圧縮する必要はない。フレーム順序制御部は、いずれの順序でフレームを圧縮するか、各フレームに対していずれの型の圧縮（Ｉ−フレーム圧縮、Ｐ−フレーム圧縮及びＢ−フレーム圧縮）を施すか、及び、参照フレームと称される、符号化済みのフレームの内のいずれのフレームを予測圧縮のために使用するか、を決定する。決定した参照フレームは、図２においてＲＦとする。Ｉ−フレーム圧縮、Ｐ−フレーム圧縮及びＢ−フレーム圧縮がそれぞれ区別され、すなわち、フレーム内（Ｉ）圧縮は現フレームの符号化された頂点位置のみを圧縮のために使用し、一方向予測（Ｐ）圧縮は現フレーム及び１個（又はそれより多く）の、以前に符号化されたＩ−フレーム又はＰ−フレームを予測のための参照フレームとして使用し、双方向（Ｂ）予測圧縮は、現フレーム及び２個（又はそれより多くの）の、以前に符号化された、Ｉ−フレーム、Ｐ−フレーム又はＢ−フレームのいずれかのフレームの符号化された位置を、符号化のための参照フレームとして使用する。Ｉ−フレーム、Ｐ−フレーム及びＢ−フレームは、図２において、それぞれＩＦ、ＰＦ及びＢＦとする。
【００７９】
第１のフレームｆ＝１は、つねにＩ−フレームであるものとする。ＮＰＢを２個の引き続くＩ−フレームの間のＰ−フレーム及びＢ−フレームの数とし、ＮＢを２個の引き続くＩ−フレーム又はＰ−フレームの間のＢ−フレームの数とする。したがって、ＮＰＢ及びＮＢを特定すると、各フレームのフレーム型は明確に定義される。これにより、圧縮の順序も示唆される。例として、フレームｆの表示順序（ＤＯ）と圧縮順序（ＣＯ）についての以下の２つの順序について述べる。
１．ＮＰＢ＝Ｆ−１，ＮＢ＝０
2010527523.tif 000009
この場合、ＤＯとＣＯとは同一である。第１のフレームはＩ−フレームであり、残りのフレームはＰ−フレームである。ＣＯは、Ｐ−フレームが、つねにＩ−フレーム又はＰ−フレームである、以前の既に符号化された参照フレームｆｒ＝ｆ−１に基いて一方向に予測されることを示す。
２．ＮＰＢ＝Ｆ−１，ＮＢ＝１
2010527523.tif 000010
ＤＯとＣＯとは相異なる。第１のフレームはＩ−フレームであり、残りの奇数フレームはＰ−フレームであり、偶数フレームはＢ−フレームである。選択されたＣＯによると、２個の隣接する既に符号化済みのＰ−フレームに基いて、偶数のフレームを双方向予測することができる。例えば、フレームｆ＝４は、参照フレームｆ１ｒ＝ｆ＋１＝５、及び、ｆ２ｒ＝ｆ−１＝３に基いて予測される。
【００８０】
他のパラメータ
2010527523.tif 000011
についての圧縮順序は、図４に示すように簡単に導き出される。この図において、Ｂ−フレームに対する階層的な圧縮順序は、上から下に向けて、ダイアディック（ｄｙａｄｉｃ）サブサンプリングに基いて定義される。ある場合には、Ｂ−フレームを符号化するための参照フレームは、現Ｂ−フレームに対して時間的に前にも後にも成り得る。
【００８１】
フレームの圧縮順序を指定した後、各フレームの頂点位置を符号化する。一般性を失うことなく、フレームｆを符号化すべきものとする。図２を参照すると、まず、フレームｆのすべての頂点位置を、頂点位置記憶部（Ｖｅｒｔｅｘ  Ｌｏｃａｔｉｏｎ  Ｍｅｍｏｒｙ）に格納する。図２において、フレームｆの頂点位置はＶＬＦとし、頂点位置記憶部はＶＬＭとする。次に、階層圧縮制御部（Ｌａｙｅｒ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ）は、次の頂点の順序ｖ∈Ｖ１，…，ｖ∈Ｖｌ，…，ｖ∈ＶＬを規定して、階層設計部から情報を得る。
【００８２】
階層圧縮制御部は、図２において、ＬＣＣとする。
【００８３】
フレームｆの頂点位置ｐｖｆは、基底階層Ｖ１のすべての頂点位置から開始して、最上階層ＶＬのすべての頂点位置で終了するように、ＤＰＣＭ符号化器に導かれる。ＤＰＣＭ符号化器は、図２において、ＤＰＣＭＥＮＣとする。階層Ｖｌ内における頂点の順序は、Ｖ１及び接続性（Ｃｏｎｎｅｃｔｉｖｉｔｙ）Ｋｌを用いた決定論的アルゴリズム（ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ａｌｇｏｒｉｔｈｍ）を適用することによって規定される。階層圧縮制御部は、フレームｆに対する以前決定されたフレーム圧縮形式、すなわち、Ｉ−フレーム、Ｐ−フレーム又はＢ−フレームと、決定された参照フレームとに基づくとともに、階層Ｖ１及び接続性Ｋｌに基いて、ＤＰＣＭ符号化器においてｐｖｆを予測するための適切な予測子を選択する。次に、位置ｐｖｆは、現在の頂点位置と符号化済みの位置との間の冗長性を除いて、ＤＰＣＭ符号化器において予測的に符号化される。図３は、頂点位置に対するＤＰＣＭ符号化器（ＤＰＣＭＥＮＣとする。）のブロック図を示す。図３を参照すると、ＤＰＣＭ符号化器要素は通常のＤＰＣＭ符号化器であり、符号化すべき各位置に対する予測子を選択するための入力が付加されている。予測子は、図３においてＳＯＰとした、予測子の集合の中から選択される。頂点位置記憶部（Ｖｅｒｔｅｘ  Ｌｏｃａｔｉｏｎ  Ｍｅｍｏｒｙ）は、図３においてＶＬＭとする。図３における頂点位置記憶部は、図２における頂点位置記憶部と同一であってもよいし、これらは異なるブロックであってもよい。残差ｒｖｆは、残留する統計的依存性を除いて、エントロピー符号化される。
【００８４】
図５を参照すると、対応するスケーラブルな復号化器は、図２のスケーラブルな符号化器の接続性符号化器（Ｃｏｎｎｅｃｔｉｖｉｔｙ  Ｅｎｃｏｄｅｒ）とＤＰＣＭ符号化器を、対応する接続性復号化器（Ｃｏｎｎｅｃｔｉｖｉｔｙ  Ｄｅｃｏｄｅｒ）（Ｔｏｕｍａ  ａｎｄ  Ｇｏｔｓｍａｎ，“Ｔｒｉａｎｇｌｅ  ｍｅｓｈ  ｃｏｍｐｒｅｓｓｉｏｎ，ｉｎ  ”Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  Ｇｒａｐｈｉｃｓ  Ｉｎｔｅｒｆａｃｅ  Ｃｏｎｆｅｒｅｎｃｅ，Ｖａｎｃｏｕｖｅｒ，Ｃａｎａｄａ，１９９８）とＤＰＣＭ復号化器に、単に置き換えることによって得られる。ＤＰＣＭ復号化器のブロック図は、図６において示されている。図６において、ＤＰＣＭ復号化器をＤＰＣＭＤＥＣとし、予測子の集合をＳＯＰとし、頂点位置記憶部をＶＬＭとする。スケーラブルな符号化器の他のすべての構成要素は、スケーラブルな復号化器においても不変である。図５において、スケーラブルな復号化器が示されている。図５において、スケーラブルな復号化器をＳＤＥＣとし、接続性復号化器をＣＤＥＣとし、ＤＰＣＭ復号化器をＤＰＣＭＤＥＣとする。図５の他の参照符号は、図２において同一の参照符号によって示される構成要素又は要素に対応する構成要素又は要素を示し、すなわち、３ＤＭＳは構成要素である３次元メッシュシーケンスを示し、ＶＬＭは頂点位置記憶部を示し、ＬＤは階層設計部を示し、ＬＣＣは階層圧縮制御部を示し、ＦＯＣはフレーム順序制御部を示し、ＶＬＦはフレームｆに対する頂点位置を示し、ＲＦは参照フレームを示し、ＩＦ、ＰＦ及びＢＦはそれぞれＩ−フレーム、Ｐ−フレーム及びＢ−フレームを示す。復号化の間、第１の接続性Ｋは復号化され、構成要素である３次元メッシュシーケンスに保存される。これは、次に、階層設計部において階層Ｖｌ及び対応する接続性Ｋｌを決定するために用いられる。
【００８５】
したがって、残差ｒｖｆを入力として有し、階層圧縮制御部は、位置ｐｖｆをスケーラブルな符号化器で符号化する際に適用されたものと同じ予測子を選択する。階層圧縮制御部を、図５において、ＬＣＣとする。この予測子は、ＤＰＣＭ復号化器において復号化された位置
2010527523.tif 000012
を求めるために用いられる。最後に、階層圧縮制御部は、現在復号化されている頂点位置
2010527523.tif 000013
をフレームｆの頂点υに関連付けて、
2010527523.tif 000014
の頂点υを決定する。
【００８６】
以下の各小節において、構成要素である階層設計部の具体例について記載し、ＤＰＣＭ符号化器及びＤＰＣＭ復号化器において用いられている予測子の集合を規定し、階層圧縮制御部において用いられる、予測子を選択するためのルールを規定する。最後に、残差ｒｖｆに適用されるエントロピー符号化について説明する。
【００８７】
［階層設計部（Ｌａｙｅｒ  Ｄｅｓｉｇｎｅｒ）］
階層、すなわち、素集合Ｖｌ及びこれに関連する接続性Ｋｌは、メッシュ単純化手法を用いることによって規定される。決定論的なメッシュ単純化アルゴリズムは、メッシュの接続性Ｋのみを用いて適用される。したがって、接続性Ｋは圧縮過程の最初から復号化器側において既知であるため、Ｖｌ及びＫｌを記述するために追加的な付加情報は必要とされない。
【００８８】
このアルゴリズムにおいて用いられる基本的な単純化操作は、パッチに基いている。自由度ｄのパッチは、価数ｄの頂点を交点とする３角形の集合である。図７ａにおいて、灰色の影を付した自由度６のパッチが示されている。図７ａにおける数字５ないし７は、頂点の価数を示すものであって、参照符号ではない。採用した単純化アルゴリズムは２つの主要なステップ、すなわち、パッチの分解及び単純化から成る。
【００８９】
［パッチへの分解］
図８を参照すると、自由度≦６のパッチのみを取り込む（ｃｏｎｑｕｅｒ）、決定論的なパッチベースの領域成長横断アルゴリズム（ｒｅｇｉｏｎ−ｇｒｏｗ  ｔｒａｖｅｒｓａｌ  ａｌｇｏｒｉｔｈｍ）を使用して、まず、メッシュの接続性を複数のパッチに分解する。図８において、灰色の影を付した３角形はパッチの一部であるが、白色の３角形はそうではない。分かりやすくするために、パッチの一部である３角形は、文字ａ，ｃ又はｅも付されている。任意に選択された自由度≦６の最初の種パッチに未処理の標識を付し、ＦＩＦＯにエンキュー（ｅｎｑｕｅｕｅ）することで、分解を開始する。横断ループにおいて、最初のパッチは、ＦＩＦＯからデキュー（ｄｅｑｕｅｕｅ）される。このパッチに処理済の標識がすでに付されている場合には、これをスキップし、ループを最初から開始する。パッチが未処理であれば、処理済の標識を付し、その中間の頂点ｗｋを保存し、すべての隣接する自由度≦６のパッチをＦＩＦＯにエンキューする。ここで、隣接するパッチは、現パッチとの間で共通の辺を１つだけ有するパッチである。この手順をＦＩＦＯが空になるまで反復する。図８を参照すると、出力として、中間の頂点ｗ１，・・・、ｗｋ，・・・、ｗＭで表されるＭ個のパッチ列が得られる。後の単純化は、これらのパッチに対してのみ行われる。
【００９０】
［パッチベースの単純化］
パッチへの分解の間に得られたすべてのパッチは、処理された順に再び横断（トラバース）される。図７ａ、７ｂ、７ｃを参照すると、各パッチの中間の頂点ｗｋは除去され、残りの多角形は再び３角形分割される。図７ａにおける数字５ないし７、図７ｂにおける数字４ないし６、及び、図７ｃにおける数字６、７は頂点の価数を示すものであって、参照符号ではない。自由度ｄのパッチに対する異なる３角形分割の個数Ｔｄはｄに依存し、すなわち、Ｔ３＝１，Ｔ４＝２，Ｔ５＝５，Ｔ６＝１４個の３角形分割がある（Ｓｔｅｄｇｅｗｉｃｋ  ａｎｄ  Ｆｌａｊｏｌｅｔ，  ｉｎ  “Ａｎ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  ｔｈｅ  Ａｎａｌｙｓｉｓ  ｏｆ  Ａｌｇｏｒｉｔｈｍｓ”，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ，１９９６）。図９を参照すると、自由度ｄのパッチのすべての３角形分割の集合をＴｄ：＝｛１，…，Ｔｄ｝として定義する。図９において、Ｔ６に対する数字１ないし１４、Ｔ５に対する数字１ないし５、及び、Ｔ４に対する数字１，２は、異なる３角形分割の個数を示すものであって、参照符号ではない。
【００９１】
中間の頂点ｗｋを除去した後の自由度ｄのパッチに対して、１つの３角形分割ｔ∈Ｔｄを選択するために、尺度
2010527523.tif 000015
を適用する。これは、接続性Ｋｉについて、
2010527523.tif 000016
に含まれるすべての頂点の価数の価数６からの平均絶対偏差を測る。
2010527523.tif 000017
ここで、
2010527523.tif 000018
は、中間の頂点ｗｋを除去し、接続性Ｋｌについての３角形分割ｔを用いて残りの多角形を再度３角形分割した後の頂点υ’の価数を示す。頂点υ’の価数が３角形分割ｔに依存して変化することから、異なる３角形分割が異なる偏差を生ずることに留意されたい。パッチを再３角形分割するための３角形分割ｔとして、最小の偏差
2010527523.tif 000019
を生ずるものを選択する。この種の選択によると、全体的に、価数６からの価数の絶対偏差を削減する。これによって、通常細長い３角形を生じさせるような、大きな価数の頂点が生じるのを防ぐ。さらに、頂点の大きな価数は、多くの価数３の頂点を生じさせることがあり、これは後に正確に予測することはできない。
【００９２】
［単純化から階層へ］
単純化された接続性に対して直前の２節に記載した手順を繰り返し適用することによって、すべての頂点の集合Ｖは接続性Ｋｌを伴うＬ個の互いに素な部分集合Ｖｌに分解される。まず、Ｖにおける頂点から成る接続性ＫＬ：＝Ｋに、パッチ分解及び単純化を適用する。このようにして、ＭＬ個の頂点の集合
2010527523.tif 000020
が除去され、Ｖ＼ＶＬ中の頂点から成る単純化された接続性Ｋｌ−１が残される。この手順を単純化された接続性に回帰的に適用することによって、各ｌ＝Ｌ，・・・２について、頂点の集合
2010527523.tif 000021
と、頂点
2010527523.tif 000022
から成る単純化された接続性Ｋｌ−１が得られる。最後に、接続性Ｋｌを伴う残りの頂点の集合
2010527523.tif 000023
として、基底階層が定義される。したがって、頂点のＶへの階層化された分解、Ｌ個の階層Ｖｌにおける接続性Ｋ、ｌ＝１，…，Ｌに対するＫＬが得られる。
【００９３】
パッチベースの単純化によると、各頂点の近傍が１階層下方に位置することが保証される。すなわち、ｌ＝２，…，Ｌについての各頂点ｖ∈Ｖｌについて
2010527523.tif 000024
が得られる。
【００９４】
これは階層化された分解の基幹となる性質であり、引き続く階層の間でインターリーブ状に配置された頂点を与える。本明細書の以下の説明から明らかとなるように、この性質によると、時空間における頂点位置ｐｖｆの階層間依存性のロバストな（ｒｏｂｕｓｔ）利用が可能となる。
【００９５】
［予測子］
階層圧縮制御部によって決定された頂点の順序によると、１フレームｆ内の頂点位置は、階層ごとに符号化される。すなわち、ｖ∈Ｖｌのｐｖｆを符号化する前に、すべての
2010527523.tif 000025
のすべての位置ｐｖｆが符号化される。したがって、ｖ∈Ｖｌ，ｌ＞１で位置ｐｖｆを符号化する場合、
2010527523.tif 000026
のすべての近隣の頂点位置ｐｖ’ｆは既に符号化されている（式１参照）。この性質によって、頂点位置の全部の空間又は時間空間的な最近接（１−ｒｉｎｇ  ｎｅｉｇｈｂｏｒｈｏｏｄ）を利用する予測子の定義が可能となる。
【００９６】
現フレームｆの形式、すなわち、Ｉ−フレーム、Ｐ−フレーム又はＢ−フレームに基くとともに、参照フレームｆｒ又は参照フレームｆ１ｒ及びｆ２ｒ（これはｆがＰ−フレーム又はＢ−フレームかということに依存する。）に基き、隣接頂点の集合
2010527523.tif 000027
に依存して、適切な予測子がＤＰＣＭ符号化器において選択される。
【００９７】
便宜上、まず、２つの関数を最初に定義する。Ｐｃ（ｆ，ｖ）が、ｐｖｆを符号化する直前にＤＰＣＭ符号化器の頂点位置記憶部に格納されていた、符号化済みの頂点位置
2010527523.tif 000028
の集合を表すものとする。したがって、位置ｐｖ’ｆ’がｐｖｆの前に符号化されていれば、その符号化された相手方は、
2010527523.tif 000029
を満足する。また、
2010527523.tif 000030
がフレームｆの符号化された頂点位置
2010527523.tif 000031
の集合を表し、その対応する頂点υ’がすべて接続性Ｋｌに対して頂点υの最近接にあるものとする。頂点位置の集合
2010527523.tif 000032
、そして潜在的には
2010527523.tif 000033
又は
2010527523.tif 000034
及び
2010527523.tif 000035
が、階層圧縮制御部から入力された
2010527523.tif 000036
及び参照フレーム番号ｆｒ又はｆ１ｒ及びｆ２ｒを用いて、ＤＰＣＭ符号化器において決定される。この集合は、位置ｐｖｆの予測に用いられる符号化された頂点位置を決定する。考えているフレームｆ及び頂点υは文脈から知り得ることから、以下では、
2010527523.tif 000037
の代りに、省略された記号
2010527523.tif 000038
を使用する。
【００９８】
ここで、ＤＰＣＭ符号化器及びＤＰＣＭ復号化器において利用可能な線形予測子の集合及び非線形予測子の集合の、２つの適応予測子の集合を定義する。予測子は、現フレームｆの形式と、近傍の符号化済み頂点位置の集合
2010527523.tif 000039
とに適合化されている。以下では、一般性を失うことなく、ｖ∈Ｖｌの位置ｐｖｆを予測するものとする。
【００９９】
［線形予測子の集合］
・Ｉ−フレーム予測子
2010527523.tif 000040
予測子
2010527523.tif 000041
は、同一のフレームｆの符号化済みの最近接（頂点）の平均を計算して、ｐｖｆを予測する。ある頂点の最近接のすべての頂点位置は、ｌ＞１についてつねに符号化されることを強調しておく。これにより、予測された位置は、接続性Ｋｌに対するフレームｆの頂点υの重心に対応する。
【０１００】
・Ｐ−フレーム予測子
2010527523.tif 000042
図１０を参照すると、予測子
2010527523.tif 000043
は、符号化済み近傍頂点位置の動きベクトルの平均化に基いて、ｐｖｆを予測する。
【０１０１】
・Ｂ−フレーム予測子
2010527523.tif 000044
一方はフレームｆ１ｒ及びｆの位置を使用し、他方はフレームｆ２ｒ及びｆの位置を使用した、２つのＰ−フレーム予測の平均を、Ｂ−フレーム予測の間に計算する。
【０１０２】
したがって、位置ｐｖｆの予測のために、フレームｆの型、すなわち
2010527523.tif 000045
又は
2010527523.tif 000046
に基いて、予測子を選択する。次に、
2010527523.tif 000047
と、潜在的にはｆｒ又はｆ１ｒ及びｆ２ｒを用いて、選択された予測子によって予測のために使用される符号化頂点位置を決定する。最後に、予測された位置
2010527523.tif 000048
が得られる。
【０１０３】
これまでに示した予測子は、一次依存性を予測のために使用する線形予測子であった。以下では、ＤＰＣＭ符号化器及びＤＰＣＭ復号化器においても使用可能な、２次依存性も使用し得る、非線形予測子の集合を導入する。これらの予測子を、すでに示した線形予測子の集合の代りに使用することができる。
【０１０４】
［非線形予測子の集合］
・Ｉ−フレーム予測子
2010527523.tif 000049
2010527523.tif 000050
は、実際に線形予測子であるが、完全を期して、下付き添字ｎｌ（非線形）を付して表す。
【０１０５】
・Ｐ−フレーム予測子
2010527523.tif 000051
及び
2010527523.tif 000052
に応じて計算した正規直交行列をＡ（ｆ，ｖ，ｆｒ）∈Ｒ３ｘ３とする。また、
2010527523.tif 000053
を定義する。
【０１０６】
図１１は、
2010527523.tif 000054
の計算を示す。予測位置
2010527523.tif 000055
及び
2010527523.tif 000056
の位置を考慮して、
2010527523.tif 000057
の位置に対する頂点位置
2010527523.tif 000058
の空間的な関係がフレームｆに保存されるように、行列Ａ（ｆ，ｖ，ｆｒ）を決定する。
図１１を参照すると、
2010527523.tif 000059
は、対応するパッチの重心
2010527523.tif 000060
及び
2010527523.tif 000061
にそれぞれ固定された局所的な正規直交座標フレーム
2010527523.tif 000062
及び
2010527523.tif 000063
を用いて計算する。
【０１０７】
基底ベクトル
2010527523.tif 000064
及び
2010527523.tif 000065
は、
2010527523.tif 000066
及び
2010527523.tif 000067
の位置を通って張られる回帰平面の法線ベクトルとしてそれぞれ計算される。基底ベクトル
2010527523.tif 000068
は、
2010527523.tif 000069
である
2010527523.tif 000070
を、法線ベクトルｚｆによって張られる平面へ正射影したものによって計算される。次に、それは、単位長さに規格化される。基底ベクトル
2010527523.tif 000071
は、フレームｆｒにおいて同様に決定される。したがって、
2010527523.tif 000072
及び
2010527523.tif 000073
が得られる。最後に、
2010527523.tif 000074
によって、行列Ａ（ｆ，ｖ，ｆｒ）を決定する。
【０１０８】
Ｍｆ及び
2010527523.tif 000075
は、ｐｖｆの時空間近傍の符号化された頂点位置のみを用いて、２次の積によって計算された正規直交行列である。すなわち、行列Ａ（ｆ，ｖ，ｆｒ）も、２次のフレーム間及び階層間の依存性を利用した正規直交行列である。
【０１０９】
前述した基底ベクトル
2010527523.tif 000076
及び
2010527523.tif 000077
は、適切に定義された面の面法線（ｆａｃｅ  ｎｏｒｍａｌ）の平均としても計算し得る。面法線に基いた方法は、推奨した回帰法よりも高速であるが、予測精度は劣る。
【０１１０】
・Ｂ−フレーム予測子
線形予測子
2010527523.tif 000078
と同様に、
2010527523.tif 000079
を定義する。
【０１１１】
［量子化及びエントロピー符号化］
ＤＰＣＭ符号化器において、予測誤差
2010527523.tif 000080
は、量子化ビンのサイズΔを用いて均一に量子化される。量子化によって、整数値の３次元ベクトル
2010527523.tif 000081
が得られる。
【０１１２】
その後のエントロピー符号化は、さらなる圧縮のために、残りの統計的依存性を利用する。エントロピー符号化は、各要素に個別に適用される。エントロピー符号化のために、ゴロム（Ｇｏｌｏｍｂ）符号と組み合された適応的な０次の算術符号化器（Ｍｏｆｆｄａｔ  ｅｔ  ａｌ．，  ｉｎ  “Ａｒｉｔｈｍｅｔｉｃ  ｃｏｄｉｎｇ  ｒｅｖｉｓｉｔｅｄ，”ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍｓ，Ｖｏｌ．１６，Ｎｏ．３，１９９８  ａｎｄ  Ｓａｙｗｏｏｄ，  ｉｎ  “Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ，”Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ，１９９６）が適用される。
【０１１３】
算術符号化は、所定の整数値の領域内に含まれるすべての整数値
2010527523.tif 000082
に適用され、この領域外の値はゴロム符号を用いて符号化される。ここではｉｍａｘ＝３とする。値ｉがＡに含まれ、｜ｉ｜≠ｉｍａｘであれば、算術符号化を用いて符号化する。これらの値をｉａとする。値ｉがＡの外側にあり、又は、｜ｉ｜＝ｉｍａｘであれば、ｉは２つの部分に分解される。
2010527523.tif 000083
であれば、ｉａ：＝ｉｍａｘ，ｉｇ：＝ｉ−ｉａと定義し、
2010527523.tif 000084
であれば、ｉａ：＝−ｉｍａｘ，ｉｇ：＝ｉａ−ｉと定義する。次に、ｉａは、算術符号化器を用いて符号化され、一方、ｉｇはゴロム符号を用いて符号化される。
【０１１４】
個別のエントロピー符号化器が、各階層ｌの残差ｒｖｆを符号化するために用いられ、それによって、以前のフレームの符号化によって得られた残差の統計的分布に算術符号化器を階層ごとに適応させる。各フレームの各階層について、まず、算術符号化された値ｉａがビットストリームに書き込まれ、その後、ゴロム符号化された値ｉｇがビットストリームに書き込まれる。
【０１１５】
復号化の間、算術符号化された部分ｉａのすべての値が復号化される。次に、ゴロム符号化されたすべての値ｉｇが復号化される。最後に、ｉａ∈Ａ、かつ、｜ｉ｜≠ｉｍａｘであれば、復号化された整数値は、ｉ：＝ｉａである。値ｉａがｉｍａｘに等しければ、それは、対応するｉｇの値に加算され、復号化値ｉ：＝ｉａ＋ｉｇが得られる。したがって、ｉａが−ｉｍａｘに等しければ、ｉ：＝ｉａ−ｉｇと決定される。最終的に、すべての残差が復号化される。
【０１１６】
［パラメータ］
符号化された接続性及びエントロピー符号化された残差の他に、復号化可能なビットストリームを生成するために、パラメータの集合を符号化し、符号化の間に適用されたパラメータが復号化器に提供される。次のパラメータ、すなわち
・階層数Ｌ
・量子化ビンのサイズΔ
・フレーム順序制御部パラメータＮＰＢ及びＮＢ
は、圧縮プロセスの最初に一度符号化される。
【０１１７】
各フレームの各階層に対して、いずれの予測子の集合を適用するか、すなわち、線形予測子又は非線形予測子の集合のうちのいずれを適用するかを指定するために、１つの階層及びフレームごとに、そのフレームのその階層の残差を符号化する直前に、付加情報の１つの追加ビットが符号化される。したがって、予測子を指定するために、１フレームについてＬビットの付加情報が符号化される。２つ以上の予測子集合を使用するように符号化器を拡張する場合には、適用される予測子集合を特定するために、より多くの付加情報ビットを符号化する必要がある。
【０１１８】
［評価及び結果］
次の４つの異なるパラメータの設定、すなわち
・ＳＬＰＣ１、線形予測子の集合のみを使用し、ＮＰＢ＝Ｆ−１，ＮＢ＝０によって規定される順序でフレームを符号化する符号化器
・ＳＬＰＣ２、線形予測子の集合のみを使用し、ＮＰＢ＝Ｆ−１，ＮＢ＝１によって規定される順序でフレームを符号化する符号化器
・ＳＣＰＣ１、線形予測子及び非線形予測子を使用し、ＮＰＢ＝Ｆ−１，ＮＢ＝０によって規定される順序でフレームを符号化する符号化器
・ＳＣＰＣ２、線形予測子及び非線形予測子を使用し、ＮＰＢ＝Ｆ−１，ＮＢ＝１によって規定される順序でフレームを符号化する符号化器
を使用して、提供する符号化器の圧縮性能を評価する。
【０１１９】
ＳＣＰＣ１及びＳＣＰＣ２は、各フレームｆの各階層ｌに対して、最小の平均予測誤差をもたらす予測子、すなわち、線形予測子又は非線形予測子の集合を選択することによって実現される。
【０１２０】
実験的に評価するために、４００個のフレームと１フレーム当り３０３０個の頂点とから成る、タイムコンシステントなメッシュシーケンス「Ｃｈｉｃｋｅｎ」と、２０４個のフレームと１フレーム当り２９０４個の頂点とから成る、タイムコンシステントなメッシュシーケンス「Ｃｏｗ」とを用いた。他のメッシュシーケンス用いて評価した場合にも、同等な結果が得られた。
【０１２１】
図１を参照すると、接続性の階層化された表示の結果として、異なる空間解像度においてタイムコンシステントなメッシュシーケンスが得られる。「Ｃｈｉｃｋｅｎ」と「Ｃｏｗ」の各シーケンスの接続性は、それぞれ８階層、６階層に分解された。表１を参照すると、新しい階層が追加されるごとに、頂点数は約３８％増大し、すなわち、空間解像度はほぼ一定の割合で増加した。
【０１２２】
表１．階層ｌごとの頂点数Ｍｌと新しい階層ごとの空間解像度の増分（％）
2010527523.tif 000085
【０１２３】
正規化された頂点ごとのＬ２ノルム（Ｋａｒｎｉ  ａｎｄ  Ｇｏｔｓｍａｎ  ｉｎ  “Ｃｏｍｐｒｅｓｓｉｏｎ  ｏｆ  Ｓｏｆｔ−ｂｏｄｙ  ａｎｉｍａｔｉｏｎ  ｓｅｑｕｅｎｃｅｓ”，Ｃｏｍｐｕｔｅｒ＆Ｇｒａｐｈｉｃｓ，Ｖｏｌ．２８，Ｎｏ．１，２００４）を用いて、対応する元の頂点位置に対する符号化された頂点位置の品質を測定した。ここでは、これをＫＧ誤差という。ビットレートは、１頂点及び１フレーム当りのビット数（ｂｉｔ  ｐｅｒ  ｖｅｒｔｅｘ  ａｎｄ  ｆｒａｍｅ、ｂｐｖｆ）で測定した。この尺度を用いた他のアプローチとの比較を可能とするために、フレームごとのすべての頂点位置、すなわち、Ｌ個すべてのフレームを符号化する。エントロピー符号化の前に、予め定めた量子化ビンのサイズΔを用いて予測誤差を均一に各々の空間方向に量子化する。図１２及び図１３に示した演算レート歪み曲線は、Δを変化させて生成された。
【０１２４】
図１２及び図１３において、異なる４つの設定を有する本提案によるスケーラブルな符号化器（ＳＬＰＣ１、ＳＬＰＣ２、ＳＣＰＣ１、ＳＣＰＣ２）を、最新の圧縮アルゴリズムに対して評価した。図１２は、ｌ＝８階層を用いて符号化されたシーケンス「Ｃｈｉｃｋｅｎ」を示し、図１３は、ｌ＝６階層を用いて符号化されたシーケンス「Ｃｏｗ」を示す。異なる誤差尺度を用いたため、上記のすべてのアルゴリズムについての比較はできなかった。Ｐａｙａｎ  ａｎｄ  Ａｎｔｏｎｉｏｎｉ（ＴＷＣ）（Ｐａｙａｎ  ａｎｄ  Ａｎｔｏｎｉｏｎｉ，  ｉｎ  “Ｔｅｍｐｏｒａｌ  ｗａｖｅｌｅｔ−ｂａｓｅｄ  ｇｅｏｍｅｔｒｙ  ｃｏｄｅｒ  ｆｏｒ  ３Ｄ  ａｎｉｍａｔｉｏｎｓ，”Ｃｏｍｐｕｔｅｒ＆Ｇｒａｐｈｉｃｓ，Ｖｏｌ．３１，Ｎｏ．１，２００７）、及び、Ｇｕｓｋｏｖ  ａｎｄ  Ｋｈｏｄａｓｋｙ（ＡＷＣ）（Ｇｕｓｋｏｖ  ａｎｄ  Ｋｈｏｄａｓｋｙ，ｉｎ  “Ｗａｖｅｌｅｔ  ｃｏｍｐｒｅｓｓｉｏｎ  ｏｆ  ｐａｒａｍｅｔｒｉｃａｌｌｙ  ｃｏｈｅｒｅｎｔ  ｍｅｓｈ  ｓｅｑｕｅｎｃｅｓ”  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ／ＥＧ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｎｉｍａｔｉｏｎ，Ｇｒｅｎｏｂｌｅ，Ｆｒａｎｃｅ，２００４）のウエーブレットベースプローチ、並びに、Ｓａｔｔｌｅｒ等（ＣＰＣＡ）（Ｓａｔｔｌｅｒ  ｅｔ  ａｌ．，  ｉｎ  “Ｓｉｍｐｌｅ  ａｎｄ  ｅｆｆｉｃｉｅｎｔ  ｃｏｍｐｒｅｓｓｉｏｎ  ｏｆ  ａｎｉｍａｔｉｏｎ  ｓｅｑｕｅｎｃｅｓ，”，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ／ＥＧ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｎｉｍａｔｉｏｎ，Ｌｏｓ  Ａｎｇｅｌｅｓ，ＣＡ，ＵＳＡ，２００５）のＰＣＡベースアプローチに対する比較を行った。
【０１２５】
本発明による４つのパラメータ設定を有するスケーラブルな符号化器ＳＬＰＣ１、ＳＬＰＣ２、ＳＣＰＣ１及びＳＣＰＣ２は、いずれも、他のすべてのアプローチよりも性能が優れている。「Ｃｈｉｃｋｅｎ」に対する誤差０．０２及び「Ｃｏｗ」に対する誤差０．１５は、画質の低下はないものと考えられる。この領域では、ウエーブレット及びＰＣＡベースのアプローチは、著しく劣っている。明らかに、インターリーブされた頂点の階層化された配置、並びに、線形及び非線形の依存性の選択的かつ予測的な利用は、予測符号化のアプローチの符号化効率を向上させる。ＳＣＰＣ１はＳＬＰＣ１と比較してビットレートを約１３％増大させ、ＳＣＰＣ２はＳＬＰＣ２と比較して１５％高い利得を与える。したがって、非線形の依存性をさらに利用すると、アプリケーションに関連する領域で大きな利得がもたらされる。ＳＬＰＣ２は、ＳＬＰＣ１よりも優れた圧縮性能を示す。これは、双方向予測に基いて量子化誤差に対する予測子の強固さが増大したこと、すなわち、予測精度が向上したことに起因する。全体として、非線形の依存性を階層ごとに利用することにより、ビットレートの利得がさらに増大し、ビットレートに余分のコストを要することなく、階層化された復号化の特徴が提供される。
【０１２６】
［アプリケーション（応用）］
提案する方法は、信号における冗長性の削減に応用することができる。ここで考える信号は、次の通りである。
・信号は、フレームのシ−ケンスとして記述される。各フレームは、接続性及びジオメトリによって記述される。接続性は、ノード又は頂点、辺及び面によって記述される。ジオメトリは、位置、点、ベクトル又は固定されたサイズのベクトルによって記述される。フレームのシーケンスは、以下の条件のうちの１つを満たす。
１．すべてのフレームは同一の接続性を伴うものの、ジオメトリはフレームごとに変化し得る。
２．フレームは、ブロック内のすべてのフレームが同一の接続性を持つように、フレームから成るブロックにグループ化される。異なるブロック間では、接続性が異なっていてもよい。
【０１２７】
ケース１では、コーダは、フレームのシ−ケンスに直接適用し得る。タイムコンシステントな３次元メッシュシ−ケンスは、条件１を満たす。ケース１では、コーダは、ブロックごとに適用でき、フレームのブロックごとに、まず接続性を符号化し、次にジオメトリを符号化する。
・多チャンネル信号において、単一の各チャンネル信号は、位置、点又は固定サイズのベクトルのシ−ケンスとする。チャンネル間依存性は、接続性によって記述される。接続性は、ノード又は頂点、辺及び面によって記述される。
【０１２８】
ここで提案する方法によると、符号化された信号を表す構成化されたビットストリームが生成され、これにより、精度、すなわち、空間的、及び／又は、時間的解像度が次第に増大する、漸進的な復号化が可能となる。とりわけ、本方法は以下の信号、すなわち、タイムコンシステントな３次元メッシュ（ワイヤフレーム）、タイムコンシステントなテクスチャ座標のシ−ケンス、又は、タイムコンシステントな法線ベクトルのシ−ケンスに適用することができる。これらのシ−ケンスは、ＶＲＭＬ９７又はＭＰＥＧ−ＢＩＦＳにおいて規定されているように、通常、ＩｎｄｅｘｅｄＦａｃｅＳｅｔ及びＣｏｏｒｄｉｎａｔｅＩｎｔｅｒｐｏｌａｔｏｒノードによって表される。
【０１２９】
［可能な拡張］
本方法の圧縮効率及びその階層化された分解の平滑性を向上させるために、特に、以下の拡張を適用することができる。
【０１３０】
・接続性Ｋのみを使用する代りに、接続性Ｋと、ｖ∈Ｖ及びｆ＝１，…，Ｆに対するすべての頂点位置ｐｖｆを使用して、ｌ＝１，…，Ｌに対する階層化された分解Ｖｌ，Ｋｌを計算する。この場合、Ｋの代りに、ｆ＝１，…，Ｌに対する階層化された分解Ｖｌ，Ｋｌを符号化する。
【０１３１】
Ｉ−フレームとＰ−フレームの使用と、圧縮のための変換符号化。これは、
Ｉ，Ｂｌｏｃｋ１，Ｐ，Ｂｌｏｃｋ２，Ｐ，Ｂｌｏｃｋ３，Ｐ，…
のように、フレームをグループ化することによって実現される。Ｂｌｏｃｋｉのようなブロックは、ここではフレームの集合を表す。
【０１３２】
Ｉ−フレーム及びＰ−フレームは、ここで示した符号化器によって符号化される。次に、符号化済みの周辺のＩ−フレーム、及び／又は、Ｐ−フレームを用いて、各ブロックＢｌｏｃｋｉを予測する。最後に、残りの予測誤差を、変換符号化を用いて無相関化し、エントロピー符号化する。
【０１３３】
・予測精度を高めるための最適参照フレームの決定。参照フレーム番号は、次に、付加情報として符号化される。
【０１３４】
本提案方法は、タイムコンシステントなメッシュシーケンスの視点依存圧縮を実現するように拡張することができる。
【０１３５】
視点依存圧縮とは、単眼視によって視認し得る頂点位置のみの圧縮をいう。ここでは、視点（ｖｉｅｗ）は固定されていても、フレームごとに変化してもよい。１フレーム当り頂点位置の部分集合のみを符号化すればよいため、視点依存圧縮によると、圧縮性能を大幅に改善することができる。視点依存圧縮は要求に応じて行う必要があり、バックチャネルを介して、復号化器は、どの視点が現にアクティブであるかを符号化器又はサーバに通知する必要がある。次に、現在見えている現フレームの頂点位置の部分集合のみを、符号化器が符号化し、又は、サーバが送出する。これは、現在見えていない頂点を含む頂点位置の上位集合（ないし超集合、ｓｕｐｅｒｓｅｔ）であってもよい。１フレーム当りの頂点位置の部分集合を符号化するために、次のように符号化器を拡張する。
【０１３６】
まず、第１のフレームは、そのフレームのすべての頂点位置を符号化するＩ−フレームとして符号化する。これ以降のフレームについては、各頂点につきそれに関連付けられた位置を符号化すべきか否かを示すビットマスクを、最初に符号化する。これは、あるフレームについて符号化すべき頂点位置の部分集合を定義する。次に、第１のフレームは、現フレームにできるだけ適合するように、アフィン変換を用いて変換してもよく、このアフィン変換を記述する変換係数を符号化する。最後に、頂点位置の部分集合を圧縮するために、本提案方法の拡張バージョンを適用する。
【０１３７】
一般に、参照フレームは、現在符号化されている頂点位置の空間的、及び／又は、時間的近傍のすべての頂点位置を含んでいるわけではない。これは、１フレームについて頂点位置の部分集合のみが符号化されていることに起因する。したがって、本方法は、第１のフレームの変換されたものを追加の参照フレームとしてつねに使用するように拡張される。第１のフレームのすべての頂点位置が符号化されているため、欠落した近傍の頂点位置は、変換された第１のフレームによって符号化器及び復号化器に供与される。
【０１３８】
［結論］
スケーラビリテイを保障するとともに利用する、タイムコンシステントな３次元メッシュシーケンスを予測的に圧縮する方法が提供される。本方法によると、メッシュシーケンスの各フレームは複数の階層に分解され、これにより、タイムコンシステントな多解像度表現が得られる。予測符号化のパラダイムに従って、階層ごとの圧縮のために、階層間及びフレーム間の局所的な時間的空間的な依存性が用いられる。現在の頂点位置を予測するために、符号化済みの近傍の頂点の動きを利用して、頂点ごとに粗な階層から密な階層へと予測が行われる。したがって、階層ごとに順次復号化することよって、精度を向上させつつフレームを再構成することができる。
【０１３９】
本提案による頂点の階層化された配置を予測的に利用することによって、応用に関連する領域において、他の最新のアプローチと比較して、圧縮性能を向上させることができる。
【０１４０】
タイムコンシステントな３次元メッシュシーケンスの階層化された予測的符号化方法を提案した。パッチベースのメッシュ単純化手法を利用して階層を定義し、階層間及びフレーム間の線形及び非線形の空間的時間的依存性を利用するために、階層ごとに予測子の選択を行った。頂点の階層化された配置により、空間時間依存性の利用が改善されることを実験によって示した。本提案方法は、応用に関連する領域において、最新のアプローチを上回る性能を有する。さらに、本提案方法は、フレームベースの階層ごとの復号化に使用でき、計算負荷が低い（実行時間が頂点数に比例する）ため、実時間の圧縮に利用することができる。
【０１４１】
優先権書類は、引用により本出願に繰込まれ、特に、誤記を訂正するために考慮される。
【図１】
2010527523.tif 000086
【図２】
2010527523.tif 000087
【図３】
2010527523.tif 000088
【図４】
2010527523.tif 000089
【図５】
2010527523.tif 000090
【図６】
2010527523.tif 000091
【図７】
2010527523.tif 000092
【図８】
2010527523.tif 000093
【図９】
2010527523.tif 000094
【図１０】
2010527523.tif 000095
【図１１】
2010527523.tif 000096
【図１２】
2010527523.tif 000097
【図１３】
2010527523.tif 000098
【手続補正書】
【提出日】平成21年12月21日(2009.12.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
タイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスを、スケーラブルな予測符号化を用いて符号化する方法であって、
フレームが関連付けられた接続性（ｃｏｎｎｅｃｔｉｖｉｔｙ）（Κ）を伴う頂点の集合（Ｖ）を含み、該接続性（Ｋ）が３次元メッシュシーケンスのすべてのフレームについて同一である、３次元メッシュシーケンスの連続フレームを受信する工程と、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的な階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する工程と、
予測符号化器を用いて前記複数の階層に含まれる頂点を符号化する工程とを含み、
前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算することを特徴とする符号化方法。
【請求項２】
前記シーケンスの第１のフレームについて、前記３次元メッシュシーケンスの接続性（Ｋ）を符号化する工程と、
各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から、１の圧縮方法を選択する工程とをさらに含むことを特徴とする、請求項１に記載の符号化方法。
【請求項３】
前記３次元メッシュシーケンスを多解像度表現に分解する工程は、
分解の階層数（Ｌ）を設定する工程と、
前記設定された分解の階層数（Ｌ）を符号化する工程と、
１つの中間の頂点を共有する３角形の集合を含む１以上のパッチを選択する工程とを含み、
前記中間の頂点（ｍｉｄｄｌｅ  ｖｅｒｔｅｘ）は所定の数以下、特に、６以下の価数（ｖａｌｅｎｃｅ）を有し、
前記価数は前記中間の頂点に直接隣接する頂点の数によって定義され、
前記１以上の選択されたパッチの中間の頂点を削除するとともに、関連付けられた接続性（ＫＬ）を伴う該削除された中間の頂点によって定義される分解された階層（ＶＬ）を生成する工程と、
残りの頂点の集合に関連する単純化された接続性を決定する工程と、
１以上のパッチを選択する工程、中間の頂点を削除する工程、及び、単純化された接続性を決定する工程を、残りの単純化された接続性を伴う頂点の集合について、設定された階層数よりも２だけ少ない反復回数（Ｌ−２）に亘って、繰り返すことにより、関連付けられた接続性（ＫＬ−１，…，Ｋ２）を伴う分解された階層（ＶＬ−１，…，Ｖ２）を生成する工程と、
残りの関連付けられた接続性Ｋ１を伴う頂点の集合（Ｖ１）を基底階層（ｂａｓｅ  ｌａｙｅｒ）として定義する工程とを含むことを特徴とする、請求項１又は２に記載の符号化方法。
【請求項４】
前記残りの頂点の集合に関連する単純化された接続性を決定する工程は、
削除された頂点の以前の最近接（１−ｒｉｎｇ  ｎｅｉｇｈｂｏｒｈｏｏｄ）の頂点を３角形分割する工程を含み、
前記最近接（頂点）は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、該３角形分割及び前記階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数（ｖａｌｅｎｃｅ）に対する、削除された頂点の最近接の頂点の価数の平均絶対偏差に基いて選択され、
予測符号化器を用いて前記階層に含まれる頂点を符号化する工程は、
選択された各フレームについて、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む一群の圧縮方法から１の圧縮方法を選択する工程と、
Ｉ−フレーム予測子、Ｐ−フレーム予測子、又は、Ｂ−フレーム予測子をそれぞれ用いて、予測誤差を生成する工程とを含み、
現フレームの現頂点についてのＰ−フレーム圧縮は、符号化済みのフレームを参照フレームとみなし、現フレームの現頂点のＩ−フレーム予測子と、参照フレームにおける現頂点の位置と該参照フレームの現頂点のＩ−フレーム予測子との間の差とを足し合わせることによって、Ｐ−フレーム予測子を計算することを含み、
前記差は、回転行列（Ｒｏｔａｔｉｏｎ  Ｍａｔｒｉｘ）（Ａ）と掛け合わされることを特徴とする、ことを特徴とする、請求項３に記載の符号化方法。
【請求項５】
現フレームの現頂点についてのＢ−フレーム圧縮は、符号化済みの２つのフレームをそれぞれ第１の参照フレーム及び第２の参照フレームとみなし、該第１の参照フレームを考慮した請求項４によるＰ−フレーム予測子と、該第２の参照フレームを考慮した請求項４によるＰ−フレーム予測子との平均、特に、重み付き平均を計算することによって、Ｂ−フレーム予測子を計算することを含むことを特徴とする、上記請求項のいずれか１項に記載の符号化方法。
【請求項６】
前記選択された予測子を示す情報を符号化することにより、前記予測子は、フレームごと又は階層ごとに、特に、所定の個数のビットを用いて符号化されることを特徴とする、請求項４又は５に記載の符号化方法。
【請求項７】
上記請求項のいずれか１項に記載の符号化方法を実行するように構成されていることを特徴とする、タイムコンシステントな３次元メッシュシーケンスを符号化する符号化装置。
【請求項８】
複数のフレームによって定義される、符号化されたタイムコンシステントな（ｔｉｍｅ−ｃｏｎｓｉｓｔｅｎｔ）３次元メッシュシーケンスを表すデータ信号を復号化する方法であって、
各フレームは関連付けられた接続性（Ｋ）を伴う頂点の集合（Ｖ）を含み、
前記接続性（Ｋ）はスケーラブルな予測符号化によって符号化される３次元メッシュシーケンスのすべてのフレームについて同一であり、
前記データ信号を受信する工程と、
前記３次元メッシュシーケンスの接続性（Ｋ）を復号化する工程と、
関連付けられた接続性（Ｋｌ）を伴う頂点の素集合（Ｖｌ）によって表される２以上の空間的階層を含む多解像度表現に、前記３次元メッシュシーケンスを分解する工程と、
復号化器を用いて前記複数の階層に含まれる頂点を復号化する工程とを含み、
前記頂点の位置データに依らず、前記３次元メッシュシーケンスの接続性（Ｋ）から前記分解を計算することを特徴とする復号化方法。
【請求項９】
各フレーム、及び／又は、各階層について、前記符号化器によって用いられる圧縮方法を示す情報を復号化し、特に、参照フレームの番号を表す参照フレーム番号を復号化するとともに、Ｉ−フレーム圧縮、及び、Ｐ−フレーム圧縮、及び／又は、Ｂ−フレーム圧縮を含む圧縮方法のタイプを復号化する工程をさらに含み、
前記３次元メッシュシーケンスを多解像度表現に分解する工程は、
符号化器から受信した、階層の数（Ｌ）を表す階層数を復号化する工程と、
１つの中間の頂点を共有する３角形の集合を含む１以上のパッチを選択する工程とを含み、
前記中間の頂点（ｍｉｄｄｌｅ  ｖｅｒｔｅｘ）は所定の数以下、特に、６以下の価数（ｖａｌｅｎｃｅ）を有し、
前記価数は前記中間の頂点に直接隣接する頂点の数によって定義され、
前記１以上の選択されたパッチの中間の頂点を削除するとともに、関連付けられた接続性（ＫＬ）を伴う該削除された中間の頂点によって定義される分解された階層（ＶＬ）を生成する工程と、
残りの頂点の集合に関連する単純化された接続性を決定する工程と、
１以上のパッチを選択する工程、中間の頂点を削除する工程、及び、単純化された接続性を決定する工程を、残りの単純化された接続性を伴う頂点の集合について、設定された階層数よりも２だけ少ない反復回数（Ｌ−２）に亘って、繰り返すことにより、関連付けられた接続性（ＫＬ−１，…，Ｋ２）を伴う分解された階層（ＶＬ−１，…，Ｖ２）を生成する工程と、
残りの関連付けられた接続性Ｋ１を伴う頂点の集合（Ｖ１）を基底階層（ｂａｓｅ  ｌａｙｅｒ）として定義する工程とを含み、
前記残りの頂点の集合に関連する単純化された関連付けられた接続性を決定する工程は、
削除された頂点の以前の最近接（１−ｒｉｎｇ  ｎｅｉｇｈｂｏｒｈｏｏｄ）の頂点を３角形分割する工程を含み、
前記最近接（頂点）は、頂点に直接隣接するすべての頂点によって定義され、
３角形分割は、該３角形分割及び前記階層に関連する接続性（Ｋｌ）に対する所定の数に等しい、特に、６に等しい価数（ｖａｌｅｎｃｅ）に対する、削除された頂点の最近接の頂点の価数の平均絶対偏差に基いて選択され、
指定された圧縮方法に従って予測子を決定する工程と、
予測誤差を復号化する工程と、
特定された予測子及び復号化された予測誤差に基いて、対応する頂点の予測値、及び／又は、位置データを計算する工程とを、好ましくは各階層において行われるようにして、さらに含み、
基底階層の頂点の位置データを復号化する工程を含み、
現フレームの現頂点についてＩ−フレームを圧縮する場合に、該現フレームの該現頂点の復号化済みの最近接（頂点）の位置の平均としてＩ−フレーム予測子を計算することを含み、
現フレームの現頂点のＰ−フレームを圧縮する場合に、復号化済みのフレームを参照フレームとみなし、現フレームの現頂点のＩ−フレーム予測子と、参照フレームの現頂点の位置と該参照フレームの現頂点のＩ−フレーム予測子との間の差とを足し合わせることによって、Ｐ−フレーム予測子を計算することを含み、該差は、回転行列（Ｒｏｔａｔｉｏｎ  Ｍａｔｒｉｘ）（Ａ）と掛け合わされ、
現フレームの現頂点のＢ−フレームを圧縮する場合に、符号化済みの２つのフレームをそれぞれ第１の参照フレーム及び第２の参照フレームとみなし、該第１の参照フレームを考慮したＰ−フレーム圧縮の場合と同様なＰ−フレーム予測子と、該第２の参照フレームを考慮したＰ−フレーム圧縮の場合と同様なＰ−フレーム予測子との平均、特に、重み付き平均を計算することによって、Ｂ−フレーム予測子を計算することを含むことを特徴とする、請求項８に記載の復号化方法。
【請求項１０】
前記選択された予測子を示す情報は、フレームごと又は階層ごとに、特に、所定の個数のビットを用いて復号化されることを特徴とする、請求項８又は９に記載の復号化方法。
【請求項１１】
請求項１乃至６のいずれか１項に記載の符号化方法により符号化されたデータ信号を、復号化するように構成されていることを特徴とする、請求項８乃至１０のいずれか１項に記載の復号化方法。
【請求項１２】
請求項８乃至１０のいずれか１項に記載の復号化方法を実行するように構成されたことを特徴とする、符号化されたタイムコンシステントな３次元メッシュシーケンスを表すデータ信号を復号化する復号化装置。
【請求項１３】
タイムコンシステントな３次元メッシュシーケンスを符号化するコンピュータプログラムであって、
請求項７に記載の符号化装置を制御するコンピュータ上で、前記コンピュータプログラムを動作させた場合に、請求項１乃至６のいずれか１項に記載の符号化方法の各工程を、該符号化装置に実行させるプログラムコード手段を含むことを特徴とするコンピュータプログラム。
【請求項１４】
符号化されたタイムコンシステントな３次元メッシュシーケンスを表すデータ信号を復号化するコンピュータプログラムであって、
請求項１２に記載の復号化器を制御するコンピュータ上で、前記コンピュータプログラムを動作させた場合に、請求項８乃至１１のいずれか１項に記載の復号化方法の各工程を、該復号化器に実行させるプログラムコード手段を含むことを特徴とするコンピュータプログラム。
【請求項１５】
請求項１乃至６のいずれか１項に記載の符号化方法によって符号化された、符号化されたタイムコンシステントな３次元メッシュシーケンスを表すことを特徴とするデータ信号。
【国際調査報告】
2010527523.tif 000099
2010527523.tif 000100
2010527523.tif 000101