(57)【特許請求の範囲】
【請求項１】
等質の領域（Ｒｉ）への画像（１４ｉ）の断片化（Ｆ）のための方法であって、該断片化は、
所定の基準に従って画像のピクセルを再集合化する断片を画成する第１ステップと、
上記断片を併合するための反復ステップとを含み、
該反復ステップは、
前回の反復により得られた断片の中から、輝度又はクロミナンスに関連する少なくとも１つの選択パラメーターに従って可能な限り類似性のある隣接する断片Ｆｉ及びＦｊを選択するサブステップと、
積Ａ×Ｂ×Ｃが閾値より小さい場合に、新たな断片を付与するために上記選択した断片Ｆｉ及びＦｊを併合するサブステップを含み、
上記類似性は、上記断片Ｆｉ及びＦｊのピクセルの数の和に対する上記断片Ｆｉ及びＦｊのピクセルの数の積の比に比例する因子Ａと、上記少なくとも１つの選択パラメーターと一致する因子Ｂの積Ａ×Ｂによって評価され、因子Ｃは、画像中の断片のピクセルの平均数の逆数に比例する、方法。
【請求項２】
Ｎｍがピクセルの平均数のような断片Ｆｉの平均サイズを表わすとき、上記因子Ｃが２／Ｎｍに比例することを特徴とする、請求項１記載の方法。
【請求項３】
上記選択パラメーターが、輝度、クロミナンス、及びテクスチャーのうちの少なくともいずれか１である、請求項１又は２記載の方法。
【請求項４】
各反復的な併合は、２つの隣接する断片Ｆｉ及びＦｊにのみ関連することを特徴とする、請求項１、２又は３記載の方法。
【請求項５】
Ｎｉ及びＮｊが併合される隣接断片Ｆｉ及びＦｊのサイズを表わすとき、上記因子ＡがＮｉ×Ｎｊ／（Ｎｉ＋Ｎｊ）に比例することを特徴とする、請求項４記載の方法。
【請求項６】
断片のサイズが該断片に含まれるピクセルの数であることを特徴とする、請求項５記載の方法。
【請求項７】
（Ｙｉ−Ｙｊ）、（Ｕｉ−Ｕ２）及び（Ｖｉ−Ｖｊ）が、２つの断片間の、輝度の差、青色の信号の差、及び赤色の信号の差を、各々表わすとき、上記因子Ｂが、［（Ｙｉ−Ｙｊ）２＋（Ｕｉ−Ｕｊ）２＋（Ｖｉ−Ｖｊ）２］に比例することを特徴とする、請求項１乃至６のうちいずれか１項の方法。
【請求項８】
当該方法は、上記反復ステップにより得られた画像の断片をグループ化するステップを更に含み、該ステップは、各断片Ｆｉの個々の動きのモデル（２４ｉ）を使用し、該動きのモデル（２４ｉ）は、当該グループ化により作成された断片に同一の動きのモデル（２４ｋ）を割り当てるため、最小の誤り若しくは分散（Ｖａｒ２４ｉ）を与えるように決定され、グループ化の判断は、２つの断片Ｆｉ及びＦｊのモデル（２４ｉ、２４ｊ）の間の動きの差の評価値（Δｉ／ｊ）に比例するグループ化コストＣｒｅの関数であることを特徴とする、請求項１乃至７のうちいずれか１項の方法。
【請求項９】
上記グループ化コスト（Ｃｒｅ）は、動きの閾値Ｓｒｅに反比例することを特徴とする、請求項８記載の方法。
【請求項１０】
Ｎｉが断片Ｆｉのピクセルの数を、Ｎｊが断片Ｆｊのピクセルの数を表わすとき、上記グループ化コストＣｒｅが、Ｃｒｅ＝Ｎｉ×Ｎｊ／（Ｎｉ＋Ｎｊ）×［（Δｉ／ｊ）／Ｓｒｅ］により計算されることを特徴とする、請求項９記載の方法。
【請求項１１】
上記Ｆｊが、上記断片Ｆｉのサイズより大きく、これらの断片Ｆｉ、Ｆｊ間の動きの差の値Δｉ／ｊは、
断片Ｆｉの動きのパラメーター（ａｉ，ｂｉ，ｃｉ，ｄｉ，ｅｉ，ｆｉ）を備えたモデル２４ｉに従い、断片Ｆｊの各ピクセルＰ（ｘ，ｙ）に対する動きベクトル（１５ｐｊ／ｉ）の計算を、Ｆｊの座標（ｘｊ，ｙｊ）を備えたピクセルＰに対して、
ｄｘｊ／ｉ＝ａｉ＋ｂｉｘｊ＋ｃｉｙｊ
ｄｙｊ／ｉ＝ｄｉ＋ｅｉｘｊ＋ｆｉｙｊ
に従って座標（ｄｘｊ／ｉ，ｄｙｊ／ｉ）を備えたベクトル１５ｐｊ／ｉを計算する方法で、実行し、
該断片Ｆｊのパラメーター（ａｉ，ｂｉ，ｃｉ，ｄｉ，ｅｉ，ｆｉ）を備えたモデル２４ｊに従い、該ピクセルＰの動きベクトル１５ｐｊ／ｊの値を、
ｄｘｊ／ｊ＝ａｊ＋ｂｊｘｊ＋ｃｊｙｊ
ｄｙｊ／ｊ＝ｄｊ＋ｅｊｘｊ＋ｆｊｙｊ
により求め、
これらの２つのベクトル１５ｐｊ／ｉ及び１５ｐｊ／ｊの間の差
【外１】
0004354146.tif 000029
の値を、
【数１】
0004354146.tif 000030
を計算することにより求め、
断片Ｆｉ及びＦｊ間の動きの差のΔｉ／ｊの値を、断片Ｆｊのすべてのピクセルの
【外２】
0004354146.tif 000031
の値を総和し、Ｎｊで除することによって求める、各ステップを含む、請求項８，９又は１０記載の方法。
【請求項１２】
断片の上記サイズは、該断片に含まれるピクセルの数として定義される特徴とする、請求項１１記載の方法。
【請求項１３】
上記グループ化閾値Ｓｒｅが、上記断片Ｆｉの動きの上記モデル化（２４ｉ）の誤り若しくは分散Ｖａｒ２４ｉに比例することを特徴とする、請求項９乃至１２のうちいずれか１項の方法。
【請求項１４】
上記グループ化閾値Ｓｒｅが、上記断片Ｆｉの動きの上記モデル（２４ｊ）の上記分散（Ｖａｒ２４ｊ）と上記画像の断片の動きの上記モデルの上記分散の上記平均（Ｖａｒｍ）との間の最大値ＭＡＸ（Ｖａｒ２４ｊ、Ｖａｒｍ）に、比例することを特徴とする、請求項９乃至１２のうちいずれか１項の方法。
【請求項１５】
上記グループ化閾値Ｓｒｅが高くなるにつれて、前の画像の同一領域に含まれていたピクセルを有する断片がグループ化されるとき、上記グループ化の選択肢が減少していくことを特徴とする、請求項１３又は１４記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ビデオ画像圧縮の分野に係り、より詳細には、デジタル・画像の断片化を停止する方法に関する。
【０００２】
【従来の技術】
デジタル・画像を送信するか記録するために、送信された情報の量及び結果的にこの送信のために必要とされる帯域幅を低減する、コード化方法が一般に活用される。
【０００３】
コード化する方法のうちの幾つかは、いわゆる等質な領域へ、即ち、この領域のピクセル（画像要素）のクロミナンス及び／又は輝度のような１若しくはそれ以上の基準による等質な性質の領域への、画像の細分化に求める。
【０００４】
次いで、領域の各ピクセルに関係する輝度とクロミナンスのデータの送信は、該当する領域の輝度とクロミナンスのデータの単純な送信によって置換されることができる。
【０００５】
さらに、この細分化は、画像間・コード化に関して求めることができる。従って、このように定義された領域の、例えば輝度とクロミナンスの状態に関係のある情報を送信するか記録する前に、この情報が既に送信されたか記録されたかどうか判断する。他言するに、この領域が以前に送信された画像の中で既に識別されたかどうか判断する。
【０００６】
この領域が以前の画像の中で識別されていない場合、画像のこの領域に関係するすべて情報が送信される。
【０００７】
反対に、この領域が以前の画像の送信中に識別された場合、以前の画像を基準としたこの領域の変位を表わす信号だけが送信される。
【０００８】
したがって、受信若しくは読み出し時に、この領域は、前の画像に関して既に送信された情報から再構築される。
【０００９】
例えば、同一の一定で静止している青い背景をすべて含む画像列を考慮する。この場合、一つの領域を形成するためにこの青い背景を考慮することによって、この領域に関係する情報は、最初の画像に対してのみ送信される。その後、次の画像をコード化は、この領域の存在および位置を示す表示を単に含む。
【００１０】
したがって、この青い背景は、すべての画像に対して、初期の画像を基準として送信された（或いは記録した）情報から再生させられる。
【００１１】
画像を細分化する既知の方法についての説明は、添付図面によって以下に与えられる。
【００１２】
この図には、画像の細分化に対する多様なステップが表わされており、この細分化は、２つの予備オペレーションを含み、即ち１のオペレーション２０は、輝度に関連し、他方のオペレーション２２は、クロミナンスあるいはその後記述されるようなアナログのパラメーターに関連する。
【００１３】
ピクセルのクロミナンスに関係のあるオペレーション２２が“断片化（フラグメンテーション）”と呼ばれる一方、クロミナンスの基準、及びピクセルの明白な動きの基準に従った画像の最終的な分割が、“細分化（セグメンテーション）”呼ばれることを、注意されたい。
【００１４】
オペレーション２０は、以前の画像１２ｉのピクセルの輝度を基準として現在の画像１４ｉのピクセルの輝度の比較を含む。この比較は、画像１２ｉのピクセルを基準とした、画像１４ｉのピクセルの動き若しくは輝度の変動を決定する。
【００１５】
このピクセルＰの輝度のこの変動若しくは動きを表わすいわゆる“オプティカルフロー”ベクトル１５ｐは、現在の画像１４ｉの各ピクセルＰに割り当てられる。これを行うために、このベクトル１５ｐは、座標(x、y)を備えたピクセルＰで画像の動きを特徴づける座標(dx、dy)によって表現される。
【００１６】
オペレーション２２中に、断片Ｆ１，Ｆ２，…ＦＮへの色に基づく画像１４ｉの断片化Ｆが実行される。これを行うために、画像１４ｉに対する輝度情報Ｙｉは、画像１４ｉの各ピクセルＰｉに対するそれぞれの信号Ｕｉ及びＶｉによる赤色および青色の配分の情報ないし値１６及び１８と共に、使用される。
【００１７】
その後、このようにして得られた断片Ｆ１，Ｆ２，…ＦＮに基づいて、画像１４ｉの最終的な細分化は、動きパラメーターを含むオペレーション３０に従った、領域と呼ばれる部分Ｒｉへのこれらの断片Ｆｉのグループ化によって、得られる。このオペレーションは、後述されている。
【００１８】
等質性は要求された断片化の質によって定義されるが、等質な色の断片Ｆ１，Ｆ２，…ＦＮへの画像のこの断片化Ｆを実行することを可能にする多数の方法がある。
【００１９】
さらに、この断片化を実行するために他の基準が使用されてもよいことは、注意されるべきである。
【００２０】
例えば、断片化は、画像中のグレーレベルの空間的な分布に基づいた、いわゆる“テクスチャー”基準よって実行することもできる。これを行うために、これらのテクスチャーは、等質性、コントラスト、好ましいオリエンテーション、若しくは周期性の基準によって、特徴づけられる。
【００２１】
この説明では、類似の色である隣接する隣接断片のペア化のような併合（マージ）に基づいた断片化が使用される。より明確には、２個のいわゆる“開始”隣接断片に基づいて、２個の併合された断片を含む新たな１つのいわゆる“完了”断片が作成される。
【００２２】
その後、この方法は、この完了断片を新たな開始断片であると考えることにより、繰り返される。
【００２３】
単一の併合は各ステップに実行される、各併合のシーケンスを決定するために、各々想定可能な併合に関連付けられたコストＣｆｕを計算する。
【００２４】
このコストＣｆｕ（その計算は以下に記述される）は、併合が想定される２個の断片の間の色における差を表わす。
【００２５】
併合するコストＣｆｕが、すべての想定される併合化のコスト中で、最低である断片Ｆｉ及びＦｊを併合すること（Ｆｉ∪Ｆｊ）によって、併合されてよいすべての断片の中で、クロミナンス的に最も類似した断片が併合される。
【００２６】
この実施例では、２つの断片Ｆｉ及びＦｊの間を併合するコストＣｆｕの計算は、以下のとおりである。
【００２７】
【数２】
0004354146.tif 000002
この式では、Ｎｉは、断片Ｆｉ中のピクセルの数であり、Ｎｊは、断片Ｆｊ中のピクセルの数であり、（Ｙｉ−Ｙｊ）、（Ｕｉ−Ｕｊ）、及び（Ｖｉ−Ｖｊ）は、２つの断片Ｆｉ及びＦｊの間の、輝度及び色における差異をそれぞれ表わす。
【００２８】
この２つの断片Ｆｉ及びＦｊ間の併合に基づいて、２個の開始断片Ｆｉ及びＦｊのピクセルを含む新たな断片Ｆｋ＝Ｆｉ∪Ｆｊが、得られる。したがって、この新たな断片Ｆｋは、Ｎｋ＝Ｎｉ＋Ｎｊ個のピクセルを含む。
【００２９】
この新たな断片Ｆｋ＝Ｆｉ∪Ｆｊは、その後、各断片の中にあるピクセルの数によって重み付けされた、併合された断片の輝度の平均に等しい輝度Ｙｋによって、特徴づけられる。
【００３０】
より正確には、断片Ｆｊと断片Ｆｉを併合する場合、断片Ｆｋの新たな平均輝度は、次の通りである。
【００３１】
【数３】
0004354146.tif 000003
同様に、新たな断片Ｆｋの色差のパラメーターＵｋおよびＶｋを、それぞれ次の通りに定義する。
【００３２】
【数４】
0004354146.tif 000004
各ピクセルは、第１の断片化ステップに対する開始断片を構成する。引き続き、併合されていないピクセルは、断片のままである。
【００３３】
しかしながら、断片の最小数Ｎは、断片のこの数が到達する場合に細分化を停止するために、指定される。
【００３４】
したがって、画像１４ｉを構築するＮ個の断片Ｆ１，Ｆ２，…ＦＮが得られ、これら断片の各々は、所与の数のピクセルＮ１，Ｎ２，…ＮＮを含む。
【００３５】
Ｎｉ．Ｎｊ／Ｎｉ＋Ｎｊに比例するＦｉとＦｊの間の併合のコストは、併合化の等方性の始まりを仮定する場合、併合に関わるピクセルの数が大きくなるにつれて、この併合のコストは、より高くなるだろうから、小さな断片の併合化、ひいては画像の等方性の断片化が好ましい。
【００３６】
その後、オペレーション２４の間に、以前に得られたような、各断片Ｆ１，Ｆ２，…ＦＮのすべてのピクセルの動きのパラメトリック・モデル特性が、評価される。
【００３７】
これを行うために、各断片Ｆｉは、断片Ｆｉの空間座標(x、y)を備えた各ピクセルの動きベクトル１５ｐの水平成分dx及び垂直成分dyにリンクされた動きパラメータ・モデル２４ｉによって、特徴づけられる。
【００３８】
より正確には、６つのパラメーター(a、b、c、d、e、f)を備えたアファイン・モデル２４は、座標(x、y)を備えたピクセルＰの動きベクトル１５ｐの成分dxおよびdyが次の通りになるように、選択される。
【００３９】
【数５】
0004354146.tif 000005
したがって、６つの成分を備えた動きパラメーターの単一のモデル２４は、考慮された断片のすべてのピクセルの動きを表現する。
【００４０】
モデル２４ｉのパラメーターａ、ｂ、ｃ、ｄ、ｅ、ｆは、ステップ２０に各ピクセルで推定された動きベクトル１５ｐから、いわゆる最小二乗法によって決定される。
【００４１】
より明確には、開始モデル２４’ｉ（ａ’，ｂ’，ｃ’，ｄ’，ｅ’，ｆ’）に基づいて、そのパラメーターは、“実数”ベクトル１５ｐと上式によりこのモデルから計算したベクトルとの間の偏差Ｅｍｏを最小にするように、変化させられる。
【００４２】
この偏差Ｅｍｏを評価するために、各ピクセルの動きベクトル１５ｐと、前記モデルから再構築されたベクトルとの間の差の平方の合計を計算する。
【００４３】
例えば、モデル２４ｉ（ａ，ｂ，ｃ，ｄ，ｅ，ｆ）によってモデル化された、座標(dx、dy)を備えたベクトル１５ｐに対しては、次のようになる。
【００４４】
【数６】
0004354146.tif 000006
最終のパラメータ・モデル（ａ，ｂ，ｃ，ｄ，ｅ，ｆ）は、この偏差若しくは“分散”Ｅｍｏが最小となるときに、得られる。断片Ｆｉの動きのモデル化における分散は、Ｖａｒ２４ｉとして指示される。
【００４５】
一般に、ここで説明された評価は、いわゆる“異常な”値、即ち全体的に評価された値から異常に異なる値を考慮していない。
【００４６】
同時に、オペレーション２６中に、断片化Ｆは、前の画像１２ｉの細分化と比較されることができる。
【００４７】
例えば、後述されるオペレーション３０による画像１２ｉの細分化の最終結果である領域Ｒ’ｉの位置と、断片Ｆｉ及びＦｊの位置と、の間のあらゆる一致２８が特定される。
【００４８】
これらの一致２８は、例えば道路交通の分野において、一連の画像にわたる物体のトラッキングを要求するオペレーション中に使用されてもよい。
【００４９】
その後、オペレーション３０中に、オペレーション２２中の前記併合化方法に類似するグループ化方法が、実行される。従って、反復プロセスは、グループ化コストＣｒｅを最小にする、関与する２個の隣接断片に適用され、このグループ化は、新たな開始断片を生成する。
【００５０】
このオペレーション３０中に、併合化のコストは、各断片の動きパラメーターのモデル２４ｉから評価される。
【００５１】
したがって、オペレーション３０の各ステップでグループ化される２個の断片は、隣接断片のすべての対のうち動きの最も大きな類似性を示す断片である。
【００５２】
例えば、それぞれのパラメータ・モデル２４ｉ（ａｉ，ｂｉ，ｃｉ，ｄｉ，ｅｉ，ｆｉ）及び２４ｊ（ａｊ，ｂｊ，ｃｊ，ｄｊ，ｅｊ，ｆｊ）によって特徴づけられた、２個の断片Ｆｉ及びＦｊの考慮によって、これら２個の断片間の動きの類似性は、以下のように計算されるが断片Ｆｉが断片Ｆｊより大きなサイズであると仮定されている。
【００５３】
動きベクトル１５ｐｊ／ｉは、断片Ｆｉに対するパラメータ・モデル２４ｉに従って断片Ｆｊの各ピクセルに対して計算される。したがって、Ｆｊの座標（ｘｊ，ｙｊ）を備えたピクセルについては、次の式によって座標（ｄｘｊ／ｉ，ｄｙｊ／ｉ）を備えたベクトル１５ｐｊ／ｉを計算する。
【００５４】
【数７】
0004354146.tif 000007
その後、このピクセルの動きベクトル１５ｐｊ／ｊは、この断片に対するパラメータ・モデル２４ｊによって評価される。即ち、次の通りである。
【００５５】
【数８】
0004354146.tif 000008
最後に２つのベクトル１５ｐｊ／ｉおよび１５ｐｊ／ｊの間の差異は、差
【００５６】
【外３】
0004354146.tif 000009
を計算して、評価される。
【００５７】
【数９】
0004354146.tif 000010
その後、Ｆｊのすべてのピクセルの
【００５８】
【外４】
0004354146.tif 000011
の平均が、２つの断片ＦｉおよびＦｊのパラメータ・モデル間の差異の評価
【００５９】
【外５】
0004354146.tif 000012
を得るために計算される。
【００６０】
続いて、動きの差
【００６１】
【外６】
0004354146.tif 000013
が前もって定義した閾値より小さい断片ＦｉおよびＦｊが、グループ化にされるが、この閾値は、小さくなるにつれて、断片間の対応性は、グループ化にされるこれらの断片に対する秩序に於いて、より大きくならなければならない。
【００６２】
しかしながら、このグループ化するオペレーション３０中に、新たな動きパラメーター２４は、グループ化により作成された断片に関して計算されない。これは、これらの複雑な計算が過度に大きな持続時間を要求するからである。
【００６３】
このため、このオペレーション３０中に、２個のグループ化された断片の動きベクトルのうちの１つと等しい動きベクトルは、グループ化により作成された各断片に割り当てられる。
【００６４】
この実施例では、最小サイズのグループ化された断片の動きパラメーターが、グループ化から得られた断片に割り当てられる。
【００６５】
例えば、断片Ｆ’ｉのピクセルＮ’ｉの数が断片Ｆ’ｊのピクセルの数Ｎ’ｊより大きくなるような、２つの断片Ｆ’ｉおよびＦ’ｊの間のグループ化を考慮する。計算は、Ｆ’ｉのグループ化及びＦ’ｊのグループ化を通じて得られた断片Ｆ’ｋに、ベクトル２４’ｉに等しい動きベクトル２４’ｋを割り当てることにより高速化される。
【００６６】
これらの反復的なグループ化は、断片の指定された数が得られるまで、実行される。
【００６７】
このグループ化するオペレーションが完成したとき、この方法による画像の細分化を特徴づける、所与の数の“最終”断片若しくは所与の数の領域Ｒｉが得られる。
【００６８】
領域Ｒｉに含まれるピクセルＰのセットは、動きという点で等質であり、このパラメーターは、領域Ｒｉのピクセルの全セットに対するユニークなモデル２４ｉによって特徴付けられている。
【００６９】
この細分化を送信する（あるいは記録）前に、マーキング・オペレーション３３が実行され、その間、画像１４ｉを構築する領域が識別される。したがって、画像１４ｉに後続する画像１６ｉが解析される時、画像１６ｉによりオペレーション２６を着手するためにこの細分化を使用することは可能だろう。
【００７０】
これを行うために、最後のステップ３５が必要とされ、このステップ３５の間、次の画像１６ｉの外観上のラグに対応する遅延が割り当てられる。
【００７１】
上述したように、断片Ｆｉの中への画像の断片化Ｆは、得られた断片の数の基準によって停止される。したがって、得られた断片の数がある閾値に達したとき、併合化方法は停止する。
【００７２】
【発明が解決しようとする課題】
本発明は、この停止基準が最適化された結果を生まないという発見に起因する。特に、この方法によれば、非常に単純な画像の断片化は、後者の過剰な断片化を発生する一方、多数の詳細を含む複雑な画像の断片化が、不適当な断片化を発生してしまう。
【００７３】
本発明は、画像の性質に適合する断片化を得ることを可能にする。
【００７４】
【課題を解決するための手段】
本発明は、断片間に併合化のコストの評価を使用する、画像の断片化のための方法に関し、この併合化コストは、（Ｆｉ∪Ｆｊ）＝Ａ＊Ｂの形であり、Ａは、色差及び／又は輝度差に比例した項で、Ｂは、ピクセルの数に反比例する項であり、本方法は、上記コストが、ピクセルの数と一致する新たな係数Ｃによって重み付けられることを特徴とする。併合のコストは、色差若しくは輝度差を基準として評価することができるので、色閾値及び／又は輝度閾値に達するときに、断片化を停止して、画像の複雑さに断片化を適応させることは可能である。
【００７５】
一実施例では、上記因子Ｃは２／Ｎｍに比例し、この場合、Ｎｍは、断片Ｆｉ当たりのピクセルの平均数のような、断片Ｆｉの平均サイズを表わす。
【００７６】
（１つ若しくはそれ以上の）選択パラメーターは、例えば、パラメーターとして、輝度、クロミナンス、及びテクスチャーのうちの少なくともいずれか１である。
【００７７】
一実施例によると、各反復的な併合は、２つの隣接する断片Ｆｉ及びＦｊにのみ関連する。
【００７８】
上記因子Ａは、一例として、Ｎｉ×Ｎｊ／（Ｎｉ＋Ｎｊ）に比例し、この場合、Ｎｉ及びＮｊが併合される隣接断片Ｆｉ及びＦｊのサイズを表わす。断片のサイズが、断片に含まれるピクセルの数であることも可能である。
【００７９】
一実施例によると、上記因子Ｂが、［（Ｙｉ−Ｙｊ）２＋（Ｕｉ−Ｕｊ）２＋（Ｖｉ−Ｖｊ）２］に比例し、この場合、（Ｙｉ−Ｙｊ）、（Ｕｉ−Ｕ２）及び（Ｖｉ−Ｖｊ）が、２つの断片間の、輝度の差、青色の信号の差、及び赤色の信号の差を、各々表わす。
【００８０】
更に、本発明は、前記実施例のいずれかによる方法によって得られた画像の断片をグループ化する方法に関する。本方法は、各断片Ｆｉの個々の動きのモデルを使用し、この動きのモデルは、作成された断片に同一の動きのモデルを割り当てるため、既知の誤り若しくは分散により決定されている。
【００８１】
一実施例では、上記グループ化コストＣｒｅは、動きの閾値Ｓｒｅに反比例し、他の停止テストがない状態でも、グループ化が、評価値Δｉ／ｊが閾値より大きい場合に、許容されないようなる。
【００８２】
より正確には、一実施例によると、グループ化コストＣｒｅが、Ｃｒｅ＝Ｎｉ×Ｎｊ／（Ｎｉ＋Ｎｊ）×［（Δｉ／ｊ）／Ｓｒｅ］により計算され、この場合、Ｎｉが断片Ｆｉのピクセルの数であり、Ｎｊが断片Ｆｊのピクセルの数である。
【００８３】
更に、Ｆｊが上記断片Ｆｉのサイズより大きい場合、これらの断片Ｆｉ、Ｆｊ間の動きの差の評価Δｉ／ｊは、例えば次のステップを含む。即ち、
断片Ｆｉの動きのパラメーター（ａｉ，ｂｉ，ｃｉ，ｄｉ，ｅｉ，ｆｉ）を備えたモデル２４ｉに従い、断片Ｆｊの各ピクセルＰ（ｘ，ｙ）に対する動きベクトル（１５ｐｊ／ｉ）の計算を、Ｆｊの座標（ｘｊ，ｙｊ）を備えたピクセルＰに対して、
ｄｘｊ／ｉ＝ａｉ＋ｂｉｘｊ＋ｃｉｙｊ
ｄｙｊ／ｉ＝ｄｉ＋ｅｉｘｊ＋ｆｉｙｊ
に従って座標（ｄｘｊ／ｉ，ｄｙｊ／ｉ）を備えたベクトル１５ｐｊ／ｉを計算する方法で、実行するステップと、
該断片Ｆｊのパラメーター（ａｉ，ｂｉ，ｃｉ，ｄｉ，ｅｉ，ｆｉ）を備えたモデル２４ｊに従い、該ピクセルＰの動きベクトル１５ｐｊ／ｊの値を、
ｄｘｊ／ｊ＝ａｊ＋ｂｊｘｊ＋ｃｊｙｊ
ｄｙｊ／ｊ＝ｄｊ＋ｅｊｘｊ＋ｆｊｙｊ
により求めるステップと、
これらの２つのベクトル１５ｐｊ／ｉ及び１５ｐｊ／ｊの間の差
【００８４】
【外７】
0004354146.tif 000014
の値を、
【００８５】
【数１０】
0004354146.tif 000015
を計算することにより求めるステップと、
断片Ｆｉ及びＦｊ間の動きの差のΔｉ／ｊの値を、断片Ｆｊのすべてのピクセルの
【００８６】
【外８】
0004354146.tif 000016
の値を総和し、Ｎｊで除することによって求めるステップの各ステップを含む。
【００８７】
本方法の一実施例では、断片の上記サイズは、この断片に含まれるピクセルの数として定義される。
【００８８】
更に、上記グループ化閾値Ｓｒｅは、好ましくは、上記断片Ｆｉの動きの上記モデル化の誤り若しくは分散Ｖａｒ２４ｉに比例する。
【００８９】
一実施例では、グループ化閾値Ｓｒｅは、断片Ｆｉの動きのモデルの上記分散と画像の断片の動きのモデルの分散の平均との間の最大値に比例する。
【００９０】
一実施例では、前の画像の同一領域に含まれていたピクセルを有する断片がグループ化されるとき、グループ化閾値Ｓｒｅがより高くなる。この場合、上記グループ化の選択肢が減少していく。
【００９１】
しかし、輝度予測テストは、より選択肢の少ないグループ化閾値Ｓｒｅを適用する前に、使用できる。
【００９２】
従って、一実施例によると、断片Ｆｊは断片Ｆｉのサイズより大きなサイズであり、輝度予測は、断片Ｆｊの座標（ｘｊ，ｙｊ）を備えた各ピクセルＰに対して、座標（ｄｘｊ／ｉ，ｄｙｊ／ｉ）を備えたベクトル１５ｐｊ／ｉを計算して実行され、現在の画像のＰ（ｘｊ，ｙｊ）で予測された輝度は、前の画像の（ｘｊ−ｄｘｊ／ｉ，ｙｊ−ｄｙｊ／ｉ）で見出された輝度である。
【００９３】
更に、任意のサイズＮｍｉｎの領域への断片のグループ化を促進すべく、断片Ｆｉのピクセルの数ＮｉとＮｍｉｎとの間の最大値Ｎ’ｉ、及び、断片Ｆｊピクセルの数ＮｊとＮｍｉｎとの間の最大値Ｎ’ｊを呼び出して、係数を乗算されたグループ化コストＣｒｅを用いるグループ化停止テストを使用することが可能である。この場合、停止テストは、
【００９４】
【数１１】
0004354146.tif 000017
であってよい。
【００９５】
しかし、Ｎｍｉｎより大きいサイズの断片のグループ化を促進しないために、Ｃｒｅ（Ｆｉ∪Ｆｊ）＞１なるグループ化停止基準を使用することも可能である。
【００９６】
本発明の他の特性及び利点は、実施例の説明により明白になるだろう。
【発明の実施の形態】
本発明の好ましい実施例の説明では、オペレーション２２中に、上述した物と類似する断片併合化コストの計算が活用される。即ち、
【００９７】
【数１２】
0004354146.tif 000018
この式では、２つの断片ＦｉおよびＦｊを併合するコストが、次の因子（ファクター）ＡおよびＢの積に等しいことがわかる。
【００９８】
【数１３】
0004354146.tif 000019
続いて、色差および輝度差と一致する停止基準を使用するために、２つの追加のステップが導入される。
【００９９】
即ち、最初に、あらゆる想定された併合のコストが、ピクセルの数の逆数と一致する因子Ｃにより乗算される。
【０１００】
好ましい実施例では、Ｃ＝２／Ｎｍ、Ｎｍは、断片化の所与のステップでの断片Ｆｉのピクセル中の平均サイズを表わす。他言すると、断片化の所与のステップで、Ｎ１，Ｎ２，…Ｎｋのピクセルを各々含むｋ個の断片Ｆ１，Ｆ２，…Ｆｋを考慮すれば、Ｎｍ＝（Ｎ１＋Ｎ２＋…＋Ｎｋ）／Ｋとなる。
【０１０１】
因子Ｃが以下の考慮により得られることが理解されるべきである。
【０１０２】
【数１４】
0004354146.tif 000020
続いて、積コスト（Ｆｉ∪Ｆｊ）＊Ｃ、即ちＡ＊Ｂ＊Ｃは、固定の閾値Ｓｃと比較される。
【０１０３】
Ａ＊Ｂ＊Ｃ＜Ｓｃの場合、２個の断片間の色及び輝度での偏差は、断片化の停止に対して固定された閾値偏差未満である。２個の断片が十分に類似しているので、併合は許可される。
【０１０４】
Ａ＊Ｂ＊Ｃ＞Ｓｃの場合、２個の断片間の色及び輝度での偏差は、固定された閾値より大きく、併合は許可されず、また、断片化は停止される。
【０１０５】
従って、断片化の停止に対するテストは、到達すべき断片の指定された数に一致することがないが、併合がこれ以上発生しない断片間等質性閾値に一致する。
【０１０６】
したがって、画像の複雑さの関数として、画像の細分化の結果得られる領域の数は可変である。
【０１０７】
さらに、併合の中に考慮される断片に依存しない項２／Ｎｍの使用によって、小さな断片の併合化は促進される。
【０１０８】
特に、併合のコストは、輝度と色の差である因子Ｂに、及び（Ｎｉ×Ｎｊ／（Ｎｉ＋Ｎｊ））．２／Ｎｍに等しい因子Ａ＊Ｃに、比例する。
【０１０９】
この因子Ａ＊Ｃに起因して、断片ＦｉおよびＦｊが平均値より小さいサイズを持っている場合、この因子は、１より小さい。
【０１１０】
反対に、断片ＦｉおよびＦｊが平均値より大きなサイズを持っている場合、この係数Ａ＊Ｃは１より大きく、また、併合のコストが増加させられる。
【０１１１】
併合化の閾値Ｓｃは、輝度差及び／又は色差の平方と一致している。
【０１１２】
【外９】
0004354146.tif 000021
が各成分の６のグレーレベルを表わす場合、
【０１１３】
【外１０】
0004354146.tif 000022
の閾値が満足な結果を生むことがわかっている。
【０１１４】
別の局面によれば、本発明は、更に、固定の動き差の基準によるオペレーション３０の断片Ｆｉのグループ化が、この併合化オペレーションを最適化しないという発見に起因する。特に、固定閾値の使用は、細分化の良好な安定性を可能としない。
【０１１５】
実際、画像を処理する場合、動き推定値及びそれらの精度は、断片間で相当に変化するものである。例えば、最初の断片は、動き推定値が±０．２５のピクセルの精度で−１および＋１のピクセルの範囲内で変化して、処理できるが、第２の断片は、動き推定値が±２のピクセルの精度で−３０と＋３０の範囲内で変化して、処理できる。
【０１１６】
その後、これらの２つの推定に対して、例えば固定閾値の使用は、この閾値がこれらの断片に対して狭すぎる若しくは広すぎるといった不適当な値となるだろうから、それらの動きの特徴化を最適化しない。
【０１１７】
このため、他の実施例と無関係に使用することができる一実施例では、関連する断片の関数として変化できるグループ化コストＣｒｅが計算され、グループ化された断片のパラメータ・モデルの間の差異の評価Δｊ／ｉを考慮し、以前に定義されたような、最も小さなグループ化された断片の動きモデルの分散Ｖａｒ２４ｉと以前の画像の先行の細分化とに関係するグループ化閾値Ｓｒｅを考慮する。
【０１１８】
続いて、断片ＦｉおよびＦｊの間の可能なグループ化は、それらのグループ化よって受けるコストＣｒｅ（Ｆｉ∪Ｆｊ）に従ってランクを定義される。この好ましい実施例では、このコストＣｒｅ（Ｆｉ∪Ｆｊ）は、次の式によって計算される。
【０１１９】
【数１５】
0004354146.tif 000023
したがって、コストが最小である断片、即ち動き基準によって最も類似した断片を、断片間の動きの違いに関係のあるグループ化停止閾値Ｓｒｅを課しながら、ともにグループ化することは可能である。
【０１２０】
その後、画像の細分化は、到達すべき前もって定義した細分の数にではなく画像の性質に依存するので、改善される。
【０１２１】
グループ化閾値Ｓｒｅは、上述したように、断片Ｆｊの動きのパラメータ・モデル２４ｊの決定がこのモデルの分散Ｖａｒ２４ｊを決定することを可能にするという事実、を考慮する。続いて、この分散は、断片間の動きの類似点を評価する際に考慮しなければならない許容マージンを表わす。
【０１２２】
したがって、他の実施例と無関係に使用することができる１の実施例では、グループ化閾値Ｓｒｅは、分散Ｖａｒ２４ｊに比例する、即ち、この閾値Ｓｒｅは、分散Ｖａｒ２４ｊが大きくなるにつれて、より高くなる。他言すると、より大きな、断片の動きのモデル化での不確実性が大きくなるにつれて、グループ化に対する許容閾値Ｓｒｅが大きくなる。
【０１２３】
したがって、断片Ｆｉのパラメータ・モデル２４ｉの決定が、エラーの大きなマージン即ちＶａｒ２４ｊを発生させるとき、この断片Ｆｉに対するグループ化閾値Ｓｒｅは、この近似を考慮に入れて高くなり、動きの類似性に関するより少ない要求による、この断片のグループ化を可能にする。
【０１２４】
しかしながら、グループ化閾値が、断片Ｆｊの動きの良好なモデル化に後続して、即ちＶａｒｊが低いとき、非常に低いことは可能である。
【０１２５】
この場合、他の断片との断片Ｆｊのグループ化は、グループ化閾値が動きのそのモデルの分散に正比例する場合、ペナルティ（罰金）を課せられ、かかる場合、閾値は低いだろう。
【０１２６】
この状況を回避するために、他の実施例と無関係に使用することができる一実施例では、各グループ化ステップで、各断片Ｆｊの動きをモデル化する分散Ｖａｒ２４ｊの平均のＶａｒｍの推定値が得られ、断片Ｆｊに対するグループ化閾値は、グループ化された断片個別の分散Ｖａｒ２４ｊと平均の分散Ｖａｒｍとの間の最大値ＭＡＸ（Ｖａｒ２４ｊ、Ｖａｒｍ）で固定される。
【０１２７】
経験的に、より良い結果は、０．５＊ＭＡＸ（Ｖａｒ２４ｊ、Ｖａｒｍ）で固定されたグループ化閾値に対して、得られる。
【０１２８】
より明確には、開始断片のすべての対に対して計算されるグループ化コストＣｒｅを最小にする、２つの断片Ｆｉ及びＦｊの間のグループ化を、考慮することができる。
【０１２９】
断片Ｆｉが、例えばピクセルの数の基準により、断片Ｆｊより小さいと考えることによって、グループ化閾値Ｓｒｅは、分散Ｖａｒ２４ｉに依存する許容値で評価される。
【０１３０】
しかしながら、同時に、すべての開始断片の平均の分散Ｖａｒｍが評価される。したがって、このステップの間、各々の分散Ｖａｒ２４１，Ｖａｒ２４２…Ｖａｒ２４ｋのｋ個の断片Ｆ１，Ｆ２…Ｆｋがある場合、以下のようになる。
【０１３１】
【数１６】
0004354146.tif 000024
続いて、この許容値Ｖａｒｍが分散Ｖａｒ２４ｉより高い場合、閾値Ｓｒｅは、Ｖａｒｍの関数として決定されるだろう。したがって、断片Ｆｉのグループ化は、平均”の場合より小さい許容値に支配されない。
【０１３２】
さらに、このグループ化閾値Ｓｒｅは、以前の画像の先行の細分化の関数として評価される。
【０１３３】
特に、独立して使用することができるこの実施例は、色断片化２２に由来する断片Ｆｉと、以前の画像１２ｉの前の細分化に由来する領域Ｒ’ｉとの間の比較オペレーション２６が、次の画像の断片化および画像１２ｉの細分化の間の対応性の助けにより予測することによって、計算を単純化するという、発見に起因する。
【０１３４】
特に、この比較２６によって、処理を受けている画像の断片ＦｉおよびＦｊが、以前に前の画像の中でグループ化された画像のゾーン、即ち同一の領域に対応するかどうかを、決定することが可能である。
【０１３５】
このため、他の実施例と無関係に使用することができる実施例では、これらの断片が再びグループ化されると仮定して、より高いグループ化閾値が、これらの断片を基準として固定され、それにより、それらのグループ化を促進する。
【０１３６】
例えば、この閾値Ｓｒｅは、次のように固定することができる。即ち、Ｓｒｅ＝４＊ＭＡＸ（Ｖａｒ２４ｊ、Ｖａｒｍ）。
【０１３７】
しかしながら、例えば２つの画像間での物体の移動が生じる場合、この仮定は、正しくないことになる。
【０１３８】
この場合、あまりにも高いグループ化閾値は、同じ動きを備えた物体に対応しない断片のグループ化を促進することになる。
【０１３９】
この状況を回避するために、前の画像１２ｊからの断片Ｆｊの輝度の変動に関する条件は、２つの画像間のどんな物体の動きも検知することを可能にして、固定される。
【０１４０】
例えば、この条件は輝度予測の解析により固定することができる。
【０１４１】
例えば、断片Ｆｊ及びパラメータ・モデル２４１に関連付けられた、この輝度予測は、次のように定義される。
【０１４２】
断片Ｆｊの座標（ｘｊ，ｙｊ）を備えた各ピクセルＰで、座標（ｄｘｊ／ｉ，ｄｙｊ／ｉ）を備えたベクトル１５ｐｊ／ｉが、先に説明されたように、計算される。続いて、画像１４ｉのＰ（ｘｊ，ｙｊ）で予測された輝度は、画像１２ｉの（ｘｊ−ｄｘｊ／ｉ，ｙｊ−ｄｙｊ／ｉ）で見いだされる。
【０１４３】
その後、予測エラーは、予測言された輝度と、断片Ｆｊの座標（ｘｊ，ｙｊ）を備えたすべてのピクセルＰの実際の輝度との間の差の平均として定義される。
【０１４４】
そのような輝度予測エラーは、それについてのグループ化の前、及び別の断片とのグループ化の後、該当する断片に関して計算される。併合は、許可されるエラーは前もって定義した解像度に依存しているが、この予測エラーが過度に変化しない場合、受容される。
【０１４５】
この場合、断片ＦｉおよびＦｊの間で対応性が存在すると想定でき、より高いグループ化閾値を適用することができる。
【０１４６】
経験的に、これらの予測間のエラーは７つのグレーレベルの偏差で固定される。
【０１４７】
上記説明を考慮すると、次式によって定義されるようなグループ化コストＣｒｅの計算による停止基準の使用によって、各断片の個々の特性を考慮することが可能になることは、明白である。
【０１４８】
【数１７】
0004354146.tif 000025
さらに、コストＣｒｅに従って可能なグループ化にランクを定義すること、及び、この基準に従って最も類似した断片のグループ化を促進することは、可能である。
【０１４９】
さらに、そのような細分化アルゴリズムのユーザが、例えばピクセルの数Ｎｍｉｎを含む所与のサイズの領域を得ることを、望んでいることが考えられる。
【０１５０】
実際、他の実施例と無関係に使用することができる実施例では、断片の各々グループ化後、この選択を考慮に入れる停止テストが適用される。例えば、断片Ｆｉのピクセルの数ＮｉとＮｍｉｎとの間の最大値Ｎ’ｉ、及び、断片Ｆｊピクセルの数ＮｊとＮｍｉｎとの間の最大値Ｎ’ｊを、呼び出すことによって、次の条件を課す。
【０１５１】
【数１８】
0004354146.tif 000026
続いて、項（Ｎ’ｉ＋Ｎ’ｊ）／（Ｎ’ｉ×Ｎ’ｊ）は、Ｎｍｉｎより小さいサイズの断片のグループ化を促進する。
【０１５２】
しかしながら、この項は、大きなサイズの断片のグループ化に不都合を与える。
【０１５３】
このため、一実施例では、第２のグループ化停止基準が、先に記載されたグループ化停止基準に代替的に使用される。より正確には、次のような第２のグループ化コストＣ’ｒｅが考慮される。
【０１５４】
【数１９】
0004354146.tif 000027
したがって、この第２のグループ化コストの使用によって、動きにおける差がグループ化閾値より小さい断片をグループ化することを可能にする第２の停止基準を考案することは、可能になる。
【０１５５】
例えば、
【０１５６】
【数２０】
0004354146.tif 000028
が停止基準として課される。
【０１５７】
この実施例では、２つの停止基準の使用が、そのサイズに対して断片にペナルティを課さない、画像の細分化を得るような方法で代替される。
【図面の簡単な説明】
【図１】画像の細分化に対する多様なステップが表わす図である。
【符号の説明】
２０    オペレーション
２２    オペレーション
２４    オペレーション
２６    オペレーション
２８    一致
３０    オペレーション
３３    マーキング・オペレーション
【図１】
0004354146.tif 000032