shazam音乐检索算法 附完整c代码

在讲算法之前,上一些前人的资料。

http://coding-geek.com/how-shazam-works/

https://laplacian.wordpress.com/2009/01/10/how-shazam-works/

http://royvanrijn.com/blog/2010/06/creating-shazam-in-java/

当然历史也有点久远了,如果你有心去百度一下 shazam 算法,

你会发现这类的博客也是不少的。

当然这显得我现在写这个,好像有点多余。

这里我就快速过一下算法的思路。

假设你有一首歌,换句话说,你有一堆数据。

你可以通过各种各样的方式,对它的内容进行抽象表达。

举个例子,对音乐而言,就是歌名,类型,时长等等。

对于一本书而言就是目录,标题,价位之类的属性。

但是有时候我们会忘记具体内容,

只知道大概的印象,这个时候想要找到对应的那个东西就比较困难了。

举个例子,Beyond 乐队的《喜欢你》这首歌,百度上一堆 问“黑凤梨” blabla的。。

而音乐检索算法就是为了提供比较人性化的方式帮忙 搜索音乐。

而shazam 这家公司就是第一个吃螃蟹的"人"。

上面提供的链接里都提到了shazam 算法的思路,需要细节了解的可以移步上面的链接。

shazam 算法分为以下步骤:

1.进行fft变换

2.切分5个频段,取频段中比较有代表性的信息,一般为该频段中强度最大值。

3.将取到的5个点,拼接起来算个字符串hash作为该段音乐的特征

4.以此类推对整个音频重复1,2,3步骤

最终拿到整个音频的所有hash信息。

后面检索音频也就是简单的建立hash库,然后撞hash数量,评分。

hash命中越多就认为越相似。

上图,感受一下,其实我感觉看图也不是很直观,哈哈哈哈。

整个算法非常简单,

最核心的点是 切分5个频段,

用上了时序信息去算哈希。

对于有时序的数据,肯定要用上时序性维度,不然是有失偏颇的。

之余图片,就要用空间性维度,之余视频,时间和空间都要有。

这个算法简单粗暴,也有效。

严格意义上讲,这个算法的泛化能力有待商榷。

改进的思路和方向也挺多的。

例如:

1.降低精度,下采样

(之于图像就是缩小图片等)

2.还分为5个频段,但是提取更加具有代表性的特征,

可以采用一些图像思路,例如模糊之后增强

(之于图像一般是计算角点等,详情参考sift)

3.加入更多的时序维度,扩展更多的时序关联,例如临近特征关键点的差距

(之于图像,就是采用卷积提取空间特征等)

4.音量归一化,拉伸音频的分贝值

(之于图像就是直方图拉伸,自动增强,白平衡等)

当然还有很多方法可以进一步拓展,其实核心目标就是控制变量因素。

尽可能的让数据处在先验条件的区间内计算。

其实说难也不难,说简单也不简单。

有另一个音频检索算法就是做了控制变量达到更加强大的鲁棒性。

他就是,dejavu

算法细节参见:http://willdrevo.com/fingerprinting-and-audio-recognition-with-python/

不过dejavu其中有一个地方的思路,我认为不妥,就是在最后算hash特征的时候采用sha-1算法。

我认为可以直接采用最后算出的值改为int16 直接拼合起来就可以了,可以降低算法的复杂度。

dejavu用到了一些图像算法,主要就是用于提取更加具有代表性的特征。

具体算法细节这里就不展开了,有兴趣的朋友可以去好好学习一下。

当然除了以上提到的两个算法之外,还有其他的一些实现,不过都是换汤不换药的节奏。

当然,我本人业余时间在研究自己构思的一个音频检索算法,还在开展中,

算法复杂度当然会更高,但是效果和后续检索准确度会大有提升。

上面提到的shazam和dejavu,本人以纯c 原汁原味实现之。

嗯,shazam的算法,开源给大家学习之。

代码来也:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "fft.h"
//ref:https://raw.githubusercontent.com/cxong/tinydir/master/tinydir.h
#include "tinydir.h"
#include "timing.h"
#define DR_WAV_IMPLEMENTATION
//ref:https://raw.githubusercontent.com/mackron/dr_libs/master/dr_wav.h
#include "dr_wav.h"

int16_t *wavRead_int16(char *filename, uint32_t *sampleRate, uint64_t *totalSampleCount) {
    unsigned int channels;
    int16_t *buffer = drwav_open_and_read_file_s16(filename, &channels, sampleRate, totalSampleCount);
    if (buffer == 0) {
        fprintf(stderr, "ERROR\n");
        exit(1);
    }
    if (channels == 2) {
        int16_t *bufferSave = buffer;
        for (int i = 0; i < *totalSampleCount; i += 2) {
            *bufferSave++ = (int16_t) ((buffer[i] + buffer[i + 1]) >> 1);
        }
        *totalSampleCount = *totalSampleCount >> 1;
    }
    return buffer;
}


unsigned long hash(unsigned char *str) {
    unsigned long hash = 5381;
    int c;
    while (c = *str++)
        hash = ((hash << 5) + hash) + c;
    return hash;
}

int generateHashes(char *input_file, int **hashtable, int songid, size_t N, int freqbandWidth, int maxElems) {
    printf("reading %s \n", input_file);
    uint32_t sampleRate = 0;
    uint64_t samplesize = 0;
    int16_t *pcmdata = wavRead_int16(input_file, &sampleRate, &samplesize);
    float *inputBuffer = (float *) calloc(sizeof(float), N);
    fft_complex *outBuffer = (fft_complex *) calloc(sizeof(fft_complex), N);
    int sect = 0;
    int cnt = 0;
    int numHashes = 0;
    for (int i = 0; i < samplesize; i++) {
        if (sect < N) {
            inputBuffer[sect] = (float) pcmdata[i];
            sect++;
        } else {
            sect = 0;
            i -= 1;
            cnt++;
            fft_plan plan = fft_plan_dft_r2c_1d(N, inputBuffer, outBuffer, 0);
            fft_execute(plan);
            fft_destroy_plan(plan);
            int freq1 = 0, freq2 = 0, freq3 = 0, freq4 = 0, freq5 = 0;
            int pt1 = 0, pt2 = 0, pt3 = 0, pt4 = 0, pt5 = 0;
            int freqbandWidth2 = freqbandWidth * 2;
            int freqbandWidth3 = freqbandWidth * 3;
            int freqbandWidth4 = freqbandWidth * 4;
            int freqbandWidth5 = freqbandWidth * 5;
            int freqbandWidth6 = freqbandWidth * 6;
            for (int k = freqbandWidth; k < freqbandWidth6; k++) {
                int freq = (outBuffer[k].real > 0) ? (int) outBuffer[k].real : (int) (0 - outBuffer[k].real);
                int Magnitude = (int) (log10f((freq + 1)) * 1000);
                if (k >= freqbandWidth && k < freqbandWidth2 && Magnitude > freq1) {
                    freq1 = Magnitude;
                    pt1 = k;
                } else if (k >= freqbandWidth2 && k < freqbandWidth3 && Magnitude > freq2) {
                    freq2 = Magnitude;
                    pt2 = k;
                } else if (k >= freqbandWidth3 && k < freqbandWidth4 && Magnitude > freq3) {
                    freq3 = Magnitude;
                    pt3 = k;
                } else if (k >= freqbandWidth4 && k < freqbandWidth5 && Magnitude > freq4) {
                    freq4 = Magnitude;
                    pt4 = k;
                } else if (k >= freqbandWidth5 && k < freqbandWidth6 && Magnitude > freq5) {
                    freq5 = Magnitude;
                    pt5 = k;
                }
            }
            char buffer[50];
            sprintf(buffer, "%d%d%d%d%d", pt1, pt2, pt3, pt4, pt5);
            unsigned long hashresult = hash(buffer) % maxElems;
            int key = (int) hashresult;
            if (key < 0)
                printf("Invalid key %d\n", key);
            hashtable[key][songid]++;
            numHashes++;
        }
    }
    free(pcmdata);
    free(inputBuffer);
    free(outBuffer);
    return numHashes;
}


int main(int argc, char *argv[]) {
    printf("Audio Processing\n");
    printf("shazam audio hash\n");
    printf("blog: http://cpuimage.cnblogs.com/\n");
    int N = 512;
    int freqbandWidth = 50;
    int maxSongs = 10;
    size_t maxElems = 200000;
    int **hashTable;
    int i = 0, n = 0;
    float count = 0;
    int numsongs = 0;
    char filenames[maxSongs + 1][_TINYDIR_FILENAME_MAX];
    int filesizes[maxSongs + 1];
    int songScores[maxSongs + 1];
    float songMatch[maxSongs + 1];
    printf("running... \n");
    if (argc < 2) {
        printf("no excerpt file to open \n");
        exit(1);
    }
    double start_total = now();
    hashTable = (int **) calloc(maxElems, sizeof(int *));
    for (i = 0; i < maxElems; i++)
        hashTable[i] = (int *) calloc(maxSongs + 1, sizeof(int));
    printf("Generating hashes for original files.. \n");
    tinydir_dir dir;
    tinydir_open(&dir, "data");
    while (dir.has_next) {
        tinydir_file file;
        tinydir_readfile(&dir, &file);
        if (file.is_reg) {
            numsongs++;
            double startTime = now();
            filesizes[numsongs] = generateHashes(file.path, hashTable, numsongs, N, freqbandWidth, maxElems);
            size_t time_interval = (size_t) (calcElapsed(startTime, now()) * 1000);
            songScores[numsongs] = 0;
            printf("%d:%d hashes for %s\n", numsongs, filesizes[numsongs], file.path);
            printf("Time taken: %d seconds %d milliseconds\n", time_interval / 1000, time_interval % 1000);
            strcpy(filenames[numsongs], file.name);
        }
        tinydir_next(&dir);
    }
    tinydir_close(&dir);
    printf("Generating hashes for recorded file.. \n");
    generateHashes(argv[1], hashTable, 0, N, freqbandWidth, maxElems);
    printf("Calculating score.. \n");
    for (i = 0; i < maxElems; i++) {
        if (hashTable[i][0] > 0) {
            for (n = 1; n <= maxSongs; n++) {
                if (hashTable[i][n] >= hashTable[i][0])
                    songScores[n] = songScores[n] + hashTable[i][0];
                else
                    songScores[n] = songScores[n] + hashTable[i][n];;
            }
        }
    }
    for (i = 1; i <= numsongs; i++) {
        songMatch[i] = ((float) songScores[i]) / ((float) filesizes[i]);
        printf("Score for %s = %f\n", filenames[i], songMatch[i]);
        if (songMatch[i] > count) {
            count = songMatch[i];
            n = i;
        }
    }
    printf("Best Score: %s\n", filenames[n]);
    for (i = 0; i < maxElems; i++)
        free(hashTable[i]);
    free(hashTable);
    size_t msec = (size_t) (calcElapsed(start_total, now()) * 1000);
    printf("Total time taken: %d seconds %d milliseconds\n", msec / 1000, msec % 1000);

    return 0;
}

项目地址:

https://github.com/cpuimage/shazam

稍微说明一下:

在对应文件下建一个“data”的文件夹,存放需要进行计算hash备档的音频文件。

然后 直接传一个文件名过去,先计算"data"下所有文件的hash,然后计算传的目标文件的hash。

计算hash碰撞,输出相似度得分。

例如:

shazam_demo.exe 有没有.wav

输出:

running...

Generating hashes for original files..

reading data/冯心怡 - 暧昧(Cover 薛之谦).wav

1:4881 hashes for data/冯心怡 - 暧昧(Cover 薛之谦).wav

Time taken: 0 seconds 268 milliseconds

reading data/薛之谦 - 别.wav

2:3370 hashes for data/薛之谦 - 别.wav

Time taken: 0 seconds 186 milliseconds

reading data/薛之谦 - 暧昧.wav

3:4879 hashes for data/薛之谦 - 暧昧.wav

Time taken: 0 seconds 271 milliseconds

reading data/薛之谦 - 有没有.wav

4:3938 hashes for data/薛之谦 - 有没有.wav

Time taken: 0 seconds 214 milliseconds

reading data/赵大雄 - 有没有(Cover 薛之谦).wav

5:3937 hashes for data/赵大雄 - 有没有(Cover 薛之谦).wav

Time taken: 0 seconds 215 milliseconds

Generating hashes for recorded file..

reading 有没有.wav

Calculating score..

Score for 冯心怡 - 暧昧(Cover 薛之谦).wav = 0.028478

Score for 薛之谦 - 别.wav = 0.025519

Score for 薛之谦 - 暧昧.wav = 0.026645

Score for 薛之谦 - 有没有.wav = 1.000000

Score for 赵大雄 - 有没有(Cover 薛之谦).wav = 0.036830

Best Score: 薛之谦 - 有没有.wav

Total time taken: 1 seconds 413 milliseconds

这个工程只是用来练手学习思路,现在它的使命已经结束。

偷偷说一句,扫头像,有打赏,就有猛料。

以上,权当抛砖引玉。

独乐乐,不如众乐乐。

若有其他相关问题或者需求也可以邮件联系俺探讨。

邮箱地址是:  gaozhihan@vip.qq.com 

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

【AlphaGo Zero 核心技术-深度强化学习教程代码实战02】理解gym的建模思想

点击上方“专知”关注获取更多AI知识! 【导读】Google DeepMind在Nature上发表最新论文,介绍了迄今最强最新的版本AlphaGo Zero,不...

3575
来自专栏专知

【读书笔记】基于知识库的问答:生成查询图进行语义分析

【导读】将DBPedia和Freebase这样的大规模知识库组织并存储在一个结构化的数据库,这已成为支持开放领域问题问答的重要资源。 KB-QA的大多数方法基于...

5067
来自专栏小鹏的专栏

是AI就躲个飞机-纯Python实现人工智能

代码下载:Here。 很久以前微信流行过一个小游戏:打飞机,这个游戏简单又无聊。在2017年来临之际,我就实现一个超级弱智的人工智能(AI),这货可以躲避从...

1K5
来自专栏SDNLAB

5G革命的技术,一个都不能少

第五代移动网络简称5G是产业界即将实现的移动技术革命,是LTE-A网络的深层演进技术。5G网络中的关键技术包括MIMO、OFDM、SC-FDMA等。 超密集微型...

45712
来自专栏数据科学与人工智能

【机器学习】Python语言下的机器学习库

Python是最好的编程语言之一,在科学计算中用途广泛:计算机视觉、人工智能、数学、天文等。它同样适用于机器学习也是意料之中的事。 当然,它也有些缺点;其中一个...

26310
来自专栏机器人网

Python最有用的机器学习工具和库

Python是最好的编程语言之一,在科学计算中用途广泛:计算机视觉、人工智能、数学、天文等。它同样适用于机器学习也是意料之中的事。

1425
来自专栏算法+

基于傅里叶变换的音频重采样算法 (附完整c代码)

如果特定情况下需要,我也可以上matlab,python,delphi,c#,c++等等。

3373
来自专栏ATYUN订阅号

在Python中使用NLTK建立一个简单的Chatbot

也许你听说过Duolingo(多邻国):一种流行的语言学习应用程序,它可以通过游戏来练习一种新的语言。由于其创新的外语教学风格,它非常受欢迎。它的思想很简单:每...

6615
来自专栏生信小驿站

生存分析①R语言

生存分析(Survival analysis)是指根据试验或调查得到的数据对生物或人的生存时间进行分析和推断,研究生存时间和结局与众多影响因素间关系及其程度大小...

2474
来自专栏机器之心

业界 | 微软提出基于程序图简化程序分析,直接从源代码中学习

1793

扫码关注云+社区

领取腾讯云代金券