(57)【要約】複数のピクセルを含む複数のフレームからなるビデオオブジェクトをセグメント化する方法により、まず各ピクセルに特徴ベクトルを割り当てる。選択されたピクセルをマーカーとして識別する。各マーカーおよび当該マーカーに隣接するピクセルの特徴ベクトル間の距離が第１の閾値未満の場合に、上記隣接ピクセルを、ピクセルのボリュームにアセンブルする。全ピクセルをボリュームにアセンブルしたら、各ボリュームに第１のスコアおよび記述子を割り当てる。この時点で各ボリュームは、セグメント化されたオブジェクトを表す。次に、上記ボリュームを上記第１のスコアに従って高低順にソートし、さらに高低順に処理する。ボリュームの対の記述子に依存する第２のスコアを決定する。上記第２のスコアが第２の閾値を越える場合に、上記ボリュームを繰り返し合成して、解像度オブジェクトツリーにおいてオブジェクトを生成する。当該ツリーは、合成されたボリュームまたはオブジェクトがビデオ全体になると完成する。
2004519966.tif 000002
【特許請求の範囲】
【請求項１】
複数のピクセルを含むビデオを複数のビデオオブジェクトにセグメント化する方法であって、
前記ビデオの前記各ピクセルに特徴ベクトルを割り当てること、
前記ビデオの選択されたピクセルをマーカーピクセルとして識別すること、
前記各マーカーピクセルの特徴ベクトルと、該マーカーピクセルに隣接するピクセルの特徴ベクトルとの間の距離が第１の所定閾値未満の場合に、前記マーカーピクセルおよび前記隣接ピクセルを、対応するボリュームにアセンブルすること、
前記各ボリュームに第１のスコア（ｓｃｏｒｅ）および記述子を割り当てること、
前記ボリュームを前記第１のスコアに従って高低順（ｈｉｇｈ−ｔｏ−ｌｏｗ ｏｒｄｅｒ）にソートすること、
前記ボリュームを高低順に処理することであって、該各ボリュームの処理は、
前記ボリュームの記述子を隣接ボリュームの記述子と比較して、第２のスコアを決定すること、
前記第２のスコアが第２の閾値を越える場合に、前記ボリュームを前記隣接ボリュームと合成して、多重解像度ビデオオブジェクトツリーにおいてビデオオブジェクトを生成すること、
前記ビデオを表す単一ビデオが残るまで前記比較するステップおよび前記合成するステップを繰り返すこと
を含む、処理すること
を含む方法。
【請求項２】
前記各ピクセルは、前記ビデオの時間−空間連結重複シーン（ｓｐａｔｉａｌ−ｔｅｍｐｏｒａｌ ｃｏｌｌｏｃａｔｅｄ ｏｖｅｒｌａｐｐｉｎｇ ｓｃｅｎｅ）における前記ピクセルおよび前記ボリュームの位置を示す空間座標（ｘ，ｙ）および時間座標（ｔ）を有する請求項１に記載の方法。
【請求項３】
前記ビデオは複数のフレームを含み、さらに、
特定フレーム中の前記各ビデオオブジェクトの一部を、隣接フレーム中の前記ビデオオブジェクトの投影と交わるように投影して、前記ビデオオブジェクトの連続シルエットを前記時間ｔ座標に従って提供すること
を含む請求項２に記載の方法。
【請求項４】
前記フレーム１０２に空間ドメイン２Ｄメディアンフィルタ２１０をかけて、エッジ構造を乱すことなく強度特異点（ｉｎｔｅｎｓｉｔｙ ｓｉｎｇｕｌａｒｉｔｉｅｓ）を除去することをさらに含む請求項３に記載の方法。
【請求項５】
前記ビデオを複数の同一サイズのボリュームに分割すること、
前記各ボリュームの中心にあるピクセルを前記マーカーピクセルとして選択すること
をさらに含む請求項１に記載の方法。
【請求項６】
前記ビデオ中の前記各ピクセルについて勾配の大きさ（ｇｒａｄｉｅｎｔ ｍａｇｎｉｔｕｄｅ）∇Ｖ＝∂Ｖ／∂ｘ＋∂Ｖ／∂ｙ＋∂Ｖ／∂ｔを決定すること、
最小の勾配を有するピクセルを前記マーカーピクセルとして選択すること、
前記マーカーの周りの所定の近傍にあるピクセルを除去すること、
残りのピクセルがなくなるまで前記選択するステップおよび前記除去するステップを繰り返すこと
をさらに含む請求項１に記載の方法。
【請求項７】
前記特徴ベクトルは、前記ピクセルの色に基づく請求項１に記載の方法。
【請求項８】
最小サイズ未満のボリュームを隣接ボリュームと結合することをさらに含む請求項１に記載の方法。
【請求項９】
前記最小サイズは、前記ビデオを表すボリュームの０．００１未満である請求項８に記載の方法。
【請求項１０】
前記ボリュームをサイズに対して昇順（ｉｎｃｒｅａｓｉｎｇ ｏｒｄｅｒ）にソートすること、
前記ボリュームを前記昇順で処理することであって、該各ボリュームの処理は、前記最小サイズ未満のボリュームがすべて処理されるまで、より小さいボリュームの各ピクセルを最も近いボリュームに含めることを含む、処理すること
をさらに含む請求項９に記載の方法。
【請求項１１】
前記記述子は、前記ボリュームの自己記述子（ｓｅｌｆ ｄｅｓｃｒｉｐｔｏｒｓ）と、前記ボリュームおよび前記隣接ボリュームの相互記述子（ｍｕｔｕａｌ ｄｅｓｃｒｉｐｔｏｒｓ）とを含む請求項１に記載の方法。
【請求項１２】
各々が複数のピクセルを含む複数のフレームからなるビデオシーケンスをセグメント化する方法であって、
前記ビデオの全フレームのピクセルをすべて、各ピクセルの特徴に従って複数のボリュームに分割することであって、各ボリュームのピクセルは、フレームベースの空間座標と、シーケンスベースの時間座標とを有する、分割すること、
各ボリュームに記述子を割り当てること、
各ボリュームを多重解像度ビデオオブジェクトツリーにおける最下位層のビデオオブジェクトとして表すこと、
ボリュームを前記記述子に従って繰り返し合成し、合成されたボリュームすべてが、前記多重解像度ビデオオブジェクトツリーにおける最上位層のビデオオブジェクトとして表されるビデオ全体を形成するまで、該合成されたボリュームの各々を前記多重解像度ビデオオブジェクトツリーにおける中間層のビデオオブジェクトとして表すこと
を含む方法。
【発明の詳細な説明】
【０００１】
［技術分野］
本発明は概して、ビデオ処理に関し、特に、ビデオオブジェクトのセグメンテーションに関する。
【０００２】
［背景技術］
ＩＳＯ  ＭＰＥＧ−１およびＭＰＥＧ−２などの古いビデオ規格は、ビデオ全体の時間的および空間的圧縮を主に扱う比較的下位レベルの仕様である。
【０００３】
ＭＰＥＧ−４およびＭＰＥＧ−７などの新しいビデオ符号化規格（「Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ −− Ｇｅｎｅｒｉｃ ｃｏｄｉｎｇ ｏｆ ａｕｄｉｏ／ｖｉｓｕａｌ ｏｂｊｅｃｔｓ」（ＩＳＯ／ＩＥＣ ＦＤＩＳ １４４９６−２ （ＭＰＥＧ４ Ｖｉｓｕａｌ）， Ｎｏｖ． １９９８）を参照）は、任意の形状のビデオオブジェクトを別個のビデオオブジェクトプレーン（ＶＯＰ）として符号化および復号化することを可能とする。これらの新生規格は、自然素材および合成素材が統合され、かつアクセスがユニバーサルであるマルチメディアの応用（インタラクティブビデオなど）を可能にすることを意図する。たとえば、動いている人物を１つのビデオから別のビデオへ「カットアンドペースト」したいとする。その人物を識別するには、まずビデオを「セグメント化」しなければならない。ビデオオブジェクトのセグメント化は、ユーザ制御下（すなわち半自動）で、または監視なし（すなわち全自動）で行うことが可能である。
【０００４】
半自動の場合、ユーザは、ビデオの１番目のフレームについてセグメンテーションを行うことができる。すると問題となるのは、ビデオオブジェクトの追跡の問題である。全自動の場合、問題は、まずビデオオブジェクトを識別し、次いで当該オブジェクトを時間および空間を通して追跡することである。明らかに、ユーザ入力はないことが最も望ましい。
【０００５】
ＶＯＰを用いると、ビデオの各フレームは任意の形状の画像領域にセグメント化される。各ＶＯＰはビデオオブジェクトを、たとえば形状、色、動きおよびテクスチャによって記述する。ビデオからＶＯＰを生成する厳密な方法は、上記規格には規定されていない。「自然の」オブジェクトは、通常の輝度成分およびクロミナンス成分の他に形状情報によって表されると考えられる。形状データは、セグメンテーションマスクとして、またはグレースケールαプレーンとして提供されて、多数のオーバーレイビデオオブジェクトを表すことができる。ビデオオブジェクトは下位層の特徴（オプティカルフロー、色、および強度など）に関して広範に変化するので、ＶＯＰセグメンテーションは非常に難しい問題である。
【０００６】
多数のセグメンテーション方法が既知である。領域ベースのセグメンテーション方法は、メッシュベースのもの、動きモデルベースのもの、および分離結合（ｓｐｌｉｔ−ａｎｄ−ｍｅｒｇｅ）を含む。これらの方法は、空間的特徴（輝度など）に頼っているために、誤ったオブジェクト境界を生じる場合があり、場合によっては、前景ビデオオブジェクトが背景に結合されてしまう場合がある。より最近では、形態学的時空間セグメンテーションが用いられている。この方法では、空間（輝度）ドメインおよび時間（動き）ドメインの両方からの情報が、ベクトルを用いて追跡される。この複雑な方法では、空間領域を時間領域に誤って割り当ててしまう可能性があり、また、２つ以上のオブジェクトを含むビデオにこの方法を適用することは困難である。
【０００７】
通常、監視なしのオブジェクトセグメンテーション方法は、３つの一般的な種類、すなわち（１）一様な色基準を用いる領域ベースの方法（Ｍ． Ｋｕｎｔ， Ａ． Ｉｋｏｎｏｍｏｐｏｕｌｏｓ， ａｎｄ Ｍ． Ｋｏｃｈｅｒ「Ｓｅｃｏｎｄ ｇｅｎｅｒａｔｉｏｎ ｉｍａｇｅ ｃｏｄｉｎｇ」（Ｐｒｏｃ． ＩＥＥＥ， ｎｏ．７３， ｐｐ．５４９−５７４， １９８５）を参照）、（２）一様な動き基準を用いるオブジェクトベースのアプローチ、および（３）オブジェクト追跡、に分類することができる。
【０００８】
色ベースの方法は、ある種の状況（たとえばビデオが比較的単純、明瞭でモデルによく適合する場合）では良好に作用するものの、一般性および頑健性に欠ける。主な問題は、単一ビデオオブジェクトが多数の異なる色を含み得るという事実から生じる。
【０００９】
動き指向のセグメンテーション方法は、意味的ビデオオブジェクトの動きは一様であるという仮定で始まる（Ｂ． Ｄｕｃ， Ｐ． Ｓｃｈｔｏｅｔｅｒ， ａｎｄ Ｊ． Ｂｉｇｕｎ「Ｓｐａｔｉｏ−ｔｅｍｐｏｒａｌ ｒｏｂｕｓｔ ｍｏｔｉｏｎ ｅｓｔｉｍａｔｉｏｎ ａｎｄ ｓｅｇｍｅｎｔａｔｉｏｎ」（Ｐｒｏｃ． ６ｔｈ Ｉｎｔ． Ｃｏｎｆ． Ｃｏｍｐｕｔ． Ａｎａｌｌ． Ｉｍａｇｅｓ ａｎｄ Ｐａｔｔｅｒｎｓ， ｐｐ．２３８−２４５， １９９５）を参照）。これらの方法は、境界設定（ｂｏｕｎｄａｒｙ ｐｌａｃｅｍｅｎｔ）方式または領域抽出方式のいずれかを用いる（Ｊ． Ｗａｎｇ ａｎｄ Ｅ． Ａｄｅｌｓｏｎ「Ｒｅｐｒｅｓｅｎｔｉｎｇ ｍｏｖｉｎｇ ｉｍａｇｅｓ ｗｉｔｈ ｌａｙｅｒｓ」（ＩＥＥＥ Ｔｒａｎｓ． Ｉｍａｇｅ Ｐｒｏｃ．， ｎｏ．３， １９９４）を参照）。これらの方法のほとんどは、オプティカルフローの概算または信頼性の低い時空間セグメンテーションに基づく。その結果、これらの方法には、オブジェクト境界が不正確であるという難点がある。
【００１０】
最後の種類のオブジェクトセグメンテーション方法は、追跡を用いる（Ｊ． Ｋ． Ａｇｇａｒｗａｌ， Ｌ． Ｓ． Ｄａｖｉｓ， ａｎｄ Ｗ． Ｎ． Ｍａｒｔｉｎ「Ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｐｒｏｃｅｓｓｅｓ ｉｎ ｄｙｎａｍｉｃ ｓｃｅｎｅ ａｎａｌｙｓｉｓ」（Ｐｒｏｃ． ＩＥＥＥ， ｎｏ．６９， ｐｐ．５６２−５７２， Ｍａｙ １９８１）を参照）。しかしながら、追跡方法はユーザとの対話を必要とし、その性能は最初のセグメンテーションに大いに左右される。ほとんどのオブジェクト抽出方法は、オブジェクトセグメンテーションをフレーム間またはフレーム内処理の問題として、いくらかの付加的な動きモデルのパラメトリック推定または平滑化制約とともに扱い、ビデオデータの３Ｄ側面を無視している。
【００１１】
したがって、ビデオ中の任意数のオブジェクトを多数の解像度に正確にセグメント化する全自動の方法が必要とされている。この方法は、経時的な動き特徴および色特徴の両方を用いるべきである。セグメンテーションは妥当な時間でなされるべきであり、最初のユーザによるセグメンテーションにも、一様な動き制約にも依存すべきではない。
【００１２】
［発明の開示］
本発明は、オブジェクト境界を正確に、ユーザの補助なしで検出するビデオオブジェクトのセグメンテーション方法を提供する。未処理のカラーまたはグレースケールビデオ、あるいは（たとえば検出されたエッジ、連続フレーム差分またはテクスチャスコアを有する）処理ビデオを、ビデオボリュームと呼ばれる構造に変換する。次に、当該ボリュームに高度な３Ｄ信号処理技術を適用する。
【００１３】
まずビデオをフィルタリングし、ビデオボリュームを形成し、たとえばピクセルの色勾配を用いてマーカーピクセルを識別する。ビデオボリュームを、色およびテクスチャ距離基準を用いて各マーカーの周囲で「増大（ｇｒｏｗｎ）」させる。自己記述子をボリュームに割り当て、相互記述子を類似ボリュームの対に割り当てる。これらの記述子は、当該ボリュームの動き情報および空間情報を取得する。
【００１４】
記述子ベースの適応的な閾値を適用および緩和している間に、考え得る各ボリュームの対の組み合わせについて類似性スコアを決定する。最大のスコアが得られたボリュームの対を繰り返し合成する。合成段階において、ボリュームは分類され、ビデオオブジェクトの多重解像度粗から密（ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ）階層において表される。
【００１５】
より具体的には、本発明による方法は、複数のフレームからなるビデオシーケンスをビデオオブジェクトにセグメント化する。各フレームはピクセルからなる。ビデオの各ピクセルには特徴ベクトルを割り当てる。次に、選択されたピクセルをマーカーピクセルとして識別する。各マーカーピクセルの特徴ベクトルと、当該マーカーピクセルに隣接するピクセルの特徴ベクトルとの間の距離が第１の所定閾値未満の場合に、上記隣接ピクセルを、対応するピクセルのボリュームにアセンブルする。
【００１６】
全ピクセルをボリュームにアセンブルしたら、各ボリュームに第１のスコアおよび自己記述子を割り当てる。この時点で各ボリュームは、セグメント化されたビデオオブジェクトを表す。
【００１７】
次に、上記ボリュームを上記第１のスコアに従って高低順にソートし、さらに高低順に処理する。
【００１８】
隣接ボリュームの対の記述子に依存する第２のスコアを決定する。上記第２のスコアが第２の閾値を越える場合に、上記ボリュームを繰り返し合成して、解像度ビデオオブジェクトツリーにおいてビデオオブジェクトを生成する。当該ツリーは、合成されたボリュームまたはビデオオブジェクトがビデオ全体になると完成する。
【００１９】
［発明を実施する最良の形態］
色、エッジ、および差分マップビデオボリューム
図１に示すように、本発明は、ビデオ１０１の１００、たとえばフレーム１〜Ｎ  １０２のシーケンスを３次元（３Ｄ）データ構造Ｖ、すなわちビデオボリューム１１１〜１１３にまとめる。色、エッジ、および差分マップボリューム１１１〜１１３は、同一の空間軸（ｘ，ｙ）１０３および時間軸（ｔ）１０４を有する。次に、高度な３Ｄ処理手法２００をビデオボリューム１１１〜１１３に適用して、ビデオオブジェクトを多重解像度階層６００に頑健にセグメント化する。
【００２０】
ビデオボリュームＶ（ｘ，ｙ，ｔ）は、ビデオ１０１の時間−空間連結シーンに関して、２つのシーンカット１２１〜１２２の間で定義される。ストリーミングビデオの場合、ビデオボリューム１１１〜１１３は、重複を可能とするために一定数（Ｎ）のフレームについて生成できる。これにより、ボリューム内でのオブジェクトの一貫性が保証される。
【００２１】
オブジェクトの動きが穏やかである場合、１フレーム中のビデオオブジェクトの一部の投影は隣接フレームと交わる。したがって、色ベースのビデオボリュームにおけるオブジェクトの部分は、時間軸ｔ１０４に沿って連続的なシルエットを有する。
【００２２】
オブジェクトセグメンテーション
図２に示すように、ビデオボリューム１１１〜１１３は、フレーム１０２中の未処理のカラーデータ（Ｒ、Ｇ、ＢまたはＹ、Ｕ、Ｖ）２０１から、または処理フレーム（すなわち、エッジ２３７、テクスチャスコア２３８、連続フレーム差分２３９など２０２（以下「特徴」）を含む）から形成され得る。
【００２３】
フレーム１０２をインデックス付けし（１〜Ｎ）、エッジ構造を乱すことなく強度特異点を除去するために３×３空間ドメイン２Ｄメディアンフィルタ２１０をフレーム１０２に適用する。２Ｄコヒーレンスを利用する、計算集約的なフィルタリングステップを加速させる２Ｄメディアンフィルタを用いる。
【００２４】
２つの水平方向に隣接する中央値も求めて、後述する必要な比較回数を低減する。動きを保存するために３Ｄメディアンフィルタは用いないことが好ましい。
【００２５】
高速メディアンフィルタリング
図８は、２−Ｄコヒーレンスを利用する高速メディアンフィルタ２１１を示す。３×３ウインドウ内で中央値（９エレメントリストでは５番目）を見つけるために必要な比較回数を３０から９．５に低減することによって、２つの水平方向に隣接する中央値を単一ステップで求める。まず、スライスｃ８０３およびｄ８０４を、前のステップのスライスａ８０１およびｂ８０２として６回の比較でソートする。ソーティングは、一組のネスト化した「ｉｆ」条件によって行われる。次に、５回の比較を用いてスライスｂ８０２およびｃ８０３をスライスｂｃに結合する。スライスａ８０１およびｂｃを結合して、ｐ／ｒの中央値を４回の比較で計算して求める。最後に、スライスｄ８０４およびｂｃを結合して、４回の比較でｑ／ｒの中央値を求める。最悪の場合、このプロセスは合計１９回の比較を要する。
【００２６】
後述のボリューム増大ステップ２４０における過度のセグメンテーションを防ぐために、上記メディアンフィルタ処理したフレームに２Ｄ平滑化フィルタ２２０を適用する。５×５空間ウインドウを有する２Ｄガウスフィルタが好ましい。ここでもまた、動きを保存するために３Ｄフィルタは用いない。
【００２７】
マーカー識別
ボリューム増大プロセス２４０は、接続されるピクセルの色およびテクスチャ分布が一様となるようにＶ（ｘ，ｙ，ｔ）のピクセルを接続する。このような分類されたピクセル（ボリュームと呼ぶ）は、いくつかのシードピクセル（マーカーと呼ぶ）から拡張される。マーカーピクセルｍｉは、ピクセルのボリューム全体のピクセルから、３つの方法で選択され得る。
【００２８】
一様に分布したマーカー
ビデオボリュームＶを、小さい同一のボリュームに分割し、小さいボリュームの中心をマーカーとして選択する。
【００２９】
近傍が固定した最小勾配マーカー
組Ｓは最初、ボリュームＶのすべての考え得る時空間ピクセルを含む。各ピクセルについて、３−Ｄ勾配
∇Ｖ＝∂Ｖ／∂ｘ＋∂Ｖ／∂ｙ＋∂Ｖ／∂ｔ
を色成分から計算する。次に、勾配が最小であるピクセルをマーカーピクセルとして識別する（２３０）。マーカーの周りの所定の近傍にあるピクセルを組Ｓから除去する。残りの組における次の最小値を選択し、組Ｓに残りのピクセルがなくなるまで識別ステップを繰り返す。
【００３０】
ボリュームが増大する最小勾配マーカー
最小値ｍｉを上記のように選択する。マーカーピクセルに隣接するピクセルを除去する代わりに、ボリュームＰｉを、ボリュームの全ピクセルが組Ｓから除去されるまで、
【数１】
2004519966.tif 000003
に従ってアセンブルする。
【００３１】
残りの組における次の最小値を選択し、その組に残りのピクセルがなくなるまで識別プロセスを繰り返す。
【００３２】
ボリュームのアセンブリング
特徴（たとえば色、テクスチャなど）の類似性基準に従って、マーカーピクセルｍｉの周りでボリュームＰｉｉ＝１，．．．，Ｍをアセンブルする（２４０）。ビデオボリュームＶ（ｘ，ｙ，ｔ）の各ピクセルに特徴ベクトル
【数２】
2004519966.tif 000004
を割り当てる。特徴ベクトルは最低限でも、ピクセルの色成分２０１を指定する。オプションとして特徴ベクトルは、他のデータ２０２（ガボールフィルタを適用することで得られるテクスチャスコア２３８など）も含むことができる。色特徴のみを用いる場合、マーカーピクセルｍｉの特徴ベクトル
【数３】
2004519966.tif 000005
は以下の通りである。
【数４】
2004519966.tif 000006
【００３３】
隣接ピクセルの特徴ベクトル
【数５】
2004519966.tif 000007
と、マーカーｍｉの特徴ベクトル
【数６】
2004519966.tif 000008
との間の距離ｄは、以下のように測定される。
【数７】
2004519966.tif 000009
【００３４】
距離ｄが所定の閾値λよりも小さい場合、隣接ピクセルをボリュームＰｉに含め、隣接ピクセルをボリュームＰｉの有効表面ピクセル（ａｃｔｉｖｅ ｓｕｒｆａｃｅ ｐｉｘｅｌ）として設定する。
【００３５】
次に、マーカーピクセルの特徴ベクトルを以下のように更新する。
【００３６】
【数８】
2004519966.tif 000010
【００３７】
次の繰り返しにおいて、有効表面ピクセルの隣接ピクセルを比較する。この動作は、ビデオボリュームの全ピクセルが処理されるまで繰り返す。上記プロセスは、マーカーピクセルと同様の特徴ベクトルを有する隣接ピクセルを同一のボリュームにアセンブルする。アセンブルされた各ボリュームの位置は、そのマーカーピクセルの位置によって示される。
【００３８】
小さいボリュームの結合
図９に示すように、最小サイズ未満のボリュームを隣接ボリュームと結合する（２５０）。これはたとえば、ボリュームＶ（すなわちビデオ全体）の０．００１未満のボリュームとする。探索プロセスを加速するために、結合２５０は、最小ボリュームで開始し、最小サイズ要件を満たさない最大ボリュームで終了することにより、階層状に行われる。要件を満たさない最小ボリュームを選択する（２５１）。この最小ボリュームの全ピクセルのマークを解除する（ｕｎｍａｒｋｅｄ）（２５２）。次に、マークを解除した各ピクセルについて、最も近いボリュームＰｃを見つけ（２５４）、そのボリュームに当該ピクセルを含める（２５５）。ステップ２５３〜２５５は、全ピクセルおよび小さなボリュームすべてについて繰り返す。
【００３９】
ボリューム記述子
次に図３、図４、および図７に示すように、一組の自己記述子Ｆ（Ｐｉ）３００および一組の相互記述子Ｆ（Ｐｉ，Ｐｊ）４００を各ボリュームＰｉに割り当てる。これらの記述子は、ボリュームの動き（軌跡）特徴７０１、形状または空間および色特徴７０２、ならびに任意のボリュームＰｉ、Ｐｊの対の間の相互関係を識別するために用いられる。記述子３００および４００は、以下のように割り当てる（２６０）。
【００４０】
後述のように、ボリューム内のピクセルの垂直座標および水平座標をフレームについて（ｆｒａｍｅ−ｗｉｓｅ）平均化することによって各ボリュームＰｉの軌跡Ｔｉを求める。平均化の代わりに、他の質量中心の定義を用いることもできる。自己記述子Ｆ１（ｐｉ）３００は、ボリューム中のピクセルの色平均を含むベクトルである。色平均（ｍｅａｎ （ａｖｅｒａｇｅ））３０１は、ＲＧＢ画像の場合に赤、緑、青の成分を、ＹＵＶ画像の場合に色相、彩度、および強度を含む。
【００４１】
自己記述子
ピクセルｐｋの色は、たとえば赤色成分の場合にＲ（ｐｋ）として示される。するとＦ１（Ｐｉ）は赤色成分の平均を意味する。Ｆ２（Ｐｉ）３０２はボリューム中のピクセル数を表す。Ｆ３（Ｐｉ）３０３はボリュームの表面上のピクセル数である。ボリューム対表面の２乗の比として定義される第１の緊密さ（ｃｏｍｐａｃｔｎｅｓｓ）３０４は、Ｆ４（Ｐｉ）である。第２の緊密さの記述子Ｆ５（Ｐｉ）３０５は、表面の代わりにｍａｘｃｏｒｄを用いることによって定義される。
【００４２】
好ましい緊密度に関するさらなる詳細については、米国特許出願第０９／ｘｘｘ，ｘｘｘ号「Ｍｅｔｈｏｄ ｆｏｒ Ｍｅａｓｕｒｉｎｇ Ｃｏｍｐａｃｔｎｅｓｓ ｏｆ Ｄａｔａ ａｎｄ Ｓｉｇｎａｌ Ｓｅｔｓ」（Ｐｏｒｉｋｌｉ、２００１年ｘｘ月ｘｘ日提出、参照により本明細書中に援用）を参照されたい。
【００４３】
ｍａｘｃｏｒｄは、ボリュームに適合可能な最長コードの長さである。Ｆ６（Ｐｉ）およびＦ７（Ｐｉ）３０６〜３０７は、フレームのシーケンスに関してボリュームの軌跡を水平方向および垂直方向でそれぞれ記述する。Ｆ８（Ｐｉ）３０８は、軌跡の全長（経路長）である。Ｆ９（Ｐｉ）３０９およびＦ１０（Ｐｉ）３１０は、ボリュームのピクセルの平均化した座標である。
【００４４】
相互記述子
相互記述子Ｆ（Ｐｉ，Ｐｊ）４００は、ボリューム間の空間、形状、動き、色の関係を表現する。Ｆ１１（Ｐｉ，Ｐｊ）４１１は、ボリュームＰｉ、Ｐｊの両方が存在する各フレームにおける軌跡の距離を合計することによる、当該ボリュームの軌跡間の平均化距離である。軌跡距離の分散はＦ１２（Ｐｉ，Ｐｊ）４１２であり、その最大値はＦ１３（Ｐｉ，Ｐｊ）４１３である。距離の平均的変化Ｆ１４（Ｐｉ，Ｐｊ）４１４は、フレーム間における軌跡の累積距離の変化を意味する。ボリュームの方向は、最後のフレームにおけるボリュームの質量中心から、当該ボリュームが存在していたフレームにおけるボリュームの質量中心を指し示すベクトルである。方向差分Ｆ１５（Ｐｉ，Ｐｊ）４１５は、ボリュームＰｉ、Ｐｊに関連する２つの当該ベクトルの距離である。Ｆ１６（Ｐｉ，Ｐｊ）４１６は相互のボリュームの緊密さを、それらの別個の緊密さスコアの平均に関して表現する。Ｆ１７（Ｐｉ，Ｐｊ）、Ｆ１８（Ｐｉ，Ｐｊ）４１７〜４１８は、共有の（ｍｕｔｕａｌ）境界およびボリュームである。Ｆ１９（Ｐｉ，Ｐｊ）４１９は色差であり、Ｆ２０（Ｐｉ，Ｐｊ）４２０は、両ボリュームが共存するフレーム数である。
【００４５】
ボリューム合成
クラスタリングステップ５００において、ビデオを多重解像度ビデオオブジェクトにセグメント化するために、ボリュームを記述子に関して合成する。各ボリュームＰ１について、フレーム毎にボリュームのピクセルの空間平均をとることにより、軌跡Ｔｉ（ｔ）＝（ｘｔ，ｙｔ）を求める。
【００４６】
【数９】
2004519966.tif 000011
【００４７】
すると、時間ｔにおける２つのボリュームＰｉおよびＰｊの軌跡間の距離Δｄｉｊ（ｔ）は、以下の通りである。
Δｄｉｊ（ｔ）＝｜Ｔｉ（ｔ）−Ｔｊ（ｔ）｜
【００４８】
動き情報（垂直方向および水平方向の動き、経路長、距離の平均および分散、方向差分、および距離の平均的変化など）を軌跡から抽出する。したがって本発明は、従来のようにオプティカルフロー、パラメトリックモデルまたは広範な探索ベースのマッチング法によって動きを推定することなく、動き情報を効率的に用いる。
【００４９】
図５に示すように、クラスタリングステップ５００は、略同様なボリューム記述子３００、４００の対を有するボリュームを繰り返し結合することによって、セグメント化されたビデオオブジェクト６００を生成する。まず、ボリュームＰｉの記述子３００を、それらのサイズ、緊密さおよび存在の値の加重平均に関してスコアリングする（ｓｃｏｒｅ）（５１０）。次に、スコアリングしたボリュームを高低順にソートする。
【００５０】
ソートしたリストにおける１番目のボリュームＰｉから開始して、単一ボリュームが残る（５９９）まで、各ボリュームを以下のように処理する。
【００５１】
結合中に、現ボリューム５１１の記述子を、隣接ボリュームの記述子と比較する（５２０）。隣接ボリュームの記述子が一組の適応的な制約の閾値ｋｋ＝１０，．．．，２０を越える（５３０）場合、以下の類似性スコアを決定する（５４０）。
Ｓ（Ｐｉ，Ｐｊ）＝ω１Ｆ１１（Ｐｉ，Ｐｊ）＋ω２Ｆ１２（Ｐｉ，Ｐｊ）＋ω３Ｆ１４（Ｐｉ，Ｐｊ）＋ω４Ｆ１５（Ｐｉ，Ｐｊ）＋ω５Ｆ１６（Ｐｉ，Ｐｊ）
【００５２】
閾値のサイズは、セグメント化されるビデオブジェクトの解像度を規定する。
【００５３】
隣接ボリュームの記述子が制約試験５３０に合格した（５３１）場合、最大の類似性スコアを有する隣接ボリュームを選択して（５５０）現ボリューム５１１と合成し（５６０）、上記ソートしたリストにおける次のボリューム５１１を用いて閾値演算（ｔｈｒｅｓｈｏｌｄｉｎｇ）および合成を繰り返す。繰り返しの中でボリュームが合成されない場合、次式を用いて閾値を緩和する（５７０）。
【００５４】
【数１０】
2004519966.tif 000012
【００５５】
合成は、類似性スコアが初期スコアを相当幅で超えるまで、あるいは残りのボリュームがなくなるまで続く。
【００５６】
多重解像度オブジェクトツリー
図６に示すように、結合を繰り返す間に、ボリュームは、Ｎ階層（各繰り返しに１階層）を有する多重解像度オブジェクトツリー６０１におけるノードとして表される。第１層（Ｌｅｖｅｌ １）はビデオ全体を表し、第２層はビデオを、動きのあるビデオオブジェクト６２１と背景６２２とにセグメント化する。背景ボリュームは、動きのあるビデオオブジェクト６２１と比べて、経時的な動きが遅く、空間的に一貫しており、比較的大きい（６２３）。多重解像度ツリーの下位層では、動きの一貫したビデオボリュームを有するビデオオブジェクトがセグメント化される（６３１）。ツリーの最下位層（すなわち第Ｎ層）では、一様な色、一様なテクスチャ、一様な形状、および空間的接続性を有する（６４１）ビデオオブジェクトが、本発明によるビデオボリュームを用いて正確にセグメント化される。
【００５７】
ビデオオブジェクトをセグメント化する本発明の方法は、ビデオ中のビデオオブジェクトの動きが大きい場合であっても頑健である。さらに本発明の方法は、密なオプティカルフローの計算に依存する方法よりも著しく高速である。本方法では、過度にセグメント化してしまう場合のある従来技術の色、動き、および追跡ベースの方法とは異なり、セグメント化されたビデオオブジェクト数が変化しないままであるとセグメンテーションが自己停止するため、深さが有限の多重解像度でのオブジェクト表現が可能となる。
【００５８】
本発明を好ましい実施の形態の例により記載してきたが、本発明の精神および範囲内で様々な他の適用および改変が行われ得ることが理解される。したがって、併記の特許請求の範囲の目的は、本発明の真の精神および範囲に含まれる変形および改変をすべて網羅することである。
【図面の簡単な説明】
【図１】本発明によるビデオボリュームのブロック図である。
【図２】本発明によるビデオセグメンテーション方法のフロー図である。
【図３】ビデオボリューム自己記述子のブロック図である。
【図４】ビデオボリューム相互記述子のブロック図である。
【図５】図２の方法のボリューム合成ステップのフロー図である。
【図６】図２の方法により作成される多重解像度ビデオオブジェクトツリーの図である。
【図７】ビデオボリューム自己記述子および相互記述子のブロック図である。
【図８】３×３ブロック内で行われる高速２−Ｄメディアンフィルタリングの図である。
【図９】本発明による、小さいボリュームの結合のフロー図である。
【図１】
2004519966.tif 000013
【図２】
2004519966.tif 000014
【図３】
2004519966.tif 000015
【図４】
2004519966.tif 000016
【図５】
2004519966.tif 000017
【図６】
2004519966.tif 000018
【図７】
2004519966.tif 000019
【図８】
2004519966.tif 000020
【図９】
2004519966.tif 000021
【国際公開パンフレット】
2004519966.tif 000022
2004519966.tif 000023
2004519966.tif 000024
2004519966.tif 000025
2004519966.tif 000026
2004519966.tif 000027
2004519966.tif 000028
2004519966.tif 000029
2004519966.tif 000030
2004519966.tif 000031
2004519966.tif 000032
2004519966.tif 000033
2004519966.tif 000034
2004519966.tif 000035
2004519966.tif 000036
2004519966.tif 000037
2004519966.tif 000038
2004519966.tif 000039
2004519966.tif 000040
2004519966.tif 000041
2004519966.tif 000042
2004519966.tif 000043
2004519966.tif 000044
2004519966.tif 000045
2004519966.tif 000046
2004519966.tif 000047
2004519966.tif 000048
2004519966.tif 000049
【国際公開パンフレット（コレクトバージョン）】
2004519966.tif 000050
【国際調査報告】
2004519966.tif 000051
2004519966.tif 000052
2004519966.tif 000053