Cum funcționează Shazam? Algoritmi de recunoaștere a muzicii, amprentare și procesare

Auzi un cântec familiar în club sau restaurant. Ai ascultat această melodie de o mie de ori în urmă, iar sentimentalismul cântecului îți atinge cu adevărat inima. Îți dorești cu disperare să îl inimiți mâine, dar nu-i poți aminti numele! Din fericire, în lumea noastră futuristă uimitoare, aveți instalat un telefon cu software de recunoaștere a muzicii și sunteți salvat. Te poți relaxa, pentru că software-ul ți-a spus numele melodiei și știi că o poți auzi din nou și din nou până când devine o parte din tine... sau te îmbolnăvești de ea.

Tehnologiile mobile, împreună cu progresul imens în procesarea semnalului audio, ne-au oferit dezvoltatorilor de algoritmi capacitatea de a crea dispozitive de recunoaștere a muzicii. Una dintre cele mai populare aplicații de recunoaștere a muzicii este Shazam. Dacă capturați 20 de secunde dintr-o melodie, indiferent dacă este intro, vers sau refren, aceasta va crea o amprentă pentru proba înregistrată, va consulta baza de date și va folosi algoritmul său de recunoaștere a muzicii pentru a vă spune exact ce melodie ascultați. .

Dar cum funcționează Shazam? Algoritmul lui Shazam a fost dezvăluit lumii de către inventatorul său Avery Li-Chung Wang în 2003. În acest articol vom trece peste elementele fundamentale ale algoritmului de recunoaștere a muzicii Shazam.

Analog la Digital - Eșantionarea unui semnal

Ce este de fapt sunetul? Este un fel de material mistic pe care nu îl putem atinge, dar care ne zboară în urechi și ne face să auzim lucruri?

Desigur, acest lucru nu este chiar așa. Știm că, în realitate, sunetul este o vibrație care se propagă ca o undă mecanică de presiune și deplasare, printr-un mediu precum aerul sau apa. Când această vibrație ajunge la urechile noastre, în special la timpan, ea mișcă oasele mici care transmit vibrația mai departe către micile celule de păr din adâncul urechii noastre interne. În cele din urmă, micile celule de păr produc impulsuri electrice, care sunt transmise creierului nostru prin nervul urechii auditive.

Dispozitivele de înregistrare imită acest proces destul de îndeaproape, folosind presiunea undei sonore pentru a o transforma într-un semnal electric. O undă sonoră reală în aer este un semnal continuu de presiune. Într-un microfon, prima componentă electrică care întâlnește acest semnal îl traduce într-un semnal analog de tensiune - din nou, continuu. Acest semnal continuu nu este atât de util în lumea digitală, așa că înainte de a putea fi procesat, trebuie tradus într-un semnal discret care poate fi stocat digital. Acest lucru se realizează prin captarea unei valori digitale care reprezintă amplitudinea semnalului.

Conversia implică cuantificarea intrării și introduce în mod necesar o cantitate mică de eroare. Prin urmare, în loc de o singură conversie, un convertor analog-digital efectuează multe conversii pe bucăți foarte mici de semnal - un proces cunoscut sub numele de eșantionare

Teorema Nyquist-Shannon ne spune ce rată de eșantionare este necesară pentru a capta o anumită frecvență în semnal continuu. În special, pentru a capta toate frecvențele pe care un om le poate auzi într-un semnal audio, trebuie să eșantionăm semnalul la o frecvență de două ori mai mare decât intervalul de auz uman. Urechea umană poate detecta frecvențe între 20 Hz și 20.000 Hz. Ca rezultat, audio este cel mai adesea înregistrat la o rată de eșantionare de 44.100 Hz. Aceasta este rata de eșantionare a discurilor compacte și este, de asemenea, cea mai frecvent utilizată rata audio MPEG-1 (VCD, SVCD, MP3). (Această rată specifică a fost aleasă inițial de Sony, deoarece putea fi înregistrată pe echipamente video modificate care rulează fie la 25 de cadre pe secundă (PAL), fie la 30 de cadre pe secundă (folosind un video recorder monocrom NTSC) și să acopere lățimea de bandă de 20.000 Hz considerată necesară pentru potriviți echipamentele de înregistrare analogice profesionale ale vremii.) Deci, atunci când alegeți frecvența eșantionului care trebuie înregistrată, probabil că veți dori să mergeți cu 44.100 Hz.

Înregistrare - Captarea sunetului

Înregistrarea unui semnal audio eșantionat este ușoară. Deoarece plăcile de sunet moderne vin deja cu convertoare analog-digitale, alegeți doar un limbaj de programare, găsiți o bibliotecă adecvată, setați frecvența eșantionului, numărul de canale (de obicei mono sau stereo), dimensiunea eșantionului (de exemplu, mostre pe 16 biți). ). Apoi deschideți linia de pe placa de sunet la fel ca orice flux de intrare și scrieți într-o matrice de octeți. Iată cum se poate face asta în 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();

Citiți doar datele din TargetDataLine . (În acest exemplu, indicatorul de running este o variabilă globală care este oprită de un alt fir - de exemplu, dacă avem GUI cu butonul STOP.)

 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); }

Domeniul timp și domeniul frecvenței

Ceea ce avem în această matrice de octeți este semnal înregistrat în domeniul timpului. Semnalul din domeniul timpului reprezintă modificarea amplitudinii semnalului în timp.

La începutul anilor 1800, Jean-Baptiste Joseph Fourier a făcut descoperirea remarcabilă că orice semnal din domeniul timpului este echivalent cu suma unui număr (posibil infinit) de semnale sinusoidale simple, având în vedere că fiecare sinusoidă componentă are o anumită frecvență, amplitudine, si faza. Seria de sinusoide care formează împreună semnalul original din domeniul timpului este cunoscută sub numele de seria lui Fourier.

Cu alte cuvinte, este posibil să se reprezinte orice semnal din domeniul timpului, oferind pur și simplu setul de frecvențe, amplitudini și faze corespunzătoare fiecărei sinusoide care formează semnalul. Această reprezentare a semnalului este cunoscută sub numele de domeniul frecvenței. În unele moduri, domeniul de frecvență acționează ca un tip de amprentă sau semnătură pentru semnalul din domeniul timp, oferind o reprezentare statică a unui semnal dinamic.

Următoarea animație demonstrează seria Fourier a unei unde pătrate de 1 Hz și modul în care o undă pătrată (aproximativă) poate fi generată din componente sinusoidale. Semnalul este afișat în domeniul timp de mai sus și în domeniul frecvenței de mai jos.

Analizarea unui semnal în domeniul frecvenței simplifică enorm multe lucruri. Este mai convenabil în lumea procesării digitale a semnalului, deoarece inginerul poate studia spectrul (reprezentarea semnalului în domeniul frecvenței) și poate determina ce frecvențe sunt prezente și care lipsesc. După aceea, se poate filtra, crește sau micșora unele frecvențe sau doar recunoaște tonul exact din frecvențele date.

Transformata Fourier discretă

Deci trebuie să găsim o modalitate de a ne converti semnalul din domeniul timpului în domeniul frecvenței. Aici apelăm la Transformarea Fourier discretă (DFT) pentru ajutor. DFT este o metodologie matematică pentru efectuarea analizei Fourier pe un semnal discret (eșantionat). Convertește o listă finită de eșantioane egal distanțate ale unei funcții în lista de coeficienți ai unei combinații finite de sinusoide complexe, ordonate după frecvențele lor, luând în considerare dacă acele sinusoide au fost eșantionate la aceeași rată.

Unul dintre cei mai populari algoritmi numerici pentru calculul DFT este transformata Fourier rapidă (FFT). De departe, cea mai frecvent utilizată variație a FFT este algoritmul Cooley-Tukey. Acesta este un algoritm de divide-and-conquer care împarte recursiv un DFT în multe DFT-uri mai mici. În timp ce evaluarea unui DFT necesită în mod direct operații O( n 2 ) , cu o FFT Cooley-Tukey același rezultat este calculat în operațiuni O( n log n ) .

Nu este greu să găsești o bibliotecă potrivită pentru FFT. Iată câteva dintre ele:

• C – FFTW
• C++ – EigenFFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (interfață cu FFTW)

Mai jos este un exemplu de funcție FFT scrisă în Java. (FFT ia numere complexe ca intrare. Pentru a înțelege relația dintre numerele complexe și funcțiile trigonometrice, citiți despre formula lui Euler.)

 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 < N / 2; k++) { even[k] = x[2 * k]; } Complex[] q = fft(even); // fft of odd terms Complex[] odd = even; // reuse the array for (int k = 0; k < N / 2; k++) { odd[k] = x[2 * k + 1]; } Complex[] r = fft(odd); // combine Complex[] y = new Complex[N]; for (int k = 0; k < N / 2; k++) { double kth = -2 * k * Math.PI / N; Complex wk = new Complex(Math.cos(kth), Math.sin(kth)); y[k] = q[k].plus(wk.times(r[k])); y[k + N / 2] = q[k].minus(wk.times(r[k])); } return y; }

Și iată un exemplu de semnal înainte și după analiza FFT:

Recunoașterea muzicii: amprenta unui cântec

Un efect secundar nefericit al FFT este că pierdem o mulțime de informații despre sincronizare. (Deși teoretic acest lucru poate fi evitat, costurile de performanță sunt enorme.) Pentru o melodie de trei minute, vedem toate frecvențele și mărimile lor, dar nu avem habar când au apărut în melodie. Dar aceasta este informația cheie care face melodia ceea ce este! Într-un fel, trebuie să știm în ce moment a apărut fiecare frecvență.

De aceea, introducem un fel de fereastră glisantă sau o bucată de date și transformăm doar această parte a informațiilor. Mărimea fiecărei bucăți poate fi determinată în câteva moduri diferite. De exemplu, dacă înregistrăm sunetul, în stereo, cu mostre de 16 biți, la 44.100 Hz, o secundă din acest sunet va fi de 44.100 de mostre * 2 octeți * 2 canale ≈ 176 kB. Dacă alegem 4 kB pentru dimensiunea unei bucăți, vom avea 44 de bucăți de date de analizat în fiecare secundă a cântecului. Aceasta este o densitate suficient de bună pentru analiza detaliată necesară pentru identificarea audio.

Acum revenim la programare:

 byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i < sampledChunkSize; j++) { Complex[chunkSize] complexArray; for(int i = 0; i < chunkSize; i++) { complexArray[i] = Complex(audio[(j*chunkSize)+i], 0); } result[j] = FFT.fft(complexArray); }

În bucla interioară, punem datele din domeniul timp (eșantioanele) într-un număr complex cu partea imaginară 0. În bucla exterioară, repetăm ​​toate bucățile și efectuăm analiza FFT pe fiecare.

Odată ce avem informații despre componența frecvenței semnalului, putem începe să ne formăm amprenta digitală a cântecului. Aceasta este cea mai importantă parte a întregului proces de recunoaștere audio Shazam. Principala provocare aici este cum să distingem, în oceanul de frecvențe captate, care frecvențe sunt cele mai importante. În mod intuitiv, căutăm frecvențele cu cea mai mare magnitudine (numite în mod obișnuit vârfuri).

Cu toate acestea, într-o melodie, intervalul de frecvențe puternice poate varia între Do scăzut - C1 (32,70 Hz) și C - C8 înalt (4186,01 Hz). Acesta este un interval uriaș de acoperit. Deci, în loc să analizăm întreaga gamă de frecvență odată, putem alege mai multe intervale mai mici, alese pe baza frecvențelor comune ale componentelor muzicale importante și să le analizăm pe fiecare separat. De exemplu, am putea folosi intervalele pe care le-a ales acest tip pentru implementarea algoritmului Shazam. Acestea sunt 30 Hz - 40 Hz, 40 Hz - 80 Hz și 80 Hz - 120 Hz pentru tonurile joase (care acoperă chitara bas, de exemplu) și 120 Hz - 180 Hz și 180 Hz - 300 Hz pentru tonurile medii și mai înalte. (acoperă vocea și majoritatea celorlalte instrumente).

Acum, în fiecare interval, putem identifica pur și simplu frecvența cu cea mai mare magnitudine. Aceste informații formează o semnătură pentru această bucată a cântecului, iar această semnătură devine parte a amprentei cântecului în ansamblu.

 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] < freq) i++; return i; } // result is complex matrix obtained in previous step for (int t = 0; t < result.length; t++) { for (int freq = 40; freq < 300 ; freq++) { // Get the magnitude: double mag = Math.log(results[t][freq].abs() + 1); // Find out which range we are in: int index = getIndex(freq); // Save the highest magnitude and corresponding frequency: if (mag > highscores[t][index]) { points[t][index] = freq; } } // form hash tag long h = hash(points[t][0], points[t][1], points[t][2], points[t][3]); } private static final int FUZ_FACTOR = 2; private long hash(long p1, long p2, long p3, long p4) { return (p4 - (p4 % FUZ_FACTOR)) * 100000000 + (p3 - (p3 % FUZ_FACTOR)) * 100000 + (p2 - (p2 % FUZ_FACTOR)) * 100 + (p1 - (p1 % FUZ_FACTOR)); }

Rețineți că trebuie să presupunem că înregistrarea nu se face în condiții perfecte (adică, o „cameră pentru surzi”) și ca urmare trebuie să includem un factor fuzz. Analiza factorului fuzz ar trebui luată în serios, iar într-un sistem real, programul ar trebui să aibă opțiunea de a seta acest parametru în funcție de condițiile înregistrării.

Pentru a facilita căutarea audio, această semnătură devine cheia într-un tabel hash. Valoarea corespunzătoare este momentul în care acest set de frecvențe a apărut în melodie, împreună cu ID-ul melodiei (titlul melodiei și artistul). Iată un exemplu despre cum ar putea apărea aceste înregistrări în baza de date.

Dacă rulăm o bibliotecă întreagă de melodii prin acest proces de identificare a muzicii, putem construi o bază de date cu amprenta digitală completă a fiecărei melodii din bibliotecă.

Algoritmul muzical: Identificarea cântecului

Pentru a identifica o melodie care se redă în prezent în club, înregistrăm melodia cu telefonul nostru și rulăm înregistrarea prin același proces de amprentare audio ca mai sus. Apoi putem începe să căutăm în baza de date etichete hash care se potrivesc.

După cum se întâmplă, multe dintre etichetele hash vor corespunde cu identificatorul muzical al mai multor melodii. De exemplu, s-ar putea ca o bucată din cântecul A să sune exact ca o piesă din cântecul E. Desigur, acest lucru nu este surprinzător - muzicienii au „împrumutat” întotdeauna lick-uri și riff-uri unul de la celălalt, iar în zilele noastre producătorii preiau alte cântece. timpul. De fiecare dată când potrivim o etichetă hash, numărul de potriviri posibile devine mai mic, dar este probabil ca aceste informații singure să nu restrângă potrivirea la o singură melodie. Deci, mai este un lucru pe care trebuie să-l verificăm cu algoritmul nostru de recunoaștere a muzicii și acesta este sincronizarea.

Eșantionul pe care l-am înregistrat în club poate fi din orice punct al melodiei, așa că nu putem pur și simplu să potrivim marcajul de timp al hash-ului potrivit cu marcajul de timp al mostrei noastre. Cu toate acestea, cu mai multe hashuri potrivite, putem analiza momentul relativ al potrivirilor și, prin urmare, ne putem crește certitudinea.

De exemplu, dacă vă uitați în tabelul de mai sus, veți vedea că eticheta hash 30 51 99 121 195 corespunde atât cântecului A, cât și cântecului E. Dacă, o secundă mai târziu, potrivim hash-ul 34 57 95 111 200 , acesta este încă unul. se potrivesc pentru Song A, dar în acest caz știm că atât hashurile, cât și diferențele de timp se potrivesc.

 // 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; } }

Să luăm i 1 și i 2 ca momente în melodia înregistrată și j 1 și j 2 ca momente în melodia din baza de date. Putem spune că avem două meciuri cu potrivire diferență de timp dacă:

<span style=font-family: TimesNewRoman;> RecordedHash(i 1 ) = SongInDBHash(j 1 ) AND RecordedHash(i 2 ) = SongInDBHash(j 2 ) </span>

<span style=font-family: TimesNewRoman;>ȘI</span>

<span style=font-family: TimesNewRoman;> abs(i 1 - i 2 ) = abs (j 1 - j 2 ) </span>

Acest lucru ne oferă flexibilitate de a înregistra melodia de la început, de la mijloc sau de la sfârșit.

În cele din urmă, este puțin probabil ca fiecare moment al cântecului pe care îl înregistrăm în club să se potrivească cu fiecare moment corespunzător al aceleiași piese din biblioteca noastră, înregistrată în studio. Înregistrarea va include mult zgomot care va introduce unele erori în meciuri. Deci, în loc să încercăm să eliminăm toate melodiile, cu excepția celei corecte, din lista noastră de potriviri, la sfârșit, sortăm toate melodiile potrivite în ordine descrescătoare a probabilității, iar preferata noastră este prima melodie de pe lista de clasament.

De sus până jos

Pentru a răspunde la întrebarea „Cum funcționează Shazam?” iată o prezentare generală a întregului proces de recunoaștere și potrivire a muzicii, de sus în jos:

Pentru acest tip de sistem, baza de date poate deveni destul de mare, așa că este important să folosiți un fel de bază de date scalabilă. Nu este nevoie specială de relații, iar modelul de date ajunge să fie destul de simplu, așa că este un caz bun pentru utilizarea unui fel de bază de date NoSQL.

Cum funcționează Shazam? Acum știi

Acest tip de software de recunoaștere a melodiilor poate fi folosit pentru a găsi asemănările dintre melodii. Acum că înțelegeți cum funcționează Shazam, puteți vedea cum acest lucru poate avea aplicații dincolo de simpla Shazaming acea melodie nostalgică care se redă la radioul taxiului. De exemplu, poate ajuta la identificarea plagiatului în muzică sau pentru a afla cine a fost inspirația inițială pentru unii pionieri ai blues-ului, jazz-ului, rock-ului, pop sau oricărui alt gen. Poate că un experiment bun ar fi să completați baza de date de mostre de melodii cu muzică clasică a lui Bach, Beethoven, Vivaldi, Wagner, Chopin și Mozart și să încercați să găsiți asemănările dintre melodii. Ai crede că până și Bob Dylan, Elvis Presley și Robert Johnson au fost plagiatori!

Dar totuși nu-i putem condamna, pentru că muzica este doar un val pe care îl auzim, îl memorăm și îl repetăm ​​în cap, unde evoluează și se schimbă până când îl înregistrăm în studio și îl transmitem următorului mare geniu muzical.