Submitted by Dominik Joe Pantůček (bez ověření) on Po, 2018-12-31 15:32
Tento příspěvek se zabývá novými možnostmi efektivního obarvování abstraktních grafických struktur (map) studovaný autory [1]. Autoři dávají volně k dispozici výsledky svého výzkumu[2]. S využitím důkazu [3] a aplikací zjištění [4] ukážeme možnost rychlého obarvení výše zmíněné mapy v rámci slabšího teorému [5].
Upozornění: Pro účely tohoto výzkumu nejsou uzavřené oblasti glyfů považovány za součást mapy.
Neobarvená mapa byla nejprve vyexportována jako bitmapa v maximálním možném rozlišení. Toto rozlišení bylo určeno jako limitní rozlišení, kdy již další zvětšení tvoří jen čtvercové struktury místo obrazových bodů.
Tato vyexportovaná bitmapa byla ohodnocena prahovým algoritmem tak, že všechny body s hodnotou menší než 225 byly označeny kódem 0 a s hodnotou stejnou či větší pak kódem 16777215. Kódy odpovídají barvám v BGR prostoru v LE kódování. Prahová hodnota 225 byla určena měřením estetické reakce testovacích subjektů.
Pro další operace byl implementován software v moderním dialektu jazyka Scheme [6].
V nově získané bitmapě byly iterativně označeny souvislé oblasti kódu 16777215 a každé byl přiřazen nový kód dle pravidla (+ (* w y) x). Následně byly tyto oblasti rozšířeny do přilehlých obrazových bodů s kódem nula. Tato operace proběhla postupně vždy jeden bod pro jeden region tak, aby nedošlo k hladovému roztáhnutí oblastí ve směru os souřadnic. Všechny body byly vyplněny v devíti iteracích.
Z takto pročištěné mapy byl sestaven seznam hran neorientovaného grafu, kdy každá plocha je reprezentována uzlem a sousedství ploch je pak vyjádřeno hranou tohoto grafu. Vhodným seřazením uzlů dle počtu navazujících hran, stochastickou alokací barev ze zadané množiny a s nutností - byť drobného - backtrackingu, byl graf obarven pěti barevnými kódy.
Rešerší z dalších prací autorú [7] byly vybrány nejvhodnější možné barvy pro zobrazení a čtyři finální barvy pak byly opět určeny měřením estetické reakce testovacích subjektů.
Výsledek algoritmu je možné vidět na [8] a [9].
Budoucí práce by se měly zaměřit na praktickou aplikaci kvadratického algoritmu pro obarvení pouze 4 barvami [4]. Nelze vyloučit, že ačkoliv chromatické číslo mapy [2] je 4 (uvádíme bez důkazů), je možné, že estetické nároky znemožní vizuálně atraktivní obarvení pouze čtyřmi barvami.
Efektivní obarvování abstraktních grafických struktur
Tento příspěvek se zabývá novými možnostmi efektivního obarvování abstraktních grafických struktur (map) studovaný autory [1]. Autoři dávají volně k dispozici výsledky svého výzkumu[2]. S využitím důkazu [3] a aplikací zjištění [4] ukážeme možnost rychlého obarvení výše zmíněné mapy v rámci slabšího teorému [5].
Upozornění: Pro účely tohoto výzkumu nejsou uzavřené oblasti glyfů považovány za součást mapy.
Neobarvená mapa byla nejprve vyexportována jako bitmapa v maximálním možném rozlišení. Toto rozlišení bylo určeno jako limitní rozlišení, kdy již další zvětšení tvoří jen čtvercové struktury místo obrazových bodů.
Tato vyexportovaná bitmapa byla ohodnocena prahovým algoritmem tak, že všechny body s hodnotou menší než 225 byly označeny kódem 0 a s hodnotou stejnou či větší pak kódem 16777215. Kódy odpovídají barvám v BGR prostoru v LE kódování. Prahová hodnota 225 byla určena měřením estetické reakce testovacích subjektů.
Pro další operace byl implementován software v moderním dialektu jazyka Scheme [6].
V nově získané bitmapě byly iterativně označeny souvislé oblasti kódu 16777215 a každé byl přiřazen nový kód dle pravidla (+ (* w y) x). Následně byly tyto oblasti rozšířeny do přilehlých obrazových bodů s kódem nula. Tato operace proběhla postupně vždy jeden bod pro jeden region tak, aby nedošlo k hladovému roztáhnutí oblastí ve směru os souřadnic. Všechny body byly vyplněny v devíti iteracích.
Z takto pročištěné mapy byl sestaven seznam hran neorientovaného grafu, kdy každá plocha je reprezentována uzlem a sousedství ploch je pak vyjádřeno hranou tohoto grafu. Vhodným seřazením uzlů dle počtu navazujících hran, stochastickou alokací barev ze zadané množiny a s nutností - byť drobného - backtrackingu, byl graf obarven pěti barevnými kódy.
Rešerší z dalších prací autorú [7] byly vybrány nejvhodnější možné barvy pro zobrazení a čtyři finální barvy pak byly opět určeny měřením estetické reakce testovacích subjektů.
Výsledek algoritmu je možné vidět na [8] a [9].
Budoucí práce by se měly zaměřit na praktickou aplikaci kvadratického algoritmu pro obarvení pouze 4 barvami [4]. Nelze vyloučit, že ačkoliv chromatické číslo mapy [2] je 4 (uvádíme bez důkazů), je možné, že estetické nároky znemožní vizuálně atraktivní obarvení pouze čtyřmi barvami.
[1] https://bugemos.com/
[2] https://www.bugemos.com/?q=node/589
[3] Wikipedia contributors. (2018, December 18). Four color theorem. In Wikipedia, The Free Encyclopedia. Retrieved 09:19, December 31, 2018, from https://en.wikipedia.org/w/index.php?title=Four_color_theorem&oldid=874329529
[4] http://people.math.gatech.edu/~thomas/PAP/fcstoc.pdf
[5] Wikipedia contributors. (2018, August 14). Five color theorem. In Wikipedia, The Free Encyclopedia. Retrieved 09:19, December 31, 2018, from https://en.wikipedia.org/w/index.php?title=Five_color_theorem&oldid=854955535
[6] http://racket-lang.org/
[7] https://www.bugemos.com/?q=taxonomy/term/51
[8] http://joe.cz/bugemos/Stresova-Zlomalovanka-5ct-hd.png
[9] http://joe.cz/bugemos/Stresova-Zlomalovanka-5ct-full.png