放送音声またはビデオプログラム信号の自動検出及び識別のための方法及び装置
【課題】 放送プログラムを監視（モニタリング）する手法を高度なコンピュータシステムを用いて完全に自動化する。
【解決手段】 本発明は、例えばラジオ、テレビ、またはインターネット、またはテレビ信号などの放送プログラムにのせて放送される音楽または音声の自動検出及び識別に関する。「放送」とは、現在知られていようと将来考案されようと、例えば、ストリーミング、ダウンロードまたはストリーミングのピアツーピア配信またはネットワークトラヒックの検出を含めた任意の容易に入手可能なコンテント源を意味する。入力信号の検出及び識別は、入力信号から複数の数値コードを同じ様に抽出し、検出された数値コードの順序を記憶されている順序と比較することによって、同時に起きる。比較プロセスにおける他の最適化を用いて、比較プロセスが促進される。
【解決手段】 本発明は、例えばラジオ、テレビ、またはインターネット、またはテレビ信号などの放送プログラムにのせて放送される音楽または音声の自動検出及び識別に関する。「放送」とは、現在知られていようと将来考案されようと、例えば、ストリーミング、ダウンロードまたはストリーミングのピアツーピア配信またはネットワークトラヒックの検出を含めた任意の容易に入手可能なコンテント源を意味する。入力信号の検出及び識別は、入力信号から複数の数値コードを同じ様に抽出し、検出された数値コードの順序を記憶されている順序と比較することによって、同時に起きる。比較プロセスにおける他の最適化を用いて、比較プロセスが促進される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばアナログ、デジタルとして放送されるのであれインターネット上でデジタルとして放送されるのであれ、ラジオ、テレビ、またはインターネット、またはテレビ信号などの放送プログラム（番組）にのせて放送される音楽または音声の自動検出及び識別に関する。「放送」とは、現在知られていようと将来考案されようと、例えば、ストリーミング、ダウンロードまたはストリーミングのピアツーピア配信またはそのようなコンテント配信活動を含むネットワークトラヒックの検出を含めた任意の容易に入手可能なコンテント源を意味する。システムは、プログラムをデジタル方式でサンプリングし、デジタルサンプルストリームを短時間セグメントの大きな集合に分離することによって既知のプログラムを先ず登録する。これらのセグメントはその後、セグメントの特徴である特定の機能集合を抽出するために処理される。本発明は、既知のプログラムの特定のセグメントのための機能集合を表す数値コードを生成するために各機能集合を有している。プログラムを識別するこれらのコード及び登録データは、データベースをシステムの一部として取り込まれる。１若しくは複数のプログラムの登録が完了したら、システムは次に、入力信号から機能集合を抽出し、システムに入力される各タイムセグメントのための数値コードを作成し、その後、検出された数値コードの順番をデータベースに格納されている数値コードと比較することによって、放送信号において登録されたプログラムの存在を検出及び識別することができる。登録されたプログラムの誤検出率、見逃し率を低下させ、正しい検出を増やすために、比較プロセス中に種々のテスト基準が適用される。本発明には、比較的短い時間内に実行するようにするための比較プロセスの改善及び最適化も含まれる。
【背景技術】
【０００２】
本発明は、ラジオ、テレビ、またはインターネット上でデジタル化されて配信されるコンテントなどの広範に広められるプログラムの自動認識に関する。
【０００３】
放映権料などの放送に絡む権利使用料を正しく計算し、契約地域制限に従っていることを確認し、または所定の広告が予定通りに放送されているかを検証するために、広告主を含む放送プログラムの著作権者は、自分たちのプログラムがいつ、どこで放送されているかを測定する必要がある。ラジオまたはテレビを監視（モニタリング）する伝統的手法は、人間が聴取または視聴して見聞きしたものを記録するか、ラジオ局及びテレビ局の放送記録に頼るかである。これは、効率または精度が制約された多大な労力を要するプロセスである。高度なコンピュータシステムを用いてこのプロセスを完全に自動化することが本発明の目的である。このように、音声またはビデオコンテントがシステムに登録され、その後、音声検出の場合には、ラジオ、テレビまたは他の広く配信される音声コンテント源からのサウンドトラックがシステムに入力される。ビデオの場合には、その源が何であれビデオ信号がシステムに入力される。本発明を用いて、登録されたプログラムコンテントの検出及び識別が自動的に行われる。
【０００４】
先行技術：
【０００５】
放送プログラムの検出を自動化するために多くの方法が開発されてきた。これらの技法は、一般的に２つのカテゴリーのうちの１つ、即ちキュー検出またはパターン認識に分類される。キュー検出法は、特許文献１〜３によって例証されている。これらの技法は、配信の前にプログラムに挿入された埋め込みキュー（embedded cue）に頼っている。これらのアプローチは当該分野では支持されてはいない。音声プログラムにキュー信号を置くことは、このアプローチの採択を制限してきた。というのも、これはプログラム所有者及び／または放送局の協力を必要とするからであり、非実用的なものになっていた。
【０００６】
パターン認識法は、一般的にコンテント自体のスペクトル特性を利用して固有の識別コードまたはシグネチャを生成する。従って、識別コンテントの技法は、次の２つのステップからなる。第１は、データベースへの挿入のために既知のコンテントからシグネチャを抽出するステップ、第２は、検出されたコンテントからシグネチャを抽出し、検出されたコンテントを識別するためにデータベースにおけるシグネチャの一致を探索するステップである。このように、好適なアプローチは放送コンテント自体の特性を利用し、当該コンテントに特有のシグネチャを作成する。例えば、特許文献４には、既知のテレビプログラムを獲得し、当該フレーム内で音声信号及びビデオ信号の両方から各ビデオフレーム即ちシグネチャコードを作成するシステムが開示されている。最近になって、インターネット分散コンテントのための類似の検出システムが提唱されている（例えば特許文献５）。
【０００７】
音声単独の場合、特許文献６では音声信号のみが用いられる音声識別システムを開示しているが、入ってくる放送信号に対して制限されたタイムスライスによって表される音声プログラムを相関させるように試みているので、有用性が限定されている。特許文献６に開示されているマッチング法は、直接信号相関に依存しているので、高度に計算集約的である。更に、このアプローチは、特にプログラムが検出前に時間圧縮されるかまたは他の方法で変更されていれば、精度が制限されることがわかっており、好ましくない。これはまた、タイムスライスのサイズがその正しい識別を向上させるために大きくされるならば、誤検出識別を起こす傾向があり、計算的に不経済である。ラートら（Lert, et. al.）は、プログラムのセクションの開始を示すような人工コードまたはその他の人為的なものでない天然のマーカのいずれかがプログラムにおいて検出され、その後、機能シグネチャが所定の時間後に測定されるという第１のカテゴリーの符号化法と組み合わせることによって、相関方法の計算作業負荷を軽減する方法を特許文献７に開示している。この方法は、キューを作成するために音声に可聴コードが挿入されなければならないのでそれを劣化させるかまたはコンテント源の協同を必要とするか、高度に当てにならない新たな音声プログラムの開始を示す天然のマーカに頼るかいずれかの場合に、音声のみの用途における有用性を限定している。特許文献８において、ラートらは更に、シグネチャを測定及び計算する前に信号において「安定条件」が生じるまで待つという本発明の改善について述べているが、この方法の信頼性はサンプルタイムスライスのサイズによって制限される。特許文献９では、信号の部分を無作為に選択し、本発明のシグネチャ生成プロセスへの入力としてサンプリングすることによってデータ処理負荷の問題に取り組んでいる。
【０００８】
特許文献１０及び１１は固有のシグネチャを計算するより複雑な方法を開示しているが、ここでは、所与のビデオフレームと以前のビデオフレームにおいてなされた同じ測定間の所定の数の周波数帯域のそれぞれにおいてエネルギーの変化を比較することによって所与のビデオフレームに対応する音声シグネチャが導かれる。しかし、マッチング技法は、音声及びビデオシグネチャの組合せ、または天然のマーカ（この場合にはプログラムの開始または終了）の使用に依存している。従って、この方法は、音声のみのプログラムに関するラートの問題と同じ問題を抱えている。
【０００９】
それに加えて、特許文献１２では、各音声プログラムに対して１つのシグネチャ値を作成するための音声プログラム内の可聴機能、特に、振幅、音の高さ（即ち基音）、帯域幅、低音（即ちリズム解析）、明るさ（即ちプログラムの周波数応答の形状）、メル周波数ケプストラム係数のグループの使用を開示している。音声における長期にわたるこれらの詳細な機能の集合は、非常に多様性がある結果をもたらし、実世界の放送局において十分なロバスト性を有していない。特許文献１３及び１４は、シグネチャを作成するために音声信号においてエンベロープ（例えば音の大きさ）機能を用いるデジタル回路を開示している。このアプローチは、時間軸圧縮技法の適用によって時間圧縮問題に取り組むべく立案されている。音の大きさ（ラウドネス）への依存は、同様に実世界環境における使用を難しくする他のロバスト性問題を有する。特許文献１５は、音楽の開始点から、所定の位置から数えられる所定の数のデジタルサンプルを用いて音声シグネチャが作成されるシステムを開示している。このアプローチは、放送、または音声がアナログ形式で検出される場合には、またはプログラムの再生が速度を変化させたか、原トラックからの周波数等化が適用されているかまたは音声がプログラムセグメントにダビングされた場合には、より一層信頼できない。
【特許文献１】米国特許第４，２２５，９６７号明細書
【特許文献２】米国特許第３，８４５，３９１号明細書
【特許文献３】米国特許第４，５４７，８０４号明細書
【特許文献４】米国特許第４，７３９，３９８号明細書
【特許文献５】国際公開公報第ＷＯ０１／６２００４ Ａ２号明細書
【特許文献６】米国特許第３，９１９，４７１号明細書
【特許文献７】米国特許第４，２３０，９９０号明細書
【特許文献８】米国特許第４，６７７，４６６号明細書
【特許文献９】米国特許第４，７３９，３９８号明細書
【特許文献１０】米国特許第５，４３６，６５３号明細書
【特許文献１１】米国特許第５，６１２，７２９号明細書
【特許文献１２】米国特許第５，９１８，２２３号明細書
【特許文献１３】米国特許第５，２１０，８２０号明細書
【特許文献１４】米国特許第４，８４３，５６２号明細書
【特許文献１５】米国特許公開公報第２００３００８６３４１号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、直列のビデオ信号（音声の場合）または信号においてプログラムにおける既知の時間を示す標準的マーカに頼ることなく、非現実的な計算能力を要求しない音声プログラムの特徴を表すコードを計算する固有かつ新規な方法により既知の音声またはビデオプログラムの識別を行うことができるシステム及び方法について説明する。このシステム及び方法の利点は、精度、速度、再生速度変化に対するロバスト性、何らかの埋め込みキューまたはウォーターマーク（透かし）に頼ることなくリアルタイムで識別プロセスを実行する能力である。それに加えて、本発明は、高速データベース探索方法論を具現化するために低コストで高性能なコンピューティングプラットフォームのアベイラビリティをうまく利用する。
【課題を解決するための手段】
【００１１】
Ａ．概要
【００１２】
本発明を具体化する放送監視／検出システムは、２つの段階即ち登録及び検出において作業する。登録段階中に、プログラムをデジタルデータとしてシステムに送信することによって既知のプログラムコンテントがシステムに登録される。一連のシグネチャは、この場合ではパターンベクトルであり、当該分野でより一般的には「フィンガープリント」または「シグネチャ」であるが、これは、集団的にこれらと相互参照されるプログラムコンテントの識別データと共に、一連のデータ記録としてデータベースに格納される。第２段階中に、未確認のプログラムがシステムに入力される。そのようなプログラムには、地上放送、衛星、インターネット、ケーブルテレビまたはその他の配信媒体であろうとなかろうと、現在知られていようとも将来的に考案されようとも、ラジオ、テレビ、インターネット放送またはその他の音声またはビデオプログラム源を含めることができる。そのようなプログラムが監視されている間、プログラム（またはその他のシグネチャ生成技法）のパターンベクトルが継続的に計算される。次に、計算されたパターンベクトルを用いてデータベースにおける一致を探索する。ある一致が見つかって確認されると、システムは、データベース中の相互参照される識別データを用いて、現在再生されているコンテントの識別データを供給する。好適実施形態においては、システムはコンピュータ上で走行するソフトウエアであるが、システムの性能及び能力を増大するために専用ハードウエア構成要素が各モジュールの一部または全部を置き換えることがあることが想定される。
【発明を実施するための最良の形態】
【００１３】
好適実施形態においては、中央処理装置を含むコンピュータがサウンドカードまたはインタフェース機器に接続され、そこに音声プログラムが与えられる。登録段階中に、ＣＰＵはサウンドカードから音声またはビデオデータをフェッチし、パターンベクトルデータを計算し、その後、プログラムの識別情報及びタイミングデータと共にこれらの結果は以下に更に述べるようにデータベースに格納される。或いは、データは、オリジナルの情報源（authentic material）、例えばコンパクトディスク、ｍｐ３ファイル、または信号を含むその他のデジタルデータ源などから直接ロードされることがある。非音声用途の場合には、素材供給源は、ＤＶＤディスク、映画スタジオから提供されるマスタ、テープまたは、プログラムが固定または格納されるその他の表現媒体であることができる。もちろん、素材によっては容易に利用可能な供給源を有しないことがあるが、そのような場合には音声または他のプログラム信号が以下の方法で用いられる。システムは、未知のプログラムを定期的に検出するが、毎回実質的に同じシグネチャの集合を含んでいれば、プログラム素材に対して任意の識別子を割り当て、登録段階中にプログラムが導入されたかのようにデータをデータベースに入れる。プログラムの同一性が将来的に決定されてしまえば、データベースは、認証情報と同様に適切な情報を含む一方で、同時に、プログラムの同一性が未だ分かっていないときに検出された使用データをプログラムの所有者に供給するように更新されることができる。データベースは、典型的な例では、任意の種類のコンピュータバスまたはデータ伝送インタフェース（ＳＣＳＩを含む）を用いてコンピュータの中央処理装置に接続されたハードディスクドライブに格納されるデータファイルである。
【００１４】
検出段階中に、ＣＰＵは、サウンドカードまたはビデオカードからプログラムデータをフェッチするか、またはコンピュータハードディスクドライブまたは外部メディアリーダに格納され得るデータファイルからプログラムデータをロードする。ＣＰＵは、パターンベクトルデータを計算し、その後、ハードディスクドライブに格納されたデータベースにタイミングデータとともにデータベース問い合わせを送信する。データベースは、コンピュータにおけるものと同じハードディスクドライブであるかまたはデジタルコンピュータネットワーク上でアクセスされる外部ハードディスクドライブであることがある。一致するデータが見つかると、ＣＰＵは、以下に詳述するようにプログラムの識別を確認するためにデータを処理し続ける。ＣＰＵはその後、識別結果を遠隔位置へ配信してグラフィカルユーザインタフェースを用いて画面上に表示されるかまたはハードディスクドライブに格納された別のデータファイルに記録される当該分野でよく知られている多種多様のコンピュータネットワーク化システムのいずれかで通信することができる。方法を実行するプログラムは、任意の種類のコンピュータ読取り可能媒体、例えば、ハードディスクドライブ、ＣＤ‐ＲＯＭ、ＥＥＰＲＯＭまたはフロッピー（登録商標）に格納され、実行時にコンピュータメモリにロードされることがある。ビデオの場合には、信号はアナログ−デジタルビデオ変換カードを用いて得ることができるか、またはデジタルビデオデータは例えばインターネットまたはデジタルテレビ放送などのデジタルビデオ源から直接検出されることができる。
【００１５】
上記システムは４つの構成要素から構成される。４つのモジュールの相互接続を図１に示す。４つのモジュールとは即ち、（１）初期段階の信号処理段階、（２）中間のパターン生成モジュール、（３）それに続くデータベース検索エンジンモジュール、（４）最後のプログラム認識モジュールである。登録段階中に、既知の音声またはビデオコンテントのためのシグネチャを作成するパターン生成モジュールの結果はデータベースに格納され、探索／パターン認識モジュールは用いられない。
【００１６】
各モジュールの機能について以下に更に詳述する。
【００１７】
１．収音（Sound Acquisition：ＳＡ）モジュール
【００１８】
ＳＡモジュール（１）は、音検出回路からアナログ音声データを受信し、それを残りのモジュールに利用可能にする。当業者は、音声またはビデオ信号を受信し、これらの信号をデジタルデータに変換する様々な製品があることを理解されよう。これらの装置は、任意のデジタル音声データ源である可能性があり、アナログ音声データをコンピュータのＣＰＵによるアクセスが可能なデジタル音声データに変換するパーソナルコンピュータにおけるインタフェースカード、デジタル音声データを標準形式で出力する独立型（スタンドアロン）装置、または音声出力を有するデジタルラジオ受信機が含まれる。或いは、デジタル形式の予め検出された信号が、典型的なデータネットワークを介してシステムに接続された記憶装置からアクセスされることができる。ＳＡモジュールは、定期的に、デジタルインタフェース機器またはデータ記憶装置からデータを読み取り、パターン生成モジュールによってアクセスされることになるデータバッファまたはメモリへデータを記憶する。典型的なデジタル音声システムが、サンプリングレートと呼ばれる規則的な間隔でデジタルワードを供給することになることを当業者は理解されよう。音声信号を表す一連のデジタルワードは、デジタル音声サンプルである。本発明は、これらのサンプルを、所定の数のサンプルからなる一連のタイムフレームに編成する。タイムフレームは、順序よく記憶される。或いは、コンピュータメモリ（オペレーティングシステムがページング及びスワッピングをサポートするのであればハードディスクドライブを含む）に格納されるデータ構造は、タイムフレームが物理的に順序よく記憶されないときに用いられることがあるが、論理的にはこれらがメモリアドレッシングによって検出された順番にインデックス付与または参照されることがある。
【００１９】
好適実施形態においては、音声信号は、低域フィルタリングを含めた当該分野で既知の方法で調整される。好適実施形態において、信号はＳＡモジュール内で８０００Ｈｚの速度でサンプリングされる。好適実施形態においては、１６，３８４個のサンプルが１フレームを構成する。この速度では、信号はサンプリングされる前にエイリアス除去のために低域フィルタリングされなければならない。しかしながら、後述するように、より高いサンプリングレートが、下流の計算における適切な調整を行って用いられることもある。
【００２０】
ビデオプログラムの場合には、収音モジュールは、本質的に同様にして類似のやり方で作動する。即ち、ビデオ信号はデジタルビデオ信号として得られ、公知の方法を用いてビデオフレーム上でフレーム方式により周波数領域に変換される。本発明については、好適実施形態に関する記述を通して音声への適用として詳細に説明する。しかし、記載のシステム及びプロセスは、音声のみならず、シグネチャまたはパターンベクトルが定期的にビデオ信号から導かれているビデオにも適用可能である。チャールズ・ポイントン氏の文献（"A Technical Introduction to Digital Video", Charles A. Poynton, John Wiley & Sons, New York, (c)1996）を参照されたい。
【００２１】
２．パターンベクトル生成（Pattern Vector Generation：ＰＧ）モジュール
【００２２】
検出段階中に作動するＰＧモジュール（２）は、ＳＡモジュールによって検出及び記憶された記憶デジタル音声またはビデオサンプルをフェッチする。サンプルのフレームが受け取られると、ＰＧモジュールはフレームのパターンベクトルを計算し、検出段階にいるときにはパターンベクトルをデータベース探索モジュールにデータベース質問の形で送信することになる。登録段階の間、ＰＧモジュールは、パターンベクトルが既知の音声またはビデオプログラムに関する他の適切な情報との相関関係においてデータベースに格納されるようにするために、パターンベクトルを計算する。パターンベクトルの計算については、以下に詳述する。
【００２３】
フレーム間距離
【００２４】
各増分音声サンプルに対して、新たなフレームを開始することができる。即ち、各音声サンプルは、Ｎが或るフレームにおけるサンプルの数であるとき、Ｎ個の重複フレームの構成要素であることがある。これらの重複フレーム間の距離は、フレーム間距離である。パターン生成のためのフレーム間距離を短くすれば、プログラム開始時の不確実性の問題が軽減される。開始時間がわかっていないとき、フレーム間距離がより短ければより良好な結果が得られる。好適実施形態においては、音声プログラム登録段階中に、フレームの約１／４である４，０００の値が用いられる。精度を向上させるかまたは計算時間及び記憶オーバヘッドを減少させるかいずれかのために他の距離が用いられることもある。従って、好適実施形態においては、既知の音声プログラムのデータベースにおける第１のフレームは音声サンプル１ないし１６，３８４に対応し、第２はサンプル４００１ないし２０，３８４に対応し、以下同様である。検出段階中に、フレーム間距離は１フレーム長さに等しい値に設定される。従って、検出された音声プログラムの第１のフレームにはサンプル１ないし１６，３８４が含まれ、第２のフレームにはサンプル１６，３８５ないし３２，７６８が含まれ、以下同様である。
【００２５】
８０００Ｈｚのサンプリングレート、１６３８４サンプルのフレームサイズ、４０００のフレーム間距離の好適実施形態の設定を用いるとしても、異なるサンプリングレートが用いられることがあり、その場合、結果に差がある。例えば、サンプリングレートが１６０００Ｈｚ（好適な設定の２倍）のとき、フレーム番号サイズは３２７６８（サイズは２倍であるが持続時間は同じ）、フレーム間距離は８０００（０．５秒でのフレーム間距離と同じ）となり、好適な設定を用いたときとほぼ同じパターンベクトルが生成される。更に変わった点は、パターンベクトルを計算するために用いられる各サブバンドにどのフーリエ変換（ＦＦＴ）係数が含まれることになるかを決定することだけである。例えば、好適な設定（後述の速度補償方式は無視する）に対して、帯域１には６６番目ないし９２番目のＦＦＴ係数が含まれる。そのとき、上記した別の例に対して、ＦＦＴ係数は３２番目ないし９４番目であることになる。８０００Ｈｚのサンプリングレートを仮定して与えられるパターンベクトルの計算は、それに応じて調整される。
【００２６】
ビデオの場合には、パターンベクトルはビデオの各フレームの２次元ＦＦＴ変換から導かれる。ビデオフレームは音声におけるサンプルと類似していると考えられることができる。従って、ビデオフレーム全域で垂直及び水平ＦＦＴ係数を収集して各タイムフレームに対してパターンベクトルを作ることができ、タイムフレームは１群のビデオフレームを構成する。テレビプログラムのオーディオサウンドトラックの機能が同じプログラムのビデオ信号の機能と組み合わされてパターンベクトルを生成することができるのであるから、これらのアプローチは組み合わされることがあることを当業者は理解されよう。
【００２７】
３．データベース探索（Database Search：ＤＢＳ）モジュール
【００２８】
ＰＧモジュールによって生成される問い合わせを受け取ったら、このモジュール（３）は、既知のプログラムのパターンベクトルの順番を含むデータベースを探索することになる。一致が見つかったら、モジュールは、音声またはビデオプログラムの集合の識別情報に対応する登録番号の集合であって、そうでなければプログラムＩＤ、フレームＩＤ（フレーム番号とも呼ばれる）と呼ばれる集合及び一致が生じたこれらのプログラム内のタイムフレーム番号を戻す。データベースの探索が一致を見つけることができなかったら、ＤＢＳモジュールはＮＯ‐ＭＡＴＣＨＥＤフラグを発行することになる。ＤＢＳモジュールのための本発明の態様は、信号シグネチャ（パターンベクトル生成モジュールにおいて用いられる技法と異なる技法を用いて導かれるシグネチャさえも）を含む任意の種類のデータ集合に適用可能であると考えられる。
【００２９】
４．プログラム検出／識別（Program Detection and Identification：ＳＤＩ）モジュール
【００３０】
このモジュール（４）は、以下に更に述べるように、直近の連続するＮ個のタイムフレームについてＤＢＳからの一致する（マッチング）結果を常に監視する。好適実施形態において、Ｎは５に設定されるが、それより大きいかまたは小さい数が用いられることがあり、その場合、結果に差がある。任意の音声またはビデオプログラムが積極的に検出されたかどうかを決定するために２つの方式が用いられる。１つ目は、Ｎ間の一致するパターンベクトルの各スレッド内で、有効な順番を有するフレームの数がフレームのブロックの指定された過半数に合格するかどうかを決定する過半数票（多数決）方式である。２つ目は、潜在的なスレッドの各々を追って、当該スレッド内のいくつのフレームが有効な順番を構成するかを数えるフレーム順序付け（sequencing）方式である。大部分の隣接フレームがフレーム順序付け要件を満足するスレッドが存在するならば、当該スレッドにおいてプログラム（音声であろうとビデオであろうと）が検出されると考えられる。誤検出を抑制し、正確な検出を増やすためにいずれか一方または両方の方式が用いられる。好適実施形態においては、両方の方式が用いられる。ある１つの（または２以上の）プログラムが検出されると仮定すると、ＳＤＩモジュールは次の２つのモードを開始することになる。
１．識別モード：このモードでは、モジュールは、プログラムが検出された時間、検出がなされたプログラムに組み入れられた時間と共に、曲名、作詞家／作曲家、アーチスト、レコード会社、出版社、またはシステムの登録段階中に入力されるその他の情報を含む被検出プログラムの参照情報全てを記録する。この情報は、検出ログに登録されることになる。
２．トラッキングモード：このモードでは、モジュールは、後述するように、放送の新たなフレーム毎の問い合わせした結果が順序付け要件に従っているかどうかを監視することによって各被検出プログラムを追跡する。問い合わせした結果が順序付け要件と一致することができなくなるまでアルゴリズムはこのモードにロックされる。トラッキングモードから出た直後に、トラッキングの全期間を含む多くの検出属性及びトラッキングスコアが記録されることになる。
【００３１】
ＰＧモジュールによって生成されるパターンベクトルは、一致のためのデータベースの探索を行うためにＤＢＳモジュールに送られる。出力は、ＮＯ‐ＭＡＴＣＨＥＤフラグまたはライブラリパターンのプログラムＩＤ及びフレームＩＤのいずれかであるが、前者はＤＢＳが探索基準に合格するデータベース内のフレームを配置できないことを示し、後者は探索基準に合格する。
【００３２】
ＳＤＩモジュールは、ＤＢＳモジュールからの出力を収集し、新たな音声プログラムが存在するかどうかを検出する。もし存在するならば、検出された歌が識別される。図１は、音声の１フレームから検出後のその結果までのアルゴリズムのフローの図解である。ビデオへの本発明の適用に関しては、パターンベクトルが生成されてしまえば演算は似ている。ＳＤＩモジュールのための本発明の態様は、信号シグネチャ（パターンベクトル生成モジュールにおいて用いられる技法と異なる技法を用いて導かれるシグネチャさえも）を含む任意の種類のデータ集合に適用可能であると考えられる。
【００３３】
パターンベクトル生成
【００３４】
ＰＧモジュールは、好適には毎秒８，０００サンプルに設定されたサンプリングレートで、好適には１６，３８４個のサンプルから構成されるような、信号のフレームを読み込む。従って、フレーム長さは時間にして約２秒である。時間にしてそれ以上またはそれ以下のサンプルまたはフレーム幅が用いられることがあり、その場合、結果に差がある。
であり、ベクトルが信号のフレームを含み、各ｘｉがｎ番目の音声サンプルの値であるとすれば、Ｎ要素パターンベクトルは以下のステップで計算される。好適実施形態においては、Ｎは３１に等しい。Ｎの値は任意であり、増加または減少させることができ、その場合、結果に差があることを当業者は理解されよう。例えば、Ｎを小さくすると、計算時間及びメモリ所要量を減少させるが、精度を低下させることがある。Ｎを大きくすると、その逆になる。また、示されている方法では、本発明の説明を単純化するために３１要素パターンベクトルが計算に用いられていると仮定することになる。目標が正確度を上げることであるかまたはコンピュータの複雑さを低減することであるかによって、Ｎが増加または減少するとき、同じ方法論が使えることになることを当業者は理解されよう。
【００３５】
１．スペクトルベクトル
を得るために、フレーム中のサンプルの数に等しい点の数でｘのフーリエ変換を計算する。この変換のスペクトル分解能は、［８０００サンプル／秒］／［１６，３８４サンプル／秒］＝０．４８８Ｈｚである。
【００３６】
ＦＦＴスペクトル値を特定の幅の周波数帯域に分離する。好適実施形態において幅は６４Ｈｚである。本発明について説明を単純化するために好適実施形態の点から更に説明するが、特許請求の範囲に限定されるものではない。
【００３７】
帯域＃１は０から６４Ｈｚまでであり、帯域＃１にはＦＦＴ係数Ｘ１からＸ１３１までが含まれる。
【００３８】
帯域＃２は６４から１２８Ｈｚまでであり、帯域＃２にはＸ１３２からＸ２６２までが含まれる。以下同様である。
【００３９】
２．各帯域の重心（または質量中心ＣＯＧ）を次式により計算する。
【数１】
好適実施形態においては、帯域２から３２のみが用いられる。というのも、帯域１は、ＦＭラジオ放送では通常用いられない０Ｈｚを含む最も低い帯域であり、帯域３２は、典型的な例では音声のフィンガープリントを符号化するのに十分な帯域幅である１，８００Ｈｚまでの帯域をカバーするからである。当然のことながら、必要に応じてより高いまたは低い帯域が用いられる可能性がある。信号特性を把握するためのより高いまたは低い帯域の包含は、経験的に決定されることができる。第１のステップでは、ステップ２で重心を計算するためにＦＦＴ係数がされる収集されるが、第１のステップはビデオの場合において異なる。ビデオの場合には、ＦＦＴ係数は、ポイントン氏の文献の２３ページに記載されているように、複素平面中かまたは２次元空間の周波数平面上かいずれかの位置から選択されなければならない。ポイントン氏の文献は引用を以って本明細書の一部となす。これらの位置は、音声の場合の周波数帯域と類似している。音声において所定の周波数帯域を用いるのに似たやり方で、周波数領域における垂直／水平面上の所定の領域を画定することができ、各領域におけるＦＦＴ係数値を用いてその領域に対応する要素を計算することができる。この選択がなされると、同等の方法で重心を計算することができる。フレームレート、同期速度（sync rate）、副搬送波またはラインレートを含む周波数領域を無視することは有利である。最終的な結果は、音声の場合に本質的に等しい。即ち、ビデオの各タイムフレームが、データベースに格納される自身に関連するパターンベクトルを有することになる。
【００４０】
ステップ３の後で、３１要素ベクトル
が得られる。好適実施形態においては、更なるステップがｃを符号なし整数に変換する。符号なし形式が用いられるのは、ｃ中の全ての要素が（１，１３１）の間隔に肯定的であるためである。ｃの更なる計算は、１３１で割る除算を実行することによって各要素を正規化して０と１の間の値になるようにし、各帯域内のＦＦＴ成分の数は、
【数２】
である。好適実施形態において、各要素は、その後、記憶に便利なように、そして更なる処理のために、符号なし１６ビット整数形式に変換される。計算時間の下流（ダウンストリーム）を低減するために、各ＦＦＴ係数即ちｃｉが最小閾値に関連してテストされる。下流プロセスは、例えば、更なる計算のために収集された下流集合にこれらの要素を含まないことによって、これらの要素を無視するように設定される。図３にこのモジュールのフローチャートを示す。好適実施形態においては、ステップ１におけるＦＦＴ及びステップ３における重心（ＣＯＧ）計算の両方が倍精度浮動小数点命令を用いて一般的には計算される。
【００４１】
速度補償方式
【００４２】
種々の理由で放送プログラムは原型のプログラムの速度から多くの場合加速されることを当業者は理解されよう。したがって、検出される音声プログラムが登録段階中に供給される音声の速度と異なることがあるときに、自動音声プログラム検出システムがロバスト（robust）であることはクリティカルである。この問題を多少とも解決するために、パターンベクトル生成式の修正が用いられる。
【００４３】
（ａ）修正は、ステップ２の各帯域の異なる数のＦＦＴ成分（即ち帯域幅）を有するようにすることである。
【００４４】
（ｂ）好適実施形態において、パターンベクトル生成式の修正は、検出段階中に入ってくる放送音声信号にのみ適用され、音声プログラムの登録段階中に適用されるパターン生成プロセスには適用されない。上記したような検出段階に対して代わりの周波数帯域を使用することは、登録段階の間に交互に行われることができ、実質的に同じ結果が得られることを当業者は理解されよう。
【００４５】
この修正の具体的詳細を以下に述べる。
【００４６】
この式は、フーリエ変換のスケーリング特性に基づく。歌を時間加速したものは、原型を時間変換したものである。
このとき、α＞１であり、ここで、ａは加速率であり、ｘ（ｔ）は時間ｔでの検出されたサンプルである。ａ＞１の場合、時間軸は「圧縮」されることに留意されたい。歌が２％加速されたら、α＝１．０２となる。
【００４７】
スケーリング特性により、係数を用いてフーリエ変換の値を調整することができる。
従って、高速再生のスペクトル、即ち歌の加速バージョンが引き伸ばされる。２％の加速率では、歌の加速なしの１００Ｈｚでのフーリエ変換周波数成分は、加速後に１０２Ｈｚにシフトされる。このことが示唆することは、検出された歌に２％の加速率が存在すれば、ステップ２における帯域幅はそれに応じて１．０２×６４Ｈｚ＝６５．２８Ｈｚに調整されるべきであり、それゆえ各帯域内のＦＦＴ成分の数は１３１×１．０２の丸め（１３４に等しい）に調整されるべきであるということである。各帯域におけるＦＦＴ成分の量を計算する式は２つあり、両者ともＦＦＴ成分の元の数に基づくものであり、それは１３１に等しい。
【００４８】
式
【００４９】
（１）加速率ｒと仮定する。帯域＃１から開始する。帯域＃１はＦＦＴ係数ｘ１からｘｚ（１）を含み、ここでｚ（１）＝１３１×（１+ｒ）の丸めである。
【００５０】
（２）ｋ＝２から３２に対して各ｚ（ｋ）＝［ｚ（ｋ‐１）＋１３１×（１+ｒ）］の丸めを繰り返し計算する。帯域＃ｍは、ｘｚ（ｍ‐１）からｘｚ（ｍ）のＦＦＴ係数からなる。
【００５１】
（３）上記で計算した新たな帯域区画により、帯域＃２から＃３２まで重心（ＣＯＧ）を計算する。各重心（ＣＯＧ）を対応する帯域におけるＦＦＴ成分の数で割ることによって正規化を実行する。
【００５２】
補償あり及びなしの相違を図４及び図５に示す。図４は、原型の帯域設定が、原型とその加速変型間のパターンミスマッチをもたらすことを示す。図５は、加速率が既知であれば修正帯域設定が非常に良好なパターンマッチング挙動を与えることを示す。
【００５３】
ロバストベクトル生成式
【００５４】
上記したパターンベクトル生成式は、ロバストマッチングを与えるために更に改良されることができる。この改良は、前の公式化の代わりに用いられることもある。加速の別の効果は、周波数軸を伸縮させるほかに、帯域毎の周波数における限界のシフトである。改良は、帯域の幅を拡張することにより、再生速度に起因するシフトの量が帯域幅と比べて僅かな割合に納まるように帯域の限界のシフトを補償することである。従って、帯域位置が変えられない限りアルゴリズムの修正‐即ち、パターンベクトルとして重心を計算すること‐がない。修正帯域限界は、記憶パターンベクトルを作成するために登録プロセス中に用いられる。同じ性質を示す周波数帯域幅を計算するために、即ち再生速度変化による周波数シフトが比較的小さくなるように帯域幅を拡張し、そこでは再生速度変化による周波数シフトのパーセンテージが各周波数帯域幅のほんの僅かであるようにするために、幾つかの別法が用いられることがあることを当業者は理解されよう。更に、この技法が、周波数帯域へのＦＦＴ係数の分離に基づく信号においてシグネチャを計算する任意の方法の役に立つことになることが考えられる。この効果を示す修正帯域限界を計算する１つの方法を好適実施形態として後述する。
【００５５】
新たな帯域限界位置を計算するためのアルゴリズム
【００５６】
周波数領域における帯域番号ｋの開始及び終了インデックスをそれぞれ、ＦＦＴ係数のインデックスであるｓｋ，１、ｓｋ，２とする。例えば、インデックスｓｌ，１は１に等しく、０Ｈｚに対する第１のＦＦＴ係数に対応する。シフトが超過すべきでない帯域幅のパーセンテージで割ったパーセントで表される予想最大加速であるようなシフト対帯域幅比を仮定する。好適実施形態においてはこの値は５％であると仮定されるが、精度を上げるかまたは計算の複雑さを減らすために他の値が用いられることもある。
【００５７】
１．開始位置がｓ１，１＝１である帯域ｋ＝１から開始する。２％の加速を仮定すれば、位置は０．０２ないし１．０２だけシフトされるが、これは丸め後でも１に等しい。結果インデックスは整数でなければならないので、丸めが必要である。シフト対帯域幅比が帯域＃１の帯域幅の０．４（シフトが表すべき量、５％帯域幅で割った２％シフトである）に等しいと仮定すれば、終了位置ｓ１，２＝（１＋．０２／．０５）×ｓ１，１＝１．４、または丸め後には１である。
【００５８】
２．ここで、帯域＃２に対する１つの位置の計算に進む。開始位置ｓ２，１＝２である。２％のシフト及び５％のシフト対帯域幅比を仮定すると、ｓ２，２＝３が求められる。
【００５９】
３．全てのＦＦＴ成分が使い尽くされるまで繰り返しを続ける。好適実施形態においては、結果（３１．２５Ｈｚに対応する、より下位の帯域ｓｋ，１＜６４と、２，６８６Ｈｚに対応する、より上位の帯域ｓｋ，１＞５５００の両方）は、用いられない。
【００６０】
４．ｋが９に等しいとき、ｓ９，２＝６６であり、ｋ＝１０のとき、ｓ１０，１＝６７であり、以下同様である。各帯域のｋに沿った帯域幅がｋとともに指数関数的に増加するのでオーバフローを回避するため、好適実施形態は、ｋがｋ＝２２まで繰り返すとｓ２２，２＝５２９８になるようにｓ１０，１＝６６を任意に設定した。結果を表にまとめたものを表１に示す。
【００６１】
５．現時点での項目の数は１３でしかないが、各項目がパターンベクトルにおける特定の要素に対応する３１個の項目の合計が好ましい。帯域の第２のバッチは、ステップ３で得られた帯域それぞれの中間を取ることによって得られる。表２に示されるように追加の１２帯域が得られる。
【００６２】
６．現時点では２５の帯域がある。残りの６帯域は、２つの表を組み合わせることによって得られる。具体的には、両表において項目１と２が組み合わせられ、項目３と４が組み合わせられ、項目５と６が組み合わせられ、表３に示されるようにもう６つの項目が作成される。上記を組み合わせて、３１帯域の開始及び終了位置を表４に示す。
【００６３】
±２％の速度変化に対するロバスト性を示すために、信号のフレームに対するテスト結果を図６に示す。
【００６４】
加速補償（speedup compensation）とロバストな式の組合せ
【００６５】
周波数帯域限界を調整するための上記した２つの方法は、加速補償も組み入れられるのであれば、組み合わせられることができる。周波数スペクトルの拡張と加速の関係は、２つのアプローチを組み合わせるために利用される。ｋ番目のサブバンド、即ち開始及び終了位置＝［ｓｋ，１，ｓｋ，２］は、±２％の速度変化に対するロバスト性を有する。その後、各値に（１＋ｒ）を乗じる。ここで、ｒは［ｓｋ，１，ｓｋ，２］への加速量である。その後、上記した丸め法を行う。これにより新たなインデックス
が得られる。速度変化に対するこのインデックスのロバスト性は、ｒ±２％にシフトされる。本質的には、新たな表は先の表４であり、ここでは値に（１＋２％）を乗じてその後同じ丸め法を適用する。表４は、ここで、データベースライブラリを投入する既知の音声プログラムからパターンベクトルを作成するために登録段階中に用いられる。検出段階中に表５を用いて、以下に更に詳述するようにデータベースにおいて一致するデータ記録を見つけるためにＤＢＳモジュールにおいて用いられる検出された入ってくる放送からパターンベクトルを作成する。従って、両方法が組み合わされる。一例として、ｒ＝０．０２（２％）に設定し、表４のあらゆる帯域を処理し、表５に示されるように０〜４％の速度変化にロバストである新たなサブバンドの集合を計算する。
【００６６】
表５は、２％の加速補償で得られる。表４の表になっているものに２％加速補償後の新たな３１対の開始及び終了位置が加えられた。この結果は、放送からの検出された歌の処理によるものである。
【００６７】
補償は、方法を０から４％の加速バリエーションのロバスト性を有するように効果的に位置付ける。変化が０より上または下である、即ち再生を減速または加速するときに速度変化の効果を和らげるために同じアプローチを用いることができることを当業者は理解されよう。
【００６８】
データベース探索（ＤＢＳ）モジュール
【００６９】
データベース探索モジュールは、ＰＧモジュールから各フレームのパターンベクトルを獲得し、そのパターンベクトルを同じパターンベクトルを有するデータベース記録に一致させるためにデータベース質問を集める。データベース問い合わせとデータベースに格納されたパターンベクトル間の一致を決定するためにソフトマッチング（soft matching）方式が用いられる。対照的に、ハードマッチング（hard matching）方式は各問い合わせに対して多くても１つの一致項目を許容する。ソフトマッチング方式は、１つの問い合わせ当たり２つ以上の一致項目を許容し、一致があるところは、誤差閾値を満たすという意味ではパターンベクトルが問い合わせベクトルに十分近いところである。一致項目の数は、（ｉ）いくつかの最大量に制限されることができるかまたは（ｉｉ）問い合わせとデータベース項目間の最大許容誤差によって制限されることができるかいずれかである。いずれのアプローチが用いられてもよい。ソフトマッチング方式は、登録段階においてプログラムパターンがオーバサンプリングされているという事実に依存している。例えば、好適実施形態において、登録のために用いられるフレーム間距離は検出において用いられるものの１／４に過ぎない。従って、特定のプログラムのｍ番目のフレームが問い合わせへの良好な一致フレームであれば、（ｍ‐１）番目のフレーム及び（ｍ＋１）番目のフレームなどその隣接フレームも良好な一致になるであろうことが期待される。ソフトマッチング方式及び順番付け方式の協力は、放送環境に固有の可変信号条件に対する検出システムのロバスト性を強化する。
【００７０】
一致が見つかったら、データ記録における対応するプログラムＩＤ番号及びフレーム番号が戻される。図７のフローチャートは、ＤＢＳモジュールにおけるフローを示している。非常に大きなデータベースにおいて所与の公差内で一致する変数の位置を見つけるための変数の全域での探索は、ばか力式で行われるのであれば、潜在的に時間が掛かることを当業者は理解されよう。計算時間問題に取り組むために、２部（two part）探索を用いる。第１部においては、範囲探索方式が問い合わせのすぐ近傍の内でそれらの項目を選択する。第２部においては、第１部からの潜在的な候補に対する改良された探索を用いて問い合わせに最も近い候補の集合を選択する。
【００７１】
ステップについて以下に詳細に述べる。
【００７２】
１．検出段階中にＰＧモジュールによって生成されるパターンベクトルからの問い合わせを集める。
【００７３】
２．最近隣探索アルゴリズムを実行する。このアルゴリズムは２つの部からなる。第１部は、近似的な探索方法論を実行する。具体的には、範囲探索（range search：ＲＳ）方式は、データベースにおけるどの項目が問い合わせのすぐ近くにあるかを決定するために利用される。第２部は、細かな探索方法論を実行する。第１部からの結果を問い合わせへのそれらの距離に従ってソートする。探索アルゴリズムは、（ｉ）最良のＭ結果（問い合わせへの最短距離を有する点で）を戻すことができるか、または（ｉｉ）いくつかの特定の閾値以下の距離を有する全ての結果を戻すことができるかのいずれかである。いずれのアプローチが用いられてもよい。以下に詳述するように、最近隣アルゴリズムは、探索を実行するときにより良好な計算時間性能を提供する他のアルゴリズムに置き換えられることができる。
【００７４】
３．一致があれば、プログラムＩＤ番号及び対応するフレーム番号を出力する。複数の一致があれば、全てのプログラムＩＤ及び対応するフレーム番号を出力する。一致がなければ、ＮＯＭＡＴＣＨフラグを出力する。
【００７５】
範囲探索は公差内で一致するパターンベクトルを必要とするが、各々の場合に必ずしも完全な一致でなくてよい。幾何学的視点から、範囲探索は、寸法が公差パラメータによって決定される多角形内にどの集合の項目が含まれたかを識別する。好適実施形態において多角形は３１次元超立方体である。
【００７６】
範囲探索（ＲＳ）公式化
【００７７】
好適実施形態においては、パターンベクトルは１×３１ベクトル
である。ここで、ｃは、一致を捜したところで検出されたパターンベクトルである。帯域の数は、上記したように、３１より多いかまたは少ないことがあり、その場合、結果に差がある。そして、計算の複雑さに対する精度の増加が代償になる。探索アルゴリズムについて３１要素ベクトルを用いて説明するが、当業者であれば、これらの方法が任意のサイズのパターンベクトルに適用されることになることを理解されよう。パターンライブラリはＭ×３１行列であり、ここでＭはデータベースに格納されたパターンベクトルの合計数であり、３１はパターンベクトル中の要素の数を表す。Ｍは、以下に示すように潜在的に膨大な数である。データベース全体は次の行列Ａによって表されると仮定する。
【数３】
【００７８】
ライブラリに格納されたこれらのパターンベクトルは、ライブラリパターンベクトルと呼ばれる。好適実施形態において、各ベクトルｚは、検出段階中にその検出が考えられている既知の音声コンテントを有するような、登録段階中に計算される３１要素のパターンベクトルである。検出段階中に、識別の実行は、ライブラリパターンベクトル｛ｚ＿ｏｐｔ｝の集合を配置することであり、このようなベクトルは公差パラメータによって決定される超立方体内に入れられている。
【００７９】
探索基準は、
【数４】
となるように任意のｚ＊の識別として表すことができる。
【００８０】
好適実施形態においては、Ｌ１ノルムが用いられる。ここで、
【数５】
はｘのＬ１ノルムである。従って
【数６】
ここで、ｅｍ，ｎは、ｃとｚｍ間のｎ番目の点誤差（point error）と呼ばれる。
【００８１】
ＲＳアルゴリズムによるライブラリ全体に対するｚ＊の探索は、点誤差基準の満足度に基づく。即ち、各点誤差は幾分かの公差以下でなければならず、好適実施形態においては、一定量以下のＬ１ノルム以下でなければならない。各要素及びＬ１ノルムに対する公差が同じであるか異なることがあり、そのことが探索の効率を変えることを当業者は理解されよう。
【００８２】
公差の決定は、経験的に測定される誤差のいくつかの統計学的測定に基づく。更に、１次Ｌ１ノルム以外の他の測定誤差が用いられることがあることが認められる。探索問題は今や範囲探索問題になっているが、そのことについては先行文献の他の場所に記載されている。P. K. Agarwal, Range Search, in J. E. Goodman and J. O'Rourke, editors, HANDBOOK OFDISGRETE AND COMPUTATIONAL GEOMETRY, page 575-598, Boca Raton, NY, 1997, CRC Press を参照されたい。Ｃ＋＋コードは、Steve Skiena, The Algorithm Design Manual, published by Telos Pr, 1997, ISBN: 0387948600 からも入手可能である。
【００８３】
以下にｚ＊を決定する方法の各ステップを示す。
【００８４】
１）Ｌをライブラリパターンベクトルのインデックス全てを含むインデックス集合に等しい値に設定する。
【数７】
【００８５】
２）ｎ＝１から開始する。
【００８６】
３）ｃのｎ番目の要素から各ｚｍ，ｎのｎ番目の要素間のｅｍ，ｎを計算する。ここで、ｍは１ないしＭである。
【００８７】
４）ｎ番目の点誤差が特定の公差Ｔｎより小さいパターンベクトルのこれらのインデックスのみを含むようにＬを更新する。
【数８】
Ｔｎは任意に設定することができる。好適実施形態においてはＴｎをｃｎの値の１０％に設定する。
【００８８】
５）Ｌが空集合でありかつｎ＜３１であれば、このルーチンから出て、ＮＯＭＡＴＣＨフラグを発行する。この条件が満たされなければ（Else）、ｎ＝ｎ＋１に設定する。ｎ＞３１であれば、ステップ６に進む。この条件が満たされなければ、ステップ３に進む。
【００８９】
６）Ｌに記載された全てのパターンベクトルとｃの誤差を計算する。
【数９】
最良の解は、ｅｍの全てを調べることにより決定され、それによってｚ＊が得られることになる。或いは、ソフトマッチングのために、２つの基準のいずれかを用いることができる。
【００９０】
基準１：誤差がいくつかの所定の閾値ｅｍａｘ以下であるｚｍのみを選択する。
基準２：最良のＭ個の候補をＬから選択する。ここで、Ｍ個の候補は最小の誤差のサイズからＭ番目の誤差のサイズである。
【００９１】
最良のＬ１の一致を有するインデックスｍが決定されたら、このインデックスを用いてパターンベクトルｚｍに対応するデータ記録を回収する。その後、データベースモジュールはプログラムＩＤ及び対応するフレーム番号を出力として出力する。
【００９２】
ｎ番目の繰り返しの開始時には、インデックス集合Ｌは、ｍ＝１からｎ‐１までの点誤差が公差テストに合格するようなライブラリパターンベクトルのインデックスを含むことに留意されたい。ｎ番目の繰り返しの開始時には、インデックス集合Ｌは
【数１０】
である。
【００９３】
ＲＳアルゴリズムのフローチャートを図８に示す。
【００９４】
３０，０００曲の歌に対して音声プログラムへの本発明の適用のためのライブラリサイズＭは数千万のオーダーであることが予測される。計算を以下に示す。
歌の数＝３０，０００
代表的な歌の長さ＝２０４秒（３分２４秒）
サンプリングレート＝８，０００サンプル／秒
フレームサイズ＝１６，３８４サンプル
フレーム間距離＝４，０００サンプル
【００９５】
歌１曲当たりのフレームの数は、歌の長さと１秒当たりのサンプルの数とを乗じた積からフレームサイズを引き、それをフレーム間距離で割ったものである。好適実施形態においては、約４０４フレームがある。３０，０００曲の歌では、Ｍ＝１２，１１７，１２０である。
【００９６】
この数字に対して、第１の繰り返しは、インデックス集合Ｌを更新するための分岐文の実行及び約１２００万の減算を必要とする。次の繰り返しはおそらくより少なくなるが、それでも数百万のオーダーにあることになる。また、メモリは、公差テストに必要な減算の結果全ての中間値を保持するように割り当てられなければならない。
【００９７】
高速範囲探索アルゴリズム
【００９８】
ｚ＊を見つけるために実行されなければならない減算の量を最小にする方法の改良がある。そして更に重要なことには、実行時間は、データベースのサイズほど速くは拡大しない。このことは、このサイズのデータベースには特に重要である。この性能強化は、大量のメモリの使用を犠牲にして達成される。しかし、コンピュータメモリのコストは歴史的に見ると連続して減少してきているので、これはここでは妥当なトレードオフであることを当業者は理解されよう。ＲＳアルゴリズムへの修正は、正確な誤差値を計算するよりむしろ指標付けを用いることである。この修正については、以下に更に説明する。
【００９９】
検出されたパターンベクトルとデータベースに保持されたパターンベクトル間の最良の一致（ベストマッチ）を回収するための改良された探索方法論は、ここでは高速範囲探索アルゴリズムと呼ばれる。前述同様に、Ａは、Ｍ行のパターンベクトルから構成されるライブラリ行列である。
【数３】
【０１００】
各行は、特定のパターンベクトルである。全部でＭ個のパターンベクトルがあり、好適実施形態においてはそれぞれが３１個の要素を有する。
【０１０１】
ステップ
【０１０２】
１．Ａの各個々の列を次のように分離する。
【数１１】
【０１０３】
２．列における要素の各々を昇順でソートする。
【数１２】
【０１０４】
３．ソートした結果、各要素ｚｍ，ｋを
にマッピングする。２つの相互参照表を作成する。表Ｒｋは、
のマッピングであり、表Ｔｋは、全てのｋ＝１〜３１に対して
をマッピングする。
【０１０５】
当業者は、ソーティング（分類）及び表作成が、登録の後であるが検出段階中のいずれかの一致の探索よりは前に行われることがあることを理解されよう。登録段階中にパターンベクトルを予めソートしてしまうことにより、システムは検出段階中の探索時間を短縮する。検出段階中に、方法は、後述するように、ソートされたベクトルを探索することから始める。
【０１０６】
インデックス探索
【０１０７】
問い合わせベクトル
及び公差ベクトル
と仮定する。公差内に収まるこれらの要素のインデックスを抽出するために二分探索法が用いられることがある。他の探索法が用いられることもあるが、ｌｏｇ（Ｍ）時間で実行する二分探索が好ましい。
【０１０８】
ステップ：
【０１０９】
１．ｋ＝１に設定する。
【０１１０】
２．二分探索を行い、
が１〜Ｍであるとき、ソートされた列ｋ、即ち
に、ｃｋ‐Ｔｋに最も近くかつｃｋ‐Ｔｋに等しいかまたはそれより大きい要素
を配置する。その後、再び二分探索を実行し、ｃｋ＋Ｔｋに最も近くかつｃｋ＋Ｔｋに等しいかまたはそれより小さい要素
を配置する。従って、集合
における全ての要素は公差要件を満たす。このように、二分探索を２回用いてｋ番目の列毎に
及び
を配置する。
【０１１１】
更に、仮に
が、公差要件を満足するような
全てのインデックスを含むインデックス集合である、即ち、
【数１３】
であるとする。
【０１１２】
３．ｋ＝ｋ＋１。ｋ＞３１であれば次のステップに進む。
【０１１３】
或いは、プロセスは、どの列がテストに合格する帯域の最小の番号を有するかを計算することができ、次のステップにおける帯域の当該番号から始めることができる。対応する帯域の番号が最小から最大へ向かうソートされたｋ値を昇順に並べることによって、結果はｋにわたる単純な増分の繰り返しより速く収束することができる。
【０１１４】
４．各上下限
（ｋ＝１〜３１）を求めるためにステップ２及び３をｋ＝３２まで繰り返し、このように３１個の
を決定する。
【０１１５】
各Ｐｋは独立して求められる。全てのｋに対し、Ｔｋを用いて、上下限
（ｋ＝１〜３１）内に入っているインデックス全てを原インデックスに再度変換することができる。その後、３１のインデックス集合に論理積（ＡＮＤ）演算を実行する。
【０１１６】
代わりの方法は、最初の２つのインデックス集合を積演算し、次にその結果を第３のインデックス集合と積演算し、最後のインデックス集合を積演算し、終わるまで以下同様にすることである。これは、以下に概説するアプローチである。
【０１１７】
５．ｋ＝１にリセットする。
【０１１８】
６．
における全てのインデックスを検索し、アレイＲに格納する。
【０１１９】
７．表Ｔｋを用いてＲにおける全てのインデックスを原インデックスに変換する。
全てのインデックスｍを集合Ｓに格納する。
表Ｒｋ+１を用いてｍを
に変換する（従って列１において表されるインデックスは列２における表現に翻訳される）。その後、結果が
の上下限内にあるかどうかを調べるためにテストする。
公差テストを適用し、
【数１４】
を生成する。このように、各連続する
は、先の
から、ｋ番目の要素に対する公差テストに合格しなかったそれらのインデックスを減じたものになることになる。従って、ステップ６においてｋ＝３０であるとき、
は３１の公差テスト全てを満たすインデックスである。
【０１２０】
８．ｋ＝ｋ＋１
【０１２１】
９．ステップ６に進み、ｋ＝３１までループする。
【０１２２】
１０．ここで、集合Ｓは３１の積演算ループ後の原インデックス全てである。Ｓが空であれば、ＮＯＭＡＴＣＨフラグを発行する。そうでなければ、ハードマッチングの場合、次に、例えば最も近い候補であり得る唯ひとつの勝ち残ったものを配置する。ソフトマッチングの場合、次に条件を満たす項目全てを求める。
【０１２３】
高速ＲＳアルゴリズムへの更なる速度増加
【０１２４】
ｋ＝１から始める代わりにステップ４から開始し、次にｋ＝２、次にｋ＝３、のように最後まで行い、各列における候補の合計数を測定することができる。各列における候補の合計数は、各
における候補の合計数に等しい。次に、テストされる最初のｋが
が最も少ない候補を有するようなものであり、全てのｋがテストされるまで以下同様であるようにｋの順序を変えることができる。このとき、積演算の順序は、候補の最小の番号を有する列から開始する。最終的な結果は、同じ３１のインデックス集合を、連続的にｋを増分させて積演算するのと同じであるが、再順序付けられたｋを昇順にすることによって、積演算の数は減るので、探索を加速する。
【０１２５】
探索ブースタ：
【０１２６】
現行の探索技法が一般的に周波数帯域方式によって周波数帯域を探索することを当業者は理解されよう。好適実施形態を用いた実証研究は、探索の最初の繰り返しによりデータベースにおける項目の６０％ないし９０％が当該周波数帯域に対してフィルタを通過することを示している。歌１曲当たり３００項目を有する６，０００の曲名のデータベースを仮定すると、探索される項目の合計数は１，８００，０００である。戻りが６０％であれば、システムは最初の積演算後に１００万以上の項目を取り扱わなければならない。最初の積演算のサイズがより小さければ、１つの探索結果に収束する必要がある繰り返しの数を減らすことができる。プロセスの最初の繰り返しにおいて探索結果の数を減らすように探索を予め処理することは、本発明（ここではブースタと呼ばれる）の別の目的である。
【０１２７】
ブースタは、２つ以上の周波数帯域をひとまとめにできるように異なる指標付け方式を用いる。ブースタを用いて、ブースタにおける単一の探索ループは範囲探索法における多重ループに等しく、それゆえに探索速度は向上した。順位方式を用いて、積演算インデックスのための探索の数を最小にするために探索の順序を決定する。この順位を確立するために、正規の範囲探索プロセス中に各帯域における戻りパーセンタイルの最大、平均及び標準偏差が計算される。これらの実証検証の結果は、ブースタプロセスを用いてどの帯域がひとまとまりになることになるかを選択するために用いられる。
【０１２８】
ブースタ指標付け方式は、２進１０進変換の拡張であり、２進値要素のベクトルは１０進の整数に変換される。拡張は単純である。具体的には、サイズＮのベクトル
の基数がＭであれば（ここでＭは整数である）、変換式は次の通りである。
【数１５】
【０１２９】
式１による変換は逆にもでき、式１を用いて
を
に変換することができることに留意されたい。従って、変換は、あらゆる固有の整数
が固有の
から計算されるように一対一の関係を有する。好適実施形態においては、パターンベクトルを収容するデータベース、パターン要素の各々は１６ビットの符号なし整数として記憶される。このことは、各パターンベクトルをＭ＝６５５３６及びＮ＝３１のコードベクトルと考えることができ、固有の
を各パターンベクトルから計算することができることを暗に意味している。この変換の結果として、パターンベクトルの多次元空間は１次元空間にマッピングされる。他では公差要件と呼ばれここではギャップ要件と呼ばれる問い合わせベクトル
からの必要な距離内にあるパターンベクトルの探索は、ギャップ要件
が満たされるようにデータベースにおいて全ての項目
を配置することである。符号化が１６ビットであるような好適実施形態においては、Ｑ＝１０％×６４Ｋ＝６５５４になるように公差Ｔｋは１６ビットの範囲の１０％である。実際には、値６，０００が用いられる。ブースタは、各帯域におけるギャップ要件（他では公差要件と呼ばれる）を
における対応するギャップ要件にマッピングする。探索は次に、全てのギャップ要件を満たす全ての項目を反復して選び出すことができるが、このアプローチの大きな問題は、複数のギャップ要件が
に複数の互いに素のセグメントをもたらすことである。具体的には、
における条件を満たす項目の識別のために３１回の繰り返しが必要であり、ここで
は
に変換され、第１のループは帯域１のためのものであり、３１番目のループは帯域３１のためのものである。パターンベクトルにおける帯域の数を変えることによって、繰り返しの数は変化することになるが、アプローチの実体は同じであることを当業者は理解されよう。
【０１３０】
技術的な問題を回避するために、２つの妥協がなされる。第１に、周波数帯域の部分集合のみが選択されてブースタに含められる、即ち、部分集合中のこれらのインデックスのみが式１を用いて符号化される。第２に、より小さな基数が用いられる。第１の妥協は、繰返しループの数、即ち具体的には互いに素のセグメントの数を減少させるので、ＣＰＵ速度の点から見ると全てのセグメントでの探索が実際的である。第２の妥協は、メモリ所要量を削減し、更に重要なことには、それは（僅かな量のＲＡＭだけで）ブースタの探索結果をハードコーディングしてブースタ内での探索を非常に高速にすることを可能にする。好適実施形態に対するプロセスについては以下に詳述する。
【０１３１】
１．基数Ｎ＝３１に設定する。
【０１３２】
２．３１帯域から３帯域を選択する。選択する帯域はそれより多くても少なくてもよい。しかし、数Ｎに比べて大きな数を選択するのであれば、ブースタ法はより遅くなり、その有用性はより制限される。小さすぎる場合には、十分に正確ではなく、加速もしない。よって、最適数は経験的に決定される。Ｎ＝３１であるような好適実施形態においては、３１から３を選択する。
【０１３３】
３．この組合せの結果は以下の通りである。
【０１３４】
（ａ）当該新たなインデックスのダイナミックレンジが０ないし３２７６７である。従って新たなインデックス各々は２バイトに符号化されることができる。
【０１３５】
（ｂ）探索結果のハードコーディング：３２７６８個のビン即ちビン０からビン３２７６７を作成する。ビンｍは、変換後に３帯域要素が値ｍをもたらすような全てのライブラリパターンベクトルのインデックスを保持する。
【０１３６】
４．探索方法論：
【０１３７】
（ａ）問い合わせベクトル
と仮定する。
【０１３８】
（ｂ）３つの特定の帯域において要素を選び出す。
【０１３９】
（ｃ）これら３つの帯域を用いて問い合わせベクトルを、式１を用いる数に変換する。
【０１４０】
（ｄ）変換された問い合わせと変換されたライブラリパターンベクトル間のｍ値の最も近い一致を探すことによって３つの特定の帯域においてギャップ要件を満たすライブラリベクトルのインデックス全てを収集する。
【０１４１】
（ｅ）（ｄ）のインデックスを出力に渡し、上記した帯域毎の（band-by-band）探索をこれらのインデックス集合上で再開する。
【０１４２】
式１を用いたライブラリパターンベクトルの変換がランタイム計算負荷を減らすために演算前に行われ得ることを当業者は理解されよう。
【０１４３】
Ｄ．歌検出／識別（Song Detection and Identification：ＳＤＩ）モジュール
【０１４４】
ＳＤＩモジュールは、ＤＢＳモジュールの結果を獲得し、その後音声またはビデオプログラムの同一性の最終確認を与える。ＳＤＩモジュールには、次の２つのルーチンが含まれる。
【０１４５】
１．検出‐検出される歌番号の規則性のフィルタリング
【０１４６】
ＤＢＳモジュールが、連続したフレームの集合上に異なるプログラムＩＤ番号を戻すときには、不規則な一致は、プログラムが全く検出されない良好なしるしである。対照的に、ＤＢＳモジュールが、連続したフレームの集合上に同一の歌番号を一貫して戻すときには、一貫性のある戻りはプログラムが首尾よく検出されることを示す。
【０１４７】
一貫性のある戻りを検出する一方で不規則な戻りを抑制するために「過半数の原則（majority vote rule）」に基づく単純なアルゴリズムが用いられる。ＤＢＳモジュールが、検出されたプログラムまたは歌のｉ番目のフレームに対する特定のプログラムＩＤ及びフレームＩＤを出力すると仮定する。不規則な戻りのせいで、結果のプログラムＩＤは、最初はフレームにおける有効なプログラム識別と考えられることにはならない。その代わり、システムは、ｉ，ｉ＋１，ｉ＋２，・・・，ｉ＋２Ｋ（好適実施形態においてＫは２から４の間に設定される）の隣接フレーム（即ち重複しないフレーム）の結果を考慮する。これら（２Ｋ＋１）個のフレームに過半数を獲得したもの（majority winner）がなければ、システムはｉ番目のフレームにおけるヌル検出を示すために歌番号＝０を発行することになる。過半数を獲得したものがあれば、即ち、フレームｉに隣接する少なくとも（Ｋ＋１）個のフレームが同一プログラムＩＤ番号を生成したら、システムはｉ番目のフレームに対して検出された歌番号をそのような過半数を獲得したプログラムＩＤ番号として発行することになる。過半数の計算は多くのやり方でなされることができ、例えば、過半数を獲得した閾値がＫ＋１より大きくかつ２Ｋ＋１より小さいかまたは２Ｋ＋１に等しい値であり、２Ｋ＋１の閾値が全会一致（unanimous vote）を構成することになるようなより強力なテストを適用することは、ある用途において有利であることがあることを当業者は理解されよう。これは、より多くの未検出の結果を潜在的に犠牲にして誤検出を減らす。ここでの目的のために、過半数は、これらの二者択一の閾値を含むように画定されることになっている。計算速度に対して、好適実施形態はメディアンフィルタを用いて過半数を決定する。ずらりと並んだ２Ｋ＋１個の数の中央値は、
Ｋ＝１，２，．．．のとき、Ｚがソートされた後のＫ番目の項目である。例えば、Ｚ＝［１，９９，１００］であれば、Ｚの中央値は９９である。そのような計算のための式について以下に述べる。
【０１４８】
ＤＢＳモジュールはｎ番目のフレームに対してプログラムＩＤ＃［ｎ］を戻すと仮定する。フレームｉに対する中央値を計算するために、
とする。次に、
とする。ここで、
である。このとき、検出された結果はｘ掛けるｙの掛け算である。この式の主な特徴は、それがループ及びカウンタを必要とする具現化よりもむしろワンパスに具現化されることができることである。
【０１４９】
２．プログラムの識別
【０１５０】
上記したような過半数の原則を用いて検出音声またはビデオプログラムがされると仮定すると、次のステップは追加の検証テストを課して、検出されている歌のフレーム同期があるかどうかを決定することである。具体的には、フレーム同期テストは、各ｐ番目のフレームに対してＤＢＳモジュールにより出力されたフレームＩＤ番号が経時的に即ちｐの増加につれて単調に増加する単調増加関数であることをチェックする。そうでなければ、即ちフレームインデックスがランダムであれば、検出は無効を宣言される。以下に示すのは、完全なＳＤＩの段階的方法である。プログラムの一部が繰り返されている場合には、例えば、毎回プログラムに編集されることがある歌のコーラスにおいて、そうでなければ実質的に同一であるがタイムフレームが異なるパターンベクトルは、ＤＢＳモジュールによって見つけられることになる。このような場合には、システムはこれらの結果をバッファに格納することによって保有し、後述する順番付けテストを受けさせる。順番付けテストが進むにつれて、これらの暫定的な結果のいくつかは、順番付けテスト下で無効であると考えられかつその後に無視されることになるタイムフレームインデックスを有することになる。単一の暫定的なスレッドが残ったら、次に検出の開始及び停止時間が更新される。
【０１５１】
ＳＤＩアルゴリズム及びステップ
【０１５２】
ｓｐを、ｐ番目のブロードキャストフレームが検出された後に直近２Ｋ＋１個のプログラムＩＤを保持する構造であるとしよう。
【数１６】
【０１５３】
ここで、ｓｍ，ｎ＝ＤＢＳモジュールによってｍ番目のブロードキャストフレーム中に検出されるｎ番目のプログラムＩＤである。Ｐｍはビンのサイズであることに留意されたい。一般的に、ｍが異なればＰｍは異なる。
【０１５４】
同様に、ｆｐは対応するフレーム番号またはフレームインデックスを保持する別の構造である。
【数１７】
ここで、ｆｍ，ｎ＝ｓｍ，ｎの対応するフレームインデックスである。
【０１５５】
また、ＳＩ＝過半数票テスト及び順序付けテストの条件がうまく満たされるように首尾よく検出された最後の歌またはプログラムのプログラムＩＤである。新たなまたは異なる歌またはプログラムが検出されるまでこの結果を保持するためにレジスタが作成される。
【０１５６】
ステップ：
【０１５７】
１．ｓｐの過半数を計算する。ｓｐの１番目のビンにおけるプログラム１つ１つを参照と考える。残りの２Ｋ個のビンをスキャンし、１番目のビンにおける任意のプログラムが過半数要件に合格するか決定する。
Ｄｐ＝過半数要件に合格するｓｐの１番目のビンにおける項目のインデックスであり、１番目のビンにおける全てのプログラムが過半数要件を満たしていなければＤｐ＝０である。
【０１５８】
２．ｗｐ＝０であれば、ｐ＝ｐ＋１とし、ステップ１に進む。上記を満足せず（Elseif）、ｗｐが単集合（１要素の集合を意味する）であり、０に等しくなければ、ＳＩ＝ｗｐに設定する。ステップ３に進む。上記をいずれをも満足せず、ｗｐが２つ以上の候補を有するのであれば、ＳＩ＝ｗｐ（複数のプログラム一致がある場合）に設定する。ステップ３に進む。ｗｐのｓｐ，ｍ毎にステップ３〜７を実行する。
【０１５９】
３．Ｄｐにおけるあらゆるｓｐ，ｍに対して、ｆｐにおける対応するフレームから行列Ａを形成する。
【数１８】
ここで、ｆｔはｆｐのｔ番目のビンにおけるフレームである。ｓｐ，ｍの一部であるｔ番目のビンにフレームがなければ、ｆｔ＝０である。
【０１６０】
４．ｆｑ＝０であればｑ番目の行をなくして、Ａの圧縮を行う。
【数１９】
【０１６１】
５．以下のステップで行を取り除くことによってＡを整理する。
【０１６２】
Ａ．ｎ＝１から開始する。
【０１６３】
Ｂ．
【数２０】
及び
【数２１】
を計算する。ミスマッチのプログラムＩＤを有する項目全てを取り除くことによってステップ５を実行した後、このステップは順序付けに正しく従う項目のみを識別する。
【０１６４】
Ｃ．ここで、量ｄ１は、Ｂにおける２つの被検出フレーム間のフレームのオフセットである。この量は、ｄ１値にサンプルにおけるフレーム間距離を乗じて１秒当たりのサンプルで割ることによって実際の時間オフセットに変換することもできる。量ｄ２は、２つのブロードキャストフレーム間のフレームオフセットである。ここで、ｄは２つのオフセットの比であり、検出された順序の向上率（advance rate）を表す。具体的には、好適実施形態において、システムは、ｄ値として理想の向上率４を期待する。しかし、ｄに対する融通が利く制約が適用される。その制約とは即ち［ｄ１∈（４［ｄ２‐１］＋２，４［ｄ２‐１］＋６）］であれば、２つのフレームは正しい並び順にあるという制約である。従って、ｄ２＝１では、同じプログラムＩＤを有する２つの隣接放送フレーム間で２から６フレームのオフセットが期待される。ｄ２＝２であれば、オフセットは２＋４から６＋４フレームである。従って、この範囲は、範囲における４つのフレームの追加オフセットを除いて同じである。２及び６の値は、理想値４を中心とした範囲である。１つの値に代わる範囲は、オフセットが厳格であるよりむしろ少し融通が利くことを可能にする。融通性を狭くするように、３から５の範囲を選択することができる。同じようにして、範囲を１から７までにして融通性を非常に広くすることも可能である。ステップＤに進む。そうでなければ、Ｂにおける全ての項目にわたり順番付けるために、ｎ＝ｎ＋１。ｎ＜Ｎであれば、ステップＣに進む。そうでなければ、ステップＤに進む。
【０１６５】
Ｄ．行列Ｃが戻される。Ｃ中のどの行もみな、順序付け要件を満たす項目から構成される。
【０１６６】
順序付け要件と合わない行を削除することによりＢを圧縮する。更に、Ｂの第１の項目を参照と考えることにより、第２の項目が順序付け要件を満たしていなければ、プロセスは第３の項目にジャンプしてそれが第１の項目で順序付け要件を満たしているかどうかを確かめることができることに留意されたい。第２の項目が要件を満たしていれば、この第２の項目は第３の項目のための参照になる。
【数２２】
【０１６７】
ここで再び過半数要件を強制する。Ｃにおける項目の数が過半数要件を満たしていなければ、項目ｓｐ，ｍは更なるテストを受ける資格がなく、ステップ３に戻ってＤｐにおける次の項目をテストする。そうでなければ続いてステップ６へ進む。
【０１６８】
過半数テストを再度適用する。なぜならば、ステップ５の過半数テストに合格したとしても、順序付けの原則の要件を用いて結果を整理した後には過半数テストに合格しないことがあるからである。修正過半数テストに合格したら、そのときには新たなプログラムまたは歌が積極的に検出されているか、そうでなければ何も検出されない。
【０１６９】
６．ｓ＝Ｃにおける項目（即ち行）の数としよう。ｓ＜Ｋであればステップ９に進む。そうでなければ回帰分析を行う。
【０１７０】
Ａ．
及び
がそれぞれＣの第１および第２列であるとしよう。ここで、上添字Ｔは転置行列であることを示す。回帰分析のために次の行列を作成する。回帰分析を用いて、フレームＩＤ番号の順序付けの線形性の尺度を計算する。
【０１７１】
Ｂ．傾き及び切片の両方を計算する
【０１７２】
Ｃ．Ｃの相関係数ｒも計算する。
【０１７３】
７．［ｒ＞０．９かつ傾き≧２かつ傾き≦６］であれば、項目ｓｐ，ｍに関連するスレッドは、全てのテストに合格し、トラッキングモードへの有効な項目である。項目ｓｐ，ｍ及び対応するスレッドをFinal＿Listと呼ばれるレジスタに格納する。
【０１７４】
この条件が満たされなければ、項目ｓｐ，ｍをなくす。
【０１７５】
Ｄｐにおける次の項目のテストを続ける。
【０１７６】
８．トラッキングモードに入る。Final＿listにおける各スレッドは、集合的にまたは個別にのいずれかで追跡されることになる。
【０１７７】
９．トラッキングモードを開始する。
【０１７８】
Ａ．トラッキングに用いられる小さなデータベースを作成する。
【０１７９】
ｉ．集合的トラッキングモードにおいては、小さなデータベースはFinal＿listにおける条件を満たす項目全てのパターンベクトル全てを含む。
【０１８０】
ｉｉ．個別トラッキングモードにおいては、各特定の項目Final＿listのためのパターンベクトルだけを含む専用データベースが当該項目のために作成される。
【０１８１】
Ｂ．トラッキングモード＝集合的トラッキングであれば、
【０１８２】
ｉ．ｐ＝ｐ＋１。
【０１８３】
ｉｉ．放送の（ｐ＋１）番目のフレームに検出を実行する。
【０１８４】
ｉｉｉ．各スレッドの順番を更新する。スレッドが順序付け要件を満足するかを観察することによって各スレッドのメリットを監視する。
【０１８５】
ｉｖ．順序付け要件を満足する少なくとも１つのスレッドが存在するのであれば、ステップｉに戻り、トラッキングを続ける。そうでなければトラッキングを出る。
【０１８６】
トラッキングモード＝個別トラッキングであれば、各スレッドのための専用データベースをトラッキングに用いる。ステップは集合的トラッキングのステップと同じである。
【０１８７】
ここでの順序付け要件は、ステップ５ｃで用いられているものと同じである。即ち、新たなブロードキャストフレームに対する被検出フレームのＩＤが単調増加様式であり、好適実施形態においては放送の連続するフレーム間の量の増加が２から６の間であることが期待できる。
【０１８８】
追跡されている任意のスレッドに対して、当該新たな放送が以前のフレームに対して順序付け要件を満たしていなかったならば、公差手段が実施される。即ち、各追跡は、せいぜいＱ回までの失敗を有することができる。ここで、Ｑ＝０，１，２，・・・である。Ｑ＝０であれば、順序付け要件を満たしていないことは容認されない。
【０１８９】
Ｃ．トラッキングモードが終わった後、各スレッドのメリットを調べる。最高スコアを有するスレッドが、Final＿listにおける全スレッド中の勝ちスレッドである。
【０１９０】
ｉ．スコアは、放送の対応するフレームへのスレッドにおける各フレーム間の誤差に基づき、またはスレッドの持続時間に基づき計算することができる。あるいはその両方に基づいて計算することができる。好適実施形態においては、持続時間は各スレッドのトラッキングスコアと考えられる。トラッキング期間内に最長のものを持つものは勝ち（winner）スレッドである。
【０１９１】
Ｄ．複数のプログラムがステップ２においてＳＩを通知されていれば、勝ちスレッドのプログラムＩＤによって通知を補正する。
【０１９２】
１０．放送からのｐ番目のフレームを待つ。ステップ１に戻る。
【０１９３】
連続的なフレームＩＤの直線性をテストするためにステップ６において用いられる値は、テストが条件を満たすのをより容易にするかまたはより困難にするかいずれかのために変更されることがあることを当業者は理解されよう。これは、検出なしに比べて正しい識別の数を増加または減少させる一方で、結果が誤検出を増加させるかまたは誤検出を抑制するかどうかを制御する。
【０１９４】
本発明について詳細に説明及び図示してきたが、これらは例証及び例示を目的としたものであり、何らかの限定として捉えられるべきものではないことは明確に理解されるであろう。本発明の種々の特徴は、明確にするために別々の実施形態との関連で説明されているものがあるが、１つの実施形態に組み合わせて与えられることもあることが理解されよう。逆に、本発明の種々の特徴は、簡潔にするために１つの実施形態との関連で説明されているものがあるが、別々に、または適切に組み合わせて与えられることもある。付録に記載の特定の実施形態が、本発明の非常に詳細な開示を提供することだけを意図し、何らかの制限を加える意図ではないことは理解されよう。本発明のソフトウエア構成要素のいずれもが、必要に応じて、ＲＯＭ（読出し専用メモリ）形式で具現化されるか、ＣＤ‐ＲＯＭ、磁気媒体を含む任意の種類のコンピュータ読取り可能媒体に格納されるか、コンピュータメモリに格納されたデジタルデータファイルとして伝送されることがあることが分かる。ソフトウエア構成要素は、一般的に、必要に応じて慣用技術を用いてハードウエアに具現化され得る。
【０１９５】
本発明の精神及び範囲は、特許請求の範囲の条件によってのみ限定されるものである。
【表１】
【表２】
【表３】
【表４】
【表５】
【図面の簡単な説明】
【０１９６】
【図１】メディア放送監視システムの構成要素
【図２】音声プログラムの一連のフレームからプログラムの同一性の検出までの検出アルゴリズムのデータフローの図示である。
【図３】パターン生成モジュールのフローチャートである。
【図４】原型の周波数帯域限界が如何に原型フレームシグネチャとより高速で再生される同一音声プログラムのシグネチャ間のパターンミスマッチをもたらすかの例。
【図５】周波数帯域限界の変更が如何に原型の音声プログラムと高速及び低速で再生される同一音声プログラムのフレームシグネチャ間の改良された一致を与えるかの例。
【図６】新たな周波数帯域限界設定は、音声プログラムにおける±２％の速度変化変化があってでも音声検出アルゴリズムのロバスト性をもたらすことを示す。
【図７】ＤＢＳ動作フローの概略である。
【図８】ＳＲＲアルゴリズムのフローチャートである。
【技術分野】
【０００１】
本発明は、例えばアナログ、デジタルとして放送されるのであれインターネット上でデジタルとして放送されるのであれ、ラジオ、テレビ、またはインターネット、またはテレビ信号などの放送プログラム（番組）にのせて放送される音楽または音声の自動検出及び識別に関する。「放送」とは、現在知られていようと将来考案されようと、例えば、ストリーミング、ダウンロードまたはストリーミングのピアツーピア配信またはそのようなコンテント配信活動を含むネットワークトラヒックの検出を含めた任意の容易に入手可能なコンテント源を意味する。システムは、プログラムをデジタル方式でサンプリングし、デジタルサンプルストリームを短時間セグメントの大きな集合に分離することによって既知のプログラムを先ず登録する。これらのセグメントはその後、セグメントの特徴である特定の機能集合を抽出するために処理される。本発明は、既知のプログラムの特定のセグメントのための機能集合を表す数値コードを生成するために各機能集合を有している。プログラムを識別するこれらのコード及び登録データは、データベースをシステムの一部として取り込まれる。１若しくは複数のプログラムの登録が完了したら、システムは次に、入力信号から機能集合を抽出し、システムに入力される各タイムセグメントのための数値コードを作成し、その後、検出された数値コードの順番をデータベースに格納されている数値コードと比較することによって、放送信号において登録されたプログラムの存在を検出及び識別することができる。登録されたプログラムの誤検出率、見逃し率を低下させ、正しい検出を増やすために、比較プロセス中に種々のテスト基準が適用される。本発明には、比較的短い時間内に実行するようにするための比較プロセスの改善及び最適化も含まれる。
【背景技術】
【０００２】
本発明は、ラジオ、テレビ、またはインターネット上でデジタル化されて配信されるコンテントなどの広範に広められるプログラムの自動認識に関する。
【０００３】
放映権料などの放送に絡む権利使用料を正しく計算し、契約地域制限に従っていることを確認し、または所定の広告が予定通りに放送されているかを検証するために、広告主を含む放送プログラムの著作権者は、自分たちのプログラムがいつ、どこで放送されているかを測定する必要がある。ラジオまたはテレビを監視（モニタリング）する伝統的手法は、人間が聴取または視聴して見聞きしたものを記録するか、ラジオ局及びテレビ局の放送記録に頼るかである。これは、効率または精度が制約された多大な労力を要するプロセスである。高度なコンピュータシステムを用いてこのプロセスを完全に自動化することが本発明の目的である。このように、音声またはビデオコンテントがシステムに登録され、その後、音声検出の場合には、ラジオ、テレビまたは他の広く配信される音声コンテント源からのサウンドトラックがシステムに入力される。ビデオの場合には、その源が何であれビデオ信号がシステムに入力される。本発明を用いて、登録されたプログラムコンテントの検出及び識別が自動的に行われる。
【０００４】
先行技術：
【０００５】
放送プログラムの検出を自動化するために多くの方法が開発されてきた。これらの技法は、一般的に２つのカテゴリーのうちの１つ、即ちキュー検出またはパターン認識に分類される。キュー検出法は、特許文献１〜３によって例証されている。これらの技法は、配信の前にプログラムに挿入された埋め込みキュー（embedded cue）に頼っている。これらのアプローチは当該分野では支持されてはいない。音声プログラムにキュー信号を置くことは、このアプローチの採択を制限してきた。というのも、これはプログラム所有者及び／または放送局の協力を必要とするからであり、非実用的なものになっていた。
【０００６】
パターン認識法は、一般的にコンテント自体のスペクトル特性を利用して固有の識別コードまたはシグネチャを生成する。従って、識別コンテントの技法は、次の２つのステップからなる。第１は、データベースへの挿入のために既知のコンテントからシグネチャを抽出するステップ、第２は、検出されたコンテントからシグネチャを抽出し、検出されたコンテントを識別するためにデータベースにおけるシグネチャの一致を探索するステップである。このように、好適なアプローチは放送コンテント自体の特性を利用し、当該コンテントに特有のシグネチャを作成する。例えば、特許文献４には、既知のテレビプログラムを獲得し、当該フレーム内で音声信号及びビデオ信号の両方から各ビデオフレーム即ちシグネチャコードを作成するシステムが開示されている。最近になって、インターネット分散コンテントのための類似の検出システムが提唱されている（例えば特許文献５）。
【０００７】
音声単独の場合、特許文献６では音声信号のみが用いられる音声識別システムを開示しているが、入ってくる放送信号に対して制限されたタイムスライスによって表される音声プログラムを相関させるように試みているので、有用性が限定されている。特許文献６に開示されているマッチング法は、直接信号相関に依存しているので、高度に計算集約的である。更に、このアプローチは、特にプログラムが検出前に時間圧縮されるかまたは他の方法で変更されていれば、精度が制限されることがわかっており、好ましくない。これはまた、タイムスライスのサイズがその正しい識別を向上させるために大きくされるならば、誤検出識別を起こす傾向があり、計算的に不経済である。ラートら（Lert, et. al.）は、プログラムのセクションの開始を示すような人工コードまたはその他の人為的なものでない天然のマーカのいずれかがプログラムにおいて検出され、その後、機能シグネチャが所定の時間後に測定されるという第１のカテゴリーの符号化法と組み合わせることによって、相関方法の計算作業負荷を軽減する方法を特許文献７に開示している。この方法は、キューを作成するために音声に可聴コードが挿入されなければならないのでそれを劣化させるかまたはコンテント源の協同を必要とするか、高度に当てにならない新たな音声プログラムの開始を示す天然のマーカに頼るかいずれかの場合に、音声のみの用途における有用性を限定している。特許文献８において、ラートらは更に、シグネチャを測定及び計算する前に信号において「安定条件」が生じるまで待つという本発明の改善について述べているが、この方法の信頼性はサンプルタイムスライスのサイズによって制限される。特許文献９では、信号の部分を無作為に選択し、本発明のシグネチャ生成プロセスへの入力としてサンプリングすることによってデータ処理負荷の問題に取り組んでいる。
【０００８】
特許文献１０及び１１は固有のシグネチャを計算するより複雑な方法を開示しているが、ここでは、所与のビデオフレームと以前のビデオフレームにおいてなされた同じ測定間の所定の数の周波数帯域のそれぞれにおいてエネルギーの変化を比較することによって所与のビデオフレームに対応する音声シグネチャが導かれる。しかし、マッチング技法は、音声及びビデオシグネチャの組合せ、または天然のマーカ（この場合にはプログラムの開始または終了）の使用に依存している。従って、この方法は、音声のみのプログラムに関するラートの問題と同じ問題を抱えている。
【０００９】
それに加えて、特許文献１２では、各音声プログラムに対して１つのシグネチャ値を作成するための音声プログラム内の可聴機能、特に、振幅、音の高さ（即ち基音）、帯域幅、低音（即ちリズム解析）、明るさ（即ちプログラムの周波数応答の形状）、メル周波数ケプストラム係数のグループの使用を開示している。音声における長期にわたるこれらの詳細な機能の集合は、非常に多様性がある結果をもたらし、実世界の放送局において十分なロバスト性を有していない。特許文献１３及び１４は、シグネチャを作成するために音声信号においてエンベロープ（例えば音の大きさ）機能を用いるデジタル回路を開示している。このアプローチは、時間軸圧縮技法の適用によって時間圧縮問題に取り組むべく立案されている。音の大きさ（ラウドネス）への依存は、同様に実世界環境における使用を難しくする他のロバスト性問題を有する。特許文献１５は、音楽の開始点から、所定の位置から数えられる所定の数のデジタルサンプルを用いて音声シグネチャが作成されるシステムを開示している。このアプローチは、放送、または音声がアナログ形式で検出される場合には、またはプログラムの再生が速度を変化させたか、原トラックからの周波数等化が適用されているかまたは音声がプログラムセグメントにダビングされた場合には、より一層信頼できない。
【特許文献１】米国特許第４，２２５，９６７号明細書
【特許文献２】米国特許第３，８４５，３９１号明細書
【特許文献３】米国特許第４，５４７，８０４号明細書
【特許文献４】米国特許第４，７３９，３９８号明細書
【特許文献５】国際公開公報第ＷＯ０１／６２００４ Ａ２号明細書
【特許文献６】米国特許第３，９１９，４７１号明細書
【特許文献７】米国特許第４，２３０，９９０号明細書
【特許文献８】米国特許第４，６７７，４６６号明細書
【特許文献９】米国特許第４，７３９，３９８号明細書
【特許文献１０】米国特許第５，４３６，６５３号明細書
【特許文献１１】米国特許第５，６１２，７２９号明細書
【特許文献１２】米国特許第５，９１８，２２３号明細書
【特許文献１３】米国特許第５，２１０，８２０号明細書
【特許文献１４】米国特許第４，８４３，５６２号明細書
【特許文献１５】米国特許公開公報第２００３００８６３４１号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、直列のビデオ信号（音声の場合）または信号においてプログラムにおける既知の時間を示す標準的マーカに頼ることなく、非現実的な計算能力を要求しない音声プログラムの特徴を表すコードを計算する固有かつ新規な方法により既知の音声またはビデオプログラムの識別を行うことができるシステム及び方法について説明する。このシステム及び方法の利点は、精度、速度、再生速度変化に対するロバスト性、何らかの埋め込みキューまたはウォーターマーク（透かし）に頼ることなくリアルタイムで識別プロセスを実行する能力である。それに加えて、本発明は、高速データベース探索方法論を具現化するために低コストで高性能なコンピューティングプラットフォームのアベイラビリティをうまく利用する。
【課題を解決するための手段】
【００１１】
Ａ．概要
【００１２】
本発明を具体化する放送監視／検出システムは、２つの段階即ち登録及び検出において作業する。登録段階中に、プログラムをデジタルデータとしてシステムに送信することによって既知のプログラムコンテントがシステムに登録される。一連のシグネチャは、この場合ではパターンベクトルであり、当該分野でより一般的には「フィンガープリント」または「シグネチャ」であるが、これは、集団的にこれらと相互参照されるプログラムコンテントの識別データと共に、一連のデータ記録としてデータベースに格納される。第２段階中に、未確認のプログラムがシステムに入力される。そのようなプログラムには、地上放送、衛星、インターネット、ケーブルテレビまたはその他の配信媒体であろうとなかろうと、現在知られていようとも将来的に考案されようとも、ラジオ、テレビ、インターネット放送またはその他の音声またはビデオプログラム源を含めることができる。そのようなプログラムが監視されている間、プログラム（またはその他のシグネチャ生成技法）のパターンベクトルが継続的に計算される。次に、計算されたパターンベクトルを用いてデータベースにおける一致を探索する。ある一致が見つかって確認されると、システムは、データベース中の相互参照される識別データを用いて、現在再生されているコンテントの識別データを供給する。好適実施形態においては、システムはコンピュータ上で走行するソフトウエアであるが、システムの性能及び能力を増大するために専用ハードウエア構成要素が各モジュールの一部または全部を置き換えることがあることが想定される。
【発明を実施するための最良の形態】
【００１３】
好適実施形態においては、中央処理装置を含むコンピュータがサウンドカードまたはインタフェース機器に接続され、そこに音声プログラムが与えられる。登録段階中に、ＣＰＵはサウンドカードから音声またはビデオデータをフェッチし、パターンベクトルデータを計算し、その後、プログラムの識別情報及びタイミングデータと共にこれらの結果は以下に更に述べるようにデータベースに格納される。或いは、データは、オリジナルの情報源（authentic material）、例えばコンパクトディスク、ｍｐ３ファイル、または信号を含むその他のデジタルデータ源などから直接ロードされることがある。非音声用途の場合には、素材供給源は、ＤＶＤディスク、映画スタジオから提供されるマスタ、テープまたは、プログラムが固定または格納されるその他の表現媒体であることができる。もちろん、素材によっては容易に利用可能な供給源を有しないことがあるが、そのような場合には音声または他のプログラム信号が以下の方法で用いられる。システムは、未知のプログラムを定期的に検出するが、毎回実質的に同じシグネチャの集合を含んでいれば、プログラム素材に対して任意の識別子を割り当て、登録段階中にプログラムが導入されたかのようにデータをデータベースに入れる。プログラムの同一性が将来的に決定されてしまえば、データベースは、認証情報と同様に適切な情報を含む一方で、同時に、プログラムの同一性が未だ分かっていないときに検出された使用データをプログラムの所有者に供給するように更新されることができる。データベースは、典型的な例では、任意の種類のコンピュータバスまたはデータ伝送インタフェース（ＳＣＳＩを含む）を用いてコンピュータの中央処理装置に接続されたハードディスクドライブに格納されるデータファイルである。
【００１４】
検出段階中に、ＣＰＵは、サウンドカードまたはビデオカードからプログラムデータをフェッチするか、またはコンピュータハードディスクドライブまたは外部メディアリーダに格納され得るデータファイルからプログラムデータをロードする。ＣＰＵは、パターンベクトルデータを計算し、その後、ハードディスクドライブに格納されたデータベースにタイミングデータとともにデータベース問い合わせを送信する。データベースは、コンピュータにおけるものと同じハードディスクドライブであるかまたはデジタルコンピュータネットワーク上でアクセスされる外部ハードディスクドライブであることがある。一致するデータが見つかると、ＣＰＵは、以下に詳述するようにプログラムの識別を確認するためにデータを処理し続ける。ＣＰＵはその後、識別結果を遠隔位置へ配信してグラフィカルユーザインタフェースを用いて画面上に表示されるかまたはハードディスクドライブに格納された別のデータファイルに記録される当該分野でよく知られている多種多様のコンピュータネットワーク化システムのいずれかで通信することができる。方法を実行するプログラムは、任意の種類のコンピュータ読取り可能媒体、例えば、ハードディスクドライブ、ＣＤ‐ＲＯＭ、ＥＥＰＲＯＭまたはフロッピー（登録商標）に格納され、実行時にコンピュータメモリにロードされることがある。ビデオの場合には、信号はアナログ−デジタルビデオ変換カードを用いて得ることができるか、またはデジタルビデオデータは例えばインターネットまたはデジタルテレビ放送などのデジタルビデオ源から直接検出されることができる。
【００１５】
上記システムは４つの構成要素から構成される。４つのモジュールの相互接続を図１に示す。４つのモジュールとは即ち、（１）初期段階の信号処理段階、（２）中間のパターン生成モジュール、（３）それに続くデータベース検索エンジンモジュール、（４）最後のプログラム認識モジュールである。登録段階中に、既知の音声またはビデオコンテントのためのシグネチャを作成するパターン生成モジュールの結果はデータベースに格納され、探索／パターン認識モジュールは用いられない。
【００１６】
各モジュールの機能について以下に更に詳述する。
【００１７】
１．収音（Sound Acquisition：ＳＡ）モジュール
【００１８】
ＳＡモジュール（１）は、音検出回路からアナログ音声データを受信し、それを残りのモジュールに利用可能にする。当業者は、音声またはビデオ信号を受信し、これらの信号をデジタルデータに変換する様々な製品があることを理解されよう。これらの装置は、任意のデジタル音声データ源である可能性があり、アナログ音声データをコンピュータのＣＰＵによるアクセスが可能なデジタル音声データに変換するパーソナルコンピュータにおけるインタフェースカード、デジタル音声データを標準形式で出力する独立型（スタンドアロン）装置、または音声出力を有するデジタルラジオ受信機が含まれる。或いは、デジタル形式の予め検出された信号が、典型的なデータネットワークを介してシステムに接続された記憶装置からアクセスされることができる。ＳＡモジュールは、定期的に、デジタルインタフェース機器またはデータ記憶装置からデータを読み取り、パターン生成モジュールによってアクセスされることになるデータバッファまたはメモリへデータを記憶する。典型的なデジタル音声システムが、サンプリングレートと呼ばれる規則的な間隔でデジタルワードを供給することになることを当業者は理解されよう。音声信号を表す一連のデジタルワードは、デジタル音声サンプルである。本発明は、これらのサンプルを、所定の数のサンプルからなる一連のタイムフレームに編成する。タイムフレームは、順序よく記憶される。或いは、コンピュータメモリ（オペレーティングシステムがページング及びスワッピングをサポートするのであればハードディスクドライブを含む）に格納されるデータ構造は、タイムフレームが物理的に順序よく記憶されないときに用いられることがあるが、論理的にはこれらがメモリアドレッシングによって検出された順番にインデックス付与または参照されることがある。
【００１９】
好適実施形態においては、音声信号は、低域フィルタリングを含めた当該分野で既知の方法で調整される。好適実施形態において、信号はＳＡモジュール内で８０００Ｈｚの速度でサンプリングされる。好適実施形態においては、１６，３８４個のサンプルが１フレームを構成する。この速度では、信号はサンプリングされる前にエイリアス除去のために低域フィルタリングされなければならない。しかしながら、後述するように、より高いサンプリングレートが、下流の計算における適切な調整を行って用いられることもある。
【００２０】
ビデオプログラムの場合には、収音モジュールは、本質的に同様にして類似のやり方で作動する。即ち、ビデオ信号はデジタルビデオ信号として得られ、公知の方法を用いてビデオフレーム上でフレーム方式により周波数領域に変換される。本発明については、好適実施形態に関する記述を通して音声への適用として詳細に説明する。しかし、記載のシステム及びプロセスは、音声のみならず、シグネチャまたはパターンベクトルが定期的にビデオ信号から導かれているビデオにも適用可能である。チャールズ・ポイントン氏の文献（"A Technical Introduction to Digital Video", Charles A. Poynton, John Wiley & Sons, New York, (c)1996）を参照されたい。
【００２１】
２．パターンベクトル生成（Pattern Vector Generation：ＰＧ）モジュール
【００２２】
検出段階中に作動するＰＧモジュール（２）は、ＳＡモジュールによって検出及び記憶された記憶デジタル音声またはビデオサンプルをフェッチする。サンプルのフレームが受け取られると、ＰＧモジュールはフレームのパターンベクトルを計算し、検出段階にいるときにはパターンベクトルをデータベース探索モジュールにデータベース質問の形で送信することになる。登録段階の間、ＰＧモジュールは、パターンベクトルが既知の音声またはビデオプログラムに関する他の適切な情報との相関関係においてデータベースに格納されるようにするために、パターンベクトルを計算する。パターンベクトルの計算については、以下に詳述する。
【００２３】
フレーム間距離
【００２４】
各増分音声サンプルに対して、新たなフレームを開始することができる。即ち、各音声サンプルは、Ｎが或るフレームにおけるサンプルの数であるとき、Ｎ個の重複フレームの構成要素であることがある。これらの重複フレーム間の距離は、フレーム間距離である。パターン生成のためのフレーム間距離を短くすれば、プログラム開始時の不確実性の問題が軽減される。開始時間がわかっていないとき、フレーム間距離がより短ければより良好な結果が得られる。好適実施形態においては、音声プログラム登録段階中に、フレームの約１／４である４，０００の値が用いられる。精度を向上させるかまたは計算時間及び記憶オーバヘッドを減少させるかいずれかのために他の距離が用いられることもある。従って、好適実施形態においては、既知の音声プログラムのデータベースにおける第１のフレームは音声サンプル１ないし１６，３８４に対応し、第２はサンプル４００１ないし２０，３８４に対応し、以下同様である。検出段階中に、フレーム間距離は１フレーム長さに等しい値に設定される。従って、検出された音声プログラムの第１のフレームにはサンプル１ないし１６，３８４が含まれ、第２のフレームにはサンプル１６，３８５ないし３２，７６８が含まれ、以下同様である。
【００２５】
８０００Ｈｚのサンプリングレート、１６３８４サンプルのフレームサイズ、４０００のフレーム間距離の好適実施形態の設定を用いるとしても、異なるサンプリングレートが用いられることがあり、その場合、結果に差がある。例えば、サンプリングレートが１６０００Ｈｚ（好適な設定の２倍）のとき、フレーム番号サイズは３２７６８（サイズは２倍であるが持続時間は同じ）、フレーム間距離は８０００（０．５秒でのフレーム間距離と同じ）となり、好適な設定を用いたときとほぼ同じパターンベクトルが生成される。更に変わった点は、パターンベクトルを計算するために用いられる各サブバンドにどのフーリエ変換（ＦＦＴ）係数が含まれることになるかを決定することだけである。例えば、好適な設定（後述の速度補償方式は無視する）に対して、帯域１には６６番目ないし９２番目のＦＦＴ係数が含まれる。そのとき、上記した別の例に対して、ＦＦＴ係数は３２番目ないし９４番目であることになる。８０００Ｈｚのサンプリングレートを仮定して与えられるパターンベクトルの計算は、それに応じて調整される。
【００２６】
ビデオの場合には、パターンベクトルはビデオの各フレームの２次元ＦＦＴ変換から導かれる。ビデオフレームは音声におけるサンプルと類似していると考えられることができる。従って、ビデオフレーム全域で垂直及び水平ＦＦＴ係数を収集して各タイムフレームに対してパターンベクトルを作ることができ、タイムフレームは１群のビデオフレームを構成する。テレビプログラムのオーディオサウンドトラックの機能が同じプログラムのビデオ信号の機能と組み合わされてパターンベクトルを生成することができるのであるから、これらのアプローチは組み合わされることがあることを当業者は理解されよう。
【００２７】
３．データベース探索（Database Search：ＤＢＳ）モジュール
【００２８】
ＰＧモジュールによって生成される問い合わせを受け取ったら、このモジュール（３）は、既知のプログラムのパターンベクトルの順番を含むデータベースを探索することになる。一致が見つかったら、モジュールは、音声またはビデオプログラムの集合の識別情報に対応する登録番号の集合であって、そうでなければプログラムＩＤ、フレームＩＤ（フレーム番号とも呼ばれる）と呼ばれる集合及び一致が生じたこれらのプログラム内のタイムフレーム番号を戻す。データベースの探索が一致を見つけることができなかったら、ＤＢＳモジュールはＮＯ‐ＭＡＴＣＨＥＤフラグを発行することになる。ＤＢＳモジュールのための本発明の態様は、信号シグネチャ（パターンベクトル生成モジュールにおいて用いられる技法と異なる技法を用いて導かれるシグネチャさえも）を含む任意の種類のデータ集合に適用可能であると考えられる。
【００２９】
４．プログラム検出／識別（Program Detection and Identification：ＳＤＩ）モジュール
【００３０】
このモジュール（４）は、以下に更に述べるように、直近の連続するＮ個のタイムフレームについてＤＢＳからの一致する（マッチング）結果を常に監視する。好適実施形態において、Ｎは５に設定されるが、それより大きいかまたは小さい数が用いられることがあり、その場合、結果に差がある。任意の音声またはビデオプログラムが積極的に検出されたかどうかを決定するために２つの方式が用いられる。１つ目は、Ｎ間の一致するパターンベクトルの各スレッド内で、有効な順番を有するフレームの数がフレームのブロックの指定された過半数に合格するかどうかを決定する過半数票（多数決）方式である。２つ目は、潜在的なスレッドの各々を追って、当該スレッド内のいくつのフレームが有効な順番を構成するかを数えるフレーム順序付け（sequencing）方式である。大部分の隣接フレームがフレーム順序付け要件を満足するスレッドが存在するならば、当該スレッドにおいてプログラム（音声であろうとビデオであろうと）が検出されると考えられる。誤検出を抑制し、正確な検出を増やすためにいずれか一方または両方の方式が用いられる。好適実施形態においては、両方の方式が用いられる。ある１つの（または２以上の）プログラムが検出されると仮定すると、ＳＤＩモジュールは次の２つのモードを開始することになる。
１．識別モード：このモードでは、モジュールは、プログラムが検出された時間、検出がなされたプログラムに組み入れられた時間と共に、曲名、作詞家／作曲家、アーチスト、レコード会社、出版社、またはシステムの登録段階中に入力されるその他の情報を含む被検出プログラムの参照情報全てを記録する。この情報は、検出ログに登録されることになる。
２．トラッキングモード：このモードでは、モジュールは、後述するように、放送の新たなフレーム毎の問い合わせした結果が順序付け要件に従っているかどうかを監視することによって各被検出プログラムを追跡する。問い合わせした結果が順序付け要件と一致することができなくなるまでアルゴリズムはこのモードにロックされる。トラッキングモードから出た直後に、トラッキングの全期間を含む多くの検出属性及びトラッキングスコアが記録されることになる。
【００３１】
ＰＧモジュールによって生成されるパターンベクトルは、一致のためのデータベースの探索を行うためにＤＢＳモジュールに送られる。出力は、ＮＯ‐ＭＡＴＣＨＥＤフラグまたはライブラリパターンのプログラムＩＤ及びフレームＩＤのいずれかであるが、前者はＤＢＳが探索基準に合格するデータベース内のフレームを配置できないことを示し、後者は探索基準に合格する。
【００３２】
ＳＤＩモジュールは、ＤＢＳモジュールからの出力を収集し、新たな音声プログラムが存在するかどうかを検出する。もし存在するならば、検出された歌が識別される。図１は、音声の１フレームから検出後のその結果までのアルゴリズムのフローの図解である。ビデオへの本発明の適用に関しては、パターンベクトルが生成されてしまえば演算は似ている。ＳＤＩモジュールのための本発明の態様は、信号シグネチャ（パターンベクトル生成モジュールにおいて用いられる技法と異なる技法を用いて導かれるシグネチャさえも）を含む任意の種類のデータ集合に適用可能であると考えられる。
【００３３】
パターンベクトル生成
【００３４】
ＰＧモジュールは、好適には毎秒８，０００サンプルに設定されたサンプリングレートで、好適には１６，３８４個のサンプルから構成されるような、信号のフレームを読み込む。従って、フレーム長さは時間にして約２秒である。時間にしてそれ以上またはそれ以下のサンプルまたはフレーム幅が用いられることがあり、その場合、結果に差がある。
であり、ベクトルが信号のフレームを含み、各ｘｉがｎ番目の音声サンプルの値であるとすれば、Ｎ要素パターンベクトルは以下のステップで計算される。好適実施形態においては、Ｎは３１に等しい。Ｎの値は任意であり、増加または減少させることができ、その場合、結果に差があることを当業者は理解されよう。例えば、Ｎを小さくすると、計算時間及びメモリ所要量を減少させるが、精度を低下させることがある。Ｎを大きくすると、その逆になる。また、示されている方法では、本発明の説明を単純化するために３１要素パターンベクトルが計算に用いられていると仮定することになる。目標が正確度を上げることであるかまたはコンピュータの複雑さを低減することであるかによって、Ｎが増加または減少するとき、同じ方法論が使えることになることを当業者は理解されよう。
【００３５】
１．スペクトルベクトル
を得るために、フレーム中のサンプルの数に等しい点の数でｘのフーリエ変換を計算する。この変換のスペクトル分解能は、［８０００サンプル／秒］／［１６，３８４サンプル／秒］＝０．４８８Ｈｚである。
【００３６】
ＦＦＴスペクトル値を特定の幅の周波数帯域に分離する。好適実施形態において幅は６４Ｈｚである。本発明について説明を単純化するために好適実施形態の点から更に説明するが、特許請求の範囲に限定されるものではない。
【００３７】
帯域＃１は０から６４Ｈｚまでであり、帯域＃１にはＦＦＴ係数Ｘ１からＸ１３１までが含まれる。
【００３８】
帯域＃２は６４から１２８Ｈｚまでであり、帯域＃２にはＸ１３２からＸ２６２までが含まれる。以下同様である。
【００３９】
２．各帯域の重心（または質量中心ＣＯＧ）を次式により計算する。
【数１】
好適実施形態においては、帯域２から３２のみが用いられる。というのも、帯域１は、ＦＭラジオ放送では通常用いられない０Ｈｚを含む最も低い帯域であり、帯域３２は、典型的な例では音声のフィンガープリントを符号化するのに十分な帯域幅である１，８００Ｈｚまでの帯域をカバーするからである。当然のことながら、必要に応じてより高いまたは低い帯域が用いられる可能性がある。信号特性を把握するためのより高いまたは低い帯域の包含は、経験的に決定されることができる。第１のステップでは、ステップ２で重心を計算するためにＦＦＴ係数がされる収集されるが、第１のステップはビデオの場合において異なる。ビデオの場合には、ＦＦＴ係数は、ポイントン氏の文献の２３ページに記載されているように、複素平面中かまたは２次元空間の周波数平面上かいずれかの位置から選択されなければならない。ポイントン氏の文献は引用を以って本明細書の一部となす。これらの位置は、音声の場合の周波数帯域と類似している。音声において所定の周波数帯域を用いるのに似たやり方で、周波数領域における垂直／水平面上の所定の領域を画定することができ、各領域におけるＦＦＴ係数値を用いてその領域に対応する要素を計算することができる。この選択がなされると、同等の方法で重心を計算することができる。フレームレート、同期速度（sync rate）、副搬送波またはラインレートを含む周波数領域を無視することは有利である。最終的な結果は、音声の場合に本質的に等しい。即ち、ビデオの各タイムフレームが、データベースに格納される自身に関連するパターンベクトルを有することになる。
【００４０】
ステップ３の後で、３１要素ベクトル
が得られる。好適実施形態においては、更なるステップがｃを符号なし整数に変換する。符号なし形式が用いられるのは、ｃ中の全ての要素が（１，１３１）の間隔に肯定的であるためである。ｃの更なる計算は、１３１で割る除算を実行することによって各要素を正規化して０と１の間の値になるようにし、各帯域内のＦＦＴ成分の数は、
【数２】
である。好適実施形態において、各要素は、その後、記憶に便利なように、そして更なる処理のために、符号なし１６ビット整数形式に変換される。計算時間の下流（ダウンストリーム）を低減するために、各ＦＦＴ係数即ちｃｉが最小閾値に関連してテストされる。下流プロセスは、例えば、更なる計算のために収集された下流集合にこれらの要素を含まないことによって、これらの要素を無視するように設定される。図３にこのモジュールのフローチャートを示す。好適実施形態においては、ステップ１におけるＦＦＴ及びステップ３における重心（ＣＯＧ）計算の両方が倍精度浮動小数点命令を用いて一般的には計算される。
【００４１】
速度補償方式
【００４２】
種々の理由で放送プログラムは原型のプログラムの速度から多くの場合加速されることを当業者は理解されよう。したがって、検出される音声プログラムが登録段階中に供給される音声の速度と異なることがあるときに、自動音声プログラム検出システムがロバスト（robust）であることはクリティカルである。この問題を多少とも解決するために、パターンベクトル生成式の修正が用いられる。
【００４３】
（ａ）修正は、ステップ２の各帯域の異なる数のＦＦＴ成分（即ち帯域幅）を有するようにすることである。
【００４４】
（ｂ）好適実施形態において、パターンベクトル生成式の修正は、検出段階中に入ってくる放送音声信号にのみ適用され、音声プログラムの登録段階中に適用されるパターン生成プロセスには適用されない。上記したような検出段階に対して代わりの周波数帯域を使用することは、登録段階の間に交互に行われることができ、実質的に同じ結果が得られることを当業者は理解されよう。
【００４５】
この修正の具体的詳細を以下に述べる。
【００４６】
この式は、フーリエ変換のスケーリング特性に基づく。歌を時間加速したものは、原型を時間変換したものである。
このとき、α＞１であり、ここで、ａは加速率であり、ｘ（ｔ）は時間ｔでの検出されたサンプルである。ａ＞１の場合、時間軸は「圧縮」されることに留意されたい。歌が２％加速されたら、α＝１．０２となる。
【００４７】
スケーリング特性により、係数を用いてフーリエ変換の値を調整することができる。
従って、高速再生のスペクトル、即ち歌の加速バージョンが引き伸ばされる。２％の加速率では、歌の加速なしの１００Ｈｚでのフーリエ変換周波数成分は、加速後に１０２Ｈｚにシフトされる。このことが示唆することは、検出された歌に２％の加速率が存在すれば、ステップ２における帯域幅はそれに応じて１．０２×６４Ｈｚ＝６５．２８Ｈｚに調整されるべきであり、それゆえ各帯域内のＦＦＴ成分の数は１３１×１．０２の丸め（１３４に等しい）に調整されるべきであるということである。各帯域におけるＦＦＴ成分の量を計算する式は２つあり、両者ともＦＦＴ成分の元の数に基づくものであり、それは１３１に等しい。
【００４８】
式
【００４９】
（１）加速率ｒと仮定する。帯域＃１から開始する。帯域＃１はＦＦＴ係数ｘ１からｘｚ（１）を含み、ここでｚ（１）＝１３１×（１+ｒ）の丸めである。
【００５０】
（２）ｋ＝２から３２に対して各ｚ（ｋ）＝［ｚ（ｋ‐１）＋１３１×（１+ｒ）］の丸めを繰り返し計算する。帯域＃ｍは、ｘｚ（ｍ‐１）からｘｚ（ｍ）のＦＦＴ係数からなる。
【００５１】
（３）上記で計算した新たな帯域区画により、帯域＃２から＃３２まで重心（ＣＯＧ）を計算する。各重心（ＣＯＧ）を対応する帯域におけるＦＦＴ成分の数で割ることによって正規化を実行する。
【００５２】
補償あり及びなしの相違を図４及び図５に示す。図４は、原型の帯域設定が、原型とその加速変型間のパターンミスマッチをもたらすことを示す。図５は、加速率が既知であれば修正帯域設定が非常に良好なパターンマッチング挙動を与えることを示す。
【００５３】
ロバストベクトル生成式
【００５４】
上記したパターンベクトル生成式は、ロバストマッチングを与えるために更に改良されることができる。この改良は、前の公式化の代わりに用いられることもある。加速の別の効果は、周波数軸を伸縮させるほかに、帯域毎の周波数における限界のシフトである。改良は、帯域の幅を拡張することにより、再生速度に起因するシフトの量が帯域幅と比べて僅かな割合に納まるように帯域の限界のシフトを補償することである。従って、帯域位置が変えられない限りアルゴリズムの修正‐即ち、パターンベクトルとして重心を計算すること‐がない。修正帯域限界は、記憶パターンベクトルを作成するために登録プロセス中に用いられる。同じ性質を示す周波数帯域幅を計算するために、即ち再生速度変化による周波数シフトが比較的小さくなるように帯域幅を拡張し、そこでは再生速度変化による周波数シフトのパーセンテージが各周波数帯域幅のほんの僅かであるようにするために、幾つかの別法が用いられることがあることを当業者は理解されよう。更に、この技法が、周波数帯域へのＦＦＴ係数の分離に基づく信号においてシグネチャを計算する任意の方法の役に立つことになることが考えられる。この効果を示す修正帯域限界を計算する１つの方法を好適実施形態として後述する。
【００５５】
新たな帯域限界位置を計算するためのアルゴリズム
【００５６】
周波数領域における帯域番号ｋの開始及び終了インデックスをそれぞれ、ＦＦＴ係数のインデックスであるｓｋ，１、ｓｋ，２とする。例えば、インデックスｓｌ，１は１に等しく、０Ｈｚに対する第１のＦＦＴ係数に対応する。シフトが超過すべきでない帯域幅のパーセンテージで割ったパーセントで表される予想最大加速であるようなシフト対帯域幅比を仮定する。好適実施形態においてはこの値は５％であると仮定されるが、精度を上げるかまたは計算の複雑さを減らすために他の値が用いられることもある。
【００５７】
１．開始位置がｓ１，１＝１である帯域ｋ＝１から開始する。２％の加速を仮定すれば、位置は０．０２ないし１．０２だけシフトされるが、これは丸め後でも１に等しい。結果インデックスは整数でなければならないので、丸めが必要である。シフト対帯域幅比が帯域＃１の帯域幅の０．４（シフトが表すべき量、５％帯域幅で割った２％シフトである）に等しいと仮定すれば、終了位置ｓ１，２＝（１＋．０２／．０５）×ｓ１，１＝１．４、または丸め後には１である。
【００５８】
２．ここで、帯域＃２に対する１つの位置の計算に進む。開始位置ｓ２，１＝２である。２％のシフト及び５％のシフト対帯域幅比を仮定すると、ｓ２，２＝３が求められる。
【００５９】
３．全てのＦＦＴ成分が使い尽くされるまで繰り返しを続ける。好適実施形態においては、結果（３１．２５Ｈｚに対応する、より下位の帯域ｓｋ，１＜６４と、２，６８６Ｈｚに対応する、より上位の帯域ｓｋ，１＞５５００の両方）は、用いられない。
【００６０】
４．ｋが９に等しいとき、ｓ９，２＝６６であり、ｋ＝１０のとき、ｓ１０，１＝６７であり、以下同様である。各帯域のｋに沿った帯域幅がｋとともに指数関数的に増加するのでオーバフローを回避するため、好適実施形態は、ｋがｋ＝２２まで繰り返すとｓ２２，２＝５２９８になるようにｓ１０，１＝６６を任意に設定した。結果を表にまとめたものを表１に示す。
【００６１】
５．現時点での項目の数は１３でしかないが、各項目がパターンベクトルにおける特定の要素に対応する３１個の項目の合計が好ましい。帯域の第２のバッチは、ステップ３で得られた帯域それぞれの中間を取ることによって得られる。表２に示されるように追加の１２帯域が得られる。
【００６２】
６．現時点では２５の帯域がある。残りの６帯域は、２つの表を組み合わせることによって得られる。具体的には、両表において項目１と２が組み合わせられ、項目３と４が組み合わせられ、項目５と６が組み合わせられ、表３に示されるようにもう６つの項目が作成される。上記を組み合わせて、３１帯域の開始及び終了位置を表４に示す。
【００６３】
±２％の速度変化に対するロバスト性を示すために、信号のフレームに対するテスト結果を図６に示す。
【００６４】
加速補償（speedup compensation）とロバストな式の組合せ
【００６５】
周波数帯域限界を調整するための上記した２つの方法は、加速補償も組み入れられるのであれば、組み合わせられることができる。周波数スペクトルの拡張と加速の関係は、２つのアプローチを組み合わせるために利用される。ｋ番目のサブバンド、即ち開始及び終了位置＝［ｓｋ，１，ｓｋ，２］は、±２％の速度変化に対するロバスト性を有する。その後、各値に（１＋ｒ）を乗じる。ここで、ｒは［ｓｋ，１，ｓｋ，２］への加速量である。その後、上記した丸め法を行う。これにより新たなインデックス
が得られる。速度変化に対するこのインデックスのロバスト性は、ｒ±２％にシフトされる。本質的には、新たな表は先の表４であり、ここでは値に（１＋２％）を乗じてその後同じ丸め法を適用する。表４は、ここで、データベースライブラリを投入する既知の音声プログラムからパターンベクトルを作成するために登録段階中に用いられる。検出段階中に表５を用いて、以下に更に詳述するようにデータベースにおいて一致するデータ記録を見つけるためにＤＢＳモジュールにおいて用いられる検出された入ってくる放送からパターンベクトルを作成する。従って、両方法が組み合わされる。一例として、ｒ＝０．０２（２％）に設定し、表４のあらゆる帯域を処理し、表５に示されるように０〜４％の速度変化にロバストである新たなサブバンドの集合を計算する。
【００６６】
表５は、２％の加速補償で得られる。表４の表になっているものに２％加速補償後の新たな３１対の開始及び終了位置が加えられた。この結果は、放送からの検出された歌の処理によるものである。
【００６７】
補償は、方法を０から４％の加速バリエーションのロバスト性を有するように効果的に位置付ける。変化が０より上または下である、即ち再生を減速または加速するときに速度変化の効果を和らげるために同じアプローチを用いることができることを当業者は理解されよう。
【００６８】
データベース探索（ＤＢＳ）モジュール
【００６９】
データベース探索モジュールは、ＰＧモジュールから各フレームのパターンベクトルを獲得し、そのパターンベクトルを同じパターンベクトルを有するデータベース記録に一致させるためにデータベース質問を集める。データベース問い合わせとデータベースに格納されたパターンベクトル間の一致を決定するためにソフトマッチング（soft matching）方式が用いられる。対照的に、ハードマッチング（hard matching）方式は各問い合わせに対して多くても１つの一致項目を許容する。ソフトマッチング方式は、１つの問い合わせ当たり２つ以上の一致項目を許容し、一致があるところは、誤差閾値を満たすという意味ではパターンベクトルが問い合わせベクトルに十分近いところである。一致項目の数は、（ｉ）いくつかの最大量に制限されることができるかまたは（ｉｉ）問い合わせとデータベース項目間の最大許容誤差によって制限されることができるかいずれかである。いずれのアプローチが用いられてもよい。ソフトマッチング方式は、登録段階においてプログラムパターンがオーバサンプリングされているという事実に依存している。例えば、好適実施形態において、登録のために用いられるフレーム間距離は検出において用いられるものの１／４に過ぎない。従って、特定のプログラムのｍ番目のフレームが問い合わせへの良好な一致フレームであれば、（ｍ‐１）番目のフレーム及び（ｍ＋１）番目のフレームなどその隣接フレームも良好な一致になるであろうことが期待される。ソフトマッチング方式及び順番付け方式の協力は、放送環境に固有の可変信号条件に対する検出システムのロバスト性を強化する。
【００７０】
一致が見つかったら、データ記録における対応するプログラムＩＤ番号及びフレーム番号が戻される。図７のフローチャートは、ＤＢＳモジュールにおけるフローを示している。非常に大きなデータベースにおいて所与の公差内で一致する変数の位置を見つけるための変数の全域での探索は、ばか力式で行われるのであれば、潜在的に時間が掛かることを当業者は理解されよう。計算時間問題に取り組むために、２部（two part）探索を用いる。第１部においては、範囲探索方式が問い合わせのすぐ近傍の内でそれらの項目を選択する。第２部においては、第１部からの潜在的な候補に対する改良された探索を用いて問い合わせに最も近い候補の集合を選択する。
【００７１】
ステップについて以下に詳細に述べる。
【００７２】
１．検出段階中にＰＧモジュールによって生成されるパターンベクトルからの問い合わせを集める。
【００７３】
２．最近隣探索アルゴリズムを実行する。このアルゴリズムは２つの部からなる。第１部は、近似的な探索方法論を実行する。具体的には、範囲探索（range search：ＲＳ）方式は、データベースにおけるどの項目が問い合わせのすぐ近くにあるかを決定するために利用される。第２部は、細かな探索方法論を実行する。第１部からの結果を問い合わせへのそれらの距離に従ってソートする。探索アルゴリズムは、（ｉ）最良のＭ結果（問い合わせへの最短距離を有する点で）を戻すことができるか、または（ｉｉ）いくつかの特定の閾値以下の距離を有する全ての結果を戻すことができるかのいずれかである。いずれのアプローチが用いられてもよい。以下に詳述するように、最近隣アルゴリズムは、探索を実行するときにより良好な計算時間性能を提供する他のアルゴリズムに置き換えられることができる。
【００７４】
３．一致があれば、プログラムＩＤ番号及び対応するフレーム番号を出力する。複数の一致があれば、全てのプログラムＩＤ及び対応するフレーム番号を出力する。一致がなければ、ＮＯＭＡＴＣＨフラグを出力する。
【００７５】
範囲探索は公差内で一致するパターンベクトルを必要とするが、各々の場合に必ずしも完全な一致でなくてよい。幾何学的視点から、範囲探索は、寸法が公差パラメータによって決定される多角形内にどの集合の項目が含まれたかを識別する。好適実施形態において多角形は３１次元超立方体である。
【００７６】
範囲探索（ＲＳ）公式化
【００７７】
好適実施形態においては、パターンベクトルは１×３１ベクトル
である。ここで、ｃは、一致を捜したところで検出されたパターンベクトルである。帯域の数は、上記したように、３１より多いかまたは少ないことがあり、その場合、結果に差がある。そして、計算の複雑さに対する精度の増加が代償になる。探索アルゴリズムについて３１要素ベクトルを用いて説明するが、当業者であれば、これらの方法が任意のサイズのパターンベクトルに適用されることになることを理解されよう。パターンライブラリはＭ×３１行列であり、ここでＭはデータベースに格納されたパターンベクトルの合計数であり、３１はパターンベクトル中の要素の数を表す。Ｍは、以下に示すように潜在的に膨大な数である。データベース全体は次の行列Ａによって表されると仮定する。
【数３】
【００７８】
ライブラリに格納されたこれらのパターンベクトルは、ライブラリパターンベクトルと呼ばれる。好適実施形態において、各ベクトルｚは、検出段階中にその検出が考えられている既知の音声コンテントを有するような、登録段階中に計算される３１要素のパターンベクトルである。検出段階中に、識別の実行は、ライブラリパターンベクトル｛ｚ＿ｏｐｔ｝の集合を配置することであり、このようなベクトルは公差パラメータによって決定される超立方体内に入れられている。
【００７９】
探索基準は、
【数４】
となるように任意のｚ＊の識別として表すことができる。
【００８０】
好適実施形態においては、Ｌ１ノルムが用いられる。ここで、
【数５】
はｘのＬ１ノルムである。従って
【数６】
ここで、ｅｍ，ｎは、ｃとｚｍ間のｎ番目の点誤差（point error）と呼ばれる。
【００８１】
ＲＳアルゴリズムによるライブラリ全体に対するｚ＊の探索は、点誤差基準の満足度に基づく。即ち、各点誤差は幾分かの公差以下でなければならず、好適実施形態においては、一定量以下のＬ１ノルム以下でなければならない。各要素及びＬ１ノルムに対する公差が同じであるか異なることがあり、そのことが探索の効率を変えることを当業者は理解されよう。
【００８２】
公差の決定は、経験的に測定される誤差のいくつかの統計学的測定に基づく。更に、１次Ｌ１ノルム以外の他の測定誤差が用いられることがあることが認められる。探索問題は今や範囲探索問題になっているが、そのことについては先行文献の他の場所に記載されている。P. K. Agarwal, Range Search, in J. E. Goodman and J. O'Rourke, editors, HANDBOOK OFDISGRETE AND COMPUTATIONAL GEOMETRY, page 575-598, Boca Raton, NY, 1997, CRC Press を参照されたい。Ｃ＋＋コードは、Steve Skiena, The Algorithm Design Manual, published by Telos Pr, 1997, ISBN: 0387948600 からも入手可能である。
【００８３】
以下にｚ＊を決定する方法の各ステップを示す。
【００８４】
１）Ｌをライブラリパターンベクトルのインデックス全てを含むインデックス集合に等しい値に設定する。
【数７】
【００８５】
２）ｎ＝１から開始する。
【００８６】
３）ｃのｎ番目の要素から各ｚｍ，ｎのｎ番目の要素間のｅｍ，ｎを計算する。ここで、ｍは１ないしＭである。
【００８７】
４）ｎ番目の点誤差が特定の公差Ｔｎより小さいパターンベクトルのこれらのインデックスのみを含むようにＬを更新する。
【数８】
Ｔｎは任意に設定することができる。好適実施形態においてはＴｎをｃｎの値の１０％に設定する。
【００８８】
５）Ｌが空集合でありかつｎ＜３１であれば、このルーチンから出て、ＮＯＭＡＴＣＨフラグを発行する。この条件が満たされなければ（Else）、ｎ＝ｎ＋１に設定する。ｎ＞３１であれば、ステップ６に進む。この条件が満たされなければ、ステップ３に進む。
【００８９】
６）Ｌに記載された全てのパターンベクトルとｃの誤差を計算する。
【数９】
最良の解は、ｅｍの全てを調べることにより決定され、それによってｚ＊が得られることになる。或いは、ソフトマッチングのために、２つの基準のいずれかを用いることができる。
【００９０】
基準１：誤差がいくつかの所定の閾値ｅｍａｘ以下であるｚｍのみを選択する。
基準２：最良のＭ個の候補をＬから選択する。ここで、Ｍ個の候補は最小の誤差のサイズからＭ番目の誤差のサイズである。
【００９１】
最良のＬ１の一致を有するインデックスｍが決定されたら、このインデックスを用いてパターンベクトルｚｍに対応するデータ記録を回収する。その後、データベースモジュールはプログラムＩＤ及び対応するフレーム番号を出力として出力する。
【００９２】
ｎ番目の繰り返しの開始時には、インデックス集合Ｌは、ｍ＝１からｎ‐１までの点誤差が公差テストに合格するようなライブラリパターンベクトルのインデックスを含むことに留意されたい。ｎ番目の繰り返しの開始時には、インデックス集合Ｌは
【数１０】
である。
【００９３】
ＲＳアルゴリズムのフローチャートを図８に示す。
【００９４】
３０，０００曲の歌に対して音声プログラムへの本発明の適用のためのライブラリサイズＭは数千万のオーダーであることが予測される。計算を以下に示す。
歌の数＝３０，０００
代表的な歌の長さ＝２０４秒（３分２４秒）
サンプリングレート＝８，０００サンプル／秒
フレームサイズ＝１６，３８４サンプル
フレーム間距離＝４，０００サンプル
【００９５】
歌１曲当たりのフレームの数は、歌の長さと１秒当たりのサンプルの数とを乗じた積からフレームサイズを引き、それをフレーム間距離で割ったものである。好適実施形態においては、約４０４フレームがある。３０，０００曲の歌では、Ｍ＝１２，１１７，１２０である。
【００９６】
この数字に対して、第１の繰り返しは、インデックス集合Ｌを更新するための分岐文の実行及び約１２００万の減算を必要とする。次の繰り返しはおそらくより少なくなるが、それでも数百万のオーダーにあることになる。また、メモリは、公差テストに必要な減算の結果全ての中間値を保持するように割り当てられなければならない。
【００９７】
高速範囲探索アルゴリズム
【００９８】
ｚ＊を見つけるために実行されなければならない減算の量を最小にする方法の改良がある。そして更に重要なことには、実行時間は、データベースのサイズほど速くは拡大しない。このことは、このサイズのデータベースには特に重要である。この性能強化は、大量のメモリの使用を犠牲にして達成される。しかし、コンピュータメモリのコストは歴史的に見ると連続して減少してきているので、これはここでは妥当なトレードオフであることを当業者は理解されよう。ＲＳアルゴリズムへの修正は、正確な誤差値を計算するよりむしろ指標付けを用いることである。この修正については、以下に更に説明する。
【００９９】
検出されたパターンベクトルとデータベースに保持されたパターンベクトル間の最良の一致（ベストマッチ）を回収するための改良された探索方法論は、ここでは高速範囲探索アルゴリズムと呼ばれる。前述同様に、Ａは、Ｍ行のパターンベクトルから構成されるライブラリ行列である。
【数３】
【０１００】
各行は、特定のパターンベクトルである。全部でＭ個のパターンベクトルがあり、好適実施形態においてはそれぞれが３１個の要素を有する。
【０１０１】
ステップ
【０１０２】
１．Ａの各個々の列を次のように分離する。
【数１１】
【０１０３】
２．列における要素の各々を昇順でソートする。
【数１２】
【０１０４】
３．ソートした結果、各要素ｚｍ，ｋを
にマッピングする。２つの相互参照表を作成する。表Ｒｋは、
のマッピングであり、表Ｔｋは、全てのｋ＝１〜３１に対して
をマッピングする。
【０１０５】
当業者は、ソーティング（分類）及び表作成が、登録の後であるが検出段階中のいずれかの一致の探索よりは前に行われることがあることを理解されよう。登録段階中にパターンベクトルを予めソートしてしまうことにより、システムは検出段階中の探索時間を短縮する。検出段階中に、方法は、後述するように、ソートされたベクトルを探索することから始める。
【０１０６】
インデックス探索
【０１０７】
問い合わせベクトル
及び公差ベクトル
と仮定する。公差内に収まるこれらの要素のインデックスを抽出するために二分探索法が用いられることがある。他の探索法が用いられることもあるが、ｌｏｇ（Ｍ）時間で実行する二分探索が好ましい。
【０１０８】
ステップ：
【０１０９】
１．ｋ＝１に設定する。
【０１１０】
２．二分探索を行い、
が１〜Ｍであるとき、ソートされた列ｋ、即ち
に、ｃｋ‐Ｔｋに最も近くかつｃｋ‐Ｔｋに等しいかまたはそれより大きい要素
を配置する。その後、再び二分探索を実行し、ｃｋ＋Ｔｋに最も近くかつｃｋ＋Ｔｋに等しいかまたはそれより小さい要素
を配置する。従って、集合
における全ての要素は公差要件を満たす。このように、二分探索を２回用いてｋ番目の列毎に
及び
を配置する。
【０１１１】
更に、仮に
が、公差要件を満足するような
全てのインデックスを含むインデックス集合である、即ち、
【数１３】
であるとする。
【０１１２】
３．ｋ＝ｋ＋１。ｋ＞３１であれば次のステップに進む。
【０１１３】
或いは、プロセスは、どの列がテストに合格する帯域の最小の番号を有するかを計算することができ、次のステップにおける帯域の当該番号から始めることができる。対応する帯域の番号が最小から最大へ向かうソートされたｋ値を昇順に並べることによって、結果はｋにわたる単純な増分の繰り返しより速く収束することができる。
【０１１４】
４．各上下限
（ｋ＝１〜３１）を求めるためにステップ２及び３をｋ＝３２まで繰り返し、このように３１個の
を決定する。
【０１１５】
各Ｐｋは独立して求められる。全てのｋに対し、Ｔｋを用いて、上下限
（ｋ＝１〜３１）内に入っているインデックス全てを原インデックスに再度変換することができる。その後、３１のインデックス集合に論理積（ＡＮＤ）演算を実行する。
【０１１６】
代わりの方法は、最初の２つのインデックス集合を積演算し、次にその結果を第３のインデックス集合と積演算し、最後のインデックス集合を積演算し、終わるまで以下同様にすることである。これは、以下に概説するアプローチである。
【０１１７】
５．ｋ＝１にリセットする。
【０１１８】
６．
における全てのインデックスを検索し、アレイＲに格納する。
【０１１９】
７．表Ｔｋを用いてＲにおける全てのインデックスを原インデックスに変換する。
全てのインデックスｍを集合Ｓに格納する。
表Ｒｋ+１を用いてｍを
に変換する（従って列１において表されるインデックスは列２における表現に翻訳される）。その後、結果が
の上下限内にあるかどうかを調べるためにテストする。
公差テストを適用し、
【数１４】
を生成する。このように、各連続する
は、先の
から、ｋ番目の要素に対する公差テストに合格しなかったそれらのインデックスを減じたものになることになる。従って、ステップ６においてｋ＝３０であるとき、
は３１の公差テスト全てを満たすインデックスである。
【０１２０】
８．ｋ＝ｋ＋１
【０１２１】
９．ステップ６に進み、ｋ＝３１までループする。
【０１２２】
１０．ここで、集合Ｓは３１の積演算ループ後の原インデックス全てである。Ｓが空であれば、ＮＯＭＡＴＣＨフラグを発行する。そうでなければ、ハードマッチングの場合、次に、例えば最も近い候補であり得る唯ひとつの勝ち残ったものを配置する。ソフトマッチングの場合、次に条件を満たす項目全てを求める。
【０１２３】
高速ＲＳアルゴリズムへの更なる速度増加
【０１２４】
ｋ＝１から始める代わりにステップ４から開始し、次にｋ＝２、次にｋ＝３、のように最後まで行い、各列における候補の合計数を測定することができる。各列における候補の合計数は、各
における候補の合計数に等しい。次に、テストされる最初のｋが
が最も少ない候補を有するようなものであり、全てのｋがテストされるまで以下同様であるようにｋの順序を変えることができる。このとき、積演算の順序は、候補の最小の番号を有する列から開始する。最終的な結果は、同じ３１のインデックス集合を、連続的にｋを増分させて積演算するのと同じであるが、再順序付けられたｋを昇順にすることによって、積演算の数は減るので、探索を加速する。
【０１２５】
探索ブースタ：
【０１２６】
現行の探索技法が一般的に周波数帯域方式によって周波数帯域を探索することを当業者は理解されよう。好適実施形態を用いた実証研究は、探索の最初の繰り返しによりデータベースにおける項目の６０％ないし９０％が当該周波数帯域に対してフィルタを通過することを示している。歌１曲当たり３００項目を有する６，０００の曲名のデータベースを仮定すると、探索される項目の合計数は１，８００，０００である。戻りが６０％であれば、システムは最初の積演算後に１００万以上の項目を取り扱わなければならない。最初の積演算のサイズがより小さければ、１つの探索結果に収束する必要がある繰り返しの数を減らすことができる。プロセスの最初の繰り返しにおいて探索結果の数を減らすように探索を予め処理することは、本発明（ここではブースタと呼ばれる）の別の目的である。
【０１２７】
ブースタは、２つ以上の周波数帯域をひとまとめにできるように異なる指標付け方式を用いる。ブースタを用いて、ブースタにおける単一の探索ループは範囲探索法における多重ループに等しく、それゆえに探索速度は向上した。順位方式を用いて、積演算インデックスのための探索の数を最小にするために探索の順序を決定する。この順位を確立するために、正規の範囲探索プロセス中に各帯域における戻りパーセンタイルの最大、平均及び標準偏差が計算される。これらの実証検証の結果は、ブースタプロセスを用いてどの帯域がひとまとまりになることになるかを選択するために用いられる。
【０１２８】
ブースタ指標付け方式は、２進１０進変換の拡張であり、２進値要素のベクトルは１０進の整数に変換される。拡張は単純である。具体的には、サイズＮのベクトル
の基数がＭであれば（ここでＭは整数である）、変換式は次の通りである。
【数１５】
【０１２９】
式１による変換は逆にもでき、式１を用いて
を
に変換することができることに留意されたい。従って、変換は、あらゆる固有の整数
が固有の
から計算されるように一対一の関係を有する。好適実施形態においては、パターンベクトルを収容するデータベース、パターン要素の各々は１６ビットの符号なし整数として記憶される。このことは、各パターンベクトルをＭ＝６５５３６及びＮ＝３１のコードベクトルと考えることができ、固有の
を各パターンベクトルから計算することができることを暗に意味している。この変換の結果として、パターンベクトルの多次元空間は１次元空間にマッピングされる。他では公差要件と呼ばれここではギャップ要件と呼ばれる問い合わせベクトル
からの必要な距離内にあるパターンベクトルの探索は、ギャップ要件
が満たされるようにデータベースにおいて全ての項目
を配置することである。符号化が１６ビットであるような好適実施形態においては、Ｑ＝１０％×６４Ｋ＝６５５４になるように公差Ｔｋは１６ビットの範囲の１０％である。実際には、値６，０００が用いられる。ブースタは、各帯域におけるギャップ要件（他では公差要件と呼ばれる）を
における対応するギャップ要件にマッピングする。探索は次に、全てのギャップ要件を満たす全ての項目を反復して選び出すことができるが、このアプローチの大きな問題は、複数のギャップ要件が
に複数の互いに素のセグメントをもたらすことである。具体的には、
における条件を満たす項目の識別のために３１回の繰り返しが必要であり、ここで
は
に変換され、第１のループは帯域１のためのものであり、３１番目のループは帯域３１のためのものである。パターンベクトルにおける帯域の数を変えることによって、繰り返しの数は変化することになるが、アプローチの実体は同じであることを当業者は理解されよう。
【０１３０】
技術的な問題を回避するために、２つの妥協がなされる。第１に、周波数帯域の部分集合のみが選択されてブースタに含められる、即ち、部分集合中のこれらのインデックスのみが式１を用いて符号化される。第２に、より小さな基数が用いられる。第１の妥協は、繰返しループの数、即ち具体的には互いに素のセグメントの数を減少させるので、ＣＰＵ速度の点から見ると全てのセグメントでの探索が実際的である。第２の妥協は、メモリ所要量を削減し、更に重要なことには、それは（僅かな量のＲＡＭだけで）ブースタの探索結果をハードコーディングしてブースタ内での探索を非常に高速にすることを可能にする。好適実施形態に対するプロセスについては以下に詳述する。
【０１３１】
１．基数Ｎ＝３１に設定する。
【０１３２】
２．３１帯域から３帯域を選択する。選択する帯域はそれより多くても少なくてもよい。しかし、数Ｎに比べて大きな数を選択するのであれば、ブースタ法はより遅くなり、その有用性はより制限される。小さすぎる場合には、十分に正確ではなく、加速もしない。よって、最適数は経験的に決定される。Ｎ＝３１であるような好適実施形態においては、３１から３を選択する。
【０１３３】
３．この組合せの結果は以下の通りである。
【０１３４】
（ａ）当該新たなインデックスのダイナミックレンジが０ないし３２７６７である。従って新たなインデックス各々は２バイトに符号化されることができる。
【０１３５】
（ｂ）探索結果のハードコーディング：３２７６８個のビン即ちビン０からビン３２７６７を作成する。ビンｍは、変換後に３帯域要素が値ｍをもたらすような全てのライブラリパターンベクトルのインデックスを保持する。
【０１３６】
４．探索方法論：
【０１３７】
（ａ）問い合わせベクトル
と仮定する。
【０１３８】
（ｂ）３つの特定の帯域において要素を選び出す。
【０１３９】
（ｃ）これら３つの帯域を用いて問い合わせベクトルを、式１を用いる数に変換する。
【０１４０】
（ｄ）変換された問い合わせと変換されたライブラリパターンベクトル間のｍ値の最も近い一致を探すことによって３つの特定の帯域においてギャップ要件を満たすライブラリベクトルのインデックス全てを収集する。
【０１４１】
（ｅ）（ｄ）のインデックスを出力に渡し、上記した帯域毎の（band-by-band）探索をこれらのインデックス集合上で再開する。
【０１４２】
式１を用いたライブラリパターンベクトルの変換がランタイム計算負荷を減らすために演算前に行われ得ることを当業者は理解されよう。
【０１４３】
Ｄ．歌検出／識別（Song Detection and Identification：ＳＤＩ）モジュール
【０１４４】
ＳＤＩモジュールは、ＤＢＳモジュールの結果を獲得し、その後音声またはビデオプログラムの同一性の最終確認を与える。ＳＤＩモジュールには、次の２つのルーチンが含まれる。
【０１４５】
１．検出‐検出される歌番号の規則性のフィルタリング
【０１４６】
ＤＢＳモジュールが、連続したフレームの集合上に異なるプログラムＩＤ番号を戻すときには、不規則な一致は、プログラムが全く検出されない良好なしるしである。対照的に、ＤＢＳモジュールが、連続したフレームの集合上に同一の歌番号を一貫して戻すときには、一貫性のある戻りはプログラムが首尾よく検出されることを示す。
【０１４７】
一貫性のある戻りを検出する一方で不規則な戻りを抑制するために「過半数の原則（majority vote rule）」に基づく単純なアルゴリズムが用いられる。ＤＢＳモジュールが、検出されたプログラムまたは歌のｉ番目のフレームに対する特定のプログラムＩＤ及びフレームＩＤを出力すると仮定する。不規則な戻りのせいで、結果のプログラムＩＤは、最初はフレームにおける有効なプログラム識別と考えられることにはならない。その代わり、システムは、ｉ，ｉ＋１，ｉ＋２，・・・，ｉ＋２Ｋ（好適実施形態においてＫは２から４の間に設定される）の隣接フレーム（即ち重複しないフレーム）の結果を考慮する。これら（２Ｋ＋１）個のフレームに過半数を獲得したもの（majority winner）がなければ、システムはｉ番目のフレームにおけるヌル検出を示すために歌番号＝０を発行することになる。過半数を獲得したものがあれば、即ち、フレームｉに隣接する少なくとも（Ｋ＋１）個のフレームが同一プログラムＩＤ番号を生成したら、システムはｉ番目のフレームに対して検出された歌番号をそのような過半数を獲得したプログラムＩＤ番号として発行することになる。過半数の計算は多くのやり方でなされることができ、例えば、過半数を獲得した閾値がＫ＋１より大きくかつ２Ｋ＋１より小さいかまたは２Ｋ＋１に等しい値であり、２Ｋ＋１の閾値が全会一致（unanimous vote）を構成することになるようなより強力なテストを適用することは、ある用途において有利であることがあることを当業者は理解されよう。これは、より多くの未検出の結果を潜在的に犠牲にして誤検出を減らす。ここでの目的のために、過半数は、これらの二者択一の閾値を含むように画定されることになっている。計算速度に対して、好適実施形態はメディアンフィルタを用いて過半数を決定する。ずらりと並んだ２Ｋ＋１個の数の中央値は、
Ｋ＝１，２，．．．のとき、Ｚがソートされた後のＫ番目の項目である。例えば、Ｚ＝［１，９９，１００］であれば、Ｚの中央値は９９である。そのような計算のための式について以下に述べる。
【０１４８】
ＤＢＳモジュールはｎ番目のフレームに対してプログラムＩＤ＃［ｎ］を戻すと仮定する。フレームｉに対する中央値を計算するために、
とする。次に、
とする。ここで、
である。このとき、検出された結果はｘ掛けるｙの掛け算である。この式の主な特徴は、それがループ及びカウンタを必要とする具現化よりもむしろワンパスに具現化されることができることである。
【０１４９】
２．プログラムの識別
【０１５０】
上記したような過半数の原則を用いて検出音声またはビデオプログラムがされると仮定すると、次のステップは追加の検証テストを課して、検出されている歌のフレーム同期があるかどうかを決定することである。具体的には、フレーム同期テストは、各ｐ番目のフレームに対してＤＢＳモジュールにより出力されたフレームＩＤ番号が経時的に即ちｐの増加につれて単調に増加する単調増加関数であることをチェックする。そうでなければ、即ちフレームインデックスがランダムであれば、検出は無効を宣言される。以下に示すのは、完全なＳＤＩの段階的方法である。プログラムの一部が繰り返されている場合には、例えば、毎回プログラムに編集されることがある歌のコーラスにおいて、そうでなければ実質的に同一であるがタイムフレームが異なるパターンベクトルは、ＤＢＳモジュールによって見つけられることになる。このような場合には、システムはこれらの結果をバッファに格納することによって保有し、後述する順番付けテストを受けさせる。順番付けテストが進むにつれて、これらの暫定的な結果のいくつかは、順番付けテスト下で無効であると考えられかつその後に無視されることになるタイムフレームインデックスを有することになる。単一の暫定的なスレッドが残ったら、次に検出の開始及び停止時間が更新される。
【０１５１】
ＳＤＩアルゴリズム及びステップ
【０１５２】
ｓｐを、ｐ番目のブロードキャストフレームが検出された後に直近２Ｋ＋１個のプログラムＩＤを保持する構造であるとしよう。
【数１６】
【０１５３】
ここで、ｓｍ，ｎ＝ＤＢＳモジュールによってｍ番目のブロードキャストフレーム中に検出されるｎ番目のプログラムＩＤである。Ｐｍはビンのサイズであることに留意されたい。一般的に、ｍが異なればＰｍは異なる。
【０１５４】
同様に、ｆｐは対応するフレーム番号またはフレームインデックスを保持する別の構造である。
【数１７】
ここで、ｆｍ，ｎ＝ｓｍ，ｎの対応するフレームインデックスである。
【０１５５】
また、ＳＩ＝過半数票テスト及び順序付けテストの条件がうまく満たされるように首尾よく検出された最後の歌またはプログラムのプログラムＩＤである。新たなまたは異なる歌またはプログラムが検出されるまでこの結果を保持するためにレジスタが作成される。
【０１５６】
ステップ：
【０１５７】
１．ｓｐの過半数を計算する。ｓｐの１番目のビンにおけるプログラム１つ１つを参照と考える。残りの２Ｋ個のビンをスキャンし、１番目のビンにおける任意のプログラムが過半数要件に合格するか決定する。
Ｄｐ＝過半数要件に合格するｓｐの１番目のビンにおける項目のインデックスであり、１番目のビンにおける全てのプログラムが過半数要件を満たしていなければＤｐ＝０である。
【０１５８】
２．ｗｐ＝０であれば、ｐ＝ｐ＋１とし、ステップ１に進む。上記を満足せず（Elseif）、ｗｐが単集合（１要素の集合を意味する）であり、０に等しくなければ、ＳＩ＝ｗｐに設定する。ステップ３に進む。上記をいずれをも満足せず、ｗｐが２つ以上の候補を有するのであれば、ＳＩ＝ｗｐ（複数のプログラム一致がある場合）に設定する。ステップ３に進む。ｗｐのｓｐ，ｍ毎にステップ３〜７を実行する。
【０１５９】
３．Ｄｐにおけるあらゆるｓｐ，ｍに対して、ｆｐにおける対応するフレームから行列Ａを形成する。
【数１８】
ここで、ｆｔはｆｐのｔ番目のビンにおけるフレームである。ｓｐ，ｍの一部であるｔ番目のビンにフレームがなければ、ｆｔ＝０である。
【０１６０】
４．ｆｑ＝０であればｑ番目の行をなくして、Ａの圧縮を行う。
【数１９】
【０１６１】
５．以下のステップで行を取り除くことによってＡを整理する。
【０１６２】
Ａ．ｎ＝１から開始する。
【０１６３】
Ｂ．
【数２０】
及び
【数２１】
を計算する。ミスマッチのプログラムＩＤを有する項目全てを取り除くことによってステップ５を実行した後、このステップは順序付けに正しく従う項目のみを識別する。
【０１６４】
Ｃ．ここで、量ｄ１は、Ｂにおける２つの被検出フレーム間のフレームのオフセットである。この量は、ｄ１値にサンプルにおけるフレーム間距離を乗じて１秒当たりのサンプルで割ることによって実際の時間オフセットに変換することもできる。量ｄ２は、２つのブロードキャストフレーム間のフレームオフセットである。ここで、ｄは２つのオフセットの比であり、検出された順序の向上率（advance rate）を表す。具体的には、好適実施形態において、システムは、ｄ値として理想の向上率４を期待する。しかし、ｄに対する融通が利く制約が適用される。その制約とは即ち［ｄ１∈（４［ｄ２‐１］＋２，４［ｄ２‐１］＋６）］であれば、２つのフレームは正しい並び順にあるという制約である。従って、ｄ２＝１では、同じプログラムＩＤを有する２つの隣接放送フレーム間で２から６フレームのオフセットが期待される。ｄ２＝２であれば、オフセットは２＋４から６＋４フレームである。従って、この範囲は、範囲における４つのフレームの追加オフセットを除いて同じである。２及び６の値は、理想値４を中心とした範囲である。１つの値に代わる範囲は、オフセットが厳格であるよりむしろ少し融通が利くことを可能にする。融通性を狭くするように、３から５の範囲を選択することができる。同じようにして、範囲を１から７までにして融通性を非常に広くすることも可能である。ステップＤに進む。そうでなければ、Ｂにおける全ての項目にわたり順番付けるために、ｎ＝ｎ＋１。ｎ＜Ｎであれば、ステップＣに進む。そうでなければ、ステップＤに進む。
【０１６５】
Ｄ．行列Ｃが戻される。Ｃ中のどの行もみな、順序付け要件を満たす項目から構成される。
【０１６６】
順序付け要件と合わない行を削除することによりＢを圧縮する。更に、Ｂの第１の項目を参照と考えることにより、第２の項目が順序付け要件を満たしていなければ、プロセスは第３の項目にジャンプしてそれが第１の項目で順序付け要件を満たしているかどうかを確かめることができることに留意されたい。第２の項目が要件を満たしていれば、この第２の項目は第３の項目のための参照になる。
【数２２】
【０１６７】
ここで再び過半数要件を強制する。Ｃにおける項目の数が過半数要件を満たしていなければ、項目ｓｐ，ｍは更なるテストを受ける資格がなく、ステップ３に戻ってＤｐにおける次の項目をテストする。そうでなければ続いてステップ６へ進む。
【０１６８】
過半数テストを再度適用する。なぜならば、ステップ５の過半数テストに合格したとしても、順序付けの原則の要件を用いて結果を整理した後には過半数テストに合格しないことがあるからである。修正過半数テストに合格したら、そのときには新たなプログラムまたは歌が積極的に検出されているか、そうでなければ何も検出されない。
【０１６９】
６．ｓ＝Ｃにおける項目（即ち行）の数としよう。ｓ＜Ｋであればステップ９に進む。そうでなければ回帰分析を行う。
【０１７０】
Ａ．
及び
がそれぞれＣの第１および第２列であるとしよう。ここで、上添字Ｔは転置行列であることを示す。回帰分析のために次の行列を作成する。回帰分析を用いて、フレームＩＤ番号の順序付けの線形性の尺度を計算する。
【０１７１】
Ｂ．傾き及び切片の両方を計算する
【０１７２】
Ｃ．Ｃの相関係数ｒも計算する。
【０１７３】
７．［ｒ＞０．９かつ傾き≧２かつ傾き≦６］であれば、項目ｓｐ，ｍに関連するスレッドは、全てのテストに合格し、トラッキングモードへの有効な項目である。項目ｓｐ，ｍ及び対応するスレッドをFinal＿Listと呼ばれるレジスタに格納する。
【０１７４】
この条件が満たされなければ、項目ｓｐ，ｍをなくす。
【０１７５】
Ｄｐにおける次の項目のテストを続ける。
【０１７６】
８．トラッキングモードに入る。Final＿listにおける各スレッドは、集合的にまたは個別にのいずれかで追跡されることになる。
【０１７７】
９．トラッキングモードを開始する。
【０１７８】
Ａ．トラッキングに用いられる小さなデータベースを作成する。
【０１７９】
ｉ．集合的トラッキングモードにおいては、小さなデータベースはFinal＿listにおける条件を満たす項目全てのパターンベクトル全てを含む。
【０１８０】
ｉｉ．個別トラッキングモードにおいては、各特定の項目Final＿listのためのパターンベクトルだけを含む専用データベースが当該項目のために作成される。
【０１８１】
Ｂ．トラッキングモード＝集合的トラッキングであれば、
【０１８２】
ｉ．ｐ＝ｐ＋１。
【０１８３】
ｉｉ．放送の（ｐ＋１）番目のフレームに検出を実行する。
【０１８４】
ｉｉｉ．各スレッドの順番を更新する。スレッドが順序付け要件を満足するかを観察することによって各スレッドのメリットを監視する。
【０１８５】
ｉｖ．順序付け要件を満足する少なくとも１つのスレッドが存在するのであれば、ステップｉに戻り、トラッキングを続ける。そうでなければトラッキングを出る。
【０１８６】
トラッキングモード＝個別トラッキングであれば、各スレッドのための専用データベースをトラッキングに用いる。ステップは集合的トラッキングのステップと同じである。
【０１８７】
ここでの順序付け要件は、ステップ５ｃで用いられているものと同じである。即ち、新たなブロードキャストフレームに対する被検出フレームのＩＤが単調増加様式であり、好適実施形態においては放送の連続するフレーム間の量の増加が２から６の間であることが期待できる。
【０１８８】
追跡されている任意のスレッドに対して、当該新たな放送が以前のフレームに対して順序付け要件を満たしていなかったならば、公差手段が実施される。即ち、各追跡は、せいぜいＱ回までの失敗を有することができる。ここで、Ｑ＝０，１，２，・・・である。Ｑ＝０であれば、順序付け要件を満たしていないことは容認されない。
【０１８９】
Ｃ．トラッキングモードが終わった後、各スレッドのメリットを調べる。最高スコアを有するスレッドが、Final＿listにおける全スレッド中の勝ちスレッドである。
【０１９０】
ｉ．スコアは、放送の対応するフレームへのスレッドにおける各フレーム間の誤差に基づき、またはスレッドの持続時間に基づき計算することができる。あるいはその両方に基づいて計算することができる。好適実施形態においては、持続時間は各スレッドのトラッキングスコアと考えられる。トラッキング期間内に最長のものを持つものは勝ち（winner）スレッドである。
【０１９１】
Ｄ．複数のプログラムがステップ２においてＳＩを通知されていれば、勝ちスレッドのプログラムＩＤによって通知を補正する。
【０１９２】
１０．放送からのｐ番目のフレームを待つ。ステップ１に戻る。
【０１９３】
連続的なフレームＩＤの直線性をテストするためにステップ６において用いられる値は、テストが条件を満たすのをより容易にするかまたはより困難にするかいずれかのために変更されることがあることを当業者は理解されよう。これは、検出なしに比べて正しい識別の数を増加または減少させる一方で、結果が誤検出を増加させるかまたは誤検出を抑制するかどうかを制御する。
【０１９４】
本発明について詳細に説明及び図示してきたが、これらは例証及び例示を目的としたものであり、何らかの限定として捉えられるべきものではないことは明確に理解されるであろう。本発明の種々の特徴は、明確にするために別々の実施形態との関連で説明されているものがあるが、１つの実施形態に組み合わせて与えられることもあることが理解されよう。逆に、本発明の種々の特徴は、簡潔にするために１つの実施形態との関連で説明されているものがあるが、別々に、または適切に組み合わせて与えられることもある。付録に記載の特定の実施形態が、本発明の非常に詳細な開示を提供することだけを意図し、何らかの制限を加える意図ではないことは理解されよう。本発明のソフトウエア構成要素のいずれもが、必要に応じて、ＲＯＭ（読出し専用メモリ）形式で具現化されるか、ＣＤ‐ＲＯＭ、磁気媒体を含む任意の種類のコンピュータ読取り可能媒体に格納されるか、コンピュータメモリに格納されたデジタルデータファイルとして伝送されることがあることが分かる。ソフトウエア構成要素は、一般的に、必要に応じて慣用技術を用いてハードウエアに具現化され得る。
【０１９５】
本発明の精神及び範囲は、特許請求の範囲の条件によってのみ限定されるものである。
【表１】
【表２】
【表３】
【表４】
【表５】
【図面の簡単な説明】
【０１９６】
【図１】メディア放送監視システムの構成要素
【図２】音声プログラムの一連のフレームからプログラムの同一性の検出までの検出アルゴリズムのデータフローの図示である。
【図３】パターン生成モジュールのフローチャートである。
【図４】原型の周波数帯域限界が如何に原型フレームシグネチャとより高速で再生される同一音声プログラムのシグネチャ間のパターンミスマッチをもたらすかの例。
【図５】周波数帯域限界の変更が如何に原型の音声プログラムと高速及び低速で再生される同一音声プログラムのフレームシグネチャ間の改良された一致を与えるかの例。
【図６】新たな周波数帯域限界設定は、音声プログラムにおける±２％の速度変化変化があってでも音声検出アルゴリズムのロバスト性をもたらすことを示す。
【図７】ＤＢＳ動作フローの概略である。
【図８】ＳＲＲアルゴリズムのフローチャートである。
【特許請求の範囲】
【請求項１】
既知の信号に関連するシグネチャを生成するデジタル信号処理システムによって実行される方法であって、前記シグネチャが少なくとも１つの要素の数値の集合から構成されかつ少なくとも信号のタイムフレームに対応し、そのような既知の信号が識別インデックスによって識別され、そのようなタイムフレームがタイムフレームインデックスによって識別される該方法が、
前記信号の前記少なくとも１つのタイムフレームを、そのようなタイムフレームに対して所定の幅の少なくとも１つの周波数帯域にグループ分けされた所定の数の周波数絶対値があるように周波数領域に変換する過程と、
各周波数帯域に対して、前記周波数帯域内にグループ分けされた前記周波数絶対値の所定の関数に等しい１つの数値を計算する過程と、
前記シグネチャをその対応するタイムフレームインデックス及び前記識別インデックスに関連してコンピュータデータベースに格納する過程とを含むことを特徴とする方法。
【請求項２】
前記所定の関数が、（ｉ）一次結合、（ｉｉ）二次関数、（ｉｉｉ）重心、（ｉｖ）分散、または（ｖ）ｎ次モーメントのいずれかによって構成され、ｎが所定の数であることを特徴とする請求項１に記載の方法。
【請求項３】
前記関数結果を前記対応する周波数帯域における前記所定の数の周波数絶対値で割る過程を更に含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記関数が一次結合であり、前記一次結合の各項の前記係数が、前記周波数帯域内の前記周波数絶対値の序数インデックスを所定の定数で割ったものに実質的に等しいことを特徴とする請求項１に記載の方法。
【請求項５】
所定の周波数帯域の前記数が、１０ないし１００であることを特徴とする請求項１に記載の方法。
【請求項６】
前記周波数帯域が、０Ｈｚより上でかつおおよそ４０００Ｈｚに等しいかそれ以下の範囲を占めることを特徴とする請求項１に記載の方法。
【請求項７】
前記所定の定数が、前記対応する周波数帯域における前記周波数絶対値の合計に実質的に等しいことを特徴とする請求項４に記載の方法。
【請求項８】
前記関数結果を、前記対応する周波数帯域における前記所定の数の周波数絶対値で割る過程を更に含むことを特徴とする請求項７に記載の方法。
【請求項９】
周波数帯域の前記幅が、前記既知の信号の前記再生速度における所定の最大変化量に起因する前記周波数シフトの前記絶対値より実質的に大きいように設定され、そのようなシフトが前記周波数帯域の前記上限または下限のいずれかで測定されていることを特徴とする請求項１に記載の方法。
【請求項１０】
前記周波数帯域の前記上限が、前記下限に、最大相対再生速度変化の絶対値に等しい値と前記下限と定数との積を足した値に等しく、
前記定数が、１０ないし１００であることを特徴とする請求項９に記載の方法。
【請求項１１】
前記定数が、１０ないし５０であることを特徴とする請求項１０に記載の方法。
【請求項１２】
各周波数帯域に対して、前記周波数帯域の前記上限が、前記周波数帯域の前記下限値に、１と所定の値との和を乗じた値に実質的に等しいことを特徴とする請求項９に記載の方法。
【請求項１３】
前記所定の値が、実質的に０ないし約１０の値であることを特徴とする請求項１０に記載の方法。
【請求項１４】
所定の数の連続的なタイムフレーム時間の被検出信号の或る部分が複数の既知の信号のうち少なくとも１つの既知の信号の一部と実質的に同じ信号であるかどうかを決定するために信号処理システムによって実行される方法であって、前記複数の既知の信号の各部分が複数の連続的なタイムフレーム時間から構成され、前記既知の信号の各タイムフレームが識別インデックス及びタイムフレームインデックスを有する該方法が、
前記既知の信号の少なくとも１つの前記タイムフレームの少なくとも１つに対して、前記タイムフレーム中に検出される所定の数の周波数絶対値から導かれる数の集合が含まれる第１のシグネチャを計算する過程と、
その対応する信号識別インデックスに関連しかつ実質的に前記既知の信号の最初から前記タイムフレームの時間における近似位置に関連して各第１のシグネチャをコンピュータデータベースに格納する過程と、
前記被検出信号の前記タイムフレームの少なくとも１つに対して、前記タイムフレーム中に検出される所定の数の周波数絶対値から導かれる数の集合が含まれる第２のシグネチャを計算する過程と、
前記格納された集合の第１のシグネチャから、前記第２のシグネチャと共に所定の一致基準を満たすそれらの第１のシグネチャを選択する過程であって、そのような選択が、前記被検出信号における各々の新たなタイムフレームの到着の結果として繰り返し生じるような該過程とを含むことを特徴とする方法。
【請求項１５】
前記第１のシグネチャ及び第２のシグネチャが、請求項１、２、または９の方法のうちいずれか１つを用いて計算及び記憶されることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記所定の一致基準が、
前記第１のシグネチャを含む数の前記集合の各序数元と前記第２のシグネチャを含む数の前記集合のそのような各元の対応する序数元間の差の絶対値の集合を計算する過程と、
前記絶対値の合計を計算する過程と、
前記合計が所定の値以下の値を生成するかを判定する過程とを含むことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記所定の一致基準が、
前記第１のシグネチャを含む数の前記集合の各序数元と前記第２のシグネチャを含む数の前記集合のそのような各元の対応する序数元間の差の絶対値の集合を計算する過程と、
前記絶対値の集合の合計を計算する過程と、
前記合計がテストした第１のシグネチャ全ての最小和であるかを判定する過程とを含むことを特徴とする請求項１４に記載の方法。
【請求項１８】
前記所定の一致基準が、
（ｉ）前記第１のシグネチャから前記第２のシグネチャへの近似ベクトル距離、
（ｉｉ）前記第１のシグネチャと前記第２のシグネチャ間の近似Ｌ１ノルム、
（ｉｉｉ）前記第１のシグネチャにおける任意の元と前記第２のシグネチャにおけるそれに対応する序数元間の近似最大差、
（ｉｖ）前記第１のシグネチャにおける任意の元と前記第２のシグネチャにおけるそれに対応する序数元間の近似最小差、
（ｖ）前記第１のシグネチャにおける前記元の全てと前記第２のシグネチャにおけるこれらに対応する元間の近似平均差、
のうちの１つを用いて誤差値を計算する過程を含むことを特徴とする請求項１４に記載の方法。
【請求項１９】
所定の一致基準を満たしかつ同一の識別インデックスを有する第１のシグネチャの前記数が、Ｋ＋１及び２Ｋ＋１を含むＫ＋１ないし２Ｋ＋１の間の数に等しいかそれより大きいかどうか決定する過程であって、２Ｋ＋１が所定の数のタイムフレームに等しくなるようにＫが評価される該過程を更に含むことを特徴とする請求項１４に記載の方法。
【請求項２０】
前記一致基準が、
同一の識別インデックスを有する一致する第１のシグネチャに対応する前記タイムフレームインデックスの前記値が、前記被検出信号の前記一致するタイムフレームの前記タイムフレームインデックスの前記値に対して実質的に単調に増加するかどうかを決定する過程を含むことを特徴とする請求項１４に記載の方法。
【請求項２１】
前記一致基準が、
同一の識別インデックスを有する一致する第１のシグネチャに対応する前記タイムフレームインデックスの前記値が、前記被検出信号の前記一致するタイムフレームの前記タイムフレームインデックスの前記値に一時的に相関するかどうかを決定する過程を含むことを特徴とする請求項１４に記載の方法。
【請求項２２】
前記一致基準が、
同一の識別インデックスを有する一致する第１のシグネチャに対応する前記タイムフレームインデックスの前記値と前記被検出信号の前記一致するタイムフレームの前記タイムフレームインデックスの前記値間の近似回帰分析を計算する過程を含むことを特徴とする請求項１４に記載の方法。
【請求項２３】
前記決定が、相関係数が約５に等しいかそれ以上であるかどうかのテストからなることを特徴とする請求項２２に記載の方法。
【請求項２４】
前記決定が、直線の傾きが２及び６を含む２から６までの近似範囲内にあるかどうかのテストからなることを特徴とする請求項２３に記載の方法。
【請求項２５】
一連の少なくとも２つのタイムフレームにおいて前記被検出信号の前記タイムフレームインデックスが前記一致する既知の信号の前記タイムフレームインデックスの増加にほぼ対応して増加することを確認するべく前記被検出信号及び一致する既知の信号の前記タイムフレームインデックスが定期的に追跡されることを特徴とする請求項４に記載の方法。
【請求項２６】
所定の数の連続的なタイムフレーム時間の被検出信号の一部が、複数の既知の信号のうち少なくとも１つの既知の信号の一部と実質的に同じ信号であるかどうかを決定するための信号処理システムによって実行される方法であって、前記複数の既知の信号の各一部が複数の連続的なタイムフレーム時間から構成され、前記既知の信号の各タイムフレームが識別インデックス及びタイムフレームインデックスを有する該方法が、
前記既知の信号の少なくとも１つの前記タイムフレームの少なくとも１つのために、前記タイムフレーム中に検出される所定の数の周波数絶対値から導かれる数の集合が含まれる第１のシグネチャを計算する過程と、
その対応する信号識別インデックスに関連しかつ実質的に前記既知の信号の最初から前記タイムフレームの時間における近似位置に関連して各第１のシグネチャをコンピュータデータベースに格納する過程と、
前記被検出信号の前記タイムフレームの少なくとも１つのために、前記タイムフレーム中に検出される所定の数の周波数絶対値から導かれる１組の数が含まれる第２のシグネチャを計算する過程と、
前記格納された集合の第１のシグネチャから、前記第２のシグネチャと共に所定の一致基準を満たすそれらの第１のシグネチャを選択する過程と、
前記一致する第１のシグネチャに対応する前記タイムフレームインデックス及び前記識別インデックスを少なくとも１つのデータ構造に格納する過程と、
前記データ構造からそれらのタイムフレームインデックス及び対応する識別インデックスを削除する過程であって、前記リスト中のＫ＋１より少ない項目が同一識別インデックスを有し、２Ｋ＋１が前記被検出信号の前記部分を構成する前記所定の数のタイムフレームに等しくなるようにＫが計算されるような該過程と、
前記リストからそれらのタイムフレームインデックス及び識別インデックスを削除する過程であって、前記第１のシグネチャの前記タイムフレームインデックスが前記被検出信号のタイムフレームインデックスとの同期性を実質的に増加することが確認されないような該過程とを含むことを特徴とする方法。
【請求項２７】
対応する識別インデックス及びタイムフレームインデックスを有する少なくともｎ個の第１のシグネチャの集合が含まれるデータベースを探索する信号処理システムによって実行される方法であって、各第１のシグネチャが前記タイムフレーム中の既知の信号の前記周波数成分を表し、前記探索が第２のシグネチャと共に所定の一致基準を満たす第１のシグネチャ全てを探し、前記第２のシグネチャがタイムフレーム中に被検出信号の周波数成分を表す該方法が、
前記第１のシグネチャの全てから構成される第１のデータアレイであって、前記第１のデータアレイにおけるｎ番目の行がｎ番目の第１のシグネチャの元の集合であるような該第１のデータアレイをコンピュータメモリに格納する過程と、
前記第１のデータアレイにおける少なくとも１つの列に対して、前記コンピュータメモリ内で前記列の前記要素を昇順または降順のいずれかでソートする過程と、
追加のデータアレイをコンピュータメモリに格納する過程であって、前記第２のデータアレイにおける１つの要素が前記第１のデータアレイの１つの列における或る要素に対応し、前記第２のデータアレイにおける前記１つの要素の値が前記ソートする過程の前に生じた前記第１のデータアレイにおける前記対応する要素を相互参照する該過程と、
前記第１のデータアレイの前記行と前記第２のシグネチャ間の最良の一致を見つけるために前記第２のシグネチャを用いる探索を適用する過程と、
前記第２のデータアレイの前記相互参照を用いることによって任意の一致する第１のシグネチャの前記識別インデックス及びタイムフレームインデックスを回収し、それを前記一致する行に適用する過程とを含むことを特徴とする方法。
【請求項２８】
前記探索アルゴリズムが、二分探索、Ｂツリー、線形探索、ヒューリスティック木探索、深さ優先探索、幅優先探索のうちのいずれか１つであることを特徴とする請求項２４に記載の方法。
【請求項２９】
信号を表す少なくとも１つの第１のシグネチャが含まれるようなデータベースを第２のシグネチャが含まれる問い合わせを用いて探索する信号処理システムによって実行される方法であって、前記第１及び第２のシグネチャが共に所定の数の要素の集合であり、各要素が数である該方法が、
各第１のシグネチャに対して、所定の計算を適用して、各第１のシグネチャを含む要素の部分集合の関数として第１の整数を計算する過程と、
前記第１のシグネチャを計算する際に用いられる前記対応する第１のシグネチャへの参照を前記第１の整数の前記値に対応するコンピュータメモリ位置に格納する過程と、
前記第２のシグネチャの前記対応する部分集合に適用したものと同じ所定の計算を用いて第２の整数を計算する過程と、
前記第２の整数から所定の誤差関数内の整数値に対応するメモリ位置を選択する過程と、
任意の第１のシグネチャ及び選択されたメモリ位置に対応するそれらの識別インデックス及びタイムフレームインデックスを決定する過程とを含むことを特徴とする方法。
【請求項３０】
前記所定の計算が、前記シグネチャの少なくとも２つの要素の一次結合であることを特徴とする請求項２９に記載の方法。
【請求項３１】
前記部分集合が、前記第１のシグネチャの５個以下の要素を有することを特徴とする請求項２９に記載の方法。
【請求項３２】
前記誤差関数が、
（ｉ）前記２つの整数値が閾値距離間隔内にあるかどうかの判定、
（ｉｉ）他の第１の整数に対する前記第２の整数までの最小距離である第１の整数の選択、
のいずれか１つであることを特徴とする請求項２に記載の方法。
【請求項３３】
前記信号が、任意の既知信号の任意の部分と一致することが分かっていない未知の識別情報のプログラムに含まれ、更に、対応するシグネチャを有するタイムフレームに含まれ、
識別インデックスを有する任意の識別子を作成する過程と、
前記信号から導かれるそれらのシグネチャに前記識別インデックスを割り当てる過程と、
前記未知の信号が識別されたときに前記任意の識別子を正しい識別に置き換える過程とを含むことを特徴とする方法。
【請求項３４】
前記データベース中の前記任意の識別インデックスを、前記信号を識別する有効な識別データを参照する既存の識別インデックスに置き換える過程を更に含むことを特徴とする請求項３３に記載の方法。
【請求項３５】
中央処理装置と、デジタルデータトランシーバ装置と、任意の機械読取り可能な媒体から構成されるデータ記憶装置とを含む機械であって、前記機械読取り可能な媒体が、前記機械によって実行されるときに請求項１ないし３４の方法を実行するコンピュータプログラムを含むことを特徴とする機械。
【請求項３６】
任意の種類の機械読取り可能な媒体であって、コンピュータによって実行されるときに請求項１ないし３４の方法を実行するコンピュータプログラムであるようなデータを含むことを特徴とする媒体。
【請求項１】
既知の信号に関連するシグネチャを生成するデジタル信号処理システムによって実行される方法であって、前記シグネチャが少なくとも１つの要素の数値の集合から構成されかつ少なくとも信号のタイムフレームに対応し、そのような既知の信号が識別インデックスによって識別され、そのようなタイムフレームがタイムフレームインデックスによって識別される該方法が、
前記信号の前記少なくとも１つのタイムフレームを、そのようなタイムフレームに対して所定の幅の少なくとも１つの周波数帯域にグループ分けされた所定の数の周波数絶対値があるように周波数領域に変換する過程と、
各周波数帯域に対して、前記周波数帯域内にグループ分けされた前記周波数絶対値の所定の関数に等しい１つの数値を計算する過程と、
前記シグネチャをその対応するタイムフレームインデックス及び前記識別インデックスに関連してコンピュータデータベースに格納する過程とを含むことを特徴とする方法。
【請求項２】
前記所定の関数が、（ｉ）一次結合、（ｉｉ）二次関数、（ｉｉｉ）重心、（ｉｖ）分散、または（ｖ）ｎ次モーメントのいずれかによって構成され、ｎが所定の数であることを特徴とする請求項１に記載の方法。
【請求項３】
前記関数結果を前記対応する周波数帯域における前記所定の数の周波数絶対値で割る過程を更に含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記関数が一次結合であり、前記一次結合の各項の前記係数が、前記周波数帯域内の前記周波数絶対値の序数インデックスを所定の定数で割ったものに実質的に等しいことを特徴とする請求項１に記載の方法。
【請求項５】
所定の周波数帯域の前記数が、１０ないし１００であることを特徴とする請求項１に記載の方法。
【請求項６】
前記周波数帯域が、０Ｈｚより上でかつおおよそ４０００Ｈｚに等しいかそれ以下の範囲を占めることを特徴とする請求項１に記載の方法。
【請求項７】
前記所定の定数が、前記対応する周波数帯域における前記周波数絶対値の合計に実質的に等しいことを特徴とする請求項４に記載の方法。
【請求項８】
前記関数結果を、前記対応する周波数帯域における前記所定の数の周波数絶対値で割る過程を更に含むことを特徴とする請求項７に記載の方法。
【請求項９】
周波数帯域の前記幅が、前記既知の信号の前記再生速度における所定の最大変化量に起因する前記周波数シフトの前記絶対値より実質的に大きいように設定され、そのようなシフトが前記周波数帯域の前記上限または下限のいずれかで測定されていることを特徴とする請求項１に記載の方法。
【請求項１０】
前記周波数帯域の前記上限が、前記下限に、最大相対再生速度変化の絶対値に等しい値と前記下限と定数との積を足した値に等しく、
前記定数が、１０ないし１００であることを特徴とする請求項９に記載の方法。
【請求項１１】
前記定数が、１０ないし５０であることを特徴とする請求項１０に記載の方法。
【請求項１２】
各周波数帯域に対して、前記周波数帯域の前記上限が、前記周波数帯域の前記下限値に、１と所定の値との和を乗じた値に実質的に等しいことを特徴とする請求項９に記載の方法。
【請求項１３】
前記所定の値が、実質的に０ないし約１０の値であることを特徴とする請求項１０に記載の方法。
【請求項１４】
所定の数の連続的なタイムフレーム時間の被検出信号の或る部分が複数の既知の信号のうち少なくとも１つの既知の信号の一部と実質的に同じ信号であるかどうかを決定するために信号処理システムによって実行される方法であって、前記複数の既知の信号の各部分が複数の連続的なタイムフレーム時間から構成され、前記既知の信号の各タイムフレームが識別インデックス及びタイムフレームインデックスを有する該方法が、
前記既知の信号の少なくとも１つの前記タイムフレームの少なくとも１つに対して、前記タイムフレーム中に検出される所定の数の周波数絶対値から導かれる数の集合が含まれる第１のシグネチャを計算する過程と、
その対応する信号識別インデックスに関連しかつ実質的に前記既知の信号の最初から前記タイムフレームの時間における近似位置に関連して各第１のシグネチャをコンピュータデータベースに格納する過程と、
前記被検出信号の前記タイムフレームの少なくとも１つに対して、前記タイムフレーム中に検出される所定の数の周波数絶対値から導かれる数の集合が含まれる第２のシグネチャを計算する過程と、
前記格納された集合の第１のシグネチャから、前記第２のシグネチャと共に所定の一致基準を満たすそれらの第１のシグネチャを選択する過程であって、そのような選択が、前記被検出信号における各々の新たなタイムフレームの到着の結果として繰り返し生じるような該過程とを含むことを特徴とする方法。
【請求項１５】
前記第１のシグネチャ及び第２のシグネチャが、請求項１、２、または９の方法のうちいずれか１つを用いて計算及び記憶されることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記所定の一致基準が、
前記第１のシグネチャを含む数の前記集合の各序数元と前記第２のシグネチャを含む数の前記集合のそのような各元の対応する序数元間の差の絶対値の集合を計算する過程と、
前記絶対値の合計を計算する過程と、
前記合計が所定の値以下の値を生成するかを判定する過程とを含むことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記所定の一致基準が、
前記第１のシグネチャを含む数の前記集合の各序数元と前記第２のシグネチャを含む数の前記集合のそのような各元の対応する序数元間の差の絶対値の集合を計算する過程と、
前記絶対値の集合の合計を計算する過程と、
前記合計がテストした第１のシグネチャ全ての最小和であるかを判定する過程とを含むことを特徴とする請求項１４に記載の方法。
【請求項１８】
前記所定の一致基準が、
（ｉ）前記第１のシグネチャから前記第２のシグネチャへの近似ベクトル距離、
（ｉｉ）前記第１のシグネチャと前記第２のシグネチャ間の近似Ｌ１ノルム、
（ｉｉｉ）前記第１のシグネチャにおける任意の元と前記第２のシグネチャにおけるそれに対応する序数元間の近似最大差、
（ｉｖ）前記第１のシグネチャにおける任意の元と前記第２のシグネチャにおけるそれに対応する序数元間の近似最小差、
（ｖ）前記第１のシグネチャにおける前記元の全てと前記第２のシグネチャにおけるこれらに対応する元間の近似平均差、
のうちの１つを用いて誤差値を計算する過程を含むことを特徴とする請求項１４に記載の方法。
【請求項１９】
所定の一致基準を満たしかつ同一の識別インデックスを有する第１のシグネチャの前記数が、Ｋ＋１及び２Ｋ＋１を含むＫ＋１ないし２Ｋ＋１の間の数に等しいかそれより大きいかどうか決定する過程であって、２Ｋ＋１が所定の数のタイムフレームに等しくなるようにＫが評価される該過程を更に含むことを特徴とする請求項１４に記載の方法。
【請求項２０】
前記一致基準が、
同一の識別インデックスを有する一致する第１のシグネチャに対応する前記タイムフレームインデックスの前記値が、前記被検出信号の前記一致するタイムフレームの前記タイムフレームインデックスの前記値に対して実質的に単調に増加するかどうかを決定する過程を含むことを特徴とする請求項１４に記載の方法。
【請求項２１】
前記一致基準が、
同一の識別インデックスを有する一致する第１のシグネチャに対応する前記タイムフレームインデックスの前記値が、前記被検出信号の前記一致するタイムフレームの前記タイムフレームインデックスの前記値に一時的に相関するかどうかを決定する過程を含むことを特徴とする請求項１４に記載の方法。
【請求項２２】
前記一致基準が、
同一の識別インデックスを有する一致する第１のシグネチャに対応する前記タイムフレームインデックスの前記値と前記被検出信号の前記一致するタイムフレームの前記タイムフレームインデックスの前記値間の近似回帰分析を計算する過程を含むことを特徴とする請求項１４に記載の方法。
【請求項２３】
前記決定が、相関係数が約５に等しいかそれ以上であるかどうかのテストからなることを特徴とする請求項２２に記載の方法。
【請求項２４】
前記決定が、直線の傾きが２及び６を含む２から６までの近似範囲内にあるかどうかのテストからなることを特徴とする請求項２３に記載の方法。
【請求項２５】
一連の少なくとも２つのタイムフレームにおいて前記被検出信号の前記タイムフレームインデックスが前記一致する既知の信号の前記タイムフレームインデックスの増加にほぼ対応して増加することを確認するべく前記被検出信号及び一致する既知の信号の前記タイムフレームインデックスが定期的に追跡されることを特徴とする請求項４に記載の方法。
【請求項２６】
所定の数の連続的なタイムフレーム時間の被検出信号の一部が、複数の既知の信号のうち少なくとも１つの既知の信号の一部と実質的に同じ信号であるかどうかを決定するための信号処理システムによって実行される方法であって、前記複数の既知の信号の各一部が複数の連続的なタイムフレーム時間から構成され、前記既知の信号の各タイムフレームが識別インデックス及びタイムフレームインデックスを有する該方法が、
前記既知の信号の少なくとも１つの前記タイムフレームの少なくとも１つのために、前記タイムフレーム中に検出される所定の数の周波数絶対値から導かれる数の集合が含まれる第１のシグネチャを計算する過程と、
その対応する信号識別インデックスに関連しかつ実質的に前記既知の信号の最初から前記タイムフレームの時間における近似位置に関連して各第１のシグネチャをコンピュータデータベースに格納する過程と、
前記被検出信号の前記タイムフレームの少なくとも１つのために、前記タイムフレーム中に検出される所定の数の周波数絶対値から導かれる１組の数が含まれる第２のシグネチャを計算する過程と、
前記格納された集合の第１のシグネチャから、前記第２のシグネチャと共に所定の一致基準を満たすそれらの第１のシグネチャを選択する過程と、
前記一致する第１のシグネチャに対応する前記タイムフレームインデックス及び前記識別インデックスを少なくとも１つのデータ構造に格納する過程と、
前記データ構造からそれらのタイムフレームインデックス及び対応する識別インデックスを削除する過程であって、前記リスト中のＫ＋１より少ない項目が同一識別インデックスを有し、２Ｋ＋１が前記被検出信号の前記部分を構成する前記所定の数のタイムフレームに等しくなるようにＫが計算されるような該過程と、
前記リストからそれらのタイムフレームインデックス及び識別インデックスを削除する過程であって、前記第１のシグネチャの前記タイムフレームインデックスが前記被検出信号のタイムフレームインデックスとの同期性を実質的に増加することが確認されないような該過程とを含むことを特徴とする方法。
【請求項２７】
対応する識別インデックス及びタイムフレームインデックスを有する少なくともｎ個の第１のシグネチャの集合が含まれるデータベースを探索する信号処理システムによって実行される方法であって、各第１のシグネチャが前記タイムフレーム中の既知の信号の前記周波数成分を表し、前記探索が第２のシグネチャと共に所定の一致基準を満たす第１のシグネチャ全てを探し、前記第２のシグネチャがタイムフレーム中に被検出信号の周波数成分を表す該方法が、
前記第１のシグネチャの全てから構成される第１のデータアレイであって、前記第１のデータアレイにおけるｎ番目の行がｎ番目の第１のシグネチャの元の集合であるような該第１のデータアレイをコンピュータメモリに格納する過程と、
前記第１のデータアレイにおける少なくとも１つの列に対して、前記コンピュータメモリ内で前記列の前記要素を昇順または降順のいずれかでソートする過程と、
追加のデータアレイをコンピュータメモリに格納する過程であって、前記第２のデータアレイにおける１つの要素が前記第１のデータアレイの１つの列における或る要素に対応し、前記第２のデータアレイにおける前記１つの要素の値が前記ソートする過程の前に生じた前記第１のデータアレイにおける前記対応する要素を相互参照する該過程と、
前記第１のデータアレイの前記行と前記第２のシグネチャ間の最良の一致を見つけるために前記第２のシグネチャを用いる探索を適用する過程と、
前記第２のデータアレイの前記相互参照を用いることによって任意の一致する第１のシグネチャの前記識別インデックス及びタイムフレームインデックスを回収し、それを前記一致する行に適用する過程とを含むことを特徴とする方法。
【請求項２８】
前記探索アルゴリズムが、二分探索、Ｂツリー、線形探索、ヒューリスティック木探索、深さ優先探索、幅優先探索のうちのいずれか１つであることを特徴とする請求項２４に記載の方法。
【請求項２９】
信号を表す少なくとも１つの第１のシグネチャが含まれるようなデータベースを第２のシグネチャが含まれる問い合わせを用いて探索する信号処理システムによって実行される方法であって、前記第１及び第２のシグネチャが共に所定の数の要素の集合であり、各要素が数である該方法が、
各第１のシグネチャに対して、所定の計算を適用して、各第１のシグネチャを含む要素の部分集合の関数として第１の整数を計算する過程と、
前記第１のシグネチャを計算する際に用いられる前記対応する第１のシグネチャへの参照を前記第１の整数の前記値に対応するコンピュータメモリ位置に格納する過程と、
前記第２のシグネチャの前記対応する部分集合に適用したものと同じ所定の計算を用いて第２の整数を計算する過程と、
前記第２の整数から所定の誤差関数内の整数値に対応するメモリ位置を選択する過程と、
任意の第１のシグネチャ及び選択されたメモリ位置に対応するそれらの識別インデックス及びタイムフレームインデックスを決定する過程とを含むことを特徴とする方法。
【請求項３０】
前記所定の計算が、前記シグネチャの少なくとも２つの要素の一次結合であることを特徴とする請求項２９に記載の方法。
【請求項３１】
前記部分集合が、前記第１のシグネチャの５個以下の要素を有することを特徴とする請求項２９に記載の方法。
【請求項３２】
前記誤差関数が、
（ｉ）前記２つの整数値が閾値距離間隔内にあるかどうかの判定、
（ｉｉ）他の第１の整数に対する前記第２の整数までの最小距離である第１の整数の選択、
のいずれか１つであることを特徴とする請求項２に記載の方法。
【請求項３３】
前記信号が、任意の既知信号の任意の部分と一致することが分かっていない未知の識別情報のプログラムに含まれ、更に、対応するシグネチャを有するタイムフレームに含まれ、
識別インデックスを有する任意の識別子を作成する過程と、
前記信号から導かれるそれらのシグネチャに前記識別インデックスを割り当てる過程と、
前記未知の信号が識別されたときに前記任意の識別子を正しい識別に置き換える過程とを含むことを特徴とする方法。
【請求項３４】
前記データベース中の前記任意の識別インデックスを、前記信号を識別する有効な識別データを参照する既存の識別インデックスに置き換える過程を更に含むことを特徴とする請求項３３に記載の方法。
【請求項３５】
中央処理装置と、デジタルデータトランシーバ装置と、任意の機械読取り可能な媒体から構成されるデータ記憶装置とを含む機械であって、前記機械読取り可能な媒体が、前記機械によって実行されるときに請求項１ないし３４の方法を実行するコンピュータプログラムを含むことを特徴とする機械。
【請求項３６】
任意の種類の機械読取り可能な媒体であって、コンピュータによって実行されるときに請求項１ないし３４の方法を実行するコンピュータプログラムであるようなデータを含むことを特徴とする媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公表番号】特表２００７−５３４００８（Ｐ２００７−５３４００８Ａ）
【公表日】平成１９年１１月２２日（２００７．１１．２２）
【国際特許分類】
【出願番号】特願２００７−５００８７６（Ｐ２００７−５００８７６）
【出願日】平成１７年２月１６日（２００５．２．１６）
【国際出願番号】ＰＣＴ／ＵＳ２００５／００４８０２
【国際公開番号】ＷＯ２００５／０８１８２９
【国際公開日】平成１７年９月９日（２００５．９．９）
【出願人】（５０６２８８１０６）メディアガイド・インコーポレイテッド (1)
【氏名又は名称原語表記】ＭＥＤＩＡＧＵＩＤＥ， ＩＮＣ．
【住所又は居所原語表記】１０００ Ｃｈｅｓｔｅｒｂｒｏｏｋ Ｂｌｖｄ， Ｓｕｉｔｅ １５０， Ｂｅｒｗｙｎ， ＰＡ １９３１２， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公表日】平成１９年１１月２２日（２００７．１１．２２）
【国際特許分類】
【出願日】平成１７年２月１６日（２００５．２．１６）
【国際出願番号】ＰＣＴ／ＵＳ２００５／００４８０２
【国際公開番号】ＷＯ２００５／０８１８２９
【国際公開日】平成１７年９月９日（２００５．９．９）
【出願人】（５０６２８８１０６）メディアガイド・インコーポレイテッド (1)
【氏名又は名称原語表記】ＭＥＤＩＡＧＵＩＤＥ， ＩＮＣ．
【住所又は居所原語表記】１０００ Ｃｈｅｓｔｅｒｂｒｏｏｋ Ｂｌｖｄ， Ｓｕｉｔｅ １５０， Ｂｅｒｗｙｎ， ＰＡ １９３１２， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]