C/C++知识点之shazam音乐检索算法 附完整c代码

本文主要向大家介绍了C/C++知识点之shazam音乐检索算法 附完整c代码，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

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" #defineDR_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){ unsignedintchannels; 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(inti=0;i<*totalSampleCount;i+=2){ *bufferSave++=(int16_t)((buffer[i]+buffer[i+1])>>1); } *totalSampleCount=*totalSampleCount>>1; } returnbuffer; }

unsignedlonghash(unsignedchar*str){ unsignedlonghash=5381; intc; while(c=*str++) hash=((hash<<5)+hash)+c; returnhash; }

intgenerateHashes(char*input_file,int**hashtable,intsongid,size_tN,intfreqbandWidth,intmaxElems){ printf("reading%s\n",input_file); uint32_tsampleRate=0; uint64_tsamplesize=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); intsect=0; intcnt=0; intnumHashes=0; for(inti=0;i<samplesize;i++){ if(sect<N){ inputBuffer[sect]=(float)pcmdata[i]; sect++; }else{ sect=0; i-=1; cnt++; fft_planplan=fft_plan_dft_r2c_1d(N,inputBuffer,outBuffer,0); fft_execute(plan); fft_destroy_plan(plan); intfreq1=0,freq2=0,freq3=0,freq4=0,freq5=0; intpt1=0,pt2=0,pt3=0,pt4=0,pt5=0; intfreqbandWidth2=freqbandWidth*2; intfreqbandWidth3=freqbandWidth*3; intfreqbandWidth4=freqbandWidth*4; intfreqbandWidth5=freqbandWidth*5; intfreqbandWidth6=freqbandWidth*6; for(intk=freqbandWidth;k<freqbandWidth6;k++){ intfreq=(outBuffer[k].real>0)?(int)outBuffer[k].real:(int)(0-outBuffer[k].real); intMagnitude=(int)(log10f((freq+1))*1000); if(k>=freqbandWidth&&k<freqbandWidth2&&Magnitude>freq1){ freq1=Magnitude; pt1=k; }elseif(k>=freqbandWidth2&&k<freqbandWidth3&&Magnitude>freq2){ freq2=Magnitude; pt2=k; }elseif(k>=freqbandWidth3&&k<freqbandWidth4&&Magnitude>freq3){ freq3=Magnitude; pt3=k; }elseif(k>=freqbandWidth4&&k<freqbandWidth5&&Magnitude>freq4){ freq4=Magnitude; pt4=k; }elseif(k>=freqbandWidth5&&k<freqbandWidth6&&Magnitude>freq5){ freq5=Magnitude; pt5=k; } } charbuffer[50]; sprintf(buffer,"%d%d%d%d%d",pt1,pt2,pt3,pt4,pt5); unsignedlonghashresult=hash(buffer)%maxElems; intkey=(int)hashresult; if(key<0) printf("Invalidkey%d\n",key); hashtable[key][songid]++; numHashes++; } } free(pcmdata); free(inputBuffer); free(outBuffer); returnnumHashes; }

intmain(intargc,char*argv[]){ printf("AudioProcessing\n"); printf("shazamaudiohash\n"); printf("blog:http://cpuimage.cnblogs.com/\n"); intN=512; intfreqbandWidth=50; intmaxSongs=10; size_tmaxElems=200000; int**hashTable; inti=0,n=0; floatcount=0; intnumsongs=0; charfilenames[maxSongs+1][_TINYDIR_FILENAME_MAX]; intfilesizes[maxSongs+1]; intsongScores[maxSongs+1]; floatsongMatch[maxSongs+1]; printf("running...\n"); if(argc<2){ printf("noexcerptfiletoopen\n"); exit(1); } doublestart_total=now(); hashTable=(int**)calloc(maxElems,sizeof(int*)); for(i=0;i<maxElems;i++) hashTable[i]=(int*)calloc(maxSongs+1,sizeof(int)); printf("Generatinghashesfororiginalfiles..\n"); tinydir_dirdir; tinydir_open(&dir,"data"); while(dir.has_next){ tinydir_filefile; tinydir_readfile(&dir,&file); if(file.is_reg){ numsongs++; doublestartTime=now(); filesizes[numsongs]=generateHashes(file.path,hashTable,numsongs,N,freqbandWidth,maxElems); size_ttime_interval=(size_t)(calcElapsed(startTime,now())*1000); songScores[numsongs]=0; printf("%d:%dhashesfor%s\n",numsongs,filesizes[numsongs],file.path); printf("Timetaken:%dseconds%dmilliseconds\n",time_interval/1000,time_interval%1000); strcpy(filenames[numsongs],file.name); } tinydir_next(&dir); } tinydir_close(&dir); printf("Generatinghashesforrecordedfile..\n"); generateHashes(argv[1],hashTable,0,N,freqbandWidth,maxElems); printf("Calculatingscore..\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("Scorefor%s=%f\n",filenames[i],songMatch[i]); if(songMatch[i]>count){ count=songMatch[i]; n=i; } } printf("BestScore:%s\n",filenames[n]); for(i=0;i<maxElems;i++) free(hashTable[i]); free(hashTable); size_tmsec=(size_t)(calcElapsed(start_total,now())*1000); printf("Totaltimetaken:%dseconds%dmilliseconds\n",msec/1000,msec%1000);

return0; } 复制代码 项目地址:

https://github.com/cpuimage/shazam

稍微说明一下:

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

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

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

例如：

shazam_demo.exe有没有.wav

输出：

running...

Generatinghashesfororiginalfiles..

readingdata/冯心怡-暧昧（Cover薛之谦）.wav

1:4881hashesfordata/冯心怡-暧昧（Cover薛之谦）.wav

Timetaken:0seconds268milliseconds

readingdata/薛之谦-别.wav

2:3370hashesfordata/薛之谦-别.wav

Timetaken:0seconds186milliseconds

readingdata/薛之谦-暧昧.wav

3:4879hashesfordata/薛之谦-暧昧.wav

Timetaken:0seconds271milliseconds

readingdata/薛之谦-有没有.wav

4:3938hashesfordata/薛之谦-有没有.wav

Timetaken:0seconds214milliseconds

readingdata/赵大雄-有没有（Cover薛之谦）.wav

5:3937hashesfordata/赵大雄-有没有（Cover薛之谦）.wav

Timetaken:0seconds215milliseconds

Generatinghashesforrecordedfile..

reading有没有.wav

Calculatingscore..

Scorefor冯心怡-暧昧（Cover薛之谦）.wav=0.028478

Scorefor薛之谦-别.wav=0.025519

Scorefor薛之谦-暧昧.wav=0.026645

Scorefor薛之谦-有没有.wav=1.000000

Scorefor赵大雄-有没有（Cover薛之谦）.wav=0.036830

BestScore:薛之谦-有没有.wav

Totaltimetaken:1seconds413milliseconds

本文由职坐标整理并发布，了解更多内容，请关注职坐标编程语言C/C+频道！