バックエンド
Shazamはどのように機能しますか？音楽認識アルゴリズム、フィンガープリント、および処理
クラブやレストランでおなじみの歌が聞こえます。あなたは千回も前にこの曲を聴いていましたが、この曲の感傷は本当にあなたの心に響きます。明日は必死に心を込めたいけど、名前が思い出せない！幸いなことに、私たちの驚くべき未来の世界では、音楽認識ソフトウェアがインストールされた電話があり、あなたは救われています。ソフトウェアが曲の名前を教えてくれたので、リラックスすることができます。そして、それがあなたの一部になるまで、またはあなたがそれにうんざりするまで、何度も何度もそれを聞くことができることを知っています。
モバイルテクノロジー 、オーディオ信号処理の大きな進歩とともに、私たちに与えてくれました アルゴリズム開発者 音楽レコグナイザーを作成する機能。最も人気のある音楽認識アプリの1つは シャザム 。イントロ、バース、コーラスに関係なく、曲の20秒をキャプチャすると、録音されたサンプルのフィンガープリントが作成され、データベースが参照され、音楽認識アルゴリズムを使用して、聴いている曲が正確にわかります。 。
しかし、Shazamはどのように機能しますか？ シャザムのアルゴリズム 2003年に発明者のAveryLi-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年代初頭、ジャンバプティストジョセフフーリエは、各成分の正弦波が特定の周波数、振幅を持っていることを考えると、時間領域の信号はいくつかの（おそらく無限の）数の単純な正弦波信号の合計に等しいという驚くべき発見をしました。とフェーズ。一緒に元の時間領域信号を形成する一連の正弦波は、 フーリエ級数 。
言い換えると、信号を構成する各正弦波に対応する周波数、振幅、および位相のセットを与えるだけで、任意の時間領域信号を表すことができます。信号のこの表現は、 周波数領域 。ある意味で、周波数領域は時間領域信号の一種のフィンガープリントまたはシグニチャとして機能し、動的信号の静的表現を提供します。
動作するリークされたクレジットカード
次のアニメーションは、1Hzのフーリエ級数を示しています 方形波 、および正弦波成分から（近似）方形波を生成する方法。信号は上の時間領域と下の周波数領域に示されています。
ソース： ルネシュワルツ
周波数領域で信号を分析すると、多くのことが非常に簡単になります。エンジニアはスペクトル（周波数領域での信号の表現）を調べて、どの周波数が存在し、どの周波数が欠落しているかを判断できるため、デジタル信号処理の世界ではより便利です。その後、フィルタリングを行ったり、一部の周波数を増減したり、特定の周波数から正確なトーンを認識したりすることができます。
離散フーリエ変換
したがって、信号を時間領域から周波数領域に変換する方法を見つける必要があります。ここで私たちは呼びかけます 離散フーリエ変換 （DFT）助けを求めて。 DFTは、実行するための数学的方法論です。 フーリエ解析 離散（サンプリングされた）信号。関数の等間隔のサンプルの有限リストを、それらの正弦波が同じレートでサンプリングされたかどうかを考慮して、周波数順に並べられた複雑な正弦波の有限の組み合わせの係数のリストに変換します。
DFTの計算に最も一般的な数値アルゴリズムの1つは、 高速フーリエ変換 （FFT）。 FFTの最も一般的に使用されるバリエーションは、 Cooley-Tukeyアルゴリズム 。これは分割統治アルゴリズムであり、DFTを多数の小さなDFTに再帰的に分割します。 DFTを直接評価するには、 OR（ n 2） Cooley-Tukey FFTを使用した操作では、同じ結果が次のように計算されます。 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の不幸な副作用の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 内側のループでは、時間領域データ（サンプル）を虚数部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〜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
この音楽識別プロセスを通じて曲のライブラリ全体を実行すると、ライブラリ内のすべての曲の完全なフィンガープリントを使用してデータベースを構築できます。
AndroidStudioでネイティブに反応する
関連： ディープラーニングチュートリアル：パーセプトロンからディープネットワークまで 音楽アルゴリズム：曲の識別
現在クラブで再生されている曲を識別するために、携帯電話で曲を録音し、上記と同じオーディオフィンガープリントプロセスを実行して録音を実行します。次に、一致するハッシュタグをデータベースで検索し始めます。
たまたま、ハッシュタグの多くは複数の曲の音楽識別子に対応します。たとえば、曲Aの一部が曲Eの一部とまったく同じように聞こえる場合があります。もちろん、これは驚くべきことではありません。ミュージシャンは常にお互いからリックやリフを「借り」ており、最近ではプロデューサーが他の曲をすべてサンプリングしています。時間。ハッシュタグを照合するたびに、一致する可能性のある数は少なくなりますが、この情報だけでは、一致を1つの曲に絞り込むことはできない可能性があります。したがって、音楽認識アルゴリズムで確認する必要があるもう1つのことがあります。それは、タイミングです。
クラブで記録したサンプルは、曲のどの時点からのものである可能性があるため、一致したハッシュのタイムスタンプをサンプルのタイムスタンプと単純に一致させることはできません。ただし、一致するハッシュが複数ある場合は、 相対的 試合のタイミング、したがって私たちの確実性を高めます。
たとえば、上の表を見ると、ハッシュタグ30 51 99 121 195が表示されます。曲Aと曲Eの両方に対応します。1秒後にハッシュ34 57 95 111 200が一致した場合、それは曲Aのもう1つの一致ですが、この場合、ハッシュと時差の両方が一致していることがわかります。
// 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）
これにより、曲の最初、中間、または最後から曲を録音する柔軟性が得られます。
最後に、クラブで録音した曲のすべての瞬間が、スタジオで録音されたライブラリ内の同じ曲の対応するすべての瞬間と一致する可能性はほとんどありません。録音には多くのノイズが含まれているため、試合でエラーが発生します。そのため、一致リストから正しい曲を除くすべてを削除しようとするのではなく、最後に、一致したすべての曲を可能性の高い順に並べ替えます。お気に入りはランキングリストの最初の曲です。
上から下まで
「Shazamはどのように機能しますか？」という質問に答えるために。音楽認識とマッチングのプロセス全体の概要を上から下に示します。
この種のシステムでは、データベースがかなり巨大になる可能性があるため、ある種のスケーラブルなデータベースを使用することが重要です。リレーションは特別に必要ではなく、データモデルは非常に単純になるため、ある種のNoSQLデータベースを使用するのに適しています。
Shazamはどのように機能しますか？今あなたは知っています
この種の曲認識ソフトウェアは、曲間の類似性を見つけるために使用できます。 Shazamがどのように機能するかを理解したので、タクシーのラジオで再生されるノスタルジックな曲を単にShazamingするだけでなく、これがどのようにアプリケーションを持つことができるかを理解できます。たとえば、音楽の盗用を特定したり、ブルース、ジャズ、ロック、ポップ、その他のジャンルのパイオニアに最初にインスピレーションを与えたのは誰かを見つけるのに役立ちます。たぶん、良い実験は、曲のサンプルデータベースをバッハ、ベートーベン、ヴィヴァルディ、ワーグナー、ショパン、モーツァルトのクラシック音楽で埋めて、曲間の類似点を見つけてみることでしょう。ボブ・ディラン、エルビス・プレスリー、ロバート・ジョンソンでさえ、疫病学者だったと思うでしょう！
しかし、それでも私たちは彼らを有罪にすることはできません。なぜなら、音楽は私たちが耳にし、記憶し、頭の中で繰り返す波であり、スタジオで録音して次の偉大な音楽の天才に引き継ぐまで進化し、変化するからです。
関連： 機械学習理論とその応用の紹介：例を含むビジュアルチュートリアル 基本を理解する
Shazamアルゴリズムはどのように機能しますか？
Shazamアルゴリズムは、曲のサンプルをフィンガープリントに抽出し、曲内の相互のタイミングを考慮して、これらのフィンガープリントを既知の曲のフィンガープリントと照合します。
オーディオ指紋とは何ですか？
オーディオフィンガープリントは、曲のサンプルのハッシュタグまたは署名のコレクションです。これらは、各サンプルのどの周波数が最も強いかを測定します。
Shazamはどのようにして音楽を見つけますか？
Shazamは、ユーザーが入力した録音の音声指紋をデータベースの既知の曲の指紋と比較することで音楽を見つけます。
