Hogyan működik Shazam? Zenefelismerési algoritmusok, ujjlenyomatok és feldolgozás

A klubban vagy az étteremben ismerős dalt hall. Ezerszer hallgattad már régen ezt a dalt, és a dal érzelmessége valóban megérinti a szívedet. Kétségbeesetten szeretnél holnap elszívni, de nem emlékszel a nevére! Szerencsére elképesztő futurisztikus világunkban telepítve van egy telefonja zenefelismerő szoftverrel, és megmenekül. Lazíthat, mert a szoftver megmondta a dal nevét, és tudja, hogy újra és újra hallhatja, amíg részévé nem válik ... vagy megbetegedik tőle.

A mobil technológiák az audiojelek feldolgozásában elért hatalmas fejlődéssel együtt lehetővé tették számunkra az algoritmus-fejlesztők számára a zenefelismerők létrehozását. Az egyik legnépszerűbb zenefelismerő alkalmazás a Shazam. Ha 20 másodpercet rögzít egy dalból, függetlenül attól, hogy intro, vers vagy kórus, akkor létrehoz egy ujjlenyomatot a felvett mintához, megkeresi az adatbázist, és annak zenefelismerési algoritmusával pontosan megmondja, hogy melyik zeneszámot hallgatja.

De hogyan működik Shazam? A Shazam algoritmusát feltalálója, Avery Li-Chung Wang tárta fel a világ előtt 2003-ban. Ebben a cikkben áttekintjük Shazam zenefelismerési algoritmusának alapjait.

Analóg-digitális - jel mintavétele

Mi a hang valójában? Ez valamiféle misztikus anyag, amelyhez nem nyúlhatunk, de amely a fülünkbe repül, és hallásra késztet minket?

Természetesen ez nem egészen így van. Tudjuk, hogy a valóságban a hang olyan rezgés, amely mechanikus nyomás- és elmozdulási hullámként terjed, olyan közegen keresztül, mint a levegő vagy a víz. Amikor ez a rezgés a fülünkbe, különösen a dobhártyájába jut, apró csontokat mozgat, amelyek tovább továbbítják a rezgést a belső fülünk mélyén lévő kis szőrsejtekhez. Végül a kis szőrsejtek elektromos impulzusokat produkálnak, amelyeket a halló fülideg közvetít az agyunkba.

A rögzítő eszközök meglehetősen szorosan utánozzák ezt a folyamatot, a hanghullám nyomását felhasználva átalakítják azt elektromos jellé. A levegőben lévő tényleges hanghullám folyamatos nyomásjel. A mikrofonban az első elektromos alkatrész, amely találkozik ezzel a jellel, analóg feszültségjellé alakítja - ismételten folyamatos. Ez a folyamatos jel nem annyira hasznos a digitális világban, ezért feldolgozása előtt diszkrét, digitálisan tárolható jellé kell lefordítani. Ez egy digitális érték rögzítésével történik, amely a jel amplitúdóját képviseli.

Az átalakítás magában foglalja a bemenet kvantálását, és ez szükségszerűen kis hibát eredményez. Ezért egyetlen átalakítás helyett az analóg-digitális átalakító sok konverziót hajt végre a jel nagyon apró darabjain - ezt a mintavételnek nevezett folyamatot

A Nyquist-Shannon tétel megmondja, hogy milyen mintavételi frekvencia szükséges egy bizonyos frekvencia folyamatos jelben való rögzítéséhez. Különösen ahhoz, hogy rögzítsük az ember által hallható összes frekvenciát egy audiojelben, a jelet az emberi hallási tartomány kétszeresénél nagyobb frekvencián kell mintavennünk. Az emberi fül nagyjából 20 Hz és 20 000 Hz közötti frekvenciákat képes felismerni. Ennek eredményeként a hangot leggyakrabban 44 100 Hz mintavételi frekvenciával rögzítik. Ez a kompakt lemezek mintavételi aránya, és egyben az MPEG-1 audió (VCD, SVCD, MP3) leggyakrabban használt sebessége. (Ezt a fajlagos sebességet eredetileg a Sony választotta, mert módosított videokészülékre rögzíthető, amely akár 25 képkocka/másodperces (PAL) vagy 30 képkocka/másodperces sebességgel működik (NTSC monokróm videofelvevő segítségével), és lefedheti a 20 000 Hz-es sávszélességet, amely szükségesnek tűnik ahhoz, hogy egyezik a korabeli professzionális analóg felvevő berendezéssel.) Tehát, ha a felvételhez szükséges minta frekvenciáját választja, akkor valószínűleg 44,100 Hz-rel szeretne.

Felvétel - A hang rögzítése

A mintavételezett hangjel felvétele egyszerű. Mivel a modern hangkártyák már rendelkeznek analóg-digitális átalakítóval, csak válasszon egy programozási nyelvet, keressen megfelelő könyvtárat, állítsa be a minta frekvenciáját, a csatornák számát (általában mono vagy sztereó), a minta méretét (pl. 16 bites minták) ). Ezután nyissa meg a vonalat a hangkártyájáról, mint minden bemeneti adatfolyam, és írjon egy bájt tömbbe. Így lehet ezt megtenni Java-ban:

Csak olvassa el a TargetDataLine adatait. (Ebben a példában a futó zászló egy globális változó, amelyet egy másik szál állít meg - például, ha GUI-val rendelkezünk a STOP gombbal.)

Időtartomány és Frekvencia tartomány

Ami ebben a bájt tömbben van, az az időtartományban rögzített jel. Az időtartományi jel a jel időbeli amplitúdó-változását jelenti.

Az 1800-as évek elején Jean-Baptiste Joseph Fourier figyelemre méltó felfedezést tett, miszerint az időtartomány bármelyik jele egyenértékű néhány (esetleg végtelen) számú egyszerű szinuszos jel összegével, tekintve, hogy az egyes szinuszos komponenseknek van egy bizonyos frekvenciája, amplitúdója, és fázis. Az sinusoidok sorozata, amely együttesen alkotja az eredeti időtartományi jelet, Fourier-sorozatának ismeretes.

Más szavakkal, bármely idõtartományi jelet lehet képviselni úgy, hogy egyszerûen megadjuk a jelet alkotó minden egyes szinuszosnak megfelelõ frekvencia-, amplitúdó- és fázishalmazot. A jel ezen ábrázolása frekvenciatartományként ismert. Bizonyos szempontból a frekvenciatartomány ujjlenyomatként vagy aláírásként működik az időtartományi jelhez, statikusan ábrázolva a dinamikus jelet.

A következő animáció bemutatja az 1 Hz-es négyzethullám Fourier-sorozatát, és azt, hogy miként hozható létre (hozzávetőleges) négyzethullám szinuszos komponensekből. A jel a fenti időtartományban, a frekvenciatartomány pedig az alábbiakban látható.

Egy jel elemzése a frekvenciatartományban sok mindent rendkívül egyszerűsít. Kényelmesebb a digitális jelfeldolgozás világában, mert a mérnök tanulmányozhatja a spektrumot (a jel reprezentációját a frekvenciatartományban), és meghatározhatja, hogy mely frekvenciák vannak jelen és melyek hiányoznak. Ezt követően szűrhet, növelhet vagy csökkenthet néhány frekvenciát, vagy csak felismerheti a pontos hangot az adott frekvenciákból.

A diszkrét Fourier-transzformáció

Tehát meg kell találnunk a módját annak, hogyan alakíthatjuk át jelünket az időtartományból a frekvenciatartományba. Itt segítségül hívjuk a Diszkrét Fourier-transzformációt (DFT). A DFT egy matematikai módszertan a Fourier-analízis diszkrét (mintavételezett) jelen történő elvégzésére. A függvény egyenlő távolságra lévő mintáinak véges listáját konvertálja a komplex szinuszosok véges kombinációjának együtthatóinak listájába, frekvenciájuk szerint rendezve, figyelembe véve, hogy ezekből a szinuszokból ugyanolyan sebességgel vettek-e mintát.

A DFT kiszámításának egyik legnépszerűbb numerikus algoritmusa a Fast Fourier transzformáció (FFT). Az FFT messze leggyakrabban használt variációja a Cooley – Tukey algoritmus. Ez egy megosztani és meghódítani algoritmus, amely rekurzívan osztja fel a DFT-t sok kisebb DFT-re. Míg a DFT értékelése közvetlenül megköveteli O (n 2) műveletek, egy Cooley-Tukey FFT-vel ugyanez az eredmény kiszámításra kerül O (n log n) tevékenységek.

Nem nehéz megfelelő könyvtárat találni az FFT számára. Íme néhány közülük:

C - FFTW
C++ - EigenFFT
Jáva - JTransform
Piton - NumPy
Rubin - Ruby-FFTW3 (interfész az FFTW-hez)

Az alábbiakban bemutatunk egy példát egy Java-ban írt FFT-függvényre. (Az FFT a komplex számokat veszi inputként. A komplex számok és a trigonometrikus függvények kapcsolatának megértéséhez olvassa el Euler képletét.)

És itt van egy példa az FFT elemzés előtti és utáni jelre:

Zenefelismerés: Egy dal ujjlenyomatának elkészítése

Az FFT egyik sajnálatos mellékhatása, hogy nagyon sok információt veszítünk az időzítésről. (Bár elméletileg ez elkerülhető, az előadási rezsi óriási.) Egy háromperces dal esetében látjuk az összes frekvenciát és nagyságukat, de fogalmunk sincs, mikor jelentek meg a dalban. De ez a legfontosabb információ teszi a dalt olyanná, amilyen! Valahogy tudnunk kell, hogy az egyes frekvenciák mely időpontban jelentek meg.

Ezért vezetünk be egyfajta csúszó ablakot vagy adatcsomagot, és az információnak csak ezt a részét alakítjuk át. Az egyes darabok méretét többféle módon lehet meghatározni. Például, ha sztereóban rögzítjük a hangot 16 bites mintákkal, 44,100 Hz frekvencián, akkor egy ilyen hang 44,100 minta * 2 bájt * 2 csatorna ≈ 176 kB. Ha 4 kB-t választunk egy darab méretéhez, akkor 44 darab adatelemzésre lesz szükségünk a dal minden másodpercében. Ez elég jó sűrűség a hangazonosításhoz szükséges részletes elemzéshez.

Most térjünk vissza a programozáshoz:

A belső hurokban az időtartomány adatait (a mintákat) egy komplex számba tesszük, a képzeletbeli 0 résszel. A külső ciklusban végigvezetjük az összes darabot, és mindegyiken elvégezzük az FFT elemzést.

Miután rendelkezünk információval a jel frekvencia-felépítéséről, elkezdhetjük a dal digitális ujjlenyomatának kialakítását. Ez a Shazam teljes hangfelismerési folyamatának legfontosabb része. A fő kihívás itt az, hogyan lehet megkülönböztetni a rögzített frekvenciák óceánjában, hogy mely frekvenciák a legfontosabbak. Intuitív módon a legnagyobb magnitúdójú frekvenciákat (általában csúcsoknak nevezzük) keressük.

Azonban egy dalban az erős frekvenciák tartománya változhat alacsony C - C1 (32,70 Hz) és magas C - C8 (4 186,01 Hz) között. Ez egy hatalmas intervallum. Tehát ahelyett, hogy egyszerre elemeznénk a teljes frekvenciatartományt, választhatunk több kisebb intervallumot, amelyeket a fontos zenei komponensek közös frekvenciái alapján választunk ki, és mindegyiket külön elemezzük. Például használhatjuk azokat az intervallumokat, amelyeket ez a srác választott a Shazam algoritmus megvalósításához. Ezek 30 Hz - 40 Hz, 40 Hz - 80 Hz és 80 Hz - 120 Hz az alacsony hangok esetében (például a basszusgitárra vonatkoznak), és 120 Hz - 180 Hz és 180 Hz - 300 Hz a középső és a magasabb hangokra (amely magában foglalja az éneket és a legtöbb egyéb hangszert).

Most minden intervallumon belül egyszerűen azonosíthatjuk a legnagyobb nagyságú frekvenciát. Ez az információ aláírást jelent a dal ezen részéhez, és ez az aláírás a dal egészének ujjlenyomatának részévé válik.

Ne feledje, hogy feltételezzük, hogy a felvétel nem tökéletes körülmények között történik (azaz „süket szobában”), és ennek eredményeként fel kell tüntetnünk egy fuzz faktort. A fuzz faktor elemzést komolyan kell venni, és egy valós rendszerben a programnak lehetőséget kell adnia arra, hogy ezt a paramétert a felvétel körülményei alapján állítsa be.

Az egyszerű hangkeresés érdekében ez az aláírás a hash tábla kulcsává válik. A megfelelő érték az az idő, amikor ez a frekvenciakészlet megjelent a dalban, valamint a dal azonosítója (dal címe és előadója). Íme egy példa arra, hogyan jelenhetnek meg ezek a rekordok az adatbázisban.

Hash Tag Time in Seconds Song

30 51 99 121 195	53.52	A dal A művésztől
33 56 92 151 185	12.32	B dal B művésztől
39 26 89 141 251	15.34	C dal C művésztől
32 67 100 128 270	78.43	D dal: D művész
30 51 99 121 195	10.89	E dal E művésztől
34 57 95 111 200	54.52	A dal A művésztől
34 41 93 161 202	11.89	E dal E művésztől

Ha egy teljes dalkönyvtárat futtatunk ezen a zenei azonosítási folyamaton keresztül, létrehozhatunk egy adatbázist, amely a könyvtár minden dalának teljes ujjlenyomatát tartalmazza.

A zenei algoritmus: a dal azonosítása

A klubban jelenleg játszott dal azonosításához rögzítjük a dalt a telefonunkkal, és a felvételt ugyanazzal az audio-ujjlenyomat-felvételi eljárással hajtjuk végre, mint fent. Ezután elkezdhetjük keresni az adatbázisban a hash-címkéket.

Amint előfordul, sok kivonatcímke meg fog felelni több dal zenei azonosítójának. Például előfordulhat, hogy az A dal egy darabja pontosan úgy hangzik, mint valami E dal. Természetesen ez nem meglepő - a zenészek mindig „kölcsönkapták” egymástól a nyalásokat és a riffeket, és manapság a producerek más dalokat is mintát vesznek az idő. Valahányszor egy hash taget illesztünk össze, a lehetséges találatok száma kisebb lesz, de valószínű, hogy ez az információ önmagában nem szűkíti le a mérkőzést egyetlen dalra. Tehát még egy dolgot ellenőriznünk kell a zenefelismerési algoritmusunkkal, ez az időzítés.

A klubban rögzített minta a dal bármely pontjáról származhat, ezért nem tudjuk egyszerűen összehangolni az illesztett kivonat időbélyegét a mintánk időbélyegével. Több egyeztetett hash segítségével azonban elemezhetjük a mérkőzések relatív időzítését, és ezáltal növelhetjük a bizonyosságunkat.

Például, ha megnézi a fenti táblázatot, akkor látni fogja, hogy a 30 51 99 121 195 hash címke mind az A, mind az E. dalnak megfelel. Ha egy másodperccel később a 34 57 95 111 200 hash-szal megegyezünk, az még egy meccs az A dalhoz, de ebben az esetben tudjuk, hogy mind a hash, mind az időbeli különbség megegyezik.

Vessünk i 1 és i 2 mint pillanatokat a felvett dalban, és j 1 és j 2 mint pillanatok a dalban az adatbázisból. Mondhatjuk, hogy két mérkőzésünk van időbeli különbséggel, ha:

RecordedHash (i 1) = SongInDBHash (j 1) ÉS RecordedHash (i 2) = SongInDBHash (j 2)

abs (i 1 - i 2) = abs (j 1 - j 2)

Ez rugalmasságot biztosít számunkra a dal elejétől, közepétől vagy végéig történő rögzítéséhez.

Végül nem valószínű, hogy a klubban rögzített dal minden egyes pillanata megegyezik könyvtárunk ugyanazon dalának minden stúdióban rögzített pillanatával. A felvétel rengeteg zajt fog tartalmazni, amely némi hibát vezet be a mérkőzésekben. Tehát ahelyett, hogy megpróbálnánk a megfelelő dalt kivenni a mérkőzések listájáról, a legvégén az összes illesztett dalt valószínűség szerint csökkenő sorrendbe rendezzük, és a kedvencünk a ranglistán az első dal.

Fentről lefelé

A kérdés megválaszolásához: "Hogyan működik Shazam?" íme egy áttekintés a teljes zenei felismerési és illesztési folyamatról, fentről lefelé:

Ilyen rendszer esetén az adatbázis elég hatalmas lehet, ezért fontos valamilyen méretezhető adatbázist használni. Nincs különösebb szükség a kapcsolatokra, és az adatmodell végül meglehetősen egyszerű, ezért jó valamilyen NoSQL adatbázis használatára.

Hogyan működik a Shazam? Most már tudod

Ez a fajta dalfelismerő szoftver felhasználható a dalok közötti hasonlóság megtalálására. Most, hogy megértette a Shazam működését, láthatja, hogy ennek milyen alkalmazásai lehetnek a taxirádióban játszott nosztalgikus dal egyszerű Shazaming-on kívül. Segíthet például a zene plágiumának azonosításában, vagy annak kiderítésében, hogy ki volt a kezdő inspiráció a blues, a jazz, a rock, a pop vagy bármely más műfaj egyes úttörői számára. Talán egy jó kísérlet az lenne, ha a dalminta-adatbázist feltöltenék Bach, Beethoven, Vivaldi, Wagner, Chopin és Mozart klasszikus zenéjével, és megpróbálnák megtalálni a dalok közötti hasonlóságokat. Azt hinné, hogy még Bob Dylan, Elvis Presley és Robert Johnson is plágium!

De mégsem tudjuk elítélni őket, mert a zene csak egy hullám, amelyet hallunk, megjegyezünk és megismételünk a fejünkben, ahol fejlődik és változik, amíg rögzítjük a stúdióban, és tovább nem adjuk a következő nagy zenei zseninek.

Az alapok megértése

Hogyan működik a Shazam algoritmus?

A Shazam algoritmus a dal mintáit ujjlenyomatokba lepárolja, és ezeket az ujjlenyomatokat az ismert zeneszámok ujjlenyomataihoz illeszti, figyelembe véve a dalon belüli egymáshoz viszonyított időzítést.

Mi az audio ujjlenyomat?

Az audio ujjlenyomat a dal mintáinak hash címkéinek vagy aláírásainak gyűjteménye. Megmérik, hogy az egyes minták mely frekvenciák a legerősebbek.

Hogyan találja meg Shazam a zenét?

A Shazam úgy találja meg a zenét, hogy összehasonlítja a felhasználó által biztosított felvétel audio ujjlenyomatát az adatbázisból származó ismert dalok ujjlenyomataival.