Algoritmi u zhvillua nga një grup ekspertësh në fushën e fotografisë (Joint Photographic Expert Group) posaçërisht për kompresimin e imazheve 24-bit dhe gri në 1991. Ky algoritëm nuk është shumë i mirë në ngjeshjen e imazheve me dy nivele, por i trajton në mënyrë të shkëlqyer imazhet me tone të vazhdueshme, në të cilat pikselët afër priren të kenë ngjyra të ngjashme. Zakonisht syri nuk është në gjendje të vërejë ndonjë ndryshim kur ngjesh me këtë metodë 10 ose 20 herë.
Algoritmi bazohet në DCT të aplikuar në një matricë 8x8 pixel të blloqeve të imazhit të ndarë. DCT i zbërthen këto blloqe sipas amplitudave të frekuencave të caktuara. Si rezultat, merret një matricë në të cilën shumë koeficientë, si rregull, janë afër zeros, të cilat mund të përfaqësohen në formë të përafërt numerike, d.m.th. në formë të kuantizuar pa humbje të konsiderueshme në cilësinë e restaurimit.
Le të shqyrtojmë funksionimin e algoritmit në më shumë detaje. Supozoni se po kompresoni një imazh 24-bit me ngjyra të plota. Në këtë rast, marrim fazat e mëposhtme të punës.
Hapi 1. Ne e përkthejmë imazhin nga hapësira RGB në hapësirën YCbCr duke përdorur shprehjen e mëposhtme:
Vëmë re menjëherë se transformimi i anasjelltë merret lehtësisht duke shumëzuar matricën e kundërt me një vektor, i cili në thelb është hapësira YUV:
.
Hapi 2. Ndani imazhin origjinal në matrica 8x8. Ne formojmë tre matrica DCT pune nga secila - 8 bit veç e veç për secilin komponent. Në raportet e larta të kompresimit, blloku 8x8 zbërthehet në përbërës YCbCr në formatin 4: 2: 0, d.m.th. komponentët për Cb dhe Cr merren përmes një pike përgjatë rreshtave dhe kolonave.
Hapi 3. Aplikimi i DCT në blloqet e imazhit 8x8 pixel. Formalisht, DCT e drejtpërdrejtë për bllokun 8x8 mund të shkruhet si
ku 
... Meqenëse DCT është "zemra" e algoritmit JPEG, në praktikë është e dëshirueshme që të llogaritet sa më shpejt që të jetë e mundur. Një qasje e thjeshtë për të shpejtuar llogaritjet është llogaritja e funksioneve të kosinusit përpara kohe dhe tabelimi i rezultateve. Për më tepër, duke pasur parasysh ortogonalitetin e funksioneve të kosinusit me frekuenca të ndryshme, formula e mësipërme mund të shkruhet si
.
Këtu është një matricë 8x8 që përshkruan një hapësirë 8-dimensionale për të përfaqësuar kolonat e një blloku në atë hapësirë. Matrica është një matricë e transpozuar dhe bën të njëjtën gjë, por për rreshtat e bllokut. Rezultati është një transformim i ndashëm, i cili në formën e matricës shkruhet si
Këtu është rezultati i DCT, llogaritja e të cilit kërkon operacione shumëzimi dhe pothuajse të njëjtën sasi shtesash, e cila është dukshëm më e vogël se llogaritjet e drejtpërdrejta duke përdorur formulën e mësipërme. Për shembull, konvertimi i një imazhi 512x512 piksel do të kërkojë operacione aritmetike. Duke marrë parasysh 3 komponentë të ndriçimit, marrim vlerën e 12 582 912 operacioneve aritmetike. Numri i shumëzimeve dhe mbledhjeve mund të reduktohet më tej duke përdorur algoritmin e transformimit të shpejtë të Furierit. Si rezultat, për të transformuar një bllok 8x8, do t'ju duhet të bëni 54 shumëzime, 468 shtesa dhe ndërrime bit.
Si rezultat i DCT, marrim një matricë në të cilën koeficientët në këndin e sipërm të majtë korrespondojnë me përbërësin me frekuencë të ulët të figurës, dhe në të djathtën e poshtme - me atë me frekuencë të lartë.
Hapi 4. Kuantizimi. Në këtë hap, disa informacione hidhen poshtë. Këtu, çdo numër nga matrica ndahet me një numër të veçantë nga "tabela e kuantizimit" dhe rezultati rrumbullakoset në numrin e plotë më të afërt:
.
Për më tepër, për secilën matricë Y, Cb dhe Cr, ju mund të vendosni tabelat tuaja të kuantizimit. Standardi JPEG madje lejon përdorimin e tabelave të veta të kuantizimit, të cilat, megjithatë, do të duhet të transmetohen në dekoder së bashku me të dhënat e kompresuara, gjë që do të rrisë madhësinë e përgjithshme të skedarit. Është e qartë se është e vështirë për një përdorues që të zgjedhë 64 koeficientë vetë, prandaj standardi JPEG përdor dy qasje për matricat e kuantizimit. E para është se standardi JPEG përfshin dy tabela kuantizimi të rekomanduara: një për luma dhe një për chroma. Këto tabela janë paraqitur më poshtë. Qasja e dytë është sintetizimi (llogaritja e shpejtë) e një tabele kuantizimi që varet nga një parametër që specifikohet nga përdoruesi. Tabela në vetvete është ndërtuar duke përdorur formulën
Në hapin e kuantizimit, raporti i kompresimit kontrollohet dhe ndodh humbja më e madhe. Është e qartë se duke vendosur tabela kuantizimi me koeficientë të mëdhenj, do të marrim më shumë zero dhe, për rrjedhojë, një raport më të madh kompresimi.
Kuantizimi shoqërohet gjithashtu me efekte specifike të algoritmit. Në vlera të mëdha të hapit të kuantizimit, humbjet mund të jenë aq të mëdha sa që imazhi të ndahet në katrorë 8x8 me një ngjyrë. Nga ana tjetër, humbjet në frekuenca të larta mund të shfaqen në të ashtuquajturin "efekt Gibbs", kur formohet një "aureolë" e valëzuar rreth kontureve me një tranzicion të mprehtë të ngjyrave.
Hapi 5. Ne e përkthejmë matricën 8x8 në një vektor me 64 elemente duke përdorur skanimin "zigzag" (Fig. 2).
Oriz. 2. "Zigzag" -skanim
Si rezultat, në fillim të vektorit, si rregull, do të shkruhen koeficientë jozero, dhe në fund do të formohen zinxhirë zero.
Hapi 6. Ne e transformojmë vektorin duke përdorur algoritmin e modifikuar RLE, në daljen e të cilit marrim çifte të tipit (kapërcim, numër), ku "kapërcimi" është numëruesi i zerove të kapërcyer, dhe "numri" është vlera që duhet të vendoset. qeliza tjetër. Për shembull, vektori 1118 3 0 0 0 -2 0 0 0 0 1… do të paloset në çifte (0, 1118) (0,3) (3, -2) (4,1)….
Duhet të theksohet se numri i parë i komponentit të transformuar është në thelb i barabartë me ndriçimin mesatar të bllokut 8x8 dhe quhet koeficienti DC. Po kështu për të gjitha blloqet e imazheve. Kjo rrethanë sugjeron që koeficientët DC mund të kompresohen në mënyrë efektive nëse mbani mend jo vlerat e tyre absolute, por vlerat relative në formën e diferencës midis koeficientit DC të bllokut aktual dhe koeficientit DC të bllokut të mëparshëm, dhe mbani mend koeficienti i parë siç është. Në këtë rast, renditja e koeficientëve DC mund të bëhet, për shembull, si më poshtë (Fig. 3). Pjesa tjetër e koeficientëve, të cilët quhen koeficientë AC, mbeten të pandryshuara.
Hapi 7. Lidhni çiftet që rezultojnë duke përdorur kode Huffman jo uniforme të tabelës fikse. Për më tepër, kode të ndryshme përdoren për koeficientët DC dhe AC, d.m.th. tabela të ndryshme me kode Huffman.
Oriz. 3. Skema e renditjes së koeficientit DC
Oriz. 4. Bllok diagrami i algoritmit JPEG
Procesi i restaurimit të imazhit në këtë algoritëm është plotësisht simetrik. Metoda ju lejon të kompresoni imazhet me 10-15 herë pa humbje të dukshme vizuale.
Gjatë zhvillimit të këtij standardi, ne u udhëhoqëm nga fakti se ky algoritëm duhej të kompresonte imazhet mjaft shpejt - jo më shumë se një minutë në një imazh mesatar. Kjo është në vitin 1991! Dhe zbatimi i tij i harduerit duhet të jetë relativisht i thjeshtë dhe i lirë. Në këtë rast, algoritmi duhej të ishte simetrik për sa i përket kohës së funksionimit. Përmbushja e kërkesës së fundit bëri të mundur shfaqjen e kamerave dixhitale që shkrepin imazhe 24-bit. Nëse algoritmi do të ishte asimetrik, do të ishte e pakëndshme të prisni për një kohë të gjatë derisa pajisja të "ringarkohet" - do të kompresojë imazhin.
Megjithëse JPEG është një standard ISO, formati i skedarit të tij nuk është rregulluar. Duke përfituar nga kjo, prodhuesit krijojnë formatet e tyre të papajtueshme dhe, për rrjedhojë, mund të ndryshojnë algoritmin. Kështu, tabelat e brendshme të algoritmit të rekomanduar nga ISO zëvendësohen prej tyre me të tyret. Ekzistojnë gjithashtu opsione JPEG për aplikacione specifike.
- Tutorial
UPD. U detyrua të hiqte formatimin monospace. Një ditë të bukur, habraparser ndaloi së perceptuari formatimin brenda etiketave para dhe kodike. I gjithë teksti u kthye në rrëmujë. Administrata e Habrit nuk mund të më ndihmonte. Tani i pabarabartë, por të paktën i lexueshëm.
A keni menduar ndonjëherë se si funksionon një skedar jpg? Le ta kuptojmë tani! Ngroheni përpiluesin tuaj të preferuar dhe redaktorin hex, le ta deshifrojmë këtë:
Kam marrë posaçërisht një vizatim më të vogël. Ky është faviconi i njohur, por shumë i ngjeshur i Google:
Unë ju paralajmëroj menjëherë se përshkrimi është thjeshtuar dhe informacioni i dhënë nuk është i plotë, por më vonë do të jetë e lehtë për të kuptuar specifikimin.
Pa e ditur as se si ndodh kodimi, ne tashmë mund të nxjerrim diçka nga skedari.
- shënuesi i fillimit. Gjendet gjithmonë në fillim të të gjithë skedarëve jpg.
I ndjekur nga byte
... Ky është një shënues që shënon fillimin e seksionit të komenteve. 2 bajtet e ardhshme
- gjatësia e seksionit (duke përfshirë këto 2 bajt). Pra, në dy të ardhshme
- vetë komenti. Këto janë kodet për karakteret ":" dhe ")", d.m.th. emoticon i rregullt. Mund ta shihni në rreshtin e parë në anën e djathtë të redaktorit hex.
Pak teori
Shkurtimisht në hapa:
Le të mendojmë për rendin në të cilin këto të dhëna mund të kodohen. Supozoni, së pari, plotësisht, për të gjithë imazhin, kanali Y është i koduar, pastaj Cb, pastaj Cr. Të gjithë e mbajnë mend ngarkimin e fotografive në dial-up. Nëse do të kodoheshin në këtë mënyrë, do të duhej të prisnim që i gjithë imazhi të ngarkohej përpara se të shfaqet në ekran. Do të jetë gjithashtu e pakëndshme nëse fundi i skedarit humbet. Ndoshta ka edhe arsye të tjera të mira. Prandaj, të dhënat e koduara renditen në mënyrë alternative, në pjesë të vogla. 
Më lejoni t'ju kujtoj se çdo bllok Y ij, Cb ij, Cr ij është një matricë e koeficientëve DCT të koduar me kodet Huffman. Në dosje ato janë renditur në këtë rend: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Leximi i një skedari
Pasi të kemi nxjerrë komentin, duhet të jetë e lehtë të kuptohet se:- Skedari ndahet në sektorë të paraprirë nga shënuesit.
- Shënuesit janë 2 bajt të gjatë, me bajtin e parë.
- Pothuajse të gjithë sektorët e ruajnë gjatësinë e tyre në 2 bajt të ardhshëm pas shënuesit.
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 FF
C4 00 16 11 01 01 01 00 00 00 00 00 00 00 00 00
00 00 00 00 11 00 01 FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00 AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9
Shënues: DQT - tabela e kuantizimit.
FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
Kreu i seksionit është gjithmonë 3 bajt. Në rastin tonë, është. Kreu përbëhet nga:
Gjatësia: 0x43 = 67 bajt
Gjatësia e vlerave në tabelë: 0 (0 - 1 bajt, 1 - 2 bajt)
[_0]
ID e tabelës: 0
64 bajtet e mbetura duhet të plotësojnë tabelën 8x8.
Shikoni më nga afër rendin në të cilin plotësohen vlerat e tabelës. Ky rend quhet rendi zigzag: 
Shënuesi: SOF0 - DCT bazë
Ky shënues quhet SOF0 dhe do të thotë që imazhi është i koduar me metodën bazë. Është shumë e zakonshme. Por në internet, metoda progresive e njohur për ju nuk është më pak e popullarizuar, kur së pari ngarkohet një imazh me rezolucion të ulët, dhe më pas një fotografi normale. Kjo ju lejon të kuptoni se çfarë tregohet atje pa pritur një shkarkim të plotë. Specifikimi përcakton disa metoda të tjera, siç më duket mua, jo shumë të zakonshme.FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01
Gjatësia: 17 bajt.
Saktësia: 8 bit. Në metodën bazë, është gjithmonë 8. Siç e kuptoj unë, kjo është thellësia bit e vlerave të kanalit.
Lartësia e modelit: 0x10 = 16
Gjerësia e modelit: 0x10 = 16
Numri i komponentëve: 3. Më shpesh këto janë Y, Cb, Cr.
Komponenti i parë:
ID: 1
Hollimi horizontal (H 1): 2
[_2]
Decimation vertikal (V 1): 2
ID e tabelës së kuantizimit: 0
Komponenti i dytë:
ID: 2
Hollimi horizontal (H 2): 1
[_1]
Hollimi vertikal (V 2): 1
Komponenti i tretë:
ID: 3
Hollimi horizontal (H 3): 1
[_1]
Hollimi vertikal (V 3): 1
ID e tabelës së kuantizimit: 1
Tani shikoni se si të përcaktoni se sa i holluar është imazhi. Gjeni H max = 2 dhe V max = 2. Kanali i do të pritet në H max / H i herë horizontalisht dhe V max / V i herë vertikalisht.
Shënues: DHT (Tabela Huffman)
Ky seksion ruan kodet dhe vlerat e marra nga kodimi Huffman.FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02
gjatësia: 21 bajt.
klasa: 0 (0 - tabela e koeficientëve DC, 1 - tabela e koeficientëve AC).
[_0]
ID e tabelës: 0
Gjatësia e kodit Huffman: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Numri i kodeve:
Numri i kodeve nënkupton numrin e kodeve të asaj gjatësi. Vini re se seksioni ruan vetëm gjatësinë e kodeve, jo vetë kodet. Ne duhet t'i gjejmë vetë kodet. Pra, kemi një kod me gjatësi 1 dhe një - me gjatësi 2. Gjithsej janë 2 kode, nuk ka më kode në këtë tabelë.
Një vlerë lidhet me secilin kod dhe ato renditen më pas në skedar. Vlerat janë me një bajt, kështu që ne lexojmë 2 bajt.
- vlera e kodit të parë.
- vlera e kodit të dytë.
Ndërtimi i një peme të kodit Huffman
Duhet të ndërtojmë një pemë binare nga tabela që morëm në seksionin DHT. Dhe tashmë nga kjo pemë ne njohim çdo kod. Ne i shtojmë vlerat në rendin në të cilin ato tregohen në tabelë. Algoritmi është i thjeshtë: pavarësisht se ku jemi, ne gjithmonë përpiqemi të shtojmë një vlerë në degën e majtë. Dhe nëse ajo është e zënë, atëherë në të djathtë. Dhe nëse nuk ka vend atje, atëherë kthehemi në një nivel më të lartë dhe provojmë nga atje. Ju duhet të ndaleni në një nivel të barabartë me gjatësinë e kodit. Degët e majta korrespondojnë me 0, degët e djathta - 1.Koment:
Nuk është e nevojshme të filloni nga lart çdo herë. Vlera e shtuar - kthehu një nivel më lart. A ekziston dega e duhur? Nëse po, ngrihuni përsëri. Nëse jo, krijoni degën e duhur dhe shkoni atje. Pastaj, nga atje, filloni kërkimin tuaj për të shtuar vlerën tjetër.
Pemë për të gjitha tabelat në këtë shembull: 
UPD (faleminderit): Nyjet e pemës së parë (DC, id = 0) duhet të kenë vlera 0x03 dhe 0x02
Në rrathë - vlerat e kodeve, nën qarqe - vetë kodet (do të shpjegoj se i kemi marrë, duke shkuar nga lart në secilën nyje). Është me kode të tilla (të kësaj dhe tabelave të tjera) që përmbajtja e vetë figurës kodohet.
Shënuesi: SOS (Fillimi i Skanimit)
Bajt në shënues do të thotë "PO! Më në fund, shkuam drejtpërdrejt në analizimin e seksionit të imazhit të koduar! ". Megjithatë, seksioni quhet simbolikisht SOS.& nbsp FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Gjatësia e pjesës së kokës (jo e gjithë seksionit): 12 bajt.
Numri i komponentëve të skanimit. Kemi 3, një për Y, Cb, Cr.
Komponenti i parë:
Numri i pjesës së figurës: 1 (Y)
ID e tabelës Huffman për koeficientët DC: 0
[_0]
ID e tabelës Huffman për koeficientët AC: 0
Komponenti i dytë:
Numri i pjesës së figurës: 2 (Cb)
[_1]
Komponenti i tretë:
Numri i komponentit të figurës: 3 (Cr)
ID-ja e tabelës Huffman për koeficientët DC: 1
[_1]
ID e tabelës Huffman për koeficientët AC: 1
Këta komponentë alternohen në mënyrë ciklike.
Këtu përfundon pjesa e kokës, nga këtu deri në fund (shënuesi) i të dhënave të koduara.
0
Gjetja e koeficientit DC.
1.
Leximi i një sekuence bitash (nëse hasim 2 bajt, atëherë ky nuk është një shënues, por vetëm një bajt)... Pas çdo bit, ne lëvizim përgjatë pemës Huffman (me identifikuesin përkatës) përgjatë degëve 0 ose 1, në varësi të bitit të lexuar. Ne ndalojmë nëse jemi në nyjen përfundimtare.
10
1011101110011101100001111100100
2.
Marrim vlerën e nyjës. Nëse është 0, atëherë koeficienti është 0, ne e shkruajmë atë në tabelë dhe vazhdojmë me leximin e koeficientëve të tjerë. Në rastin tonë - 02. Kjo vlerë është gjatësia e koeficientit në bit. Kjo do të thotë, ne lexojmë 2 bitet e ardhshme, ky do të jetë koeficienti.
10
10
11101110011101100001111100100
3. Nëse shifra e parë e vlerës në binar është 1, atëherë e lëmë ashtu siç është: DC_coef = vlera. Përndryshe, transformojmë: DC_koefi = vlera-2 gjatësia e vlerës +1. Ne shkruajmë koeficientin në tabelë në fillim të zigzagut - këndi i sipërm i majtë.
Gjetja e koeficientëve AC.
1.
Ngjashëm me pikën 1, gjetja e koeficientit DC. Ne vazhdojmë të lexojmë sekuencën:
10
10
1110
1110011101100001111100100
2.
Marrim vlerën e nyjës. Nëse është e barabartë me 0, do të thotë që vlerat e mbetura të matricës duhet të plotësohen me zero. Pastaj matrica tjetër është e koduar. Të parët që lexuan deri këtu dhe më shkruajtën për mua në një personal, do të marrin një plus në karma. Në rastin tonë, vlera e nyjës është 0x31.
Thithja e parë: 0x3 - kjo është sa zero duhet të shtojmë në matricë. Këta janë 3 koeficientë zero.
Thithja e dytë: 0x1 - gjatësia e koeficientit në bit. Ne lexojmë pjesën tjetër.
10
10
1110
1
110011101100001111100100
3. Ngjashëm me pikën 3 të gjetjes së koeficientit DC.
Siç e keni kuptuar tashmë, ju duhet të lexoni koeficientët AC derisa të hasim një vlerë të kodit zero, ose derisa matrica të plotësohet.
Në rastin tonë, marrim:
10
10
1110
1
1100
11
101
10
0
0
0
1
11110
0
100
dhe matrica:
A keni vënë re se vlerat janë plotësuar në të njëjtin rend zigzag?
Arsyeja e përdorimit të këtij rendi është e thjeshtë - pasi sa më të mëdha të jenë vlerat e v dhe u, aq më pak i rëndësishëm është koeficienti S vu në transformimin kosinus diskret. Prandaj, në raportet e larta të kompresimit, koeficientët e parëndësishëm janë zero, duke zvogëluar kështu madhësinë e skedarit.
[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-1 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]
[-4 2 2 1 0 0 0 0]
[-1 0 -1 0 0 0 0 0]
[-1 -1 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]
Oh, harrova të them se koeficientët e koduar DC nuk janë vetë koeficientët DC, por dallimet e tyre midis koeficientëve të tabelës së mëparshme (i njëjti kanal)! Është e nevojshme të korrigjohen matricat:
DC për të 2-tën: 2 + (-4) = -2
DC për të tretën: -2 + 5 = 3
DC për 4: 3 + (-4) = -1
[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………
Tani është rendi. Ky rregull zgjat deri në fund të dosjes.
... dhe sipas matricës për Cb dhe Cr:
[-1 0 0 0 0 0 0 0]
[ 1 1 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]
Meqenëse këtu ka vetëm një matricë, koeficientët DC mund të lihen vetëm.
Llogaritjet
Kuantizimi
A ju kujtohet se matrica kalon në fazën e kuantizimit? Elementet e matricës duhet të shumëzohen term pas termi me elementët e matricës së kuantizimit. Mbetet për të zgjedhur atë që ju nevojitet. Së pari, ne skanuam komponentin e parë, komponentin e tij të imazhit = 1. Komponenti i imazhit me këtë identifikues përdor matricën e kuantizimit 0 (e kemi të parën nga të dyja). Pra, pas shumëzimit:
[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 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]
Në mënyrë të ngjashme, marrim 3 matrica të tjera të kanalit Y ...
[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 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] [ 0 0 0 0 0 0 0 0]
[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 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]
... dhe me matricë për Cb dhe Cr.
[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 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 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]
Transformimi i kosinusit diskret i anasjelltë
Formula nuk duhet të jetë e vështirë *. S vu është matrica jonë e koeficientit që rezulton. u është një kolonë, v është një rresht. s yx - vlerat e drejtpërdrejta të kanalit.
* Në përgjithësi, kjo nuk është plotësisht e vërtetë. Kur arrita të deshifroja dhe shfaqja imazhin 16x16 në ekran, bëra një imazh 600x600 (nga rruga, ishte kopertina e albumit të preferuar të Mind.In.A.Box - Lost Alone). Nuk funksionoi menjëherë - u shfaqën defekte të ndryshme. Së shpejti mund të admiroja foton e ngarkuar saktë. Vetëm shpejtësia e shkarkimit ishte shumë shqetësuese. Ende e mbaj mend që u deshën 7 sekonda. Por kjo nuk është për t'u habitur, nëse përdorni pa menduar formulën e mësipërme, atëherë për të llogaritur një kanal prej një piksel, do t'ju duhet të gjeni 128 kosinus, 768 shumëzime dhe disa shtesa atje. Thjesht mendoni për këtë - pothuajse një mijë operacione të vështira në vetëm një kanal të një piksel! Për fat të mirë, ka vend për optimizim (pas shumë eksperimentesh, e zvogëlova kohën e ngarkimit në kufirin e saktësisë së kohëmatësit 15 ms, dhe pas kësaj e ndryshova imazhin në një fotografi 25 herë më të madhe. Ndoshta do të shkruaj për këtë në një tjetër artikull).
Do të shkruaj rezultatin e llogaritjes vetëm të matricës së parë të kanalit Y (vlerat janë të rrumbullakosura):
[ 87 72 50 36 37 55 79 95]
[-10 5 31 56 71 73 68 62]
[-87 -50 6 56 79 72 48 29]
Dhe 2 të tjerat:
Cb Cr
[ 60 52 38 20 0 -18 -32 -40] [ 19 27 41 60 80 99 113 120]
[ 48 41 29 13 -3 -19 -31 -37] [ 0 6 18 34 51 66 78 85]
[ 25 20 12 2 -9 -19 -27 -32] [-27 -22 -14 -4 7 17 25 30]
[ -4 -6 -9 -13 -17 -20 -23 -25] [-43 -41 -38 -34 -30 -27 -24 -22]
[ -37 -35 -33 -29 -25 -21 -18 -17] [-35 -36 -39 -43 -47 -51 -53 -55]
[ -67 -63 -55 -44 -33 -22 -14 -10] [ -5 -9 -17 -28 -39 -50 -58 -62]
[ -90 -84 -71 -56 -39 -23 -11 -4] [ 32 26 14 -1 -18 -34 -46 -53]
[-102 -95 -81 -62 -42 -23 -9 -1] [ 58 50 36 18 -2 -20 -34 -42]
- Oh, le të shkojmë të hamë!
- Po nuk hyj fare, për çfarë bëhet fjalë.
- Pasi të merren vlerat e ngjyrave YCbCr, mbetet të konvertohet në RGB, si kjo: YCbCrToRGB (Y ij, Cb ij, Cr ij), Y ij, Cb ij, Cr ij - matricat tona rezultuese.
- 4 matrica Y dhe nga një Cb dhe Cr, pasi kemi holluar kanalet dhe 4 piksele të Y korrespondojnë me një Cb dhe Cr. Prandaj, llogaritni kështu: YCbCrToRGB (Y ij, Cb, Cr)
YCbCr në RGB
R = Y + 1,402 * KrG = Y - 0,34414 * Cb - 0,71414 * Cr
B = Y + 1,772 * Cb
Mos harroni të shtoni 128. Nëse vlerat janë jashtë intervalit, atëherë caktoni vlerat kufitare. Formula është e thjeshtë, por gjithashtu konsumon një pjesë të kohës së CPU.
Këtu janë tabelat që rezultojnë për kanalet R, G, B për katrorin e sipërm majtas 8x8 të shembullit tonë:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108
231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186
255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134
fund
Në përgjithësi, unë nuk jam specialist i JPEG, kështu që vështirë se mund t'u përgjigjem të gjitha pyetjeve. Thjesht, kur shkruaja dekoderin tim, shpesh më duhej të përballesha me probleme të ndryshme të pakuptueshme. Dhe kur imazhi u shfaq gabimisht, nuk e dija se ku bëra një gabim. Ndoshta ai i ka keqinterpretuar pjesët, ose ndoshta ka keqpërdorur DCT. Kam humbur një shembull hap pas hapi, kështu që shpresoj se ky artikull do të ndihmojë kur shkruaj një dekoder. Mendoj se mbulon përshkrimin e metodës bazë, por megjithatë nuk mund ta bësh vetëm atë. Këtu janë disa lidhje që më ndihmuan:JPEG është një nga algoritmet më të rinj dhe më të fuqishëm. Në praktikë, ai është standardi de fakto për imazhet me ngjyra të plota. Algoritmi funksionon me zona 8x8, ku shkëlqimi dhe ngjyra ndryshojnë relativisht pa probleme. Si rezultat, kur matrica e një rajoni të tillë zgjerohet në një seri të dyfishtë në kosinus (formula më poshtë), vetëm koeficientët e parë janë të rëndësishëm. Kështu, kompresimi në JPFG kryhet në kurriz të ndryshimeve të buta në ngjyrat në imazh.
Algoritmi u zhvillua nga një grup ekspertësh fotografie posaçërisht për kompresimin e imazheve JPEG 24-bit - Grupi i Përbashkët i Ekspertëve Fotografik - një ndarje brenda ISO - Organizata Ndërkombëtare për Standardizim. Në përgjithësi, algoritmi bazohet në një transformim kosinus diskret (më tej DCT), i aplikuar në matricën e imazhit për të marrë një matricë të re koeficientësh. Për të marrë imazhin origjinal, zbatohet transformimi i kundërt
DCT zbërthen imazhin në amplitudat e disa frekuencave, kështu, gjatë transformimit, marrim një matricë në të cilën shumë koeficientë janë ose afër ose të barabartë me zero. Përveç kësaj, sistemi i perceptimit të ngjyrave të njeriut është i dobët në njohjen e frekuencave të caktuara. Prandaj, është e mundur të përafrohen disa koeficientë më përafërsisht pa humbje të dukshme të cilësisë së imazhit.
Për këtë përdoret kuantizimi. Në rastin më të thjeshtë, është një zhvendosje aritmetike në të djathtë. Me këtë transformim, disa informacione humbasin, por mund të arrihen raporte të mëdha kompresimi.
Funksionimi i algoritmit.
Le të kompresojmë një imazh 24-bit.
Hapi I.
Ne e përkthejmë imazhin nga hapësira e ngjyrave RGB, me komponentët përgjegjës për përbërësit e kuq (E kuqe), jeshile (E gjelbër) dhe blu (Blu) të ngjyrës së pikës, në hapësirën e ngjyrave YCrCb (nganjëherë quhet YUV).
Në të, Y është komponenti i shkëlqimit, dhe Cg, Cb janë përbërësit përgjegjës për ngjyrën (e kuqe kromatike dhe blu kromatike). Për shkak të faktit se syri i njeriut është më pak i ndjeshëm ndaj ngjyrës sesa ndaj shkëlqimit, bëhet e mundur arkivimi i grupeve për komponentët Cg dhe Cb me humbje të larta dhe, në përputhje me rrethanat, raporte të larta kompresimi. Ky transformim është përdorur prej kohësh në televizion. Një brez më i ngushtë frekuencash u ndahet sinjaleve përgjegjëse për ngjyrën.
Përkthimi i thjeshtuar nga hapësira me ngjyra RGB në hapësirën e ngjyrave YCrCb mund të përfaqësohet si më poshtë:
Transformimi i anasjelltë kryhet duke shumëzuar vektorin YUV me matricën e kundërt:
Hapi 2.
Ndani imazhin origjinal në matrica 8x8. Ne formojmë tre matrica DCT pune nga secila - 8 bit veç e veç për secilin komponent. Në raportet më të larta të kompresimit, ky hap mund të jetë pak më i vështirë. Imazhi ndahet nga komponenti Y - si në rastin e parë, dhe për komponentët Cr dhe Cb matricat shtypen përmes një rreshti dhe përmes një kolone. ato. nga matrica origjinale 16x16, merret vetëm një matricë DCT funksionale. Për më tepër, siç është e lehtë për t'u parë, ne humbasim 3/4 e informacionit të dobishëm në lidhje me përbërësit e ngjyrave të figurës dhe marrim menjëherë një ngjeshje të dyfishtë. Ne mund ta bëjmë këtë duke punuar në hapësirën YCrCb. Siç ka treguar praktika, kjo nuk ndikon ndjeshëm në imazhin RGB që rezulton.
Hapi 3.
Ne aplikojmë DCT për secilën matricë të punës. Në këtë rast, marrim një matricë në të cilën koeficientët në këndin e sipërm të majtë korrespondojnë me përbërësin me frekuencë të ulët të figurës, dhe në të djathtën e poshtme - me atë me frekuencë të lartë.
Në një formë të thjeshtuar, ai transformim mund të përfaqësohet si më poshtë:
Hapi 4.
Ne kryejmë kuantizimin. Në parim, kjo është thjesht pjesëtimi i matricës së punës me elementin e matricës së kuantizimit sipas elementit. Për çdo komponent (Y, U dhe V), në rastin e përgjithshëm, specifikohet matrica e saj e kuantizimit (më tej MK).
Në këtë hap, raporti i ngjeshjes kontrollohet dhe ndodh humbja më e madhe. Është e qartë se duke specifikuar MK me koeficientë të mëdhenj, do të marrim më shumë zero dhe, për rrjedhojë, një raport më të madh kompresimi.
Kuantizimi shoqërohet gjithashtu me efekte specifike të algoritmit. Në vlera të mëdha të koeficientit gama , - humbja në frekuenca të ulëta mund të jetë aq e madhe sa që imazhi të ndahet në katrorë 8x8. Humbjet në frekuenca të larta mund të shfaqen në të ashtuquajturin "efekt Gibbs", kur një lloj "halo" formohet rreth kontureve me një tranzicion të mprehtë të ngjyrave.
Hapi 5.
Ne e përkthejmë matricën 8x8 në një vektor me 64 elemente duke përdorur një skanim zigzag, d.m.th. zgjidhni elementet me indekse (0.0). (0.1). (1.0). (2.0) ...
Kështu, në fillim të vektorit, marrim koeficientët e matricës që korrespondojnë me frekuenca të ulëta, dhe në fund - frekuenca të larta.
Hapi 6.
Përbërja e vektorit duke përdorur algoritmin e kodimit të grupit. Në këtë rast, marrim çifte të tipit (kapërcim, numër), ku "kapërcimi" është numëruesi i zerave të kapërcyer, dhe "numri" është vlera që duhet të vendoset në qelizën tjetër.
Pra, vektori do të paloset në çifte (0, 42) (0, 3) (3, -2) (4, 1)
Hapi 7.
I shembim çiftet e mësuara duke koduar Huffman me një tabelë fikse.
Procesi i restaurimit të imazhit në këtë algoritëm është plotësisht simetrik. Metoda ju lejon të kompresoni disa imazhe 10-15 herë pa humbje serioze.
Tubacioni operativ i përdorur në algoritmin JPEG.
Aspektet pozitive të rëndësishme të algoritmit janë se:
- 1) Është vendosur raporti i kompresimit
- 2) Imazhi me ngjyra në dalje mund të jetë 24 bit për pikë.
Disavantazhet e algoritmit janë se:
- 1) Kur rritet raporti i kompresimit, imazhi ndahet në katrorë të veçantë (8x8). Kjo për faktin se humbje të mëdha ndodhin në frekuenca të ulëta gjatë kuantizimit dhe bëhet e pamundur rikthimi i të dhënave origjinale.
- 2) Shfaqet efekti Gibbs - halo përgjatë kufijve të tranzicioneve të mprehta të ngjyrave.
JPEG u standardizua relativisht kohët e fundit - në 1991. Por edhe atëherë kishte algoritme që ngjeshnin më fort me më pak humbje të cilësisë. Fakti është se veprimet e zhvilluesve të standardit ishin të kufizuara nga fuqia e teknologjisë që ekzistonte në atë kohë. Kjo do të thotë, edhe në një kompjuter personal, algoritmi duhej të punonte për më pak se një minutë në një imazh mesatar, dhe zbatimi i tij në harduer duhej të ishte relativisht i thjeshtë dhe i lirë. Algoritmi duhej të ishte simetrik (koha e dekompresimit është afërsisht e barabartë me kohën e arkivimit).
Kërkesa e fundit bëri të mundur shfaqjen e kamerave dixhitale - pajisje me madhësinë e një videokamere të vogël që kapin fotografi 24-bit në një kartë flash 10-20 MB me një ndërfaqe PCMCIA. Pastaj karta futet në folenë e laptopit dhe programi përkatës ju lejon të lexoni imazhet. Nëse algoritmi ishte asimetrik, do të ishte e pakëndshme të prisni për një kohë të gjatë derisa pajisja të "ringarkohet" - do të kompresojë imazhin.
Një tipar jo shumë i këndshëm i JPEG është gjithashtu fakti që shpesh vijat horizontale dhe vertikale në ekran janë plotësisht të padukshëm dhe mund të shfaqen vetëm kur printohen në formën e një modeli moire. Ndodh kur një ekran printimi i zhdrejtë mbivendoset në vijat horizontale dhe vertikale të figurës. Për shkak të këtyre surprizave, JPEG nuk rekomandohet të përdoret në mënyrë aktive në printim, duke vendosur koeficientë të lartë. Sidoqoftë, kur arkivohen dhe imazhe të destinuara për shikimin njerëzor, aktualisht është i pazëvendësueshëm.
Përdorimi i gjerë i JPEG ka qenë i kufizuar për një kohë të gjatë, ndoshta vetëm nga fakti se funksionon me imazhe 24-bit. Prandaj, për të parë një fotografi me një cilësi të pranueshme në një monitor të rregullt në një gamë 256 ngjyrash, ishte e nevojshme të përdorni algoritmet e duhura dhe, për rrjedhojë, një sasi të caktuar kohe. Në aplikacionet që synojnë një përdorues zgjedhës, siç janë lojërat, vonesa të tilla janë të papranueshme. Përveç kësaj, nëse imazhet që keni, të themi, konvertohen në formatin GIF 8-bit në JPEG 24-bit, dhe më pas kthehen në GIF për t'u parë, atëherë humbja e cilësisë do të ndodhë dy herë me të dy konvertimet. Sidoqoftë, fitimi në madhësinë e arkivave është shpesh aq i madh (3-20 herë!), Dhe humbja në cilësi është aq e vogël sa ruajtja e imazheve në JPEG është shumë efikase.
Duhet thënë disa fjalë për modifikimet e këtij algoritmi. Megjithëse JPEG është një standard ISO, formati i skedarit të tij nuk është rregulluar. Duke përfituar nga kjo, prodhuesit përdorin formatet e tyre të papajtueshme dhe, për rrjedhojë, mund të ndryshojnë algoritmin. Pra, tabelat e brendshme të algoritmit, të rekomanduara nga ISO. zëvendësohen prej tyre me Kronat e tyre, përveç kësaj, ka një konfuzion të lehtë kur vendosni shkallën e humbjeve. Për shembull, gjatë testimit, rezulton se cilësia "e shkëlqyer", "100%" dhe "10 pikë" japin imazhe dukshëm të ndryshme. Për më tepër, nga rruga, cilësia "100%" nuk do të thotë kompresim pa humbje. Ekzistojnë gjithashtu opsione JPEG për aplikacione specifike.
Si standard ISO, JPEG po përdoret më gjerësisht në shkëmbimin e imazheve përmes rrjeteve kompjuterike. Algoritmi JPEG mbështetet në formatet Quick Time, PostScript Level 2, Tiff 6.0 dhe, për momentin, zë një vend të spikatur në sistemet multimediale.
Karakteristikat e algoritmit JPFG:
Raportet e kompresimit: 2-200 (Përcaktuar nga përdoruesi).
Klasa e imazhit: Imazhe 24-bitëshe me ngjyra të plota, ose imazhe në shkallë gri pa tranzicion të menjëhershëm të ngjyrave (foto).
Simetria: 1.
Karakteristikat e veçanta: Në disa raste, algoritmi krijon një "halo" rreth skajeve të prera horizontale dhe vertikale në imazh (efekti Gibbs). Përveç kësaj, kur raporti i kompresimit është i lartë, imazhi ndahet në blloqe prej 8x8 pikselësh.
(shqiptohet "japeg" Joint Photographic Experts Group, sipas emrit të organizatës zhvilluese) është një nga formatet grafike të njohura që përdoret për të ruajtur imazhe fotografike dhe imazhe të ngjashme. Skedarët që përmbajnë të dhëna JPEG zakonisht kanë shtesat .jpeg, .jfif, .jpg, .JPG ose .JPE. Nga këto, megjithatë, .jpg është zgjerimi më i popullarizuar në të gjitha platformat.
1. Grupi i Përbashkët i Ekspertëve Fotografik;
2. Një metodë e kompresimit të imazhit e zhvilluar nga ky grup dhe një format grafik përkatës që përdoret shpesh në WWW. Karakterizohet nga kompaktësia e skedarëve dhe, në përputhje me rrethanat, transferimi i shpejtë, si dhe "humbja" e cilësisë së imazhit. Përdoret kryesisht për fotografi, pasi humbja e cilësisë është më pak kritike për ta. Ruan cilësimet e ngjyrave në hapësirën e ngjyrave RGB.
Jpeg(shqiptohet " japeg", Ing. Grupi i Përbashkët i Ekspertëve Fotografik, sipas emrit të zhvilluesit) është një nga formatet grafike të njohura që përdoret për të ruajtur imazhe fotografike dhe imazhe të ngjashme. Skedarët që përmbajnë të dhëna JPEG zakonisht kanë shtesa .jpeg, .jfif, .jpg, .JPG, ose .JPE... Megjithatë, në mesin e tyre .jpg shtesa më e njohur në të gjitha platformat. Lloji MIME është imazh / jpeg.
JPEG është një algoritëm i kompresimit të të dhënave me humbje.
Zona e aplikimit
Algoritmi JPEG është më i përshtatshmi për kompresimin e fotografive dhe pikturave që përmbajnë skena realiste me tranzicion të qetë në shkëlqim dhe ngjyra. JPEG përdoret më gjerësisht në fotografinë dixhitale dhe për ruajtjen dhe transmetimin e imazheve duke përdorur internetin.
Nga ana tjetër, JPEG ka pak përdorim për kompresimin e vizatimeve, tekstit dhe grafikëve të karaktereve, ku kontrasti i mprehtë midis pikselëve ngjitur çon në artefakte të dukshme. Këshillohet që të ruani imazhe të tilla në formate pa humbje si TIFF, GIF, PNG ose RAW.
JPEG (si metodat e tjera të kompresimit të shtrembërimit) nuk është i përshtatshëm për kompresimin e imazheve me përpunim shumëfazor, pasi shtrembërimet do të futen në imazhe sa herë që ruhen rezultatet e ndërmjetme të përpunimit.
JPEG gjithashtu nuk duhet të përdoret në rastet kur edhe humbja minimale është e papranueshme, për shembull, kur kompresoni imazhe astronomike ose mjekësore. Në raste të tilla, mund të rekomandohet mënyra e kompresimit JPEG pa humbje e ofruar nga standardi JPEG (i cili, për fat të keq, nuk mbështetet nga shumica e kodekëve të njohur) ose standardi i kompresimit JPEG-LS.
Kompresimi
Kur kompresohet, imazhi konvertohet nga RGB në YCbCr (YUV). Duhet të theksohet se standardi JPEG (ISO / IEC 10918-1) nuk rregullon në asnjë mënyrë zgjedhjen e YCbCr, duke lejuar lloje të tjera konvertimi (për shembull, me një numër komponentësh të ndryshëm nga tre), dhe kompresim pa konvertim (drejtpërdrejt në RGB), megjithatë, specifikimi JFIF (JPEG File Interchange Format, i propozuar në 1991 nga C-Cube Microsystems, dhe tani standardi de facto) supozon përdorimin e konvertimit RGB-> YCbCr.
Pas konvertimit RGB-> YCbCr për kanalet e imazhit Cb dhe Cr përgjegjës për ngjyrën, mund të kryhet "nën-kampionimi", që do të thotë se çdo blloku prej 4 pikselësh (2x2) të kanalit të ndriçimit Y i caktohen vlerat mesatare Cb dhe Cr (skema e dekimit "4: 2: 0"). Në të njëjtën kohë, për çdo bllok 2x2, në vend të 12 vlerave (4 Y, 4 Cb dhe 4 Cr), përdoren vetëm 6 (4 Y dhe një Cb dhe Cr mesatarisht). Nëse kërkesat e shtuara vendosen për cilësinë e imazhit të rikuperuar pas ngjeshjes, decimimi mund të kryhet vetëm në një drejtim - vertikalisht (skema "4: 4: 0") ose horizontalisht ("4: 2: 2"), ose jo. fare ("4: 4: 4").
Standardi gjithashtu lejon decimation me mesatare Cb dhe Cr jo për një bllok 2x2, por për katër pikselë të njëpasnjëshëm (vertikalisht ose horizontalisht), domethënë për blloqet 1x4, 4x1 (skema 4: 1: 1), si dhe 2x4 dhe 4x2 . Lejohet gjithashtu përdorimi i llojeve të ndryshme të decimimit për Cb dhe Cr, por në praktikë skema të tilla përdoren rrallë.
Më tej, komponenti luma Y dhe komponentët Cb dhe Cr përgjegjës për ngjyrën ndahen në blloqe prej 8x8 pikselësh. Çdo bllok i tillë i nënshtrohet një transformimi kosinus diskret (DCT). Koeficientët e marrë DCT kuantizohen (për Y, Cb dhe Cr, në rastin e përgjithshëm, përdoren matrica të ndryshme kuantizimi) dhe paketohen duke përdorur kodet Huffman. Standardi JPEG gjithashtu lejon përdorimin e kodimit aritmetik dukshëm më efikas, megjithatë, për shkak të kufizimeve të patentës (patenta për koduesin aritmetik QM të përshkruar në standardin JPEG i përket IBM), ajo nuk përdoret në praktikë.
Matricat e përdorura për të kuantizuar koeficientët DCT ruhen në pjesën e kokës së skedarit JPEG. Zakonisht ato ndërtohen në mënyrë që koeficientët e frekuencës së lartë të kuantizohen më fort se sa ato me frekuencë të ulët. Kjo çon në ashpërsimin e detajeve të imta në imazh. Sa më i lartë të jetë raporti i kompresimit, aq më fort kuantizohen të gjithë koeficientët.
Kur ruani një imazh në një skedar JPEG, specifikohet një parametër i cilësisë, i specifikuar në disa njësi arbitrare, për shembull, nga 1 në 100 ose nga 1 në 10. Një numër më i lartë zakonisht korrespondon me një cilësi më të mirë (dhe një madhësi më të madhe skedari të kompresuar ). Sidoqoftë, edhe kur përdoret cilësia më e lartë (që korrespondon me një matricë kuantizimi të përbërë nga vetëm një), imazhi i rindërtuar nuk do të përkojë saktësisht me atë origjinal, i cili shoqërohet si me saktësinë përfundimtare të ekzekutimit të DCT-së ashtu edhe me nevojën për të rrumbullakosur vlerat e Y, Cb, Cr dhe koeficientët DCT në tërësinë më të afërt. Modaliteti i kompresimit JPEG pa humbje, i cili nuk përdor DCT, siguron një përputhje të saktë të imazheve të rindërtuara dhe origjinale, megjithatë, efikasiteti i tij i ulët (raporti i kompresimit rrallë tejkalon 2) dhe mungesa e mbështetjes nga zhvilluesit e softuerit nuk kontribuan në popullaritetin e JPEG-së pa humbje. .
Varietetet e skemave të kompresimit JPEG
Standardi JPEG ofron dy mënyra kryesore për paraqitjen e të dhënave të koduara.
Më e zakonshmja, e mbështetur nga shumica e kodekëve të disponueshëm, është paraqitja vijuese JPEG e të dhënave, e cila përfshin kalimin sekuencial të bllokut të imazhit të koduar nga blloku nga e majta në të djathtë, nga lart poshtë. Veprimet e përshkruara më sipër kryhen në çdo bllok imazhi të koduar dhe rezultatet e kodimit vendosen në rrjedhën e daljes në formën e një "skanimi" të vetëm, d.m.th. grup të dhënash të koduara që korrespondojnë me imazhin e përshkuar në mënyrë sekuenciale ("skanuar"). Modaliteti i kodimit bazë ose "bazë" e lejon vetëm këtë paraqitje. Modaliteti i zgjatur (i zgjatur), së bashku me atë sekuencial, gjithashtu lejon prezantimin progresiv (JPEG progresiv) të të dhënave.
Në rastin e JPEG-së progresive, të dhënat e kompresuara shkruhen në rrjedhën e daljes si një grup skanimesh, secila prej të cilave përshkruan imazhin plotësisht me shkallë në rritje të detajeve. Kjo arrihet ose duke regjistruar në çdo skanim jo një grup të plotë koeficientësh DCT, por vetëm disa prej tyre: së pari - me frekuencë të ulët, në skanimet e ardhshme - me frekuencë të lartë (metoda e "zgjedhjes spektrale", dmth. kampionimi spektral) , ose në mënyrë sekuenciale, nga skanimi në skanim, përsosje e koeficientëve të DCT (metoda "përafrim i njëpasnjëshëm", dmth përafrime të njëpasnjëshme). Ky përfaqësim progresiv i të dhënave është veçanërisht i dobishëm kur transferoni imazhe të kompresuara duke përdorur kanale komunikimi me shpejtësi të ulët, pasi ju lejon të merrni një ide për të gjithë imazhin pasi të jetë transferuar vetëm një pjesë e vogël e skedarit JPEG.
Të dy skemat e përshkruara (si JPEG sekuenciale ashtu edhe progresive) bazohen në DCT dhe në thelb nuk lejojnë marrjen e një imazhi të rivendosur absolutisht identik me atë origjinal. Megjithatë, standardi gjithashtu lejon kompresimin që nuk përdor DCT, por është ndërtuar mbi bazën e një parashikuesi linear (pa humbje, d.m.th. "pa humbje", JPEG), i cili garanton koincidencë të plotë, bit për bit, të origjinalit dhe të rindërtuar. imazhe. Në të njëjtën kohë, raporti i kompresimit për imazhet fotografike rrallë arrin 2, por mungesa e garantuar e shtrembërimit në disa raste rezulton të jetë e kërkuar. Raporte dukshëm më të larta të kompresimit mund të merren duke përdorur metodën e ngjeshjes JPEG-LS të përshkruar nga ISO / IEC 14495-1, e cila, pavarësisht ngjashmërisë në emra, nuk lidhet drejtpërdrejt me standardin JPEG ISO / IEC 10918-1 (ITU T. 81 Rekomandim) (ITU T.87 Rekomandim).
Sintaksa dhe struktura JPEG
Skedari JPEG përmban sekuencë shënues, secila prej të cilave fillon me bajt 0xFF, që tregon fillimin e shënuesit dhe identifikuesin e bajtit. Disa shënues përbëhen vetëm nga ky çift bajtësh, ndërsa të tjerët përmbajnë të dhëna shtesë që përbëhen nga një fushë me dy bajtë me gjatësinë e pjesës së informacionit të shënuesit (duke përfshirë gjatësinë e kësaj fushe, por minus dy bajtët e fillimit të shënuesi, dmth 0xFF dhe identifikuesi) dhe vetë të dhënat.
| Shënues | Bajt | Gjatësia | Emërimi |
|---|
JPEG është një nga algoritmet e reja dhe mjaft të fuqishme. Në praktikë, ai është standardi de fakto për imazhet me ngjyra të plota. Algoritmi funksionon me zona 8x8, ku shkëlqimi dhe ngjyra ndryshojnë relativisht pa probleme. Si rezultat, kur zbërthehet një matricë e tillë, zona në një rresht të dyfishtë në kosinus (shih formulat më poshtë) konsiderohet e rëndësishme vetëm nga koeficientët e parë. Kështu, kompresimi në JPEG kryhet për shkak të butësisë së ndryshimeve të ngjyrave në imazh.
Një algoritëm i zhvilluar nga një grup ekspertësh fotografie posaçërisht për kompresimin e imazheve 24-bit. JPEG - Joint Photographic Expert Group është një divizion brenda ISO - Organizatës Ndërkombëtare për Standardizim. Emri i algoritmit lexon ["jei" peg]. Në përgjithësi, algoritmi bazohet në një transformim kosinus diskret (më tej referuar si DCT), i cili aplikohet në matricën e imazhit për të marrë një matricë të re koeficientësh. Për të marrë imazhin origjinal, zbatohet një transformim invers.
DCT zbërthen imazhin në amplituda të frekuencave të caktuara. Kështu, kur transformojmë, marrim një matricë në të cilën shumë koeficientë janë ose afër ose të barabartë me zero. Përveç kësaj, për shkak të papërsosmërisë së vizionit njerëzor, koeficientët mund të përafrohen më përafërsisht pa humbje të dukshme të cilësisë së imazhit.
Për këtë përdoret kuantizimi. Në rastin më të thjeshtë, është një zhvendosje aritmetike në të djathtë. Me këtë transformim, disa informacione humbasin, por mund të arrihet një raport i madh kompresimi.
Si funksionon algoritmi
Pra, le të shqyrtojmë algoritmin më në detaje (Fig. 2.1). Le të themi se po kompresojmë një imazh 24-bit.
Hapi 1. Ne e përkthejmë imazhin nga hapësira e ngjyrave RGB, me komponentët përgjegjës për përbërësit e kuq (E kuqe), jeshile (E gjelbër) dhe blu (Blu) të ngjyrës së pikës, në hapësirën e ngjyrave YCrCb (nganjëherë quhet YUV).
Në të, Y është komponenti i shkëlqimit, dhe Cr, Co janë përbërësit përgjegjës për ngjyrën (e kuqja kromatike dhe bluja kromatike). Për shkak të faktit se syri i njeriut është më pak i ndjeshëm ndaj ngjyrave sesa ndaj shkëlqimit, bëhet i mundur arkivimi i grupeve për komponentët Cr dhe Co me humbje të mëdha dhe, në përputhje me rrethanat, raporte të mëdha kompresimi. Një transformim i tillë është përdorur prej kohësh në televizion. Një brez më i ngushtë frekuencash u ndahet sinjaleve përgjegjëse për ngjyrën. Përkthimi i thjeshtuar nga hapësira me ngjyra RGB në hapësirën e ngjyrave YCrCb mund të përfaqësohet duke përdorur një matricë tranzicioni:
Hapi 2. Ndani imazhin origjinal në matrica 8x8. Ne formojmë 3 matrica DCT pune nga secila - 8 bit veç e veç për secilin komponent. Në raportet më të larta të kompresimit, ky hap mund të jetë pak më i vështirë. Imazhi ndahet me komponentin Y, si në rastin e parë, dhe për komponentët Cr dhe Cb, matricat shtypen përmes një rreshti dhe përmes një kolone. Kjo do të thotë, nga matrica origjinale 16x16, merret vetëm një matricë DCT funksionale. Në të njëjtën kohë, siç është e lehtë për t'u parë, ne humbasim 3/4 e informacionit të dobishëm në lidhje me përbërësit e ngjyrave të figurës dhe marrim menjëherë një kompresim 2-fish. Ne mund ta bëjmë këtë duke punuar në hapësirën YCrCb. Siç ka treguar praktika, kjo ka pak efekt në imazhin RGB që rezulton.
Hapi 3. Në një formë të thjeshtuar, DCT për n = 8 mund të përfaqësohet si më poshtë:
nu, v] = ^ Hc (i, u) xC (j, v) y r Y) Yq= Numri i plotë Round Në këtë hap, raporti i ngjeshjes kontrollohet dhe ndodh humbja më e madhe. Është e qartë se duke specifikuar MK me koeficientë të mëdhenj, do të marrim më shumë zero dhe, për rrjedhojë, një raport më të madh kompresimi. Kuantizimi shoqërohet gjithashtu me efekte specifike të algoritmit. Me vlera të larta gama, humbja në frekuenca të ulëta mund të jetë aq e madhe sa që imazhi të ndahet në katrorë 8x8. Humbjet në frekuenca të larta mund të manifestohen në të ashtuquajturat Efekti Gibbs, kur rreth kontureve formohet një lloj "halo" me një tranzicion të mprehtë ngjyrash. Hapi 5. Ne e përkthejmë matricën 8x8 në një vektor 64 elementësh duke përdorur "zig-zag" -skanim, domethënë marrim elementë me indekse (0,0), (0,1), (1,0), (2). ,0)... Kështu, në fillim të vektorit, marrim koeficientët e matricës që korrespondojnë me frekuenca të ulëta, dhe në fund - frekuenca të larta. Hapi 6. Përbërja e vektorit duke përdorur algoritmin e kodimit të grupit. Në këtë rast, marrim çifte të tipit<пропустить, число>ku "kapërce" është numërimi i zeros për të kapërcyer dhe "numri" është vlera për të vendosur në qelizën tjetër. Pra, vektori 42 3000-2 00001 ... do të paloset në çifte (0.42) (0.3) (3, -2) (4.1) .... Hapi 7. Përziej çiftet që rezultojnë duke koduar Huffman me një tabelë fikse. Procesi i restaurimit të imazhit në këtë algoritëm është plotësisht simetrik. Metoda ju lejon të kompresoni disa imazhe 10-15 herë pa humbje serioze. Aspektet pozitive të rëndësishme të algoritmit janë se: ■ vendoset shkalla e ngjeshjes; ■ imazhi me ngjyra në dalje mund të jetë 24 bit për pikë. Disavantazhet e algoritmit janë se: ■ Rritja e raportit të kompresimit e ndan imazhin në katrorë të veçantë (8x8). Kjo për faktin se humbje të mëdha ndodhin në frekuenca të ulëta gjatë kuantizimit dhe bëhet e pamundur rikthimi i të dhënave origjinale. ■ Shfaqet efekti Gibbs - halo përgjatë skajeve të tranzicioneve të mprehta të ngjyrave. Siç u përmend tashmë, JPEG u standardizua relativisht kohët e fundit - në 1991. Por edhe atëherë kishte algoritme që ngjeshnin më fort me më pak humbje të cilësisë. Fakti është se veprimet e zhvilluesve të standardit ishin të kufizuara nga fuqia e teknologjisë që ekzistonte në atë kohë. Kjo do të thotë, edhe në një PC, algoritmi duhej të punonte për më pak se një minutë në një imazh mesatar, dhe zbatimi i tij në harduer duhej të ishte relativisht i thjeshtë dhe i lirë. Algoritmi duhej të ishte simetrik (koha e dekompresimit është afërsisht e barabartë me kohën e arkivimit). Përmbushja e kërkesës së fundit bëri të mundur shfaqjen e pajisjeve të tilla si kamerat dixhitale që shkrepin foto 24-bit në një kartë flash 8-256 MB. "Kjo kartë futet në një fole në laptop dhe programi përkatës ju lejon të lexoni imazhe Nuk është e vërtetë. Nya, nëse algoritmi do të ishte asimetrik, do të ishte e pakëndshme të prisni për një kohë të gjatë derisa pajisja të "ringarkohet" - do të kompresojë imazhin. Një veçori jo shumë e bukur e JPEG është gjithashtu pastaj, se shpesh vijat horizontale dhe vertikale në ekran janë plotësisht të padukshëm dhe mund të shfaqen vetëm kur printoni në formën e një modeli moire. Ndodh kur një ekran printimi i zhdrejtë mbivendoset në vijat horizontale dhe vertikale të figurës. Për shkak të këtyre surprizave, JPEG-të nuk janë rekomandohet në mënyrë aktive përdorimi në printim, duke vendosur koeficientë të lartë të matricës së kuantizimit. Sidoqoftë, kur arkivoni imazhe të destinuara për shikimin e njerëzve, aktualisht është i pazëvendësueshëm. I gjerë Përdorimi i JPEG ka qenë i kufizuar për një kohë të gjatë, ndoshta vetëm nga fakti se funksionon me imazhe 24-bit. Prandaj, për të parë një fotografi me një cilësi të pranueshme në një monitor të rregullt në një gamë 256 ngjyrash, ishte e nevojshme të përdorni algoritmet e duhura dhe, për rrjedhojë, një sasi të caktuar kohe. Në aplikacionet që synojnë një përdorues zgjedhës, siç janë lojërat, vonesa të tilla janë të papranueshme. Përveç kësaj, nëse imazhet që keni, për shembull, konvertohen në formatin GIF 8-bit në JPEG 24-bit, dhe më pas kthehen në GIF për t'u parë, atëherë humbja e cilësisë do të ndodhë dy herë me të dy konvertimet. Megjithatë, fitimi në madhësinë e arkivave është shpesh aq i madh (3-20 herë), dhe humbja e cilësisë është aq e vogël sa ruajtja e imazheve në JPEG rezulton të jetë shumë efikase. Duhet thënë disa fjalë për modifikimet e këtij algoritmi. Megjithëse JPEG është një standard ISO, formati i skedarit të tij nuk është rregulluar. Duke përdorur këtë, prodhuesit krijojnë formatet e tyre të papajtueshme dhe, për rrjedhojë, mund të ndryshojnë algoritmin. Kështu, tabelat e brendshme të algoritmit të rekomanduar nga ISO zëvendësohen prej tyre me të tyret. Përveç kësaj, ka pak konfuzion kur specifikoni një shkallë humbjeje. Për shembull, gjatë testimit, rezulton se cilësia "e shkëlqyer", "100%" dhe "10 pikë" japin imazhe dukshëm të ndryshme. Në të njëjtën kohë, nga rruga, cilësia "100%" nuk do të thotë kompresim pa humbje. Ekzistojnë gjithashtu opsione JPEG për aplikacione specifike. Si standard ISO, JPEG po përdoret më gjerësisht në shkëmbimin e imazheve përmes rrjeteve kompjuterike. Algoritmi JPEG mbështetet në Quick Time, PostScript Level 2, Tiff 6.0 dhe aktualisht zë një vend të spikatur në sistemet multimediale. Karakteristikat e algoritmit JPEG: o! sh. ,. Raporti i kompresimit: 2-200 (përcaktuar nga përdoruesi). , c,: _ ,. ... Klasa e imazhit: imazhe me ngjyra të plota 2jj. bit ose iso- | imazhe në shkallë gri pa tranzicione të papritura të ngjyrave (foto). Simetria: 1. Karakteristikat: në disa raste, algoritmi krijon! "halo" rreth skajeve të mprehta horizontale dhe vertikale në imazh (efekti Gibbs). Përveç kësaj, me një raport të lartë kompresimi, iso-! Reflektimi është i ndarë në blloqe prej 8x8 piksele.
