Cilat karakteristika lidhen me metodën e kompresimit jpeg. Transformimi i kosinusit diskret

18.05.2019 Gabimet

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 zerave 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.

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 përbërësit 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.

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.

Për lehtësi, le të theksojmë 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.

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ë - 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! Fatmirësisht, ka vend për optimizim (pas shumë eksperimentesh, e kam ulur kohën e ngarkimit në kufirin e saktësisë së kohëmatësit prej 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ë artikull të veçantë).

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)

Nëse keni zgjedhur 1 dhe 4, atëherë unë jam i lumtur për ju. Ose e keni kuptuar mirë, ose së shpejti do të shijoni vaktin tuaj.

YCbCr në RGB

R = Y + 1,402 * Kr
G = 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: Probleme me algoritmet e arkivimit me humbje

Algoritmet e njohura u përdorën fillimisht për të arkivuar imazhe. Ato që janë përdorur dhe përdoren në sistemet rezervë, gjatë krijimit të shpërndarjeve, etj. Këto algoritme e arkivuan informacionin të pandryshuar. Megjithatë, tendenca kryesore në vitet e fundit ka qenë përdorimi i klasave të reja të imazhit. Algoritmet e vjetra nuk i plotësojnë më kërkesat për arkivim. Shumë imazhe praktikisht nuk ishin të ngjeshura, megjithëse "në një shikim" ato kishin një tepricë të dukshme. Kjo çoi në krijimin e një lloji të ri të algoritmeve - algoritme të kompresimit me humbje. Si rregull, raporti i arkivimit dhe, për rrjedhojë, shkalla e humbjes së cilësisë në to mund të vendoset. Ky është një shkëmbim ndërmjet madhësisë dhe cilësisë së imazhit.

Një nga problemet serioze të grafikës kompjuterike është se ende nuk është gjetur një kriter adekuat për vlerësimin e humbjes së cilësisë së imazhit. Dhe humbet vazhdimisht - kur dixhitalizohet, kur transferohet në një gamë të kufizuar ngjyrash, kur transferohet në një sistem tjetër të përfaqësimit të ngjyrave për printim, dhe, gjë që është veçanërisht e rëndësishme për ne, kur arkivojmë me humbje. Mund të jepet një shembull i një kriteri të thjeshtë: devijimi standard i vlerave të pikselit (L 2 masë, ose rrënja mesatare katrore - RMS):

Sipas tij, imazhi do të dëmtohet rëndë kur ndriçimi të ulet me vetëm 5% (syri nuk do ta vërejë këtë - cilësimi i ndriçimit ndryshon shumë më tepër për monitorë të ndryshëm). Në të njëjtën kohë, imazhet me "borë" - një ndryshim i mprehtë në ngjyrën e pikave individuale, vija të dobëta ose "moire" do të konsiderohen "pothuajse të pandryshuara" (Shpjegoni pse?). Kriteret e tjera kanë edhe anët e tyre të pakëndshme.

Konsideroni, për shembull, devijimin maksimal:

Kjo masë, siç mund ta merrni me mend, është jashtëzakonisht e ndjeshme ndaj ritmit të pikselëve individualë. ato. në të gjithë imazhin, vetëm vlera e një piksel mund të ndryshojë ndjeshëm (e cila është pothuajse e padukshme për syrin), megjithatë, sipas kësaj mase, imazhi do të dëmtohet rëndë.

Masa që përdoret tani në praktikë quhet raporti sinjal-zhurmë i pikut në majë (PSNR).

Kjo masë, në fakt, është e ngjashme me devijimin standard, por është disi më i përshtatshëm për ta përdorur atë për shkak të shkallës logaritmike të shkallës. Ka të njëjtat disavantazhe si devijimi standard.

Humbja e cilësisë së imazhit vlerësohet më së miri nga sytë tanë. Arkivimi konsiderohet i shkëlqyeshëm, në të cilin është e pamundur të dallosh me sy midis imazheve origjinale dhe të zbërthyera. Mirë - kur mund të dalloni se cila nga imazhet është arkivuar, mund të krahasoni vetëm dy foto ngjitur. Me një rritje të mëtejshme të raportit të kompresimit, si rregull, efektet anësore karakteristike të këtij algoritmi bëhen të dukshme. Në praktikë, edhe me ruajtjen e cilësisë së shkëlqyer, mund të bëhen ndryshime të rregullta dhe specifike në imazh. Prandaj, algoritmet e arkivimit me humbje nuk rekomandohen për kompresimin e imazheve që më vonë ose do të printohen me cilësi të lartë ose do të përpunohen nga programet e njohjes së imazheve. Efektet e pakëndshme me imazhe të tilla, siç kemi thënë tashmë, mund të ndodhin edhe me shkallëzim të thjeshtë të imazhit. Algoritmi JPEG

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 (shih formulat më poshtë), vetëm koeficientët e parë janë të rëndësishëm. Kështu, kompresimi në JPEG kryhet në kurriz të ndryshimeve të buta në ngjyrat 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 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 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, është e mundur që të përafrohen koeficientët më përafërsisht pa humbje të dukshme të cilësisë së imazhit.

Si funksionon algoritmi

Pra, le t'i hedhim një vështrim më të afërt algoritmit. Le të themi se po kompresojmë një imazh 24-bit.

Hapi 1.

Në të, Y është komponenti i ndriçimit, dhe Cr, 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 Cr 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 duke përdorur një matricë tranzicioni:

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. 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ë imazhit dhe marrim kompresim dy herë në të njëjtën kohë. 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, ky transformim mund të përfaqësohet si më poshtë:

Hapi 4.

Ne kuantizojmë. Në thelb, është vetëm 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 q (në tekstin e mëtejmë 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 elementë duke përdorur një skanim "zigzag", d.m.th. marrim elemente 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 42 3 0 0 0 -2 0 0 0 0 1 ... do të paloset në çifte (0.42) (0.3) (3, -2) (4.1) ....

Hapi 7.

Lidhni ç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.

Tubacioni operativ i përdorur në algoritmin JPEG.

Aspektet pozitive të rëndësishme të algoritmit janë se:

Është vendosur raporti i kompresimit.
Fundjavë një imazh me ngjyra mund të jetë 24 bit për pikë.

Disavantazhet e algoritmit janë se:

Ndërsa raporti i kompresimit rritet, 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 rivendosja e të dhënave origjinale.
Efekti Gibbs manifestohet - halo përgjatë kufijve të tranzicioneve të mprehta të ngjyrave.

Siç u përmend, 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 që lodrat të tilla si kamerat dixhitale - pajisje me madhësinë e një videokamere të vogël të bënin fotografi 24-bit në një kartë flash 10-20 MB me një ndërfaqe PCMCIA. Pastaj kjo kartë futet në folenë e laptopit dhe programi përkatës ju lejon të lexoni imazhet. A nuk është e vërtetë, nëse algoritmi do të ishte asimetrik, do të ishte e pakëndshme të prisni një kohë të gjatë derisa pajisja të "ringarkohet" - do të ngjesh imazhin.

Një veti jo shumë e këndshme e JPEG është edhe fakti se 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 arkivoni imazhe të destinuara për shikimin e njerëzve, aktualisht është i pazëvendësueshëm.

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 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 pamje 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.

Karakteristikat e algoritmit JPEG:

Klasa e imazhit: Imazhe me ngjyra të plota 24-bit ose në shkallë gri pa tranzicione të mprehta të ngjyrave (foto).

Simetria: 1

Karakteristikat: Në disa raste, algoritmi krijon një "halo" rreth skajeve të mprehta 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.

Algoritmi fraktal

Ideja e metodës

Arkivimi fraktal bazohet në faktin se ne e përfaqësojmë imazhin në një formë më kompakte - duke përdorur koeficientët e Sistemit të Funksionit të Përsëritur (në tekstin e mëtejmë IFS). Përpara se të shikojmë vetë procesin e arkivimit, le të hedhim një vështrim se si IFS ndërton një imazh, d.m.th. procesi i dekompresimit.

Në mënyrë të rreptë, IFS është një grup transformimesh afine tre-dimensionale, në rastin tonë duke transformuar një imazh në një tjetër. Pikat në hapësirën tredimensionale transformohen (x_koordinata, y_koordinata, shkëlqimi).

Ky proces u demonstrua më qartë nga Barnsley në librin e tij "Compression Fractal Image". Atje u prezantua koncepti i një fotokopjuesi, i cili përbëhet nga një ekran në të cilin shfaqet fotografia origjinale dhe një sistem lentesh që projektojnë imazhin në një ekran tjetër:

Lentet mund të projektojnë një pjesë të imazhit formë të lirë kudo tjetër në imazhin e ri.
Zonat në të cilën imazhet janë projektuar mos kryqëzohen.
Lente mund ndryshoni ndriçimin dhe ulni kontrastin.
Lente mund pasqyrojnë dhe rrotullohen fragmenti i imazhit tuaj.
Lente duhet në shkallë(zvogëloni) fragmentin tuaj të imazhit.

Duke vendosur lentet dhe duke ndryshuar karakteristikat e tyre, ne mund të kontrollojmë imazhin që rezulton. Një përsëritje e punës së Makinerisë është se një i ri është ndërtuar nga imazhi origjinal duke përdorur dizajnin, pas së cilës i riu merret si fillestar. Argumentohet se në procesin e përsëritjes, ne do të marrim një imazh që do të ndalojë së ndryshuari. Do të varet vetëm nga vendndodhja dhe karakteristikat e lenteve dhe nuk do të varet nga imazhi origjinal. Ky imazh quhet " pikë fikse"ose tërheqës të këtij IFS. Teoria përkatëse garanton se ka saktësisht një pikë fikse për çdo IFS.

Meqenëse harta e lenteve është kompresive, çdo lente specifikon në mënyrë eksplicite i vetëngjashëm zonat në imazhin tonë. Falë vetë-ngjashmërisë, ne marrim një strukturë komplekse imazhi në çdo zmadhim. Kështu, është intuitivisht e qartë se sistemi i funksioneve të përsëritura përcakton fraktal(lirshëm - objekt matematikor i ngjashëm).

Më të njohurat janë dy imazhe IFS: Trekëndëshi i Sierpinskit dhe Fern Barnsley. "Trekëndëshi i Sierpinskit" përcaktohet nga tre, dhe "Fieri i Barnsley" nga katër transformime afine (ose, në terminologjinë tonë, "thjerrëza"). Çdo transformim është i koduar fjalë për fjalë nga bajtët e lexuar, ndërsa imazhi i ndërtuar me ndihmën e tyre mund të marrë disa megabajt.

Aktiviteti: Vizatoni 4 zona në imazh që do të kombinoheshin për të mbuluar të gjithë imazhin, secila prej të cilave do të ishte e ngjashme me të gjithë imazhin (mos harroni kërcellin e fierit).

Nga sa më sipër, bëhet e qartë se si funksionon arkivi dhe pse zgjat kaq shumë. Në fakt, kompresimi fraktal është një kërkim për rajone të ngjashme në një imazh dhe përcaktimin e parametrave të transformimeve afinike për to.

=>
Në rastin më të keq, nëse nuk zbatohet algoritmi optimizues, do të kërkohet një numërim dhe krahasim i të gjitha fragmenteve të mundshme të imazhit të madhësive të ndryshme. Edhe për imazhe të vogla, duke marrë parasysh diskretitetin, marrim një numër astronomik opsionesh për t'u kërkuar. Për më tepër, edhe një ngushtim i mprehtë i klasave të transformimit, për shembull, për shkak të shkallëzimit vetëm me një numër të caktuar herë, nuk jep një fitim të dukshëm në kohë. Përveç kësaj, cilësia e imazhit humbet. Shumica dërrmuese e kërkimeve në fushën e kompresimit fraktal tani synojnë zvogëlimin e kohës së arkivimit të kërkuar për të marrë një imazh me cilësi të lartë.

Përkufizimi.

ku a, b, c, d, e, f numra realë dhe quhet transformimi afinal dydimensional.

Përkufizimi. Transformimi i paraqitur si

ku a, b, c, d, e, f, p, q, r, s, t, u janë numra realë dhe quhet transformim afinal tredimensional.

Përkufizimi. Le të jetë një transformim në hapësirën X. Pika është ajo që quhet pikë fikse(tërheqës) transformim.

Përkufizimi. Një transformim në një hapësirë metrike (X, d) quhet kontraktues nëse ka një numër s:, e tillë që

Koment: Formalisht, ne mund të përdorim çdo hartë tkurrjeje për kompresimin fraktal, por në realitet përdoren vetëm transformimet afine tredimensionale me kufizime mjaft të forta në koeficientët.

Teorema. (Rreth kontraktimit të transformimit)

Lëreni në një hapësirë të plotë metrike (X, d). Atëherë ekziston saktësisht një pikë fikse e këtij transformimi, dhe për çdo pikë sekuenca konvergon në.

Një formulim më i përgjithshëm i kësaj teoreme garanton konvergjencë.

Përkufizimi. Imazhiështë një funksion S i përcaktuar në katrorin e njësisë dhe merr vlera nga 0 në 1 ose

Le të shkruhet në formë transformimi afinal tredimensional

dhe është përcaktuar në një nënbashkësi kompakte të katrorit kartezian x. Pastaj do të transferojë një pjesë të sipërfaqes S në një zonë të vendosur me një zhvendosje (e, f) dhe rrotullimi i dhënë nga matrica

Për më tepër, nëse interpretojmë vlerën S si shkëlqimi i pikave përkatëse, do të ulet në fq herë (transformimi duhet të jetë shtypës) dhe të ndryshojë në zhvendosje q.

Përkufizimi. Popullsi e fundme W kontraktimi i transformimeve afinale tredimensionale të përcaktuara në domene të tilla që quhet një sistem funksionesh të përsëritura ( IFS).

Sistemi i funksioneve të përsëritura shoqërohet në mënyrë unike me një pikë fikse - një imazh. Kështu, procesi i kompresimit është gjetja e koeficientëve të sistemit, dhe procesi i dekompresimit është të përsëritet sistemi derisa imazhi i marrë të stabilizohet (pika fikse IFS). Në praktikë, 7-16 përsëritje janë të mjaftueshme. Zonat do të referohen më poshtë si renditur, dhe zonat - domain.

Ndërtimi i algoritmit

Siç është bërë tashmë e qartë nga sa më sipër, detyra kryesore në ngjeshjen e algoritmit fraktal është gjetja e transformimeve përkatëse afine. Në rastin më të përgjithshëm, ne mund të përkthejmë zona imazhi të çdo madhësie dhe forme, por në këtë rast marrim një numër astronomik të versioneve të përsëritura të fragmenteve të ndryshme, të cilat nuk mund të përpunohen në momentin aktual as në një superkompjuter.

V versioni i trajnimit të algoritmit më poshtë, janë bërë kufizimet e mëposhtme të zonës:

Të gjitha zonat janë katrorë me brinjë paralele me anët e figurës. Ky kufizim është mjaft i rreptë. Në fakt, ne do të përafrojmë të gjithë shumëllojshmërinë e formave gjeometrike vetëm me katrorë.
Kur përktheni një domen domeni në një domen të renditur, kryhet zvogëlimi i madhësisë saktësisht dy herë... Kjo thjeshton shumë kompresorin dhe dekompresorin, pasi detyra e shkallëzimit të zonave të vogla nuk është e parëndësishme.
Të gjitha blloqet e domenit janë katrorë dhe kanë madhësi fikse... Imazhi ndahet nga një rrjet uniform në një grup blloqe domenesh.
Fushat e domenit janë marrë "Përmes pikës" përgjatë X dhe Y, e cila redukton menjëherë kërkimin me 4 herë.
Kur përktheni një domen domeni në një rrotullim të renditjes së një kubi, është e mundur vetëm në 0 0, 90 0, 180 0 ose 270 0... Reflektimi i pasqyrës lejohet gjithashtu. Numri i përgjithshëm i transformimeve të mundshme (duke numëruar bosh) është 8.
Bëhet shkallëzimi (ngjeshja) vertikalisht (shkëlqimi). një numër të caktuar herë- 0,75.

Këto kufizime ju lejojnë të:

Ndërtoni një algoritëm që kërkon një numër relativisht të vogël operacionesh edhe në imazhe mjaft të mëdha.
Është shumë kompakte për të paraqitur të dhëna për shkrim në një skedar. Ne kemi nevojë për çdo transformim afinal në IFS:

dy numra për të vendosur kompensimin e bllokut të domenit. Nëse i kufizojmë imazhet hyrëse në 512x512, atëherë do të mjaftojnë 8 bit për çdo numër.
tre bit për të vendosur transformimin e simetrisë kur përktheni një bllok domeni në një bllok të renditjes.
7-9 bit për të vendosur ndryshimin e shkëlqimit gjatë përkthimit.

Informacioni i madhësisë së bllokut mund të ruhet në kokën e skedarit. Kështu, ne shpenzuam më pak se 4 bajt për një transformim afine. Në varësi të madhësisë së bllokut, mund të llogarisni sa blloqe do të ketë në imazh. Kështu, ne mund të marrim një vlerësim të shkallës së ngjeshjes.

Për shembull, për një skedar në shkallë gri 256 ngjyra 512x512 piksele me një madhësi blloku prej 8 pikselësh, transformimet afinale do të jenë 4096 (512 / 8x512 / 8). Secili do të kërkojë 3.5 bajt. Prandaj, nëse skedari origjinal ishte 262144 (512x512) bajt (pa marrë parasysh kokën), atëherë skedari me koeficientë do të zërë 14336 bajt. Raporti i arkivimit është 18 herë. Në të njëjtën kohë, ne nuk marrim parasysh që skedari me koeficientë mund të ketë gjithashtu tepricë dhe të arkivohet duke përdorur një metodë arkivimi pa humbje, për shembull, LZW.

Disavantazhet e kufizimeve të propozuara:

Meqenëse të gjitha zonat janë katrore, është e pamundur të përfitohet nga ngjashmëria e objekteve që janë larg katrorëve (të cilat janë mjaft të zakonshme në imazhet reale.)
Në mënyrë të ngjashme, ne nuk do të jemi në gjendje të përdorim ngjashmërinë e objekteve në imazh, koeficienti i ngjashmërisë midis të cilave është shumë i ndryshëm nga 2.
Algoritmi nuk do të jetë në gjendje të përfitojë nga ngjashmëria e objekteve në imazh, këndi midis të cilit nuk është shumëfish i 90 0.

Kjo është tarifa për shpejtësia e kompresimit dhe për thjeshtësinë e paketimit të koeficientëve në një skedar.

Vetë algoritmi i paketimit reduktohet në numërimin e të gjitha blloqeve të domenit dhe zgjedhjen për çdo bllok të renditjes përkatëse. Më poshtë është një diagram i këtij algoritmi.

për (të gjitha blloqet e gamës) (
Min_distanca = Maksimumi Distance;
R ij= imazh-> CopyBlock (i, j);
për (të gjitha blloqet e domenit) (// Me kthesa dhe neg.
rrymë = Koordinatat e rrymës. transformimet;
D = imazh-> CopyBlock (aktual);
distanca_rryme = R ij.L2distanca (D);
nëse (distanca_aktuale< min_distance) {
// Nëse shanset më të mira janë më të këqija:
min_distanca = distanca_rryme;
më e mira = aktuale;
}
) // Gama tjetër
Ruaj_koeficientët_te_file (më e mira);
) // Domeni tjetër

Siç shihet nga algoritmi i mësipërm, për çdo bllok të renditjes, ne e kontrollojmë atë me të gjitha blloqet e mundshme të domenit (përfshirë ato që kanë kaluar transformimin e simetrisë), gjejmë opsionin me masën më të vogël L. 2 (devijimi standard më i vogël) dhe ruani koeficientët e këtij transformimi në një skedar. Koeficientët janë (1) koordinatat e bllokut të gjetur, (2) një numër nga 0 në 7 që karakterizon transformimin e simetrisë (rotacioni, reflektimi i bllokut) dhe (3) zhvendosja e shkëlqimit për këtë palë blloqe. Zhvendosja e ndriçimit llogaritet si:

ku r ij- vlerat e pikselit të bllokut të rangut ( R), a d ij- vlerat e pikselëve të bllokut të domenit ( D). Në këtë rast, masa konsiderohet si:

Ne nuk e llogarisim rrënjën katrore të L 2 masat dhe mos e ndani në n, meqenëse këto transformime janë monotonike dhe nuk do të na pengojnë të gjejmë ekstremin, megjithatë, ne do të jemi në gjendje të kryejmë dy operacione më pak për çdo bllok.

Le të llogarisim numrin e operacioneve të nevojshme për të kompresuar një imazh në shkallë gri 256 ngjyra 512x512 piksele me një madhësi blloku prej 8 pikselësh:

Kështu, ne arritëm të reduktojmë numrin e operacioneve të algoritmit të kompresimit në vlera mjaft të llogaritshme (megjithëse në disa orë).

Diagrami i algoritmit të dekompresimit të imazhit

Dekompresimi i algoritmit të kompresimit fraktal është jashtëzakonisht i thjeshtë. Është e nevojshme të kryhen disa përsëritje të transformimeve afine tredimensionale, koeficientët e të cilave janë marrë në fazën e kompresimit.

Absolutisht çdo imazh (për shembull, absolutisht i zi) mund të merret si fillestar, pasi aparati matematikor përkatës na garanton konvergjencën e sekuencës së imazheve të marra gjatë përsëritjeve IFS me një imazh të palëvizshëm (afër atij origjinal). Zakonisht 16 përsëritje janë të mjaftueshme për këtë.

Lexoni koeficientët e të gjitha blloqeve nga skedari;
Krijo një imazh të zi të madhësisë së dëshiruar;
Derisa (imazhi nuk do të lëvizë) (
Për (çdo varg (R)) (
D = imazh-> CopyBlock (D_coord_for_R);
Për (çdo piksel ( i, j) në bllok (
R ij = 0,75 D ij + o R;
) // Pixel tjetër
) // Blloku tjetër
) // Deri në fund

Meqenëse shënuam koeficientët për blloqet R ij(të cilat, siç kemi diskutuar, në rastin tonë të veçantë janë katrorë me të njëjtën madhësi) në mënyrë të vazhdueshme, rezulton se ne e mbushim imazhin në mënyrë sekuenciale me katrorët e rrjetës së ndarjes duke përdorur transformimin afin.

Siç mund ta llogaritni, numri i operacioneve për një piksel të një imazhi në shkallë gri gjatë restaurimit është jashtëzakonisht i vogël (N operacione "+", 1 operacione "*", ku N është numri i përsëritjeve, domethënë 7-16). Për shkak të kësaj, dekompresimi i imazheve për algoritmin fraktal është më i shpejtë se dekompresimi, për shembull, për algoritmin JPEG, në të cilin ka 64 operacione "+" dhe 64 "? ”(Me përjashtim të hapave RLE dhe kodimit Huffman!). Në këtë rast, për algoritmin fraktal, shumëzimi ndodh me një numër racional, një për çdo bllok. Kjo do të thotë që ne, së pari, mund të përdorim aritmetikën racionale me numra të plotë, e cila është dukshëm më e shpejtë se aritmetika me pikë lundruese. Së dyti, shumëzimi i një vektori me një numër është një operacion më i thjeshtë dhe më i shpejtë, i përfshirë shpesh në arkitekturën e procesorit (procesorët SGI, Intel MMX ...), sesa produkti me pika i dy vektorëve, i cili është i nevojshëm në rastin e JPEG. Për një imazh me ngjyra të plota, situata nuk ndryshon cilësisht, pasi të dy algoritmet përdorin përkthimin në një hapësirë tjetër ngjyrash.

Vlerësimi i humbjeve dhe metodat e rregullimit të tyre

Në një përmbledhje të versionit të thjeshtuar të algoritmit, shumë pyetje të rëndësishme janë lënë jashtë. Për shembull, çfarë të bëni nëse algoritmi nuk mund të gjejë një të ngjashëm për ndonjë fragment të imazhit? Një zgjidhje mjaft e qartë është ta thyeni këtë fragment në më të vogla dhe të përpiqeni t'i kërkoni ato. Në të njëjtën kohë, është e qartë se kjo procedurë nuk mund të përsëritet pafundësisht, përndryshe numri i transformimeve të nevojshme do të bëhet aq i madh sa që algoritmi do të pushojë së qeni një algoritëm kompresimi. Prandaj, ne lejojmë humbjen në një pjesë të imazhit.

Për algoritmin e ngjeshjes fraktal, si dhe për algoritmet e tjera të kompresimit me humbje, mekanizmat me anë të të cilëve do të mundësohet rregullimi i raportit të ngjeshjes dhe raportit të humbjeve janë shumë të rëndësishëm. Deri më sot, është zhvilluar një grup mjaft i madh i metodave të tilla. Së pari, është e mundur të kufizohet numri i transformimeve afine, duke siguruar me vetëdije raporti i kompresimit nuk është më i ulët se një vlerë fikse. Së dyti, është e mundur të kërkohet që në një situatë kur ndryshimi midis fragmentit të përpunuar dhe përafrimit më të mirë të tij është më i lartë se një vlerë e caktuar pragu, ky fragment duhet të shtypet (për të, kërkohen disa "thjerrëza"). Së treti, mund të ndaloni ndarjen e fragmenteve më të vogla se, të themi, katër pika. Duke ndryshuar vlerat e pragut dhe përparësinë e këtyre kushteve, ne do të jemi shumë fleksibël për të kontrolluar raportin e kompresimit të imazhit në rangun nga bitmap në çdo raport kompresimi. Vini re se ky fleksibilitet do të jetë shumë më i lartë se ai i rivalit më të afërt, algoritmi JPEG.

Karakteristikat e algoritmit fraktal :

Raportet e kompresimit: 2-2000 (përcaktuar nga përdoruesi).

Klasa e imazhit: Imazhe me ngjyra të plota 24-bit ose në shkallë gri pa tranzicione të mprehta të ngjyrave (foto). Është e dëshirueshme që zonat me rëndësi më të madhe (për perceptimin) të jenë më të kundërta dhe të mprehta, dhe zonat me rëndësi më të vogël - me kontrast të ulët dhe të paqarta.

Simetria: 100-100000

Karakteristikat: Mund ta shkallëzojë lirisht imazhin kur e zbërtheni, duke e zmadhuar 2-4 herë pa shfaqjen e "efektit të shkallëve". Ndërsa shkalla e ngjeshjes rritet, një efekt "bllokues" shfaqet në kufijtë e blloqeve në imazh.

Algoritmi rekurziv (valor).

Emri në anglisht për kompresimin rekurziv është wavelet. Përkthehet në Rusisht si kompresim i valës dhe si kompresim duke përdorur shpërthime. Ky lloj arkivimi është i njohur për një kohë të gjatë dhe rrjedh drejtpërdrejt nga ideja e përdorimit të koherencës së zonave. Algoritmi është i fokusuar në imazhet me ngjyra dhe bardh e zi me tranzicion të qetë. Ideale për fotografi të tilla si rrezet X. Raporti i kompresimit është vendosur dhe varion nga 5-100. Kur përpiqeni të vendosni një koeficient më të lartë në skajet e mprehta, veçanërisht ato që kalojnë përgjatë diagonales, shfaqet një "efekt shkallësh" - hapa me shkëlqim të ndryshëm, me madhësi disa pikselë.

Ideja e algoritmit është që ne të ruajmë ndryshimin në një skedar - numrin midis vlerave mesatare të blloqeve fqinje në imazh, i cili zakonisht merr vlera afër 0.

Pra dy numra a 2i dhe a 2i +1 mund të përfaqësohet gjithmonë si b 1 i=(a 2i +a 2i +1 ) / 2 dhe b 2 i=(a 2i -a 2i +1 ) / 2. Në mënyrë të ngjashme, sekuenca a imund të përkthehet në dyshe në sekuencë b 1,2 i.

Le të shohim një shembull specifik: le të kompresojmë një varg me vlera 8 pikselësh të ndriçimit ( a i): (220, 211, 212, 218, 217, 214, 210, 202). Ne marrim sekuencat e mëposhtme b 1 i, dhe b 2 i: (215.5, 215, 215.5, 206) dhe (4.5, -3, 1.5, 4). Vini re se vlerat b 2 ijanë mjaftueshëm afër 0. E përsërisim veprimin, duke marrë parasysh b 1 i si a i... Ky veprim kryhet sikur në mënyrë rekursive, prandaj emri i algoritmit. Marrim nga (215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75). Koeficientët e marrë, të rrumbullakosura në numra të plotë dhe të ngjeshur, për shembull, duke përdorur algoritmin Huffman me tabela fikse, mund t'i vendosim në një skedar.

Vini re se ne e kemi aplikuar transformimin tonë në zinxhir vetëm dy herë. Në realitet, ne mund të përballojmë të aplikojmë transformimin e valëzimit 4-6 herë. Për më tepër, ngjeshja shtesë mund të merret duke përdorur tabela jo uniforme të hapit Huffman (d.m.th. duhet të ruajmë kodin Huffman për vlerën më të afërt në tabelë). Këto teknika ju lejojnë të arrini raporte të dukshme të ngjeshjes.

Ushtrimi: Ne kemi rivendosur zinxhirin (215, 211) (0, 5) (5, -3, 2, 4) nga skedari (shih shembullin). Ndërtoni një varg me tetë vlera të shkëlqimit të pikselëve që do të rikrijohen nga algoritmi i kompresimit të valës.

Algoritmi për të dhënat 2D zbatohet në mënyrë të ngjashme. Nëse kemi një katror prej 4 pikësh me shkëlqim a 2 i, 2 j,a 2 i +1, 2 j,a 2 i, 2 j +1, dhe a 2 i +1, 2 j +1, pastaj

Origjinale		B 1	B 2
imazh		B 3	B 4

Duke përdorur këto formula, për një imazh prej 512x512 piksele, pas transformimit të parë, marrim 4 matrica me elemente 256x256:

-- E para, siç mund ta merrni me mend, do të ruajë një kopje të reduktuar të imazhit. Në të dytën, dallimet mesatare të çifteve të pikselave vlerësohen horizontalisht. Në të tretën, dallimet mesatare të çifteve të vlerave të pikselit përgjatë vertikales. E katërta përmban dallimet mesatare në vlerat e pikselit përgjatë diagonales. Për analogji me rastin dy-dimensional, ne mund të përsërisim transformimin tonë dhe të marrim në vend të matricës së parë 4 matrica me madhësi 128x128. Duke përsëritur transformimin tonë për herë të tretë, marrim si rezultat: 4 matrica 64x64, 3 matrica 128x128 dhe 3 matrica 256x256. Në praktikë, kur shkruani në një skedar, vlerat e marra në rreshtin e fundit () zakonisht neglizhohen (duke fituar menjëherë rreth një të tretën e madhësisë së skedarit - 1 - 1/4 - 1/16 - 1/64 ... ).

Përparësitë e këtij algoritmi mund t'i atribuohen faktit se ai shumë lehtë ju lejon të realizoni mundësinë e "zhvillimit" gradual të imazhit gjatë transmetimit të imazhit në rrjet. Përveç kësaj, duke qenë se ne në fakt ruajmë një kopje të miniaturës në fillim të figurës, e bën më të lehtë shfaqjen e imazhit "të përafërt" sipas titullit.

Ndryshe nga JPEG dhe algoritmi fraktal, kjo metodë nuk funksionon në blloqe, për shembull, 8x8 piksele. Më saktë operojmë me blloqet 2x2, 4x4, 8x8 etj. Sidoqoftë, për shkak të faktit se ne i ruajmë koeficientët për këto blloqe në mënyrë të pavarur, mund të shmangim lehtësisht ndarjen e imazhit në katrorë "mozaik".

Karakteristikat e algoritmit të valës:

Raportet e kompresimit: 2-200 (Përcaktuar nga përdoruesi).

Klasa e imazhit: Si fractal dhe JPEG.

Simetria: ~1.5

Karakteristikat: Përveç kësaj, kur raporti i kompresimit është i lartë, imazhi ndahet në blloqe të veçanta.

konkluzioni

Si përfundim, merrni parasysh tabelat që bashkojnë parametrat e algoritmeve të ndryshme të kompresimit të imazhit të diskutuar më sipër.

Algoritmi	Karakteristikat e imazhit për shkak të të cilave ndodh kompresimi
RLE	Ngjyra të njëpasnjëshme identike: 2 2 2 2 2 2 15 15 15
LZW	Zinxhirët identikë: 2 3 15 40 2 3 15 40
Huffman	Frekuenca e ngjyrave të ndryshme: 2 2 3 2 2 4 3 2 2 2 4
CCITT-3	Mbizotërimi i së bardhës në imazh, zona të mëdha të mbushura me një ngjyrë
Rekursive	Tranzicione të lëmuara ngjyrash dhe pa skaje të mprehta
Jpeg	Mungesa e kufijve të mprehtë
Fraktal	Ngjashmëria midis elementeve të imazhit

Algoritmi	Kompleti për kompresim	Simetria e kohës	Per cfare i orientuar	Humbjet	Dimensioni
RLE	32, 2, 0.5	1	3.4 bit	Jo	1D
LZW	1000, 4, 5/7	1.2-3	1-8 bit	Jo	1D
Huffman	8, 1.5, 1	1-1.5	8 bit	Jo	1D
CCITT-3	213(3), 5, 0.25	~1	1-bit	Jo	1D
JBIG	2-30 herë	~1	1-bit	Jo	2D
JPEG pa humbje	2 herë	~1	24-bit, gri	Jo	2D
Jpeg	2-20 herë	~1	24-bit, gri	po	2D
Kompresimi rekurziv	2-200 herë	1.5	24-bit, gri	po	2D
Fraktal	2-2000 herë	1000-10000	24-bit, gri	po	2.5D

“Zbatimi i algoritmeve

JPEG dhe JPEG2000 "

E përfunduar:

grupi nxënës 819

Dmitry Ugarov

Si funksionojnë JPEG dhe JPEG2000

1. Algoritmi JPEG

JPEG (Joint Photographic Experts Group) është një metodë e përdorur gjerësisht për ngjeshjen e imazheve fotografike. Formati i skedarit që përmban të dhëna të kompresuara zakonisht quhet edhe emri JPEG; shtesat më të zakonshme për skedarë të tillë janë .jpeg, .jfif, .jpg, .JPG ose .JPE. Nga këto, megjithatë, .jpg është zgjerimi më i popullarizuar në të gjitha platformat.

Algoritmi JPEG është një algoritëm kompresimi me humbje të cilësisë.

Zona e aplikimit

Formati është një format kompresimi me humbje, kështu që është e gabuar të supozohet se JPEG ruan të dhënat si 8 bit për kanal (24 bit për pixel). Nga ana tjetër, meqenëse të dhënat e kompresuara dhe të dekompresuara me JPEG zakonisht përfaqësohen në 8-bit për kanal, kjo terminologji përdoret ndonjëherë. Mbështetet gjithashtu kompresimi i imazheve në shkallë gri.

Kur ruani një skedar JPEG, mund të specifikoni nivelin e cilësisë dhe rrjedhimisht shkallën e kompresimit, e cila zakonisht vendoset në disa njësi arbitrare, për shembull, nga 1 në 100 ose nga 1 në 10. Sa më i lartë numri korrespondon me cilësinë më të mirë , por madhësia e skedarit rritet. Zakonisht, ndryshimi në cilësi midis 90 dhe 100 praktikisht nuk perceptohet nga syri. Duhet mbajtur mend se imazhi i rindërtuar pak nga pak është gjithmonë i ndryshëm nga origjinali. Një keqkuptim i zakonshëm është se cilësia JPEG është e njëjtë me sasinë e informacionit të ruajtur.

Hapat e kodimit

Procesi i kompresimit JPEG përfshin një numër hapash:

1. Konvertimi i imazhit në hapësirën optimale të ngjyrave;

Kur përdorni një hapësirë ngjyrash luma / chroma (YCbCr), arrihet raporti më i mirë i ngjeshjes. Në këtë fazë të kodimit, duke përdorur raportet e duhura, modeli i ngjyrave RGB konvertohet në YCbCr:

Y = 0,299 * R + 0,587 * G + 0,114 * B

Cb = - 0,1687 * R - 0,3313 * G + 0,5 * B

Cr = 0,5 * R - 0,4187 * G - 0,0813 * B.
Gjatë dekodimit, mund të përdorni transformimin e duhur të kundërt:
R = Y + 1,402 * Kr

G = Y - 0,34414 * Cb - 0,71414 * Cr

B = Y + 1,772 * Cb.
Një shënim që lidh Y, Cb, Cr në sistemin vizual të njeriut:

Syri, veçanërisht retina, ka dy lloje qelizash si analizues vizual: qelizat për shikimin e natës, të cilat perceptojnë vetëm nuancat e grisë (nga e bardha e ndezur në të zezën e errët) dhe qelizat e shikimit të ditës, të cilat perceptojnë një ngjyrosje. Qelizat e para që japin ngjyrën RGB shfaqin një nivel ndriçimi të ngjashëm me vlerën Y. Qelizat e tjera që janë përgjegjëse për perceptimin e nuancës përcaktojnë vlerën që lidhet me ndryshimin e kromës.

2. Nën-kampionimi i komponentëve të kromatikitetit sipas grupeve mesatare të pikselëve;

Shumica e informacionit vizual ndaj të cilit syri i njeriut është më i ndjeshëm përbëhet nga komponentë me frekuencë të lartë, në shkallë gri të ndriçimit (Y) të hapësirës së ngjyrave YCbCr. Dy komponentët e tjerë të krominancës (Cb dhe Cr) përmbajnë informacione ngjyrash me frekuencë të lartë ndaj të cilave syri i njeriut është më pak i ndjeshëm. Prandaj, një pjesë e tij mund të hidhet poshtë dhe, në këtë mënyrë, është e mundur të zvogëlohet numri i pikselëve të numëruar për kanalet kroma.

1) lloji 4: 2: 0 (kur imazhi ndahet në katrorë 2x2 pikselë dhe në secilën prej tyre të gjithë pikselët marrin të njëjtat vlera të kanaleve Cb dhe Cr, dhe shkëlqimi Y y mbetet për secilin)

2) lloji 4: 2: 2 (kombinimi sipas përbërësve të ngjyrave ndodh vetëm horizontalisht në grupe prej dy pikselësh).

3) Lloji 4: 4: 4 nënkupton që çdo piksel në secilën rresht ka vlerën e tij unike për komponentët Y, Cb dhe Cr. (Fig. 1 a)

4) lloji 4: 2: 2. Duke ulur kampionin e sinjalit chroma me një faktor 2 horizontalisht, marrim një rrymë YCbCr 4: 4: 4 nga një rrjedhë YCbCr 4: 2: 2. Rekordi "4: 2: 2" do të thotë që në një rresht të vetëm, për 2 vlera të kromaticitetit, ka 4 vlera të shkëlqimit (shih Fig. 1 b). Sinjali 4: 2: 2 YCbCr është shumë pak inferior në cilësinë e imazhit ndaj sinjalit 4: 4: 4 YCbCr, por gjerësia e brezit të kërkuar zvogëlohet me 33% të origjinalit.

3. Aplikimi i transformimeve diskrete të kosinusit për të reduktuar tepricën e të dhënave të imazhit;

Faza kryesore e algoritmit është transformimi diskret i kosinusit (DCT ose DCT), i cili është një lloj transformimi Furier. Përdoret kur punoni me imazhe për qëllime të ndryshme, jo vetëm për qëllime kompresimi. Kalimi në një paraqitje të frekuencës së vlerave të vlerave të pikselit ju lejon të shikoni imazhin në një mënyrë tjetër, ta përpunoni atë dhe, çfarë është interesante për ne, ta kompresoni atë. Për më tepër, duke ditur faktorët e konvertimit, ne gjithmonë mund të kryejmë veprimin e kundërt - të kthejmë imazhin origjinal.

DCT e aplikuar drejtpërdrejt në bllokun (në rastin tonë 8x8 piksele) të imazhit do të dukej kështu:

ku x, y - koordinatat hapësinore të pikselit (0..7),

f (x, y) - vlerat e pikselit të makrobllokut origjinal (le të themi ndriçimi)

u, v - koordinatat e pikselit në paraqitjen e frekuencës (0..7)

w (u) = 1 / SQRT (2) për u = 0, përndryshe w (u) = 1 (SQRT është rrënja katrore)

w (v) = 1 / SQRT (2) për v = 0, përndryshe w (v) = 1

Ose në formë matrice:

4. Kuantizimi i çdo blloku të koeficientëve DCT duke përdorur funksionet e peshës të optimizuara duke marrë parasysh perceptimin vizual të njeriut;

Transformimi i kosinusit diskret përgatit informacionin për kompresim dhe rrumbullakim me humbje. Për çdo element të matricës së transformuar, ekziston një element përkatës i matricës kuantizimi. Matrica që rezulton merret duke ndarë çdo element të matricës së transformuar me elementin përkatës të matricës së kuantizimit dhe më pas duke rrumbullakosur rezultatin në numrin e plotë më të afërt. Kur përpiloni një matricë kuantizimi, elementët e saj të mëdhenj janë në këndin e poshtëm të majtë, kështu që kur ndahen me to, të dhënat në këtë cep pas një transformimi kosinus diskret (vetëm ato, rrumbullakimi i të cilëve do të jetë më pak i dhimbshëm) do të rrumbullakoseshin më përafërsisht. Prandaj, informacioni i humbur është më pak i rëndësishëm për ne sesa informacioni i mbetur.

5. Faza e Kompresimit Sekondar

Faza e fundit e koduesit JPEG është kodimi i matricës që rezulton.

5.1 Permutacioni Zigzag i 64 Koeficientëve DCT

Pra, pasi kemi DCT në një bllok 8x8, kemi një bllok të ri 8x8. Pastaj, ky bllok 8x8 është zigzag si ky:

(Numrat në bllokun 8x8 tregojnë rendin në të cilin po shohim matricën 2-dimensionale 8x8)

0, 1, 5, 6,14,15,27,28,

2, 4, 7,13,16,26,29,42,

3, 8,12,17,25,30,41,43,

9,11,18,24,31,40,44,53,

10,19,23,32,39,45,52,54,

20,22,33,38,46,51,55,60,

21,34,37,47,50,56,59,61,

35,36,48,49,57,58,62,63

Siç mund ta shihni, së pari këndi i sipërm i majtë (0,0), pastaj vlera në (0,1), pastaj (1,0), pastaj (2,0), (1,1), (0,2 ), (0.3), (1.2), (2.1), (3.0) dhe të ngjashme.

Pasi të bëjmë zigzag matricën 8x8, tani kemi një vektor me 64 koeficientë (0..63) Kuptimi i këtij vektori zigzag është se ne shikojmë koeficientët 8x8 DCT sipas renditjes së rritjes së frekuencave hapësinore. Pra, marrim një vektor të renditur sipas kritereve të frekuencës hapësinore: vlera e parë në vektor (indeksi 0) korrespondon me frekuencën më të ulët në imazh - shënohet me termin DC. Me një rritje të indeksit në vektor, marrim vlerat që korrespondojnë me frekuencat më të larta (vlera me indeksin 63 korrespondon me amplituda e frekuencës më të lartë në bllokun 8x8). Pjesa tjetër e koeficientëve DCT referohen si AC.

5.2 Zerat e kodimit të gjatësisë së ekzekutimit (RLE)

Tani kemi një vektor me një sekuencë të gjatë zerosh. Ne mund ta shfrytëzojmë këtë duke koduar zero të njëpasnjëshme. E RËNDËSISHME: Do ta shihni më vonë pse, por këtu po anashkalojmë kodimin e koeficientit të parë të vektorit (koeficienti DC), i cili është i koduar ndryshe. Konsideroni vektorin origjinal 64 si një vektor 63 (ky është një vektor 64 pa koeficientin e parë)

Le të themi se kemi 57,45,0,0,0,0,23,0, -30, -16,0,0,1,0,0,0,0,0,0, vetëm 0, ... , 0

Ja se si bëhet kompresimi RLC JPEG për këtë shembull:

(0,57); (0.45); (4.23); (1, -30); (0, -16); (2.1); EOB

Siç mund ta shihni, ne kodojmë për secilën vlerë të ndryshme nga 0, numrin e zerove të njëpasnjëshme PRIORING përpara vlerës, pastaj shtojmë vlerën. Një tjetër shënim: EOB është një formë e shkurtër për Fundin e Bllokut, është një vlerë e veçantë e koduar (shënues). Nëse kemi arritur në një pozicion në një vektor nga i cili kemi vetëm zero vektoriale deri në fund, ne do ta nxjerrim atë pozicion me një EOB dhe do të plotësojmë kompresimin RLC të vektorit të kuantizuar.

[Vini re se nëse vektori i kuantizuar nuk përfundon me zero (elementi i fundit nuk është 0), nuk do të kemi një shënues EOB.]

(0,57); (0,45); (4,23); (1,-30); (0,-16); (2,1); (0,0)

Një gjë tjetër THEMELORE: Le të themi diku në një vektor të kuantizuar kemi:

57, tetëmbëdhjetë zero, 3, 0,0, 0,0 2, tridhjetë e tre zero, 895, EOB

Kodimi Huffman JPG bën kufizimin që numri i zerave kryesore duhet të kodohet si një vlerë 4-bit - nuk mund të kalojë 15.

Pra, shembulli i mëparshëm duhet të kodohet si:

(0,57); (15,0) (2,3); (4,2); (15,0) (15,0) (1,895), (0,0)

(15,0) është një vlerë e veçantë e koduar që tregon se çfarë pasohet nga 16 zero të njëpasnjëshme atje.

5.3 Hapi i fundit - Kodimi i Huffman

Shënim i RËNDËSISHËM fillimisht: Në vend që të ruajmë vlerën aktuale, standardi JPEG specifikon që ne ruajmë madhësinë minimale në bit në të cilat mund ta mbajmë atë vlerë (kjo quhet kategoria e asaj vlere) dhe më pas një paraqitje të koduar me bit të asaj vlere. si kjo:

7,..,-4,4,..,7 3 000,001,010,011,100,101,110,111

15,..,-8,8,..,15 4 0000,..,0111,1000,..,1111

31,..,-16,16,..,31 5 00000,..,01111,10000,..,11111

63,..,-32,32,..,63 6 .

127,..,-64,64,..,127 7 .

255,..,-128,128,..,255 8 .

511,..,-256,256,..,511 9 .

1023,..,-512,512,..,1023 10 .

2047,..,-1024,1024,..,2047 11 .

4095,..,-2048,2048,..,4095 12 .

8191,..,-4096,4096,..,8191 13 .

16383,..,-8192,8192,..,16383 14 .

32767,..,-16384,16384,..,32767 15 .

Më pas për shembullin e mëparshëm:

(0,57); (0,45); (4,23); (1,-30); (0,-8); (2,1); (0,0)

le të kodojmë vetëm vlerën e duhur të këtyre çifteve, me përjashtim të çifteve që janë shënues të veçantë si (0,0) ose (nëse duhet të kemi) (15,0)

45 gjithashtu do të kodohej si (6.101101)

30 -> (5,00001)

Dhe tani, ne do të shkruajmë përsëri rreshtin e çifteve:

(0,6), 111001; (0,6), 101101; (4,5), 10111; (1,5), 00001; (0,4), 0111; (2,1), 1; (0,0)

Çiftet e 2 vlerave, të mbyllura në kllapa, mund të përfaqësohen në një bajt, pasi në fakt secila nga 2 vlerat mund të përfaqësohet në një pjesë 4-bitësh (numëruesi i zerave të mëparshme është gjithmonë më i vogël se 15 dhe, si p.sh. kategoria [numrat e koduar në skedarin JPG - në zonën -32767..32767]). Në këtë bajt, feta e rendit të lartë përfaqëson numrin e zerot kryesore, dhe feta e rendit të ulët është kategoria e vlerës së re përveç 0.

Hapi i fundit i kodimit është që Huffman të bëhet ky bajt, dhe më pas të shkruhet skedari JPG si një bitstream i kodit Huffman të këtij bajt, i ndjekur nga përfaqësimi i bitit të atij numri.

Për shembull, për bajtin 6 (ekuivalent me (0.6)) kemi kodin Huffman = 111000;

21 = (1,5) - 11111110110

4 = (0,4) - 1011

33 = (2,1) - 11011

0 = EOB = (0,0) - 1010

Bitstream-i përfundimtar i regjistruar në skedarin JPG në disk për shembullin e mëparshëm është 63 koeficientë (mos harroni se kemi kapërcyer koeficientin e parë) -

111000 111001 111000 101101 1111111110011001 10111 11111110110 00001

1011 0111 11011 1 1010
Avantazhet dhe disavantazhet

Disavantazhet e formatit përfshijnë faktin se me raporte të forta kompresimi struktura e të dhënave të bllokut bëhet e ndjeshme, imazhi "ndahet në katrorë" (secila me një madhësi 8x8 piksele). Ky efekt është veçanërisht i dukshëm në zonat me frekuencë të ulët hapësinore (tranzicione të qetë të imazhit, për shembull, një qiell i pastër). Në zonat me frekuencë të lartë hapësinore (për shembull, skajet e kundërta të imazhit), shfaqen "artefakte" karakteristike - një strukturë e parregullt pikselësh me ngjyrë dhe / ose shkëlqim të shtrembëruar. Përveç kësaj, detajet e imëta të ngjyrave zhduken nga imazhi. Gjithashtu, mbani në mend se ky format nuk e mbështet transparencën.

Megjithatë, pavarësisht nga mangësitë e tij, JPEG është bërë shumë i përhapur për shkak të raportit të tij të lartë të kompresimit, në krahasim me alternativat ekzistuese në kohën e shfaqjes së tij.

2. Algoritmi JPEG2000

Algoritmi JPEG-2000 u zhvillua nga i njëjti grup ekspertësh të fotografisë si JPEG. Formimi i JPEG si standard ndërkombëtar përfundoi në vitin 1992. Në vitin 1997, u bë e qartë se nevojitej një standard i ri, më fleksibël dhe i fuqishëm, i cili u finalizua për dimrin e vitit 2000.

Dallimet kryesore midis algoritmit JPEG 2000 dhe algoritmit JPEG janë si më poshtë:

1) Cilësia më e mirë e imazhit me raport të lartë kompresimi. Ose, në mënyrë ekuivalente, një raport më i lartë kompresimi për të njëjtën cilësi për raportet e larta të kompresimit. Në fakt, kjo do të thotë një reduktim i dukshëm në madhësinë e grafikëve "web-quality" të përdorura nga shumica e sajteve.

2) Mbështetje për kodimin e zonave individuale me cilësi më të mirë. Dihet se zona të caktuara të një imazhi janë kritike për perceptimin njerëzor (për shembull, sytë në një fotografi), ndërsa cilësia e të tjerave mund të sakrifikohet (për shembull, sfondi). Me optimizimin "manual", raporti i kompresimit rritet derisa cilësia të humbasë në një pjesë të rëndësishme të imazhit. Tani bëhet e mundur vendosja e cilësisë në zonat kritike, duke ngjeshur më fort pjesën tjetër të zonave, d.m.th. marrim një raport kompresimi përfundimtar edhe më të lartë me cilësi imazhi subjektivisht të barabartë.

3) Algoritmi kryesor i kompresimit zëvendësohet me valëzues. Përveç rritjes së specifikuar të raportit të kompresimit, kjo na lejoi të heqim qafe bllokimin e 8 pikselëve që ndodh kur rritet raporti i kompresimit. Për më tepër, zhvillimi i qetë i imazhit tani është një standard (JPEG progresiv, i cili përdoret në mënyrë aktive në internet, u shfaq shumë më vonë se JPEG).

4) Për të rritur raportin e kompresimit, algoritmi përdor kompresimin aritmetik. Standardi origjinal JPEG përfshinte gjithashtu kompresimin aritmetik, por më vonë ai u zëvendësua nga kompresimi më pak efikas i Huffman sepse ngjeshja aritmetike mbrohej nga patentat. Tani patenta kryesore ka skaduar dhe ekziston një mundësi për të përmirësuar algoritmin.

5) Mbështet kompresimin pa humbje. Përveç kompresimit të zakonshëm me humbje, JPEG-i i ri tani do të mbështesë gjithashtu kompresimin pa humbje. Kështu, bëhet e mundur përdorimi i JPEG për kompresimin e imazheve mjekësore, në printim, duke ruajtur tekstin për sistemet e njohjes OCR, etj.

6) Mbështetje për kompresimin e imazheve me një bit (2 ngjyra). Për ruajtjen e imazheve me një bit (vizatime me bojë, tekst të skanuar, etj.), Më parë rekomandohej gjerësisht formati GIF, pasi kompresimi duke përdorur DCT është shumë i paefektshëm për imazhet me tranzicion të mprehtë të ngjyrave. Në JPEG, kur kompresohej, një fotografi 1-bit konvertohej në 8-bit, d.m.th. u rrit 8 herë, pas së cilës u bë një përpjekje për të ngjeshur, shpesh më pak se 8 herë. Tani mund të rekomandojmë JPEG 2000 si një algoritëm universal.

7) Në nivel formati, transparenca mbështetet. Tani do të jetë e mundur të mbivendosni pa probleme sfondin kur krijoni faqe WWW jo vetëm në GIF, por edhe në JPEG 2000. Përveç kësaj, nuk mbështetet vetëm 1 bit transparencë (një piksel është transparent / i errët), por një kanal i veçantë, e cila do t'ju lejojë të vendosni një tranzicion të qetë nga një imazh i errët në sfond transparent.

Përveç kësaj, në nivelin e formatit, përfshirja e informacionit të së drejtës së autorit në imazh mbështetet, mbështetje për elasticitetin ndaj gabimeve të bitit gjatë transmetimit dhe transmetimit, mund të kërkohen mjete të jashtme (plug-ins) për dekompresim ose përpunim, përshkrimi i tij, informacioni i kërkimit , etj mund të përfshihen në imazh. .d.

Hapat e kodimit

Procesi i kompresimit JPEG2000 përfshin një sërë hapash:

1. Konvertimi i imazhit në hapësirën optimale të ngjyrave.
Në këtë fazë të kodimit, duke përdorur raportet e duhura, modeli i ngjyrave RGB konvertohet në YUV:

Gjatë dekompresimit, aplikohet transformimi përkatës i anasjelltë:

2. Transformimi i valëzuar diskrete.

Transformimi i valëve diskrete (DWT) gjithashtu mund të jetë i dy llojeve - për rastin e kompresimit me humbje dhe për kompresimin pa humbje.

Në rastin njëdimensional, ky transformim është produkti me pika i koeficientëve përkatës dhe vargut të vlerave. Por që kur Meqenëse shumë koeficientë janë zero, transformimi i valëve të përparme dhe të kundërt mund të shkruhet me formulat e mëposhtme (për të transformuar elementët ekstremë të vargut, përdoret shtrirja e tij me 2 pikselë në çdo drejtim, vlerat e të cilave janë simetrike me vlerat e elementeve të vargut në lidhje me pikselët e tij ekstrem):
y (2 * n + 1) = x (2 * n + 1) - (int) (x (2 * n) + x (2 * n + 2)) / 2

y (2 * n) = x (2 * n) + (int) (y (2 * n - 1) + y (2 * n + 1) + 2) / 4

dhe anasjelltas

x (2 * n) = y (2 * n) - (int) (y (2 * n - 1) + y (2 * n + 1) + 2) / 4

x (2 * n + 1) = y (2 * n + 1) + (int) (x (2 * n) + x (2 * n + 2)) / 2.

3. Kuantizimi i koeficientëve.

Ashtu si me algoritmin JPEG, kuantizimi përdoret kur kodohet një imazh në formatin JPEG2000. Transformimi i valëzuar diskrete, si analogu i tij, rendit koeficientët sipas frekuencës. Por, ndryshe nga JPEG, në formatin e ri matrica e kuantizimit është një për të gjithë imazhin.

4. Faza sekondare e kompresimit

. Ashtu si me JPEG, në formatin e ri, hapi i fundit në algoritmin e kompresimit është kodimi pa humbje. Por, ndryshe nga formati i mëparshëm, JPEG2000 përdor një algoritëm aritmetik të kompresimit.

Implementimi i softuerit

Në këtë punim janë implementuar algoritmet JPEG dhe JPEG2000. Të dy algoritmet zbatojnë kodimin përpara dhe prapa (nuk ka fazë të fundit të kompresimit dytësor). Llogaritja JPEG kërkon një kohë mjaft të gjatë (rreth 30 sekonda) për shkak të llogaritjes "direkte" të DCT. Nëse keni nevojë për të rritur shpejtësinë e punës, fillimisht duhet të llogaritni matricën DCT (bëni ndryshime në klasën DCT).

Le të kalojmë në rishikimin e programit:

Pas nisjes, shfaqet një dritare ku

dhe mund ta ruani duke klikuar butonin (2) dhe duke futur emrin e dëshiruar në kutinë e dialogut.

Nëse Faktori i Cilësisë është mjaft i lartë, imazhi do të ndryshojë shumë. Nëse ky është një algoritëm JPEG, atëherë do të shqiptohen blloqe 8x8. (Në rastin e algoritmit JPEG2000, nuk do të ketë ndarje blloku)

Para:

Pas: