VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA INFORMAČNÍCH TECHNOLOGIÍ ÚSTAV POČÍTAČOVÉ GRAFIKY A MULTIMÉDIÍ FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER GRAPHICS AND MULTIMEDIA
VERIFIKACE METADAT ZVUKOVÝCH ZÁZNAMŮ
DIPLOMOVÁ PRÁCE MASTER‘S THESIS
AUTOR PRÁCE AUTHOR
BRNO 2012
Bc. PETR PŘEROVSKÝ
VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA INFORMAČNÍCH TECHNOLOGIÍ ÚSTAV POČÍTAČOVÉ GRAFIKY A MULTIMÉDIÍ FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER GRAPHICS AND MULTIMEDIA
VERIFIKACE METADAT ZVUKOVÝCH ZÁZNAMŮ VERIFICATION OF METADATA FOR SOUND RECORDINGS
DIPLOMOVÁ PRÁCE MASTER‘S THESIS
AUTOR PRÁCE
Bc. PETR PŘEROVSKÝ
AUTHOR
VEDOUCÍ PRÁCE SUPERVISOR
BRNO 2012
Ing. ALEŠ LÁNÍK
Abstrakt Práce se zabývá návrhem systému verifikace metadat zvukových záznamů v prostředí mobilních telefonů se systémem Android. Text práce je rozdělen do třech hlavních částí. První část práce je zaměřená spíše na teoretický základ, kde je kladen hlavní důraz na popis systému Android, struktury aplikací, popis audio souboru MP3 a teoretický základ Fourierovy transformace v oblasti zpracování signálů. Druhá část práce je věnována návrhu řešení, analýze a implementaci. Třetí část se zaobírá testováním.
Abstract The work deals with verification of the metadata of audio recordings in an environment of mobile phones running Android. The text work is divided into three main parts. The first part is focused more on theoretical basis, where the main emphasis on the description of Android, application structure, description of the audio MP3 file and theoretical basis of Fourier transform in signal processing. The second part is devoted to solution design, analysis and implementation. The third part deals with testing.
Klíčová slova Android, Java, C++, SDK, NDK, MP3, MPEG-1, ID3, DFT, FFT, Fourierova transformace, Hannovo okno, Java Virtual Machine, Dalvik Virtual Machine, Emulátor, Otisk, Šum, Nativní, Redukce, Mobilní telefon
Keywords Android, Java, C++, SDK, NDK, MP3, MPEG-1, ID3, DFT, FFT, Fourier transform, Hann window, Java Virtual Machine, Dalvik Virtual Machine, Emulator, Fingerprint, Noise, Native, Reduction, Mobile phone
Citace Bc. Petr Přerovský: Verifikace metadat zvukových záznamů, diplomová práce, Brno, FIT VUT v Brně, 2012
Verifikace metadat zvukových záznamů Prohlášení Prohlašuji, ţe jsem tuto diplomovou práci vypracoval samostatně pod vedením Ing. Aleše Láníka Uvedl jsem všechny literární prameny a publikace, ze kterých jsem čerpal.
…………………… Bc. Petr Přerovský 2012
Poděkování Rád bych zde poděkoval Ing. Aleši Láníkovi a doc. Dr. Ing. Janu Černockému za jejich odbornou pomoc a cenné rady při zpracování této práce. Velmi rád bych také poděkoval své rodině za podporu a přítelkyni za její čas věnovaný čtením textové části práce.
© Bc. Petr Přerovský, 2012 Tato práce vznikla jako školní dílo na Vysokém učení technickém v Brně, Fakultě informačních technologií. Práce je chráněna autorským zákonem a její užití bez udělení oprávnění autorem je nezákonné, s výjimkou zákonem definovaných případů..
Obsah Obsah................................................................................................................................................ 1 1
Úvod......................................................................................................................................... 3
2
Teorie ....................................................................................................................................... 4
3
4
5
2.1
Android ............................................................................................................................. 4
2.2
MPEG-1 Audio Layer 3 (MP3) .......................................................................................... 8
2.3
Fourierova transformace .................................................................................................. 13
2.4
Obdélníkové vs. Hannovo okno........................................................................................ 16
Analýza .................................................................................................................................. 18 3.1
Poţadavky na funkčnost ................................................................................................... 18
3.2
Minimální poţadavky na mobilní zařízení ........................................................................ 18
Návrh řešení ........................................................................................................................... 19 4.1
Generování audio otisků................................................................................................... 19
4.2
Databáze .......................................................................................................................... 22
4.3
Rychlé vyhledávání metadat, LUT ................................................................................... 23
4.4
Generátor databáze........................................................................................................... 23
4.5
Návrh systému klient-server aplikace ............................................................................... 23
4.6
Návrh demonstrační aplikace, FingerDemo ...................................................................... 26
Implementace ......................................................................................................................... 27 5.1
HashGenerator.java .......................................................................................................... 27
5.2
Hash.java ......................................................................................................................... 28
5.3
Mp3File.java .................................................................................................................... 28
5.4
Mp3FileFFT.java ............................................................................................................. 29
5.5
HannWin.java .................................................................................................................. 29
5.6
Frame.java ....................................................................................................................... 29
5.7
FrameFFT.java ................................................................................................................ 29
5.8
TransformFFT.java .......................................................................................................... 30
5.9
Database.java ................................................................................................................... 30
5.10
ID3.java ........................................................................................................................... 31
5.11
Reader.java ...................................................................................................................... 31
5.12
Server.java ....................................................................................................................... 32
5.13
ClientThread.java ............................................................................................................. 32
5.14
FingerService.java ........................................................................................................... 33
5.15
FingerServiceIntents.java ................................................................................................. 33
5.16
FingerDemoActivity.java ................................................................................................. 34
1
6
7
Testování vyhledávání dat a průběhu generování databáze ...................................................... 35 6.1
Nástroje pouţité při testování ........................................................................................... 35
6.2
Testovací zařízení ............................................................................................................ 36
6.3
Návrh a implementace testování ....................................................................................... 36
6.4
Generování databáze ........................................................................................................ 37
6.5
Šum ................................................................................................................................. 38
6.6
Vzorkovací frekvence ...................................................................................................... 43
6.7
Bitrate .............................................................................................................................. 44
6.8
Zesílení signálu ................................................................................................................ 45
6.9
Doba vyhledávání ............................................................................................................ 46
6.10
Zhodnocení výsledků testů ............................................................................................... 47
Závěr ...................................................................................................................................... 48 7.1
Moţnosti rozšíření a pokračování v práci ......................................................................... 48
7.2
Optimalizace .................................................................................................................... 48
8
Literatura ................................................................................................................................ 49
A
Obsah DVD ............................................................................................................................ 52
B
Návod ..................................................................................................................................... 53
C
B.1
Generování databáze ........................................................................................................ 53
B.2
Server .............................................................................................................................. 54
B.3
FingerDemo ..................................................................................................................... 54
Seznam zkratek ....................................................................................................................... 56
2
1
Úvod
V současnosti kolem sebe téměř nepotkáme člověka, který by nevlastnil mobilní telefon. Díky stále rychlejšímu tempu vývoje informačních a komunikačních technologií se na trhu s mobilními telefony začaly postupně více a více prosazovat zařízení s vlastním operačním systémem, které svou bohatou nabídkou funkcí a výkonem představují kombinaci dříve pouţívaného kapesního počítače (PDA) a mobilního telefonu. Tato zařízení se označují souhrnným názvem jako tzv. smartphone nebo také zcela jednoduše jako „chytré“ telefony. Současný trend vývoje mobilních telefonů dává programátorům moţnost vyvíjet sofistikované, robustní a opravdu mobilní aplikace, které mohou mít uţivatelé kdykoli a kdekoli při ruce. Cílem práce je navrhnout robustní systém umoţňující extrakci vhodných příznaků ze zvukových záznamů (systém generování audio otisků) a k nim zpracování a také vyhledávání příslušejících metadat (autor, album, …) z těchto audio otisků. Systém je rozdělen do čtyř částí. První část systému tvoří klientská aplikace pro operační systém Android pracující na mobilních zařízeních. Druhou část reprezentuje aplikace typu server s moţností efektivního vyhledávání. Server je navrţen tak, aby byl schopen pro patřičný audio otisk zvukového záznamu nalézt jemu odpovídající metadata v databázi a nalezené informace předat klientské aplikaci např. pomocí sítě internet. Třetí částí je persistentní databáze audio otisků a metadat. Čtvrtou a poslední částí systému je plnič (generátor) databáze. O návrhu tohoto systému a principu jednotlivých částí pojednává kapitola 4 Návrh řešení. Kapitola 2 Teorie obsahuje strukturovaný teoretický základ práce zaměřený především na popis platformy Android, zejména pak popis SDK1 a NDK2 systému Android, strukturu aplikací a informace týkající se emulátoru. Dále kapitola obsahuje popis jednoho z nejpouţívanějších hudebních formátů MPEG-1 Audio Layer 3 (MP3), popis jeho struktury, obecné informace o ID3 3 tagu společně s popisem struktury jeho dvou verzí ID3v1 a ID3v2. V kapitole je také rozebrán princip, účel a pouţití dvou externích Java knihoven, umoţňujících přístup k MP3 souborům a jejich matedatům s příklady jejich vyuţití v této práci. Předposlední část kapitoly zaujímá podkapitola s názvem Fourierova transformace, jejímţ cílem je nastínit a současně popsat důleţitý matematický základ zpracování signálů pouţívaný právě při extrakci vhodných příznaků ze zvukových záznamů. Součástí podkapitoly je i popis knihovny jTransform, nabízející 4 typy uţitečných transformací. Nakonec poslední částí kapitoly Teorie je podkapitola zabývající se úpravou dat pomocí Hannova okna. Kapitola 3 pojednává stručně o analýze problému, specifikaci všech poţadavků a také definuje minimální konfiguraci mobilního zařízení. Kapitola 4 Návrh řešení pojednává jiţ konkrétněji o navrhovaném systému generování audio otisků, o jednoznačném binárním popisu audio souborů, o návrhu databáze, zrychleném vyhledávání metadat a také o systému klient-server aplikace. Kapitola 5 Implementace popisuje konkrétněji implementaci hlavních částí aplikace, které vychází z návrhu v předchozí kapitole. Obsah poslední kapitoly 6 tvoří specifikace a výsledky jednotlivých testů ke zjištění různých vlivů na výsledky vyhledávání metadat v databázi audio otisků.
1
SDK - Software Development Kit NDK - Native Development Kit 3 ID3 tag byl vyvinut pro hudební formát MP3 a obsahuje strukturu informací o skladbě typu: Název, Album, Ţánr, … 2
3
2
Teorie
2.1
Android
Android je operační systém vyuţívaný především pro mobilní telefony od firmy Google. Různé zdroje spekulují ([1], [20]) o tom, ţe by se technologie Android mohla pouţívat i pro jiná zařízení (např. počítače, vestavěné systémy, přístroje palubních desek automobilů, atd.), ale hlavní důraz je kladen zejména na vývoj aplikací pro mobilní telefony. Pro vývojáře to má své výhody i nevýhody. Mezi nesporné výhody programování mobilních aplikací obecně patří, ţe chytré telefony jsou velmi oblíbené a ţádané mezi uţivateli a také s rozvojem přístupu k internetu v mobilních telefonech se obliba těchto chytrých zařízení stále zvyšuje (viz Obrázek 2.1). Programování pro Android tedy představuje zkušenost s opravdu zajímavou technologií na velmi rychle se rozvíjejícím trhu mobilních aplikací [Murphy, Mark, L., 2011: 22]. Naopak mezi hlavní nevýhody programování aplikací po mobilní telefony patří jednoznačně to, ţe jsou obecně „malé“ a s tím spojené následující omezení: - „velmi malá“ obrazovka, - chatrnost polohovacích zařízení v případě ztráty elektronického pera nebo jejich výrazná nepřesnost v kombinaci dotykového displeje a velkých prstů, - rozdíl výkonnosti mobilního CPU a velikosti vnitřní paměti oproti klasickému PC nebo serveru je stále výrazný, - v neposlední řadě také závislost na omezeném zdroji energie. Android je open source platforma zaloţená na pozměněném linuxovém jádře. Platforma se kromě linuxového jádra skládá také z řady C/C++ systémových knihoven. Dále obsahuje Dalvik Virtual Machine, který slouţí pro vykonávání bytecodu a tedy aplikace běţí v prostředí Dalvik virtuálního stroje. Pro programování v Androidu se primárně vyuţívá programovacího jazyka Java. Ovšem Dalvik Virtual Machine není to samé co Java Virtual Machine a pro převod Java bytecode do Dalvik bytecode se vyuţívají nástroje dx obsaţené v Android SDK [5]. Android také nabízí poměrně nesmlouvavý a oddělený aplikační rámec, ve kterém vytvořené programy musí běţet. To nám v podstatě poskytuje „jistotu“, ţe naše programy nebudou narušovat funkci ostatních programů nebo samotného přístroje.
Device OS Mix
Connected Device & Smartphone OS Mix Android
3% 1% 1%
14%
Smartphones
14% 72%
Conected Devices
iOS
13% 28%
Features Phones
54%
RIM Other Windows Symbian
Obrázek 2.1: Aktivovaná zařízení s OS Android na trhu [19]
4
2.1.1
SDK
Software Development Kit (SDK) je sada základních nástrojů a komponent, bez kterých si v Androidu vůbec nic nevytvoříme. Holé SDK v základu obsahuje pouze některé vývojové nástroje a ostatní části se doinstalovávají v podobě komponent. Jistě příjemnou skutečností je, ţe sada nástrojů je dostupná pro všechny hlavní platformy (Linux, Windows a Mac)4. Android SDK mimo jiné obsahuje také vlastní emulátor, který umoţňuje testování aplikací bez nutnosti reálného zařízení (více informací o emulátoru obsahuje podkapitola 2.1.4). Pomocí Android SDK a AVD 5 Manageru lze vytvářet a spouštět Android Virtual Devices, coţ jsou nakonfigurované instance „androidního“ emulátoru. Lze si také vymodelovat velice přesné vlastnosti konkrétního zařízení. Příklad Android SDK and AVD Manageru můţeme spatřit na obrázku 2.2.
Obrázek 2.2: Android SDK and AVD Manager
Dalším, dosti důleţitým nástrojem SDK, pomocí kterého lze ladit jednotlivé aplikace, je Dalvik Debug Monitor. Tento nástroj umí komunikovat s běţícími instancemi v emulátoru a také s telefony připojenými k počítači pomocí USB. V případě připojeného telefonu je nutné povolit ladění pomocí USB v nastavení telefonu, abychom byli schopni ladit naše aplikace pomocí debug monitoru. Dalvik Debug Monitor lze pouţít mimo jiné také k získávání screenshotů obrazovky telefonu. Platformy systému Android uvnitř SDK odpovídají produkčním platformám, které běţí na skutečných zařízeních. Jsou to vůbec nejdůleţitější komponenty uvnitř SDK. Kaţdá platforma obsahuje systémové knihovny, systémový obraz, skiny emulátoru, ukázky zdrojových kódů a jiné specifické zdroje konkrétní platformy. Vývojové nástroje, pomocí kterých lze například nahrávat soubory nebo aplikace na zařízení, jsou obsaţeny v balíku Android SDK Platform-tools nebo Google API obsahující knihovny Google map pro vývoj aplikací vyuţívající interně Mapy Google. 4 5
Z pohledu autora je tohle známkou „dobrého vychování“. AVD – Android Virtual Device
5
2.1.2
Struktura Android aplikací
Výsledná Android aplikace je zabalena do balíku s koncovkou .apk (Android package), coţ je ZIP archiv slouţící k distribuci aplikací na reálná zařízení. Archiv obsahuje jiţ zkompilovanou verzi našich prostředků (resources.arsc), jakékoli naše nezkompilované prostředky (uloţené v adresáři res/raw/) a také soubor AndroidManifest.xml. Aplikace jsou navrţeny jako balíky několika komponent, které lze jednotlivě instanciovat. Důvodem je základní vlastnost Androidu, která nám umoţňuje vyuţívat jednotlivé části jiných aplikací a tím zamezit opakovanému vytváření jiţ existující funkcionality, a tak zpříjemnit práci vývojáře [5]. Aplikace se skládají z následující čtveřice hlavních komponent: Aktivity: Aktivity jsou základními stavebními kameny pro tvorbu uţivatelského rozhraní. Lze si je představit jako obrazovky aplikace nebo také jako analogii oken či dialogů stolních počítačů. Kaţdá aktivita specifikuje pouze jednu obrazovku a typicky zaplňuje celé její okno. Obsah okna je specifikován pomocí views (pohledů). View představuje základní stavební kameny pro komponenty uţivatelského rozhraní. Obvykle zabírá obdélníkový tvar na obrazovce a je zodpovědný za kreslení a zpracování událostí. View je základní třída pro widgety, které se pouţívají pro tvorbu interaktivních prvků uţivatelského rozhraní (tlačítka, textová pole, atd.) [15]. Dodavatelé obsahu (Content provider): Dodavatelé obsahu slouţí ke zpřístupnění dat uloţených v zařízení více různým aplikacím. Android poskytuje podporu v tom, abychom mohli svá data zpřístupnit i jiným aplikacím neţ pouze svoji vlastní. Toho lze dosáhnout právě vytvořením dodavatele obsahu. Data lze aplikacemi číst i upravovat. Služby (Service): Sluţby jsou navrţené tak, aby pokračovaly ve své práci nezávisle na jakékoli aktivitě. Jsou uţivatelsky neviditelné, běţí na pozadí. Lze je pouţít např. k detekování aktualizace RSS, k síťové komunikaci při stahování či odesílání e-mailu na pozadí atd. Záměry (Broadcast receiver): Záměry jsou broadcastové zprávy upozorňující aplikace na výskyt různých událostí jako jsou např. přijetí SMS, vloţení datové karty, kritický stav baterie apod. Na záměry můţeme nejenom reagovat, ale lze také vytvářet záměry vlastní a spouštět jejich prostřednictvím jiné aktivity, nebo detekovat různé specifické situace. Android manifest Mimo čtveřici hlavních komponent se mezi základy aplikace Androidu řadí také soubor manifestu (AndroidManifest.xml) v kořenovém adresáři projektu. Manifest je součástí kaţdé aplikace a pomocí něj je moţné deklarovat obsah naší aplikace (jaké komponenty, aktivity, sluţby jsou k dispozici, systémová práva, atd.). Kromě obsahu je zde také uvedeno, jakým způsobem jsou tyto součásti aplikace propojeny s operačním systémem. Zásobník aktivit (Task) Jednotlivě spuštěné instance aktivit jsou vţdy řazeny na zásobník. V momentě, kdy jedna aktivita spustí druhou, je tato nová aktivita přesunuta na vrchol zásobníku a v případě jejího ukončení se předchozí aktivita přesouvá zpět na vrchol zásobníku. Uţivatel můţe komunikovat pouze s instancí aktivity, která je umístěna na vrcholu zásobníku.
2.1.3
NDK
Jak jiţ bylo výše zmíněno, při programování v operačním systému Android se vyuţívá primárně programovacího jazyku Java, výsledné aplikace běţí ve virtuálním stroji Dalvik Virtual Machine. Android Native Development Kit (NDK) umoţňuje vývojářům implementovat části těchto aplikací pomocí nativního kódu jazyky C/C++. To přináší prospěch pro různé druhy aplikací, jejichţ kritické části jsou výpočetně nejnáročnější a implementace těchto částí v C/C++ by přinesla sníţení výpočetní a zároveň časové náročnosti. 6
NDK nabízí sadu nástrojů a souborů ke generování nativních knihoven z C/C++ zdrojů a také způsob, jak vkládat odpovídající nativní knihovny do souboru aplikačních balíků (.apk), které pracují pod systémem Android. NDK stanoví také set nativních systémových hlaviček a knihoven, které budou podporovány ve všech budoucích verzích platformy Android od verze 1.5. Aplikace, které pouţívají nativní technologii, musí být spuštěny na systému Android verze 2.3 nebo vyšší. Výčet podporovaných ARM instrukčních sad aktuální verze NDK a také úplnou dokumentaci systému NDK je moţné nalézt na domovských stránkách android developers [15],[16]. Vyuţívání NDK není relevantní pro všechny druhy Android aplikací a je jen a pouze na vývojářích, aby důkladně zváţili veškeré výhody a nevýhody, kterých není málo. Mezi jedny z hlavních nevýhod patří zvyšující se sloţitost, sníţená kompatibilita, nemoţnost přístupu k frameworks API a výrazně sloţitější ladění aplikací. Z toho plyne, ţe NDK je vhodné spíše pro samostatné aplikace vysoce náročné na operace procesoru a které mohou jednoznačně těţit ze zvýšeného výkonu. Mezi takové aplikace mohou patřit např.: aplikace zpracovávající signály, intenzivní fyzikální simulace a některé druhy zpracovávání dat.
2.1.4
Emulátor
Emulátor je samostatná aplikace, která umoţňuje testování mobilních aplikací bez nutnosti vlastnit reálný přístroj. Tato aplikace je standardní součástí Android SDK. Prostřednictvím nástroje AVD Manager (Obrázek 2.2) lze vytvářet, konfigurovat a spouštět Android Virtual Devices (AVD), coţ jsou virtuální zařízení navrţená tak, aby přesně napodobovala reálná zařízení pouţívající operační systém Android a umoţnila nám tak testovat naše aplikace prostřednictvím emulátoru. Při vytváření kaţdého virtuálního zařízení je třeba specifikovat, jakou třídu zařízení má AVD simulovat. Specifikací třídy zařízení je jednoduše myšleno zvolit si platformu emulovaného systému Android (např. Android 2.2). Vytvoříme-li si například aplikaci s minimálními poţadavky na operační systém Android 2.0, pak je třeba vytvořit AVD také pro platformu Android verze 2.0 nebo vyšší. Aktualizované verze Android platformy jsou navrţeny tak, aby nová verze byla zpětně kompatibilní s verzí starší. Bohuţel ne vše se dá zcela simulovat. Pokud si chceme ušetřit nemalé starosti a také, pokud to s vývojem pro Android myslíme váţně, je třeba mít po ruce vţdy reálné zařízení, na kterém si můţeme veškeré naše postupy patřičně otestovat. Vzhledem k povaze emulátoru, který simuluje chování zařízení, je zřejmé, ţe výkon emulátoru nebude vysoký. Na obrázku 2.3 je znázorněn příklad emulovaného zařízení se systémem Android 2.2.
Obrázek 2.3: Android emulátor
7
2.2
MPEG-1 Audio Layer 3 (MP3)
MP3 je datový formát zápisu zvukových signálů a v současnosti je jedním z nejpouţívanějších audio formátů pro uchovávání a přehrávání zvukových dat. Jedním z důvodů jeho široké rozšířenosti je nízká velikost a dobrá kvalita výsledních audio souborů. Klasické CD sice poskytují mnohdy výrazně vyšší kvalitu, ale jejich velikost je podstatně větší. Klíč k účinné kompresi audio signálů do formátu MP3 tkví v nedokonalosti lidského sluchu. Dalším krokem v kompresi audio signálu je tzv. Joint Stereo. Jedná se o technologii redukce přebytečných informací v okamţiku, kdy se na obou kanálech stereo záznamu nachází totoţný signál. Velikost MP3 souboru je přímo závislá na délce záznamu a na šířce datového toku (bitrate). Bitrate představuje hodnotu udávající mnoţství bitů, které jsou třeba k zakódování 1s zvukového záznamu. Nejčastěji se pouţívá bitrate v rozmezí 128 aţ 192 kbps, přičemţ od 160 kbps je zvukový záznam téměř nerozeznatelný od originálu. Standardní vzorkovací frekvence MP3 souborů je 44,1 kHz.
2.2.1
Struktura MP3
Soubor MP3 neobsahuje pouze komprimovaná audio data, ale jeho součástí mohou být také doplňující informace v podobě ID3 tagu obsahující např. informace o interpretovi, název skladby, … Celý zvukový soubor je rozkouskován na krátké časové úseky tzv. rámce (frame). Součástí kaţdého rámce je hlavička, která popisuje základní údaje (např. typ komprese aplikované na rámec, …) a komprimovaná audio data.
ID3v2
H E A D
FRAME
H E A D
FRAME
…
H E A D
FRAME
ID3v1
Obrázek 2.4: Struktura MP3
Jednotlivé rámce jsou na sobě nezávislé a lze s nimi pracovat zcela samostatně. To nám umoţňuje např. začít přehrávat audio soubor z jeho libovolného místa. Kaţdý rámec začíná svoji hlavičkou a končí začátkem hlavičky rámce následujícího. Délka kaţdého časového úseku je konstantní a to zpravidla 26ms, datová velikost však konstantní být nemusí za předpokladu pouţití variabilního datového toku. Systém variabilního datového toku slouţí ke sníţení velikosti výsledného souboru a přitom zachování vysoké kvality zvukové nahrávky. Principem systému je pouţití vyššího datového toku v místech s vyššími tóny a naopak nízkého datového toku v oblastech s tóny nízkými. Meta-data a jejich struktura obsaţená v hlavičce kaţdého rámce jsou přehledně znázorněna na obrázku 2.5. Hlavička začíná vţdy synchronizačním blokem o velikosti 11 bitů, následuje ID (MPEG verze) 2 bity, MPEG Layer (Layer I, II, III) 2 bity, Chybový bit, Bitrate (datový tok rámce) 4 bity, Sampling rate frequency (vzorkovací frekvence, standardně 44,1 kHz) 2 bity, Padding bit, Private bit, Channel mode (stereo, joint stereo, dual channel, single channel) 2 bity, Mode extension (rozšíření pouze pro joint stereo), Copyright (autorsky chráněno true/false) 1 bit, Original (true/false) 1 bit, Emphasis (nevyuţívá se) 2 bity. Velikost hlavičky je pevně stanovena a to na 32 bitů.
8
Synchronizace
Protect bit
Layer
ID
Bitrate Frequency
Padding bit
Private bit
Channel mode
Mode extention
Copyright Original
Emphasis
Audio Data
Obrázek 2.5: Struktura MP3 frame head [6]
2.2.2
ID3 Tag
Primárním účelem ID3 tagu je připojit k MP3 souboru doplňující informace, které by napomáhaly v identifikaci a popisu audio souboru. Pomocí ID3 tagu je hudební přehrávač schopen zobrazovat např. informace typu: název interpreta, název skladby, název alba, rok vydání, popis a ve verzi 2 dokonce i obrázky. První pevná struktura doplňujících textových informací, která se připojovala na konec souboru MP3 byla navrţena Ericem Kempem a byla označována jako ID3 tag (později ID3v1) [7]. Díky řadě nedostatků a malé flexibilitě ID3v1 vznikla nová, mnohem sofistikovanější verze s označením ID3v2. ID3v1 První verze ID3 tagu je umístěna aţ na samém konci MP3 souboru a její velikost je fixně stanovena na 128 bajtů. Toto jsou ovšem jedny z hlavních nedostatků ID3v1. Umístění na samém konci souboru má zásadní nevýhodu v případě streamování hudby, kdy informace o skladbě jsou staţeny aţ jako poslední. Fixně stanovená délka umoţňuje vkládat informace o skladbě pouze v pevné a omezené délce. V případě názvu skladby, názvu interpreta nebo názvu alba je délka informace omezena na 30 znaků. Vše, co je delší jak 30 znaků, musí být zkráceno a vše, co je kratší, musí být naopak doplněno binární nulou. Všechny tyto závaţné nedostatky řeší mnohem sofistikovanější ID3v2.
9
Informace
Délka
Pozice
Identifikátor “TAG“
3B (znaky)
0-2
Název skladby
30B (znaků)
3 - 32
Název interpreta
30B (znaků)
33 - 62
Název alba
30B (znaků)
63 - 92
Rok vydání
4B (znaky)
93 - 96
Komentář
30B (znaků)
97 - 126
Ţánr
1B (znak)
127
Tabulka 2.1: Struktura tagu ID3v1 [9]
Strukturu tagu ID3v1 popisuje Tabulka 2.1. První tři bajty tagu představují identifikátor v podobě tří znaků „TAG“, které informují o tom, ţe od tohoto místa začíná ID3v1 tag a za tímto identifikátorem následuje 125 bajtů doplňujících informací. Jak jiţ bylo zmíněno, jednotlivé poloţky tagu mají svoji fixní délku (viz Tabulka 2.1). V průběhu času prošel ID3v1 řadou úprav a bylo vytvořeno několik verzí typu ID3v1.x, které ale hlavní nedostatky neodstranily aţ verze ID3v2. ID3v2 Sofistikovanější verze ID3 tagu přináší nový pohled na strukturu doplňujících informací a také nové moţnosti práce s nimi. Umístění tagu ID3v2 se přesunulo z konce souboru na jeho začátek. Tato změna zcela odstraňuje zásadní problém při streamování hudby, kdy se informace o skladbě načítaly jako poslední. Odstraněna byla také fixní délka ID3 tagu, která zcela znemoţňovala jeho rozšiřování v případě potřeby přidávat další informace. Výsledkem je, ţe tag ID3v2 můţe obsahovat libovolný počet poloţek s libovolnou délkou informace. Jistě příjemnou změnou je i to, ţe tag můţe obsahovat i obrázek nebo dokonce videoklip, coţ na druhou stranu zvětšuje velikost souboru, ale také zvyšuje komfort předávané informace. Hlavní nevýhodou ID3v2 je jeho poměrně sloţitá implementace a s ní související zpracování tagu, u kterého oproti předchozí verzi není fixní pořadí a ani délka jednotlivých poloţek. Dokonce i umístění tagu na začátku souboru není pevně dáno. Jelikoţ se tagy mohou stále rozšiřovat, musí být software schopen vyhledat a přečíst informace, které zná a ostatní jednoduše ignorovat. Tag je v audio souboru uloţen jako jednolitý celek, kde jednotlivé části na sebe musí vţdy navazovat. Nesmí dojít k tomu, ţe by se mezi jednotlivými částmi objevila audio data. Strukturu tagu ID3v2 znázorňuje obrázek 2.6. Obecně platí, ţe výplň a zápatí tagu se vzájemně vylučují a proto se nemůţe vyskytnout výplň a zápatí zároveň. Podrobnější informace viz [10].
10
Hlavička (10 bajtu) Rozšířená hlavička (proměnná délka, VOLITELNĚ) Položka 1 - Frame (proměnná délka) Položka 2 - Frame (proměnná délka)
... Položka x - Frame (proměnná délka) Výplň (proměnná délka, VOLITELNĚ) Zápatí (10 bajtů, VOLITELNĚ)
Obrázek 2.6: Struktura tagu ID3v2.4 [10]
První část tagu ID3v2 zaujímá Hlavička, jejíţ délka je pevně nastavena na 10 bajtů. Hlavička slouţí k identifikaci ID3v2 tagu a první 3 bajty obsahují 3 znaky „ID3“, coţ je identifikátor tagu. Struktura hlavičky je sloţena takto: ID3v2 ID3v2 ID3v2 ID3v2
identifier version flags size
"ID3" $04 00 %abcd0000 4 * %0xxxxxxx
Následuje volitelná Rozšířená hlavička obsahující informace, které mohou poskytnout další data do struktury, ale zároveň nejsou nezbytně nutné, a proto je rozšířená hlavička volitelná. Struktura hlavičky má následující tvar: Extended header size Number of flag bytes Extended Flags
4 * %0xxxxxxx $01 $xx
Výplň je volitelnou součástí, je umístěna na konci tagu za posledním framem a obsahuje pouze nulové bajty. Vyuţívá se v případě, kdy dojde např. ke změně názvu skladby za název nepatrně větší. Bez výplně by se musel celý tag znova přepsat. Výplň tedy funguje jako taková rezerva pro případné změny či úpravy. Pozor: výplň a zápatí se vzájemně vylučují, proto kdyţ tag obsahuje výplň, nesmí obsahovat zápatí. Zápatí slouţí ke zvýšení rychlosti procesu lokalizace ID3v2 tagu při prohledávání souboru od konce. Zápatí je v podstatě kopie hlavičky jen s tím rozdílem, ţe identifikátor je oproti hlavičce zrcadlově obrácen „3DI“. Pozor: platí stejně tak jako u výplně, obsahuje-li tag zápatí, nesmí obsahovat výplň. Struktura zápatí je následující: ID3v2 ID3v2 ID3v2 ID3v2
identifier version flags size
"3DI" $04 00 %abcd0000 4 * %0xxxxxxx
11
Položka (Frame) obsahuje poţadované informace o skladbě. Pro kaţdou informaci, která se v tagu nachází, je vyhrazena jedna poloţka (frame). Všechny poloţky se skládají z hlavičky, která má 10 bajtů a dat nesoucích informaci. Deseti bajtová hlavička má následující tvar: Frame ID $xx xx xx xx (four characters) Size 4 * %0xxxxxxx Flags $xx xx Kompletní informace viz [10].
2.2.3
jLayer – MP3 Library
jLayer je open source Java MP3 knihovna umoţňující práci se soubory MP3. Zatím nejdůleţitější částí této knihovny, která je vyuţívána v této práci, je její dekodér umoţňující přístup k diskrétním audio datům jednotlivých framů souboru MP3. Pomocí dekodéru lze načítat jednotlivé framy MP3 souboru postupně tak, jak jdou za sebou a získávat audio data v podobě pole hodnot typu short z kaţdého framu. Příkladem získání surových audio dat z jednoho framu budiţ následující úryvek kódu: private static short[] example() { short[] out = null; File file = new File("C:/audio/audio.mp3"); try { FileInputStream fis = new FileInputStream(file);// input stream Bitstream bitstr = new Bitstream(fis); // Bitstream vstupni mp3 Decoder decoder = new Decoder(); // mp3 dekoder Header head = bitstr.readFrame(); // hlavicka datoveho okna if (head != null) { SampleBuffer sbuf = (SampleBuffer) decoder.decodeFrame(head, bitstr); out = sbuf.getBuffer(); // pristup k surovym datum okna bitstr.closeFrame(); // uzavreni predchoziho okna } fis.close(); bitstr.close(); } catch (DecoderException e) { e.printStackTrace(); } catch (BitstreamException e) { e.printStackTrace(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } return (out); }
Nejprve je třeba zajistit přístup k souboru audio.mp3. Toho dosáhneme jednoduše tak, ţe si vytvoříme FileImputStream, který prováţeme s jLayer knihovnou pomocí objektu typu Bitstream knihovny jLayer. Následně si vytvoříme objekt typu Decoder a prostřednictvím metody readFrame() datového objektu Bitstream získáme hlavičku prvního framu audio souboru. Informace obsaţené v hlavičce (viz kapitola 2.2.1) jsou nezbytně důleţité pro objekt dekodéru, který nám pomocí metody decodeFrame(head, bitstr) zprostředkovává přístup k audio datům načteného framu v podobě objektu typu SampleBuffer. V posledním kroce uţ jen přistoupíme k datům uvnitř bufferu metodou getBuffer().
12
2.2.4
jid3lib – Java ID3 Tag Library
Java ID3 Tag Library (dále jen jid3lib) je knihovna nabízející jiţ zcela odladěné a sofistikované metody přístupu k doplňujícím informacím, které jsou obsaţeny v ID3 Tagu souboru MP3. Tato knihovna umoţňuje pohodlně přečíst informace o skladbě, jako je název skladby, interpreta, alba a spousty dalších uţitečných informací. V současnosti knihovna disponuje podporou následujících tagů doplňujících informací: ID3v1, ID3v1.1, Lyrics3v1, Lyrics3v2, ID3v2.2, ID3v2.3 a ID3v2.4. [17] V této práci je knihovna vyuţívána především k přístupu k těmto informacím uvnitř MP3 souborů.
2.3
Fourierova transformace
Fourierova transformace je matematická metoda pro (lineární) zpracování signálů. Umoţňuje nám převod signálů z časové reprezentace 𝑓(𝑡) do frekvenční reprezentace 𝐹(𝜉) a naopak. Vstupní signál můţe být buď v čase spojitém, nebo v čase diskrétním. Principem Fourierovy transformace je rozloţení časově závislého signálu na jeho jednotlivé harmonické sloţky a vyjádření obsahu signálu pomocí frekvenčního spektra. Dovoluje nám tedy analyzovat frekvenční obsah (spektrum) signálu [11].
Přímá Fourierova transformace spojité komplexní funkce 𝑓(𝑥): +∞
𝑓 𝑥 𝑒 −2𝜋𝑖𝑢𝑥 𝑑𝑥
𝐹 𝑢 =
(1)
−∞
Inverzní Fourierova transformace komplexní funkce 𝐹(𝑢) s označením 𝐹 −1 (𝑢): +∞
𝑓 𝑥 = 𝐹 −1 𝑢 =
𝐹 𝑢 𝑒 2𝜋𝑖𝑢𝑥 𝑑𝑢
(2)
−∞
Následující obrázek znázorňuje princip Fourierovy transformace, kdy na vstupu je periodická sinusová vlna s danou amplitudou o frekvenci = 𝑓0 . Průběh vlny je dán vztahem 𝑈 𝑡 = sin (𝑓0 ∙ 𝑡). Výsledné spektrum takovéto periodické vlny vypadá následovně:
Obrázek 2.7: Fourierova transformace, spektrum [12]
13
2.3.1
Diskrétní Fourierova transformace (DFT)
V případě počítačového zpracování signálů máme k dispozici pouze vzorky signálu či spektra v diskrétních časových okamţicích z konečného intervalu. Zavádíme tedy tzv. diskrétní Fourierovu transformaci (DFT), kterou dostáváme formálním nahrazením integrálu integrálním součtem s dělením odpovídajícím periodě vzorkování [13]. Zejména s rozvojem výpočetní techniky našla diskrétní Fourierova transformace mimořádně velké uplatnění. Díky tomu se začaly objevovat jednoúčelové procesory realizující DFT, které jsou součástí mnoha přístrojů.
Diskrétní Fourierova transformace: 𝑁−1
𝐹 𝑢 =
𝑓 𝑥 𝑒
−2𝜋𝑖𝑢𝑥 𝑁
(3)
2𝜋𝑖𝑢𝑥 𝑁
(4)
𝑛=0
Inverzní diskrétní Fourierova transformace: 1 𝑓 𝑥 = 𝑁
2.3.2
𝑁−1
𝐹(𝑢) 𝑒 𝑛=0
Rychlá Fourierova transformace (FFT)
Provádění výpočtu diskrétní Fourierovy transformace je časově velice náročné. Dle definice vyţaduje výpočet 𝑁 2 komplexních součtů a 𝑁 2 komplexních součinů, tedy 2𝑁 2 operací, coţ i pro malý počet vzorků vede k vysoce časově náročnému výpočtu. Tato skutečnost DFT velice omezuje pro pouţití v reálném čase. V roce 1965 J.W.Cooley a J.W.Tukey popsali velice efektivní algoritmus pro výpočet DFT s názvem Fast Fourier Transform (FFT). Tento rychlý algoritmus pro svůj výpočet vyţaduje pouze 𝑁/ 2𝑙𝑜𝑔2 (𝑁) komplexních součinů a 𝑁𝑙𝑜𝑔2 (𝑁) komplexních součtů [12]. Díky algoritmu FFT se stala diskrétní Fourierova transformace velmi rozšířenou metodou pro výpočet Fourierovy transformace. FFT se tak stala nepostradatelnou součástí nejrozšířenějších matematických programů a také je hojně vyuţívána v oblasti digitálního zpracování signálů.
2.3.3
Harmonické složky signálu
Harmonické sloţky signálu je moţné popsat jako jednoduché sinové, případně kosinové (harmonické) průběhy obecně různých kmitočtů, amplitud a fází, na něţ lze daný signál rozloţit. Příklad takového signálu, viz Obrázek 2.8, který znázorňuje tři periodické harmonické sloţky signálu.
Obrázek 2.8: Harmonické složky [14]
14
2.3.4
jTransforms – Java FFT Library
jTransform je open source FFT knihovna, která je napsána v čisté Jave a tudíţ velice dobře přenositelná. V současnosti disponuje čtyřmi typy transformací. K dispozici je Diskrétní Fourierova Transformace (DFT), Diskrétní Kosinová Transformace (DCT), Diskrétní Sinová Transformace (DST) a Diskrétní Hartley Transformace (DHT). Knihovna pro kaţdý typ transformace nabízí několik jejich verzí pro různé druhy vstupních dat. Jsou tomu především 1D, 2D a 3D transformace, které jsou navíc ještě rozděleny do dvou kategorií dle vstupních datových typů, Float a Double. Primární Vyuţití knihovny v této práci je při převodu časově závislých dat do frekvenčního spektra aplikací algoritmu FFT na audio data jednotlivých framů. Jednoduchý příklad práce s knihovnou reprezentuje následující část kódu. Podrobnou dokumentaci knihovny lze nalézt na stránkách knihovny jTransfrom [18]. private static float[] exampleFFT(float[] data) { if (data != null) { int n = data.length; int n2 = n * 2; float[] newData = new float[n2]; for (int i = 0; i < n; i++) { newData[i] = (float) data[i]; } // vstupni pole fft musi byt vzdy dvojnasobne delky data = newData; // mnozstvi dat v poli je vzdy polovicni, zbytek je vypln FloatFFT_1D fft = new FloatFFT_1D(data.length/2); // fft upravi pole do vysledneho tvaru [real,imag,real,imag,...] fft.realForwardFull(data); return(data); } else { return(null); } }
FFT transformace knihovny jTransform ke své práci vyţaduje vţdy pole o dvojnásobné velikosti neţli je skutečná velikost dat umístěných v poli. Zbytek pole je tedy jakási výplň s totoţnou velikostí, jako velikost vstupních dat. Je tomu tak proto, ţe výstup transformace je v komplexním tvaru. Metoda transformace převádí pole do výstupního formátu typu [real, imag, real, imag, …], kde „real“ je reálná sloţka komplexního čísla a „imag“ je sloţka imaginární. Nejprve si tedy deklarujeme nové datové pole newData[] o dvojnásobné velikosti a pomocí cyklu do něj přesuneme data z původního pole od počátečního indexu. Zbytek pole ponecháme prázdné. Dále vytvoříme objekt typu FloatFFT_1D, zapouzdřující algoritmus Fast Fourier Transform, pracující s jednorozměrným polem dat. Při vytváření tohoto objektu je třeba definovat mnoţství zpracovávaných dat, coţ je polovina velikosti datového pole s výplní. Nakonec pomocí metody realForwardFull(data) aplikujeme dopřednou FFT transformaci na vstupní pole dat, které metoda převede do jiţ zmíněného výsledného komplexního tvaru [real, imag, real, imag, …].
15
2.4
Obdélníkové vs. Hannovo okno
Reálný signál před vstupem ke spektrální analýze je z pravidla vţdy neperiodický. Tento stav je před provedením DFT nebo FFT nutné řešit jeho periodizací (výběrem úseku dat ke zpracování). To se provádí za pouţití tzv. „okénkových funkcí“. Mezi nejprimitivnější okénkové funkce se řadí funkce obdélníkového okna (Obrázek 2.9), která provádí jen prostý výřez ze zdrojového signálu bez jakékoli úpravy jeho amplitudy. Při pouţití této funkce mohou nastat dva stavy: - První, začátek i konec vybraného úseku na sebe spojitě a hladce navazují. Při pouţití spektrální analýzy pomocí DFT nebo FFT nebude v tomto případě ţádný problém, neboť periodizovaný zdrojový signál nebude obsahovat ţádné skokové přechody. S tímto stavem se však v reálu bohuţel setkáme jen velmi zřídka. - Druhý, začátek a konec vybraného úseku na sebe spojitě nenavazují, vznikají tak mezi jednotlivými úseky ostré, skokové přechody viz Obrázek 2.10. Výsledné spektrum je pak díky nespojitosti analyzovaného signálu silně zarušené a frekvenční sloţky s menšími amplitudami by se v něm mohly zcela ztratit.
Obrázek 2.9: Obdélníkové okno - úsek s nekoherentním vzorkováním [22]
Obrázek 2.10: Obdélníkové okno - periodický signál analyzovaný Fourierovou transformací [22]
Řešením problému nespojitosti a tím pádem skokových přechodů zřetelných na obrázku 2.10 je pouţití okna, které kromě výběru úseku signálu také vhodně upravuje jeho amplitudu. Za tímto účelem bylo vybráno Hannovo okno, jehoţ průběh zajistí, aby začátky i konce periodizovaného signálu na sebe hladce a spojitě navazovaly, viz Obrázek 2.12. Bohuţel Hannovo okno, podobně jako kaţdé jiné, má svoje vlastní spektrum, které se přičítá ke spektru analyzovaného signálu a tím jej částečně ovlivňuje.
16
Průběh Hannova okna je definován následující funkcí: 2𝜋𝑛 𝑤 𝑛 = 0.5 1 − cos 𝑁−1
(5)
Obrázek 2.11: Hannovo okno - úsek s nekoherentním vzorkováním [22]
Obrázek 2.12: Hannovo okno - periodický signál analyzovaný Fourierovou transformací [22]
Na obrázku 2.11 je tečkovaně zvýrazněn průběh Hannova okna a také, jak okno upravuje vybraný úsek signálu dle definiční funkce. Graf na obrázku 2.12 jiţ znázorňuje přímé vyuţití Hannova okna při periodizaci signálu, kde zajišťuje hladkou a spojitou návaznost jednotlivých period oproti grafu na obrázku 2.10.
17
Analýza
3
Následující kapitola je zaměřená zejména na analýzu práce a na specifikaci poţadavků, které byly kladeny hned na počátku vývoje aplikace. Dle zadání má být cílem této práce navrhnout a implementovat systém zpracovávající databázi příznaků (audio otisků) a k nim příslušejících metadat s moţností efektivního vyhledávání. Systém by měl umět pro patřičný zvukový záznam nalézt odpovídající metadata. Po řadě konzultací byla navrţena aplikace typu klient/server s vlastní databází, kde klientská část bude realizována jako sluţba pro mobilní zařízení s operačním systémem Android.
Požadavky na funkčnost
3.1 Klient
Klientská aplikace má být realizována jako sluţba operačního systému Android. Aplikace musí být schopna generovat otisky z audio souborů typu .mp3 kompatibilní s otisky uloţenými v databázi. Síťová komunikace se serverovou částí bude řešena v rámci sluţby, ta bude nabízet pouze veřejné metody umoţňující předání konkrétního souboru k vyhledání metadat a k přístupu k získaným metadatům přijatých ze serveru. Navrţená aplikace by měla být maximálně přenositelná.
Server
Server musí být schopen přijmout a obsluhovat přiměřené mnoţství klientů. Server bude řešit poţadavky klientů na přístup k vyhledávání v databázi. Prohledávání databáze otisků a hledání odpovídajících metadat pro patřičný zvukový záznam bude implementováno kompletně na straně databáze, server zde bude figurovat pouze jako prostředník. V případě nalezení odpovídajících metadat server data předá klientovi, v opačném případě server klienta informuje o neúspěchu hledání.
Databáze
Databáze musí uchovávat kompletní otisky audio souborů a k nim patřičná metadata. Databáze musí nabízet moţnost efektivního a rychlého vyhledávání metadat skrze uloţené audio otisky.
Minimální požadavky na mobilní zařízení
3.2
Klientská aplikace předpokládá, ţe mobilní zařízení bude splňovat alespoň tyto minimální poţadavky.
Operační systém Android 2.2 RAM: 384 MB CPU: 600 MHz Přístup k datové síti: GPRS/3G/WiFi
18
Návrh řešení
4
Kapitola návrh řešení se zabývá návrhem systému generování jednoznačného popisu audio dat (audio otisků) ze souboru MP3, návrhem systému zpracovávající databázi těchto audio otisků a k nim příslušejících metadat s moţností efektivního a rychlého vyhledávání. Kapitola se také zabývá návrhem architektury klient-server aplikace, kde klientská aplikace je navrţena jako mobilní aplikace pro zařízení s operačním systémem Android a serverová část jako více-vláknový, neblokující server obsluhující poţadavky klientů na přístup k databázi otisků.
4.1
Generování audio otisků
Stejně jako MP3 soubor se skládá z dílčích částí, tak i audio otisk je sloţen z dílčích částí nazývaných sub-otisky. K vygenerování jediného dílčího otisku je třeba specifická sada dat a proto se tato kapitola dělí na dvě části. Na část zabývající se výběrem specifické sady dat a na část popisující generování dílčího sub-otisku.
4.1.1
Výběr dat
Jak jiţ bylo zmíněno, zvukový soubor MP3 je sloţen z dílčích datových oken (označovaných jako „frame“) o konstantní délce zpravidla 26ms (viz podkapitola 2.2.1 Struktura MP3). Této struktury souboru lze při generování audio otisku vhodně vyuţít. Zdrojová audio data jsou nejprve rozdělena na překrývající se úseky (FrameQueue) s faktorem překrytí 31/32, kde právě 1/32 tohoto úseku odpovídá jednomu frame audio souboru (viz Obrázek 4.1). Je tedy zřejmé, ţe takový úsek dat obsahuje 32 MP3 frame, jehoţ celková délka odpovídá cca 0,83s zvukového signálu (32x26ms) a po souboru se pohybuje posunem vţdy pouze o jeden MP3 frame. V případě vícekanálového zvuku jsou data v jednom zpracovávaném úseku ukládána jako průměr všech kanálů. Kaţdý vybraný úsek dat je dále váţen pomocí Hannova okna k zajištění hladké a spojité návaznosti před provedením spektrální analýzy. Výstupem Hannova okna je pole dat označené jako MP3 TIME FRAME. Tato strategie výběru dat vede dále k extrakci jednoho dílčího otisku pro kaţdých 26ms audio souboru. FrameQueue overlap: 31/32
…
FRAME
head
FRAME
head
FRAME
head
FRAME
head
head
ID3v1
FrameQueue overlap: 31/32
FRAME
ID3v2
FrameQueue overlap: 31/32
HannWindow
MP3 TIME FRAME 0,83s Obrázek 4.1: Výběr dat
19
4.1.2
Generátor dílčích audio otisků
Následující podkapitola obsahuje návrh algoritmu generování jednoznačného popisu audio dat řídícího se dle následujícího schématu:
ENERGY IN CRITICAL BAND 1
ENERGY IN CRITICAL BAND 2
ENERGY IN
F(n,0) + -
FFT
CRITICAL BAND 31
ENERGY IN
Save until next frame
-
>0?
+ F(n,2)
+
Save until next frame
-
>0?
+
. . . .
. . . . ENERGY IN
>0?
+
-
-
FRAME
-
F(n,1) +
CRITICAL BAND 3
MP3 TIME
Save until next frame
. . . . F(n,30)
+ -
Save until next frame
-
Save until next frame
-
>0?
+ F(n,31)
+
CRITICAL BAND 32
-
>0?
+
ENERGY IN CRITICAL BAND 33 Obrázek 4.2: Hash Generátor [21]
V první části obrázku 4.2 jsou na vstupu generátoru přiváděny časové rámce, jejichţ výběr z audio souboru popisuje podkapitola 4.1.1. Pro kaţdý vstupní MP3 TIME FRAME je pomocí Fourierovy transformace vytvořeno frekvenční spektrum, ze kterého je vybrána pouze část dat nacházejících se v intervalu 300Hz aţ 2kHz. Zmíněný interval představuje nejdůleţitější spektrální 20
rozsah pro generování sub-otisku, neboť uvnitř tohoto intervalu je obsaţeno nejvíce informací z celého spektra. Za účelem získání 32-bit sub-otisku je tato vybraná část dat plynule rozdělena do 33 nepřekrývajících se kritických pásem. V kaţdém z nich je vypočtena jeho celková energie prostým součtem všech energií uvnitř pásma rozprostřených (ENERGY IN CRITICAL BAND). Další části obrázku 4.2 popisují kroky algoritmu, které jsou výsledkem experimentálního bádání, testování a hledání vhodných cest k nalezení dostatečně robustní metody zpracování audio dat a generování audio otisku. Princip generování binárního sub-otisku ze spektra rozděleného do energetických pásem se dá shrnout pomocí následující rovnice: 𝐹 𝑛, 𝑚 =
1 𝑖𝑓 𝐸 𝑛, 𝑚 − 𝐸 𝑛, 𝑚 + 1 − 𝐸 𝑛 − 1, 𝑚 − 𝐸 𝑛 − 1, 𝑚 + 1
>0
0 𝑖𝑓 𝐸 𝑛, 𝑚 − 𝐸 𝑛, 𝑚 + 1 − 𝐸 𝑛 − 1, 𝑚 − 𝐸 𝑛 − 1, 𝑚 + 1
≤0
(6)
Kde: - 𝐹(𝑛, 𝑚) je výsledný binární otisk (0/1) segmentu dat - 𝐸(𝑛, 𝑚) je hodnota energie v konkrétním kritickém pásmu Z rovnice, ale i z obrázku 4.2 plyne, ţe k vygenerování jednoho sub-otisku je zapotřebí alespoň dvou vstupních rámců překrývajících se dat a jejich vybrané části spektra rozdělené do 33 energ. pásem. Výsledný sub-otisk je sloţen z 32 binárních hodnot a popisuje 26ms zvukového záznamu. Celkový otisk skladby se skládá z dynamické posloupnosti sub-otisků, jejíţ velikost závisí na délce MP3 souboru (počet frame - 32). K redukci dat, ukládání a práci s jednotlivými sub-otisky je pouţit datový typ int, jehoţ velikost přesně odpovídá velikosti sub-otisku (32bit). Binární otisk audio souboru
32b
Frame1
Frame2
Frame3
Frame4
1
1
0
1
0
.. .
1
.. .
0
.. .
1
.. .
0
0
1
1
1
1
1
0
32b Frame1
1
0
1
.
. .
Převod binárního pole na datový typ int int frameNumber1 frameNumber1, frameNumber2, frameNumber3, … Obrázek 4.3: Redukce dat
21
Principem navrhovaného systému je maximálně redukovat binární data a převést je do vhodného formátu, který umoţňuje vyuţití nástrojů programovacího jazyka Java např.: pro ukládání a vyhledávání dat.
Databáze
4.2
Vlastní databáze audio otisků je navrţena jako persistentní tabulka s vyuţitím implementace externí knihovny MegaMap [23]. Je rozdělena do dvou hlavních částí tak, aby uspořila co nejvíce prostoru při ukládání dat a zároveň minimalizovala čas potřebný k vyhledávání poloţek uloţených v databázi pomocí audio otisků. První část databáze je zaměřena na přímé ukládání dat a tvoří persistentní Hash tabulku uchovávající pouze objekty ID3v1/2 tagu, jenţ reprezentují metadata jednotlivých MP3 skladeb. Pro kaţdý záznam v tabulce je vygenerován unikátní klíč (hash), který jej identifikuje a pomocí něhoţ lze k datům později přistoupit. Tento klíč je velice důleţitý a je pouţit v druhé části databáze, kde slouţí jako jedinečný identifikátor konkrétní MP3 skladby. Druhou část databáze lze svojí konstrukcí přirovnat k Lookup Table. Kaţdý záznam je zde identifikován pomocí unikátního sub-otisku. Právě proto byl jedním z hlavních důvodů v podkapitole 4.1.1 vybrán datový typ int k ukládání dílčích sub-otisků. Jednotlivé poloţky tabulky obsahují pole identifikátorů (hash klíčů) konkrétních MP3 skladeb z první části databáze, ve kterých se daný subotisk vyskytuje. Z výše uvedeného je zřejmé, ţe díky datovému typu int a jeho velikosti 32bit můţe maximální počet poloţek LUT 6 dosáhnout aţ 232 . V praxi však tato situace v běţném systému s omezenou pamětí7 RAM není moţná. Proto je Lookup table řešena také pomocí persistentní Hash table, která se v průběhu generování otisků postupně zaplňuje a to jen při výskytu sub-otisku, který v LUT chybí. Také díky řešení implementace v knihovně MegaMap se data z LUT načítají do RAM po částech. Následující obrázek 4.4 znázorňuje průběh konstrukce databázové Lookup tabulky. MP3x 26ms FRAME 2
head
head
head
FRAME 1
FRAME 3
......
32b Sub-Hash 0 1 1 0 0 0 1 32b Sub-H 1 0 0 1 0 0 1
.....
INT
INT
INT
INT
INT
INT
0x00000000 0x00000001
. . .
.....
Audio otisk
LUT
...........
0x62000000
. . .
mp3x
0xB4000000
mp3x
. . .
0xffffffff Obrázek 4.4: Generování LUT 6 7
LUT – Lookup Table Pro příklad PC s 32bit Intel procesorem a 4GB RAM paměti.
22
4.3
Rychlé vyhledávání metadat, LUT
Výsledkem generování audio otisku z mp3 skladby pomocí implementace systému HashGenerátor je audio otisk v podobě pole hodnot typu int, kde kaţdá hodnota představuje v binárním tvaru dílčí sub-otisk konkrétního audio souboru. Tyto hodnoty jsou dále pouţity při generování databázové LUT tabulky k identifikaci audia a jeho metadat uvnitř systému databáze (viz Obrázek 4.4). Kaţdá poloţka LUT tabulky tedy obsahuje seznam všech hash klíčů audio skladeb, ve kterých se dílčí sub-otisk (identifikátor poloţky) vyskytuje. V případě generování otisku audio skladby za účelem nalezení odpovídajících metadat uloţených v databázi není třeba vytvářet otisk z kompletních dat. K jednoznačné identifikaci audia postačí vygenerovat pouze pole 256 dílčích sub-otisků z libovolného souvislého úseku dat zdrojového audio soboru, coţ odpovídá zrnitosti cca 7s zvukového signálu. Toto pole svým obsahem představuje 256 identifikátorů skrze LUT tabulku přímo k seznamu hash klíčů konkrétních metadat uloţených v databázi. V tuto chvíli uţ jen stačí z mnoţství všech hash klíčů vybrat ten, který má nejvyšší skóre výskytu. Nejvyšší skóre, které je „moţné“ dosáhnout je hodnota 256 (konkrétní hash klíč je obsaţen ve všech 256 sub-otiscích LUT tabulky). Takovéto situace lze dosáhnout opravdu jen výjimečně a to pouze jen u audia, které je 100% identické s otiskem v databázi. Hledání přesné shody lze přirovnat k hledání jehly v kupce sena. Uvaţujeme-li běţnou databázi o 10 000 písní, pak taková databáze představuje mnoţství cca 250 × 106 sub-otisků (32bitové sub-otisky). Z toho průměrná pozice výskytu v LUT o velikost 232 je 0,058 = (250 × 106 /232 ). Budeme-li také předpokládat, ţe všechny moţné sub-otisky jsou stejně pravděpodobné, pak průměrné skóre, které lze povaţovat za identifikaci audio souboru je pouze 15 = (0,058 × 256) [24]. V praxi však průměrné skóre u záznamu, který není 100% identický s otiskem v databázi, dosahuje hodnoty 10 - 25.
4.4
Generátor databáze
Generátor databáze představuje aplikaci, která umoţní jednoduše vygenerovat celou databázi nebo snadno do jiţ existující (databáze) přidávat nové záznamy. Aplikace je navrţena jako jednoduchý reader mp3 souborů, bez grafického uţivatelského rozhraní, spustitelná přímo z příkazového řádku. Mezi nabízené funkce aplikace spadá moţnost načítat pouze jednotlivé mp3 soubory nebo kompletní adresáře včetně jejich podadresářů, obsahující mp3 data. Funkce budou rozděleny do dvou kategorií, přičemţ v první budou zahrnuty funkce určené pro běţné počítače a ve druhé funkce upravené pro více-jádrové procesory za účelem jejich efektivního vytíţení a zrychlení tak generování databáze. Předpokladem generátoru je, ţe kaţdý mp3 soubor, zahrnutý do zpracování, bude mít řádně a bezchybně vyplněna doplňující metadata v podobě ID3 tagu.
4.5
Návrh systému klient-server aplikace
Jak jiţ bylo zmíněno výše v úvodu, systém by měl být vypracován ve dvou verzích. První jako klientská aplikace navrţená pro mobilní telefony s operačním systémem Android. Druhá jako server s moţností efektivního vyhledávání metadat audio souborů ve vlastní databázi audio otisků. Součástí obou aplikací je generátor otisků, pracující na totoţném principu navrhovaném v podkapitole 4.1. Přenos dat mezi klientem a serverem je řešen pomocí klasických nástrojů síťové komunikace jazyka Java (ObjectInput/OutputStream). Princip navrhovaného systému znázorňuje Obrázek 4.6.
23
4.5.1
Klient
Klientská aplikace je navrţena jako sluţba systému Android, jejíţ hlavní účel je získání přístupu k poţadovaným metadatům, které jsou uloţeny na serveru. Sluţba generuje otiskové posloupnosti 256 sub-otisků ze zvolených audio dat. Následně navazuje spojení se serverem a zasílá získaný otisk dat na server ke zjištění metainformací o zvolené skladbě. Sluţba po přijetí nalezených metadat ze serveru nabízí metody přístupu k přijaté struktuře grafickému uţivatelskému rozhraní aplikace za účelem zobrazení informací uţivateli. Sluţba nabízí vyuţití v mnoha různých aplikacích.
4.5.2
Server
Server je navrţen jako jednoduchý více vláknový síťový systém obsluhy připojených klientů a představuje prostředníka mezi klienty a databází. Kaţdý klient je obsluhován ve vlastním vláknu. Jedním z hlavních účelů serveru je vyhledávání informací v databázi audio otisků pomocí metody popsané v podkapitole 4.3 Rychlé vyhledávání, LUT. Jako doplňující funkcionalitou serveru můţe být např. tvorba statistik vyhledávání, statistik nejvyhledávanějších skladeb, distribuce skladeb apod.
4.5.3
Komunikační protokol
Komunikační protokol je zaloţen na velice jednoduchém principu předávání datových objektů skrze nástroje typu Input/OutputObjectStrem. Po navázání spojení server očekává na svojí straně příjem objektu typu Hash, který reprezentuje otisk generovaný na straně klienta. Přijetím zasílaných dat server aktivuje databázi a předá přijatý otisk metodám prohledávajícím databázi (viz podkap. 4.3). V případě nalezení metadat jsou tato data zaslána klientské aplikaci v podobě objektu typu ID3. Naopak při nenalezení metadat je klientu zaslán pouze prázdný ID3 objekt, informující o neúspěchu vyhledávání. Po úspěšném odeslání dat je spojení s klientem ze strany serveru ukončeno. Přijetí prázdného objektu nebo jakýchkoli jiných dat na straně serveru představuje okamţité ukončení spojení. V aplikaci klient/server komunikaci vţdy inicializuje klient a v rámci TCP protokolu server přijímá spojení.
Klient
TCP open three-way handshake
Server
SYN SYN, ACK ACK HASH Komunikace výměna objektů
ID3
Prodleva mezi nalezením metadat
FIN ACK FIN ACK four-way handshake TCP close Obrázek 4.5: Komunikační protokol
24
ANDROID APP Mobilní Audio
Telefon Zpracování audia mobilním telefonem a předání metodě generující audio otisk HashGenerátor
… … … …
. . . . .. .. .. .. 1 0 1 1
1 1 0 1
0 0 1 1
1 1 0 0
… … … …
Vygenerovaný audio otisk je zaslán pomocí sítě internet na stanici serveru.
. . . . .. .. .. ..
Síť internet
Síť internet
SERVER APP
Server Odpověď serveru: V případě úspěchu jsou předány nalezená metadata. V případě neúspěchu jsou předány informace specifikující neúspěšné vyhledávání.
Při doručení otisku dochází k jeho rozboru a za pomoci návrhu metod v kapitole 3.3 k vyhledání metadat uvnitř databáze serveru.
FastSearch
Databáze MP3 otisků
Obrázek 4.6: Návrh systému klient-server
25
4.6
Návrh demonstrační aplikace, FingerDemo
Tato kapitola se věnuje návrhu demonstrační aplikace pro mobilní zařízení s operačním systémem Android, jejíţ součástí je také grafické uţivatelské rozhraní. Aplikace je koncipována tak, aby co nejvíce usnadnila uţivateli výběr zkoumaného souboru mp3, nastavení síťové komunikace a také průchod nalezenými metadaty. Po započetí generování otisku a následném vyhledávání metadat, ke zvolenému souboru, bude uţivatel o průběhu operace neustále informován pomocí nástroje typu ProgressBar. Uţivateli bude v rámci demonstrace zobrazena pouze část nalezených metadat, do které jsou vybrány nejdůleţitější informace o skladbě: Title, Artist, Album, Comment. V případě jakéhokoli neúspěchu bude vygenerována zpráva podávající konkrétní informace. Aplikace slouţí pouze k účelům demonstrace a testování funkčnosti navrţeného systému. Mimo výše zmíněného, je vyuţita také jako příklad práce s implementací v podobě sluţby operačního systému Android. FingerDemo pro výběr souborů vyuţívá externí aplikace OI File Manager [25], umoţňující průchod adresáři a přístup k souborům uloţených uvnitř zařízení, např.: na paměťové kartě zařízení.
Obrázek 4.7 FingerDemo
26
5
Implementace
Tato kapitola obsahuje popis hlavních implementačních detailů, popis nejdůleţitějších tříd a funkcí výsledných aplikací. Implementace všech částí systému vychází z předešlých kapitol zabývajících se teorií a návrhem řešení (viz Kapitola 2 a Kapitola 4). Obecné popisy technologií zmíněné a popsané výše se v této kapitole jiţ nebudou opakovat.
5.1
HashGenerator.java
Třída HashGenerator obsahuje sadu různě optimalizovaných veřejných metod, pomocí kterých lze generovat audio otisky ze zdrojových mp3 souborů. Implementace jednotlivých částí třídy se řídí striktně dle návrhu, který je uveden v podkapitole 4.1. Instanci třídy vyuţívá především generátor databáze při vytváření jednotlivých otisků dat, dále pak implementace klientské aplikace. Jednotlivé metody třídy vyuţívají vlastní implementaci vstupních a výstupních dat. Tyto objekty budou popsány níţe v této kapitole. Třída obsahuje následující výčet veřejných metod:
public Hash genHash(Mp3FileFFT mp3) Funkce generuje kompletní otisk ze zdrojového mp3 souboru předávaného v podobě objektu typu Mp3FileFFT. Generátor si v tomto případě ukládá průběh a výsledky kompletní rychlé Fourierovy transformace zcela do paměti. Funkce má velkou spotřebu paměti RAM, ale méně zatěţuje procesor. V případě nedostatečně velkého mp3 soboru (méně jak 260 frame) vyvolá výjimku VerySmallMp3Exception. -
public Hash genHashOptim(Mp3FileFFT mp3) Stejně jako v předchozím případě, funkce také generuje kompletní otisk ze zdrojového souboru mp3. Generátor si ale v průběhu generování otisku neukládá výsledky kompletní Fourierovy transformace do paměti, nýbrţ průběţně generuje audio otisk. Funkce tímto velice uspoří paměť RAM, ale o něco více zatíţí procesor. -
8
Input: Mp3FileFFT Output: Hash Exception: VerySmallMp3Exception
Input: Mp3FileFFT Output: Hash Exception: VerySmallMp3Exception
public Hash genHashOptim4T(Mp3FileFFT mp3) Principiálně je tato funkce totoţná s genHashOptim(). Funkce však navíc zavádí optimalizaci pro více-jádrové procesory8. Tato Optimalizace spočívá v plynulém rozloţení zátěţe do 4 synchronizovaných vláken a postupném generování jednotlivých částí otisku zvlášť v samostatných vláknech. Oproti předchozí funkci je dosaţeno téměř 100% vytíţení všech jader více-jádrového procesoru8 a navýšení výkonnosti generátoru cca o 50%. Je třeba brát
Konkrétně jde o optimalizaci pro 4 jádrový procesor Intel CORE i5.
27
v potaz i zátěţ procesoru produkovanou systémem přepínání jednotlivých vláken. Nelze tedy očekávat aţ čtyřnásobné navýšení výkonu oproti předchozí funkci, která bez zmíněných optimalizačních úprav dokázala naplno vytíţit pouze jedno jádro procesoru.
public Hash genHash256(Mp3FileFFT mp3) Funkce pracuje na stejném principu generování audio otisků jako genHash() společně se zmíněnými výhodami i nevýhodami. Podstatným rozdílem v implementaci této metody oproti ostatním je, ţe funkce generuje otisk sloţený pouze z 256 dílčích sub-otisků. Toto mnoţství k identifikaci metadat v databázi zcela postačuje (viz podkap. 4.3). -
Input: Mp3FileFFT Output: Hash Exception: VerySmallMp3Exception
public Hash genHash256Optim(Mp3FileFFT mp3) Metoda pracuje obdobně jako předchozí funkce genHash256(). Odlišuje se opět pouze v optimalizaci, která spočívá v neukládání kompletní Fourierovy transformace do paměti, ale v průběţném generování audio otisku. Funkce je tak mnohem vhodnější pro mobilní zařízení se značně omezenou velikostí operační paměti RAM. -
5.2
Input: Mp3FileFFT Output: Hash Exception: VerySmallMp3Exception
Input: Mp3FileFFT Output: Hash Exception: VerySmallMp3Exception
Hash.java
Třída Hash zapouzdřuje implementaci serializovaného objektu určeného k uchovávání a přenosu dat představujících audio otisk konkrétního mp3 souboru. Třída obsahuje dvojici konstruktorů: public Hash() public Hash(int[] hashIntArray) První konstruktor vytváří jen prázdný objekt, který je nutné před naplněním daty inicializovat délkou pole vkládaných dat pomocí metody initHashArr(int length). Druhý konstruktor slouţí k vytvoření objektu, který reprezentuje audio otisk, jenţ obsahuje data v podobě pole dílčích subotisků (int[] hashIntArray) konkrétního mp3 souboru. Třída také nabízí sadu metod, umoţňujících přístup ke kompletním datům uvnitř objektu, jejich úpravě nebo k jejím konkrétním částem, které jsou identifikovány indexy.
5.3
Mp3File.java
Následující třída představuje zástupce audio souboru společně se sadou metod a nástrojů pro obsluhu, dekódování a přístup k datům mp3 soboru prostřednictvím dekodéru externí knihovny jLayer (viz podkap. 2.2.3). Skrze obsaţené metody lze přistupovat např. k informacím týkajících se vzorkovací frekvence, bitrate, počtu frame mp3 souboru, ale především lze přistupovat k datům zvukového souboru obsaţených v jednotlivých framech.
28
5.4
Mp3FileFFT.java
V podkapitolách 4.1.1 a 4.1.2 byl popsán systém výběru dat do datových polí MP3 TIME FRAME a následném generování dílčích sub-otisků. Tato třída doplňuje implementaci předchozí Mp3File.java právě o takové metody, umoţňující výběr překrývajících se datových úseků z mp3 způsobem, který byl detailně popsán ve zmíněné podkapitole 4.1.1.
5.5
HannWin.java
Třída implementuje princip úpravy dat pomocí Hannova okna, které je popsáno v podkapitole 2.4. Obsahem třídy je dvojice statických metod popsané níţe:
public static float[] hannDataWin(short[] data) Metoda ořízne vstupní data dle Hannova okna o stejné velikosti jako velikost pole vstupních dat. Průběh Hannova okna kopíruje matematickou definici specifikovanou rovnicí č.: 5. Funkce nejprve vygeneruje pole vah o stejné velikosti jako vstupní pole dat. Jednotlivé váhy jsou vypočteny dle zmíněné definice okna. Kaţdý prvek vstupního pole je následně váţen jemu odpovídajícím prvkem z pole vah. -
short[] data float[] – Upravená data pomocí Hannova okna.
public static float[] hannFunction(int N) Metoda generuje pouze pole vah Hannova okna o velikosti N. -
5.6
Input: Output:
Input: Output:
int N float[]
– Velikost okna. – Pole vah Hannova okna.
Frame.java
Objekt třídy Frame uchovává data překrývajících se datových polí označených v této práci jako MP3 TIME FRAME (viz podkap. 4.1.1). Cílem implementace je vytvořit datový objekt, který je moţné snadno předávat jako vstup metodám implementujícím FFT9 a který bude také obsahovat i doplňující informace, jako je např.: vzorkovací frekvence apod.
5.7
FrameFFT.java
Výstupem implementace FFT jsou data frekvenčního spektra, obsaţená v objektu třídy FrameFFT. Tato třída zajišťuje výběr dat ze spektra v rozsahu 300Hz – 2kHz a jejich plynulé rozdělení do 33 energetických pásem. Význam tohoto spektrálního rozsahu a účel rozdělení dat do pásem je popsán v podkapitole 4.1.2. Implementace nabízí metody, umoţňující přístup ke kompletním spektrálním datům, dále jen k části spektra nacházejícího se ve zmíněném rozsahu, k jednotlivým energetickým pásmům vypočtených z vybrané části, ale i z kompletního spektra.
9
FFT – Fast Fourier Transform (dále jen FFT)
29
5.8
TransformFFT.java
Třída TransformFFT umoţňuje přístup k vyuţití nástrojů z externí knihovny jTransform (viz podkap. 2.3.4). Implementace nabízí pouze jedinou veřejnou metodu:
public FrameFFT transformFrame(Frame frame) Metoda zajišťuje úpravu vstupních dat audio souboru pomocí Hannova okna a následně jejich převod do frekvenčního spektra s vyuţitím funkcí FFT externí knihovny jTransform. -
5.9
Input: Output:
Frame FrameFFT
- Vstupní data v podobě jednotného objektu (viz 5.6). - Výstupní data v podobě jednotného objektu (viz 5.7).
Database.java
Implementace databáze zcela vychází z návrhu uvedeného v kapitole 4.2. Systém je rozdělen do dvou částí, přičemţ kaţdá část operuje nad vlastním persistentním úloţištěm dat. Jednotlivá úloţiště se nacházejí v podadresáři /database na pevném disku počítače a jsou pojmenována následovně: dataID3.data - Úloţiště obsahuje kompletní metadata audio souborů. dataID3.index - Indexace úloţiště, data jsou generována nástroji z MegaMap. dataSubHash.data - Úloţiště obsahuje data dílčích sub-otisků (viz podkap. 4.2 a 4.3). dataSubHash.index - Indexace úloţiště, data jsou generována nástroji z MegaMap. Pro veškerou práci s persistentní pamětí (přístupy k datům, ukládání, vyhledávání) databáze vyuţívá dostupné nástroje a řešení externí knihovny MegaMap [23]. Třída disponuje následujícími funkcemi:
public void load(String Directorypath) Před započetím práce s databází je třeba načíst uloţená data a databázi připravit k pouţití. Za tímto účelem slouţí metoda load(), která má jako jediný vstupní parametr hodnotu typu String, obsahující cestu k adresáři úloţišť databáze (např.: c:/data/database). V případě jakékoli chyby v průběhu přípravy databáze, metoda vyvolá výjimku MegaMapException. POZOR: Po skončení práce s databází je třeba databázi uzavřít metodou shutdown(). -
Input: String Directorypath Exception: MegaMapException
public void shutdown() Metoda zcela uzavírá databázi, ukládá veškerá data do úloţišť a uvolňuje obsazenou operační paměť RAM. POZOR: Metodu je třeba vyvolat vţdy při ukončení práce s databází. Neuzavřením riskujeme ztrátu neuloţených a načtených dat v operační paměti systému!
public void put(Hash hash, ID3 id3) Metoda vkládá do databáze metadata v podobě ID3 tagu souboru mp3 (viz podkap. 4.2). Tato data jsou uvnitř databáze identifikována pomocí otisku popisujícího konkrétní audio soubor. Hash - Otisk audio souboru mp3 (viz podkap. 5.2). ID3 - ID3 tag obsahující metadata souboru mp3 (viz podkap. 5.10). - Exception: MegaMapException public ID3 searchID3withHighScore(Hash hash) Rychlé vyhledávání metadat v podobě ID3 tagu z databáze audio otisků zprostředkovává následující metoda, která vrací objekt s nejvyšším skóre shody. Vstupní parametr představuje -
Input:
30
kompletní, nebo částečný otisk audio souboru v podobě objektu typu Hash. Celý princip vyhledávání spočívá v průchod LUT tabulkou a výběru metadat s nejvyšším počtem shod dílčích sub-otisků. Nastane-li případ, ţe není nalezena ţádná shoda s dílčí částí vstupního otisku, pak metoda předává pouze prázdný objekt s hodnotou null. Implementace a princip vyhledávání přesně odpovídá návrhu řešení uvedeném v podkapitole 4.3. -
Input: Hash - Dílčí, nebo kompletní otisk audio souboru (viz podkap. 5.2). Output: ID3 - Nalezená metadata v podobě ID3 tagu (viz podkap. 5.10). Exception: MegaMapException
Příklad načítání databáze při spuštění serveru je uveden v přiloţeném návodu.
5.10
ID3.java
Objekt třídy ID3 je navrţen jako komplexní prostředek k archivaci a přenosu metadat mp3 souboru. Implementace vyuţívá nástroje knihovny jid3lib (viz podkap. 2.2.4) ke zpřístupnění jednotlivých informací obsaţených ve strukturách dat tagů ID3v1 a ID3v2 souboru mp3 (viz podkap. 2.2.2), které objekt zapouzdřuje. Přístup k veškerým metainformacím je zajištěn prostřednictvím sady veřejných metod. Třída obsahuje dvojici konstruktorů, kde první z dvojice vytváří zcela prázdný objekt vhodný k pozdějším úpravám případně vlastnímu naplnění metadaty. Druhý konstruktor jiţ inicializuje objekt konkrétním obsahem metadat z audio souboru mp3. public ID3() public ID3(ID3v1 id3v1, AbstractID3v2 id3v2) Vstupní parametry typu ID3v1 a AbstractID3v2 jsou součástí implementace externí knihovny jid3lib.
5.11
Reader.java
Třída Reader reprezentuje implementaci metod jednoduchého generátoru databáze, jehoţ návrh je obsahem podkapitoly 4.4. Veškeré metody uvnitř třídy jsou optimalizovány pro procesor 10 s více výpočetními jádry a při generování audio otisků pouţívají nástroje třídy HashGenerator, zmíněné v podkapitole 5.1. Třída disponuje následujícím výčtem čtyř hlavních metod. Uvedené metody se dělí do dvou skupin společných vlastností, ale s odlišnými parametry. První skupinou jsou metody obsahující parametr databaseDir specifikující adresář, ve kterém je nebo bude uloţena konkrétní databáze. Druhou skupinou jsou metody, které jiţ zmíněný parametr neobsahují. Tyto metody předpokládají, ţe databáze bude uloţena v podadresáři data/database, nacházejícího se ve stejném adresáři jako je generující aplikace. V opačném případě metody samy vytvoří výše zmíněný adresář a do něj uloţí novou, aktuálně generovanou databázi.
10
public void readDirectory4T(File dir) Metoda načítá veškerý audio obsah (.mp3) z předávaného adresáře a jeho podadresářů. Ke kaţdému souboru vygeneruje audio otisk a uloţí jej společně s metadaty souboru do databáze. V případě její neexistence vytvoří databázi novou a data do ní vloţí. Do jiţ existující data jen přidá a uzavře ji. Metoda se řadí do druhé skupiny zmíněných metod. - Input: File dir - Cesta k adresáři s uloţenými audio daty.
public void readDirectory4T(String databaseDir, String audioDir)
Konkrétně 4 jádrový procesor Intel CORE i5
31
Stejně jako předchozí metoda i tato pracuje na totoţném principu načítání audio (.mp3) souborů z adresáře a přidávání jejich otisků společně s metadaty do databáze. Jediným podstatným rozdílem v implementaci metody je, ţe obsahuje popisovaný parametr databaseDir a tedy spadá do první ze zmíněných skupin metod v úvodu této podkapitoly.
– Cesta k adresáři databáze. - Cesta k adresáři s uloţenými audio daty.
Input: File file - Zpracovávaný mp3 soubor. Exception: VerySmallMp3Exception
public void readFile4T(String databaseDir, File file) Ke stejnému účelu jako předcházející metoda slouţí i tato. Metoda se liší pouze doplňujícím parametrem databaseDir, jenţ ji zařazuje do první ze zmíněných skupin metod v úvodu této podkapitoly. -
5.12
String databaseDir String audioDir
public void readFile4T(File file) Metoda načítá a vkládá do databáze pouze jeden záznam v podobě audio otisku mp3 souboru s jeho metadaty. Metoda se řadí do druhé skupiny zmíněných metod, tj. předpokládá existující databázi v podadresáři data/database. -
Input:
String databaseDirt - Cesta k adresáři databáze. File file - Zpracovávaný mp3 soubor. Exception: VerySmallMp3Exception Input:
Server.java
Server je zaloţen na principu vícevláknové obsluhy připojených klientů. K jeho implementaci, vycházející z návrhu systému klient-server (viz podkap. 4.5) byly vyuţity standardní nástroje jazyka Java. Konkrétně se jedná o tyto třídy InetAddress, InetSocketAddress, ServerSocket, SocketAddress, Socket. Jádro celého serveru tvoří hlavní vlákno zajišťující přípravu databáze, spuštění a udrţování síťové komunikace, příjem a akceptování spojení. O obsluhu jednotlivých klientů se stará klientské vlákno ClientThread. Nastavení společně s příkladem spuštění serveru je popsáno v přiloţeném návodu.
5.13
ClientThread.java
Obsluha poţadavků klientské aplikace připojené na server je soustředěna do vlastního obsluţného vlákna. Vlákno implementuje komunikační protokol navrţený v podkapitole 4.5.3 a řeší veškeré poţadavky klienta na přístup k databázi. Příjem a odesílání dat mezi klientem a serverem je řešeno uvnitř tohoto vlákna pomocí nástrojů ObjectInputStream a ObjectOutputStream. Popis činnosti: Obsluţné vlákno očekává příjem audio otisku ze strany klienta zapouzdřeného v objektu typu Hash (viz podkap. 5.2). Záhy po přijetí dochází k aktivaci databáze a vyhledávání záznamu metadat odpovídajících doručenému otisku. Nalezená data v podobě objektu ID3 (viz podkap. 5.10) jsou následně odeslána klientské části. Krátce po odeslání dat je spojení ukončeno společně s ukončením obsluţného vlákna a uvolněním veškerých obsazených prostředků.
32
5.14
FingerService.java
Sluţba FingerService slouţí k navázání spojení se serverem, generování audio otisků a zasílání poţadavků na vyhledávání metadat v databázi serveru. Veškerá činnost sluţby je prováděna na pozadí aktivity, se kterou sluţba komunikuje pomocí „broadcast“ záměru zprostředkovávaného instancí třídy Intent. K záměru jsou navíc sluţbou přibaleny doplňující informace o výsledku vyhledávání a také nalezená metadata. Sluţba je navrţena a implementována tak, aby ji mohla pouţívat jakákoli komponenta systému Android. API sluţby nabízí následující veřejné funkce:
public void setNetworkSetting(String address, int port) Nastavení síťového rozhranní sluţby. -
Input:
String address Int port
- defaultní nastavení: 127.0.0.1 - defaultní nastavení: 10991
public String getActualAdress() Vrací aktuálně nastavenou adresu serveru.
public int getActualPort() Vrací aktuálně nastavený port síťového spojení k serveru.
public void search(File file) V rámci sluţby, funkce vytvoří vlastní vlákno, ve kterém na pozadí aktivity spustí generování audio otisku předaného mp3 souboru. Vygenerovaný otisk následně zašle na server za účelem vyhledání metadat o vstupním audiu. Server poţadavek zpracuje a sluţbě odpoví (viz podkap. 4.5). Vlákno sluţby odpověď serveru zpracuje a informaci o výsledku vyhledávání společně s doručenými metadaty přibalí k záměru (intentu), který předá aktivitě jako BroadcastIntent. Po odeslání intentu dochází k ukončení vlákna a uvolnění veškerých obsazených prostředků. Přibalené informace a metadata k intentu společně se záměrem samotným jsou identifikovány dle specifických klíčů, které jsou obsahem statické třídy FingerServiceIntents (viz podkap. 5.15). -
5.15
Input:
File file
- Vstupní mp3 soubor.
FingerServiceIntents.java
FingerServiceIntents je knihovnou statických hodnot obsahující identifikátory intentů, klíče k předávaným informacím a metadatům uvnitř intentů, hodnoty request kódů. Popis jednotlivých hodnot společně s významem jednotlivých request kódů je uveden v následujícím výčtu:
String INTENT_SERVICE_BROADCAST Identifikátor broadcast záměru (intentu) vysílaného sluţbou za účelem informování klientské aktivity o dokončení procesu vyhledávání metadat. Předávaný broadcast intent obsahuje také rozšiřující informace a nalezená metadata. Příklad přístupu k rozšiřujícím datům: - intent.getExtends(KEY_REQUEST_CODE) -> int request code - intent.getExtends(KEY_ID3_DATA) -> ID3 nalezená metadata
33
String KEY_ID3_DATA Přístupový klíč k metadatům, které rozšiřují sluţbou předávaný broadcast intent.
String KEY_REQUEST_CODE Přístupový klíč k request kódu, který rozšiřuje sluţbou předávaný broadcast intent.
int REQUEST_SEARCH_FILE_OK Nalezení mp3 metadat v databázi proběhlo úspěšně. Metadata jsou součástí předávaného broadcast intentu.
int REQUEST_SEARCH_FILE_NO Vyhledávání mp3 metadat proběhlo neúspěšně. Databáze otisk audio souboru neobsahuje.
int REQUEST_SEARCH_FILE_ERROR V průběhu procesu vyhledávání mp3 metadat došlo k blíţe nespecifikované chybě.
int REQUEST_FILE_IS_VERY_SMALL Upozornění na skutečnost, ţe audio soubor předávaný sluţbě k nalezení metadat je příliš malý.
5.16
FingerDemoActivity.java
FingerDemoActivity představuje implementaci nenáročné aktivity demonstrační aplikace, jejíţ návrh je popsán v podkapitole 4.6. K vyhledávání metadat konkrétních audio souboru vyuţívá aplikace plně implementaci výše zmíněné sluţby. Procházení adresářů a výběr jednotlivých souborů z paměťové karty mobilního zařízení je zajištěn externí aplikací OI File Manager [25]. Demonstrační aplikace je určena pouze pro mobilní zařízení s operační systémem Android.
34
6
Testování vyhledávání dat a průběhu generování databáze
Výsledný systém generování audio otisků pro mobilní zařízení byl od začátku koncipován jako sluţba, generující audio otisk souboru mp3 a běţící na pozadí volajícího procesu po dobu vyhledávání meta-dat. Mezi hlavní kritéria celého systému spadá rychlost generování audio otisku, rychlost generování databáze a schopnost systému efektivně vyhledávat metadata zvukových záznamů s rozdílnými vlastnostmi. Tato kapitola bude obsahovat návrh, implementaci a zhodnocení několika testů, zabývajících se vlivy změny komprese, změny intenzity signálu, změny vzorkovací frekvence a výskytu rušení na výsledky vyhledávání. Dále statistiku generátoru databáze a výpočet průměrného času potřebného k vytvoření jednoho audio otisku z mp3 soboru. Pro všechny druhy testů byl pouţit totoţný stereo úsek audio souboru o délce 30s, vzorkovací frekvenci 44,1 kHz, bitrate 128 kbps a u kterého bez úprav dosahovalo skóre shody hodnoty 110 z max. 256. Hodnota skóre je ovlivněna pouţitím nástroje Audacity k výběru úseku audio dat (viz níţe). Testování bylo prováděno na dvojici mobilních zařízeních s operačním systémem Android a na dvou počítačových stanicích. Technická specifikace a účel jednotlivých zařízení budou níţe obsaţeny v této kapitole. Kaţdý test je prováděn nad sadou dat se specifickými vlastnostmi.
6.1
Nástroje použité při testování
Audacity 1.3 Beta Audacity [28] je volně dostupný zvukový editor nabízející mnoho moţností práce se zvukem, jako jsou např.: přímé nahrávání zvuku, exportování nahrávek do různých formátů, importování nahrávek, výběr stop, výběr úseků nahrávek atd. Audacity nabízí také nástroje umoţňující generovat různé druhy tónů, šumy, audio efekty a další data. Tento editor je v práci vyuţíván především pro úpravu mp3 soborů, sniţování vzorkovací frekvence, generování a přidávání šumu k nahrávkám, výběr úseků konkrétních dat. V průběhu testování bylo zjištěno, ţe editor sám upravuje data nahrávky i v případě, ţe v nahrávce nebyly provedeny ţádné změny. Tyto samočinné úpravy se projevují tak, ţe před otevřením originální nahrávky v editoru byl otisk audia 100% totoţný s otiskem dat v databázi. Po otevření mp3 nahrávky v editoru a jejího znovu uloţení, bez jakýchkoliv úprav, je shoda otisku nahrávky s otiskem v databázi cca 50%. Toto však nic nemění na tom, ţe skóre shody se pohybuje v rozmezí 110 - 130 sub-otisků z 256, coţ je stále velice vysoká hodnota shody (viz podkap. 4.3) a není třeba se znepokojovat.
JConsole Aplikace JConsole umoţňuje monitorovat vyuţití systémových prostředků jedné nebo více aplikací najednou. JConsole je produktem společnosti Sun Microsystems a slouţí především k monitorování zátěţe systému (CPU či paměti) produkované sledovanou aplikací. Vyuţití tohoto nástroje bylo především při testování a to pouze pro informativní účely.
35
6.2
Testovací zařízení
Jednotlivé sady testů byly prováděny na následujících zařízeních: Počítačová sestva: Zařízení: Notebook1 (generátor databáze, server) Procesor: Intel Core i5 2520M s frekvencí 2,5 GHz Operační paměť: 2x4 GB DDR3 1333 MHz Grafická karta: NVIDIA Quadro NVS4200M s 1024 MB vlastní pamětí Konektivita: LAN, WiFi Operační systém: Windows 7 Professional, SP 1 Zařízení: Notebook2 (záloţní server, monitoring) Procesor: Intel Pentium M 1,73 GHz Operační paměť: 2x1024 MB Grafická karta: Intel Media Graphics Akcelerator 900 se 128 MB sdílené paměti Konektivita: LAN, WiFi Operační systém: Windows XP Professional, SP 2 Mobilní telefon: Telefon1: HTC Desire S Procesor: 1 GHz Paměť RAM: 768 MB Displej: 800x600 px, 16mil barev Konektivita: WiFi Operační systém: Android 2.3.5 Telefon2: Samsung S5570 Galaxy Mini Procesor: 600 MHz Paměť RAM: 384 MB Displej: 320x240 px, 262mil barev Konektivita: WiFi Operační systém: Android 2.2
6.3
Návrh a implementace testování
Testování bylo zaměřeno především na analýzu vlivu různých změn vzorků na výsledky vyhledávání. Dále pak na rychlost generování audio otisků a také na její závislosti na různé velikosti vstupních dat. Jednotlivé testovací scénáře byly prováděny na výše zmíněných zařízeních v následujících rolích na malé lokální síti:
Notebook1: generátor databáze, hlavní server. Notebook2: záloţní server. Síť: router obsahující integrovaný bezdrátový přístupový bod. Mobilní telefon1-2: nezávislý klient testování.
36
Generování databáze
6.4
Generátor databáze je navrţen a implementován tak, aby v rámci moţností co nejvíce vyuţil dostupné kapacity procesoru (viz podkap. 5.1). Tento test si klade za cíl provést statistiku časové náročnosti generování jednotlivých audio otisků mp3 souborů v závislosti na jejich velikosti. Součástí testu je také výpočet průměrné doby zpracování jednoho mp3 souboru o průměrné velikosti 4,7 MB (viz test). Výsledky testu jsou silně závislé na pouţitém HW generátoru a tedy čistě individuální. Na jiném HW mohou být generované výsledky zcela odlišné. V rámci tohoto testovacího scénáře byl generátor spuštěn na zařízení specifikovaném jako Notebook1. V rámci generování databáze bylo pouţito 255 audio souborů různých ţánrů a velikostí o celkové dálce 6 hodin audio záznamu. Kaţdý soubor obsahuje vyplněný ID3 tag pouze textovými informacemi (Title, Artist, Album) a neobsahuje doplňující data, jako jsou např. obrázky.
18000
Velikost zpracovávaného souboru
Velikost souboru (kB)
16000 14000 12000 10000 8000
6000 4000 2000 1 10 19 28 37 46 55 64 73 82 91 100 109 118 127 136 145 154 163 172 181 190 199 208 217 226 235 244 253
0
Vzorek (mp3) Obrázek 6.1 Velikost zpracovávaného souboru
50
Čas spotřebovaný generování otisku
40 35 30 25 20 15 10
5 0 1 10 19 28 37 46 55 64 73 82 91 100 109 118 127 136 145 154 163 172 181 190 199 208 217 226 235 244 253
Doba generování (s)
45
Vzorek (mp3) Obrázek 6.2 Čas spotřebovaný generováním otisku
37
Z grafů na obrázcích 6.1 a 6.2 je patrná silná závislost času, který je potřebný k vygenerování jednoho audio otisku, na velikosti zpracovávaného souboru. Jednotlivé grafy jsou svojí charakteristikou průběhu téměř totoţné. Z obou grafů lze tedy vyčíst i teoretický čas potřebný k vygenerování audio otisku mp3 souboru o konkrétní velikosti. Na konci testu byla vygenerována kompletní databáze metadat čítající 255 různých skladeb. V průběhu testu byly zaznamenávány statistické hodnoty, jejichţ výsledky jsou obsahem následující tabulky: Popis
Hodnota
Celkový čas běhu: Počet zpracovaných mp3: Průměrný čas zpracování jedné mp3: Celkový počet zpracovaných framu: Průměrný počet framu na jedenu mp3: Celková velikost zpracovávaných souboru: Průměrná velikost jednoho souboru:
1h 11min 5s 255 16,7 s 2 164 119 8 487 1 219 MB 4,8 MB
Tabulka 6.1 Generátor databáze, výsledky
6.5
Šum
Šum jako takový se v širším slova smyslu dá chápat jako zvukové nebo hlukové znečištění. V různě zaměřených oborech je moţné jej chápat odlišně, ale obecně se jedná o neţádoucí nespojitý náhodný signál. Akustický šum většinou vzniká nedokonalostí nahrávacího nebo reprodukčního zařízení a je integrován do výstupního audia. Šumy je moţné dělit podle jejich světlosti na šum bílý, růţový, hnědý. Právě tyto tři druhy akustického šumu byly pouţity v tomto testu, který je zaměřen na zjištění, jaký vliv má příměs neţádoucího signálu na výsledky vyhledávání. Hlavní parametr, který byl v testu monitorován, je skóre shody (viz podkap. 4.3). Pro veškeré varianty testů byl pouţit totoţný úsek audio signálu a stejná databáze čítající 255 otisků skladeb. Testy se liší pouze v druhu a intenzitě přidaného šumu, který je generován nástrojem Audacity (viz výše). Jednotka intenzity je prezentována % v rozsahu od 0% do 100% a skokem po 5%. Záznam „obsahující“ šum o intenzitě 0% je naprosto čistý vzorový úsek dat. Naopak záznam obsahující šum o intenzitě 100% je takový, kde šum jiţ zcela přehlušuje původní audio obsah. Jednotlivé testy si kladou za cíl zjistit, jak se bude systém chovat v případě částečně i silně zarušené nahrávky.
Obrázek 6.3 Bílý šum [26]
Obrázek 6.4 Hnědý šum [26]
38
Bílý šum
6.5.1
Obsah šumu je rovnoměrně zastoupen všemi frekvencemi a jeho spektrum je ploché. Název bílý šum je odvozen od analogie s bílým světlem, které je také rovnoměrně zastoupeno všemi frekvencemi. Vlastností bílého šumu je, ţe frekvenční pásma o stejné šířce mají vţdy stejnou energii. Například pásmo v rozsahu 20 Hz – 50 Hz má stejnou energii jako pásmo v rozsahu 220Hz – 250 Hz. Všech zmíněných vlastností bylo vyuţito v průběhu testování vlivu intenzity bílého šumu na výsledky vyhledávání. Bylo provedeno celkem 21 testů s audio daty o jeho různé hodnotě na pozadí. Šum od 5% do 15% je výrazně slyšitelný, ale pro posluchače stále snesitelný. Intenzita šumu od 20% do 50% je pro posluchače velice nepříjemná, ale stále je moţné záznam ještě rozeznat. Výsledky testu zachycuje následující graf:
Skóre shody, Bílý šum 120
Skóre shody
100 80 60 40 20
0
Obrázek 6.5 Skóre shody, Bílý šum
Z výsledného grafu je patrná schopnost implementovaného systému rozpoznávat záznamy s intenzitou bílého šumu do 15%. Ostatní hodnoty jsou jiţ příliš nízké na to, aby mohly být prohlášeny za identifikaci audia. Skóre shody s hodnotou niţší jak 3 nelze povaţovat za identifikaci. S takto nízkou hodnotou můţe nastat i překrytí otiskem jiného audio záznamu. Záznam s 15% bílého šumu lze z pohledu poslechu povaţovat za silně zarušený. Následující tabulka obsahuje jednotlivé výsledky testu. Intenzita šumu 0% 5% 10% 15% 20% 25% 30% 35% 40% 45%
Skóre shody
Shoda
110 Shoda 61 Shoda 15 Shoda 8 Shoda 1 Překrytí 0 Neidentifikováno 2 Překrytí 1 Překrytí 2 Překrytí 2 Překrytí
39
50% 55% 60% 65% 70% 75% 80% 85% 90% 95% 100%
1 Překrytí 1 Překrytí 2 Překrytí 1 Překrytí 1 Překrytí 1 Překrytí 1 Překrytí 1 Překrytí 1 Překrytí 0 Neidentifikováno 2 Překrytí
Tabulka 6.2 Skóre shody, Bílý šum
Pozn.: Sloupec shoda informuje o tom, zda nalezená metadata odpovídala konkrétnímu otisku, nebo byla překryta jiným, v databázi uloţeným otiskem.
Růžový šum
6.5.2
Název růţového šumu je zřejmě odvozen od přechodu mezi bílým a červeným šumem. Svými vlastnostmi odpovídá poloze někde mezi těmito dvěma druhy. Jeho spektrální hustota je přímo úměrná převrácené hodnotě frekvence, tedy 1/𝑓. Poslech růţového šumu spíše neţ bílého způsobuje překrytí, nebo odfiltrování všech okolních zvuků. Tato série testů se snaţí zachytit opět vliv zvyšování intenzity zmíněného druhu šumu na výsledky vyhledávání v porovnání s výsledky předchozího scénáře.
Skóre shody, Růžový šum 120
Skóre shody
100 80 60 40 20 0
Obrázek 6.6 Skóre shody, Růžový šum
Výsledky testu jsou téměř srovnatelné s výsledky bílého šumu. Opět je patrná schopnost systému identifikovat záznamy s obsahem růţového šumu o intenzitě do 15%. Shodu nalezených metadat s originálem lze pozorovat do intenzity 25%, pak jiţ předávaná metadata neodpovídají vzorovému audiu a dochází k překrytí (viz Tabulka 6.3) otiskem, který náleţí jinému záznamu
40
v databázi. Bohuţel, i kdyţ se nalezená metadata při intenzitě šumu 20-25% shodovala se vzorovými, nelze je povaţovat za identifikaci. Hodnoty skóre jsou příliš nízké. Intenzita šumu 0% 5% 10% 15% 20% 25% 30% 35% 40% 45% 50% 55% 60% 65% 70% 75% 80% 85% 90% 95% 100%
Skóre shody
Shoda
110 Shoda 50 Shoda 22 Shoda 10 Shoda 1 Shoda 2 Shoda 1 Překrytí 2 Překrytí 1 Překrytí 1 Překrytí 2 Překrytí 2 Překrytí 1 Překrytí 1 Překrytí 0 Neidentifikováno 1 Překrytí 1 Překrytí 1 Překrytí 1 Překrytí 1 Překrytí 1 Překrytí
Tabulka 6.3 Skóre shody, Růžový šum
Pozn.: Sloupec shoda informuje o tom, zda nalezená metadata odpovídala konkrétnímu otisku, nebo byla překryta jiným, v databázi uloţeným otiskem.
6.5.3
Hnědý šum
Hnědý šum lze přirovnat k náhodnému signálu, který napodobuje zvuk Brownova pohybu. Odtud získal i barevné pojmenování hnědý. Je podobný růţovému šumu a jeho spektrální hustota je přímo úměrná převrácené hodnotě druhé mocniny frekvence, tedy 1/𝑓 2 . Různé zdroje povaţují hnědý šum jako synonymum k šumu červenému. Testování vlivu zvyšování intenzity hnědého šumu na výsledky vyhledávání zachycuje následující graf. Opět jako v předchozích dvou testovacích scénářích bylo provedeno celkem 21 testů s audio daty lišících se pouze v intenzitě šumu. V kaţdém testu byl pouţit shodný vzorek audio dat.
41
Skóre shody, Hnědý šum 120
Skóre shody
100 80 60 40 20
0
Obrázek 6.7 Skóre shody, Hnědý šum
Výsledný graf je svým průběhem velice podobný předchozím dvěma, ale po bliţším zhodnocení výsledků (viz Tabulka 6.4) je zřetelné částečné zlepšení úspěšnosti rozpoznávání. Vliv na toto zlepšení mají jistě vlastnosti hnědého šumu a také fakt, ţe šum není na pozadí nahrávky tolik intenzivní a překrývá spíše niţší frekvence audia. Intenzita šumu 0% 5% 10% 15% 20% 25% 30% 35% 40% 45% 50% 55% 60% 65% 70% 75% 80% 85% 90% 95% 100%
Skóre shody 110 105 63 32 9 4 3 1 1 3 1 2 1 1 2 2 1 1 2 1 1
Shoda Shoda Shoda Shoda Shoda Shoda Shoda Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí Překrytí
Tabulka 6.4 Skóre shody, Hnědý šum
42
Pozn.: Sloupec shoda informuje o tom, zda nalezená metadata odpovídala konkrétnímu otisku, nebo byla překryta jiným, v databázi uloţeným otiskem.
Vzorkovací frekvence
6.6
Vzorkovací frekvence je při digitalizaci spojitého analogového signálu chápána jako počet vzorků zpracovávaného signálu za jednu sekundu. Čím vyšší frekvence, tím kvalitnější digitální audio, ale také vyšší počet informací popisujících jednu sekundu záznamu. Účelem tohoto testu je zjistit, jaký vliv má změna této frekvence na výsledky vyhledávání. Vzorový audio úsek je vzorkován frekvencí 44,1 kHz a originální záznam obsaţen v databázi taktéţ.
Skóre shody, Vzorkovací frekvence 120
Skóre shody
100 80
60 40
20 0 44100Hz
32000Hz
22050Hz
16000Hz
11025Hz
8000Hz
Obrázek 6.8 Skóre shody, Vzorkovací frekvence
Výsledky testování jednoznačně prokazují, ţe sniţování vzorkovací frekvence má silně negativní vliv na vyhledávání metadat v databázi. Jiţ před začátkem testování se předpokládalo, ţe změna vzorkovací frekvence bude mít na vyhledávání negativní vliv. Jedním z návrhů moţného řešení této situace by bylo doplnění databáze o otisky pořízené z totoţných audio záznamů o různé vzorkovací frekvenci. Vzorkovací frekvence
Skóre shody
44100Hz 32000Hz 22050Hz 16000Hz 11025Hz 8000Hz
110 14 1 7 2 1
Shoda Shoda Shoda Překrytí Shoda Shoda Překrytí
Tabulka 6.5 Skóre shody, Vzorkovací frekvence
Pozn.: Sloupec shoda informuje o tom, zda nalezená metadata odpovídala konkrétnímu otisku, nebo byla překryta jiným, v databázi uloţeným otiskem.
43
6.7
Bitrate
Bitrate představuje datový tok, neboli kolik dat se přenáší v daném čase. Určuje kvalitu zvuku (kompresi) a obvykle se udává v jednotce kbps (kilobitů za sekundu). Originální digitální stereo záznam, jehoţ otisk je uloţen v databázi, má hodnotu bitrate 128kbps a vzorkovací frekvenci 44,1 kHz, stejně tak i vzorový stereo úsek audia. Test se zabývá vlivy sniţení datového toku na výsledky vyhledávání metadat.
Skóre shody, Bitrate 120
Skóre shody
100 80 60 40 20 0
Obrázek 6.9 Skóre shody, Bitrate
Z výsledků tohoto testu je zřejmé, ţe hodnota bitrate nemá výrazný dopad na skóre shody oproti předchozím testům. Přitom změna kvality reprodukovaného audia jednotlivých vzorků je dost výrazná. V průběhu testu dochází v 9 z 10 sub testů k jednoznačné identifikaci a shodě metadat (viz Tabulka 6.6). Bitrate
Skóre shody
128kbps 112kbps 96kbps 80kbps 64kbps 56kbps 48kbps 40kbps 32kbps 24kbps
110 94 78 62 61 47 47 18 8 1
Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Překrytí
Tabulka 6.6 Skóre shody, Bitrate
Pozn.: Sloupec shoda informuje o tom, zda nalezená metadata odpovídala konkrétnímu otisku, nebo byla překryta jiným, v databázi uloţeným otiskem.
44
Zesílení signálu
6.8
Test zesílení signálu si klade za cíl simulovat změnu hlasitosti a také zjistit vliv intenzity signálu na výsledky vyhledávání. V průběhu testu byl vzorek audio dat postupně zesilován krokem 0,5 dB aţ do hodnoty 10 dB. Na výsledném grafu je vidět, jak se hodnota skóre shody postupně sniţuje. Dodatečně byly provedeny ještě dva testy a to pro zesílení 15 dB a 20 dB. Tyto dva testy byly provedeny za účelem zjištění, jak se bude hodnota skóre dále vyvíjet. Zesílené audio je při těchto hodnotách jiţ dost znehodnocené a s ořezanými vysokými frekvencemi, kde převládají spíše basy.
Skóre shody, Zesílení signálu 140
Skóre shody
120
100 80 60 40 20 20dB
15dB
10dB
9,5dB
9,0dB
8,5dB
8,0dB
7,5dB
7,0dB
6,5dB
6,0dB
5,5dB
5,0dB
4,5dB
4,0dB
3,5dB
3,0dB
2,5dB
2,0dB
1,5dB
1,0dB
0,5dB
0,0dB
0
Obrázek 6.10 Skóre shody, Zesílení signálu
Hodnota skóre se v průběhu testu postupně sniţuje asi stejně tak, jak se sniţuje kvalita audia jeho zesilováním. Jednotlivá zesílení aţ do hodnoty 5 dB nejsou pro posluchače příliš zřetelné, ale přidaná hodnota následujících zesílení výrazně sniţuje kvalitu audia ořezáváním maxim vysokých frekvencí a tím tak sniţuje i výsledky vyhledávání (viz Obrázek 6.11 - Spektrum originálního audia vs. Obrázek 6.12 - Spektrum zesílení audia o 10dB). Zesílení 0,0dB 0,5dB 1,0dB 1,5dB 2,0dB 2,5dB 3,0dB 3,5dB 4,0dB 4,5dB 5,0dB 5,5dB
Skóre shody 110 108 93 118 108 93 98 99 94 95 79 71
Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda
45
6,0dB 6,5dB 7,0dB 7,5dB 8,0dB 8,5dB 9,0dB 9,5dB 10dB 15dB 20dB
58 60 29 28 33 21 17 15 6 5 1
Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Shoda Překrytí Překrytí
Tabulka 6.7 Skóre shody, Zesílení signálu
Pozn.: Sloupec shoda informuje o tom, zda nalezená metadata odpovídala konkrétnímu otisku, nebo byla překryta jiným, v databázi uloţeným otiskem.
Obrázek 6.11 Spektrum originálního audia
Obrázek 6.12 Spektrum zesílení audia o 10dB
6.9
Doba vyhledávání
V průběhu všech prováděných testů, na mobilních telefonech, byl pořizován záznam spotřebovaného času k vyhledání metadat pro kaţdý telefon. Z těchto záznamů byla vypočtena průměrná doba trvání jednoho vyhledávacího procesu. Mobilní telefon za účelem vyhledávání generuje vţdy otisk v podobě 256 sub-otisků ze zkoumaných dat (viz podkap. 4.3). Proces vyhledávání není tedy nijak závislý na velikosti zpracovávaného souboru. Jednotlivé výsledky obsahuje následující tabulka: Telefon
Průměrná doba procesu
Mobilní telefon 1: 50s Mobilní telefon 2: 166s Tabulka 6.8 Průměrná doba vyhledávání
46
6.10
Zhodnocení výsledků testů
Z jednotlivých testů plyne, ţe největší negativní vliv na výsledky má obsah šumu na pozadí audia a nízká vzorkovací frekvence. Tyto výsledky se daly očekávat, neboť v případě šumu je originální spektrum audia od intenzity šumu 20% z velké části překryté. Vzorkovací frekvence naopak sniţuje mnoţství informací na 1s audia záznamu a i tady se v rámci principu generování otisků dá očekávat ne příliš pozitivních výsledků. Za účelem zlepšení vyhledávání je moţné databázi doplnit otisky audia o stejném obsahu, ale převzorkovaných na niţší frekvenci nebo bitrate. Výsledky doby vyhledávání jednotlivých metadat na mobilních telefonech jsou závislé na výkonu HW, neboť jsou výpočetně velmi náročné. Jejich optimalizace je navrţena v závěru.
47
Závěr
7
Cílem práce bylo seznámit se s platformou Android, především s SDK a NDK. Dále studium dostupné literatury, týkající se extrakce vhodných příznaků ze zvukových záznamů a návrh systému zpracování těchto příznaků společně s verifikací metadat audio souborů. V rámci splnění poţadavků zadání a demonstraci zvládnuté problematiky byla navrţena a naprogramována mobilní testovací aplikace s názvem FingerDemo, která z audio (mp3) souboru extrahuje vhodné příznaky, ze kterých vytvoří a zašle binární otisk na server k vyhledání metadat v databázi. Za tímto účelem byly navrţeny a implementovány nedílné součásti projektu a to vlastní databáze systému, generátor audio otisků plnič (generátor) databáze a také server společně s komunikačním protokolem. Implementace všech částí je provedena v jazyce Java k zachování vysoké přenositelnosti celého systému. Práce pro mě byla velice zajímavá a v mnoha okamţicích zábavná. Přinesla mi mnoho nových poznatků a praktických zkušeností hlavně v oblasti zpracování signálů a audio souborů. Hlavní přínos práce vidím v moţnostech vyuţití navrhovaného systému v mnoha projektech zabývajících se přehráváním nebo zpracováním digitální hudby.
7.1
Možnosti rozšíření a pokračování v práci
Práce si mimo výše zmíněné klade také za cíl moţnost integrace systému do mobilních aplikací typu MP3 přehrávač a jiných podobně zaměřených hudebních aplikací. Z tohoto hlediska by bylo vhodné následující rozšíření:
Rozšíření generátoru databáze. Jednou z moţností rozšíření by bylo vhodné implementovat generátor také v podobě mobilní sluţby běţící na pozadí s moţností integrace do libovolného mp3 přehrávače. Tato sluţba by v případě přehrávání audia vygenerovala jeho otisk a odeslala na server ke zjištění, zda jiţ databáze vzorek obsahuje. V případě negativní odezvy by byl na server odeslán kompletní audio otisk společně s metadaty k doplnění databáze.
Podpora více audio formátů. Systém je navrţen pro generování otisků a vyhledávání metadat pouze mp3 audio souborů. K robustnosti systému by jistě přispělo rozšířit systém i pro více audio formátu.
Podpora, integrace a vyuţití i jiných systémů audio otisků. V případě komplexnosti systému by stálo za zváţení rozšíření o podporu jiţ existujících databází audio otisků.
7.2
Optimalizace
Z výsledků testování zaměřeného na čas spotřebovaný při generování otisků a také při profilování aplikace prováděného na mobilních telefonech bylo zjištěno, ţe nejnáročnější částí na výpočetní výkon je Fourierova transformace. Proto jako její optimalizaci navrhuji zefektivnění výpočtu implementací a také všech kritických částí aplikace pomocí nativního kódu jazyka C++ a vyuţití NDK systému Android. To i za cenu moţného sníţení přenositelnosti aplikace.
48
8
Literatura
Monografie [1]
MURPHY, Mark, L. Android. Computer Press, a.s., Brno, 2011. ISBN 978-80-251-31947.
[2]
HEROUT, Pavel. Učebnice jazyka Java. Kopp nakladatelství, České Budějovice, 2007. ISBN 978-80-7232-323-4.
[3]
SPELL, Brett. Java. Programujeme profesionálně. Computer Press, Praha, 2002. ISBN 80-7226-667-5.
[4]
HORTON, Ivor. Java 2. Neocortex, spol.s.r.o., Praha, 2003. ISBN 80-86330-12-5.
Elektronické zdroje [5]
Vyvíjíme pro Android – úvod. [online]. ABC Linuxu. Aktualizováno 2011-03-16 [cit.2011-12-10]. Dostupné na URL:
[6]
Hacker, Scott. MP 3: The Definitive Guide. [online]. O’Reilly, Online Catalog. Aktualizováno 2000-03. [cit.2011-12-10]. Dostupné na URL: < http://oreilly.com/catalog/mp3/chapter/ch02.html>
[7]
The Audience Is Informed. Low Tech History. [online]. ID3v2 The Audince is informed. Aktualizováno 2006-12-17 [cit. 2011-12-10] Dostupné na URL:
[8]
The Audience Is Informed. Welcome. [online]. ID3v2 .The Audience is informed. Aktualizováno 2010-11-20 [cit. 2011-12-10] Dostupné na URL:
[9]
Id3v2 tag structure. [online]. Everything2. Aktualizováno 2001-10-26 [cit. 2011-12-12] Dostupné na URL: < http://everything2.com/title/id3v1+tag+structure>
[10]
The Audience Is Informed. [online]. ID3v2 the Audience is Informed. Aktualizováno 2000-11-01[cit. 2011-12-10] Dostupné na URL:
[11]
Fourierova transformace v 1D a 2D. Hlaváč, Václav. České vysoké učení technické v Praze. [online]. [cit. 2011-12-12] Dostupné na URL:
49
[12]
Transformace signálu - diskrétní Fourierova transformace, spektrum signálu, FFT, Ztransformace. [online]. Aktualizováno 2010-11-24 [cit. 2011-12-12] Dostupné na URL:
[13]
(Diskrétní) Fourierova transformace. [online]. [cit. 2011-12-12] Dostupné na URL:
[14]
Harmonická analýza. [online]. Noţka. [cit.2011-12-13] Dostupné na URL:
[15]
Android Developers. [online]. Android developers. [cit.2011-12-16] Dostupné na URL:
[16]
Download the Android NDK. [online]. Android developers. Aktualizováno 2011-11 [cit. 2011-12-16] Dostupné na URL: < http://developer.android.com/sdk/ndk/index.html>
[17]
Java ID3 Tag Library. [online]. Java ID 3 Tag Library. Aktualizováno 2005-06-13 [cit. 2011-12-18] Dostupné na URL: < http://javamusictag.sourceforge.net/>
[18]
J Transforms. [online]. Piotr Wendykier. [cit.2012-01-06] Dostupné na URL:
[19]
Android by mohl do konce října dosáhnout 1 milionu aktivací denně. [online]. Android market.cz Aktualizováno 2011-10-05 [cit. 2012-01-06] Dostupné na URL:
[20]
Budoucnost systému Android. [online]. Knebl-mobil-servis. Aktualizováno 2011-05-17 [cit. 2012-01-07] Dostupné na URL:
[21]
Audio Fingerprint Generation. [online]. Connexions. Aktualizováno 2006-12-22 [cit. 2012-01-07] Dostupné na URL:
[22]
Mášláň, Stanislav. Rychlá Fourierova transformace (FFT) pro AVR. [online]. Aktualizováno 2012-02-28 [cit. 2012-04-26] Dostupné na URL:
50
[23]
A simple, unbounded hashtable for Java. [online]. MegaMap. Aktualizováno 2005-01-27 [cit. 2012-05-02] Dostupné na URL:
[24]
Haitsma, Jaap.; Kalker, Ton. A Highly Robust Audio Fingerprinting. 2002. [online]. [cit. 2012-05-03] Dostupné na URL:
[25]
OI File Manager. [online]. Open Intents. [cit. 2012-05-13] Dostupné na URL:
[26]
Šum. [online]. Slovník MIDI. Aktualizováno 2007 [cit. 2012-05-15] Dostupné na URL:
[27]
Barvy šumu. [online]. Wikipedie. Aktualizováno 2012-02-02 [cit. 2012-05-16] Dostupné na URL: < http://cs.wikipedia.org/wiki/Barvy_%C5%A1umu>
[28]
Audacity. [online]. Audacity. Aktualizováno 2012-02-02 [cit. 2012-05-16] Dostupné na URL:
51
A
Obsah DVD
Obsah přiloţeného DVD:
Soubor: dp.pdf Obsahuje text technické zprávy diplomové práce.
Adresář: application\databaseGenerator Obsahuje přeloţený a spustitelný kód generátoru databáze (.jar).
Adresář: application\fingerDemo Obsahuje přeloţený a spustitelný kód demonstrační aplikace FingerDemo (.apk).
Adresář: application\server Obsahuje přeloţený a spustitelný kód serverové části (.jar).
Adresář: source\FingerDemo Obsahuje zdrojové kódy demonstrační aplikace FingerDemo, včetně projektových souborů vývojového prostředí Eclipse.
Adresář: source\FingerProject Obsahuje balíky se zdrojovými kódy audio otisku (otisk), generátoru databáze (reader), databáze (database) a serveru (Server), včetně projektových souborů vývojového prostředí Eclipse.
Adresář: source\doku Obsahuje zdrojový soubor technické zprávy.
Adresář: javadoc\FingerDemo Obsahuje dokumentaci zdrojového kódu demonstrační aplikace FingeDemo generovanou pomocí nástroje javadoc.
Adresář: javadoc\FingerProject Obsahuje dokumentaci zdrojového kódu celého projektu generovanou pomocí nástroje javadoc.
Adresář: database Obsahuje vygenerovanou testovací databázi společně se seznamem 255 audio skladeb obsaţených v databázi otisků.
Adresář: poster Obsahuje prezentační plakátek práce.
52
B
Návod
Tento návod předpokládá, ţe na počítači, kde budou spouštěny jednotlivé aplikace, bude nainstalován operační systém Wndows XP nebo Windows 7 a prostředí Java. Na přiloţeném DVD se nachází následující dvojice adresářů application\databaseGenerator, application\server se spustitelnými soubory generátoru databáze a obsluhujícího serveru. Adresář application\fingerDemo obsahuje instalační balík demonstrační aplikace pro mobilní telefony s operačním systémem Android minimální verze 2.2.
B.1
Generování databáze
V případě, ţe se rozhodneme nevyuţít přiloţené databáze, je v prvním kroku třeba generovat databázi vlastní. K tomu slouţí generátor databáze umístěný v adresáři application\databaseGenerator. Spouštění aplikace se provádí pomocí příkazového řádku s následujícím seznamem ovládacích parametrů: argument1 (args[0]) readDir4T readFile4T help
argument2 (args[1]) „audioDirectoryPath“ „audioFilePath“
popis - načte obsah celého adresáře - načte konkrétní soubor - vyvolání nápovědy
Tabulka B.1 Generátor databáze, ovládací parametry
Generátor se spouští dávkou java –jar generator.jar . Aplikace ihned po svém spuštění vytvoří automaticky ve svém kořenovém adresáři, odkud byla spuštěna, adresářovou poloţku \data, která po dokončení procesu generování bude obsahovat výslednou databázi.
Obrázek B.1 Příklad spuštění
53
B.2
Server
Server slouţí zejména ke zpřístupnění databáze otisků jednotlivým klientům, a proto před pouţitím demonstrační aplikace FingerDemu musí být spuštěn. Spuštění se provádí pomocí příkazové řádky dávkou java –jar server.jar <port>. Aplikace je umístěna v adresáři application\server. Před spuštěním je třeba zajistit, aby kořenový adresář, odkud je server spouštěn, obsahoval databázi otisků v podobě vygenerovaného adresáře \data. Po ukončení práce je třeba server ukončit klávesovou zkratkou CTRL+C!
Obrázek B.2 Příklad spuštění
B.3
FingerDemo
Demonstrační aplikace FingerDemo obsaţená v adresáři application\fingerDemo má klasickou podobu instalačního balíků (.apk) systému Android. Jeho instalace na telefon je zcela v reţii operačního systému a tedy stačí jen potvrdit instalační upozornění. Aplikace ke svojí práci potřebuje přístup k síti (resp. k serveru). Před spuštěním vyhledávání metadat ke zvolené mp3 je vhodné ověřit síťové nastavení skrývající se pod ikonkou s motivem ozubeného kolečka. UPOZORNĚNÍ: FingerDemo k výběru mp3 souborů vyuţívá sluţeb externí aplikace OI File Manager (viz [25]). Před spuštěním je třeba správce souborů nainstalovat, pokud není jiţ součástí telefonu, např. staţením z Google play.
54
Obrázek B.3 Spuštění a nastavení sítě
Obrázek B.4 Výběr souboru a spuštění vyhledávání
55
C
Seznam zkratek
J2SE - Java 2 Standart Edition CPU - Central Processing Unit WiFi - Wireless LAN LAN - Local Area Network AP - Access Point IP - Internet Protocol TCP - Transmissing Control Protocol GPRS - General Packet Radio Service API - Aplication Programming Interface GUI - Graphical User Interface PDA - Personal Digital Assistant AVD - Android Virtual Device FFT - Fast Fourier Transform LUT - Lookup Table USB - Universal Serial Bus RAM - Random Access Memory DFT - Discrete Fourier Transform NDK - Native Development Kit SDK - Software Development Kit MPEG - Motion Picture Experts Group
56
