Come funziona l’algoritmo di Shazam?

Come funziona l’algoritmo di Shazam?

phone 5513376 640


Che cos’è Shazam?

C’è un bel servizio chiamato Shazam, che prende un breve campione di musica e identifica la canzone.


Shazam Entertainment Ltd. è stata fondata nel 2000 con l’idea di fornire un servizio che possa essere utile per riconoscere un brano riprodotto nell’ambiente circostante utilizzando soltanto il cellulare.
Ci sono un paio di modi per usarlo, ma uno dei più convenienti è installare la loro app gratuita su uno smartphone. Basta premere il pulsante “Tocca per Shazam”, tenere il microfono del telefono vicino a un altoparlante e questo identificherà il brano, fornendo le informazioni su titolo, artista, album, oltre al link per ascoltare il brano sulle principali piattaforme streaming o per acquistarlo.

Ciò che è così straordinario del servizio è che funziona anche su canzoni in sottofondo ad altre voci e anche se durante la registrazione è presente qualche rumore estraneo (l’ho provato anche seduta in un bar affollato e in una pizzeria).
Ero curiosa di come funzionasse e fortunatamente c’è un documento scritto da uno degli sviluppatori che spiega proprio questo. Ovviamente tralasciano alcuni dettagli, ma l’idea di base è esattamente quella che ti aspetteresti: si basa sulla scansione dei brani e sulla creazione di impronte acustiche e di uno spettrogramma (rappresentazione grafica dell’intensità di un suono in funzione del tempo e della frequenza).
Shazam può identificare musica trasmessa da qualsiasi sorgente, come ad esempio la radio, la televisione o il cinema, a condizione che il livello di rumore di fondo non sia molto alto, per evitare che la canzone non venga riconosciuta nel database del software.


Cosa opera Shazam?

I passaggi di base sono questi:
1. In precedenza, Shazam ha scansionato un catalogo completo di musica e ha memorizzato le impronte acustiche di ogni brano in un database. Ad oggi sono oltre 11 milioni di canzoni ed il catalogo viene aggiornato di tanto in tanto in base alle nuove uscite.
2. Un utente vuole avere informazioni su una canzone trasmessa in quel momento. Apre l’app di Shazam e avvia una registrazione di massimo 15 secondi di audio, tenendo il microfono del cellulare quanto più vicino alla sorgente.
3. L’app estrae dal campione un’impronta acustica e la carica automaticamente sui server di Shazam. Questa viene confrontata, creando uno spettrogramma, con tutte le impronte acustiche già presenti nel database. 
4. Se viene trovata una corrispondenza vengono restituite le informazioni sul brano, altrimenti l’utente è invitato ad effettuare di nuovo la ricerca.

Si può pensare a qualsiasi brano musicale come ad un grafico tempo-frequenza, lo spettrogramma. Su un asse c’è il tempo (in secondi), su un altro c’è la frequenza (in hertz) e sul terzo asse c’è l’intensità.
Ogni punto del grafico rappresenta una determinata frequenza con la sua intensità in un preciso momento del brano. E’ come se fosse una vera e propria “impronta digitale acustica”, una sorta di riassunto digitale delle informazioni contenute nel brano stesso.

audio 3540254 640

L’algoritmo Shazam rileva una canzone generando questo spettrogramma e identificando le frequenze di “intensità massima”. Per ciascuno di questi punti di picco tiene traccia della frequenza e della quantità di tempo dall’inizio della traccia.
Ovviamente, alla base della magia di Shazam ci sono archivi di riferimento contenenti milioni di impronte digitali acustiche catalogate nel corso del tempo e in continuo aggiornamento.
Shazam costruisce il proprio catalogo di impronte acustiche come una tabella hash (rappresentazione non ambigua e non falsificabile), dove la chiave è la frequenza.
Nel momento in cui Shazam “ascolta” una decina di secondi del brano in questione, non fa altro che generare lo spettrogramma del campione e inviarlo al server per la comparazione.


Come avviene la comparazione vera e propria?

Un software non può effettuare una comparazione “ad occhio”, ma deve per forza di cose ridurre le informazioni in un formato snello, in grado di essere analizzato per fornire risultati in pochi secondi.
Shazam quindi cerca di semplificare e di creare dei riferimenti nello spettrogramma stesso, in modo da utilizzarli per il confronto con il database.
A questo punto il grafico viene privato delle parti non necessarie e vengono tenute soltanto quelle utili alla comparazione, cioè i punti dello spettrogramma dove l’intensità delle frequenze è più alta.
Questa sorta di “mappa” ottenuta dalla semplificazione dell’impronta acustica digitale viene adesso “targetizzata”, cioè vengono fissati dei punti di riferimento sui quali applicare il vero e proprio algoritmo.
In poche parole il software sceglie un gruppo di punti nella cosiddetta “target-zone” e un punto d’ancoraggio vicino ad essi, per stabilire delle corrispondenze univoche.
Senza entrare nel dettaglio, l’algoritmo mette in relazione i valori di ogni punto della target-zone con quelli del punto di ancoraggio creando un risultato che può essere istantaneamente (e in maniera molto più veloce) comparato con quelli presenti sui databases, finchè non vengono trovati uno o più risultati presunti.
Se siamo di fronte a due brani uguali, il software esegue un’ulteriore analisi comparando i picchi di volume tra i due riferimenti. Se in un qualsiasi punto del tempo otterremo una sovrapposizione e quindi un valore estremamente alto, il software riconoscerà come uguali i due brani.

Falsi positivi

L’algoritmo è stato progettato per riconoscere file audio già presenti nel database.
Visto che potrebbe essere presente un moltitudine di diverse esecuzioni della stessa canzone, l’algoritmo campiona e restituisce il brano corrispondente corretto (anche se all’orecchio umano sembrano tutti praticamente indistinguibili).
Occasionalmente possono anche esserci segnalazioni di falsi positivi. In questi casi l’algoritmo non è applicato in modo scorretto ma, restituendo un falso positivo, evidenzia la presenza di caratteristiche molto simili con il brano ascoltato (o un eventuale plagio) oppure indica che la registrazione è avvenuta in modo scorretto (troppo lontano dalla sorgente o è troppo rumorosa/disturbata).


La matematica in Shazam

Il suono è dato dalla vibrazione di un corpo in vibrazione. Tale vibrazione, che si propaga nell’aria o in un altro mezzo elastico, raggiunge l’apparato uditivo dell’orecchio che, tramite un complesso meccanismo interno, crea una sensazione “uditiva” correlata alla natura della vibrazione; in particolar modo la membrana timpanica subendo variazioni di pressione entra in vibrazione.
Il suono è quindi una variazione di pressione dell’aria, che è quindi descrivibile da una funzione continua. I microfoni sono capaci di tramutare la variazione di pressione in un un segnale elettrico, anche questo continuo. Questo segnale continuo non è per nulla utile nel mondo digitale, dove è possibile trattare solo quantità discrete, descrivibili attraverso numeri discreti (solo 0 e 1). Quindi un segnale continuo deve essere approssimato con un segnale discreto attraverso un campionamento. In linguaggio matematico, potremmo dire di approssimare la funzione continua con una funzione semplice. Una domanda centrale in questa fase è la seguente: con che periodo/frequenza eseguire il campionamento? Se la frequenza è troppo bassa, l’errore di approssimazione potrebbe risultare troppo elevato. Una frequenza troppo alta porterebbe a trattare una grande quantità di dati, rallentando tutto il processo. Il Teorema del campionamento di Nyquist- Shannon stabilisce la minima frequenza necessaria per campionare un segnale analogico senza perdere informazioni. In particolare, per catturare tutte le frequenze che un orecchio umano può percepire, il campionamento deve essere eseguito ad una frequenza che sia il doppio della frequenza udibile dall’orecchio umano. Poiché l’orecchio umano può percepire frequenze che vanno da 20Hz a 20.000Hz, le conversioni audio sono fatte solitamente utilizzando una frequenza di campionamento di 44.100Hz (Compact Disc, MP3). Abbiamo quindi ora un segnale digitale che rappresenta la variazione di ampiezza del segnale nel tempo. Poiché il suono prodotto da strumenti musicali è altamente periodico, è possibile pensare a piccole parti del segnale raccolto come funzioni periodiche. Grazie alla teoria di Fourier, sappiamo che tale segnale può essere scomposto nella somma di seni e coseni di determinate frequenze, e sappiamo anche calcolare facilmente i relativi coefficienti. Ad ogni frequenza sarà quindi associato un coefficiente (o ampiezza), ed è possibile vedere quindi la funzione nel dominio delle frequenze. L’ informazione può essere immagazzinata in un vettore. In realtà, poiché si sta lavorando ora su un segnale discreto, si utilizza la trasformata discreta di Fourier (DFT). Si tratta di una trasformata che converte una collezione finita di campioni equispaziati di una funzione in una collezione di coefficienti di una combinazione lineare di sinusoidi complesse, ordinate al crescere della frequenza. Analogamente alla trasformata di Fourier, si tratta di un modo per rappresentare una funzione (la cui variabile è spesso il tempo) nel dominio delle frequenze. Le frequenze delle sinusoidi della combinazione lineare (periodica) prodotta dalla trasformata sono multipli interi di una frequenza fondamentale, il cui periodo è la lunghezza dell’intervallo di campionamento.
Un’effetto collaterale della DFT è la perdita di un’enorme quantità di informazione riguardante il tempo. Infatti, se si facesse la DFT sull’intero brano raccolto, si perderebbe l’informazione di quando una determinata frequenza è apparsa. Per risolvere questo problema, si esegue la DFT su tante piccole finestre temporali, così da avere su ciascuna di esse il vettore contenente le ampiezze delle rispettive ampiezze. Il brano raccolto sarà quindi immagazzinato nel dominio delle frequenze sotto forma di matrice. Solitamente, una buona partizione per l’analisi del brano prevede finestre temporali di un secondo.
Tramite i metodi informatici accennati sopra si può confrontare la matrice che abbiamo trovato con le tantissime matrici raccolte nel corso del tempo, per capire a quale corrisponde il nostro brano.

Bibliografia utile:


https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf
https://laplacian.wordpress.com/2009/01/10/how-shazam-works/
https://www.toptal.com/algorithms/shazam- it- music- processing- fingerprinting- and- recognition
http://scipy.github.io/devdocs/generated/scipy.signal.stft.html

Il post è finito. Per scrivermi, visita la sezione "contatti". Ti è piaciuta questa pagina? Condividila in due click!

Torna su