帮助:音乐识别扩展

音乐识别扩展是一个提供Shazam类功能（音乐/音频识别配对），以音频搜索资讯的系统。
此功能尚处于技术验证阶段，而且可能会因为实际原因不会实装。

功能简介

每人都经历过空有一段音频、视频BGM、录音而对其名称以及详细咨询毫无头绪的困境，这时候音乐识别搜索技术就派上用场了。
只要简单地分析一段10来秒的音频，就能快速找到对应的曲目资料。
就是这么一个功能。

理论流程

网络上描述音乐识别功能原理的文章很多¹²，仔细阅读了一个比较详细的后，总结了一下流程：

文件读取读取需要被分析的文件，并将其解码变成可以处理的.wav形式，时间×振幅资讯
音频分析对音频进行离散快速傅里叶变换，获取时间×频率×强度资讯
寻找特征点这是第二难的步骤，分析变换结果，在各个频域寻找强度较高的点作为特征点，并记录为频率×时间资讯
关联特征点把每个特征点和它后面的若干个特征点关联起来，形成特征点对，计算方便储存的哈希值后变成可以储存并用来搜索的哈希×时间资讯
储存特征点把得到的特征点对哈希和对应时间、加上曲目ID就可以储存到资料库了，搜索则是把每个哈希丢进去资料库搜索，得到一大堆时间×曲目ID资讯
搜索特征点就是用数据库搜索，没什么特别的，关键是如何提高效率，Hash Database和MySQL的PARTITION BY是很好的工具
分析搜索结果这是最难的步骤，没有之一。简单来说就是对一大堆时间和已知的一大堆时间进行配对，对每个曲目ID进行算分，分数高的便最有可能是答案
返回曲目信息返回排位最高的若干位的详细曲目信息，至少要有词条名
显示搜索结果在用户端显示简单易懂的搜索结果

技术特点

因为各种客观因素和特殊需要，本功能会有以下关键要素：

把最费劲的FFT放到交给客户端（浏览器）处理，降低服务器负荷
东方同人曲相对来说不算多，可是部分同人曲旋律相似度很高
本WIKI有庞大（？）的同人音乐资料库，对传回曲目详细信息会有帮助

实现平台

Javascript: 文件读取、音频分析、寻找特征点、显示搜索结果
PHP: 关联特征点、储存搜索特征点、分析搜索结果
MySQL 及 Hash Database: 配对特征点、返回曲目信息

由于用于实验的Windows平台没有好用的Hash Database，所以只能用MySQL凑合，unix平台的话就可以用Constant Hash Database。

技术验证

此段会对每个阶段实际的做法做详细的分析，但考虑到可能会被Shazam律师盯上不会写太详细的东西

文件读取

因为要把最费功夫的FFT在客户端实现，文件读取和解码只能用Javascript实现。文件选择和读取不是什么难事，用表单浏览或拖曳文件，FileReader什么的。难点是解码，总不能只支持wav，其他常用的格式至少mp3都要支持。

然后我找到了Audiocogs制作的aurora系列库，立刻就把这个难题解决了。比较遗憾的是目前只有mp3、alac、flac及acc的解码器，没有tta的。

aurora可以有序地读取File物件，将解码出来的变为时间×振幅资讯作一波一波的Event异步发送到我的音频分析函数。另外它还可以读取tag和一堆技术信息。不过就是有时候会出现无法解码的Error，此库还是有一点不成熟的地方。

音频分析

离散快速傅里叶变换，好高大上的名称。不过其实也没什么，演算法通街都有，简单算法：

function Fourier( input ) {
	var data = [];
	data[0] = 0;
	var n = input.length;
	var j = 1;
	for ( i = 0; i < n; ++i ) data[i+1] = input[i];
	for ( i = 1; i < n; i += 2 ) {
		if ( j > i ) {
			var temp = [data[(i+0)], data[(j+0)], data[(i+1)], data[(j+1)]];
			data[(j+0)] = temp[0];
			data[(i+0)] = temp[1];
			data[(j+1)] = temp[2];
			data[(i+1)] = temp[3];
		}
		var m = n >> 1;
		while ( (m >= 2) && (j > m) ) {
			j -= m;
			m = m >> 1;
		}
		j += m;
	}
	var mmax = 2;
	
	while ( n > mmax ) {
		var istep = mmax << 1;
		var theta = 2*Math.PI/mmax;
		var wtemp = Math.sin(0.5 * theta);
		var wpr   = -2*wtemp*wtemp;
		var wpi   = Math.sin(theta);
		var wr = 1;
		var wi = 0;
		for (m = 1; m < mmax; m += 2) {
			for ( i = m; i <= n; i += istep) {
				j = i + mmax;
				var tempr = wr * data[j]   - wi * data[j+1];
				var tempi = wr * data[j+1] + wi * data[j];
				data[j]   = data[i]   - tempr;
				data[j+1] = data[i+1] - tempi;
				data[i]   += tempr;
				data[i+1] += tempi;
				//if ( isNaN( data[j] ) )console.log(j, data[j]);
			}
			wtemp = wr;
			wr = (wr * wpr) - (wi    * wpi) + wr;
			wi = (wi * wpr) + (wtemp * wpi) + wi;
		}
		mmax = istep;
	}
	var output = [];
	var imax = data.length >> 1;
	var mult = n/4*Math.SQRT2;
	for ( i = 1; i < imax; i += 2 ) {
		var c = Cabs( data[i] / mult, data[i+1] / mult );
		output[i>>1] = c < 1E-8 ? 0 : c;
	}
	return output;
}
function Cabs ( x, y ) {
	x = Math.abs(x);
	y = Math.abs(y);
	if (x < 1E-8) return y;
	if (y < 1E-8) return x;
	if (x > y) {
		var temp = y / x;
		return x * Math.sqrt(1 + temp * temp);
	} 
	var temp = x / y;
	return y * Math.sqrt(1 + temp * temp);
}

关键的是变换的密度和取样数，我采用的是每秒（不论是44100hz还是48000hz）固定做32次双声道混合4096个样本的变换。4096个样本可以保证得到的频率有足够的解析度，尤其是低频音符密集的情况下也不会纠结成一团，每秒16次则可以确保每次变换的样本都会有重叠范围，提高对位移的兼容性。

变换4096个样本会得出2048个频率正弦及余弦波的强度，其中后半和前半是对称的，0号是直流，实际上只有直流和1023个频率。

寻找特征点

这个步骤我研究和测试了好久才得出了一个比较好的解法。

对于人眼来说，特征点可能就是在频谱图中比周围的点亮的点，理想的情况是找到所有在周围特定范围内最强的点，但这得要比对极大量的点和数据，演算法也很复杂，对位移和截取可能也会很敏感，完全不实际。

最大的难题是低频的强度要比高频的强得多，强度也没有绝对的上下限和比例。如果单纯寻找每秒强度最高的几个点，那就只会找到最低频的那些点，稍微高一点的都没机会。我本来也认为按频率固定分段是最好和简单的解决方法，但硬性分段会带来更多更严重的问题，分段方式所需的实验数据也很难保证在全部数据中也能表现得好。

又研究了一阵子，发现只要有适当的方法，对各种频率进行曲线加权是最理想的方法，也是最理论式的，可以尽可能不受到不完全的实验和主观因素影响。

目前来说最适合的加权方法莫过于用响度，响度是人耳对不同频率的声响感受上的大小，即使是同样强度、声压、分贝，一般人对低频和极高频的声音都不太敏感，2000Hz左右的音频就会觉得特别响，只要根据响度来加权，就可以得出对人耳最响的频率，而不仅仅是对机器最响的频率。

响度和频率的关系并没有理论公式，只有实验公式，不过对这种应用来说一点点误差不算什么，简单算法：

function weight ( f ) {
	var f2 = f * f;
	return ( 148840000 * f2 * f2 )/( ( f2 + 424.36 )*( f2 + 148840000 )*Math.sqrt( ( f2 + 11599.29 )*( f2 + 544496.41 ) ) );
}

如此一来就不需要分区了，演算法简化了好多，找特征点的间隔时间也自由得多，一秒4个点会比较能适当还原旋律。

向服务器传送资料

至此客户端（浏览器）可以做的工作已经没有了，是时候把数据传送到服务器了。在这个关节点传送资料可以将费劲的步骤尽量留给客户端（浏览器），减轻服务器负担，并可以最大限度地减少资料的传送量。下一个步骤其实也可以在客户端（浏览器）执行，只不过这会让需要传送的资料量大大增加，降低效率。

需要传送的资料格式很简单：

[ //包含大量特征点的阵列
 [ 频率1, 时间1 ],
 [ 频率2, 时间2 ],
 ...
 [ 频率n, 时间n ]
]

要把这些资料传送出去的话就要把这些资料变成字串，这个做法有很多。刚开始实验的时候我用冒号分隔频率和时间；用逗号分隔特征点；用空格分隔区间（如果有的话），虽然最后出来字串很长但很皮实。

后来我用Base64强力最小化了字串长度。每个特征点均由一个极限为1023的频率和一个应该不会超过65535（换算下来如果要超过此值曲目需要有68分钟长度）的时间组成，即是10bits的频率f和16bits的时间t，一共26bits，可以用5个64进制符号表示，即是：

00ffff ffffff 00tttt tttttt tttttt

每秒有4个点，一个点5个字，一秒就大概会有20个字，一个字也就1byte，正常一首曲目260秒也就5KB。

64进制符号采用“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789*-”，区间分隔符用“_”，简单算法：

function decode( $c ) {
	$c = ord( $c );
	if ( $c > 96 ) return $c - 71;
	elseif ( $c > 64 ) return $c - 65;
	elseif ( $c > 47 ) return $c + 4;
	elseif ( $c == 42 ) return 62;
	return 63;
}
function encode( $c ) {
	if ( $c == 62 ) return chr(42);
	elseif ( $c == 63 ) return chr(45);
	elseif ( $c > 51 ) return chr($c - 4);
	elseif ( $c > 25 ) return chr($c + 71);
	return chr($c + 65);
}

关联特征点

关联特征点是为了增加搜索准确度，简单来说就是把一个特征点和其后的特征点两两连结，成为

特征点1频率 特征点2频率 两点时间差 特征点1时间

的一条资料，搜的时候也是两点连结一起搜索，可以有效缩小结果范围。为了搜索效率，更加好的是把特征点1频率、特征点2频率和两点时间差制作成一条哈希，储存在一个哈希表或SQL里面，搜的时候只需要完全等于就足够。

频率fr为10bits，时间差o精度不需要太高，太高反而搜索不了，3bits就够了，加起来是23bits，刚好能放进一个24bits的MEDIUMINT，正好还有可以用来控制有效状态c的1bit：

cfffffff fffrrrrr rrrrrooo

以上倒不是难的地方，难的是虽然在有分区的情况下只要把同分区的几个相邻的点关联到一起就可以了，但对于每一个点要关联多少个点、横跨多少秒，还是需要通过试验来找出答案的。

一开始我设定是关联10个点，结果实在太多点了效率太低，而且横跨太多秒，准确度会降低。之后我减少到6个，还是太多，尤其是最低频率（6），搜索非常慢。最后我设定如果是最低频率（6）的话，只关联后4秒（2点），其他关联后8秒（5点）。效果很好，最低频率（6）关联距离只有一半顺便还可以把时间差精度提升一倍，把哈希重复情况降低一半。改用响度曲线加权之后，关联后1秒（4点）大概就够了。

储存特征点

数据库里面，会储存着很多条特征点对的资料，基本由以下元素组成：

项目	大小bits	信息
哈希	24	构成上面已经说过了。这个哈希值在中频的位置重复率较高，不过这也是没办法的
时间	16	能有68分钟
曲目ID	24	通过曲目ID以及一个独立的表来把特征点对和WIKI资料库关联起来

在使用MySQL的情况下，用PARTITION BY建立分区是非常重要的，不然几千万条资料搜到眼花。稍微做点测试，按每个哈希值出现的频率，平均分到若干（我是255个正常区加一个无效区）个分区里就可以了，这个比较简单。PARTITION BY的用法：

CREATE tablename (
hash MEDIUMINT UNSIGNED NOT NULL
) ENGINE = MYISAM PARTITION BY RANGE (hash) (
PARTITION p0 VALUES LESS THAN (999),
PARTITION p1 VALUES LESS THAN (10086),

PARTITION p12 VALUES LESS THAN (12450),

PARTITION p70 VALUES LESS THAN (700000),

PARTITION p254 VALUES LESS THAN (8388608),
PARTITION p255 VALUES LESS THAN (MAXVALUE)
);

搜索特征点

搜索的时候只需要用=（完全等于）就可以了，模糊搜索效率太低，或者可以只对高频模糊搜索，不过实际效果可能不会太好。是否需要模糊搜索还需要更多的试验和时间才能有定案。

分析搜索结果

这是最难的步骤，没有之一，需要兼顾的东西太多了，准确度、效率还有内存。

搜索的时候，会拿着一大堆特征点对的哈希，一个一个搜，随便一个哈希尤其是低频的一搜能就拉出来几十万条记录，包含着几十万个时间和曲目ID，其中哪些是对的哪些是错的不一一计算是不可能知道的。

计算方法是把搜到的每一条的时间和当前已知那个点的时间相减，把这个差值按曲目分开统计起来。在所有曲目所有差值之中，出现频率最高的那一个，就是最有可能的曲目，以及最有可能的截取偏移距离。这个操作非常复杂，需要处理的条数也很大，在不影响准确度的情况下适当偷懒甚至提早结束搜索是非常重要的。简单来说就是只要已经处理了一定时长（确保已有趋势大致正确），就开始判定如果第二位的最大值在后面的点以同样（或若干倍）的速率增长，也无法超越现在的第一位的话，就提早结束。或者先处理碰撞情况不太严重的高频，没有定案的时候才处理碰撞较多的低频。

然而当同一首曲目（完全一样或只是简单重编过的）因为在多个专辑中出现而被登记了多次，在数据库产生了多批几乎完全一致的数据，就会导致搜索几个的前二甚至更多位都是位于不同专辑的同一个曲目。这样的话就会难以判断何时提早结束搜索，往往都会搜到最后而结果其实早就已经确定了。

返回曲目信息

在得到了首若干位的曲目ID后，就可以用这些ID去一个独立的表里寻找这些ID对应的词条ID（或者更直接的子物件ID）。然后就可以用这些ID从WIKI获取任意相关资料，就像cd.thwiki.cc一样。

返回曲目信息单纯只是下行的一个步骤，没有必要对数据进行压缩，所以只要用json格式把资讯传回来就行了。

显示搜索结果

UI设计其实是个很大的问题，不过跟后台没太大关系这里不详细说了。

实际问题

商业的音乐识别引擎拥有庞大的数据库，内含几亿首曲目，上千亿个资料点，用超精密超复杂的演算法，也能在短时间内准确找到结果，完全不虚，这完全得归功于其优秀的服务器。

对于服务器很渣的一般网站来说，提供这个功能无疑的自找麻烦。即使采用了很多优化的措施，效果可能仍然会很糟糕，此外也得权衡使用率和成本。

规模

可以用简单的统计方式估算一下数据库可能需要的大小，根据统计：

平均每秒的资料在数据库里会有13.6条资料
每首曲目平均有250秒
WIKI内大概有30000首曲目

13.6×250×30000=102,000,000

在SQL内一条资料需要9Bytes

102,000,000×9Bytes=918,000,000Bytes≈875.47MB

效率

对于大多数样本，结果曲目在数据库中没有重复被登记多次，只需要搜索10到20秒的资料就已经可以找到确定的结果了。这样的搜索一般可以在2秒内完成。

对于有重复的曲目，如何判断是重复，允许在首几位（同一曲目）匹配度都很高的情况下提前结束搜索，仍然是一个难题。

准确度

目前还未有足够测试去统计准确度，只有以下几点是比较明显的：

取样频率差异（比如数据库登记的是44100Hz的，提交的样本是48000Hz的）会导致匹配度略微下降，需要更加长的取样才能找到正确的结果
码率在96kbps以上的话，对匹配度影响很微
即使是来自同一原曲的同人曲，只要有20秒就已经能全部区分了
小于10秒的话几乎是不可能找到正确答案的

使用率

现阶段无法得知，已有的cd.thwiki.cc自开始服务以来平均每天只有10次搜索（可能是因为一直以来bug都比较多）。

注释

↑ 详细原理 http://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf
↑ 试作方式 http://www.redcode.nl/blog/2010/06/creating-shazam-in-java/

[详细原理-1] 详细原理 http://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf

[试作方式-2] 试作方式 http://www.redcode.nl/blog/2010/06/creating-shazam-in-java/

1

2