1 #LyX 1.6.3 created this file. For more info see http://www.lyx.org/
7 %\usepackage[utf-8]{inputenc} % nastavuje použité kódování, uživatelé Windows zamění latin2 za cp1250
8 %\usepackage[czech]{babel}
9 %\usepackage{a4wide} % nastavuje standardní evropský formát stránek A4
10 %\usepackage{index} % nutno použít v případě tvorby rejstříku balíčkem makeindex
11 %\usepackage{fancybox} % umožňuje pokročilé rámečkování :-)
12 %\usepackage[final]{graphicx} % nezbytné pro standardní vkládání obrázků do dokumentu
14 \usepackage[bindingoffset=1.5cm]{geometry} % nastavení dané velikosti okrajů
15 %[outer=2.5cm,inner=4cm,top=2cm,bottom=3cm]
17 %\newindex{default}{idx}{ind}{Rejstřík} % zavádí rejstřík v případě použití balíku index
20 \def\bcTitle{Moderní metody fraktální komprese obrazu}
21 \def\bcTitleEn{Contemporary Methods in Fractal Image Compression}
22 \def\bcAuthor{Vladimír Čunát}
23 \def\bcAuthorEn{Vladimir Cunat}
24 \def\bcTeacher{RNDr.~Tomáš Dvořák, CSc.}
25 \def\bcTeacherMail{Tomas.Dvorak@mff.cuni.cz}
26 \def\bcKSVI{Kabinet software a výuky informatiky}
27 \def\bcKSVIen{Department of Software and Computer Science Education}
34 %pdfauthor={\bcAuthorEn},
35 %pdftitle={\bcTitleEn},
37 %pdfsubject={Fractal Image Compression},
38 %pdfkeywords={image compression,fractals}
41 pdftitle={\bcTitleEn},
42 pdfauthor={\bcAuthorEn},
43 pdfsubject={Fractal Image Compression},
44 pdfkeywords={image compression, fractals}
48 % url formátování, použito v referencích
52 \newtheorem{veta}{Věta}[chapter]
54 \options notitlepage,12pt
55 \use_default_options false
60 \font_typewriter default
61 \font_default_family default
68 \paperfontsize default
72 \pdf_bookmarksnumbered false
73 \pdf_bookmarksopen false
74 \pdf_bookmarksopenlevel 1
86 \paperorientation portrait
98 \paragraph_separation indent
100 \quotes_language german
103 \paperpagestyle default
104 \tracking_changes false
105 \output_changes false
112 \begin_layout Standard
113 \begin_inset CommandInset include
115 filename "bc_start.tex"
120 \begin_inset Note Note
123 \begin_layout Plain Layout
134 \begin_layout Chapter
138 \begin_layout Standard
139 Množství a rozměry zpracovávaných digitálních obrázků se neustále zvětšují,
140 a tak možnost jejich efektivní reprezentace narůstá na důležitosti.
141 Kapacity pamětí a rychlosti síťových přenosů sice také rostou, ale na druhou
142 stranu se rozšiřují mnohem menší, úspornější a méně výkonná zařízení pracující
150 \begin_layout Standard
151 Fraktální komprese obrazu je relativně nová a velmi netradiční ztrátová
152 metoda, kde je obrázek charakterizován pomocí vzájemných vztahů mezi jeho
154 Vykazuje mnoho neobvyklých vlastostí, které lze využít i pro jiné účely
156 Díky nim získala mnoho popularity, ale také se stala terčem mýtů.
159 \begin_layout Standard
160 Samotná komprese nemá daný pevný postup.
161 Naopak, každou její část lze provádět mnoha různými způsoby.
166 této práci bylo cílem vytvořit modulární systém pro fraktální kompresi,
167 kde by bylo možné vyměňovat jednotlivé části komprese, a umožnit tak snadné
168 porovnávání jednotlivých algoritmů a vyhodnocení jejich interakcí.
171 \begin_layout Standard
180 kapitole jsou popsány základní principy fraktální komprese a různé zkoumané
181 způsoby jejího vylepšení.
187 \begin_inset CommandInset ref
189 reference "Chyba_zobrazení"
193 pak podrobněji rozebírá zobrazení mezi zdrojovými a cílovými bloky, která
194 jsou základem komprese.
204 \begin_inset CommandInset ref
206 reference "Implementace"
210 jsou popsány věci související s
218 --- použité vývojové nástroje, způsob modularizace a implementace jednotlivých
225 \begin_inset CommandInset ref
227 reference "Testování_a_vyhodnocení"
231 vyhodnocuje vliv použití různých technik ve fraktální kompresi na testovacích
232 obrázcích a také porovnává účinnost komprese se standardními ztrátovými
240 \begin_layout Chapter
241 Vývoj a principy fraktální komprese obrazu
242 \begin_inset CommandInset label
244 name "Vývoj_a_principy"
251 \begin_layout Standard
252 V této kapitole bude používáno následující značení:
255 \begin_layout Description
261 \begin_inset Formula $2^{X}=\left\{ A:\, A\subseteq X\right\} $
267 \begin_layout Description
272 zobrazení mějme zobrazení
273 \begin_inset Formula $f:\, X\rightarrow X$
277 \begin_inset Formula $f^{k}:\, X\rightarrow X$
280 je definováno tak, že
281 \begin_inset Formula $f^{0}$
285 \begin_inset Formula \[
286 \forall k\geq1\quad\forall x\in X\quad f^{k}\left(x\right)=f\left(f^{k-1}\left(x\right)\right)\]
293 \begin_layout Description
299 \begin_inset Formula $f:\, X\rightarrow X$
302 na metrickém prostoru
303 \begin_inset Formula $X$
311 \begin_inset Formula $d$
314 je kontraktivní, pokud
315 \begin_inset Formula \[
316 \exists s<1\quad\forall x,y\in X\quad d\left(x,y\right)\leq s\, d\left(f\left(x\right),f\left(y\right)\right)\]
321 \begin_inset Formula $s$
324 budeme nazývat faktorem kontraktivity
325 \begin_inset Formula $f$
331 \begin_layout Section
335 \begin_layout Standard
336 Základy fraktální komprese byly položeny v druhé polovině 80.
337 \begin_inset space \thinspace{}
340 let, kdy Barnsley studoval systémy iterovaných funkcí (IFS).
342 \begin_inset Formula $A$
349 úplném metrickém prostoru
350 \begin_inset Formula $X$
353 definována pomocí souboru kontraktivních zobrazení
354 \begin_inset Formula $X$
358 Mějme soubor zobrazení
359 \begin_inset Formula $f_{i}:X\rightarrow X$
363 \begin_inset Formula $i\in J$
366 a definujme jejich sjednocení
367 \begin_inset Formula $f:2^{X}\rightarrow2^{X}$
371 \begin_inset Formula $B\subseteq X$
375 \begin_inset Formula $f\left(B\right)=\left\{ f_{i}\left(b\right)\mid i\in J,\ b\in B\right\} $
380 \begin_inset Formula $2^{X}$
383 lze definovat metriku tak, abychom dostali zase úplný metrický prostor
385 \begin_inset Formula $f$
388 bylo kontraktivní, jak je ukázáno například v
393 \begin_inset CommandInset citation
399 pomocí Hausdorffovy metriky.
400 To podle Banachovy věty o
404 pevném bodě dává, že takto vzniklé zobrazení
405 \begin_inset Formula $f$
408 má právě jeden pevný bod, kterým je právě hledaná množina
409 \begin_inset Formula $A$
412 , často nazývaná atraktor nebo fraktál
416 \begin_layout Plain Layout
417 fraktály lze konstruovat i jinými způsoby než pomocí IFS
425 \begin_layout Standard
426 IFS mají několik zajímavých vlastností.
427 Pro získání atraktoru stačí znát zobrazení
428 \begin_inset Formula $f$
431 a iterovat ho na libovolné neprázdné kompaktní podmnožině prostoru
432 \begin_inset Formula $X$
436 Navíc vzniklé fraktály mohou mít detailní kresbu při libovolném přiblížení,
437 přestože jejich matematický popis je velmi malý, takže pro tyto speciální
438 obrázky lze dosáhnout libovolně velkého kompresního poměru.
439 Mezi nejznámější IFS patří Barnsleyho kapradina, generovaná v
444 \begin_inset Formula $\mathbb{R}^{2}$
447 pomocí čtyř afinních zobrazení.
448 Barnsley zkoumal, zda by nebylo možné proces obrátit
456 danému obrázku najít soubor zobrazení, jehož pevný bod by obrázku byl velmi
458 Pak by místo souboru pixelů stačil pro popis obrázku jen popis těchto zobrazení.
461 \begin_layout Standard
462 Zde se používá takzvaná kolážová věta, uvedená například v
467 \begin_inset CommandInset citation
473 , která dává horní odhad na odchylku atraktoru od požadovaného obrázku:
476 \begin_layout Standard
480 \begin_layout Plain Layout
499 \begin_inset Formula $f$
502 je zobrazení úplného metrického prostoru do sebe, které je kontraktivní
508 \begin_inset Formula $s<1$
516 \begin_inset Formula $d$
520 \begin_inset Formula \[
521 d\left(A,\lim_{n\rightarrow\infty}f^{n}\left(A\right)\right)\;\le\;\frac{1}{1-s}\, d\left(A,f\left(A\right)\right).\]
529 \begin_layout Plain Layout
541 \begin_layout Standard
542 Díky tomu stačí hledat zobrazení, která obrázek transformují a přitom ho
544 Pro jistotu konvergence dokonce stačí,
554 \begin_inset Formula $f^{k}$
571 \begin_inset Formula $s<1$
575 \begin_inset Formula $k$
579 Ukázalo se, že největší problém je v
583 tom, že na rozdíl od klasických IFS málokterý obrázek lze charakterizovat
584 jako sjednocení několika transformovaných zmenšenin celého obrázku.
585 Bylo sice možné obrázek rozdělit na menší kusy charakterizované IFS, ale
586 tuto metodu se nepodařilo zautomatizovat.
589 \begin_layout Section
591 \begin_inset CommandInset label
600 \begin_layout Standard
601 Pro kompresi obrázků také bylo nutné najít lepší model, než množinu bodů
607 \begin_inset Formula $\mathbb{R}^{2}$
615 možností reprezentace obrázků ve stupních šedi je funkce tvaru
616 \begin_inset Formula $g:I^{2}\rightarrow I$
620 \begin_inset Formula $I$
623 je značení pro interval
624 \begin_inset Formula $\left[0,1\right]\subset\mathbb{R}$
628 Zde budeme analogicky hledat soubor funkcí na těchto obrázkových funkcích
629 (budeme je nazývat operátory) takový, aby jejich sjednocením vznikl operátor
631 \begin_inset Formula $F$
638 pevným bodem co nejblíže danému obrázku (tedy jeho funkci).
639 Aby bylo zaručeno, že lze sjednocení provést, v
643 PIFS (partitioned IFS) je prostor obrázku rozdělen na disjunktní části
644 \begin_inset Formula \[
645 \forall i\in J\quad R_{i}\subset I^{2},\qquad\bigcup_{i\in J}R_{i}=I^{2},\qquad\forall i,j\in J\quad i\neq j\;\rightarrow\; R_{i}\cap R_{j}=\emptyset\]
649 a operátory jsou tvaru
650 \begin_inset Formula $F_{i}:\left(I^{2}\rightarrow I\right)\rightarrow\left(R_{i}\rightarrow I\right)$
656 \begin_layout Standard
657 PIFS, které zavedl Jacquin, dnes tvoří základ naprosté většiny technik pro
658 fraktální kompresi obrazu.
659 Pro zjednodušení se zde uvažují pouze afinní operátory, kde se navíc vzájemně
660 neovlivňuje transformace polohy s
665 Formální zápis aplikace operátoru na obrázek
666 \begin_inset Formula $g:I^{2}\rightarrow I$
670 \begin_inset Formula \[
671 F_{i}g=h_{i},\qquad h_{i}:R_{i}\rightarrow I,\qquad h_{i}\left(\left[\begin{array}{c}
673 y\end{array}\right]\right)=\left(c_{i}\circ g\circ w_{i}\right)\left(\left[\begin{array}{c}
675 y\end{array}\right]\right)\]
680 \begin_inset Formula \[
681 \text{pro nějaká afinní zobrazení\quad}w_{i}:R_{i}\rightarrow I^{2}\mbox{\quad a\quad}c_{i}:I\rightarrow\mathbb{R}\]
695 \begin_inset Formula $R_{i}$
698 se volí souvislé části obrazu, typicky čtverce o
703 \begin_inset Formula $2^{k}$
710 nazývají se cílové bloky.
712 \begin_inset Formula $w_{i}$
716 \begin_inset Formula $D_{i}=w_{i}\left(R_{i}\right)$
719 také souvislé části obrazu a nazývají se zdrojové bloky.
723 \begin_layout Plain Layout
734 \begin_inset Formula $D_{i}$
738 \begin_inset Formula $R_{i}$
778 \begin_inset Formula $w_{i}$
781 určuje, která část obrazu bude zobrazena do cílového bloku a také jak bude
782 otočena a případně symetricky převrácena.
784 \begin_inset Formula $w_{i}$
787 se volí kontraktivní zobrazení, přestože to pro níže uvedené tvrzení o
791 konvergenci není potřeba.
792 Tato kontraktivita mimo jiné způsobuje vytváření nových detailů při přiblížení.
795 \begin_layout Subsection
799 \begin_layout Standard
800 Pro konvergenci a horní odhad chyby PIFS modelu lze zase použít kolážovou
802 Následující důkaz je modifikací důkazu uvedeného v
807 \begin_inset CommandInset citation
814 Zde se hodí metrika na obrázcích (funkcích
815 \begin_inset Formula $g_{i}:I^{2}\rightarrow I$
819 \begin_inset Formula \[
820 d_{s\mathrm{up}}\left(g_{1},g_{2}\right)=\sup_{\vec{z}\in I^{2}}\left\{ \left|g_{1}\left(\vec{z}\right)-g_{2}\left(\vec{z}\right)\right|\right\} \]
824 Postačí, aby existovalo
834 \begin_inset Formula $s<1$
837 takové, že každé ze zobrazení
838 \begin_inset Formula $c_{i}$
842 \begin_inset Formula $a_{i}:\;\left|a_{i}\right|\le s$
846 Pak pro libovolné obrázky
847 \begin_inset Formula $g_{1},g_{2}:I^{2}\rightarrow I$
851 \begin_inset Formula $\vec{z}\in I^{2}$
855 \begin_inset Formula $R_{i}$
859 \begin_inset Formula $\vec{z}\in R_{i}$
863 \begin_inset Formula \[
864 \left|\left(F_{i}g_{1}\right)\left(\vec{z}\right)-\left(F_{i}g_{2}\right)\left(\vec{z}\right)\right|\;\le\; s\left|\left(g_{1}\circ w_{i}\right)\left(\vec{z}\right)-\left(g_{2}\circ w_{i}\right)\left(\vec{z}\right)\right|\;\leq\; s\, d_{s\mathrm{up}}\left(g_{1},g_{2}\right)\]
868 Z toho už plyne kontraktivita celého operátoru
869 \begin_inset Formula $F$
873 \begin_inset Formula \[
874 d_{s\mathrm{up}}\left(Fg_{1},Fg_{2}\right)\;\le\; s\, d_{s\mathrm{up}}\left(g_{1},g_{2}\right)\]
878 a díky tomu lze použít kolážovou větu.
881 \begin_layout Standard
882 Ukazuje se ale, že pro použití v
886 implementaci je tento odhad příliš volný, stejně jako použitá metrika nedává
887 dobré vizuální výsledky.
890 \begin_layout Subsection
892 \begin_inset CommandInset label
894 name "PIFS/Optimální_zobrazení"
901 \begin_layout Standard
912 \begin_inset Formula $R_{i}$
915 se volí afinní zobrazení
916 \begin_inset Formula $w_{i}$
919 tak, aby mapovalo blok na jeden ze souboru zdrojových bloků.
920 Tento soubor bývá pevně daný kvůli zjednodušení ukládání a vyhledávání.
921 Volba zdrojového bloku je hlavním zdrojem výpočetní složitosti celé komprese
922 a jejímu urychlení byla věnována značná část výzkumu v
927 Obecně je snaha zvolit takový blok
928 \begin_inset Formula $D_{i}$
935 optimálním barevným zobrazením
936 \begin_inset Formula $c_{i}$
939 bude pro složený operátor
940 \begin_inset Formula $F_{i}g=\left(c_{i}\circ g\circ w_{i}\right)$
944 \begin_inset Formula $d\left(\ c_{i}\circ g\circ w_{i},\ g\ \right)$
966 \begin_inset Formula $R_{i}$
982 \begin_layout Plain Layout
983 funkce jejichž vzdálenost měříme jsou definovány pouze na
984 \begin_inset Formula $R_{i}$
988 \begin_inset Formula $I^{2}$
999 \begin_layout Standard
1000 Volba optimálního zobrazení
1001 \begin_inset Formula $c_{i}$
1004 a tedy i následně volba
1005 \begin_inset Formula $w_{i}$
1008 je silně závislá na použité metrice.
1009 Ve fraktální kompresi se téměř výhradně používá RMSE metrika.
1010 Její hlavní výhody i nevýhody jsou dány tím, že se vždy berou v
1011 \begin_inset space ~
1014 úvahu pouze sobě odpovídající body.
1015 To umožnuje velmi jednoduchou a rychlou práci s
1016 \begin_inset space ~
1019 metrikou a také optimalizaci v
1020 \begin_inset space ~
1023 ní, na druhou stranu díky tomu pro větší bloky nedává metrika výsledky odpovídaj
1024 ící vizuálnímu rozdílu.
1025 Možnosti použití alternativních metrik jsou zmíněny v
1026 \begin_inset space ~
1030 \begin_inset CommandInset ref
1032 reference "Články/Zlepšení_vzhledu/Další_metody"
1039 \begin_layout Standard
1041 \begin_inset space ~
1045 \begin_inset space ~
1049 \begin_inset CommandInset ref
1051 reference "Chyba_zobrazení"
1055 pro diskrétní případ, při použití RMSE existuje právě jedno optimální
1056 \begin_inset Formula $c_{i}$
1060 \begin_inset Formula $g$
1064 \begin_inset Formula $w_{i}$
1067 ) snadno spočítat analyticky.
1068 To platí za předpokladu, že
1069 \begin_inset Formula $g\circ w_{i}$
1073 \begin_inset Formula $R_{i}$
1077 \begin_inset space ~
1081 \begin_inset Formula $g$
1085 \begin_inset Formula $D_{i}$
1089 \begin_inset space ~
1092 --- jinak by se jednalo o
1093 \begin_inset space ~
1096 aproximaci konstantním blokem, volba lineárního koeficientu by byla libovolná
1097 a výsledek vždy horší, než při výběru jakéhokoliv nekonstantního zdrojového
1101 \begin_layout Subsection
1103 \begin_inset CommandInset label
1105 name "PIFS/Rychlá_konvergence"
1112 \begin_layout Standard
1113 Fraktální komprese v
1114 \begin_inset space ~
1117 této podobě stále trpěla jedním skrytým problémem.
1118 Při dodržení kontraktivity všech zobrazení
1119 \begin_inset Formula $c_{i}$
1122 kolážová věta sice zaručovala, že obrázek zkonverguje (v
1123 \begin_inset space ~
1126 prostoru všech obrázků s
1127 \begin_inset space ~
1130 libovolnou metrikou) a nebude se příliš lišit, ale nijak neomezovala počet
1131 nutných iteračních kroků.
1132 Ukázalo se, že tento problém není jen teoretický
1133 \begin_inset space ~
1137 \begin_inset space ~
1140 při přísnějších omezeních na kontraktivitu bylo pro některé obrázky nutné
1141 provádět mnoho desítek iterací než změny přestaly být okem viditelné.
1144 \begin_layout Standard
1145 Řešení tohoto problému bylo publikováno v
1146 \begin_inset space ~
1150 \begin_inset CommandInset citation
1156 a podrobněji rozebráno v
1157 \begin_inset space ~
1161 \begin_inset space ~
1165 \begin_inset space ~
1169 \begin_inset CommandInset citation
1177 \begin_inset space ~
1180 drobnou modifikaci barevného zobrazení.
1181 Pokud bylo původní optimální barevné zobrazení ve tvaru
1182 \begin_inset Formula $c_{i}\left(z\right)=p_{i}\, z+q_{i}$
1185 , pak místo ukládání
1186 \begin_inset Formula $p_{i}$
1190 \begin_inset Formula $q_{i}$
1194 \begin_inset Formula $p_{i}$
1197 a průměrná barva bloku
1198 \begin_inset Formula $R_{i}$
1203 \begin_inset Formula $\tilde{c_{i}}$
1206 pak znormalizuje barvu zdrojového bloku
1207 \begin_inset Formula $D_{i}$
1210 odečtením jeho aktuálního průměru, výsledek vynásobí lineárním koeficienem
1212 \begin_inset Formula $p_{i}$
1215 a přičte předpočítanou průměrnou barvu bloku
1216 \begin_inset Formula $R_{i}$
1219 ve vstupním obrázku.
1222 \begin_layout Standard
1223 Přestože přičítaná průměrná barva
1224 \begin_inset Formula $R_{i}$
1228 \begin_inset space ~
1231 charakteristice zobrazení a je stále stejná, skutečný konstantní koeficient
1233 \begin_inset Formula $q_{i}$
1237 \begin_inset space ~
1240 každou iterací, takže z
1241 \begin_inset space ~
1244 matematického hlediska se
1245 \begin_inset Formula $\tilde{c_{i}}$
1248 chová pokaždé jako jiné zobrazení.
1251 \begin_layout Standard
1253 \begin_inset space ~
1256 rámci jedné iterace je ale
1257 \begin_inset Formula $\tilde{c_{i}}$
1260 stále afinní zobrazení.
1261 Navíc lze snadno ukázat, že při použití RMSE metriky optimální afinní zobrazení
1263 \begin_inset Formula $c_{i}$
1266 také vždy zobrazuje průměnou barvu
1267 \begin_inset Formula $D_{i}$
1271 \begin_inset Formula $R_{i}$
1274 , takže když stav obrázku při iterování konverguje k
1275 \begin_inset space ~
1279 \begin_inset Formula $g$
1282 (zdrojovému obrázku), pak i
1283 \begin_inset space ~
1287 \begin_inset Formula $\tilde{c_{i}}$
1291 \begin_inset space ~
1295 \begin_inset Formula $c_{i}$
1302 \begin_layout Standard
1303 V tomto přístupu je tedy iterační operátor složitější na vyhodnocení, ale
1304 má lepší vlastnosti, například efektivnější ukládání koeficientů zobrazení
1305 díky jejich menší korelaci.
1307 \begin_inset Formula $q_{i}$
1311 \begin_inset Formula $c_{i}$
1315 \begin_inset space ~
1318 absolutní hodnotě malá čísla, ale mohly se pohybovat ve velkém rozsahu.
1319 Průměrná barva bloku se může pohybovat jen v
1320 \begin_inset space ~
1324 \begin_inset Formula $\left[0,1\right]$
1327 a má jasnější význam
1328 \begin_inset space ~
1331 --- to pomáhá při volbě způsobu kvantizace při uložení do souboru a umožnuje
1332 například využít toho, že sousední bloky budou mít pravděpodobně blízkou
1336 \begin_layout Standard
1337 Další výhodou je mnohem rychlejší a jistější konvergence.
1338 Je vidět, že po každé iteraci mají všechny bloky
1339 \begin_inset Formula $R_{i}$
1342 správnou průměrnou barvu.
1343 Tím se vzhled zdrojových bloků
1344 \begin_inset Formula $D_{i}$
1347 už po první iteraci dostane blízko vzorovému obrázku, což se při další
1348 iteraci promítne do cílových bloků
1349 \begin_inset Formula $R_{i}$
1355 \begin_layout Standard
1357 \begin_inset space ~
1360 výše odkazovaných publikacích je ukázáno, že po takovéto úpravě barevných
1361 zobrazení iterační proces konverguje ke stejnému výsledku a také, že za
1362 trochu silnějších předpokladů než zde uvedené bude potřebný počet iterací
1363 malý a bude záviset pouze na velikostech zdrojových a cílových bloků.
1364 Používá se zde diskrétní model obrázku
1365 \begin_inset space ~
1368 --- posloupnost reálných čísel, kde cílové bloky jsou tvořeny
1369 \begin_inset Formula $2^{b_{i}}$
1372 po sobě jdoucími hodnotami a zdrojové bloky o
1373 \begin_inset space ~
1377 \begin_inset Formula $2^{d_{i}}$
1380 jsou tvořeny několika po sobě jdoucími cílovými bloky.
1381 Zmenšování bloků vždy probíhá zprůměrováním
1382 \begin_inset Formula $2^{d_{i}-b_{i}}$
1385 po sobě jdoucích hodnot.
1388 \begin_layout Standard
1389 Na rozdíl od konvergence založené na kolážové větě je důkaz proveden bez
1390 jakéhokoliv omezení na kontraktivitu barevných zobrazení
1391 \begin_inset Formula $\bar{c_{i}}$
1394 , což umožnuje mnohem přesnější aproximaci bloků s
1395 \begin_inset space ~
1398 ostrými přechody bez ztráty jistoty konvergence.
1399 Zde se naopak využívá kontraktivity transformací
1400 \begin_inset Formula $w_{i}$
1406 \begin_layout Subsection
1407 Úprava lineárních koeficientů
1408 \begin_inset CommandInset label
1410 name "PIFS/Použitý_model"
1417 \begin_layout Standard
1418 Podobným způsobem, jako byly konstantní koeficienty barevných zobrazení
1419 nahrazeny průměry, lze také lineární koeficienty nahradit směrodatnými
1421 \begin_inset space ~
1424 --- barvy zdrojových bloků jsou vyděleny svou směrodatnou odchylkou a vynásobeny
1425 cílovou směrodatnou odchylkou.
1427 \begin_inset space ~
1431 \begin_inset space ~
1435 \begin_inset CommandInset ref
1437 reference "Chyba_zobrazení/Upravená"
1441 , mírně se tím zvýší chyba optimálního zobrazení.
1444 \begin_layout Standard
1445 Výhody a nevýhody tohoto přístupu jsou podobné jako při nahrazování konstantních
1446 koeficientů zobrazení
1447 \begin_inset space ~
1450 --- především jednodušší reprezentace zobrazení a pravděpodobně také rychlejší
1454 \begin_layout Standard
1456 \begin_inset space ~
1460 \begin_inset space ~
1464 \begin_inset CommandInset citation
1471 \begin_inset space ~
1474 této práci je používán právě tento model barevných zobrazení, ale nikde
1475 se mi nepodařilo nalézt nějaké zdůvodnění nebo odkaz na text zabývající
1476 se jeho vlastnostmi.
1477 Nejsou mi tedy známy žádné výsledky týkající se konvergence ani pro případné
1481 \begin_layout Standard
1482 Lineární koeficienty barevných zobrazení nejsou stejně jako v
1483 \begin_inset space ~
1486 předchozím modelu nijak omezeny, ale experimenty prováděné v
1487 \begin_inset space ~
1490 rámci této práce ukazují, že může být výhodné vyhýbat se zobrazením, kde
1491 je absolutní hodnota lineárního koeficientu vysoká.
1492 Tato úprava je diskutována v
1493 \begin_inset space ~
1497 \begin_inset CommandInset ref
1499 reference "Chyba_zobrazení/Penalizace"
1503 , včetně teoretického zdůvodnění.
1506 \begin_layout Section
1507 Nejčastější oblasti výzkumu
1508 \begin_inset CommandInset label
1517 \begin_layout Standard
1519 \begin_inset space ~
1523 \begin_inset space \thinspace{}
1526 let bylo věnováno fraktální kompresi velké úsilí.
1527 Bylo zkoumáno (většinou odděleně) mnoho odlišných způsobů vylepšení základních
1528 technik popsaných výše.
1530 \begin_inset space ~
1533 této části jsou shrnuty nejvýznamnější výsledky a zajímavé návrhy pro další
1535 Pro přehlednost jsou rozčleněny podle toho, na které aspekty komprese se
1539 \begin_layout Subsection
1541 \begin_inset CommandInset label
1543 name "Články/Zrychlení"
1550 \begin_layout Standard
1551 Za největší problém byla považována obrovská výpočetní náročnost hledání
1552 vhodných zdrojových bloků.
1553 Od dob nejintenzivnějšího výzkumu v
1554 \begin_inset space ~
1557 oblasti se sice výkon běžných počítačů mnohonásobně zvýšil, ale stále je
1558 nutné se tímto problémem zabývat.
1560 \begin_inset space ~
1563 důvodů je, že dnes je potřeba zpracovávat mnohem větší množství dat.
1564 Velikosti a množství fotografií roste a také je zkoumána možnost využití
1565 pro kompresi videozáznamů.
1568 \begin_layout Subsubsection
1572 \begin_layout Standard
1573 Nejčastější technikou pro urychlení výběru vhodného zdrojového bloku byly
1574 klasifikační metody.
1575 Všechny cílové a potencionální zdrojové bloky jsou nějakým způsobem ohodnoceny
1576 a poté je vzájemná zobrazitelnost přesně vyhodnocována pouze pro
1577 \begin_inset Quotes gld
1581 \begin_inset Quotes grd
1586 \begin_inset space ~
1589 vynechání některých optimálních zobrazení, ale pokles kvality bývá velmi
1590 malý a urychlení mnohonásobné (zkomprimovaná velikost se nezmění).
1593 \begin_layout Standard
1595 \begin_inset space ~
1598 jednoduché rozdělení bloků do několika tříd a uvažování pouze zobrazení
1599 v rámci jedné třídy, například klasifikace navržené Jacquinem nebo Fisherem
1600 \begin_inset space ~
1604 \begin_inset CommandInset citation
1611 Zde je nevýhodné, že pro bloky
1612 \begin_inset Quotes gld
1616 \begin_inset space ~
1620 \begin_inset Quotes grd
1623 tříd často mohou mít podobné bloky v
1624 \begin_inset space ~
1628 \begin_inset Quotes gld
1632 \begin_inset Quotes grd
1636 To vede ke složitějším metodám, které hledají i v
1637 \begin_inset space ~
1640 příbuzných třídách, nebo používají hierarchické způsoby klasifikace, například
1641 \begin_inset space ~
1645 \begin_inset CommandInset citation
1654 \begin_layout Subsubsection
1655 Převod na hledání nejbližšího bodu
1658 \begin_layout Standard
1659 Problémem klasifikačních metod je, že přes výrazné zrychlení nejsou schopny
1660 zlepšit asymptotickou složitost výpočtu.
1661 Zde se nabízí zobecnění klasifikačních metod, kde by pro blok byl vygenerován
1663 \begin_inset space ~
1666 nějakého prostoru uspořádaného tak, že vzdálenost v
1667 \begin_inset space ~
1670 něm odpovídá míře vzájemné zobrazitelnosti.
1671 Pak by pro každý bod prostoru odpovídající nějakému cílovému bloku stačilo
1673 \begin_inset space ~
1676 množiny bodů prostoru odpovídající zdrojovým blokům.
1677 Hledání nejbližších sousedů je známá úloha, kterou už lze řešit výrazně
1678 rychleji než úměrně se součinem velikostí obou množin.
1681 \begin_layout Standard
1682 Tato možnost byla publikována mezi projekty v
1683 \begin_inset space ~
1687 \begin_inset space ~
1691 \begin_inset CommandInset citation
1697 a podrobněji rozebrána v
1698 \begin_inset space ~
1702 \begin_inset space ~
1706 \begin_inset CommandInset citation
1713 Je zde především dokázáno, že při uvažování klasických afinních zobrazení
1714 pro transformaci barvy mezi bloky je pro pevný cílový blok optimální čtvercová
1715 chyba (SE) rovna určité rostoucí transformaci eukleidovské vzdálenosti
1716 normalizovaných vektorů obou bloků (cílového a zdrojového).
1717 Tedy pro nalezení zdrojového bloku
1718 \begin_inset Quotes gld
1722 \begin_inset Quotes grd
1726 \begin_inset space ~
1729 cílovému stačí jen najít nejbližší bod v
1730 \begin_inset space ~
1733 eukleidovském prostoru.
1736 \begin_layout Standard
1737 Jsou zde různé komplikace
1738 \begin_inset space ~
1741 --- kvůli kvantizaci koeficientů nemusí nejbližší bod být ten nejlepší,
1742 při uvažování i zobrazení se zápornými lineárními koeficienty je nutné
1743 prohledávát strukturu dvakrát (nebo vložit každý bod dvakrát).
1744 Je zde také otázka spotřeby paměti, která sice není tak velkým problémem,
1746 \begin_inset space ~
1749 době publikace metody, ale stále potřeba se jí věnovat.
1750 Dále se problematikou zabýváme v
1751 \begin_inset space ~
1755 \begin_inset space ~
1759 \begin_inset CommandInset ref
1761 reference "Implementace/Predikce"
1768 \begin_layout Subsubsection
1769 Lokální prohledávání
1772 \begin_layout Standard
1773 Za další možnost urychlení se považoval jiný způsob redukce nutných porovnání
1774 \begin_inset space ~
1777 --- přeskočení zdrojových bloků, které jsou v
1778 \begin_inset space ~
1781 obrázku příliš vzdálené od cílového bloku (pro který hledáme zobrazení).
1782 Na rozdíl od klasifikačních metod je množina uvažovaných zdrojových bloků
1784 \begin_inset space ~
1787 polohy cílového bloku, takže lze ušetřit nějaký prostor nutný pro uložení
1788 jejich identifikačních čísel.
1791 \begin_layout Standard
1792 Základem této techniky je domněnka, že ideální zdrojový blok má větší pravděpodo
1793 bnost výskytu blíže k
1794 \begin_inset space ~
1797 danému cílovému bloku.
1799 \begin_inset space ~
1803 \begin_inset space ~
1807 \begin_inset CommandInset citation
1813 je ukázáno, že posun rozdělení vzdáleností optimálních dvojic oproti vzdálenost
1814 em náhodně vybraných dvojic je zanedbatelný.
1815 Zrádné je zde především to, že už jen rozdělení vzdálenosti dvou náhodných
1816 bodů je velmi nerovnoměrné.
1819 \begin_layout Standard
1821 \begin_inset space ~
1824 další nevýhody spojené s
1825 \begin_inset space ~
1828 tím, že je množina uvažovaných zdrojových bloků pro každý cílový blok jiná,
1829 například obtížná kombinace s
1830 \begin_inset space ~
1833 jinými metodami urychlení komprese.
1836 \begin_layout Standard
1837 Na druhou stranu například v
1838 \begin_inset space ~
1842 \begin_inset space ~
1846 \begin_inset CommandInset citation
1852 je zkoumána závislost podobnosti dvou cílových bloků na jejich vzdálenosti
1854 \begin_inset space ~
1857 opačnými výsledky na stejném obrázku (Lenna).
1858 To je pravděpodobně způsobeno tím, že při hledání podobnosti mezi zdrojovým
1859 a cílovým blokem vždy dochází ke zmenšování, zatímco blízké cílové bloky
1860 často mívají stejnou velikost.
1863 \begin_layout Standard
1864 Této podobnosti je zde využito nejen pro urychlení hledání zdrojového bloku
1865 tím, že jsou nejprve vyzkoušeny zdrojové bloky blízkých cílových bloků,
1866 ale hlavně ke zvýšení kompresního poměru.
1867 Místo ukládání identifikačního čísla zdrojového bloku stačí uložit relativní
1868 pozici nejbližšího cílového bloku se stejným zdrojovým blokem.
1870 \begin_inset space ~
1873 tomu, že cílových bloků bývá mnohem méně než zdrojových a podobné cílové
1874 bloky se často vyskytují blízko, lze takto ušetřit mnoho bitů ve výstupu
1875 za cenu minimálního poklesu kvality.
1878 \begin_layout Subsubsection
1879 Přerušení prohledávání
1882 \begin_layout Standard
1883 Další metoda snížení počtu nutných porovnání je nehledat nejlepší zdrojový
1884 blok a spokojit se s
1885 \begin_inset space ~
1888 dostatečně dobrým už nalezeným blokem.
1889 Dosažené zrychlení ale nejspíš nebude nijak veliké.
1890 Nejsou mi známy žádné práce, které by se podrobněji zabývaly touto technikou.
1893 \begin_layout Subsection
1897 \begin_layout Standard
1898 Vetšinou nezávisle na rychlosti komprese byly zkoumány také metody zlep\SpecialChar \-
1901 kvalitu dekomprimovaných obrázků.
1902 Zde jsou zařazeny i techniky zvyšující kompresní poměr, protože jde o
1903 \begin_inset space ~
1907 \begin_inset space ~
1910 --- typicky lze pouhým nastavováním parametrů komprese zlepšovat jeden z
1911 \begin_inset space ~
1914 těchto ukazatelů na úkor druhého.
1917 \begin_layout Subsubsection
1918 Dělení na cílové bloky
1921 \begin_layout Standard
1922 Jedním ze základních faktorů ovlivňujících vzhled je způsob dělení obrázku
1924 Nejjednodušší je určit dělení napevno.
1926 \begin_inset space ~
1929 praxi nepoužitelné kvůli obtížné regulaci kvality a kompresního poměru.
1930 Navíc nalézt dobré zobrazení pro skoro konstatní bloky je velmi jednoduché,
1931 zatímco pro bloky obsahující hodně detailů nejspíš žádný vhodný zdrojový
1933 \begin_inset space ~
1937 Proto bylo nutné hledat adaptivní metody, které by v
1938 \begin_inset space ~
1942 \begin_inset Quotes gld
1946 \begin_inset Quotes grd
1949 místech nechávaly velké bloky a v
1950 \begin_inset space ~
1953 místech se složitější kresbou mohly dělit obrázek na menší a zvyšovat u
1954 \begin_inset space ~
1957 nich tak pravděpodobnost nalezení dostatečně dobrého zobrazení.
1960 \begin_layout Standard
1961 \begin_inset VSpace defskip
1967 \begin_layout Standard
1968 Jednoznačně nejpoužívanější metodou je dělení pomocí čtyřstromu (Quadtree),
1969 popsaného například v
1970 \begin_inset space ~
1974 \begin_inset CommandInset citation
1981 Pro zjednodušení se uvažují jako velikosti obrázku a bloků jen čtverce
1983 \begin_inset space ~
1986 hranách délky mocniny 2.
1988 \begin_inset space ~
1991 jedním velkým cílovým blokem pokrývajícím celý obrázek a postupuje se tak,
1992 že se vždy vezme nějaký cílový blok a najde se pro něj nejlepší zobrazení.
1993 Pokud je chyba dostatečně malá, je zobrazení použito, jinak je blok rozdělen
1995 \begin_inset space ~
1998 poloviční velikosti, pro které se použije stejný postup.
2001 \begin_layout Standard
2002 Tento způsob dělení je celkem efektivní a také jednoduchý na implementaci,
2003 včetně velmi úsporného uložení tvaru čtyřstromu.
2005 \begin_inset space ~
2008 praxi je potřeba čtyřstrom zobecnit i pro jiné velikosti obrázku a jsou
2009 vhodná i další vylepšení.
2010 Podrobněji je dělení čtyřstromem rozebráno v
2011 \begin_inset space ~
2015 \begin_inset space ~
2019 \begin_inset CommandInset ref
2021 reference "Implementace/MQuadTree"
2028 \begin_layout Standard
2030 \begin_inset space ~
2033 nevýhod čtyřstromu je, že skoky mezi jednotlivými velikostmi bloků jsou
2034 relativně velké, takže v
2035 \begin_inset space ~
2038 některých případech dochází k
2039 \begin_inset space ~
2042 dělení na zbytečně malé bloky.
2043 Tento problém je řešen v
2044 \begin_inset space ~
2048 \begin_inset CommandInset citation
2054 pomocí přidání jednoho mezikroku, což sice vede k
2055 \begin_inset space ~
2058 delšímu výpočtu, ale také mírně zlepšuje kvalitu komprimovaných obrázků.
2061 \begin_layout Standard
2062 \begin_inset VSpace defskip
2068 \begin_layout Standard
2069 Zobecněním dělení čtyřstromem je HV (horizontálně-vertikální) dělení, popsané
2071 \begin_inset space \thinspace{}
2075 \begin_inset space ~
2079 \begin_inset CommandInset citation
2086 Základní myšlenka je stejná jako u
2087 \begin_inset space ~
2092 mů, akorát umožňuje dělit obecné obdelníkové bloky na dva menší
2093 podle libovolné svislé nebo vodorovné přímky.
2096 \begin_layout Standard
2098 \begin_inset space ~
2101 menším skokům mezi velikostmi bloků, ale hlavní výhoda je ve vyšší adaptivitě.
2103 \begin_inset space ~
2107 \begin_inset CommandInset citation
2113 je navržena heuristická metoda, která vybírá místo dělení nejčastěji těsně
2115 \begin_inset space ~
2118 silných barevných zlomů a zároveň se vyhýbá blokům s
2119 \begin_inset space ~
2122 příliš velkým poměrem délek stran.
2123 To zvyšuje pravděpodobnost nalezení vhodného zdrojového bloku a vyvažuje
2124 tak větší složitost uložení struktury rozdělení obrázku.
2127 \begin_layout Standard
2128 Podle autorů dává metoda o
2129 \begin_inset space ~
2132 něco lepší výsledky než klasický čtyřstrom, ale komplikuje ostatní fáze
2134 Protože cílové bloky mohou mít libovolné obdelníkové tvary, je mnohem těžší
2135 použití klasifikačních a jiných urychlujících metod.
2138 \begin_layout Standard
2139 \begin_inset VSpace defskip
2145 \begin_layout Standard
2146 Další typy dělení zmiňované v
2147 \begin_inset space ~
2151 \begin_inset CommandInset citation
2157 , například trojúhelníkové, polygonální, nebo šestiúhelníkové
2161 \begin_layout Plain Layout
2162 toto dělení na rozdíl od šestiúhelníkové architektury zmíněné níže pracuje
2164 \begin_inset space ~
2167 klasickými čtvercovými pixely, jen zdrojové bloky mají přibližně tvar šestiúheln
2173 jsou velmi komplikované na implementaci a pravděpodobně by nepřinesly významné
2175 Mezi jejich předpokládané výhody ale patří méně
2176 \begin_inset Quotes gld
2180 \begin_inset Quotes grd
2183 vhled způsobený dělením podle šikmých nebo různě orientovaných hran, případně
2184 mírným překryvem pixelů na krajích bloků.
2187 \begin_layout Standard
2188 \begin_inset VSpace defskip
2194 \begin_layout Standard
2195 Dělení na nezávisle zobrazované bloky vytváří rušivou strukturu, jejíž redukcí
2196 je možné výrazně zlepšit subjektivní vzhled a někdy i PSNR komprimovaného
2198 Problémem je vysoká citlivost lidského na hrany, obzvláště horizontálně
2199 a vertikálně orientované.
2200 Pro potlačení této struktury lze dělat zásahy na dvou různých místech celého
2201 kompresního procesu.
2204 \begin_layout Standard
2205 Nejjednodušší možnost je věnovat se tomuto problému až při dekódování.
2206 Hranice bloků jsou vždy známé, takže je možné vyhlazovat výsledný obrázek
2207 jen na jejich okrajích.
2208 Vizuálního zlepšení lze dosáhnout už použitím jednoduchých nebo vážených
2210 \begin_inset space ~
2214 \begin_inset CommandInset citation
2222 \begin_inset space ~
2225 vyšším kompresním poměrem a také u jednotlivých větších cílových bloků je
2226 větší potřeba vyhlazování a obvykle dojde i ke zvýšení PSNR, ale naopak
2227 při nastavení vysoké kvality po vyhlazování PSNR klesne (přestože obrázek
2229 \begin_inset Quotes gld
2233 \begin_inset Quotes grd
2239 \begin_layout Standard
2240 Další možností je snažit se redukovat tyto přechody už při kompresi.
2241 Zde mi nejsou známy žádné publikované výsledky kromě návrhů způsobů řešení.
2242 Lze vážit chybu na okrajích cílových bloků více než chybu uvnitř, případně
2243 použít dělení na překrývající se bloky a při dekódování hodnoty na překryvu
2247 \begin_layout Subsubsection
2251 \begin_layout Standard
2252 Dalším faktorem ovlivňujícím vzhled je volba souboru zdrojových bloků.
2253 Důležitý je především počet bloků v
2254 \begin_inset space ~
2258 Zvýšení počtu sice vede k
2259 \begin_inset space ~
2262 potřebě většího prostoru na uložení identifikačních čísel zdrojových bloků,
2263 ale také zvyšuje pravděpodobnost nalezení vhodného bloku, takže lze při
2264 stejné kvalitě použít rozdělení obrázku na menší počet větších cílových
2268 \begin_layout Standard
2269 Výsledky testování (například v
2270 \begin_inset space ~
2274 \begin_inset CommandInset citation
2280 ) ukazují, že zvyšování množství zdrojových bloků typicky vede ke zlepšení
2282 Nevýhodou je vyšší výpočetní náročnost.
2283 Zde se ukazuje spojitost se zrychlením komprese
2284 \begin_inset space ~
2287 --- při vyšší rychlosti by bylo únosné prohledat větší soubor bloků a zlepšit
2288 tak kvalitu (případně kompresní poměr).
2291 \begin_layout Standard
2292 \begin_inset VSpace defskip
2298 \begin_layout Standard
2299 Kromě množství zdrojových bloků je potřeba rozhodnout, jak zdrojové bloky
2301 Základní podmínkou je, že musí být větší než příslušné cílové bloky, aby
2302 byla prostorová část zobrazení kontraktivní.
2303 Ekvivalentně lze uvažovat výběr zdrojových bloků stejně velkých jako příslušné
2305 \begin_inset space ~
2308 nějaké zmenšeniny původního obrázku.
2309 To je díky své obecnosti někdy výhodné i pro implementaci (využito také
2311 \begin_inset space ~
2317 \begin_layout Standard
2318 Samotné zmenšování lze provádět mnoha různými způsoby.
2319 Kvůli jednoduché implementaci se nejčastěji používá především zmenšování
2321 \begin_inset space ~
2324 obou rozměrech na polovinu (průměrováním hodnot po čtveřicích) a navíc se
2325 uvažuje všech osm transformací čtverce složených ze
2326 \begin_inset space ~
2329 symetrií a otáčení o
2330 \begin_inset space ~
2334 \begin_inset Formula $90^{\circ}$
2339 \begin_inset space ~
2343 \begin_inset CommandInset citation
2349 je navíc zkoumáno použití zmenšování s
2350 \begin_inset space ~
2353 kontraktivitou rozdílnou pro obě osy nebo s
2354 \begin_inset space ~
2358 \begin_inset space ~
2362 \begin_inset Formula $45^{\circ}$
2366 \begin_inset space ~
2370 Tyto myšlenky byly také využity při implementaci (část
2371 \begin_inset space ~
2375 \begin_inset CommandInset ref
2377 reference "Implementace/Domény"
2384 \begin_layout Standard
2386 \begin_inset space ~
2390 \begin_inset CommandInset citation
2396 přidávání osmi transformací čtverce nijak nezlepšuje kvalitu, ale může
2397 sloužit spíše jako způsob zvětšování počtu zdrojových bloků.
2399 \begin_inset space ~
2402 takto zvětšeném souboru bloků je často pak možné dosáhnout úspory paměti
2403 a zrychlení oproti jiným způsobům zvětšování souboru.
2406 \begin_layout Subsubsection
2407 Šestiúhelníková architektura
2410 \begin_layout Standard
2412 \begin_inset space ~
2415 poslední době je zkoumáno také pojetí obrázku jako bodů uspořádaných do
2416 šestiúhelníkové mříže místo čtvercové.
2417 Tato architektura mnohem lépe odpovídá rozložení tyčinek a čípků na sítnici
2419 \begin_inset space ~
2422 přirozené redukci horizontálních a vertikálních artefaktů.
2423 Další výhodou je větší množství přirozených rotací na mříži.
2424 \begin_inset VSpace defskip
2430 \begin_layout Standard
2431 Protože běžné formáty obrázků podporují pouze obdélníkový tvar se
2432 \begin_inset space ~
2435 čtvercovými body, je potřeba nejprve stanovit způsob převodu mezi mřížemi.
2436 Objevují se dva různé přístupy.
2437 První možnost je představit si čtvercovou mříž o
2438 \begin_inset space ~
2442 \begin_inset Formula $60^{\circ}$
2445 zkosenou, tím se středy pixelů dostanou právě do pravidelné šestiúhelníkové
2446 mříže a je možné je převádět
2447 \begin_inset Formula $1:1$
2451 \begin_inset space ~
2455 \begin_inset CommandInset citation
2462 Druhou možností je body přepočítat pomocí váženého průměrování, například
2464 \begin_inset space ~
2468 \begin_inset CommandInset citation
2477 \begin_layout Standard
2478 Výhoda prvního přístupu oproti druhému je, že zobrazuje právě jeden čtvercový
2479 pixel na jeden šestiúhelníkový, takže nedochází k žádnému rozmazávání.
2480 Na druhou stranu se v
2481 \begin_inset space ~
2484 podstatě pracuje se zkoseným obrázkem, takže interpretace vzdáleností bude
2486 \begin_inset space ~
2489 různých směrech různě změněna, což může vést k
2490 \begin_inset space ~
2493 nerovnoměrným projevům zkreslení způsobeného kompresí.
2496 \begin_layout Standard
2497 \begin_inset VSpace defskip
2503 \begin_layout Standard
2504 Změna architektury také přináší mnoho otázek a implementačních problémů.
2505 Po libovolném převodu obdélníkového obrázku budou v
2506 \begin_inset space ~
2509 šestiúhelníkové mříži
2510 \begin_inset Quotes gld
2514 \begin_inset Quotes grd
2517 neobvyklých tvarů nebo nepravidelné okraje a už samotný způsob reprezentace
2519 \begin_inset space ~
2522 paměti je netriviální.
2523 Ve zmíněných článcích jsou tyto potíže řešeny kompresí pouze části obrázku
2525 \begin_inset space ~
2528 vhodném tvaru, ale ani tak zde dosažené výsledky nejsou přesvědčivé.
2531 \begin_layout Subsubsection
2535 \begin_layout Standard
2536 Ve většině případů je fraktální komprese zkoumána pouze na obrázcích ve
2538 \begin_inset space ~
2541 argumentem, že barevné obrázky lze snadno komprimovat jako tři nezávislé
2543 Je ale zřejmé, že RGB není vhodný model pro kompresi obrazu, protože jsou
2544 jeho složky vzájemně silně závislé.
2547 \begin_layout Standard
2548 Nejjednodušší je použít některý z
2549 \begin_inset space ~
2552 barevných prostorů navržených pro tyto účely, například YCbCr nebo L*a*b*
2553 \begin_inset space ~
2557 \begin_inset CommandInset citation
2564 Toto je standardní řešení v
2565 \begin_inset space ~
2568 mnoha jiných metodách komprese obrazu.
2570 \begin_inset space ~
2573 závislosti na použitém modelu může být vhodné navíc upravit nastavení kvality
2574 komprese jednotlivých složek, protože citlivost oka na různé barvy se liší.
2575 Ve formátech založených na standardu JPEG se dokonce u
2576 \begin_inset space ~
2579 barevných složek snižuje rozlišení, ale ve fraktální kompresi je mnohem
2580 výhodnější rozlišení ponechat a snížit kvalitu, protože zde výhody oproti
2582 \begin_inset space ~
2585 kompresním poměrem (experimenty, například v
2586 \begin_inset space ~
2590 \begin_inset space ~
2594 \begin_inset space ~
2598 \begin_inset CommandInset citation
2604 , jasně ukazují, že fraktální komprese nejsnáze překonává JPEG při extrémních
2605 kompresních poměrech).
2608 \begin_layout Standard
2609 Alternativně lze spočítat vlastní barevný prostor pro konkrétní obrázek.
2610 Budeme pro jednoduchost uvažovat jen změnu báze vektorového prostoru, charakter
2611 izovanou maticí velikosti
2612 \begin_inset Formula $3\times3$
2616 \begin_inset space ~
2619 RGB prostoru je prvkem
2620 \begin_inset Formula $\mathbb{R}^{3}$
2624 Zde lze použít metodu zvanou PCA (principal component analysis), známou
2625 také jako KLT (Karhunen–Loève transform).
2626 Metoda nalezne nejlepší ortonormální bázi z
2627 \begin_inset space ~
2630 hlediska soustředění maxima informace (rozptylu) do minima souřadnic.
2631 Transformační matice je dána vlastními vektory kovariační matice a navíc
2632 příslušná vlastní čísla charakterizují důležitost jednotlivých souřadnic.
2636 \begin_layout Plain Layout
2637 PCA samotnou lze použít ke kompresi obázků tak, že se obrázek rozdělí na
2639 \begin_inset space ~
2644 \begin_inset space ~
2647 nich se pracuje jako s
2648 \begin_inset space ~
2652 Po náročném výpočtu pak vznikne transformace, v
2653 \begin_inset space ~
2656 praxi často velmi podobná diskrétní kosinové transformaci.
2664 \begin_layout Standard
2665 Je možné také volit jiné přístupy ke zpracování barev.
2667 \begin_inset space ~
2671 \begin_inset CommandInset citation
2677 je předvedena metoda, která pomocí čtyřstromu dělí barevný obrázek na bloky
2678 (podobně jako při dělení cílových bloků) dokud nejsou barvy v
2679 \begin_inset space ~
2682 blocích dostatečně korelované.
2683 Parametry korelace barev pro každý z
2684 \begin_inset space ~
2687 bloků jsou uloženy a do dalšího kódování postupuje již jen jeden obrázek
2690 \begin_inset space ~
2693 adaptivní kompresi informací o
2694 \begin_inset space ~
2698 \begin_inset space ~
2701 urychlení díky tomu, že se složité metody fraktální komprese použijí jen
2702 na jeden jednobarevný obrázek, přestože většina vnímané informace bude
2704 \begin_inset space ~
2710 \begin_layout Subsubsection
2712 \begin_inset CommandInset label
2714 name "Články/Zlepšení_vzhledu/Další_metody"
2721 \begin_layout Standard
2722 Zde ještě ještě stručně zmíněno několik dalších metod používaných pro zlepšení
2723 vzhledu komprimovaných obrázků.
2726 \begin_layout Standard
2727 Obzvláště při vysokých kompresních poměrech je výhodné počítat chybu zobrazení
2728 ze zdrojových bloků do cílových s
2729 \begin_inset space ~
2732 použitím kvantizovaných parametrů zobrazení místo teoretických optim (tedy
2734 \begin_inset space ~
2737 hodnot dostupných při dekompresi místo hodnot dostupných při kompresi).
2738 Aby šlo metodu použít, je potřeba se omezit jen na některé způsoby kvantizace
2739 a také výpočet této chyby bývá trochu složitější.
2742 \begin_layout Standard
2743 Jak již bylo zmíněno, RMSE metrika pro větší bloky nepopisuje dobře vnímaný
2745 Použití přesnějších metrik bylo zatím věnováno jen velmi málo pozornosti,
2746 především díky jednoduchosti práce s
2747 \begin_inset space ~
2750 RMSE umožnující relativně rychlou implementaci jejího vyhodnocení.
2751 Vhodností jiných metrik pro fraktální kompresi se zabývá například
2752 \begin_inset space ~
2756 \begin_inset CommandInset citation
2765 \begin_layout Standard
2766 PIFS uvažuje afinní zobrazení z
2767 \begin_inset space ~
2770 jednoho zdrojového bloku do jednoho cílového bloku.
2771 To lze zobecnit na hledání zobrazení z
2772 \begin_inset space ~
2775 dvou nebo více zdrojových bloků.
2776 Víceprůchodové komprese, kde se jednoduše kóduje chyba předchozího kroku,
2777 nedávají lepší výsledky.
2778 Přímé hledání zobrazení z
2779 \begin_inset space ~
2782 více zdrojových bloků ke zlepšení kvality výsledku vede, ale množství kombinací
2783 zde roste ještě mnohem rychleji než v
2784 \begin_inset space ~
2787 klasické PIFS kompresi.
2789 \begin_inset space ~
2793 \begin_inset CommandInset citation
2799 je navrženo snižovat složitost pomocí redukce podobných zdrojových bloků
2800 a použití hladového přístupu.
2803 \begin_layout Subsection
2807 \begin_layout Subsubsection
2811 \begin_layout Standard
2812 Fraktální dekomprese bývá považována za velmi rychlou, což je způsobeno
2814 \begin_inset space ~
2819 \begin_inset space ~
2822 skutečnosti se stále vyplatí pracovat na jejím zrychlení.
2823 Při prvních iteracích zobrazení je obrázek složen z
2824 \begin_inset space ~
2827 jednolitých bloků a je tedy zbytečné pracovat v
2828 \begin_inset space ~
2834 \begin_layout Standard
2836 \begin_inset space ~
2840 \begin_inset CommandInset citation
2846 , stačí začít dekompresi na zmenšeném obrázku, kde nejmenší cílové bloky
2847 zabírají jediný pixel, a po každé iteraci zobrazení pak zvětšit obrázek
2848 na dvojnásobek (efektivní především při dělení čtyřstromem).
2850 \begin_inset space ~
2853 plné velikosti pak stačí udělat jen okolo dvou iterací.
2856 \begin_layout Subsubsection
2857 Progresivní dekódování
2860 \begin_layout Standard
2861 Při praktickém využití je důležitá možnost progresivního dekódování obrázků
2862 \begin_inset space ~
2865 --- generování náhledů s
2866 \begin_inset space ~
2869 použitím pouze malé počáteční části souboru.
2870 To je užitečné především na internetových stránkách, nebo při prohlížení
2872 \begin_inset space ~
2875 velkým množstvím fotografií.
2876 Progresivním dekódováním pro klasický PIFS se zabývá
2877 \begin_inset space ~
2881 \begin_inset CommandInset citation
2890 \begin_layout Standard
2891 Při použití modifikací nahrazující konstantní koeficienty barevných zobrazení
2892 průměrnými barvami cílových bloků lze ale postupovat mnohem efektivněji
2893 \begin_inset space ~
2896 --- uložit nejprve způsob rozdělení na bloky (zabere velmi málo místa),
2897 potom průměrné barvy všech cílových bloků a pak až ostatní parametry.
2899 \begin_inset space ~
2902 velmi malé části souboru náhled jen z
2903 \begin_inset space ~
2906 průměrných barev bloků, který může vypadat relativně dobře, obzvláště pokud
2907 se pro zobrazení použijí pokročilé interpolační metody.
2910 \begin_layout Subsection
2911 Využití technik fraktální komprese pro jiné účely
2914 \begin_layout Standard
2915 Fraktální komprese má velmi zajímavé vlastnosti, které lze využít i pro
2916 další, často velmi odlišné, účely.
2917 V této části budou nějdůležitějších z
2918 \begin_inset space ~
2921 nich zmíněny, ale jen velmi stručně a bez odkazů na zdroje.
2924 \begin_layout Standard
2925 Díky možnosti dekódování v
2926 \begin_inset space ~
2929 libovolném rozlišení lze použít fraktální kompresi pro inteligentní zvětšování
2931 Při správném nastavení dává velmi dobré výsledky díky tomu, že zvětšenina
2932 nepůsobí rozmazaným dojmem a ostré hrany jsou výborně zachovány.
2935 \begin_layout Standard
2937 \begin_inset space ~
2940 podobných důvodů lze fraktální kompresi použít i pro čištění obrázků od
2942 Při kontraktivních zobrazeních mezi bloky se totiž šum velmi potlačí a
2943 proto nelze typicky najít zdrojový blok, který by šum v
2944 \begin_inset space ~
2947 cílovém bloku napodobil.
2948 Větší útvary a ostré hrany se naopak většinou podaří mezi zdrojovými bloky
2949 najít, takže zůstanou zachovány.
2952 \begin_layout Standard
2953 Je také zkoumáno přidávání
2954 \begin_inset Quotes gld
2958 \begin_inset Quotes grd
2961 do obrázků pomocí fraktální komprese.
2962 Ty mají velmi zajímavé vlastnosti
2963 \begin_inset space ~
2966 --- nejsou vidět (ale lze je z
2967 \begin_inset space ~
2970 obrázku extrahovat) a jsou velmi odolné proti ořezávání obrázku, JPEG kompresi
2972 \begin_inset space ~
2978 \begin_layout Standard
2979 Dále je diskutována možnost využití technik fraktální komprese pro videonahrávky.
2980 Největší redundance je zde v
2981 \begin_inset space ~
2984 podobnosti mezi po sobě následujícími snímky.
2986 \begin_inset space ~
2989 klasických metodách se používají bloky některých snímků jako predikce stejně
2990 umístěných (případně trochu posunutých) bloků jiných snímků a kóduje se
2992 Stejnou metodu lze využít i při fraktální kompresi, ale nabízí se mnohem
2993 přirozenější rozšíření.
2995 \begin_inset space ~
2998 dvoudimenzionálnímu prostoru pixelů v
2999 \begin_inset space ~
3002 obrázcích přidat třetí dimenzi tvořenou časem.
3003 Potom videozáznam dělený na
3004 \begin_inset Quotes gld
3008 \begin_inset Quotes grd
3011 místo obdélníků lze komprimovat podobným způsobem jako obrázky pomocí zobrazení
3012 mezi trojdimenzionálními bloky.
3013 Zde je zajímavá například možnost dekódování ve vyšším rozlišení
3014 \begin_inset space ~
3017 --- lze tak generovat rozumné mezisnímky, které v
3018 \begin_inset space ~
3021 původní nahrávce nebyly.
3024 \begin_layout Chapter
3025 Chyba zobrazení mezi bloky
3026 \begin_inset CommandInset label
3028 name "Chyba_zobrazení"
3035 \begin_layout Standard
3037 \begin_inset space ~
3040 této kapitole je rozebrána nejdůležitější část komprese
3041 \begin_inset space ~
3044 --- výpočet chyby optimálního zobrazení mezi dvojicí bloků.
3048 \begin_layout Standard
3050 \begin_inset space ~
3053 následujících výpočtech budeme pro zjednodušení pracovat se zdrojovým blokem,
3054 který je už zmenšen na velikost cílového a správně otočen.
3055 Navíc použijeme diskrétní model obrázku, přestože analogická odvození lze
3056 udělat i se spojitým modelem.
3057 Protože zde pracujeme s
3058 \begin_inset space ~
3061 RMSE metrikou, nehraje tvar bloků žádnou roli.
3062 Bloky budou uvažovány jako jednorozměrné vektory hodnot, indexované tak,
3063 aby sobě odpovídající hodnoty zdrojových a cílových bloků měly stejné indexy
3064 (ovlivněno rotacemi).
3066 \begin_inset Formula $i$
3069 -tého pixelu zdrojového a cílového bloku budeme značit
3070 \begin_inset Formula $d_{i}$
3074 \begin_inset Formula $r_{i}$
3078 \begin_inset Formula $i$
3082 \begin_inset space ~
3086 \begin_inset Formula $\left\{ 1,2,\ldots,n\right\} $
3092 \begin_layout Standard
3093 Je potřeba si uvědomit, že zde jsou počítané odchylky mezi původním obrázkem
3094 a jeho obrazem, přestože ve skutečnosti potřebujeme omezit odchylku obrázku
3095 od pevného bodu zobrazení.
3097 \begin_inset space ~
3101 \begin_inset space ~
3105 \begin_inset CommandInset ref
3111 byla diskutována možnost použití kolážové věty, která skutečnou chybu omezuje,
3113 \begin_inset space ~
3116 praxi je nepoužitelná.
3117 Hlavním důvodem je to, že dává příliš volný odhad, který neodpovídá realitě
3118 a také je nepříjemné, že plnění předpokladu kontraktivity barevných zobrazení
3119 výslednou odchylku výrazně zvětšuje.
3122 \begin_layout Section
3126 \begin_layout Standard
3127 Ve fraktální kompresi se používá několik ukazatelů míry odchylky obrázku
3128 od originálu, které jsou vzájemně velmi provázané.
3130 \begin_inset space ~
3134 \begin_inset Formula $e_{i}$
3138 \begin_inset space ~
3141 --- rozdílů hodnot jednotlivých pixelů (uvažujeme jednobarevný obrázek).
3144 \begin_layout Standard
3145 Pro výpočty je velmi vhodná SE (
3149 ) metrika měřící čtvercovou chybu.
3150 \begin_inset Formula \[
3151 \mathrm{SE}=\sum_{i=1}^{n}e_{i}^{2}\]
3155 Někdy se používá její normalizovaná verze, která umožňuje korektní porovnávání
3156 odchylek naměřených na různě velkých obrázcích.
3159 root mean square error
3161 ) je vždy stejný jako rozsah hodnot pixelů.
3163 \begin_inset Formula \[
3164 \mathrm{RMSE}=\sqrt{\frac{\mathrm{SE}}{n}}\]
3168 Pro porovnávání různých metod je vhodnějším měřítkem PSNR kvalita (
3170 peak signal-to-noise ratio
3172 ), protože je nezávislá na rozsahu hodnot pixelů a je v
3173 \begin_inset space ~
3176 logaritmickém měřítku.
3178 \begin_inset space ~
3182 \begin_inset space ~
3185 rozsahu nula až nekonečno, kde nekonečno odpovídá nulové odchylce.
3189 \begin_layout Standard
3190 \begin_inset Formula \[
3191 \mathrm{PSNR}=-20\log_{10}\frac{\mathrm{RMSE}}{M},\mbox{\quad kde hodnoty pixelů jsou z\, rozsahu 0--\ensuremath{M}}.\]
3198 \begin_layout Section
3200 \begin_inset CommandInset label
3202 name "Chyba_zobrazení/Klasická"
3209 \begin_layout Standard
3210 Při klasické fraktální kompresi je chyba zobrazení dána
3211 \begin_inset Formula \[
3212 \mathrm{SE}=\sum_{i=1}^{n}\left(ud_{i}+v-r_{i}\right)^{2},\]
3216 přičemž uvažujeme minimum pro libovolné konstanty
3217 \begin_inset Formula $u$
3221 \begin_inset Formula $v$
3225 Úloha odpovídá lineární regresi používané ve statistice, kde RMSE metrika
3226 dává volbu koeficientů metodou nejmenších čtverců.
3227 Použitím derivací a řešením jednoduché soustavy rovnic
3231 \begin_layout Plain Layout
3233 \begin_inset space ~
3236 sum jsou dále vynechány, protože jsou vždy stejné a zbytečně by výpočty
3252 \begin_inset Formula \begin{eqnarray*}
3253 {\textstyle 2u\sum d_{i}^{2}+2v\sum d_{i}-2\sum r_{i}d_{i}} & = & 0\\
3254 {\textstyle 2u\sum d_{i}+2nv-2\sum r_{i}} & = & 0\end{eqnarray*}
3258 lze spočítat obecné optimální hodnoty koeficientů
3259 \begin_inset Formula \[
3260 \hat{u}=\frac{n\sum r_{i}d_{i}-\left(\sum d_{i}\right)\left(\sum r_{i}\right)}{n\sum d_{i}^{2}-\left(\sum d_{i}\right)^{2}},\qquad\hat{v}=\frac{\left(\sum d_{i}^{2}\right)\left(\sum r_{i}\right)-\left(\sum d_{i}\right)\left(\sum r_{i}d_{i}\right)}{n\sum d_{i}^{2}-\left(\sum d_{i}\right)^{2}}.\]
3264 Jmenovatele jsou nulové právě když má zdrojový blok konstantní barvu, což
3265 je případ, který můžeme vyloučit například proto, že při něm chyba zobrazení
3266 nemůže být lepší než s
3267 \begin_inset space ~
3270 libovoným jiným zdrojovým blokem.
3271 Díky tomu, že matice druhých parciálních derivací
3272 \begin_inset Formula \[
3273 {\displaystyle \left(\begin{array}{cc}
3274 \frac{\partial^{2}\mathrm{SE}}{\partial u^{2}} & \frac{\partial^{2}\mathrm{SE}}{\partial u\,\partial v}\\
3275 \frac{\partial^{2}\mathrm{SE}}{\partial u\,\partial v} & \frac{\partial^{2}\mathrm{SE}}{\partial v^{2}}\end{array}\right)=\left(\begin{array}{cc}
3276 2\sum d_{i}^{2} & 2\sum d_{i}\\
3277 2\sum d_{i} & 2n\end{array}\right)}\]
3281 je pozitivně definitní pro libovolný nekonstantní zdrojový blok, jedná se
3283 \begin_inset space ~
3287 Zpětným dosazením optimálních parametrů do vzorce pro chybu a úpravou získáme
3289 \begin_inset Formula \[
3290 \widehat{SE}=\frac{\left(\sum r_{i}d_{i}\right)\left[2\left(\sum d_{i}\right)\left(\sum r_{i}\right)-n\sum r_{i}d_{i}\right]-\left(\sum d_{i}^{2}\right)\left(\sum d_{i}\right)^{2}}{n\sum d_{i}^{2}-\left(\sum d_{i}\right)^{2}}+\sum r_{i}^{2}.\]
3294 Pomocí struktur uvedených v
3295 \begin_inset space ~
3299 \begin_inset CommandInset ref
3301 reference "Implementace/Matice"
3305 lze všechny sumy kromě jedné snadno spočítat.
3307 \begin_inset Formula $\sum r_{i}d_{i}$
3310 je nutné vyčíslit pro každou uvažovanou dvojici bloků zvlášť.
3313 \begin_layout Section
3314 Chyba upravených zobrazení
3315 \begin_inset CommandInset label
3317 name "Chyba_zobrazení/Upravená"
3324 \begin_layout Standard
3326 \begin_inset space ~
3329 implementaci je použita úprava klasického modelu popsaná v
3330 \begin_inset space ~
3334 \begin_inset CommandInset ref
3336 reference "PIFS/Použitý_model"
3340 , kde místo koeficientů
3341 \begin_inset Formula $u$
3345 \begin_inset Formula $v$
3348 je uložena průměrná hodnota a směrodatná odchylka hodnot cílového bloku.
3349 Koeficienty zobrazení jsou pak počítány v
3350 \begin_inset space ~
3354 \begin_inset space ~
3357 těchto uložených hodnot a ze stavu zdrojového bloku v
3358 \begin_inset space ~
3362 Nová definice koeficientů je
3363 \begin_inset Formula \[
3364 \bar{u}=\pm\frac{\sqrt{n\sum r_{i}^{2}-\left(\sum r_{i}\right)^{2}}}{\sqrt{n\sum\bar{d}_{i}^{2}-\left(\sum\bar{d_{i}}\right)^{2}}},\qquad\bar{v}=\frac{1}{n}\sum r_{i}-\frac{\bar{u}}{n}\sum\bar{d}_{i},\]
3369 \begin_inset Formula $\bar{d_{i}}$
3372 je značení pro hodnotu pixelu zdrojového bloku z
3373 \begin_inset space ~
3379 \begin_layout Standard
3380 Tím je ovlivněna i optimální chyba zobrazení, protože ani za předpokladu
3381 zobrazování původního obrázku se nemusí
3382 \begin_inset Formula $\bar{u}$
3386 \begin_inset Formula $u$
3390 Pro následující odvození bude použito statistické značení, které je zde
3394 \begin_layout Description
3396 \begin_inset space ~
3400 \begin_inset space ~
3404 \begin_inset Formula ${\displaystyle s_{r}=\sqrt{\frac{1}{n-1}\left[\sum_{i=1}^{n}r_{i}^{2}-\frac{1}{n}\left(\sum_{i=1}^{n}r_{i}\right)^{2}\right]}}$
3410 \begin_layout Description
3412 \begin_inset space ~
3416 \begin_inset Formula ${\displaystyle q_{d,r}=\frac{1}{n-1}\left(\sum_{i=1}^{n}d_{i}r_{i}-\frac{1}{n}\sum_{i=1}^{n}d_{i}\sum_{i=1}^{n}r_{i}\right)}$
3422 \begin_layout Description
3424 \begin_inset space ~
3428 \begin_inset Formula ${\displaystyle \rho_{d,r}=\frac{q_{d,r}}{s_{d}s_{r}}}$
3434 \begin_layout Description
3435 konvergence frázemi typu
3436 \begin_inset Quotes gld
3442 \begin_inset Formula $a\rightarrow b$
3446 \begin_inset Formula $c\rightarrow d$
3452 \begin_inset Quotes grd
3456 \begin_inset Formula ${\displaystyle \lim_{a\rightarrow b}c=d}$
3462 \begin_layout Standard
3472 Optimální lineární koeficient
3482 \begin_inset Formula ${\displaystyle u=\frac{q_{d,r}}{s_{d}^{2}}}$
3485 bude nahrazen koeficientem
3486 \begin_inset Formula ${\displaystyle \bar{u}=\pm\frac{s_{r}}{s_{\bar{d}}}}$
3490 Pokud povolíme zobrazení se záporným lineárním koeficientem, je nutné také
3491 uložit znaménko (zde značeno symbolem
3492 \begin_inset Formula $\pm$
3496 Při implementaci je navíc potřeba ošetřit situaci, kdy
3497 \begin_inset Formula $s_{\bar{d}}=0$
3500 , což nastává hlavně při první iteraci pro typický případ inicializace celého
3501 obrázku šedivou barvou.
3504 \begin_layout Standard
3515 \begin_inset Formula $s_{\bar{d}}\rightarrow s_{d}$
3518 (platí speciálně když
3519 \begin_inset Formula $\bar{d}\rightarrow d$
3523 \begin_inset Formula \[
3524 {\displaystyle \frac{u}{\bar{u}}\rightarrow\pm\frac{q_{d,r}}{s_{d}^{2}}\frac{s_{d}}{s_{r}}=\pm\frac{q_{d,r}}{s_{d}s_{r}}}=\pm\rho_{d,r}.\]
3528 Pokud byla chyba barevného zobrazení s
3529 \begin_inset space ~
3533 \begin_inset Formula $u$
3537 \begin_inset space ~
3541 \begin_inset Formula $\rho_{d,r}\rightarrow\pm1$
3546 \begin_inset Formula $u$
3549 je stejné jako znaménko
3550 \begin_inset Formula $\rho_{d,r}$
3554 \begin_inset Formula $\bar{u}\rightarrow u$
3559 \begin_inset space ~
3562 toho je zřejmé, že cílový obrázek bude pevným bodem i takto pozměněného
3564 \begin_inset VSpace bigskip
3570 \begin_layout Standard
3571 Novou čtvercovou chybu lze vyjádřit jako
3572 \begin_inset Formula \begin{equation}
3573 \mathrm{\overline{SE}}\;=\;\sum_{i=1}^{n}\left(\bar{u}\bar{d}_{i}+\bar{v}\right)^{2}.\label{Chyba/SE_vzorec}\end{equation}
3577 Po postupném dosazení
3578 \begin_inset Formula $\bar{v}=\frac{1}{n}\sum r_{i}-\frac{\bar{u}}{n}\sum\bar{d}_{i}$
3582 \begin_inset Formula ${\displaystyle \bar{u}=\pm\frac{s_{r}}{s_{\bar{d}}}}$
3586 \begin_inset Formula \begin{multline*}
3587 \mathrm{\overline{SE}}\;=\;\sum_{i=1}^{n}\left[\bar{u}\left(\bar{d}_{i}-\frac{1}{n}\sum\bar{d}_{j}\right)-\left(r_{i}-\frac{1}{n}\sum r_{j}\right)\right]^{2}\;=\\
3588 =\;{\textstyle \bar{u}^{2}{\displaystyle \sum_{i=1}^{n}}\left(\bar{d}_{i}-\frac{\sum\bar{d}_{j}}{n}\right)^{2}-2\bar{u}{\displaystyle \sum_{i=1}^{n}}\left(\bar{d}_{i}-\frac{\sum\bar{d}_{j}}{n}\right)\left(r_{i}-\frac{\sum r_{j}}{n}\right)+{\displaystyle \sum_{i=1}^{n}}\left(r_{i}-\frac{\sum r_{j}}{n}\right)^{2}\;=}\\
3589 {\displaystyle =\; n\bar{u}^{2}s_{\bar{d}}^{2}-2n\bar{u}q_{\bar{d},r}+ns_{r}^{2}\;=\; n\frac{s_{r}^{2}}{s_{\bar{d}}^{2}}s_{\bar{d}}^{2}\mp2n\frac{s_{r}}{s_{\bar{d}}}q_{\bar{d},r}+ns_{r}^{2}\;=\;2n\left(s_{r}^{2}\mp\frac{s_{r}}{s_{\bar{d}}}q_{\bar{d},r}\right)}.\end{multline*}
3594 \begin_inset Formula $q_{\bar{d},r}$
3597 má vždy stejné znaménko jako
3598 \begin_inset Formula $\bar{u}$
3601 , lze výraz upravit na
3602 \begin_inset Formula \[
3603 \mathrm{\overline{SE}}\;=\;2ns_{r}^{2}\left(1-\frac{\left|q_{\bar{d},r}\right|}{s_{\bar{d}}s_{r}}\right)\;=\;2ns_{r}^{2}\left(1-\left|\rho_{\bar{d},r}\right|\right).\]
3608 \begin_inset VSpace bigskip
3614 \begin_layout Standard
3615 Původní optimální čtvercovou chybu lze přepsat do tvaru:
3618 \begin_layout Standard
3619 \begin_inset Formula \[
3620 \mathrm{\widehat{SE}}\;=\; n\frac{s_{d}^{2}s_{r}^{2}-q_{d,r}^{2}}{s_{d}^{2}}\;=\; ns_{r}^{2}\left(1-\rho_{d,r}^{2}\right)\;=\; ns_{r}^{2}\left(1-\left|\rho_{d,r}\right|\right)\left(1+\left|\rho_{d,r}\right|\right).\]
3625 \begin_inset Formula $s_{\bar{d}}\rightarrow s_{d}$
3628 , dostaneme absolutní a relativní nárůst chyby
3629 \begin_inset Formula \[
3630 \mathrm{\overline{SE}}-\mathrm{\widehat{SE}}\;=\; ns_{r}^{2}\left(1-\left|\rho_{d,r}\right|\right)\left[2-\left(1+\left|\rho_{d,r}\right|\right)\right]\;=\; ns_{r}^{2}\left(1-\left|\rho_{d,r}\right|\right)^{2}\]
3637 \begin_layout Standard
3638 \begin_inset Formula \[
3639 \frac{\mathrm{\overline{SE}}-\mathrm{\widehat{SE}}}{\mathrm{\widehat{SE}}}=\frac{\left(1-\left|\rho_{d,r}\right|\right)^{2}}{\left(1-\left|\rho_{d,r}\right|\right)\left(1+\left|\rho_{d,r}\right|\right)}=\frac{1-\left|\rho_{d,r}\right|}{1+\left|\rho_{d,r}\right|}\]
3644 \begin_inset VSpace defskip
3647 Pro vzájemně dobře zobrazitelné bloky
3648 \begin_inset Formula $\left|\rho_{d,r}\right|\rightarrow1$
3651 , takže nárůst chyby bude velmi malý.
3654 \begin_layout Section
3655 Penalizace vysokého lineárního koeficientu
3656 \begin_inset CommandInset label
3658 name "Chyba_zobrazení/Penalizace"
3665 \begin_layout Standard
3666 Výše zmíněnou úpravou barevných zobrazení bylo sníženo riziko divergence
3667 zobrazení bez nutnosti omezení lineárního koeficientu.
3668 Díky tomu, že všechny hodnoty jsou omezeny v
3669 \begin_inset space ~
3673 \begin_inset Formula $\left\langle 0,1\right\rangle $
3676 a cílové bloky mají vždy správnou průměrnou hodnotu, nemohou se obrazy
3677 zobrazení od původního obrázku příliš lišit (v
3678 \begin_inset space ~
3681 praxi funguje dobře, ale bez jakéhokoliv důkazu omezení odchylky).
3684 \begin_layout Standard
3685 Přesto jsou vysoké lineární koeficienty nebezpečné, protože zdrojové bloky
3686 jsou při dekódování vždy pouze aproximací jejich stavu v
3687 \begin_inset space ~
3691 Čím vyšší je lineární koeficient, tím více se případná odchylka zdrojového
3692 bloku distribuuje do cílového a poté případně v
3693 \begin_inset space ~
3696 dalších iteracích i do jiných zdrojových bloků.
3699 \begin_layout Standard
3700 Proto je zde navržena následující penalizace, která zvyšuje odhadovanou
3702 \begin_inset space ~
3705 závislosti na jeho lineárním koeficientu.
3706 Pokud vyjdeme ze vzorce pro chybu (
3707 \begin_inset CommandInset ref
3709 reference "Chyba/SE_vzorec"
3714 \begin_inset space ~
3717 hodnotám zdrojového bloku odchylku
3718 \begin_inset Formula $\epsilon_{i}$
3722 \begin_inset Formula \[
3723 \mathrm{\widetilde{SE}}\;=\;\sum_{i=1}^{n}\left[\bar{u}\left(\bar{d}_{i}+\epsilon_{i}\right)+\bar{v}\right]^{2}\;=\;\sum_{i=1}^{n}\left[\left(\bar{u}\bar{d}_{i}+\bar{v}\right)^{2}+\left(\bar{u}\bar{d}_{i}+\bar{v}\right)\bar{u}\epsilon_{i}+\bar{u}^{2}\epsilon_{i}^{2}\right].\]
3727 Když označíme původní odchylku
3728 \begin_inset Formula $e_{i}=\bar{u}\bar{d}_{i}+\bar{v}$
3732 \begin_inset Formula \[
3733 \mathrm{\widetilde{SE}}\;=\;{\textstyle \sum}e_{i}^{2}+\bar{u}{\textstyle \sum}e_{i}\epsilon_{i}+\bar{u}^{2}{\textstyle \sum}\epsilon_{i}^{2}.\]
3737 První suma je zřejmě rovna původní chybě
3738 \begin_inset Formula $\mathrm{\overline{SE}}$
3742 \begin_inset space ~
3746 \begin_inset CommandInset ref
3748 reference "Chyba/SE_vzorec"
3753 Hodnota druhé sumy je závislá na korelaci odchylek způsobených nepřesností
3754 zobrazení a odchylek ve zdrojovém bloku.
3755 Lze snadno ukázat, že
3756 \begin_inset Formula $\sum e_{i}=0$
3759 (platí díky tomu, že optimální zobrazení v
3760 \begin_inset space ~
3763 RMSE metrice zobrazují průměrnou hodnotu zdrojového bloku na průměrnou hodnotu
3765 Za předpokladu, že chyby
3766 \begin_inset Formula $\epsilon_{i}$
3769 nejsou korelované, vyjde nulová očekávaná hodnota
3773 \begin_layout Plain Layout
3782 ) je zde používáno ve smyslu teorie pravděpodobnosti a statistiky
3790 \begin_layout Standard
3791 Třetí suma odpovídá odchylce zmenšeného zdrojového bloku.
3792 Pokud požadovanou odchylku pro cílový blok označíme
3793 \begin_inset Formula $\mathrm{SE'}$
3796 a poměr velikostí zdrojového bloku po zmenšení a před zmenšením označíme
3798 \begin_inset Formula $\alpha\in\left(0,1\right)$
3801 , pak lze očekávat, že se bude odchylka zdrojového bloku před zmenšením
3803 \begin_inset Formula $\frac{\mathrm{SE'}}{\alpha}$
3807 Když při zmenšování jeden pixel vzniká jako průměr
3808 \begin_inset Formula $\frac{1}{\alpha}$
3811 pixelů zdrojového bloku s
3812 \begin_inset space ~
3815 nekorelovanými odchylkami, pak očekávaná čtvercová chyba zmenšeného zdrojového
3817 \begin_inset Formula $\alpha\cdot\mathrm{SE'}$
3820 , tedy nová chyba zobrazení zahrnující očekávanou odchylku se zjednoduší
3831 \begin_inset Formula \[
3832 \mathrm{\widetilde{SE}}\;\approx\;\mathrm{\overline{SE}}\ +\ \bar{u}^{2}\alpha\ \mathrm{SE'}\;=\;\mathrm{\overline{SE}}\ +\ \alpha\frac{s_{r}^{2}}{s_{\bar{d}}^{2}}\ \mathrm{SE'}\]
3839 \begin_layout Standard
3840 Celé odvození penalizace lze analogicky provést i pro klasický model zobrazování
3842 \begin_inset space ~
3846 \begin_inset CommandInset ref
3848 reference "Chyba_zobrazení/Klasická"
3853 \begin_inset space ~
3856 obou případech jsou používany nepodložené předpoklady, především předpoklad
3857 nekorelovanosti chyb jednotlivých pixelů, který by bylo vhodné alespoň
3861 \begin_layout Standard
3862 Implementace příslušného modulu (popsaná v
3863 \begin_inset space ~
3867 \begin_inset CommandInset ref
3869 reference "Implementace/Zobrazování"
3873 ) dává možnost započítat penalizaci do chyb zobrazení.
3874 Při jejím použití je dosahována výrazně vyšší kvalita dekódovaného obrázku
3875 než při klasickém počítání s
3876 \begin_inset space ~
3879 omezenou nebo neomezenou velikostí lineárních koeficientů za cenu pouze
3880 nepatrného poklesu kompresního poměru.
3883 \begin_layout Chapter
3885 \begin_inset CommandInset label
3894 \begin_layout Subsubsection
3898 \begin_layout Standard
3899 Cílem implementace bylo vytvořit framework pro studium fraktální komprese,
3900 kde by byly jednotlivé části algoritmů oddělené do modulů, aby bylo možné
3901 kompatibilní algoritmy snadno vzájemně vyměnovat a aby implementace jednotlivýc
3902 h technik byla tvořena převážně algoritmickým kódem, odděleně od správy
3903 závislostí mezi moduly, interakce s
3904 \begin_inset space ~
3907 uživatelem a nezávisle na způsobu implementace ostatních modulů.
3910 \begin_layout Standard
3911 Aby bylo možné jednotlivé techniky objektivně porovnávat, je kladen důraz
3912 na efektivitu implementace.
3914 \begin_inset space ~
3917 některých algoritmech, kde by dělení do více modulů významným způsobem snížilo
3918 efektivitu, upřednostněna konfigurace modulu pomocí jiných parametrů.
3921 \begin_layout Subsubsection
3922 Zvolené vývojové nástroje
3925 \begin_layout Standard
3926 Jako programovací jazyk pro implementaci bylo zvoleno C++, především kvůli
3927 kombinaci vysoké efektivity a mnoha pokročilých vlastností (například generické
3929 Pro překlad byl používán překladač z
3930 \begin_inset space ~
3933 rodiny GNU překladačů (GCC
3934 \begin_inset space ~
3938 \begin_inset CommandInset citation
3947 \begin_layout Standard
3948 Grafické uživatelské rozhraní (GUI) je realizováno pomocí knihoven Qt
3949 \begin_inset space ~
3953 \begin_inset CommandInset citation
3959 , které také zajišťují čtení a zápis obrázků ve standardních formátech (BMP,
3963 \begin_layout Standard
3964 Díky použitým prostředkům by měl být celý program snadno přenositelný (na
3965 úrovni zdrojového kódu).
3966 Vývoj a ladění probíhaly na GNU/Linux, s
3967 \begin_inset space ~
3970 testováním také na MS
3971 \begin_inset space ~
3975 \begin_inset space ~
3981 \begin_layout Section
3985 \begin_layout Standard
3986 Oddělení modulů do jednotlivých dynamických knihoven by zde nepřineslo významný
3987 užitek, takže byla zvolena kompilace celého programu do jednoho spustitelného
3988 souboru (kromě knihoven Qt).
3989 Přesto jsou zde minimalizovány vzájemné závislosti mezi moduly.
3992 \begin_layout Standard
3993 Deklarace související s
3994 \begin_inset space ~
3998 \begin_inset space ~
4005 , většina implementace je pro přehlednost v
4006 \begin_inset space ~
4014 \begin_layout Subsubsection
4015 Základní vlastnosti modulů
4018 \begin_layout Standard
4019 Všechny moduly jsou potomky třídy
4023 , která definuje základní společné vlastnosti, především způsob reprezentace
4025 Je zde virtuální metoda
4029 , která vrací referenci na strukturu obsahující informace o
4030 \begin_inset space ~
4034 \begin_inset space ~
4037 --- jeho identifikační číslo, jméno, text popisující funkci, počet parametrů
4038 nastavení a ukazatel na pole obsahující vlastnosti jednotlivých parametrů
4039 nastavení (typ, rozsah hodnot, název a popis).
4044 obsahuje ukazatel na pole skutečných hodnot nastavení pro daný modul a
4045 také spoustu dalších pomocných typů a metod.
4048 \begin_layout Standard
4049 Tento způsob práce s
4050 \begin_inset space ~
4053 nastaveními umožňuje jejich automatické měnění, ukládání a zobrazování libovolný
4054 m uživatelským rozhraním.
4055 Vše pomocí společného kódu odděleného od všech modulů.
4058 \begin_layout Standard
4059 Obsah zmíněné informační struktury je potřeba pro každý typ modulu nadefinovat,
4060 což by znamenalo mnoho opakujícího se technického kódu, a proto jsou pro
4061 tento účel vytvořeny funkce a makra, kterým stačí předat pouze jednotlivé
4062 vlastnosti (název, typy parametrů, \SpecialChar \ldots{}
4063 ), takže implementace jednotlivých modulů
4064 je jednodušší a přehlednější.
4067 \begin_layout Subsubsection
4071 \begin_layout Standard
4072 Aby framework mohl s
4073 \begin_inset space ~
4076 modulem pracovat, je potřeba upravit soubor
4080 vložením hlavičkového souboru (pomocí
4084 ) a přidáním typu modulu do seznamu
4090 \begin_inset space ~
4093 souboru se postará o
4094 \begin_inset space ~
4097 možnost volby modulu, závislosti a další technické záležitosti.
4098 Zde je nejsložitější generování některých metod z
4099 \begin_inset space ~
4102 tohoto seznamu typů, pro které je využita část z
4103 \begin_inset space ~
4106 knihovny, kterou napsal Andei Alexandrescu jako přílohu ke knize
4111 \begin_inset space ~
4115 \begin_inset CommandInset citation
4124 \begin_layout Standard
4126 \begin_inset space ~
4129 správu modulů a vytváření nových slouží třída
4131 Module\SpecialChar \-
4135 Ta má jedinou instanci, která při startu vytvoří prototyp pro každý typ
4137 Prototypy uchovávají výchozí nastavení jednotlivých typů modulů a je možné
4138 je použít pro získání obecných informací o
4139 \begin_inset space ~
4142 typech modulů (metoda
4146 ) nebo pro vytváření dalších instancí.
4149 \begin_layout Standard
4150 Nové moduly jsou vytvářeny zásadně klonováním, mělkým nebo hlubokým.
4151 Oba způsoby vytvoří novou instanci pomocí kopírovacího konstruktoru a zkopírují
4153 Mělké klonování navíc vynuluje odkazy na podřízené moduly, zatímco hluboké
4154 klonování je naklonuje stejným způsobem.
4155 Hluboké klonování se hodí například pro vytvoření nového výchozího stromu
4156 modulů (například před kompresí) a mělké se používá při načítání ze souborů,
4157 kde není ve chvíli vytváření modulů zřejmé, jakých typů budou podřízené
4161 \begin_layout Subsubsection
4162 Závislosti mezi moduly
4165 \begin_layout Standard
4166 Jsou definována rozhraní, každé popisující jednu požadovanou funkcionalitu.
4167 Všechna použitá rozhraní se nacházejí v
4168 \begin_inset space ~
4181 \begin_inset space ~
4184 nich je potomkem šablonované třídy
4186 Inter\SpecialChar \-
4189 , která zpřístupňuje seznam identifikátorů všech typů modulů implementujících
4190 toto rozhraní (kód je vygenerován ze seznamu
4197 \begin_layout Standard
4198 Každý modul implementuje právě jedno rozhraní a může využívat libovolné
4199 množství dalších rozhraní
4200 \begin_inset space ~
4204 \begin_inset space ~
4207 typů parametrů modulů je podřízený modul implementující zvolené rozhraní.
4208 Uživatel pak na tato místa může zapojit libovolný typ modulu (jsou zobrazeny
4209 pouze kompatibilní typy).
4210 Konfigurace komprese je tedy dána tímto stromem typů modulů spolu s
4211 \begin_inset space ~
4214 jejich dalším nastavením.
4217 \begin_layout Section
4221 \begin_layout Subsubsection
4225 \begin_layout Standard
4226 Rozhraní pro kořenový modul je navrženo jako jediný přístupový bod pro GUI
4227 ke kompresi a dekompresi.
4230 \begin_layout Standard
4231 Kořen včetně celého stromu může být ve třech různých stavech.
4233 \begin_inset space ~
4236 počátečním prázdném stavu strom neobsahuje žádný obrázek, ale může v
4237 \begin_inset space ~
4240 něm docházet ke změnám konfigurace, včetně vyměňování podřízených modulů.
4243 \begin_layout Standard
4245 \begin_inset space ~
4248 počátečního stavu může přejít do komprimovaného stavu úspěšným voláním metody
4253 , které je předán bitmapový obrázek ke kompresi (třída knihoven Qt) a reference
4255 \begin_inset Note Note
4258 \begin_layout Plain Layout
4264 umožňující komunikaci s
4265 \begin_inset space ~
4268 jiným vláknem během tohoto často zdlouhavého procesu.
4269 Pokud nebylo možné kompresi dokončit (například kvůli přerušení uživatelem),
4275 \begin_inset space ~
4281 \begin_layout Standard
4282 Druhou možností je přejít z
4283 \begin_inset space ~
4286 počátečního stavu do dekomprimovaného stavu úspěšným voláním metody
4291 , které je předán proud bytů obsahující komprimovanou podobu obrázku a míra
4292 přiblížení pro dekompresi.
4293 Rozměry dekomprimovaného obrázku jsou původní rozměry vynásobené
4294 \begin_inset Formula $2^{i}$
4298 \begin_inset Formula $i$
4302 Pokud nebylo možné dekódovat obrázek, například kvůli špatnému formátu
4303 souboru, vrátí metoda
4307 a stav stromu se nezmění.
4310 \begin_layout Standard
4311 Dále rozhraní obsahuje metody pro ukládání obrázku v
4312 \begin_inset space ~
4315 komprimovaném stavu do proudu bytů, pro provádění dekódovacích akcí (vyčištění
4316 obrázku nebo iterování zobrazení), pro uložení momentálního stavu dekódování
4317 do bitmapového obrázku (třída knihoven Qt) a pro ukládání a nahrávání nastavení
4321 \begin_layout Subsubsection
4326 \begin_inset space \hfill{}
4336 \begin_layout Standard
4337 Implementace kořenového modulu umožňuje jednotné nastavení nejzákladnějších
4338 parametrů komprese a rozděluje fáze procesu mezi několik nezávislých modulů.
4341 \begin_layout Standard
4342 Kvůli uživatelské přívětivosti bylo zvoleno nastavování kvality komprese
4344 \begin_inset space ~
4348 Hodnota je pomocí zvoleného modulu s
4349 \begin_inset space ~
4358 konvertována na nejvyšší možnou čtvercovou chybu pro danou velikost cílového
4359 bloku (modul je ve skutečnosti použit až v
4360 \begin_inset space ~
4363 podřízených modulech).
4366 \begin_layout Standard
4367 Dále lze zvolit modul s
4368 \begin_inset space ~
4373 IColor\SpecialChar \-
4374 Trans\SpecialChar \-
4378 \begin_inset space ~
4382 \begin_inset space ~
4386 \begin_inset space ~
4391 IShape\SpecialChar \-
4392 Trans\SpecialChar \-
4395 zajišťující další fáze komprese a také maximální množství zdrojových bloků,
4396 protože je to velmi důležitý parametr pro všechny metody fraktální komprese.
4399 \begin_layout Section
4403 \begin_layout Subsubsection
4407 \begin_layout Standard
4408 Rozhraní pro konverzi kvality
4409 \begin_inset space ~
4413 \begin_inset space ~
4416 velikosti cílového bloku a nastavení kvality spočítá odpovídající maximální
4417 přípustnou čtvercovou odchylku.
4420 \begin_layout Subsubsection
4425 \begin_inset space \hfill{}
4430 modules/quality2SE.h
4435 \begin_layout Standard
4440 je triviální implementací rozhraní pro konverzi kvality, která používá
4441 čtvercovou odchylku nezávislou na velikostech bloků.
4442 Přípustná odchylka je pro nejvyšší kvalitu nulová a pak roste přibližně
4443 exponenciálně (exponenciální funkce je mírně posunutá tak, aby procházela
4445 \begin_inset Formula $100\%$
4451 \begin_layout Standard
4452 Bylo by sice přirozenější mít pro danou kvalitu místo čtvercové chyby konstantní
4454 \begin_inset space ~
4457 počtem pixelů bloku.
4459 \begin_inset space ~
4462 větší variabilitě velikostí bloků a ve většině případů i k
4463 \begin_inset space ~
4466 nepatrně lepší objektivní kvalitě (při stejném kompresním poměru), ale protože
4468 \begin_inset space ~
4471 tomto projektu nebyly implementovány žádné vyhlazovací techniky, objevily
4473 \begin_inset space ~
4476 velkých bloků velmi výrazné hrany, takže by se subjektivní kvalita zhoršila.
4477 Pro porovnání je implementována i tato možnost v
4478 \begin_inset space ~
4488 \begin_layout Section
4492 \begin_layout Subsubsection
4496 \begin_layout Standard
4497 Rozhraní převádí práci s
4498 \begin_inset space ~
4501 jedním barevným obrázkem na práci s
4502 \begin_inset space ~
4505 několika jednobarevnými.
4506 Barevné obrázky jsou reprezentované třídou
4511 \begin_inset space ~
4514 knihoven Qt, jednobarevné obrázky jsou zde definovány jako matice pixelů
4516 \begin_inset space ~
4519 ukazatelem na strukturu obsahující některé parametry (rozměry, přiblížení,
4520 kvalita komprese a modul pro její konverzi, maximální počet zdrojových
4522 \begin_inset Note Note
4525 \begin_layout Plain Layout
4526 rozepsat? aktualizační struktura? diskuze o volbě reprezentace?
4534 \begin_layout Standard
4535 Metody rozhraní umožňují vytvoření jednobarevných obrázků pro dané parametry
4536 a barevný obrázek, zpětné složení do barevného obrázku, uložení nebo načtení
4537 případných dat modulu.
4540 \begin_layout Subsubsection
4545 \begin_inset space \hfill{}
4550 modules/colorModel.*
4555 \begin_layout Standard
4560 je triviální implementací rozhraní pro zpracování barev, která nabízí práci
4562 \begin_inset space ~
4565 modelech RGB a YCbCr.
4566 Protože je citlivost oka na jednotlivé barevné složky různá, je navíc umožněno
4567 zvolit pro každou ze složek číslo z
4568 \begin_inset space ~
4572 \begin_inset Formula $\left[0;1\right]$
4575 , kterým se vynásobí původní kvalita komprese.
4578 \begin_layout Section
4579 Počítání s maticemi pixelů
4580 \begin_inset CommandInset label
4582 name "Implementace/Matice"
4589 \begin_layout Standard
4591 \begin_inset space ~
4598 je definováno mnoho generických struktur a několik funkcí pro jednoduchou
4600 \begin_inset space ~
4604 Tyto nástroje jsou pak použity v
4605 \begin_inset space ~
4608 mnoha modulech a jejich rozhraních.
4611 \begin_layout Subsubsection
4615 \begin_layout Standard
4616 Při ukládání digitálních obrázků se pro reprezentaci pixelu nejčastěji používá
4618 \begin_inset space ~
4622 Tento způsob je paměťově velmi úsporný, ale pro tento projekt se ukázal
4623 jako příliš omezující.
4624 Například už při převodu do jiných barevných modelů by mohlo docházet k
4625 \begin_inset space ~
4628 výraznějším ztrátám informace.
4629 Proto byla zvolena reprezentace pomocí čísla s
4630 \begin_inset space ~
4633 plovoucí řádovou čárkou z
4634 \begin_inset space ~
4638 \begin_inset Formula $\left[0;1\right]$
4642 Pro reprezentaci běžných pixelů postačují čísla s
4643 \begin_inset space ~
4648 jednoduchou přesností
4650 , ale pro většinu složitějších výpočtů a mezivýsledků jsou použita čísla
4652 \begin_inset space ~
4659 , aby byly minimalizovány zaokrouhlovací chyby.
4662 \begin_layout Subsubsection
4666 \begin_layout Standard
4667 Matice jsou reprezentovány tak, že jsou jejich prvky po sloupcích uloženy
4670 \begin_inset space ~
4673 maticemi zajišťuje šablona
4675 Matrix\SpecialChar \-
4678 (parametrizovaná typem prvků matice), která uchovává ukazatel na levý horní
4679 prvek a počet kroků nutných k
4680 \begin_inset space ~
4683 přechodu na další sloupec.
4684 Navenek poskytuje přirozené indexování, konverzi na instanci pouze pro
4685 čtení a další operace.
4688 \begin_layout Standard
4689 Oproti reprezentacím založených na ukládání jednotlivých řádkových nebo
4690 sloupcových vektorů má toto řešení mnoho výhod.
4691 Má menší nároky na spotřebu paměťi a na její alokátor, průchody jsou překladače
4692 m lépe optimalizovatelné a je možné vytvářet odkazy na podmatice.
4695 \begin_layout Subsubsection
4696 Rychlé sčítání podmatic
4699 \begin_layout Standard
4700 Některé moduly potřebují znát součty hodnot pixelů a jejich druhých mocnin
4701 na blocích se kterými pracují.
4702 Pro tyto účely je používána jednoduchá struktura (implementovaná v
4703 \begin_inset space ~
4708 Matrix\SpecialChar \-
4711 ), která si předpočítá součty pro všechny obdélníky začínající v
4712 \begin_inset space ~
4715 levém horním rohu a pak může spočítat součet libovolného obdélníka pouze
4716 ze čtyř rohových hodnot.
4719 \begin_layout Standard
4722 Matrix\SpecialChar \-
4725 není používána samostaně, ale jako součást šablony
4727 Summed\SpecialChar \-
4730 , která kromě matice vlastních hodnot obsahuje její rozměry a šablonu
4732 Matrix\SpecialChar \-
4735 pro rychlý výpočet součtů hodnot a jejich druhých mocnin.
4736 Konkrétně je definována struktura
4738 Summed\SpecialChar \-
4741 , která je jen instanciací šablony
4743 Summed\SpecialChar \-
4746 pro již zmíněné typy hodnot pixelů používané v
4747 \begin_inset space ~
4753 \begin_layout Subsubsection
4757 \begin_layout Standard
4759 \begin_inset space ~
4762 projektu je potřeba současně procházet dvě stejně velké obdélníkové podmatice
4763 a provádět nějakou činnost s
4764 \begin_inset space ~
4767 příslušnými dvojicemi jejich prvků, navíc je často nutné počítat s
4768 \begin_inset space ~
4772 \begin_inset space ~
4775 8 vzájemných afinních transformací podmatic.
4776 Opakovaně ručně psané cykly by velmi znepřehledňovaly kód a byly by potencionál
4778 Proto je zde použit jiný přístup využívající generické programovaní a optimaliz
4782 \begin_layout Standard
4783 Základem celé techniky je funkce
4788 , která má tři parametry
4789 \begin_inset space ~
4792 --- řídící iterátor, druhý (podřízený) iterátor a operátor.
4793 Funkce pak pouze najednou posouvá oba iterátory a na odpovídajících dvojicích
4794 prvků volá operátor.
4795 Díky tomu, že se jednotlivé části cyklu takto oddělí, je možné konkrétní
4796 alternativy implementovat a pak libovolně kombinovat.
4799 \begin_layout Standard
4800 Iterátory musí podporovat metody pro získání aktuálního prvku (nejlépe formou
4801 reference), posun na další prvek, posun na další seznam (řádek/sloupec),
4802 zahájení práce se seznamem a v
4803 \begin_inset space ~
4806 případě řídícího iterátoru také test konce seznamu a test úplného konce
4808 Operátor pak musí být schopný volání s
4809 \begin_inset space ~
4812 parametry prvků prvního a druhého iterátoru.
4813 Díky tomu, že funkce
4818 vrací koncový stav operátoru, lze jako operátor použít i strukturu, která
4819 do sebe sbírá nějaká data.
4822 \begin_layout Standard
4824 \begin_inset space ~
4827 souboru jsou přímo implementovány iterátory pro osm afinních zobrazení a
4828 také přetížení funkce
4834 \begin_inset space ~
4837 parametrech místo druhého iterátoru číslo afinní transformace, podle kterého
4838 vybere příslušný iterátor.
4839 Dále je zde iterátor pro třídu QImage používaný pro konverzi na matici
4840 a také několik jednoduchých operátorů pro výpočet součtu vzájemných součinů
4841 a pro afinní transformaci hodnot.
4844 \begin_layout Section
4848 \begin_layout Subsubsection
4850 \begin_inset CommandInset label
4852 name "Implementace/IShapeTransformer"
4859 \begin_layout Standard
4861 \begin_inset Quotes gld
4865 \begin_inset Quotes grd
4868 zajišťuje kompresi a dekompresi jednobarevných obrázků (definovaných v
4869 \begin_inset space ~
4874 IColor\SpecialChar \-
4875 Trans\SpecialChar \-
4879 Je zamýšleno jako rozcestí pro několik druhů voleb, například pro možnost
4881 \begin_inset space ~
4884 šestiúhelníkovému tvaru pixelů.
4888 \begin_layout Standard
4889 Ze souboru vstupujících obrázků je vytvořeno několik nezávislých
4893 , pro které lze provádět výpočty vzájemně paralelně.
4894 Rozhraní poskytuje metody pro provádění komprese a dekódovacích akcí pro
4899 a také ukládání do proudu bytů a zpětné nahrávání.
4903 \begin_layout Standard
4908 jsou ukládána po fázích, což umožňuje přidat v
4909 \begin_inset space ~
4912 budoucnu implementaci progresivního dekódování, přestože pro něj momentálně
4914 \begin_inset space ~
4917 kořenovém modulu podpora.
4918 Důležité pro účinnost progresivního dekódování je, že uspořádání fází má
4919 vyšší prioritu než dělení na jednobarevné části způsobené zpracováním barev
4920 nebo přílišnou velikostí obrázku.
4921 Proto bylo nutné dostat tento koncept už do tak obecného rozhraní.
4924 \begin_layout Subsubsection
4929 \begin_inset space \hfill{}
4934 modules/squarePixels.*
4939 \begin_layout Standard
4944 je implementací rozhraní pro
4945 \begin_inset Quotes gld
4949 \begin_inset Quotes grd
4953 \begin_inset space ~
4956 čtvercového tvaru pixelů, umožňující navíc dělení velkých obrázků na menší,
4957 nezávisle (případně i
4958 \begin_inset space ~
4961 paralelně) zpracovávané.
4965 \begin_inset space ~
4970 jsou použity zvolené moduly pro dělení na cílové bloky, pro výběr množiny
4971 zdrojových bloků a pro hledání optimálních zobrazení.
4974 \begin_layout Standard
4975 Dělení jednobarevných obrázků na
4980 \begin_inset space ~
4983 předaných bloků a probíhá rekurzivně.
4984 Každý blok, který je větší než nastavená mez, je rozdělen podle delší souřadnic
4985 e tak, že poměr velikostí je nejvýše dvojnásobný a navíc nově vzniklá strana
4986 levé/horní části má délku mocniny 2.
4989 \begin_layout Subsubsection
4990 \begin_inset Quotes gld
4994 \begin_inset Quotes grd
5000 \begin_layout Standard
5005 navazuje několik rozhraní a modulů obsahující v
5006 \begin_inset space ~
5014 Všechny pracují pouze s
5015 \begin_inset space ~
5018 klasickou (čtvercovou) topologií pixelů a upřednostňují čtvercové bloky
5020 \begin_inset space ~
5023 hraně délky mocniny 2.
5024 Často se pro libovolný blok definuje jeho
5029 \begin_inset Formula $i$
5032 takové, že oba rozměry jsou nejvýše
5033 \begin_inset Formula $2^{i}$
5041 je 2, což nejčastěji odpovídá blokům velikosti
5042 \begin_inset Formula $4\times4$
5048 \begin_layout Standard
5050 \begin_inset space ~
5055 ISquare\SpecialChar \-
5060 ISquare\SpecialChar \-
5065 ISquare\SpecialChar \-
5068 (definovanými níže) spolupracující na jenom
5072 často potřebují vzájemně volat své metody a také sdílet některá další data.
5073 Proto je definována struktura
5075 Plane\SpecialChar \-
5079 \begin_inset space ~
5089 \begin_layout Standard
5092 Plane\SpecialChar \-
5095 obsahuje vlastní jednobarevnou část obrázku zpracovávnou
5100 \begin_inset space ~
5105 Summed\SpecialChar \-
5109 \begin_inset space ~
5113 \begin_inset CommandInset ref
5115 reference "Implementace/Matice"
5120 Dále obsahuje ukazatele na moduly spolupracující na
5125 \begin_inset space ~
5128 některými nastaveními (definovanou v
5129 \begin_inset space ~
5134 IColor\SpecialChar \-
5135 Trans\SpecialChar \-
5141 \begin_layout Section
5142 Dělení na cílové bloky
5145 \begin_layout Subsubsection
5149 \begin_layout Standard
5150 Rozhraní pro dělení na obdélníkové cílové bloky definuje základní strukturu
5153 Range\SpecialChar \-
5156 pro reprezentaci cílového bloku, která obsahuje souřadnice jeho okrajů,
5161 bloku a přídavný ukazatel, do kterého si spolupracující modul s
5162 \begin_inset space ~
5167 ISquare\SpecialChar \-
5170 může ukládat pomocná data
5175 Moduly implementující rozhraní mohou používat libovolný typ odvozený z
5176 \begin_inset space ~
5181 Range\SpecialChar \-
5184 , ale ostatním je viditelná pouze část definovaná v
5185 \begin_inset space ~
5191 \begin_layout Standard
5192 Kromě klasických metod pro ukládání a nahrávání nastavení a dalších dat
5193 je zde metoda pro získání seznamu ukazatelů na bloky, na které je
5197 rozdělen, a metoda pro zpracování celého
5202 Při jejím provádění je celý blok rozdělen na cílové bloky a pomocí volání
5203 metod modulů spolupracujících na úkolu je pro každý z
5204 \begin_inset space ~
5207 nich nalezeno optimální zobrazení.
5208 Tyto činnosti jsou spojeny proto, že schopnost nalézt dostatečně dobrá
5209 zobrazení typicky ovlivňuje jemnost rozdělení na cílové bloky.
5212 \begin_layout Subsubsection
5214 \begin_inset CommandInset label
5216 name "Implementace/MQuadTree"
5224 \begin_inset space \hfill{}
5234 \begin_layout Standard
5239 implementuje klasický čtyřstromový algoritmus s
5240 \begin_inset space ~
5243 několika drobnými rozšířeními.
5244 Je možné zvolit zda se má používat heuristické dělení a také nejmenší a
5245 největší povolenou velikost bloku.
5248 \begin_layout Paragraph
5252 \begin_layout Standard
5253 Původní algoritmus počítá pouze s
5254 \begin_inset space ~
5257 obrázky tvaru čtverce o
5258 \begin_inset space ~
5261 hraně mocniny 2, což by zde nebylo dostačující.
5262 Naštěstí stačí pracovat s
5263 \begin_inset space ~
5266 bloky stejným způsobem, jen v
5267 \begin_inset space ~
5270 některých případech jsou jejich skutečné rozměry menší, protože jsou
5271 \begin_inset Quotes gld
5275 \begin_inset Quotes grd
5279 Je pouze potřeba navíc ošetřit případy, kdy by při dělení na čtvrtiny vznikly
5283 \begin_layout Standard
5284 Dělení čtyřstromem se řídí jednoduchým principem.
5285 Na začátku je celý vstupní obrázek jeden cílový blok.
5286 Pak se rekurzivně pro každý blok zkouší nalézt dostatečně dobré zobrazení
5288 \begin_inset space ~
5291 případě neúspěchu je blok rozdělen na čtyři o
5292 \begin_inset space ~
5295 poloviční velikosti.
5296 Samozřejmě, bloky větší než nastavené maximum jsou rozděleny bez hledání
5298 \begin_inset space ~
5302 \begin_inset space ~
5305 velikosti nastaveného minima se modul vždy spokojí s
5306 \begin_inset space ~
5309 nejlepším nalezeným zobrazením.
5312 \begin_layout Paragraph
5316 \begin_layout Standard
5317 Byla zde jedna velká nevýhoda
5318 \begin_inset space ~
5321 --- původní algoritmus slepě zkoušel hledat zobrazení i pro bloky, pro které
5322 bylo zřejmé, že nemůže uspět.
5323 Proto zde může být dělení prováděno podle jednoduché heuristiky, která
5325 \begin_inset space ~
5329 \begin_inset space ~
5332 bloku) chybu optimálního zobrazení.
5333 Pokud pro nějaký blok bylo hledáno dostatečně dobré zobrazení, ale neúspěšně,
5334 je blok dále dělen původním algoritmem.
5335 Pokud byl nějaký blok naopak spekulativně rozdělen a všem jeho následníkům
5336 se podařilo najít optimální zobrazení, pak se zkusí hledat zobrazení i
5338 \begin_inset space ~
5341 případě úspěchu je zpětně sloučen (to může způsobit kaskádu slučování).
5345 \begin_layout Standard
5346 Heuristické dělení dává stejný výsledek za předpokladu (který platí téměř
5347 vždy), že pokud je možné nalézt dostatečně dobré zobrazení pro blok, pak
5348 je to možné i pro jeho čtvrtiny.
5350 \begin_inset space ~
5353 praxi představuje tato technika významné urychlení, přestože není heuristika
5354 moc přesná, například chyby bloků s
5355 \begin_inset space ~
5359 \begin_inset Quotes gld
5363 \begin_inset Quotes grd
5366 šumem jsou podhodnoceny a naopak chyby bloků s
5367 \begin_inset space ~
5370 jedním pozvolným nebo ostrým přechodem výrazně nadhodnoceny.
5371 Urychlení nastává zejména proto, že přeskočené hledání zobrazení pro velké
5372 bloky bývá časově velmi náročné, často kvůli nutnosti stavby složitých
5376 \begin_layout Standard
5377 Bylo by možné heuristiku ještě výrazně zpřesnit pomocí rozšíření rozhraní
5380 ISquare\SpecialChar \-
5384 \begin_inset space ~
5387 příslušnou odhadující metodu.
5388 Například implementace založené na mnohadimenzionálních prostorových datových
5389 strukturách by pak mohly odhadovat optimální chybu mnohem přesněji a také
5393 \begin_layout Paragraph
5397 \begin_layout Standard
5398 Efektivita uložení do proudu bytů je při kompresi obrazu velmi důležitá.
5399 Proto je nejprve uložena největší a nejmenší použitá
5403 (tedy ne nastavené limity) a potom při rekurzivním průchodu čtyřstromem
5404 je pro blok uložen jeden bit nastavený podle toho, zda blok byl nebo nebyl
5406 Bit se ukládá pouze pro bloky, kdy není možné informaci získat už z
5407 \begin_inset space ~
5410 uložené minimální a maximální
5417 \begin_layout Standard
5418 Cílové bloky jsou vraceny z
5419 \begin_inset space ~
5423 \begin_inset space ~
5426 pořadí jejich výskytu na Hilbertově křivce.
5427 Tím jsou sníženy vzájemné vzdálenosti po sobě jdoucích bloků a tedy i zefektivn
5428 ěny diferenční metody používané v
5429 \begin_inset space ~
5432 implementaci rozhraní
5434 ISquare\SpecialChar \-
5438 \begin_inset space ~
5442 \begin_inset CommandInset ref
5444 reference "Implementace/Zobrazování"
5451 \begin_layout Section
5452 Výběr množiny zdrojových bloků
5453 \begin_inset CommandInset label
5455 name "Implementace/Domény"
5462 \begin_layout Subsubsection
5466 \begin_layout Standard
5467 Vytváření rozhraní vybírajícího množinu zdrojových bloků bylo obtížné.
5468 Zdrojové bloky lze volit mnoha různými způsoby.
5469 Pokud by ale bylo rozhraní příliš obecné, mohla by se velmi výrazně snížit
5470 rychlost komprese a dekomprese.
5473 \begin_layout Standard
5474 Rozhraní poskytuje několik matic pro cílové bloky, jejichž obsah je už zmenšen
5475 tak, že zbytek zobrazení mezi zdrojovými a cílovými bloky nemění rozměry.
5476 Poskytované zdrojové bloky jsou vždy čtverce o
5477 \begin_inset space ~
5480 hranách délky mocniny 2, které jsou pravidelně rozmístěny po matici.
5481 Omezení velikostí zdrojových bloků ve skutečnosti neomezuje velikosti cílových
5482 bloků, protože modul pro zobrazování (s
5483 \begin_inset space ~
5488 ISquare\SpecialChar \-
5491 ) nemusí využít celý blok.
5493 \begin_inset space ~
5496 těchto matic a pro každou
5500 bloku je rozhraním poskytnut rozestup
5501 \begin_inset space ~
5505 \begin_inset space ~
5508 který jsou vzdáleny odpovídající rohy zdrojových bloků v
5509 \begin_inset space ~
5515 \begin_layout Standard
5516 Metody rozhraní umožňují inicializaci modulu pro daný
5520 , aktualizaci hodnot pixelů v
5521 \begin_inset space ~
5524 maticích pro zdrojové bloky (ze stavu
5528 ), vrácení seznamu těchto matic, ukládání a nahrávaní nastavení a dalších
5530 Také je zde metoda pro zjištění hustoty pokrytí zdrojovými bloky pro všechny
5531 matice, danou úroveň a daný maximální počet zdrojových bloků.
5534 \begin_layout Subsubsection
5539 \begin_inset space \hfill{}
5544 modules/stdDomains.*
5549 \begin_layout Standard
5554 implementuje rozhraní
5556 ISquare\SpecialChar \-
5559 a nabízí mnoho možností nastavení.
5562 \begin_layout Standard
5563 Předně lze regulovat maximální množství zdrojových bloků v
5564 \begin_inset space ~
5567 závislosti na jejich
5572 Původní maximum platí pro
5576 2, pro vyšší lze nastavit míru poklesu (koeficient geometrické řady).
5579 \begin_layout Paragraph
5580 Druhy zdrojových bloků
5583 \begin_layout Standard
5584 Třída umožňuje vytvářet několik druhů matic pro zdrojové bloky.
5585 Základní matice jsou čtyř druhů:
5602 Vzájemné poměry množství zdrojových bloků generovaných z
5603 \begin_inset space ~
5606 matic jednotlivých druhů může uživatel nastavit (přibližně).
5609 \begin_layout Standard
5614 matice vznikají zmenšením celého vstupu v
5615 \begin_inset space ~
5618 obou směrech na polovinu pomocí průměrování hodnot pixelů po čtveřicích.
5619 To je ve fraktální kompresi nejčastější metoda, protože je velmi jednoduchá,
5621 \begin_inset space ~
5624 praxi dobré výsledky.
5625 Další způsoby zmenšování jsou inspirovány především článkem
5626 \begin_inset space ~
5630 \begin_inset CommandInset citation
5636 , ale podobné návrhy lze najít i na mnoha jiných místech.
5639 \begin_layout Standard
5648 matice vznikají nerovnoměrným zmenšením celého vstupu v
5649 \begin_inset space ~
5653 \begin_inset space ~
5657 \begin_inset space ~
5660 jednom směru probíhá zmenšení na
5661 \begin_inset Formula $\nicefrac{1}{3}$
5665 \begin_inset space ~
5669 \begin_inset Formula $\nicefrac{2}{3}$
5676 \begin_layout Plain Layout
5677 Ve starší implementaci projektu probíhalo zmenšování pouze v
5678 \begin_inset space ~
5681 jednom směru, což těsně porušovalo podmínku kontraktivity z
5682 \begin_inset space ~
5686 \begin_inset CommandInset ref
5688 reference "PIFS/Rychlá_konvergence"
5693 Při okrajovém nastavení pak bylo snadno možné dosáhnout obrázku, kde některé
5694 bloky konvergovaly velmi pomalu a k
5695 \begin_inset space ~
5698 chybnému vodorovně nebo svisle
5699 \begin_inset Quotes gld
5703 \begin_inset Quotes grd
5711 Zmenšování probíhá výpočtem váženého průměru, kde jeden pixel vzniká ze
5712 tří celých a tří polovin pixelů, viz obrázek
5713 \begin_inset space ~
5717 \begin_inset CommandInset ref
5719 reference "Implementace/Domény/Náčrtek"
5726 \begin_layout Standard
5731 matice vznikají otáčením částí vstupu o
5732 \begin_inset space ~
5736 \begin_inset Formula $45^{\circ}$
5739 proti směru hodinových ručiček.
5740 Přes svůj název (odvozený z
5741 \begin_inset space ~
5749 \begin_inset space ~
5753 \begin_inset CommandInset citation
5760 \begin_inset space ~
5764 \begin_inset space ~
5767 tvaru pootočeného čtverce.
5768 Zde je použit jednoduchý způsob zmenšování
5769 \begin_inset space ~
5772 --- středy nových pixelů leží na některých rozích vstupních pixelů a jejich
5773 hodnota je spočtena jako průměr hodnot čtveřice vstupních pixelů sdílející
5775 Při čtvercovém vstupu se takto využije jen polovina jeho plochy a pokud
5776 by poměr stran byl větší, bylo by to ještě méně.
5777 Proto jsou takové vstupy pokryty více
5781 maticemi rozmístěnými tak, aby nevznikaly identické zdrojové bloky, viz
5783 \begin_inset space ~
5787 \begin_inset CommandInset ref
5789 reference "Implementace/Domény/Náčrtek"
5795 \begin_inset Float figure
5800 \begin_layout Plain Layout
5801 \begin_inset Caption
5803 \begin_layout Plain Layout
5804 \begin_inset CommandInset label
5806 name "Implementace/Domény/Náčrtek"
5810 Schéma zmenšování pro
5823 Tenké čáry značí původní pixely, čárkované značí jejich pokrytí pixely
5825 \begin_inset VSpace defskip
5834 \begin_inset Graphics
5835 filename dom_regular.eps
5841 \begin_inset space \hfill{}
5845 \begin_inset Graphics
5852 \begin_inset space \hfill{}
5856 \begin_inset Graphics
5857 filename dom_diamond.eps
5870 \begin_layout Paragraph
5871 Vícenásobné zmenšování
5874 \begin_layout Standard
5875 Ze základních matic lze ještě vytvářet další, ještě více zmenšené (a z
5876 \begin_inset space ~
5879 nich rekurzivně další).
5880 Použit je stejný algoritmus jako pro vytváření
5885 Lze navíc zvolit, jak velké množství zdrojových bloků bude z
5886 \begin_inset space ~
5889 těchto matic vytvořeno
5890 \begin_inset space ~
5893 --- buď stejné ze všech zmenšujících kroků (přestože ty více zmenšené mají
5894 menší plochu) nebo se bude s
5895 \begin_inset space ~
5898 každým krokem množství vytvořených bloků zmenšovat na polovinu nebo se vícenásob
5899 né zmenšování nepoužije.
5902 \begin_layout Standard
5903 Kvůli obecnosti návrhu rozhraní se i při dekompresi nezobrazují bloky rovnou,
5904 ale přes tyto matice, takže počet matic pro zdrojové bloky významně ovlivňuje
5905 rychlost dekomprese (na rozdíl od komprese, kde nehraje znatelnou roli).
5908 \begin_layout Section
5909 Hledání optimálních zobrazení
5910 \begin_inset CommandInset label
5912 name "Implementace/Zobrazování"
5919 \begin_layout Standard
5920 Hledání optimálních zobrazení je nejdůležitější část celého kompresního
5922 Zde se nejvíce ovlivňuje kvalita výsledku a také stráví nejvíce výpočetního
5926 \begin_layout Subsubsection
5930 \begin_layout Standard
5935 je rozhraní pro správu zobrazení mezi zdrojovými bloky generovanými modulem
5937 \begin_inset space ~
5942 ISquare\SpecialChar \-
5945 a cílovými bloky vytvářenými modulem s
5946 \begin_inset space ~
5951 ISquare\SpecialChar \-
5957 \begin_layout Standard
5958 Rozhraní obsahuje metody pro inicializaci před (de)kompresí
5962 , pro hledání optimálního zobrazení do daného cílového bloku, pro dokončení
5963 komprese a pro provádění dekódovacích akcí (vyčištění obrázku nebo iterování
5965 Dále jsou zde metody pro uložení a nahrání nastavení, pro zjištění počtu
5966 ukládacích fází a pro uložení nebo nahrání dat jednotlivých fází (význam
5968 \begin_inset space ~
5972 \begin_inset CommandInset ref
5974 reference "Implementace/IShapeTransformer"
5981 \begin_layout Subsubsection
5986 \begin_inset space \hfill{}
5991 modules/stdEncoder.*
5996 \begin_layout Standard
6001 implementuje rozhraní podle modelu upravených zobrazení popsaného v
6002 \begin_inset space ~
6006 \begin_inset space ~
6010 \begin_inset CommandInset ref
6012 reference "PIFS/Použitý_model"
6016 a využívá vzorců odvozených v
6017 \begin_inset space ~
6021 \begin_inset space ~
6025 \begin_inset CommandInset ref
6027 reference "Chyba_zobrazení"
6034 \begin_layout Standard
6035 Při hledání optimálního zdrojového bloku pro daný cílový blok (při kompresi)
6036 jsou nejprve předpočítány různé údaje z
6037 \begin_inset space ~
6041 \begin_inset space ~
6045 Pak je postupně pro všechny zdrojové bloky předané predikčním modulem s
6046 \begin_inset space ~
6056 (zvolen uživatelem, rozhraní popsáno v
6057 \begin_inset space ~
6061 \begin_inset CommandInset ref
6063 reference "Implementace/Predikce"
6067 ) počítána chyba zobrazení mezi dvojicí a je zapamatována nejlepší kombinace.
6068 Uživatel také může zvolit, zda bude zkoušeno osm způsobů otočení nebo jen
6069 identita, zda budou povoleny záporné lineární koeficienty, jak moc budou
6070 penalizovány vysoké lineární koeficienty (diskutováno v
6071 \begin_inset space ~
6075 \begin_inset CommandInset ref
6077 reference "Chyba_zobrazení/Penalizace"
6081 ), zda budou započítány chyby vzniklé kvantizací, jak bude omezena absolutní
6082 hodnota lineárních koeficientů, jak nízká dosažená chyba bude stačit pro
6083 okamžité ukončení hledání, jak jemná bude kvantizace průměrů a směrodatných
6084 odchylek a jaké moduly se budou starat o
6085 \begin_inset space ~
6088 ukládání kvantizovaných hodnot.
6091 \begin_layout Standard
6092 Moduly pro ukládání kvantizovaných průměrů a směrodatných odchylek cílových
6093 bloků splňují rozhraní
6099 \begin_inset space ~
6103 \begin_inset CommandInset ref
6105 reference "Implementace/Kódování_celočíselných_řad"
6109 ) a jsou zapojeny proto, že po sobě jdoucí hodnoty mají vysokou pravděpodobnost
6111 To zajištuje například modul
6113 MQuad\SpecialChar \-
6117 \begin_inset space ~
6121 \begin_inset CommandInset ref
6123 reference "Implementace/MQuadTree"
6127 ), který řadí bloky podle jejich pořadí na Hilbertově křivce, což výrazně
6128 zvyšuje lokalitu posloupnosti.
6129 Tyto vlastnosti ukládaných posloupností lze využít různými způsoby ke zvýšení
6130 efektivity jejich uložení, a proto je tato práce oddělena do jiných modulů.
6133 \begin_layout Standard
6134 Celá chyba lze pro všechny konfigurace snadno spočítat ze součtu hodnot
6135 ve zdrojovém bloku, součtu jejich druhých mocnin, z
6136 \begin_inset space ~
6139 předpočítaných údajů o
6140 \begin_inset space ~
6143 cílovém bloku a ze součtu součinů hodnot odpovídajících pixelů zdrojového
6145 Tento součet součinů je jediný potřebný údaj, který nelze získat v
6146 \begin_inset space ~
6150 Ostatní hodnoty jsou spočteny snadno, nejčastěji pomocí struktur zmíněných
6152 \begin_inset space ~
6156 \begin_inset space ~
6160 \begin_inset CommandInset ref
6162 reference "Implementace/Matice"
6169 \begin_layout Standard
6170 Uživatel má mnoho možností pro změnu způsobu výpočtu chyby mezi dvojicí
6172 Zjišťovat konfiguraci a vyhodnocovat mnoho podmínek při každém výpočtu
6173 chyby by způsobilo výrazné zpomalení.
6174 Proto jsou možnosti realizovány jako šablonové parametry funkce počítající
6175 chybu, která je instanciována pro každou kombinaci parametrů.
6176 Na začátku hledání optimálního zdrojového bloku pro cílový blok se podle
6177 konfigurace zjistí adresa příslušné funkce, která je pak vždy volána.
6179 \begin_inset space ~
6182 funkcí je tedy kompilátorem optimalizována zvlášť a již nevyhodnocuje žádné
6183 podmínky způsobené konfigurací.
6184 Velké množství instanciovaných funkcí zvyšuje kromě rychlosti také velikost
6185 binárního souboru, ale díky tomu, že funkce obsahují jen nejnutnější výpočty,
6186 je tento přínos pro celkovou velikost souboru nevýznamný.
6189 \begin_layout Standard
6190 Modul implementuje podporu pro progresivní dekódování založenou na ukládácích
6192 \begin_inset space ~
6196 \begin_inset space ~
6200 \begin_inset CommandInset ref
6202 reference "Implementace/IShapeTransformer"
6208 \begin_inset space ~
6211 první fázi jsou uloženy průměrné hodnoty všech bloků.
6212 Průměry zaberou málo místa, ale už z
6213 \begin_inset space ~
6216 nich samotných lze zrekonstruovat použitelný náhled výsledku.
6218 \begin_inset space ~
6221 druhé fázi jsou uloženy směrodatné odchylky bloků.
6223 \begin_inset space ~
6226 třetí, poslední, fázi je uložen zbytek potřebných informací pro cílové bloky
6228 \begin_inset space ~
6231 nenulovou směrodatnou odchylkou
6232 \begin_inset space ~
6235 --- vždy bit pro znaménko lineárního koeficientu a tři bity kódující otočení
6236 (jen pokud jsou potřeba) a index zdrojového bloku.
6239 \begin_layout Section
6240 Predikce vhodných zdrojových bloků
6241 \begin_inset CommandInset label
6243 name "Implementace/Predikce"
6250 \begin_layout Standard
6252 \begin_inset space ~
6256 \begin_inset space ~
6260 \begin_inset CommandInset ref
6262 reference "Implementace/Zobrazování"
6266 je řešen přesný výpočet vhodnosti zobrazení mezi dvojicí bloků, ale provádět
6267 ho pro každou možnost by bylo příliš zdlouhavé.
6268 Je tedy nutné umět rychle odhadnout, které zdrojové bloky (a v
6269 \begin_inset space ~
6272 jakých rotacích) je vhodné pro daný cílový blok zkoušet (možné přístupy
6274 \begin_inset space ~
6278 \begin_inset CommandInset ref
6280 reference "Články/Zrychlení"
6287 \begin_layout Subsubsection
6291 \begin_layout Standard
6293 \begin_inset space ~
6300 slouží jako generátor prediktorů vhodných zdrojových bloků pro modul
6306 Definuje strukturu, která obsahuje všechny potřebné informace o
6307 \begin_inset space ~
6310 daném cílovém bloku a nastavení komprese včetně mnoha předpočítaných údajů.
6313 \begin_layout Standard
6314 Po předání správně vyplněné instance této struktury do rozhraní je vytvořena
6316 \begin_inset space ~
6325 tor::IOne\SpecialChar \-
6326 Range\SpecialChar \-
6331 , která postupně vrací vhodné zdrojové bloky (pro tento účel jsou různé
6332 rotace bloku považovány za různé zdrojové bloky).
6333 Bloky nejsou vraceny po jednom, ale v
6334 \begin_inset space ~
6337 seznamech, aby se tak snížila režie spojená s
6338 \begin_inset space ~
6341 voláním virtuální metody.
6342 Je také předávána maximální akceptovaná čtvercová chyba, což ulehčuje prediktor
6343 u rozhodování, které bloky je bezpečné vynechat.
6346 \begin_layout Standard
6347 Dále je definována metoda volaná po skončení všech predikčních požadavků.
6349 \begin_inset space ~
6352 uvolnění potenciální paměti alokované pro urychlení predikcí.
6355 \begin_layout Subsubsection
6360 \begin_inset space \hfill{}
6365 modules/noPredictor.h
6370 \begin_layout Standard
6375 je zcela triviální implementací rozhraní, která nedělá žádnou predikci
6376 a vrací všechny možnosti.
6377 Slouží hlavně pro vyhodnocení účinnosti ostatních implementací.
6380 \begin_layout Subsubsection
6385 \begin_inset space \hfill{}
6390 modules/saupePredictor.*
6395 \begin_layout Standard
6400 je založen na větě publikované v
6401 \begin_inset space ~
6405 \begin_inset CommandInset citation
6413 \begin_inset space ~
6416 mírně upravené podobě, která je bližší značení z
6417 \begin_inset space ~
6421 \begin_inset space ~
6425 \begin_inset CommandInset ref
6432 \begin_inset space ~
6436 \begin_inset CommandInset ref
6438 reference "Chyba_zobrazení"
6445 \begin_layout Standard
6449 \begin_layout Plain Layout
6459 \begin_inset CommandInset label
6461 name "Implementace/Predikce/Věta"
6466 \begin_inset Formula $n\ge2$
6470 \begin_inset Formula $X=\mathbb{R}^{n}\setminus\left\{ r\cdot\left(1,1,\ldots,1\right)\left|r\in\mathbb{R}\right.\right\} $
6474 Definujme normalizační funkci
6475 \begin_inset Formula $\Phi:X\rightarrow X$
6479 \begin_inset Formula $D:X\times X\rightarrow\left\langle 0,\sqrt{2}\right\rangle $
6483 \begin_inset Formula \[
6484 \left(\Phi\left(x\right)\right)_{i}=\frac{x_{i}-\frac{1}{n}\sum_{j=1}^{n}x_{j}}{\sqrt{\frac{1}{n}\sum_{j=1}^{n}\left(x_{j}-\frac{1}{n}\sum_{k=1}^{n}x_{k}\right)^{2}}}\mbox{\; a}\]
6489 \begin_inset Formula \[
6490 D\left(r,d\right)=\min\left\{ \ \left\Vert \Phi(r)-\Phi(d)\right\Vert ,\ \left\Vert -\Phi(r)-\Phi(d)\right\Vert \ \right\} \mbox{,}\]
6495 \begin_inset Formula $\left\Vert .\right\Vert $
6498 značí eukleidovskou normu.
6501 \begin_layout Standard
6502 Pak pro nejmenší čtvercovou chybu definovanou
6503 \begin_inset Formula \[
6504 E\left(r,d\right)=\min_{p,q\in\mathbb{R}}\sum_{i=1}^{n}\left(p\, d_{i}+q-r_{i}\right)^{2}\mbox{\quad platí}\]
6509 \begin_inset Formula \[
6510 E\left(r,d\right)=\left(\sum_{i=1}^{n}\left(\Phi(r)\right)_{i}r_{i}\right)g\left(D(r,d)\right)\mbox{,\quad kde }g(x)=x^{2}\left(1-\frac{x^{2}}{4}\right).\]
6518 \begin_layout Plain Layout
6530 \begin_layout Standard
6532 \begin_inset Formula $\sum_{i=1}^{n}\left(\Phi(r)\right)_{i}r_{i}$
6535 pro daný cílový blok konstantní a funkce
6536 \begin_inset Formula $g(x)$
6539 je rostoucí na oboru hodnot funkce
6540 \begin_inset Formula $D(r,d)$
6543 , lze převést hledání optimálního zdrojového bloku na dvojici problémů hledání
6545 \begin_inset space ~
6551 \begin_layout Standard
6552 Pro každou velikost cílového bloku je tedy postavena datová struktura obsahující
6553 všechny možné zdrojové bloky normalizované funkcí
6554 \begin_inset Formula $\Phi$
6557 , konkrétně je použita varianta statického KD-stromu popsaná
6558 \begin_inset CommandInset ref
6559 LatexCommand vpageref
6560 reference "Implementace/KD-stromy"
6566 \begin_inset space ~
6569 danému bodu jsou vraceny prvky struktury v
6570 \begin_inset space ~
6573 pořadí podle dolních odhadů na jejich vzdálenost od tohoto bodu.
6574 Struktury jsou stavěny vždy až když je potřeba je prohledávat.
6576 \begin_inset space ~
6579 modulu a sdíleny všemi prediktory vracenými modulem (struktury jsou statické).
6582 \begin_layout Paragraph
6583 Omezení prohledávání
6586 \begin_layout Standard
6588 \begin_inset Formula $m$
6591 pro čtvercovou chybu, pak maximální přípustná čtvercová chyba v
6592 \begin_inset space ~
6595 normalizovaném prostoru je rovna
6596 \begin_inset Formula \[
6597 {\textstyle 2-2\sqrt{1-\frac{m}{\sum_{i=1}^{n}\left(\Phi(r)\right)_{i}r_{i}}}}\mbox{\quad(pokud existuje).}\]
6601 Tento limit sám nemusí dostatečně zkrátit prohledávání prostoru, protože
6602 téměř konstantní cílové bloky lze dobře aproximovat už konstantním blokem
6603 a aproximace nekonstantním blokem není nikdy horší.
6605 \begin_inset space ~
6608 takovém případě vyjde pod odmocninou záporné číslo.
6609 Proto má uživatel možnost v
6610 \begin_inset space ~
6613 modulu nastavit, jaká největší část zdrojových bloků může být predikována.
6616 \begin_layout Paragraph
6617 Vícenásobné prohledávání
6620 \begin_layout Standard
6622 \begin_inset space ~
6626 \begin_inset space ~
6630 \begin_inset CommandInset ref
6632 reference "Implementace/Predikce/Věta"
6636 je zřejmé, že je potřeba vždy pro dvojici bloků
6637 \begin_inset Formula $r^{i}$
6641 \begin_inset Formula $d^{j}$
6644 uvažovat dvě možnosti
6645 \begin_inset Formula $\left\Vert \Phi(r^{i})-\Phi(d^{j})\right\Vert $
6658 \begin_inset Formula $\left\Vert -\Phi(r^{i})-\Phi(d^{j})\right\Vert $
6661 (pokud jsou povolena zobrazení se zápornými lineárními koeficienty).
6662 Jedna možnost řešení je, že struktura obsahuje vždy
6663 \begin_inset Formula $\Phi(d^{j})$
6667 \begin_inset Formula $-\Phi(d^{j})$
6670 a je hledán nejbližší bod k
6671 \begin_inset space ~
6675 \begin_inset Formula $\Phi(r^{i})$
6680 \begin_inset space ~
6683 druhé možnosti obsahuje struktura pouze
6684 \begin_inset Formula $\Phi(d^{j})$
6688 \begin_inset space ~
6692 \begin_inset Formula $\Phi(r^{i})$
6696 \begin_inset Formula $-\Phi(r^{i})$
6700 Analogicky lze dvěma způsoby řešit uvažování osmi vzájemných rotací (pokud
6701 jsou povoleny uživatelem)
6702 \begin_inset space ~
6705 --- buď je struktura postavena z
6706 \begin_inset space ~
6709 osminásobného množství otočených bloků, nebo je nutné ji osminásobně prohledávat.
6710 Kvůli úspoře paměti byla zde v
6711 \begin_inset space ~
6714 obou případech zvolena varianta s
6715 \begin_inset space ~
6718 menší strukturou a násobným prohledáváním.
6721 \begin_layout Standard
6722 Vícenásobné prohledávání je realizováno tak, že jsou stavy všech prohledávání
6724 \begin_inset space ~
6727 haldě (použita je generická
6728 \begin_inset space ~
6731 STL implementace binární haldy) uspořádané podle příštího odhadu vzdálenosti
6732 ve struktuře a prohledává se tedy vždy ta varianta, která je nejblíže k
6733 \begin_inset space ~
6736 výchozímu bodu hledání (podle odhadu struktury).
6739 \begin_layout Paragraph
6743 \begin_layout Standard
6744 Pro účely predikce jsou bloky zmenšeny na velikost
6745 \begin_inset Formula $4\times4$
6749 \begin_inset space ~
6753 \begin_inset CommandInset citation
6760 Už ze zmenšenin lze vzájemnou zobrazitelnost dobře odhadnout
6761 \begin_inset space ~
6764 --- RMSE optimálního zobrazení mezi zmenšeninami je dolním odhadem na
6765 \begin_inset space ~
6768 RMSE optimálního zobrazení v
6769 \begin_inset space ~
6772 původním rozlišení a rovnost nastává, pokud v
6773 \begin_inset space ~
6776 rámci zprůměrovaných skupin pixelů byly
6777 \begin_inset Quotes gld
6780 stejné vzájemné odchylky
6781 \begin_inset Quotes grd
6784 ve zdrojovém i cílovém bloku.
6785 Díky spojitému charakteru běžných obrázků bývá tento odhad dostatečně blízko,
6786 takže už podle něj lze většinu kandidátů bezpečně vyřadit (protože odhad
6787 překročí maximální povolenou chybu).
6790 \begin_layout Standard
6792 \begin_inset space ~
6795 velkými zdrojovými bloky by přinášela řadu problémů.
6797 \begin_inset space ~
6800 důvodů je, že efektivita KD-stromů klesá s
6801 \begin_inset space ~
6804 růstem počtu souřadnic.
6805 Dalším důvodem je paměťová náročnost.
6806 Pokud bychom pro účel stavby stromu uložili obrazy funkce
6807 \begin_inset Formula $\Phi$
6810 , potřebujeme už při velikosti
6811 \begin_inset Formula $16\times16$
6815 \begin_inset space \thinspace{}
6819 Počty zdrojových bloků se běžně pohybují v
6820 \begin_inset space ~
6823 řádu stovek tisíc, což dává neúnosnou spotřebu stovek megabytů paměti.
6824 Alternativně by bylo možné uchovávat v
6825 \begin_inset space ~
6828 paměti pouze koeficienty funkce
6829 \begin_inset Formula $\Phi$
6832 (pro pevný blok je to afinní funkce) a počítat hodnotu na
6833 \begin_inset space ~
6836 každé souřadnici normalizovaného bloku z
6837 \begin_inset space ~
6840 původního obrázku jednotlivě při každém přístupu.
6842 \begin_inset space ~
6845 mnohonásobnému zpomalení.
6848 \begin_layout Standard
6849 Pro predikci by bylo možné použít i jiné způsoby snižování počtu dimenzí,
6850 například výběr několika nejdůležitějších koeficientů dvourozměrné diskrétní
6851 kosinové transformace bloku
6852 \begin_inset space ~
6856 \begin_inset space ~
6859 použití transformace ve standardu JPEG je zřejmé, že je to velmi dobrý způsob
6860 aproximace obrázku malým množstvím souřadnic.
6863 \begin_layout Subsubsection
6865 \begin_inset CommandInset label
6867 name "Implementace/KD-stromy"
6875 \begin_inset space \hfill{}
6885 \begin_layout Standard
6886 KD-strom je binární strom, který rekurzivně dělí spravovaný prostor v
6887 \begin_inset space ~
6891 dém svém vrcholu podle hodnoty jedné ze souřadnic.
6892 Tato struktura byla zvolena především pro svou jednoduchost a možnost paměťově
6893 úsporné implementace.
6896 \begin_layout Paragraph
6900 \begin_layout Standard
6901 Protože je strom statický a binární, lze jeho tvar volit stejně jako pro
6902 binární haldy a ukládat jeho vrcholy v
6903 \begin_inset space ~
6907 Je zvolena varianta, kde jsou všechny obsažené body až v
6908 \begin_inset space ~
6912 Pro každý vnitřní vrchol pak stačí uložit jen souřadnici, podle které je
6913 dělen podprostor vrcholu, a hodnotu, na které je hranice dělení.
6914 Pro listy je pak uložen jen index bodu, kterému odpovídá.
6917 \begin_layout Standard
6919 \begin_inset space ~
6923 \begin_inset space ~
6926 KD-stromech by byly uchovány také souřadnice všech obsažených bodů.
6927 Ty by ale ovlivnily prohledávání až po dělení vrcholů nad listy, kdy už
6928 je dolní odhad vzdálenosti blízko skutečnosti.
6929 Zde navíc není nutné znát vzdálenosti přesně
6930 \begin_inset space ~
6933 --- většinou se pracuje se zmenšeninami a přesné porovnání je stejně poté
6934 provedeno jiným modulem.
6935 Souřadnice všech bodů také zabírají mnoho místa, takže bylo zvoleno, že
6936 budou využity pouze pro postavení stromu a pak zahozeny.
6937 Tato volba pravděpodobně zhorší výkon struktury, ale alternativa zde není
6938 implementována, takže míra jejího vlivu není známa (je to možnost rozšíření
6940 \begin_inset space ~
6946 \begin_layout Standard
6947 Části prostoru patřící jednotlivým vrcholům jsou definovány rekurzivně.
6948 Kořen reprezentuje hyperkvádr uložený ve stromě, který těsně obaluje všechny
6949 body ve struktuře (minima a maxima všech bodů v
6950 \begin_inset space ~
6953 každé ze souřadnic ve struktuře).
6954 Synové každého vrcholu si rozdělí jeho hyperkvádr podle nadroviny kolmé
6955 na jednu ze souřadnic (souřadnice a mezní hodnota je ve vrcholu uložena).
6957 \begin_inset space ~
6960 této implementaci patří body ležící na mezní nadrovině do obou podstromů,
6961 aby bylo možné vždy volit libovolné velikosti podstromů a dosáhnout tak
6962 tvaru odpovídajícímu binární haldě.
6965 \begin_layout Paragraph
6969 \begin_layout Standard
6970 Hledání nejbližších bodů staví postupu typickém pro všechny podobné struktury.
6971 Je udržována halda z
6972 \begin_inset space ~
6975 vrcholů stromu uspořádaná podle vzdáleností podprostorů vrcholů stromu od
6976 výchozího bodu (toho, k
6977 \begin_inset space ~
6980 němuž hledáme nejbližší body).
6982 \begin_inset space ~
6985 haldě jen kořen a pak se vždy odebere z
6986 \begin_inset space ~
6989 haldy minimum a vloží se do ní synové obsaženého vrcholu stromu.
6991 \begin_inset space ~
6994 minimu haldy list stromu, je pouze poslán na výstup jako další z
6995 \begin_inset space ~
7001 \begin_layout Standard
7003 \begin_inset space ~
7006 haldou efektivní, jsou v
7007 \begin_inset space ~
7010 každém prvku kromě čísla vrcholu stromu uloženy souřadnice bodu z
7011 \begin_inset space ~
7014 části prostoru patřící vrcholu, který je nejblíže výchozímu bodu, a také
7015 druhá mocnina jeho eukleidovské vzdálenosti od výchozího bodu (podle ní
7016 je halda uspořádaná).
7017 Umocnění vzdálenosti nepokazí uspořádání, protože je to pro nezáporná čísla
7018 rostoucí funkce, a významně zjednoduší výpočty.
7019 Tyto údaje lze při dělení na syny velmi snadno přepočítat, protože nejbližší
7020 bod se může změnit jen v
7021 \begin_inset space ~
7024 jedné souřadnici a druhá mocnina jeho vzdálenosti se tedy změní jen o
7025 \begin_inset space ~
7028 rozdíl druhých mocnin rozdílů hodnoty výchozího bodu v
7029 \begin_inset space ~
7032 té souřadnici od nové a původní hodnoty nejbližšího bodu.
7035 \begin_layout Standard
7036 Při prohledávání lze navíc nastavit, že souřadnice výchozího bodu, které
7037 obsahují speciální hodnotu NaN (
7041 ), budou ignorovány.
7044 MSaupe\SpecialChar \-
7049 využito pro lepší predikci pro ořízlé cílové bloky, které jsou menší, protože
7050 leží na okraji obrázku.
7053 \begin_layout Paragraph
7057 \begin_layout Standard
7058 Strom je stavěn rekurzivně
7059 \begin_inset space ~
7062 --- při stavbě vrcholu
7063 \begin_inset Formula $v$
7067 \begin_inset Formula $b$
7071 \begin_inset space ~
7075 \begin_inset Formula $p$
7078 obsahujícím indexy bodů, které mají být reprezentovány podstromem vrcholu
7079 \begin_inset space ~
7083 \begin_inset Formula $v$
7087 Nejprve je určeno, jaké počty bodů budou patřit synům vrcholu
7088 \begin_inset Formula $v$
7093 \begin_inset Quotes gld
7097 \begin_inset Quotes grd
7100 je určen jednoznačně počtem listů, který zde odpovídá počtu bodů ve struktuře,
7101 a navíc se tento tvar dědí
7102 \begin_inset space ~
7105 --- pokud má podstrom nějakého vrcholu tvar haldy, pak ho mají i podstromy
7106 jeho synů a tedy i všechny ostatní podstromy.
7109 \begin_layout Standard
7110 Pak je určena souřadnice
7111 \begin_inset Formula $i$
7114 , podle které bude část prostoru patřící
7115 \begin_inset Formula $v$
7118 dělena (metody rozebrány níže).
7119 Podle ní se obsah pole
7120 \begin_inset Formula $p$
7124 \begin_inset space ~
7128 \begin_inset Formula $b$
7131 rozdělí na dvě části tak, aby jejich velikosti odpovídaly počtům bodů,
7132 které budou patřit synům, a aby žádný bod levého syna neměl v
7133 \begin_inset space ~
7137 \begin_inset Formula $i$
7140 -té souřadnici hodnotu větší než nějaký bod pravého syna.
7141 To je provedeno pomocí generického algoritmu
7143 nth_ele\SpecialChar \-
7147 \begin_inset space ~
7150 STL, který najde k-tý nejmenší prvek a přeuspořádá ostatní prvky korektně
7152 \begin_inset space ~
7156 Pak se uloží hodnota souřadnice
7157 \begin_inset Formula $i$
7160 na vzniklé hranici do vrcholu
7161 \begin_inset Formula $v$
7164 a rekurzivně se zkonstruují jeho synové (pokud na ně zbývá více než jeden
7168 \begin_layout Standard
7169 Při stavbě je možno zvolit jeden z
7170 \begin_inset space ~
7173 několika implementovaných způsobů volby souřadnice
7174 \begin_inset Formula $i$
7178 Jsou zde dva triviální algoritmy
7179 \begin_inset space ~
7182 --- jeden cyklicky střídá souřadnice podle houbky a druhý je volí náhodně.
7185 MSaupe\SpecialChar \-
7190 používá lepší algoritmus, který volí tu souřadnici, ve které má část prostoru
7192 \begin_inset Formula $v$
7198 \begin_layout Paragraph
7199 Korespondence se zdrojovým kódem
7202 \begin_layout Standard
7203 Struktura stromu je reprezentována generickou třídou
7208 Prohledávání provádí její podtřída
7210 Point\SpecialChar \-
7213 , která při konstrukci požaduje zadání výchozího bodu, instance prohledávaného
7214 stromu a volbu zda se mají ignorovat některé souřadnice.
7215 Pak na požadavek vrací indexy jednotlivých bodů nebo momentální odhad vzdálenos
7216 ti od výchozího bodu.
7219 \begin_layout Standard
7220 Vytváření stromu provádí statická (ve smyslu objektové terminologie) metoda
7230 Ta umožňuje také zvolit jednu z
7231 \begin_inset space ~
7238 , která bude použita pro volbu souřadnice
7239 \begin_inset Formula $i$
7245 \begin_layout Section
7246 Kódování celočíselných řad
7247 \begin_inset CommandInset label
7249 name "Implementace/Kódování_celočíselných_řad"
7256 \begin_layout Subsubsection
7260 \begin_layout Standard
7265 je rozhraní pro kódování posloupností celých čísel z
7266 \begin_inset space ~
7270 \begin_inset Formula $\{0,1,\ldots,n-1\}$
7275 \begin_inset space ~
7278 této práci je využito modulem
7283 pro ukládání průměrných barev a směrodatných odchylek cílových bloků.
7286 \begin_layout Standard
7288 \begin_inset space ~
7291 něm poskytnuty metody pro nastavení počtu možností
7292 \begin_inset Formula $n$
7295 , pro uložení seznamu čísel do proudu bytů a pro zpětné zrekonstruování
7296 seznamu dané délky z
7297 \begin_inset space ~
7301 Dále jsou zde metody pro uložení a nahrání nastavení modulu.
7304 \begin_layout Subsubsection
7305 MDifferentialVLICodec
7309 \begin_inset space \hfill{}
7319 \begin_layout Standard
7322 MDifferentialVLICodec
7324 je kodek určený pro efektivní ukládání posloupností čísel, kde mají po
7326 \begin_inset space ~
7329 vysokou pravděpodobností blízké hodnoty.
7330 Místo samotných prvků posloupnosti se uvažuje vždy rozdíl hodnoty od předchozíh
7332 \begin_inset space ~
7336 \begin_inset Formula $\{-\left\lceil \frac{n}{2}\right\rceil ,\ldots,\left\lfloor \frac{n}{2}\right\rfloor \}$
7340 \begin_inset Formula $n$
7344 Tyto rozdíly jsou pak jednotlivě kódovány pomocnou třídou
7351 \begin_layout Standard
7356 provádí kódování tak, že pro čísla blízká nule použije menší množství bitů.
7357 Nejprve převede všechna čísla do rozsahu
7358 \begin_inset Formula $\{0,1,\ldots,n-1\}$
7362 \begin_inset Formula \[
7365 -2x-1 & (x<0)\end{cases}.\]
7369 Pak je celý interval rozdělen na několik částí kódovaných různými počty
7371 Délka první části je nastavena uživatelem (je to mocnina čísla
7372 \begin_inset Formula $2$
7375 ) a každá další část má dvojnásobnou délku, dokud se nevyčerpají všechna
7377 \begin_inset space ~
7381 Každé číslo je pak reprezentováno několika bity udávajícími do jaké části
7382 patří a pak dalším blokem bitů (jejich počet závisí na velikosti dané části),
7383 které udávají pozici v
7384 \begin_inset space ~
7390 \begin_layout Chapter
7391 Testování a vyhodnocení
7392 \begin_inset CommandInset label
7394 name "Testování_a_vyhodnocení"
7401 \begin_layout Standard
7403 \begin_inset space ~
7406 této kapitole budou ukázány výsledky testování komprese na vybraných černobílých
7410 \begin_layout Standard
7411 Testy jsou omezeny pouze na odstíny šedi kvůli jednoduššímu vyhodnocování.
7412 Publikované výsledky se většinou také zabývají pouze černobílými obrázky
7413 a navíc by bylo obtížné sladit míru komprese všech barevných složek na
7414 podobnou úroveň, aby bylo možné výsledky rozumně porovnat.
7417 \begin_layout Standard
7418 Použito je celkem šest testovacích obrázků získaných z
7419 \begin_inset space ~
7422 různorodé kolekce jedné výzkumné skupiny univerzity ve Waterloo
7423 \begin_inset space ~
7427 \begin_inset CommandInset citation
7450 jsou ve fraktální kompresi často používané a mají klasické rozměry
7451 \begin_inset Formula $512\times512$
7464 \begin_inset space ~
7467 --- nejsou to fotografie (spíše se dají popsat spojením
7468 \begin_inset Quotes gld
7472 \begin_inset Quotes grd
7475 ) a mají i neobvyklé rozměry.
7478 \begin_layout Standard
7479 \begin_inset Float figure
7484 \begin_layout Plain Layout
7485 \begin_inset Caption
7487 \begin_layout Plain Layout
7488 \begin_inset CommandInset label
7490 name "Testování/Lena_a_Mandrill"
7503 \begin_inset Formula $512\times512$
7512 \begin_inset VSpace defskip
7518 \begin_layout Plain Layout
7519 \begin_inset Graphics
7527 \begin_inset space \hfill{}
7531 \begin_inset Graphics
7532 filename mandrill.png
7546 \begin_layout Standard
7547 \begin_inset Float figure
7552 \begin_layout Plain Layout
7553 \begin_inset Caption
7555 \begin_layout Plain Layout
7556 \begin_inset CommandInset label
7558 name "Testování/Peppers_a_Goldhill"
7571 \begin_inset Formula $512\times512$
7580 \begin_inset VSpace defskip
7586 \begin_layout Plain Layout
7587 \begin_inset Graphics
7588 filename peppers.png
7595 \begin_inset space \hfill{}
7599 \begin_inset Graphics
7600 filename goldhill.png
7614 \begin_layout Standard
7615 \begin_inset Float figure
7620 \begin_layout Plain Layout
7621 \begin_inset Caption
7623 \begin_layout Plain Layout
7624 \begin_inset CommandInset label
7626 name "Testování/Serrano"
7635 \begin_inset Formula $629\times794$
7644 \begin_inset VSpace defskip
7650 \begin_layout Plain Layout
7651 \begin_inset space \hfill{}
7655 \begin_inset Graphics
7656 filename serrano.png
7663 \begin_inset space \hfill{}
7674 \begin_layout Standard
7675 \begin_inset Float figure
7680 \begin_layout Plain Layout
7681 \begin_inset Caption
7683 \begin_layout Plain Layout
7684 \begin_inset CommandInset label
7686 name "Testování/Clegg"
7695 \begin_inset Formula $814\times880$
7704 \begin_inset VSpace defskip
7708 \begin_inset space \hfill{}
7712 \begin_inset Graphics
7720 \begin_inset space \hfill{}
7731 \begin_layout Standard
7732 Ke kompresi pomocí standardů JPEG a JPEG
7733 \begin_inset space ~
7736 2000 byly použity utility projektu
7741 \begin_inset space ~
7745 \begin_inset CommandInset citation
7752 Všechny uvedené doby fraktální komprese, hodnoty PSNR a kompresní poměry
7753 byly naměřeny samotným programem.
7757 \begin_layout Plain Layout
7758 Kompresním poměrem se zde rozumí poměr nekomprimované velikosti ke komprimované,
7760 \begin_inset Quotes gld
7763 nekomprimovaného obrázku
7764 \begin_inset Quotes grd
7768 \begin_inset space ~
7771 bytech je dána jako počet jeho pixelů (obrázky jsou černobílé).
7776 Doby fraktální i standardní komprese byly získány jednovláknovým spouštěním
7778 \begin_inset space ~
7781 dávkovém režimu (bez GUI) na počítači s
7782 \begin_inset space ~
7786 \begin_inset space ~
7790 \begin_inset space \thinspace{}
7793 GHz, systémem Gentoo Linux a kompilátorem GCC verze 4.2.1.
7796 \begin_layout Standard
7797 Následují tři skupiny testů zaměřené na vyhodnocení konkrétních částí komprese
7798 a jedna zkoumající celkový výsledek.
7799 Parametry modulů, které nejsou uvedeny, jsou vždy nechávány na přednastavených
7803 \begin_layout Section
7807 \begin_layout Standard
7809 \begin_inset space ~
7813 \begin_inset space ~
7817 \begin_inset CommandInset ref
7819 reference "Chyba_zobrazení/Penalizace"
7823 byla navržena alternativa k
7824 \begin_inset space ~
7827 omezení absolutní hodnoty lineárních koficientů barevných zobrazení mezi
7828 bloky a bylo zdůvodněno, proč by to mělo být výhodnější.
7829 Zde bude porovnán vliv penalizace a omezení koeficientů na kvalitu a kompresní
7831 Aby bylo hodnocení vlivu objektivnější, je pro predikci zvolen modul
7838 a je zrušen limit pro předčasné ukončení hledání, tedy jsou vždy zkoušeny
7839 všechny zdrojové bloky.
7842 \begin_layout Standard
7843 Výsledky testů jsou v
7844 \begin_inset space ~
7848 \begin_inset space ~
7852 \begin_inset CommandInset ref
7854 reference "Testování/Penalizace/Tabulka"
7859 Pro šest obrázků a několik nastavení míry penalizace nebo omezení koeficientů
7860 je změřen kompresní poměr a hodnota PSNR.
7861 Absolutní hodnoty lineárních koeficientů barevných zobrazení jsou omezovány
7863 \begin_inset space ~
7873 ) tak, že kombinace bloků, kde by byla hodnota příliš vysoká, nejsou uvažovány.
7876 \begin_layout Standard
7877 Výrazně nejhorší výsledky vyšly pro nastavení, kde není použita ani jedna
7879 \begin_inset space ~
7883 Omezení koeficientů pod
7884 \begin_inset Formula $1.0$
7887 nutné pro zaručení konvergence dekódování sice dává dobré výsledky pro
7897 \begin_inset space ~
7900 ostatních případech je kvalita hluboko pod nejlepším výsledkem.
7901 Proto je často omezení uvolněno a jsou dovoleny i hodnoty vyšší (zkoumáno
7903 \begin_inset space ~
7907 \begin_inset space ~
7911 \begin_inset space ~
7915 \begin_inset CommandInset citation
7923 \begin_inset space ~
7926 výraznému zlepšení a kvalita většiny obrázků se přiblíží k
7927 \begin_inset space ~
7930 nejlepším hodnotám dosaženým v
7931 \begin_inset space ~
7936 \begin_inset space ~
7943 je PSNR stále více než
7944 \begin_inset Formula $0.9$
7948 \begin_inset space \thinspace{}
7954 \begin_layout Standard
7955 Při použití penalizace místo omezení lineárních koeficientů vycházejí nepatrně
7956 nižší kopresní poměry, ale kvalita se pohybuje blízko nejvyšší hodnoty
7958 \begin_inset space ~
7961 všech testovaných obrázků.
7963 \begin_inset space ~
7966 implicitním nastavení proto nejsou omezeny lineární koeficenty zobrazení
7967 mezi bloky a je použita penalizace s
7968 \begin_inset space ~
7972 \begin_inset Formula $0.25$
7975 (kompromis mezi kvalitou a kompresním poměrem).
7978 \begin_layout Standard
7979 \begin_inset Float table
7984 \begin_layout Plain Layout
7985 \begin_inset Caption
7987 \begin_layout Plain Layout
7988 \begin_inset CommandInset label
7990 name "Testování/Penalizace/Tabulka"
7994 Testování účinností penalizace a omezení koeficientů
8002 \begin_inset VSpace defskip
8008 \begin_layout Plain Layout
8011 \begin_inset Tabular
8012 <lyxtabular version="3" rows="32" columns="5">
8014 <column alignment="center" valignment="top" width="0">
8015 <column alignment="center" valignment="top" width="0">
8016 <column alignment="center" valignment="top" width="0">
8017 <column alignment="center" valignment="top" width="0">
8018 <column alignment="center" valignment="top" width="0">
8020 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8023 \begin_layout Plain Layout
8029 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8032 \begin_layout Plain Layout
8040 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8043 \begin_layout Plain Layout
8051 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8054 \begin_layout Plain Layout
8062 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
8065 \begin_layout Plain Layout
8075 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
8078 \begin_layout Plain Layout
8086 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
8089 \begin_layout Plain Layout
8097 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
8100 \begin_layout Plain Layout
8108 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
8111 \begin_layout Plain Layout
8119 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
8122 \begin_layout Plain Layout
8132 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8135 \begin_layout Plain Layout
8143 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8146 \begin_layout Plain Layout
8154 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8157 \begin_layout Plain Layout
8165 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8168 \begin_layout Plain Layout
8176 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
8179 \begin_layout Plain Layout
8189 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8192 \begin_layout Plain Layout
8198 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8201 \begin_layout Plain Layout
8209 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8212 \begin_layout Plain Layout
8220 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8223 \begin_layout Plain Layout
8231 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8234 \begin_layout Plain Layout
8245 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8248 \begin_layout Plain Layout
8254 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8257 \begin_layout Plain Layout
8265 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8268 \begin_layout Plain Layout
8276 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8279 \begin_layout Plain Layout
8287 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8290 \begin_layout Plain Layout
8301 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8304 \begin_layout Plain Layout
8310 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8313 \begin_layout Plain Layout
8321 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8324 \begin_layout Plain Layout
8332 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8335 \begin_layout Plain Layout
8343 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8346 \begin_layout Plain Layout
8357 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8360 \begin_layout Plain Layout
8366 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8369 \begin_layout Plain Layout
8377 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8380 \begin_layout Plain Layout
8388 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8391 \begin_layout Plain Layout
8399 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8402 \begin_layout Plain Layout
8412 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8415 \begin_layout Plain Layout
8421 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8424 \begin_layout Plain Layout
8432 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8435 \begin_layout Plain Layout
8443 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8446 \begin_layout Plain Layout
8454 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8457 \begin_layout Plain Layout
8467 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8470 \begin_layout Plain Layout
8476 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8479 \begin_layout Plain Layout
8487 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8490 \begin_layout Plain Layout
8498 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8501 \begin_layout Plain Layout
8509 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8512 \begin_layout Plain Layout
8522 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8525 \begin_layout Plain Layout
8531 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8534 \begin_layout Plain Layout
8542 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8545 \begin_layout Plain Layout
8553 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8556 \begin_layout Plain Layout
8564 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8567 \begin_layout Plain Layout
8577 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8580 \begin_layout Plain Layout
8586 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8589 \begin_layout Plain Layout
8597 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8600 \begin_layout Plain Layout
8608 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8611 \begin_layout Plain Layout
8619 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8622 \begin_layout Plain Layout
8632 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8635 \begin_layout Plain Layout
8641 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8644 \begin_layout Plain Layout
8652 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8655 \begin_layout Plain Layout
8663 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8666 \begin_layout Plain Layout
8674 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8677 \begin_layout Plain Layout
8687 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8690 \begin_layout Plain Layout
8698 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8701 \begin_layout Plain Layout
8709 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8712 \begin_layout Plain Layout
8720 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8723 \begin_layout Plain Layout
8731 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
8734 \begin_layout Plain Layout
8744 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8747 \begin_layout Plain Layout
8753 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8756 \begin_layout Plain Layout
8764 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8767 \begin_layout Plain Layout
8775 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8778 \begin_layout Plain Layout
8786 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8789 \begin_layout Plain Layout
8799 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8802 \begin_layout Plain Layout
8808 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8811 \begin_layout Plain Layout
8819 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8822 \begin_layout Plain Layout
8830 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8833 \begin_layout Plain Layout
8841 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8844 \begin_layout Plain Layout
8854 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8857 \begin_layout Plain Layout
8863 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8866 \begin_layout Plain Layout
8874 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8877 \begin_layout Plain Layout
8885 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8888 \begin_layout Plain Layout
8896 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8899 \begin_layout Plain Layout
8910 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8913 \begin_layout Plain Layout
8919 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8922 \begin_layout Plain Layout
8930 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8933 \begin_layout Plain Layout
8941 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8944 \begin_layout Plain Layout
8952 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8955 \begin_layout Plain Layout
8966 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8969 \begin_layout Plain Layout
8975 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8978 \begin_layout Plain Layout
8986 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8989 \begin_layout Plain Layout
8997 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9000 \begin_layout Plain Layout
9008 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9011 \begin_layout Plain Layout
9021 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9024 \begin_layout Plain Layout
9030 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9033 \begin_layout Plain Layout
9041 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9044 \begin_layout Plain Layout
9052 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9055 \begin_layout Plain Layout
9063 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9066 \begin_layout Plain Layout
9076 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9079 \begin_layout Plain Layout
9085 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9088 \begin_layout Plain Layout
9096 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9099 \begin_layout Plain Layout
9107 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9110 \begin_layout Plain Layout
9118 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9121 \begin_layout Plain Layout
9131 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9134 \begin_layout Plain Layout
9140 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9143 \begin_layout Plain Layout
9151 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9154 \begin_layout Plain Layout
9162 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9165 \begin_layout Plain Layout
9173 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9176 \begin_layout Plain Layout
9186 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9189 \begin_layout Plain Layout
9195 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9198 \begin_layout Plain Layout
9206 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9209 \begin_layout Plain Layout
9217 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9220 \begin_layout Plain Layout
9228 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
9231 \begin_layout Plain Layout
9241 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9244 \begin_layout Plain Layout
9252 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9255 \begin_layout Plain Layout
9263 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9266 \begin_layout Plain Layout
9274 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9277 \begin_layout Plain Layout
9285 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9288 \begin_layout Plain Layout
9298 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9301 \begin_layout Plain Layout
9307 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9310 \begin_layout Plain Layout
9318 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9321 \begin_layout Plain Layout
9329 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9332 \begin_layout Plain Layout
9340 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9343 \begin_layout Plain Layout
9353 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9356 \begin_layout Plain Layout
9362 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9365 \begin_layout Plain Layout
9373 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9376 \begin_layout Plain Layout
9384 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9387 \begin_layout Plain Layout
9395 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9398 \begin_layout Plain Layout
9408 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9411 \begin_layout Plain Layout
9417 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9420 \begin_layout Plain Layout
9428 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9431 \begin_layout Plain Layout
9439 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9442 \begin_layout Plain Layout
9450 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9453 \begin_layout Plain Layout
9464 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9467 \begin_layout Plain Layout
9473 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9476 \begin_layout Plain Layout
9484 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9487 \begin_layout Plain Layout
9495 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9498 \begin_layout Plain Layout
9506 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9509 \begin_layout Plain Layout
9520 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9523 \begin_layout Plain Layout
9529 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9532 \begin_layout Plain Layout
9540 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9543 \begin_layout Plain Layout
9551 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9554 \begin_layout Plain Layout
9562 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9565 \begin_layout Plain Layout
9576 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9579 \begin_layout Plain Layout
9585 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9588 \begin_layout Plain Layout
9596 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9599 \begin_layout Plain Layout
9607 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9610 \begin_layout Plain Layout
9618 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9621 \begin_layout Plain Layout
9631 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9634 \begin_layout Plain Layout
9640 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9643 \begin_layout Plain Layout
9651 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9654 \begin_layout Plain Layout
9662 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9665 \begin_layout Plain Layout
9673 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9676 \begin_layout Plain Layout
9686 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9689 \begin_layout Plain Layout
9695 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9698 \begin_layout Plain Layout
9706 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9709 \begin_layout Plain Layout
9717 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9720 \begin_layout Plain Layout
9728 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9731 \begin_layout Plain Layout
9741 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9744 \begin_layout Plain Layout
9750 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9753 \begin_layout Plain Layout
9761 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9764 \begin_layout Plain Layout
9772 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9775 \begin_layout Plain Layout
9783 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
9786 \begin_layout Plain Layout
9800 \begin_inset space \hfill{}
9804 \begin_inset Tabular
9805 <lyxtabular version="3" rows="32" columns="5">
9807 <column alignment="center" valignment="top" width="0">
9808 <column alignment="center" valignment="top" width="0">
9809 <column alignment="center" valignment="top" width="0">
9810 <column alignment="center" valignment="top" width="0">
9811 <column alignment="center" valignment="top" width="0">
9813 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9816 \begin_layout Plain Layout
9822 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9825 \begin_layout Plain Layout
9833 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9836 \begin_layout Plain Layout
9844 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9847 \begin_layout Plain Layout
9855 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
9858 \begin_layout Plain Layout
9868 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9871 \begin_layout Plain Layout
9879 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9882 \begin_layout Plain Layout
9890 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9893 \begin_layout Plain Layout
9901 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9904 \begin_layout Plain Layout
9912 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
9915 \begin_layout Plain Layout
9925 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9928 \begin_layout Plain Layout
9936 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9939 \begin_layout Plain Layout
9947 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9950 \begin_layout Plain Layout
9958 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9961 \begin_layout Plain Layout
9969 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
9972 \begin_layout Plain Layout
9982 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9985 \begin_layout Plain Layout
9991 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9994 \begin_layout Plain Layout
10002 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10005 \begin_layout Plain Layout
10013 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10016 \begin_layout Plain Layout
10024 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10027 \begin_layout Plain Layout
10037 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10040 \begin_layout Plain Layout
10046 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10049 \begin_layout Plain Layout
10057 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10060 \begin_layout Plain Layout
10068 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10071 \begin_layout Plain Layout
10079 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10082 \begin_layout Plain Layout
10093 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10096 \begin_layout Plain Layout
10102 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10105 \begin_layout Plain Layout
10113 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10116 \begin_layout Plain Layout
10124 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10127 \begin_layout Plain Layout
10135 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10138 \begin_layout Plain Layout
10149 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10152 \begin_layout Plain Layout
10158 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10161 \begin_layout Plain Layout
10169 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10172 \begin_layout Plain Layout
10180 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10183 \begin_layout Plain Layout
10191 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10194 \begin_layout Plain Layout
10205 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10208 \begin_layout Plain Layout
10214 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10217 \begin_layout Plain Layout
10225 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10228 \begin_layout Plain Layout
10236 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10239 \begin_layout Plain Layout
10247 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10250 \begin_layout Plain Layout
10260 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10263 \begin_layout Plain Layout
10269 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10272 \begin_layout Plain Layout
10280 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10283 \begin_layout Plain Layout
10291 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10294 \begin_layout Plain Layout
10302 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10305 \begin_layout Plain Layout
10315 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10318 \begin_layout Plain Layout
10324 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10327 \begin_layout Plain Layout
10335 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10338 \begin_layout Plain Layout
10346 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10349 \begin_layout Plain Layout
10357 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10360 \begin_layout Plain Layout
10370 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10373 \begin_layout Plain Layout
10379 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10382 \begin_layout Plain Layout
10390 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10393 \begin_layout Plain Layout
10401 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10404 \begin_layout Plain Layout
10412 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10415 \begin_layout Plain Layout
10425 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10428 \begin_layout Plain Layout
10434 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10437 \begin_layout Plain Layout
10445 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10448 \begin_layout Plain Layout
10456 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10459 \begin_layout Plain Layout
10467 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10470 \begin_layout Plain Layout
10480 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
10483 \begin_layout Plain Layout
10491 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
10494 \begin_layout Plain Layout
10502 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
10505 \begin_layout Plain Layout
10513 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
10516 \begin_layout Plain Layout
10524 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
10527 \begin_layout Plain Layout
10537 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10540 \begin_layout Plain Layout
10546 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10549 \begin_layout Plain Layout
10557 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10560 \begin_layout Plain Layout
10568 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10571 \begin_layout Plain Layout
10579 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10582 \begin_layout Plain Layout
10592 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10595 \begin_layout Plain Layout
10601 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10604 \begin_layout Plain Layout
10612 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10615 \begin_layout Plain Layout
10623 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10626 \begin_layout Plain Layout
10634 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10637 \begin_layout Plain Layout
10647 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10650 \begin_layout Plain Layout
10656 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10659 \begin_layout Plain Layout
10667 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10670 \begin_layout Plain Layout
10678 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10681 \begin_layout Plain Layout
10689 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10692 \begin_layout Plain Layout
10703 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10706 \begin_layout Plain Layout
10712 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10715 \begin_layout Plain Layout
10723 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10726 \begin_layout Plain Layout
10734 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10737 \begin_layout Plain Layout
10745 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10748 \begin_layout Plain Layout
10758 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10761 \begin_layout Plain Layout
10767 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10770 \begin_layout Plain Layout
10778 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10781 \begin_layout Plain Layout
10789 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10792 \begin_layout Plain Layout
10800 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10803 \begin_layout Plain Layout
10813 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10816 \begin_layout Plain Layout
10822 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10825 \begin_layout Plain Layout
10833 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10836 \begin_layout Plain Layout
10844 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10847 \begin_layout Plain Layout
10855 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10858 \begin_layout Plain Layout
10868 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10871 \begin_layout Plain Layout
10877 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10880 \begin_layout Plain Layout
10888 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10891 \begin_layout Plain Layout
10899 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10902 \begin_layout Plain Layout
10910 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10913 \begin_layout Plain Layout
10923 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10926 \begin_layout Plain Layout
10932 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10935 \begin_layout Plain Layout
10943 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10946 \begin_layout Plain Layout
10954 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10957 \begin_layout Plain Layout
10965 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10968 \begin_layout Plain Layout
10978 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
10981 \begin_layout Plain Layout
10987 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
10990 \begin_layout Plain Layout
10998 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11001 \begin_layout Plain Layout
11009 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11012 \begin_layout Plain Layout
11020 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
11023 \begin_layout Plain Layout
11033 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11036 \begin_layout Plain Layout
11044 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11047 \begin_layout Plain Layout
11055 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11058 \begin_layout Plain Layout
11066 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11069 \begin_layout Plain Layout
11077 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11080 \begin_layout Plain Layout
11090 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11093 \begin_layout Plain Layout
11099 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11102 \begin_layout Plain Layout
11110 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11113 \begin_layout Plain Layout
11121 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11124 \begin_layout Plain Layout
11132 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11135 \begin_layout Plain Layout
11145 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11148 \begin_layout Plain Layout
11154 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11157 \begin_layout Plain Layout
11165 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11168 \begin_layout Plain Layout
11176 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11179 \begin_layout Plain Layout
11187 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11190 \begin_layout Plain Layout
11200 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11203 \begin_layout Plain Layout
11209 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11212 \begin_layout Plain Layout
11220 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11223 \begin_layout Plain Layout
11231 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11234 \begin_layout Plain Layout
11242 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11245 \begin_layout Plain Layout
11256 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11259 \begin_layout Plain Layout
11265 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11268 \begin_layout Plain Layout
11276 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11279 \begin_layout Plain Layout
11287 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11290 \begin_layout Plain Layout
11298 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11301 \begin_layout Plain Layout
11311 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11314 \begin_layout Plain Layout
11320 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11323 \begin_layout Plain Layout
11331 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11334 \begin_layout Plain Layout
11342 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11345 \begin_layout Plain Layout
11353 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11356 \begin_layout Plain Layout
11366 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11369 \begin_layout Plain Layout
11375 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11378 \begin_layout Plain Layout
11386 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11389 \begin_layout Plain Layout
11397 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11400 \begin_layout Plain Layout
11408 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11411 \begin_layout Plain Layout
11421 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11424 \begin_layout Plain Layout
11430 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11433 \begin_layout Plain Layout
11441 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11444 \begin_layout Plain Layout
11452 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11455 \begin_layout Plain Layout
11463 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11466 \begin_layout Plain Layout
11476 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11479 \begin_layout Plain Layout
11485 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11488 \begin_layout Plain Layout
11496 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11499 \begin_layout Plain Layout
11507 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11510 \begin_layout Plain Layout
11518 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11521 \begin_layout Plain Layout
11531 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11534 \begin_layout Plain Layout
11540 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11543 \begin_layout Plain Layout
11551 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11554 \begin_layout Plain Layout
11562 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11565 \begin_layout Plain Layout
11573 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
11576 \begin_layout Plain Layout
11597 \begin_layout Section
11601 \begin_layout Standard
11602 Zkoušení všech zdrojových bloků pro každý cílový je neúnosně zdlouhavý proces.
11603 Proto je podstatná efektivní predikce.
11605 \begin_inset space ~
11608 této části je zkoumána účinnost predikce modulem popsaným v
11609 \begin_inset space ~
11613 \begin_inset CommandInset ref
11615 reference "Implementace/Predikce"
11622 \begin_layout Standard
11624 \begin_inset space ~
11628 \begin_inset CommandInset ref
11630 reference "Testování/Predikce/Tabulka"
11634 ukazuje pro různá množství zdrojových bloků dosaženou kvalitu, kompresní
11635 poměr a spotřebovaný čas.
11636 Hodnoty jsou naměřeny vždy pro různá nastavení limitu na predikovanou část
11637 ze všech bloků včetně varianty s
11638 \begin_inset space ~
11641 úplným prohledáváním místo predikce.
11645 \begin_layout Standard
11646 \begin_inset Float table
11651 \begin_layout Plain Layout
11652 \begin_inset Caption
11654 \begin_layout Plain Layout
11655 \begin_inset CommandInset label
11657 name "Testování/Predikce/Tabulka"
11661 Testování účinnosti predikce
11669 \begin_inset VSpace defskip
11675 \begin_layout Plain Layout
11678 \begin_inset space \hfill{}
11682 \begin_inset Tabular
11683 <lyxtabular version="3" rows="38" columns="6">
11685 <column alignment="center" valignment="top" width="0">
11686 <column alignment="center" valignment="top" width="0">
11687 <column alignment="center" valignment="top" width="0">
11688 <column alignment="center" valignment="top" width="0">
11689 <column alignment="center" valignment="top" width="0">
11690 <column alignment="center" valignment="top" width="0">
11692 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11695 \begin_layout Plain Layout
11701 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11704 \begin_layout Plain Layout
11712 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11715 \begin_layout Plain Layout
11723 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11726 \begin_layout Plain Layout
11734 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11737 \begin_layout Plain Layout
11745 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
11748 \begin_layout Plain Layout
11756 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11759 \begin_layout Plain Layout
11767 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11770 \begin_layout Plain Layout
11778 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11781 \begin_layout Plain Layout
11789 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11792 \begin_layout Plain Layout
11800 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11803 \begin_layout Plain Layout
11811 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
11814 \begin_layout Plain Layout
11824 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11827 \begin_layout Plain Layout
11835 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11838 \begin_layout Plain Layout
11841 \begin_inset Formula $2^{11}$
11849 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11852 \begin_layout Plain Layout
11855 \begin_inset Formula $2^{-10}$
11863 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11866 \begin_layout Plain Layout
11874 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11877 \begin_layout Plain Layout
11885 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
11888 \begin_layout Plain Layout
11898 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11901 \begin_layout Plain Layout
11907 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11910 \begin_layout Plain Layout
11916 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11919 \begin_layout Plain Layout
11922 \begin_inset Formula $2^{-8}$
11930 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11933 \begin_layout Plain Layout
11941 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11944 \begin_layout Plain Layout
11952 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11955 \begin_layout Plain Layout
11965 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11968 \begin_layout Plain Layout
11974 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11977 \begin_layout Plain Layout
11983 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11986 \begin_layout Plain Layout
11989 \begin_inset Formula $2^{-6}$
11997 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12000 \begin_layout Plain Layout
12008 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12011 \begin_layout Plain Layout
12019 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12022 \begin_layout Plain Layout
12032 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12035 \begin_layout Plain Layout
12041 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12044 \begin_layout Plain Layout
12050 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12053 \begin_layout Plain Layout
12061 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12064 \begin_layout Plain Layout
12072 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12075 \begin_layout Plain Layout
12083 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
12086 \begin_layout Plain Layout
12096 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12099 \begin_layout Plain Layout
12105 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12108 \begin_layout Plain Layout
12111 \begin_inset Formula $2^{15}$
12119 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12122 \begin_layout Plain Layout
12125 \begin_inset Formula $2^{-10}$
12133 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12136 \begin_layout Plain Layout
12144 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12147 \begin_layout Plain Layout
12155 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12158 \begin_layout Plain Layout
12168 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12171 \begin_layout Plain Layout
12177 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12180 \begin_layout Plain Layout
12186 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12189 \begin_layout Plain Layout
12192 \begin_inset Formula $2^{-8}$
12200 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12203 \begin_layout Plain Layout
12211 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12214 \begin_layout Plain Layout
12222 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12225 \begin_layout Plain Layout
12235 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12238 \begin_layout Plain Layout
12244 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12247 \begin_layout Plain Layout
12253 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12256 \begin_layout Plain Layout
12259 \begin_inset Formula $2^{-6}$
12267 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12270 \begin_layout Plain Layout
12278 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12281 \begin_layout Plain Layout
12289 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12292 \begin_layout Plain Layout
12302 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12305 \begin_layout Plain Layout
12311 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12314 \begin_layout Plain Layout
12320 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12323 \begin_layout Plain Layout
12331 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12334 \begin_layout Plain Layout
12342 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12345 \begin_layout Plain Layout
12353 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12356 \begin_layout Plain Layout
12366 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12369 \begin_layout Plain Layout
12375 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12378 \begin_layout Plain Layout
12381 \begin_inset Formula $2^{19}$
12389 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12392 \begin_layout Plain Layout
12395 \begin_inset Formula $2^{-10}$
12403 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12406 \begin_layout Plain Layout
12414 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12417 \begin_layout Plain Layout
12425 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
12428 \begin_layout Plain Layout
12438 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12441 \begin_layout Plain Layout
12447 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12450 \begin_layout Plain Layout
12456 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12459 \begin_layout Plain Layout
12462 \begin_inset Formula $2^{-8}$
12470 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12473 \begin_layout Plain Layout
12481 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12484 \begin_layout Plain Layout
12492 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12495 \begin_layout Plain Layout
12505 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12508 \begin_layout Plain Layout
12514 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12517 \begin_layout Plain Layout
12523 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12526 \begin_layout Plain Layout
12529 \begin_inset Formula $2^{-6}$
12537 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12540 \begin_layout Plain Layout
12548 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12551 \begin_layout Plain Layout
12559 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12562 \begin_layout Plain Layout
12572 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12575 \begin_layout Plain Layout
12581 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12584 \begin_layout Plain Layout
12590 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12593 \begin_layout Plain Layout
12601 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12604 \begin_layout Plain Layout
12612 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12615 \begin_layout Plain Layout
12623 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12626 \begin_layout Plain Layout
12636 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12639 \begin_layout Plain Layout
12647 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12650 \begin_layout Plain Layout
12653 \begin_inset Formula $2^{11}$
12661 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12664 \begin_layout Plain Layout
12667 \begin_inset Formula $2^{-10}$
12675 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12678 \begin_layout Plain Layout
12686 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12689 \begin_layout Plain Layout
12697 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
12700 \begin_layout Plain Layout
12710 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12713 \begin_layout Plain Layout
12719 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12722 \begin_layout Plain Layout
12728 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12731 \begin_layout Plain Layout
12734 \begin_inset Formula $2^{-8}$
12742 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12745 \begin_layout Plain Layout
12753 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12756 \begin_layout Plain Layout
12764 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12767 \begin_layout Plain Layout
12777 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12780 \begin_layout Plain Layout
12786 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12789 \begin_layout Plain Layout
12795 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12798 \begin_layout Plain Layout
12801 \begin_inset Formula $2^{-6}$
12809 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12812 \begin_layout Plain Layout
12820 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12823 \begin_layout Plain Layout
12831 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12834 \begin_layout Plain Layout
12844 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12847 \begin_layout Plain Layout
12853 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12856 \begin_layout Plain Layout
12862 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12865 \begin_layout Plain Layout
12873 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12876 \begin_layout Plain Layout
12884 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12887 \begin_layout Plain Layout
12895 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
12898 \begin_layout Plain Layout
12908 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12911 \begin_layout Plain Layout
12917 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12920 \begin_layout Plain Layout
12923 \begin_inset Formula $2^{15}$
12931 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12934 \begin_layout Plain Layout
12937 \begin_inset Formula $2^{-10}$
12945 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12948 \begin_layout Plain Layout
12956 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12959 \begin_layout Plain Layout
12967 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12970 \begin_layout Plain Layout
12980 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12983 \begin_layout Plain Layout
12989 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12992 \begin_layout Plain Layout
12998 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13001 \begin_layout Plain Layout
13004 \begin_inset Formula $2^{-8}$
13012 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13015 \begin_layout Plain Layout
13023 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13026 \begin_layout Plain Layout
13034 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13037 \begin_layout Plain Layout
13047 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13050 \begin_layout Plain Layout
13056 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13059 \begin_layout Plain Layout
13065 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13068 \begin_layout Plain Layout
13071 \begin_inset Formula $2^{-6}$
13079 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13082 \begin_layout Plain Layout
13090 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13093 \begin_layout Plain Layout
13101 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13104 \begin_layout Plain Layout
13114 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13117 \begin_layout Plain Layout
13123 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13126 \begin_layout Plain Layout
13132 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13135 \begin_layout Plain Layout
13143 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13146 \begin_layout Plain Layout
13154 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13157 \begin_layout Plain Layout
13165 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
13168 \begin_layout Plain Layout
13178 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13181 \begin_layout Plain Layout
13187 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13190 \begin_layout Plain Layout
13193 \begin_inset Formula $2^{19}$
13201 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13204 \begin_layout Plain Layout
13207 \begin_inset Formula $2^{-10}$
13215 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13218 \begin_layout Plain Layout
13226 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13229 \begin_layout Plain Layout
13237 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13240 \begin_layout Plain Layout
13250 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13253 \begin_layout Plain Layout
13259 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13262 \begin_layout Plain Layout
13268 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13271 \begin_layout Plain Layout
13274 \begin_inset Formula $2^{-8}$
13282 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13285 \begin_layout Plain Layout
13293 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13296 \begin_layout Plain Layout
13304 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13307 \begin_layout Plain Layout
13317 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13320 \begin_layout Plain Layout
13326 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13329 \begin_layout Plain Layout
13335 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13338 \begin_layout Plain Layout
13341 \begin_inset Formula $2^{-6}$
13349 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13352 \begin_layout Plain Layout
13360 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13363 \begin_layout Plain Layout
13371 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13374 \begin_layout Plain Layout
13384 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13387 \begin_layout Plain Layout
13393 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13396 \begin_layout Plain Layout
13402 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13405 \begin_layout Plain Layout
13413 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13416 \begin_layout Plain Layout
13424 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13427 \begin_layout Plain Layout
13435 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
13438 \begin_layout Plain Layout
13448 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13451 \begin_layout Plain Layout
13459 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13462 \begin_layout Plain Layout
13465 \begin_inset Formula $2^{11}$
13473 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13476 \begin_layout Plain Layout
13479 \begin_inset Formula $2^{-10}$
13487 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13490 \begin_layout Plain Layout
13498 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13501 \begin_layout Plain Layout
13509 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13512 \begin_layout Plain Layout
13522 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13525 \begin_layout Plain Layout
13531 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13534 \begin_layout Plain Layout
13540 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13543 \begin_layout Plain Layout
13546 \begin_inset Formula $2^{-8}$
13554 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13557 \begin_layout Plain Layout
13565 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13568 \begin_layout Plain Layout
13576 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13579 \begin_layout Plain Layout
13589 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13592 \begin_layout Plain Layout
13598 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13601 \begin_layout Plain Layout
13607 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13610 \begin_layout Plain Layout
13613 \begin_inset Formula $2^{-6}$
13621 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13624 \begin_layout Plain Layout
13632 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13635 \begin_layout Plain Layout
13643 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13646 \begin_layout Plain Layout
13656 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13659 \begin_layout Plain Layout
13665 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13668 \begin_layout Plain Layout
13674 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13677 \begin_layout Plain Layout
13685 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13688 \begin_layout Plain Layout
13696 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13699 \begin_layout Plain Layout
13707 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13710 \begin_layout Plain Layout
13720 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13723 \begin_layout Plain Layout
13729 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13732 \begin_layout Plain Layout
13735 \begin_inset Formula $2^{15}$
13743 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13746 \begin_layout Plain Layout
13749 \begin_inset Formula $2^{-10}$
13757 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13760 \begin_layout Plain Layout
13768 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13771 \begin_layout Plain Layout
13779 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
13782 \begin_layout Plain Layout
13792 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13795 \begin_layout Plain Layout
13801 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13804 \begin_layout Plain Layout
13810 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13813 \begin_layout Plain Layout
13816 \begin_inset Formula $2^{-8}$
13824 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13827 \begin_layout Plain Layout
13835 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13838 \begin_layout Plain Layout
13846 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13849 \begin_layout Plain Layout
13859 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13862 \begin_layout Plain Layout
13868 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13871 \begin_layout Plain Layout
13877 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13880 \begin_layout Plain Layout
13883 \begin_inset Formula $2^{-6}$
13891 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13894 \begin_layout Plain Layout
13902 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13905 \begin_layout Plain Layout
13913 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13916 \begin_layout Plain Layout
13926 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13929 \begin_layout Plain Layout
13935 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13938 \begin_layout Plain Layout
13944 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13947 \begin_layout Plain Layout
13955 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13958 \begin_layout Plain Layout
13966 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13969 \begin_layout Plain Layout
13977 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13980 \begin_layout Plain Layout
13990 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13993 \begin_layout Plain Layout
13999 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14002 \begin_layout Plain Layout
14005 \begin_inset Formula $2^{19}$
14013 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14016 \begin_layout Plain Layout
14019 \begin_inset Formula $2^{-10}$
14027 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14030 \begin_layout Plain Layout
14038 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14041 \begin_layout Plain Layout
14049 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14052 \begin_layout Plain Layout
14062 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14065 \begin_layout Plain Layout
14071 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14074 \begin_layout Plain Layout
14080 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14083 \begin_layout Plain Layout
14086 \begin_inset Formula $2^{-8}$
14094 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14097 \begin_layout Plain Layout
14105 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14108 \begin_layout Plain Layout
14116 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
14119 \begin_layout Plain Layout
14129 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14132 \begin_layout Plain Layout
14138 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14141 \begin_layout Plain Layout
14147 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14150 \begin_layout Plain Layout
14153 \begin_inset Formula $2^{-6}$
14161 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14164 \begin_layout Plain Layout
14172 <cell alignment="center" valignment="top" leftline="true" usebox="none">
14175 \begin_layout Plain Layout
14183 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
14186 \begin_layout Plain Layout
14196 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
14199 \begin_layout Plain Layout
14205 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
14208 \begin_layout Plain Layout
14214 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
14217 \begin_layout Plain Layout
14225 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
14228 \begin_layout Plain Layout
14236 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
14239 \begin_layout Plain Layout
14247 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
14250 \begin_layout Plain Layout
14264 \begin_inset Note Note
14267 \begin_layout Plain Layout
14270 \begin_inset Tabular
14271 <lyxtabular version="3" rows="11" columns="6">
14273 <column alignment="center" valignment="top" width="0">
14274 <column alignment="center" valignment="top" width="0">
14275 <column alignment="center" valignment="top" width="0">
14276 <column alignment="center" valignment="top" width="0">
14277 <column alignment="center" valignment="top" width="0">
14278 <column alignment="center" valignment="top" width="0">
14280 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14283 \begin_layout Plain Layout
14291 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14294 \begin_layout Plain Layout
14297 \begin_inset Formula $2^{11}$
14305 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14308 \begin_layout Plain Layout
14311 \begin_inset Formula $2^{-10}$
14319 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14322 \begin_layout Plain Layout
14330 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14333 \begin_layout Plain Layout
14341 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14344 \begin_layout Plain Layout
14354 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14357 \begin_layout Plain Layout
14363 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14366 \begin_layout Plain Layout
14372 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14375 \begin_layout Plain Layout
14378 \begin_inset Formula $2^{-8}$
14386 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14389 \begin_layout Plain Layout
14397 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14400 \begin_layout Plain Layout
14408 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14411 \begin_layout Plain Layout
14421 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14424 \begin_layout Plain Layout
14430 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14433 \begin_layout Plain Layout
14439 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14442 \begin_layout Plain Layout
14445 \begin_inset Formula $2^{-6}$
14453 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14456 \begin_layout Plain Layout
14464 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14467 \begin_layout Plain Layout
14475 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14478 \begin_layout Plain Layout
14488 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14491 \begin_layout Plain Layout
14497 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14500 \begin_layout Plain Layout
14506 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14509 \begin_layout Plain Layout
14517 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14520 \begin_layout Plain Layout
14528 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14531 \begin_layout Plain Layout
14539 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14542 \begin_layout Plain Layout
14552 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14555 \begin_layout Plain Layout
14561 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14564 \begin_layout Plain Layout
14567 \begin_inset Formula $2^{15}$
14575 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14578 \begin_layout Plain Layout
14581 \begin_inset Formula $2^{-10}$
14589 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14592 \begin_layout Plain Layout
14600 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14603 \begin_layout Plain Layout
14611 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14614 \begin_layout Plain Layout
14624 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14627 \begin_layout Plain Layout
14633 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14636 \begin_layout Plain Layout
14642 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14645 \begin_layout Plain Layout
14648 \begin_inset Formula $2^{-8}$
14656 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14659 \begin_layout Plain Layout
14667 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14670 \begin_layout Plain Layout
14678 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14681 \begin_layout Plain Layout
14691 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14694 \begin_layout Plain Layout
14700 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14703 \begin_layout Plain Layout
14709 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14712 \begin_layout Plain Layout
14715 \begin_inset Formula $2^{-6}$
14723 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14726 \begin_layout Plain Layout
14734 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14737 \begin_layout Plain Layout
14745 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14748 \begin_layout Plain Layout
14758 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14761 \begin_layout Plain Layout
14767 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14770 \begin_layout Plain Layout
14776 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14779 \begin_layout Plain Layout
14787 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14790 \begin_layout Plain Layout
14798 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14801 \begin_layout Plain Layout
14809 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14812 \begin_layout Plain Layout
14822 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14825 \begin_layout Plain Layout
14831 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14834 \begin_layout Plain Layout
14837 \begin_inset Formula $2^{19}$
14845 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14848 \begin_layout Plain Layout
14851 \begin_inset Formula $2^{-10}$
14859 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14862 \begin_layout Plain Layout
14870 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14873 \begin_layout Plain Layout
14881 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14884 \begin_layout Plain Layout
14894 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14897 \begin_layout Plain Layout
14903 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14906 \begin_layout Plain Layout
14912 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14915 \begin_layout Plain Layout
14918 \begin_inset Formula $2^{-8}$
14926 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14929 \begin_layout Plain Layout
14937 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14940 \begin_layout Plain Layout
14948 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14951 \begin_layout Plain Layout
14961 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14964 \begin_layout Plain Layout
14970 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14973 \begin_layout Plain Layout
14979 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14982 \begin_layout Plain Layout
14985 \begin_inset Formula $2^{-6}$
14993 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14996 \begin_layout Plain Layout
15004 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15007 \begin_layout Plain Layout
15015 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
15018 \begin_layout Plain Layout
15037 \begin_inset space \hfill{}
15048 \begin_layout Standard
15050 \begin_inset space ~
15053 výsledků je především vidět, že při malém množství zdrojových bloků je implement
15054 ovaná predikce velmi nevýhodná
15055 \begin_inset space ~
15059 \begin_inset space ~
15062 výrazně horší kvalitě i horšímu kompresnímu poměru při relativně malém množství
15064 To je nejspíše způsobeno vysokým počtem dimenzí prostoru indexovaného KD-strome
15066 Množství zdrojových bloků je uvažováno i s
15067 \begin_inset space ~
15070 rotacemi, takže limit
15071 \begin_inset Formula $2^{11}$
15075 \begin_inset Formula $2^{8}$
15079 \begin_inset space ~
15083 Protože body ve stromě jsou 16-prvkové vektory, jsou podprostory patřící
15084 listům omezeny nejvýše v
15085 \begin_inset space ~
15088 polovině ze všech souřadnic, což je velmi málo.
15089 Zde by nejspíše pomohla volba varianty stromu, kde listy obsahují přesné
15092 \begin_inset space ~
15095 přesnějším odhadům výměnou za větší časovou a paměťovou náročnost.
15098 \begin_layout Standard
15099 Pro účinnou kompresi jsou ale vhodnější větší počty zdrojových bloků a zde
15100 je již predikce účinnější.
15102 \begin_inset Formula $2^{19}$
15105 zdrojových blocích a predikování jejich části o
15106 \begin_inset space ~
15109 relativní velikosti
15110 \begin_inset Formula $2^{-8}$
15114 \begin_inset Formula $2^{-6}$
15117 jsou už poklesy PSNR okolo
15118 \begin_inset Formula $0.5$
15122 \begin_inset space \thinspace{}
15126 \begin_inset space ~
15129 některých obrázků znatelně klesá i kompresní poměr.
15132 \begin_layout Standard
15133 Zajímavé je porovnání s
15134 \begin_inset space ~
15138 \begin_inset space ~
15141 článku publikujícím základní použitou větu.
15142 \begin_inset space ~
15146 \begin_inset CommandInset citation
15152 Zde jsou také bloky pro účely predikce zmenšeny na velikost
15153 \begin_inset Formula $4\times4$
15156 , ale všechna čísla jsou kvantizována na 8 bitů a místo KD-stromů je použita
15157 mnohem složitější strutura navržená pro přibližné hledání nejbližších sousedů.
15158 Další drobnou odlišností je, že v
15159 \begin_inset space ~
15162 článku jsou obě metody prohledávání prováděny pouze v
15163 \begin_inset space ~
15166 rámci klasifikační třídy (použit je kód od Fishera
15167 \begin_inset space ~
15171 \begin_inset CommandInset citation
15177 ), ale to by na porovnání nemělo mít větší vliv.
15178 Výsledky na identických obrázcích
15186 pro různá množství zdrojových bloků zde ukazují pokles PSNR pod
15187 \begin_inset Formula $0.5$
15191 \begin_inset space \thinspace{}
15194 dB při zanedbatelném poklesu kompresního poměru, přestože je predikováno
15196 \begin_inset Formula $5\times16$
15199 bloků (je uvažováno 8 možných otočení a obě možnosti znaménka lineárního
15200 koeficientu barevného zobrazení).
15204 \begin_layout Plain Layout
15205 obrázek zde nazývaný
15210 \begin_inset space ~
15214 \begin_inset space ~
15218 \begin_inset CommandInset citation
15231 Nejpravděpodobnějším důvodem vyšší účinnosti predikce z
15232 \begin_inset space ~
15236 \begin_inset space ~
15240 \begin_inset CommandInset citation
15246 je použití jiné datové struktury a tedy KD-stromy pro tento problém zřejmě
15247 nebudou vhodné (alespoň v
15248 \begin_inset space ~
15251 uvedené implementaci bez informací o
15252 \begin_inset space ~
15255 souřadnicích bodů v
15256 \begin_inset space ~
15262 \begin_layout Standard
15263 Přesto se celkové výsledky v
15264 \begin_inset space ~
15267 implicitním nastavení pohybují okolo nejlepších hodnot dosahovaných Fisherovým
15269 \begin_inset space ~
15272 klasické variantě používající čtyřstrom a klasifikaci) a jeho zrychlenou
15274 \begin_inset space ~
15278 \begin_inset CommandInset citation
15280 key "Fish95,Saup95"
15284 ), jak ukazuje tabulka
15285 \begin_inset space ~
15289 \begin_inset CommandInset ref
15291 reference "Testování/Predikce/Fisher-Saupe-Tabulka"
15300 je dokonce kvalita výrazně vyšší.
15303 \begin_layout Standard
15304 \begin_inset Float table
15309 \begin_layout Plain Layout
15313 \begin_layout Plain Layout
15314 \begin_inset Caption
15316 \begin_layout Plain Layout
15317 \begin_inset CommandInset label
15319 name "Testování/Predikce/Fisher-Saupe-Tabulka"
15324 \begin_inset space ~
15327 publikovanými výsledky
15328 \begin_inset CommandInset citation
15330 key "Fish95,Saup95"
15342 \begin_inset VSpace defskip
15348 \begin_inset Box Frameless
15357 height_special "totalheight"
15360 \begin_layout Plain Layout
15361 \begin_inset space \hfill{}
15365 \begin_inset Tabular
15366 <lyxtabular version="3" rows="7" columns="5">
15368 <column alignment="center" valignment="top" width="0">
15369 <column alignment="center" valignment="top" width="0">
15370 <column alignment="center" valignment="top" width="0">
15371 <column alignment="center" valignment="top" width="0">
15372 <column alignment="center" valignment="top" width="0">
15374 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15377 \begin_layout Plain Layout
15383 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15386 \begin_layout Plain Layout
15392 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15395 \begin_layout Plain Layout
15402 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15405 \begin_layout Plain Layout
15411 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
15414 \begin_layout Plain Layout
15419 \begin_layout Plain Layout
15420 publikované doby komprese nejsou porovnatelné, protože byly získány na o
15421 \begin_inset space ~
15424 mnoho let starším hardwaru (procesor MIPS R4000)
15436 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15439 \begin_layout Plain Layout
15445 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15448 \begin_layout Plain Layout
15454 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15457 \begin_layout Plain Layout
15463 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15466 \begin_layout Plain Layout
15472 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15475 \begin_layout Plain Layout
15483 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15486 \begin_layout Plain Layout
15492 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15495 \begin_layout Plain Layout
15501 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15504 \begin_layout Plain Layout
15510 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15513 \begin_layout Plain Layout
15519 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
15522 \begin_layout Plain Layout
15530 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15533 \begin_layout Plain Layout
15539 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15542 \begin_layout Plain Layout
15548 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15551 \begin_layout Plain Layout
15557 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15560 \begin_layout Plain Layout
15566 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
15569 \begin_layout Plain Layout
15579 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15582 \begin_layout Plain Layout
15588 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15591 \begin_layout Plain Layout
15597 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15600 \begin_layout Plain Layout
15606 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15609 \begin_layout Plain Layout
15615 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15618 \begin_layout Plain Layout
15626 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15629 \begin_layout Plain Layout
15635 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15638 \begin_layout Plain Layout
15644 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15647 \begin_layout Plain Layout
15653 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15656 \begin_layout Plain Layout
15662 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
15665 \begin_layout Plain Layout
15673 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15676 \begin_layout Plain Layout
15682 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15685 \begin_layout Plain Layout
15691 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15694 \begin_layout Plain Layout
15700 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15703 \begin_layout Plain Layout
15709 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
15712 \begin_layout Plain Layout
15726 \begin_inset space \hspace*{\fill}
15742 \begin_layout Section
15743 Účinnost diferenčního kódování
15746 \begin_layout Standard
15748 \begin_inset space ~
15754 \begin_inset space ~
15758 \begin_inset CommandInset ref
15760 reference "Implementace/Zobrazování"
15766 sloužící pro správu zobrazení mezi bloky ukládá kvantizované průměrné hodnoty
15767 a směrodatné odchylky bloků pomocí kodeků, které spotřebovávají méně místa
15768 pro posloupnosti se
15769 \begin_inset space ~
15772 vzájemně blízkými po sobě jdoucími prvky
15773 \begin_inset space ~
15777 \begin_inset CommandInset ref
15779 reference "Implementace/Kódování_celočíselných_řad"
15784 Protože kódování ovlivňuje pouze způsob uložení a nemá vliv na přesnost
15785 hodnot, stačí testovat pouze změnu kompresního poměru (vliv na spotřebovaný
15786 čas je zanedbatelný).
15788 \begin_inset space ~
15791 této části bude zjištěno, kolik prostoru technika skutečně ušetří.
15795 \begin_layout Standard
15796 Prostor zabraný klasickou metodou byl změřen tak, že byly diferenčním modulům
15797 nastaveny počty symbolů v
15798 \begin_inset space ~
15801 první části na jejich celkový počet, což vede k
15802 \begin_inset space ~
15805 tomu, že se na každou hodnotu spotřebuje pevný počet bitů, právě dvojkový
15807 \begin_inset space ~
15810 počtu symbolů (to je pro
15812 MStd\SpecialChar \-
15820 \begin_layout Standard
15821 Výsledky pro tři obrázky a různá nastavení kvality ukazuje tabulka
15822 \begin_inset space ~
15826 \begin_inset CommandInset ref
15828 reference "Testování/Kódování/Tabulka"
15832 , kde diferenční kódování vždy přináší úsporu prostoru, obvykle okolo
15833 \begin_inset Formula $5\%$
15837 Jsou zde také vidět dva trendy
15838 \begin_inset space ~
15841 --- větší účinek při vyšší kvalitě a také při menším počtu zdrojových bloků.
15842 Zvýšení nastavené kvality vede k
15843 \begin_inset space ~
15846 rozdělení na menší cílové bloky, což zvyšuje korelaci jejich vlastností
15847 a tím i efektivitu metody.
15848 Snížení počtu zdrojových bloků také vede k
15849 \begin_inset space ~
15852 rozdělení na více cílových bloků, protože je tím snížena pravděpodobnost
15853 nalezení vhodného zobrazení, a navíc ještě zvyšuje podíl výsledného prostoru
15854 ovlivněného metodou, protože identifikátory zdrojových bloků zaberou méně
15858 \begin_layout Standard
15861 \begin_inset Float table
15866 \begin_layout Plain Layout
15869 \begin_inset Caption
15871 \begin_layout Plain Layout
15872 \begin_inset CommandInset label
15874 name "Testování/Kódování/Tabulka"
15878 Testování účinnosti diferenčního kódování
15884 \begin_inset VSpace defskip
15890 \begin_layout Plain Layout
15893 \begin_inset space \hfill{}
15897 \begin_inset Tabular
15898 <lyxtabular version="3" rows="14" columns="8">
15900 <column alignment="center" valignment="top" width="0">
15901 <column alignment="center" valignment="top" width="0">
15902 <column alignment="center" valignment="top" width="0">
15903 <column alignment="center" valignment="top" width="0">
15904 <column alignment="center" valignment="top" width="0">
15905 <column alignment="center" valignment="top" width="0">
15906 <column alignment="center" valignment="top" width="0">
15907 <column alignment="center" valignment="top" width="0">
15909 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15912 \begin_layout Plain Layout
15918 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15921 \begin_layout Plain Layout
15929 <cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15932 \begin_layout Plain Layout
15937 \begin_inset Formula $2^{19}$
15946 <cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15949 \begin_layout Plain Layout
15955 <cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15958 \begin_layout Plain Layout
15964 <cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15967 \begin_layout Plain Layout
15972 \begin_inset Formula $2^{15}$
15981 <cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15984 \begin_layout Plain Layout
15990 <cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15993 \begin_layout Plain Layout
16001 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16004 \begin_layout Plain Layout
16012 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16015 \begin_layout Plain Layout
16023 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16026 \begin_layout Plain Layout
16035 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16038 \begin_layout Plain Layout
16047 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16050 \begin_layout Plain Layout
16058 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16061 \begin_layout Plain Layout
16070 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16073 \begin_layout Plain Layout
16082 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
16085 \begin_layout Plain Layout
16095 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16098 \begin_layout Plain Layout
16106 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16109 \begin_layout Plain Layout
16117 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16120 \begin_layout Plain Layout
16128 <cell alignment="center" valignment="top" topline="true" usebox="none">
16131 \begin_layout Plain Layout
16139 <cell alignment="center" valignment="top" topline="true" usebox="none">
16142 \begin_layout Plain Layout
16150 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16153 \begin_layout Plain Layout
16161 <cell alignment="center" valignment="top" topline="true" usebox="none">
16164 \begin_layout Plain Layout
16172 <cell alignment="center" valignment="top" topline="true" rightline="true" usebox="none">
16175 \begin_layout Plain Layout
16185 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16188 \begin_layout Plain Layout
16194 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16197 \begin_layout Plain Layout
16205 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16208 \begin_layout Plain Layout
16216 <cell alignment="center" valignment="top" usebox="none">
16219 \begin_layout Plain Layout
16227 <cell alignment="center" valignment="top" usebox="none">
16230 \begin_layout Plain Layout
16238 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16241 \begin_layout Plain Layout
16249 <cell alignment="center" valignment="top" usebox="none">
16252 \begin_layout Plain Layout
16260 <cell alignment="center" valignment="top" rightline="true" usebox="none">
16263 \begin_layout Plain Layout
16273 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16276 \begin_layout Plain Layout
16282 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16285 \begin_layout Plain Layout
16293 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16296 \begin_layout Plain Layout
16304 <cell alignment="center" valignment="top" usebox="none">
16307 \begin_layout Plain Layout
16315 <cell alignment="center" valignment="top" usebox="none">
16318 \begin_layout Plain Layout
16326 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16329 \begin_layout Plain Layout
16337 <cell alignment="center" valignment="top" usebox="none">
16340 \begin_layout Plain Layout
16348 <cell alignment="center" valignment="top" rightline="true" usebox="none">
16351 \begin_layout Plain Layout
16361 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16364 \begin_layout Plain Layout
16370 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16373 \begin_layout Plain Layout
16381 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16384 \begin_layout Plain Layout
16392 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
16395 \begin_layout Plain Layout
16403 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
16406 \begin_layout Plain Layout
16414 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16417 \begin_layout Plain Layout
16425 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
16428 \begin_layout Plain Layout
16436 <cell alignment="center" valignment="top" bottomline="true" rightline="true" usebox="none">
16439 \begin_layout Plain Layout
16449 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16452 \begin_layout Plain Layout
16460 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16463 \begin_layout Plain Layout
16471 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16474 \begin_layout Plain Layout
16482 <cell alignment="center" valignment="top" usebox="none">
16485 \begin_layout Plain Layout
16493 <cell alignment="center" valignment="top" usebox="none">
16496 \begin_layout Plain Layout
16504 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16507 \begin_layout Plain Layout
16515 <cell alignment="center" valignment="top" usebox="none">
16518 \begin_layout Plain Layout
16526 <cell alignment="center" valignment="top" rightline="true" usebox="none">
16529 \begin_layout Plain Layout
16539 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16542 \begin_layout Plain Layout
16548 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16551 \begin_layout Plain Layout
16559 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16562 \begin_layout Plain Layout
16570 <cell alignment="center" valignment="top" usebox="none">
16573 \begin_layout Plain Layout
16581 <cell alignment="center" valignment="top" usebox="none">
16584 \begin_layout Plain Layout
16592 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16595 \begin_layout Plain Layout
16603 <cell alignment="center" valignment="top" usebox="none">
16606 \begin_layout Plain Layout
16614 <cell alignment="center" valignment="top" rightline="true" usebox="none">
16617 \begin_layout Plain Layout
16627 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16630 \begin_layout Plain Layout
16636 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16639 \begin_layout Plain Layout
16647 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16650 \begin_layout Plain Layout
16658 <cell alignment="center" valignment="top" usebox="none">
16661 \begin_layout Plain Layout
16669 <cell alignment="center" valignment="top" usebox="none">
16672 \begin_layout Plain Layout
16680 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16683 \begin_layout Plain Layout
16691 <cell alignment="center" valignment="top" usebox="none">
16694 \begin_layout Plain Layout
16702 <cell alignment="center" valignment="top" rightline="true" usebox="none">
16705 \begin_layout Plain Layout
16715 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16718 \begin_layout Plain Layout
16724 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16727 \begin_layout Plain Layout
16735 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16738 \begin_layout Plain Layout
16746 <cell alignment="center" valignment="top" usebox="none">
16749 \begin_layout Plain Layout
16757 <cell alignment="center" valignment="top" usebox="none">
16760 \begin_layout Plain Layout
16768 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16771 \begin_layout Plain Layout
16779 <cell alignment="center" valignment="top" usebox="none">
16782 \begin_layout Plain Layout
16790 <cell alignment="center" valignment="top" rightline="true" usebox="none">
16793 \begin_layout Plain Layout
16803 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16806 \begin_layout Plain Layout
16814 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16817 \begin_layout Plain Layout
16825 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16828 \begin_layout Plain Layout
16836 <cell alignment="center" valignment="top" topline="true" usebox="none">
16839 \begin_layout Plain Layout
16847 <cell alignment="center" valignment="top" topline="true" usebox="none">
16850 \begin_layout Plain Layout
16858 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16861 \begin_layout Plain Layout
16869 <cell alignment="center" valignment="top" topline="true" usebox="none">
16872 \begin_layout Plain Layout
16880 <cell alignment="center" valignment="top" topline="true" rightline="true" usebox="none">
16883 \begin_layout Plain Layout
16893 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16896 \begin_layout Plain Layout
16902 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16905 \begin_layout Plain Layout
16913 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16916 \begin_layout Plain Layout
16924 <cell alignment="center" valignment="top" usebox="none">
16927 \begin_layout Plain Layout
16935 <cell alignment="center" valignment="top" usebox="none">
16938 \begin_layout Plain Layout
16946 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16949 \begin_layout Plain Layout
16957 <cell alignment="center" valignment="top" usebox="none">
16960 \begin_layout Plain Layout
16968 <cell alignment="center" valignment="top" rightline="true" usebox="none">
16971 \begin_layout Plain Layout
16981 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16984 \begin_layout Plain Layout
16990 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16993 \begin_layout Plain Layout
17001 <cell alignment="center" valignment="top" leftline="true" usebox="none">
17004 \begin_layout Plain Layout
17012 <cell alignment="center" valignment="top" usebox="none">
17015 \begin_layout Plain Layout
17023 <cell alignment="center" valignment="top" usebox="none">
17026 \begin_layout Plain Layout
17034 <cell alignment="center" valignment="top" leftline="true" usebox="none">
17037 \begin_layout Plain Layout
17045 <cell alignment="center" valignment="top" usebox="none">
17048 \begin_layout Plain Layout
17056 <cell alignment="center" valignment="top" rightline="true" usebox="none">
17059 \begin_layout Plain Layout
17069 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
17072 \begin_layout Plain Layout
17078 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
17081 \begin_layout Plain Layout
17089 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
17092 \begin_layout Plain Layout
17100 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
17103 \begin_layout Plain Layout
17111 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
17114 \begin_layout Plain Layout
17122 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
17125 \begin_layout Plain Layout
17133 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
17136 \begin_layout Plain Layout
17144 <cell alignment="center" valignment="top" bottomline="true" rightline="true" usebox="none">
17147 \begin_layout Plain Layout
17161 \begin_inset Note Note
17164 \begin_layout Plain Layout
17167 \begin_inset Tabular
17168 <lyxtabular version="3" rows="11" columns="6">
17170 <column alignment="center" valignment="top" width="0">
17171 <column alignment="center" valignment="top" width="0">
17172 <column alignment="center" valignment="top" width="0">
17173 <column alignment="center" valignment="top" width="0">
17174 <column alignment="center" valignment="top" width="0">
17175 <column alignment="center" valignment="top" width="0">
17177 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17180 \begin_layout Plain Layout
17188 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17191 \begin_layout Plain Layout
17194 \begin_inset Formula $2^{11}$
17202 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17205 \begin_layout Plain Layout
17208 \begin_inset Formula $2^{-10}$
17216 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17219 \begin_layout Plain Layout
17227 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17230 \begin_layout Plain Layout
17238 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17241 \begin_layout Plain Layout
17251 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17254 \begin_layout Plain Layout
17260 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17263 \begin_layout Plain Layout
17269 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17272 \begin_layout Plain Layout
17275 \begin_inset Formula $2^{-8}$
17283 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17286 \begin_layout Plain Layout
17294 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17297 \begin_layout Plain Layout
17305 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17308 \begin_layout Plain Layout
17318 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17321 \begin_layout Plain Layout
17327 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17330 \begin_layout Plain Layout
17336 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17339 \begin_layout Plain Layout
17342 \begin_inset Formula $2^{-6}$
17350 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17353 \begin_layout Plain Layout
17361 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17364 \begin_layout Plain Layout
17372 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17375 \begin_layout Plain Layout
17385 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17388 \begin_layout Plain Layout
17394 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17397 \begin_layout Plain Layout
17403 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17406 \begin_layout Plain Layout
17414 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17417 \begin_layout Plain Layout
17425 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17428 \begin_layout Plain Layout
17436 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17439 \begin_layout Plain Layout
17449 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17452 \begin_layout Plain Layout
17458 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17461 \begin_layout Plain Layout
17464 \begin_inset Formula $2^{15}$
17472 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17475 \begin_layout Plain Layout
17478 \begin_inset Formula $2^{-10}$
17486 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17489 \begin_layout Plain Layout
17497 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17500 \begin_layout Plain Layout
17508 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17511 \begin_layout Plain Layout
17521 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17524 \begin_layout Plain Layout
17530 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17533 \begin_layout Plain Layout
17539 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17542 \begin_layout Plain Layout
17545 \begin_inset Formula $2^{-8}$
17553 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17556 \begin_layout Plain Layout
17564 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17567 \begin_layout Plain Layout
17575 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17578 \begin_layout Plain Layout
17588 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17591 \begin_layout Plain Layout
17597 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17600 \begin_layout Plain Layout
17606 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17609 \begin_layout Plain Layout
17612 \begin_inset Formula $2^{-6}$
17620 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17623 \begin_layout Plain Layout
17631 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17634 \begin_layout Plain Layout
17642 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17645 \begin_layout Plain Layout
17655 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17658 \begin_layout Plain Layout
17664 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17667 \begin_layout Plain Layout
17673 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17676 \begin_layout Plain Layout
17684 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17687 \begin_layout Plain Layout
17695 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17698 \begin_layout Plain Layout
17706 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17709 \begin_layout Plain Layout
17719 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17722 \begin_layout Plain Layout
17728 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17731 \begin_layout Plain Layout
17734 \begin_inset Formula $2^{19}$
17742 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17745 \begin_layout Plain Layout
17748 \begin_inset Formula $2^{-10}$
17756 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17759 \begin_layout Plain Layout
17767 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17770 \begin_layout Plain Layout
17778 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17781 \begin_layout Plain Layout
17791 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17794 \begin_layout Plain Layout
17800 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17803 \begin_layout Plain Layout
17809 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17812 \begin_layout Plain Layout
17815 \begin_inset Formula $2^{-8}$
17823 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17826 \begin_layout Plain Layout
17834 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17837 \begin_layout Plain Layout
17845 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17848 \begin_layout Plain Layout
17858 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17861 \begin_layout Plain Layout
17867 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17870 \begin_layout Plain Layout
17876 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17879 \begin_layout Plain Layout
17882 \begin_inset Formula $2^{-6}$
17890 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17893 \begin_layout Plain Layout
17901 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17904 \begin_layout Plain Layout
17912 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
17915 \begin_layout Plain Layout
17934 \begin_inset space \hfill{}
17945 \begin_layout Section
17949 \begin_layout Standard
17950 Během předchozích testů bylo doladěno implicitní nastavení některých parametrů
17953 \begin_inset space ~
17956 této části je vyhodnocována celková efektivita komprese a porovnána se standardn
17957 ími metodami JPEG a JPEG
17958 \begin_inset space ~
17964 \begin_layout Standard
17965 Fraktální komprese je testována pro několik vybraných nastavení počtu zdrojových
17966 bloků a jejich maximální predikované části (značeny
17967 \begin_inset Formula $z$
17971 \begin_inset Formula $p$
17974 ), které představují různé poměry účinnosti a spotřebovaného času.
17975 Implicitní nastavení je
17976 \begin_inset Formula $z=2^{19}$
17980 \begin_inset Formula $p=2^{-8}$
17986 \begin_layout Standard
17988 \begin_inset space ~
17992 \begin_inset CommandInset ref
17994 reference "Testování/Celkové/Čas-Lena"
17998 ukazuje závislost spotřebovaného času na kompresním poměru pro obrázek
18004 Graf potvrzuje fakt, že fraktální komprese spotřebuje při použitelné kvalitě
18005 řádově více času než standardní metody.
18007 \begin_inset space ~
18010 těch se spotřebovaný čas s
18011 \begin_inset space ~
18014 kompresním poměrem výrazněji nemění, ale fraktální komprese spotřebuje při
18015 nízkém nastavení kvality času méně.
18016 Grafy závislosti času na kompresním poměru pro ostatních pět testovaných
18017 obrázků vypadají stejně, a proto zde nejsou uvedeny.
18020 \begin_layout Standard
18021 \begin_inset Float figure
18026 \begin_layout Plain Layout
18027 \begin_inset Caption
18029 \begin_layout Plain Layout
18030 \begin_inset CommandInset label
18032 name "Testování/Celkové/Čas-Lena"
18036 Graf závislosti doby komprese na kompresním poměru pro obrázek
18044 \begin_inset space \hfill{}
18048 \begin_inset Graphics
18049 filename graphs/lena-time.eps
18054 \begin_inset space \hfill{}
18065 \begin_layout Standard
18066 Zajímavější je závislost kvality na kompresním poměru.
18068 \begin_inset space ~
18072 \begin_inset CommandInset ref
18074 reference "Testování/PSNR-Lena"
18082 , kde mají všechny křivky podobný průběh a fraktální komprese nedosahuje
18083 účinnosti standardních metod.
18084 Stejný vzhled mají i neuvedené grafy pro obrázky
18093 Podobný je také graf pro obrázek
18096 \begin_inset space ~
18102 \begin_inset CommandInset ref
18104 reference "Testování/PSNR-Mandrill"
18108 , akorát mají křivky jiné tvary a při použitelných hodnotách kvality se
18109 fraktální komprese více přibližuje JPEG kompresi.
18112 \begin_layout Standard
18114 \begin_inset space ~
18120 \begin_inset space ~
18126 \begin_inset CommandInset ref
18128 reference "Testování/PSNR-Serrano"
18133 Zde dává fraktální komprese výrazně lepší výsledky než JPEG a v
18134 \begin_inset space ~
18137 některých případech dokonce i
18138 \begin_inset space ~
18142 \begin_inset space ~
18146 \begin_inset space ~
18150 Podobně vypadá i graf pro obrázek
18153 \begin_inset space ~
18159 \begin_inset CommandInset ref
18161 reference "Testování/PSNR-Clegg"
18165 , ale zde již nedává fraktální komprese tak dobré výsledky.
18168 \begin_layout Standard
18169 Testy ukazují, že spíše než na běžné spojité fotografie je zde implementovaná
18170 fraktální komprese vhodnější pro obrázky obsahující ostré hrany, jako zkoušené
18174 \begin_layout Standard
18175 \begin_inset Float figure
18180 \begin_layout Plain Layout
18181 \begin_inset Caption
18183 \begin_layout Plain Layout
18184 \begin_inset CommandInset label
18186 name "Testování/PSNR-Lena"
18190 Graf závislosti kvality na kompresním poměru pro obrázek
18198 \begin_inset space \hfill{}
18202 \begin_inset Graphics
18203 filename graphs/lena-PSNR.eps
18208 \begin_inset space \hfill{}
18214 \begin_layout Plain Layout
18223 \begin_layout Standard
18224 \begin_inset Float figure
18229 \begin_layout Plain Layout
18230 \begin_inset Caption
18232 \begin_layout Plain Layout
18233 \begin_inset CommandInset label
18235 name "Testování/PSNR-Mandrill"
18239 Graf závislosti kvality na kompresním poměru pro obrázek
18249 \begin_layout Plain Layout
18250 \begin_inset space \hfill{}
18254 \begin_inset Graphics
18255 filename graphs/mandrill-PSNR.eps
18260 \begin_inset space \hfill{}
18271 \begin_layout Standard
18272 \begin_inset Float figure
18277 \begin_layout Plain Layout
18278 \begin_inset Caption
18280 \begin_layout Plain Layout
18281 \begin_inset CommandInset label
18283 name "Testování/PSNR-Serrano"
18287 Graf závislosti kvality na kompresním poměru pro obrázek
18297 \begin_layout Plain Layout
18298 \begin_inset space \hfill{}
18302 \begin_inset Graphics
18303 filename graphs/serrano-PSNR.eps
18308 \begin_inset space \hfill{}
18319 \begin_layout Standard
18320 \begin_inset Float figure
18325 \begin_layout Plain Layout
18326 \begin_inset Caption
18328 \begin_layout Plain Layout
18329 \begin_inset CommandInset label
18331 name "Testování/PSNR-Clegg"
18335 Graf závislosti kvality na kompresním poměru pro obrázek
18345 \begin_layout Plain Layout
18346 \begin_inset space \hfill{}
18350 \begin_inset Graphics
18351 filename graphs/clegg-PSNR.eps
18356 \begin_inset space \hfill{}
18367 \begin_layout Chapter
18371 \begin_layout Standard
18373 \begin_inset space ~
18376 této práci byl představen modulární systém pro fraktální kompresi obrazu
18377 umožňující efektivní implementaci vyměnitelných algoritmů s
18378 \begin_inset space ~
18381 minimální zátěží technického kódu.
18382 Pro tento systém byla implementována sada modulů provádějící většinou klasická
18383 řešení jednotlivých části fraktální komprese.
18385 \begin_inset space ~
18388 grafickým a dávkovým uživatelským rozhraním vznikl funkční celek vhodný
18389 pro výzkum vlastností komprese.
18390 Kromě použití známých metod byla navržena drobná vylepšení.
18391 Jejich vliv a také celkový výsledek byly experimentálně vyhodnoceny a porovnány
18392 se standardními metodami komprese.
18395 \begin_layout Standard
18396 Implementace byla prováděna s
18397 \begin_inset space ~
18400 ohledem na možnost snadného doplnění dalších algoritmů a jejich kombinování.
18401 Mnoho možností dalšího rozšíření bylo zmíněno v
18402 \begin_inset space ~
18406 \begin_inset space ~
18410 \begin_inset CommandInset ref
18417 Mezi nejzajímavější patří horizontálně-vertikální dělení cílových bloků
18418 a možnost aproximace cílových bloků pomocí většího počtu zdrojových bloků.
18419 Dalším vhodným rozšířením implementace by v
18420 \begin_inset space ~
18423 budoucnosti mohlo být vylepšení nebo nahrazení stávajícího predikčního modulu,
18424 jehož účinnost podle provedených testů není ideální.
18427 \begin_layout Chapter*
18431 \begin_layout Standard
18432 \begin_inset CommandInset bibtex
18433 LatexCommand bibtex
18434 btprint "btPrintCited"
18435 bibfiles "fractals"
18443 \begin_layout Chapter*
18447 \begin_layout Standard
18448 \begin_inset CommandInset bibtex
18449 LatexCommand bibtex
18450 btprint "btPrintCited"
18451 bibfiles "internet"