JP2006172437A - データのストリームにおけるセグメント境界の位置の決定方法、データサブセットを近隣のデータサブセットと比較してセグメント境界を決定する方法、コンピュータによって実行可能な命令のプログラム、ならびにデータのストリームにおける境界及び非境界を識別するシステム又は装置 - Google Patents

Abstract

【課題】データのストリームにおけるセグメント境界の位置の決定方法を提供する。
【解決手段】本決定方法は、（ａ）前記データのストリーム内のデータサブセットを、現在及び未来のデータサブセットの群から選択された１つ以上のデータサブセットと比較することによって１つ以上の類似度値を決定することであって、前記未来のデータサブセットが前記データのストリーム内の前記データサブセットよりも時間的に後に生じ、前記現在のデータサブセットが前記データのストリーム内の前記データサブセットと同時に生じる、前記１つ以上の類似度値を決定することと、（ｂ）類似度値の１つ以上のセットを分類することと、を含む。
【選択図】図１

Description

本発明は、アフィニティ(affinity)即ち類似度マトリックスに基づいたセグメント境界の識別方法に関する。特に、データのストリームにおけるセグメント境界の位置の決定方法、データサブセットを近隣のデータサブセットと比較してセグメント境界を決定する方法、コンピュータによって実行可能な命令のプログラム、ならびにデータのストリームにおける境界及び非境界を識別するシステム又は装置に関する。

初期のビデオ（映像）自動抽出技術は、カット境界(cut-boundary)の検出に焦点を当てたものであった。使用された主な技術は、ピクセルの差、統計的な差、ヒストグラムの比較、エッジ差、圧縮差及び運動ベクトルの検出であった。ヒストグラムはショット境界の検出に使用される最も一般的な方法である。最も単純な方法は画像の濃度ヒストグラムの計算である。これまでは、フレーム指標付きのノベルティスコア（novelty score）は一般に類似度マトリックスの主要対角線に沿った小さい核（カーネル）関数を相関させることにより計算され、ノベルティスコアの極大値がセグメント境界であるとみなされていた。

これまでに多数の核相関関数がビデオのセグメンテーションに関連して記載されている。尺度空間（ＳＳ）分析は、隣接する時間サンプルを比較し、主要対角線の上又は下の第１の対角線上のみにある非ゼロ要素、即ち要素Ｓ（ｎ，ｎ＋１）を有する核を使用することに相当する。対角線相互類似度（ＤＣＳ）を検出する方法も有効である。ＤＣＳ核（Ｋ_DCS）は、セグメント境界を中心とした際、異なるセグメントから一定間隔（Ｌ）離れた時間サンプルを比較するＳの要素のみに重みをつける。相関の計算では、Ｋ_DCS＞０であるＳの要素は、Ｓの主要対角線よりも上（及び下）にあるＬ番目の対角線に位置する。完全類似度核（Ｋ_FS）や相互類似度核（Ｋ_CS）も記載されている。

メディアセグメンテーション技術の大部分は分類器（クラシファイア）（classifier）を組み込まず、隣接フレームの類似度の値を閾値としている。加速された正確なｋＮＮ分類器がビデオショットセグメンテーションの分析に用いられるようになったのはつい最近のことである。しかし、評価対象のフレームを早い時間のフレームと比較し、分類器と併用するための類似度特徴量を生成していただけであり、類似度値の計算にはＬ¹測度が用いられていた。また、ｋＮＮ分類器は類似度値と共に直接利用されることはなく、分類出力の時間的な平滑化が必要であった。

メディアセグメンテーションは重大な問題であり、その重大さはますます高まっている。例えば、多数のビデオ検索作業やビデオ管理作業が場面境界の正確なセグメンテーションに依存している。

本願に関連する以下の関連技術がある。
特許文献１は、ビデオセグメント化ヒドンマルコフモデル（Hidden Markov Model）によりビデオの状態シーケンスをモデル化することを開示している。そこでは、自動学習、及びモーションベクトル、音声差、ヒストグラム差当の複数の特徴量の使用を可能にしている。
特許文献２は、会議中の音声とビデオのセグメント化について開示している。そのセグメント化は発言者の識別システムを有し、当該識別システムはヒドンマルコフモデルを用いる。
特許文献３は、ビデオのセグメント化された部分の重要度の計算に関する技術を開示している。そして、重要度の計算では閾値処理が用いられる。
特許文献４は、音声信号内の変化点の決定に関する。重要変化が生じる点が過去あるいは未来との類似性を有することの着目するものであり、ベクトルパラメータ化が用いられる。
特許文献５は、マルチモードの入出力での会話の処理に関する。
特許文献６は、メディアブラウザに関し、時間的特徴ベースで生成されたメタデータはその特徴がマルチメディア中に存在する確立を示すスコア値にマッピングされる。
特許文献７は、ビデオフレームを統計モデルを用いて分類する方法を開示している。
特許文献８は、ビデオにおけるインタラクティブな類似性検索について開示している。
特許文献９は、ユーザインタフェースを介してビデオのキーフレームの順番を操作する技術を開示している。
しかし、いずれの技術も上記問題点を解決していない。
米国特許第６，０７２，５４２Ａ号明細書 米国特許第６，４０４，９２５Ｂ１号明細書 米国特許第６，５３５，６３９Ｂ１号明細書 米国特許第６，５４２，８６９Ｂ１号明細書 米国特許第６，５７０，５５５Ｂ１号明細書 米国特許第６，３６６，２９６Ｂ１号明細書 米国特許第６，７５１，３５４Ｂ２号明細書 米国特許第６，７７４，９１７Ｂ１号明細書 米国特許第６，８０７，３６１Ｂ１号明細書

本発明は上記の事情に鑑みて成されたものであり、類似度分析と監督付き分類(supervised classification)の組み合わせに基づいてセグメント境界を決定するデータ分析方法を提供するものである。テキスト、音声ストリーム又はビデオを含む任意の順序のメディアにこの方法を適用することができる。また、附属のトランスクリプトから抽出された低レベルのビデオ特徴やテキスト特徴など、異質の特徴が組み合わされる相互メディア分析に使用することもできる。一般に、これらのメディアの各形態では、データストリームは順序付けされたデータのサブセットから構成されている。データサブセットは、データのストリームを分割する要素である。データストリームの各要素を１つ以上のデータサブセットに含めることができ、例えば、ビデオストリームを各ビデオフレームに対応するデータサブセットに分割することができる。データサブセットの順序付けは経時順であることが多い。

２つの異なるタイプの新規なデータサブセット指標付き特徴量ベクトルを詳述する。一方は、幅が変化する核関数から得られる複数の時間的尺度にわたる値を含む。もう一方は、対象となるサブセットの近隣にあるデータサブセット間の種々の生の類似度スコアを含む。また、「修正カイ２乗」類似度測度の新規な使用が説明され、類似度マトリックスに記憶された初期のペアワイズ類似度値が計算される。より詳細には、本発明の第１の態様は、データのストリームにおけるセグメント境界の位置の決定方法であって、
（ａ）前記データのストリーム内のデータサブセットを、現在及び未来のデータサブセットの群から選択された１つ以上のデータサブセットと比較することによって１つ以上の類似度値を決定することであって、前記未来のデータサブセットが前記データのストリーム内の前記データサブセットよりも時間的に後に生じ、前記現在のデータサブセットが前記データのストリーム内の前記データサブセットと同時に生じる、前記１つ以上の類似度値を決定することと、
（ｂ）類似度値の１つ以上のセットを分類することと、
を含む。

また、本発明の第２の態様は、データのストリームにおけるセグメント境界の位置の決定方法であって、
（ａ）前記データのストリームにある１つ以上のデータサブセットの１つ以上の類似度値を、近隣データの１つ以上のサブセットと比較して（前記データストリームにおける各データサブセットの比較に基づいて）計算することと、
（ｂ）前記類似度値に基づいて１つ以上の類似度マトリックスを生成することと、
（ｃ）異なる範囲Ｌを有する１つ以上の核関数を前記類似度マトリックスに適用し、各Ｌに対して１つ以上のノベルティスコアを生成することと、
（ｄ）ｑ＞１であるｑ個の異なるＬの値に対して対応するｑ個のノベルティスコアを入力して特徴量ベクトルを生じるようにＬを変更することと、
（ｅ）前記特徴量ベクトルを分類して前記セグメント境界の位置を決定することと、
を含む。

本発明の第３の態様は、データのストリームにおけるセグメント境界の位置の決定方法であって、
（ａ）近隣データの１つ以上のサブセットと比較して（前記データストリームにおける各データサブセットの比較に基づいて）、データのストリームにある１つ以上のデータサブセットの１つ以上の類似度値を計算することと、
（ｂ）前記類似度値に基づいて１つ以上の類似度マトリックスを生成することと、
（ｃ）相互類似度核及び完全な類似度核の群から選択された核関数を前記類似度マトリックスに適用することと、
（ｄ）前記類似度マトリックスの生のペアワイズデータを抽出し、核関数の各非ゼロ値に対して特徴量ベクトルを生じることと、
（ｅ）前記特徴量ベクトルを分類して前記セグメント境界の位置を決定することと、
を含む。

更に、本発明の第４の態様は、データサブセットを近隣のデータサブセットと比較してセグメント境界を決定する方法であって、
（ａ）１つ以上のデータサブセットを近隣データの１つ以上のサブセットと比較することに基づいて（各データサブセットの比較に基づいて）１つ以上の類似度値を計算する手段と、
（ｂ）前記類似度値から１つ以上の類似度マトリックスを生成する手段と、
（ｃ）前記類似度マトリックスから生のペアワイズデータを抽出する手段であって、核関数の各非ゼロ値に対して前記マトリックスの前記生のペアワイズデータを抽出し、前記核関数が相互類似度核及び完全類似度核の群から選択される、前記手段と、
（ｄ）抽出した前記生のペアワイズデータから特徴量ベクトルを生成する手段と、
（ｅ）分類器を用いて前記特徴量ベクトルを分類する手段と、
を含む。

また、本発明の第５の態様は、テストデータのストリームにおけるセグメント境界を決定する機能を果たすようにコンピュータによって実行可能な命令のプログラムであって、前記機能が、
（ａ）１つ以上のデータサブセットを近隣データの１つ以上のサブセットと比較することに基づいて（前記データストリームにおける各データサブセットの比較に基づいて）１つ以上の類似度値を計算するステップと、
（ｂ）前記類似度値から１つ以上の類似度マトリックスを生成するステップと、
（ｃ）相互類似度核及び完全類似度核の群から選択された１つ以上の核関数を前記類似度マトリックスに適用することによって特徴量ベクトルを生成するステップと、
（ｄ）データ及びグランドトルースクラスラベリングの１つ以上のトレーニングセットから生成された特徴量ベクトルを用いて分類器を学習させるステップと、
（ｅ）学習した前記分類器を用いたテストデータ及び類似する特徴量ベクトルから特徴量ベクトルを分類し、前記セグメント境界を決定するステップと、
を含む。

更に、本発明の第６の態様は、データのストリームにおける境界及び非境界を識別するシステム又は装置であって、前記識別が、
ａ）前記データのストリームにおける各データサブセットに対して類似度値を計算することができ、１つ以上の類似度マトリックスを生成することができ、核関数を前記マトリックスに適用することができ、特徴量ベクトルを生成することができ、前記データサブセットを分類することができる１つ以上のプロセッサと、
ｂ）前記データのストリームにおける各データサブセットに対して前記類似度値を生成するステップと、１つ以上の類似度マトリックスを作成するステップと、核関数を前記マトリックスに適用するステップと、特徴量ベクトルを生成するステップと、前記データサブセットを境界及び非境界として分類するステップを、前記１つ以上のプロセッサによって処理される際にシステムに行わせるオペレーションが記憶されたマシン可読媒体と、
を含む。

本発明の上記の各態様によれば、データのストリームにおけるセグメント境界の位置の決定の改善された方法が提供される。

本発明の好ましい実施の形態を図面に基づいて詳述する。これらの図面は発明の詳細な説明で十分に説明される。

図１は、本発明に従ったデータストリームの境界を検出し分類する処理手順を示すフローチャートである。図１のステップ１０１で入力されたデータストリームから類似度値が求められ（ステップ１０２）、類似度マトリックスが得られる（ステップ１０３）。その後、処理はステップ１０４とステップ１０７の２つに分かれる。ステップ１０４では、低レベル特徴量の抽出が行われる。一方、ステップ１０７では、Ｌを変更しつつ（ステップ１１０）、ｑ回の反復が終了するまで（ステップ１０８）（ｑはＬの異なる値の数。後述。）の核関数の計算が繰り返され、ｑ個のノベルティスコアが得られる（ステップ１０９）。そして、ステップ１０４及びステップ１０９の結果に基づき、特徴量ベクトルが求められる（ステップ１０５）。求められた特徴量ベクトルは分類器を用いてトレーニングデータと比較され（ステップ１０６）、カット境界、非境界、及び段階的境界の分類が行われる。

尚、本発明は、例えば、パーソナル・コンピュータ、ＰＤＡなどのコンピュータ・システムにおいて実施されることができる。該コンピュータ・システムは、例えば、上記データストリームやユーザからの指示情報（命令）を入力する入力部、プロセッサによる実行の際の作業領域を形成すると共にプログラムや処理対象としての上記入力したデータストリーム、及び各ステップで処理されたデータを格納する記憶部（メモリ）、処理内容や処理結果を表示画面上に表示する表示部（表示装置）、およびデータをインターネットやイントラネットなどの通信網（ネットワーク）などに出力する出力部などを含む。そして、プロセッサは、記憶部に格納したプログラム（ソフトウェア）を読み出し実行することにより、処理対象のデータストリーム等に対し、当該プログラムの処理手順、すなわち、類似度値の計算（上記ステップ１０２）、低レベル特徴量の抽出（上記ステップ１０４）、核関数の計算の繰り返しによるノベルティスコアの決定（上記ステップ１０９）、トレーニングデータとの比較による境界の分類（上記ステップ１０６）に対応した処理を当該コンピュータ・システムに実行させる。尚、プロセッサは複数であってもよい。さらに、上記プログラムは、コンピュータにより読取可能な記憶媒体（マシン可読媒体）に格納され、処理実行時にプロセッサによりアクセスされて読み出され、一時的に上記記憶部に格納されて実行される構成でもよい。
各処理手順の詳細については、以下の説明から明らかになるであろう。
類似度分析
マトリックスへの埋込み
本発明の１つの実施の形態では、データのストリーム内の各データサブセットを表すために低レベルの特徴量を計算する。サブセット間のデータ類似度を確実に定量化できる任意の特徴量のパラメータ表示を使用することができる。次いで、サブセットのヒストグラムＸ_iとＸ_jとの間の類似度（又は相違度）（Ｄ）の測度を、式１に示すようなデータストリーム内のサブセットデータ”ｉ”及び”ｊ”の各対に対して計算することができる。類似度マトリックスＳは、図２に示すように全てのデータサブセットの対の類似度値を記憶する。マトリックスＳのｉｊ番目のエントリＳ（ｉ，ｊ）は、式１に従った”ｉ”のサブセットと”ｊ”のサブセットとの間の類似度の測度である。
Ｓ（ｉ，ｊ）＝Ｄ（Ｘ_i，Ｘ_j） （式１）

図２は、データストリーム内のサブセット要素”ｉ”と隣接するサブセット要素”ｊ”との間の関係と、サブセット要素の各対の低レベル特徴量を比較して記憶する類似度マトリックスＳ（ｉ，ｊ）におけるこれらの位置とを示す図である。図２において、時間は双方の軸と対角線に沿って進んでいる。類似度Ｄの測度は対称的であり、Ｓも対称的である。記載される方法は、類似度の対称測度又は非対称測度と共に用いることができる。

類似度の測度
抽出した低レベルのヒストグラム特徴量間で類似度のペアワイズ比較を計算する。ここで、Ｘ_i、Ｘ_jはデータストリームのｉ番目とｊ番目のデータサブセットにそれぞれ対応する低レベルの特徴量である。この比較を、差分関数、比率関数、積分関数及び導関数に基づいて行うことができる。差分関数は有限未来でもよいし、有限過去でもよい。前に生じるデータサブセットとの比較を行う場合、これを過去差分という。後に生じるデータサブセットとの比較を行う場合は未来差分という。Ｌ¹、Ｌ²、「カイ２乗」測度（χ²）及び「修正カイ２乗」測度（Ｍχ²）を含む、類似度の多数の差分測度を考慮する。相違度の測度の定義は、式２乃至式５に与えられたものを含む。これら全ての測度に対し、類似度マトリックスＳは、各サブセットを自身と比較する主要対角線に沿って最小相違度（ゼロ）を有する。

式中、Ｐは各データサブセットに関連する低レベル特徴量の次元数である。

核相関によるセグメンテーション
通常、密着した（コヒーレントな）セグメント内のサブセットは低い相違度を示し、隣接する密着したセグメント内のサブセットは高い相違度を示す。セグメント内部での相違度がゼロであり、セグメント間の相違度が大きいことが理想的である。これにより、Ｓの主要対角線に沿ったチェッカーボードパターンが生じる。従って、このようなチェッカーボードパターンをＳに配置することによって合理的なセグメンテーション方法が得られる。本発明の１つの実施の形態では、相関スコアがＳの領域を理想的なチェッカーボード核マトリックスＫに適合させる。具体的には、Ｌ×Ｌ核Ｋに基づいたノベルティスコアは式６によって定義される。

本発明の１つの実施の形態では、短いセグメント間の境界の発見に優れた傾向にある小さな値から、長いセグメント間の境界の発見に優れている大きな値に核の尺度（Ｌ）を変更する。

類似度マトリックスＳ全体の計算にはＮ²個の計算が必要となる。Ｎはデータサブセットの数である。実際には、核の範囲、即ち要素Ｓ（ｉ，ｊ）（ここで｜ｉ−ｊ｜＞Ｌ）を越えて類似度マトリックス値を計算する理由はない。また、Ｓ及びＫの双方が一般に対称であるため、冗長となる計算が多い。このため、本発明の１つの実施の形態では、類似度マトリックスは、主要対角線付近のＳの小さい部分と「遅れ領域(lag domain)」に記憶されたデータにおいてのみ、式７に従って計算される。
Ｓ_lag（ｎ，ｌ）＝Ｓ（ｎ，ｎ＋ｌ） （式７）
式中、ｎ＝１，．．．，Ｎ、ｌ＝１，．．．，Ｌ、及びＬ＜＜Ｎである。よって、アルゴリズムの複雑さはＮに減らされる。

メディアセグメンテーションのための核関数
相互類似度(cross similarity)核（Ｋ_CS）と、前述した３つの他の核（完全類似度(full similarity)核Ｋ_FS、尺度空間(scale-space)核Ｋ_SS及び対角線相互類似度(diagonal cross similarity)核Ｋ_DCS）を図３にグラフで示す。図３は、Ｌ＝４である場合のセグメント境界検出のために提案された核を示す図であり、図３（Ａ）はＫ_CS核、図３（Ｂ）はＫ_FS核、図３（Ｃ）はＫ_SS核、図３（Ｄ）はＫ_DCS核を示している。各パネルにおいて、空白の要素は対応するノベルティスコアに貢献しない（即ち、式６において、Ｋ（ｌ，ｍ）＝０）。図３において、黒丸を含む要素はノベルティスコアに正に貢献する（Ｋ（ｌ，ｍ）＞０）。白丸を含む要素はノベルティスコアに負に貢献する（Ｋ（ｌ，ｍ）＜０）。相関のために、式６により、これらの核をＳの主要対角線に沿って適用する。

Ｋ_CSは、Ｌ¹類似度マトリックスにおける理想的なセグメント境界のための整合フィルタである。Ｋ_CS（Ｌ＝４の場合が図３（Ａ）に示される）は式８によって定義される。

Ｋ_FS（Ｌ＝４の場合が図３（Ｂ）に示される）は、核相関による場面(scene)セグメンテーションに以前から使用されている。Ｋ_FSはセグメント間の項とセグメント内の項の双方を含む。この核は、Ｋ_CS内のゼロ要素を負の重みに置き換える。負の重みは高いセグメント内相違度にペナルティを科す。式９を参照のこと。
図３（ｃ）のＫ_SS核は尺度空間（ＳＳ）分析に相当し、隣接する時間サンプルを比較し、主要対角線の上又は下の第１の対角線上のみにある非ゼロ要素、即ち要素Ｓ（ｎ，ｎ＋１）を有する核を使用することに相当する。
図３（ｄ）のＤＣＳ核（Ｋ_DCS）は、セグメント境界を中心とした際、異なるセグメントから一定間隔（Ｌ）離れた時間サンプルを比較するＳの要素のみに重みをつける。相関の計算では、Ｋ_DCS＞０であるＳの要素は、Ｓの主要対角線よりも上（及び下）にあるＬ番目の対角線に位置する。

特徴量ベクトル
核ベースの特徴量ベクトル
本発明の１つの実施の形態では、「核ベースの」特徴量ベクトルを用いてデータを評価する。異なる尺度Ｌのセットを考慮する。λである各Ｌに対し、ノベルティスコアを類似度マトリックスから尺度Ｌの核によって計算する（図４は、類似度マトリックス（Ｓ）に核相関関数（ここではｑ＝２と示され、Ｋ_FSに対してＬ＝２及びＬ＝３である）を適用することによってノベルティスコア（ｖ）を生成することを示す図である）。そして、λに対してこの処理を繰り返す。これらのノベルティの各々を特徴量ベクトル（Ｆ_n）に連結する（図５は、サブセット要素”ｎ”とｎ番目の要素Ｆ_nの特徴量ベクトルとの関係を示す図である）。特徴量ベクトルの異なるエントリは、λであるＬのｑ個の異なる値に対応する。例えば、λ＝｛２，３，４，５｝とすると、ｑ＝｜λ｜＝４である。次に、各データサブセットは、ｑ個のノベルティスコアを含む関連する４×１特徴量ベクトルを有する。ｎ番目のサブセットと関連する特徴量ベクトルは式１０によって与えられる。
Ｆ_n＝［ｖ₂（ｎ），ｖ₃（ｎ），ｖ₄（ｎ），ｖ₅（ｎ）］ （式１０）
式中、ｖ_L（ｎ）は、ｎ番目のデータサブセットのための幅Ｌを有する核を用いて計算されたノベルティスコアを示す。この例は、特徴量ベクトルのノベルティスコアの数であるｒが、考慮する異なる尺度Ｌの数であるｑに等しい実施の形態を示している。

生類似度ベースの特徴量ベクトル
本発明の１つの実施の形態では、特徴量ベクトルは「生のペアワイズ類似度（pairwise similarity）」データから直接得られる。核を用いてデータサブセットのための単一の値を計算する代わりに、核の各非ゼロ位置に対する特徴量ベクトルにエントリを行う。例えば、Ｌ＝５であるＫ_CS特徴量ベクトルを用いる場合、ｎ番目のデータサブセットは式１１に示す列ベクトルによって表される。
Ｆ_n＝［Ｓ^(G)（ｎ，ｎ−４），．．．，Ｓ^(G)（ｎ，ｎ−１），Ｓ^(G)（ｎ＋１，ｎ−
４），．．．，Ｓ^(G)（ｎ＋１，ｎ−１），］
［Ｓ^(G)（ｎ＋２，ｎ−４），．．．，Ｓ^(G)（ｎ＋２，ｎ−１），Ｓ^(G)（ｎ＋
３，ｎ−４），．．．，Ｓ^(G)（ｎ＋３，ｎ−１）］^T （式１１）

一般に、生類似度ベースの特徴量ベクトルは、分類器に送られる特徴量ベクトルＦ_nの次元数を増加させ、ｒ＝｜Ｆ_n｜である。ＣＳ及びＦＳの核は、「行(row)」核、ＤＣＳ核及びＳＳ核の利点を組み合わせたものである。具体的には、「行」核は現在のサブセットを過去及び未来のサブセットと比較する。ＤＣＳ核は、現在のサブセットを用いず、過去と未来のサブセットを互いに比較する。ＳＳ核は、現在、過去及び未来のサブセットをこれらのすぐ隣にあるサブセットと比較する。ＦＳ核は、現在のサブセットのＬ個のフレーム内にある全てのデータサブセットを比較することによってこの情報の全てを直接組み合わせる。このように、現在のサブセットは、ペアワイズのサブセット間類似度の総合的な局所的特徴付け（ローカルキャラクタリゼーション）に基づいてセグメント境界として分類される。現在のサブセットは、過去及び未来のサブセットと直接比較される。同様に、現在のサブセットの時間的距離Ｌ内の過去及び未来のサブセットが比較される。これらの特徴量を監督付き分類と組み合わせることにより、メディアセグメント境界の特徴付けのロバスト性をより高いものにし、メディアセグメンテーションのパフォーマンスを高めることができる。

本発明の１つの実施の形態では、特徴量ベクトルは１つ以上の類似度マトリックスから同時に得られた値を含む。あるいは、これらの類似度マトリックスを大きな次元ｕの単一の類似度マトリックスに埋め込むことができる。よって、１つの実施の形態では、音声と映像の混合データストリームを、一方は音声用、他方は映像用といった２つの類似度マトリックスによって表すことができ、これらは共に特徴量ベクトルに貢献する。あるいは、他の実施の形態では、音声と映像の値をｕ次元の類似度マトリックスに入力する。他の実施の形態では、「核ベースの」特徴量ベクトルを使用して、１種類以上の核からのノベルティスコアが特徴量ベクトルに貢献する。

メディアセグメンテーションのための分類器の使用
本発明の１つの実施の形態では、トレーニングデータのセット内の各データサブセットに対して特徴量ベクトルを計算する。次に、テストデータの各データサブセットに対して特徴量ベクトルを計算し、監督付き分類器を用いてデータサブセットをカット境界又は非境界として分類する（図６は、分類器を用いて、テストデータから得られた特徴量ベクトルをトレーニングデータから生成された特徴量ベクトルと比較する態様を示す図である）。例えば、ｋＮＮ分類器を用いて、検討中のテストデータサブセットに最も近い特徴量ベクトルを有するｋ個のトレーニングサブセットを選択する。これらのｋ個の最近隣のサブセットのうち十分に多い数が境界である場合、このサブセットを境界として選択する。ｋＮＮ分類の感度は、整数パラメータκ（１≦κ≦ｋ）を用いて制御される。トレーニングデータ内のベクトルＦ_nのｋ個の最近隣値のうち少なくともκ個が境界であるとわかった場合、データサブセット「ｎ」をそれぞれ境界又は非境界としてラベル付けする。図７乃至図１０に示す本発明の実施の形態では、κを変化させて再現率対適合率の曲線を生成している。同一のスキームを用いて複数種類の境界を区別することができる。１つの実施の形態では、バイナリの分類器を繰り返し使用し、クラスの数が２を上回る一般的なケースに拡張することができる。あるいは、２つ以上のクラス間で分類を行うように単一の分類器を学習させることができる。本発明の１つの実施の形態において、分類器は各トレーニングデータサブセットに関連する特徴量ベクトルを学習し、各テストデータサブセットに関連する特徴量ベクトルを検証する。この方法を使用して、境界と非境界の区別に加え、異なる種類の境界を区別することもできる。これには２つのアプローチが可能である。一方では、複数の回路を持つ分類器を用い、各サブセットを非境界として、又は境界の種類の１つとして分類する。もう一方のアプローチでは、バイナリの分類器を用いてこの方法を繰り返し適用する。最初に境界と非境界を区別し、次いで、１つの種類の境界を全ての他の種類から区別し、全ての種類の境界が考慮されるまでこれを繰り返す。この方法を用いて、ビデオにおけるカット境界フレーム、段階的な境界フレーム及び非境界フレームを区別した。

カット境界の検出実験
以下の実験において、本明細書に開示される類似度ベースのセグメンテーション方法が本発明の１つの実施の形態として適用され、ビデオデータストリーム内のカット境界が決定される。各ビデオフレームをデータサブセットとみなし、フレームを表すヒストグラムをＹＵＶ色空間において抽出する。各フレームに対し、グローバルＹＵＶヒストグラム及びブロックＹＵＶヒストグラムを一様な４×４グリッドを用いて抽出する。グローバルヒストグラムデータＳ^(G)及びブロックヒストグラムデータＳ^(B)のための個別の類似度マトリックスを計算する。監督付きバイナリｋＮＮ分類を用いて、各フレームをカット境界又は非境界としてラベル付けする。これにより、種々の核を比較するための一貫した境界検出スキームが生じる。Ｓ^(G)及びＳ^(B)から計算したフレーム指標付きデータを連結してＦ_nを生成し、これを用いてｋＮＮ分類器を学習させてテストし、カット（急な）セグメント境界を検出する。テストには、ショット境界検出作業用のＴＲＥＣＶＩＤ ２００２の報告されたテストデータと評価ソフトウェアを利用した。ＴＲＥＣＶＩＤは大規模な距離ベースの評価であり、ビデオ分析で種々のシステムの比較に用いられる標準データを提供する。カット検出の平均の再現率（式１２で定義）及び適合率（式１３で定義）がそれぞれ０．８６及び０．８４であることが、ＴＲＥＣＶＩＤ ２００２からわかっている。テストセットは、手動のグランドトルース(manual ground truth)により、ほぼ６時間のビデオ及び１４６６のカット遷移から成る。ｋＮＮトレーニングには交差検定を使用し、テストセット内の残りのビデオを用いて個々の分類器に各ビデオを学習させた。完全なテストセットのためにこれらの結果を組み合わせた。一貫してｋ＝１１であった。
再現率＝正しいとみなした境界セグメントの数／（正しい境界セグメントの数＋見落とし
た境界セグメントの数） （式１２）
適合率＝正しいとみなした境界セグメントの数／（正しい境界セグメントの数＋不正確な
境界セグメントの数） （式１３）

核ベースの特徴量ベクトル
Ｌ＝２，３，４，５の範囲の核に対応するｑ＝４を有するショット境界検出のためのノベルティ特徴量を使用した。各Ｌに対し、フレーム指標付き核相関を、式６のＳ^(G)及びＳ^(B)を用いて個々に計算した。これらの実験では、式２の類似度測度を用いてＳ^(G)及びＳ^(B)を計算した。これらのノベルティスコアを連結し、これにより、グローバルヒストグラム特徴量とブロックヒストグラム特徴量の双方のために各ビデオフレームに対し４つのノベルティスコアを生じた。式１４に記載の各ビデオフレーム”ｎ”を表すため、このデータを組み合わせて単一の８×１特徴量ベクトルを生じた。この例は、ｒ（連結されて特徴量ベクトルを生じたノベルティスコアの数）がｑを上回る実施の形態を示しており、ここでｒはｑの２倍である。
Ｆ_n＝［ｖ₂ ^(G)（ｎ），ｖ₃ ^(G)（ｎ），ｖ₄ ^(G)（ｎ），ｖ₅ ^(G)（ｎ），ｖ₂ ^(B)
（ｎ），ｖ₃ ^(B)（ｎ），ｖ₄ ^(B)（ｎ），ｖ₅ ^(B)（ｎ）］^T （式１４）
式中、ｖ_L ^(G)は核幅Ｌを有するＳ^(G)を用いて計算されたノベルティスコアを示し、ｖ_L ^(B)は核幅Ｌを有するＳ^(B)を用いて計算されたノベルティスコアを示す。本発明の本実施の形態では、入力データ｛Ｆ_n：ｎ＝１，．．．，Ｎ｝を「グランドトルース」クラスラベル付けと共に使用し、ｋＮＮ分類器を学習させる。

図７は、Ｋ_FS（”○”）、Ｋ_CS（”×”）、Ｋ_SS（”□”）及びＫ_DCS（”＋”）の再現率及び適合率の値を示している。最高のパフォーマンスはＫ_CS及びＫ_DCSにより達成される。前述のように、Ｋ_CSは、Ｓ内のセグメント境界によって生じる予想パターンのための整合フィルタである。Ｋ_CS及びＫ_DCSの双方は、複数の時間尺度において明白な、セグメント間の相違度を強調している。ユークリッドの相違度測度を選択したため、Ｋ_FSのパフォーマンスは最も悪い。Ｋ_FSは、コサイン類似度測度のような正及び負の値をとる相違度測度により適している。

生類似度ベースの特徴量ベクトル
別の実験において、ｋＮＮ分類器への入力として生のペアワイズ類似度データを用いた際のパフォーマンスを調べた。本発明の本実施の形態では、２つの類似度マトリックスＳ^(G)及びＳ^(B)を用いてＦ_nを形成する。各核に対し、Ｌ＝５である場合に対応するノベルティスコアに貢献するＳ^(G)及びＳ^(B)の要素から入力特徴量ベクトルを構築した。例えば、ＣＳ特徴量に関しては、ｎ番目のフレームは式１５に示す列ベクトルによって表される。

この結果は図８からわかる。図８は、異なる核相関関数を用いた生類似度ベースの特徴量ベクトルの適合率対再現率を示しており、（×）はＫ_CS、（○）はＫ_FS、（□）はＫ_SS、（＋）はＫ_DCS、（△）はＫ_ROWを示す。この場合、ＦＳデータに含まれる付加的な類似度情報がパフォーマンスを改善している。しかし、ＳＳ方法はＣＳ特徴量よりもパフォーマンスに優れている。カット検出のパフォーマンスは主に一次（隣接フレーム）類似度に依存しており、これはＣＳ特徴量やＤＣＳ特徴量によって強調されないため、この結果は意外ではない。図８は、先に提案した「行」特徴量核（Ｋ_ROW）のパフォーマンスの比較もしており、各フレームｎは式１６に示すような２Ｌ×１ベクトルによって表される。
Ｆ_n＝［Ｓ^(G)（ｎ，ｎ−１），Ｓ^(G)（ｎ，ｎ−２），．．．，Ｓ^(G)（ｎ，ｎ−Ｌ），
．．．，Ｓ^(B)（ｎ，ｎ−１），Ｓ^(B)（ｎ，ｎ−２），．．．，Ｓ^(B)（ｎ，
ｎ−Ｌ）］^T （式１６）

全ての方法が、ｋＮＮ分類器への入力として高レベルのパフォーマンスを示している。図７及び図８を比較すると、類似度ベースの特徴量の方がより優れたカット境界検出のパフォーマンスを生じている。また、類似度ベースの特徴量のなかでもＦＳデータは最高の結果をもたらしており、先に用いた行ベースの特徴量に比べてはるかに改善している。

類似度の測度
別の実験において、異なる類似度測度を比較する。図９は、ＴＲＥＣＶＩＤ ２００３テストセットを用いたカット検出のパフォーマンスを示している。すなわち、図９は、Ｋ_FS及び異なる類似度測度を類似度マトリックスの生成に用いた生類似度ベースの特徴量ベクトルの適合率対再現率を示しており、（×）はＤ_Mx２、（○）はＤ_L１、（□）はＤ_L２を示す。本発明の本実施の形態では、生のＦＳ特徴量を用い、Ｌ＝５を有する特徴量ベクトルを生成した。各曲線は類似度測度の異なる選択に対応している。式２のＬ¹測度を用いた結果を（○）で示す。（×）で示される曲線は、式５に与えられたＭχ²測度を用いている。（□）で示される曲線は式３のＬ²測度に対応している。このプロットは、Ｄ_Mχ２を使用した場合にパフォーマンスが著しく改善したことを示している。また、Ｄ_L１測度はＤ_L２測度よりもパフォーマンスに優れている。図１０は、２００３ ＴＲＥＣＶＩＤコンテストからの他の点を有するプロットにおいてＤ_L１測度及びＤ_Mχ２測度を用いた際のパフォーマンスを示している。すなわち、図１０は、Ｋ_FS及び異なる類似度測度を類似度マトリックスの生成に用いた生類似度ベースの特徴量ベクトルの適合率対再現率を示しており、（×）はＴＲＥＣＶＩＤコンテスト、（○）はＤ_Mx２、（□）はＤ_L１を示す。双方の曲線は、このコンテストに参加した他のグループに対して高いレベルのパフォーマンスを示している。

本発明に従ったデータストリームの境界を検出する発明のブロック図である。 データストリーム内のサブセット要素”ｉ”と隣接するサブセット要素”ｊ”との間の関係と、サブセット要素の各対の低レベル特徴量を比較して記憶する類似度マトリックスＳ（ｉ，ｊ）におけるこれらの位置とを示す図である。 Ｌ＝４である場合のセグメント境界検出のために提案された核を示す図であり、（Ａ）はＫ_CS核、（Ｂ）はＫ_FS核、（Ｃ）はＫ_SS核、（Ｄ）はＫ_DCS核を示している。 類似度マトリックス（Ｓ）に核相関関数（ここではｑ＝２と示され、Ｋ_FSに対してＬ＝２及びＬ＝３である）を適用することによってノベルティスコア（ｖ）を生成することを示す図である。 サブセット要素”ｎ”とｎ番目の要素Ｆ_nの特徴量ベクトルとの関係を示す図である。 分類器を用いて、テストデータから得られた特徴量ベクトルをトレーニングデータから生成された特徴量ベクトルと比較する態様を示す図である。 異なる核相関関数を用いた核ベースの特徴量関数の適合率対再現率を示しており、（×）はＫ_CS、（○）はＫ_FS、（□）はＫ_SS、（＋）はＫ_DCSを示す。 異なる核相関関数を用いた生類似度ベースの特徴量ベクトルの適合率対再現率を示しており、（×）はＫ_CS、（○）はＫ_FS、（□）はＫ_SS、（＋）はＫ_DCS、（△）はＫ_ROWを示す。 Ｋ_FS及び異なる類似度測度を類似度マトリックスの生成に用いた生類似度ベースの特徴量ベクトルの適合率対再現率を示しており、（×）はＤ_Mx２、（○）はＤ_L１、（□）はＤ_L２を示す。 Ｋ_FS及び異なる類似度測度を類似度マトリックスの生成に用いた生類似度ベースの特徴量ベクトルの適合率対再現率を示しており、（×）はＴＲＥＣＶＩＤコンテスト、（○）はＤ_Mx２、（□）はＤ_L１を示す。Ｄ_Mx２及びＤ_L１の類似度測度を有するｋＮＮ分類器を使用した。

Claims (31)

1. データのストリームにおけるセグメント境界の位置の決定方法であって、
   （ａ）前記データのストリーム内のデータサブセットを、現在及び未来のデータサブセットの群から選択された１つ以上のデータサブセットと比較することによって１つ以上の類似度値を決定することであって、前記未来のデータサブセットが前記データのストリーム内の前記データサブセットよりも時間的に後に生じ、前記現在のデータサブセットが前記データのストリーム内の前記データサブセットと同時に生じる、前記１つ以上の類似度値を決定することと、
   （ｂ）類似度値の１つ以上のセットを分類することと、
   を含む、前記方法。
2. 前記セグメント境界の決定が、
   （ｃ）前記データのストリーム内の前記データサブセットを、過去のデータサブセットの群から選択された１つ以上のデータサブセットと比較することによって１つ以上の類似度値を決定することであって、前記過去のデータサブセットが前記データのストリーム内の前記データサブセットよりも時間的に前に生じる、前記１つ以上の類似度値を決定することと、
   （ｄ）前記未来のデータサブセットと比較された前記データサブセットの少なくとも１つの類似度値を含む前記類似度値から特徴量ベクトルを生成することと、
   （ｅ）前記特徴量ベクトルを分類して前記セグメント境界を決定することと、
   を更に含む、請求項１の方法。
3. 前記ステップ（ａ）及び前記ステップ（ｃ）が、比較されている前記データサブセットをオフセットによって分離することを更に含み、前記オフセットが０と最大オフセットＬとの間で変更され、前記比較が前記変更されたオフセットのうちの１つ以上で行われる、請求項２の方法。
4. 前記ステップ（ａ）、前記ステップ（ｃ）及び前記ステップ（ｄ）が、
   （ｆ）前記データのストリーム内の前記データサブセットからのＬ個のデータサブセット内の過去及び未来のデータサブセットを、過去及び未来のデータサブセットの群から選択された１つ以上の類似度値と比較することと、
   （ｇ）前記データサブセットの前記類似度値、ならびに前記過去及び未来のデータサブセットの類似度値から特徴量ベクトルを生成することと、
   を更に含む、請求項３の方法。
5. 前記ステップ（ｅ）が、
   トレーニングデータ及びグランドトルースの１つ以上のセットから得られた１つ以上の特徴量ベクトルに基づいて１つ以上の分類器を学習させることと、
   １つ以上の学習した前記分類器に基づいて、前記データサブセットからの前記特徴量ベクトルを境界及び非境界として分類することと、
   を更に含む、請求項４の方法。
6. 前記ステップ（ｄ）において、前記データサブセットと未来のデータサブセットとの間の比較の類似度値が前記特徴量ベクトルに正に貢献し、前記データサブセットと過去のデータサブセットとの間の比較の類似度値が前記特徴量ベクトルに負に貢献する、請求項４の方法。
7. 前記特徴量ベクトルの決定が、
   前記類似度値を１つ以上の類似度マトリックスに記憶することと、
   異なる範囲Ｌを有する１つ以上の核関数を前記類似度マトリックスに適用し、前記類似度マトリックスから異なる類似度値を抽出することと、
   を更に含む、請求項４の方法。
8. ｑ個の異なるＬの値に対してノベルティスコアを生成し、これにより、ｑ個のノベルティスコアが、異なる範囲Ｌを有するｑ個の核関数を前記類似度マトリックスに適用することによって生じる、請求項７の方法。
9. 前記特徴量ベクトルが前記ｑ個のノベルティスコアを連結することによって生成される、請求項８の方法。
10. 前記特徴量ベクトルが、前記核関数の各非ゼロ値に対する類似度マトリックスの生のペアワイズデータを抽出することにより生成される、請求項７の方法。
11. 前記ステップ（ａ）が、
    過去、未来及び現在のデータサブセットの１つ以上の低レベル特徴量を生成することと、
    「修正カイ２乗」測度、「カイ２乗」測度、Ｌ¹及びＬ²の群から選択された測度によって前記低レベル特徴量の前記ペアワイズ比較から前記類似度値を計算することであって、Ｌ¹が、前記データサブセットの低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との差の係数の合計であり、Ｌ²が、前記データサブセットの前記低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との間の差の２乗の２乗根の合計である、前記類似度値の計算と、
    を更に含む、請求項４の方法。
12. 前記ステップ（ａ）が、
    過去、未来及び現在のデータサブセットの１つ以上の低レベル特徴量を生成することと、
    「修正カイ２乗」測度、「カイ２乗」測度、Ｌ¹及びＬ²の群から選択された測度によって前記低レベル特徴量の前記ペアワイズ比較から前記類似度値を計算することであって、Ｌ¹が、前記データサブセットの低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との差の係数の合計であり、Ｌ²が、前記データサブセットの前記低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との間の差の２乗の２乗根の合計である、前記類似度値の計算と、
    を更に含む、請求項９の方法。
    
13. 前記ステップ（ａ）が、
    過去、未来及び現在のデータサブセットの１つ以上の低レベル特徴量を生成することと、
    「修正カイ２乗」測度、「カイ２乗」測度、Ｌ¹及びＬ²の群から選択された測度によって前記低レベル特徴量の前記ペアワイズ比較から前記類似度値を計算することであって、Ｌ¹が、前記データサブセットの低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との差の係数の合計であり、Ｌ²が、前記データサブセットの前記低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との間の差の２乗の２乗根の合計である、前記類似度値の計算と、
    を更に含む、請求項１０の方法。
    
14. データのストリームにおけるセグメント境界の位置の決定方法であって、
    （ａ）前記データのストリームにある１つ以上のデータサブセットの１つ以上の類似度値を、近隣データの１つ以上のサブセットと比較して計算することと、
    （ｂ）前記類似度値に基づいて１つ以上の類似度マトリックスを生成することと、
    （ｃ）異なる範囲Ｌを有する１つ以上の核関数を前記類似度マトリックスに適用し、各Ｌに対して１つ以上のノベルティスコアを生成することと、
    （ｄ）ｑ＞１であるｑ個の異なるＬの値に対して対応するｑ個のノベルティスコアを入力して特徴量ベクトルを生じるようにＬを変更することと、
    （ｅ）前記特徴量ベクトルを分類して前記セグメント境界の位置を決定することと、
    を含む、前記方法。
15. データのストリームにおけるセグメント境界の位置の決定方法であって、
    （ａ）近隣データの１つ以上のサブセットと比較して、データのストリームにある１つ以上のデータサブセットの１つ以上の類似度値を計算することと、
    （ｂ）前記類似度値に基づいて１つ以上の類似度マトリックスを生成することと、
    （ｃ）相互類似度核及び完全な類似度核の群から選択された核関数を前記類似度マトリックスに適用することと、
    （ｄ）前記類似度マトリックスの生のペアワイズデータを抽出し、核関数の各非ゼロ値に対して特徴量ベクトルを生じることと、
    （ｅ）前記特徴量ベクトルを分類して前記セグメント境界の位置を決定することと、
    を含む、前記方法。
16. 前記核関数が相互類似度核及び完全類似度核の群から選択される、請求項１４の方法。
17. 前記ステップ（ａ）が、
    過去、未来及び現在のデータサブセットの１つ以上の低レベル特徴量を生成することと、
    「修正カイ２乗」測度、「カイ２乗」測度、Ｌ¹及びＬ²の群から選択された測度によって前記低レベル特徴量の前記ペアワイズ比較から前記類似度値を計算することであって、Ｌ¹が、前記データサブセットの低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との差の係数の合計であり、Ｌ²が、前記データサブセットの前記低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との間の差の２乗の２乗根の合計である、前記類似度値の計算と、
    を更に含む、請求項１４の方法。
18. 前記ステップ（ａ）が、
    過去、未来及び現在のデータサブセットの１つ以上の低レベル特徴量を生成することと、
    「修正カイ２乗」測度、「カイ２乗」測度、Ｌ¹及びＬ²の群から選択された測度によって前記低レベル特徴量の前記ペアワイズ比較から前記類似度値を計算することであって、Ｌ¹が、前記データサブセットの低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との差の係数の合計であり、Ｌ²が、前記データサブセットの前記低レベル特徴量と前記過去、未来及び現在のデータサブセットの前記低レベル特徴量との間の差の２乗の２乗根の合計である、前記類似度値の計算と、
    を更に含む、請求項１５の方法。
19. 前記ステップ（ｂ）の前記類似度マトリックスは非対称である、請求項１４の方法。
20. 前記ステップ（ｂ）の前記類似度マトリックスは非対称である、請求項１５の方法。
21. ステップ（ｄ）において、非連続的なＬの値からの前記ノベルティスコアを入力して特徴量ベクトルを生じる、請求項１４に記載の方法。
22. １種類以上の核関数を前記類似度マトリックスに適用することによって前記特徴量ベクトルが生成される、請求項１４に記載の方法。
23. ビデオにおけるショットセグメンテーションを決定する、請求項１４の方法。
24. ビデオにおけるショットセグメンテーションを決定する、請求項１５の方法。
25. 前記ステップ（ｂ）で、ｋＮＮ分類器を用いて前記セグメントを境界及び非境界として決定する、請求項４に記載の方法。
26. データサブセットを近隣のデータサブセットと比較してセグメント境界を決定する方法であって、
    （ａ）１つ以上のデータサブセットを近隣データの１つ以上のサブセットと比較することに基づいて１つ以上の類似度値を計算する手段と、
    （ｂ）前記類似度値から１つ以上の類似度マトリックスを生成する手段と、
    （ｃ）前記類似度マトリックスから生のペアワイズデータを抽出する手段であって、核関数の各非ゼロ値に対して前記マトリックスの前記生のペアワイズデータを抽出し、前記核関数が相互類似度核及び完全類似度核の群から選択される、前記手段と、
    （ｄ）抽出した前記生のペアワイズデータから特徴量ベクトルを生成する手段と、
    （ｅ）分類器を用いて前記特徴量ベクトルを分類する手段と、
    を含む、前記方法。
27. 前記ステップ（ｅ）が、
    トレーニングデータ及びグランドトルースクラスラベリングの１つ以上のセットから得られた１つ以上の特徴量ベクトルを用いて分類器を学習させる手段と、
    学習した前記分類器を用いて前記特徴量ベクトルを分類し、前記セグメント境界を決定する手段と、
    を更に含む、請求項２６に記載の方法。
28. テストデータのストリームにおけるセグメント境界を決定する機能を果たすようにコンピュータによって実行可能な命令のプログラムであって、前記機能が、
    （ａ）１つ以上のデータサブセットを近隣データの１つ以上のサブセットと比較することに基づいて１つ以上の類似度値を計算するステップと、
    （ｂ）前記類似度値から１つ以上の類似度マトリックスを生成するステップと、
    （ｃ）相互類似度核及び完全類似度核の群から選択された１つ以上の核関数を前記類似度マトリックスに適用することによって特徴量ベクトルを生成するステップと、
    （ｄ）データ及びグランドトルースクラスラベリングの１つ以上のトレーニングセットから生成された特徴量ベクトルを用いて分類器を学習させるステップと、
    （ｅ）学習した前記分類器を用いたテストデータ及び類似する特徴量ベクトルから特徴量ベクトルを分類し、前記セグメント境界を決定するステップと、
    を含む、プログラム。
29. 前記ステップ（ｃ）が、
    １つ以上の核相関関数を１つ以上の類似度マトリックスに適用して１つ以上のノベルティスコアを生成することと、
    異なる核相関関数の幅に対して得られたノベルティスコアを入力することによって前記特徴量ベクトルを生成することと、
    を更に含む、請求項２８のプログラム。
30. 前記ステップ（ｃ）が、
    １つ以上の核相関関数を１つ以上の類似度マトリックスに適用することと、
    前記核相関関数の各非ゼロ値に対し、前記類似度マトリックスの前記生のペアワイズデータを抽出して前記特徴量ベクトルを生成することと、
    を更に含む、請求項２８のプログラム。
31. データのストリームにおける境界及び非境界を識別するシステムであって、前記識別が、
    ａ）前記データのストリームにおける各データサブセットに対して類似度値を計算することができ、１つ以上の類似度マトリックスを生成することができ、核関数を前記マトリックスに適用することができ、特徴量ベクトルを生成することができ、前記データサブセットを分類することができる１つ以上のプロセッサと、
    ｂ）前記データのストリームにおける各データサブセットに対して前記類似度値を生成するステップと、１つ以上の類似度マトリックスを作成するステップと、核関数を前記マトリックスに適用するステップと、特徴量ベクトルを生成するステップと、前記データサブセットを境界及び非境界として分類するステップを、前記１つ以上のプロセッサによって処理される際にシステムに行わせるオペレーションが記憶されたマシン可読媒体と、
    を含む、前記システム。

Images