沙贊如何運作？ 音樂識別算法、指紋識別和處理

您在俱樂部或餐廳聽到熟悉的歌曲。 這首歌你聽了一千遍了，這首歌的感傷真的觸動了你的心。 你明天拼命想把它放在心上，但你不記得它的名字了！ 幸運的是，在我們令人驚嘆的未來世界中，您有一部安裝了音樂識別軟件的手機，您就得救了。 您可以放鬆一下，因為軟件會告訴您歌曲的名稱，並且您知道您可以一遍又一遍地聽到它，直到它成為您的一部分……或者您厭倦了它。

移動技術，以及音頻信號處理方面的巨大進步，使我們的算法開發人員能夠創建音樂識別器。 Shazam 是最受歡迎的音樂識別應用程序之一。 如果您捕獲一首歌曲的 20 秒，無論是前奏、主歌還是副歌，它都會為錄製的樣本創建指紋，查詢數據庫，並使用其音樂識別算法準確地告訴您您正在聽哪首歌.

但是，Shazam 是如何工作的？ Shazam 的算法由其發明者 Avery Li-Chung Wang 於 2003 年向世界展示。在本文中，我們將介紹 Shazam 音樂識別算法的基礎知識。

模擬到數字 - 對信號進行採樣

什麼是真正的聲音？ 它是某種我們無法觸摸但飛入我們耳朵並讓我們聽到事物的神秘物質嗎？

當然，情況並非如此。 我們知道，在現實中，聲音是一種振動，它以壓力和位移的機械波的形式通過空氣或水等介質傳播。 當這種振動傳到我們的耳朵，尤其是耳膜時，它會移動小骨頭，這些骨頭會將振動進一步傳遞到我們內耳深處的小毛細胞。 最後，小毛細胞產生電脈衝，通過聽耳神經傳遞到我們的大腦。

錄音設備非常接近地模仿這個過程，利用聲波的壓力將其轉換為電信號。 空氣中的實際聲波是連續的壓力信號。 在麥克風中，第一個遇到該信號的電子元件將其轉換為模擬電壓信號——同樣是連續的。 這種連續的信號在數字世界中不是那麼有用，因此在對其進行處理之前，必須將其轉換為可以以數字方式存儲的離散信號。 這是通過捕獲表示信號幅度的數字值來完成的。

轉換涉及輸入的量化，它必然會引入少量的誤差。 因此，模數轉換器不是單次轉換，而是對非常小的信號片段執行多次轉換——這一過程稱為採樣

Nyquist-Shannon 定理告訴我們在連續信號中捕獲某個頻率所需的採樣率。 特別是，為了捕獲人類可以在音頻信號中聽到的所有頻率，我們必須以人類聽覺範圍兩倍的頻率對信號進行採樣。 人耳可以檢測到大約 20 Hz 到 20,000 Hz 之間的頻率。 因此，音頻最常以 44,100 Hz 的採樣率記錄。 這是光盤的採樣率，也是 MPEG-1 音頻（VCD、SVCD、MP3）最常用的採樣率。 （這個特定的速率最初是由 Sony 選擇的，因為它可以在以每秒 25 幀 (PAL) 或每秒 30 幀（使用 NTSC 單色視頻錄像機）運行的修改後的視頻設備上錄製，並覆蓋認為必要的 20,000 Hz 帶寬匹配當時的專業模擬錄音設備。）因此，在選擇需要錄製的樣本頻率時，您可能希望使用 44,100 Hz。

錄音 - 捕捉聲音

錄製採樣的音頻信號很容易。 由於現代聲卡已經帶有模數轉換器，只需選擇一種編程語言，找到一個合適的庫，設置樣本的頻率，通道數（通常是單聲道或立體聲），樣本大小（例如 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 年代初期，Jean-Baptiste Joseph Fourier 做出了驚人的發現，即時域中的任何信號都等效於一些（可能無限）簡單正弦信號的總和，因為每個正弦分量都有一定的頻率、幅度、和相。 一起形成原始時域信號的一系列正弦曲線稱為傅里葉級數。

換句話說，可以通過簡單地給出與構成信號的每個正弦曲線相對應的頻率、幅度和相位的集合來表示任何時域信號。 信號的這種表示稱為頻域。 在某些方面，頻域充當時域信號的一種指紋或簽名，提供動態信號的靜態表示。

以下動畫演示了 1 Hz 方波的傅立葉級數，以及如何從正弦分量生成（近似）方波。 信號在上面的時域中顯示，在下面的頻域中顯示。

在頻域中分析信號極大地簡化了許多事情。 在數字信號處理領域更方便，因為工程師可以研究頻譜（信號在頻域中的表示）並確定哪些頻率存在，哪些頻率缺失。 之後，可以進行過濾，增加或減少一些頻率，或者只是從給定的頻率中識別出確切的音調。

離散傅里葉變換

所以我們需要找到一種方法將我們的信號從時域轉換到頻域。 在這裡，我們求助於離散傅里葉變換 (DFT)。 DFT 是一種對離散（採樣）信號執行傅里葉分析的數學方法。 它通過考慮這些正弦曲線是否以相同的速率採樣，將函數的等距樣本的有限列表轉換為複雜正弦曲線的有限組合的係數列表，按頻率排序。

用於計算 DFT 的最流行的數值算法之一是快速傅里葉變換 (FFT)。 到目前為止，最常用的 FFT 變體是 Cooley-Tukey 算法。 這是一種分而治之的算法，它將一個 DFT 遞歸地劃分為許多更小的 DFT。 直接評估 DFT 需要O( n 2 ) 次運算，而使用 Cooley-Tukey FFT 時，相同的結果需要O( n log n )次運算。

為 FFT 找到合適的庫並不難。 以下是其中幾個：

• C – FFTW
• C++ – 特徵 FFT
• 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 的一個不幸的副作用是我們丟失了大量有關時間的信息。 （雖然理論上這是可以避免的，但性能開銷是巨大的。）對於一首三分鐘的歌曲，我們可以看到所有的頻率及其大小，但我們不知道它們是在何時出現在歌曲中的。 但這是使這首歌成為現實的關鍵信息！ 不知何故，我們需要知道每個頻率出現的時間點。

這就是為什麼我們引入一種滑動窗口或數據塊，並只轉換這部分信息。 每個塊的大小可以通過幾種不同的方式確定。 例如，如果我們以 44,100 Hz 的 16 位樣本以立體聲錄製聲音，那麼一秒鐘的此類聲音將是 44,100 個樣本 * 2 字節 * 2 個通道 ≈ 176 kB。 如果我們選擇 4 kB 作為塊的大小，我們將在歌曲的每一秒中分析 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 音頻識別過程中最重要的部分。 這裡的主要挑戰是如何在捕獲的頻率海洋中區分哪些頻率是最重要的。 直觀地說，我們搜索幅度最高的頻率（通常稱為峰值）。

然而，在一首歌曲中，強頻率範圍可能在低 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 - 300 Hz 用於中音和更高音（涵蓋人聲和大多數其他樂器）。

現在，在每個區間內，我們可以簡單地確定幅度最高的頻率。 這些信息形成了這首歌曲的簽名，而這個簽名成為整個歌曲指紋的一部分。

 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 完全一樣。當然，這並不奇怪 - 音樂家總是“借用”彼此的 licks 和 riff，而現在製作人都對其他歌曲進行採樣時間。 每次我們匹配一個哈希標籤時，可能匹配的數量會變少，但僅此信息可能不會將匹配範圍縮小到一首歌曲。 所以我們還需要用我們的音樂識別算法檢查一件事，那就是時間。

我們在俱樂部中錄製的樣本可能來自歌曲中的任何一點，因此我們不能簡單地將匹配哈希的時間戳與樣本的時間戳進行匹配。 但是，對於多個匹配的哈希，我們可以分析匹配的相對時間，從而增加我們的確定性。

例如，如果您查看上表，您將看到哈希標籤30 51 99 121 195對應於歌曲 A 和歌曲 E。如果一秒鐘後，我們匹配哈希34 57 95 111 200 ，那就多了一個匹配歌曲 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; } }

讓我們將i 1和i 2作為錄製歌曲中的時刻，將j 1和j 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 掃描之外，它還有哪些應用程序。 例如，它可以幫助識別音樂中的抄襲，或者找出誰是藍調、爵士、搖滾、流行或任何其他流派先驅的最初靈感來源。 也許一個很好的實驗是用巴赫、貝多芬、維瓦爾第、瓦格納、肖邦和莫扎特的古典音樂填充歌曲樣本數據庫，並嘗試找出歌曲之間的相似之處。 你會認為鮑勃·迪倫、貓王和羅伯特·約翰遜都是抄襲者！

但我們仍然無法定罪他們，因為音樂只是我們聽到、記憶和在腦海中重複的一種波，它會在其中演變和變化，直到我們在錄音室錄製它並將其傳遞給下一個偉大的音樂天才。