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 në dy nivele, por trajton shumë mirë 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ë të blloqeve të imazhit që nuk mbivendosen, me madhësi 8x8 piksele. DCT i zbërthen këto blloqe sipas amplitudave të frekuencave të caktuara. Rezultati është një matricë në të cilën shumë nga koeficientët priren të jenë afër zeros, e cila mund të përfaqësohet në një 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ësh 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ë arrihet lehtësisht duke shumëzuar matricë e anasjelltë në një vektor i cili në thelb është një hapësirë YUV:
.
Hapi 2 Ne e ndajmë imazhin origjinal në matrica 8x8. Ne formojmë tre matrica pune DCT nga secila - 8 bit veç e veç për secilin komponent. Në raportet e larta të kompresimit, një bllok 8x8 zbërthehet në përbërës YCbCr në një format 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, 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 paraprakisht dhe tabelimi i rezultateve të llogaritjes. 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 bllokut 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 shkruhet në formën e matricës si
Këtu është rezultati i DCT, llogaritja e të cilit kërkon operacione shumëzimi dhe pothuajse të njëjtin numër mbledhjesh, që është shumë më pak se llogaritjet e drejtpërdrejta duke përdorur formulën e mësipërme. Për shembull, për të kthyer një imazh prej 512x512 pikselësh, kërkohen veprime aritmetike. Duke marrë parasysh 3 komponentë të shkëlqimit, 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 janë në të majtë këndi i sipërm 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, një pjesë e informacionit hidhet poshtë. Këtu, çdo numër nga matrica ndahet me një numër të veçantë nga "tabela e kuantizimit" dhe rezultati rrumbullakohet deri 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 tabelat e veta të kuantizimit, të cilat, megjithatë, do të duhet t'i kalojnë dekoderit 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 e shpejtë) e një tabele kuantizimi në varësi të një parametri, i cili specifikohet nga përdoruesi. Tabela në vetvete është ndërtuar sipas formulës
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 rrjedhimisht një raport më të madh kompresimi.
Efektet specifike të algoritmit shoqërohen gjithashtu me kuantizimin. Në vlera të mëdha të hapit të kuantizimit, humbjet mund të jenë aq të mëdha sa që imazhi të ndahet në katrorë të thjeshtë 8x8. Nga ana tjetër, humbjet frekuencave të larta mund të manifestohen në të ashtuquajturin "efekt Gibbs", kur një "nimbus" me onde 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 skanimin "zigzag" (Fig. 2).
Oriz. 2. Skanim zigzag
Si rezultat, në fillim të vektorit, si rregull, do të shkruhen koeficientë jo zero, dhe në fund do të formohen zinxhirë zero.
Hapi 6 Ne e transformojmë vektorin duke përdorur algoritmin e modifikuar RLE, në daljen e të cilit marrim çifte të tipit (kapërcim, numër), ku "kapërcimi" është numëruesi i zerove të kapërcyer, dhe "numri" është vlera që duhet të vendoset. qeliza tjetër. Për shembull, vektori 1118 3 0 0 0 -2 0 0 0 0 1 … do të paloset në çifte (0, 1118) (0.3) (3,-2) (4.1) … .
Duhet të theksohet se numri i parë i komponentit të transformuar është në thelb i barabartë me ndriçimin mesatar të bllokut 8x8 dhe quhet koeficienti DC. Në mënyrë të ngjashme për të gjitha blloqet e imazhit. Kjo rrethanë sugjeron që koeficientët DC mund të kompresohen në mënyrë efektive nëse nuk ruhen 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 të parës. koeficienti ruhet ashtu siç është. Në këtë rast, renditja e koeficientëve DC mund të bëhet, për shembull, si më poshtë (Fig. 3). Koeficientët e mbetur, të cilët quhen koeficientë AC, mbeten të pandryshuar.
Hapi 7 Ne i shembim çiftet që rezultojnë duke përdorur kode jo uniforme Huffman 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ë koeficientëve DC
Oriz. 4. Diagrami strukturor i algoritmit JPEG
Procesi i rindërtimit 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.
Zhvillimi i këtij standardi u orientua nga fakti se këtë algoritëm supozohej 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. Plotësimi i kërkesës së fundit të bërë pamja e mundshme kamera dixhitale që marrin imazhe 24-bit. Nëse algoritmi do të ishte asimetrik, do të ishte e pakëndshme të prisni një kohë të gjatë derisa pajisja të "ringarkohet" - të ngjesh imazhin.
Megjithëse algoritmi JPEG është një standard ISO, formati i skedarit të tij nuk është rregulluar. Duke përdorur këtë, prodhuesit krijojnë formatet e tyre të papajtueshme dhe, për rrjedhojë, mund të ndryshojnë algoritmin. Pra, tabelat e brendshme të algoritmit të rekomanduar nga ISO zëvendësohen prej tyre me të tyren. Ekzistojnë gjithashtu variante të JPEG për aplikacione specifike.
Algoritmi JPEG u zhvillua posaçërisht për kompresimin e imazhit nga Joint Photographic Expert Group (JPEG) dhe bazohet në DCT.
DCT zbërthen imazhin në një grup koeficientësh, disa prej të cilëve mund të jenë të barabartë me zero për shkak të mospërdorimit të disa funksioneve DCT. Tashmë duke përdorur ky fakt mund të arrihet një ngjeshje e të dhënave. Megjithatë, efekti më i madh arrihet duke hequr disa nga koeficientët e parëndësishëm (duke i barazuar me zero).
Zakonisht nga jashtë matrica ka një veçori qartësisht të dukshme. Vlerat numerike të elementeve të matricës zvogëlohen me shpejtësi nga këndi i sipërm i majtë në këndin e poshtëm të djathtë. Kështu, të dhënat më të rëndësishme vendosen në këndin e sipërm të majtë, dhe të dhënat më pak të rëndësishme vendosen në këndin e poshtëm djathtas. Duke përdorur këtë fakt, të dhënat më pak të rëndësishme mund të eliminohen. Për ta bërë këtë, kuantizoni të dhënat e transformuara.
Ideja e kuantizimit është që informacioni spektral (frekuenca) duhet të kalojë një prag të njohur në mënyrë që të përbëjë një pjesë të rëndësishme të të gjithë informacionit për një fragment të caktuar imazhi. Pikërisht në fazën e kuantizimit ndodh humbja e një pjese të informacionit dhe rrjedhimisht humbja e cilësisë.
Kuantizimi zakonisht bëhet në bazë të matricë e veçantë, i cili përmban pjesëtuesit me të cilët do të duhet të ndahen elementet e DCT. Shpesh përdoret algoritmi i mëposhtëm:
Q(i,j) = 1 + ((1 + i + j)q);
Ku Q(i,j) është matrica e pjesëtuesve,
q - parametri i cilësisë.
Duke zgjedhur parametrin q, mund të kontrolloni vlerat e pjesëtuesit dhe të rregulloni raportin e kompresimit. Për shembull, nëse q = 2, ju merrni një matricë të formës së mëposhtme (Fig.3.6):
Figura 3.6. Një shembull i një matrice kuantizimi.
Pas ndarjes së 64 elementeve të matricës në elementet e matricës Q(i,j), si rezultat, një matricë që ka:
Do të ketë një numër të madh vlerash zero shtesë,
Efekti i uljes së vlerave nga lart majtas poshtë djathtas do të jetë edhe më i theksuar.
Për shënimin ekonomik, kërkohet të ndryshohet rendi i kalimit të vlerave të marra në atë mënyrë që sekuencat e elementeve zero të jenë sa më të gjata. Nje nga mënyrat e mundshme ndryshimi i rendit të kalimit është metoda zig-zag (Figura 3.7).
Figura 3.7. Shndërrimi i një matrice dydimensionale në një sekuencë njëdimensionale duke përdorur metodën "zigzag".
Siç shihet nga figura, një matricë dydimensionale prej 8 x 8 elementësh shndërrohet në një sekuencë njëdimensionale me gjatësi prej 64 elementësh. Vetia kryesore e një sekuence të tillë do të jetë vendndodhja e koeficientëve më të rëndësishëm në fillimin e saj, dhe më së paku elemente të rëndësishme(zakonisht zero) në fund të tij.
Zbatimi i algoritmit përfshin veprime të njëpasnjëshme, e cila është ilustruar në Fig. 3.8.
Figura 3.8. Sekuenca e veprimeve në zbatimin e algoritmit JPEG.
1. Nëse është e nevojshme, imazhi konvertohet në formatin YUV.
2. Diferenca e ngjyrave Sinjalet U dhe V janë kampionuar sipas formatit 4:2:0. Ndarja e imazhit në fragmente me 8 x 8 elementë. Më tej, përpunimi i sinjaleve të ndriçimit dhe krominancës mund të kryhet në mënyrë të pavarur dhe paralelisht.
3. Transformimi i kosinusit diskret kryhet në të gjitha blloqet me elementë 8 x 8.
4. Kuantizimi sipas parametrit të cilësisë së zgjedhur.
5. Skanimi i "zigzagut" për të marrë një sekuencë njëdimensionale prej 64 elementësh.
6. Algoritmi RLE aplikuar në një sekuencë njëdimensionale.
7. Algoritmi Huffman aplikohet në një sekuencë tashmë të ngjeshur me RLE.
8. P.p. 3 - 7 kryhen për të gjitha blloqet në formatin e elementeve 8 x 8 dhe për të gjitha planet e ngjyrave.
Karakteristikat kryesore Metoda JPEG janë si më poshtë:
1. Raport i lartë kompresimi, veçanërisht për imazhet që konsiderohen me cilësi të mirë ose të shkëlqyer.
2. Një numër i madh parametrash që lejojnë një përdorues të sofistikuar të eksperimentojë me cilësimet e metodës dhe të arrijë balancën e kërkuar të kompresimit/cilësisë.
3. Rezultate të mira për të gjitha llojet e imazheve me tone të vazhdueshme, pavarësisht nga rezolucioni i tyre, hapësira e ngjyrave, madhësia e pikselit ose veçoritë e tjera.
4. Një metodë kompresimi mjaft e sofistikuar, por jo shumë e ndërlikuar, që ju lejon të krijoni pajisje të përshtatshme dhe të shkruani programe për zbatimin e metodës për kompjuterët e shumicës së platformave, si dhe harduerin.
5. Mundësia e përdorimit të kompresimit pa humbje informacioni në një raport kompresimi jo shumë të lartë.
Për të kompresuar në mënyrë efektive të dhënat, së pari duhet të vlerësoni natyrën e imazhit tuaj. JPEG ngjesh të dhënat e imazhit bazuar në atë që sheh syri i njeriut. Prandaj, për të kuptuar se si dhe çfarë bën JPEG, do të doja t'ju jap ide e pergjithshme mbi perceptimin vizual të njeriut.
Kompresimi JPEG ndodh në disa faza. Qëllimi është të transformohen të dhënat grafike në atë mënyrë që informacioni vizual i parëndësishëm të identifikohet dhe të hidhet lehtësisht. Ky kompresim "me humbje" është i ndryshëm nga shumica e qasjeve të tjera të përdorura me formatet grafike, të cilat përpiqen të mbajnë çdo pjesë të imazhit të paprekur.
model ngjyrash
Hapi i parë në JPEG është zgjedhja e një mënyre të përshtatshme për të paraqitur ngjyrat. Ngjyrat zakonisht specifikohen në një sistem koordinativ 3D. Një sistem i njohur mirë për shumicën e programuesve e përshkruan ngjyrën si një kombinim të së kuqes, jeshiles dhe blusë (RGB). Fatkeqësisht, për sa i përket aftësisë së kompresimit, kjo nuk është Menyra me e mire përshkrimet e ngjyrave. Problemi është se të tre komponentët - e kuqe, jeshile dhe blu - janë ekuivalente. Sidoqoftë, kalimi në një sistem tjetër të interpretimit të ngjyrave ju lejon të nënvizoni disa më shumë informacion i rendesishem.
Profesionistët përdorin dy modele ngjyrash: HSL (Hue-Saturation-Lightness) dhe HSV (Hue-Saturation-Value). Është intuitivisht e qartë se komponenti i ndriçimit (Lightness) i modelit HSL dhe komponenti i shkëlqimit (Vlera) i modelit HSV përcaktojnë secili raportin e dritës dhe hijes në mënyrën e vet. Ngopja përcakton nivelin e ngjyrës "të pastër". Ngjyrat e pangopura shpesh quhen joformalisht si "të pista" (të hirta). Ngjyra është ajo që ne e perceptojmë si ngjyra e një objekti, të tillë si e kuqe ose jeshile gri. Këtu është e rëndësishme të theksohet fakt mahnitës: Shikimi i njeriut është më i ndjeshëm ndaj ndryshimeve në dritë, jo ndaj ngjyrës në vetvete!
Implementime të ndryshme të algoritmit të kompresimit JPEG përdorin të ndryshme sistemet e ngjyrave. Sistemi i paraqitjes së ngjyrave YCbCr i përdorur nga formati JFIF është në shumë mënyra i ngjashëm me skemën e zhvilluar shumë vite më parë për televizionin me ngjyra.
rrallimi
Arsyeja kryesore për konvertimin nga një model ngjyrash në një tjetër është identifikimi i informacionit që është më pak i rëndësishëm për shikimin në një imazh. JPEG zvogëlon sasinë e informacionit të ngjyrave. Ndërsa komponenti i ndriçimit transmetohet me rezolucion të plotë, përbërësit kroma përdorin gjysmën e diapazonit të vlerave. Si rezultat një hap i thjeshtë sasia e të dhënave zvogëlohet për një të tretën.
Nën-kampionimi rregullon ngjyrat e figurës së televizorit me ngjyra. Zakonisht në TV imazh bardh e zi dhe informacionet e ngjyrave transmetohen veçmas. Për më tepër, informacioni i ngjyrave transmetohet në një formë më pak strikte sesa informacioni i ndriçimit të imazhit.
Transformimi i kosinusit diskret (DCT)
Çdo komponent ngjyrash trajtohet veçmas, sikur të mos ishin një ngjyrë, por tre imazhe në shkallë gri. Nëse shikoni një imazh të detajuar nga një distancë, mund të dalloni vetëm tonin e përgjithshëm të figurës. Për shembull, "kryesisht blu" ose "kryesisht e kuqe". Sa më shumë t'i afroheni imazhit, aq më shumë detaje mund të shihni. Për të imituar këtë efekt, JPEG përdor një truk matematikor të quajtur Transformimi i Kosinusit Diskret (DCT). DCT konverton informacionin e pikselit në informacionin e ndryshimit të pikselit. Gjëja e parë që mund të japë DCT është ngjyra mesatare e zonës. Më pas ai shtjellon gjithnjë e më shumë detajet.
Si në rastin imazh në distancë, vlera mesatare e ngjyrës është një informacion shumë i rëndësishëm për zonën e imazhit. Syri juaj është më pak i ndjeshëm ndaj shkallës së ndryshimit të ngjyrës, kështu që nuk është aq i rëndësishëm. Konvertimi i informacionit të ngjyrave Në mënyrë të ngjashme, ne theksojmë informacionin që mund të dhurohet.
Besohet se humbjet shkaktohen nga kjo fazë. Nëse kodoni një imazh duke përdorur DCT dhe më pas e rivendosni duke përdorur funksionin e anasjelltë DCT, nuk do të merrni saktësisht të njëjtin grup bitesh. Megjithatë, ky gabim është një gabim rrumbullakimi. Ndodh gjatë kryerjes së veprimeve aritmetike dhe zakonisht nuk është shumë i madh. Prandaj, unë preferoj të mendoj për fazën DCT si një operacion "kryesisht pa humbje".
Për imazhe të mëdha llogaritja e DCT dhe DCT e anasjelltë është një proces që kërkon shumë kohë. Për të reduktuar kohën e llogaritjes, JPEG e ndan imazhin në një mozaik tetë me tetë pikselë. Secili nga mozaikët përpunohet veçmas, gjë që redukton ndjeshëm kohën e llogaritjes së kërkuar për DCT. Problemi që lind me këtë qasje është se pas kuantizimit (i cili do të diskutohet në seksionin vijues), kufijtë e këtyre katrorëve mund të mos përkojnë dhe për këtë arsye të bëhen të dukshëm kur specifikohet vlerë të ulët parametri i cilësisë.
Kuantizimi
Zhvilluesit JPEG ishin kryesisht të interesuar për imazhet me cilësi fotografike (fotografike, ton të vazhdueshëm). Si rregull, këto imazhe gjysmëtonike karakterizohen nga tranzicione të buta nga një ngjyrë në tjetrën. Për imazhe të tilla, komponenti DCT me frekuencë të ulët (ndryshon ngadalë) është më i rëndësishëm se komponenti me frekuencë të lartë (ndryshim i shpejtë).
Termi kuantizim do të thotë thjesht "rrumbullakim". jpeg hedh poshtë disa informacion grafik duke rrumbullakosur çdo anëtar të DCT me pesha të ndryshme bazuar në faktorë të ndryshëm. Komponenti i frekuencës së lartë është i rrumbullakosur më shumë se komponenti i frekuencës së ulët. Për shembull, komponenti me frekuencë të ulët, i cili ruan vlerën mesatare të shkëlqimit, mund të rrumbullakoset në shumëfishin e tre, ndërsa komponenti i frekuencës së lartë mund të rrumbullakohet në shumëfishin e njëqind!
Operacioni i kuantizimit shpjegon pse kompresimi JPEG, në rastin e kontureve të qarta, çon në formimin e linjave "të nervozuara". Konturet përcaktohen nga komponenti hapësinor me frekuencë të lartë (me ndryshim të shpejtë). (Në shikim të parë, mund të duket se duhet të keni një skicë të paqartë, por mbani mend se C në DCT qëndron për kosinusin.)
Në mënyrë tipike, rrafshet me ngjyra kuantizohen shumë më ashpër se sa rrafshet luma. Këtu zgjedhja e duhur Modeli i ngjyrave ndihmon në identifikimin e informacionit që mund të hidhet poshtë.
Kompresimi
Deri më tani, me përjashtim të rastit kur frekuenca e kampionimit prej dy kanalet me ngjyra, nuk ka ndodhur asnjë ngjeshje. Të gjithë hapat e diskutuar më sipër - transformimi i modelit të ngjyrave, DCT dhe kuantizimi - e lanë madhësinë e të dhënave të pandryshuar. Më në fund, arrijmë në hapin e fundit, gjatë të cilit teknika standarde e kompresimit pa humbje në fakt do të zvogëlojë madhësinë e të dhënave.
Të dhënat e renditura në hapat e mëparshëm mund të kompresohen në mënyrë më efikase sesa lënda e parë që është të dhënat grafike RGB. Për më tepër, asnjë nga hapat e ndërmarrë nuk ishte i tepërt, çdo ndryshim në të dhëna kishte për qëllim ngjeshjen e versionit përfundimtar në mënyrë më efikase.
Ndryshimi i modelit të ngjyrave bëri të mundur hollimin e informacionit të kanalit dhe më pas kuantizimin e tyre më fuqishëm.
DCT bëri të mundur izolimin e komponentit hapësinor me frekuencë të lartë. Komponenti i frekuencës së lartë zakonisht ka vlera të vogla, duke rezultuar në një sasi joproporcionale të vlerave të vogla në daljen e hapit DCT, duke lehtësuar procesin e kompresimit.
Gjatë procesit të kuantizimit, pjesa më e madhe e komponentit me frekuencë të lartë vendoset në zero, dhe pjesa tjetër merr vlera specifike. Reduktimi i numrit kuptime të ndryshme gjithashtu lehtëson procesin e kompresimit të të dhënave.
Standardi JPEG ofron dy metodë të ndryshme kompresim pa humbje që mund të përdoret në hapi i fundit. Kompresimi Huffman është një algoritëm i njohur prej kohësh i papatentuar, lehtësisht i programueshëm. Ndryshe nga ai, më shumë algoritmi i ri Kodimi aritmetik është objekt i patentave të shumta. (Prandaj, nuk është për t'u habitur që shumë programe të kompresimit JPEG mbështesin vetëm kompresimin Huffman.)
Gjatë dekodimit Imazhet JPEG të gjitha këto hapa duhet të ndërmerren rend i kundërt. Rrjedha e të dhënave fillimisht dekompresohet, më pas çdo bllok 8-8 i nënshtrohet një DCT të kundërt dhe në fund imazhi konvertohet në atë përkatëse. model ngjyrash(zakonisht RGB). Vini re se informacioni që është hedhur qëllimisht nga përcaktimi dhe kuantizimi nuk rikuperohet kurrë. Megjithatë, nëse gjithçka është bërë si duhet, humbja e informacionit nuk do të shkaktojë ndonjë degradim të dukshëm të imazhit.
Probleme me algoritmet e arkivimit me humbjeAlgoritmet konvencionale ishin të parët që u përdorën për arkivimin e imazheve. 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 kohët 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 - kompresim me humbje informacioni. Si rregull, raporti i arkivimit dhe, rrjedhimisht, shkalla e humbjes së cilësisë në to mund të vendoset. Në këtë rast, arrihet një kompromis midis madhësisë dhe cilësisë së imazheve.
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 konvertohet në një gamë të kufizuar ngjyrash, kur konvertohet 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ë japim një shembull të 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 shumë kur ndriçimi të zvogëlohet me vetëm 5% (syri nuk do ta vërejë këtë - në monitorë të ndryshëm cilësimi i ndriçimit ndryshon shumë më tepër). Në të njëjtën kohë, imazhet me "borë" - një ndryshim i mprehtë në ngjyrën e pikave individuale, vija të zbehta ose "moiré" do të njihen si "pothuajse të pandryshuara" (Shpjegoni pse?). Kriteret e tjera kanë gjithashtu disavantazhet e tyre.
Merrni parasysh, për shembull, devijimin maksimal:
Kjo masë, siç mund ta merrni me mend, është jashtëzakonisht e ndjeshme ndaj goditjes së pikselëve individualë. ato. në të gjithë imazhin, vetëm vlera e një piksel mund të ndryshojë ndjeshëm (gjë që është pothuajse e padukshme për syrin), megjithatë, sipas kësaj mase, imazhi do të dëmtohet rëndë.
Masa e përdorur aktualisht në praktikë quhet matja e raportit sinjal-zhurmë (raporti sinjal-zhurmë pik-pikës - PSNR).
Kjo masë, në fakt, është e ngjashme me devijimin standard, por është disi më i përshtatshëm për t'u përdorur 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ë bëhet dallimi midis imazheve origjinale dhe të zbërthyera me sy. 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 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 një shkallëzim të thjeshtë të imazhit. Algoritmi JPEG
JPEG është një nga algoritmet më të rinj dhe mjaft të fuqishëm. Është praktikisht standardi de fakto për imazhet me ngjyra të plota. Algoritmi funksionon me zona 8x8, në të cilat shkëlqimi dhe ngjyra ndryshojnë relativisht pa probleme. Si rezultat, kur zgjerohet matrica e një rajoni të tillë në një seri të dyfishtë për sa i përket kosinuseve (shih formulat më poshtë), vetëm koeficientët e parë rezultojnë të jenë domethënës. Kështu, kompresimi në JPEG kryhet për shkak të butësisë së ndryshimeve të ngjyrave në imazh.
Algoritmi u zhvillua nga një grup ekspertësh fotografie posaçërisht për kompresimin e imazheve 24-bit. JPEG - Joint Photographic Expert Group - një divizion brenda ISO - Organizata Ndërkombëtare për Standardizim. Emri i algoritmit lexon ["jei" peg]. Në përgjithësi, algoritmi bazohet në një transformim diskret kosinus (në tekstin e mëtejmë DCT) i aplikuar në matricën e imazhit për të marrë një matricë të re koeficientësh. Zbatohet një transformim i kundërt për të marrë imazhin origjinal.
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 të përafrohen koeficientët më përafërsisht pa një humbje të dukshme në cilësinë e imazhit.
Për këtë përdoret kuantizimi i koeficientëve. Në shumë rast i thjeshtëështë një zhvendosje aritmetike djathtas. Ky transformim humbet disa informacione, por mund të arrihen raporte të mëdha kompresimi.
Si funksionon algoritmi
Pra, le të shqyrtojmë algoritmin në më shumë detaje. Le të themi se po kompresojmë një imazh 24-bit.
Hapi 1.
Ne përkthejmë imazhin nga hapësirë ngjyrash RGB, me komponentët përgjegjës për përbërësit e kuq (E kuqe), jeshile (E gjelbër) dhe blu (Blu) të ngjyrës së pikës, në hapësirën e ngjyrave YCrCb (ndonjëherë quhet YUV).
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. Një transformim i ngjashëm është përdorur prej kohësh në televizion. Një brez më i ngushtë frekuencash u ndahet sinjaleve përgjegjëse për ngjyrën.
I thjeshtuar, përkthimi nga hapësira e ngjyrave RGB në hapësirën e ngjyrave YCrCb mund të përfaqësohet duke përdorur matricën e tranzicionit:
Transformimi i anasjelltë bëhet duke shumëzuar vektorin YUV me matricën e kundërt.
Hapi 2
Ne e ndajmë imazhin origjinal në matrica 8x8. Ne formojmë tre matrica pune DCT nga secila - 8 bit veç e veç për secilin komponent. Në raportet e 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 rreshtit dhe përmes kolonës. ato. nga matrica origjinale 16x16, merret vetëm një matricë DCT funksionale. Në këtë rast, siç shihet lehtë, humbasim 3/4 informacione të dobishme në lidhje me përbërësit e ngjyrave të figurës dhe menjëherë marrim 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 shumë 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, ky transformim mund të përfaqësohet si më poshtë:
Hapi 4
Ne bëjmë kuantizimin. Në parim, kjo është thjesht ndarja e matricës së punës me matricën e kuantizimit element për element. 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ë MC).
Në këtë hap, raporti i ngjeshjes kontrollohet dhe ndodh humbja më e madhe. Është e qartë se duke vendosur MC me koeficientë të mëdhenj, do të marrim më shumë zero dhe, rrjedhimisht, një raport më të madh kompresimi.
Efektet specifike të algoritmit shoqërohen gjithashtu me kuantizimin. Në vlerat e larta të koeficientit gama, humbjet në frekuenca të ulëta mund të jenë aq të mëdha sa që imazhi të ndahet në katrorë 8x8. Humbjet në frekuenca të larta mund të shfaqen në të ashtuquajturin "efekt Gibbs", kur një lloj "nimbus" formohet rreth kontureve me një tranzicion të mprehtë të ngjyrave.
Hapi 5.
Ne e përkthejmë matricën 8x8 në një vektor 64 elementësh duke përdorur skanimin "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 - e lartë.
Hapi 6
Ne e lidhim vektorin 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. Kështu, 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
Çiftet që rezultojnë i palosim duke koduar Huffman me një tabelë fikse.
Procesi i rindërtimit të imazhit në këtë algoritëm është plotësisht simetrik. Metoda ju lejon të kompresoni disa imazhe me 10-15 herë pa humbje serioze.
Tubacioni operativ i përdorur në algoritmin JPEG.
domethënëse aspektet pozitive algoritmi është se:
- Përcakton raportin e kompresimit.
- ditë pushimi imazh me ngjyra mund të ketë 24 bit për pikë.
- Rritja e raportit të kompresimit e ndan imazhin në katrorë të veçantë (8x8). Kjo për faktin se humbje të mëdha ndodhin në frekuenca të ulëta gjatë kuantizimit, dhe bëhet e pamundur rivendosja e të dhënave origjinale.
- Shfaqet efekti Gibbs - halo përgjatë kufijve të tranzicioneve të mprehta të ngjyrave.
Kërkesa e fundit bëri të mundur lodra të tilla si kamera dixhitale - pajisje të madhësisë së një videokamere të vogël që nxjerrin 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ë që nëse algoritmi do të ishte asimetrik, do të ishte e pakëndshme të prisni një kohë të gjatë derisa pajisja të "ringarkohet" - të ngjesh imazhin.
Një tjetër veçori jo shumë e këndshme e JPEG është se shpesh vijat horizontale dhe vertikale në ekran janë absolutisht të padukshme dhe mund të shfaqen vetëm kur printohen në formën e një modeli moiré. Ndodh kur një model printimi i zhdrejtë aplikohet në vijat horizontale dhe vertikale të imazhit. Për shkak të këtyre surprizave, JPEG nuk rekomandohet për përdorim aktiv në printim, duke vendosur koeficientë të lartë. Sidoqoftë, kur arkivoni imazhe të destinuara për shikimin e njerëzve, aktualisht është i domosdoshëm.
Aplikim i gjerë i JPEG kohe e gjate i përmbajtur, ndoshta, vetëm nga fakti se ai operon me imazhe 24-bit. Prandaj, për të parë një fotografi me cilësi të pranueshme në një monitor konvencional në një gamë 256 ngjyrash, ishte e nevojshme të përdorni algoritme të përshtatshme dhe, për rrjedhojë, kohë të caktuar. Në aplikacionet që synojnë një përdorues zgjedhës, si lojërat, vonesa të tilla janë të papranueshme. Përveç kësaj, nëse imazhet i keni, le të themi, në 8-bit Formati GIF konvertohet në JPEG 24-bit dhe më pas kthehet në GIF për shikim, atëherë humbja e cilësisë do të ndodhë dy herë me të dy konvertimet. Sidoqoftë, fitimi në madhësinë e arkivit është shpesh aq i madh (3-20 herë!), dhe humbja në cilësi është aq e vogël, saqë 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ërdorur këtë, prodhuesit krijojnë formatet e tyre të papajtueshme dhe, për rrjedhojë, mund të ndryshojnë algoritmin. Pra, tabelat e brendshme të algoritmit të rekomanduar nga ISO zëvendësohen prej tyre me të tyren. Përveç kësaj, ka një konfuzion të lehtë kur vendosni shkallën e humbjes. 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 variante të JPEG për aplikacione specifike.
Si standardi ISO JPEG po fillon të përdoret gjithnjë e më gjerësisht në shkëmbimin e imazheve në rrjetet 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 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, me një shkallë të lartë kompresimi, imazhi ndahet në blloqe prej 8x8 piksele.
Algoritmi FraktalIdeja e metodës
Arkivimi fraktal bazohet në faktin se ne e paraqesim imazhin në një formë më kompakte - duke përdorur koeficientët e sistemit të funksioneve të përsëritura (Sistemi i Funksionit të Përsëritur - më poshtë referuar si IFS). Përpara se të shqyrtojmë vetë procesin e arkivimit, le të shohim 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 (x_koordinata, y_koordinata, shkëlqimi) i nënshtrohen transformimit.
Ky proces u demonstrua më qartë nga Barnsley në librin e tij "Compression Fractal Image". Atje u prezantua koncepti i një fotokopjuesi, i përbërë nga një ekran në të cilin shfaqet imazhi origjinal dhe një sistem lentesh që projektojnë imazhin në një ekran tjetër:
- Lentet mund të projektojnë një pjesë të imazhit formë të lirë në çdo vend 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 rrotullojeni dhe rrotullojeni fragmenti i imazhit tuaj.
- Lente duhet në shkallë(zvogëloni) fragmentin e imazhit tuaj.
Duke vendosur lente dhe duke ndryshuar karakteristikat e tyre, ne mund të kontrollojmë imazhin që rezulton. Një përsëritje e punës së Makinerisë konsiston në faktin se një i ri është ndërtuar nga imazhi origjinal me ndihmën e projeksionit, pas së cilës ai i ri merret si fillestar. Pretendohet se në procesin e përsëritjeve do të marrim një imazh që nuk do të ndryshojë më. 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 këtë IFS. Teoria përkatëse garanton se ka saktësisht një pikë fikse për çdo IFS.
Meqenëse harta e lenteve është kontraktuese, çdo lente përcakton 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(jo rreptësisht - objekt matematikor i ngjashëm).
Më të famshmet janë dy imazhe të marra me ndihmën e IFS: "Trekëndëshi Sierpinski" dhe "Fier Barnsley". "Trekëndëshi i Sierpinskit" jepet nga tre, dhe "Fieri i Barnsley" me katër transformime afine (ose, në terminologjinë tonë, "thjerrëza"). Çdo transformim është i koduar në vetëm disa bajt, ndërsa imazhi i ndërtuar me ndihmën e tyre mund të marrë disa megabajt.
Ushtrim: Tregoni 4 zona në imazh që do të kombinohen për të mbuluar të gjithë imazhin dhe 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 kërkon kaq shumë kohë. Në fakt, kompresimi fraktal është një kërkim për zona të ngjashme në një imazh dhe përcaktimi i parametrave të transformimeve afinike për to.
=>
Në rastin më të keq, nëse nuk zbatohet një algoritëm optimizues, do të jetë e nevojshme të numërohen dhe krahasohen të gjitha fragmentet e mundshme të imazhit të madhësive të ndryshme. Edhe për imazhe të vogla, duke marrë parasysh diskretin, do të marrim një numër astronomik opsionesh për t'u renditur. Për më tepër, edhe një ngushtim i mprehtë i klasave të transformimit, për shembull, duke shkallëzuar vetëm 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 përfaqësuar në formë
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. Një pikë e tillë si quhet pikë fikse(tërheqës) i transformimit.
Përkufizimi. Një transformim në një hapësirë metrike (X, d) thuhet se është kontraktues nëse ekziston një numër s: , e tille qe
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 transformimit të kompresimit)
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 transformimi afinal tredimensional , si
dhe është përcaktuar në një nënbashkësi kompakte të katrorit kartezian x. Pastaj do të përkthejë një pjesë të sipërfaqes S në zonën e vendosur me zhvendosje (e,f) dhe rrotullimi i dhënë nga matrica
Megjithatë, nëse interpretojmë vlerën S si shkëlqimi i pikave përkatëse, do të ulet në fq herë (transformimi duhet të jetë kontraktues) dhe do të ndryshojë në një ndryshim q.
Përkufizimi.
popullsi e fundme W kontraktimi i transformimeve afinale tredimensionale të përcaktuara në domene të tilla që dhe 
, quhet sistemi i funksioneve të përsëritura ( IFS).
Një sistem funksionesh të përsëritura shoqërohet në mënyrë unike me një pikë fikse - një imazh. Kështu, procesi i kompresimit konsiston në kërkimin e koeficientëve të sistemit, dhe procesi i dekompresimit konsiston në përsëritjen e sistemit derisa imazhi që rezulton të stabilizohet (pika fikse IFS). Në praktikë, mjaftojnë 7-16 përsëritje. Rajonet do të referohen si renditjen, dhe zonat domain.
Ndërtimi i një algoritmi
Siç është bërë tashmë e qartë nga sa më sipër, detyra kryesore në ngjeshjen nga algoritmi fraktal është gjetja e transformimeve afine përkatëse. Në rastin më të përgjithshëm, ne mund të përkthejmë zona imazhi të çdo madhësie dhe forme, megjithatë, në këtë rast, marrim një numër astronomik opsionesh për fragmente të ndryshme për t'u renditur, të cilat nuk mund të përpunohen për momentin as në një superkompjuter.
AT versioni i trajnimit të algoritmit , të theksuar më poshtë, janë bërë kufizimet e mëposhtme në këtë zonë:
- Të gjitha zonat janë katrorë me brinjë paralele me anët e figurës. Ky kufizim është mjaft i rëndë. Në fakt, ne do të përafrojmë të gjithë manifoldin forma gjeometrike vetëm katrorë.
- Kur konvertohet një zonë domeni në një domen të renditjes, madhësia zvogëlohet saktësisht dy herë. Kjo thjeshton shumë kompresorin dhe dekompresorin. detyra e shkallëzimit të zonave të vogla është jo 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.
- Zonat e domenit janë marrë "përmes një pike" si në X ashtu edhe në Y, e cila redukton menjëherë kërkimin me një faktor prej 4.
- Kur konvertoni një domen domeni në një rang, kubi mund të rrotullohet vetëm në 0 0 , 90 0 , 180 0 ose 270 0. Gjithashtu lejohet pasqyrim pasqyre. Numri total transformimet e mundshme (duke numëruar bosh) - 8.
- Bëhet shkallëzimi (ngjeshja) vertikalisht (shkëlqimi). një numër të caktuar herë- në 0.75.
Këto kufizime lejojnë:
- 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 të përfaqësosh të dhënat që do të shkruhen 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 numër.
- tre bit për të specifikuar transformimin e simetrisë kur konvertohet një bllok domeni në një bllok të renditjes.
- 7-9 bit për të vendosur ndryshimin e shkëlqimit gjatë përkthimit.
Për shembull, për një skedar në shkallë gri me 256 ngjyra të 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 ka zënë 262144 (512x512) bajt (duke përjashtuar kokën), atëherë skedari me koeficientë do të merrte 14336 bajtë. Koeficienti i arkivimit - 18 herë. Në të njëjtën kohë, nuk marrim parasysh që një skedar me koeficientë mund të ketë gjithashtu tepricë dhe të arkivohet duke përdorur një metodë arkivimi pa humbje, siç është LZW.
Aspektet negative të kufizimeve të propozuara:
- Meqenëse të gjitha zonat janë katrore, është e pamundur të përdoret ngjashmëria e objekteve që janë larg katrorëve në formë (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ërdorë ngjashmërinë e objekteve në imazh, këndi midis të cilave nuk është shumëfish i 90 0 .
Vetë algoritmi i paketimit reduktohet në numërimin e të gjitha blloqeve të domenit dhe përzgjedhjen 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 rrotullime dhe neg.
aktuale=Koordinatat aktuale transformimet;
D=image->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;
}
) //Rapësi 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 e kontrollojmë me të gjitha blloqet e mundshme të domenit (përfshirë ato që kanë pësuar një transformim simetrie), gjejmë variantin me masën më të vogël L. 2 (devijimi më i vogël standard) 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) ndryshimi i shkëlqimit për këtë palë blloqe. Zhvendosja e ndriçimit llogaritet si:
,
ku r ij- vlerat e pikselit të bllokut të renditjes ( R), a d ij- vlerat e pikselit të bllokut të domenit ( D). Në këtë rast, masa konsiderohet si:
.
Ne nuk llogarisim rrenja katrore nga L 2 matni dhe mos e ndani me n, meqenëse të dhënat e transformimit 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 që na duhen 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 origjinalit). Zakonisht 16 përsëritje janë të mjaftueshme për këtë.
Lexoni koeficientët e të gjitha blloqeve nga skedari;
Le të krijojmë imazh i zi madhësia e duhur;
Derisa (imazhi nuk do të mbetet i qetë)(
Për (çdo varg (R))(
D=image->CopyBlock(D_coord_for_R);
Për(çdo piksel( i,j) në bllok (
R ij = 0,75 D ij + o R;
) //Piksel tjetër
) //Blloku tjetër
)//Deri në fund
Meqenëse kemi regjistruar koeficientët për blloqet R ij(të cilat, siç e kemi përcaktuar, në rastin tonë të veçantë janë katrorë me të njëjtën madhësi) radhazi, rezulton se ne e mbushim imazhin në mënyrë të njëpasnjëshme me katrorët e rrjetës së ndarjes duke përdorur një transformim afine.
Siç mund të llogaritet, numri i operacioneve për piksel të imazhit në shkallë gri gjatë restaurimit është jashtëzakonisht i vogël (N operacione "+", 1 operacione "*", ku N është numri i përsëritjeve, d.m.th. 7-16). Për shkak të kësaj, dekompresimi i imazhit për algoritmin fraktal është më i shpejtë se dekompresimi, për shembull, për algoritmin JPEG, në të cilin ka 64 "+" dhe 64 "? ” (duke përjashtuar hapat RLE dhe kodimin Huffman!). Në të njëjtën kohë, 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 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ë, shpesh i integruar në arkitekturën e procesorit (procesorët SGI, Intel MMX...), sesa produkti skalar 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 konvertimin në një hapësirë tjetër ngjyrash.
Vlerësimi i humbjeve dhe mënyrat e rregullimit të tyre
Në përmbledhje Versioni i thjeshtuar i algoritmit humbi shumë çështje të rëndësishme. Për shembull, çka nëse algoritmi nuk mund të gjejë një imazh të ngjashëm për ndonjë fragment të imazhit? Zgjidhja 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 kompresimit fraktal, si dhe për algoritmet e tjera të kompresimit me humbje, mekanizmat me anë të të cilëve do të mundësohet kontrollimi i shkallës së ngjeshjes dhe shkallës së humbjes 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 afinale duke u siguruar që raporti i kompresimit të mos jetë më i ulët se një vlerë fikse. Së dyti, mund të kërkohet që në një situatë kur ndryshimi midis fragmentit që përpunohet dhe përafrimit më të mirë të tij është mbi një vlerë të caktuar pragu, ky fragment të ndahet domosdoshmërisht (për të krijohen domosdoshmërisht disa "thjerrëza"). Së treti, është e mundur të ndalohet fragmentimi i 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ë kemi kontroll shumë fleksibël mbi raportin e ngjeshjes së imazhit në intervalin nga përputhja bit-pas-bit në çdo shkallë kompresimi. Vini re se ky fleksibilitet do të jetë shumë më i lartë se ai i "konkurrentit" 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 perceptim) 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ë paqartë.
Simetria: 100-100000
Karakteristikat: Mund ta shkallëzojë lirshëm imazhin kur zbërthehet, duke e rritur atë me 2-4 herë pa shfaqjen e një "efekti shkallësh". Ndërsa niveli i kompresimit rritet, një efekt "blloqe" 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ë rajoneve. Algoritmi është i fokusuar në imazhe me ngjyra dhe bardh e zi me tranzicione të qetë. Ideale për foto si rrezet x. Raporti i ngjeshjes është vendosur dhe varion midis 5-100. Kur përpiqeni të vendosni një koeficient më të lartë në kufijtë e mprehtë, veçanërisht ato që kalojnë diagonalisht, shfaqet një "efekt i shkallëve" - hapa me shkëlqim të ndryshëm në madhësi disa pikselë.
Ideja e algoritmit është që ne të ruajmë ndryshimin në 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 sekuencë a imund të përkthehet në dyshe në një sekuencë b 1.2i.
Le të analizojmë 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). Do të 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 imjaft afër 0. Le ta 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 që rezultojnë, 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 aplikuam 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, kompresim shtesë mund të merret duke përdorur tabela jo uniforme të hapit Huffman (d.m.th., ne 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.
Një ushtrim: Ne rivendosëm 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ë algoritmi i kompresimit të valës do të rikrijojë.
Algoritmi për të dhënat dydimensionale zbatohet në mënyrë të ngjashme. Nëse kemi një katror prej 4 pikësh me shkëlqim a 2i, 2j,a 2 i +1 , 2 j,a 2i, 2j+1, dhe a 2 i +1 , 2 j +1, pastaj
| Fillestare | B1 | B2 | |
| imazh | B3 | B4 |
Duke përdorur këto formula, për një imazh prej 512x512 pikselësh, pas transformimit të parë, do të marrim 4 matrica me madhësi 256x256 elementësh:
-- 
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ë vlerave të pikselit përgjatë horizontales. Në të tretën - dallimet mesatare të çifteve të vlerave të pikselit përgjatë vertikales. Në të katërtin - ndryshimi mesatar 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 4 matrica me madhësi 128x128 në vend të matricës së parë. Duke përsëritur transformimin tonë për herë të tretë, do të përfundojmë me: 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 (menjëherë duke marrë një fitim prej rreth një të tretës së madhësisë së skedarit - 1- 1/4 - 1/16 - 1/64 ...).
Përparësitë e këtij algoritmi përfshijnë faktin se ai ju lejon shumë lehtë të zbatoni mundësinë e një "zhvillimi" gradual të imazhit kur transmetoni imazhin në rrjet. Përveç kësaj, duke qenë se ne në fakt ruajmë një kopje të vogël të tij në fillim të figurës, është më e lehtë të tregohet imazhi "i trashë" sipas titullit.
Ndryshe nga JPEG dhe algoritmi fraktal, kjo metodë nuk funksionon me blloqe, për shembull, 8x8 piksele. Më saktë operojmë me blloqet 2x2, 4x4, 8x8 etj. Megjithatë, 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, me një shkallë të lartë kompresimi, imazhi ndahet në blloqe të veçanta.
konkluzioni
Si përfundim, le të shohim tabelat që përmbledhin 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 | Nënstrings të njëjta: 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 ngjyrë të bardhë në një imazh, zona të mëdha të mbushura me një ngjyrë të vetme |
| Rekursive | Tranzicione të lëmuara ngjyrash dhe pa skaje të mprehta |
| JPEG | Nuk ka kufij të mprehtë |
| fraktal | Ngjashmëria midis elementeve të imazhit |
| Algoritmi | K-ju ngjeshje | Simetria në kohë | 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 | gri 24-bit | Jo | 2D |
| JPEG | 2-20 herë | ~1 | gri 24-bit | po | 2D |
| Kompresimi rekurziv | 2-200 herë | 1.5 | gri 24-bit | po | 2D |
| fraktal | 2-2000 herë | 1000-10000 | gri 24-bit | po | 2.5D |
- tutorial
UPD. U detyrova të hiqja formatimin monospace. Një ditë të bukur, habraparser pushoi së perceptuari formatimin brenda para etiketat dhe kodin. I gjithë teksti është kthyer në një rrëmujë. Administrata e habrit nuk mund të më ndihmonte. Tani i pabarabartë, por të paktën i lexueshëm.
A keni dashur ndonjëherë të dini se si funksionon një skedar jpg? Tani le ta kuptojmë! Ngroheni përpiluesin tuaj të preferuar dhe redaktorin hex, le ta deshifrojmë këtë:
Posaçërisht mori 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ë pas do të jetë e lehtë për të kuptuar specifikimin.
Edhe pa e ditur se si ndodh kodimi, ne tashmë mund të nxjerrim diçka nga skedari.
- shënuesi i fillimit. Është gjithmonë në fillim të të gjithë skedarëve jpg.
Bajt pasojnë.
. Ky është një shënues që shënon fillimin e një seksioni komentesh. 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 e karaktereve ":" dhe ")", d.m.th. buzëqeshje e rregullt. Mund ta shihni në rreshtin e parë të anës së djathtë të redaktorit hex.
Pak teori
Shumë e shkurtër hap pas hapi:
Le të mendojmë për rendin në të cilin këto të dhëna mund të kodohen. Supozoni, në fillim, kanali Y është i koduar për të gjithë imazhin, 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. Ato janë të vendosura në skedar në rendin e mëposhtëm: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Leximi i një skedari
Pasi të kemi nxjerrë komentin, do të jetë e lehtë të kuptohet se:- Skedari ndahet në sektorë të paraprirë nga shënuesit.
- Shenjat janë 2 bajt të gjatë, me bajtin e parë.
- Pothuajse të gjithë sektorët e ruajnë gjatësinë e tyre në 2 bajt të ardhshëm pas shënuesit.
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01FF
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 00AE 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ë, kjo ë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, që do të thotë se imazhi është i koduar në metodën bazë. Është shumë e zakonshme. Por në internet, metoda progresive e njohur për ju nuk është më pak e popullarizuar, kur një imazh ngarkohet për herë të parë nga rezolucion të ulët, dhe më pas një foto normale. Kjo ju lejon të kuptoni se çfarë tregohet atje, pa pritur ngarkesë të plotë. Specifikimi përcakton disa të tjera, më duket, metoda 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 figurës: 0x10 = 16
Gjerësia e modelit: 0x10 = 16
Numri i komponentëve: 3. Më shpesh është Y, Cb, Cr.
Komponenti i parë:
ID: 1
Hollimi horizontal (H 1): 2
[_2]
Hollimi 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
Identifikuesi i tabelës së kuantizimit: 1
Tani shikoni se si të përcaktoni se sa i holluar është një imazh. Ne gjejmë H max \u003d 2 dhe V max \u003d 2. Kanali i do të shkatërrohet me H max /H i herë horizontalisht dhe V max /V i herë vertikalisht.
Shënuesi: DHT (grafiku i 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 koeficientit DC, 1 - Tabela e koeficientit 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ë.
Çdo kod ka një vlerë të lidhur me të, dhe ato janë të renditura 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ë kodeve të Huffman
Duhet të ndërtojmë një pemë binare nga tabela që morëm në seksionin DHT. Dhe tashmë nga kjo pemë ne do të njohim çdo kod. Vlerat shtohen sipas radhës në të cilën janë renditur 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ë nivelin e mësipërm dhe provojmë nga atje. Ju duhet të ndaleni në një nivel të barabartë me gjatësinë e kodit. Degët e majta korrespondojnë me vlerën 0, e djathta - 1.Koment:
Nuk ka nevojë të filloni nga lart çdo herë. Vlera e shtuar - kthehu në nivelin e mësipërm. A ekziston dega e duhur? Nëse po, ngjituni përsëri. Nëse jo, krijoni një degë të duhur dhe shkoni atje. Pastaj, nga atje, filloni të kërkoni 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ë vlerat 0x03 dhe 0x02
Në rrathë - vlerat e kodeve, nën rrathë - vetë kodet (do të shpjegoj se i morëm duke shkuar nga lart në secilën nyje). Është me kode të tilla (të kësaj dhe tabelave të tjera) që vetë përmbajtja e figurës kodohet.
Shënuesi: SOS (Fillimi i Skanimit)
Bajt në shenjë do të thotë "PO! Më në fund, shkuam drejtpërdrejt në analizimin e seksionit të imazhit të koduar! Megjithatë, seksioni quhet simbolikisht SOS. FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Gjatësia e kokës (jo e gjithë seksionit): 12 bajt.
Numri i komponentëve të skanimit. Kemi 3, nga një për Y, Cb, Cr.
Komponenti i parë:
Numri i komponentit të imazhit: 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 komponentit të imazhit: 2 (Cb)
[_1]
Komponenti i tretë:
Numri i komponentit të imazhit: 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) të dhënat e koduara.
0
Gjetja e koeficientit DC.
1.
Leximi i një sekuence bitash (nëse takojmë 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ës 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ë e barabartë me 0, atëherë koeficienti është 0, shkruajeni atë në tabelë dhe vazhdoni 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ë paraqitje binare- 1, pastaj lëreni siç është: DC_koefi = vlera. Përndryshe, konverto: DC_coef = 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ë lexojnë deri në këtë pikë dhe më kanë shkruar për këtë në një personal, do të marrin një plus në karma. Në rastin tonë, vlera e nyjës është 0x31.
Thithja e parë: 0x3 - ja sa zero duhet të shtojmë në matricë. Këta janë 3 koeficientë zero.
Thithja e dytë: 0x1 - gjatësia e koeficientit në bit. Lexoni 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ë, duhet të lexoni koeficientët AC derisa të pengoheni vlerë zero kodi, ose derisa të plotësohet matrica.
Në rastin tonë, ne do të 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ë të mbushura në të njëjtin model zigzag?
Arsyeja e përdorimit të kësaj porosie është e thjeshtë - sepse çfarë më shumë vlerë v dhe u, aq më pak i rëndësishëm është koeficienti S vu në transformimin e kosinusit diskret. Prandaj, në raportet e larta të kompresimit, koeficientët e parëndësishëm vendosen në 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 (të të njëjtit kanal)! Ju duhet të rregulloni 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 porositni. Ky rregull është i vlefshëm deri në fund të skedarit.
… 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 ka vetëm një matricë secila, koeficientët DC mund të lihen të paprekur.
Informatikë
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ë të duhurin. Së pari, ne skanuam komponentin e parë, komponentin e tij të imazhit = 1. Komponenti i imazhit me këtë ID përdor një matricë kuantizimi prej 0 (e kemi të parën nga dy). 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 të anasjelltë
Formula nuk duhet të jetë e vështirë*. S vu është matrica jonë e koeficientit që rezulton. u - kolonë, v - 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 një vizatim 16x16 në ekran, bëra një imazh 600x600 (nga rruga, ky ishte kopertina e albumit tim të preferuar 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ë. I vetmi zhgënjim ishte shpejtësia e shkarkimit. 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, duhet të gjeni 128 kosinus, 768 shumëzime dhe disa shtesa atje. Vetëm mendoni për këtë - pothuajse një mijë operacione të vështira për vetëm një kanal prej një piksel! Fatmirësisht, këtu ka vend për optimizim (pas shumë eksperimentesh, e zvogëlova 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ë foto 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 unë nuk hyj fare, për çfarë po flisni.
- 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 janë matricat tona të marra.
- 4 matrica Y, dhe nga një Cb dhe Cr secila, pasi holluam kanalet dhe 4 piksel Y korrespondojnë me nga një Cb dhe Cr secila. Prandaj, llogaritni kështu: YCbCrToRGB(Y ij , Cb , Cr )
YCbCr në RGB
R = Y + 1,402 * KrG = Y - 0,34414 * Cb - 0,71414 * Cr
B = Y + 1,772 * Cb
Mos harroni të shtoni 128 secila. Nëse vlerat shkojnë përtej intervalit, atëherë caktoni vlerat kufitare. Formula është e thjeshtë, por gjithashtu ha një pjesë të kohës së procesorit.
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
