Kuidas JPEG-formaat töötab

JPEG-formaat pilte leiavad aset meie digitaalses elus igal pool, kuid selle teadlikkuse taga peituvad algoritmid, mis eemaldavad detailid, mida inimsilma ei tajuta. Tulemuseks on kõrgeim visuaalne kvaliteet minimaalsete failisuurustega – kuid kuidas see kõik täpselt töötab? Vaatame, mida meie silmad ei näe!

On kerge võtta enesestmõistetavaks võimalus saata foto sõbrale, muretsemata selle pärast, millist seadet, brauserit või operatsioonisüsteemi ta kasutab – kuid nii see alati ei olnud. 1980. aastate alguseks oskasid arvutid hoida ja kuvada digitaalseid pilte, kuid parima viisi leidmiseks nende edastamiseks oli palju konkurentsivõimelisi ideid. Ei olnud võimalik lihtsalt saata pilti ühest arvutist teise ja loota, et kõik töötab.

Selle probleemi lahendamiseks kogunes 1986. aastal rahvusvaheline ekspertkomitee nimega „Ühine fotograafide ekspertgrupp“ (Joint Photographic Experts Group, JPEG), mis loodi rahvusvahelise standardimisorganisatsiooni (ISO) ja Rahvusvaheline Elektrotehnilise Komisjoni (IEC) koostöö raames – kahe rahvusvahelise standardimisorganisatsiooni, mille peakorter asub Genfis (Šveits).

Grupid, kes kutsusid end JPEG-iks, lõid 1992. aastal JPEG digitaalsete piltide tihendamise standardi. Igaüks, kes on Internetti kasutanud, on tõenäoliselt kokku puutunud JPEG- kodeerimisega pilte. See on kõige levinum viis piltide kodeerimiseks, edastamiseks ja salvestamiseks. Alates veebilehtedest kuni e-kirjade ja sotsiaalmeediani, kasutatakse JPEG-i miljardeid kordi päevas – praktiliselt iga kord, kui me vaatame pilti veebis või saadame selle edasi. Ilma JPEG-ita oleks veeb vähem elav, aeglasem ja tõenäoliselt vähem kassipilte!

See artikkel käsitleb seda, kuidas dekodeerida JPEG-pilti. Teisisõnu, sellest, mis on vajalik kokkusurutud andmete muundamiseks, mis hoitakse arvutis, pildiks, mis kuvatakse ekraanil. Sellest tasub teada mitte ainult seetõttu, et see on oluline arusaamiseks tehnoloogiast, mida me iga päev kasutame, vaid ka seetõttu, et avades kokkusurutuse tasemeid, saame paremini mõista tajumist ja nägemist ning millistele detailidele meie silmad kõige enam reageerivad.

Lisaks on pilte sellisel viisil redigeerida väga huvitav.

Vaadates JPEG-i sisse

Arvutis hoitakse kõike binaarsete numbrite järjestusena. Tavaliselt grupeeritakse neid bitte, nullid ja ühed, kaheksaks, moodustades baitid. Kui avate JPEG-pildi arvutis, peab midagi (brauser, operatsioonisüsteem, midagi muud) dekodeerima baitide, taastades algse pildi värvide nimekirjana, mida saab kuvada.

Kui Laadite alla selle armsa kassi foto ja avate selle tekstiredaktoris, näete hunnikut segaseid märke.

Siin kasutan Notepad++ faili sisu uurimiseks, kuna tavalised tekstiredaktorid, nagu Windowsi Notepad, rikuvad binaarfaili pärast salvestamist ja see lõpetab JPEG-formaadile vastamise.

Avades pildi tekstiredaktoris, segad te arvutit sedasi nagu segad oma ajus, kui hõõrud silmi ja hakata nägema värvilisi täppe!

Need täpid, mida näete, on tuntud kui fosfeenid, ega ole valguse stiimuli mõju või mõistuse poolt tekitatud hallutsinatsioonid. Need tekivad, kuna teie aju arvab, et kõik elektrilised signaalid silmanärvides edastavad teavet valguse kohta. Aju peab tegema selliseid oletusi, kuna ei ole võimalik teada, kas signaal on heli, nägemine või midagi muud. Kõik närvid kehas edastavad täiesti samu elektrilisi impulsside. Silmi vajutades saadate signaale, mis ei ole nägemislikud, kuid aktiveeritakse silma retseptoreid, mida teie aju tõlgendab - antud juhul valesti - kui midagi nägeliku. Te olete sõna otseses mõttes suuteline nägema survet!

Naljakas on mõelda, kui sarnased on arvutid ajule, kuid see on ka kasulik analoogia, mis illustreerib, kuidas andmete – mis edastatakse keha kaudu närvidega või salvestatakse arvutisse – tähendus sõltub nende tõlgendusest. Kõik binaarsed andmed koosnevad nullidest ja ühtedest, põhikoostisosadest, mis suudavad edastada igasugusest teavet. Teie arvuti arvab sageli, kuidas neid tõlgendada vihjete, näiteks faililaiendite, abil. Ja nüüd sunnime me seda tõlgendama neid tekstina, kuna just seda eeldab tekstiredaktor.

Kuna mõista, kuidas JPEG-i dekodeerida, peame nägema algseid signaale – binaarseid andmeid. Seda saab teha kuuesaksteheksandiku redigeerija abil või otse artikli originaali veebilehel! Seal on pilt, mille kõrval on tekstiväljas kõik selle baitid (välja arvatud päis), esitatud kümnendkujul. Võite neid muuta ja skript kodeerib ja väljastab uue pildi reaalajas.

Saame palju teada, lihtsalt mängides selle redigeerijaga. Näiteks, kas suudate öelda, millises järjekorras on pikslid?

Selles näites on veider see, et teatud numbrite muutmine ei mõjuta pilti üldse, aga näiteks, kui asendada number 17 nulliga esimeses reas, siis pilt läheb täiesti rikki!

Teised muudatused, näiteks number 7 asendamine 1988. reas numbriga 254, muudab värvi, kuid ainult järgmiste pikslite puhul.

Võib-olla on kõige kummalisem see, et mõned numbrid muudavad mitte ainult värvi, vaid ka pildi kuju. Muutke 70 12. reas 2-ks ja vaadake ülemist rida, et näha, mida ma mõtlen.

Ja olenemata sellest, millist JPEG pilti te kasutate, leiate alati need müstilised šakhmattikandid bite redigeerimise käigus.

Redigeerijaga mängides on raske mõista, kuidas see pilt nende baitide hulgast taasloodakse, kuna JPEG-i tihendamine koosneb kolmest erinevast tehnoloogiast, mida rakendatakse järjestikku kihtide kaupa. Uurime igaüht neist eraldi, et avada nähtud müstilist käitumist.

Kolm JPEG-i tihendamise taset:

1. Värvialane subdiskreetimine.
2. Diskreetne kosinuse transformatsioon ja diskreetimine.
3. Pikade jada kodeerimine, delt ja Huffman

Ette kujutaksid ette kokkusurumise ulatust, pane tähele, et ülalolev pilt sisaldab 79 819 numbrit, see tähendab umbes 79 Kb. Kui me oleksime seda ladustanud ilma kokkusurumiseta, oleks iga piksel nõudnud kolme numbrit – punase, rohelise ja sinise komponendi jaoks. See oleks olnud 917 700 numbrit või umbes 917 Kb. JPEG kokkusurumise tõttu vähenes lõplik fail rohkem kui 10 korda!

Tegelikult saab seda pilti veelgi tugevamalt kokku suruda. Allpool on kaks pilti kõrval – parempoolne foto on kokku surutud 16 Kb-ni, mis on 57 korda vähem kui kokku surumata versioon!

Kui tähelepanelikult vaadata, siis on näha, et need pildid ei ole identsed. Mõlemad on JPEG kokkusurumisega pildid, kuid parem on mahtude poolest oluliselt väiksem. Samuti näeb see veidi halvem välja (vaata taustavärvide ruute). Seetõttu nimetatakse JPEG-d ka kadudega kokkusurumiseks; kokkusurumise protsessis muutub pilt ja kaotab teatud detaile.

1. Värvisubdisgustimine

Siin on pilt, millel on rakendatud ainult esimest kokkusurutuse taset.

(Interaktiivne versioon – originaalis artikkel). Ühe numbri eemaldamine hävitab kõik värvid. Kuid kui eemaldada täpselt kuus numbrit, ei mõjuta see pilti praktiliselt.

Nüüd on numbreid kergem dešifreerida. See on peaaegu lihtne värviliste loend, kus iga bait muudab täpselt ühte pikslit, kuid samas on see juba kaks korda väiksem kui kokku surumata pilt (mis oleks umbes 300 Kb selle vähendatud suuruse korral). Kas arvate, miks?

On näha, et need numbrid ei tähista standardseid punase, rohelise ja sinise komponente, sest kui asendada kõik numbrid nullidega, saame rohelise pildi (mitte valge).

See on sellepärast, et need baitid tähistavad Y (heleduse),

Cb (suhteline sinisus),

ja Cr (suhteline punasus) pilti.

Miks mitte kasutada RGB? Lõppude lõpuks töötab enamiku tänapäevaste ekraanide puhul just nii. Teie monitor saab kuvada mis tahes värvi, sealhulgas punase, rohelise ja sinise värvi erineva intensiivsusega iga pikseli jaoks. Valge tekib, kui kõik kolm on täielikult heledad, ja must – kui need on välja lülitatud.

See sarnaneb ka inimsilma tööle. Meie silmade värviretseptorid nimetatakse "kobaradeks«, ja jagunevad need kolme tüüpi, millest igaüks on tundlikum kas punaste, roheliste või siniste värvide suhtes [S-tüüpi kolvikesed on tundlikud violetsinises (S inglise keeles Short — lühikesed lainepikkused), M-tüüpi – rohelise-kollase (M inglise keeles Medium — keskmised lainepikkused) ja L-tüüpi – kollase-punase (L inglise keeles Long — pikad lainepikkused) spektri osadele. Nende kolme tüüpi kolvike (ja pulgad, mis on tundlikud smaragdrohelises spektriosas) olemasolu annab inimesele värvitaju. / märkus tõlkes]. Pulgad, teine tüüp fotoretseptoreid meie silmades, suudavad tabada muutusi heleduses, kuid on palju tundlikumad värvi suhtes. Meie silmades on umbes 120 miljonit pulka ja vaid 6 miljonit kolvikut.

Seetõttu märkavad meie silmad muudatusi heleduses palju paremini kui muudatusi värvis. Kui eraldada värv heledusest, saab veidi värvi vähendada ja keegi ei pane seda tähele. Värvi aladišreetimine on protsess, mille käigus esitatakse pildi värvikomponendid madalama eraldusvõimega võrreldes heleduskomponentidega. Ülaltoodud näites on igas pikslis täpselt üks Y komponent ja igas nelja piksliga grupis on täpselt üks Cb ja üks Cr komponent. Seetõttu sisaldab pilt neli korda vähem värviinfot kui originaalis.

Värviruum YCbCr ei kasutata mitte ainult JPEG-des. See on algselt välja mõeldud 1938. aastal televiisorite jaoks. Mitte kõigil ei olnud värvilist televiisorit, seega võimaldas värvi ja heleduse eraldamine kõigil saada sama signaali, samas kui värvitud televiisorid kasutasid lihtsalt ainult heleduse komponenti.

Seetõttu hävitab ühe numbri eemaldamine redigeerijast täielikult kõik värvid. Komponendid salvestatakse kujul Y Y Y Y Cb Cr (tegelikult ei pea see olema tingimata sellises järjekorras – salvestamise järjekord määratakse faili päises). Esimese numbri eemaldamine toob kaasa selle, et esimene Cb väärtus tõlgendatakse kui Y, Cr kui Cb, ja see toob kaasa dominoefekti, mis muudab kõiki pildi värve.

JPEG spetsifikatsioon ei nõua YCbCr kasutamist. Kuid enamikus failides kasutatakse seda, kuna see annab subdiskreetimise järel parema kvaliteediga pilte võrreldes RGB-ga. Aga te ei pea mind sõna-sõnalt uskuma. Vaadake ise allolevas tabelis, milline välja näeb iga eraldi komponendi subdiskreetimine nii RGB kui ka YCbCr puhul.

(Interaktiivne versioon – originaalis artiklid).

Sinise eemaldamine ei ole nii märgatav kui punase või rohelise. See tuleneb sellest, et teie silmades on umbes 64% punaste, 32% roheliste ja 2% siniste koonusrakke.

Komponendi Y subdiskreetimine (vasakul all) on kõige paremini nähtav. Iga väike muutus on märgatav.

Pildi konverteerimine RGB-st YCbCr-iks ei vähenda faili suurust, kuid lihtsustab vähem nähtavate detailide leidmist, mida saab eemaldada. Kaod, millel on kahjulik mõju, toimuvad teises etapis. Selle aluseks on idee esitada andmed kompaktsemal kujul.

2. Diskreetne kosinusmuundamine ja diskreetimine

See kompressiooni tase määrab peaaegu täielikult JPEG-i olemuse. Pärast värvide konverteerimist YCbCr-iks componeeritakse komponendid eraldi, seetõttu saame keskenduda ainult Y-komponendile. Ja sellised näevad välja Y-komponendi baitid pärast selle taseme rakendamist.

(Interaktiivne versioon – originaalis artiklid). Interaktiivses versioonis klikkimine pikslile kerib redigeerijat reale, mida see tähistab. Proovige eemaldada numbreid lõpust või lisada mõnele numbrile mõned nullid.

Esmapilgul tundub, et tegemist on väga kehva kompressiooniga. 100 000 piksliga pildis on Y-komponentide heleduse määramiseks vajalik 102 400 numbrit - see on halvem kui juhul, kui ei compressitagi!

Kuid pidage meeles, et enamik neist numbritest on nullid. Lisaks saab kõik need nullid ridade lõpus eemaldada, ilma et see pilti muudaks. Jääb umbes 26 000 numbrit, mis on juba peaaegu neli korda vähem!

Selle taseme juures peitubki šahhi mustrite saladus. Erinevalt teistest nähtustest, mida me oleme näinud, ei ole nende mustrite ilmumine viga. Need on kogu pildi ehitusplokid. Igas redigeerija reas on täpselt 64 numbrit, diskreetse kosinusmuundamise (DCT) koefitsiendid, mis vastavad 64 ainulaadse mustri intensiivsusele.

Need patterns are formed based on the cosine chart. Here’s what some of them look like:

8 out of 64 coefficients

Below is an image showing all 64 patterns.

(Interaktiivne versioon – originaalis artiklid).

These patterns are significant as they form the basis of 8x8 sized images. If you are unfamiliar with linear algebra, this means that any 8x8 image can be obtained from these 64 patterns. DCT is the process of breaking images into 8x8 blocks and transforming each block into a combination of these 64 coefficients.

The fact that any image can be composed of 64 specific patterns seems magical. However, it’s the same as saying that any place on Earth can be described by two numbers – latitude and longitude [with specifying hemispheres / translator's note]. We often consider the Earth's surface to be two-dimensional, so we only need two numbers. An 8x8 image has 64 dimensions, so we need 64 numbers.

It’s still unclear how this helps us in terms of compression. If we need 64 numbers to represent an 8x8 image, why is this method better than just storing 64 brightness components? We do it for the same reason we transformed three RGB numbers into three YCbCr numbers: it allows us to remove imperceptible details.

It's difficult to see exactly which details are removed at this stage since JPEG applies DCT to 8x8 blocks. However, no one prevents us from applying it to an entire image. Here’s what DCT looks like on the Y component when applied to the whole image:

From the end, we can remove over 60,000 numbers virtually without noticeable changes to the photo.

However, note that if we zero out the first five numbers, the difference will be obvious.

The numbers at the beginning denote low-frequency changes in the image, which our eyes catch the best. The numbers closer to the end indicate high-frequency changes that are harder to notice. To "see what is not visible to the eye," we can isolate these high-frequency details by zeroing out the first 5,000 numbers.

We see all areas of the image where the most change occurs from pixel to pixel. The cat's eyes, its whiskers, the plush blanket, and shadows in the lower left corner stand out. We can go further by zeroing out the first 10,000 numbers:

20 000:

40 000:

60 000:

Need to transform high-frequency JPEG details and remove them at the compression stage. Color conversion to DCT coefficients is lossless. Losses occur at the discretization step, where high-frequency or near-zero values are eliminated. When you lower the quality of JPEG saving, the program increases the threshold number of values removed, resulting in a smaller file size but making the image more pixelated. This is why the image in the first section, which was 57 times smaller, appeared this way. Each 8x8 block was represented by far fewer DCT coefficients compared to a higher-quality version.

You can create an amazing effect like gradual streaming of images. You can display a blurred image that becomes increasingly detailed as more coefficients are downloaded.

Here's, just for interest, what happens when using only 24,000 numbers:

Or just 5,000:

Very blurry, but somewhat recognizable!

3. Run-length encoding, delta, and Huffman

So far, all stages of compression have been lossy. The last stage, on the other hand, is lossless. It does not remove information but significantly reduces file size.

How can you compress something without discarding information? Imagine how we could describe a simple black rectangle of 700 x 437.

JPEG uses 5,000 numbers for this, but much better results can be achieved. Can you imagine a coding scheme that describes such an image in as few bytes as possible?

The minimal scheme I could come up with uses four: three to denote color, and the fourth – how many pixels have that color. The idea of representing repeating values in such a compressed way is called run-length encoding. It is lossless since we can restore the encoded data in its original form.

JPEG-faili suurus musta ristküliku puhul on palju suurem kui 4 baiti – pidage meeles, et DCT tasemel rakendatakse tihendamist 8x8 pikslite plokkide kaupa. Seega on meil vähemalt vajalik üks DCT koefitsient iga 64 piksli kohta. Üks on vajalik, sest selle asemel, et salvestada üks DCT koefitsient, millele järgneb 63 nulli, võimaldab järjestuste kodeerimine meil salvestada ühe numbri ja märkida, et "kõik teised – on nullid".

Delta-kodeerimine on tehnika, kus iga bait sisaldab erinevust mõnest väärtusest, mitte absoluutset suurust. Seetõttu muudab teatud baitide muutmine kõigi teiste pikslite värvi. Näiteks, selle asemel, et salvestada

12 13 14 14 14 13 13 14

Me võiksime alustada 12-st ja seejärel lihtsalt näidata, kui palju tuleb juurde lisada või ära võtta, et saada järgmine number. Ja see järjestus delta-kodeerimises omandab järgmise kuju:

12 1 1 0 0 -1 0 1

Töödeldud andmed ei muutu väiksemaks algsetest, kuid neid on kergem tihendada. Delta-kodeerimise rakendamine enne järjestuste kodeerimist võib olla suureks abiks, jäädes samas kaotustatud tihendamiseks.

Delta-kodeerimine on üks väheseid tehnikaid, mida rakendatakse väljaspool 8x8 plokke. 64 DCT koefitsiendist on üks lihtsalt pidev lainefunktsioon (ühtlane värv). See esindab iga ploki keskmist heledust valgustuskomponentide jaoks või keskmist sinisust Cb komponentide jaoks, ja nii edasi. Iga DCT-ploki esimene väärtus nimetatakse DC- väärtuseks, ja iga DC- väärtus läbib delta-kodeerimist eelnevate väärtuste suhtes. Seetõttu mõjutab esimese ploki heleduse muutmine kõiki plokke.

Viimane mõistatus jääb: kuidas ühe numbri muutmine rikub kogu pildi? Seni ei ole tihendusastmetel olnud selliseid omadusi. Vastus peitub JPEG-i pealkirjas. Esimesed 500 baiti sisaldavad metaandmeid pildi kohta – laiust, kõrgust ja muud, ja seni, kuni me nendega ei töötanud.

Ilma pealkirjata on JPEG-dekodeerimine peaaegu võimatu (või väga keeruline). See näeks välja nagu ma püüaksin teile maali kirjeldada ja hakkan isegi sõnu leiutama, et edasi anda oma mulje. Kirjeldus on tõenäoliselt väga kokkusurutud, kuna ma võin leiutada sõnu just selle tähendusega, mida soovin edastada, kuid kõigile teistele ei ole need tõenäoliselt mõistetavad.

Kuulub jaburana, kuid just nii see toimub. Iga JPEG-pilt komprimeeritakse spetsiifiliste koodide abil, mis on just sellele pildile omased. Koodide sõnastik salvestatakse päisesse. Seda tehnikat nimetatakse „Huffman'i koodiks“ ja sõnastikku – Huffman'i tabeliks. Päises on tabel märgitud kahe baitiga – 255 ja seejärel 196. Igal värvikoos komponendil võib olla oma tabel.

Muutused tabelites mõjutavad radikaalselt igat pilti. Hea näide on vahetada 15. real 1 12 vastu.

See juhtub seetõttu, et tabelites on öeldud, kuidas tuleb lugeda eraldi bitte. Siiani oleme töötanud ainult binaarsete arvudega kümnendsüsteemis. Kuid see peidab meist fakti, et kui soovite hoida arvu 1 ühes baitis, siis näeb see välja nagu 00000001, kuna igas baitis peab olema täpselt kaheksa bitti, isegi kui vajate neist ainult ühte.

Potentsiaalselt on see suur ruumipaiskumine, kui teil on palju väikeseid numbreid. Huffman'i kood on tehnika, mis võimaldab meil leevendada nõuet, et iga number peab võtma kaheksa bitti. See tähendab, et kui näete kahte bitti:

234 115

Siis võivad need, sõltuvalt Huffman'i tabelist, olla kolm numbrit. Nende väljavõtmiseks peate esmalt jagama need eraldi bittideks:

11101010 01110011

Siis pöördume tabeli poole, et mõista, kuidas neid rühmitada. Näiteks võivad need olla esimesed kuus bitti (111010), või 58 kümnendsüsteemis, millele järgneb viis bitti (10011), või 19, ja lõpuks viimased neli bitti (0011), või 3.

Seetõttu on selles faasis tihendamiseks väga keeruline baite mõista. Baiid ei esinda seda, mida tundub. Ma ei hakka süvenema tabeli töö detailidesse selles artiklis, kuid materjale selle teema kohta internetis piisab.

Üks huvitav trikk, mida oskades teha, on eraldada JPEG-päis ja hoida seda eraldi. Põhimõtteliselt tähendab see, et faili saate lugeda ainult teie. Facebook teeb seda, et faile veelgi rohkem vähendada.

Mis veel on võimalik teha – tabelit Huffman'i täiusta just natuke. Teiste jaoks näeb see välja nagu rikutud pilt. Ja ainult teie teate maagilist varianti selle taastamiseks.

Kokkuvõtteks: mis siis on vajalik JPEG-dekodeerimiseks? On vajalik:

1. Eraldada Huffman'i tabel (tabelid) päisest ja dekodeerida bitid.
2. Tõmmake välja diskreetse kosinuste ümberarvestamise koefitsiendid iga värvi ja heleduse komponendi jaoks iga 8x8 ploki puhul, tehes tagasi pikkade seeriate kodeerimise ja delta ümberarvestused.
3. Kombineerige kosinused koefitsientide põhjal, et saada iga 8x8 ploki jaoks piksliväärtused.
4. Skaalake värvikomponente, kui on tehtud aldisreteerimine (see teave on pealkirjas).
5. Transformeerige saadud YCbCr väärtused igale pikslile RGB-ks.
6. Näidake pilti ekraanil!

Tõsine ülesanne tavalise kassifoto vaatamiseks! Kuid see, mis mulle selle juures meeldib, on see, et see näitab, kui inimese keskne JPEG-tehnoloogia tegelikult on. See põhineb meie tajumise eripäradel, võimaldades saavutada palju paremat tihendust kui tavapärased tehnoloogiad. Ja nüüd, mõistes, kuidas JPEG töötab, on võimalik kujutada, kuidas neid tehnoloogiaid saab üle kanda teistesse valdkondadesse. Näiteks võib delta kodeerimine videos anda tõsise faili suuruse vähendamise, kuna seal on sageli suuri piirkondi, mis ei muutu kaadrist kaadrisse (näiteks taust).

Artiklis kasutatud kood, on avatud ja sisaldab juhiseid, kuidas asendada pilte enda omadustega.

Allikas: habr.com