Baksiden
Hvordan fungerer Shazam? Musikkgjenkjenningsalgoritmer, fingeravtrykk og prosessering
Du hører en kjent sang i klubben eller restauranten. Du lyttet til denne sangen for tusen ganger for lenge siden, og sangens sentimentalitet berører virkelig hjertet ditt. Du vil desperat tenke på det i morgen, men du kan ikke huske navnet! Heldigvis, i vår fantastiske futuristiske verden, har du en telefon med programvare for musikkgjenkjenning installert, og du er lagret. Du kan slappe av, fordi programvaren fortalte deg navnet på sangen, og du vet at du kan høre den igjen og igjen til den blir en del av deg ... eller du blir lei av det.
Mobilteknologi , sammen med den enorme fremgangen innen lydsignalbehandling, har gitt oss algoritmeutviklere evnen til å lage musikkgjenkjenninger. En av de mest populære appene for musikkgjenkjenning er Shazam . Hvis du tar 20 sekunder av en sang, uansett om det er intro, vers eller kor, vil det lage et fingeravtrykk for det innspilte eksemplet, konsultere databasen og bruke algoritmen for musikkgjenkjenning for å fortelle deg nøyaktig hvilken sang du lytter til .
Men hvordan fungerer Shazam? Shazams algoritme ble avslørt for verden av oppfinneren Avery Li-Chung Wang i 2003. I denne artikkelen vil vi gå gjennom det grunnleggende i Shazams algoritme for musikkgjenkjenning.
Analog til Digital - Sampling av et signal
Hva er lyd egentlig? Er det et slags mystisk materiale som vi ikke kan berøre, men som flyr inn i ørene våre og får oss til å høre ting?
Dette er selvfølgelig ikke helt tilfelle. Vi vet at lyd i virkeligheten er en vibrasjon som forplantes som en mekanisk bølge av trykk og forskyvning, gjennom et medium som luft eller vann. Når denne vibrasjonen kommer til ørene våre, spesielt trommehinnen, beveger den små bein som overfører vibrasjonen videre til små hårceller dypt i vårt indre øre. Til slutt produserer de små hårcellene elektriske impulser som overføres til hjernen vår gjennom hørselsnerven.
Opptaksenheter etterligner denne prosessen ganske nøye ved å bruke lydbølgens trykk for å konvertere den til et elektrisk signal. En faktisk lydbølge i luft er en kontinuerlige trykksignal. I en mikrofon oversetter den første elektriske komponenten som møter dette signalet det til et analogt spenningssignal - igjen kontinuerlig. Dette kontinuerlige signalet er ikke så nyttig i den digitale verden, så før det kan behandles, må det oversettes til et diskret signal som kan lagres digitalt. Dette gjøres ved å fange en digital verdi som representerer amplituden til signalet.
Konverteringen innebærer kvantisering av inngangen, og det introduserer nødvendigvis en liten mengde feil. Derfor, i stedet for en enkelt konvertering, en analog-til-digital-omformer utfører mange konverteringer på veldig små biter av signalet - en prosess kjent som prøvetaking
De Nyquist-Shannon-teorem forteller oss hvilken samplingsfrekvens som er nødvendig for å fange en viss frekvens i kontinuerlig signal. Spesielt, for å fange opp alle frekvensene som et menneske kan høre i et lydsignal, må vi sampler signalet med en frekvens som er dobbelt så stor som det menneskelige hørselsområdet. Det menneskelige øret kan oppdage frekvenser omtrent mellom 20 Hz og 20 000 Hz. Som et resultat blir lyd oftest tatt opp med en samplingsfrekvens på 44.100 Hz. Dette er samplingsfrekvensen på CD-plater , og er også den mest brukte hastigheten med MPEG-1 Lyd ( VCD , SVCD , MP3 ). (Denne spesifikke hastigheten ble opprinnelig valgt av Sony fordi den kunne spilles inn på modifisert videoutstyr som kjører med enten 25 bilder per sekund ( PAL ) eller 30 bilder per sekund (ved hjelp av en NTSC monokrom videoopptaker) og dekk 20.000 Hz båndbredde som er tenkt nødvendig for å matche profesjonelt analogt opptaksutstyr på den tiden.) Så når du velger frekvensen på prøven som er nødvendig for å bli tatt opp, vil du sannsynligvis ønske å gå med 44,100 Hz.
Opptak - Fange lyden
Det er enkelt å ta opp et samplet lydsignal. Siden moderne lydkort allerede har analog-til-digital-omformere, er det bare å velge et programmeringsspråk, finne et passende bibliotek, angi frekvensen på prøven, antall kanaler (vanligvis mono eller stereo), prøvestørrelse (f.eks. 16-bit eksempler ). Åpne deretter linjen fra lydkortet ditt akkurat som en hvilken som helst inngangsstrøm, og skriv til et byte-utvalg. Slik kan du gjøre det i Java:
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(); Bare les dataene fra TargetDataLine. (I dette eksemplet er flagget running en global variabel som stoppes av en annen tråd - for eksempel hvis vi har GUI med STOPP-knappen.)
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); } Time-Domain og Frequency-Domain
Det vi har i denne byteoppsettet er signal registrert i tids domene . Tidsdomenesignalet representerer amplitudeendringen av signalet over tid.
Tidlig på 1800-tallet gjorde Jean-Baptiste Joseph Fourier den bemerkelsesverdige oppdagelsen at ethvert signal i tidsdomenet tilsvarer summen av noe (muligens uendelig) antall enkle sinusformede signaler, gitt at hver komponent sinusoid har en viss frekvens, amplitude, og fase. Serien av sinusoider som sammen danner det originale tidsdomenesignalet, er kjent som dens Fourier-serien .
Med andre ord er det mulig å representere et hvilket som helst tidsdomenesignal ved ganske enkelt å gi settet med frekvenser, amplituder og faser som tilsvarer hver sinusform som utgjør signalet. Denne representasjonen av signalet er kjent som frekvensdomene . På noen måter fungerer frekvensdomenet som en type fingeravtrykk eller signatur for tidsdomenesignalet, og gir en statisk fremstilling av et dynamisk signal.
Følgende animasjon demonstrerer Fourier-serien på 1 Hz firkantbølge , og hvordan en (omtrentlig) firkantbølge kan genereres ut av sinusformede komponenter. Signalet vises i tidsdomenet ovenfor og frekvensdomenet nedenfor.
Kilde: René Schwarz
Analysering av et signal i frekvensdomenet forenkler mange ting enormt. Det er mer praktisk i verden av digital signalbehandling fordi ingeniøren kan studere spekteret (representasjonen av signalet i frekvensdomenet) og bestemme hvilke frekvenser som er tilstede, og hvilke som mangler. Etter det kan man gjøre filtrering, øke eller redusere noen frekvenser, eller bare gjenkjenne den eksakte tonen fra de gitte frekvensene.
The Discrete Fourier Transform
Så vi må finne en måte å konvertere signalet vårt fra tidsdomenet til frekvensdomenet. Her kaller vi på Diskret Fourier Transform (DFT) for hjelp. DFT er en matematisk metode for å utføre Fourier-analyse på et diskret (samplet) signal. Den konverterer en endelig liste over like fordelte eksempler på en funksjon til listen over koeffisienter for en endelig kombinasjon av komplekse sinusoider, ordnet etter deres frekvenser, ved å vurdere om disse sinusoidene hadde blitt prøvetatt med samme hastighet.
En av de mest populære numeriske algoritmene for beregning av DFT er Rask Fourier-transformasjon (FFT). Den klart mest brukte variasjonen av FFT er Cooley – Tukey-algoritme . Dette er en del-og-erobre algoritme som rekursivt deler en DFT i mange mindre DFT-er. Mens evaluering av en DFT krever direkte ELLER( n 2) operasjoner, med en Cooley-Tukey FFT beregnes det samme resultatet ELLER( n Logg n ) operasjoner.
Det er ikke vanskelig å finne et passende bibliotek for FFT. Her er få av dem:
- C - FFTW
- C ++ - EigenFFT
- Java - JTransform
- Python - NumPy
- Rubin - Ruby-FFTW3 (Grensesnitt til FFTW)
Nedenfor er et eksempel på en FFT-funksjon skrevet i Java. (FFT tar komplekse tall som input. For å forstå forholdet mellom komplekse tall og trigonometriske funksjoner, les om Eulers formel .)
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 Og her er et eksempel på et signal før og etter FFT-analyse:
Musikkgjenkjenning: Fingeravtrykk av en sang
En uheldig bivirkning av FFT er at vi mister mye informasjon om timing. (Selv om dette teoretisk sett kan unngås, er ytelseskostnadene enorme.) For en tre-minutters sang ser vi alle frekvensene og størrelsen deres, men vi har ikke peiling på når i sangen de dukket opp. Men dette er nøkkelinformasjonen som gjør sangen til den den er! På en eller annen måte må vi vite hvilket tidspunkt hver frekvens dukket opp.
Derfor introduserer vi et slags skyvevindu eller en del data, og transformerer bare denne delen av informasjonen. Størrelsen på hver del kan bestemmes på noen forskjellige måter. For eksempel, hvis vi tar opp lyden, i stereo, med 16-biters sampler, ved 44 100 Hz, vil ett sekund av slik lyd være 44 100 eksempler * 2 byte * 2 kanaler ≈ 176 kB. Hvis vi velger 4 kB for størrelsen på en del, vil vi ha 44 biter av data å analysere i hvert sekund av sangen. Det er god nok tetthet for den detaljerte analysen som trengs for lydidentifisering.
Nå tilbake til programmering:
byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i I den indre sløyfen setter vi tidsdomenedataene (prøvene) inn i et komplekst tall med imaginær del 0. I den ytre sløyfen gjentar vi oss gjennom alle biter og utfører FFT-analyse på hver.
Når vi har informasjon om signalets frekvens, kan vi begynne å danne vårt digitale fingeravtrykk av sangen. Dette er den viktigste delen av hele Shazam-lydgjenkjenningsprosessen. Hovedutfordringen her er hvordan man i havet av fangede frekvenser skiller hvilke frekvenser som er de viktigste. Intuitivt søker vi etter frekvensene med høyest størrelse (ofte kalt topper).
I en sang kan imidlertid rekkevidden for sterke frekvenser variere mellom lave C - C1 (32,70 Hz) og høye C - C8 (4,186,01 Hz). Dette er et stort intervall å dekke. Så i stedet for å analysere hele frekvensområdet på en gang, kan vi velge flere mindre intervaller, valgt ut fra de vanlige frekvensene til viktige musikalske komponenter, og analysere hver for seg. For eksempel kan vi bruke intervallene denne fyren valgte for sin implementering av Shazam-algoritmen. Dette er 30 Hz - 40 Hz, 40 Hz - 80 Hz og 80 Hz - 120 Hz for lave toner (dekker for eksempel bassgitar) og 120 Hz - 180 Hz og 180 Hz - 300 Hz for mellomtoner og høyere toner (dekker vokal og de fleste andre instrumenter).
Nå innen hvert intervall kan vi ganske enkelt identifisere frekvensen med den høyeste størrelsen. Denne informasjonen danner en signatur for denne delen av sangen, og denne signaturen blir en del av fingeravtrykket til sangen som helhet.
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] Merk at vi må anta at opptaket ikke er gjort under perfekte forhold (dvs. et 'døve rom'), og som et resultat må vi inkludere en fuzz-faktor. Fuzz-faktoranalyse bør tas på alvor, og i et reelt system bør programmet ha en mulighet til å sette denne parameteren basert på opptaksforholdene.
For å gjøre det enkelt for lydsøk, blir denne signaturen nøkkelen i en hash-tabell. Den tilsvarende verdien er tiden dette frekvenssettet dukket opp i sangen, sammen med sang-ID (sangtittel og artist). Her er et eksempel på hvordan disse postene kan vises i databasen.
Emneknagg Tid på sekunder Sang 30 51 99 121 19553,52 Sang A av artist A. 33 56 92 151 18512.32 Sang B av artist B 39 26 89 141 25115.34 Sang C av artist C 32 67 100 128 27078.43 Sang D av artist D. 30 51 99 121 19510.89 Sang E av artist E. 34 57 95 111 20054,52 Sang A av artist A. 34 41 93 161 20211.89 Sang E av artist E.
Hvis vi kjører et helt bibliotek med sanger gjennom denne musikkidentifikasjonsprosessen, kan vi bygge opp en database med et fullstendig fingeravtrykk av hver sang i biblioteket.
I slekt: En Deep Learning Tutorial: Fra Perceptrons til Deep Networks Musikkalgoritmen: Song Identification
For å identifisere en sang som for øyeblikket spilles i klubben, spiller vi inn sangen med telefonen vår, og kjører innspillingen gjennom samme lydfingeravtrykk som ovenfor. Deretter kan vi begynne å søke i databasen etter samsvarende hash-koder.
Når det skjer, vil mange av hash-kodene tilsvare musikkidentifikatoren til flere sanger. For eksempel kan det være at noe av sang A høres ut som et stykke E. Dette er selvfølgelig ikke overraskende - musikere har alltid 'lånt' licks og riff fra hverandre, og i disse dager prøver produsenter andre sanger alle tiden. Hver gang vi matcher en hash-tag, blir antallet mulige kamper mindre, men det er sannsynlig at denne informasjonen ikke alene vil begrense kampen til en enkelt sang. Så det er en ting til som vi må sjekke med vår musikkgjenkjenningsalgoritme, og det er timingen.
Prøven vi spilte inn i klubben kan være fra hvilket som helst punkt i sangen, så vi kan ikke bare matche tidsstemplet for den matchede hashen med tidsstemplet i eksemplet vårt. Imidlertid, med flere matchede hashes, kan vi analysere slektning tidspunktet for kampene, og øker derfor vår sikkerhet.
Hvis du for eksempel ser i tabellen over, vil du se den hash-taggen 30 51 99 121 195 tilsvarer både sang A og sang E. Hvis vi, ett sekund senere, matcher hash 34 57 95 111 200, er det en kamp for sang A, men i dette tilfellet vet vi at både hasj og tidsforskjeller stemmer overens.
// 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; } } La oss ta Jegen og Jeg2 som øyeblikk i den innspilte sangen, og jen og j2 som øyeblikk i sangen fra databasen. Vi kan si at vi har to kamper med tidsforskjellskamp hvis:
RecordedHash (ien) = SongInDBHash (jen) OG RecordedHash (i2) = SongInDBHash (j2)
OG
abs (ien- Jeg2) = abs (jen- j2)
Dette gir oss fleksibilitet til å spille inn sangen fra begynnelsen, midten eller slutten.
Til slutt er det lite sannsynlig at hvert eneste øyeblikk av sangen vi spiller inn i klubben vil matche hvert tilsvarende øyeblikk av den samme sangen i biblioteket vårt, spilt inn i studio. Opptaket vil inneholde mye støy som vil føre til feil i kampene. Så i stedet for å prøve å eliminere alle bortsett fra den riktige sangen fra listen vår over kamper, helt på slutten, sorterer vi alle matchede sanger i synkende rekkefølge, og vår favoritt er den første sangen på ranglisten.
Fra topp til bunn
For å svare på spørsmålet: 'Hvordan fungerer Shazam?' her er en oversikt over hele musikkgjenkjennings- og matchingprosessen, fra topp til bunn:
For denne typen system kan databasen bli ganske stor, så det er viktig å bruke en slags skalerbar database. Det er ikke noe spesielt behov for relasjoner, og datamodellen ender med å bli ganske enkel, så det er en god sak å bruke en slags NoSQL-database.
Hvordan fungerer Shazam? Nå vet du
Denne typen programvare for sanggjenkjenning kan brukes til å finne likhetene mellom sangene. Nå som du forstår hvordan Shazam fungerer, kan du se hvordan dette kan ha applikasjoner utover bare Shazaming den nostalgiske sangen som spilles på taxiradioen. For eksempel kan det hjelpe å identifisere plagiering i musikk, eller å finne ut hvem som var den første inspirasjonen til noen pionerer innen blues, jazz, rock, pop eller andre sjangre. Kanskje et godt eksperiment ville være å fylle opp sangeksempeldatabasen med den klassiske musikken til Bach, Beethoven, Vivaldi, Wagner, Chopin og Mozart og prøve å finne likhetene mellom sangene. Du skulle tro at selv Bob Dylan, Elvis Presley og Robert Johnson var plagiarister!
Men likevel kan vi ikke overbevise dem, for musikk er bare en bølge som vi hører, husker og gjentar i hodene våre, hvor den utvikler seg og endres til vi tar den inn i studioet og viderefører den til neste store musikalske geni.
I slekt: En introduksjon til maskinlæringsteori og dens applikasjoner: En visuell opplæring med eksempler Forstå det grunnleggende
Hvordan fungerer Shazam-algoritmen?
Shazam-algoritmen destillerer prøver av en sang til fingeravtrykk, og matcher disse fingeravtrykkene mot fingeravtrykk fra kjente sanger, og tar i betraktning deres timing i forhold til hverandre i en sang.
Hva er et lydfingeravtrykk?
Et lydfingeravtrykk er en samling hash-koder eller signaturer av sangens eksempler. De måler hvilke frekvenser i hver prøve som er sterkest.
Hvordan finner Shazam musikk?
Shazam finner musikk ved å sammenligne lydfingeravtrykket til et brukeroppgitt opptak med fingeravtrykk av kjente sanger fra databasen.
