Shazamはどのように機能しますか？ 音楽認識アルゴリズム、指紋、および処理

クラブやレストランでおなじみの歌が聞こえます。 あなたは千回も前にこの曲を聴いていましたが、この曲の感傷は本当にあなたの心に響きます。 明日は必死に心を込めたいのですが、名前が思い出せません！ 幸いなことに、私たちの驚くべき未来の世界では、音楽認識ソフトウェアがインストールされた電話があり、あなたは救われています。 ソフトウェアが曲の名前を教えてくれたので、リラックスすることができます。そして、それがあなたの一部になるまで、またはあなたがそれにうんざりするまで、何度も何度もそれを聞くことができることを知っています。

モバイルテクノロジーは、オーディオ信号処理の大きな進歩とともに、アルゴリズム開発者に音楽認識機能を作成する機能を提供してきました。 最も人気のある音楽認識アプリの1つはShazamです。 イントロ、バース、コーラスに関係なく、曲の20秒をキャプチャすると、録音されたサンプルのフィンガープリントが作成され、データベースが参照され、音楽認識アルゴリズムを使用して、聴いている曲が正確にわかります。 。

しかし、Shazamはどのように機能しますか？ Shazamのアルゴリズムは、2003年に発明者のAvery Li-Chung Wangによって世界に公開されました。この記事では、Shazamの音楽認識アルゴリズムの基本について説明します。

アナログ-デジタル-信号のサンプリング

本当に音ってなに？ 触れることはできないが、耳に飛び込んで物事を聞かせるような神秘的な素材なのだろうか？

もちろん、これは完全には当てはまりません。 実際には、音は空気や水などの媒体を介して、圧力と変位の力学的波として伝播する振動であることがわかっています。 その振動が私たちの耳、特に鼓膜に来ると、それは小さな骨を動かし、それが内耳の奥深くにある小さな有毛細胞に振動をさらに伝達します。 最後に、小さな有毛細胞は電気インパルスを生成し、それが聴覚耳神経を介して私たちの脳に伝達されます。

録音デバイスは、音波の圧力を使用して音波を電気信号に変換し、このプロセスをかなり厳密に模倣します。 空気中の実際の音波は、連続的な圧力信号です。 マイクでは、この信号に最初に遭遇した電気部品が、この信号をアナログ電圧信号に変換します。これも連続しています。 この連続信号はデジタルの世界ではあまり有用ではないため、処理する前に、デジタルで保存できる離散信号に変換する必要があります。 これは、信号の振幅を表すデジタル値をキャプチャすることによって行われます。

変換には入力の量子化が含まれ、必然的に少量のエラーが発生します。 したがって、単一の変換の代わりに、アナログ-デジタル変換器は信号の非常に小さな部分で多くの変換を実行します-サンプリングとして知られているプロセス

ナイキスト-シャノンの定理は、連続信号で特定の周波数をキャプチャするために必要なサンプリングレートを示しています。 特に、人間が音声信号で聞くことができるすべての周波数をキャプチャするには、人間の可聴範囲の2倍の周波数で信号をサンプリングする必要があります。 人間の耳は、およそ20 Hz〜20,000Hzの周波数を検出できます。 その結果、オーディオはほとんどの場合44,100Hzのサンプリングレートで録音されます。 これはコンパクトディスクのサンプリングレートであり、MPEG-1オーディオ（VCD、SVCD、MP3）で最も一般的に使用されるレートでもあります。 （この特定のレートは、25フレーム/秒（PAL）または30フレーム/秒（NTSCモノクロビデオレコーダーを使用）で動作する変更されたビデオ機器で記録でき、必要と思われる20,000 Hzの帯域幅をカバーできるため、元々ソニーによって選択されました。当時のプロのアナログ録音機器と一致します。）したがって、録音する必要のあるサンプルの周波数を選択するときは、おそらく44,100Hzを使用することをお勧めします。

録音-サウンドのキャプチャ

サンプリングされたオーディオ信号の録音は簡単です。 最新のサウンドカードにはすでにアナログ-デジタルコンバーターが付属しているため、プログラミング言語を選択し、適切なライブラリを見つけ、サンプルの周波数、チャンネル数（通常はモノラルまたはステレオ）、サンプルサイズ（16ビットサンプルなど）を設定するだけです。 ）。 次に、他の入力ストリームと同じようにサウンドカードから行を開き、バイト配列に書き込みます。 これをJavaで行う方法は次のとおりです。

 private AudioFormat getFormat() { float sampleRate = 44100; int sampleSizeInBits = 16; int channels = 1; //mono boolean signed = true; //Indicates whether the data is signed or unsigned boolean bigEndian = true; //Indicates whether the audio data is stored in big-endian or little-endian order return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian); } final AudioFormat format = getFormat(); //Fill AudioFormat with the settings DataLine.Info info = new DataLine.Info(TargetDataLine.class, format); final TargetDataLine line = (TargetDataLine) AudioSystem.getLine(info); line.open(format); line.start();

TargetDataLineからデータを読み取るだけです。 （この例では、 running中のフラグはグローバル変数であり、別のスレッドによって停止されます。たとえば、STOPボタンのあるGUIがある場合です。）

 OutputStream out = new ByteArrayOutputStream(); running = true; try { while (running) { int count = line.read(buffer, 0, buffer.length); if (count > 0) { out.write(buffer, 0, count); } } out.close(); } catch (IOException e) { System.err.println("I/O problems: " + e); System.exit(-1); }

時間領域と周波数領域

このバイト配列にあるのは、時間領域で記録された信号です。 時間領域信号は、時間の経過に伴う信号の振幅変化を表します。

1800年代初頭、ジャンバプティストジョセフフーリエは、各成分の正弦波が特定の周波数、振幅、とフェーズ。 元の時間領域信号を一緒に形成する一連の正弦波は、そのフーリエ級数として知られています。

言い換えると、信号を構成する各正弦波に対応する周波数、振幅、および位相のセットを与えるだけで、任意の時間領域信号を表すことができます。 信号のこの表現は、周波数領域として知られています。 ある意味で、周波数領域は時間領域信号の一種のフィンガープリントまたはシグニチャとして機能し、動的信号の静的表現を提供します。

次のアニメーションは、1 Hzの方形波のフーリエ級数と、正弦波成分から（近似）方形波を生成する方法を示しています。 信号は上の時間領域と下の周波数領域に示されています。

周波数領域で信号を分析すると、多くのことが非常に簡単になります。 エンジニアはスペクトル（周波数領域での信号の表現）を調べて、どの周波数が存在し、どの周波数が欠落しているかを判断できるため、デジタル信号処理の世界ではより便利です。 その後、フィルタリングを行ったり、一部の周波数を増減したり、特定の周波数から正確なトーンを認識したりすることができます。

離散フーリエ変換

したがって、信号を時間領域から周波数領域に変換する方法を見つける必要があります。 ここでは、離散フーリエ変換（DFT）に助けを求めます。 DFTは、離散（サンプリング）信号に対してフーリエ解析を実行するための数学的方法論です。 関数の等間隔のサンプルの有限リストを、それらの正弦波が同じレートでサンプリングされたかどうかを考慮して、周波数順に並べられた複雑な正弦波の有限の組み合わせの係数のリストに変換します。

DFTを計算するための最も一般的な数値アルゴリズムの1つは、高速フーリエ変換（FFT）です。 FFTの最も一般的に使用されるバリエーションは、Cooley-Tukeyアルゴリズムです。 これは分割統治アルゴリズムであり、DFTを多数の小さなDFTに再帰的に分割します。 DFTを直接評価するにはO（ n 2 ）演算が必要ですが、Cooley-Tukey FFTでは、同じ結果がO（ n log n ）演算で計算されます。

FFTに適したライブラリを見つけるのは難しくありません。 それらのいくつかはここにあります：

• C – FFTW
• C ++ – EigenFFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3（FFTWへのインターフェース）

以下は、Javaで記述されたFFT関数の例です。 （FFTは複素数を入力として受け取ります。複素数と三角関数の関係を理解するには、オイラーの公式について読んでください。）

 public static Complex[] fft(Complex[] x) { int N = x.length; // fft of even terms Complex[] even = new Complex[N / 2]; for (int k = 0; k < N / 2; k++) { even[k] = x[2 * k]; } Complex[] q = fft(even); // fft of odd terms Complex[] odd = even; // reuse the array for (int k = 0; k < N / 2; k++) { odd[k] = x[2 * k + 1]; } Complex[] r = fft(odd); // combine Complex[] y = new Complex[N]; for (int k = 0; k < N / 2; k++) { double kth = -2 * k * Math.PI / N; Complex wk = new Complex(Math.cos(kth), Math.sin(kth)); y[k] = q[k].plus(wk.times(r[k])); y[k + N / 2] = q[k].minus(wk.times(r[k])); } return y; }

そして、これがFFT分析の前後の信号の例です。

音楽認識：曲の指紋認証

FFTの不幸な副作用の1つは、タイミングに関する多くの情報が失われることです。 （理論的にはこれを回避できますが、パフォーマンスのオーバーヘッドは膨大です。）3分間の曲の場合、すべての周波数とその大きさがわかりますが、曲に登場したときの手がかりはありません。 しかし、これは曲をそれが何であるかを作る重要な情報です！ どういうわけか、各周波数がどの時点で出現したかを知る必要があります。

そのため、一種のスライディングウィンドウ、つまりデータのチャンクを導入し、情報のこの部分だけを変換します。 各チャンクのサイズは、いくつかの異なる方法で決定できます。 たとえば、ステレオで16ビットサンプルを使用して44,100 Hzでサウンドを録音すると、そのようなサウンドの1秒は44,100サンプル*2バイト*2チャネル≈176kBになります。 チャンクのサイズとして4kBを選択すると、曲の1秒ごとに分析するデータのチャンクが44個あります。 これは、音声識別に必要な詳細な分析に十分な密度です。

プログラミングに戻りましょう。

 byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i < sampledChunkSize; j++) { Complex[chunkSize] complexArray; for(int i = 0; i < chunkSize; i++) { complexArray[i] = Complex(audio[(j*chunkSize)+i], 0); } result[j] = FFT.fft(complexArray); }

内側のループでは、時間領域データ（サンプル）を虚数部0の複素数に入れています。外側のループでは、すべてのチャンクを反復処理し、それぞれに対してFFT分析を実行します。

信号の周波数構成に関する情報が得られたら、曲のデジタル指紋の作成を開始できます。 これは、Shazamオーディオ認識プロセス全体の中で最も重要な部分です。 ここでの主な課題は、キャプチャされた周波数の海で、どの周波数が最も重要であるかをどのように区別するかです。 直感的に、最大の大きさの周波数（一般にピークと呼ばれます）を検索します。

ただし、1つの曲では、強い周波数の範囲が低C-C1（32.70 Hz）と高C-C8（4,186.01 Hz）の間で異なる場合があります。 これはカバーするための巨大な間隔です。 したがって、周波数範囲全体を一度に分析する代わりに、重要な音楽コンポーネントの共通の周波数に基づいて選択されたいくつかの小さな間隔を選択し、それぞれを個別に分析することができます。 たとえば、この男がShazamアルゴリズムの実装に選択した間隔を使用する場合があります。 これらは、低音（ベースギターなどをカバー）の場合は30 Hz〜40 Hz、40 Hz〜80 Hz、80 Hz〜120 Hz、中音および高音の場合は120 Hz〜180Hzおよび180Hz〜300Hzです。 （ボーカルや他のほとんどの楽器をカバーしています）。

これで、各間隔内で、最大の大きさの周波数を簡単に識別できます。 この情報は、曲のこのチャンクの署名を形成し、この署名は、曲全体のフィンガープリントの一部になります。

 public final int[] RANGE = new int[] { 40, 80, 120, 180, 300 }; // find out in which range is frequency public int getIndex(int freq) { int i = 0; while (RANGE[i] < freq) i++; return i; } // result is complex matrix obtained in previous step for (int t = 0; t < result.length; t++) { for (int freq = 40; freq < 300 ; freq++) { // Get the magnitude: double mag = Math.log(results[t][freq].abs() + 1); // Find out which range we are in: int index = getIndex(freq); // Save the highest magnitude and corresponding frequency: if (mag > highscores[t][index]) { points[t][index] = freq; } } // form hash tag long h = hash(points[t][0], points[t][1], points[t][2], points[t][3]); } private static final int FUZ_FACTOR = 2; private long hash(long p1, long p2, long p3, long p4) { return (p4 - (p4 % FUZ_FACTOR)) * 100000000 + (p3 - (p3 % FUZ_FACTOR)) * 100000 + (p2 - (p2 % FUZ_FACTOR)) * 100 + (p1 - (p1 % FUZ_FACTOR)); }

録音は完璧な状態（つまり、「聴覚障害者の部屋」）で行われていないと想定する必要があり、その結果、ファズファクターを含める必要があることに注意してください。 ファズファクター分析は真剣に受け止められるべきであり、実際のシステムでは、プログラムは録音の条件に基づいてこのパラメーターを設定するオプションを持っている必要があります。

オーディオ検索を簡単にするために、この署名がハッシュテーブルのキーになります。 対応する値は、この周波数のセットが曲に表示された時間と、曲ID（曲のタイトルとアーティスト）です。 これらのレコードがデータベースにどのように表示されるかの例を次に示します。

この音楽識別プロセスを通じて曲のライブラリ全体を実行すると、ライブラリ内のすべての曲の完全なフィンガープリントを使用してデータベースを構築できます。

音楽アルゴリズム：曲の識別

クラブで現在再生されている曲を識別するために、携帯電話で曲を録音し、上記と同じオーディオフィンガープリントプロセスで録音を実行します。 次に、一致するハッシュタグをデータベースで検索し始めます。

たまたま、ハッシュタグの多くは複数の曲の音楽識別子に対応します。 たとえば、曲Aの一部が曲Eの一部とまったく同じように聞こえる場合があります。もちろん、これは驚くべきことではありません。ミュージシャンは常にお互いからリックやリフを「借り」ており、最近ではプロデューサーが他の曲をすべてサンプリングしています。時間。 ハッシュタグを照合するたびに、一致する可能性のある数は少なくなりますが、この情報だけでは、一致を1つの曲に絞り込むことはできない可能性があります。 したがって、音楽認識アルゴリズムで確認する必要があるもう1つのことがあります。それは、タイミングです。

クラブで録音したサンプルは曲のどの時点からのものである可能性があるため、一致したハッシュのタイムスタンプをサンプルのタイムスタンプと単純に一致させることはできません。 ただし、複数の一致するハッシュを使用すると、一致の相対的なタイミングを分析できるため、確実性が高まります。

たとえば、上の表を見ると、ハッシュタグ30 51 99 121 195がソングAとソングEの両方に対応していることがわかります。1秒後にハッシュ34 57 95 111 200と一致すると、それはもう1つになります。曲Aと一致しますが、この場合、ハッシュと時差の両方が一致することがわかります。

 // Class that represents specific moment in a song private class DataPoint { private int time; private int songId; public DataPoint(int songId, int time) { this.songId = songId; this.time = time; } public int getTime() { return time; } public int getSongId() { return songId; } }

録音された曲の瞬間としてi1とi2を取り、データベースからの曲の瞬間としてj1とj2を取りましょう。 次の場合、時差が一致する2つの一致があると言えます。

<span style = font-family：TimesNewRoman;> RecordedHash（i 1 ）= SongInDBHash（j 1 ）AND RecordedHash（i 2 ）= SongInDBHash（j 2 ） </ span>

<span style = font-family：TimesNewRoman;> AND </ span>

<span style = font-family：TimesNewRoman;> abs（i 1 -i 2 ）= abs（j 1 -j 2 ） </ span>

これにより、曲の最初、途中、または最後から録音する柔軟性が得られます。

最後に、クラブで録音した曲のすべての瞬間が、スタジオで録音されたライブラリ内の同じ曲の対応するすべての瞬間と一致する可能性はほとんどありません。 録音には多くのノイズが含まれているため、試合でエラーが発生します。 したがって、一致リストから正しい曲を除くすべてを削除しようとするのではなく、最後に、一致したすべての曲を可能性の高い順に並べ替えます。お気に入りはランキングリストの最初の曲です。

上から下まで

「Shazamはどのように機能しますか？」という質問に答えるために。 音楽認識とマッチングのプロセス全体の概要を上から下に示します。

この種のシステムでは、データベースがかなり巨大になる可能性があるため、ある種のスケーラブルなデータベースを使用することが重要です。 リレーションは特別に必要ではなく、データモデルは非常に単純になるため、ある種のNoSQLデータベースを使用する場合に適しています。

Shazamはどのように機能しますか？ 今あなたは知っています

この種の曲認識ソフトウェアは、曲間の類似点を見つけるために使用できます。 Shazamがどのように機能するかを理解したので、タクシーのラジオで再生されているノスタルジックな曲を単にShazamingするだけでなく、これがどのようにアプリケーションに使用できるかを理解できます。 たとえば、音楽の盗作を特定したり、ブルース、ジャズ、ロック、ポップ、その他のジャンルのパイオニアに最初にインスピレーションを与えたのは誰かを見つけるのに役立ちます。 たぶん、良い実験は、曲のサンプルデータベースをバッハ、ベートーベン、ヴィヴァルディ、ワーグナー、ショパン、モーツァルトのクラシック音楽で埋めて、曲間の類似点を見つけてみることです。 ボブ・ディラン、エルビス・プレスリー、ロバート・ジョンソンでさえ盗作者だと思うでしょう！

しかし、それでも私たちは彼らを有罪にすることはできません。なぜなら、音楽は私たちが耳にし、記憶し、頭の中で繰り返す波であり、スタジオで録音して次の偉大な音楽の天才に引き継ぐまで進化し、変化するからです。