Shazam 和 SoundHound 是怎樣識別歌曲的？

01-16

它們的工作原理是怎樣的？SoundHound 還支持識別哼唱的音樂，請問技術上有何不同呢？

一句話概括：對擁有的歌曲資料庫中的每首歌曲提取數字指紋，然後對客戶端採集到的簡短歌曲樣本也做同樣的處理，得到數字指紋後提交給伺服器，在之前生成的指紋庫查找匹配。

他們發表過一篇簡短的論文介紹演算法，全文在此 http://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf

有人根據那篇論文做了個 Java 版本的實現，附帶源碼，地址在 http://www.redcode.nl/blog/2010/06/creating-shazam-in-java/

================= Talk is cheap, show you the code =================

我實現了Shazam的整個過程，源碼 DavaiZa/AudioSearch。準確性是不錯的，錄音匹配準確率在90%以上。不過性能還是有些慢：用postgresql存儲聲紋，197首歌，建庫要1h，匹配一個10秒有噪音片段，平均22s。商用還是差一些。不過自己搞197首歌做實驗，性能還是可以接受的。

問題中的SoundHound沒有研究過，不過既然能做到哼唱識別，應該比基於傅里葉窗口的Shazam技術要複雜一些；根據我看過的論文來推測，在特徵工程方面可能用了共振峰提取、在模型方面就不得而知了（總之肯定比Shazam的匹配演算法更先進），有研究過的朋友請不吝賜教。

這個代碼我優化了大概1個月，由於Shazam的匹配演算法已經脫離時代潮流，就不想繼續優化了。

（希望大作業寫Shazam的學弟學妹們不要打我。對，說的就是某軟15屆全體軟工班o(*￣▽￣*)ブ）

應評論區要求，已經補充了README.md，內容為項目的運行方法。

================= 原理：特徵提取 =================

Shazam演算法有兩個關鍵部分，特徵提取和指紋檢索。

Shazam把音樂的時間序列按0.1秒分成眾多時間窗口，對每個時間窗口做傅里葉變換，從而把時域轉化為頻域。接下來，找到每個窗口（記為窗口A）中幅度最大的N個頻率；並從下兩個窗口A1、A2中用同樣的方法找出2N個最大頻率。最後，把先頭的N個頻率中的每一個，和後來的2N個頻率中的每一個，組成2N^2個tuple。

採用傅里葉變換，是因為傅里葉變換對平移有較強的魯棒性。對於shazam演算法來說，只需要保證平移半個窗口之後仍然不變（顯然是可以保證的）。這一點可以在matlab上進行驗證。

有人會問，為什麼是tuple不是pair啊？因為我還需要知道兩個頻率中間隔了幾個時間窗啊。

到這裡，就完成了特徵提取。每個窗口都有2N^2個tuple，以及窗口在歌曲中的時間，共2N^2+1個自由度。當然代碼中還不止做到這裡，為了加快性能，我把每個tuple+它在歌曲中的時間，用位運算的方式編碼到一個int中，這樣每個時間窗有2N^2個int，這些int就是一個時間窗的指紋。

【以上內容應該有圖，以後再補，請有需要的讀者私信提醒我】

特徵提取有個坑：沒學過模電或者信號處理的童鞋，可能會不加考慮地把極低頻（0-500Hz）和極高頻（22050-44100Hz，已經超出人類聽覺範圍了）當成幅度最高的頻率。這些實際上不是噪音，而是有限傅里葉變換在極低頻產生畸變，同時由於實數傅里葉變換的對稱性，從而在極高頻產生同樣的畸變。據我所知，漢明窗演算法能用來修正這種畸變。當然，對於一個「能聽」的音樂來講，有意義的頻率都在500Hz以上，8000Hz以下。而這段頻率對於4096個採樣點（4096/44100秒）的時間窗來說，使用漢明窗前後變化不大。結論就是，我們只需要在500Hz-8000Hz之間找到最強的N個頻率就行，而不要在整個頻譜中找。

【以上內容應該有圖，以後再補，請有需要的讀者私信提醒我】

================= 原理：指紋檢索（匹配） =================

Shazam的匹配採用了倒排索引的方法。它不是在資料庫中拿出每首歌的所有指紋，從而和目標指紋進行比對；而是以指紋為主鍵、以歌曲ID為外鍵，記錄擁有這個指紋的歌曲集合。

但是有一個問題，對於單個指紋來說，可能在很多風格不同的歌曲中都出現過；即使統計每首歌出現指紋的相應次數，也是不科學的，因為同樣的指紋序列可能以其他的順序出現在其他歌曲中。

為了解決這個問題，Shazam演算法中一個頗有創意的想法就是，假如目標指紋和庫中指紋的時間差是固定的，就認為庫中的指紋所對應的歌曲為匹配歌曲。Shazam演算法還給出了如何檢驗這種「固定性」：為每一首歌記錄上述時間差，並為時間差做直方圖。每首歌的直方圖的峰值就是這首歌的打分。

【圖來自論文：Wang03Shazam】

不匹配音樂的指紋時間差的直方圖：

匹配音樂的指紋時間差的直方圖：

================= 後記 =================

在馬爾可夫鏈、CNN、RNN等更加先進的機器學習方法面前，Shazam演算法該退休了，因為它的特徵工程還是不夠高效；它的匹配方法也過於死板，無法學習歌曲深層的音律和語義特徵。但是Shazam為我們指明了傅里葉變換的局部極值具有抗噪性，這也是共振峰的原理。同時Shazam也提供了一種倒排索引的方法，為工業界提高演算法性能提供了思路。

哼唱相當於是模糊搜索，原聲檢索相當於是精確搜索。國內的acrcloud原聲和哼唱都可以支持。他們給小米，多米提供音樂檢索的技術。全球最大的在線歌詞服務Musixmatch也是通過他們家的音樂識別來同步歌曲的，你可以下一個試試

Rio說的沒錯,國外有專門的音樂識別服務提供商.比較出名的有gracenote和

AmpliFind等,itunes和sony有些功能里嵌了gracenote的服務.

但是大家有誰知道

shazam和

soundhound的服務是自己的還是誰提供的呢?

據了解

國內有幾個大學的實驗室里也有成熟的演算法，但商用估計還差一些;

國外也有類似的服務，不過費用不菲

Gracenote http://www.gracenote.com/

AudibleMagic http://audiblemagic.com/