(57)【要約】【課題】  ビデオを自動的に編集してビデオ要約を生成するシステムおよび方法を提供する。【解決手段】  一態様では、ビデオからサブショットが抽出される。抽出されたサブショットの少なくとも一部分に関して重要度が計算される。その他のサブショットの重要度と比べて比較的高い重要度を有するサブショットに関するそれぞれの相対分布が特定される。特定された相対分布に基づき、特定のサブショットのなかでその他のサブショットに対して一様な分布を示さないサブショットがドロップされる。残っているサブショットがそれぞれの遷移と結合されてビデオ要約が生成される。【選択図】  図１
2004159331.tif 000002
【特許請求の範囲】
【請求項１】
ビデオデータシーケンスを自動的に編集してビデオ要約を生成するための方法であって、
前記ビデオデータシーケンスからサブショットを抽出する動作と、
前記サブショットの少なくとも一部分に関する重要度を計算する動作と、
その他のサブショットの重要度と比べて相対的により高い重要度を有する前記一部分の特定のサブショットを割り出す動作と、
前記特定のサブショットのなかの各サブショットの相対分布を特定する動作と、
前記特定のサブショットの各サブショットの相対分布に基づき、前記特定のサブショットのなかでその他のサブショットに対して一様な分布を有さないサブショットを前記特定のサブショットからドロップする動作と、
前記特定のサブショットのなかの残っているサブショットをそれぞれのショット遷移と結合して前記ビデオ要約を生成する動作とを含むことを特徴とする方法。
【請求項２】
前記サブショットの前記一部分は、前記サブショットの相当に高い方の品質のサブショットから成ることを特徴とする請求項１に記載の方法。
【請求項３】
前記割り出す動作と、前記特定する動作と、前記ドロップする動作は、以下の最適化
【数１】
2004159331.tif 000023
に基づくものであり、ここで、Ｉは、重要度であり、Ｈは、分布の一様性の測度であり、Ｍは、選択されたサブショットの数であることを特徴とする請求項１に記載の方法。
【請求項４】
ビデオデータシーケンスを自動的に編集してビデオ要約を生成するためのコンピュータプログラム命令を含むコンピュータ可読媒体であって、
前記コンピュータプログラム命令は、
前記ビデオデータシーケンスからサブショットを抽出する動作、
前記サブショットの少なくとも一部分に関する重要度を計算する動作、
その他のサブショットの重要度と比べて相対的により高い重要度を有する前記一部分の特定のサブショットを割り出す動作、
前記特定のサブショットのなかの各サブショットの相対分布を特定する動作、
前記特定のサブショットの各サブショットの相対分布に基づき、前記特定のサブショットのなかでその他のサブショットに対して一様な分布を有さないサブショットを前記特定のサブショットからドロップする動作、および
前記特定のサブショットのなかの残っているサブショットをそれぞれのショット遷移と結合して前記ビデオ要約を生成する動作のためにプロセッサによって実行可能であることを特徴とする媒体。
【請求項５】
前記サブショットの前記一部分は、前記サブショットの相当に高い方の品質のサブショットから成ることを特徴とする請求項４に記載のコンピュータ可読媒体。
【請求項６】
前記割り出すためのコンピュータプログラム命令、前記特定するためのコンピュータプログラム命令、および前記ドロップするためのコンピュータプログラム命令は、以下の最適化
【数２】
2004159331.tif 000024
に基づくものであり、ここで、Ｉは、重要度であり、Ｈは、分布の一様性の測度であり、Ｍは、選択されたサブショットの数であることを特徴とする請求項４に記載のコンピュータ可読媒体。
【請求項７】
ビデオデータシーケンスを自動的に編集してビデオ要約を生成するためのコンピューティングデバイスであって、
プロセッサと、
前記プロセッサに結合されたメモリであって、
前記ビデオデータシーケンスからサブショットを抽出する動作、
前記サブショットの少なくとも一部分に関する重要度を計算する動作、
その他のサブショットの重要度と比べて相対的により高い重要度を有する前記一部分の特定のサブショットを割り出す動作、
前記特定のサブショットのなかの各サブショットの相対分布を特定する動作、
前記特定のサブショットの各サブショットの相対分布に基づき、前記特定のサブショットのなかでその他のサブショットに対して一様な分布を有さないサブショットを前記特定のサブショットからドロップする動作、および
前記特定のサブショットのなかの残っているサブショットをそれぞれのショット遷移と結合して前記ビデオ要約を生成する動作のためにプロセッサによって実行可能であるコンピュータプログラム命令を含むメモリとを含むことを特徴とするコンピューティングデバイス。
【請求項８】
前記サブショットの前記一部分は、前記サブショットの相当に高い方の品質のサブショットから成ることを特徴とする請求項７に記載のコンピューティングデバイス。
【請求項９】
前記割り出すための命令、前記特定するための命令、および前記ドロップするための命令は、以下の最適化
【数３】
2004159331.tif 000025
に基づくものであり、ここで、Ｉは、重要度であり、Ｈは、分布の一様性の測度であり、Ｍは、選択されたサブショットの数であることを特徴とする請求項７に記載のコンピューティングデバイス。
【請求項１０】
独立の音楽源に関連してビデオデータシーケンスを自動的に編集するための方法であって、
サブショットおよびサブ音楽を含むメタデータを前記ビデオデータシーケンスおよび前記独立の音楽源から抽出する動作と、
前記サブショットの少なくとも一部分に関する重要度を計算する動作と、
その他のサブショットの重要度と比べて比較的高い重要度を有する前記一部分の特定のサブショットを割り出す動作と、
前記サブ音楽のそれぞれに関するそれぞれのムードを割り出す動作と、
サブショットの動きの激しさをサブ音楽のムードにマッチさせて前記サブショットの特定のサブショットを割り出す動作と、
前記特定のサブショットを対応するサブ音楽と整列させる動作と、
整列されたサブショットを対応するサブ音楽と融合して自動編集されたビデオを生成する動作とを含むことを特徴とする方法。
【請求項１１】
前記抽出する動作は、フレーム差分曲線を生成して前記ビデオデータシーケンスの中のサブショットを割り出す動作をさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記抽出する動作は、
前記ビデオデータシーケンスを第１の方向で解析してショットおよびサブショットを割り出す動作と、
前記ビデオデータシーケンスを第２の方向で解析して検出されたショットおよびサブショットをマージして１つまたは複数のシーンにする動作とをさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１３】
前記整列させる動作は、サブショット境界と音楽ビートの整列の基準、サブショット境界と文の整列の基準、および音楽ムードを動きの激しさとマッチさせる整列の基準に基づくことを特徴とする請求項１０に記載の方法。
【請求項１４】
前記抽出する動作は、
ショット、シーン、サブショットに関する動きの激しさおよび色エントロピー、ならびに前記ビデオデータシーケンスの音声チャネルからの発話データを割り出す動作と、
前記発話データから文の境界を検出する動作と、
前記独立の音楽源をそれぞれビートの位置に従って前記サブ音楽にセグメント化する動作とをさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１５】
前記サブショットから低品質のサブショットをドロップして相当に高い方の品質のサブショットを残す動作と、
前記相当に高い方の品質のサブショットに関する重要度を計算する動作と、
前記サブ音楽に関するムード値を計算する動作とを抽出する動作の後、マッチさせる動作の前にさらに含み、前記サブショットの特定のサブショットを前記サブ音楽にマッチさせる動作は、前記重要度にさらに基づき、前記特定のサブショットが、前記特定のサブショットの中で代表されないサブショットの重要度と比べて比較的高い重要度を有するサブショットであるように選択されるようにすることを特徴とする請求項１０に記載の方法。
【請求項１６】
前記整列させる動作は、１つまたは複数のサブショットの長さを変更して対応するサブショットの長さと対応するサブ音楽の長さが実質的に同じであるようにする動作をさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１７】
前記整列させる動作が、前記特定のサブショットの１つまたは複数のサブショットの中で検出された始まりと終りを有する文がカットされないように行われることを特徴とする請求項１０に記載の方法。
【請求項１８】
前記融合させる動作が、整列されたサブショットの中の文が対応するサブ音楽との関係で聴き取れなくされないように行われることを特徴とする請求項１０に記載の方法。
【請求項１９】
前記ビデオデータシーケンスは、ビデオフレームを含む方法であって、
前記ビデオフレームおよび／または前記サブショットの視覚上の品質を検出する動作と、
低品質のビデオフレームおよび／または低品質のサブショットをドロップして相当に高い方の品質のフレームおよび／またはサブショットを残す動作とを抽出する動作の後、マッチさせる動作の前にさらに含むことを特徴とする請求項１０に記載の方法。
【請求項２０】
前記ドロップされるフレームおよび／またはドロップされるサブショットは、ドロップされるフレームシーケンスおよび／またはドロップされるサブショットシーケンスを含み、低品質のフレームおよび／または低品質のサブショットは、劣悪な色エントロピー、および異常な動き解析結果の属性の任意の組合せに対応することを特徴とする請求項１９に記載の方法。
【請求項２１】
独立の音楽源に関連してビデオデータシーケンスを編集するためのコンピュータ実行可能命令を含むコンピュータ可読媒体であって、
前記コンピュータ実行可能命令は、
サブショットおよびサブ音楽を含むメタデータを前記ビデオデータシーケンスおよび前記独立の音楽源から抽出するための命令と、
前記サブショットの少なくとも一部分に関する重要度を計算するための命令と、
その他のサブショットの重要度と比べて比較的高い重要度を有する前記一部分の特定のサブショットを割り出すための命令と、
前記サブ音楽のそれぞれに関するそれぞれのムードを割り出すための命令と、
それぞれサブショットの動きの激しさを前記それぞれムードにマッチさせて、前記独立の音楽源と整列させ、融合させる前記サブショットの特定のサブショットを割り出すための命令と、
前記特定のサブショットを対応するサブ音楽と整列させるための命令と、
整列されたサブショットを対応するサブ音楽と融合して自動編集されたビデオを生成するための命令を含むことを特徴とするコンピュータ可読媒体。
【請求項２２】
前記抽出するための命令は、検出されたショットおよびサブショットをマージして１つまたは複数のシーンにするためのコンピュータプログラム命令をさらに含むことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項２３】
前記コンピュータプログラム命令は、前記抽出するための命令の後、前記マッチさせる命令の前、前記サブショットから低品質のサブショットをドロップして相当に高い方の品質のサブショットを残すための命令をさらに含むことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項２４】
前記整列させる動作は、サブショット境界と音楽ビートの整列の基準、サブショット境界と文の整列の基準、および音楽ムードを動きの激しさとマッチさせる整列の基準に基づくことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項２５】
前記整列させるための命令は、対応するサブショットの長さと対応するサブ音楽の長さが実質的に同じになるように１つまたは複数のサブショットの長さを変更するための命令をさらに含むことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項２６】
前記整列させる動作が、前記特定のサブショットの１つまたは複数のサブショットの中で検出された始まりと終りを有する文がカットされないように行われることを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項２７】
前記マッチさせるための命令は、前記それぞれのムードを
【数４】
2004159331.tif 000026
に従って特定するための命令をさらに含み、ただし、Ｅ（ｘ）およびＤ（ｘ）はそれぞれ、シーケンスｘの平均値および分散値を表わし、上付き文字θは、元のシーケンスの選択されたサブシーケンスを含む対応するシーケンスを表わすことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項２８】
前記マッチさせるための命令は、分散の一様性を測定するのにエントロピーではなく平均偏差の使用を介して前記特定のサブショットを選択するための命令をさらに含むことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項２９】
前記マッチさせるための命令は、前記特定のサブショットが、
【数５】
2004159331.tif 000027
に従って一様に分布するように前記特定のサブショットを選択するための命令をさらに含み、
ただし、
【数６】
2004159331.tif 000028
ただし、｜・｜は、有限集合の中の要素の数を表わすことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項３０】
前記マッチさせるための命令は、
【数７】
2004159331.tif 000029
に従って前記特定のサブショットを選択するための命令をさらに含むことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項３１】
前記マッチさせるための命令は、
前記サブショットの少なくとも一部分に関して、対応するサブショット色エントロピー、およびカメラの動きのタイプおよび速度にそれぞれが基づくそれぞれの重要度を計算するための命令をさらに含み、前記特定のサブショットは、前記特定のサブショットの１つではないサブショットと比べてそれぞれより高い重要度値を有することを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項３２】
前記それぞれの重要度は、前記対応するサブショットの中で発話が検出されたかどうかにさらに基づくことを特徴とする請求項３１に記載のコンピュータ可読媒体。
【請求項３３】
前記融合するための命令は、前記特定のサブショットの２つの間の、前記２つの類似性に基づき、長さを有する遷移を生成する動作をさらに含むことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項３４】
前記長さは、前記サブ音楽の対応するサブ音楽の中のビートの強さに基づくことを特徴とする請求項３３に記載のコンピュータ可読媒体。
【請求項３５】
前記ビデオデータシーケンスは、ビデオフレームを含み、前記方法は、
前記ビデオフレームおよび／または前記サブショットの視覚上の品質を検出する動作と、
低品質のビデオフレームおよび／または低品質のサブショットをドロップして相当に高い方の品質のビデオフレームおよび／またはサブショットを残す動作とを抽出する動作の後、マッチさせる動作の前にさらに含むことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項３６】
前記ドロップされるフレームおよび／またはドロップされるサブショットは、ドロップされるフレームシーケンスおよび／またはドロップされるサブショットシーケンスを含み、低品質のフレームおよび／または低品質のサブショットは、劣悪な色エントロピー、および異常な動き解析結果の属性の任意の組合せに対応することを特徴とする請求項３５に記載のコンピュータ可読媒体。
【請求項３７】
前記マッチさせるための命令は、前記特定のサブショットが、前記特定のサブショットの複数のサブショットから成るシーンおよび／またはショットにわたって一様に分布するように前記特定のサブショットを選択するための命令をさらに含むことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項３８】
前記特定のサブショットが、前記シーンにわたって一様に分布するように前記特定のサブショットを選択するための前記命令は、
【数８】
2004159331.tif 000030
に基づくことを特徴とする請求項３７に記載のコンピュータ可読媒体。
【請求項３９】
前記特定のサブショットが、前記ショットにわたって一様に分布するように前記特定のサブショットを選択するための前記命令は、
Ｈ（ＳＨ）（ｍ，ｖ，θ）＝Ｈ（ＳＨ（θ））
に基づくことを特徴とする請求項３７に記載のコンピュータ可読媒体。
【請求項４０】
独立の音楽源に関連してビデオデータシーケンスを編集するためのコンピューティングデバイスであって、
プロセッサと、
前記プロセッサに結合されたメモリであって、
サブショットおよびサブ音楽を含むメタデータを前記ビデオデータシーケンスおよび前記独立の音楽源から抽出する動作、
前記サブショットの少なくとも一部分に関する重要度を計算する動作、
その他のサブショットの重要度と比べて比較的高い重要度を有する前記一部分の特定のサブショットを割り出す動作、
それぞれサブ音楽ビートに基づいて前記サブ音楽のそれぞれに関するそれぞれのムードを計算する動作、
それぞれのサブショットの動きの激しさを前記それぞれのムードにマッチさせて、前記独立の音楽源と整列させて融合する前記サブショットの特定のサブショットを割り出す動作、
前記特定のサブショットを対応するサブ音楽と整列させて、前記特定のサブショットが、前記特定のサブショットによって代表されるショットおよび／またはシーンにわたって一様に分布するようにする動作、および
整列されたサブショットを対応するサブ音楽と融合して自動編集されたビデオを生成する動作のために前記プロセッサによって実行可能なコンピュータプログラム命令を含むメモリとを含むことを特徴とするコンピューティングデバイス。
【請求項４１】
整列させる動作は、サブショット境界と音楽ビートの整列の基準、サブショット境界と文の整列の基準、および音楽ムードを動きの激しさとマッチさせる整列の基準に基づくことを特徴とする請求項４０に記載のコンピューティングデバイス。
【請求項４２】
前記整列させるための命令は、検出された文をカットせずに、対応するサブショットの長さと対応するサブ音楽の長さが実質的に同じになるように１つまたは複数のサブショットの長さを変更するための命令をさらに含むことを特徴とする請求項４０に記載のコンピューティングデバイス。
【請求項４３】
前記マッチさせるための命令は、前記それぞれのムードを
【数９】
2004159331.tif 000031
に従って特定するための命令をさらに含み、ただし、Ｅ（ｘ）およびＤ（ｘ）はそれぞれ、シーケンスｘの平均値および分散値を表わし、上付き文字θは、元のシーケンスの選択されたサブシーケンスを含む対応するシーケンスを表わすことを特徴とする請求項４０に記載のコンピューティングデバイス。
【請求項４４】
前記マッチさせるための命令は、分散の一様性を測定するのにエントロピーではなく平均偏差の使用を介して前記特定のサブショットを選択するための命令をさらに含むことを特徴とする請求項４０に記載のコンピューティングデバイス。
【請求項４５】
前記マッチさせるための命令は、
【数１０】
2004159331.tif 000032
に従って前記特定のサブショットを選択するための命令をさらに含むことを特徴とする請求項４０に記載のコンピューティングデバイス。
【請求項４６】
前記マッチさせるための命令は、
前記サブショットの少なくとも一部分に関して、対応するサブショット色エントロピー、およびカメラの動きのタイプおよび速度にそれぞれが基づくそれぞれの重要度を計算するための命令をさらに含み、前記特定のサブショットは、前記特定のサブショットの１つではないサブショットと比べてそれぞれより高い重要度値を有することを特徴とする請求項４０に記載のコンピューティングデバイス。
【請求項４７】
前記それぞれの重要度は、前記対応するサブショットの中で発話が検出されたかどうかにさらに基づくことを特徴とする請求項４６に記載のコンピューティングデバイス。
【請求項４８】
前記融合するための命令は、前記特定のサブショットの２つの間の、前記２つの類似性に基づき、長さを有する遷移を生成する動作をさらに含むことを特徴とする請求項４０に記載のコンピューティングデバイス。
【請求項４９】
前記長さは、前記サブ音楽の対応するサブ音楽の中のビートの強さに基づくことを特徴とする請求項４８に記載のコンピューティングデバイス。
【請求項５０】
前記マッチさせるための命令は、前記特定のサブショットが、前記特定のサブショットの複数のサブショットから成るシーンおよび／またはショットにわたって一様に分布するように前記特定のサブショットを選択するための命令をさらに含むことを特徴とする請求項４０に記載のコンピューティングデバイス。
【請求項５１】
前記特定のサブショットが、前記ショットにわたって一様に分布するように前記特定のサブショットを選択するための前記命令は、以下の数式
Ｈ（ＳＨ）（ｍ，ｖ，θ）＝Ｈ（ＳＨ（θ））
に基づくことを特徴とする請求項５０に記載のコンピューティングデバイス。
【請求項５２】
前記ビデオデータシーケンスは、ビデオフレームを含み、前記コンピュータプログラム命令は、
前記ビデオフレームおよび／または前記サブショットの視覚上の品質を検出するための命令と、
低品質のビデオフレームおよび／または低品質のサブショットをドロップして相当に高い方の品質のビデオフレームおよび／またはサブショットを残すための命令とを抽出する動作の後、マッチさせる動作の前にさらに含むことを特徴とする請求項４０に記載のコンピューティングデバイス。
【請求項５３】
前記ドロップされるフレームおよび／またはドロップされるサブショットは、ドロップされるフレームシーケンスおよび／またはドロップされるサブショットシーケンスを含み、低品質のフレームおよび／または低品質のサブショットは、劣悪な色エントロピー、および異常な動き解析結果の属性の任意の組合せに対応することを特徴とする請求項５２に記載のコンピューティングデバイス。
【請求項５４】
独立の音楽源に関連してビデオデータシーケンスを編集するためのコンピューティングデバイスであって、
サブショットおよびサブ音楽を含むメタデータを前記ビデオデータシーケンスおよび前記独立の音楽源から抽出するための手段と、
前記サブショットの少なくとも一部分に関する重要度を計算するための手段と、
その他のサブショットの重要度と比べて比較的高い重要度を有する前記一部分の特定のサブショットを割り出すための手段と、
それぞれサブ音楽ビートに基づいて前記サブ音楽のそれぞれに関するそれぞれのムードを計算するための手段と、
それぞれのサブショットの動きの激しさを前記それぞれのムードにマッチさせて、前記独立の音楽源と整列させて融合する前記サブショットの特定のサブショットを割り出すための手段と、
前記特定のサブショットを対応するサブ音楽と整列させて、前記特定のサブショットが、前記特定のサブショットによって代表されるショットおよび／またはシーンにわたって一様に分布するようにするための手段と、
整列されたサブショットを対応するサブ音楽と融合して自動編集されたビデオを生成するための手段とを含むことを特徴とするコンピューティングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオデータを利用するシステムおよび方法に関する。詳細には、本発明は、入力音楽ファイルに関連して、または関連せずにビデオデータを自動的に編集することに関する。
【背景技術】
【０００２】
本特許出願は、本出願と同じ譲受人に譲渡され、参照により本明細書に組み込まれている2001年6月14日に出願した「ショット検出のための方法および装置（A Method and Apparatus for Shot Detection）」という名称の米国特許出願番号０９／８８２，７８７、および本出願と同じ譲受人に譲渡され、参照により本明細書に組み込まれている2002年11月1日に出願した「総合的なユーザ注目モデルを生成するためのシステムおよび方法（Systems and Methods for Generating a Comprehensive User Attention Model）」という名称の米国特許出願番号＿＿＿＿＿＿＿に関連する。
【０００３】
カメラ一体型ビデオ（ｃａｍｃｏｒｄｅｒ）が、ビデオを作成するのにプロによってもアマチュアによっても同様にますます使用されるようになっている。しかし、ビデオが作成されると、個人がそのビデオを再び観る機会、またはそのビデオを友人と共用する機会は、めったにない。これは、ある程度、大量の編集されていないビデオデータファイルを見るのに、通常、多量の時間が必要とされることに起因する。これにより、ビデオを要約するための効率的で効果的な処理ツールが緊急に必要とされることになる。
【０００４】
既存のビデオ要約方式またはビデオスキミング（ｓｋｉｍｍｉｎｇ）方式は、サイズを縮減し、ビデオデータを要約する一部のユーザのニーズに適合する可能性がある。ただし、そのような従来の技術を実施するのにコンピュータが使用される場合でさえ、その技術は、通常、相当に時間を消費し、労力がかかり、また、しばしば、専門家でないカメラ一体型ビデオのユーザに都合よく利用できる知識を超えたビデオ処理知識を要する。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
以下のシステムおよび方法は、既存のビデオ編集ツールの以上の限界、およびその他の限界に対処する。
【課題を解決するための手段】
【０００６】
ビデオを自動的に編集するシステムおよび方法を説明する。一態様では、ビデオからサブショットが抽出される。抽出されたサブショットの少なくとも一部分に関して重要度（ｉｍｐｏｒｔａｎｃｅ  ｍｅａｓｕｒｅ）が計算される。他のサブショットの重要度と比べて比較的高い重要度を有するサブショットに関するそれぞれの相対分布が特定される。特定された相対分布に基づき、特定のサブショットの中で他のサブショットに対して一様な分布を示さないサブショットがドロップされる。残っているサブショットは、それぞれショット遷移によって結合されて、ビデオ要約を構成する。サブショット境界を音楽ビートと揃え、サブショットの動きの激しさを音楽ムードとマッチさせることにより、独立の音楽源を付帯的な音楽として追加することもできる。
【０００７】
以下の詳細な説明は、添付の図を参照して述べられている。図では、符合の左端の数字が、その符号が最初に現れる図面（「図」）を特定する。
【発明を実施するための最良の形態】
【０００８】
概要
独立の音楽源に関連して、または関連せずにビデオデータシーケンスを自動的に編集するためのシステムおよび方法を説明する。このシステムの入力は、２つのメディアファイル、すなわち、１つのビデオファイルと１つの音楽ファイルである。ビデオファイルは、ビデオチャネルおよび音声チャネルから成る。したがって、実際には、３つの入力データシーケンス、すなわち、ビデオと音声（ビデオファイルからの）、および別個の、または独立の音楽ファイルが存在する。音楽に関連してビデオファイルを自動的に編集するのに、ビデオファイルが、まず、シーン、ショット、およびサブショットに階層式に分割される。次いで、メタデータ特徴が各サブショットから抽出される。以下に説明するとおり、そのような抽出されたサブショットメタデータは、動きの激しさ、カメラの動きのパターン（ｃａｍｅｒａ  ｍｏｔｉｏｎ  ｐａｔｔｅｒｎ）、色エントロピー情報、および音声データ（例えば、ビデオデータなどの音声チャネルからの発話（ｓｐｅｅｃｈ）、非発話（ｎｏｎ−ｓｐｅｅｃｈ）、文の境界）のあらゆる組合せを含むことが可能である。
【０００９】
次に、低品質のフレームシーケンス（例えば、劣悪な色エントロピー、異常な動き解析結果等を有するフレームシーケンス）が、抽出されたビデオのショット、サブショット、および／またはシーンから廃棄される。次に、それぞれの残っているサブショットの重要度が、抽出されたメタデータに基づいて計算される。計算された重要度に基づいて抽出された情報から入力ビデオデータシーケンスの要約が生成される。要約は、入力ビデオデータシーケンスから重要な概念を組み込み、入力シーケンスの低い重要度の態様および低品質の態様を濾過して取り除くように生成される。
【００１０】
入力音楽ファイルが、検出された強いビート位置または強いリズム位置に従ってクリップ、つまり「サブ音楽」にセグメント化される。それぞれのムード値が、サブ音楽に関して決められる。それぞれ音楽クリップのムードにおおむね相関するサブショットのいくつかが選択され、音楽クリップと揃えられて、融合される。出力は、音楽の強いビートで生じるサブショット遷移を伴い、ビデオの動きの激しさが、時間に関して音楽のリズムおよび計算されたムードとマッチさせられている自動編集されたビデオ要約である。さらに、自動編集されたビデオ要約の中の文が、カット（ｃｌｉｐ）されること、または別の形で融合された音楽によって聴き取れなくなることはない。
【００１１】
次のセクションは、音楽ファイルに関連してビデオデータを自動的に編集する例示的な動作環境、ビデオデータを編集するのに使用される例示的なコンピュータプログラム応用例およびプログラムデータ、ならびに専門用語および概念について概説し、また音楽に関連してビデオファイルを自動的に編集する例示的な手続きも提示する。
【００１２】
例示的な動作環境
同様の符号が同様の要素を指す図面を参照すると、本発明が、適切なコンピューティング環境において実施されているのが示されている。必須ではないが、本発明は、パーソナルコンピュータによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的な文脈で説明する。プログラムモジュールには、一般に、特定のタスクを行う、または特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、構成要素、データ構造等が含まれる。
【００１３】
図１は、音楽に関連してビデオファイルを自動的に編集する以下に説明するシステム、装置、および方法を実施することが可能な適切なコンピューティング環境１２０の例を示している。例示的なコンピューティング環境１２０は、適切なコンピューティング環境の一例に過ぎず、本明細書で説明するシステムおよび方法の使用および機能の範囲に関して何ら限定を示唆するものではない。また、コンピューティング環境１２０が、コンピューティング環境１２０内に示した構成要素のいずれか１つ、またはいずれかの組合せに関連する依存性または要件を有するものと解釈してはならない。
【００１４】
本明細書で説明する方法およびシステムは、多数の他の汎用、または特殊目的のコンピューティングシステム環境またはコンピューティングシステム構成で動作する。適切である可能性がある周知のコンピューティングシステム、コンピューティング環境、および／またはコンピューティング構成の例には、ハンドヘルドデバイス、マルチプロセッサシステム、マイクロプロセッサベースの家庭用電化製品、またはプログラマブル家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、可搬通信デバイス等が含まれるが、以上には限定されない。また、本発明は、通信網を介してリンクされた遠隔の処理デバイスによってタスクが行われる分散コンピューティング環境において実施することも可能である。分散コンピューティング環境では、プログラムモジュールは、ローカルのメモリ記憶デバイスと遠隔のメモリ記憶デバイスの中にともに配置することができる。
【００１５】
図１に示すとおり、コンピューティング環境１２０は、コンピュータ１３０の形態で汎用コンピューティングデバイスを含む。コンピュータ１３０の構成要素には、１つまたは複数のプロセッサまたは処理ユニット１３２、システムメモリ１３４、ならびにシステムメモリ１３４からプロセッサ１３２までを含む様々なシステム構成要素を結合するバス１３６が含まれることが可能である。
【００１６】
バス１３６は、様々なバスアーキテクチャのいずれかを使用するメモリバスまたはメモリコントローラ、周辺バス、アクセラレーテッドグラフィックスポート（ａｃｃｅｌｅｒａｔｅｄ  ｇｒａｐｈｉｃｓ  ｐｏｒｔ）、およびプロセッサバスまたはローカルバスを含むいくつかのタイプのバス構造のいずれかの１つまたは複数を表わす。例として、限定としてではなく、そのようなアーキテクチャには、インダストリスタンダードアーキテクチャ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）（ＭＣＡ）バス、エンハンストＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）（ＥＩＳＡ）バス、ビデオエレクトロニクススタンダーズアソシエーション（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）（ＶＥＳＡ）ローカルバス、およびメザニン（Ｍｅｚｚａｎｉｎｅ）バスとしても知られるペリフェラルコンポーネントインターコネクツ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔｓ）（ＰＣＩ）バスが含まれる。
【００１７】
コンピュータ１３０は、通常、様々なコンピュータ可読媒体を含む。そのような媒体は、コンピュータ１３０がアクセスすることができる任意の可用な媒体であることが可能であり、揮発性媒体と不揮発性媒体、取外し可能な媒体と取外し不可能な媒体がともに含まれる。図１で、システムメモリ１３４は、ランダムアクセスメモリ（ＲＡＭ）１４０などの揮発性メモリ、および／または読取り専用メモリ（ＲＯＭ）１３８などの不揮発性メモリの形態でコンピュータ可読媒体を含む。始動中など、コンピュータ１３０内部の要素間で情報を転送するのを助ける基本ルーチンを含む基本入力／出力システム（ＢＩＯＳ）１４２が、ＲＯＭ１３８の中に記憶されている。ＲＡＭ１４０は、通常、プロセッサ１３２によって即時にアクセスされることが可能であり、かつ／または現在、処理されているデータおよび／またはプログラムモジュールを含む。
【００１８】
コンピュータ１３０は、他の取外し可能な／取外し不可能な、揮発性／不揮発性のコンピュータ記憶媒体をさらに含むことが可能である。例えば、図１は、取外し不可能な不揮発性の磁気媒体（図示しておらず、通常、「ハードドライブ」と呼ばれる）に対して読取りおよび書込みを行うためのハードディスクドライブ１４４、取外し可能な不揮発性の磁気ディスク１４８（例えば、「フロッピー（登録商標）ディスク」）に対して読取りおよび書込みを行うための磁気ディスクドライブ１４６、およびＣＤ−ＲＯＭ／Ｒ／ＲＷ、ＤＶＤ−ＲＯＭ／Ｒ／ＲＷ／＋Ｒ／ＲＡＭまたはその他の光媒体などの取外し可能な不揮発性の光ディスク１５２に対して読取りおよび書込みを行うための光ディスクドライブ１５０を示している。ハードディスクドライブ１４４、磁気ディスクドライブ１４６、および光ディスクドライブ１５０はそれぞれ、１つまたは複数のインターフェース１５４によってバス１３６に接続される。
【００１９】
以上のドライブおよび関連するコンピュータ可読媒体により、コンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの不揮発性ストレージがコンピュータ１３０に提供される。本明細書で説明する例示的な環境は、ハードディスク、取外し可能な磁気ディスク１４８、および取外し可能な光ディスク１５２を使用しているが、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）などのコンピュータによってアクセス可能なデータを記憶することができる他のタイプのコンピュータ可読媒体も例示的な動作環境において使用できることが、当分野の技術者には認められよう。
【００２０】
例えば、オペレーティングシステム１５８、１つまたは複数のアプリケーションプログラム１６０、他のプログラムモジュール１６２、およびプログラムデータ１６４を含め、いくつかのプログラムモジュールが、ハードディスク、磁気ディスク１４８、光ディスク１５２、ＲＯＭ１３８、またはＲＡＭ１４０に記憶されていることが可能である。
【００２１】
音楽に関連してビデオデータを自動的に編集する本明細書で説明するシステムおよび方法は、動作システム１５８内部、１つまたは複数のアプリケーションプログラム１６０内部、他のプログラムモジュール１６２内部、および／またはプログラムデータ１６４内部で実施することができる。
【００２２】
ユーザは、キーボード１６６やポインティングデバイス１６８（「マウス」などの）入力デバイスを介してコンピュータ１３０にコマンドおよび情報を与えることができる。他の入力デバイス（図示せず）には、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ、シリアルポート、スキャナ、カメラ等が含まれることが可能である。以上の入力デバイスおよびその他の入力デバイスは、バス１３６に結合されたユーザ入力インターフェース１７０を介して処理ユニット１３２に接続されるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ）（ＵＳＢ）などの他のインターフェースおよびバス構造によって接続してもよい。
【００２３】
また、モニタ１７２または他のタイプの表示デバイスも、ビデオアダプタ１７４などのインターフェースを介してバス１３６に接続される。モニタ１７２に加えて、パーソナルコンピュータは、通常、出力周辺インターフェース１７５を介して接続することができるスピーカやプリンタなどの他の周辺出力デバイス（図示せず）も含む。
【００２４】
コンピュータ１３０は、遠隔コンピュータ１８２のような１つまたは複数の遠隔コンピュータに対する論理接続を使用するネットワーク化された環境において動作することが可能である。遠隔コンピュータ１８２は、コンピュータ１３０に関連して本明細書で説明した要素および特徴の多く、またはすべてを含むことが可能である。図１に示した論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７７および汎用のワイドエリアネットワーク（ＷＡＮ）１７９である。そのようなネットワーキング環境は、オフィス、企業全体のコンピュータ網、イントラネット、およびインターネットで一般的である。
【００２５】
ＬＡＮネットワーキング環境で使用される場合、コンピュータ１３０は、ネットワークインターフェースまたはネットワークアダプタ１８６を介してＬＡＮ１７７に接続される。ＷＡＮネットワーキング環境で使用される場合、コンピュータは、通常、ＷＡＮ１７９を介して通信を確立するためのモデム１７８、またはその他の手段を含む。内部にあることも、外部にあることも可能なモデム１７８は、ユーザ入力インターフェース１７０またはその他の適切な機構を介してシステムバス１３６に接続することができる。
【００２６】
図１に描いているのは、インターネットによるＷＡＮの特定の実施形態である。この場合、コンピュータ１３０は、モデム１７８を使用してインターネット１８０を介して少なくとも１つの遠隔コンピュータ１８２と通信を確立する。
【００２７】
ネットワーク化された環境では、コンピュータ１３０に関連して描いたプログラムモジュール、またはプログラムモジュールの部分が、遠隔のメモリ記憶デバイスの中に記憶されることが可能である。したがって、図１に描いたとおり、遠隔のアプリケーションプログラム１８９は、遠隔コンピュータ１８２のメモリデバイス上に常駐することが可能である。図示し、説明するネットワーク接続は、例示的であり、コンピュータ間で通信リンクを確立する他の手段も使用できることが認められよう。
【００２８】
図２は、図１の例示的なコンピューティングデバイス１２０のアプリケーションプログラム１６０およびプログラムデータ１６４のさらなる例示的な態様を示すブロック図である。アプリケーションプログラムは、音楽に関連してビデオデータを自動的に編集するようにプログラムデータを操作し、かつ／または生成する。詳細には、システムメモリ１３４が、例えば、ビデオ編集モジュール２０２を含むいくつかのアプリケーションプログラムを含むのが示されている。ビデオ編集モジュールは、ビデオデータシーケンス２０４および音楽ファイル２０６を入力として受け取る。以上２つの入力２０４および２０６は、３つのタイプのデータ、すなわち、ビデオ、音声、および音楽（ビデオおよび音声は、入力ビデオデータシーケンスからである）を含む。
【００２９】
ビデオ編集モジュール２０２は、メタデータ抽出モジュール２０８を利用して入力ファイルから情報２１０〜２１４を抽出する。詳細には、メタデータ抽出モジュールは、ビデオ構造パース（ｖｉｄｅｏ  ｓｔｒｕｃｔｕｒｅ  ｐａｒｓｉｎｇ）（すなわち、シーン、ショット、およびサブショットの抽出）、サブショット特徴抽出、文検出、およびビート／ムード検出を行う。（抽出されたサブショット特徴およびサブ音楽特徴のほとんどは、［０，１］に正規化される。）抽出モジュールは、コンテンツ選択モジュール２１６による抽出された情報の使用に先立って抽出された情報から低品質のサブショットを除去する。
【００３０】
コンテンツ選択モジュール２１６は、サブショットのそれぞれの重要度、ならびに音楽クリップのリズムおよびムードにマッチする特性に基づいてサブショットの特定のものを選択する（選択されたサブショットは、「他のデータ」２２４によって表される）。整列／融合（ａｌｉｇｎｍｅｎｔ／ｆｕｓｉｏｎ）モジュール２１８が、いくつかの整列基準に基づいて選択されたサブショットを対応する音楽クリップと整列させる。次に、整列されたサブショットとクリップ、つまりサブ音楽が一緒に融合されて自動編集されたビデオ２２０が生成される。次に、プログラムアプリケーション１６０およびプログラムデータ１６４の以上の態様およびその他の態様のそれぞれをより詳細に説明する。
【００３１】
ビデオ構造パース
メタデータ抽出モジュール２０８は、ショット検出アルゴリズムを使用してビデオデータシーケンス２０４内のショット境界を検出する。説明のため、ビデオデータシーケンスｖは、
シーン＝｛シーンｉ，０≦ｉ＜Ｋ（ＳＣ）｝                （１）
で表わされる一連のシーンから成る。同様に、ビデオｖも、一連のショットおよびサブショットとして、すなわち、
ショット＝｛ショットｉ，０≦ｉ＜Ｋ（ＳＨ）｝            （２）
サブショット＝｛サブショットｉ，０≦ｉ＜Ｋ（ＳＳ）｝    （３）
として表わすことができ、ただし、Ｋ（ＳＣ）、Ｋ（ＳＨ）、およびＫ（ＳＳ）は、それぞれ、ビデオｖの中のシーン（「ＳＣ」）、ショット（「ＳＨ」）、およびサブショット（「ＳＳ」）である。ＬＢ（ｘ）、ＲＢ（ｘ）、およびＬｅｎ（ｘ）を使用して、対応する要素ｘの左境界／右境界、および長さをそれぞれ表わす。Ｋ（ＳＳ）の代わりにＮを使用する。というのは、Ｋ（ＳＳ）が、以下の数式で非常に頻繁に使用されるからである。
【００３２】
ビデオデータシーケンス２０４の構造をパースするため、メタデータ抽出モジュール２０８が、２つの異なる方向に関してデータシーケンスを解析する。第１の方向では、ビデオデータは、ショット、およびサブショットと呼ばれるより小さいセグメントに分割される。一実施形態では、これは、サブショットを特定するのにそれぞれが使用されるフレーム差分曲線（ＦＤＣ）検出の最大頂または最大ピークを解析することによって達せられる。連続するビデオフレームの中のすべての対応するピクセルの輝度の差分を平均することによってフレーム差分が計算される。生のホームビデオの場合、ほとんどのショット境界は、ハードカット（ｈａｒｄ  ｃｕｔ）であり、ハードカットは、プロに編集されたビデオと比べて正しく検出するのがより容易である。
【００３３】
図３は、入力ビデオデータシーケンスに関して構造上の態様（例えば、サブショット間の境界）を検出するのにメタデータ抽出モジュール２０８によって使用される例示的なフレーム差分曲線（ＦＤＣ）を示す表３００である。この例では、３つのサブショット境界が明らかにされている。サブショット境界として適格であるには、ＦＤＣ上のピークが、ある距離だけ、例えば、サブショットの少なくとも最小の長さだけショット境界から離れていなければならない。ショットにおけるピークが検出された場合、ショットは、そのピークの位置で２つに切断される。この時点で、それぞれサブショットの長さが最大サブショット長（サブショット整列に関連して以下により詳細に説明する）より長い場合、その２つのサブショットにおけるＦＤＣの最大値が探し出され、各サブショットが、そのそれぞれの位置で分割される。このプロセスが、すべてのサブショットの長さが最大サブショット長より長くなくなるまで繰り返される。
【００３４】
メタデータ抽出モジュール２０８は、他の技術を使用してビデオデータシーケンス２０４の中のショットを特定することも可能である。例えば、一実施形態では、メタデータ抽出モジュールは、付録の参照文献［１］（参照により本明細書に組み込まれている）に記載されるショット検出技術を利用する。別の実施形態では、メタデータ抽出モジュールは、本出願と同じ譲受人に譲渡され、参照により本明細書に組み込まれている2001年6月14日に出願された「ショット検出のための方法および装置（A Method and Apparatus for Shot Detection）」という名称の米国特許出願番号０９／８８２，７８７に記載されるショット境界検出実施形態を利用する。
【００３５】
ショットおよびサブショットを検出することに続き、メタデータ抽出モジュール２０８は、第２の異なる方向に関してデータシーケンスを解析して検出されたショットをマージしてグループのショット、つまり「シーン」にする。例えば、付録の、参照により本明細書に組み込まれている参照文献［２］で説明されている力競争（ｆｏｒｃｅ  ｃｏｍｐｅｔｉｔｉｏｎ）によるビデオシーン抽出などの、文献において提示されている多数のシーングループ化方法が存在する。この実施形態では、類似度（ｓｉｍｉｌａｒｉｔｙ  ｍｅａｓｕｒｅ）によって決められた最も類似した隣接するシーン／ショットが、段階的に、より大きい単位に階層式にマージされる。類似度は、色調、彩度、および光度に関する、つまりＨＳＶ空間に関する平均され、量子化された色ヒストグラムの交差である。ショットがもはやマージされないポイント、つまり「停止条件」は、ショット類似度しきい値を設定することによって、または所望の数のシーンを決めることによって特定することができる。そのような停止条件は、主観的基準または客観的基準などの任意の数の異なる基準に基づいて手動で、または自動的に構成することができる。
【００３６】
サブショット特徴抽出
特定されたシーン、ショット、およびサブショット２１０から、メタデータ抽出モジュール２０８は、ビデオメタデータ２１２を抽出する。詳細には、サブショットに関して、重要度（「Ｉｍｐｔ」）、動きの激しさ、およびサブショットが属するシーン（「ＳＣ」）およびショット（「ＳＨ」）のＩＤを含め、いくつかの特徴が、サブショットのコンテンツおよび時間的位置に従って抽出される。これらの抽出される特徴は、次のとおり表わされる。  
Ｉｍｐｔ＝｛ｉｍｐｔｉ，０≦ｉ＜Ｎ｝                  （４）
動き＝｛動きｉ，０≦ｉ＜Ｎ｝                              （５）
ＳＣ＝｛ｓｃｉ，０≦ｉ＜Ｎ｝，０≦ｓｃｉ＜Ｋ（ＳＣ）      （６）
ＳＨ＝｛ｓｈｉ，０≦ｉ＜Ｎ｝，０≦ｓｈｉ＜Ｋ（ＳＨ）      （７）
【００３７】
抽出されるビデオメタデータ２１２には、例えば、色エントロピー、動きの激しさ、カメラの動きのタイプ／速度、および発話の任意の組合せがさらに含まれる。色エントロピーは、ＨＳＶ空間における量子化された色ヒストグラム（サブショットにわたって平均された）のエントロピーである。一実施形態では、動きの激しさは、ＭＰＥＧビデオにおけるＢフレームおよびＰフレームの動きベクトルの平均の長さを計算することによって得られる。動きの激しさは、動きベクトルフィールドを使用することによって、またより一般的なケースでは、いくつかの周知の技術のいずれかを使用して得ることができる。動きのタイプおよび速度は、いくつかの周知の技術のいずれかを使用して動きベクトルの方向から判定される。
【００３８】
発話／文検出
メタデータ抽出モジュール２０８は、入力ビデオデータシーケンス２０４の中の音声チャネルから発話を検出する。例えば、発話セグメントは、付録の参照文献［３］（参照により組み込まれている）に記載される技術を使用して特定される。詳細には、そのような例示的な技術を使用して、検出された音声を発話または非発話（例えば、音楽セグメントまたは雑音セグメント）として分類する。
【００３９】
文は、以下のとおり表現される。  
ＳＴ＝｛ｓｔｉ，０≦ｉ＜Ｋ（ＳＴ）｝                    （８）
文の切れ目が、特定された発話セグメント間の相当に長い休止を探し出すことにより、特定された発話セグメントに関して検出され、これにより、文が特定される。
【００４０】
図４は、文のセグメント化の結果を表わす例示的な発話検出データ曲線を示す表４００である。発話の中の検出された休止時間が、発話を文にセグメント化するのに使用される。発話データ曲線におけるピークが、休止時間に基づいて文がセグメント化された後、各文の平均エネルギーを表わす。
【００４１】
音楽のビートおよびムードの特定
メタデータ抽出モジュール２０８が、入力音楽２０６からの多数の特徴２１４をセグメント化し、特定する。詳細には、入力音楽ファイルが、相当に強いビートまたはリズムの場所に従って「サブ音楽」、つまりクリップにセグメント化される。「ムード」の特徴が、サブ音楽から特定される。
【００４２】
説明のため、以下の数学記号および数式を使用して、音楽のサブ音楽、ムード、およびビートを表わす。音楽ｍ２０６のサブ音楽は、
サブ音楽＝｛サブ音楽ｉ，０≦ｉ＜Ｍ｝                  （９）
によって表わされ、Ｍは、以下に説明する重要度基準に基づいて選択されたいくつかのサブショットを表わす。それぞれの計算されたサブ音楽の対応するムードは、
ムード＝｛ムードｉ，０≦ｉ＜Ｍ｝                      （１０）
によって表わされる。各サブ音楽（最後のサブ音楽を除く）後のビートの強さは、
ビート＝｛ビートｉ，０≦ｉ＜Ｍ−１｝                  （１１）
によって表わされる。
【００４３】
音楽ビートは、いくつかの高度なアルゴリズムを使用して検出することができる。例えば、入力音楽２０６のビートは、付録の参照文献［４］（参照により本明細書に組み込まれている）に記載されているアルゴリズムを使用して検出することができる。ただし、この実施形態では、メタデータ抽出モジュール２０８は、スライディングウインドウ（ｓｌｉｄｉｎｇ  ｗｉｎｄｏｗ）におけるエネルギー変動の局所極大を探し出すことにより、ビートを検出する。（スライディングウインドウは、ある長さのウインドウである。スライディングウインドウは、重なり合いを伴って、または伴わずにデータシーケンスから一部分を選択するのに使用される。例えば、１００秒間のデータシーケンスに対する５秒間を有するスライディングウインドウは、０〜５秒のセグメント、次に１〜６秒のセグメント、２〜７秒のセグメント、．．．９５〜１００秒のセグメントであることが可能である。）入力音楽２０６のムードは、サブ音楽におけるビート周波数から計算される。
【００４４】
図５は、音楽における検出された強いビートおよび強いムードを明らかにする例示的なデータ曲線を示す表である。各線分が、１つのサブ音楽を表わし、高さが、そのサブ音楽の「ムード」／強さを示す。
【００４５】
図６は、音楽２０６の入力データシーケンス、ビデオ２０４（１）の入力データシーケンス、および音声２０４（２）の入力データシーケンスの例示的な態様を示す表６００である。詳細には、図６の音楽データシーケンス、ビデオデータシーケンス、および音声データシーケンスは、抽出されたビデオメタデータおよび音声メタデータ、ならびに特定された音楽クリップ、つまり「サブ音楽」に関して示されている。ビデオデータシーケンスと音声データシーケンスは、並列に（すなわち、同一のデータシーケンスの一部として）入力される。これは、組合せで、ビデオデータシーケンスと音声データシーケンスが、入力ビデオデータシーケンス２０４を表わすからである。
【００４６】
音楽２０６データセグメント、ビデオ２０４（１）データセグメント、および音声２０４（２）データセグメントは、互いに垂直に並べられて、特定された構造（例えば、シーン、ショット、サブショット／サブ音楽、および文の境界）に関するデータ関係を示している。例えば、表の水平軸は、入力データシーケンスの長さ、またはサイズを表わす。この例は、入力音楽セグメントを入力ビデオデータシーケンス（ビデオおよび音声）に比べて小さいものとして示しているが、入力音楽セグメントは、ビデオデータシーケンスより大きい、または時間が長いことも可能である。
【００４７】
入力データシーケンス成分に関して、音楽２０６は、相当に強いビートまたはリズムの場所に従って「サブ音楽」、つまりクリップにセグメント化されているものとして示されている。クリップのそれぞれは、音楽データ線に直交する線分で示されている。ビデオデータ２０４（１）は、ショットおよびサブショットにセグメント化されているのが示され、ショットとサブショットの隣接した組合せが、シーンを表わす。ショットおよびサブショットは、ビデオデータ線に垂直な対応する線分で特定されている。音声データ２０４（２）は、文を特定するように解析されているものとして示されている。文は、音声データ線のすぐ上に並べられた対応する線分で示すとおり、音声データ線に対して境界および長さを有するものとして示されている。
【００４８】
コンテンツ選択
この時点で、図２を参照すると、入力ビデオシーケンス２０４のビデオ構造２１０およびメタデータ２１２（例えば、動きの激しさ、色エントロピー、音声文／エネルギー等）の態様が、ビデオデータシーケンスから抽出されている。さらに、音楽クリップ、つまりサブ音楽、リズム、およびムードの特徴２１４が、入力音楽２０６から抽出されている。コンテンツ選択モジュール２１６は、それらの抽出され、計算された特徴２１０〜２１６を解析して、一連のサブショットを入力音楽２０６と整列させ、統合し、または融合して自動編集されたビデオ２２０を生成するために選択する。（整列および融合は、整列−融合プログラムモジュール２１８によって行われる）。自動編集されたビデオは、基本的に、入力音楽に関連して編集されている入力ビデオデータシーケンスの要約である。
【００４９】
コンテンツ選択モジュール２１６は、抽出されたビデオのショット、サブショット、および／またはシーン２１０から低品質のフレームシーケンス（例えば、劣悪な色エントロピー、異常な動き解析結果等を有するフレームシーケンス）を取り除く。例えば、相当に低い色エントロピーで特定された非常に暗いイメージ、または非常に明るいイメージ、および均質なイメージ（例えば、床または壁）が、特定されたサブショットから取り除かれる。非常に暗いイメージ、または非常に明るいイメージは、ビデオ露出パラメータがうまく設定されていない場合に生成される可能性がある。均質なイメージ（例えば、床または壁）は、誤った焦点設定によって生じさせられる可能性がある。
【００５０】
カメラの動きのタイプおよび速度を解析することにより、非常に高速なパン（ｐａｎ）またはズームを表わすビデオセグメントが、検出され、取り除かれる。そのようなビデオセグメントは、マシンを停止させることなく視点を急速に変えることにより、または素早くズームインする／ズームアウトすることにより生じさせられる可能性がある。さらに、動き解析を使用して、検出されたビデオショットおよびビデオサブショットから激しく揺れ動くイメージを取り除く。この場合、７つのパラメータを使用してどこでカメラが揺れているかを特定する。７つのパラメータとは、グレー階調度、色ヒストグラム、順方向予測比（ｆｏｒｗａｒｄ  ｐｒｅｄｉｃｔｉｏｎ  ｒａｔｉｏ）Ａ、非予測比Ｂ、動きベクトルの大きさ、動きベクトルの分散、および動きベクトルの方向ヒストグラムである。後の５つのパラメータはすべて、ＭＰＥＧストリームの中のＰフレームの動きベクトルフィールドに基づいて計算される。２つの比、ＡおよびＢは、以下のとおり定義される。
【００５１】
【数１】
2004159331.tif 000003
【００５２】
【数２】
2004159331.tif 000004
【００５３】
一実施形態では、カメラ揺れ検出中、１５フレームのサイズを有するスライディングウインドウが、以上のパラメータの統計値を計算するのに使用される。つまり、平均のグレー階調度、色ヒストグラム差、平均の順方向予測比Ａ、平均の非予測比Ｂ、動きベクトルの平均の大きさ、動きベクトルの平均分散、および動きベクトルの優勢な方向である。以上の統計パラメータに基づき、次の２つのステップでカメラの動きを検出する。
１）平均Ａが、しきい値および平均Ｂより低い場合、動きベクトルの平均の大きさ、および動きベクトルの平均分散は、それぞれ、しきい値よりも大きく、他方、現在のビデオクリップがカメラの揺れの候補である優勢なカメラの動きは全く存在しない。
２）平均のグレー階調度がより低い値を有し、色ヒストグラム差が当該のクリップにおいて高い場合、当該のクリップは、カメラが揺れているセグメント（ｃａｍｅｒａ  ｓｈａｋｉｎｇ  ｓｅｇｍｅｎｔ）であると確認される。
【００５４】
相対サブショット重要度を計算すること
抽出されたビデオ構造２１０から低品質のサブショットを取り除くことに続き、コンテンツ選択モジュール２１６は、それぞれの残っているサブショットに関する重要度を計算する。入力ビデオデータシーケンスの要約２２２が、計算された重要度に基づいて抽出された情報から生成される。要約は、入力シーケンスのより低い重要度の態様およびより低い品質の態様が既に濾過されて取り除かれており、入力ビデオデータシーケンスからの重要な概念を組み込むように生成される。
【００５５】
一実施形態では、抽出された／計算された色エントロピー、動きの激しさ、カメラの動きのタイプ／速度、および発話の特徴２１２が組み合わされて「重要度」が生成される。例えば、重要度は、以下に基づく。
ｉｍｐｔ＝ｐ１色エントロピー＋ｐ２動きの激しさ＋ｐ３タイプ＋ｐ４発話  （１２）
ただし、
ｐ１＋ｐ２＋ｐ３＋ｐ４＝１、かつ
【００５６】
【数３】
2004159331.tif 000005
【００５７】
ｐ＝｛ｐｉ，１≦ｉ＜４｝の値は、ユーザのバイアスに基づいて決められる。
【００５８】
図７は、例示的な色エントロピーのデータ曲線、動きの激しさのデータ曲線、および計算されたサブショット重要度のデータ曲線を示す表７００であり、これらのデータ曲線に関する情報は、入力データシーケンスから抽出され、かつ／または計算されている。
【００５９】
この実施形態は、サブショット重要度を決める要因として色エントロピー、動きの激しさ、カメラの動きのタイプ／速度、および発話の組合せを利用するが、その他の技術を使用することも可能である。例えば、別の実施形態では、「総合的なユーザ注目モデルを生成するためのシステムおよび方法（Systems and Methods for Generating a Comprehensive User Attention Model）」という名称の米国特許出願（参照により組み込まれている）に記載される技術を使用して、サブショット重要度を決めることも可能である。
【００６０】
最適化ベースのサブショット選択
一実施形態では、コンテンツ選択モジュール２１６が、重要なサブショットを入力音楽２０６との整列および融合のために選択するための最適化ベースのサブショット選択動作を実施する。選択されたサブショット２１０は、計算されたサブ音楽ムード２１４とマッチさせられる。選択されたサブショットは、ビデオ要約２２２の中でショットを構成し、最終的にシーンを構成するその他の選択されたサブショット（まだ音楽と整列または融合させられていない）に対して一様に分布している。最適化ベースのサブショット選択動作を以下の制約、つまり数式に関連して説明する。
【００６１】
Θが、Ｍ個のサブショットを含む｛０，１，２，．．．，Ｎ−１｝というすべてのサブショット部分集合の集合を表わすものとすると、問題（例えば、全体のサブショットの集合から重要なサブショットを選択し、同時に、音楽を選択されたサブショットとマッチさせ、シーンレベルおよびショットレベルにおいて、選択されたサブショットの分布をほぼ正規分布にすること）は、以下のとおり表わされる。
最大化／最小化目的関数（ｍ，ｖ，θ）、ただし、θ∈Θ        （１５）
他のサブショットより高い相対重要度のサブショットを選択するのに、コンテンツ選択モジュール２１６は、サブショットの正規化された重要度を以下に従って測定する。
【００６２】
【数４】
2004159331.tif 000006
【００６３】
サブショットを音楽ムードとマッチさせるのに、コンテンツ選択モジュール２１６は、選択されたサブショットの音楽ムードシーケンスと動きの激しさのシーケンスの相関係数を利用する。つまり、
【００６４】
【数５】
2004159331.tif 000007
【００６５】
ただし、
【００６６】
【数６】
2004159331.tif 000008
【００６７】
（便宜上、Ｅ（ｘ）で表わすこともする）およびＤ（ｘ）は、シーケンスｘの平均および分散を表わし、上付き文字θは、対応するシーケンスが、元のシーケンスの選択されたサブシーケンスであることを意味する。すなわち、
−１≦ρ（ｍ，ｖ，θ）≦１                            （１８）
【００６８】
コンテンツ選択モジュール２１６は、正規化されたエントロピーを介して分布の一様性を表わし、正規化されたエントロピーは、シーンレベルでは、以下に基づく。
【００６９】
【数７】
2004159331.tif 000009
【００７０】
ショットレベルにおける分布の一様性は、次のとおり表わされる。Ｈ（ＳＨ）（ｍ，ｖ，θ）＝Ｈ（ＳＨ（θ））。したがって、分布の一様性の全体的な測度は、以下のとおりである。  
Ｈ（ｍ，ｖ，θ）＝ｋ１Ｈ（ＳＣ）（ｍ，ｖ，θ）＋ｋ２Ｈ（ＳＨ）（ｍ，ｖ，θ）、ただし、ｋ１，ｋ２≧０，ｋ１＋ｋ２＝１                            （２０）
【００７１】
以上の公式において、
０≦Ｈ（ｍ，ｖ，θ）≦１                              （２１）
したがって、最適化ベースのサブショット選択を行うのに、以下を満たすθ＊を特定する。
【００７２】
【数８】
2004159331.tif 000010
【００７３】
すなわち、
−α≦Ｆ（ｍ，ｖ，θ）≦１                            （２３）
（２６）で（ρ＋１）／２をρで置き換えると、Ｆ（ｍ，ｖ，θ）を［０，１］に正規化することができる。以下に説明するとおり、以上の最適化ベースのサブショット選択アルゴリズムは、非線形０−１プログラミング問題としてさらに明確に書き換えることができる。
【００７４】
詳細には、部分集合θ∈Θを以下のとおり、Ｎ次元の０−１シーケンスｘによって表わすこともできる。
【００７５】
【数９】
2004159331.tif 000011
【００７６】
重要度Ｉ（ｍ，ｖ，θ）は、以下のとおり書き換えることができる。
【００７７】
【数１０】
2004159331.tif 000012
【００７８】
これは、線形関数である。
【００７９】
以上に鑑みて、サブショット分布の一様性の測度を以下のとおり、書き換えることができる。
【００８０】
【数１１】
2004159331.tif 000013
【００８１】
上式で、
【００８２】
【数１２】
2004159331.tif 000014
【００８３】
であり、上式で、｜・｜は、有限集合の中の要素の数を表わす。この測度は、非線形である。前述した最適化ベースのサブショット選択動作の「動き−ムード」マッチング測度も同様なやり方で書き換えることができ、これも、線形関数ではない。
【００８４】
したがって、最適化ベースのサブショット選択動作は、以下のとおり非線形の０−１整数プログラミング問題として書き直される。
【００８５】
【数１３】
2004159331.tif 000015
【００８６】
Θの中の要素の数、つまり可能な解空間のサイズは、以下のとおりである。
【００８７】
【数１４】
2004159331.tif 000016
【００８８】
ＮおよびＭが大きい場合、この値は、指数関数さえよりも急速に増加する。これに鑑みて、最適化ベースのサブショット選択は、ＮＰ困難問題（すなわち、非決定論的多項式時間困難問題（Ｎｏｎ−ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｐｏｌｙｎｏｍｉａｌ−ｔｉｍｅ  ｈａｒｄ  ｐｒｏｂｌｅｍ））である。したがって、局所最適解を見つけるのに次元を減らすアルゴリズムおよび遺伝的アルゴリズムが使用される。
【００８９】
例えば、次元を減らすことに関して、ＭおよびＮが大きい場合、探索空間は非常に大きい。ただし、ＭおよびＮが十分に小さい場合、数式の複雑さは急速に減少する。これにより、この問題を網羅的な探索によって解決することができるより小さい下位問題に分けるように啓発される。妥当な方法は、ビデオの中のシーンの数に従って音楽をいくつかのセグメントに分割することであり、すると、目的関数が音楽の各セグメントに関して最適化される。シーン数は、コントロールされる。したがって、音楽の各セグメントに割り当てられるサブ音楽の数は、シーンに入るように制約される。各下位問題を解決した後、全体的な結果が、自動編集されたビデオ２２０である最終的な解である。
【００９０】
ＮＰ困難問題を解決するための一般的な探索法は、周知の遺伝的アルゴリズム手法であり、これは、多項式時間における大域最適解は保証しないが、十分に良好な解を提供する。遺伝的アルゴリズムを使用するため、２つの問題に対処する。１つは、解（ポピュレーション（ｐｏｐｕｌａｔｉｏｎ））の符号化法である。都合のよいことには、この問題は、０−１プログラミングであり、したがって、その０−１シーケンスを直接に可能な解の、すなわち、遺伝的アルゴリズムのポピュレーションの符号とする。
【００９１】
第２の問題は、どのように親の解から子の解を生成するかである。この問題に関して、容認できる解の近傍は、（２４）に示した制約を満たさなければならない。したがって、次の方法を使用して単一の親による子の遺伝子を生成することができる。  
０≦Ｒ０＜Ｒ１＜Ｒ２＜Ｒ３＜Ｎ                            （３１）
によって表わされる（０，Ｎ）で４つの整数をランダムに生成する。「対立遺伝子」クリップ［Ｒ０，Ｒ１）および［Ｒ２，Ｒ３）が交換されて子の解（または「染色体」）が獲得される。遺伝的アルゴリズムは、最大回数の反復に達したとき、または所望の結果が達せられたときに停止される。
【００９２】
以上に鑑みて、３つの部分から成る最適化ベースのサブショット選択アルゴリズムの客観的な態様だけを単純化することができる。これは、制約のないプログラミング問題であることを想い起こされたい。この３つの部分には、サブショット重要度、サブショット／ムード相関、および分布の一様性の測度が含まれる。数式（２８）、Ｉ（ｍ，ｖ，ｘ）は、線形関数である。
【００９３】
ビデオの最も重要な部分だけを残しておくことを望む場合、Ｉ（ｍ，ｖ，ｘ）を目的関数とする。すると、問題は、非常に特殊なものになり、行う必要があるのは、ビデオからＭ個の最も重要なサブショットを選ぶことだけである。ただし、この種の結果は、実質的に最適な解を与えない可能性がある。というのは、多数の同様なサブショットが選択される可能性があるからである。これに鑑みて、分布の一様性を使用して、選択されたサブショットの一様な分布が存在することを確実にする。つまり、以下の最適化問題を解決することによって付帯的な音楽を伴わないビデオ要約を自動的に生成することができる。
【００９４】
【数１５】
2004159331.tif 000017
【００９５】
ただし、Ｉは、重要度であり、Ｈは、分布の一様性の測度であり、Ｍは、選択されたサブショットの数である。
【００９６】
エントロピーは、非線形関数である。ただし、以下のとおり、エントロピーの代わりに平均偏差を使用して分布の一様性を測定する場合、
【００９７】
【数１６】
2004159331.tif 000018
【００９８】
測度は、区分的な線形の目的関数として書き直すことができる。つまり、
ＤＮ（ｍ，ｖ，ｘ）＝１−λ・ＭＤ（ｍ，ｖ，ｘ）          （３４）
であり、ただし、λは、上式の第２項を間隔［０，１］に正規化するのに使用される係数である。ＭＤ（ｍ，ｖ，ｘ）の最小値は、ゼロであり、
【００９９】
【数１７】
2004159331.tif 000019
【０１００】
である。したがって、λを以下のように選択する
【０１０１】
【数１８】
2004159331.tif 000020
【０１０２】
ショットレベルで、分布の一様性を同様なやり方で書き直すことができる。分布の一様性の測度を区分的関数に移すことにより、０−１プログラミングにおける前の探求結果を利用することができる。各シーンにある数の選択されたサブショットを割り当てることにより、分布の一様性の測度は、非常に低くはなくなる。したがって、相当に一様に分布してもいる十分に重要なサブショットを特定することができる。
【０１０３】
数式３２〜３６で表現される以上の単純化は、選択されたサブショットを音楽とマッチさせない最適化ベースのビデオ要約／編集技術を介してビデオ要約２２２を生成するのに使用される。また、音楽マッチング以外のいくつかのさらなる制約を追加することを望む場合、それらの制約に従って所望の最適化結果が獲得される。
【０１０４】
例えば、目的関数から相関係数を抽出して、制約として使用することができる。これにより、所与のホームビデオに対して最適にマッチする音楽を選択することができる。例えば、ビデオｖ、およびいくつかの異なる音楽ファイルｍ１，ｍ２，．．．，ｍｋに対して最適化手続きを適用する。相関係数を最大の値、すなわち、ｍｉ，＝ａｒｇ  ｍａｘ  ρ（ｍｊ、ｖ、θ）にする音楽が、そのビデオに対して最適にマッチする音楽である。さらに、３つの成分の１つまたは複数を強調する必要がある場合、その１つまたは複数を制約とすること、または数式（２９）および（３２）においてその１つまたは複数により大きい重みを与えることができる。
【０１０５】
選択されたサブショットと音楽の整列および融合
整列／融合モジュール２１８は、選択されたサブショット（コンテンツ選択モジュール２１６によって選択された）と音楽を以下の整列基準に関して整列させる。すなわち、
出力ビデオにおけるサブショット遷移（これは、出力ビデオにおけるショット遷移である）が音楽のビートに対応するようにするサブショット境界と音楽ビートの整列の基準、
文がサブショット境界によって途中で切断されないようにするサブショット境界と文の整列の基準、および
コンテンツ選択モジュール２１６の最適化ベースのサブショット選択動作に関連して前述した音楽ムードを動きの激しさとマッチさせる整列基準である。
【０１０６】
以上の整列基準を実施するため、整列−融合モジュール２１８が、サブショットの長さとサブ音楽の長さを編集して、それぞれの長さが実質的に同じであるようにする。（説明のため、最大の長さと最小の長さを以下の構文で表わす、ＬｍａｘおよびＬｍｉｎ）。この目的で、選択されたサブショットの長さが対応するサブ音楽より長い場合、サブショットは、等しい長さになるまで短くされる。反対に、サブショットの長さがサブ音楽より短い場合、サブショットは、同一のショットの中にある隣接するサブショットとマージされる。文の整列に関しては、文が１つのサブショットの中に含まれることを確実にするようにサブショット境界が移動される。文、および対応するサブショットが対応するサブ音楽より長い場合、文がフェードアウトされるか、または代替として、サブ音楽が、相当に類似したムードマッチを有する別のサブ音楽とマージされる。
【０１０７】
オプションとして、前述したサブショット／文／サブ音楽整列動作を最適化することができる。整列後の目的関数値は、特定のサブショットに関する最適化ベースのサブショット選択手続き（コンテンツ選択モジュール２１６動作を参照されたい）における前に計算した値と比べて相当に変化している可能性がある。これは、説明した整列動作が、サブショットの対応する特徴を（例えば、サブショットを短くすること、またはマージすることによって）変化させる可能性があるためである。整列される前と整列された後のサブショットの特徴の差を考慮に入れるため、整列されたサブショットの特徴は、元の選択されたサブショットの特徴にできる限り実質的に近いところまで修正する。
【０１０８】
例えば、サブショットｉは、長さが対応するサブ音楽、サブ音楽ｊより長い選択されたサブショットであり、サブショットｉを切断する必要があるものと想定する。ＳＳｋが、長さがＬｅｎ（サブ音楽ｊ）に等しいサブショットｉのすべてのサブシーケンスを表わすものとする。すると、整列されたサブショットは、
【０１０９】
【数１９】
2004159331.tif 000021
【０１１０】
によって決定され、ただし、Ｉｍｐｔ（ＳＳｋ）および動き（ＳＳｋ）は、ＳＳｋの重要度および動きの激しさをそれぞれ表わす。反対に、サブショットｉの長さがＬｅｎ（サブ音楽ｊ）より短い場合、サブショットｉに隣接するサブショットをマージさせ、次に前述した手続きを行う。さらに、整列されたサブショットの特徴を使用して適合性を（自動編集されたビデオ２２０に組み込むためにサブショットを特定する、または選択するのに使用される遺伝的アルゴリズムにおける目的関数値）を計算することができ、これにより、整列によって生じさせられる誤差がさらに良好に小さくされることが可能である。
【０１１１】
整列−融合モジュール２１８が、選択され、整列されたサブショット２２４と音楽２０６を融合し、または統合して自動編集されたビデオ２２０を生成する。これを実現するため、多数の異なるサブショット間遷移が使用される。２つのサブショット間の遷移のタイプは、以下のとおり記述されるその２つのショットの類似性に基づいて決定される。
シーンＩＤｉ＝シーンＩＤｉ＋１である場合、フェードアウトする／フェードインし、そうではなく、
シーンＩＤｉ≠シーンＩＤｉ＋１である場合、その他のタイプからランダムに選択する
この実施形態では、それぞれのサブショット間で使用するために最大で１５の異なるタイプの遷移から選択することができる。これらのサブショット遷移は、選択され、整列されたサブショット２２４を音楽２０６と融合して自動編集されたビデオファイル２２０にするマイクロソフトコーポレーションのＤｉｒｅｃｔＸ（登録商標）によって提供される。
【０１１２】
２つのそれぞれのサブショット間の遷移の長さは、対応するサブ音楽２２４のビートの強さによって決まり、以下の数式（３８）によって記述される。  
遷移の長さｉ＝１−ビートｉ                                （３８）
ただし、０≦ｉ＜Ｍ−１である。ビデオ／音楽のより多くの特徴、およびユーザのバイアスを考慮に入れることによってより複雑な遷移選択法を設計することができる。
【０１１３】
代替の実施形態−規則ベースのサブショット選択
例えば、次元を減らすこと、および遺伝的アルゴリズムを使用することによって前述した最適化ベースのサブショット選択の数式を解決する代わりに、他の基準を使用して、サブショットを後に入力音楽２０６と整列させるために選択することができる。
【０１１４】
例えば、コンテンツ選択モジュール２１０は、いくつかの規則ベースの基準を使用して音楽２０６をＭＳＳｊで表わされるＫ（ＳＣ）個のセグメントに分割することができる。これらのセグメントは、前述した音楽クリップまたはサブ音楽には対応しない。各セグメントの長さは、以下によって定義されるシーンの平均サブショット重要度によって決まる。
【０１１５】
【数２０】
2004159331.tif 000022
【０１１６】
次に、コンテンツ選択モジュールは、音楽セグメントに対して各シーン、シーンｉからサブショットを選択し、シーンｉから選択されるサブショットの数は、ＭＳＳｊの中のサブ音楽の数に等しい。
【０１１７】
このようにして、一度に音楽の１つのセグメントと１つのビデオシーンだけを考慮するだけでよい。また、シーンに関しては、選択がショットに関して行われるようにプロセスを繰り返すことができる。シーンの中のショットの数が割り当てられたサブショット数より多い場合、最も重要度の低いショットがドロップされる。その後、各ショットから１つの最も重要なサブショットが選択され、音楽との関連で互いに結合される。
【０１１８】
音楽に関連してビデオを自動的に編集する手続き
図８は、独立の音楽源に関連してビデオを自動的に編集する例示的な手続き８００を示す流れ図である。説明のため、この手続きの動作を図２のコンピュータプログラムアプリケーション１６０およびプログラムデータ１６４に関連して説明する。ブロック８０２で、メタデータ抽出モデルが、入力ビデオデータシーケンス２０４からメタデータ（ショット、サブショット、シーン、動きの激しさ、カメラ注目（ｃａｍｅｒａ  ａｔｔｅｎｔｉｏｎ）等）を抽出し、かつ／または計算する。ブロック８０４で、メタデータ抽出モデルは、独立の音楽源２０６からメタデータ（サブ音楽、リズム、ムード等）を抽出し、かつ／または計算する。
【０１１９】
ブロック８０６で、コンテンツ選択モジュール２１６が、抽出されたビデオ構造２１０から低品質のサブショットを取り除く。ブロック８０８で、コンテンツ選択モジュールは、残っているサブショットのそれぞれの重要度を計算する。ブロック８０２で、コンテンツ選択モジュールは、少なくともある程度、サブブロックの動きの激しさ（抽出されたビデオメタデータ２１２の一部）を計算されたサブ音楽ムード（抽出された音楽特徴２１４の一部）とマッチさせることに基づき、入力ビデオデータ２０４の要約２２２を表わすサブショットを選択する。図２の例では、選択されたサブショットは、「その他のデータ」２２４によって表わされている。
【０１２０】
ブロック８１２で、整列／融合モジュール２１８が、前述したとおり、いくつかの整列基準に従って選択されたサブショットをサブ音楽と整列させる。ブロック８１４で、整列／融合モジュールが、整列されたサブショットをサブ音楽と融合して自動編集されたビデオ２２０を生成する。
【０１２１】
結論
前述したシステムおよび方法は、入力音楽に関連して入力ビデオデータシーケンスを自動的に編集する。このシステムおよび方法を構造上の特徴および方法上の動作に特有の言葉遣いで説明してきたが、頭記の特許請求の範囲で定義する主題は、説明した特定の特徴および動作に必ずしも限定されない。むしろ、特定の特徴および動作は、請求の主題を実施する例示的な形態として開示している。
【図面の簡単な説明】
【０１２２】
【図１】音楽に関連してビデオデータを自動的に編集するシステムおよび方法を実施することが可能な例示的なコンピューティング環境を示すブロック図である。
【図２】図１のコンピューティング環境において特定された、音楽に関連してビデオデータを自動的に編集するコンピュータプログラムアプリケーションを表わす例示的なアプリケーションプログラム、および自動ビデオ編集プロセス中にその例示的なアプリケーションプログラムによって操作され、生成されるデータを表わす例示的なプログラムデータのさらなる態様を示すブロック図である。
【図３】例えば、サブショット境界を含む入力ビデオデータシーケンスの構造上の態様を検出するのに使用される抽出されたビデオメタデータ（フレーム差分）を表わす例示的なフレーム差分曲線（ＦＤＣ）を示す表の図である。
【図４】シーケンスセグメント化操作の結果を表わす例示的な速度検出データ曲線を示す表の図である。
【図５】入力音楽ファイルからの音楽クリップ、つまり「サブ音楽（ｓｕｂｍｕｓｉｃ）」に関して強いビートおよび強いムードを検出するのに使用される例示的な抽出された音楽メタデータを示す表の図である。
【図６】特に、入力ビデオシーケンスから抽出されたメタデータ（ビデオおよび音声）、および入力音楽ファイルから抽出された音楽メタデータ（音楽クリップ、つまり「サブ音楽」）に関して示した音楽データシーケンス、ビデオデータシーケンス、および音声データシーケンスの例示的な態様を示す表の図である。
【図７】特に、色エントロピー、動きの激しさ、および計算されたサブショット重要度データ値を互いとの関係で示した抽出されたビデオメタデータに関する例示的な値を示す表の図である。
【図８】独立の音楽源に関連してビデオを自動的に編集する例示的な手続き８００を示す流れ図である。
【符号の説明】
【０１２３】
１３４  システムメモリ
１６０  アプリケーションプログラム
１６４  プログラムデータ
２０２  ビデオ編集モジュール
２０４  ビデオデータシーケンス
２０６  音楽
２０８  メタデータ抽出モジュール
２１０  シーン、ショット、サブショット
２１２  抽出されたビデオメタデータ
２１４  抽出された音楽の特徴
２１６  コンテンツ選択モジュール
２１８  整列−融合モジュール
２２０  自動編集されたビデオ
２２２  入力ビデオデータの要約
２２４  データ
２２６  他のモジュール
（付録−参照文献）
［１］D. Zhang、W. Qi、H. J. Zhang、「新しいショット検出アルゴリズム」、マルチメディアに関する第２回ＩＥＥＥ環太平洋地域会議（2nd IEEE Pacific-Rim Conf on Multimedia）（PCM2001）、63〜70ページ、中国、北京、2001年10月
［２］T. Lin、H. J. Zhang、「力競争によるビデオシーン抽出」、マルチメディアに関するＩＥＥＥ国際会議および展示会（IEEE Intl Conf on Multimedia and Expo）（ICME001）日本、東京、早稲田大学、2001年8月22〜25日
［３］L. Lu、H. Jiang、H. J. Zhang、「堅牢な音声分類およびセグメント化の方法」、第９回マルチメディア（9th ACM Multimedia）、203〜211ページ、2001年
［４］Eric D. Scheirer、「音響音楽信号のテンポおよびビートの解析」、米国音響学会ジャーナル（Journal of Acoustical Society of America）、103 (1):588〜601ページ、1998年
【図１】
2004159331.tif 000033
【図２】
2004159331.tif 000034
【図３】
2004159331.tif 000035
【図４】
2004159331.tif 000036
【図５】
2004159331.tif 000037
【図６】
2004159331.tif 000038
【図７】
2004159331.tif 000039
【図８】
2004159331.tif 000040