Come funziona Shazam? Algoritmi di riconoscimento musicale, impronta digitale ed elaborazione

Si sente una canzone familiare nel club o al ristorante. Hai ascoltato questa canzone migliaia di volte fa, e il sentimentalismo della canzone ti tocca davvero il cuore. Vuoi disperatamente assaporarlo domani, ma non ricordi il suo nome! Fortunatamente, nel nostro fantastico mondo futuristico, hai un telefono con un software di riconoscimento musicale installato e sei salvato. Puoi rilassarti, perché il software ti ha detto il nome della canzone, e sai che puoi ascoltarla ancora e ancora finché non diventa parte di te... o te ne stanchi.

Le tecnologie mobili, insieme agli enormi progressi nell'elaborazione del segnale audio, hanno dato a noi sviluppatori di algoritmi la possibilità di creare riconoscitori di musica. Una delle app di riconoscimento musicale più popolari è Shazam. Se catturi 20 secondi di una canzone, non importa se è intro, strofa o ritornello, creerà un'impronta digitale per il campione registrato, consulterà il database e utilizzerà il suo algoritmo di riconoscimento musicale per dirti esattamente quale canzone stai ascoltando .

Ma come funziona Shazam? L'algoritmo di Shazam è stato rivelato al mondo dal suo inventore Avery Li-Chung Wang nel 2003. In questo articolo esamineremo i fondamenti dell'algoritmo di riconoscimento musicale di Shazam.

Da analogico a digitale - Campionamento di un segnale

Che cos'è davvero il suono? È una sorta di materiale mistico che non possiamo toccare ma che ci vola nelle orecchie e ci fa sentire le cose?

Naturalmente, questo non è proprio il caso. Sappiamo che in realtà il suono è una vibrazione che si propaga come un'onda meccanica di pressione e spostamento, attraverso un mezzo come l'aria o l'acqua. Quando quella vibrazione arriva alle nostre orecchie, in particolare al timpano, muove le piccole ossa che trasmettono la vibrazione ulteriormente alle piccole cellule ciliate in profondità nel nostro orecchio interno. Infine, le piccole cellule ciliate producono impulsi elettrici, che vengono trasmessi al nostro cervello attraverso il nervo uditivo dell'orecchio.

I dispositivi di registrazione imitano questo processo abbastanza da vicino, utilizzando la pressione dell'onda sonora per convertirla in un segnale elettrico. Un'onda sonora reale nell'aria è un segnale di pressione continua. In un microfono, il primo componente elettrico che incontra questo segnale lo traduce in un segnale di tensione analogico, ancora una volta, continuo. Questo segnale continuo non è così utile nel mondo digitale, quindi prima che possa essere elaborato, deve essere tradotto in un segnale discreto che può essere memorizzato digitalmente. Questo viene fatto catturando un valore digitale che rappresenta l'ampiezza del segnale.

La conversione comporta la quantizzazione dell'input e introduce necessariamente una piccola quantità di errore. Pertanto, invece di una singola conversione, un convertitore analogico-digitale esegue molte conversioni su porzioni molto piccole del segnale, un processo noto come campionamento

Il teorema di Nyquist-Shannon ci dice quale frequenza di campionamento è necessaria per catturare una certa frequenza in un segnale continuo. In particolare, per catturare tutte le frequenze che un essere umano può sentire in un segnale audio, dobbiamo campionare il segnale a una frequenza doppia rispetto alla gamma uditiva umana. L'orecchio umano è in grado di rilevare frequenze all'incirca comprese tra 20 Hz e 20.000 Hz. Di conseguenza, l'audio viene spesso registrato con una frequenza di campionamento di 44.100 Hz. Questa è la frequenza di campionamento dei Compact Disc ed è anche la frequenza più comunemente utilizzata con l'audio MPEG-1 (VCD, SVCD, MP3). (Questa velocità specifica è stata originariamente scelta da Sony perché poteva essere registrata su apparecchiature video modificate in esecuzione a 25 fotogrammi al secondo (PAL) o 30 fotogrammi al secondo (utilizzando un videoregistratore monocromatico NTSC) e coprire la larghezza di banda di 20.000 Hz ritenuta necessaria per corrisponda alle apparecchiature di registrazione analogiche professionali dell'epoca.) Quindi, quando scegli la frequenza del campione che è necessario registrare, probabilmente vorrai andare con 44.100 Hz.

Registrazione - Catturare il suono

La registrazione di un segnale audio campionato è facile. Poiché le moderne schede audio sono già dotate di convertitori analogico-digitali, basta scegliere un linguaggio di programmazione, trovare una libreria appropriata, impostare la frequenza del campione, il numero di canali (tipicamente mono o stereo), la dimensione del campione (es. campioni a 16 bit ). Quindi apri la linea dalla tua scheda audio proprio come qualsiasi flusso di input e scrivi in ​​un array di byte. Ecco come è possibile farlo in 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();

Basta leggere i dati da TargetDataLine . (In questo esempio, il flag running è una variabile globale che viene interrotta da un altro thread, ad esempio se abbiamo la GUI con il pulsante 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); }

Dominio del tempo e dominio della frequenza

Quello che abbiamo in questo array di byte è il segnale registrato nel dominio del tempo. Il segnale nel dominio del tempo rappresenta la variazione di ampiezza del segnale nel tempo.

Nei primi anni del 1800, Jean-Baptiste Joseph Fourier fece la straordinaria scoperta che qualsiasi segnale nel dominio del tempo è equivalente alla somma di un certo numero (possibilmente infinito) di semplici segnali sinusoidali, dato che ogni componente sinusoide ha una certa frequenza, ampiezza, e fase. La serie di sinusoidi che insieme formano il segnale originale nel dominio del tempo è nota come serie di Fourier.

In altre parole, è possibile rappresentare qualsiasi segnale nel dominio del tempo semplicemente fornendo l'insieme di frequenze, ampiezze e fasi corrispondenti a ciascuna sinusoide che compone il segnale. Questa rappresentazione del segnale è nota come dominio della frequenza. In qualche modo, il dominio della frequenza agisce come un tipo di impronta digitale o firma per il segnale nel dominio del tempo, fornendo una rappresentazione statica di un segnale dinamico.

L'animazione seguente mostra la serie di Fourier di un'onda quadra da 1 Hz e come un'onda quadra (approssimativa) può essere generata da componenti sinusoidali. Il segnale è mostrato nel dominio del tempo sopra e nel dominio della frequenza sotto.

L'analisi di un segnale nel dominio della frequenza semplifica immensamente molte cose. È più conveniente nel mondo dell'elaborazione del segnale digitale perché l'ingegnere può studiare lo spettro (la rappresentazione del segnale nel dominio della frequenza) e determinare quali frequenze sono presenti e quali mancano. Dopodiché, è possibile filtrare, aumentare o diminuire alcune frequenze o semplicemente riconoscere il tono esatto dalle frequenze date.

La Trasformata Discreta di Fourier

Quindi dobbiamo trovare un modo per convertire il nostro segnale dal dominio del tempo al dominio della frequenza. Qui chiediamo aiuto alla Trasformata di Fourier Discreta (DFT). Il DFT è una metodologia matematica per eseguire l'analisi di Fourier su un segnale discreto (campionato). Converte un elenco finito di campioni equidistanti di una funzione nell'elenco dei coefficienti di una combinazione finita di sinusoidi complesse, ordinati in base alle loro frequenze, considerando se quei sinusoidi fossero stati campionati alla stessa velocità.

Uno degli algoritmi numerici più diffusi per il calcolo della DFT è la trasformata Fast Fourier (FFT). La variazione di gran lunga più comunemente usata di FFT è l'algoritmo Cooley-Tukey. Questo è un algoritmo divide et impera che divide ricorsivamente un DFT in molti DFT più piccoli. Mentre la valutazione di una DFT richiede direttamente O( n 2 ) operazioni, con una FFT di Cooley-Tukey lo stesso risultato viene calcolato in O( n log n ) operazioni.

Non è difficile trovare una libreria appropriata per FFT. Eccone alcuni:

• C – FFTW
• C++ – EigenFFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (interfaccia a FFTW)

Di seguito è riportato un esempio di una funzione FFT scritta in Java. (FFT accetta numeri complessi come input. Per comprendere la relazione tra numeri complessi e funzioni trigonometriche, leggi la formula di Eulero.)

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

Ed ecco un esempio di segnale prima e dopo l'analisi FFT:

Riconoscimento musicale: impronte digitali di una canzone

Uno sfortunato effetto collaterale di FFT è che perdiamo una grande quantità di informazioni sui tempi. (Anche se in teoria questo può essere evitato, le spese generali della performance sono enormi.) Per una canzone di tre minuti, vediamo tutte le frequenze e le loro grandezze, ma non abbiamo la più pallida idea di quando sono apparse nella canzone. Ma questa è l'informazione chiave che rende la canzone quello che è! In qualche modo abbiamo bisogno di sapere in quale momento è apparsa ciascuna frequenza.

Ecco perché introduciamo una sorta di finestra scorrevole, o blocco di dati, e trasformiamo solo questa parte delle informazioni. La dimensione di ogni pezzo può essere determinata in diversi modi. Ad esempio, se registriamo il suono, in stereo, con campioni a 16 bit, a 44.100 Hz, un secondo di tale suono sarà 44.100 campioni * 2 byte * 2 canali ≈ 176 kB. Se scegliamo 4 kB per la dimensione di un pezzo, avremo 44 blocchi di dati da analizzare in ogni secondo della canzone. Questa è una densità sufficientemente buona per l'analisi dettagliata necessaria per l'identificazione audio.

Ora torniamo alla programmazione:

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

Nel ciclo interno stiamo inserendo i dati nel dominio del tempo (i campioni) in un numero complesso con la parte immaginaria 0. Nel ciclo esterno, ripetiamo tutti i blocchi ed eseguiamo l'analisi FFT su ciascuno.

Una volta che abbiamo informazioni sulla composizione della frequenza del segnale, possiamo iniziare a formare la nostra impronta digitale della canzone. Questa è la parte più importante dell'intero processo di riconoscimento audio di Shazam. La sfida principale qui è come distinguere, nell'oceano di frequenze catturate, quali frequenze sono le più importanti. Intuitivamente, cerchiamo le frequenze con la magnitudine più alta (comunemente chiamate picchi).

Tuttavia, in una canzone la gamma delle frequenze forti potrebbe variare tra C basso - C1 (32,70 Hz) e C alto - C8 (4.186,01 Hz). Questo è un intervallo enorme da coprire. Quindi, invece di analizzare l'intera gamma di frequenze in una volta, possiamo scegliere diversi intervalli più piccoli, scelti in base alle frequenze comuni di importanti componenti musicali, e analizzarli separatamente. Ad esempio, potremmo usare gli intervalli che questo tizio ha scelto per la sua implementazione dell'algoritmo Shazam. Questi sono 30 Hz - 40 Hz, 40 Hz - 80 Hz e 80 Hz - 120 Hz per i toni bassi (che coprono il basso, ad esempio) e 120 Hz - 180 Hz e 180 Hz - 300 Hz per i toni medi e alti (copertura vocale e la maggior parte degli altri strumenti).

Ora all'interno di ogni intervallo, possiamo semplicemente identificare la frequenza con la magnitudine più alta. Questa informazione costituisce una firma per questo pezzo della canzone e questa firma diventa parte dell'impronta digitale della canzone nel suo insieme.

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

Si noti che dobbiamo presumere che la registrazione non sia stata eseguita in condizioni perfette (cioè una "stanza per non udenti") e, di conseguenza, dobbiamo includere un fattore fuzz. L'analisi del fattore fuzz dovrebbe essere presa sul serio e, in un sistema reale, il programma dovrebbe avere un'opzione per impostare questo parametro in base alle condizioni della registrazione.

Per facilitare la ricerca dell'audio, questa firma diventa la chiave in una tabella hash. Il valore corrispondente è il tempo in cui questo insieme di frequenze è apparso nel brano, insieme all'ID del brano (titolo del brano e artista). Ecco un esempio di come questi record potrebbero apparire nel database.

Se eseguiamo un'intera libreria di brani attraverso questo processo di identificazione della musica, possiamo creare un database con un'impronta digitale completa di ogni brano nella libreria.

L'algoritmo musicale: identificazione della canzone

Per identificare un brano attualmente in riproduzione nel club, registriamo il brano con il nostro telefono ed eseguiamo la registrazione attraverso lo stesso processo di fingerprinting audio di cui sopra. Quindi possiamo iniziare a cercare nel database gli hash tag corrispondenti.

A quanto pare, molti degli hash tag corrisponderanno all'identificatore musicale di più brani. Ad esempio, può darsi che un brano della canzone A suoni esattamente come un brano della canzone E. Ovviamente, questo non è sorprendente: i musicisti hanno sempre "preso in prestito" lick e riff l'uno dall'altro e in questi giorni i produttori campionano altre canzoni tutte il tempo. Ogni volta che abbiniamo un hash tag, il numero di possibili corrispondenze diminuisce, ma è probabile che queste informazioni da sole non riducano la corrispondenza a un singolo brano. Quindi c'è un'altra cosa che dobbiamo controllare con il nostro algoritmo di riconoscimento musicale, ed è il tempismo.

Il campione che abbiamo registrato nel club potrebbe provenire da qualsiasi punto della canzone, quindi non possiamo semplicemente abbinare il timestamp dell'hash abbinato con il timestamp del nostro campione. Tuttavia, con più hash abbinati, possiamo analizzare i tempi relativi delle partite, e quindi aumentare la nostra certezza.

Ad esempio, se guardi nella tabella sopra, vedrai che l'hashtag 30 51 99 121 195 corrisponde sia al brano A che al brano E. Se, un secondo dopo, abbiniamo l'hash 34 57 95 111 200 , quello è un altro corrisponde alla canzone A ma in questo caso sappiamo che sia gli hash che le differenze di tempo corrispondono.

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

Prendiamo i 1 e i 2 come momenti nella canzone registrata e j 1 e j 2 come momenti nella canzone dal database. Possiamo dire che abbiamo due partite con differenza di tempo se:

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

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

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

Questo ci dà la flessibilità di registrare il brano dall'inizio, dal centro o dalla fine.

Infine, è improbabile che ogni singolo momento della canzone che registriamo nel club corrisponda a ogni momento corrispondente della stessa canzone nella nostra libreria, registrata in studio. La registrazione includerà molto rumore che introdurrà qualche errore nelle partite. Quindi, invece di cercare di eliminare tutto tranne il brano corretto dal nostro elenco di corrispondenze, alla fine, ordiniamo tutti i brani abbinati in ordine decrescente di probabilità e il nostro preferito è il primo brano della classifica.

Da cima a fondo

Per rispondere alla domanda "Come funziona Shazam?" ecco una panoramica dell'intero processo di riconoscimento e abbinamento della musica, dall'alto verso il basso:

Per questo tipo di sistema, il database può diventare piuttosto grande, quindi è importante utilizzare una sorta di database scalabile. Non c'è bisogno di relazioni speciali e il modello di dati finisce per essere piuttosto semplice, quindi è un buon caso per usare una sorta di database NoSQL.

Come funziona Shazam? Ora sapete

Questo tipo di software di riconoscimento dei brani può essere utilizzato per trovare le somiglianze tra i brani. Ora che capisci come funziona Shazam, puoi vedere come questo può avere applicazioni oltre al semplice Shazam di quella canzone nostalgica che suona alla radio dei taxi. Ad esempio, può aiutare a identificare il plagio nella musica o a scoprire chi è stato l'ispirazione iniziale di alcuni pionieri del blues, del jazz, del rock, del pop o di qualsiasi altro genere. Forse un buon esperimento sarebbe riempire il database dei campioni di canzoni con la musica classica di Bach, Beethoven, Vivaldi, Wagner, Chopin e Mozart e provare a trovare le somiglianze tra le canzoni. Penseresti che anche Bob Dylan, Elvis Presley e Robert Johnson fossero plagiatori!

Ma ancora non possiamo condannarli, perché la musica è solo un'onda che sentiamo, memorizziamo e ripetiamo nella nostra testa, dove si evolve e cambia fino a quando non la registriamo in studio e la trasmettiamo al prossimo grande genio musicale.