(57)【要約】【課題】  類似度マトリックスの基底ベクトルを識別するために類似度マトリックスの確率論的因数分解を使用するシステムと方法とを提供する。【解決手段】  例えばオーディオ、ビデオおよび／またはテキスト・データといった順序付けられた情報のストリームは、ウィンドウ化しパラメータ化する。順序付けられた情報のパラメータ化されウィンドウ化されたストリーム間の類似度が決定でき、この類似度マトリックスに、非ネガティブ・マトリックス因数分解といった確率論的分解または確率論的マトリックス因数分解が適用できる。この分解の結果得られる成分マトリックスは、順序付き情報の主要成分またはセグメントを示す。そして、順序付き情報のストリームの要約を生成するためにこれらの成分マトリックスに基づいて順序付き情報のストリームから抄録が抽出できる。【選択図】  図６
2005174333.tif 000002
【特許請求の範囲】
【請求項１】
順序付けられた情報のストリームに関する類似度マトリックスを生成するステップと、
確率論的マトリックス因数分解に基づいて前記類似度マトリックスを複数の成分マトリックスに分解するステップと、
各成分マトリックスに対して、前記順序付けられた情報のストリームの代表的部分を決定するステップと、
前記決定された代表的部分を抽出するステップと、
前記抽出された代表的部分を前記順序付けられた情報のストリームの要約に結合するステップと、からなることを特徴とする、順序付けられた情報のストリームを要約する方法。
【請求項２】
前記順序付けられた情報のストリームはビデオ情報とオーディオ情報と静止画像情報とテキスト情報のうちの少なくとも一つを含むことを特徴とする、請求項１に記載の方法。
【請求項３】
前記順序付けられた情報のストリームは少なくともビデオ情報とオーディオ情報と静止画像情報とテキスト情報とのうちの複数を含むことを特徴とする、請求項１に記載の方法。
【請求項４】
前記順序付けられた情報のストリームに関して前記類似度マトリックスを生成するステップは、
前記順序付けられた情報のストリームをウィンドウ化するステップと、
前記順序付けられた情報のウィンドウ化ストリームをパラメータ化するステップと、
前記順序付けられた情報のパラメータ化されたウィンドウ化ストリームの前記類似度マトリックスを決定するステップとを含むことを特徴とする、請求項１に記載の方法。
【請求項５】
前記順序付けられた情報のストリームは少なくともオーディオ情報を含んでおり、また前記順序付けられた情報のストリームをパラメータ化するステップは、ＳＴＦＴフーリエ変換とメル周波数ケプストラム係数分析とスペクトル写真と高速フーリエ変換とウェーブレット分解とのうちの少なくとも一つに基づいて前記順序付けられたオーディオ情報のストリームをパラメータ化するステップを含むことを特徴とする、請求項４に記載の方法。
【請求項６】
前記順序付けられた情報のストリームは少なくともビデオ情報を含んでおり、また前記順序付けられた情報のストリームをパラメータ化するステップはヒストグラムと正規直交射影と圧縮マクロブロックのＤＣ係数からのデシメートされた画像の導出と離散余弦変換とのうちの少なくとも一つに基づいて前記順序付けられたビデオ情報のストリームをパラメータ化するステップを含むことを特徴とする、請求項４に記載の方法。
【請求項７】
前記順序付けられた情報のストリームは少なくともテキスト情報を含んでおり、また前記順序付けられた情報のストリームをパラメータ化するステップはセンテンス（文）とパラグラフ（段落）とメタデータ情報と項頻度・反転文書頻度情報とスピーチ情報の一部とのうちの少なくとも一つに基づいて前記順序付けられたテキスト情報のストリームをパラメータ化するステップを含むことを特徴とする、請求項４に記載の方法。
【請求項８】
ある関数に基づいて前記順序付けられた情報の成分マトリックスの数を決定する前記ステップを更に含むことを特徴とする、請求項１に記載の方法。
【請求項９】
ある関数に基づいて前記順序付けられた情報の成分マトリックスの数を決定するステップは前記順序付けられた情報に関する類似度マトリックスの確率論的因数分解ランクに基づいて前記順序付けられた情報の成分マトリックスの数を決定するステップを含むことを特徴とする、請求項８に記載の方法。
【請求項１０】
確率論的マトリックス因数分解に基づいて前記類似度マトリックスを前記複数の成分マトリックスに分解する前記ステップは、
2005174333.tif 000024
および
2005174333.tif 000025
であるように類似度マトリックスＳを複数の成分マトリックスＡkに分解するステップを含んでおり、ここで、
Ｗ（ｉ，ｋ）はＮ×Ｋマトリックスであり、
Ｈ（ｋ，ｊ）はＫ×Ｎマトリックスであり、
Ｎは前記順序付けられた情報のストリームの分離可能部分の数であり、
Ｋは基底ベクトルの数であり、
ｋは整数である、
ことを特徴とする、請求項１に記載の方法。
【請求項１１】
各成分マトリックスに対して前記順序付けられた情報のストリームの代表的部分を決定する前記ステップは、各成分マトリックスに対して、その成分マトリックスに対応する前記順序付け情報のストリームの１つのサブパートからの複数の候補抄録の各々のためにその候補抄録がどれほど代表的であるかの度合いを決定するステップを含むことを特徴とする、請求項１０に記載の方法。
【請求項１２】
候補抄録がどれほど代表的であるかの前記度合いを決定する前記ステップはその候補抄録に関する平均クラス内マトリックスＡ*k（ｑ，ｒ）を決定するステップを含むことを特徴とする、請求項１１に記載の方法。
【請求項１３】
候補抄録に関する前記平均クラス内マトリックスＡ*k（ｑ，ｒ）を決定する前記ステップは、
2005174333.tif 000026
のように、Ａ*k（ｑ，ｒ）を決定するステップを含んでおり、ここで、
Ｎは順序付けられた情報のストリームの対応するサブパートの分離可能部分の数であり、
ｒは前記抄録の終了部分であり、
ｑは前記抄録の開始部分であることを特徴とする、請求項１２に記載の方法。
【請求項１４】
成分マトリックスに対応する前記順序付けられた情報のストリームのサブパートからの前記複数の候補抄録に関してその候補抄録がどれほど代表的であるかの度合いを決定する前記ステップは、すべての可能な開始点ｒを有する抄録に関する前記平均クラス内成分マトリックスＡ*k（ｑ，ｒ）を決定するステップを含むことを特徴とする、請求項１３に記載の方法。
【請求項１５】
成分マトリックスに対応する前記順序付けられた情報のストリームのサブパートからの前記複数の候補抄録に関してその候補抄録がどれほど代表的であるかの度合いを決定する前記ステップは、各々の抄録が開始点ｒと終了点ｑとの間に一定の長さＬを有する、すべての可能な開始点ｒを有する抄録に関する前記平均クラス内成分マトリックスＡ*k（ｑ，ｒ）を決定するステップを含むことを特徴とする、請求項１４に記載の方法。
【請求項１６】
成分マトリックスに対応する前記順序付けられた情報のストリームのサブパートからの前記複数の候補抄録に関してその候補抄録がどれほど代表的であるかの度合いを決定する前記ステップは、すべての可能な終了点ｑを有する抄録に関する前記平均クラス内成分マトリックスＡ*k（ｑ，ｒ）を決定するステップを含むことを特徴とする、請求項１４に記載の方法。
【請求項１７】
成分マトリックスに対応する前記順序付けられた情報のストリームのサブパートからの前記複数の候補抄録に関してその候補抄録がどれほど代表的であるかの度合いを決定する前記ステップは、成分ｋに関して長さｌkを有する抄録に関する前記平均クラス内成分マトリックスＡ*k（ｑ，ｒ）を決定するステップを含んでおり、前記長さｌkは
2005174333.tif 000027
のように、決定され、ここでＬTは結合された抄録に関する全長であることを特徴とする、請求項１４に記載の方法。
【請求項１８】
候補抄録がどれほど代表的であるかの前記度合いを決定する前記ステップは、所定の成分マトリックスＡkに関して、ｋth成分のｉth開始位置に関するスコアＱL(k)（ｉ）を
2005174333.tif 000028
のように、決定するステップを含んでおり、ここで、
Ｎは前記順序付けられた情報のストリームの対応するサブパートの分離可能部分の数であり、
ｉは前記抄録の開始部分であり、
Ｌは前記抄録の長さであることを特徴とする、請求項１１に記載の方法。
【請求項１９】
ｋth成分のｉth開始位置に関するスコアＱL(k)（ｉ）を決定する前記ステップはｋth成分から抽出される抄録に関する開始点ｑL(k)を決定するステップを含むことを特徴とする、請求項１８に記載の方法。
【請求項２０】
ｋth成分から抽出される抄録に関する開始点ｑL(k)を決定する前記ステップはｋth成分に関するスコアＱL(k)を最大にする開始点ｑL(k)を見出すステップを含むことを特徴とする、請求項１９に記載の方法。
【請求項２１】
確率的マトリックス因数分解に基づいて前記類似度マトリックスを前記複数の成分マトリックスに分解する前記ステップは、前記類似度マトリックスを、非ネガティブ・マトリックス因数分解を使用して前記複数の成分マトリックスに分解するステップを含むことを特徴とする、請求項１に記載の方法。
【請求項２２】
前記類似度マトリックスを、非ネガティブ・マトリックス因数分解を使用して前記複数の成分マトリックスに分解する前記ステップは、
2005174333.tif 000029
のように、表される類似度マトリックスＳを
2005174333.tif 000030
のように、表される複数の成分マトリックスＡkに分解するステップを含んでおり、ここで、
Ｗ（ｉ，ｋ）はＮ×Ｋマトリックスであり、
Ｈ（ｋ，ｊ）はＫ×Ｎマトリックスであり、
Ｎは順序付けられた情報のストリームの分離可能部分の数であり、
Ｋは基底ベクトルの数であり、
ｋは整数である、ことを特徴とする、請求項２１に記載の方法。
【請求項２３】
順序付けられた情報のストリームに関して前記類似度マトリックスを生成する前記ステップは、
2005174333.tif 000031
および
2005174333.tif 000032
であるような類似度マトリックスＳを生成するステップを含んでおり、ここでＳｂは前記類似度マトリックスＳの一次近似であることを特徴とする、請求項２２に記載の方法。
【請求項２４】
順序付けられた情報のストリームに関して前記類似度マトリックスを生成する前記ステップは、前記類似度マトリックスＳにおける各位置（ｉ，ｊ）に関して
2005174333.tif 000033
のように、表される類似値Ｓ（ｉ，ｊ）を決定するステップを更に含んでおり、ここで、
ｖiとｖjは順序付けられた情報の前記ストリームのｉthとｊth部分とに関して前記順序付けられた情報のストリームから生成されたパラメータ・ベクトルであり、
ｄcはパラメータ・ベクトルｖi、ｖj間の余弦角であることを特徴とする、請求項２３に記載の方法。
【請求項２５】
データ処理装置上で実行可能であって順序付けられた情報のストリームの要約処理を実行するプログラムであって、前記処理は、
メモリに記憶された前記順序付けられた情報のストリームを読み出し、該ストリームに関する類似度マトリックスを生成するステップと、
確率論的マトリックス因数分解に基づいて前記類似度マトリックスを複数の成分マトリックスに分解するステップと、
各成分マトリックスに関して前記順序付けられた情報のストリームの代表的部分を決定するステップと、
前記決定された代表的部分を抽出するステップと、
前記抽出された代表的部分を前記順序付けられた情報のストリームの要約に結合するステップと、からなることを特徴とするプログラム。
【請求項２６】
前記順序付けられた情報のストリームはビデオ情報とオーディオ情報と静止画像情報とテキスト情報のうちの少なくとも一つを含むことを特徴とする、請求項２５に記載のプログラム。
【請求項２７】
前記順序付けられた情報のストリームは少なくともビデオ情報とオーディオ情報と静止画像情報とテキスト情報のうちの複数を含むことを特徴とする、請求項２５に記載のプログラム。
【請求項２８】
前記順序付けられた情報のストリームに関する前記類似度マトリックスを生成するための前記ステップは前記順序付けられた情報のストリームをウィンドウ化するためのステップと、
前記順序付けられた情報のウィンドウ化ストリームをパラメータ化するためのステップと、
前記順序付けられた情報のパラメータ化されたウィンドウ化ストリームの前記類似度マトリックスを決定するためのステップと、を含むことを特徴とする、請求項２５に記載のプログラム。
【請求項２９】
前記順序付けられた情報のストリームは少なくともオーディオ情報を含んでおり、また前記順序付けられた情報のストリームをパラメータ化するためのステップはＳＴＦＴフーリエ変換とメル周波数ケプストラム係数分析とスペクトル写真と高速フーリエ変換とウェーブレット分解とのうちの少なくとも一つに基づいて前記順序付けられたオーディオ情報のストリームをパラメータ化するためのステップを含むことを特徴とする、請求項２８に記載のプログラム。
【請求項３０】
前記順序付けられた情報のストリームは少なくともビデオ情報を含んでおり、また前記順序付けられた情報のストリームをパラメータ化するための前記ステップはヒストグラムと正規直交射影と圧縮マクロブロックのＤＣ係数からのデシメートされた画像の導出と離散余弦変換とのうちの少なくとも一つに基づいて前記順序付けられたビデオ情報のストリームをパラメータ化するステップを含むことを特徴とする、請求項２８に記載のプログラム。
【請求項３１】
前記順序付けられた情報のストリームは少なくともテキスト情報を含んでおり、また前記順序付けられた情報のストリームをパラメータ化するためのステップはセンテンスとパラグラフとメタデータ情報と項頻度・反転文書頻度情報とスピーチ情報の一部とのうちの少なくとも一つに基づいて前記順序付けられたテキスト情報のストリームをパラメータ化するためのステップを含むことを特徴とする、請求項２８に記載のプログラム。
【請求項３２】
ある関数に基づいて前記順序付けられた情報の成分マトリックスの数を決定するためのステップを更に含むことを特徴とする、請求項２５に記載のプログラム。
【請求項３３】
ある関数に基づいて前記順序付けられた情報の成分マトリックスの数を決定するための前記ステップは前記順序付けられた情報に関する類似度マトリックスの確率論的因数分解ランクに基づいて前記順序付けられた情報の成分マトリックスの数を決定するためのステップを含むことを特徴とする、請求項３２に記載のプログラム。
【請求項３４】
確率論的マトリックス因数分解に基づいて前記類似度マトリックスを前記複数の成分マトリックスに分解するための前記ステップは
2005174333.tif 000034
のように表される類似度マトリックスＳを
2005174333.tif 000035
のように表される複数の成分マトリックスＡkに分解するためのステップを含んでおり、ここで、
Ｗ（ｉ，ｋ）はＮ×Ｋマトリックスであり、
Ｈ（ｋ，ｊ）はＫ×Ｎマトリックスであり、
Ｎは順序付けられた情報のストリームの分離可能部分の数であり、
Ｋは基底ベクトルの数であり、
ｋは整数である、
ことを特徴とする、請求項２５に記載のプログラム。
【請求項３５】
各成分マトリックスに関して前記順序付けられた情報のストリームの代表的部分を決定するための前記ステップは、各成分マトリックスに関して、その成分マトリックスに対応する前記順序付けられた情報のストリームの１サブパート（１小部分）からの複数の候補抄録の各々のためにその候補抄録がどれほど代表的であるかの度合いを決定するためのステップを含むことを特徴とする、請求項３４に記載のプログラム。
【請求項３６】
候補抄録がどれほど代表的であるかの前記度合いを決定するための前記ステップはその候補抄録に関する平均クラス内マトリックスＡ*k（ｑ，ｒ）を決定するためのステップを含むことを特徴とする、請求項３５に記載のプログラム。
【請求項３７】
候補抄録に関する前記平均クラス内マトリックスＡ*k（ｑ，ｒ）を決定するための前記ステップは
2005174333.tif 000036
のように、Ａ*k（ｑ，ｒ）を決定するためのステップを含んでおり、ここで、
Ｎは前記順序付けられた情報のストリームの対応するサブパートの分離可能部分の数であり、
ｒは前記抄録の終了部分であり、
ｑは前記抄録の開始部分であることを特徴とする、請求項３６に記載のプログラム。
【請求項３８】
成分マトリックスに対応する前記順序付けられた情報のストリームのサブパートからの前記複数の候補抄録に関してその候補抄録がどれほど代表的であるかの度合いを決定するための前記ステップは、すべての可能な開始点ｒを有する抄録に関する前記平均クラス内成分マトリックスＡ*k（ｑ，ｒ）を決定するためのステップを含むことを特徴とする、請求項３７に記載のプログラム。
【請求項３９】
成分マトリックスに対応する前記順序付けられた情報のストリームのサブパートからの前記複数の候補抄録に関してその候補抄録がどれほど代表的であるかの度合いを決定するための前記ステップは、各々の抄録が開始点ｒと終了点ｑとの間に一定の長さＬを有する、すべての可能な開始点ｒを有する抄録に関する前記平均クラス内成分マトリックスＡ*k（ｑ，ｒ）を決定するためのステップを含むことを特徴とする、請求項３８に記載のプログラム。
【請求項４０】
成分マトリックスに対応する前記順序付けられた情報のストリームのサブパートからの前記複数の候補抄録に関してその候補抄録がどれほど代表的であるかの度合いを決定するための前記ステップは、すべての可能な終了点ｑを有する抄録に関する前記平均クラス内成分マトリックスＡ*k（ｑ，ｒ）を決定するためのステップを含むことを特徴とする、請求項３９に記載のプログラム。
【請求項４１】
成分マトリックスに対応する前記順序付けられた情報のストリームのサブパートからの前記複数の候補抄録に関してその候補抄録がどれほど代表的であるかの度合いを決定するための前記ステップは、その成分ｋに関して長さｌkを有する抄録に関する前記平均クラス内成分マトリックスＡ*k（ｑ，ｒ）を決定するためのステップを含んでおり、ここで前記長さｌkは
2005174333.tif 000037
のように、決定され、ＬTは結合された抄録に関する全長であることを特徴とする、請求項３８に記載のプログラム。
【請求項４２】
その候補抄録がどれほど代表的であるかの前記度合いを決定するための前記ステップは、所定の成分マトリックスＡkに関して、ｋth成分のｉth開始位置に関するスコアＱL(k)（ｉ）を
2005174333.tif 000038
のように、決定するためのステップを含んでおり、ここで、
Ｎは前記順序付けられた情報のストリームの対応するサブパートの分離可能部分の数であり、
ｉは前記抄録の開始部分であり、
Ｌは前記抄録の長さであることを特徴とする、請求項３５に記載のプログラム。
【請求項４３】
ｋth成分のｉth開始位置に関するスコアＱL(k)（ｉ）を決定するための前記ステップはｋth成分から抽出される抄録に関する開始点ｑL(k)を決定するためのステップを含むことを特徴とする、請求項４２に記載のプログラム。
【請求項４４】
ｋth成分から抽出される抄録に関する開始点ｑL(k)を決定するための前記ステップはｋth成分に関するスコアＱL(k)を最大にする開始点ｑL(k)を見出すためのステップを含むことを特徴とする、請求項４３に記載のプログラム。
【請求項４５】
確率論的マトリックス因数分解に基づいて前記類似度マトリックスを前記複数の成分マトリックスに分解するための前記ステップは前記類似度マトリックスを、非ネガティブ・マトリックス因数分解を使用して前記複数の成分マトリックスに分解するためのステップを含むことを特徴とする、請求項２５に記載のプログラム。
【請求項４６】
前記類似度マトリックスを、非ネガティブ・マトリックス因数分解を使用して前記複数の成分マトリックスに分解するための前記ステップは、非ネガティブ・マトリックス因数分解を使用して
2005174333.tif 000039
のように表される類似度マトリックスＳを
2005174333.tif 000040
のように表される複数の成分マトリックスＡkに分解するステップを含んでおり、ここで、
Ｗ（ｉ，ｋ）はＮ×Ｋマトリックスであり、
Ｈ（ｋ，ｊ）はＫ×Ｎマトリックスであり、
Ｎは前記順序付けられた情報のストリームの分離可能部分の数であり、
Ｋは基底ベクトルの数であり、
ｋは整数である、ことを特徴とする、請求項４５に記載のプログラム。
【請求項４７】
前記順序付けられた情報のストリームに関する前記類似度マトリックスを生成するための前記ステップは、
2005174333.tif 000041
および
2005174333.tif 000042
であるような類似度マトリックスＳを生成するためのステップを含んでおり、ここで、Ｓｂは前記類似度マトリックスＳの一次近似である、ことを特徴とする、請求項４６に記載のプログラム。
【請求項４８】
前記順序付けられた情報のストリームに関する前記類似度マトリックスを生成するための前記ステップは、前記類似度マトリックスＳにおける各位置（ｉ，ｊ）に関する
2005174333.tif 000043
のように、表される類似値Ｓ（ｉ，ｊ）を決定するためのステップを含んでおり、ここで、
ｖiとｖjは順序付けられた情報の前記ストリームのｉth部分とｊth部分とに関して前記順序付けられた情報のストリームから生成されるパラメータ・ベクトルであり、
ｄcはパラメータ・ベクトルｖi、ｖj間の余弦角である、ことを特徴とする、請求項４７に記載のプログラム。
【請求項４９】
順序付けられた情報のストリームの二つの部分の間の類似度を決定し、その決定された類似度を類似度マトリックスに格納する類似度マトリックス決定回路、ルーチンまたはアプリケーションと、
確率論的マトリックス因数分解に基づいて前記類似度マトリックスを複数の成分マトリックスに分解する確率論的分解回路、ルーチンまたはアプリケーションと、
各成分マトリックスに関して前記順序付けられた情報のストリームの代表的部分を決定する抄録決定回路、ルーチンまたはアプリケーションと、
前記決定された代表的部分を抽出する抄録抽出回路、ルーチンまたはアプリケーションと、
前記抽出された代表的部分を前記順序付けられた情報のストリームの要約に結合する要約生成回路、ルーチンまたはアプリケーションと、を含むことを特徴とする、順序付けられた情報のストリームを要約するシステム。
【請求項５０】
前記順序付けられた情報のストリームをウィンドウ化するウィンドウ化回路、ルーチンまたはアプリケーションと、
前記順序付けられた情報のウィンドウ化されたストリームをパラメータ化するパラメータ化回路、ルーチンまたはアプリケーションと、を更に含んでおり、
前記類似度マトリックス決定回路、ルーチンまたはアプリケーションは前記順序付けられた情報のウィンドウ化され、パラメータ化されたストリームの二つの部分の間の類似度を決定することを特徴とする、請求項４９に記載の、順序付けられた情報のストリームを要約するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全ストリームの構造文字を代表するメディア・ストリームの要約を生成するためのシステムと方法とに関する。
【背景技術】
【０００２】
メディア要約技術は、電子商取引（Ｅコマース）と情報検索とにおいて非常に多くのアプリケーションを持っている。このような多数のアプリケーションは、大きなファイルサイズとマルチメディアデータの高い帯域要求とのために、長い作品の要約および／または代替物を使用している。メディア作品の要約は、ある仕方で典型的には長い作品の良好な代表である一つ以上のセグメントを抄録することによって短縮される。長い作品の良好な代表であるセグメントを識別するためには、メディア・ストリームの構造が決定されなくてはならない。
【０００３】
その全体が引用によってここに組み入れられている特許文献１は、３個のステップを含むメディア・ストリームの構造を評価するための方法を開示している。第１のステップで、メディア・ストリームの単一フレームか短い時間単位のいずれかである各ウィンドウは、そのウィンドウに関する特徴ベクトルを計算することによってパラメータ化される。第２のステップで、ウィンドウ特徴ベクトルに基づいてすべてのウィンドウのペアに関して類似度が決定される。これら類似度は、分析のために類似度マトリックスに埋め込まれる。第３のステップで、この類似度マトリックスは、メディア・ストリームの主要構造成分を決定するために特異値分解（Ｓｉｎｇｕｌａｒ  Ｖａｌｕｅ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ：ＳＶＤ）を使用して因数分解される。セグメント境界と類似セグメントのクラスタとを決定するために主要構造成分または基底ベクトルが処理される。
【０００４】
いったん主要構造セグメントと構造セグメントのクラスタとが識別されると、各抄録（抜粋）に関してその抄録の、対応するセグメント・クラスタの他のメンバーに対する類似度を最大にすることによって、各構造セグメント・クラスタを表すように単一の抄録が識別され得る。このメディアの有意に異なるセグメントの各々に関する抄録は生成されるが、同一クラスタ内の類似構造セグメントに関する冗長な抄録は削除される。
【０００５】
その全体が引用によってここに組み入れられている特許文献２は、類似性分析を使用して長いメディア源の要約抄録を選択するための方法を開示している。この方法では類似度マトリックスは、組み入れられている特許文献１の初めの二つのステップに概説したように生成される。その後、類似度マトリックスは、全ソース・ストリームに対する最大類似度を有する抄録を決定するように処理される。
【特許文献１】米国特許公開第２００３／００４８９４６号
【特許文献２】米国特許公開第２００３／０１６１３９６号
【非特許文献１】「知的マルチメディア情報検索（Ｉｎｔｅｌｌｉｇｅｎｔ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ）」エーエーエー・プレス（ＡＡＡ  Ｐｒｅｓｓ），エムアイティー・プレス（ＭＩＴ  Ｐｒｅｓ），１９９７年、のツハング（Ｚｈａｎｇ）等著「ビデオの構文解析、検索およびブラウジング：統合化された内容ベースの解（Ｖｉｄｅｏ  Ｐａｒｓｉｎｇ，  Ｒｅｔｒｉｅｖａｌ  ａｎｄ  Ｂｒｏｗｓｉｎｇ：  ａｎ  Ｉｎｔｅｇｒａｔｅｄ  ａｎｄ  Ｃｏｎｔｅｎｔ−Ｂａｓｅｄ  Ｓｏｌｕｔｉｏｎ）」
【非特許文献２】ギルゲンソーン（Ｇｉｒｇｅｎｓｏｈｎ）等著「変換係数を使用したビデオの分類（Ｖｉｄｅｏ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  Ｕｓｉｎｇ  Ｔｒａｎｓｆｏｒｍ  Ｃｏｅｆｆｉｃｉｅｎｔ）」アリゾナ州フェニックス，ＩＥＥＥ，Ｐｒｏｃ  ＩＣＡＳＳＰ、’９９Ｖｏｌ．６予稿集，１９９９年，ｐ．３０４５〜３０４８
【非特許文献３】エム・ベリー（Ｍ．Ｂｅｒｒｙ）等著「知的情報検索のための線形代数の使用（Ｕｓｉｎｇ  Ｌｉｎｅａｒ  Ａｌｇｅｂｒａ  ｆｏｒ  Ｉｎｔｅｌｌｉｇｅｎｔ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ）」エスアイエーエム・レビュー（ＳＩＡＭ  Ｒｅｖｉｅｗ）、３７（４），１９９５年，ｐ．５７３〜５９５
【非特許文献４】ディー・リー（Ｄ．Ｌｅｅ）等著「非ネガティブ・マトリックス因数分解によるオブジェクトの部分の学習（Ｌｅａｒｎｉｎｇ  ｔｈｅ  ｐａｒｔｓ  ｏｆ  ｏｂｊｅｃｔｓ  ｂｙ  ｎｏｎ−ｎｅｇａｔｉｖｅ  ｍａｔｒｉｘ  ｆａｃｔｏｒｉｚａｔｉｏｎ）」ネイチャー（Ｎａｔｕｒｅ），４０１，１９９９年，ｐ．７８８〜７９１
【非特許文献５】ティー・ホフマン（Ｔ．Ｈｏｆｆｍａｎ）著「クラスタ抽出モデル：テキスト・データからの見出し階層の非管理的学習（Ｔｈｅ  Ｃｌｕｓｔｅｒ−Ａｂｓｔｒａｃｔｉｏｎ  Ｍｏｄｅｌ：  Ｕｎｓｕｐｅｒｖｉｓｅｄ  Ｌｅａｒｎｉｎｇ  ｏｆ  Ｔｏｐｉｃ  Ｈｉｅｒａｒｃｈｉｅｓ  ｆｒｏｍ  Ｔｅｘｔ  Ｄａｔａ）」ＩＪＣＡＩ予稿集，１９９９年
【非特許文献６】ティー・ホフマン（Ｔ．Ｈｏｆｆｍａｎ）著「確率論的潜在意味分析による非管理的学習（Ｕｎｓｕｐｅｒｖｉｓｅｄ  Ｌｅａｒｎｉｎｇ  ｂｙ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｌａｔｅｎｔ  Ｓｅｍａｎｔｉｃ  Ａｎａｌｙｓｉｓ）」マシン・ラーニング（Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ）４２，２００１年，ｐ．１７７〜９６
【発明の開示】
【発明が解決しようとする課題】
【０００６】
特許文献１の特異値分解法の使用時に生成された特異基底ベクトルは、データ内のばらつきの本質的モードを表す低次元セットの直交正規化方向を与える。しかしながら特異値分解法は欠点を持っている。分析の観点から、特異基底ベクトルの識別は決定論的ではなく、また正しい構造セグメントの識別であるとの信頼ができない。
【０００７】
本発明は、類似度マトリックスの基底ベクトルを識別するために類似度マトリックスの確率論的因数分解を使用するシステムと方法とを提供する。
【０００８】
本発明はまた、類似度マトリックスの基底ベクトルを識別するために類似度マトリックスの非ネガティブ・マトリックス因数分解を使用するシステムと方法とを提供する。
【０００９】
本発明はまた、メディア・ストリームの各主要構造成分またはセグメント・クラスタを表す要約の最適長さを決定するシステムと方法とを提供する。
【００１０】
本発明はまた、メディア・ストリームの各主要構造成分またはセグメント・クラスタを表す要約の開始点を決定するシステムと方法とを提供する。
【００１１】
本発明はまた、マルチモードのメディア・ストリームを表す要約を生成するシステムと方法とを提供する。
【課題を解決するための手段】
【００１２】
本発明によるシステムと方法の種々の例示的な実施形態では、メディア・ストリームは、このメディア・ストリーム内のウィンドウまたはフレームのすべてに関して特徴ベクトルを計算することによってパラメータ化される。ウィンドウまたはフレームの各可能なペアに関して類似度が決定される。そして、これらの類似度は、類似度マトリックス内に集められる。その後、この類似度マトリックスは、メディア・ストリームの各主要構造成分または基底ベクトルを識別し、１成分ごとにその成分を表す成分マトリックスを生成するために一つ以上の確率論的方法を使用して因数分解される。特定の主要構造成分または基底ベクトルを表す成分マトリックスは、セグメント境界または類似セグメントのクラスタを決定するように処理される。
【００１３】
種々の例示的な実施形態では本発明によるシステムと方法は、各識別された主要構造成分から抄録を含む要約を生成する。これらの抄録は、各抄録の最適または適当な長さを決定し、その後、抄録内のフレームまたはウィンドウとその抄録が表す主要構造成分内のフレームまたはウィンドウとの間の類似度を増加させるか最大にする傾向のある各抄録に関して最適または適当な開始点を見出すことによって抽出されるか、さもなければ生成される。
【００１４】
種々の例示的な実施形態で本発明によるシステムと方法は、複数のモードを有するメディア・ストリームから要約を生成する。マルチモードのメディア・ストリームの要約は、各モードから生成された類似度マトリックスを結合し、そして、この結合されたマトリックスに対して確率論的因数分解を実行することによって生成される。その後、要約は、単一モードのメディア・ストリームに関して使用される方法と同じ方法を使用して各主要構造成分または基底ベクトルを表すマトリックスから生成される。
【００１５】
具体的には、本発明の第１の態様は、順序付けられた情報のストリームに関する類似度マトリックスを生成するステップと、確率論的マトリックス因数分解に基づいて前記類似度マトリックスを複数の成分マトリックスに分解するステップと、各成分マトリックスに対して、前記順序付けられた情報のストリームの代表的部分を決定するステップと、前記決定された代表的部分を抽出するステップと、前記抽出された代表的部分を前記順序付けられた情報のストリームの要約に結合するステップと、からなることを特徴とする、順序付けられた情報のストリームを要約する方法である。
【００１６】
また、本発明の第２の態様は、データ処理装置上で実行可能であって順序付けられた情報のストリームの要約処理を実行するプログラムであって、前記処理は、メモリに記憶された前記順序付けられた情報のストリームを読み出し、該ストリームに関する類似度マトリックスを生成するステップと、確率論的マトリックス因数分解に基づいて前記類似度マトリックスを複数の成分マトリックスに分解するステップと、各成分マトリックスに関して前記順序付けられた情報のストリームの代表的部分を決定するステップと、前記決定された代表的部分を抽出するステップと、前記抽出された代表的部分を前記順序付けられた情報のストリームの要約に結合するステップと、からなることを特徴とするプログラムである。
【００１７】
そして、本発明の第３の態様は、順序付けられた情報のストリームの二つの部分の間の類似度を決定し、その決定された類似度を類似度マトリックスに格納する手段である類似度マトリックス決定回路、ルーチンまたはアプリケーション（類似度マトリックス決定部）と、確率論的マトリックス因数分解に基づいて前記類似度マトリックスを複数の成分マトリックスに分解する手段である確率論的分解回路、ルーチンまたはアプリケーション（確立論的分解部）と、各成分マトリックスに関して前記順序付けられた情報のストリームの代表的部分を決定する手段である抄録決定回路、ルーチンまたはアプリケーション（抄録決定部）と、前記決定された代表的部分を抽出する手段である抄録抽出回路、ルーチンまたはアプリケーション（抄録抽出部）と、前記抽出された代表的部分を前記順序付けられた情報のストリームの要約に結合する手段である要約生成回路、ルーチンまたはアプリケーション（要約生成部）と、を含むことを特徴とする、順序付けられた情報のストリームを要約するシステムである。
【００１８】
さらに、本発明の第４の態様は、第３の態様において、前記順序付けられた情報のストリームをウィンドウ化する手段であるウィンドウ化回路、ルーチンまたはアプリケーション（ウィンドウ化部）と、前記順序付けられた情報のウィンドウ化されたストリームをパラメータ化する手段であるパラメータ化回路、ルーチンまたはアプリケーション（パラメータ化部）と、を更に含んでおり、前記類似度マトリックス決定回路、ルーチンまたはアプリケーションは前記順序付けられた情報のウィンドウ化され、パラメータ化されたストリームの二つの部分の間の類似度を決定することを特徴とする。
【００１９】
本発明のこれらおよび他の特徴と利点は、本発明によるシステムと方法の種々の例示的な実施形態についての下記の詳細な説明に記述され、あるいはこの詳細説明から明らかになろう。
【発明を実施するための最良の形態】
【００２０】
本発明によるメディア・ストリームを要約するためのシステムと方法の種々の例示的な実施形態は、例えばビデオ・ストリーム、オーディオ・ストリーム、オーディオ／ビデオ・ストリーム、テキスト文書などといった任意の既知のまたは新たに開発されるタイプのメディア・ストリームを要約するために使用可能である。下記の詳細な論議は、馴染みやすさと理解の容易さのために、種々の点でビデオ・ストリームまたはオーディオ・ストリームといった特定のタイプのメディア・ストリームを指すことがある。これは、これらのタイプのメディア・ストリームだけが本発明によるシステムと方法において適切に使用されることを意味すると理解されるべきではない。
【００２１】
本発明によるメディア要約システムと方法とに関する一つの例示的ななアプリケーションは、インターネット上で販売され配布されるビデオ・スとチームを要約することにある。この例示的ななアプリケーションではインターネット・ビデオの見込み購入者は、オーディオおよび／またはビデオ作品を購入すると決める前にその作品を概観する。ユーザは、作品の要約を要求し、これがオーディオおよび／またはビデオ作品の要約を生成するために本発明による要約システムを起動する。この要約システムは、ビデオ作品内の主要成分の各々を決定し、その決定された主要成分のサンプルに基づいて要約を生成する。
【００２２】
例えばオーディオおよび／またはビデオ作品の意外な結末といった作品のすべてを開示することを避けるために、決定された要約は、作品の冒頭、中間および／または結末における決定された主要成分のあるパーセンテージだけを反映できる。この要約システムは主要成分の境界を決定するために使用できるので、各決定された主要成分の長さが決定できて、各成分の全長のうちの適当な部分だけがその要約に含まれる。本発明によるシステムと方法の種々の例示的なな実施形態では、オーディオ／ビデオ作品を要約することは、オーディオ成分だけ、ビデオ成分だけ、および／またはオーディオとビデオ成分の両者を要約することを含むことは明らかになろう。
【００２３】
オーディオおよび／またはビデオ編集システムのユーザはまた、巧妙な切取り／貼付け機能と、決定された主要成分境界に基づく他の拡張された編集機能とを備えるために、本発明による要約システムおよび方法を使用できる。例えばビデオ編集システムのユーザは、ビデオ作品を検索する。そして、このビデオ作品は、ビデオ作品の主要成分を識別するために要約システムによって要約される。
【００２４】
その後、ビデオ作品のこれらの決定された主要成分は、主要ビデオ成分またはセグメントの境界を決定するために使用される。そして、これらの決定された主要成分またはセグメントの境界は、このビデオ作品内の決定された主要成分に関して巧妙な切取り／貼付け操作および／または他の拡張されたビデオ操作を提供するために使用される。ビデオ作品の主要シーンといった重要な成分は決定されているので、このビデオ作品の編集を遂行するために必要とされる時間と専門知識は削減される。本発明によるシステムと方法の種々の他の例示的なな実施形態では、要約システムは、ビデオ編集システム内および／または任意のアクセス可能な場所に配置できることは明らかにあろう。種々の例示的なな実施形態ではオーディオ、テキスト、または他の任意の順序付けられた情報の主要成分も同様に決定できる。
【００２５】
本発明によるシステムと方法の種々の例示的なな実施形態ではオーディオ／ビデオ情報は、ＭＰＥＧ−３、ＭＰＥＧ−４、ＭＰＥＧ−Ｊ、ＰＮＭ−ＲｅａｌＮｅｔｗｏｒｋｓプロトコル、ＲｅａｌＮｅｔｗｏｒｋｓ社のＲｅａｌＶｉｄｅｏプロトコル、マイクロソフト社のＷｉｎｄｏｗｓ（登録商標）  Ｍｅｄｉａ  ＰｌａｙｅｒのＭｉｃｒｏｓｏｆｔ  Ｍｅｄｉａ  Ｓｔｒｅａｍｉｎｇ  Ｐｒｏｔｏｃｏｌ、あるいは他の任意の既知のまたは新たに開発されるオーディオおよび／またはビデオ・プロトコルといったストリーミング・オーディオ／ビデオ・プロトコルに符号化できる。本発明によるシステムと方法の種々の例示的なな実施形態はまた、別々の復号および符号化を必要とせずに、符号化された情報ストリームまたはプロトコル内に符号化されたウィンドウ化とパラメータ化に直接アクセスするためにＭＰＥＧ−４または他の任意の符号化情報上での動作に備えている。
【００２６】
順序付けられた情報は、オーディオ、ビデオ、テキストあるいはオーディオおよび／またはビデオ情報に関する時間、テキスト情報に関する位置といった順序付け次元を有する他の任意の情報を含むことができる。
【００２７】
検索および／または受信された情報は、この検索および／または受信された情報に適用される適切なタイプのパラメータ化を決定するために分析される。例えばオーディオ情報、ビデオ情報、テキスト情報または他のタイプの順序付けられた情報には、異なるウィンドウ化とパラメータ化が適用できる。本発明による第１の例示的なな実施形態ではオーディオ波形といったオーディオ情報は、フレームにウィンドウ化され、あるいは作品内のオーディオ情報に付随するビデオ情報に関連するこれらのフレームはウィンドウとして使用される。
【００２８】
その後、このウィンドウ化されたオーディオ情報のパラメータ化が決定される。ウィンドウ化されたオーディオ情報は本発明の精神と範囲から逸脱することなく、短時間フレーム・フーリエ変換（ＳＴＦＴ）、フーリエ変換、メル周波数（Ｍｅｌ−Ｆｒｅｑｕｅｎｃｙ）ケプストラム係数分析、スペクトル写真、高速フーリエ変換（ＦＦＴ）、ウェーブレット分解、あるいは他の任意の既知のまたは新たに開発される分析手法を使用してパラメータ化できる。
【００２９】
同様にビデオおよびテキスト情報といった他の順序付けられた情報もウィンドウ化可能である。例えばビデオ情報は、ビデオ情報の個別フレームを選択することおよび／またはフレームのグループを選択することによってウィンドウ化でき、これらのフレームは互いに平均化されて平均値を決定する。テキスト情報は、単語、センテンス、パラグラフ、任意の数の単語を選択することにより、あるいはスピーチの一部、メタデータ、ＸＭＬおよび／またはＨＴＭＬ符号化、重要度、項（用語）頻度（ｔｅｒｍ  ｆｒｅｑｕｅｎｃｙ）、および／または反転文書頻度（ｉｎｖｅｒｓｅ  ｄｏｃｕｍｅｎｔ  ｆｒｅｑｕｅｎｃｙ）といった属性にもとづいて単語を選択することにより、あるいはテキストをウィンドウ化するための他の任意の既知のまたは新たに開発される手法により、ウィンドウ化またはフレーム化できる。
【００３０】
その後、この他のウィンドウ化された順序付き情報のパラメータ化が決定される。例えばビデオ情報をパラメータ化することは、引用によって全体がここに組み入れられている、非特許文献１、すなわち、「知的マルチメディア情報検索（Ｉｎｔｅｌｌｉｇｅｎｔ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ）」エーエーエー・プレス（ＡＡＡ  Ｐｒｅｓｓ），エムアイティー・プレス（ＭＩＴ  Ｐｒｅｓ），１９９７年、のツハング（Ｚｈａｎｇ）等著「ビデオの構文解析、検索およびブラウジング：統合化された内容ベースの解（Ｖｉｄｅｏ  Ｐａｒｓｉｎｇ，  Ｒｅｔｒｉｅｖａｌ  ａｎｄ  Ｂｒｏｗｓｉｎｇ：  ａｎ  Ｉｎｔｅｇｒａｔｅｄ  ａｎｄ  Ｃｏｎｔｅｎｔ−Ｂａｓｅｄ  Ｓｏｌｕｔｉｏｎ）」に開示されているようなカラー・ヒストグラムの使用を含むことができる。代替として、パラメータ化されデシメート（１／１０削減）されたビデオ情報は、圧縮マクロブロックのＤＣ係数から導出でき、離散余弦変換（ｄｉｓｃｒｅｔｅ  ｃｏｓｉｎｅ  ｔｒａｎｓｆｏｒｍ：ＤＣＴ）がこのビデオ情報に適用でき、あるいは順序付き情報のパラメータ化の他の任意の既知のまたは新たに開発される方法が使用できる。
【００３１】
パラメータ化されたデータは、パラメータ化情報のメモリ記憶要求を削減するように圧縮、さもなければ削減できる。例えば記憶要求は、全体として引用によってここに組み入れられている、非特許文献２、すなわち、ギルゲンソーン（Ｇｉｒｇｅｎｓｏｈｎ）等著「変換係数を使用したビデオの分類（Ｖｉｄｅｏ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  Ｕｓｉｎｇ  Ｔｒａｎｓｆｏｒｍ  Ｃｏｅｆｆｉｃｉｅｎｔ）」アリゾナ州フェニックス，ＩＥＥＥ，Ｐｒｏｃ  ＩＣＡＳＳＰ、’９９Ｖｏｌ．６予稿集，１９９９年，ｐ．３０４５〜３０４８、に論じられている方法のいずれによっても削減できる。代替として、元のウィンドウまたはフレームに関する顕著な情報を保存するパラメータ化情報の削減された表現を生成するために、切捨て、主要成分分析、順序付き判別子分析、あるいは他の任意の既知のまたは新たに開発されるデータ削減方法が、単独でまたは組合せて使用できる。例えばパラメータ化されたオーディオ／ビデオ情報の削減された表現は、各オーディオおよび／またはビデオ・フレームに関する削減化係数の圧縮特徴ベクトルを反映できる。削減化表現は元の順序付き情報の再生のためではなくむしろ分析のために使用されるので、この削減化表現は元の情報を復元できる必要はなく、主要成分を指示するために使用される。このようにして削減化表現は、更に削減できる。
【００３２】
類似度ｄは、
【数１】
2005174333.tif 000003
【００３３】
のように、フレームまたはウィンドウｉ、ｊに関するパラメータ化情報ベクトル(間のユークリッド距離に基づいて決定できる。
【００３４】
種々の他の例示的なな実施形態では類似度ｄは、類似度マトリックスを含むパラメータ化情報ベクトルのドット積に基づいて決定できる。例えば二つの大きな類似性ベクトルのドット積は、次式で表される。
【００３５】
【数２】
2005174333.tif 000004
【００３６】
類似度ｄは、パラメータ化情報ベクトル間の余弦角を使用して、あるいはＫｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ距離といったベクトル統計値の関数を使用して、あるいは本発明の精神または範囲を逸脱することなく情報ベクトルの類似度を決定する他の任意の既知のまたは新たに開発される方法を使用して決定できる。距離値または距離マトリックスｄは、対角線上の類似度または類似要素ｄ（ｉ，ｊ）が各測定値または要素のそれ自身に対する類似度ｄを表すような類似度マトリックスに組み入れられる。こうして自己類似度は、対角線上で最大になる。
【００３７】
各類似度または類似要素ｄ（ｉ，ｊ）の値は、最大輝度といった最大特徴値との比較に基づいて決定されたカラー情報値を割り当てられることができる。高い自己類似度を有する類似度または類似要素ｄ（ｉ，ｊ），ｉ＝ｊの各々は、対応する更に高い輝度値を持っており、対角線に沿って現れる。
【００３８】
このようにして、上記に概説したように、特許文献１に記載されたメディア要約方法では、第１のステップはメディアのパラメータ化である。特許文献１では、ビデオデータストリームに関する特徴ベクトルは、低次の離散余弦変換（ＤＣＴ）係数に基づいて計算される。個別のＲＧＢフレームは、１Ｈｚでサンプリングされ、３色チャネルがほぼ非相関化された色空間に変換される。各変換されたチャネルの離散余弦変換（ＤＣＴ）が計算されて、特徴ベクトルはこれら３個のチャネルの結果的に得られた低い周波数係数を連結することによって形成される。任意数の代替のパラメータ化方法が使用できることを認識されたい。
【００３９】
上記に概説したようにいったんメディアがパラメータ化されると、特許文献１に記載された第２のステップは、異なるフレームの特徴ベクトル間の類似度を計算して、その結果を二次元的表現に埋め込む。そのキーとなるのは、フレームｉ、ｊから計算された１対の特徴ベクトルｖi、ｖj間の類似の度合いｄである。本発明による種々の例示的なな実施形態では有用な類似距離値は、次式のような、パラメータ・ベクトル間の余弦角である。
【００４０】
【数３】
2005174333.tif 000005
この類似距離値ｄc（ｖi，ｖj）はこれらのベクトルの大きさが小さい場合でも、大きな類似度スコアを与えるという性質を持っている。
【００４１】
図１は、類似度マトリックスＳと、特異値分解を使用して生成された多数の基底ベクトルまたは基底項Ｂkとを示す。すべての可能なフレーム間の類似度を考慮するために、類似度マトリックス１１０内の各位置Ｓ（ｉ、ｊ）が次式で定義されるように、類似距離値は、図１に示す類似度マトリックス１１０内に埋め込まれる。
【００４２】
【数４】
2005174333.tif 000006
類似度マトリックス１１０のｘ軸はフレームｉを表し、ｙ軸はフレームｊを表す。スケール１１１は、類似距離値ｄc（ｖi，ｖj）を、１．４という最大スコアに関して白、ゼロというスコアに関して黒といったグレイスケールに相関させる。ｉ＝ｊを表す対角線は、１．４という最大類似距離値ｄc（ｖi，ｖj）を持ち、そして白色である。
【００４３】
図１に示す類似度マトリックス１１０では、種々のメディア・セグメント１１２、１１４、１１６、１１８が識別できる。特に類似度マトリックス１１０ではｉとｊが同じセグメント内に在る位置Ｓ（ｉ，ｊ）は、高い類似度スコアを示す。更に類似度マトリックス１１０ではセグメント１１４といった一つのセグメント内にフレームｉが存在し、セグメント１１８といった他のセグメント内にフレームｊが存在する位置Ｓ（ｉ，ｊ）もまた高い類似度スコアを示す。これは、セグメント１１４、１１８が一つのクラスタを形成しており、類似度マトリックス１１０に対応するメディアの単一の基底ベクトルまたは構造成分として取り扱い得ることを示している。
【００４４】
上記に概説したように特許文献１に記載されたメディア要約方法の第３のステップは、特異値分解（ＳＶＤ）を使用するマトリックス因数分解である。このステップでは、要約されるメディアの基底ベクトルまたはセグメント・クラスタＢ1、Ｂ2、Ｂ3を表す、図１に示す１２０、１３０、１４０といった新しいマトリックスまたは項が生成される。因数分解されたマトリックス１２０〜１４０内の各位置は次式のように定義される。
【００４５】
【数５】
2005174333.tif 000007
ここで
Ｕ（ｉ，ｋ）は正規直交列を有するＮ×Ｋマトリックス、
Ｖ（ｋ，ｊ）は正規直交行を有するＫ×Ｎマトリックス、
Ｎはフレームの数、
Ｋは基底ベクトルの数、
ｋ＝１〜Ｋであり、そして
【数６】
2005174333.tif 000008
ここでΣは要素（ｉ，ｉ）＝σiを有する対角マトリックスである。
【００４６】
種々の例示的なな実施形態においてＫの値は、特異値に直接適用またはｋth特異値対最大特異値の比率に適用、どちらにも適用される絶対閾値を使用して特異値σkに基づいてＳの有効ランクとして決定される。Ｋの値はまた、要約されつつある順序付き情報の内容に関する前の情報および／または知識に基づいて決定され、ユーザによってもセットできる。Ｋの値を決定するために適当な他の任意の既知のまたは新たに開発される手法が使用できることも認識されたい。
【００４７】
マトリックスＵ（ｉ，ｊ）のＫ個の列は因数分解の基底ベクトルであり、マトリックスＶ（ｋ，ｊ）のＫ個の行はこの基底上への類似度マトリックス１１０の列の係数表現である。σkとＵ（ｉ，ｋ）とＶ（ｋ，ｊ）とがどのように決定されるかの詳細については、非特許文献３、すなわち、エム・ベリー（Ｍ．Ｂｅｒｒｙ）等著「知的情報検索のための線形代数の使用（Ｕｓｉｎｇ  Ｌｉｎｅａｒ  Ａｌｇｅｂｒａ  ｆｏｒ  Ｉｎｔｅｌｌｉｇｅｎｔ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ）」エスアイエーエム・レビュー（ＳＩＡＭ  Ｒｅｖｉｅｗ）、３７（４），１９９５年，ｐ．５７３〜５９５、を参照のこと。
【００４８】
図１に示す因数分解されたマトリックス１２０、１３０、１４０のｘ軸はフレームｉを表し、ｙ軸はフレームｊを表す。因数分解されたマトリックス１２０のスケール１２１は、最大スコア１．０が白、スコア０．５が黒といったグレイスケースに位置値Ｂ1（ｉ，ｊ）を相関させている。因数分解されたマトリックス１２０は、ｉとｊが両者ともセグメント１１４内に存在するか、両者ともセグメント１１８内に存在する領域において高いスコアを示す。因数分解されたマトリックス１２０はまた、ｉがセグメント１１４に存在してｊがセグメント１１８に存在する領域においても、これらのセグメントを基底ベクトルまたはクラスタとして識別して高いスコアを示す。
【００４９】
因数分解されたマトリックス１３０のスケール１３１は、最大スコア０．４が白、スコア−０．４が黒といったグレイスケースに位置値Ｂ2（ｉ，ｊ）を相関させる。因数分解されたマトリックス１３０は、ｉがセグメント１１４に存在してｊがセグメント１１８に存在する領域において、これらのセグメントを基底ベクトルまたはクラスタとして識別して高いスコアを示す。因数分解されたマトリックス１３０はまた、ｉがセグメント１１２に存在してｊがセグメント１１６に存在する領域においても、これらのセグメントを基底ベクトルまたはクラスタとして誤って識別して高いスコアを示す。因数分解されたマトリックス１４０のスケール１４１は、最大スコア０．５が白、スコア−０．５が黒といったグレイスケースに位置値Ｂ3（ｉ，ｊ）を相関させる。因数分解されたマトリックス１４０は、ｉとｊが両者ともセグメント１１２内に存在するか、両者ともセグメント１１６内に存在する領域において高いスコアを示す。因数分解されたマトリックス１４０はまた、ｉがセグメント１１２に存在してｊがセグメント１１６に存在する領域においても、これらのセグメント１１２、１１６が同じくラスタの一部でないことを示す負のスコアを示す。
【００５０】
図２は、類似度マトリックス１１０の類似度スコアの行合計と、特異値分解を使用して生成された基底ベクトル１２０〜１４０とをグラフで示す。類似度マトリックス１１０の各行合計２１０は、このマトリックスのｉth行内のすべての値Ｓ（ｉ，ｊ）の合計である。そして、各行ｉに関する行合計は、ｉの関数としてプロットされている。類似度マトリックス１１０の行合計２１０は、すべての基底ベクトルとクラスタを正確には識別しない。因数分解されたマトリックス１２０の行合計２２０は、因数分解済みのマトリックス１２０のｉ行内のすべての値Ｂ1（ｉ，ｊ）の合計であって、ｉの関数としてプロットされている。セグメント１１４、１１８内のフレームｉに関する行合計２２０の値は、その他のフレームに関する行合計の値よりもかなり大きく、分析によってセグメント１１４、１１８を第１の基底ベクトル・クラスタとして識別することを容易にしている。
【００５１】
因数分解されたマトリックス１３０の行合計２３０は、因数分解済みのマトリックス１３０のｉ行内のすべての値Ｂ2（ｉ，ｊ）の合計であって、ｉの関数としてプロットされている。セグメント１１２、１１６内のフレームｉに関する行合計２３０の値は、その他のフレームに関する行合計の値よりもかなり大きく、分析においてセグメント１１２、１１６を基底ベクトル・クラスタとして誤って識別する可能性を残している。因数分解されたマトリックス１４０の行合計２４０は、因数分解済みのマトリックス１４０のｉ行内のすべての値Ｂ3（ｉ，ｊ）の合計であって、ｉの関数としてプロットされている。セグメント１１２、１１４、１１６、１１８内のフレームｉに関する行合計２４０の値は、きわめて小さく、分析用には信頼できない。
【００５２】
図３は、類似度マトリックスと、本発明による非ネガティブ・マトリックス因数分解（ＮＭＦ）を使用して生成された多数のベクトルまたは項Ａkを示す。図３に示す類似度マトリックス３１０では、このマトリックス内の各位置Ｓ（ｉ，ｊ）は次式のように定義される。
【００５３】
【数７】
2005174333.tif 000009
ここで各類似要素（ｉ，ｊ）は、方程式（１ｃ）の指数変数を使用して定義される。類似度マトリックス３１０のｘ軸はフレームｉを表し、ｙ軸はフレームｊを表す。スケール３１１は、最大スコア１．４が白、スコア０が黒といったグレイスケースに類似距離値Ｓ（ｉ，ｊ）を相関させている。ｉ＝ｊを表す対角線は、１．４という最大類似距離値Ｓ（ｉ，ｊ）スコアを持ち、白である。
【００５４】
この非ネガティブ因数分解が、類似度データがポアソン・ノイズ・モデルにしたがって生成されると仮定している対数尤度関数を最大にすることは認識されたい。この最大化は、非ネガティブ性制約の下で実行される。すなわち非ネガティブ性制約は、結果として得られる基底ベクトルが互いに打ち消すことなくＳの列に近づくように結合されることを意味する。Ｎ×ＮマトリックスＳの非ネガティブ因数分解は、Ｓｂ＝ＷＨとして表されるＳへの一次近似を定義する。反復手法を使用すると、Ｓｂは関数
【数８】
2005174333.tif 000010
の極大値に収束し、また
【数９】
2005174333.tif 000011
であり、ここで
Ｗはその列が因数分解に関する基底ベクトルであるＮ×Ｋマトリックスであり、
Ｈは基底ベクトルへのＳの列の係数表現のＫ×Ｎマトリックスである。
【００５５】
類似度マトリックスＳの非ネガティブ・マトリックス因数分解を決定することによって各成分マトリックスＡは下記に定義するように、高い類似度を有するセグメントの１クラスタを表す。方程式（５）のマトリックス合計のこれらの項Ａは、類似度マトリックスＳの構造成分を表す。特異値分解において、Ｗの列は正規直交的であり、Ｈの行は直交的である。その結果、これらは結合されると両者が加算されて打ち消される。対照的に非ネガティブ・マトリックス因数分解の基底ベクトルと係数との結合は、厳密に加法的である。
【００５６】
図３に示す類似度マトリックス３１０では、多数のメディア・セグメント３１２、３１４、３１６、３１８が識別できる。各セグメント３１２、３１４、３１６、３１８は、類似度マトリックス３１０の主要対角線に沿った正方形の領域に対応しており、ここではフレームｉ、ｊが同一セグメント内に存在するこれらの位置Ｓ（ｉ，ｊ）が高い類似度スコアを示している。更に類似度マトリックス３１０では、フレームｉがセグメント３１４といった一つのセグメント内に存在し、フレームｊがセグメント３１８といったもう一つのセグメント内に存在する位置Ｓ（ｉ，ｊ）もまた高い類似度スコアを示すことができる。これは、セグメント３１４と３１８が一つのクラスタを形成しており、ソース・ストリームの単一の基底ベクトルまたは構造成分として取り扱い得ることを示している。
【００５７】
その後、類似度マトリックス３１０は、非ネガティブ・マトリックス因数分解（ＮＭＦ）を使用して因数分解される。このステップでは、メディアの基底ベクトルＡkまたはセグメント・クラスタを表す新しいマトリックス３２０、３３０、３４０が生成される。この因数分解は、Ｓの構造分解を表す項Ａkを生成するために使用される。項Ａ1、Ａ2、Ａ3に対応する所定の因数分解されたマトリックス３２０、３３０、３４０はそれぞれ、次式のように定義される。
【００５８】
【数１０】
2005174333.tif 000012
ここで
Ｗ（ｉ，ｋ）はＮ×Ｋマトリックス、
Ｈ（ｋ，ｊ）はＫ×Ｎマトリックス、
Ｎは要約されるストリームのフレームまたは分離可能な部分の数、
Ｋは基底ベクトルの数、
ｋは１とＫとを含めてこれらの間の整数、そして
【数１１】
2005174333.tif 000013
である。
【００５９】
種々の例示的なな実施形態では、Ｋの値は先ずＳの有効ランクＫを評価し、その後、Ｓの確率論的因数分解のＫ項を評価することによって決定される。そして、下記に更に詳細に論議されるように、クラス内類似度に関して所望の、または理想的には最適の長さＬの要約を決定するために、項Ａ1、Ａ2、・・・、Ａkが処理される。
【００６０】
マトリックスＷ（ｉ，ｋ）のＫ個の列は、因数分解の基底ベクトルであり、Ｓの有意部分、すなわち高い類似度の有意ブロックを表す。マトリックスＨ（ｋ，ｊ）のＫ個の行は、この基底に対する類似度マトリックス３１の列を表す係数である。因数分解は、結果的に得られる基底ベクトルが互いに打ち消すことなく、類似度マトリックス３１０の列に近づくように結合できることを保証する非ネガティブ性制約の下で実行される。引用によってその全体がここに組み入れられている、非特許文献４、すなわち、ディー・リー（Ｄ．Ｌｅｅ）等著「非ネガティブ・マトリックス因数分解によるオブジェクトの部分の学習（Ｌｅａｒｎｉｎｇ  ｔｈｅ  ｐａｒｔｓ  ｏｆ  ｏｂｊｅｃｔｓ  ｂｙ  ｎｏｎ−ｎｅｇａｔｉｖｅ  ｍａｔｒｉｘ  ｆａｃｔｏｒｉｚａｔｉｏｎ）」ネイチャー（Ｎａｔｕｒｅ），４０１，１９９９年，ｐ．７８８〜７９１は、マトリックスＷ（ｉ，ｊ）とＨ（ｋ，ｊ）とがどのようにして決定されるかについての更なる詳論を用意している。
【００６１】
非特許文献５、すなわち、ティー・ホフマン（Ｔ．Ｈｏｆｆｍａｎ）著「クラスタ抽出モデル：テキスト・データからの見出し階層の非管理的学習（Ｔｈｅ  Ｃｌｕｓｔｅｒ−Ａｂｓｔｒａｃｔｉｏｎ  Ｍｏｄｅｌ：  Ｕｎｓｕｐｅｒｖｉｓｅｄ  Ｌｅａｒｎｉｎｇ  ｏｆ  Ｔｏｐｉｃ  Ｈｉｅｒａｒｃｈｉｅｓ  ｆｒｏｍ  Ｔｅｘｔ  Ｄａｔａ）」ＩＪＣＡＩ予稿集，１９９９年に記載されたような確率論的クラスタ化（ＰＣ）は、類似度マトリックス３１０を因数分解するために、非ネガティブ・マトリックス因数分解（ＮＭＦ）の代わりに使用できる。非特許文献６、すなわち、ティー・ホフマン（Ｔ．Ｈｏｆｆｍａｎ）著「確率論的潜在意味分析による非管理的学習（Ｕｎｓｕｐｅｒｖｉｓｅｄ  Ｌｅａｒｎｉｎｇ  ｂｙ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｌａｔｅｎｔ  Ｓｅｍａｎｔｉｃ  Ａｎａｌｙｓｉｓ）」マシン・ラーニング（Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ）４２，２００１年，ｐ．１７７〜９６に記載されたような確率論的潜在意味分析（ＰＬＳＡ）は、類似度マトリックス３１０を因数分解するために、非ネガティブ・マトリックス因数分解（ＮＭＦ）の代わりに使用できることも認識されたい。一般に本発明によるシステムと方法では、類似度マトリックスを因数分解するために、他の任意の既知のまたは新たに開発される確率論的分解または確率論的マトリックス因数分解が使用できる。
【００６２】
図３に示す因数分解されたマトリックス３２０、３３０、３４０のｘ軸はフレームｉを表し、ｙ軸はフレームｊを表す。因数分解されたマトリックス３２０、３３０、３４０のスケール３２１、３３１、３４１はそれぞれ、最大スコア１．２が白、スコア０が黒といったグレイスケースに位置値Ａk（ｉ，ｊ）を相関させている。因数分解されたマトリックス３２０は、フレームｉとｊが両者ともセグメント３１４内に存在するか、両者ともセグメント３１８内に存在する領域において高いスコアを示す。因数分解されたマトリックス３２０はまた、フレームｉがセグメント３１４に存在してフレームｊがセグメント３１８に存在する領域においても、これらのセグメント３１４、３１８を第１の基底ベクトルまたはクラスタとして正しく識別して高いスコアを示す。
【００６３】
因数分解されたマトリックス３３０は、フレームｉ、ｊが両者ともセグメント３１２内に存在する領域において、セグメント３１２を第２の基底ベクトルとして識別して高いスコアを示す。因数分解されたマトリックス３４０は、フレームｉ、ｊが両者ともセグメント３１６内に存在する領域において、セグメント３１６を第３の基底ベクトルとして識別して高いスコアを示す。
【００６４】
図４は、類似度マトリックスＳの類似度スコアの行合計と、非ネガティブ・マトリックス因数分解（ＮＭＦ）を使用して生成された基底ベクトルまたは項Ａkとをグラフで示す。図４で各類似度行合計４１０が、
【数１２】
2005174333.tif 000014
のように、決定されることは認識されたい。
類似度マトリックス３１０の各類似度行合計４１０は、類似度マトリックス３１０のｉ行内のすべての値Ｓ（ｉ，ｊ）の合計であって、ｉの関数としてプロットされている。筆者らはまた、次式にしたがってマトリックスＡkの各々に関する行合計を計算している。
【００６５】
【数１３】
2005174333.tif 000015
行合計４１０は、類似度マトリックス３００のすべての基底ベクトルとクラスタとを正確には識別しない。因数分解されたマトリックス３２０の行合計４２０は、因数分解済みのマトリックス３２０のｉ行内のすべての値Ａ1（ｉ，ｊ）の合計であって、ｉの関数としてプロットされている。セグメント３１４、３１８内のフレームｉに関する因数分解されたマトリックス３２０の行合計４２０の値は、その他のフレームに関する行合計の値よりもかなり大きく、分析によってセグメント３１４、３１８を第１の基底ベクトル・クラスタとして識別することを容易にしている。
【００６６】
因数分解されたマトリックス３３０の行合計４３０は、因数分解済みのマトリックス３３０のｉ行内のすべての値Ａ2（ｉ，ｊ）の合計であって、ｉの関数としてプロットされている。セグメント３１２内のフレームｉに関する因数分解済みのマトリックス３３０の行合計４３０の値は、その他のフレームの行合計の値よりもかなり大きく、分析によってセグメント３１２を第２の基底ベクトル・クラスタとして識別することを容易にしている。因数分解されたマトリックス３４０の行合計４４０は、因数分解済みのマトリックス３４０のｉ行内のすべての値Ａ3（ｉ，ｊ）の合計であって、ｉの関数としてプロットされている。セグメント３１６内のフレームｉに関する因数分解済みのマトリックス３４０の行合計４４０の値は、その他のフレームの行合計の値よりもかなり大きく、分析によってセグメント３１６を第３の基底ベクトル・クラスタとして識別することを容易にしている。
【００６７】
図５は、一つの例示的なな因数分解された成分マトリックスＡkを示す。因数分解された成分マトリックス３２０〜３４０は、要約されるメディア・ストリームの各セグメント・クラスタまたは基底ベクトルから抽出される所望の長さＬの代表的抄録を決定するために使用できる。図５に示すように特定の抄録がどれほど代表的であるかの度合いあるいはスコアは、抄録５２０といったある特定の抄録に関する平均クラス内（基底ベクトル）成分マトリックスＡ*k（ｑ、ｒ）を決定することによって得られる。成分マトリックスＡk（ｉ，ｊ）に関する値は、抄録領域５２０に亘って合計され、この抄録領域５２０のサイズで除算される。すなわちＡ*k（ｑ、ｒ）は、次式のように決定される。
【００６８】
【数１４】
2005174333.tif 000016
ここで、ｒは抄録の終了フレームであり、ｑは抄録の開始フレームである。
【００６９】
平均クラス内（基底ベクトル）成分マトリックスＡ*k（ｑ，ｒ）は、すべての可能な開始点ｒを有する抄録とおそらくすべての所望の長さＬとに関して決定される。結果的に最も高い平均クラス内（基底ベクトル）成分マトリックスＡ*k（ｑ，ｒ）となる、開始点とおそらくは長さとを有する抄録は、その基底ベクトルに関して最適のまたは所望の抄録として選択される。その後、このプロセスは、各基底ベクトルに関して繰り返される。
【００７０】
各成分マトリックスＡkは選択された抄録が最終的要約内に表現しなくてはならないセグメント・クラスタに対応する類似度マトリックスのその部分を表すので、各成分マトリックスＡkがクラス内類似度を数量化するということを認識されたい。本発明によるシステムと方法の種々の例示的な実施形態では、所定の成分マトリックスＡkに関する要約抄録を選択するために、ｋth成分のｉth開始位置に関するスコアＱL(k)（ｉ）は次式のように定義される。
【００７１】
【数１５】
2005174333.tif 000017
方程式（７）の内部合計に対応する行合計は、図４に示されている。本発明によるシステムと方法の種々の例示的な実施形態ではｋth成分から抽出される抄録に関する開始点ｑL(k)が決定されることを認識されたい。種々の例示的なな実施形態では開始点ｑL(k)は、ｋth成分に関するスコアＱL(k)を最大にするその点である。すなわち、
【数１６】
2005174333.tif 000018
そして、ｋth成分マトリックスＡkに関する抄録は、開始点または時刻ｑL(k)と終了点または時刻ｑL(k)＋Ｌとの間に延びる要約されるメディア・ストリームのｋthセグメントの抄録になる。本発明によるシステムと方法の種々の例示的なな実施形態では、その後、この要約はｋ個のセグメントから得られるｋ個の抄録を連結することによって結合しまたはコンパイルされる。
【００７２】
種々の例示的なな実施形態では、長さＬが固定値であるよりはむしろ、抄録がその一部である成分に付加された重要度にしたがって変化できることを認識されたい。例えば種々の例示的なな実施形態では、要約の所望の全長ＬTが定義できる。その後、種々の成分Ｋの長さｌkは、それらの長さｌkが全長ＬTに合計され、各成分ｋの長さｌkがある仕方でその成分ｋの重要度に関係するように決定される。種々の例示的なな実施形態で所定の成分ｋの長さｌkは、次式で表される。
【００７３】
【数１７】
2005174333.tif 000019
すなわちこのような例示的なな実施形態では要約の全長ＬTは一定であって、成分Ｋのすべてに関する平均類似度の合計に対するその成分ｋの平均類似度に基づいて、その全長ＬTの一部分が各成分ｋに分配される。全長ＬTが任意の適当な既知のまたは新たに開発される分配方式に基づいて種々の成分ｋに分配され得ることを認識されたい。
【００７４】
上記に概説した例示的なな実施形態では順序付き情報のストリームの特性に関する最小限の仮定がなされていることも認識されたい。しかしながら種々の例示的なな実施形態では、順序付き情報のストリームの分解を一つ以上のこのような特性に基づかせることは適切な場合もある。種々の例示的なな実施形態では、これは順序付き情報のストリームの特定の部分を強調するために重み付け関数を適用することによって遂行できる。このような例示的なな実施形態では重み付けられたスコアＳwは、方程式（７ｃ）を次式のように修正することによって生成できる。
【００７５】
【数１８】
2005174333.tif 000020
非ネガティブ・マトリックス因数分解（ＮＭＦ）を使用すると、ビデオ部分とオーディオ部分の両者を含むマルチメディア・ストリームといったマルチモードのメディアは、同様に要約できる。このような例示的なな実施形態では、各モードに関する類似度マトリックスが、生成されて次式のように結合される。
【００７６】
【数１９】
2005174333.tif 000021
ここで、
Ｓc（ｉ，ｊ）は結合Ｎ×２Ｎ類似度マトリックス、
Ｓa（ｉ，ｊ）はＮ×Ｎオーディオ類似度マトリックス、
Ｓv（ｉ，ｊ）はＮ×Ｎビデオ類似度マトリックスである。
【００７７】
そして、クラスタ化に関する結合尤度モデルは、次式のように生成できる。
【００７８】
【数２０】
2005174333.tif 000022
および
【数２１】
2005174333.tif 000023
ここで、Ｗはその列が因数分解のための基底ベクトルであるＮ×Ｋマトリックスであり、Ｈはこれらの基底ベクトルに対するＳcの列の符号化のＫ×２Ｎマトリックスである。これが方程式（５）の直接的な拡張であることを認識されたい。上記に概説した要約プロセスは、Ｋ個の異なるＮ×２Ｎ因数分解マトリックスＡkを生成するためにＮ×ＫマットリックスＷとＫ×２ＮマトリックスＨとを使用してより大きなマトリックスに適用できる。
【００７９】
図６は、本発明によるメディア・ストリームの要約を生成するための方法の一つの例示的なな実施形態を略述する流れ図である。図６に示すように本方法の動作は、ステップＳ１００から始まり、ステップＳ２００に続き、ここでメディア・ストリームはパラメータ化される。その後、ステップＳ３００で、方程式（１ｃ）を使用してメディア内の各ペアワイヤ・セット（ｐａｉｒ−ｗｉｒｅ  ｓｅｔ）のフレームに関して類似度が決定される。次にステップＳ４００で方程式（４）を使用して類似度マトリックスＳ（ｉ，ｊ）が生成される。その後、動作はステップＳ５００に続く。
【００８０】
ステップＳ５００で類似度マトリックスＳ（ｉ，ｊ）は、一つ以上の因数分解されたマトリックスを生成するために、例えば非ネガティブ・マトリックス因数分解（ＮＭＦ）法といった一つ以上の確率論的手法を使用して因数分解される。この場合、類似度マトリックスＳ（ｉ，ｊ）は方程式（５）を使用して因数分解される。次にステップＳ６００で、結果として得られた因数分解済みの一つ以上のマトリックスを使用して、このメディアの各基底ベクトルを表す抄録が識別される。そして、ステップＳ７００で、これら識別された抄録がメディア・ストリームから抽出されて、メディア・ストリームの要約内に集められる。その後、動作はステップＳ８００に続いて行き、本方法の動作は終了する。
【００８１】
図７は、本発明によるメディア・ストリームの各基底ベクトルまたは有意な構造成分に関して抄録を識別するための方法の一つの例示的なな実施形態をより詳細に概説する流れ図である。図７に示すように本方法の動作は、ステップＳ６００から始まってステップＳ６１０に続き、そこで最初の／次の基底ベクトルが選択される。そして、ステップＳ６２０で、生成すべき要約の長さが決定される。要約の長さは、省略時のパラメータによって、オペレータ入力によって、および／または基底ベクトルの相対長さまたはある他のパラメータに基づいて省略時の長さを調整することによって決定できる。幾つかの例示的なな実施形態では二つ以上の長さが使用でき、および／またはその長さが、所定の開始点における各抄録がそのスコアを最大にする長さを持つように、抄録のスコア付けにしたがって動的に決定できることを認識されたい。次にステップＳ６３０ですべての可能な開始点に対応する各抄録の代表的スコアが、方程式（６）を使用して生成される。その後、動作はステップＳ６４０に続く。
【００８２】
ステップＳ６４０で、選択された基底ベクトルの抄録に関する最適または所望の開始点が、ステップＳ６３０で最も高いスコアを生成した抄録を選択することのよって決定される。そして、ステップＳ６５０で、すべての基底ベクトルに関して抄録が生成されたかどうかの決定がなされる。もしすべての基底ベクトルに関して抄録が生成されていなければ、動作はステップＳ６１０に戻る。そうでなければ動作はステップＳ６６０に続き、そこで動作はステップＳ７００に戻る。
【００８３】
図８は、本発明によるメディア・ストリームの代表的要約を生成するために使用可能なメディア要約システム６００の一つの例示的なな実施形態を示す。図８に示すようにこのメディア要約システム６００は、一つ以上の制御手段および／またはデータバスおよび／またはアプリケーション・プログラミング・インタフェースなど６８０によって相互接続された、入出力インタフェース６１０と、コントローラ６２０と、メモリ６３０と、メディア・ストリーム・パラメータ化回路、ルーチンまたはアプリケーション６４０と、類似度マトリックス生成回路、ルーチンまたはアプリケーション６５０と、類似度マトリックス因数分解回路、ルーチンまたはアプリケーション６６０と、メディア要約生成回路、ルーチンまたはアプリケーション６７０と、を含んでいる。図８に示すようにデータ送信側７００とデータ受信側８００はそれぞれ、リンク７１０、８１０によってメディア要約システム６００に接続されている。
【００８４】
一般に図８に示すデータ送信側７００は、要約すべきメディア・ストリームをメディア要約システム６００に供給できる任意の既知のまたは新たに開発される装置であり得る。一般にデータ送信側７００は、メディア・ストリームとして電子データを生成するために適したスキャナー、ディジタル複写機、ファクシミリ装置、ディジタルカメラ、ディジタルビデオレコーダなど、あるいはネットワークまたはインターネットまた特にワールドワイドウェブのクライアントまたはサーバといった電子データをメディア・ストリームとして記憶および／または送信するために適した装置といった多数の異なる送信源のうちの任意のひとつであり得る。一般にデータ受信側８００は、メディア要約システム６００からのメディア要約を表示、記憶、送信あるいは受信するために使用可能な任意の既知のまたは新たに開発される装置であり得る。
【００８５】
データ送信側７００および／またはデータ受信側８００は、メディア要約システム６００と共に統合することができる。更にメディア要約システム６００は、データ送信側７００および／またはデータ受信側８００に加えて付加的機能を与える装置と一緒に統合できる。
【００８６】
データ送信側７００とデータ受信側８００とをそれぞれメディア要約システム６００に接続するリンク７１０、８１０の各々は、直接的ケーブル接続、モデム、ローカルアリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、イントラネット、エクストラネット、インターネット、公衆電話網、その他任意の分散処理ネットワーク、あるいは他の任意の既知のまたは新たに開発される接続装置、であり得る、および／または、を含み得る。リンク７１０、８１０の各々が一つ以上の有線および／または無線部分を含み得ることを認識されたい。一般にリンク７１０、８１０の各々は、それぞれの装置をメディア要約システム６００に接続するために使用可能な任意の既知のまたは新たに開発される接続システムまたは構造であり得る。リンク７１０と８１０とが同じタイプである必要がないことは理解されるべきである。
【００８７】
図８に示すように、メモリ６３０は変更可能な揮発性または不揮発性メモリ、あるいは変更不能なまたは固定したメモリの任意の適当な組合せを使用して実現可能である。揮発性または不揮発性の可変メモリは、スタティックまたはダイナミックＲＡＭ、フロッピー（登録商標）ディスクとディスクドライブ、書き込み可能または書き換え可能光ディスクとディスクドライブ、ハードドライブ、フラッシュメモリなどのうちの任意の一つ以上を使用して実現可能である。同様に変更不能すなわち固定メモリは、ＲＯＭと、ＰＲＯＭと、ＥＰＲＯＭと、ＥＥＰＲＯＭと、ＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭとディスクドライブなどといった光ＲＯＭディスクと、のうちの任意の一つ以上を使用して実現可能である。
【００８８】
メディア要約システム６００の種々の実施形態が、プログラムされた汎用コンピュータ、専用コンピュータ、マイクロプロセッサなどの上で実行可能なコンピュータ可読媒体に記憶されたソフトウエアとして実現可能であることは理解されるべきである。このようなコンピュータ可読媒体は、搬送波等を使用してソフトウエア命令を処理装置に供給することを含む。図８に示す回路、ルーチン、アプリケーション、マネージャ、プロシージャ（手順）、オブジェクトなどの各々が適当にプログラムされた汎用コンピュータの一部分として実現可能であることも理解されるべきである。代替として図８に示す回路、ルーチン、アプリケーション、マネージャ、プロシージャ、オブジェクトなどの各々は、ディジタルシグナルプロセッサ（ＤＳＰ）を使用して，ＦＰＧＡ、ＰＤＬ、ＰＬＡおよび／またはＰＡＬを使用して、あるいは個別論理素子または個別回路素子を使用してＡＳＩＣ内の物理的に個別のハードウエア回路として実現可能である。図８に示す回路、ルーチン、アプリケーション、マネージャ、プロシージャ、オブジェクトなどの特定の形式は、設計上の選択であり、本技術に精通する人々には明らかであって予測可能であろう。図８に示す回路、ルーチン、アプリケーション、マネージャ、プロシージャ、オブジェクトなどが同じ設計である必要がないことを認識されたい。
【００８９】
ルーチン、アプリケーション、マネージャ、プロシージャ、オブジェクトなどが所望の結果に至る自己矛盾のない一連のコンピュータ化されたステップであり得ることを認識されたい。これらのステップは、コンピュータ可読媒体に記憶された一つ以上のコンピュータ命令によって、および／または、において定義可能であり、これはソフトウエア命令を処理装置に供給するためにメモリ、搬送波等を使用することを包含すると理解すべきである。これらのステップは、ステップを定義する命令を実行するコンピュータによって実行可能である。したがって用語「ルーチン」、「アプリケーション」、「マネージャ」「プロシージャ（手順）」、および「オブジェクト」は、例えば一連の命令、プログラムされた手順またはプログラムされた機能内に構成された一連の命令、および／または一つ以上のコンピュータ内で実行するプログラムされたプロセス内に構成された一連の命令を指す場合もある。このようなルーチン、アプリケーション、マネージャ、プロシージャ、オブジェクトなども、プロシージャ（手順）を実行する回路内に直接実現可能である。更にコンピュータ制御された方法は、一つ以上の適当なプログラムを実行するコンピュータによって、またはこの方法を実行するように設計された専用のハードウエアによって、あるいはこのようなハードウエア、ファームウエアおよびソフトウエア要素の任意の組合せによって実行可能である。
【００９０】
動作時にメディア要約システム６００は、リンク７１０上でデータ送信側７００からメディア・ストリームを受信する。入出力インタフェース６１０は、受信されたメディア・ストリームを入力し、コントローラ６２０の制御下でそれをメモリ６３０の入力メディア・ストリーム部６３１に、および／または、メディア・ストリーム・パラメータ化回路、ルーチンまたはアプリケーション６４０に直接に転送する。そして、メディア・ストリーム・パラメータ化回路、ルーチンまたはアプリケーション６４０は、受信したメディア・ストリームの各フレームに関して特徴ベクトルを生成する。メディア・ストリーム・パラメータ化回路、ルーチンまたはアプリケーション６４０はその後、、コントローラ６２０の制御下で、その生成された特徴ベクトルをメモリ６３０の類似度パラメータ部６３２内に格納するか、あるいはその生成された特徴ベクトルを類似度マトリックス生成回路、ルーチンまたはアプリケーション６５０へ直接に転送する。
【００９１】
類似度マトリックス生成回路、ルーチンまたはアプリケーション６５０は、コントローラ６２０の制御下で、メモリ６３０の類似度パラメータ部６３２から、またはメディア・ストリーム・パラメータ化回路、ルーチンまたはアプリケーション６４０から特徴ベクトルを入力する。生成された特徴ベクトルを使用して類似度マトリックス生成回路、ルーチンまたはアプリケーション６５０は、フレームの各ペアに関して類似度距離を決定し、決定された類似度距離を類似度マトリックス内に加える。そして、類似度マトリックス生成回路、ルーチンまたはアプリケーション６５０は、コントローラ６２０の制御下で、類似度マトリックスをメモリ６３０の類似度マトリックス部６３３に格納するか、あるいは類似度マトリックス因数分解回路、ルーチンまたはアプリケーション６６０に直接出力する。類似度マトリックス生成回路、ルーチンまたはアプリケーション６５０が、上記に概説した種々の手法を含む任意の既知のまたは新たに開発される手法を使用して類似度マトリックスを生成できることを認識されたい。
【００９２】
類似度マトリックス因数分解回路、ルーチンまたはアプリケーション６６０はコントローラ６２０の制御下で、メモリ６３０の類似度マトリックス部６３３から、あるいは類似度マトリックス生成回路、ルーチンまたはアプリケーション６４０から類似度マトリックスを入力する。類似度マトリックス因数分解回路、ルーチンまたはアプリケーション６６０は、確率論的マトリックス因数分解手法を使用して、各基底ベクトルまたは有意構造（significant structure）またはメディアに関して基底ベクトル項を生成する。類似度マトリックス因数分解回路、ルーチンまたはアプリケーション６６０はコントローラ６２０の制御下で、メモリ６３０の基底ベクトル項部６３４内に基底ベクトル項を格納するか、あるいはこれらの基底ベクトル項をメディア要約生成回路、ルーチンまたはアプリケーション６７０に直接出力する。類似度マトリックス因数分解回路、ルーチンまたはアプリケーション６６０が、上記に概説した種々の手法を含む任意の既知のまたは新たに開発される確率論的マトリックス因数分解手法を使用して類似度マトリックスを因数分解できることを認識されたい。
【００９３】
メディア要約生成回路、ルーチンまたはアプリケーション６７０はコントローラ６２０の制御下で、メモリ６３０の基底ベクトル項部６３４から、あるいは類似度マトリックス因数分解回路、ルーチンまたはアプリケーション６６０から基底ベクトル項を入力する。メディア要約生成回路、ルーチンまたはアプリケーション６７０は、各基底ベクトルから代表的抄録を抽出することにより、そして抽出した抄録を要約に結合することにより各基底ベクトルに関する基底ベクトル項または有意構造またはそのメディアから所望のメディア要約を生成する。メディア要約生成回路、ルーチンまたはアプリケーション６６０はコントローラ６２０の制御下で、メモリ６３０のメディア要約部６３５内にそのメディア要約を格納するか、あるいはメディア要約をリンク８１０上で入出力インタフェース６１０を介してデータ受信側８００に直接出力する。メディア要約生成回路、ルーチンまたはアプリケーション６７０が上記に概説した種々の手法を含む任意の手法を使用してメディア要約を生成できることを認識されたい。特にメディア要約生成回路、ルーチンまたはアプリケーション６７０は、上記に概説した種々の手法を含む、種々の代表的抄録を決定するための任意の既知のまたは新たに開発される手法を使用できる。
【００９４】
本発明は上記に概説した例示的なな実施形態に関連して説明されてきたが、既知であるか、存在しているか、現在予見されないかにかかわらず、種々の改変、修正、変形、改良および／または実質的同等物が明らかになり得る。したがって前述の本発明の例示的なな実施形態は、例示を意図するものであって限定を意図していない。本発明の精神と範囲とから逸脱せずに種々の変更が可能である。したがって本発明は、すべての既知のまたは新たに開発される改変、修正、変形、改良および／または同等物を包含することが意図されている。
【図面の簡単な説明】
【００９５】
本発明によるシステムと方法の種々の例示的な実施形態は、下記の図を参照して詳細に説明されている。
【図１】類似度マトリックスと、特異値分解を使用して生成されたその基底ベクトルまたは項とを示す図である。
【図２】類似度マトリックスと、特異値分解を使用して生成されたその基底ベクトルまたは項の類似度スコアの行合計とを示す１セットのグラフである。
【図３】類似度マトリックスと、本発明による非ネガティブ・マトリックス因数分解を使用して生成されたその基底ベクトルまたは項とを示す図である。
【図４】類似度マトリックスの要約と、非ネガティブ・マトリックス因数分解を使用して生成されたその基底ベクトルまたは項とに関する類似度スコアを示す１セットのグラフである。
【図５】本発明にしたがって要約類似度が決定されるメディア間隔を示す図である。
【図６】本発明によるメディア・ストリームの要約を生成するための方法の一つの例示的な実施形態を概説する流れ図である。
【図７】本発明によるメディア・ストリームの各基底ベクトルまたは有意構造成分に関して抄録を生成するための方法の一つの例示的な実施形態をより詳細に概説する流れ図である。
【図８】本発明によるメディア要約システムの一つの例示的な実施形態のブロック図である。
【符号の説明】
【００９６】
１１０  類似度マトリックス、  １１１、１２１、１３１、１４１  スケール、  １１２、１１４、１１６、１１８  メディア・セグメント、  １２０〜１４０  因数分解されたマトリックス、  Ｓ  類似度マトリックス、  Ｂ1、Ｂ2、Ｂ3  基底ベクトルまたは項、  ２１０、２２０、２３０、２４０  行合計、  ３１０  類似度マトリックス、  ３２０、３３０、３４０  因数分解されたマトリックス、  ３１１、３２１、３３１、３４１  スケール、  ３１２、３１４、３１６、３１８  メディア・セグメント、  Ａ1、Ａ2、Ａ3  成分マトリックス（基底ベクトルまたは項）、  ４１０、４２０、４３０、４４０  行合計、  ５１０、５２０  抄録、  ６００  メディア要約システム、  ６１０  入出力インタフェース、  ６２０  コントローラ、  ６３０  メモリ、  ６３１  入力メディア・ストリーム部、  ６３２  類似度パラメータ部、  ６３３  類似度マトリックス部、  ６３４  基底ベクトル項部、  ６３５  メディア要約部、  ６４０  メディア・ストリーム・パラメータ化回路、ルーチンまたはアプリケーション、  ６５０  類似度マトリックス生成回路、ルーチンまたはアプリケーション、  ６６０  類似度マトリックス因数分解回路、ルーチンまたはアプリケーション、  ６７０  メディア要約生成回路、ルーチンまたはアプリケーション、  ７００  データ送信側、  ８００  データ受信側、  ７１０、８１０  リンク
【図２】
2005174333.tif 000044
【図４】
2005174333.tif 000045
【図５】
2005174333.tif 000046
【図６】
2005174333.tif 000047
【図７】
2005174333.tif 000048
【図８】
2005174333.tif 000049
【図１】
2005174333.tif 000050
【図３】
2005174333.tif 000051