Shazamの仕組み（2022）
(cameronmacleod.com)- Shazamは、数秒間のマイク録音だけで曲を見つけるために、音声全体を比較するのではなく、オーディオフィンガープリントを作成してデータベースから検索する
- 波形をそのままスライドさせながら比較する方法は、1,000万曲規模とマイクノイズ、音量変化、周波数効果のため現実的ではない
- 中核となる流れは、音声をspectrogramに変換し、強い周波数のpeakを見つけ、そのpeakのペアをhashとして保存して高速に比較する方式
- peakはノイズがあっても比較的残りやすく、保存量も減らせるが、時間と周波数に均等に分布していないと曲のどの区間でも認識できない
- 認識段階では、一致したhashのTrack time - Sample timeの差をhistogramにまとめ、1つのbinに最も集中する曲を正解として選ぶ
Shazamが解くべき問題
- Shazamは、周囲で再生中の曲を数秒間録音したあと、データベースから探して結果を表示するアプリ
- アプリになる前のShazamは、電話番号ベースのサービスだった
- ユーザーは番号に電話をかけ、携帯電話のマイクを音楽の方へ向ける必要があった
- 30秒後、Shazamが通話を切り、聴いていた曲の情報をSMSで送ってきた
- 2002年当時の携帯電話の通話品質は、曲認識をさらに難しくしていた
- 小さな例であれば、音声断片をトラック全体の上で少しずつ移動させながら一致するか確認できる
- しかし、どの曲か分からない状態で1,000万曲のデータベースを検索すると、時間は大幅に増える
- 実際のマイクサンプルは、背景雑音、周波数効果、音量変化によって波形の形が変わることがあり、単純なスライド比較ではうまくいかない
システム全体の流れ
- Shazam方式は、registerとrecogniseの流れに分かれる
- registerは、後で見つけられるように曲を保存する流れ
- recogniseは、短い音声区間がどの曲かを見つける流れ
- どちらの流れも同じ前処理段階を通る
- 音声のspectrogramを計算
- spectrogramから最も強い周波数成分であるpeakを見つける
- peakをペアにしてhashを生成
- registerの流れでは、計算したhashをデータベースに保存する
- recogniseの流れでは、新しい音声から作ったhashをデータベース内のhashと比較し、matching段階で曲を識別する
Spectrogramの計算
- Fourier transformは、音声にどんな周波数が含まれているかを教えてくれる
- 20Hzのsine waveにFourier transformを適用すると、20Hz付近に大きなspikeが現れる
- sine waveは単一の周波数だけを含むため、pure toneとも呼ばれる
- Fourier transformの結果はfrequency spectrum
- 時間軸を中心にした表現はtime domain
- 周波数軸を中心にした表現はfrequency domain
- frequency spectrumのY軸は各周波数成分の強さを表し、強い成分ほどtime-domain信号でよりはっきり聞こえる
- 複数のsine waveを足し合わせると、各waveの周波数成分が結合される
- 20Hzのsine waveに半分の強さの50Hzのsine waveを足すと、20Hzのspikeと、より小さい50Hzのspikeが現れる
- すべての音声信号は、このようなwaveから再構成できる
- frequency domainは、time domainでは見えにくい情報を明らかにする
- ノイズが追加されてtime-domainの形が変わっても、frequency domainでは主要な周波数spikeが依然としてはっきりしていることがある
- 曲全体に一度だけFourier transformを適用すると、全体の周波数強度しか見えないが、実際の曲の周波数は時間とともに変化する
- 曲を小さな区間に分け、各区間にFourier transformを適用してからまとめるとspectrogramになる
- spectrogramは時間・周波数・強度を同時に表現し、強度は色で示せる
- 例の「Like a Stone」のspectrogramでは、最も明るい点、つまり強い周波数の大半が5000Hz以下に現れる
- 音楽ではこうした分布は一般的で、ピアノの周波数範囲の大半は27Hz-4186Hzである
Peakベースのフィンガープリント
- オーディオフィンガープリントは、spectrogramからpeakを見つけるところから始まる
- peakは、特定の時点で最も大きい周波数成分
- 音楽では、ギターソロの強い音のように、その時点で最も大きい音がpeakになることがある
- peakはノイズの影響を比較的受けにくい
- peakを認識できなくするには、ノイズがそのpeakより大きくなければならない
- spectrogramのpeakは、トラック内で最も強い周波数成分である
- peakだけを保存すると、フィンガープリントに必要なデータ量を減らせる
- すべての周波数情報を保存せず、最も大きい周波数成分だけを残す
- 検索対象のデータが減るため、フィンガープリント検索が高速になる
- peakは、時間と周波数の両方で均等に分布している必要がある
- 時間的に一方へ偏ると、曲の残りの区間のサンプルを認識できない
- 周波数帯域が狭く偏ると、クラクションのような特定帯域の大きな雑音がpeak選択を変えてしまい、その区間を見分けにくくなる
Maximum filterでpeakを見つける
- peakを均等に見つけるために、画像処理のmaximum filterという手法を使える
- maximum filterは、各pixelの周囲の近傍領域で最大値を探し、そのpixelをそのlocal maximum値に置き換える
- 例では、各pixelの周囲の3x3領域を見る方式
- この処理には、local peakを周辺領域へ広げる効果がある
- maximum filterをかけたspectrogramは、元のspectrogramの低解像度版のように見える
- 信号のpeakが広がって他のpixelを占めるため
- 同じ色のboxは、元画像の1つのlocal peakに対応する
- maximum filterには、local maximumを探すboxサイズのパラメータがある
- 小さいboxを使うとpeakは多くなる
- 大きいboxを使うとpeakは少なくなる
- peakの位置は、元のspectrogramとフィルタ後のspectrogramの値が同じ点を探すことで復元する
- peakでない点はlocal peak値に置き換わるため値が変わる
- 値がそのまま残った点だけがpeak
- すべてのpeakを集めて描くとconstellation mapになる
- 夜空の画像のように見えるため、この名前が付いている
- peak数はフィンガープリントのサイズに直接影響する
- 数百万曲を保存する必要があるなら、フィンガープリントを小さく保つことが重要
- peakを減らすと精度も下がり、サンプルを正しい曲にmatchingできる機会も減る
- peakを減らす方法は2つある
- 上位N個のpeakを使う方法で、Nは短い曲が過剰にサンプリングされないよう音声長に比例させるべき
- 特定のthresholdより大きいpeakをすべて使う方法で、時間あたりのフィンガープリントサイズは保証しないが、より正確なことがある
Peakのペアをhashにする
- フィンガープリントが単一のspectrogram peakの集まりだと、重複がすぐに増える
- 各peakの周波数を10bitで表現すると、2^10=1024個の個別周波数を表現できる
- トラックごとに数千の点があると、繰り返しが多くなる
- フィンガープリントでは固有性が重要
- 固有性が高いほど検索は速い
- より多くの曲を認識する助けになる
- Shazam方式では、単一のpeakではなくpeakのペアからhashを作る
- hashには、2つのpeakの周波数 fA、fB と、2つのpeakの時間差 ΔT が入る
- 各peakが10bitの周波数情報を持ち、ΔTも10bitで表現されるなら、合計30bitの情報になる
- 2^30=1,073,741,824通りの可能性は、単一ポイントの1024通りよりはるかに大きい
- ペア生成ではanchor pointとtarget zoneを使う
- 1つのpointをanchor pointとして選ぶ
- そのanchor pointに対するspectrogram target zoneを計算する
- target zone内のすべてのpointとanchor pointをペアにする
- Shazamの論文は、target zoneの選び方を詳しく説明していない
- 論文中の画像では、target zoneはanchor pointより少し後ろの時刻から始まり、anchor pointの周波数を中心に置かれている
- 生成したペアはhashとしてデータベースに保存される
- hashの構成要素は fA、fB、ΔT
- 追加情報として、Point A time と Track ID を保存する
- Point A time と Track ID は、後のmatchingで特定の曲の特定時点を見つけるために使われる
- あるトラックのすべてのhashの集合が、そのトラックのフィンガープリントになる
Matchingの方法
- recogniseの流れでは、sampleからフィンガープリントを作り、それをすでにデータベースに保存されているフィンガープリントと比較する
- matchingアルゴリズムは4段階で進む
- sample fingerprintと一致するすべてのhashをデータベースから取得する
- hashを曲ごとにgroup化する
- 各曲について、hashが時間的に整列しているか確認する
- 整列したhashが最も多いトラックを選ぶ
- abracadabraは、3-tupleである (fA, fB, ΔT) をそのまま検索せず、
hash(fA, fB, ΔT)が返す単一の値として保存する- hashごとに3つの値を検索する代わりに、1つの値を検索できる
- データベース内の各hashにはTrack IDが紐付いているため、曲ごとのgroup化が可能
- このようにgroup化した後、各候補トラックにスコアを付けられる
- sampleがある曲と一致するなら、sample内のhashは原曲のある区間にうまく整列しているはず
- ノイズは、sample内に別の時点のpeakのように見えるpeakを作ることがある
- hashが誤った曲と一致することもある
- 整列しているかどうかは、各matching hashについて Track time - Sample time の値を計算して確認する
- 本当にmatchingしているhashは、同じ差分値を共有する
- 例では、差分値10を持つ行がtrue matchで、他の差分値はfalse match
- 差分値からhistogramを作り、最も大きいbinをその曲のスコアとして使う
- 良いmatchでない曲は、どのbinの値も低い
- 良いmatchの曲は、1つのbinで大きなspikeが生じる
- 単純にmatching hash数が最も多い曲を選ばない理由は、曲長バイアスのため
- 長い曲は短い曲よりmatch数が多くなりやすい
- Spotifyには4時間を超えるトラックもあり、結果が大きく偏る可能性がある
abracadabraと参考資料
- abracadabra は、Shazam論文の方式を実装したオープンソースプロジェクト
- Pythonコードでspectrogram、peak検出、hashing、matchingの過程を追える
- 他のプロジェクトからlibraryとして使うこともできる
- 関連する実装と資料
- abracadabra docs: abracadabraのドキュメント
- dejavu: Pythonで書かれた別の曲認識実装
- Computer Vision for Music Identification: dejavu方式に似た曲認識アプローチ
- Chromaprint: やや異なるアプローチを使うアルゴリズム
- Musicbrainz: オープンソース音楽情報百科によるオーディオフィンガープリントの説明
- Playing with Shazam fingerprints: 2009年にShazamアルゴリズムを実装した経験談
- Alignment of videos of same event using audio fingerprinting: 音楽を超えて、同じイベント映像の整列にオーディオフィンガープリントを使った例
1件のコメント
Hacker News の意見
Wall Street Journal が Shazam を説明したよくできた動画がある
https://www.wsj.com/video/series/in-depth-features/how-shaza...
Chris、Shazam 共同創業者
Lawn Love は 2014〜2018 年にその上階のスイートを借りていたが、そのオフィスにいた Shazam モバイルアプリ開発者たちは買収後も静かにしていて、祝杯のシャンパンの音も聞いたことがなかった
Shazam が 2008 年に登場したとき、ハッシュベースのアプローチは賢い選択だった
自分なら、まず全曲をできるだけ計算効率よくハッシュに変換する方法を作っただろう
もし今日リリースしていたら、研究開発の基本方針はモデル学習になっていただろうが、はるかに効率が悪く、ホスティング費用もより高くついたかもしれない
モデルが得意そうに感じられる問題ではあるが、曲数が有限である点ではハッシュ方式のほうがずっと性能がよい可能性が高い
短いサンプルから得られる数十個、多くても低い数百個程度のハッシュが、どれだけ多く、概ね連続して一致するかを探す仕組みである
今日でもモデル学習ではやらないと思う。毎日膨大な数の新曲が追加されるため、継続的に再学習しなければならないからだ
ハッシュは効率だけでなく、全体的な堅牢性の面でも依然としてよりよいアプローチに見える
その後、辞書で単語を探すように曲を探せた。このアイデアが簡単に消えてしまわないでほしい
[1]: https://en.wikipedia.org/wiki/Parsons_code
最初の携帯電話アプリは 2006 年の BREW 向けだった
2008 年は Apple が App Store をリリースした時点にすぎず、それ以前はサードパーティが iPhone アプリを作ることはできなかった
どちらも優れたインデックス化と圧縮の解法であり、ただデータ規模が違うだけだ
新曲ごとに完全な再学習なしで埋め込みベクトルを計算できる埋め込みモデルを作る方法があるのかもしれない
Shazam は 20 年間、魔法のような感覚が失われていない珍しい製品である
技術者が目指すべきものに本当に近い
動物や物体の画像認識のように、表面的には似ているが大半は奇妙な機械学習の魔法に近い機能とは異なり、珍しいが理解可能な問題領域にうまく当てはまる
以前の世代の iPhone では時間内にロードすらできず、結局アプリを削除した記憶がある
Now Playing 機能は常に曲を検出して履歴に残し、Google Assistant では鼻歌だけでも曲を検索できる
安定して動作するわけではないが、ときどき正確に当てる
America’s Got Talent で誰かが歌っていた曲を探そうとしたら、結果が AGT に出ていたその歌手として返ってきて驚いた
テレビ番組までインデックスしているのかと思った
だがプロダクトマネージャーは、ボーナスと休暇を得るために製品を壊し続けないなら、ほかに何をするというのか
Chromaprint もあり、少し違う方式で動作する
スペクトルの最大値ではなく、音高の変化パターンに基づいている
Chromaprint は、オーディオフィンガープリントと MusicBrainz の録音を結びつける大規模な公開データベース AcoustID で使われている
Shazam ほど商業的支援が多くないにもかかわらず、その中に非常に多くの音楽がある点は驚きだ
[1]: https://oxygene.sk/2011/01/how-does-chromaprint-work/
重複検出にはよいが、Shazam のフィンガープリント設計は短い断片を曲全体にマッチできるようにしている
スペクトログラムが何をしているのかをよく捉えた優れた記事であり、オーディオフィンガープリント抽出がどのように動作するかを理解したい人には必読に近い
他の媒体にも似た近似アルゴリズムがあるので、現実世界のハッシュを理解するには、この記事をじっくり学ぶ価値がある
Shazam が行ったのは、偽陽性を減らすために組み合わせ的にハッシュ化したことだ
曲ではなく、ジャンル分類と新曲のシグネチャが生み出すサブジャンルの分岐をアルゴリズムによるマッチングで扱う、優れたサイトがあります。
個人のサイドプロジェクトとして運営されている驚くべき資料ですが、ホスティングの問題などで消えてしまう危険がありそうです。
以前はPandoraのMusic DNAやLastFMの似たような機能がありましたが、このサイトは2023年までに人類が作った音楽全体の視覚的なつながりのネットワークのようなもので、消えればWeb全体の損失になるでしょう。
Every Noise At Once
https://everynoise.com
Every Noise at Once - https://news.ycombinator.com/item?id=26668426 - 2021年4月、コメント94件
Every Noise at Once - https://news.ycombinator.com/item?id=20585447 - 2019年8月、コメント82件
Every Noise at Once – an algorithmically-generated scatter-plot of musical genre - https://news.ycombinator.com/item?id=10269685 - 2015年9月、コメント23件
An algorithmically-generated scatter-plot of musical genres - with samples - https://news.ycombinator.com/item?id=9315499 - 2015年4月、コメント3件
Spotifyにいたときはジャンル研究者でした。
似た曲を表示してくれますが、かなりよくできていると思います。
この方式がどれほど直感的で、私たち自身の認識プロセスとどれほどよく合っているかには驚かされます。
ざっくり言えば、メロディの断片を識別してから、それらを順番に照合していく方式です。
私たちが5個、7個、10個の音を聞いただけでも何かに気づくのと似ています。
音量のピークのようなものに依存する別の楽曲フィンガープリント抽出方式も読んだ気がしますが、そうした方式も同じくらいうまく動作し得るとしても、私たちの脳が行う方式とはまったく合っていません。
この方式は「人工的な副産物」に頼るのではなく、基本的に私たちが行っていることに近い形で動作するので、かなり見事です。
技術的には常にメロディとは限りませんが、大半はメロディである可能性が高いです。
Shazamが時間軸が線形でない、または一定でない場合をどう処理しているのか気になります。
テープ、ワウ・フラッター、ずっと速くなったり遅くなったりするような状況です。
私の知る限り、フィンガープリント抽出は時間に非常に敏感で、50ms程度の断片に切っても完全には解決しません。
最後に見たとき、この種の問題の一般的な手法である動的時間伸縮法（Dynamic Time Warping）は計算コストが高すぎました。
関連記事。ほかにもあれば気になります
How Shazam Works (2003 Paper) - https://news.ycombinator.com/item?id=33299853 - 2022年10月、コメント1件
Creating Shazam in Java (2010) - https://news.ycombinator.com/item?id=32530056 - 2022年8月、コメント36件
Shazam turns 20 - https://news.ycombinator.com/item?id=32520593 - 2022年8月、コメント227件
How Shazam Works (2015) - https://news.ycombinator.com/item?id=23806142 - 2020年7月、コメント7件
Designing an audio adblocker - https://news.ycombinator.com/item?id=18855029 - 2019年1月、コメント186件
Show HN: A radio/podcast adblocker featuring ML and Shazam-like fingerprinting - https://news.ycombinator.com/item?id=18459058 - 2018年11月、コメント2件
Show HN: Shazam-like acoustic fingerprinting of continuous audio streams - https://news.ycombinator.com/item?id=15809291 - 2017年11月、コメント76件
How Shazam Works (2015) - https://news.ycombinator.com/item?id=15350729 - 2017年9月、コメント13件
Tell HN: Shazam picks up song from my kitchen light - https://news.ycombinator.com/item?id=11593305 - 2016年4月、コメント2件
How Shazam works - https://news.ycombinator.com/item?id=9870408 - 2015年7月、コメント48件
Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 - 2015年5月、コメント18件
The Shazam Effect (2014) - https://news.ycombinator.com/item?id=9593429 - 2015年5月、コメント37件
The Shazam Effect - https://news.ycombinator.com/item?id=8634357 - 2014年11月、コメント34件
Ask HN: Is there an audio search technology that finds exact and similar audio? - https://news.ycombinator.com/item?id=8420141 - 2014年10月、コメント3件
Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724422 - 2013年5月、コメント16件
Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 - 2013年5月、コメント43件
An Industrial-Strength Audio Search Algorithm (Shazam) - https://news.ycombinator.com/item?id=2621103 - 2011年6月、コメント4件
Shazam's Search for Songs Creates New Music Jobs - https://news.ycombinator.com/item?id=2215295 - 2011年2月、コメント1件
How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=2214992 - 2011年2月、コメント2件
Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 - 2010年9月、コメント23件
Shazam: not magic after all - https://news.ycombinator.com/item?id=909263 - 2009年10月、コメント28件
How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=893353 - 2009年10月、コメント16件