To delo je na voljo pod pogoji slovenske licence Creative Commons 2.5:

priznanje avtorstva - nekomercialno - deljenje pod enakimi pogoji.

Celotna licenca je na voljo na spletu na naslovu http://creativecommons.org/licenses/by-nc-sa/2.5/si/. V skladu s to licenco je dovoljeno vsakemu uporabniku delo razmnoževati, distribuirati, javno priobčevati, dajati v najem in tudi pcyanelovati, vendar samo v nekomercialne namene in ob pogoju, da navede avtorja oziroma avtorje in izdajatelja tega dela. Če uporabnik delo pcyanela, kar pomeni, da ga spremeni, preoblikuje, prevede ali uporabi to delo v svojem delu, lahko predelavo dela ponudi na voljo le pod pogoji, ki so enaki pogojem iz te licence oziroma pod enako licenco.

Matríka je v matematiki pravokotna razpredelnica števil, ki jo zapišemo med oglate oklepaje. Elementi matrike so realna ali kompleksna števila. Vodoravne črte v matriki so vrstice, navpične pa stolpci. Matrika z $m$ vrsticami in $n$ stolpci se imenuje $m \times n$ matrika, pri čemer sta $m$ in $n$ njeni razsežnosti.

Oglejmo si spodnji primer, kjer je pravokotna razpredelnica predstavljena oziroma zapisana tudi kot 4×3 matrika $A$:

$$ A = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 2 & 7 \\ 4 & 9 & 2 \\ 6 & 1 & 5 \end{bmatrix} $$

Element $A[2,3]$ ali $a_{2,3}$ je $7$.

Postopek stiskanja slikovnih datotek z metodo JPEG poteka v naslednjih korakih:

Korak 1: Pretvorba iz barvnega prostora RGB v YCbCr

Za pretvarjanje iz RGB v YCbCr barvni prostor izračunamo vrednosti svetlosti in barvitosti za vsak RGB piksel.

Y  =   0 + (0,2990 × R) + (0,5870 × G) + (0,1140 × B)
Cb = 128 - (0,1687 × R) - (0,3313 × G) + (0,5000 × B)
Cr = 128 + (0,5000 × R) - (0,4187 × G) - (0,0813 × B)

Korak 2: Zmanjšanje vzorčenja

Ker barvitost ni zelo pomembna, lahko zmanjšamo količino barve (komponent Cb in Cr). V splošnem je barvitost zmanjšana za faktor 2 v obeh smereh (navpično in vodoravno) – to pomeni, da je Y vzorčen pri vsakem pikslu, pri čemer se vzorci Cb in Cr vzorčijo pri vsakem bloku 2×2 pikslov. Torej za vsake 4 Y piksle obstaja samo 1 CbCr piksel.

Korak 3: Uporaba diskretne kosinusne transformacije (DCT)

Vsaka izmed treh komponent YCbCr je stisnjena in kodirana na enak način, ki je opisan v nadaljevanju. Oglejmo si postopek za eno komponento (za preostali je postopek identičen).

Osnovne slike

DCT je metoda, ki izraža končno zaporedje podatkovnih točk v obliki vsote kosinusnih funkcij, različnih frekvenc in amplitud.

Pri stiskanju namesto sinusnih funkcij sinus raje uporabljamo kosinusne funkcije, zaradi njihovega obnašanja ob mejah. Funkcija, kot je na primer svetlost slike, ob mejah ne sme zavzeti vrednosti nič, kot jo zavzame sinusna funkcija. Zato je težko ustvarjati približke signala z linearno kombinacijo sinusnih funkcij.

Iz kosinusnih funkcij različnih frekvenc po oseh X in Y lahko ustvarimo 64 različnih osnovnih slik, ki so prikazane spodaj:

Bloki

Celotno sliko, ki jo želmo stisniti, razdelimo na bloke velikosti 8×8 pikslov. Te bloke si lahko predstavljamo kot matrike velikosti 8×8. Celotno sliko stiskamo tako, da zaporedno stiskamo posamezne bloke.

Oglejmo si primer. Recimo, da imamo naslednji blok 8×8 pikslov (slika na desni). Vrednosti komponente, ki jo trenutno opazujemo, so podane v matriki oziroma tabeli:

  

Ker bomo uporabili metodo DCT in ker lahko kosinusna funkcija zavzame vrednosti med 1 in -1, bomo skušali vrednosti premakniti tako, da jih bo večina okoli ničle. To pomeni, da bomo premaknili obseg vrednosti iz [0..255] v [-128..127]. Zato bomo od vsake vrednosti odšteli 128. Vrednosti komponente bodo premaknjene takole:

Sedaj imamo dve stvari: blok velikosti 8×8, ki ga želimo stisniti in 64 osnovnih slik. Naša naloga je, da preoblikujemo blok v linearno zaporedje teh 64 osnovnih slik.

Blok lahko pretvorimo v linearno zaporedje z uporabo normalizirane, dvo-dimenzionalne diskretne kosinusne transformacije (DCT) tipa II.

Lahko si zamislimo, da je blok sestavljen iz utežene množice teh 64 osnovnih slik, ki so združene ena nad drugo. Zato velja: $$blok = C_{1} \times f_{1} + C_{2} \times f_{2} + C_{3} \times f_{3} + \dots + C_{64} \times f_{64}$$ kjer so $C_{i}$ neke konstante, $f_{i}$ pa so osnovne slike.

Vsakega od teh koeficientov ($C_{i}$) lahko izračunamo s pomočjo DCT tipa II. Več o tem, kako deluje metoda DCT, si lahko prebereš tukaj.

S pomočjo spodnje kode, v programskem jeziku Python, izračunamo matriko bloka, spremenjeno z metodo DCT tipa II:

import numpy  # Uvozimo knjižnico numpy
import scipy  # Uvozimo knjižnico scipy

# Definirajmo funkcijo: 2D DCT tipa II
def dct2D(x):
  tmp = scipy.fftpack.dct(x, type=2 ,norm='ortho').transpose()
  return scipy.fftpack.dct(tmp, type=2 ,norm='ortho').transpose()

# Premaknjen blok v obsegu [-128..127]
print(dct2D([
  [-76.0, -73.0, -67.0, -62.0, -58.0, -67.0, -64.0, -55.0],
  [-65.0, -69.0, -73.0, -38.0, -19.0, -43.0, -59.0, -56.0],
  [-66.0, -69.0, -60.0, -15.0, 16.0, -24.0, -62.0, -55.0],
  [-65.0, -70.0, -57.0, -6.0, 26.0, -22.0, -58.0, -59.0],
  [-61.0, -67.0, -60.0, -24.0, -2.0, -40.0, -60.0, -58.0],
  [-49.0, -63.0, -68.0, -58.0, -51.0, -60.0, -70.0, -53.0],
  [-43.0, -57.0, -64.0, -69.0, -73.0, -67.0, -63.0, -45.0],
  [-41.0, -49.0, -59.0, -60.0, -63.0, -52.0, -50.0, -34.0]
]))

Koda uporablja knjižnici NumPy in SciPy. Knjižnici običajno nista nameščeni in ju je potrebno namestiti posebej. To storiš tako, da zaženeš Python v terminalu ter nato uporabiš ukaz pip za nameščanje Pythonovih knjižnic:

> pip install numpy
> pip install scipy

Knjižnica SciPy vsebuje funkcijo scipy.fftpack.dct, s katero izračunamo DCT eno-dimenzionalne matrike. DCT dvo-dimenzionalne matrike izračunamo tako, funkcijo najprej izvedemo po stolpcih, stolpce transponiramo, nato funkcijo izvedemo po vrsticah in razvejavimo transpozicijo.

Ko izvedemo metodo DCT tipa II, dobimo matriko oziroma tabelo velikosti 8×8, ki vsebuje koeficiente. Ti koeficienti predstavljajo delež vsake od osnovnih slik v bloku.

Korak 4: Kvantizacija

Sedaj bomo kvantizirali tabelo oziroma matriko koeficientov, ki smo jo dobili z metodo DCT. To je resnični del z izgubami v celotnem procesu. V matriki koeficientov celice levo-zgoraj ustrezajo nizkim frekvencam, celice desno-spodaj pa visokim frekvencam. Spomnimo se, da lahko odstranimo del z visokimi frekvencami, kar ne bo preveč opazno, saj je človeško oko bolj občutljivo na nizke frekvence.

Pripravimo kvantizacijsko tabelo oziroma matriko, ki bo vsebovala majhne vrednosti v celicah levo-zgoraj in velike vrednosti v celicah desno-spodaj.

Vsako vrednost v matriki koeficientov bomo nato delili z ustrezno vrednostjo iz kvantizacijske matrike ter rezultat zaokrožili na najbližje celo število. Zaradi velikih vrednosti kvantizacijske matrike v celicah desno-spodaj, bodo rezultati v tem delu enaki nič – s čimer bomo odstranili podatke o visokih frekvencah.

Kvantizacijska tabela je odvisna od kodirnika, zato je shranjena v glavi slike, da lahko sliko kasneje odkodiramo. Spodaj je standardna JPEG kvantizacijska tabela oziroma matrika:

In tabela oziroma matrika bloka po kvantizaciji (po tem, ko smo vsako vrednost iz matrike koeficientov delili z vrednostjo iz kvantizacijske matrike).

Opazimo lahko, da zgornja tabela oziroma matrika vsebuje veliko ničel. Vse to so visoke frekvence, ki smo jih odstranili. Postopek JPEG se »hvali«, da lahko samo s temi vrednostmi (brez ničel) nazaj dobimo skoraj popolnoma enako sliko.

Korak 5: Kodiranje

Sedaj imamo stisnjene podatke v obliki 2D tabele oziroma matrike. Vemo, da je veliko vrednosti enakih nič. Torej bomo našli boljši način za shranjevanje teh vrednosti, kot je 2D matrika.

Vrednosti bomo shranili v cikcakastem zaporedju. Vrednosti si bodo sledile v naslednjem zaporedju: -26, -3, 0, -3, -2, -6, 2, -4, 1, -4, 1, 1, 5, 1, 2, -1, 1, -1, 2, 0, 0, 0, 0, 0, -1, -1 in še 38 ničel.

Podatke tega vzorca lahko enostavno stisnemo s postopkom kodiranja z dolžinami čet (RLE). Končni rezultat stiskanja pa zakodiramo s kombinacijo kodiranja z dolžinami čet in Huffmanovega kodiranja.

Korak 6: Glava slike

JPEG/JFIF datoteke v splošnem v glavi slike vsebujejo naslednje podatke:

• Znak (0xFFD8) za začetek JPEG slike (ang. JPEG Start Of Image – SOI)
• Podatke o aplikaciji, ki je sliko ustvarila oziroma stisnila
• Širino v pikslih
• Višino v pikslih
• Število komponent (na primer: 3 za RGB)

Tako smo dobili stisnjeno JPEG datoteko!

Postopek razširjanja stisnjenih slikovnih datotek z metodo JPEG poteka v naslednjih korakih:

Korak 1: Odkodiranje

Končni rezultat stiskanja odkodiramo s kombinacijo kodiranja z dolžinami čet in Huffmanovega kodiranja. Dobimo cikcakasto zaporedje, ki ga lahko predstavimo kot tabelo oziroma matriko.

Korak 2: Dekvantizacija

Ker je kvantizacijska tabela odvisna od kodirnika, je shranjena v glavi slike, da lahko sliko kasneje odkodiramo. Spodaj je standardna JPEG kvantizacijska tabela oziroma matrika:

Vsako vrednost iz odkodirane tabele oziroma matrike pomnožimo z ustrezno vrednostjo iz kvantizacijske matrike ter rezultat zaokrožimo na najbližje celo število. Tako dobimo tabelo oziroma matriko koeficientov po dekvantizaciji (po tem, ko smo vsako vrednost iz odkodirane matrike pomnožili z vrednostjo iz kvantizacijske matrike).

Korak 3: Uporaba inverzne diskretne kosinusne transformacije (DCT)

Oglejmo si postopek za eno komponento (za preostali je postopek identičen).

S pomočjo spodnje kode, v programskem jeziku Python, izračunamo matriko bloka, spremenjeno z inverzno metodo DCT, to je metoda DCT tipa III:

import numpy  # Uvozimo knjižnico numpy
import scipy  # Uvozimo knjižnico scipy

# Definirajmo inverzno funkcijo: 2D DCT tipa III
def idct2D(x):
  tmp = scipy.fftpack.idct(x, type=2 ,norm='ortho').transpose()
  return scipy.fftpack.idct(tmp, type=2 ,norm='ortho').transpose()

# Matrika koeficientov odkodiranega bloka slike
print(idct2D([
  [-416.0, -33.0, -60.0, 32.0, 48.0, -40.0, 0.0, 0.0],
  [0.0, -24.0, -56.0, 19.0, 26.0, 0.0, 0.0, 0.0],
  [-42.0, 13.0, 80.0, -24.0, -40.0, 0.0, 0.0, 0.0],
  [-56.0, 17.0, 44.0, -29.0, 0.0, 0.0, 0.0, 0.0],
  [18.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
  [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
  [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
  [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
]))

Ker smo uporabili metodo DCT in ker lahko kosinusna funkcija zavzame vrednosti med 1 in -1, bomo dobili matriko z vrednostmi v obsegu [-128..127]:

Sedaj moramo vrednosti v matriki še ustrezno premakniti. To storimo tako, da vsaki vrednosti prištejemo 128 in dobimo:

  

Korak 4: Pretvorba iz barvnega prostora YCbCr v RGB

Za pretvarjanje iz YCbCr v RGB barvni prostor izračunamo vrednosti za vsak piksel posebej.

R = Y + 1,4020                       × (Cr - 128)
G = Y - 0,3441 × (Cb - 128) - 0,7141 × (Cr - 128)
B = Y + 1,7720 × (Cb - 128)

Tako smo dobili nestisnjeno slikovno datoteko v RGB barvnem prostoru!