Phil 17 dhjetor 2013 në orën 14:09

Shpikja e JPEG

• Algoritmet,
• Përpunimi i imazhit

• Tutorial

Ju e kuptuat saktë nga titulli që ky nuk është një përshkrim shumë i zakonshëm i algoritmit JPEG (formatin e skedarit e kam përshkruar në detaje në artikull). Para së gjithash, metoda e zgjedhur e paraqitjes së materialit supozon se nuk dimë asgjë jo vetëm për JPEG, por edhe për transformimin Fourier dhe kodimin Huffman. Në përgjithësi, ne mbajmë mend pak nga ligjëratat. Ata sapo e morën fotografinë dhe filluan të mendojnë se si mund të kompresohej. Prandaj, u përpoqa të shpreh qartë vetëm thelbin, por në të cilin lexuesi do të zhvillojë një kuptim mjaft të thellë dhe, më e rëndësishmja, intuitiv i algoritmit. Formulat dhe llogaritjet matematikore - në minimum, vetëm ato që janë të rëndësishme për të kuptuar se çfarë po ndodh.

Njohja e algoritmit JPEG është shumë e dobishme jo vetëm për kompresimin e imazhit. Ai përdor teorinë nga përpunimi dixhital sinjalet, analizat matematikore, algjebra lineare, teoria e informacionit, në veçanti, transformimi i Furierit, kodimi pa humbje, etj. Prandaj, njohuritë e marra mund të jenë të dobishme kudo.

Nëse dëshironi, ju sugjeroj të kaloni të njëjtat hapa vetë paralelisht me artikullin. Kontrolloni sa i përshtatshëm është arsyetimi i mësipërm për imazhe të ndryshme, përpiquni të bëni modifikimet tuaja në algoritëm. Është shumë interesante. Si një mjet, unë mund të rekomandoj kombinimin e mrekullueshëm të Python + NumPy + Matplotlib + PIL (jastëk). Pothuajse e gjithë puna ime (përfshirë grafikën dhe animacionin) është bërë duke i përdorur ato.

Kujdes, trafik! Shumë ilustrime, grafikë dhe animacione (~ 10 Mb). Për ironi, në artikullin për JPEG ka vetëm 2 imazhe me këtë format nga pesëdhjetë.

Cilido qoftë algoritmi i kompresimit të informacionit, parimi i tij do të jetë gjithmonë i njëjtë - gjetja dhe përshkrimi i modeleve. Sa më shumë modele, aq më shumë tepricë, aq më pak informacion. Arkivuesit dhe koduesit zakonisht janë "të përshtatur" për një lloj specifik informacioni dhe dinë se ku mund ta gjejnë atë. Në disa raste, një model është menjëherë i dukshëm, siç është një fotografi e një qielli blu. Çdo rresht i paraqitjes së tij dixhitale mund të përshkruhet mjaft saktë nga një vijë e drejtë.

Ne do të stërvitemi me macet rakun. Imazhi gri i mësipërm është marrë si shembull. Kombinon mirë si zonat homogjene ashtu edhe ato të kundërta. Dhe nëse mësojmë të ngjeshim gri, atëherë nuk do të ketë probleme me ngjyrën.

Paraqitja vektoriale

Së pari, le të kontrollojmë se sa të varur janë dy pikselët fqinjë. Është logjike të supozohet se ka shumë të ngjarë që ato të jenë shumë të ngjashme. Le ta kontrollojmë këtë për të gjitha çiftet e imazheve. Le t'i shënojmë në planin koordinativ me pika në mënyrë që vlera e pikës përgjatë boshtit X të jetë vlera e pikselit të parë, dhe përgjatë boshtit Y - e dyta. Për imazhin tonë me përmasa 256 me 256, marrim 256*256/2 piksele:

Në mënyrë të parashikueshme, shumica e pikave janë të vendosura në ose afër vijës y=x (dhe ka edhe më shumë prej tyre sesa mund të shihen në figurë, pasi ato mbivendosen shumë herë me njëra-tjetrën dhe, për më tepër, janë të tejdukshme). Nëse po, do të ishte më e lehtë për të punuar duke i rrotulluar ato me 45°. Për ta bërë këtë, ju duhet t'i shprehni ato në një sistem tjetër koordinativ.

Vektorët bazë të sistemit të ri janë padyshim: . Ne jemi të detyruar të pjesëtojmë me rrënjën e dy për të marrë një sistem ortonormal (gjatësitë e vektorëve bazë janë të barabartë me një). Këtu tregojmë se një pikë p = (x, y) në sistemi i ri do të përfaqësohet si një pikë (a 0 , a 1). Duke ditur koeficientët e rinj, ne mund t'i marrim lehtësisht të vjetrit duke i kthyer ato. Natyrisht, koordinata e parë (e re) është mesatarja, dhe e dyta është diferenca e x dhe y (por e ndarë me rrënjën 2). Imagjinoni që ju kërkohet të lini vetëm njërën nga vlerat: ose 0 ose 1 (d.m.th., barazoni tjetrën me zero). Është më mirë të zgjidhni një 0, pasi vlera e një 1 ka shumë të ngjarë të jetë rreth zero. Kjo është ajo që ndodh nëse e rivendosim imazhin vetëm nga një 0:

Zmadhimi 4x:

Kjo ngjeshje nuk është shumë mbresëlënëse, për të qenë i sinqertë. Është më mirë që në mënyrë të ngjashme ta ndani imazhin në treshe pikselësh dhe t'i paraqisni ato në hapësirën tre-dimensionale.

Ky është i njëjti grafik, por me pika të ndryshme vizion. Vijat e kuqe janë akset që sugjerojnë veten. Ato korrespondojnë me vektorët: . Më lejoni t'ju kujtoj se ju duhet të pjesëtoni me disa konstante në mënyrë që gjatësitë e vektorëve të bëhen të barabartë me një. Kështu, duke u zgjeruar mbi këtë bazë, marrim 3 vlera a 0, një 1, një 2 dhe një 0 është më e rëndësishme se një 1 dhe një 1 është më e rëndësishme se një 2. Nëse hedhim një 2, atëherë grafiku do të "rrafshohet" në drejtim të vektorit e 2. Kjo fletë tashmë mjaft e hollë tre-dimensionale do të bëhet e sheshtë. Ai nuk do të humbasë aq shumë, por ne do të heqim qafe një të tretën e vlerave. Le të krahasojmë imazhet e rindërtuara nga treshe: (a 0 , 0, 0), (a 1 , a 2 , 0) dhe (a 0 , a 1 , a 2). Në versionin e fundit nuk hodhëm asgjë, kështu që do të marrim origjinalin.

Zmadhimi 4x:

Vizatimi i dytë tashmë është i mirë. Zonat e mprehta u zbutën pak, por në përgjithësi fotografia u ruajt shumë mirë. Dhe tani, le të ndajmë me katër në të njëjtën mënyrë dhe të përcaktojmë vizualisht bazën në hapësirën katër-dimensionale ... Oh, mirë, po. Por ju mund të merrni me mend se cili do të jetë një nga vektorët bazë: (1,1,1,1)/2. Prandaj, mund të shikohet projeksioni i hapësirës katër-dimensionale në hapësirën pingul me vektorin (1,1,1,1) për të identifikuar të tjerët. Por kjo nuk është mënyra më e mirë.
Qëllimi ynë është të mësojmë se si të transformojmë (x 0 , x 1 , ..., x n-1) në (a 0, a 1, ..., a n-1) në mënyrë që çdo vlerë e a të jetë më pak e rëndësishme se ato të mëparshmet. Nëse mund ta bëjmë këtë, atëherë ndoshta vlerat e fundit të sekuencës mund të hidhen fare. Eksperimentet e mësipërme lënë të kuptohet se është e mundur. Por nuk mund të bësh pa një aparat matematikor.
Pra, ne duhet t'i transformojmë pikat në një bazë të re. Por së pari ju duhet të gjeni një bazë të përshtatshme. Le të kthehemi te eksperimenti i parë i çiftëzimit. Le ta konsiderojmë atë në përgjithësi. Ne kemi përcaktuar vektorët bazë:

Ne e shprehëm vektorin përmes tyre fq:

ose në koordinata:

Për të gjetur një 0 dhe një 1 ju duhet të projektoni fq në e 0 dhe e 1 respektivisht. Dhe për këtë ju duhet të gjeni produktin skalar

i ngjashëm:

Në koordinata:

Shpesh është më i përshtatshëm për të kryer transformimin në formë matrice.

Pastaj A = EX dhe X = E T A. Kjo është një formë e bukur dhe e përshtatshme. Matrica E quhet matricë e transformimit dhe është ortogonale, do ta takojmë më vonë.

Kalimi nga vektorët në funksione.

Është i përshtatshëm për të punuar me vektorë të dimensioneve të vogla. Megjithatë, ne duam të gjejmë modele në blloqe më të mëdha, kështu që në vend të vektorëve N-dimensionale është më e përshtatshme të operojmë me sekuencat që përfaqësojnë imazhin. Sekuenca të tilla do t'i quaj funksione diskrete, pasi arsyetimi i mëposhtëm vlen edhe për funksionet e vazhdueshme.
Duke iu rikthyer shembullit tonë, imagjinoni një funksion f(i), i cili përcaktohet vetëm në dy pika: f(0)=x dhe f(1)=y. Le të vendosim në mënyrë të ngjashme funksionet bazë e 0 (i) dhe e 1 (i) bazuar në baza e 0 dhe e 1 . Ne marrim:

Ky është një përfundim shumë i rëndësishëm. Tani në shprehjen "zgjerimi i një vektori në vektorët ortonormalë" mund të zëvendësojmë fjalën "vektor" me "funksion" dhe të marrim shprehjen plotësisht të saktë "zgjerimi i një funksioni në funksionet ortonormale". Nuk ka rëndësi që kemi marrë një funksion kaq të shkurtër, pasi i njëjti arsyetim funksionon për një vektor N-dimensional, i cili mund të përfaqësohet si një funksion diskret me vlera N. Dhe puna me funksionet është më e qartë se sa me vektorët me dimensione N. Në të kundërt, ju mund të përfaqësoni një funksion të tillë si një vektor. Për më tepër, e zakonshme funksion të vazhdueshëm mund të paraqitet si një vektor me dimensione të pafundme, edhe pse jo në hapësirën Euklidiane, por në hapësirën Hilbert. Por ne nuk do të shkojmë atje; do të jemi të interesuar vetëm për funksione diskrete.
Dhe problemi ynë për të gjetur një bazë kthehet në problemin e gjetjes së një sistemi të përshtatshëm funksionesh ortonormale. Në arsyetimin e mëposhtëm, supozohet se ne kemi përcaktuar disi një grup funksionesh bazë, sipas të cilave do të zbërthehemi.
Le të themi se kemi një funksion (të përfaqësuar, për shembull, me vlera) që duam ta përfaqësojmë si një shumë të të tjerëve. Ju mund ta përfaqësoni këtë proces në formë vektoriale. Për të zbërthyer një funksion, duhet ta "projektoni" atë në funksionet bazë një nga një. Në kuptimin vektorial, llogaritja e projeksionit jep qasjen minimale të vektorit origjinal ndaj një tjetri për sa i përket distancës. Duke kujtuar se distanca llogaritet duke përdorur teoremën e Pitagorës, një paraqitje e ngjashme në formën e funksioneve jep përafrimin më të mirë të rrënjës mesatare katrore të një funksioni me një tjetër. Kështu, çdo koeficient (k) përcakton "afërsinë" e funksionit. Më formalisht, k*e(x) është përafrimi më i mirë i rrënjës mesatare katrore me f(x) midis l*e(x).
Shembulli i mëposhtëm tregon procesin e përafrimit të një funksioni duke përdorur vetëm dy pika. Në të djathtë është një paraqitje vektoriale.

Në lidhje me eksperimentin tonë të ndarjes në çifte, mund të themi se këto dy pika (0 dhe 1 përgjatë abshisës) janë një çift pikselësh fqinjë (x, y).
E njëjta gjë, por me animacion:

Nëse marrim 3 pikë, atëherë duhet të marrim parasysh vektorët tredimensionale, por përafrimi do të jetë më i saktë. Dhe për një funksion diskret me vlera N, duhet të merrni parasysh vektorët N-dimensionale.
Duke pasur një grup koeficientësh të marrë, mund të merrni lehtësisht funksion origjinal, duke përmbledhur funksionet bazë të marra me koeficientët përkatës. Analiza e këtyre koeficientëve mund të zbulojë shumë informacione të dobishme(në varësi të bazës). Një rast i veçantë i këtyre konsideratave është parimi i zgjerimit të serisë Fourier. Në fund të fundit, arsyetimi ynë është i zbatueshëm për çdo bazë, dhe kur zgjerohet në një seri Fourier, merret një krejtësisht specifik.

Transformimet diskrete të Furierit (DFT)

Në pjesën e mëparshme, arritëm në përfundimin se do të ishte mirë të zbërthehej një funksion në përbërësit e tij. Në fillim të shekullit të 19-të, Fourier gjithashtu mendoi për këtë. Vërtetë, ai nuk kishte një fotografi të një rakun, kështu që ai duhej të studionte shpërndarjen e nxehtësisë përgjatë unazës metalike. Pastaj zbuloi se është shumë e përshtatshme të shprehet temperatura (dhe ndryshimi i saj) në secilën pikë të unazës si një shumë e sinusoideve me periudha të ndryshme. "Fourier zbuloi (rekomandoj të lexoni, është interesante) se harmonika e dytë zbërthehet 4 herë më shpejt se e para dhe harmonikat e rendit më të lartë zbehen me një ritëm edhe më të shpejtë."
Në përgjithësi, shpejt doli që funksionet periodike mund të zbërthehen në mënyrë të përsosur në shumën e sinusoideve. Dhe meqenëse në natyrë ka shumë objekte dhe procese të përshkruara nga funksionet periodike, është shfaqur një mjet i fuqishëm për analizën e tyre.
Ndoshta një nga proceset periodike më vizuale është zëri.

• Grafiku i parë - ton i pastër me një frekuencë prej 2500 herc.
• 2 - zhurma e bardhë. Kjo do të thotë, zhurma me frekuenca të shpërndara në mënyrë të barabartë në të gjithë gamën.
• 3 - shuma e dy të parave.

Nëse do të më kishin dhënë vlerat e funksionit të fundit në atë moment kur nuk dija për seritë Fourier dhe do të më kërkonin t'i analizoja, atëherë patjetër do të isha hutuar dhe nuk do të kisha mundur të thoja asgjë me vlerë. Epo, po, një lloj funksioni, por si e kuptoni që ka diçka të porositur atje? Por sikur të kisha menduar të dëgjoja funksioni i fundit, atëherë veshi do të kapte një ton të pastër mes zhurmës. Edhe pse jo shumë i mirë, pasi gjatë gjenerimit kam zgjedhur posaçërisht parametra të tillë në mënyrë që në grafikun përmbledhës sinjali të shpërndahet vizualisht në zhurmë. Siç e kuptoj unë, ende nuk është e qartë se si e bën këtë një aparat dëgjimi. Sidoqoftë, kohët e fundit u bë e qartë se nuk e zbërthen tingullin në valë sinus. Ndoshta një ditë do të kuptojmë se si ndodh kjo dhe do të shfaqen algoritme më të avancuara. Epo, tani për tani ne po e bëjmë atë në mënyrën e vjetër.
Pse të mos provoni të përdorni sinusoidet si bazë? Në fakt, ne e kemi bërë tashmë këtë. Le të kujtojmë zbërthimin tonë në 3 vektorë bazë dhe t'i paraqesim në grafik:

Po, po, e di, duket si një rregullim, por me tre vektorë është e vështirë të presësh më shumë. Por tani është e qartë se si të merrni, për shembull, 8 vektorë bazë:


Jo mirë kontroll kompleks tregon se këta vektorë janë pingul në çift, d.m.th., ortogonal. Kjo do të thotë se ato mund të përdoren si bazë. Transformimi mbi një bazë të tillë është i njohur gjerësisht dhe quhet transformimi i kosinusit diskret (DCT). Unë mendoj se është e qartë nga grafikët e mësipërm se si është marrë formula e transformimit DCT:

Kjo është ende e njëjta formulë: A = EX me një bazë të zëvendësuar. Vektorët bazë të DCT të specifikuar (ata janë gjithashtu vektorë rreshtash të matricës E) janë ortogonalë, por jo ortonormalë. Kjo duhet mbajtur mend kur konvertim i anasjelltë(Nuk do të ndalem në këtë, por për ata që janë të interesuar, DCT inversi ka një term 0.5*a 0, ​​pasi vektori i bazës zero është më i madh se të tjerët).
Shembulli i mëposhtëm tregon procesin e përafrimit të nëntotaleve me vlerat origjinale. Në çdo përsëritje, baza tjetër shumëzohet me koeficientin tjetër dhe i shtohet shumës së ndërmjetme (d.m.th., njësoj si në eksperimentet e hershme në rakun - një e treta e vlerave, dy të tretat).

Por, megjithatë, përkundër disa argumenteve për këshillueshmërinë e zgjedhjes së një baze të tillë, ende nuk ka argumente reale. Në të vërtetë, ndryshe nga zëri, mundësia e zbërthimit të një imazhi në funksione periodike është shumë më pak e dukshme. Sidoqoftë, imazhi mund të jetë vërtet shumë i paparashikueshëm edhe në një zonë të vogël. Prandaj, fotografia është e ndarë në copa mjaft të vogla, por jo absolutisht të vogla, që dekompozimi të ketë kuptim. Në JPEG, imazhi "ndahet" në katrorë 8x8. Brenda një pjese të tillë, fotografitë janë zakonisht shumë uniforme: sfondi plus luhatje të vogla. Zona të tilla afrohen bukur nga sinusoidet.
Epo, le të themi se ky fakt është pak a shumë intuitiv. Por ka një ndjenjë të keqe për tranzicionet e papritura të ngjyrave, sepse ndryshimi i ngadaltë i funksioneve nuk do të na shpëtojë. Duhet të shtojmë funksione të ndryshme me frekuencë të lartë që bëjnë punën e tyre, por shfaqen anash në një sfond homogjen. Le të marrim një imazh 256x256 me dy zona të kundërta:

Le të zbërthejmë çdo rresht duke përdorur DCT, duke marrë kështu 256 koeficientë për rresht.
Pastaj ne lëmë vetëm koeficientët e parë n dhe vendosim pjesën tjetër në zero, dhe, për rrjedhojë, imazhi do të paraqitet si një shumë e vetëm harmonikëve të parë:

Numri në foto është numri i gjasave të mbetura. Në imazhin e parë, mbetet vetëm vlera mesatare. Në të dytin, tashmë është shtuar një sinusoid me frekuencë të ulët, etj. Meqë ra fjala, kushtojini vëmendje kufirit - pavarësisht nga përafrimi më i mirë, 2 vija janë qartë të dukshme pranë diagonales, njëra më e lehtë, tjetra më e errët. Një pjesë e imazhit të fundit është zmadhuar 4 herë:

Dhe në përgjithësi, nëse larg kufirit shohim një sfond uniform fillestar, atëherë kur i afrohemi, amplituda fillon të rritet, më në fund arrin një vlerë minimale dhe më pas befas bëhet maksimale. Ky fenomen njihet si efekti Gibbs.

Lartësia e këtyre gungave, të cilat shfaqen pranë ndërprerjeve të funksionit, nuk do të ulet me rritjen e numrit të përmbledhjeve të funksioneve. Në një transformim diskret ai zhduket vetëm kur ruhen pothuajse të gjithë koeficientët. Më saktësisht, ajo bëhet e padukshme.
Shembulli i mëposhtëm është plotësisht i ngjashëm me dekompozimin e mësipërm të trekëndëshave, por në një rakun të vërtetë:


Kur studiohet DCT, mund të krijohet përshtypja e rreme se vetëm koeficientët e parë (frekuencë të ulët) janë gjithmonë të mjaftueshëm. Kjo është e vërtetë për shumë fotografi, ato kuptimet e të cilave nuk ndryshojnë në mënyrë dramatike. Sidoqoftë, në kufirin e zonave të kundërta, vlerat do të "kërcejnë" shpejt dhe madje edhe koeficientët e fundit do të jenë të mëdhenj. Prandaj, kur dëgjoni për vetinë e ruajtjes së energjisë të DCT, merrni parasysh faktin se ai zbatohet për shumë lloje sinjalesh të hasura, por jo për të gjitha. Për shembull, mendoni se si do të dukej një funksion diskret, koeficientët e zgjerimit të të cilit janë të barabartë me zero, përveç atij të fundit. Këshillë: Mendoni për zbërthimin në formë vektoriale.
Megjithë mangësitë, baza e zgjedhur është një nga më të mirat në fotografitë reale. Do të shohim një krahasim të vogël me të tjerët pak më vonë.

DCT kundrejt gjithçkaje tjetër

Kur studiova çështjen e transformimeve ortogonale, për të qenë i sinqertë, nuk u binda shumë nga argumentet se gjithçka përreth është një shumë dridhjet harmonike, kështu që ju duhet t'i zbërtheni fotografitë në sinusoidë. Apo ndoshta disa funksione hapash do të ishin më të mira? Prandaj, kërkova rezultatet e hulumtimit mbi optimalitetin e DCT në imazhet reale. Fakti që "Është DCT që gjendet më shpesh në aplikime praktike për shkak të vetive të "ngjeshjes së energjisë"" shkruhet kudo. Kjo veti do të thotë që sasia maksimale e informacionit përmbahet në koeficientët e parë. Dhe pse? Nuk është e vështirë të bësh kërkime: ne armatosim veten me një mori fotografish të ndryshme, baza të ndryshme të njohura dhe fillojmë të llogarisim devijimin standard nga imazhi real për sasi të ndryshme koeficientët Gjeta një studim të vogël në një artikull (imazhe të përdorura) mbi këtë teknikë. Ai tregon grafikët e varësisë së energjisë së ruajtur nga numri i koeficientëve të parë të zgjerimit për baza të ndryshme. Nëse shikoni grafikët, ishit të bindur se DCT vazhdimisht zë një vend të nderuar... um... vendin e 3-të. Si keshtu? Çfarë lloj konvertimi KLT është ky? Unë po lavdëroja DCT, dhe më pas...

KLT

Të gjitha transformimet, përveç KLT-së, janë transformime me bazë konstante. Dhe në KLT (transformimi Karhunen-Loeve) llogaritet baza më optimale për disa vektorë. Ai llogaritet në atë mënyrë që koeficientët e parë të japin gabimin mesatar katror më të vogël në total për të gjithë vektorët. Ne kemi kryer më parë punë të ngjashme me dorë, duke përcaktuar vizualisht bazën. Në fillim duket si një ide e shëndoshë. Mund, për shembull, ta ndajmë imazhin në seksione të vogla dhe të llogarisim bazën e vet për secilën. Por jo vetëm që ekziston shqetësimi i ruajtjes së kësaj baze, por edhe operacioni i llogaritjes së saj është mjaft i mundimshëm. Por DCT humbet vetëm pak, dhe përveç kësaj, DCT ka algoritme të shpejta konvertimi.

DFT

DFT (Transformimi Diskret Furier) - transformim diskret Furieri. Nën këtë emër, nganjëherë përmendet jo vetëm një transformim specifik, por edhe e gjithë klasa e transformimeve diskrete (DCT, DST...). Le të shohim formulën DFT:

Siç mund ta merrni me mend, ky është një transformim ortogonal me një lloj baze komplekse. Që të tillë formë komplekse ndodh pak më shpesh se gjithmonë, ka kuptim të studiohet përfundimi i tij.
Mund të duket se çdo sinjal harmonik i pastër (me një frekuencë të plotë) me zbërthim DCT do të japë vetëm një koeficient jozero që korrespondon me këtë harmonik. Kjo nuk është e vërtetë, sepse përveç frekuencës, rëndësi ka edhe faza e këtij sinjali. Për shembull, zgjerimi i sinusit në kosinus (në mënyrë të ngjashme në zgjerimin diskret) do të jetë si ky:

Kaq shumë për harmonitë e pastra. Ajo pjelli një bandë të tjerë. Animacioni tregon koeficientët DCT të një vale sinus në faza të ndryshme.


Nëse ju dukej se kolonat po rrotulloheshin rreth një boshti, atëherë nuk ju dukej.
Kjo do të thotë se tani ne do ta zgjerojmë funksionin në shumën e sinusoideve jo vetëm të frekuencave të ndryshme, por edhe atyre të zhvendosura përgjatë një faze. Do të jetë më e përshtatshme të merret në konsideratë zhvendosja e fazës duke përdorur shembullin e kosinusit:

Një identitet i thjeshtë trigonometrik jep një rezultat të rëndësishëm: zhvendosja fazore zëvendësohet nga shuma e sinusit dhe kosinusit, marrë me koeficientët cos(b) dhe sin(b). Kjo do të thotë që funksionet mund të zgjerohen në shumën e sinuseve dhe kosinuseve (pa asnjë fazë). Kjo është një formë e zakonshme trigonometrike. Sidoqoftë, kompleksi përdoret shumë më shpesh. Për ta marrë atë duhet të përdorni formulën e Euler-it. Thjesht duke zëvendësuar formulat e derivateve për sinusin dhe kosinusin, marrim:


Tani për një ndryshim të vogël. Nënvizimi është numri i konjuguar.

Ne marrim barazinë përfundimtare:

c është një koeficient kompleks, pjesa reale e të cilit është e barabartë me koeficientin e kosinusit dhe pjesa imagjinare është e barabartë me koeficientin e sinusit. Dhe grupi i pikave (cos(b), sin(b)) është një rreth. Në një regjistrim të tillë, çdo harmonik hyn në zgjerim me një frekuencë pozitive dhe negative. Prandaj, në formula të ndryshme të analizës Furier, përmbledhja ose integrimi zakonisht ndodh nga minus në plus pafundësi. Shpesh është më i përshtatshëm për të kryer llogaritjet në këtë formë komplekse.
Transformimi zbërthen sinjalin në harmonikë me frekuenca nga një në N lëkundje në rajonin e sinjalit. Por shkalla e kampionimit është N për zonë sinjali. Dhe sipas teoremës së Kotelnikov (aka teorema Nyquist-Shannon), frekuenca e kampionimit duhet të jetë të paktën dyfishi i frekuencës së sinjalit. Nëse nuk është kështu, atëherë efekti është shfaqja e një sinjali me një frekuencë të rreme:

Vija me pika tregon sinjalin e rindërtuar gabimisht. Këtë fenomen e keni hasur shpesh në jetë. Për shembull, lëvizja qesharake e rrotave të makinës në një video, ose efekti moire.
Kjo çon në faktin se gjysma e dytë e amplitudave komplekse N duket se përbëhet nga frekuenca të tjera. Këto harmonike të rreme të gjysmës së dytë janë një pasqyrë e të parës dhe nuk përmbajnë informacion shtesë. Kështu, na mbeten kosinuset N/2 dhe sinuset N/2 (duke formuar një bazë ortogonale).
Mirë, ka një bazë. Përbërësit e tij janë harmonikë me një numër të plotë lëkundjesh në rajonin e sinjalit, që do të thotë se vlerat ekstreme të harmonikave janë të barabarta. Më saktësisht, ato janë pothuajse të barabarta, pasi vlera e fundit nuk merret tërësisht nga buza. Për më tepër, çdo harmonik është pothuajse pasqyrë simetrike në lidhje me qendrën e saj. Të gjitha këto dukuri janë veçanërisht të forta në frekuencave të ulëta, të cilat janë të rëndësishme për ne kur kodojmë. Kjo është gjithashtu e keqe sepse kufijtë e bllokut do të jenë të dukshëm në imazhin e ngjeshur. Më lejoni të ilustroj bazën DFT me N=8. 2 rreshtat e parë janë përbërës kosinus, të fundit janë sinus:

Kushtojini vëmendje paraqitjes së komponentëve të dyfishtë ndërsa frekuenca rritet.

Ju mund të mendoni mendërisht se si një sinjal, vlerat e të cilit zvogëlohen gradualisht vlera maksimale në fillim deri në minimum në fund. Një përafrim pak a shumë adekuat mund të bëhet vetëm nga harmonikët drejt fundit, gjë që nuk është shumë e madhe për ne. Figura në të majtë është një përafrim i një sinjali me një skaj. Në të djathtë - simetrike:


Gjërat janë jashtëzakonisht të këqija me të parën.
Pra, ndoshta ne mund ta bëjmë atë si në DCT - të zvogëlojmë frekuencat me 2 ose një numër tjetër herë, në mënyrë që numri i disa lëkundjeve të jetë i pjesshëm dhe kufijtë të jenë në faza të ndryshme? Atëherë komponentët do të jenë jo ortogonalë. Dhe nuk ka asgjë për të bërë për këtë.

DST

Po sikur të përdorim sinuset në vend të kosinuseve në DCT? Ne do të marrim Transformimin Diskret të Sinusit (DST). Por për detyrën tonë, të gjitha ato nuk janë interesante, pasi të dyja periudhat e plota dhe gjysma e sinuseve janë afër zeros në kufij. Kjo do të thotë, ne do të marrim afërsisht të njëjtin zbërthim të papërshtatshëm si ai i DFT.

Kthimi në DCT

Si është ai në kufi? Mirë. Ka antifaza dhe nuk ka zero.

Të gjitha të tjerat

Transformimet jo-Furiere. Nuk do ta përshkruaj.
WHT - matrica përbëhet vetëm nga komponentë hapash me vlera -1 dhe 1.
Haar është gjithashtu një transformim ortogonal i valëzimit.
Ato janë inferiore ndaj DCT, por janë më të lehta për t'u llogaritur.

Pra, ju lindi ideja që të krijoni transformimin tuaj. Mbaje mend këte:

1. Baza duhet të jetë ortogonale.
2. Me një bazë fikse, nuk mund ta mposhtni KLT për cilësinë e kompresimit. Ndërkohë, në fotografitë reale, DCT është pothuajse po aq i mirë.
3. Duke përdorur shembullin e DFT dhe DST, duhet të mbani mend për kufijtë.
4. Dhe mbani mend se DCT ka një avantazh tjetër të mirë - afër kufijve të përbërësve të tyre, derivatet janë të barabartë me zero, që do të thotë se kalimi midis blloqeve fqinje do të jetë mjaft i qetë.
5. Transformimet Furier kanë algoritme të shpejta me kompleksitet O(N*logN), në ndryshim nga llogaritja e drejtpërdrejtë: O(N 2).

Nuk do të jetë e lehtë, apo jo? Megjithatë, për disa lloje imazhesh është e mundur të zgjidhet një bazë më e mirë se ajo e DCT.

transformimet 2D

Tani le të përpiqemi të bëjmë një eksperiment të tillë. Le të marrim, për shembull, një pjesë të një imazhi.

Grafiku i tij 3D:

Le të kalojmë përmes DCT(N=32) përmes çdo rreshti:

Tani dua që ju të kaloni sytë nëpër secilën kolonë të koeficientëve që rezultojnë, domethënë nga lart poshtë. Mos harroni se qëllimi ynë është të lëmë sa më pak vlera, duke eliminuar ato që nuk janë të rëndësishme. Ju ndoshta keni marrë me mend se vlerat e secilës kolonë të koeficientëve që rezultojnë mund të zgjerohen saktësisht në të njëjtën mënyrë si vlerat e imazhit origjinal. Askush nuk na kufizon në zgjedhjen e një matrice transformimi ortogonal, por ne do ta bëjmë atë përsëri duke përdorur DCT(N=8):

Koeficienti (0.0) doli të ishte shumë i madh, kështu që zvogëlohet me 4 herë në grafik.
Pra, çfarë ndodhi?
Këndi i sipërm i majtë është koeficienti më domethënës i zgjerimit të koeficientëve më domethënës.
Këndi i poshtëm i majtë janë koeficientët më të parëndësishëm të zgjerimit të koeficientëve më domethënës.
Këndi i sipërm i djathtë është koeficientët më të rëndësishëm të zgjerimit të koeficientëve më të parëndësishëm.
Këndi i poshtëm djathtas janë koeficientët më të parëndësishëm të zgjerimit të koeficientëve më të parëndësishëm.
Është e qartë se rëndësia e koeficientëve zvogëlohet nëse lëvizni diagonalisht nga e majta e sipërme në të djathtën e poshtme. Cila është më e rëndësishme: (0, 7) apo (7, 0)? Madje çfarë nënkuptojnë?
Së pari, sipas rreshtave: A 0 = (EX T) T = XE T (transpozuar, pasi formula është A=EX për kolonat), pastaj sipas kolonave: A=EA 0 = EXE T . Nëse llogaritni me kujdes, merrni formulën:

Kështu, nëse një vektor zbërthehet në sinusoidë, atëherë matrica zbërthehet në funksione të formës cos(ax)*cos(by). Çdo bllok 8x8 në JPEG përfaqësohet si një shumë e 64 funksioneve të formës:


Në Wikipedia dhe burime të tjera, funksione të tilla paraqiten në një formë më të përshtatshme:

Prandaj, koeficientët (0, 7) ose (7, 0) janë po aq të dobishëm.
Sidoqoftë, në fakt ky është një zbërthim i zakonshëm njëdimensional në 64 baza 64-dimensionale. E gjithë sa më sipër vlen jo vetëm për DCT, por edhe për çdo dekompozim ortogonal. Duke vazhduar me analogji, në rastin e përgjithshëm marrim një transformim ortogonal N-dimensionale.
Dhe këtu është një transformim 2D i një rakun (DCT 256x256). Përsëri me vlerat e rivendosura në zero. Numrat - numri i koeficientëve jozero nga të gjithë (më së shumti vlera të rëndësishme, e vendosur në zonën trekëndore në të majtë këndi i sipërm).

Mos harroni se koeficienti (0, 0) quhet DC, 63 të mbetur quhen AC.

Zgjedhja e një madhësie blloku

Një mik pyet pse JPEG përdor ndarjen 8x8. Nga përgjigja e votuar kundër:

DCT e trajton bllokun sikur të ishte periodik dhe duhet të rindërtojë kërcimin që rezulton në kufij. Nëse merrni blloqe 64x64, me shumë mundësi do të keni një kërcim të madh në kufij dhe do t'ju nevojiten shumë komponentë me frekuencë të lartë për ta rindërtuar atë në një saktësi të kënaqshme

Për shembull, DCT funksionon mirë vetëm në funksione periodike, dhe nëse ecni i madh, ka të ngjarë të keni një kërcim gjigant në kufijtë e bllokut dhe të keni nevojë për shumë komponentë me frekuencë të lartë për ta mbuluar atë. Kjo nuk eshte e vertete! Ky shpjegim është shumë i ngjashëm me DFT, por jo me DCT, pasi mbulon në mënyrë të përsosur kërcime të tilla me komponentët e parë.
Në të njëjtën faqe është një përgjigje nga FAQ MPEG, me argumentet kryesore kundër blloqeve të mëdha:

• Pak fitim kur ndahet në blloqe të mëdha.
• Rritja e kompleksitetit llogaritës.
• Probabilitet i lartë i një numri të madh kufijsh të mprehtë në një bllok, i cili do të shkaktojë efektin Gibbs.

Unë ju sugjeroj ta hulumtoni vetë këtë. Le të fillojmë me së pari.


Boshti horizontal tregon pjesën e koeficientëve të parë jozero. Vertikale - devijimi standard i pikselëve nga origjinali. Devijimi maksimal i mundshëm merret si një. Sigurisht, një foto nuk mjafton qartë për një vendim. Për më tepër, unë nuk po veproj plotësisht si duhet, thjesht po rivendos në zero. Në një JPEG real, në varësi të matricës së kuantizimit, vetëm vlerat e vogla të komponentëve me frekuencë të lartë zeroohen. Prandaj, eksperimentet dhe përfundimet e mëposhtme synojnë të nxjerrin në sipërfaqe parimet dhe modelet.
Ju mund ta krahasoni ndarjen në blloqe të ndryshme me 25 përqind të koeficientëve majtas (nga e majta në të djathtë, pastaj nga e djathta në të majtë):

Blloqet e mëdha nuk tregohen, pasi ato vizualisht pothuajse nuk dallohen nga 32x32. Tani le të shohim ndryshimin absolut me imazhin origjinal (përforcuar me 2 herë, përndryshe asgjë nuk është vërtet e dukshme):

8x8 jep rezultate më të mira se 4x4. Një rritje e mëtejshme në madhësi nuk ofron më një avantazh qartësisht të dukshëm. Edhe pse do ta konsideroja seriozisht 16x16 në vend të 8x8: rritja e kompleksitetit me 33% (më shumë për kompleksitetin në paragrafin tjetër) jep një përmirësim të vogël, por ende të dukshëm për të njëjtin numër koeficientësh. Sidoqoftë, zgjedhja e 8x8 duket mjaft e arsyeshme dhe mund të jetë mesatarja e artë. JPEG u botua në vitin 1991. Mendoj se një kompresim i tillë ishte shumë i vështirë për procesorët e asaj kohe.

Së dyti argument. Një gjë që duhet mbajtur parasysh është se rritja e madhësisë së bllokut do të kërkojë më shumë llogaritje. Le të vlerësojmë se sa. Kompleksiteti i konvertimit, siç e dimë mjaft mirë tashmë: O(N 2), pasi çdo koeficient përbëhet nga N terma. Por në praktikë përdoret algoritmi efikas transformimi i shpejtë i Furierit (FFT, Fast Fourier Transform, FFT). Përshkrimi i tij është përtej qëllimit të këtij artikulli. Kompleksiteti i tij: O(N*logN). Për një zgjerim dydimensional duhet ta përdorni dy herë N herë. Pra, kompleksiteti i DCT 2D është O(N 2 logN). Tani le të krahasojmë kompleksitetin e llogaritjes së një imazhi me një bllok dhe disa të vegjël:

• Një bllok (kN)x(kN): O((kN) 2 log(kN)) = O(k 2 N 2 log(kN))
• k*k blloqe N*N: O(k 2 N 2 logN)

Kjo do të thotë që, për shembull, llogaritja për një ndarje 64x64 është dy herë më komplekse se një ndarje 8x8.

Së treti argument. Nëse kemi në imazh kufi i mprehtë ngjyrat, kjo do të ndikojë në të gjithë bllokun. Ndoshta do të ishte më mirë që ky bllok të ishte mjaft i vogël, sepse në shumë blloqe fqinje ndoshta nuk do të ketë më një kufi të tillë. Megjithatë, larg kufijve, zbutja ndodh mjaft shpejt. Përveç kësaj, vetë kufiri do të duket më mirë. Le të kontrollojmë shembullin me sasi e madhe tranzicionet e kontrastit, përsëri, me vetëm një të katërtën e koeficientëve:


Megjithëse shtrembërimi i blloqeve 16x16 shtrihet më tej se ai i 8x8, shkronjat janë më të buta. Prandaj, vetëm dy argumentet e para më bindën. Por disi më pëlqen më shumë divizioni 16x16.

Kuantizimi

Në këtë pikë kemi një grup matricash 8x8 me koeficientë të transformimit të kosinusit. Është koha për të hequr qafe koeficientët e parëndësishëm. Ekziston një zgjidhje më elegante sesa thjesht rivendosja e koeficientëve të fundit në zero, siç bëmë më sipër. Ne nuk jemi të kënaqur me këtë metodë, pasi vlerat jo-zero ruhen me saktësi të tepruar, dhe midis atyre që ishin të pafat mund të ketë edhe mjaft të rëndësishme. Zgjidhja është përdorimi i një matrice kuantizimi. Humbjet ndodhin pikërisht në këtë fazë. Çdo koeficient Furier pjesëtohet me numrin përkatës në matricën e kuantizimit. Le të shohim një shembull. Le të marrim bllokun e parë nga rakun tonë dhe të kryejmë kuantizimin. Specifikimi JPEG ofron një matricë standarde:


Matrica standarde korrespondon me 50% cilësi në FastStone dhe IrfanView. Kjo tabelë u zgjodh për sa i përket ekuilibrit midis cilësisë dhe raportit të ngjeshjes. Unë mendoj se vlera për koeficientin DC është më e madhe se sa fqinjët e saj për faktin se DCT nuk është normalizuar dhe vlera e parë është më e madhe se sa duhet. Koeficientët e frekuencës së lartë janë ashpërsuar më fort për shkak të rëndësisë së tyre më të ulët. Unë mendoj se matrica të tilla përdoren rrallë tani, pasi përkeqësimi i cilësisë është qartë i dukshëm. Askush nuk e ndalon përdorimin e tabelës tuaj (me vlera nga 1 në 255)
Gjatë dekodimit, ndodh procesi i kundërt - koeficientët e kuantizuar shumëzohen term pas termi me vlerat e matricës së kuantizimit. Por meqenëse i rrumbullakuam vlerat, nuk do të jemi në gjendje të rivendosim me saktësi koeficientët origjinalë të Furierit. Sa më i madh të jetë numri i kuantizimit, aq më i madh është gabimi. Kështu, koeficienti i rindërtuar është vetëm shumëfishi më i afërt.
Një shembull tjetër:

Dhe për ëmbëlsirë, merrni parasysh cilësinë 5% (kur kodoni në Fast Stone).


Kur e rivendosim këtë bllok, do të marrim vetëm vlerën mesatare plus gradientin vertikal (për shkak të vlerës së ruajtur prej -1). Por vetëm dy vlera ruhen për të: 7 dhe -1. Situata nuk është më e mirë me blloqet e tjera, këtu është fotografia e restauruar:

Nga rruga, rreth 100% cilësi. Siç mund ta merrni me mend, në këtë rast matrica e kuantizimit përbëhet tërësisht nga njësi, domethënë, nuk ndodh kuantizimi. Megjithatë, për shkak të rrumbullakimit të koeficientëve në numrin e plotë më të afërt, ne nuk mund të rivendosim saktë imazhin origjinal. Për shembull, rakun mbajti saktësisht 96% të pikselëve, por 4% ishin të fikur me 1/256. Natyrisht, "shtrembërime" të tilla nuk mund të vërehen vizualisht.
Ose mund të shikoni matricat e kuantizimit të kamerave të ndryshme.

Kodimi

Përpara se të vazhdojmë, duhet të përdorim shembuj më të thjeshtë për të kuptuar se si mund të kompresojmë vlerat që rezultojnë.

Shembulli 0(për ngrohje)
Imagjinoni një situatë të tillë që shoku juaj ka harruar një copë letër me një listë në shtëpinë tuaj dhe tani ju kërkon ta diktoni atë përmes telefonit (nuk ka metoda të tjera komunikimi).
Listë:

• d9rg3
• wfr43gt
• wfr43gt
• d9rg3
• d9rg3
• d9rg3
• wfr43gt
• d9rg3

Si do ta lehtësoni detyrën tuaj? Ju nuk keni ndonjë dëshirë të veçantë për të diktuar me dhimbje të gjitha këto fjalë. Por janë vetëm dy prej tyre dhe ato përsëriten. Prandaj, ju thjesht disi diktoni dy fjalët e para dhe pranoni që tani e tutje do të quani "d9rg3" fjalën e parë dhe "wfr43gt" të dytën. Atëherë do të jetë e mjaftueshme për të diktuar: 1, 2, 2, 1, 1, 1, 2, 1.

Ne do të shënojmë fjalë të tilla si A, B, C... dhe do t'i quajmë simbole. Për më tepër, çdo gjë mund të fshihet nën simbolin: një shkronjë e alfabetit, një fjalë ose një hipopotam në kopshtin zoologjik. Gjëja kryesore është që simbolet identike korrespondojnë me koncepte identike, dhe ato të ndryshme korrespondojnë me ato të ndryshme. Meqenëse detyra jonë është kodimi (kompresimi) efikas, ne do të punojmë me bit, pasi këto janë njësitë më të vogla të paraqitjes së informacionit. Prandaj, le ta shkruajmë listën si ABBAAABA. Në vend të "fjalës së parë" dhe "fjalës së dytë", mund të përdoren bitet 0 dhe 1. Më pas ABBAAABA kodohet si 01100010 (8 bit = 1 bajt).

Shembulli 1
Kodoni ABC.
3 m personazhe të ndryshme(A, B, C) nuk mund të krahasohet në asnjë mënyrë 2 vlerat e mundshme bit (0 dhe 1). Dhe nëse po, atëherë mund të përdorni 2 bit për simbol. Për shembull:

• A: 00
• B:01
• C: 10

Sekuenca e biteve të lidhur me një simbol do të quhet kod. ABC do të kodohet si kjo: 000110.

Shembulli 2
Kodoni AAAAAABC.
Përdorimi i 2 bit për karakterin A duket pak i kotë. Po sikur të provoni këtë:

• C: 00

Sekuenca e koduar: 000000100.
Natyrisht, ky opsion nuk është i përshtatshëm, pasi nuk është e qartë se si të deshifrohen dy bitet e para të kësaj sekuence: si AA apo si C? Është shumë e kotë të përdorësh ndonjë ndarës midis kodeve, ne do të mendojmë se si ta kapërcejmë këtë pengesë në një mënyrë tjetër. Pra, dështimi është për faktin se kodi i C fillon me kodin e A. Por ne jemi të vendosur të kodojmë A me një bit, edhe nëse B dhe C kanë nga dy. Bazuar në këtë dëshirë, ne i japim A-së kodin 0. Atëherë kodet B dhe C nuk mund të fillojnë me 0. Por ato mund të fillojnë me 1:

• B: 10
• C: 11

Sekuenca është e koduar si kjo: 0000001011. Mundohuni ta deshifroni mendërisht. Ju mund ta bëni këtë vetëm në një mënyrë.
Ne kemi zhvilluar dy kërkesa për kodim:

1. Sa më e madhe të jetë pesha e një simboli, aq më i shkurtër duhet të jetë kodi i tij. Dhe anasjelltas.
2. Për dekodim të paqartë, një kod karakteri nuk mund të fillojë me kodin e ndonjë karakteri tjetër.

Natyrisht, rendi i personazheve nuk është i rëndësishëm, ne jemi të interesuar vetëm për shpeshtësinë e shfaqjes së tyre. Prandaj, çdo simbol shoqërohet me një numër të quajtur peshë. Pesha e një simboli mund të jetë ose një vlerë relative, që pasqyron proporcionin e shfaqjes së tij, ose një vlerë absolute, e barabartë me numrin e karaktereve. Gjëja kryesore është që peshat janë proporcionale me shfaqjen e simboleve.

Shembulli 3
Le të shqyrtojmë rastin e përgjithshëm për 4 simbole me çdo peshë.

• A: pa
• B: pb
• C: pc
• D: pd

Pa humbur përgjithësinë, le të vendosim pa ≥ pb ≥ pc ≥ pd. Ekzistojnë vetëm dy opsione që janë thelbësisht të ndryshme në gjatësinë e kodit:


Cila është e preferueshme? Për ta bërë këtë, ju duhet të llogarisni gjatësinë që rezulton e mesazheve të koduara:
W1 = 2*pa + 2*pb + 2*pc + 2*pd
W2 = pa + 2 * pb + 3 * pc + 3 * pd
Nëse W1 është më pak se W2 (W1-W2<0), то лучше использовать первый вариант:
W1-W2 = pa - (pc+pd)< 0 =>pa< pc+pd.
Nëse C dhe D së bashku ndodhin më shpesh se të tjerët, atëherë kulmi i tyre i përbashkët merr kodin më të shkurtër një-bit. Përndryshe, një bit shkon te karakteri A. Kjo do të thotë se bashkimi i karaktereve sillet si një karakter i pavarur dhe ka një peshë të barabartë me shumën e karaktereve hyrëse.
Në përgjithësi, nëse p është pesha e një karakteri të përfaqësuar nga fraksioni i shfaqjes së tij (nga 0 në 1), atëherë gjatësia më e mirë e kodit është s=-log 2 p.
Le të shohim këtë rast i thjeshtë(është e lehtë ta imagjinosh atë në formën e një peme). Pra, duhet të kodojmë 2 s karaktere me pesha të barabarta (1/2 s). Për shkak të barazisë së peshave, gjatësia e kodit do të jetë e njëjtë. Çdo karakter do të kërkojë bit s. Kjo do të thotë që nëse pesha e një simboli është 1/2 s, atëherë gjatësia e tij është s. Nëse e zëvendësojmë peshën me p, marrim gjatësinë e kodit s=-log 2 p. Kjo do të thotë që nëse një karakter shfaqet dy herë më shpesh se një tjetër, atëherë gjatësia e kodit të tij do të jetë një bit më e gjatë. Sidoqoftë, ky përfundim është i lehtë për t'u nxjerrë nëse mbani mend se shtimi i një biti ju lejon të dyfishoni numrin e opsioneve të mundshme.
Dhe një vëzhgim tjetër - dy simbolet me peshën më të vogël kanë gjithmonë më të madhin, por gjatësi të barabarta kodet Për më tepër, pjesët e tyre, përveç të fundit, janë të njëjta. Nëse kjo nuk do të ishte e vërtetë, atëherë të paktën një kod mund të shkurtohej me 1 bit pa thyer prefiksin. Kjo do të thotë se dy simbolet me peshën më të vogël në pema e kodit kanë një prind të përbashkët në një nivel më të lartë. Ju mund ta shihni këtë në shembullin C dhe D më lart.

Shembulli 4
Le të përpiqemi të zgjidhim shembulli tjetër, bazuar në përfundimet e marra në shembullin e mëparshëm.

1. Të gjitha simbolet janë renditur në rend zbritës të peshave.
2. Dy simbolet e fundit kombinohen në një grup. Këtij grupi i caktohet një peshë e barabartë me shumën e peshave të këtyre elementeve. Ky grup merr pjesë në algoritëm së bashku me simbolet dhe grupet e tjera.

Hapat përsëriten derisa të mbetet vetëm një grup. Brenda secilit grup, një karakteri (ose nëngrupi) i është caktuar biti 0 dhe një tjetër biti i karakterit 1.
Ky algoritëm quhet kodim Huffman.
Ilustrimi tregon një shembull me 5 karaktere (A: 8, B: 6, C: 5, D: 4, E: 3). Në të djathtë është pesha e simbolit (ose grupit).

Ne kodojmë koeficientët

Le të kthehemi. Tani kemi shumë blloqe me 64 koeficientë në secilin, të cilët duhet të ruhen disi. Zgjidhja më e thjeshtë është përdorimi i një numri fiks të biteve për koeficient - padyshim i pasuksesshëm. Le të ndërtojmë një histogram të të gjitha vlerave të marra (d.m.th., varësia e numrit të koeficientëve nga vlera e tyre):

Ju lutemi vini re - shkalla është logaritmike! A mund të shpjegoni arsyen e shfaqjes së një grupi vlerash që i kalojnë 200? Këta janë koeficientë DC. Meqenëse ato janë shumë të ndryshme nga të tjerët, nuk është për t'u habitur që ato janë të koduara veçmas. Këtu është vetëm DC:

Vini re se forma e grafikut të kujton grafikët nga eksperimentet më të hershme të çiftimit dhe trefishimit të pikselëve.
Në përgjithësi, vlerat e koeficientit DC mund të ndryshojnë nga 0 në 2047 (më saktë nga -1024 në 1023, pasi JPEG zbret 128 nga të gjitha vlerat origjinale, që korrespondon me zbritjen e 1024 nga DC) dhe shpërndahet mjaft në mënyrë të barabartë me maja të vogla. Pra, kodimi i Huffman nuk do të ndihmojë shumë këtu. Dhe imagjinoni sa e madhe do të jetë pema e kodimit! Dhe gjatë dekodimit do të duhet të kërkoni kuptime në të. Është shumë e shtrenjtë. Mendojmë më tej.
Koeficienti DC është vlera mesatare e një blloku 8x8. Le të imagjinojmë një tranzicion gradient (megjithëse jo ideal), i cili shpesh gjendet në fotografi. Vetë vlerat DC do të jenë të ndryshme, por ato do të përfaqësojnë një progresion aritmetik. Kjo do të thotë se ndryshimi i tyre do të jetë pak a shumë konstant. Le të ndërtojmë një histogram të dallimeve:

Kjo është më mirë, sepse vlerat përgjithësisht përqendrohen rreth zeros (por algoritmi Huffman përsëri do të japë një pemë shumë të madhe). Vlerat e vogla (nga vlere absolute) janë të zakonshme, të mëdha janë të rralla. Dhe meqenëse vlerat e vogla marrin pak bit (nëse hiqen zerat kryesore), një nga rregullat e ngjeshjes ndiqet mirë: simboleve me pesha të mëdha u caktohen kode të shkurtra (dhe anasjelltas). Aktualisht jemi të kufizuar nga mospërputhja me një rregull tjetër: pamundësia e dekodimit të qartë. Në përgjithësi, ky problem është zgjidhur në mënyrat e mëposhtme: shqetësoni me kodin ndarës, specifikoni gjatësinë e kodit, përdorni kodet e parashtesave(ju tashmë i njihni ato - ky është rasti kur asnjë kod nuk fillon me tjetrin). Le të shkojmë me opsionin e dytë të thjeshtë, d.m.th., çdo koeficient (më saktë, ndryshimi midis atyre fqinjëve) do të shkruhet kështu: (gjatësia) (vlera), sipas kësaj shenje:

Kjo do të thotë, vlerat pozitive kodohen drejtpërdrejt nga përfaqësimi i tyre binar, dhe vlerat negative kodohen në të njëjtën mënyrë, por me 1 kryesore të zëvendësuar me 0. Mbetet të vendoset se si të kodohen gjatësitë. Meqenëse ka 12 vlera të mundshme, 4 bit mund të përdoren për të ruajtur gjatësinë. Por këtu është më mirë të përdorni kodimin Huffman.

Ka më shumë vlera me gjatësi 4 dhe 6, kështu që ata morën kodet më të shkurtra (00 dhe 01).

Mund të lindë pyetja: pse, në shembull, vlera 9 ka kodin 1111110 dhe jo 1111111? Në fund të fundit, a mund ta ngrini me siguri "9" në një nivel më të lartë, pranë "0"? Fakti është se në JPEG nuk mund të përdorni një kod që përbëhet vetëm nga një - një kod i tillë është i rezervuar.
Ekziston edhe një veçori tjetër. Kodet e marra nga algoritmi i përshkruar Huffman mund të mos përkojnë në bit me kodet në JPEG, megjithëse gjatësia e tyre do të jetë e njëjtë. Duke përdorur algoritmin Huffman, përftohen gjatësitë e kodeve dhe gjenerohen vetë kodet (algoritmi është i thjeshtë - filloni me kode të shkurtra dhe shtoni ato një nga një në pemë sa më larg majtas të jetë e mundur, duke ruajtur vetinë e prefiksit ). Për shembull, për pemën e mësipërme lista ruhet: 0,2,3,1,1,1,1,1. Dhe, natyrisht, ruhet një listë vlerash: 4,6,3,5,7,2,8,1,0,9. Gjatë dekodimit, kodet gjenerohen në të njëjtën mënyrë.

Tani gjithçka është në rregull. Ne kuptuam se si ruhen DC-të:
[Kodi Huffman për gjatësinë e ndryshimit DC (në bit)]
ku ndryshim DC = rrymë DC - DC e mëparshme

Le të shikojmë AC:

Meqenëse grafiku është shumë i ngjashëm me grafikun për diferencat DC, parimi është i njëjtë: [Kodi Huffman për gjatësinë AC (në bit)]. Por jo në të vërtetë! Meqenëse shkalla në grafik është logaritmike, kjo nuk vërehet menjëherë vlera zero afërsisht 10 herë më e madhe se vlerat 2, e radhës më e shpeshta. Kjo është e kuptueshme - jo të gjithë i mbijetuan kuantizimit. Le të kthehemi te matrica e vlerave të marra gjatë fazës së kuantizimit (duke përdorur matricën e kuantizimit FastStone, 90%).

Meqenëse ka shumë grupe zerosh të njëpasnjëshme, lind një ide - të shënohet vetëm numri i zerave në grup. Ky algoritëm kompresimi quhet RLE (Run-length encoding). Mbetet për të zbuluar drejtimin e anashkalimit të atyre "të njëpasnjëshme" - kush qëndron pas kujt? Shkrimi nga e majta në të djathtë dhe nga lart poshtë nuk është shumë efektiv, pasi koeficientët jo zero janë të përqendruar pranë këndit të sipërm të majtë, dhe sa më afër djathtas poshtë, aq më shumë zero.

Prandaj, JPEG përdor një urdhër të quajtur "Zig-zag", i cili tregohet në figurën e majtë. Kjo metodë dallon mirë grupet e zerove. Në foton e duhur - mënyrë alternative bypass, jo i lidhur me JPEG, por me një emër kurioz (provë). Mund të përdoret në MPEG për kompresim të ndërthurur të videos. Zgjedhja e algoritmit të kalimit nuk ndikon në cilësinë e imazhit, por mund të rrisë numrin e grupeve të koduara të zeros, gjë që përfundimisht mund të ndikojë në madhësinë e skedarit.
Le të modifikojmë hyrjen tonë. Për çdo koeficient AC jo zero:
[Numri i zeros para AC][Kodi Huffman për gjatësinë AC (në bit)]
Unë mendoj se ju mund të kuptoni menjëherë se numri i zerave është gjithashtu i koduar në mënyrë të përsosur nga Huffman! Kjo është një përgjigje shumë e afërt dhe e mirë. Por mund të optimizohet pak. Imagjinoni që kemi një koeficient AC, para të cilit kishte 7 zero (sigurisht, nëse shkruhej në një rend zigzag). Këto zero janë fryma e vlerave që nuk i mbijetuan kuantizimit. Me shumë mundësi, edhe koeficienti ynë është dëmtuar shumë dhe është bërë i vogël, që do të thotë se gjatësia e tij është e shkurtër. Kjo do të thotë se numri i zerove përpara AC dhe gjatësia e AC janë sasi të varura. Prandaj e shkruajmë kështu:
[Kodi Huffman për (Numri i zerave para AC, gjatësia e AC (në bit)]
Algoritmi i kodimit mbetet i njëjtë: ato çifte (numri i zerave para AC, gjatësia e AC) që ndodhin shpesh do të marrin kode të shkurtra dhe anasjelltas.

Ne ndërtojmë një histogram të varësisë së sasisë për këto çifte dhe një pemë Huffman.


"Krashta e malit" e gjatë konfirmon supozimin tonë.

Karakteristikat e zbatimit në JPEG:
Një çift i tillë merr 1 bajt: 4 bit për numrin e zerove dhe 4 bit për gjatësinë e AC. 4 bit janë vlera nga 0 në 15. Për gjatësinë e AC kjo është më se e mjaftueshme, por a mund të ketë më shumë se 15 zero? Pastaj përdoren më shumë çifte. Për shembull, për 20 zero: (15, 0) (5, AC). Kjo do të thotë, zeroja e 16-të është e koduar si një koeficient jo zero. Meqenëse ka gjithmonë shumë zero afër fundit të bllokut, çifti (0,0) përdoret pas koeficientit të fundit jozero. Nëse haset gjatë dekodimit, atëherë vlerat e mbetura janë 0.

Ne zbuluam se çdo bllok është i koduar dhe i ruajtur në një skedar si ky:
[Kodi Huffman për gjatësinë e ndryshimit DC]
[Kodi Huffman për (numri i zerave para AC 1, gjatësia e AC 1]
…
[Kodi Huffman për (numri i zerave para AC n, gjatësia e AC n]
Ku AC i janë koeficientë AC jo zero.

Imazhi me ngjyra

Mënyra se si paraqitet një imazh me ngjyra varet nga përzgjedhja model ngjyrash. Një zgjidhje e thjeshtë është përdorimi i RGB dhe kodimi i secilit kanal ngjyrash të imazhit veç e veç. Atëherë kodimi nuk do të jetë i ndryshëm nga kodimi i një imazhi gri, vetëm 3 herë më shumë punë. Por kompresimi i imazhit mund të rritet nëse kujtojmë se syri është më i ndjeshëm ndaj ndryshimeve të shkëlqimit sesa ngjyrave. Kjo do të thotë që ngjyra mund të ruhet me humbje më të mëdha se shkëlqimi. RGB nuk ka një kanal të veçantë ndriçimi. Varet nga shuma e vlerave të secilit kanal. Prandaj, kubi RGB (kjo është një paraqitje e të gjitha vlerave të mundshme) thjesht "vendoset" në diagonale - sa më i lartë, aq më i ndritshëm. Por ata nuk ndalen këtu - kubi shtypet pak nga anët, dhe rezulton më shumë si një paralelipiped, por kjo është vetëm për të marrë parasysh tiparet e syrit. Për shembull, është më e ndjeshme ndaj jeshiles sesa blu. Kështu u shfaq modeli YCbCr.

(Imazhi nga Intel.com)
Y është komponenti i ndriçimit, Cb dhe Cr janë komponentët e ndryshimit të ngjyrave blu dhe të kuqe. Prandaj, nëse duan të kompresojnë më shumë imazhin, atëherë RGB konvertohet në YCbCr dhe kanalet Cb dhe Cr hollohen. Kjo do të thotë, ato ndahen në blloqe të vogla, për shembull 2x2, 4x2, 1x2, dhe të gjitha vlerat e një blloku janë mesatare. Ose, me fjalë të tjera, ata zvogëlojnë madhësinë e imazhit për këtë kanal me 2 ose 4 herë vertikalisht dhe/ose horizontalisht.

Çdo bllok 8x8 është i koduar (DCT + Huffman), dhe sekuencat e koduara shkruhen në këtë renditje:

Shtë kureshtare që specifikimi JPEG nuk kufizon zgjedhjen e modelit, domethënë, zbatimi i koduesit mund ta ndajë në mënyrë arbitrare imazhin në përbërës me ngjyra (kanale) dhe secila do të ruhet veçmas. Jam i vetëdijshëm për përdorimin e Grayscale (1 kanal), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). Tre të parat mbështeten pothuajse nga të gjithë, por ka probleme me 4-kanalet e fundit. FastStone, GIMP i mbështesin në mënyrë korrekte dhe programet standarde të Windows, paint.net nxjerrin saktë të gjithë informacionin, por më pas hidhni kanalin e 4-të të zi, prandaj (ai tha që nuk e hedhin, lexoni komentet e tij) tregoni më shumë imazh i lehtë. Në të majtë është një YCbCr JPEG klasik, në të djathtë është një CMYK JPEG:



Nëse ato ndryshojnë në ngjyrë, ose vetëm një fotografi është e dukshme, atëherë ka shumë të ngjarë që ju keni IE (ndonjë version) (UPD. në komente thonë "ose Safari"). Mund të provoni ta hapni artikullin në shfletues të ndryshëm.

Dhe një gjë tjetër

Me pak fjalë për veçoritë shtesë.

Mënyra progresive

Le t'i zbërthejmë tabelat rezultuese të koeficientëve DCT në shumën e tabelave (përafërsisht si kjo (DC, -19, -22, 2, 1) = (DC, 0, 0, 0, 0) + (0, -20 , -20, 0, 0) + (0, 1, -2, 2, 1)). Së pari, kodojmë të gjithë termat e parë (siç kemi mësuar tashmë: Huffman dhe traversal zigzag), pastaj të dytin, etj. Ky truk është i dobishëm kur interneti është i ngadaltë, pasi së pari ngarkohen vetëm koeficientët DC, të cilët përdoren për të ndërtoni një fotografi të përafërt me 8x8 “pikselë”. Pastaj rrumbullakosni koeficientët AC për të përmirësuar figurën. Pastaj korrigjimet e përafërta të tyre, pastaj ato më të sakta. Dhe kështu me radhë. Koeficientët janë të rrumbullakosur, pasi në fazat e hershme të ngarkimit saktësia nuk është aq e rëndësishme, por rrumbullakimi ka një efekt pozitiv në gjatësinë e kodeve, pasi çdo fazë përdor tabelën e vet Huffman.

Modaliteti pa humbje

Kompresim pa humbje. Nuk ka DCT. Përdoret parashikimi i pikës së 4-të bazuar në tre fqinjë. Gabimet e parashikimit janë të koduara nga Huffman. Për mendimin tim, përdoret pak më shpesh se kurrë.

Mënyra hierarkike

Nga imazhi krijohen disa shtresa me rezolucione të ndryshme. Shtresa e parë e trashë kodohet si zakonisht, dhe më pas vetëm ndryshimi (përsosja e imazhit) midis shtresave (pretendohet të jetë një valë valësh Haar). DCT ose Lossless përdoret për kodim. Sipas mendimit tim, përdoret pak më rrallë se kurrë.

Kodimi aritmetik

Algoritmi Huffman prodhon kode optimale bazuar në peshën e karaktereve, por kjo është e vërtetë vetëm për një hartim fiks nga karakteri në kod. Aritmetika nuk ka një lidhje kaq të ngurtë, e cila lejon përdorimin e kodeve sikur me një numër të pjesshëm të biteve. Ai pretendon se zvogëlon madhësinë e skedarit me një mesatare prej 10% në krahasim me Huffman. Jo i përhapur për shkak të çështjeve të patentave, nuk mbështetet nga të gjithë.

Shpresoj që tani ta kuptoni algoritmin JPEG në mënyrë intuitive. Faleminderit per leximin!

UPD
sugjeruar duke treguar softuerin e përdorur. Kam kënaqësinë të njoftoj se gjithçka është në dispozicion dhe falas:

• Python + NumPy + Matplotlib + PIL (jastëk). Mjeti kryesor. E gjeta duke kërkuar për "Matlab alternativë pa pagesë". Unë rekomandoj! Edhe nëse nuk jeni të njohur me Python, në vetëm disa orë do të mësoni se si të bëni llogaritjet dhe të ndërtoni grafikë të bukur.
• JpegSnoop. Tregon informacion të detajuar në lidhje me skedarin jpeg.
• yEd. Redaktori i grafikut.
• Inkscape. Kam bërë ilustrime në të, të tilla si një shembull i algoritmit Huffman. Kam lexuar disa mësime, doli të ishte shumë e lezetshme.
• Redaktori i Ekuacionit Daum. po kërkoja redaktues vizual formula, pasi nuk jam shumë miqësor me lateksin. Daum Equation është një shtojcë për Chrome që e pashë shumë të përshtatshme. Përveç goditjes së miut, ju mund të modifikoni Latex.
• FastStone. Unë mendoj se nuk ka nevojë ta prezantoj atë.
• PicPick. Alternativë falas SnagIt. Ai ulet në tabaka, merr një pamje të ekranit të asaj që thonë dhe ku e thonë. Plus të gjitha llojet e të mirave, të tilla si vizore, pipeta, raportues, etj.

Etiketa:

• jpeg
• dct
• dft
• Furieri
• huffman

Shto etiketa

Zona e aplikimit

Algoritmi JPEG më e përshtatshme për ngjeshjen e fotografive dhe pikturave që përmbajnë skena realiste me tranzicione të qetë shkëlqimin dhe ngjyrën. JPEG është më i përhapur 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 kontrastet e mprehta midis pikselëve ngjitur çojnë në artefakte të dukshme. Këshillohet që të ruani imazhe të tilla në formate pa humbje si TIFF, GIF ose PNG.

JPEG (si metodat e tjera të kompresimit të shtrembërimit) nuk është i përshtatshëm për kompresimin e imazheve gjatë përpunimit me shumë faza, pasi shtrembërimet do të futen në imazhe sa herë që ruhen rezultatet e përpunimit të ndërmjetëm.

JPEG nuk duhet të përdoret në rastet kur edhe humbjet minimale janë të 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, megjithatë, nuk mbështetet nga kodekët më të njohur) ose standardi i kompresimit JPEG-LS.

Kompresimi

Kompresimi konverton imazhin nga hapësira e ngjyrave 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 (Formati i shkëmbimit të skedarëve JPEG, i propozuar në 1991 nga specialistë nga C-Cube Microsystems, dhe i cili tani është bërë një standard de facto) përfshin përdorimin e konvertimit RGB->YCbCr.

Pas konvertimit RGB->YCbCr, për kanalet e imazhit Cb dhe Cr, të cilat janë përgjegjëse për ngjyrën, mund të kryhet "nën-kampionimi", i cili konsiston në caktimin e vlerave mesatare të Cb dhe Cr (skema e hollimit "4:2:0 ”). Për më tepër, 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 secila). Nëse vendosen kërkesa të shtuara për cilësinë e imazhit të rivendosur pas ngjeshjes, rrallimi mund të kryhet vetëm në një drejtim - vertikalisht (skema "4:4:0") ose horizontalisht ("4:2:2"), ose nuk kryhet fare (“4:4:4”).

Standardi gjithashtu lejon decimation me mesataren e Cb dhe Cr jo për një bllok 2x2, por për katër piksel të vendosur në mënyrë sekuenciale (vertikalisht ose horizontalisht), domethënë për blloqet 1x4, 4x1 (skema "4:1:1"), gjithashtu. si 2x4 dhe 4x2 (skema "4:1:0"). Është gjithashtu e mundur të përdoren lloje të ndryshme të rrallimit për Cb dhe Cr, por në praktikë skema të tilla përdoren jashtëzakonisht rrallë.

Më pas, komponenti i shkëlqimit Y dhe komponentët e ngjyrave Cb dhe Cr ndahen në blloqe prej 8x8 pikselësh. Çdo bllok i tillë i nënshtrohet një transformimi kosinus diskret (DCT). Koeficientët e DCT që rezultojnë janë të kuantizuar (matrica të ndryshme kuantizimi përdoren përgjithësisht për Y, Cb dhe Cr) dhe paketohen duke përdorur kodimin run dhe Huffman. Standardi JPEG lejon gjithashtu përdorimin e kodimit aritmetik shumë 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), përdoret rrallë në praktikë. Versionet më të fundit të bibliotekës së njohur libjpeg përfshijnë mbështetje për kodimi aritmetik, por shikimi i imazheve të ngjeshura duke përdorur këtë metodë mund të jetë problematik sepse shumë shikues nuk e mbështesin dekodimin e tyre.

Matricat e përdorura për kuantizimin e koeficientëve 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'i nënshtrohen kuantizimit më të fortë se ato me frekuencë të ulët. Kjo rezulton në ashpërsimin e detajeve të vogla në imazh. Sa më i lartë të jetë raporti i ngjeshjes, aq më fort kuantizohen të gjithë koeficientët.

Kur ruani një imazh si skedar JPEG, një parametër cilësie specifikohet 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 cilësi më të mirë (dhe madhësi më të madhe skedar i ngjeshur). Megjithatë, edhe kur përdorni cilësi më të 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ë e kufizuar të zbatimit të DCT, ashtu edhe me nevojën për të rrumbullakosur vlerat e Y, Cb, Koeficientët Cr dhe DCT në numrin e plotë më të afërt. Modaliteti i kompresimit JPEG pa humbje, i cili nuk përdor DCT, ofron përputhje e saktë imazhet e restauruara 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 pa humbje.

Varietetet e skemave të kompresimit JPEG

Standardi JPEG ofron dy mënyra kryesore për të paraqitur të dhënat e koduara.

Më e zakonshme, e mbështetur nga shumica e kodekëve të disponueshëm, është paraqitja sekuenciale e të dhënave JPEG, e cila përfshin kalimin sekuencial të bllokut të imazhit të koduar nga blloku nga e majta në të djathtë, nga lart poshtë. Operacionet e përshkruara më sipër kryhen në çdo bllok të koduar të imazhit, dhe rezultatet e kodimit vendosen në rrjedhën e daljes në formën e një "skanimi" të vetëm, domethënë një grup të dhënash të koduara që korrespondojnë me kalimin vijues ("skanuar") imazh. Mënyra kryesore ose "bazë" e kodimit lejon vetëm këtë paraqitje. Modaliteti i zgjeruar, së bashku me modalitetin vijues, gjithashtu lejon përfaqësimin progresiv të të dhënave JPEG.

Në rastin e JPEG progresiv, të dhënat e kompresuara shkruhen në rrjedhën e daljes si një grup skanimesh, secila prej të cilave përshkruan të gjithë imazhin me një shkallë në rritje të detajeve. Kjo arrihet ose duke regjistruar në çdo skanim jo grupin e plotë të koeficientëve DCT, por vetëm disa pjesë të tyre: së pari - ato me frekuencë të ulët, në skanimet e mëvonshme - ato me frekuencë të lartë (metoda e "zgjedhjes spektrale", d.m.th. mostrat spektrale), ose me anë të njëpasnjëshme, nga skanimi në skanim, rafinimi i koeficientëve të DCT (metoda e "përafrimit të njëpasnjëshëm", domethënë përafrimet e njëpasnjëshme). Ky përfaqësim progresiv i të dhënave është veçanërisht i dobishëm gjatë transmetimit 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 pas transmetimit të një pjese të vogël të skedarit JPEG.

Të dy skemat e përshkruara (si JPEG vijuese ashtu edhe progresive) bazohen në DCT dhe në thelb nuk lejojnë marrjen e një imazhi të rindërtuar 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, domethënë "pa humbje", JPEG), duke garantuar një përputhje të plotë, bit-për-bit, të origjinalit. dhe imazhet e restauruara. 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 është në kërkesë. Raporte dukshëm më të larta të kompresimit mund të merren duke përdorur metodën e ngjeshjes JPEG-LS, e cila, pavarësisht ngjashmërisë në emra, nuk lidhet drejtpërdrejt me standardin JPEG ISO/IEC 10918-1 (Rekomandimi ITU T.81), i përshkruar nga ISO/ Standardi IEC 14495-1 (Rekomandimi ITU T.87).

Sintaksa dhe struktura

Skedari JPEG përmban sekuencën shënues, secila prej të cilave fillon me bajt 0xFF, që tregon fillimin e shënuesit dhe një bajt identifikues. 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 bajtet e fillimit të shënuesi, domethënë 0xFF dhe identifikuesi) dhe vetë të dhënat. Kjo strukturë skedari ju lejon të gjeni shpejt një shënues me të dhënat e nevojshme (për shembull, gjatësia e rreshtit, numri i linjave dhe numri i përbërësve të ngjyrave të imazhit të ngjeshur).

Shënuesit bazë JPEG

Shënues	Bajt	Gjatësia	Qëllimi	Komentet
KËSHTU UNË	0xFFD8	Nr	Fillimi i imazhit
SOF0	0xFFC0	madhësi e ndryshueshme	Fillimi i kornizës (bazë, DCT)	Tregon që imazhi është koduar në modalitetin bazë duke përdorur kodin DCT dhe Huffman. Shënuesi përmban numrin e linjave dhe gjatësinë e linjës së imazhit (fusha me dy bajtë me zhvendosje 5 dhe 7 në lidhje me fillimin e shënuesit, përkatësisht), numrin e komponentëve (fusha bajt me zhvendosje 8 në lidhje me fillimin i shënuesit), numri i biteve për komponent (fusha e bajtit me zhvendosje 4 në lidhje me fillimin e shënuesit), si dhe raporti i komponentëve (për shembull, 4:2:0).
SOF1	0xFFC1	madhësi e ndryshueshme	Fillimi i kornizës (i zgjatur, DCT, kodi Huffman)	Tregon që imazhi është koduar në modalitetin e zgjeruar duke përdorur kodin DCT dhe Huffman. Shënuesi përmban numrin e rreshtave dhe gjatësinë e rreshtit të figurës, numrin e komponentëve, numrin e biteve për komponent dhe raportin e komponentit (për shembull, 4:2:0).
SOF2	0xFFC2	madhësi e ndryshueshme	Fillimi i kornizës (progresive, DCT, kodi Huffman)	Tregon që imazhi është koduar në modalitetin progresiv duke përdorur kodin DCT dhe Huffman. Shënuesi përmban numrin e rreshtave dhe gjatësinë e rreshtit të figurës, numrin e komponentëve, numrin e biteve për komponent dhe raportin e komponentit (për shembull, 4:2:0).
DHT	0xFFC4	madhësi e ndryshueshme	Përmban tabela Huffman	Përcakton një ose më shumë tabela Huffman.
DQT	0xFFDB	madhësi e ndryshueshme	Përmban tabela kuantizimi	Përcakton një ose më shumë tabela kuantizimi.
DRI	0xFFDD	4 bajt	Përcakton intervalin e përsëritjes	Vendos intervalin midis shënuesve RST n në makroblloqe.
SOS	0xFFDA	madhësi e ndryshueshme	Filloni skanimin	Fillimi i skanimit të parë ose të ardhshëm të një imazhi me drejtimin e kalimit nga e majta në të djathtë nga lart poshtë. Nëse është përdorur modaliteti bazë i kodimit, përdoret një skanim. Kur përdorni mënyra progresive, përdoren skanime të shumta. Shënuesi SOS është ndarësi midis pjesëve informative (titullit) dhe të koduar (në fakt të dhëna të ngjeshura) të imazhit.
RST n	0xFFD n	Nr	Rifillo, fillo përsëri	Futur në çdo r makroblloku, ku r- Intervali i rinisjes së shënuesit DRI. Nuk përdoret nëse nuk ka shënues DRI. n, 3 bit të ulët të shënuesit të kodit, ciklet nga 0 në 7.
APP n	0xFFE n	madhësi e ndryshueshme	Vendosur nga aplikacioni	Për shembull, EXIF ​​i një skedari JPEG përdor shënuesin APP1 për të ruajtur meta të dhënat e rregulluara në një strukturë të bazuar në TIFF.
COM	0xFFFE	madhësi e ndryshueshme	Një koment	Përmban tekstin e komentit.
EOI	0xFFD9	Nr	Fundi i pjesës së koduar të figurës.

Avantazhet dhe disavantazhet

Disavantazhet e kompresimit sipas standardit JPEG përfshijnë shfaqjen e objekteve karakteristike në imazhet e restauruara me ritme të larta kompresimi: imazhi shpërndahet në blloqe prej 8x8 pikselësh (ky efekt është veçanërisht i dukshëm në zonat e imazhit me ndryshime të buta në shkëlqim), në zona me frekuencë të lartë hapësinore (për shembull, konturet e kontrastit dhe kufijtë e imazhit), artefaktet shfaqen në formën e aureolëve të zhurmës. Duhet të theksohet se standardi JPEG (ISO/IEC 10918-1, Shtojca K, pika K.8) parashikon përdorimin e filtrave specialë për të shtypur artefaktet bllokuese, por në praktikë filtra të tillë, pavarësisht efikasitetit të tyre të lartë, praktikisht nuk janë të përdorura. Megjithatë, pavarësisht nga mangësitë e tij, JPEG është bërë shumë i përhapur për shkak të raportit të kompresimit mjaft të lartë (në raport me alternativat që ekzistonin në kohën e shfaqjes së tij), mbështetjes për kompresimin e imazheve me ngjyra të plota dhe kompleksitetit relativisht të ulët llogaritës.

Performanca e kompresimit JPEG

Për të shpejtuar procesin e kompresimit sipas standardit JPEG, tradicionalisht përdoret paralelizimi i llogaritjeve, veçanërisht kur llogaritet DCT. Historikisht, një nga përpjekjet e para për të shpejtuar procesin e kompresimit duke përdorur këtë qasje përshkruhet në një punim të botuar në 1993 nga Kasperovich dhe Babkin, i cili propozoi një përafrim origjinal të DCT që bën të mundur paralelizimin efikas të llogaritjeve duke përdorur 32-bit për qëllime të përgjithshme. regjistrat Procesorët Intel 80386. Më produktive u shfaqën më vonë qarqet kompjuterike përdorur zgjerime SIMD të grupit të instruksioneve të procesorëve x86. Shumë rezultatet më të mira bëjnë të mundur arritjen e skemave që përdorin aftësitë llogaritëse të përshpejtuesve grafikë (teknologjitë NVIDIA CUDA dhe AMD FireStream) për të organizuar llogaritjet paralele jo vetëm të DCT, por edhe të fazave të tjera. Kompresimi JPEG(konvertimi i hapësirës së ngjyrave, niveli i ekzekutimit, kodimi statistikor, etj.), dhe për çdo bllok 8x8 të imazhit të koduar ose të dekoduar. Artikulli ishte për herë të parë [ burimi?] paraqet një implementim të paralelizimit të të gjitha fazave të algoritmit JPEG duke përdorur teknologjinë CUDA, i cili përshpejtoi ndjeshëm performancën e kompresimit dhe dekodimit duke përdorur standardin JPEG.

Në vitin 2010, shkencëtarët nga projekti PLANETS vendosën udhëzimet për leximin e formatit JPEG në një kapsulë të veçantë, e cila u vendos në një bunker të veçantë në Alpet zvicerane. Kjo u bë me synimin për të ruajtur për pasardhësit informacionin rreth formateve dixhitale të njohura në fillim të shekullit të 21-të.

Shiko gjithashtu

Shënime

Lidhjet

• Specifikimi JFIF 1.02 (skedar teksti)
• Optimizimi JPEG. Pjesa 1, Pjesa 2, Pjesa 3.

Zona e aplikimit

Formati është një format kompresimi me humbje, prandaj është e gabuar të mendohet se JPEG ruan të dhëna si 8 bit për kanal (24 bit për pixel). Nga ana tjetër, meqenëse të dhënat e ngjeshura dhe të dekompresuara JPEG zakonisht përfaqësohen në 8 bit për format kanali, kjo terminologji përdoret ndonjëherë. Mbështetet gjithashtu kompresimi i imazheve gjysmëtonale bardh e zi.

Kur ruani një skedar JPEG, mund të specifikoni shkallën e cilësisë, dhe rrjedhimisht shkallën e kompresimit, e cila zakonisht specifikohet në disa njësi konvencionale, për shembull, nga 1 në 100 ose nga 1 në 10. Një numër më i madh korrespondon me cilësi më të mirë , por madhësia e skedarit rritet. Zakonisht, ndryshimi në cilësi midis 90 dhe 100 praktikisht nuk perceptohet me sy. Ju lutemi mbani mend se një imazh i restauruar nga formati JPEG nuk është një kopje të saktë origjinale. Një keqkuptim i zakonshëm është se cilësi JPEG identike me pjesën e informacionit të ruajtur.

Mbështetja e përhapur për formatin JPEG nga softuer të ndryshëm shpesh çon në kodimin JPEG të imazheve që nuk ishin të destinuara për atë qëllim - pa ndonjë përfitim në kompresim në krahasim me PNG ose GIF të bërë siç duhet, por me pasoja fatkeqe për cilësinë. Për shembull, një përpjekje për të regjistruar një imazh në JPEG që përmban detaje të vogla kontrasti (veçanërisht ato me ngjyra) do të çojë në shfaqjen e objekteve karakteristike, qartësisht të dukshme edhe në një "nivel cilësor" të lartë.

Kompresimi

Kompresimi konverton imazhin nga hapësira e ngjyrave 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ërsëdrejti në RGB), por specifikimi JFIF (JPEG File Interchange Format, i propozuar në 1991 nga specialistë nga C-Cube Microsystems, dhe i cili tani është bërë një standard de facto) përfshin përdorimin e konvertimit RGB->YCbCr.

Pas konvertimit RGB->YCbCr, për kanalet e imazhit Cb dhe Cr, të cilat janë përgjegjëse për ngjyrën, mund të kryhet "nën-kampionimi", i cili konsiston në faktin se çdo bllok prej 4 pikselësh (2x2) i kanalit të ndriçimit Y është caktuar. vlerat mesatare të Cb dhe Cr (skema e rrallimit "4:2:0". Në këtë rast, 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ë mesatare Cb dhe Cr). Nëse cilësia e kompresimit të imazhit të rindërtuar ka kërkesa të rritura, rrallimi mund të kryhet vetëm në një drejtim - vertikalisht (skema "4:4:0") ose horizontalisht ("4:2 :2"), ose nuk kryhet fare ("4: 4:4").

Standardi gjithashtu lejon përcaktimin me mesataren e Cb dhe Cr jo për një bllok 2x2, por për katër piksel të vendosur në mënyrë sekuenciale (vertikalisht ose horizontalisht), domethënë për blloqet 1x4 ose 4x1 (skema "4:1:1"). Është gjithashtu e mundur të përdoren lloje të ndryshme rrallimi për Cb dhe Cr, por në praktikë skema të tilla janë jashtëzakonisht të rralla.

Më pas, komponenti i shkëlqimit Y dhe komponentët e ngjyrave Cb dhe Cr ndahen në blloqe prej 8x8 pikselësh. Çdo bllok i tillë i nënshtrohet një transformimi kosinus diskret (DCT). Koeficientët DCT që rezultojnë janë të kuantizuar (në përgjithësi, matrica të ndryshme kuantizimi përdoren për Y, Cb dhe Cr) dhe paketohen duke përdorur kodet Huffman. Standardi JPEG gjithashtu lejon përdorimin e kodimit aritmetik shumë 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 kuantizimin e koeficientëve 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'i nënshtrohen kuantizimit më të fortë se ato me frekuencë të ulët. Kjo rezulton në ashpërsimin e detajeve të vogla në imazh. Sa më i lartë të jetë raporti i ngjeshjes, aq më fort kuantizohen të gjithë koeficientët.

Varietetet e skemave të kompresimit JPEG

Standardi JPEG ofron dy mënyra kryesore për të paraqitur të dhënat e koduara.

Më e zakonshme, e mbështetur nga shumica e kodekëve të disponueshëm, është paraqitja sekuenciale e të dhënave JPEG, 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 të koduar të imazhit dhe rezultatet e kodimit vendosen në mënyrë sekuenciale në rrjedhën e daljes në formën e një "skanimi" të vetëm (një grup të dhënash të koduara). Mënyra kryesore ose "bazë" e kodimit lejon vetëm këtë paraqitje. Modaliteti i zgjeruar, së bashku me modalitetin vijues, gjithashtu lejon përfaqësimin progresiv të të dhënave JPEG.

Në rastin e JPEG progresiv, të dhënat e kompresuara shkruhen në rrjedhën e daljes si një grup skanimesh, secila prej të cilave përshkruan të gjithë imazhin me një shkallë në rritje të detajeve. Kjo arrihet ose duke regjistruar në çdo skanim jo grupin e plotë të koeficientëve DCT, por vetëm një pjesë të tyre: së pari - ato me frekuencë të ulët, në skanimet e mëvonshme - ato me frekuencë të lartë (metoda e "përzgjedhjes spektrale", d.m.th. mostrat spektrale ), ose në mënyrë sekuenciale, nga skanimi në skanim, përsosje e koeficientëve të DCT (metoda e "përafrimit të njëpasnjëshëm", d.m.th. përafrimet e njëpasnjëshme). Ky paraqitje progresive e të dhënave është veçanërisht e dobishme kur transmetoni imazhe të kompresuara duke përdorur kanale komunikimi me shpejtësi të ulët, pasi ju lejon të merrni një pasqyrë të të gjithë imazhit pasi të jetë transmetuar vetëm një pjesë e vogël e skedarit JPEG.

Të dy skemat e përshkruara (si JPEG vijuese ashtu edhe progresive) bazohen në DCT dhe në thelb nuk lejojnë marrjen e një imazhi të rindërtuar 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), duke garantuar një përputhje të plotë, bit-për-bit, të origjinalit dhe imazhe të restauruara. 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 është në kërkesë. Raportet dukshëm më të larta të ngjeshjes mund të merren duke përdorur një metodë që, pavarësisht ngjashmërisë në emra, nuk lidhet drejtpërdrejt me standardin JPEG ISO/IEC 10918-1 (Rekomandimi ITU T.81). Kompresimi JPEG-LS, përshkruar nga standardi ISO/IEC 14495-1 (Rekomandimi ITU T.87).

Sintaksa dhe struktura

Skedari JPEG përmban një sekuencë shënuesish, secili prej të cilëve fillon me një bajt 0xFF që tregon fillimin e shënuesit dhe një bajt identifikues. 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 bajtet e fillimit të shënuesi, d.m.th. 0xFF dhe identifikuesi) dhe vetë të dhënat.

Shënuesit bazë JPEG

Shënues	Bajt	Gjatësia	Qëllimi

Algoritmi u zhvillua nga Joint Photographic Expert Group posaçërisht për kompresimin e imazheve 24-bit dhe gri në 1991. Ky algoritëm nuk i ngjesh shumë mirë imazhet me dy nivele, por bën një punë të mirë në trajtimin e imazheve me tone të vazhdueshme në të cilat pikselët e afërt 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ë të blloqeve të imazhit të ndarë prej 8x8 pikselësh. DCT i zbërthen këto blloqe sipas amplitudave të frekuencave të caktuara. Rezultati është 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. Le të supozojmë se një imazh 24-bit me ngjyra të plota është duke u ngjeshur. Në këtë rast, marrim fazat e mëposhtme të punës.

Hapi 1. Ne e konvertojmë imazhin nga hapësira RGB në hapësirën YCbCr duke përdorur shprehjen e mëposhtme:

Le të vërejmë menjëherë se transformimi i anasjelltë arrihet lehtësisht duke shumëzuar matricën e kundërt me vektorin, i cili në thelb është një hapësirë ​​YUV:

.

Hapi 2. Ne e ndajmë 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 pikës në rreshta dhe kolona.

Hapi 3. Aplikimi i DCT në blloqet e imazhit 8x8 pixel. Formalisht, DCT direkte për një bllok 8x8 mund të shkruhet si

Ku . Meqenëse DCT është "zemra" e algoritmit JPEG, është e dëshirueshme që në praktikë 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 paraprakisht 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ë e elementeve 8x8, që përshkruan një hapësirë ​​8-dimensionale, për të përfaqësuar kolonat e një blloku në këtë 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ë matrice shkruhet si

Këtu është rezultati i DCT, llogaritja e të cilit kërkon operacione shumëzimi dhe pothuajse po aq shtesa, që është dukshëm më pak se llogaritjet e drejtpërdrejta duke përdorur formulën e mësipërme. Për shembull, do t'ju duhet për të kthyer një imazh me përmasa 512x512 piksele veprimet aritmetike. Duke marrë parasysh 3 komponentë të shkëlqimit, marrim një vlerë prej 12,582,912 operacionesh aritmetike. Numri i shumëzimeve dhe mbledhjeve mund të reduktohet më tej duke përdorur algoritmin e shpejtë të transformimit 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 komponentin 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 përdoruesin të zgjedhë në mënyrë të pavarur 64 koeficientë, kështu që 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 krominancën. Këto tabela janë paraqitur më poshtë. Qasja e dytë është sintetizimi (llogaritja në fluturim) e një tabele kuantizimi që varet nga një parametër që specifikohet nga përdoruesi. Tabela në vetvete është ndërtuar sipas formulës

Faza e kuantizimit është ajo ku kontrollohet raporti i kompresimit dhe ku ndodhin humbjet më të mëdha. Është e qartë se duke specifikuar tabelat e kuantizimit me koeficientë të mëdhenj, do të marrim më shumë zero dhe, për rrjedhojë, një raport më të lartë kompresimi.

Efektet specifike të algoritmit shoqërohen gjithashtu me kuantizimin. Në vlera të mëdha hapi i kuantizimit, humbjet mund të jenë aq të mëdha sa që imazhi të ndahet në katrorë monokromatikë 8x8. Nga ana tjetër, humbjet në frekuencave të larta mund të manifestohen në të ashtuquajturin "efekt Gibbs", kur një "halo" me onde formohet rreth kontureve me një tranzicion të mprehtë të ngjyrave.

Hapi 5. Ne e konvertojmë matricën 8x8 në një vektor me 64 elemente duke përdorur skanimin zigzag (Fig. 2).

Oriz. 2. Skanim zigzag

Si rezultat, koeficientët jo zero, si rregull, do të shkruhen në fillim të vektorit, dhe zinxhirët e zerove do të formohen në fund.

Hapi 6. Ne e transformojmë vektorin duke përdorur algoritmin e modifikuar RLE, prodhimi i të cilit janë ç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ë radhën tjetër. qelizë. Për shembull, vektori 1118 3 0 0 0 -2 0 0 0 0 1 ... do të shembet në çifte (0, 1118) (0,3) (3,-2) (4,1) ... .

Duhet të theksohet se numri i parë i komponentit të konvertuar është në thelb i barabartë me ndriçimin mesatar të bllokut 8x8 dhe quhet koeficienti DC. E njëjta gjë për të gjitha blloqet e imazhit. Kjo rrethanë sugjeron që koeficientët DC mund të kompresohen në mënyrë efektive nëse mbani mend jo vlerat e tyre absolute, por ato 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 koeficientin e parë si eshte. Në këtë rast, renditja e koeficientëve DC mund të bëhet, për shembull, kështu (Fig. 3). Koeficientët e mbetur, të cilët quhen koeficientë AC, mbeten të pandryshuar.

Hapi 7 Ne i bashkojmë çiftet që rezultojnë duke përdorur kode Huffman jo uniforme me një tabelë 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 në kohën e funksionimit. Plotësimi i kërkesës së fundit të bërë pamja e mundshme kamera dixhitale që shkrepin imazhe 24-bit. Nëse algoritmi do të ishte asimetrik, do të ishte e pakëndshme të prisni një kohë të gjatë që pajisja të "ringarkohet" dhe të kompresojë imazhin.

Megjithëse algoritmi JPEG është një standard ISO, formati i skedarit të tij nuk është rregulluar. Duke përfituar nga kjo, prodhuesit krijojnë formatet e tyre që janë të papajtueshme me njëri-tjetrin dhe, për rrjedhojë, mund të ndryshojnë algoritmin. Kështu, tabelat e algoritmeve të brendshme të rekomanduara nga ISO zëvendësohen nga të tyret. Ekzistojnë gjithashtu opsione JPEG për aplikacione specifike.

Gjenerimi adaptiv i matricave të kuantizimit në skemat e ngjashme me JPEG

Luzhkov Yuri Valerievich,

student i diplomuar i Shën Petersburgut Universiteti Shtetëror teknologjia e informacionit, mekanika dhe optika.

Drejtues shkencor – Doktor i Shkencave Teknike, Profesor

Tropchenko Alexander Yuvenalievich.

Prezantimi

NË vitet e fundit Ekziston një tendencë e qartë për të popullarizuar skemat e kompresimit të imazhit me humbje të bazuara në transformimet e valëve. Megjithatë, formatet e kompresimit të imazhit të bazuara në transformimin diskrete të kosinusit (DCT) janë ende më të përdorurit.

Format i përhapur JPEG (Grupi i Përbashkët i Ekspertëve të Fotografisë) [ Wallace G.K.] shtron pyetjen e mëposhtme për studiuesit: a është e mundur të modifikohet skema ekzistuese e kompresimit në atë mënyrë që të rritet cilësia e kompresimit pa ndryshuar algoritmin e dekompresimit? Zgjidhja e këtij problemi do të bëjë të mundur zbatimin e modifikimeve në kompresorët ekzistues pa u shqetësuar për disponueshmërinë e softuerit special (të modifikuar) për dekompresimin e imazhit nga përdoruesit.

Me skemë të ngjashme me JPEG nënkuptojmë një variant të një skeme kompresimi me ndarjen e imazhit në fragmente drejtkëndëshe, elementët e detyrueshëm të së cilës janë: transformimi ortogonal, kuantizimi i të dhënave të konvertuara dhe kodimi statistikor i tyre pasues.

Shumë algoritme kompresimi përdorin një numër parametrash të paracaktuar. Në JPEG, këto përfshijnë matricat e kuantizimit dhe tabelat Huffman. Ato ruhen në kokën e skedarit të ngjeshur dhe mund të përcaktohen nga përdoruesi në mënyrë të pavarur, gjë që lejon përmirësimin e cilësisë së kompresimit.

Kështu, sot tashmë janë propozuar disa qasje për përpilimin e matricave të kuantizimit JPEG (për shembull, dhe ), të cilat, megjithatë, nuk janë universale. Në punën tonë, ne do të shqyrtojmë një qasje të përgjithësuar për kuantizimin skalar adaptiv të koeficientëve të spektrit, i cili është i lehtë për t'u zbatuar dhe mund të zbatohet në skema të ngjashme me JPEG.

Kuantizimi i sinjalit adaptiv

Kuantizimi është një metodë e përpunimit të sinjalit që përfshin futjen e shtrembërimit në të. Thelbi kuantizimi skalar zbret në për të ndarë gamën e vlerave të funksionit në një numër të fundëm intervalesh dhe më pas zgjedhjen e një vlere për të përfaqësuar çdo vlerë nga ky interval.

Pra, le të jepet një grup intervalesh dhe një grup pikësh, atëherë funksioni i kuantizimitështë përcaktuar si për . Kur kuantizimi skalar uniform një grup intervalesh mund të përfaqësohet si:

ku - parametri, ose hapi i kuantizimit, – kompensimi bazë i intervalit, , – numri i intervalit, i cili është objekti i koduar. Pastaj operacioni i kuantizimit mund të reduktohet në ndarje të thjeshtë me rrumbullakim:

.(1)

Përshtatshmëria në kuantizimin skalar arrihet përmes përzgjedhjes individuale të hapit të kuantizimit për secilën vlerë të kuantizuar.

Kuantizimi skalar adaptiv bazuar në kriterin e peshës

Qasja që ne propozojmë bazohet në analiza statistikore e koeficienteve spektrale. Mund të përdoret në skemat e kompresimit (p.sh JPEG ) me kusht që dritarja e skanimit të sinjalit të ketë një madhësi konstante.

Pra, le të jepet një sekuencë sasish, e ndarë nëMblloqe identike tëNvlerat në secilin, dhe është indeksi i elementit në një bllok të caktuar, domethënë, çdo element ka analogun e tij në çdo bllok tjetër. Thelbi i qasjes së propozuar është si më poshtë: për secilënntë elementit të th, llogaritet vlera e një kriteri të peshës speciale dhe vendoset hapi i kuantizimit të një elementi të caktuar të spektrit, sa më i madh, aq më i vogël është vlera përkatëse e kriterit të peshës.

Kështu, procedura e kuantizimit kryhet duke marrë parasysh disa informacione statistikore për sinjalin, të dhëna nga , të mbledhura ngaMblloqe dhe unike për elementet e secilit indeks n. Funksioni i kuantizimit (1) në këtë rast do të shënohet si , dhe funksioni i parametrit të kuantizimit – .

Le të prezantojmë një kriter, duke e quajtur atë pesha e koeficientit të spektrit. Vlera do të pasqyrojë shkallën e rëndësisë së pozicionit spektral përkatësnkoeficientët .

Një metodë llogaritjeje bazohet në amplituda mesatare:

.(2)

Siç kanë treguar eksperimentet, llogaritja sipas (2) për koeficientët DCT çon në një shpërndarje joproporcionale të vlerave të kriterit për koeficientët e spektrit me frekuencë të lartë dhe të ulët. Ju mund ta korrigjoni situatën duke përdorur funksioni korrigjues(shih më poshtë), ose duke llogaritur vlerat bazuar në amplituda maksimale:

.(3)

Le t'i drejtohemi çështjes së përcaktimit të një funksioni. Lërini vlerat e tij të kufizohen nga diapazoni . Le të prezantojmë një funksion linear të:

,

ku dhe janë vlerat minimale dhe maksimale, përkatësisht (rasti shqyrtohet veçmas).

Në praktikë, mund të jetë e dobishme të përdoret një funksion jolinear i , i cili arrihet përmes përdorimit të një funksioni korrigjues:

.(4)

Meqenëse çdo në përgjithësi varet nga të gjithë elementët e vektorit origjinal spektral, funksioniEgjithashtu varet nga . Në fakt, ky është një funksion i hapit të kuantizimit të sinjalit. Le të prezantojmë shënimin . Pastaj formula (4) më në fund merr formën:

.(5)

Kështu, funksioni i hapit të kuantizimit lokalizohet në intervalin ngaa 1 deri në a 2 Duke ndryshuar formën e tij, është e mundur të shtypni grupe të caktuara koeficientësh në një masë më të madhe ose më të vogël.

Le të zbatojmë tani qasjen e propozuar për gjenerimin adaptiv të matricave të kuantizimit në qark JPEG . Në (5) do të përdorim funksionin e korrigjimit linear dhe kriterin e amplitudave maksimale (3).

Grafikët e funksioneve të hapit të paracaktuar të kuantizimit JPEG janë paraqitur në Fig.Ka mbetur 1. Δ Grafikët e krijuar në mënyrë adaptive për imazhin "Njeri i vjeter" janë paraqitur në Fig.1, drejtë. Në të dyja rastet, vlerat renditen në rend rritës. Siç mund ta shihni, për të tretën e parë të vlerave të argumentit ka një rritje të mprehtë në Δ, e cila është veçanërisht tipike për funksionet e gjeneruara. Në këtë faqe gjeneruarΔ në disa vende tejkalon ndjeshëm vlerat standarde, gjë që çon në shtypje më të madhe të frekuencave përkatëse.

Oriz. 1. Funksionet e parametrave të kuantizimit standard dhe të gjeneruar me porositur

vlerat në rritje.

Grafiku për imazhin "Njeri i vjeter» është paraqitur në Fig.2, majtas. Në të djathtë janë rezultatet e kompresimit duke përdorur matricat e paracaktuara dhe matricat e krijuara si pjesë e eksperimentit. Siç shihet nga rezultatet, diferenca në raportin e kompresimit është deri në 20% në favor të qasjes adaptive me të njëjtat vlera. PSNR.

Oriz. 2. Gjenerimi i matricave të kuantizimit përshtatës për qarkun JPEG.

konkluzioni

Ne kemi propozuar një metodë për kuantizimin skalar adaptiv të koeficientëve të spektrit, bazuar në llogaritjen e kriterit për rëndësinë e komponentëve spektralë. Siç kanë treguar eksperimentet, përdorimi i qasjes së konsideruar në qark JPEG ju lejon të merrni një fitim në raportin e ngjeshjes deri në 20% në krahasim me përdorimin e matricave standarde të kuantizimit.

Përdorimi praktik i modifikimit të konsideruar përfshin zbatimin e vetëm një kompresori, dhe për të parë imazhet mjafton të përdorni një standard JPEG -dekompresori, i cili është një avantazh i rëndësishëm i zgjidhjes së propozuar.

Letërsia

1. Fung H. T., Parker K. J. Dizajnimi i tabelave të kuantizimit përshtatës të imazhit për JPEG // Journal of Electronic Imaging. – 1996. – Vëll. 4, N. 2. – F. 144 – 150.

2. Grey R.M., Neuhoff D.L.Kuantizimi // Transaksionet IEEE mbi teorinë e informacionit. – 1998. – Vëll. 44, N. 6. – F. 2325 – 2383.

3. Ratnakar V., Livny M. Zgjerimi i RD -OPT me prag global për optimizimin JPEG // Konferenca e kompresimit të të dhënave.– 1996.

4. Wallace G. K. Standardi i kompresimit të fotografive JPEG // IEEE Trans. Elektronikë Konsumatore. – 1992. – Vëll. 38, N. 1. – F. 18 – 34.