(57)【要約】  ビデオオブジェクトのカットアンドペースト（１００）を説明する。１つの実装において、ビデオフレーム（１０８）を領域（３１８）に事前にセグメント化（２０２）することを、３Ｄグラフカットセグメント（２０４）の前に実施する。３Ｄグラフカットセグメント（２０４）は一時的なコヒーレンス（３２６）およびグローバルカラーモデル（３２０）を使用して、ビデオオブジェクト境界（５０４）の正確性を実現する。２Ｄローカルグラフカットセグメント（２０６）を次いで使用して境界を精練化（５０８）することができる。境界を、ユーザが選択したウィンドウ（５０２）シーケンス内部で追跡し、ローカルカラーモデル（３３６）を用いて精練化することができる。
2009500752.tif 000002
【特許請求の範囲】
【請求項１】
ビデオシーケンス（１０８）のフレームを、前記ビデオシーケンス（１０８）内のビデオオブジェクト（１０６）の輪郭（５０４）を指定する３Ｄグラフカットセグメント（２０４）を適用する前に分割すること（７０２）と、
隣接ビデオフレームにおける対応領域（３１８）の間の関連を形成することにより、一時的なコヒーレンスを前記３次元グラフ（４００）に埋め込むこと（３２６）を含む３次元グラフ（４００）を構築すること（７０４）と、
グローバルカラーモデルに従って前記３Ｄグラフカットセグメント（２０４）を前記３次元グラフ（４００）に適用して（７０６）、前記ビデオオブジェクトの前記輪郭（５０４）を表現するバイナリセグメントを導出することと、
ローカルカラーモデルに従って２Ｄグラフカットセグメントを少なくともいくつかのバイナリセグメントに適用して（７０８）、前記ビデオオブジェクト（１０６）の精練化した輪郭（５０８）を得ることと
を備えたことを特徴とする方法。
【請求項２】
前記ビデオシーケンス（１０８）のフレームを領域（３１８）に分割することが、ウォーターシェッド技術（３１６）を用いて前記ビデオシーケンス（１０８）を事前にセグメント化（２０２）することを含むことを特徴とする請求項１に記載の方法。
【請求項３】
修正コヒーレントマッティング技術（２１０）（３５４）を前記バイナリセグメント（３０２）に適用して（７０６）、前記ビデオシーケンス（１０８）から前記ビデオオブジェクト（１０６）を切り取るマットシーケンス（３５６）を得ることをさらに備えたことを特徴とする請求項１に記載の方法。
【請求項４】
前記ビデオオブジェクト（１０６）を前記ビデオシーケンス（１０８）から切り取ること、および前記ビデオオブジェクト（１０６）を別のビデオシーケンス（３６４）に貼り付けることをさらに備えたことを特徴とする請求項３に記載の方法。
【請求項５】
ウィンドウ選択入力（３３８）を受信することであって、前記ウィンドウ選択入力（３３８）が、前記ビデオシーケンスのビデオフレームの部分（５０２）を指定する受信することと、
前記ウィンドウ選択入力（３３８）に基づいて前記ビデオシーケンス（１０８）内部に一時的なウィンドウのシーケンス（３３４）を自動的に生成することと、
前記ウィンドウのシーケンス（３３４）内部で前記２Ｄグラフカットセグメント（３２８）を適用することと、
前記ローカルカラーモデル（３３６）を前記ウィンドウのシーケンス（３３４）内部の色に限定することと
を備えたことを特徴とする請求項１に記載の方法。
【請求項６】
ビデオシーケンス（１０８）のフレームを領域（３１８）に事前にセグメント化すること（２０２）と、
前記ビデオシーケンス（１０８）の２つのモデルフレーム（１１０）を選択することであって、前記２つのモデルフレーム（１１０）の各々はビデオオブジェクト（１０６）を表す前景と、背景とを有する選択することと、
単一フレーム上の領域（３１８）を同一フレーム上の隣接領域（４０８、４１０、４１２、４１４）と関連付けることと、
前記単一フレーム上の領域（３１８）を隣接フレーム上の対応する候補領域（４１６、４１８、４２０）（４２２、４２４、４２６、４２８、４３０）と関連付けることと
を含む、前記２つのモデルフレームにより一時的に囲んだフレームの３Ｄボリュームから３次元（３Ｄ）グラフ（４００）構築することと、
グローバルカラーモデルに従って前記３Ｄグラフ（４００）を関連する前景領域と関連する背景領域とにセグメント化すること（７０６）であって、前記の関連する前景領域は前記ビデオシーケンス（１０８）のフレーム内の前記ビデオオブジェクト（１０６）を表すことと
を備えたことを特徴とする方法。
【請求項７】
フレームの事前にセグメント化（２０２）は、ウォーターシェッド技術（３１６）またはトボガニング技術を用いることを特徴とする請求項６に記載の方法。
【請求項８】
前記単一フレーム上の前記領域（３１８）を隣接フレーム上の候補対応領域（４１６、４１８、４２０）（４２２、４２４、４２６、４２８、４３０）と関連付けることが、前記単一フレーム上のある領域（３１８）を、前記隣接フレーム上の対応しうる領域の位置の所与半径内にある、隣接フレーム上の領域と関連付けることをさらに含むことを特徴とする請求項６に記載の方法。
【請求項９】
前記単一フレーム上の前記領域（３１８）を隣接フレーム上の候補対応領域（４１６、４１８、４２０）（４２２、４２４、４２６、４２８、４３０）と関連付けることが、前記単一フレーム上の領域を、前記単一フレーム上の領域と前記隣接フレーム上の領域との間の色エネルギー比較（３２０）によって、前記隣接フレーム上の領域と関連付けることをさらに含むことを特徴とする請求項６に記載の方法。
【請求項１０】
前記３Ｄグラフ（４００）を関連する前景領域と関連する背景領域とにセグメント化することが、前記３Ｄグラフ（４００）のエネルギー関数（３２２）を最小化することにより実現されることを特徴とする請求項６に記載の方法。
【請求項１１】
最小化される前記エネルギー関数（３２２）が、
【数１】
2009500752.tif 000015
で表され、ここで、ＸｒおよびＸｓはそれぞれ領域ｒおよびｓの前景／背景ラベルであり、 
【数２】
2009500752.tif 000016
であって、Ｅ１は領域ｒの色の、前記２つのモデルフレームにおける色情報に関連付けられる前景／背景カラーモデルに対する適合を表し、Ｅ２は同一フレームにおける２つの隣接領域間の色差を表し、Ｅ３は２つの隣接フレームにおける２つの領域間の色差を表し、λ１およびλ２は定数であることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記グローバルカラーモデル（３２０）が、前記の２つのモデルフレームからグローバルに導出した前景色／背景色分布を含むことを特徴とする請求項６に記載の方法。
【請求項１３】
前記３Ｄグラフ（４００）のビデオチューブ部分（３３４）を特定することであって、前記ビデオチューブ（３３４）が、ビデオフレームの一部（５０２）と前記ビデオシーケンス（１０８）の他のビデオフレームの対応部分とを含む特定することと、
前記ビデオチューブ（３３４）を有する前記前景領域と前記背景領域との間の境界（５０４）を精練化するために、ローカルカラーモデル（３３６）を、前記ビデオチューブ部（３３４）内部の２次元（２Ｄ）グラフカットセグメント（３２８）に適用することと
をさらに含む請求項６に記載の方法。
【請求項１４】
前記のビデオチューブ部（３３４）を指定することが、第１フレーム上の第１ビデオチューブウィンドウ（５０２）と第２フレーム上の第２ビデオチューブウィンドウ（５０２）とを指定することをさらに含み、前記２つのモデルフレーム（１１０）の少なくとも１つが前記第１フレームと第２フレームとの間にあることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記第１フレームと前記第２フレームとの間のフレーム上で前記ビデオチューブ（３３４）の追加ウィンドウを自動的に生成するために、前記第１または第２のウィンドウ（５０２）の１つを前記ビデオシーケンス（１０８）の一部を介して双方向追跡（３３２）することをさらに備えたことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記の２つのモデルフレームの１つにおいて前記ビデオチューブウィンドウ（５０２）のうち１つの色から導出したローカル前景カラーモデルおよびローカル背景カラーモデル（３３６）を用いて、２Ｄグラフカットセグメント（２０６）を前記ビデオチューブ部分（３３４）のそれぞれのウィンドウ（５０２）に適用することをさらに備えたことを特徴とする請求項１３に記載の方法。
【請求項１７】
前記ビデオチューブウィンドウ（５０２）内の精練化した境界（５０８）を、前記ビデオチューブウィンドウ５０２に隣接する先在の境界（５１０、５１２）にシームレスに接続することをさらに備えたことを特徴とする請求項１６に記載の方法。
【請求項１８】
前記３Ｄセグメントまたは前記２Ｄセグメントの１つを行った後にビデオフレームの前景画素および背景画素を手動で割り当てること（３４０）により、前記３Ｄセグメントおよび前記２Ｄセグメントを上書きすることをさらに備えたことを特徴とする請求項１５に記載の方法。
【請求項１９】
前記前景領域を前記背景領域から分離するために、修正コヒーレントマッティング技術（２１０、３５４）を適用することをさらに備えたことを特徴とする請求項６に記載の方法。
【請求項２０】
ビデオシーケンス内部でフレームからフレームに持続する可視領域（３１８）を決定する手段と、
前記ビデオシーケンスの前記領域（３１８）から３次元グラフ（４００）を構築する手段と、
前記ビデオシーケンス（１０８）の隣接フレーム内の対応領域（３１８）（４１６、４１８、４２０）（４２２、４２４、４２６、４２８、４３０）間の関連を含めることで、一時的なコヒーレンスを３次元グラフ（４００）内に埋め込む（３２６）手段と、
セグメント化結果を得るために、前記ビデオシーケンス（１０８）のグローバルな色に基づいて、３次元グラフカットセグメント（２０４）を前記３次元グラフ（４００）に適用する手段と、
前記セグメント化結果のローカル部分（５０２）を指定する手段と、
２次元グラフカットセグメント（２０６）を前記ローカル部分（５０２）のローカルカラー（３３６）に基づいて前記ローカル部分（５０２）に適用する手段と
を備えることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
ビデオシーケンスを行き来する移動オブジェクトのカットアンドペーストは、ビデオ処理の領域において多数の応用例を有する。オブジェクトのデジタルセグメントは上記のカットアンドペーストを可能とし、ビデオ処理においてますます評判の高い研究領域となった。
【０００２】
従来は、ビデオオブジェクトのカットアンドペーストは、ブルースクリーンマッティングまたは“ブルースクリーニング”とも呼ばれるクロマキーイングにより実施されてきた。クロマキーイングにおいては、前景のオブジェクトは通常は青または緑である無地色の背景の前でビデオ録画され、次いで公知の背景色を利用するマッティング技術を用いて背景から分離される。これらの技術は簡潔であるので、高速に前景を分離することができる。クロマキーイングをリアルタイムに計算するシステムもある。しかしながら、これらの方法は無地色の単純な背景に限定される。前景のオブジェクトが背景に類似した色を含むと、エラーが発生することがよくある。
【０００３】
ビデオオブジェクトの切り取りに対するいくつかの従来アプローチとしてシルエット追跡がある。これらの既存方法を一般の背景に適用して追跡プロセスに高い堅牢性を提供することができるが、それらはオブジェクト境界を不正確かつ粗く表現する平滑曲線を使用する。粗境界ディスクリプタはシルエットの細部を捕捉できないため、これらの技術は大部分のカットアンドペーストアプリケーションに対して不十分である。これらの粗境界技術を自動キーイングにより対話的に精練することができる。自動キーイングは、スプライン編集を通して細部の境界を調整するユーザインタフェースを提供する。しかしながら、それぞれのビデオフレームをユーザにより個々に修正しなければならないため、境界の細部を正確に描くのに必要な手動作業のコストが高い。
【０００４】
近年、従来のビデオマッティング技術における無地色背景の要件が緩和され、単一の同一背景色の代わりに滑らかな色変化が可能となった。上記のシナリオにおいてビデオマッティングが成功するか否か、例えばどれだけ正確にトライマップを伝播できるか、およびどれだけベイジアンマッティングをそれぞれの個別フレームで良好に実施できるかは様々な技術に依存する。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
背景が複雑なときのビデオマッティングには、一般的なビデオシーケンスに対して２つの主な難点がある。第１に、多数のビデオは高速な動き、シルエットの変形、トポロジーの頻繁な変化を含み、これらはトライマップを双方向に伝播させる最先端のオプティカルフローアルゴリズムに対して非常に困難である。第２に、十分なユーザ対話で正確なトライマップを得ることが可能な場合でも、前景／背景が複雑なテクスチャを含むか、または前景の色が背景色と類似する際に、ベイジアンマッティング技術が不満足な結果を生むことがよくある。言い換えれば、背景が単一の無地色より複雑なとき、ビデオ再生中にビデオオブジェクトが変化したり動いたりする際のビデオオブジェクトの縁を自動的に決定することは、高度なプロセッサ集中型のタスクである。
【課題を解決するための手段】
【０００６】
課題を解決するための手段は、複数の概念から選択したものを簡潔な形で導入するために提供する。これらの概念は以下の発明を実施するための最良の形態でさらに説明する。本要約はクレーム主題の主要な特徴または本質的な特徴を特定するようには意図しておらず、クレーム主題の範囲を決定するための支援として使用するようにも意図していない。
【０００７】
上記を考慮して、ビデオオブジェクトのカットアンドペーストを説明する。一実施態様において、３Ｄグラフカットセグメントの前にビデオフレームを領域に予めセグメント化する。３Ｄグラフカットセグメントは一時的コヒーレンスおよびグローバルカラーモデルを使用してビデオオブジェクト境界の正確性を実現する。次に、２Ｄローカルグラフカットセグメントを使用して、前記境界を精練することができる。前記境界をユーザが選択したウィンドウのシーケンス内で追跡し、ローカルカラーモデルを用いて精練することができる。
【発明を実施するための最良の形態】
【０００８】
概要
動いたり変化する可視オブジェクトを、時には複雑な場合もある動画シーケンス（ビデオクリップ）の背景から自動的に分離して（すなわち“切り取って”）、例えば、別の動画背景上に貼り付け可能とするシステムおよび方法を説明する。前記システムおよび方法は、切り取られるビデオオブジェクトの微細な外部境界の細部を保存できることが重要である。
【０００９】
前記システムおよび方法は、従来の技術よりも改善された特徴を有する３次元（３Ｄ）グラフカットセグメントを用いて、ユーザが少量のキーフレームマットを入力することにより複雑な形状変形を捕捉することができる。さらに、色が曖昧であるかまたは指定した前景と背景との間のコントラストが低いときでも、ローカルカラーモデルを用いてビデオオブジェクトの境界を正確に発見することができる。ローカルカラーモデルを用いて可視領域を正確に追跡するように双方向特性追跡技術を設計する。結果の切り取りビデオオブジェクトシーケンスは、他の背景に組み込むことが可能な状態である。
【００１０】
システムの例
図１はシステムの例１００を示す。システム１００において、ビデオカットアンドペーストエンジン１０２がコンピューティング装置１０４内に存在する。ビデオカットアンドペーストエンジン１０２は一時的に並べたビデオオブジェクト１０６（この場合、動くダンサー）をビデオクリップ１０８から切り取ることができ、その結果ビデオオブジェクト１０６を別の動画背景に貼り付けることができる。システム１００は、周囲の背景“マット(matte)”１１０から切り取られるビデオオブジェクト１０６を、従来技術より高速に、使い易く、効率的な方式で区別する（すなわち、“セグメント化する”）ことにより、このような“グラフカット”を実施する。
【００１１】
３Ｄグラフカット動作は、ビデオオブジェクト１０６が移動してフレーム上のそのフットプリントをある２Ｄフレームから次のフレームへ変化させる間に、時間インターバルを表す２次元（２Ｄ）表面（ビデオフレーム）の時間列、すなわちビデオクリップ１０８からビデオオブジェクト１０６を切り取る。３Ｄグラフカットではオブジェクトを紙片から切り取るように可視オブジェクトを単一の２Ｄ表面から分離する点で、３Ｄグラフカットは２Ｄグラフカットとは異なる。３Ｄグラフカットの“３次元”は、長さ、幅、および深さから成る３空間次元ではなく、第３の時間次元を通って移動する（すなわち、再生されている）（ビデオフレームの）２つの空間次元を言う。しかしながら、本明細書で説明する技術の例は３Ｄグラフカットに必ずしも限定されず、本発明の態様を、例えばホログラフィックオブジェクトがその空間内の環境から切り取られ、別の環境を有する別の空間に挿入されるような４次元グラフカットに適用することもできる。
【００１２】
本明細書で説明するシステムおよび方法は、コヒーレントマッティング(coherent matting)の適用前に正確なバイナリセグメントを生成するという利点を有する。すなわち、修正コヒーレントマッティングは、切り取られるビデオオブジェクト１０６のアルファマットを生成する前段としてバイナリセグメントを使用する。コヒーレントマッティングは例えば従来のベイジアンマッティングよりも良い結果を生成することができる。なぜなら、コヒーレントマッティングは、アルファマットに対する正規化項を有するバイナリセグメント内の情報を完全に活用するからである。さらに、バイナリビデオセグメントを提供することにおいて、例示的なシステムはより正確な結果を取得し、輪郭追跡およびトライマップ(trimap)伝播から成る従来技術よりも使い易いユーザインタフェース（ＵＩ）を境界精練化に対して利用する。
【００１３】
主題の一実施態様はさらに２Ｄイメージセグメント化方法を使用する。この方法により、グラフカットアルゴリズムと組み合わせた単純なユーザ対話を用いて正確なオブジェクト境界を容易に得ることができる。
【００１４】
本明細書で説明するシステムおよび方法は、単に画素ではなく、ビデオオブジェクト１０６を処理するために、従来の画素レベルの３Ｄグラフカッティングを領域ベースのグラフカッティングに拡張する。ローカル精練化方法の例は、同様に追跡機能を使用する。
【００１５】
図２は、ビデオカットアンドペーストエンジン１０２により実装したグラフカッティングプロセスの例に対する１つの実装の概要２００を示す。概要２００において、事前セグメント化２０２を３Ｄグラフカット２０４の前に行う。“ウォーターシェッド”パーティショニング（すなわち、”ウォーターシェッドアルゴリズム”を用いること）を入力ビデオシーケンス上で実施する。これにより、セグメント化が大幅に促進される。すなわち、３Ｄグラフカットを行う前にこのウォーターシェッドセグメント化を実施することにより、ビデオカットアンドペースト動作が大幅に加速される。このウォーターシェッドパーティショニングは、エネルギー評価を用いたグラフ領域への粗いバイナリ事前セグメント化から成る。
【００１６】
次に、３Ｄグラフカット２０４は、ビデオクリップから選択した少数のモデルビデオフレームをセグメント化プロセスの初期開始点として使用する。これらのモデルビデオフレームを、ビデオオブジェクト１０６および背景の間のコントラストを示す効果に関して選択することができる。次いで、グラフカッティングプロセスの例は、隣接ビデオフレーム内の対応する“候補”イメージ領域に渡るフレーム間接続を自動的に形成し、ビデオフレームを越えて時間を通してオブジェクトが動いたり変化したりする際に、正確なオブジェクトセグメントを保存する。
【００１７】
ユーザは、ローカルカラーモデルを用いて、ローカル２Ｄグラフカット２０６で自動的に生成したビデオオブジェクト境界をさらに精練化することができる。キーフレーム間の双方向特徴追跡を提供することもできる。この双方向特徴追跡により、ユーザは自動的に生成したビデオオブジェクト境界を局所的に補正することができる。
【００１８】
境界精練化２０８に対する手動ツールも提供する。この手動ツールは自動セグメントを上書きして、オブジェクト境界における細部を指定または補正する。
【００１９】
修正コヒーレントマッティングプロセスの例２１０は、ビデオクリップ１０８のフレームに対して一連のマットを自動的に生成する。修正コヒーレントマッティングプロセスの例２１０は、前記の一連のマットを用いて、ビデオクリップ１０８から指定ビデオオブジェクト１０６を抽出し、前記ビデオオブジェクトの前景色を抽出する。
【００２０】
他の機能にはマップ保存が含まれる。マップ保存により、ユーザはユーザ対話とカットアンドペーストの設定を後の使用および修正のためにファイルに保存することができる。前記の他の機能にはオブジェクト貼り付けも含まれる。オブジェクト貼り付けにより、ユーザはセグメント化オブジェクトを新規背景に配置することができる。
【００２１】
エンジンの例
図３は、図１のビデオカットアンドペーストエンジン１０２をさらに詳細に示す。図３に示すビデオカットアンドペーストエンジン１０２は、１つの配置例を概観の目的で提供することを意図している。示したコンポーネントまたは同様のコンポーネントに対する多数の他の配置方法が可能である。上記のビデオカットアンドペーストエンジン１０２をハードウェア、ソフトウェア、またはハードウェア、ソフトウェア、ファームウェアの組み合わせ、等で実行することができる。
【００２２】
エンジンの例１０２にはバイナリセグメント化器３０２が含まれる。バイナリセグメント化器３０２は、ビデオオブジェクト１０６とその背景との間の境界を発見することを目的とする。すなわち、バイナリセグメント化器３０２はそれぞれの画素に対して、前記画素が前景（切り取られるビデオオブジェクト１０６）にあるかまたは背景（マットの一部）にあるかを決定することを目的とする。ビデオオブジェクト１０６内の画素とビデオオブジェクト１０６外部にある次の隣接画素との間で完全な切り取りまたは“セグメント化”が行われることが理想的である。しかしながら、エンジンの例１０２は、個々の画素ではなく一時的に変化する３Ｄビデオボリュームのビデオフレームの領域を考慮することにより、従来技術に勝る速度と正確性を得る。
【００２３】
バイナリセグメント化器３０２には、ビデオオブジェクト境界の全体的発見プロセスを実施するための３Ｄグラフカットセグメント化エンジン３０４と、３Ｄグラフカットセグメント化エンジン３０４により得られた結果を精練化するための２Ｄローカル境界精練化器３０６とが含まれる。これらコンポーネントの両方はユーザインタフェース３０８と対話する。
【００２４】
３Ｄグラフカットセグメント化エンジン３０４には、さらに、フレーム事前セグメント化エンジン３１０と３Ｄグラフエンジン３１２が含まれる。フレーム事前セグメント化エンジン３１０には、さらに、３Ｄボリュームバッファ３１４、ウォーターシェッドパーティション化器３１６、およびウォーターシェッドパーティション化器３１６により決定される領域３１８の記憶域が含まれる。３Ｄグラフエンジン３１２には、さらに、グローバルカラーエネルギー評価器３２０、フレーム内コネクタ３２４、およびフレーム間コネクタ３２６が含まれる。グローバルカラーエネルギー評価器３２０は、さらに、カラー比較器３２２を含むことができる。
【００２５】
２Ｄローカル境界精練化器３０６はローカル２Ｄグラフカッター３２８およびセグメント上書器３３０を含むことができる。ローカル２Ｄグラフカッター３２８には、さらに、双方向特徴トラッカー３２２、ビデオチューブエンジン３３４、およびローカルカラーモデラー３３６が含まれる。ビデオチューブエンジンにはウィンドウ指定器３３８が含まれる。セグメント上書器３３０には、一般に、ユーザインタフェースブラシツールのような、ビデオフレームの前景領域と背景領域を指定するためのユーザツール３４０が含まれる。ユーザインタフェース３０８はビデオディスプレイ３４２、ディスプレイ制御装置３４４、キーフレーム入力器３４６、およびオブジェクトセレクタ３４８を含むことができる。
【００２６】
マップセーバ３５０はバイナリセグメント化器３０２により得られるバイナリセグメントを保存することができる。これは、ユーザがローカル２Ｄグラフカッター３２８およびユーザツール３４０等である程度手動で干渉して実施した境界の修正を含むことができる。
【００２７】
バイナリセグメント化器３０２からのバイナリセグメント化結果を用いて、マット抽出器３５２は修正コヒーレントマッティングアルゴリズム３５４を適用してビデオクリップ１０８内の各フレームのアルファマット、すなわち“マットシーケンス”３５６を得ることができる。前景の色抽出器３５８は、３Ｄビデオオブジェクト１０６をオブジェクトシーケンス３６０として抽出する。オブジェクト貼付器３６２は、オブジェクトシーケンス３６０を複数の新規背景３６４の１つに置くことができる。
【００２８】
１つの実装において、ビデオカットアンドペーストエンジンの例１０２の動作を以下のように要約することができる。ビデオフレームの事前セグメント化領域３１８をウォーターシェッドパーティション化器３１６により決定する。次いで、３Ｄグラフカットセグメント化エンジン３０４は、セグメントを、時空間ビデオボリュームの事前セグメント化領域に適用し、バッファ３１４内に保持することができる。３Ｄグラフエンジン３１２は、ビデオオブジェクト１０６の一時的なコヒーレンスを保存するように事前セグメント化領域３１８を接続する。２Ｄローカル境界精練化器３０６はこの初期セグメント化結果を取得し、２Ｄローカル境界精練化器３０６によりユーザはローカル精練化用の領域３１８を指定することができる。ローカル精練化において、ローカル２Ｄグラフカッター３２８は、背景全体からの色の代わりに局所的な色を利用するローカルカラーモデラー３３６を有する。
【００２９】
ビデオオブジェクトカットアンドペーストエンジン１０２のより詳細な説明を行う。一般的なシナリオでは、ユーザは最初にキーフレーム入力器３４６を用いてビデオクリップ１０８から少数のキーフレームを選択し、オブジェクトセレクタ３４８を用いてそれらの正確な前景／背景セグメントを提供する。オブジェクトセレクタ３４８は従来のイメージスナッピングツールを含むことができる。１つの実装において、エンジン１０２は１０フレーム間隔でキーフレームの標本を求め、その間のフレームの背景マットを生成するが、サンプル化速度は特定のビデオクリップ１０８におけるオブジェクトの動きに従って変化してもよい。動きが遅くなる、またはオブジェクトが変形した場合、低速なサンプル化速度を使用することができる。
【００３０】
３Ｄグラフカットセグメント化エンジン３０４はビデオクリップ１０８の時空間ボリュームに作用して、その時空間ボリュームを３Ｄボリュームバッファ３１４に記憶することができる。最適化プロセスを扱いやすくするため、フレーム事前セグメント化エンジン３１０はビデオクリップ１０８内のそれぞれのフレームを、ＶｉｎｃｅｎｔおよびＳｏｉｌｌｅのウォーターシェッドアルゴリズムのようなウォーターシェッド技術を用いて、多数の原子領域３１８に事前にセグメント化する。３Ｄグラフエンジン３１２はこれら原子領域３１８に基づいて３Ｄグラフを構築する。ＭｏｒｔｅｎｓｅｎおよびＢａｒｒｅｔｔのトボガニング（tobogganing）のような、代替的な事前セグメント化技術を使用することができる。いずれの場合も、３Ｄグラフカットセグメント化エンジン３０４は一時的接続を形成する。この一時的接続は、フレームからフレームへの一連の領域候補を保存し、従って明示的に動きを見積もらずに、一時的一貫性を埋め込む。
【００３１】
図４は３Ｄグラフ４００を構築する例の概要を示す。この３Ｄグラフ４００から３Ｄビデオオブジェクト１０６をセグメント化し、切り取ることができる。１つの実装において、領域ｒ３１８に対してグラフエンジン３１２は３つのエネルギー量を用いて３Ｄグラフ４００を構築する。先ず、３Ｄグラフエンジン３１２が、エネルギー項Ｅ１に従って、領域３１８を前景仮想ノード（例えば、４０４）および背景仮想ノード（例えば、４０６）に接続する。第２に、フレーム内コネクタ３２４が、エネルギー項Ｅ２に従って、領域３１８を単一フレーム（ｔ）内部の隣接領域（例えば、４０８、４１０、４１２、４１４）に接続する。次いで、フレーム間コネクタ３２６は領域３１８を、エネルギー項Ｅ３を有する隣接フレーム上の候補領域（例えば、先行フレームｔ−１上の候補領域４１４、４１６、および４１８、ならびに後続フレームｔ＋１上の候補領域４２２、４２４、４２６、４２８および４３０）に接続する。次いで、候補領域が、別の時点（すなわち、隣接ビデオフレーム上）ではカレント領域４０２にあるかも知れない隣接フレーム上の領域を表す。
【００３２】
図３のエンジンコンポーネントに戻ると、３Ｄグラフエンジン３１２が、従来技術のように個々の画素ではなくフレーム事前セグメント化エンジン３１０により得た“原子”領域３１８の上で、選択したキーフレームの各組の間で３Ｄグラフ４００を構築する。色比較器３２２を用いて各領域３１８の色一貫性をキーフレーム内の前景／背景の色分布と比較し、次いでビデオオブジェクト１０６の前景／背景の境界に渡る領域の間で色差を最大化することにより、３Ｄグラフエンジン３１２はセグメント化を実施する。加えて、３Ｄグラフエンジン３１２は、３つのエネルギーを使用して最適化することにより、３Ｄグラフに埋め込んだ一時的なコヒーレンスを利用する。実際は、ビデオオブジェクトのシルエットの大部分を３Ｄグラフカットセグメント化エンジン３０４により正確に見つけることができる。
【００３３】
さらに詳細に述べると、３Ｄグラフエンジン３１２が、一意なラベルｘ∈{１（前景）、０（背景）}をそれぞれの領域３１８に割当てる。キーフレーム内の領域３１８は、例えば、オブジェクトセレクタ３４８からのラベルを既に有し、３Ｄグラフエンジン３１２はラベルを他のフレーム内の領域に割当てる。
【００３４】
３Ｄグラフエンジン３１２が、キーフレーム入力器３４６からの２つの連続キーフレームにより囲まれる３ＤボリュームΓ＝〈ζ、Ａ〉を構築する。ノード集合ζはウォーターシェッドパーティション化器３１６により生成した原子領域（例えば、３１８）を含む。アーク集合Ａは２種類のアーク、すなわち、１つのフレーム内部のノードを接続するフレーム内アークＡ1および隣接フレームに跨るノードを接続するフレーム間アークＡＴを含む。
【００３５】
フレーム内アークＡＩを構築するため、フレーム内コネクタ３２４が、それぞれの領域ｒｔ３１８を同一フレーム（Ｉｔ）内の隣接領域（例えば、４０２、４０４、４０６および４０８）の各々に接続する。フレーム間アークＡＴを構築するため、平均色が領域ｒｔ３１８の平均色と閾値Ｔｃ（一般には３０ピクセル）以上異なるような明らかに無関係な領域は除いて、フレーム間コネクタ３２６はそれぞれの領域ｒｔ３１８を、所与の半径（一般には１５ピクセル）内にある隣接フレーム（Ｉｔ±１）内のそれぞれの候補領域（例えば、４２２、４２４、４２６、４２８、４３０）に接続する。“Ｌ”形または薄くて長い領域のような様々な形状を有する領域を扱うため、領域中心間のユークリッド距離の代わりに変形ダイレーションによって領域間の隣接性を計算する。３Ｄグラフエンジン３１２は、これらの候補接続集合を保持して隣接フレーム上で対応できるようにし、色比較器３２２により与えた最適化により、切り取るべきものを決定する。対応する可能性がある領域間の候補接続をフレームに渡って保持することにより、１つの対応のみを決定する従来の追跡方法よりも強力な堅牢性が得られる。
【００３６】
３Ｄグラフ生成器３１２は、式（１）のように３ＤグラフΓ上に定義したエネルギー関数を色比較器３２２に最小化させることで、対応する領域をラベル付けする。
【００３７】
【数１】
2009500752.tif 000003
【００３８】
ここで、ｘｒは領域ｒ３１８の前景／背景ラベルであり、
【００３９】
【数２】
2009500752.tif 000004
【００４０】
である。第１項は“尤度エネルギー”Ｅ１であり、キーフレームにおける色情報から構築した前景色／背景カラーモデルに対する領域ｒ３１８の色の適合性を表す。第２および第３項は“主エネルギー”、Ｅ２およびＥ３である。Ｅ２は同一フレーム内における２つの隣接領域間の色差を表し、フレーム内コネクタ３２４により使用されて２つの同様な隣接領域が前景内部または背景内部に共存することを促進する。第３項Ｅ３は２つの隣接フレームにおける２つの隣接領域間の色差を表し、フレーム間コネクタ３２４により使用されてフレーム間アークＡＴを通して一時的なコヒーレンスをグラフカット最適化プロセスに埋め込む。フレーム間コネクタ３２６はフレーム間の時間的接続を形成、すなわち、あるフレーム内の単一領域を後続フレーム内の複数の候補領域に接続し、数個の接続を最終段階の最適化で保持する。
【００４１】
グローバルカラーエネルギー評価器３２０は、キーフレーム内の色をサンプル化し、Ｅ１に対する前景色／背景カラーモデルを構築する。１つの実装において、グローバルカラーエネルギー評価器３２０はガウス混合モデル（ＧＭＭ）を使用して前景色／背景色分布を記述する。前景ＧＭＭのｍ番目の成分は（Ｗｍｆ、μｍｆ、Σｍｆ）で表され、重み、平均色、および共分散行列を表す。グローバルカラーエネルギー評価器３２０はＭ個の成分を使用して前景色または背景色を記述する。従って、ｍ∈［１、Ｍ］であり、一般にＭ＝６である。
【００４２】
所与の色ｃに対し、その前景ＧＭＭに対する距離を式（２）のように定義する。
【００４３】
【数３】
2009500752.tif 000005
【００４４】
ここで、式（３）に示すように、
【００４５】
【数４】
2009500752.tif 000006
【００４６】
である。
【００４７】
かつ、式（４）に示すように、
【００４８】
【数５】
2009500752.tif 000007
【００４９】
である。
【００５０】
領域ｒ３１８に対してその前景ＧＭＭに対する距離を、前記領域内部の全画素の距離の期待値として定義し、〈ｄｆ〉で表す。背景色に対する距離〈ｄｂ〉を同様に定義する。次いで、尤度エネルギーＥ１（ｘγ）を表１のように定義する。
【００５１】
【表１】
2009500752.tif 000008
【００５２】
{Ｆ}および{Ｂ}はそれぞれキーフレーム内の前景領域および背景領域の集合であり、それらのラベルが入力である。０および∞をＥ１に割当てることで、最適化においてこれらの強い制約を課す。
【００５３】
２つのエネルギーＥ２およびＥ３を２つの領域ｒおよびｓの間の色類似性に関して式（５）のように定義する。
【００５４】
【数６】
2009500752.tif 000009
【００５５】
ここで、‖ｃγ−ｃｓ‖はＲＧＢ色差のＬ２ノルムである。
【００５６】
堅牢性パラメータβは色コントラストを重み付けし、β＝（２〈‖ｃγ−ｃｓ‖２〉）−１に設定することができる。ここで、〈・〉は期待値演算子である。グローバルカラーエネルギー評価器３２０はβをＥ２およびＥ３に対して別々に計算する。要素｜ｘγ―ｘｓ｜により、エネルギーをセグメント境界に渡る接続に対してのみ考慮することができる。主エネルギーＥ２およびＥ３は、隣接ノードに異なるラベルを割当てる際のペナルティ項である。
【００５７】
３Ｄグラフエンジン３１２は効率的なグラフカットアルゴリズムを用いることで式（１）の目的関数をグローバルに最小化し、各領域に対する結果として得たラベルがビデオボリューム内のセグメントを決定する。
【００５８】
３Ｄグラフ構築において、グラフ内の仮想前景（または背景）に対するアークのエッジコストはＥ１（０）（Ｅ１（１））であり、フレーム内アークまたはフレーム間アークのエッジコストはｅ-β‖ｃｒ−ｃｓ‖２である。同様な色を有するノードｃｒ−ｃｓ間のアークのコストは高くなる。
【００５９】
１つの実装において、グローバルカラーエネルギー評価器３２０はデフォルトパラメータをλ１＝２４、λ２＝１２に固定する。これらの値により、３Ｄグラフカットセグメント化エンジン３０４はビデオオブジェクト１０６の境界を合理的な速度で無事に計算することができる。
【００６０】
グローバルカラーエネルギー評価器３２０はキーフレームからグローバルに前景色／背景色の分布を構築するので、３Ｄグラフカットセグメントの結果が、前景色がビデオクリップ１０８の異なる部分の背景色に一致する場所（逆も真である）では芳しくない可能性がある。従って、２Ｄローカル境界精練化器３０６にはビデオチューブエンジン３３４が含まれる。ビデオチューブエンジン３３４により、ユーザは非常に局所的な境界精練化を適用することができる。“ビデオチューブ”とは、時間にわたるビデオフレームフットプリントの小領域であり、この中でローカルカラーモデルのみをグラフカットセグメントにおいて使用する。局所的な色を隔離することにより、セグメント境界を大幅に改善することができる。ビデオチューブエンジン３３４にはウィンドウ指定器３３８が含まれる。ウィンドウ指定器により、ユーザはローカル境界精練化が生ずるビデオフレーム内の領域を指定することができる。１つの実装においてユーザは方形（ウィンドウ）を描く。その方形は、フレームに渡って伝播し、セグメントを自身の境界内部に限定する。ウィンドウ指定器３３８を通して方形を描くことは、ユーザインタフェース３０８およびディスプレイ３４４を通して実現することができる。
【００６１】
１つの実装において、ビデオチューブエンジン３３４のウィンドウ指定器３３８はビデオチューブを方形ウィンドウ{Ｗｔ}Ｔｔ＝１、すなわち、Ｔフレームに渡るビデオフレームのサブ部分として定義する。ビデオチューブを指定するには、ユーザは２つのキーウィンドウＷ１およびＷＴを選択する必要があるだけである。Ｗ１およびＷＴはそれぞれ、選択されているビデオチューブの最初と最後のウィンドウである。残りのウィンドウは、双方向特徴追跡器３３２により自動的に突き止められる。
【００６２】
１つの実装において、ビデオチューブエンジン３３４は、ローカルカラーモデラー３３６が局所的な前景／背景モデルを精練化のために取得可能であるように、Ｗ１とＷＴとの間には少なくとも１つのキーフレームがあることを決定する。また、ビデオチューブエンジン３３４は、交点により最適化において重い制約が与えられるので、チューブ境界が（ビデオオブジェクト１０６の縁にある前景と背景の間の）セグメント境界において正確であることを決定する。
【００６３】
２Ｄローカル境界精練化器３０６が追跡を実施した後、ローカル２Ｄグラフカッター３２８が、制約付き２Ｄ画素レベルグラフカットセグメントを、キーフレーム（複数）上の対応するビデオチューブウィンドウから構築した前景および背景カラーモデルを用いてそれぞれのビデオチューブウィンドウに適用する。最後に、２Ｄローカル境界精練化器３０６は、この精練化したセグメント化結果をそれぞれのビデオチューブから、ビデオチューブウィンドウに隣接する既存のビデオオブジェクト境界へシームレスに接続する。
【００６４】
図５は２Ｄ境界精練化の例を、ちょうど説明したビデオチューブを用いて示す。ビデオチューブウィンドウ５０２が、ユーザにより既存のセグメント化結果５０６の境界５０４上に配置される。ローカル２Ｄグラフカッター３２８はローカルカラーモデラー３３６が発見した局所的な色を用いてセグメント化を実施する。この境界精練化において、ウィンドウ５０２の端にある最外画素を既存のセグメント化結果に従って前景／背景の強い制約としてラベル付けし、その結果、ウィンドウ５０２の内部画素に対して決定されるもの全てが、３Ｄグラフカットセグメントからの既存のセグメント化結果５０６とシームレスに接続する。ウィンドウ選択の開始時はウィンドウ５０２の各内部画素の前景／背景の状態は不確定であり、より精練化された境界５０８によって決定される。この２Ｄグラフカットセグメント化結果、および（破線で示された）精練化した境界５０８を用いて以前のセグメント境界５０４を置き換える。ビデオチューブウィンドウ５０２が以前のセグメント境界５０４と交わる２つの交点５１０および５１２は同じ位置に留まるが、精練化した境界５０８の残りは以前の境界５０４と異なる可能性がある。
【００６５】
双方向特徴追跡
双方向特徴追跡器３３２をより詳細に説明する。２つのキーウィンドウＷ１とＷＴ、すなわち、ビデオチューブの第１のウィンドウと最後のウィンドウが与えられると、双方向特徴追跡器３３２は中間フレーム内のウィンドウ位置を追跡する。Ｗ１とＷＴの大きさは異なってもよく、ユーザにより調節することができる。追跡前に、中間のウィンドウ（の位置および大きさの両方）をＷ１とＷＴから線形補間する。
【００６６】
ビデオチューブエンジン３３４は、ビデオチューブ内のウィンドウＷＴの中間位置をｐｔで表す。ビデオチューブエンジン３３４は、さらにそれぞれのウィンドウ位置に対して検索範囲Ｓｔを定義する。ウィンドウの全位置
【００６７】
【数７】
2009500752.tif 000010
【００６８】
は以下の式（６）に示す目的関数を最小化することにより求めることができる。
【００６９】
【数８】
2009500752.tif 000011
【００７０】
ここで、Ｄ（ｐｔ１，ｐｔ２）は、ウィンドウＷｔ１およびＷｔ２の間の、それらの中心ｐｔ１、ｐｔ２が並ぶときのそれら重複領域における色距離の２乗の和である。項
【００７１】
【数９】
2009500752.tif 000012
【００７２】
および
【００７３】
【数１０】
2009500752.tif 000013
【００７４】
は最適化前のウィンドウＷｔ−１およびＷｔの位置であり、線形補間で計算する。１つの実装では、η１＝０．１およびη２＝１である。
【００７５】
式（６）の第１項は、キーウィンドウに関するウィンドウの色一貫性を最適化するように設計される。ビデオチューブエンジン３３４は最も一致するキーウィンドウを選択してこのコストを計算し、長時間に渡る特徴変化を可能とする。第２項はビデオチューブの平滑性を強制する。第３項は隣接ウィンドウ間の色差を最小化するためにある。キーウィンドウの位置は、それらがユーザにより配置されたので本最適化において固定されることに留意されたい。それぞれのウィンドウが２つのキーウィンドウから２方向に情報を受信するので、前記追跡を“双方向的”と称する。
【００７６】
１つの実装において、式（６）の目的関数を動的プログラミング（ＤＰ）アルゴリズムを用いて最適化することができる。双方向特徴追跡器３３２は前記最適化に対してマルチスケール法を使用することができる。先ず、双方向特徴追跡器３３２はビデオクリップ１０８内の各フレームに対してガウスピラミッドを構築し、それぞれの高次レベルは直下レベルのフレームサイズの半分である。双方向フレーム追跡器３２２はそれに応じてウィンドウの位置とサイズを拡大または縮小する。次いで、双方向フレーム追跡器３２２はピラミッドの頂上から始めてそれぞれのレベルにおいて、前のレベル内の最適化位置に集中させた検索範囲Ｓｔ内で最適化を実施する。最上位レベルに対しては、双方向特徴追跡器３３２はキーウィンドウからのＷｔの初期位置を線形補間する。一般に、ＮＴＳＣビデオ（７２０×４８０ピクセル）に対して、Ｌ＝４個のレベルがあり、それぞれのレベルでＳｔは７×７の正方形ウィンドウである。
【００７７】
ビデオチューブを配置すると、２Ｄローカル境界精練化器３０６はそれぞれのウィンドウ内で２Ｄグラフカットセグメント化を実施し、既存のセグメント境界を精練化する。２Ｄグラフを式（７）に示すように画素レベルで構築する。
【００７８】
【数１１】
2009500752.tif 000014
【００７９】
ここで、ｘｉは画素ｉのラベルであり、ζ'は追跡されている全ての画素で、Ａ'Ｉは画素間の８つの近傍の関係である。Ｅ１およびＥ２は、領域を画素で置き換えることを除いて式（１）と同様な定義を有する。１つの実装において、λ'Ｉの値は、一般に１０に設定される。
【００８０】
精練化を既存のセグメント境界にシームレスに埋め込むため、ローカル２Ｄグラフカッター３２８は既存のセグメント境界結果に従って自動的に前景および背景の強い制約を生成する。図５に示すように、ウィンドウ内部の全画素のラベルは、ウィンドウ境界上の画素を除いて、ローカル２Ｄグラフカッター３２８により解決される。既存のセグメント境界の前景にある場合、これらの画素は前景の強い制約として印を付けられる。そうでなければ、背景の強い制約として印を付けられる。これらの強い制約のため、図５に示すようにローカル２Ｄグラフカッター３２８は、ウィンドウのすぐ外側の既存境界にシームレスに接続したウィンドウ内部に結果を生成する。
【００８１】
上述のように、ビデオチューブ内には少なくとも１つのキーフレームがなければならない。ビデオチューブエンジン３３４はキーフレーム内のウィンドウ内部の画素を収集して、上のＥ１項に関するビデオチューブに対して前景／背景ＧＭＭを計算する。３Ｄグラフカットセグメント化エンジン３０４が使用するグローバルカラーモデルと比較して、ローカル２Ｄグラフカッター３２８はより正確なカラーモデルをローカルウィンドウにおいて使用して、大幅に改善した結果を取得する。これが、２Ｄグラフカッター３２８を２Ｄローカル境界精練化に使用する理由である。
【００８２】
図６はローカル精練化の前後のセグメント化結果を示す。３Ｄグラフカットセグメント化エンジン３０４を介してローカル境界精練化器３０６が生成した前記精練化には、正確なユーザ対話は必要でない。実際、ユーザは無関係な色を除外するようにビデオチューブウィンドウをフレームに置くだけでよい。フレーム６０２ａにおいて、示された人物の制服の記章は、背景内の旗と同様な赤色である。３Ｄグラフカットセグメント化エンジン３０４はグローバルカラーエネルギー評価器３２０を使用するので、３Ｄグラフエンジン３１２が赤色の記章が背景の一部であると決定するような、フレーム６０２ｂに示す境界誤差が導入される可能性ある。それは、記章が制服の可視外縁上にあり、緑色の制服の残部分とは一際異なる色を有するからである。実際、赤色の旗がフレーム６０２ａ内で目立って存在するので、グローバルカラーエネルギー評価器３２０は赤が強い背景色であると考える。しかしながら、フレーム６０４において２Ｄローカル境界精練化器３０６は、より小さい長方形のビデオチューブウィンドウ６０６内部でローカルカラーモデラー３３６を使用する。無関係なグローバルカラー情報を除外するローカルカラーモデルにより、境界はより正確に精練化される。
【００８３】
セグメント上書器の例
現実のビデオオブジェクト境界の周囲に曖昧な縁がある、または境界のコントラストが非常に低いとき、ローカル２Ｄグラフカッター３２８は正確なビデオオブジェクト境界を生成できない可能性がある。これは、人の指のビデオといった、微細な構造を自動的に区別できない薄い可視構造に対して特に当てはまる。これらの難点を手動で解決するため、セグメント上書器３３０を提供することができる。１つの実装において、セグメント上書器３３０はユーザツール３４０を有する。ユーザツール３４０によりユーザは、例えば明確な前景領域と明確な背景領域とを識別する２つの上書きブラシを用いて、非常に正確にオブジェクト境界を直接制御することができる。さらに、後の使用のため、ユーザの上書き動作をディスクに保存してロードすることができる。
【００８４】
バイナリセグメント化器の例３０２がビデオクリップ１０８をセグメント化すると、マット抽出器３５２が貼り付け用にビデオオブジェクト１０６を抽出する。１つの実装において、マット抽出器３５２はビデオオブジェクト境界に対して部分アルファマットを計算するようにコヒーレントマッティングアルゴリズム３５４を適応させる。１つの実装において、マット抽出器３５２は、アルファに対して正規化項を導入することにより従来のベイジアンマッティングを改善する。従ってマット抽出器３５２は以前のバイナリセグメント境界に従うアルファマットを生成し、前景色／背景色が類似しているときでも良好に動作する。
【００８５】
マット抽出器３５２は、バイナリビデオオブジェクト境界を一般には１０ピクセルだけダイレーションすることにより、不明確な境界領域を処理する。前景内の小穴またはシンギャップに対し、このダイレーションの結果、近隣でサンプル化される背景色はない。この場合、マット抽出器３５２はその代わりとして近傍のフレームから背景色をサンプル化する。
【００８６】
マット抽出器３５２は、ビデオオブジェクトのアルファマットを取得してマットシーケンス３５６を構成し、前景色抽出器３５８を有してビデオオブジェクトシーケンス３６０に対して前景色を取得する。次いで、オブジェクト貼付器３６２は、切り取ったビデオオブジェクトシーケンスを新規背景３６４に貼り付けることができる。
【００８７】
実験結果
実験例において、３．１ＧＨｚのコンピュータで試験を実施した。ソースビデオクリップ１０８をＤＶカメラにより、１２．５フレーム／秒の速度のプログレッシブスキャンモードで撮影した。それぞれのビデオクリップ１０８をセグメント当たり約３０フレームに分割し、それぞれのセグメントを独立にロードおよび処理した。キーフレームを通常は１０フレーム毎にサンプル化したが、ビデオクリップ１０８の中には速い動きや陰影変化のため、より密な標本を必要とするものもあった。
【００８８】
処理時間は、前述したビデオクリップ１０８のセグメントの各々に対して約３０分であった。１つの実験例において、フレーム事前セグメント化エンジン３１０による処理および他の計算が処理時間の約２０％を占め、ビデオチューブエンジン３３４による追跡および調整が処理時間の約４０％を占め、セグメント上書器３３０による上書き動作が処理時間の残り４０％を占めた。
【００８９】
中間結果の保存
前処理は、それぞれのセグメントに対し、一般に１回だけ実施され、ウォーターシェッドパーティション化器３１６および３Ｄグラフカットセグメント化エンジン３０４からの結果は、一般にはマップサーバ３５０により保存され、要望に応じて再利用することができる。３Ｄグラフエンジン３１２は、使用した処理時間の大部分に対して一般には責任を負わない。
【００９０】
モデルの例
図７はビデオシーケンスからビデオオブジェクトをセグメント化する方法の例７００を示す。フロー図において、動作を個々のブロックに要約してある。方法の例７００の一部をハードウェア、ソフトウェア、または両方の組合せにより実施することができ、例えばビデオカットアンドペーストエンジンの例１０２のコンポーネントにより実施することができる。
【００９１】
ブロック７０２で、ビデオシーケンスのフレーム内部で領域を確立する。例えば、フレーム事前セグメント化エンジン３１０はウォーターシェッドアルゴリズムを適用してビデオフレームを原子領域にレンダリングすることができる。画素の代わりに領域を使用すると多くの利点がある。１つには、領域での作業には処理能力が少なくてよく、ビデオのカットアンドペースト動作を高速化することができる。所与の領域はビデオシーケンスの再生中に位置、形状、および色等を変更可能であるので、そのような動くオブジェクトの境界を定義する上での難点の１つは、ビデオシーケンスのフレームを通して領域を正確に追跡することである。
【００９２】
従って、ブロック７０４で、一時的なコヒーレンスを前記領域の３Ｄグラフに埋め込む。３Ｄグラフエンジン３１２は例えば、同一フレーム上の隣接領域間だけでなく、一時的に隣接するビデオフレーム上の領域と可能な“候補”領域との間でも関連性を形成することにより、３Ｄグラフを構築することができる。これによりシーケンスのフレーム間にある所与領域の識別が一貫し、次いでこれによりビデオシーケンス内のビデオオブジェクトをよりはっきりと区別することができる。なぜなら、領域が複数フレームに渡って移動および変形する際の、所与領域がビデオオブジェクト１０６の一部であるかまたは背景の一部であるかに関する不確実性が少ないからである。
【００９３】
ブロック７０６で、３Ｄグラフカットセグメントをグローバルカラーモデルに基づいて適用する。３Ｄグラフカットセグメント化エンジン３０４は例えば、少数のキーフレーム、すなわち切り取られるビデオオブジェクトの良好なモデルとして選択したものを用いることで、ビデオオブジェクトの可視境界を発見し始めることができる。グローバルカラーモデルはこれらのキーモデルフレームからビデオシーケンス内の他のフレームに向かって動作し、ビデオオブジェクトの可視縁を背景色から区別することができる。３Ｄグラフを個々の画素ではなく領域上に構築するので、本セグメントは従来のセグメント化技術より高速である。
【００９４】
ブロック７０８で、２Ｄグラフカットセグメントをローカルカラーモデルに基づいて適用する。２Ｄローカル境界精練器３０６は例えば、境界精練化をビデオフレーム内部のユーザ選択ウィンドウ内に含まれるものに限定することができる。選択ウィンドウをビデオシーケンスのフレームに渡って自動的に伝播させることができ、ビデオオブジェクト境界の精練化に関する決定に用いる色をウィンドウのシーケンス内部のものに限定することができる。これにより、ビデオオブジェクトがその可視縁において微細な細部を有するときに、非常に正確なビデオオブジェクト境界を生成することができる。
【００９５】
結論
前述の議論はビデオオブジェクトのカットアンドペーストのシステムおよび方法の例を説明する。主題を構造的特徴および／または方法論的動作に固有な言語で説明したが、添付特許請求の範囲項で定義した主題は、上述の特定の特徴または動作に必ずしも限定されないことを理解されたい。むしろ、上述の特定の特徴および動作は、特許請求の範囲を実装する形態例として開示されている。
【図面の簡単な説明】
【００９６】
【図１】ビデオカットアンドペーストシステムの一例の図である。
【図２】ビデオオブジェクトカットアンドペーストプロセスの一例の概要図である。
【図３】ビデオオブジェクトカットアンドペーストエンジンの一例のブロック図である。
【図４】３Ｄグラフ構築の一例の図である。
【図５】ビデオオブジェクト境界を精練する技術の一例の図である。
【図６】３Ｄおよび２Ｄセグメント化結果の一例の図である。
【図７】ビデオオブジェクトをビデオシーケンスからセグメント化する方法の一例のフロー図である。
【図１】
2009500752.tif 000017
【図２】
2009500752.tif 000018
【図３】
2009500752.tif 000019
【図４】
2009500752.tif 000020
【図５】
2009500752.tif 000021
【図６】
2009500752.tif 000022
【図７】
2009500752.tif 000023