Education
Register
Advertisement

Kompresja obrazów cyfrowych pozwala na zmniejszenie rozmiaru danych opisujących obraz. Zależnie od tego, czy po dekompresji możliwe jest odtworzenie idealnego obrazu źródłowego, czy też dane zostaną częściowo zmienione (przez usunięcie drobnych szczegółów lub dodanie artefaktycznych elementów) dzielimy metody kompresji na stratne i bezstratne. ;_

Kompresja bezstratna[]

Lossless compression to ogólna nazwa takich metod upakowywania informacji do postaci zawierającej zmniejszoną liczbę bitów tak, aby całą informację dało się z tej postaci odtworzyć do identycznej postaci pierwotnej. Najważniejszym twierdzeniem o kompresji bezstratnej jest Twierdzenie o zliczaniu (counting theorem), wg którego

Niemożliwe jest skonstruowanie funkcji przekształcającej odwracalnie informację na informację (czyli funkcji kompresji bezstratnej), która nie wydłuża jakieś informacji o przynajmniej 1 bit, chyba że nie kompresuje ona żadnej informacji.

Algorytmy kompresji bezstratnej dobrze kompresują "typowe" dane, czyli takie w których występuje znaczna nadmiarowość informacji (redundancja).

Pewne rodzaje danych są bardzo trudne lub niemożliwe do skompresowania:

  • strumienie liczb losowych (niemożliwe do skompresowania),
  • strumienie liczb pseudolosowych (w praktyce trudne, choć teoretycznie bardzo dobrze kompresowalne),
  • dane skompresowane za pomocą tego samego lub innego algorytmu (w praktyce trudne).

Najczęściej używane metody kompresji bezstratnej można podzielić na słownikowe i statystyczne, choć wiele metod lokuje się pośrodku:

  • metody słownikowe poszukują dokładnych wystąpień danego ciągu znaków, np. zastępują 'the ' krótszą ilością bitów niż jest potrzebna na zakodowanie 4 niezwiązanych znaków. Jednak znajomość symbolu 'the ' nie pociąga za sobą usprawnień w kompresowaniu 'they' czy 'then'.
  • metody statystyczne używają mniejszej ilości bitów dla częściej występujących symboli, w przypadku praktycznie wszystkich oprócz najprostszych metod, prawdopodobieństwa zależą od kontekstu. A więc np. dla 'h' występującego po 't' używają mniejszej ilości bitów niż dla innych znaków w tym kontekście.

Popularne metody to:

  • BZIP2
  • Kodowanie Huffmana
  • Kodowanie arytmetyczne
  • Move To Front
  • transformata Burrowsa-Wheelera

Popularne formaty

  • LZ77 (GIF)
  • LZW (GIF)
  • PCX
  • PNG
  • RLE
  • PPM
  • APE (dźwięk)

Kompresja stratna[]

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 wykonania, 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.

Popularne formaty kompresji stratnej obrazu:

  • JPEG
  • JPEG2000 (kompresja falkowa)

Popularne formaty kompresji stratnej wideo:

  • DivX
  • XviD
  • MPEG
  • Real Video

Popularne formaty kompresji stratnej dźwięku:

  • MP3
  • OGG Vorbis
  • Real Audio

JPEG[]

JPEG to nazwa systemu kompresji statycznych obrazów rastrowych, przeznaczonego głównie do przetwarzania obrazów naturalnych (zdjęć satelitarnych, pejzaży, portretów itp.), a więc takich, które nie mają zbyt wielu ostrych krawędzi i małych detali. Motywacją do powstania tego systemu była standaryzacja algorytmów kompresji obrazów monochromatycznych i kolorowych.

Prace nad standardem rozpoczęły się w roku 1986 z inicjatywy organizacji ISO oraz CCITT i były prowadzone przez zespół ekspertów nazywany Joint Photographic Experts Group. Standard został opublikowany po 5 latach, w 1991 roku. Definiuje on cztery tryby kompresji:

  • sekwencyjny, oparty na DCT (kompresja stratna)
  • progresywny, oparty na DCT (kompresja stratna)
  • sekwencyjny, bezstratny
  • hierarchiczny

Dwie pierwsze metody umożliwiają uzyskanie bardzo dużej kompresji obrazu, rzędu 20:1 kosztem pewnej utraty szczegółów, na ogół niezauważalnej.

Metoda 3., bezstratna, kompresuje ok. 2:1 i nie jest zbyt powszechnie stosowana.

Tryb hierarchiczny kompresuje coraz mniejsze, przeskalowane obrazy (można to sobie wyobrazić jako piramidę obrazów: na samym dole znajduje się największy obraz, wyżej 2 razy mniejszy, jeszcze wyżej 4 razy mniejszy itd.). Został pomyślany głównie po to, by móc szybko pobierać z obrazów b. wysokiej rozdzielczości mniejsze obrazy; tryb ten nie definiuje która z metod kompresji ma zostać użyta: może być stratna, albo bezstratna.

Standard opisujący sposób zapisu plików graficznych skompresowanych metodą JPEG nazywa się JFIF (JPEG File Interchange Format). Pliki JFIF - zwyczajowo nazywane JPEG (wym. "dżej-peg") i posiadające rozszerzenie "jpeg" albo "jpg" - obok formatów GIF i PNG, są najczęściej stosowanym formatem grafiki na stronach WWW.

Kompresja[]

Algorytm kompresji używany przez JPEG jest algorytmem stratnym, tzn. w czasie jego wykonywania tracona jest bezpowrotnie część pierwotnej informacji.

Algorytm przebiega następująco:

  • obraz jest konwertowany z kanałów czerwony-zielony-niebieski (RGB) na jasność (luminancję) i 2 kanały barwy (chrominancje). 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 (opcjonalnie można go pominąć).
  • wstępnie odrzucana jest część pikseli kanałów barwy, ponieważ ludzkie oko ma znacznie niższą rozdzielczość barwy niż rozdzielczość jasności. Można nie redukować wcale, redukować 2 do 1 lub 4 do 1.
  • kanały są dzielone na bloki 8x8. W przypadku kanałów kolorów, jest to 8x8 aktualnych danych, a więc zwykle 16x8.
  • na blokach wykonywana jest dyskretna transformacja kosinusowa (DCT). Zamiast wartości pixeli 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.
  • współczynniki DCT są uporządkowywane zygzakowato, aby zera leżały obok siebie.
  • współczynniki niezerowe są kompresowane algorytmem Huffmana. Są specjalne kody dla ciągów zer.

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

Wielką innowacją algorytmu JPEG była możliwość kontroli stopnia kompresji w jej trakcie, co umożliwia dobranie jego stopnia do danego obrazka, tak aby uzyskać jak najmniejszy plik, ale o zadowalającej jakości.

MPEG[]

MPEG (ang. Moving Picture Experts Group) - zatwierdzony przez ISO format zapisu danych zawierających obraz i dźwięk. Opracowany przez grupę niezależnych ekspertów format używany jest do zapisu filmów Video CD, DVD i transmisji telewizji cyfrowej (MPEG 2).

Grupa MPEG powstała w 1988 roku, jej celem było opracowanie standardu kodowania wideo wraz z dźwiękiem. Rozwój technologii wymógł konieczność opracowania sposobu kompresji ponieważ np. obraz PAL składa się 25 klatek na sekundę, 720 punktów w poziomie i 576 punktów w pionie, a kolor każdego z tych punktów opisany jest 24 bitami. Oznacza to, że każda sekunda nieskompresowanego obrazu w standardzie PAL na wielkość prawie 30 megabajtów. Jak łatwo wyliczyć półtoragodzinny film zajmie ponad 156 gigabajtów - zmieści się na 224 krążkach CD.

  • W 1991 roku opracowano oficjalną specyfikację standardu MPEG-1. Obraz ma w nim rozdzielczość 352x240 punktów i jest wyskalowany do odtwarzania pełnoekranowego, a przepustowość wynosi 1,5 Mb/s. Trzecia część standardu MPEG-1 dotyczy kodowania dźwięku i jest wykorzystywana w formacie MP3.
  • W roku 1994 pojawiła się specyfikacja standardu MPEG-2, w którym maksymalna rozdzielczość obrazu wynosi 1920x1152 punktów, a prędkość transferu waha się między 3 a 130 Mb/s.
  • MPEG-4 jest przystosowany głównie do kompresji danych strumieniowych (wideokonferencje), dlatego posiadał zaimplementowane funkcje ochronne przed błędami przesyłu. Ich usunięcie i lekkie przekompilowanie kodeka przez młodego Francuza Jerome Rota zaowocowało powstaniem kodeka DivX ;-). Od tej pory rozpoczął się dynamiczny rozwój tej gałęzi multimediów, oraz powstanie coraz bardziej wydajnych kodeków, takich jak XviD. Część 10 standardu MPEG-4 opisuje jeszcze wydajniejszy algorytm kompresji, nazwany AVC - Advanced Video Coding.
  • MPEG-7 to standard opisu danych multimedialnych. Umożliwia zapis informacji o cechach obrazu: kształtach, kolorach, teksturach. Na podstawie tych danych możliwe jest szybkie i trafne odnajdywanie obrazów podobnych do siebie.
  • MPEG-21 to przyszłościowy standard, mający na celu dalszą standardyzację treści multimedialnych.

Metody kompresji[]

W kodowaniu obrazu MPEG 1, 2 i 4 wykorzystywane są różne metody kompresji bazujące na analizie możliwości i ograniczeń ludzkiego zmysłu wzroku:

  • podpróbkowanie chrominancji. W obrazie cyfrowym kolor każdego punktu kodowany jest przy pomocy trzech 8-bitowych wartości. Informują one o nasyceniu punktu kolorami: czerwonym (red), zielonym (green) oraz niebieskim (blue)- standard RGB. W cyfrowym obrazie wideo do zdefiniowania koloru punktu używa się standardu YUV, w którym używane są parametry luminancji (jasności, oznaczenie Y) oraz chrominancji (unikatowy kolor, oznaczenie U i V). Aby zobaczyć obraz wideo należy przeprowadzić konwersję danych o kolorach ze standardu RGB na YUV. Jak wykazały badania, informacja kolorystyczna ma mniejsze znaczenie dla ludzkiego oka, dlatego stosuje się "podpróbkowanie" - na każde 2x2 punkty luminancji przypada zaledwie jeden punkt chrominancji U i jeden V.
  • kodowanie transformatowe. Obraz każdej klatki dzielony jest na bloki o wielkości 8x8 punktów, a następnie dokonuje się na takim bloku operacji matematycznej nazywanej Transformatą Kosinusową, która informację o wszystkich 64 punktach pozwala zapisać na zaledwie kilku liczbach bez zauważalnej straty jakości.
  • kompensacja ruchu. Często w filmach występują momenty, w których na ekranie ruszają się tylko postacie, a tło pozostaje niezmienione (np. sceny rozmowy). Zamiast podawania w każdej klatce informacji o każdym pikselu, podaje się dane o pikselach, które zmieniły swoje cechy. Dla każdego makrobloku (16x16 punktów) oblicza się wektor, wskazujący na miejsce w klatce odniesienia (najczęściej jest to poprzednia klatka filmu), które jest najbardziej podobne do kodowanego makrobloku. Do odbiornika przesyła się wartość wektora i różnicę względem "podobnego" makrobloku. Ta operacja pozwala na ogromną redukcję przesyłanych danych.
  • kodowanie Huffmana. Informacja o wektorach ruchu i współczynnikach DCT jest kodowana kodem Huffmana. Wartości bardzo prawdopodobne są reprezentowane przez krótsze ciągi zer i jedynek, a mało prawdopodobne - przez dłuższe.

MPEG-1[]

MPEG-1 jest standardem kompresji dźwięku i ruchomych obrazów zaproponowanym przez MPEG. Format wideo MPEG-1 używany jest na Video CD. Jakość obrazu przy zwykłej przepustowości VCD jest w przybliżeniu porównywalna do tej znanych z kaset VHS. MPEG-1 audio layer 3 jest pełną nazwą popularnego formatu, MP3.

MPEG-1 składa się z wielu "partii", kolejno:

  1. Synchronizacja oraz mieszanie wideo i audio.
  2. Kodek kompresji sygnałów wideo bez przeplotu.
  3. Kodek kompresji stratnej sygnałów audio. Standard definiuje trzy "warstwy", czy też poziomy złożoności kodowania audio MPEG.
  4. MP1 lub MPEG-1 Part 3 Layer 1 (MPEG-1 Audio Layer 1)
  5. MP2 lub MPEG-1 Part 3 Layer 2 (MPEG-1 Audio Layer 2)
  6. MP3 lub MPEG-1 Part 3 Layer 3 (MPEG-1 Audio Layer 3)
  7. Procedury dla testów zgodności.
  8. Oprogramowanie referencyjne.

Standard MPEG-1 zaprojektowano pierwotnie dla przepustowości danych 1.5Mbit/s i rozdzielczości 352x240. Późniejsze udoskonalenia zezwoliły na przepustowość do 4Mbit/s i lepszą jakość. Na dzień dzisiejszy, MPEG-1 jest najbardziej kompatybilnym formatem z całej rodziny MPEG; daje się go odtworzyć na praktycznie wszystkich komputerach i odtwarzaczach VCD/DVD.

Format posiada poważną wadę, mianowicie wspiera jedynie skanowanie progresywne obrazu (brak przeplotu), co stało się bezpośrednim powodem publikacji MPEG-2 w późniejszym czasie.

MPEG-2[]

MPEG-2 jest standardem kompresji dźwięku i ruchomych obrazów zaproponowanym przez MPEG. MPEG-2 definiuje strumień transportowy (transmisja audio i obrazu przez strumienie zawodne) i strumień programowy (strumienie niezawodne, np. nośniki DVD, SVCD). Istnieje wsparcie dla obrazu z przeplotem. Standard jest kompatybilny wstecz.

Obraz reprezentowany jest jako składowa luminancji i dwie składowe chrominancji (Cb i Cr). Dane zorganizowane sa w makrobloki, a w każdym z nich można wyróżnić 4 bloki 8x8 luminancji i zmienną ilość bloków 8x8 chrominancji zależnych od formatu obrazu. Przykładowo w formacie 4:2:0 znajduje się po jednym bloku 8x8 dla każdej ze składowych chrominancji, co daje 6 bloków na makroblok.

Transport obrazu w MPEG-2 definiuje trzy rodzaje ramek obrazu:

  • Intra frames
  • forward Predicted frames
  • Bidirectionally predicted frames

Ramki I są dekodowane wprost, podczas gdy ramki P i B podlegają estymacji ruchu. W sąsiednich klatkach (w przypadku P - poprzednej i obecnej, B - poprzedniej, obecnej i następnej) znajdowane są makrobloki, które sa do siebie najbardziej zbliżone. Zmiana ich położenia opisywana jest w postaci ruchu makrobloku opisywanego w ramkach P i B. Obraz po przesunieciu makrobloków różni się przeważnie w sposób niedostrzegalny od obrazu przed kompresją. Istnieje jednak metoda wprowadzenia dodatkowych (szczątkowych) informacji o modyfikacji obrazu.

Kompresja ramek I opiera się na przestrzennym nadmiarze (podoieństwa fragmentów jednej katki) a P i B na nadmiarze czasowym (mała zmienność obrazu w czasie). Wygenerowane makrobloki kompresowane są przy pomocy dyskretnej transformaty kosinusowej (DCT) podlegają kwantyzacji w celu uzyskania jak największej liczby następujących po sobie zer lub jedynek, kompresowane algorytmem RLE a następnie przy pomocy tablic Huffmana.

Grupa kolejnych zapisanych ramek zwana jest jako GOP (Group Of Pictures) i stanowi ciąg 15 ramek:

I_BB_P_BB_P_BB_P_BB_P_BB_

Stosowany jest też podobny ciąg 12 ramek. Statyczne sceny moga być silniej kodowane przy zastosowaniu większej liczby ramek B (np. IBBBPBBBPBBP) a dynamiczne z uszczupleniem liczby ramek P (np. IPPBPBPPPPPP).

Pizdencja

Advertisement