Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Kompresja danych
Koordynator przedmiotu:
Grzegorz Pastuszak
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. 2018/2019
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 wykładu jest omówienie podstaw teoretycznych oraz metod 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 doboru koderów optymalnych dla określonego rodzaju danych, a także sformułowanie współczesnych paradygmatów kompresji. Zarys użytecznych teorii obejmuje podstawy teorii informacji (modele, reguły kodowania i zniekształceń źródeł) oraz elementy analizy funkcjonalnej, teorii aproksymacji oraz przetwarzania sygnałów. Zagadnienia implementacji omawiane są na przykładzie kodów Huffmana oraz arytmetycznego. Szczególny nacisk położono na analizę kodeków danych obrazowych, modelowanie danych w przestrzeni obrazu, transformacje i kodowanie kontekstowe. Studenci poznają algorytmy m.in. CALIC, EZW, JPEG-LS, JPEG, JPEG2000, JPEG_XR, ZIP, PNG, JBIG, WebP, rodziny MPEG. Spodziewane efekty kształcenia to zdobycie syntetycznej i pragmatycznej wiedzy w zakresie nowoczesnych i użytecznych metod kompresji danych multimedialnych, umiejętność konstrukcji efektywnych algorytmów kompresji różnego przeznaczenia, optymalizacji metod bazujących na otwartych bibliotekach według kryteriów dopasowanych do charakteru zastosowań, a także projektowania i realizacji testów oceny efektywności technik kompresji odwracalnej i nieodwracalnej, z analizą wyników i formułowaniem wniosków.
Treści kształcenia:
Treść wykładu Wprowadzenie: przegląd i charakterystyka różnego typu danych wykorzystywanych do przekazu informacji, form ich reprezentowania (formaty, protokoły) 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, kierunki rozwoju nowoczesnych metod kompresji (2h). Podstawy teorii informacji: definicje informacji, pojęcia nadmiarowości, kanału przekazu informacji, modele źródeł informacji (m.in. źródła 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, WebP, 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 itp.) 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 itp.) 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, strumieniowania w systemach telemedycznych, itd.) i dostępnych narzędzi oraz 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:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103D-xxxxx-MSP-KODA; 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

Charakterystyka 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 charakterystyki kierunkowe: K_W04, K_W09, K_W11
Powiązane charakterystyki obszarowe: I.P7S_WG
Charakterystyka 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 charakterystyki kierunkowe: K_W04, K_W09
Powiązane charakterystyki obszarowe: I.P7S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka 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 charakterystyki kierunkowe: K_U01, K_U11, K_U13
Powiązane charakterystyki obszarowe: I.P7S_UK, I.P7S_UW, III.P7S_UW.3.o
Charakterystyka 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 charakterystyki kierunkowe: K_U01, K_U07, K_U09, K_U11
Powiązane charakterystyki obszarowe: I.P7S_UK, I.P7S_UW, III.P7S_UW.2.o, III.P7S_UW.1.o, III.P7S_UW.3.o
Charakterystyka 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 charakterystyki kierunkowe: K_U01, K_U08, K_U09, K_U10, K_U13
Powiązane charakterystyki obszarowe: I.P7S_UK, I.P7S_UW, III.P7S_UW.3.o, III.P7S_UW.1.o

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka 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 charakterystyki kierunkowe: K_K01
Powiązane charakterystyki obszarowe: I.P7S_KO