Come funziona Shazam?

Shazam è una delle app per smartphone più note e scaricate, il programma permette di riconoscere una canzone semplicemente accostando il ricevitore del cellulare alla fonte audio. Oltre a riconoscere la canzone (in pochissimi secondi) informa pure la tua “rete di amici” che ha appena riconosciuto una canzone per te.
Come funziona Shazam? Ovviamente è magia, ma qualcuno con un po’ di tempo libero s’è dato da fare e ha scoperto che dietro c’è anche del tecnologico e poi ha scritto una spiegazione abbastanza dettagliata. Il post di questo “curioso ingeniere” (adesso si dice così nedr?) l’ha segnalato Inkiostro qualche giorno fa, io non ho fatto altro che tradurlo. Vista la gran presenza di tecnicismi, i consigli su come rendere al meglio certi termini o alcuni passaggi sono sempre benvenuti.

Ah, visto che sul mio blog non esiste una categoria adatta a questo tipo di post, ne ho creata una nuova dove finiranno i Geek & Nerd stuff, si chiama “nerditude“.

Vi lascio al “curioso ingeniere”, buona lettura!

Il servizio offerto da Shazam è davvero notevole, non solo perchè fa quello che tutti sappiamo, ma perchè lo fa anche in canzoni di audio poco nitido o con rumore di fondo. Io l’ho fatto lavorare in un affollato coffee shop e in una pizzeria e ha funzionato.
Ero curioso di sapere come funzionava, e per fortuna ho trovato un documento scritto da uno degli sviluppatori che lo spiega in modo abbastanza dettagliato. Naturalmente sorvola su alcuni dettagli, ma l’idea di base è esattamente ciò che ci si aspetta: Shazam si basa sulle impronte digitali della musica, lo spettrogramma.

I passaggi fondamentali

1. Shazam crea un catalogo completo di “impronte digitali della musica”, archiviando tutto in un database.
2. Gli utenti “taggano” le canzoni che ascoltano, creando nuove impronte digitali della durata di 10 secondi di audio.
3. Shazam carica l’impronta digitale sul server, che esegue la ricerca di corrispondenza dell’impronta digitale nel database, dove sono riposte le impronte giù note.
4. Se Shazam trova una corrispondenza, le informazioni sulla canzone sono restituite all’utente, altrimenti viene inviato un messaggio di servizio.

Come funziona il rilevamento delle impronte audio

Potete pensare a qualsiasi pezzo di musica come a un grafico tempo-frequenza chiamato spettrogramma. Su un asse di questo grafico c’è il tempo, sull’altro la frequenza, e sul terzo l’intensità. Ogni punto del grafico rappresenta l’intensità di una data frequenza in un punto specifico del tempo. Supponendo che il tempo sia sull’asse x e la frequenza sull’asse y, una linea orizzontale rappresenterebbe tono puro continuo e una linea verticale rappresenterebbe uno scoppio istantaneo di rumore bianco. Ecco un esempio di come potrebbe essere una canzone:


Lo spettrogramma di un campione di canzone con potenze di picco segnate in rosso. Wang, Avery Li-Chun. Un algoritmo di ricerca audio potenza-industriale. Shazam Entertainment, 2003. Fig. 1A,B.

L’algoritmo di Shazam crea le impronte digitali di una canzone generando questo grafico 3d e identificando le frequenze di “intensità di picco.”
Per ciascuno di questi punti di picco è registrata la frequenza e la quantità di tempo a partire dall’inizio del brano. Sulla base degli esempi su carta, credo siano trovati circa 3 di questi punti al secondo. [nda Un utente nei commenti osserva che nella sua implementazione ha avuto bisogno di più di 30 punti/ sec.] Quindi, un esempio di impronta digitale per un campione di 10 secondi potrebbe essere:

Frequency in Hz Time in seconds
823.44 1.054
1892.31 1.321
712.84 1.703
. . . . . .
819.71 9.943

Shazam costruisce il proprio catalogo digitale come una tabella hash, in cui la chiave è la frequenza. Quando Shazam riceve un’impronta digitale come quella sopra, utilizza la prima chiave (in questo caso 823. 44), e ricerca tutti i brani corrispondenti. La tabella hash di Shazam potrebbe essere simile alla seguente:

Frequency in Hz Time in seconds, song information
823.43 53.352, “Song A” by Artist 1
823.44 34.678, “Song B” by Artist 2
823.45 108.65, “Song C’ by Artist 3
. . . . . .
1892.31 34.945, “Song B” by Artist 2

Qualche dettaglio in più

Shazam non si limitaa a segnare un solo punto nello spettrogramma, piuttosto sono segnati un paio di punti: il “picco di intensità” più di un secondo “punto fermo”. Quindi, la chiave non è solo una singola frequenza, è un hash delle frequenze di entrambi i punti. Questo comporta, a meno di collisioni hash, che di volta in volta accelera la ricerca su catalogo per diversi ordini di grandezza, permettendo all’algoritmo di trarre il maggior vantaggio dal tempo di ricerca costante (O(1)) di tabella.


Grafico in alto: Canzoni e frequenze campione hanno molte corrispondenze, ma non si allineano in tempo, quindi non c’è alcuna corrispondenza. Grafico in basso: le frequenza di corrispondenza si verifica nello stesso tempo, così la canzone e il campione sono in corrispondenza. Wang, Avery Li-Chun. Un algoritmo di ricerca audio potenza-industriale. Shazam Entertainment, 2003. Fig. 2B.

Se un brano specifico entra in corrispondenza più volte (sulla base degli esempi su carta penso che ci sia bisogno di circa 1 hit di frequenza al secondo), Shazam controlla per vedere se queste frequenze corrispondono nel tempo. In realtà Shazam ha un modo intelligente di fare questo, crea una seconda trama di hit di frequenza, su un asse c’è il tempo a partire da cui quelle frequenze appaiono nel brano della canzone, sull’altro asse c’è il tempo in cui quelle frequenze appaiono nel campione. Se c’è una relazione temporale tra gli insiemi di punti, allora i punti si allineano lungo una diagonale. Shazam usa un altro metodo di elaborazione del segnale per trovare questa linea e se esiste con una certa sicurezza, allora etichettano il brano come una corrispondenza.

Leave a Reply