(57)【要約】  同一または類似の有用信号を費用効率が高く自動的に検出することを可能にする、有用信号用のフットプリントを生成する方法であって、有用信号はその周波数、例えば音声周波数を含むスペクトラムの長期にわたる展開を表わし、フットプリントは人間のユーザーには知覚できない有用信号の変更に対して強固であり、有用信号の一部を含む少なくとも１つのデータセットは所定の解析命令に従って解析器によって処理され、そして解析器は、処理の結果として、処理されたデータセットに従属し、それを識別するフットプリント・データ・ベクトルを出力する方法。【選択図】  図２
2008529047.tif 000002
【特許請求の範囲】
【請求項１】
有用信号用のフットプリントを生成する方法であって、前記有用信号は有用信号周波数、例えば音声周波数を含むスペクトラムの長期にわたる展開を表わし、
前記有用信号の一部を含む少なくとも１つのデータセットが所定の解析命令に従って解析器によって処理され、前記解析器は、前記処理の結果として、前記処理されたデータセットに従属し、それを識別するフットプリント・データ・ベクトルを出力することを特徴とする方法。
【請求項２】
前記解析命令が、人間による前記有用信号の受信中に人間の感覚で知覚できる前記データセットの特性に関して前記データセットを処理することを特徴とする請求項１に記載の方法。
【請求項３】
前記データセットが２つ以上の解析器および／または２つ以上の解析命令によって処理され、前記フットプリント・データ・ベクトルが前記解析器および／または解析命令による前記処理の結果を表わすことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記有用信号の２つ以上の重複または非重複データセットが処理され、前記フットプリント・データ・ベクトルが前記データセットの前記処理の結果を表わすことを特徴とする請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記データセットが前記有用信号の有用信号フレームを含み、前記解析命令が前記データセットと所定のパターン辞書（前記パターン辞書はパターンフレームの番号付きリストを含む）の各パターンフレームとの比較を含み、前記有用信号フレームと前記パターンフレームの各々との類似点の推定を含み、前記解析器が、前記データセットの前記処理の前記結果として、前記有用信号フレームとの最高の類似点を有すると決定されるパターンフレームの番号を出力することを特徴とする請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記有用信号フレームに有用信号フレームベクトルを割り当て、前記パターンフレームの各々にパターン・フレーム・ベクトルを割り当て、そして有用信号フレームおよびパターンフレームの各対の前記類似点が、前記有用信号フレームベクトルと前記関連するパターン・フレーム・ベクトルとの間の距離を計算することによって決定されることを特徴とする請求項５に記載の方法。
【請求項７】
前記解析器がスペクトル解析器であり、前記スペクトル解析器は、線形予測アルゴリズムを用いて、前記フレームについて平滑化したスペクトルパラメータ、具体的にはケプストラム係数を計算することを特徴とする請求項５または６に記載の方法。
【請求項８】
前記ケプストラム係数が、前記パターン辞書と、前記パターン辞書の基準ベクトル間の距離の行列とを用いて符号化されることを特徴とする請求項７に記載の方法。
【請求項９】
前記解析器が前記データセットの各々の周波数スペクトルを処理する周波数フィルタを備え、前記周波数フィルタの各々は前記データセットの前記周波数スペクトルから特定のトーンをフィルタに通すように構成されて、一組のトーンを生じ、そして前記解析命令が、前記データセットの各々の前記トーンの各々の振幅の計算を含むことを特徴とする請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記解析命令が、特に前記有用信号のメロディーおよび／または１つ以上のトーンの期間を決定するために、特にリズムおよび／または前記有用信号の１分当たりのビートを表わすｂｐｍ値を決定するために、様々なトーンの発生周波数を計算する命令をさらに含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記解析器が前記有用信号をダウンサンプリングする信号デシメータを備え、前記有用信号のエネルギーの少なくとも９０％を含む周波数帯が保たれることを特徴とする請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
前記解析器が、エネルギーが所定の閾値未満であるデータセットが更なる処理から除外されるように前記有用信号を処理する、能動フレーム検出器を備えることを特徴とする請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
入力有用信号と同一または類似である所定のセットの有用信号から有用信号を識別する方法であって、前記有用信号の各々に請求項１〜１２のいずれか一項の方法によって生成されるフットプリントが割り当てられ、
識別子ユニットが、
入力として前記入力有用信号の前記フットプリント・データ・ベクトルを受信し、
前記入力有用信号と前記セットの有用信号の１つの各対について、前記セットの関連するフットプリント・データ・ベクトル間の所定の距離命令による距離を計算し、
前記識別の結果として、距離が所定の閾値未満である有用信号のリストを戻す方法。
【請求項１４】
前記距離を計算する前記工程が、
ａ．前記有用信号のサブベクトルがありのままの距離を計算するために距離計算で用いられ、ありのままの距離が第１閾値未満である前記有用信号は一時的に識別される第１サブステップと、
ｂ．前記一時的に識別された有用信号の前記入力有用信号までの前記距離は前記完全な有用データベクトルを用いて計算される第２サブステップと、
を含むことを特徴とする請求項１〜１３のいずれか一項に記載の方法。
【請求項１５】
プログラマブルコンピュータ、プログラマブル・コンピュータ・ネットワーク、または別のプログラマブル装置上で動くように構成される、請求項１〜１２のいずれか一項に記載の方法を実行するコンピュータプログラム。
【請求項１６】
プログラマブルコンピュータ、プログラマブル・コンピュータ・ネットワーク、または別のプログラマブル装置上で動くように構成される、請求項１３または１４に記載の方法を実行するコンピュータプログラム。
【請求項１７】
前記コンピュータプログラムがコンピュータ可読媒体に格納される請求項１５または１６に記載のコンピュータプログラム。
【請求項１８】
請求項１６に記載のコンピュータプログラムがインストールされる、請求項１〜１２のいずれか一項に記載の有用信号のフットプリントを生成する方法を実行する装置、具体的には、プログラマブルコンピュータ、プログラマブル・コンピュータ・ネットワーク、または別のプログラマブル装置。
【請求項１９】
請求項１７に記載のコンピュータプログラムがインストールされる、請求項１３または１４に記載の所定のセットの有用信号から有用信号を識別する方法を実行する装置、具体的には、プログラマブルコンピュータ、プログラマブル・コンピュータ・ネットワーク、または別のプログラマブル装置。
【請求項２０】
フットプリント・データ・ベクトルを格納するデータベースが前記装置に接続され、前記装置は前記データベースにアクセスするように構成されることを特徴とする請求項１９に記載の装置を備える構成。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は有用信号用のフットプリントを生成する方法に関する。
【背景技術】
【０００２】
本明細書で用いる用語「有用信号」は、最終的にはユーザー、具体的には人間のユーザーによって受信されることを目的とするデータを表わす信号を意味している。有用信号の一般的な例は、音声周波数のスペクトル（例えば、電話用の３００Ｈｚ〜３４００Ｈｚ、またはクラシックコンサートの高品質再生用の１０Ｈｚ〜２０ｋＨｚのスペクトル）の長期にわたる展開を表わす音声信号であり、あるいは、有用信号の周波数が、例えばテレビまたは映画の画面に表示するために、画像特性によって規定され、０Ｈｚ（空の像）と、画面の行列および動画の垂直走査周波数によって決定される最大周波数、例えば多くのテレビシステムの場合は６．５ＭＨｚとの間にあるビデオ信号（単一像ならびに動画）である。  
【０００３】
また、有用信号は、テキスト文字列または他の表現を表わす信号、および特に人間の知覚を直接または間接に対象とする、このような信号をさらに展開させたものも含む。
【０００４】
有用信号は、例えばラジオまたはテレビ信号のように、アナログ方式で表わされ、あるいはディジタル信号、例えばアナログ信号をサンプリングし、続いて量子化し、そして符号化することによって形成されるＰＣＭ信号として表わされる。どんな場合でも、有用信号は、それが単一の楽曲、またはこのようなトラックの集まり、単一像または完全な映画であっても、関連データセットの完全な表現を含むように意図されているものである。
【０００５】
例えば、特定の信号を他の信号から識別するために、または２つの有用信号の同一性を検査するために、有用信号を互いに比較することが一般に必要である。
【０００６】
２つのディジタル信号の同一性を検査する明らかな方法は、ビット単位の比較である。しかしながら、この手順は多くの場合に有用ではない。信号が互いに全く一致するように、信号は複写処理によって複製されたと想定する。第２信号が次に変更、例えばダウンロード用として広く知られているＭＰ３フォーマットに変換される場合は、解凍後に、両信号の比較によって両信号は異なるという結果を生じる。ディジタル／アナログおよびアナログ／ディジタル変換の場合も同じである。
【０００７】
さらに、本出願人が知っている限りでは、同一ではないが互いに類似しており、類似点が人から観て分かる有用信号を自動的に識別する既知の方法は無い。例えば、メロディーまたはリズムが互いに類似する音楽トラックを識別する技術的方法は知られていない。
【０００８】
通常、有用信号の自動処理を可能にするために、識別データを信号とともに提供しなければならない。例として、作者を表わす列のデータフィールド、記録日付、音楽の種類などが音楽トラックに加えられる。同一または類似の信号を決定するために、これらの追加データフィールドを処理しなければならない。それでも、類似信号、例えばメロディーが類似しているクラシックおよびロック音楽を識別することは困難である。
【０００９】
複数の面において有用信号を識別するデータを以下「フットプリント」と称する（このようなデータは「フィンガープリント」と称することもある）。具体的には、フットプリントデータは、人間のユーザーによる信号の受信中に人間の知覚に関する信号を識別する。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の目的は、有用信号、特に音声信号用のフットプリントを生成する方法およびその装置を提供することであり、この方法は、フットプリントが人間のユーザーには知覚できない有用信号の変更に対して強固である、同一または類似の有用信号を費用効率が高く自動的に検出することを可能にし、そして同一または類似のフットプリントを効率的に検出することを可能にする。
【課題を解決するための手段】
【００１１】
この目的は、請求項１の特徴を備える方法および請求項１８の特徴を備える装置によって解決される。
【００１２】
本発明によれば、有用信号の一部を含む少なくとも１つのデータセットは所定の解析命令に従って解析器によって処理され、解析器は、処理の結果として、処理されたデータセットに従属し、それを識別するフットプリント・データ・ベクトルを出力する。
【００１３】
本発明の基本的な概念の１つは、有用信号解析命令によって有用信号またはその一部を処理する結果として、フットプリントを生成することである。従って、フットプリントは有用信号自体の特性を表すフットプリント・データ・ベクトルを含む。人間の管理者が記述データを有用信号に手動で追加することは要求されない。フットプリントが有用信号の特性に関連するので、同一または類似の有用信号は、関連するフットプリントの適切な比較によって識別され得る。
【００１４】
詳細に言えば、本発明によれば、有用信号、特に音声信号用のフットプリントを生成する方法では、有用信号は有用信号周波数、例えば音声周波数を含むスペクトルの長期にわたる展開を表わし、有用信号の一部を含む少なくとも１つのデータセットは所定の解析命令に従って解析器によって処理され、解析器は、処理の結果として、処理されたデータセットに従属し、それを識別するフットプリント・データ・ベクトルを出力する。
【００１５】
本発明の方法の好ましい実施形態では、解析命令は、人間による有用信号の受信中に人間の感覚で知覚できるデータセットの特性に関してデータセットを処理する。このようにして、人間の知覚には類似に見える有用信号の識別は有利に可能である。
【００１６】
本発明の方法の別の好ましい実施形態では、データセットは２つ以上の解析器および／または２つ以上の解析命令によって処理され、フットプリント・データ・ベクトルは解析器および／または解析命令による処理の結果を表わす。このようにして、有用信号の２つ以上の特性がフットプリント、例えばメロディーおよびリズム中に表わされる。
【００１７】
本発明の他の実施形態では、有用信号の２つ以上の重複または非重複データセットは処理され、フットプリント・データ・ベクトルはデータセットの処理の結果を表わす。このようにして、フットプリント・データ・ベクトルの信号特性を表わす可能性が非常に大きくなる。
【００１８】
本発明の方法の別の実施形態では、データセットは有用信号の有用信号フレームを含み、解析命令はデータセットと所定のパターン辞書（パターン辞書はパターンフレームの番号付きリストを含む）の各パターンフレームとの比較を含み、有用信号フレームとパターンフレームの各々との類似点の推定を含み、そして解析器は、データセットの処理の結果として、有用信号フレームとの最高の類似点を有すると決定されるパターンフレームの番号を出力する。有利なことに、例えば、特定の種類の信号にとって典型的である有用信号に現れるパターンを既知のパターンにマッピングし、パターンをパターン番号によって置換することが可能である。このようにして、小さいデータセット（一組のパターン番号）を用いて有用信号のより大きいデータセットを特徴付けることが可能である。
【００１９】
別の展開された実施形態では、有用信号フレームに有用信号フレームベクトルを割り当て、パターンフレームの各々にパターン・フレーム・ベクトルを割り当て、そして有用信号フレームおよびパターンフレームの各対の類似点は、有用信号フレームベクトルと関連するパターン・フレーム・ベクトルとの間の距離を計算することによって決定される。このようにして、ベクトル解析によって知られる効率的なアルゴリズムが有利に展開され得る。
【００２０】
さらに別の展開された実施形態では、解析器はスペクトル解析器であり、このスペクトル解析器は、線形予測アルゴリズムを用いて、フレームについて平滑化したスペクトルパラメータ、具体的にはケプストラム係数を計算する。さらに、ケプストラム係数は、パターン辞書と、パターン辞書の基準ベクトル間の距離の行列とを用いて符号化される。ここで、有利なことに、有用信号のトーン関連の特性（例えば、音楽トラック用）を解析し、フットプリントに解析結果を表わすことが可能である。
【００２１】
本発明の方法の他の好ましい実施形態では、解析器はデータセットの各々の周波数スペクトルを処理する周波数フィルタを備え、周波数フィルタの各々はデータセットの周波数スペクトルから特定のトーンをフィルタに通すように構成されて、一組のトーンを生じ、そして解析命令はデータセットの各々のトーンの各々の振幅の計算を含む。このようにして、別のトーン関連の特性のリズムおよびメロディーを容易に解析できる。
【００２２】
本発明の方法の別の実施形態では、解析命令は、特に有用信号のメロディーおよび／または１つ以上のトーンの期間を決定するために、特にリズムおよび／または有用信号の１分当たりのビートを表わすｂｐｍ値を決定するために、様々なトーンの発生周波数を計算する命令をさらに含む。
【００２３】
本発明の方法のさらに別の実施形態では、解析器は有用信号をダウンサンプリングする信号デシメータを備え、有用信号のエネルギーの少なくとも９０％を含む周波数帯は保たれる。これはシステムの残りのハードウェア要件を低くさせる。
【００２４】
本発明の別の実施形態では、解析器は、エネルギーが所定の閾値未満であるデータセットが更なる処理から除外されるように有用信号を処理する能動フレーム検出器を備え、この場合は閾値は平均信号エネルギーにユーザー定義重み係数を乗じることによって得られる。この手順は雑音に起因する誤り検出を防止する。
【００２５】
本発明によれば、入力有用信号と同一または類似である所定のセットの有用信号から有用信号を識別する方法において、有用信号の各々に前の請求項のいずれか一項の方法によって生成されるフットプリントが割り当てられ、この方法は識別子ユニットを含み、識別子ユニットは、
入力として入力有用信号のフットプリント・データ・ベクトルを受信し、
入力有用信号と前記セットの有用信号の１つの各対について、関連するフットプリント・データ・ベクトル間の所定の距離命令による距離を計算し、
識別の結果として、距離が所定の閾値未満である有用信号のリストを戻す。
これは同一または類似の信号の高速かつ確実な識別を可能にする。
【００２６】
前述の方法の好ましい実施形態では、距離を計算する工程は次のサブステップを含む。
第１サブステップで、有用信号のサブベクトルはありのままの距離を計算するために距離計算で用いられ、ありのままの距離が第１閾値未満である有用信号は一時的に識別される。
第２サブステップで、一時的に識別された有用信号の入力有用信号までの距離は完全な有用データベクトルを用いて計算される。有用信号のセットにおいて多数の信号がある場合に、これは類似の有用信号の高速識別を可能にする。
【００２７】
前述の方法はコンピュータプログラムで実行可能であり、このコンピュータプログラムはプログラマブルコンピュータ、プログラマブル・コンピュータ・ネットワーク、または別のプログラマブル装置上で動くように構成される。この構成は本発明の方法を安価、容易に実施、かつ高速の開発を可能にする。具体的には、このようなコンピュータプログラムは、例えばＣＤ-ＲＯＭまたはＤＶＤ-ＲＯＭのようなコンピュータ可読媒体に格納できる。
【００２８】
本発明の方法で用いる装置は、具体的には、コンピュータプログラムがインストールされる、プログラマブルコンピュータ、プログラマブル・コンピュータ・ネットワーク、または別のプログラマブル装置を備え、本発明を実行する。
【００２９】
本発明の更なる特徴および利点は、添付図面と共に本発明の実施形態についての次の説明から明らかになる。
【発明を実施するための最良の形態】
【００３０】
本発明は２つの独立した解析器を提案する。
【００３１】
第１解析器はパターン辞書を用いてベクトル符号化を実行する（図１）。解析シーケンスの各フレームについて、Ｎ＝１２ケプストラム係数から成るＮ次元入力ベクトルが線形予測アルゴリズム（ＬＣＰ）を用いて計算される。
【００３２】
音楽トラックの典型的セットはパターン辞書を構築するために処理された。この有用信号のセットについて、一組の入力ベクトルが生成された。パターン辞書は、コードブック設計用のセントロイド計算（Ｃｅｎｔｒｏｉｄ  Ｃｏｍｐｕｔａｔｉｏｎ  ｆｏｒ  Ｃｏｄｅｂｏｏｋ  Ｄｅｓｉｇｎ）［Ｌ  ラビナー、Ｂ  ヤング著、「音声認識の基本」、ＡＴ＆Ｔ、１９９３年（Ｌ．Ｒａｂｉｎｅｒ，Ｂ．Ｊｕａｎｇ，Ｆｕｎｄａｍｅｎｔａｌｓ  ｏｆ  Ｓｐｅｅｃｈ  Ｒｅｃｏｇｎｉｔｉｏｎ，ＡＴ＆Ｔ，１９９３）］を用いてこのベクトルのセットから構成された。パターン辞書の受入れ可能なサイズ（８１９２基準ベクトル）は実験的に決定された。
【００３３】
次に現在の入力ベクトルは、選択された距離における入力ベクトルに最も近い基準ベクトルによって置換される。このようにして、有用信号の各フレームは基準ベクトルの１つの番号に符号化される。その結果、断片全体はパターン辞書から基準ベクトルのＴａｎ／Ｔｆｒａｍｅ番号のシーケンスとして符号化される。
【００３４】
このアルゴリズムは、音楽ファイルの効率的な符号化を１７，５００を超える圧縮係数で提供する。コンピュータ実施システムでは、ユーザーは、処理される有用信号の特性によって上述のパラメータを設定できる。Ｄコード（Ｄ辞書コード）に基づくフットプリントは広範囲の有用信号（音声、ビデオ、薬など）に適用できる。
【００３５】
音声信号を使用する本発明の好ましい実施形態では、有用信号は個別の断片で解析され、Ｔａｎの各々＝６０秒長さである。各断片について、個別のフットプリントコードが生成される。隣接した断片は１／２Ｔａｎだけ重複するように選ばれる。
【００３６】
信号は周波数８０００Ｈｚでダウンサンプリングされ、これはその周波数を４０００Ｈｚで本質的にカットする。解析される信号間隔はそれぞれＴｆｒ＝０．２秒の順次フレームに分割される。コンピュータ実施システムでは、ユーザーは処理される信号の特性によってこれらのパラメータを最適化することができる。
【００３７】
第２解析器は非均一フィルタバンクのＦＦＴ実施に基づいている（図２）。中心周波数がトーンに対応するフィルタバンクは、次元Ｎｆｆｔ＝６５，５３６であるＦＦＴアルゴリズムを用いて実行される。
【００３８】
フィルタＦｋの中心周波数はノート（トーン）周波数に相当しなければならない。
【数１】
2008529047.tif 000003
【００３９】
フィルタの出力における振幅の時間依存性は、すべてのフレームについて計算され、処理される有用信号フレームのメロディーおよびリズムを推定するために使用される。ここで説明される好ましい実施形態では、推定アルゴリズムが次の工程で実行される。
【００４０】
１）全てのノート（トーン）が単一オクターブに置き換えられ、それらは、
ソースノートの最大振幅Ａ［ｉ］を保ちながら、番号ｉ＝０、１、．．．１１を得る。
【００４１】
２）ノート番号ｎ［ｉ］が振幅の大きいものから順にソートされる。
Ａ［ｎ［０］］＞Ａ［ｎ［１］］＞．．．＞Ａ［ｎ［１１］］
【００４２】
３）３つのノートシーケンスが断片のＫフレームから形成される。
｛ｎ［０，ｋ］｝，｛ｎ［１，ｋ］｝，｛ｎ［２，ｋ］｝，
ここで、ｋ＝０，１，．．．，ｋ−１
【００４３】
４）最初の３つのノートＰｎ［０，ｉ］，Ｐｎ［１，ｉ］，Ｐｎ［２，ｉ］，ｉ＝０，１，．．．，１１の発生周波数が計算され、処理される断片の３６次元ベクトルが計算される。このベクトルは本質的にメロディー推定である（Ｍコード）。
【００４４】
５）この３６次元ベクトルの成分が処理される断片のメロディー推定として記録される。
【００４５】
６）一連のノート時間値がシーケンスｎ［０，ｋ］について計算される。
【００４６】
７）０．２〜４．０秒の時間値の発生周波数から成る１２次元ベクトルが計算される。
【００４７】
８）加重平均間隔が計算され、２０次元リズムベクトルが計算される。
【００４８】
９）１分当たりのビート数（ｂｐｍ）が断片について推定され（これは本質的にテンポ値である）、これは２０次元リズムベクトルの成分とともに記録される。
【００４９】
両方の解析器を備える本発明の実施形態では、次の工程が実行される。
【００５０】
１）最初に有用信号が信号デシメータによって処理され、これは有用信号をダウンサンプリングするが、ソース有用信号のエネルギーの少なくとも９０％を含む周波数帯を保つ。これはシステムの残りのハードウェア要件を低くする。可変数の周波数依存部分を備え、サンプルレートが可変であるフィルタは有用信号のデシメーションに使用され、これによってユーザーは、デシメーション後にフットプリントデータを計算するために、有用信号の最重要の特性を保つことができる。
【００５１】
２）デシメーション後に、ダウンサンプリングされた有用信号は能動フレーム検出器によって処理され、この検出器はエネルギーが所定の閾値未満であるフレームを更なる処理から除外し、この場合は閾値は平均信号エネルギーにユーザー定義重み係数を乗じることによって得られる。この手順は雑音に起因する誤り検出を防止する。
【００５２】
ここで説明する実施形態では、エネルギーが或る閾値未満である現在の断片の全てのフレームは、次の工程によって更なる処理から除外される。
【００５３】
ａ）閾値ＴｈＮが次式によって計算される。
【数２】
2008529047.tif 000004
2008529047.tif 000005
ここで、ＮＶはＰｉ＞ＴｈＳであるフレームの数であり、ｎ０はフレーム長であり、Ｎは断片におけるフレームの数であり、Ｓｈは重複長であり、そしてγＮ
はユーザー定義重み因子である。
【００５４】
ｂ）各フレームｉについて、その特性Ｓｉが計算される。
【数３】
2008529047.tif 000006
ｉ番目のフレームが、Ｓｉ−１＋Ｓｉ＋Ｓｉ＋１＞１である場合は、次の解析段階へ渡される。さもなければ、それは更なる処理から除外される。
【００５５】
３）残りのフレームがスペクトル解析器によって処理され、このスペクトル解析器は、線形予測アルゴリズムを用いて、各フレームについて平滑化したスペクトルパラメータ（ケプストラム係数）を計算する。
【００５６】
ここに、ケプストラム距離に関するパターン比較技術およびスペクトル歪み測定（Ｐａｔｔｅｒｎ−Ｃｏｍｐａｒｉｓｏｎ  Ｔｅｃｈｎｉｑｕｅｓ  ａｎｄ  Ｓｐｅｃｔｒａｌ−Ｄｉｓｔｏｒｔｉｏｎ  Ｍｅａｓｕｒｅｓ  ｆｏｒ  Ｃｅｐｓｔｒａｌ  Ｄｉｓｔａｎｃｅｓ）を説明する。パターン辞書、およびパターン辞書の基準ベクトル間距離の行列が、多数の有用信号を処理することよって得られる［Ｌ  ラビナー、Ｂ  ヤング著、「音声認識の基本」、ＡＴ＆Ｔ、１９９３年（Ｌ．Ｒａｂｉｎｅｒ，Ｂ．Ｊｕａｎｇ，Ｆｕｎｄａｍｅｎｔａｌｓ  ｏｆ  Ｓｐｅｅｃｈ  Ｒｅｃｏｇｎｉｔｉｏｎ，ＡＴ＆Ｔ，１９９３）］。
【００５７】
パターン辞書の基準ベクトルの数は有用信号のクラスに依存する。好ましい値は、音声の場合は１０２４〜２０４８、音楽の場合は４０９６〜８１９２である。本発明のフットプリント技術が様々な特性を有する信号に適用される場合は、信号の各クラスについて、基準ベクトル間距離の対応する行列とともに個別のパターン辞書を形成しなければならない。
【００５８】
現在のフレーム（すなわちフレームのＤコード）に対応する、パターン辞書による基準ベクトルの数は次の工程によって得られる。
ａ）ＬＰＣ解析
ｂ）Ｎケプストラム係数の計算
ｃ）パターン辞書を用いるベクトル符号化
【００５９】
４）現在のフレームのＮケプストラム係数は、事前に計算したパターン辞書およびパターン辞書の基準ベクトル間距離の行列を用いて効率的に符号化される。現在のフレームの得られたＤコードはパターン辞書による単数の基準ベクトルである。このアルゴリズムは高度の圧縮および高効率の符号化を与える。断片全体のＤコードはパターン辞書による基準ベクトルの一連の番号である。
【００６０】
５）有用信号の弁別的素性の解析および符号化は非均一フィルタバンクのＦＦＴ実施を用いて実行される。フィルタバンクのＦＦＴサイズおよび限界周波数は、有用信号のクラスに従ってユーザーによって規定される。音声信号の場合は、我々は、値Ｎｆｆｔ＝６５，５３６、および限界周波数が３２Ｈｚ〜３，９５０Ｈｚのトーンを含むように選ばれることを提案する。
【００６１】
様々なノートの発生周波数の解析は、有用信号の現在の断片について対応するメロディーコード（Ｍコード）を与える。各ノートの時間の解析は、現在の断片についてＲコードおよび１分当たりのビート（Ｎｂｐｍ）値を与える。
【００６２】
有用信号の弁別的素性の推定、それらの符号化およびフットプリントデータへの追加の場合は、非均一フィルタバンクのＦＦＴ実施が使用され、音楽の場合は、非均一フィルタバンクは、フィルタＦｋの中心周波数がノート周波数に一致するように選ばれる。
【数４】
2008529047.tif 000007
【００６３】
現在の断片のＭコード、Ｒコード、およびＮｂｐｍが次の工程で計算される。
ａ）ＦＦＴフィルタバンク
ｂ）スペクトル振幅の時間依存性
ｃ）全てのノートの単一オクターブへの置き換え（ノートは０〜１１の番号を得る）、およびノートの振幅が大きいものから順へのソート
ｄ）メロディー推定（Ｍコード）
ｅ）リズム推定（Ｒコード）
ｆ）テンポ推定（Ｎｂｐｍ）
【００６４】
ＦＦＴの比較的大きいサイズは、フィルタの境界周波数を決定するＦＦＴ係数番号を変化させることによってだけ、フィルタバンクを信号特性に合わせることを可能にする。
【００６５】
図１および図２の解析器の出力データの組合せによって生じるフットプリントデータの構造が図３に示される。フットプリントデータは、パターン辞書からの一組のパターン番号、３６次元ベクトル、２０次元ベクトル、および番号から成る。勿論、他の実施形態では、１つの解析器しか使用されない。結果として生じるフットプリントはその分だけ要素が少ない。
【００６６】
前の説明による多くの有用信号の解析の結果はデータベースに格納できる。各有用信号に固有フットプリントデータが割り当てられ、このデータはデータベースに記録される。同じ信号に対応するフットプリントは信号中の断片の順序によって順序づけられる。従って、信号は全体としてばかりでなく、その断片のいずれかによっても識別できる。
【００６７】
データベースの目的は、フットプリント技術が用いられるシステム全体の目的によって決まる。音楽信号の場合は、フットプリントデータは次の構造を有する。
フットプリントデータ＝（Ｄコード、Ｍコード、Ｒコード、Ｎｂｐｍ）
【００６８】
単一断片のこのデータのサイズは約２Ｋである。
【００６９】
本発明に従って類似のフットプリントコードを探索する方法の好ましい実施形態は次の特徴を備える。
【００７０】
多数のトラック用のフットプリントデータのデータベースはサーバに格納される。このデータベースはまた音楽トラックの属性（名前、著者、ジャンルなど）も含む。サーバはまたユーザーと通信する手段も保有すべきであり、ユーザーは、音楽トラックまたはその一部によって生成されるフットプリントデータをサーバに送信することによって、それを識別することを求める。それに応じて、ユーザーは、タイトルと、適合性の順序にソートされた音楽トラックの他の特性とを含む報告書を得る。
【００７１】
このようなリストは、同じ音楽についての様々な状況での様々な演奏による多くの記録が存在する可能性から必要であり、これらは全て戻されるべきである。ユーザーが自身のトラックを聴いている間に、リストはリアルタイムに更新される。データベース中のトラックの数が数１０万に達する可能性があるので、高速探索方法を実現することが重要である。
【００７２】
従ってここで説明する実施形態は２工程探索システムを備える。
【００７３】
現在の断片のフットプリントコードを｛Ｄｉ、Ｍｉ、Ｒｉ、Ｎｂｐｍ｝として、データベースからのフットプリントコードを
2008529047.tif 000008
として指定する。
【００７４】
探索アルゴリズムの第１工程では、データベースからのフットプリントコードは、次の規則に従ってＲｉ値およびＮｂｐｍ値によってだけ探索される。
【数５】
2008529047.tif 000009
ここで、Ｎｃｎｄは一時的候補者の所望値であり、Δｂｐｍ、ΔＲはＮｃｎｄに従属する調整できる閾値である。
【００７５】
探索アルゴリズムの第２工程では、一時的候補者は重み付け誤りが大きい順にソートされる。
【数６】
2008529047.tif 000010
ここで
【数７】
2008529047.tif 000011
【００７６】
誤り値εＤは動的時間ラッピング（ＤＴＷ）と呼ばれる動的計画アルゴリズムを用いて計算される。探索速度は、パターン辞書の基準ベクトル間距離の行列を事前に計算することによって、著しく大きくなる。従って、εＤ値は現在の値Ｄｉおよび
2008529047.tif 000012
に対応する行列要素を合計することよって得られる。
【００７７】
ユーザーは次式を用いて計算される類似の値とともにデータベース記録のリストを受け取る。
Ｌｎ＝（１−ε）Ｓｎ
ここで、ｎはリスト中の記録の番号であり、Ｓｎは単調に減少するシーケンスである。
【００７８】
コンピュータ実施システムは、全ての上述のパラメータを有用信号の特性によって最適化することを可能にする。
【００７９】
従って、データベース中の類似のフットプリントを探索する方法は次の工程を含む。
【００８０】
１）フットプリントデータが有用信号の現在の断片について生成される。
【００８１】
２）Ｋ候補者が、フットプリントデータ全体からの１つまたはいくつかのフットプリントコードによる高速探索を用いて、フットプリントコードのデータベースから選択される。
【００８２】
３）選択したＫ候補者が目的関数の値が大きい順にソートされて、生成したフットプリントデータの全てのフットプリントコードを考慮する。
【００８３】
Ｋ候補者の選択は、数１０万のフットプリントを有する大きいデータベースにおいても高速探索を与える。目的関数は有用信号の真の識別と誤りの識別との間に必要な妥協を与える。
【００８４】
音楽信号に適用すると、現在の断片は次の工程によって識別される。
【００８５】
１）断片が処理され、Ｄコード、Ｍコード、Ｒコード、およびＮｂｐｍを含む、そのフットプリントデータが生成される。
【００８６】
２）データベースからのＫ候補断片の高速選択が実行される。
【数８】
2008529047.tif 000013
2008529047.tif 000014
ここで、ＩＲは相当するＲコードベクトルの次元数であり、
2008529047.tif 000015
はデータベースからの候補断片のフットプリントコードであり、そして閾値ΔＲ、Δｂｐｍは候補者Ｋの望ましい番号に従属する。
【００８７】
３）選択した候補者Ｋを誤りが大きい順にソートする。
【数９】
2008529047.tif 000016
ここで
【数１０】
2008529047.tif 000017
ここで、ＩＭはＭコードベクトルの次元数である。
誤りεＤは動的時間ラッピング（ＤＴＷ）アルゴリズムを用いて計算されて、パターン辞書の基準ベクトル間の事前に計算した距離を考慮する。
【００８８】
４）データベースからの全てのＫ候補について、類似の値（Ｌ）を推定する。
Ｌ＝（１−ε）Ｓ％
ここで、Ｓは０％〜１００％の類似スケールを決定する関数である。
【００８９】
本発明の好ましい実施形態では、フットプリント生成およびフットプリント探索方法をソフトウェア、ハードウェア、または両方で実施できる。各方法またはその一部は、プログラムまたはプログラムモジュールのような、コンピュータ可読命令形式で適切なプログラミング言語を用いて記述することができる。これらのコンピュータプログラムは、１つ以上のコンピュータまたは同等のプログラマブルデバイスにインストールされ、実行され得る。プログラムは、格納および配布のために、取外し可能媒体（ＣＤ-ＲＯＭ、ＤＶＤ-ＲＯＭなど）または他の記憶装置に格納するか、またはインターネットを経由して配布することができる。
【００９０】
本発明のフットプリント生成および探索方法を実施する装置は、パソコンで使用するオーディオ・プレーヤー・ツールである場合がある。これらのプレーヤーは適切なソフトウェアを備える専用ハードウェア、すなわち独立型プレーヤーであるか、あるいは既知のプレーヤーで実行するために、ウェブページに統合されるか、またはプラグインとしてダウンロードされ、インストールされて、パソコンのデスクトップディスプレイ上で起動することができるものである。
【００９１】
例として、図４は本発明のフットプリント生成および探索方法が実施されるアプリケーションのデスクトップビューを示す。ユーザーからの要求に応じて、ビューの左部分のライトドットの１つをクリックすることによって、プレーヤーは要求したトラックを演奏し始める。類似のトラック（すなわち、類似のフットプリントをアプリケーションに供給するデータベース内のトラック）は互いのすぐ近くに表示される。従ってユーザーが同程度の特性を有するトラックを選ぶことは容易に可能である。どの特性が比較のために用いられるかもまたユーザーが選ぶことができる。
【００９２】
本発明のいくつかの適切な実施形態について、本明細書に説明した。添付の特許請求の範囲によって排他的に規定される本発明の範囲を逸脱せずに、さらに多くの実施例が可能であり、そして多くの当業者には明らかである。
【図面の簡単な説明】
【００９３】
【図１】本発明の第１実施形態の概略図である。
【図２】本発明の第２実施形態の概略図である。
【図３】本発明によるフットプリント・データ・ベクトルの概略図である。
【図４】本発明を実行するアプリケーションのスクリーンショットである。
【図１】
2008529047.tif 000018
【図２】
2008529047.tif 000019
【図３】
2008529047.tif 000020
【国際調査報告】
2008529047.tif 000021
2008529047.tif 000022
2008529047.tif 000023