用Java做音乐识别软件

几天前我看到了这篇文章: How Shazam Works 。

这让我对 Shazam 一类的应用程序很感兴趣……更重要的是,用 Java 编写类似的程序会有多困难呢?

关于 Shazam

Shazam 是一款用来分析/匹配音乐的应用程序。当你将它安装在手机上并用麦克风采集音源20到30秒,它就能告诉你这是首什么歌。

我第一次使用时感觉太神奇了。“它是怎么办到的!?”。甚至是今天,用了很久后,我依然觉得它有些神奇。如果我们能编写出可以带来相同感觉的程序会不会更棒呢?这是我在上周末的目标。

听着……!

先说重要的,为了获取音乐样品来分析,我们首先需要在 Java 中听取麦克风……!我从没有用 Java 实现过这个,所以我并不清楚会有多难。但结果是这很简单:

final AudioFormat format = getFormat(); //Fill AudioFormat with the wanted settings
DataLine.Info info = new DataLine.Info(TargetDataLine.class, format);
final TargetDataLine line = (TargetDataLine) AudioSystem.getLine(info);
line.open(format);
line.start();

现在我们只要像普通 InputStream 那样从 TargetDataLine 中读取数据:

// In another thread I start:

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);
}

使用这种方式会让打开麦克风和录取所有声音的操作变得非常简单!我现在正在使用的AudioFormat是:

private AudioFormat getFormat() {
    float sampleRate = 44100;
    int sampleSizeInBits = 8;
    int channels = 1; //mono
    boolean signed = true;
    boolean bigEndian = true;
    return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian);
}

所以,现在我们获得了用 ByteArrayOutputStream 包装的录音数据,很好!第一步完成了。

麦克风数据

下个问题是分析数据,当我输出在字节数组中获取的数据时,我获得了一串长长的数据列表,像是这样:

0
0
1
2
4
7
6
3
-1
-2
-4
-2
-5
-7
-8
(etc)

额……对吗?这是声音吗?

为了让数据可视化我将输出放入Open Office形成一张线状图表:

01

 

 

 

 

 

 

 

哦是的!这有点像是’声音‘!就像是使用 Windows Sound Recorder 时看到的一样。

这种数据通常是 时间域 。但这些数据目前对我们来说基本上是无用的……如果你阅读了上面 Shazam 工作方式的文章,你会发现他们使用的是 频谱分析器 而不是直接使用时间域数据。

所以下个大问题是:我们怎么将现在的数据转换成频谱分析?

离散傅里叶变化

为了将数据转换成有用的数据我们需要应用所谓的 离散傅里叶变换 。它能将数据从时域转换成频域。

仅仅有一个问题,如果将数据转换成频域,每一位与时间有关的信息会变得松散。所以需要知道所有频率的大小,但并不清楚他们什么时候出现。

我们需要滑动窗口来解决这个问题。取出数据块(在我的例子中是 4096 字节数据)并且转换这部分信息。那么就知道了出现在 4096字节中所有频率的大小。

实现这些

我并不担心傅里叶变换,而是在谷歌搜索到了所谓的FFT(快速傅里叶转换)的代码,我调用了这个代码块:

byte audio[] = out.toByteArray();

final int totalSize = audio.length;

int amountPossible = totalSize/Harvester.CHUNK_SIZE;

//When turning into frequency domain we'll need complex numbers:
Complex[][] results = new Complex[amountPossible][];

//For all the chunks:
for(int times = 0;times < amountPossible; times++) {
    Complex[] complex = new Complex[Harvester.CHUNK_SIZE];
    for(int i = 0;i < Harvester.CHUNK_SIZE;i++) {
        //Put the time domain data into a complex number with imaginary part as 0:
        complex[i] = new Complex(audio[(times*Harvester.CHUNK_SIZE)+i], 0);
    }
    //Perform FFT analysis on the chunk:
    results[times] = FFT.fft(complex);
}

//Done!

现在我们有了一个 double 数组,它包含了所有 Complex[] 类的数据块。这个数组包含了关于频率的数据。为了将数据可视化我决定实现一个完整的频谱分析器(只是为了保证我获得正确的数据)。我设计了这个程序来显示数据:

for(int i = 0; i < results.length; i++) {
    int freq = 1;
    for(int line = 1; line < size; line++) {
        // To get the magnitude of the sound at a given frequency slice
        // get the abs() from the complex number.
        // In this case I use Math.log to get a more managable number (used for color)
        double magnitude = Math.log(results[i][freq].abs()+1);

        // The more blue in the color the more intensity for a given frequency point:
        g2d.setColor(new Color(0,(int)magnitude*10,(int)magnitude*20));
        // Fill:
        g2d.fillRect(i*blockSizeX, (size-line)*blockSizeY,blockSizeX,blockSizeY);

        // I used a improviced logarithmic scale and normal scale:
        if (logModeEnabled && (Math.log10(line) * Math.log10(line)) > 1) {
            freq += (int) (Math.log10(line) * Math.log10(line));
        } else {
            freq++;
        }
    }
}

介绍一下,Aphex Twin

似乎有些跑题了,但我还想介绍这位名叫 Aphex Twin(Richard David James)的电子音乐家。他创作疯狂的电子音乐。。。。。。但一些歌曲有着有趣的特点。他大热的作品,比如 Windowlicker 中就有频谱图像。如果将这首歌看成是频谱的图像,它展示了一幅漂亮的螺旋。另一首称为“Mathematical Equation”的歌曲显示了 Twin 的脸!在这里可以发现更多信息: Bastwood - Aphex Twin’s face 。

在我的频谱分析器中播放歌曲获得下面结果:

02

 

 

 

 

 

 

 

 

不是很完美,但似乎就是Twin 的脸!

决定关键音乐的点

Shazam 算法下一步是决定歌曲中一些关键点,将这些点存储为哈希表并且尝试与数据库中超过 8 百万的歌曲匹配。这些操作被快速完成,哈希表的查找速度是 O(1)级的。这就解释了 Shazam 令人惊叹的执行力。

因为我想要在一个周末让一切运转起来(可悲的是这是我最长的注意力持续时间,随后我需要开始一个新的工程)我尽可能使我的算法简单。惊奇的是它运转起来了。

我在频谱分析每行中取出一定范围内量级最大的点。在我的例子中范围是:40—80、80—120、120—180、180—300。

//For every line of data:

for (int freq = LOWER_LIMIT; freq < UPPER_LIMIT-1; freq++) {
    //Get the magnitude:
    double mag = Math.log(results[freq].abs() + 1);

    //Find out which range we are in:
    int index = getIndex(freq);

    //Save the highest magnitude and corresponding frequency:
    if (mag > highscores[index]) {
        highscores[index] = mag;
        recordPoints[index] = freq;
    }
}

//Write the points to a file:
for (int i = 0; i < AMOUNT_OF_POINTS; i++) {
    fw.append(recordPoints[i] + "\t");
}
fw.append("\n");

// ... snip ...

public static final int[] RANGE = new int[] {40,80,120,180, UPPER_LIMIT+1};

//Find out in which range
public static int getIndex(int freq) {
    int i = 0;
    while(RANGE[i] < freq) i++;
        return i;
    }
}

现在录取一首歌,我们会得到一个数字列表,像这样:

33	56	99	121	195	
30	41	84	146	199	
33	51	99	133	183	
33	47	94	137	193	
32	41	106	161	191	
33	76	95	123	185	
40	68	110	134	232	
30	62	88	125	194	
34	57	83	121	182	
34	42	89	123	182	
33	56	99	121	195	
30	41	84	146	199	
33	51	99	133	183	
33	47	94	137	193	
32	41	106	161	191	
33	76	95	123	185

如果我录取一首歌并将其可视化,看起来像这样:

03

 

 

 

 

 

 

 

 

(所有红点都是‘重要的点’)

把我的音乐编入索引

为了使算法就绪,我决定将我3000首歌编入索引。你可以仅仅打开mp3文件而不使用麦克风,将文件转换成正确的格式,和使用麦克风一样的方式用 AudioInputStream 读取它们。将立体声音乐转换成单声道音频比我想象的要复杂。在网上找得到的示例(需要在这里粘贴太多的代码了)需要更改一些取样。

匹配!

这个程序最重要的部分是匹配的过程。Shazam 文档显示,他们使用散列法获取匹配然后决定哪首歌是最佳匹配。

与其最后使用点集,我决定使用一串数据(例如“33、47、94、137”)作为一个散列:1370944733(在我的测试中使用3或4个点效果最佳,但是调整很困难,我每次都需要重新检索我的mp3!)

每行使用 4 个点作为哈希码的例子:

//Using a little bit of error-correction, damping
private static final int FUZ_FACTOR = 2;

private long hash(String line) {
    String[] p = line.split("\t");
    long p1 = Long.parseLong(p[0]);
    long p2 = Long.parseLong(p[1]);
    long p3 = Long.parseLong(p[2]);
    long p4 = Long.parseLong(p[3]);
    return  (p4-(p4%FUZ_FACTOR)) * 100000000 + (p3-(p3%FUZ_FACTOR)) * 100000 + (p2-(p2%FUZ_FACTOR)) * 100 + (p1-(p1%FUZ_FACTOR));
}

现在我创建两个数据集:

-一个歌曲列表,List (列表索引是歌曲ID, 字符串是歌曲名)

-哈希表的数据库:Map<Long,List>

哈希表数据库中的 long 代表着哈希表本身,包含许多 DataPoints 对象。

一个DataPoint是这样的:

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;
    }
}

现在我们已经为查找准备好了一切。首先我读取所有的歌曲并且为每个数据点形成哈希表并放进哈希数据库。

第二步是读取我们需要匹配的歌曲数据。检索获得哈希表并查看匹配数据点。

有一个问题,每个哈希表有许多匹配记录,我们怎么决定哪首歌是正确的呢……?匹配的数量?不,这是不可行的。

最重要的是计时。我们必须将时间点重叠……!但是如果我们不知道处在歌曲哪部分该怎么办呢?毕竟,我们本可以简单录取歌曲的最后和弦。

我在查看数据时发现有趣的事情,因为我们有以下的数据:

-一个录音的哈希表

-一个可能匹配的匹配哈希

-一个可能匹配的歌曲ID

-我们自己录音的现在时间

-在可能匹配中的哈希的时间。

现在我们可以用匹配哈希的时间(例如1352行)减去录音的现在时间(例如34行)。这个差和歌曲ID一起存储。起点和差值告诉我们可能处在的歌曲位置。

当我们在录音中完成所有的哈希表时,我们获得了许多歌曲ID和偏移。酷炫的是,如果你获得了许多有匹配偏移的哈希表,你也就找到了歌曲。

结果

例如,听20秒的The Kooks - Match Box,这是程序的输出:

Done loading: 2921 songs

Start matching song...

Top 20 matches:

01: 08_the_kooks_-_match_box.mp3 with 16 matches.
02: 04 Racoon - Smoothly.mp3 with 8 matches.
03: 05 Röyksopp - Poor Leno.mp3 with 7 matches.
04: 07_athlete_-_yesterday_threw_everyting_a_me.mp3 with 7 matches.
05: Flogging Molly - WMH - Dont Let Me Dia Still Wonderin.mp3 with 7 matches.
06: coldplay - 04 - sparks.mp3 with 7 matches.
07: Coldplay - Help Is Round The Corner (yellow b-side).mp3 with 7 matches.
08: the arcade fire - 09 - rebellion (lies).mp3 with 7 matches.
09: 01-coldplay-_clocks.mp3 with 6 matches.
10: 02 Scared Tonight.mp3 with 6 matches.
11: 02-radiohead-pyramid_song-ksi.mp3 with 6 matches.
12: 03 Shadows Fall.mp3 with 6 matches.
13: 04 Röyksopp - In Space.mp3 with 6 matches.
14: 04 Track04.mp3 with 6 matches.
15: 05 - Dress Up In You.mp3 with 6 matches.
16: 05 Supergrass - Can't Get Up.mp3 with 6 matches.
17: 05 Track05.mp3 with 6 matches.
18: 05The Fox In The Snow.mp3 with 6 matches.
19: 05_athlete_-_wires.mp3 with 6 matches.
20: 06 Racoon - Feel Like Flying.mp3 with 6 matches.

Matching took: 259 ms

Final prediction: 08_the_kooks_-_match_box.mp3.song with 16 matches.

这是可行的!!

听20秒就可以匹配几乎我拥有的所有歌曲。甚至是可以在听取这个 编辑器的现场录音 40秒后匹配正确的歌曲!

再次感觉神奇!:-)

目前,这段代码不是发行版也没有运行得很完美。它只是一个周末的拼拼凑凑,更像是理论证明/算法探索。

或许,如果许多人问起它,我会整理后在某处发布。

更新:

Shazam 专利持有人的律师给我发送邮件阻止我发布代码并且要求删除博客,在这里可以看到事件原委。

原文链接: Roy van Rijn 翻译: ImportNew.com - Jyy
译文链接: http://www.importnew.com/21839.html
[ 转载请保留原文出处、译者和译文链接。]



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部