Kodowanie transformatowe

Kodowanie transformatowe (inne nazwy: kodowanie transformacyjne, kodowanie transformujące) – algorytm kompresji stratnej sygnałów cyfrowych (obrazu, dźwięku, video).

Zasada działania

Podstawowa idea polega na przekształceniu danych z reprezentacji oryginalnej (opisującej wartości próbek w dziedzinie czasu lub przestrzeni) do innej dziedziny przy pomocy transformacji liniowej (na przykład transformacji kosinusowej), gdzie następuje właściwe kodowanie. Dane w tej nowej dziedzinie reprezentowane są przez współczynniki transformaty, które charakteryzuje koncentracja energii (największa część sygnału zawarta jest w niewielkiej liczbie współczynników, pozostałe współczynniki mają niewielkie wartości lub wręcz są równe zero). Tą dziedziną jest najczęściej dziedzina częstotliwości reprezentowana przez wektory próbek funkcji sinusoidalnych lub kosinusoidalnych, lecz może być nią również dziedzina oparta na innym zbiorze dyskretnych wektorów ortogonalnych, zarówno uniwersalnych (np. transformacja falkowa, która wykorzystuje funkcje falkowe) jak i adaptacyjnie dobranych do sygnału (np. transformacja Karhunena-Loève, która wykorzystuje wektory własne macierzy autokowariancji sygnału).

Sama transformacja nie zmniejsza ilości danych, choć w pewnych warunkach redukuje ich korelację oraz entropię. Właściwa kompresja stratna odbywa się poprzez kwantowanie współczynników, które zmniejsza liczbę bitów potrzebną na ich reprezentację oraz opcjonalne kodowanie entropijne (np. kodowanie Huffmana), które w bezstratny sposób reprezentuje poszczególne skwantowane współczynniki ciągami binarnymi o zmiennej długości (im częściej występująca wartość tym krótsza sekwencja bitów).

Większość popularnych transformacji oferuje największą wydajność kodowania, gdy sygnał jest stacjonarny, ponieważ baza funkcji ortogonalnych składa się z funkcji o charakterze stacjonarnym (np. DCT oparta jest na funkcjach kosinusowych o stałej częstotliwości). Z kolei sygnały poddawane kompresji (mowa, muzyka, obraz) są najczęściej niestacjonarne. Zastosowanie pojedynczej transformacji dla wszystkich próbek sygnału jest również bardzo złożone obliczeniowo. Dlatego popularnym rozwiązaniem jest podział sygnału na krótkie segmenty lub bloki i zastosowanie transformacji dla każdego bloku z osobna (np. w obrazie stosuje się bloki o wymiarach 8x8 pikseli, ale także 4x4 i 16x16, w dźwięku stosuje się bloki 1152 lub 2048 próbek). Jednak niezależne kodowanie każdego bloku może powodować powstanie dokuczliwego efektu blokowego, co szczególnie przy danych audio jest nieakceptowalne i wymusza stosowanie algorytmów typu MDCT.

Dekodowanie

Dekodowanie polega na odtworzeniu wartości skwantowanych współczynników transformaty (potocznie, acz nieprawidłowo, nazywane dekwantyzacją), a następnie wykonaniu transformacji odwrotnej, która rekonstruuje sygnał w jego początkowej dziedzinie. Tak zrekonstruowany sygnał jest niestety zniekształcony w stosunku do oryginalnego.

Zniekształcenia

Zniekształcenia wynikające z kodowania transformatowego są tym silniejsze, im silniej skwantowane były współczynniki (a więc im silniejsza kompresja), przy czym zniekształcenie ma charakter zależny od właściwości zastosowanej transformacji oraz właściwości samego sygnału. Najczęstszymi zniekształceniami są

• utrata wysokich częstotliwości (rozmycie krawędzi i utrata szczegółów w obrazie, utrata wysokich tonów w dźwięku)
• efekt blokowy (niedopasowanie fragmentów sygnału na granicy sąsiednich bloków)

Zastosowania

Popularnymi zastosowaniami kodowania transformatowego są techniki kompresji

• JPEG
• MPEG-1
• MPEG-2
• MPEG-4

Zobacz też

• Kompresja falkowa
• Kompresja fraktalna

Bibliografia

• Marek Domański, "Zaawansowane techniki kompresji obrazów i sekwencji wizyjnych", Wydawnictwo Politechniki Poznańskiej, Poznań, 2000, ISBN 83-7143-030-2
• Khalid Sayood, "Kompresja danych", Wydawnictwo RM, Warszawa, 2002, ISBN 83-7243-094-2
• N. S. Jayant, Peter Noll, "Digital Coding of Waveforms: Principles and Applications to Speech and Video", Prentice Hall Professional Technical Reference, 1990, ISBN 0-13-211913-7
• K.R. Rao, P.C.Yip (red.), "The transform and data compression handbook", CRC Press, 2001, ISBN 0-8493-3692-9
• V.K. Goyal, Theoretical foundations of transform coding, IEEE Signal Processing Magazine, Volume 18, Issue 5, Sep 2001, ss. 9 – 21
• Jelena Kovacevic, Martin Vetterli, Transform coding: past, present and future, IEEE Signal Processing Magazine, vol. 18, num. 5, 2001, s. 6

Linki zewnętrzne

• Przetwarzanie sygnałów cyfrowych. dsp.agh.edu.pl. [zarchiwizowane z tego adresu (2016-08-19)]. (materiały dydaktyczne AGH)