(57)【要約】【課題】  ビデオ内容を各自が望む詳細なレベルで要約しナビゲートする柔軟性をユーザに提供する。【解決手段】  ビデオドキュメント（２０）を自動的に要約する方法およびシステム。ビデオドキュメント（２０）はシーン（２２）、ショット（２４）、およびフレーム（２６）に分解され、重要値が各シーン、ショット、およびフレームに割り当てられる。キーフレームが各ショット（２４）の重要値に基づいてショット（２４）に割り振られる。次いで、割り振られた数のキーフレームが各ショット（２４）から選択される。キーフレームの数は、ユーザ入力に応答して詳細度を高める、または低めるように変更することができる。
2005525034.tif 000002
【特許請求の範囲】
【請求項１】
ビデオドキュメントを自動的に要約する方法であって、
前記ビデオドキュメント（２０）を、シーン（２２）、ショット（２４）およびフレーム（２６）に分解するステップと、
各シーン（２２）、ショット（２４）およびフレーム（２６）に、重要値を計算するステップと、
前記シーン（２２）の前記重要値に基づいて、前記シーン（２２）に所定数のキーフレーム（Ｎ）を割り当てるステップと、
前記ショット（２４）の前記重要値に基づいて、各シーン（２２）に割り当てられた前記キーフレームを、各シーンの前記構成要素ショット（２４）に振り分けるステップと、
前記割り振られた数のキーフレームを、各ショット（２４）から選択するステップと、
ユーザ入力に応答して、キーフレーム数を変更するステップと
を含む方法。
【請求項２】
シーンの重要値を計算することは、
前記シーン（２２）の長さを測定するステップと、
前記シーン（２２）のアクティビティレベルを定量化するステップと、
前記シーン（２２）中のショット（２４）の数をカウントするステップと
を含む請求項１に記載の方法。
【請求項３】
前記シーン（２２）の前記アクティビティレベルを定量化することは、
前記シーン内の連続した各フレーム対のカラーヒストグラム差分を計算するステップと、
それぞれの平均を用いて前記シーンのアクティビティレベルを示すステップと
を含む
請求項２に記載の方法。
【請求項４】
ショットの重要値を計算することは、
前記ショット（２４）の長さを測定するステップと、
前記ショット（２４）内のアクティビティレベルを定量化するステップと、
前記ショット（２４）内のカメラの動きを定量化するステップと
を含む
請求項１に記載の方法。
【請求項５】
前記ショット（２４）内のアクティビティレベルを定量化することは、
前記ショット（２４）内のあらゆる基準フレーム対間の動き量を計算するステップと、
それぞれの平均を用いて前記ショットのアクティビティレベルを示すステップと
を含む
請求項４に記載の方法。
【請求項６】
前記ショット（２４）内のカメラの動きを定量化することは、
各フレーム（２６）の方向動きベクトルｍｖを離散数の方向に分類するステップと、
動きベクトルヒストグラム（３２）を計算するステップと、
方向動き比率および前記方向動きベクトルｍｖの大きさ平均を計算するステップと
を含む請求項１に記載の方法。
【請求項７】
フレームの重要値を計算することは、
前記フレーム（２６）中の肌色ピクセルの割合を求めるステップと、
前記フレーム（２６）において検出された人間の顔の数をカウントするステップと、
前記フレーム（２６）のエッジエネルギー分布を計算するステップと、
前記フレーム（２６）に含まれる動きアクティビティ量を定量化するステップと
を含む請求項１に記載の方法。
【請求項８】
各ショット（２４）から割り振られた数のキーフレームを選択することは、
時間制約付きキーフレーム選択または重要度適応キーフレーム選択を使用して、前記キーフレームを選択するステップ
を含む
請求項１に記載の方法。
【請求項９】
ユーザ入力に応答してキーフレーム数を変更することは、
前記所定数の選択されたキーフレーム（Ｎ）から１つまたは複数のキーフレームを除去するステップ、または、
前記所定数の選択されたキーフレーム（Ｎ）に１つまたは複数のキーフレームを追加するステップ
を含む
請求項１に記載の方法。
【請求項１０】
ビデオドキュメントを要約する方法を実行するようにコンピュータシステムを制御する命令を含むコンピュータ可読媒体であって、前記方法は、
前記ビデオドキュメントをシーン、ショット、およびフレームに分解するステップと、
各シーン、ショット、およびフレームに重要値を割り当てるステップと、
各シーンの前記重要値に基づいて、前記シーンに或る数の（a number of）キーフレームを割り振るステップと、
各ショットの前記重要値に基づいて、前記ショットに或る数のキーフレームを割り振るステップと、
各ショットから前記割り振られた数のキーフレームを選択するステップと、
ユーザ入力に応答してキーフレーム数を変更するステップと
を含む
コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、包括的にはビデオ材料の要約および閲覧に関し、より詳細には要約プロセスおよび閲覧プロセスの自動化およびカスタマイズに関する。
【背景技術】
【０００２】
［発明の背景］
デジタルビデオは、コンピュータ業界および電気通信業界で急成長している要素である。
多くの企業、大学、さらには家庭がすでに、アナログフォーマットのビデオおよびデジタルフォーマットのビデオの両方を大量に収納している。
例としては、放送ニュースに使用されるビデオ、訓練・教育ビデオ、セキュリティ監視ビデオ、およびホームビデオが挙げられる。
デジタルビデオの急速な発達により、多くの人々がマルチメディアを取り込みマルチメディアと対話する方法が変化しつつあり、その過程の中で多くの新しいニーズおよび用途がもたらされた。
【０００３】
したがって、ビデオのアーカイブ、カタログ化、およびインデックス付けのコストを削減すると共に、格納されているビデオの効率、操作性、およびアクセス可能性を向上させる新技術の研究開発が大いに必要である。
１つの重要な話題は、ユーザが大量のビデオデータコレクションを素早く閲覧できるようにする方法、およびビデオデータの素早い閲覧を可能にしながら、ビデオ内容への効率的なアクセスおよび表現を実現する方法である。
こういった問題に対処するために、ビデオ要約技法が出現し、近年、研究の関心をより多く集めている。
【０００４】
ビデオ要約は、名称が示すようにより長いビデオドキュメントの内容を短くまとめたものであり、オリジナルの本質的なメッセージを良い状態で保持しながら、ビデオドキュメントの内容についての簡潔な情報をユーザに提供する。
理論上、ビデオ要約は手動で、または自動的に生成することができる。
しかし、大量のビデオデータがすでに存在し、作成される新しいビデオデータの量が今後も増え続けることから、ビデオ要約を手動で生成することはますます困難になっている。
したがって、ビデオ要約プロセスにおいて人間の介入を減らすように、完全に自動化されたビデオ解析・処理ツールを開発することがますます重要になりつつある。
【０００５】
２つの基本的に異なる種類のビデオ要約、すなわち静止画像要約および動画像要約がある。
静止画像要約は、ビデオサマリとも呼ばれ、基礎となるビデオソースから抽出または生成された目立った画像（キーフレームとして知られる）の小さな集まりである。
動画像要約は、ビデオスキミングとも呼ばれ、画像シーケンスの集まり、ならびにオリジナルシーケンスから抽出された対応するオーディオ要約からなり、したがってそれ自体、長さのかなり短いビデオクリップである。
一般にビデオサマリは、視覚的情報のみが利用され、オーディオ情報またはテキスト情報を処理する必要がないため、スキミングよりもはるかに素早く構築することができる。
したがってビデオサマリは、タイミングすなわち同期の問題がないことからより容易に表示することができる。
さらに、抽出されたすべての代表フレームの時間順を空間順で表示することができ、したがって、ユーザはビデオの内容をより素早く把握することができる。
最後に、必要なときに、ビデオサマリ中の抽出静止画像をすべて非常に容易にプリントアウトすることができる。
【０００６】
ビデオ要約化に対する一般的な手法として、多くの場合、ビデオシーケンス全体がまず一連のショットに分割され、次いで１つまたは複数のキーフレームが、色および動きを含む様々な特徴に基づいた基礎となるビデオ内容の複雑性に応じて、均一サンプリング（uniform sampling）または適応型方式のいずれか一方によって各ショットから抽出される。
こういったシステムの代表的な出力は、抽出されたキーフレームすべてがそれぞれの時間順に表示される静止ストーリーボードである。
こういった手法には２つの主な欠点がある。
第１に、こういった作業はデータ量の削減を図るが、多くの場合、ビデオ内容を要約するのではなく「そのまま」提示するだけである。
ショットが異なるとユーザに対する重要性が異なる場合があるため、重要なショットには重要性の低いショットよりも多くのキーフレームを割り当てることが好ましい。
第２に、静止ストーリーボードは、実際の要約システムにおいて有用な特徴であるスケーラブルなビデオサマリを得る機能をユーザに提供することができない。
たとえば、ユーザはより多くのキーフレームが必要な、特定のシーンまたはショットを詳細に見たいときもあり、また単により少ないキーフレームを必要とする非常に粗い要約化を必要とするときもある。
【特許文献１】米国特許第５９９５０９５号
【特許文献２】欧州特許出願公開第１０４５３１６号
【非特許文献１】Lajendijk R L et al., 「Visual Search in a SMASH System」, 1996年9月16日, 1996年9月16-19日 Interanaional Conference on Image Processing(ICIP)会報, Lausanne New York US, IEEE, vol. 1, p671-674
【非特許文献２】Dufaux F, 「Key Frame Selection to Represent a Video」, 2000年9月10日, IEEE INT CONF IMAGE PROCESS; IEEE International Conference on Image Processing(ICIP 2000)会報, Vancouver Canada, vol. 2, p275-278
【非特許文献３】Yueting Zhuang et al., 「Adaptive Key Frame Extraction Using Unsupervised Clusting」, Image Processing, ICIP 98 International Conference 会報, 1998年10月4-7日 Chicago IL USA, 1998年10月4日 Los Alamitos CA USA, IEEE Comput. SOC, p866-870
【非特許文献４】Corridoni J M et al.,「Structured Representation and Automatic Indexing of Movie Information Content」, Pattern Recongnition, Pergamon Press INC., 1998年12月1日, Elmsford NY US, vol. 31, no. 12, p2027-2045
【非特許文献５】J. Kim, H. S. Chang, J. KimおよびH. M. Kim,「Efficient camera motion characterization for MPEG video indexing」ICME2000, 2000年, New York
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ビデオ内容を各自が望む詳細なレベルで要約しナビゲートする柔軟性をユーザに提供する、ビデオドキュメントのスケーラブルなビデオサマリを自動的かつ知的に生成するシステムおよび方法が必要である。
【課題を解決するための手段】
【０００８】
［発明の概要］
本明細書に記載の本発明は、ビデオドキュメントを自動的に要約するシステムおよび方法を提供する。
ビデオドキュメントはシーン、ショット、およびフレームに分解され、各シーン、ショット、およびフレームに重要値が割り当てられる。
各ショットの重要値に基づいて、或る数のキーフレームがショットに割り振られる。
次いで、割り振られた数のキーフレームが各ショットから選択される。
キーフレーム数は、ユーザ入力に応答して詳細度を高める、または低めるように変更することができる。
【発明を実施するための最良の形態】
【０００９】
［好ましい実施形態の説明］
以下の好ましい実施形態の詳細な説明では、本明細書の一部を成し、本発明を実施し得る特定の実施形態を例として示す添付図面を参照する。
他の実施形態も利用することができ、構造的または論理的な変更を本発明の範囲から逸脱することなく行い得ることを理解されたい。
したがって、以下の詳細な説明は限定の意味で解釈されるべきではなく、本発明の範囲は添付の特許請求の範囲によって規定される。
【００１０】
本発明によれば、ビデオシーケンス２０がまず、図１ａに示すように、検出されたシーン２２およびショット２４の構造に基づいて階層ツリーとして表現される。
本明細書で使用される場合、ショット２４は連続した撮影期間中に取り込まれたビデオセグメントとして定義され、シーン２２は意味的に関連するショット２４のセットからなる。
ショット２４は一連の個々のフレーム２６からなる。
ショットおよびシーンを検出する様々なアルゴリズムが存在し、そのうちのいずれもビデオシーケンス２０をシーン２２、ショット２４、およびフレーム２６の構造に分解するにあたって使用するのに適している場合がある。
解析されるビデオシーケンス２０のタイプに応じて、或るアルゴリズムが別のアルゴリズムよりも好ましい場合がある。
たとえば、ホームビデオとの併用に特に適した手法が２００１年１２月１４日に出願され、本発明と同じ譲受人に譲渡され、参照により本明細書に援用される米国特許出願第１０／０２０，２５５号に提示されている。
【００１１】
本発明によりビデオサマリ８０を作成する１つのプロセスを図１ｂに示す。
ビデオシーケンス２０をシーン２２、ショット２４、およびフレーム２６に分解した後、以下さらに詳細に説明する測定値に基づいて各構成要素シーン２２、ショット２４、およびフレーム２６に重要値が割り当てられる。
本発明により重要値を生成する１つのプロセスを図１ｃに示す。
次に、所望の数のキーフレームＮが与えられた場合、キーフレームはシーン２２の重要値に基づいて基礎となるシーン２２に振り分けられ、重要なシーン２２ほど、多くのキーフレームが割り当てられる。
次いで、各シーン２２内で、割り当てられた数のキーフレームが、ショット２４の重要値に基づいてシーンの構成要素ショット２４にさらに振り分けられる。
最後に、指定された数のキーフレームが、フレーム２６の重要値に従って各ショット２４の基礎となるビデオフレーム２６から選択される。
このプロセスを用いて、重要なシーン、ショットおよびフレームにより多くのキーフレームを割り当てるスケーラブルなビデオ要約８０が実現する。
さらに、柔軟なビデオ内容の閲覧に対するユーザのニーズを満たすために、キーフレームの指定数を、ユーザがビデオ内容をナビゲートする際に増減することができる。
【００１２】
本明細書に記載の本発明のパフォーマンスは、シーン２２、ショット２４、およびフレーム２６のそれぞれに対する重要度測定値の３つのカテゴリの定義および計算に大きく依存することが容易に明らかになる。
重要値の計算について以下さらに詳細に説明する。
【００１３】
［シーン重要度計算］
本発明の一実施形態によりシーン２２の重要度を求める際に３つの要因が考慮される。
すなわち、
１）シーン中のフレーム数から見たシーンの長さ、
２）シーンのアクティビティレベル、および、
３）シーンに含まれる構成要素ショットの数。
上記考慮事項の基礎となる根拠は、シーンが長い、アクティビティが高い、またショットが多いことはすべて重要なシーンであることを示すということである。
たとえば、興味のある被写体にビデオ撮影者の注意が引き付けられる場合、通常、被写体に興味がない場合よりもビデオの取り込みにより長い時間をかける。
また、シーン２２の基礎となるビデオ内容がかなりダイナミックである（通常、カメラの動きが多いこと、オブジェクトのアクティビティが多いこと、および含まれるショットの数が多いことを特徴とする）場合、シーン２２は複雑な内容を有し、したがってより多くのキーフレームを受けるに値する。
【００１４】
シーンの長さおよびシーン２２に含まれる構成要素ショット２４の数を求めることは、シーン２２中のフレーム２６およびショット２４の数をカウントする以外に必要なことは殆どない単純なプロセスである。
そのために、フレーム２６およびショット２４をカウントする適した方法をいずれも採用することができる。
より困難な態様は、シーン２２のアクティビティレベルの定量化である。
【００１５】
シーン２２のアクティビティレベルを定量化するために、シーン内の連続した各フレーム対のフレーム間カラーヒストグラム差分が計算され、それぞれの平均がシーンのアクティビティレベル指標として使用される。
ヒストグラム差分はあまり正確な動き指標ではないが、計算が速く、結果はシーンレベルに十分である。
個々のショット２４の重要値の計算に関して以下説明するように、より正確であるが、より時間のかかる動きベクトル計算を使用してもよい。
解析中のビデオシーケンス２０が総計でＳＮ個のシーンを含み、シーンｉの重要度をＩＭｉで表すと想定すると、シーンの重要度は、
【００１６】
【数１】
2005525034.tif 000003
【００１７】
として計算される。
ここで、α１、β１、およびγ１は足して１になる重み係数であり、ｌｉはシーンｉの長さであり、ＨＤｉは平均ヒストグラム差分であり、ＳＨｉは包含するショットの数である。
所望のキーフレームの総数がＮである場合、シーンｉに割り振られるキーフレーム数Ｎｉは、Ｎｉ＝ＩＭｉ×Ｎである。
【００１８】
α１、β１、およびγ１の値は経験的に求められる。
本発明の一実施形態によれば、α１の値の範囲は０．１０〜０．２０であることができ、β１の値の範囲は０．３０〜０．５０であることができ、γ１の値の範囲は０．４０〜０．６０であることができる。
【００１９】
［ショット重要度計算］
本発明の一実施形態によりショット２４の重要度を求める際に、３つの要因が考慮される。
すなわち、
１）ショット中のフレーム数から見たショットの長さ、
２）ショットのアクティビティレベル、および、
３）検出されたカメラの動き（主にカメラパニングが考慮される）。
ショットの長さおよびアクティビティレベルを考慮する根拠は、シーン２２の重要度を求めることに関して上に説明した根拠と同様である。
カメラの動きの検出を含める理由は、特定のカメラの動きが存在する場合にショットの内容がより複雑になる傾向があり、したがってショット２４がより多くのキーフレームを受けるに値するためである。
【００２０】
シーン２２の重要度を求める場合と同様に、ショットの長さは、任意の適したカウント方法を用いてショット２４中のフレーム２６の数をカウントすることによって求めることができる。
【００２１】
ショット２４のアクティビティレベルを計算するには、ショット内のあらゆる基準フレーム対間の動き量が計算され、それぞれの平均がショット２４のアクティビティレベルを示すために使用される。
多くのビデオシーケンス２０（特にホームビデオ）はデジタル化され、Ｈ．２６ＸフォーマットまたはＭＰＥＧ−Ｘフォーマットに圧縮されるため、動きベクトル情報は、予測符号化フレーム２６を含むオリジナルビットストリームから直接得ることができる。
特に、予測符号化フレーム、たとえばＰフレームの場合は、あらゆるマクロブロックの動きベクトルｍｖの大きさがまず計算され、次いでＰフレーム中のすべての動きベクトルｍｖの大きさの平均を使用してアクティビティレベルを示す。
ビデオデータが予測符号化フレーム２６を含まない場合は、ビデオシーケンス２０を、予測符号化フレーム２６を含むフォーマットに変換することができるか、あるいは当該技術分野において既知の他の方法を用いて動きベクトルｍｖ情報を求めて定量化することができる。
【００２２】
カメラの動きの検出は従来技術において利用されており、大半の既存の方法は連続した画像間で計算されるオプティカルフローを解析することに基づいている。
基本的に、カメラの動きの解析作業はすべて２つのクラスに分類することができる。
すなわち、
１）カメラの動きを表すアフィンモデルを定め、計算されたオプティカルフローからモデルパラメータを推測するアルゴリズム、および、
２）角度分布またはオプティカルフローベクトルの大きさを使用することにより、動きモデルなしで、観察されたオプティカルフローパターンを直接解析するアルゴリズム（たとえば、J. Kim, H. S. Chang, J. KimおよびH. M. Kim著「Efficient camera motion characterization for MPEG video indexing」ICME2000, New York, 2000を参照のこと）。
いずれのクラスのアルゴリズムを使用してもよいが、最初のクラスのアルゴリズムはカメラの振動および突然の動きに敏感であるため、ホームビデオ等の用途によっては２番目のクラスのアルゴリズムが好ましい。
図２は、カメラのパニング、傾斜、およびズーミングを含む典型的な３つのタイプのカメラの動きの理想的なオプティカルフローパターンを示す。
【００２３】
オプティカルフローの推定は通常、未処理のビデオデータを使用する勾配方法またはブロックマッチング方法に基づくため、計算的に非常に高価な場合がある。
本発明の一実施形態によれば、すぐに使用できる動きベクトルｍｖ情報がビデオデータビットストリーム（ＭＰＥＧ−ＸフォーマットまたはＨ．２６Ｘフォーマットにあるように）に埋め込まれることを意図する。
この情報は、オプティカルフローの推定に対する代替として使用することができ、それによって計算負荷が低減する。
カメラの動きは、抽出された動きベクトルｍｖのレイアウトパターンを解析することによって検出することができる。
ショット２４のアクティビティレベルを求めることに関して上に述べたように、ビデオデータが動きベクトルｍｖ情報を含む予測符号化フレーム２６を含まない場合、予測符号化フレームを含むフォーマットにビデオを変換することができるか、あるいは当該技術分野において既知の他の方法を使用して動きベクトル情報を求めて定量化することができる。
【００２４】
図３に示すように、カメラの動きは８つの方向に量子化される。
各方向は、反時計方向に沿った最近傍部分領域を含む。
たとえば、動きベクトルｍｖが０〜４５度の領域にある場合、それは方向１とインデックス付けられる。
以下の考察は、カメラのパニングの方向に焦点をあてる。
これは、カメラのパニングがホームビデオにおいて観察される主なカメラの動きであるためである。
理想的には、カメラパニング中、すべての動きベクトルｍｖはすべて図３に示す方向１または５を指すべきである。
しかし、カメラの振動により、方向１および８、または方向４および５の領域にある動きベクトルｍｖもあるであろう。
【００２５】
典型的なＭＰＥＧビデオシーケンスには、３つのフレームタイプがある。
すなわち、Ｉフレーム、Ｐフレーム、およびＢフレームである。
Ｉフレームはすべて、動き予測および補償なしでフレーム内符号化される一方で、Ｐフレームは前のＩフレームまたはＰフレームから予測符号化される。
Ｐフレーム内の各マクロブロックはフレーム内符号化、順方向予測、または単にスキップすることができる。
圧縮率をさらに向上させるために、前のまたは後のＩフレームおよびＰフレームから双方向予測符号化することのできるＢフレームが定義される。
図４は、ＩＢＢＰＢＢＰＢＢ・・・のパターンを有する１５枚のフレームを含む典型的なＭＰＥＧ  ＧＯＰ（ピクチャグループ）構造３０を示す。
Ｂフレームは、カメラの動きの検出を混乱させる傾向がある順方向予測および逆方向予測の両方の動きベクトルｍｖを含むことができるため、すべてのＢフレームは破棄され、Ｐフレームのみが使用される。
これは、典型的な１秒あたり２９．９７フレームのレートの場合、１秒内に８枚のＰフレームがあることができ、典型的なカメラの動きは通常、１秒よりも長く続くため好ましい。
【００２６】
本明細書において説明するカメラの動きを検出する方法には３つの主なステップが含まれる。
ステップ１において、各Ｐフレームの動きベクトルｍｖが上に述べた８つの方向に分類され、方向ヒストグラム３２が計算される。
フレーム２６は、カメラの動きシーケンス、たとえば右へのカメラパニングに属する場合、過半数の動きベクトルｍｖを方向１および８に有するはずであり、その他の場合、動きベクトルｍｖは表される主な方向なしで分散し得る。
さらに、連続した一連のＰフレームは、カメラの動きが検出されたことが明らかになる前に同様の動きパターンを提示する必要がある。
これを図５aおよび図５ｂに示す。
図５ａは、右パニングシーケンス内の８枚のＰフレームのヒストグラム３２を示し、図５ｂは、カメラズーミングシーケンス内の８枚のＰフレームのヒストグラム３２'を示す。
図５ａ中の略すべてのＰフレームが右を向いた主な方向で同様のパターンを提示していることは極めて明らかである。
図５ｂにおいて、動きベクトルｍｖは、ズーミングシーケンスを特徴付ける各方向に沿って略等しく分布している。
【００２７】
カメラの動きを検出する方法のステップ２において、Ｐフレームの方向動き比率ｒおよび方向動きベクトルの大きさの平均（ＡｖｇＭａｇ）が計算される。
右へのカメラパニングの場合、ｒはフレーム２６に含まれる動きベクトルｍｖの総数に対する、方向１および８に沿った動きベクトルｍｖの量の比率である。
ｒが特定のしきい値、たとえば０．６よりも大きい場合、フレーム２６は候補としてインデックス付けられる。
ｒの値は経験的に選択され、本発明の一実施形態では、０．５〜０．７の範囲の値を有することができる。
ＡｖｇＭａｇは単に、方向１および８にあるすべての動きベクトルｍｖの大きさの平均である。
【００２８】
カメラの動きを検出する方法のステップ３では、上記計算が所与のショット内のあらゆるＰフレームに対して繰り返される。
十分な長さを有する候補のシーケンス４０が観察され、その平均ＡｖｇＭａｇが予め設定されたしきい値よりも大きい場合、カメラパニングシーケンスが検出されることが明らかになり、その他の場合、カメラの動きは存在しない。
図６ａおよび図６ｂはそれぞれ統計ｒおよびＡｖｇＭａｇのグラフを示し、図６ａはカメラパニングシーケンスを含むショットであり、図６ｂはカメラの動きのないショットである。
図６ａおよび図６ｂを入念に観察することにより、ＡｖｇＭａｇを考慮せずにｒのみを考慮すると、カメラの動きの誤った検出に繋がる可能性があることが分かる。
たとえば、ｒのみを考慮すると、カメラの小さな揺れの動きに起因する長い候補シーケンスもあるため、図６ｂのショットシーケンスでの誤った動き検出判断に繋がる可能性がある。
最後に、より正確な検出結果が望まれる場合は、方向動きベクトルの大きさの標準偏差ＳｔｄＭａｇも考慮することができる。
たとえば、連続したカメラのパニングシーケンスがある場合は、ＳｔｄＭａｇ値は動きの一貫性により極めて小さいはずである。
【００２９】
ここで、シーンｉ内に総計でＳＨ枚のショットがあると想定する。
次いで、ショットｉの重要度ＩＭＳｉを
【００３０】
【数２】
2005525034.tif 000004
【００３１】
として計算することができる。
ここで、α２、β２、およびγ２は足して１になる重み係数であり、ｌｓｉはショットｉの長さであり、Ａｃｔｉは動きベクトルの大きさの平均であり、Ｃａｍｉは二値カメラ動き検出結果である。
ここで、シーンｉに割り当てられるキーフレームがＮｉである場合、ショットｉに割り当てられるキーフレーム数ＮＳｉは、ＮＳｉ＝ＩＭＳｉ×Ｎｉである。
ＮＳｉが１未満の場合、各ショットから少なくとも１つのキーフレームを抽出することが望まれるのであれば、ＮＳｉの値を１に設定することができる。
別法として、各ショットから少なくとも１つのキーフレームを抽出することが好ましくないのであれば、ＮＳｉの値を０に設定することができる。
【００３２】
α２、β２、およびγ２の値は経験的に求められる。
本発明の一実施形態によれば、α２の値の範囲は０．３〜０．５であることができ、β２の値の範囲は０．４〜０．６であることができ、γ２の値の範囲は０．０〜０．２であることができる。
【００３３】
［フレーム重要度計算］
本発明の一実施形態によりフレーム２６の重要度を求める際に４つの要因が考慮される。
すなわち、
１）フレーム中の肌色のピクセルの割合、
２）フレームにおいて検出された人間の顔の数、
３）フレームのエッジエネルギーの分布、および、
４）フレームに含まれる動きアクティビティ量。
最初の２つの要因を含める理由は、一般的に言えば、人間の顔を含むフレーム２６は、たとえば風景フレームよりも多くの情報を提供するためである。
顔検出アルゴリズムが顔を見落とした場合、見落とされた顔検出を肌色検出により補償することができる。
最後の２つの要因は、抽出されたキーフレームが、素早いカメラの動き、素早い被写体の移動、またはカメラ焦点合わせの不良等に起因するぶれた画像ではなく、十分に焦点が合った鮮明な画像であることを確実にするために使用される。
たとえば、カメラパニング後に撮影された静止画像は、ぶれる、または不安定である場合があるパニング中に撮影された画像よりも好ましい。
したがって、フレーム重要度の場合、より少ないアクティビティを含むフレーム２６が好ましい。
【００３４】
肌色検出は、顔検出分野および顔認識分野の両方で広く利用されている。
主に２つのモデルが評価され使用されている。
ＹＣｂＣｒモデルは生来、ＭＰＥＧ符号化およびＪＰＥＧ符号化に関連し、ＨＳＶ（色相、彩度、明度）モデルは主にコンピュータグラフィックスに使用される。
肌色部分空間を概算するために、両方のモデルにおいて肌色パッチを使用して肌の色合いの領域を画定する。
また、強度値Ｙは肌色の分布に対して殆ど影響がないことが観察されているため、作業によっては、Ｙを考慮することなく、クロミナンス平面（ＣｂＣｒ）において肌色分類が直接実行される（たとえば、H. WangおよびS. -F. Chang著「A highly efficient system for automatic face region detection in MPEG video」IEEE Transaction on Circuit System and Video Technology, vol. 7, no.4, pp. 615-628, 1997を参照のこと）。
図７ａはＣｂＣｒ色空間における色相を示す一方で、図７ｂは、広範囲の肌色の外観（異なる人種、異なる照明条件等）をカバーする様々な静止画像からなるデータから得られる、肌色が占める対応領域を示す。
肌色サンプルは実際に、ＣｂＣｒ色空間において単一で極めてコンパクトなクラスタを形成することが分かる。
この観察から導き出されるように、色を肌色と分類するためにＲＧＢに関して以下の規則が使用される。
すなわち、（Ｙ≧３２）かつ（Ｇ＜０．８＊Ｒ）かつ（Ｂ＜Ｇ）かつ（Ｂ＞０．７＊Ｇ）の場合に肌色である。
【００３５】
Ｙ基準を含める理由は暗すぎる領域を除外するためである。
図８ａ（ビデオフレーム２６を示す）および図８ｂ（図８ａにおけるビデオフレームの肌色減色）は、肌色検出により男性の顔を十分に認識することができる一方で、後ろにいる女性の顔は影になっているため無視される一例を示す。
【００３６】
顔検出・認識アルゴリズムは当該技術分野において既知である。
任意の適したアルゴリズムを、本明細書に記載の本発明の実施態様に使用することができる。
アルゴリズムの感度および特定のアルゴリズムに必要な計算負荷を考慮することができる。
図９ａおよび図９ｂは、顔が検出されない例（図９ａ）および顔が検出される例（図９ｂ）を示す。
【００３７】
大抵のホームビデオの簡単（casual）な写真性質により、ぶれて焦点がぼけた多くのビデオフレーム２６を容易に見つけることができる。
一般的にいえば、好ましいキーフレームは、示差的なエッジを有する、十分に焦点が合った鮮明な画像である。
この選好は適切なキーフレーム候補を特定するのに役立つように適用される。
具体的には、所与のフレームについて、エッジオペレータを使用してフレームのすべてのエッジを見つける。
次いで、エッジエネルギーの標準偏差が計算される。
エッジエネルギーの標準偏差が予め設定された値よりも大きい場合、フレームの焦点が十分に合っていることが明らかになり、キーフレームに適格であり、その他の場合、フレームはキーフレーム候補として破棄される。
図１０ａ〜図１０ｄは、或る画像はぶれており（図１０ａ）、他の或る画像は鮮明な（図１０ｃ）２つの画像に垂直エッジオペレータを適用する例を示す。
図１０ｃの鮮明な画像は非常に示差的なエッジ（図１０ｄ）を有するが、図１０ａのぶれた画像は、仮にあったとしても殆ど識別できないエッジ（図１０ｂ）を有することが容易に分かる。
【００３８】
エッジはいくつかの適した様式で検出することができる。
エッジを検出する１つの適した様式は「Ｐｒｅｗｉｔｔ」エッジオペレータの使用であり、この場合、以下の２つの勾配が用いられる。
【００３９】
【数３】
2005525034.tif 000005
【００４０】
ここで、ＧＲおよびＧＣは、それぞれ行勾配および列勾配である。
図１１は、１つの特定のショット２４内のすべてのフレーム２６のエッジエネルギーの計算された標準偏差６０を示す。
ショット２４内のフレーム２６の大半は、より大きな数を有する一組のフレーム２６以外は小さい値を有することが分かる。
実際、このショット２４は多くのぶれた部分を含み、十分に焦点の合ったフレーム２６はほんのわずかである。
【００４１】
［キーフレーム選択］
ショットｉ内に総計でＦ枚のフレームがあると想定する。
そうすると、フレームｉの重要度ＩＭＦｉは、
【００４２】
【数４】
2005525034.tif 000006
【００４３】
として計算することができる。
ここで、α３、β３、γ３、およびδは足して１になる重み係数であり、ＰＳｉは肌色ピクセルの割合であり、ＮＦｉは検出された顔の数であり、ＥＳｔｄｉは計算されたエッジエネルギーの標準偏差であり、ＦＡｃｔｉはフレームｉに含まれる動きアクティビティである。
顔およびエッジの検出は両方とも非常に時間のかかるものであるため、１つ１つのフレームに対して繰り返す必要はないことに留意されたい。
その代わり、ビデオ内容の連続性により、隣接するフレームの小さなセットが通常、同じ顔およびエッジ検出結果を共有することができる。
【００４４】
α３、β３、γ３、およびδの値は経験的に求められる。
本発明の一実施形態によれば、α３の値の範囲は０．１〜０．３であることができ、β３の値の範囲は０．１〜０．３であることができ、γ３の値の範囲は０．１〜０．３であることができ、δの値の範囲は０．３〜０．５であることができる。
【００４５】
フレーム重要度が求められた後、各ショットに割り当てられるキーフレーム数ＮＳｉを、ショット内のＦ枚すべてのフレームから選択しなければならない。
Ｆ枚すべてのフレームはそれぞれの重要値に基づいて降順にソートされ、理論上、最上部からＮＳｉ枚のフレームが、最も重要なフレームであるためキーフレームとして選択されるべきである。
しかし、１枚のフレームが大きな重要値を有する場合、そのフレームに隣接するフレームの多くもまた、ビデオ内容の視覚的また動きの連続性により大きな重要値を有することになる。
したがって、割り振られたキーフレームのすべてまたは多くがショットの同じ時間領域から採用される場合があり、ビデオ内容の良好な表現を提供しない場合がある。
【００４６】
ショットのビデオ内容のより良好な表現を提供するために、時間制約付きキーフレーム選択あるいは重要度適応キーフレーム選択を用いることができる。
時間制約付きキーフレーム選択では２つの追加規則が実施される。
第１に、キーフレームは互いに視覚的に異なっているべきである。
具体的には、新たに抽出されたキーフレームはそれまでに抽出されたすべてのキーフレームと視覚的に異なっているべきである。
カラーヒストグラム比較がこの目的のために用いることのできる１つの方法である。
第２に、キーフレームは互いに時間的に離れているべきである。
具体的には、抽出されたキーフレームはすべて、ビデオ内容全部をカバーするように、可能な限り均一にショットに分散すべきである。
良好に分散したキーフレームのセットは通常、時間的にまとまったキーフレームのセットよりも基礎となるビデオ内容を良好に表現することになる。
【００４７】
重要度適応キーフレーム選択では、キーフレームは基礎となる重要曲線に適応することによって選択される。
特に、ショット内のすべてのフレームの重要値はまず正規化されて、基礎となる面積が１に等しい曲線が形成される。
図１２は１つの特定のショットの重要曲線７０を示し、下（正規化後）の曲線７０'が上の未処理曲線から３×１平均フィルタを使用することによって得られる。
次に、ショットの全体の時間軸が、各セグメント７２内の重要値の和（すなわち、曲線下の面積）が１／ＮＳｉに等しくなるように、ＮＳｉ個のセグメント７２に分けられる（図には１つのセグメント７２のみを示す）。
次いで、各セグメント７２内で最高の重要度を有するフレーム２６が代表フレーム２６として選択される。
抽出されたすべてのフレームが時間線において良好に分散することを確実にするため、時間制約付きキーフレーム選択に用いられたもののような時間制限規則を用いることができる。
【００４８】
実験結果に基づくと、時間制約付きキーフレーム選択は重要度適応キーフレーム選択よりもわずかに良好な結果を生成するが、カラーヒストグラムの計算および比較により、速度がより遅いという代償を払う。
最後に、時間制約付きキーフレーム選択では、抽出されるキーフレームの数は、基礎となるショットが単調な内容を有する場合にＮＳｉより少ない場合がある。
【００４９】
実験結果により、フレームの重要度を求めるために使用される要因の有効性が確認される。
図９ａおよび図９ｂは２つのフレームを示し、図９ｂは顔検出を含めた後に抽出されたキーフレームであり、図９ａはオリジナルの候補である。
図９ｂの画像は画像において人物をより容易に識別することができるため、図９ｂの画像が明らかに良好な選択である。
図１３ａおよび図１３ｂは、エッジエネルギー制限要因が実施される場合に、図１３ａに示す最初に選択されたキーフレームが図１３ｂに示すフレームで置き換えられる別の２つのフレームを示す。
図１３ｂの画像はよりはっきりと焦点が合っており、図１３ａのぼやけた画像よりも視覚的に感じがよい。
【００５０】
初期キーフレームセットＮを上に述べたように生成した後、ショット・シーン構造に基づいて新しいキーフレームセットＮ'を構築することができる。
新しいキーフレームセットＮ'は、ユーザがより多くのキーフレームおよびより高い詳細度（Ｎ'＞Ｎ）、またはより少数のキーフレームおよびより低い詳細度（Ｎ'＜Ｎ）をビデオサマリに望む場合に望ましい場合がある。
【００５１】
より多くのキーフレームが必要な場合、追加の数のキーフレームを基礎となるビデオ内容から抽出しなければならない。
さらに抽出する必要のあるキーフレームＮＤ（ＮＤ＝Ｎ'−Ｎ）が与えられる場合、初期キーフレームセットＮを生成する場合に上に述べたような様式で、追加のキーフレームが、基礎となるシーン２２およびショット２４のすべてに、それぞれの重要値に基づいて割り当てられる。
基本的な割り当て規則は、重要なシーン２２およびショット２４ほど多くのキーフレームを得ることである。
上に述べたものと同様のキーフレーム抽出プロセスを、各ショット２４が新たに指定された数のキーフレームを得た後、適用することができる。
【００５２】
より少ないキーフレームが必要な場合、余分なキーフレームが初期キーフレームセットＮから除去される。
図１ｄに示すように、オリジナルセットＮから除去しなければならないキーフレームＮＤ（ＮＤ＝Ｎ−Ｎ'）が与えられる場合、ＮＤ枚のキーフレームが基礎となるシーン２２に分散される。
但し、シーン２２から除去すべきキーフレーム数はシーン２２の重要度に反比例する。
Ｒ枚のフレームをシーンｊのキーフレームセットから除去する必要があると想定する場合の手順は以下である。
すなわち、シーン２２内の最低重要度ショット２４から始めて各ショット２４をチェックする。
ショットが２つ以上のキーフレームを含む場合、最低重要度キーフレームを除去し、Ｒを１だけ減分する。
Ｒが０に等しい場合は停止し、その他の場合は次のショット２４に続く。
最後のショット２４に達した場合は、最低重要度ショット２４から再び始める。
あらゆるショット２４に残っているキーフレームが１枚のみであり、Ｒが依然として０よりも大きい場合、最低重要度ショット２４からはじめて、そのショットの最後のキーフレームを除去する。
【００５３】
したがって、ユーザの好みに基づいてスケーラブルなビデオサマリ８０を実現することができる。
さらに、初期キーフレームセットＮがオフラインで生成される場合、リアルタイムビデオ要約を実現することができる。
スケーラブルなビデオサマリの価値は、ユーザがビデオ階層（シーン−ショット−フレーム）ツリーに沿ってナビゲートを必要とする例で分かる。
たとえば、ユーザが特定のシーン２２またはショット２４の詳細なサマリを見たい一方で、他の短いレビューだけを見たい場合、本明細書に記載の本発明は、予め規定されているが、調整可能なスケールファクタを使用することによってこれを容易に実現することができる。
具体的には、初期キーフレーム割り当て数に基づいてスケールファクタを使用して、所望のショット、シーン、さらにはシーケンス全体に現在所望のキーフレーム数を計算することができる。
次いで、キーフレームが上に述べた方式を使用して抽出または除去される。
ユーザは、デフォルトのナビゲーションスケールに満足しない場合、各自が満足するように容易に調整することができる。
【００５４】
本明細書に記載のビデオ要約化およびナビゲーションシステムは、選ばれたプラットフォームが十分な計算能力を有するプロセッサ１０２、ビデオサマリを記憶するデータ記憶システム１０４、およびビデオサマリ８０の詳細レベルをユーザが変更できるようにするインタフェース１０６を有する限り、家庭用コンピュータ１００等、様々なプラットフォームに実装することができる。
データ記憶システム１０４は、ハードドライブディスクであっても、他の永久記憶装置であっても、または選ばれたプラットフォームのランダムアクセスメモリであってもよい。
ビデオサマリ８０は、表示装置１０８、たとえばビデオモニタやプリンタによって生成されるハードコピーに表示することができる。
【００５５】
［実験結果］
図１４ａおよび図１４ｂは、本明細書に記載のスケーラブルなビデオサマリ８０の一例を示し、図１４ａは特定のショットに初期生成される３枚のキーフレームを示し、図１４ｂはユーザが基礎となる内容をより詳細に見ることを要求した場合にさらに抽出される２枚のキーフレームを示す。
このショットは実際に、出席しているすべてのゲストを紹介する長いカメラパニングシーケンスを含み、２枚の追加キーフレームによりユーザがショットについての理解度を深めることができることが分かる。
【００５６】
特定の実施形態を好ましい実施形態の説明を目的として本明細書に図示し説明したが、本発明の範囲から逸脱することなく、図示し説明した特定の実施形態に代えて広範な代替および／または等価の実施態様を用い得ることが当業者により理解されよう。
コンピュータ分野および電気分野の当業者は、本発明を非常に広い範囲の実施形態で実施し得ることを容易に理解するであろう。
本願は、本明細書において説明した好ましい実施形態の適合形態および変形形態をいずれも包含することを意図する。
したがって、本発明は特許請求項および特許請求項の等価物によってのみ限定されることを明らかに意図する。
【図面の簡単な説明】
【００５７】
【図１ａ】ビデオ階層構造の概略図である。
【図１ｂ】本発明によるビデオサマリを作成する１つのプロセスを示すフローチャートである。
【図１ｃ】本発明による重要値計算の一実施形態を示すフローチャートである。
【図１ｄ】本発明によるキーフレーム除去の一実施形態を示すフローチャートである。
【図２】カメラのパニング、傾斜、およびズーミングのオプティカルフローフィールドを示す。
【図３】カメラの動きが量子化される８つの方向を示す。
【図４】ＭＰＥＧピクチャグループ構造の一例を示す。
【図５ａ】カメラの右へのパニングを示すヒストグラムの一例である。
【図５ｂ】カメラのズーミングを示すヒストグラムの一例である。
【図６ａ】カメラパニングシーケンスを含むビデオショットを示す統計ｒおよびＡｖｇＭａｇのグラフである。
【図６ｂ】カメラの動きなしのショットを含むビデオショットを示す統計ｒおよびＡｖｇＭａｇのグラフである。
【図７ａ】ＣｂＣｒ色空間において肌色が占める領域を示す。
【図７ｂ】ＣｂＣｒ色空間において肌色が占める領域を示す。
【図８ａ】肌色検出により或る顔が認識される一方で別の顔が無視される一例を示す。
【図８ｂ】肌色検出により或る顔が認識される一方で別の顔が無視される一例を示す。
【図９ａ】顔認識アルゴリズムが或るフレームにおいて顔の検出に失敗する一方で、別のフレームにおいて顔を検出する一例を示す。
【図９ｂ】顔認識アルゴリズムが或るフレームにおいて顔の検出に失敗する一方で、別のフレームにおいて顔を検出する一例を示す。
【図１０ａ】垂直エッジオペレータを適用して十分に焦点合わせされたキーフレームを選択する例を示す。
【図１０ｂ】垂直エッジオペレータを適用して十分に焦点合わせされたキーフレームを選択する例を示す。
【図１０ｃ】垂直エッジオペレータを適用して十分に焦点合わせされたキーフレームを選択する例を示す。
【図１０ｄ】垂直エッジオペレータを適用して十分に焦点合わせされたキーフレームを選択する例を示す。
【図１１】ビデオショット例のエッジエネルギーの計算された標準偏差のグラフである。
【図１２】ビデオショット例の重要曲線を示す。
【図１３ａ】フレームエッジエネルギーを考慮したキーフレーム選択を示す。
【図１３ｂ】フレームエッジエネルギーを考慮しないキーフレーム選択を示す。
【図１４ａ】本明細書に記載のスケーラブルなビデオサマリの一例を示す。
【図１４ｂ】本明細書に記載のスケーラブルなビデオサマリの一例を示す。
【図１５】本発明によるビデオサマリの作成に使用することができるコンピュータシステムの概略図である。
【符号の説明】
【００５８】
２０・・・ビデオシーケンス，
２２・・・シーン，
２４・・・ショット，
２６・・・フレーム，
１０２・・・データプロセッサ，
１０４・・・データ記憶装置，
１０６・・・ユーザインタフェース，
１０８・・・表示装置，
【図１ａ】
2005525034.tif 000007
【図１ｂ】
2005525034.tif 000008
【図１ｃ】
2005525034.tif 000009
【図１ｄ】
2005525034.tif 000010
【図２】
2005525034.tif 000011
【図３】
2005525034.tif 000012
【図４】
2005525034.tif 000013
【図５ａ】
2005525034.tif 000014
【図５ｂ】
2005525034.tif 000015
【図６ａ】
2005525034.tif 000016
【図６ｂ】
2005525034.tif 000017
【図７ａ】
2005525034.tif 000018
【図７ｂ】
2005525034.tif 000019
【図８ａ】
2005525034.tif 000020
【図８ｂ】
2005525034.tif 000021
【図９ａ】
2005525034.tif 000022
【図９ｂ】
2005525034.tif 000023
【図１０ａ】
2005525034.tif 000024
【図１０ｂ】
2005525034.tif 000025
【図１０ｃ】
2005525034.tif 000026
【図１０ｄ】
2005525034.tif 000027
【図１１】
2005525034.tif 000028
【図１２】
2005525034.tif 000029
【図１３ａ】
2005525034.tif 000030
【図１３ｂ】
2005525034.tif 000031
【図１４ａ】
2005525034.tif 000032
【図１４ｂ】
2005525034.tif 000033
【図１５】
2005525034.tif 000034
【国際調査報告】
2005525034.tif 000035
2005525034.tif 000036
2005525034.tif 000037