ZABAGED mapy pro OziExplorer - další generace
Ahoj,
dostal jsem se na toto fórum a vidím, že jsou tu k dispozici mapy ZABAGED ZM10 s turistickými trasami. Mapy se mi velmi líbí a tak bych rád přispěl svoji troškou.
Před tím, ale než začnu, bych se chtěl zeptat na vaše názory. Osobně bych chtěl vytvořit něco jako ZABAGED mapy pro OziExplorer od uživatele Kocour Mikeš - https://www.svetmobilne.cz/forum/showthread.php/36749-Mapy-na-MEGA-prehledny-seznam-bez-pokecu
Mám několik nápadů na vylepšení mapy:
1. Více zoomů (přiblížení v jednom OZF souboru) - OZF technicky umožňuje vložit do souboru jiný obrázek pro každé přiblížení.
2. Přidání cyklotras - osobně používám podobně často jako turistické trasy.
3. Přidání stínování (hillshading) - mapa vypadá plastičtěji (již navrženo).
4. Běžkařské trasy - na mapy.cz lze zobrazit i trasy pro běžkaře, využili byste tuto vrstvu?
5. Vyhlazování - WMS služba nepoužívá vyhlazování, toto lze obejít tím, že se stáhne větší obrázek a následně se zmenší.
6. Vyšší stupeň detailu (přiblížení) - technicky nic složitého, ptám se na názor, zda by toto někdo využil.
7. Waypointy z mapy.cz (zastávky, stanice, zajímavá POI...) nebo turistika.cz přidány přímo do mapy.
Nějaké další nápady? Připomínky? Požadavky? Má vůbec cenu se něčemu takovému věnovat?
dostal jsem se na toto fórum a vidím, že jsou tu k dispozici mapy ZABAGED ZM10 s turistickými trasami. Mapy se mi velmi líbí a tak bych rád přispěl svoji troškou.
Před tím, ale než začnu, bych se chtěl zeptat na vaše názory. Osobně bych chtěl vytvořit něco jako ZABAGED mapy pro OziExplorer od uživatele Kocour Mikeš - https://www.svetmobilne.cz/forum/showthread.php/36749-Mapy-na-MEGA-prehledny-seznam-bez-pokecu
Mám několik nápadů na vylepšení mapy:
1. Více zoomů (přiblížení v jednom OZF souboru) - OZF technicky umožňuje vložit do souboru jiný obrázek pro každé přiblížení.
2. Přidání cyklotras - osobně používám podobně často jako turistické trasy.
3. Přidání stínování (hillshading) - mapa vypadá plastičtěji (již navrženo).
4. Běžkařské trasy - na mapy.cz lze zobrazit i trasy pro běžkaře, využili byste tuto vrstvu?
5. Vyhlazování - WMS služba nepoužívá vyhlazování, toto lze obejít tím, že se stáhne větší obrázek a následně se zmenší.
6. Vyšší stupeň detailu (přiblížení) - technicky nic složitého, ptám se na názor, zda by toto někdo využil.
7. Waypointy z mapy.cz (zastávky, stanice, zajímavá POI...) nebo turistika.cz přidány přímo do mapy.
Nějaké další nápady? Připomínky? Požadavky? Má vůbec cenu se něčemu takovému věnovat?
Zkoušel jsem vytvořit první testovací mapu:
[code]https://mega.co.nz/#!p1oAybQC!cHn6a1Sy4O8RJ8PM0vT_hUouo0MIHgZ2TyoSRtebgMM (8.0 MB)[/code]
Mapa obsahuje tři přiblížení: 100% (1 mpx), 50% a 25% (zoom 15 - 13 na mapy.cz) a tyto vrstvy:
Další nastavení:
Pro základní ZABAGED vrstvu je použito vyhlazování - stáhne se větší obrázek, který se následně zmenší.
Díval jsem se na běžkařské trasy a zdá se, že Seznam opět změnil rozhranní, takže chvíli potrvá, než se podaří dekódovat jejich zobrazování.
Zápis do OZF řeším vlastním programem, což nese výhodu, že mohu zapisovat, co chci, ne jen vrstvy, které vznikly zmenšením té hlavní. Osobně používám Androzic a tam si s třemi přiblíženími vystačím.
Opět prosím o připomínky, návrhy, potřehy. Díky
[code]https://mega.co.nz/#!p1oAybQC!cHn6a1Sy4O8RJ8PM0vT_hUouo0MIHgZ2TyoSRtebgMM (8.0 MB)[/code]
Mapa obsahuje tři přiblížení: 100% (1 mpx), 50% a 25% (zoom 15 - 13 na mapy.cz) a tyto vrstvy:
- ZABAGED ZM10
- stínování
- turistické trasy
- cyklotrasy
- POI
Další nastavení:
- počet přiblížení: 3
- intenzita stínování: 50%
- počet barev: 128
- dithering: vypnuto
Pro základní ZABAGED vrstvu je použito vyhlazování - stáhne se větší obrázek, který se následně zmenší.
Díval jsem se na běžkařské trasy a zdá se, že Seznam opět změnil rozhranní, takže chvíli potrvá, než se podaří dekódovat jejich zobrazování.
Zápis do OZF řeším vlastním programem, což nese výhodu, že mohu zapisovat, co chci, ne jen vrstvy, které vznikly zmenšením té hlavní. Osobně používám Androzic a tam si s třemi přiblíženími vystačím.
Opět prosím o připomínky, návrhy, potřehy. Díky
V URI na Seznam Mapy je proti drivejsku pridany navic "!" (vykricnik). Treba to bude ono.
http://www.mapy.cz/#[COLOR="#EE82EE"]![/COLOR]x=13.528930&y=50.416294&z=7
Stahuji v MapGen 2.5 a jde to. I kdyz jsem trasy neztahoval.
Autor mi psal, ze to prilezitostne opravi.
http://www.mapy.cz/#[COLOR="#EE82EE"]![/COLOR]x=13.528930&y=50.416294&z=7
Stahuji v MapGen 2.5 a jde to. I kdyz jsem trasy neztahoval.
Autor mi psal, ze to prilezitostne opravi.
[QUOTE=jiri.pokorny.jr;355673]Zkoušel jsem vytvořit první testovací mapu:
Pro základní ZABAGED vrstvu je použito vyhlazování - stáhne se větší obrázek, který se následně zmenší.
Opět prosím o připomínky, návrhy, potřehy. Díky[/QUOTE]
Tohle ovšem není přimo mapa ZABAGED ale RZM10 odvozená ze ZABAGED - rozdíl je především v aktuálnosti, vlastní mapa ZABAGED je samozřejmě mnohem aktuálnější, do odvozené mapy se veškeré změny promítají až větším či menším zpožděním, je to pochopitelné, vektorová data ZABAGED se aktualizují mnohem jednodušeji než rastrová u odvozené mapy. ZABAGED navíc obsahuje četné další datové vrstvy jako např. jména ulic atd., ty by mi taky dost chyběly
Pro základní ZABAGED vrstvu je použito vyhlazování - stáhne se větší obrázek, který se následně zmenší.
Opět prosím o připomínky, návrhy, potřehy. Díky[/QUOTE]
Tohle ovšem není přimo mapa ZABAGED ale RZM10 odvozená ze ZABAGED - rozdíl je především v aktuálnosti, vlastní mapa ZABAGED je samozřejmě mnohem aktuálnější, do odvozené mapy se veškeré změny promítají až větším či menším zpožděním, je to pochopitelné, vektorová data ZABAGED se aktualizují mnohem jednodušeji než rastrová u odvozené mapy. ZABAGED navíc obsahuje četné další datové vrstvy jako např. jména ulic atd., ty by mi taky dost chyběly
[QUOTE=zany;355677]Tohle ovšem není přimo mapa ZABAGED ale RZM10 odvozená ze ZABAGED - rozdíl je především v aktuálnosti, vlastní mapa ZABAGED je samozřejmě mnohem aktuálnější, do odvozené mapy se veškeré změny promítají až větším či menším zpožděním, je to pochopitelné, vektorová data ZABAGED se aktualizují mnohem jednodušeji než rastrová u odvozené mapy. ZABAGED navíc obsahuje četné další datové vrstvy jako např. jména ulic atd., ty by mi taky dost chyběly[/QUOTE]
Aha, vůbec jsem netušil, že je mezi tímto rozdíl. Počítal jsem s tím, že použiji ZM10, ZM25, ZM50 a ZM200 pro různá přiblížení. Díval jsem se na ZABAGED v Geoprohlížeči a zkusím si s tím pohrát.
Aha, vůbec jsem netušil, že je mezi tímto rozdíl. Počítal jsem s tím, že použiji ZM10, ZM25, ZM50 a ZM200 pro různá přiblížení. Díval jsem se na ZABAGED v Geoprohlížeči a zkusím si s tím pohrát.
Zkusil jsem vytvořit další testovací mapu. Tentokráte snad se již jedná o ZABAGED:
[code]https://mega.co.nz/#!x8oEVSID!Gq7XTSz8pTtq7kh_A1VOoAzWYaxv6fafPc815Qx2Aqc (6.2 MB)[/code]
Tady je náhled (pouze 100% zoom): http://imageshack.us/photo/my-images/706/fyi1.jpg/
Použil jsem všechny vrstvy, které se zobrazují v Geoprohlížeči a přidal vrstevnice.
Zastávky se již nezobrazují v nižších přiblíženích.
Počet přiblížení je nastaven na 4 (100 %, 50 %, 25 % a 12,5%).
Mapa se mi začala "dlaždicovat" (bílé okraje okolo dlaždic), na toto se ještě zaměřím.
Lyžařské stopy stále nejsou podporovány.
[code]https://mega.co.nz/#!x8oEVSID!Gq7XTSz8pTtq7kh_A1VOoAzWYaxv6fafPc815Qx2Aqc (6.2 MB)[/code]
Tady je náhled (pouze 100% zoom): http://imageshack.us/photo/my-images/706/fyi1.jpg/
Použil jsem všechny vrstvy, které se zobrazují v Geoprohlížeči a přidal vrstevnice.
Zastávky se již nezobrazují v nižších přiblíženích.
Počet přiblížení je nastaven na 4 (100 %, 50 %, 25 % a 12,5%).
Mapa se mi začala "dlaždicovat" (bílé okraje okolo dlaždic), na toto se ještě zaměřím.
Lyžařské stopy stále nejsou podporovány.
Zkoušel jsem se dostat k informacím o lyžařských stopách z mapy.cz. Seznam dělá vše proto, aby dala nebyla jednoduše čitelná. Před používáním FastRPC, bylo možné informace možné získat jako čisté XML. Nyní je použita obálka volání procedur FastRPC a nějaké divné kódování seznamu souřadnic do řetězce.
Nyní zápasím s tím, aby se cyklotrasy kreslily podobně jako turistické trasy v závislosti na přiblížení.
Převzal jsem definici vrstev z Geoprohlížeče, ale tím musím skládat dohromady 11 vrstev, což hodně zpomaluje, před vytvořením mapy prvního velkého města se ještě zaměřím na optimalizaci vrstev.
Mřížování je stále problém. Budu řešit.
Nyní zápasím s tím, aby se cyklotrasy kreslily podobně jako turistické trasy v závislosti na přiblížení.
Převzal jsem definici vrstev z Geoprohlížeče, ale tím musím skládat dohromady 11 vrstev, což hodně zpomaluje, před vytvořením mapy prvního velkého města se ještě zaměřím na optimalizaci vrstev.
Mřížování je stále problém. Budu řešit.
Dělal jsem další pokusy s mapou.
Takto bych chtěl, aby vypadala konečná verze mapy. Odkaz na stažení:
[code]https://mega.co.nz/#!9852nIxK!PwtGlWFu8u8nk-AK-r1vcBHxeWBrabcjNqMQQP45Yrk (68.5 MB)[/code]
Mapa obsahuje přiblížení 1mpx, 2mpx, 4mpx a 8 mpx (čtyři různá přiblížení)
Dále se zaměřím na redukci barev, abych mohl mapu ještě změnšit. Aktuálně používám 128 barev, chtěl bych zkusit 64.
Pro redukci barev používám NeuQuant, se kterým mám dobré výsledky. Pracuji v RGB barevném prostoru, ale někde jsem četl, že HSL by měl přinést lepší výsledky. Taktéž optimalizace algoritmu na hledání nejbližší barvy je v mém zájmu.
- Zredukoval jsem počet vrstev, které skládám z 11 na 7, což hodně pomohlo s rychlostí.
- Odstranil jsem “dlaždicování” z mapy.
- Zjistil jsem, že mapy.cz začaly pro některé vrstvy vracet HTTP kód 302 - .NET framework s tím měl nějaké problémy.
- Kreslení lyžařských stezek by nyní mělo fungovat.
Takto bych chtěl, aby vypadala konečná verze mapy. Odkaz na stažení:
[code]https://mega.co.nz/#!9852nIxK!PwtGlWFu8u8nk-AK-r1vcBHxeWBrabcjNqMQQP45Yrk (68.5 MB)[/code]
Mapa obsahuje přiblížení 1mpx, 2mpx, 4mpx a 8 mpx (čtyři různá přiblížení)
Dále se zaměřím na redukci barev, abych mohl mapu ještě změnšit. Aktuálně používám 128 barev, chtěl bych zkusit 64.
Pro redukci barev používám NeuQuant, se kterým mám dobré výsledky. Pracuji v RGB barevném prostoru, ale někde jsem četl, že HSL by měl přinést lepší výsledky. Taktéž optimalizace algoritmu na hledání nejbližší barvy je v mém zájmu.
No, mapa je to pekna, do PDA, jak delana. Ja to resil 3 samostatnymi mapami, protoze pri zmensovani se zmensi i text.
Jen az bude cas, zajima me toto:
1. Více zoomů (přiblížení v jednom OZF souboru) - OZF technicky umožňuje vložit do souboru jiný obrázek pro každé přiblížení.
Jak se to sakra dela?
vkb
Jen az bude cas, zajima me toto:
1. Více zoomů (přiblížení v jednom OZF souboru) - OZF technicky umožňuje vložit do souboru jiný obrázek pro každé přiblížení.
Jak se to sakra dela?
vkb
[QUOTE=vkb;355689]
1. Více zoomů (přiblížení v jednom OZF souboru) - OZF technicky umožňuje vložit do souboru jiný obrázek pro každé přiblížení.
Jak se to sakra dela?
vkb[/QUOTE]
Zápis do OZF řeším vlastním programem. Podařilo se mi totiž získat specifikaci pro nešifrovaný OZF2 soubor, takže nevytvářím pomocný PNG / JPEG soubor, ale zapisuji přímo OZF. Mojí hlavní motivací bylo, že IMG2OZF nedokáže (nedokázal, když jsem to zkoušel) vytvořit mapu z obrázku, který se nevejde do paměti, takže teď mohu vytvořit pohodlně mapu větší než 30000 × 30000 pixelů.
Dříve jsem také zapisoval pouze hlavní obrázek a další vrstvy (zoomy) jsem pouze zmenšoval, ale říkal jsem si, že technicky nebude těžké podstrčit konvertoru více různých obrázků pro každý zoom.
Hlavní problém je v tom, že mapy vytvořené pomocí IMG2OZF jsou o něco menší, ale snažím se tento problém vyřešit lepší redukcí barev (NeuQuant). Dalším problémem je také to, že OZF využívá omezený počet barev (max 256) a barevná redukce není zrovna nejjednodušší na implementaci.
Zkoušel jsem dnes začít se stahováním potřebných dlaždic a jedná se asi o dva miliony, takže výsledek bude chvíli trvat.
1. Více zoomů (přiblížení v jednom OZF souboru) - OZF technicky umožňuje vložit do souboru jiný obrázek pro každé přiblížení.
Jak se to sakra dela?
vkb[/QUOTE]
Zápis do OZF řeším vlastním programem. Podařilo se mi totiž získat specifikaci pro nešifrovaný OZF2 soubor, takže nevytvářím pomocný PNG / JPEG soubor, ale zapisuji přímo OZF. Mojí hlavní motivací bylo, že IMG2OZF nedokáže (nedokázal, když jsem to zkoušel) vytvořit mapu z obrázku, který se nevejde do paměti, takže teď mohu vytvořit pohodlně mapu větší než 30000 × 30000 pixelů.
Dříve jsem také zapisoval pouze hlavní obrázek a další vrstvy (zoomy) jsem pouze zmenšoval, ale říkal jsem si, že technicky nebude těžké podstrčit konvertoru více různých obrázků pro každý zoom.
Hlavní problém je v tom, že mapy vytvořené pomocí IMG2OZF jsou o něco menší, ale snažím se tento problém vyřešit lepší redukcí barev (NeuQuant). Dalším problémem je také to, že OZF využívá omezený počet barev (max 256) a barevná redukce není zrovna nejjednodušší na implementaci.
Zkoušel jsem dnes začít se stahováním potřebných dlaždic a jedná se asi o dva miliony, takže výsledek bude chvíli trvat.
Protože už se tu delší dobu nic neudálo, chtěl jsem napsat, jaký je stav projektu. Pracuje se. Mám finalizované všechny vrstvy, které bych chtěl použít, mapa se bude skládat ze sedmi vrstev a bude to zoom 15.
Drobný problém je v tom, že dlaždic, ze kterých se bude mapa skládat jsou dva milióny, což chvíli trvá, než se všechny stáhnou. Přemýšlím, že stahování odložím do chladnějších měsíců kvůli zahřívání počítače.
Ještě bych chtěl implementovat "vynucené barvy", protože ne vždy je redukce barev provedena úplně ideálně, mezitím ale stahovat dlaždice mohu, takže to snad stihnu současně.
No, a zatím největší nedořešené rozhodnutí je, jak rozdělit republiku na jednotlivé mapy. Zda podle čtverců jako pravidelnou síť nebo použít třeba rozložení, které používá SHOCART u map 1:50000. Tohle se ještě musí dořešit, zajímá mne váš názor.
Máte ještě nějaké požadavky, než začnu tvořit finální mapu?
Drobný problém je v tom, že dlaždic, ze kterých se bude mapa skládat jsou dva milióny, což chvíli trvá, než se všechny stáhnou. Přemýšlím, že stahování odložím do chladnějších měsíců kvůli zahřívání počítače.
Ještě bych chtěl implementovat "vynucené barvy", protože ne vždy je redukce barev provedena úplně ideálně, mezitím ale stahovat dlaždice mohu, takže to snad stihnu současně.
No, a zatím největší nedořešené rozhodnutí je, jak rozdělit republiku na jednotlivé mapy. Zda podle čtverců jako pravidelnou síť nebo použít třeba rozložení, které používá SHOCART u map 1:50000. Tohle se ještě musí dořešit, zajímá mne váš názor.
Máte ještě nějaké požadavky, než začnu tvořit finální mapu?
Me vice vyhovuji ctverce, treba 10 x 10 km.
Lepe se kdyz tak slozi do vetsi, s delenim velkych map to uz je horsi. Musel jsem to dela treba pres bmp a znova kalibrovat, program (nebo muj PC) uz to neumel.
Ctverce se musi prekryvat, treba o cca 500 m (jak vyjdou zakladni ctverce) mam nemecke mapy, kde se neprekryvaji a neni to ono.
Lepe se kdyz tak slozi do vetsi, s delenim velkych map to uz je horsi. Musel jsem to dela treba pres bmp a znova kalibrovat, program (nebo muj PC) uz to neumel.
Ctverce se musi prekryvat, treba o cca 500 m (jak vyjdou zakladni ctverce) mam nemecke mapy, kde se neprekryvaji a neni to ono.
Ahoj,
tak jsem se zase na chvíli dostal k mapám. Dlaždice poctivě stahuju, ale trvá to dlouho. Strašně dlouho.
Před vytvořením finální mapy jsem se chtěl dostat ještě k několika věcem:
První z nich je možnost vynutit některé barvy v OZF, protože tento formát používá omezenou barevnou paletu a ne vždy jsou barvy vybrány úplně ideálně. I přes to, že barvy můj algoritmus optimalizuje podle mne podstatně lépe než IMG2OZF, přesto se mi občas stalo, že výsledek nebyl úplně ideální. Přidal jsem tedy možnost vynutit některé barvy. Nejvíce je to viditelné na velkých mapách a turistických značkách na nich, protože značky netvoří velkou plochu na mapě a občas mohou být vyhodnoceny, že jejich barva není dostatečně důležitá vzhledem k celkové ploše. Důležitá ale je. Nadefinoval jsem tedy několik barev, které budou vynucené:
[code]
#B218B5 - cyklo
#0013C0 - modra
#1A8A00 - zelena
#CC0000 - cervena
#E0C412 - zluta
#000000 - cerna
#FFFFFF - bila
#C5DDA5 - lesy
#83B1D0 - vodni plocha
#ECE0C9 - zastavena plocha 1
#F2F1E1 - zastavena plocha 2
[/code]
Dalším velkým problémem bylo hledání nejbližší barvy. Naimplementoval jsem cvičně v C# několik algoritmů pro srovnání:
[code]Algorithm Speed (ms) SUM diff^2 SUM diff Complexity
=============================================================================
Normal , 3016,6032 - 1034173527, 44752521 O(n)
Updated , 1648,3296 - 1034173527, 44752351 O(n)
Octree , 443,0886 - 1624739258, 55307568 O(log n)
OctreePatch , 416,0832 - 1854775253, 59535619 O(log n)
Cube(S=4) , 717,6435 - 1438147552, 52417586 O(1)
CubeAdv(S=4) , 751,6503 - 1438147552, 52417586 O(1)
Cube(S=8) , 2365,4730 - 1074512522, 45822748 O(1)
CubeAdv(S=8) , 2398,4796 - 1074512522, 45822748 O(1)
Cube(S=16) , 8524,2045 - 1069207642, 45963326 O(1)
CubeAdv(S=16) , 8981,7960 - 1069207642, 45963326 O(1)
AdaptCube(S=32,B=4) , 280,0560 - 1034747751, 44763293 O(1)
AdaptCubeOptim(S=32,B=4), 257,5515 - 1034198578, 44753492 O(1) <== vítěz
ThreeTree , 149,5299 - 4870269614, 80099112 O(log n)
KdTree2 , 8663,2323 - 1569903844, 55401166 O(log n)
KdTreeLibrary , 21788,2085 - 1044098866, 45652250 O(log n)
Null , 61,4877 - 49939799675, 323097719 O(1)
Random , 94,9810 - 31863572090, 252510650 O(1)
[/code]
První algoritmus jsem používal až do teď. Pro hledanou barvu prochází celou paletu a hledá nejbližší barvu, používá cache pro hledání barvy, přesto není ideální.
Vyzkoušel jsem algoritmus, který hledal v seřazeném poli (v tabulce Updated), ale ten zlepšil rychlost jen o polovinu. Zkoušel jsem vlastní zprzněnou implementaci Octree, ale výsledky byly pouze uspokojivé. Zkoušel jsem rozdělení prostoru na krychle a v případě nenalezení barvy blízko, se prohledávalo okolí. Nejvíce nadějí jsem vkládal do KDTree - http://en.wikipedia.org/wiki/K-d_tree, ale to dopadlo snad nejhůře. Věřím, že pro miliony barev by algoritmus fungoval dobře, ale omezení 256 barev přináší různá omezení a potřebu optimalizovat trochu jinak.
Nakonec jsem použil variantu k rozdělení na krychle, ale s tím, že index obsahuje pevnou velikost barev, které jsou nejbližší. Teoreticky může být tato metoda nepřesná, ale výsledky ukazují opak, navíc pevně dlouhý index pomáhá mnoha optimalizacím.
Nakonec jsem je ještě vybičoval k tomu, abych některé části kódu optimalizoval ručně pomocí MMX/SSE instrukcí. Je zajímavé, že použitím správných instrukcí, lze dost pěkně optimalizovat rychlost kódu.
Zkoušel jsem, jak velký export dokážu udělat a tady je testovací stáhnutí celé České republiky ze serveru http://map1.eu. Zkoušel jsem i větší, ale soubor mi pak neotevře Androzic. Možná časem se podívám na OZF3 formát.
[code]cr_14_map1eu.map (2 KB)
https://mega.co.nz/#!poIV0YrD!XGG5LTVLNcbiFH0QWCWxDlenxiJKorrb0GzNrgB0fNI
cr_14_map1eu.ozf (1.49 GB)
https://mega.co.nz/#!ttoXnAjT!VcNP0GgekN7KtCryRQBI5jOZkKwakRPrz7e3HzE-im8[/code]
Dále jsem optimalozoval alokaci paměti, kterou zlib potřebuje pro deflate. Překvapivě si knihovna alokuje celkem dost paměti a poměrně často, navíc se tato operace volá pro zápis každé dlaždice. Paměť tedy alokuji pouze jednou a pak ji používám opakovaně znovu a znovu.
Přemýšlím nad několika dalšími vylepšeními:
Intenzita barevných kanálů
Protože lidské oko vnímá různé barevné kanály jinak - http://en.wikipedia.org/wiki/Grayscale#Converting_color_to_grayscale, přemýšlím, že bych toto použil i pro optimalizaci vytváření barevné palety a pak ke hledání nejbližší barvy. Otázka je, zda to nějak výrazně ovlivní vzhled nebo kompresi.
Alternativní implementace Deflate algoritmu
OZF používá pro kompresi Deflate algoritmus. Nejlepší si mi zdálo použít implementaci, kterou používá zlib, protože ji také používá libpng pro zápis PNG obrázků.
Našel jsem zajímavou optimalizaci napsanou v assembleru http://www.gildor.org/en/projects/zlib. Tento patch jsem použil a výkon se slušně zvýšil.
Další cestou, kterou se lze vydat, je použít ZOPFLI od lidí z Google - https://code.google.com/p/zopfli/. Výhody a nevýhody jsou jasné - komprese je lepší o 2 - 3 %, čas potřebný na kompresi je 100× větší. ZOPFLI se mi podařilo zkompilovat, ale nefunguje spolehlivě, navíc bych tímto přišel o
Ztrátová komprese
Možná si řeknete, co je to za pitomost? Deflate použitý v OZF je bezztrátový (losseless) algoritmus, stejně tak PNG formát, který jej používá. Výzkum na http://membled.com/work/apps/lossy_png/ ukazuje, že lze uložit ztrátovou kompresi i pro PNG formát. Tady je jiná implementace v Go: https://github.com/foobaz/lossypng/blob/master/lossypng.go. Bohužel ani jedna není přímo použitelná pro mne - první nefunguje na obrázky s paletou, druhá využívá triků při ukládání PNG. Zkoušel jsem si implementovat několik algoritmů, které by měly pomoci snížit velikost, ale zatím bez výraznější pomoci
Možná tento výzkum využiju pro optimalizaci výstupu do SQlite formátu.
Optimalizace JPEG
Moje takové malé soukromé přání je vytvořit i mapy pro Trek Buddyho, ukázalo se, že lepší je JPEG. Pár možností, jak ještě zmenšit JPEG je, ale zatím jsem nenašel takový, který by byl binárně kompatibilní.
Pokud máte nějaké další nápady na vylepšení nebo vás cokoliv dalšího napadne, napište.
tak jsem se zase na chvíli dostal k mapám. Dlaždice poctivě stahuju, ale trvá to dlouho. Strašně dlouho.
Před vytvořením finální mapy jsem se chtěl dostat ještě k několika věcem:
První z nich je možnost vynutit některé barvy v OZF, protože tento formát používá omezenou barevnou paletu a ne vždy jsou barvy vybrány úplně ideálně. I přes to, že barvy můj algoritmus optimalizuje podle mne podstatně lépe než IMG2OZF, přesto se mi občas stalo, že výsledek nebyl úplně ideální. Přidal jsem tedy možnost vynutit některé barvy. Nejvíce je to viditelné na velkých mapách a turistických značkách na nich, protože značky netvoří velkou plochu na mapě a občas mohou být vyhodnoceny, že jejich barva není dostatečně důležitá vzhledem k celkové ploše. Důležitá ale je. Nadefinoval jsem tedy několik barev, které budou vynucené:
[code]
#B218B5 - cyklo
#0013C0 - modra
#1A8A00 - zelena
#CC0000 - cervena
#E0C412 - zluta
#000000 - cerna
#FFFFFF - bila
#C5DDA5 - lesy
#83B1D0 - vodni plocha
#ECE0C9 - zastavena plocha 1
#F2F1E1 - zastavena plocha 2
[/code]
Dalším velkým problémem bylo hledání nejbližší barvy. Naimplementoval jsem cvičně v C# několik algoritmů pro srovnání:
[code]Algorithm Speed (ms) SUM diff^2 SUM diff Complexity
=============================================================================
Normal , 3016,6032 - 1034173527, 44752521 O(n)
Updated , 1648,3296 - 1034173527, 44752351 O(n)
Octree , 443,0886 - 1624739258, 55307568 O(log n)
OctreePatch , 416,0832 - 1854775253, 59535619 O(log n)
Cube(S=4) , 717,6435 - 1438147552, 52417586 O(1)
CubeAdv(S=4) , 751,6503 - 1438147552, 52417586 O(1)
Cube(S=8) , 2365,4730 - 1074512522, 45822748 O(1)
CubeAdv(S=8) , 2398,4796 - 1074512522, 45822748 O(1)
Cube(S=16) , 8524,2045 - 1069207642, 45963326 O(1)
CubeAdv(S=16) , 8981,7960 - 1069207642, 45963326 O(1)
AdaptCube(S=32,B=4) , 280,0560 - 1034747751, 44763293 O(1)
AdaptCubeOptim(S=32,B=4), 257,5515 - 1034198578, 44753492 O(1) <== vítěz
ThreeTree , 149,5299 - 4870269614, 80099112 O(log n)
KdTree2 , 8663,2323 - 1569903844, 55401166 O(log n)
KdTreeLibrary , 21788,2085 - 1044098866, 45652250 O(log n)
Null , 61,4877 - 49939799675, 323097719 O(1)
Random , 94,9810 - 31863572090, 252510650 O(1)
[/code]
První algoritmus jsem používal až do teď. Pro hledanou barvu prochází celou paletu a hledá nejbližší barvu, používá cache pro hledání barvy, přesto není ideální.
Vyzkoušel jsem algoritmus, který hledal v seřazeném poli (v tabulce Updated), ale ten zlepšil rychlost jen o polovinu. Zkoušel jsem vlastní zprzněnou implementaci Octree, ale výsledky byly pouze uspokojivé. Zkoušel jsem rozdělení prostoru na krychle a v případě nenalezení barvy blízko, se prohledávalo okolí. Nejvíce nadějí jsem vkládal do KDTree - http://en.wikipedia.org/wiki/K-d_tree, ale to dopadlo snad nejhůře. Věřím, že pro miliony barev by algoritmus fungoval dobře, ale omezení 256 barev přináší různá omezení a potřebu optimalizovat trochu jinak.
Nakonec jsem použil variantu k rozdělení na krychle, ale s tím, že index obsahuje pevnou velikost barev, které jsou nejbližší. Teoreticky může být tato metoda nepřesná, ale výsledky ukazují opak, navíc pevně dlouhý index pomáhá mnoha optimalizacím.
Nakonec jsem je ještě vybičoval k tomu, abych některé části kódu optimalizoval ručně pomocí MMX/SSE instrukcí. Je zajímavé, že použitím správných instrukcí, lze dost pěkně optimalizovat rychlost kódu.
Zkoušel jsem, jak velký export dokážu udělat a tady je testovací stáhnutí celé České republiky ze serveru http://map1.eu. Zkoušel jsem i větší, ale soubor mi pak neotevře Androzic. Možná časem se podívám na OZF3 formát.
[code]cr_14_map1eu.map (2 KB)
https://mega.co.nz/#!poIV0YrD!XGG5LTVLNcbiFH0QWCWxDlenxiJKorrb0GzNrgB0fNI
cr_14_map1eu.ozf (1.49 GB)
https://mega.co.nz/#!ttoXnAjT!VcNP0GgekN7KtCryRQBI5jOZkKwakRPrz7e3HzE-im8[/code]
Dále jsem optimalozoval alokaci paměti, kterou zlib potřebuje pro deflate. Překvapivě si knihovna alokuje celkem dost paměti a poměrně často, navíc se tato operace volá pro zápis každé dlaždice. Paměť tedy alokuji pouze jednou a pak ji používám opakovaně znovu a znovu.
Přemýšlím nad několika dalšími vylepšeními:
Intenzita barevných kanálů
Protože lidské oko vnímá různé barevné kanály jinak - http://en.wikipedia.org/wiki/Grayscale#Converting_color_to_grayscale, přemýšlím, že bych toto použil i pro optimalizaci vytváření barevné palety a pak ke hledání nejbližší barvy. Otázka je, zda to nějak výrazně ovlivní vzhled nebo kompresi.
Alternativní implementace Deflate algoritmu
OZF používá pro kompresi Deflate algoritmus. Nejlepší si mi zdálo použít implementaci, kterou používá zlib, protože ji také používá libpng pro zápis PNG obrázků.
Našel jsem zajímavou optimalizaci napsanou v assembleru http://www.gildor.org/en/projects/zlib. Tento patch jsem použil a výkon se slušně zvýšil.
Další cestou, kterou se lze vydat, je použít ZOPFLI od lidí z Google - https://code.google.com/p/zopfli/. Výhody a nevýhody jsou jasné - komprese je lepší o 2 - 3 %, čas potřebný na kompresi je 100× větší. ZOPFLI se mi podařilo zkompilovat, ale nefunguje spolehlivě, navíc bych tímto přišel o
Ztrátová komprese
Možná si řeknete, co je to za pitomost? Deflate použitý v OZF je bezztrátový (losseless) algoritmus, stejně tak PNG formát, který jej používá. Výzkum na http://membled.com/work/apps/lossy_png/ ukazuje, že lze uložit ztrátovou kompresi i pro PNG formát. Tady je jiná implementace v Go: https://github.com/foobaz/lossypng/blob/master/lossypng.go. Bohužel ani jedna není přímo použitelná pro mne - první nefunguje na obrázky s paletou, druhá využívá triků při ukládání PNG. Zkoušel jsem si implementovat několik algoritmů, které by měly pomoci snížit velikost, ale zatím bez výraznější pomoci
Možná tento výzkum využiju pro optimalizaci výstupu do SQlite formátu.
Optimalizace JPEG
Moje takové malé soukromé přání je vytvořit i mapy pro Trek Buddyho, ukázalo se, že lepší je JPEG. Pár možností, jak ještě zmenšit JPEG je, ale zatím jsem nenašel takový, který by byl binárně kompatibilní.
Pokud máte nějaké další nápady na vylepšení nebo vás cokoliv dalšího napadne, napište.
