(57)【要約】【課題】特に像軌跡の場合に、動きを表現する正確度を向上させることである。【解決手段】一連の画像に現れる物体の動きを表現する方法は、各画像について、物体の場所を表す代表点のセットを導き出すステップと、上記一連の画像の中の２枚以上の画像における代表点の軌跡を表す近似関数を導き出すステップと、画像の代表点について、上記近似関数の誤差値を算出するステップとを含み、誤差値は、代表点によって表される物体の面積と、代表点が各近似関数値で置き換えられた物体の面積との差分に基づくことを特徴とする。【選択図】図８
2004158014.tif 000002
【特許請求の範囲】
【請求項１】
各画像について、物体の場所を表す代表点のセットを導き出すステップと、
一連の画像の中の２枚以上の画像における代表点の軌跡を表す近似関数を導き出すステップと、
画像の代表点について、前記近似関数の誤差値を算出するステップと
を含む一連の画像に現れる物体の動きを表現する方法において、
前記誤差値は、前記代表点によって表される物体の面積と、前記代表点が各近似関数値で置き換えられた物体の面積との変化に基づく
ことを特徴とする、一連の画像に現れる物体の動きを表現する方法。
【請求項２】
前記誤差値は、画像の面積の変化に基づく
請求項１記載の一連の画像に現れる物体の動きを表現する方法。
【請求項３】
前記誤差値は、複数の画像の面積の変化に基づく
請求項１記載の一連の画像に現れる物体の動きを表現する方法。
【請求項４】
関数近似は、代表点の各座標毎に導き出される
請求項１から請求項３までのいずれかに記載の一連の画像に現れる物体の動きを表現する方法。
【請求項５】
関数近似は、各代表点毎に導き出される
請求項１から請求項４までのいずれかに記載の一連の画像に現れる物体の動きを表現する方法。
【請求項６】
関数近似は、代表点に対して独立して行われる
請求項１から請求項５までのいずれかに記載の一連の画像に現れる物体の動きを表現する方法。
【請求項７】
関数近似は、２つ以上の頂点に対してまとめて行われる
請求項１から請求項５までのいずれかに記載の一連の画像に現れる物体の動きを表現する方法。
【請求項８】
画像の前記誤差値は、代表点が関数近似値で置き換えられた変更後の前記物体の輪郭線内にあるが、元の輪郭線内にはないピクセルの数、および前記元の輪郭線内にはあるが、前記変更後の輪郭線内にはないピクセルの数の関数に基づく
請求項１から請求項７までのいずれかに記載の一連の画像に現れる物体の動きを表現する方法。
【請求項９】
一連の画像中の画像における物体の選択を識別する方法であって、
前記物体の動きは、請求項１から請求項８までのいずれかに記載の一連の画像に現れる物体の動きを表現する方法を用いて導き出された表現を有し、
前記画像の選択された領域を識別するステップと、
動き記述子を使用して前記画像中の前記物体の場所を求めるステップと、
前記物体の場所を前記選択された領域と比較して、前記物体が選択されているか否かを判定するステップと
を含む一連の画像中の画像における物体の選択を識別する方法。
【請求項１０】
画像に対応する信号を処理することによって一連の画像を探索する方法であって、
物体移動クエリを入力するステップと、
前記物体移動クエリの表現を導き出すステップと、
前記表現を、請求項１から請求項８までのいずれかに記載の一連の画像に現れる物体の動きを表現する方法を用いて導き出された表現と比較するステップと、
前記表現が前記クエリとある程度の類似度を示す一連の画像を選択して表示するステップと
を含む画像に対応する信号を処理することによって一連の画像を探索する方法。
【請求項１１】
請求項１から請求項１０までのいずれかに記載の方法を実施するように適合された装置。
【請求項１２】
請求項１から請求項１０までのいずれかに記載の方法を実行させるためのコンピュータプログラム。
【請求項１３】
請求項１から請求項１０までのいずれかに記載の方法に従って動作するようにプログラムされたコンピュータシステム。
【請求項１４】
請求項１から請求項１０までのいずれかに記載の方法を実行させるためのコンピュータ実行可能プロセスステップを記録した、または請求項１２に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１５】
請求項１から請求項８までのいずれかに記載の一連の画像に現れる物体の動きを表現する方法によって導き出される一連の画像における物体の動き記述子。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一連の画像に現れる移動物体を表す改良された方法および装置に関する。
【背景技術】
【０００２】
画像または一連の画像における物体の表現を導き出す様々な技法が知られている。このような表現は、たとえば、探索・検索目的のために画像にインデックスを付与するにあたって有用である。主観的であり、かつ労働集約的なテキストベースのインデックス付与の後には、色、形状、および輪郭線等、物体の固有の属性に基づくインデックス付与が続けられた。さらに進んだ発展は、一連の画像における物体の動きを表現することであった。このような表現の非常に重要な側面は、導入される近似誤差を最小化しながら、必要な帯域幅および記憶領域を最小化する効率的な符号化である。
【０００３】
動きを表現する第１の既知の技法は、パラメータ軌跡（parameter trajectory)として知られている。この技法では、物体全体の動きが、回転および平行移動等、１つまたは複数のパラメータを使用して表現される。たとえば、フレーム中の頂点と基準フレーム中の頂点の間の置換ベクトルが導き出され、これを使用して、アフィン変換移動等、既知の動きモデルの式を解く。この技法により比較的コンパクトな表現が生成されるが、この技法は剛体物体、および動きモデル（たとえば、アフィン変換）がわかっている場合に制限される。
【０００４】
動きを表現する別の既知の技法は、像軌跡（figure trajectory）として知られている。この技法では、物体の動きが、いくつかの代表点それぞれの軌跡により独立して表現される。より具体的には、各代表点の座標が一連のフレームを通してトラッキングされ、各代表点の各座標の軌跡を近似する関数が導き出される。関数近似は、一次近似、二次近似、またはスプライン関数近似等、既知の技法を用いて行われる。像軌跡は、未知の、かつ／または複雑な動きを有する剛体物体の動きを含め、様々な種類の動きに使用することが可能である。
【０００５】
両方の技術において、物体が比較的複雑な輪郭線を有する場合、より複雑な物体の輪郭線を近似した矩形、楕円、または多角形等の参照領域でこの物体を表現することができる。多角形の場合、代表点は頂点であることができる。同様に、矩形の場合、代表点は４つの頂点のうちの３つに制限されうる。これは、４番目の頂点の位置は、その他の３つの頂点の位置から算出することができるためである。楕円の場合、矩形に外接する３つの頂点を代表点として選択することができる。
【０００６】
上に概説した像軌跡およびパラメータ軌跡に類似する一連の画像における物体の動きを表現する方法が開示されている（例えば、特許文献１及び特許文献２参照）。特許文献２及び特許文献１それぞれには、物体の代表領域をどのように導き出すか（多角形近似アルゴリズム）およびフレーム中の代表点をどのように別のフレーム中の代表点と関連付けるか（対応決定アルゴリズム）についてもより詳細に開示されている。
【０００７】
像軌跡では、時空的補間アルゴリズムとして知られている関数近似は、抽出誤差しきい値（ＥＥＴ）が所定のしきい値よりも大きくなるまで、近似関数の間隔を延長することを含む。
【０００８】
このアルゴリズムでは、補間の初期値は最初の２つの点に設定される。次に、補間を広げて一度に１点ずつ追加していき、ついに補間のＥＥＴが予め規定されたしきい値よりも大きくなる。その点で、新しい補間間隔が開始される。この手順はすべての点が処理されるまで繰り返される。補間モデルが変数値と良好にマッチングした場合、このアルゴリズムにより少数の長い補間間隔が得られる。反対に、マッチングが不良の場合、多数の短い補間間隔が得られることになる。
【０００９】
このアルゴリズムについて正しく説明するため、以下の表記を定義する。ｄ（＞０）を変数（次元）の数とし、時間ｔでのｊ番目の変数の値をｖt(j)（ｊ＝１，２，・・・，ｄ）で表す。一続きの時間点をｔi（ｉ＝０，１，・・・）で表す。（候補）補間間隔についての開始時間（終了時間）をｔSTART（ｔEND）で表す。ｆtSTART,tEND(j)（ｔ）（ｊ＝１，２，・・・，ｄ）をｊ番目の変数補間関数の候補とする。これは、最小二乗法を用いて算出することができる。この場合、ｆtSTART,tEND(j)（ｔ）は、次の式を最小化するように算出される。
【００１０】
【数１】
2004158014.tif 000003
【００１１】
ここで補間関数は一次または二次の多項式である。導き出された候補関数を評価するために、Ｔjをｊ番目の変数のしきい値とし、誤差ｅ(j)（ｊ＝１，２，・・・，ｄ）を、次の式のように定義する。
【００１２】
【数２】
2004158014.tif 000004
【００１３】
ｅ(j)は、範囲ｔSTART≦ｔi≦ｔENDのｊ番目の変数の最大近似誤差である。ｅ(j)＜Ｔjがすべてのｊについて当てはまる場合、ｆta,tb(j)（ｔ）は許容可能な候補である。しかし、より広い間隔で別の補間関数が見つかりうる。この可能性をテストしようとするため、ＥＮＤを増分することによって間隔を広げ、新しい関数を導き出してテストする。この手順は、新たに導き出される関数が容認条件を満たすまで繰り返される。次に、最後の候補関数が許容される。
【００１４】
同様の技法が、特許文献１に開示されている。
【００１５】
【特許文献１】米国特許出願公開第２００１／００４０９２４号明細書
【特許文献２】米国特許出願公開第２００１／００２５２９８号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明の目的は、特に像軌跡の場合に、動きを表現する正確度を向上させることである。
【課題を解決するための手段】
【００１７】
したがって、本発明は、画像に対応する信号を処理することによって一連の画像に現れる物体の動きを表現する方法であって、各画像について、物体の場所を表す代表点のセットを導き出すこと、上記一連の画像の中の２枚以上の画像における代表点の軌跡を表す近似関数を導き出すこと、画像の代表点の上記近似関数の誤差値を算出することとを含み、誤差値が、代表点によって表される物体の面積と代表点が各近似関数値で置き換えられた物体の面積との差分に基づくことを特徴とする、物体の動きを表現する方法を提供する。
【００１８】
画像のセットを通しての各代表点の全体的な軌跡が、近似関数または近似関数のセットによって表現され、誤差値を使用して、それぞれの開始点および終了点を含むこれら近似関数を求める。
【００１９】
近似関数は、一連の画像を通しての物体の動きについての記述子を形成するために使用される。したがって、一連の画像中の任意の画像の物体記述子を補間することができる。
【００２０】
たとえば、代表点は、物体の輪郭線を近似する多角形、矩形、楕円等の像の頂点であることができる。好ましくは、本方法は、一連の画像における代表点間の対応を導き出すステップを含む。
【００２１】
本発明により、改良された、より正確な物体移動の表現を導き出すことができる。
【００２２】
本発明の実施形態について、添付図面を参照して述べる。
【発明を実施するための最良の形態】
【００２３】
図１は、本発明の一実施形態によるコンピュータ化されたビデオデータベースシステムを示す。システムは、コンピュータからなる制御ユニット２と、モニタからなる表示ユニット４と、マウスからなるポインティングデバイス６と、動画像（以下、ビデオと記す）を構成する一連の画像が格納されたビデオデータベース８と、ビデオデータベース（画像データベース）８に格納されている画像に現れる物体のまたは物体の部分についての記述子を格納した記述子データベース１０とを備える。
【００２４】
ビデオデータベース中の画像および画像に現れる物体の記述子は、制御ユニット２によって導き出され、記述子データベース１０に格納される。制御ユニット２は、適切なプログラムの制御下で動作して記述子を導き出す。当該技術分野の他のどこかに述べられている画像中の物体の色、形状、および輪郭線の記述子等、多くの種類の記述子が既知であり、使用することが可能である。本実施形態の記述子は、ビデオ中の物体の動き記述子の導出に焦点を合わせる。
【００２５】
本実施形態の技法は、上に述べた像軌跡に基づくものであり、像軌跡の特徴の中のいくつかについて短くまとめたものをまず提供する。
【００２６】
図２は、制御ユニット２の機能構成要素を示す。これらは、望みに応じてソフトウェアおよび／またはハードウェアの形で実施することができる。制御ユニット２は、入力画像を受け取り、より詳しく以下に述べるように、画像中の物体の輪郭線を近似した多角形を導き出す多角形近似ユニット１２を含む。多角形近似ユニット１２の出力は、バッファ１６および対応決定ユニット１４に入力される。対応決定ユニット１４は、より詳しく以下に述べるように、現フレーム中の多角形の頂点と、別のフレーム中の多角形の頂点との対応を求めるためのものである。対応決定ユニット１４の出力は、一連のフレームを通しての各多角形頂点の軌跡を表現する近似関数を求める軌跡関数近似ユニット１８に入力される。関数近似について、より詳しく以下に述べる。
【００２７】
軌跡関数近似ユニット１８の出力は記述子形成ユニット２０に入力され、記述子形成ユニット２０が軌跡関数から記述子を形成する。
【００２８】
図３の流れ図は、一連の画像における物体の動きの表現を導き出す方法のステップを示す。
【００２９】
ステップ１００において、関心のある物体を含む一連の画像中の各画像が、多角形近似ユニット１２に入力される。ステップ１１０において、各画像について、バイナリマスクが物体について導き出される。これは図４に示される。より具体的には、各ピクセルについて、ピクセルが関心のある物体の一部である場合、そのピクセルは第１の値、図４では黒丸に設定され、ピクセルが関心のある物体の一部ではない場合、そのピクセルは、図４では白丸と示される第２の値に設定され、バイナリマスクが生成される。
【００３０】
ステップ１２０において、物体の輪郭線が抽出され、近似多角形の頂点が生成される。物体の輪郭線はすでに、五角形または六角形等の単純な多角形の形でありうる。しかし、通常、物体の輪郭線ははるかに複雑であり、これにより必要な処理量が大幅に増す。したがって、物体の輪郭線は多角形で近似される。たとえばこれは、特許文献１及び２に記載のように物体の輪郭線を平滑化することにより、または所定数の頂点を有する多角形にマッチングまたは変更することによって行うことができる。多角形近似についてのさらに詳しいことは、たとえば、特許文献１及び２に見出すことができる。図５は、図４の物体輪郭線の多角形近似を示す。この場合の多角形近似は六角形である。
【００３１】
この例では、各フレームにおける物体の多角形近似が同じ数の頂点を有するものと想定するが、これが必ずしも当てはまるとは限らない。
【００３２】
所与のフレームについて、多角形近似が多角形近似ユニット１２から出力され、一時的に格納するためのバッファ１６に入力されるとともに、対応ユニット１４にも入力される。より具体的には、画像中の近似多角形の頂点の座標が入力される。
【００３３】
次に、ステップ１３０において、現画像の多角形の頂点と前の画像の多角形の頂点の間の対応が見つけられる。
【００３４】
図６は、時間ｔにおける最初の画像中の多角形（六角形）の位置、および時間ｔ’における後続画像中の多角形の位置を示す。この目的は、時間ｔにおける画像中のどの頂点が時間ｔ’における画像中のどの頂点に対応するかを求めることである。多角形は六角形であるため、考えられる対応の組合せが６つあることが理解されよう。言い換えれば、最初のフレーム中の各多角形頂点は、後続フレーム中で最も近い頂点に単純にマッピングされる場合もあり、または、たとえば頂点１つ分、頂点２つ分等、様々な程度で回転している場合もある。
【００３５】
頂点の対応を決定する方法は、特許文献１及び２により詳しく述べられている。
【００３６】
各頂点について、各画像中の頂点の座標が、頂点対応決定ユニットの結果を用いてリンクされる。これら座標は各頂点の軌跡を表す。
【００３７】
次のステップであるステップ１４０において、頂点の軌跡の関数近似が導き出される。
【００３８】
本実施形態では、各頂点が独立して検査され、さらに、各座標が別個に取り扱われる。
【００３９】
図７は、様々な時間ｔ０〜ｔ８における所与の頂点（図８中の頂点Ａ）のｙ座標の値を示したグラフであり、各時間点は画像に対応する。グラフに示される曲線は、間隔ｔ０〜ｔ４およびｔ４〜ｔ８にわたる近似関数の例である。
【００４０】
近似関数は、一次近似、二次近似、またはスプライン関数近似等、任意の適切な既知の技法を用いて導き出される。
【００４１】
本実施形態では、候補関数および誤差の算出および評価の違いを除き、このアルゴリズムは先行技術を考察するにあたり上述したアルゴリズムと同様である。
【００４２】
このアルゴリズムでは、補間の初期値は最初の２つの点に設定される。次に、補間を広げて一度に１点ずつ追加していき、ついに補間のＥＥＴが予め規定されたしきい値よりも大きくなる。その点で、新しい補間間隔が開始される。この手順は、すべての点が処理されるまで繰り返される。
【００４３】
このアルゴリズムについて正しく説明するため、以下の表記を定義する。ｄ（＞０）を変数（次元）の数とし、時間ｔでのｊ番目の変数の値をｖt(j)（ｊ＝１，２，・・・，ｄ）で表す。一続きの時間点をｔi（ｉ＝０，１，・・・）で表す。（候補）補間間隔について、開始時間（終了時間）をｔSTART（ｔEND）で表す。ｆtSTART,tEND(j)（ｔ）（ｊ＝１，２，・・・，ｄ）をｊ番目の変数補間関数の候補とする。これは、最小二乗法を用いて算出することができる。この場合、ｆtSTART,tEND(j)（ｔ）は、次の式を最小化するように算出される。
【００４４】
【数３】
2004158014.tif 000005
【００４５】
ここで補間関数は一次または二次の多項式である。候補関数の時間間隔は反復的に延長される。
【００４６】
本例では、頂点Ａのｙ座標の候補関数が導き出されている。候補近似関数ｆが、時間間隔ｔ＝Ｓからｔ＝Ｅ−１までについて上に概説したように導き出されたものと想定する。次に、ｔがＥに設定され、ｔ＝Ｅの候補関数の値が求められる。言い換えれば、導き出された近似関数をｔ＝Ｅに拡張しようと試みる。次に、結果もたらされる誤差が算出される。
【００４７】
結果もたらされる誤差は、図８を参照して以下のように算出される。
【００４８】
図８は、時間Ｅにおける画像の、上記ステップ１２０において求められた頂点を有する物体輪郭線を実線で示す。また、図８は、元のｙ値が時間Ｅにおける近似関数の値で置き換えられた頂点の位置をバツ印で示す。破線は、頂点値が変更された物体輪郭線を示している。
【００４９】
図８から見て取ることができるように、頂点の１つを変更した結果、多角形の面積が変化している。本実施形態では、誤差値は、元の多角形の面積と変更された多角形の面積の差分である。より具体的には、本実施形態では、時間ｔでの面積の差分は、以下の式を用いて算出される。
【００５０】
【数４】
2004158014.tif 000006
【００５１】
式中、ｉは画像中のピクセルにインデックスを付与し、ＰOR（ｉ）は、ピクセルｉが元の物体の輪郭線内にあるが、変更後の物体の輪郭線内にはない場合、またはピクセルｉが変更後の物体の輪郭線内にあるが、元の物体の輪郭線内にはない場合（すなわち、変更後の物体の輪郭線が元の物体の輪郭線よりも外側にある場合）、値１をとる。これにより、面積の差分の指標が与えられる。部分的に一方の面積内にあるが、他方の面積内にないピクセルの場合、ＰOR（ｉ）は、望みに応じて１または０に設定することができる。１つの変数（ｙ）のみが変更されているため、変更後の物体の輪郭線は、全体的に元の輪郭線内にあるか、あるいは全体的に元の輪郭線の外側にあるかのいずれか一方である。
【００５２】
他の式を用いて、面積の差分を算出することができる。たとえば、以下の式を使用して、延長された間隔での誤差を算出し、しきい値と比較することが可能である。
【００５３】
【数５】
2004158014.tif 000007
【００５４】
式中、ＳおよびＥは関数近似の開始点および終了点それぞれである。言い換えれば、関数近似の間隔中の誤差合計は、関数近似の適切性をテストするものとみなされる。結果得られる誤差値は所定のしきい値と比較される。誤差値がしきい値未満の場合、関数近似は時間Ｅ＋１に延長され、手順が繰り返される。代替として、たとえば、時間間隔ｔ＝Ｓ〜ｔ＝Ｅにおける式（１）からの最大誤差Ｄtをしきい値と比較することができる。
【００５５】
ｔ＝Ｅの誤差値がしきい値よりも大きい場合、関数近似はｔ＝Ｅ−１で終了する。新しい関数近似がｔ＝Ｅ−１で開始され、最初の終了点はｔ＝Ｅである。この関数近似もまた、上に概説したように算出される誤差を用いてテストされる。
【００５６】
最初の関数もまた、上に概説したように算出される誤差でテストされる。
【００５７】
上記諸ステップは、一連の画像中のｔのすべての値に対して繰り返され、頂点のｙ座標の軌跡を近似する関数のセットが得られる。
【００５８】
図７に示すように、この場合では、上記諸ステップにより２つの候補関数が得られる。
【００５９】
同じ諸ステップが、同じ頂点のｘ座標に対して行われる。
【００６０】
頂点のｘおよびｙ座標の関数を組み合わせて、頂点の軌跡の記述を形成することができる。
【００６１】
上記諸ステップが各頂点の各座標に対して繰り返され、各頂点の軌跡記述が得られる。
【００６２】
すべての頂点の軌跡記述子が組み合わせられて、物体の動き記述子が形成される。
【００６３】
図８に示すように、先行技術による誤差は、ｙ（Ａ）とｙ（Ａ’）との一次元差に対応するが、本実施形態は、ｙの変更により物体の面積の変更を反映しており、物体の動きの表現という点においてより正確である。
【００６４】
予め算出された関数の間隔を延長する代わりに、ｔ＝Ｓ〜ｔ＝Ｅの点に合う別の候補関数がある可能性がある。この可能性は、より長い間隔について、上に述べた最小二乗法によってテストすることができ、上記式を使用してｔ＝Ｓ〜ｔ＝Ｅまでのｔの各値について結果もたらされる面積誤差をテストする。面積誤差が、ｔの各値に所定のしきい値未満の場合、その候補関数を前の候補関数の代わりに選択することができる。２つのうちから選ぶため、全体面積、すなわち間隔中のｔのすべての値についての面積誤差の和を、選択された最も小さい全体誤差を有する候補関数と比較することができる。同様に、候補関数は、ｔ＝Ｓからｔの最大値までの時間間隔を考慮することによって導き出すことができ、候補関数を見つけ、すべてのｔについて結果もたらされる面積誤差をテストする。ｔの値についての最大面積誤差が所定のしきい値よりも大きい場合、ｔの最大値が１だけ減じられ、適切な候補関数が見つけられるまで手順が繰り返される。次に、ｔの値をｔの最小値に設定し、手順を繰り返すことができる。
【００６５】
上記実施形態では、関数近似が各頂点の各座標毎に別個に算出される。これは比較的粗い近似であるが、それでも先行技術と比較して、動き記述の品質を向上させる。
【００６６】
高度なアルゴリズムは、再帰的にすべての頂点を同時に解析して、近似を向上させる。別の手法では、異なる頂点の関数近似の主要な部分（開始点および終了点）すべてを同時に行う必要がある。
【００６７】
すべての頂点の関数近似およびそれぞれの主要点の再帰的な同時推定の例は以下である。
１．各頂点の最初の数個の主要点および対応する近似関数が、上記実施形態のように独立して推定される。主要点は、少なくともいくつかの頂点に数個の主要点を確保するに足る長さの間隔が与えられるように選択された所定の時間点ＥIまで選択される。
２．最初の頂点を選択する。
３．選択された頂点について、最初の主要点が識別され、選択される。
４．選択された主要点について、ステップ１において導き出された関数を使用して、同じ時間におけるその他のすべての頂点の（調整された）位置を求める。
５．ステップ４において算出された頂点の位置について、Ｄt’（上記式（２））の値が算出され、しきい値と比較される。Ｄt’がしきい値よりも大きい場合、考慮中の頂点の主要点が変更される。より具体的には、Ｄt’がしきい値未満になるまで、Ｄt’の値を算出する各段階において、主要点が後方に向けて段階的にとられ、すべての頂点がステップ２のように調整される。Ｄt’がしきい値よりも小さい場合、同様の段階的な主要点の延長が行われる。
６．ステップ４およびステップ５が、ステップ２と同じ頂点について、ステップ１において算出された次の主要点に対して繰り返される。この主要点は終了点であり、対応する関数の開始点はステップ５において求められる点である。
７．ステップ６は、考慮中の頂点のすべての主要点に対して繰り返される。
８．次の頂点が選択され、ステップ３〜７がこの頂点について繰り返される。
９．次に、主要点の変化が止まるまで、または変化が十分に小さくなる（すなわち、所定のしきい値未満になる）まで、繰り返しステップ８がすべての頂点に対して繰り返される。
１０．全体の時間期間がＥIから延長され、これに従って、各頂点の近似関数が独立して延長され、次にステップ２〜９が繰り返される。
【００６８】
全体の時間期間は、比較的短い場合、ＥIに設定し、ステップ９を省くことが可能である。
【００６９】
テストにより、誤差が実際の領域と関数近似によって推定された領域とのピクセル数の差分として定義される場合、提案された技法が、先行技術を越える平均正規化誤差（すべてのフレームにわたっての平均をとる）において大幅な改良をもたらすことがわかっている。
【００７０】
上に述べた実施形態では、一次元関数が、各頂点の各座標毎に別個に近似される。代替として、二次元関数を各頂点の両方の座標に同時に導き出すことができる。１つの座標が変更される実施形態では、物体の輪郭線は増大するか、あるいは減少するかのいずれか一方であり、ピクセルの変化は面積の変化である。しかし、２つの座標が同時に処理される場合、物体輪郭線の全体面積値が同じままであるが、元の物体がカバーする元画像の面積（ピクセル）と変更後の輪郭線がカバーするピクセルとに関して変化が生じている場合がある。誤差値は、変更後の輪郭線ないにあるが元の輪郭線内にないピクセル数、および元の輪郭線内にはあったが、変更後の輪郭線内にはないピクセル数の関数（たとえば、和）として算出される。
【００７１】
記述子は、物体の移動の表現である。これは、たとえば、ビデオシーケンス中の物体の選択を可能にするため、探索、比較、および検索目的で一連の画像にインデックスを付与するため、診断目的、監視または解析のために移動を識別または分類するため、また他の多くの用法に使用することができる。本発明の適用例としては、再生中のビデオシーケンス中の物体をクリックして、たとえば物体の説明とともに、関連するウェブページを呼び出せるようにすることができることである。大量のデータが関わる物体の記述子および各画像毎にその位置を格納する代わりに、動き記述子により、クリックされたポイントが物体に対応することを識別することが可能であり、これに伴って格納されるデータの量はかなり少ない。
【００７２】
これは、所与の物体について、前の画像中の物体の場所が、後続画像を通して動き記述子（動き関数）とともにわかっているためである。したがって、時間ｔにおける関心のある画像について、物体の場所を計算することができる。この場所を、たとえば、マウスおよびカーソルを使用して選択された画像中のポイントまたは領域の位置と比較して、物体が選択されているか否かを判定することができる。
【００７３】
本発明によるシステムは、たとえば、ビデオライブラリに提供することができる。代替として、データベースをシステムの制御ユニットから離れた場所に配置し、電話回線等の一時的なリンク、またはインターネット等のネットワークにより制御ユニットに接続してもよい。ビデオおよび記述子データベースは、たとえば、永久記憶装置またはＣＤ−ＲＯＭもしくはＤＶＤ等のポータブルデータ記憶装置に提供することができる。
【００７４】
セレクタおよびコンパレータ等、上述したシステムの構成要素は、ソフトウェアまたはハードウェアの形で設けることが可能である。本発明はコンピュータシステムの形で説明されているが、たとえば、専用チップを使用して、他の形で実施することも可能である。
【００７５】
本発明は、たとえば、認証目的のための物体画像のマッチング、またはフィルタリングにも使用することが可能である。
【００７６】
本発明は、フィルムまたはビデオからの画像等の一連の画像、または同じウェブページ上にあるなど、なんらかの様式で関連している画像の集まりの中の画像に適用することが可能である。
【図面の簡単な説明】
【００７７】
【図１】ビデオデータベースシステムのブロック図である。
【図２】図１のシステムの制御ユニットの構成要素のブロック図である。
【図３】物体の動きの表現を導き出す方法の流れ図である。
【図４】画像における物体のバイナリマスクを示す図である。
【図５】図４に示す物体の輪郭線を近似した多角形を示す物体である。
【図６】物体輪郭線の頂点間の対応を導き出すステップを示す図である。
【図７】一連の画像に対応する時間間隔での頂点座標の変動を示す図である。
【図８】近似誤差の算出を示す図である。
【符号の説明】
【００７８】
２  制御ユニット、４  表示ユニット、６  ポインティングデバイス、８  ビデオデータベース、１０  記述子データベース、１２  多角形近似ユニット、１４  対応決定ユニット、１６  バッファ、１８  軌跡関数近似ユニット、２０  記述子形成ユニット。
【図１】
2004158014.tif 000008
【図２】
2004158014.tif 000009
【図３】
2004158014.tif 000010
【図４】
2004158014.tif 000011
【図５】
2004158014.tif 000012
【図６】
2004158014.tif 000013
【図７】
2004158014.tif 000014
【図８】
2004158014.tif 000015