| Discrete
Cosinus Transformation - DCT |
Sada ćemo se malo pozabaviti konkretnim stvarima
kod SVCD kodiranja, tj. kada, kako, zašto i zbog čega se to radi. Pokušat
ću to objasniti, na najjednostavnije moguće način. Ako vam šta ne bude jasno,
pročitajte opet i opet, te na kraju potražite savjet na mreži ili kod psihijatra...
:)) Ako niste već zdimili, vrime vam je....
Zamislite da se slika na ljevoj strani (sive vrijednosti kodirane vrijednostima
od 0 do 255) multuplicira sa matricom, koja
izgleda kao slika na desnoj strani (sa vrijednostima od -1 do +1)
Iz
toga "mješanja" proizlazi jako smješna slika, koja za ljudsko
oko nema nikakvo značenje ispočetka! Prije svega upada u oči, da nova
slika, gore ljevo, ima visoke vrijednosti (crveno), a u ostalom djelu
slike manje-više ima niske vrijednosti (plavo).
Šale
radi, isječemo desno dolje jedan kvadrat ...
te
ga mutipliciramo sa slikom i vidimo.......
kao
rezultat prvobitni motiv. Pitanje glasi :
Kolika može biti plava kocka koju smo isjekli, a da se motiv još uvijek
prepoznaje ??
Time se bavi DCT.
korištenoi algoritam u kompresiji
Prije nego se izvrši DCT, podaci se
moraju još malo preraditi. Jer samo 8x8 pixela liki blokovi se mogu obraditi,
orginalna slika se mora, ako se ne može točno podijeliti u blokove 8x8,
povećati na desnoj, odnosno donjoj strani. Pri tome se nadodaju pixeli,
desno ili dolje, dok rezolucija ne bude djeljiva sa 8. Tek tada može početi
prava kompresija.
Diskrete
Cosinus Transformation
Kao prvo, blok se pretvara u 8x8 koeficijentnu matricu. DCT je jako sličan
jednoj drugoj matematičkoj funkciji - Fourier-transformaciji (FFT). Obe
transformacije služe, prevođenju signala. Kao primjer, možemo audiosignal,
pomoću FFT-a razdvojiti u brojne, različite, osnovne frekvencije.
Slika 1 pokazuje prekrivanje tri
sinusna vala.Nakon transformacije pomoću FFT-a se ova komplicirana valna
forma prikazuje samo kroz tri točke (Slika 2), X-os je pri tome frekvencija,
a Y-os amplituda frekvencije.  Slika
1
 Slika 2
DCT
funkcionira slično, samo što on radi sa trodimenzionalnim signalom. X-
i Y-osi su pri tome koordinate na motitoru/TV-u, a Z-os daje vrijednost
određenog piksela. Tako se prostorne informacije transformiraju u frekventne
informacije.
Transformacija
se vrši sljedećom formulom:
Slika 3
Prva
formula vrši transformaciju podataka iz slike u DCT-matricu, a druga ponovno
transformiranje DCT-vrijednosti u sliku.
I i J
su pri tome offset unutar DCT-matrice, x
i y su offset unutar bloka slike.
N je korištena veličina bloka (u
našem slučaju, 8).
Dodatak: moguće je koristiti i veće blokove npr. 16x16. To bi omogućilo
jače kompresije, ali bi se procesorsko vrijeme obrade enormno povećalo,
a i kvalitet kompresirane slike rapidno opada. Tako da se sa velikim
blokovima (64 x 64, 256 x 256, ...) ne bi dobila nikakva prednost.
Samo
kroz ovu transformaciju se nije dobila nikakva kompresija, nasuprot: iz
8-bitnih sivih vrijednosti (0 - 256) mogu nastati vrijednosti između -1024
i 1024. Čisti DCT je u principu, do malih grečkica pri zaobljavanju, kompresija
bez gubitaka.
Kvantizacija
koeficijenata
Ako pogledamo nastalu 8x8 matricu, vidimo da su u gornjem ljevom kutu zastupljene
visoke vrijednosti, takozvani DC-Koeficijent. Tek u pravcu desno
dolje nastaju niskofrekventni AC-Koeficijent i nakon njega visokofrekventni.
Jer ljudsko oko slabije prepoznaje visokofrekventne dijelove (visokofrekventno
- više informacija), ovi dijelovi se mogu izostaviti u korist manje datoteke,
bez da oko to prepozna.
Nakon
toga se svi koeficijenti dijele sa određenim faktorom i zaokružuju na
integralnu vrijednost. (pri povratnoj transformaciji - čitaj reprodukciji
- ovi se koeficijenti množe.)
Moguća
matrica kvantizacije :
Vrijednost
na svakoj poziciji se izračunava:
Kvantizacija[ x ] [ y ] = 1 + ( ( 1 + x + y ) * Kvalitet
)
Moguće
je koristiti i druge matrice, mada mi se čini da je se ova dokazala u
dosta testova.
Kodiranje
koeficijenata
Pogledajmo tipičnu DCT-matricu, nakon kvantizacije:
Vidljivo je, da je zbog kvantizacije
veliki dio dobio vrijednost 0, naročito dolje desno.
Da bi se podaci dobili u prihvatljivoj formi za kompresiju, snimaju se
"hopa-hala" metodom.
Time se najprije snimaji niskofrekventne
vrijednosti, a tek nakon njih visokofrekventne (koje su postale nule -
nadamo se).
Kompresija podataka
Nastalu koeficijentnu matricu
moramo snimiti, u moguće boljem formatu. Zbog toga se, pored ostaloga, koriste
Variable Length Integers - VLI (integri varijabilne duljine). Ovdje
se brojevi ne snimaju na osnovi duljine bitova, već se snimaju mali brojevi
- malom duljinom bitova, a veći - većom. To bi ovako izgledalo:
| Bitovi |
Broj
bitova (određena duljina, u našem slučaju 4 bita, je dovoljno za
brojeve do 15 bitova duljine |
| Predznak |
1
ako je broj < 0, inače 0 |
| Kod |
Oznaka
broja |
Primjeri :
| Decimalni
broj |
VLI |
8-bitni
binarni broj |
| 0 |
000. |
00000000 |
| -1 |
001.1 |
11111111 |
| 4 |
011.0.00 |
00000010 |
| -21 |
101.1.0101 |
11101011 |
| 124 |
111.0.111100 |
01111100 |
Kompletan 8x8 blok se snima u sljedećem formatu: najprije se snima DC-Koeficijent
kao VLI, nakon toga se ponavlja: 4 Bita, koji označavaju broj nula prije
sljedeće ne-nula vrijednosti i onda ne-nula vrijednost kao VLI.
Poseban slučaj je ako je broj nula = 15, što znači da se do kraja bloka
nalaze same nule.
Dekompresija
Dekompreija se izvršava obrnutim redosljedom:
- učitavanje
kvantizirane DCT-matrice
- množenje
kvantizirane matrice sa faktorom kvantizacije
- izvršiti
obrnuti DCT (iDCT)
|
