(57)【特許請求の範囲】
【請求項１】
オーディオ・サンプルを識別する方法であって、
前記オーディオ・サンプルの内容に基づき計算される当該オーディオ・サンプルにおける時間上の特定の位置で生じるランドマークと、当該オーディオ・サンプルの前記特定の位置またはその付近における１または２以上の特徴量を含むフィンガープリントとで形成される、サンプル・ランドマーク／フィンガープリント・ペアを生成するステップと、
１または２以上のオーディオ・ファイルの各々に対し、当該オーディオ・ファイルの内容に基づき計算される当該オーディオ・ファイルにおける時間上の特定の位置で生じるランドマークと、当該オーディオ・ファイルの前記特定の位置またはその付近における１または２以上の特徴量を含むフィンガープリントとで形成される、ファイル・ランドマーク／フィンガープリント・ペアを生成するファイル・フィンガープリント生成ステップと、
各サンプル・ランドマーク／フィンガープリント・ペアと過去に生成されたファイル・ランドマーク／フィンガープリント・ペアとのほぼリニアな対応関係を特定する特定ステップと、
前記ほぼリニアな対応関係が多数あるときにベストなファイルを識別する識別ステップと、
を有することを特徴とする方法。
【請求項２】
各フィンガープリントは、各ランドマーク位置またはその位置からわずかにオフセットした位置における当該オーディオの多数の特徴量を表現することを特徴とする請求項１に記載の方法。
【請求項３】
各フィンガープリントは、前記サンプルの時間伸縮に対し不変であることを特徴とする請求項１又は２に記載の方法。
【請求項４】
各フィンガープリントは、スペクトル・スライス・フィンガープリント、マルチスライス・フィンガープリント、ＬＰＣ係数、ケプストラム係数、およびスペクトルピークの周波数成分のうちのいずれかとして計算されることを特徴とする請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
前記スペクトル・スライス・フィンガープリントは、ランドマーク時点に対する時間オフセットのセットにおいて計算されることを特徴とする請求項４に記載の方法。
【請求項６】
各ランドマークの位置は、サウンド記録における特徴的かつ再現可能な位置をみつけるランドマーク分析方法を用いて識別されることを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
前記ランドマーク分析方法は、スペクトルＬｐノルムを用いて前記サウンド記録においてとりうるすべての時点で瞬時パワーを計算し、ランドマークとしての極大点を選択することを特徴とする請求項６に記載の方法。
【請求項８】
１または２以上のランドマークは、固定もしくは可変のオフセットでの複数の時間スライスにわたるスペクトル成分から得られるマルチスライス・ランドマークであることを特徴とする請求項６または７に記載の方法。
【請求項９】
前記ファイル・ランドマーク／フィンガープリント・ペアはデータベースに格納され、そのデータベース内の各ファイルはそのファイルのフィンガープリントによってインデックスされることを特徴とする請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
前記インデックスはフィンガープリントに基づきソートされることを特徴とする請求項９に記載の方法。
【請求項１１】
固有のフィンガープリントとそれに対応するランドマークのリストへのポインタと含むエントリを有するマスター・インデックス・リストが構成されることを特徴とする請求項１０に記載の方法。
【請求項１２】
各ファイルはSOUND_IDによって識別され、前記データベースは、フィンガープリントと、ランドマークと、SOUND_IDとの３つ組を複数記憶することを特徴とする請求項９乃至１１のいずれか１項に記載の方法。
【請求項１３】
統計的に最もリニアな対応関係にあるファイル・ランドマーク／フィンガープリント・ペアを有するファイルが前記ベストなファイルとして選択されることを特徴とする請求項１乃至１２のいずれか１項に記載の方法。
【請求項１４】
サンプル・ランドマーク／フィンガープリント・ペアが許容範囲内でファイル・ランドマーク／フィンガープリント・ペアにマッチするときに、サンプル・ランドマークとファイル・ランドマークのペア（landmarkn, landmark*n）においてリニアな対応関係が生じることを特徴とする請求項１乃至１３のいずれか１項に記載の方法。
【請求項１５】
個々のフィンガープリント同士がマッチし、なおかつ、個々のランドマーク同士がリニアな関係にあるときに、サンプル・ランドマーク／フィンガープリント・ペアとファイル・ランドマーク／フィンガープリント・ペアとの間にリニアな対応関係が生じることを特徴とする請求項１乃至１４のいずれか１項に記載の方法。
【請求項１６】
フィンガープリント同士が同一または所定の許容範囲内の差にあるときに、両者のフィンガープリントがマッチしたとすることを特徴とする請求項１５に記載の方法。
【請求項１７】
リスト内のサンプル・ランドマークとファイル・ランドマークのペア（landmarkn, landmark*n）が
landmark*n=m*landmarkn+offset、
の関係にあるときに、リニアな対応関係が生じることを特徴とする請求項１５または１６に記載の方法。
【請求項１８】
前記サンプルは、音響波、無線波、ディジタルオーディオＰＣＭストリーム、圧縮ディジタルオーディオストリーム、インターネットストリーミング放送のいずれかの形式であることを特徴とする請求項１乃至１７のいずれか１項に記載の方法。
【請求項１９】
前記サンプル・フィンガープリントはローリング・バッファに格納されることを特徴とする請求項１乃至１８のいずれか１項に記載の方法。
【請求項２０】
前記特定ステップおよび識別ステップは、前記ローリング・バッファの内容に対して周期的に実行されることを特徴とする請求項１９に記載の方法。
【請求項２１】
前記特定ステップおよび識別ステップは、認識するのに十分な情報が前記ローリング・バッファから得られしだい実行されることを特徴とする請求項１９または２０に記載の方法。
【請求項２２】
前記特定ステップおよび識別ステップは、まずファイルの第１のサブセットに対して実行され、その第１のサブセットでベストなファイルが識別されなかったときに、残りのファイルを収めた第２のサブセットが検索されることを特徴とする請求項１乃至２１のいずれか１項に記載の方法。
【請求項２３】
前記第１のサブセットは、当該第１のサブセットに含まれないファイルよりも識別される経験的に確率が高いファイルを含むことを特徴とする請求項２２に記載の方法。
【請求項２４】
前記特定ステップは、前記対応する位置間の差分をとり、その差分のヒストグラムのピークを計算することにより、前記対応する位置の散布図における斜線を特定することを特徴とする請求項１に記載の方法。
【請求項２５】
前記識別ステップは、多数の対応関係を生じる前記ベストなファイルにおける位置に対するオフセットの指標を提供するステップを更に有することを特徴とする請求項１に記載の方法。
【請求項２６】
オーディオ・サンプルを識別する方法であって、
クライアントからの要求に応じて、前記オーディオ・サンプルの少なくとも一部を、請求項１に記載の各ステップを実行するサーバに取り次ぐステップと、
前記サーバがベストなファイルを識別したことに応じて、前記クライアントに応答を返すステップと
を有することを特徴とする方法。
【請求項２７】
請求項１乃至２６のいずれか１項に記載の方法をコンピュータに実行させるためのプログラムを格納したコンピュータ読み取り可能な記憶媒体。
【請求項２８】
請求項１乃至２５のいずれか１項に記載の方法を実行するコンピュータシステムであって、
キャプチャされた信号サンプルのランドマーク／フィンガープリント・ペアを含む特徴抽出サマリを、認識処理を実行するサーバ端末に送信するクライアント端末を含むことを特徴とするコンピュータシステム。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明は、コンテンツに基づく情報検索に関し、具体的には、大きく歪んでいたり高いレベルのノイズが混入したサウンドもしくは楽音を含む音響信号の認識に関する。
【０００２】
（背景技術）
さまざまな音源から生成された音楽もしくはその他のオーディオ信号の自動認識のニーズが高まっている。例えば、著作物のある作品の所有者や広告主は、彼らの作品の放送頻度のデータを得ることに興味がある。音楽追跡サービスは大きな市場の主要ラジオ局のプレイリストを提供する。消費者は、新曲や興味のある曲あるいはその他の製品やサービスを購入できるように、ラジオでオンエアされる曲や宣伝を特定することを希望している。連続的な音響認識あるいはオンデマンド型の音響認識のいずれのタイプのものでも、人手によって行われる場合には非効率であり大きな労働力を要する。よって、音楽・音響の自動認識は、消費者、アーティスト、およびさまざまな業界に非常に大きなメリットをもたらすであろう。音楽販売の形態が店舗購入からインターネットを介したダウンロードに移行すれば、インターネット購入またはその他のインターネット型サービスによりコンピュータで実行される音楽認識に直接リンクすることがまさに現実のものとなる。
従来、ラジオでオンエアされた曲の認識は、ラジオ局もしくはサードパーティの情報源のいずれかから提供されたプレイリストで、曲が演奏されたラジオ局と時刻を照合していた。この方法は本質的に、情報を受け取ることのできるラジオ局だけに限られる。その他、放送信号への耳に聞き取れないコードの埋め込みに頼る方法もある。埋め込まれた信号は受信機でデコードされて放送信号についての識別情報が抽出される。この方法の欠点は、信号を識別するための専用のデコード装置が必要になることと、コードが埋め込まれた曲しか識別できないことである。
【０００３】
大規模オーディオ認識は、識別されていない放送信号を既知の信号のデータベースと比較して同一もしくは近似のデータベース信号を識別する、ある種のコンテンツベースのオーディオ検索を必要とする。コンテンツベースのオーディオ検索は、オーディオファイルを囲みもしくは付属するメタデータテキストだけが検索される、既存のウェブサーチエンジンによるオーディオ検索とは違うことに注意されたい。音声認識は、音声信号を、 周知の手法でインデックスを付与し検索可能なテキストに変換するのに有用であり、音楽・音響を含んだオーディオ信号の多くは適用することができないことにも注意されたい。
【０００４】
ある意味では、オーディオ情報検索は、サーチエンジンにより提供されるテキストベースの情報検索と類似している。しかし、オーディオ信号は検索やインデクシングのための識別子を提供する単語のような識別容易な存在に欠ける点で、オーディオ認識は類似しない。このことから、現在のオーディオ検索手法は、信号の諸種の品質や特性を示す知覚可能な特徴量を計算することでオーディオ信号をインデクシングする。
【０００５】
コンテンツベースのオーディオ検索は一般に、クエリー信号を分析して多数の代表特徴量を得て、その得られた特徴量を類似度測定に与えて、そのクエリー信号に最も類似するデータベースファイルを位置させることで行われる。受信したオブジェクトの類似度は選択された知覚特徴量の反映に必要である。多くのコンテンツベースの検索方法が従来より提案されている。例えば、Kenyonによる米国特許第5,210,820号は、各サンプリングポイントで信号値を得るように受信信号が処理されサンプリングされる信号認識方法を開示している。そして、 ストアされた信号の識別子と比較可能な特徴ベクトルを生成して類似信号を得るために、サンプル値の統計モーメントが計算される。Kenyon等による米国特許4,450,531号および4,843,562号は、識別されていない信号とストアされたリファレンス信号との相互相関を計算する同様の放送情報の分類方法を開示している。
【０００６】
音響類似度によるオーディオ・ドキュメントを検索するシステムが、J. T. Footeによる "Content-Based Retrieval of Music and Audio," （C. -C. J. Kuo et al., editor, Multimedia Storage and Archiving Systems II, Proc. of SPIE, volume 3229, pages 138-147, 1997）に開示されている。各オーディオファイルをメル尺度ケプストラム係数にパラメータ化することで特徴ベクトルが計算され、パラメータ化データから量子化木が成長する。クエリーを実行するために、未知の信号がパラメータ化されて上記量子化木のリーフノードにソーティングされる特徴ベクトルを得るべくパラメータ化される。各リーフノードごとにヒストグラムが得られ、その結果、未知の信号を表すＮ次元ベクトルが生成される。これら２つのベクトル間の距離は、２つのサウンドファイル間の類似度を示す。この方法において、 管理下の量子化スキームは、人手によってトレーニングデータが割り当てられるクラスに基づき、 重要でない変動を無視しつつ音響特徴量の分類を学習する。この分類システムに依存して、異なる音響特徴量が重要なものとして選択される。したがって、この方法は、音楽の認識よりも、曲同士の類似度の計算や音楽のクラス分類に好適である。
【０００７】
オーディオ情報のコンテンツベースの分析、ストレージ、検索、セグメンテーションの方法が、Blum等による米国特許第5,918,223号に開示されている。この方法では、ラウドネス、バス、ピッチ、ブライトネス、帯域幅、メル周波数ケプストラム係数などの各ファイルの多数の音響特徴量が周期的に測定される。これらの特徴量の統計的測定値が得られると、結合されて特徴ベクトルが形成される。データベース中のオーディオデータファイルは、それらの特徴ベクトルと未確認ファイルの特徴ベクトルとの類似度に基づいて検索される。
【０００８】
上記した従来のオーディオ認識方法すべてにいえる重大な問題は、 認識しようとする信号が、背景雑音、伝送誤りおよび欠損、干渉、帯域制限フィルタリング、量子化、タイムワーピング、音声品質ディジタル圧縮などによって生じる線形または非線形の歪みを受けた場合には、失敗する傾向にあることである。従来の方法においては、歪みを受けた音響サンプルが音響特徴量を得るべく処理されると、オリジナル記録について抽出される特徴量はわずかな部分にすぎない。したがって、得られる特徴ベクトルはオリジナル記録の特徴ベクトルとは大して類似しておらず、認識が正確に行なわれる見込みなし、ということになる。よって、高レベルの雑音および歪みが加わる状況下でも良好に動作する音響認識システムに対するニーズは依然としてある。
【０００９】
従来の方法における別の問題は、演算量が大きく、うまくそれを縮小できないことである。したがって、大規模データベースによる従来の方法ではリアルタイム認識は不可能である。このようなシステムにおいては、数百、数千を超える録音のデータベースを持たせることは現実的ではない。従来の方法における検索時間はデータベースのサイズに対し直線的に延びる傾向にあり、数千の録音を数百万に拡大させるのは経済的に実行不可能である。Kenyonの方法も大規模な専用ディジタル信号処理ハードウェアが必要である。
【００１０】
現在の商用化されている方法はたいてい、認識ができるように、入力サンプルに厳格な必要条件を求める。例えば、曲全体や、少なくとも曲の３０秒間がサンプルされていることが求められたり、曲の始まりからサンプルされていることが求められたりする。また、１つのストリームに複数の曲が混在しているものを認識することも困難である。これらの欠点はすべて、従来の方法の実用化を阻んでいる。
【００１１】
（発明の目的と効果）
したがって、本発明の主な目的は、高レベルの雑音や歪みを受けたオーディオ信号を認識する方法を提供することである。
【００１２】
本発明の別の目的は、信号が識別されるまでに数秒で済むようなリアルタイムで実行可能な認識方法を提供することである。
【００１３】
本発明の別の目的は、音響の始まりからではなく任意の位置のサンプルに基づいて音響を認識することができる認識方法を提供することである。
【００１４】
本発明はさらに、音響サンプルを符号化したり特定のラジオ局やプレイリストに関連づけることを必要としない認識方法を提供することを目的とする。
【００１５】
さらに、本発明は、１つのストリームに複数のサウンド記録が混在したものの各々を認識することのできる認識方法を提供することを目的とする。
【００１６】
さらに、本発明は、ほとんどすべての公知の方法によるあらゆる環境から未知音響がシステムに提供されうる音響認識システムを提供することも目的とする。
【００１７】
（概要）
これらの目的は、オーディオ・サンプルなどのメディア・サンプルを、大量の既知のメディア・ファイルのデータベース・インデックスから認識する方法によって達成される。データベース・インデックスは、インデックスされたメディア・ファイルの特定の位置での特徴を表す。データベース内のメディア・ファイルのフィンガープリントの相対的な位置と、未知のメディア・サンプルのフィンガープリントの相対的な位置とが最も忠実にマッチする場合に、そのメディア・サンプルはそのメディア・ファイル（ベストなメディア・ファイル）と認識される。オーディオ・ファイルの場合、ベストなファイルのフィンガープリントの時間進行が、サンプルのフィンガープリントの時間進行とマッチする。
【００１８】
この方法は、好ましくは分散コンピュータシステムによって実現され、以下のステップを有する。すなわち、サンプルにおける特定の位置のサンプル・フィンガープリントのセットを計算するステップと、
【００１９】
前記メディア・ファイルにおける少なくとも１のファイル位置を特徴づけるファイル・フィンガープリントのセットを取得する取得ステップと、データベース・インデックスからマッチするフィンガープリントを特定するステップと、サンプルの前記特定の位置とファイルの前記ファイル位置との間で、対応する位置が同等のフィンガープリントを有する対応関係を生成するステップと、前記対応関係の多くがリニアな関係にあるときに、前記メディア・ファイルを識別するステップとを有する。前記対応関係の多くがリニアな関係にあると、それがベストなメディア・ファイルとみなす。多くの対応関係からファイルを識別する一方法は、対応関係のペアから生成される散布図における斜線を確認することである。一実施形態においては、リニアな対応関係検査からのメディア・ファイルの識別は、メディア・ファイルの第１のサブセットだけから実行する。第１のサブセットにおけるファイルは、その第１のサブセットに含まれないファイルに比べ識別される確率が高い。識別の確率は、事前の識別頻度を反映させるだけでなく、過去の識別における経験的な頻度または時期の新しさに基づくものであることが好ましい。メディア・ファイルが第１のサブセットから識別されなかったときには、残りのファイルを収めた第２のサブセットが検索される。かわりに、ファイルは確率によってランクづけされて、そのランク順に検索されるようにしてもよい。ファイルが特定されると検索は終了する。
【００２０】
好ましくは、サンプルの特定の位置は、そのサンプルに依存して再現可能に計算される。このような再現可能に計算される位置は「ランドマーク」とよばれる。フィンガープリントは数値であることが好ましい。一実施形態においては、各フィンガープリントは、各位置またはその位置から少しオフセットした位置でのメディア・サンプルの多くの特徴を表す。
【００２１】
本方法はとりわけ、オーディオ・サンプルの認識に有用であり、この場合、特定の位置はオーディオ・サンプルの時点となる。これらの時点は、たとえば、オーディオ・サンプルのスペクトルＬｐノルムが極大となる点である。フィンガープリントは各種オーディオ・サンプルの分析によって計算することができ、好ましくは、フィンガープリントはそのサンプルの時間伸縮に対し不変である。フィンガープリントの例は、スペクトル・スライス・フィンガープリント、マルチスライス・フィンガープリント、ＬＰＣ係数、ケプストラム係数、スペクトルピークの周波数成分を含む。
【００２２】
本発明はまた、特定の位置を計算するランドマーク分析オブジェクト、フィンガープリントを計算するフィンガープリント分析オブジェクト、メディア・ファイルのファイル位置およびフィンガープリントを含むデータベース・インデックス、および解析オブジェクトを含み、上記方法を実現するシステムを提供する。解析オブジェクトは、データベース・インデックスにおけるマッチング・フィンガープリントを特定し、対応関係を生成し、その対応関係を分析してベストなメディア・ファイルを選択する。
【００２３】
また、上記方法の各ステップを実行するためのコンピュータによって実行可能な命令のプログラムを有形的に具現化する、当該コンピュータによりアクセス可能なプログラム記憶デバイスも提供される。
【００２４】
くわえて、本発明は、データベース内の大量のオーディオ・ファイルのインデックスを生成するために、以下のステップを含む方法も提供する。すなわち、各ファイルの特定の位置でのフィンガープリントのセットを計算するステップと、ファイルのフィンガープリントと位置とＩＤをメモリに格納するステップとを有する。対応するフィンガープリント、位置、ＩＤは、３つ組の形式で関連付けられる。好ましくは、オーディオ・ファイルの時点であるその位置は、そのファイルに基づき計算され、再現可能である。たとえば、その時点では、そのオーディオ・ファイルのスペクトルＬｐノルムが極大となる。あるケースにおいては、各フィンガープリントは、好ましくは数値であり、特定の位置付近のファイルの多数の特徴を表す。フィンガープリントは、オーディオ・ファイルのあらゆる分析やディジタル信号処理から計算できる。フィンガープリントの例は、スペクトル・スライス・フィンガープリント、マルチスライス・フィンガープリント、ＬＰＣ係数、ケプストラム係数、スペクトルピークの周波数成分、連結されたスペクトルピークを含む。
【００２５】
また、本発明は、時間伸縮に対し不変のフィンガープリントおよび、さまざまな階層検索を組み込んだ、オーディオ・サンプルを識別する方法を提供する。
【００２６】
（詳細な説明）
本発明は、大量の既知メディア・ファイルを含むデータベースに与えられる外来のメディア・サンプルを認識する方法を提供する。また、本発明の認識方法を用いた効率的な検索を可能にするデータベース・インデックスを生成する方法も提供する。以下の説明は主にオーディオデータに言及するものであるが、本発明の方法は、テキスト、オーディオ、ビデオ、画像、別個のメディアタイプを組み合わせた種々のマルチメディアなどを含む、あるゆるタイプのメディア・サンプル、メディア・ファイルにも適用可能であることが理解されよう。オーディオの場合、本発明は、例えば、背景雑音、伝送誤りおよび欠落、干渉、帯域制限フィルタリング、量子化、タイムワーピング、音声品質ディジタル圧縮などによって生じた高レベルの線形歪みもしくは非線形歪みを含んだサンプルの認識に特に有用である。以下の説明から明らかなように、本発明は、たとえ計算される特徴量のわずかな部分だけしか歪みに耐えられなかったとしても、歪みを受けた信号を正確に認識できるため、かかる状況の下で動作する。音響（sound）、音声（voice）、音楽（music）、またはそれらの組み合わせ、を含むあらゆるタイプのオーディオ（audio）が、本発明によって認識されうる。オーディオサンプルの例は、記録された音楽、ラジオ放送プログラム、広告を含む。
【００２７】
外来のメディア・サンプルは、本明細書では、後述するような種々の音源から得られるあらゆるサイズのメディアデータのセグメントをいう。認識が行われるためには、サンプルは、本発明によって使用されるデータベースにおけるインデックス・メディア・ファイルの一部の再現（rendition）でなければならない。インデックス・メディア・ファイルはオリジナル記録であり、サンプルはそのオリジナル記録が歪みを受けおよび／もしくは短縮化された変形もしくは再現であると考えることができる。一般に、サンプルは、インデックス・ファイルの小部分のみに対応する。例えば、データベースにインデックスが付与された５分間の曲のうちの１０秒間で認識が行われうる。「ファイル」の用語はインデックスが付与される構成単位に用いられるが、その構成単位は、必要な値（後述）が得られるかぎり、いかなるフォーマットでもよい。さらに、その値が得られた後にファイルを記憶したりアクセスする必要もない。
【００２８】
図１は、本発明の方法１０の全体ステップを概念的に示す図である。以下、各ステップを詳しく説明する。この方法は、固有フィンガープリントの相対位置が外来サンプルの同様のフィンガープリントの相対位置に最も近似するメディア・ファイルを、ベストなメディア・ファイルとして識別するものである。ステップ１２で外来サンプルがキャプチャー（記録）された後、ステップ１４で、ランドマーク（landmark）およびフィンガープリント（fingerprint）が計算される。ランドマークは、サンプルにおける特定の位置（例えば時点）で生じる。ランドマークのサンプルにおける位置は、サンプル自身によって（すなわち、同じ品質に依存して）決定され、再現可能であることが好ましい。これは、同じ信号に処理を繰り返しても各時刻において同じランドマークが計算されるということである。各ランドマークに対して、そのランドマークまたはその付近でのサンプルの１または２以上の特性を特徴付けるフィンガープリントが得られる。ランドマークへの特性の近似度は、使用されるフィンガープリント法によって定義される。あるケースにおいて、ある特性が明らかにランドマークに一致し、前のランドマークおよび後続のランドマークには一致しない場合には、その特性はそのランドマークに近いと考えれる。別のケースでは、特性は近接する複数のランドマークに相当する。例えば、テキストのフィンガープリントは単語列、オーディオのフィンガープリントはスペクトル成分、画像のフィンガープリントは画素ＲＧＢ値、とすることができる。以下では、ステップ１４の２つの一般的な実施態様を説明する。１つは、ランドマークおよびフィンガープリントがシーケンシャルに計算されるもの、もう１つはランドマークおよびフィンガープリントが同時に計算されるものである。
【００２９】
ステップ１６では、サンプルのフィンガープリントが、マッチング・フィンガープリントのセットをデータベース・インデックス１８から検索するのに用いられる。ここで、マッチング・フィンガープリントはメディア・ファイルのセットのランドマークおよび識別子に関連付けられている。検索されたファイルの識別子およびランドマーク値のセットは、同じフィンガープリントが計算された位置におけるサンプルのランドマーク（ステップ１４で計算された）と検索されたファイルのランドマークとを含む対応ペアの生成（ステップ２０）に用いられる。得られた対応ペアは楽曲ＩＤでソートされ、各適用ファイルのサンプル・ランドマークとファイル・ランドマークとの対応関係のセットを生成する。各セットは、ファイル・ランドマークとサンプル・ランドマークとの位置合わせのために検査される。これは、ランドマーク同士にリニアな対応関係が確認され、そのセットはリニアな対応関係にあるペアの数に従いスコアリングされることになる。多数のサンプル位置とファイル位置との対応関係が許容誤差の範囲内でほぼ等しい一次方程式を記述できる場合に、リニアな対応関係が生じる。例えば、対応ペアのセットを記述する多くの方程式の勾配が＋−５％の範囲の変動で収まっている場合には、対応関係のすべてのセットはリニアな関係を有していると考えられる。もちろん、別の好適な許容誤差を選択してもよい。最高スコアの（すなわち、リニアな対応関係の数が最大の）セットのＩＤが、ステップ２２で、ベストなファイルＩＤとして特定され返される。
【００３０】
さらに後述するように、データベースのエントリ数の対数に比例する時間成分で認識が行われうる。大規模なデータベースであっても、基本的にはリアルタイムで認識が行われうる。すなわち、サンプルが得られてから小さな時間遅れで認識されうる。この方法は、５〜１０秒間、あるいはもっと短い１〜３秒間のセグメントに基づいて音響を識別できる。好適な実施形態においては、ステップ１４のランドマーク分析およびフィンガープリント分析は、ステップ１２でサンプルがキャプチャされるのと同時に実行される。データベース検索（ステップ１６）は、サンプル・フィンガープリントが利用可能となりしだい実行され、対応関係の結果が計算されリニアな対応関係を求めて周期的に検査される。しがたって、この方法の全ステップは、図１に示したとおりの順次実行ではなく、同時進行させることができる。この方法は、部分的にはテキスト検索エンジンに類似していることに留意されたい。ユーザは検索サンプルを提示し、音響データベースにインデックス付与されたファイルのうちマッチするものが返される。
【００３１】
本方法は、典型的にはコンピュータシステムで操作するソフトウェアとして実現され、個々のステップは独立したソフトウェアモジュールとして最も効率的に実現される。したがって、本発明を実現するシステムは、ランドマークおよびフィンガープリント分析オブジェクト、インデックス付けされたデータベース、データベース・インデックスを検索し、対応関係を計算し、ベストなファイルを識別するための解析オブジェクト、で構成されうる。ランドマーク分析およびフィンガープリント分析を順次行う場合には、ランドマーク分析オブジェクトとフィンガープリント分析オブジェクトとは別個のオブジェクトとしてもよい。上記個別のオブジェクトに対するコンピュータ命令コードは、１または２以上のコンピュータのメモリに格納され、１または２以上のコンピュータ・プロセッサにより実行される。一実施形態においては、コード・オブジェクトは、インテルベースのパーソナルコンピュータやその他のワークステーションなどの単一のコンピュータシステムにまとめて収容される。好適な実施形態においては、本方法は、ネットワークにより分散した中央処理装置（ＣＰＵ）によって実現され、演算負荷を分散させるために、別個のソフトウェア・オブジェクトはそれぞれ別個のプロセッサによって実行される。あるいは、それぞれ同様に構成された要素の同形ネットワークとすることを考慮して、各ＣＰＵがすべてのソフトウェア・オブジェクトのコピーを保持するようにしてもよい。この後者の構成においては、各ＣＰＵがデータベース・インデックスのサブセットを有し、自身のメディア・ファイルのサブセットの検索に応答することが可能である。
【００３２】
図２は、分散コンピュータシステム３０の好適な実施形態の一例を示す図である。ただし、本発明は特定のハードウェアシステムに限定されるものではない。システム３０は、マルチプロセッシング・バスアーキテクチャ３４もしくは、ベオウルフ・クラスタ演算プロトコル（the Beowulf cluster computing protocol）などのネットワーク・プロトコル、あるいはそれら２つの組み合わせによって接続されたＬｉｎｕｘベースのプロセッサ３２ａ〜３２ｆを含む。かかる構成において、フィンガープリント分析の高速な立ち上がりが確保されるよう、データベース・インデックスは、クラスタ内の少なくとも１のノード３２ａのランダム・アクセス・メモリ（ＲＡＭ）に記憶されることが好ましい。ランドマーキング・ノード３２ｃおよび３２ｆ、フィンガープリンティング・ノード３２ｂおよび３２ｅや、位置合わせ検査ノード３２ｄなど、その他のオブジェクトに対応する演算ノードは、データベース・インデックスを保持するノード３２ａほどに大容量のＲＡＭは必要ではない。各オブジェクトに割り当てられる演算ノードの数は、１つのオブジェクトがボトルネックとならなよう要求に従い増減することができる。したがって、演算ネットワークは高度に並列処理化することができ、くわえて、利用可能な演算リソース間に分配された複数の信号認識探索を同時進行で処理できる。これは、多数のユーザが認識を要求してきても短時間で結果を返すアプリケーションを可能にするということである。
【００３３】
別の実施形態においては、いくつかの機能オブジェクトがより強固に結合し、一方で他のオブジェクトとはそれほど強固には結合させないでおく。例えば、ランドマーク分析オブジェクトおよびフィンガープリント分析オブジェクトは残りのオブジェクトからは物理的に離れた位置に配置することができる。この一例は、ランドマーク分析オブジェクトおよびフィンガープリント分析オブジェクトと、信号キャプチャ処理との強固な連係が挙げられる。この配置構成において、ランドマーク分析オブジェクトおよびフィンガープリント分析オブジェクトは、例えば移動電話、無線アプリケーションプロトコル（ＷＡＰ）ブラウザ、個人情報端末（ＰＤＡ）、オーディオ検索エンジンのクライアント端末のようなその他のリモート端末などに埋め込まれる、追加的なハードウェアまたはソフトウェアとして組み込まれうる。コンテンツ表示サービスなどのインターネット・ベースのオーディオ検索サービスにおいて、ランドマーク分析オブジェクトおよびフィンガープリント分析オブジェクトは、マイクロソフト（登録商標）ダイナミック・リンク・ライブラリ（ＤＬＬ）のような、リンクされたソフトウェア命令セットまたはソフトウェア・プラグイン・モジュールとして、クライアントのブラウザ・アプリケーションに組み込まれうる。これらの実施形態において、信号キャプチャ、ランドマーキング、フィンガープリンティングのすべてを含めたオブジェクトは、サービスのクライアント端末を構成する。クライアント端末は、ランドマークおよびフィンガープリントのペアを含む特徴量が抽出されたキャプチャ信号サンプルのサマリを、認識を実行するサーバ端末に送信する。生のキャプチャ信号のかわりに、この特徴量が抽出されたサマリをサーバへ送信することは、データ量を大幅に、たいてい５００分の１またはそれ以下に、減らせる点で有利である。このような情報であれば、例えばサーバに送信されるオーディオストリームと一緒にもしくは一緒にではなく、狭い帯域幅の片側チャネルでリアルタイムに送信されうる。これは、各ユーザに狭小な帯域幅しか与えられていない公衆通信網上で本発明を実現することが可能になる。
【００３４】
以下、オーディオ・サンプルと、音響データベースにインデックスが付与されたオーディオ・ファイルを参照して、本方法を詳細に説明する。本方法は音響データベース・インデックスの構築と、サンプル認識の２つに大別される。
【００３５】
（データベース・インデックスの構築）
音響認識を行う前提として、探索可能な音響データベース・インデックスを構築する必要がある。本明細書において、データベースとは、インデックスが付与されたデータの集合体をいうが、商業ベースにのるデータベースに限られない。データベース・インデックスにおいて、つながりのあるデータの要素は互いに関連づけられ、個々の要素は関連するデータの検索に用いられうる。音響データベース・インデックスは、音声、音楽、広告、ソナー信号、またはその他の音響を含む、選択された集合もしくはライブラリにおける各ファイルまたは記録（recording）のインデックスセットを含む。また、各記録は固有の識別子sound_IDも有する。音響データベースそのものは各記録に対するオーディオファイルを記憶する必要はないが、sound_IDは、別の場所からオーディオファイルの検索に使用されうる。音響データベース・インデックスは、数百万、場合によっては何十億のファイルのインデックスを含むため、非常に大きなサイズであると予想される。新たな記録は徐々にデータベース・インデックスに追加されることが望ましい。
【００３６】
図３は、第１の実施形態により探索可能な音響データベース・インデックスを構築する好適な方法４０を示す図である。本実施形態においては、まずランドマークが計算され、その後、そのランドマーク位置もしくはその付近のフィンガープリントが計算される。データベース・インデックスを構築する他の方法が考えられるのは当業者には明らかであろう。とりわけ、以下に示すステップの多くは選択的なものであるが、より効率的に検索がなされるデータベース・インデックスを生成する役を果たす。大規模データベースからのリアルタイム音響認識のためには探索効率が重要であるが、小規模データベースであればたとえ最適にソートされていなくても比較的高速に探索されうる。
【００３７】
音響データベースにインデックスを付与するために、集合における各記録はランドマーク分析およびフィンガープリント分析され、各オーディオファイルのインデックスセットが生成される。図４は、ランドマーク（ＬＭ）およびフィンガープリント（ＦＰ）が計算されるサウンド記録のセグメントを模式的に示す図である。ランドマークは音響の特定の時点で生じ、ファイルの始まりからの時間単位オフセットの値を有しており、フィンガープリントは特定のランドマーク位置またはその付近の音響を特徴付ける。したがって、本実施形態においては、特定のファイルに対する各ランドマークは固有のものである一方、フィンガープリントは１つのファイルまたは複数のファイルで何回も同じものが生じうる。
【００３８】
ステップ４２において、サウンド記録における特徴的で再現性のある位置をみつける方法を用いて、各サウンド記録がランドマーク分析される。好適なランドマーク分析アルゴリズムは、雑音やその他の線形、非線形の歪みが存在していても、サウンド記録内の同じ時点をマークすることができる。いくつかのランドマーク分析方法は、後述するフィンガープリント工程とは概念的に独立のものであるが、その工程の性能を最適化すべく選択することができる。ランドマーク分析によって、サウンド記録における時点 {landmarkk} のリストが得られ、各時点で順次フィンガープリントが計算される。良好なランドマーク分析スキームによれば、サウンド記録の１秒間あたりにおよそ５〜１０個のマークがなされる。もちろん、ランドマークの密度はサウンド記録における活性度に依存する。
【００３９】
ランドマークの計算にはさまざまな手法をとることができるが、いずれも本発明の範疇のものである。本発明のランドマーク分析スキームを実現するのに用いられる特定の手法は公知のものであるのでその詳細な説明は省略する。パワーノルムとよばれる単純なランドマーク分析手法は、サウンド記録の各時点における瞬時パワーを計算し、極大点を選択するものである。これを行う一方法は、波形を直接、調整およびフィルタリングすることで包絡線を計算することである。別の方法は、信号のヒルベルト変換（直交変換）を計算し、ヒルベルト変換および原信号の２乗振幅を用いることである。
【００４０】
ランドマーク分析のパワーノルム法は音響信号における遷移をみつけるのに好適である。パワーノルムは、一般的なスペクトルＬｐノルムのまさに特殊なケース（ｐ＝２）である。一般スペクトルＬｐノルムは、例えばハニング窓の高速フーリエ変換（ＦＦＴ）による短時間スペクトルを計算することにより音響信号の各時点で計算される。好適な実施形態は、８０００Ｈｚのサンプリング・レート、１０２４サンプルのＦＦＴフレームサイズ、各時間スライスのための６４サンプルのシフト幅、を用いる。スペクトル成分の絶対値のｐ乗の和として各時間スライスのＬｐノルムが計算され、選択的に次にｐ乗根も計算される。前述したように、ランドマークは各時刻で得られる値の極大値として選択される。スペクトルＬｐノルム法の一例を、図５に示す。図５は、ある音響信号の時間関数としてのＬ４ノルムのグラフである。極大値における破線はランドマークが選択される位置を示している。
【００４１】
Ｐ＝∞であるとき、Ｌ∞ノルムは事実上最大ノルムとなる。つまり、ノルムの値はスペクトル面における最大のスペクトル成分の絶対値である。このノルムはロバストなランドマークと良好な認識性能が得られ、また、音色の楽曲（tonal music）にも好適なものとなる。
【００４２】
あるいは、単一の時間スライスではなく、固定もしくは可変のオフセットでの複数の時間スライスにわたってスペクトル成分の絶対値のｐ乗の和をとることで、「マルチスライス」スペクトル・ランドマークが計算されうる。この拡張された和の極大値を見つけることによって、後述するマルチスライス・フィンガープリントの配置を最適化することが可能になる。
【００４３】
ランドマークが計算されると、ステップ４４で、各ランドマーク時間位置でフィンガープリントが計算される。フィンガープリントは一般に、サウンド記録における各ランドマーク時間位置もしくはその付近における特徴量のセットを集約した値もしくは値のセットである。この好適な実施形態においては、各フィンガープリントは複数の特徴量のハッシュ関数である単一の数値である。フィンガープリントがとりうるタイプは、スペクトル・スライス・フィンガープリント、マルチスライス・フィンガープリント、ＬＰＣ係数、ケプストラム係数を含む。もちろん、信号またはランドマーク付近の信号の特性を特徴付ける、フィンガープリントのあるゆるタイプは、本発明の範疇のものである。フィンガープリントは、あらゆるタイプのディジタル信号処理または信号の周波数分析によって計算されうる。
【００４４】
スペクトルスライス・フィンガープリントを生成するために、各ランドマーク時間位置の近くで周波数分析が行われ、いくつかのスペクトルピークの頂点が抽出される。単純なフィンガープリント値は、最大のスペクトルピークの周波数値にすぎない。このような単純なピークを用いると、雑音が存在しても非常に良好な認識性能が得られる。しかし、単一の周波数スペクトルスライス・フィンガープリントは、これらが固有でないために、他のフィンガープリント分析スキームよりもフェールス・ポジティブ（false positives）生成する傾向にある。２または３の最大スペクトルピークの関数からなるフィンガープリントを使用することにより、フェールス・ポジティブの数を減らすことが可能である。しかし、これらは、２番目に大きなスペクトルピークが、存在する雑音に対し十分に識別可能なほどに大きくないと、雑音に非常に弱い場合がある。つまり、計算されたフィンガープリント値は、信頼性のある再現につき十分ロバストでない場合がある。にもかかわらず、このケースの性能も良好である。
【００４５】
多くの音響の時間進行を利用するために、時間オフセットのセットをランドマーク時点に加えることによってタイムスライスのセットが計算される。得られた各タイムスライスで、スペクトルスライス・フィンガープリントが計算される。その後、得られたフィンガープリント情報のセットが結合されて、１スライスまたはマルチスライスのフィンガープリントが形成される。各マルチスライス・フィンガープリントは、時間進行をたどっていくので、単一のスペクトル・フィンガープリントに比べ、さらに特有のものとなり、後述するデータベース・インデックス探索においてマッチングの失敗が減ることになる。実験によれば、固有度合いを増したため、２つの時間スライスのそれぞれにおける単一の最大スペクトルピークから計算されたマルチスライス・フィンガープリントによって、後続のデータベース・インデックス探索の演算が速くなった（約１００倍の速度）ものの、大きな雑音が存在する状況では認識率の低下がみられた。
【００４６】
また、マルチスライス・フィンガープリントを計算するのに、与えられた時間スライスからの固定オフセットを用いるのではなく、可変のオフセットを用いることもできる。選択されたスライスへの可変オフセットは、フィンガープリントに対する、次のランドマークへのオフセット、または、“アンカー”ランドマークからのあるオフセット範囲におけるランドマークへのオフセットである。この場合において、ランドマーク間の時間差もマルチ周波数情報と共にフィンガープリントにエンコードされる。フィンガープリントにより次元を加えることにより、さらに固有度合が強まり、マッチングに失敗する機会も減る。
【００４７】
スペクトル成分に加え、他のスペクトル特性を抽出しフィンガープリントとして使用してもよい。線形予測符号化（ＬＰＣ）分析は、信号の予測可能な線形な特性、例えば、スペクトル形状の他にスペクトルピーク、を抽出するものである。ＬＰＣはディジタル信号処理の分野では周知である。本発明に対し、ランドマーク位置で固定された波形スライスのＬＰＣ係数が、量子化されたＬＰＣ係数をインデックス値にハッシングすることによって、フィンガープリントとして用いられうる。
【００４８】
周期性を測定するものとしてはケプストラム係数が有用であり、音声や多くの楽器のような調波構造の信号を特徴付けるのに使用することができる。ケプストラム分析はディジタル信号処理の分野で周知のものである。本発明に対しては、多数のケプストラム係数がインデックスにハッシングされてフィンガープリントとして使用される。
【００４９】
図６は、ランドマークおよびフィンガープリントが同時に計算される別の実施形態５０を示す図である。図３のステップ４２および４４がステップ５２、５４、５６で置き換えられている。後述するように、ステップ５２で、サウンド記録から多次元関数が計算され、その関数からランドマーク（５４）およびフィンガープリント（５６）が抽出される。
【００５０】
図６の実施形態において、ランドマークおよびフィンガープリントは、音声記録のスペクトログラムから計算される。スペクトログラムは音声記録の時間−周波数分析で、一般には高速フーリエ変換（ＦＦＴ）を用いて、音響サンプルの窓かけおよびオーバラップしたフレームがスペクトル分析されたものである。先述したように、好適な実施形態は、８０００Ｈｚのサンプリング・レート、１０２４サンプルのＦＦＴフレームサイズ、各時間スライスのための６４サンプルのシフト幅、を用いる。スペクトログラムの一例を、図７Ａに示す。横軸が時間で、縦軸が周波数である。連続する各ＦＦＴフレームは、時間軸に沿って等間隔に、縦に配置される。このスペクトログラムは、各時間−周波数ポイントでのエネルギー密度を示している。グラフ上の黒い部分は高いエネルギー密度を示す。スペクトログラムはオーディオ信号処理の分野では周知のものである。本発明に対し、ランドマークおよびフィンガープリントは、図７Ｂのスペクトログラムにおいて丸印で示したスペクトルの極大値のような点による凸角点から得られる。例えば、各ピークの時間−周波数座標が得られ、その時間はランドマークとしてとられ、周波数は対応するフィンガープリントの計算に使用される。スペクトルピーク・ランドマークはＬ∞ノルムに近似し、ここでノルムの最大絶対値がランドマーク位置を決定する。しかし、スペクトログラムにおいて、極大値の探索は、時間スライス全体にわたるよりもむしろ、時間−周波数平面のパッチに支配される。
【００５１】
以下では、サウンド記録の凸角点抽出分析から得られる凸角点のセットを、コンステレーション（constellation）という。極大値を有するコンステレーションに対し、好適な分析は、選択された各点の近隣にわたる時間−周波数平面でエネルギーが最大となる点を選択することである。例えば、(t0-T,f0-F), (t0-T, f0+F), (t0+T,f0-F), (t0+T, f0+F) を頂点とする四角形、すなわち、コンステレーションの適当な数が得られるように選ばれたＴおよびＦにより、２Ｔおよび２Ｆを辺の長さとする四角形、において、座標 (t0, f0) の点が最大エネルギーの点であるとき、その点が選択される。四角形の範囲は、周波数値に応じてそのサイズを変更することもできる。もちろん、領域の形状はあらゆるものを用いてもよい。時間−周波数平面における距離に応じて競合の時間−周波数エネルギーのピークが逆に重み付けされるように、すなわち、遠いポイントは低い重み付けとなるように、最大エネルギー基準を重み付けすることもできる。例えば、エネルギーは次式で重みづけされる。
【００５２】
S(t, f) / (1+Ct(t-t0)2+Cf(f-f0)2)
【００５３】
ただし、S(t,f) は点(t,f)における二乗振幅値、CtおよびCfは正の値である（定数である必要はない。）。その他の距離重み付け関数を用いてもよい。極大点選択の制約にはその他の（最大値ではない）凸角点特徴抽出手法を適用してもよく、これらも本発明の範疇のものである。
【００５４】
この方法は、上述した多くの同一の性質を有する単一の周波数スペクトルフィンガープリントに非常に近似した値の組が得られる。スペクトログラム時間−周波数法は、単一周波数法よりも多くのランドマーク／フィンガープリントのペアを生成するが、後述するマッチングステージにおけるマッチングの失敗も多く生じうる。しかし、これは、単一周波数スペクトルフィンガープリントよりもロバストなランドマーク分析およびフィンガープリント分析を提供する。なぜならば、音響サンプルに含まれる主要な雑音は各スライスにおけるスペクトルのあらゆる部分に広がっているわけではないからである。すなわち、スペクトルの部分における多くのランドマークとフィンガープリントとのペアは主要な雑音の影響をほとんど受けない。
【００５５】
このスペクトログラム・ランドマーク分析およびフィンガープリント分析法は、次元の１つを時間とする音響信号の多次元関数を計算し、その関数の値における凸角点を位置決めする分析方法の特殊なケースである。凸角点は極大値、極小値、零交差点などの特徴値とすることができる。ランドマークは凸角点の時間座標として取得され、対応するフィンガープリントが残りの座標の少なくともいずれかから計算されうる。例えば、多次元関数フィンガープリントを形成するために、多次元凸角点の非時間座標が共にハッシングされうる。
【００５６】
上記したマルチスライス・スペクトルフィンガープリントに対する可変オフセット法は、スペクトログラムまたはその他の多次元関数フィンガープリントに適用することができる。この場合において、図７Ｃのスペクトログラムに示されるように、コンステレーションの点が共に結ばれてリンク点が形成される。コンステレーションの各点は、ランドマーク時刻を定義するアンカーポイントとしての役を果たし、その他の点の残りの座標値が連結されてリンクされたフィンガープリントが形成される。例えば後ほど定義するような互いに近い点同士が共に連結されて、より識別および検索が容易となるより複合的な総合特徴フィンガープリントが形成される。マルチスライス・スペクトルフィンガープリントのように、複数リンク凸角点からの情報を単一のフィンガープリントに結合することの目的は、フィンガープリント値がより多くの値をとりうるようにし、それによりマッチングの失敗の可能性を減少させること、すなわち、同じフィンガープリントが２つの異なる音楽サンプルを指し示してしまう可能性を減少させることである。
【００５７】
原理的には、Ｎ個の凸角点の各々は、およそＮ／２通りのリンクを生成する２点連結法により互いの点に連結される。同様に、Ｋ点連結のために、コンステレーションから得られる可能な組み合わせの数はＮのオーダである。このような組み合わせの膨張を回避するために、互いに連結される近隣のポイントを制限することが望ましい。そのような制限を実現する一方法は、各アンカーポイントに対し「ターゲットゾーン」を定義することである。アンカーポイントはその後そのターゲットゾーン内のポイントと連結される。ターゲットゾーン内のポイントのサブセットを選択してすべてのポイントに連結されないようにすることが可能である。たとえば、ターゲットゾーン内の最大ピークに係るポイントだけに連結されるようにすることが可能である。ターゲットゾーンは固定された形状でもよいし、アンカーポイントの特徴に応じて変化する形状でもよい。スペクトルピークのコンステレーションに対するアンカーポイント (t0,f0) のターゲットゾーンの簡単な例は、tが範囲 [t0+L, t0+L+W] 内（ただし、Lはリード時間長、Wはターゲットゾーンの幅）にあるといったようなスペクトル面の点 (t,f) のセットである。この方法において、ターゲットゾーン内ですべての周波数がとりうる。たとえば、レート制御メカニズムが生成される連結組み合わせ数を変調するのに使用される場合には、LまたはWは可変とすることができる。かわりに、たとえば、周波数fが範囲 [f0-F,f0+F] 内（ただし、Fは境界パラメータとする。）にあるといったようなターゲットゾーンの制約によって、周波数制限を実現することができる。周波数制限の利点は次のとおりである。心理音響学において、音符の並びが互いに近い周波数を有するとき、メロディーがよく干渉する傾向があることが知られている。このような制約は、心理音響学のモデリングは本発明の目標に必要でないにもかかわらず、より「心理音響学的に実際的な」認識性能を示すことを可能にする。fを [f0-F,f0+F] の範囲外に選択するような、逆のルールを考えることも可能である。これは、コンステレーション抽出結果が、時間的に近くなおかつ同じ周波数を有する時間−周波数ポイントの吃音列を発するケースを回避することを可能にするように、周波数が相違するポイントを連結させる。その他の局所性のパラメータのように、Fは定数である必要はなく、例えばf0の関数としてもよい。
【００５８】
時間座標にフィンガープリント値のアンカー凸角点が含まれないときは、フィンガープリントが時不変とするために相対時間値を用いる必要がある。たとえばフィンガープリントは、(i) 非時間座標値、および／または、(ii) 凸角点の対応する時間座標値の差、の関数とすることができる。時間差はたとえば、アンカーポイントに関して取得でき、あるいは、連結されたセットにおける一連の凸角点間の逐次の差分として取得できる。座標および差分値は連続ビットフィールドにパックされてハッシングされたフィンガープリントを形成することができる。座標値のセットをフィンガープリント値にマッピングする方法は数多くあり、それらは本発明の範疇に含まれることは当業者には明らかであろう。
【００５９】
この方法の具体例は、座標 (tk, fk)（ただし、k=1, . . . , N）においてN＞1 個の連結されたスペクトルピークを用いる。そして、(i) 第１ピークの時刻t1がランドマーク時刻として取得され、(ii) 周波数fk（ただし、k=1, . . . , N）での、連結ピークの時間差Δtk=tk-t1（ただし、k=2, . . . , N）が共にハッシングされてフィンガープリント値が形成される。フィンガープリントはΔtk-fk座標のとりうるすべての点またはサブセットから演算することができる。たとえば、望まれる場合には、時間差分のすべて一部または全部を除外することができる。
【００６０】
複数ポイントを用いてフィンガープリントを形成することの他の利点は、たとえばサウンド記録が元の録音スピードと異なるスピードで再生されたときの時間伸縮に対しても、フィンガープリント符号化を不変とすることができる点にある。この利点は、スペクトル法および時間スライス法の両方に当てはまる。伸長された時間信号においては、時間差と周波数は相反する関係を有する（たとえば、２点間の時間差が1/2に縮められると周波数は２倍になる）ことに留意されたい。この方法は、フィンガープリントから時間伸縮を除外する方法で時間差と周波数との結合によるデータを利用する。
【００６１】
たとえば、座標値 (tk,fk)（ただし、k=1, . . . , N）に対するＮポイントスペクトルピークの場合において、フィンガープリントにハッシュするためのとりうる中間値は、Δtk=tk-t1（ただし、k=2, . . . , N, また、fk, k=1, . . . , N）である。いずれかの周波数を基準周波数f1として、（ｉ）他の周波数との商、および（ii）時間差との積、を計算することにより、中間値を、時間伸縮に対して不変値とすることができる。たとえば、中間値をgk=fk/f1（ただし、k=2, . . . , N）、sk=Δtk/f1（ただし、k=2, . . . , N）とすることができる。サンプルをα倍に速めると、周波数fkはαfk、時間差tkはΔtk/αとなり、そのため、gk=αfk/αf1、sk=(Δtk/α)(αf1)=Δtkf1となる。そして、これらの新たな中間値は、時間伸縮に左右されないハッシュされたフィンガープリント値を形成するための関数を用いて結合される。たとえば、gkおよびskの値は連結されたビットフィールドにパッキングすることでハッシュされうる。
【００６２】
あるいは、基準周波数ではなく、基準時間差（たとえばΔt2）を用いてもよい。この場合には、（ｉ）他の時間差との商Δtk/Δt2、（ii）周波数との積Δt2fk、として新たな中間値が計算される。この場合は基準周波数を用いるのと等価である。結果の値は上記のgkおよびskの積および商から生成されうるからである。周波数比の相対性を全く等しく用いることもできる。つまり、元の中間値の対数値の和および差をそれぞれ、積と商に替えて用いることもできる。このような数学的操作の交換（commutations, substitutions, permutations）によって得られた時間伸縮に左右されないフィンガープリント値はすべて、本発明の範疇のものである。また、時間差を相対化する複数の基準周波数もしくは基準時間差を用いてもよい。複数の基準周波数もしくは基準時間差の使用は単一の基準値を用いるのと等価である。gkおよびskの演算操作によって同じ結果を得ることができるからである。
【００６３】
図３および図６に説明を戻す。上述した方法のいずれかによるランドマーク分析およびフィンガープリント分析により、図８Ａに示すようなSound_IDのインデックスセットが得られる。与えられたサウンド記録のインデックスセットは、ペアの値（fingerprint, landmark）のリストである。インデックス付けされた各サウンド記録は典型的には、そのインデックスセットに1,000のオーダの（fingerprint, landmark）のペアを有する。上記した第１の実施例では、ランドマーク分析とフィンガープリント分析の手法は基本的には独立であり、両者は別々のもので、かつ交換可能なモジュールとして取り扱うことができる。システム、信号品質、認識される音響のタイプに依存して、多くの異なるランドマーク分析やフィンガープリント分析のモジュールのいずれかを使用することができる。実際に、インデックスセットは値のペアの単純な複合化であるから、複数のランドマーク分析およびフィンガープリント分析の手法を同時に使用することが可能であり、またその方が好ましいことが多い。たとえば、ユニークな調音パターンを検出には、あるランドマーク分析およびフィンガープリント分析手法がよいが、パーカッションの識別には不十分である場合もあり、かかる場合には、対立する属性を有する異なるアルゴリズムがよい、というものである。複数のランドマーク／フィンガープリント分析を用いる手法により、よりロバストで十分なレンジの認識性能が得られる。数種類のフィンガープリント分析のためにいくらかのレンジを確保しておくことによって異なるフィンガープリント分析手法を一緒に用いてもよい。たとえば、３２ｂｉｔのフィンガープリント値において、初めの３ｂｉｔが８つのフィンガープリント分析手法を記述するのに使用し、残りの２９ｂｉｔが符号化に使用するようにしてもよい。
【００６４】
音響データベースのインデックスが付与される各サウンド記録に対してインデックスセットが生成される。ここで、検索可能なデータベースインデックスは高速（すなわち対数時間）検索を可能にするような方法で構築される。これは、ｓｔｅｐ４６で、各インデックスセットにおける各２つ組に対応するsound_IDを追加して得られる３つ組（fingerprint, landmark, sound_ID）のリストを構築することにより実現される。全てのサウンド記録に対しこのような３つ組が大規模なインデックス・リストとして収集される。図８Ｂにこの一例を示す。後続の検索処理を最適化するために、３つ組のリストはフィンガープリントによってソーティングされる。高速なソーティング・アルゴリズムは周知であり、D. E. Knuth、“The Art of Computer Programming, Volume 3: Sorting and Searching, Reading, Mass”（Addison-Wesley, 1998）に詳しく論じられている。これは、この引用により本明細書に含められる。高性能ソーティング・アルゴリズムは、リストのエントリ数をNとすると、NlogN回でリストをソートすることができる。
【００６５】
インデックス・リストがソーティングされると、ｓｔｅｐ４８で、リスト内の固有のフィンガープリントの各々が新たなマスター・インデックス・リストに集められるように区分される。図８Ｃにこの一例を示す。マスター・インデックス・リストの各エントリは、フィンガープリント値と（landmark, sound_ID）のリストへのポインタとを含む。インデックスされるサウンド記録の数および特徴に依存して、収集結果全体に特定のフィンガープリントが数百回以上現れることが考えられる。インデックス・リストをマスター・インデックス・リストに再構成することは任意であるが、各フィンガープリント値が１回しか現れないので、メモリの節約になる。現行のリストのエントリ数が固有の値のリストに大幅に減少するので、後続のデータベース検索の高速化にもなる。あるいは、バランス木（B-tree）に各３つ組を挿入することでマスター・インデックス・リストが構成されるようにしてもよい。周知のように、マスター・インデックス・リストを構築する方法は他にもある。マスター・インデックス・リストは、信号認識処理中の高速アクセスのためにＤＲＡＭのようなシステムメモリに保持されることが好ましい。マスター・インデックス・リストは、図２に示すようなシステム内の単一ノードのメモリに保持するようにしてもよい。あるいは、マスター・インデックス・リストは複数のリストに分割され複数の演算ノード間に分配されるようにしてもよい。上記した音響データベース・インデックスは図８Ｃに示したマスター・インデックス・リストであることが好ましい。
【００６６】
音響データベース・インデックスはオフラインで構築され、認識システムに新たな音響が入力されたときに追加的に更新することが好ましい。リストを更新するために、新たなフィンガープリントがマスター・インデックス・リストのしかるべき位置に挿入されうる。新たなサウンド記録が既に存在するフィンガープリントを含んでいる場合には、対応するペア（landmark, sound_ID）が、それらのフィンガープリントに対して既に存在するリストに追加される。
【００６７】
（認識システム）
上記のように生成されたマスター・インデックス・リストを用いて、入力される音響サンプルに対して音響認識が行われる。音響サンプルは典型的にはそのサンプルの識別に関心を持っているユーザによって供給される。たとえば、ユーザがラジオで新曲を聴いてその曲のアーティストとタイトルを知りたくなるであろう。サンプルはあらゆる環境から作り出すことができる。たとえば、ラジオ放送、ディスコ、パブ、サブマリーン（submarine）、サウンドファイル、ストリーミング・オーディオのセグメント、ステレオシステムなど。そして、これらは背景雑音、音飛び（dropouts）、あるいは話し声を含んでいてもよい。ユーザは、オーディオサンプルを認識システムに供給する前にそのオーディオサンプルを、応答装置、コンピュータファイル、テープレコーダ、電話もしくは移動電話、ボイスメールシステムといった記憶デバイスに記憶させることができる。システム設定およびユーザ設定に基づいて、あるゆるアナログもしくはディジタルの音源（ステレオシステム、テレビ、コンパクトディスクプレーヤー、ラジオ放送、応答装置、電話、移動電話、インターネットストリーミング放送、ＦＴＰ、電子メールの添付ファイルとしてのコンピュータファイル、これらの記録物を送信に適したその他の装置）から、オーディオサンプルが本発明の認識システムに供給される。サンプルは、その音源に依存して、音響波、無線波、ディジタルオーディオＰＣＭストリーム、圧縮ディジタルオーディオストリーム（ドルビーデジタル、ＭＰ３など）、インターネットストリーミング放送、などの形式であったりする。ユーザは、電話、移動電話、ＷＥＢブラウザ、電子メールなどの標準的なインタフェースを介して認識システムと対話する。サンプルはシステムによってキャプチャされ、リアルタイムに処理されるか、あるいは、過去にキャプチャされたサウンド（たとえばサウンドファイル）から処理するために再生されることになる。キャプチャ中、オーディオサンプルはマイクロホンのようなサンプリングデバイスによってディジタルで抽出されてシステムに送られる。サンプルは、キャプチャ方法に依存して、チャネルやサウンドキャプチャ装置の制限によって更に劣化するであろう。
【００６８】
サウンド信号がディジタル形式に変換されると、認識のための処理が行われる。データベースファイルのインデックスセットの構築として、そのサンプルに対し、サウンド記録データベースを処理するのに使用したのと同じアルゴリズムでランドマークおよびフィンガープリントが計算される。オリジナルのサウンドファイルが大きく歪んだものの処理しても、オリジナル記録に対して得られたランドマークとフィンガープリントのペアのセットと同一もしくは近似のものが得られるのであれば、方法は最適に動作する。サウンドサンプルに対し得られたインデックスセットは、図９Ａに示す分析値のペアセット（fingerprint, landmark）となる。
【００６９】
サウンドサンプルについての分析値ペアが与えられると、データベース・インデックスが検索されて、マッチしそうなファイルを特定する。検索は次のように実行される。未知サンプルのインデックスセットにおける各（fingerprintk, landmarkk）ペアは、マスター・インデックス・リストにおけるfingerprintkを検索することで処理される。順序付きリストに対する高速検索アルゴリズムは周知であり、D. E. Knuth、“The Art of Computer Programming, Volume 3: Sorting and Searching, Reading, Mass”（Addison-Wesley, 1998）に詳しく論じられている。マスター・インデックス・リストのfingerprintkが見つかると、マッチする（landmark*j, sound_IDj）ペアの対応するリストがコピーされ、landmarkkを加えて、（landmarkk, landmark*j, sound_IDj）の形式の３つ組のセットを形成する。ここで、アスタリスク（*）はデータベース内のインデックスファイルのいずれかのランドマークを示しており、アスタリスクのないランドマークはサンプルのものを示している。場合によっては、両者のフィンガープリントが同一のときに限りマッチするとする必要はなく、フィンガープリントが互いに近似している（たとえば、差が予め定められたしきい値に収まる）場合にはマッチしていると判定することが好ましい。両者同一によりマッチするフィンガープリント同士も、近似によりマッチするフィンガープリント同士も、ここでは「同等（equivalent）」という。３つ組におけるsound_IDjは、アスタリスクの付いたlandmarkを有するファイルに対応する。したがって、各３つ組は、同等のフィンガープリントが計算されたときの、２つの別個のランドマークを含む。１つはデータベース・インデックスのもので、もう１つはサンプルのものである。この処理は、入力サンプルのインデックスセットの範囲にわたるすべてのｋについて繰り返される。得られたすべての３つ組は、図９Ｂに示すような大規模な候補リストに収集される。候補リストは、フィンガープリントのマッチングによるサウンドファイルのsound_IDを含んでおり、これらのsound_IDが入力されたサウンドサンプルに対する識別の候補であるので、そのように呼ばれる。
【００７０】
候補リストが集められた後は、sound_IDによるセグメンテーションが行われる。この簡便な方法は、sound_IDによって候補リストをソーティングするか、候補リストをバランス木（B-tree）に挿入することである。多くのソーティング・アルゴリズムが適用可能であることは先述したとおりである。この処理の結果が、候補sound_IDのリストとなり、それぞれが、図９Ｃに示すように、オプションとしてそのsound_IDが除去された、サンプルのランドマーク時刻とデータベースファイルのランドマーク時刻とのペア（landmarkk, landmark*j）の散布リストを有する。したがって各散布リストは、互いが同等のフィンガープリントによって特徴付けられるランドマークのセットを含むことになる。
【００７１】
そして、sound_IDがサンプルにマッチするかどうかを判断するために、各候補sound_IDに対する散布リストが分析される。極めて小さい散布リストしかない候補を除外するために、オプションとして、しきい値処理ステップを用いてもよい。明らかに、散布リストにエントリが１つしかない候補、すなわち、サンプルと同様のフィンガープリントが１つしかない候補は、そのサンプルとはマッチしない。１以上のあらゆる適切なしきい値を用いてもよい。
【００７２】
最終的な候補数が決定されると、ベストな候補が特定される。以下のアルゴリズムでベストな候補が特定できなければ、認識失敗のメッセージが返される。このマッチング処理のキーポイントは、両者の時間軸が固定されていると想定して、サウンドのマッチングにおける時間の進行が、リニアな対応関係に従っているはずである点である。これは、いずれかのサウンドが作為的に非線形に歪んでいたり、速度が小刻みに揺れる異常があるテープデッキの如く再生装置に欠陥があるようなことがないかぎり、そのとおりになる。したがって、与えられたsound_IDの散布リストにおける正常なランドマークペア（landmarkn, landmark*n）は次式のリニアな対応関係を有するはずである。
【００７３】
landmark*n=m*landmarkn+offset
【００７４】
ただし、ｍは傾きで１に近い値である。landmarknは入力されたサンプルにおける時点、landmark*nはsound_IDによってインデックスされたサウンド記録における対応する時点、offsetは入力されたサウンドサンプルの始点に対応するサウンド記録への時間オフセットである。特定の値ｍおよびoffsetによって上式に適合するランドマークペアは「リニアな関係」にあるという。明らかに、リニアな関係にあることの概念は、対応するランドマークペアが２以上あれば有効である。このリニアな関係は、重要でない範囲外のランドマークペアを除外すると、正常なサウンドファイルを高い確率で識別する注意されたい。２の別個の信号が多数の同一のフィンガープリントを含むことが可能であるとはいえ、これらのフィンガープリントが同じ相対的な時間進行を有することはまずない。リニアな対応関係の要求は本発明のキーとなる特徴であり、単純に普通の特徴量のトータル数をカウントしたり特徴量の類似度を測定するといった技術よりも大きく認識性能を上げることができる。実際、本発明のこの側面により、たとえオリジナル記録のフィンガープリントが入力されたサウンドサンプルに現れるのが１％に満たないとしても、すなわち、サウンドサンプルが非常に短かったり大きく歪んでいる場合であったとしても、サウンドを認識することができる。
【００７５】
そのため、入力されたサンプルに対してマッチするかどうかの判断の問題が、与えられた散布リストのランドマークポイントの散布図のうちで傾き１程度の斜線をみつけることに相当するものへと絞り込まれる。図１０Ａおよび図１０Ｂに散布図の２つの例を示す。横軸がサウンドファイルのランドマークで、縦軸が入力されたサウンドサンプルのランドマークである。図１０Ａにおいて、ほぼ１の傾きの斜線が認識される。これは曲が確かにサンプルにマッチした、すなわち、そのサウンドファイルがベストなファイルであることを示している。横軸での切片は、サンプルの始めにおけるオーディオファイル内のオフセットを示している。図１０Ｂの散布図には統計上の有意な斜線がみられない。これは入力されたサンプルに対しそのサウンドファイルはマッチしないことを示している。
【００７６】
散布図における斜線をみつける方法は多くあり、これらはすべて本発明の範疇のものである。「斜線の特定（locating a diagonal line）」の用語は、明示的に斜線を生成せずに斜線を特定することに相当するすべての方法をいう。好適な方法は、上式の両辺からm*landmarknを引いて次式を得ることにより開始する。
【００７７】
(landmark*n-m*landmarkn)=offset
【００７８】
ｍはほぼ１と想定する（すなわち、時間伸縮がないと想定する）と、次式が得られる。
【００７９】
(landmark*n-landmarkn)=offset
【００８０】
斜線を特定するときの問題は、ほぼ同じオフセット値で分割される所定のsound_IDに対する複数のランドマークペアをみつけることに絞られる。これは、１のランドマークと他のランドマークとを引き算して得られたオフセット値のヒストグラムを収集することにより、容易に実現できる。高速ソーティング・アルゴリズムを用いて、あるいは、カウンタでビンのエントリを生成しバランス木（B-tree）に挿入することにより、このヒストグラムを加工してもよい。ヒストグラムのベストなオフセット・ビンは最大のポイント数を含む。以下では、このビンをヒストグラムのピークという。入力されたサウンド信号が正常なライブラリ・サウンドファイルに十分に含まれていればオフセットは正のはずであるから、負のオフセットとなるランドマークペアは除外される。同様に、ファイルの終端を超えるオフセットも除外される。ヒストグラムのベストなオフセット・ビンにおけるポイント数が各予選sound_IDに対し示される。この数は各サウンド記録のスコアとなる。最高スコアの候補リストにおけるサウンド記録がベストとして選ばれる。識別の成功を通知すべくベストなsound_IDが下記のようにユーザにレポートされる。識別の失敗を防ぐために、最小しきい値スコアを用いて識別処理の成功をゲート制御するようにしてもよい。ライブラリ・サウンドがしきい値を超えるスコアでなければ、認識はされず、その旨ユーザに通知される。
【００８１】
入力されたサウンド信号が複数のサウンドを含む場合、それぞれのサウンドを認識することができる。この場合、位置合わせ検査において複数の当たり（winner）が特定される。サウンド信号が複数の当たりを含んでいることを知っている必要はない。位置合わせ検査で、残りのスコアよりもかなり高いスコアのsound_IDが２つ以上特定されるであろうからである。よく使われるフィンガープリント分析方法は良好な線形な重ね合わせを示し、そのため個々のフィンガープリントが抽出される。たとえば、スペクトログラム・フィンガープリント分析方法は線形な重ね合わせを示す。
【００８２】
サウンドサンプルが時間伸縮を受けると、傾き（slope）は等しく１とはならない。時間伸縮を受けたサンプルの傾きを１と仮定する（フィンガープリントが時間伸縮に対し不変であると仮定する）と、計算されるオフセット（offset）値は均一でなくなる。これに対処してほどほどの時間伸縮に適応する一方法は、オフセット・ビンのサイズを増加させること、すなわち、オフセットが均一になる範囲を考慮することである。一般に、各点が直線上に位置しなければ、計算されるオフセット値が大きく異なり、オフセット・ビンのサイズがわずかに増加しても、フェールス・ポジティブを大量に生じることはない。
【００８３】
直線をみつける手法は他にもある。たとえば、マシン・ビジョンやグラフィックの研究の分野で周知な、T. Risse, "Hough Transform for Line Recognition," （Computer Vision and Image Processing, 46, 327-345, 1989）に記述されているRadon変換またはHough変換を用いてもよい。Hough変換では、散布図の各点は（slope, offset）空間における直線に射影する。したがって、散布図の点の集合がHough変換における２空間の直線上に投影される。Hough変換におけるピークはパラメータ直線の交点に対応する。このような所定の散布図の変換のグローバルピークは、Hough変換における交差する直線の最大数、つまり共直線性の点の最大数、を示している。５％のスピードの変動を許容すべく、たとえば、Hough変換の構成を傾きパラメータが0.95から1.05の間で変動する領域に制限して、それにより演算量を節約するようにしてもよい。
【００８４】
（階層検索）
非常に小さな散布リストで候補をふるい落とすしきい値処理ステップに加えて、さらに効果的な改良策を施すこともできる。改良策の１つは、発生確率に応じてデータベース・インデックスを少なくとも２つの区分にセグメント化しておき、サンプルのマッチングをとる確率の高いほうのサウンドファイルのみをまず検索するというものである。分割は処理のさまざまな段階で行うことができる。たとえば、いずれか１のセグメントでｓｔｅｐ１６またはｓｔｅｐ２０が実行されるときに、マスター・インデックス・リスト（図８Ｃ）を２以上の区分にセグメント化することが可能である。すなわち、データベース・インデックスの一部分だけからマッチング・フィンガープリントに対応するファイルが検索され、その一部分から散布リストが生成される。ベストなサウンドファイルが特定されなければ、別のデータベース・インデックスについて処理が繰り返される。別の実現例では、データベース・インデックスからすべてのファイルが検索されるが、斜線検査は異なるセグメントで別々に行われる。
【００８５】
この手法を用いて、演算量が集中している斜線検査は、まず、データベース・インデックスにおけるサウンドファイルの小さなサブセットで行われる。斜線検査は検査されるサウンドファイルの数に対してほぼリニアな時間成分を有しているので、階層検索を行うことは大変有効である。たとえば、サウンド・データベース・インデックスが1,000,000のサウンドファイルを表すフィンガープリントを含んでいるが、高い頻度で検索照会されるサンプルにマッチするのは1000ファイル程度しかない場合、たとえば、検索照会の95％が1000ファイルに対するもので、検索照会の５％だけが残りの999,000のファイルに対するものである場合、を想定する。演算コストがファイル数の一次従属であると仮定すると、その演算コストは、1000ファイルの95％時間に比例し、999,000ファイルの５％時間に比例する。そうすると、平均演算コストはおよそ50,900に比例する。したがって、階層検索は演算負荷を1/20近くに抑えることができる。もちろん、データベース・インデックスは、２レベル以上の階層（たとえば、ニュー・リリースの曲のグループ、最近リリースされた曲のグループ、古くて流行らない曲のグループ）にセグメント化することができる。
【００８６】
上述したように、検索は、サウンドファイルの高確率のファイルの集合である第１のサブセットについてまず行われ、この第１の検索が失敗したときにのみ、残りのファイルを含む第２のサブセットについて行われる。各オフセット・ビンにおけるポイント数が予め定められたしきい値に届かないときは、斜線検査の失敗となる。かわりに、２つの検索を並列的（同時）に実行させてもよい。第１のサブセットの検索で正しいサウンドファイルが特定されると、第２のサブセットの検索を終了させるための信号が送られる。第１のサブセットの検索で正しいサウンドファイルが特定されなければ、ベストなファイルが特定されるまで第２のサブセットの検索が継続される。これら２つの異なる実現例は演算量と時間のトレードオフの関係にある。第１の実現例は演算量が軽いが第１の検索が失敗に終わると若干の遅延を招く。これに対して、第２の実現例は、ベストなファイルが第１のサブセットにある場合には演算量が多いが、そうでなければ遅延は最小化される。
【００８７】
リストのセグメント化の目的は、サウンドファイルが検索照会のターゲットである確率を見積もって、検索を、照会サンプルにもっともマッチしそうなファイルに限定することにある。データベースのサウンドに確率を割当ててソーティングする方法はいくつも考えられるが、それらはすべて本発明の範疇のものである。確率は、ベストなサウンドファイルとして識別される時期の新しさ（recency）や頻度（frequency）に基づいて割り当てられるのが好ましい。時期の新しさは、とりわけポピュラーソングに対しては有用な測定値である。新曲がリリースされるので、音楽の関心が時間の流れにつれて非常に急速に変化するからである。確率スコアが計算されると、ファイルにランキングが割り当てられ、そのランキングでそのリスト自身をソートする。ソートされたリストは検索のために２以上のサブセットにセグメント化される。小さなサブセットは所定数のファイルを含む。たとえば、ランキングがたとえば上位1000ファイルにおけるファイルを特定すると、そのファイルは速い検索のための小さなサブセットに置かれる。かわりに、２つのサブセットに対するカットオフポイントを動的に調整するようにしてもよい。たとえば、所定のしきい値を超えるスコアのファイルすべてを第１のサブセットに置いて、それにより各サブセット内のファイル数が頻繁に変わるようにしてもよい。
【００８８】
確率を計算する特別な一方法は、照会サンプルがマッチしたと識別された各時刻でサウンドファイルのスコアを１ずつ増加させることである。時期の新しさを考慮するために、新しい照会が古い照会よりもランキングで強い結果となるように、スコアのすべてが周期的に下方修正される。たとえば、照会があるごとにすべてのスコアを一定倍率でもって段階的に減らすようにすることができる。その結果、スコアは更新されなければ指数関数的に減少していく。データベースにおけるファイル数（難なく100万くらいになりうる）に依存して、この方法は照会がある度に大量のスコアの更新を要することになり、場合によっては望ましくない状況となる。代案として、相対的に少ない頻度の間隔（たとえば１日に１回）でスコアを下方修正するようにしてもよい。少ない頻度での修正による結果は、照会の度に修正する場合の結果とだいたい似たようなものであるが、まったく同じではない。しかし、ランキングを更新するための計算負荷は非常に小さくなる。
【００８９】
この時期の新しさによる調整の変形例としては、指数関数的に増加するスコア更新at（ただし、tは最後の一括更新からの経過時間）を照会の都度ベストなサウンドファイルに付加することが考えられる。一括更新の都度、aT（ただし、Tは最後の一括更新からの総合経過時間）で割り算することで全スコアが下方修正される。この変形例において、aは近時率（recency factor）で、１より大の値である。
【００９０】
上述したランキング処理に加えて、リスティングの強弱をつけるのに役立つように事前の知識を導入することもできる。たとえば、ニューリリースは古い曲よりも問い合わせが多く来るであろう。そこで、ニューリリースは、照会サンプルにマッチする確率の高い曲を集めた第１のサブセットに自動的に置くようにしてもよい。これは上記した自己ランキングアルゴリズムとは独立に行われうる。自己ランキングの特徴をも用いると、ニューリリースは第１のサブセット内のいずれかの位置する初期ランキングに割り当てられる。ニューリリースは、リストの最上位、高い確率の曲のリストの末尾、もしくはリスト中の中間のどこか、にシードされうる。検索の目的のため、ランキングは時間経過につれて収束して関心の真のレベルを反映するようになるので、初期位置は問題にならない。
【００９１】
代替の実施例においては、時期の新しさのランキングの順序で検索を行い、sound_IDスコアが所定のしきい値を超えた時点で終了する。これは、各セグメントがsound_IDを１つだけを含む上記の方法と等価である。
【００９２】
ベストなサウンドのスコアは他のすべてのサウンドファイルのスコアよりもかなり高いことが実験で分かり、そのため、わずかな実験で好適なしきい値を選択することができる。この実施例を実現する一方法は、データベース・インデックスのすべてのsound_IDを、時期の新しさに応じて、スコアが同一の場合に任意の決定で、ランクづけすることである。時期の新しさの各ランキングはユニークであるから、時期の新しさのスコアとsound_IDとの間は１対１でマッピングされる。そして、候補sound_IDのリストとそれに付随する散布リスト（図９Ｃ）を作成するためにsound_IDをソーティングするときに、ランキングがsound_IDのかわりに用いられる。３つ組（fingerprint, landmark, sound_ID）のインデックス・リストが生成され、そのインデックス・リストがマスター・インデックス・リストにソートされる前に、ランキング番号をインデックスと結合してもよい。そして、sound_IDについてランキングが実行される。かわりに、検索および更新機能を用いてランキング付きsound_IDを更新することもできる。ランキングが更新されると、新たなランキングが古いランキングのところに割り当てられ、マッピングの整合性が維持される。
【００９３】
代替案として、ランキングを後の処理において結合するようにしてもよい。いったん散布リストが生成されると、ランキングを各sound_IDに対応付けることができる。そして、そのセットがランキングによってソートされる。この実現例においては、散布リストへのポインタだけを修正する必要がある。散布リストへのグルーピングを繰り返す必要はない。後の処理において結合することの利点は、ランキングが更新される度にデータベース・インデックス全部を再生成する必要がない点である。
【００９４】
流行によるランキングはそれ自身、経済的価値の対象となりうることにも注目すべきである。すなわち、ランキングは、知らないサウンドサンプルを確認しようとする消費者の好みを反映するものである。多くの場合、曲の記録物の購入への欲求によって照会が指示される。実際に、ユーザについての人口情報が分かっていれば、要求された人口グループの各々に対して別のランキング手法を実現することもできる。ユーザの人口グループは、そのユーザが認識サービスに登録したときに受けたプロフィール情報から得ることができる。標準協調フィルタリング技術により動的に判断することも可能である。
【００９５】
リアルタイムシステムでは、サウンドが認識システムに時間経過につれて追加的に供給され、パイプライン認識が可能である。この場合、セグメント内で入力データを処理してサンプルのインデックスセットを追加的に更新することが可能である。各更新周期の後、上述の検索および検査ステップによりサウンド記録の候補リストを検索するために、新たな拡張インデックスセットが用いられる。新たに得られたサンプル・フィンガープリントにマッチするフィンガープリントに対しデータベース・インデックスが検索され、新しい３つ組（landmarkk, landmark*j, sound_IDj）が生成される。新たなペアが散布リストに付加されて、ヒストグラムが追加される。このアプローチの利点は、サウンド記録を正確に識別するのに十分なデータが収集されると、たとえば、あるサウンドファイルのオフセット・ビンにおけるポイント数が高いしきい値を超える場合、もしくは２番目に高いサウンドファイルのスコアを超える場合には、データ収集を中断してその結果を通知することができることである。
【００９６】
いったん正しいサウンドが識別されると、適当な方法でその結果がユーザもしくはシステムに通知される。 その結果はたとえば、コンピュータ印刷、電子メール、ｗｅｂ検索結果ページ、移動電話へのＳＭＳ（short messaging service）テキストメッセージ、コンピュータ生成された電話による音声メッセージ、ユーザが後でアクセスできるｗｅｂサイトもしくはインターネット・アカウントへの結果のポスティングなどによって通知されうる。通知された結果には、曲の名称やアーティスト、クラシック曲の作曲者やレコーディング属性（たとえば演奏者、指揮者、会場）、広告の会社やプロダクト、その他各種の好適な識別子などの、サウンドの識別情報を含めてもよい。くわえて、経歴情報、周辺のコンサート情報、その他ファンが関心のある情報を提供してもよいし、そのような情報へのハイパーリンクを提供してもよい。通知される結果には、サウンドファイルの絶対スコアもしくは次にスコアの高かったサウンドファイルとの比較におけるスコアを含めてもよい。
【００９７】
認識方法の有用な成果の一つは、同じサウンドの異なる２つの演奏を混同しない点である。たとえば、クラシックの同じ曲でも演奏が異なれば、たとえ人が両者の違いを検知できなくても、それらを同一とみなさない。ランドマーク／フィンガープリントのペアとそれらの時間進行が２つの演奏ではマッチする可能性が非常に低いからである。本実施例では、リニアな対応関係が特定されるためには、ランドマーク／フィンガープリントのペアが互いに約10msの中になければならない。この結果、本発明の自動認識によって、あらゆるケースにおいて、適切な演奏／サウンドトラックやアーティスト／ラベルが得られる。
【００９８】
（実現例）
以下、本発明の好適な実現例である連続スライディング・ウィンドウ・オーディオ認識について説明する。マイクロホンまたはその他の音源が連続的にバッファにサンプリングされ、過去Ｎ秒のサウンドの記録が得られる。 サウンド・コンテンツのＩＤを突き止めるべく、サウンド・バッファの内容が周期的に分析される。サウンド・バッファは固定サイズとしてもよいし、サウンドがサンプリングされるときのサイズに応じて増大するようにしてもよい。後者は、オーディオ・サンプルの順次増大セグメントとよばれる。サウンド記録が識別されたことを示すための通知がなされる。たとえば、ログファイルが収集され、もしくは、タイトル、アーティスト、アルバムカバーアート、歌詞といった 曲の情報や購入情報を示す装置にディスプレイ表示される。重複を避けるため、認識されるサウンドのＩＤが変わったとき、たとえば、ジュークボックスのプログラムが変わったとき、にだけ通知がなされる。かかる装置は、あらゆるサウンド・ストリーム（ラジオ、インターネット・ストリーミング・ラジオ、隠しマイク、電話呼び出しなど）から再生された音楽のリストを生成するのに使用されうる。曲ＩＤに加え、認識時刻のような情報のログをとることができる。特定情報が（例えばＧＰＳから）取得可能であれば、これらの情報のログをとることができる。
【００９９】
識別を達成するため、各バッファを初めから識別してもよい。かわりに、サウンドパラメータをたとえばフィンガープリントまたは他の中間特徴量抽出形式に抽出し、第２バッファに記憶してもよい。 第２バッファの前に、新たなフィンガープリントを、バッファの最後から廃棄される古いフィンガープリントとともに加算してもよい。このようなローリング・バッファ法の利点は、サウンドサンプルのオーバーラップしているセグメントで同じ分析を重複して行う必要がなく、そのため演算量を節約できることである。ローリング・フィンガープリント・バッファの内容に対し識別プロセスが周期的に実行される。小型の携帯型装置の場合、フィンガープリント・ストリームはデータ量が非常に大きいので、フィンガープリント分析をその装置で行い、その結果を、比較的低い帯域のデータチャネルを用いて認識サーバに送信するようにしてもよい。ローリング・フィンガープリント・バッファは、これを携帯型装置に置き、各回ごとに認識サーバに送信してもよいし、認識サーバにローリング・フィンガープリント・バッファを備え、サーバで認識セッションが連続的に行われるようにしてもよい。
【０１００】
このようなローリング・バッファ認識システムでは、認識するのに十分な情報が得られしだい新たなサウンド記録が認識されうる。十分な情報はバッファ長より少なくてもよい。たとえば、特徴的な曲は１秒間の演奏で一義的に認識されうるし、バッファが１５〜３０秒の長さを有しているとしても、システムは１秒で周期的に認識し、曲が直ちに認識されうる。逆に、特徴的でない曲が認識にさらに数秒間のサンプルを必要とする場合には、システムは曲のＩＤを宣言する前に長時間待たなければならない。このスライディング・ウィンドウ認識法においては、サウンドが識別されうるようになりしだい認識される。
【０１０１】
次の点に注意することが重要である。本発明は全機能を備えたシステムおよび方法を前提に説明されたが、本発明の構成はさまざまな形式による命令を格納したコンピュータ読み取り可能な媒体のかたちで流通させることが可能であり、また、本発明はその流通に実際に用いるメディアに記録する信号の形式にかかわらず適用されることは当業者には理解されよう。このようなコンピュータによってアクセス可能なデバイスは、コンピュータメモリ（ＲＡＭ，ＲＯＭ）、フロッピディスク、ＣＤ−ＲＯＭをはじめ、ディジタルまたはアナログの通信リンクのような伝送系メディアを含む。
【０１０２】
上述した実施の形態は、本発明の技術的範囲から逸脱することなく多くの方法で変更可能であることは明らかであろう。よって、本発明の技術的範囲は請求の範囲およびその均等の範囲によって画定される。
【図面の簡単な説明】
【図１】  音響サンプルを認識する本発明の方法を示すフローチャートである。
【図２】  図１の方法を実現する分散型コンピュータシステムの一例を示すブロック図である。
【図３】  音響ファイルのデータベース・インデックスを構築する方法を示すフローチャートである。
【図４】  音響サンプルに対して計算されるランドマークおよびフィンガープリントを模式的に示す図である。
【図５】  ランドマークの選択を示す、音響サンプルのＬ４ノルムのグラフである。
【図６】  図１の方法で用いられる音響ファイルのデータベース・インデックスを構築する別の実施態様を示すフローチャートである。
【図７Ａ】、
【図７Ｂ】、
【図７Ｃ】  凸角点および連結した凸角点を示すスペクトログラムである。
【図８Ａ】、
【図８Ｂ】、
【図８Ｃ】  図３の方法におけるインデックス・セット、インデックス・リスト、マスター・インデックス・リストを示す図である。
【図９Ａ】、
【図９Ｂ】、
【図９Ｃ】  図１の方法におけるインデックス・リスト、候補リスト、散布リストを示す図である。
【図１０Ａ】、
【図１０Ｂ】  未知音響サンプルに対する識別の成功および識別の失敗をそれぞれ示す散布図である。
【図１】
0004945877.tif 000002
【図２】
0004945877.tif 000003
【図３】
0004945877.tif 000004
【図４】
0004945877.tif 000005
【図５】
0004945877.tif 000006
【図６】
0004945877.tif 000007
【図７Ａ】
0004945877.tif 000008
【図７Ｂ】
0004945877.tif 000009
【図７Ｃ】
0004945877.tif 000010
【図８Ａ】
0004945877.tif 000011
【図８Ｂ】
0004945877.tif 000012
【図８Ｃ】
0004945877.tif 000013
【図９Ａ】
0004945877.tif 000014
【図９Ｂ】
0004945877.tif 000015
【図９Ｃ】
0004945877.tif 000016
【図１０Ａ】
0004945877.tif 000017
【図１０Ｂ】
0004945877.tif 000018