Shazamのしくみをちょっと理解してみる

Tweet

アップルのSiriにも組み込まれてる音楽検索システムShazam、とても優秀ですよね。

Shazamなどがやってる仕事は一般的にAudio fingerprintingと呼ばれてます。強いノイズやダウンサンプリング、クエリ音声の短さ、膨大なデータベースに対する検索スピードの要求等、高いハードルを克服して楽曲をズバリ特定することが求められ、とても困難そうに見えますが、現在すでに業務レベルのパフォーマンスに達しているのは驚くべきことです。

もちろんShazamの完全な技術が公開されてるわけないですが、Shazamの基本技術となるLandmark-based fingerprintingを実装したシステムはgithubで公開されてます。

https://github.com/dpwe/audfprint

元論文はこれ

A. Wang, An Industrial-Strength Audio Search Algorithm

もともとは教育用としてMATLABで書いてたものを、２０１４年からpythonで再実装し始めたものだそうです。

このaudfprintのソースコードをちょっと読んで、基本的な仕組みを探って見ました。

ソースコードと論文をもとに、順を追って説明してみましょう。（図形は論文から切り取ったものです）

スペクトラムピークの抽出

データベースへの登録もクエリも、フィンガープリントを抽出する手順は共通です。ソースコードはaudfprint_analyze.pyのAnalyzerクラスを参照(おもにfind_peaks())。

まず、音声が来たら普通にSTFTします。求まったスペクトログラムを対数域に変換して、平均値を引いたりしてピークを強調させます。そしてピークの位置（周波数と時間）を記録。

一般的にエネルギーが高い所ほどノイズなどに強いし、ピークなので位置も安定しているので、ピーク点を基点としたアプローチは高いロバスト性が期待できます。

ランドマークとハッシュの構築

同じくAnalyzerクラスのpeaks2landmarks()メソッドを参照。

抽出されたピークは、近くにあるもの同士（具体的には図のように、あるピークを基準にして、そのピークとの時間、周波数の距離が一定範囲内のピークとの間）を連結して、ペアとします。これを「ランドマーク」と呼んでます。一つのランドマークは、<f1, f2, deltatime>という形で表示できます（deltatimeはペア間の時間距離）。これをつなげてハッシュ値とし、曲のIDとランドマークの起点位置をそれに関連付けて保存（クエリの場合はマッチングに使う）。

単独のピークは情報が足りない。しかしピークをペアで保存、ハッシュ化することで情報量が一気に上がります。

ハッシュのマッチング

保存したランドマークと同じものがクエリ音声のものと一致すれば、ハッシュテーブルを通じてすぐに該当の作品にたどり着けます。マッチングの手順はaudfprint_match.pyのMatcherクラスに記述されてます。

ただ、一つのハッシュ値に関連付けられてる作品は一つとは限らないし、ランドマーク自身の表現力も限界があるので、やはりクエリ音声と違う作品とも、たくさんのマッチを生み出してしまいます。その中からどう選べばいいんでしょう。

そこは、論文を読んだ方が分かりやすいんですが、マッチしたランドマークのペアを、（元音声での時刻、クエリ音声での時刻）の二次元平面に展開します。すると、クエリと元音声がマッチしない場合は、こんな風になります。バラバラ。

一方、マッチする場合はこう。x軸の４０の所から点が一直線に並んでます。

こんな風に、マッチする部分では、点が主対角線方向（傾斜率が１の線）に並びます。このように並んでいるということは、一定時間内に持続的に特徴量が一致していることをあらわしますので、当たりとみなすことができます。

これを数値的に評価する方法は極めて簡単。上述の平面上のすべての点において、x軸とy軸の値の差を求め、その差の値でヒストグラムを求めます。同じ線の上に並んでいる点は、(直線x-y=b上にあるため)x、yの差は定数なので、一列に並んだ点が多ければ、ヒストグラムの特定の値が押し上げられます。

前述の、マッチされていない例では、ヒストグラムはこう。

一方、マッチしている例ではこう。直線x-y=40上の点が多いようです。

ヒストグラムの最大値をマッチのスコアとみなせば、最終的な判断ができます。

実際ソースコードはもうちょっと複雑な仕事をしてるみたいですがよくわかんないので今回はスルー。

しかしaudfprintのソースコードではこのような基準で数えていないようで、単純にペアの元音声の時刻（x軸の値）だけを取って、一定間隔に並んでいるサブセットの長さだけで判断してるように見えます（ソースコードの注釈曰く、time-consistent matching hashesを数える）。

実験

では、このコードを走らせて遊んでみましょう。

データベースは、とりあえず、自分のiTunesライブラリにあるブツを全部放り込んでやります。全部で６９８曲あるそうです。

取り込みにかかる時間は一曲ごとに2、3秒くらい。出来上がったハッシュのデータベースのサイズは12.4MBと結構コンパクト。

そして、クエリの録音。自分のiPadで再生させて、PCのマイクで録りました。静かな室内で7個、昼の学食で6個、各クエリは約10秒録りました。

その一部はこちら。

静かな場所で録った「孤独の果て」（光収容）

静かな場所で録った「未完」(ミスチル)

三日月の舞、ソロパートオーディション香織版in学食

三日月の舞、ソロパートオーディション麗奈版in学食

「運命の流れ」in学食

軽く「響け！ユーフォニアム」推しですがお気になさらず。

結果はいかに。

静かな室内版は、全問正解です。

学食版は、ユーフォのOSTにあるピアノ曲「運命の流れ」がマッチを見つけることができませんでした。それ以外は正解。

両方とも、三日月の舞の二つのソロパートで試してみたところに注目。香織と麗奈の演奏の違いがしっかり区別されてますね。

感想

人が完成させたコードで遊ぶのは楽しい（爆）

Shazamが出てきたときは本当に「未来きてる」という感じの衝撃だったのですが、原理を紐解いてみると案外分かりやすいものでした。単に簡単というわけではなく、とても巧妙で、エレガントで、奇麗。

だいたい技術のブレイクスルーは、「分かってしまえば結構自明で簡単なもの」というパターンが多いんですよね。この技術も、その一例と言えるでしょう。

MIRのほかの分野でも、どんな手法がブレイクスルーをもたらすのか、楽しみですね。