変形可能なメッシュを用いた動き推定のための方法
本発明は、不連続ゾーンが第１のメッシュ内にあることを検出するために、第１のメッシュを使用することによって推定された画像の動きフィールドを分析し、前記ゾーン内に破断線を配置し、そして不連続ゾーンの外側にある第１のメッシュのメッシュで構成される正常部分、及び破断線を含む領域においてオーバーラップする２つのサブメッシュを含む第２のメッシュを生成する方法に関係する。２つのサブメッシュの各々は、正常部分に共有されるノード、及び正常部分に属さない追加のノードを含むノードによって境界を定められると共に、不連続ゾーンの境界に位置するそれぞれのメッシュセルと、正常部分に共有される２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含む。前記第２のメッシュは、関係がある画像のグループにおける動きフィールドを最終的に推定するために使用される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像のデジタル処理に関するものであると共に、更に特に、シーケンスの連続する画像の間の動きを推定するための技術に関するものである。
【背景技術】
【０００２】
殆どのビデオ符号化方式（特に、ＭＰＥＧ−１，２，４、及びＩＴＵ−Ｔ Ｈ２６ｘ）は、画像のブロックワイズ（blockwise）パーティション分割による変換を用いた動きの表現を使用する。この動きモデルは、多数の問題を生み出す。それは、多くの場合、現在のビデオ符号化方式による復号化に見ることができるブロック効果の原因の大部分であると共に、それは特定のタイプの動き（ズーム、回転等）にあまり適していない表現モデルを提示する。
【０００３】
動きの表現の他のモードは、これらの欠陥を緩和するように提案された。後者の中の提案は、とりわけ、アクティブなメッシュが発見されることである。表現のこのモードにおいて、動きは、画像上に配置されたメッシュのノード上で定義された値のセットを用いて表現される。補間技術が、このメッシュのノードにおいて保存された値に基づいて、画像のあらゆる点の動きベクトルを推論するために使用される。一般的に、これは、ラグランジュタイプ補間（Lagrange type interpolation）を包含することができ、すなわち画像の点に割り当てられた動きベクトルは、隣接しているノードに関して計算されたベクトルのアフィン変換機能（affine function）である。
【０００４】
ＭＰＥＧのビデオ符号器または他のタイプの動き補償モードを、メッシュを基礎とする動き補償モードによって置き換えることが、従って可能である。分析合成タイプの符号化方式を達成するように、ビデオシーケンスの動きとテクスチャ情報を無相関化するためのメッシュを使用することが、同様に可能である。
【０００５】
これらのアクティブなメッシュは、特に、階層的なメッシュが使用されているとき、同一の時間において、動き情報のより効果的符号化の効力による、更に豊かな動きモデル及び改良された符号化の有効性の可能性を提供する（例えば国際公開第００／１４９６９号パンフレットを参照）。
【０００６】
ビデオシーケンスの真の動きが実際は一般的に不連続である一方、変形可能なメッシュは、動きフィールドの連続的表現を定義する。従って、場面において様々な平面、及びオブジェクトがオーバーラップする場合、不連続線を生成する隠蔽ゾーン及び露出ゾーンが現れる。
【０００７】
広範囲のメッシュによるそのような加工品のモデル化は、場面を構成する構成要素のビデオオブジェクトに従って分割されたメッシュとは対照的に、表現モデルの変更なしに解決されることができない問題を構成する。課題は、不連続ゾーン（zone of discontinuity）を判定することによって、このビジュアル劣化を解消すると共に、それを分析期間に制限することである。
【０００８】
従来は、実際の動きフィールドのこのタイプの障害は、そのメッシュ化された表現において、結果としてメッシュセルの反転になる。
【０００９】
後処理技術は、この問題を解決するために実行され得る。これらの技術の内の１つは、事後の修正によって進展すると共に、計算が動きベクトルを生成するように、動きベクトルを適用すること、問題がある動きベクトルを検出すること、そして、動きベクトルの値を訂正することから構成される。これらの技術の内の別のものは、反転がないそのような方法で、各反復において、ノードに対して予期される変位の一部分を加えることによって、及び処理が収束するまで反復を継続することによって、繰り返して進展する。
【００１０】
動き推定を１度実行する後処理技術が、実施された。従って、予測誤差の極小化に対する貢献とは無関係に動きベクトルが訂正されるので、結果は次善である。
【００１１】
改良は、最適化処理における非反転の制限を考慮することによって、動きフィールドを最適化することにある。この目的のために、動き推定は、メッシュセルのエリアがゼロに近づくときに、メッシュセルの変形を訂正することを可能にする拡張されたラグランジュを、二次の予測誤差に加えることによって、適合される。後者の技術は、但し後者が連続的フィールドを表すという条件で、実際に最適な解決法を決定することを可能にする。しかしながら、通常、ビデオシーケンスの性質は不連続である。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
国際公開第０１／４３４４６号パンフレットにおいて発表された別の技術は、不連続ゾーン（discontinuity zone）を復元するために、オブジェクトの出現、または消滅を監視することによって、不連続ゾーンを識別することにある。第１の動き推定は、メッシュセルの反転を妨げることなく、２つの連続する時刻“t1”と時刻“t2”の間で実行される。幾何学の基準を用いたこの第１の計算の完了と同時に反転を正確に指摘することによって、不連続ゾーンは検出される。処理は、その場合に、時刻“t1”と時刻“t2”の間で新しい動き推定を達成することから成る一方、検討された２つの画像の間の予測誤差を最小限にするために、少なくとも１つの反転を含む問題のあるゾーンの寄与を最適化基準から除外する。この再最適化は、連続的なゾーンに関する最適な動きベクトルを決定する（時刻“t1”と時刻“t2”の間で全単射を認める）と共に、従って、前の最適化において獲得された、不連続ゾーンによって生成される動きベクトル値の妨害を回避することを可能にする。問題のあるゾーンは、画像圧縮によって、周波数近似、もしくは空間近似の対象を形成すると共に、それらは、ビデオオブジェクトの追跡によって、最適化の方法から除外される。
【００１３】
様々な既知の技術は、不連続ゾーンにおける連続的ゾーンに基づいて計算された動きを強制的に押し付けることによって、不連続な動きフィールドを連続的にするように試みる。これは、不連続ゾーンにおける間違った動きと、質が悪いテクスチャーの一時的な予測に帰着すると共に、従って符号化の費用オーバヘッドに帰着する。
【００１４】
不連続ゾーンを除外することを目的としている技術は、それらのゾーンにどんな動きも強制的に押し付けないと共に、それらを異なって符号化する。しかしながら、かなりの数の不連続ゾーンがある場合には、同じくらい異なって符号化されるべき多くのゾーンがあり、これらのストリームのヘッダーを符号化するのに費用オーバーヘッドを必要とする。更に、スケーラブル符号化の枠組の中で、この技術は比較的高価である。
【００１５】
本発明の目的は、２次元（２Ｄ）メッシュを用いてビデオシーケンスの動きを推定すること、及び最も良く、真の動きフィールドを描写するために、不連続な方法でこの動きを描写することである。
【課題を解決するための手段】
【００１６】
本発明は、従って、
−ノードによって境界が定められるメッシュセルを含むと共に、シーケンスの参照画像に適用されるべき第１のメッシュを生成する段階と、
−画像の点が属する前記第１のメッシュの前記メッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、画像の各点に割り当てることによって、前記参照画像を包含する画像のグループにおける第１の変位フィールドを推定する段階と、
−前記第１の変位フィールドを分析することによって、各々が画像のグループにおけるメッシュセルの変形基準を満足する少なくとも１つの前記メッシュセルを含む、第１のメッシュにおける少なくとも１つの不連続ゾーンを検出する段階と、
−各検出された前記不連続ゾーンにおいて、画像のグループにおいて現れる少なくとも１つの破断線（break line）を判定する段階と、
−前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの検出された不連続ゾーンに関して、前記不連続ゾーンで判定される前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含む、前記参照画面に適用されるべき第２のメッシュを生成する段階と、
−検出された前記不連続ゾーンに位置する各点が属する前記第２のメッシュの選択されたメッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、検出された前記不連続ゾーンに位置する各点に割り当てることによって、画像のグループにおける第２の変位フィールドを推定する段階とを含み、
前記２つのサブメッシュの各々は、前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含み、前記選択されたメッシュセルが、前記不連続ゾーンで判定される前記破断線に対する前記点の位置によって決まることを特徴とする一連のデジタル動画像における動き推定の方法を提案する。
【００１７】
その方法は、動きを判定するための大域的最適化を実行する。推測的な制限は、最適化されるべき基準に与えられないと共に、それは、同様に、動画に頻繁に現れる不連続ゾーンを計算から除外することを回避する。従って、実行される動き推定は、不連続ゾーンを含んでいても、破断線が信頼できる方法においてタグを付けられるので、最適であり得る。推定された動きは、それ以降、ビデオ符号器によって使用されることができることになる。この枠組の中で、それは、メッシュの不連続ゾーンにおいてさえも、シーケンスの画像の良い予測を可能にすることになると共に、ビデオシーケンスの符号化のコストにおいて改良を可能にすることになる。推定された動きを表すパラメータは、その場合に、復号器に送信されるか、または次の復号化を目的としてメモリに記録されることになる。
【００１８】
動き推定方法は、前記変位フィールドの推定が、メッシュの最も粗い階層レベル（１）から最も細かい階層レベル（nivFin）に対して達成される階層型メッシュの使用に適合する。不連続ゾーンは、好ましくは、メッシュセルの変形基準を満足する最も細かい階層レベルのメッシュセルの隣接しているセットとして検出される。それ以降、それは、メッシュセルの変形基準を満足する最も細かい階層レベルの少なくとも１つのそれぞれのメッシュを含む少なくとも１つのメッシュセルで構成されるように、より高い階層レベルで定義される。
【００１９】
有利に、第２のメッシュの２つのサブメッシュは、最も細かい階層レベル“nivFin”を発端に生成され、より高いレベルのメッシュセルは、それ以降、階層の累進的な上流方向へのバックトラッキングの間に生成される。
【００２０】
階層レベル“n”からすぐ上の階層レベル“n-1”へのバックトラッキングは、サブメッシュの各々に関して、及び“1＜n≦nivFin”に関して、
/a/レベル“n”で事前に定義される前記サブメッシュの各メッシュセルをレベル“n-1”で生成された前記サブメッシュの新しいメッシュセルに統合する段階と、
/b/“n'=n”を計算する段階と、
/c/もしレベル“n'-1”の前記新しいメッシュセルがレベル“n'”で既に生成された前記サブメッシュのメッシュセルによって完成され得ない場合、レベル“n'-1”の前記新しいメッシュセルを完成するために、レベル“n'”で前記サブメッシュの少なくとも１つの新しいメッシュセルを生成する段階と、
/d/もし“n'＜nivFin”である場合、“n'”を１ユニットだけ増やして前記“/c/”段階から繰り返す段階とを含む。
【００２１】
方法の好ましい実施例において、それぞれの深度値は、前記正常部分のノード、及び前記第２のメッシュの各サブメッシュの追加のノードに割り当てられる。前記不連続ゾーンに関して生成されたサブメッシュの追加のノードに割り当てられる値は、前記不連続ゾーンで判定される前記破断線に対する前記サブメッシュの位置によって決まる。第２のメッシュの正常部分のメッシュセル、及びサブメッシュの少なくとも１つのメッシュセルに属する画像の各点に関して、前記第２の変位フィールドを推定する段階は、前記点を含む各メッシュセルに関して、前記メッシュセルの境界を定めるノードにそれぞれ割り当てられた前記深度値の加重和を計算する段階と、前記点に対する前記変位値の割り当てに関して、計算された前記加重和が最大のメッシュセルを選択する段階とを含む。
【００２２】
これらの深度値の使用は、画像のグループに共存する数個の平面の存在を明らかにすることを可能にする。そこに２つより多い平面がある場合に、相対的な深度値は、動きの合成のために、復号器に伝達されなければならないことになる。
【００２３】
本発明の他の特徴は、上記で定義されるような方法を実現するように適合された手段を備える、一連のデジタル動画像における動き推定のための装置の他に、前記装置の計算ユニットによってプログラムを実行した場合に上記で定義されるような動き推定の方法の段階を実現するための命令を含む、動画を処理するための装置にインストールされるべきコンピュータプログラムとも関係がある。
【００２４】
本発明は、同様に、一連のデジタル動画像における動きを推定するための手段と、前記動きを推定するための手段によって生成された動きパラメータを含む出力ストリームを組み立てるための手段とを備え、前記動きを推定するための手段が、上記で定義されるような方法に従って動作するように設計されるビデオ符号器を提案する。
【００２５】
本発明の更に別の特徴は、上記で定義されるような方法を実行することによって獲得された動きパラメータの表現を含む、一連のデジタル動画像を代表する信号、及びそのような信号が記録される記録媒体と関係がある。
【００２６】
参照画像を包含する画像のグループに関して、動きパラメータは、
−前記参照画像に適用されるべき第１のメッシュにおいて、画像のグループにおける少なくとも１つの不連続ゾーンを構成するメッシュセルを示す第１の動きパラメータと、
−各不連続ゾーンにおいて少なくとも１つの破断線を位置決めするための第２の動きパラメータと、
−前記参照画像に適用されるべき第２のメッシュのノードに割り当てられた変位値を示す第３の動きパラメータとを含み、
前記第２のメッシュは、前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの不連続ゾーンに関して、前記不連続ゾーンに位置する前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含み、前記２つのサブメッシュの各々は、前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含む。
【００２７】
信号で表される動きパラメータは、正常部分のノード、及び第２のメッシュの各サブメッシュの追加のノードにそれぞれ割り当てられる深度値を示すパラメータで補完され得る。
【００２８】
本発明は、ビデオ復号器か、または動画を処理するため他の装置において実行されて、動きを復号化する側で同様に具体化される。
【００２９】
本発明は、従って、ノードによって境界が定められるメッシュセルを含む画像のメッシュを用いた、一連のデジタル動画像における動きをデコードする方法を提案する。
【００３０】
前記方法は、
−上記で定義されるような動きパラメータを含む入力ストリームを受信する段階と、
−前記第１の動きパラメータ及び前記第２の動きパラメータに基づいて前記第２のメッシュを生成する段階と、
−前記第３の動きパラメータに基づいて獲得された変位値を、前記第２のメッシュの各ノードに割り当てることによって、そして検出された前記不連続ゾーンに位置する各点が属する前記第２のメッシュの選択されたメッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、検出された前記不連続ゾーンに位置する各点に割り当てることによって、画像のグループにおける変位フィールドを生成する段階とを含み、前記選択されたメッシュセルが、前記不連続ゾーンで判定される前記破断線に対する前記点の位置によって決まる。
【００３１】
本発明の他の特徴は、上記で定義されるような方法を実現するように適合された手段を備える、一連のデジタル動画像における動きの復号化のための装置の他に、前記装置の計算ユニットによってプログラムを実行した場合に上記で定義されるような動きの復号化の方法の段階を実現するための命令を含む、動画を処理するための装置にインストールされるべきコンピュータプログラムとも関係がある。
【００３２】
本発明は、更に、動きを復号化する手段と、前記動きを復号化する手段によって生成された変位フィールドを考慮して、一連のデジタル動画像を組み立てるための合成手段とを備え、それらが、上記で定義されるような動きの復号化の方法に従って動作するように設計されているビデオ復号器を提案する。
【発明を実施するための最良の形態】
【００３３】
本発明の他の特徴、及び利点は、添付の図面を参照することによって、これから先の制限しない代表的な実施例の記述に現れることになる。
【００３４】
“x”、“y”が、画像のフィールドにおける画素の座標を指定すると共に、“t”が、ここではシーケンスの各画像において“１”ずつ増加すると仮定された離散化時刻（discretized time）を指定する、一連のデジタル画像“I(x,y,t)”を考察する。画素と関連付けられた値“I(x,y,t)”は、一般的に輝度値である。
【００３５】
動き推定は、画像“I(x,y,t)”における座標“(x,y)”を有する各点について、画像“I(x,y,t-1)”から、画像“I(x,y,t)”の良い近似である置き換えられた画像“I'(x,y,t)=I(x-dx,y-dy,t-1)”を構成することを可能にする変位ベクトル“D(x,y,t)=(dx,dy)”を生成することから構成される。
【００３６】
その計算は、Ωに対応する推定に関して実行される。それは、下記式の関数“Φ(t)”を最小化する変位フィールド“D(x,y,t)”を決定することから構成される。
【００３７】
【数１】
【００３８】
ここで、“ρ(A,B)”は、最も一般的な式が“ρ(A,B)=(A-B)2”である測定基準である。
【００３９】
画像のメッシュの使用は、未知数の数を減少させることを可能にする。メッシュのノード“i”に位置する点の変位ベクトル“D(xi[t],yi[t],t)”だけが検索される。これらのノードから離れて、変位フィールド“D(x,y,t)”は、例えば、下記のアフィン変換に関する手順に従って、補間される。
【００４０】
【数２】
【００４１】
ここで、加重値“wi(x,y,t)”は、時刻“t”における画像内のノード“i”の位置に関して表された点“(x,y)”の座標を示す。
【００４２】
都合の良いメッシュは、その頂点が、時刻“t”において、それぞれが座標“(xi[t],yi[t])”、座標“(xj[t],yj[t])”、及び座標“(xk[t],yk[t])”を有するメッシュのノード“i”、“j”、“k”である三角形に、各点“(x,y)”が属すると考えられる三角形のメッシュである。時刻“t”における点“(x,y)”に関連付けられた補間の加重値は、以下の数式によって与えられた三角形の重心座標である。
【００４３】
【数３】
【００４４】
【数４】
【００４５】
【数５】
【００４６】
【数６】
【００４７】
ここで、“πi,j,k[t]=xj[t].yk[t]-xk[t].yj[t]+xk[t].yi[t]-xi[t].yk[t]+xi[t].yj[t]-xj[t].yi[t]”は、時刻“t”における三角形に関連づけられたベクトル積である。
【００４８】
その計算は、一般的に、およそ１０個の画像程度の、シーケンスの連続的な画像のグループに関して実施される。そのメッシュは、習慣的に、正三角形の編み目（network）によって、グループの第１の画像（t=0）に関して定義される。変位ベクトル“D(xi[1],yi[1],1)”は、例えば、ガウス−サイデル（Gauss-Seide）、または類似のタイプの最急降下法を適用することによる関数“Q(1)”の極小化によって推定される。時刻“1”におけるメッシュのノード“i”の位置は、数式“(xi[1],yi[1])=(xi[0],yi[0])+D(xi[1],yi[1],1)”を通して、これから推論される。“Q(t)”の極小化による変位ベクトル“D(xi[t],yi[t],t)”の推定、そして時刻“t”におけるメッシュのノードの位置の計算：“(xi[t],yi[t])=(xi[t‐1],yi[t‐1])+D(xi[t],yi[t],t)”という、この処理は、グループの最後の画像（t=2,3,4等）まで繰り返される。
【００４９】
動き推定は、それ自体が周知である方法でシステムの更に良い収束を保証する階層型メッシュを用いて有利に実行される。メッシュの特定の細かさは、忠実に画像の中の動きを表すために必要である。しかし、強い動きの事象において、先行する極小化技術は、もしそれが直接細かいメッシュに適用される場合、収束しないかもしれない。更に、非常に細かいメッシュの使用は、過度に大きな数のパラメータのせいによるシステムの不安定性の原因となる可能性がある。
【００５０】
図１は、代表的な階層型メッシュを示す。階層型表現は、いくつかの表現レベルから構成される。符号３０で示される最も低いレベル（図中のレベル０）は、メッシュを定義するための３つのノードだけを備えた粗いフィールドを有する。符号３２、３３、３５で示される順で更に細かいレベルの方へ向かうと、そのフィールドは、次第に更に濃密になると共に、メッシュのノードの数が増加する。動きの品質はレベルによって異なり、符号３０で示される最も低いレベルはシーンの支配的な動きを表すと共に、細かいレベルは、局所的な動きを表すための支配的な動きを絞り込む。階層型メッシュのレベルの数は、推定段階の調節可能なパラメータであり、それは、推定されるべきシーケンスに従って変化し得る。
【００５１】
階層型メッシュによる動き推定の技術において、１つのレベルは、符号３０で示される最も粗いレベル上の動きを推定することによって始まり、そして、１つのレベルは、以前のレベルにおいて推定された変位値から推論された節の変位値に基づいて傾斜降下（gradient descent）を始める次のレベルに移動する階層型メッシュのいくつかのレベルが、画像に基づいて生成され、２つのレベルに共通のノードは、まさに推定されたそれらに等しい最初の変位ベクトルを受け取ると共に、より細かいレベルにおいて加えられたノードは、空間的補間によって計算された最初の変位ベクトルを受け取る。反復の終りにおいて、復号器に送信されるように定量化されるのは、最も細かいレベルにおいて推定された変位ベクトルである。
【００５２】
階層型メッシュによる動き推定の技術は、最初の画像に基づいて構成されたフィルタ処理されると共に廃棄される画像の角錐に作用するマルチ解像度推定技術（multi-resolution estimation technique）と結合できる。階層型メッシュのレベルにおける動き推定は、その場合に、適切な解像度のレベルにおいてサンプリングされた画像に基づいて実行される。
【００５３】
メッシュを基礎とする動き推定技術に関する一般的な問題は、メッシュセルの反転の問題である。この問題は、２つの連続する時刻における画像のメッシュを、図の左側部分において、これらの２つの時刻の間で推定されたメッシュの基本の三角形の頂点を形成するノード“i,j,k”における変位ベクトルの例と共に発見する図２で例証される。この三角形の反転は、ノード“i”、及びノード“j”を通過する直線に交差するノード“k”に起因する。
【００５４】
一般的に、三角形“i,j,k”の反転は、ベクトル積“πi,j,k[t]”の符号の変更に対応する。そのような人為的な結果は、動き推定を非常に妨害する。それらは、一般的に、撮影されたシーンの様々な平面におけるオブジェクトの相対的な動きのせいである。図２の実例は、（ゼロエリアの三角形を通過して）単一の三角形が反転するので、非常に単純化される。実際には、オーバーラップは、通常、画像における特定の広がりを有する不連続ゾーン（discontinuity zone）で発生する。
【００５５】
階層型メッシュによって、メッシュセルの反転は、必然的に、粗いレベルにおける発生の可能性より、細かいレベルにおける更に大きな発生の可能性を有している。
【００５６】
メッシュセルの反転の問題を扱うために、本発明は、不連続ゾーンのタグ付け、及びそれらが含む破断線（break line）のタグ付けを使用する。画像の再メッシュ化は、破断線のどちらの側においても、最初のメッシュに固定された複数のサブメッシュを用いて、不連続ゾーンにおいて達成される。不連続ゾーンで生成された複数のサブメッシュは、それらが相互にオーバーラップするように、破断線を越えて伸びる。それらは、不連続ゾーンの外側に更にはみ出すことができる。式（２）のような補間の式を用いて不連続ゾーンに位置する像点（image point）の変位を推定するために、破断線または複数の破断線に関する点の位置の関数として選択されたサブメッシュの内の１つのノードが参照される。従って、サブメッシュは、それらの使用がシーンにおいて出現するか、または消滅するオブジェクトに従って決定される、一連の画像に存在する様々な平面から構成されることを可能にする。
【００５７】
本発明は、動きの不連続ゾーンを、符号化の時に、それらを欠陥がある状態にするか、またはそれらを排斥することなく、管理することを可能にする。オーバーラップ、または露出面が検出される場合、その原理は、不連続性が作成される所で局所的にメッシュを切ることであると共に、メッシュをいわゆる“非多様体（non-manifold）”メッシュに変換することである。非多様体メッシュは、エッジが２つ以上のメッシュセルによって共有され得るメッシュである。それによって、ビデオシーケンスにおける動きを推定すること、及び不連続の動きフィールドを形に表すことを可能にする。利点は、従って、符号化の時に、不連続ゾーンを、連続的なゾーンと同じ方法で考慮することを可能にすることである。
【００５８】
図３は、本発明による動き推定方法のフローチャートを示す。
【００５９】
最初のステップ９は、符号化されるべきビデオシーケンスの画像に関する最初のメッシュを定義することから構成される。次に、ステップ１０において、Ｔ個の連続した画像のグループにおける動きフィールドの最初の推定を始める。この推定は、例えば、上記で説明される手順に従って、好ましくは階層型メッシュを用いて従来の方法において達成される。この計算の過程で、特定の三角形のメッシュセルは、反転するか、もしくは非常に変形することができる。
【００６０】
それ以降、その方法は、最初のメッシュにおける不連続ゾーンを検出するためのステップ１１を含む。
【００６１】
不連続ゾーンは、それぞれ、最も細かい階層レベルにおいて定義された縮退したメッシュセルの隣接しているセットから構成される。それらは、ステップ１０における動き推定の過程で反転する三角形を少なくとも含む。これらの三角形は、最も細かい階層レベルにおける、及び連続する時刻“t=0,1,2,...,T-1,T”におけるメッシュの様々な三角形に関して、（最小限にされるべき汎関数における変位の補間のために）ステップ１０において計算されたベクトル積“πi,j,k[t]”に従って容易に検出可能である。三角形は、ベクトル積“πijk[t]”が全て正であるように、初めに配置される。メッシュセルの反転は、その場合に、負のベクトル積によって明らかにされる。
【００６２】
検出は、不連続ゾーンにおいて、（ベクトル積“πi,j,k[t]”の絶対値の半分に等しい）その領域がゼロに近くなる、すなわち、少なくとも１つの時刻“t”に関して事前に定義されたしきい値未満である三角形のメッシュセル“i,j,k”を含むように一般化され得る。
【００６３】
不連続ゾーンに含まれるべき縮退した三角形の検出は、更に一般的に、時刻“0”の画像と時刻“T”の画像との間の三角形の変形の学習を含むことができる。もしメッシュセルの変形がある限界を越える場合、このメッシュセルは縮退していると考えられる。
【００６４】
縮退したメッシュセルの隣接しているセットは、不連続ゾーンを形成する。それは、動きにおいて不連続性が明白なゾーンである。それは、最も細かい階層レベルで定義されると共に、最も細かい階層レベルを構成する三角形のメッシュセル（または、それに接しているノード）は、復号器に送信されることになるパラメータの一部分を形成する。同様に、不連続ゾーンの形状は、スプライン（spline）で表されることができる。
【００６５】
もし不連続ゾーンがステップ１１（テスト１２）において検出されない場合、動き推定方法は、ビデオ復号器に送信されるように定量化されることになる動きのパラメータが供給されるステップ２０において終了する。この場合、これらのパラメータは、ステップ１０において獲得されたパラメータであると共に、不連続ゾーンが検出されなかった(連続的な動きである)ことを信号伝達するための表示が加えられる。
【００６６】
もし画像のグループにおいて１つ以上の不連続ゾーンが検出される場合、まず検出された各不連続ゾーンにおいて破断線の判定に着手する（ステップ１３）。
【００６７】
破断線は、ゾーン内に不連続性を生み出したオブジェクトの形状に関して位置決めされる。不連続ゾーンにおける単一の破断線の場合がこれから先に詳述されることになる。処理は、同一のゾーンの中のいくつかの破断線に一般化が可能であることが気付かれることになる。
【００６８】
オブジェクトの形状は、内側の領域（前景領域）、及び外側の領域（背景領域）を定義するように配置される。本質的に知られているいくつかの手順が、ステップ１３においてこの形状を発見するために適用できる。もしシーケンスの画像を分割するためのマスクが既に利用可能な場合、その形状は、これらのマスクに基づいて抽出される。しかしながら、大部分のシーケンスに関しては、分割マスクが利用可能ではない。
【００６９】
この場合、画像は、“Dorin Comaniciu”及び“Peter Meer”によって、“IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, No. 5, May 2002, pp. 603-619”の“Mean Shift: A Robust Approach Toward Feature Space Analysis”において示された技術のような“平均シフト”技術によって事前分割（pre-segment）され得る。それ以降、一連の拡張、及び一連の形態学に関する浸食（morphological erosion）は、小さな分割された領域を除去することを可能にする。オブジェクトの形状は、最終的に分割された画像から抽出される。
【００７０】
ステップ１３において、同様に、顕著な点を検出するための技術が適用され得る。顕著な点は、主にオブジェクトの形状に基づいて位置決めされる。完全な形状を定義しない顕著な点のリストに、これらの点の連鎖に基づく形状の微調整の段階を加えることは適切である。画像“I”の顕著な点は、高周波の領域に属する画像“I”の画素に対応する。それらを検出するために、ウェーブレット理論を使用することが可能である。ウェーブレット変換は、１／２、１／４等の様々な解像度で画像を表すことを可能にする画像のマルチ解像度の表現である。従って、各解像度レベル“2j(j≦-1)”において、ウェーブレット変換は、サイズ“2k+j×21+j”の画像のグループの形で、サイズ“n×m=2k×2l(k,l ε Z)”の画像“Im”、すなわち、粗い画像である
【００７１】
【数７】
【００７２】
と、高い水平周波数を表す細部の画像である
【００７３】
【数８】
【００７４】
、すなわち水平の形状と、高い垂直周波数を表す細部の画像である
【００７５】
【数９】
【００７６】
、すなわち垂直の形状と、そして、高い対角線の周波数を表す細部の画像である
【００７７】
【数１０】
【００７８】
、すなわち角とを表す。
【００７９】
詳細な３つの画像の各々は、（
【００８０】
【数１１】
【００８１】
の状態で）各方向において、続いてサブサンプリングが実行される、２つの係数によるフィルタ処理を実行することによって、
【００８２】
【数１２】
【００８３】
から獲得される。画像の顕著な点を検出するために、ウェーブレットを基礎とする最小の解像度レベル“2r(r<=-1)”が最初に使用される。一度ウェーブレット変換が実行されたなら、３つの詳細画像の各々
【００８４】
【数１３】
【００８５】
【数１４】
【００８６】
【数１５】
【００８７】
は、ウェーブレット係数のツリー構造を構成するように、詳しく検討される。このツリー構造は、画像符号化の分野において知られている、いわゆるに“Zerotree”アプローチに基づいている。それによって、解像度“2r”における各ウェーブレット係数の重要性を反映するサイズ“2k+r×2l+r”の特性マップを適所に置くことが可能になる。従って、有意の突出性を有する係数は、高い周波数を示す“Im”の領域に対応する。具体的には、解像度“2r”における有意の係数のウェーブレット係数は、特別な方向（水平の方向、垂直の方向、もしくは斜めの方向）に従っている画像である
【００８８】
【数１６】
【００８９】
の形状と対応する。“Zerotree”アプローチは、解像度“2r”におけるウェーブレット係数の各々が、画像“Im”におけるサイズ“2-r×2-r”の空間ゾーンに対応することを示す。構成された特性マップに基づいて、従って、“Im”の“2-r×2-r”の画素の中から、このゾーンを最も代表する画素を選択することが可能である。
【００９０】
一度不連続ゾーンにおいてこれらの顕著な点が測定されたならば、それらは、利用可能な破断線を有するように連結される。この目的のために、点の連鎖の既知の技術、あるいは補間または多項式の近似の技術（ニュートン、スプライン、チェビチェフ（Tchebicheff）、最小２乗等）を使用することが可能である。
【００９１】
ステップ１３において、画像のグループの各々の画像における破断線が判定されるということに注目するべきである。これらの線の位置は、復号器に伝達されることを目的として、ステップ１３において供給される動きパラメータの一部となることになる。
【００９２】
方法のステップ１４において、ステップ１１において検出された不連続ゾーンは、非多様体（non-manifold）再メッシュ化の対象を形成する。この再メッシュ化は、最も細かい階層レベルにおいて最初に実行される。
【００９３】
図４は、最初の三角形のメッシュの８つの隣接しているメッシュセルから構成される代表的な不連続ゾーンＺを示す。このメッシュは、グループの最初の画像に関するその定義の間に、正三角形から構成される。図４は、ステップ１３においてゾーンＺ内で判定されて、配置された破断線“L”を示す。
【００９４】
ステップ１４において採用された新しいメッシュは、不連続ゾーンに属する最初のメッシュの三角形で構成される正常部分を含む。破断線“L”を含んでいる各不連続ゾーンＺにおいて、不連続ゾーンＺのエッジに沿った正常部分に付着する２つのサブメッシュが生成される。これらの２つのサブメッシュの各々は、破断線“L”の面に割り当てられると共に、それは、不連続ゾーン“Z”のエッジに沿ったこの面に位置する最初のメッシュのノードを含む。
【００９５】
図５、及び図６における破線の三角形は、従って、それぞれ、図４の不連続ゾーン“Z”において生成され得る２つのサブメッシュを表す。この例において、図４において“a,b,c,d,e,f”で示される最初のメッシュのノードは、図５において示される“左側の”サブメッシュに属する（すなわち、破断線“L”の左側の最初のメッシュに付着すると共に、ここで、左側及び右側は、破断線“L”に関して決定された方向性に関連して定義される。）と共に、図４において“a,f,g,h,i,j”で示される最初のメッシュのノードは、図６において示される“右側の”サブメッシュに属する。
【００９６】
不連続ゾーンに接する最初のメッシュのノードのいくつかは、２つのサブメッシュに共通である（ここでは、ノード“a”及びノード“f”）。
【００９７】
図５の例において、左側のサブメッシュは、８個の新しいノード“a'-h'”と、１６個の新しい三角形(a,a',h')，(a,b,a')，(b,b',a')，(b,c,b')，(c,d,b')，(d,c',b')，(d,e,c')，(e,d',c')，(e,f,d')，(f,e',d')，(d',e',f')、(c',d',f')，(c',f',g')，(b',c',g')，(a',b',g')、及び(a',g',h')を含む。
【００９８】
図６の例において、右側のサブメッシュは、８個の新しいノード“a"-h"”と、１６個の新しい三角形(a,h",a")，(j,a,a")，(i,j,a")，(i,a",b")，(i,b",c")，(h,i,c")，(h,c",d")，(g,h,d")，(f,g,d")，(f,d",e")，(c",e",d")，(c",f",e")，(b",f",c")，(b",g",f")，(a",g",b")，及び(a",h",g")を含む。
【００９９】
新しいサブメッシュにおいて生成された追加のノードは、第１の画像内で、最初のメッシュのノードの位置と一致する位置を有することができる。図５及び図６において、図の読取りを容易にするために、それらはシフトされて表される。
【０１００】
不連続線“L”によって横断される不連続ゾーン“Z”の境界におけるエッジのノードは、最初のメッシュと共にだけ動くことができる境界ノードである。これら境界ノードは、以下の３つのタイプであり得る。
【０１０１】
−単に左側のサブメッシュの基礎としての役目を果たす左側の境界ノードであって、それらは、図４から図６におけるノード“b”、ノード“c”、ノード“d”、及びノード“e”である。
−単に右側のサブメッシュの基礎としての役目を果たす右側の境界ノードであって、それらは、図４から図６におけるノード“g”、ノード“h”、ノード“i”、及びノード“j”である。
−両方のサブメッシュの基礎としての役目を果たす共有された境界ノードであって、それらは、図４から図６におけるノード“a”、及びノード“f”である。
【０１０２】
破断線“L”が少なくとも１つの境界ノードを頂点として有する三角形を横切る場合、このノードは、配置された線に対するその位置の関数として、左側の境界、もしくは右側の境界であるとして特定される。破断線“L”が終了する三角形に関して、例えば、（図４〜図６にあるように、）破断線“L”に横切られた境界に位置するノードを左側及び右側の境界ノードとして特定し、そして第３のノードを共有された境界ノードとして、特定することが可能である。別の可能性は、それが三角形の境界に遭遇するまで、外挿法（extrapolation）によって破断線を延長することであると共に、この境界に位置するノードを共有された境界ノードとして特定し、そして配置された線に対するその位置の関数として第３のノードを左側または右側の境界ノードとして特定することである。
【０１０３】
ビデオシーケンスにおいて発生する可能性がある考えられる露出面を考慮するために、新しいメッシュセルは、図５及び図６によって示されたように、不連続ゾーン“Z”を越えて伸びる。正常部分のメッシュセル、及びサブメッシュのメッシュセルは、その場合に、オーバーラップする。
【０１０４】
画像の復元の間の不一致を回避するために、３次元画像合成の分野ではその使用が良く知られている“２−バッファ（2-buffer）”に端を発する、ノードにおける“２−オーダー（2-order）”の手順が使用される。ここで使用される非多様体（non-manifold）メッシュに対する適応は、各サブメッシュの新しいノードに、このサブメッシュに割り当てられた正または負の深度値Ｚを割り当てることによって実行される。
【０１０５】
保存された最初のメッシュのノードは、深度値“Z=0”を受け取る。値“z>0”は、一般的に、前景のオブジェクトに対応すると共に、値“z<0”は、背景のオブジェクトに対応する。“z”の符号は、破断線“L”の方向性によって与えられる。その形状が破断線に対応する前景のオブジェクトは、破断線“L”の方向性に関連して、（例えば、その方向性という意味で動いている場合に、線の右側に関連して）位置決めされる。従って、図４〜図７の場合に、図７における斜線部分は、その破断線“L”が形状を構成するオブジェクトに属している。
【０１０６】
ノードにおけるこの値“z”は、メッシュセルの各点において補間技術（例えば、アフィン変換）によって“z”の値を計算することを可能にする。いくつかのメッシュセルによって復元されることが可能である点の復元の間に、値ｚが、これらの様々なメッシュセルに関して、この点において計算されると共に、最も大きい値ｚを与えるメッシュセルを保持するように、これらの値は比較される。これは、背景に対しての前景においてオブジェクトを支持することを可能にする。
【０１０７】
不連続ゾーンにいくつかの破断線が現れる場合、一連の画像の対応する部分に２つ以上の平面が存在する。破断線の検出は、様々な平面を位置決めすることを可能にすると共に、それらは、区別された値“z”を割り当てられる。上記の手順は、その場合に、画像の各点の復元のために、関連したメッシュセルを選択することを可能にする。ノードにおける値“z”は、そのためにメッシュセルが導入された画像を最もよく復元するように位置決めされる。その位置決めは、最初の画像と復元された画像との間の平均二乗誤差を最小限にしようと試みるＩＣＭ（Iterative Condition Mode）タイプの反復的アルゴリズムを用いて実行され得る。不連続ゾーンにいくつかの破断線があるとき、対応するサブメッシュに関して決定された値“z”は、復号器に送信されるべき動きのパラメータの一部を形成する。
【０１０８】
最も細かいレベルにおいて一度再メッシュ化が達成されると、破断線“L”が表す不連続性は、より高いレベルを通して、あるレベルで消滅するまで上流方向にバックトラックされる。不連続性がメッシュレベルに存在する限り、このレベルに関して定義された不連続ゾーンは、メッシュの階層を維持するように低いレベルの再メッシュ化を考慮することによって、再メッシュ化される。
【０１０９】
階層構造を通した不連続性の上流方向へのバックトラッキングは、各レベルに関して不連続ゾーンを決定する段階と、ゾーンの境界におけるノードに課せられる制限を決定する段階という２つのステップを含む。“nivFin”を、最初に再メッシュ化が実行されたメッシュの最も細かいレベルとする。“nivFin”より小さいか、または等しいレベル“n”に関して、もし不連続ゾーンが検出された場合、レベル“n-1”における不連続ゾーンは、図８によって示されるように、レベル“n”の閉鎖された状態のゾーンのメッシュセルの親メッシュセルのセットによって定義される。
【０１１０】
２つのサブメッシュに共有された境界ノードの制限は、例えば、以下のアルゴリズムに従って、階層構造を通して上流方向にバックトラックされる。
【０１１１】
レベル“n”において共有された境界ノードを構成するノード“m”に関して、
・もし“m”がレベル“n-1”に親“p”を有している場合、“p”は、レベル“n-1”において共有された境界ノードとなる。
・そうでなければ、“A”を、破断線“L”がそれを通してレベル“n-1”の三角形の中を貫通するエッジとすると共に、“q”を、このエッジの反対側に位置するメッシュセルノードとする。
【０１１２】
破断線“L”は、“q”のところまで人工的に延長されると共に、このノード“q”は、レベル“n-1”に関して共有された境界ノードになる。
【０１１３】
既に再メッシュ化された階層レベル“n”より低い階層レベル“n-1”に関する新しいメッシュセルの生成は、以下の３つのタイプであり得る。
【０１１４】
「１／」
図９ａから図９ｄ：破断線“L”は、レベル“n-1”における不連続ゾーンに属するメッシュセル“ABC”と完全に交差する。
【０１１５】
右側に関する境界ノードはノード“C”及びノード“B”であり、新しいノード“A'”がレベル“n-1”で作成される。新しいメッシュレベル“n-1”のセル“A'BC”は、レベル“n”のメッシュセル“A'E'D'”、“E'CF”、“D'FB”、及び“E'D'F”を、ドーターメッシュセル（daughter mesh cell）として見なすと共に、ここで、“F”は、エッジ“B-C”の中央であり、“D'”及び“E'”は、レベル“n”の右側の再メッシュ化によって作成されたノードである。メッシュセル“A'E'D'”は、たとえ、もしそれがレベル“n”の再メッシュ化の間に生成されなかったとしても、レベル“n”と関係があるが、しかし、より高いレベルの“n-1”の場合は、再メッシュ化の間に生成されなければならない。同様に、左側の倍増に関して、境界ノードは“A”であり、ノード“B'”、“C'”、及び“F'”は、レベル“n-1”の再メッシュ化によって作成されている。レベル“n-1”の新しいメッシュセル“AB'C'”は、ドーターメッシュセルとして、レベル“n”における“AED”、“EC'F'”、“EDF'”、及び“DF'B'”を有すると共に、ここで、“D”及び“E”は、それぞれ、エッジ“A-B”、及びエッジ“A-C”の中央である。
【０１１６】
「２／」
図１０ａ〜図１０ｄでは、破断線“L”は、レベル“n-1”における不連続ゾーンに属するメッシュセル“ABC”を横断すると共に、ノード“C”で終了する。
【０１１７】
このケースは、ノード“C”が共有された境界ノードになるという差異を有する一方、ケース“１／”と類似する。レベル“n-1”における右側の再メッシュ化に関して、（例えば、）ノード“C”及びノード“B”は、境界ノードであると共に、ノード“A'”が作成される。レベル“n-1”の新しいメッシュセル“A'BC”は、ドーターメッシュセルとして、レベル“n”のメッシュセル“A'E'D'”、“E'CF”、“D'FB”、及び“E'D'F”を有すると共に、レベル“n”における再メッシュ化の間に追加されたメッシュセル“A'E'D'”を含む。同様に、左側の倍増に関して、ノード“C”及びノード“A”は、境界ノードであると共に、ノード“B'”が作成される。レベル“n-1”の新しいメッシュセル“AB'C”は、ドーターメッシュセルとして、レベル“n”における“AED”、“ECF'”、“EF'D”、及び“DF'B'”を有する。
【０１１８】
「３／」
図１１ａ〜図１１ｄでは、破断線“L”は、レベル“n-1”のメッシュセル“ABC”を完全には横断しない。
【０１１９】
レベル“n”では、それは、メッシュセルに入って横断して、それによって図１０ａから図１０ｄの場合に戻るように、エッジ“E-F”の反対側のノード“C”のところまで、または、エッジに進入するのとは対照的に、エッジ（図１１ａにおける“E-F”）のところまでのいずれかにより、人工的に延長される。ノード“E”、及びノード“F”は、その場合に、レベル“n”における共有された境界ノードである。メッシュ“(n-1)”の、より高い階層レベルが考慮される場合、破断線“L”は、ノードまたはエッジまで延長される（より細かいレベル“n”に関してちょうど見られたものと同様の場合）。図１１ｄにおいて、形状は、ノード“C”まで延長された。右側の再メッシュ化に関して、ノード“C”及びノード“B”は境界ノードであると共に、ノード“A'”が作成される。レベル“n-1”のメッシュセル“A'BC”は、ドーターメッシュセルとして、レベル“n”における“A'ED'”、“ED'F”、“EFC”、及び“D'FB”を有する。メッシュセル“A'ED'”は、たとえ、もしそれがレベル“n”の再メッシュ化の間に生成されなかったとしても、レベル“n”と関係があるが、しかし、より高いレベルの“n-1”の場合は、再メッシュ化の間に生成されなければならない。左側の再メッシュ化に関して、境界ノードはノード“C”及びノード“A”であると共に、ノード“B'”が作成される。レベル“n-1”のメッシュセル“ACB'”は、ドーターメッシュセルとして、レベル“n”における“AED”、“ECF”、“EDF”、及び“DFB'”を有する。この場合、レベル“n”のメッシュセル“ECF”は、メッシュセル“A'BC”及びメッシュセル“ACB'”によって共有されるということが言及されている。
【０１２０】
破断線が完全にメッシュセルに含まれるとき、それは、より高いレベルにおいて消滅する。新しいメッシュセルの生成のために現在のレベルで導入される新しいノードは、より高いレベルの親メッシュセルにおけるそれらの重心座標によって定義される。これらのノードは、従って、より高いレベルのメッシュセルのノードによって影響を受けるグローバルな動きを有することになる。
【０１２１】
図１２ａから図１２ｃは、破断線が消失する場合を示す。レベル“n”において、破断線は、ノード“B”及びノード“C”のところまで延長され、それは従って共有された境界ノードになった。再メッシュ化は、右側に関してノード“E'”、及びノード“D'”を導入したと共に、上側（頂点側）に関してノード“F'”を導入した。レベル“n-1”において、形状はメッシュセル“ABC”に完全に含まれる。右側に関して、ノード“A'”は、メッシュセル“A'BC”を形成するために導入される。左側に関して、ノードは導入されず、再メッシュ化は、最初のメッシュセル“ABC”を導入する。メッシュセル“A'BC”は、最初のメッシュ“ABC”によって動くことを抑制され、その結果、レベル“n-1”における点“A”、及び点“A'”は、実質的に同じになる。レベル“n”において、“A'”が存在すると共に、レベル“n-1”の“ABC”におけるその重心座標によって定義される。
【０１２２】
再メッシュ化処理は、より低いメッシュの変形を考慮する連続する階層レベルのノードの間の重み付けを獲得するように、動き推定のために時折使用される幾何学的なマルチグリッドアプローチ（geometric multi-grid approach）と互換性がある。この場合、ノードの重み付けは、以下のとおりに実行され得る。
【０１２３】
（ｉ）もし細かいノードが粗いノードの直接的な子供である場合、重み付けは“1”である。
（ｉｉ）もし細かいノードがいくつかの粗いノードから生じる場合、重み付けは、粗いノードに対する細かいノードの重心の重みの平均に対応する。
【０１２４】
一度全ての階層レベルにおいて新しいメッシュが完全に完成されたならば、ステップ１５において、動きは、画像のグループに関して再度推定される。この再度の推定は、新しいメッシュのいくつかの三角形によって復元されることが可能である画素に関する予防措置と共に、例えば、上述の数式（１）から数式（６）を用いて、ステップ１０と同様に実行され得る。この曖昧性は、新しいメッシュの一部の三角形のメッシュセルがオーバーラップするという事実のせいで存在する。
【０１２５】
不連続ゾーンにおいてそれを解決するために、可視性のマスクが各時間“t”において定義される。以前に例証された例において、このマスクは、図７における斜線部分と対応する。それは、時刻“t”において不連続ゾーンの中にある点で構成される（すなわち、新しいメッシュにおいて再使用される最初のメッシュのメッシュセルに属さない）と共に、例えば、この時刻“t”において決定される配置された破断線“L”の右側に位置する。不連続ゾーンの中の点は、右側のサブメッシュの三角形か、または左側のサブメッシュの三角形のいずれかによって復元されることが可能である。もし点がマスクに属する場合、数式（３）から数式（５）のアプリケーションに関して、そのような点に対して利用される三角形“i,j,k”は、右側のサブメッシュの三角形であると共に、そうでない場合は、左側のサブメッシュの三角形である。
【０１２６】
同様に、サブメッシュのスピルオーバ（溢出効果）のせいで、不連続ゾーンの外側の特定の点に関して、曖昧性が存在する。それを解決するために、不連続ゾーンから溢れ出るサブメッシュが前景に位置するか、またあ背景に位置するかを判定するように、以前に示されたように、値“z”が使用される。従って、不連続ゾーンの外側にあると共に、サブメッシュの三角形に属する点に関して、我々は、この点を含むメッシュの各三角形に関する値“z”を計算すると共に、我々は、数式（３）から数式（５）のアプリケーションに関して最も大きな値“z”を与える三角形を選択する。
【０１２７】
ステップ１５における最小化アルゴリズムの収束を向上させるために、最初のメッシュの保存されたノードにおける変位ベクトルを最初の推定１０の間に獲得された値に初期化することによって、傾斜降下を開始することが可能である。
【０１２８】
動きの再推定１５の過程で、再メッシュ化ステップ１４において追加されたノードのうちの１つが、時刻“t”において、画像のいずれの点においても復元されないということが起こる可能性がある。この場合において、汎関数（１）の最小化は、そのようなノードに関するどのような変位ベクトルも提供できない。変位ベクトルは、その場合に、同一のサブメッシュの隣接しているノードに関して獲得された変位ベクトルの補間によって再生成される。
【０１２９】
最終的に、ステップ２０で提供された動きパラメータは、画像グループが少なくとも１つの不連続ゾーンを含む場合、以下を含む。
【０１３０】
（ａ）不連続ゾーンに属する最初のメッシュのメッシュセルの表示。
（ｂ）各不連続ゾーンに関する、グループの各画像における少なくとも１つの破断線の位置。
（ｃ）もし不連続ゾーンが２つ以上の破断線を含む場合、ゾーンにおいて生成された様々なサブメッシュと関連付けられた、オブジェクトの相対的な深さを示すための値“ｚ”の表示。
（ｄ）ステップ１５において計算された、メッシュのノードにおける変位ベクトル。
【０１３１】
上述のような動き推定は、ビデオ符号化アプリケーションにおいて、特に使用できる。本発明を実装する符号器の単純化した構成図が、図１３において提示される。そのような符号器は、ビデオストリームの一連のデジタル画像に関する動き推定を引き受ける（モジュール３６）と共に、他方ではビデオ符号化の分野で知られている様々な技術に従って実行されるテクスチャーの符号化を引き受ける（モジュール３７）。本発明に基づいた符号器において、モジュール３６は、図３を参照して説明される方法に従って動作する。それが提供する動きパラメータ（ａ）から動きパラメータ（ｄ）は、モジュール３９によって符号器のデジタル出力ストリームに挿入される前に、テクスチャーの符号化情報と共に、モジュール３８による符号化の対象物を形成する。
【０１３２】
この出力ストリームを伝送する信号は、通信チャンネル上で、送信され得るか、または放送され得る。それは、同様に、光ディスク、磁気テープ等のような記録媒体に対する記録の対象物を形成し得る。
【０１３３】
図１４を参照すると、そのような符号器に適合するビデオ復号器は、符号器の出力ストリームと類似した入力ストリームを受信すると共に、このストリームにおいて、動きパラメータ、及びテクスチャー情報を分離する（モジュール４０）。モジュール４１、及びモジュール４２は、符号化されたビデオシーケンスの画像の連続するグループにおける動き、及びテクスチャーを復号化するために、各々、この情報を処理する。復号化された動き、及び復号化されたテクスチャーは、ビデオ画像を復元するために、合成モジュール４３によって処理される。
【０１３４】
動きの復号化モジュール４１は、以下のとおりに動作する。画像のグループは、従来の復号器と同様に、最初に、シーケンスにおいて正確に指摘される。慣例により決定された最初のメッシュに基づいて、モジュール４１は、上述の情報（ａ）に基づいて、不連続ゾーンを配置する。その後で、グループの第１の画像における破断線の位置（ｂ）に従って、これらの不連続ゾーンにおいて破断線を配置する。モジュール４１は、その場合に、図３から図１２を参照して以前に説明されたステップ１４に従って不連続ゾーンの再メッシュ化を引き受けることによって、非多様体メッシュを再生成する。非多様体メッシュのノードに割り当てられた定量化された変位ベクトルは、符号化されたストリームにおいて示される。各時間“t”における画像の変位フィールドを確定するために、モジュール４１は、以前に説明されたステップ１５において符号器によって使用される処理と同じ処理に基づいて、（もしこの点が不連続ゾーンに位置する場合）破断線に対する点の位置（ｂ）に従って、及び深さを示す値“z”（ｃ）に従って、各点の変位ベクトルを合成することを提供する三角形のメッシュセルを識別する。
【０１３５】
図１３に基づいた符号器、または図１４に基づいた復号器は、詳細な電子回路の形で具体化され得る。しかしながら、それは、非常に多くの場合、ソフトウェアの一部分の形で具体化される。上で示された方法のステップは、その場合に、ビデオ符号器またはビデオ復号器のプロセッサにより実行されるプログラムの命令によって制御される。符号化に関して、この装置は、例えばコンピュータ、ビデオカメラ、テレビリレーのワークポスト（work post of a television relay）、記録装置等であり得る。復号化に関して、それは、例えばコンピュータ、記録媒体読み取り機、テレビジョン信号受信機、画像表示装置等であり得る。
【図面の簡単な説明】
【０１３６】
【図１】画像の階層メッシュ化を例証する図である。
【図２】メッシュセルの反転現象を例証する図である。
【図３】本発明に基づく動き推定方法のフローチャートである。
【図４】本発明の実施例に使用される再メッシュ化処理を例証する図である。
【図５】本発明の実施例に使用される再メッシュ化処理を例証する図である。
【図６】本発明の実施例に使用される再メッシュ化処理を例証する図である。
【図７】本発明の実施例に使用される再メッシュ化処理を例証する図である。
【図８】最も細かいレベルにおいて一度決定された階層メッシュのより高いレベルにおける不連続ゾーンの定義を例証する図である。
【図９ａ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図９ｂ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図９ｃ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図９ｄ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１０ａ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１０ｂ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１０ｃ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１０ｄ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１１ａ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１１ｂ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１１ｃ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１１ｄ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１２ａ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１２ｂ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１２ｃ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１３】本発明に基づいたビデオ符号器の単純化された構成図である。
【図１４】本発明に基づいたビデオ復号器の単純化された構成図である。
【符号の説明】
【０１３７】
３６：動きの推定モジュール
３７：テクスチャーの符号化モジュール
３８：動きパラメータの符号化モジュール
３９：出力ストリームの組み立てモジュール
４０：パラメータの分離モジュール
４１：動きの復号化モジュール
４２：テクスチャーの復号化モジュール
４３：ビデオ画像の合成モジュール
【技術分野】
【０００１】
本発明は、動画像のデジタル処理に関するものであると共に、更に特に、シーケンスの連続する画像の間の動きを推定するための技術に関するものである。
【背景技術】
【０００２】
殆どのビデオ符号化方式（特に、ＭＰＥＧ−１，２，４、及びＩＴＵ−Ｔ Ｈ２６ｘ）は、画像のブロックワイズ（blockwise）パーティション分割による変換を用いた動きの表現を使用する。この動きモデルは、多数の問題を生み出す。それは、多くの場合、現在のビデオ符号化方式による復号化に見ることができるブロック効果の原因の大部分であると共に、それは特定のタイプの動き（ズーム、回転等）にあまり適していない表現モデルを提示する。
【０００３】
動きの表現の他のモードは、これらの欠陥を緩和するように提案された。後者の中の提案は、とりわけ、アクティブなメッシュが発見されることである。表現のこのモードにおいて、動きは、画像上に配置されたメッシュのノード上で定義された値のセットを用いて表現される。補間技術が、このメッシュのノードにおいて保存された値に基づいて、画像のあらゆる点の動きベクトルを推論するために使用される。一般的に、これは、ラグランジュタイプ補間（Lagrange type interpolation）を包含することができ、すなわち画像の点に割り当てられた動きベクトルは、隣接しているノードに関して計算されたベクトルのアフィン変換機能（affine function）である。
【０００４】
ＭＰＥＧのビデオ符号器または他のタイプの動き補償モードを、メッシュを基礎とする動き補償モードによって置き換えることが、従って可能である。分析合成タイプの符号化方式を達成するように、ビデオシーケンスの動きとテクスチャ情報を無相関化するためのメッシュを使用することが、同様に可能である。
【０００５】
これらのアクティブなメッシュは、特に、階層的なメッシュが使用されているとき、同一の時間において、動き情報のより効果的符号化の効力による、更に豊かな動きモデル及び改良された符号化の有効性の可能性を提供する（例えば国際公開第００／１４９６９号パンフレットを参照）。
【０００６】
ビデオシーケンスの真の動きが実際は一般的に不連続である一方、変形可能なメッシュは、動きフィールドの連続的表現を定義する。従って、場面において様々な平面、及びオブジェクトがオーバーラップする場合、不連続線を生成する隠蔽ゾーン及び露出ゾーンが現れる。
【０００７】
広範囲のメッシュによるそのような加工品のモデル化は、場面を構成する構成要素のビデオオブジェクトに従って分割されたメッシュとは対照的に、表現モデルの変更なしに解決されることができない問題を構成する。課題は、不連続ゾーン（zone of discontinuity）を判定することによって、このビジュアル劣化を解消すると共に、それを分析期間に制限することである。
【０００８】
従来は、実際の動きフィールドのこのタイプの障害は、そのメッシュ化された表現において、結果としてメッシュセルの反転になる。
【０００９】
後処理技術は、この問題を解決するために実行され得る。これらの技術の内の１つは、事後の修正によって進展すると共に、計算が動きベクトルを生成するように、動きベクトルを適用すること、問題がある動きベクトルを検出すること、そして、動きベクトルの値を訂正することから構成される。これらの技術の内の別のものは、反転がないそのような方法で、各反復において、ノードに対して予期される変位の一部分を加えることによって、及び処理が収束するまで反復を継続することによって、繰り返して進展する。
【００１０】
動き推定を１度実行する後処理技術が、実施された。従って、予測誤差の極小化に対する貢献とは無関係に動きベクトルが訂正されるので、結果は次善である。
【００１１】
改良は、最適化処理における非反転の制限を考慮することによって、動きフィールドを最適化することにある。この目的のために、動き推定は、メッシュセルのエリアがゼロに近づくときに、メッシュセルの変形を訂正することを可能にする拡張されたラグランジュを、二次の予測誤差に加えることによって、適合される。後者の技術は、但し後者が連続的フィールドを表すという条件で、実際に最適な解決法を決定することを可能にする。しかしながら、通常、ビデオシーケンスの性質は不連続である。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
国際公開第０１／４３４４６号パンフレットにおいて発表された別の技術は、不連続ゾーン（discontinuity zone）を復元するために、オブジェクトの出現、または消滅を監視することによって、不連続ゾーンを識別することにある。第１の動き推定は、メッシュセルの反転を妨げることなく、２つの連続する時刻“t1”と時刻“t2”の間で実行される。幾何学の基準を用いたこの第１の計算の完了と同時に反転を正確に指摘することによって、不連続ゾーンは検出される。処理は、その場合に、時刻“t1”と時刻“t2”の間で新しい動き推定を達成することから成る一方、検討された２つの画像の間の予測誤差を最小限にするために、少なくとも１つの反転を含む問題のあるゾーンの寄与を最適化基準から除外する。この再最適化は、連続的なゾーンに関する最適な動きベクトルを決定する（時刻“t1”と時刻“t2”の間で全単射を認める）と共に、従って、前の最適化において獲得された、不連続ゾーンによって生成される動きベクトル値の妨害を回避することを可能にする。問題のあるゾーンは、画像圧縮によって、周波数近似、もしくは空間近似の対象を形成すると共に、それらは、ビデオオブジェクトの追跡によって、最適化の方法から除外される。
【００１３】
様々な既知の技術は、不連続ゾーンにおける連続的ゾーンに基づいて計算された動きを強制的に押し付けることによって、不連続な動きフィールドを連続的にするように試みる。これは、不連続ゾーンにおける間違った動きと、質が悪いテクスチャーの一時的な予測に帰着すると共に、従って符号化の費用オーバヘッドに帰着する。
【００１４】
不連続ゾーンを除外することを目的としている技術は、それらのゾーンにどんな動きも強制的に押し付けないと共に、それらを異なって符号化する。しかしながら、かなりの数の不連続ゾーンがある場合には、同じくらい異なって符号化されるべき多くのゾーンがあり、これらのストリームのヘッダーを符号化するのに費用オーバーヘッドを必要とする。更に、スケーラブル符号化の枠組の中で、この技術は比較的高価である。
【００１５】
本発明の目的は、２次元（２Ｄ）メッシュを用いてビデオシーケンスの動きを推定すること、及び最も良く、真の動きフィールドを描写するために、不連続な方法でこの動きを描写することである。
【課題を解決するための手段】
【００１６】
本発明は、従って、
−ノードによって境界が定められるメッシュセルを含むと共に、シーケンスの参照画像に適用されるべき第１のメッシュを生成する段階と、
−画像の点が属する前記第１のメッシュの前記メッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、画像の各点に割り当てることによって、前記参照画像を包含する画像のグループにおける第１の変位フィールドを推定する段階と、
−前記第１の変位フィールドを分析することによって、各々が画像のグループにおけるメッシュセルの変形基準を満足する少なくとも１つの前記メッシュセルを含む、第１のメッシュにおける少なくとも１つの不連続ゾーンを検出する段階と、
−各検出された前記不連続ゾーンにおいて、画像のグループにおいて現れる少なくとも１つの破断線（break line）を判定する段階と、
−前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの検出された不連続ゾーンに関して、前記不連続ゾーンで判定される前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含む、前記参照画面に適用されるべき第２のメッシュを生成する段階と、
−検出された前記不連続ゾーンに位置する各点が属する前記第２のメッシュの選択されたメッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、検出された前記不連続ゾーンに位置する各点に割り当てることによって、画像のグループにおける第２の変位フィールドを推定する段階とを含み、
前記２つのサブメッシュの各々は、前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含み、前記選択されたメッシュセルが、前記不連続ゾーンで判定される前記破断線に対する前記点の位置によって決まることを特徴とする一連のデジタル動画像における動き推定の方法を提案する。
【００１７】
その方法は、動きを判定するための大域的最適化を実行する。推測的な制限は、最適化されるべき基準に与えられないと共に、それは、同様に、動画に頻繁に現れる不連続ゾーンを計算から除外することを回避する。従って、実行される動き推定は、不連続ゾーンを含んでいても、破断線が信頼できる方法においてタグを付けられるので、最適であり得る。推定された動きは、それ以降、ビデオ符号器によって使用されることができることになる。この枠組の中で、それは、メッシュの不連続ゾーンにおいてさえも、シーケンスの画像の良い予測を可能にすることになると共に、ビデオシーケンスの符号化のコストにおいて改良を可能にすることになる。推定された動きを表すパラメータは、その場合に、復号器に送信されるか、または次の復号化を目的としてメモリに記録されることになる。
【００１８】
動き推定方法は、前記変位フィールドの推定が、メッシュの最も粗い階層レベル（１）から最も細かい階層レベル（nivFin）に対して達成される階層型メッシュの使用に適合する。不連続ゾーンは、好ましくは、メッシュセルの変形基準を満足する最も細かい階層レベルのメッシュセルの隣接しているセットとして検出される。それ以降、それは、メッシュセルの変形基準を満足する最も細かい階層レベルの少なくとも１つのそれぞれのメッシュを含む少なくとも１つのメッシュセルで構成されるように、より高い階層レベルで定義される。
【００１９】
有利に、第２のメッシュの２つのサブメッシュは、最も細かい階層レベル“nivFin”を発端に生成され、より高いレベルのメッシュセルは、それ以降、階層の累進的な上流方向へのバックトラッキングの間に生成される。
【００２０】
階層レベル“n”からすぐ上の階層レベル“n-1”へのバックトラッキングは、サブメッシュの各々に関して、及び“1＜n≦nivFin”に関して、
/a/レベル“n”で事前に定義される前記サブメッシュの各メッシュセルをレベル“n-1”で生成された前記サブメッシュの新しいメッシュセルに統合する段階と、
/b/“n'=n”を計算する段階と、
/c/もしレベル“n'-1”の前記新しいメッシュセルがレベル“n'”で既に生成された前記サブメッシュのメッシュセルによって完成され得ない場合、レベル“n'-1”の前記新しいメッシュセルを完成するために、レベル“n'”で前記サブメッシュの少なくとも１つの新しいメッシュセルを生成する段階と、
/d/もし“n'＜nivFin”である場合、“n'”を１ユニットだけ増やして前記“/c/”段階から繰り返す段階とを含む。
【００２１】
方法の好ましい実施例において、それぞれの深度値は、前記正常部分のノード、及び前記第２のメッシュの各サブメッシュの追加のノードに割り当てられる。前記不連続ゾーンに関して生成されたサブメッシュの追加のノードに割り当てられる値は、前記不連続ゾーンで判定される前記破断線に対する前記サブメッシュの位置によって決まる。第２のメッシュの正常部分のメッシュセル、及びサブメッシュの少なくとも１つのメッシュセルに属する画像の各点に関して、前記第２の変位フィールドを推定する段階は、前記点を含む各メッシュセルに関して、前記メッシュセルの境界を定めるノードにそれぞれ割り当てられた前記深度値の加重和を計算する段階と、前記点に対する前記変位値の割り当てに関して、計算された前記加重和が最大のメッシュセルを選択する段階とを含む。
【００２２】
これらの深度値の使用は、画像のグループに共存する数個の平面の存在を明らかにすることを可能にする。そこに２つより多い平面がある場合に、相対的な深度値は、動きの合成のために、復号器に伝達されなければならないことになる。
【００２３】
本発明の他の特徴は、上記で定義されるような方法を実現するように適合された手段を備える、一連のデジタル動画像における動き推定のための装置の他に、前記装置の計算ユニットによってプログラムを実行した場合に上記で定義されるような動き推定の方法の段階を実現するための命令を含む、動画を処理するための装置にインストールされるべきコンピュータプログラムとも関係がある。
【００２４】
本発明は、同様に、一連のデジタル動画像における動きを推定するための手段と、前記動きを推定するための手段によって生成された動きパラメータを含む出力ストリームを組み立てるための手段とを備え、前記動きを推定するための手段が、上記で定義されるような方法に従って動作するように設計されるビデオ符号器を提案する。
【００２５】
本発明の更に別の特徴は、上記で定義されるような方法を実行することによって獲得された動きパラメータの表現を含む、一連のデジタル動画像を代表する信号、及びそのような信号が記録される記録媒体と関係がある。
【００２６】
参照画像を包含する画像のグループに関して、動きパラメータは、
−前記参照画像に適用されるべき第１のメッシュにおいて、画像のグループにおける少なくとも１つの不連続ゾーンを構成するメッシュセルを示す第１の動きパラメータと、
−各不連続ゾーンにおいて少なくとも１つの破断線を位置決めするための第２の動きパラメータと、
−前記参照画像に適用されるべき第２のメッシュのノードに割り当てられた変位値を示す第３の動きパラメータとを含み、
前記第２のメッシュは、前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの不連続ゾーンに関して、前記不連続ゾーンに位置する前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含み、前記２つのサブメッシュの各々は、前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含む。
【００２７】
信号で表される動きパラメータは、正常部分のノード、及び第２のメッシュの各サブメッシュの追加のノードにそれぞれ割り当てられる深度値を示すパラメータで補完され得る。
【００２８】
本発明は、ビデオ復号器か、または動画を処理するため他の装置において実行されて、動きを復号化する側で同様に具体化される。
【００２９】
本発明は、従って、ノードによって境界が定められるメッシュセルを含む画像のメッシュを用いた、一連のデジタル動画像における動きをデコードする方法を提案する。
【００３０】
前記方法は、
−上記で定義されるような動きパラメータを含む入力ストリームを受信する段階と、
−前記第１の動きパラメータ及び前記第２の動きパラメータに基づいて前記第２のメッシュを生成する段階と、
−前記第３の動きパラメータに基づいて獲得された変位値を、前記第２のメッシュの各ノードに割り当てることによって、そして検出された前記不連続ゾーンに位置する各点が属する前記第２のメッシュの選択されたメッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、検出された前記不連続ゾーンに位置する各点に割り当てることによって、画像のグループにおける変位フィールドを生成する段階とを含み、前記選択されたメッシュセルが、前記不連続ゾーンで判定される前記破断線に対する前記点の位置によって決まる。
【００３１】
本発明の他の特徴は、上記で定義されるような方法を実現するように適合された手段を備える、一連のデジタル動画像における動きの復号化のための装置の他に、前記装置の計算ユニットによってプログラムを実行した場合に上記で定義されるような動きの復号化の方法の段階を実現するための命令を含む、動画を処理するための装置にインストールされるべきコンピュータプログラムとも関係がある。
【００３２】
本発明は、更に、動きを復号化する手段と、前記動きを復号化する手段によって生成された変位フィールドを考慮して、一連のデジタル動画像を組み立てるための合成手段とを備え、それらが、上記で定義されるような動きの復号化の方法に従って動作するように設計されているビデオ復号器を提案する。
【発明を実施するための最良の形態】
【００３３】
本発明の他の特徴、及び利点は、添付の図面を参照することによって、これから先の制限しない代表的な実施例の記述に現れることになる。
【００３４】
“x”、“y”が、画像のフィールドにおける画素の座標を指定すると共に、“t”が、ここではシーケンスの各画像において“１”ずつ増加すると仮定された離散化時刻（discretized time）を指定する、一連のデジタル画像“I(x,y,t)”を考察する。画素と関連付けられた値“I(x,y,t)”は、一般的に輝度値である。
【００３５】
動き推定は、画像“I(x,y,t)”における座標“(x,y)”を有する各点について、画像“I(x,y,t-1)”から、画像“I(x,y,t)”の良い近似である置き換えられた画像“I'(x,y,t)=I(x-dx,y-dy,t-1)”を構成することを可能にする変位ベクトル“D(x,y,t)=(dx,dy)”を生成することから構成される。
【００３６】
その計算は、Ωに対応する推定に関して実行される。それは、下記式の関数“Φ(t)”を最小化する変位フィールド“D(x,y,t)”を決定することから構成される。
【００３７】
【数１】
【００３８】
ここで、“ρ(A,B)”は、最も一般的な式が“ρ(A,B)=(A-B)2”である測定基準である。
【００３９】
画像のメッシュの使用は、未知数の数を減少させることを可能にする。メッシュのノード“i”に位置する点の変位ベクトル“D(xi[t],yi[t],t)”だけが検索される。これらのノードから離れて、変位フィールド“D(x,y,t)”は、例えば、下記のアフィン変換に関する手順に従って、補間される。
【００４０】
【数２】
【００４１】
ここで、加重値“wi(x,y,t)”は、時刻“t”における画像内のノード“i”の位置に関して表された点“(x,y)”の座標を示す。
【００４２】
都合の良いメッシュは、その頂点が、時刻“t”において、それぞれが座標“(xi[t],yi[t])”、座標“(xj[t],yj[t])”、及び座標“(xk[t],yk[t])”を有するメッシュのノード“i”、“j”、“k”である三角形に、各点“(x,y)”が属すると考えられる三角形のメッシュである。時刻“t”における点“(x,y)”に関連付けられた補間の加重値は、以下の数式によって与えられた三角形の重心座標である。
【００４３】
【数３】
【００４４】
【数４】
【００４５】
【数５】
【００４６】
【数６】
【００４７】
ここで、“πi,j,k[t]=xj[t].yk[t]-xk[t].yj[t]+xk[t].yi[t]-xi[t].yk[t]+xi[t].yj[t]-xj[t].yi[t]”は、時刻“t”における三角形に関連づけられたベクトル積である。
【００４８】
その計算は、一般的に、およそ１０個の画像程度の、シーケンスの連続的な画像のグループに関して実施される。そのメッシュは、習慣的に、正三角形の編み目（network）によって、グループの第１の画像（t=0）に関して定義される。変位ベクトル“D(xi[1],yi[1],1)”は、例えば、ガウス−サイデル（Gauss-Seide）、または類似のタイプの最急降下法を適用することによる関数“Q(1)”の極小化によって推定される。時刻“1”におけるメッシュのノード“i”の位置は、数式“(xi[1],yi[1])=(xi[0],yi[0])+D(xi[1],yi[1],1)”を通して、これから推論される。“Q(t)”の極小化による変位ベクトル“D(xi[t],yi[t],t)”の推定、そして時刻“t”におけるメッシュのノードの位置の計算：“(xi[t],yi[t])=(xi[t‐1],yi[t‐1])+D(xi[t],yi[t],t)”という、この処理は、グループの最後の画像（t=2,3,4等）まで繰り返される。
【００４９】
動き推定は、それ自体が周知である方法でシステムの更に良い収束を保証する階層型メッシュを用いて有利に実行される。メッシュの特定の細かさは、忠実に画像の中の動きを表すために必要である。しかし、強い動きの事象において、先行する極小化技術は、もしそれが直接細かいメッシュに適用される場合、収束しないかもしれない。更に、非常に細かいメッシュの使用は、過度に大きな数のパラメータのせいによるシステムの不安定性の原因となる可能性がある。
【００５０】
図１は、代表的な階層型メッシュを示す。階層型表現は、いくつかの表現レベルから構成される。符号３０で示される最も低いレベル（図中のレベル０）は、メッシュを定義するための３つのノードだけを備えた粗いフィールドを有する。符号３２、３３、３５で示される順で更に細かいレベルの方へ向かうと、そのフィールドは、次第に更に濃密になると共に、メッシュのノードの数が増加する。動きの品質はレベルによって異なり、符号３０で示される最も低いレベルはシーンの支配的な動きを表すと共に、細かいレベルは、局所的な動きを表すための支配的な動きを絞り込む。階層型メッシュのレベルの数は、推定段階の調節可能なパラメータであり、それは、推定されるべきシーケンスに従って変化し得る。
【００５１】
階層型メッシュによる動き推定の技術において、１つのレベルは、符号３０で示される最も粗いレベル上の動きを推定することによって始まり、そして、１つのレベルは、以前のレベルにおいて推定された変位値から推論された節の変位値に基づいて傾斜降下（gradient descent）を始める次のレベルに移動する階層型メッシュのいくつかのレベルが、画像に基づいて生成され、２つのレベルに共通のノードは、まさに推定されたそれらに等しい最初の変位ベクトルを受け取ると共に、より細かいレベルにおいて加えられたノードは、空間的補間によって計算された最初の変位ベクトルを受け取る。反復の終りにおいて、復号器に送信されるように定量化されるのは、最も細かいレベルにおいて推定された変位ベクトルである。
【００５２】
階層型メッシュによる動き推定の技術は、最初の画像に基づいて構成されたフィルタ処理されると共に廃棄される画像の角錐に作用するマルチ解像度推定技術（multi-resolution estimation technique）と結合できる。階層型メッシュのレベルにおける動き推定は、その場合に、適切な解像度のレベルにおいてサンプリングされた画像に基づいて実行される。
【００５３】
メッシュを基礎とする動き推定技術に関する一般的な問題は、メッシュセルの反転の問題である。この問題は、２つの連続する時刻における画像のメッシュを、図の左側部分において、これらの２つの時刻の間で推定されたメッシュの基本の三角形の頂点を形成するノード“i,j,k”における変位ベクトルの例と共に発見する図２で例証される。この三角形の反転は、ノード“i”、及びノード“j”を通過する直線に交差するノード“k”に起因する。
【００５４】
一般的に、三角形“i,j,k”の反転は、ベクトル積“πi,j,k[t]”の符号の変更に対応する。そのような人為的な結果は、動き推定を非常に妨害する。それらは、一般的に、撮影されたシーンの様々な平面におけるオブジェクトの相対的な動きのせいである。図２の実例は、（ゼロエリアの三角形を通過して）単一の三角形が反転するので、非常に単純化される。実際には、オーバーラップは、通常、画像における特定の広がりを有する不連続ゾーン（discontinuity zone）で発生する。
【００５５】
階層型メッシュによって、メッシュセルの反転は、必然的に、粗いレベルにおける発生の可能性より、細かいレベルにおける更に大きな発生の可能性を有している。
【００５６】
メッシュセルの反転の問題を扱うために、本発明は、不連続ゾーンのタグ付け、及びそれらが含む破断線（break line）のタグ付けを使用する。画像の再メッシュ化は、破断線のどちらの側においても、最初のメッシュに固定された複数のサブメッシュを用いて、不連続ゾーンにおいて達成される。不連続ゾーンで生成された複数のサブメッシュは、それらが相互にオーバーラップするように、破断線を越えて伸びる。それらは、不連続ゾーンの外側に更にはみ出すことができる。式（２）のような補間の式を用いて不連続ゾーンに位置する像点（image point）の変位を推定するために、破断線または複数の破断線に関する点の位置の関数として選択されたサブメッシュの内の１つのノードが参照される。従って、サブメッシュは、それらの使用がシーンにおいて出現するか、または消滅するオブジェクトに従って決定される、一連の画像に存在する様々な平面から構成されることを可能にする。
【００５７】
本発明は、動きの不連続ゾーンを、符号化の時に、それらを欠陥がある状態にするか、またはそれらを排斥することなく、管理することを可能にする。オーバーラップ、または露出面が検出される場合、その原理は、不連続性が作成される所で局所的にメッシュを切ることであると共に、メッシュをいわゆる“非多様体（non-manifold）”メッシュに変換することである。非多様体メッシュは、エッジが２つ以上のメッシュセルによって共有され得るメッシュである。それによって、ビデオシーケンスにおける動きを推定すること、及び不連続の動きフィールドを形に表すことを可能にする。利点は、従って、符号化の時に、不連続ゾーンを、連続的なゾーンと同じ方法で考慮することを可能にすることである。
【００５８】
図３は、本発明による動き推定方法のフローチャートを示す。
【００５９】
最初のステップ９は、符号化されるべきビデオシーケンスの画像に関する最初のメッシュを定義することから構成される。次に、ステップ１０において、Ｔ個の連続した画像のグループにおける動きフィールドの最初の推定を始める。この推定は、例えば、上記で説明される手順に従って、好ましくは階層型メッシュを用いて従来の方法において達成される。この計算の過程で、特定の三角形のメッシュセルは、反転するか、もしくは非常に変形することができる。
【００６０】
それ以降、その方法は、最初のメッシュにおける不連続ゾーンを検出するためのステップ１１を含む。
【００６１】
不連続ゾーンは、それぞれ、最も細かい階層レベルにおいて定義された縮退したメッシュセルの隣接しているセットから構成される。それらは、ステップ１０における動き推定の過程で反転する三角形を少なくとも含む。これらの三角形は、最も細かい階層レベルにおける、及び連続する時刻“t=0,1,2,...,T-1,T”におけるメッシュの様々な三角形に関して、（最小限にされるべき汎関数における変位の補間のために）ステップ１０において計算されたベクトル積“πi,j,k[t]”に従って容易に検出可能である。三角形は、ベクトル積“πijk[t]”が全て正であるように、初めに配置される。メッシュセルの反転は、その場合に、負のベクトル積によって明らかにされる。
【００６２】
検出は、不連続ゾーンにおいて、（ベクトル積“πi,j,k[t]”の絶対値の半分に等しい）その領域がゼロに近くなる、すなわち、少なくとも１つの時刻“t”に関して事前に定義されたしきい値未満である三角形のメッシュセル“i,j,k”を含むように一般化され得る。
【００６３】
不連続ゾーンに含まれるべき縮退した三角形の検出は、更に一般的に、時刻“0”の画像と時刻“T”の画像との間の三角形の変形の学習を含むことができる。もしメッシュセルの変形がある限界を越える場合、このメッシュセルは縮退していると考えられる。
【００６４】
縮退したメッシュセルの隣接しているセットは、不連続ゾーンを形成する。それは、動きにおいて不連続性が明白なゾーンである。それは、最も細かい階層レベルで定義されると共に、最も細かい階層レベルを構成する三角形のメッシュセル（または、それに接しているノード）は、復号器に送信されることになるパラメータの一部分を形成する。同様に、不連続ゾーンの形状は、スプライン（spline）で表されることができる。
【００６５】
もし不連続ゾーンがステップ１１（テスト１２）において検出されない場合、動き推定方法は、ビデオ復号器に送信されるように定量化されることになる動きのパラメータが供給されるステップ２０において終了する。この場合、これらのパラメータは、ステップ１０において獲得されたパラメータであると共に、不連続ゾーンが検出されなかった(連続的な動きである)ことを信号伝達するための表示が加えられる。
【００６６】
もし画像のグループにおいて１つ以上の不連続ゾーンが検出される場合、まず検出された各不連続ゾーンにおいて破断線の判定に着手する（ステップ１３）。
【００６７】
破断線は、ゾーン内に不連続性を生み出したオブジェクトの形状に関して位置決めされる。不連続ゾーンにおける単一の破断線の場合がこれから先に詳述されることになる。処理は、同一のゾーンの中のいくつかの破断線に一般化が可能であることが気付かれることになる。
【００６８】
オブジェクトの形状は、内側の領域（前景領域）、及び外側の領域（背景領域）を定義するように配置される。本質的に知られているいくつかの手順が、ステップ１３においてこの形状を発見するために適用できる。もしシーケンスの画像を分割するためのマスクが既に利用可能な場合、その形状は、これらのマスクに基づいて抽出される。しかしながら、大部分のシーケンスに関しては、分割マスクが利用可能ではない。
【００６９】
この場合、画像は、“Dorin Comaniciu”及び“Peter Meer”によって、“IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, No. 5, May 2002, pp. 603-619”の“Mean Shift: A Robust Approach Toward Feature Space Analysis”において示された技術のような“平均シフト”技術によって事前分割（pre-segment）され得る。それ以降、一連の拡張、及び一連の形態学に関する浸食（morphological erosion）は、小さな分割された領域を除去することを可能にする。オブジェクトの形状は、最終的に分割された画像から抽出される。
【００７０】
ステップ１３において、同様に、顕著な点を検出するための技術が適用され得る。顕著な点は、主にオブジェクトの形状に基づいて位置決めされる。完全な形状を定義しない顕著な点のリストに、これらの点の連鎖に基づく形状の微調整の段階を加えることは適切である。画像“I”の顕著な点は、高周波の領域に属する画像“I”の画素に対応する。それらを検出するために、ウェーブレット理論を使用することが可能である。ウェーブレット変換は、１／２、１／４等の様々な解像度で画像を表すことを可能にする画像のマルチ解像度の表現である。従って、各解像度レベル“2j(j≦-1)”において、ウェーブレット変換は、サイズ“2k+j×21+j”の画像のグループの形で、サイズ“n×m=2k×2l(k,l ε Z)”の画像“Im”、すなわち、粗い画像である
【００７１】
【数７】
【００７２】
と、高い水平周波数を表す細部の画像である
【００７３】
【数８】
【００７４】
、すなわち水平の形状と、高い垂直周波数を表す細部の画像である
【００７５】
【数９】
【００７６】
、すなわち垂直の形状と、そして、高い対角線の周波数を表す細部の画像である
【００７７】
【数１０】
【００７８】
、すなわち角とを表す。
【００７９】
詳細な３つの画像の各々は、（
【００８０】
【数１１】
【００８１】
の状態で）各方向において、続いてサブサンプリングが実行される、２つの係数によるフィルタ処理を実行することによって、
【００８２】
【数１２】
【００８３】
から獲得される。画像の顕著な点を検出するために、ウェーブレットを基礎とする最小の解像度レベル“2r(r<=-1)”が最初に使用される。一度ウェーブレット変換が実行されたなら、３つの詳細画像の各々
【００８４】
【数１３】
【００８５】
【数１４】
【００８６】
【数１５】
【００８７】
は、ウェーブレット係数のツリー構造を構成するように、詳しく検討される。このツリー構造は、画像符号化の分野において知られている、いわゆるに“Zerotree”アプローチに基づいている。それによって、解像度“2r”における各ウェーブレット係数の重要性を反映するサイズ“2k+r×2l+r”の特性マップを適所に置くことが可能になる。従って、有意の突出性を有する係数は、高い周波数を示す“Im”の領域に対応する。具体的には、解像度“2r”における有意の係数のウェーブレット係数は、特別な方向（水平の方向、垂直の方向、もしくは斜めの方向）に従っている画像である
【００８８】
【数１６】
【００８９】
の形状と対応する。“Zerotree”アプローチは、解像度“2r”におけるウェーブレット係数の各々が、画像“Im”におけるサイズ“2-r×2-r”の空間ゾーンに対応することを示す。構成された特性マップに基づいて、従って、“Im”の“2-r×2-r”の画素の中から、このゾーンを最も代表する画素を選択することが可能である。
【００９０】
一度不連続ゾーンにおいてこれらの顕著な点が測定されたならば、それらは、利用可能な破断線を有するように連結される。この目的のために、点の連鎖の既知の技術、あるいは補間または多項式の近似の技術（ニュートン、スプライン、チェビチェフ（Tchebicheff）、最小２乗等）を使用することが可能である。
【００９１】
ステップ１３において、画像のグループの各々の画像における破断線が判定されるということに注目するべきである。これらの線の位置は、復号器に伝達されることを目的として、ステップ１３において供給される動きパラメータの一部となることになる。
【００９２】
方法のステップ１４において、ステップ１１において検出された不連続ゾーンは、非多様体（non-manifold）再メッシュ化の対象を形成する。この再メッシュ化は、最も細かい階層レベルにおいて最初に実行される。
【００９３】
図４は、最初の三角形のメッシュの８つの隣接しているメッシュセルから構成される代表的な不連続ゾーンＺを示す。このメッシュは、グループの最初の画像に関するその定義の間に、正三角形から構成される。図４は、ステップ１３においてゾーンＺ内で判定されて、配置された破断線“L”を示す。
【００９４】
ステップ１４において採用された新しいメッシュは、不連続ゾーンに属する最初のメッシュの三角形で構成される正常部分を含む。破断線“L”を含んでいる各不連続ゾーンＺにおいて、不連続ゾーンＺのエッジに沿った正常部分に付着する２つのサブメッシュが生成される。これらの２つのサブメッシュの各々は、破断線“L”の面に割り当てられると共に、それは、不連続ゾーン“Z”のエッジに沿ったこの面に位置する最初のメッシュのノードを含む。
【００９５】
図５、及び図６における破線の三角形は、従って、それぞれ、図４の不連続ゾーン“Z”において生成され得る２つのサブメッシュを表す。この例において、図４において“a,b,c,d,e,f”で示される最初のメッシュのノードは、図５において示される“左側の”サブメッシュに属する（すなわち、破断線“L”の左側の最初のメッシュに付着すると共に、ここで、左側及び右側は、破断線“L”に関して決定された方向性に関連して定義される。）と共に、図４において“a,f,g,h,i,j”で示される最初のメッシュのノードは、図６において示される“右側の”サブメッシュに属する。
【００９６】
不連続ゾーンに接する最初のメッシュのノードのいくつかは、２つのサブメッシュに共通である（ここでは、ノード“a”及びノード“f”）。
【００９７】
図５の例において、左側のサブメッシュは、８個の新しいノード“a'-h'”と、１６個の新しい三角形(a,a',h')，(a,b,a')，(b,b',a')，(b,c,b')，(c,d,b')，(d,c',b')，(d,e,c')，(e,d',c')，(e,f,d')，(f,e',d')，(d',e',f')、(c',d',f')，(c',f',g')，(b',c',g')，(a',b',g')、及び(a',g',h')を含む。
【００９８】
図６の例において、右側のサブメッシュは、８個の新しいノード“a"-h"”と、１６個の新しい三角形(a,h",a")，(j,a,a")，(i,j,a")，(i,a",b")，(i,b",c")，(h,i,c")，(h,c",d")，(g,h,d")，(f,g,d")，(f,d",e")，(c",e",d")，(c",f",e")，(b",f",c")，(b",g",f")，(a",g",b")，及び(a",h",g")を含む。
【００９９】
新しいサブメッシュにおいて生成された追加のノードは、第１の画像内で、最初のメッシュのノードの位置と一致する位置を有することができる。図５及び図６において、図の読取りを容易にするために、それらはシフトされて表される。
【０１００】
不連続線“L”によって横断される不連続ゾーン“Z”の境界におけるエッジのノードは、最初のメッシュと共にだけ動くことができる境界ノードである。これら境界ノードは、以下の３つのタイプであり得る。
【０１０１】
−単に左側のサブメッシュの基礎としての役目を果たす左側の境界ノードであって、それらは、図４から図６におけるノード“b”、ノード“c”、ノード“d”、及びノード“e”である。
−単に右側のサブメッシュの基礎としての役目を果たす右側の境界ノードであって、それらは、図４から図６におけるノード“g”、ノード“h”、ノード“i”、及びノード“j”である。
−両方のサブメッシュの基礎としての役目を果たす共有された境界ノードであって、それらは、図４から図６におけるノード“a”、及びノード“f”である。
【０１０２】
破断線“L”が少なくとも１つの境界ノードを頂点として有する三角形を横切る場合、このノードは、配置された線に対するその位置の関数として、左側の境界、もしくは右側の境界であるとして特定される。破断線“L”が終了する三角形に関して、例えば、（図４〜図６にあるように、）破断線“L”に横切られた境界に位置するノードを左側及び右側の境界ノードとして特定し、そして第３のノードを共有された境界ノードとして、特定することが可能である。別の可能性は、それが三角形の境界に遭遇するまで、外挿法（extrapolation）によって破断線を延長することであると共に、この境界に位置するノードを共有された境界ノードとして特定し、そして配置された線に対するその位置の関数として第３のノードを左側または右側の境界ノードとして特定することである。
【０１０３】
ビデオシーケンスにおいて発生する可能性がある考えられる露出面を考慮するために、新しいメッシュセルは、図５及び図６によって示されたように、不連続ゾーン“Z”を越えて伸びる。正常部分のメッシュセル、及びサブメッシュのメッシュセルは、その場合に、オーバーラップする。
【０１０４】
画像の復元の間の不一致を回避するために、３次元画像合成の分野ではその使用が良く知られている“２−バッファ（2-buffer）”に端を発する、ノードにおける“２−オーダー（2-order）”の手順が使用される。ここで使用される非多様体（non-manifold）メッシュに対する適応は、各サブメッシュの新しいノードに、このサブメッシュに割り当てられた正または負の深度値Ｚを割り当てることによって実行される。
【０１０５】
保存された最初のメッシュのノードは、深度値“Z=0”を受け取る。値“z>0”は、一般的に、前景のオブジェクトに対応すると共に、値“z<0”は、背景のオブジェクトに対応する。“z”の符号は、破断線“L”の方向性によって与えられる。その形状が破断線に対応する前景のオブジェクトは、破断線“L”の方向性に関連して、（例えば、その方向性という意味で動いている場合に、線の右側に関連して）位置決めされる。従って、図４〜図７の場合に、図７における斜線部分は、その破断線“L”が形状を構成するオブジェクトに属している。
【０１０６】
ノードにおけるこの値“z”は、メッシュセルの各点において補間技術（例えば、アフィン変換）によって“z”の値を計算することを可能にする。いくつかのメッシュセルによって復元されることが可能である点の復元の間に、値ｚが、これらの様々なメッシュセルに関して、この点において計算されると共に、最も大きい値ｚを与えるメッシュセルを保持するように、これらの値は比較される。これは、背景に対しての前景においてオブジェクトを支持することを可能にする。
【０１０７】
不連続ゾーンにいくつかの破断線が現れる場合、一連の画像の対応する部分に２つ以上の平面が存在する。破断線の検出は、様々な平面を位置決めすることを可能にすると共に、それらは、区別された値“z”を割り当てられる。上記の手順は、その場合に、画像の各点の復元のために、関連したメッシュセルを選択することを可能にする。ノードにおける値“z”は、そのためにメッシュセルが導入された画像を最もよく復元するように位置決めされる。その位置決めは、最初の画像と復元された画像との間の平均二乗誤差を最小限にしようと試みるＩＣＭ（Iterative Condition Mode）タイプの反復的アルゴリズムを用いて実行され得る。不連続ゾーンにいくつかの破断線があるとき、対応するサブメッシュに関して決定された値“z”は、復号器に送信されるべき動きのパラメータの一部を形成する。
【０１０８】
最も細かいレベルにおいて一度再メッシュ化が達成されると、破断線“L”が表す不連続性は、より高いレベルを通して、あるレベルで消滅するまで上流方向にバックトラックされる。不連続性がメッシュレベルに存在する限り、このレベルに関して定義された不連続ゾーンは、メッシュの階層を維持するように低いレベルの再メッシュ化を考慮することによって、再メッシュ化される。
【０１０９】
階層構造を通した不連続性の上流方向へのバックトラッキングは、各レベルに関して不連続ゾーンを決定する段階と、ゾーンの境界におけるノードに課せられる制限を決定する段階という２つのステップを含む。“nivFin”を、最初に再メッシュ化が実行されたメッシュの最も細かいレベルとする。“nivFin”より小さいか、または等しいレベル“n”に関して、もし不連続ゾーンが検出された場合、レベル“n-1”における不連続ゾーンは、図８によって示されるように、レベル“n”の閉鎖された状態のゾーンのメッシュセルの親メッシュセルのセットによって定義される。
【０１１０】
２つのサブメッシュに共有された境界ノードの制限は、例えば、以下のアルゴリズムに従って、階層構造を通して上流方向にバックトラックされる。
【０１１１】
レベル“n”において共有された境界ノードを構成するノード“m”に関して、
・もし“m”がレベル“n-1”に親“p”を有している場合、“p”は、レベル“n-1”において共有された境界ノードとなる。
・そうでなければ、“A”を、破断線“L”がそれを通してレベル“n-1”の三角形の中を貫通するエッジとすると共に、“q”を、このエッジの反対側に位置するメッシュセルノードとする。
【０１１２】
破断線“L”は、“q”のところまで人工的に延長されると共に、このノード“q”は、レベル“n-1”に関して共有された境界ノードになる。
【０１１３】
既に再メッシュ化された階層レベル“n”より低い階層レベル“n-1”に関する新しいメッシュセルの生成は、以下の３つのタイプであり得る。
【０１１４】
「１／」
図９ａから図９ｄ：破断線“L”は、レベル“n-1”における不連続ゾーンに属するメッシュセル“ABC”と完全に交差する。
【０１１５】
右側に関する境界ノードはノード“C”及びノード“B”であり、新しいノード“A'”がレベル“n-1”で作成される。新しいメッシュレベル“n-1”のセル“A'BC”は、レベル“n”のメッシュセル“A'E'D'”、“E'CF”、“D'FB”、及び“E'D'F”を、ドーターメッシュセル（daughter mesh cell）として見なすと共に、ここで、“F”は、エッジ“B-C”の中央であり、“D'”及び“E'”は、レベル“n”の右側の再メッシュ化によって作成されたノードである。メッシュセル“A'E'D'”は、たとえ、もしそれがレベル“n”の再メッシュ化の間に生成されなかったとしても、レベル“n”と関係があるが、しかし、より高いレベルの“n-1”の場合は、再メッシュ化の間に生成されなければならない。同様に、左側の倍増に関して、境界ノードは“A”であり、ノード“B'”、“C'”、及び“F'”は、レベル“n-1”の再メッシュ化によって作成されている。レベル“n-1”の新しいメッシュセル“AB'C'”は、ドーターメッシュセルとして、レベル“n”における“AED”、“EC'F'”、“EDF'”、及び“DF'B'”を有すると共に、ここで、“D”及び“E”は、それぞれ、エッジ“A-B”、及びエッジ“A-C”の中央である。
【０１１６】
「２／」
図１０ａ〜図１０ｄでは、破断線“L”は、レベル“n-1”における不連続ゾーンに属するメッシュセル“ABC”を横断すると共に、ノード“C”で終了する。
【０１１７】
このケースは、ノード“C”が共有された境界ノードになるという差異を有する一方、ケース“１／”と類似する。レベル“n-1”における右側の再メッシュ化に関して、（例えば、）ノード“C”及びノード“B”は、境界ノードであると共に、ノード“A'”が作成される。レベル“n-1”の新しいメッシュセル“A'BC”は、ドーターメッシュセルとして、レベル“n”のメッシュセル“A'E'D'”、“E'CF”、“D'FB”、及び“E'D'F”を有すると共に、レベル“n”における再メッシュ化の間に追加されたメッシュセル“A'E'D'”を含む。同様に、左側の倍増に関して、ノード“C”及びノード“A”は、境界ノードであると共に、ノード“B'”が作成される。レベル“n-1”の新しいメッシュセル“AB'C”は、ドーターメッシュセルとして、レベル“n”における“AED”、“ECF'”、“EF'D”、及び“DF'B'”を有する。
【０１１８】
「３／」
図１１ａ〜図１１ｄでは、破断線“L”は、レベル“n-1”のメッシュセル“ABC”を完全には横断しない。
【０１１９】
レベル“n”では、それは、メッシュセルに入って横断して、それによって図１０ａから図１０ｄの場合に戻るように、エッジ“E-F”の反対側のノード“C”のところまで、または、エッジに進入するのとは対照的に、エッジ（図１１ａにおける“E-F”）のところまでのいずれかにより、人工的に延長される。ノード“E”、及びノード“F”は、その場合に、レベル“n”における共有された境界ノードである。メッシュ“(n-1)”の、より高い階層レベルが考慮される場合、破断線“L”は、ノードまたはエッジまで延長される（より細かいレベル“n”に関してちょうど見られたものと同様の場合）。図１１ｄにおいて、形状は、ノード“C”まで延長された。右側の再メッシュ化に関して、ノード“C”及びノード“B”は境界ノードであると共に、ノード“A'”が作成される。レベル“n-1”のメッシュセル“A'BC”は、ドーターメッシュセルとして、レベル“n”における“A'ED'”、“ED'F”、“EFC”、及び“D'FB”を有する。メッシュセル“A'ED'”は、たとえ、もしそれがレベル“n”の再メッシュ化の間に生成されなかったとしても、レベル“n”と関係があるが、しかし、より高いレベルの“n-1”の場合は、再メッシュ化の間に生成されなければならない。左側の再メッシュ化に関して、境界ノードはノード“C”及びノード“A”であると共に、ノード“B'”が作成される。レベル“n-1”のメッシュセル“ACB'”は、ドーターメッシュセルとして、レベル“n”における“AED”、“ECF”、“EDF”、及び“DFB'”を有する。この場合、レベル“n”のメッシュセル“ECF”は、メッシュセル“A'BC”及びメッシュセル“ACB'”によって共有されるということが言及されている。
【０１２０】
破断線が完全にメッシュセルに含まれるとき、それは、より高いレベルにおいて消滅する。新しいメッシュセルの生成のために現在のレベルで導入される新しいノードは、より高いレベルの親メッシュセルにおけるそれらの重心座標によって定義される。これらのノードは、従って、より高いレベルのメッシュセルのノードによって影響を受けるグローバルな動きを有することになる。
【０１２１】
図１２ａから図１２ｃは、破断線が消失する場合を示す。レベル“n”において、破断線は、ノード“B”及びノード“C”のところまで延長され、それは従って共有された境界ノードになった。再メッシュ化は、右側に関してノード“E'”、及びノード“D'”を導入したと共に、上側（頂点側）に関してノード“F'”を導入した。レベル“n-1”において、形状はメッシュセル“ABC”に完全に含まれる。右側に関して、ノード“A'”は、メッシュセル“A'BC”を形成するために導入される。左側に関して、ノードは導入されず、再メッシュ化は、最初のメッシュセル“ABC”を導入する。メッシュセル“A'BC”は、最初のメッシュ“ABC”によって動くことを抑制され、その結果、レベル“n-1”における点“A”、及び点“A'”は、実質的に同じになる。レベル“n”において、“A'”が存在すると共に、レベル“n-1”の“ABC”におけるその重心座標によって定義される。
【０１２２】
再メッシュ化処理は、より低いメッシュの変形を考慮する連続する階層レベルのノードの間の重み付けを獲得するように、動き推定のために時折使用される幾何学的なマルチグリッドアプローチ（geometric multi-grid approach）と互換性がある。この場合、ノードの重み付けは、以下のとおりに実行され得る。
【０１２３】
（ｉ）もし細かいノードが粗いノードの直接的な子供である場合、重み付けは“1”である。
（ｉｉ）もし細かいノードがいくつかの粗いノードから生じる場合、重み付けは、粗いノードに対する細かいノードの重心の重みの平均に対応する。
【０１２４】
一度全ての階層レベルにおいて新しいメッシュが完全に完成されたならば、ステップ１５において、動きは、画像のグループに関して再度推定される。この再度の推定は、新しいメッシュのいくつかの三角形によって復元されることが可能である画素に関する予防措置と共に、例えば、上述の数式（１）から数式（６）を用いて、ステップ１０と同様に実行され得る。この曖昧性は、新しいメッシュの一部の三角形のメッシュセルがオーバーラップするという事実のせいで存在する。
【０１２５】
不連続ゾーンにおいてそれを解決するために、可視性のマスクが各時間“t”において定義される。以前に例証された例において、このマスクは、図７における斜線部分と対応する。それは、時刻“t”において不連続ゾーンの中にある点で構成される（すなわち、新しいメッシュにおいて再使用される最初のメッシュのメッシュセルに属さない）と共に、例えば、この時刻“t”において決定される配置された破断線“L”の右側に位置する。不連続ゾーンの中の点は、右側のサブメッシュの三角形か、または左側のサブメッシュの三角形のいずれかによって復元されることが可能である。もし点がマスクに属する場合、数式（３）から数式（５）のアプリケーションに関して、そのような点に対して利用される三角形“i,j,k”は、右側のサブメッシュの三角形であると共に、そうでない場合は、左側のサブメッシュの三角形である。
【０１２６】
同様に、サブメッシュのスピルオーバ（溢出効果）のせいで、不連続ゾーンの外側の特定の点に関して、曖昧性が存在する。それを解決するために、不連続ゾーンから溢れ出るサブメッシュが前景に位置するか、またあ背景に位置するかを判定するように、以前に示されたように、値“z”が使用される。従って、不連続ゾーンの外側にあると共に、サブメッシュの三角形に属する点に関して、我々は、この点を含むメッシュの各三角形に関する値“z”を計算すると共に、我々は、数式（３）から数式（５）のアプリケーションに関して最も大きな値“z”を与える三角形を選択する。
【０１２７】
ステップ１５における最小化アルゴリズムの収束を向上させるために、最初のメッシュの保存されたノードにおける変位ベクトルを最初の推定１０の間に獲得された値に初期化することによって、傾斜降下を開始することが可能である。
【０１２８】
動きの再推定１５の過程で、再メッシュ化ステップ１４において追加されたノードのうちの１つが、時刻“t”において、画像のいずれの点においても復元されないということが起こる可能性がある。この場合において、汎関数（１）の最小化は、そのようなノードに関するどのような変位ベクトルも提供できない。変位ベクトルは、その場合に、同一のサブメッシュの隣接しているノードに関して獲得された変位ベクトルの補間によって再生成される。
【０１２９】
最終的に、ステップ２０で提供された動きパラメータは、画像グループが少なくとも１つの不連続ゾーンを含む場合、以下を含む。
【０１３０】
（ａ）不連続ゾーンに属する最初のメッシュのメッシュセルの表示。
（ｂ）各不連続ゾーンに関する、グループの各画像における少なくとも１つの破断線の位置。
（ｃ）もし不連続ゾーンが２つ以上の破断線を含む場合、ゾーンにおいて生成された様々なサブメッシュと関連付けられた、オブジェクトの相対的な深さを示すための値“ｚ”の表示。
（ｄ）ステップ１５において計算された、メッシュのノードにおける変位ベクトル。
【０１３１】
上述のような動き推定は、ビデオ符号化アプリケーションにおいて、特に使用できる。本発明を実装する符号器の単純化した構成図が、図１３において提示される。そのような符号器は、ビデオストリームの一連のデジタル画像に関する動き推定を引き受ける（モジュール３６）と共に、他方ではビデオ符号化の分野で知られている様々な技術に従って実行されるテクスチャーの符号化を引き受ける（モジュール３７）。本発明に基づいた符号器において、モジュール３６は、図３を参照して説明される方法に従って動作する。それが提供する動きパラメータ（ａ）から動きパラメータ（ｄ）は、モジュール３９によって符号器のデジタル出力ストリームに挿入される前に、テクスチャーの符号化情報と共に、モジュール３８による符号化の対象物を形成する。
【０１３２】
この出力ストリームを伝送する信号は、通信チャンネル上で、送信され得るか、または放送され得る。それは、同様に、光ディスク、磁気テープ等のような記録媒体に対する記録の対象物を形成し得る。
【０１３３】
図１４を参照すると、そのような符号器に適合するビデオ復号器は、符号器の出力ストリームと類似した入力ストリームを受信すると共に、このストリームにおいて、動きパラメータ、及びテクスチャー情報を分離する（モジュール４０）。モジュール４１、及びモジュール４２は、符号化されたビデオシーケンスの画像の連続するグループにおける動き、及びテクスチャーを復号化するために、各々、この情報を処理する。復号化された動き、及び復号化されたテクスチャーは、ビデオ画像を復元するために、合成モジュール４３によって処理される。
【０１３４】
動きの復号化モジュール４１は、以下のとおりに動作する。画像のグループは、従来の復号器と同様に、最初に、シーケンスにおいて正確に指摘される。慣例により決定された最初のメッシュに基づいて、モジュール４１は、上述の情報（ａ）に基づいて、不連続ゾーンを配置する。その後で、グループの第１の画像における破断線の位置（ｂ）に従って、これらの不連続ゾーンにおいて破断線を配置する。モジュール４１は、その場合に、図３から図１２を参照して以前に説明されたステップ１４に従って不連続ゾーンの再メッシュ化を引き受けることによって、非多様体メッシュを再生成する。非多様体メッシュのノードに割り当てられた定量化された変位ベクトルは、符号化されたストリームにおいて示される。各時間“t”における画像の変位フィールドを確定するために、モジュール４１は、以前に説明されたステップ１５において符号器によって使用される処理と同じ処理に基づいて、（もしこの点が不連続ゾーンに位置する場合）破断線に対する点の位置（ｂ）に従って、及び深さを示す値“z”（ｃ）に従って、各点の変位ベクトルを合成することを提供する三角形のメッシュセルを識別する。
【０１３５】
図１３に基づいた符号器、または図１４に基づいた復号器は、詳細な電子回路の形で具体化され得る。しかしながら、それは、非常に多くの場合、ソフトウェアの一部分の形で具体化される。上で示された方法のステップは、その場合に、ビデオ符号器またはビデオ復号器のプロセッサにより実行されるプログラムの命令によって制御される。符号化に関して、この装置は、例えばコンピュータ、ビデオカメラ、テレビリレーのワークポスト（work post of a television relay）、記録装置等であり得る。復号化に関して、それは、例えばコンピュータ、記録媒体読み取り機、テレビジョン信号受信機、画像表示装置等であり得る。
【図面の簡単な説明】
【０１３６】
【図１】画像の階層メッシュ化を例証する図である。
【図２】メッシュセルの反転現象を例証する図である。
【図３】本発明に基づく動き推定方法のフローチャートである。
【図４】本発明の実施例に使用される再メッシュ化処理を例証する図である。
【図５】本発明の実施例に使用される再メッシュ化処理を例証する図である。
【図６】本発明の実施例に使用される再メッシュ化処理を例証する図である。
【図７】本発明の実施例に使用される再メッシュ化処理を例証する図である。
【図８】最も細かいレベルにおいて一度決定された階層メッシュのより高いレベルにおける不連続ゾーンの定義を例証する図である。
【図９ａ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図９ｂ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図９ｃ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図９ｄ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１０ａ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１０ｂ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１０ｃ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１０ｄ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１１ａ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１１ｂ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１１ｃ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１１ｄ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１２ａ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１２ｂ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１２ｃ】本発明の実施例における階層メッシュのより高いレベルにおけるメッシュの生成を例証する図である。
【図１３】本発明に基づいたビデオ符号器の単純化された構成図である。
【図１４】本発明に基づいたビデオ復号器の単純化された構成図である。
【符号の説明】
【０１３７】
３６：動きの推定モジュール
３７：テクスチャーの符号化モジュール
３８：動きパラメータの符号化モジュール
３９：出力ストリームの組み立てモジュール
４０：パラメータの分離モジュール
４１：動きの復号化モジュール
４２：テクスチャーの復号化モジュール
４３：ビデオ画像の合成モジュール
【特許請求の範囲】
【請求項１】
一連のデジタル動画像における動き推定の方法であって、
−ノードによって境界が定められるメッシュセルを含むと共に、シーケンスの参照画像に適用されるべき第１のメッシュを生成する段階と、
−画像の点が属する前記第１のメッシュの前記メッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、画像の各点に割り当てることによって、前記参照画像を包含する画像のグループにおける第１の変位フィールドを推定する段階と、
−前記第１の変位フィールドを分析することによって、各々が画像のグループにおけるメッシュセルの変形基準を満足する少なくとも１つの前記メッシュセルを含む、第１のメッシュにおける少なくとも１つの不連続ゾーンを検出する段階と、
−各検出された前記不連続ゾーンにおいて、画像のグループにおいて現れる少なくとも１つの破断線を判定する段階と、
−前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの検出された不連続ゾーンに関して、前記不連続ゾーンで判定される前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含む、前記参照画面に適用されるべき第２のメッシュを生成する段階と、
−検出された前記不連続ゾーンに位置する各点が属する前記第２のメッシュの選択されたメッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、検出された前記不連続ゾーンに位置する各点に割り当てることによって、画像のグループにおける第２の変位フィールドを推定する段階とを含み、
前記２つのサブメッシュの各々が、
前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、
前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含み、
前記選択されたメッシュセルが、前記不連続ゾーンで判定される前記破断線に対する前記点の位置によって決まる
ことを特徴とする方法。
【請求項２】
前記不連続ゾーンが、前記破断線によって、それぞれが２つのサブメッシュと関連する２つの部分に分離されると共に、
前記不連続ゾーンに位置すると共に複数のメッシュセルに属する点に関して、前記点が位置する前記不連続ゾーンの一部分と関連するサブメッシュのメッシュセルが選択される
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記第１のメッシュ、及び前記第２のメッシュが、階層的なメッシュであり、
前記変位フィールドの推定が、メッシュの最も粗い階層レベルから最も細かい階層レベルに対して達成されると共に、
前記不連続ゾーンが、メッシュセルの変形基準を満足する最も細かい階層レベルのメッシュセルの隣接のセットとして検出され、
前記不連続ゾーンが、前記メッシュセルの変形基準を満足する最も細かい階層レベルの少なくとも１つのそれぞれのメッシュを含む少なくとも１つのメッシュセルで構成されるように、より高い階層レベルで定義される
ことを特徴とする請求項１または請求項２のいずれか一項に記載の方法。
【請求項４】
前記第２のメッシュの２つのサブメッシュが、最も細かい階層レベル“nivFin”を発端に生成され、
より高いレベルのメッシュセルが、それ以降、階層の累進的な上流方向へのバックトラッキングの間に生成されると共に、
階層レベル“n”からすぐ上の階層レベル“n-1”へのバックトラッキングが、サブメッシュの各々に関して、及び“1＜n≦nivFin”に関して、
/a/レベル“n”で事前に定義される前記サブメッシュの各メッシュセルをレベル“n-1”で生成された前記サブメッシュの新しいメッシュセルに統合する段階と、
/b/“n'=n”を計算する段階と、
/c/もしレベル“n'-1”の前記新しいメッシュセルがレベル“n'”で既に生成された前記サブメッシュのメッシュセルによって完成され得ない場合、レベル“n'-1”の前記新しいメッシュセルを完成するために、レベル“n'”で前記サブメッシュの少なくとも１つの新しいメッシュセルを生成する段階と、
/d/もし“n'＜nivFin”である場合、“n'”を１ユニットだけ増やして前記“/c/”段階から繰り返す段階とを含む
ことを特徴とする請求項１から請求項３のいずれか一項に記載の方法。
【請求項５】
それぞれの深度値が、前記正常部分のノード、及び前記第２のメッシュの各サブメッシュの追加のノードに割り当てられ、
前記不連続ゾーンに関して生成されたサブメッシュの追加のノードに割り当てられる値が、前記不連続ゾーンで判定される前記破断線に対する前記サブメッシュの位置によって決まると共に、
前記第２のメッシュの正常部分のメッシュセル、及び前記サブメッシュの少なくとも１つのメッシュセルに属する画像の各点に関して、前記第２の変位フィールドを推定する段階が、
前記点を含む各メッシュセルに関して、前記メッシュセルの境界を定めるノードにそれぞれ割り当てられた前記深度値の加重和を計算する段階と、
前記点に対する前記変位値の割り当てに関して、計算された前記加重和が最大のメッシュセルを選択する段階とを含む
ことを特徴とする請求項１から請求項４のいずれか一項に記載の方法。
【請求項６】
一連のデジタル動画像における動き推定のための装置であって、
請求項１から請求項５のいずれか一項に記載の方法を実現するように適合された手段（３６）を備える
ことを特徴とする装置。
【請求項７】
動画を処理するための装置にインストールされるべきコンピュータプログラムであって、
前記装置の計算ユニットによってプログラムを実行した場合に請求項１から請求項５のいずれか一項に記載の動き推定の方法の段階を実現するための命令を含む
ことを特徴とするコンピュータプログラム。
【請求項８】
一連のデジタル動画像における動きを推定するための手段（３６）と、
前記動きを推定するための手段によって生成された動きパラメータを含む出力ストリームを組み立てるための手段（３８−３９）とを備え、
前記動きを推定するための手段が、請求項１から請求項５のいずれか一項に記載の方法に従って動作するように配置される
ことを特徴とするビデオ符号器。
【請求項９】
前記出力ストリームに含まれる動きパラメータが、
−検出された不連続ゾーンを構成する第１のメッシュのメッシュセルを示すパラメータと、
−各検出された不連続ゾーンにおいて判定された破断線の位置パラメータと、
−第２のメッシュのノードに割り当てられた変位値を記述するパラメータとを含み、
前記変位値が、第２の変位フィールドの推定において獲得される
ことを特徴とする請求項８に記載のビデオ符号器。
【請求項１０】
前記出力ストリームに含まれる動きパラメータが、前記正常部分のノード、及び前記動きを推定するための手段によって生成される第２のメッシュの各サブメッシュの追加のノードにそれぞれ割り当てられた深度値を示すパラメータを更に含む
ことを特徴とする請求項９に記載のビデオ符号器。
【請求項１１】
動きパラメータの表現を含む一連のデジタル動画像を代表する信号であって、参照画像を包含する画像のグループに関して、
−前記参照画像に適用されるべき第１のメッシュにおいて、画像のグループにおける少なくとも１つの不連続ゾーンを構成するメッシュセルを示す第１の動きパラメータと、
−各不連続ゾーンにおいて少なくとも１つの破断線を位置決めするための第２の動きパラメータと、
−前記参照画像に適用されるべき第２のメッシュのノードに割り当てられた変位値を示す第３の動きパラメータとを含み、
前記第２のメッシュが、前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの不連続ゾーンに関して、前記不連続ゾーンに位置する前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含み、
前記２つのサブメッシュの各々が、
前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、
前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含む
ことを特徴とする信号。
【請求項１２】
前記動きパラメータは、前記正常部分のノード、及び前記第２のメッシュの各サブメッシュの追加のノードにそれぞれ割り当てられた深度値を示すパラメータを更に含む
ことを特徴とする請求項１１に記載の信号。
【請求項１３】
請求項１１または請求項１２のいずれか一項に記載の信号が記録された記録媒体。
【請求項１４】
ノードによって境界が定められるメッシュセルを含む画像のメッシュを用いた、一連のデジタル動画像における動きの復号化の方法であって、
前記方法が、
−参照画像を包含する画像のグループに関して、
・前記参照画像に適用されるべき第１のメッシュにおいて、画像のグループにおける少なくとも１つの不連続ゾーンを構成するメッシュセルを示す第１の動きパラメータと、
・各前記不連続ゾーンにおいて少なくとも１つの破断線を位置決めするための第２の動きパラメータと、
・前記参照画像に適用されるべき第２のメッシュのノードに割り当てられた変位値を示す第３の動きパラメータと
を含む動きパラメータを含む入力ストリームを受信する段階と、
−前記第１の動きパラメータ及び前記第２の動きパラメータに基づいて前記第２のメッシュを生成する段階と、
−前記第３の動きパラメータに基づいて獲得された変位値を、前記第２のメッシュの各ノードに割り当てることによって、そして検出された前記不連続ゾーンに位置する各点が属する前記第２のメッシュの選択されたメッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、検出された前記不連続ゾーンに位置する各点に割り当てることによって、画像のグループにおける変位フィールドを生成する段階とを含み、
前記第２のメッシュが、前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの不連続ゾーンに関して、前記不連続ゾーンに位置する前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含み、
前記２つのサブメッシュの各々が、
前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、
前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含み、
前記選択されたメッシュセルが、前記不連続ゾーンで判定される前記破断線に対する前記点の位置によって決まる
ことを特徴とする方法。
【請求項１５】
前記不連続ゾーンが、前記破断線によって、各々２つのサブメッシュと関連する２つの部分に分離されると共に、
前記不連続ゾーンに位置すると共に複数のメッシュセルに属する点に関して、前記点が位置する前記不連続ゾーンの一部分と関連するサブメッシュのメッシュセルが選択される
ことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記入力ストリームの動きパラメータが、前記正常部分のノード、及び前記第２のメッシュの各サブメッシュの追加のノードにそれぞれ割り当てられた深度値を更に含み、
前記不連続ゾーンに対応するサブメッシュの追加のノードに割り当てられる値が、前記不連続ゾーンに位置する前記破断線に対する前記サブメッシュの位置によって決まると共に、
前記第２のメッシュの正常部分のメッシュセル、及び前記サブメッシュの少なくとも１つのメッシュセルに属する画像の各点に関して、前記変位フィールドを生成する段階が、
前記点を含む各メッシュセルに関して、前記メッシュセルの境界を定めるノードにそれぞれ割り当てられた前記深度値の加重和を計算する段階と、
前記点に対する前記変位値の割り当てに関して、計算された前記加重和が最大のメッシュセルを選択する段階とを含む
ことを特徴とする請求項１４または請求項１５のいずれか一項に記載の方法。
【請求項１７】
一連のデジタル動画像における動きの復号化のための装置であって、
請求項１４から請求項１６のいずれか一項に記載の方法を実現するように適合された手段（４１）を備える
ことを特徴とする装置。
【請求項１８】
動画を処理するための装置にインストールされるべきコンピュータプログラムであって、
前記装置の計算ユニットによってプログラムを実行した場合に請求項１４から請求項１６のいずれか一項に記載の動きの復号化の方法の段階を実現するための命令を含む
ことを特徴とするコンピュータプログラム。
【請求項１９】
動きを復号化する手段（４１）と、
前記動きを復号化する手段によって生成された変位フィールドを考慮して、一連のデジタル動画像を組み立てるための合成手段（４３）とを備え、
前記動きを復号化する手段が、請求項１４から請求項１６のいずれか一項に記載の方法に従って動作するように配置される
ことを特徴とするビデオ復号器。
【請求項１】
一連のデジタル動画像における動き推定の方法であって、
−ノードによって境界が定められるメッシュセルを含むと共に、シーケンスの参照画像に適用されるべき第１のメッシュを生成する段階と、
−画像の点が属する前記第１のメッシュの前記メッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、画像の各点に割り当てることによって、前記参照画像を包含する画像のグループにおける第１の変位フィールドを推定する段階と、
−前記第１の変位フィールドを分析することによって、各々が画像のグループにおけるメッシュセルの変形基準を満足する少なくとも１つの前記メッシュセルを含む、第１のメッシュにおける少なくとも１つの不連続ゾーンを検出する段階と、
−各検出された前記不連続ゾーンにおいて、画像のグループにおいて現れる少なくとも１つの破断線を判定する段階と、
−前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの検出された不連続ゾーンに関して、前記不連続ゾーンで判定される前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含む、前記参照画面に適用されるべき第２のメッシュを生成する段階と、
−検出された前記不連続ゾーンに位置する各点が属する前記第２のメッシュの選択されたメッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、検出された前記不連続ゾーンに位置する各点に割り当てることによって、画像のグループにおける第２の変位フィールドを推定する段階とを含み、
前記２つのサブメッシュの各々が、
前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、
前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含み、
前記選択されたメッシュセルが、前記不連続ゾーンで判定される前記破断線に対する前記点の位置によって決まる
ことを特徴とする方法。
【請求項２】
前記不連続ゾーンが、前記破断線によって、それぞれが２つのサブメッシュと関連する２つの部分に分離されると共に、
前記不連続ゾーンに位置すると共に複数のメッシュセルに属する点に関して、前記点が位置する前記不連続ゾーンの一部分と関連するサブメッシュのメッシュセルが選択される
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記第１のメッシュ、及び前記第２のメッシュが、階層的なメッシュであり、
前記変位フィールドの推定が、メッシュの最も粗い階層レベルから最も細かい階層レベルに対して達成されると共に、
前記不連続ゾーンが、メッシュセルの変形基準を満足する最も細かい階層レベルのメッシュセルの隣接のセットとして検出され、
前記不連続ゾーンが、前記メッシュセルの変形基準を満足する最も細かい階層レベルの少なくとも１つのそれぞれのメッシュを含む少なくとも１つのメッシュセルで構成されるように、より高い階層レベルで定義される
ことを特徴とする請求項１または請求項２のいずれか一項に記載の方法。
【請求項４】
前記第２のメッシュの２つのサブメッシュが、最も細かい階層レベル“nivFin”を発端に生成され、
より高いレベルのメッシュセルが、それ以降、階層の累進的な上流方向へのバックトラッキングの間に生成されると共に、
階層レベル“n”からすぐ上の階層レベル“n-1”へのバックトラッキングが、サブメッシュの各々に関して、及び“1＜n≦nivFin”に関して、
/a/レベル“n”で事前に定義される前記サブメッシュの各メッシュセルをレベル“n-1”で生成された前記サブメッシュの新しいメッシュセルに統合する段階と、
/b/“n'=n”を計算する段階と、
/c/もしレベル“n'-1”の前記新しいメッシュセルがレベル“n'”で既に生成された前記サブメッシュのメッシュセルによって完成され得ない場合、レベル“n'-1”の前記新しいメッシュセルを完成するために、レベル“n'”で前記サブメッシュの少なくとも１つの新しいメッシュセルを生成する段階と、
/d/もし“n'＜nivFin”である場合、“n'”を１ユニットだけ増やして前記“/c/”段階から繰り返す段階とを含む
ことを特徴とする請求項１から請求項３のいずれか一項に記載の方法。
【請求項５】
それぞれの深度値が、前記正常部分のノード、及び前記第２のメッシュの各サブメッシュの追加のノードに割り当てられ、
前記不連続ゾーンに関して生成されたサブメッシュの追加のノードに割り当てられる値が、前記不連続ゾーンで判定される前記破断線に対する前記サブメッシュの位置によって決まると共に、
前記第２のメッシュの正常部分のメッシュセル、及び前記サブメッシュの少なくとも１つのメッシュセルに属する画像の各点に関して、前記第２の変位フィールドを推定する段階が、
前記点を含む各メッシュセルに関して、前記メッシュセルの境界を定めるノードにそれぞれ割り当てられた前記深度値の加重和を計算する段階と、
前記点に対する前記変位値の割り当てに関して、計算された前記加重和が最大のメッシュセルを選択する段階とを含む
ことを特徴とする請求項１から請求項４のいずれか一項に記載の方法。
【請求項６】
一連のデジタル動画像における動き推定のための装置であって、
請求項１から請求項５のいずれか一項に記載の方法を実現するように適合された手段（３６）を備える
ことを特徴とする装置。
【請求項７】
動画を処理するための装置にインストールされるべきコンピュータプログラムであって、
前記装置の計算ユニットによってプログラムを実行した場合に請求項１から請求項５のいずれか一項に記載の動き推定の方法の段階を実現するための命令を含む
ことを特徴とするコンピュータプログラム。
【請求項８】
一連のデジタル動画像における動きを推定するための手段（３６）と、
前記動きを推定するための手段によって生成された動きパラメータを含む出力ストリームを組み立てるための手段（３８−３９）とを備え、
前記動きを推定するための手段が、請求項１から請求項５のいずれか一項に記載の方法に従って動作するように配置される
ことを特徴とするビデオ符号器。
【請求項９】
前記出力ストリームに含まれる動きパラメータが、
−検出された不連続ゾーンを構成する第１のメッシュのメッシュセルを示すパラメータと、
−各検出された不連続ゾーンにおいて判定された破断線の位置パラメータと、
−第２のメッシュのノードに割り当てられた変位値を記述するパラメータとを含み、
前記変位値が、第２の変位フィールドの推定において獲得される
ことを特徴とする請求項８に記載のビデオ符号器。
【請求項１０】
前記出力ストリームに含まれる動きパラメータが、前記正常部分のノード、及び前記動きを推定するための手段によって生成される第２のメッシュの各サブメッシュの追加のノードにそれぞれ割り当てられた深度値を示すパラメータを更に含む
ことを特徴とする請求項９に記載のビデオ符号器。
【請求項１１】
動きパラメータの表現を含む一連のデジタル動画像を代表する信号であって、参照画像を包含する画像のグループに関して、
−前記参照画像に適用されるべき第１のメッシュにおいて、画像のグループにおける少なくとも１つの不連続ゾーンを構成するメッシュセルを示す第１の動きパラメータと、
−各不連続ゾーンにおいて少なくとも１つの破断線を位置決めするための第２の動きパラメータと、
−前記参照画像に適用されるべき第２のメッシュのノードに割り当てられた変位値を示す第３の動きパラメータとを含み、
前記第２のメッシュが、前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの不連続ゾーンに関して、前記不連続ゾーンに位置する前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含み、
前記２つのサブメッシュの各々が、
前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、
前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含む
ことを特徴とする信号。
【請求項１２】
前記動きパラメータは、前記正常部分のノード、及び前記第２のメッシュの各サブメッシュの追加のノードにそれぞれ割り当てられた深度値を示すパラメータを更に含む
ことを特徴とする請求項１１に記載の信号。
【請求項１３】
請求項１１または請求項１２のいずれか一項に記載の信号が記録された記録媒体。
【請求項１４】
ノードによって境界が定められるメッシュセルを含む画像のメッシュを用いた、一連のデジタル動画像における動きの復号化の方法であって、
前記方法が、
−参照画像を包含する画像のグループに関して、
・前記参照画像に適用されるべき第１のメッシュにおいて、画像のグループにおける少なくとも１つの不連続ゾーンを構成するメッシュセルを示す第１の動きパラメータと、
・各前記不連続ゾーンにおいて少なくとも１つの破断線を位置決めするための第２の動きパラメータと、
・前記参照画像に適用されるべき第２のメッシュのノードに割り当てられた変位値を示す第３の動きパラメータと
を含む動きパラメータを含む入力ストリームを受信する段階と、
−前記第１の動きパラメータ及び前記第２の動きパラメータに基づいて前記第２のメッシュを生成する段階と、
−前記第３の動きパラメータに基づいて獲得された変位値を、前記第２のメッシュの各ノードに割り当てることによって、そして検出された前記不連続ゾーンに位置する各点が属する前記第２のメッシュの選択されたメッシュセルの境界を定めるノードに割り当てられた値に従って計算された変位値を、検出された前記不連続ゾーンに位置する各点に割り当てることによって、画像のグループにおける変位フィールドを生成する段階とを含み、
前記第２のメッシュが、前記不連続ゾーンに属さない第１のメッシュのメッシュセルで構成された正常部分、及び少なくとも１つの不連続ゾーンに関して、前記不連続ゾーンに位置する前記破断線を含む領域においてオーバーラップする少なくとも２つのサブメッシュを含み、
前記２つのサブメッシュの各々が、
前記正常部分に共有されるノード、及び前記正常部分に属さない追加のノードを含むノードによって境界を定められると共に、前記不連続ゾーンの境界に位置するそれぞれのメッシュセルと、
前記正常部分に共有される前記２つのサブメッシュのそれぞれのノードの間に位置している破断線とを含み、
前記選択されたメッシュセルが、前記不連続ゾーンで判定される前記破断線に対する前記点の位置によって決まる
ことを特徴とする方法。
【請求項１５】
前記不連続ゾーンが、前記破断線によって、各々２つのサブメッシュと関連する２つの部分に分離されると共に、
前記不連続ゾーンに位置すると共に複数のメッシュセルに属する点に関して、前記点が位置する前記不連続ゾーンの一部分と関連するサブメッシュのメッシュセルが選択される
ことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記入力ストリームの動きパラメータが、前記正常部分のノード、及び前記第２のメッシュの各サブメッシュの追加のノードにそれぞれ割り当てられた深度値を更に含み、
前記不連続ゾーンに対応するサブメッシュの追加のノードに割り当てられる値が、前記不連続ゾーンに位置する前記破断線に対する前記サブメッシュの位置によって決まると共に、
前記第２のメッシュの正常部分のメッシュセル、及び前記サブメッシュの少なくとも１つのメッシュセルに属する画像の各点に関して、前記変位フィールドを生成する段階が、
前記点を含む各メッシュセルに関して、前記メッシュセルの境界を定めるノードにそれぞれ割り当てられた前記深度値の加重和を計算する段階と、
前記点に対する前記変位値の割り当てに関して、計算された前記加重和が最大のメッシュセルを選択する段階とを含む
ことを特徴とする請求項１４または請求項１５のいずれか一項に記載の方法。
【請求項１７】
一連のデジタル動画像における動きの復号化のための装置であって、
請求項１４から請求項１６のいずれか一項に記載の方法を実現するように適合された手段（４１）を備える
ことを特徴とする装置。
【請求項１８】
動画を処理するための装置にインストールされるべきコンピュータプログラムであって、
前記装置の計算ユニットによってプログラムを実行した場合に請求項１４から請求項１６のいずれか一項に記載の動きの復号化の方法の段階を実現するための命令を含む
ことを特徴とするコンピュータプログラム。
【請求項１９】
動きを復号化する手段（４１）と、
前記動きを復号化する手段によって生成された変位フィールドを考慮して、一連のデジタル動画像を組み立てるための合成手段（４３）とを備え、
前記動きを復号化する手段が、請求項１４から請求項１６のいずれか一項に記載の方法に従って動作するように配置される
ことを特徴とするビデオ復号器。
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９ａ】
【図９ｂ】
【図９ｃ】
【図９ｄ】
【図１０ａ】
【図１０ｂ】
【図１０ｃ】
【図１０ｄ】
【図１１ａ】
【図１１ｂ】
【図１１ｃ】
【図１１ｄ】
【図１２ａ】
【図１２ｂ】
【図１２ｃ】
【図１３】
【図１４】
【図１】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９ａ】
【図９ｂ】
【図９ｃ】
【図９ｄ】
【図１０ａ】
【図１０ｂ】
【図１０ｃ】
【図１０ｄ】
【図１１ａ】
【図１１ｂ】
【図１１ｃ】
【図１１ｄ】
【図１２ａ】
【図１２ｂ】
【図１２ｃ】
【図１３】
【図１４】
【図１】
【公表番号】特表２００８−５１４０７３（Ｐ２００８−５１４０７３Ａ）
【公表日】平成２０年５月１日（２００８．５．１）
【国際特許分類】
【出願番号】特願２００７−５３１７９０（Ｐ２００７−５３１７９０）
【出願日】平成１７年９月６日（２００５．９．６）
【国際出願番号】ＰＣＴ／ＦＲ２００５／００２２１６
【国際公開番号】ＷＯ２００６／０３０１０３
【国際公開日】平成１８年３月２３日（２００６．３．２３）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
【公表日】平成２０年５月１日（２００８．５．１）
【国際特許分類】
【出願日】平成１７年９月６日（２００５．９．６）
【国際出願番号】ＰＣＴ／ＦＲ２００５／００２２１６
【国際公開番号】ＷＯ２００６／０３０１０３
【国際公開日】平成１８年３月２３日（２００６．３．２３）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
[ Back to top ]