Baksiden
Shazam! Musikkalgoritme anerkjennelse, fingeravtrykk og prosessering
Du hører en familiesang på klubben eller restauranten. Du har lyttet til denne sangen tusenvis av ganger på lang tid, og følelsen av sangen berører hjertet ditt. Du vil desperat høre henne igjen om morgenen, men du husker ikke navnet hennes! Heldigvis, i vår fantastiske futuristiske verden, har du en telefon med programvare for musikkgjenkjenning installert. Du kan slappe av, siden programvaren fortalte deg navnet på sangen, slik at du vet at du kan lytte til den om og om igjen til den blir en del av deg ... eller du blir desperat ...
Mobilteknologi , kombinert 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 . Ta en sang på 20 sekunder, uansett om det er introen, verset eller refrenget, vil applikasjonen lage et fingeravtrykk av det innspilte eksemplet, konsultere databasen og bruke musikkgjenkjenningsalgoritmen til å fortelle deg nøyaktig hvilken. er sangen du hører på.
Hvordan fungerer Shazam egentlig? Shazams algoritme Søknaden ble først eksponert av oppfinneren Avery Li-Chung Wang i 2003. I denne artikkelen vil vi snakke om det grunnleggende i Shazam-musikkgjenkjenningsalgoritmen.
Fra analog til digital - ett prøvesignal
Hva er egentlig lyd? Er det noe slags mystisk materiale som vi ikke kan berøre, men som flyr i ørene og får oss til å høre ting?
Dette er selvfølgelig ikke tilfelle. Vi vet at lyd i realiteten er en vibrasjon som forplantes som en mekanisk bølge mekanisk trykkbølge og beveger seg gjennom et medium som luft eller vann. Når denne vibrasjonen når ørene våre, spesielt trommehinnen, beveger den små bein som overfører vibrasjonene til hårcellene dypt nok i vårt indre øre. I tillegg produserer de få hårcellene elektriske impulser som overføres til hjernen vår gjennom hørselsnerven i øret.
Opptaksenheter etterligner denne prosessen ved å trykke lydbølgen inn i et elektrisk signal. En ekte lydbølge i luften er en kontinuerlige trykksignal. I en mikrofon blir den første elektriske komponenten etter dette signalet oversatt til et analogt spenningssignal - igjen kontinuerlig. Dette kontinuerlige signalet er ikke så nyttig i den digitale verden, så før det blir behandlet, må det oversettes til diskret signal et diskret signal som kan lagres digitalt. Dette gjøres ved å fange en digital verdi som representerer amplituden til signalet.
Konvertering innebærer kvantisering kvantiseringen av inngangen som nødvendigvis introduserer en liten mengde feil. Derfor, i stedet for en enkel konvertering, a analog-til-digital-omformer Analog-digital omformer utfører mange konverteringer på veldig små biter av signalet - en prosess kjent som prøvetaking
De Nyquist-Shannon-teorem Nyquist - Shannon-teorem forteller oss hvilken samplingsfrekvens som er nødvendig for å fange en viss frekvens i et kontinuerlig signal. Spesielt, for å fange opp alle frekvensene som et menneske kan høre i et lydsignal, må vi prøve signalet med en frekvens som er dobbelt så stor som det menneskelige hørselsområdet. Det menneskelige øret kan oppdage frekvenser mellom omtrent 20 Hz og 20 000 Hz. Som et resultat har innspillingslyd mesteparten av tiden en samplingsfrekvens på 44 100 Hz. Dette er samplingsfrekvensen til Compact Discs CD-er og er også den mest brukte 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 en hastighet på 25 bilder per sekund ( PAL ) eller 30 bilder per sekund (ved hjelp av en NTSC monokrom videoopptaker) og dekker 20.000 Hz båndbredde som trengs for å matche den profesjonelle tenkningen til analogt opptaksutstyr). Så når du velger frekvensen på prøven som er nødvendig for å bli registrert, vil du sannsynligvis ønske å velge 44,100 Hz.
Opptak - Fange lyden
Det er enkelt å ta opp et samplet lydsignal. Siden moderne lydkort allerede har analoge til digitale omformere, trenger du bare å velge et programmeringsspråk, finne et passende bibliotek og angi samplingsfrekvens, antall kanaler (mono eller stereo) og vanligvis størrelsen på prøve (f.eks. 16-biters prøver). Åpne deretter lydkortlinjen, akkurat som en hvilken som helst inngangsstrøm, og skriv til en byteoppstilling. 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(); Les dataene fra 'TargetDataLine'. (I dette eksemplet er 'Running' en global variabel som stoppes av en annen tråd - for eksempel hvis vi har en 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 dette byteoppsettet er det tidsregistrerte signalet til domenet domene . Tidsdomenesignalet representerer endringen i amplituden til signalet over tid.
I de første tiårene av 1800-tallet gjorde Jean-Baptiste Joseph Fourier den bemerkelsesverdige oppdagelsen at intet signal i tidsdomenet tilsvarer summen av noen (muligens uendelige) antall enkle sinusformede signaler, siden hver komponent har en viss sinusformet frekvens , amplitude og fase. Serien av sinusoider som sammen danner det originale tidsdomenesignalet er kjent som serien av Fourier .
Med andre ord er det mulig å representere hvilket som helst signal i tidsdomenet ganske enkelt ved å gi settet med frekvenser, amplituder og faser som tilsvarer hver sinusform som utgjør signalet. Denne representasjonen av signalet er kjent som domenefrekvensen frekvensdomene . På en måte fungerer frekvensdomenet som en type fingeravtrykk eller signatur for tidsdomenesignalet, og gir en statisk fremstilling av et dynamisk signal.
Følgende animasjon viser Fourier-serien av en 1 HZ firkantbølge squarewave og hvordan en (omtrentlig) firkantbølge kan genereres fra sinusformede komponenter. Signalet vises i tidsdomenet over og i 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 filtrere, øke eller redusere noen frekvenser, eller bare gjenkjenne den nøyaktige stigningen til frekvensene.
Den diskrete Fourier-transformasjonen
Derfor må vi finne en måte å konvertere signalet vårt fra domenemomentet til frekvensdomenet. Her kaller vi det den diskrete Fourie-transformasjonen Diskret Fourier Transform (DFT) for å hjelpe. DFT er en matematisk metode å utføre Fourier-analyse i et diskret (prøvesignal). Konverterer en endelig liste over like lange prøver av en funksjon til listen over koeffisientene til en endelig kombinasjon av komplekse sinusoider, ordnet etter deres frekvenser, med tanke på om sinusoidene hadde blitt prøvetatt i samme andel.
En av de mest populære numeriske algoritmene for beregning av DFT er Rask Fourier-transformasjon (FFT). Den mest brukte er FFT-variasjonen Cooley – Tukey-algoritme . Denne algoritmen er en del-og-erobre-algoritme som rekursivt deler en DFT i flere små DFT-er. Mens evaluering av en DFT krever direkte ELLER( n 2) operasjoner, med en Cooley-Tukey FFT beregnes den i ELLER( n Logg n ) operasjoner.
Det er ikke vanskelig å finne et passende bibliotek for FFT. Her er noen av dem:
- C - FFTW
- C ++ - EigenFFT
- Java - JTransformere
- Python - NumPy
- Rubin - Ruby-FFTW3 (Grensesnitt til FFTW)
Nedenfor er et eksempel på en FFT-funksjon skrevet i Java. (FFT har komplekse tall som input. For å forstå sammenhengen 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 i en sang
En uheldig bivirkning av FFT er at vi mister mye informasjon om timing (selv om dette teoretisk sett kan unngås, overheadytelsen er enorm) for en 3-minutters sang, kan vi se alle frekvensene og deres størrelser, men vi gjør ikke ' t har en anelse når de dukket opp på sangen. Men dette er nøkkelen til informasjonen som gjør sangen slik! På en eller annen måte må vi vite når hver frekvens dukket opp.
Derfor introduserer vi typen skyvevindu, eller datafragment, samt transformasjonen av denne delen av informasjonen. Størrelsen på hvert fragment kan bestemmes på forskjellige måter. For eksempel, hvis vi ønsker å ta opp lyden i stereo, med 16-biters sampler, ved 44 100 Hz, vil ett sekund av lyden være 44 100 eksempler * 2 byte * 2 kanaler ≈ 176 kB. Hvis vi tar 4 kB for størrelsen på et segment, vil vi ha 44 stykker data å analysere i hvert sekund av sangen. Det er en god nok tetthet for detaljert analyse.
La oss nå komme 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 segmentene og utfører en FFT-analyse av hver enkelt.
Når vi har fått informasjon om signalets frekvens, kan vi begynne å danne fingeravtrykk av sangen. Dette er den viktigste delen av hele Shazam-musikkgjenkjenningsprosessen. Hovedutfordringen er hvordan man i havet av de fangede frekvensene skiller mellom de frekvensene som er viktigst. Intuitivt kan vi se etter frekvensene med høyest størrelse (ofte kalt topper).
Imidlertid kan det sterke frekvensområdet i en sang variere mellom lave C - C1 (32,70 Hz) og høye C - C8 (4,186,01 Hz). Dette er et flott intervall på dekk. Så i stedet for å analysere hele frekvensområdet på en gang, kan vi velge flere mindre områder. Velg basert på de vanlige frekvensene til viktige musikkomponenter og analyser hver enkelt separat. For eksempel kan vi bruke intervallene denne fyren valgte for implementeringen 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 øst og høyere tonehøyder (dekker de fleste andre instrumenter og stemmer).
Nå innen hvert intervall kan vi bestemme frekvensen med den høyeste størrelsen. Denne informasjonen utgjør 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] Husk at vi må anta at innspillingen ikke er i perfekt stand (for eksempel et 'døvesal'), og som et resultat må en tilnærmingsfaktor inkluderes. En analyse av tilnærmelsesfaktoren må tas på alvor og i et reelt system må programmet ha en mulighet til å stille denne parameteren i henhold til opptaksforholdene.
For å lette søket blir denne signaturen nøkkelen i en hashtag-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 prosessen, kan vi bygge en komplett database med et fingeravtrykk av hver sang i biblioteket.
I slekt: En Deep Learning Tutorial: Fra Perceptrons til Deep Networks Velge en sang
For å identifisere en sang som for øyeblikket spilles i klubben, ta opp sangen på telefonen din og kjør opptaket ved hjelp av den samme digitale sporingsprosessen som før. Deretter kan du starte det matchende søket i hashtag-databasen.
Når det skjer, tilsvarer mange hashtags forskjellige sanger. For eksempel kan det være at et stykke av en sang høres ut som et fragment av sangen E. Selvfølgelig er dette ikke overraskende - musikere har alltid 'lånt' sangtekster fra hverandre, og i disse dager viser produsentene andre sanger alle tiden. Hver gang vi har startet fra en hashtag, blir antallet mulige kamper mindre, men det er sannsynlig at denne informasjonen ikke alene vil redusere kampen til en enkelt sang. Så det er en ting til vi må bekrefte med vår musikkgjenkjenningsalgoritme, og det er oppsettet.
Prøven som ble registrert i klubben kan være et hvilket som helst poeng i sangen, så vi kan bare ikke matche tidsstempelet på hashtaggen som samsvarer med vårt merkevare. Imidlertid, med flere matchende hashtag-algoritmer, kan vi analysere den relative tiden for kombinasjonen, og derfor øke sikkerheten vår.
Hvis du for eksempel ser i tabellen over, vil du se at hashtaggen '30 51 99 121 195 'tilsvarer både sang A og sang E. Hvis et sekund senere samsvarer vi med hash '34 57 95 111 200', som er mer en kamp for en sang, men i dette tilfellet vet vi at både hasjene stemmer overens og tidsforskjellene også.
// 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 øyeblikk av sangen vi spiller inn i klubben vil falle sammen med hvert tilsvarende øyeblikk av den samme sangen i biblioteket vårt, som vi spiller inn i studio. Opptaket inkluderer mye støy som vil introdusere noen feil i kampene. Så i stedet for å prøve å fjerne alle bortsett fra den riktige sangen fra kamplisten vår, til slutt har vi forsonet oss med å sortere alle sangene i synkende rekkefølge etter sannsynlighet, og vår favoritt er den første sangen på ranglisten.
Opp ned
Her er en oversikt over hele musikkgjenkjennings- og forsoningsprosessen, fra topp til bunn:
For denne typen systemer kan databasen bli ganske stor, så det er viktig å bruke en slags endret database. Det er ikke noe spesielt behov for relasjoner, og datamodellen ender med å bli ganske enkel, så det er et godt tilfelle å bruke en slags NoSQL-database.
Konklusjon, Shazam!
Denne typen programvare for musikkgjenkjenning kan brukes til å finne likhetene mellom sangene. Nå som du forstår hvordan Shazam fungerer, kan du se hvordan dette kan ha applikasjoner utover enkel Shazaming enn den nostalgiske sangen som spiller på taxiradioen. For eksempel kan du hjelpe til med å identifisere plagiering i musikk, eller å finne ut hvem som var den første inspirasjonen for noen pionerer innen blues, jazz, rock, pop eller en hvilken som helst annen sjanger. Kanskje et godt eksperiment ville være å fylle databasen med klassisk musikk fra Bach, Beethoven, Vivaldi, Wagner, Chopin og Mozart og prøve å finne likhetene mellom sangene. Jeg vil tro at selv Bob Dylan, Elvis Presley og Robert Johnson var plagiarists!
Men vi kan fremdeles ikke fordømme dem, for musikk er rett og slett en bølge som vi hører, husker og gjentar i hodene våre, hvor den utvikler seg og endres til vi spiller inn i studioet og gir den videre til neste store musikalske geni.
I slekt: En introduksjon til maskinlæringsteori og dens applikasjoner: En visuell opplæring med eksempler
