First page Back Continue Last page Overview Graphics

Podstawowe kompresje


Notes:

Krotki wstęp
Iloczyn dowolnej sekwencji macierzy (ZLOZENIE) obrotu, przesunięcia i skalowania nazywamy przekształceniem afinicznym. Takie przekształcenie ma bardzo ważna właściwość – zawsze zostaje zachowana równoległość linii.
Rozpatrzymy teraz przekształcenie afiniczne w R2: W(x,y) = (ax+by+e,cx+dy+f).
Parametry a, b, c oraz d są odpowiedzialne za część liniowa i opisują obrót, przesuniecie i skalowanie natomiast parametry e i f to odległości przesunięć w kierunku x i y.
Będziemy korzystać tylko ze zwężających (contractive) odwzorowań afinicznych. Odwzorowanie afiniczne jest uważane za zwężające, jeżeli jego współczynnik skalowania jest mniejszy od 1.
Skończony zbiór zwężających odwzorowań afinicznych W1, W2, …,Wn tworzy wcześniej wspomniane IFS - iterated functions system
Jeżeli założymy, ze B jest niepustym zwartym podzbiorem Rn wtedy odwzorowanie W(B) = U Wi(B) jest odwzorowaniem zwężającym w H – przestrzeni metrycznej zwartych zbiorów w Rn.
Dla przestrzeni R można zdefiniować zwartą przestrzeń metryczną H z metryką Hausdorffa h, gdzie H - zbiór wszystkich niepustych domkniętych podzbiorów R.
Atraktorem iterowanego układu funkcji nazywa się zbiór G € H taki, że W(G) = G.
Podstawę teoretyczną kompresji fraktalnej stanowi tzw. Collage Theorem. 
FRACTAL IMAGE COMPRESSION – KOMPRESJA FRAKTALOWA
Zakładamy, ze chcemy skompresować zdjęcie B w formacie cyfrowej bitmapy. Rozdzielczość m na n pikseli, plik składa się z nagłówka za którym występuje m*n komórek danych, po jednej dla każdego piksela. Mając podana rozdzielczość, możemy określić współrzędne każdego piksela. I tak pierwsza komórka n jest to pierwszy rząd pikseli zaczynając od lewej.Wielkość takiej komórki jest rożna w zależności od rodzaju zdjęcia.Dla najprostszego, czarno-białego ta wielkość to 1 bit – 0  biały 1  czarny
Otrzymujemy wiec prosty dwuwymiarowy zbiór w którym interesują nas tylko piksele, których bit = 1.
Tak wiec możemy rozpatrywać to zdjęcie jako zwarty podzbiór R2.
Jeżeli nasze zdjęcie B byłoby w skali szarości, rozpatrywalibyśmy je jako podzbiór R3. Trzeci bit byłby odpowiedzialny za określenie intensywności skali szarości.
Jeżeli B byłoby zdjęciem kolorowym, rozpatrywalibyśmy je jako podzbiór R5.
Poza dwoma podstawowymi pikselami jak to było w przypadku zdjęcia czarnobiałego, potrzebne są jeszcze 3 pozycje dla RGB. Poprzez odpowiednie sterowanie natężeniem poszczególnych kolorów RGB możemy uzyskać dowolny widziany przez oko ludzkie kolor. W komputerach każdy kolor jest dzielony na 256 poziomów natężenia.
Z obserwacji Barnsley’a wynika, ze obrazy z rzeczywistego świata zawierają dużo powtórzeń afinicznych. Oznacza to, ze przy odpowiedniej funkcji IFS duże części obrazu są podobne do mniejszych części tego samego obrazu. Obraz jest traktowany jako funkcja f(x, y) opisująca piksel.
System kompresji fraktalowej najpierw dzieli obraz wejściowy na “podstawowe obszary” dowolnego kształtu i wielkości wynajdując samo podobne obszary. Nie mogą one zachodzić na siebie. (domain regions)