转载自：https://blog.csdn.net/yutianzuijin/article/details/49787551

随着微信摇一摇逐渐被大众所广泛使用，听歌识曲功能也开始被关注。目前来看，像音乐雷达和微信摇一摇都采用了经典的shazam算法，为了使大家对shazam算法更加了解，我将其经典论文进行了翻译，希望对大家学习shazam算法有所帮助。

一个企业级的音频搜索算法

摘要

       我们设计实现并实际部署了一套灵活性很高的音频搜索引擎。核心算法抗噪声和扰动能力强，计算复杂度低，同时具有很高的可扩展性。即使外界噪音很强，它也可以迅速地通过手机录制的一小段压缩音频从百万级的曲库中辨识出正确的歌曲。算法分析音频频域上的星状图来组合时间-频率信息构造哈希。这种方式具有不寻常的优势，例如它能将混合在一起的几首歌都辨识出来。针对不同的应用，即使曲库非常非常大，检索速度也可以达到毫秒级。

1. 简介

       Shazam公司创立于2000年，最初的目的是方便用户通过自己的手机检索正在播放的歌曲。（为了达到很高的可用性，算法必须具有下面几个特性。）算法必须能利用很短的音频片段辨识出正确的歌曲。特别地，即使该音频片段包含很强的噪音和扰动，并且经过各种损害性处理，例如压缩和网络丢包等，算法也需要准确地返回结果。此外，当曲库规模达到200万时算法也需要很快地返回结果。返回的结果在保证高识别率的同时必须具有很低的假阳性（false positive）概率。

       这是一个很难的问题，到目前为止还没出现可以满足上述要求的算法，但是我们设计的算法可以满足上述要求[1]。

       我们实际部署了一套曲库规模达180万的商用音乐识别服务。目前给德国、芬兰和英国的50w用户提供服务，很快就会覆盖欧洲、亚洲的多个国家以及美国。使用方法很简单：用户听到一首正在播放的歌曲，然后用手机录制15秒的片段上传到我们的服务器，服务器将歌手和歌名以短信的形式返回给用户。用户也可以通过网站访问我们的服务，并可以根据返回的歌名购买相应的CD或者自行下载对应歌曲。

       目前有不少类似的应用: Musicwave公司采用philips算法[2-4]在西班牙部署了一套类似的系统。Neuros在他们的MP3播放器中内置了一个属性，允许用户截取30s正在播放的音频进行识别[5,6]。Audible Magic公司则采用Muscle Fish算法识别网络广播电台中的音频流[7-9]。

       shazam算法除了辨识歌曲之外还有很多其他应用。由于算法抗噪能力强，例如，即使在广告中有很大的说话声，算法也能正确识别出其中的背景音乐。另一方面，由于算法非常快，还可以用来进行版权保护检测，速度可以达到1000倍实时。这样部署一台中型服务器就可以同时对多路音频流进行检测。shazam算法也适用于基于内容的跟踪和索引。

2. 算法的基本原理

       数据库和录制的音频文件都需要提取可复现的哈希“令牌”，也即指纹。从未知音频中提取的指纹需要和音乐库中提取的海量指纹进行匹配。匹配上的指纹会用来衡量匹配的正确性。提取的指纹需要满足几个指导性原则：时间局部性(temporally localized)，转换不变性(translation-invariant)，鲁棒性(robust)和指纹信息量大(sufficiently entropic)。时间局部性表示指纹是由时间上接近的音频数据构造的，这样较远时刻的事件不会对该指纹产生影响（如果指纹是由时刻相距较远的音频数据构造的，则指纹会很不稳定，易受到外界噪音干扰）。转换不变性表示提取的指纹必须和位置无关，并且是可复现的。这是因为用户录音可以从任意位置开始。鲁棒性表示从“干净”音乐中提取的指纹也必须可以从含有各种噪音的音频中复现。此外，指纹也必须要包含足够的信息以便减少错误位置的无用匹配。指纹包含的信息量过少通常会导致冗余繁琐的匹配，从而浪费大量计算资源。但是，如果指纹包含的信息量过多又会导致指纹的脆弱性，使指纹在噪音和失真环境下不能复现。

       shazam算法共有三个主要模块，下面分别进行介绍。

2.1 星状图

       为了解决在噪音和失真情况下的音乐识别问题，我们尝试了大量的特征，最终选择了“频谱的极大值(spectrogram peaks)”。因为频谱极大值（亦可称为峰值）具有很强的抗噪能力，同时又具有近似的线性可加性[1]。频谱上的极大值表示在给定的时频区域内某个点的值大于所有的邻居。在选择候选极大值时需要满足密度准则使选取的极大值在不同的时间段内能均匀分布。在一个小的时间区间内选择极大值也要保证选择是最大值的极大值，因为最大值才最有可能在各种噪音和失真环境下保持不变（即最大值能在录音前后保持不变，也就满足指纹的健壮性）。

       通过极大值选取，复杂的频谱图（1A）就简化成了稀疏的极大值坐标（1B）。需要注意一点，经过该步骤之后频谱图中的幅值信息就丢失了（只利用时间和频率信息，不利用幅值信息）。这种简化操作具有对EQ（不清楚怎么翻译）不敏感的好处。因为一个极大值经过各种滤波之后依旧会是相同位置的极大值（假定滤波器传递函数的导数很小，也即信号剧烈变化位置的峰值在经过传递函数之后只会引起轻微的频率上下浮动）。我们将这些稀疏的坐标称为“星状图”，因为它们确实很像天空中的星星。