(57)【要約】原画像シーケンスを符号化するための方法であって、少なくとも一部の原画像についてモーション画像として知られる動きを表す情報とテクスチャ画像として知られるテクスチャを表す情報とを生成するためのモーション／テクスチャ分解と、モーション画像またはテクスチャ画像をそれぞれ対応する推定画像と比較することによって得られる差分画像（残差）に適用されるウェーブレット符号化とを含んでなる。
2006521048.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一部の原画像についてモーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行する、原画像シーケンスを符号化するための方法であって、
前記モーション画像を取得するために動きを推定する段階と、
その上では動きの効果がキャンセルされている前記テクスチャ画像を取得するために各前記原画像を少なくとも１つの基準グリッド上に投影する段階と、
モーション残差と称されるモーション差分画像を取得するためにモーション画像と対応する推定画像とを比較する段階と、
テクスチャ残差と称されるテクスチャ差分画像を取得するためにテクスチャ画像と対応する推定画像とを比較する段階と、
前記モーション残差と前記テクスチャ残差を独立にウェーブレット符号化する段階と
を含んでなる、画像シーケンスの符号化方法。
【請求項２】
前記比較は前記画像シーケンスの少なくとも最初の画像および／または最後の画像を使用して補間された画像との差分を使用することを特徴とする請求項１に記載の画像シーケンスの符号化方法。
【請求項３】
前記テクスチャの時間的符号化が実行され、この時間的符号化はウェーブレット符号化を使って時間軸に沿って暫定的に符号化された前記動きによって調整されるものである請求項１または２に記載の画像シーケンスの符号化方法。
【請求項４】
時間的ウェーブレット符号化とそれに続いて行われる空間的ウェーブレット符号化とを含むテクスチャの符号化を含むものである請求項１から３のいずれかに記載の画像シーケンスの符号化方法。
【請求項５】
メッシュ分割を考慮するモーション符号化を含むものである請求項１から４のいずれかに記載の画像シーケンスの符号化方法。
【請求項６】
前記メッシュ分割は、階層的メッシュ分割である請求項５に記載の画像シーケンスの符号化方法。
【請求項７】
空間ウェーブレット符号化が、その後に続いて行われる時間的ウェーブレット符号化から成るモーション符号化を含むものである請求項１から６のいずれかに記載の画像シーケンスの符号化方法。
【請求項８】
前記原画像は、可変数（Ｎ）個の原画像を含む画像ブロックにグループ化されることを特徴とする請求項１から７のいずれかに記載の画像シーケンスの符号化方法。
【請求項９】
２つの連続する画像ブロックは、少なくとも１つの共通する画像を含むことを特徴とする請求項８に記載の画像シーケンスの符号化方法。
【請求項１０】
ある画像ブロックの最初の画像は符号化されず、この最初の画像は１つ前の画像ブロックの最後の画像と同一であることを特徴とする請求項９に記載の画像シーケンスの符号化方法。
【請求項１１】
各前記画像ブロックごとに、画像ブロックの全ての画像の動きをその画像ブロックの最初の画像から推定することを特徴とする請求項１から１０のいずれかに記載の画像シーケンスの符号化方法。
【請求項１２】
前記投影段階においては、議論しているブロックの最初の画像と最後の画像をそれぞれ表現する２つの基準グリッドを使用することを特徴とする請求項１１に記載の画像シーケンスの符号化方法。
【請求項１３】
Ｎ個の画像を含むブロックに対して、１から（Ｎ＋１）／２までの画像は最初の画像を表現する基準グリッド上に積み重ねられ、（Ｎ＋１）／２＋１からＮまでの画像は最後の画像を表現する基準グリッド上に積み重ねられることを特徴とする請求項１２に記載の画像シーケンスの符号化方法。
【請求項１４】
少なくとも２つのレベルの画像解像度で動きを推定する多重解像度モーション（動き）推定を実行するモーション符号化を含むものである請求項１から１３のいずれかに記載の画像シーケンスの符号化方法。
【請求項１５】
前記動き推定を、少なくとも２つのレベルの前記階層的メッシュ分割で実行することを特徴とする請求項６かつ請求項１４に記載の画像シーケンスの符号化方法。
【請求項１６】
テクスチャ・マスクを取得するために画像内のメッシュ分割のノードのポジションによって指定されるサンプリンググリッドに対応する少なくとも１つの基準グリッド上に画像を投影する段階を含むものである請求項１から１５のいずれかに記載の画像シーケンスの符号化方法。
【請求項１７】
階層的メッシュ分割の少なくとも２つの階層レベルにそれぞれ特定の基準グリッドが付随するマルチグリッドアプローチを実行することを特徴とする請求項１６に記載の画像シーケンスの符号化方法。
【請求項１８】
前記階層レベルの間でメッシュ分割ノードに重み付けをして、幾何学的変形を表現することを特徴とする請求項１７に記載の画像シーケンスの符号化方法。
【請求項１９】
別の画像に対応する基準グリッドを使用することにより前記画像投影段階の後に定義されないままになっている少なくとも１つの画像サポートゾーンを検出する段階と、前記定義されないままになっている画像サポートゾーンをパディングする段階（パディング段階）とを含むものである請求項１６から１８のいずれかに記載の画像シーケンスの符号化方法。
【請求項２０】
前記パディング段階は、分解・合成型アプローチに基づいて実行され、比較による残差を取得するために完成されるべき画像が分解され続いて合成されることを特徴とする請求項１９に記載の画像シーケンスの符号化方法。
【請求項２１】
前記分解・合成することは、前回の逐次代入で得られた残差に対して少なくとももう一度逐次代入し直されることを特徴とする請求項２０に記載の画像シーケンスの符号化方法。
【請求項２２】
予測による、時間的パディング段階がそれに続いて行われる少なくとも１つの画像に対する空間的パディング段階を含むことを特徴とする請求項１８から２１のいずれかに記載された画像シーケンスの符号化方法。
【請求項２３】
前記パディング段階は、特に補間によって実行されることを特徴とする請求項２２に記載の画像シーケンスの符号化方法。
【請求項２４】
サポートが無限長の信号をシミュレートするために画像のエッジに対応するウェーブレット係数に反対称性が適用されることを特徴とする請求項１から２３のいずれかに記載の画像シーケンスの符号化方法。
【請求項２５】
符号化されたデータは少なくとも２つのレイヤへと配送され、最下位レイヤは粗いクオリティの画像を再構成するためのデータを含み、最上位レイヤは前記粗い画像のクオリティをより精密にするためのデータを含むことを特徴とする請求項１から２４に記載の画像シーケンスの符号化方法。
【請求項２６】
前記最下位レイヤは、前記画像ブロックの最後の画像のモーションデータを含む低レベルのモーションストリームと、前記画像ブロックの最初と最後の画像のテクスチャデータを含む低レベルのテクスチャストリームとを含むことを特徴とする請求項２５に記載の画像シーケンスの符号化方法。
【請求項２７】
前記最上位レイヤは、前記残差の符号化に対応する高レベルのモーションストリームと高レベルのテクスチャストリームとを含むことを特徴とする請求項２５または２６に記載の画像シーケンスの符号化方法。
【請求項２８】
一群の原画像を選ぶ段階と、
前記一群の原画像における動きを解析して前記モーション画像を生成する段階と、
前記一群の原画像に属する画像の、対応するモーション画像の上に積み重ねられるテクスチャを解析して前記テクスチャ画像を生成する段階と、
前記一群の原画像の少なくとも一部のテクスチャ画像を予測して予測テクスチャ画像を生成する段階と、
テクスチャ画像と予測テクスチャ画像との差分に対応するテクスチャ残差を求める段階と、
前記一群の原画像の少なくとも一部のモーション画像を予測して予測モーション画像を生成する段階と、
モーション画像と予測モーション画像との差分に対応するモーション残差を求める段階と、
前記テクスチャ残差と前記モーション残差とにウェーブレット符号化を適用する段階と
を含んでなる請求項１から２７のいずれかに記載の画像シーケンスの符号化方法。
【請求項２９】
原画像シーケンスを表現する信号であり、少なくとも一部の原画像についてモーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行する請求項１から２８のいずれかに記載された符号化方法によって得られる信号であって、
モーション画像と対応する推定画像との比較によって得られるモーション残差と称されるモーション差分画像に適用されるウェーブレット符号化を表す第１のデジタルデータと、テクスチャ画像と対応する推定画像との比較によって得られるテクスチャ残差と称される、その上では動きの効果がきゃんせるされているテクスチャ差分画像に適用されるウェーブレット符号化を表す第２のデジタルデータとを含み、前記第１のデータは前記第２のデータとは独立に符号化されることを特徴とする信号。
【請求項３０】
少なくとも２つのレイヤから構築され、１つは最下位レイヤであり、該最下位レイヤは粗いクオリティの画像を再構成するためのデータを含み、もう１つは最上位レイヤであり、該最上位レイヤは前記粗い画像のクオリティをより精密なものにできるようにすること特徴とする請求項２９に記載の信号。
【請求項３１】
前記最下位レイヤは、連続的に、リセットデータを含むベースストリームと動きを表す第１のストリームとテクスチャを表す第１のストリームとを含み、前記最上位レイヤは、連続的に、動きを表す第２のストリームとテクスチャを表す第２のストリームとを含み、これらの第２のストリームは前記残差の符号化に対応することを特徴とする請求項３０に記載の信号。
【請求項３２】
オブジェクトの動き、テクスチャ、および形状をそれぞれ表現する、そのオブジェクトを記述するための３つのフィールドを含んでいる請求項２９から３１に記載の信号。
【請求項３３】
少なくとも一部の原画像についてモーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行する符号化方法によって符号化された原画像シーケンスを復号化するための方法であって、
前記ウェーブレット符号化は、原画像と対応する推定画像との比較によって得られる残差と称される差分画像に適用されるとともに、当該復号化するための方法は、
モーション画像を形成するために、動きに関連した前記残差の少なくとも一部を考慮して、その動きを復号化する段階と、
テクスチャ画像を形成するために、テクスチャに関連した前記残差の少なくとも一部を考慮して、そのテクスチャを復号化する段階と、
前記テクスチャ画像を前記モーション画像の上に投影することによって、前記原画像シーケンスに相当する、復号化された画像のシーケンスを合成する段階と
を含んでなることを特徴とする、画像シーケンスの復号化方法。
【請求項３４】
オリジナルのテクスチャ画像と復号化されたテクスチャ画像との間の歪みを解析することによって、前記復号化された画像のシーケンスのクオリティを測定するための段階を更に含むことを特徴とする請求項３３に記載の画像シーケンスの復号化方法。
【請求項３５】
前記モーション復号化段階は、
最初の画像上に階層的メッシュを生成する段階と、
最後の画像に関連したメッシュ分割を決めるために、その最後の画像に関連したモーション情報を復号化する段階と、
中間のモーション画像を補間する段階と
を含むことを特徴とする請求項３３または３４に記載の画像シーケンスの復号化方法。
【請求項３６】
符号化する際に適用されたウェーブレット変換とは逆のウェーブレット変換を含む前記残差を復号化するための段階と、前記残差を前記補間された中間モーション画像に加えるための段階とを更に含むことを特徴とする請求項３５に記載の画像シーケンスの復号化方法。
【請求項３７】
前記テクスチャ符号化段階は、有利には、
最初の画像についてテクスチャを生成する段階と、
最後の画像に関連したテクスチャを決めるために、その最後の画像に関連したテクスチャ情報を符号化する段階と、
中間テクスチャ画像を補間する段階と
を含んでなることを特徴とする請求項３３から３６のいずれかに記載の画像シーケンスの復号化方法。
【請求項３８】
「インター」ブロックと称される、前記画像ブロックの少なくとも一部の画像ブロックに対して、最初の画像のテクスチャを生成する前記段階は、１つ前の画像ブロックの最後の画像を考慮することを特徴とする請求項３７に記載の画像シーケンスの復号化方法。
【請求項３９】
符号化する際に適用されたウェーブレット変換とは逆のウェーブレット変換を含む前記残差を復号化するための段階と、前記残差を前記補間された中間テクスチャ画像に加える段階とを更に含むことを特徴とする請求項３７または３８に記載の画像シーケンスの復号化方法。
【請求項４０】
前記動き推定によって生じるリバーサルを管理するための段階を更に含むことを特徴とする請求項３３から３９のいずれかに記載の画像シーケンスの復号化方法。
【請求項４１】
実行されるべき一定レベルの質および／または量の処理作業が成し遂げられたら前記残差の処理を停止する段階を含むことを特徴とする請求項３３から４０のいずれかに記載の画像シーケンスの復号化方法。
【請求項４２】
少なくとも一部の原画像についてモーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行して原画像シーケンスを符号化するための装置であって、
原画像と対応する推定画像とを比較することによって得られる残差と称される差分画像に適用されるウェーブレット符号化の手段を含むことを特徴とする画像シーケンスの符号化装置。
【請求項４３】
少なくとも一部の原画像についてモーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行する符号化方法によって符号化された、原画像シーケンスを復号化するための装置であって、
前記ウェーブレット符号化は、原画像と対応する推定画像との比較によって得られる残差と称される差分画像に適用されるとともに、
モーション画像を形成するために、動きに関連した前記残差の少なくとも一部を考慮して、その動きを復号化するための手段と、
テクスチャ画像を形成するために、テクスチャに関連した前記残差の少なくとも一部を考慮して、そのテクスチャを復号化するための手段と、
前記テクスチャ画像を前記モーション画像の上に投影することによって、前記原画像シーケンスに相当する、復号化された画像のシーケンスを合成するための手段と
を含んでなることを特徴とする画像シーケンスの復号化装置。
【請求項４４】
請求項１から２８のいずれかに記載された符号化方法を実行するための手段を含むことを特徴とするデータサーバ。
【請求項４５】
端末装置によって読み出しが可能なデジタルデータ搬送波であって、請求項１から２８のいずれかに記載された符号化方法によって得られた請求項２９から３２のいずれかに記載された少なくとも１つの信号を搬送するデジタルデータ搬送波。
【請求項４６】
少なくとも一部の原画像についてモーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行して原画像シーケンスの符号化を実行するための命令を含むコンピュータプログラムであって、
前記モーション画像を取得するために動きを推定するための命令と、
その上では動きの効果がキャンセルされている前記テクスチャ画像を取得するために各前記原画像を少なくとも１つの基準グリッド上に投影するための命令と、
モーション残差と称されるモーション差分画像を取得するためにモーション画像と対応する推定画像を比較するための命令と、
テクスチャ残差と称されるテクスチャ差分画像を取得するためにテクスチャ画像と対応する推定画像を比較するための命令と、
前記モーション残差と前記テクスチャ残差を独立にウェーブレット符号化するための命令と
を含んでなることを特徴とするコンピュータプログラム。
【請求項４７】
少なくとも一部の原画像についてモーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行する符号化方法によって符号化された原画像シーケンスの復号化を実行するための命令を含むコンピュータプログラムであって、
前記ウェーブレット符号化は、原画像と対応する推定画像との比較によって得られる残差と称される差分画像に適用されるとともに、
モーション画像を形成するために、動きに関連した前記残差の少なくとも一部を考慮して、その動きを復号化するための手段と、
テクスチャ画像を形成するために、テクスチャに関連した前記残差の少なくとも一部を考慮して、そのテクスチャを復号化するための手段と、
前記テクスチャ画像を前記モーション画像の上に投影することによって、前記原画像シーケンスに相当する、復号化された画像のシーケンスを合成するための手段と
を含んでなることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はビデオ画像を例えば少なくとも１つの端末装置に記憶または伝送するためのビデオ画像シーケンスの符号化および復号化の技術に関する。
【０００２】
ビデオ画像の符号化は、様々な可変的なリソースおよび帯域幅を必要とする多くの用途に使用される。これらの異なるニーズに応えるために、スケーラビリティ（scalability）特性、すなち利用可能なリソースおよびビットレートに適応することが可能な特性を備えたビデオストリームを実現することが有用である。
【０００３】
本発明は、特にこのフレームワーク内に入るものである。
【０００４】
スケーラビリティは、特にビデオ符号化スキームにおいてウェーブレット変換を使用することによって実現することができる。ウェーブレットとスケーラビリティというこれら２つの側面によって信号を階層的に表現することが可能であることが実際に観測されている。
【背景技術】
【０００５】
２．１  ３Ｄウェーブレットを使用するビデオ符号化
ウェーブレットを使用するいくつかのビデオ符号化スキームはすでに文献の中で提示されている。例えば以下の文献には３Ｄ（三次元）ウェーブレット変換を使用することが提案されている。
１）S.J.ChoiおよびJ.W.Woods共著、「ビデオのモーション補償された３Ｄサブバンド符号化（Motion-Compensated 3d subband coding of video）」、画像処理に関するＩＥＥＥトランザクションズ（IEEE Transactions on Image Processing）、１９９９年２月、第８巻（第２号）、ｐ．１５−１６７、
２）J.R Ohm著、「モーション補償による三次元サブバンド符号化（Three-dimensional subband coding with motion compensation）」、画像処理に関するＩＥＥＥトランザクションズ（IEEE Transactions on Image Processing）、１９９４年９月、第３巻（第５号）、ｐ．５５９−５７１、
３）Secker A.およびD.Taubman共著、「リフティングに基づく３Ｄウェーブレット変換を使用したモーション補償されたスケーラビリティの高いビデオ圧縮（Motion-compensated highly-scalable video compression using 3d wavelet transform based on lifting）」、ＩＥＥＥ  ２００１、
４）D. TaubmanおよびA.Zakhor共著、「ビデオのマルチレート３Ｄサブバンド符号化（Multirate 3d subband coding of video）」、画像処理に関するＩＥＥＥトランザクションズ（IEEE transactions on Image processing）、１９９４年９月、第３巻（第５号）、ｐ．５７２−５８８。
【０００６】
１９９４年にTaubmanとZakhorによって提案された最初のスキームの１つは、画像シーケンスの最初の画像に基づいて調整された画像シーケンスに３Ｄウェーブレット変換を実行する。この技術において、対象とされる動き（motion）は、あるシーンにおける全体的な動きのみで、不十分なクオリティしか実現できない。縮小ゾーンおよび拡大ゾーンを提示するようなより複雑な動きを使用するには、非一様なサンプリンググリッド上で画像を調整する必要があり、このときこのスキームはもはや可逆的ではなくなる。
【０００７】
特に、１９９４年にOhm、１９９９年にChoiおよびWoodsによって開発された他のスキームは動きの表現にブロックを使用する。３Ｄウェーブレット変換はこれらのブロック上で運動経路に沿って実行される。
【０００８】
しかしながら、ブロック毎の動き（blockwise motion）は連続的ではなく、孤立したピクセル、または他のピクセルに二重に結合したピクセルが出現する。この結果、時間（テンポラル）サブバンドは多くの高い周波数を含む。さらに、これらの特定のピクセルはウェーブレットフィルタの長さを制限する。
【０００９】
特に、２００１年にTaubmanおよびSeekerによって提示された別のアプローチはテンポラル（時間方向）変換の「リフティング（lifting）」フォームを適用する際に３Ｄウェーブレットを使用する。この方法において、テンポラル変換はモーション（動き）補償（Motion Compensation）と同時に実行される。リフティングの使用は可逆変換を与える。しかしながら、順方向および逆方向のモーションフィールドの知識が必要である。現時点で、これらのモーションフィールドは符号化にコストがかかる。
【００１０】
ブロック毎の動きの使用は、頭切り型５／３フィルタ（truncated 5/3 filter）といったショートフィルタの使用を意味する。不連続的なこのブロック毎の動きは、サブバンドで符号化するのが難しい高い周波数を導入する。
【００１１】
２．２  上記従来技術の課題
これらの異なる周知のアプローチは時間軸に沿ってウェーブレットを使用しようと試みるものである。しかしながら、これらの研究のほとんどはブロック毎の動きを使用し、モーション補償（動き補償）の際に不連続性をもたらす。これらの不連続性が原因で、時間（テンポラル）ウェーブレットは、信号と最大効率の関連をなくすことはない。より具体的には、不連続性はサブバンドにおいて高周波数を生成し、これは続いて２Ｄウェーブレットで符号化することが難しい。
【００１２】
２．３  メッシュ分割を考慮した分解・合成のアプローチ
２００３年１月１６日〜１７日にリヨン（Lyon）で開かれたオーディオビジュアル信号の圧縮および表現に関するコレサ会議２００３（Conference Coresa'03 - Compression and Representation des Signaux Audiovisuels）の会議録に収録されたNathalie CamasおよびStephane Pateux共著「メッシュ分割に基づくスケーラブルなビデオ符号化と３Ｄウェーブレット（Codage video scalable par maillage et ondelettes 3D）」と題された論文おいて、著者は、特にメッシュ分割（meshing、本願ではメッシュ分割という言い方をするが、メッシュ化あるいはそのままメッシングという言い方をすることもできる）に基づく分解・合成型アプローチと動きの正確な表現に基づいて、これらの技術の改良を提示した。
【００１３】
メッシュ分割によるかかる動き推定（motion estimation）を使用することによって、時間軸に沿ったテクスチャの変形が効率的に追跡される。メッシュ分割によるモーション補償は、実際にテクスチャの時間的連続性を提供し、例えばブロックワイズ法といった他の補償方法とは共存しない。この時間的連続性は時間軸に沿ったウェーブレットを使用することによって活用することができる。
【００１４】
本発明は、より具体的にはこの後者の符号化技術に関係しており、ビデオ画像シーケンスを表現するために、特に伝送または記憶されるデータの量を減らすことによって改良することを目的としている。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
３．本発明の目標
本発明の目標は特に従来技術の異なる欠点を軽減することにある。
【００１６】
特に、本発明の目標は、上記従来技術と比較して、与えられたデータビットに対してより多くの情報を伝送（または記憶）し、あるいは与えられた量の情報に対してより低いビットレートを必要とするために使用される符号化技術を提供することにある。
【００１７】
本発明のもう１つの目標は、各画像または画像シーケンスを段階的に再構成することができるスケーラブルなビデオ符号化の方法を提供することにある。
【００１８】
本発明のもう１つの目標は、ハイクオリティなロバスト性を備えたこの種の符号化技術を提供することにある。
【００１９】
従って、本発明の目標は、スケーラビリティおよびロバスト性を更に提供する際にＨ２６４符号化の圧縮レート以下の圧縮レートを実現することにある。
【課題を解決するための手段】
【００２０】
４．本発明の主な特徴
これらの目標並びに以下現れる他の目標は、少なくとも一部の原画像についてモーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行する、原画像シーケンスを符号化するための方法であって、
前記モーション画像を取得するために動きを推定する段階と、
その上では動きの効果がキャンセルされている前記テクスチャ画像を取得するために各前記原画像を少なくとも１つの基準グリッド上に投影する段階と、
モーション残差と称されるモーション差分画像を取得するためにモーション画像と対応する推定画像とを比較する段階と、
テクスチャ残差と称されるテクスチャ差分画像を取得するためにテクスチャ画像と対応する推定画像とを比較する段階と、
前記モーション残差と前記テクスチャ残差を独立にウェーブレット符号化する段階と
を含んでなることを特徴とする、画像シーケンスの符号化方法によって達成される。
【００２１】
その結果、符号化される情報要素の数は大幅に減らされ、このため有用なビットレートの増大がなされ、または一定のビットレートのままで、符号化および／または保存（記憶）済みの画像の改善がなされる。
【００２２】
本発明のアプローチによれば、動きの効果がテクスチャ情報の中から取り除かれているので、モーション信号およびテクスチャ信号を独立に処理することが可能となる。これらの信号は両方のタイプの情報を独立に符号化することが可能である。
【００２３】
有利には、前記比較は前記画像シーケンスの少なくとも最初の画像および／または最後の画像を使用して補間された画像との差分を使用する。
【００２４】
有利には、前記テクスチャの時間符号化が実行され、この符号化はウェーブレット符号化を使って時間軸に沿って事前に符号化された動きによって調整される。
【００２５】
好ましくは、本発明の方法は、空間ウェーブレット符号化がその後に続いて行われる時間ウェーブレット符号化を含むテクスチャ符号化を含む。
【００２６】
本発明の有利な側面として、本発明の方法は、メッシュ分割を考慮するモーション符号化と、好ましくは階層的メッシュ分割を実行する。
【００２７】
有利には、モーション符号化も、空間ウェーブレット符号化がその後に続いて行われる時間ウェーブレット符号化を含む。
【００２８】
本発明の好ましい側面として、本発明の方法は、前記原画像は可変数（Ｎ）個の原画像を含む画像ブロックにグループ化される。
【００２９】
この数は特に画像の特性に応じて変化することがある。それは例えば８画像の範囲内にある。
【００３０】
有利には、２つの連続する画像ブロックは少なくとも１つの共通する画像を含む。言い換えると、ブロック達は重なり合う。
【００３１】
この場合、画像ブロックの最初の画像は符号化されず、この最初の画像は１つ前の画像ブロックの最後の画像と同一であることが有利である。
【００３２】
このことは有用なビットレートをさらに増やす。
【００３３】
課題解決手段の第１の形態として、各前記画像ブロックごとに、画像ブロックの全ての画像の動きはその画像ブロックの最初の画像から推定される。
【００３４】
特に、少なくとも１つの基準グリッド（reference grid）に関してモーション補償（動き補償）段階を実行することが可能である。
【００３５】
有利には、前記モーション補償段階においては、議論しているブロックの最初の画像と最後の画像をそれぞれ表現する２つの基準グリッドが使用される。
【００３６】
このとき本発明の第２の形態として、Ｎ個の画像を含むブロックに対して、１から（Ｎ＋１）／２までの画像は最初の画像を表現する基準グリッド上に積み重ねられ、（Ｎ＋１）／２＋１からＮまでの画像は最後の画像を表現する基準グリッド上に積み重ねられる。
【００３７】
本発明の別の好ましい側面として、本発明の符号化方法は、動きが少なくとも２つのレベルの画像解像度で推定される多重解像度モーション推定（動き推定）を実行する。
【００３８】
従って、前記動き推定は、有利には少なくとも２つのレベルの階層的メッシュ分割で実行されることがある。
【００３９】
当然、本発明は唯一のメッシュ分割解像度レベル、例えばコンテンツに適合した変則的なレベルのメッシュ分割で実行されてもよい。
【００４０】
有利には、テクスチャ・マスクを取得するために画像内のメッシュ分割のノードのポジションによって指定されるサンプリンググリッドに対応する少なくとも１つの基準グリッド上に画像を投影する段階が計画される。
【００４１】
好ましくは、階層的メッシュ分割の少なくとも２つの階層レベルにそれぞれ特定の基準グリッドが付随するマルチグリッドアプローチが実行される。
【００４２】
この場合、有利には、本発明は前記階層レベル間でメッシュ分割ノードのウェイトによる重み付けを実行し、それより幾何学的変形が表現される。
【００４３】
好ましくは、前記重み付けは１つのレベルから別のレベルへシフトが影響（波及）する際に（下位のメッシュ分割を保存するために）修正される。
【００４４】
有利には、粗いメッシュ分割と細かいメッシュ分割に対応する２つの連続する階層レベルの間で、前記細かいメッシュ分割のノードはそれらが属する粗いメッシュ分割の三角形に関連した重心座標によって表される。前記細かいメッシュ分割は、一方では前記粗いメッシュ分割のノードに従属する直系子孫（direct offspring）ノードと称される第１のノードと、他方では前記粗いメッシュ分割のリッジ中央のポジション（mid-ridge position）に対応する第２のノードとを含む。
【００４５】
このとき前記直系子孫ノードは前記粗いメッシュ分割の対応する親ノードの値を採ることがある。また前記第２のノードは前記リッジが属する２つの三角形の４つのノードの間の線形結合に対応することがある。
【００４６】
こうして、有利には、前記ノードが前記リッジ上にある場合には、前記リッジの２つの遠端（far-end）ノードのみが考慮され、前記ノードが前記リッジ上にない場合には、前記細かいメッシュ分割の該ノードが属する前記粗いメッシュ分割の三角形に属する３つのノードのみが考慮される。
【００４７】
本発明の別の側面として、前記マルチグリッド法は、幾何学的アプローチを拠り所とする初期化に基づいて、モーション・メッシュ分割に適用される。
【００４８】
この場合、本発明の方法は有利には、別の画像に対応する基準グリッドを使用するせいで前記画像投影段階の後に定義されないままになっている少なくとも１つの画像サポートゾーンを検出する段階と、前記定義されないままになっている画像サポートゾーンをパディングする段階（以下、「パディング段階」とよぶ）とを含む。
【００４９】
前記パディング段階は、分解・合成型アプローチに基づいて実行され、比較による残差を取得するために完成されるべき画像が分解され、続いて合成される。
【００５０】
好ましくは、前記分解・合成は前回の逐次代入（iteration）で得られた残差に対して少なくとももう一度逐次代入し直される。
【００５１】
前記パディング段階は、有利には、予測による、時間的パディング段階がそれに続いて行われる少なくとも１つの画像に対する空間的パディング段階を含む。
【００５２】
前記パディング段階は特に補間によって実行されることがある。
【００５３】
好ましくは、サポートが無限長の信号をシミュレートするために画像のエッジに対応するウェーブレット係数に反対称性（anti-symmetry）が適用される。
【００５４】
本発明の別の有利な側面として、符号化されたデータは少なくとも２つのレイヤに配送され、最下位レイヤは粗いクオリティの画像を再構成するためのデータを含み、最上位レイヤは前記粗い画像のクオリティをより精密（高品位）にするためのデータを含む。
【００５５】
前記最下位レイヤは、前記画像ブロックの最後の画像のモーションデータを含む低レベルのモーションストリームと、前記画像ブロックの最初と最後の画像のテクスチャデータを含む低レベルのテクスチャストリームとを含む。
【００５６】
前記最上位レイヤは、部分的に有利には、前記残差の符号化に対応する最高レベルのモーションストリームと最高レベルのテクスチャストリームとを含む。
【００５７】
本発明の特有の形態として、
一群の原画像を選ぶ段階と、
前記一群の原画像における動きを解析して前記モーション画像を生成する段階と、
前記一群の原画像に属する画像の、対応するモーション画像の上に積み重ねられるテクスチャを解析して前記テクスチャ画像を生成する段階と、
前記一群の原画像の少なくとも一部のテクスチャ画像を予測して予測テクスチャ画像を生成する段階と、
テクスチャ画像と予測テクスチャ画像との差分に対応するテクスチャ残差を求める段階と、
前記一群の原画像の少なくとも一部のモーション画像を予測して予測モーション画像を生成する段階と、
モーション画像と予測モーション画像との差分に対応するモーション残差を求める段階と、
前記テクスチャ残差と前記モーション残差とにウェーブレット符号化を適用する段階と  を含んでなることを特徴とする符号化方法が提供される。
【００５８】
本発明は、前記符号化方法によって生成される信号にも関係している。
【００５９】
この種の信号は、原画像シーケンスを表現するもので、少なくとも一部の原画像についてモーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行することにより得られる。この信号は、原画像と対応する推定画像との比較によって得られる残差と称される差分画像に適用されるウェーブレット符号化を表すデジタル信号を含む。
【００６０】
好ましくは、それは少なくとも２つのレイヤによって構築され、１つは最下位レイヤでありこの最下位レイヤは粗いクオリティの画像を再構成するためのデータを含み、もう１つは最上位レイヤでありこの最上位レイヤは前記粗い画像のクオリティをより精密（高品位）にできるようにする。
【００６１】
有利には、前記最下位レイヤは、連続的に、リセットデータを含むベースストリームと動きを表現する第１のストリームとテクスチャを表現する第１のストリームとを含み、前記最上位レイヤは、連続的に、動きを表す第２のストリームとテクスチャを表現する第２のストリームとを含み、これら第２のストリームは前記残差の符号化に対応する。
【００６２】
本発明の別の側面として、本信号は、オブジェクトの動き、テクスチャ、および形状をそれぞれ表現する、そのオブジェクトを記述するための３つのフィールドを含む。
【００６３】
また、本発明は、このような信号を復号化するための方法であって、および/または、本発明に係る前記符号化方法に対応する復号化方法にも関係している。
【００６４】
かかる復号化方法は、有利には、
モーション画像を形成するために、動きに関連した前記残差の少なくとも一部を考慮して、その動きを復号化する段階と、
テクスチャ画像を形成するために、テクスチャに関連した前記残差の少なくとも一部を考慮して、そのテクスチャを復号化する段階と、
前記テクスチャ画像を前記モーション画像の上に投影することによって、前記原画像シーケンスに相当する、復号化された画像のシーケンスを合成する段階と
を含んでなる。
【００６５】
好ましくは、それは、オリジナルのテクスチャ画像と復号化されたテクスチャ画像の間の歪みを解析することによって、復号化された画像の前記シーケンスのクオリティを測定するための段階を更に含む。
【００６６】
有利には、前記モーション復号化段階は、
最初の画像上に階層的メッシュを生成する段階と、
最後の画像に関連したメッシュ分割を決めるために、その最後の画像に関連したモーション情報を復号化する段階と、
中間のモーション画像を補間する段階と
を含む。
【００６７】
このとき、好ましくは、それは、符号化する際に適用されたウェーブレット変換とは逆のウェーブレット変換を含む前記残差を復号化する段階と、前記残差を前記補間された中間モーション画像に加える段階とを更に含む。
【００６８】
同様に、前記テクスチャ符号化段階は、有利には、
最初の画像についてテクスチャを生成する段階と、
最後の画像に関連したテクスチャを決めるために、この最後の画像に関連したテクスチャ情報を符号化する段階と、
中間テクスチャ画像を補間する段階と
を含む。
【００６９】
本発明の特有の側面として、「インター（inter）」ブロックと称される、前記画像ブロックの少なくとも一部の画像ブロックに対して、最初の画像のテクスチャを生成する前記段階は１つ前の画像ブロックの最後の画像を考慮する。
【００７０】
有利には、このとき上記復号化方法は、符号化する際に適用されるウェーブレット変換とは逆のウェーブレット変換を含む前記残差を復号化するための段階と、前記残差を前記補間された中間テクスチャ画像に加える段階とを更に含む。
【００７１】
それは、前記動き推定によって生じるリバーサル（reversals：逆転）を管理するための段階を更に含む。
【００７２】
好ましくは、それは、実行されるべき一定レベルの質および／または量の処理作業が成し遂げられたら前記残差の処理を停止する段階を含む。
【００７３】
本発明は、上記方法を実行する符号化装置および／または復号化装置、本発明に係る信号を記憶するとともに少なくとも１つの端末装置に伝送することが可能なデータサーバ、端末装置によって読み出しが可能でかかる信号を搬送することが可能なデジタルデータ搬送波、更には、本発明に係る符号化および／または復号化作業を実行するための命令を含むコンピュータプログラムにも関係している。
【発明を実施するための最良の形態】
【００７４】
６．１  本発明の一般原理
本発明に係る符号化技術は、メッシュ分割（meshing）と３Ｄウェーブレットによるビデオシーケンス符号化を提供する。
【００７５】
このビデオシーケンスは、最初にＮ個の画像を含む画像群（以下、ＧＯＰ（group of pictures）と称する）に分割される。ＧＯＰ１つ当たりの画像（ピクチャまたはイメージ）の数は特にシーケンスにおけるモーション（動き）の強さに応じて変動することがある。後述するように、平均してＧＯＰの大きさは８つの画像を含む。
【００７６】
符号化は分解・合成アプローチに基づく。第１段階は、変形可能なメッシュ分割を使用した、ＧＯＰによるモーション（動き）推定（motion estimation）である。第２段階は、ＧＯＰの動きおよびテクスチャの符号化である。
【００７７】
動きはＧＯＰの画像１と画像ｔにおいて推定される。ここで画像ｔはＧＯＰの１つの画像で、画像１はＧＯＰの最初の画像である。３Ｄウェーブレットと符号化スキームの分解・合成特性を使用することにより自然なスケーラビリティが得られる。
【００７８】
メッシュ分割をベースとするアプローチは、連続的なモーションフィールドを使用することによって従来技術についてまわるブロック効果を回避し、従って時間的予測を改善する。
【００７９】
本発明の符号化は従ってスケーラブルかつ段階的なストリームを提供するものである。分解・合成アプローチによれば、分解は動きがその中で推定される時間的窓（temporal window）に属する一群の画像の処理を含む。得られた補償モデルは時間的窓の最初の画像から最後の画像まで画像を補うために使用される。画像は、モーション情報とテクスチャ情報を分離するために、基準グリッド上に置くことができる。
【００８０】
これらの情報は、２つのレイヤにおいて別々に符号化することが可能である。
・サンプルされたビデオ信号を表現するために使用することができ、遠端（ファーエンド）の時間窓画像の情報を含むベースレイヤ、
・窓内の画像はこれらの２つの遠端画像の間に補間することが可能である。
・再構成されるビデオシーケンスの画質を改善するために少なくとも１つの連続するレイヤをベースレイヤの上に積み上げることが可能である。上に積み上がるレイヤは、窓の遠端（ファーエンド）内部画像にテクスチャおよび／または動きの精密化をもたらす。
【００８１】
ビデオシーケンスは、テクスチャ画像をオリジナルのサンプリンググリッド上に投影する合成段階によって再構成される。符号化戦略における動きおよびテクスチャの分離は動きのロッシー符号化を可能にするが、ビットレートの利得は構造の符号化に繰り越すことができる。最上位レイヤの符号化においてウェーブレットを使用することによりスケーラブルなストリームを提供することが更に可能となる。
【００８２】
６．２  符号化の一般スキーム（図１）
図１は、本発明に係る符号化方法および符号器の一般原理の概略を示した図である。
【００８３】
以下、具体的に述べる。それぞれの画像群１１は最初に１からｔの補償モデルに基づく動き推定段階１２を経て、次いで低レベル「ビットストリーム」１３１および高レベルもしくはレベルを上げた「ビットストリーム」１３２を配信するモーション符号化段階１３に送られる。
【００８４】
分解・合成の原理によれば、動きを表すデータはモーション復号化段階１４において符号化の際に再復号化される。基準グリッド上にテクスチャを積み重ねるための段階１５はこのテクスチャに関する情報を与え、次にこれらの情報は低レベルテクスチャ「ビットストリーム」と高レベルテクスチャ「ビットストリーム」にそれぞれ対応する２つのストリーム１６１と１６２とに符号化される（ステップ１６）。
【００８５】
異なるストリーム１３１、１３２、１６１、１６２は、次いでビットストリームを形成するために編成され、伝送および／または記憶用に設計されたストリームを提供する。
【００８６】
図２は、図１をより詳細にしたものである。そこで補償の段階１２およびテクスチャを符号化する段階１６についてより詳しく述べる。以下、より詳しく説明する。
【００８７】
［符号化の原理］
提案された符号化スキームは分解・合成型スキームである。それぞれの画像は（画像合成において実行することができるものと同じように）メッシュ分割を使って積み重ねられたテクスチャを使って与えられる。テクスチャ情報の他にメッシュ分割の進行情報も上記モーション推定アルゴリズムの他にモザイク画像を構築するための技術も使って得られる。
【００８８】
それぞれの画像は変形可能なメッシュ分割を使って積み重ねられた動的テクスチャ（つまり以前に生成された動的モザイク）を使って復元される。動的テクスチャは３Ｄウェーブレット表現を使って復号化される。メッシュ分割の変形に関する情報も３Ｄウェーブレットを使って復号化される。分割レベルもそれぞれの画像を個別に分割するために付加することが可能である。
【００８９】
この符号化スキームは多くの興味深い特徴を提供する。最初に、それはビデオに存在する空間／時間相互関係（特に時間的相互関係のレベルにおいて）を最大限まで活用する。
【００９０】
それは更に、復号器においてモーション情報をテクスチャ情報から分離する可能性を与える。従って、メッシュ分割の変形に関する情報のロッシー符号化が視覚的な劣化を与えることなく実現される。従って例えば、視覚的な不快感を引き起こすことなく、画像におけるピクセルのポジションのエラーを許容することが可能である。古典的な閉ループ符号化スキームでは、その場合、このモーションエラーをテクスチャの符号化を通じて補正することは必要であろう。
【００９１】
モーション情報の符号化における潜在的利得は特に重要である。というのは、低ビットレート（例えば３０ＨｚでのＣＩＦに対して２５６ｋビット／秒）で適用する際、モーション情報はＨ２６３型スキームにおける全ビットレートの３０％から４０％を占めることがあるからである。
【００９２】
テクスチャおよびモーション情報フィールドを符号化するために、３Ｄウェーブレット符号化技術が使用される。この技術は符号化のビットレート歪み最適化を実現すると同時に最大の（空間的かつＳＮＲの）スケーラビリティを与えるために使用することができるＪＰＥＧ２０００ウェーブレット符号器をテクスチャに対して使用することに基づく。ＪＰＥＧ２０００は基本的には２Ｄ画像符号器であるので、３Ｄウェーブレット符号化はそれに複数成分画像を提供することによって得られる。これらの成分は議論される３Ｄ情報のボリュームの異なる時間サブバンドを表現する。
【００９３】
［符号化の構造とスケーラビリティ］
ビデオシーケンスを符号化するために、このシーケンスはまず最初に画像群（Groups of Pictures；ＧＯＰ）に分割される。各ＧＯＰにおいて、動きに関する情報とテクスチャに関する情報が別々に、しかもスケーラブルに符号化される。画像に対するＭＰＥＧ符号化構造と同様の仕方で、イントラＧＯＰ（inra GOP）およびインターＧＯＰ（inter GOP）といった２つのタイプのＧＯＰが区別できる。イントラＧＯＰはその他のＧＯＰとは独立に復号化されるＧＯＰのことである（例えばシーケンスの最初のＧＯＰといったもの）。インターＧＯＰは前回のＧＯＰとは異なった符号化がなされたＧＯＰのことである（このインター符号化の目的はＧＯＰの最初にあるイントラ画像の符号化を妨げることによって圧縮を改善することにある）。
【００９４】
これらのＧＯＰの各ＧＯＰごとに、最初の画像において使用されるメッシュ分割は正則（regular）メッシュ分割である。それ故にそれは符号器と復号器には分かっており、符号化される必要はない（階層レベルの数といったそれを定義するパラメータのコストあるいは再びメッシュ分割のサイズは実際には見過ごされる場合がある）。ＧＯＰの最初の画像は（イントラＧＯＰの場合に）「イントラ」符号化されるか、または前回のＧＯＰから取り出されるかいずれかである（インターＧＯＰは前回のＧＯＰと共通する最初の画像を有する）。
【００９５】
最大のスケーラビリティを提案するために、最後の画像を指定する情報は最初に符号化される（メッシュ分割の変形、ＧＯＰの最初の再構成された画像とＧＯＰの最後の再構成された画像との間のモザイク上のテクスチャの差異）。最後に、残りの情報はスケーラブルな符号化技術を使用する３Ｄウェーブレットによって符号化される（ＪＰＥＧ２０００参照）。図３１は異なるレベルの表現をまとめたものである。
【００９６】
最下位レイヤはＭＰＥＧスキームのＩＰＰＰＰ最下位レイヤと似ていることがある。ビットストリームのスケーラブルな最上位レイヤはＧＯＰの中間および最後の画像に段階的な改善をもたらす。
【００９７】
［テクスチャに関する情報の符号化］
図３１から分かるように、ＧＯＰに関するテクスチャ情報は２段階において符号化される。最初の段階では、最下位レイヤが符号化される。この段階は、最初の画像の符号化（当該ＧＯＰがイントラＧＯＰの場合）と、差分モードにおける最後の画像のテクスチャの符号化とを含む。第２段階では、その部分の残りが３Ｄウェーブレットによって符号化される。
【００９８】
符号化すべき残差情報は、ＧＯＰ（画像群）の各画像ごとに、瞬間ｔ0から瞬間ｔ1までの範囲であり、
【数１】
2006521048.tif 000003
である画像として定義される。このとき時間ウェーブレット変換は残差画像上で定義される（Daubechies 9,7 type filter）。このウェーブレット変換に関して議論される画像はＧＯＰの全ての残差画像（インターＧＯＰの最初の画像の残差の画像を除く）である。異なる時間サブバンドの画像は符号化すべき画像の成分としてそれぞれの時間サブバンドを指定する際にＪＰＥＧ２０００を使って連続的に符号化される。
【００９９】
モーション補償が前もって実行されているので、符号化の際に動きの存在を考慮する必要はない。
【０１００】
復号化レベルでは、最初に低いレイヤの全ての情報と、次に最上位レイヤの情報（符号器に使用されるスケーラビリティのタイプに依存する情報）が復号化される。最上位レイヤから来るインクリメントが次に最下位レイヤからの復号化情報に加えられる。
【０１０１】
［動きに関する情報の符号化］
モーション情報はテクスチャ情報と同じように符号化される。低いレイヤのレベルにおいて、メッシュ分割のポジションはＧＯＰの最後の画像に対してのみ符号化される。最上位レイヤにおいて、残差はＧＯＰの端のノードのポジションの線形補間を使ってメッシュ分割のポジションで計算される。
【０１０２】
最下位レイヤにおけるシフトの符号化はＤＰＣＭタイプの符号化を通じて、一様なスカラ数量化を使用して実現される。これを実行するために、ＪＰＥＧ−ＬＳ型符号器が適用されている。
【０１０３】
最上位レイヤでは、最初に時間ウェーブレット変換がDaubechies-9,7フィルタを使って各ノードごとに行われる。この時間変換はそれぞれの時間サブバンドに対応する１セットのクラスタの値を与える。これらのクラスタの値はメッシュ分割のノードに付随した値に対応する。
【０１０４】
［Maquant-2000］において提案されたものと同様に、メッシュ分割をベースとするウェーブレット変換が空間（スペーシャル）サブバンドを取得するためにこれらに値に実行される。空間・時間サブバンドは文脈的算術符号器（contextual arithmetic encoder）を使って連続的にビットマップで符号化される。ビットレート歪み最適化は符号化のために選ばれた最終ビットマップレベルを定めるために実行される（大きなサイズのＥＢＣＯＴブロックが使用されるＪＰＥＧ２０００によって実行されるビットレート割り当てに似た技術）。
【０１０５】
研究の最初の段階では、モーション情報を符号化するためのスキームは、階層的メッシュ分割の符号化で、しかも良好な圧縮レートを実現するために適応メッシュ分割を使用することによる符号化に基づくものであった。ウェーブレットの使用は実際このタイプの符号化を一般化する方法と見なされてよい。また数量化は階層ツリーにおける符号化されないゾーンを明らかにする。ウェーブレットアプローチの利点は、ビットレート歪み最適化のみならず精密なスケーラビリティを提供するということにあるが、これは以前のアプローチでは定義するのは比較的困難であった。
【０１０６】
６．３  動きの推定
符号化スキームの最初の段階は動きの推定である。以下の３つのポイントは、２つの連続する画像の間の動きの推定の異なる方法を提示する。最後のポイントは本符号器のために選ばれた推定方法を提示する。
【０１０７】
［動き推定（復習）］
動きは、変形可能なメッシュ分割を使って２つの連続する画像ｔおよびｔ＋１の間で推定される。動き推定の一般原理は汎関数の式、
Σρ∈Ωρ（Ｉ（ｐ，ｔ）−Ｉ（ｐ−ｄｐ，ｔ−１））
を最小化することを含む。この式において、Ωは推定サポート（estimation support）、ρは誤差計量（error metric）で最もよく使用されるのはρ＝ｒ2であり、Ｉ（ｐ，ｔ）はポイントｐおよび瞬間ｔにおける画像Ｉの値、ｄｐは稠密（デンス）なモーションフィールドである。ｄｐ＝Σiｗi（ｐ）ｄｐiと書け、ｗi（ｐ）はノードｉに関するｐの座標、ｄpiはノードｉに付随するシフトを表す。
【０１０８】
上記汎関数を最小化するためのアルゴリズムは、２０００年１２月１４日に提出された仏国レンヌ第１大学・学位論文、Gwenaelle Marquant著MarquantOO「Representation par maillage adaptatif deformable pour la manipulation et la communication d'objets videos」に記述されている。この最小化はメッシュ分割のノードに関して実行される。探索はｔからｔ＋１までのノードのシフトベクトルｄpiに対して行われる。
【０１０９】
エネルギーは、勾配法（Gauss-Seidel型）によって反復的に最小化される。解かれるべきシステムは次のような形を有する。
【数２】
2006521048.tif 000004
【０１１０】
このシステムの未知因子はΔｄｐi値である。このシステムはＡ．Ｘ＝Ｂ型の線形システムであり、それは疎（hollow）である。解はロバストな高速共役勾配法によって求まる。
【０１１１】
［多重解像度および階層的推定］
本発明に係る符号器の場合、動き推定は多重解像度（multiple-resolution）および階層的メッシュ分割（hierarchical meshing）によっても実行することができる。この技術はシステムの収束性を改善することを目的とする。実際、動きが重い間は、従来の最小化法は収束しない場合があり、さらに細かいメッシュ分割の使用は過度に多数のパラメータのせいでシステムの不安定性を促しかねない。
【０１１２】
階層的メッシュ分割を使用する動き推定法は、ｔおよびｔ＋１の画像に対する階層的メッシュ分割を生成して、異なるメッシュ分割レベルで動きを推定することにある。
【０１１３】
図３に階層的メッシュ分割の一例を示す。この階層表現は数個のレベルの表現によって構築される。最低レベル３０（図ではレベル０）は粗いフィールドを有する（３つのノードのみがメッシュ分割を定める）。
【０１１４】
より細かいレベル３２、３３、３５に進むと、フィールドは段階的に密になり、メッシュ分割のノード数は増加する。動きの質はレベルとともに変化する。従って低レベル３０はシーンの大まかな主要な動きを表し、細かいレベルはその大まかな主要な動きを細かくして局所的な動きを表す。階層的メッシュ分割のレベル数は推定段階の可調パラメータであり、それは推定すべきシーケンスに応じて変化することがある。
【０１１５】
多重解像度推定法は画像の異なるレベルの解像度で動きを推定することを含む。動きは最初に最低解像度の画像の間で推定され、次いで次第により精密な画像を使用する中で精密化される。既に言及したように、本発明は唯一のレベルのメッシュ分割、例えば一様でなく在中物に適用されるメッシュ分割の場合にも適用可能である。
【０１１６】
低解像度値の使用は動きの振幅を制限する。つまり、精密な解像度の画像で幅広な振幅の動きは粗い解像度で振幅は低い。フィルタ処理してつぶした画像のピラミッドが画像ｔから画像ｔ＋１にかけて構築され、次いで動きが粗いレベルからより細かいレベルへと推定される。
【０１１７】
図４に一例を示すように、多重解像度でしかも階層的な動きの推定は先の２つの技術を結合する。最初に、推定は粗いメッシュ分割かつ粗い解像度レベルで行われる。続いて、メッシュ分割の解像度および階層レベルは細かいメッシュ分割でフル解像度の画像に対応する機能値に近づくように精密化される。
【０１１８】
図４にメッシュ分割と解像度を細かくする異なる可能性を示す。
【０１１９】
アプローチａは多重解像度アプローチのみに対応し、アプローチｂは階層的推定のみに対応する。またアプローチｃは多重解像度を通じて粗いレベルで幅広な振幅の動きの推定を可能にするとともに、階層的なメッシュ分割を使って動きが局所的に精密化されるのを可能にする。アプローチｄは多重解像度と階層的メッシュ分割を組み合わせた別のアプローチであって、その利点はメッシュ分割の三角形のサイズに関して十分なレベルの解像度を使用することにある。この階層的多重解像度アプローチの原理はすでに述べたMarquant00の論文において考案された。
【０１２０】
図５に、本発明の１つの好ましい実施形態として、動き推定のために選ばれたアプローチを示す。この技術は遭遇するかもしれない異なるタイプの動きを考慮することを可能にする。パラメータＲ０は使用される最も粗いレベルの解像度で、Ｈ-Ｒ０は推定された局所的な動きの大きさをコントロールする。ＤＨは低解像度画像での推定に関係したバイアスを制限し、Ｈｆは最も細かい階層レベルを表す。
【０１２１】
これらのパラメータはシーケンスのタイプに依存する。良い結果を与える１組の固定パラメータは以下のようになる。Ｈｆは動き推定に対して所望のメッシュ分割精密度を得られるよう定められる。また、Ｈ-Ｒ０＝Ｈｆ、ＤＨ＝２、Ｒ０＝３である。
【０１２２】
［マルチグリッド推定（Multiple-grid estimation）］
この技術の原理は以下さらに明らかにされる。この技術は動き推定の際の多重解像度・階層的メッシュ分割アプローチに関係している。マルチグリッド推定は非一様なメッシュ分割での動き推定の際に現れる次善最適性の問題を解決するために使用される。
【０１２３】
［コンビネーション］
符号器で使用される動き推定は、上で更に説明したように、多重解像度、階層的メッシュ分割およびマルチグリッドを組み合わせたアプローチである。図２に示されるように、動きは連続する画像ｔおよびｔ＋１の間で推定され（ステップ１２２）、続いて１およびｔ＋１の間の推定によって精密化される（ステップ１２３）。ここで１はＧＯＰの最初の画像である。メッシュ分割は次のＧＯＰの最初の画像でリセットされる。このアプローチはＧＯＰのＮ個の画像に対して繰り返される（ステップ１２４、１２５、１２６）。
【０１２４】
［モーションパディング（Motion Padding）］
パディングはオブジェクトによって画定されるゾーンの外側における動きの外挿（extrapolation）に対応する。このパディングの目的は不完全な信号をオリジナルの信号に近い値によって完全なものにすることにある。この操作は、不完全な信号が存在するとき、そしてそれが完全な信号として処理されなければならないときに必要なようである。
【０１２５】
動き推定において、この操作は全ての画像にわたる動き推定の最後に起きる。実際、ＧＯＰ内で、推定は前回の推定から導かれた変形したメッシュ分割から毎回再開され、メッシュが画像の定義のフィールドから出るときに、それらはその変形した形状を維持する。次に、その後これらのメッシュが再びその定義のフィールドに入ると（画像内で交互に行き来する動き）、次の推定は入ってくるメッシュが均質な場合には、つまりそれらがそれ以上変形されない場合には、よりよい質にある。
【０１２６】
モーションパディング操作は画像の定義のフィールドの外側にポジションするメッシュを滑らかにするために推定の各終わりに適用される。
【０１２７】
パディングの原理は完成されるべき情報のタイプが何であれ、テクスチャまたは動きのいずれであれ、同じでよい。それは以下さらに説明されるマルチグリッドアプローチと同様である。原理はそれ故に分解・合成の原理で、情報の階層的ウェーブレット表現が使用される。
【０１２８】
ｓが完成されるべき信号である場合、信号の近似ｓ∧＝Σkｃkφkについて探索が行われる。｛φｋ｝は正規直交基底である。
【０１２９】
この目的のため、汎関数‖ｓ−ｓ∧‖2が最小化される。この最小化法は図６に示すように逐次代入によって行われる。
【０１３０】
第１の粗い近似ｓ∧Gが計算され（分解６１）、続いてこの第１の粗い近似はｓ∧f（６７）を得るために細かいドメインまで拡張される（合成６２）。残差ｓ−ｓ∧fについて計算が行われ（６３）、計算された残差にプロセスを適用することによって第１の近似が精密化される。
【０１３１】
このプロセスは、残差が一定の閾値未満かどうかを判定する停止基準まで繰り返される（６５）。この停止基準は残差が一定の閾値未満かどうかを判定するためのもので、信号の近似の精度を決定する。パディングは不完全な初期の信号のゾーンを信号の完全な近似によって埋めることにある（６６）。
【０１３２】
分解（analysis）と合成（synthesis）の段階は完成されるべき信号の性質に依存し、その信号が動きに関する情報あるいはテクスチャに関する情報のどちらを表すかに依る。その信号が動きに関する情報を表す場合、完成されるべき信号は階層的メッシュ分割である。細かい階層レベルを完成させることが求められ、その際、近似は、最も粗いレベルから最も細かいレベルへと進む中で、より低いレベルで逐次的に計算されることになる。
【０１３３】
あるレベルでの分解はウェーブレットモーションがこのレベルで決定されることを可能にするシステムの解像度によって実行される。つまり、このレベルのメッシュから最良の動き（モーション）について探索が行われる。
【０１３４】
続いて細かいレベルの近似は見つかった解によって更新される。システムの残差は細かいレベルで計算され、作業はより高い粗いレベルへと進む。細かいレベルのシステムは粗いレベルに変換され、このレベルのウェーブレットモーションについて探索が行われる。それらのレベルでプロパゲーションが生じたら、細かいレベルの近似は精密化される。プロセスはシステムがそれぞれの粗いレベルに戻ったときに停止する。最後に、初期の細かいメッシュ分割において定義されない値は精密な近似から更新される。
【０１３５】
テクスチャ信号の分解と合成については動き（移動）とテクスチャの分離に関係する部分において以下より詳細に説明される。
【０１３６】
６．４  ２つのレイヤにおけるスケーラブルな符号化
［ベーシックレイヤ］
符号化は２つのレイヤ、最下位レイヤ（ボトムレイヤ）および最上位レイヤ（トップレイヤ）、において行われる。最下位レイヤはＧＯＰの最初と最後の画像に関する情報を含む。ＧＯＰの中間の画像はこれら２つの最初と最後の画像の間を補間することによって再構成される。
【０１３７】
動きとテクスチャは線形補間によって得られ、続いて画像は補間された動きとテクスチャに基づいてそれらのサンプリンググリッド上で合成される。線形補間は以下の形を有する。Ｉ（ｔ）＝ａ＊Ｉ（１）＋（１−ａ）＊Ｉ（Ｎ）。この式で、Ｉ（１）はＧＯＰの最初の画像、Ｉ（Ｎ）はＧＯＰの最後の画像、Ｉ（ｔ）は１およびＮの間のＧＯＰの画像である。また、ａ＝ｔ／Ｎ、Ｉｘは画像ｘのテクスチャの情報、または動きの情報のいすれかを表す。
【０１３８】
最下位レイヤは符号器の最小限の質の再現を実現するベーシックレイヤである。それはＮ個の画像の段階によってサンプルされた初期の信号を表す。
【０１３９】
［閉ループＰ型最下位レイヤ］
最下位レイヤはＰ型であって、最初の画像はイントラ符号化され、次の画像は閉ループで機能するように符号化・復号化された前の画像ＩまたはＰに基づく予測によって符号化される。最下位レイヤはＧＯＰの最後の画像のテクスチャおよびモーション情報とＧＯＰがイントラＧＯＰの場合には最初の画像の情報とを含む。
【０１４０】
ＧＯＰがイントラＧＯＰである場合、最下位レイヤは符号化された画像Ｉ（１）を含む。画像Ｉ（Ｎ）は予測によって符号化される。つまりＩ（Ｎ）−Ｉ∧（１）が符号化される。ここでＩ∧（１）は符号化・復号化された画像Ｉ（１）である。ＧＯＰがイントラＧＯＰでない場合、Ｉ（Ｎ）の動きおよびテクスチャ情報のみが最下位レイヤで符号化される。この場合、Ｉ（Ｎ）を予測するために、本発明は前のＧＯＰのＩ（Ｎ）を使用する。つまり、現在のＧＯＰが前のＧＯＰのＩ∧（Ｎ）に等しい場合はＩ（１）である。ここでＩ∧（Ｎ）は符号化・復号化された画像Ｉ（Ｎ）である。
【０１４１】
［スケーラブルな精密化レイヤ（Scalable refining layer）］
最上位レイヤはＧＯＰの画像の動きおよびテクスチャに関する情報を含む精密化レイヤである。遠端画像（ＧＯＰの最初と最後の画像）の精密化は最下位レイヤに関する符号化の精密化である。中間画像の精密化はこれらの画像と最下位レイヤからのそれらの補間との予測誤差である。この誤差はここではｄＩ（ｔ）＝Ｉ（ｔ）−Ｉ（１）−ａ*（Ｉ（Ｎ）−Ｉ（１））で与えられる。
【０１４２】
最上位レイヤはスケーラブルなストリームを提供する例えばＪＰＥＧ２０００符号器によって符号化される。
【０１４３】
６．５  動きおよびテクスチャの分離
［基準グリッド上への画像の積み重ね（piling）］
ｉ．動きはテクスチャとは独立に符号化される。動きは、各画像に対応する、各瞬間ｔにおけるメッシュ分割のノードのポジションによって与えられる。テクスチャは基準グリッド上に画像を積み重ねるための作業によって取り出される。
【０１４４】
基準グリッドはこの画像におけるノードのポジションによって指定されるサンプリンググリッドである。画像ｋ上に画像ｉを積み重ねる操作は画像ｋのグリッド上に画像ｉを再構成すること、すなわち、画像ｋに関して画像ｉを調整することにある。再構成画像Ｉｒは画像ｋと同じサンプリンググリッドを有する。
【０１４５】
画像の再構成サポートは、画像から抜け出す動きを考慮に入れるために、画像の初期のサポートよりも大きい場合があるが、サポートのサイズは動き推定において決定されるともにその動きの大きさに依存する。基準グリッド上の積み重ねの時点で、パイリングサポート（piling suport）と同じサイズを有し、再構成されたサポートのピクセルを表示するマスクも取り出される。
【０１４６】
図７Ａから図７Ｆに示された例は、画像ｉ（図７Ａ）上への画像ｋ（図７Ｂ）の積み重ね（パイリング）を示しており、ｉとｋの間の動き（ｉ（図７Ｃ）におけるメッシュ分割のポジションとｋ（図７Ｄ）におけるメッシュ分割のポジション）が分かる。
【０１４７】
補遺３に提示されたアルゴリズム１は画像ｉ（図７Ａ）上に投影された画像ｋを再構成するためにのアルゴリズムである。画像Ｉｒを再構成するために、この画像はスキャンされ、ピクセルのポジションはそれ故に整数で、画像ｋにおけるＩｒのそれぞれのピクセルのコレスポンデントについてｉからｋまで逆の動きをそれに適用することにより探索が行われる。
【０１４８】
モーションベクトルは整数値を持たないので、対応するピクセルは整数値のポジションを持たない。双一次補間がその輝度値を計算するために必要である。
【０１４９】
図８は、整数値における輝度値にわたって実行される双一次補間の詳細な記述を提供する。
【０１５０】
Ｍにおける輝度Ｌの双一次補間
ａ＝（１−ｕ）*Ｌ（ｐ，ｑ）＋ｕ*Ｌ（ｐ＋１，ｑ）
ｂ＝（１−ｕ）*Ｌ（ｐ，ｑ＋１）＋ｕ*Ｌ（ｐ＋１，ｑ＋１）
Ｌ(u,v)＝（１−ｖ）*ａ＋ｖ*ｂ
【０１５１】
このようにして計算された輝度は再構成されるべき画像Ｉｒの現在のピクセルに付与される。再構成されたピクセルは最初に画像ｉの定義マスクに含まれなければならない。続いてシフトされたピクセルは予測可能、すなわち、画像ｋの定義マスクに含まれなければならない。画像ｋの予測マスク（図７Ｆ）はこれら２つの基準を満足するピクセルで「真」値を採る。
【０１５２】
ｉｉ．  画像の投影に関する基準グリッドの選択とテクスチャの取り出しにおいて、本発明は図９に示すように２つの基準サンプリンググリッド、１つはＧＯＰの最初の画像７１のもの、もう１つはＧＯＰの最後の画像７２のもの、を使用する。Ｎ個の画像を含むＧＯＰに対して、１から（Ｎ＋１）／２の画像７３はＧＯＰの最初の画像の上に置かれ、（Ｎ＋１）／２＋１からＮの画像７３は画像Ｎ７２の上に置かれる。
【０１５３】
［テクスチャの３Ｄ（三次元）パディング］
ｉｉｉ．  ２Ｄ（二次元）パディング
基準グリッド上への画像の積み重ね（パイリング）はそれらの１つを除いて、サポートのゾーンは積み重ね（パイリング）操作の後も未定義のままであることを意味する。これらのゾーンは積み重ねられた画像の予測マスクを使って特定される。これらの無定義ゾーンはパディング操作によって埋められる。
【０１５４】
画像のパディングは画像が定義されていないゾーンをその近傍で定義された値に近い値で埋めることにある。パディングは分解・合成の原理に基づく。
【０１５５】
完成されるべき画像は分解され、続いて合成される。そして残差が合成に関して計算され、分解はこの残差に関して再開される。図１０に、この種の原理を示す。画像の連続する低周波数バージョンが画像に重なるブロック上で定義された値で計算され、次いで低周波数が未定義のゾーンで連続的に展開される。
【０１５６】
例えば、ＣＩＦフォーマットのサイズが３５２×２８８のピクセルにおける画像Ｉｏ１０１に対して、第１の低周波数が全体の画像に重なる５１２×５１２のサイズのブロック上で計算される。平均が予測マスク内で定義された画像のピクセル上で計算され、無定義ピクセルは０にある（図では黒色）。
【０１５７】
ブロックのサイズを有する平均画像Ｉｍｏｙ１・１０２は計算された平均の値で満たされる。
【０１５８】
唯一のブロックしかないので、唯一の平均値しか存在しない。続いて残差画像Ｉ１・１０３がオリジナルの画像を平均画像から差し引くことによって得られる（Ｉ１＝Ｉｏ−Ｉｍｏｙ１）。
【０１５９】
（＊）５１２×５１２サイズのブロックが４つに分割され（各ブロックのサイズは２５６×２５６）、続いてプロセスは各ブロックごとに平均の計算を再開する。しかし今の場合、平均はオリジナル画像の予測マスク内で定義される残差画像Ｉ１のピクセル上で計算される。得られた平均画像Ｉｍｏｙ２・１０４は前の平均画像に加えられる（１０５）。得られた最後の画像１０５はＩ２・１０６を得るためにＩ１から差し引かれる。
【０１６０】
プロセスはＩ１の代わりにＩ２を議論して（＊）から再開する。このプロセスはブロックのサイズがピクセルのサイズに等しくなるまで繰り返される。
【０１６１】
定義されないゾーンの低周波数バージョンによるパディングは定義されたゾーンと比べてこれらの無定義ゾーンにおいて不明瞭さを生じさせる。
【０１６２】
しかしながら、画像の連続性は保たれる。無定義ゾーンはパディング操作の後に定義されるようになり、オリジナル画像の予測マスクは画像のあらゆるピクセルで「真」値を採る。
【０１６３】
ｉｖ．時間的パディング（Temporal padding）
符号器によって行われるパディングは３Ｄパディングである。それは２Ｄ画像と時間次元とを考慮する。２ＤパディングはＧＯＰの最初の画像（Ｉ１）と最後の画像（ＩＮ）で実施され、続いて時間的パディングがＧＯＰのその他の画像を完成するために実行される。
【０１６４】
時間的パディングは内部画像が２つの遠端画像の間の線形補間によって予測されるという事実を利用する。予測残差は３Ｄウェーブレットによって符号化されるので、可能な限り小さな残差を得ることが求められる。パディングはそれ故に未定義でないゾーンを、非常に小さな残差あるいはゼロでさえある残差を与える値で、空間の時間的な連続性を保ちながら、完成させなければならない。
【０１６５】
これが、ＧＯＰの内部画像が２つの空間的にパディングされた遠端画像に基づいて線形補間によって完成される理由である。このためＧＯＰの１からＮの各画像がスキャンされ、これは現在の画像ｔの各ピクセルごとに行われる。ピクセルがマスクにおいて無定義の場合、その値はａ*Ｉ（１）＋（１−ａ）*Ｉ（Ｎ）である。ここでａ＝ｔ／Ｎである。
【０１６６】
６．５  モーション符号化
この符号化の原理を図１３のフロー図に示す。
【０１６７】
［最下位レイヤにおける符号化］
最下位レイヤにおいて、符号化されたモーション情報はＧＯＰの最後の画像におけるメッシュ分割のポジションに関係している。
【０１６８】
ｉ．ＧＯＰの最初の画像におけるメッシュ分割のポジションと共に最後の画像におけるメッシュ分割のポジションの予測（１３１）が行われる。続いて予測誤差が上述したように符号化される（Ｐ型最下位レイヤ）。
【０１６９】
ｉｉ．推定から来るモーション情報はメッシュ分割の最も細かい階層レベルに対して与えられる。最も粗いレベルに向けて値が引き上げられる（１３２）。最も粗いレベルに対しては我々はこのレベルで作用するノードのポジションを有し、次により細かいレベルに対しては、新たなノード、中点ノード（mid-arc nodes）のポジションを有する。
【０１７０】
ｉｉｉ．値は０．５数量化単位で数量化される（１３３）。
【０１７１】
ｉｖ．続いて、数量化された値は、各階層レベルごとに異なる統計量を指定する算術符号器に送られる（１３４）。算術符号器はいくつかのシンボルを含むメッセージによって１セットの値を符号化する。シンボルは別々には符号化されない。結果として生じるメッセージがインターバルを使って表される場合、それぞれの可能なメッセージは確率ｐｉのインターバルＩｉ上で符号化される。算術符号器の統計量は各インターバルの確率の集合である。本発明のケースでは、符号器は確率を１／ｎで初期化する。ｎは符号化されるシンボルの数である。また最初は、メッセージはそれぞれ等確率である。集合の値が符号化されなければならないときはいつでも確率は更新される。全ての値が符号化されると、結果として生じるメッセージのインターバルに含まれる番号を送信すれば十分である。
【０１７２】
メッシュ分割のポジションの算術符号化は、各階層レベルごとに異なる統計量を使用する。というのは、ある与えられた階層レベルでの値は異なるレベルの間の値よりも互いに近づくチャンスがより大きいからである。値の類似は送信メッセージのサイズと符号化コストの利得を減らすことを可能にする。
【０１７３】
ｖ．メッシュ分割の有効なノードのみが符号化される。ノードはそれが有効な三角形に属する場合に有効である。また三角形はそれが画像のマスクにおける少なくとも１つのピクセルを再構成する場合に有効である。非有効なノードは画像のピクセルを一切再構成しないし、それらを符号化することは不必要である。
【０１７４】
［最上位レイヤにおける符号化］
ｉ．最上位レイヤにおけるモーション情報はＧＯＰの最初と最後の画像の間のメッシュ分割の中間的ポジションに関する情報である。このため、最後の画像のポジションが復号化され（１３５）、続いて中間画像のポジションが補間によって予測される（１３６）。残差の符号化が行われる。これら２つの画像におけるポジションと中間的ポジションとの間の補間の残差が符号化される（１３７）。ｍ（１）とｍ（Ｎ）がそれぞれ最初と最後の画像におけるメッシュ分割のポジションである場合、連続的に符号化された残差はｒｅｓ（ｔ）＝ｍ（ｔ）−ｍ（１）−（１−ｔ）／Ｎ＊ｍ（Ｎ）で与えられる。符号化された残差は有効なノードの残差である。
【０１７５】
ｉｉ．残差は（補遺１に与えられる）アントニーニ・フィルタ（Antonini filter）を有する「ゼロ側（zero side）」時間ウェーブレットによって変換される（１３８）。
【０１７６】
ｉｉｉ．続いて中間画像の残差モーションはウェーブレットモーションに変換される（１３９）。ウェーブレットモーションは階層レベルによるメッシュ分割の表現であって、各レベルごとに、ノードの与えられたポジションはこの階層レベルの最適なポジションである。最も粗いレベルはシーンの全体的な動きを与え、最も細かいレベルは局所的な動きの連続的な細分化を可能にする。各メッシュ分割レベルにおいて、符号化される情報は中点ポジション（mid-arc positions）で生まれた新たなノードである。ノードのポジションの精密化はより低いレベルにすでに存在する。
【０１７７】
ｉｖ．各階層レベルごとに最適なノードポジションを有する事実は各レベルでのビットレート／歪み（bit rate/distortion）最適化作業の実行を可能にする。
【０１７８】
ビットレート／歪み最適化プロセス１３１０は、最初に各階層レベルごとに、それぞれの数量化ステップに関連したビットレートおよび歪みの計算を必要とする。与えられたビットレートに対して、各階層レベルの異なるポイントの最適な組み合わせが探索される。この組み合わせはビットレートと歪みの間の最善の妥協案である。各レベルは与えれたモーションの質に対する影響を考慮した重みで重み付けされる。
【０１７９】
粗いレベルはより細かいレベルよりも大きな重みを有することになる。これは、最善の組み合わせを探索する際に、数量化ステップに関連した歪みは細かいレベルに対するよりもそれぞれの粗いレベルに対してより大きいことを意味する。実際、粗いレベルでの誤差は細かいレベルよりもよく目に見える。
【０１８０】
ビットレート／歪み最適化プロセスは最適な符号化を実現するために動きのそれぞれの階層レベルに適用されるそれぞれのビットレートに関連した数量化ステップを与える。
【０１８１】
ｖ．次に階層レベルの値は与えられたビットレートに対して数量化され、算術符号器に送られる（１３１１）。
【０１８２】
［ロッシー（不可逆）符号化（Lossy encoding）］
既存のスキームと比べて本発明の革新の１つは動きが不可逆に（ロッシーにあるいは損失を含んで）符号化されるということにある。ロッシー符号化された動きは、オリジナルのビデオと見栄えは同じだがピクセルレベルでオフセットを有するビデオの再構成を可能にする。
【０１８３】
実際、再構成されたビデオは動きおよびテクスチャに関する復号化された情報と合成される。動きのロッシー符号化は、人間の目は動きの欠陥に対してはテクスチャの欠陥に対するほど敏感ではないという事実を考慮している。従って、動きに関して得られたビットレートはテクスチャの符号化に影響し、それを改善する。
【０１８４】
６．７  テクスチャの符号化
この符号化の原理を図１２のアルゴリズムに示す。
【０１８５】
［より低いレイヤにおける符号化］
ｉ．符号化されるＧＯＰがイントラＧＯＰ（テスト１２１）である場合、ＧＯＰの最初の画像はＪＰＥＧ２０００符号器によるイントラ符号化（１２２）に従う。
【０１８６】
ｉｉ．ＧＯＰの最後の画像は最初の画像で予測される（１２３）。ＧＯＰがイントラＧＯＰである場合、予測に使用される画像は復号化されたＧＯＰの最初の画像である（１２４）。ＧＯＰがイントラＧＯＰでない場合は、それは前回の符号化・復号化されたＧＯＰの最後の画像である（１２５）。予測誤差はＪＰＥＧ２０００符号器によって符号化される（１２６）。
【０１８７】
［最上位レイヤにおける符号化］
ｉ．最上位レイヤにおいて符号化された遠端画像は、最下位レイヤと比較すると符号化の精密化である。ＧＯＰがイントラＧＯＰである場合、最上位レイヤにおける最初の画像はこの画像での符号化の精密化である。ＧＯＰがインターＧＯＰである場合、この画像に対する精密化は存在しない。
【０１８８】
ｉｉ．動きのケースのように、補間残差は補間された画像（１２８）を使用して中間画像で計算される（１２７）。Ｉ（１）とＩ（Ｎ）をＧＯＰの遠端画像とすると、ｒｅｓ（ｔ）＝Ｉ（ｔ）−Ｉ（１）−（１−ｔ）／Ｎ*Ｉ（Ｎ）である。
【０１８９】
ｉｉｉ．続いて残差は時間ウェーブレット変換によって変換される（１２９）。ウェーブレット変換はその「リフティング」フォームで使用され、使用されるファイルは５／３フィルタ（補遺１参照）である。
【０１９０】
上記変換は、動きの経路に沿った中間画像の残差に適用される。
【０１９１】
このとき、同じ基準画像を使用しない係数を計算する際にモーション補償が必要である。
【０１９２】
ｉｖ．上記変換は「ゼロ側（zero-side）」変換である。実行される補間では、変換される信号は遠端でゼロである。実際、ＧＯＰの最初と最後の画像の値は使用される補間によってゼロである。補間はＩ（ｔ）interp＝（１−ａ）*Ｉ（１）＋ａ*Ｉ（Ｎ）である。それぞれ０と１に等しいＩ（１）とＩ（Ｎ）に対しては、１とＮにおいて残差０を与える。
【０１９３】
図１１は、Ｉ（ｔ）−Ｉ（ｔ）interpと見なされる残差信号の形を与える。信号の形は線形補間による信号テクスチャ（および動き）の予測の有効性を示している。予測は遠端で正確であり、ＧＯＰの中央に近づくにときに若干劣化する。時間変換の際、変換信号は２およびＮ−１の間で定義される補間残差である。
【０１９４】
信号の端に位置する係数の計算の時には、サポートが無限長の信号のシミュレーションを可能にするために対称性が信号に適用される。しかしながら、１とＮ（これらのポイントで信号はゼロ）における信号の値から、変換は実質的に１からＮに適用されると考えられる。結果的に、端部に適用される対称性はもはや存在しないが、反対称性（anti-symmetry）が存在する。
【０１９５】
ｖ．ウェーブレット変換１２９から結果するサブバンドと遠端画像（それぞれ最初の復号化画像（１２４）と最後の復号化画像（１２１２）における残差１２１０と１２１１の計算によって得られる）の符号化の精密化はＪＰＥＧ２０００型のスケーラブルなプログレシブ符号器１２１４によって符号化される。
【０１９６】
空間ウェーブレット分解１２１３において使用されるウェーブレット分解のレベルはそれぞれ符号化される成分の性質に応じて別々に依存する。符号化残差はわずかなウェーブレット分解レベル、例えば唯一のレベル、で変換することが好ましい高い周波数であり、ブロックサイズは１６×１６が使用される。時間サブバンドに対して、サブバンドの周波数が考慮される。低い周波数に対しては、５つの分解レベルが使用される。非常に高い周波数に対しては３つのレベルが使用される。中間の周波数に対しては４つの分解レベルが使用される。ブロックのサイズはサブバンドが何であれ６４×６４である。
【０１９７】
６．８  ビットストリーム
ビットストリームは、低レベルテクスチャストリーム、低レベルモーションストリーム、リフティングテクスチャストリーム、リフティングモーションストリームを含む、４つの符号化の結果生じる４つのビットストリームによって形成される。ビットストリームのレイアウトはビットストリームを必要とするアプリケーションに依存する複数フィールドのレイアウトである。
【０１９８】
そのアプリケーションは３つの有効なフィールド、動き、テクスチャおよび形、を有する。それぞれのフィールドはどこでもカットすることができ、ベーシックなクオリティは各フィールドごとに各フィールドの最下位レイヤの情報によって提供される。アプリケーションは各フィールドごとに所望のクオリティ（動き、テクスチャおよび形）を選択することができる。次いで、結果として生じるフィールドはユーザに伝送されるビットストリームを形成するために多重化される。
【０１９９】
６．９  復号化プロセス
復号化プロセスはバイナリストリームの動きおよびテクスチャ情報を取り出す。最初に動きが復号化され、次にテクスチャが復号化される。
【０２００】
［動きの復号化］
一様な階層的メッシュ分割が復号器によって、符号器によって行われたのと同じ方法で、最初の画像で生成され、従って符号器と復号器の初期のメッシュ分割は同一である。次に最後の画像における動きのポジションが復号化され、最初の画像のメッシュ分割のポジションがこれらのポジションに加えられる。
【０２０１】
中間の画像のポジションは、符号化において行われるように、最後の画像と最初の画像におけるポジションによって補間される。次いで、最上位レイヤのモーション情報がパラメータとして指示されたビットレートで復号化される。
【０２０２】
復号化された情報は動きの空間／時間サブバンドに対応する。逆ウェーブレットモーション変換がサブバンドに適用され、続いて逆時間ウェーブレット変換（補遺１のAntonini合成フィルタ）が適用される。得られた残差は以前に補間された値に加えられる。
【０２０３】
［テクスチャの復号化］
テクスチャの復号化は動きの符号化に似ている。しかしながら、現在のＧＯＰがイントラＧＯＰであることを確かめる必要がある。これが当てはまる場合、復号化すべき最下位レイヤのテクスチャに関する最初の情報はＧＯＰの最初の画像のテクスチャである。この画像が復号化されるとすぐに、最後の画像の残差が復号化され、最後の画像の予測に加えられる（予測は最初の画像による符号化によるものと同じ方法で行われる）。
【０２０４】
続いて中間の画像が符号化で行われたように補間される。ＧＯＰがインターＧＯＰである場合、ＧＯＰの最後の画像の予測が前のＧＯＰの最後の復号化された画像を使って行われる。次に最上位レイヤのテクスチャに関する情報が復号化される。ＧＯＰの最初と最後の画像の符号化残差がそれぞれそれに加えられる。
【０２０５】
中間の画像の時間サブバンドが５／３ウェーブレットリフティングによって変換される。順変換および逆変換におけるリフティングに使用されるフィルタは同一で、補遺２に説明されるリフティングの原理に依れば、２つのステップの符号のみが逆転している。
【０２０６】
得られた残差は以前に補間された中間の画像に加えられる。
【０２０７】
［ビデオシーケンスの合成］
ビデオシーケンスの合成はテクスチャ画像をそれらのオリジナルのサンプリンググリッド上に投影する。これは動きおよびテクスチャを結合してオリジナルのビデオシーケンスにできるだけ近い合成されたビデオシーケンスを最終的に取得する段階である。
【０２０８】
［再構成されたビデオシーケンスのクオリティの測定］
再構成されたビデオとオリジナルのビデオとの間のＰＳＮＲ（peak signal-to-noise ratio）の計算は視覚的なクオリティを判断するための信頼できる基準を与えない。実際、動きのロッシー符号化は、ビデオシーケンスがオリジナルシーケンスと比べてずれて合成されることを意味しており、計算されたＰＳＮＲはこのときこのシフトだけバイアスがかかっている。
【０２０９】
合成されたシーケンスのクオリティを測定するために使用される基準はテクスチャ画像のフィールドで計算されたＰＳＮＲである。また人間の肉眼は欠陥が一定の閾値未満のままの状態にある程度まではシーケンスのモーション欠陥に敏感でないといことが仮定されている。
【０２１０】
結果、テクスチャＰＳＮＲは、オリジナルのテクスチャ画像と復号化されたテクスチャ画像との間の歪みを計算するもので、合成されたシーケンスの復元されたクオリティの測定値を提供する。
【０２１１】
６．９  メッシュ分割に基づく動き推定によって生成された逆転の管理
［原理］
変形可能メッシュ分割はビデオシーケンスの実際の動きが本来不連続でもモーションフィールドの連続表現を定義する。このため、異なる平面とオブジェクトがシーンの中で重なると、隠れてカバーされないゾーンが現れて不連続線が生じる。
【０２１２】
全体のメッシュ分割によってこのような人工物のモデルを構築することは、シーンを構成するビデオオブジェクトに基づいて分割されたメッシュ分割とは反対に、表現モデルを修正することなしには解決できない困難を構成する。挑戦はこの視覚的な劣化をなくすことだけなく、分解の観点から欠陥ゾーンを特定する中でそれを抑えることにある。
【０２１３】
通常、この問題を解決するために、２つのタイプの技術が使用される。１つは後処理（post-processing）で、もう１つはノンリバーサル条件の設定である。
【０２１４】
後処理は２つのタイプのシナリオに基づいて実行することができる。第１のタイプのシナリオ（帰納的補正）はモーションベクトルを適用することにあるが、問題のあるベクトルを検出してそれらの値を補正するようにする。第２のタイプのシナリオは逐次代入法で、期待されるシフトの一部を各逐次代入ごとにノードに加えて逆転が存在しないようにし、そのプロセスが収束するまでのループを設定することにある。
【０２１５】
後処理法は推定がなされるとすぐに実施され、その結果は次善最適である。というのは、モーションベクトルは予測誤差の最小化への寄与とは無関係に補正されるからである。従って１つの改善策は最適化プロセスの際にノンリバーサル条件を考慮に入れてフィールドを最適化することにある。
【０２１６】
この目的のため、動き推定は拡張ラグランジェ法（augmented Lagrangian）を予測の平均自乗誤差に適用することにある。このラグランジェ法は三角形がゼロ面積三角形に近づくときに三角形の変形の補正を可能にする。この技術により、この問題の最適な解決法をそれが連続フィールドを表す場合に効率的に決めることが可能になる。次に、ビデオシーケンスの性質は不連続的であるので、オブジェクトの出現または消失を生み出すことによって不連続のゾーンを復元するためにそれらを特定するための別の技術を使用することが可能である。
【０２１７】
［本実施形態に使用されるアプローチ］
仏国特許FR-99 15568号明細書において、このアプローチはメッシュ分割をベースとするモーション推定器によって生み出された逆転の問題を解決する。
【０２１８】
そのアプローチでは動き推定器に２つの連続する瞬間ｔ１およびｔ２の間で逆転を作り出させる。逆転ゾーンを特定する際には、不連続ゾーンが検出される。プロセスは次に、議論される２つの画像の間の予測誤差を最小化するために欠陥ゾーン（少なくとも１つの逆転を含むゾーン）を排除する際にｔ１およびｔ２の間で新たな動き推定を行う。
【０２１９】
この再最適化は連続ゾーンに対する最適なモーションベクトルを決定するために使用され（ｔ１およびｔ２の間の全単写を仮定）、不連続ゾーンによって生み出された以前の最適化において得られたモーションベクトルの値の乱れを抑える。
【０２２０】
このアプローチでは、欠陥ゾーンは３つの異なる方法で処理することが可能である。
【０２２１】
［人工的プロパゲーション］
最初のアイデアは、欠陥ゾーンを除いたメッシュ分割の、INSIDE頂点と称される頂点のモーションベクトルを、関心のある三角形の密度を最適化した欠陥ゾーンの頂点に向けて、人工的にプロパゲート（伝搬）させることにある。このプロパゲーションはモーションベクトルがそこで最適化されているピラミッドの最低レベル（Ｌｍレベル）の頂点に適用される前後二重の反復（折り返し）走査に基づく。このアプローチは１９９４年９月２１に仏国グルノーブル（Grenoble）にあるジョセフ・フーリエ大学（Universite Joseph Fourier）に提出されたEdouard THIEL著・学位論文「画像解析における面取り距離−基礎とその応用（Les distances de chanfrein en analyse d'images : fondements et applications" (Chamfer distances in image analysis: foundation and applications））」にある面取り距離写像の計算に基づく。それは以下のアルゴリズムに従う。
【０２２２】
アルゴリズム
・Lmのすべての頂点Sに対して
・INSIDE(S)の場合にはＳはPROPAGATEDになる
それ以外の場合、Ｓはnon-PROPAGATEDになる
・未定義のモーションベクトルが残っている限り反復せよ
・一番上左から一番下右まで走査されるLmのすべての頂点Sに対して、
・・・・non-PROPAGATED(S)かつＳが少なくとも２つのPROPAGATEDな隣接点を有す      る場合
MOTION(S)=PROPAGATEDな隣接点のMOTIONの平均
ＳはPROPAGATEDになる
・一番下右から一番上左まで走査されたLmのすべての頂点Sに対して
・・・・non-PROPAGATED（S)かつＳが少なくとも２つのPROPAGATEDな隣接点を有す      る場合
MOTION(S)=PROPAGATEDな隣接点のMOTIONの平均
SはPROPAGATEDになる
・Lm-1からL0にわたってピラミッドのすべての頂点Ｐに対して
・・・・MOTION(P)=MOTION(F)、ＰはＦの親である
【０２２３】
２つの他の技術を使用することも可能である。１つは頂点の出現または崩壊、もう１つはn-manifoldメッシュ分割である。
【０２２４】
［頂点の崩壊］
第１の方法は、復号器において、対向するモーションベクトルに頂点を有する三角形によって決まる隠蔽ゾーン（concealment zone）を検出することを含む（ＣＡ基準）。事実上、検出された三角形は、頂点が異なるオブジェクトの中に置かれているので、逆転させることが可能である（２つのオブジェクトの１つは隣のオブジェクトを隠す）。
【０２２５】
この場合、正反対の動きを有する２つの隣り合う頂点の間で辺の合併（edge merger）または辺の崩壊（edge collapse）を実行することが提案される。従ってこの結果、ある三角形が消失して、オブジェクトの一部の消失を表している。
【０２２６】
この原理を図１５に示す。
【０２２７】
［”n-manifold”メッシュ分割］
第２の方法はn-manifoldメッシュ分割において機能することにある（１つの辺はいつもはｎ＝１または２の代わりにｎ＞＝２個の三角形に共有されることがある）。これを行うため、動き推定が実行される。隠蔽ゾーン（三角形の逆転）が検出されると、それらのゾーンに付随する三角形がフラグOVERLAPPED（新フラグ）でマークされる。
【０２２８】
続いて動きの最適化がOVERLAPPED三角形を除いて実行し直される。第２の最適化は新たな三角形の逆転をもたらすことがある。これらの三角形もOVERLAPPEDでマークされ、最適化が再度計算される。こうしてOVERLAPPEDゾーンは露出（decouvrements（仏））または覆い隠し（recouvremnets（仏））をマークする。
【０２２９】
OVERLAPPEDでマークされたゾーンはそれ故に隠蔽されているオブジェクトに対応する。選ばれたアイデアはこれらの三角形を一時的に取り除いて、それと同時にそれらをメモリに保存して将来の再出現を経済的に管理することができるようにすることにある。
【０２３０】
OVERLAPPEDメッシュ再分割（sub-meshing）のトポロジーによれば、２つのケースが生じる。
・メッシュ再分割の境界が引き出される。メッシュ分割はn-manifoldメッシュ分割（ｎ＝３）になる。
・メッシュ再分割の境界の一部分のみが引き出され、この場合、局所的なイントラ補正がその他のOVERLAPPEDメッシュ上で実行されなければならない。
【０２３１】
n-manifoldメッシュ分割を使用するという事実はシーケンスの間の様々な時間に消失のみならず再出現することが可能なゾーンに関する光度情報を保存する。
【０２３２】
このような”n-manifold”メッシュ分割の一例を図１６に示す。
【０２３３】
６．１０  メッシュ分割の逆転の管理の実施例−退化または逆転した三角形の検出および分離
メッシュの逆転を抑えるために、逆転の原因となり得る三角形が１からｔの推定の最後に検出される。これらの三角形は退化した形状を有し、動き推定に乱れを引き起こす。それらは露出または覆い隠しのゾーンを示唆する。
【０２３４】
検出されると、これらのメッシュはメッシュ分割の残りから分離され、推定はそれらのゾーンを考慮することなく再開される。同様に、逆転した三角形が検出され、メッシュ分割から分離される。逆転した三角形の検出は三角形が正の向きまたは負の向きに指定されたかどうかをチェックすることによって行われる。最初、全ての三角形は正の向き（順方向）に向き付けられる。そして三角形のベクトル積の計算の際に符号が負の場合にはその三角形は逆転している。退化した三角形の検出は画像１および画像ｔの間で三角形の変形を調べることによって行われる。
【０２３５】
三角形の変形は１からｔまで三角形のモーションパラメータを議論して調べることができる。（ｘ、ｙ）を１におけるあるポイントのポジション、（ｘ’、ｙ’）をｔにおけるそのポイントのポジションとすると、アフィン（affine）モーションのパラメータは以下のようなものである。
ｘ’＝ａｘ＋ｂｙ＋ｃ
ｙ’＝ｄｘ＋ｅｙ＋ｆ
行列表現を使えばこれは次のように表される。
【数３】
2006521048.tif 000005
この式で、Ｂは並進パラメータ、Ａは拡大（ズーム）・回転パラメータを表す。並進は三角形を変形しないので、我々は行列Ａのみを見る。ＤをＡの対角化行列とする。
【数４】
2006521048.tif 000006
λ1とλ2は行列Ａの固有値である。
【０２３６】
最初に変形がトータルズーム（全体的拡大）であるかどうかを知るために固有値の比が調べられる。固有値の比はＡのトレースとＡの行列式を通じて計算されることがある。
【０２３７】
トータルズーム（ｘとｙにおいて同じ大きさで解像度が変化する）の場合、三角形は変形されたと見なされない。というのは、その構造はスケールファクタを除いてｔと１で同じであるからである。
【０２３８】
固有値の比が１と異なるとすれば、変形は両方の意味で同じではない。このときＡの固有値が調べられる。ｘをＡの固有値の１つであるとして、三項式ｘ＿−ｔｒａｃｅＡ＿*ｘ＋（ｄｅｔＡ）＿の解がＡの２つの固有値を与える。固有値の値に応じて、三角形は退化しているまたは退化していないと見なされる。それが退化している場合、それはメッシュ分割から分離される。
【０２３９】
６．１１  マルチグリッドアプローチに基づく動き推定
入れ子状階層的メッシュ分割における２つの画像の間の動き推定のための方法に関するSept 98(98 11 227)において提示されたアルゴリズムの収束性を改善するために、応用数学分野から導き出された、マルチグリッド法として知られる新規の技術を開発した。
【０２４０】
これを実行するために、有限要素法に関連したマルチグリッドアプローチを説明しよう。
【０２４１】
ｕ∈ＶN、ａ（ｕ，ν）＝Ｌ（ν）、∀ν∈ＶN        （Ｉ）
について探索を行う。ＶNはサイズＮのベクトル状態、ａ（ｕ，ν）はＶN×ＶN上の双一次形式、Ｌ（ν）はＶN上の線形形式を表す。
【０２４２】
サイズＭ＜Ｎ、ＶM⊂ＶNなる各部分空間ＶMごとに、以下のように２つのレベルの解像度を構築することが可能である。
ｕ〜∈ＶNが与えれると、精密解ｕの近似として、補正ｃ＝ｕ−ｕ〜は以下の関係を満足する。
ｃ∈ＶN、ａ（ｃ，ν）＝Ｌ（ν）−ａ（ｕ〜，ν）、∀ν∈ＶN        （ＩＩ）
【０２４３】
ｃの近似ｃMは以下のように定義される。
ｃM∈ＶM、ｃMは次の関係を満足する。
ａ（ｃM，ｗ）＝Ｌ（ｗ）−ａ（ｕ〜，ｗ）、∀ｗ∈ＶM      （ＩＩＩ）
【０２４４】
異なる問題の行列表現を調べることにする。φi、１≦ｉ≦ＮをＶNの基底関数、そしてΦj∈ＶM、１≦ｊ≦ＭをＶMの基底関数とする。
【０２４５】
Φj∈ＶM⊂ＶNであるので、次のような展開係数ｒijが存在する。
Ｒを成分値がｒijであるＬ（ＲN，ＲM）の行列とする。ｙ＝ΣjｙjΦjと書かれる関数ｙ∈ＶM⊂ＶNは以下のようになる。
Σj,iｙjｒjiφi＝Σiｘiφi
ここでｘi＝Σj，iｙjｒji、これを行列で表すとｘ＝Ｒtｙ（ＲtはＲの転置行列）。
（Ｉ）がΣiｕiφiと書かれた場合の解ｕ
再びｕ∈ＲNを成分ｕiのＮ次元ベクトルとする。行列Ａ∈Ｌ（ＲN）とベクトルｂ∈ＲNは次のように定義される。
ａij＝ａ（φj，φi）およびｂi＝Ｌ（φi）
ｕは以下のような線形方程式の解であることが分かる。
Ａｕ＝ｂ
ｃは（ＩＩ）の解であって次式を満足する。
Ａｃ＝ｂ−Ａｕ〜
ｃMは（ＩＩＩ）の解であって次式を満足する。
（ＲＡＲt）ｃM＝Ｒ（ｂ−Ａｕ〜）
【０２４６】
ＶNで提起された問題に対してＶMにおける近似を定義するこのシステマチックな方法によって、同一のドメイン上、すなわち細かいメッシュ分割に対応するドメイン上で全て定義された関数の構築が、たとえそれらが粗いメッシュ分割のノードに割り当てられたパラメータによって特徴付けられているとしても、可能となる。
【０２４７】
図１７にこのアプローチの一例を示す。細かいメッシュ分割１７１に正確な粗いメッシュ分割１７２と不正確な粗いメッシュ分割１７３が結び付けられる。
【０２４８】
アルゴリズムの理解を容易にするために、２つのグリッド上で線形システムＨｄ＝Ｆを解くことにする。
【０２４９】
線形システムＨｄ＝Ｆは細かいグリッド上で書かれる。
【０２５０】
Ｐを細かいグリッド上での粗いグリッドの拡張（エクステンション）オペレータとする。２グリッド法（two-grid method）は以下のように構成される。
【０２５１】
何回かのGauss Seidel逐次代入（例えば）の後に、近似ｄ〜が得られたとすると、残差Ｆ−Ｈｄ〜が計算される。ｄ〜に加えられるべき補正ν＝Ｐｗについて探索が行われる。ｗは以下のような方程式の解である。
ＱＨＰｗ＝Ｑ（Ｆ−Ｈｄ〜）
【０２５２】
従って粗いグリッド上のオペレータは行列ＱＨＰによって表現される。
【０２５３】
Ｑ＝Ｐtは可能な制限オペレータであることに注意されたい。これは、Ｈが正定値対称行列であったとすると、行列Ｈのベクトル空間ＩｍＰ（Ｐの像）への制限である正定値対称行列ＰtＨＰをもたらす利点を有する。
【０２５４】
拡張オペレータＰ、Ｑ＝Ｐtを決定しよう。
【０２５５】
Ｐが、以下の公式、
【数５】
2006521048.tif 000007
（ｈは細かいメッシュ分割の離散化ピッチ（discretization pitch）、Ｈは粗いメッシュ分割の離散化ピッチである。）
によって定義される、正則（regular）メッシュ分割上の双一次拡張オペレータである場合には、Ｐtは以下のような多様な「加重平均」オペレータである。
ＰtＶH（ｊ、ｋ）＝
Ｖh（ｊ、ｋ）＋０．５［Ｖh（ｊ1、ｋ1）＋・・・＋Ｖh（ｊv、ｋv）］
ここでｖは（ｊ、ｋ）の価数を表す。古典的な単射オペレータをとると、
Ｑ＝Ｐt
は成り立たない。
【０２５６】
粗いグリッド上における簡約化した行列ＰtＨＰの計算
Ｈは、変分問題の離散化の結果生じ、各ポイント（ν＋１）ごとに、未知関数の値、すなわち問題にしているポイントとｖ個の最も近い隣接点での値、に作用する。
【０２５７】
Ｖ（ｏ）をポイントｏおよびｖ個の最も近い隣接点の近傍とする。
細かいグリッド（ＩＶ）上における粗いグリッドの拡張オペレータＰは図１８に示すように選ばれるとしよう。
【０２５８】
ｉを粗いグリッドのポイントＧiのインデクス、ｋを細かいグリッドのポイントＦkのインデクスとすると、行列Ｐの係数は以下のような値を採る。
【数６】
2006521048.tif 000008
【０２５９】
行列の積の一般公式からＢ＝ＰtＨＰに対しては成分表示で次のように書くことができる。
Ｂij＝Σkl（Ｐt）ijＨklＰlj＝ΣklＰkiＨklＰlj
【０２６０】
Ｂijがノンゼロになるためには、Ｈkl≠０となるような、すなわちｋとｌは隣接点、全ての隣接点は細かいグリッド上に存在するような、少なくとも１つのインデクスｋ∈Ｖ（ｉ）と少なくとも１つのインデクスｌ∈Ｖ（ｊ）が存在しなければならない。
【０２６１】
インデクスｉとｊを持つポイントが粗いグリッド上の隣接点である場合を除いてはＢijはノンゼロに成り得ないことを示すのは容易である。
【０２６２】
［単純化したアルゴリズム原理（２つのグリッド上）］
図１９に示した粗いグリッド１９１と細かいグリッド１９２を使用して、以下の段階が１サイクル実行される。
【０２６３】
ｉ．ピッチｈの細かいグリッド上で何回か（一般的に２、３回）のGauss Seidel逐次代入（例えば）を実行する、
ｉｉ．細かいグリッド１９２上で残差を計算する、
ｉｉｉ．この残差をピッチＨ＝２ｈの粗いグリッド１９１上に制限する、その制限は加重平均によって行われる、
ｉｖ．補正の近似を得るために粗いグリッド上でシステムを解く、
ｖ．細かいグリッド１９２上で得られた近似解を補正するために細かいグリッド１９２上でこの補正を補間する。
【０２６４】
この段階の最後に、細かいグリッド上の残差があまりに大きい場合、最初の段階のスタートから操作を再開してもう１回サイクルが開始される。粗いグリッド上でシステムを解くために、２グリッド法を再度使用することが可能である。この場合、マルチグリッド法が使用される。
【０２６５】
［幾何マルチグリッドの原理］
幾何マルチグリッドは上述したアプローチを使用するが、連続するレベルにわたってノードにメッシュ分割の幾何学的変形を考慮したウェイトで重み付けすることが求められる。実際、すでに使用されたウェイトは細かいメッシュ分割をより低いレベルの正則メッシュ分割から再構成するために使用される。
【０２６６】
しかしながら、メッシュ分割が変形されると、これらのウェイトはより下位のメッシュ分割の構造を保つために使用することができない。より下位のメッシュ分割の構造を保つために、図２０に示すように、あるレベルから別のレベルまでシフトの影響を受けるノードに使用される重み付けを修正することが提案される。
２０１：粗いメッシュ分割のノードの変形、
２０２：細かいメッシュ分割のノードの変形、
２０３：細かいメッシュ分割の変形、
・２０３１：ノーマルな変形（点線）、
・２０３２：マルチグリッド変形（太線）。
【０２６７】
２つの連続する階層レベルの間で、細かいメッシュ分割のノードはそれらが属する粗いレベルの三角形に関するそれらの重心座標によって表されることがある。このとき２つのタイプのノード、つまり上位レベルのノードおよび上位レベルのリッジの中間にあるノード（mid-ridge nodes）の直系子孫であるノード、が細かいメッシュ分割レベルで区別される。
【０２６８】
直系子孫のノードは直に親の値を採る。その他のタイプのノードに対しては、４つのノードがノードの値の線形結合で関与する（come into play）ことがあり得る。２つの三角形の４つのノードは上位レベルのリッジを含む。ノードがそのリッジ上にある場合、そのリッジの両端にある２つのノードのみが関与し、そのリッジを含む２つの三角形のその他の２つのノードの重心ウェイトはゼロ値である。ノードがそのリッジ上にない場合、関与するノードは細かいレベルのノードが属する上位レベルの三角形の３つのノードである。
【０２６９】
２つの連続するレベルの間の遷移行列は非常に疎（hollow）である。２つの不連続なレベルの間の遷移行列を、
Ｈll-k＝Ｈll-1Ｈl-1l-2・・・Ｈl-k+1l-k
で定義することは可能である。Ｈll-1は２つの連続するレベルの間の遷移行列である。
【０２７０】
［補足情報］
より詳細な説明とこのマルチグリッド法を改良するための提案については補遺４を参照されたい。
【０２７１】
６．１２  メッシュ分割の追跡−ビデオオブジェクトの動的なモザイクの構成
［メッシュ分割の追跡］
前のセクションで提示された動き推定法は２つの連続する画像の間で動きを推定するために使用される。メッシュ分割を時間で追跡することは、次のメッシュ分割のポジションが利用可能な画像ｔと、画像ｔ＋１との間で動きを推定することにある。画像ｔ上のメッシュ分割は変形された画像であり、正則なメッシュ分割に基づく階層的古典的な推定はすぐに行き詰まることがあり得るので、マルチグリッド推定法の使用はこの段階において極めて重要である。
【０２７２】
提案された追跡アルゴリズムを図２８に示す。
【０２７３】
動き推定は２つの段階で行われる。最初に、画像ｔと画像ｔ＋１の間で、精密化操作が画像ｔ＋１と処理済みシーケンスの最初の画像との間で実行される。基準画像はノイズを抑えるだけでなくテクスチャの時間的変化（後述の動的モザイク参照）を考慮に入れるためにフィルタ処理されることがある。
【０２７４】
フィルタ処理された画像の使用は特にビデオオブジェクトモザイクの生成、そこでは瞬間ｔにおけるオリジナル画像のテクスチャよりも瞬間ｔにおけるモザイクのテクスチャを使用することが好ましい、に使用される。初期画像と瞬間ｔ＋１における画像との間のモーション精密化の段階は、提案された符号化スキームに使用されるｔの方へのタイプ１の画像補償の際に画像の描画を最適化するために行われる。
【０２７５】
［ビデオオブジェクトの動的なモザイクの生成］
メッシュ分割を時間の経過中に追跡し、サポートマスク（追跡されたビデオオブジェクトの、あるいは、モノオブジェクトシーケンスの場合には単に画像の）を使用することにより、追跡されたオブジェクトのモザイクを生成することが可能である。このモザイクは、時間内に観測されたテクスチャに関する情報を統合し、観測されたカバーしていないゾーンを埋めることを可能にする。
【０２７６】
モザイクの構成の原理を図２９に示す。
【０２７７】
古典的なモザイク画像再構成アプローチと比較すると、提案された方法は、通常の制約（深さが比較的浅い仮定を置くためにオブジェクトがカメラから離れていること、カメラの移動が”パン・アンド・チルト（pan and tilt）”タイプの動きに制限されること、など）によって制限されることなく、時間発展している変形可能なオブジェクトの管理を可能にする。これはトータルモーション補償ツール（アフィン、パノラマ、グラフィックその他のタイプの動き）を階層的メッシュ分割によるモーション補償のためのツールで置き換えることによって行われる。
【０２７８】
使用される階層的モーションの表現とウェーブレット表現とのより密接なつながりにより（［Marquant-2000］参照）、動きを推定サポートを超えて延長することが可能となる。
【０２７９】
生成されたモザイク画像は画像において観測された値に基づいて時間を追って徐々に更新される。新たなゾーンの更新はモザイクにすでに存在するゾーンの更新とは以下のように区別される。
【数７】
2006521048.tif 000009
上の関係はリセットされていないゾーンにおけるもので、下の関係はすでにリセットされたゾーンにおけるものである。
【０２８０】
パラメータαはモザイクの時間的変化に対して実行されるフィルタ処理をチェックするために使用される。値０は固定されたモザイクに対応する。値１は観測された値のフィルタ不処理に対応する。中間的な値は観測された値の時間的Kalmanフィルタ処理を実行するために使用される。
【０２８１】
このフィルタ処理はビデオ信号をノイズ除去する、あるいは他に符号化される情報の時間的な高い周波数の大きさを小さくするのに有用な場合がある（３Ｄウェーブレットアプローチを用いた動的モザイクの符号化を参照）。
【０２８２】
この分解が行われてしまえばモザイクは完成する。最初に、異なる時点で得られた値は未来から過去へプロパゲートする。プロパゲーションは定義された値をまだ有していない場所だけで行われる。最後に、定義されないゾーン（これに対し観測を行うことは不可能であった）を完成するためにパディングが行われる。
【０２８３】
［６．１３  本発明の補足的な特徴］
すでに言及したように、本発明は、符号化方法、復号化方法および対応する信号に関するが、以下の特徴も有する。
【０２８４】
［符号器（符号化装置）］
本発明に係る符号器は、原画像と対応する推定画像とを比較することによって得られる残差（residues）と称される差分画像（difference images）に適用されるウェーブレット符号化手段を含む。
［復号器（復号化装置）］
本発明に係る復号器は、有利な形態として、
モーション画像を形成するために動きに関係する残差の少なくとも一部を考慮してその動きを復号化するための手段と、
テクスチャ画像を形成するためにテクスチャに関係する残差の少なくとも一部を考慮してそのテクスチャを復号化するための手段と、
テクスチャ画像をモーション画像上に投影することによって、原画像のシーケンスに対応する、復号化された画像のシーケンスを合成するための手段と
を含む。
【０２８５】
［データサーバ（Data server）］
本発明に係るデータサーバは、少なくとも一部の原画像に対して、モーション画像と称される動作を表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行することによって得られる、原画像のシーケンスを表現する信号を記憶し且つ少なくとも１つの端末装置に伝送することが可能であって、前記信号は、原画像と対応する推定画像との比較によって得られる残差と称される差分画像に適用されるウェーブレット符号化を表すデジタルデータを含むことを特徴とする。
【０２８６】
［データ搬送波（data carrier）］
本発明に係るデータ搬送波は、端末装置によって読み出しが可能であり、少なくとも一部の原画像に対して、モーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行することによって得られる、原画像のシーケンスを表現する少なくとも１つに信号を搬送する。この搬送波は、原画像と対応する推定画像との比較によって得られる残差と称される差分画像に適用されるウェーブレット符号化を表すデジタルデータを含む。
【０２８７】
［コンピュータ符号化プログラム］
本発明に係るコンピュータプログラムは、少なくとも一部の原画像に対して、モーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行して、原画像シーケンスの符号化を実行するための命令を備える。このプログラムは、特に、原画像と対応する推定画像との比較によって得られる残差と称される差分画像に適用されるウェーブレット符号化手段を含む。
【０２８８】
［コンピュータ復号化プログラム］
本発明に係るコンピュータプログラムは、少なくとも一部の原画像に対して、モーション画像と称される動きを表す情報とテクスチャ画像と称されるテクスチャを表す情報とを生成するモーション／テクスチャ分解とウェーブレット符号化とを実行して符号化された原画像シーケンスの復号化を実行するための命令を備える。前記ウェーブレット符号化は原画像と対応する推定画像との比較によって得られる残差と称される差分画像に適用される。それは、
モーション画像を形成するために動きに関係する残差の少なくとも一部を考慮してその動きを復号化するための手段と、
テクスチャ画像を形成するためにテクスチャに関係する残差の少なくとも一部を考慮してそのテクスチャを復号化するための手段と、
テクスチャ画像をモーション画像上に投影することによって、原画像のシーケンスに対応する、復号化された画像のシーケンスを合成するための手段と
を含む。
【０２８９】
［補遺１：使用されるフィルタ］
１．Antoniniフィルタ：７／９フィルタ
M.Antonini、M.Barlaud、P.Mathieu、およびI.Daubechies共著、「ウェーブレット変換を用いた画像符号化（Image coding using wavelet transform）」、画像処理に関するＩＥＥＥトランザクションズ（IEEE Transactions on Image Processing）、１９９２年発行、第１巻、ｐ．２０５〜２２０参照。
Antonini合成（シンセシス）＝｛
-6.453888262893856e-02, 
-4.068941760955867e-02, 
4.180922732222124e-01,
7.884856164056651 e-01, 
4.180922732222124e-01,
-4.068941760955867e-02, 
-6.453888262893856e-02｝；
Antonini分解（アナリシス）＝｛
3.782845550699535e-02,
-2.384946501937986e-02, 
-1.106244044184226e-01, 
3.774028556126536e-01,
8.526986790094022e-01,
3.774028556126537e-01,
-1.106244044184226e-01, 
-2.384946501937986e-02, 
3.782845550699535e-02｝；
【０２９０】
２．５／３フィルタ：Cohen-Daubeschies-Feauveau双直交（２，２）
【数８】
2006521048.tif 000010
【０２９１】
３．リフティング構成の５／３フィルタ
【数９】
2006521048.tif 000011
【０２９２】
［補遺２：リフティングの原理］
信号のフィルタ・バンクによる変換（コンバージョン）は２つの異なる構成、畳み込み構成またはリフティング構成、のいずれかで行うことができる。畳み込み構成は最もよく知られており、計算コストと丸め誤差の点で最もコストがかかる。２つのフィルタ、１つはハイパスフィルタＨ、もう１つはローパスフィルタＬ、による１Ｄ信号ｓ（ｔ）のウェーブレット変換（コンバージョン）に対して、変換された畳み込みウェーブレットは次のようになる。
ｂｆ（ｔ）＝ΣkＬ（ｋ）*ｓ（ｔ−ｋ）
ｈｆ（ｔ）＝ΣkＨ（ｋ）*ｓ（ｔ−ｋ）
上式においてｂｆは低周波数、ｈｆは高周波数である。
【０２９３】
低周波数と高周波数は初期信号と同じ情報数を保つために２（ダウン・サンプラ）で間引きされる。図２２において、信号Ｘはハイパス・フィルタ２２１とローパス・フィルタ２２２を使用して低周波数と高周波数へ分割され、２（ダウン・サンプラ）で間引きされる２２３、２２４。
【０２９４】
図の右側半分は信号の再構成を示すものである。ロー（low）信号２２５とハイ（high）信号２２６は２（アップ・サンプラ）で拡張され（それぞれの値の間にゼロを補間する）、合成フィルタ２２７と２２８でフィルタ処理された後、合成される２２９。
【０２９５】
リフティング構成は畳み込み構成で行われたように信号を低周波数成分と高周波数成分に分解するが、そのスキームは丸め誤差を管理して計算コストをより低く抑えるという利点を有する。リフティング構成では（図２１参照）、変換（コンバート）される信号Ｘは最初にオペレータSPLIT２１１によって信号ｘevenと信号Ｘoddを得るために２つに分離される。
【０２９６】
実際、ｘevenは偶パリティインデクス信号のサンプルを含み、Ｘoddは奇パリティインデクス信号のサンプルを含む。
【０２９７】
続いて、オペレータＰ２１２は奇パリティ信号を偶パリティ信号で予測する、Ｘ∧odd＝Xeven。予測信号Ｘ∧oddはＸoddから減じられ、結果として生じる信号は信号の高周波数成分である。偶パリティ信号はオペレータＵ２１３によって更新される。結果として生じる信号は信号の低周波数成分である。リフティング段階は２つのフィルタリグ操作ＰとＵから構築される。ウェーブレット変換は更新された信号に毎回適用される一連のリフティング段階である。
【０２９８】
リフティングスキームの逆はシンプルで高速である。加算を減算で逆転させれば十分で、オペレータＰとＵは変わらない。畳み込みフィルタのリフティング版は畳み込みフィルタのユークリッド除法によって計算することができるが、リフティングフィルタは畳み込みフィルタとの対比で何の均等物もなしに生成されることがある。本符号器では、リフティングに使用されるフィルタのみが既存の畳み込みフィルタである。以下に、既存の畳み込みフィルタに基づくリフティングスキームの構成を示す。
【０２９９】
図２２を参照してウェーブレット変換による分解と合成について説明する。低周波数Ｂｆは信号Xをローパス・フィルタｈ〜でフィルタ処理して、その後にフィルタ信号を間引きすることによって得られる。高周波数Ｈｆはハイパス・フィルタｇ〜で信号をフィルタ処理して、その後にフィルタ信号を間引きすることによって得られる。信号の再構成はフィルタｇおよびｈによるフィルタ処理によって行われ、再構成された信号Ｘｒが得られる。
【０３００】
我々はフィルタｈ〜をより陽に使って低周波数Ｂｆの計算を展開すべきである。
【数１０】
2006521048.tif 000012
【０３０１】
ローパス・フィルタを使って信号Ｘをフィルタ処理した後、変換された係数を間引く。残りの係数は以下で与えられる。
【数１１】
2006521048.tif 000013
【０３０２】
低周波数係数の計算は多相形式で、偶パリティインデクスと奇パリティインデクスの係数が分離されるようにＢｆ＝ｈe〜ｘe＋ｈo〜ｘoと書き換えることができる。ｘe＋とｘoは偶パリティインデクスと奇パリティインデクスの係数である。
【０３０３】
同様に、再構成された信号だけでなく高周波数も得られる。分解と合成の式は次のようになる。
分解（アナリシス）：
Ｂｆ＝ｈ〜eｘe＋ｈ〜oｘo
Ｈｆ＝ｇ〜eｘe＋ｇ〜oｘo
合成（シンセシス）：
Ｘｒｅ＝ｈｅ（Ｂｆ）＋ｇｅ（Ｈｆ）
Ｘｒｏ＝ｈｏ（Ｂｆ）＋ｇｏ（Ｈｆ）
【０３０４】
このようにして、信号Ｐ〜とＰの分解と合成に対する２つの双対的な多相行列を定義することが可能である。
【数１２】
2006521048.tif 000014
【０３０５】
図２３に多相行列を使って上で定義されたものに対応するウェーブレット変換を示す。Ｐ〜は次の形に因子分解可能であることが示される。
【数１３】
2006521048.tif 000015
【０３０６】
図１７に、リフティングステージと、双対なリフティングステージを示す。ウェーブレット変換はこれらのステージの連続である。リフティングの逆変換は加算を減算で置き換えることによって簡単に得られる。
【０３０７】
［補遺３：アルゴリズム１：画像ｋの画像ｊへの投影］
アルゴリズムの入力
Mask(i)＝画像ｉの定義マスク、画像ｉのどのピクセルが定義されるかを示す
Mask(k)＝画像ｋの定義マスク
mi＝画像ｉのメッシュ分割のポジション
mk＝画像ｋのメッシュ分割のポジション
アルゴリズムの出力
Ir＝再構成される画像、画像ｉに投影された画像ｋ
MaskPrediction＝再構成される画像Irの定義マスク
For  Irの任意のピクセル(xj,r,yj,r)
If  (xj,r,yj,r)がMask(i)に定義されている
(xj,r,yj,r)を含むmiの三角形ｔを特定する；
ｔのノードに付随した(xj,r,yj,r)のウェイトw1,ti、w2,ti、w3,tiを        計算する；
mkにおける(xj,r,yj,r)の新たなポジションを決める：
xj,mk=w1,ti*x1,mk+w2,ti*x2,mk+w3,ti*x3,mk
yj,mk=w1,ti*y1,mk+w2,ti*y2,mk+w3,ti*y3,mk
ここでx1,mk、ｘ2,mk、x3,mkはｔのノードｘのポジションである（yも同様）        ；
If  (xj,mk,yj,mk)がMask(k)に定義されている
(xj,mk,yj,mk)の輝度を双一次補間により計算する；
MaskPrediction(xj,r,yj,r)=true（真）；
end if
else MaskPrediction(xj,r,yj,r)=false（偽）
end if
Else MaskPrediction(xj,r,yj,r)=false（偽）
end for
【０３０８】
［補遺４：マルチグリッド推定］
１．一般原理
メッシュ分割を時間で追跡する段階において、動きが推定されるメッシュ分割はもはや階層的な正則メッシュ分割ではないという問題が生じる。そのとき動きの階層的推定は難しくなる。このため[Marquant-2000]において、与えられた階層レベルの正三角形上で実行された動き推定を次に細かいレベルにプロパゲートさせて、階層的なメッシュ分割での動き推定を可能にする方法が提案された（図２４参照）。このアプローチは、大きな三角形で推定された動きが、変形された構造の実際の動きとはかなり異なることがあるような（大きな三角形の推定サポートはこの三角形を構成すると考えられるメッシュ分割のサポートとは実際に異なる）はっきりしたメッシュ分割変形の場合にすぐに次善最適となり得る。
【０３０９】
この問題を解決するために、マルチグリッドタイプの最小化法がセットアップされる。この方法は縮小した集合のパラメータを使って定義されたメッシュ分割の変形の探索に基づく。そうするために、メッシュ分割の階層構造の平均がとられる。
【０３１０】
記号ｄｐliはメッシュ分割の階層レベルｌにおけるノードｉに付随したシフトを表す。階層レベルｌで変形フィールドを得るための縮小した集合のパラメータは階層レベルｌ−１の変形フィールドから得られることがある。シフトｄｐl-1jはレベルｌのノードｉに以下のようして手渡される（四角形のメッシュ分割の場合の図２５も参照）。
【数１４】
2006521048.tif 000016
【０３１１】
レベルｌとｌ−１のシフトの間の関係は行列形式で［ｄｐlj］＝Ｈll-1［ｄｐl-1j］と書くことができる。この公式を連続して適用すると一般に［ｄｐlj］＝Ｈll-k［ｄｐl-kj］、ここでＨll-k＝Ｈll-1Ｈl-1l-2・・・Ｈl-k+1l-k、が得られる。予測誤差を最小化するこのタイプの最適変形が使用される場合、最適なシフトを定義するシステムはレベルｌの一般公式Ａl［Δｄｐli］＝Ｂlからシステム（tＨll-k．Ａl．Ｈll-k）［Δｄｐl-kj］＝（tＨll-k.Ｂl）へ変換される。
【０３１２】
このマルチグリッド推定は、もはや最も粗いメッシュ分割の上ではないがこれらのより粗いメッシュ分割のノードのシフトを使って動きを推定する際の動きの階層的推定スキームに使用される。
【０３１３】
２．幾何マルチグリッド
ここに以上提示されたアプローチでは、連続する階層レベルのノードの間の重み付け（１および０．５）はいくらか経験に基づいたものであることが見て取れる。実際、これらのウェイトは下位レベルのメッシュ分割の正則構造を保つために正則なメッシュ分割上で適用されるウェイトである。しかしながら、メッシュ分割が変形されると、重み付けの使用は下位レベルのメッシュ分割の構造を保つことを保証しない。このため、図２６において、トータルズームの場合、メッシュ分割の構造はもはや保たれない（下位レベルのメッシュ分割に適用される変形はトータルズームに相当しない）。
【０３１４】
従ってこの問題を克服するために、１つのレベルから別のレベルへシフトが影響する際にノードに使用される重み付けを修正することが提案される。メッシュ分割の２つの連続する階層レベルの間で、細かいメッシュ分割のノードはそれより上位の階層レベルのノードの線形結合として最終的に表すことができる（各ノードごとにこのノードを含む粗いレベルの三角形に関連する重心表現を使用）。この特性はノードのシフトの波及に使用されることになる。
【０３１５】
細かいメッシュ分割のレベルにおいて、２つのタイプのノード、１つは上位レベルのノードの直系子孫ノード、もう１つはその上位レベルのリッジの子孫ノード、が区別できる。１番目のタイプのノードについては、直接の影響が存在し、唯一のノードが関与する。２番目のタイプのノードについては、重み付け公式において、可能性として４つのノードが関与することができる（リッジの両側にある両方の三角形のノード）。リッジの両端にある２つのノードはそのノードを含む上位レベルの三角形の追加的なノードとともに使用される。子孫ノードがリッジ上に位置するとした場合、リッジの端にあるノードのみが使用される（そのほかのノードに関する重心座標はゼロ）。結果として生じる行列Ｈll-1はまだ非常に疎（hollow）である（１ラインあたりノンゼロの値は３個未満）。連続しない階層レベルの間の遷移行列を得るために、本発明は先の行列積公式Ｈll-1＝Ｈll-1Ｈl-1l-2・・・Ｈl-k+1l-kを使用する。
【０３１６】
３．動き推定アルゴリズムをロバスト（robust）にすること
動き推定アルゴリズムは動きの差分最小化に基づいており、計算ノイズによって急速に乱される可能性がある。それ故に推定アルゴリズムを、特にシフト・インクリメント［Δｄｐi］を見い出すために解くべき方程式系を解く中で、ロバストにする必要がある。[Lechat-1999]に提案された解は解くべき線形システムを再調整（recondition）させるためにLevenberg-Marquardt法を使用することにある。この技法は、システムＡＸ＝Ｂにおいて、最小化されるべき機能値の減少が全く観測されない限り、行列Ａの対角成分を大きくすることにある。この対角成分の増大は行列の全てのラインで行われ、問題を経験しているノードのみ成らず全てのノードのシフトを抑える結果を有する。
【０３１７】
この現象を抑えるため、そして他のドリフトを抑えるために、行列Ａの対角項の増大を制限しかつうまく適応させることを提案する中で、いくつかの修正がテストされた。
【０３１８】
３．１  ノードのシフトを抑えるための再調整（reconditioning）
差分最適化法の使用を通じて、見い出されるシフトのインクリメントが（一般的に処理された解像度において１ピクセルの範囲内に）制限されなければならない。従って、システムＡＸ＝Ｂを解く際、全ての成分が最大に許容されたシフトの範囲内にうまく収まっていることがチェックされる。最大許容範囲を超えた場合、前記係数のラインに属する行列Ａの対角項が大きくされる。この増大はLevenberg-Marquardtと同じようにＡ’ii＝（１＋λ）Ａiiで行われ、これは制約条件を満足するために必要な回数だけ行われる。
【０３１９】
３．２  アパーチャ問題に関連した再調整（reconditioning）
動き推定の文脈において、アパーチャ問題（aperture problem）は頻繁に遭遇する問題である。この問題は、テクスチャ勾配の好ましい方向性せいで、ローカルな動きに関する情報が１方向（勾配方向）にのみ確実に指定することができるという事実に関係している。メッシュ分割での推定の場合、この問題は制限される（なぜなら、ノードの影響はこのノードと接触する三角形に含まれるピクセルに関係するからである）。しかしながら、それはテクスチャのはっきりした方向性（marked orintation）を有するゾーンに（例えば、２つの弱くテクスチャ化したゾーンの間の、メッシュのスライディングが輪郭に沿って見られるところの、境界において）現れる。
【０３２０】
この現象はシステムＡ．Ｘ＝Ｂを解くレベルでより明確に説明することができる。その性質から、システムは支配的な対角成分を持たず、多数の「受容可能な」解を持つ場合がある。例えば、共役勾配法は‖ＡＸ−Ｂ‖が低い解を見つけ出すことができる。さて、行列Ａが低い固有値を有する場合には多数の解が生じることがある（古典的なアパーチャ問題の場合に当てはまるように）。
【０３２１】
提案されたアプローチは、各ノードごとに、最適なシフトベクトルに対するノイズに関連したノイズの感度を特定することにある。（ｄｘi，ｄｙi）に対するシフトノイズに関係する‖ＡＸ−Ｂ‖に対するノイズの標準は、Ａxi，xiｄｘi2＋２．Ａxi，yi．ｄｘi．ｄｙi＋Ａyi，yi．ｄｙi2といった二次形式（このノイズのみを議論した場合）で表される。Ａx，xは未知量ｄｘiに付随した係数のラインの標準自乗ノルムＬ2に対応し（Ａy，yも同様）、Ａx、yは未知量ｄｘiとｄｙiに付随した行列のラインの間のスカラー積に対応する。Ａ’xi，xiｄｕi2＋Ａ’yi，yi．ｄνi2の形の二次形式を得るために（ｄｘi，ｄｙi）に対して座標系の回転が行われることがある。λ1とλ2は議論したノードの決まったシフト方向に対するシステムの感度を表す（低い値は関連する変数に関してシステムがうまく調整されていないことを示しており、一方、高い値は有効な調整を示している）。アルゴリズムをロバストにするために、λ1とλ2の値が同じ大きさになるように各ノードごとに対角成分の増加が最小になり得る変数変換（各ノードごとの回転）がシステムで行われる。
【０３２２】
３．３  最小テクスチャ勾配に関連した再調整（reconditioning）
行列Ａのうまくゆかない調整の原因は画像の勾配が低いゾーンの存在と関係する。最後に、平均最小勾配法の概念を紹介する。行列Ａの係数の表現を見ると、対角成分は勾配の加重和の形になっていることが見て取れる。次に標準化したシステムＡnormが計算される。画像勾配の項はこの公式では省略される。再調整（reconditioning）はＡii＞▽Ｉmin［Ａmin］i,jを課すことによって実行される。
【０３２３】
実験的に、この最小勾配項に対して値１０が過度なスムージングを生じない良い結果を与えることを示すことができる（このスムージング効果はより粗いメッシュ分割の階層で計算されたトータルモーションに関連したスムージングによるものである）。
【０３２４】
３．４  推定サポートに関連した再調整（reconditioning）
動き推定段階に推定サポートΩを導入することも、解くべき線形システムの調整問題を引き起こす。例えば、図２７は、三角形Ｎ1Ｎ2Ｎ7内のポイントへの影響が制限されているので、Ｎ1はうまく調整されていないノードであることを示している（だから大きなシフトがこのノードに対して許容されることがある）。この問題を抑えるため、スムージングの概念がノードに導入される。しかしながら、スムージングの導入は動き推定器のクオリティを制限する場合がある。このため、ノードに対するスムージングは不完全な推定サポートを有するノードでのみ行われる。
【０３２５】
次のような形を有するスムージング・エネルギーμ（［Ａnorm，full］i,j−［Ａnorm，Ω］i,j）×（ｄｐi−ｄｐj）2が２つの隣接するノードｉとｊの間に加えられる。Ａnorm，fullとＡnorm,Ωはそれぞれ完全マスクとマスクΩによる「標準化した方程式」（すなわち画像勾配タームを使用しない）のシステムを表す。μはスムージングの効力をコントロールするために使用される重みタームである。このタームの良好な大きさは以前使用されたテクスチャの最小勾配の値を採ることにある。
【０３２６】
再調整の異なる操作が解くべき異なる線形システムに行われてよいことは注意しなければならない。標準化した行列を使用した重み付けの使用により、変化する解像度の問題と三角形の自動的に変わり得るサイズの問題を自動的に考慮する中で導入されたパラメータの調節を制限することが可能となる。最後に、Levenberg-Marquardtによって提案されたスキームは最小化すべき機能因子の減少が見られない場合にのみこれらの様々な再調整操作の後に使用される。
【図面の簡単な説明】
【０３２７】
【図１】本発明に係る符号化の一般原理を説明するための単純化したフロー図である。
【図２】図１の符号化スキームのより詳細なフロー図である。
【図３】階層的メッシュ分割の一例を示した図である。
【図４】本発明に係る多重解像度および階層的推定の原理を説明するための図である。
【図５】階層および解像度のレベルを上げた場合の様子を示した図である。
【図６】ウェーブレット”パディング”の原理を説明するためのフロー図である。
【図７Ａ−７Ｆ】画像Ｉに画像ｋを投影する原理を説明するための図である。
【図８】双一次補間の原理を説明するための図である。
【図９】基準グリッド上への投影を説明するための図である。
【図１０】低周波数の計算による２Ｄ（二次元）パディングを説明するための図である。
【図１１】テクスチャ（または動き）残差信号の一例を示した図である。
【図１２】テクスチャの符号化のアルゴリズムを示した図である。
【図１３】動きの符号化のアルゴリズムを示した図である。
【図１４】メッシュ分割に両立しないベクトルを適用した様子を示した図である。
【図１５】バーテックス（頂点）を合併する一例を示した図である。
【図１６】”n-manifold”メッシュ分割の一例を示した図である。
【図１７】適切なサポートを持つメッシュ分割の一例を示した図である。
【図１８】本発明に基づいて使用される拡張（エクステンション）操作を示した図である。
【図１９Ａ−１９Ｂ】それぞれ本発明の単純化した構成において使用することができる粗いグリッドと細かいグリッドを示した図である。
【図２０】幾何マルチグリッドの原理を説明するための図である。
【図２１】本発明に基づくリフティング段階を示した図である。
【図２２】本発明に基づく信号の分解・合成の原理を説明するための図である。
【図２３】多相行列による別の分解・合成スキームを示した図である。
【図２４−２７】補遺４にコメントされたマルチグリッド推定の特徴を示した図である。
【図２８】時間の経過に沿ってメッシュ分割を追跡する原理のブロック図である。
【図２９】時間の経過に沿ったビデオモザイクの構築を説明するための図である。
【図３０】分解・合成符号化スキームを示した図である。
【図３１】本発明に基づいて生成されたビデオストリームの構造を示した図である。
【図１】
2006521048.tif 000017
【図２】
2006521048.tif 000018
【図３】
2006521048.tif 000019
【図４】
2006521048.tif 000020
【図５】
2006521048.tif 000021
【図６】
2006521048.tif 000022
2006521048.tif 000023
2006521048.tif 000024
【図８】
2006521048.tif 000025
【図９】
2006521048.tif 000026
【図１０】
2006521048.tif 000027
【図１１】
2006521048.tif 000028
【図１２】
2006521048.tif 000029
【図１３】
2006521048.tif 000030
【図１４】
2006521048.tif 000031
【図１５】
2006521048.tif 000032
【図１６】
2006521048.tif 000033
【図１７】
2006521048.tif 000034
【図１８】
2006521048.tif 000035
【図１９】
2006521048.tif 000036
【図２０】
2006521048.tif 000037
【図２１】
2006521048.tif 000038
【図２２】
2006521048.tif 000039
【図２３】
2006521048.tif 000040
【図２４】
2006521048.tif 000041
【図２５】
2006521048.tif 000042
【図２６】
2006521048.tif 000043
【図２７】
2006521048.tif 000044
【図２８】
2006521048.tif 000045
【図２９】
2006521048.tif 000046
【図３０】
2006521048.tif 000047
【図３１】
2006521048.tif 000048
【国際調査報告】
2006521048.tif 000049
2006521048.tif 000050
2006521048.tif 000051
2006521048.tif 000052
2006521048.tif 000053
2006521048.tif 000054
2006521048.tif 000055
2006521048.tif 000056