バックエンド
シャザム！音楽アルゴリズム、指紋、および処理の認識
クラブやレストランで家族の歌が聞こえます。あなたは長い間この曲を何千回も聴いていて、曲の感傷は本当にあなたの心に触れます。あなたは必死に朝に彼女の話を聞きたいのですが、彼女の名前を覚えていません！幸いなことに、私たちの驚くべき未来の世界では、音楽認識ソフトウェアがインストールされた電話があります。ソフトウェアが曲の名前を教えてくれたので、リラックスすることができます。それで、それがあなたの一部になるまで、またはあなたが絶望するまで、何度も何度もそれを聞くことができることを知っています...
Linuxカーネルはどの言語で書かれていますか
モバイルテクノロジー オーディオ信号処理の計り知れない進歩と相まって、 アルゴリズム開発者 、音楽レコグナイザーを作成する機能。最も人気のある音楽認識アプリの1つは シャザム 。イントロ、バース、コーラスのいずれであるかに関係なく、20秒で曲をキャプチャします。アプリケーションは、録音されたサンプルのフィンガープリントを作成し、データベースを調べ、音楽認識アルゴリズムを使用して正確にどれを教えます。あなたが聴いている曲です。
Shazamは実際にどのように機能しますか？ シャザムのアルゴリズム このアプリケーションは、2003年に発明者のAvery Li-Chung Wangによって最初に公開されました。この記事では、Shazam音楽認識アルゴリズムの基本について説明します。
アナログからデジタルへ-1つのサンプル信号
本当に音は何ですか？触ることはできないけれど、耳の中を飛んで物事を聞かせるような神秘的な素材なのだろうか？
もちろん、そうではありません。音は実際には振動として伝播することを私たちは知っています 力学的波 圧力の力学的波であり、空気や水などの媒体を通過します。この振動が私たちの耳、特に鼓膜に到達すると、小さな骨が動き、内耳のかなり深いところにある有毛細胞に振動が伝わります。さらに、いくつかの有毛細胞は電気インパルスを生成し、それが耳の聴覚神経を介して脳に伝達されます。
録音デバイスは、音波を電気信号に押し込むことによってこのプロセスを模倣します。空気中の実際の音波は 連続 圧力信号。マイクでは、この信号に遭遇したときの最初の電気部品がアナログ電圧信号に変換されます。これも連続しています。この連続信号はデジタルの世界ではそれほど有用ではないため、処理する前に次のように変換する必要があります。 離散信号 デジタルで保存できる離散信号。これは、信号の振幅を表すデジタル値をキャプチャすることによって行われます。
変換には 量子化 必然的に少量の誤差をもたらす入力の量子化。したがって、単純な変換ではなく、 アナログ-デジタルコンバーター アナログ-デジタルコンバーターは、信号の非常に小さな部分で多くの変換を実行します-として知られているプロセス サンプリング
ザ・ ナイキスト-シャノンの定理 ナイキスト–シャノンの定理は、連続信号で特定の周波数をキャプチャするために必要なサンプリングレートを示しています。特に、人間が音声信号で聞くことができるすべての周波数をキャプチャするには、人間の可聴範囲の2倍の周波数で信号をサンプリングする必要があります。人間の耳は約20Hz〜20,000 Hzの周波数を検出できます。その結果、録音されたオーディオのほとんどの時間のサンプリングレートは44,100 Hzです。これは、のサンプリング周波数です。 コンパクトディスク コンパクトディスクであり、 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'からデータを読み取ります。 （この例では、「実行中」は別のスレッドによって停止されるグローバル変数です。たとえば、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); } 時間領域と周波数領域
このバイト配列にあるのは、ドメインの時間記録された信号です ドメイン 。時間領域信号は、時間の経過に伴う信号の振幅の変化を表します。
19世紀の最初の数十年で、ジャンバプティストジョセフフーリエは、各コンポーネントが特定の正弦波周波数を持っているため、時間領域の信号がいくつかの（おそらく無限の）数の単純な正弦波信号の合計に相当しないという驚くべき発見をしました。 、振幅と位相。元の時間領域信号を一緒に形成する一連の正弦波は、一連の正弦波として知られています。 フーリエ 。
言い換えると、信号を構成する各正弦波に対応する周波数、振幅、および位相のセットを与えるだけで、時間領域で任意の信号を表すことができます。信号のこの表現は、ドメイン周波数として知られています 周波数領域 。ある意味で、周波数ドメインは、時間ドメイン信号の一種のフィンガープリントまたはシグネチャとして機能し、動的信号の静的表現を提供します。
次のアニメーションは、1HZ方形波のフーリエ級数を示しています。 方形波 正弦波成分から（近似）方形波を生成する方法。信号は、上の時間領域と下の周波数領域に表示されます。
ソース： ルネシュワルツ
周波数領域で信号を分析すると、多くのことが非常に簡単になります。エンジニアはスペクトル（周波数領域での信号の表現）を調べて、どの周波数が存在し、どの周波数が欠落しているかを判断できるため、デジタル信号処理の世界ではより便利です。その後、フィルタリングを実行したり、一部の周波数を増減したり、単に周波数の正確なピッチを認識したりできます。
離散フーリエ変換
したがって、信号をドメインモーメントから周波数ドメインに変換する方法を見つける必要があります。ここでは、それを離散フォーリー変換と呼びます 離散フーリエ変換 （DFT）助けて。 DFTは、実行する数学的方法です フーリエ解析 離散（サンプル）信号で。関数の等距離サンプルの有限リストを、正弦波が同じ比率でサンプリングされたかどうかを考慮して、周波数順に並べられた複雑な正弦波の有限の組み合わせの係数のリストに変換します。
DFTを計算するための最も一般的な数値アルゴリズムの1つは、 高速フーリエ変換 （FFT）。最も広く使用されているのはFFTバリエーションです Cooley-Tukeyアルゴリズム 。このアルゴリズムは、DFTをいくつかの小さなDFTに再帰的に分割する分割統治タイプです。 DFTの評価には直接必要ですが OR（ n 2） Cooley-Tukey FFTを使用すると、iで計算されます。 OR（ n ログ n ） オペレーション。
FFTに適したライブラリを見つけることは難しくありません。それらのいくつかを次に示します。
- C - FFTW
- C ++ - EigenFFT
- Java - JTransform
- Python - NumPy
- ルビー - 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 そして、FFT分析の前後の信号の例を次に示します。
音楽認識：歌の指紋
FFTの不幸な副作用は、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 内側のループでは、時間領域データ（サンプル）を虚数部0の複素数に入れています。外側のループでは、すべてのセグメントを反復処理し、各セグメントのFFT分析を実行します。
信号の周波数に関する情報を取得したら、曲のフィンガープリントを作成し始めることができます。これは、Shazamの音楽認識プロセス全体の中で最も重要な部分です。主な課題は、捕獲された周波数の海で、最も重要な周波数をどのように区別するかです。直感的に、最大の大きさの周波数（一般にピークと呼ばれます）を探すことができます。
ただし、曲では、強い周波数範囲は低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〜180 Hz、180 Hz〜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] 録音が完全な状態（たとえば、「聴覚障害者の部屋」）で行われていないと想定する必要があり、その結果、近似係数を含める必要があることに注意してください。近似係数の分析は真剣に受け止めなければならず、実際のシステムでは、プログラムには記録条件に基づいてこのパラメータを設定するオプションが必要です。
検索を容易にするために、この署名はハッシュタグテーブルのキーになります。対応する値は、この周波数のセットが曲に出現した時間と、曲ID（曲のタイトルとアーティスト）です。これらのレコードがデータベースにどのように表示されるかの例を次に示します。
ハッシュタグ 秒単位の時間 歌 30 51 99 121 19553.52 アーティストAの曲A 33 56 92 151 18512.32 アーティストBの曲B 39 26 89 141 25115.34 アーティストCによる曲C 32 67 100 128 27078.43 アーティストDによる曲D 30 51 99 121 19510.89 アーティストEによる曲E 34 57 95 111 20054.52 アーティストAの曲A 34 41 93 161 20211.89 アーティストEによる曲E
このプロセスで曲のライブラリ全体を実行すると、ライブラリ内の各曲のフィンガープリントを使用して完全なデータベースを構築できます。
関連： ディープラーニングチュートリアル：パーセプトロンからディープネットワークまで 曲の選択
クラブで現在再生されている曲を特定するには、携帯電話で曲を録音し、以前と同じデジタル追跡プロセスを使用して録音を実行します。次に、ハッシュタグデータベースで一致する検索を開始できます。
たまたま、ハッシュタグの多くはさまざまな曲に対応しています。たとえば、曲の一部が曲Eの断片とまったく同じように聞こえる場合があります。もちろん、これは驚くべきことではありません。ミュージシャンは常にお互いに歌詞を「借用」しており、最近ではプロデューサーが他の曲をすべて表示しています。時間。ハッシュタグから始めるたびに、一致する可能性のある数は少なくなりますが、この情報だけでは一致が1曲に減ることはない可能性があります。したがって、音楽認識アルゴリズムで確認する必要があるもう1つのことがあります。それは、レイアウトです。
クラブに登録されたサンプルは曲のどのポイントでもかまいません。そのため、サンプルブランドに一致するハッシュタグのタイムスタンプと一致させることはできません。ただし、いくつかの一致するハッシュタグアルゴリズムを使用すると、組み合わせの相対時間を分析できるため、セキュリティが向上します。
たとえば、上の表を見ると、ハッシュタグ'30 51 99 121 195 'が曲Aと曲Eの両方に対応していることがわかります。1秒後にハッシュ'34 57 95 111200'と一致します。は曲との一致に近いですが、この場合、ハッシュが一致し、時差も一致することがわかります。
// 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; } } 取りましょう 私1 そして 私2 録音された曲の瞬間として、そして j1 そして j2 データベースからの曲の瞬間として。次の場合、時差が一致する2つの一致があると言えます。
RecordedHash（i1）= SongInDBHash（j1）AND RecordedHash（i2）= SongInDBHash（j2）
そして
abs（i1- 私2）= abs（j1--j2）
これにより、曲の最初、途中、または最後から録音する柔軟性が得られます。
最後に、クラブで録音する曲のすべての瞬間が、スタジオで録音するライブラリの同じ曲の対応するすべての瞬間と一致する可能性はほとんどありません。録音には、試合でいくつかのエラーを引き起こす多くのノイズが含まれています。そのため、一致リストから正しい曲を除くすべてを削除しようとする代わりに、最終的に、すべての曲を確率の降順で並べ替えるように調整しました。お気に入りはランキングリストの最初の曲です。
一気飲み
音楽認識と調整プロセス全体の概要を上から下に示します。
このタイプのシステムでは、データベースが非常に大きくなる可能性があるため、何らかの変更データベースを使用することが重要です。関係は特別に必要ではなく、データモデルは非常に単純になるため、ある種のNoSQLデータベースを使用するのに適しています。
結論、Shazam！
このタイプの音楽認識ソフトウェアは、曲間の類似点を見つけるために使用できます。 Shazamがどのように機能するかを理解したので、タクシーのラジオで再生されるノスタルジックな曲よりも、単純なShazaming以外のアプリケーションを使用できることがわかります。たとえば、音楽の盗用を特定したり、ブルース、ジャズ、ロック、ポップ、その他のジャンルのパイオニアの最初のインスピレーションとなった人物を見つけたりするのに役立ちます。おそらく良い実験は、バッハ、ベートーベン、ヴィヴァルディ、ワーグナー、ショパン、モーツァルトのクラシック音楽でデータベースを埋め、曲間の類似点を見つけようとすることでしょう。ボブ・ディラン、エルビス・プレスリー、ロバート・ジョンソンでさえ、疫病学者だったと思います！
しかし、それでも彼らを非難することはできません。なぜなら、音楽は私たちが耳にし、記憶し、頭の中で繰り返す波であり、スタジオで録音して次の偉大な音楽の天才に引き継ぐまで進化し、変化するからです。
関連： 機械学習理論とその応用の紹介：例を含むビジュアルチュートリアル
