text/bc.lyx

   1 #LyX 1.5.7 created this file. For more info see http://www.lyx.org/
   2 \lyxformat 276
   3 \begin_document
   4 \begin_header
   5 \textclass article
   6 \begin_preamble
   7 \usepackage[final]{graphicx}
   8 \end_preamble
   9 \language czech
  10 \inputencoding utf8
  11 \font_roman default
  12 \font_sans default
  13 \font_typewriter default
  14 \font_default_family default
  15 \font_sc false
  16 \font_osf false
  17 \font_sf_scale 100
  18 \font_tt_scale 100
  19 \graphics default
  20 \paperfontsize default
  21 \spacing onehalf
  22 \papersize default
  23 \use_geometry false
  24 \use_amsmath 1
  25 \use_esint 0
  26 \cite_engine basic
  27 \use_bibtopic false
  28 \paperorientation portrait
  29 \paperwidth 0cm
  30 \paperheight 0cm
  31 \leftmargin 0cm
  32 \topmargin 0cm
  33 \rightmargin 0cm
  34 \bottommargin 0cm
  35 \headheight 0cm
  36 \headsep 0cm
  37 \footskip 0cm
  38 \secnumdepth 3
  39 \tocdepth 3
  40 \paragraph_separation indent
  41 \defskip medskip
  42 \quotes_language swedish
  43 \papercolumns 1
  44 \papersides 1
  45 \paperpagestyle default
  46 \tracking_changes false
  47 \output_changes false
  48 \author ""
  49 \author ""
  50 \end_header
  51
  52 \begin_body
  53
  54 \begin_layout Standard
  55 \begin_inset Include \input{bc_start.tex}
  56 preview false
  57
  58 \end_inset
  59
  60
  61 \newpage
  62
  63 \end_layout
  64
  65 \begin_layout Section
  66 Úvod
  67 \end_layout
  68
  69 \begin_layout Standard
  70 <Představení práce, motivace a přehled obsahu kapitol.>
  71 \end_layout
  72
  73 \begin_layout Section
  74 Vývoj a principy fraktálové komprese obrazu
  75 \end_layout
  76
  77 \begin_layout Subsection
  78 IFS
  79 \end_layout
  80
  81 \begin_layout Standard
  82 Základy fraktálové komprese byly položeny v druhé polovině 80.\InsetSpace ~
  83 let, kdy Barnsley
  84  studoval systémy iterovaných funkcí (IFS).
  85  IFS je množina bodů v\InsetSpace ~
  86 úplném metrickém prostoru definována pomocí souboru
  87  kontraktivních zobrazení prostoru do sebe.
  88  Mějme soubor zobrazení
  89 \begin_inset Formula $f_{i}:X\rightarrow X$
  90 \end_inset
  91
  92  pro
  93 \begin_inset Formula $i\in J$
  94 \end_inset
  95
  96  a definujme jejich sjednocení
  97 \begin_inset Formula $f:2^{X}\rightarrow2^{X}$
  98 \end_inset
  99
 100 ,
 101 \begin_inset Formula $f\left(A\right)=\left\{ f_{i}\left(a\right)\mid i\in J,\ a\in A\right\} $
 102 \end_inset
 103
 104 , kde zápisem
 105 \begin_inset Formula $2^{X}$
 106 \end_inset
 107
 108  je značena množina všech podmnožin
 109 \begin_inset Formula $X$
 110 \end_inset
 111
 112 .
 113  Na
 114 \begin_inset Formula $2^{X}$
 115 \end_inset
 116
 117  lze definovat metriku tak, abychom dostali zase úplný metrický prostor
 118  a zobrazení
 119 \begin_inset Formula $f$
 120 \end_inset
 121
 122  bylo kontraktivní
 123 \begin_inset Foot
 124 status collapsed
 125
 126 \begin_layout Standard
 127 ukázáno například v
 128 \begin_inset LatexCommand cite
 129 key "Barn88b"
 130
 131 \end_inset
 132
 133  pomocí Hausdorffovy metriky
 134 \end_layout
 135
 136 \end_inset
 137
 138 .
 139  To spolu s\InsetSpace ~
 140 Banachovou větou o\InsetSpace ~
 141 pevném bodě dává, že zobrazení
 142 \begin_inset Formula $f$
 143 \end_inset
 144
 145  má právě jeden pevný bod, kterým je právě hledaná množina bodů, často nazývaná
 146  atraktor nebo fraktál
 147 \begin_inset Foot
 148 status collapsed
 149
 150 \begin_layout Standard
 151 fraktály lze konstruovat i jinými způsoby než pomocí IFS
 152 \end_layout
 153
 154 \end_inset
 155
 156 .
 157 \end_layout
 158
 159 \begin_layout Standard
 160 IFS mají několik zajímavých vlastností.
 161  Pro získání atraktoru stačí znát zobrazení
 162 \begin_inset Formula $f$
 163 \end_inset
 164
 165  a iterovat ho na libovolné neprázdné kompaktní podmnožině
 166 \begin_inset Formula $X$
 167 \end_inset
 168
 169 .
 170  Navíc vzniklé fraktály můžou mít detailní kresbu při libovolném přiblížení,
 171  přestože jejich matematický popis je velmi malý.
 172  Mezi nejznámější IFS patří Barnsleyho kapradina, generovaná v
 173 \begin_inset Formula $\mathbb{R}^{2}$
 174 \end_inset
 175
 176  pomocí čtyř afinních zobrazení.
 177  Barnsley zkoumal, zda by nebylo možné proces obrátit -- k\InsetSpace ~
 178 danému obrázku
 179  najít soubor zobrazení, jehož pevný bod by obrázku byl velmi blízký.
 180
 181 \end_layout
 182
 183 \begin_layout Standard
 184 Zde se používá takzvaná kolážová věta, uvedená například v\InsetSpace ~
 185
 186 \begin_inset LatexCommand cite
 187 key "Fish95"
 188
 189 \end_inset
 190
 191 , která dává horní odhad na odchylku atraktoru od požadovaného obrázku:
 192
 193 \begin_inset Formula \[
 194 f\mbox{ je zobrazení, }\exists k\; f^{k}\mbox{ je kontraktivní s faktorem }s<1\mbox{ v metrice }d\mbox{, pak}\]
 195
 196 \end_inset
 197
 198
 199 \begin_inset Formula \[
 200 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)\]
 201
 202 \end_inset
 203
 204 Díky tomu stačí hledat zobrazení, která obrázek transformují a přitom ho
 205  změní co nejméně
 206 \begin_inset Foot
 207 status collapsed
 208
 209 \begin_layout Standard
 210 triviální identické zobrazení sice vždy zkonverguje, ale jinak samozřejmě
 211  fungovat nebude, nesplňuje předpoklad kontraktivity
 212 \end_layout
 213
 214 \end_inset
 215
 216 .
 217  Ukázalo se, že největší problém je v tom, že na rozdíl od klasických IFS
 218  málokterý obrázek lze charakterizovat jako sjednocení několika transformovaných
 219  zmenšenin celého obrázku.
 220  Bylo sice možné obrázek rozdělit na menší kusy charakterizované IFS, ale
 221  tuto metodu se nepodařilo zautomatizovat.
 222 \end_layout
 223
 224 \begin_layout Subsection
 225 PIFS
 226 \end_layout
 227
 228 \begin_layout Standard
 229 Pro kompresi obrázků také bylo nutné najít lepší model, než množinu bodů
 230  v
 231 \begin_inset Formula $\mathbb{R}^{2}$
 232 \end_inset
 233
 234 .
 235  Jedna z\InsetSpace ~
 236 možností reprezentace obrázků ve stupních šedi je funkce tvaru
 237 \begin_inset Formula $g:I^{2}\rightarrow I$
 238 \end_inset
 239
 240 , kde
 241 \begin_inset Formula $I$
 242 \end_inset
 243
 244  je značení pro interval
 245 \begin_inset Formula $\left[0,1\right]\subset\mathbb{R}$
 246 \end_inset
 247
 248 .
 249  Zde budeme analogicky hledat soubor operátorů takový, aby jejich sjednocením
 250  vznikl operátor
 251 \begin_inset Formula $F$
 252 \end_inset
 253
 254  s\InsetSpace ~
 255 pevným bodem co nejblíže danému obrázku (jeho funkci).
 256  Aby bylo zaručeno, že sjednocení lze provést, v\InsetSpace ~
 257 PIFS (partitioned IFS) je
 258  prostor obrázku rozdělen na disjunktní části
 259 \begin_inset Formula \[
 260 \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\]
 261
 262 \end_inset
 263
 264 a operátory jsou tvaru
 265 \begin_inset Formula $F_{i}:\left(I^{2}\rightarrow I\right)\rightarrow\left(R_{i}\rightarrow I\right)$
 266 \end_inset
 267
 268 .
 269 \end_layout
 270
 271 \begin_layout Standard
 272 PIFS dnes tvoří základ naprosté většiny technik pro fraktální kompresi obrazu.
 273  Pro zjednodušení se typicky uvažují pouze afinní operátory, kde se navíc
 274  vzájemně neovlivňuje transformace polohy s transformací barvy, formálně
 275
 276 \begin_inset Formula \[
 277 F_{i}g=h_{i},\qquad h_{i}:R_{i}\rightarrow I,\qquad h_{i}\left(\left[\begin{array}{c}
 278 x\\
 279 y\end{array}\right]\right)=\left(c_{i}\circ g\circ w_{i}\right)\left(\left[\begin{array}{c}
 280 x\\
 281 y\end{array}\right]\right)\]
 282
 283 \end_inset
 284
 285
 286 \begin_inset Formula \[
 287 \mbox{pro nějaká afinní zobrazení\quad} w_{i}:R_{i}\rightarrow I^{2}\mbox{\quad a\quad}c_{i}:I\rightarrow I\]
 288
 289 \end_inset
 290
 291 Za
 292 \family roman
 293 \series medium
 294 \shape up
 295 \size normal
 296 \emph off
 297 \bar no
 298 \noun off
 299 \color none
 300
 301 \begin_inset Formula $R_{i}$
 302 \end_inset
 303
 304  se volí souvislé části obrazu, typicky čtverce o straně délky
 305 \begin_inset Formula $2^{k}$
 306 \end_inset
 307
 308 , a nazývají se zdrojové bloky.
 309  Díky spojitosti
 310 \begin_inset Formula $w_{i}$
 311 \end_inset
 312
 313  jsou
 314 \begin_inset Formula $D_{i}=w_{i}\left(R_{i}\right)$
 315 \end_inset
 316
 317  také souvislé části obrazu a nazývají se zdrojové bloky
 318 \begin_inset Foot
 319 status collapsed
 320
 321 \begin_layout Standard
 322
 323 \family roman
 324 \series medium
 325 \shape up
 326 \size normal
 327 \emph off
 328 \bar no
 329 \noun off
 330 \color none
 331 značení pochází z anglických termínů
 332 \family default
 333 \series default
 334 \shape default
 335 \size default
 336 \emph on
 337 \bar default
 338 \noun default
 339 \color inherit
 340 domain block
 341 \family roman
 342 \series medium
 343 \shape up
 344 \size normal
 345 \emph off
 346 \bar no
 347 \noun off
 348 \color none
 349  a
 350 \family default
 351 \series default
 352 \shape default
 353 \size default
 354 \emph on
 355 \bar default
 356 \noun default
 357 \color inherit
 358 range block
 359 \end_layout
 360
 361 \end_inset
 362
 363 .
 364 \end_layout
 365
 366 \begin_layout Subsubsection
 367 Konvergence PIFS
 368 \end_layout
 369
 370 \begin_layout Standard
 371 Pro konvergenci a horní odhad chyby PIFS modelu lze zase použít kolážovou
 372  větu.
 373  Následující důkaz je modifikací důkazu uvedeného v
 374 \begin_inset LatexCommand cite
 375 key "Fish95"
 376
 377 \end_inset
 378
 379 .
 380  Zde se hodí metrika
 381 \begin_inset Formula \[
 382 d_{sup}\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\} \]
 383
 384 \end_inset
 385
 386 Postačí, aby
 387 \family roman
 388 \series medium
 389 \shape up
 390 \size normal
 391 \emph off
 392 \bar no
 393 \noun off
 394 \color none
 395
 396 \begin_inset Formula $\exists s<1\;\forall i\in J\quad c_{i}$
 397 \end_inset
 398
 399  mělo lineární člen
 400 \begin_inset Formula $a_{i}:\;\left|a_{i}\right|\le s$
 401 \end_inset
 402
 403 , pak pro obrázky
 404 \begin_inset Formula $g_{1},g_{2}:I^{2}\rightarrow I\quad$
 405 \end_inset
 406
 407
 408 \begin_inset Formula $\forall\vec{z}\in I^{2}\quad\exists!i\in J\quad\vec{z}\in R_{i}\quad$
 409 \end_inset
 410
 411 a platí
 412 \begin_inset Formula \[
 413 \left|\left(F_{i}g_{1}\right)\left(\vec{z}\right)-\left(F_{i}g_{2}\right)\left(\vec{z}\right)\right|\quad\le\quad 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|\quad\leq\quad s\ d_{sup}\left(g_{1},g_{2}\right)\]
 414
 415 \end_inset
 416
 417 Z toho už plyne kontraktivita celého operátoru
 418 \begin_inset Formula $F:\quad d_{sup}\left(Fg_{1},Fg_{2}\right)\;\le\; s\ d_{sup}\left(g_{1},g_{2}\right)$
 419 \end_inset
 420
 421
 422 \end_layout
 423
 424 \begin_layout Standard
 425
 426 \newpage
 427
 428 \begin_inset LatexCommand bibtex
 429 options "bibtotoc,plain"
 430 bibfiles "fractals"
 431
 432 \end_inset
 433
 434
 435 \end_layout
 436
 437 \end_body
 438 \end_document