Shazam：音楽認識アルゴリズム、署名、データ処理

ほとんど忘れられていた歌がレストランで流れ始めました。 あなたは遠い昔に彼女に耳を傾けました。 感動的な記憶がどれだけ和音や言葉を引き起こす可能性がありますか...あなたは必死にこの歌をもう一度聴きたいと思いますが、その名前は頭から完全に飛び出しました！ になる方法 幸いなことに、私たちの素晴らしいハイテクの世界では、この質問に対する答えがあります。

あなたのポケットには、音楽を認識するためのプログラムがインストールされているスマートフォンがあります。 このプログラムはあなたの救世主です。 曲の名前を見つけるために、自分の記憶から大切な行を抽出するために隅から隅まで移動する必要はありません。 そして、それがうまくいくという事実ではありません。 プログラムは、音楽を「聞く」と、すぐに作曲の名前を知らせます。 その後、心に優しい音を何度も聞くことができるようになります。 彼らがあなたと一つになるまで、またはあなたがそれのすべてに飽きるまで。


モバイルテクノロジーとサウンド処理の分野における驚くべき進歩により、 アルゴリズム開発者は音楽作品を認識するためのアプリケーションを作成できます。 この種の最も一般的なソリューションの1つはShazamと呼ばれます。 20秒のサウンドを与える場合、イントロ、コーラス、または主要な動機の一部であるかどうかは関係ありません。Shazamは署名コードを作成し、データベースをチェックし、独自の音楽認識アルゴリズムを使用して作品の名前を伝えます。

これはどのように機能しますか？
2003年の基本的なShazamアルゴリズムの説明は、作成者のAvery Li-Chung Wangによって公開されました。 この記事では、Shazam音楽認識アルゴリズムの基本を詳細に分析します。

アナログからデジタルへ：離散化

本当に音とは何ですか？ たぶん、これは私たちの耳に浸透し、私たちが聞くことを可能にする不思議な体内物質ですか？

もちろん、すべてがそれほど神秘的ではありません。 音は、弾性波の形で固体、液体、気体の媒体を伝播する機械的振動であることが長い間知られています。 波が耳、特に鼓膜に到達すると、耳小骨が動き始め、それが振動をさらに内耳にある有毛細胞に伝えます。 その結果、機械的振動は電気インパルスに変換され、それが聴覚神経を介して脳に伝達されます。

録音デバイスは、上記のプロセスを非常に正確に模倣し、音波の圧力を電気信号に変換します。 空気中の音波は、圧縮と希薄化の領域で表される連続信号です。 マイクは、音声信号が最初に遭遇する電子部品であり、それを電気信号に変換しますが、電気信号は依然として連続しています。 デジタルの世界では、このような信号は特に有用ではないため、デジタルシステムに保存して処理する前に、 個別の形式に変換する必要があります。 これは、信号の振幅を表す値をサンプリングすることにより行われます。

そのような変換の過程で、アナログ信号の量子化が行われます。 少数のエラーなしではできません。 したがって、同時変換を処理するのではなく、 A / Dコンバーターが多くの操作を実行して、アナログ信号のごく一部をデジタルに変換します。 このプロセスは、 サンプリングまたはサンプリングと呼ばれます。


アナログ（連続）およびデジタル（離散）信号

コテルニコフの定理により、特定の周波数に制限された連続信号を正確に表すために必要なサンプリング周波数がわかります。 特に、人間の耳に聞こえる音の周波数スペクトル全体をキャプチャするには、人間が聞く周波数の上限の2倍のサンプリング周波数を使用する必要があります。

すなわち、人は約20Hzから20,000Hzの範囲の音を聞くことができます。 その結果、ほとんどの場合、音は44100 Hzのサンプリング周波数で記録されます。 CDで使用されるのはこのサンプリングレートです。 MPEG-1標準のグループ（ VCD 、 SVCD 、 MP3 ）のサウンドのエンコードに最もよく使用されます。

44100 Hzのサンプリング周波数の普及は、主にソニー株式会社によるものです。 かつて、この方法でエンコードされたオーディオトラックは、 PAL （25フレーム/秒）およびNTSC （30フレーム/秒） 規格のビデオと組み合わせて既存の機器を使用して作業するのに便利でした。 また、この周波数が最大20,000 Hzの範囲で高品質の音声伝送に十分であることも非常に重要です。 このサンプリングレートを使用するデジタルオーディオ機器は、デジタルサウンド標準が出現した当時のアナログ機器と比べて高品質でした。 その結果、録音中にサウンドのサンプリング周波数を選択すると、ほとんどの場合44100 Hzで停止します。

録音：オーディオキャプチャ

サンプリングされたサウンドの録音は、かなり簡単な作業です。 最新のサウンドカードには、アナログ-デジタルコンバーターが組み込まれています。 そのため、プログラミング言語を選択し、サウンドを操作するのに適したライブラリを見つけ、サンプリング周波数、チャンネル数（通常、モノラルおよびステレオサウンドの場合は通常1つまたは2つ）を示し、1つのサンプルのビット数を選択します（たとえば、16ビットがよく使用されます） 。 次に、入力ストリームが開くように、サウンドカードからデータラインを開き、その内容をバイト配列に書き込む必要があります。 Javaで行う方法は次のとおりです。

private AudioFormat getFormat() { float sampleRate = 44100; int sampleSizeInBits = 16; int channels = 1; //  boolean signed = true; //   ,        boolean bigEndian = true; //   ,     (big-endian)   (little-endian)   return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian); } final AudioFormat format = getFormat(); //   AudioFormat  DataLine.Info info = new DataLine.Info(TargetDataLine.class, format); final TargetDataLine line = (TargetDataLine) AudioSystem.getLine(info); line.open(format); line.start(); 

次に、 TargetDataLineクラスのオブジェクトからデータを読み取ります。 この例では、 runningフラグが使用されています。これは、別のスレッドから影響を受ける可能性があるグローバル変数です。 たとえば、このような変数を使用すると、[停止]ボタンを使用してユーザーインターフェイスストリームからのサウンドのキャプチャを停止できます。

 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); } 

時間および周波数領域

配列には、 時間領域の音声信号のデジタル表現が含まれています 。 つまり、信号の振幅が時間とともにどのように変化したかについての情報があります。

19世紀に、ジャンバプティストジョセフフーリエは素晴らしい発見をしました。 これは、各正弦波が特定の周波数、振幅、位相を持っている場合、時間領域の信号は特定の数（おそらく無限）の単純な正弦波信号の合計に等しいという事実から成ります。 元の信号を形成する正弦波のセットは、 フーリエ級数と呼ばれます。

つまり、この信号を形成する各正弦波に対応する周波数、振幅、位相のセットを設定するだけで、ほぼすべての信号が時間内に展開されることを想像できます。 このような信号の表現は、周波数間隔のセットと呼ばれます 。 ある意味では、周波数間隔に関する情報は、「指紋」または時間の経過とともに展開される信号シグネチャのようなものであり、動的データの静的な表現を提供します。


時間内に展開される信号とその周波数特性

1 Hzの方形波に対するフーリエ級数のアニメーション表現は次のようになります。 また、一連の正弦波に基づく元の信号の近似も示しています。 上のグラフでは、信号は振幅時間領域で表示され、下のグラフでは、振幅周波数形式で表示されます。


フーリエ変換の動作。 出典： Rene Schwarz

信号の周波数特性を分析すると、多くの問題の解決が大幅に促進されます。 デジタル信号処理の分野でこのような特性で動作することは非常に便利です。 これらを使用すると、信号のスペクトル（その周波数特性）を調べ、この信号のどの周波数がどの周波数であるかを判断できます。 その後、特定の周波数をフィルタリング、増幅、または減衰するか、既存の周波数セットの中で特定の高さの音を単に認識することができます。

離散フーリエ変換

そのため、時間内に展開された信号の周波数特性を取得する方法を見つける必要があります。 これには離散フーリエ変換 （DFT、DFT、離散フーリエ変換）が役立ちます。 DFTは、離散信号のフーリエ解析の数学的手法です 。 これを使用して、等間隔で取得した信号サンプルの有限セットを、これらの正弦波が同じ周波数で離散化されたことを考慮して、周波数で順序付けられた複素正弦波の有限組み合わせの係数のリストに変換できます。

DFTを計算するための最も一般的な数値アルゴリズムの1つは、 高速フーリエ変換 （FFT、FFT、高速フーリエ変換）と呼ばれます。 実際、FFTは一連のアルゴリズム全体で表されます。 その中でも、 アルゴリズムのCooley-Tukeyバリアントが最もよく使用されます。 このアルゴリズムの基礎は、「分割して征服する」という原則です。 計算中、元のDFTの小さな部分への再帰的分解が使用されます。 特定のデータセットnのDFTを直接計算するには、 O（n ² ）操作が必要です。Cooley-Tukeyアルゴリズムを使用すると、 O（n log n）操作の同じ問題を解決できます 。

FFTアルゴリズムを実装する適切なライブラリを見つけるのは簡単です。 さまざまな言語用のこれらのライブラリの一部を次に示します。

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

Javaで記述されたFFTを計算するための関数の例を次に示します。 複素数が入力に送られます。 複素数と三角関数の関係を理解するために、オイラーの公式について読むと便利です。

 public static Complex[] fft(Complex[] x) { int N = x.length; // fft   Complex[] even = new Complex[N / 2]; for (int k = 0; k < N / 2; k++) { even[k] = x[2 * k]; } Complex[] q = fft(even); // fft   Complex[] odd = even; //    for (int k = 0; k < N / 2; k++) { odd[k] = x[2 * k + 1]; } Complex[] r = fft(odd); //  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分析の前後の信号

音楽認識：曲の署名

FFTの不快な副作用の1つは、分析後、時間情報が失われることです。 （ただし、理論的にはこれを回避できますが、実際には非常に大きな処理能力が必要になります。）たとえば、3分間の歌の場合、音の周波数とその振幅を見ることができますが、これらの周波数が作品のどこに現れるかはわかりません。 そして、これは音楽をそれが何であるかを作る最も重要な特性です！ 各周波数が現れる時間の正確な値を何らかの方法で見つける必要があります。

そのため、スライディングウィンドウやデータブロックのようなものを使用し、この「ウィンドウ」に入る信号の部分のみを変換します。 各ブロックのサイズは、さまざまなアプローチを使用して決定できます。 たとえば、16ビットのサンプルサイズで44100 Hzのサンプリング周波数で2チャンネルのサウンドを録音すると、そのようなサウンドの1秒は176 KBのメモリを占有します（44100サンプル* 2バイト* 2チャンネル）。 スライディングウィンドウのサイズを4 KBに設定した場合、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が実装する音楽認識プロセス全体の中で最も重要な部分です。 ここでの主な困難は、非常に重要な周波数を膨大な数から選択することです。 純粋に直感的に、最大振幅の周波数（通常ピークと呼ばれます）に注意を払います。

ただし、ある曲では、「強い」周波数の範囲は、「音」からコントロクターブ（32.70 Hz）音まで、5オクターブ（4186.01 Hz）音まで変化します。 これは大きな間隔です。 したがって、周波数範囲全体をすぐに分析する代わりに、いくつかの小さい間隔を選択できます。 通常、重要な音楽コンポーネントに固有の周波数に基づいて選択し、それらを個別に分析できます。 たとえば、 このプログラマがShazamアルゴリズムの実装に使用した間隔を使用できます。 つまり、これらは低音用の30 Hz〜40 Hz、40 Hz〜80 Hz、および80 Hz〜120 Hzです（これには、たとえばベースギターが含まれます）。 中音以上の音には、120 Hz〜180 Hzおよび180 Hz〜300 Hzの周波数が使用されます（これには、ボーカルや他のほとんどの楽器が含まれます）。

間隔を決定したので、最高レベルの間隔を簡単に見つけることができます。 この情報は、分析されている特定のデータブロックの署名を形成し、曲全体の署名の一部です。

  public final int[] RANGE = new int[] { 40, 80, 120, 180, 300 }; //    ,      public int getIndex(int freq) { int i = 0; while (RANGE[i] < freq) i++; return i; } //  –   ,     for (int t = 0; t < result.length; t++) { for (int freq = 40; freq < 300 ; freq++) { //   : double mag = Math.log(results[t][freq].abs() + 1); // ,    : int index = getIndex(freq); //         : if (mag > highscores[t][index]) { points[t][index] = freq; } } //  - 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)); } 

録音は理想的な条件下（つまり、防音室ではない）で行われたものではないことに注意してください。 その結果、部屋の特性に応じて、録音に外来ノイズが存在し、録音された音に歪みが生じる可能性があります。 この問題は非常に真剣に取り組む必要があります。実際のシステムでは、録音が実行される条件に応じて、発生する可能性のある歪みと外来音（ファズファクター）の分析のチューニングを実装する価値があります。

楽曲の検索を簡単にするために、それらの署名はハッシュテーブルのキーとして使用されます。 キーは、署名が見つかった周波数のセットが作品に現れたときの時間値と、作品自体の識別子（曲名やアーティスト名など）に対応します。 このようなレコードがデータベースでどのように見えるかのオプションを次に示します。

ハッシュタグ	秒単位の時間	歌
30 51 99 121 195	53.52	歌A by A
33 56 92 151185	12.32	歌B by B
39 26 89141251	15.34	歌C by C
32 67100128270	78.43	歌D by D
30 51 99 121 195	10.89	ソングE by E
34 57 95111200	54.52	歌A by A
34 41 93161202	11.89	ソングE by E

この方法で特定の音楽レコードのライブラリを処理する場合、各曲の完全な署名を含むデータベースを構築できます。

一致を検索

レストランで現在再生されている曲を確認するには、電話を使用して音声を録音し、上記の署名計算プロセスを実行する必要があります。 その後、データベース内の計算されたハッシュタグの検索を開始できます。

しかし、それほど単純ではありません。 事実、異なる作品の多くの断片について、ハッシュタグが一致するということです。 たとえば、曲Aの一部が曲Eの特定のセクションとまったく同じように聞こえることが判明する場合があります。 ミュージシャンと作曲家は、常にお互いから成功した曲を「借りています」。

一致するハッシュタグを見つけることができるときはいつでも、一致する可能性のある数は減少しますが、この情報だけでは、正しい曲だけで停止するほど検索範囲を狭めることはできません。 したがって、音楽認識アルゴリズムで他の何かをチェックする必要があります。 つまり、タイムスタンプについて話しています。

レストランで録音された歌の断片は、その場所のいずれかからのものである可能性があるため、記録された断片内の相対時間をデータベース内のものと直接比較することはできません。

ただし、複数の一致が見つかった場合、一致の相対的なタイミングを分析できるため、検索の信頼性が向上します。

たとえば、上の表を見ると、ハッシュタグ30 51 99 121 195が曲Aと曲Eの両方に適用されていることがわかります。ハッシュタグ34 57 95 111 200を1秒後にチェックすると、別のさらに、曲Aと一致する場合、同様の場合、ハッシュタグとその時間分布が一致することがわかります。

 // ,       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つの一致があると言えます。

 RecordedHash(i1) = SongInDBHash(j1) AND RecordedHash(i2) = SongInDBHash(j2) AND abs(i1 - i2) = abs (j1 - j2) 

これにより、レコードの最初、中間、または最後でレコードのどの部分に該当するか心配する必要がなくなります。

そして最後に、「野生」の条件で録音された曲の各処理済みフラグメントが、スタジオ録音に基づいて構築されたデータベースの類似フラグメントと一致することはほとんどありません。 私たちが作品の名前を見つけたいと思う記録には、多くのノイズが含まれており、それが比較のいくつかの矛盾につながります。 そのため、データベースとの照合手順の最後に、正しい構成のみを除いて、一致のリストからすべてを除外しようとする代わりに、一致するレコードをソートします。 降順に並べ替えます。 偶然の一致が多ければ多いほど、正しい道を見つけた可能性が高くなります。 したがって、彼女はリストの一番上になります。

音楽認識の概要

以下に、音楽認識手順全体の概要を示します。 私たちは最初から最後までそれを歩きます。


音楽認識の概要

それはすべて元の音から始まります。 次に、キャプチャされ、周波​​数特性が検出され、ハッシュタグが計算され、音楽データベースに保存されているタグと比較されます。

このようなシステムでは、データベースが巨大になる可能性があるため、スケーラブルなソリューションを使用することが重要です。 データベーステーブルの関係は特に必要ありません。データモデルは非常に単純なので、ここでは何らかの種類のNoSQLデータベースが適しています。

シャザム！

ここでお話ししたようなプログラムは、音楽作品の同様の場所を見つけるのに適しています。 Shazamの仕組みが理解できたので、音楽認識アルゴリズムは、タクシーでラジオで演奏される、過去の忘れられた曲の名前の「リマインダー」としてだけでなく適用可能であることがわかります。

たとえば、彼らの助けを借りて、音楽の盗作を検索したり、ブルース、ジャズ、ロックミュージック、ポップミュージック、その他のジャンルの先駆者に影響を与えたアーティストを見つけることができます。

おそらく、バッハ、ベートーヴェン、ヴィヴァルディ、ワーグナー、ショパン、モーツァルトの作品などの古典をデータベースに入力し、それらの作品で似たようなものを見つけることは良い実験でしょう。 だから、ボブ・ディラン、エルビス・プレスリー、ロバート・ジョンソンでさえ、他の人から何かを借りることを嫌がっていなかったと知ることはかなり可能です！

しかし、私たちはそれらを責めることができますか？ きっと違います。 結局のところ、音楽は人の頭の中で聞こえ、記憶し、繰り返す音に過ぎません。 そこで開発され、変更されます-スタジオで録音され、野生にリリースされるまで、音楽から別の天才を鼓舞する可能性があります。

ああ、仕事に来てくれませんか？ :)

wunderfund.ioは、 高頻度アルゴリズム取引を扱う若い財団です。 高頻度取引は、世界中の最高のプログラマーと数学者による継続的な競争です。 私たちに参加することで、あなたはこの魅力的な戦いの一部になります。

熱心な研究者やプログラマー向けに、興味深く複雑なデータ分析と低遅延の開発タスクを提供しています。
柔軟なスケジュールと官僚主義がないため、意思決定が迅速に行われ、実施されます。

チームに参加： wunderfund.io