KOmpresja DAnych (KODA)

Materiały

Wykład dotyczy zagadnienia kompresji danych, w tym całego procesu opracowania efektywnego algorytmu kompresji: od przesłanek teoretycznych i charakterystyki źródła informacji poprzez koncepcje, modele, kody, algorytmy, po praktyczne realizacje i eksperymenty weryfikujące użyteczność.

Prezentowana jest krótka charakterystyka wybranych elementów teorii informacji oraz zniekształceń źródeł informacji, analizy funkcjonalnej, metod przetwarzania obrazów i teorii aproksymacji. Podstawy teoretyczne uzupełnia analiza współczesnych formatów i standardów kompresji z uwzględnieniem potencjalnych obszarów zastosowań.

Istotnym elementem jest dedykowany zdobyciu umiejętności oceny przydatności różnego typu narzędzi w kontekście wybranych zastosowań oraz zdolności konstruowania prostych, ale efektywnych algorytmów kompresji.

Tematyka dotyczy wybranych zagadnień kompresji bezstratnej i stratnej ze szczególnym uwzględnieniem danych obrazowych. W szczególności:

Wprowadzenie: przegląd różnego typu danych i zbiorów danych oraz formatów ich zapisu, występujących w systemach informatycznych (głównie pliki tekstowe i graficzne, obrazy naturalne, medyczne, czarno-białe, wideo); podstawowe pojęcia z dziedziny kompresji, rozwój nowoczesnych metod kompresji;

Elementy teorii informacji: informacja i nadmiarowość, modele źródeł informacji (m.in. źródło Markowa), entropijne miary ilości informacji, twierdzenia o kodowaniu źródeł, reguły i ograniczenia efektywnego kodowania danych, kody (przedrostkowe, drzew binarnych, symboli, strumieniowe);

Podstawowe metody bezstratnej kompresji danych: schematy ogólne bezstratnych metod kompresji, kody długości serii, Shannona-Fano, Huffmana, Golomba, przekształcenie BWT, algorytmy adaptacyjne;

Efektywne metody bezstratnej kompresji danych: kodowanie arytmetyczne (w tym kodery binarne), słownikowe (m.in. archiwizery rodziny ZIP), metody predykcyjne (DPCM, nieliniowe, w przestrzeni obrazu), przegląd dostępnych bibliotek (m.in. ZLIB, QccPack);

Techniki i standardy odwracalnej kompresji obrazów: predykcja 2-D (HINT, CALIC), modelowanie i kwantyzacja kontekstu (CALIC, JPEG-LS), standardy GIF, PNG, JPEG-LS, JBIG;

Podstawy stratnej kompresji danych: teoria zniekształceń źródeł informacji, optymalizacja R-D, metody kwantyzacji, miary jakości, cechy koderów (elastyczność, interakcyjność, progresja, odwracalność);

Efektywne metody kompresji nieodwracalnej: stratna predykcja (JPEG-LS), wektorowa kwantyzacja, kodowanie transformacyjne z DCT (standard JPEG), z analizą wielorozdzielczą (JPEG2000, DjVu), kompresja map bitowych (JBIG);

Optymalizacja kodeka obrazów: metoda SPIHT, rozszerzenia standardu JPEG2000 (do transmisji bezprzewodowej, danych 3W, sekwencji obrazów), najnowsze koncepcje zaawansowanych koderów obrazów;

Przykłady zastosowań, głównie medycznych i internetowych: archiwizacja z kompresją i indeksowaniem, interakcyjne protokoły transmisji obrazów (JPIP) oraz porządkowanie informacji do celów telediagnostyki.

Ciekawe linki

Literatura

 

Materiały (tylko do celów dydaktycznych i naukowych):

Tematy projektów

Top lista projektów

Skrypt (wersja beta)

Prezentacje:
    wprowadzenie 
    informacja 
    kody symboli 
    kod arytmetyczny 
    metody słownikowe 
    metody predykcyjne, bezstratna kompresja obrazów
    metody wektorowej kwantyzacji
    metody transformacyjne
    metody falkowe

Przykładowe zadania egzaminacyjne

Wstęp do JPEG

Wstęp do JPEG2000

LABKO - laboratorium kompresji (narzędzia z sieci oraz własne)

Wyniki

Linki:

Kompresja bezstratna

Lossless compression

Kompresja stratna

Compression Research

Kompresja falkowa

Wavelet Resources

Biblioteki

DataCompression Library

Compression Pointers

Mitsuharu ARIMURA's Bookmarks on Source Coding/Data Compression

Data compression of raindrop

Narzędzia

SPIHT wavelet coder

Standardy

JPEG

MPEG

DjVu

Ocena efektywności

Image Communications Lab: PSNR Results

Xiaolin Wu

Więcej

Literatura:

 

  1. A. Przelaskowski, "Kompresja danych: podstawy, metody bezstratne, kodery obrazów", Wydawnictwo BTC, W-wa, 2005.
  2. W. Skarbek, "Metody reprezentacji obrazów cyfrowych", Akademicka Oficyna Wydawnicza PLJ, W-wa 1993.
  3. W. Skarbek, "Multimedia. Algorytmy i standardy kompresji", Akademicka Oficyna Wydawnicza PLJ, W-wa 1998.
  4. M. Nelson, "The Data Compression Book", 1991.
  5. M. Rabbani, P. W. Jones, "Digital Image Compression Techniques", SPIE Press, 1991.
  6. K. Sayood, "Introduction to Data Compression", Morgan Kaufmann Publishers, 1996.
  7. K. Sayood, "Kompresja danych. Wprowadzenie", READ ME, 2002.
  8. A. Drozdek, "Wprowadzenie do kompresji danych", WNT, 1999.
  9. M. Domański, "Zaawansowane techniki kompresji obrazów i sekwencji wizyjnych", Wydawnictwo Politechniki Poznańskiej, 2000.

 

Termin ostatniej modyfikacji: 20.10.2005