Taustaa
Shazam! Musiikkialgoritmien, sormenjälkien ja käsittelyn tunnistaminen
Kuulet perhelaulun klubissa tai ravintolassa. Olet kuunnellut tätä kappaletta tuhansia kertoja pitkään aikaan, ja laulun sentimentaalisuus koskettaa todella sydäntäsi. Haluat epätoivoisesti kuulla hänet uudelleen aamulla, mutta et muista hänen nimeään! Onneksi hämmästyttävässä futuristisessa maailmassa sinulla on puhelin, johon on asennettu musiikin tunnistusohjelmisto. Voit rentoutua, koska ohjelmisto kertoi sinulle kappaleen nimen, joten tiedät, että voit kuunnella sitä uudestaan ja uudestaan, kunnes siitä tulee osa sinua ... tai epätoivoisit ...
Mobiiliteknologiat yhdessä valtavan edistymisen kanssa äänisignaalien käsittelyssä ovat antaneet meille, algoritmien kehittäjät , kyky luoda musiikin tunnistimia. Yksi suosituimmista musiikin tunnistussovelluksista on Shazam . Sieppaa kappale 20 sekunnissa riippumatta siitä, onko kyseessä intro, jae vai kuoro, sovellus luo tallennetusta näytteestä sormenjäljen, etsii tietokantaa ja käyttää sen musiikin tunnistusalgoritmia kertoakseen sinulle tarkalleen. on kappale, jota kuuntelet.
Kuinka Shazam todella toimii? Shazamin algoritmi Keksijä Avery Li-Chung Wang paljasti sovelluksen ensimmäisen kerran vuonna 2003. Tässä artikkelissa käsitellään Shazam-musiikin tunnistusalgoritmin perusteita.
Analogisesta digitaaliseen - yksi näytesignaali
Mikä on oikea ääni? Onko se jonkinlainen mystinen materiaali, jota emme voi koskettaa, mutta joka lentää korvissamme ja saa meidät kuulemaan asioita?
Näin ei tietenkään ole. Tiedämme, että ääni on itse asiassa tärinä, joka leviää a mekaaninen aalto mekaaninen paine-aalto ja kulkee väliaineen, kuten ilman tai veden, läpi. Kun tämä tärinä saavuttaa korvamme, erityisesti tärykalvossa, se liikuttaa pieniä luita, jotka välittävät värähtelyt hiussoluihin melko syvälle sisäkorvassamme. Lisäksi harvat hiussolut tuottavat sähköisiä impulsseja, jotka välittyvät aivoihimme korvan kuulohermon kautta.
Tallennuslaitteet jäljittelevät tätä prosessia painamalla ääniaalto sähköiseksi signaaliksi. Todellinen ääniaalto ilmassa on a jatkuva painesignaali. Mikrofonissa ensimmäinen sähkökomponentti tämän signaalin kohdatessa muunnetaan analogiseksi jännitesignaaliksi - jälleen jatkuvana. Tämä jatkuva signaali ei ole niin hyödyllinen digitaalisessa maailmassa, joten ennen käsittelyä se on käännettävä erillinen signaali erillinen signaali, joka voidaan tallentaa digitaalisesti. Tämä tapahtuu kaappaamalla digitaalinen arvo, joka edustaa signaalin amplitudia.
Muuntaminen sisältää kvantisointi tulon kvantisointi, joka aiheuttaa väistämättä pienen määrän virhettä. Siksi yksinkertaisen muunnoksen sijasta a analogia-digitaalimuunnin Analogi-digitaalimuunnin suorittaa monia muunnoksia hyvin pienille signaalipaloille - prosessi tunnetaan nimellä näytteenotto
Nyquist-Shannon-lause Nyquist - Shannon-lause kertoo, mikä näytetaajuus on tarpeen tietyn taajuuden kaappaamiseksi jatkuvassa signaalissa. Erityisesti kaikkien taajuuksien kaappaamiseksi, jotka ihminen voi kuulla äänisignaalissa, meidän on näytettävä signaali taajuudella, joka on kaksinkertainen ihmisen kuuloalueeseen nähden. Ihmiskorva pystyy havaitsemaan taajuudet välillä noin 20 Hz - 20 000 Hz. Tämän seurauksena suurin osa tallennetun äänen näytteenottotaajuus on 44 100 Hz. Tämä on CD-levyt CD-levyjä, ja sitä käytetään myös eniten MPEG-1 Ääni ( VCD , SVCD , MP3 ). Sony valitsi alun perin tämän erityisen nopeuden, koska se voitiin tallentaa muokatulle videolaitteelle, jonka nopeus oli 25 kuvaa sekunnissa ( PAL ) tai 30 kuvaa sekunnissa (käyttämällä a NTSC yksivärinen videonauhuri) ja joka kattaa 20 000 Hz: n kaistanleveyden, joka tarvitaan vastaamaan analogisten tallennuslaitteiden ammattimaista ajattelua). Joten kun valitset tallennettavan näytteen taajuuden, haluat todennäköisesti valita 44 100 Hz.
Tallennus - äänen sieppaaminen
Näytteistetyn äänisignaalin nauhoittaminen on helppoa. Koska nykyaikaisilla äänikorteilla on jo analogia-digitaalimuuntimet, sinun tarvitsee vain valita ohjelmointikieli, löytää sopiva kirjasto ja asettaa näytteenottotaajuus, kanavien lukumäärä (mono tai stereo) ja yleensä koko. näyte (esim. 16-bittiset näytteet). Avaa sitten linja äänikortillesi, kuten mikä tahansa tulovirta, ja kirjoita tavutaulukkoon. Näin voit tehdä sen 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(); Lue tiedot kohdasta TargetDataLine. (Tässä esimerkissä 'Käynnissä' on globaali muuttuja, jonka toinen säie pysäyttää - esimerkiksi jos meillä on GUI ja STOP-painike.)
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); } Aikatoimialue ja taajuusalue
Tässä tavutaulukossa on toimialueen aikatallennettu signaali verkkotunnus . Aikavyöhykesignaali edustaa signaalin amplitudimuutosta ajan myötä.
1800-luvun ensimmäisinä vuosikymmeninä Jean-Baptiste Joseph Fourier havaitsi merkittävän havainnon, että mikään signaali aikatasossa ei vastaa joidenkin (mahdollisesti loputtomien) yksinkertaisten sinimuotoisten signaalien määrää, koska jokaisella komponentilla on tietty sinimuotoinen taajuus , amplitudi ja vaihe. Sinusoidusarja, joka yhdessä muodostaa alkuperäisen aikatason signaalin, tunnetaan nimellä sarja Fourier .
Toisin sanoen, on mahdollista edustaa mitä tahansa signaalia aikatasossa yksinkertaisesti antamalla joukko taajuuksia, amplitudeja ja vaiheita, jotka vastaavat kutakin signaalia muodostavaa sinimuotoa. Tämä signaalin esitys tunnetaan toimialueen taajuutena taajuusalueella . Tavallaan taajuusalue toimii eräänlaisena sormenjälkeen tai allekirjoituksena aikatason signaalille, joka tarjoaa dynaamisen signaalin staattisen esityksen.
Seuraava animaatio näyttää Fourier-sarjan 1 HZ: n neliöaaltoja kanttiaalto ja kuinka (likimääräinen) neliöaalto voidaan tuottaa sinimuotoisista komponenteista. Signaali näytetään ajanjaksossa yllä ja taajuusalueella alla.
Lähde: René Schwarz
Signaalin analysointi taajuusalueella yksinkertaistaa monia asioita valtavasti. Se on helpompaa digitaalisen signaalinkäsittelyn maailmassa, koska insinööri voi tutkia spektriä (signaalin esitys taajuusalueella) ja määrittää, mitkä taajuudet ovat läsnä ja mitkä puuttuvat. Sen jälkeen voidaan tehdä suodatus, lisätä tai vähentää joitain taajuuksia tai yksinkertaisesti tunnistaa taajuuksien tarkka sävelkorkeus.
Diskreetti Fourier-muunnos
Siksi meidän on löydettävä tapa muuntaa signaalimme toimialueen hetkestä taajuusalueeksi. Tässä kutsumme sitä diskreetiksi Fourie-muunnokseksi Diskreetti Fourier-muunnos (DFT) auttaa. DFT on matemaattinen menetelmä suorittaa Fourier-analyysi erillisessä (näyte) signaalissa. Muuntaa rajallisen luettelon funktion yhtä kaukana olevista näytteistä monimutkaisten sinimuotojen äärellisen yhdistelmän kertoimien luetteloksi niiden taajuuksien mukaan järjestettynä, ottaen huomioon, onko sinimuotoisista näytteistä otettu samassa suhteessa.
Yksi suosituimmista numeerisista algoritmeista DFT: n laskemiseksi on Nopea Fourier-muunnos (FFT). Yleisimmin käytetty on FFT-muunnos Cooley – Tukey-algoritmi . Tämä algoritmi on jaa ja hallitse -tyyppi, joka jakaa rekursiivisesti DFT: n useiksi pieniksi DFT: ksi. Vaikka DFT: n arviointi vaatii suoraan TAI( n 2) toiminnot, Cooley-Tukey FFT: llä se lasketaan i TAI( n Hirsi n ) toimintaan.
Ei ole vaikeaa löytää sopivaa kirjastoa FFT: lle. Tässä on joitakin niistä:
- C - FFTW
- C ++ - EigenFFT
- Java - JTransform
- Python - NumPy
- Rubiini - Ruby-FFTW3 (Liitäntä FFTW: hen)
Alla on esimerkki Java-kielellä kirjoitetusta FFT-toiminnosta. (FFT: llä on kompleksiluvut syötteenä. Jos haluat ymmärtää kompleksilukujen ja trigonometristen funktioiden välisen suhteen, lue lisätietoja Eulerin kaava .)
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 tässä on esimerkki signaalista ennen ja jälkeen FFT-analyysin:
Musiikin tunnistus: sormenjäljet kappaleessa
FFT: n valitettava sivuvaikutus on, että menetämme paljon tietoa ajoituksesta (vaikka teoreettisesti tämä voidaan välttää, yleiskäyttökyky on valtava) 3 minuutin kappaleessa, voimme nähdä kaikki taajuudet ja niiden suuruudet, mutta emme '' Ei ole aavistustakaan, kun he esiintyivät kappaleessa. Mutta tämä on avain tietoihin, jotka tekevät kappaleesta näin! Jotenkin meidän on tiedettävä, milloin kukin taajuus ilmestyi.
Siksi esitellään liukuvan ikkunan tai datan fragmentin tyyppi sekä tiedon tämän osan muunnos. Kunkin fragmentin koko voidaan määrittää eri tavoin. Esimerkiksi, jos haluamme tallentaa äänen stereona 16-bittisillä näytteillä taajuudella 44 100 Hz, yksi sekunti siitä äänestä on 44 100 näytettä * 2 tavua * 2 kanavaa ≈ 176 kB. Jos otamme 4 kB segmentin kokoon, meillä on 44 kappaletta analysoitavaa kappaleen jokaisessa sekunnissa. Se on tarpeeksi hyvä tiheys yksityiskohtaista analyysiä varten.
Palataan nyt ohjelmointiin:
byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i Sisemmässä silmukassa laitamme aikatasotiedot (näytteet) kompleksilukuun, jonka kuvitteellinen osa on 0. Ulommassa silmukassa iteroidaan kaikkien segmenttien läpi ja suoritetaan jokaisen FFT-analyysi.
Kun meillä on tietoa signaalin taajuudesta, voimme aloittaa sormenjäljen muodostamisen kappaleesta. Tämä on tärkein osa koko Shazam-musiikin tunnistusprosessia. Suurin haaste on, kuinka erotetaan kaapattujen taajuuksien meressä tärkeimmät taajuudet. Intuitiivisesti voimme etsiä taajuuksia, joiden suuruus on suurin (kutsutaan yleisesti huippuiksi).
Kappaleessa voimakas taajuusalue voi kuitenkin vaihdella matalan C - C1 (32,70 Hz) ja korkean C - C8 (4186,01 Hz) välillä. Tämä on hieno väli kannella. Joten sen sijaan, että analysoimme koko taajuusaluetta kerralla, voimme valita useita pienempiä alueita. Valitse tärkeiden musiikkikomponenttien yhteisten taajuuksien perusteella ja analysoi kukin erikseen. Voisimme esimerkiksi käyttää intervalleja Tämä kaveri valitsi sen toteuttamiseksi Shazam-algoritmin. Nämä ovat 30 Hz - 40 Hz, 40 Hz - 80 Hz ja 80 Hz - 120 Hz matalille sävyille (esimerkiksi bassokitara) ja 120 Hz - 180 Hz ja 180 Hz - 300 Hz itään ja korkeammat sävelet (kattavat useimmat muut soittimet ja äänet).
Nyt jokaisella aikavälillä voimme määrittää taajuuden suurimmalla voimakkuudella. Nämä tiedot ovat allekirjoitus tälle kappaleelle, ja tästä allekirjoituksesta tulee osa kappaleen sormenjälkeä kokonaisuutena.
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] Huomaa, että meidän on oletettava, että nauhoitus ei ole moitteettomassa kunnossa (esimerkiksi 'kuurojen huone') ja sen seurauksena likiarvo on sisällytettävä. Lähestymistekijän analyysi on otettava vakavasti, ja todellisessa järjestelmässä ohjelmalla on oltava mahdollisuus asettaa tämä parametri tallennusolosuhteiden perusteella.
Haun helpottamiseksi tästä allekirjoituksesta tulee avain hashtag-taulukossa. Vastaava arvo on aika, jonka taajuussarja ilmestyi kappaleessa, sekä kappaleen tunnus (kappaleen nimi ja esittäjä). Tässä on esimerkki siitä, kuinka nämä tietueet voivat näkyä tietokannassa.
Hashtag Aika sekunneissa Laulu 30 51 99 121 19553,52 Esittäjän A laulu A 33 56 92 151 18512.32 Laulu B taiteilija B 39 26 89 141 25115.34 Laulu C, taiteilija C 32 67 100 128 27078,43 Laulu D taiteilija D 30 51 99 121 19510.89 Laulu E taiteilija E 34 57 95 111 20054.52 Esittäjän A laulu A 34 41 93 161 20211.89 Laulu E taiteilija E
Jos suoritamme koko kirjaston kappaleita tämän prosessin kautta, voimme rakentaa täydellisen tietokannan, jossa on sormenjäljet kustakin kirjaston kappaleesta.
Liittyvät: Syväoppimisopetus: Perceptronista syvään verkostoon Kappaleen valitseminen
Voit tunnistaa klubissa toistettavan kappaleen nauhoittamalla kappaleen puhelimeesi ja suorittamalla nauhoituksen samalla digitaalisella seurantaprosessilla kuin aiemmin. Sitten voit aloittaa vastaavan haun hashtag-tietokannasta.
Kuten tapahtuu, monet hashtagit vastaavat erilaisia kappaleita. Esimerkiksi voi olla, että jokin kappale kappaleesta kuulostaa täsmälleen samalta kappaleelta kuin kappale E. Tietysti tämä ei ole yllättävää - muusikot ovat aina 'lainanneet' kappaleiden sanoituksia toisiltaan, ja nykyään tuottajat näyttävät muille kappaleille kaikki aika. Joka kerta, kun aloitamme hashtagista, mahdollisten osumien määrä pienenee, mutta on todennäköistä, että pelkästään tämä tieto ei pelkkä ottelua yhdeksi kappaleeksi. Joten on vielä yksi asia, joka meidän on tarkistettava musiikin tunnistusalgoritmillamme, ja se on asettelu.
Klubissa rekisteröity näyte voi olla mikä tahansa kohta kappaleessa, joten emme yksinkertaisesti pysty vastaamaan hashtagin aikaleimaa näytemerkkiamme vastaavalla tavalla. Useilla vastaavilla hashtag-algoritmeilla voimme kuitenkin analysoida yhdistelmän suhteellisen ajan ja lisätä siten turvallisuuttamme.
Esimerkiksi, jos tarkastelet yllä olevaa taulukkoa, huomaat, että hashtag '30 51 99 121 195 'vastaa sekä kappaletta A että kappaletta E. Jos sekunnin kuluttua sovitamme hash-koodin '34 57 95111200 200', joka on pikemminkin kappaleen ottelu, mutta tässä tapauksessa tiedämme, että sekä hashit vastaavat että aikaerot.
// 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; } } Otetaan iyksi ja i2 hetkinä nauhoitetussa kappaleessa, ja jyksi ja j2 hetkinä kappaleessa tietokannasta. Voimme sanoa, että meillä on kaksi ottelua aikaero-ottelun kanssa, jos:
RecordedHash (iyksi) = SongInDBHash (jyksi) JA RecordedHash (i2) = SongInDBHash (j2)
JA
abs (iyksi- i2) = abs (jyksi- j2)
Tämä antaa meille joustavuutta tallentaa kappaletta alusta, keskeltä tai lopusta.
Lopuksi on epätodennäköistä, että klubissa nauhoittamasi kappaleen jokainen hetki osuu samaan aikaan vastaavan hetken kirjastossamme olevan saman kappaleen kanssa, jonka äänitämme studiossa. Tallenne sisältää paljon melua, joka aiheuttaa virheitä otteluissa. Joten sen sijaan, että yritämme poistaa kaikki paitsi oikean kappaleen ottelulistastamme, olemme loppujen lopuksi sovittaneet lajittelemaan kaikki kappaleet todennäköisyyden alenevassa järjestyksessä, ja suosikkimme on ensimmäinen kappale ranking-listalla.
Pohja ylös
Tässä on yleiskatsaus koko musiikin tunnistus- ja sovitteluprosessista ylhäältä alas:
Tämän tyyppisessä järjestelmässä tietokanta voi olla melko suuri, joten on tärkeää käyttää jonkinlaista muuttuvaa tietokantaa. Suhteille ei ole erityistä tarvetta, ja tietomalli on melko yksinkertainen, joten se on hyvä tapa käyttää jonkinlaista NoSQL-tietokantaa.
Päätelmä, Shazam!
Tämän tyyppistä musiikin tunnistusohjelmistoa voidaan käyttää kappaleiden yhtäläisyyksien löytämiseen. Nyt kun ymmärrät Shazamin toiminnan, voit nähdä, kuinka tällä voi olla sovelluksia yksinkertaisen Shazamingin lisäksi kuin taksiradiossa toistettava nostalginen kappale. Voit esimerkiksi auttaa tunnistamaan musiikin plagioinnin tai selvittämään kuka oli inspiraation lähde bluesin, jazzin, rockin, popin tai muun tyylilajin edelläkävijöille. Ehkä hyvä kokeilu olisi täyttää tietokanta Bachin, Beethovenin, Vivaldin, Wagnerin, Chopinin ja Mozartin klassisella musiikilla ja yrittää löytää yhtäläisyyksiä kappaleiden välillä. Luulisin, että jopa Bob Dylan, Elvis Presley ja Robert Johnson olivat plagioijaa!
Mutta emme vieläkään voi tuomita heitä, koska musiikki on yksinkertaisesti aalto, jonka kuulemme, muistan ja toistamme päänämme, missä se kehittyy ja muuttuu, kunnes äänitämme studiossa ja välitämme sen seuraavalle suurelle musiikilliselle neroille.
Liittyvät: Johdatus koneoppimisteoriaan ja sen sovelluksiin: Visuaalinen opetusohjelma esimerkkien kera
