(57)【特許請求の範囲】
【請求項１】
ビデオワークの編集システムであって、
コントローラと、
順序付けられたビデオ情報を受信する入力手段と、
受信された前記順序付けられたビデオ情報をウィンドウ処理するためのウィンドウ処理手段と、
ウィンドウ処理された情報をパラメータ化するためのパラメータ化手段と、
２つのパラメータ化された情報ベクトルの類似性を判断し、類似性情報を類似性マトリックスに格納するための、類似性マトリックス決定手段と、
特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの分解を決定するための直交マトリックス分解手段と、
決定された前記類似性マトリックスの分解にもとづいて、前記順序付けられたビデオ情報における主要構成要素の境界を決定する主要構成要素境界決定手段と、
決定された前記主要構成要素の境界に基づいて決定されるビデオ情報のセグメントを用いてビデオワークを生成するビデオワーク生成手段と、
生成されたビデオワークを受信しユーザへ表示する表示手段と、
を含む、ビデオワークの編集システム。
【請求項２】
音声情報の編集システムであって、
コントローラと、
順序付けられた音声情報を受信する入力手段と、
受信された前記順序付けられた音声情報をウィンドウ処理するためのウィンドウ処理手段と、
ウィンドウ処理された情報をパラメータ化するためのパラメータ化手段と、
２つのパラメータ化された情報ベクトルの類似性を判断し、類似性情報を類似性マトリックスに格納するための、類似性マトリックス決定手段と、
特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの分解を決定するための直交マトリックス分解手段と、
決定された前記類似性マトリックスの分解にもとづいて、前記順序付けられた音声情報における主要構成要素の境界を決定する主要構成要素境界決定手段と、
決定された前記主要構成要素の境界に基づいて決定される音声情報のセグメントを用いて音声情報ワークを生成する音声情報ワーク生成手段と、
生成された音声情報ワークを受信しユーザに提示する提示手段と、
を含む、音声情報の編集システム。
【請求項３】
順序付けられたビデオ情報を受信するステップと、
受信された前記順序付けられたビデオ情報をウィンドウ処理するステップと、
ウィンドウ処理された情報をパラメータ化するステップと、
パラメータ化された情報を二次元表示に格納するステップと、
二次元表示のベクトルの類似性マトリックスを決定するステップと、
特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの直交マトリックス分解を決定するステップと、
決定された前記類似性マトリックスの直交マトリックス分解にもとづいて、前記順序付けられたビデオ情報における主要構成要素の境界を決定するステップと、
決定された前記主要構成要素の境界に基づいて決定されるビデオ情報のセグメントを用いてビデオワークを生成するステップと、
生成されたビデオワークを受信しユーザに表示するステップと、
を含む、ビデオワークの編集機能を、コンピュータに実行させるためのプログラム。
【請求項４】
順序付けられた音声情報を受信するステップと、
受信された前記順序付けられた音声情報をウィンドウ処理するステップと、
ウィンドウ処理された情報をパラメータ化するステップと、
パラメータ化された情報を二次元表示に格納するステップと、
二次元表示のベクトルの類似性マトリックスを決定するステップと、
特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの直交マトリックス分解を決定するステップと、
決定された前記類似性マトリックスの直交マトリックス分解にもとづいて、前記順序付けられたビデオ情報における主要構成要素の境界を決定するステップと、
決定された前記主要構成要素の境界に基づいて決定される音声情報のセグメントを用いて音声情報ワークを生成するステップと、
生成された音声情報ワークを受信しユーザに提示するステップと、
を含む、音声情報の編集機能を、コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は順序付けられた情報の自動セグメント化及びクラスタ化に関する。
【０００２】
【従来の技術及び発明が解決しようとする課題】
これまでの音声要約技術は、音声を分割（セグメント化）し、各セグメントから代表的な選択肢を選択する。これら選択肢の部分集合は音声の要約として用いられる。しかしながら、これら従来のシステムでは、候補セグメントを作成するためにワーク全体を再検討しなければならないので、要約を生成するのに多くの時間を必要とする。要約に対し代表的なセグメント選択肢を選択するために更なる検討が要求される。最後に、代表的なセグメントが選択された場合でも、その代表的なセグメントが適切な要約を付与するにはあまりに長すぎることもある。
【０００３】
ビデオの要約を生成する場合、一般的なビデオ要約生成プログラムはシーン遷移グラフを用いてケースバイケース(ad-hoc)のセグメント化を実行することを試みてきた。このケースバイケースのセグメント化の後に階層クラスタ化処理が行なわれて要約を作成する。他の一般的なビデオ要約生成プログラムでは、クローズドキャプション（字幕）、音響上の無音及びピッチを用いてセグメント境界を決定し、要約の生成に使用するための候補セグメントを識別してきた。これら従来のシステムは、ワーク内部のクローズドキャプション、音響上の無音及びピッチの存在を判断することに依存し、これらの特徴の検出が困難であったり、ワークから欠落されている場合にはうまく作動しない。さらに、これら従来のシステムは単に代表的なセグメントを選択するだけなので、過度に長い候補セグメントの要約を生成することは不可能である。
【０００４】
【課題を解決するための手段】
本発明によるシステム及び方法は、順序付けられたデータの自動セグメント化及びクラスタ化を提供する。本発明によるシステム及び方法はまた、自己類似性に基づく自動セグメント化を提供する。
【０００５】
自動要約は種々の環境において有用である。例えば、自動音声／ビデオ要約は、音声／ビデオ分類及びリトリーブシステムにおいて有用である。ビデオワークはセグメント化され、各セグメントの主要構成要素は同様にセグメント化された第２のビデオと比較決定される。この比較の細分性に基づいて、主要構成要素の類似度を比較し、主要構成要素の変更のシーケンス及び／又は度数を決定し、あるいは比較された第１及び第２の各ワークの主要構成要素の類似性を決定する他の手段を用いることによって、類似した又は実質的に類似したワークを識別してもよい。
【０００６】
本発明による具体例としての種々の実施の形態において、第１のワーク及び他の任意の数のワークの主要構成要素が決定される。第１のテキストの第１の部分と、第２のテキストの第１の部分と、に存在する主要構成要素を決定することができ、速度（テンポ）等の一部の特徴に基づくワーク間における自己類似性の程度の視覚化を利用して同一の特徴に基づき他の同様なワークを分類することもできる。
【０００７】
テキスト情報の自動セグメント化及びクラスタ化は、テキスト情報ストリームの主要構成要素を決定することも含む。新聞、書籍、電子メッセージ又はその他のテキスト情報の主要構成要素が決定される。例えば、新聞の中の個々のニュース記事が、テキスト情報ストリーム内の種々のテキスト特徴の決定された主要構成要素に基づいて決定されることがある。ニュース記事の境界を決定することによって、更なる処理は個々に決定されたニュース記事に対し焦点を合わせても良い。この更なる処理には、決定されたニュース記事のテーマを決定することや、テーマによって異なる索引付け機構をトリガすること、あるいは他の周知の若しくは後日開発される処理が含まれることがある。ニューステキストの選択が一例にすぎないことは明白である。本の中の個々の章、文書内の個々のセクション、ニュース放送等の話し言葉による文字の表現形式、公判記録の謄本、あるいは順序付けられたテキスト若しくは他の情報の細部は、本発明の種々の実施の形態によって決定され且つクラスタ化される。
【０００８】
決定されたワークの主要構成要素に対するアクセスは、本発明の種々の実施の形態による音声及びビデオ索引付け機能によって付与される。例えば、査閲者は本発明のシステム及び方法によって自動的に決定されるように、ビデオワークをあるシーンへと進めたり、音声ワークをクライマックス(crescendo)へ進展させることがある。他の種々の実施の形態において、査閲者は、最も代表的な若しくは重要なシーン、又は主要構成要素へと進めたり、ワークの要約として自動的に決定された主要構成要素の何れかを使用してもよい。このように、ワークの査閲は簡易化される。
【０００９】
音声及び／又はビデオワークの開始、終了、中間の各動作点もまた、順序付けられた情報の自動セグメント化及びクラスタ化に基づいて自動的に選択される。音声ワークの決定された主要構成要素を対応する決定されたビデオワークの主要構成要素に一致させるように、音声ワークは整列又は変形されてもよい。同様に、音声ワークの決定された主要構成要素は、対応するビデオアニメーションの主要構成要素を決定し、バーチャルアクターによるビデオワークでのより現実的な口の動きを付与するために使用される。このように、インタラクティブゲーム及びインタラクティブフィルム等の音声及び／又はビデオワーク内のユーザのインターアクションが本発明による種々の実施の形態によって簡易化される。
【００１０】
本発明による具体例としての種々の実施の形態はさらに、バーチャルディスクジョッキーを提供する。仮想ディスクジョッキーは、テンポ、ビート、あるいはその他の特徴を決定するとともに、同様のテンポ、ビート、リズム、あるいは識別可能な特徴を有する音楽トラックを単一のワーク若しくは種々のトラックを含む「ミックス」に自動的に追加するために使用される。
【００１１】
本発明の第１の態様は、順序付けられた情報のセグメント化及びクラスタ化方法であって、順序付けられた情報をウィンドウ処理するステップと、ウィンドウ処理された情報をパラメータ化するステップと、パラメータ化された情報を二次元表示に格納するステップと、二次元表示のベクトルの類似性マトリックスを決定するステップと、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法の少なくとも１つに基づいて類似性マトリックスの直交マトリックス分解を決定するステップと、を含む。
【００１２】
本発明の第２の態様は、順序付けられたビデオ情報のセグメント化及びクラスタ化方法であって、順序付けられたビデオ情報をウィンドウ処理するステップと、ウィンドウ処理された情報をパラメータ化するステップと、パラメータ化された情報を二次元表示に格納するステップと、二次元表示のベクトルの類似性マトリックスを決定するステップと、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法の少なくとも１つに基づいて類似性マトリックスの直交マトリックス分解を決定するステップと、を含む。
【００１３】
本発明の第３の態様は、順序付けられた音声情報のセグメント化及びクラスタ化方法であって、順序付けられた音声情報をウィンドウ処理するステップと、ウィンドウ処理された情報をパラメータ化するステップと、パラメータ化された情報を二次元表示に格納するステップと、二次元表示のベクトルの類似性マトリックスを決定するステップと、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法の少なくとも１つに基づいて類似性マトリックスの直交マトリックス分解を決定するステップと、を含む。
【００１４】
本発明の第４の態様は、順序付けられたテキスト情報のセグメント化及びクラスタ化方法であって、順序付けられたテキスト情報をウィンドウ処理するステップと、ウィンドウ処理された情報をパラメータ化するステップと、パラメータ化された情報を二次元表示に格納するステップと、二次元表示のベクトルの類似性マトリックスを決定するステップと、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法の少なくとも１つに基づいて類似性マトリックスの直交マトリックス分解を決定するステップと、を含む。
【００１５】
本発明の第５の態様は、上記第３の態様において、上記順序付けられた音声情報のパラメータ化が、ＳＴＦＴフーリエ変換、メル周波数ケプストラル係数分析、スペクトログラム、高速フーリエ変換、及びウェーブレット分解のうちの少なくとも１つに基づくことを特徴とする。
【００１６】
本発明の第６の態様は、上記第２の態様において、上記順序付けられたビデオ情報のパラメータ化が、ヒストグラム、正規直交投影、圧縮マクロブロックのＤＣ係数から間引かれた画像を導出すること、及び離散コサイン変換のうちの少なくとも１つに基づくことを特徴とする。
【００１７】
本発明の第７の態様は、上記第４の態様において、上記順序付けられたテキスト情報のパラメータ化が、文、段落、メタデータ情報、用語頻度ドキュメント頻度の逆数情報、及び音声情報の一部のうちの少なくとも１つに基づくことを特徴とする。
【００１８】
本発明の第８の態様は、上記第１の態様において、上記順序付けられた情報の主要セグメントの数を関数に基づいて決定することをさらに含むことを特徴とする。
【００１９】
本発明の第９の態様は、上記第８の態様において、上記関数がしきい値を越える特異値の数であることを特徴とする。
【００２０】
本発明の第１０の態様は、上記第１の態様において、決定された特異ベクトルに基づいて少なくとも１つの順序付けられた情報のセグメント境界を決定することをさらに含むことを特徴とする。
【００２１】
本発明の第１１の態様は、順序付けられた情報のセグメント化及びクラスタ化方法であって、符号化された情報ストリームからウィンドウ及びパラメータ情報を読み取るステップと、圧縮された情報ストリームにおけるベクトルの類似性マトリックスを決定するステップと、圧縮された情報ストリームの特異値分解を決定するステップと、を含む。
【００２２】
本発明の第１２の態様は、順序付けられた情報のセグメント化及びクラスタ化システムであって、コントローラと、順序付けられた情報をウィンドウ処理するためのウィンドウ処理回路と、ウィンドウ処理された情報をパラメータ化するためのパラメータ化回路と、２つのパラメータ化された情報ベクトルの類似性を判断し、類似性情報を類似性マトリックスに格納するための、類似性マトリックス決定回路と、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの分解を決定するための直交マトリックス分解回路と、を含む。
【００２３】
本発明の第１３の態様は、順序付けられたビデオ情報のセグメント化及びクラスタ化システムであって、コントローラと、順序付けられたビデオ情報をウィンドウ処理するためのウィンドウ処理回路と、ウィンドウ処理された情報をパラメータ化するためのパラメータ化回路と、２つのパラメータ化された情報ベクトルの類似性を判断し、類似性情報を類似性マトリックスに格納するための、類似性マトリックス決定回路と、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの分解を決定するための直交マトリックス分解回路と、を含む。
【００２４】
本発明の第１４の態様は、順序付けられた音声情報のセグメント化及びクラスタ化システムであって、コントローラと、順序付けられた音声情報をウィンドウ処理するためのウィンドウ処理回路と、ウィンドウ処理された情報をパラメータ化するためのパラメータ化回路と、２つのパラメータ化された情報ベクトルの類似性を判断し、類似性情報を類似性マトリックスに格納するための、類似性マトリックス決定回路と、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの分解を決定するための直交マトリックス分解回路と、を含む。
【００２５】
本発明の第１５の態様は、順序付けられたテキスト情報のセグメント化及びクラスタ化システムであって、コントローラと、順序付けられたテキスト情報をウィンドウ処理するためのウィンドウ処理回路と、ウィンドウ処理された情報をパラメータ化するためのパラメータ化回路と、２つのパラメータ化された情報ベクトルの類似性を判断し、類似性情報を類似性マトリックスに格納するための、類似性マトリックス決定回路と、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの分解を決定するための直交マトリックス分解回路と、を含む。
【００２６】
本発明の第１６の態様は、上記第１４の態様において、上記順序付けられた音声情報のパラメータ化が、ＳＴＦＴフーリエ変換、メル周波数ケプストラル係数分析、スペクトログラム、高速フーリエ変換、及びウェーブレット分解のうちの少なくとも１つに基づくことを特徴とする。
【００２７】
本発明の第１７の態様は、上記第１３の態様において、上記順序付けられたビデオ情報のパラメータ化が、ヒストグラム、正規直交投影、圧縮マクロブロックのＤＣ係数から間引かれた画像を導出すること、及び離散コサイン変換のうちの少なくとも１つに基づくことを特徴とする。
【００２８】
本発明の第１８の態様は、上記第１５の態様において、上記順序付けられたテキスト情報のパラメータ化が、文、段落、メタデータ情報、用語頻度ドキュメント頻度の逆数情報、及び品詞情報の一部のうちの少なくとも１つに基づくことを特徴とする。
【００２９】
本発明の第１９の態様は、上記第１２の態様において、上記順序付けられた情報の主要セグメントの数を関数に基づいて決定することをさらに含むことを特徴とする。
【００３０】
本発明の第２０の態様は、上記第１９の態様において、上記関数がしきい値を越える特異値の数であることを特徴とする。
【００３１】
本発明の第２１の態様は、上記第１２の態様において、決定された特異値ベクトルに基づいて少なくとも１つの順序付けられた情報のセグメント境界を決定するための構成要素境界決定回路をさらに含むことを特徴とする。
【００３２】
本発明の第２２の態様は、コンピュータ読み取り可能記憶媒体に記憶されるコンピュータ読み取り可能プログラムコードを含む、コンピュータ読み取り可能記憶媒体であって、順序付けられた情報をウィンドウ処理するステップと、ウィンドウ処理された情報をパラメータ化するステップと、パラメータ化された情報を二次元表示に格納するステップと、二次元表示のベクトルの類似性マトリックスを決定するステップと、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの直交マトリックス分解を決定するステップと、を含む順序付けられた情報をセグメント化及びクラスタ化する方法、を実行するようにコンピュータをプログラムするのに使用可能である、上記コンピュータ読み取り可能プログラムコードを含む、コンピュータ読み取り可能記憶媒体である。
【００３３】
本発明の第２３の態様は、順序付けられた情報をセグメント化及びクラスタ化するための方法に使用可能な制御プログラムであって、順序付けられた情報のウィンドウ処理を受信するためのステップと、ウィンドウ処理された情報をパラメータ化するためのステップと、パラメータ化された情報を二次元表示に格納するためのステップと、二次元表示のベクトルの類似性マトリックスを決定するためのステップと、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法のうちの少なくとも１つに基づいて類似性マトリックスの直交行列分解を決定するためのステップと、を含む。
【００３４】
本発明の第２４の態様は、順序付けられた情報のセグメント化及びクラスタ化方法であって、順序付けられた音声情報と、順序付けられたビデオ情報と、順序付けられたテキスト情報のうちの少なくとも２つをウィンドウ処理するステップと、少なくとも２つのウィンドウ処理された情報をパラメータ化するステップと、少なくとも２つのパラメータ化された情報を、次元の１つが情報の順序付けに対応する、単一の二次元表示に格納するステップと、二次元表示のベクトルの類似性マトリックスを決定するステップと、特異値分解、固有ベクトル分析、グラム−シュミット及びガウス消去法の少なくとも１つに基づいて類似性マトリックスの直交マトリックス分解を決定するステップと、を含む。
【００３５】
【発明の実施の形態】
図１は、本発明による具体例としての自動セグメント化及びクラスタ化システムを含む概略図である。ユーザ装置１０は通信リンク２１０を介して、ウェブサーバ２０、音声／ビデオｅコマース（電子商取引）サーバ３０、音声ビデオ編集システム４０、音声／ビデオ整列システム５０、及び自動セグメント化及びクラスタ化システム１００に接続されている。
【００３６】
ユーザ装置１０を使用するインターネットビデオの購入を考えている人は、音声及び／又はビデオワークを再検討した後で、音声／ビデオ電子商取引サーバ３０を用いてそのワークを購入する。音声／ビデオ電子商取引サーバ３０は音声及び／又はビデオワークをリトリーブするとともに、自動セグメント化及びクラスタ化システム１００を起動して音声及び／又はビデオワークの要約を生成する。自動セグメント化及びクラスタ化システム１００は、ビデオワークにおける主要構成要素のそれぞれを決定し、決定された主要構成要素のサンプルに基づいて要約を生成する。音声及び／又はビデオワークの意外なエンディングをばらさないようにするために、決定された要約にはビデオワークの開始及び中間において決定された主要構成要素の部分のみが反映されてもよい。さらに、自動セグメント化及びクラスタ化システム１００を用いて主要構成要素の境界を決定するので、決定された主要構成のそれぞれの長さを決定し、全長の適切な部分のみを要約に含めてもよい。本発明の種々の実施の形態において、音声／ビデオワークの自動セグメント化及びクラスタ化によって音声構成要素、ビデオ構成要素、及び／又は音声・ビデオ結合構成要素が決定されることは明白である。
【００３７】
音声／ビデオ編集システム４０のユーザはまた、自動セグメント化及びクラスタ化システム１００を用いて、主要構成要素の境界を自動的に決定することに基づくスマートなカット／ペースト機能と、他の強化された編集能力を提供することもできる。例えば、音声／ビデオ編集システム４０のユーザはビデオワークをリトリーブする。ビデオワークは、通信リンク２１０を介して自動セグメント化及びクラスタ化システム１００に転送されて、ビデオワークの主要構成要素が決定される。
【００３８】
ビデオワークの決定された主要構成要素はさらに音声／ビデオ編集システム４０に返送され、主要なビデオ構成要素又はセグメントの境界を決定するために使用される。決定された主要構成要素又はセグメントの境界を使用して、ビデオワーク内の決定された主要構成要素に対しスマートなカット・ペースト作業、及び／又は他の強化されたビデオ作業を提供する。ビデオワークの編集を完成させるために必要な時間と専門知識が軽減されるのは、ビデオワークの主要なシーン等の重要な構成要素が自動的に決定されるからである。本発明による代替例としての種々の実施の形態において、自動セグメント化及びクラスタ化システム１００が音声／ビデオ編集システム４０に設置され、さらに／あるいは通信リンク２１０によってアクセス可能な位置にあってもよいことは明白である。他の種々の実施の形態において、音声、テキスト、又は他の順序付けられた情報の主要構成要素は同じように決定される。
【００３９】
アクセス装置（ユーザ装置）１０のユーザは、ウェブサーバ２０で使用可能なインタラクティブゲーム又はインタラクティブビデオを開始させる。ゲーム又はインタラクティブフィルムに関する音声／ビデオ情報を、通信リンク２１０を介し音声／ビデオ整列システム５０経由で自動セグメント化及びクラスタ化システム１００に転送してもよい。音声／ビデオ整列システム５０は、インタラクティブゲーム又はインタラクティブフィルムにおいてユーザの現在のビデオシーン、位置及び／又は現在の活動の現状を判断し、自動セグメント化及びクラスタ化システム１００によって決定された主要構成要素及び主要構成要素の境界に基づいて現在のビデオシーン、位置又は活動の現状にふさわしい音声を整列させたり整合させたりする。整列された音声／ビデオ情報はユーザへの表示のために、通信リンク２１０を介してユーザ装置１０へ転送される。
【００４０】
本発明による種々の実施の形態において、音声／ビデオ情報は、ＭＰＥＧ−３、ＭＰＥＧ−４、ＰＮＭ−リアルネットワークス・プロトコル、リアルネットワークスのリアルビデオ・プロトコル、マイクロソフトコーポレーションからのウィンドウズ（登録商標）メディアプレーヤにおけるマイクロソフト・メディア・ストリーミング・プロトコル、又は周知の若しくは後日開発される音声及び／又はビデオプロトコル等のストリーミング・音声／ビデオ・プロトコルに符号化される。個別に復号化及び符号化を必要とすることなく、符号化された情報ストリーム又はプロトコル内で符号化されたウィンドウ及びパラメータに直接アクセスするために、本発明による種々の実施の形態はまた、ＭＰＥＧ−４又は他の符号化された情報の作業を提供する。
【００４１】
図２は、本発明による具体例としての自動セグメント化及びクラスタ化システム１００を示す。コントローラ１０２、メモリ１０４、パラメータ化回路１０６、データ圧縮回路１０８、マトリックス記憶メモリ１１０、類似性マトリックス決定回路１１２、直交マトリックス分解回路１１４、しきい値記憶メモリ１１６、特異ベクトル決定回路１１８、主要構成要素境界決定回路１２０、及びインジケータベクトル決定回路１２２は、入出力回路１２４を介して通信リンク２１０に接続される。
【００４２】
コントローラ１０２は入出力回路１２４を起動させて、順序付けられた情報を通信リンク２１０を介してリトリーブ及び／又は受信する。この順序付けられた情報は、音声及び／又はビデオ情報のための時間、ならびにテキスト情報の位置等の順序付け次元を有する音声、ビデオ、テキスト又は他の情報を含む。
【００４３】
リトリーブ及び／又は受信された情報はメモリ１０４に格納される。パラメータ化回路１０６は、その受信及び／又はリトリーブされた情報に付加される適切な種類のパラメータ化を決定するために起動される。例えば、異なるウィンドウ及びパラメータ化を音声情報、ビデオ情報、テキスト情報又は他の種類の順序付けられた情報に付加してもよい。
【００４４】
本発明による具体例としての第１の実施の形態において、音声波形等の音声情報はフレームにウィンドウ処理されたり、ワークの音声情報を伴なうビデオ情報に対応付けられるフレームがウィンドウとして使用される。
【００４５】
次に、ウィンドウ処理された音声情報のパラメータ化が決定される。ウィンドウ処理された音声情報は、短時間フレームフーリエ変換（ＳＴＦＴ）、フーリエ変換、メル周波数ケプストラル係数分析、スペクトログラム、高速フーリエ変換（ＦＦＴ）、ウェーブレット分解、あるいは、本発明の精神及び範囲から逸脱することのない他の周知の若しくは後日開発される分析技術を用いて、パラメータ化してもよい。
【００４６】
同様に、ビデオ及びテキスト情報等の他の順序付けられた情報もまた、ウィンドウ処理することができる。例えば、ビデオ情報は、ビデオ情報の個々のフレームを選択し、さらに／あるいは、平均値を決定するために平均化されるフレームの群を選択することによってウィンドウ処理されてもよい。テキスト情報は、語、文、段落、任意の数の語を選択し、品詞、メタデータ、ＸＭＬ及び／又はＨＴＭＬ符号化、重要性、用語頻度及び／若しくはドキュメント頻度の逆数などの属性、又は他の周知の若しくは後日開発されるテキストをウィンドウ処理するための技術に基づいて、語を選択することによって、ウィンドウ処理されてもよい。
【００４７】
次にウィンドウ処理された他の順序付けられた情報のパラメータ化を決定する。例えば、ビデオ情報のパラメータ化は、参考のために全体が明細書に組み込まれる「Video Parsing, Retrieval and Browsing: an Integrated and Content-Based Solution」（by Zhang et al, in Intelligent Multimedia Information Retrieval, AAA Press, MIT Press, 1997）に開示されているように、カラーヒストグラムの使用を含むことがある。あるいはまた、パラメータ化され且つ間引かれたビデオ情報が圧縮マクロブロックのＤＣ係数から導出されてもよいし、離散コサイン変換がビデオ情報に適用されてもよいし、又は、他の周知の若しくは後日開発される、順序付けられた情報のパラメータ化方法が使用されてもよい。
【００４８】
任意選択のデータ圧縮回路１０８は、パラメータ化情報のメモリ必要記憶量を軽減するために任意選択により起動される。例えば、参考のために全体が明細書に組み込まれる「Video Classification Using Transform Coefficients」（by Girgensohn et al., in Proc ICASSP '99 Vo.6 p.3045-3048, Phoenix, AZ, IEEE, 1999）に記載される方法のいずれかによって、この必要記憶量は圧縮されてもよい。あるいはまた、トランケーション（打ち切り又は切り捨て）、主要構成要素分析、順序付け識別分析又は、他の周知の若しくは後日開発されるデータ圧縮方法を、単独又は組み合わせて用いて、元のウィンドウ又はフレームに関する顕著な情報を保存するパラメータ化情報の任意選択の縮小表示を作成するようにしてもよい。例えば、パラメータ化された音声／ビデオ情報の縮小表示は、音声及び／又はビデオの各フレームごとに縮小係数のコンパクト特徴ベクトルを示す。この縮小表示は元の順序付けられた情報の再現のためではなく、分析のために使用されるので、元の情報をリカバーする必要はなく、主要構成要素を示すために使用される。このように、縮小表示をさらに縮小してもよい。
【００４９】
各要素Ｄ（ｉ，ｊ）の値には、最大輝度等の最大特徴値との比較に基づく決定された色情報値が割り当てられる。自己類似性が高い要素D(i,j), i=j はそれぞれ、対応するより高い輝度値を有し、対角線に沿って現われる。反復される部分は、対角線から離れて出現する高輝度の領域によって示される。高輝度値の対角線ストライプ及び／又はチェッカー盤パターンは、パラメータ化情報の反復を示す。各要素Ｄ（ｉ，ｊ）の類似値は、類似性マトリックス決定回路１１２により決定され、マトリックス記憶装置１１０に格納される。
【００５０】
類似性マトリックス決定回路１１２は、以下式（１）に示されるようなパラメータ化情報ベクトル間のユークリッド距離に基づく類似性を決定する。
【００５１】
【数１】
0004254160.tif 000002
【００５２】
具体例としての他の種々の実施の形態における類似性は、類似性マトリックスを含むパラメータ化情報ベクトルの内積に基づいて決定することもできる。例えば、２つの大きな類似性ベクトルの内積は、以下式（２）によって示されるように大きくなる。
【００５３】
【数２】
0004254160.tif 000003
【００５４】
類似性は、パラメータ化情報ベクトル間のコサイン角度、カルバック−ライブラー距離等のベクトル統計の関数、又は本発明の精神若しくは範囲から逸脱することなく情報ベクトルの類似性を決定する他の周知の若しくは後日開発される方法を用いて決定することもできる。距離測定又は距離は、対角線上の要素Ｄ（ｉ，ｊ）がそれに対する各要素の類似性を表示するように類似性マトリックスに組み込まれる。したがって、自己類似性は、対角線上で最大になる。
【００５５】
直交行列分解回路１１４は、マトリックス記憶装置１１０に格納された類似性マトリックスを対角マトリックスにするために起動される。この直交行列分解は、特異値分解型の直交行列分解を用いて説明する。しかしながら、本発明の精神又は範囲から逸脱することなく固有ベクトル分析、ガウス消去法、グラム−シュミット又は他の周知の若しくは後日開発される行列分解技術を使用してもよいことは明白である。
【００５６】
例えば、ｍ×ｎのマトリックスＡが、式（３）により付与される。
Ａ＝ＵΣＶt       （３）
ここで、Ｕは直交列を備えたｍ×ｍマトリックスであり、Ｖは列を備えたｎ×ｎマトリックスである。Ｕの列はＡＡTの固有ベクトルｓであり、Ｖの列はＡtＡの固有ベクトルｓであり、Σは、対角線行列である。Σの対角線行列は、Ａの特異値である。正の有限マトリックスの因数分解は、Ａの固有値／固有ベクトル分解に相当する。
【００５７】
特異値分解技術を用いる機能が有益であるのは、特異値分解が矩形行列に適用されるからである。特に、矩形行列の使用は、本発明による種々の実施の形態における音声及びビデオマトリックス等の個別に決定されるマトリックスの組み合わせを可能にする。
【００５８】
有効ランクは、しきい値記憶装置１１６からリトリーブされたしきい値を越える特異値の数を決定することによって算出することができる。
【００５９】
ｕiによりＵの列が付与され、ｖiによりＶの列が付与される
Ａ＝ＵΣＶt       （４）
に対し、
σ1≧σ2≧・・・≧σn      （５）
とすると、
【００６０】
【数３】
0004254160.tif 000004
【００６１】
フロベニウス行列正規化を用いて、以下の式が得られる。
【００６２】
【数４】
0004254160.tif 000005
【００６３】
特異ベクトル決定回路１１８は、マトリックスＡにおける特異ベクトルを決定するために起動される。
【００６４】
ランク縮小近似は、Ａの本質的なブロック構造を示す。しかしながら、決定された主要特異ベクトルは、圧縮形態の類似性マトリックスの構造内容の有効な要約である。
【００６５】
主要構成要素境界決定回路１２０は、特異ベクトルに基づいて決定された主要構成要素のそれぞれの境界を決定するために起動される。例えば、しきい値を越える特異値の数は主要構成要素に対応する。順序付けられた情報における主要構成要素の配置又は位置は、しきい値を越える各特異値に対応付けられる特異ベクトルから決定されることもある。
【００６６】
インジケータベクトル決定回路１２２は、特異値ベクトルに基づいて遷移又はインジケータベクトルを決定するために起動される。遷移又はインジケータベクトルを用いて決定された主要構成要素の変化を指示することもできる。例えば、第１の特異ベクトルが最大であれば、対応するインジケータベクトルは最大値、例えば、１を示す。同様に、第１の特異ベクトルが最小であれば、対応するインジケータベクトルは最小値、例えば、０を示す。これらの値の間のインジケータベクトルの遷移は、決定された主要構成要素の境界に対応する。
【００６７】
具体例としての種々の実施の形態において、決定された主要構成要素の境界に対応付けられるパラメータ化情報を直観的視覚インジケータとして使用してもよい。例えば、音声／ビデオ編集システム４０では、インジケータベクトル遷移によって指示されるように、決定されたシーン又は主要構成要素に対応する情報画像等の直観的視覚インジケータは、スクロールバーに直接表示される。ユーザは、直観的視覚インジケータが情報ストリームの主要構成要素に対応することを理解するとともに、直観的視覚インジケータ又は表示されたパラメータ化情報画像を選択することによって情報ストリームの一部を直ちに選択することもできる。
【００６８】
図３及び図４は、本発明による自動セグメント化及びクラスタ化の具体例としての方法のフローチャートである。ステップＳ１０からプロセスが開始し、ステップＳ２０へと続く。
【００６９】
ステップＳ２０において、情報は情報のタイプに基づいてウィンドウ又はフレームにパラメータ化される。例えば、音声情報は、ＳＴＦＴフーリエ変換、メル周波数ケプストラル係数分析、分光写真、高速フーリエ変換（ＦＦＴ）あるいは周知の若しくは後日開発されるパラメータ化方法を適用してパラメータ化することもできる。
【００７０】
同様に、その情報がビデオ情報であると判断されると、ビデオ情報は、ビデオの個々のフレーム、平均化されるフレームの群、あるいは、本発明の精神又は範囲から逸脱することなくビデオ情報をウィンドウ処理する他の周知の若しくは後日開発される方法を選択することによって、ウィンドウ処理されてもよい。特に、情報のウィンドウ処理は固定であっても変動性であってもよいことに注意されたい。同じように、テキスト情報は、語、文、段落、品詞、あるいは他の周知の若しくは後日開発される方法や技術に基づいてウィンドウ処理されるとともにパラメータ化されることがある。
【００７１】
ウィンドウ処理されたビデオ情報はさらにパラメータ化され、カラーヒストグラムを用いて係数を生成する。しかしながら、圧縮ブロックのＤＣ係数、離散的コサイン変換、あるいは他の周知の若しくは後日開発されるパラメータ化方法から導出される間引かれた画像を発明の精神又は範囲から逸脱することなく使用してもよいことは明白である。制御はさらにステップＳ３０へと続く。
【００７２】
ステップＳ３０において、パラメータ化情報の係数は任意選択的に低減される。パラメータ化情報の係数の任意選択的縮小は、元のウィンドウまたはフレーム情報に関する顕著な情報を保存する。例えば、トランケーション（切り捨て）、主要構成要素の分析、線形識別分析、Girgensohn et al.において論じられている方法、あるいは、他の周知の若しくは後日開発される分析技術を本発明の実施に使用してもよい。制御はさらにステップＳ４０へと続く。
【００７３】
パラメータ化され且つ任意選択的に縮小された情報は類似性の判断に基づいて二次元表示で格納される。この二次元表示はマトリックス、線形表示、あるいは他の周知の若しくは後日開発される次元表示でもよい。制御はさらにステップＳ５０へと続く。
【００７４】
ステップＳ５０において、二次元表示における各ベクトル間の類似性の判断は、例えば、パラメータ化空間におけるパラメータ化ベクトル間のユークリッド距離、ベクトルの内積、ベクトル間の角度のコサイン、カルバック−ライブラ距離等のベクトル統計の関数、あるいは他の周知の若しくは後日開発される類似性判断の技術に基づいて行なってもよい。制御はさらにステップＳ６０へと続く。
【００７５】
ステップＳ６０において、類似性マトリックス値は、すべてのフレームの組み合わせに対し決定される。制御はさらにステップＳ７０へと続く。
【００７６】
ステップＳ７０において、距離マトリックスは類似性表示に組み込まれる。例えば、類似性マトリックスが類似性の表示として使用されると、Ｄ（ｉ，ｊ）の値は、２つのベクトル間の相対類似度を示す。従って、ｉ＝ｊの場合の値Ｄ（ｉ，ｊ）が最大値を示すのは、ベクトルが対角線に沿うそれ自体に対し最も類似しているからである。制御はさらにステップＳ８０へと続く。
【００７７】
特異値分解、固有ベクトル分析、ガウス消去法、グラム−シュミット、又は他の周知の若しくは後日開発される、類似性表示若しくは類似性マトリックスの分解等の直交行列分解はステップＳ８０において決定される。記載の便宜上、特異値分解について説明する。しかしながら、直交行列分解のいずれの技術も本発明の実施に使用してもよいことは明白である。特異値分解は、既述された技術や方法の何れかを使用して決定されてＵ／Ｖマトリックスを作成する。制御はさらにステップＳ９０へと続く。
【００７８】
ステップＳ９０において、情報における主要構成要素は、しきい値を越える特異値の数に基づいて決定される。このしきい値は情報ストリームから主要構成要素を判別するために使用される。制御はさらにステップＳ１００へと続く。
【００７９】
情報の主要構成要素の境界は、ステップＳ１００における特異ベクトルに基づいて決定される。制御はさらに、ステップＳ１１０へと続く。
【００８０】
ステップＳ１１０において、インジケータベクトルは、対応する特異値に基づいて決定される。例えば、インジケータベクトルの値の各遷移は情報ストリームの決定された主要構成要素間の距離を指示する。制御はさらにステップＳ１２０へと続く。
【００８１】
ステップＳ１２０において、主要構成要素の数は、しきい値を越える特異値の数に基づいて決定される。制御はさらにステップＳ１３０へと続き、プロセスは終了する。
【００８２】
図５は本発明による具体例としての類似性マトリックスデータ構造を示す。情報ストリーム４００に含まれる情報はウィンドウ処理され且つパラメータ化される。例えば、情報ストリーム４００はウィンドウ処理され、パラメータベクトルｉ及びｊにパラメータ化される。各パラメータベクトルの値は、類似値が類似の輝度を有するように任意選択的に減少又は正規化される。本発明による他の具体例としての種々の実施の形態において、類似性マトリックスの視覚化は、決定した類似性マトリックスの明暗の各部分を決定することによって、順序付け情報ストリームの各部分間の類似度を決定するために使用されることもある。
【００８３】
図６は本発明の一つの実施の形態による具体例としての類似性マトリックス５００を示している。類似性マトリックス５００は、具体例としての情報ストリーム［７，８，８，８，９，９，８，８］に基づく。具体例としての類似性マトリックス５００の値は、一例としての類似性の測定Ｓ（ｉ，ｊ）＝ｄ（Ｓi，Ｓj）＝２−｜Ｓi−Ｓj｜に基づいて決定される。例えば、類似性マトリックス５００の第１の行５１０は以下のように決定される。
Ｓ（１，１）＝２−｜７−７｜＝２
Ｓ（１，２）＝２−｜８−７｜＝１
Ｓ（１，３）＝２−｜８−７｜＝１
Ｓ（１，４）＝２−｜８−７｜＝１
Ｓ（１，５）＝２−｜９−７｜＝０
Ｓ（１，６）＝２−｜９−７｜＝０
Ｓ（１，７）＝２−｜８−７｜＝１
Ｓ（１，８）＝２−｜８−７｜＝１
このようにして、類似性マトリックス５００の第１の行５１０は決定される。類似性マトリックス５００のそれ以降の行は同様にして決定される。
【００８４】
図７は本発明による一例としての固有ベクトルｓのグラフである。このグラフは、類似性ストリーム［７，８，８，８，９，９，８，８］の固有ベクトルを示す。最大固有値は、７、８及び９の値をもつストリームの主要構成要素に対応するそれぞれの重みとして、λ1＝１１．８、λ2＝３．１、λ3＝１．１を有する。それぞれ長さが８の３つの固有ベクトルは、類似性マトリックスの構造と、順序付け情報ストリーム内の決定された主要構成要素の分布を決定するために使用される。固有ベクトルν3、要素６３０は第１の要素でのみ最大である。これは正確には、情報ストリームの第１の要素である長さ１のセグメント［７］、最短の構成要素、及び最小の非ゼロ固有値に対応する。二番目に大きい固有値λ2は、要素５及び６で最大になる要素６２０、ν2によって指示される構成成分に対応する。これは正確には、元のシーケンスにおけるセグメント［９，９］に対応する。最大固有値λ1は固有ベクトルν1に対応し、要素６１０は情報ストリームの最長構成要素、即ち、８から成る２つのセグメントに対応付けられる。同図に見られるように、ν1、要素６１０は、元のシーケンスにおいて位置２、３、４及び７、８すなわち正確には８の位置で最大になる。このように、主要固有値の数は、構成要素セグメントの数を表示し、対応する固有ベクトルｓはセグメントを表示する。
【００８５】
上記で概説された具体例としての種々の実施の形態において、自動セグメント化及びクラスタ化システム１００は、プログラム式汎用コンピュータを用いて実施可能である。しかしながら、この自動セグメント化及びクラスタ化システム１００は、特殊コンピュータ、プログラム式マイクロプロセッサ又はマイクロコントローラ及び周辺集積回路要素、ＡＳＩＣ若しくは他の集積回路、ディジタル信号プロセッサ、離散素子回路等の配線電子又は論理回路、ＰＬＤ、ＰＬＡ、ＦＰＧＡ若しくはＰＡＬ等のプログラマブル論理デバイス等を用いて実施することも可能である。一般に、図３及び図４に示されるフローチャートを実行可能な有限状態マシンを実施することのできる何れかのデバイスを用いて自動セグメント化及びクラスタ化システム１００を実施することができる。
【００８６】
上記で概説された自動セグメント化及びクラスタ化システム１００の回路１０２乃至１２４はそれぞれ、適切にプログラムされた汎用コンピュータの各部分として実施可能である。あるいはまた、自動セグメント化及びクラスタ化システム１００の回路１０２乃至１２４はＡＳＩＣ内部の物理的に識別可能なハードウェア回路として、又は、ＦＰＧＡ、ＰＤＬ、ＰＬＡ若しくはＰＡＬや、離散的論理要素若しくは離散的回路要素を用いて実施することができる。自動セグメント化及びクラスタ化システム１００のこれら回路１０２乃至１２４のそれぞれ特定の形状は、設計上の選択があり、当業者には明白且つ当然予測できるであろう。
【００８７】
さらに、自動セグメント化及びクラスタ化システム１００及び／又は上記で論じられた種々の回路はそれぞれ、ソフトウェアルーチン、プログラム式汎用コンピュータ上で実行するマネジャー又はオブジェクト、特殊コンピュータ、マイクロプロセッサ等として実施可能である。この場合、自動セグメント化及びクラスタ化システム１００及び／又は上記で論じられた種々の回路はそれぞれ、通信ネットワークに組み込まれた１つ以上のルーチン、サーバー上に存在する資源等として実施可能である。自動セグメント化及びクラスタ化システム１００及び上記で論じられた種々の回路はそれぞれ、自動セグメント化及びクラスタ化システム１００をウェブサーバのハードウェア及びソフトウェアシステム等のソフトウェア及び／又はハードウェアシステムに物理的に組み込むことによって実施可能である。
【００８８】
図２に示すように、メモリ１０４、マトリックス記憶装置１１０、及びしきい値記憶装置１１６は、可変揮発性若しくは不揮発性メモリ、又は非可変若しくは固定メモリの適切な組み合わせを用いて実施することができる。揮発性又は不揮発性であるこの可変メモリは、１つ以上のスタティック又はダイナミックＲＡＭ、フロッピー（登録商標）ディスク及びディスクドライブ、書き込み可能若しくは書き換え可能な光学ディスク及びディスクドライブ、ハードドライブ、フラッシュメモリ等を用いて実施可能である。同様に、非可変又は固定メモリは、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭ若しくはＤＶＤ−ＲＯＭディクス等の光学ＲＯＭディスク、及びディスクドライブ等の少なくとも１つを用いて実施可能である。
【００８９】
図１及び図２に示される通信リンク２１０は、直接回線接続、ワイドエリアネットワーク若しくはローカルエリアネットワーク上の接続、イントラネット上の接続、インターネット上の接続、又は他の分散された処理ネットワーク若しくはシステム上の接続を含む、通信装置を自動セグメント化及びクラスタ化システム１００に接続するための周知の若しくは後日開発される装置又はシステムである。一般に、通信リンク２１０は、装置を接続し通信を容易にするのに使用できる周知の若しくは後日開発される接続システム又は構造であってよい。
【００９０】
さらに、通信リンク２１０がネットワークに対して有線又は無線リンクでもよいことを理解すべきである。このネットワークは、ローカルエリアネットワーク、ワイドエリアネットワーク、イントラネット、インターネット、又は他の分散された処理／記憶ネットワークであってよい。
【００９１】
本発明を上記に概説された具体例としての実施の形態に関連して述べてきたが、多くの代替方法、変形、及び変更が当業者には明白であることは確かである。したがって、本発明の具体例としての実施の形態は、上記に示したように図示を意図するためであり、限定するものではない。本発明の精神及び範囲から逸脱することなく種々の変更が可能である。
【００９２】
【発明の効果】
本発明は上記のように構成されているので、順序付けられた情報の自動セグメント化及びクラスタ化を提供することにより、例えば、ビデオワークの主要なシーン等の重要な構成要素が自動的に決定されて、ビデオワークの編集を完成させるために必要な時間と専門知識が軽減されるという効果を有する。
【図面の簡単な説明】
【図１】本発明による具体例としての自動セグメント化及びクラスタ化システムの概略図である。
【図２】本発明による具体例としての自動セグメント化及びクラスタ化システムを示す図である。
【図３】本発明による具体例としての自動セグメント化及びクラスタ化方法の前半部分を示すフローチャートである。
【図４】本発明による具体例としての自動セグメント化及びクラスタ化方法の後半部分を示すフローチャートである。
【図５】本発明の第１の実施の形態による類似性マトリックスデータ構造を示す図である。
【図６】本発明の第２の実施の形態による類似性マトリックスを示す図である。
【図７】本発明の実施の形態による具体例としての固有ベクトルのグラフである。
【符号の説明】
１００    自動セグメント化及びクラスタ化システム
１０２    コントローラ
１０４    メモリ
１０６    パラメータ化回路
１０８    データ圧縮回路
１１０    マトリックス記憶メモリ
１１２    類似性マトリックス決定回路
１１４    直交マトリックス分解回路
１１６    しきい値記憶メモリ
１１８    特異ベクトル決定回路
１２０    主要構成要素境界決定回路
１２２    インジケータベクトル決定回路
１２４    入出力回路
【図１】
0004254160.tif 000006
【図２】
0004254160.tif 000007
【図３】
0004254160.tif 000008
【図４】
0004254160.tif 000009
【図５】
0004254160.tif 000010
【図６】
0004254160.tif 000011
【図７】
0004254160.tif 000012