Kompresja rastrowych map geograficznych wykorzystujĐca transformacje falkowe.pdf

Politechnika Gdańska

WYDZIAŁ ELEKTRONIKI

TELEKOMUNIKACJI I

INFORMATYKI

Katedra: Systemów Geoinformatycznych

Imię i nazwisko dyplomanta: Janusz Blank

Nr albumu: 88916

Rodzaj studiów: dzienne

Kierunek studiów: Informatyka

Praca magisterska

Temat pracy: Kompresja rastrowych map geograficznych wykorzystująca transformacje

falkowe.

Kierujący pracą: dr hab. inż. Marek Moszyński

Zakres pracy: Przegląd technik kompresji stosowanych do obrazów stałych ze szczególnym

uwzględnieniem tych opartych na wykorzystaniu transformacji falkowej. Opracowanie

standardu kompresji dedykowanej do map historycznych. Implementacja algorytmów

transformacji falkowej dla obrazów stałych. Realizacja oprogramowania do kompresji map

historycznych i oprogramowania rozszerzającego właściwości przeglądarek do ich

prezentacji.

Gdańsk, 2006

1. WSTĘP............................................................................................................................................................... 3

1.1. W PROWADZENIE .......................................................................................................................................... 3

1.2. G ŁÓWNE CELE .............................................................................................................................................. 4

1.3. P RZEGLĄD ROZDZIAŁÓW .............................................................................................................................. 4

2. WYBRANE ZAGADNIENIA Z TEORII FALEK ........................................................................................ 6

2.1. P ERSPEKTYWA HISTORYCZNA ...................................................................................................................... 6

2.2. P ODSTAWY TEORETYCZNE ........................................................................................................................... 8

2.2.1. Transformata Fouriera........................................................................................................................ 8

2.2.2. Ciągła transformata falkowa............................................................................................................. 10

2.2.3. Dyskretna transformata falkowa i algorytm Mallata ........................................................................ 12

2.3 Z ASTOSOWANIA FALEK ............................................................................................................................... 16

3. METODY KOMPRESJI OBRAZÓW W ZASTOSOWANIU DO DANYCH GEOGRAFICZNYCH .. 18

3.1. F ORMAT JPEG ........................................................................................................................................... 18

3.2. F ORMAT M R SID ........................................................................................................................................ 20

3.3. F ORMAT ECW............................................................................................................................................ 22

3.4. F ORMAT JPEG 2000................................................................................................................................... 24

3.4.1. Model obrazu..................................................................................................................................... 25

3.4.2. Struktura kodera ................................................................................................................................28

3.4.3. Przetwarzanie wstępne ...................................................................................................................... 29

3.4.4. Transformacja falkowa...................................................................................................................... 30

3.4.5. Kwantyzacja ...................................................................................................................................... 34

3.4.6. Kodowanie Tier-1 .............................................................................................................................. 35

3.4.7. Kodowanie Tier-2 .............................................................................................................................. 40

3.4.8. Kodowanie nagłówka pakietu............................................................................................................ 43

3.4.9. Kodowanie pakietu ............................................................................................................................ 44

3.5. P RZEWAGA FORMATÓW FALKOWYCH NAD STARSZYMI FORMATAMI .......................................................... 45

3.6. P ARAMETRY KOMPRESJI DLA RÓŻNYCH FORMATÓW .................................................................................. 46

4. PROJEKT SYSTEMU I ARCHITEKTURA OPROGRAMOWANIA ..................................................... 51

4.1. K ODER ....................................................................................................................................................... 51

4.2. F ORMAT PLIKU ........................................................................................................................................... 56

4.3. D EKODER ................................................................................................................................................... 59

5. IMPLEMENTACJA ....................................................................................................................................... 61

5.1. Z AŁOŻENIA WSTĘPNE ................................................................................................................................. 61

5.2. K ODER ....................................................................................................................................................... 61

5.2.1. Technologia wykonania ..................................................................................................................... 62

5.2.2. Kompilacja ........................................................................................................................................ 62

5.2.3. Instalacja ........................................................................................................................................... 63

5.2.4. Interfejs.............................................................................................................................................. 64

5.2.5. Instrukcja obsługi .............................................................................................................................. 65

5.3. D EKODER ................................................................................................................................................... 65

5.3.1. Technologia wykonania ..................................................................................................................... 65

5.3.2. Kompilacja ........................................................................................................................................ 67

5.3.3. Instalacja ........................................................................................................................................... 68

5.3.4. Interfejs.............................................................................................................................................. 68

5.3.5. Instrukcja obsługi .............................................................................................................................. 69

6. WNIOSKI ........................................................................................................................................................ 71

BIBLIOGRAFIA................................................................................................................................................. 75

DODATEK A ...................................................................................................................................................... 76

1. Wstęp

1.1. Wprowadzenie

Początek XXI wieku to początek ery informacji, która charakteryzuje się intensywnym

rozwojem społeczeństwa informacyjnego, przekształcającego się w społeczeństwo wiedzy, w

którym przetwarzanie i tworzenie wiedzy jest podstawą jego rozwoju.

Znakiem czasu jest nadmiar informacji. Zewsząd otoczeni jesteśmy informacjami różnej

jakości, dotyczących wszystkich dziedzin życia. Coraz bardziej pożądane stają się narzędzia

zwiększające ułatwiające skuteczną selekcje informacji. Szybki dostęp do istotnej i

wiarygodnej informacji staje się zagadnieniem kluczowym.

Pojawiają się zatem pytania i naturę informacji, jej opis ilościowy i sens, a także jak ją

wybierać, przetwarzać i klasyfikować. Wymaga to konstruowania systemów i narzędzi

operujących na danych, najlepiej w postaci upakowanej, ułatwiającej analizę, przechowanie i

przesyłanie. Celem kompresji danych jest uzyskanie optymalnej reprezentacji. Zmniejsza ona

rozmiar przesyłanych zbiorów, daje szybszy dostęp do informacji, porządkuje i wpływa na

jakość informacji. Rośnie ilość informacji zapisywanej na nośniku o danej pojemności.

Rośnie ilość informacji dostarczanej w jednostce czasu, jest ona bardziej użytecznie

reprezentowana. Efektywna kompresja dociera do istoty informacji, jest więc narzędziem

niezwykle przydatnym.

W informatyce, kompresja danych polega na zmianie sposobu zapisu informacji w taki

sposób, aby zmniejszyć redundancję i tym samym objętość zbioru, nie zmieniając

przenoszonych informacji. Innymi słowy chodzi o wyrażenie tego samego zestawu

informacji, lecz za pomocą mniejszej liczby bitów. Działaniem przeciwnym do kompresji jest

dekompresja.

Kompresja dzieli się na bezstratną, w której z postaci skompresowanej można

odzyskać identyczną postać pierwotną, oraz stratną, w której takie odzyskanie jest

niemożliwe, jednak główne właściwości które nas interesują zostają zachowane. Kompresja

falkowa jest algorytmem wydajnej ale stratnej kompresji. Oparta jest o transformatę falkową.

Głównie kojarzona jest z kompresją grafiki, chociaż rodzaj danych, które można

kompresować nie jest zdeterminowany.

Analiza falkowa to dziedzina młoda, licząca zaledwie dziesięć lat. Umożliwia

jednoczesne przedstawienie czasowych oraz częstotliwościowych własności sygnałów i

prowadzi do aproksymacji sygnałów przez wyodrębnienie ich charakterystycznych

elementów strukturalnych. Dziś analiza falkowa jest stosowana w geofizyce, fizyce,

astronomii, biologii, a także w ekonomii. Jest obecna w sejsmologii i w hydrodynamice.

Wykorzystuje się ją w analizie mowy i w sterowaniu procesami przemysłowymi. Ma więc

wiele zastosowań, a jej popularność ciągle rośnie.

1.2. Główne cele

W niniejszej pracy dokonano teoretycznego wprowadzenia do zagadnień teorii falek.

Następnie przedstawiono niektóre istniejące standardy kompresji obrazów stałych.

Szczególną uwagę zwrócono na te z nich, oparte o transformację falkową. Następnie

zaproponowano standard kompresji dedykowany do rastrowych map historycznych, oparty o

wspomnianą transformację. Jednym z głównych celów pracy jest również stworzenie

oprogramowania realizującego kompresję w proponowanym standardzie, oraz

oprogramowania służącego do prezentacji obrazów w omawianym formacie.

1.3. Przegląd rozdziałów

Drugi rozdział pracy stanowi teoretyczne wprowadzenie w zagadnienia teorii falek i

analizy wielorozdzielczej. Dokonano w nim wprowadzenia historycznego, stwarzając

kontekst powstania teorii oraz przedstawiając niektóre z wczesnych odkryć z użyciem falek.

Następnie dokonano omówienia istoty analizy falkowej za pomocą porównania do dobrze

poznanej analizy Fourierowskiej. Skupiając się na dyskretnej wersji transformacji falkowej,

omówiono algorytmu obliczania transformaty z wykorzystaniem filtrów, za pomocą metody

Mallata. Zamykając wstęp teoretyczny wskazano na różnorodność zastosowań wskazując na

dziedziny nauki, w których teoria falek znajduje zastosowanie.

W trzecim rozdziale omówiono standardy kompresji używane do obrazów rastrowych.

Wśród omówionych standardów znajdzie się popularny format JPEG, bazujący na dyskretnej

transformacji kosinusowej, oraz jego następca, format JPEG2000 bazujący już na

transformacji falkowej. Omówiono również standardy MrSID oraz ECW, wykorzystywane do

kompresji danych geograficznych w postaci map rastrowych i znanych z aplikacji typu GIS

(ang. Geographic Information System ). Formaty te bazują na transformacji falkowej.

Czwarty rozdział traktuje o proponowanym standardzie kompresji. Przedstawiono w

nim projekt systemu, założenia i architekturę stworzonego oprogramowania. Omówiono

wykorzystywane metody oraz strukturę i działanie zaprojektowanego systemu, składającego

się z kodera i dekodera plików .wvb w proponowanym formacie. Przedstawiono format pliku

i możliwości wykorzystania jego zalet podczas transmisji plików przez sieć.

W piątym rozdziale omówiono szczegóły implementacyjne, takie jak wykorzystane

technologie, zasady kompilacji i instalacji. Przedstawiono interfejs opracowanego systemu

kompresji i omówiono zasady korzystania.

Rozdział szósty poświęcono na wnioski dotyczące transformacji falkowej oraz jej

wykorzystania do kompresji obrazów stałych. Pokazano zestawienia rozmiarów różnych

plików dla tych samych obrazów, wskazując na przewagę formatów wykorzystujących

transformacje falkowe.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: