(57)【特許請求の範囲】
【請求項１】
マルチメディアの最適要約を自動作成する方法であって、
（ａ）パラメータ化メディア信号生成手段が、一連のマルチメディア・ソースをパラメータ化してパラメータ化メディア信号を生成するステップであって、該ステップは、
前記マルチメディア・ソースを複数のウィンドウに分割するステップと、
各ウィンドウにパラメータ化を適用して、各ウィンドウを表現する特徴ベクトルを生成するステップと、
前記特徴ベクトルを前記複数のウィンドウの順に配列してパラメータ化メディア信号を生成するステップであって、前記パラメータ化メディア信号は開始部分から終了部分までの各部分を有し、各部分は前記複数のウィンドウ各々に相当する、前記パラメータ化メディア信号を生成するステップと、
を有する、前記パラメータ化メディア信号を生成するステップと、
（ｂ）類似度配列作成手段が、ｎ次正方マトリクスからなる類似度配列を作成するステップであって、各マトリクス要素が、前記マトリクス要素の行に関連する前記パラメータ化メディア信号の第１部分に相当する第１特徴ベクトルと、前記マトリクス要素の列に関連する前記パラメータ化メディア信号の第２部分に相当する第２特徴ベクトルと、の間の類似度測定値を含み、前記マトリクス要素の１行からｎ行までの各行に関連する前記第１部分は前記パラメータ化メディア信号の前記開始部分から前記終了部分までの各部分に相当し、前記マトリクス要素の１列からｎ列までの各列に関連する前記第２部分は前記開始部分から前記終了部分までの各部分に相当する、前記類似度配列を作成するステップと、
（ｃ）最適セグメント発見手段が、前記類似度配列を使用して最適セグメントを見つけるステップであって、前記ｎ次正方マトリクスの一部であって各要素の類似度測定値の平均値が最大であるｍ次正方マトリクスを特定するステップを含み、前記最適セグメントは、前記パラメータ化メディア信号の一部であって開始位置部分から終了位置部分までの長さを有するセグメントであり、前記ｍ次正方マトリクスの１行１列目の要素に関連する前記第１部分及び前記第２部分が前記開始位置部分に相当し、前記ｍ次正方マトリクスのｍ行ｍ列目の要素に関連する前記第１部分及び前記第２部分が前記終了位置部分に相当する、前記最適セグメントを見つけるステップと、
（ｄ）最適要約選択手段が、前記マルチメディア・ソースの一部を最適要約として選択するステップであって、前記マルチメディア・ソースの前記一部が前記最適セグメントに相当する、前記選択するステップと、
を含む方法。
【請求項２】
前記マルチメデイア・ソースがオーディオ・ファイル又はビデオ・ファイルの場合、前記ウィンドウの前記パラメータ化が周波数領域変換を含む、請求項１に記載の方法。
【請求項３】
前記マルチメデイア・ソースがテキスト・ファイルの場合、前記パラメータ化が前記ウィンドウのステミング、ストップ・リスト・フィルタリング、及びトークン化処理を含む、請求項１に記載の方法。
【請求項４】
前記特徴ベクトルに対してウィンドウ内のトークン頻度及び逆ドキュメント頻度を使用した重みを適用して前記類似度測定値を算出することを含む、請求項３に記載の方法。
【請求項５】
前記類似度測定値がパラメータ空間内の特徴ベクトル間のユークリッド距離を含む、請求項１に記載の方法。
【請求項６】
前記類似度測定値が特徴ベクトルのスカラー（ドット）積を含む、請求項１に記載の方法。
【請求項７】
前記類似度測定値が特徴ベクトル間の角度のコサインを含む、請求項１に記載の方法。
【請求項８】
前記パラメータ化メディア信号の少なくとも一部を強調する重み関数を適用して前記類似度測定値の平均値を算出することを含む、請求項１に記載の方法。
【請求項９】
ステップ（ｃ）が、前記最適セグメントの前記長さが予め定められ、前記開始位置を求めるステップを含む、請求項１に記載の方法。
【請求項１０】
ステップ（ｃ）が、前記最適セグメントの前記開始位置が予め定められ、前記最適セグメントの前記長さを求めるステップを含む、請求項１に記載の方法。
【請求項１１】
ステップ（ｃ）が、前記最適セグメントの前記開始位置及び前記長さを求めるステップを含む、請求項１に記載の方法。
【請求項１２】
さらに、
（ｅ）変更類似度配列作成手段が、前記類似度配列から前記最適化セグメントを削除し、変更された類似度配列を作成するステップと、
（ｆ）第２最適要約作成手段が、前記変更された類似度配列を使用して前記ステップ（ｂ）、（ｃ）、および（ｄ）を繰り返し、前記マルチメディア・ソースの第２最適要約を作成するステップと、
を含む、請求項１に記載の方法。
【請求項１３】
コンピュータを、
一連のマルチメディア・ソースをパラメータ化してパラメータ化メディア信号を生成するパラメータ化メディア信号生成手段であって、前記マルチメディア・ソースを複数のウィンドウに分割し、各ウィンドウにパラメータ化を適用して、各ウィンドウを表現する特徴ベクトルを生成し、前記特徴ベクトルを前記複数のウィンドウの順に配列してパラメータ化メディア信号を生成し、前記パラメータ化メディア信号は開始部分から終了部分までの各部分を有し、各部分は前記複数のウィンドウ各々に相当する、前記パラメータ化メディア信号生成手段と、
ｎ次正方マトリクスからなる類似度配列を作成する類似度配列作成手段であって、各マトリクス要素が、前記マトリクス要素の行に関連する前記パラメータ化メディア信号の第１部分に相当する第１特徴ベクトルと、前記マトリクス要素の列に関連する前記パラメータ化メディア信号の第２部分に相当する第２特徴ベクトルと、の間の類似度測定値を含み、前記マトリクス要素の１行からｎ行までの各行に関連する前記第１部分は前記パラメータ化メディア信号の前記開始部分から前記終了部分までの各部分に相当し、前記マトリクス要素の１列からｎ列までの各列に関連する前記第２部分は前記開始部分から前記終了部分までの各部分に相当する、前記類似度配列作成手段と、
前記類似度配列を使用して最適セグメントを見つける最適セグメント発見手段あって、前記ｎ次正方マトリクスの一部であって各要素の類似度測定値の平均値が最大であるｍ次正方マトリクスを特定するステップを含み、前記最適セグメントは、前記パラメータ化メディア信号の一部であって開始位置部分から終了位置部分までの長さを有するセグメントであり、前記ｍ次正方マトリクスの１行１列目の要素に関連する前記第１部分及び前記第２部分が前記開始位置部分に相当し、前記ｍ次正方マトリクスのｍ行ｍ列目の要素に関連する前記第１部分及び前記第２部分が前記終了位置部分に相当する、前記最適セグメント発見手段と、
前記マルチメディア・ソースの一部を最適要約として選択するステップであって、前記マルチメディア・ソースの前記一部が前記最適セグメントに相当する、前記最適要約選択手段選と、
として機能させるためのマルチメディア最適要約自動作成プログラム。
【請求項１４】
請求項１３に記載のプログラムを記録したコンピュータ読取可能記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は線形メディアの最適要約または抜粋を自動的に作成する方法に関する。
【０００２】
【従来の技術】
マルチメディア情報を使用する多くのアプリケーションが存在する。しかし、ユーザーおよびアプリケーションがマルチメディア情報を効果的に扱い、処理することは、マルチメディア情報の性質に起因して面倒である。マルチメディア情報はディジタル・データ・ファイルに格納されることが多い。これらファイルは大容量の格納を必要とし、アプリケーションによるマルチメディア情報処理の計算機上の費用を高くする。ディジタル・データ・ファイルがネットワーク上に格納される場合、アプリケーションによるディジタル・データ・ファイルへのアクセスにとって、ネットワーク帯域幅の制限が障害となる。
【０００３】
マルチメディア情報によりアプリケーションに生じる困難性に加えて、ユーザーはまた、マルチメディア情報処理の難しさに直面する。映画や音楽のようなマルチメディア情報は時間依存メディアである。マルチメディア情報は時間依存であるため、ユーザーが作品全体を調べることは、多くの場合実際的ではない。例えば、映画サーチ・エンジンが多くの結果を元に戻す場合、その各々は９０分またはそれ以上継続するので、ユーザーは各結果を詳細に調べる時間を持てない。別の例では、音楽の電子商取引ウェブサイトが、潜在的な購入者に音楽を聴けるよう提供することがある。ユーザーが音楽全体を聴かないと、その音楽を気に入るかどうか決められないのは煩わしいことである。さらに、ユーザーに完全な長さの音楽へのアクセスを提供するので、ウェブサイト・オペレータは基本的にその商品を無償で与えていることになり、音楽の購入意欲をユーザーから喪失させていた。
【０００４】
実際のアプリケーションそれぞれに、マルチメディアの要約があることが望まれる。要約の一型式は、マルチメディア情報の抜粋セグメントである。効果的な要約であるためには、セグメントがその作品全体を正しく代表することが非常に望ましい。不都合な点は、既存のアルゴリズムで要約を作成すると、作成された要約が長いマルチメディア情報の代表となることはほとんど保証されないことである。
【０００５】
要約を作成する従来の方法の１つは、マルチメディア情報の特定の時間セグメントを常に選択して、要約を作成する。例えば、この方法は常に、オーディオ・トラックの最初の３０秒を要約として選択する。この雑な方法の結果は、例えば、オーディオ・トラックの大部分が固有の導入部にほとんど類似度を持たない場合、全く満足できないものになる。
【０００６】
自動要約化の別の方法は、特定型式のマルチメディア情報に対して特別に調整する必要がある。ビデオ要約化には、ビデオをセグメントに分割し、そのセグメントを類似度に従って相互にクラスタにまとめる。各クラスタの中心に最も近いセグメント・クラスタを、クラスタ全体の代表セグメントとして選択する。別のビデオ要約方法は、ビデオに付随する字幕の分析から一般的に引き出される発見法を使用してビデオを要約することを試みる。これら方法はビデオのセグメント化に頼るか、あるいはクラスタ化または連結化のどちらかを必要とする。
【０００７】
オーディオ要約方法は一般に、セグメント化フェーズを利用して、オーディオをセグメントに分割する。一般にこれは、無音またはピッチのようなオーディオの特徴箇所を探してなされる。次に、各種の基準に基づいて代表セグメントを選択する。特定マルチメディア・ソースのこれら特徴箇所が存在しない場合、これら方法はほとんど機能できない。
【０００８】
テキスト要約は一般に、期間−頻度／逆ドキュメント頻度を利用して、ドキュメントを代表し、かつ他のドキュメントとはかなり違うパラグラフ、センテンス、またはキー・フレーズを選択する。これは、他のドキュメントの内容に関する知識を必要とする。
【０００９】
１）あらゆる型式のマルチメディア情報に対処でき、２）作品全体を正しく表す代表を作成し、３）マルチメディア情報の特定の特徴によらず、４）セグメント化、クラスタ化または連結化を必要としないような、自動要約を作成する方法があることが望ましい。さらに、所望の長さの要約を容易に作成できる方法があることは有利である。
【００１０】
【非特許文献１】
ZHANG, H. J., LOW, C. Y., SMOLIAR, S., WU, J. H., 「ビデオの解析、検索および走査：総合的かつ内容を基礎とする解法(Video Parsing, Retrieval and Browsing: and Integrated and Content-Based Solution)」, in MAYBURY, M. ed., Intelligent Multimedia Information Retrieval, AAAI Press/MIT Press, 1997
【非特許文献２】
MOHAN, R., 「ビデオ・シーケンス一致(Video Sequence Matching)」, Proc. of the International Conference on Acoustics, Speech, and Signal Processing '98, Seatle, WA, IEEE, 1998
【非特許文献３】
FOOTE, J., 「オーディオ・ノベルティの測定を用いた自動オーディオ分割(Automatic Audio Segmentation Using a Measure of Audio Novelty)」, Proc. IEEE International Conference on Multimedia and Expo (ICME) 2000, vol. I, pp. 452-455, New York, NY, August 2000
【００１１】
【発明が解決しようとする課題】
本発明によれば、一般に、線形メディア・ソースの最適要約を自動作成する方法は、第１ステップとして線形メディア・ソースをパラメータ化して、パラメータ化メディア信号を生成する。パラメータ化メディア信号を使用して、類似度配列を作成する。各配列要素は、パラメータ化メディア信号の２つの部分間の類似度測定の値を含む。セグメント一致関数は、パラメータ化メディア信号のあらゆる可能なセグメントに対しても計算でき、セグメントとパラメータ化メディア信号全体との間の代表類似度を測定する。セグメント一致関数を最適化して、最適セグメント化を見つける。セグメント一致関数を最適化するセグメントは、最良の代表セグメントであり、最適セグメント位置の相当する線形メディア・ソースのその部分が最適要約として選択される。
【００１２】
【課題を解決するための手段】
本願請求項１に記載の発明は、線形メディアの最適要約を自動作成する方法であって、（ａ）線形メディア・ソースをパラメータ化してパラメータ化メディア信号を生成するステップと、（ｂ）複数の配列要素で構成される類似度配列を作成するステップであり、各配列要素が、該パラメータ化メディア信号の第１部分と、該パラメータ化メディア信号の第２部分と、の間の類似度測定値を含む、ステップと、（ｃ）該類似度配列全体に渡ってセグメント一致関数を最適化して、最適セグメントを見つけるステップであり、該セグメント一致関数が、該パラメータ化メディア信号のセグメントと全体パラメータ化メディア信号との間の類似度を測定するのに使用され、かつ少なくともセグメントの位置の数学的関数である、ステップと、（ｄ）線形メディア・ソースの一部を最適要約として選択するステップであり、線形メディア・ソースの該一部が該最適セグメントに相当する、ステップと、を含む方法である。
【００１３】
請求項２に記載の発明は、請求項１のステップ（ａ）が、線形メディア・ソースをメディア・フレームのセットに分解するステップと、各メディア・フレームにパラメータ化を適用して、各メディア・フレームを表現する特徴ベクトルを生成するステップと、該特徴ベクトルを総計して、パラメータ化メディア信号を生成するステップと、を含む方法である。
【００１４】
請求項３に記載の発明は、請求項２に記載の方法において、メディア・フレームの該パラメータ化が周波数領域変換を含む方法である。
【００１５】
請求項４に記載の発明は、請求項２に記載の方法において、該パラメータ化が該メディア・フレームの一部分にトークン値を割り当てることを含む方法である。
【００１６】
請求項５に記載の発明は、請求項１のステップ（ａ）が、各メディア・フレームがパラメータ化線形メディア情報を備える、複数のメディア・フレームに分割される線形メディア・ソースを含む線形メディア・データを読み取るステップと、各フレームに含まれるパラメータ化線形メディア情報から、各メディア・フレームの特徴ベクトルを生成するステップと、該特徴ベクトルを総計して、パラメータ化メディア信号を生成するステップと、を含む方法である。
【００１７】
請求項６に記載の発明は、請求項１に記載の方法における類似度測定値が、パラメータ化メディア信号の該第１部分に相当する第１特徴ベクトルと、パラメータ化メディア信号の該第２部分に相当する第２特徴ベクトルと、の間のベクトル類似度の測定値を含む方法である。
【００１８】
請求項７に記載の発明は、請求項６に記載の方法におけるベクトル類似度の該測定値が、パラメータ空間内の特徴ベクトル間のユークリッド距離を含む方法である。
【００１９】
請求項８に記載の発明は、請求項６に記載の方法におけるベクトル類似度の該測定値が、特徴ベクトルのスカラー（ドット）積を含む方法である。
【００２０】
請求項９に記載の発明は、請求項６に記載の方法におけるベクトル類似度の該測定値が、特徴ベクトル間の角度のコサインを含む方法である。
【００２１】
請求項１０に記載の発明は、請求項６に記載の方法におけるベクトル類似度の該測定値が、特徴ベクトルに対し期間−頻度／逆ドキュメント頻度重みを適用することを含む方法である。
【００２２】
請求項１１に記載の発明は、請求項１に記載の方法における類似度測定値が、パラメータ化メディア信号の該第１部分に相当する第１の複数の特徴ベクトルと、パラメータ化メディア信号の該第２部分に相当する第２の複数の特徴ベクトルと、のベクトル相関を含む方法である。
【００２３】
請求項１２に記載の発明は、請求項１に記載の方法における類似度配列が、該パラメータ化メディア信号の一部に相当する該マトリクスの各行および各列を有する２次元マトリクスであり、それにより、各マトリクス要素が、該マトリクス要素の行に関連するパラメータ化メディア信号の該部分に相当する第１特徴ベクトルと、該マトリクス要素の列に関連するパラメータ化メディア信号の該部分に相当する第２特徴ベクトルと、の間の類似度測定値の値を含む方法である。
【００２４】
請求項１３に記載の発明は、請求項１に記載の方法におけるセグメント一致関数が該類似度配列の一部の平均類似度測定値を含み、類似度配列の該部分が、対象セグメントと全体パラメータ化メディア信号との間の複数の類似度測定値を含む方法である。
【００２５】
請求項１４に記載の発明は、請求項１３に記載の方法におけるセグメント一致関数が、線形メディア・ソースの所望の部分に相当するパラメータ化メディア信号の少なくとも一部に対する類似度測定値を強調する重み関数を含む方法である。
【００２６】
請求項１５に記載の発明は、請求項１に記載のステップ（ｃ）が、１次元最適化を使用してセグメント一致関数の値を最適化し、所定の長さのセグメントの最適位置を求めるステップを含む方法である。
【００２７】
請求項１６に記載の発明は、請求項１に記載のステップ（ｃ）が、１次元最適化を使用してセグメント一致関数の値を最適化し、所定の位置のセグメントに対する最適セグメント長さを求めるステップを含む方法である。
【００２８】
請求項１７に記載の発明は、請求項１に記載のステップ（ｃ）が、２次元最適化を使用してセグメント一致関数の値を最適化し、最適セグメント位置および最適セグメント長さを求めるステップを含む方法である。
【００２９】
請求項１８に記載の発明は、請求項１に記載のステップ（ｃ）が、さらに、（ｅ）類似度配列から該最適化セグメントを削除し、変更された類似度配列を作成するステップと、（ｆ）該変更された類似度配列を持つステップ（ｂ）、（ｃ）、および（ｄ）を繰り返し、線形メディア・ソースの第２最適要約を作成するステップとを含む方法である。
【００３０】
請求項１９に記載の発明は、情報を格納する情報格納メディアを備える製品であって、該情報が、処理デバイス上で動作するのに使用されるプロセッサ読み取り可能な命令のグループを含み、そのプロセッサ読み取り可能命令のグループが、請求項１の方法に従って処理デバイスを動作させる製品である。
【００３１】
請求項２０に記載の発明は、コンピュータによって実行可能なプログラムであり、次のことを含む。すなわち、線形メディア・ソースをパラメータ化してパラメータ化メディア信号を生成することを含み、複数の配列要素で構成される類似度配列を作成することであって、各配列要素が、該パラメータ化メディア信号の第１部分と、該パラメータ化メディア信号の第２部分と、の間の類似度測定値を含む、該類似度配列を作成することを含み、該類似度配列全体に渡ってセグメント一致関数を最適化して、最適セグメントを見つけることであって、該セグメント一致関数が、該パラメータ化メディア信号のセグメントと全体パラメータ化メディア信号との間の類似度を測定するのに使用され、かつ少なくともセグメントの位置の数学的関数である、該最適セグメントを見つけることを含み、線形メディア・ソースの一部が最適セグメントに相当するという線形メディア・ソースの該一部を最適要約として選択することと、を含むプログラムである。
【００３２】
１つの実施形態では、線形メディア・ソースは、線形メディア・ソースをメディア・フレームのセットに分解することにより、パラメータ化される。パラメータ化を各メディアに適用して、特徴ベクトルを生成する。各メディア・フレームの特徴ベクトルを総計して、パラメータ化メディア信号を生成する。パラメータ化の例は周波数ドメイン変換およびトークン化を含む。代替実施形態では、線形メディア・ソースは、パラメータ化形態の線形メディア・データ・ファイルから抽出される。
【００３３】
１つの実施形態では、類似度配列は２次元マトリクス（行列）を含む。各行および各列はパラメータ化メディア信号の１つの部分に相当する。各マトリクス要素はマトリクス要素の行に関連する特徴ベクトルと、マトリクス要素の列に関連する特徴ベクトルとの間の類似度測定の値を含む。
【００３４】
使用される類似度測定のタイプの例は、例えば特徴ベクトル間のユークリッド距離またはスカラー（ドット）積のようなベクトル類似度測定を含む。類似度測定はまた、特徴ベクトルの２つのグループ間のベクトル相関を利用できる。類似度測定は重み付けできる。重みの１つの例は、期間−頻度／逆ドキュメント頻度重みである。
【００３５】
１つの実施形態では、セグメント類似度関数は、対象のセグメントと全体のパラメータ化メディア信号との平均類似度測定である。別の実施形態では、セグメント類似度関数は重み関数を用いてさらに重み付けされ、線形メディア・ソースの所望部分の類似度測定値を強調する。
【００３６】
１つの実施形態では、予め決めた長さの最適セグメントのセグメント類似度関数は、１次元最適化を使用して最適化される。最適セグメントの長さが予め決められない場合、セグメント類似度関数を最適化して、最適セグメント位置と長さを見つける。
【００３７】
別の実施形態では、類似度配列から最適セグメントを削除し、変更された類似度配列にその方法を繰り返して、第２の最適要約を見つける。
【００３８】
本発明の１つの実施形態は、例えばビデオ、オーディオ、またはテキスト情報のような、あらゆるタイプの線形メディア・ソースに対処可能である。線形メディア・ソースには、ビデオ、オーディオ、テキスト情報が含まれる。
【００３９】
【発明の実施の形態】
本発明を、図面を参照して説明する。
【００４０】
本発明はマルチメディア情報の要約を作成する他の方法に伴う問題を解決するものである。詳細には、本発明はすべての型式の線形メディアの要約または抜粋を自動的に作成する。線形メディアとは、マルチメディア情報が１次元変数の関数であるマルチメディアである。線形メディアの例には、オーディオ（音、audio）およびビデオ（画像、video）を含み、その場合マルチメディア情報は時間の関数およびテキストドキュメントとして表される。ここで、テキストドキュメントとは、マルチメディア情報がドキュメント位置の離散関数である。
【００４１】
本発明により作成される要約は作品全体を正しく代表する。要約が作品全体を正しく代表しているかどうかを決定する１つの方法は、要約と作品全体の自己類似度の度合いを測定することである。類似度の既知の定義では、最適要約は、そのセグメントと作品全体との間の自己類似度を最大化するセグメントと定義される。最適要約は、最適要約のどの微小部分も、他のどの要約から取られた微小部分に比べてもその作品全体中の微小部分に類似すると見込まれる、確率的解釈である。本発明の実施形態は、セグメントのサポート全体に渡る自己類似度マトリクスの和を最大化することにより、マルチメディア情報全体の最適要約を作成する。
【００４２】
さらに、本発明はマルチメディア情報の特定の特徴に依存しない。１つの実施形態では、本発明はマルチメディア情報の意味内容に左右されずに要約を作成する。これにより、本発明をセグメント化、クラスタ化または連結化を必要とせずに操作できる。
【００４３】
さらに本発明は、各点毎の（point-to-point）類似度の特定の判断基準を計算可能な、任意の時間依存または線形データの最適要約を決定可能である。本発明は多数の異なる有用なアプリケーションに採用可能であり、そのいくつかの例を以下に述べる。
【００４４】
本発明は、作品全体の特徴を最も良く表わす短いセグメントを見出して、オーディオ、ビデオ、またはテキストを要約可能である。アプリケーションの１例では、これにより、潜在的な顧客が購入の前に、大型メディア・ソースの無料サンプルをプレビューすることができる。最適要約により、顧客を購入に至らしめるような販売者の能力が向上する。
【００４５】
アプリケーションの別の例は、メディア分類、索引付け、検索に対して代表要約を使用するためである。大規模なメディア作品に対しては、分類・索引付け・検索は費用のかかる処理である。本発明を使用して、分類・索引付け・検索処理の代わりに、大規模な作品の短くて最適な要約を作成することは、全体コストを低減させる。要約が大規模作品を正しく代表するということは、パフォーマンスを犠牲にせずに、最適要約化を実施可能とする。
【００４６】
ビデオ編集は別のアプリケーションの例である。ビデオ・ソースは個別のショットに分割して編集される。本発明を使用して、各ショットの長さを一定の長さにまで短縮可能である。これは、各ショットの所望の長さの代表要約を作成することによりなされる。各ショットの代表要約を連結して、時間では短縮されているが、全ショットおよびそれらの相対的な長さを維持しているビデオを作成可能である。この方法は他の型式のマルチメディア情報にも同様に適用できる。
【００４７】
別のアプリケーションの例では、本発明を利用して、ビデオ・ショット、またはビデオ全体の最良の代表キーフレームを見つける。これはビデオの１フレーム長さの最適要約を作成することによりなされる。最適キーフレームは多数のアプリケーションに有用である。それらアプリケーションには、例えばキーフレームまたは漫画的代表図を使用してビデオを要約するか、あるいはキーフレームをアイコンとして使用してグラフィック・ビデオ編集アプリケーションにおいてショットを代表するような、ことが含まれる。
【００４８】
図１は、ダイアグラム１００に本発明の方法の１つの実施形態を示す。第１ステップ１２０では、マルチメディア・ソースはパラメータ化マルチメディア信号に変換される。パラメータ化マルチメディア信号は、コンパクトな特徴ベクトルのセットを含む。各特徴ベクトルはマルチメディア・ソースの一部分を表わす。一般に、各特長ベクトルのサイズは、マルチメディア・ソースの対応する部分に比べて小さく、その結果、本発明の方法での処理が容易になる。パラメータ化のタイプは、提供されるマルチメディア情報のタイプに依存する。理論的には、パラメータ化のタイプは、マルチメディア・ソースの類似部分が類似特徴ベクトルを持つように選択する必要がある。
【００４９】
音楽またはオーディオ情報に対しては、１つの実施形態のマルチメディア・ソースはディジタル・オーディオ・ファイルである。ディジタル・オーディオの共通フォーマットはＭＰＥＧ−１、レイヤ３（ＭＰ３）フォーマットである。本発明に、他のディジタル・オーディオ・フォーマットを適応させるのは容易であろう。代替実施形態では、音楽またはオーディオをアナログ・オーディオ信号で本発明の方法に入力し、ディジタル・オーディオ・ファイルに変換可能である。この実施形態では、ブロック１２０はハードウェアおよび／またはソフトウェアを備え、それらにより、アナログ・オーディオ信号をディジタル・オーディオ信号に変換し、かつそのディジタル・オーディオ・データを格納する。いずれの実施形態においても、ディジタル・オーディオ・ファイルは、ローカルのディジタル情報格納メディアに格納するか、または代わりに、ローカルまたはワイド・エリア・コンピュータ・ネットワークを介してアクセスできる遠隔のディジタル情報格納メディアに格納してもよい。別の実施形態では、ステレオまたはマルチチャネル・オーディオ情報を平均して、パラメータ化の前に単一チャネルを形成してもよい。
【００５０】
１つの実施形態では、オーディオ・マルチメディア・ソースは、最初に、オーディオ・波形を分割または「ウィンドウ生成」して、別個の部分またはフレームにすることでパラメータ化される。可変フレーム幅および重ね合わせを使用して、結果を最適化可能である。１つの実施形態では、ディジタル・オーディオ・ソースは、各々Ｎ個のオーディオ・サンプルのフレーム内にウィンドウ表示される。各フレームはＮ／２サンプルだけ前のフレームおよび後ろのフレームと重なる。
【００５１】
例として、Ｎの値は２５６、Ｎ／２の値は１２８にできる。１６ｋＨｚでサンプリングされたオーディオでは、この結果、１６ミリ秒のフレーム継続時間、および１２５フレーム／秒のフレーム・レートになる。各フレームは、短期間フーリエ変換（ＳＴＦＴ）またはメル周波数ケプストラル係数（ＭＦＣＣ）分析などの標準オーディオ分析法を使用してパラメータ化される。
【００５２】
オーディオ・フレームに変換を適用すると、一般には、多数の変換係数が発生する。１つの実施形態では、オーディオは一般に、スペルトルまたはＭＦＣＣ形態を利用してパラメータ化される。スペクトル形態は各ウィンドウのフーリエ変換の対数振幅である。これらは１０〜１００の線形周波数ビン全体で平均化され、オーディオ・ウィンドウ当たり１０〜１００パラメータの特性ベクトルを生成する。ＭＦＣＣ形態は、各ウィンドウのフーリエ変換の対数振幅となり、それらを非線形メル−スケール周波数ビン全体に渡り平均化する。次に離散コサイン変換（ＤＣＴ）を利用して、平均振幅値を変換する。高次のＤＣＴ係数は削除され、オーディオ・ウィンドウ当たり８〜１２パラメータの特徴ベクトルが残る。ＭＦＣＣパラメータ化はスペクトル形態より小さい相関を有するが、フレームのオーディオ情報のこれら表現のいずれも、本発明の方法に適する。なぜなら、類似フレームは類似変換係数、したがって類似特徴ベクトルを有するからである。
【００５３】
パラメータ化に利用できる代替のオーディオ分析方法は、線形予測方法またはスペクトログラム分析と組み合わせた音響心理学上の検討を含む。ＭＰＥＧ−１、レイヤ３のような多くのオーディオ圧縮方法が、前述の例と類似の方法でオーディオ情報を提供する。オーディオ表現を使用して、オーディオ圧縮方法でも使用する特徴ベクトルを生成することにより、この実施形態は、圧縮されたオーディオ・データ・ソースからパラメータ化された特徴ベクトルを直接生成する。この実施形態により、費用のかかるオーディオ復元および圧縮されたオーディオ・フォーマットの処理に一般に関連する復号化を回避できる。
【００５４】
ビデオ情報に対しては、１つの実施形態におけるマルチメディア・ソースは、ビデオ・データ・ファイルである。ディジタル・ビデオの１つの標準フォーマットはＤＶビデオ・フォーマットである。本発明には、他のディジタル・ビデオ・フォーマットを容易に適合できよう。ビデオ・ファイルは、ローカルのディジタル情報格納メディアに格納してもよく、または代わりに、ローカルまたはワイド・エリア・コンピュータ・ネットワークを介してアクセス可能な遠隔のディジタル情報格納メディアに格納してもよい。
【００５５】
代替の実施形態では、ブロック１２０において本発明の方法にアナログ・ビデオ信号が入力されることがある。この実施形態では、ブロック１２０はハードウェアおよび／またはソフトウェアを備え、それらにより、アナログ・ビデオ信号をディジタル・ビデオ信号に変換し、かつそのディジタル・ビデオ・データを格納する。ビデオはアナログ・ビデオ信号として本発明の方法に入力して、ディジタル・ビデオ・データ・ファイルに変換してもよい。ディジタル・ビデオ・ファイルは、ローカルのディジタル情報格納メディアに格納するか、または代わりに、ローカルまたはワイド・エリア・コンピュータ・ネットワークを介してアクセス可能な遠隔のディジタル情報格納メディアに格納してもよい。
【００５６】
１つの実施形態では、ビデオ・マルチメディア・ソースは、離散コサイン変換（ＤＣＴ）またはアダマール変換（ＨＴ）のような正規直交投影を利用してパラメータ化される。この変換は、一度に全体画像に適用してもよく、また代わりに、画像をサブブロックに分割して、各サブブロックに個々に適用されてもよい。
【００５７】
画像に変換を適用することにより、一般に多数の変換係数が生成される。１つの実施形態では、切捨て、主要成分分析、または線形識別分析により変換成分の数を減少させる。変換係数の数を減少させる場合には、オリジナル・ソースの最適復元と対照的に、データ圧縮アプリケーションでなされたのと同様に、特徴ベクトルの最適分析に対する成分を選択することが望ましい。本発明の１つの実施形態では、最大分散変換成分以外のすべての成分は削除され、結果的に、各ビデオ・フレームの１０〜３０パラメータのコンパクトな特徴ベクトルを生成する。フレームのオーディオ情報のこの表現は、発明の方法に適する。なぜなら、類似フレームは類似変換係数、したがって類似特徴ベクトルを有するからである。
【００５８】
代替のパラメータ化方法を使用して、パラメータ化ビデオ信号の特徴ベクトルを生成できる。一例にはZhangらの「ビデオの解析、検索および走査：総合的かつ内容を基礎とした解法（ZHANG, H.J., LOW, C.Y., SMOLIAR, S., WU, J.H., "Video Parsing, Retrieval, and Browsing: and Integrated and Content-Based Solution", in M. Maybury ed., Intelligent Multimedia Information Retrieval, AAAI Press/MIT Press, 1997）」に記載の、カラー・ヒストグラム分析がある。大幅に削減された画像の輝度の圧縮マクロブロックまたは順序のＤＣ係数から導き出される削減された画像は、Mohanの「ビデオ・シーケンス一致（MOHAN, R., "Video Sequence Matching", Proc. of the International Conference on Acoustics, Speech, and Signal Processing '98, Seatle, WA, IEEE, 1998）」に記載のような場合がある。上記に参照の刊行物両方が、本明細書に組み入れられる。
【００５９】
またテキスト情報もマルチメディア・ソースとして使用してよい。１つの実施形態では、テキスト情報はテキスト・データ・ファイルに格納される。テキスト・データの１つの標準フォーマットはＡＳＣＩＩデータ・フォーマットである。例えばワードプロセッサ、電子出版またはドキュメント管理システム、あるいはＷＥＢブラウザに関連して使用されているデータ・フォーマットのような、テキスト・データを含む他のデータ・フォーマットは、本発明に容易に適合できよう。テキスト情報ファイルは、ローカルのディジタル情報格納メディアに格納してもよく、または代わりに、ローカルまたはワイド・エリア・コンピュータ・ネットワークを介してアクセス可能な遠隔ディジタル情報格納メディアに格納してもよい。
【００６０】
代替実施形態では、テキスト情報信号を、ブロック１２０において、本発明の方法に入力できる。この実施形態では、ブロック１２０はハードウェアおよび／またはソフトウェアを備え、それらにより、テキスト情報信号を処理してテキスト情報に変換し、かつそのテキスト情報をテキスト情報ファイルとして格納する。テキスト情報信号の例には、テキストまたは文字入力、手書き入力、または音声入力を含む。テキスト情報ファイルはローカル・ディジタル情報格納メディアに格納してもよい。また代わりに、ローカルまたはワイド・エリア・コンピュータ・ネットワークを介してアクセス可能な遠隔ディジタル情報格納メディアに格納してもよい。
【００６１】
１つの実施形態では、テキスト情報は、ステミング、ストップ・リスト・フィルタリング、およびトークン化処理によりパラメータ化される。ステミングは各単語の異なる語形変化を削除して、その単語をルートワード（root word, 語根）に減少させる。例えば、単語「ｒｅｍｏｖｅ」、「ｒｅｍｏｖｅｄ」、「ｒｅｍｏｖｉｎｇ」および「ｒｅｍｏｖａｌ」はすべて、ルートワードの「ｒｅｍｏｖ」に減少する。ステミング（stemming, 語幹処理）はテキスト情報の各単語について実行される。
【００６２】
当業者には公知のステミング・アルゴリズムが多くあるが、それらはこの実施形態に容易に適合される。ステミングは、各単語の語尾を、前に定義した接尾語に一致する接尾語の存在について分析して実行されてもよい。接尾語が存在する場合、各接尾語に関連する判定基準により、その接尾語をその単語から削除してよいかどうかを決定する。代わりに、ステミングはルート・ステム（語根・語幹）辞書と組み合わせて実行してもよい。
【００６３】
ステミング・プロセスの完了に続いて、ステミング後のテキスト・データについてストップ・リスト・フィルタリングを実行する。ストップ・リスト・フィルタリングは、共通のストップ・ワード、例えば「ａ」、「ｔｈｅ」、「ａｎｄ」、「ｏｆ」のような、識別上意味のない単語を削除する。テキスト情報からストップ・ワードを除去した後、トークン化を実行する。トークン化は、固有番号またはコードを残りすべての固有の語根・語幹に割り当てることである。固有のトークン値のセットは、「辞書」と呼ばれる。以下に説明するように、辞書のサイズは特徴ベクトルの長さを決定する。
【００６４】
１つの実施形態においては、各トークンの数値は特徴ベクトル内のパラメータ位置に相当する。例えば１の数値を持つトークンは、特徴ベクトルの第１パラメータに相当する。同様に、２の数値を持つトークンは、の第２特徴ベクトル・パラメータに相当する。各トークン値が特徴ベクトル・パラメータに相当するため、特徴ベクトルは全辞書サイズと同一数のパラメータを含む。
【００６５】
特徴ベクトルは、トークン化テキスト情報を個別のフレームに分割またはウィンドウ化することにより、生成される。可変フレーム幅および重複を利用して結果を最適化可能である。典型的なテキスト・ウィンドウの例は、単一センテンス、パラグラフ、または一定数の単語である。１つの実施形態では、最適復元長さは２４〜３６行のテレテキスト（約１００〜２００単語）である。一般に、フレーム幅の選択は、信頼性のある距離測定値と主要な要約終了点との間のトレード・オフ（同時に満足できない諸条件間の取捨選択）になる。フレーム幅が小さくなると、要約を正確に配置できるが、小さいフレームは含む単語数が少ないため、大規模な作品に対する要約の類似度の測定の信頼性が低下する。逆に、ウィンドウが大きくなると、類似度測定の信頼性が上がる。ただし、要約の開始および終了点は、テキスト・ウィンドウの幅と同程度に正確に配置可能である。
【００６６】
代替実施形態では、境界情報を使用してトークン化テキスト情報を分割してもよい。例えば、テキスト情報をパラグラフまたはセンテンスにより分割するのが望ましいだろう。１つの実施形態では、この分割は、行中のパラグラフの終了を表わす２つの改行復帰を検出するか、またはセンテンスの境界を表わす、スペースおよび大文字が後に続くピリオドを検出することにより達成されてもよい。ページ番号表示のような他のタイプの境界情報も同様に使用してもよい。
【００６７】
各ウィンドウ内で、各固有のトークンの量がカウントされる。トークン・カウントはそのウィンドウの特徴ベクトルの値を定義する。与えられたウィンドウに対し、特徴ベクトルの各パラメータが、対応するトークンがそのウィンドウ内に出現する回数を表示する。前述の例に続いて、第１トークンがそのウィンドウ内に３回出現し、第２トークンが１回出現する場合、このウィンドウの特徴ベクトルの第１の２つのパラメータは（３、１）である。
【００６８】
次に、テキスト情報のパラメータ化ステップの１つの実施形態を説明する。テキスト情報の以下の２つのウィンドウを仮定する。
【００６９】
【表１】
テキスト情報ウィンドウの例
0004345321.tif 000002
ステミング、ストップ・ワード・フィルタリング、およびトークン化の後、テキスト情報は次のように表示される。
【００７０】
【表２】
トークン化テキスト情報ウィンドウの例
0004345321.tif 000003
この表記法では、トークン番号は各単語の後ろの括弧内に表示される。この例では、ルート・ステム（語根・語幹）「ポテト」は（１）のトークンを表わし、ルート・ステム「嫌い」は（２）のトークンを表わし、また単語「誰」は（３）のトークンを表わす。したがって、この例の辞書は（ポテト、嫌い、誰）を表わし、特徴ベクトル長さは３である。
【００７１】
次に、各トークンの出現数をカウントして、各ウィンドウに対し特徴ベクトルを形成する。例に続いて、各テキスト・ウィンドウのトークンをカウントすることにより、以下の特徴ベクトルが形成される。
【００７２】
【表３】
トークン化テキスト・ウィンドウからの特徴ベクトル形成
0004345321.tif 000004
上の表に示したように、この例では、第１ウィンドウ内に、ワード「ポテト」のトークンは２回、「嫌い」のトークンは１回現われ、また「誰」のトークンは現れないが、第２ウィンドウに１回現われる。したがって、第１ウィンドウの特徴ベクトルの第１パラメータは２、第２パラメータは１、第３パラメータは０である。同時に、これらパラメータは第１ウィンドウに対する特徴ベクトル（２，１，０）を定義する。同様に、第２ウィンドウは特徴ベクトル（１，１，１）を有する。
【００７３】
マルチメディア情報のタイプまたは実行されるパラメータ化の型式に関係なく、ステップ１２０の結果は、ソース・マルチメディアに対応する特徴ベクトルのセットであり、パラメータ化マルチメディア信号と呼ばれる。１つの実施形態では、パラメータ化マルチメディア信号の特徴ベクトルは、ソース・マルチメディアの対応するマルチメディア情報と同一順に配列される。
【００７４】
ステップ１２０におけるソース・マルチメディアのパラメータ化に続いて、パラメータ化マルチメディア信号が、ステップ１４０における自己類似度分析に対する類似度マトリクスに埋め込まれる。自己類似度分析は、Footeの「オーディオ新規性の測定を用いた自動オーディオ分割（FOOTE, J., "Automatic Audio Segmentation using a Measure of Audio Novelty", Proc. IEEE International Conference on Multimedia and Expo (ICME) 2000, vol. I, pp. 452-455, New York, NY, August 2000）」に記載されている。この参照文献は、本明細書に組み入れられる。
【００７５】
図２は、オーディオおよび／またはビデオの自己類似度分析に使用される類似度マトリクスの構成を示す。パラメータ化信号２１０は特徴ベクトルを、それらの関連マルチメディア情報の順に配列する。特徴ベクトル２２０は、信号位置（ｉ）２２５に配置されたパラメータ化マルチメディア情報である。特徴ベクトル２３０は、信号位置（ｊ）２３５に配置されたパラメータ化マルチメディア情報である。信号位置（ｉ）２２５および（ｊ）２３０は、マルチメディア・ソース内の特徴ベクトルの時間または位置である。信号時間（ｉ）２２５および（ｊ）２３０の値は、パラメータ化信号２２７の開始からパラメータ化信号２２９の終了まで変化できる。
【００７６】
自己類似度分析の基本は、特徴ベクトル２２０および２３０の類似度２７０（Ｄ）の測定である。類似度２７０（Ｄ）の値は、類似度の度合いの測定値、または特徴ベクトル２２０と２３０との非類似度の測定値である。類似度２７０の簡単な測定値の１つは、パラメータ空間内で計算された特徴ベクトル間のユークリッド距離である。特徴ベクトルｖi２２０およびｖj２３０が、位置（ｉ）２２５および（ｊ）２３５にそれぞれ配置されたと仮定すると、ユークリッド距離は以下のように計算される。
【００７７】
【式１】
0004345321.tif 000005
【００７８】
代替実施形態では、類似度２７０は特徴ベクトルのスカラー（ドット）積である。この値は、特徴ベクトルが大きく、かつ類似度依存である場合に、大きくなる。別の実施形態では、スカラー積を正規化して、特徴ベクトル間の角度のコサインを得る。これにより特徴ベクトルの大きさに関する類似度の依存度を取り除く。この類似度測定２７０は標準的方法で計算し、２つのベクトル間の角度のコサインを、以下の式で求める。
【００７９】
【式２】
0004345321.tif 000006
【００８０】
この類似度測定は、特性ベクトルの大きさが小さい場合でも、大きい類似度スコアをもたらす。オーディオについては、これは、低エネルギーの相対的に類似する領域が、高エネルギーの相対的に類似する領域と同等の類似度を持つと判定される点で有利である。
【００８１】
特定のタイプのマルチメディア情報に対しては、フレーム・レートは一般的なイベントに比べて高速である。この状態の例は、フレーム・レートが、例えば１２５フレーム／秒のオーディオまたは音楽であり、このフレーム・レートはオーディオまたは音楽の有意な変化速度に比べてかなり高速である。このタイプのメディア情報に適用される類似度測定は、ウィンドウ幅ｗの全体に渡りベクトル相関を計算する。この類似度測定は、１つの位置の複数の連続特徴ベクトルを第２位置における複数の特徴ベクトルと比較する。この類似性測定は、フレーム・レートに比べて遅い時間スケール上のイベントを取り込むだけでなく、類似度測定における特徴ベクトルの時間依存イベントまたはシーケンスも取り込む。高い類似度スコアを持つためには、第１ウィンドウ内の特徴ベクトルは、第２ウィンドウ内の相当する特徴ベクトルと類似でなければならず、また各ウィンドウ内の特徴ベクトルのシーケンスが順に類似でなければならない。ウィンドウ幅ｗおよび類似度関数Ｄと仮定し、それらが前述の実施形態を含む、あらゆるタイプの距離関数であるとすると、特徴ベクトルのベクトル相関の類似度測定は以下の式になる。
【００８２】
【式３】
0004345321.tif 000007
【００８３】
パラメータ化テキスト情報に対しては、前述のベクトル測定のどのベクトル測定を使用しても、２つの特徴ベクトル間の類似度を計算できる。さらに、本発明の１つの実施形態は、２つの特徴ベクトルに共通のトークンの数をカウントすることにより類似度を測定する。代替実施形態では、２つの特徴ベクトル間の類似度計算において、各トークンに別々の重み値を適用する。類似度測定は２つの特徴ベクトルに共通の各トークンの重みの和である。
【００８４】
１つの実施形態では、類似度測定は、期間−頻度／逆ドキュメント頻度（ＴＦ／ＩＤＦ）重み、すなわち各トークンへの重み値を割り当てる重み付け方法を使用する。重み値は期間頻度、すなわちオリジナル・テキスト・ウィンドウ内に現れるトークンの頻度の測定、および逆ドキュメント頻度、すなわち全体としてのマルチメディア・ソース内のトークンの希薄度測定の組み合わせである。トークンは、オリジナル・テキスト・ウィンドウ内で共通であり、かつ全体としてマルチメディア・ソース内で相対的に少数である場合、高い重みで受け取られる。
【００８５】
１つの実施形態では、トークンの期間頻度値（ｔｆ）はテキスト・ウィンドウに出現する回数である。さらにトークンの逆ドキュメント頻度（ｉｄｆ）は、以下の式で与えられる。
【００８６】
idf(t) = logN(t) - logn(t)
【００８７】
ここでＮ（ｔ）はソース・マルチメディア内のテキスト・ウィンドウの全体数であり、ｎ（ｔ）はその中にトークンｔが出現するテキスト・ウィンドウの数である。２つの特徴ベクトルに共通の各トークンについては、１つの実施形態では、重み（Ｗ）は以下の式で計算できる。
【００８８】
【式４】
0004345321.tif 000008
【００８９】
ここでＮＤＬはテキスト・ウィンドウのサイズである。ｋおよびｂは調整定数であり、トークン重みへの期間頻度およびドキュメント長さの影響をそれぞれ緩和する。一般に、ｂの範囲は０〜１、ｋは任意の数、例えば２であってもよい。
【００９０】
別の実施形態では、テキスト・ウィンドウが少数のワードまたは１つのセンテンスに比べて大きい場合、トークンは異なる頻度でテキスト・ウィンドウ内に現れる。トークン（ｔ）がテキスト・ウィンドウ内に頻度ＱＦ（ｔ）で出現する場合、調整重み（ＡＷ）は以下の式で計算できる。
【００９１】
AW(t) = QF(t)W(t)
【００９２】
代替実施形態では、重みは、例えば期間頻度またはドキュメント重み、あるいは特徴ベクトルまたはマルチメディア・ソースから得られる他の属性のような、前述の特徴ベクトル属性の異なる数学的組合せにより計算できる。
【００９３】
使用される類似測定のタイプに関係なく、類似度測定はパラメータ化マルチメディア信号の２つの特徴ベクトルの関数である。パラメータ化信号内のすべての可能な類似度測定を考慮することが有利である。これは類似度測定を２次元表現内に埋め込むことによりなされる。正方マトリクス２５０はパラメータ化信号内の全特長ベクトル間の類似度２７０の２次元表現である。マトリクス２５０はパラメータ化信号２１０内のフレームの全組合せに対して計算された類似度２７０を含む。
【００９４】
マトリクス２５０では、水平軸２６０は信号時間（ｊ）のすべての値を表わす。垂直軸２５５は信号時間（ｉ）のすべての値を表わす。垂直軸位置２６５は信号時間（ｉ）２２５に対応し、水平軸位置２７０は信号時間（ｊ）２３０に対応する。マトリクス要素２７５は位置２６５と２７０の交点に置かれる。マトリクス要素２７５の値は、信号時間（ｉ）２２５における特徴ベクトル２２０と、信号時間（ｊ）２３５における特徴ベクトル２３０との間で計算される類似度測定値２７０である。類似度の計算は、マトリクス２５０の全要素に対して計算される。類似度測定値２７０が対称である場合、すなわち、Ｄ（ｉ，ｊ）＝Ｄ（ｊ，ｉ）である場合、マトリクス２５０は同様に対称である。
【００９５】
図３は本発明の方法の１つの実施形態により作成された類似度マトリクスの例の図である。グラフ３１０は、パラメータ化マルチメディア信号の例から計算される類似度マトリクスの図である。グラフ３１０の各要素は、要素の類似度の値に比例してグレー・スケール値で濃淡を付けられている。明るい領域は高い類似度、暗い領域は低い類似度を表わす。
【００９６】
主対角線は特徴ベクトル同士の比較を表わすため、類似度マトリクスの主対角線は白いラインで明瞭に目に見える（各特徴ベクトルはそれ自体に対し最高の類似度を有する）。例えばオーディオの無音または静止ビデオ画像のような、高い類似度の領域は、対角線上に明るい正方形で表わされる。繰り返しのオーディオ・サウンドまたはビデオ・ショットは、明るい対角線から外れた矩形で表わされる。オーディオまたはビデオの繰り返し回数が多い場合、主対角線から繰り返し回数だけ偏り、対角の縞またはチェッカーボードで表われる。グラフ３１０から明らかなように、パラメータ化マルチメディア信号の別個の領域間の移動、例えばビデオ・シーンの変化は、別個の「チェッカーボード」パターンを生成する。
【００９７】
類似度マトリクスの各行に注目すると、全体マルチメディア・ソースに対するマルチメディア・ソースの単一フレームの類似度が表われていることが分かる。特定の行に沿って見てゆくと、その行の所定の点における類似度の値が、その行に関連するフレームと、該所定の点において該行に交差する列に関連するフレームとの間の類似度を表わす。全体として、類似度マトリクスの各行は、その時間（または位置）におけるマルチメディア・ソースの一部分と、マルチメディア・ソースの残り部分とに関連するフレームの間の類似度を表わす。類似度マトリクスが対称であるため、類似度測定値が対称である場合、各列も、その時間（または位置）におけるマルチメディア・ソースの一部分と、マルチメディア・ソースの残り部分とに対応する特徴ベクトル間の類似度を表わす。
【００９８】
マルチメディア・ソースの１つのフレームと残りとの間の類似度を表わす類似度マトリクスの１つの行（または列）についてのこの概念を拡張して、マルチメディア・ソースを最適に要約するセグメントを見つけることができる。セグメントはマルチメディア・ソースの隣接する部分である。これは類似度マトリクスの隣接する行または列のセットに相当する。作品全体を最良に表わす作品のセグメントを見つけるには、対象のセグメントが他のすべての対象セグメントに比べて、作品全体に対し最高の類似度を有することが望ましい。
【００９９】
図４は類似度マトリクスから最適類似度のセグメントを配置する方法の１つの実施形態である。対象セグメント４２０はパラメータ化マルチメディア信号４１０の一部分である。対象セグメント４２０は開始点ｑ４２３および終了点ｒ４２５、ならびにｌ＝ｒ−ｑで定義される長さｌを有する。類似度マトリクス４５０は上述の方法で計算される。対象セグメント４２０は類似度マトリクス４５０の隣接行４６０のセットに相当する。
【０１００】
マルチメディア・ソースに対する対象セグメント４２０の全体類似度は、そのセグメントの平均類似度測定値を求めることにより計算される。類似度マトリクス４５０については、セグメントの平均類似度測定値は、セグメント長さによって正規化されたセット４６０の各行の類似度測定値の和である。図としては、平均類似度は、領域４７０の領域により正規化された、類似度マトリクス４５０のハッチング領域４７０内のすべての類似度測定値の和で表わされる。平均類似度のこの計算は以下の式で表わされる。
【０１０１】
【式５】
0004345321.tif 000009
【０１０２】
ここでＬは全体のパラメータ化マルチメディア・ソースの長さである。
【０１０３】
【外１】
0004345321.tif 000010
【０１０４】
最高の平均類似度値を持つセグメントが最適セグメントとして選択され、このセグメントに対応するマルチメディア・ソースの部分が最適要約となる。１つの実施形態では、すべての可能な開始および終了位置全体に渡る平均類似度関数を最大にすることにより、複数の最適要約を配置する。また別に、１つの実施形態では複数の最適要約を作成するが、それには、第１最適セグメントを見出し、そのセグメントを類似度マトリクスから削除し、その後、該変更された類似度マトリクスの最適セグメントを見出して第２最適要約を配置することにより作成する。このプロセスを、所望の数の要約を作成し終わるまで繰り返すか、または停止基準に一致するまで繰り返す。
【０１０５】
代替実施形態では、重み関数を使用して、以下の式により重み平均類似度を求める。
【０１０６】
【式６】
0004345321.tif 000011
【０１０７】
重み平均類似度関数は前述のようにして最大化し、最適要約を求める。重み関数の例は時間と共に重みを減少させ、作品の最初のセグメントを最後のセグメントに比べて優先するようにする。オーディオについては、重み関数の例は音の大きさと共に重みを増加させ、例えばトゥッティ（tutti、全楽器演奏の楽句）や合唱のような音楽の音量の大きい部分を、詩歌（verse）のような静かな節に比べて優先する。ビデオについては、重み関数の例は運動または顔検出器を含み、それにより、演技または人の表情を含むようにする。これらの例から、作品についての優先度の既知のあらゆる情報を、重み関数に組み入れることができる。これにより重み関数が、最適要約に含めるのが望ましい任意の部分を優先するようにできる。
【０１０８】
本発明の実施形態にかかるコンピュータ上で実行可能なプログラム（以下、単にプログラムという。ここで、プログラムとは、命令のグループである。）及びコンピュータ読み取り可能な記録媒体（以下、単に記録媒体という。また、情報格納メディアでもある。）について説明する。ここで、記録媒体とは、コンピュータのハードウェア資源に備えられている読み取り装置に対して、プログラムの記述内容に応じて、磁気、光、電気等のエネルギーの変化状態を引き起こして、それに対応する信号の形式で、読み取り装置にプログラムの記述内容を伝達できるものである。かかる記録媒体としては、例えば、磁気ディスク、光ディスク、CD-ROM、コンピュータに内蔵されるメモリなどが該当する。
【０１０９】
記録媒体は、プログラムを記録するプログラム領域を備え、このプログラム領域には、本プログラムが記録されている。
【０１１０】
記録媒体に記録されているプログラムは、上記実施の形態を実行するためのプログラムである。
【０１１１】
処理デバイスであるコンピュータは、プロセッサを備え、そのプロセッサによって本プログラムを読み取り実行することができる。
【０１１２】
本発明の好ましい実施形態の前述の記述は、図示および説明の目的のために提供してきた。これは、本発明を、開示したものと全く同一の形態に限定または制限することを意図するものではない。当然、当業者には、多くの修正または変形形態は明らかであろう。実施形態の選択および説明は、本発明の原理およびそれの実際の用途を最も分かり易く説明するのが目的であり、それにより、当業者が、各種の実施形態に対する本発明、および意図する特定の用途に適する各種修正形態を有する本発明を理解可能にする。本発明の範囲は前述の特許請求の範囲およびそれの均等物により定義する。
【図面の簡単な説明】
【図１】本発明の方法の１つの実施形態のブロック図を示す。
【図２】パラメータ化マルチメディアを類似度マトリクスに埋め込む方法の１つの実施形態を示す。
【図３】本発明の方法の１つの実施形態により作成された類似度マトリクス例の図を示す。
【図４】類似度マトリクスから最適類似度のセグメントを配置する方法の１つの実施形態を示す。
【符号の説明】
１００  ダイアグラム
１２０、１４０、１６０、１８０  ステップ
２１０  パラメータ化信号
ｖi２２０、ｖj２３０  特徴ベクトル
（ｉ）２２５、（ｊ）２３５  位置
２２７  パラメータ化信号
２２９  パラメータ化信号
２５０  正方マトリクス
２５５  垂直軸
２６０  水平軸
２６５  垂直軸位置
２７０（Ｄ）  類似度
２７０  水平軸位置
２７５  マトリクス要素
３１０  グラフ
４１０  パラメータ化マルチメディア信号
４２０  対象セグメント
ｑ４２３  開始点
ｒ４２５  終了点
４５０  類似度マトリクス
４６０  隣接行
４７０  領域
ｊ、ｉ  信号時間
ｌ  長さ
【図１】
0004345321.tif 000012
【図２】
0004345321.tif 000013
【図３】
0004345321.tif 000014
【図４】
0004345321.tif 000015