Tagumine Ots
Kuidas Shazam töötab? Muusika äratundmise algoritmid, sõrmejälgede võtmine ja töötlemine
Klubis või restoranis kuulete tuttavat laulu. Kuulasite seda laulu tuhat korda ammu ja laulu sentimentaalsus puudutab tõesti teie südant. Sa tahaksid seda homme hädasti südamesse viia, kuid sa ei mäleta selle nime! Õnneks on meie hämmastavas futuristlikus maailmas telefon, millele on installitud muusikatuvastustarkvara, ja olete päästetud. Võite lõõgastuda, sest tarkvara ütles teile loo nime ja teate, et kuulete seda ikka ja jälle, kuni see muutub teie osaks ... või jääte sellest haigeks.
Mobiiltehnoloogiad koos tohutute edusammudega helisignaali töötlemisel on meile andnud algoritmide arendajad võime luua muusikatunnuseid. Üks populaarsemaid muusika tuvastamise rakendusi on Shazam . Kui jäädvustate 20 sekundit laulust, olenemata sellest, kas see on sissejuhatus, värss või koor, loob see salvestatud näidisele sõrmejälje, uurib andmebaasi ja kasutab selle muusika tuvastamise algoritmi, et öelda täpselt, millist lugu kuulate .
Aga kuidas Shazam töötab? Shazami algoritm ilmutas selle leiutaja Avery Li-Chung Wang 2003. aastal maailmale. Selles artiklis käsitleme Shazami muusika tuvastamise algoritmi põhialuseid.
Analoog-digitaalne - signaali proovivõtt
Mis on heli tegelikult? Kas see on mingi müstiline materjal, mida me ei saa puudutada, kuid mis lendab meile kõrva ja paneb meid asju kuulma?
Muidugi pole see päris nii. Me teame, et tegelikkuses on heli vibratsioon, mis levib a-na mehaaniline laine rõhu ja nihke kaudu, näiteks õhus või vees. Kui see vibratsioon jõuab meie kõrvu, eriti kuulmekile, liigutab see väikseid luid, mis edastavad vibratsiooni edasi väikestesse juukserakkudesse sügaval meie sisekõrvas. Lõpuks tekitavad väikesed juukserakud elektrilisi impulsse, mis kanduvad meie ajusse kuulmisnärvi kaudu.
Salvestusseadmed jäljendavad seda protsessi üsna täpselt, kasutades helilainerõhku selle muundamiseks elektriliseks signaaliks. Tegelik helilaine õhus on a pidev rõhusignaal. Mikrofonis muundab esimene selle signaaliga kokku puutunud elektriline komponent analoogpinge signaaliks - jällegi pidev. See pidev signaal pole digitaalses maailmas nii kasulik, nii et enne selle töötlemist tuleb see tõlkida a diskreetne signaal mida saab digitaalselt salvestada. Seda tehakse digitaalse väärtuse hõivamisega, mis tähistab signaali amplituudi.
Teisendamine hõlmab kvantimine sisendist ja sellega kaasneb tingimata väike viga. Seetõttu on ühe konversiooni asemel an analoog-digitaalmuundur teostab palju teisendusi signaali väga väikestele osadele - protsess, mida nimetatakse proovide võtmine
The Nyquist-Shanoni teoreem ütleb meile, milline diskreetimissagedus on vajalik kindla sageduse hõivamiseks pidevas signaalis. Eelkõige selleks, et jäädvustada kõik sagedused, mida inimene helisignaalis kuuleb, peame signaali proovima sagedusega, mis on kaks korda suurem kui inimese kuulmisulatus. Inimese kõrv suudab tuvastada sagedusi vahemikus 20 Hz kuni 20 000 Hz. Seetõttu salvestatakse heli kõige sagedamini proovivõtusagedusega 44 100 Hz. See on proovivõtumäär Kompaktplaadid ja on ka kõige sagedamini kasutatav määr MPEG-1 Heli ( VCD , SVCD , MP3 ). (Selle konkreetse määra valis algselt Sony, kuna seda oli võimalik salvestada modifitseeritud videoseadmetele, mis töötavad kas 25 kaadrit sekundis ( PAL ) või 30 kaadrit sekundis (kasutades NTSC ühevärviline videosalvesti) ja katke 20 000 Hz ribalaius, mida peetakse vajalikuks, et sobitada tolleaegseid professionaalseid analoogsalvestusseadmeid.) Nii et salvestamiseks vajaliku valimi sageduse valimisel soovite tõenäoliselt minna 44 100 Hz sagedusega.
Salvestamine - heli jäädvustamine
Valimisse võetud helisignaali salvestamine on lihtne. Kuna tänapäevastel helikaartidel on juba analoog-digitaalmuundurid, valige lihtsalt programmeerimiskeel, leidke sobiv teek, määrake valimi sagedus, kanalite arv (tavaliselt mono- või stereo), valimi suurus (nt 16-bitised proovid) ). Seejärel avage helikaardilt rida nagu iga sisendvoog ja kirjutage baidimassiivi. Java-s saab seda teha järgmiselt:
private AudioFormat getFormat() { float sampleRate = 44100; int sampleSizeInBits = 16; int channels = 1; //mono boolean signed = true; //Indicates whether the data is signed or unsigned boolean bigEndian = true; //Indicates whether the audio data is stored in big-endian or little-endian order return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian); } final AudioFormat format = getFormat(); //Fill AudioFormat with the settings DataLine.Info info = new DataLine.Info(TargetDataLine.class, format); final TargetDataLine line = (TargetDataLine) AudioSystem.getLine(info); line.open(format); line.start(); Lihtsalt lugege andmeid TargetDataLine -st. (Selles näites on lipp running globaalne muutuja, mille peatab teine lõim - näiteks kui meil on nupuga STOP GUI.)
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); } Aja- ja sagedusdomeen
See, mis meil selles baidimassiivis on, on signaal salvestatud aja domeen . Ajadomeeni signaal tähistab signaali amplituudi muutust ajas.
1800-ndate alguses tegi Jean-Baptiste Joseph Fourier tähelepanuväärse avastuse, et mis tahes signaal ajas on samaväärne mõne (võib-olla lõpmatu) hulga lihtsate sinusoidsete signaalide summaga, arvestades, et igal sinusoidkomponendil on teatud sagedus, amplituud, ja faas. Sinusoidide seeriat, mis koos moodustavad algse ajadomeeni signaali, tuntakse selle nime all Fourieri seeria .
Teisisõnu on võimalik kujutada mis tahes ajadomeeni signaali, andes lihtsalt sageduste, amplituudide ja faaside komplekti, mis vastavad igale signaali moodustavale sinusoidile. Seda signaali kujutist tuntakse kui sagedusdomeen . Mõnes mõttes toimib sagedusdomeen ajadomeeni signaali sõrmejälje või allkirja tüübina, pakkudes dünaamilise signaali staatilist kujutist.
parimate tavade kontoplaani koostamine
Järgmine animatsioon näitab Fourieri seeriat 1 Hz kandiline laine ja kuidas saab sinusoidkomponentidest tekitada (ligikaudse) ruutlaine. Signaali näidatakse ülaltoodud ajapiirkonnas ja allpool sagedusdomeeni.
Allikas: René Schwarz
Signaali analüüs sagedusvaldkonnas lihtsustab paljusid asju tohutult. Digitaalse signaalitöötluse maailmas on see mugavam, kuna insener saab uurida spektrit (signaali esitamist sagedusalas) ja teha kindlaks, millised sagedused on olemas ja millised puuduvad. Pärast seda saab filtreerida, mõnda sagedust suurendada või vähendada või lihtsalt ära tunda antud sageduste täpse tooni.
Diskreetne Fourieri teisendus
Seega peame leidma viisi, kuidas oma signaal ajadomeenist sagedusdomeeniks teisendada. Siin kutsume üles Diskreetne Fourieri teisendus (DFT) abi saamiseks. DFT on esituseks matemaatiline metoodika Fourieri analüüs diskreetsel (valimis) signaalil. See teisendab funktsiooni võrdsete vahedega valimite lõpliku loendi keerukate sinusoidide lõpliku kombinatsiooni koefitsientide loendiks, järjestatuna nende sageduste järgi, kaaludes, kas nendest sinusoididest on võetud proovid sama kiirusega.
Üks populaarsemaid arvulisi algoritme DFT arvutamiseks on Kiire Fourieri teisendus (FFT). Ülekaalukalt kõige sagedamini kasutatav FFT variatsioon on Cooley – Tukey algoritm . See on jagamise ja vallutamise algoritm, mis jagab DFT rekursiivselt paljudeks väiksemateks DFT-deks. DFT hindamine nõuab otseselt VÕI ( n 2) operatsioonide puhul arvutatakse sama tulemus ka Cooley-Tukey FFT-ga VÕI ( n logi n ) toimingud.
FFT jaoks pole keeruline leida sobivat teeki. Siin on mõned neist:
- C - FFTW
- C ++ - EigenFFT
- Java - JTransform
- Python - NumPy
- Rubiin - Rubiin-FFTW3 (Liides FFTW-ga)
Allpool on näide Java-s kirjutatud FFT-funktsioonist. (FFT võtab sisendiks kompleksarvud. Kompleksarvude ja trigonomeetriliste funktsioonide vahelise seose mõistmiseks lugege järgmist Euleri valem .)
public static Complex[] fft(Complex[] x) { int N = x.length; // fft of even terms Complex[] even = new Complex[N / 2]; for (int k = 0; k Ja siin on näide signaalist enne ja pärast FFT analüüsi:
Muusika äratundmine: loo sõrmejälgede võtmine
FFT üks kahetsusväärne kõrvalmõju on see, et me kaotame ajastamise kohta palju teavet. (Ehkki teoreetiliselt on seda võimalik vältida, on esinemise üldkulud tohutud.) Kolme minuti pikkuse loo jaoks näeme kõiki sagedusi ja nende suurusi, kuid meil pole aimugi, millal need loos ilmusid. Kuid see on peamine teave, mis muudab laulu selliseks, nagu see on! Kuidagi peame teadma, millisel ajahetkel iga sagedus ilmus.
Sellepärast tutvustame mingisugust libisevat akent ehk andmepakku ja muudame selle teabe osa. Iga tüki suurust saab määrata mitmel erineval viisil. Näiteks kui salvestame heli stereo kujul 16-bitiste näidistega sagedusel 44 100 Hz, on selle sekundi sekundiks 44 100 näidist * 2 baiti * 2 kanalit ≈ 176 kB. Kui valime tüki suuruseks 4 kB, on meil loo igas sekundis analüüsimiseks 44 tükki andmeid. See on heli tuvastamiseks vajaliku üksikasjaliku analüüsi jaoks piisavalt hea tihedus.
Nüüd tagasi programmeerimise juurde:
byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i Sisemises silmus paneme ajadomeeni andmed (proovid) kompleksarvu, mille kujuteldav osa on 0. Välises tsüklis itereerime kõik tükid ja teostame FFT analüüsi igaühel.
Kui meil on teavet signaali sageduse kohta, võime hakata loo digitaalset sõrmejälge moodustama. See on kogu Shazami heli tuvastamise protsessi kõige olulisem osa. Siin on peamine väljakutse, kuidas püütud sageduste ookeanis vahet teha, millised sagedused on kõige olulisemad. Intuitiivselt otsime kõige suurema sagedusega sagedusi (neid nimetatakse tavaliselt tippudeks).
Kuid ühes loos võib tugevate sageduste vahemik varieeruda madala C-C1 (32,70 Hz) ja kõrge C-C8 (4 186,01 Hz) vahel. See on tohutu intervall, mida tuleb katta. Nii et selle asemel, et analüüsida kogu sagedusvahemikku korraga, saame valida mitu väiksemat intervalli, mis valitakse oluliste muusikaliste komponentide ühiste sageduste põhjal, ja analüüsime kumbagi eraldi. Näiteks võime kasutada intervalle see kutt valis oma rakendamiseks Shazami algoritmi. Need on 30 Hz - 40 Hz, 40 Hz - 80 Hz ja 80 Hz - 120 Hz madalate toonide puhul (hõlmates näiteks basskitarri) ning 120 Hz - 180 Hz ja 180 Hz - 300 Hz keskmiste ja kõrgemate toonide puhul (hõlmab vokaali ja enamikku muid instrumente).
Nüüd saame iga intervalli sees tuvastada lihtsalt suurima sagedusega sageduse. See teave moodustab loo selle tüki allkirja ja sellest allkirjast saab osa kogu laulu sõrmejäljest.
public final int[] RANGE = new int[] { 40, 80, 120, 180, 300 }; // find out in which range is frequency public int getIndex(int freq) { int i = 0; while (RANGE[i] Pange tähele, et peame eeldama, et salvestamine ei toimu ideaalsetes tingimustes (st 'kurtide ruum') ja seetõttu peame lisama fuzz-teguri. Fuzz-faktori analüüsi tuleks võtta tõsiselt ja reaalses süsteemis peaks programmis olema võimalus see parameeter seadistada salvestamise tingimuste põhjal.
Lihtsa heliotsingu hõlbustamiseks saab see allkiri räsitabeli võtmeks. Vastav väärtus on aeg, mil see sageduste kogum loos ilmus, koos loo ID-ga (loo pealkiri ja esitaja). Siin on näide selle kohta, kuidas need kirjed võivad andmebaasis ilmuda.
Hashtag Aeg sekundites Laul 30 51 99 121 19553.52 Esitaja A laul 33 56 92 151 18512.32 Esitaja B laul B 39 26 89 141 25115.34 Esitaja C laul C 32 67 100 128 27078,43 Artisti D laul D 30 51 99 121 19510.89 Esitaja E laul 34 57 95 111 20054.52 Esitaja A laul 34 41 93 161 20211.89 Esitaja E laul
Kui selle muusika tuvastamise protsessi käigus käitame tervet lugude kogu, saame üles ehitada andmebaasi, kus on kogu raamatukogu laulu täielik sõrmejälg.
Seotud: Sügava õppimise õpetus: alates Perceptronist kuni sügavate võrkudeni Muusikaalgoritm: laulu tuvastamine
Klubis praegu mängiva loo tuvastamiseks lindistame laulu oma telefoniga ja käivitame salvestise sama audio sõrmejälgede võtmise protsessiga nagu eespool. Seejärel saame hakata andmebaasist otsima räsimärgendeid.
Sel juhul vastavad paljud räsimärgendid mitme loo muusikatunnusele. Näiteks võib juhtuda, et mõni pala pala A kõlab täpselt nagu mõni pala E. Muidugi pole see üllatav - muusikud on alati lakkumisi ja riffe üksteiselt „laenanud“ ning tänapäeval proovivad produtsendid teisi lugusid aeg. Iga kord, kui sobitame räsimärgendi, väheneb võimalike vastete arv, kuid tõenäoliselt ei kitsenda see teave ainuüksi ühte laulu. Seega on veel üks asi, mida peame oma muusika tuvastamise algoritmiga kontrollima, ja see on ajastus.
Klubis salvestatud proov võib olla pärit loo mis tahes punktist, seega ei saa me sobitada sobitatud räsi ajatemplit meie valimi ajatempliga. Kuid mitme sobitatud räsi korral saame seda analüüsida sugulane matšide ajastuse ja seeläbi meie kindluse suurendamiseks.
Näiteks kui vaatate ülaltoodud tabelit, näete seda räsimärgendit 30 51 99 121 195 vastab nii laulule A kui ka laulule E. Kui sekundi hiljem sobitame räsi 34 57 95 111 200, siis on see veel üks vaste laulule A, kuid sel juhul teame, et nii räsid kui ka ajaerinevused vastavad.
kevadboot erandi käsitlemise parimad tavad
// Class that represents specific moment in a song 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; } } Võtame iüks ja i2 hetkedena salvestatud loos ja jüks ja j2 hetkedena andmebaasis olevast loost. Võime öelda, et meil on kaks ajavahega vastet, kui:
RecordedHash (iüks) = SongInDBHash (jüks) JA RecordedHash (i2) = SongInDBHash (j2)
JA
abs (iüks- i2) = abs (jüks- j2)
See annab meile paindlikkuse loo salvestamiseks algusest, keskpaigast või lõpust.
Lõpuks on ebatõenäoline, et klubis salvestatud loo iga hetk sobib stuudios salvestatud meie raamatukogu sama laulu iga vastava hetkega. Salvestus sisaldab palju müra, mis toob matšides sisse mõne vea. Nii et selle asemel, et proovida oma mängude nimekirjast välja jätta kõik, välja arvatud õige lugu, sorteerime kõige lõpus kõik sobitatud lood tõenäosuse järgi kahanevas järjekorras ja meie lemmik on edetabeli esimene lugu.
Ülevalt alla
Vastuseks küsimusele: 'Kuidas Shazam töötab?' siin on ülevaade kogu muusika tuvastamise ja sobitamise protsessist ülevalt alla:
Sellise süsteemi jaoks võib andmebaas muutuda üsna suureks, seetõttu on oluline kasutada mingit skaleeritavat andmebaasi. Suhete järele pole erilist vajadust ja andmemudel on lõpuks üsna lihtne, nii et see on hea mingisuguse NoSQL-i andmebaasi kasutamiseks.
Kuidas Shazam töötab? Nüüd sa tead
Sellist laulutuvastustarkvara saab kasutada laulude sarnasuste leidmiseks. Nüüd, kui olete aru saanud, kuidas Shazam töötab, näete, kuidas sellel võib olla rakendusi peale selle, et taksoraadios mängitav nostalgiline lugu lihtsalt Shazaming. Näiteks võib see aidata tuvastada muusikas plagieerimist või teada saada, kes oli algupärane inspiratsioon mõnele bluusi, jazzi, rocki, popi või mõne muu žanri pioneerile. Võib-olla oleks hea eksperiment täita laulude näidisandmebaas Bachi, Beethoveni, Vivaldi, Wagneri, Chopini ja Mozarti klassikalise muusikaga ning proovida leida laulude sarnasusi. Võib arvata, et isegi Bob Dylan, Elvis Presley ja Robert Johnson olid plagiaatid!
Kuid ikkagi ei saa me neid süüdi mõista, sest muusika on lihtsalt laine, mida kuuleme, jätame meelde ja kordame oma peas, kus see areneb ja muutub, kuni me selle stuudios salvestame ja järgmisele suurele muusikageenile edasi anname.
Seotud: Sissejuhatus masinõppe teooriasse ja selle rakendustesse: visuaalne õpetus koos näidetega Põhitõdede mõistmine
Kuidas töötab Shazami algoritm?
Shazami algoritm destilleerib loo näidised sõrmejälgedeks ja sobitab need sõrmejäljed tuntud lugude sõrmejälgedega, võttes arvesse nende ajastamist laulu sees.
Mis on heli sõrmejälg?
Heli sõrmejälg on loo näidiste räsimärgendite või allkirjade kogu. Nad mõõdavad, millised sagedused igas valimis on kõige tugevamad.
Kuidas Shazam muusikat leiab?
Shazam leiab muusikat, võrreldes kasutaja sisestatud salvestise heli sõrmejälge oma andmebaasist pärit tuntud laulude sõrmejälgedega.
