Hoe Sha­zam mu­ziek her­kent

Hoe Sha­zam num­mers her­kent

C’t Magazine - - Inhoud 11/2018 - Jürgen Schuck

Er klinkt een leuk num­mer uit de luid­spre­kers in het ca­fé, maar nie­mand van je vrien­den kan op de ti­tel ko­men. Aan de ta­fel naast je wordt luid­keels over voet­bal ge­dis­cus­si­eerd, maar het lukt Sha­zam toch om het num­mer te her­ken­nen aan de hand van een kor­te op­na­me die je met je smartpho­ne maakt. Hoe werkt dat?

Au­dio-fin­ger­prin­ting werd voor het eerst in 2003 ge­pre­sen­teerd in een whi­te­pa­per van Ave­ry Li-Chun Wang, een van de op­rich­ters van Sha­zam [1]. Daar­in pre­sen­teert hij een al­go­rit­me voor het iden­ti­fi­ce­ren van mu­ziek­num­mers op ba­sis van kor­te op­na­mes die je met een mo­bie­le te­le­foon maakt. Mo­bie­le te­le­foons uit het jaar 2000 wa­ren daad­wer­ke­lijk niet meer dan dat: je kon ze mee­ne­men en er­mee bel­len, maar de uit­ge­brei­de func­ties van smartpho­nes wa­ren nog ver weg. De kwa­li­teit van de mi­cro­foon, het ver­wer­ken van sig­na­len door het ap­pa­raat en de GSM-sig­naal­kwa­li­teit wa­ren maar en­ke­le van de tech­ni­sche ob­sta­kels die des­tijds nog on­o­ver­win­baar le­ken. Chris Bar­ton, een van de op­rich­ters en voor­ma­lig CEO van Sha­zam, weet daar ver­ma­ke­lijk over te ver­tel­len in een vi­deo (zie de link on­der­aan dit ar­ti­kel). On­danks al­le scep­sis hield Sha­zam stug vast aan het ver­we­zen­lij­ken van zijn vi­sie en nam Li-Chun Wang in dienst. Ook hij acht­te het in eer­ste in­stan­tie nog on­mo­ge­lijk, maar hij ont­wik­kel­de een bij­zon­der slim al­go­rit­me waar­mee hij een jaar la­ter het pro­bleem al had op­ge­lost. In 2001 ver­liep dat nog via een te­le­foon­ge­sprek, te­gen­woor­dig gaat het met een app.

Het prin­ci­pe ach­ter het al­go­rit­me is een­vou­dig: het be­paalt wat de ka­rak­te­ris­tie­ke au­dio-ei­gen­schap­pen van een frag­ment (pro­be) zijn – de vin­ger­af­druk – en zoekt naar over­een­kom­sten in een da­ta­ba­se van au­dio-vin­ger­af­druk­ken van ori­gi­ne­le num­mers. Sha­zam heeft daar­bij niet al­le as­pec­ten van au­dio-fin­ger­prin­ting

zelf uit­ge­von­den, maar heeft wel het pro­bleem wel we­ten op te los­sen om op­na­mes te her­ken­nen waar­in veel ach­ter­grond­ruis zit en die met een be­perk­te ge­ge­vens­over­dracht wor­den ver­zon­den.

Sha­zam heeft de de­tails van zijn al­go­rit­me nooit vol­le­dig open­baar ge­maakt. Aan de hand van het prin­ci­pe heb­ben en­ke­le hob­by­ont­wik­ke­laars ech­ter hun ei­gen va­ri­an­ten van het al­go­rit­me ge­ïm­ple­men­teerd (zie de link aan het eind van dit ar­ti­kel), aan de hand waar­van je goed kunt af­lei­den hoe het ori­gi­neel van Sha­zam zo on­ge­veer moet wer­ken.

Op­spo­ren

Een mu­ziek­num­mer kun je be­schrij­ven als een op­een­vol­ging van to­nen, waar­bij een toon wordt ge­de­fi­ni­eerd door zijn hoog­te (fre­quen­tie) en sterk­te (am­pli­tu­de). Aan de hand daar­van pro­beert Sha­zam de mu­ziek te her­ken­nen. Daar­bij ne­geert het ove­ri­ge toon­pa­ra­me­ters zo­als de duur en klank­kleur. Om de mu­ziek­da­ta­ba­se suc­ces­vol te kun­nen raad­ple­gen, heeft Sha­zam een au­dio-vin­ger­af­druk no­dig die het num­mer een­dui­dig iden­ti­fi­ceert. Dat werkt in prin­ci­pe via een se­rie pa­ren (tu­pels), die be­staan uit de fre­quen­tie (toon­hoog­te) en het ge­luids­vo­lu­me (toon­sterk­te). Op welk mo­ment die te ho­ren zijn (toon­volg­or­de), maakt elk num­mer uniek iden­ti­fi­ceer­baar.

Een au­dio­sig­naal wordt als een se­rie van dui­zen­den sam­ples op een smartpho­ne of pc op­ge­sla­gen. Die vor­men een re­gi­stra­tie van de lucht­druk res­pec­tie­ve­lijk de ma­te van tril­ling van het mi­cro­foon­mem­braan in in­ter­val­len van 0,02 ms. De fre­quen­ties kun je daar ech­ter niet di­rect uit af­le­zen. Voor het be­pa­len van de fre­quen­ties wordt een Fou­rier­trans­for­ma­tie ge­bruikt, die een au­dio­sig­naal af­beeldt als fre­quen­ties en am­pli­tu­des bin­nen een be­paald tijds­be­stek. Voor di­gi­ta­le au­dio­sig­na­len wordt een dis­cre­te Fou­rier­trans­for­ma­tie ge­bruikt, die ef­fi­ci­ënt kan wor­den be­re­kend. Ook bij de snel­le ver­sie, de Fast Fou­rier Trans­form (FFT), is de fre­quen­tie­ana­ly­se nog al­tijd een re­ken­in­ten­sief pro­ces. Het is daar­om zaak om de hoe­veel­heid da­ta die moet wor­den be­re­kend zo be­perkt mo­ge­lijk te hou­den. Bij een di­gi­taal au­dio­sig­naal kan dat on­der meer door ste­reo­ka­na­len naar mo­no te down­mixen (in­dien de smartpho­ne meer dan één ka­naal op­neemt), en door het zo­ge­naam­de 'down­sam­pling', of­te­wel het sa­men­voe­gen van op­een­vol­gen­de sam­ples. Hoe Sha­zam dat exact doet, houdt het be­drijf

ge­heim. In het whi­te­pa­per wordt ge­meld dat met au­dio­be­stan­den wor­den ge­werkt met 8 kHz 16-bit mo­no-sam­ples.

Het re­sul­taat van de Fou­rier­trans­for­ma­tie is een spec­tro­gram van een num­mer met drie­di­men­si­o­na­le in­for­ma­tie over toon­hoog­te, toon­sterk­te en tijd. Dat kan wor­den weer­ge­ge­ven als een twee­di­men­si­o­na­le heat­map, waar­bij tijd de x-as is, toon­hoog­te de y-as en ver­schil­len­de kleu­ren het ge­luids­vo­lu­me re­pre­sen­te­ren. Blau­we pixels zijn de zach­te to­nen en ro­de pixels de har­de.

De hoe­veel­heid da­ta is ech­ter veel te groot om daar­mee een query naar een da­ta­ba­se te stu­ren. Sha­zam fil­tert daar­om al­leen de bij­zon­der lui­de to­nen (peaks) er­uit en let daar­bij al­leen op een zo ge­lijk­ma­tig mo­ge­lij­ke ver­de­ling van die peaks ge­du­ren­de het ver­loop van het mu­ziek­stuk. Sha­zam meldt ver­der niet wel­ke de­fi­ni­tie zij voor lui­de to­nen han­te­ren. De com­mu­ni­ty op in­ter­net is het ech­ter met el­kaar eens dat er re­ke­ning wordt ge­hou­den met de ei­gen­schap­pen van het men­se­lij­ke ge­hoor, waar­bij la­ge to­nen als zach­ter en ho­ge to­nen als lui­der wor­den er­va­ren. De mu­ziek­in­du­strie weet dat ook en ver­sterkt de la­ge to­nen in een mix. Om de meest sig­ni­fi­can­te to­nen te be­pa­len, moet er daar­om een fre­quen­tie­af­han­ke­lijk drem­pel­fil­ter zijn. Dat houdt bo­ven­dien re­ke­ning met de ei­gen­schap van veel mu­ziek­stuk­ken dat die aan het be­gin en aan het eind zach­ter klin­ken dan in het mid­den.

Spo­ren vei­lig­stel­len

Als je de pie­ken in een apart dia­gram zet, lijkt dat een beet­je op een ster­ren­kaart. Daar­om om­schrijft het whi­te­pa­per dat ook wel als 'con­stel­la­ti­on map'. Zo'n con­stel­la­ti­on map re­pre­sen­teert de meest sig­ni­fi­can­te to­nen van een num­mer ge­lijk­ma­tig ver­deeld over tijd. Als je het al­go­rit­me op een kort frag­ment toe­past, be­re­kent hij daar ook een con­stel­la­ti­on map voor.

Des­on­danks is het geen goed idee om voor één pro­be de con­stel­la­ti­on maps van mil­joe­nen num­mers af te zoe­ken op zoek naar een match. Uit­gaan­de van 30 pie­ken per se­con­de zou de zoek­op­dracht van een pro­be van 10 se­con­den in een da­ta­ba­se van 1 mil­joen num­mers van ge­mid­deld 3 mi­nu­ten zo'n 1,5 bil­joen ope­ra­ties ver­gen (30 × 10 × 30 × 10 × 1.000.000 × 3 × 60) – en dat zon­der re­ke­ning te hou­den met mo­ge­lij­ke fou­ten in de pro­be.

Het op­los­sen van het pro­bleem van een ef­fi­ci­ën­te zoek­tocht is fei­te­lijk de clou ach­ter het al­go­rit­me. De ba­sis is het idee om in plaats van naar apar­te pie­ken met­een naar meer­de­re pie­ken in één keer te zoe­ken. Dat doet Sha­zam door een con­stel­la­ti­on map in zo­ge­naam­de 'tar­get zo­nes' in te de­len en voor el­ke zo­ne een piek als an­ker­punt te be­pa­len. Ver­vol­gens com­bi­neert Sha­zam de fre­quen­tie van el­ke piek bin­nen een tar­get zo­ne met de fre­quen­tie van het toe­ge­we­zen an­ker­punt en het tijds­ver­schil tus­sen bei­de pie­ken. Het re­sul­taat is een bi­treeks (has­h­key) die Sha­zam sa­men met de tijd­po­si­tie van het an­ker­punt in een da­ta­ba­se op­slaat. De has­h­keys en tim­e­mar­kers van een con­stel­la­ti­on map vor­men dan sa­men de au­dio­vin­ger­af­druk van het num­mer of van de pro­be.

Doel­zo­nes

Sha­zam be­schrijft he­laas niet vol­gens wel­ke me­tho­de tar­get zo­nes ge­de­fi­ni­eerd wor­den. Na­ge­maak­te im­ple­men­ta­ties op in­ter­net pak­ken bij­voor­beeld om het n-aan­tal pie­ken één piek sa­men met een m-aan­tal pie­ken die op die eer­ste piek vol­gen, en ge­brui­ken daar­voor waar­den van 1 tot 5 voor n en 5 tot 7 voor m.

De has­h­keys be­staan uit 32 bits: 9 bits voor de bei­de pie­ken en 14 bits voor hun tijds­ver­schil. Daar­mee kun je 512 (29) ver­schil­len­de fre­quen­ties on­der­schei­den, die bij een sam­p­le­ra­te van 1 mil­li­se­con­de maxi­maal rond 16 se­con­den (214/1000) af­stand mo­gen heb­ben. Bij mu­ziek­stuk­ken als ASAP van Jo­hn Ca­ge zal dat niet wer­ken, maar voor po­pu­lai­re mu­ziek werkt dat pri­ma.

Een con­stel­la­ti­on map met 30 pie­ken per se­con­de en tar­get zo­nes met 5 pie­ken heeft voor een vin­ger­af­druk van een num­mer van 3 mi­nu­ten een re­sul­taat van 27.000 waar­den (30 × 5 × 3 × 60) bij maxi­ma­le over­lap van de tar­get zo­nes (als je el­ke piek ook nog eens als an­ker­punt kiest). Als je bij­voor­beeld al­leen el­ke der­de piek als an­ker­punt vast­legt, re­du­ceert dat het to­taal tot 9000 waar­den. Als je dat ver­me­nig­vul­digd met een re­a­lis­tisch aan­tal van 50 mil­joen num­mers in een mu­ziek­da­ta­ba­se voor au­dio­vin­ger­af­druk­ken, is het re­sul­taat ook voor die klei­ne­re waar­de nog steeds 450 mil­jard has­h­keys. Daar moe­ten ook nog re­dun­dan­ties tus­sen zit­ten, om­dat je met 32-bit has­h­keys maxi­maal on­ge­veer 4 mil­jard waar­den kunt on­der­schei­den. De­zelf­de has­h­key kan ook daad­wer­ke­lijk in meer­de­re num­mers voor­ko­men. De key wordt in dat ge­val meer­de­re ke­ren in de da­ta­ba­se op­ge­no­men, tel-

kens ge­kop­peld aan een num­mer-ID en de po­si­tie van de has­h­key in het num­mer.

De kop­pe­ling tus­sen tim­e­mar­kers en num­mers wordt ge­maakt in het lij­st­ele­ment als com­bi­na­tie van bei­de waar­den met tel­kens 32 bit, waar­bij de waar­de voor het num­mer een ID is. Door het op die ma­nier te or­ga­ni­se­ren, wordt de vin­ger­af­druk­ta­bel in de mu­ziek­da­ta­ba­se be­grensd tot maxi­maal 232, zo­dat het mo­ge­lijk is die met de has­h­key te in­dexe­ren.

Da­ta­ba­se­ver­ge­lij­king

Het zoe­ken ver­loopt ver­vol­gens in stap­pen. Al­ler­eerst stuurt het al­go­rit­me een query naar de da­ta­ba­se met al­le has­h­keys van de pro­be – in fei­te diens vin­ger­af­druk. Het re­sul­taat voor el­ke has­h­key is een lijst van num­mers en tim­e­mar­kers waar die has­h­key voor­komt. Het al­go­rit­me be­schikt dan over een lijst van al­le num­mers in de da­ta­ba­se die een over­een­komst be­vat­ten.

Of het ge­zoch­te num­mer ook in de da­ta­ba­se staat, hangt er­van af of er een num­mer tus­sen zit met tim­e­mar­kers in de has­h­key die de­zelf­de re­la­tie­ve af­stand heb­ben als die in de pro­be. Een der­ge­lij­ke over­een­stem­ming vind je een­vou­dig in een dia­gram dat de ver­de­ling van de tim­e­mar­kers weer­geeft als een strooi­veld van pun­ten, waar­van de co­ör­di­na­ten zich be­vin­den op de tijds­po­si­ties van zo­wel de pro­be als het mu­ziek­stuk. Een tref­fer her­ken je aan een sig­ni­fi­can­te op­ho­ping van pun­ten in de vorm van een dia­go­naal lo­pen­de lijn.

Voor een ma­the­ma­ti­sche op­los­sing van dat pro­bleem wor­den meest­al re­gres­sie­me­tho­den ge­bruikt. Dit vergt ech­ter in­ten­sie­ve be­re­ke­nin­gen. Sha­zam ge­bruikt daar­om een an­de­re aan­pak: de cor­res­pon­de­ren­de tim­e­mar­kers van de pro­be en het num­mer in het dia­gram kun­nen ge­for­mu­leerd wor­den als tm = tp + Δtp, waar­bij tm de tim­e­mar­ker van het num­mer en tp die van de pro­be is. Daar­bij duidt Δtp het ver­schil aan tus­sen bei­de tim­e­mar­kers. Die kan wor­den be­re­kend met Δtp = tm - tp. Het al­go­rit­me be­re­kent die ver­schil­len voor elk sprei­dings­veld­di­a­gram, dus al­le num­mers van de zoek­re­sul­ta­ten, en maakt daar tel­kens een his­to­gram van. De laat­ste stap on­der­zoekt de his­to­gram­men dan op af­wij­kin­gen. Als één er­van een sta­tis­tisch sig­ni­fi­can­te af­wij­king van het ge­mid­del­de van al­le re­sul­ta­ten heeft, dan is de kans groot dat dit het ge­zoch­te num­mer is. Dat komt door­dat de tijd­ver­schil­len bij het juis­te num­mer veel min­der zul­len ver­schil­len dan bij de an­de­re num­mers, die al­leen door toe­val en­ke­le over­een­kom­sti­ge has­h­keys heb­ben.

Voor de per­for­man­ce van de be­schre­ven pro­ce­du­re zijn twee fac­to­ren be­pa­lend: de hoe­veel­heid be­re­ke­nin­gen die no­dig zijn voor het zoe­ken in de vin­ger­af­druk­ta­bel van de mu­ziek­da­ta­ba­se en de be­re­ke­nin­gen die no­dig zijn voor het ana­ly­se­ren van de lijst met tref­fers. Bij het zoe­ken met de has­h­keys van een pro­be gaat het om een veld­in­dex. De vin­ger­af­druk­ta­bel kan door zijn com­pac­te for­maat voor een groot aan­tal num­mers in het werk­ge­heu­gen zit­ten (in-me­mo­ry). De au­dio­vin­ger­af­druk­ken van 50 mil­joen num­mers met 9000 waar­den per num­mer en 64 bit per waar­de ne­men bij­voor­beeld on­ge­veer 4 TB in be­slag (50.000.000 × 9000 × 64/8). Als het werk over meer­de­re ser­vers wordt ver­deeld, le­vert dat geen pro­ble­men op.

De moei­te die voor het zoe­ken ge­daan moet wor­den, hangt af van de duur van de pro­be. Hoe lan­ger die is, hoe meer bij­be­ho­ren­de has­h­keys er zijn. El­ke has­h­key vergt ech­ter maar één ta­bel­toe­gang. Bij de ana­ly­se is het van be­lang om de hoe­veel­heid da­ta van de kan­di­da­ten zo klein mo­ge­lijk te hou­den. Om­dat de has­h­keys zeer spe­ci­fiek zijn, zal het aan­tal po­ten­ti­ë­le kan­di­da­ten te over­zien zijn.

Het pro­ce­dé van Sha­zam werkt bui­ten­ge­woon goed, zo­als je snel merkt als je de app ge­bruikt. Ook de vrij be­schik­ba­re im­ple­men­ta­ties op in­ter­net (zie de link hier­on­der) la­ten zien hoe ef­fec­tief het prin­ci­pe werkt. Het al­go­rit­me is snel en vindt het num­mer met gro­te be­trouw­baar­heid, mits het in de da­ta­ba­se is op­ge­no­men na­tuur­lijk.

Ten slot­te nog een per­soon­lij­ke anek­do­te: Sha­zam was in staat om bij een op­tre­den de li­ve-ver­sie van een num­mer te iden­ti­fi­ce­ren. De mu­zi­kan­ten kon­den het num­mer dus op de mil­li­se­con­de nauw­keu­rig exact na­spe­len, of het was in fei­te he­le­maal niet li­ve.

Newspapers in Dutch

Newspapers from Netherlands

© PressReader. All rights reserved.