(57)【特許請求の範囲】
【請求項１】
局所的な相対的ｚオーダリング情報を決定する方法であって、
（ａ）デジタル画像データを含む第１の画像フレームと第２の画像フレームとを取得するステップと、
（ｂ）前記第１の画像フレームと前記第２の画像フレームとをセグメントに分割するステップと、
（ｃ）前記第１の画像フレームのセグメントを前記第２の画像フレームに整合させて、前記第２の画像フレームのセグメントを前記第１の画像フレームに整合させるステップと、
（ｄ）画像フレーム間の前記セグメントの相対変位を表す、前記セグメントの相対オフセットを決定するステップと、
（ｅ）前記セグメントが前記セグメント間の相対オフセットだけ移動させられた場合に重なり合うこととなる前記第１の画像フレームまたは前記第２の画像フレームのセグメントを決定するステップと、
（ｆ）前記重なり合うセグメントについて相対的ｚオーダリングを決定するステップと、
（ｇ）前記ｚオーダリングにおいて形成された周期的関係を破断するステップであって、
（ｇ１）前記周期的関係を共有するセグメントのシーケンスを取得し、及び、
（ｇ２）前記周期的関係が破断されるまで、セグメント間の関係のうち最弱な関係を取り消すことを繰り返す
ことによって、該周期的関係を破断するステップ
を含む、方法。
【請求項２】
前記セグメントは、実質的に均一な色の各々であり、複数の幾何学形状及び範囲内において具現化されることからなる、請求項１に記載の方法。
【請求項３】
前記整合させるステップが、フォワードマッチングルーチンか又はバックワードマッチングルーチンを用いて行われ、前記ステップ（ｄ）が、前記重なり合うセグメントの共通の境界を共有する複数の整合されたセグメントの群を決定するステップを含む、請求項１に記載の方法。
【請求項４】
前記第１の画像フレーム内の複数の重なり合うセグメントの各々を前記第２の画像フレーム内の対応する重なり合うセグメントの各々と比較することによって計算された各々の差を表すパラメータから、前記ｚオーダリングが決定される、請求項１に記載の方法。
【請求項５】
前記差が最小のときの前記複数のセグメントの配置関係から前記ｚオーダリングを決定するためのエラー最小化技法が用いられる、請求項４に記載の方法。
【請求項６】
前記セグメント間の関係の強度が、平均エラーの差に基づくことからなる、請求項１に記載の方法。
【請求項７】
前記セグメント間の関係の強度が、任意の適切な統計的パラメータに基づくことからなる、請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
（関連出願の相互参照）
この開示は、下記に関連する。
【０００２】
米国特許第＿＿＿号（「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｓｅｇｍｅｎｔａｔｉｏｎ」という名称の２０００年６月９日に出願された米国特許出願第０９／５９１，４３８号）（以下、「Ｐｒａｋａｓｈ  ＩＩ」）。
【０００３】
米国特許第＿＿＿号（「Ｍｏｔｉｏｎ  Ｍａｔｃｈｉｎｇ  Ｍｅｔｈｏｄ」という名称の２００１年６月２３日に出願されたドケット番号０２０５５４−０００６００ＵＳ）（以下、「Ｐｒａｋａｓｈ  ＶＩＩ」）。
【０００４】
この開示は、下記の優先権を主張する。
【０００５】
「Ｍｅｔｈｏｄ  ｏｆ  Ｄｅｔｅｒｍｉｎｉｎｇ  Ｒｅｌａｔｉｖｅ  Ｚ−Ｏｒｄｅｒｉｎｇ  ｉｎ  ａｎ  Ｉｍａｇｅ  ａｎｄ  Ｍｅｔｈｏｄ  ｏｆ  Ｕｓｉｎｇ  Ｓａｍｅ」という名称の２０００年８月４日に出願された米国仮特許出願第６０／２２３，０５７号。
【０００６】
本明細書中、全ての目的のために、上記のそれぞれの開示を参考として援用する。
【０００７】
（発明の背景）
本発明は、概して、画像処理に関し、具体的には、画像内で発見されるセグメント間の相対的なｚ値の識別、および、デジタル画像処理における相対的なオーバーラップ情報の使用に関する。
【０００８】
本明細書中に開示される解法は、一時的に相互に関連付けられる画像フレームのシーケンスに含まれるｚオーダリング情報（ｚ−ｏｒｄｅｒｉｎｇ  ｉｎｆｏｒｍａｔｉｏｎ）を決定することである。ｚオーダリングは、文字どおりに、「ｚ」または深さの軸によってオーダリングすることを意味する。すなわち、ｚオーダリングは、画像領域が画像フレーム内のどの深さにあるかに基づいて、画像領域を配列またはオーダリングすることを意味する。この慣習において、ｚオーダリングは、閲覧者の観点から測定される。従って、画像領域が離れているほど、または、画像領域が画像フレーム内の深い位置にあるほど、その領域のｚ値は高くなる。
【０００９】
画像の異なる領域のｚオーダ（ｚ−ｏｒｄｅｒ）または深さを決定することは、デジタル画像操作、画像／映像編集、映像圧縮、および種々の他のデジタル画像処理の応用などの用途に非常に有用である。
【００１０】
概して、画像内の異なるオブジェクトのｚオーダを知ることによって、映像フレームを編集または操作することができる。なぜならば、画像の完全性または画像の品質を失うことなく、この画像フレームのシーケンスにオブジェクトを削除または追加することが可能になるからである。現在、一時的に相互に関連付けられる画像シーケンス内の任意のオブジェクトのｚオーダを十分に識別し得る方法は存在しない。
【００１１】
本発明において適用されるｚオーダリングは、全く新しい技術である。現在、人間が介入することなく、デジタル画像フレームの任意に選択されるシーケンスからｚオーダリング情報を決定することを可能にする技術で、広範に利用可能な技術は存在しない。現在のｚオーダリングルーチンは、逆の適用（すなわち、ｚオーダリングを知った後で、画像フレームを描く）に制限される。例えば、図１において、それぞれ雲、太陽、および背景の領域１１〜１３の３つの画像領域が描かれるべきである。雲がｚオーダリング１を有する場合、太陽はｚオーダリング２を有し、背景はｚオーダリング３を有し、画像作成ルーチンは、最初に背景を描き、次いで太陽を描き、最終的に雲を描くことを知っている。
【００１２】
（発明の要旨）
本発明は、画像フレームのシーケンスから、画像フレーム内の画像領域の相対的なｚオーダリングを決定する方法および装置に関する。本発明は、複数のフレームによって、画像領域の隠れた部分のいくつかの部分が可視になり得、従って、異なる画像領域の相対的なｚオーダが可能になることを理解することによって作動する。本発明の基本原理は、特定の画像フレームのオーバーラップする２つ以上の画像領域を、オーバーラップしない異なる画像フレームの同じ画像領域と比較することによって、画像領域の相対的なｚオーダリングを決定することが可能であることである。これは、図２ａおよび２ｂに示される。図２ａを参照して、画像領域２１および２２の印がそれぞれ付いている２つの任意の画像領域がある。図２ａだけでは、どの画像領域が他の画像領域を塞いでいる（ｏｃｃｌｕｄｉｎｇ）かを決定するのに十分な情報が含まれていない。図２ｂを参照して、塞がれていない完全な画像領域２１および２２が第２の画像フレームに示される。図２ａにおいて、画像領域２１が画像領域２２を部分的に塞いでいたことが明らかである。
【００１３】
（特定の実施形態の説明）
例示的な図（同様の参照符号は、図に共通して、同様のまたは対応する要素を示す）を参照して、本発明によるシステムの実施形態について詳細に説明する。本明細書中、用語「セグメント」および「領域」が、区別なく使用されることに留意されたい。
【００１４】
図３は、本明細書において説明される発明による全体のフローチャートを示す。ステップ３１０において、本発明によって、映像データを含む第１および第２の画像フレームが得られる。ステップ３２０において、本発明によって、第１および第２の画像フレームの両方から画像領域が得られる。本発明の一実施形態において、任意の他の実施形態を制限することなく、画像領域はセグメントである。
【００１５】
ステップ３３０において、第１および第２の画像フレームの対応する画像領域を決定するために、画像領域のモーションマッチング（ｍｏｔｉｏｎ  ｍａｔｃｈｉｎｇ）が行われる。ステップ３４０は、任意のフレーム１画像領域が潜在的にオーバーラップするかどうかを決定する。ステップ３５０は、任意のオーバーラップする画像領域間の対ごと（ｐａｉｒｗｉｓｅ）の関係を決定する。ステップ３６０において、任意の周期的関係が破断される。本発明は、ステップ３９９において終了する。
【００１６】
（モーションマッチング）
図４は、隠れた画像領域の構造を決定するためにモーションマッチングが用いられる方法を示す。モーションマッチングは、画像フレームのコレクションから、画像フレーム内のどの画像領域が所定の画像領域に最もよく似ているかを決定するプロセスである。本発明は、種々の画像領域の隠れた部分の構造を決定するためにモーションマッチングを用いる。
【００１７】
図４ａは、それぞれに画像領域４１、４２、および４３の印が付いている太陽、雲、および背景の３つの画像領域を含む。太陽は、雲の後ろに部分的に隠れている。図４ｂも、それぞれに画像領域４４、４５、および４６の印が付いている太陽、雲、および背景の３つ画像領域を含む。図４ｂにおいて、図４ａとは違い、太陽は完全に可視である。すなわち、太陽は雲によって塞がれていない。
【００１８】
本発明は、マッチングルーチンを適用し、画像領域４１（図４ａにおける太陽）が画像領域４４（図４ｂにおける太陽）と一致することを決定する。本発明は、一旦この決定を下すと、画像領域４１の構造のより多くの部分（すなわち、部分的に隠れた太陽）を決定し得る。なぜならば、画像領域４１および画像領域４４は、同じピクセルのコレクションを表すからである。画像領域４１の隠れた不明の部分は、画像領域４４の対応する可視部分と同一である。従って、画像領域４４の以前に不明だった部分の少なくともいくつかの部分（すなわち、画像領域の新しく可視になる部分）は、モーションマッチングを用いることによって決定される。
【００１９】
さらに、この原理は、図４ｂの太陽（画像領域４２）が部分的に塞がれたままである場合であっても適用される。例えば、図５において、それぞれに画像領域５１〜５３の印が付いている太陽、雲、および背景の３つの画像領域がある。図示のように、太陽は、図４ａより隠れていないが、雲の後ろに部分的に隠れている。モーションマッチングルーチンを適用することによって、画像領域４１が画像領域５１と一致する。この場合も、画像領域４１の隠れた不明の部分は、画像領域５１の対応する可視部分と同一である。
【００２０】
（フォワードモーションマッチング）
図６は、最も従来的なモーションマッチングルーチンの制限を示す。具体的には、画像領域が実質的に同じままである状況、または、画像領域がより少なく塞がれている（すなわち、任意の可視部分を塞ぐことなく、画像領域の以前に隠れていた部分の一部分が可視になる）状況に制限される。他の全ての状況は、多くのモーションマッチングルーチンを混乱させる。これは、モーションマッチングルーチンが、画像領域の新しく隠れた部分にアクセスできないからである。
【００２１】
図６ａは、それぞれに画像領域６１〜６３の印が付いている太陽、雲、および背景の３つの画像領域を含む。図６ｂは、太陽、雲、および背景の３つの画像領域を含む。図６ａとは違い、図６ｂにおいて、雲は部分的に太陽を遮っている。概念上、画像領域６４（図６ｂにおける太陽）を、２つの画像サブ領域（可視部分をサブ領域６４ａ、隠れた部分をサブ領域６４ｂ）として考えると便利である。サブ領域は、画像領域の任意のサブセットである。同様に、画像領域６１（図６ａにおける太陽）は、それぞれがサブ領域６４ａおよび６４ｂに対応するサブ領域６１ａおよび６１ｂを含むと考えられ得る。線６１０は、サブ領域６１ａおよび６１ｂの間の概念上の分離を意味する。
【００２２】
マッチングルーチンは、サブ領域６１ａのピクセル値をサブ領域６４ａのピクセル値と一致させ得る。しかし、画像領域６１の残りのピクセル値（すなわち、サブ領域６１ｂ）は、画像領域６４の残りのピクセル値（すなわち、サブ領域６４ｂ）が隠れていて、従って、マッチングルーチンによってアクセスできないため、これらのピクセル値と一致しない。
【００２３】
サブ領域６４ｂのピクセル値がマッチングルーチンによってアクセスできない結果として、多くのモーションマッチングルーチンは、画像領域６１および６４の一致を認めない。
【００２４】
数学的には、従来のモーションマッチングルーチンは、フレーム１の領域を図２の領域のサブセット（すなわち、より小さい部分）と一致させない。
【００２５】
（バックワードモーションマッチング）
図７は、モーションマッチングの別の用途を示す。上記のように、モーションマッチングルーチンのフォワードアプリケーションは、画像領域を同じ画像領域のサブセットと一致させない。しかし、その逆は当てはまらない。多くのモーションマッチングルーチンは、画像領域を画像領域のスーパーセットと一致させる。本明細書中、画像領域のスーパーセットは、少なくとも第１の画像領域の全てのピクセルを含む画像領域を指す。
【００２６】
それぞれに画像領域７１〜７３の印が付いている太陽、山、および背景の３つの画像領域を含む図７ａを参照して、昇る太陽（画像領域７１）は、山の後ろに部分的に隠れている。同様に、図７ｂも、昇る太陽、山、および背景の領域７４〜７６の３つの画像領域を含む。昇る太陽は、もはや、雲の後ろに隠れていない。
【００２７】
図７ａの部分的に隠れている太陽は、２つの画像サブ領域（可視部分をサブ領域７１ａ、隠れた部分をサブ領域７１ｂ）として考えられ得る。マッチングルーチンによって、図７ｂの画像領域７１との一致を発見しようとすると、サブ領域７１ａのピクセルしか考慮され得ない。なぜならば、サブ領域７１ｂのピクセルが隠れていて、従って、考慮されないからである。この例において、サブ領域７１ａの各ピクセルは、領域７４に対応するピクセルを有し、従って、一致が発見される。
【００２８】
（バックワードモーションマッチングの適用）
１実施形態において、本発明は、整合ルーチンを逆方向に適用する。すなわち、フレーム１における画像領域からフレーム２における画像領域に整合させる代わりに、本発明は、画像をフレーム２から受け取り、この画像をフレーム１における画像領域と整合させる。
【００２９】
逆方向整合工程は、図６ａおよび図６ｂに示されるように、最大モーションマッチングアルゴリズム（ｍｏｓｔ  ｍｏｔｉｏｎ  ｍａｔｃｈｉｎｇ  ａｌｇｏｒｉｔｈｍｓ）が、画像領域を画像領域のサブセットと整合させないという事実を利用する。しかしながら、図７ａおよび図７ｂに示されるように、最大モーションマッチングアルゴリズムは、画像領域を、同じ画像領域のスーパーセットと整合させる。
【００３０】
画像領域が１つのフレームから次のフレームに移動すると、画像は、より多く隠される（ｏｃｃｌｕｄｅｄ）か、より少なく隠されるか、または同じ状態でとどまる。より多く隠された画像領域は、フォーワードモーションマッチング方法を用いて整合され得ないので、これらの画像領域は、バックワードマッチングを用いて整合されなければならない。少なく隠されるか、または同じ状態でとどまる画像領域は、フォワードマッチングを用いて整合され得る。
【００３１】
従って、フォワードモーションマッチングルーチンが、フレーム２においてより多く隠されない画像領域を識別した後、本発明は、バックワードモーションマッチングを用いて、残りの画像領域を整合させる。
【００３２】
例えば、図８に見出され得るように、４つの画像領域が存在する。領域８１〜８４とそれぞれ示された、これらの画像領域は、雲、太陽、山、および背景である。フレーム１（Ｆｒａｍｅ１）において、太陽のみが部分的に隠される。しかしながら、フレーム２（Ｆｒａｍｅ２）において、太陽は、もはや隠されないが、雲が隠される。フォワードモーションマッチングは、両方のフレームにおいて山を整合させ、山が変化しない状態であるようにする。さらに、太陽が整合され、フレーム１における太陽がフレーム２における太陽のサブセットであるようにする。すなわち、太陽は、フレーム２において少なく隠された。しかしながら、雲は整合されない。
【００３３】
バックワードマッチングは、フレーム２における整合されない雲をフレーム１における画像領域と整合させることを試みる。フレーム２の雲は、フレーム１の雲のサブセットであるので、逆方向に適応された整合ルーチンは、整合相手として雲を示す。
【００３４】
（マッチングのフローチャート）
図９を参照して、ステップ９１０にて、本発明は、フレーム１において画像領域を決定する。同様に、ステップ９２０にて、フレーム２の画像領域が決定される。ステップ９３０にて、フレーム１からの画像領域が選択され、ステップ９４０にて、従来の整合ルーチンが適用される。ステップ９５０にて、整合された後、本発明は、整合されるべきフレーム１の任意のさらなる画像領域があるか否かを決定する。さらなる画像領域がある場合、ルーチンはステップ９３０に進む。さらなる画像領域がない場合、本発明は、ステップ９６０にて続行し、ここで、整合されないフレーム２の画像領域が選択される。新しい整合ルーチンは、ステップ９７０にて、逆方向に適用される。ステップ９８０にて、本発明は、整合されないフレーム２の任意のさらなる画像領域があるか否かを決定する。さらなる画像領域がある場合、本発明は、ステップ９６０に進み、ない場合、本発明は、ステップ９９９にて続行する。
【００３５】
（エラー最小化）
図１０は、エラー最小化の方法を示す。画像領域が一度整合されると、本発明は、エラー最小化として公知の手順を用いて、ｚオーダリング情報を計算する。エラー最小化は、本発明が、同じ画像フレーム内で重なり合う画像領域の収集が与えられた、重なり合う２つの画像領域を考察し、２つの画像領域のうちのどちらが、もう一方の画像領域を部分的に隠すのかを決定する工程である。これは、２つの画像領域間に対ごと（ｐａｉｒｗｉｓｅ）の関係をもたらす。この慣例において、隠す画像領域は、隠された画像領域よりも低いｚオーダリング（ｚ−ｏｒｄｅｒ）を有する。エラー最小化は、重なり合う画像領域の収集内の重なり合う画像領域の各対に適用される。目的は、対ごとの関係のシーケンスを生成することである。これらの対ごとの関係は、過渡的または周期的関係を形成し得る。
【００３６】
重なり合う画像領域の収集の対ごとの関係が、過渡的関係を形成する場合、画像領域のｚオーダリングは、過渡的関係と同じである。過渡的関係は、対ごとのオーダリングの全部が決定された後、領域のすべてがｚ軸に沿ってオーダリングされ、相対深さが割り当てられ得る関係である。例えば、図１０ａにおいて、対ごとの関係が、画像領域１０２は１０３の上方にあり、１０３は、１０１の上方にあり、１０２は１０１の上方にあることを決定した場合、１０２が１０３の上にあり、１０３が１０１の上にあることを決定することが可能である。これは、過渡的関係であると考えられる。逆に、対ごとの関係は、１０２が１０３の上方にあり、１０３が１０１の上方にあり、１０１が１０２の上方にあることを決定した場合、この関係は、周期的関係を生成する。なぜなら、これらの領域をｚ軸に沿ってオーダリングすることは不可能だからである。このような周期的関係が生じた場合、正確なｚオーダリングは決定され得ない。周期的破断（ｂｒｅａｋｉｎｇ）と呼ばれる方法は、画像領域の収集のｚオーダリングを決定する工程を含む。周期的破断の方法は、後節にて詳細に説明される。
【００３７】
上述のように、図１０ａにおいて、それぞれ領域１０１、１０２および１０３と表示された背景、三角形および四角形の３つの画像領域があり、これらの各々は、２つのフレーム（Ｆｒａｍｅ１、Ｆｒａｍｅ２）間のこれらのセグメントの相対動作によって決定された共通のピクセルを共有する。対ごとの関係を決定するために、ルーチンは、共通のピクセルを共有する２つの画像領域を選択する。このルーチンは、第１の画像領域を第２の画像上に配置した結果を計算し、第２の画像領域を第１の画像上に配置する。結果として生じた２つの画像は、元の画像と比較され、より良好な整合が対ごとの関係を決定する。１実施形態において、整合は、結果として生じた２つの画像を元の画像ピクセルとピクセルによって比較することによって、および２つの画像間の最低平均エラーを計算することによって決定される。本発明の他の実施形態において、任意の他の統計的パラメータが、最良の整合を決定するための基準として用いられ得る。本発明は、さらに、２つの画像領域を比較することに限定されない。本発明は、任意の数の画像領域を同時に考察し得る。
【００３８】
図１０ｂにおいて、本発明は、領域１０１および１０２を用いて開始し、領域１０２上に配置された領域１０１を含む画像フレームを生成する。図１０ｂ、図１０ｃ、図１０ｄおよび図１０ｅにおいて、範囲１０４は、図１０ａフレーム１から三角形１０２および矩形１０３を除去することによる空白またはホール（ｈｏｌｅ）である。図１０に図示する目的で、すべての後続ステップは、他のすべての領域が除去された背景が、依然として、それ自体と整合され得ることを想定する。１０１の下から見える三角形１０２の小さい部分は、１０２ａと表示される。次の画像は、領域１０１上に描かれた領域１０２であり、図１０ｃに示されたように、背景にて三角形を生成する。領域１０１上の領域１０２は、より良好な整合であり、領域１０２は領域１０１よりも低いｚオーダリングを有する。
【００３９】
次に、本発明は、領域１０１と１０３とを比較する。図１０ｄは、領域１０３（四角形）上に領域１０１（背景）が描かれた結果を示す。これは、１０４と表示された上述のホールおよび下から見える１０３の部分を含む領域１０１を生成する。逆に、図１０ｅは、領域１０１上に描かれた領域１０３が図１０ａとより近い整合である四角形および背景を生成することを示す。従って、領域１０３は、領域１０１よりも低いｚオーダリングを有する。
【００４０】
残りのすべては、領域１０２と領域１０３との間の対ごとの関係を決定する。本発明は、領域１０３上に配置された領域１０２の画像を生成し、これは図１０ｆに見出され得る結果をもたらす。さらに、本発明は、領域１０２上に配置された領域１０３の画像（図１０ｇ）を生成する。領域１０３上の領域１０２は、第１のフレームとのより良好な整合を生成し、従って、領域１０２は、領域１０３よりも低いｚオーダリングを有する。３つの画像領域をまとめて、領域１０２は、領域１０１よりも低いｚオーダリングを有する領域１０３よりも低いｚオーダリングを有することが決定され得る。この関係は、過渡的関係であるので、領域１０２が、領域１０１を隠す領域１０３を隠し、ｚオーダリングが決定される。
【００４１】
図１１を参照して、ステップ１１１０にて、本発明は、重なり合う画像領域の群を考察する。重なり合う２つの画像領域が１１２０にて選択される。ステップ１１３０にて、ルーチンは、エラー最小化を適用する。すなわち、第１の画像領域を第２の画像領域上に配置する工程は、第２の画像領域を第１の画像領域上に配置する工程よりも、元の画像と、より近い整合であるかどうかを決定する工程である。ステップ１１４０は、ステップ１１３０の結果を用いて、２つの画像領域間の対ごとの関係を生成する。ステップ１１５０は、重なり合う任意のさらなる画像領域があるか否かを照会し、さらなる画像領域がある場合、本発明は、ステップ１１２０へと飛び越える。さらなる画像領域がない場合、ステップ１１６０にて続行する。ステップ１１６０は、対ごとの関係が周期的関係を形成したか否かを照会する（６節にて十分に説明された）。ステップ１１７０にて、周期的関係を形成する場合、図１５における周期的破断ルーチンが実行される。周期的関係を形成しない場合、ルーチンはステップ１１８０にて続行する。ルーチンは、対ごとの関係を用いて、ｚオーダリングを生成する。ステップ１１９０にて、本発明は、重なり合う画像領域の任意のさらなる群があるか否かを決定する。さらなる群がある場合、ルーチンは、ステップ１１１０へと飛び越え、続行する。さらなる群がない場合、本発明は、ステップ１１９９にて停止する。
【００４２】
（周期破断）
上述のように、概して言うと、重なり合う画像領域の群間の対ごとの関係を決定する工程は、画像領域のｚオーダリングを決定するために十分である。一般に、対ごとの関係は、図１２に見出されるように、過渡的関係を決定する。領域１２１が領域１２２上にある場合、領域１２２が領域１２３上にあり、従って、領域１２１も領域１２３上にあることがわかる。
【００４３】
しかしながら、時には、図１３における状態が生じる。図１３は、示されるように、３つの画像領域を表す。領域１３１はライトグレーの円形、領域１３２はダークブラックの円形、領域１３３はミディアムグレーの円形である。本図示のために、背景は無視される。なぜなら、背景を含むことは、内容を不必要に複雑にするだけだからである。
【００４４】
整合ルーチンおよびエラー最小化アルゴリズムを適用した後、結果は、次の対ごとの関係（図１３ｂ〜図１３ｇを参照）である。すなわち、画像領域１３１は領域１３２上にあり、領域１３２は領域１３３上にあり、領域１３３は領域１３１上にある。従って、画像領域は、図１３ａに見出されるように、周期的関係を有する。
【００４５】
この周期的関係を過渡的関係に変更し、ｚオーダリングが取得され得るように、ルーチンは、対ごとの関係のうちのどれが最弱かを決定する。第１の画像領域を第２の画像領域上に配置する工程、およびこの対と元の画像との間の平均エラーを計算する工程が、第２の画像を第１の画像上に配置し、この対と、元の画像内の対応する領域の対との間の平均エラーを計算する工程と同じ値になる場合、対ごとの関係は弱いと考えられる。換言すると、２つの平均エラー間の差が小さい場合、対ごとの関係は弱いと考えられる。従って、関係を取り消す工程は、最終的な画像を著しく変更しない。本発明は、周期的関係が解消されるまで、最弱で開始する対ごとの関係を取り消す。図１３において、画像領域１３３と画像領域１３１との間の対ごとの関係は最弱である。結果として生じた対ごとの関係は、領域１３２上の領域１３１、領域１３３上の領域１３２である。従って、過渡的関係が形成され、領域１３１がビュアに最も近い、すなわち、最低のｚオーダリングを有し、領域１３２はより深く、より高いｚオーダリングを有し、領域１３３はさらに深く、最高のｚオーダリングを有することがわかる。図１４は、結果として生じた画像を示す。これは、図１３とほぼ同一である。
【００４６】
図１５を参照して、ステップ１５１０にて、本発明は、周期的関係を有する画像領域の群を考察する。ステップ１５２０にて、本発明は、どの対ごとの関係が最弱かを決定する。ステップ１５３０は、関係を取り消す。
【００４７】
ステップ１５４０にて、本発明は、周期的関係が破断されたか否かを決定する。はいである場合、本発明は、ステップ１５９９にて戻る。いいえである場合、本発明は、ステップ１５２０に戻り、すべての周期的関係が破断されるまで、次の際弱の対ごとの関係を考察する。
【図面の簡単な説明】
【図１】    図１は、既知の相対的なｚオーダを有する３つのオブジェクトを含む画像フレームである。
【図２ａ】    図２ａは、２つのオーバーラップする領域を含む画像フレームである。
【図２ｂ】    図２ｂは、２つの領域がオーバーラップしなくなった画像フレームである。
【図３】    図３は、ｚオーダーリングプロセスのフローチャートである。
【図４ａ】    図４ａは、隠れたセグメントの構造を決定するためにモーションマッチングが用いられる方法を示す。
【図４ｂ】    図４ｂは、隠れたセグメントの構造を決定するためにモーションマッチングが用いられる方法を示す。
【図５】    図５は、２つのセグメントのいくつかの部分がオーバーラップする場合においても、モーションマッチングが効果的であることを示す。
【図６ａ】    図６ａは、図６ｂと合わせて、従来のモーションマッチングルーチンが、部分的に塞がれている特定の領域を識別できない場合の一連の２つの画像フレームを示す。
【図６ｂ】    図６ｂは、図６ａと合わせて、従来のモーションマッチングルーチンが、部分的に塞がれている特定の領域を識別できない場合の一連の２つの画像フレームを示す。
【図７ａ】    図７ａは、図７ｂと合わせて、従来のモーションマッチングルーチンが、特定の領域を識別することに成功する場合の一連の２つの画像フレームを示す。
【図７ｂ】    図７ｂは、図７ａと合わせて、従来のモーションマッチングルーチンが、特定の領域を識別することに成功する場合の一連の２つの画像フレームを示す。
【図８】    図８は、背景モーションマッチングが適用されるべき２つの画像フレームのシーケンスである。
【図９】    図９は、フォワードならびにフォワードおよびバックワードモーションマッチングのフローチャートである。
【図１０ａ】    図１０ａは、領域（セグメント）を対ごとに比較するプロセスを示す。
【図１０ｂ】    図１０ｂは、領域（セグメント）を対ごとに比較するプロセスを示す。
【図１０ｃ】    図１０ｃは、領域（セグメント）を対ごとに比較するプロセスを示す。
【図１０ｄ】    図１０ｄは、領域（セグメント）を対ごとに比較するプロセスを示す。
【図１０ｅ】    図１０ｅは、領域（セグメント）を対ごとに比較するプロセスを示す。
【図１０ｆ】    図１０ｆは、領域（セグメント）を対ごとに比較するプロセスを示す。
【図１０ｇ】    図１０ｇは、領域（セグメント）を対ごとに比較するプロセスを示す。
【図１１】    図１１は、エラー最小化のプロセスのフローチャートである。
【図１２】    図１２は、過渡的関係を示す。
【図１３ａ】    図１３ａは、周期的破断（ｃｙｃｌｅ  ｂｒｅａｋｉｎｇ）を示す。
【図１３ｂ】    図１３ｂは、周期的破断を示す。
【図１３ｃ】    図１３ｃは、周期的破断を示す。
【図１３ｄ】    図１３ｄは、周期的破断を示す。
【図１３ｅ】    図１３ｅは、周期的破断を示す。
【図１３ｆ】    図１３ｆは、周期的破断を示す。
【図１３ｇ】    図１３ｇは、周期的破断を示す。
【図１４】    図１４は、周期的破断後の過渡的関係の回復を示す。
【図１５】    図１５は、周期的破断のフローチャートである。
【図１】
0004698926.tif 000002
【図２ａ】
0004698926.tif 000003
【図２ｂ】
0004698926.tif 000004
【図３】
0004698926.tif 000005
【図４ａ】
0004698926.tif 000006
【図４ｂ】
0004698926.tif 000007
【図５】
0004698926.tif 000008
【図６ａ】
0004698926.tif 000009
【図６ｂ】
0004698926.tif 000010
【図７ａ】
0004698926.tif 000011
【図７ｂ】
0004698926.tif 000012
【図８ａ】
0004698926.tif 000013
【図８ｂ】
0004698926.tif 000014
【図９】
0004698926.tif 000015
【図１０ａ（１）】
0004698926.tif 000016
【図１０ａ（２）】
0004698926.tif 000017
【図１０ｂ】
0004698926.tif 000018
【図１０ｃ】
0004698926.tif 000019
【図１０ｄ】
0004698926.tif 000020
【図１０ｅ】
0004698926.tif 000021
【図１０ｆ】
0004698926.tif 000022
【図１０ｇ】
0004698926.tif 000023
【図１１】
0004698926.tif 000024
【図１２】
0004698926.tif 000025
【図１３ａ】
0004698926.tif 000026
【図１３ｂ】
0004698926.tif 000027
【図１３ｃ】
0004698926.tif 000028
【図１３ｄ】
0004698926.tif 000029
【図１３ｅ】
0004698926.tif 000030
【図１３ｆ】
0004698926.tif 000031
【図１３ｇ】
0004698926.tif 000032
【図１４】
0004698926.tif 000033
【図１５】
0004698926.tif 000034