Prezentační vrstva pro exploraci multimediálních kolekcí

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

DIPLOMOVÁ PRÁCE

Bc. Miroslav Macík Prezentační vrstva pro exploraci multimediálních kolekcí Katedra softwarového inženýrství

Vedoucí diplomové práce: RNDr. Jakub Lokoč, Ph.D. Studijní program: Informatika Studijní obor: Softwarové systémy

Praha 2015

Prohlašuji, že jsem tuto diplomovou práci vypracoval samostatně a výhradně s použitím citovaných pramenů, literatury a dalších odborných zdrojů. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona v platném znění, zejména skutečnost, že Univerzita Karlova v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle §60 odst. 1 autorského zákona.

V . . . . . . . . dne . . . . . . . . . . . .

Podpis autora

i

Název práce: Prezentační vrstva pro exploraci multimediálních kolekcí Autor: Bc. Miroslav Macík Katedra: Katedra softwarového inženýrství Vedoucí diplomové práce: RNDr. Jakub Lokoč, Ph.D., Katedra softwarového inženýrství Abstrakt: Multimediální explorace se zaměřuje na problém vyhledávání v multimediálních kolekcích, kdy data nejsou anotovaná, uživatel neví, jak formulovat dotaz, nemá vzorová data anebo se chce rychle seznámit s charakteristikou kolekce. Součástí explorace je také prezentace výsledků, na kterou se tato práce zaměřuje. Vztahy mezi obrázky ve výsledcích explorace jsou transformovány do grafu, který je vizualizován pomocí fyzikálního modelu částic. Aby bylo možné vizualizovat velké množství obrázků, je nutné výpočet optimalizovat. V práci jsou popsány jak optimalizace základních algoritmů, tak i jejich úprava pro potřeby multimediální explorace. Výpočet rozložení je možný ve 2D nebo 3D prostoru. Klíčová slova: prezentační vrstva, multimediální explorace, fyzikální model pohybu částic

Title: Presentation Layer For Multimedia Exploration In Multimedia Collections Author: Bc. Miroslav Macík Department: Department of Software Engineering Supervisor: RNDr. Jakub Lokoč, Ph.D., Department of Software Engineering Abstract: Multimedia exploration is addressing the issue of searching within multimedia collections where the data is not annotated, the user is not able to formulate the text query, does not have any example data or wants to get quickly acquainted with the features of the collection. Part of the exploration is also the presentation of the results which is the main contribution of this thesis. The relations between the pictures in the exploration results are transformed into a graph which is visualised through a particle physics model. To visualize a large number of pictures, it is necessary to optimize the calculation. This thesis describes the optimization of both the basic algorithms and their adaptations for the need of multimedia exploration. The calculation layout is available in 2D and 3D space. Keywords: Presentation layer, Multimedia exploration, Particle physics model

ii

Děkuji mému vedoucímu práce RNDr. Jakubovi Lokočovi, Ph.D., rodině, Kateřině Hupákové a přátelům.

iii

Obsah Úvod Přínosy práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 6

1 Problematika a motivace 1.1 Multimediální explorace . . . . . . . . . . . . . . . . . . . . . . . 1.2 Grafy a multimediální explorace . . . . . . . . . . . . . . . . . . . 1.3 Vizualizace grafů . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7 8 8

2 Související práce

10

3 Vykreslování grafu 3.1 Fyzikální model pohybu částic . . . . . . . . . . . . . . . . . . . . 3.1.1 Základní algoritmus . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Adaptivní délka kroku . . . . . . . . . . . . . . . . . . . . 3.2 Klastrování částic . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Barnesův a Hutův algoritmus . . . . . . . . . . . . . . . . 3.3 Vícevrstvý algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Rozdělení grafu na vrstvy . . . . . . . . . . . . . . . . . . 3.3.2 Výpočet vhodného rozložení pro nejnižší vrstvu . . . . . . 3.3.3 Propagování pozic do vyšších vrstev a dopočítávání rozložení 3.4 Gravitace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Vykreslování grafu ve 3D . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Barnesovo a Hutovo kritérium ve 3D prostoru . . . . . . . 3.6 Srovnání použitých algoritmů . . . . . . . . . . . . . . . . . . . . 3.6.1 Fixní čas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.2 Dle času potřebného k dosažení kvalitní vizualizace . . . . 3.6.3 Dle velikosti grafu . . . . . . . . . . . . . . . . . . . . . . .

11 11 12 13 14 14 19 20 22 22 24 25 25 26 26 27 30

4 Využití pro multimediální exploraci 4.1 Úprava Fruchtermanova–Reingoldova algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Prořezávání hran . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

5 Implementace 5.1 Nastavení a parametry . . . . 5.2 Příklad použití . . . . . . . . 5.3 Fáze algoritmu . . . . . . . . 5.3.1 Inicializace . . . . . . . 5.3.2 Výpočet rozložení . . . 5.3.3 Vydání výsledku . . . 5.4 Testovací prostředí . . . . . . 5.5 Napojení na explorační portál

36 37 39 39 40 40 41 41 42

. . . . . . . .

1

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

32 33

6 Webový klient 6.1 Realizace . . . . . . . . . . . . . 6.1.1 Three.js . . . . . . . . . 6.1.2 Formát dat . . . . . . . 6.2 Napojení na explorační portál . 6.2.1 Komunikace se serverem 6.3 Ukázka . . . . . . . . . . . . . .

. . . . . .

45 45 45 45 46 46 47

Závěr Možná rozšíření . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48 50

Seznam použité literatury

51

Seznam obrázků

54

Přílohy

55

2

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Úvod V rostoucím množství multimediálních dat (obrázků, videí a dalších) je stále těžší zprostředkovat kvalitní vyhledávání pomocí zadaného textu (text query), neboť velká část dat postrádá anotaci či jiné označení. Z těchto důvodu se začal výzkum ubírat směrem k vyhledávání dle obsahu (z anglického content based ), které namísto klasického hledání dle anotace (metadat; jako jsou popis či klíčová slova) používá informace obsažené přímo v obrázku, tedy například barvy, textury a tvary. Výhodou tohoto přístupu je nezávislost na anotaci, která nemusí být vůbec obsažena anebo může být chybná; právě zde by klasické vyhledávání selhalo. Navíc neorganizované ruční anotování lidmi vede k neuniformním a nestrukturovaným datům a hrozí také opomenutí některého z klíčových slov či popisu. Pro vyhledávání v kolekcích multimediálních dat se jako vhodná alternativa k textovému vyhledávání nabízí vyhledávání pomocí vzorových dat, konkrétně u obrázků například vyhledávání podobných obrázků k obrázku, který dodal uživatel. Tento způsob již některé vyhledávače v dnešní době nabízí. Oba přístupy se však potýkají se stejným problémem: neumí pomoci uživateli, jež chce vyhledat obrázek, který si pouze představuje (například jej někde viděl), případně neumí dobře specifikovat vyhledávací dotaz. Jednou z obecných formulací tohoto problému může být, že chceme ve velmi velké kolekci obrázků najít jeden specifický, který víme, že je v ní někde umístěn. A nemusí se jednat o jeden konkrétní obrázek, ale můžeme chtít také najít všechny obrázky, které mají společný nějaký rys (například všechny obrázky, na nichž je moře). Řešení výše zmíněných problémů nabízí multimediální explorace, která je založena na vyhledávání dle obsahu, ale zároveň umožňuje uživateli udělat si v krátkém čas představu o datech obsažených v kolekci a současně i v datech rychle vyhledávat. Díky těmto vlastnostem je velmi vhodná, pokud uživatel není schopen formulovat explicitní vyhledávací dotaz. Na rozdíl od klasického vyhledávání uživatel postupně vybírá relevantní objekty, a tím zužuje svůj výběr. Vyhledávání tedy probíhá v několika krocích, ve kterých uživatel prochází podmnožinami kolekce a vybírá vhodné objekty. Multimediální explorace nabízí uživateli v každém kroku podmnožinu objektů z celé kolekce, a proto je pro její fungování důležitá také kvalita tohoto zobrazení. Zatímco nejjednodušším řešením je zobrazit objekty za sebou, jako lepší řešení se nabízí uspořádat objekty tak, aby jejich rozložení vyjadřovalo podobnost mezi objekty. K tomuto účelu využijeme grafů: obrázky budou reprezentovány vrcholy a ohodnocené hrany budou vyjadřovat míru podobnosti mezi obrázky. Takto získáme úplný graf vyjadřující podobnosti mezi všemi obrázky.

3

Obrázek 1: Ukázka vizualizace podobnostního grafu s 20 obrázky. Tato práce si klade za cíl vytvořit komponentu pro výpočet rychlého a kvalitního rozložení podobnostních grafů ve 2D a 3D prostoru, přičemž tyto grafy reprezentují výsledek multimediální explorace. Více se této problematice věnuje úvodní kapitola, která obsahuje detailnější seznámení s multimediální explorací a popisuje existující metody vizualizace grafů, včetně metody nazývané jako fyzikální model částic, která je použita i v této práci. Druhá kapitola zmiňuje související práce, které se týkají jak vizualizací grafů, tak i multimediální explorace. Podrobné informace o vykreslování grafů pomocí fyzikálního modelu částic nabízí třetí kapitola. Na úvod jsou zmíněny a srovnány tři existující přístupy k výpočtu fyzikálním modelem a zdůvodněna volba použitého modelu. Následuje seznámení se základním algoritmem Fruchtermana a Reingolda včetně jeho možných vylepšení pomocí adaptivní délky kroku; klastrování částic kvadrantovým stromem a následného zrychlení výpočtu aplikací Barnesova–Hutova algoritmu; použitím vícevrstvého rozložení grafu, které vede k dalšímu zrychlení a kvalitnějším vizualizacím. Součástí třetí kapitoly je také zmínka o úpravě algoritmu pro 3D prostor. Poslední část této kapitoly je věnována měření a srovnání použitých technik. Rozpracována jsou měření kvality vizualizace grafu za fixní čas; porovnání, kdy je již vizualizace kvalitní a výpočet by mohl být ukončen z pohledu uživatele a z pohledu algoritmu; a měření času potřebného pro výpočet rozložení pro různé velikosti grafu.

4

Čtvrtá kapitola popisuje nutnou úpravu Fruchtermanova–Reingoldova algoritmu, neboť jeho základní verze neumožňuje používat hrany grafu různých délek, což je jeden ze základních požadavků ze strany multimediální explorace. Různé délky hran totiž reprezentují podobnosti mezi jednotlivými obrázky (tedy čím kratší hrana, tím jsou si obrázky podobnější). Kapitola uvádí upravený vzorec pro výpočet vhodného rozložení. Jelikož je podobnostní graf, který algoritmu poskytuje multimediální explorace, úplný, je nutné pro dosažených dobrých výsledků hrany prořezávat. Nejenže je díky tomu výpočet rychlejší, ale je také dosaženo lepšího rozložení. Součástí této kapitoly je také popis navrženého k-NN prořezávání, které na rozdíl od jednoduchého prořezávání garantuje pro každý vrchol zachování alespoň minimálních vazeb (hran) k okolí, a tím dosahuje lepších výsledků výsledného uspořádání. Pátá kapitola se zabývá implementací algoritmů navrhovaných v předchozích kapitolách. Na začátku je zmíněno obecné rozhraní pro algoritmy vizualizující grafy a následně jeho konkrétní implementace fyzikálním modelem částic. Dále je popsána použitá reprezentace grafů, očekávané vstupy a výstupy algoritmu, důležité pomocné třídy pro dělení prostoru (kvadrantový a oktantový strom) a vícevrstvý algoritmus. Následuje seznam všech nastavitelných parametrů třídy, které ovlivňují fungování použitých algoritmů a příklad použití třídy. Významnou částí je popis hlavních fází běhu algoritmu, které jsou v implementaci použity. Závěr patří testovacímu prostředí, které umožňuje jednoduše testovat nastavení algoritmu, a návrhu možného napojení na již existující explorační portál. Poslední šestá kapitola je věnována webovému klientu, který byl vytvořen k zobrazování výsledného rozložení grafu ve 3D prostoru. Jedná se o stránku, která kombinací základních webových technologií a knihovny určené pro zobrazování 3D grafiky v internetových prohlížečích, dokáže zobrazit obrázky v prostoru na pozicích určených vizualizačním algoritmem. Současně kapitola obsahuje i popis možného načítání dat z exploračního serveru.

5

Přínosy práce Přínosy této diplomové práce je možné shrnout do následujících bodů: • aplikace algoritmů pro výpočet rozložení obrázků multimediální explorace ve 2D prostoru a přidání možnosti vizualizovat i ve 3D, • měření a srovnání použitých optimalizačních algoritmů, • úprava vzorce Fruchtermanova–Reingoldova algoritmu pro výpočet rozložení grafů s variabilní délkou hran, • implementace k-NN prořezávání úplných podobnostních grafů, které reprezentují výsledky multimediální explorace, • naprogramování komponenty určené k výpočtu rozložení grafu na exploračním serveru, • vytvoření prostředí pro testování různých nastavení parametrů algoritmů, • vytvoření webového klienta pro zobrazení výsledného rozložení obrázků ve 3D prostoru.

6

1. Problematika a motivace Díky množství multimediálních dat, která jsou v dnešní době k dispozici, se mění i nároky na jejich vyhledávání. Klasické vyhledávače nabízí nejčastěji vyhledávání dle zadaného slovního řetězce, případně pomocí uživatelem dodaného obrázku. Vyhledávání dle obsahu (dle informací v obrázku; z anglického content based image retrieval ) je v současné době aktivně studováno, ve svých pracích se problematice věnují například Lew, Sebe, Djeraba a Jain (2006); Datta, Joshi, Li a Wang (2008). Klasické přístupy k vyhledávání naráží na problém: uživatel musí vědět, co hledá a také musí umět tento svůj požadavek dobře specifikovat vyhledávači. Pokud chce uživatel vyhledat obrázek, který si nese v hlavě, tak tyto vyhledávací přístupy selhávají.

1.1

Multimediální explorace

Multimediální explorace se snaží uživateli zprostředkovat jednoduché a zároveň efektivní procházení (tzv. explorování) velkých kolekcí multimediálních dat (v tomto případě obrázků) a vyhledávání v nich (Beecks, Skopal, Schöffmann a Seidl, 2011). Na rozdíl od výše zmíněného klasického vyhledávání však nabízí větší zapojení uživatele do vyhledávacího procesu. Uživateli je nabídnuta množina obrázků, ze které volí nejvhodnějšího kandidáta a tím zpřesňuje svůj výběr. Na úvod jsou uživateli nabídnuti zástupci celé kolekce a na základě jeho volby následně obrázky odpovídající předchozímu výběru. Uživatel tím získává zpětnou reakci (obrázky) reflektující jeho preference. V každém kroku navíc není nutné vybírat pouze jeden obrázek, ale je možné jich zvolit více (Grošup, Moško a Čech, 2015), případně se zanořovat a vynořovat v kolekci a tím upravovat vyhledávání (Moško, Lokoč, Grošup, Čech, Skopal a Lánský, 2015). Na pozadí multimediální explorace jsou používány různé indexační struktury a podobnostní modely, které musí zajišťovat rychlé získávání výsledků na základě požadavků (explorování) uživatele. Srovnáním těchto metod se zabývá práce Čecha a Grošupa (Čech a Grošup, 2015). Důležitou součástí je také vizualizace (zobrazení) výsledků. Na úspěšné vyhledávání v aktuálně zobrazené množině obrázků má jejich rozložení značný vliv. V současné době pro tyto účely již existuje explorační portál (Čech, Grošup, Kinšt, Macík a Navrátil, 2014), který pro vizualizaci využívá komponentu vytvořenou Jáchymem Touškem v rámci ročníkového projektu. Tato komponenta zvládá interpretovat výsledky explorace pro řádově desítky obrázků, a to výpočtem jejich rozložení na klientské části ve webovém prohlížeči. Ideou práce je přesunout výpočet na explorační server, který může následně prohlížeči poskytovat již vypočítané vhodné rozložení obrázků, případně předpočítá přibližné pozice a na klientské části bude dopočítán zbytek. Poměr rozložení výpočtu mezi serverem a klientem může být závislý například na aktuální serverové zátěži anebo klient může explicitně vyjádřit, že hotové rozložení potřebuje, protože sám jej vypočítat neumí. Součástí je také optimalizace výpočtu, díky které by měl zvládnout v krátkém čase najít vhodné rozložení tisíce obrázků. 7

1.2

Grafy a multimediální explorace

V kontextu multimediální explorace můžeme využít grafy jako nástroj popisující vztahy mezi obrázky, konkrétně jejich podobnosti. Pro množinu obrázků, která je v každé fázi explorace nabídnuta uživateli, známe podobnost každý s každým. Z těchto dat jsme schopni jednoduše sestrojit graf, a to tak, že: obrázky, které jsou si podobné, budou spojeny ohodnocenou hranou; navíc hodnota hrany bude odpovídat míře podobnosti těchto obrázků. Tedy obrázky, které jsou si podobné více, by se měly držet v blízkosti a vytvářet shluky. Naopak nepodobné obrázky by měly být od těchto shluků dále.

1.3

Vizualizace grafů

V obecné rovině jsou grafy výborným nástrojem pro vyjadřování vztahů mezi objekty. Nemusí se vždy jednat pouze o abstraktní model obsahující vrcholy a hrany, ale za objekty a hrany můžeme dosadit například webové stránky a odkazy vedoucí mezi nimi, fáze výrobního procesu (obecně automat), vazby na sociálních sítích anebo obrázky a jejich vzájemné podobnosti. Abychom byli schopni grafy číst, je pro nás vizualizace a její kvalita velmi důležitá.

Obrázek 1.1: Srovnání různých vizualizací stejného grafu. Uvažujme jednotlivá rozložení z Obrázku 1.1, který obsahuje tři vizualizace stejného grafu. Je zřejmé, že grafy napravo jsou čitelnější a ukazují nám strukturu dat; naopak graf vlevo je na první pohled pouze náhodným uskupením vrcholů a hran. Můžeme tedy říci – a to i přestože neexistují jasně daná kritéria vzhledu (estetiky) grafu –, že rovnoměrné rozložení vrcholů a minimální křížení hran vede ke kvalitním vizualizacím. Najít obecně takové rozložení je NP-těžký optimalizační problém (Battista, Eades, Tamassia a Tollis, 1994). V průběhu šedesátých let začala být oblast hledání vhodného rozložení grafů aktivní (Tutte, 1963). Následný výzkum vedl k několika rozličným přístupům: například přes obloukové diagramy, ve kterých jsou všechny vrcholy umístěny na jednu společnou přímku a hrany mezi nimi jsou kresleny formou oblouků (Saaty, 1964); pomocí statistické metody mnohorozměrného škálování (Kruskal a Seery, 1980); použitím kruhového rozmístění grafu (Do˘grusöz, Madden a Madden, 1997); umístěním grafu do velmi vysokých dimenzí a jeho následnou projekcí do 2D prostoru (Harel a Koren, 2002); pomocí spektrální metody (Koren, Carmel a Harel, 2003). Systém TopoLayout volí přístup rozkládání grafu na podgrafy, hledání topologických vlastností v těchto podgrafech, redukcí křížení hran a v poslední fázi eliminací překrývání vrcholů (Archambault, Munzner a Auber, 2007). 8

Velmi častým způsobem vizualizace grafů je také fyzikální model částic, kterým se zabývá i tato práce. Shrnutím různých přístupů se zabývá kniha Battisty a kol. (Battista a kol., 1998). Ideou fyzikálního modelu, jakožto modelu pro hledání vhodného rozložení grafu, je použití kroužků, které reprezentují vrcholy grafu, a pružin, které tyto kroužky spojují. Jednotlivé implementace se poté liší v rozmístění pružin a v konkrétních výpočtech, které chování systému simulují. Detailněji jsou jednotlivé implementace popsány ve třetí kapitole.

Obrázek 1.2: Intuitivní vizualizace úplného grafu o šestnácti vrcholech.

9

2. Související práce Problém vizualizace grafu se objevuje v mnoha článcích a literatuře. Každoročně je pořádána konference International Symposium on Graph Drawing. Obecně problém kreslení grafu se objevuje ve hrách již ve třináctém století, případně v kreslení rodokmenů, které bylo populární ve středověku (Kruja, Marks, Blair a Waters, 2001). Přechodem k moderním grafům byla práce Eulera (Euler, 1736), který grafy abstraktně popsal tak, jako je známe dnes. Další informace o historii vizualizace grafů lze nalézt ve společné práci Krujové a kol. (Kruja a kol., 2001). Myšlenku vizualizace grafu pomocí fyzikálního modelu částic formovali Eades (1984), Kamada a Kawai (1989) a Fruchterman a Reingold (1991). Vylepšením byla aplikace Barnesova–Hutova algoritmu (Barnes a Hut, 1986), který je používán ve fyzice pro snížení časové složitosti jedné iterace výpočtu problému n těles z kvadratické na O(n log(n)). Algoritmus použili ve svých pracích Tunkelang (1999) a následně také Quigley a Eades (2001) v projektu nazvaném fade. Dále byly tyto myšlenky rozšířeny o použití vícevrstvého rozložení grafu, které předchází uváznutí výpočtu v lokálním minimu, formované nejprve Gajerem, Goodrichem a Kobourovem (Gajer, Goodrich a Kobourov, 2000, 2004) a následně Walshawem (Walshaw, 2001). Multimediální explorace (Beecks a kol., 2011) je založena na konceptu vyhledávání dle obsahu (content based vyhledávání). Vizualizace výsledků pomocí fyzikálního modelu částic již byla použita v exploračním portálu SIR (Lokoč, Grošup a Skopal, 2012), v projektu Find The Image (Grošup, Čech, Lokoč a Skopal, 2015) anebo je použita v exploračním portálu (Čech a kol., 2014).

10

3. Vykreslování grafu V této kapitole práce se budeme zabývat samotným výpočtem rozložení grafu. K tomuto účelu používáme model označovaný jako fyzikální model pohybu částic. Nejprve uvedeme základní ideu fyzikálního modelu a následně použitá vylepšení, která vedou k rychlejšímu běhu algoritmu a lepšímu rozložení výsledného grafu. V celém textu budeme používat neorientované grafy, které budeme značit jako G = (V, E), kde V je množina vrcholů a E množina hran.

Obrázek 3.1: Ilustrace fyzikálního modelu částic.

3.1

Fyzikální model pohybu částic

Fyzikální algoritmus modeluje vizualizaci grafu pomocí působení fyzikálních sil mezi objekty. Použití fyzikálního modelu jakožto systému částic (kroužků) a pružin nejprve navrhl Eades (1984), který však nepoužíval odpudivé síly dané Hookovým zákonem, namísto toho použil vzorec, který pro každou dvojice vrcholů počítá odpudivou sílu a pro grafové sousedy naopak přitažlivou. Z toho důvodu je časová složitost v rámci jedné iterace O(|E|) pro výpočet přitažlivých sil mezi sousedy, avšak O(|V |2 ) pro výpočet odpudivých sil, které jsou počítány stylem každý s každým. Eadsův algoritmus následně upravili Kamada a Kawai (1989), kteří pro výpočet použili také pouze simulaci pružin a to tak, že pružiny byly rozmístěny mezi všemi vrcholy (každý vrchol byl pružinami spojen se všemi ostatními). Zároveň byla pružinám nastavena ideální délka, ke které se ze své povahy poté pružiny snaží přiblížit. Tato délka odpovídala vzdálenosti vrcholů v grafu. Časová složitost jedné iterace tohoto algoritmu je O(|V |2 ). Mírně odlišný přístup zvolili Fruchterman a Reingold (1991), kteří zachovali pružiny pouze mezi vrcholy, které spolu v grafu sousedí. Zároveň přidali odpudivou sílu působící mezi všemi vrcholy grafu reprezentovanou Hookovým zákonem. Jejich algoritmus má časovou složitost O(|V |2 +|E|), kterou je ale možné vylepšit aplikací Barnesova–Hutova algoritmu (Barnes a Hut, 1986), který na předchozí algoritmy aplikovat nelze, protože zrychluje pouze výpočet odpudivých sil (Hookův zákon) a nikoliv přitažlivých sil, které způsobují pružiny. Z tohoto důvodu je v práci použit algoritmus Fruchtermana a Reingolda. 11

3.1.1

Základní algoritmus

Pro nalezení vhodného rozložení grafu simulujeme pohyb částic, na které působí přitažlivé a odpudivé síly. Tím se nám změní charakter úlohy na optimalizační úlohu hledající klidový stav fyzikálního systému. Zjednodušeně můžeme říci, že všechny vrcholy budou simulovány kladně nabitými elektrickými částicemi, které se dle Coulombova zákona odpuzují, a přitažlivé síly budou působit mezi částicemi, které jsou spojeny pružinami. Základní popis nabízí Algoritmus 3.1. while !konvergence do for i ∈ V do vypočti odpudivé síly (plynoucí z působení ostatních částic); vypočti přitažlivé síly (plynoucí z částic spojených s i hranou); posuň vrchol i; end end Algoritmus 3.1: Pseudokód algoritmu pro výpočet rozložení grafu pomocí fyzikálního modelu pohybu částic. Přesněji jsou síly vyjádřeny vztahem: fr (i, j) = −CK 2 /kxi − xj k, fa (i, j) = kxi − xj k2 /K,

i 6= j, {i, j} ∈ E,

i, j ∈ V,

(3.1) (3.2)

kde fr znační odpudivou a fa přitažlivou sílu, parametr K vyjadřuje optimální vzdálenost mezi vrcholy – někdy bývá označován také jako přirozená délka pružiny (Fruchterman a Reingold, 1991) – a parametr C slouží jako regulace odpudivé síly a ve své práci jej uvádí Walshaw (2001). Zápis kxi − xj k označuje eukleidovskou vzdálenost vektorů xi a xj . V Algoritmu 3.2 parametr ε vyjadřuje minimální nutný pohyb částic v systému, při kterém se pokračuje další iterací; v opačném případě je běh algoritmu ukončen a je vydán výsledek. Proměnná xi reprezentuje pozici i-té částice v systému, s vyjadřuje koeficient délky kroku v rámci jedné iterace algoritmu. Po skončení každé iterace algoritmu je upravena hodnota proměnné s zavoláním funkce cool, která v základním algoritmu není přímo specifikována (Fruchterman a Reingold, 1991). Je ji ale možné realizovat jednoduchým vynásobením konstantou menší než jedna. Eades (1984) ve své práci tvrdí, že: Téměř všechny grafy dosáhly ” stavu energetického minima po 100 iteracích.“ Vhodnou hodnotou parametru t se ukázalo být 0,95. vyšší hodnota (například 0,99) by vedla k delšímu běhu algoritmu s plynulejším průběhem.

12

do m = 0; e = 0; for i ∈ V do f = 0; for j ∈ V do if i 6= j then f +=

fr (i,j) (xj kxi −xj k

− xi );

end end for j ∈ V ∧ {i, j} ∈ E do f +=

fa (i,j) (xj kxi −xj k

− xi );

end mi = f /kf k ∗ s; xi += mi ; m += mi ; e += kf k2 ; end s = cool(s); while m ∗ K > ε; Algoritmus 3.2: Základní algoritmus pro výpočet rozložení grafu pomocí fyzikálního modelu pohybu částic.

3.1.2

Adaptivní délka kroku

Hu (2005) uvádí vylepšení funkce cool, které je nazýváno jako adaptivní a umožňuje v určité situaci prodloužit délka kroku s. Vzhledem k tomu, že základní verze algoritmu pracuje s předpokladem náhodných startovacích pozic jednotlivých částic, je toto řešení vhodné, neboť umožňuje algoritmu opustit zaseknutí v podobě lokálního minima. return s ∗= t; Algoritmus 3.3: Základní funkce cool. Algoritmus 3.4 upravuje délku kroku stejným způsobem jako základní algoritmus (Fruchterman a Reingold, 1991). Pokud ale v pěti po sobě jdoucích iteracích klesla celková energie v systému, je délka kroku prodloužena.

13

if e < e0 then p ++; if p >= 5 then p = 0; s /= t; end end else p = 0; s ∗= t; end Algoritmus 3.4: Adaptivní délka kroku

3.2

Klastrování částic

Hlavním problémem základního algoritmu je jeho časová složitost. Z pseudokódu je zřejmé, že v rámci jedné iterace počítáme pro každý vrchol odpudivou sílu, kterou na něj působí všechny ostatní vrcholy. Proto je pro výpočet odpudivé síly mezi n vrcholy potřeba provést O(n2 ) operací (Fruchterman a Reingold, 1991). Abychom snížili časovou složitost, snažíme se tvořit z částic klastry a poté počítat odpudivou sílu pouze vzhledem ke klastrům a nikoliv ke všem částicím. Pro vyřešení tohoto problému můžeme využít metodu ve fyzice známou jako problém n těles. Obecně se tato metoda snaží vypočítat pohyb (pozice) částic, které na sebe navzájem působí (například gravitací); v základní variantě opět narážíme na kvadratickou časovou složitost O(n2 ), jsou ale známy optimalizace, které tuto složitost snižují na O(n log(n)). Jednou z nich je i Barnesova–Hutova simulace.

3.2.1

Barnesův a Hutův algoritmus

Barnesův–Hutův algoritmus (Barnes a Hut, 1986) je aproximační metodou pro výpočet pohybu n těles. Jeho hlavní výhodou je logaritmická časová složitost na rozdíl od kvadratické při výpočtu každý s každým. Základem algoritmu je rozdělení prostoru na rovnoměrné bloky a myšlenka: je-li skupina těles (částic) dostatečně vzdálená od aktuálně počítaného tělesa (částice), není nutné počítat působení sil každého s každým, ale můžeme tuto skupinu aproximovat jako jedno velké těleso (částici). Pro rozdělení částic ve 2D prostoru nám bude sloužit stromová datová struktura kvadrantový strom.

14

Kvadrantový strom Kvadrantový strom (z anglického quadtree) je datová struktura, ve které má každý uzel právě 0, 1 nebo 4 potomky. Název této struktuře dali Finkel a Bentley (1974). Strom můžeme využit k rozdělení 2D prostoru. Na každé úrovni stromu dochází k dělení na čtyři oblasti (regiony). V nejzákladnější variantě předpokládáme rovnoměrné dělení čtvercového prostoru na čtyři stejně velké čtverce. Protože se jedná o rekurzivní datovou strukturu, probíhá rekurzivní dělení dokud není v každé oblasti jeden nebo žádný prvek.

p1

p2

p3

p4

Obrázek 3.2: Rozdělení prostoru pomocí kvadrantového stromu. Pro každý uzel tedy platí, že je sám stromem, obsahuje právě jeden prvek anebo je prázdný. Dělení 2D prostoru pomocí kvadrantového stromu ilustruje Obrázek 3.2. Na Obrázku 3.3 můžeme vidět schéma tohoto stromu. Q

Q1 p1

Q2 Q

Q

Q

Q

∅

p2

p3

∅

Q3

Q4

∅

p4

Obrázek 3.3: Kvadrantový strom vytvořený rozdělením prostoru z Obrázku 3.2.

15

Na začátku se jedná pouze o prázdný strom, který obsahuje předem vymezený čtverec. Postupným přidáváním je dle potřeby čtverec štěpen a jsou vytvářeny podstromy vymezené menšími vnořenými čtverci. Obecnější varianty stromu připouští například i dělení na velikostně nerovnoměrné oblasti, případně více prvků v rámci jednoho regionu, aniž by docházelo k jeho štěpení na další podstromy. Vhodné může být neštěpit strom od určité úrovně, aby se zabránilo hlubokému štěpení v případě, že jsou dva prvky na velmi blízkých pozicích (Hu, 2005). Analogií pro kvadrantový strom ve 3D prostoru je oktantový strom (octree).

Obrázek 3.4: Kvadrantový strom pro 1000 náhodně rozmístěných bodů ve 2D prostoru.

Aplikace Barnesova–Hutova kritéria Abychom dosáhli logaritmické výpočetní složitosti, musíme vhodně rozhodovat, které prvky budeme porovnávat s konkrétními prvky a které pouze s klastry a případně s jakými (máme totiž rekurzivní dělení prostoru). K tomuto určení použijeme kritérium tolerance (Quigley a Eades, 2001), jehož základem je porovnání s/d ≤ θ,

(3.3)

kde s určuje šířku oblasti vymezenou daným kvadrantovým stromem, d vzdálenost mezi aktuálně počítanou částicí p a centrem gravitace kvadrantového stromu. 16

Parametr θ určuje porovnávací toleranci. V případě, že je podmínka (3.3) splněna, je síla působící na p vypočtena pouze vzhledem k celému klastru, který je pro výpočet uvažován jako jedna (velká) částice; v opačném případě je porovnání rekurzivně aplikováno na všechny potomky aktuálně vyhodnocovaného stromu, dokud není podmínka splněna, nebo není dosaženo listu. Na Obrázku 3.5 můžeme vidět rozhodování pomocí porovnávacího kritéria pro částici p1 , respektive p4 vzhledem ke klastru Q2 skládajícího se z částic p2 a p3 v pravém horním rohu rozděleného prostoru pomocí kvadrantového stromu.

p1

d1 Q2 d2 p4

s Obrázek 3.5: Příklad testování dle porovnávacího kritéria.

Volba parametru tolerance Na základě hodnoty parametru tolerance θ se odvíjí množství porovnání a také kvalita výsledku. Čím nižší bude hodnota tohoto parametru, tím častěji nebude splněno kritérium pro využití klastru a o to bude provedeno více porovnání s rekurzivně zanořenými menšími klastry, nebo přímo konkrétními částicemi. Nastavíme-li θ na hodnotu 0, získáme základní algoritmus s kvadratickou časovou složitostí O(n2 ), jelikož kritérium tolerance nebude nikdy splněno. Naopak budeli parametr θ příliš vysoký, algoritmus bude používat pouze velké klastry. To sice povede k rychlému výpočtu, který se bude přibližovat k lineární časové složitosti O(n), nicméně cenou za tuto rychlost bude velká nepřesnost (Quigley a Eades, 2001). Pro ilustraci můžeme nahlédnout na Obrázek 3.5 s použitím parametru θ = 1. Je zřejmé, že vzdálenost s/d1 ≤ 1. Díky tomu je splněno toleranční kritérium a odpudivá síla působící na částici p1 bude vypočtena vzhledem ke klastru Q2 , který je tvořen částicemi p2 a p3 . Naopak při výpočtu odpudivých sil působících 17

na částici p4 nebude kritérium naplněno (protože s/d2 > 1) a odpudivé síly budou rekurzivně vypočítány vzhledem ke všem potomkům klastru Q2 (v tomto konkrétním případě přímo vzhledem k částicím p2 a p3 ). Doporučená hodnota parametru bývá obecně θ ≤ 1, konkrétně 0,5 (Coole, Wernsing a Stitt, 2009) anebo 0,75 (Hamada a Nakasato, 2005). Vzhledem k vlastnímu testování a článku Hua (Hu, 2005) je v práci použita hodnota θ = 1,2, která garantuje kvalitní výsledky v dobrém čase. Úprava základního algoritmu pohybu částic Abychom rozšířili základní algoritmus o použití Barnesova–Hutova kritéria, je potřeba udělat několik úprav. Pseudokód upraveného výpočtu popisuje algoritmus 3.5. while !konvergence do sestroj kvadrantový strom; for i ∈ V do vypočti odpudivé síly (za použití Barnesova–Hutova kritéria); vypočti přitažlivé síly (plynoucí z částic spojených s i hranou); posuň vrchol i; end end Algoritmus 3.5: Pseudokód algoritmu pro výpočet rozložení grafu pomocí fyzikálního modelu pohybu částic za použití Barnesova–Hutova kritéria. V samotném výpočtu je nutné upravit výpočet odpudivé síly: fr (i, Q) = −|Q|CK 2 /kxi − xQ k, který nyní bude jako druhý parametr používat uzel kvadrantového stromu Q; pracuje tedy s celým klastrem a nikoliv pouze s jednou částicí (list stromu chápeme také jako klastr, který obsahuje pouze jednu částici). Hodnotu xQ nazveme centrem gravitace klastru Q a jeho hodnotu vypočteme vzorcem: X  xQ = xj /|Q|. j∈Q

Jak můžeme nahlédnout, je-li splněno toleranční kritérium, je výpočet odpudivých sil proveden vůči jakési superčástici, která zastupuje svou velikostí i pozicí celý klastr. Toto chování můžeme vidět na Obrázku 3.5, kde roli superčástice zastupující (na první úrovni stromu) pravý horní klastr plní superčástice Q2 .

18

Z algoritmu 3.5 také můžeme vyčíst, že kvadrantový strom budujeme vždy při startu každé iterace algoritmu a následně s jednotlivými částicemi pohybujeme. To může vést k přesunu některých částic do sousedních klastrů. Dle testování, pozorování a Hua (Hu, 2005) však nemá tento nedostatek vliv na výpočet ani na výsledek.

Obrázek 3.6: Rozložení grafu jagmesh11 (|V | = 936, |E| = 2664) pomocí fyzikálního modelu částic.

3.3

Vícevrstvý algoritmus

Přestože zavedením klastrování částic časová složitost algoritmu klesla, potýká se výpočet ještě s jedním nedostatkem, kterým je inicializační rozmisťování částic. Základní algoritmus částice rozmisťuje na náhodné pozice a poté spouští výpočet. Z tohoto důvodu se v rámci několika prvních iterací odehrávají velké přesuny, protože startovací pozice částic nerespektují žádnou charakteristiku grafu. Navíc se náhodným rozmístěním zvyšuje pravděpodobnost uváznutí v nějakém lokálním minimu výpočtu. Tyto neduhy se snaží odstranit vícevrstvý algoritmus. Základní myšlenkou je redukování grafu na jednodušší graf, pro který jsme schopni najít rozložení velmi rychle, a poté zpětné propagování těchto pozic jako výchozích pozic pro nezjednodušený graf. Vícevrstvý algoritmus má tři fáze: (a) rozdělení grafu na vrstvy (odtud plyne název algoritmu), (b) výpočet vhodného rozložení pro nejnižší vrstvu, (c) propagování pozic do vyšších vrstev a dopočítávání rozložení.

1

Matice grafu jagmesh1 pochází ze serveru MatrixMarket (http://math.nist.gov/ MatrixMarket).

19

3.3.1

Rozdělení grafu na vrstvy

Cílem této fáze je redukce vrcholů a hran v grafu tak, aby byla co nejvíce zachována jeho charakteristika. Tento postup je opakován a výsledkem jsou jednotlivé vrstvy grafu. Původní graf značíme jako G0 , jeho redukcí nám vzniká graf G1 , redukcí G1 následně graf G2 , G3 , . . . Gn . Redukce probíhá, dokud nezískáme graf Gn obsahující pouze několik málo vrcholů a hran. Možností, jak graf redukovat, je několik; ve své práci se jimi zabývali Gajer a kol. (2000, 2004) i Walshaw (2001). V práci jsou implementovány dvě mětody: jedna využívající aproximační algoritmus pro minimální vrcholové pokrytí a druhá využívající aproximační algoritmus pro maximální párování v grafu. Pomocí minimálního vrcholového pokrytí Aproximační algoritmus pro minimální vrcholové pokrytí (Algoritmus 3.6) vybere v každém kroku jeden náhodný vrchol a odstraní jej společně s jeho sousedy. Při redukci grafu Gi si evidujeme, které vrcholy byly v jednotlivých krocích vybrány – právě tyto vrcholy bude obsahovat graf Gi+1 . Hrany budou spojovat vrcholy, jejichž předchůdci (samotný vrchol a jeho sousedé) byli v původním grafu Gi spojeni. Jelikož odstraňujeme vrchol společně se všemi jeho sousedy, znamená délka cesty 2, že hrana v novém grafu Gi+1 bude mezi vrcholy, které měly společného souseda v původním grafu Gi . Zjednodušeně by se dal algoritmus popsat tak, že vrcholy společně s jejich sousedy srocujeme do zástupných vrcholů, které zachovávají vazby (hrany) z předchozího grafu.

while |V | > 0 do vyber náhodný vrchol v ∈ V ; přidej v do minimálního pokrytí grafu; odstraň všechny vrcholy w takové, že {v, w} ∈ E; odstraň vrchol v; end Algoritmus 3.6: Pseudokód aproximačního algoritmu pro minimální vrcholové pokrytí v grafu. Redukci pomocí aproximačního algoritmu pro vrcholové pokrytí můžeme vidět na Obrázku 3.7. Graf G0 je mřížka o velikosti 9x9 (a); (b) ukazuje vrcholy vybrané algoritmem, ze kterých je vytvořen graf G1 ; (c) znázorňuje další redukci vrcholů a samotný graf G2 .

20

(a)

(b)

(c)

Obrázek 3.7: Redukce grafu (mřížka 9x9) pomocí minimálního vrcholového pokrytí. Poslední obrázek obsahuje i zakreslení zredukovaného grafu G2 . Pomocí maximálního párování Druhou implementovanou metodou je redukce pomocí aproximačního algoritmu pro maximálního párování v grafu (Algoritmus 3.7). Průběh algoritmu je podobný předchozímu. Namísto vrcholu však v každém kroku vybíráme náhodnou hranu a z grafu Gi odstraňujeme vrcholy, které jsou touto hranou spojeny. Za každou tuto odstraněnou dvojici se v novém grafu Gi+1 objeví jeden vrchol. Vrcholy budou v Gi+1 spojeny hranou, pokud byli jejich předchůdci (dvojice vrcholů) v Gi spojeni hranou. Tato redukce by se dala přirovnat k postupnému provádění kontrakcí hran za předpokladu, že vrchol, který již kontrakcí hrany vznikl, nemůže být znovu v kontrakci použit.

while |E| > 0 do vyber náhodnou hranu e : {v, w} ∈ E; přidej e do maximálního párování grafu; odstraň vrcholy v a w; end Algoritmus 3.7: Pseudokód aproximačního algoritmu pro maximální párování v grafu. Výběr hran a vrcholů grafu pomocí aproximačního algoritmu pro maximální párování ukazuje Obrázek 3.8. Graf G0 je opět mřížka o velikosti 9x9 (a); (b) znázorňuje výběr hran a vrcholů pro tvorbu grafu G1 .

21

(a)

(b)

Obrázek 3.8: Redukce grafu (mřížka 9x9) pomocí maximálního párování. Jednoduše můžeme nahlédnout, že při redukci grafu pomocí první metody se bude velikost grafu (ve smyslu množství vrcholů a hran) snižovat rychleji, protože ze zvoleného vrcholu včetně jeho sousedů se přenáší do další úrovně pouze jeden vrchol; druhá metoda redukuje pouze dvojice vrcholů do vrcholu jednoho.

3.3.2

Výpočet vhodného rozložení pro nejnižší vrstvu

Další fáze algoritmu již pracuje s nejvíce zredukovaným grafem (s nejnižší vrstvou). Může se jednat pouze o jeden vrchol, přímku, trojúhelník anebo o složitější graf dle počtu provedených redukčních kroků a dle volby redukčního algoritmu. Není nutné redukovat graf na minimum (jeden vrchol). Hlavní snahou je najít vhodné startovací pozice pro částice v nejvyšší vrstvě. K tomu nám stačí, obsahuje-li nejnižší vrstva řádově jednotky až desítky vrcholů, pro které jsme schopni nalézt rozložení velmi rychle. Toto rozložení již hledáme pomocí základního algoritmu, v němž částice rozmístíme na náhodné pozice a spustíme výpočet. Po jeho skončení následuje poslední fáze, ve které propagujeme výsledek do vyšších vrstev.

3.3.3

Propagování pozic do vyšších vrstev a dopočítávání rozložení

Protože již máme hotové rozdělení grafu do jednotlivých vrstev (redukci) a známe rozložení nejnižší vrstvy, potřebujeme nyní toto rozložení propagovat do vyšších vrstev. Stejně jako jsme v první fázi postupně redukovali vrcholy a hrany, budeme je nyní v opačném případě rekonstruovat. Algoritmus 3.8 popisuje, jak probíhá přenos základního rozložení od nejnižší vrstvy Gn až k původnímu grafu G0 . Nejprve jsou do vyšší vrstvy přeneseny informace o pozicích částic v nižší vrstvě. Vrcholy, ze kterých byl v průběhu redukce vytvořen jeden vrchol, v této fázi přebírají polohu tohoto vrcholu. Konkrétně vznikl-li vrchol e∗ ∈ Gi z vrcholů e1 , e2 , . . . ek ∈ Gi−1 , pak bude těmto vrcholům nastavena iniciální pozice stejná, jako je vypočítaná pozice vrcholu e∗ . Po nastavení startovacích pozic částic pro vrstvu grafu Gi−1 je na tuto vrstvu spuštěn algoritmus hledající rozložení grafu pomocí fyzikálního modelu a celý algoritmus propagování pozic částic se opakuje.

22

Obrázek 3.9: Příklad postupné redukce grafu jagmesh1 (Obrázek 3.6) pomocí minimálního vrcholového pokrytí (vlevo) a maximálního párování (vpravo).

23

level = n; while level > 0 do nastav pozice částic v Glevel−1 dle pozic v Glevel ; najdi rozložení částic v Glevel−1 pomocí fyzikálního modelu; level −−; end Algoritmus 3.8: Pseudokód propagování pozic části do vyšších vrstev. Hledáme-li rozložení částic pro redukované vrstvy (všechny vrstvy kromě G0 ), nevyžadujeme dokonalé rozložení, ale spíše požadujeme, abychom jej dostali velmi rychle. Můžeme proto provádět výpočet s vyšším parametrem ε (viz Algoritmus 3.2).

Obrázek 3.10: Příklad uváznutí výpočtu v lokálním minimu (graf jagmesh1, viz Obrázek 3.6).

3.4

Gravitace

Aby bylo výsledné rozložení grafu kompaktní a také pro případ, že je vstupní graf řídký, je v každém kroku algoritmu pro výpočet fyzikálního modelu částic na všechny vrcholy aplikována malá síla, která vrcholy přitahuje do středu prostoru. To nám zaručí, že se jednotlivé komponenty grafu (nejčastěji osamělé vrcholy) nerozletí v prostoru a že výsledný graf má kruhový tvar.

24

3.5

Vykreslování grafu ve 3D

Algoritmus pro výpočet fyzikálního modelu částic ve 2D prostoru není těžké rozšířit o další (třetí) dimenzi. Hlavní změnou je použití oktantového stromu (anglicky octree). Další úpravy nejsou nutné a všechny ostatní části algoritmu zůstávají zachovány (viz Algoritmus 3.2).

3.5.1

Barnesovo a Hutovo kritérium ve 3D prostoru

Základem Barnesova–Hutova kritéria v předchozí kapitole byl kvadrantový strom, který čtvercový 2D prostor rozděloval na čtyři stejně velké čtverce. Jeho analogií pro 3D prostor je oktantový strom, který tento prostor rozděluje na osm stejně velkých krychlí.

p1

p2

p3 p4

Obrázek 3.11: Rozdělení prostoru pomocí oktantového stromu. Stromová reprezentace má větvící faktor osm a to v případě, že v oblasti vymezené danou krychlí leží alespoň dva objekty.

25

3.6

Srovnání použitých algoritmů

Použitá rozšíření základního Fruchtermanova–Reingoldova algoritmu mají různorodý vliv na celkovou kvalitu výpočtu. Zatímco Burnesovo–Hutovo kritérium snižuje asymptotickou časovou složitost, vícevrstvý algoritmus zabraňuje uváznutí v lokálním minimu a celkově zrychluje výpočet. Díky němu nedochází k velkým přesunům vrcholů na začátku běhu algoritmu a tím se snižuje celkový počet iterací, které musí proběhnout pro dosažení výsledného rozložení. Tato sekce si klade za cíl přiblížit vliv jednotlivých algoritmů na celkový výpočet. Základem veškerých srovnání bude 2D graf ve tvaru pyramidy, který budeme značit Pn , kde n vyjadřuje (počet pater pyramidy − 1), tedy pro n = 1 se jedná o jediný bod, n = 2 nám dává trojúhelník. Veškerá měření vychází ze základního nastavení parametrů s vypnutou gravitací; nejsou-li použity výchozí hodnoty, je tato skutečnost u měření uvedena. U všech výpočtů byla použita adaptivní délka kroku. Veškerá testování byla provedena autorem práce a to včetně hodnocení kvality výsledných rozložení (zejména při měření času potřebného k dosažení kvalitní vizualizace).

3.6.1

Fixní čas

V první části budeme pracovat s grafem P30 (|V | = 465, |E| = 1305), jehož vizualizace byla spuštěna vždy přesně na 400 ms. Po uplynutí této doby byla dokončena aktuálně probíhající iterace algoritmu a byl vydán výsledek. Délka kroku (Step) byla nastavena na hodnotu 0,6 a koeficient snižování délky kroku (StepResizeCoef ) na 0,95. Obrázky 3.12 nám nabízí srovnání výsledků. První vizualizace (a) byla počítána pouze za pomoci základního Fruchtermanova–Reingoldova algoritmu. Je zde možné pozorovat negativní projev náhodného rozmístění částic při startu vizualizace. Vizualizace je po uplynutí času velmi nekvalitní a není vůbec čitelná. Druhý obrázek (b) ukazuje výsledek vizualizace s použitím Barnesova–Hutova algoritmu. Na tomto výsledku je již vidět formování struktury grafu, avšak stále je patrná nevýhoda náhodného rozmístění částic při inicializaci. Třetí obrázek (c) zobrazuje vizualizaci, která k výpočtu sil používá základní algoritmus a k němu pomocí vícevrstvého rozložení grafu nejprve vypočítá startovací pozice jednotlivých vrcholů. Na této vizualizaci již můžeme vidět přibližování se k výslednému tvaru grafu, avšak rozložení vrcholů ještě není optimální a rovnoměrné. Poslední obrázek (d) ukazuje aplikaci jak Barnesova–Hutova kritéria, tak i vícevrstvého algoritmu. Vizualizace je již kvalitní, ve středu můžeme pozorovat hotovou strukturu grafu a chybí dopočítat pouze rozložení cípů trojúhelníku.

26

(a) Základní algoritmus.

(b) Barnesovo–Hutovo kritérium.

(c) Vícevrstvý algoritmus.

(d) Barnesovo–Hutovo kritérium v kombinaci s vícevrstvým algoritmem.

Obrázek 3.12: Srovnání kvality vizualizací po 400 ms výpočtu.

3.6.2

Dle času potřebného k dosažení kvalitní vizualizace

Druhé srovnání se zaměřuje na čas, který potřebují jednotlivé metody k získání kvalitního intuitivního rozložení grafu. Pro testování používáme opět graf P30 , vzdálenostní koeficient ε (DistanceCoef ) nastavený na hodnotu 60, délku kroku na 0,6 a koeficient snižování délky kroku (StepResizeCoef ) na 0,95 (nebude-li řečeno jinak). Důležité pro nás bude, za jak dlouho dosáhneme kvalitního rozložení (dle hodnocení uživatele) a za jak dlouho sám algoritmus výpočet ukončí. Za kvalitní je považováno takové rozložení grafu P30 , kde jsou vrcholy rovnoměrně rozmístěny a cípy grafu jsou napnuty. Pro každou variantu spustíme algoritmus pětkrát a výsledné časy zprůměrujeme.

27

Základní algoritmus Na úvod opět začneme základním algoritmem bez jakékoliv optimalizace. S koeficientem snižování délky kroku nastaveným na hodnotu 0,95 algoritmus při každém z pokusů uvázl v lokálním minimu a správný výsledek nevydal (viz Obrázek 3.13). Z tohoto důvodu bylo nutné zvýšit koeficient na hodnotu 0,99. Při testování nižších hodnot (0,96; 0,97 a 0,98) algoritmus vždy alespoň v jednom z pěti testů uvázl.

Obrázek 3.13: Uváznutí výpočtu vizualizace grafu P30 v lokálním minimu při použití základního algoritmu s nastavením StepResizeCoef = 0,95. Výsledné srovnání nám nabízí Tabulka 3.1. Hodnoty v prvním řádku označují čas, ve kterém uživatel označil rozložení jako kvalitní, druhý řádek udává, za kolik vteřin algoritmus sám rozhodl o ukončení výpočtu. Můžeme zde pozorovat, že výsledné časy označené uživatelem jsou téměř poloviční oproti časům daným algoritmem. Tento jev je způsoben nastavením vysoké hodnoty koeficientu pro snižování délky kroku. Nedochází již k uváznutí v lokálním minimu, ale délka kroku klesá pomalu, a proto je i po nalezení vhodného rozložení (dle hodnocení uživatele) aktuální délka kroku relativně vysoká. Z toho plyne, že vrcholy jsou v každé iteraci algoritmu posouvány o velké vzdálenosti i přesto, že jsou již velmi blízko svých ideálních pozic (poskakují sem a tam). Kdo

Čas označení (s)

Uživatel 22,11 16,45 15,18 19,81 17,43 Algoritmus 33,16 30,09 32,42 32,06 30,55

Průměr 18,19 31,65

Tabulka 3.1: Srovnání časů, ve kterých uživatel označil kvalitní vizualizaci a ve kterých běh algoritmu skutečně skončil při použití základního algoritmu.

28

Barnesův–Hutův algoritmus Pro druhé srovnání byla použita optimalizace pomocí Barnesova–Hutova kritéria. Startovací pozice vrcholů byly – stejně jako u základního algoritmu – určeny náhodně. Z toho důvodu bylo nutné opět nastavit koeficient snižování kroku na hodnotu 0,99. Barnesův–Hutův algoritmus sice snižuje asymptotickou časovou složitost, ale ta nemá vliv na možné uváznutí v lokálním minimu. Srovnání časů v Tabulce 3.2 nám ukazuje, že výpočet se výrazně zrychlil. Zároveň je vidět, že příliš vysoká hodnota koeficientu DistanceCoef opět znamená velké rozdíly mezi uživatelsky zvolenými časy a skutečným ukončením běhu algoritmu. Kdo Uživatel 3,48 Algoritmus 4,85

Čas označení (s) 2,69 2,73

2,51 5,01

3,61 4,95

Průměr 2,37 4,22

2,93 4,35

Tabulka 3.2: Srovnání časů, ve kterých uživatel označil kvalitní vizualizaci a ve kterých běh algoritmu skutečně skončil při použití Barnesova–Hutova algoritmu. Vícevrstvý algoritmus Vícevrstvý algoritmus slibuje odstranění problému s uváznutím v lokálním minimu. Proto můžeme výpočet spouštět s koeficientem snižování kroku DistanceCoef = 0, 95 avizovaným již na začátku. Tabulka 3.3 nabízí časy jednotlivých běhů algoritmu. Časy označení uživatelem jsou velmi blízké časům běhu algoritmu. Toto plyne z povahy výpočtu, kdy nedochází k velkým přesunům vrcholů. Ve chvíli, kdy jsou vrcholy rovnoměrně rozmístěny, končí i běh algoritmu. Základní rozložení grafu je k dispozici rychle a většinu času poté trvá právě rovnoměrné rozmístění vrcholů (které bylo uvedeno jako jedna z podmínek kvalitního rozložení). Kdo Uživatel 9,05 Algoritmus 9,24

Čas označení (s) 9,63 9,51 10,21 9,42 9,81 10 10,34 10,25

Průměr 9,56 9,93

Tabulka 3.3: Srovnání časů, ve kterých uživatel označil kvalitní vizualizaci a ve kterých běh algoritmu skutečně skončil při použití vícevrstvého rozložení. Kombinace Barnesova–Hutova kritéria a vícevrstvého algoritmu Poslední srovnání nabízí kombinaci předchozích technik, tedy základní výpočet obohacený o Barnesův–Hutův algoritmus a vícevrstvé rozložení grafu. Díky vícevrstvému algoritmu jsou opět časy mezi označením od uživatele a ukončením výpočtu velmi malé (viz Tabulka 3.4).

29

Kdo Uživatel 1,33 Algoritmus 1,43

Čas označení (s) 1,26 1,28

1,48 1,59

1,29 1,38

Průměr 1,4 1,45

1,35 1,42

Tabulka 3.4: Srovnání časů, ve kterých uživatel označil kvalitní vizualizaci a ve kterých běh algoritmu skutečně skončil při použití kombinace Barnesova–Hutova kritéria a vícevrstvého algoritmu.

3.6.3

Dle velikosti grafu

Poslední měření se zaměřuje na rozdíly mezi délkou běhu základního algoritmu a délkou běhu za pomoci jeho optimalizací. V tomto případě již pracujeme s časy, kdy algoritmus sám ukončil výpočet (tedy v důsledku malých přesunů vrcholů v rámci jedné iterace algoritmu bylo splněno kritérium zastavení, viz Algoritmus 3.2). Vzdálenostní koeficient ε (DistanceCoef ) byl v tomto případě nastaven na hodnotu |V |/5, délka kroku (Step) na hodnotu 1 a koeficient snižování délky kroku (StepResizeCoef ) u algoritmů používajících vícevrstvé rozložení na 0,95 a u ostatních na 0,99. K testování byly použity grafy P10 , P20 , P30 , P40 , P50 , přičemž nejmenší z těchto grafů má 55 vrcholů a 135 hran, největší pak 1275 vrcholů a 3675 hran. Měření opět probíhalo nejprve pomocí základního Fruchtermanova–Reingoldova algoritmu, následně byl výpočet optimalizován použitím klastování vrcholů dle Barnesova–Hutova algoritmu. Třetí testování měřilo základní výpočet, který využíval vícevrstvý algoritmus a poslední měření kombinovalo obě optimalizace. Výsledky ukazuje Tabulka 3.5, ve které můžeme pozorovat značný vliv jednotlivých optimalizací na rychlost výpočtu. Zatímco pro větší grafy doba běhu základního algoritmu rychle roste, pomocí optimalizací není tento nárůst natolik drastický. Zajímavé srovnání nabízí porovnání Barnesova–Hutova algoritmu a vícevrstvého rozložení: u menších grafů není rozdíl v čase nijak propastný, avšak s rostoucí velikostí grafu již klastrování částic vítězí. Nejlepších výsledků pak dosahuje kombinace obou algoritmů, při níž bylo spočítáno rozložení grafu P50 za 3,58 vteřin. Důležité je také poznamenat, že rozložení grafu je čitelné – tedy lze již rozpoznat strukturu, ale vrcholy ještě nejsou rovnoměrně rozprostřeny – přibližně v polovině tohoto času. Pro graf P30 je možné výsledky porovnat napříč všemi metodami měření. Algoritmus

P10

Základní Barnes–Hut Vícevrstvý Kombinace

0,41 4,89 24,12 66,91 148,02 0,28 1,4 3,47 7,49 12,39 0,11 1,41 5,63 17,5 49,91 0,06 0,4 1,08 2,2 3,58

P20

P30

P40

P50

Tabulka 3.5: Srovnání délek běhů algoritmů pro vizualizaci grafu, časy jsou uvedeny v sekundách.

30

Grafické porovnání dat z Tabulky 3.5 nabízí také následující graf (viz Obrázek 3.14). 160

Čas běhu algoritmu (s)

140 120

Základní Barnes–Hut Vícevrstvý Kombinace

100 80 60 40 20 0 10

20

30 40 Velikost grafu n (Pn )

50

Obrázek 3.14: Srovnání výkonnosti algoritmů v závislosti na velikosti grafu.

31

4. Využití pro multimediální exploraci Hlavním cílem práce je využití fyzikálního modelu pro potřeby multimediální explorace. Vrcholy grafu mají reprezentovat obrázky a hrany mezi nimi jejich vzájemnou podobnost. Obrázky, které jsou si podobnější, by měly být spojeny kratší hranou; tím bude dosaženo tvorby shluků podobných obrázků. K tomuto účelu je nutné upravit výpočet sil v algoritmu Fruchtermana a Reingolda (Fruchterman a Reingold, 1991), kteří ve svém návrhu pracují s uniformními délkami hran.

4.1

Úprava Fruchtermanova–Reingoldova algoritmu

Uvažujme vzorce ze základní verze algoritmu pro výpočet odpudivých sil mezi všemi vrcholy fr (3.1) a přitažlivých sil mezi vrcholy spojenými hranou fa (3.2). Významnou konstantou v těchto vzorcích je parametr K, který reprezentuje ideální vzdálenost. Hu (2005) ve své práci uvádí odvození, že jsou-li dva vrcholy (částice) propojeny hranou (pružinou), pak síla působící mezi nimi bude nulová právě, když se jejich vzdálenost bude rovnat K(C)1/3 . Můžeme také nahlédnout, že přitažlivá síla fa vrcholy opravdu vždy přitahuje a parametr K zde určuje pouze sílu tohoto přitahování. Jednoduše: budeme-li mít dva vrcholy, mezi kterými bude působit pouze přitažlivá síla fa (odpudivou sílu nyní opemeneme), vrcholy se budou v každé iteraci přibližovat ke společnému středu; teprve ve chvíli, kdy bude jejich vzdálenost nulová, bude nulová i přitažlivá síla fa . Toto bude platit i v případě volby libovolné hodnoty parametru K, který má vliv pouze na množství iteračních kroků, které by bylo nutné k dosažení tohoto stavu provést. Aby výpočet přitažlivé síly fa reflektoval délku hrany, zavedeme nový vzorec síly fa∗ : fa∗ (i, j) = kxi − xj k − d(i, j),

{i, j} ∈ E,

(4.1)

kde funkce d(i, j) udává optimální délku hrany mezi vrcholy i a j. Tato síla již nemusí být vždy nutně přitažlivá, neboť je-li délka hrany d(i, j) větší, než je aktuální vzdálenost mezi vrcholy i a j, síla nabude záporného hodnoty a bude působit jako odpudivá.

32

d1

d2

d

Obrázek 4.1: Působení síly fa∗ vzhledem ke vzdálenosti částic. Působení upravené síly fa∗ je ilustrováno na Obrázku 4.1. Zde je postupně zobrazeno působení na hranu (pružinu), která je příliš krátká a měla by být prodloužena (d1 < d); má ideální délku (d); ideální délku překračuje a měla by být kratší (d < d2 ). V upraveném fyzikálním modelu částic, který používá původní odpudivou sílu mezi vrcholy fr a upravenou sílu mezi vrcholy spojenými hranou fa∗ , jsme již schopni reflektovat požadavek na různé délky hran. Síla fr nyní stále zajišťuje rovnoměrné rozdělení vrcholů, protože všechny se nadále odpuzují, a upravená síla fa∗ k sobě vrcholy přitahuje anebo je ještě více odpuzuje na základě požadované délky hrany d.

Obrázek 4.2: Graf s různými délkami hran. Nyní jsme již schopni vyjádřit ve vizualizaci podobnost jednotlivých obrázků, která bude nepřímo úměrná délce hrany. Čím jsou si obrázky více podobné, tím kratší bude hrana mezi nimi.

4.2

Prořezávání hran

Výstupem podobnostních algoritmů, které se v multimediální exploraci používají, je množina obrázků a jejich vzájemná podobnost. V řeči grafů to znamená, že výstupem je úplný graf o n vrcholech (Kn ). Z teorie grafů plyne vzorec, že úplný graf o n vrcholech má právě n(n − 1)/2 hran. Tedy kupříkladu úplný graf se sto vrcholy K100 má 4950 hran. Nejenom, že takový počet hran zpomaluje výpočet, ale vede také ke špatným výsledkům, neboť v takovém množství hran zanikají délky hran a výsledkem je uváznutí v lokálním minimu (viz Obrázek 4.3).

33

Obrázek 4.3: Vizualizace úplného grafu K100 . Abychom dosáhli lepších výsledků a rychlejšího výpočtu, tak některé hrany odstraníme. Jednoduché prořezávání Snadno můžeme realizovat odstranění určitého počtu hran. Nabízí se odstranit hrany, které vyjadřující velmi malou podobnost mezi obrázky, tedy těch, u nichž se podobnost přibližuje nule; respektive jsou to nejdelší hrany v grafu. Problémem tohoto přístupu je, že existuje-li v kolekci obrázek nebo skupina obrázků, které jsou velmi odlišné od ostatních, nebudou s nimi spojeny žádnou hranou. Proto tento přístup vede často ke vzniku několika komponent souvislosti v grafu. k -NN prořezávání Abychom zamezili trhání grafu na několik komponent souvislosti a udrželi graf kompaktní, realizujeme prořezávání respektující nejdůležitější hrany pro každý vrchol. V této práci je algoritmus označen jako k-NN prořezávání (k-NN pochází z anglického k-Nearest Neighbors). Stejně jako v jednoduchém prořezávání postupně odstraňujeme hrany od té nejdelší. Pokud ale narazíme na hranu, která obsahuje vrchol připojený ke zbytku grafu již pouze k hranami, tak tuto hranu neodstraňujeme. Výsledkem je graf, ve kterém je každý vrchol spojen alespoň k hranami.

34

(a) Jednoduché prořezávání.

(b) k-NN prořezávání.

Obrázek 4.4: Srovnání jednoduchého prořezávání a k-NN prořezávání (v tomto případě k = 3). Další nevýhodou jednoduchého prořezávání je, že vrcholy, které nejsou připojeny žádnou hranou, nerespektují svou výslednou pozicí podobnost mezi ostatními obrázky. Tento nedostatek můžeme vidět na Obrázku 4.4: na pravé straně (a) se střídají tmavé obrázky se světlými, které nejsou spojeny žádnými hranami. Naopak u (b) se již tento problém v důsledku použití k-NN prořezávání neobjevuje.

35

5. Implementace Součástí práce je také implementace algoritmů pro vizualizaci grafů a výsledků multimediální explorace ve 2D a 3D prostoru. Implementace obsahuje Fruchtermanův–Reingoldův algoritmus (viz 3.1) s adaptivní délkou kroku a s upraveným vzorcem pro různé délky hran (viz 4.1); výpočet je zrychlen použitím Barnesova–Hutova algoritmu (viz 3.2), který snižuje asymptotickou časovou složitost jedné iterace algoritmu z O(n2 ) na O(n log(n)). Pro další zrychlení a vylepšení kvality výsledků je také použit vícevrstvý algoritmus (viz 3.3). Aby bylo rozložení obrázků z explorace co nejlepší, je použito k-NN prořezávání hran (viz 4.2). Výpočet vizualizace dat je naprogramován v jazyce C#. Základem je jednoduché rozhraní (5.1), které implementuje třída starající se o vizualizaci pomocí fyzikálního modelu částic (5.2). Zdrojový kód 5.1: Rozhraní pro výpočet rozložení grafu. public interface IDataVisualizationHelper { void CreateDataVisualization( List nodes, List edges ); }

Zdrojový kód 5.2: Implementace rozhraní 5.1. public class ForceDirectedDataVisualizationHelper : IDataVisualizationHelper { ... }

Stejně jako rozhraní, tak i třída ForceDirectedDataVisualizationHelper je generická. Jako parametr T je možné použít Vector2D anebo Vector3D, které jsou oba také součástí implementace. Na základě zvoleného vektoru je následně rozložení grafu vypočítáno ve 2D anebo 3D prostoru. Mimo hlavní třídu jsou implementovány také pomocné třídy, mezi nejdůležitější patří třída reprezentující kvadrantový a oktantový strom a třída zajišťující podporu pro vícevrstvý algoritmus a dělení grafu na vrstvy. Reprezentace grafu Graf je reprezentován velmi jednoduchým způsobem; pro vrcholy slouží třída GraphNode, která obsahuje jedinou proměnnou a to odkaz (URL) na obrázek, který daný vrchol zastupuje. Hrany jsou reprezentovány třídou GraphEdge, jež pomocí proměnných Source a Target určuje indexy vrcholů, které spojuje. Zároveň obsahuje proměnnou Value, která obecně označuje ohodnocení (váhu) hrany, v našem případě délku hrany.

36

Vstupy a výstupy Vstupem hlavní metody CreateDataVisualization pro hledání vhodného rozložení grafu je seznam vrcholů a hran. U hran je očekáváno nastavení délky hrany. Graf je neorientovaný, a proto není nutné vkládat hranu dvakrát pro každé dva vrcholy, tedy pro hranu mezi vrcholy x a y stačí vložit (x, y) ⊕ (y, x). Quadtree, Octree Dvě pomocné třídy pro stromové dělení prostoru, Quadtree pro dělení 2D prostoru a Octree 3D prostoru. U obou je dělení prostoru rekurzivní, tudíž každá instance objektu je buď listem (a obsahuje jeden nebo žádný prvek) anebo obsahuje reference na čtyři (kvadrantový strom), respektive osm (oktantový strom) stromů, které dále rovnoměrně dělí prostor vymezený touto instancí. CoarseningGraph Třída zajišťující redukci grafu pro vícevrstvý algoritmus. Inicializována je grafem a voláním metody Coarse vydá nový objekt třídy CoarseningGraph, který již reprezentuje zredukovaný graf. Na tomto objektu je možné znova volat metodu Coarse a tím graf opětovně redukovat (viz Obrázek 5.1). Tím získáváme jednotlivé redukční vrstvy G0 , G1 , G2 , . . . Gn , které jsou základem vícevrstvého algoritmu. V rámci každé redukce redukujeme množinu vrcholů na jeden vrchol, proto je u každé vrstvy uložena také informace o mapování mezi vrcholy, tedy které vrcholy byly zredukovány na jaký. G0

Coarse();

G1

Coarse();

...

Coarse();

Gn

Obrázek 5.1: Volání metody Coarse.

5.1

Nastavení a parametry

Třída ForceDirectedDataVisualizationHelper (5.2) nabízí rozličné možnosti nastavení. Je možné nastavit většinu parametrů všech algoritmů, které jsou pro získání rozložení grafu použity. V následujícím seznamu jsou nastavitelné parametry uvedeny včetně inicializačních hodnot. Fruchtermanův–Reingoldův algoritmus K =1 V původním algoritmu určuje optimální (přirozenou) délku pružiny, v upraveném optimální vzdálenost mezi vrcholy. C = 0,2 Reguluje odpudivou sílu mezi vrcholy.

37

Step = 1 Reguluje množství síly, které je v každém kroku na vrcholy aplikováno. Postupně slábne, díky adaptivní délce kroku však může za určitých podmínek i vzrůst. StepResizeCoef = 0,95 Zajišťuje snižování délky kroku, po každé iteraci je touto hodnotou délka kroku vynásobena. Pokud má být délka kroku naopak prodloužena, je touto hodnotou vydělena. DistanceCoef = 1 Reprezentuje ε ze základního algoritmu. Používá se k testování, zda-li má být již běh algoritmu ukončen anebo je ještě vhodné pokračovat další iterací. MaxNumberOfTicks = 10000 Maximální počet iterací algoritmu; pokud je hodnota překročena, je vydán výsledek. GravityStrength = 0,01 Upravuje sílu gravitace, která přitahuje graf ke středu prostoru.

Vícevrstvý algoritmus CoarseGraph = true Rozhoduje, zda-li bude na graf použit vícevrstvý algoritmus. CoarsedGraphNodesThreshold = 10 Určuje množství vrcholů, které musí být v grafu, aby byla prováděna další redukce. Pokud je jich rovno nebo méně, není již prováděna další redukce a aktuálně zpracovávaná vrstva je označena jako nejnižší. CoarsePolicy = V ertexCover Nastavení typu algoritmu redukce grafu. Jedná se o výběr ze dvou možností; jednou z nich je aproximační algoritmus pro vrcholové pokrytí (VertexCover ), druhou aproximační algoritmus pro maximální párování (Matching).

Prořezávání CutEdges = true Povoluje nebo zakazuje prořezávání hran grafu. EdgeCuttingPolicy = kN N Nastavení typu prořezávání hran grafu. Je možné zvolit jednoduché prořezávání (Simple) anebo k-NN prořezávání (kNN ).

38

SimpleEdgeCutting = 20 Určuje koeficient prořezávání hran x, výsledně je odstraněno 1/x z celkového počtu hran (například pro x = 2 bude odstraněna polovina hran). KNNEdgeCutting = 5 Nastavuje parametr k algoritmu pro k-NN prořezávání.

5.2

Příklad použití

Na ukázce 5.3 můžeme vidět příklad použití pro jednoduchý grafový trojúhelník. Nejprve připravíme graf, tedy seznam vrcholů a hran, které chceme vizualizovat. U vrcholů specifikujeme názvy obrázků, které mají reprezentovat, u hran zdroj, stok a ideální délku hrany. Následně vytvoříme instanci vizualizační třídy; upravíme nastavení vizualizace; spustíme výpočet. Výsledek je následně dostupný v normalizované podobě, ve které jsou pozice všech bodů rozprostřeny do intervalu [0; 1]. Zdrojový kód 5.3: Příklad použití. var nodes = new List () { new GraphNode ("1.jpg"), new GraphNode ("2.jpg"), new GraphNode ("3.jpg") }; var edges = new List () { new GraphEdge (0, 1, 1.0), new GraphEdge (1, 2, 2.5), new GraphEdge (2, 0, 1.0) }; var visualization = new ForceDirectedDataVisualizationHelper(); visualization.CoarseGraph = false; visualization.K = 1.2; visualization.CreateDataVisualization(nodes, edges); var result = visualization.NormalizedPoints();

5.3

Fáze algoritmu

Hledání nejvhodnějšího rozložení je realizováno pomocí tří hlavních fází. První fáze je inicializační, v druhé fázi hledáme ideální rozložení (a to s použitím vícevrstvého algoritmu) a ve třetí fázi vydáváme normalizovaný výpočet.

39

5.3.1

Inicializace

Inicializační fáze slouží k přípravě dat pro samotný výpočet. Pokud není v nastavení zakázáno používání vícevrstvého algoritmu, je součástí této fáze také redukce grafu na jednotlivé vrstvy. Základní graf G = G0 je postupně redukován na grafy G1 , G2 , . . . Gn . Redukce je zastavena ve chvíli, kdy aktuálně zredukovaný graf Gi neobsahuje počet vrcholů daný nastavením CoarsedGraphNodesThreshold. Na závěr jsou připraveny prostorové reprezentace vrcholů – body, které určují, na jaké pozici v prostoru se body aktuálně nachází (viz Algoritmus 5.1). while CoarseGraph ∧ kV k > CoarsedGraphNodesThreshold do redukuj graf (metodou odpovídající nastavení CoarsePolicy); end pro nejnižší vrstvu grafu připrav body na náhodné pozice; Algoritmus 5.1: Pseudokód inicializační fáze.

5.3.2

Výpočet rozložení

Druhou a nejdůležitější částí je výpočet rozložení. Postupně pracujeme s jednotlivými vrstvami grafu Gn , Gn−1 , . . . G0 , které byly vytvořeny v inicializační fázi algoritmu. Tento postup bude fungovat i v případě zákazu používání vícevrstvého algoritmu, protože budeme pracovat zrovna s původním grafem, který je vlastně nultou vrstvou G0 . Pro aktuálně zpracovávanou vrstvu grafu Gi je nejprve sestaven kvadrantový nebo oktantový strom (v závislosti na hledání rozložení ve 2D anebo 3D prostoru). Následuje výpočet působení sil na každý vrchol z tohoto grafu, načež je vrchol ihned po spočítání působící síly posunut, což může vést i k přesunu vrcholů do sousedních klastrů stromu. Jak již však bylo diskutováno (viz Sekce 3.2), není kvůli tomu nutné jakkoliv strom upravovat a přesouvat vrcholy k sousedům, neboť toto chování nemá vliv na výsledek. Celý tento blok je opakován dokud není splněna podmínka konvergence (viz Algoritmus 3.2) anebo není dosaženo maximálního počtu iterací MaxNumberOfTicks. V rámci zrychlení běhu algoritmu probíhá výpočet sil působících na vrcholy paralelně. Stejně jako u možných přesunů do sousedních klastrů stromu, i u paralelizace hrozí vznik potenciálních nepřesností ve výpočtu. Ani zde však nebyl zaznamenán žádný vliv na výsledek. Je-li dosaženo konvergence a aktuálně zpracovávaný graf je G0 , pak je druhá fáze algoritmu u konce. Nejednalo-li se však o nejvyšší vrstvu vícevrstvého algoritmu, je potřeba přenést vypočítané pozice vrcholů do vyšší úrovně a hledání vhodného rozložení zopakovat pro tuto vrstvu. K tomu nám pomůže mapování vrcholů, které je součástí každé redukční vrstvy. Díky tomuto mapování víme, které vrcholy byly zredukovány na které a můžeme tedy jednoduše zpětně přenést pozice z nižší vrstvy na vrcholy z vrstvy vyšší.

40

i = n; for Gi ∈ Gn , . . . G0 do while !konvergence do sestroj kvadrantový/oktantový strom; for i ∈ Vi do vypočítej působení sil; posuň vrchol dle působení sil; end end přenes pozice vrcholů z Gi do Gi−1 ; i −−; end Algoritmus 5.2: Pseudokód výpočetní fáze.

5.3.3

Vydání výsledku

Po nalezení rozložení grafu následuje poslední fáze, a tou je normalizace výsledků. Výsledky jsou záměrně v normalizovaném tvaru – díky tomu je výsledné rozložení jednoduché zobrazit na libovolně velké prezentační ploše.

5.4

Testovací prostředí

Součástí práce je také testovací prostředí, které umožňuje spouštět výpočet rozložení pro množinu obrázků a předem vypočítané podobnostní grafy. Jedná se o jednoduchou formulářovou aplikaci určenou pro testování algoritmu a jeho nastavení. Součástí je také zobrazení výsledného rozložení ve 2D prostoru. Podobnostní grafy, které testovací prostředí obsahuje, byly vygenerovány pomocí exploračního portálu (Čech a kol., 2014). K výpočtu podobností mezi obrázky byl použit podobnostní model feature signatures. Jak testovací prostředí vypadá nám ukazuje Obrázek ??. Hlavní část tvoří výsledné rozložení grafu, vpravo jsou umístěny ovládací prvky pro úpravu nastavení vizualizace. Mimo nastavení, které již bylo zmíněno v sekci o možných nastavení vizualizace (viz 5.1), je možné také zvolit data, která se mají vizualizovat. Na výběr jsou grafy s 10 až 214 obrázky. V druhém případě je možné zapnout si průběžnou aktualizaci rozložení grafu – díky tomu je vidět průběh výpočtu vizualizace za cenu mírného zpomalení vypočtu. V levém horním rohu jsou zobrazeny informace o průběhu výpočtu. Postupně po řádcích to jsou: počet vrcholů a hran grafu; doba běhu algoritmu; počet iterací algoritmu, v závorce poté počet iterací za sekundu; celková energie v systému; aktuální délka kroku.

41

Obrázek 5.2: Ukázka testovacího prostředí pro graf s 50 obrázky.

5.5

Napojení na explorační portál

Jak již bylo zmíněno v úvodu do problematiky (viz Kapitola 1), v současné době již existuje explorační portál (Čech a kol., 2014), který umožňuje uživatelům explorovat v různých kolekcích dat, vyhledávat pomocí textového řetězce (zprostředkovaně skrz vyhledávač Bing) a následně explorovat výsledky. Návštěvník také může nahrát vlastní fotky ze sociálních sítí. Portál se skládá ze serverové a klientské části. Serverová část vyřizuje požadavky, které jsou zasílány z webové klientské části. Ke komunikaci mezi serverem a klientem se využívá rozhraní typu REST (z anglického Representational State Transfer ) a data jsou předávána ve formátu JSON1 . Pomocí technologie WebSocket může komunikovat i server s webovým klientem a zasílat průběh aktuálního výpočtu. Klientská část se stará o zobrazování výsledků uživateli, který může jednoduše explorovat anebo využít některé z pokročilých funkcí, jako je například dotaz pomocí více obrázků či explorace v některém ze čtyř základních směrů. Možné je také volit mezi různými nastaveními: je možné měnit zdroj dat, způsob výpočtu podobnosti mezi obrázky, použité indexy a podobně. Součástí klientské části portálu je i vizualizace dat; stejně jako v této práci je k tomuto účelu použita vizualizace grafu pomocí fyzikálního modelu částic. Současné řešení je naprogramováno v jazyce JavaScript a veškerý výpočet rozložení probíhá na klientské straně v internetovém prohlížeči. Jelikož není tento výpočet

1

http://www.json.org

42

optimalizován pomocí klastrování (viz Sekce 3.2), je možné v reálném čase vizualizovat pouze několik desítek obrázků. Není použit ani vícevrstvý algoritmus (viz Sekce 3.3), a proto vizualizace v několika prvních krocích mění výrazně pozice obrázků (obrázky skáčou). To může být pro uživatele nepříjemným chováním, neboť dochází k velkým přesunům a je složité se v rozložení před dokončením výpočtu zorientovat. Řešení, které vzniklo v rámci této práce, je možné použít přímo na serveru exploračního portálu. Napojení ilustruje Obrázek 5.3, který srovnává současné řešení s možným řešením po rozšíření exploračního portálu. Zatímco nyní na serveru probíhá výpočet podobnosti mezi obrázky, z jeho výsledků je sestaven podobnostní graf a ten je následně odeslán do klientského části. Po rozšíření by byl server obohacen o komponentu umožňující výpočet (předpočítání) rozložení a součástí odpovědi pro klientský prohlížeč by již bylo i vhodné rozložení.

Server

Server

Výpočet podobnosti obrázků

Výpočet podobnosti obrázků

Sestrojení podobnostního grafu

Sestrojení podobnostního grafu

Předpočítání rozložení obrázků

Webový klient

Webový klient

(a)

(b)

Obrázek 5.3: Srovnání současného řešení (a) a možného napojení na explorační portál (b).

43

Možná by byla také společná koordinace výpočtu, kdy server vypočítá pouze část rozložení a zbytek (dohlazení výsledků) dopočítá klient. Tím by se na klientské části zamezilo velkým přesunům obrázků na začátku výpočtu a zároveň by se snížilo zatížení serveru, který by počítal pouze část výpočtu. Toto by bylo možné realizovat nastavením maximálního počtu iterací, které bude počítat server, případně omezit délku výpočtu maximálním časem výpočtu. Server by také spolu s výsledkem mohl posílat aktuální stav proměnných (například délky kroku), aby dopočítání mohlo jednoduše pokračovat na klientské části.

44

6. Webový klient K samotnému prohlížení rozložení, které je vyprodukované fyzikálním modelem částic, je určen webový klient. Ten je také součástí práce. Tento klient přijímá jako vstup vypočítané pozice jednotlivých obrázků a ty na základě těchto pozic rozprostře do 3D prostoru. Sám tedy neprovádí žádný výpočet rozložení, ale pouze interpretuje výsledky fyzikálního modelu.

6.1

Realizace

Webový klient je tvořen kombinací HTML, CSS a JavaScriptu; JavaScriptová část navíc využívá knihovnu Three.js1 , pomocí které je vytvořeno zobrazení výsledného uspořádání obrázků.

6.1.1

Three.js

Three.js je JavaScriptovou knihovnou, která byla vytvořena za účelem usnadnění zobrazování 3D grafiky ve webovém prohlížeči; samotná knihovna pak pro vykreslování používá WebGL. Její použití je ale jednodušší než programování právě ve WebGL. Knihovna umožňuje za použití pouze JavaScriptu vytvářet 3D scény a animace, pracovat s kamerou, objekty, světlem a materiály. Výsledek je možné vložit přímo jako součást webové stránky. Běh knihovny je hardwarově akcelerovaný na grafické kartě. Součástí knihovny je také několik připravených komponent (například ovládání kamery pro pohyb po scéně), které je možné použít pro tvorbu základních vizualizací. Díky použití WebGL není potřeba instalovat žádná speciální rozšíření do prohlížeče. Autorem knihovny je Ricardo Cabello.

6.1.2

Formát dat

Informace o rozložení obrázků jsou webovému prohlížeči předávány souborem ve formátu JSON. Celkově jsou v souboru dva seznamy: seznam vypočítaných pozic vrcholů (obrázků) a seznam vrcholů. Jedná se o serializovaná data tříd Point a GraphNode. Pozice vrcholů jsou normalizované; v seznamu vrcholů každý vrchol obsahuje URL obrázku, který zastupuje. Příklad formátovaných dat pro dva vrcholy ilustruje Zdrojový kód 6.1.

1

http://threejs.org

45

Zdrojový kód 6.1: Příklad dat. { "points": [ { "Position": { "X": 0.7, "Y": 0.3, "Z": 0.8 } }, { "Position": { "X": 0.5, "Y": 0.6, "Z": 0.9 } }], "nodes": [ { "url": "86.jpg" }, { "url": "42.jpg" }] }

6.2

Napojení na explorační portál

Pakliže bychom přidali výpočet rozložení z této práce na současný server exploračního portálu, mohli bychom zobrazovat výsledky explorace i v tomto webovém klientovi. Tento klient totiž umožňuje pouze zobrazení výsledků a nikoliv výpočet rozložení. Pokud by však server posílal jakou součást odpovědi vhodné rozložení, nic by použití tohoto klienta nebránilo.

6.2.1

Komunikace se serverem

V současné době probíhá komunikace klienta se serverem pomocí rozhraní REST, se kterým je velmi jednoduché z JavaScriptového klienta komunikovat. Data jsou ve formátu JSON, který používá i tato verze webového klienta. Již v současné verzi je pro klienta na serveru připraven podobností graf (tedy včetně pole nodes, které využívá i tato verze) a jedinou úpravou by bylo rozšíření o seznam pozic vrcholů points. Tento seznam by dodala serverová část starající se o výpočet rozložení grafu.

46

6.3

Ukázka

Obrázek 6.1 ukazuje, jak vypadá vizualizace obrázků ve 3D prostoru. Ve webovém prohlížeči je možné pomocí myši vizualizací otáčet, rolováním pak přibližovat anebo oddalovat kameru.

Obrázek 6.1: Ukázka 3D webové vizualizace obsahující 214 obrázků.

47

Závěr Práce se zaměřila na průnik dvou různých témat: multimediální exploraci a vizualizaci grafů. Tyto dvě – na první pohled rozličná témata – mají společného jmenovatele, kterým je kvalitní a čitelné zobrazení dat uživateli. Multimediální explorace se snaží řešit problém vyhledávání v neanotovaných kolekcích multimediálních dat, případně situaci, kdy uživatel neumí správně specifikovat požadavek či nemá referenční data (například obrázek, pomocí kterého by se mohlo vyhledávat). Základem, na kterém explorace staví, je takzvané vyhledávání dle obsahu, tedy informací obsažených přímo v datech (v obrázcích například barvy nebo tvary). Aby multimediální explorace dosahovala kvalitních výsledků, je pro ni důležité zobrazení dat uživateli. Pro znázornění vztahů mezi obrázky proto využívá grafy, které pomocí vrcholů reprezentují jednotlivé obrázky a pomocí hran vztahy (podobnosti) mezi nimi. Tyto grafy jsou následně vykreslovány do 2D anebo 3D prostoru a uživatel díky nim dostává lepší přehled o aktuálně zobrazené množině obrázků. Jak již bylo v úvodu práce zmíněno, kvalita vizualizace je velmi důležitá, neboť grafy jakožto abstraktní struktury nemají jednoznačně dané nejlepší rozložení. Kvalitní vizualizace však může uživateli usnadnit čtení a porozumění grafu, který data reprezentuje. V kontextu multimediální explorace se díky kvalitnímu rozložení může uživatel rychleji zorientovat v kolekci obrázků, neboť svou pozicí v prostoru tyto obrázky zároveň reprezentují podobnostní vztah vůči okolním objektům. Hlavním přínosem práce je vytvoření komponenty pro rychlý výpočet rozložení podobnostního grafu, který reprezentuje výsledek multimediální explorace. Základem této komponenty je Fruchtermanův–Reingoldův algoritmus, který slouží pro výpočet rozložení grafů s uniformními délkami hran. Výpočet je realizován simulací fyzikálního modelu, kde vrcholy jsou nahrazeny kladně nabitými částicemi (obecně v literatuře označovány jako kroužky, rings; které se dle Coulombova zákona odpuzují) a hrany pružinami (které se dle Hookova zákona smršťují). Asymptotická časová složitost algoritmu byla následně snížena pomocí Barnesova–Hutova algoritmu. Abychom zabránili uváznutí výpočtu v lokálním minimu, je použit také vícevrstvý algoritmus, který ještě před samotným výpočtem pomocí fyzikálního modelu částic najde vhodné startovací pozice jednotlivých vrcholů. Pro porovnání použitých optimalizací proběhly v rámci práce také tři druhy měření. První měření se zabývalo testováním kvality vizualizace po prvních 400 ms výpočtu. Druhé měření srovnávalo rozdíl mezi časem, ve kterém již uživatel považoval vizualizaci za kvalitní, a kdy byl běh algoritmu skutečně ukončen. Poslední měření se věnovalo porovnání rychlosti výpočtu pro různé velikosti grafu; nejprve při použití základního algoritmu a následně s použitím jeho optimalizací.

48

Pro vizualizaci podobnostních grafů, jejichž hrany jsou ohodnocené a vyjadřují míru podobnosti mezi obrázky (vrcholy), bylo nutné upravit výpočet algoritmu tak, aby dokázal reprezentovat hrany různých délek. Toho se podařilo dosáhnout, a to úpravou výpočtu síly, kterou na vrcholy pružiny působí. V základním algoritmu mohou pružiny působit pouze přitažlivou silou, avšak v upravené verzi mohou – stejně jako elektrický náboj – vrcholy i odpuzovat. Podobnostní grafy samy o sobě obsahují velmi velké množství hran (dokonce maximální množství hran – jedná se totiž o úplné grafy). Nejenom, že tak velké množství hran zpomaluje výpočet, ale také vede ke špatným výsledným rozložením. Hrany je tedy nutné prořezávat. Jako nejjednodušší řešení se nabízí odstranit hrany, které jsou nejdelší (tedy říkají, že podobnost daných dvou obrázků je velmi malá). Při použití tohoto jednoduchého prořezávání však mohou vznikat osamocené komponenty souvislosti (povětšinou osamocené vrcholy). To se projevuje hlavně ve chvíli, kdy vizualizace obsahuje obrázek nebo malé množství obrázků, které jsou velmi odlišné od ostatních. Tyto obrázky pak volně plují vizualizací a mohou se dostat do blízkosti obrázků, které s nimi podobnostně nesouvisí. Abychom tomuto chování zabránili, je v práci navrženo a implementováno takzvané k-NN prořezávání, které zajišťuje, že každý vrchol bude s okolím spojen alespoň k hranami. Použitím tohoto prořezávání dosahuje vizualizace lepších výsledků. K testovacím účelům byla vytvořena formulářová aplikace, která umožňuje jednoduše měnit parametry vizualizace a ihned ji spouštět. Je možné měnit nastavení základního vizualizačního a vícevrstvého algoritmu a také parametry prořezávání. Výsledná 2D vizualizace je zobrazena uvnitř aplikace. Pro testování ve 3D prostoru byl vytvořen webový klient, který za pomoci HTML, CSS a JavaScriptu dokáže zobrazit výsledné rozložení grafu.

49

Možná rozšíření Komponenta pro výpočet rozložení by mohla být využita na již existujícím exploračním portále. Možné napojení bylo diskutována v páté kapitole (viz Sekce 5.5) a mělo by být velmi jednoduché, neboť návrh komponenty probíhal již s ohledem na budoucí použití právě na tomto portále. Kvalita výsledného rozložení by mohla být vylepšena výpočtem pozic ve vyšších dimenzích a jejich následnou projekcí do 2D nebo 3D prostoru. Tento postup popisují ve své práci Gajer a kol. (2004). Jimi navrhované řešení umožňuje projekci z libovolné dimenze Rn do R3 anebo R2 . Základem projekce je volba n lineárně nezávislých vektorů z prostoru Rn , použití Gramovy-Schmidtovy ortogonalizace pro nalezení ortogonální báze prostoru Rn z těchto vektorů a použití vzorce pro výpočet pozice bodu ve 2D nebo 3D prostoru. Dalším vylepšením by mohlo být nastavení maximální hloubky kvadrantového a oktantového stromu. Už v sekci o klastrování částic (viz Sekce 3.2) je zmíněn článek Hua (Hu, 2005), který maximální hloubku stromu navrhuje. Použitím tohoto omezení by se eliminoval potenciální problém zbytečně hlubokých stromů, které vznikají, jsou-li dva body umístěny velmi blízko sebe. To plyne z povahy těchto datových struktur, jelikož dělí prostor rovnoměrně a nezávisle na rozložení dat. Kupříkladu rozdělení 2D prostoru se třemi body (0, 0), (1, 1) a (100, 100) povede ke vzniku kvadrantového stromu o výšce 8. V případě použití vizualizační komponenty na serveru exploračního portálu by mohl být vypracován koncept předání výpočtu rozložení ze serveru na klientskou část. Při výpočtu rozložení bez použití vícevrstvého rozložení se největší přesuny vrcholů odehrávají na začátku výpočtu. Aby se tomuto jevu zabránilo, je použit vícevrstvý algoritmus, který však nemusí být na klientovi implementován. Server by tedy mohl vypočítat část výpočtu (například pouze určit startovací rozložení pomocí vícevrstvého algoritmu) a tento mezivýsledek předat klientovi, který by již dopočítal zbytek a zabránilo by se tak velkým přesunům obrázků, které jsou jedním z nedostatků současného exploračního portálu. Druhou možností je, že by server počítal rozložení a po určitém počtu iterací anebo po určitém čase by výpočet předal klientovi. Pro zachování konzistence výpočtu by bylo ideální předat klientovi i aktuální délku kroku. Míra dělení, tedy jak velkou část výpočtu by počítal server a jak velkou klient, by se mohla odvíjet od aktuálního zatížení serveru.

50

Seznam použité literatury Archambault, D., Munzner, T. a Auber, D. (2007). Topolayout: Multilevel graph layout by topological features. Visualization and Computer Graphics, IEEE Transactions on, 13(2), 305–317. Barnes, J. a Hut, P. (1986). algorithm.

A hierarchical O(n log n) force-calculation

Battista, G. D., Eades, P., Tamassia, R. a Tollis, I. G. (1994). Algorithms for drawing graphs: an annotated bibliography. Computational Geometry, 4(5), 235 – 282. ISSN 0925-7721. Battista, G. D., Eades, P., Tamassia, R. a Tollis, I. G. (1998). Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1st edition. ISBN 0133016153. Beecks, C., Skopal, T., Schöffmann, K. a Seidl, T. (2011). Towards large-scale multimedia exploration. In Proceedings of the 5th International Workshop on Ranking in Databases (DBRank 2011), pages 31–33. Čech, P. a Grošup, T. (2015). Comparison of metric space browsing strategies for efficient image exploration. In Content-Based Multimedia Indexing (CBMI), 2015 13th International Workshop on, pages 1–6. IEEE. Čech, P., Grošup, T., Kinšt, J., Macík, M. a Navrátil, L. (2014). Explorační portál. http://herkules.ms.mff.cuni.cz. Coole, J., Wernsing, J. a Stitt, G. (2009). A traversal cache framework for FPGA acceleration of pointer data structures: a case study on BarnesHut N-body simulation. In Reconfigurable Computing and FPGAs, 2009. ReConFig’09. International Conference on, pages 143–148. IEEE. Datta, R., Joshi, D., Li, J. a Wang, J. Z. (2008). Image retrieval: Ideas, influences, and trends of the new age. ACM Computing Surveys (CSUR), 40 (2), 5. ˘ rusöz, U., Madden, B. a Madden, P. (1997). Circular layout in the Dog graph layout toolkit. In Graph Drawing, pages 92–100. Springer. Eades, P. A. (1984). A heuristic for graph drawing. In Congressus Numerantium, volume 42, pages 149–160. Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 128–140. Finkel, R. a Bentley, J. (1974). Quad trees a data structure for retrieval on composite keys. Acta Informatica, 4(1), 1–9. ISSN 0001-5903. Fruchterman, T. M. a Reingold, E. M. (1991). Graph drawing by forcedirected placement. Softw., Pract. Exper., 21(11), 1129–1164.

51

Gajer, P., Goodrich, M. T. a Kobourov, S. G. (2000). A fast multidimensional algorithm for drawing large graphs. In Graph Drawing’00 Conference Proceedings, pages 211–221. Gajer, P., Goodrich, M. T. a Kobourov, S. G. (2004). A multidimensional approach to force-directed layouts of large graphs. Computational Geometry, 29(1), 3–18. Grošup, T., Čech, P., Lokoč, J. a Skopal, T. (2015). A web portal for effective multi-model exploration. In MultiMedia Modeling, pages 315–318. Springer. Grošup, T., Moško, J. a Čech, P. (2015). Continuous hierarchical exploration of multimedia collections. In Content-Based Multimedia Indexing (CBMI), 2015 13th International Workshop on, pages 1–4. IEEE. Hamada, T. a Nakasato, N. (2005). Massively parallel processors generator for reconfigurable system. pages 329–330. IEEE. Harel, D. a Koren, Y. (2002). Graph drawing by high-dimensional embedding. In Graph Drawing, pages 207–219. Springer. Hu, Y. (2005). Efficient, high-quality force-directed graph drawing. Mathematica Journal, 10(1), 37–71. Kamada, T. a Kawai, S. (1989). An algorithm for drawing general undirected graphs. Information processing letters, 31(1), 7–15. Koren, Y., Carmel, L. a Harel, D. (2003). Drawing huge graphs by algebraic multigrid optimization. Multiscale Modeling & Simulation, 1(4), 645–673. Kruja, E., Marks, J., Blair, A. a Waters, R. C. (2001). A short note on the history of graph drawing. 2265, 272–286. Kruskal, J. B. a Seery, J. B. (1980). Designing network diagrams. In Proc. First General Conf. on Social Graphics, pages 22–50. Lew, M. S., Sebe, N., Djeraba, C. a Jain, R. (2006). Content-based multimedia information retrieval: State of the art and challenges. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 2(1), 1–19. Lokoč, J., Grošup, T. a Skopal, T. (2012). SIR: The Smart Image Retrieval Engine. In Similarity Search and Applications, pages 240–241. Springer. Moško, J., Lokoč, J., Grošup, T., Čech, P., Skopal, T. a Lánský, J. (2015). Evaluating multilayer multimedia exploration. In Similarity Search and Applications, pages 162–169. Springer. Quigley, A. a Eades, P. (2001). Fade: Graph drawing, clustering, and visual abstraction. In Graph Drawing, pages 197–210. Springer.

52

Saaty, T. L. (1964). The minimum number of intersections in complete graphs. Proceedings of the National Academy of Sciences of the United States of America, 52(3), 688. Tunkelang, D. (1999). A numerical optimization approach to general graph drawing. PhD thesis, IBM TJ Watson Research Center. Tutte, W. T. (1963). How to draw a graph. Walshaw, C. (2001). A multilevel algorithm for force-directed graph drawing. In Graph Drawing, pages 171–182. Springer.

53

Seznam obrázků 1

Vizualizace podobnostního grafu . . . . . . . . . . . . . . . . . . .

4

1.1 1.2

Srovnání různých vizualizací stejného grafu . . . . . . . . . . . . . Intuitivní vizualizace úplného grafu o šestnácti vrcholech . . . . .

8 9

3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14

Ilustrace fyzikálního modelu částic . . . . . . . . . . . . . Rozdělení prostoru pomocí kvadrantového stromu . . . . Kvadrantový strom . . . . . . . . . . . . . . . . . . . . . Kvadrantový strom pro 1000 bodů . . . . . . . . . . . . Porovnávací kritérium . . . . . . . . . . . . . . . . . . . Rozložení grafu jagmesh1 . . . . . . . . . . . . . . . . . . Redukce grafu pomocí minimálního vrcholového pokrytí . Redukce grafu pomocí maximálního párování . . . . . . . Redukce grafu . . . . . . . . . . . . . . . . . . . . . . . . Uváznutí v lokálním minimu (jagmesh1) . . . . . . . . . Rozdělení prostoru pomocí oktantového stromu . . . . . Srovnání kvality vizualizací po 400 ms výpočtu . . . . . Uváznutí v lokálním minimu (P30 ) . . . . . . . . . . . . . Srovnání výkonnosti algoritmů . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

11 15 15 16 17 19 21 22 23 24 25 27 28 31

4.1 4.2 4.3 4.4

Působení síly fa∗ vzhledem ke vzdálenosti částic Graf s různými délkami hran . . . . . . . . . . . Vizualizace úplného grafu K100 . . . . . . . . . Srovnání jednoduchého a k-NN prořezávání . . .

. . . .

. . . .

. . . .

. . . .

. . . .

33 33 34 35

5.1 5.2 5.3

Volání metody Coarse . . . . . . . . . . . . . . . . . . . . . . . . Testovací prostředí pro graf s 50 obrázky . . . . . . . . . . . . . . Možné napojení na explorační portál . . . . . . . . . . . . . . . .

37 42 43

6.1

3D webová vizualizace . . . . . . . . . . . . . . . . . . . . . . . .

47

54

. . . .

. . . .

. . . .

. . . .

. . . .

Přílohy Přiložené CD obsahuje následující obsah: • tento text ve formátu PDF, • komponentu určenou pro výpočet vizualizace grafu včetně testovacího prostředí, • webového klient pro prezentaci rozložení ve 3D prostoru.

55