Fraktale w multimediach


FRACTAL IMAGE COMPRESSION



Pobieranie 274.68 Kb.
Strona4/4
Data25.10.2017
Rozmiar274.68 Kb.
1   2   3   4

FRACTAL IMAGE COMPRESSION

(Fraktalowa Kompresja Obrazu)


http://www.math.psu.edu/tseng/class/Fractals.html

Wprowadzenie do grafiki komputerowej – J.D. Foley



http://www.zssio.bielsko.ids.pl/edu/mat/fraktale/rys_f.htm#IFS


Wstęp


Dobrze znane przyczyny poszukiwania efektywnej kompresji obrazu:

 Możliwość przesyłania przez internet

 Możliwość łatwego przechowywania I przenoszenia
Standardowy CD-ROM może pomieścić do 650MB – to w zupełności wystarcza na przechowywanie tekstu – na takiej płycie można spokojnie zmieścić cały tekst opisany w Encyclopedia Britannica I jeszcze zostanie sporo wolnego miejsca.

Sytuacja się zmienia, jeżeli chcemy wcisnąć na taka płytę chociaż jeden film.



Kompresja Obrazu


Istnieją dwie podstawowe kategorie kompresji – stratna I bezstratna (lossless, lossy).

Kompresja bezstratna polega na możliwości odtworzenia każdego pojedynczego bitu pierwotnego pliku. Kompresja stratna ma wpływ na zawartość pliku, dąży jednak do tego, aby obraz był dla obserwatora niemalże identyczny.

Oczywiście kompresja stratna nie może być stosowana do plików tekstowych lub programów.
Najbardziej popularnymi formatami kompresji stratnej to JPEG (Joint Photographic Experts Group) czy GIF (CompuServe)

Istnieje również format Fractal Image Compression oparta na lokalnym samopodobienstwie obrazu – właścicielem formatu jest firma Iterated Systems, Inc.

Metody kompresji można tez podzielić na symetryczne I asymetryczne.

Przy metodach symetrycznych kompresja I dekompresja zajmuje mniej więcej tyle samo czasu. (JPEG). Metoda fraktalowa jest natomiast przykładem kompresji asymetrycznej.

Zdecydowanie więcej czasu jest potrzebne na kompresje niż na późniejsza dekompresje obrazu. Większość wymaganej pracy jest wykonywana podczas kompresji I dla tego dekompresja zajmuje już niewiele czasu.

Podstawowe Zasady

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, gdzie

Podstawę teoretyczną kompresji fraktalnej stanowi tzw. Collage Theorem.



Collage Theorem. Niech {R, wn : n = 1, ... , N} - układ hiperboliczny, tj.

d(wn(x), wn(y)) s d(x,y)

o atraktorze A. Załóżmy, że podzbiór spełnia nierówność

dla

Wówczas

FRACTAL IMAGE COMPRESSION

Zakładamy, ze chcemy skompresować zdjęcie B w formacie cyfrowej bit-mapy.

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-bialego 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ło by 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 czarnobialego, 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 samopodobne obszary. Nie mogą one zachodzić na siebie. (domain regions)

Następnie tworzony jest zbiór możliwych “obszarów – zakresów”. (range regions) Mogą zachodzić na siebie I musza być większe niż obszary podstawowe.

Następnie algorytm szuka dla podstawowego obszaru odpowiedniego “obszaru-zakresu”

Który po zastosowaniu odpowiedniej transformacji afinicznej będzie do złudzenia przypominał podstawowy obszar.

Jako rezultat tworzony jest plik FIF (Fractal Image Format) dla zdjęcia.

Plik taki zawiera informacje na temat obszarów podstawowych oraz listę współrzędnych afinicznych wszystkich powiązanych transformacji czyli obraz zostaje zapisany jako zbiór przekształceń za pomocą których możemy potem odwzorować zdjęcie w jego kopie.

Tak wiec piksele z danego obszaru są zamieniane na opis macierzy transformującej z 1-bitowym opisem 0 – 255.

Ten proces jest niezależny od rozdzielczości oryginalnego zdjęcia. Zdjęcie wynikowe będzie wyglądało tak samo niezależnie od rozdzielczości – ponieważ kompresor znalazł funkcje IFS której atraktor replikuje oryginalny obraz. Proces ten nie posiada wady typowej dla JPEG czyli zblokowania pikseli.

Proces kompresji pochłania dużo pracy, w szczególności szukanie odpowiednich obszarow-zakresow. Jednak po dokonaniu pełnej kompresji dekompresja następuje nieporównywalnie szybko.

Ten typ kompresji pozwala na wybór jakości – im niższa jakość obrazu wynikowego tym szybsza kompresja.

Dekompresja obrazu:

Aby dokonać dekompresji, potrzebna jest alokacja dwóch buforów w pamięci.

W buforze pierwszym przechowywane są obraz-zakres, natomiast w drugim obraz-podstawowy. Obraz podstawowy jest dzielony na obszary podstawowe zgodnie z opisem w pliku FIF. Dla każdego obszru-podstawowego jest lokalizowany obszar-zakres.

Odpowiednie odwzorowanie afiniczne jest aplikowane do obszaru-zakresu,

“pociągając” zawartość w stronę atraktora odwzorowania.

Ponieważ każde odwzorowanie jest zwężające, również obszar-zakres ulega zmniejszeniu. Dlatego podczas kompresji obszary-zakresu musza być większe niż

obszary-podstawowe.
W następnej iteracji obszar-zakresu I obszar-podstawowy zamieniają się rolami.

Proces odwzorowania odbywa się od obszarow-zakresow do obszarow-podstawowych.

Operacja jest powtarzana wielokrotnie, formowany jest obraz wyjściowy.
Kompresja – od kilkudziesięciu do kilkuset razy!
Inaczej:
Działanie takiego algorytmu opiera się więc na podzieleniu obrazu (ściślej - dziedziny owej funkcji) na fragmenty i następnie podaniu przekształceń, za pomocą których można odtworzyć cały obraz z jego części

FIC vs. JPEG

Format JPEG posługuje się metoda DCT (Discrete Cosine Transform).

DCT rozdziela obraz na małe części, z reguły 8 na 8 pikseli, następnie konwertuje natężenie pikseli w ich odpowiedniki wyrażone w częstotliwości. Rezultatem takiej operacji są 64 wykresy cosinusoidalne o rożnej amplitudzie.

Kompresja jest dokonywana poprzez odrzucenie wysokich częstotliwości.

Taka operacja powoduje utratę drobnych, mało znaczących części obrazu.

Jeżeli obraz zawiera ostre krawędzie, które zapisywane są w zakresie wysokich częstotliwości, DCT spowoduje ich “rozmazanie”

Dodatkowo, format JPEG jest zależny od rozdzielczości.

Takiej samej wielkości obraz większej rozdzielczości musi być podzielony na znacznie większą liczbę kwadratów 8 na 8 pikseli.


FIC nie posiada tych negatywnych cech.

Ma tez jednak swoje wady- długa kompresja nie pozwala na transmisje video w czasie rzeczywistym.



Jedna z aplikacji używających FIF jest Microsoft Encarta.

Maciej Zabielski Strona 10/25/17


Pobieranie 274.68 Kb.

Share with your friends:
1   2   3   4




©operacji.org 2020
wyślij wiadomość

    Strona główna
warunków zamówienia
istotnych warunków
przedmiotu zamówienia
wyboru operacji
Specyfikacja istotnych
produktu leczniczego
oceny operacji
rozwoju lokalnego
strategii rozwoju
kierowanego przez
specyfikacja istotnych
Nazwa przedmiotu
Karta oceny
ramach działania
przez społeczno
obszary wiejskie
dofinansowanie projektu
lokalnego kierowanego
Europa inwestująca
Regulamin organizacyjny
przetargu nieograniczonego
kryteria wyboru
Kryteria wyboru
Lokalne kryteria
Zapytanie ofertowe
Informacja prasowa
nazwa produktu
Program nauczania
Instrukcja obsługi
zamówienia publicznego
Komunikat prasowy
programu operacyjnego
udzielenie zamówienia
realizacji operacji
opieki zdrowotnej
przyznanie pomocy
ramach strategii
Karta kwalifikacyjna
oceny zgodno
Specyfikacja techniczna
Instrukcja wypełniania
Wymagania edukacyjne
Regulamin konkursu
lokalnych kryteriów
strategia rozwoju
sprawozdania finansowego
ramach programu
ramach poddziałania
kryteriów wyboru
operacji przez
trybie przetargu