The Shazam Music Recognition Service
Shazam 音楽認識サービス
他でも，音楽識別（identification）の配信 の試みがなされてきた．例えば，1999 年に初 期の先駆者StarCD が携帯電話ユーザを使っ て，あるラジオ局で流れている歌の識別を可 能にするサービスを導入した[1]．識別には， ユーザは未知の歌が流れている時に StarCD サービスを電話で呼び出す．次に，ラジオ局 のコールサイン（call letter，例えば NHK） を 電 話 の キ ー パ ッ ド で 入 力 す る ． StarCD はサードパーティのプレイリ ストデータベース提供会社に自動的 に問い合わせ，呼び出しのあった時刻 に指定されたラジオ局で流された歌 を確認する．その音楽の身元を知る と，ユーザはそのCD を買う機会を与 えられたことになる． この結果， StarCD システムは，サードパーティ のプレイリスト提供会社がモニター しているラジオ局の歌だけに限られ ていた． QBE は，StarCD で提供されてい たものよりも柔軟な音楽認識用入力モダリテ ィを有しており，ユーザにラジオ局情報を入 力させる代わりに録音されたサンプルから認 識する．QBE 音楽認識研究は，世界中の複数 のグループが推進してきた．例えば，1980 年 代 初 期 に Broadcast Data Systems （www.bdsonline.com/）は，初期の先駆者であ り，多様な波形相関法を用いていた[4]．1996 年，Musclefish（www.musclefish.com/） が多Avery Wang
ユーザが与えた query-by-example の音楽サンプルに導かれて，
関連する音楽情報だけでなく，
そのユーザに直接興味があるマッチする歌を配信してくれる．
図：Shazam インターフェース：(a) 10 秒間の 音響サンプルの録音，(b) クエリ結果の表示． 人々は，毎日の環境―車，家，レストラン，ムービーシアター，ショッピングモ ール―において，日常的に音楽にさらされているのに，聞こえてきたものについて もっと知ることができないことに，フラストレーションを感じている．例えば，あ る特定の楽曲に興味を持っていて，そのタイトルやそれを作ったアーティストの名 前を知りたいと思っているかもしれないし，その歌のディジタルダウンロードや着 メロを購入したいと思うかもしれない．これらの限界を取り組むため，Shazam Entertainment で，私と同僚は，query-by-example（QBE）の音楽検索サービス を開発した．これにより，ユーザは携帯電話を録音機器として用いて数秒間の音を サンプリングすることで，録音済み音楽の身元（identitiy）を知ることができる．次元特徴解析とユークリッド距離測度に基づ く手法を開発した[6]．しかし，これらの方法 はすべて，かなりクリーンな音響サンプルに 対して最も適しており，重大な雑音や歪みが 存在する下では十分に機能しなかった． 我 々 が 2000 年 に ロ ン ド ン で Shazam Entertainment を設立した時，携帯電話を通 じて提供する商用 QBE 音楽認識サービスの 開発を目指した[5]．ユーザは，短縮ダイヤル コードでサービスに電話をかけ，音響サンプ ルを録音する．サンプリング後，サーバは電 話を切って，認識結果を SMS テキストメッ セ ー ジ 経 由 で 返 す ．2004 年 に は ， Song Identity と呼ぶ新バージョンを導入した．も っとインタラクティブなインターフェースを 提供するもので，最初はアメリカの Verizon Wireless を通じて利用できた．以降，このア プリケーションを様々な受話器（handset） プラットフォームに移植している． Song Identity を用いる前に，ユーザはまず アプレットをダウンロードして受話器にイン ストールする．認識したい音楽が聞こえたら， アプレットを開始し，周囲の音響信号を約10 秒間録音して，音響ファイルをShazam に送 るか電話機上で特徴抽出を行って小さな署名 （signature）ファイルを生成する．この署名 ファイルは中央サーバに送られ，中央サーバ が検索をし，マッチするメタデータ―タイト ル，アーティスト，アルバム―をアプレット にもどす（図を参照のこと）．次に，ユーザに タイトル，アーティスト，アルバムの情報が 提示され，さらに，対応する着メロ（ringtone） をダウンロードするオプションも―マッチす るものがあれば―示される．数種のプラット フォーム上の将来のバージョンでは，フルト ラックのダウンロード，CD，コンサートチケ ット，歌詞，さらにその音楽に関連する追加 情報やイベントを購入できるようになろう． Song Identity を含む商業的 QBE 音楽認識 システムが克服しなければならない数々の手 強い技術的チャレンジを以下に示す： 雑音（noise）．雑音はある種の環境では対 象の音楽と張り合うほど大きい．例えば，音 楽は一般に騒々しいカフェやショッピングモ ールの背景となっている．車の中にいれば， 交通やエンジン雑音といったやっかいごとが 加わる．雑音のパワーは実に信号のパワーよ り著しく大きい可能性があり，そのため認識 アルゴリズムは顕著な雑音を扱えるほどにロ バストである必要がある． 歪み（distortion）．システムは，不完全な 再生・録音機器だけでなく環境的要因（残響 （reverberation）や吸収）を含むさまざまな 原因から来る歪みを扱えなければならない． 電話機器を通じてサンプリングすると，周波 数応答は約300Hz～3,400Hz までに縮退して しまう．歪みは，携帯電話における低ビット レートの音声圧縮に起因する音響サンプルか らも生ずる可能性もある．受話器や携帯電話 会社のネットワークに組み込まれた非線形雑 音抑制（nonlinear noise suppression）や音 声 圧 縮 と 音 声 品 質 強 調 （voice-quality- enhancement）アルゴリズムは，背景音楽の サンプリングがほとんど無音しか含まない録 音という結果に終わってしまうので，さらな るチャレンジの代表格となろう． データベース管理．システムは，過度な台 数のサーバを要求することなく，オンライン データベースにおける数百万もの歌の「フィ ンガープリント」をインデックス付けできな ければならない．そのため，各歌のフィンガ ープリント，つまり一意的な特徴表現が，高々 数キロバイトのオーダと言う，十分に小さく なければならない．さらに，システムは1 秒 間に数百から数千のクエリをさばく必要があ ると思われるので，数百万曲まで規模が拡大 した時に，バックエンド検索エンジンに重大 な処理負荷を招いてはならない．システムは 量的な規模拡大ができなければならない．つ まり，数百万曲をデータベースに追加しても， 正解マッチングを見つける確率が著しく低下 し て は な ら な い し ， 誤 っ た 結 果 （false
数百万曲をデータベースに追加しても
正解マッチングを見つける確率が著しく低下してはならないし，
誤った結果を報告する確率が著しく上昇してもならない
positive）を報告する確率が著しく上昇しても ならない． 我々は，携帯電話を通して集めた初期の音 響サンプルに落胆した．音楽の歪みがとても 激しく，我々の耳をもってしても音楽の存在 がかろうじて認識できるほどのことが数多く あった．我々は，数百万の録音まで規模拡大 するどころか，電話を通した音響サンプルを その既知のマスター録音にマッチさせること にすらしばしば四苦八苦した．我々の努力を 断念せざるを得なくなるという危機にすらさ らされていた．幸いにも，2000 年に 3 ヶ月に わたる作業の後，これらのチャレンジを一般 的に克服する，時間伸縮のする組み合わせハ ッシュ法（temporally aligned combinatorial hashing）を用いた解決策にたどり着いた． 我々が何とか解決しようとしたもう1 つの チャレンジは，技術的というより物流上のも のである．つまり，数百万もの歌から成るデ ータベースをどうやってコストを効果的に （cost-effectively）まとめ上げるかということ である．Shazam は，大規模な音楽カタログ を持つコンテンツパートナーからフィンガー プリントを抽出するだけでなく，音楽資産を 購入している．実際には，こうした制約に直 面したことは，我々の音楽認識アルゴリズム の開発を単純化する手助けとなった．特に信 号より大きい雑音が存在する中で，大量の録 音へと規模拡大できないようなアプローチ は，我々は無視せざるを得なかった．こうし た考えは数々のひらめきをもたらした[5]．ま ず初めに，顕著な雑音や歪みがあっても再現 可能なロバストな特徴量を見つけなければな らない．我々は数々の候補となる特徴量（例 えばパワー包絡（power envelop）やメル周波 数ケプストラム係数（mel-frequency cepstral coefficients））を検討したが，大部分は我々の 要求に十分なほどロバストではなかった． 我々は，線形に重ね合わせが可能で（透過 的（transparently）），雑音が存在しても復元 できる特徴量が必要であった．そこで我々は， スペクトログラムピークに転じた[1]．これ は，時間および周波数の項でのエネルギーの 分布のマップを提供するものである1．ピーク の位置は，非線形処理の結果ではあるものの， 実質的に線形重ね合わせが可能である．つま り，音楽と雑音の混合音に対するスペクトロ グラムのピーク解析は，各々を別々に解析し た場合の（音楽と雑音それぞれの）ピークを 含んでいる．雑音ありと雑音なしの音楽信号 それぞれに対応するスペクトログラムピーク が存在すれば，音響サンプルがデータベース 中の録音とマッチするかどうかを高い確率で 決定することができる． ロバストではあるものの，フィンガープリ ント特徴量として使用される個々のスペクト ログラムピークの集合は，効率的な検索を可 能にするには，特に大規模なデータベースに 対しては，十分なエントロピーを提供できな い（一意的特徴量の数が少なすぎる）．透過性 を維持したままエントロピーを上げるため， 「 組 み 合 わ せ ハ ッ シ ュ 法 」（computational hashing）と呼ぶ方法を我々は見つけるに至 った．この方法では，解析している信号に存 在するすべてのスペクトログラムピークの集 合から選ばれたスペクトログラムピーク対を 使用してフィンガープリントハッシュトーク ンを構築する．フィンガープリント形成処理 では，スペクトログラムピークの部分集合を 「アンカー点」（anchor point）として用いる． 各アンカー点には，そのアンカーの座標から 時間・周波数値のオフセットで指定される範 囲によって定義される対象区域が与えられて いる．また，各アンカー点は，対象区域中の いくつかの対象点と対にされる．周波数情報 と各点対から相対的な時間オフセットを使っ て，32 バイトのフィンガープリントハッシュ トークンを構築される． この組み合わせ的展開の結果，元のスペク トログラムピーク数に対して，データベース 中で検索されるトークン数がおそらく 10 倍 増加することになろう．しかし，ハッシュト ークンのエントロピーが増加することによ 1 重なりのある短時間フーリエ変換（Short-Time Fourier Transform）が，音響データ上の決まっ た間隔で計算され，その結果得られる時間周波 数ビン（bin）のそれぞれに対してパワーレベル を計算する．あるビンのパワーレベルが，その ビンの周りの有界領域における他のすべてのビ ンのパワーレベルよりも大きければ，そのビン
り，インデックス検索が100 万倍以上の高速 化するのに役立ち，この結果，特定の歌を識 別する時に著しい処理速度の改善をもたら す．この高速化は，情報中に意味あるビット が増えるほど，曖昧性の高い乱雑からもっと 効率的に切り抜けられるという事実による． この組み合わせハッシュ法の音楽と雑音の 混合音に対する効果により，生成されたフィ ンガープリントトークンは３つのクラスに分 かれる： z 両方のスペクトログラムピークが対 象信号に属する． z 1 つのピークが対象信号に属し，１つ が雑音信号に属する． z 両方のピークが雑音に属する． 対象信号からのピークを含むトークンだけ が検索処理に重要である．Shazam アプリケ ーションでよく遭遇するSN 比が低い状況で は，音響サンプルから生成されたトークンの 大部分は，ごみである．しかし，数％しかな いがよくマッチするトークンが存在すれば， 歌の大規模データベースにおいて正しい歌を 見つける統計的に有意な確率を示すのに十分 である． 我々は，フィンガープリント特徴量が時間 的に対応付けられていなければならないこと にも気がついた．すなわち，特徴量集合がデ ータベース中の元々の録音とサンプルクエリ の両方に出現していれば，各録音中の各特徴 量の相対位置は同じでなければならない．音 声認識では，話す速度が時間的に変化し非決 定的であり，対応がルーズになってしまう特 徴量とのマッチングをうまく行うために動的 時間ワープ（dynamic time warping）が用い るのに対して，Shazam 技術では，そのよう な対応が正に線形であることを仮定する．つ まり，時間対時間の相関図に各トークンの相 対的発生時刻をプロットすると，妥当なマッ チとなる点は，対角線上に集積するはずであ る． このような直線は，相対的時間差のヒスト グラム中のピークを探すことで素早く検出す ることができる．時間的対応付けに関するこ の仮定は，マッチング処理を大きく加速し， 所与のフィンガープリント特徴量が妥当かど うかを決めるアクセプト／リジェクトの基準 を強固なものにすることができ，その結果， 組み合わせハッシュ法の段階で生成された大 量のごみトークンを排除する高速かつ効果的 な方法を提供することになる． 我々は，この認識アルゴリズムをC++で実 装し，速度が決定的意味を持つ箇所はアセン ブリで最適化した．認識サーバは，数十台の 市販の 64 ビット x86 ベースのサーバのクラ スタとして実装した．各サーバは，8GB の RAM を持ち，最適化された Linux カーネル が走っている． 2006 年 6 月現在で，Shazam データベース には300 万以上のトラックを含まれている． 個々の入ってくる要求はマスタープロセスが 受け取り，クエリをスレーブプロセッサの集 合（farm）にブロードキャストする．個々の スレーブプロセッサは，メモリにデータベー スインデックスの1 部を保持している．各ス レーブは，フィンガープリントトークンの世 界の内それが有する1 塊りを独立に検索し， 識別結果をマスターに報告する．マスターは この結果を集め，（認識に関する）報告をリモ ートのクライアントに返す．認識アルゴリズ ムの性能特性の議論に関しては，[5]を参照さ れたい． Shazam 音 楽 認 識 サ ー ビ ス （www.shazam.com）は 2002 年以来イギリス で，携帯電話上で一般に利用可能になってい る．その後，アメリカのVerizon Wireless や Cingular を含むさまざまなサービスブラン ド名でさまざまな地域パートナーを通じてサ ービス提供国は20 カ国以上に広がっている． 2006 年 6 月現在， 世界中で 600 万人近くの 有料顧客がこのサービスを利用している．
雑音ありと雑音なしの音楽信号それぞれに対応する
スペクトログラムピークが存在すれば，
音響サンプルがデータベース中の録音とマッチするかどうかを
高い確率で決定することができる．
その間，Philips Electronics は 2001 年に 自社の「ロバストハッシュ」音響フィンガー プリントアルゴリズムを発表した．これは， 時 間 ・ 周 波 数 格 子 中 の 微 分 エ ネ ル ギ ー 束 （differential energy flux）からハッシュを構 成しているものの，Shazam と同様に，自由 場（free-field）音響識別（QBE）が可能であ る[2]．この技術は 2005 年にカリフォルニア 州エメリービル市の音楽データベース会社 Gracenote が買収した．同様に 2001 年には， ド イ ツ ・ エ ル ラ ン ゲ ン 市 の Fraunhofer Institut（www.iis.fraunhofer.de）が「スペクト ルフラットネス（spectral flatness）」に基づ く技術のデモを行った[3]． QBE 音楽認識は，商業的に現実性のあるも のである．次の数年のうちには，より多くの 携帯電話会社と電話機メーカーが関連サービ スを提供し，QBE は，ちょうどカメラ付き携 帯が今日的であるように，携帯電話の標準的 な特徴群の1 つとなっていく可能性が大であ る．クエリあたりのコストは下げていくべき であり，後続の販売や発見サービスへとさら なる統合も可能とすべきである．他の検索入 力モダリティ（例えば鼻歌検索（query-by- hamming ） や 類 似 楽 曲 検 索 （ query-by- similarity）など）も追加できよう． 文献
1. Bond, P. StarCD: A star is born nationally seeking stellar CD sales. Hollywood Reporter CCCLX, 13 (Nov. 1, 1999), 3. 2. Haitsma, J., Kalker, T., and Oostveen, J.
Robust audio hashing for content identifi- cation. In Proceedings of the International Workshop on Content-based Multimedia Indexing (Brescia, Italy, Sept. 19-21, 2001). 3. Herre, J., Allamanche, E., and Helmuth, O. Robust matching of audio signals using spectral flatness features. In Proceedings of the 2001 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (Mohonk, NY, 2001), 127-130.
4. Kenyon, S., Simkins, L., Brown, L., and Sebastian, R. U.S. Patent 4,450,531: Broadcast Signal Recognition System and Method. U.S. Patent and Trademark Office,
5. Wang, A. An industrial-strength audio search algorithm. In Proceedings of the Fourth International Conference on Music Information Retrieval (Baltimore, Oct. 26-30, 2003); www.ismir.net.
6. Wold, E., Blum, T., Keislar, D., and Wheaton, J. Content-based classification, search, and retrieval of audio. IEEE Multimedia 3, 3 (Fall 1996), 27-36. Avery Wang mailto:[email protected] （[email protected]）は，イギリス・ ロンドンのShazam Entertainment, Ltd. のチーフサイエンティストである． 訳：北原鉄朗（京都大学・情報学研究科）
