How the JPEG format works

JPEG-bilder finnes overalt i vårt digitale liv, men bak dette laget av bevissthet skjuler det seg algoritmer som eliminerer detaljer som ikke oppfattes av det menneskelige øyet. Resultatet er strålende bildekvalitet med minimal filstørrelse – men hvordan fungerer egentlig dette? La oss se nærmere på hva øynene våre ikke ser!

Det er lett å ta for gitt muligheten til å sende et bilde til en venn uten å bekymre seg for hvilken enhet, nettleser eller operativsystem de bruker – men slik har det ikke alltid vært. På begynnelsen av 1980-tallet kunne datamaskiner lagre og vise digitale bilder, men det var mange konkurrerende ideer om den beste måten å gjøre dette på. Man kunne ikke bare sende et bilde fra én datamaskin til en annen og håpe at alt ville fungere.

For å løse dette problemet ble det i 1986 opprettet et ekspertutvalg fra hele verden kalt «Joint Photographic Experts Group, JPEG» (Joint Photographic Experts Group, JPEG), dannet under et samarbeid mellom Den internasjonale standardiseringsorganisasjonen (ISO) og Den internasjonale elektrotekniske kommisjonen (IEC) – to internasjonale standardiseringsorganisasjoner med hovedkontor i Genève (Sveits).

Gruppen av mennesker kalt JPEG etablerte JPEG-kompressionsstandarden for digitale bilder i 1992. Enhver som har brukt internett, har sannsynligvis støtt på bilder i JPEG-koding. Dette er den mest utbredte metoden for koding, sending og lagring av bilder. Fra nettsider til e-post og sosiale medier, brukes JPEG milliarder av ganger om dagen – omtrent hver gang vi ser et bilde på nettet eller sender det. Uten JPEG ville nettet vært mindre livlig, tregere, og sannsynligvis mindre fullt av kattbilder!

Denne artikkelen handler om hvordan man dekoder et JPEG-bilde. Med andre ord, hva som kreves for å konvertere komprimerte data som lagres på datamaskinen til et bilde som vises på skjermen. Dette er viktig å vite, ikke bare fordi det er essensielt for å forstå teknologien vi bruker daglig, men også fordi å avdekke komprimeringslagene gir oss en bedre forståelse av persepsjon og syn, samt hvilke detaljer øynene våre er mest følsomme overfor.

I tillegg er det veldig interessant å eksperimentere med bilder på denne måten.

Se inn i JPEG

På datamaskinen lagres alt som en sekvens av binære tall. Vanligvis grupperes disse bitene, nuller og enere, i grupper på åtte for å danne bytes. Når du åpner et JPEG-bilde på datamaskinen, må noe (nettleseren, operativsystemet, eller noe annet) dekode bytes, og gjenskape det originale bildet som en liste av farger som kan vises.

Hvis du laster ned dette søte kattebildet og åpner det i en tekstredigerer, vil du se en haug med uforståelige tegn.

Her bruker jeg Notepad++ for å undersøke innholdet i filen, fordi vanlige tekstredigerere, som Notepad i Windows, vil ødelegge den binære filen etter lagring, og den vil ikke lenger oppfylle JPEG-formatet.

Ved å åpne bildet i en tekstredigerer forvirrer du datamaskinen, akkurat som du forvirrer hjernen din når du gnir øynene og begynner å se fargede flekker!

Disse flekkene du ser er kjent som fosefen, og er ikke et resultat av lysstimuli eller hallusinasjoner skapt av sinnet. De oppstår fordi hjernen din antar at alle elektriske signaler i øynenes nerver overfører informasjon om lys. Hjernen må gjøre slike antagelser, ettersom det ikke er mulig å vite om signalet er lyd, syn eller noe annet. Alle nerver i kroppen overfører helt identiske elektriske impulser. Når du trykker på øynene, sender du signaler som ikke er visuelle, men som aktiverer øyets reseptorer, noe hjernen din tolker – i dette tilfellet feilaktig – som noe visuelt. Du kan bokstavelig talt se trykket!

Det er morsomt å tenke på hvor lik datamaskiner er på hjernen, men det er også en nyttig analogi som illustrerer hvor mye betydningen av data - som overføres gjennom kroppen av nerver, eller lagres på datamaskinen - avhenger av hvordan de tolkes. All binær data består av nuller og enere, grunnleggende komponenter som kan overføre informasjon av enhver art. Datamaskinen din gjetter ofte hvordan man skal tolke dem ved hjelp av ledetråder, som for eksempel filutvidelser. Og nå ber vi den om å tolke dem som tekst, ettersom dette er det tekstbehandleren forventer.

For å forstå hvordan JPEG dekodes, må vi se de opprinnelige signalene - den binære dataen. Dette kan gjøres ved hjelp av en heksadesimal redigerer, eller rett på websiden til den opprinnelige artikkelen! Der finnes det et bilde, ved siden av hvilket alle byte (unntatt headeren) er oppført i tekstfeltet, representert i desimal form. Du kan endre dem, og skriptet vil omkode og gi et nytt bilde i sanntid.

Du kan lære mye bare ved å spille med denne redigereren. For eksempel, kan du si i hvilken rekkefølge pikslene lagres?

Det merkelige med dette eksemplet er at endring av noen tall ikke påvirker bildet i det hele tatt, men for eksempel, hvis du erstatter tallet 17 med 0 i den første linjen, vil bildet bli helt ødelagt!

Andre endringer, for eksempel å erstatte 7 i linje 1988 med tallet 254, endrer fargene, men bare for de påfølgende pikslene.

Kanskje det mest merkelige er at noen tall endrer ikke bare fargen, men også formen på bildet. Endre 70 i linje 12 til 2 og se på den øverste raden i bildet for å se hva jeg mener.

Og uansett hvilket JPEG-bilde du bruker, vil du alltid finne disse mystiske sjakkmønstrene når du redigerer byte.

Når du leker med redigereren, er det vanskelig å forstå hvordan bildet rekonstruksjonere fra disse byte, siden JPEG-kompresjon består av tre forskjellige teknologier som brukes sekvensielt på nivåer. Vi vil utforske hver enkelt for å avdekke den mystiske oppførselen vi observerer.

Tre nivåer av JPEG-kompresjon:

1. Fargesubdiscretisering.
2. Diskret cosinus-transformasjon og diskretisering.
3. Koding av lengder, delta og Huffman

For you to grasp the scale of compression, note that the image above represents 79,819 numbers, or about 79 KB. If we stored it uncompressed, each pixel would require three numbers – for the red, green, and blue components. This would amount to 917,700 numbers, or approximately 917 KB. As a result of JPEG compression, the final file size has been reduced by more than 10 times!

In fact, this image can be compressed even more. Below are two images side by side – the photo on the right has been compressed to 16 KB, which is 57 times smaller than the uncompressed version!

If you take a closer look, you will notice that these images are not identical. Both are JPEG compressed images, but the one on the right is significantly smaller. It also looks a bit worse (look at the squares of the background colors). That’s why JPEG is also referred to as lossy compression; during compression, the image changes and loses some details.

1. Color Subsampling

Here is an image using only the first level of compression.

(Interactive version – in the original article). Removing a single number disrupts all colors. However, if six numbers are removed, it has virtually no impact on the image.

Now the numbers are slightly easier to decipher. It’s almost a simple list of colors, in which each byte changes exactly one pixel, and yet it is already half the size of the uncompressed image (which would take about 300 KB in this reduced size). Can you guess why?

It can be seen that these numbers do not represent the standard red, green, and blue components, since replacing all the numbers with zeros would yield a green image (not white).

This is because these bytes represent Y (luminance),

Cb (chroma blue),

and Cr (chroma red) of the image.

Why not use RGB? After all, this is how most modern displays operate. Your monitor can display any color by varying the intensity of red, green, and blue for each pixel. White is achieved by turning all three on to full brightness, while black is the result of turning them off.

This is also very similar to how the human eye works. The color receptors in our eyes are called “cones«, og er delt inn i tre typer, der hver er mer sensitiv for rødt, grønt eller blått [S-type tapper er sensitive i violett-blått (S fra engelsk Short – kort bølgelengde spektrum), M-type – i grønn-gul (M fra engelsk Medium – middels bølgelengde), og L-type – i gul-rød (L fra engelsk Long – lang bølgelengde) deler av spektret. Tilstedeværelsen av disse tre typene tapper (og staver som er sensitive i smaragdgrønt) gir mennesker fargesyn. / overs. anm.]. Staver, en annen type fotoreceptorer i øynene våre, kan oppdage endringer i lysstyrke, men er mye mer sensitiv for farge. Det finnes omtrent 120 millioner staver og bare 6 millioner tapper i øynene våre.

Derfor er øynene våre mye bedre til å oppdage endringer i lysstyrke enn endringer i farge. Hvis man skiller farge fra lysstyrke, kan man fjerne litt farge, og ingen vil merke det. Fargesubdiscretisering er prosessen med å representere fargekomponentene i et bilde med lavere oppløsning sammenlignet med lysstyrkekomponentene. I eksempelet ovenfor har hvert piksel nøyaktig én Y-komponent, mens hver enkelt gruppe av fire piksler har nøyaktig én Cb-komponent og én Cr. Derfor inneholder bildet fire ganger mindre fargeinformasjon enn det opprinnelige.

Fargeområdet YCbCr brukes ikke bare i JPEG. Det ble først utviklet i 1938 for kringkasting. Ikke alle hadde farge-TV-er, så separasjonen av farge og lysstyrke gjorde det mulig for alle å motta det samme signalet, mens farge-TV-er uten farge bare brukte lysstyrkekomponenten.

Derfor vil fjerning av ett tall fra redaktøren fullstendig ødelegge alle farger. Komponentene lagres som Y Y Y Y Cb Cr (i virkeligheten, ikke nødvendigvis i den rekkefølgen - rekkefølgen spesifiseres i filoverskriften). Å fjerne det første tallet vil føre til at den første Cb-verdien blir oppfattet som Y, Cr som Cb, og det vil totalt sett gi en dominoreffekt som endrer alle fargene i bildet.

JPEG-spesifikasjonen forplikter deg ikke til å bruke YCbCr. Men i de fleste filer brukes den, da den gir bilder av bedre kvalitet etter subprøving sammenlignet med RGB. Men du trenger ikke å ta mitt ord for det. Se selv i tabellen nedenfor hvordan subprøvingen av hver enkelt komponent vil se ut både i RGB og YCbCr.

(Interactive version – in the original artikler).

Fjerning av blått er ikke så merkbart som rødt eller grønt. Alt fordi 64% av de seks millionene staverne i øynene dine er sensitive for rødt, 32% for grønt og 2% for blått.

Subprøving av Y-komponenten (nederst til venstre) er mest synlig. Selv små endringer er merkbare.

Å konvertere et bilde fra RGB til YCbCr reduserer ikke filstørrelsen, men gjør det lettere å finne mindre synlige detaljer som kan fjernes. Tapende komprimering skjer i det andre stadium. Den er basert på ideen om å representere data i en mer komprimerbar form.

2. Diskret kosinustransformasjon og subprøving

Dette kompresjonsnivået definerer i stor grad essensen av JPEG. Etter fargekonverteringen til YCbCr, komprimeres komponentene individuelt, så vi kan fokusere på Y-komponenten. Her er hvordan byte av Y-komponenten ser ut etter påføring av dette nivået.

(Interactive version – in the original artikler). I den interaktive versjonen, klikker du på en piksel for å rulle redigereren til linjen som representerer den. Prøv å fjerne tall fra slutten eller legge til noen nuller til et bestemt tall.

Ved første øyekast ser det ut som en veldig dårlig komprimering. I bildet er det 100 000 piksler, og for å representere lysstyrken deres (Y-komponenten) kreves 102 400 tall – dette er verre enn å ikke komprimere i det hele tatt!

Legg imidlertid merke til at de fleste av disse tallene er null. Dessuten kan alle disse nullene på slutten av linjene fjernes uten å endre bildet. Det gjenstår omtrent 26 000 tall, og det er nesten fire ganger mindre!

På dette nivået ligger hemmeligheten bak sjakkmønstrene. I motsetning til andre effekter vi har sett, er fremveksten av disse mønstrene ikke en feil. De er byggeklossene i hele bildet. Hver linje i redigeringsprogrammet inneholder nøyaktig 64 tall, koeffisientene til den diskrete kosinus-transformasjonen (DCT), som tilsvarer intensiteten til 64 unike mønstre.

Disse mønstrene dannes basert på en kosinusgraf. Slik ser noen av dem ut:

8 av 64 koeffisienter

Nedenfor er et bilde som viser alle 64 mønstre.

(Interactive version – in the original artikler).

Disse mønstrene har spesiell betydning, da de danner basis for bilder i størrelse 8x8. Hvis du ikke er kjent med lineær algebra, betyr det at ethvert bilde i størrelse 8x8 kan gjengis fra disse 64 mønstrene. DCT er prosessen med å dele opp bilder i blokker på 8x8 og omforme hver blokk til en kombinasjon av disse 64 koeffisientene.

At et bilde kan konstrueres fra 64 bestemte mønstre virker magisk. Imidlertid er det det samme som å si at ethvert punkt på jorden kan beskrives med to tall – breddegrad og lengdegrad [med separate halvkuler / merkn. oversetter]. Vi anser ofte jordens overflate som todimensjonal, så vi trenger bare to tall. Et 8x8-bilde har 64 dimensjoner, så vi trenger 64 tall.

Det er fortsatt uklart hvordan dette hjelper oss med hensyn til komprimering. Hvis vi trenger 64 tall for å representere et 8x8-bilde, hvorfor vil ikke denne metoden være bedre enn bare å lagre 64 lysstyrkekomponenter? Vi gjør dette av samme grunn som vi konverterte tre RGB-tall til tre YCbCr-tall: det lar oss fjerne usynlige detaljer.

Det er vanskelig å se hvilke detaljer som faktisk blir fjernet på dette stadiet, siden JPEG anvender DCT på blokker av 8x8. Imidlertid er ingen hindret i å anvende det på et helt bilde. Slik ser DCT ut for komponenten Y når den anvendes på et helt bilde:

Fra slutten kan vi fjerne over 60 000 tall uten merkbare endringer på bildet.

Vær imidlertid oppmerksom på at dersom vi nullstiller de første fem tallene, vil forskjellen være åpenbar.

Tallene i starten representerer endringer i lav frekvens i bildet, og øynene våre fanger dem best. Tallene nærmere slutten representerer endringer i høy frekvens, som er vanskeligere å legge merke til. For å 'se det som ikke er synlig for det blotte øye,' kan vi isolere disse høyfrekvente detaljene ved å nullstille de første 5000 tallene.

Vi ser alle områdene i bildet hvor det skjer størst endring fra piksel til piksel. Øynene til katten, dens skjegg, det fluffy teppet og skygger i nederste venstre hjørne blir fremhevet. Vi kan gå enda lenger ved å nullstille de første 10 000 tallene:

20 000:

40 000:

60 000:

Disse høye frekvensdelene i JPEG fjernes under kompresjonen. Fargeomformingen til DCT-koeffisienter er tapsfri. Tap skjer på diskretiseringssteget, der høye frekvenser eller verdier nær null fjernes. Når du reduserer kvaliteten på JPEG-lagringen, øker programmet terskelen for antall verdier som fjernes, noe som gir en reduksjon i filstørrelse, men gjør bildet mer pikselert. Derfor så bildet i første avsnitt ut slik, da det var 57 ganger mindre. Hver 8x8 blokk ble representert med betydelig færre DCT-koeffisienter sammenlignet med en høyere kvalitetsversjon.

Du kan oppnå en kult effekt som gradvis strømmende bildeoverføring. Du kan vise et uskarpt bilde som blir mer detaljert ettersom flere koeffisienter lastes ned.

Her, bare for moro skyld, er hva som skjer med bare 24 000 tall:

Eller bare 5 000:

Veldig uskarpt, men på en måte gjenkjennelig!

3. Koding av løpelengder, delta og Huffman

Så langt har alle kompresjonstrinn vært med tap. Det siste trinnet derimot, er tapsfritt. Det fjerner ikke informasjon, men reduserer filstørrelsen betydelig.

Hvordan kan man komprimere noe uten å kaste bort informasjon? Forestill deg hvordan vi ville beskrevet et enkelt svart rektangel på 700 x 437.

JPEG bruker 5000 tall for dette, men man kan oppnå mye bedre resultater. Kan du forestille deg et kodeord som beskriver et slikt bilde med så få byte som mulig?

Det minimumsformatet jeg klarte å komme opp med, bruker fire: tre for å indikere fargen, og den fjerde – hvor mange piksler har den fargen. Ideen om å representere gjentatte verdier på en slik komprimert måte kalles koding av løpelengder. Det er tapsfritt, siden vi kan gjenopprette de kodede dataene til deres opprinnelige tilstand.

JPEG-filen med det svarte rektangelet er mye større enn 4 byte – husk at ved DCT blir komprimering anvendt på blokker på 8x8 piksler. Derfor trenger vi minst én DCT-koeffisient for hver 64 piksler. Vi trenger én, fordi i stedet for å lagre én DCT-koeffisient etterfulgt av 63 nuller, lar løpende koding oss lagre ett tall og indikere at "alle de andre er nuller."

Delta-koding er en teknikk der hver byte inneholder forskjellen fra en verdi, snarere enn en absolutt størrelse. Derfor påvirker redigering av bestemte byte fargen til alle de andre pikslene. For eksempel, i stedet for å lagre

12 13 14 14 14 13 13 14

Vi kunne startet med 12, og deretter bare angi hvor mye som må legges til eller trekkes fra for å få neste nummer. Og denne sekvensen i delta-koding får utseendet:

12 1 1 0 0 -1 0 1

De transformerede dataene blir ikke mindre enn de opprinnelige, men de er lettere å komprimere. Bruken av delta-koding før løpende koding kan være svært nyttig, samtidig som det forblir tapsfri komprimering.

Delta-koding er en av de få teknikkene som brukes utenfor 8x8-blokkene. Av de 64 DCT-koeffisientene er én bare en konstant bølgefunksjon (en ensfarget farge). Den representerer gjennomsnittlig lysstyrke for hver blokk for lysstyrkekomponentene, eller gjennomsnittlig blåhet for Cb-komponentene, og så videre. Den første verdien for hver DCT-blokk kalles DC-verdi, og hver DC-verdi blir delta-kodet i forhold til de tidligere. Dermed vil endringen av lysstyrken i den første blokken påvirke alle blokkene.

Det gjenstår et siste mysterium: hvordan endringen av et enkelt tall kan ødelegge hele bildet? Det har foreløpig ikke vært slike egenskaper ved komprimeringsnivåene. Svaret ligger i JPEG-headeren. De første 500 byte inneholder metadata om bildet – bredde, høyde, osv., og før vi har jobbet med dem.

Uten headeren er det nesten umulig (eller veldig vanskelig) å dekode JPEG. Dette ville se ut som om jeg prøvde å beskrive et maleri for deg, og jeg begynner å finne opp ord for å formidle inntrykket mitt. Beskrivelsen vil sannsynligvis bli ganske komprimert, siden jeg kan finne på ord med akkurat den betydningen jeg ønsker å formidle, men for alle andre vil de ikke gi mening.

Det høres dumt ut, men slik skjer det. Hvert JPEG-bilde komprimeres med koder som er spesifikke for det. Ordboken med koder lagres i overskriften. Denne teknikken kalles 'Huffman-koding', og ordboken er en Huffman-tabell. I overskriften er tabellen merket med to byte – 255 og deretter 196. Hver fargekomponent kan ha sin egen tabell.

Endringer i tabellene vil radikalt påvirke ethvert bilde. Et godt eksempel er å endre 1 til 12 på linje 15.

Dette skjer fordi tabellene angir hvordan man skal lese de enkelte bitene. Så langt har vi bare arbeidet med binære tall i desimalform. Men dette skjuler for oss det faktum at hvis du vil lagre tallet 1 i en byte, vil det se ut som 00000001, fordi hver byte må inneholde nøyaktig åtte biter, selv om man bare trenger én av dem.

Potensielt er dette en stor plasssløsing hvis du har mange små tall. Huffman-koding er en teknikk som lar oss svekke dette kravet om at hvert tall må ta opp åtte biter. Dette betyr at hvis du ser to byte:

234 115

Så, avhengig av Huffman-tabellen, kan dette være tre tall. For å hente dem ut må du først dele dem opp i separate biter:

11101010 01110011

Deretter konsulterer vi tabellen for å forstå hvordan de skal grupperes. For eksempel kan dette være de første seks bitene (111010), som er 58 i desimal, etterfulgt av fem biter (10011), som er 19, og til slutt de siste fire bitene (0011), som er 3.

Derfor er det veldig vanskelig å forstå byte på dette kompresjonstrinnet. Bytes representerer ikke det som det ser ut til. Jeg vil ikke gå inn på detaljene om hvordan man arbeider med tabellen i denne artikkelen, men materialer om dette emnet på nettet er ganske.

Et av de interessante triksene du kan gjøre, når du vet dette, er å skille overskriften fra JPEG og lagre den separat. I praksis vil det si at filen bare kan leses av deg. Facebook gjør dette for å redusere filene enda mer.

Hva annet kan gjøres – litt endre Huffman-tabellen. For andre vil dette se ut som et ødelagt bilde. Og bare du vil vite den magiske versjonen for å fikse det.

La oss oppsummere: hva trenger vi for å dekode JPEG? Vi trenger:

1. Å hente ut Huffman-tabellen(e) fra overskriften og dekode bitene.
2. Hent koeffisientene for den diskrete cosinus-transformasjonen for hver farge- og lysstyrkekomponent for hver 8x8 blokk, ved å utføre omvendte lengde-kodings- og delta-transformasjoner.
3. Kombiner cosinusene basert på koeffisientene for å få pikselverdier for hver 8x8 blokk.
4. Skalere fargekomponentene hvis subprøve ble utført (denne informasjonen finnes i headeren).
5. Konverter de oppnådde YCbCr-verdiene til RGB for hver piksel.
6. Vis bildet på skjermen!

En seriøs oppgave for å bare se på et bilde av en katt! Men det jeg liker med dette – er at det viser hvor menneskesentrert JPEG-teknologien er. Den er basert på nyansene i vår oppfatning, som gjør det mulig å oppnå mye bedre komprimering enn vanlige teknologier. Og nå, ved å forstå hvordan JPEG fungerer, kan man forestille seg hvordan disse teknologiene kan overføres til andre områder. For eksempel kan delta-koding i video gi betydelig filreduksjon, ettersom det ofte finnes store områder som ikke endres fra ramme til ramme (som bakgrunnen).

Koden som ble brukt i artikkelen, er åpen og inneholder instruksjoner for å erstatte bildene med egne.

Kilde: habr.com