Multimedia
Dr hab. inż. Ewa Świercz
Multimedia
Dr hab. inż. Ewa Świercz
Kompresja danych multimedialnych
Co to jest kompresja?
W jakim celu dokonujemy kompresji danych?
Z czym związana jest kompresja – co zyskujemy a co
tracimy?
Jakie mechanizmy są podstawą algorytmów kompresji
danych?
Jakie algorytmy są wykorzystywane do kompresji
obrazu, dźwięku i wideo? Jak działają? Jakie są ich
wady i zalety? Gdzie znajdują zastosowanie?
Kompresja danych multimedialnych
Co zyskujemy a co tracimy?
Zmniejszenie zajmowanej powierzchni na nośniku lub
oszczędność przepustowości łącza. Szczególnie ważne przy
materiale wideo, zajmującym najwięcej zasobów spośród
wszystkich składników systemu multimedialnego.
Konieczność dekompresji przed końcowym wykorzystaniem, a
więc niezbędne jest poświęcenie czasu i części mocy
obliczeniowych maszyny
– co może stanowić problem,
zwłaszcza, jeżeli potrzebne jest odtwarzanie „w locie”.
Kompresja stratna i bezstratna. Czy możemy sobie
pozwolić na utratę części informacji? Jak bardzo będzie
to zauważalne? Jak wpłynie na przydatność
skompresowanego zbioru do naszych celów?
Dlaczego kompresja jest tak istotna?
Nieskompresowany obraz kolorowy w trybie „true color” – 24 bity na
piksel:
Nieskompresowana sekwencja wideo, 25 klatek/s, w jakości
telewizyjnej (PAL 704x576, po 12 bitów/piksel):
121 651 kbit/s (121,6 Mbit/s)
Dwugodzinny film PAL, 25 klatek/s, 12 bitów/piksel:
Blisko 120 GB!
wymiary
352x288 CIF
Common
Intermediate
Format
704x576 PAL
Phase
Alternating Line
1600x1200
BMP
Format plików
z grafiką
bitmapową
rozmiar
297 kB
1,16 MB
5,5 MB
Przykład obrazu w formacie BMP , wymiar 549X601, 967.29 kB
Dlaczego można cokolwiek skompresować?
Redundancja (nadmiarowość)
Informacje w danych powtarzają się, jest ich więcej, niż to absolutnie
konieczne
– np. w dowodzie osobistym jest zarówno PESEL jak i data
urodzenia, chociaż PESEL ją zawiera, w formularzach często należy
wpisać adres zameldowania i zamieszkania, chociaż mogą być takie
same, itd…
Różne sposoby reprezentacji
np.reprezentacja grafiki: rastrowa i wektorowa. Często można coś
krócej opisać za pomocą wzoru lub metody postępowania, niż
dosłownej listy. „Kwadrat o boku 500 i górnym-lewym wierzchołku w
punkcie (0,0) ” jest krótszym zapisem niż lista współrzędnych
wszystkich pikseli składających się na ten kwadrat.
Ograniczenia percepcji
wzrokowej
– nie jesteśmy w stanie dostrzec niektórych szczegółów,
więc nie zauważymy różnicy, jeżeli zostaną wycięte z obrazu.
słuchowej – nie jesteśmy w stanie usłyszeć niektórych częstotliwości
występujących w sygnale dźwiękowym, więc nie zauważymy, jeżeli
zostaną wycięte.
Czy każde dane można skompresować
?
Nie zawsze!!
Możliwe, że używając danej metody kompresji
dla specyficznego tekstu nie osiągniemy
żadnego zysku!
Kompresja danych multimedialnych
Podstaw teoretyczne
Podstawowe definicje:
Kompresja
– proces zmiany sposobu zapisu
informacji, mający na celu zmniejszenie zajmowanej
przez nie przestrzeni w nośniku (nośnik fizyczny,
kanał transmisyjny, itd…)
Koder
– implementacja algorytmu kodowania i
kompresji.
Dekoder
– implementacja algorytmu dekodowania i
dekompresji.
Kodek
– koder + dekoder, w kontekście multimediów
rozumiane jako kompletna implementacja kompresji i
dekompresji danych określonego formatu
.
Kompresja danych multimedialnych
Podstaw teoretyczne c.d.
Podstawowe definicje:
Symbol
– w kontekście kodowania: unikalny,
niepodzielny i jednoznacznie odróżnialny składnik
strumienia danych, niosący informację. Przykłady:
litera w tekście, bit w pliku binarnym.
Alfabet
– zbiór wszystkich symboli, z których może
być złożona wiadomość.
Kodowanie
– przyporządkowanie każdemu
symbolowi z alfabetu A unikalnego ciągu symboli z
alfabetu B.
Kompresja danych multimedialnych
Miary jakości algorytmu kompresji
Współczynnik kompresji:
Jest to stosunek liczby bitów po kompresji do liczby bitów przed
kompresją.
Bitrate
Średnia liczba bitów na symbol w skompresowanej wiadomości.
Czas kompresji i dekompresji
Średni czas wykonania operacji dla określonej porcji danych
(np. 1kB)
Zapotrzebowanie na dodatkowe zasoby-
np. dodatkową
pamięć na buforowanie danych.
Subiektywna ocena odbiorcy
– nie zawsze parametry
liczbowe algorytmu dobrze opisują postrzeganą jakość
zbioru wynikowego! Można wskazać obraz subiektywnie
„lepszy”, „wyraźniejszy” , „ostrzejszy”.
Kompresja bezstratna
Kompresja bezstratna wykorzystuje redundancję
(nadmiarowość) danych w strumieniu i pozwala
ograniczyć ich rozmiar bez jakiejkolwiek straty informacji.
Skompresowany zbiór danych po dekompresji jest w
100% zgodny z oryginałem- identyczność bitowa!
Algorytmy kompresji mogą być zatem wykorzystane do
dowolnego typu danych, także np. plików
wykonywalnych czy danych pomiarowych.
Kompresja bezstratna jest całkowicie odwracalna!
Kompresja bezstratna
Wydajność algorytmów kompresji bezstratnej zależy od
stopnia redundancji strumienia wejściowego – od ilości
nadmiarowych informacji w nim zawartych.
Strumień o wysokim stopniu redundancji danych:
AAAA
BBB
CCCCC
DD
AAAA
BBBBBBB
Strumień o niskim stopniu redundancji danych:
A
BB
C
D
A
B
C
B
C
A
DD
B
A
C
A
B
D
A
C
Kompresja bezstratna
Przykłady zbiorów danych o wysokim stopniu
redundancji:
Tekst w języku naturalnym
Zdjęcia
Sekwencje wideo, film
Mowa, muzyka
Takie zbiory dadzą się zwykle silnie skompresować!
Kompresja bezstratna
Przykłady zbiorów danych o niskiej redundancji:
Ciągi liczb pseudolosowych
Szum
Dane skompresowane innym algorytmem
bezstratnym
Takie zbiory nie dadzą się silnie skompresować!
Kompresja bezstratna
Klasy algorytmów kompresji bezstratnej:
Algorytmy proste
– nie dokonują analizy strumienia
wejściowego przed kompresją, wykorzystują podobieństwo
sąsiedztwa.
Algorytmy statystyczne
– przed kompresją cały strumień jest
buforowany i analizowany pod kątem częstości występowania
poszczególnych elementów, na podstawie wyników dobierana
jest odpowiednia strategia kompresji
Algorytmy słownikowe
– kompresja oparta jest na stworzeniu
słownika podciągów w strumieniu danych i zastąpieniu ich
krótszymi „numerami” swojej pozycji w słowniku.
Algorytmy proste
Najmniej wydajne, ale szybkie i łatwe w
implementacji, mają bardzo małe wymagania
pamięciowe – nie potrzebują bufora.
Przykłady algorytmów należących do grupy
algorytmów prostych:
ByteRun
RLE (Run Length Encoding)
Algorytm ByteRun
Operuje na pojedynczych bajtach (symbol ma reprezentację bajtową),
opiera się na eliminacji redundancji lokalnej. Zasada działania:
Grupa bajtów ze strumienia wejściowego może zostać
zakodowana na jeden z dwóch sposobów:
Sposób pierwszy: oznaczamy
n
następnych bajtów, które mają
zostać skopiowane bez zmian i umieszczamy tę liczbę wraz z
bajtami, których dotyczy w strumieniu wyjściowym, czyli:
A
B
C
D => 4
A
B
C
D
n musi się zawierać w przedziale <1, 127>
Sposób drugi: jeżeli znajdziemy powtarzające się, sąsiednie
symbole, zastępujemy je symbolem
K [ -n+1, A
x
], gdzie: n -
liczba powtórzeń, A
x
- powtarzany symbol,
czyli:
AAAA
=> -3
A
, ponieważ: - (-3) +1 = 4*
A
=
AAAA
n musi się zawierać w przedziale <1, 127>
Algorytm ByteRun
Przykład:
Strumień oryginalny
:
AAAA
BBB
C
D
A
BBBBBB
– 16 bajtów
Strumień skompresowany
:
-3
A
-2
B
3
C
D
A
-5
B
– 10 bajtów
Dekodowanie jest bardzo proste, sprawdzamy znak pierwszego
bajtu, rozpoznajemy rodzaj sekwencji, a później albo powielamy
albo kopiujemy określoną liczbę bajtów.
Wady:
w najbardziej pesymistycznym przypadku
– brak grup
powtarzających się symboli skompresowany strumień będzie
dłuższy niż strumień oryginalny!
Algorytm Run Length Encoding
Podobny do algorytmu ByteRun, ale zawiera
dodatkowe sekwencje sterujące.
Kopiowanie oznaczane jest symbolem [0, n, A
1
, A
2
, …, A
n
], gdzie
n -
liczba kolejnych bajtów do skopiowania bez zmian.
Przykład:
A
B
C
D
=> 04
A
B
C
D
Powielanie oznaczane jest symbolem [n, A] , gdzie n
– liczba
powtórzeń, A – powtarzany symbol
AAAA
=> 4
A
n może zawierać się w przedziale <1, 255> , zysk przy długich
sekwencjach w porównaniu do ByteRun
Algorytmy proste
– podsumowanie
Szybkie w działaniu, nie zajmujące zasobów,
umiarkowanie wydajne.
Wykorzystywane między innymi w formatach grafiki
PCX, wariantach formatu GIFF, Truevision TGA (format
grafiki rastrowej), PackBits, czy ILBM.
Mogą w niekorzystnych warunkach generować
strumienie dłuższe niż oryginalny.
Algorytmy statystyczne
Dokonują analizy strumienia wejściowego pod kątem
częstości występowania poszczególnych symboli i
przyporządkowują najczęściej występującym najkrótsze
słowa kodowe.
Jest to grupa algorytmów o zmiennej długości słowa
kodowego.
Zysk w kodowaniu statystycznym polega na tym, że
symbole występujące częściej niż średnia otrzymują
słowa kodowe krótsze niż średnia długość słowa
kodowego dla symbolu. Część symboli otrzymuje co
prawda słowa kodowe dłuższe niż średnia, ale ponieważ
występują rzadziej – całość strumienia jest krótsza!
Kodowanie Huffmana najczęściej wykorzystywany
statystyczny algorytm kompresji bezstratnej
Opracowany przez Davida Huffmana w Massachusetts
Institute of Technology, ogłoszony w 1952 roku, prosty,
efektywny jest jednym z najbardziej
rozpowszechnionych algorytmów kompresji bezstratnej.
Podstawą jego działania jest analiza statystyczna danej
wiadomości pod kątem częstotliwości występowania w
niej poszczególnych symboli. Każda wiadomość musi
być indywidualnie analizowana!
Stosowany także jako jeden z etapów wielu algorytmów
kompresji stratnej
– np. JPEG czy MP3.
Kodowanie Huffmana
Zasada działania:
Etap 1:
Analiza częstości występowania symboli (liter) w wiadomości
(tekście) i uszeregowanie ich od najrzadziej do najczęściej
występujących,
HELLO WORLD
L
– 3 wystąpienia
O
– 2 wystąpienia
H
– 1 wystąpienie
E
– 1 wystąpienie
W
– 1 wystąpienie
R
– 1 wystąpienie
D -
1 wystąpienie
Kolejność: L, O, H, E, W, R, D
Każdy tekst ma swój charakterystyczny rozkład częstości występowania znaków,
dlatego przy kodowaniu algorytmem Huffmana konieczna jest indywidualna
analiza każdej wiadomości!
Kodowanie Huffmana
Etap 2:
Budowa drzewa binarnego, w którym liśćmi będą litery pojawiające
się w tekście. Każdemu węzłowi przyporządkowywana jest waga – na
początku węzłami są występujące w tekście litery a ich wagami-
częstość ich wystąpienia. Drzewo budowane jest przez łączenie
dwóch węzłów o najmniejszych wagach w jeden węzeł- rodzic, i
przypisanie mu wagi będącej sumą jego potomków
.
R(1)
E(1)
W(1)
H(1)
O(2)
L(3)
(2)
D(1)
R(1)
(2)
D(1)
E(1)
W(1)
H(1)
Kodowanie Huffmana
O(2)
L(3)
R(1)
(2)
D(1)
H(1)
W(1)
(2)
E(1)
W(1)
(2)
E(1)
O(2)
L(3)
R(1)
(2)
D(1)
H(1)
Kodowanie Huffmana
W(1)
(2)
E(1)
O(2)
L(3)
R(1)
(2)
D(1)
(3)
H(1)
W(1)
(2)
E(1)
(3)
H(1)
O(2)
L(3)
R(1)
(2)
D(1)
Kodowanie Huffmana
W(1)
(2)
E(1)
(3)
H(1)
O(2)
L(3)
R(1)
(2)
D(1)
(4)
O(2)
R(1)
(2)
D(1)
(4)
W(1)
(2)
E(1)
(3)
H(1)
L(3)
Kodowanie Huffmana
Zbudowane drzewo Huffmana dla „Hello World”
O(2)
R(1)
(2)
D(1)
(4)
W(1)
(2)
E(1)
(3)
H(1)
L(3)
(6)
(10)
Kodowanie Huffmana
Etap 3:
Przypisanie gałęziom od rodzica do potomka cyfr 1 lub 0.
Gałąź lewa – 0, „idź w lewo”, gałąź prawa – 1, „idź w prawo”
Wtedy każda litera- liść może być jednoznacznie opisana
przez sekwencję zer i jedynek opisujących drogę od korzenia
do liścia.
A
B
(2)
(0)
C
0
1
0
1
Kod litery B: 01
Kod Huffmana - podsumowanie
Optymalny wśród kodów prefiksowych
Symbolom występującym najczęściej odpowiadają
najkrótsze słowa kodowe.
Kodowanie i dekodowanie w czasie liniowym
– więc
szybkie.
Konieczność przesłania informacji o drzewie znaków do
dekodera
– bez tego odczytanie jest niemożliwe.
Powszechnie stosowany jako samodzielny algorytm
kompresji bezstratnej, lub jako etap w bardziej
zaawansowanych metodach, stanowi element
standardów JPEG, MP3, gzip, arj.
Algorytmy słownikowe
Algorytmy słownikowe polegają na kolejnym czytaniu
danych wejściowych i przeglądaniu słownika w
poszukiwaniu dokładnie takiej samej sekwencji danych.
Słownik może być zadany lub budowany dynamicznie w
trakcie działania algorytmu.
Rodzina algorytmów o stałej długości słowa kodowego –
którym jest po prostu indeks pozycji danej grupy symboli
wejściowych w słowniku.
Efektywność algorytmów słownikowych dla danej
wiadomości zależy od częstości występowania w niej
takich samych grup symboli. Im dłuższa sekwencja w
słowniku, tym efektywniejsza kompresja.
Algorytmy słownikowe
Algorytm LZ77, opracowany przez pp. Jacoba Ziva i
Abrahama Lempela w 1977 roku. Podobnie jak
kodowanie Huffmana, jest wykorzystywany w szeregu
popularnych standardów kompresji, np. RAR, czy
formacie graficznym PNG.
W tej metodzie słownik budowany jest na bieżąco,
spośród pewnej liczby ostatnio przeanalizowanych
bajtów strumienia. Jeżeli jakaś grupa wystąpiła w
ostatnich n bajtach strumienia-
mamy ją w słowniku.
Słownik nie jest w tej metodzie stały!
Algorytm LZ77
Zasada działania:
Kompresor, czytając kolejne dane ze strumienia
sprawdza, czy nie natrafił ostatnio na podobny ciąg, a
jeżeli tak, to zamiast całego ciągu zapisuje tylko
długość powtórzonego ciągu i przesunięcie do tyłu.
Hej, 20 bajtów wcześniej widziałem taki sam ciąg o
długości 4 bajtów !
W praktycznych implementacjach śledzone „okno
słownikowe” jest dosyć duże – kilka, kilkanaście kB.
Algorytm LZ77
LZ77 - kodowanie
Przesuwanie okna wzdłuż czytanego strumienia danych
wejściowych.
Szukanie najdłuższego łańcucha danych w buforze „patrz w
przód”, który ma swój dokładny odpowiednik w słowniku.
Tworzenie sekwencji kodowej tego łańcucha (start, ile, następny
znak).
Przesuwanie okna o długość zakodowanej frazy.
Powtarzanie kroków 2, 3 i 4 aż do zakodowania ostatniego
symbolu z danych wejściowych.
Format słowa kodowego: [(o ile wstecz, jak długi ciąg)
następny znak]
Algorytm LZ77
Przykład:
Okno=(8-
słownik
,4-
Bufor „patrz w przód”
)
Wiadomość: ABRAKADABRA_CZARY_MARY
Tekst w oknie:
ABRAKADA
BRA_
CZARY_MARY
Zatem po zakodowaniu:
(0,0)A
(0,0)B
(0,0)R
(3,1)K
(2,1)D
(7,4)_
(0,0)C
(0,0)Z
(4,1)R
(0,0)Y
(6,1)M
(5,3)EOF
Inny przykład
Kodujemy ciąg zakładając długość słownika równą - 7.
długość bufora kodowania równą - 6
k a b r a k a d a b r a r r a r r a d
Zakładamy, że podciąg
k a b r a k a
jest już zakodowany
Dopasowanie musi
zaczynać się w buforze słownikowym a może kończyć się w
buforze kodowania
Dekodowanie algorytmu LZ77
Startujemy z odkodowanego podącigu
k a b r a k a
Odkodowujemy (0,0,C(d))
– czyli C(d)
Odkodowujemy (7,4,C(r)) tzn. przesuwamy o 7 i kopiujemy 4 kolejne
znaki słownika
Odkodowanie trójki liczb (3,5,C(d))
d
d
d
d
d
d
Algorytm LZ77
LZ77 -
efektywność
Zależy silnie od długości fraz w słowniku – im
dłuższe, tym lepsze.
Skuteczna do kompresji tekstu języka naturalnego,
fotografii (ze względu na często występujące,
jednolite kolorystycznie regiony)
Szybki obliczeniowo