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"
122 \begin_layout Chapter
126 \begin_layout Standard
127 <Představení práce, motivace a přehled obsahu kapitol.>
130 \begin_layout Chapter
131 Vývoj a principy fraktální komprese obrazu
134 \begin_layout Standard
135 V této kapitole bude používáno následující značení:
138 \begin_layout Description
144 \begin_inset Formula $2^{X}=\left\{ A:\, A\subseteq X\right\} $
150 \begin_layout Description
155 zobrazení mějme zobrazení
156 \begin_inset Formula $f:\, X\rightarrow X$
160 \begin_inset Formula $f^{k}:\, X\rightarrow X$
163 je definováno tak, že
164 \begin_inset Formula $f^{0}$
168 \begin_inset Formula \[
169 \forall k\geq1\quad\forall x\in X\quad f^{k}\left(x\right)=f\left(f^{k-1}\left(x\right)\right)\]
176 \begin_layout Description
182 \begin_inset Formula $f:\, X\rightarrow X$
185 na metrickém prostoru
186 \begin_inset Formula $X$
194 \begin_inset Formula $d$
197 je kontraktivní, pokud
198 \begin_inset Formula \[
199 \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)\]
204 \begin_inset Formula $s$
207 budeme nazývat faktorem kontraktivity
208 \begin_inset Formula $f$
214 \begin_layout Section
218 \begin_layout Standard
219 Základy fraktální komprese byly položeny v druhé polovině 80.
220 \begin_inset space \thinspace{}
223 let, kdy Barnsley studoval systémy iterovaných funkcí (IFS).
225 \begin_inset Formula $A$
232 úplném metrickém prostoru
233 \begin_inset Formula $X$
236 definována pomocí souboru kontraktivních zobrazení
237 \begin_inset Formula $X$
241 Mějme soubor zobrazení
242 \begin_inset Formula $f_{i}:X\rightarrow X$
246 \begin_inset Formula $i\in J$
249 a definujme jejich sjednocení
250 \begin_inset Formula $f:2^{X}\rightarrow2^{X}$
254 \begin_inset Formula $B\subseteq X$
258 \begin_inset Formula $f\left(B\right)=\left\{ f_{i}\left(b\right)\mid i\in J,\ b\in B\right\} $
263 \begin_inset Formula $2^{X}$
266 lze definovat metriku tak, abychom dostali zase úplný metrický prostor
268 \begin_inset Formula $f$
271 bylo kontraktivní, jak je ukázáno například v
276 \begin_inset CommandInset citation
282 pomocí Hausdorffovy metriky.
283 To podle Banachovy věty o
287 pevném bodě dává, že takto vzniklé zobrazení
288 \begin_inset Formula $f$
291 má právě jeden pevný bod, kterým je právě hledaná množina
292 \begin_inset Formula $A$
295 , často nazývaná atraktor nebo fraktál
299 \begin_layout Plain Layout
300 fraktály lze konstruovat i jinými způsoby než pomocí IFS
308 \begin_layout Standard
309 IFS mají několik zajímavých vlastností.
310 Pro získání atraktoru stačí znát zobrazení
311 \begin_inset Formula $f$
314 a iterovat ho na libovolné neprázdné kompaktní podmnožině prostoru
315 \begin_inset Formula $X$
319 Navíc vzniklé fraktály mohou mít detailní kresbu při libovolném přiblížení,
320 přestože jejich matematický popis je velmi malý, takže pro tyto speciální
321 obrázky lze dosáhnout libovolně velkého kompresního poměru.
322 Mezi nejznámější IFS patří Barnsleyho kapradina, generovaná v
323 \begin_inset Formula $\mathbb{R}^{2}$
326 pomocí čtyř afinních zobrazení.
327 Barnsley zkoumal, zda by nebylo možné proces obrátit
335 danému obrázku najít soubor zobrazení, jehož pevný bod by obrázku byl velmi
337 Pak by místo souboru pixelů stačil pro popis obrázku jen popis těchto zobrazení.
340 \begin_layout Standard
341 Zde se používá takzvaná kolážová věta, uvedená například v
346 \begin_inset CommandInset citation
352 , která dává horní odhad na odchylku atraktoru od požadovaného obrázku:
355 \begin_layout Standard
359 \begin_layout Plain Layout
378 \begin_inset Formula $f$
381 je zobrazení úplného metrického prostoru do sebe, které je kontraktivní
387 \begin_inset Formula $s<1$
395 \begin_inset Formula $d$
399 \begin_inset Formula \[
400 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).\]
408 \begin_layout Plain Layout
420 \begin_layout Standard
421 Díky tomu stačí hledat zobrazení, která obrázek transformují a přitom ho
423 Pro jistotu konvergence dokonce stačí,
433 \begin_inset Formula $f^{k}$
450 \begin_inset Formula $s<1$
454 \begin_inset Formula $k$
458 Ukázalo se, že největší problém je v
462 tom, že na rozdíl od klasických IFS málokterý obrázek lze charakterizovat
463 jako sjednocení několika transformovaných zmenšenin celého obrázku.
464 Bylo sice možné obrázek rozdělit na menší kusy charakterizované IFS, ale
465 tuto metodu se nepodařilo zautomatizovat.
468 \begin_layout Section
470 \begin_inset CommandInset label
479 \begin_layout Standard
480 Pro kompresi obrázků také bylo nutné najít lepší model, než množinu bodů
486 \begin_inset Formula $\mathbb{R}^{2}$
494 možností reprezentace obrázků ve stupních šedi je funkce tvaru
495 \begin_inset Formula $g:I^{2}\rightarrow I$
499 \begin_inset Formula $I$
502 je značení pro interval
503 \begin_inset Formula $\left[0,1\right]\subset\mathbb{R}$
507 Zde budeme analogicky hledat soubor funkcí na těchto obrázkových funkcích
508 (budeme je nazývat operátory) takový, aby jejich sjednocením vznikl operátor
510 \begin_inset Formula $F$
517 pevným bodem co nejblíže danému obrázku (tedy jeho funkci).
518 Aby bylo zaručeno, že lze sjednocení provést, v
522 PIFS (partitioned IFS) je prostor obrázku rozdělen na disjunktní části
523 \begin_inset Formula \[
524 \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\]
528 a operátory jsou tvaru
529 \begin_inset Formula $F_{i}:\left(I^{2}\rightarrow I\right)\rightarrow\left(R_{i}\rightarrow I\right)$
535 \begin_layout Standard
536 PIFS, které zavedl Jacquin, dnes tvoří základ naprosté většiny technik pro
537 fraktální kompresi obrazu.
538 Pro zjednodušení se zde uvažují pouze afinní operátory, kde se navíc vzájemně
539 neovlivňuje transformace polohy s
544 Formální zápis aplikace operátoru na obrázek
545 \begin_inset Formula $g:I^{2}\rightarrow I$
549 \begin_inset Formula \[
550 F_{i}g=h_{i},\qquad h_{i}:R_{i}\rightarrow I,\qquad h_{i}\left(\left[\begin{array}{c}
552 y\end{array}\right]\right)=\left(c_{i}\circ g\circ w_{i}\right)\left(\left[\begin{array}{c}
554 y\end{array}\right]\right)\]
559 \begin_inset Formula \[
560 \text{pro nějaká afinní zobrazení\quad}w_{i}:R_{i}\rightarrow I^{2}\mbox{\quad a\quad}c_{i}:I\rightarrow\mathbb{R}\]
574 \begin_inset Formula $R_{i}$
577 se volí souvislé části obrazu, typicky čtverce o
582 \begin_inset Formula $2^{k}$
589 nazývají se cílové bloky.
591 \begin_inset Formula $w_{i}$
595 \begin_inset Formula $D_{i}=w_{i}\left(R_{i}\right)$
598 také souvislé části obrazu a nazývají se zdrojové bloky.
602 \begin_layout Plain Layout
613 \begin_inset Formula $D_{i}$
617 \begin_inset Formula $R_{i}$
657 \begin_inset Formula $w_{i}$
660 určuje, která část obrazu bude zobrazena do cílového bloku a také jak bude
661 otočena a případně symetricky převrácena.
663 \begin_inset Formula $w_{i}$
666 se volí kontraktivní zobrazení, přestože to pro níže uvedené tvrzení o
670 konvergenci není potřeba.
671 Tato kontraktivita mimo jiné způsobuje vytváření nových detailů při přiblížení.
674 \begin_layout Subsection
678 \begin_layout Standard
679 Pro konvergenci a horní odhad chyby PIFS modelu lze zase použít kolážovou
681 Následující důkaz je modifikací důkazu uvedeného v
686 \begin_inset CommandInset citation
693 Zde se hodí metrika na obrázcích (funkcích
694 \begin_inset Formula $g_{i}:I^{2}\rightarrow I$
698 \begin_inset Formula \[
699 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\} \]
703 Postačí, aby existovalo
713 \begin_inset Formula $s<1$
716 takové, že každé ze zobrazení
717 \begin_inset Formula $c_{i}$
721 \begin_inset Formula $a_{i}:\;\left|a_{i}\right|\le s$
725 Pak pro libovolné obrázky
726 \begin_inset Formula $g_{1},g_{2}:I^{2}\rightarrow I$
730 \begin_inset Formula $\vec{z}\in I^{2}$
734 \begin_inset Formula $R_{i}$
738 \begin_inset Formula $\vec{z}\in R_{i}$
742 \begin_inset Formula \[
743 \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)\]
747 Z toho už plyne kontraktivita celého operátoru
748 \begin_inset Formula $F$
752 \begin_inset Formula \[
753 d_{s\mathrm{up}}\left(Fg_{1},Fg_{2}\right)\;\le\; s\, d_{s\mathrm{up}}\left(g_{1},g_{2}\right)\]
757 a díky tomu lze použít kolážovou větu.
760 \begin_layout Standard
761 Ukazuje se ale, že pro použití v
765 implementaci je tento odhad příliš volný, stejně jako použitá metrika nedává
766 dobré vizuální výsledky.
769 \begin_layout Subsection
771 \begin_inset CommandInset label
773 name "PIFS/Optimální_zobrazení"
780 \begin_layout Standard
791 \begin_inset Formula $R_{i}$
794 se volí afinní zobrazení
795 \begin_inset Formula $w_{i}$
798 tak, aby mapovalo blok na jeden ze souboru zdrojových bloků.
799 Tento soubor bývá pevně daný kvůli zjednodušení ukládání a vyhledávání.
800 Volba zdrojového bloku je hlavním zdrojem výpočetní složitosti celé komprese
801 a jejímu urychlení byla věnována značná část výzkumu v
806 Obecně je snaha zvolit takový blok
807 \begin_inset Formula $D_{i}$
814 optimálním barevným zobrazením
815 \begin_inset Formula $c_{i}$
818 bude pro složený operátor
819 \begin_inset Formula $F_{i}g=\left(c_{i}\circ g\circ w_{i}\right)$
823 \begin_inset Formula $d\left(\ c_{i}\circ g\circ w_{i},\ g\ \right)$
845 \begin_inset Formula $R_{i}$
849 \begin_inset Note Note
852 \begin_layout Plain Layout
862 vysvětlit měření na části
870 \begin_layout Standard
871 Volba optimálního zobrazení
872 \begin_inset Formula $c_{i}$
875 a tedy i následně volba
876 \begin_inset Formula $w_{i}$
879 je silně závislá na použité metrice.
880 Ve fraktální kompresi se téměř výhradně používá RMSE metrika.
881 Její hlavní výhody i nevýhody jsou dány tím, že se vždy berou v
885 úvahu pouze sobě odpovídající body.
886 To umožnuje velmi jednoduchou a rychlou práci s
890 metrikou a také optimalizaci v
894 ní, na druhou stranu díky tomu pro větší bloky nedává metrika výsledky odpovídaj
895 ící vizuálnímu rozdílu.
896 Možnosti použití alternativních metrik jsou zmíněny v
901 \begin_inset CommandInset ref
903 reference "Články/Zlepšení_vzhledu/Další_metody"
910 \begin_layout Standard
920 \begin_inset CommandInset ref
922 reference "Chyba_zobrazení"
926 pro diskrétní případ, při použití RMSE existuje právě jedno optimální
927 \begin_inset Formula $c_{i}$
931 \begin_inset Formula $g$
935 \begin_inset Formula $w_{i}$
938 ) snadno spočítat analyticky.
939 To platí za předpokladu, že
940 \begin_inset Formula $g\circ w_{i}$
944 \begin_inset Formula $R_{i}$
952 \begin_inset Formula $g$
956 \begin_inset Formula $D_{i}$
963 --- jinak by se jednalo o
967 aproximaci konstantním blokem, volba lineárního koeficientu by byla libovolná
968 a výsledek vždy horší, než při výběru jakéhokoliv nekonstantního zdrojového
972 \begin_layout Subsection
974 \begin_inset CommandInset label
976 name "PIFS/Rychlá_konvergence"
983 \begin_layout Standard
988 této podobě stále trpěla jedním skrytým problémem.
989 Při dodržení kontraktivity všech zobrazení
990 \begin_inset Formula $c_{i}$
993 kolážová věta sice zaručovala, že obrázek zkonverguje (v
997 prostoru všech obrázků s
1001 libovolnou metrikou) a nebude se příliš lišit, ale nijak neomezovala počet
1002 nutných iteračních kroků.
1003 Ukázalo se, že tento problém není jen teoretický
1004 \begin_inset space ~
1008 \begin_inset space ~
1011 při přísnějších omezeních na kontraktivitu bylo pro některé obrázky nutné
1012 provádět mnoho desítek iterací než změny přestaly být okem viditelné.
1015 \begin_layout Standard
1016 Řešení tohoto problému bylo publikováno v
1017 \begin_inset space ~
1021 \begin_inset CommandInset citation
1027 a podrobněji rozebráno v
1028 \begin_inset space ~
1032 \begin_inset space ~
1036 \begin_inset space ~
1040 \begin_inset CommandInset citation
1048 \begin_inset space ~
1051 drobnou modifikaci barevného zobrazení.
1052 Pokud bylo původní optimální barevné zobrazení ve tvaru
1053 \begin_inset Formula $c_{i}\left(z\right)=p_{i}\, z+q_{i}$
1056 , pak místo ukládání
1057 \begin_inset Formula $p_{i}$
1061 \begin_inset Formula $q_{i}$
1065 \begin_inset Formula $p_{i}$
1068 a průměrná barva bloku
1069 \begin_inset Formula $R_{i}$
1074 \begin_inset Formula $\tilde{c_{i}}$
1077 pak znormalizuje barvu zdrojového bloku
1078 \begin_inset Formula $D_{i}$
1081 odečtením jeho aktuálního průměru, výsledek vynásobí lineárním koeficienem
1083 \begin_inset Formula $p_{i}$
1086 a přičte předpočítanou průměrnou barvu bloku
1087 \begin_inset Formula $R_{i}$
1090 ve vstupním obrázku.
1093 \begin_layout Standard
1094 Přestože přičítaná průměrná barva
1095 \begin_inset Formula $R_{i}$
1099 \begin_inset space ~
1102 charakteristice zobrazení a je stále stejná, skutečný konstantní koeficient
1104 \begin_inset Formula $q_{i}$
1108 \begin_inset space ~
1111 každou iterací, takže z
1112 \begin_inset space ~
1115 matematického hlediska se
1116 \begin_inset Formula $\tilde{c_{i}}$
1119 chová pokaždé jako jiné zobrazení.
1122 \begin_layout Standard
1124 \begin_inset space ~
1127 rámci jedné iterace je ale
1128 \begin_inset Formula $\tilde{c_{i}}$
1131 stále afinní zobrazení.
1132 Navíc lze snadno ukázat, že při použití RMSE metriky optimální afinní zobrazení
1134 \begin_inset Formula $c_{i}$
1137 také vždy zobrazuje průměnou barvu
1138 \begin_inset Formula $D_{i}$
1142 \begin_inset Formula $R_{i}$
1145 , takže když stav obrázku při iterování konverguje k
1146 \begin_inset space ~
1150 \begin_inset Formula $g$
1153 (zdrojovému obrázku), pak i
1154 \begin_inset space ~
1158 \begin_inset Formula $\tilde{c_{i}}$
1162 \begin_inset space ~
1166 \begin_inset Formula $c_{i}$
1173 \begin_layout Standard
1174 V tomto přístupu je tedy iterační operátor složitější na vyhodnocení, ale
1175 má lepší vlastnosti, například efektivnější ukládání koeficientů zobrazení
1176 díky jejich menší korelaci.
1178 \begin_inset Formula $q_{i}$
1182 \begin_inset Formula $c_{i}$
1186 \begin_inset space ~
1189 absolutní hodnotě malá čísla, ale mohly se pohybovat ve velkém rozsahu.
1190 Průměrná barva bloku se může pohybovat jen v
1191 \begin_inset space ~
1195 \begin_inset Formula $\left[0,1\right]$
1198 a má jasnější význam
1199 \begin_inset space ~
1202 --- to pomáhá při volbě způsobu kvantizace při uložení do souboru a umožnuje
1203 například využít toho, že sousední bloky budou mít pravděpodobně blízkou
1207 \begin_layout Standard
1208 Další výhodou je mnohem rychlejší a jistější konvergence.
1209 Je vidět, že po každé iteraci mají všechny bloky
1210 \begin_inset Formula $R_{i}$
1213 správnou průměrnou barvu.
1214 Tím se vzhled zdrojových bloků
1215 \begin_inset Formula $D_{i}$
1218 už po první iteraci dostane blízko vzorovému obrázku, což se při další
1219 iteraci promítne do cílových bloků
1220 \begin_inset Formula $R_{i}$
1226 \begin_layout Standard
1228 \begin_inset space ~
1231 výše odkazovaných publikacích je ukázáno, že po takovéto úpravě barevných
1232 zobrazení iterační proces konverguje ke stejnému výsledku a také, že za
1233 trochu silnějších předpokladů než zde uvedené bude potřebný počet iterací
1234 malý a bude záviset pouze na velikostech zdrojových a cílových bloků.
1235 Používá se zde diskrétní model obrázku
1236 \begin_inset space ~
1239 --- posloupnost reálných čísel, kde cílové bloky jsou tvořeny
1240 \begin_inset Formula $2^{b_{i}}$
1243 po sobě jdoucími hodnotami a zdrojové bloky o
1244 \begin_inset space ~
1248 \begin_inset Formula $2^{d_{i}}$
1251 jsou tvořeny několika po sobě jdoucími cílovými bloky.
1252 Zmenšování bloků vždy probíhá zprůměrováním
1253 \begin_inset Formula $2^{d_{i}-b_{i}}$
1256 po sobě jdoucích hodnot.
1259 \begin_layout Standard
1260 Na rozdíl od konvergence založené na kolážové větě je důkaz proveden bez
1261 jakéhokoliv omezení na kontraktivitu barevných zobrazení
1262 \begin_inset Formula $\bar{c_{i}}$
1265 , což umožnuje mnohem přesnější aproximaci bloků s
1266 \begin_inset space ~
1269 ostrými přechody bez ztráty jistoty konvergence.
1270 Zde se naopak využívá kontraktivity transformací
1271 \begin_inset Formula $w_{i}$
1277 \begin_layout Subsection
1278 Úprava lineárních koeficientů
1279 \begin_inset CommandInset label
1281 name "PIFS/Použitý_model"
1288 \begin_layout Standard
1289 Podobným způsobem, jako byly konstantní koeficienty barevných zobrazení
1290 nahrazeny průměry, lze také lineární koeficienty nahradit směrodatnými
1292 \begin_inset space ~
1295 --- barvy zdrojových bloků jsou vyděleny svou směrodatnou odchylkou a vynásobeny
1296 cílovou směrodatnou odchylkou.
1298 \begin_inset space ~
1302 \begin_inset space ~
1306 \begin_inset CommandInset ref
1308 reference "Chyba_zobrazení/Upravená"
1312 , mírně se tím zvýší chyba optimálního zobrazení.
1315 \begin_layout Standard
1316 Výhody a nevýhody tohoto přístupu jsou podobné jako při nahrazování konstantních
1317 koeficientů zobrazení
1318 \begin_inset space ~
1321 --- především jednodušší reprezentace zobrazení a pravděpodobně také rychlejší
1325 \begin_layout Standard
1327 \begin_inset space ~
1331 \begin_inset space ~
1335 \begin_inset CommandInset citation
1342 \begin_inset space ~
1345 této práci je používán právě tento model barevných zobrazení, ale nikde
1346 se mi nepodařilo nalézt nějaké zdůvodnění nebo odkaz na text zabývající
1347 se jeho vlastnostmi.
1348 Nejsou mi tedy známy žádné výsledky týkající se konvergence ani pro případné
1352 \begin_layout Standard
1353 Lineární koeficienty barevných zobrazení nejsou stejně jako v
1354 \begin_inset space ~
1357 předchozím modelu nijak omezeny, ale experimenty prováděné v
1358 \begin_inset space ~
1361 rámci této práce ukazují, že může být výhodné vyhýbat se zobrazením, kde
1362 je absolutní hodnota lineárního koeficientu vysoká.
1363 Tato úprava je diskutována v
1364 \begin_inset space ~
1368 \begin_inset CommandInset ref
1370 reference "Chyba_zobrazení/Penalizace"
1374 , včetně teoretického zdůvodnění.
1377 \begin_layout Section
1378 Nejčastější oblasti výzkumu
1381 \begin_layout Standard
1383 \begin_inset space ~
1387 \begin_inset space \thinspace{}
1390 let bylo věnováno fraktální kompresi velké úsilí.
1391 Bylo zkoumáno (většinou odděleně) mnoho odlišných způsobů vylepšení základních
1392 technik popsaných výše.
1394 \begin_inset space ~
1397 této části jsou shrnuty nejvýznamnější výsledky a zajímavé návrhy pro další
1399 Pro přehlednost jsou rozčleněny podle toho, na které aspekty komprese se
1403 \begin_layout Subsection
1405 \begin_inset CommandInset label
1407 name "Články/Zrychlení"
1414 \begin_layout Standard
1415 Za největší problém byla považována obrovská výpočetní náročnost hledání
1416 vhodných zdrojových bloků.
1417 Od dob nejintenzivnějšího výzkumu v
1418 \begin_inset space ~
1421 oblasti se sice výkon běžných počítačů mnohonásobně zvýšil, ale stále je
1422 nutné se tímto problémem zabývat.
1424 \begin_inset space ~
1427 důvodů je, že dnes je potřeba zpracovávat mnohem větší množství dat.
1428 Velikosti a množství fotografií roste a také je zkoumána možnost využití
1429 pro kompresi videozáznamů.
1432 \begin_layout Subsubsection
1436 \begin_layout Standard
1437 Nejčastější technikou pro urychlení výběru vhodného zdrojového bloku byly
1438 klasifikační metody.
1439 Všechny cílové a potencionální zdrojové bloky jsou nějakým způsobem ohodnoceny
1440 a poté je vzájemná zobrazitelnost přesně vyhodnocována pouze pro
1441 \begin_inset Quotes gld
1445 \begin_inset Quotes grd
1450 \begin_inset space ~
1453 vynechání některých optimálních zobrazení, ale pokles kvality bývá velmi
1454 malý a urychlení mnohonásobné (zkomprimovaná velikost se nezmění).
1457 \begin_layout Standard
1459 \begin_inset space ~
1462 jednoduché rozdělení bloků do několika tříd a uvažování pouze zobrazení
1463 v rámci jedné třídy, například klasifikace navržené Jacquinem nebo Fisherem
1464 \begin_inset space ~
1468 \begin_inset CommandInset citation
1475 Zde je nevýhodné, že pro bloky
1476 \begin_inset Quotes gld
1480 \begin_inset space ~
1484 \begin_inset Quotes grd
1487 tříd často mohou mít podobné bloky v
1488 \begin_inset space ~
1492 \begin_inset Quotes gld
1496 \begin_inset Quotes grd
1500 To vede ke složitějším metodám, které hledají i v
1501 \begin_inset space ~
1504 příbuzných třídách, nebo používají hierarchické způsoby klasifikace, například
1505 \begin_inset space ~
1509 \begin_inset CommandInset citation
1518 \begin_layout Subsubsection
1519 Převod na hledání nejbližšího bodu
1522 \begin_layout Standard
1523 Problémem klasifikačních metod je, že přes výrazné zrychlení nejsou schopny
1524 zlepšit asymptotickou složitost výpočtu.
1525 Zde se nabízí zobecnění klasifikačních metod, kde by pro blok byl vygenerován
1527 \begin_inset space ~
1530 nějakého prostoru uspořádaného tak, že vzdálenost v
1531 \begin_inset space ~
1534 něm odpovídá míře vzájemné zobrazitelnosti.
1535 Pak by pro každý bod prostoru odpovídající nějakému cílovému bloku stačilo
1537 \begin_inset space ~
1540 množiny bodů prostoru odpovídající zdrojovým blokům.
1541 Hledání nejbližších sousedů je známá úloha, kterou už lze řešit výrazně
1542 rychleji než úměrně se součinem velikostí obou množin.
1545 \begin_layout Standard
1546 Tato možnost byla publikována mezi projekty v
1547 \begin_inset space ~
1551 \begin_inset space ~
1555 \begin_inset CommandInset citation
1561 a podrobněji rozebrána v
1562 \begin_inset space ~
1566 \begin_inset space ~
1570 \begin_inset CommandInset citation
1577 Je zde především dokázáno, že při uvažování klasických afinních zobrazení
1578 pro transformaci barvy mezi bloky je pro pevný cílový blok optimální čtvercová
1579 chyba (SE) rovna určité rostoucí transformaci eukleidovské vzdálenosti
1580 normalizovaných vektorů obou bloků (cílového a zdrojového).
1581 Tedy pro nalezení zdrojového bloku
1582 \begin_inset Quotes gld
1586 \begin_inset Quotes grd
1590 \begin_inset space ~
1593 cílovému stačí jen najít nejbližší bod v
1594 \begin_inset space ~
1597 eukleidovském prostoru.
1600 \begin_layout Standard
1601 Jsou zde různé komplikace
1602 \begin_inset space ~
1605 --- kvůli kvantizaci koeficientů nemusí nejbližší bod být ten nejlepší,
1606 při uvažování i zobrazení se zápornými lineárními koeficienty je nutné
1607 prohledávát strukturu dvakrát (nebo vložit každý bod dvakrát).
1608 Je zde také otázka spotřeby paměti, která sice není tak velkým problémem,
1610 \begin_inset space ~
1613 době publikace metody, ale stále potřeba se jí věnovat.
1614 Dále se problematikou zabýváme v
1615 \begin_inset space ~
1619 \begin_inset space ~
1623 \begin_inset CommandInset ref
1625 reference "Implementace/Predikce"
1632 \begin_layout Subsubsection
1633 Lokální prohledávání
1636 \begin_layout Standard
1637 Za další možnost urychlení se považoval jiný způsob redukce nutných porovnání
1638 \begin_inset space ~
1641 --- přeskočení zdrojových bloků, které jsou v
1642 \begin_inset space ~
1645 obrázku příliš vzdálené od cílového bloku (pro který hledáme zobrazení).
1646 Na rozdíl od klasifikačních metod je množina uvažovaných zdrojových bloků
1648 \begin_inset space ~
1651 polohy cílového bloku, takže lze ušetřit nějaký prostor nutný pro uložení
1652 jejich identifikačních čísel.
1655 \begin_layout Standard
1656 Základem této techniky je domněnka, že ideální zdrojový blok má větší pravděpodo
1657 bnost výskytu blíže k
1658 \begin_inset space ~
1661 danému cílovému bloku.
1663 \begin_inset space ~
1667 \begin_inset space ~
1671 \begin_inset CommandInset citation
1677 je ukázáno, že posun rozdělení vzdáleností optimálních dvojic oproti vzdálenost
1678 em náhodně vybraných dvojic je zanedbatelný.
1679 Zrádné je zde především to, že už jen rozdělení vzdálenosti dvou náhodných
1680 bodů je velmi nerovnoměrné.
1683 \begin_layout Standard
1685 \begin_inset space ~
1688 další nevýhody spojené s
1689 \begin_inset space ~
1692 tím, že je množina uvažovaných zdrojových bloků pro každý cílový blok jiná,
1693 například obtížná kombinace s
1694 \begin_inset space ~
1697 jinými metodami urychlení komprese.
1700 \begin_layout Standard
1701 Na druhou stranu například v
1702 \begin_inset space ~
1706 \begin_inset space ~
1710 \begin_inset CommandInset citation
1716 je zkoumána závislost podobnosti dvou cílových bloků na jejich vzdálenosti
1718 \begin_inset space ~
1721 opačnými výsledky na stejném obrázku (Lenna).
1722 To je pravděpodobně způsobeno tím, že při hledání podobnosti mezi zdrojovým
1723 a cílovým blokem vždy dochází ke zmenšování, zatímco blízké cílové bloky
1724 často mívají stejnou velikost.
1727 \begin_layout Standard
1728 Této podobnosti je zde využito nejen pro urychlení hledání zdrojového bloku
1729 tím, že jsou nejprve vyzkoušeny zdrojové bloky blízkých cílových bloků,
1730 ale hlavně ke zvýšení kompresního poměru.
1731 Místo ukládání identifikačního čísla zdrojového bloku stačí uložit relativní
1732 pozici nejbližšího cílového bloku se stejným zdrojovým blokem.
1734 \begin_inset space ~
1737 tomu, že cílových bloků bývá mnohem méně než zdrojových a podobné cílové
1738 bloky se často vyskytují blízko, lze takto ušetřit mnoho bitů ve výstupu
1739 za cenu minimálního poklesu kvality.
1742 \begin_layout Subsubsection
1743 Přerušení prohledávání
1746 \begin_layout Standard
1747 Další metoda snížení počtu nutných porovnání je nehledat nejlepší zdrojový
1748 blok a spokojit se s
1749 \begin_inset space ~
1752 dostatečně dobrým už nalezeným blokem.
1753 Dosažené zrychlení ale nejspíš nebude nijak veliké.
1754 Nejsou mi známy žádné práce, které by se podrobněji zabývaly touto technikou.
1757 \begin_layout Subsection
1761 \begin_layout Standard
1762 Vetšinou nezávisle na rychlosti komprese byly zkoumány také metody zlep\SpecialChar \-
1765 kvalitu dekomprimovaných obrázků.
1766 Zde jsou zařazeny i techniky zvyšující kompresní poměr, protože jde o
1767 \begin_inset space ~
1771 \begin_inset space ~
1774 --- typicky lze pouhým nastavováním parametrů komprese zlepšovat jeden z
1775 \begin_inset space ~
1778 těchto ukazatelů na úkor druhého.
1781 \begin_layout Subsubsection
1782 Dělení na cílové bloky
1785 \begin_layout Standard
1786 Jedním ze základních faktorů ovlivňujících vzhled je způsob dělení obrázku
1788 Nejjednodušší je určit dělení napevno.
1790 \begin_inset space ~
1793 praxi nepoužitelné kvůli obtížné regulaci kvality a kompresního poměru.
1794 Navíc nalézt dobré zobrazení pro skoro konstatní bloky je velmi jednoduché,
1795 zatímco pro bloky obsahující hodně detailů nejspíš žádný vhodný zdrojový
1797 \begin_inset space ~
1801 Proto bylo nutné hledat adaptivní metody, které by v
1802 \begin_inset space ~
1806 \begin_inset Quotes gld
1810 \begin_inset Quotes grd
1813 místech nechávaly velké bloky a v
1814 \begin_inset space ~
1817 místech se složitější kresbou mohly dělit obrázek na menší a zvyšovat u
1818 \begin_inset space ~
1821 nich tak pravděpodobnost nalezení dostatečně dobrého zobrazení.
1824 \begin_layout Standard
1825 \begin_inset VSpace defskip
1831 \begin_layout Standard
1832 Jednoznačně nejpoužívanější metodou je dělení pomocí čtyřstromu (Quadtree),
1833 popsaného například v
1834 \begin_inset space ~
1838 \begin_inset CommandInset citation
1845 Pro zjednodušení se uvažují jako velikosti obrázku a bloků jen čtverce
1847 \begin_inset space ~
1850 hranách délky mocniny 2.
1852 \begin_inset space ~
1855 jedním velkým cílovým blokem pokrývajícím celý obrázek a postupuje se tak,
1856 že se vždy vezme nějaký cílový blok a najde se pro něj nejlepší zobrazení.
1857 Pokud je chyba dostatečně malá, je zobrazení použito, jinak je blok rozdělen
1859 \begin_inset space ~
1862 poloviční velikosti, pro které se použije stejný postup.
1865 \begin_layout Standard
1866 Tento způsob dělení je celkem efektivní a také jednoduchý na implementaci,
1867 včetně velmi úsporného uložení tvaru čtyřstromu.
1869 \begin_inset space ~
1872 praxi je potřeba čtyřstrom zobecnit i pro jiné velikosti obrázku a jsou
1873 vhodná i další vylepšení.
1874 Podrobněji je dělení čtyřstromem rozebráno v
1875 \begin_inset space ~
1879 \begin_inset space ~
1883 \begin_inset CommandInset ref
1885 reference "Implementace/MQuadTree"
1892 \begin_layout Standard
1894 \begin_inset space ~
1897 nevýhod čtyřstromu je, že skoky mezi jednotlivými velikostmi bloků jsou
1898 relativně velké, takže v
1899 \begin_inset space ~
1902 některých případech dochází k
1903 \begin_inset space ~
1906 dělení na zbytečně malé bloky.
1907 Tento problém je řešen v
1908 \begin_inset space ~
1912 \begin_inset CommandInset citation
1918 pomocí přidání jednoho mezikroku, což sice vede k
1919 \begin_inset space ~
1922 delšímu výpočtu, ale také mírně zlepšuje kvalitu komprimovaných obrázků.
1925 \begin_layout Standard
1926 \begin_inset VSpace defskip
1932 \begin_layout Standard
1933 Zobecněním dělení čtyřstromem je HV (horizontálně-vertikální) dělení, popsané
1935 \begin_inset space \thinspace{}
1939 \begin_inset space ~
1943 \begin_inset CommandInset citation
1950 Základní myšlenka je stejná jako u
1951 \begin_inset space ~
1956 mů, akorát umožňuje dělit obecné obdelníkové bloky na dva menší
1957 podle libovolné svislé nebo vodorovné přímky.
1960 \begin_layout Standard
1962 \begin_inset space ~
1965 menším skokům mezi velikostmi bloků, ale hlavní výhoda je ve vyšší adaptivitě.
1967 \begin_inset space ~
1971 \begin_inset CommandInset citation
1977 je navržena heuristická metoda, která vybírá místo dělení nejčastěji těsně
1979 \begin_inset space ~
1982 silných barevných zlomů a zároveň se vyhýbá blokům s
1983 \begin_inset space ~
1986 příliš velkým poměrem délek stran.
1987 To zvyšuje pravděpodobnost nalezení vhodného zdrojového bloku a vyvažuje
1988 tak větší složitost uložení struktury rozdělení obrázku.
1991 \begin_layout Standard
1992 Podle autorů dává metoda o
1993 \begin_inset space ~
1996 něco lepší výsledky než klasický čtyřstrom, ale komplikuje ostatní fáze
1998 Protože cílové bloky mohou mít libovolné obdelníkové tvary, je mnohem těžší
1999 použití klasifikačních a jiných urychlujících metod.
2002 \begin_layout Standard
2003 \begin_inset VSpace defskip
2009 \begin_layout Standard
2010 Další typy dělení zmiňované v
2011 \begin_inset space ~
2015 \begin_inset CommandInset citation
2021 , například trojúhelníkové, polygonální, nebo šestiúhelníkové
2025 \begin_layout Plain Layout
2026 toto dělení na rozdíl od šestiúhelníkové architektury zmíněné níže pracuje
2028 \begin_inset space ~
2031 klasickými čtvercovými pixely, jen zdrojové bloky mají přibližně tvar šestiúheln
2037 jsou velmi komplikované na implementaci a pravděpodobně by nepřinesly významné
2039 Mezi jejich předpokládané výhody ale patří méně
2040 \begin_inset Quotes gld
2044 \begin_inset Quotes grd
2047 vhled způsobený dělením podle šikmých nebo různě orientovaných hran, případně
2048 mírným překryvem pixelů na krajích bloků.
2051 \begin_layout Standard
2052 \begin_inset VSpace defskip
2058 \begin_layout Standard
2059 Dělení na nezávisle zobrazované bloky vytváří rušivou strukturu, jejíž redukcí
2060 je možné výrazně zlepšit subjektivní vzhled a někdy i PSNR komprimovaného
2062 Problémem je vysoká citlivost lidského na hrany, obzvláště horizontálně
2063 a vertikálně orientované.
2064 Pro potlačení této struktury lze dělat zásahy na dvou různých místech celého
2065 kompresního procesu.
2068 \begin_layout Standard
2069 Nejjednodušší možnost je věnovat se tomuto problému až při dekódování.
2070 Hranice bloků jsou vždy známé, takže je možné vyhlazovat výsledný obrázek
2071 jen na jejich okrajích.
2072 Vizuálního zlepšení lze dosáhnout už použitím jednoduchých nebo vážených
2074 \begin_inset space ~
2078 \begin_inset CommandInset citation
2086 \begin_inset space ~
2089 vyšším kompresním poměrem a také u jednotlivých větších cílových bloků je
2090 větší potřeba vyhlazování a obvykle dojde i ke zvýšení PSNR, ale naopak
2091 při nastavení vysoké kvality po vyhlazování PSNR klesne (přestože obrázek
2093 \begin_inset Quotes gld
2097 \begin_inset Quotes grd
2103 \begin_layout Standard
2104 Další možností je snažit se redukovat tyto přechody už při kompresi.
2105 Zde mi nejsou známy žádné publikované výsledky kromě návrhů způsobů řešení.
2106 Lze vážit chybu na okrajích cílových bloků více než chybu uvnitř, případně
2107 použít dělení na překrývající se bloky a při dekódování hodnoty na překryvu
2111 \begin_layout Subsubsection
2115 \begin_layout Standard
2116 Dalším faktorem ovlivňujícím vzhled je volba souboru zdrojových bloků.
2117 Důležitý je především počet bloků v
2118 \begin_inset space ~
2122 Zvýšení počtu sice vede k
2123 \begin_inset space ~
2126 potřebě většího prostoru na uložení identifikačních čísel zdrojových bloků,
2127 ale také zvyšuje pravděpodobnost nalezení vhodného bloku, takže lze při
2128 stejné kvalitě použít rozdělení obrázku na menší počet větších cílových
2132 \begin_layout Standard
2133 Výsledky testování (například v
2134 \begin_inset space ~
2138 \begin_inset CommandInset citation
2144 ) ukazují, že zvyšování množství zdrojových bloků typicky vede ke zlepšení
2146 Nevýhodou je vyšší výpočetní náročnost.
2147 Zde se ukazuje spojitost se zrychlením komprese
2148 \begin_inset space ~
2151 --- při vyšší rychlosti by bylo únosné prohledat větší soubor bloků a zlepšit
2152 tak kvalitu (případně kompresní poměr).
2155 \begin_layout Standard
2156 \begin_inset VSpace defskip
2162 \begin_layout Standard
2163 Kromě množství zdrojových bloků je potřeba rozhodnout, jak zdrojové bloky
2165 Základní podmínkou je, že musí být větší než příslušné cílové bloky, aby
2166 byla prostorová část zobrazení kontraktivní.
2167 Ekvivalentně lze uvažovat výběr zdrojových bloků stejně velkých jako příslušné
2169 \begin_inset space ~
2172 nějaké zmenšeniny původního obrázku.
2173 To je díky své obecnosti někdy výhodné i pro implementaci (využito také
2175 \begin_inset space ~
2181 \begin_layout Standard
2182 Samotné zmenšování lze provádět mnoha různými způsoby.
2183 Kvůli jednoduché implementaci se nejčastěji používá především zmenšování
2185 \begin_inset space ~
2188 obou rozměrech na polovinu (průměrováním hodnot po čtveřicích) a navíc se
2189 uvažuje všech osm transformací čtverce složených ze
2190 \begin_inset space ~
2193 symetrií a otáčení o
2194 \begin_inset space ~
2198 \begin_inset Formula $90^{\circ}$
2203 \begin_inset space ~
2207 \begin_inset CommandInset citation
2213 je navíc zkoumáno použití zmenšování s
2214 \begin_inset space ~
2217 kontraktivitou rozdílnou pro obě osy nebo s
2218 \begin_inset space ~
2222 \begin_inset space ~
2226 \begin_inset Formula $45^{\circ}$
2230 \begin_inset space ~
2234 Tyto myšlenky byly také využity při implementaci (část
2235 \begin_inset space ~
2239 \begin_inset CommandInset ref
2241 reference "Implementace/Domény"
2248 \begin_layout Standard
2250 \begin_inset space ~
2254 \begin_inset CommandInset citation
2260 přidávání osmi transformací čtverce nijak nezlepšuje kvalitu, ale může
2261 sloužit spíše jako způsob zvětšování počtu zdrojových bloků.
2263 \begin_inset space ~
2266 takto zvětšeném souboru bloků je často pak možné dosáhnout úspory paměti
2267 a zrychlení oproti jiným způsobům zvětšování souboru.
2270 \begin_layout Subsubsection
2271 Šestiúhelníková architektura
2274 \begin_layout Standard
2276 \begin_inset space ~
2279 poslední době je zkoumáno také pojetí obrázku jako bodů uspořádaných do
2280 šestiúhelníkové mříže místo čtvercové.
2281 Tato architektura mnohem lépe odpovídá rozložení tyčinek a čípků na sítnici
2283 \begin_inset space ~
2286 přirozené redukci horizontálních a vertikálních artefaktů.
2287 Další výhodou je větší množství přirozených rotací na mříži.
2288 \begin_inset VSpace defskip
2294 \begin_layout Standard
2295 Protože běžné formáty obrázků podporují pouze obdélníkový tvar se
2296 \begin_inset space ~
2299 čtvercovými body, je potřeba nejprve stanovit způsob převodu mezi mřížemi.
2300 Objevují se dva různé přístupy.
2301 První možnost je představit si čtvercovou mříž o
2302 \begin_inset space ~
2306 \begin_inset Formula $60^{\circ}$
2309 zkosenou, tím se středy pixelů dostanou právě do pravidelné šestiúhelníkové
2310 mříže a je možné je převádět
2311 \begin_inset Formula $1:1$
2315 \begin_inset space ~
2319 \begin_inset CommandInset citation
2326 Druhou možností je body přepočítat pomocí váženého průměrování, například
2328 \begin_inset space ~
2332 \begin_inset CommandInset citation
2341 \begin_layout Standard
2342 Výhoda prvního přístupu oproti druhému je, že zobrazuje právě jeden čtvercový
2343 pixel na jeden šestiúhelníkový, takže nedochází k žádnému rozmazávání.
2344 Na druhou stranu se v
2345 \begin_inset space ~
2348 podstatě pracuje se zkoseným obrázkem, takže interpretace vzdáleností bude
2350 \begin_inset space ~
2353 různých směrech různě změněna, což může vést k
2354 \begin_inset space ~
2357 nerovnoměrným projevům zkreslení způsobeného kompresí.
2360 \begin_layout Standard
2361 \begin_inset VSpace defskip
2367 \begin_layout Standard
2368 Změna architektury také přináší mnoho otázek a implementačních problémů.
2369 Po libovolném převodu obdélníkového obrázku budou v
2370 \begin_inset space ~
2373 šestiúhelníkové mříži
2374 \begin_inset Quotes gld
2378 \begin_inset Quotes grd
2381 neobvyklých tvarů nebo nepravidelné okraje a už samotný způsob reprezentace
2383 \begin_inset space ~
2386 paměti je netriviální.
2387 Ve zmíněných článcích jsou tyto potíže řešeny kompresí pouze části obrázku
2389 \begin_inset space ~
2392 vhodném tvaru, ale ani tak zde dosažené výsledky nejsou přesvědčivé.
2395 \begin_layout Subsubsection
2399 \begin_layout Standard
2400 Ve většině případů je fraktální komprese zkoumána pouze na obrázcích ve
2402 \begin_inset space ~
2405 argumentem, že barevné obrázky lze snadno komprimovat jako tři nezávislé
2407 Je ale zřejmé, že RGB není vhodný model pro kompresi obrazu, protože jsou
2408 jeho složky vzájemně silně závislé.
2411 \begin_layout Standard
2412 Nejjednodušší je použít některý z
2413 \begin_inset space ~
2416 barevných prostorů navržených pro tyto účely, například YCbCr nebo L*a*b*
2417 \begin_inset space ~
2421 \begin_inset CommandInset citation
2428 Toto je standardní řešení v
2429 \begin_inset space ~
2432 mnoha jiných metodách komprese obrazu.
2434 \begin_inset space ~
2437 závislosti na použitém modelu může být vhodné navíc upravit nastavení kvality
2438 komprese jednotlivých složek, protože citlivost oka na různé barvy se liší.
2439 Ve formátech založených na standardu JPEG se dokonce u
2440 \begin_inset space ~
2443 barevných složek snižuje rozlišení, ale ve fraktální kompresi je mnohem
2444 výhodnější rozlišení ponechat a snížit kvalitu, protože zde výhody oproti
2446 \begin_inset space ~
2449 kompresním poměrem (experimenty, například v
2450 \begin_inset space ~
2454 \begin_inset space ~
2458 \begin_inset space ~
2462 \begin_inset CommandInset citation
2468 , jasně ukazují, že fraktální komprese nejsnáze překonává JPEG při extrémních
2469 kompresních poměrech).
2472 \begin_layout Standard
2473 Alternativně lze spočítat vlastní barevný prostor pro konkrétní obrázek.
2474 Budeme pro jednoduchost uvažovat jen změnu báze vektorového prostoru, charakter
2475 izovanou maticí velikosti
2476 \begin_inset Formula $3\times3$
2480 \begin_inset space ~
2483 RGB prostoru je prvkem
2484 \begin_inset Formula $\mathbb{R}^{3}$
2488 Zde lze použít metodu zvanou PCA (principal component analysis), známou
2489 také jako KLT (Karhunen–Loève transform).
2490 Metoda nalezne nejlepší ortonormální bázi z
2491 \begin_inset space ~
2494 hlediska soustředění maxima informace (rozptylu) do minima souřadnic.
2495 Transformační matice je dána vlastními vektory kovariační matice a navíc
2496 příslušná vlastní čísla charakterizují důležitost jednotlivých souřadnic.
2500 \begin_layout Plain Layout
2501 PCA samotnou lze použít ke kompresi obázků tak, že se obrázek rozdělí na
2503 \begin_inset space ~
2508 \begin_inset space ~
2511 nich se pracuje jako s
2512 \begin_inset space ~
2516 Po náročném výpočtu pak vznikne transformace, v
2517 \begin_inset space ~
2520 praxi často velmi podobná diskrétní kosinové transformaci.
2528 \begin_layout Standard
2529 Je možné také volit jiné přístupy ke zpracování barev.
2531 \begin_inset space ~
2535 \begin_inset CommandInset citation
2541 je předvedena metoda, která pomocí čtyřstromu dělí barevný obrázek na bloky
2542 (podobně jako při dělení cílových bloků) dokud nejsou barvy v
2543 \begin_inset space ~
2546 blocích dostatečně korelované.
2547 Parametry korelace barev pro každý z
2548 \begin_inset space ~
2551 bloků jsou uloženy a do dalšího kódování postupuje již jen jeden obrázek
2554 \begin_inset space ~
2557 adaptivní kompresi informací o
2558 \begin_inset space ~
2562 \begin_inset space ~
2565 urychlení díky tomu, že se složité metody fraktální komprese použijí jen
2566 na jeden jednobarevný obrázek, přestože většina vnímané informace bude
2568 \begin_inset space ~
2574 \begin_layout Subsubsection
2576 \begin_inset CommandInset label
2578 name "Články/Zlepšení_vzhledu/Další_metody"
2585 \begin_layout Standard
2586 Zde ještě ještě stručně zmíněno několik dalších metod používaných pro zlepšení
2587 vzhledu komprimovaných obrázků.
2590 \begin_layout Standard
2591 Obzvláště při vysokých kompresních poměrech je výhodné počítat chybu zobrazení
2592 ze zdrojových bloků do cílových s
2593 \begin_inset space ~
2596 použitím kvantizovaných parametrů zobrazení místo teoretických optim (tedy
2598 \begin_inset space ~
2601 hodnot dostupných při dekompresi místo hodnot dostupných při kompresi).
2602 Aby šlo metodu použít, je potřeba se omezit jen na některé způsoby kvantizace
2603 a také výpočet této chyby bývá trochu složitější.
2606 \begin_layout Standard
2607 Jak již bylo zmíněno, RMSE metrika pro větší bloky nepopisuje dobře vnímaný
2609 Použití přesnějších metrik bylo zatím věnováno jen velmi málo pozornosti,
2610 především díky jednoduchosti práce s
2611 \begin_inset space ~
2614 RMSE umožnující relativně rychlou implementaci jejího vyhodnocení.
2615 Vhodností jiných metrik pro fraktální kompresi se zabývá například
2616 \begin_inset space ~
2620 \begin_inset CommandInset citation
2629 \begin_layout Standard
2630 PIFS uvažuje afinní zobrazení z
2631 \begin_inset space ~
2634 jednoho zdrojového bloku do jednoho cílového bloku.
2635 To lze zobecnit na hledání zobrazení z
2636 \begin_inset space ~
2639 dvou nebo více zdrojových bloků.
2640 Víceprůchodové komprese, kde se jednoduše kóduje chyba předchozího kroku,
2641 nedávají lepší výsledky.
2642 Přímé hledání zobrazení z
2643 \begin_inset space ~
2646 více zdrojových bloků ke zlepšení kvality výsledku vede, ale množství kombinací
2647 zde roste ještě mnohem rychleji než v
2648 \begin_inset space ~
2651 klasické PIFS kompresi.
2653 \begin_inset space ~
2657 \begin_inset CommandInset citation
2663 je navrženo snižovat složitost pomocí redukce podobných zdrojových bloků
2664 a použití hladového přístupu.
2667 \begin_layout Subsection
2671 \begin_layout Subsubsection
2675 \begin_layout Standard
2676 Fraktální dekomprese bývá považována za velmi rychlou, což je způsobeno
2678 \begin_inset space ~
2683 \begin_inset space ~
2686 skutečnosti se stále vyplatí pracovat na jejím zrychlení.
2687 Při prvních iteracích zobrazení je obrázek složen z
2688 \begin_inset space ~
2691 jednolitých bloků a je tedy zbytečné pracovat v
2692 \begin_inset space ~
2698 \begin_layout Standard
2700 \begin_inset space ~
2704 \begin_inset CommandInset citation
2710 , stačí začít dekompresi na zmenšeném obrázku, kde nejmenší cílové bloky
2711 zabírají jediný pixel, a po každé iteraci zobrazení pak zvětšit obrázek
2712 na dvojnásobek (efektivní především při dělení čtyřstromem).
2714 \begin_inset space ~
2717 plné velikosti pak stačí udělat jen okolo dvou iterací.
2720 \begin_layout Subsubsection
2721 Progresivní dekódování
2724 \begin_layout Standard
2725 Při praktickém využití je důležitá možnost progresivního dekódování obrázků
2726 \begin_inset space ~
2729 --- generování náhledů s
2730 \begin_inset space ~
2733 použitím pouze malé počáteční části souboru.
2734 To je užitečné především na internetových stránkách, nebo při prohlížení
2736 \begin_inset space ~
2739 velkým množstvím fotografií.
2740 Progresivním dekódováním pro klasický PIFS se zabývá
2741 \begin_inset space ~
2745 \begin_inset CommandInset citation
2754 \begin_layout Standard
2755 Při použití modifikací nahrazující konstantní koeficienty barevných zobrazení
2756 průměrnými barvami cílových bloků lze ale postupovat mnohem efektivněji
2757 \begin_inset space ~
2760 --- uložit nejprve způsob rozdělení na bloky (zabere velmi málo místa),
2761 potom průměrné barvy všech cílových bloků a pak až ostatní parametry.
2763 \begin_inset space ~
2766 velmi malé části souboru náhled jen z
2767 \begin_inset space ~
2770 průměrných barev bloků, který může vypadat relativně dobře, obzvláště pokud
2771 se pro zobrazení použijí pokročilé interpolační metody.
2774 \begin_layout Subsection
2775 Využití technik fraktální komprese pro jiné účely
2778 \begin_layout Standard
2779 Fraktální komprese má velmi zajímavé vlastnosti, které lze využít i pro
2780 další, často velmi odlišné, účely.
2781 V této části budou nějdůležitějších z
2782 \begin_inset space ~
2785 nich zmíněny, ale jen velmi stručně a bez odkazů na zdroje.
2788 \begin_layout Standard
2789 Díky možnosti dekódování v
2790 \begin_inset space ~
2793 libovolném rozlišení lze použít fraktální kompresi pro inteligentní zvětšování
2795 Při správném nastavení dává velmi dobré výsledky díky tomu, že zvětšenina
2796 nepůsobí rozmazaným dojmem a ostré hrany jsou výborně zachovány.
2799 \begin_layout Standard
2801 \begin_inset space ~
2804 podobných důvodů lze fraktální kompresi použít i pro čištění obrázků od
2806 Při kontraktivních zobrazeních mezi bloky se totiž šum velmi potlačí a
2807 proto nelze typicky najít zdrojový blok, který by šum v
2808 \begin_inset space ~
2811 cílovém bloku napodobil.
2812 Větší útvary a ostré hrany se naopak většinou podaří mezi zdrojovými bloky
2813 najít, takže zůstanou zachovány.
2816 \begin_layout Standard
2817 Je také zkoumáno přidávání
2818 \begin_inset Quotes gld
2822 \begin_inset Quotes grd
2825 do obrázků pomocí fraktální komprese.
2826 Ty mají velmi zajímavé vlastnosti
2827 \begin_inset space ~
2830 --- nejsou vidět (ale lze je z
2831 \begin_inset space ~
2834 obrázku extrahovat) a jsou velmi odolné proti ořezávání obrázku, JPEG kompresi
2836 \begin_inset space ~
2842 \begin_layout Standard
2843 Dále je diskutována možnost využití technik fraktální komprese pro videonahrávky.
2844 Největší redundance je zde v
2845 \begin_inset space ~
2848 podobnosti mezi po sobě následujícími snímky.
2850 \begin_inset space ~
2853 klasických metodách se používají bloky některých snímků jako predikce stejně
2854 umístěných (případně trochu posunutých) bloků jiných snímků a kóduje se
2856 Stejnou metodu lze využít i při fraktální kompresi, ale nabízí se mnohem
2857 přirozenější rozšíření.
2859 \begin_inset space ~
2862 dvoudimenzionálnímu prostoru pixelů v
2863 \begin_inset space ~
2866 obrázcích přidat třetí dimenzi tvořenou časem.
2867 Potom videozáznam dělený na
2868 \begin_inset Quotes gld
2872 \begin_inset Quotes grd
2875 místo obdélníků lze komprimovat podobným způsobem jako obrázky pomocí zobrazení
2876 mezi trojdimenzionálními bloky.
2877 Zde je zajímavá například možnost dekódování ve vyšším rozlišení
2878 \begin_inset space ~
2881 --- lze tak generovat rozumné mezisnímky, které v
2882 \begin_inset space ~
2885 původní nahrávce nebyly.
2888 \begin_layout Chapter
2889 Chyba zobrazení mezi bloky
2890 \begin_inset CommandInset label
2892 name "Chyba_zobrazení"
2899 \begin_layout Standard
2901 \begin_inset space ~
2904 této kapitole je rozebrána nejdůležitější část komprese
2905 \begin_inset space ~
2908 --- výpočet chyby optimálního zobrazení mezi dvojicí bloků.
2912 \begin_layout Standard
2914 \begin_inset space ~
2917 následujících výpočtech budeme pro zjednodušení pracovat se zdrojovým blokem,
2918 který je už zmenšen na velikost cílového a správně otočen.
2919 Navíc použijeme diskrétní model obrázku, přestože analogická odvození lze
2920 udělat i se spojitým modelem.
2921 Protože zde pracujeme s
2922 \begin_inset space ~
2925 RMSE metrikou, nehraje tvar bloků žádnou roli.
2926 Bloky budou uvažovány jako jednorozměrné vektory hodnot, indexované tak,
2927 aby sobě odpovídající hodnoty zdrojových a cílových bloků měly stejné indexy
2928 (ovlivněno rotacemi).
2930 \begin_inset Formula $i$
2933 -tého pixelu zdrojového a cílového bloku budeme značit
2934 \begin_inset Formula $d_{i}$
2938 \begin_inset Formula $r_{i}$
2942 \begin_inset Formula $i$
2946 \begin_inset space ~
2950 \begin_inset Formula $\left\{ 1,2,\ldots,n\right\} $
2956 \begin_layout Standard
2957 Je potřeba si uvědomit, že zde jsou počítané odchylky mezi původním obrázkem
2958 a jeho obrazem, přestože ve skutečnosti potřebujeme omezit odchylku obrázku
2959 od pevného bodu zobrazení.
2961 \begin_inset space ~
2965 \begin_inset space ~
2969 \begin_inset CommandInset ref
2975 byla diskutována možnost použití kolážové věty, která skutečnou chybu omezuje,
2977 \begin_inset space ~
2980 praxi je nepoužitelná.
2981 Hlavním důvodem je to, že dává příliš volný odhad, který neodpovídá realitě
2982 a také je nepříjemné, že plnění předpokladu kontraktivity barevných zobrazení
2983 výslednou odchylku výrazně zvětšuje.
2986 \begin_layout Section
2990 \begin_layout Standard
2991 Ve fraktální kompresi se používá několik ukazatelů míry odchylky obrázku
2992 od originálu, které jsou vzájemně velmi provázané.
2994 \begin_inset space ~
2998 \begin_inset Formula $e_{i}$
3002 \begin_inset space ~
3005 --- rozdílů hodnot jednotlivých pixelů (uvažujeme jednobarevný obrázek).
3008 \begin_layout Standard
3009 Pro výpočty je velmi vhodná SE (
3013 ) metrika měřící čtvercovou chybu.
3014 \begin_inset Formula \[
3015 \mathrm{SE}=\sum_{i=1}^{n}e_{i}^{2}\]
3019 Někdy se používá její normalizovaná verze, která umožňuje korektní porovnávání
3020 odchylek naměřených na různě velkých obrázcích.
3023 root mean square error
3025 ) je vždy stejný jako rozsah hodnot pixelů.
3027 \begin_inset Formula \[
3028 \mathrm{RMSE}=\sqrt{\frac{\mathrm{SE}}{n}}\]
3032 Pro porovnávání různých metod je vhodnějším měřítkem PSNR kvalita (
3034 peak signal-to-noise ratio
3036 ), protože je nezávislá na rozsahu hodnot pixelů a je v
3037 \begin_inset space ~
3040 logaritmickém měřítku.
3042 \begin_inset space ~
3046 \begin_inset space ~
3049 rozsahu nula až nekonečno, kde nekonečno odpovídá nulové odchylce.
3053 \begin_layout Standard
3054 \begin_inset Formula \[
3055 \mathrm{PSNR}=-20\log_{10}\frac{\mathrm{RMSE}}{M},\mbox{\quad kde hodnoty pixelů jsou z\, rozsahu 0--\ensuremath{M}}.\]
3062 \begin_layout Section
3064 \begin_inset CommandInset label
3066 name "Chyba_zobrazení/Klasická"
3073 \begin_layout Standard
3074 Při klasické fraktální kompresi je chyba zobrazení dána
3075 \begin_inset Formula \[
3076 \mathrm{SE}=\sum_{i=1}^{n}\left(ud_{i}+v-r_{i}\right)^{2},\]
3080 přičemž uvažujeme minimum pro libovolné konstanty
3081 \begin_inset Formula $u$
3085 \begin_inset Formula $v$
3089 Úloha odpovídá lineární regresi používané ve statistice, kde RMSE metrika
3090 dává volbu koeficientů metodou nejmenších čtverců.
3091 Použitím derivací a řešením jednoduché soustavy rovnic
3095 \begin_layout Plain Layout
3097 \begin_inset space ~
3100 sum jsou dále vynechány, protože jsou vždy stejné a zbytečně by výpočty
3116 \begin_inset Formula \begin{eqnarray*}
3117 {\textstyle 2u\sum d_{i}^{2}+2v\sum d_{i}-2\sum r_{i}d_{i}} & = & 0\\
3118 {\textstyle 2u\sum d_{i}+2nv-2\sum r_{i}} & = & 0\end{eqnarray*}
3122 lze spočítat obecné optimální hodnoty koeficientů
3123 \begin_inset Formula \[
3124 \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}}.\]
3128 Jmenovatele jsou nulové právě když má zdrojový blok konstantní barvu, což
3129 je případ, který můžeme vyloučit například proto, že při něm chyba zobrazení
3130 nemůže být lepší než s
3131 \begin_inset space ~
3134 libovoným jiným zdrojovým blokem.
3135 Díky tomu, že matice druhých parciálních derivací
3136 \begin_inset Formula \[
3137 {\displaystyle \left(\begin{array}{cc}
3138 \frac{\partial^{2}\mathrm{SE}}{\partial u^{2}} & \frac{\partial^{2}\mathrm{SE}}{\partial u\,\partial v}\\
3139 \frac{\partial^{2}\mathrm{SE}}{\partial u\,\partial v} & \frac{\partial^{2}\mathrm{SE}}{\partial v^{2}}\end{array}\right)=\left(\begin{array}{cc}
3140 2\sum d_{i}^{2} & 2\sum d_{i}\\
3141 2\sum d_{i} & 2n\end{array}\right)}\]
3145 je pozitivně definitní pro libovolný nekonstantní zdrojový blok, jedná se
3147 \begin_inset space ~
3151 Zpětným dosazením optimálních parametrů do vzorce pro chybu a úpravou získáme
3153 \begin_inset Formula \[
3154 \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}.\]
3158 Pomocí struktur uvedených v
3159 \begin_inset space ~
3163 \begin_inset CommandInset ref
3165 reference "Implementace/Matice"
3169 lze všechny sumy kromě jedné snadno spočítat.
3171 \begin_inset Formula $\sum r_{i}d_{i}$
3174 je nutné vyčíslit pro každou uvažovanou dvojici bloků zvlášť.
3177 \begin_layout Section
3178 Chyba upravených zobrazení
3179 \begin_inset CommandInset label
3181 name "Chyba_zobrazení/Upravená"
3188 \begin_layout Standard
3190 \begin_inset space ~
3193 implementaci je použita úprava klasického modelu popsaná v
3194 \begin_inset space ~
3198 \begin_inset CommandInset ref
3200 reference "PIFS/Použitý_model"
3204 , kde místo koeficientů
3205 \begin_inset Formula $u$
3209 \begin_inset Formula $v$
3212 je uložena průměrná hodnota a směrodatná odchylka hodnot cílového bloku.
3213 Koeficienty zobrazení jsou pak počítány v
3214 \begin_inset space ~
3218 \begin_inset space ~
3221 těchto uložených hodnot a ze stavu zdrojového bloku v
3222 \begin_inset space ~
3226 Nová definice koeficientů je
3227 \begin_inset Formula \[
3228 \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},\]
3233 \begin_inset Formula $\bar{d_{i}}$
3236 je značení pro hodnotu pixelu zdrojového bloku z
3237 \begin_inset space ~
3243 \begin_layout Standard
3244 Tím je ovlivněna i optimální chyba zobrazení, protože ani za předpokladu
3245 zobrazování původního obrázku se nemusí
3246 \begin_inset Formula $\bar{u}$
3250 \begin_inset Formula $u$
3254 Pro následující odvození bude použito statistické značení, které je zde
3258 \begin_layout Description
3260 \begin_inset space ~
3264 \begin_inset space ~
3268 \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]}}$
3274 \begin_layout Description
3276 \begin_inset space ~
3280 \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)}$
3286 \begin_layout Description
3288 \begin_inset space ~
3292 \begin_inset Formula ${\displaystyle \rho_{d,r}=\frac{q_{d,r}}{s_{d}s_{r}}}$
3298 \begin_layout Description
3299 konvergence frázemi typu
3300 \begin_inset Quotes gld
3306 \begin_inset Formula $a\rightarrow b$
3310 \begin_inset Formula $c\rightarrow d$
3316 \begin_inset Quotes grd
3320 \begin_inset Formula ${\displaystyle \lim_{a\rightarrow b}c=d}$
3326 \begin_layout Standard
3336 Optimální lineární koeficient
3346 \begin_inset Formula ${\displaystyle u=\frac{q_{d,r}}{s_{d}^{2}}}$
3349 bude nahrazen koeficientem
3350 \begin_inset Formula ${\displaystyle \bar{u}=\pm\frac{s_{r}}{s_{\bar{d}}}}$
3354 Pokud povolíme zobrazení se záporným lineárním koeficientem, je nutné také
3355 uložit znaménko (zde značeno symbolem
3356 \begin_inset Formula $\pm$
3360 Při implementaci je navíc potřeba ošetřit situaci, kdy
3361 \begin_inset Formula $s_{\bar{d}}=0$
3364 , což nastává hlavně při první iteraci pro typický případ inicializace celého
3365 obrázku šedivou barvou.
3368 \begin_layout Standard
3379 \begin_inset Formula $s_{\bar{d}}\rightarrow s_{d}$
3382 (platí speciálně když
3383 \begin_inset Formula $\bar{d}\rightarrow d$
3387 \begin_inset Formula \[
3388 {\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}.\]
3392 Pokud byla chyba barevného zobrazení s
3393 \begin_inset space ~
3397 \begin_inset Formula $u$
3401 \begin_inset space ~
3405 \begin_inset Formula $\rho_{d,r}\rightarrow\pm1$
3410 \begin_inset Formula $u$
3413 je stejné jako znaménko
3414 \begin_inset Formula $\rho_{d,r}$
3418 \begin_inset Formula $\bar{u}\rightarrow u$
3423 \begin_inset space ~
3426 toho je zřejmé, že cílový obrázek bude pevným bodem i takto pozměněného
3428 \begin_inset VSpace bigskip
3434 \begin_layout Standard
3435 Novou čtvercovou chybu lze vyjádřit jako
3436 \begin_inset Formula \begin{equation}
3437 \mathrm{\overline{SE}}\;=\;\sum_{i=1}^{n}\left(\bar{u}\bar{d}_{i}+\bar{v}\right)^{2}.\label{eq:vzorec}\end{equation}
3441 Po postupném dosazení
3442 \begin_inset Formula $\bar{v}=\frac{1}{n}\sum r_{i}-\frac{\bar{u}}{n}\sum\bar{d}_{i}$
3446 \begin_inset Formula ${\displaystyle \bar{u}=\pm\frac{s_{r}}{s_{\bar{d}}}}$
3450 \begin_inset Formula \begin{multline*}
3451 \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}\;=\\
3452 =\;{\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}\;=}\\
3453 {\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*}
3458 \begin_inset Formula $q_{\bar{d},r}$
3461 má vždy stejné znaménko jako
3462 \begin_inset Formula $\bar{u}$
3465 , lze výraz upravit na
3466 \begin_inset Formula \[
3467 \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).\]
3472 \begin_inset VSpace bigskip
3478 \begin_layout Standard
3479 Původní optimální čtvercovou chybu lze přepsat do tvaru:
3482 \begin_layout Standard
3483 \begin_inset Formula \[
3484 \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).\]
3489 \begin_inset Formula $s_{\bar{d}}\rightarrow s_{d}$
3492 , dostaneme absolutní a relativní nárůst chyby
3493 \begin_inset Formula \[
3494 \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}\]
3501 \begin_layout Standard
3502 \begin_inset Formula \[
3503 \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|}\]
3508 \begin_inset VSpace defskip
3511 Pro vzájemně dobře zobrazitelné bloky
3512 \begin_inset Formula $\left|\rho_{d,r}\right|\rightarrow1$
3515 , takže nárůst chyby bude velmi malý.
3518 \begin_layout Section
3519 Penalizace vysokého lineárního koeficientu
3520 \begin_inset CommandInset label
3522 name "Chyba_zobrazení/Penalizace"
3529 \begin_layout Standard
3530 Výše zmíněnou úpravou barevných zobrazení bylo sníženo riziko divergence
3531 zobrazení bez nutnosti omezení lineárního koeficientu.
3532 Díky tomu, že všechny hodnoty jsou omezeny v
3533 \begin_inset space ~
3537 \begin_inset Formula $\left\langle 0,1\right\rangle $
3540 a cílové bloky mají vždy správnou průměrnou hodnotu, nemohou se obrazy
3541 zobrazení od původního obrázku příliš lišit (v
3542 \begin_inset space ~
3545 praxi funguje dobře, ale bez jakéhokoliv důkazu omezení odchylky).
3548 \begin_layout Standard
3549 Přesto jsou vysoké lineární koeficienty nebezpečné, protože zdrojové bloky
3550 jsou při dekódování vždy pouze aproximací jejich stavu v
3551 \begin_inset space ~
3555 Čím vyšší je lineární koeficient, tím více se případná odchylka zdrojového
3556 bloku distribuuje do cílového a poté případně v
3557 \begin_inset space ~
3560 dalších iteracích i do jiných zdrojových bloků.
3563 \begin_layout Standard
3564 Proto je zde navržena následující penalizace, která zvyšuje odhadovanou
3566 \begin_inset space ~
3569 závislosti na jeho lineárním koeficientu.
3570 Pokud vyjdeme ze vzorce pro chybu (
3571 \begin_inset CommandInset ref
3573 reference "eq:vzorec"
3578 \begin_inset space ~
3581 hodnotám zdrojového bloku odchylku
3582 \begin_inset Formula $\epsilon_{i}$
3586 \begin_inset Formula \[
3587 \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].\]
3591 Když označíme původní odchylku
3592 \begin_inset Formula $e_{i}=\bar{u}\bar{d}_{i}+\bar{v}$
3596 \begin_inset Formula \[
3597 \mathrm{\widetilde{SE}}\;=\;{\textstyle \sum}e_{i}^{2}+\bar{u}{\textstyle \sum}e_{i}\epsilon_{i}+\bar{u}^{2}{\textstyle \sum}\epsilon_{i}^{2}.\]
3601 První suma je zřejmě rovna původní chybě
3602 \begin_inset Formula $\mathrm{\overline{SE}}$
3606 \begin_inset space ~
3610 \begin_inset CommandInset ref
3612 reference "eq:vzorec"
3617 Hodnota druhé sumy je závislá na korelaci odchylek způsobených nepřesností
3618 zobrazení a odchylek ve zdrojovém bloku.
3619 Lze snadno ukázat, že
3620 \begin_inset Formula $\sum e_{i}=0$
3623 (platí díky tomu, že optimální zobrazení v
3624 \begin_inset space ~
3627 RMSE metrice zobrazují průměrnou hodnotu zdrojového bloku na průměrnou hodnotu
3630 \begin_inset Note Note
3633 \begin_layout Plain Layout
3637 \begin_layout Plain Layout
3638 Pokud by tedy byly chyby nezávislé, očekávaná hodnota sumy by byla nulová.
3640 \begin_inset space ~
3643 její hodnotě nelze moc říct
3644 \begin_inset space ~
3647 --- může být kladná i záporná, je zde zanedbána, což odpovídá předpokladu
3648 nezávislosti chyb (který je ale zcela nepodložený).
3653 Za předpokladu, že chyby
3654 \begin_inset Formula $\epsilon_{i}$
3657 nejsou korelované, vyjde nulová očekávaná hodnota
3661 \begin_layout Plain Layout
3670 ) je zde používáno ve smyslu teorie pravděpodobnosti a statistiky
3678 \begin_layout Standard
3679 Třetí suma odpovídá odchylce zmenšeného zdrojového bloku.
3680 Pokud požadovanou odchylku pro cílový blok označíme
3681 \begin_inset Formula $\mathrm{SE'}$
3684 a poměr velikostí zdrojového bloku po zmenšení a před zmenšením označíme
3686 \begin_inset Formula $\alpha\in\left(0,1\right)$
3689 , pak lze očekávat, že se bude odchylka zdrojového bloku před zmenšením
3691 \begin_inset Formula $\frac{\mathrm{SE'}}{\alpha}$
3695 Když při zmenšování jeden pixel vzniká jako průměr
3696 \begin_inset Formula $\frac{1}{\alpha}$
3699 pixelů zdrojového bloku s
3700 \begin_inset space ~
3703 nekorelovanými odchylkami, pak očekávaná čtvercová chyba zmenšeného zdrojového
3705 \begin_inset Formula $\alpha\cdot\mathrm{SE'}$
3708 , tedy nová chyba zobrazení zahrnující očekávanou odchylku se zjednoduší
3719 \begin_inset Formula \[
3720 \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'}\]
3727 \begin_layout Standard
3728 Celé odvození penalizace lze analogicky provést i pro klasický model zobrazování
3730 \begin_inset space ~
3734 \begin_inset CommandInset ref
3736 reference "Chyba_zobrazení/Klasická"
3741 \begin_inset space ~
3744 obou případech jsou používany nepodložené předpoklady, především předpoklad
3745 nekorelovanosti chyb jednotlivých pixelů, který by bylo vhodné alespoň
3749 \begin_layout Standard
3750 Implementace příslušného modulu (popsaná v
3751 \begin_inset space ~
3755 \begin_inset CommandInset ref
3757 reference "Implementace/Zobrazování"
3761 ) dává možnost započítat penalizaci do chyb zobrazení.
3762 Při jejím použití je dosahována výrazně vyšší kvalita dekódovaného obrázku
3763 než při klasickém počítání s
3764 \begin_inset space ~
3767 omezenou nebo neomezenou velikostí lineárních koeficientů za cenu pouze
3768 nepatrného poklesu kompresního poměru.
3771 \begin_layout Chapter
3775 \begin_layout Subsubsection
3779 \begin_layout Standard
3780 Cílem implementace bylo vytvořit framework pro studium fraktální komprese,
3781 kde by byly jednotlivé části algoritmů oddělené do modulů, aby bylo možné
3782 kompatibilní algoritmy snadno vzájemně vyměnovat a aby implementace jednotlivýc
3783 h technik byla tvořena převážně algoritmickým kódem, odděleně od správy
3784 závislostí mezi moduly, interakce s
3785 \begin_inset space ~
3788 uživatelem a nezávisle na způsobu implementace ostatních modulů.
3791 \begin_layout Standard
3792 Aby bylo možné jednotlivé techniky objektivně porovnávat, je kladen důraz
3793 na efektivitu implementace.
3795 \begin_inset space ~
3798 některých algoritmech, kde by dělení do více modulů významným způsobem snížilo
3799 efektivitu, upřednostněna konfigurace modulu pomocí jiných parametrů.
3802 \begin_layout Subsubsection
3803 Zvolené vývojové nástroje
3806 \begin_layout Standard
3807 Jako programovací jazyk pro implementaci bylo zvoleno C++, především kvůli
3808 kombinaci vysoké efektivity a mnoha pokročilých vlastností (například generické
3810 Pro překlad byl používán překladač z
3811 \begin_inset space ~
3814 rodiny GNU překladačů (GCC
3815 \begin_inset space ~
3819 \begin_inset CommandInset citation
3828 \begin_layout Standard
3829 Grafické uživatelské rozhraní (GUI) je realizováno pomocí knihoven Qt
3830 \begin_inset space ~
3834 \begin_inset CommandInset citation
3840 , které také zajišťují čtení a zápis obrázků ve standardních formátech (BMP,
3844 \begin_layout Standard
3845 Díky použitým prostředkům by měl být celý program snadno přenositelný (na
3846 úrovni zdrojového kódu).
3847 Vývoj a ladění probíhaly na GNU/Linux, s
3848 \begin_inset space ~
3851 testováním také na MS
3852 \begin_inset space ~
3856 \begin_inset space ~
3862 \begin_layout Section
3866 \begin_layout Standard
3867 Oddělení modulů do jednotlivých dynamických knihoven by zde nepřineslo významný
3868 užitek, takže byla zvolena kompilace celého programu do jednoho spustitelného
3869 souboru (kromě knihoven Qt).
3870 Přesto jsou zde minimalizovány vzájemné závislosti mezi moduly.
3873 \begin_layout Standard
3874 Deklarace související s
3875 \begin_inset space ~
3879 \begin_inset space ~
3886 , většina implementace je pro přehlednost v
3887 \begin_inset space ~
3895 \begin_layout Subsubsection
3896 Základní vlastnosti modulů
3899 \begin_layout Standard
3900 Všechny moduly jsou potomky třídy
3904 , která definuje základní společné vlastnosti, především způsob reprezentace
3906 Je zde virtuální metoda
3910 , která vrací referenci na strukturu obsahující informace o
3911 \begin_inset space ~
3915 \begin_inset space ~
3918 --- jeho identifikační číslo, jméno, text popisující funkci, počet parametrů
3919 nastavení a ukazatel na pole obsahující vlastnosti jednotlivých parametrů
3920 nastavení (typ, rozsah hodnot, název a popis).
3925 obsahuje ukazatel na pole skutečných hodnot nastavení pro daný modul a
3926 také spoustu dalších pomocných typů a metod.
3929 \begin_layout Standard
3930 Tento způsob práce s
3931 \begin_inset space ~
3934 nastaveními umožňuje jejich automatické měnění, ukládání a zobrazování libovolný
3935 m uživatelským rozhraním.
3936 Vše pomocí společného kódu odděleného od všech modulů.
3939 \begin_layout Standard
3940 Obsah zmíněné informační struktury je potřeba pro každý typ modulu nadefinovat,
3941 což by znamenalo mnoho opakujícího se technického kódu, a proto jsou pro
3942 tento účel vytvořeny funkce a makra, kterým stačí předat pouze jednotlivé
3943 vlastnosti (název, typy parametrů, \SpecialChar \ldots{}
3944 ), takže implementace jednotlivých modulů
3945 je jednodušší a přehlednější.
3948 \begin_layout Subsubsection
3952 \begin_layout Standard
3953 Aby framework mohl s
3954 \begin_inset space ~
3957 modulem pracovat, je potřeba upravit soubor
3961 vložením hlavičkového souboru (pomocí
3965 ) a přidáním typu modulu do seznamu
3971 \begin_inset space ~
3974 souboru se postará o
3975 \begin_inset space ~
3978 možnost volby modulu, závislosti a další technické záležitosti.
3979 Zde je nejsložitější generování některých metod z
3980 \begin_inset space ~
3983 tohoto seznamu typů, pro které je využita část z
3984 \begin_inset space ~
3987 knihovny, kterou napsal Andei Alexandrescu jako přílohu ke knize
3992 \begin_inset space ~
3996 \begin_inset CommandInset citation
4005 \begin_layout Standard
4007 \begin_inset space ~
4010 správu modulů a vytváření nových slouží třída
4012 Module\SpecialChar \-
4016 Ta má jedinou instanci, která při startu vytvoří prototyp pro každý typ
4018 Prototypy uchovávají výchozí nastavení jednotlivých typů modulů a je možné
4019 je použít pro získání obecných informací o
4020 \begin_inset space ~
4023 typech modulů (metoda
4027 ) nebo pro vytváření dalších instancí.
4030 \begin_layout Standard
4031 Nové moduly jsou vytvářeny zásadně klonováním, mělkým nebo hlubokým.
4032 Oba způsoby vytvoří novou instanci pomocí kopírovacího konstruktoru a zkopírují
4034 Mělké klonování navíc vynuluje odkazy na podřízené moduly, zatímco hluboké
4035 klonování je naklonuje stejným způsobem.
4036 Hluboké klonování se hodí například pro vytvoření nového výchozího stromu
4037 modulů (například před kompresí) a mělké se používá při načítání ze souborů,
4038 kde není ve chvíli vytváření modulů zřejmé, jakých typů budou podřízené
4042 \begin_layout Subsubsection
4043 Závislosti mezi moduly
4046 \begin_layout Standard
4047 Jsou definována rozhraní, každé popisující jednu požadovanou funkcionalitu.
4048 Všechna použitá rozhraní se nacházejí v
4049 \begin_inset space ~
4062 \begin_inset space ~
4065 nich je potomkem šablonované třídy
4067 Inter\SpecialChar \-
4070 , která zpřístupňuje seznam identifikátorů všech typů modulů implementujících
4071 toto rozhraní (kód je vygenerován ze seznamu
4078 \begin_layout Standard
4079 Každý modul implementuje právě jedno rozhraní a může využívat libovolné
4080 množství dalších rozhraní
4081 \begin_inset space ~
4085 \begin_inset space ~
4088 typů parametrů modulů je podřízený modul implementující zvolené rozhraní.
4089 Uživatel pak na tato místa může zapojit libovolný typ modulu (jsou zobrazeny
4090 pouze kompatibilní typy).
4091 Konfigurace komprese je tedy dána tímto stromem typů modulů spolu s
4092 \begin_inset space ~
4095 jejich dalším nastavením.
4098 \begin_layout Section
4102 \begin_layout Subsubsection
4106 \begin_layout Standard
4107 Rozhraní pro kořenový modul je navrženo jako jediný přístupový bod pro GUI
4108 ke kompresi a dekompresi.
4111 \begin_layout Standard
4112 Kořen včetně celého stromu může být ve třech různých stavech.
4114 \begin_inset space ~
4117 počátečním prázdném stavu strom neobsahuje žádný obrázek, ale může v
4118 \begin_inset space ~
4121 něm docházet ke změnám konfigurace, včetně vyměňování podřízených modulů.
4124 \begin_layout Standard
4126 \begin_inset space ~
4129 počátečního stavu může přejít do komprimovaného stavu úspěšným voláním metody
4134 , které je předán bitmapový obrázek ke kompresi (třída knihoven Qt) a reference
4136 \begin_inset Note Note
4139 \begin_layout Plain Layout
4145 umožňující komunikaci s
4146 \begin_inset space ~
4149 jiným vláknem během tohoto často zdlouhavého procesu.
4150 Pokud nebylo možné kompresi dokončit (například kvůli přerušení uživatelem),
4156 \begin_inset space ~
4162 \begin_layout Standard
4163 Druhou možností je přejít z
4164 \begin_inset space ~
4167 počátečního stavu do dekomprimovaného stavu úspěšným voláním metody
4172 , které je předán proud bytů obsahující komprimovanou podobu obrázku a míra
4173 přiblížení pro dekompresi.
4174 Rozměry dekomprimovaného obrázku jsou původní rozměry vynásobené
4175 \begin_inset Formula $2^{i}$
4179 \begin_inset Formula $i$
4183 Pokud nebylo možné dekódovat obrázek, například kvůli špatnému formátu
4184 souboru, vrátí metoda
4188 a stav stromu se nezmění.
4191 \begin_layout Standard
4192 Dále rozhraní obsahuje metody pro ukládání obrázku v
4193 \begin_inset space ~
4196 komprimovaném stavu do proudu bytů, pro provádění dekódovacích akcí (vyčištění
4197 obrázku nebo iterování zobrazení), pro uložení momentálního stavu dekódování
4198 do bitmapového obrázku (třída knihoven Qt) a pro ukládání a nahrávání nastavení
4202 \begin_layout Subsubsection
4207 \begin_inset space \hfill{}
4217 \begin_layout Standard
4218 Implementace kořenového modulu umožňuje jednotné nastavení nejzákladnějších
4219 parametrů komprese a rozděluje fáze procesu mezi několik nezávislých modulů.
4222 \begin_layout Standard
4223 Kvůli uživatelské přívětivosti bylo zvoleno nastavování kvality komprese
4225 \begin_inset space ~
4229 Hodnota je pomocí zvoleného modulu s
4230 \begin_inset space ~
4239 konvertována na nejvyšší možnou čtvercovou chybu pro danou velikost cílového
4240 bloku (modul je ve skutečnosti použit až v
4241 \begin_inset space ~
4244 podřízených modulech).
4247 \begin_layout Standard
4248 Dále lze zvolit modul s
4249 \begin_inset space ~
4254 IColor\SpecialChar \-
4255 Trans\SpecialChar \-
4259 \begin_inset space ~
4263 \begin_inset space ~
4267 \begin_inset space ~
4272 IShape\SpecialChar \-
4273 Trans\SpecialChar \-
4276 zajišťující další fáze komprese a také maximální množství zdrojových bloků,
4277 protože je to velmi důležitý parametr pro všechny metody fraktální komprese.
4280 \begin_layout Section
4284 \begin_layout Subsubsection
4288 \begin_layout Standard
4289 Rozhraní pro konverzi kvality
4290 \begin_inset space ~
4294 \begin_inset space ~
4297 velikosti cílového bloku a nastavení kvality spočítá odpovídající maximální
4298 přípustnou čtvercovou odchylku.
4301 \begin_layout Subsubsection
4306 \begin_inset space \hfill{}
4311 modules/quality2SE.h
4316 \begin_layout Standard
4321 je triviální implementací rozhraní pro konverzi kvality, která používá
4322 čtvercovou odchylku nezávislou na velikostech bloků.
4323 Přípustná odchylka je pro nejvyšší kvalitu nulová a pak roste přibližně
4324 exponenciálně (exponenciální funkce je mírně posunutá tak, aby procházela
4326 \begin_inset Formula $100\%$
4332 \begin_layout Standard
4333 Bylo by sice přirozenější mít pro danou kvalitu místo čtvercové chyby konstantní
4335 \begin_inset space ~
4338 počtem pixelů bloku.
4340 \begin_inset space ~
4343 větší variabilitě velikostí bloků a ve většině případů i k
4344 \begin_inset space ~
4347 nepatrně lepší objektivní kvalitě (při stejném kompresním poměru), ale protože
4349 \begin_inset space ~
4352 tomto projektu nebyly implementovány žádné vyhlazovací techniky, objevily
4354 \begin_inset space ~
4357 velkých bloků velmi výrazné hrany, takže by se subjektivní kvalita zhoršila.
4358 Pro porovnání je implementována i tato možnost v
4359 \begin_inset space ~
4369 \begin_layout Section
4373 \begin_layout Subsubsection
4377 \begin_layout Standard
4378 Rozhraní převádí práci s
4379 \begin_inset space ~
4382 jedním barevným obrázkem na práci s
4383 \begin_inset space ~
4386 několika jednobarevnými.
4387 Barevné obrázky jsou reprezentované třídou
4392 \begin_inset space ~
4395 knihoven Qt, jednobarevné obrázky jsou zde definovány jako matice pixelů
4397 \begin_inset space ~
4400 ukazatelem na strukturu obsahující některé parametry (rozměry, přiblížení,
4401 kvalita komprese a modul pro její konverzi, maximální počet zdrojových
4403 \begin_inset Note Note
4406 \begin_layout Plain Layout
4407 rozepsat? aktualizační struktura? diskuze o volbě reprezentace?
4415 \begin_layout Standard
4416 Metody rozhraní umožňují vytvoření jednobarevných obrázků pro dané parametry
4417 a barevný obrázek, zpětné složení do barevného obrázku, uložení nebo načtení
4418 případných dat modulu.
4421 \begin_layout Subsubsection
4426 \begin_inset space \hfill{}
4431 modules/colorModel.*
4436 \begin_layout Standard
4441 je triviální implementací rozhraní pro zpracování barev, která nabízí práci
4443 \begin_inset space ~
4446 modelech RGB a YCbCr.
4447 Protože je citlivost oka na jednotlivé barevné složky různá, je navíc umožněno
4448 zvolit pro každou ze složek číslo z
4449 \begin_inset space ~
4453 \begin_inset Formula $\left[0;1\right]$
4456 , kterým se vynásobí původní kvalita komprese.
4459 \begin_layout Section
4460 Počítání s maticemi pixelů
4461 \begin_inset CommandInset label
4463 name "Implementace/Matice"
4470 \begin_layout Standard
4472 \begin_inset space ~
4479 je definováno mnoho generických struktur a několik funkcí pro jednoduchou
4481 \begin_inset space ~
4485 Tyto nástroje jsou pak použity v
4486 \begin_inset space ~
4489 mnoha modulech a jejich rozhraních.
4492 \begin_layout Subsubsection
4496 \begin_layout Standard
4497 Při ukládání digitálních obrázků se pro reprezentaci pixelu nejčastěji používá
4499 \begin_inset space ~
4503 Tento způsob je paměťově velmi úsporný, ale pro tento projekt se ukázal
4504 jako příliš omezující.
4505 Například už při převodu do jiných barevných modelů by mohlo docházet k
4506 \begin_inset space ~
4509 výraznějším ztrátám informace.
4510 Proto byla zvolena reprezentace pomocí čísla s
4511 \begin_inset space ~
4514 plovoucí řádovou čárkou z
4515 \begin_inset space ~
4519 \begin_inset Formula $\left[0;1\right]$
4523 Pro reprezentaci běžných pixelů postačují čísla s
4524 \begin_inset space ~
4529 jednoduchou přesností
4531 , ale pro většinu složitějších výpočtů a mezivýsledků jsou použita čísla
4533 \begin_inset space ~
4540 , aby byly minimalizovány zaokrouhlovací chyby.
4543 \begin_layout Subsubsection
4547 \begin_layout Standard
4548 Matice jsou reprezentovány tak, že jsou jejich prvky po sloupcích uloženy
4551 \begin_inset space ~
4554 maticemi zajišťuje šablona
4556 Matrix\SpecialChar \-
4559 (parametrizovaná typem prvků matice), která uchovává ukazatel na levý horní
4560 prvek a počet kroků nutných k
4561 \begin_inset space ~
4564 přechodu na další sloupec.
4565 Navenek poskytuje přirozené indexování, konverzi na instanci pouze pro
4566 čtení a další operace.
4569 \begin_layout Standard
4570 Oproti reprezentacím založených na ukládání jednotlivých řádkových nebo
4571 sloupcových vektorů má toto řešení mnoho výhod.
4572 Má menší nároky na spotřebu paměťi a na její alokátor, průchody jsou překladače
4573 m lépe optimalizovatelné a je možné vytvářet odkazy na podmatice.
4576 \begin_layout Subsubsection
4577 Rychlé sčítání podmatic
4580 \begin_layout Standard
4581 Některé moduly potřebují znát součty hodnot pixelů a jejich druhých mocnin
4582 na blocích se kterými pracují.
4583 Pro tyto účely je používána jednoduchá struktura (implementovaná v
4584 \begin_inset space ~
4589 Matrix\SpecialChar \-
4592 ), která si předpočítá součty pro všechny obdélníky začínající v
4593 \begin_inset space ~
4596 levém horním rohu a pak může spočítat součet libovolného obdélníka pouze
4597 ze čtyř rohových hodnot.
4600 \begin_layout Standard
4603 Matrix\SpecialChar \-
4606 není používána samostaně, ale jako součást šablony
4608 Summed\SpecialChar \-
4611 , která kromě matice vlastních hodnot obsahuje její rozměry a šablonu
4613 Matrix\SpecialChar \-
4616 pro rychlý výpočet součtů hodnot a jejich druhých mocnin.
4617 Konkrétně je definována struktura
4619 Summed\SpecialChar \-
4622 , která je jen instanciací šablony
4624 Summed\SpecialChar \-
4627 pro již zmíněné typy hodnot pixelů používané v
4628 \begin_inset space ~
4634 \begin_layout Subsubsection
4638 \begin_layout Standard
4640 \begin_inset space ~
4643 projektu je potřeba současně procházet dvě stejně velké obdélníkové podmatice
4644 a provádět nějakou činnost s
4645 \begin_inset space ~
4648 příslušnými dvojicemi jejich prvků, navíc je často nutné počítat s
4649 \begin_inset space ~
4653 \begin_inset space ~
4656 8 vzájemných afinních transformací podmatic.
4657 Opakovaně ručně psané cykly by velmi znepřehledňovaly kód a byly by potencionál
4659 Proto je zde použit jiný přístup využívající generické programovaní a optimaliz
4663 \begin_layout Standard
4664 Základem celé techniky je funkce
4669 , která má tři parametry
4670 \begin_inset space ~
4673 --- řídící iterátor, druhý (podřízený) iterátor a operátor.
4674 Funkce pak pouze najednou posouvá oba iterátory a na odpovídajících dvojicích
4675 prvků volá operátor.
4676 Díky tomu, že se jednotlivé části cyklu takto oddělí, je možné konkrétní
4677 alternativy implementovat a pak libovolně kombinovat.
4680 \begin_layout Standard
4681 Iterátory musí podporovat metody pro získání aktuálního prvku (nejlépe formou
4682 reference), posun na další prvek, posun na další seznam (řádek/sloupec),
4683 zahájení práce se seznamem a v
4684 \begin_inset space ~
4687 případě řídícího iterátoru také test konce seznamu a test úplného konce
4689 Operátor pak musí být schopný volání s
4690 \begin_inset space ~
4693 parametry prvků prvního a druhého iterátoru.
4694 Díky tomu, že funkce
4699 vrací koncový stav operátoru, lze jako operátor použít i strukturu, která
4700 do sebe sbírá nějaká data.
4703 \begin_layout Standard
4705 \begin_inset space ~
4708 souboru jsou přímo implementovány iterátory pro osm afinních zobrazení a
4709 také přetížení funkce
4715 \begin_inset space ~
4718 parametrech místo druhého iterátoru číslo afinní transformace, podle kterého
4719 vybere příslušný iterátor.
4720 Dále je zde iterátor pro třídu QImage používaný pro konverzi na matici
4721 a také několik jednoduchých operátorů pro výpočet součtu vzájemných součinů
4722 a pro afinní transformaci hodnot.
4725 \begin_layout Section
4729 \begin_layout Subsubsection
4731 \begin_inset CommandInset label
4733 name "Implementace/IShapeTransformer"
4740 \begin_layout Standard
4742 \begin_inset Quotes gld
4746 \begin_inset Quotes grd
4749 zajišťuje kompresi a dekompresi jednobarevných obrázků (definovaných v
4750 \begin_inset space ~
4755 IColor\SpecialChar \-
4756 Trans\SpecialChar \-
4760 Je zamýšleno jako rozcestí pro několik druhů voleb, například pro možnost
4762 \begin_inset space ~
4765 šestiúhelníkovému tvaru pixelů.
4769 \begin_layout Standard
4770 Ze souboru vstupujících obrázků je vytvořeno několik nezávislých
4774 , pro které lze provádět výpočty vzájemně paralelně.
4775 Rozhraní poskytuje metody pro provádění komprese a dekódovacích akcí pro
4780 a také ukládání do proudu bytů a zpětné nahrávání.
4784 \begin_layout Standard
4789 jsou ukládána po fázích, což umožňuje přidat v
4790 \begin_inset space ~
4793 budoucnu implementaci progresivního dekódování, přestože pro něj momentálně
4795 \begin_inset space ~
4798 kořenovém modulu podpora.
4799 Důležité pro účinnost progresivního dekódování je, že uspořádání fází má
4800 vyšší prioritu než dělení na jednobarevné části způsobené zpracováním barev
4801 nebo přílišnou velikostí obrázku.
4802 Proto bylo nutné dostat tento koncept už do tak obecného rozhraní.
4805 \begin_layout Subsubsection
4810 \begin_inset space \hfill{}
4815 modules/squarePixels.*
4820 \begin_layout Standard
4825 je implementací rozhraní pro
4826 \begin_inset Quotes gld
4830 \begin_inset Quotes grd
4834 \begin_inset space ~
4837 čtvercového tvaru pixelů, umožňující navíc dělení velkých obrázků na menší,
4838 nezávisle (případně i
4839 \begin_inset space ~
4842 paralelně) zpracovávané.
4846 \begin_inset space ~
4851 jsou použity zvolené moduly pro dělení na cílové bloky, pro výběr množiny
4852 zdrojových bloků a pro hledání optimálních zobrazení.
4855 \begin_layout Standard
4856 Dělení jednobarevných obrázků na
4861 \begin_inset space ~
4864 předaných bloků a probíhá rekurzivně.
4865 Každý blok, který je větší než nastavená mez, je rozdělen podle delší souřadnic
4866 e tak, že poměr velikostí je nejvýše dvojnásobný a navíc nově vzniklá strana
4867 levé/horní části má délku mocniny 2.
4870 \begin_layout Subsubsection
4871 \begin_inset Quotes gld
4875 \begin_inset Quotes grd
4881 \begin_layout Standard
4886 navazuje několik rozhraní a modulů obsahující v
4887 \begin_inset space ~
4895 Všechny pracují pouze s
4896 \begin_inset space ~
4899 klasickou (čtvercovou) topologií pixelů a upřednostňují čtvercové bloky
4901 \begin_inset space ~
4904 hraně délky mocniny 2.
4905 Často se pro libovolný blok definuje jeho
4910 \begin_inset Formula $i$
4913 takové, že oba rozměry jsou nejvýše
4914 \begin_inset Formula $2^{i}$
4922 je 2, což nejčastěji odpovídá blokům velikosti
4923 \begin_inset Formula $4\times4$
4929 \begin_layout Standard
4931 \begin_inset space ~
4936 ISquare\SpecialChar \-
4941 ISquare\SpecialChar \-
4946 ISquare\SpecialChar \-
4949 (definovanými níže) spolupracující na jenom
4953 často potřebují vzájemně volat své metody a také sdílet některá další data.
4954 Proto je definována struktura
4956 Plane\SpecialChar \-
4960 \begin_inset space ~
4970 \begin_layout Standard
4973 Plane\SpecialChar \-
4976 obsahuje vlastní jednobarevnou část obrázku zpracovávnou
4981 \begin_inset space ~
4986 Summed\SpecialChar \-
4990 \begin_inset space ~
4994 \begin_inset CommandInset ref
4996 reference "Implementace/Matice"
5001 Dále obsahuje ukazatele na moduly spolupracující na
5006 \begin_inset space ~
5009 některými nastaveními (definovanou v
5010 \begin_inset space ~
5015 IColor\SpecialChar \-
5016 Trans\SpecialChar \-
5022 \begin_layout Section
5023 Dělení na cílové bloky
5026 \begin_layout Subsubsection
5030 \begin_layout Standard
5031 Rozhraní pro dělení na obdélníkové cílové bloky definuje základní strukturu
5034 Range\SpecialChar \-
5037 pro reprezentaci cílového bloku, která obsahuje souřadnice jeho okrajů,
5042 bloku a přídavný ukazatel, do kterého si spolupracující modul s
5043 \begin_inset space ~
5048 ISquare\SpecialChar \-
5051 může ukládat pomocná data
5056 Moduly implementující rozhraní mohou používat libovolný typ odvozený z
5057 \begin_inset space ~
5062 Range\SpecialChar \-
5065 , ale ostatním je viditelná pouze část definovaná v
5066 \begin_inset space ~
5072 \begin_layout Standard
5073 Kromě klasických metod pro ukládání a nahrávání nastavení a dalších dat
5074 je zde metoda pro získání seznamu ukazatelů na bloky, na které je
5078 rozdělen, a metoda pro zpracování celého
5083 Při jejím provádění je celý blok rozdělen na cílové bloky a pomocí volání
5084 metod modulů spolupracujících na úkolu je pro každý z
5085 \begin_inset space ~
5088 nich nalezeno optimální zobrazení.
5089 Tyto činnosti jsou spojeny proto, že schopnost nalézt dostatečně dobrá
5090 zobrazení typicky ovlivňuje jemnost rozdělení na cílové bloky.
5093 \begin_layout Subsubsection
5095 \begin_inset CommandInset label
5097 name "Implementace/MQuadTree"
5105 \begin_inset space \hfill{}
5115 \begin_layout Standard
5120 implementuje klasický čtyřstromový algoritmus s
5121 \begin_inset space ~
5124 několika drobnými rozšířeními.
5125 Je možné zvolit zda se má používat heuristické dělení a také nejmenší a
5126 největší povolenou velikost bloku.
5129 \begin_layout Paragraph
5133 \begin_layout Standard
5134 Původní algoritmus počítá pouze s
5135 \begin_inset space ~
5138 obrázky tvaru čtverce o
5139 \begin_inset space ~
5142 hraně mocniny 2, což by zde nebylo dostačující.
5143 Naštěstí stačí pracovat s
5144 \begin_inset space ~
5147 bloky stejným způsobem, jen v
5148 \begin_inset space ~
5151 některých případech jsou jejich skutečné rozměry menší, protože jsou
5152 \begin_inset Quotes gld
5156 \begin_inset Quotes grd
5160 Je pouze potřeba navíc ošetřit případy, kdy by při dělení na čtvrtiny vznikly
5164 \begin_layout Standard
5165 Dělení čtyřstromem se řídí jednoduchým principem.
5166 Na začátku je celý vstupní obrázek jeden cílový blok.
5167 Pak se rekurzivně pro každý blok zkouší nalézt dostatečně dobré zobrazení
5169 \begin_inset space ~
5172 případě neúspěchu je blok rozdělen na čtyři o
5173 \begin_inset space ~
5176 poloviční velikosti.
5177 Samozřejmě, bloky větší než nastavené maximum jsou rozděleny bez hledání
5179 \begin_inset space ~
5183 \begin_inset space ~
5186 velikosti nastaveného minima se modul vždy spokojí s
5187 \begin_inset space ~
5190 nejlepším nalezeným zobrazením.
5193 \begin_layout Paragraph
5197 \begin_layout Standard
5198 Byla zde jedna velká nevýhoda
5199 \begin_inset space ~
5202 --- původní algoritmus slepě zkoušel hledat zobrazení i pro bloky, pro které
5203 bylo zřejmé, že nemůže uspět.
5204 Proto zde může být dělení prováděno podle jednoduché heuristiky, která
5206 \begin_inset space ~
5210 \begin_inset space ~
5213 bloku) chybu optimálního zobrazení.
5214 Pokud pro nějaký blok bylo hledáno dostatečně dobré zobrazení, ale neúspěšně,
5215 je blok dále dělen původním algoritmem.
5216 Pokud byl nějaký blok naopak spekulativně rozdělen a všem jeho následníkům
5217 se podařilo najít optimální zobrazení, pak se zkusí hledat zobrazení i
5219 \begin_inset space ~
5222 případě úspěchu je zpětně sloučen (to může způsobit kaskádu slučování).
5226 \begin_layout Standard
5227 Heuristické dělení dává stejný výsledek za předpokladu (který platí téměř
5228 vždy), že pokud je možné nalézt dostatečně dobré zobrazení pro blok, pak
5229 je to možné i pro jeho čtvrtiny.
5231 \begin_inset space ~
5234 praxi představuje tato technika významné urychlení, přestože není heuristika
5235 moc přesná, například chyby bloků s
5236 \begin_inset space ~
5240 \begin_inset Quotes gld
5244 \begin_inset Quotes grd
5247 šumem jsou podhodnoceny a naopak chyby bloků s
5248 \begin_inset space ~
5251 jedním pozvolným nebo ostrým přechodem výrazně nadhodnoceny.
5252 Urychlení nastává zejména proto, že přeskočené hledání zobrazení pro velké
5253 bloky bývá časově velmi náročné, často kvůli nutnosti stavby složitých
5257 \begin_layout Standard
5258 Bylo by možné heuristiku ještě výrazně zpřesnit pomocí rozšíření rozhraní
5261 ISquare\SpecialChar \-
5265 \begin_inset space ~
5268 příslušnou odhadující metodu.
5269 Například implementace založené na mnohadimenzionálních prostorových datových
5270 strukturách by pak mohly odhadovat optimální chybu mnohem přesněji a také
5274 \begin_layout Paragraph
5278 \begin_layout Standard
5279 Efektivita uložení do proudu bytů je při kompresi obrazu velmi důležitá.
5280 Proto je nejprve uložena největší a nejmenší použitá
5284 (tedy ne nastavené limity) a potom při rekurzivním průchodu čtyřstromem
5285 je pro blok uložen jeden bit nastavený podle toho, zda blok byl nebo nebyl
5287 Bit se ukládá pouze pro bloky, kdy není možné informaci získat už z
5288 \begin_inset space ~
5291 uložené minimální a maximální
5298 \begin_layout Standard
5299 Cílové bloky jsou vraceny z
5300 \begin_inset space ~
5304 \begin_inset space ~
5307 pořadí jejich výskytu na Hilbertově křivce.
5308 Tím jsou sníženy vzájemné vzdálenosti po sobě jdoucích bloků a tedy i zefektivn
5309 ěny diferenční metody používané v
5310 \begin_inset space ~
5313 implementaci rozhraní
5315 ISquare\SpecialChar \-
5319 \begin_inset space ~
5323 \begin_inset CommandInset ref
5325 reference "Implementace/Zobrazování"
5332 \begin_layout Section
5333 Výběr množiny zdrojových bloků
5334 \begin_inset CommandInset label
5336 name "Implementace/Domény"
5343 \begin_layout Subsubsection
5347 \begin_layout Standard
5348 Vytváření rozhraní vybírajícího množinu zdrojových bloků bylo obtížné.
5349 Zdrojové bloky lze volit mnoha různými způsoby.
5350 Pokud by ale bylo rozhraní příliš obecné, mohla by se velmi výrazně snížit
5351 rychlost komprese a dekomprese.
5354 \begin_layout Standard
5355 Rozhraní poskytuje několik matic pro cílové bloky, jejichž obsah je už zmenšen
5356 tak, že zbytek zobrazení mezi zdrojovými a cílovými bloky nemění rozměry.
5357 Poskytované zdrojové bloky jsou vždy čtverce o
5358 \begin_inset space ~
5361 hranách délky mocniny 2, které jsou pravidelně rozmístěny po matici.
5362 Omezení velikostí zdrojových bloků ve skutečnosti neomezuje velikosti cílových
5363 bloků, protože modul pro zobrazování (s
5364 \begin_inset space ~
5369 ISquare\SpecialChar \-
5372 ) nemusí využít celý blok.
5374 \begin_inset space ~
5377 těchto matic a pro každou
5381 bloku je rozhraním poskytnut rozestup
5382 \begin_inset space ~
5386 \begin_inset space ~
5389 který jsou vzdáleny odpovídající rohy zdrojových bloků v
5390 \begin_inset space ~
5396 \begin_layout Standard
5397 Metody rozhraní umožňují inicializaci modulu pro daný
5401 , aktualizaci hodnot pixelů v
5402 \begin_inset space ~
5405 maticích pro zdrojové bloky (ze stavu
5409 ), vrácení seznamu těchto matic, ukládání a nahrávaní nastavení a dalších
5411 Také je zde metoda pro zjištění hustoty pokrytí zdrojovými bloky pro všechny
5412 matice, danou úroveň a daný maximální počet zdrojových bloků.
5415 \begin_layout Subsubsection
5420 \begin_inset space \hfill{}
5425 modules/stdDomains.*
5430 \begin_layout Standard
5435 implementuje rozhraní
5437 ISquare\SpecialChar \-
5440 a nabízí mnoho možností nastavení.
5443 \begin_layout Standard
5444 Předně lze regulovat maximální množství zdrojových bloků v
5445 \begin_inset space ~
5448 závislosti na jejich
5453 Původní maximum platí pro
5457 2, pro vyšší lze nastavit míru poklesu (koeficient geometrické řady).
5460 \begin_layout Paragraph
5461 Druhy zdrojových bloků
5464 \begin_layout Standard
5465 Třída umožňuje vytvářet několik druhů matic pro zdrojové bloky.
5466 Základní matice jsou čtyř druhů:
5483 Vzájemné poměry množství zdrojových bloků generovaných z
5484 \begin_inset space ~
5487 matic jednotlivých druhů může uživatel nastavit (přibližně).
5490 \begin_layout Standard
5495 matice vznikají zmenšením celého vstupu v
5496 \begin_inset space ~
5499 obou směrech na polovinu pomocí průměrování hodnot pixelů po čtveřicích.
5500 To je ve fraktální kompresi nejčastější metoda, protože je velmi jednoduchá,
5502 \begin_inset space ~
5505 praxi dobré výsledky.
5506 Další způsoby zmenšování jsou inspirovány především článkem
5507 \begin_inset space ~
5511 \begin_inset CommandInset citation
5517 , ale podobné návrhy lze najít i na mnoha jiných místech.
5520 \begin_layout Standard
5529 matice vznikají nerovnoměrným zmenšením celého vstupu v
5530 \begin_inset space ~
5534 \begin_inset space ~
5538 \begin_inset space ~
5541 jednom směru probíhá zmenšení na
5542 \begin_inset Formula $\nicefrac{1}{3}$
5546 \begin_inset space ~
5550 \begin_inset Formula $\nicefrac{2}{3}$
5557 \begin_layout Plain Layout
5558 Ve starší implementaci projektu probíhalo zmenšování pouze v
5559 \begin_inset space ~
5562 jednom směru, což těsně porušovalo podmínku kontraktivity z
5563 \begin_inset space ~
5567 \begin_inset CommandInset ref
5569 reference "PIFS/Rychlá_konvergence"
5574 Při okrajovém nastavení pak bylo snadno možné dosáhnout obrázku, kde některé
5575 bloky konvergovaly velmi pomalu a k
5576 \begin_inset space ~
5579 chybnému vodorovně nebo svisle
5580 \begin_inset Quotes gld
5584 \begin_inset Quotes grd
5592 Zmenšování probíhá výpočtem váženého průměru, kde jeden pixel vzniká ze
5593 tří celých a tří polovin pixelů, viz obrázek
5594 \begin_inset space ~
5598 \begin_inset CommandInset ref
5600 reference "Implementace/Domény/Náčrtek"
5607 \begin_layout Standard
5612 matice vznikají otáčením částí vstupu o
5613 \begin_inset space ~
5617 \begin_inset Formula $45^{\circ}$
5620 proti směru hodinových ručiček.
5621 Přes svůj název (odvozený z
5622 \begin_inset space ~
5630 \begin_inset space ~
5634 \begin_inset CommandInset citation
5641 \begin_inset space ~
5645 \begin_inset space ~
5648 tvaru pootočeného čtverce.
5649 Zde je použit jednoduchý způsob zmenšování
5650 \begin_inset space ~
5653 --- středy nových pixelů leží na některých rozích vstupních pixelů a jejich
5654 hodnota je spočtena jako průměr hodnot čtveřice vstupních pixelů sdílející
5656 Při čtvercovém vstupu se takto využije jen polovina jeho plochy a pokud
5657 by poměr stran byl větší, bylo by to ještě méně.
5658 Proto jsou takové vstupy pokryty více
5662 maticemi rozmístěnými tak, aby nevznikaly identické zdrojové bloky, viz
5664 \begin_inset space ~
5668 \begin_inset CommandInset ref
5670 reference "Implementace/Domény/Náčrtek"
5676 \begin_inset Float figure
5681 \begin_layout Plain Layout
5682 \begin_inset Caption
5684 \begin_layout Plain Layout
5685 \begin_inset CommandInset label
5687 name "Implementace/Domény/Náčrtek"
5691 Schéma zmenšování pro
5704 Tenké čáry značí původní pixely, čárkované značí jejich pokrytí pixely
5706 \begin_inset VSpace defskip
5715 \begin_inset Graphics
5716 filename dom_regular.eps
5722 \begin_inset space \hfill{}
5726 \begin_inset Graphics
5733 \begin_inset space \hfill{}
5737 \begin_inset Graphics
5738 filename dom_diamond.eps
5751 \begin_layout Paragraph
5752 Vícenásobné zmenšování
5755 \begin_layout Standard
5756 Ze základních matic lze ještě vytvářet další, ještě více zmenšené (a z
5757 \begin_inset space ~
5760 nich rekurzivně další).
5761 Použit je stejný algoritmus jako pro vytváření
5766 Lze navíc zvolit, jak velké množství zdrojových bloků bude z
5767 \begin_inset space ~
5770 těchto matic vytvořeno
5771 \begin_inset space ~
5774 --- buď stejné ze všech zmenšujících kroků (přestože ty více zmenšené mají
5775 menší plochu) nebo se bude s
5776 \begin_inset space ~
5779 každým krokem množství vytvořených bloků zmenšovat na polovinu nebo se vícenásob
5780 né zmenšování nepoužije.
5783 \begin_layout Standard
5784 Kvůli obecnosti návrhu rozhraní se i při dekompresi nezobrazují bloky rovnou,
5785 ale přes tyto matice, takže počet matic pro zdrojové bloky významně ovlivňuje
5786 rychlost dekomprese (na rozdíl od komprese, kde nehraje znatelnou roli).
5789 \begin_layout Section
5790 Hledání optimálních zobrazení
5791 \begin_inset CommandInset label
5793 name "Implementace/Zobrazování"
5800 \begin_layout Standard
5801 Hledání optimálních zobrazení je nejdůležitější část celého kompresního
5803 Zde se nejvíce ovlivňuje kvalita výsledku a také stráví nejvíce výpočetního
5807 \begin_layout Subsubsection
5811 \begin_layout Standard
5816 je rozhraní pro správu zobrazení mezi zdrojovými bloky generovanými modulem
5818 \begin_inset space ~
5823 ISquare\SpecialChar \-
5826 a cílovými bloky vytvářenými modulem s
5827 \begin_inset space ~
5832 ISquare\SpecialChar \-
5838 \begin_layout Standard
5839 Rozhraní obsahuje metody pro inicializaci před (de)kompresí
5843 , pro hledání optimálního zobrazení do daného cílového bloku, pro dokončení
5844 komprese a pro provádění dekódovacích akcí (vyčištění obrázku nebo iterování
5846 Dále jsou zde metody pro uložení a nahrání nastavení, pro zjištění počtu
5847 ukládacích fází a pro uložení nebo nahrání dat jednotlivých fází (význam
5849 \begin_inset space ~
5853 \begin_inset CommandInset ref
5855 reference "Implementace/IShapeTransformer"
5862 \begin_layout Subsubsection
5867 \begin_inset space \hfill{}
5872 modules/stdEncoder.*
5877 \begin_layout Standard
5882 implementuje rozhraní podle modelu upravených zobrazení popsaného v
5883 \begin_inset space ~
5887 \begin_inset space ~
5891 \begin_inset CommandInset ref
5893 reference "PIFS/Použitý_model"
5897 a využívá vzorců odvozených v
5898 \begin_inset space ~
5902 \begin_inset space ~
5906 \begin_inset CommandInset ref
5908 reference "Chyba_zobrazení"
5915 \begin_layout Standard
5916 Při hledání optimálního zdrojového bloku pro daný cílový blok (při kompresi)
5917 jsou nejprve předpočítány různé údaje z
5918 \begin_inset space ~
5922 \begin_inset space ~
5926 Pak je postupně pro všechny zdrojové bloky předané predikčním modulem s
5927 \begin_inset space ~
5937 (zvolen uživatelem, rozhraní popsáno v
5938 \begin_inset space ~
5942 \begin_inset CommandInset ref
5944 reference "Implementace/Predikce"
5948 ) počítána chyba zobrazení mezi dvojicí a je zapamatována nejlepší kombinace.
5949 Uživatel také může zvolit, zda bude zkoušeno osm způsobů otočení nebo jen
5950 identita, zda budou povoleny záporné lineární koeficienty, jak moc budou
5951 penalizovány vysoké lineární koeficienty (diskutováno v
5952 \begin_inset space ~
5956 \begin_inset CommandInset ref
5958 reference "Chyba_zobrazení/Penalizace"
5962 ), zda budou započítány chyby vzniklé kvantizací, jak bude omezena absolutní
5963 hodnota lineárních koeficientů, jak nízká dosažená chyba bude stačit pro
5964 okamžité ukončení hledání, jak jemná bude kvantizace průměrů a směrodatných
5965 odchylek a jaké moduly se budou starat o
5966 \begin_inset space ~
5969 ukládání kvantizovaných hodnot.
5972 \begin_layout Standard
5973 Moduly pro ukládání kvantizovaných průměrů a směrodatných odchylek cílových
5974 bloků splňují rozhraní
5980 \begin_inset space ~
5984 \begin_inset CommandInset ref
5986 reference "Implementace/Kódování celočíselných řad"
5990 ) a jsou zapojeny proto, že po sobě jdoucí hodnoty mají vysokou pravděpodobnost
5992 To zajištuje například modul
5994 MQuad\SpecialChar \-
5998 \begin_inset space ~
6002 \begin_inset CommandInset ref
6004 reference "Implementace/MQuadTree"
6008 ), který řadí bloky podle jejich pořadí na Hilbertově křivce, což výrazně
6009 zvyšuje lokalitu posloupnosti.
6010 Tyto vlastnosti ukládaných posloupností lze využít různými způsoby ke zvýšení
6011 efektivity jejich uložení, a proto je tato práce oddělena do jiných modulů.
6014 \begin_layout Standard
6015 Celá chyba lze pro všechny konfigurace snadno spočítat ze součtu hodnot
6016 ve zdrojovém bloku, součtu jejich druhých mocnin, z
6017 \begin_inset space ~
6020 předpočítaných údajů o
6021 \begin_inset space ~
6024 cílovém bloku a ze součtu součinů hodnot odpovídajících pixelů zdrojového
6026 Tento součet součinů je jediný potřebný údaj, který nelze získat v
6027 \begin_inset space ~
6031 Ostatní hodnoty jsou spočteny snadno, nejčastěji pomocí struktur zmíněných
6033 \begin_inset space ~
6037 \begin_inset space ~
6041 \begin_inset CommandInset ref
6043 reference "Implementace/Matice"
6050 \begin_layout Standard
6051 Uživatel má mnoho možností pro změnu způsobu výpočtu chyby mezi dvojicí
6053 Zjišťovat konfiguraci a vyhodnocovat mnoho podmínek při každém výpočtu
6054 chyby by způsobilo výrazné zpomalení.
6055 Proto jsou možnosti realizovány jako šablonové parametry funkce počítající
6056 chybu, která je instanciována pro každou kombinaci parametrů.
6057 Na začátku hledání optimálního zdrojového bloku pro cílový blok se podle
6058 konfigurace zjistí adresa příslušné funkce, která je pak vždy volána.
6060 \begin_inset space ~
6063 funkcí je tedy kompilátorem optimalizována zvlášť a již nevyhodnocuje žádné
6064 podmínky způsobené konfigurací.
6065 Velké množství instanciovaných funkcí zvyšuje kromě rychlosti také velikost
6066 binárního souboru, ale díky tomu, že funkce obsahují jen nejnutnější výpočty,
6067 je tento přínos pro celkovou velikost souboru nevýznamný.
6070 \begin_layout Standard
6071 Modul implementuje podporu pro progresivní dekódování založenou na ukládácích
6073 \begin_inset space ~
6077 \begin_inset space ~
6081 \begin_inset CommandInset ref
6083 reference "Implementace/IShapeTransformer"
6089 \begin_inset space ~
6092 první fázi jsou uloženy průměrné hodnoty všech bloků.
6093 Průměry zaberou málo místa, ale už z
6094 \begin_inset space ~
6097 nich samotných lze zrekonstruovat použitelný náhled výsledku.
6099 \begin_inset space ~
6102 druhé fázi jsou uloženy směrodatné odchylky bloků.
6104 \begin_inset space ~
6107 třetí, poslední, fázi je uložen zbytek potřebných informací pro cílové bloky
6109 \begin_inset space ~
6112 nenulovou směrodatnou odchylkou
6113 \begin_inset space ~
6116 --- vždy bit pro znaménko lineárního koeficientu a tři bity kódující otočení
6117 (jen pokud jsou potřeba) a index zdrojového bloku.
6120 \begin_layout Section
6121 Predikce vhodných zdrojových bloků
6122 \begin_inset CommandInset label
6124 name "Implementace/Predikce"
6131 \begin_layout Standard
6133 \begin_inset space ~
6137 \begin_inset space ~
6141 \begin_inset CommandInset ref
6143 reference "Implementace/Zobrazování"
6147 je řešen přesný výpočet vhodnosti zobrazení mezi dvojicí bloků, ale provádět
6148 ho pro každou možnost by bylo příliš zdlouhavé.
6149 Je tedy nutné umět rychle odhadnout, které zdrojové bloky (a v
6150 \begin_inset space ~
6153 jakých rotacích) je vhodné pro daný cílový blok zkoušet (možné přístupy
6155 \begin_inset space ~
6159 \begin_inset CommandInset ref
6161 reference "Články/Zrychlení"
6168 \begin_layout Subsubsection
6172 \begin_layout Standard
6174 \begin_inset space ~
6181 slouží jako generátor prediktorů vhodných zdrojových bloků pro modul
6187 Definuje strukturu, která obsahuje všechny potřebné informace o
6188 \begin_inset space ~
6191 daném cílovém bloku a nastavení komprese včetně mnoha předpočítaných údajů.
6194 \begin_layout Standard
6195 Po předání správně vyplněné instance této struktury do rozhraní je vytvořena
6197 \begin_inset space ~
6206 tor::IOne\SpecialChar \-
6207 Range\SpecialChar \-
6212 , která postupně vrací vhodné zdrojové bloky (pro tento účel jsou různé
6213 rotace bloku považovány za různé zdrojové bloky).
6214 Bloky nejsou vraceny po jednom, ale v
6215 \begin_inset space ~
6218 seznamech, aby se tak snížila režie spojená s
6219 \begin_inset space ~
6222 voláním virtuální metody.
6223 Je také předávána maximální akceptovaná čtvercová chyba, což ulehčuje prediktor
6224 u rozhodování, které bloky je bezpečné vynechat.
6227 \begin_layout Standard
6228 Dále je definována metoda volaná po skončení všech predikčních požadavků.
6230 \begin_inset space ~
6233 uvolnění potenciální paměti alokované pro urychlení predikcí.
6236 \begin_layout Subsubsection
6241 \begin_inset space \hfill{}
6246 modules/noPredictor.h
6251 \begin_layout Standard
6256 je zcela triviální implementací rozhraní, která nedělá žádnou predikci
6257 a vrací všechny možnosti.
6258 Slouží hlavně pro vyhodnocení účinnosti ostatních implementací.
6261 \begin_layout Subsubsection
6266 \begin_inset space \hfill{}
6271 modules/saupePredictor.*
6276 \begin_layout Standard
6281 je založen na větě publikované v
6282 \begin_inset space ~
6286 \begin_inset CommandInset citation
6294 \begin_inset space ~
6297 mírně upravené podobě, která je bližší značení z
6298 \begin_inset space ~
6302 \begin_inset space ~
6306 \begin_inset CommandInset ref
6313 \begin_inset space ~
6317 \begin_inset CommandInset ref
6319 reference "Chyba_zobrazení"
6326 \begin_layout Standard
6330 \begin_layout Plain Layout
6340 \begin_inset CommandInset label
6342 name "Implementace/Predikce/Věta"
6347 \begin_inset Formula $n\ge2$
6351 \begin_inset Formula $X=\mathbb{R}^{n}\setminus\left\{ r\cdot\left(1,1,\ldots,1\right)\left|r\in\mathbb{R}\right.\right\} $
6355 Definujme normalizační funkci
6356 \begin_inset Formula $\Phi:X\rightarrow X$
6360 \begin_inset Formula $D:X\times X\rightarrow\left\langle 0,\sqrt{2}\right\rangle $
6364 \begin_inset Formula \[
6365 \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}\]
6370 \begin_inset Formula \[
6371 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{,}\]
6376 \begin_inset Formula $\left\Vert .\right\Vert $
6379 značí eukleidovskou normu.
6382 \begin_layout Standard
6383 Pak pro nejmenší čtvercovou chybu definovanou
6384 \begin_inset Formula \[
6385 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í}\]
6390 \begin_inset Formula \[
6391 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).\]
6399 \begin_layout Plain Layout
6411 \begin_layout Standard
6413 \begin_inset Formula $\sum_{i=1}^{n}\left(\Phi(r)\right)_{i}r_{i}$
6416 pro daný cílový blok konstantní a funkce
6417 \begin_inset Formula $g(x)$
6420 je rostoucí na oboru hodnot funkce
6421 \begin_inset Formula $D(r,d)$
6424 , lze převést hledání optimálního zdrojového bloku na dvojici problémů hledání
6426 \begin_inset space ~
6432 \begin_layout Standard
6433 Pro každou velikost cílového bloku je tedy postavena datová struktura obsahující
6434 všechny možné zdrojové bloky normalizované funkcí
6435 \begin_inset Formula $\Phi$
6438 , konkrétně je použita varianta statického KD-stromu popsaná
6439 \begin_inset CommandInset ref
6440 LatexCommand vpageref
6441 reference "Implementace/KD-stromy"
6447 \begin_inset space ~
6450 danému bodu jsou vraceny prvky struktury v
6451 \begin_inset space ~
6454 pořadí podle dolních odhadů na jejich vzdálenost od tohoto bodu.
6455 Struktury jsou stavěny vždy až když je potřeba je prohledávat.
6457 \begin_inset space ~
6460 modulu a sdíleny všemi prediktory vracenými modulem (struktury jsou statické).
6463 \begin_layout Paragraph
6464 Omezení prohledávání
6467 \begin_layout Standard
6469 \begin_inset Formula $m$
6472 pro čtvercovou chybu, pak maximální přípustná čtvercová chyba v
6473 \begin_inset space ~
6476 normalizovaném prostoru je rovna
6477 \begin_inset Formula \[
6478 {\textstyle 2-2\sqrt{1-\frac{m}{\sum_{i=1}^{n}\left(\Phi(r)\right)_{i}r_{i}}}}\mbox{\quad(pokud existuje).}\]
6482 Tento limit sám nemusí dostatečně zkrátit prohledávání prostoru, protože
6483 téměř konstantní cílové bloky lze dobře aproximovat už konstantním blokem
6484 a aproximace nekonstantním blokem není nikdy horší.
6486 \begin_inset space ~
6489 takovém případě vyjde pod odmocninou záporné číslo.
6490 Proto má uživatel možnost v
6491 \begin_inset space ~
6494 modulu nastavit, jaká největší část zdrojových bloků může být predikována.
6497 \begin_layout Paragraph
6498 Vícenásobné prohledávání
6501 \begin_layout Standard
6503 \begin_inset space ~
6507 \begin_inset space ~
6511 \begin_inset CommandInset ref
6513 reference "Implementace/Predikce/Věta"
6517 je zřejmé, že je potřeba vždy pro dvojici bloků
6518 \begin_inset Formula $r^{i}$
6522 \begin_inset Formula $d^{j}$
6525 uvažovat dvě možnosti
6526 \begin_inset Formula $\left\Vert \Phi(r^{i})-\Phi(d^{j})\right\Vert $
6539 \begin_inset Formula $\left\Vert -\Phi(r^{i})-\Phi(d^{j})\right\Vert $
6542 (pokud jsou povolena zobrazení se zápornými lineárními koeficienty).
6543 Jedna možnost řešení je, že struktura obsahuje vždy
6544 \begin_inset Formula $\Phi(d^{j})$
6548 \begin_inset Formula $-\Phi(d^{j})$
6551 a je hledán nejbližší bod k
6552 \begin_inset space ~
6556 \begin_inset Formula $\Phi(r^{i})$
6561 \begin_inset space ~
6564 druhé možnosti obsahuje struktura pouze
6565 \begin_inset Formula $\Phi(d^{j})$
6569 \begin_inset space ~
6573 \begin_inset Formula $\Phi(r^{i})$
6577 \begin_inset Formula $-\Phi(r^{i})$
6581 Analogicky lze dvěma způsoby řešit uvažování osmi vzájemných rotací (pokud
6582 jsou povoleny uživatelem)
6583 \begin_inset space ~
6586 --- buď je struktura postavena z
6587 \begin_inset space ~
6590 osminásobného množství otočených bloků, nebo je nutné ji osminásobně prohledávat.
6591 Kvůli úspoře paměti byla zde v
6592 \begin_inset space ~
6595 obou případech zvolena varianta s
6596 \begin_inset space ~
6599 menší strukturou a násobným prohledáváním.
6602 \begin_layout Standard
6603 Vícenásobné prohledávání je realizováno tak, že jsou stavy všech prohledávání
6605 \begin_inset space ~
6608 haldě (použita je generická
6609 \begin_inset space ~
6612 STL implementace binární haldy) uspořádané podle příštího odhadu vzdálenosti
6613 ve struktuře a prohledává se tedy vždy ta varianta, která je nejblíže k
6614 \begin_inset space ~
6617 výchozímu bodu hledání (podle odhadu struktury).
6620 \begin_layout Paragraph
6624 \begin_layout Standard
6625 Pro účely predikce jsou bloky zmenšeny na velikost
6626 \begin_inset Formula $4\times4$
6630 \begin_inset space ~
6634 \begin_inset CommandInset citation
6641 Už ze zmenšenin lze vzájemnou zobrazitelnost dobře odhadnout
6642 \begin_inset space ~
6645 --- RMSE optimálního zobrazení mezi zmenšeninami je dolním odhadem na
6646 \begin_inset space ~
6649 RMSE optimálního zobrazení v
6650 \begin_inset space ~
6653 původním rozlišení a rovnost nastává, pokud v
6654 \begin_inset space ~
6657 rámci zprůměrovaných skupin pixelů byly
6658 \begin_inset Quotes gld
6661 stejné vzájemné odchylky
6662 \begin_inset Quotes grd
6665 ve zdrojovém i cílovém bloku.
6666 Díky spojitému charakteru běžných obrázků bývá tento odhad dostatečně blízko,
6667 takže už podle něj lze většinu kandidátů bezpečně vyřadit (protože odhad
6668 překročí maximální povolenou chybu).
6671 \begin_layout Standard
6673 \begin_inset space ~
6676 velkými zdrojovými bloky by přinášela řadu problémů.
6678 \begin_inset space ~
6681 důvodů je, že efektivita KD-stromů klesá s
6682 \begin_inset space ~
6685 růstem počtu souřadnic.
6686 Dalším důvodem je paměťová náročnost.
6687 Pokud bychom pro účel stavby stromu uložili obrazy funkce
6688 \begin_inset Formula $\Phi$
6691 , potřebujeme už při velikosti
6692 \begin_inset Formula $16\times16$
6696 \begin_inset space \thinspace{}
6700 Počty zdrojových bloků se běžně pohybují v
6701 \begin_inset space ~
6704 řádu stovek tisíc, což dává neúnosnou spotřebu stovek megabytů paměti.
6705 Alternativně by bylo možné uchovávat v
6706 \begin_inset space ~
6709 paměti pouze koeficienty funkce
6710 \begin_inset Formula $\Phi$
6713 (pro pevný blok je to afinní funkce) a počítat hodnotu na
6714 \begin_inset space ~
6717 každé souřadnici normalizovaného bloku z
6718 \begin_inset space ~
6721 původního obrázku jednotlivě při každém přístupu.
6723 \begin_inset space ~
6726 mnohonásobnému zpomalení.
6729 \begin_layout Standard
6730 Pro predikci by bylo možné použít i jiné způsoby snižování počtu dimenzí,
6731 například výběr několika nejdůležitějších koeficientů dvourozměrné diskrétní
6732 kosinové transformace bloku
6733 \begin_inset space ~
6737 \begin_inset space ~
6740 použití transformace ve standardu JPEG je zřejmé, že je to velmi dobrý způsob
6741 aproximace obrázku malým množstvím souřadnic.
6744 \begin_layout Subsubsection
6746 \begin_inset CommandInset label
6748 name "Implementace/KD-stromy"
6756 \begin_inset space \hfill{}
6766 \begin_layout Standard
6767 KD-strom je binární strom, který rekurzivně dělí spravovaný prostor v
6768 \begin_inset space ~
6771 každém svém vrcholu podle hodnoty jedné ze souřadnic.
6772 Tato struktura byla zvolena především pro svou jednoduchost a možnost paměťově
6773 úsporné implementace.
6776 \begin_layout Paragraph
6780 \begin_layout Standard
6781 Protože je strom statický a binární, lze jeho tvar volit stejně
6782 \begin_inset Note Note
6785 \begin_layout Plain Layout
6791 jako pro binární haldy a ukládat jeho vrcholy v
6792 \begin_inset space ~
6796 Je zvolena varianta, kde jsou všechny obsažené body až v
6797 \begin_inset space ~
6801 Pro každý vnitřní vrchol pak stačí uložit jen souřadnici, podle které je
6802 dělen podprostor vrcholu, a hodnotu, na které je hranice dělení.
6803 Pro listy je pak uložen jen index bodu, kterému odpovídá.
6806 \begin_layout Standard
6808 \begin_inset space ~
6812 \begin_inset space ~
6815 KD-stromech by byly uchovány také souřadnice všech obsažených bodů.
6816 Ty by ale ovlivnily prohledávání až po dělení vrcholů nad listy, kdy už
6817 je dolní odhad vzdálenosti blízko skutečnosti.
6818 Zde navíc není nutné znát vzdálenosti přesně
6819 \begin_inset space ~
6822 --- většinou se pracuje se zmenšeninami a přesné porovnání je stejně poté
6823 provedeno jiným modulem.
6824 Souřadnice všech bodů také zabírají mnoho místa, takže bylo zvoleno, že
6825 budou využity pouze pro postavení stromu a pak zahozeny.
6826 Tato volba pravděpodobně zhorší výkon struktury, ale alternativa zde není
6827 implementována, takže míra jejího vlivu není známa (je to možnost rozšíření
6829 \begin_inset space ~
6835 \begin_layout Standard
6836 Části prostoru patřící jednotlivým vrcholům jsou definovány rekurzivně.
6837 Kořen reprezentuje hyperkvádr uložený ve stromě, který těsně obaluje všechny
6838 body ve struktuře (minima a maxima všech bodů v
6839 \begin_inset space ~
6842 každé ze souřadnic ve struktuře).
6843 Synové každého vrcholu si rozdělí jeho hyperkvádr podle nadroviny kolmé
6844 na jednu ze souřadnic (souřadnice a mezní hodnota je ve vrcholu uložena).
6846 \begin_inset space ~
6849 této implementaci patří body ležící na mezní nadrovině do obou podstromů,
6850 aby bylo možné vždy volit libovolné velikosti podstromů a dosáhnout tak
6851 tvaru odpovídajícímu binární haldě.
6854 \begin_layout Paragraph
6858 \begin_layout Standard
6859 Hledání nejbližších bodů staví postupu typickém pro všechny podobné struktury.
6860 Je udržována halda z
6861 \begin_inset space ~
6864 vrcholů stromu uspořádaná podle vzdáleností podprostorů vrcholů stromu od
6865 výchozího bodu (toho, k
6866 \begin_inset space ~
6869 němuž hledáme nejbližší body).
6871 \begin_inset space ~
6874 haldě jen kořen a pak se vždy odebere z
6875 \begin_inset space ~
6878 haldy minimum a vloží se do ní synové obsaženého vrcholu stromu.
6880 \begin_inset space ~
6883 minimu haldy list stromu, je pouze poslán na výstup jako další z
6884 \begin_inset space ~
6890 \begin_layout Standard
6892 \begin_inset space ~
6895 haldou efektivní, jsou v
6896 \begin_inset space ~
6899 každém prvku kromě čísla vrcholu stromu uloženy souřadnice bodu z
6900 \begin_inset space ~
6903 části prostoru patřící vrcholu, který je nejblíže výchozímu bodu, a také
6904 druhá mocnina jeho eukleidovské vzdálenosti od výchozího bodu (podle ní
6905 je halda uspořádaná).
6906 Umocnění vzdálenosti nepokazí uspořádání, protože je to pro nezáporná čísla
6907 rostoucí funkce, a významně zjednoduší výpočty.
6908 Tyto údaje lze při dělení na syny velmi snadno přepočítat, protože nejbližší
6909 bod se může změnit jen v
6910 \begin_inset space ~
6913 jedné souřadnici a druhá mocnina jeho vzdálenosti se tedy změní jen o
6914 \begin_inset space ~
6917 rozdíl druhých mocnin rozdílů hodnoty výchozího bodu v
6918 \begin_inset space ~
6921 té souřadnici od nové a původní hodnoty nejbližšího bodu.
6924 \begin_layout Standard
6925 Při prohledávání lze navíc nastavit, že souřadnice výchozího bodu, které
6926 obsahují speciální hodnotu NaN (
6930 ), budou ignorovány.
6933 MSaupe\SpecialChar \-
6938 využito pro lepší predikci pro ořízlé cílové bloky, které jsou menší, protože
6939 leží na okraji obrázku.
6942 \begin_layout Paragraph
6946 \begin_layout Standard
6947 Strom je stavěn rekurzivně
6948 \begin_inset space ~
6951 --- při stavbě vrcholu
6952 \begin_inset Formula $v$
6956 \begin_inset Formula $b$
6960 \begin_inset space ~
6964 \begin_inset Formula $p$
6967 obsahujícím indexy bodů, které mají být reprezentovány podstromem
6968 \begin_inset Formula $v$
6972 Nejprve je určeno, jaké počty bodů budou patřit synům vrcholu
6973 \begin_inset Formula $v$
6978 \begin_inset Quotes gld
6982 \begin_inset Quotes grd
6985 je určen jednoznačně počtem listů, který zde odpovídá počtu bodů ve struktuře,
6986 a navíc se tento tvar dědí
6987 \begin_inset space ~
6990 --- pokud má podstrom nějakého vrcholu tvar haldy, pak ho mají i podstromy
6991 jeho synů a tedy i všechny ostatní podstromy.
6994 \begin_layout Standard
6995 Pak je určena souřadnice
6996 \begin_inset Formula $i$
6999 , podle které bude část prostoru patřící
7000 \begin_inset Formula $v$
7003 dělena (metody rozebrány níže).
7004 Podle ní se obsah pole
7005 \begin_inset Formula $p$
7009 \begin_inset space ~
7013 \begin_inset Formula $b$
7016 rozdělí na dvě části tak, aby jejich velikosti odpovídaly počtům bodů,
7017 které budou patřit synům, a aby žádný bod levého syna měly neměl v
7018 \begin_inset space ~
7022 \begin_inset Formula $i$
7025 -té souřadnici hodnotu větší než nějaký bod pravého syna.
7026 To je provedeno pomocí generického algoritmu
7028 nth_ele\SpecialChar \-
7032 \begin_inset space ~
7035 STL, který najde k-tý nejmenší prvek a přeuspořádá ostatní prvky korektně
7037 \begin_inset space ~
7041 Pak se uloží hodnota souřadnice
7042 \begin_inset Formula $i$
7045 na vzniklé hranici do vrcholu
7046 \begin_inset Formula $v$
7049 a rekurzivně se zkonstruují jeho synové (pokud na ně zbývá více než jeden
7053 \begin_layout Standard
7054 Při stavbě je možno zvolit jeden z
7055 \begin_inset space ~
7058 několika implementovaných způsobů volby souřadnice
7059 \begin_inset Formula $i$
7063 Jsou zde dva triviální algoritmy
7064 \begin_inset space ~
7067 --- jeden cyklicky střídá souřadnice podle houbky a druhý je volí náhodně.
7070 MSaupe\SpecialChar \-
7075 používá lepší algoritmus, který volí tu souřadnici, ve které má část prostoru
7077 \begin_inset Formula $v$
7083 \begin_layout Paragraph
7084 Korespondence se zdrojovým kódem
7087 \begin_layout Standard
7088 Struktura stromu je reprezentována generickou třídou
7093 Prohledávání provádí její podtřída
7095 Point\SpecialChar \-
7098 , která při konstrukci požaduje zadání výchozího bodu, instance prohledávaného
7099 stromu a volbu zda se mají ignorovat některé souřadnice.
7100 Pak na požadavek vrací indexy jednotlivých bodů nebo momentální odhad vzdálenos
7101 ti od výchozího bodu.
7104 \begin_layout Standard
7105 Vytváření stromu provádí statická (ve smyslu objektové terminologie) metoda
7115 Ta umožňuje také zvolit jednu z
7116 \begin_inset space ~
7123 , která bude použita pro volbu souřadnice
7124 \begin_inset Formula $i$
7130 \begin_layout Section
7131 Kódování celočíselných řad
7132 \begin_inset CommandInset label
7134 name "Implementace/Kódování celočíselných řad"
7141 \begin_layout Subsubsection
7145 \begin_layout Standard
7150 je rozhraní pro kódování posloupností celých čísel z
7151 \begin_inset space ~
7155 \begin_inset Formula $\{0,1,\ldots,n-1\}$
7160 \begin_inset space ~
7163 této práci je využito modulem
7168 pro ukládání průměrných barev a směrodatných odchylek cílových bloků.
7171 \begin_layout Standard
7173 \begin_inset space ~
7176 něm poskytnuty metody pro nastavení počtu možností
7177 \begin_inset Formula $n$
7180 , pro uložení seznamu čísel do proudu bytů a pro zpětné zrekonstruování
7181 seznamu dané délky z
7182 \begin_inset space ~
7186 Dále jsou zde metody pro uložení a nahrání nastavení modulu.
7189 \begin_layout Subsubsection
7190 MDifferentialVLICodec
7194 \begin_inset space \hfill{}
7204 \begin_layout Standard
7207 MDifferentialVLICodec
7209 je kodek určený pro efektivní ukládání posloupností čísel, kde mají po
7211 \begin_inset space ~
7214 vysokou pravděpodobností blízké hodnoty.
7215 Místo samotných prvků posloupnosti se uvažuje vždy rozdíl hodnoty od předchozíh
7217 \begin_inset space ~
7221 \begin_inset Formula $\{-\left\lceil \frac{n}{2}\right\rceil ,\ldots,\left\lfloor \frac{n}{2}\right\rfloor \}$
7225 \begin_inset Formula $n$
7229 Tyto rozdíly jsou pak jednotlivě kódovány pomocnou třídou
7236 \begin_layout Standard
7241 provádí kódování tak, že pro čísla blízká nule použije menší množství bitů.
7242 Nejprve převede všechna čísla do rozsahu
7243 \begin_inset Formula $\{0,1,\ldots,n-1\}$
7247 \begin_inset Formula \[
7250 -2x-1 & (x<0)\end{cases}.\]
7254 Pak je celý interval rozdělen na několik částí kódovaných různými počty
7256 Délka první části je nastavena uživatelem (je to mocnina čísla
7257 \begin_inset Formula $2$
7260 ) a každá další část má dvojnásobnou délku, dokud se nevyčerpají všechna
7262 \begin_inset space ~
7266 Každé číslo je pak reprezentováno několika bity udávajícími do jaké části
7267 patří a pak dalším blokem bitů (jejich počet závisí na velikosti dané části),
7268 které udávají pozici v
7269 \begin_inset space ~
7275 \begin_layout Chapter
7276 Testování a vyhodnocení
7279 \begin_layout Standard
7281 \begin_inset space ~
7284 této kapitole budou ukázány výsledky testování komprese na vybraných černobílých
7288 \begin_layout Standard
7289 Testy jsou omezeny pouze na odstíny šedi kvůli jednoduššímu vyhodnocování.
7290 Publikované výsledky se většinou také zabývají pouze černobílými obrázky
7291 a navíc by bylo obtížné sladit míru komprese všech barevných složek na
7292 podobnou úroveň, aby bylo možné výsledky rozumně porovnat.
7295 \begin_layout Standard
7296 Použito je celkem šest testovacích obrázků získaných z
7297 \begin_inset space ~
7300 různorodé kolekce jedné výzkumné skupiny univerzity ve Waterloo
7301 \begin_inset space ~
7305 \begin_inset CommandInset citation
7328 jsou ve fraktální kompresi často používané a mají rozměry
7329 \begin_inset Formula $512\times512$
7342 \begin_inset space ~
7345 --- nejsou to fotografie (spíše se dají popsat spojením
7346 \begin_inset Quotes gld
7350 \begin_inset Quotes grd
7353 ) a mají neobvyklé rozměry
7354 \begin_inset Formula $629\times794$
7358 \begin_inset Formula $814\times880$
7364 \begin_layout Standard
7365 Ke kompresi pomocí standardů JPEG a JPEG
7366 \begin_inset space ~
7369 2000 byly použity utility projektu
7374 \begin_inset space ~
7378 \begin_inset CommandInset citation
7385 Všechny uvedené doby fraktální komprese, hodnoty PSNR a kompresní poměry
7386 byly naměřeny samotným programem.
7390 \begin_layout Plain Layout
7391 Kompresním poměrem se zde rozumí poměr nekomprimované velikosti ke komprimované,
7393 \begin_inset Quotes gld
7396 nekomprimovaného obrázku
7397 \begin_inset Quotes grd
7401 \begin_inset space ~
7404 bytech je dána jako počet jeho pixelů (obrázky jsou černobílé).
7409 Doby fraktální i standardní komprese byly získány jednovláknovým spouštěním
7411 \begin_inset space ~
7414 dávkovém režimu (bez GUI) na počítači s
7415 \begin_inset space ~
7419 \begin_inset space ~
7423 \begin_inset space \thinspace{}
7426 GHz, systémem Gentoo Linux a kompilátorem GCC verze 4.2.1.
7429 \begin_layout Standard
7430 Následují tři skupiny testů zaměřené na vyhodnocení konkrétních částí komprese
7431 a jedna zkoumající celkový výsledek.
7432 Parametry modulů, které nejsou uvedeny, jsou vždy nechávány na přednastavených
7436 \begin_layout Section
7440 \begin_layout Standard
7442 \begin_inset space ~
7446 \begin_inset space ~
7450 \begin_inset CommandInset ref
7452 reference "Chyba_zobrazení/Penalizace"
7456 byla navržena alternativa k
7457 \begin_inset space ~
7460 omezení absolutní hodnoty lineárních koficientů barevných zobrazení mezi
7461 bloky a bylo zdůvodněno, proč by to mělo být výhodnější.
7462 Zde bude porovnán vliv penalizace a omezení koeficientů na kvalitu a kompresní
7464 Aby bylo hodnocení vlivu objektivnější, je pro predikci zvolen modul
7471 a je zrušen limit pro předčasné ukončení hledání, tedy jsou vždy zkoušeny
7472 všechny zdrojové bloky.
7475 \begin_layout Standard
7476 Výsledky testů jsou v
7477 \begin_inset space ~
7481 \begin_inset space ~
7485 \begin_inset CommandInset ref
7487 reference "Testování/Penalizace/Tabulka"
7492 Pro šest obrázků a několik nastavení míry penalizace nebo omezení koeficientů
7493 je změřen kompresní poměr a hodnota PSNR.
7494 Absolutní hodnoty lineárních koeficientů barevných zobrazení jsou omezovány
7496 \begin_inset space ~
7506 ) tak, že kombinace bloků, kde by byla hodnota příliš vysoká, nejsou uvažovány.
7509 \begin_layout Standard
7510 Výrazně nejhorší výsledky vyšly pro nastavení, kde není použita ani jedna
7512 \begin_inset space ~
7516 Omezení koeficientů pod
7517 \begin_inset Formula $1.0$
7520 nutné pro zaručení konvergence dekódování sice dává dobré výsledky pro
7530 \begin_inset space ~
7533 ostatních případech je kvalita hluboko pod nejlepším výsledkem.
7534 Proto je často omezení uvolněno a jsou dovoleny i hodnoty vyšší (zkoumáno
7536 \begin_inset space ~
7540 \begin_inset space ~
7544 \begin_inset space ~
7548 \begin_inset CommandInset citation
7556 \begin_inset space ~
7559 výraznému zlepšení a kvalita většiny obrázků se přiblíží k
7560 \begin_inset space ~
7563 nejlepším hodnotám dosaženým v
7564 \begin_inset space ~
7569 \begin_inset space ~
7576 je PSNR stále více než
7577 \begin_inset Formula $0.9$
7581 \begin_inset space \thinspace{}
7587 \begin_layout Standard
7588 Při použití penalizace místo omezení lineárních koeficientů vycházejí nepatrně
7589 nižší kopresní poměry, ale kvalita se pohybuje blízko nejvyšší hodnoty
7591 \begin_inset space ~
7594 všech testovaných obrázků.
7596 \begin_inset space ~
7599 implicitním nastavení proto nejsou omezeny lineární koeficenty zobrazení
7600 mezi bloky a je použita penalizace s
7601 \begin_inset space ~
7605 \begin_inset Formula $0.25$
7608 (kompromis mezi kvalitou a kompresním poměrem).
7611 \begin_layout Standard
7612 \begin_inset Float table
7617 \begin_layout Plain Layout
7618 \begin_inset Caption
7620 \begin_layout Plain Layout
7621 \begin_inset CommandInset label
7623 name "Testování/Penalizace/Tabulka"
7627 Testování účinností penalizace a omezení koeficientů
7635 \begin_layout Plain Layout
7638 \begin_inset Tabular
7639 <lyxtabular version="3" rows="32" columns="5">
7641 <column alignment="center" valignment="top" width="0">
7642 <column alignment="center" valignment="top" width="0">
7643 <column alignment="center" valignment="top" width="0">
7644 <column alignment="center" valignment="top" width="0">
7645 <column alignment="center" valignment="top" width="0">
7647 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
7650 \begin_layout Plain Layout
7656 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
7659 \begin_layout Plain Layout
7667 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
7670 \begin_layout Plain Layout
7678 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
7681 \begin_layout Plain Layout
7689 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
7692 \begin_layout Plain Layout
7702 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
7705 \begin_layout Plain Layout
7713 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
7716 \begin_layout Plain Layout
7724 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
7727 \begin_layout Plain Layout
7735 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
7738 \begin_layout Plain Layout
7746 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
7749 \begin_layout Plain Layout
7759 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
7762 \begin_layout Plain Layout
7770 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
7773 \begin_layout Plain Layout
7781 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
7784 \begin_layout Plain Layout
7792 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
7795 \begin_layout Plain Layout
7803 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
7806 \begin_layout Plain Layout
7816 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7819 \begin_layout Plain Layout
7825 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7828 \begin_layout Plain Layout
7836 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7839 \begin_layout Plain Layout
7847 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7850 \begin_layout Plain Layout
7858 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
7861 \begin_layout Plain Layout
7872 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7875 \begin_layout Plain Layout
7881 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7884 \begin_layout Plain Layout
7892 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7895 \begin_layout Plain Layout
7903 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7906 \begin_layout Plain Layout
7914 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
7917 \begin_layout Plain Layout
7928 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7931 \begin_layout Plain Layout
7937 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7940 \begin_layout Plain Layout
7948 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7951 \begin_layout Plain Layout
7959 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7962 \begin_layout Plain Layout
7970 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
7973 \begin_layout Plain Layout
7984 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7987 \begin_layout Plain Layout
7993 <cell alignment="center" valignment="top" leftline="true" usebox="none">
7996 \begin_layout Plain Layout
8004 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8007 \begin_layout Plain Layout
8015 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8018 \begin_layout Plain Layout
8026 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8029 \begin_layout Plain Layout
8039 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8042 \begin_layout Plain Layout
8048 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8051 \begin_layout Plain Layout
8059 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8062 \begin_layout Plain Layout
8070 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8073 \begin_layout Plain Layout
8081 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8084 \begin_layout Plain Layout
8094 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8097 \begin_layout Plain Layout
8103 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8106 \begin_layout Plain Layout
8114 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8117 \begin_layout Plain Layout
8125 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8128 \begin_layout Plain Layout
8136 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8139 \begin_layout Plain Layout
8149 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8152 \begin_layout Plain Layout
8158 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8161 \begin_layout Plain Layout
8169 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8172 \begin_layout Plain Layout
8180 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8183 \begin_layout Plain Layout
8191 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8194 \begin_layout Plain Layout
8204 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8207 \begin_layout Plain Layout
8213 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8216 \begin_layout Plain Layout
8224 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8227 \begin_layout Plain Layout
8235 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8238 \begin_layout Plain Layout
8246 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8249 \begin_layout Plain Layout
8259 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8262 \begin_layout Plain Layout
8268 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8271 \begin_layout Plain Layout
8279 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8282 \begin_layout Plain Layout
8290 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8293 \begin_layout Plain Layout
8301 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8304 \begin_layout Plain Layout
8314 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8317 \begin_layout Plain Layout
8325 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8328 \begin_layout Plain Layout
8336 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8339 \begin_layout Plain Layout
8347 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
8350 \begin_layout Plain Layout
8358 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
8361 \begin_layout Plain Layout
8371 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8374 \begin_layout Plain Layout
8380 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8383 \begin_layout Plain Layout
8391 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8394 \begin_layout Plain Layout
8402 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8405 \begin_layout Plain Layout
8413 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8416 \begin_layout Plain Layout
8426 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8429 \begin_layout Plain Layout
8435 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8438 \begin_layout Plain Layout
8446 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8449 \begin_layout Plain Layout
8457 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8460 \begin_layout Plain Layout
8468 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8471 \begin_layout Plain Layout
8481 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8484 \begin_layout Plain Layout
8490 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8493 \begin_layout Plain Layout
8501 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8504 \begin_layout Plain Layout
8512 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8515 \begin_layout Plain Layout
8523 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8526 \begin_layout Plain Layout
8537 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8540 \begin_layout Plain Layout
8546 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8549 \begin_layout Plain Layout
8557 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8560 \begin_layout Plain Layout
8568 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8571 \begin_layout Plain Layout
8579 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8582 \begin_layout Plain Layout
8593 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8596 \begin_layout Plain Layout
8602 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8605 \begin_layout Plain Layout
8613 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8616 \begin_layout Plain Layout
8624 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8627 \begin_layout Plain Layout
8635 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8638 \begin_layout Plain Layout
8648 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8651 \begin_layout Plain Layout
8657 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8660 \begin_layout Plain Layout
8668 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8671 \begin_layout Plain Layout
8679 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8682 \begin_layout Plain Layout
8690 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8693 \begin_layout Plain Layout
8703 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8706 \begin_layout Plain Layout
8712 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8715 \begin_layout Plain Layout
8723 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8726 \begin_layout Plain Layout
8734 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8737 \begin_layout Plain Layout
8745 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8748 \begin_layout Plain Layout
8758 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8761 \begin_layout Plain Layout
8767 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8770 \begin_layout Plain Layout
8778 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8781 \begin_layout Plain Layout
8789 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8792 \begin_layout Plain Layout
8800 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8803 \begin_layout Plain Layout
8813 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
8816 \begin_layout Plain Layout
8822 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
8825 \begin_layout Plain Layout
8833 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
8836 \begin_layout Plain Layout
8844 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
8847 \begin_layout Plain Layout
8855 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
8858 \begin_layout Plain Layout
8868 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8871 \begin_layout Plain Layout
8879 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8882 \begin_layout Plain Layout
8890 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8893 \begin_layout Plain Layout
8901 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8904 \begin_layout Plain Layout
8912 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8915 \begin_layout Plain Layout
8925 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8928 \begin_layout Plain Layout
8934 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8937 \begin_layout Plain Layout
8945 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8948 \begin_layout Plain Layout
8956 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8959 \begin_layout Plain Layout
8967 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
8970 \begin_layout Plain Layout
8980 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8983 \begin_layout Plain Layout
8989 <cell alignment="center" valignment="top" leftline="true" usebox="none">
8992 \begin_layout Plain Layout
9000 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9003 \begin_layout Plain Layout
9011 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9014 \begin_layout Plain Layout
9022 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9025 \begin_layout Plain Layout
9035 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9038 \begin_layout Plain Layout
9044 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9047 \begin_layout Plain Layout
9055 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9058 \begin_layout Plain Layout
9066 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9069 \begin_layout Plain Layout
9077 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9080 \begin_layout Plain Layout
9091 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9094 \begin_layout Plain Layout
9100 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9103 \begin_layout Plain Layout
9111 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9114 \begin_layout Plain Layout
9122 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9125 \begin_layout Plain Layout
9133 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9136 \begin_layout Plain Layout
9147 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9150 \begin_layout Plain Layout
9156 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9159 \begin_layout Plain Layout
9167 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9170 \begin_layout Plain Layout
9178 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9181 \begin_layout Plain Layout
9189 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9192 \begin_layout Plain Layout
9203 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9206 \begin_layout Plain Layout
9212 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9215 \begin_layout Plain Layout
9223 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9226 \begin_layout Plain Layout
9234 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9237 \begin_layout Plain Layout
9245 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9248 \begin_layout Plain Layout
9258 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9261 \begin_layout Plain Layout
9267 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9270 \begin_layout Plain Layout
9278 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9281 \begin_layout Plain Layout
9289 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9292 \begin_layout Plain Layout
9300 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9303 \begin_layout Plain Layout
9313 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9316 \begin_layout Plain Layout
9322 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9325 \begin_layout Plain Layout
9333 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9336 \begin_layout Plain Layout
9344 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9347 \begin_layout Plain Layout
9355 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9358 \begin_layout Plain Layout
9368 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9371 \begin_layout Plain Layout
9377 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9380 \begin_layout Plain Layout
9388 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9391 \begin_layout Plain Layout
9399 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9402 \begin_layout Plain Layout
9410 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
9413 \begin_layout Plain Layout
9427 \begin_inset space \hfill{}
9431 \begin_inset Tabular
9432 <lyxtabular version="3" rows="32" columns="5">
9434 <column alignment="center" valignment="top" width="0">
9435 <column alignment="center" valignment="top" width="0">
9436 <column alignment="center" valignment="top" width="0">
9437 <column alignment="center" valignment="top" width="0">
9438 <column alignment="center" valignment="top" width="0">
9440 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9443 \begin_layout Plain Layout
9449 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9452 \begin_layout Plain Layout
9460 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9463 \begin_layout Plain Layout
9471 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9474 \begin_layout Plain Layout
9482 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
9485 \begin_layout Plain Layout
9495 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9498 \begin_layout Plain Layout
9506 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9509 \begin_layout Plain Layout
9517 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9520 \begin_layout Plain Layout
9528 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
9531 \begin_layout Plain Layout
9539 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
9542 \begin_layout Plain Layout
9552 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9555 \begin_layout Plain Layout
9563 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9566 \begin_layout Plain Layout
9574 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9577 \begin_layout Plain Layout
9585 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
9588 \begin_layout Plain Layout
9596 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
9599 \begin_layout Plain Layout
9609 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9612 \begin_layout Plain Layout
9618 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9621 \begin_layout Plain Layout
9629 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9632 \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" rightline="true" usebox="none">
9654 \begin_layout Plain Layout
9664 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9667 \begin_layout Plain Layout
9673 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9676 \begin_layout Plain Layout
9684 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9687 \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" rightline="true" usebox="none">
9709 \begin_layout Plain Layout
9720 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9723 \begin_layout Plain Layout
9729 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9732 \begin_layout Plain Layout
9740 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9743 \begin_layout Plain Layout
9751 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9754 \begin_layout Plain Layout
9762 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9765 \begin_layout Plain Layout
9776 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9779 \begin_layout Plain Layout
9785 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9788 \begin_layout Plain Layout
9796 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9799 \begin_layout Plain Layout
9807 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9810 \begin_layout Plain Layout
9818 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9821 \begin_layout Plain Layout
9832 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9835 \begin_layout Plain Layout
9841 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9844 \begin_layout Plain Layout
9852 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9855 \begin_layout Plain Layout
9863 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9866 \begin_layout Plain Layout
9874 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9877 \begin_layout Plain Layout
9887 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9890 \begin_layout Plain Layout
9896 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9899 \begin_layout Plain Layout
9907 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9910 \begin_layout Plain Layout
9918 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9921 \begin_layout Plain Layout
9929 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9932 \begin_layout Plain Layout
9942 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9945 \begin_layout Plain Layout
9951 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9954 \begin_layout Plain Layout
9962 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9965 \begin_layout Plain Layout
9973 <cell alignment="center" valignment="top" leftline="true" usebox="none">
9976 \begin_layout Plain Layout
9984 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
9987 \begin_layout Plain Layout
9997 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10000 \begin_layout Plain Layout
10006 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10009 \begin_layout Plain Layout
10017 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10020 \begin_layout Plain Layout
10028 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10031 \begin_layout Plain Layout
10039 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10042 \begin_layout Plain Layout
10052 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10055 \begin_layout Plain Layout
10061 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10064 \begin_layout Plain Layout
10072 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10075 \begin_layout Plain Layout
10083 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10086 \begin_layout Plain Layout
10094 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10097 \begin_layout Plain Layout
10107 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
10110 \begin_layout Plain Layout
10118 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
10121 \begin_layout Plain Layout
10129 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
10132 \begin_layout Plain Layout
10140 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
10143 \begin_layout Plain Layout
10151 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
10154 \begin_layout Plain Layout
10164 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10167 \begin_layout Plain Layout
10173 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10176 \begin_layout Plain Layout
10184 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10187 \begin_layout Plain Layout
10195 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10198 \begin_layout Plain Layout
10206 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10209 \begin_layout Plain Layout
10219 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10222 \begin_layout Plain Layout
10228 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10231 \begin_layout Plain Layout
10239 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10242 \begin_layout Plain Layout
10250 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10253 \begin_layout Plain Layout
10261 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10264 \begin_layout Plain Layout
10274 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10277 \begin_layout Plain Layout
10283 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10286 \begin_layout Plain Layout
10294 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10297 \begin_layout Plain Layout
10305 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10308 \begin_layout Plain Layout
10316 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10319 \begin_layout Plain Layout
10330 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10333 \begin_layout Plain Layout
10339 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10342 \begin_layout Plain Layout
10350 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10353 \begin_layout Plain Layout
10361 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10364 \begin_layout Plain Layout
10372 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10375 \begin_layout Plain Layout
10385 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10388 \begin_layout Plain Layout
10394 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10397 \begin_layout Plain Layout
10405 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10408 \begin_layout Plain Layout
10416 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10419 \begin_layout Plain Layout
10427 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10430 \begin_layout Plain Layout
10440 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10443 \begin_layout Plain Layout
10449 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10452 \begin_layout Plain Layout
10460 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10463 \begin_layout Plain Layout
10471 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10474 \begin_layout Plain Layout
10482 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10485 \begin_layout Plain Layout
10495 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10498 \begin_layout Plain Layout
10504 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10507 \begin_layout Plain Layout
10515 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10518 \begin_layout Plain Layout
10526 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10529 \begin_layout Plain Layout
10537 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10540 \begin_layout Plain Layout
10550 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10553 \begin_layout Plain Layout
10559 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10562 \begin_layout Plain Layout
10570 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10573 \begin_layout Plain Layout
10581 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10584 \begin_layout Plain Layout
10592 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10595 \begin_layout Plain Layout
10605 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
10608 \begin_layout Plain Layout
10614 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
10617 \begin_layout Plain Layout
10625 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
10628 \begin_layout Plain Layout
10636 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
10639 \begin_layout Plain Layout
10647 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
10650 \begin_layout Plain Layout
10660 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10663 \begin_layout Plain Layout
10671 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10674 \begin_layout Plain Layout
10682 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10685 \begin_layout Plain Layout
10693 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10696 \begin_layout Plain Layout
10704 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10707 \begin_layout Plain Layout
10717 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10720 \begin_layout Plain Layout
10726 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10729 \begin_layout Plain Layout
10737 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10740 \begin_layout Plain Layout
10748 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10751 \begin_layout Plain Layout
10759 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10762 \begin_layout Plain Layout
10772 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10775 \begin_layout Plain Layout
10781 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10784 \begin_layout Plain Layout
10792 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10795 \begin_layout Plain Layout
10803 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10806 \begin_layout Plain Layout
10814 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10817 \begin_layout Plain Layout
10827 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10830 \begin_layout Plain Layout
10836 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10839 \begin_layout Plain Layout
10847 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10850 \begin_layout Plain Layout
10858 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10861 \begin_layout Plain Layout
10869 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10872 \begin_layout Plain Layout
10883 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10886 \begin_layout Plain Layout
10892 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10895 \begin_layout Plain Layout
10903 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10906 \begin_layout Plain Layout
10914 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10917 \begin_layout Plain Layout
10925 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10928 \begin_layout Plain Layout
10938 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10941 \begin_layout Plain Layout
10947 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10950 \begin_layout Plain Layout
10958 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10961 \begin_layout Plain Layout
10969 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10972 \begin_layout Plain Layout
10980 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
10983 \begin_layout Plain Layout
10993 <cell alignment="center" valignment="top" leftline="true" usebox="none">
10996 \begin_layout Plain Layout
11002 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11005 \begin_layout Plain Layout
11013 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11016 \begin_layout Plain Layout
11024 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11027 \begin_layout Plain Layout
11035 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11038 \begin_layout Plain Layout
11048 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11051 \begin_layout Plain Layout
11057 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11060 \begin_layout Plain Layout
11068 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11071 \begin_layout Plain Layout
11079 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11082 \begin_layout Plain Layout
11090 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11093 \begin_layout Plain Layout
11103 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11106 \begin_layout Plain Layout
11112 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11115 \begin_layout Plain Layout
11123 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11126 \begin_layout Plain Layout
11134 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11137 \begin_layout Plain Layout
11145 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11148 \begin_layout Plain Layout
11158 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11161 \begin_layout Plain Layout
11167 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11170 \begin_layout Plain Layout
11178 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11181 \begin_layout Plain Layout
11189 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11192 \begin_layout Plain Layout
11200 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
11203 \begin_layout Plain Layout
11224 \begin_layout Section
11228 \begin_layout Standard
11229 Zkoušení všech zdrojových bloků pro každý cílový je neúnosně zdlouhavý proces.
11230 Proto je podstatná efektivní predikce.
11232 \begin_inset space ~
11235 této části je zkoumána účinnost predikce modulem popsaným v
11236 \begin_inset space ~
11240 \begin_inset CommandInset ref
11242 reference "Implementace/Predikce"
11249 \begin_layout Standard
11251 \begin_inset space ~
11255 \begin_inset CommandInset ref
11257 reference "Testování/Predikce/Tabulka"
11261 ukazuje pro různá množství zdrojových bloků dosaženou kvalitu, kompresní
11262 poměr a spotřebovaný čas.
11263 Hodnoty jsou naměřeny vždy pro různá nastavení limitu na predikovanou část
11264 ze všech bloků včetně varianty s
11265 \begin_inset space ~
11268 úplným prohledáváním místo predikce.
11272 \begin_layout Standard
11273 \begin_inset Float table
11278 \begin_layout Plain Layout
11279 \begin_inset Caption
11281 \begin_layout Plain Layout
11282 \begin_inset CommandInset label
11284 name "Testování/Predikce/Tabulka"
11288 Testování účinnosti predikce
11296 \begin_layout Plain Layout
11299 \begin_inset space \hfill{}
11303 \begin_inset Tabular
11304 <lyxtabular version="3" rows="38" columns="6">
11306 <column alignment="center" valignment="top" width="0">
11307 <column alignment="center" valignment="top" width="0">
11308 <column alignment="center" valignment="top" width="0">
11309 <column alignment="center" valignment="top" width="0">
11310 <column alignment="center" valignment="top" width="0">
11311 <column alignment="center" valignment="top" width="0">
11313 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11316 \begin_layout Plain Layout
11322 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11325 \begin_layout Plain Layout
11333 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11336 \begin_layout Plain Layout
11344 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11347 \begin_layout Plain Layout
11355 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11358 \begin_layout Plain Layout
11366 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
11369 \begin_layout Plain Layout
11377 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11380 \begin_layout Plain Layout
11388 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11391 \begin_layout Plain Layout
11399 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11402 \begin_layout Plain Layout
11410 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11413 \begin_layout Plain Layout
11421 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11424 \begin_layout Plain Layout
11432 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
11435 \begin_layout Plain Layout
11445 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11448 \begin_layout Plain Layout
11456 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11459 \begin_layout Plain Layout
11462 \begin_inset Formula $2^{11}$
11470 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11473 \begin_layout Plain Layout
11476 \begin_inset Formula $2^{-10}$
11484 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11487 \begin_layout Plain Layout
11495 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11498 \begin_layout Plain Layout
11506 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
11509 \begin_layout Plain Layout
11519 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11522 \begin_layout Plain Layout
11528 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11531 \begin_layout Plain Layout
11537 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11540 \begin_layout Plain Layout
11543 \begin_inset Formula $2^{-8}$
11551 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11554 \begin_layout Plain Layout
11562 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11565 \begin_layout Plain Layout
11573 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11576 \begin_layout Plain Layout
11586 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11589 \begin_layout Plain Layout
11595 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11598 \begin_layout Plain Layout
11604 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11607 \begin_layout Plain Layout
11610 \begin_inset Formula $2^{-6}$
11618 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11621 \begin_layout Plain Layout
11629 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11632 \begin_layout Plain Layout
11640 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11643 \begin_layout Plain Layout
11653 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11656 \begin_layout Plain Layout
11662 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11665 \begin_layout Plain Layout
11671 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11674 \begin_layout Plain Layout
11682 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11685 \begin_layout Plain Layout
11693 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
11696 \begin_layout Plain Layout
11704 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
11707 \begin_layout Plain Layout
11717 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11720 \begin_layout Plain Layout
11726 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11729 \begin_layout Plain Layout
11732 \begin_inset Formula $2^{15}$
11740 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11743 \begin_layout Plain Layout
11746 \begin_inset Formula $2^{-10}$
11754 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11757 \begin_layout Plain Layout
11765 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11768 \begin_layout Plain Layout
11776 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11779 \begin_layout Plain Layout
11789 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11792 \begin_layout Plain Layout
11798 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11801 \begin_layout Plain Layout
11807 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11810 \begin_layout Plain Layout
11813 \begin_inset Formula $2^{-8}$
11821 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11824 \begin_layout Plain Layout
11832 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11835 \begin_layout Plain Layout
11843 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11846 \begin_layout Plain Layout
11856 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11859 \begin_layout Plain Layout
11865 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11868 \begin_layout Plain Layout
11874 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11877 \begin_layout Plain Layout
11880 \begin_inset Formula $2^{-6}$
11888 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11891 \begin_layout Plain Layout
11899 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11902 \begin_layout Plain Layout
11910 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11913 \begin_layout Plain Layout
11923 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11926 \begin_layout Plain Layout
11932 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11935 \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" usebox="none">
11955 \begin_layout Plain Layout
11963 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11966 \begin_layout Plain Layout
11974 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
11977 \begin_layout Plain Layout
11987 <cell alignment="center" valignment="top" leftline="true" usebox="none">
11990 \begin_layout Plain Layout
11996 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
11999 \begin_layout Plain Layout
12002 \begin_inset Formula $2^{19}$
12010 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12013 \begin_layout Plain Layout
12016 \begin_inset Formula $2^{-10}$
12024 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12027 \begin_layout Plain Layout
12035 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12038 \begin_layout Plain Layout
12046 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
12049 \begin_layout Plain Layout
12059 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12062 \begin_layout Plain Layout
12068 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12071 \begin_layout Plain Layout
12077 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12080 \begin_layout Plain Layout
12083 \begin_inset Formula $2^{-8}$
12091 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12094 \begin_layout Plain Layout
12102 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12105 \begin_layout Plain Layout
12113 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12116 \begin_layout Plain Layout
12126 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12129 \begin_layout Plain Layout
12135 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12138 \begin_layout Plain Layout
12144 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12147 \begin_layout Plain Layout
12150 \begin_inset Formula $2^{-6}$
12158 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12161 \begin_layout Plain Layout
12169 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12172 \begin_layout Plain Layout
12180 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12183 \begin_layout Plain Layout
12193 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12196 \begin_layout Plain Layout
12202 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12205 \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" usebox="none">
12225 \begin_layout Plain Layout
12233 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12236 \begin_layout Plain Layout
12244 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12247 \begin_layout Plain Layout
12257 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12260 \begin_layout Plain Layout
12268 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12271 \begin_layout Plain Layout
12274 \begin_inset Formula $2^{11}$
12282 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12285 \begin_layout Plain Layout
12288 \begin_inset Formula $2^{-10}$
12296 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12299 \begin_layout Plain Layout
12307 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
12310 \begin_layout Plain Layout
12318 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
12321 \begin_layout Plain Layout
12331 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12334 \begin_layout Plain Layout
12340 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12343 \begin_layout Plain Layout
12349 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12352 \begin_layout Plain Layout
12355 \begin_inset Formula $2^{-8}$
12363 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12366 \begin_layout Plain Layout
12374 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12377 \begin_layout Plain Layout
12385 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12388 \begin_layout Plain Layout
12398 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12401 \begin_layout Plain Layout
12407 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12410 \begin_layout Plain Layout
12416 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12419 \begin_layout Plain Layout
12422 \begin_inset Formula $2^{-6}$
12430 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12433 \begin_layout Plain Layout
12441 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12444 \begin_layout Plain Layout
12452 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12455 \begin_layout Plain Layout
12465 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12468 \begin_layout Plain Layout
12474 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12477 \begin_layout Plain Layout
12483 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12486 \begin_layout Plain Layout
12494 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12497 \begin_layout Plain Layout
12505 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12508 \begin_layout Plain Layout
12516 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
12519 \begin_layout Plain Layout
12529 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12532 \begin_layout Plain Layout
12538 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12541 \begin_layout Plain Layout
12544 \begin_inset Formula $2^{15}$
12552 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12555 \begin_layout Plain Layout
12558 \begin_inset Formula $2^{-10}$
12566 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12569 \begin_layout Plain Layout
12577 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12580 \begin_layout Plain Layout
12588 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12591 \begin_layout Plain Layout
12601 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12604 \begin_layout Plain Layout
12610 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12613 \begin_layout Plain Layout
12619 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12622 \begin_layout Plain Layout
12625 \begin_inset Formula $2^{-8}$
12633 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12636 \begin_layout Plain Layout
12644 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12647 \begin_layout Plain Layout
12655 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12658 \begin_layout Plain Layout
12668 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12671 \begin_layout Plain Layout
12677 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12680 \begin_layout Plain Layout
12686 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12689 \begin_layout Plain Layout
12692 \begin_inset Formula $2^{-6}$
12700 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12703 \begin_layout Plain Layout
12711 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12714 \begin_layout Plain Layout
12722 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12725 \begin_layout Plain Layout
12735 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12738 \begin_layout Plain Layout
12744 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12747 \begin_layout Plain Layout
12753 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12756 \begin_layout Plain Layout
12764 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12767 \begin_layout Plain Layout
12775 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
12778 \begin_layout Plain Layout
12786 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
12789 \begin_layout Plain Layout
12799 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12802 \begin_layout Plain Layout
12808 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12811 \begin_layout Plain Layout
12814 \begin_inset Formula $2^{19}$
12822 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12825 \begin_layout Plain Layout
12828 \begin_inset Formula $2^{-10}$
12836 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12839 \begin_layout Plain Layout
12847 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12850 \begin_layout Plain Layout
12858 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12861 \begin_layout Plain Layout
12871 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12874 \begin_layout Plain Layout
12880 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12883 \begin_layout Plain Layout
12889 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12892 \begin_layout Plain Layout
12895 \begin_inset Formula $2^{-8}$
12903 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12906 \begin_layout Plain Layout
12914 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12917 \begin_layout Plain Layout
12925 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12928 \begin_layout Plain Layout
12938 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12941 \begin_layout Plain Layout
12947 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12950 \begin_layout Plain Layout
12956 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12959 \begin_layout Plain Layout
12962 \begin_inset Formula $2^{-6}$
12970 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12973 \begin_layout Plain Layout
12981 <cell alignment="center" valignment="top" leftline="true" usebox="none">
12984 \begin_layout Plain Layout
12992 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
12995 \begin_layout Plain Layout
13005 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13008 \begin_layout Plain Layout
13014 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13017 \begin_layout Plain Layout
13023 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13026 \begin_layout Plain Layout
13034 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13037 \begin_layout Plain Layout
13045 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13048 \begin_layout Plain Layout
13056 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
13059 \begin_layout Plain Layout
13069 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13072 \begin_layout Plain Layout
13080 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13083 \begin_layout Plain Layout
13086 \begin_inset Formula $2^{11}$
13094 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13097 \begin_layout Plain Layout
13100 \begin_inset Formula $2^{-10}$
13108 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13111 \begin_layout Plain Layout
13119 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13122 \begin_layout Plain Layout
13130 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13133 \begin_layout Plain Layout
13143 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13146 \begin_layout Plain Layout
13152 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13155 \begin_layout Plain Layout
13161 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13164 \begin_layout Plain Layout
13167 \begin_inset Formula $2^{-8}$
13175 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13178 \begin_layout Plain Layout
13186 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13189 \begin_layout Plain Layout
13197 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13200 \begin_layout Plain Layout
13210 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13213 \begin_layout Plain Layout
13219 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13222 \begin_layout Plain Layout
13228 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13231 \begin_layout Plain Layout
13234 \begin_inset Formula $2^{-6}$
13242 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13245 \begin_layout Plain Layout
13253 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13256 \begin_layout Plain Layout
13264 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13267 \begin_layout Plain Layout
13277 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13280 \begin_layout Plain Layout
13286 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13289 \begin_layout Plain Layout
13295 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13298 \begin_layout Plain Layout
13306 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13309 \begin_layout Plain Layout
13317 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13320 \begin_layout Plain Layout
13328 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13331 \begin_layout Plain Layout
13341 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13344 \begin_layout Plain Layout
13350 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13353 \begin_layout Plain Layout
13356 \begin_inset Formula $2^{15}$
13364 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13367 \begin_layout Plain Layout
13370 \begin_inset Formula $2^{-10}$
13378 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13381 \begin_layout Plain Layout
13389 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13392 \begin_layout Plain Layout
13400 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
13403 \begin_layout Plain Layout
13413 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13416 \begin_layout Plain Layout
13422 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13425 \begin_layout Plain Layout
13431 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13434 \begin_layout Plain Layout
13437 \begin_inset Formula $2^{-8}$
13445 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13448 \begin_layout Plain Layout
13456 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13459 \begin_layout Plain Layout
13467 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13470 \begin_layout Plain Layout
13480 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13483 \begin_layout Plain Layout
13489 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13492 \begin_layout Plain Layout
13498 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13501 \begin_layout Plain Layout
13504 \begin_inset Formula $2^{-6}$
13512 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13515 \begin_layout Plain Layout
13523 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13526 \begin_layout Plain Layout
13534 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13537 \begin_layout Plain Layout
13547 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13550 \begin_layout Plain Layout
13556 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13559 \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" usebox="none">
13579 \begin_layout Plain Layout
13587 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13590 \begin_layout Plain Layout
13598 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13601 \begin_layout Plain Layout
13611 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13614 \begin_layout Plain Layout
13620 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13623 \begin_layout Plain Layout
13626 \begin_inset Formula $2^{19}$
13634 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13637 \begin_layout Plain Layout
13640 \begin_inset Formula $2^{-10}$
13648 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13651 \begin_layout Plain Layout
13659 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13662 \begin_layout Plain Layout
13670 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
13673 \begin_layout Plain Layout
13683 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13686 \begin_layout Plain Layout
13692 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13695 \begin_layout Plain Layout
13701 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13704 \begin_layout Plain Layout
13707 \begin_inset Formula $2^{-8}$
13715 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13718 \begin_layout Plain Layout
13726 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13729 \begin_layout Plain Layout
13737 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13740 \begin_layout Plain Layout
13750 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13753 \begin_layout Plain Layout
13759 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13762 \begin_layout Plain Layout
13768 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13771 \begin_layout Plain Layout
13774 \begin_inset Formula $2^{-6}$
13782 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13785 \begin_layout Plain Layout
13793 <cell alignment="center" valignment="top" leftline="true" usebox="none">
13796 \begin_layout Plain Layout
13804 <cell alignment="center" valignment="top" leftline="true" rightline="true" usebox="none">
13807 \begin_layout Plain Layout
13817 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13820 \begin_layout Plain Layout
13826 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13829 \begin_layout Plain Layout
13835 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13838 \begin_layout Plain Layout
13846 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13849 \begin_layout Plain Layout
13857 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
13860 \begin_layout Plain Layout
13868 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
13871 \begin_layout Plain Layout
13885 \begin_inset Note Note
13888 \begin_layout Plain Layout
13891 \begin_inset Tabular
13892 <lyxtabular version="3" rows="11" columns="6">
13894 <column alignment="center" valignment="top" width="0">
13895 <column alignment="center" valignment="top" width="0">
13896 <column alignment="center" valignment="top" width="0">
13897 <column alignment="center" valignment="top" width="0">
13898 <column alignment="center" valignment="top" width="0">
13899 <column alignment="center" valignment="top" width="0">
13901 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13904 \begin_layout Plain Layout
13912 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13915 \begin_layout Plain Layout
13918 \begin_inset Formula $2^{11}$
13926 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13929 \begin_layout Plain Layout
13932 \begin_inset Formula $2^{-10}$
13940 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13943 \begin_layout Plain Layout
13951 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13954 \begin_layout Plain Layout
13962 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
13965 \begin_layout Plain Layout
13975 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13978 \begin_layout Plain Layout
13984 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13987 \begin_layout Plain Layout
13993 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
13996 \begin_layout Plain Layout
13999 \begin_inset Formula $2^{-8}$
14007 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14010 \begin_layout Plain Layout
14018 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14021 \begin_layout Plain Layout
14029 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14032 \begin_layout Plain Layout
14042 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14045 \begin_layout Plain Layout
14051 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14054 \begin_layout Plain Layout
14060 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14063 \begin_layout Plain Layout
14066 \begin_inset Formula $2^{-6}$
14074 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14077 \begin_layout Plain Layout
14085 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14088 \begin_layout Plain Layout
14096 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14099 \begin_layout Plain Layout
14109 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14112 \begin_layout Plain Layout
14118 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14121 \begin_layout Plain Layout
14127 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14130 \begin_layout Plain Layout
14138 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14141 \begin_layout Plain Layout
14149 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14152 \begin_layout Plain Layout
14160 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14163 \begin_layout Plain Layout
14173 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14176 \begin_layout Plain Layout
14182 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14185 \begin_layout Plain Layout
14188 \begin_inset Formula $2^{15}$
14196 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14199 \begin_layout Plain Layout
14202 \begin_inset Formula $2^{-10}$
14210 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14213 \begin_layout Plain Layout
14221 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14224 \begin_layout Plain Layout
14232 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14235 \begin_layout Plain Layout
14245 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14248 \begin_layout Plain Layout
14254 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14257 \begin_layout Plain Layout
14263 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14266 \begin_layout Plain Layout
14269 \begin_inset Formula $2^{-8}$
14277 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14280 \begin_layout Plain Layout
14288 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14291 \begin_layout Plain Layout
14299 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14302 \begin_layout Plain Layout
14312 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14315 \begin_layout Plain Layout
14321 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14324 \begin_layout Plain Layout
14330 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14333 \begin_layout Plain Layout
14336 \begin_inset Formula $2^{-6}$
14344 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14347 \begin_layout Plain Layout
14355 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14358 \begin_layout Plain Layout
14366 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14369 \begin_layout Plain Layout
14379 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14382 \begin_layout Plain Layout
14388 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14391 \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" usebox="none">
14411 \begin_layout Plain Layout
14419 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14422 \begin_layout Plain Layout
14430 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14433 \begin_layout Plain Layout
14443 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14446 \begin_layout Plain Layout
14452 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14455 \begin_layout Plain Layout
14458 \begin_inset Formula $2^{19}$
14466 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14469 \begin_layout Plain Layout
14472 \begin_inset Formula $2^{-10}$
14480 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14483 \begin_layout Plain Layout
14491 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14494 \begin_layout Plain Layout
14502 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14505 \begin_layout Plain Layout
14515 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14518 \begin_layout Plain Layout
14524 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14527 \begin_layout Plain Layout
14533 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14536 \begin_layout Plain Layout
14539 \begin_inset Formula $2^{-8}$
14547 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14550 \begin_layout Plain Layout
14558 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
14561 \begin_layout Plain Layout
14569 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
14572 \begin_layout Plain Layout
14582 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14585 \begin_layout Plain Layout
14591 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14594 \begin_layout Plain Layout
14600 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14603 \begin_layout Plain Layout
14606 \begin_inset Formula $2^{-6}$
14614 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14617 \begin_layout Plain Layout
14625 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14628 \begin_layout Plain Layout
14636 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
14639 \begin_layout Plain Layout
14658 \begin_inset space \hfill{}
14669 \begin_layout Standard
14671 \begin_inset space ~
14674 výsledků je především vidět, že při malém množství zdrojových bloků je implement
14675 ovaná predikce velmi nevýhodná
14676 \begin_inset space ~
14680 \begin_inset space ~
14683 výrazně horší kvalitě i horšímu kompresnímu poměru při relativně malém množství
14685 To je nejspíše způsobeno vysokým počtem dimenzí prostoru indexovaného KD-strome
14687 Množství zdrojových bloků je uvažováno i s
14688 \begin_inset space ~
14691 rotacemi, takže limit
14692 \begin_inset Formula $2^{11}$
14696 \begin_inset Formula $2^{8}$
14700 \begin_inset space ~
14704 Protože body ve stromě jsou 16-prvkové vektory, jsou podprostory patřící
14705 listům omezeny nejvýše v
14706 \begin_inset space ~
14709 polovině ze všech souřadnic, což je velmi málo.
14710 Zde by nejspíše pomohla volba varianty stromu, kde listy obsahují přesné
14713 \begin_inset space ~
14716 přesnějším odhadům výměnou za větší časovou a paměťovou náročnost.
14719 \begin_layout Standard
14720 Pro účinnou kompresi jsou ale vhodnější větší počty zdrojových bloků a zde
14721 je již predikce účinnější.
14723 \begin_inset Formula $2^{19}$
14726 zdrojových blocích a predikování jejich části o
14727 \begin_inset space ~
14730 relativní velikosti
14731 \begin_inset Formula $2^{-8}$
14735 \begin_inset Formula $2^{-6}$
14738 jsou už poklesy PSNR okolo
14739 \begin_inset Formula $0.5$
14743 \begin_inset space \thinspace{}
14747 \begin_inset space ~
14750 některých obrázků znatelně klesá i kompresní poměr.
14753 \begin_layout Standard
14754 Zajímavé je porovnání s
14755 \begin_inset space ~
14759 \begin_inset space ~
14762 článku publikujícím základní použitou větu.
14763 \begin_inset space ~
14767 \begin_inset CommandInset citation
14773 Zde jsou také bloky pro účely predikce zmenšeny na velikost
14774 \begin_inset Formula $4\times4$
14777 , ale všechna čísla jsou kvantizována na 8 bitů a místo KD-stromů je použita
14778 mnohem složitější strutura navržená pro přibližné hledání nejbližších sousedů.
14779 Další drobnou odlišností je, že v
14780 \begin_inset space ~
14783 článku jsou obě metody prohledávání prováděny pouze v
14784 \begin_inset space ~
14787 rámci klasifikační třídy (použit je kód od Fishera
14788 \begin_inset space ~
14792 \begin_inset CommandInset citation
14798 ), ale to by na porovnání nemělo mít větší vliv.
14799 Výsledky na identických obrázcích
14807 pro různá množství zdrojových bloků zde ukazují pokles PSNR pod
14808 \begin_inset Formula $0.5$
14812 \begin_inset space \thinspace{}
14815 dB při zanedbatelném poklesu kompresního poměru, přestože je predikováno
14817 \begin_inset Formula $5\times16$
14820 bloků (je uvažováno 8 možných otočení a obě možnosti znaménka lineárního
14821 koeficientu barevného zobrazení).
14825 \begin_layout Plain Layout
14826 obrázek zde nazývaný
14831 \begin_inset space ~
14835 \begin_inset space ~
14839 \begin_inset CommandInset citation
14852 Nejpravděpodobnějším důvodem vyšší účinnosti predikce z
14853 \begin_inset space ~
14857 \begin_inset space ~
14861 \begin_inset CommandInset citation
14867 je použití jiné datové struktury a tedy KD-stromy pro tento problém zřejmě
14868 nebudou vhodné (alespoň v
14869 \begin_inset space ~
14872 uvedené implementaci bez informací o
14873 \begin_inset space ~
14876 souřadnicích bodů v
14877 \begin_inset space ~
14883 \begin_layout Standard
14884 Přesto se celkové výsledky v
14885 \begin_inset space ~
14888 implicitním nastavení pohybují okolo nejlepších hodnot dosahovaných Fisherovým
14890 \begin_inset space ~
14893 klasické variantě používající čtyřstrom a klasifikaci) a jeho zrychlenou
14895 \begin_inset space ~
14899 \begin_inset CommandInset citation
14901 key "Fish95,Saup95"
14905 ), jak ukazuje tabulka
14906 \begin_inset space ~
14910 \begin_inset CommandInset ref
14912 reference "Testování/Predikce/Fisher-Saupe-Tabulka"
14921 je dokonce kvalita výrazně vyšší.
14924 \begin_layout Standard
14925 \begin_inset Float table
14930 \begin_layout Plain Layout
14934 \begin_layout Plain Layout
14935 \begin_inset Caption
14937 \begin_layout Plain Layout
14938 \begin_inset CommandInset label
14940 name "Testování/Predikce/Fisher-Saupe-Tabulka"
14945 \begin_inset space ~
14948 publikovanými výsledky
14949 \begin_inset CommandInset citation
14951 key "Fish95,Saup95"
14961 \begin_inset Box Frameless
14970 height_special "totalheight"
14973 \begin_layout Plain Layout
14974 \begin_inset space \hfill{}
14978 \begin_inset Tabular
14979 <lyxtabular version="3" rows="7" columns="5">
14981 <column alignment="center" valignment="top" width="0">
14982 <column alignment="center" valignment="top" width="0">
14983 <column alignment="center" valignment="top" width="0">
14984 <column alignment="center" valignment="top" width="0">
14985 <column alignment="center" valignment="top" width="0">
14987 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14990 \begin_layout Plain Layout
14996 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
14999 \begin_layout Plain Layout
15005 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15008 \begin_layout Plain Layout
15015 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15018 \begin_layout Plain Layout
15024 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
15027 \begin_layout Plain Layout
15032 \begin_layout Plain Layout
15033 publikované doby komprese nejsou porovnatelné, protože byly získány na o
15034 \begin_inset space ~
15037 mnoho let starším hardwaru (procesor MIPS R4000)
15049 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15052 \begin_layout Plain Layout
15058 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15061 \begin_layout Plain Layout
15067 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15070 \begin_layout Plain Layout
15076 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15079 \begin_layout Plain Layout
15085 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15088 \begin_layout Plain Layout
15096 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15099 \begin_layout Plain Layout
15105 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15108 \begin_layout Plain Layout
15114 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15117 \begin_layout Plain Layout
15123 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15126 \begin_layout Plain Layout
15132 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15135 \begin_layout Plain Layout
15143 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15146 \begin_layout Plain Layout
15152 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15155 \begin_layout Plain Layout
15161 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15164 \begin_layout Plain Layout
15170 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15173 \begin_layout Plain Layout
15179 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15182 \begin_layout Plain Layout
15192 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15195 \begin_layout Plain Layout
15201 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15204 \begin_layout Plain Layout
15210 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15213 \begin_layout Plain Layout
15219 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15222 \begin_layout Plain Layout
15228 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15231 \begin_layout Plain Layout
15239 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15242 \begin_layout Plain Layout
15248 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15251 \begin_layout Plain Layout
15257 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15260 \begin_layout Plain Layout
15266 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15269 \begin_layout Plain Layout
15275 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15278 \begin_layout Plain Layout
15286 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15289 \begin_layout Plain Layout
15295 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15298 \begin_layout Plain Layout
15304 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15307 \begin_layout Plain Layout
15313 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
15316 \begin_layout Plain Layout
15322 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
15325 \begin_layout Plain Layout
15339 \begin_inset space \hspace*{\fill}
15350 \begin_layout Plain Layout
15359 \begin_layout Section
15360 Účinnost diferenčního kódování
15363 \begin_layout Standard
15365 \begin_inset space ~
15371 \begin_inset space ~
15375 \begin_inset CommandInset ref
15377 reference "Implementace/Zobrazování"
15383 sloužící pro správu zobrazení mezi bloky ukládá kvantizované průměrné hodnoty
15384 a směrodatné odchylky bloků pomocí kodeků, které spotřebovávají méně místa
15385 pro posloupnosti se
15386 \begin_inset space ~
15389 vzájemně blízkými po sobě jdoucími prvky
15390 \begin_inset space ~
15394 \begin_inset CommandInset ref
15396 reference "Implementace/Kódování celočíselných řad"
15401 Protože kódování ovlivňuje pouze způsob uložení a nemá vliv na přesnost
15402 hodnot, stačí testovat pouze změnu kompresního poměru (vliv na spotřebovaný
15403 čas je zanedbatelný).
15405 \begin_inset space ~
15408 této části bude zjištěno, kolik prostoru technika skutečně ušetří.
15412 \begin_layout Standard
15413 Prostor zabraný klasickou metodou byl změřen tak, že byly diferenčním modulům
15414 nastaveny počty symbolů v
15415 \begin_inset space ~
15418 první části na jejich celkový počet, což vede k
15419 \begin_inset space ~
15422 tomu, že se na každou hodnotu spotřebuje pevný počet bitů, právě dvojkový
15424 \begin_inset space ~
15427 počtu symbolů (to je pro
15429 MStd\SpecialChar \-
15437 \begin_layout Standard
15438 Výsledky pro tři obrázky a různá nastavení kvality ukazuje tabulka
15439 \begin_inset space ~
15443 \begin_inset CommandInset ref
15445 reference "Testování/Kódování/Tabulka"
15449 , kde diferenční kódování vždy přináší úsporu prostoru, obvykle okolo
15450 \begin_inset Formula $5\%$
15454 Jsou zde také vidět dva trendy
15455 \begin_inset space ~
15458 --- větší účinek při vyšší kvalitě a také při menším počtu zdrojových bloků.
15459 Zvýšení nastavené kvality vede k
15460 \begin_inset space ~
15463 rozdělení na menší cílové bloky, což zvyšuje korelaci jejich vlastností
15464 a tím i efektivitu metody.
15465 Snížení počtu zdrojových bloků také vede k
15466 \begin_inset space ~
15469 rozdělení na více cílových bloků, protože je tím snížena pravděpodobnost
15470 nalezení vhodného zobrazení, a navíc ještě zvyšuje podíl výsledného prostoru
15471 ovlivněného metodou, protože identifikátory zdrojových bloků zaberou méně
15475 \begin_layout Standard
15478 \begin_inset Float table
15483 \begin_layout Plain Layout
15486 \begin_inset Caption
15488 \begin_layout Plain Layout
15489 \begin_inset CommandInset label
15491 name "Testování/Kódování/Tabulka"
15495 Testování účinnosti diferenčního kódování
15503 \begin_layout Plain Layout
15506 \begin_inset space \hfill{}
15510 \begin_inset Tabular
15511 <lyxtabular version="3" rows="14" columns="8">
15513 <column alignment="center" valignment="top" width="0">
15514 <column alignment="center" valignment="top" width="0">
15515 <column alignment="center" valignment="top" width="0">
15516 <column alignment="center" valignment="top" width="0">
15517 <column alignment="center" valignment="top" width="0">
15518 <column alignment="center" valignment="top" width="0">
15519 <column alignment="center" valignment="top" width="0">
15520 <column alignment="center" valignment="top" width="0">
15522 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15525 \begin_layout Plain Layout
15531 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15534 \begin_layout Plain Layout
15542 <cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15545 \begin_layout Plain Layout
15550 \begin_inset Formula $2^{19}$
15559 <cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15562 \begin_layout Plain Layout
15568 <cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15571 \begin_layout Plain Layout
15577 <cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15580 \begin_layout Plain Layout
15585 \begin_inset Formula $2^{15}$
15594 <cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15597 \begin_layout Plain Layout
15603 <cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
15606 \begin_layout Plain Layout
15614 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15617 \begin_layout Plain Layout
15625 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15628 \begin_layout Plain Layout
15636 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15639 \begin_layout Plain Layout
15648 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15651 \begin_layout Plain Layout
15660 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15663 \begin_layout Plain Layout
15671 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15674 \begin_layout Plain Layout
15683 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15686 \begin_layout Plain Layout
15695 <cell alignment="center" valignment="top" bottomline="true" leftline="true" rightline="true" usebox="none">
15698 \begin_layout Plain Layout
15708 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15711 \begin_layout Plain Layout
15719 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15722 \begin_layout Plain Layout
15730 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15733 \begin_layout Plain Layout
15741 <cell alignment="center" valignment="top" topline="true" usebox="none">
15744 \begin_layout Plain Layout
15752 <cell alignment="center" valignment="top" topline="true" usebox="none">
15755 \begin_layout Plain Layout
15763 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
15766 \begin_layout Plain Layout
15774 <cell alignment="center" valignment="top" topline="true" usebox="none">
15777 \begin_layout Plain Layout
15785 <cell alignment="center" valignment="top" topline="true" rightline="true" usebox="none">
15788 \begin_layout Plain Layout
15798 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15801 \begin_layout Plain Layout
15807 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15810 \begin_layout Plain Layout
15818 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15821 \begin_layout Plain Layout
15829 <cell alignment="center" valignment="top" usebox="none">
15832 \begin_layout Plain Layout
15840 <cell alignment="center" valignment="top" usebox="none">
15843 \begin_layout Plain Layout
15851 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15854 \begin_layout Plain Layout
15862 <cell alignment="center" valignment="top" usebox="none">
15865 \begin_layout Plain Layout
15873 <cell alignment="center" valignment="top" rightline="true" usebox="none">
15876 \begin_layout Plain Layout
15886 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15889 \begin_layout Plain Layout
15895 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15898 \begin_layout Plain Layout
15906 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15909 \begin_layout Plain Layout
15917 <cell alignment="center" valignment="top" usebox="none">
15920 \begin_layout Plain Layout
15928 <cell alignment="center" valignment="top" usebox="none">
15931 \begin_layout Plain Layout
15939 <cell alignment="center" valignment="top" leftline="true" usebox="none">
15942 \begin_layout Plain Layout
15950 <cell alignment="center" valignment="top" usebox="none">
15953 \begin_layout Plain Layout
15961 <cell alignment="center" valignment="top" rightline="true" usebox="none">
15964 \begin_layout Plain Layout
15974 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15977 \begin_layout Plain Layout
15983 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15986 \begin_layout Plain Layout
15994 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
15997 \begin_layout Plain Layout
16005 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
16008 \begin_layout Plain Layout
16016 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
16019 \begin_layout Plain Layout
16027 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16030 \begin_layout Plain Layout
16038 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
16041 \begin_layout Plain Layout
16049 <cell alignment="center" valignment="top" bottomline="true" rightline="true" usebox="none">
16052 \begin_layout Plain Layout
16062 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16065 \begin_layout Plain Layout
16073 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16076 \begin_layout Plain Layout
16084 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16087 \begin_layout Plain Layout
16095 <cell alignment="center" valignment="top" usebox="none">
16098 \begin_layout Plain Layout
16106 <cell alignment="center" valignment="top" usebox="none">
16109 \begin_layout Plain Layout
16117 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16120 \begin_layout Plain Layout
16128 <cell alignment="center" valignment="top" usebox="none">
16131 \begin_layout Plain Layout
16139 <cell alignment="center" valignment="top" rightline="true" usebox="none">
16142 \begin_layout Plain Layout
16152 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16155 \begin_layout Plain Layout
16161 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16164 \begin_layout Plain Layout
16172 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16175 \begin_layout Plain Layout
16183 <cell alignment="center" valignment="top" usebox="none">
16186 \begin_layout Plain Layout
16194 <cell alignment="center" valignment="top" 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" rightline="true" usebox="none">
16230 \begin_layout Plain Layout
16240 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16243 \begin_layout Plain Layout
16249 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16252 \begin_layout Plain Layout
16260 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16263 \begin_layout Plain Layout
16271 <cell alignment="center" valignment="top" usebox="none">
16274 \begin_layout Plain Layout
16282 <cell alignment="center" valignment="top" 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" rightline="true" usebox="none">
16318 \begin_layout Plain Layout
16328 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16331 \begin_layout Plain Layout
16337 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16340 \begin_layout Plain Layout
16348 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16351 \begin_layout Plain Layout
16359 <cell alignment="center" valignment="top" usebox="none">
16362 \begin_layout Plain Layout
16370 <cell alignment="center" valignment="top" usebox="none">
16373 \begin_layout Plain Layout
16381 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16384 \begin_layout Plain Layout
16392 <cell alignment="center" valignment="top" usebox="none">
16395 \begin_layout Plain Layout
16403 <cell alignment="center" valignment="top" rightline="true" usebox="none">
16406 \begin_layout Plain Layout
16416 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16419 \begin_layout Plain Layout
16427 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16430 \begin_layout Plain Layout
16438 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16441 \begin_layout Plain Layout
16449 <cell alignment="center" valignment="top" topline="true" usebox="none">
16452 \begin_layout Plain Layout
16460 <cell alignment="center" valignment="top" topline="true" usebox="none">
16463 \begin_layout Plain Layout
16471 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16474 \begin_layout Plain Layout
16482 <cell alignment="center" valignment="top" topline="true" usebox="none">
16485 \begin_layout Plain Layout
16493 <cell alignment="center" valignment="top" topline="true" rightline="true" usebox="none">
16496 \begin_layout Plain Layout
16506 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16509 \begin_layout Plain Layout
16515 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16518 \begin_layout Plain Layout
16526 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16529 \begin_layout Plain Layout
16537 <cell alignment="center" valignment="top" usebox="none">
16540 \begin_layout Plain Layout
16548 <cell alignment="center" valignment="top" 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" rightline="true" usebox="none">
16584 \begin_layout Plain Layout
16594 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16597 \begin_layout Plain Layout
16603 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16606 \begin_layout Plain Layout
16614 <cell alignment="center" valignment="top" leftline="true" usebox="none">
16617 \begin_layout Plain Layout
16625 <cell alignment="center" valignment="top" usebox="none">
16628 \begin_layout Plain Layout
16636 <cell alignment="center" valignment="top" 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" rightline="true" usebox="none">
16672 \begin_layout Plain Layout
16682 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16685 \begin_layout Plain Layout
16691 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16694 \begin_layout Plain Layout
16702 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16705 \begin_layout Plain Layout
16713 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
16716 \begin_layout Plain Layout
16724 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
16727 \begin_layout Plain Layout
16735 <cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
16738 \begin_layout Plain Layout
16746 <cell alignment="center" valignment="top" bottomline="true" usebox="none">
16749 \begin_layout Plain Layout
16757 <cell alignment="center" valignment="top" bottomline="true" rightline="true" usebox="none">
16760 \begin_layout Plain Layout
16774 \begin_inset Note Note
16777 \begin_layout Plain Layout
16780 \begin_inset Tabular
16781 <lyxtabular version="3" rows="11" columns="6">
16783 <column alignment="center" valignment="top" width="0">
16784 <column alignment="center" valignment="top" width="0">
16785 <column alignment="center" valignment="top" width="0">
16786 <column alignment="center" valignment="top" width="0">
16787 <column alignment="center" valignment="top" width="0">
16788 <column alignment="center" valignment="top" width="0">
16790 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16793 \begin_layout Plain Layout
16801 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16804 \begin_layout Plain Layout
16807 \begin_inset Formula $2^{11}$
16815 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16818 \begin_layout Plain Layout
16821 \begin_inset Formula $2^{-10}$
16829 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16832 \begin_layout Plain Layout
16840 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16843 \begin_layout Plain Layout
16851 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
16854 \begin_layout Plain Layout
16864 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16867 \begin_layout Plain Layout
16873 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16876 \begin_layout Plain Layout
16882 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16885 \begin_layout Plain Layout
16888 \begin_inset Formula $2^{-8}$
16896 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16899 \begin_layout Plain Layout
16907 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16910 \begin_layout Plain Layout
16918 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
16921 \begin_layout Plain Layout
16931 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16934 \begin_layout Plain Layout
16940 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16943 \begin_layout Plain Layout
16949 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16952 \begin_layout Plain Layout
16955 \begin_inset Formula $2^{-6}$
16963 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16966 \begin_layout Plain Layout
16974 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
16977 \begin_layout Plain Layout
16985 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
16988 \begin_layout Plain Layout
16998 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17001 \begin_layout Plain Layout
17007 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17010 \begin_layout Plain Layout
17016 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17019 \begin_layout Plain Layout
17027 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17030 \begin_layout Plain Layout
17038 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17041 \begin_layout Plain Layout
17049 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17052 \begin_layout Plain Layout
17062 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17065 \begin_layout Plain Layout
17071 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17074 \begin_layout Plain Layout
17077 \begin_inset Formula $2^{15}$
17085 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17088 \begin_layout Plain Layout
17091 \begin_inset Formula $2^{-10}$
17099 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17102 \begin_layout Plain Layout
17110 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17113 \begin_layout Plain Layout
17121 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17124 \begin_layout Plain Layout
17134 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17137 \begin_layout Plain Layout
17143 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17146 \begin_layout Plain Layout
17152 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17155 \begin_layout Plain Layout
17158 \begin_inset Formula $2^{-8}$
17166 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17169 \begin_layout Plain Layout
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" rightline="true" usebox="none">
17191 \begin_layout Plain Layout
17201 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17204 \begin_layout Plain Layout
17210 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17213 \begin_layout Plain Layout
17219 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17222 \begin_layout Plain Layout
17225 \begin_inset Formula $2^{-6}$
17233 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17236 \begin_layout Plain Layout
17244 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17247 \begin_layout Plain Layout
17255 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17258 \begin_layout Plain Layout
17268 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17271 \begin_layout Plain Layout
17277 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17280 \begin_layout Plain Layout
17286 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17289 \begin_layout Plain Layout
17297 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17300 \begin_layout Plain Layout
17308 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17311 \begin_layout Plain Layout
17319 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17322 \begin_layout Plain Layout
17332 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17335 \begin_layout Plain Layout
17341 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17344 \begin_layout Plain Layout
17347 \begin_inset Formula $2^{19}$
17355 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17358 \begin_layout Plain Layout
17361 \begin_inset Formula $2^{-10}$
17369 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17372 \begin_layout Plain Layout
17380 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17383 \begin_layout Plain Layout
17391 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17394 \begin_layout Plain Layout
17404 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17407 \begin_layout Plain Layout
17413 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17416 \begin_layout Plain Layout
17422 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17425 \begin_layout Plain Layout
17428 \begin_inset Formula $2^{-8}$
17436 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17439 \begin_layout Plain Layout
17447 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
17450 \begin_layout Plain Layout
17458 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
17461 \begin_layout Plain Layout
17471 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17474 \begin_layout Plain Layout
17480 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17483 \begin_layout Plain Layout
17489 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17492 \begin_layout Plain Layout
17495 \begin_inset Formula $2^{-6}$
17503 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17506 \begin_layout Plain Layout
17514 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
17517 \begin_layout Plain Layout
17525 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
17528 \begin_layout Plain Layout
17547 \begin_inset space \hfill{}
17558 \begin_layout Section
17562 \begin_layout Standard
17563 Během předchozích testů bylo doladěno implicitní nastavení některých parametrů
17566 \begin_inset space ~
17569 této části je vyhodnocována celková efektivita komprese a porovnána se standardn
17570 ími metodami JPEG a JPEG
17571 \begin_inset space ~
17577 \begin_layout Standard
17578 Fraktální komprese je testována pro několik vybraných nastavení počtu zdrojových
17579 bloků a jejich maximální predikované části (značeny
17580 \begin_inset Formula $z$
17584 \begin_inset Formula $p$
17587 ), které představují různé poměry účinnosti a spotřebovaného času.
17588 Implicitní nastavení je
17589 \begin_inset Formula $z=2^{19}$
17593 \begin_inset Formula $p=2^{-8}$
17599 \begin_layout Standard
17601 \begin_inset space ~
17605 \begin_inset CommandInset ref
17607 reference "Testování/Celkové/Čas-Lena"
17611 ukazuje závislost spotřebovaného času na kompresním poměru pro obrázek
17617 Graf potvrzuje fakt, že fraktální komprese spotřebuje při použitelné kvalitě
17618 řádově více času než standardní metody.
17620 \begin_inset space ~
17623 těch se spotřebovaný čas s
17624 \begin_inset space ~
17627 kompresním poměrem výrazněji nemění, ale fraktální komprese spotřebuje při
17628 nízkém nastavení kvality času méně.
17629 Grafy závislosti času na kompresním poměru pro ostatních pět testovaných
17630 obrázků vypadají stejně, a proto zde nejsou uvedeny.
17633 \begin_layout Standard
17634 \begin_inset Float figure
17639 \begin_layout Plain Layout
17640 \begin_inset Caption
17642 \begin_layout Plain Layout
17643 \begin_inset CommandInset label
17645 name "Testování/Celkové/Čas-Lena"
17649 Graf závislosti doby komprese na kompresním poměru pro obrázek
17657 \begin_inset Graphics
17658 filename lena-time.eps
17670 \begin_layout Standard
17671 Zajímavější je závislost kvality na kompresním poměru.
17673 \begin_inset space ~
17677 \begin_inset CommandInset ref
17679 reference "Testování/PSNR-Lena"
17687 , kde mají všechny křivky podobný průběh a fraktální komprese nedosahuje
17688 účinnosti standardních metod.
17689 Stejný vzhled mají i neuvedené grafy pro obrázky
17698 Podobný je také graf pro obrázek
17701 \begin_inset space ~
17707 \begin_inset CommandInset ref
17709 reference "Testování/PSNR-Mandrill"
17713 , akorát mají křivky jiné tvary a při použitelných hodnotách kvality se
17714 fraktální komprese více přibližuje JPEG kompresi.
17717 \begin_layout Standard
17719 \begin_inset space ~
17725 \begin_inset space ~
17731 \begin_inset CommandInset ref
17733 reference "Testování/PSNR-Serrano"
17738 Zde dává fraktální komprese výrazně lepší výsledky než JPEG a v
17739 \begin_inset space ~
17742 některých případech dokonce i
17743 \begin_inset space ~
17747 \begin_inset space ~
17751 \begin_inset space ~
17755 Podobně vypadá i graf pro obrázek
17758 \begin_inset space ~
17764 \begin_inset CommandInset ref
17766 reference "Testování/PSNR-Clegg"
17770 , ale zde již nedává fraktální komprese tak dobré výsledky.
17773 \begin_layout Standard
17774 Testy ukazují, že spíše než na běžné spojité fotografie je zde implementovaná
17775 fraktální komprese vhodnější pro obrázky obsahující ostré hrany, jako zkoušené
17779 \begin_layout Standard
17780 \begin_inset Float figure
17785 \begin_layout Plain Layout
17786 \begin_inset Caption
17788 \begin_layout Plain Layout
17789 \begin_inset CommandInset label
17791 name "Testování/PSNR-Lena"
17795 Graf závislosti kvality na kompresním poměru pro obrázek
17803 \begin_inset Graphics
17804 filename lena-PSNR.eps
17811 \begin_layout Plain Layout
17820 \begin_layout Standard
17821 \begin_inset Float figure
17826 \begin_layout Plain Layout
17830 \begin_layout Plain Layout
17831 \begin_inset Caption
17833 \begin_layout Plain Layout
17834 \begin_inset CommandInset label
17836 name "Testování/PSNR-Mandrill"
17840 Graf závislosti kvality na kompresním poměru pro obrázek
17850 \begin_layout Plain Layout
17851 \begin_inset Graphics
17852 filename mandrill-PSNR.eps
17864 \begin_layout Standard
17865 \begin_inset Float figure
17870 \begin_layout Plain Layout
17874 \begin_layout Plain Layout
17875 \begin_inset Caption
17877 \begin_layout Plain Layout
17878 \begin_inset CommandInset label
17880 name "Testování/PSNR-Serrano"
17884 Graf závislosti kvality na kompresním poměru pro obrázek
17894 \begin_layout Plain Layout
17895 \begin_inset Graphics
17896 filename serrano-PSNR.eps
17908 \begin_layout Standard
17909 \begin_inset Float figure
17914 \begin_layout Plain Layout
17918 \begin_layout Plain Layout
17919 \begin_inset Caption
17921 \begin_layout Plain Layout
17922 \begin_inset CommandInset label
17924 name "Testování/PSNR-Clegg"
17928 Graf závislosti kvality na kompresním poměru pro obrázek
17938 \begin_layout Plain Layout
17939 \begin_inset Graphics
17940 filename clegg-PSNR.eps
17952 \begin_layout Chapter*
17956 \begin_layout Standard
17957 \begin_inset CommandInset bibtex
17958 LatexCommand bibtex
17959 btprint "btPrintCited"
17960 bibfiles "fractals"
17968 \begin_layout Chapter*
17972 \begin_layout Standard
17973 \begin_inset CommandInset bibtex
17974 LatexCommand bibtex
17975 btprint "btPrintCited"
17976 bibfiles "internet"