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 1
  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\InsetSpace ~
 128
 129 \begin_inset LatexCommand cite
 130 key "Barn88b"
 131
 132 \end_inset
 133
 134  pomocí Hausdorffovy metriky
 135 \end_layout
 136
 137 \end_inset
 138
 139 .
 140  To spolu s\InsetSpace ~
 141 Banachovou větou o\InsetSpace ~
 142 pevném bodě dává, že zobrazení
 143 \begin_inset Formula $f$
 144 \end_inset
 145
 146  má právě jeden pevný bod, kterým je právě hledaná množina bodů, často nazývaná
 147  atraktor nebo fraktál
 148 \begin_inset Foot
 149 status collapsed
 150
 151 \begin_layout Standard
 152 fraktály lze konstruovat i jinými způsoby než pomocí IFS
 153 \end_layout
 154
 155 \end_inset
 156
 157 .
 158 \end_layout
 159
 160 \begin_layout Standard
 161 IFS mají několik zajímavých vlastností.
 162  Pro získání atraktoru stačí znát zobrazení
 163 \begin_inset Formula $f$
 164 \end_inset
 165
 166  a iterovat ho na libovolné neprázdné kompaktní podmnožině
 167 \begin_inset Formula $X$
 168 \end_inset
 169
 170 .
 171  Navíc vzniklé fraktály můžou mít detailní kresbu při libovolném přiblížení,
 172  přestože jejich matematický popis je velmi malý.
 173  Mezi nejznámější IFS patří Barnsleyho kapradina, generovaná v
 174 \begin_inset Formula $\mathbb{R}^{2}$
 175 \end_inset
 176
 177  pomocí čtyř afinních zobrazení.
 178  Barnsley zkoumal, zda by nebylo možné proces obrátit\InsetSpace ~
 179 -- k\InsetSpace ~
 180 danému obrázku
 181  najít soubor zobrazení, jehož pevný bod by obrázku byl velmi blízký.
 182
 183 \end_layout
 184
 185 \begin_layout Standard
 186 Zde se používá takzvaná kolážová věta, uvedená například v\InsetSpace ~
 187
 188 \begin_inset LatexCommand cite
 189 key "Fish95"
 190
 191 \end_inset
 192
 193 , která dává horní odhad na odchylku atraktoru od požadovaného obrázku:
 194
 195 \begin_inset Formula \[
 196 f\mbox{ je zobrazení, které je kontraktivní s faktorem }s<1\mbox{ v metrice }d\mbox{, pak}\]
 197
 198 \end_inset
 199
 200
 201 \begin_inset Formula \[
 202 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)\]
 203
 204 \end_inset
 205
 206 Díky tomu stačí hledat zobrazení, která obrázek transformují a přitom ho
 207  změní co nejméně
 208 \begin_inset Foot
 209 status collapsed
 210
 211 \begin_layout Standard
 212 triviální identické zobrazení sice vždy zkonverguje, ale jinak samozřejmě
 213  fungovat nebude, nesplňuje předpoklad kontraktivity
 214 \end_layout
 215
 216 \end_inset
 217
 218 .
 219  Pro jistotu konvergence dokonce stačí, že
 220 \begin_inset Formula $\exists k\ f^{k}$
 221 \end_inset
 222
 223  je kontraktivní s faktorem
 224 \begin_inset Formula $s<1$
 225 \end_inset
 226
 227 .
 228  Ukázalo se, že největší problém je v\InsetSpace ~
 229 tom, že na rozdíl od klasických IFS
 230  málokterý obrázek lze charakterizovat jako sjednocení několika transformovaných
 231  zmenšenin celého obrázku.
 232  Bylo sice možné obrázek rozdělit na menší kusy charakterizované IFS, ale
 233  tuto metodu se nepodařilo zautomatizovat.
 234 \end_layout
 235
 236 \begin_layout Subsection
 237 PIFS
 238 \end_layout
 239
 240 \begin_layout Standard
 241 Pro kompresi obrázků také bylo nutné najít lepší model, než množinu bodů
 242  v\InsetSpace ~
 243
 244 \begin_inset Formula $\mathbb{R}^{2}$
 245 \end_inset
 246
 247 .
 248  Jedna z\InsetSpace ~
 249 možností reprezentace obrázků ve stupních šedi je funkce tvaru
 250 \begin_inset Formula $g:I^{2}\rightarrow I$
 251 \end_inset
 252
 253 , kde
 254 \begin_inset Formula $I$
 255 \end_inset
 256
 257  je značení pro interval
 258 \begin_inset Formula $\left[0,1\right]\subset\mathbb{R}$
 259 \end_inset
 260
 261 .
 262  Zde budeme analogicky hledat soubor operátorů takový, aby jejich sjednocením
 263  vznikl operátor
 264 \begin_inset Formula $F$
 265 \end_inset
 266
 267  s\InsetSpace ~
 268 pevným bodem co nejblíže danému obrázku (jeho funkci).
 269  Aby bylo zaručeno, že sjednocení lze provést, v\InsetSpace ~
 270 PIFS (partitioned IFS) je
 271  prostor obrázku rozdělen na disjunktní části
 272 \begin_inset Formula \[
 273 \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\]
 274
 275 \end_inset
 276
 277 a operátory jsou tvaru
 278 \begin_inset Formula $F_{i}:\left(I^{2}\rightarrow I\right)\rightarrow\left(R_{i}\rightarrow I\right)$
 279 \end_inset
 280
 281 .
 282 \end_layout
 283
 284 \begin_layout Standard
 285 PIFS, které zavedl Jacquin, dnes tvoří základ naprosté většiny technik pro
 286  fraktální kompresi obrazu.
 287  Pro zjednodušení se zde uvažují pouze afinní operátory, kde se navíc vzájemně
 288  neovlivňuje transformace polohy s\InsetSpace ~
 289 transformací barvy, formálně
 290 \begin_inset Formula \[
 291 F_{i}g=h_{i},\qquad h_{i}:R_{i}\rightarrow I,\qquad h_{i}\left(\left[\begin{array}{c}
 292 x\\
 293 y\end{array}\right]\right)=\left(c_{i}\circ g\circ w_{i}\right)\left(\left[\begin{array}{c}
 294 x\\
 295 y\end{array}\right]\right)\]
 296
 297 \end_inset
 298
 299
 300 \begin_inset Formula \[
 301 \mbox{pro nějaká afinní zobrazení\quad}w_{i}:R_{i}\rightarrow I^{2}\mbox{\quad a\quad}c_{i}:I\rightarrow\mathbb{R}\]
 302
 303 \end_inset
 304
 305 Za
 306 \family roman
 307 \series medium
 308 \shape up
 309 \size normal
 310 \emph off
 311 \bar no
 312 \noun off
 313 \color none
 314
 315 \begin_inset Formula $R_{i}$
 316 \end_inset
 317
 318  se volí souvislé části obrazu, typicky čtverce o\InsetSpace ~
 319 straně délky
 320 \begin_inset Formula $2^{k}$
 321 \end_inset
 322
 323 , a\InsetSpace ~
 324 nazývají se cílové bloky.
 325  Díky spojitosti
 326 \begin_inset Formula $w_{i}$
 327 \end_inset
 328
 329  jsou
 330 \begin_inset Formula $D_{i}=w_{i}\left(R_{i}\right)$
 331 \end_inset
 332
 333  také souvislé části obrazu a nazývají se zdrojové bloky.
 334 \begin_inset Foot
 335 status collapsed
 336
 337 \begin_layout Standard
 338
 339 \family roman
 340 \series medium
 341 \shape up
 342 \size normal
 343 \emph off
 344 \bar no
 345 \noun off
 346 \color none
 347 značení pochází z\InsetSpace ~
 348 anglických termínů
 349 \family default
 350 \series default
 351 \shape default
 352 \size default
 353 \emph on
 354 \bar default
 355 \noun default
 356 \color inherit
 357 domain block
 358 \family roman
 359 \series medium
 360 \shape up
 361 \size normal
 362 \emph off
 363 \bar no
 364 \noun off
 365 \color none
 366  a
 367 \family default
 368 \series default
 369 \shape default
 370 \size default
 371 \emph on
 372 \bar default
 373 \noun default
 374 \color inherit
 375 range block
 376 \end_layout
 377
 378 \end_inset
 379
 380  Transformace
 381 \begin_inset Formula $w_{i}$
 382 \end_inset
 383
 384  určuje, která část obrazu bude zobrazena do cílového bloku a také jak bude
 385  otočena a případně symetricky převrácena.
 386  Za
 387 \begin_inset Formula $w_{i}$
 388 \end_inset
 389
 390  se volí kontraktivní zobrazení, přestože to pro níže uvedené tvrzení o\InsetSpace ~
 391 konvergen
 392 ci není potřeba.
 393 \end_layout
 394
 395 \begin_layout Subsubsection
 396 Konvergence PIFS
 397 \end_layout
 398
 399 \begin_layout Standard
 400 Pro konvergenci a horní odhad chyby PIFS modelu lze zase použít kolážovou
 401  větu.
 402  Následující důkaz je modifikací důkazu uvedeného v\InsetSpace ~
 403
 404 \begin_inset LatexCommand cite
 405 key "Fish95"
 406
 407 \end_inset
 408
 409 .
 410  Zde se hodí metrika
 411 \begin_inset Formula \[
 412 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\} \]
 413
 414 \end_inset
 415
 416 Postačí, aby
 417 \family roman
 418 \series medium
 419 \shape up
 420 \size normal
 421 \emph off
 422 \bar no
 423 \noun off
 424 \color none
 425
 426 \begin_inset Formula $\exists s<1\;\forall i\in J\; c_{i}$
 427 \end_inset
 428
 429  mělo lineární člen
 430 \begin_inset Formula $a_{i}:\;\left|a_{i}\right|\le s$
 431 \end_inset
 432
 433 , pak pro obrázky
 434 \begin_inset Formula $g_{1},g_{2}:I^{2}\rightarrow I\quad$
 435 \end_inset
 436
 437
 438 \begin_inset Formula $\forall\vec{z}\in I^{2}\quad\exists!i\in J\quad\vec{z}\in R_{i}\quad$
 439 \end_inset
 440
 441  a platí
 442 \begin_inset Formula \[
 443 \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)\]
 444
 445 \end_inset
 446
 447 Z toho už plyne kontraktivita celého operátoru
 448 \begin_inset Formula $F:\; d_{sup}\left(Fg_{1},Fg_{2}\right)\;\le\; s\, d_{sup}\left(g_{1},g_{2}\right)$
 449 \end_inset
 450
 451  a díky tomu lze použít kolážovou větu.
 452 \end_layout
 453
 454 \begin_layout Standard
 455 Ukazuje se ale, že pro použití v\InsetSpace ~
 456 implementaci je tento odhad příliš volný,
 457  stejně jako použitá metrika nedává dobré vizuální výsledky.
 458 \end_layout
 459
 460 \begin_layout Subsubsection
 461 Optimální zobrazení
 462 \end_layout
 463
 464 \begin_layout Standard
 465 Pro daný cílový blok
 466 \family roman
 467 \series medium
 468 \shape up
 469 \size normal
 470 \emph off
 471 \bar no
 472 \noun off
 473 \color none
 474
 475 \begin_inset Formula $R_{i}$
 476 \end_inset
 477
 478  se volí afinní zobrazení
 479 \begin_inset Formula $w_{i}$
 480 \end_inset
 481
 482  tak, aby mapovalo blok na jeden ze souboru zdrojových bloků, který bývá
 483  pevně daný kvůli zjednodušení ukládání a vyhledávání.
 484  Tato volba je hlavním zdrojem výpočetní složitosti celé komprese a jejímu
 485  urychlení byla věnována značná část výzkumu v oblasti.
 486  Obecně je snaha zvolit takový zdrojový blok
 487 \begin_inset Formula $D_{i}$
 488 \end_inset
 489
 490 , že spolu s\InsetSpace ~
 491 optimálním barevným zobrazením
 492 \begin_inset Formula $c_{i}$
 493 \end_inset
 494
 495  bude pro složený operátor
 496 \begin_inset Formula $F_{i}g=\left(c_{i}\circ g\circ w_{i}\right)$
 497 \end_inset
 498
 499  vzdálenost
 500 \begin_inset Formula $d\left(\ c_{i}\circ g\circ w_{i},\ g\ \right)$
 501 \end_inset
 502
 503
 504 \family default
 505 \series default
 506 \shape default
 507 \size default
 508 \emph default
 509 \bar default
 510 \noun default
 511 \color inherit
 512
 513 \family roman
 514 \series medium
 515 \shape up
 516 \size normal
 517 \emph off
 518 \bar no
 519 \noun off
 520 \color none
 521 měřená na
 522 \begin_inset Formula $R_{i}$
 523 \end_inset
 524
 525  co nejmenší.
 526 \end_layout
 527
 528 \begin_layout Standard
 529 Volba optimálního zobrazení
 530 \begin_inset Formula $c_{i}$
 531 \end_inset
 532
 533  a tedy i následně volba
 534 \begin_inset Formula $w_{i}$
 535 \end_inset
 536
 537  je silně závislá na použité metrice.
 538  Ve fraktální kompresi se téměř výhradně používá RMSE metrika (zde uvedena
 539  v\InsetSpace ~
 540 nebvyklé spojité podobě):
 541 \begin_inset Formula \[
 542 d_{RMSE}\left(g_{1},g_{2}\right)=\sqrt{\frac{\iintop_{R_{i}}\left[g_{1}\left(x,y\right)-g_{2}\left(x,y\right)\right]^{2}\,\mathrm{d}x\mathrm{\, d}y}{\iintop_{R_{i}}\,\mathrm{d}x\mathrm{\, d}y}}\]
 543
 544 \end_inset
 545
 546 Její hlavní výhody i nevýhody jsou dány tím, že se vždy berou v\InsetSpace ~
 547 úvahu pouze
 548  sobě odpovídající body
 549 \begin_inset Formula $g_{1}\left(x,y\right)$
 550 \end_inset
 551
 552  a
 553 \begin_inset Formula $g_{2}\left(x,y\right)$
 554 \end_inset
 555
 556 .
 557  To umožnuje velmi jednoduchou a rychlou práci s\InsetSpace ~
 558 metrikou a také optimalizaci
 559  v\InsetSpace ~
 560 ní, na druhou stranu díky tomu pro větší bloky nedává metrika výsledky
 561  odpovídající vizuálnímu rozdílu.
 562 \end_layout
 563
 564 \begin_layout Standard
 565 Při použití RMSE existuje právě jedno
 566 \begin_inset Foot
 567 status collapsed
 568
 569 \begin_layout Standard
 570 platí za předpokladu, že
 571 \begin_inset Formula $g\circ w_{i}$
 572 \end_inset
 573
 574  není konstantní na
 575 \begin_inset Formula $R_{i}$
 576 \end_inset
 577
 578  (tj.\InsetSpace ~
 579
 580 \begin_inset Formula $g$
 581 \end_inset
 582
 583  není konstantní na
 584 \begin_inset Formula $D_{i}$
 585 \end_inset
 586
 587 )\InsetSpace ~
 588 -- jinak by se jednalo o\InsetSpace ~
 589 aproximaci konstantním blokem, volba lineárního
 590  koeficientu by byla libovolná a výsledek vždy horší, než při výběru jakéhokoliv
 591  nekonstantního zdrojového bloku
 592 \end_layout
 593
 594 \end_inset
 595
 596  optimální
 597 \begin_inset Formula $c_{i}$
 598 \end_inset
 599
 600  a lze ho (pro dané
 601 \begin_inset Formula $g$
 602 \end_inset
 603
 604  a
 605 \begin_inset Formula $w_{i}$
 606 \end_inset
 607
 608 ) snadno spočítat analyticky.
 609  Podrobnosti jsou pro diskrétní případ rozebrány v\InsetSpace ~
 610 části <odkaz na kapitolu
 611  o\InsetSpace ~
 612 encoderu>.
 613 \end_layout
 614
 615 \begin_layout Subsubsection
 616 Rychlá konvergence
 617 \end_layout
 618
 619 \begin_layout Standard
 620 Fraktálová komprese v\InsetSpace ~
 621 této podobě stále trpěla jedním skrytým problémem.
 622  Při dodržení kontraktivity všech zobrazení
 623 \begin_inset Formula $c_{i}$
 624 \end_inset
 625
 626  kolážová věta sice zaručovala, že obrázek zkonverguje a nebude se příliš
 627  lišit, ale nijak neomezovala počet nutných iteračních kroků.
 628  Ukázalo se, že tento problém není jen teoretický\InsetSpace ~
 629 -- i\InsetSpace ~
 630 při přísnějších omezeních
 631  na kontraktivitu bylo pro některé obrázky nutné provádět mnoho desítek
 632  iterací než změny přestaly být okem viditelné.
 633 \end_layout
 634
 635 \begin_layout Standard
 636 Řešení tohoto problému bylo publikováno v\InsetSpace ~
 637
 638 \begin_inset LatexCommand cite
 639 key "Oien94"
 640
 641 \end_inset
 642
 643  a podrobněji rozebráno v\InsetSpace ~
 644
 645 \begin_inset LatexCommand cite
 646 key "Fish95"
 647
 648 \end_inset
 649
 650 .
 651  Jedná se jen o\InsetSpace ~
 652 drobnou modifikaci barevného zobrazení.
 653  Pokud bylo původní optimální barevné zobrazení ve tvaru
 654 \begin_inset Formula $c_{i}\left(z\right)=p_{i}\, z+q_{i}$
 655 \end_inset
 656
 657 , pak místo ukládání
 658 \begin_inset Formula $p_{i}$
 659 \end_inset
 660
 661  i
 662 \begin_inset Formula $q_{i}$
 663 \end_inset
 664
 665  je uloženo
 666 \begin_inset Formula $p_{i}$
 667 \end_inset
 668
 669  a průměrná barva bloku
 670 \begin_inset Formula $R_{i}$
 671 \end_inset
 672
 673 .
 674  Nové zobrazení pak znormalizuje barvu zdrojového bloku
 675 \begin_inset Formula $D_{i}$
 676 \end_inset
 677
 678  odečtením jeho aktuálního průměru, výsledek vynásobí lineárním koeficienem
 679
 680 \begin_inset Formula $p_{i}$
 681 \end_inset
 682
 683  a přičte předpočítanou průměrnou barvu bloku
 684 \begin_inset Formula $R_{i}$
 685 \end_inset
 686
 687  ve vstupním obrázku.
 688 \end_layout
 689
 690 \begin_layout Standard
 691 Formálně bude zobrazení vypadat
 692 \begin_inset Formula \[
 693 \bar{c_{i}}\left(z\right)=p_{i}\left(z-\frac{\iintop_{D_{i}}\bar{g}\left(x,y\right)\,\mathrm{d}x\mathrm{\, d}y}{\iintop_{D_{i}}\,\mathrm{d}x\mathrm{\, d}y}\right)+\frac{\iintop_{R_{i}}g\left(x,y\right)\,\mathrm{d}x\mathrm{\, d}y}{\iintop_{R_{i}}\,\mathrm{d}x\mathrm{\, d}y}\mbox{,}\]
 694
 695 \end_inset
 696
 697 kde
 698 \begin_inset Formula $g$
 699 \end_inset
 700
 701  značí vstupní obrázek a
 702 \begin_inset Formula $\bar{g}$
 703 \end_inset
 704
 705  právě dekódovaný obrázek z\InsetSpace ~
 706 předchozí iterace.
 707  Je důležité, že zatímco druhý zlomek je uložený v\InsetSpace ~
 708 charakteristice zobrazení
 709  a je stále stejný, první zlomek se může měnit s\InsetSpace ~
 710 každou iterací, takže z\InsetSpace ~
 711 matematic
 712 kého hlediska se
 713 \begin_inset Formula $\bar{c_{i}}$
 714 \end_inset
 715
 716  chová pokaždé jako jiné zobrazení.
 717 \end_layout
 718
 719 \begin_layout Standard
 720 V\InsetSpace ~
 721 rámci jedné iterace je ale
 722 \begin_inset Formula $\bar{c_{i}}$
 723 \end_inset
 724
 725  stále afinní zobrazení.
 726  Navíc lze snadno ukázat, že při použití RMSE metriky optimální afinní zobrazení
 727
 728 \begin_inset Formula $c_{i}$
 729 \end_inset
 730
 731  vždy zobrazuje průměnou barvu
 732 \begin_inset Formula $D_{i}$
 733 \end_inset
 734
 735  na průměrnou barvu
 736 \begin_inset Formula $R_{i}$
 737 \end_inset
 738
 739 , takže když
 740 \begin_inset Formula $\bar{g}\rightarrow g$
 741 \end_inset
 742
 743 , pak
 744 \begin_inset Formula $\bar{c_{i}}\rightarrow c_{i}$
 745 \end_inset
 746
 747 .
 748
 749 \end_layout
 750
 751 \begin_layout Standard
 752 V tomto přístupu je tedy iterační operátor složitější na vyhodnocení, ale
 753  má lepší vlastnosti, například efektivnější ukládání koeficientů zobrazení
 754  díky jejich menší korelaci.
 755  Koeficienty
 756 \begin_inset Formula $q_{i}$
 757 \end_inset
 758
 759  zobrazení
 760 \begin_inset Formula $c_{i}$
 761 \end_inset
 762
 763  byla většinou v\InsetSpace ~
 764 absolutní hodnotě malá čísla, ale mohla se pohybovat ve
 765  velkém rozsahu.
 766  Průměrná barva bloku se může pohybovat jen v\InsetSpace ~
 767 rozmezí
 768 \begin_inset Formula $\left[0,1\right]$
 769 \end_inset
 770
 771  a má jasnější význam\InsetSpace ~
 772 -- to pomáhá při volbě způsobu kvantizace při uložení
 773  do souboru a umožnuje například využít toho, že sousední bloky budou mít
 774  pravděpodobně blízkou barvu.
 775 \end_layout
 776
 777 \begin_layout Standard
 778 Další výhodou je mnohem rychlejší a jistější konvergence.
 779  Je vidět, že po každé iteraci mají všechny bloky
 780 \begin_inset Formula $R_{i}$
 781 \end_inset
 782
 783  správnou průměrnou barvu.
 784  Tím se vzhled zdrojových bloků
 785 \begin_inset Formula $D_{i}$
 786 \end_inset
 787
 788  hned po první iteraci dostane blízko vzorovému obrázku, což se při další
 789  iteraci promítne do cílových bloků
 790 \begin_inset Formula $R_{i}$
 791 \end_inset
 792
 793 .
 794 \end_layout
 795
 796 \begin_layout Standard
 797 Ve\InsetSpace ~
 798 výše odkazovaných publikacích je ukázáno, že po takovéto úpravě barevných
 799  zobrazení iterování konverguje ke stejnému výsledku a také, že za trochu
 800  silnějších předpokladů než zde uvedené bude potřebný počet iterací malý
 801  a bude záviset pouze na velikostech zdrojových a cílových bloků.
 802  Používá se zde diskrétní model obrázku\InsetSpace ~
 803 -- posloupnost reálných čísel, kde
 804  cílové bloky jsou tvořeny
 805 \begin_inset Formula $2^{b_{i}}$
 806 \end_inset
 807
 808  po sobě jdoucími hodnotami a zdrojové bloky o velikosti
 809 \begin_inset Formula $2^{d_{i}}$
 810 \end_inset
 811
 812  jsou tvořeny několika po sobě jdoucími cílovými bloky.
 813  Zmenšování bloků vždy probíhá zprůměrováním
 814 \begin_inset Formula $2^{d_{i}-b_{i}}$
 815 \end_inset
 816
 817  po sobě jdoucích hodnot.
 818 \end_layout
 819
 820 \begin_layout Standard
 821 Na rozdíl od konvergence založené na kolážové větě je důkaz proveden bez
 822  jakéhokoliv omezení na kontraktivitu barevných zobrazení
 823 \begin_inset Formula $\bar{c_{i}}$
 824 \end_inset
 825
 826 , což umožnuje mnohem přesnější aproximaci bloků s ostrými přechody bez
 827  ztráty jistoty konvergence.
 828  Zde se naopak využívá kontraktivity transformací
 829 \begin_inset Formula $w_{i}$
 830 \end_inset
 831
 832 .
 833 \end_layout
 834
 835 \begin_layout Standard
 836
 837 \newpage
 838
 839 \begin_inset LatexCommand bibtex
 840 options "bibtotoc,plain"
 841 bibfiles "fractals"
 842
 843 \end_inset
 844
 845
 846 \end_layout
 847
 848 \end_body
 849 \end_document