Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Kompresja danych
Koordynator przedmiotu:
Artur Przelaskowski
Status przedmiotu:
Fakultatywny ograniczonego wyboru
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne - zaawansowane
Kod przedmiotu:
KODA
Semestr nominalny:
4 / rok ak. 2014/2015
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Realizacja przedmiotu obejmuje następujące formy zajęć: - wykład prowadzony w wymiarze 2 godz. tygodniowo, - zajęcia projektowe w wymiarze 1 godz. tygodniowo; - student może ponadto uczestniczyć w cotygodniowych konsultacjach (w wymiarze do 2 godz.). Bilans nakładu pracy przeciętnego studenta wygląda następująco: - udział w wykładach: 30 godz. - przygotowanie do kolejnych wykładów, rozwiązywanie sygnalizowanych na wykładzie problemów: 20 godzin - udział w zajęciach projektowych (omówienie projektów, wybór tematu, zaliczanie projektu): 3 godziny - realizacja projektu (analiza teoretyczna, realizacja algorytmiczna, implementacja, eksperymenty, sprawozdanie): 40 godzin - udział w konsultacjach: 6 godz. (zakładamy, że student sześciokrotnie w ciągu semestru korzysta z 1-godz. konsultacji dot. wykładu i projektu, w proporcjach 1:2) - przygotowanie do egzaminu końcowego (rozwiązanie zadań przygotowawczych): 15 godzin Łączny nakład pracy studenta wynosi zatem: 30+ 20 + 3 + 40 + 6 + 15 = 114 godz., co odpowiada ok. 4 punktom ECTS.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- udział w wykładach: 30 godz. - udział w zajęciach projektowych (omówienie projektów, wybór tematu, zaliczanie projektu): 3 godziny - udział w konsultacjach: 6 godz. (zakładamy, że student sześciokrotnie w ciągu semestru korzysta z 1-godz. konsultacji dot. wykładu i projektu, w proporcjach 1:2) w sumie 30 + 3 + 6 = 39 godz., co odpowiada ok. 1.5 punktom ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- udział w zajęciach projektowych (omówienie projektów, wybór tematu, zaliczanie projektu): 3 godziny - realizacja projektu (analiza teoretyczna, realizacja algorytmiczna, implementacja, eksperymenty, sprawozdanie): 40 godzin - udział w konsultacjach: 4 godz. (zakładamy, że student sześciokrotnie w ciągu semestru korzysta z 1-godz. konsultacji dot. wykładu i projektu, w proporcjach 1:2) Nakład pracy związany z zajęciami o charakterze praktycznym wynosi 3 + 40 + 4 = 47 godz., co odpowiada ok. 2 punktom ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
Podstawy przetwarzania danych (obrazów, dźwięku). Podstawy algorytmów i struktur danych. Podstawy probabilistyki, algebry liniowej i analizy matematycznej.
Limit liczby studentów:
100
Cel przedmiotu:
Celem jest przekazanie wiedzy i umiejętności z zakresu podstaw teoretycznych oraz metodologii kodowania danych, zasad realizacji prostych algorytmów kompresji, przegląd współczesnych narzędzi i standardów z uwzględnieniem potencjalnych obszarów zastosowań, analiza możliwości oraz kryteriów i sposobów doboru koderów optymalnych dla określonego rodzaju danych, a także sformułowanie współczesnych paradygmatów kompresji. Wśród prezentowanego zarysu teorii użytecznych znajdują się przede wszystkim podstawy teorii informacji w zakresie modeli i reguł obejmujących kodowanie odwracalne oraz zniekształcenia źródeł informacji. Uzupełniają je wybrane zagadnienia analizy funkcjonalnej, teorii aproksymacji oraz przetwarzania i analizy obrazów. Wśród metod omawiane są zasady tworzenia kodów jednoznacznie dekodowalnych, sposoby redukcji nadmiarowości w reprezentacji danych tekstowych, obrazowych, przestrzennych, sekwencji obrazów. Na przykładzie kodu Huffmana oraz arytmetycznego analizowane są problemy związane z implementacją kodeków, ich optymalizacją i pragmatycznym upraszczaniem teoretycznych założeń.
Treści kształcenia:
Treść wykładu: - 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, dźwięk, obrazy naturalne, medyczne, czarno-białe, wideo); podstawowe pojęcia z dziedziny kompresji, rozwój nowoczesnych metod kompresji (2h); - Podstawy teorii informacji: definicje informacji, nadmiarowość, kanał informacji, modele źródeł informacji (m.in. źródło Markowa), miary ilości informacji, twierdzenia o kodowaniu źródeł, reguły i ograniczenia efektywnego kodowania danych, kody jednoznacznie dekodowalne, praktyczne wykorzystanie modeli teoretycznych - kody optymalne, (3h); - Podstawowe metody kodowania odwracalnego: schematy ogólne i paradygmaty bezstratnych metod kompresji, kodery długości sekwencji, Shannona-Fano, Huffmana (statyczny i dynamiczny), Golomba, przekształcenia BWT i adaptacyjne modele kontekstowe (3h); - Efektywne metody bezstratnej kompresji danych: kodowanie arytmetyczne (m.in. szybkie kodeki binarne typu BAC i FBAC), słownikowe (m.in. przegląd archiwizerów rodziny ZIP), metody predykcyjne (wstecz, wprzód, DPCM, nieliniowe,), analiza porównawcza skuteczności znanych narzędzi kompresji dla różnego typu danych, przegląd dostępnych bibliotek (m.in. ZLIB, BZIP2, QccPack) (6h); - Wybrane standardy odwracalnej kompresji obrazów: predykcja 2-D (adaptacyjne modele przełączane, HINT, kilkuetapowe), modelowanie i kwantyzacja kontekstu (CALIC, JPEG-LS), standardy GIF, PNG, JPEG-LS, JBIG (2h); - Podstawy metod selekcji informacji: teoria zniekształceń źródeł informacji, optymalizacja R-D, średnia informacja wzajemna, metody kwantyzacji, kryteria i metody oceny jakości rekonstrukcji danych, podstawowe cechy skutecznych algorytmów kompresji – elastyczność, interakcja, skalowalność, hierarchia informacji, zagnieżdżanie kodu, sterowana średnia bitowa (2h); - Metody kompresji nieodwracalnej: stratna predykcja (JPEG-LS), BTC, wektorowa kwantyzacja, kodowanie transformacyjne z DCT (standard JPEG), modyfikacje JPEG-XR, z analizą wielorozdzielczą (EZW, JPEG2000), kompresja map bitowych (JBIG), zasady kodowania dźwięku (AAC), kodowanie wideo (MPEG-2, AVC) (7h); - Optymalizacja kodeka obrazów: zalety falkowej metody SPIHT, rozszerzenia standardu JPEG2000 (do transmisji bezprzewodowej, kompresji danych przestrzennych, sekwencji obrazów, zabezpieczenia danych), najnowsze koncepcje zaawansowanych koderów obrazów (AIC) (3h); - Przykłady zastosowań multimedialnych: archiwizacja z kompresją i indeksowaniem, interakcyjne protokoły transmisji obrazów (JPIP) oraz progresja i skalowanie informacji do celów telekonsultacji (2h). Zakres projektu: Zadania projektowe obejmują takie aktywności jak studia literaturowe, opracowanie koncepcji i algorytmów kodowania, implementacja poznanych metod kompresji, analiza najnowszych standardów, formatów czy narzędzi (w zakresie algorytmów, dostępnych pakietów oprogramowania, optymalizacja i modyfikacja dostępnych bibliotek, implementacje sprzętowe, projektowanie i realizacja testów weryfikacji narzędzi. Treść poszczególnych zadań projektowych, stale aktualizowanych, należy do jednej z kilku zasadniczych grup tematycznych: - samodzielna realizacja prostych aplikacji kodeków (według kodu Huffmana, arytmetycznego, Golomba, słownikowego, predykcji, RLE, wykorzystującego BWT) oraz narzędzi wspomagających (do liczenia entropii, do eksperymentalnej weryfikacji określonych kodeków); - realizacja kodeków złożonych (archiwizery, CALIC, JPEG-LS, kodek falkowy, kodek obrazów z serializacją, JPEG-XR, JPEG2000) oraz monitorów śledzących działanie wybranego algorytmu - z możliwością wykorzystania zewnętrznych bibliotek; - optymalizacja i testy kodeków złożonych, z wykorzystaniem dostępnych pakietów oprogramowania (JPEG2000, MPEG-2 i MPEG-4, DIRAC, SNOW, kodeki dźwięku CAC, AAC, AC-3, Vobis itp.); - analiza teoretyczna w zakresie wybranych zagadnień (podstaw wykorzystywanych teorii, specyficznych zastosowań – np. kompresji grafiki, systemy telemedyczne, itd.) i dostępnych narzędzi i usług bazujących na algorytmach kodowania.
Metody oceny:
Przedmiot jest zaliczany na podstawie wyników z egzaminu oraz zaliczenia projektu. Ocena końcowa jest średnią ocen uzyskanych z egzaminu oraz projektu. Egzamin jest oceną pisemnej umiejętności rozwiązywania krótkich zadań problemowych z zakresu prezentowanej wiedzy. W ramach projektu student realizuje wybrane zadania z elementami analizy teoretycznej, praktycznej realizacji oraz eksperymentalnej weryfikacji.
Egzamin:
tak
Literatura:
1. Przelaskowski A., "Kompresja danych: podstawy, metody bezstratne, kodery obrazów", Wydawnictwo BTC, str. 258, 2005. 2. A.Przelaskowski, "Kompresja danych", skrypt internetowy, http://www.ire.pw.edu.pl/~arturp/Dydaktyka/koda/skrypt.html 3. A. Przelaskowski, "Falkowe metody kompresji danych obrazowych", Prace Naukowe – Elektronika, z. 138, Oficyna Wydawnicza PW, 2002. 4. K. Sayood, "Kompresja danych. Wprowadzenie", READ ME, 2002. 5. W. Skarbek, "Metody reprezentacji obrazów cyfrowych", Akademicka Oficyna Wydawnicza PLJ, W-wa 1993. 6. W. Skarbek (red.), "Multimedia. Algorytmy i standardy kompresji", Akademicka Oficyna Wydawnicza PLJ, W-wa 1998. 7. A. Drozdek, "Wprowadzenie do kompresji danych", WNT, 1999. 8. M. Domański, "Zaawansowane techniki kompresji obrazów i sekwencji wizyjnych", Wydawnictwo Politechniki Poznańskiej, 2000. 9. D. Salomon, "A concise introduction to data compression", Springer, 2008. 10. M. Nelson, "The Data Compression Book", M&T Books, 1991. 11. M. Rabbani, P. W. Jones, "Digital Image Compression Techniques", SPIE Press, 1991.
Witryna www przedmiotu:
http://www.ire.pw.edu.pl/~arturp/Dydaktyka/koda/download_koda.php
Uwagi:
Szczególny nacisk położony jest na analizę koderów danych obrazowych, modelowanie danych w przestrzeni obrazu, kontekstowe kodowanie binarne, a także na dobór efektywnych przekształceń w transformacyjnych metodach kodowania. Studenci poznają szczególnie efektywne rozwiązania koderów (np. CALIC, EZW, SPIHT,JPEG-LS), popularne standardy i formaty (ZIP, GIF, PNG, AAC, JPEG, JPEG2000, JBIG, MPEG-2, AVC), jak i nowe propozycje (JPEG_XR, AIC). Metody kompresji omawiane są na poziomie algorytmu, niekiedy kodu źródłowego w C/C++, szczegółów aplikacyjnych, kosztów czasowych i sprzętowych, użyteczności oraz możliwych modyfikacji. Szczególnie istotne jest omówienie kluczowych paradygmatów, porządkujących i systematyzujących najbardziej obiecujące koncepcje kodowania.

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt W1
Student, który zaliczył przedmiot potrafi syntetycznie scharakteryzować podstawy teorii kompresji danych, obejmujące zasadnicze elementy teorii informacji, teorii zniekształceń źródeł informacji oraz teorii aproksymacji
Weryfikacja: egzamin
Powiązane efekty kierunkowe: K_W04, K_W09, K_W11
Powiązane efekty obszarowe: T2A_W02, T2A_W03, T2A_W03, T2A_W04, T2A_W07
Efekt W2
zna podstawowe algorytmy kompresji danych, bezstratnej i z selekcja informacji, a także obowiązujące paradygmaty kompresji oraz metody kompresji wykorzystywane w standardach rodziny JPEG i MPEG
Weryfikacja: egzamin
Powiązane efekty kierunkowe: K_W04, K_W09
Powiązane efekty obszarowe: T2A_W02, T2A_W03

Profil ogólnoakademicki - umiejętności

Efekt U1
potrafi projektować i realizować algorytmy wybranych metod kompresji danych, dobierać parametry i formy implementacji metod znanych, a także realizować własne pomysły w zakresie kompresji danych
Weryfikacja: egzamin/zaliczenie projektu
Powiązane efekty kierunkowe: K_U01, K_U11, K_U13
Powiązane efekty obszarowe: T2A_U01, T2A_U16, T2A_U18
Efekt U2
potrafi wykorzystać potencjał metod kompresji w określonych zastosowaniach oraz dobrać metodę lub narzędzie kompresji do zastosowania wykorzystując znane cechy algorytmów oraz właściwości możliwych do wykorzystania modeli źródeł informacji
Weryfikacja: egzamin/zaliczenie projektu
Powiązane efekty kierunkowe: K_U01, K_U07, K_U09, K_U11
Powiązane efekty obszarowe: T2A_U01, T2A_U10, T2A_U11, T2A_U16
Efekt U3
potrafi ocenić skuteczność metod kompresji dobierając właściwą miarę, kryterium, zbiór testowy oraz procedurę testu weryfikacyjnego
Weryfikacja: egzamin/zaliczenie projektu
Powiązane efekty kierunkowe: K_U01, K_U08, K_U09, K_U10, K_U13
Powiązane efekty obszarowe: T2A_U01, T2A_U12, T2A_U11, T2A_U15, T2A_U18

Profil ogólnoakademicki - kompetencje społeczne

Efekt K1
potrafi sprawozdać rezultaty pracy własnej i zespołowej oraz konfrontować rezultaty pracy własnej i zespołowej ze specyfiką zastosowań
Weryfikacja: zaliczenie projektu
Powiązane efekty kierunkowe: K_K01
Powiązane efekty obszarowe: T2A_K06