【誤訳訂正書】
【提出日】平成21年9月10日(2009.9.10)
【誤訳訂正１】
【訂正対象書類名】明細書
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【書類名】        明細書
【発明の名称】    ２つの画像間の動きの推定方法
【特許請求の範囲】
【請求項１】  輝度Ｙ1およびＹ2をそれぞれ有する２つのデジタル画像Ｉ1およびＩ2間の動きを推定して、デジタル画像Ｉ2の座標ｘ，ｙの各点に対して動きベクトル：
【式１】
2002524807.tif 000001
を生成し、デジタル画像Ｉ1から、デジタル画像Ｉ2の近似値である、輝度：
【式２】
2002524807.tif 000002
の画像
【外１】
2002524807.tif 000003
を形成する方法において：
（ａ）ノードがデジタル画像Ｉ2の点であるメッシュと、前記メッシュの各ノードにおける動きベクトルと、デジタル画像Ｉ2が属するメッシュのノードの動きベクトルの値からデジタル画像Ｉ2の各点の動きベクトル値を計算する補間式とからなる有限要素の初期モデルを規定し、
（ｂ）微分法に従って、前記有限要素の初期モデルの前記動きベクトルの値を最適化し、
（ｃ）デジタル画像Ｉ2と画像
【外２】
2002524807.tif 000004
との間の、各有限要素またはメッシュごとの差Ｅを計算し、
（ｄ）差Ｅに関する判定基準に従って決められた有限要素の集合の一部分をより細かいメッシュに細分化し、新しいメッシュノードそれぞれに動きベクトルを割当て、
（ｅ）停止判定基準が満たされるまで、前ステップ（ｄ）の最後に得られる有限要素のモデルにステップ（ｂ）、（ｃ）および（ｄ）を繰り返す
ステップを含むことを特徴とする方法。
【請求項２】  ステップ（ｄ）の全有限要素の一部分をより細かいメッシュに細分化するため、前記有限要素の集合を差Ｅの降順に分類し、且つこの分類の最初のＸ個の三角形をより小さい三角形に細分し、ここで、Ｘが一連の有限要素の数の予め決められた一部分を表すことを特徴とする請求項１に記載の方法。
【請求項３】  ステップ（ｄ）の全有限要素の一部分をより細かいメッシュに細分化するため、ステップ（ｃ）で計算された差Ｅの集合とその有限要素の大きさに関係する閾値差とを比較し、差Ｅが閾値差より大きい有限要素をより小さい有限要素に細分化することを特徴とする請求項１に記載の方法。
【請求項４】  停止判定基準が、ステップ（ｄ）の最後に達すべき有限要素のモデルを構成する所定の数の有限要素であることを特徴とする請求項１〜３のいずれか１項に記載の方法。
【請求項５】  ステップ（ｄ）の最後に得られるモデルの有限要素の集合の差Ｅが該有限要素の大きさに関係する汎関数の閾値差より小さい時、ステップ（ｅ）の停止判定基準が満たされることを特徴とする請求項１〜３のいずれか１項に記載の方法。
【請求項６】  デジタル画像Ｉ1とＩ2に加えて、解像度レベルがｒで輝度がＹirであるＲ個の画像の集合Ｉirを規定し、ｒは順に（Ｒ−１,Ｒッ２，．．．０）の値を、ｉは（１，２）の値をとり、解像度レベルｒ＝Ｒ−１からレベルｒ＝０までの各解像度レベルにおいて、ステップ(ｂ)〜（ｅ）を実施することを特徴とする請求項１〜５のいずれか１項に記載の方法。
【請求項７】  デジタル画像Ｉ1とＩ2に加えて、解像度レベルがｒのＲ個の画像の集合が、パルスレスポンスフィルタがｈnrのローパスフィルタを用いて、デジタル画像Ｉ1およびＩ2を２方向ｘおよびｙに沿ってフィルタリングして得られ、画像Ｉirが以下の式によって規定されることを特徴とする請求項６に記載の方法：
【式３】
2002524807.tif 000005
（ここでＭは自然数である）。
【請求項８】  パルスレスポンスｈnrが以下のように規定されることを特徴とする請求項７に記載の方法：
【式４】
2002524807.tif 000006
（Ｂが自然数である）。
【請求項９】  初めの動きベクトルがゼロベクトルであることを特徴とする請求項１〜８のいずれか１項に記載の方法。
【請求項１０】  各有限要素ｅに対する画像
【外３】
2002524807.tif 000007
とデジタル画像Ｉ2間の差Ｅが以下の式で規定されることを特徴とする請求項１〜９のいずれか１項に記載の方法：
【式５】
2002524807.tif 000008
【請求項１１】  頂点がＰi、ＰjおよびＰkであり、その各座標が（ｘi，ｙi）、（ｘj，ｙj）および（ｘk，ｙk）である有限要素ｅに属するデジタル画像Ｉ2にある座標（ｘ，ｙ）の点Ｐの動きベクトル値を計算する補間式が以下であり：
【式６】
2002524807.tif 000009
ここで、リIが以下の形の関数であることを特徴とする請求項１〜１０のいずれか１項に記載の方法。
【式７】
2002524807.tif 000010
【請求項１２】  動きベクトルを最適化する微分方法が、ガウス−ニュートン法であることを特徴とする請求項１〜１１のいずれか１項に記載の方法。
【請求項１３】  動きベクトルを最適化する微分方法が、ガウス−ニュートン法のマルカルト拡張であることを特徴とする請求項１〜１１のいずれか１項に記載の方法。
【請求項１４】  各有限要素がゼロにならないようにする密度の条件が、有限要素のモデルの動きベクトルを最適化する時に各有限要素に課せられることを特徴とする請求項１〜１３のいずれか１項に記載の方法。
【請求項１５】  頂点がＰi、Ｐj、Ｐkで、密度がＣ（Ｐi、Ｐj、Ｐk）である有限要素ｅ上の密度の条件が下記式で規定されることを特徴とする請求項１４に記載の方法：
【式８】
2002524807.tif 000011
（ここで、
【外４】
2002524807.tif 000012
が最適化ステップ中の頂点Ｐi、Ｐj、Ｐkの動きベクトルを表し、Ｋが許可された密度差を固定するパラメターである）
【請求項１６】  有限要素への条件下における最適化が、増加ラグランジュ法で解かれることを特徴とする請求項１４または１５に記載の方法。
【請求項１７】  増加ラグランジュ法で、条件が線形の形で用いられることを特徴とする請求項１６に記載の方法。
【請求項１８】  動きベクトルを最適化する方法でＬＤＬtプロフィール法が用いられることを特徴とする請求項１２、１３または１７のいずれか１項に記載の方法。
【請求項１９】  動き推定方法のステップｄ）で実施されるメッシュの一部分の細分化が、部分的四次ツリーと組み合わされる、ツリーの各レベルがメッシュレベルを表し、ツリーの各ノードが所定レベルの三角形を表し、生成されるものが前記ツリーを示す２進列であることを特徴とする、請求項１〜１８のいずれか１項に記載の２つのデジタル画像間の動きを推定する方法を使用して画像をコード化する方法。
【請求項２０】  前記ツリーの各ノードに関する動きベクトルが、もとのノードが存在する場合、もとのノードの動きベクトルに関して微分法でコード化され、前記ツリーの幅パッセージに沿って前記２進列に配列されることを特徴とする、２つのデジタル画像間の動きを推定する方法を使用して画像をコード化する請求項１９に記載の方法。
【請求項２０】  動き推定方法のステップｄ）で実施されるメッシュの一部分の細分化が、部分的四次ツリーと組み合わされる、ツリーの各レベルがメッシュレベルを表し、ツリーの各ノードが所定レベルの三角形を表し、前記ツリーが前記ツリーを示すコード化されたデータの２進列から生成されることを特徴とする、請求項１〜１８のいずれか１項に記載の２つのデジタル画像間の動きを推定する方法を使用して画像をコード化する方法。
【請求項２２】  所定レベルのツリーに関するコード化されたデータを２進列で集合的に再グループ化して、列が読取られるとレベル単位でツリーを生成することを特徴とする、２つのデジタル画像間の動きを推定する方法を使用して画像をコード化する請求項２１に記載の方法。
の動きを推定する方法
【請求項２３】
−画像のシーケンスの圧縮、および
−２つより大きい空間におけるデータの圧縮
の内の少なくとも一方のために、請求項１〜２２のいずれか１項に記載の方法を使用する圧縮方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２つのデジタル画像間の動きを推定する方法に関する。
２つの連続するデジタル画像Ｉ1およびＩ2間の動きは、一般にデジタル画像Ｉ1およびＩ2のいずれかに関連する動きフィールドの形で示され、それぞれが対象となるデジタル画像の１点に関連する、動きベクトルによって構成される。動きベクトルは、撮影される場面の同じ物理的点に関して、デジタル画像Ｉ1のピクセルと関連するデジタル画像Ｉ2のピクセルとの位置の違いを表す２次元ベクトルである。
【０００２】
【従来の技術】
動きの評価は、２つの画像の動きまたは不一致を知る必要のある画像処理の分野において有用である。例として、下記範囲の用途を挙げることができる：
−画像の圧縮：評価方法は１つの画像をコード化するデータの量を限定するのに使用される。画像は互いに関連するものとする；
−２次元以上の空間におけるデータの圧縮；
−ビデオコーディング：既にコード化された画像から規定される動きフィールドを用いて次の画像を予測する；
−医学用画像：２つの画像間の動きを推定する方法を用いて、例えば心臓の動きの分析をする；
−遠隔モニタリング：この方法を用いて道路交通を監視できる；
−多方向の画像（multi-view images）からの三次元再構築：この方法を用いて各図の間の不一致を推定する。
【０００３】
この動きフィールドを得るために、画像を分解して有限要素にする方法が知られている。この有限要素は例えば三角形または四角形でよく、ノードが有限要素の頂点に対応するメッシュによって決められる。動きベクトルはメッシュの各ノードについて計算する。補間関数のバイアスを介して、これから対象画像の各点に対する動きベクトルを演繹することができる。こうして動きフィールドは、画像を有限要素に分割するのに用いられるメッシュを規定する有限要素のモデル、および画像のあらゆる点における動きベクトルの計算を可能にする補間関数によって決定される。
【０００４】
使用されるメッシュは、規則的でも不規則的でもよく、２つの画像間の動きをできるだけ最適にモデル化するのに十分な密度にし、ただし計算量または伝送データ量を過剰に必要としないように選択しなければならない。この選択は、方法の開始時にのみ一度実施され、このメッシュは一般に推定の間、等しいままである。
【０００５】
メッシュのノードの動きベクトルは各種の方法で計算できる。まず、メッシュの各ノードに対して動きベクトルの可能な値の離散集合をテストし、所定の判定基準に従って最適なベクトルを保持するという、対応またはマッチング法が挙げられる。変換方法として知られている第２の方法は、フーリエ変換とその拡張の特性を用いて、動きを変換空間の位相飛び越しに変換するものである。最後に微分法として知られる第３の方法があり、この方法では、数学的判定基準（例えば画像と動きフィールドに関する前の値との間の二次誤差）を最適化して動きベクトルを決定する。この方法は、有限要素によるモデル化を用いた動きの推定に、最も頻繁に用いられる。動きベクトルを最適化する一般的な微分方法は、ガウス−ニュートン法である。本出願は、特に有限要素のモデルおよび動きフィールドを決める微分法を用いた一連の動き推定法に関する。
【０００６】
【発明が解決しようとする課題】
この種の方法は広く用いられているが、複数の欠点を有する。この方法の開始時に選択されるメッシュは、画像のある領域ではより高密度なメッシュを必要とし、他の領域ではより目の粗いメッシュを必要とするため、画像の意味的内容に対して不適当であることが分かっている。さらに、メッシュのノードの、動きベクトルフィールドの影響下において、例えばＩ2である開始画像上の初期メッシュは、例えばＩ1である他の画像上の新しいメッシュに変換される。そこで、新しいメッシュの準位において、下記のような異常事態が起こる：
【０００７】
−有限要素の反転：有限要素が反転し、且つ他を覆って、任意のメッシュが検証しなければならない画像の範囲の分割特性を損なう、
−画像Ｉ1の範囲の外に動きベクトルを適用した後の、移動したメッシュの周辺ノードのオーバーフロー：画像Ｉ2のあるピクセルは画像Ｉ1の範囲外に配置される画像Ｉ1のピクセルと組み合わせることができる。このことは厳密には問題ではないが、移動したメッシュの周辺ノードを画像Ｉ1の範囲内に維持するようにするのが有利である。
【０００８】
【課題を解決するための手段】
本発明の一目的は、推定の間にメッシュを最適化し、方法の最後に画像の意味的内容に適合したメッシュを得るという、動き推定法に関する。このために、有限要素を動きの推定の間に細分化する。
本発明の他の目的は、ガウス・ニュートン法の効果を改良し、メッシュのノードの動きベクトルを最適化することにある。このため、この最適化は複数の解像度レベルの画像で実施される。
最後に、本発明の他の目的は、動きを推定して前記異常事態を防ぐ方法を提供することにある。このために、本発明は動きベクトルの最適化ステップの間に、異常事態を避けるための条件を加える。
【０００９】
さらに、本発明は輝度Ｙ1およびＹ2を有する２つのデジタル画像Ｉ1およびＩ2間の動きを推定し、画像Ｉ2の座標ｘ，ｙの各点に対して動きベクトル：
【式９】
2002524807.tif 000013
を生成し、画像Ｉ1から、画像Ｉ2の近似値である、輝度：
【００１０】
【式１０】
2002524807.tif 000014
の画像
【００１１】
【外５】
2002524807.tif 000015
を構成する方法に関し、この方法は下記ステップ（ａ）〜（ｅ）を含むことを特徴とする：
【００１２】
（ａ）ノードが画像Ｉ2の点であるメッシュを備える有限要素の初期モデルと、前記メッシュの各ノードにおける動きベクトルと、画像Ｉ2が属するメッシュのノードの動きベクトルの値から画像Ｉ2の各点の動きベクトル値を計算する補間式とを規定し、
（ｂ）微分法に従って、モデルの動きベクトルの値を最適化し、
（ｃ）画像Ｉ2と画像
【００１３】
【外６】
2002524807.tif 000016
【００１４】
との間の、各有限要素またはメッシュに対する差Ｅを計算し、
（ｄ）差Ｅに関する判定基準に従って決められた有限要素の集合の一部分に対してより細かいメッシュを実施し、新しいメッシュノードそれぞれに動きベクトルを割当て、
（ｅ）停止判定基準が満たされるまで、前ステップ（ｄ）の最後に得られる有限要素のモデルにステップ（ｂ）、（ｃ）および（ｄ）を繰り返す。
【００１５】
【発明の実施の形態】
改良された実施例では、各デジタル画像Ｉ1とＩ2に対してさらにＲ個の画像の集合Ｉjrが解像度レベルｒおよび輝度Ｙirで規定され、ｒは値（０,...,Ｒ−１）をとり、ｉは値１および２をとり、画像Ｉ10およびＩ20はデジタル画像Ｉ1とＩ2に対応し、ステップ（ｂ）〜（ｅ）がレベルｒ＝Ｒ−１からレベルｒ＝０まで、解像度の各レベルｒに対して実施される。
最後に、好ましい実施例では、動きベクトルの最適化時に有限要素の動きに条件を加え、有限要素が反転しないようにする。別の実施例では、条件を導入して、画像Ｉ1の範囲の外に動きベクトルを適用した後に得られるメッシュがフローオーバーしないようにすることも可能である。
本発明の他の特性および利点は、下記添付図面を参照して下記の詳細な説明を読めば明らかになるであろう。
【００１６】
【実施例】
まず輝度がそれぞれＹ1およびＹ2である２つのデジタル画像Ｉ1およびＩ2を参照する。本発明の方法は、画像Ｉ2の座標（ｘ，ｙ）の各点Ｐに対して動きベクトル：
【式１１】
2002524807.tif 000017
を生成することで構成される。このベクトルは画像Ｉ1から画像Ｉ2の近似値である輝度：
【式１２】
2002524807.tif 000018
の画像
【外７】
2002524807.tif 000019
を構成することのできるベクトルであると規定される。こうして動きは画像Ｉ1から画像Ｉ2へ規定される。
【００１７】
求められる動きフィールドは、有限要素のモデルによって規定される。説明の最後に、有限要素は三角形であるものとみなし、この形の有限要素には、本発明の範囲の制限が全く無いものとする。この結果、有限要素のモデルは三角形のメッシュと、メッシュノードで規定される動きベクトルと、三角形内の点の動きベクトルを計算する補間式とを備える。
【００１８】
画像Ｉ2の範囲の任意の点における動きフィールドを計算するのに用いられる補間式は下記の通りである：
座標（ｘ，ｙ）の点Ｐが、頂点がＰi、ＰjおよびＰkであり、その各座標が（ｘi，ｙi）、（ｘj，ｙj）および（ｘk，ｙk）である三角形ｅに属する画像Ｉ2にあるとすると、その動きベクトルは以下の式に等しい：
【００１９】
【式１３】
2002524807.tif 000020
（ここで、リIeは三角形ｅに関する基礎関数を表す）
【００２０】
アフィン補間の場合、リIe（ｘ，ｙ）は、頂点がＰi、ＰjおよびＰkである三角形ｅにおける点の重心座標を表す。これらの関数は以下の式で定義される：
【式１４】
2002524807.tif 000021
【００２１】
アフィン関数リje（ｘ，ｙ）およびリke（ｘ，ｙ）は、指数ｉ、ｊ、ｋを環状に置換して、関数リie（ｘ，ｙ）から演繹される。有限要素の展開モデルを用いることも可能であり、関数リを次数ｎ＝２の多項式にすることができるが、動きベクトルの補間式は、第１、第２導関数等を導入する。有限要素のモデルの種々の選択は、文献「Handbook of Numerical Analysis」 by P. G. Ciarlet and J. L Lions, Volume 2, pages 59-99, published by North Hollandに示される。
【００２２】
本発明では、動きが徐々に推定されると、ノードベクトルとして知られるメッシュノードの動きベクトル値が最適化され、必要に応じてメッシュは局所的に高密度にされる。低解像度レベルから始めて複数の解像度レベルで最適化するのが有利である。
【００２３】
図１で示される第１の実施例では、本発明の方法は（ａ）〜（ｅ）で表される５つのステップを有する。
ステップ（ａ）では、初期の三角形のメッシュに従って画像のＩ2の点を選択することで、有限要素の初期のモデルが規定される。メッシュのノードはモデルの三角形（有限要素）の頂点を表す。いずれにせよこのメッシュは、例えば同じ映像シーケンスの、用途の必要性または予め知っている必要性または前の２つの画像間で計算された動きの必要性によって規定できる。初期のメッシュに関してデータが全く特定されない場合、標準的なスタッガーメッシュが用いられる。この時メッシュは三角形である。ゼロ値の動きベクトルがメッシュの各ノードと組み合わされる。先に規定された補間式も初期モデルのデータ要素である。
【００２４】
ステップ（ｂ）では、モデルの動きベクトル値は、ガウス−ニュートン法またはそのマルカルト拡張等の微分法によって最適化される。この最適化は自由にでき、つまりノードベクトルの可能な値に条件が無くても、条件があってもよい。ノードベクトルは、メッシュのノードの動きベクトルを示す。条件付き最適化は自由な最適化と直接関連し、本明細書で後に詳細に示される実施例の目的となる。
【００２５】
ここで用いられる自由な最適化法では、ガウス−ニュートン法（最適値の急速な収束）および適応的ステップを有する傾斜法（局所的最適値への大域収束）の有利な特性を利用して、従うべき線形システムを解明する。この方法は、動きベクトル
【外８】
2002524807.tif 000022
の繰り返し修正であり、これによって最初から動きの概算近似値を得ることが可能になる。動きベクトルの最適化の繰り返し数ｋは、方法の開始時にユーザによって設定されるか、２回の連続する繰り返しに対するノードベクトルの２連続値間の最大差に関する閾値に依存する。以下は、ガウス−ニュートン最適化法のマルカルト拡張の詳細である。
【００２６】
この方法による動きベクトルの繰り返し数ｋ＋１における修正値艟Ｄk+1は、下記線形システムによって表され：
【式１５】
2002524807.tif 000023
【００２７】
ここで、
−Ｄk+1は、繰り返し数ｋ＋１におけるノードベクトルの成分ｄxとｄyを含む２Ｎ要素の列マトリックスであり、Ｎは今のステップにおけるメッシュのノード数であり、
−Ｄkは、繰り返しｋにおけるノードベクトルの成分ｄxとｄyを含む２Ｎ要素の列マトリックスであり；
−Ｈ＝[Ｒk＋痾．Ｉ2N]
−Ｉ2Nは、次元が２Ｎの恒等行列であり；
【００２８】
【式１６】
2002524807.tif 000024
は２Ｎ要素の列マトリックスであり、この内Ｎ要素が∇x,nＥk、Ｎ要素が∇y,nＥkであり、ｎはメッシュのノードを示して、順番に値（１．．．Ｎ）をとり；
ここで：
【００２９】
【式１７】
2002524807.tif 000025
であり、ここで、繰り返し数ｋにおいてＤＦＤ（ｘ，ｙ）＝Ｙ2（ｘ，ｙ）−(ｘ−ｄx，ｙ−ｄy)であり、ｓｕｐｐ（ｎ）はノードｎに属する基礎関数リen（ｘ，ｙ）の支持関数であり、つまり全ての三角形が頂点に対するノードｎを有し；
【００３０】
【式１８】
2002524807.tif 000026
は、次元が２Ｎの正方行列であり、
【００３１】
ここで、
【式１９】
2002524807.tif 000027
ここで、ｍおよびｎはメッシュノードを示し、交互に値（１．．．Ｎ）をとり、
ｓｕｐｐ（ｎｍ）＝ｓｕｐｐ（ｎ）∩ｓｕｐｐ（ｍ）である。
【００３２】
【式２０】
2002524807.tif 000028
ここで、
【外９】
2002524807.tif 000029
は、リnの関数ノルムである。２つの最も有利なノルムは下記の通りであり、
【００３３】
【式２１】
2002524807.tif 000030
≡ｓｕｐｐ（ｎ）≡は、離散領域ｓｕｐｐ（ｎ）のカージナル数を示す。
【００３４】
最適化段階の終了時に、Ｎ個のノードベクトルが有効であり、それぞれがメッシュの１つのノードに関係する。
適応性勾配の変形例では、技術用語で「ＬＤＬtプロフィール」として知られる分解法を用いて、線形システム（１）を分解し、処理を加速化することも可能である。この方法は、Theodore Lascauxによる文献「Matrix numerical analysis applied to the art of the engineer」, Volume 1, pp 295-299, published by Masson, 1986,に説明されている。
【００３５】
本発明の有利な特性により、これらの三角形上の画像
【外１０】
2002524807.tif 000031
と画像Ｉ2間の差が大きすぎる時、メッシュは三角形の分割を介して局所的に細分化される。このため本発明の方法のステップ（ｃ）では、差Ｅが各三角形ｅに対して、画像
【外１１】
2002524807.tif 000032
と画像Ｉ2との間で計算される。差Ｅは下記の通りである：
【００３６】
【式２２】
2002524807.tif 000033
もちろん、各三角形に対する差を計算するにはまず、ステップ（ｂ）の最後に得られるノードベクトルから得られる補間を用いて、画像Ｉ2の全ての点の動きベクトル値を計算する必要がある。
【００３７】
次に、ステップ（ｄ）によって、メッシュはモデルの全三角形の一部分上で細分化される。この一部分は、ステップ（ｃ）で予め計算された差Ｅに関する判定基準に従って決められる。こうした細分化を実施するため、例えば、差Ｅを降順に分類し、且つこの分類の、Ｘ個のこのクラスの最初の三角形をより小さい三角形に細分して、モデルの三角形を分類することも可能である。Ｘはモデルの有限要素の数の所定の一部分、例えば半分である。
【００３８】
メッシュを局所的に細分化するため、ステップ（ｃ）で計算された、全ての差Ｅとその有限要素の大きさに関係する閾値差とを比較し、差Ｅが閾値差より大きい有限要素をより小さい有限要素に細分することも可能である。
【００３９】
三角形ｅの４つの小さい三角形への細分化が図２で示される。三角形ｅは、それぞれ動きベクトル
【外１２】
2002524807.tif 000034
を有する３つの頂点Ｐ1、Ｐ2およびＰ3によって規定される。４つに細分するため、３つの新しいノードＰ4、Ｐ5、Ｐ6が三角形の３辺Ｐ1Ｐ3、Ｐ1Ｐ2、Ｐ2Ｐ3の中点に規定される。これら３つの新しいノードそれぞれに、ノードが属する辺の２頂点間の動きベクトルの平均値に等しい動きベクトル：
【００４０】
【式２３】
2002524807.tif 000035
が割当てられる。次に辺がＰ1Ｐ2、Ｐ2Ｐ3、Ｐ1Ｐ3の三角形ｅに隣接する三角形が２つまたは３つに細分される。
【００４１】
こうして、メッシュが局所的に細分化された有限要素のモデルが得られる。ステップ(ｅ)では、ステップ（ｂ）、（ｃ）および（ｄ）が前のステップ（ｄ）の最後に繰り返される。この連続するステップを停止判定基準が満たされるまで繰り返す。停止判定基準は、例えばステップ（ｄ）の最後に達成すべき所定数の有限要素である。
前ステップ（ｃ）の最後に得られるモデルの全有限要素の差が閾値差より小さい時も、本発明の方法を止めることが可能である。
【００４２】
図３に示される改良例では、画像Ｉ1とＩ2の複数の解像度レベルに依存してステップ（ｂ）〜（ｅ）を実施する。こうした変形は動きベクトルの計算の収束を改良、且つ加速するためである。これを達成するために、まずデジタル画像Ｉ1とＩ2に対して、解像度レベルがｒで輝度がＹirであるＲ個の画像Ｉirの集合を規定し、ｒは順に（Ｒ−１,Ｒッ２，．．．０）の値を、ｉは（１，２）の値をとり、解像度レベルｒ＝Ｒ−１からレベルｒ＝０までの各解像度レベルにおいて、ステップ(ｂ)〜（ｅ）を実施する。画像Ｉ10とＩ20がデジタル画像Ｉ1とＩ2に対応することに注意しなくてはならない。
【００４３】
実際には、画像Ｉjrは、その画像のスペクトルバンドの１／２rだけをｘおよびｙの方向にする、線形ローパスフィルタを用いて画像Ｉiをフィルタリングして得られ、線形ローパスフィルタは、標準化周波数[−１／２，１／２]の空間内に通過帯域ＢＰr＝[１／２r+1，１／２r+1]を有するパルスレスポンスフィルタｈnrである。画像Ｉirは下記式によって規定される：
【００４４】
【式２４】
2002524807.tif 000036
【００４５】
用いられるフィルタは、例えば理想のフィルタの近似値であり、そのパルスレスポンスは下記のように規定される：
【式２５】
2002524807.tif 000037
ここで、ＢおよびＭは自然数であり、
理想的な場合には、Ｍ＝＋∞である。
【００４６】
前記に示したように、複数の解像度レベルにおける最適化は動きベクトルの計算の収束を改良し、加速することができる。選択される解像度レベルの数は、メッシュで実施される連続細分化の数とは異なっていてもよい。
好ましい実施例では、モデルの各三角形に密度の条件を加え、三角形が反転しないようにする。
頂点Ｐi、ＰjおよびＰkを有する三角形の密度は下記式で規定される：
【００４７】
【式２６】
2002524807.tif 000038
【００４８】
三角形の密度をゼロに向かわないようにすると、反転しないようになる。このため、三角形を反転させないために、各三角形が下記条件を証明しなくてはならない：
【００４９】
【式２７】
2002524807.tif 000039
ここで、Ｋは許可された密度差を固定するパラメターであり、
【外１３】
2002524807.tif 000040
は、モデルのノードの動きベクトルの列ベクトルである。
【００５０】
本発明で、この条件は動きベクトルの最適化時の各三角形に関係する。動きベクトルを最適化するステップは下記タイプの系に等しく：
【式２８】
2002524807.tif 000041
ここで、
−
【外１４】
2002524807.tif 000042
は、画像Ｉ2および前記画像
【外１５】
2002524807.tif 000043
間の差を表し；
−ｇeは三角形ｅに関する条件であり；
−Ｉはメッシュの三角形の集合である。
【００５１】
条件下における最適化の問題を解決するために、いわゆる増加ラグランジュ法が用いられる。この方法は、「Theories and algorithms」 by Michel Minoux, Volume 1, pp 257-260, published by Dunod 1983という文献に記載されている。この方法では、２つの最適化方法：ラグランジュ最適化および外部損失の最適化を組み合わせる。
【００５２】
この方法では、前記系の解決は、以下によって条件無しで系を解決することである：
【式２９】
2002524807.tif 000044
ここで、
ｒeは損失要素であり、
・eはラグランジュ乗数であり、
Ｇは以下の式で決められる増加ラグランジアンである：
【００５３】
【式３０】
2002524807.tif 000045
【００５４】
条件ｇeはテイラーの公式で予め次数１に線形化した：
【式３１】
2002524807.tif 000046
【００５５】
最適化法は下記の通りである：
−ｋ＝０を初期化し、
−・＝０およびｒ＝０を代入して、
【外１６】
2002524807.tif 000047
および
【外１７】
2002524807.tif 000048
となり、ｍがモデルの三角形の数を示し、
【００５６】
−最小の艟Ｄk+1（・，ｒ）を決めて、繰り返し数ｋ＋１において、
【式３２】
2002524807.tif 000049
ここで、繃t＝（・，ｒ）、Ｃtは
【外１８】
2002524807.tif 000050
のマトリックスであり、
Ｃtは係数に対して以下の値を有する線形条件のマトリックスを形成し：
【００５７】
【式３３】
2002524807.tif 000051
ここで、ｅは頂点Ｐi、ＰjおよびＰkを有する三角形を表す。
【００５８】
次に・をUzawaのアルゴリズムで更新し、ｒを増加させる。繰り返し数ｋ＋２に進む前に、前記操作を全ての条件が証明されるまで繰り返す。Uzawaのアルゴリズムは、「Theories and algorithms」 by Michel Minoux, Volume 1, published by Dunod 1983という文献に詳細に記載されている。
【００５９】
最後の実施例では、条件を導入して、画像Ｉ1の範囲外に動きベクトルを適用した後に得られるメッシュのフローイングオーバーを避けることが可能である。本実施例は、動きベクトルの適用後にメッシュの周辺ノードを画像のエッジに残しておくことにある。これを実施するため、画像Ｉ2の左右エッジの周辺ノードに対する横座標成分艟Ｄk+1は、各繰り返しｋにおいて取り消される。同様に、画像Ｉ2の上下エッジの周辺ノードに対する縦座標成分艟Ｄk+1は、各繰り返しｋにおいて取り消される。
【００６０】
コード化を用いる場合、メッシュと組み合わされるのは部分的四次ツリーである。メッシュの細分化（ステップｄ）において、さらなるレベルがツリーに加えられる。ツリーの各レベルがメッシュレベルを表し、ツリーの各ノードが対応するメッシュレベルの三角形を表す。コーディングステップで生成される２進列は、レベル単位のツリーの読取りを介して得られる。この２進列において、ツリーの各ノードに関する動きベクトルは、もとのノードが存在する場合、もとのノードの動きベクトルに関して微分法でコード化するのが好ましく、レベル単位で配置される。対応するデコーディングステップは、エンコーダ由来で受信される２進列からこのツリーを再生することにある。
【図面の簡単な説明】
【図１】
本発明の動き推定方法の第１実施例の概略図を表す。
【図２】
本発明の方法のステップ（ｄ）を示す。
【図３】
本発明の動き推定方法の改良された実施例の概略図を表す。