(57)【要約】本発明は、各フレームからカラー情報を取得するステップと、各フレームのカラーヒストグラムを決定するステップと、カラーヒストグラムを利用した境界検出技術を適用するステップとを有する映像シーケンスの連続するフレーム系列のセグメント境界を検出する方法を提供する。本方法は、映像シーケンスのフレームを一様カラーセグメントにセグメント化するステップを有する。さらに、映像シーケンスの連続するフレーム系列のセグメント境界を検出するシステムが提供される。本システムは、各フレームからカラー情報を取得する手段と、各フレームのカラーヒストグラムを決定する手段と、カラーヒストグラムを利用した境界検出技術を適用する手段とを有する。本システムは、映像シーケンスのフレームを一様カラーセグメントにセグメント化する手段を有する。境界検出技術には、ファミリーカラーヒストグラム法、加重平均カラーヒストグラム法、連続カラーヒストグラム法、確率的方法、ショットベースカラーヒストグラム法、モザイクカラーヒストグラム法及び計算可能マクロセグメント境界法が含まれる。
2006510072.tif 000002
【特許請求の範囲】
【請求項１】
映像シーケンスの連続するフレーム系列に対するセグメント境界を検出する方法であって、
各フレームからカラー情報を取得するステップと、
各フレームのカラーヒストグラムを決定するステップと、
前記カラーヒストグラムを利用した境界検出技術を適用するステップと、
前記映像シーケンスのフレームを一様カラーセグメントにセグメント化するステップと、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、
前記適用される境界検出技術は、前記連続するフレームのカラーヒストグラムに基づき比較測度を計算し、前記比較測度に基づきファミリーヒストグラムを生成するステップを有するファミリーカラーヒストグラム法であることを特徴とする方法。
【請求項３】
請求項２記載の方法であって、
前記比較測度は、
【数１】
2006510072.tif 000057
に基づく（ここで、ＤＣＨ［ｊ］はフレームｊとフレームｊ−１との間のカラーヒストグラム差分であり、ＣＨ［ｉ］［ｊ］はフレームｊにおいて定義されるｉ番目のｂｉｎのカラーヒストグラムであり、ｎはｂｉｎの個数である）ことを特徴とする方法。
【請求項４】
請求項２記載の方法であって、さらに、
前記比較測度が閾値より小さいとき、前記連続するフレームのカラーヒストグラムを第１ファミリーヒストグラムにマージするステップを有することを特徴とする方法。
【請求項５】
請求項２記載の方法であって、さらに、
前記比較測度が前記閾値より大きいとき、新しい一様カラーセグメントの第１フレームを示す新たなファミリーヒストグラムを生成するステップを有することを特徴とする方法。
【請求項６】
請求項１記載の方法であって、
前記適用される境界検出技術は、加重平均カラーヒストグラム高さと加重平均カラーヒストグラム高さ分散を計算するステップを有する加重平均カラーヒストグラム法であることを特徴とする方法。
【請求項７】
請求項６記載の方法であって、さらに、
前記分散の加重平均カラーヒストグラム高さ分散を計算するステップを有することを特徴とする方法。
【請求項８】
請求項６記載の方法であって、
前記加重平均カラーヒストグラム高さは、
【数２】
2006510072.tif 000058
に基づくことを特徴とする方法。
【請求項９】
請求項６記載の方法であって、
前記加重平均カラーヒストグラム高さ分散は、
【数３】
2006510072.tif 000059
に基づくことを特徴とする方法。
【請求項１０】
請求項７記載の方法であって、
前記分散の加重平均カラーヒストグラム高さ分散は、
【数４】
2006510072.tif 000060
に基づくことを特徴とする方法。
【請求項１１】
請求項７記載の方法であって、さらに、
前記加重平均＜ν＞ｊ及び＜α＞ｊを所定の閾値と比較し、前記加重平均が前記所定の閾値を超えるとき、新たな一様カラーセグメントを決定するステップを有することを特徴とする方法。
【請求項１２】
請求項１記載の方法であって、
前記適用される境界検出技術は、前記連続するフレーム間のカラーヒストグラムを比較測度を利用することにより比較するステップを有する連続カラーヒストグラム法であることを特徴とする方法。
【請求項１３】
請求項１２記載の方法であって、
前記比較測度は、
【数５】
2006510072.tif 000061
に基づく（ここで、ＤＣＨはフレームｊとフレームｊ−１との間のカラーヒストグラム差分であり、ＣＨ［ｉ］［ｊ］はフレームｊにおいて定義されるｉ番目のｂｉｎのカラーヒストグラムであり、ｎはｂｉｎの個数である）ことを特徴とする方法。
【請求項１４】
請求項１２記載の方法であって、さらに、
前記比較測度が閾値より大きいとき、新たな一様カラーセグメントを特定する第１フレームを決定するステップを有することを特徴とする方法。
【請求項１５】
請求項１記載の方法であって、
前記適用される境界検出技術は、Ｋａｌｍａｎフィルタリング技術に基づく確率的方法であることを特徴とする方法。
【請求項１６】
請求項１５記載の方法であって、さらに、
カラーヒストグラムｉのフレームｊにおける状態及び測定方程式を定義するステップを有することを特徴とする方法。
【請求項１７】
請求項１５記載の方法であって、さらに、
前記映像シーケンスの第１フレームから、カラーヒストグラムベクトルとカラーヒストグラム差分ベクトルを推定するため状態及び共分散関数を利用したＫａｌｍａｎフィルタリングを用いて前記映像シーケンスを処理するステップと、
前記共分散行列のＫａｌｍａｎフィルタリング推定が閾値より大きいとき、新たな一様カラーセグメントを決定するステップと、
を有することを特徴とする方法。
【請求項１８】
請求項１６記載の方法であって、
前記状態方程式は、
【数６】
2006510072.tif 000062
【数７】
2006510072.tif 000063
に基づく（ここで、ｗＣＨ［・］［ｊ］とｗＤＣＨ［・］［ｊ］は、カラーヒストグラムとカラーヒストグラム差分に対する状態ノイズ関数である）ことを特徴とする方法。
【請求項１９】
請求項１６記載の方法であって、
前記測定方程式は、
【数８】
2006510072.tif 000064
【数９】
2006510072.tif 000065
に基づく、（ここで、ｎＣＨ［・］［ｊ］とｎＤＣＨ［・］［ｊ］は、カラーヒストグラムとカラーヒストグラム差分に対する測定ノイズ関数である）ことを特徴とする方法。
【請求項２０】
請求項１記載の方法であって、
前記適用される境界検出技術は、ショットベースカラーヒストグラム法であることを特徴とする方法。
【請求項２１】
請求項２０記載の方法であって、
前記ショットベースカラーヒストグラム法は、
前記映像シーケンスの複数のショットをインデックス処理するステップと、
各ショットのカラーヒストグラムを計算するステップと、
前記各ショットのカラーヒストグラムを比較するステップと、
前記各ショットのカラーヒストグラムの比較結果に基づき、一様カラーセグメント境界を決定するステップと、
を有することを特徴とする方法。
【請求項２２】
請求項１記載の方法であって、
前記適用される境界検出技術は、モザイクカラーヒストグラム法であることを特徴とする方法。
【請求項２３】
請求項２２記載の方法であって、
前記モザイクカラーヒストグラム法は、
フレーム系列のモザイクを計算するステップと、
前記モザイクのカラーヒストグラムを決定するステップと、
フレームのカラーヒストグラムと前記モザイクのカラーヒストグラムを比較するステップと、
前記モザイクのカラーヒストグラムが前記フレームのカラーヒストグラムに等しいとき、一様カラーセグメント境界を決定するステップと、
を有することを特徴とする方法。
【請求項２４】
映像シーケンスの連続するフレーム系列に対するセグメント境界を検出するシステムであって、
各フレームからカラー情報を取得する手段と、
各フレームのカラーヒストグラムを決定する手段と、
前記カラーヒストグラムを利用した境界検出技術を適用する手段と、
前記映像シーケンスのフレームを一様カラーセグメントにセグメント化する手段と、
を有することを特徴とするシステム。
【請求項２５】
請求項２４記載のシステムであって、
前記境界検出技術は、ファミリーカラーヒストグラム法であることを特徴とするシステム。
【請求項２６】
請求項２４記載のシステムであって、
前記境界検出技術は、加重平均カラーヒストグラム法であることを特徴とするシステム。
【請求項２７】
請求項２４記載のシステムであって、
前記境界検出技術は、連続カラーヒストグラム法であることを特徴とするシステム。
【請求項２８】
請求項２４記載のシステムであって、
前記境界検出技術は、確率的方法であることを特徴とするシステム。
【請求項２９】
請求項２４記載のシステムであって、
前記境界検出技術は、ショットベースカラーヒストグラム法であることを特徴とするシステム。
【請求項３０】
請求項２４記載のシステムであって、
前記境界検出技術は、モザイクカラーヒストグラム法であることを特徴とするシステム。
【請求項３１】
記憶媒体装置であって、
各フレームからカラー情報を取得するステップと、
各フレームのカラーヒストグラムを決定するステップと、
前記カラーヒストグラムを利用した境界検出技術を適用するステップと、
前記映像シーケンスのフレームを一様カラーセグメントにセグメント化するステップと、
前記セグメントデータを該記憶媒体装置に格納するステップと、
に従って生成される映像データの特徴を実現するシステムにより読み出し可能な記憶媒体装置。
【請求項３２】
映像プログラムのマクロセグメントのマクロ境界を検出する方法であって、
映像プログラムの一様セグメント化を実行するステップと、
各一様セグメントの累積カラーヒストグラムを生成するステップと、
前記一様セグメントの各累積カラーヒストグラムに対し、前記ヒストグラムの残りとの類似度を前記映像プログラムの終わりまでプロットする類似度曲線を生成するステップと、
時間セグメントと以降の時間セグメントの間の類似度を表すすべての類似度曲線を有する加法類似度曲線を生成するステップと、
前記加法類似度曲線上の接続されたノード間に不連続性が存在する場合、累積カラーヒストグラム系列間の類似性が確立しないように、前記マクロ境界を検出するステップと、
を有することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カラー情報に基づく映像シーケンスのセグメント化及びインデック処理を行うための方法及びシステムに関する。特に、カラーヒストグラムを利用して、番組のセグメントをカラー類似度を用いたシーンに分類する。
【背景技術】
【０００２】
コンピュータシステム及びネットワークにおけるデジタル画像及び映像の利用の急激な増大により、画像及び映像データをそれらのコンテンツに基づき効果的にインデックス処理、格納及び抽出するマルチメディアデータベースシステムの必要性が急激に増大してきた。このように増大する必要性をより良くサポートする様々な技術が開発されてきた。ユーザによる視覚類似性に基づく画像の抽出を可能にするコンテンツベースの画像抽出技術が開発される一方、連続的な映像シーケンスを効果的にインデック処理および抽出することができるように、視覚的に一致したユニットにセグメント化するための映像ショット境界検出技術が開発されてきた。
【０００３】
映像プログラムは、一般に異なる映像セグメントを編集したものから構成されている。これらのセグメントは、典型的には、ショットまたはシーンとして分類される。例えば、１つのシーンは、アクションが行われる場所または設定である。１つのシーンは、連続するアクションまたはイベントを描く１以上のショットから構成することができる。１つのショットは、中断されることなく１台のカメラにより連続的に撮影されたビューである。各ショットは、テイク（ｔａｋｅ）である。同じアクションの追加的なショットが同一の設定から設営されるとき、得られるショットは「リテイク（ｒｅｔａｋｅ）」となる。このため、各ショットは連続するフレームのシーケンス、すなわち、１台のカメラからの連続的かつ中断のない動作期間中に生成された画像から構成される。例えば、動画では、ショットは、記録の開始から停止までに１台のカメラにより生成されるフィルムに記録された連続するフレーム系列である。ライブのテレビ放送では、ショットは、１台のカメラにより放映された時間から他のカメラに切り替えられるまでのスクリーン上に映し出される画像から構成される。ショットは、２つの連続するショットの間の境界（「カット（ｃｕｔ）」として知られる）が画定されるアブラプトモード（ａｂｒｕｐｔ  ｍｏｄｅ）（例えば、バットエディット（ｂｕｔｔ−ｅｄｉｔ）またはスイッチなど）あるいは１つのショットから次のショットへの段階的移行をもたらすフェードやディゾルブ（ｄｉｓｓｏｌｖｅ）などの他の多くの編集モードの１つを介し結合することが可能である。利用される移行モードは、一般に視聴者がイベントの進捗についていくことを支援する時間及び場所の変化に関する手がかりを与えるため、ディレクタにより選ばれる。
【０００４】
異なるショット間のアブラプトな移行を検出する自動映像インデックス処理方法が知られている。例えば、米国特許第６，０５５，０２５号は、そのような方法を開示している。「シーン」は、実質的に類似した情報を伝達する密接に関連したコンテンツを有するフレームシーケンスと通常みなされる。カメラが固定されることにより、「静止画ショット」が生成されるケースがある。しかしながら一般に、映像プログラムは、静止画ショットだけでなく、「動画ショット」（すなわち、パン、ティルト及びズームなどのカメラ処理によるショット）からも構成される。このため、カメラの動きにより、各ショットのフレームシーケンスのコンテンツは、大きく変化する可能性があり、これにより、与えられたシーンに複数のショットが存在することとなる。このため、異なるショット間の境界がシーン境界となる一方、カメラの挙動はショット内のシーン変化をもたらすため、このような境界は映像プログラムに起こるすべてのシーン境界の一部となるかもしれない。従って、シーンは編集効果のない連続したフレーム群であるショットの集まりとして定義することができる。従来技術はまた、やりとりに関係する２人の俳優を交互に映す対話シーンなどの同じテーマを有する複数のショットを有するものとしてシーンを定義している。しかしながら、複数のシーンを含む１つの長いショットから始まる映画などのようにこの定義の例外はある。本発明に対しては、シーンは典型的にはいくつかのショットから構成される。
【０００５】
従来技術では、映像プログラムにおけるショット境界の様々な検出方法が開示されているが、これらの方法の何れもが映像インデックス処理に対しては十分適したものではない。１つの理由としては、ショットはしばしば偽物であり、すなわち、シーン情報に真の変化を示すものでないカメラフラッシュなどのアーチファクトにより生成されるためである。映像をいくつかのシーンにセグメント化することは、映像によりキャプチャされる真の情報により近いものとなる。
【０００６】
本発明では、「一様な映像セグメント」という用語は、与えられた視覚的性質が一定時間において一様であるかあるいはほぼ一定である連続する映像フレームの集まりを示す。特に本発明は、カラーベースの一様性を扱っている。
【０００７】
カラー情報は、映像のインデックス化のための大変有用な視覚的手がかりである。典型的には、映像の一様なカラーセグメントは、「一定の」全体的なカラー分布を有する連続したフレームの集まりである。例えば、サッカーやゴルフなどの屋外スポーツでは、映像に芝生や空が存在することによる「緑」と「青」が優勢となっている。このような屋外シーンに対しカラーヒストグラムが計算される場合、「緑」と「青」のｂｉｎが優勢となる。すなわち、それらはｂｉｎあたり最大数となるであろう。
【０００８】
カラースーパーヒストグラムは、カラーヒストグラムを逐次的に更新することにより生成される。この生成方法の１つは以下のようなものである。ＭＰＥＧ−１／２／４などの映像では、連続したフレームはＩ／Ｐ／Ｂフレームとして構成され、これらのフレームは、ＩＢＢＢＰＢＢＢＰＢＢＢＰＢＢＢなどの繰り返されるグループとなる。カラーヒストグラムは、選択されたフレームまたはすべてのフレームに対し生成される。処理スピードの観点から、時間領域においてフレームをサブサンプリングすることが可能である。ＩフレームまたはＢフレームがサンプリングレートにより取得される。カラースーパーヒストグラムが、連続するカラーヒストグラムの情報を合成することにより生成される。カラースーパーヒストグラムは映像のロウバストかつ安定的なカラー表示であるため、カラーヒストグラムは、一様なカラーセグメントを検出するための重要なツール及び特徴となる。一般に、カラー情報は、一様なカラーセグメントへの映像インデック処理に基礎的なものである。従って、スーパーヒストグラムは、典型的には、映像の特徴付けに利用される。スーパーヒストグラムは、ジャンルの特定、プログラム境界の検出及び視覚サマリの生成に利用可能である。例えば、プログラム境界の検出に利用することにより、ニュース番組に対して、サインフェルド（Ｓｅｉｎｆｅｌｄ）のエピソードを特定することができる。しかしながら、本発明の一様カラーセグメント境界検出は、ニュース番組の個々のストーリーセグメントへのセグメント化を可能にする。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
以上より、映像プログラムにおいて一様なカラーセグメント境界を検出するための効率的かつ適切な方法及びシステムが必要とされる。
【００１０】
本発明の課題及び効果は、本発明の実施例に供する以下の説明に与えられ、それから明らかとなるであろう。本発明の追加的な効果は、添付された図面と共に、詳細な説明及び請求項に具体的に示される方法及びシステムにより実現及び達成されるであろう。
【課題を解決するための手段】
【００１１】
実現及び記載されるような本発明の課題に従う上記及び他の効果を実現するため、本発明は、映像シーケンスにおける連続するフレーム系列に対してセグメント境界を検出する方法を有する。本方法は、各フレームからカラー情報を取得するステップと、各フレームに対しカラーヒストグラムを決定するステップと、前記カラーヒストグラムを利用して境界検出技術を適用するステップとを有する。最後に、本方法は、映像シーケンスのフレームを一様なカラーセグメントにセグメント化するステップを有する。
【００１２】
本発明はまた、映像シーケンスにおける連続するフレーム系列に対しセグメント境界を検出するシステムを有する。本システムは、各フレームからカラー情報を取得する手段と、各フレームに対しカラーヒストグラムを決定する手段と、前記カラーヒストグラムを利用して境界検出技術を適用する手段とを有する。最後に、本システムは、映像シーケンスのフレームを一様なカラーセグメントにセグメント化する手段を有する。この境界検出技術は、ファミリーカラーヒストグラム法、加重平均カラーヒストグラム法、連続カラーヒストグラム法、確率的方法、ショットベースカラーヒストグラム法、モザイクカラーヒストグラム法及び計算可能マクロセグメント境界法を含む。
【００１３】
上記の一般的な説明と以下の詳細な説明は共に例示的なものであり、請求される本発明のさらなる説明を提供するためのものであるということは理解されるであろう。
【００１４】
本明細書に含まれ、その一部を構成する添付された図面は、本発明の方法及びシステムのさらなる理解を図示及び提供するため含まれる。説明と共に、図面は、本発明の原理を説明するのに利用される。
【発明を実施するための最良の形態】
【００１５】
以下の説明は、当業者による本発明の構成及び利用を可能にするよう与えられたものである。好適な実施例に対する様々な変更は、当業者には容易に明らかとなり、ここに与えられる開示は、本発明及び添付された請求項の趣旨及び範囲を逸脱することなく、他の実施例及び応用に適用可能である。従って、本発明は、記載される実施例に限定されるものでなく、与えられる開示に従う最も広範な範囲と一致すべきものである。
システム
映像シーケンスにおいて一様なカラーセグメントの境界を検出する方法は、好ましくは、図１に示されるような従来の汎用コンピュータシステム１００を用いて実現される。ここで、図２のプロセスは、コンピュータシステム１００の内部で実行されるアプリケーションプログラムなどのソフトウェアとして実現されてもよい。特に、一様なカラーセグメントの境界を検出する方法の各ステップは、コンピュータにより実行されるソフトウェアとして符号化された命令により実行される。ソフトウェアは、映像一様カラーセグメント検出方法を実行する部分と、後者とユーザとの間のユーザインタフェースを管理する部分との２つの部分に分割されてもよい。ソフトウェアは、例えば後述の記憶装置を含むコンピュータ読み出し可能な媒体に格納されてもよい。ソフトウェアは、コンピュータ読み出し可能媒体からコンピュータにロードされ、その後コンピュータにより実行される。記録されたこのようなソフトウェアやコンピュータプログラムを有するコンピュータ読み出し可能媒体は、コンピュータプログラムプロダクツである。コンピュータにおけるコンピュータプログラムプロダクツの利用は、好ましくは、本発明の実施例による映像一様カラーセグメント境界を検出する効果的な装置から構成される。
【００１６】
コンピュータシステム１００は、コンピュータモジュール１０５と、キーボード１１０やマウス１１５などの入力装置と、プリンタ１２０や表示装置１２５などの出力装置とを有する。変調復調（モデム）送受信機の形態による通信装置１３０は、電話線１４０や他の機能媒体を介し接続可能な通信ネットワーク１３５と通信するためのコンピュータモジュール１０５により利用可能である。通信装置１３０は、インターネット及びローカルエリアネットワーク（ＬＡＮ）やワイドエリアネットワーク（ＷＡＮ）などの他のネットワークシステムとアクセスするために利用することができる。
【００１７】
コンピュータモジュール１０５は、典型的には、少なくとも１つのプロセッサユニット１４５（ＣＰＵ：中央処理ユニット）と、半導体ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）やＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）から構成されるメモリユニット１５０と、ビデオインタフェース１５５と、キーボード１１０やマウス１１５、及び任意的にジョイスティック（図示せず）のためのＩ／Ｏインタフェース１６０と、通信装置１３０のためのインタフェース１６５とを有する。記憶装置１７０が設けられ、典型的には、ハードディスクドライブ１７５とフロッピー（登録商標）ディスクドライブ１８０とを有する。磁気テープ装置（図示せず）またはスマートメディアタイプドライブがまた利用されてもよい。コンピュータモジュール１０５の上述の構成要素１４５〜１６０は、典型的には、インタコネクトバス１９０あるいは赤外線及びブルートゥース技術などのデータ転送に適した他の手段を介し通信し、当業者には既知なコンピュータシステム１００の従来の動作モードを実現する。本発明の実施例を実現可能にするコンピュータの例としては、ＩＢＭ−ＰＣ互換製品、ＳｕｎのＳｐａｒｃｓｔａｔｉｏｎ、ＡｐｐｌｅのＭａｃｉｎｔｏｓｈコンピュータまたはこれらから派生した同様のコンピュータシステムがあげられる。
【００１８】
典型的には、好適な実施例のアプリケーションプログラムは、ハードディスクドライブ１７５に設けられ、プロセッサ１４５による実行により読み出し及び制御が行われる。当該プログラムおよびネットワーク１３５から取得されたデータの中間的格納は、おそらくハードディスクドライブ１７５と共に半導体メモリ１５０を用いて実現されてもよい。いくつかの例では、アプリケーションプログラムは、ＣＤ−ＲＯＭやフロッピー（登録商標）ディスク上に符号化され、それぞれに対応するドライブ１８５や１８０を介し読み出されることによりユーザに提供されてもよいし、あるいはモデム通信装置１３０を介しネットワーク１３５からユーザにより読み出されてもよい。さらに、ソフトウェアはまた、磁気テープを含む他のコンピュータ読み出し可能媒体、ＲＯＭ集積回路、光磁気ディスク、コンピュータモジュール１０５と他の装置との間の無線または赤外線送信チャネル、ＰＣＭＣＩＡカードなどのコンピュータ読み出し可能カード、電子メール送信やウェブサイトに記録された情報を含むインターネット及びイントラネットなどからコンピュータシステム１００にロード可能である。上記は、該当するコンピュータ読み出し可能媒体の単なる一例である。本発明の範囲及び趣旨から逸脱することなく、他のコンピュータ読み出し可能媒体が利用されてもよい。
【００１９】
コンピュータシステム１００は、一様カラーセグメント境界検出法への入力として用いられる大量の映像データを格納するための容量を有する。映像データは、ＤＶＤ−ＲＯＭドライブ１８５を介し、または入力１６５を介しビデオレコーダ（図示せず）から直接的にコンピュータシステム１００に入力されるようにしてもよい。
【００２０】
あるいは、映像シーケンスにおける一様なカラーセグメントの境界を検出する方法は、図２の機能またはサブ機能を実行する１以上の集積回路などの専用ハードウェアにより実現されてもよい。このような専用ハードウェアは、ビデオカメラやＶＣＲなどに内蔵されてもよく、グラフィックプロセッサ、デジタル信号プロセッサや１以上のマイクロプロセッサ及び関連するメモリを含むようにしてもよい。
一般的方法
図２を参照するに、映像シーケンスにおいて一様なカラーセグメントの境界を検出する方法が図示される。本方法は、映像シーケンスのセグメント化及びインデックス処理のためのいくつかの境界検出技術を利用する。本発明の好適な実施例によると、各技術は、映像シーケンスから取得されたカラー情報に基づくものである。カラーは、一般的な映像セグメント化及びインデックス処理の強力な視覚属性である。これは、「一様な」カラーインターバルに関する映像のセグメント化を含む。
【００２１】
映像一様カラーセグメントは、「一定の」全体的または支配的カラーを有する連続するフレームの集まりである。本発明では、これら支配的カラーをキャプチャするため、カラーヒストグラムが利用される。カラーヒストグラムとは、１つの画像における各カラーのカウントである。好ましくは、カラー情報を利用して、プログラムのセグメントを一様なカラーセグメントに分類する。
【００２２】
「一様カラーセグメント」とは、カラー属性が一様である、すなわち、一定期間におけるカラーヒストグラム情報に基づき、一定または略一定であるセグメントとして定義することができる。
【００２３】
従って、図２に示されるように、映像シーケンスにおいて一様カラーセグメント境界を検出する方法は、映像シーケンス２００の各フレームに対しカラー情報２０５を取得するステップを有する。ステップ２１０において、取得したカラー情報に基づき、各フレームに対するカラーヒストグラムが決定される。映像フレームからのカラーヒストグラムの導出は、当該技術分野では周知である。一般に、すべての画像は、パレットと呼ばれるいくつかのカラーにより記述されている。パレットのカラー数は、用途に応じて選択することができる。ヒストグラムは、与えられたカラー領域による画像の画素数をカウントする。各ヒストグラムは、フレーム番号と関連付けされている。上述及び当該分野では周知であるように、画像のカラー分布は、各ｂｉｎが各カラーコンポーネントの値の範囲に対応するヒストグラムにより表現することができる。例えば、８ビット画像に対して、カラーコンポーネントは、０〜２５５の値の範囲をとる。典型的には、カスタマイズ（または非一様）量子化と一様量子化の２つのタイプの量子化方法がある。カスタマイズ方法では、本発明の目的のためには、網羅的なパレットより小さいものを選ぶことが好ましい。すべてのフレームに出現するような黒、白及び肌色などのカラーは、好ましくは、パレットには選ばれず、あるいは低いウェートが与えられる。白と黒のシェードを説明する明るいグレー、中間のグレー及び暗いグレーに対しては、デフォルトのｂｉｎを設けることができる。これらには、他のｂｉｎより低いウェートを与えることができる。
【００２４】
あるいは、他の一様量子化手法が利用可能である。カラー量子化は、典型的には、映像ヒストグラムの計算における第１ステップである。カラー量子化には様々な方法があり、それらは当該技術分野では周知である。関係する要因としては、どのカラー空間（ＨＳＶＣ、ＹＵＶ、ＲＧＢなど）が利用されるか、いくつのカラーが選ばれるか、カラー空間の分割方法（例えば、９、３０、９０、９００など）があげられる。例えば、１２８個のｂｉｎがＹ（ルミナンス）に対し利用可能であり、あるいはトータルで２８８個のｂｉｎがスケールダウンされたＹ、Ｃｒ（クロミナンス−赤）、Ｃｂ（クロミナンス−青）に対し利用可能である。多くの利用可能な可能性が存在する。例示のため、また当該空間においてＭＰＥＧは動作しているため、Ｙ、Ｃｒ及びＣｂカラー空間が以降において利用される。あるいは、ＨＳＢ（Ｈｕｅ、Ｓａｔｕｒａｔｉｏｎ、Ｂｒｉｇｈｔｎｅｓｓ）カラー空間を用いて、基本カラーのｂｉｎを定義することができる。
【００２５】
ステップ２１０において、ヒストグラムが各フレームに対し定義された後、以下で詳述される境界検出技術の１つがステップ２１５において適用される。境界検出技術の適用に続いて、ステップ２２０において、映像ストリームは一様カラーセグメントにセグメント化される。
特定の境界検出技術の適用
時間的には、映像ストリームは、連続するフレームまたはインタレースフィールドの集まりから構成される。これらのフレームは、ＭＰＥＧ（１，２，４）映像ストリームのＩフレーム位置または抽出による映像ショットに従ってインデックス処理することができる。ＭＰＥＧは、Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔ  Ｇｒｏｕｐを表す映像圧縮規格の１つである。映像ショットは、当該技術分野では周知なＤＣＴ（離散コサイン変換）ベースの方法などの他の方法に基づき抽出することができる。例えば、参照することによりここに含まれるＰｅｔｅｒ  Ｄ．Ｓｙｍｅｓによる「Ｖｉｄｅｏ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｄｅｍｙｓｔｉｆｉｅｄ」（ＭｃＧｒａｗ−Ｈｉｌｌ  Ｐｒｏｆｅｓｓｉｏｎａｌ  Ｐｕｂｌｉｓｈｉｎｇ；ＩＳＢＮ：００７１３６３２４６；１ｓｔ  ｅｄｉｔｉｏｎ；Ｄｅｃｅｍｂｅｒ  ２０，２０００）によりこのような方法が開示されている。
【００２６】
図３を参照するに、Ｎ個のフレームを含む映像シーケンスのＩフレームの典型的な集まりが示される。各Ｉフレームに対し、９ｂｉｎのカラーヒストグラムＣＨ［ｉ］［ｊ］が存在する（ここで、インデックスｉはｂｉｎ位置を示し、インデックスｊは映像シーケンスのフレーム位置を示す）。カラー「一様性」に基づく映像シーケンスにおける境界を検出するための様々な技術が、以下において説明される。「一様性」の概念は、説明される各方法に対し異なっている。さらに、映像圧縮のＭＰＥＧの世界では、後述されるすべての技術と共に、例えば、Ｉ、ＰまたはＢタイプフレームの任意のタイプのフレームが利用可能である。好ましくは、Ｐ及びＢフレームによる解像度のロスによりＩフレームが利用される。
【００２７】
［１．ファミリーカラーヒストグラム］
この方法において、「ファミリー」カラーヒストグラムＣＨＦ［ｉ］［ｊ］は以下のように生成される。１≦ｊ≦Ｎ（ただし、ｊはフレームインデックス、ｉはｂｉｎインデックスである）に対して、図４を参照するに、ｊ番目のフレームのカラーヒストグラムＣＨ［ｉ］［ｊ］が、以下の差分、
【数１０】
2006510072.tif 000003
（ただし、
［外１］
2006510072.tif 000004
は後述されるようなＬ１、Ｌ２など）を計算することにより「ファミリー」カラーヒストグラムＣＨＦ［ｉ］［ｊ］と比較される（ステップ４００）。限定的でなく単なる例示のため、９個のｂｉｎが利用されている。ＤＣＨＦ［ｊ］の式の「ファミリー」カラーヒストグラムフレームインデックスは、ｊ−１である。
（ａ）ｊ番目のフレームのＤＣＨＦ［ｊ］が閾値τＤＣＨＦより小さい場合、ＣＨ［ｉ］［ｊ］はＣＨＦ［ｉ］［ｊ−１］と「マージ」され（ステップ４１５）、ＣＨＦ［ｉ］［ｊ］が生成される。この「マージ」は、後述されるように、単なる加重平均またはＫａｌｍａｎフィルタリングを利用することにより実行することができる。
（ｂ）ｊ番目のＤＣＨＦ［ｊ］が閾値τＤＣＨＦより大きい場合、ＣＨ［ｉ］［ｊ］は新たな「ファミリー」カラーヒストグラムをスタートさせ（ステップ４１０）、ｊ番目のフレームが次の映像「一様カラーセグメント」の第１フレームとみなされる。
（ｃ）ステップ（ａ）及び（ｂ）は、好ましくは、ｊ＝Ｎとなるまで繰り返される。このプロセスの終わりで、「一様」カラーパレットを有する連続する映像「一様カラーセグメント」の集まりが決定される。各「ファミリー」カラーヒストグラムにおいて複数のｂｉｎが支配的となる可能性がある。
【００２８】
上述のように、カラーヒストグラムは各フレームに対し計算され、最も近いファミリーヒストグラムを求めるため、以前に計算したファミリーヒストグラムを検索する。現在のヒストグラムＣＨｃ（ＣＨ［ｉ］［ｊ］に等しい）と以前のファミリーヒストグラムＣＨｐ（ＣＨＦ［ｉ］［ｊ−１］に等しい）との比較は、様々なヒストグラム比較法を用いて計算することができる。本発明の他の実施例によると、ヒストグラムの差Ｄを計算するため、以下の方法を利用することが可能である。
【００２９】
（１）Ｌ１距離測度を用いたヒストグラムの差は、以下の式を用いることにより計算可能である。
【００３０】
【数１１】
2006510072.tif 000005
ここで、Ｎは用いられるカラーｂｉｎの合計である（例えば、９個のｂｉｎが利用可能である）。この式を用いて得られる値は、０から各画像の最大画素数の２倍までの範囲をとる。類似度のパーセント表示を取得することが好ましいため、上記値は、トータルの画素数で除することにより正規化される。この正規化された値は０と１の範囲に属し、この値が０に近いほど画像が類似し、１に近いほど画像が非類似となることを意味する。
【００３１】
（２）あるいは、Ｌ２距離測度を用いたヒストグラムの差は、以下の式を用いることにより計算可能である。
【００３２】
【数１２】
2006510072.tif 000006
ケース（１）と同様に、Ｄの値は好ましくは正規化される。Ｌ２ノルムは、平方された値である。しかしながら、それを距離関数として使用するためには、平方根（例えば、ユークリッド距離など）が必要である。
【００３３】
（３）ヒストグラムインタセクション（ｉｎｔｅｒｓｅｃｔｉｏｎ）は、以下の式を用いて計算可能である。
【００３４】
【数１３】
2006510072.tif 000007
この式を用いて取得される値は、０から１までの範囲に属する。値が０に近いほど画像は非類似であり、値が１に近いほど画像は類似することを示す。同様の類似の解釈によりヒストグラムを比較するため、距離測度として式
Ｄ＝１−Ｉ
が用いられる。
【００３５】
（４）２つの画像ヒストグラムに対するカイ二乗テストが、以下の式を用いて計算される。
【００３６】
【数１４】
2006510072.tif 000008
このケースにおいて、上記値は０からカラーｂｉｎの個数Ｎまでの範囲に属する。この値は、Ｎを用いて正規化される。すなわち、
【数１５】
2006510072.tif 000009
（５）ｂｉｎ単位のヒストグラムインタセクションが、以下の式を用いて計算される。
【００３７】
【数１６】
2006510072.tif 000010
ヒストグラムインタセクションと同様に、値が小さいほど非類似を意味し、値が大きいほど画像が類似していることを意味する。上述の測度と一致させるため、当該距離は、
【数１７】
2006510072.tif 000011
を用いて計算される。
【００３８】
上記５つの方法は、ヒストグラム間の距離の異なる測定方法を可能にする。上記５つの距離測度の何れか１つが本発明の実際の適用において利用可能であることを当業者は理解するであろう。さらに、従来技術は、利用可能な他の距離測度（例えば、Ｍａｈａｌａｎｏｂｉｓ距離など）を開示している。
【００３９】
［２．加重平均カラーヒストグラム］
本発明の他の実施例によると、上記方法の異なる実現方法は、加重平均カラーヒストグラム高さ、加重平均カラーヒストグラム高さ分散、及びこの分散の加重平均カラーヒストグラム分散を計算することに関する。
（ａ）ｊ番目のフレームのｉ番目のｂｉｎ加重平均カラーヒストグラム高さ＜ｈ＞ｉ，ｊは、
【数１８】
2006510072.tif 000012
である。ここで、
【数１９】
2006510072.tif 000013
は、ｊ−１時点で規定されている平均ヒストグラム高さ＜ｈ＞ｊ−１に依存するガウス加重関数を表し、σｈは、高さ分散パラメータである。
（ｂ）加重平均カラーヒストグラム高さ分散＜ν＞ｉは、
【数２０】
2006510072.tif 000014
である。ここで、
【数２１】
2006510072.tif 000015
であり、
【数２２】
2006510072.tif 000016
は、ガウス分散加重であり、σνは分散パラメータである。
（ｃ）分散の加重平均カラーヒストグラム高さ分散＜α＞ｉは、
【数２３】
2006510072.tif 000017
である。ここで、
【数２４】
2006510072.tif 000018
であり、
【数２５】
2006510072.tif 000019
は、ガウス加重であり、σαは加速分散パラメータである。
【００４０】
上記３つの平均は、新しい「カラー」と新しい一様カラーセグメントの出現を示す急激な変化チェックするため、Ｉフレームまたは映像サブサンプリングフレームの連続時点により比較される。このとき、上記平均は、例えば、０から１までで可変となる値を得るため、正規化される。
【００４１】
これら平均の変動にはトレンドがある。連続かつ一貫して大きな分散は、パン一様カラーセグメントなどに対応する。最後に、新しいカラーが出現すると、上記平均はより多くの情報を有することとなり、以前から存在していたｂｉｎより大きな加重が与えられる。＜ν＞ｊと＜α＞ｊが所定の閾値を超えると、新しい一様カラーセグメントが検出され、そうでない場合には、時点ｊ−１と同様の一様カラーセグメントが存在することとなる。
【００４２】
［３．連続カラーヒストグラム］
この技術では、本発明の他の実施例により、連続するフレームの間のカラーヒストグラムを比較することにより、映像境界が検出される。従って、ＣＨ［ｉ］［ｊ］とＣＨ［ｉ］［ｊ−１］がフレームｊとｊ−１において規定されるｉ番目のｂｉｎの２つのカラーヒストグラムである場合、以下の差分測度を次のように計算する。
【００４３】
【数２６】
2006510072.tif 000020
ここでは、９個のｂｉｎが一例として用いられている。
【００４４】
ＤＣＨＳ［ｊ］が閾値τＤＣＨＳより大きい場合、ｊ番目のフレームはカラー境界として決定され、新しい「一様」カラー映像セグメントの第１フレームとみなされる。
【００４５】
［４．確率的方法］
本発明のさらなる他の実施例によると、確率的方法はＫａｌｍａｎフィルタリングに基づくものである。Ｋａｌｍａｎフィルタは、実質的に、いくつかの前提となる条件が満たされるとき、推定されるエラー共分散を最小化するという意味で最適な予測器―訂正器タイプの推定器を実現する数式群である。Ｋａｌｍａｎフィルタにより解決される問題は、所与の時点における画素の位置及び測度などの特徴ベクトルの推定が与えられると、時点ｔ＋１における推定されるベクトル値がどのようになるかということである。これは、状態方程式の動作に関する知識と与えられた測定方程式を利用する。
【００４６】
Ｋａｌｍａｎフィルタリングは、従来技術において周知である。
【００４７】
本発明による技術の一般的アイデアは、ｉによりインデックス付けされるＮ個のｂｉｎに対するカラーヒストグラムＣＨ［ｉ］［ｊ］が「一様」となる映像インターバルに「追従」することである。各時点ｊに対し、ＣＨ［ｉ］［ｊ］はＮ個のコンポーネントからなるベクトルを表す。Ｋａｌｍａｎフィルタリングの用語では、これは状態ベクトルと呼ばれる。
【００４８】
Ｋａｌｍａｎフィルタリング法を記述する方程式として、状態方程式と測定方程式の２つがある。
【００４９】
各方程式を説明する前に、以下の用語が定義される。ｊ番目のフレームに対し定義されるカラーヒストグラムベクトル
【数２７】
2006510072.tif 000021
は、各カラーｂｉｎに１つずつの合計９個のコンポーネントを有する。カラーヒストグラム差分ベクトルＤＣＨ［ｊ］は、
【数２８】
2006510072.tif 000022
として定義される。ここで、
［外２］
2006510072.tif 000023
は測度演算子を示す。
【００５０】
ｉ番目のカラーヒストグラムベクトルとカラーヒストグラム差分ベクトルに対し、時点ｊにおける以下の状態方程式を得る。
【数２９】
2006510072.tif 000024
【数３０】
2006510072.tif 000025
ここで、ｗＣＨ［・］［ｊ］とｗＤＣＨ［・］［ｊ］は、それぞれカラーヒストグラムとカラーヒストグラム差分に対する状態ノイズ関数を表す。同様に、２つの測定方程式は、
【数３１】
2006510072.tif 000026
【数３２】
2006510072.tif 000027
となる。ここで、ｎＣＨ［・］［ｊ］とｎＤＣＨ［・］［ｊ］は、それぞれカラーヒストグラムとカラーヒストグラム差分に対する測定ノイズ関数である。
【００５１】
上記４つの方程式は、単一の状態及び測定方程式を形成するよう合成することができる。ベクトルＣＨ［ｊ］とベクトルＤＣＨ［ｊ］を用いて、離散状態ベクトルＳ［ｊ］は、
【数３３】
2006510072.tif 000028
により定義される。Ｓ［ｊ］に対する時間進化状態モデルは、
【数３４】
2006510072.tif 000029
となる。ここで、
【数３５】
2006510072.tif 000030
であり、Ｆ１，ｊ，．．．，Ｆ４，ｊは９×９の行列であり、Ｆ３，ｊ＝０（０は、９×９の零行列）であり、
【数３６】
2006510072.tif 000031
である。ただし、
【数３７】
2006510072.tif 000032
は、１×９の単位行列である。特に、式（８．１）と（８．２）を生成するため、
【数３８】
2006510072.tif 000033
である。ベクトルｗ［ｊ］は、平均が０の離散ガウスタンダム変数（ＲＶ）である。すなわち、
【数３９】
2006510072.tif 000034
である。ここで、Ｅ［・］はＲＶの期待値を表し、ｊ＝ｋの場合にはδｊｋ＝１であり、それ以外の場合にはδｊｋ＝０となる。測定モデルＭ［ｊ］は、
【数４０】
2006510072.tif 000035
である。ここで、
【数４１】
2006510072.tif 000036
である。ただし、Ｈ１，ｊ，．．．，Ｈ４，ｊは９×９の行列であり、ベクトルｎ［ｊ］は、ベクトルｗ［ｊ］と同様の性質を有するノイズである。すなわち、
【数４２】
2006510072.tif 000037
である。特に、式（９．１）と（９．２）を生成するため、
【数４３】
2006510072.tif 000038
である。状態及び測定も出るが与えられると、Ｋａｌｍａｎフィルタ予測及びフィルタリング更新方程式は、以下のようになる。
予測
【数４４】
2006510072.tif 000039
【数４５】
2006510072.tif 000040
フィルタリング
【数４６】
2006510072.tif 000041
【数４７】
2006510072.tif 000042
である。ただし、
【数４８】
2006510072.tif 000043
【数４９】
2006510072.tif 000044
【数５０】
2006510072.tif 000045
【数５１】
2006510072.tif 000046
である。
【００５２】
【数５２】
2006510072.tif 000047
は、時点ｊ−１までの測定値が与えられたとき、時点ｊにおける状態ベクトル
【数５３】
2006510072.tif 000048
の推定を示す。
【００５３】
【数５４】
2006510072.tif 000049
は、時点ｊ−１において推定される状態ベクトルを示すという相違はあるが、
【数５５】
2006510072.tif 000050
と類似している。
【００５４】
【数５６】
2006510072.tif 000051
は、時点ｊ−１までの測定値が与えられたとき、時点ｊにおいて推定される共分散行列を示し、
【数５７】
2006510072.tif 000052
は、時点ｊ−１までの測定値が与えられたとき、時点ｊ−１において推定される共分散行列を示す。
【００５５】
時間の経過とともに、ｊを介しＣＨ［ｉ］［ｊ］は更新される。Ｋａｌｍａｎフィルタリングでは、ＣＨ［ｉ］［ｊ］の進展が決定される。好ましくは、エラー、すなわち、ＣＨ［ｉ］［ｊ］とそれの「平均」ベクトルとの差がまた決定される。カラーヒストグラム差分ベクトルは、時間的に連続するカラーヒストグラム間におけるＤＣＨ［ｉ］［ｊ］＝ＣＨ［ｉ］［ｊ−１］−ＣＨ［ｉ］［ｊ］により定義される。ＤＣＨ［ｉ］［ｊ］の利用は、ＣＨ［ｉ］［ｊ］の変化、すなわち、「速度」を決定するためである。ＣＨ［ｉ］［ｊ］が絶対的に一定である場合、ＤＣＨ［ｉ］［ｊ］はゼロとなる。
【００５６】
より多くのサンプルが得られると、この結合状態ベクトルの「予測」はより良好なものとなる。固定的な背景と前景のカラーパレットを有するニュース配置などの与えられた映像一様カラーセグメントでは、カラーヒストグラムベクトルの決定に用いられるＩフレームが多いほど、その予測はより良好なものとなる。
【００５７】
測定モデル
【数５８】
2006510072.tif 000053
は、カラーヒストグラムの実際の測定値とそれの差分に対応する。Ｋａｌｍａｎフィルタリングでは、予測とフィルタリング方程式の２つの方程式がある。予測部は、推定された状態ベクトルと分散行列が同数のフレームが与えられたときにある時点からそれに連続する時点までどのように進展したか判断する一方、フィルタリング部は、「新たな」フレーム情報を追加することにより、状態ベクトルと分散行列がどのように進展したか判断する。
【００５８】
Ｋａｌｍａｎフィルタリングの基礎となる概念は、フレーム数が増えるに従い、分散行列の要素はゼロに近づき、状態ベクトルの要素は「一定」となる。典型的には、ＤＣＨの要素はゼロに近づく一方、ＣＨの要素は一定となる。
【００５９】
従って、一様カラーセグメントの変化がある場合、カラーパレットが変化することが予想され、これにより、予測とフィルタリングはもはや満たされなくなるであろう。このため、新しい一様カラーセグメントの開始時を決定するための尺度を利用することが好ましい。これは、測定された差分ベクトルＭＤＣＨ［ｊ］と推定された差分ベクトル（Ｋａｌｍａｎフィルタリングから）を比較することにより実行可能である。測定された差分ベクトルが推定された差分の２０％などの所定の閾値より大きい場合、新たな一様カラーセグメントが開始される。これにより、一様カラーセグメント境界の検出が可能となる。
【００６０】
典型的には、Ｋａｌｍａｎフィルタリングは、変数の分散が漸近的にゼロとなるように、すなわち、分散が時間的に一定となるように、変数の時間的推移を決定するためのものである。しかしながら、オブジェクトの方向及び／または速度などの変数の急激な変化が生じた場合、Ｋａｌｍａｎフィルタリングは適用されなくなる。典型的には、この急激な変化は、加重平均カラーヒストグラム法により計算される分散値のスパイク（ｓｐｉｋｅ）により検出される。本発明によると、急激な変化は、ショットまたはシーンの変化が存在することにより生じる。
【００６１】
［５．ショットベースカラーヒストグラム］
本発明の他の実施例によると、ショットベースカラーヒストグラム手法が適用される。この手法を利用することにより、ショットに基づく映像境界が検出される。
【００６２】
Ｎ個のフレームを含む映像シーケンスのＭ個のショットの集合｛Ｓｈ１，．．．，ＳｈＭ｝が与えられる。各ショットに対し、例えば、９−ｂｉｎカラーヒストグラムＣＨ［ｉ］［ｊ］が存在する。ここで、インデックスｉはｂｉｎ位置を示し、インデックスｊは映像シーケンスのフレーム位置を示す。任意数のｂｉｎが、用途に応じて利用可能である。ショットＳｈｉの代表カラーヒストグラムＣＨ［Ｓｈｉ］は、与えられたショット内の「平均」カラーヒストグラムとして決定される。好ましくは、この手法は、上述されたようなＫａｌｍａｎフィルタリングを利用することにより定式化される。例えば、カラーヒストグラムの集合｛ＣＨ［Ｓｈ１］，．．．，ＣＨ［ＳｈＭ］｝が与えられると、映像一様カラーセグメント境界が検出可能となる。
【００６３】
［６．モザイクカラーヒストグラム］
本発明の他の実施例によると、モザイクカラーヒストグラム手法は、３次元一様カラーセグメントの静止部分、すなわち、画像背景部分のモザイクが計算されていることを仮定する。モザイクカラーヒストグラム法の計算は、従来技術において周知である。例えば、参照することによりここに含まれる、Ｌ．ＴｈｅｏｄｏｓｉｏとＷ．Ｂｅｎｄｅｒによる「Ｓａｌｉｅｎｔ  Ｖｉｄｅｏ  Ｓｔｉｌｌｓ：Ｃｏｎｔｅｎｔ  ａｎｄ  Ｃｏｎｔｅｘｔ  Ｐｒｅｓｅｒｖｅｄ」（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ  Ｃｏｎｆｅｒｅｎｃｅ，ＡＣＭ  Ｐｒｅｓｓ（１９９３））は、このような方法の１つを開示している。モザイク画像またはパノラマビューは、カメラ挙動検出法とともに画像構成法を利用して導出することが可能である。モザイク表現は、映像ショットに対する良好な視覚的空間−時間合成表現である。典型的には、モザイク抽出は、動き推定と動き添加の２つのステップから構成される。生成プロセスの与えられた時点において、入力フレームは、以前のフレームから構成された現在フレームとマージされる。入力フレームをマージするため、グローバル動き推定アルゴリズムを用いて、動きパラメータが求められる。動き推定方法は、当業者に周知である。たとえば、従来技術による方法の１つとして、オプティカルフロー計算があげられる。しかしながら、この方法は、計算量が大きく、照明状態の変動に対しロウバストさが欠落している。あるいは、ハウスドルフ距離方法を利用して、動き推定を実行することが可能である。動き推定後、現在のモザイクは、背景に属さない画像部分を拒絶するため、現在モザイクと歪められた入力フレームを混成する前に、加重関数を用いることにより計算される。
【００６４】
本発明の一実施例によると、パノラマモザイクを構成するための典型的な方法は、各画像からストリップと呼ばれる部分を収集し、これらのストリップをモザイクを形成するため互いに隣り合うようにペーストすることからなる。パンしたカメラ（水平移動する）の簡単なケースでは、各画像から垂直のストリップが取得され、並行してペーストされる。このプロセスは、ある垂直の幅によるシーンのスキャンとしてみなすことができる。この垂直幅は、水平のオプティカルフローと直交している。ストリップがパノラマ画像において構成された後、オプティカルフローはパノラマ画像が生成される方向に向けられる。カメラの動きに応じて、異なるスキャン方法が選択可能である。例えば、パンに対しては垂直スキャニング幅が選択可能であり、ティルトに対しては水平スキャニング幅が選択可能であり、ズーム及び前進移動に対しては循環スキャニング幅が選択可能である。
【００６５】
本発明の他の実施例によると、各モザイク画像に対し、ショットの開始から現在フレームまでの映像セグメントを表すカラーヒストグラムが計算される。フレーム０とフレームｊとの間の一様カラーセグメントモザイクのカラーヒストグラムＣＨｉＭｏｓａｉｃは、１つの画像のカラーヒストグラムである。ｊ番目のフレームのモザイクに対するカラーヒストグラムＣＨＭ［ｉ］［ｊ］は、以下の差分測度
【数５９】
2006510072.tif 000054
を計算することにより、「ファミリーモザイク」カラーヒストグラムＣＨＭＦ［ｉ］［ｊ］のものと比較される。
【００６６】
好ましくは、新しい各モザイク画像に対するセグメントのモザイクを構成するとき、新たな各入力モザイクに対し、正規化されたカラーヒストグラムが計算される。モザイク画像はもとの画像より大きくなる傾向があるため、正規化されたカラーヒストグラムが好ましい。同様に、新しいカラーヒストグラムが計算され、新しいカラーｂｉｎが新たなカラーを取得すると（すなわち、新たなカラーが入ってくると）、モザイクのヒストグラムはより多くの情報を含むようになる。このため、新たなカラーｂｉｎには、従前より存在していたｂｉｎより高い重要度が与えられる。すなわち、より高い加重ｗｉがこのカラーｂｉｎに割当てられる。上述のように、Ｌ１測度が加重の割当てに利用可能である。あるいは、Ｌ２、ヒストグラムインタセクション、カイ二乗やｂｉｎ単位ヒストグラムインタセクションなどの上述の他の測度が利用可能である。
【００６７】
本発明の一実施例によると、モザイクカラーヒストグラム法は、ファミリーカラーヒストグラムに関する上記セクション１において説明されたように進行する。
【００６８】
［７．計算可能マクロセグメント境界］
計算可能なシーンは、典型的には、互いに関連する一様時間セグメントのシーケンスとして定義される。例えば、会話シーンは、会話中の２人の参加者を示す時間セグメントのシーケンスである。
【００６９】
本発明の一実施例によると、マクロセグメント境界検出法は、ファミリー（累積）ヒストグラムのリスト｛Ｐ１，．．．，Ｐｚ｝から、各ファミリーヒストグラムＰｉと以降のファミリーヒストグラムＰｉ＋ｊ（１＜ｊ，ｚ≧ｊ）を比較するステップを有する。好ましくは、ルックアヘッドウィンドウ（ｌｏｏｋ  ａｈｅａｄ  ｗｉｎｄｏｗ）は、プログラム（例えば、テレビショーや消費者ホームビデオなど）の終わりまでのすべてのヒストグラムにわたっている必要はない。
【００７０】
好ましくは、大部分のホームコメディが３０分の長さであるため、このスパンは以降の３０分を超えるべきでないということが仮定される。同様に、映画やより長いプログラムでは、視覚コンテンツは通常は連続的に構成される。すなわち、シーンは以前のシーンの上に構成されるか、あるいはシーンが繰り返される。
【００７１】
このため、本発明の一実施例によると、マクロセグメント境界検出法は、以下のステップを有する。
ａ）セクション１、２または６で説明されたように一様セグメント化を実行するステップ
ｂ）テレビ番組全体の各一様セグメントに対する累積ヒストグラムを生成するステップ
ｃ）セグメントの各ヒストグラムに対し、番組（またはルックアヘッドウィンドウ）の終わりまでの残りのヒストグラムとの類似性をプロットする類似度曲線ｙｊ（ｘ）を生成するステップ  ここで、ｘ軸はフレーム番号（または時間）であり、ｙ軸は現在セグメントの現在累積ヒストグラムと以降すべての累積ヒストグラムとの間の類似度測度である。これにより、類似度曲線は以下のように定式化される。
【００７２】
【数６０】
2006510072.tif 000055
ｄ）時間セグメントと以降の時間セグメントとの間の類似度を表すすべての類似度曲線の加法類似度曲線を生成するステップ  この加法類似度曲線は以下のように定式化される。
【００７３】
【数６１】
2006510072.tif 000056
ｅ）最後に、ヒストグラム系列Ｐｋ，．．．，ＰｊとＰｊ＋ｍ，．．．，Ｐｔとの間に類似性が確立できない場合、プログラム境界が存在することとなる。すなわち、接続された（類似した）ノード間に明らかな不連続性が存在する。加法類似度曲線では、このことは、境界が存在するたびに、曲線がｘ軸と交わることを意味する。さらに、ゼロセグメントに対しては、ゼロセグメント全体をマクロセグメントとするか、あるいは２）新しい各ミクロセグメントにおける境界を生成するという２つの選択がある。
【００７４】
典型的には、ショーでは、図５に示されるように、コマーシャルからのヒストグラムにより散在するファミリーヒストグラムの繰り返しがある。例えば、散在するヒストグラムから累積ヒストグラムＰ１４とＰ３５が導出される。最初の５つのヒストグラムの間と、７番目と８番目のヒストグラムの間には類似性が存在し、このことは、Ｐ６とＰ７の間に境界が存在することを意味する。
【００７５】
図６は、会話マクロセグメントの後のマクロ境界の一例と対応する類似度関数を示す。類似度関数ｙ１（ｘ），．．．，ｙ６（ｘ）は、会話マクロセグメントを構成する最初の６つの一様時間セグメントに対し示されている。加法類似度関数は、これら最初の６つのセグメントＰ１〜Ｐ６の集合の内部の類似性を示す。
【００７６】
本発明の趣旨及び範囲を逸脱することなく、本発明の方法及びシステムにおいて様々な変更及び変形が可能であるということが当業者には明らかであろう。従って、本発明は、添付された請求項とそれらの均等物の範囲に属する変更及び変形を含むものとされる。
【図面の簡単な説明】
【００７７】
【図１】図１は、本発明の実施例が実現可能な汎用コンピュータの概略ブロック図である。
【図２】図２は、本発明の一実施例による一般的方法を示すフロー図である。
【図３】図３は、本発明の一実施例を示す。
【図４】図４は、本発明の他の実施例によるファミリーカラーヒストグラム法を示すフロー図である。
【図５】図５は、本発明の一実施例による累積ヒストグラムに基づく会話マクロセグメントのためのマクロ境界決定方法の一例を示す。
【図６】図６は、本発明の一実施例による累積ヒストグラムに基づくマクロ境界決定方法の一例を示す。
【図１】
2006510072.tif 000066
【図２】
2006510072.tif 000067
【図３】
2006510072.tif 000068
【図４】
2006510072.tif 000069
【図５】
2006510072.tif 000070
【図６】
2006510072.tif 000071
【国際調査報告】
2006510072.tif 000072
2006510072.tif 000073
2006510072.tif 000074
2006510072.tif 000075
2006510072.tif 000076