JPEG-bilder er allestedsnærværende i våre digitale liv, men bak denne fineren av bevissthet er algoritmer som fjerner detaljer som ikke er synlige for det menneskelige øyet. Resultatet er den høyeste visuelle kvaliteten i den minste filstørrelsen - men hvordan fungerer det egentlig? La oss se hva øynene våre ikke ser!
Det er lett å ta for gitt muligheten til å sende et bilde til en venn og ikke bekymre deg for hvilken enhet, nettleser eller operativsystem de bruker – men det var ikke alltid tilfelle. 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å. Du kunne ikke bare sende et bilde fra en datamaskin til en annen og håpe at det ville fungere.
For å løse dette problemet ble en komité av eksperter fra hele verden samlet i 1986 kalt "» (Joint Photographic Experts Group, JPEG), grunnlagt som en felles innsats mellom International Organization for Standardization (ISO) og International Electrotechnical Commission (IEC), to internasjonale standardiseringsorganisasjoner med hovedkontor i Genève, Sveits.
En gruppe mennesker kalt JPEG opprettet JPEG-standarden for digital bildekomprimering i 1992. Alle som har brukt Internett har sannsynligvis støtt på JPEG-kodede bilder. Dette er den vanligste måten å kode, sende og lagre bilder på. Fra nettsider til e-post til sosiale medier, JPEG brukes milliarder av ganger om dagen – praktisk talt hver gang vi ser på et bilde på nettet eller sender det. Uten JPEG ville nettet vært mindre fargerikt, tregere og sannsynligvis ha færre kattebilder!
Denne artikkelen handler om hvordan du dekoder et JPEG-bilde. Med andre ord, hva som kreves for å konvertere komprimerte data lagret på en datamaskin til et bilde som vises på skjermen. Dette er verdt å vite, ikke bare fordi det er viktig å forstå teknologien vi bruker hver dag, men også fordi vi ved å låse opp kompresjonsnivåer lærer mer om persepsjon og syn, og hvilke detaljer øynene våre er mest følsomme for.
I tillegg er det veldig interessant å leke med bilder på denne måten.
Ser inn i JPEG
På en datamaskin lagres alt som en sekvens av binære tall. Vanligvis er disse bitene, nuller og enere, gruppert i grupper på åtte for å utgjøre byte. Når du åpner et JPEG-bilde på en datamaskin, må noe (en nettleser, et operativsystem, noe annet) dekode bytene, og gjenopprette det originale bildet som en liste over farger som kan vises.
Hvis du laster ned denne søte og åpne den i et tekstredigeringsprogram, vil du se en haug med usammenhengende tegn.
Her bruker jeg Notepad++ for å undersøke innholdet i filen, siden vanlige tekstredigerere som Notepad på Windows vil ødelegge den binære filen etter lagring, og den vil ikke lenger tilfredsstille JPEG-formatet.
Å åpne et bilde i en tekstbehandler forvirrer datamaskinen, akkurat som du forvirrer hjernen din når du gnir deg i øynene og begynner å se fargeflekker!
Disse stedene du ser er kjent som , og er ikke et resultat av en lysstimulus eller en hallusinasjon generert av sinnet. De oppstår fordi hjernen din tror at eventuelle elektriske signaler i synsnervene formidler informasjon om lys. Hjernen trenger å gjøre disse antakelsene fordi det ikke er noen måte å vite om et signal er en lyd, et syn eller noe annet. Alle nerver i kroppen overfører nøyaktig de samme elektriske impulsene. Ved å legge press på øynene sender du signaler som ikke er visuelle, men aktiverer øyets reseptorer, som hjernen din tolker – i dette tilfellet feil – som noe visuelt. Du kan bokstavelig talt se presset!
Det er morsomt å tenke på hvor lik datamaskiner er hjernen, men det er også en nyttig analogi for å illustrere hvor mye betydningen av data – enten de bæres gjennom kroppen av nerver eller lagres på en datamaskin – avhenger av hvordan de tolkes. Alle binære data er bygd opp av 0-er og 1-ere, de grunnleggende komponentene som kan formidle informasjon av alle slag. Datamaskinen din finner ofte ut hvordan de skal tolke dem ved å bruke ledetråder som filtyper. Nå tvinger vi den til å tolke dem som tekst, for det er det tekstredaktøren forventer.
For å forstå hvordan vi dekoder JPEG, må vi se de originale signalene selv - de binære dataene. Dette kan gjøres ved hjelp av en heksadesimal editor, eller direkte på ! Det er et bilde, ved siden av det i tekstfeltet er alle dets byte (bortsett fra overskriften), presentert i desimalform. Du kan endre dem, og skriptet omkodes og produserer et nytt bilde i farten.
Du kan lære mye bare ved å spille med denne editoren. Kan du for eksempel fortelle hvilken rekkefølge pikslene er lagret i?
Det merkelige med dette eksemplet er at det å endre noen tall ikke påvirker bildet i det hele tatt, men hvis du for eksempel bytter ut tallet 17 med 0 på første linje, vil bildet bli fullstendig ødelagt!
Andre endringer, som å erstatte 7 på linje 1988 med tallet 254, endrer fargen, men bare på påfølgende piksler.
Det merkeligste er kanskje 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 bytene.
Når du spiller med editoren, er det vanskelig å forstå hvordan et bilde gjenskapes fra disse bytene, siden JPEG-komprimering består av tre forskjellige teknologier, brukt sekvensielt i nivåer. Vi vil studere hver enkelt for å avdekke den mystiske oppførselen vi ser.
Tre nivåer av JPEG-komprimering:
- .
- .
- , и
For å gi deg en ide om størrelsen på komprimeringen, merk at bildet ovenfor representerer 79 819 tall, eller omtrent 79 KB. Hvis vi lagret den uten komprimering, ville hver piksel kreve tre tall – for de røde, grønne og blå komponentene. Dette vil utgjøre 917 700 numre, eller ca. 917 KB. Som et resultat av JPEG-komprimering ble den endelige filen redusert med mer enn 10 ganger!
Faktisk kan dette bildet komprimeres mye mer. Nedenfor er to bilder side om side - bildet til høyre er komprimert til 16 KB, det vil si 57 ganger mindre enn den ukomprimerte versjonen!
Hvis du ser nøye etter, vil du se at disse bildene ikke er identiske. Begge er bilder med JPEG-komprimering, men det høyre er mye mindre i volum. Det ser også litt dårligere ut (se på bakgrunnsfarge-firkantene). Det er derfor JPEG også kalles tapskomprimering; Under komprimeringsprosessen endres bildet og mister noen detaljer.
1. Fargedelprøvetaking
Her er et bilde med kun det første komprimeringsnivået.
(Interaktiv versjon - in artikler). Å fjerne ett tall ødelegger alle farger. Men hvis nøyaktig seks tall fjernes, har det praktisk talt ingen effekt på bildet.
Nå er tallene litt lettere å tyde. Dette er nesten en enkel liste over farger, der hver byte endrer nøyaktig én piksel, men samtidig er den allerede halvparten av størrelsen på det ukomprimerte bildet (som vil ta opp omtrent 300 KB i denne reduserte størrelsen). Kan du gjette hvorfor?
Du kan se at disse tallene ikke representerer de standard røde, grønne og blå komponentene, siden hvis vi erstatter alle tallene med nuller, vil vi få et grønt bilde (i stedet for hvitt).
Dette er fordi disse bytene står for Y (lysstyrke),
Cb (relativ blåhet),
og Cr (relativ rødhet) bilder.
Hvorfor ikke bruke RGB? Det er tross alt slik de fleste moderne skjermer fungerer. Skjermen kan vise hvilken som helst farge, inkludert rød, grønn og blå, med forskjellige intensiteter for hver piksel. Hvitt oppnås ved å slå på alle tre med full lysstyrke, og svart ved å slå dem av.
Dette er også veldig likt hvordan det menneskelige øyet fungerer. Fargereseptorene i øynene våre kalles "“, og er delt inn i tre typer, som hver er mer følsomme for enten røde, grønne eller blå farger [S-type kjegler er følsomme i den fiolett-blå (S fra det engelske kortbølgespekteret), M -type - i de grønn-gule (M fra engelsk Medium - medium-wave), og L-type - i de gul-røde (L fra den engelske Long - long-wave) delene av spekteret. Tilstedeværelsen av disse tre typene kjegler (og stenger, som er følsomme i den smaragdgrønne delen av spekteret) gir en person fargesyn. / ca. overs.]. , en annen type fotoreseptor i øynene våre, er i stand til å oppdage endringer i lysstyrke, men er mye mer følsomme for farger. Øynene våre har omtrent 120 millioner stenger og bare 6 millioner kjegler.
Dette er grunnen til at øynene våre er mye bedre til å oppdage endringer i lysstyrke enn endringer i farge. Hvis du skiller farge fra lysstyrke, kan du fjerne litt farge og ingen vil merke noe. Chroma subsampling er prosessen med å representere fargekomponentene i et bilde med en lavere oppløsning enn luminanskomponentene. I eksemplet ovenfor har hver piksel nøyaktig én Y-komponent, og hver enkelt gruppe på fire piksler har nøyaktig én Cb- og én Cr-komponent. Derfor inneholder bildet fire ganger mindre fargeinformasjon enn originalen.
YCbCr-fargerommet brukes ikke bare i JPEG. Den ble opprinnelig oppfunnet i 1938 for TV-programmer. Ikke alle har en farge-TV, så å skille farge og lysstyrke tillot alle å få det samme signalet, og TV-er uten farge brukte ganske enkelt bare lysstyrkekomponenten.
Så å fjerne ett tall fra editoren ødelegger alle fargene fullstendig. Komponentene lagres i formen YYYY Cb Cr (faktisk ikke nødvendigvis i den rekkefølgen - lagringsrekkefølgen er spesifisert i filoverskriften). Fjerning av det første tallet vil føre til at den første verdien av Cb blir oppfattet som Y, Cr som Cb, og generelt vil du ha en dominoeffekt som bytter alle fargene i bildet.
JPEG-spesifikasjonen tvinger deg ikke til å bruke YCbCr. Men de fleste filer bruker det fordi det produserer bedre nedsamplede bilder enn RGB. Men du trenger ikke ta mitt ord for det. Se selv i tabellen nedenfor hvordan subsampling av hver enkelt komponent vil se ut i både RGB og YCbCr.
(Interaktiv versjon - in artikler).
Fjerningen av blått er ikke like merkbart som rødt eller grønt. Det er på grunn av de seks millioner kjeglene i øynene dine, ca 64% er følsomme for rødt, 32% for grønt og 2% for blått.
Nedsamplingen av Y-komponenten (nederst til venstre) sees best. Selv en liten endring er merkbar.
Konvertering av et bilde fra RGB til YCbCr reduserer ikke filstørrelsen, men det gjør det lettere å finne mindre synlige detaljer som kan fjernes. Tapskompresjon oppstår i andre trinn. Den er basert på ideen om å presentere data i en mer komprimerbar form.
2. Diskret cosinustransformasjon og sampling
Dette komprimeringsnivået er for det meste hva JPEG handler om. Etter å ha konvertert fargene til YCbCr, komprimeres komponentene individuelt, så vi kan konsentrere oss om kun Y-komponenten. Og her er hvordan Y-komponentbytene ser ut etter påføring av dette laget.
(Interaktiv versjon - in artikler). I den interaktive versjonen ruller redigeringen til linjen som representerer den ved å klikke på en piksel. Prøv å fjerne tall fra slutten eller legg til noen få nuller til et bestemt tall.
Ved første øyekast ser det ut som veldig dårlig kompresjon. Det er 100 000 piksler i et bilde, og det tar 102 400 tall for å representere lysstyrken deres (Y-komponenter) – det er verre enn å komprimere ingenting i det hele tatt!
Vær imidlertid oppmerksom på at de fleste av disse tallene er null. Dessuten kan alle disse nullene på slutten av linjene fjernes uten å endre bildet. Det er omtrent 26 000 tall igjen, og dette er nesten 4 ganger mindre!
Dette nivået inneholder hemmeligheten bak sjakkmønstre. I motsetning til andre effekter vi har sett, er ikke utseendet til disse mønstrene en feil. De er byggesteinene i hele bildet. Hver linje i editoren inneholder nøyaktig 64 tall, diskrete cosinustransformasjon (DCT) koeffisienter som tilsvarer intensiteten til 64 unike mønstre.
Disse mønstrene er dannet basert på cosinusplottet. Slik ser noen av dem ut:
8 av 64 odds
Nedenfor er et bilde som viser alle 64 mønstrene.
(Interaktiv versjon - in artikler).
Disse mønstrene er spesielt viktige fordi de danner grunnlaget for 8x8-bildene. Hvis du ikke er kjent med lineær algebra, betyr dette at et hvilket som helst 8x8-bilde kan lages fra disse 64 mønstrene. DCT er prosessen med å dele opp bilder i 8x8 blokker og konvertere hver blokk til en kombinasjon av disse 64 koeffisientene.
Det virker som magi at ethvert bilde kan være sammensatt av 64 spesifikke mønstre. Dette er imidlertid det samme som å si at ethvert sted på jorden kan beskrives med to tall - breddegrad og lengdegrad [som indikerer halvkuler / ca. overs.]. Vi tenker ofte på jordoverflaten som todimensjonal, så vi trenger bare to tall. Et 8x8 bilde har 64 dimensjoner, så vi trenger 64 tall.
Det er ennå ikke klart hvordan dette hjelper oss når det gjelder komprimering. Hvis vi trenger 64 tall for å representere et 8x8 bilde, hvorfor ville dette være bedre enn å bare lagre 64 lysstyrkekomponenter? Vi gjør dette av samme grunn som vi gjorde tre RGB-numre til tre YCbCr-numre: det lar oss fjerne subtile detaljer.
Det er vanskelig å se nøyaktig hvilke detaljer som fjernes på dette stadiet fordi JPEG bruker DCT på 8x8 blokker. Imidlertid er det ingen som forbyr oss å bruke det på hele bildet. Slik ser DCT ut for Y-komponenten brukt på hele bildet:
Mer enn 60 000 numre kan fjernes fra slutten med praktisk talt ingen merkbare endringer på bildet.
Vær imidlertid oppmerksom på at hvis vi nullstiller de første fem tallene, vil forskjellen være åpenbar.
Tallene i begynnelsen representerer lavfrekvente endringer i bildet, som øynene våre fanger best opp. Tall mot slutten indikerer endringer i de høye frekvensene som er vanskeligere å legge merke til. For å "se det øyet ikke kan se," kan vi isolere disse høyfrekvente detaljene ved å nullstille de første 5000 tallene.
Vi ser alle områdene i bildet der den største endringen skjer fra piksel til piksel. Kattens øyne, værhårene, frottéteppet og skyggene i nedre venstre hjørne skiller seg ut. Du kan gå videre ved å nullstille de første 10 000 tallene:
20 000 XNUMX:
40 000 XNUMX:
60 000 XNUMX:
Disse høyfrekvente detaljene fjernes av JPEG under komprimeringsfasen. Det er ingen tap i å konvertere farger til DCT-koeffisienter. Tap oppstår ved prøvetakingstrinnet, der høyfrekvente eller nær nullverdier fjernes. Når du senker JPEG-lagringskvaliteten, øker programmet terskelen for antall verdier som er fjernet, noe som reduserer filstørrelsen, men gjør bildet mer pikselert. Derfor så bildet i den første delen, som var 57 ganger mindre, slik ut. Hver 8x8 blokk var representert av langt færre DCT-koeffisienter sammenlignet med versjonen med høyere kvalitet.
Du kan lage en så kul effekt som gradvis strømming av bilder. Du kan vise et uskarpt bilde som blir mer og mer detaljert ettersom flere og flere koeffisienter lastes ned.
Her, bare for moro skyld, er det du får ved å bruke bare 24 000 numre:
Eller bare 5000:
Veldig uskarpt, men på en eller annen måte gjenkjennelig!
3. Kjørelengdekoding, delta og Huffman
Så langt har alle stadier av kompresjon vært tapsmessige. Den siste fasen, tvert imot, fortsetter uten tap. Den sletter ikke informasjon, men den reduserer filstørrelsen betydelig.
Hvordan kan du komprimere noe uten å kaste informasjon? Tenk deg hvordan vi vil beskrive et enkelt svart rektangel på 700 x 437.
JPEG bruker 5000 tall for dette, men mye bedre resultater kan oppnås. Kan du forestille deg et kodingsskjema som vil beskrive et slikt bilde i så få byte som mulig?
Det minimale oppsettet jeg kunne komme opp med bruker fire: tre for å representere en farge, og en fjerde for å indikere hvor mange piksler den fargen har. Ideen om å representere repeterende verdier på denne kondenserte måten kalles løpelengdekoding. Det er tapsfritt fordi vi kan gjenopprette de kodede dataene til sin opprinnelige form.
En JPEG-fil med et svart rektangel er mye større enn 4 byte - husk at på DCT-nivå brukes komprimering på 8x8 pikselblokker. Derfor trenger vi som et minimum én DCT-koeffisient for hver 64 piksler. Vi trenger en fordi i stedet for å lagre én DCT-koeffisient etterfulgt av 63 nuller, lar kjørelengdekoding oss lagre ett tall og indikere at "alle andre er nuller."
Delta-koding er en teknikk der hver byte inneholder en forskjell fra en verdi, i stedet for en absolutt verdi. Derfor endrer redigering av visse byte fargen på alle andre piksler. For eksempel i stedet for å lagre
12 13 14 14 14 13 13 14
Vi kan starte med 12 og så ganske enkelt angi hvor mye vi må legge til eller trekke fra for å få det neste tallet. Og denne sekvensen i deltakoding har formen:
12 1 1 0 0 -1 0 1
De konverterte dataene er ikke mindre enn de opprinnelige dataene, men det er lettere å komprimere dem. Å bruke delta-koding før kjøringslengdekoding kan hjelpe mye mens det fortsatt er tapsfri komprimering.
Deltakoding er en av de få teknikkene som brukes utenfor 8x8 blokker. Av de 64 DCT-koeffisientene er én rett og slett en konstant bølgefunksjon (helfarget). Den representerer gjennomsnittlig lysstyrke for hver blokk for luma-komponentene, eller gjennomsnittlig blåhet for Cb-komponentene, og så videre. Den første verdien av hver DCT-blokk kalles DC-verdien, og hver DC-verdi er deltakodet i forhold til de foregående. Derfor vil endring av lysstyrken til den første blokken påvirke alle blokkene.
Det endelige mysteriet gjenstår: hvordan ødelegger det å endre entall fullstendig hele bildet? Så langt har ikke kompresjonsnivåer hatt slike egenskaper. Svaret ligger i JPEG-overskriften. De første 500 bytene inneholder metadata om bildet – bredde, høyde osv., og vi har ikke jobbet med dem ennå.
Uten en header er det nesten umulig (eller svært vanskelig) å dekode JPEG. Det vil se ut som om jeg prøver å beskrive bildet for deg, og jeg begynner å finne på ord for å formidle inntrykket mitt. Beskrivelsen blir nok ganske fortettet, 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 det er akkurat det som skjer. Hvert JPEG-bilde er komprimert med koder som er spesifikke for det. Kodeordboken er lagret i overskriften. Denne teknikken kalles Huffman-kode og vokabularet kalles Huffman-tabell. I overskriften er tabellen merket med to byte - 255 og deretter 196. Hver fargekomponent kan ha sin egen tabell.
Endringer i tabeller vil radikalt påvirke ethvert bilde. Et godt eksempel er å endre den 15. linjen til 1.
Dette skjer fordi tabellene spesifiserer hvordan individuelle biter skal leses. Så langt har vi kun jobbet 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, siden hver byte må ha nøyaktig åtte biter, selv om det bare trengs én av dem.
Dette er potensielt en stor sløsing med plass hvis du har mange små tall. Huffman-kode er en teknikk som lar oss lempe på dette kravet om at hvert tall må oppta åtte biter. Dette betyr at hvis du ser to byte:
234
Deretter, avhengig av Huffman-tabellen, kan disse være tre tall. For å trekke dem ut, må du først dele dem ned i individuelle biter:
11101010
Deretter ser vi på tabellen for å finne ut hvordan vi skal gruppere dem. For eksempel kan dette være de første seks bitene, (111010), eller 58 i desimal, etterfulgt av fem biter (10011), eller 19, og til slutt de fire siste bitene (0011), eller 3.
Derfor er det veldig vanskelig å forstå bytene på dette stadiet av komprimering. Bytes representerer ikke hva de ser ut til. Jeg vil ikke gå inn på detaljer om arbeidet med tabellen i denne artikkelen, men om denne saken på nett .
Et interessant triks du kan gjøre med denne kunnskapen er å skille overskriften fra JPEG og lagre den separat. Faktisk viser det seg at bare du kan lese filen. Facebook gjør dette for å gjøre filene enda mindre.
Hva annet kan gjøres er å endre Huffman-bordet ganske mye. For andre vil det se ut som et ødelagt bilde. Og bare du vil vite den magiske måten å fikse det på.
La oss oppsummere: så hva trengs for å dekode JPEG? Nødvendig:
- Trekk ut Huffman-tabellen(e) fra overskriften og dekod bitene.
- Trekk ut de diskrete cosinustransformasjonskoeffisientene for hver farge- og luminanskomponent for hver 8x8 blokk, og utfør transformasjoner for invers kjørelengde og deltakoding.
- Kombiner cosinus basert på koeffisienter for å få pikselverdier for hver 8x8 blokk.
- Skaler fargekomponenter hvis delsampling ble utført (denne informasjonen er i overskriften).
- Konverter de resulterende YCbCr-verdiene for hver piksel til RGB.
- Vis bildet på skjermen!
Seriøst arbeid for bare å se et bilde med en katt! Men det jeg liker med den er at den viser hvor menneskesentrisk JPEG-teknologi er. Den er basert på særegenhetene ved oppfatningen vår, og lar oss oppnå mye bedre komprimering enn konvensjonelle teknologier. Og nå som vi forstår hvordan JPEG fungerer, kan vi forestille oss hvordan disse teknologiene kan overføres til andre områder. Delta-koding i video kan for eksempel gi en betydelig reduksjon i filstørrelse, siden det ofte er hele områder som ikke endres fra ramme til ramme (for eksempel bakgrunnen).
, er åpen, og inneholder instruksjoner om hvordan du erstatter bildene med dine egne.
Kilde: www.habr.com