Kompresja stratna

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

Kompresja stratna to metody zmniejszania ilości bitów potrzebnych do wyrażenia danej informacji, które nie dają gwarancji, że odtworzona informacja będzie identyczna z oryginałem. Dla niektórych danych algorytm kompresji stratnej może odtworzyć informację w sposób identyczny.

Kompresja stratna jest możliwa ze względu na sposób działania ludzkich zmysłów, tj. wyższą wartość pewnych części danych nad innymi. Algorytmy kompresji stratnej zazwyczaj posługują się modelami psychoakustycznymi, psychowizualnymi itd., aby odrzucić najmniej istotne dane o dźwięku, obrazie, pozostawiając dane o wyższej wartości dla rozpoznawania tej informacji (akustycznej, wizualnej) przez zmysły. Ilość odrzucanych danych jest zazwyczaj określana przez stopień kompresji.

Z tego też względu nie istnieją algorytmy kompresji stratnej, które można stosować do dowolnego typu danych. Np. kompresja stratna plików wykonywalnych byłaby praktycznie niemożliwa do zastosowania, gdyż nie jest to informacja odczytywana przez zmysły, a przez maszynę.

Zwykle kompresję stratną stosuje się do:

obrazków
dźwięków
ruchomych obrazów, np. w filmie

Przy danych audiowizualnych zazwyczaj kompresuje się osobno dźwięk, a osobno obraz.

Prostym przykładem kompresji stratnej jest np. zachowanie tylko co drugiego piksela, lub odrzucenie 2 najmniej istotnych bitów. Takie metody jednak nie dają zazwyczaj tak zadowalających rezultatów jak oparte na modelach psychozmysłowych.

Najpopularniejsze algorytmy kompresji

Obraz

JPEG, podstawa algorytmu MPEG, oparty na DCT i dający relatywnie słabe rezultaty.
JPEG2000, oparty na falkach, dający znacznie lepsze wyniki

Video

DivX/XviD, przy odpowiednich warunkach może skompresować zawartość płyty DVD na zwykłą CD, bez widocznych różnic.
MPEG, jedną z jego odmian stosuje się przy filmach na DVD, bardzo wysoka jakość, połączona z większymi objętościowo plikami (100mb DivX = ok.350mb MPEG).
Real Video, niską jakość obrazu rekompensuje mała objętość dzięki czemu wykorzystywany jest przy transmisjach na żywo.

Dźwięk

MP3, najpopularniejsze kodowanie stratne audio, oparte na MDCT, stosuje model psychoakustyczny Instytutu Fraunhoffera i firmy Tomphson.
Ogg Vorbis, oparte na MDCT
Real Audio, podobnie jak Real Video, rekompensuje straty jakości małą objętością, jest stosowany głównie do transmisji na żywo.

Kompresja obrazków

JPEG

Najbardziej powszechnym algorytmem kompresji obrazów jest JPEG. Wiele rozwiązań użytych w JPEG jest używanych także w innych algorytmach, więc warto je tutaj omówić. Kolejne kroki algorytmu JPEG to:

zamiana przestrzeni kolorów z RGB na kanał jasności i dwa kanały koloru. Ludzie znacznie dokładniej postrzegają drobne różnice jasności od drobnych różnic barwy, a więc użyteczne jest tutaj użycie różnych parametrów kompresji. Krok nie jest obowiązkowy.
obniżenie rozdzielczości kanałów koloru, zwykle odrzuca się co drugą wartość wzdłuż osi poziomej i każdą na pionowej, choć możliwe są też inne ustawienia. Tak radykalne cięcie danych nieznacznie wpływa na jakość, ponieważ rozdzielczość postrzegania kolorów przez ludzkie oko jest słaba. Krok nie jest obowiązkowy.
podzielenie każdego kanału obrazka na bloki 8x8. W przypadku kanałów kolorów, jest to 8x8 aktualnych danych, a więc zwykle 16x8.
transformata kosinusowa każdego z bloków. Zamiast wartości pikseli mamy teraz średnią wartość wewnątrz bloku oraz częstotliwości zmian wewnątrz bloku, obie wyrażone przez liczby zmiennoprzecinkowe. Transformata DCT jest odwracalna, więc na razie nie tracimy żadnych danych.
Zastąpienie średnich wartości bloków przez różnice wobec wartości poprzedniej. Poprawia to w pewnym stopniu współczynnik kompresji.
Kwantyzacja, czyli zastąpienie danych zmiennoprzecinkowych przez liczby całkowite. To właśnie tutaj występują straty danych. Zależnie od parametrów kompresora, odrzuca się mniej lub więcej danych. Zasadniczo większa dokładność jest stosowana do danych dotyczących niskich częstotliwości niż wysokich kodowanych algorytmem Huffmana.

Użyta transformata powoduje efekty blokowe w przypadku mocno skompresowanych obrazków.

Inne metody

Inne algorytmy kompresji obrazków opierają się głównie na:

użyciu innej transformaty
- zmodyfikowanej transformaty kosinusowej, która nie powoduje efektu bloków, a więc jest korzystniejsza w przypadku mocno skompresowanych obrazków. Nie odbiega ona wynikami znacząco od DCT w przypadku obrazów o średniej i niskiej kompresji.
- transformat falkowych - mogą one dać znacznie lepsze wyniki. Zazwyczaj nie powodują efektu bloków.
użyciu innego algorytmu kompresji bezstratnej
kompresja wszystkich kanałów naraz, w szczególności ich wspólna kwantyzacja. Daje lepsze wyniki jeśli wartości w różnych kanałach są mocno skorelowane.

Kompresja fraktalna

Zupełnie inną metodą jest kompresja fraktalna. Opisuje ona obraz w postaci parametrów funkcji fraktalnej, która daje w efekcie przybliżoną postać obrazu. Dotychczas kompresja fraktalna daje znacznie słabszą jakość w przypadku obrazów o niskim i średnim stopniu kompresji. Dla obrazów silnie skompresowanych może dawać lepsze rezultaty niż JPEG, przede wszystkim nie powoduje efektu bloków, jednak są one słabsze od znacznie prostszych metod opartych na MDCT czy falkach. Nic nie wskazuje na to, że kompresja fraktalna znajdzie szersze zastosowanie.

Kompresja ruchomych obrazów

Najprostsze systemy kompresji ruchomych obrazów po prostu kompresują wszystkie klatki osobno. Jest to bardzo nieefektywne, ponieważ kolejne klatki są zazwyczaj do siebie bardzo podobne.

Zazwyczaj używa się zestawu klatek kluczowych, które kompresuje się tak samo jak samodzielne obrazki. Pozostałe klatki kompresuje się natomiast korzystając z danych z klatek poprzednich. Lepsze wyniki dałoby wykorzystanie danych o poprzednich klatkach przy kompresji każdej klatki, jednak utrudniało by to znacznie przewijanie.

Prostym sposobem wykorzystania danych o poprzednich klatkach jest kodowanie różnicy wartości pikseli o tym samym położeniu zamiast samych wartości. Tym sposobem można dobrze skompresować sceny w których kamera jest nieruchoma, jednak nie da to znaczących efektów w scenach z ruchomą kamerą. Zwykle wykorzystuje się więc różne rodzaje kompensacji ruchu. Np. dla każdego bloku podaje się który niewielki wektor przesunięcia, np. <+2,-1>, czyli zamiast tego samego bloku klatki poprzedniej używamy bloku o 2 piksele w prawo i jeden w górę (czy też w lewo i w dół).

Inną ważną techniką wykorzystywaną przy kompresji ruchomych obrazów jest zmienna przepływność (variable bitrate), czyli używanie różnej dokładności dla różnych klatek. Jest wiele sposobów dobierania takich różnic, algorytmy wyboru jakości zwykle są cechą bardziej enkodera niż formatu. Często enkodery stosują metody dwu-przejazdowe, pierwszy przejazd po danych zbiera informacje potrzebne algorytmowi zmiennej przepływności, a dopiero drugi kompresuje dane.

Ruchome obrazy są zazwyczaj mocno skompresowane, a więc dla kodeka MPEG, który używa podobnie jak JPEG transformaty kosinusowej, efekty blokowe mogą być bardzo uciążliwe.

Kompresja dźwięku

Dwa najpopularniejsze publicznie dostępne algorytmy - MP3 i Vorbis, używają podobnych technik. Warto tu omówić algorytm Vorbis, ponieważ używa on bardziej efektywnych rozwiązań.

Strumień jest dzielony na okna. Okna występują w dwóch rozmiarach - duże (zwykle 2048 próbek) i małe (zwykle 256 próbek). Małe służą do przedstawienia szybko zmieniającego się dźwięku oraz nagłego wzrostu intensywności dźwięku w danej częstotliwości. Nie używa się ich w przypadku spadków intensywności, ponieważ ludzkie ucho jest na nie znacznie mniej czułe. Okna nie są po prostu grupą kolejnych wartości natężenia dźwięku. Okna częściowo się nakrywają i jedna wartość należy w tych obszarach częściowo do kilku okien. Dla obszarów zachodzenia na siebie okien, dana wartość należy do lewego okna w stopniu sin(pi/2 × sin²(pi/2 × t)), gdzie t=0 dla początku obszaru i t=1 dla jego końca.
Na każdym oknie jest przeprowadzana zmodyfikowana transformata kosinusowa. Zamiast poszczególnych wartości mamy teraz w bloku widmo parametrów MDCT czyli (pomijając szczegóły) częstotliwości.
Dane z MDCT są upraszczane zależnie od parametrów kompresji zgodnie z modelem psychoakustycznym.
Dane o energii przypadającej na daną częstotliwość są skalowane, co umożliwia równie dobrą kompresje głośnych jak i cichych dźwięków.
Dane są kwantyfikowane i kompresowane bezstratnie.