Beeldcompressie: JPEG en JPEG2000. JPEG uitvinden

Digitale JPEG-beeldcompressie

Een van de meest uitgebreide en populaire standaarden voor beeldcompressie is de JPEG-standaard.

Het compressieproces zelf bestaat uit drie opeenvolgende stappen:

a) Berekening van de discrete cosinustransformatie (DCT) voor matrices van 8*8 blokken verkregen na standaardpartitionering van de CI-matrix;

b) kwantisering van DCT-coëfficiënten;

c) coderen met een ongelijke code.

Eerst worden de digitale gegevens verdeeld in afzonderlijke blokken van 8*8 elementen, die opeenvolgend van links naar rechts en van boven naar beneden worden verwerkt. De verwerking van elk blok begint met een verschuiving in de helderheid van de waarden van alle 64 elementen, wat wordt bereikt door de waarde af te trekken, waar het maximale aantal helderheidsniveaus is. Vervolgens wordt de tweedimensionale DCT van de blokelementen berekend. De verkregen coëfficiëntwaarden worden gekwantiseerd volgens de formule:

waar is het resultaat van de kwantisering van de waarde van de DCT-coëfficiënt, en is het overeenkomstige element van de matrix van kwantiseringscoëfficiënten:

(Opgemerkt moet worden dat voordat de gekwantiseerde DCT-coëfficiënten kunnen worden onderworpen aan inverse DCT om een beeldblok te reconstrueren, ze moeten worden vermenigvuldigd met:

. (2.5)

Uiteraard zal de inverse transformatie van de verkregen waarden resulteren in een benadering van het gereconstrueerde beeldblok.)

De gekwantiseerde waarden van de coëfficiënten worden opnieuw geordend door een zigzagtransformatie volgens:

waarbij de volgorde wordt weergegeven waarin de coëfficiënten worden geselecteerd. Het resultaat is een eendimensionale reeks gekwantiseerde coëfficiënten.

De eendimensionale array die wordt verkregen na de zigzagtransformatie wordt geordend door de ruimtelijke frequentie te verhogen, wat in de regel lange reeksen nullen produceert, die effectief worden gebruikt door de JPEG-coderingsprocedure. De aanbevolen JPEG-kwantiseringsmatrix is als volgt:

Voorbeeld. Sequentiële JPEG-codering en decodering. Overweeg het comprimeren en decomprimeren van het volgende blok van 8*8 elementen volgens de sequentiële JPEG-coderingsstandaard:

De bronpixels kunnen 256 of 2 8 helderheidsniveaus hebben, dus het coderingsproces begint met het verschuiven van het bereik van waarden - door 2 7 of 128 af te trekken van de pixelwaarden. Het resultaat is een array:

wat er na directe DCT als volgt uit zal zien:

Als de bovenstaande kwantiseringsmatrix wordt gebruikt om de ontvangen gegevens te kwantiseren, zullen de coëfficiënten na kwantisering de vorm aannemen:

De kwantiseringsprocedure produceert een aanzienlijk aantal nulelementen. Nadat de coëfficiënten opnieuw zijn gerangschikt volgens de zigzagtransformatie, wordt de volgende array verkregen:

(-26 -31 -3 -2 -6 2 -4 1 -4 1 1 5 0 2 0 0 -1 2 0 0 0 0 0 -1 -1 KB)

Het codewoord KB betekent het einde van het blok, wat aangeeft dat alle resterende coëfficiënten in de opnieuw geordende reeks gelijk zijn aan 0. Om de resulterende array te coderen, worden standaard Huffman-codes gebruikt, die de array omzetten in een continue stroom bits.

Bij het reconstrueren van een gecomprimeerd JPEG-blok moet de decoder eerst de gekwantiseerde DCT-coëfficiënten opnieuw creëren uit een continue bitstroom. Omdat de binaire Huffman-codereeks uniek decodeerbaar is, kan deze stap eenvoudig worden geïmplementeerd met behulp van een tabeltransformatie. Na vermenigvuldiging met kwantiseringscoëfficiënten verkrijgen we, volgens (2.5), de array:

Een volledig hersteld blok wordt verkregen na het uitvoeren van de inverse DCT van de resulterende array:

en omgekeerde verschuiving van het waardenbereik met +2 7 =+128. Als resultaat krijgen we:

Alle verschillen in de waarden van de elementen van de originele en herstelde blokken komen voort uit de aard van compressie met verlies, wat de essentie is van de JPEG-compressie- en herstelprocedures. In dit voorbeeld variëren de herstelfouten van -14 tot 11 en zijn ze als volgt verdeeld:

Karakteristieke kenmerken van enkelvoudige aantallen digitale beeldmatrixblokken met JPEG-compressie . Laat de originele DI in grijswaarden, opgeslagen in een verliesvrij formaat, bijvoorbeeld in het TIF-formaat, waarvan de matrix afmetingen heeft, op een standaard manier in blokken worden verdeeld. Als we voor elk DI-blok de verzameling van alle VLF's (enkelvoudig spectrum) bepalen, dan blijkt dat gemiddeld slechts 2,40% van het totale aantal blokken (ONB) nul VLF's heeft.

Dit feit is niet toevallig. De rangorde van elke matrix wordt bepaald door het aantal niet-nul SLF's, wat betekent dat de aanwezigheid van nullen in het enkelvoudige spectrum aangeeft dat het aantal lineair onafhankelijke rijen (kolommen) kleiner is dan de grootte ervan. Voor een willekeurige reële DI is de kans echter klein dat de rijen (kolommen) van het volgende blok lineair afhankelijk blijken te zijn, zelfs als er rekening wordt gehouden met de correlatie van pixelhelderheidswaarden.

Kwantisering van DCT-coëfficiënten, die plaatsvindt tijdens het opslaan van DI in JPEG-formaat (met verliezen), is een onomkeerbare procedure en leidt tot enkele kenmerken van de verstoringen van VLF-blokken.

Laat de originele digitale gegevens onderwerpen aan JPEG-compressie. Laten we er een gedeeltelijke hersteloperatie (PR) voor uitvoeren, die het volgende omvat: 1) entropiedecodering; 2) het vermenigvuldigen van de verkregen coëfficiënten met de overeenkomstige elementen van de normalisatiearray (kwantisatiematrix); 3) toepassing van inverse DCT, maar zonder daaropvolgende afronding.

Bijna alle blokken van de resulterende matrix bevatten nul VLF's, en er zullen nogal wat van dergelijke waarden in de blokken voorkomen (tabel 2.1). Deze situatie is natuurlijk. Na het kwantiseren en afronden van de coëfficiënten van de DCT-blokken, zullen veel ervan, die overeenkomen met hoge en middenfrequenties, op nul worden teruggezet en nul blijven na de frequentiegolf, die, rekening houdend met de overeenkomst tussen de coëfficiënten van de discrete Fourier-transformatie en de enkelvoudige tripletten van de beeldmatrix, waar respectievelijk de VLF en de corresponderende linker en rechter SNV zijn, zullen leiden tot het op nul zetten van de kleinste (en mogelijk middelgrote) VLF-blokmatrices.

Tabel 2.1. Resultaten van decompositie van unieke waarden van blokken gedeeltelijk gereconstrueerde afbeeldingen

	BWB		Aantal blokken met meer dan 2 nul-VLF's, relatief ten opzichte van de BNR (in%)
m=8	m=7	m=6	m=5	m=4	m=3	m=2	m=1	m=0
STEENBOLK
CAMERAMAN
BAND
MAAN									99.8
CEL

Merk op dat hoe minder nul-VLF's in het betreffende blok voorkomen, hoe meer contourlijnen het bevat. De aanwezigheid van contouren in een blok duidt inderdaad op een significante hoogfrequente component in het signaal dat met dit blok correspondeert. Dan zullen de DCT-coëfficiënten die overeenkomen met hoge en middenfrequenties relatief groot zijn en na kwantisering en FM niet-nul blijven, en daarom niet alleen bijdragen aan de maximale VLF.

Om de geldigheid van het bovenstaande te visualiseren, bekijkt u het CELL.TIF-beeld (Fig. 2.5(a)). Figuur 2.5(b) toont een matrix van nul VLF-blokken (MNSNB) van de dimensie van het HF-beeld, waarvan elk element gelijk is aan het aantal nul VLF-blokken in het overeenkomstige blok. De figuur benadrukt de elementen met de kleinste waarden, waardoor u duidelijk de overeenkomst kunt zien tussen de contouren van de originele DI en de blokken die het kleinste aantal nul-VLF's bevatten.

Laat de originele JPEG-gecomprimeerde afbeelding volledig herstellen. Dit betekent dat na de frequentierespons alle pixelhelderheidswaarden worden afgerond op hele getallen en in het bereik worden ingevoerd. Deze actie zal de beeldmatrix verstoren die wordt verkregen na de frequentiegolf, en het aantal nul-VLF's in de blokken zal op een bepaalde manier veranderen (Tabel 2.2). Als er na de CV geen elementen zijn die significant kleiner zijn dan 0 of groter dan 255, zal de verstoring van de matrix klein zijn. Volgens de verhouding

, (2.6)

Wat plaatsvindt voor een willekeurige matrix, waarbij de VLF van respectievelijk de originele en verstoorde matrices is, de verstoringsmatrix van het blok is, de spectrale matrixnorm is, zijn de VLF ongevoelig voor storende invloeden. Als sommige van de nul-VLF-blokken van de FM-beeldmatrix na volledige restauratie (RF) niet-nul worden, zullen hun waarden vergelijkbaar zijn met de afrondingsfout, wat niet typisch is voor blokken van de originele DI.

Afb.2.5. Origineel beeld CELL.TIF (a); MNSchB na ChV (b); MNSCHhB na volledig herstel (c)

Het meest opvallende verschil tussen de geaggregeerde originele afbeelding en de volledig herstelde afbeelding na JPEG-compressie is het vergelijken van hun MNSCHB. Een typisch beeld wordt getoond in figuur 2.5(c), waarbij de MNSCHhB voor CELL.TIF slechts nulwaarden heeft.

Tabel 2.2. Resultaten van decompositie van unieke waarden van blokken van volledig gereconstrueerde afbeeldingen

Lossless beeld (TIF)	BWB	Aantal blokken met nul VLF	Aantal blokken met meer dan twee nul SB's, relatief ten opzichte van SB (%)
m=8	m=7	m=6	m=5	m=4	m=3	m=2	m=1	m=0
STEENBOLK
CAMERAMAN
BAND
MAAN
CEL

Vragen

Wat betekent datacompressie? Wat is gegevensredundantie?
Belangrijkste soorten gegevensredundantie.
Hoe wordt compressie geïmplementeerd via kwantisering?
Wat is een low-rank image-benadering? Hoe wordt compressie geïmplementeerd met behulp van low-rank beeldbenaderingen?
Wat is de ontbinding van de singuliere waarde van een matrix?
Wat is spectrale ontleding van een matrix?
Correspondentie tussen digitale beeldparameters in ruimtelijke en frequentiedomeinen.
Basisstappen JPEG is digitale beeldcompressie. Kwantiseringsmatrices.
Karakteristieke kenmerken van enkelvoudige aantallen digitale beeldmatrixblokken in JPEG-compressie.
Gedeeltelijke en volledige restauratie van een digitaal beeld na compressie.

Literatuur

Kobozeva A.A. Analyse van informatiebeveiliging / A.A.Kobozeva, V.A.Khoroshko. – K.: Ed. GUIKT, 2009. – 251 p.
Demmel J. Computationele lineaire algebra / J. Demmel; vertaald uit het Engels Kh.D.Ikramova. - M.: Mir, 2001. - 430 p.
Bakhvalov N.S. Numerieke methoden / N.S.Bakhvalov, N.P.Zhidkov, G.M.Kobelkov. - M.: BINOM. Kennislaboratorium, 2006. - 636 p.
Gonzalez R. Digitale beeldverwerking / R. Gonzalez, R. Woods; laan uit het Engels bewerkt door PACiochia. - M.: Technosphere, 2005. - 1072 p.
Kahaner D. Numerieke methoden en software / D. Kahaner, K. Mouler, S. Nash; laan uit het Engels Kh.D.Ikramova. - M.: Mir, 2001. - 575 p.
Gantmakher F.R. Theorie van matrices / F.R. - M.: Nauka, 1988. - 552 p.
Voevodin V.V. Computationele grondslagen van lineaire algebra / V.V. - M.: Wetenschap. Hoofdredacteur van fysieke en wiskundige lit., 1977. - 304 p.

(uitgesproken als "japeg" Joint Photographic Experts Group, naar de naam van de ontwikkelingsorganisatie) is een van de populaire grafische formaten die worden gebruikt voor het opslaan van foto's en soortgelijke afbeeldingen. Bestanden die JPEG-gegevens bevatten, hebben doorgaans de extensies .jpeg, .jfif, .jpg, .JPG of .JPE. Hiervan is .jpg echter de meest populaire extensie op alle platforms.

1. Gezamenlijke groep van deskundigen op het gebied van fotografie;

2. Een door deze groep ontwikkelde beeldcompressiemethode en het bijbehorende grafische formaat, vaak gebruikt op het WWW. Het wordt gekenmerkt door de compactheid van bestanden en dienovereenkomstig snelle overdracht, evenals "verlies" van beeldkwaliteit. Het wordt voornamelijk gebruikt voor foto's, omdat voor hen het kwaliteitsverlies minder kritisch is. Slaat kleurparameters op in het RGB-kleurmodel.

JPEG(uitgesproken " jpeg", Engels Gezamenlijke groep fotografische experts, genaamd de ontwikkelaarsorganisatie) is een van de populaire grafische formaten die worden gebruikt voor het opslaan van foto's en soortgelijke afbeeldingen. Bestanden die JPEG-gegevens bevatten, hebben meestal de extensie .jpeg, .jfif, .jpg, .JPG, of .JPE. Echter, van deze .jpg de meest populaire extensie op alle platforms. Het MIME-type is image/jpeg.

Het JPEG-algoritme is een algoritme voor gegevenscompressie met verlies.

Toepassingsgebied

Het JPEG-algoritme is het meest geschikt voor het comprimeren van foto's en schilderijen met realistische scènes met vloeiende overgangen van helderheid en kleur. JPEG wordt het meest gebruikt in digitale fotografie en voor het opslaan en verzenden van afbeeldingen via internet.

Aan de andere kant is JPEG ongeschikt voor het comprimeren van tekeningen, tekst en karakterafbeeldingen, waarbij het scherpe contrast tussen aangrenzende pixels tot merkbare artefacten leidt. Het is raadzaam om dergelijke afbeeldingen op te slaan in verliesvrije formaten zoals TIFF, GIF, PNG of RAW.

JPEG is (net als andere methoden voor vervormingscompressie) niet geschikt voor het comprimeren van afbeeldingen tijdens verwerking in meerdere fasen, omdat er elke keer dat tussentijdse verwerkingsresultaten worden opgeslagen, vervormingen in de afbeeldingen worden geïntroduceerd.

JPEG mag niet worden gebruikt in gevallen waarin zelfs minimale verliezen onaanvaardbaar zijn, bijvoorbeeld bij het comprimeren van astronomische of medische beelden. In dergelijke gevallen kan de Lossless JPEG-compressiemodus van de JPEG-standaard (die helaas niet wordt ondersteund door de meeste populaire codecs) of de JPEG-LS-compressiestandaard worden aanbevolen.

Compressie

Compressie converteert het beeld van de RGB-kleurruimte naar YCbCr (YUV). Opgemerkt moet worden dat de JPEG-standaard (ISO/IEC 10918-1) op geen enkele manier de keuze van YCbCr reguleert, waardoor andere soorten conversie mogelijk zijn (bijvoorbeeld met een ander aantal componenten dan drie), en compressie zonder conversie (rechtstreeks naar RGB), maar de specificatie JFIF (JPEG File Interchange Format, voorgesteld in 1991 door specialisten van C-Cube Microsystems, en die nu de facto standaard is geworden) omvat het gebruik van de RGB->YCbCr-conversie.

Na de RGB->YCbCr-conversie kan “subsampling” worden uitgevoerd voor de beeldkanalen Cb en Cr, die verantwoordelijk zijn voor kleur, wat bestaat uit het toekennen van gemiddelde waarden van Cb en Cr (verdunningsschema “4:2:0” ). Bovendien worden er voor elk blok van 2x2, in plaats van 12 waarden (4 Y, 4 Cb en 4 Cr), slechts 6 gebruikt (elk 4 Y en één gemiddelde Cb en Cr). Als er hogere eisen worden gesteld aan de kwaliteit van het beeld dat na compressie wordt hersteld, kan het verdunnen slechts in één richting worden uitgevoerd: verticaal (“4:4:0”-schema) of horizontaal (“4:2:2”), of niet uitgevoerd. helemaal niet (“4:4:4”).

De standaard staat ook decimering toe met middeling van Cb en Cr, niet voor een blok van 2x2, maar voor vier pixels die opeenvolgend (verticaal of horizontaal) zijn geplaatst, dat wil zeggen ook voor blokken 1x4, 4x1 (“4:1:1”-schema). als 2x4 en 4x2. Het is ook mogelijk om verschillende soorten verdunning voor Cb en Cr te gebruiken, maar in de praktijk worden dergelijke schema's uiterst zelden gebruikt.

Vervolgens worden de helderheidscomponent Y en de kleurcomponenten Cb en Cr verdeeld in blokken van 8x8 pixels. Elk dergelijk blok wordt onderworpen aan een discrete cosinustransformatie (DCT). De resulterende DCT-coëfficiënten worden gekwantiseerd (in het algemeen worden verschillende kwantiseringsmatrices gebruikt voor Y, Cb en Cr) en verpakt met behulp van Huffman-codes. De JPEG-standaard maakt ook het gebruik van veel efficiëntere rekenkundige codering mogelijk, maar vanwege patentbeperkingen (het patent voor de rekenkundige QM-encoder beschreven in de JPEG-standaard is eigendom van IBM) wordt deze in de praktijk niet gebruikt.

De matrices die worden gebruikt om de DCT-coëfficiënten te kwantiseren, worden opgeslagen in het headergedeelte van het JPEG-bestand. Ze zijn meestal zo geconstrueerd dat hoogfrequente coëfficiënten sterker worden gekwantiseerd dan laagfrequente coëfficiënten. Dit resulteert in het grover maken van kleine details in het beeld. Hoe hoger de compressieverhouding, hoe sterker alle coëfficiënten worden gekwantiseerd.

Wanneer u een afbeelding opslaat als een JPEG-bestand, geeft u een kwaliteitsinstelling op die in een willekeurige eenheid wordt opgegeven, zoals 1 tot 100 of 1 tot 10. Een hoger getal staat doorgaans gelijk aan een betere kwaliteit (en een grotere gecomprimeerde bestandsgrootte). Maar zelfs als de hoogste kwaliteit wordt gebruikt (overeenkomend met een kwantiseringsmatrix die uit slechts één bestaat), zal het gereconstrueerde beeld niet exact overeenkomen met het originele beeld, wat zowel verband houdt met de uiteindelijke nauwkeurigheid van de DCT als met de noodzaak om de beelden af te ronden. waarden van Y, Cb, Cr en coëfficiënten DCT tot op het dichtstbijzijnde gehele getal. De Lossless JPEG-compressiemodus, die geen gebruik maakt van DCT, zorgt voor een exacte match tussen de herstelde en de originele afbeeldingen, maar de lage efficiëntie (de compressieverhouding overschrijdt zelden de 2) en het gebrek aan ondersteuning van softwareontwikkelaars hebben niet bijgedragen aan de populariteit van Lossless JPEG.

Rassen van JPEG-compressieschema's

De JPEG-standaard biedt twee manieren om gecodeerde gegevens weer te geven.

De meest voorkomende, ondersteund door de meeste beschikbare codecs, is de sequentiële weergave van JPEG-gegevens, waarbij het gecodeerde beeld blok voor blok van links naar rechts en van boven naar beneden wordt doorlopen. De hierboven beschreven bewerkingen worden uitgevoerd op elk gecodeerd beeldblok, en de coderingsresultaten worden in de uitvoerstroom geplaatst in de vorm van een enkele “scan”, d.w.z. een reeks gecodeerde gegevens die overeenkomen met een opeenvolgend doorgegeven ("gescande") afbeelding. De hoofd- of "basislijn"-coderingsmodus staat alleen deze representatie toe. De uitgebreide modus maakt, samen met de sequentiële modus, ook progressieve JPEG-gegevenspresentatie mogelijk.

In het geval van progressieve JPEG worden de gecomprimeerde gegevens naar de uitvoerstroom geschreven als een reeks scans, die elk het gehele beeld met steeds meer detail beschrijven. Dit wordt bereikt door in elke scan niet de volledige set DCT-coëfficiënten op te nemen, maar slechts een deel ervan: eerst - laagfrequente, in daaropvolgende scans - hoogfrequente (de "spectrale selectie" -methode, d.w.z. spectrale monsters ), of door sequentieel, van scan tot scan, verfijning van DCT-coëfficiënten (methode van "opeenvolgende benadering", d.w.z. opeenvolgende benaderingen). Deze progressieve weergave van gegevens is vooral handig bij het verzenden van gecomprimeerde afbeeldingen via communicatiekanalen met lage snelheid, omdat u hierdoor een overzicht van de gehele afbeelding kunt krijgen nadat slechts een klein deel van het JPEG-bestand is verzonden.

Beide beschreven schema's (zowel sequentiële als progressieve JPEG) zijn gebaseerd op DCT en maken het in principe niet mogelijk een gereconstrueerd beeld te verkrijgen dat absoluut identiek is aan het origineel. De standaard staat echter ook compressie toe waarbij geen gebruik wordt gemaakt van DCT, maar die is opgebouwd op basis van een lineaire voorspeller (lossless, d.w.z. “lossless”, JPEG), waardoor een volledige, bit-voor-bit, match van het origineel en de herstelde afbeeldingen. Tegelijkertijd bereikt de compressieverhouding voor fotografische afbeeldingen zelden 2, maar in sommige gevallen is er vraag naar de gegarandeerde afwezigheid van vervorming. Merkbaar hogere compressieverhoudingen kunnen worden verkregen met behulp van de JPEG-LS-compressiemethode, die, ondanks de gelijkenis in namen, niet direct gerelateerd is aan de JPEG ISO/IEC 10918-1 (ITU T.81 Recommendation) standaard, beschreven door de ISO/ IEC 14495-1-standaard (ITU T.87-aanbeveling).

Syntaxis en structuur van JPEG-formaat

Het JPEG-bestand bevat de reeks markeringen, die elk beginnen met byte 0xFF, die het begin van de markering aangeeft, en een identificatiebyte. Sommige markeringen bestaan alleen uit dit paar bytes, terwijl andere aanvullende gegevens bevatten, bestaande uit een veld van twee bytes met de lengte van het informatiegedeelte van de markering (inclusief de lengte van dit veld, maar minus de twee bytes van het begin van de markering). marker, d.w.z. 0xFF en de identificatie) en de gegevens zelf.

Basis JPEG-markeringen

Markering	Bytes	Lengte	Doel

Compressiemethode JPEG is de meest gebruikelijke en effectieve compressiemethode. In 1992 werd het een internationale standaard op het gebied van GI. JPEG is een afkorting voor de groep experts die de standaard heeft gemaakt (Joint Photographic Experts Group).

De methode is gebaseerd op het vinden van het verschil tussen aangrenzende pixels. Het coderen wordt in verschillende fasen uitgevoerd.

1. Conversie kleurmodel van de afbeelding (meestal RGB) in het YUV-kleurmodel, een analoog van het Lab-model, waarbij de helderheidscomponent gescheiden is van de kleurcomponent. In het RGB-model resulteert het wijzigen van een kleurcomponent in een verandering in de helderheid van de pixel. In het YUV-model is de Y-component de helderheidscomponent en slaan de U- en V-componenten kleurinformatie op.

Y = 0,299 x R + 0,587 x G + 0,114 x B

U = (B – Y) / 0,433 +128

V = (R – Y) / 0,355 + 128

2. Substeekproef– aangrenzende pixels zijn in paren gegroepeerd in de U- en V-kanalen. Door luminantie en kleur te scheiden, kan er meer aandacht worden besteed aan luminantie dan aan kleurgegevens. Dit proces wordt uitgevoerd voor componenten met verschillende frequenties.

Er worden twee subsamplingmethoden gebruikt: 4:1:1 en 4:2:2. Omdat elke kleur in 3 bytes is gecodeerd, zijn voor het overbrengen van een kleur van 4 pixels (12 bytes in RGB) respectievelijk 6 bytes en 8 bytes nodig. Die. YUV411 vermindert het datavolume met de helft en YUV422 met 1,5 keer. Vanuit wiskundig oogpunt is er een aanzienlijk verlies aan informatie, maar het menselijk oog neemt dit niet waar vanwege de redundantie van informatie in het beeld zelf.

3. Pixels groeperen in blokken, meestal 8x8 groot. In elk monster wordt een registratie van frequentieveranderingen bepaald (hoe vaak de helderheid en kleur van de pixels veranderen), de zogenaamde discrete cosinustransformatie(DCT). De helderheid wordt dus vervangen door de frequentie waarmee een bepaalde helderheid voorkomt. De bestandsgrootte kan in dit stadium toenemen, maar de volgende stappen zullen dit elimineren.

4. Kwantisering– verwijdering van informatie die voor het oog onbeduidend is. Alle componenten zijn onderverdeeld in coëfficiënten van relatief belang en afgerond op het dichtstbijzijnde gehele getal.

Het is in dit stadium dat de grootste verliezen optreden. Hoogfrequente componenten worden grofweg gekwantiseerd, laagfrequente componenten worden nauwkeuriger gekwantiseerd, omdat het meest opvallend. Om verliezen in het luminantiekanaal te verminderen worden kleinere coëfficiënten gebruikt dan in de chrominantiekanalen. De hoeveelheid kwantisering kan worden gewijzigd, waardoor u de hoeveelheid compressie en daarmee de beeldkwaliteit kunt regelen.

5. Zigzag-podium. Het podium wordt zo genoemd vanwege het feit dat de pixels op grootte worden samengevoegd in een reeks (de pixels die verantwoordelijk zijn voor grotere objecten worden eerst gerangschikt). De encoder beweegt alsof hij zigzagt.

6. Compressie met behulp van de RLE-methode.

7. Compressie met behulp van de JPEG-methode.

JPEG is beter in het comprimeren van grijswaardenafbeeldingen met een hoge resolutie. Belangrijke opmerking: het formaat mag alleen als eindresultaat worden gebruikt, omdat Elke keer dat u een bestand opent en vervolgens comprimeert, wordt de originele afbeelding gecomprimeerd. Als u een afbeelding dus herhaaldelijk comprimeert, wordt deze na verschillende compressiefasen mogelijk niet herkend.

Zelftestvragen.

1. Waarom zijn algoritmen voor datacompressie nodig?

2. Wat is verliesvrije compressie en verliesgevende compressie?

3. Beschrijf de basisalgoritmen voor verliesloze compressie voor grafische informatie.

4. Beschrijf het JPEG-compressie-algoritme.

Toepassingsgebied

Het JPEG-algoritme is het meest geschikt voor het comprimeren van foto's en schilderijen met realistische scènes met vloeiende overgangen van helderheid en kleur. JPEG is het meest wijdverspreid in digitale fotografie en voor het opslaan en verzenden van afbeeldingen via internet.

JPEG mag niet worden gebruikt in gevallen waarin zelfs minimale verliezen onaanvaardbaar zijn, bijvoorbeeld bij het comprimeren van astronomische of medische beelden. In dergelijke gevallen kan de Lossless JPEG-compressiemodus van de JPEG-standaard (die echter niet wordt ondersteund door de meeste populaire codecs) of de JPEG-LS-compressiestandaard worden aanbevolen.

Compressie

Na de RGB->YCbCr-conversie voor de beeldkanalen Cb en Cr, die verantwoordelijk zijn voor kleur, kan “subsampling” worden uitgevoerd, wat erin bestaat dat elk blok van 4 pixels (2x2) van het helderheidskanaal Y de gemiddelde waarden van Cb en Cr (verdunningsschema “4:2:0”). Bovendien worden er voor elk blok van 2x2, in plaats van 12 waarden (4 Y, 4 Cb en 4 Cr), slechts 6 gebruikt (elk 4 Y en één gemiddelde Cb en Cr). Als er hogere eisen worden gesteld aan de kwaliteit van het beeld dat na compressie wordt hersteld, kan het verdunnen slechts in één richting worden uitgevoerd: verticaal (“4:4:0”-schema) of horizontaal (“4:2:2”), of niet uitgevoerd. helemaal niet (“4:4:4”).

De standaard staat ook decimering toe met middeling van Cb en Cr, niet voor een blok van 2x2, maar voor vier pixels die opeenvolgend (verticaal of horizontaal) zijn geplaatst, dat wil zeggen ook voor blokken 1x4, 4x1 (“4:1:1”-schema). als 2x4 en 4x2 (schema “4:1:0”). Het is ook mogelijk om verschillende soorten verdunning voor Cb en Cr te gebruiken, maar in de praktijk worden dergelijke schema's uiterst zelden gebruikt.

Vervolgens worden de helderheidscomponent Y en de kleurcomponenten Cb en Cr verdeeld in blokken van 8x8 pixels. Elk dergelijk blok wordt onderworpen aan een discrete cosinustransformatie (DCT). De resulterende DCT-coëfficiënten worden gekwantiseerd (over het algemeen worden verschillende kwantiseringsmatrices gebruikt voor Y, Cb en Cr) en verpakt met behulp van run- en Huffman-codering. De JPEG-standaard maakt ook het gebruik van veel efficiëntere rekenkundige codering mogelijk, maar vanwege patentbeperkingen (het patent voor de rekenkundige QM-encoder beschreven in de JPEG-standaard is eigendom van IBM) wordt deze in de praktijk zelden gebruikt. Recente versies van de populaire libjpeg-bibliotheek bieden ondersteuning voor rekenkundige codering, maar het bekijken van afbeeldingen die met deze methode zijn gecomprimeerd, kan problematisch zijn omdat veel kijkers het decoderen ervan niet ondersteunen.

Wanneer u een afbeelding opslaat als een JPEG-bestand, geeft u een kwaliteitsinstelling op die in een willekeurige eenheid wordt opgegeven, zoals 1 tot 100 of 1 tot 10. Een hoger getal staat doorgaans gelijk aan een betere kwaliteit (en een grotere gecomprimeerde bestandsgrootte). Maar zelfs als de hoogste kwaliteit wordt gebruikt (overeenkomend met een kwantiseringsmatrix die uit slechts één bestaat), zal het gereconstrueerde beeld niet precies samenvallen met het originele beeld, wat zowel verband houdt met de eindige nauwkeurigheid van de DCT-uitvoering als met de noodzaak om het beeld af te ronden. de waarden van Y-, Cb-, Cr- en DCT-coëfficiënten tot op het dichtstbijzijnde gehele getal. De Lossless JPEG-compressiemodus, die geen gebruik maakt van DCT, zorgt voor een exacte match tussen de herstelde en de originele afbeeldingen, maar de lage efficiëntie (de compressieverhouding overschrijdt zelden de 2) en het gebrek aan ondersteuning van softwareontwikkelaars hebben niet bijgedragen aan de populariteit van verliesvrije JPEG.

Rassen van JPEG-compressieschema's

De JPEG-standaard biedt twee manieren om gecodeerde gegevens weer te geven.

De meest voorkomende, ondersteund door de meeste beschikbare codecs, is de sequentiële weergave van JPEG-gegevens, waarbij het gecodeerde beeld blok voor blok van links naar rechts en van boven naar beneden wordt doorlopen. De hierboven beschreven bewerkingen worden op elk gecodeerd beeldblok uitgevoerd en de coderingsresultaten worden in de uitvoerstroom geplaatst in de vorm van een enkele “scan”, dat wil zeggen een array van gecodeerde gegevens die overeenkomen met de opeenvolgend doorgegeven (“gescande”) gegevens. afbeelding. De hoofd- of "basislijn"-coderingsmodus staat alleen deze representatie toe. De uitgebreide modus maakt, samen met de sequentiële modus, ook progressieve JPEG-gegevenspresentatie mogelijk.

In het geval van progressieve JPEG worden de gecomprimeerde gegevens naar de uitvoerstroom geschreven als een reeks scans, die elk het gehele beeld met steeds meer detail beschrijven. Dit wordt bereikt door in elke scan niet de volledige set DCT-coëfficiënten op te nemen, maar slechts een deel ervan: eerst - laagfrequente, in daaropvolgende scans - hoogfrequente (de "spectrale selectie" -methode, dat wil zeggen: spectrale monsters), of door sequentiële, van scan tot scan, verfijning van DCT-coëfficiënten (methode van “opeenvolgende benadering”, dat wil zeggen opeenvolgende benaderingen). Deze progressieve weergave van gegevens is vooral handig bij het verzenden van gecomprimeerde afbeeldingen via communicatiekanalen met lage snelheid, omdat u hierdoor een overzicht van de gehele afbeelding kunt krijgen nadat slechts een klein deel van het JPEG-bestand is verzonden.

Beide beschreven schema's (zowel sequentiële als progressieve JPEG) zijn gebaseerd op DCT en maken het in principe niet mogelijk een gereconstrueerd beeld te verkrijgen dat absoluut identiek is aan het origineel. De standaard staat echter ook compressie toe die geen DCT gebruikt, maar is gebouwd op basis van een lineaire voorspeller (lossless, dat wil zeggen “lossless”, JPEG), waardoor een volledige, bit-voor-bit, overeenkomst met het origineel wordt gegarandeerd. en gerestaureerde afbeeldingen. Tegelijkertijd bereikt de compressieverhouding voor fotografische afbeeldingen zelden 2, maar in sommige gevallen is er vraag naar de gegarandeerde afwezigheid van vervorming. Merkbaar hogere compressieverhoudingen kunnen worden verkregen met behulp van de JPEG-LS-compressiemethode, die, ondanks de gelijkenis in namen, niet direct gerelateerd is aan de JPEG ISO/IEC 10918-1 (ITU T.81 Recommendation) standaard, beschreven door de ISO/ IEC 14495-1-standaard (ITU T.87-aanbeveling).

Syntaxis en structuur

Het JPEG-bestand bevat de reeks markeringen, die elk beginnen met byte 0xFF, die het begin van de markering aangeeft, en een identificatiebyte. Sommige markeringen bestaan alleen uit dit paar bytes, terwijl andere aanvullende gegevens bevatten, bestaande uit een veld van twee bytes met de lengte van het informatiegedeelte van de markering (inclusief de lengte van dit veld, maar minus de twee bytes van het begin van de markering). marker, dat wil zeggen 0xFF en de identificatie) en de gegevens zelf. Dankzij deze bestandsstructuur kunt u snel een markering vinden met de benodigde gegevens (bijvoorbeeld lijnlengte, aantal lijnen en aantal kleurcomponenten van de gecomprimeerde afbeelding).

Basis JPEG-markeringen

Markering	Bytes	Lengte	Doel	Opmerkingen
SOI	0xFFD8	Nee	Begin van afbeelding
SOF0	0xFFC0	variabele grootte	Begin van frame (basis, DCT)	Geeft aan dat de afbeelding in de basismodus is gecodeerd met behulp van DCT- en Huffman-code. De markering bevat het aantal lijnen en de lengte van de beeldlijn (velden van twee bytes met respectievelijk een offset van 5 en 7 ten opzichte van het begin van de markering), het aantal componenten (byteveld met een offset van 8 ten opzichte van het begin van de markering), het aantal bits per component (byteveld met offset 4 ten opzichte van het begin van de markering), evenals de verhouding van componenten (bijvoorbeeld 4:2:0).
SOF1	0xFFC1	variabele grootte	Begin van frame (uitgebreid, DCT, Huffman-code)	Geeft aan dat de afbeelding in de uitgebreide modus is gecodeerd met behulp van DCT- en Huffman-code. De markering bevat het aantal lijnen en lijnlengte van de afbeelding, het aantal componenten, het aantal bits per component en de componentverhouding (bijvoorbeeld 4:2:0).
SOF2	0xFFC2	variabele grootte	Begin van frame (progressief, DCT, Huffman-code)	Geeft aan dat de afbeelding in progressieve modus is gecodeerd met behulp van DCT- en Huffman-code. De markering bevat het aantal lijnen en lijnlengte van de afbeelding, het aantal componenten, het aantal bits per component en de componentverhouding (bijvoorbeeld 4:2:0).
DHT	0xFFC4	variabele grootte	Bevat Huffman-tabellen	Specificeert een of meer Huffman-tabellen.
DQT	0xFFDB	variabele grootte	Bevat kwantiseringstabellen	Specificeert een of meer kwantiseringstabellen.
DRI	0xFFDD	4 bytes	Specificeert het herhalingsinterval	Stelt het interval tussen RST-markeringen in N in macroblokken.
Sos	0xFFDA	variabele grootte	Begin met scannen	Het begin van de eerste of volgende scan van een afbeelding met de verplaatsingsrichting van links naar rechts, van boven naar beneden. Als de basiscoderingsmodus is gebruikt, wordt één scan gebruikt. Bij gebruik van progressieve modi worden meerdere scans gebruikt. De SOS-markering is de scheidingsteken tussen de informatieve (header) en gecodeerde (eigenlijk gecomprimeerde gegevens) delen van de afbeelding.
RST N	0xFFD N	Nee	Opnieuw opstarten	Ingevoegd in elke R macroblok, waar R- Herstartinterval van de DRI-markering. Niet gebruikt als er geen DRI-markering is. N, lage 3 bits van de codemarkering, cycli van 0 tot 7.
APP N	0xFFE N	variabele grootte	Ingesteld per toepassing	De EXIF van een JPEG-bestand gebruikt bijvoorbeeld de APP1-markering om metadata op te slaan die zijn gerangschikt in een op TIFF gebaseerde structuur.
COM	0xFFFE	variabele grootte	Opmerking	Bevat de tekst van de opmerking.
EOI	0xFFD9	Nee	Einde van het gecodeerde deel van de afbeelding.

Voor- en nadelen

De nadelen van compressie volgens de JPEG-standaard zijn onder meer het optreden van karakteristieke artefacten in herstelde afbeeldingen bij hoge compressiesnelheden: het beeld wordt verspreid in blokken van 8x8 pixels (dit effect is vooral merkbaar in beeldgebieden met vloeiende veranderingen in helderheid), in gebieden bij een hoge ruimtelijke frequentie (bijvoorbeeld contrastcontouren en beeldgrenzen) verschijnen artefacten in de vorm van ruishalo's. Opgemerkt moet worden dat de JPEG-standaard (ISO/IEC 10918-1, bijlage K, clausule K.8) voorziet in het gebruik van speciale filters om blokkerende artefacten te onderdrukken, maar in de praktijk zijn dergelijke filters, ondanks hun hoge efficiëntie, praktisch niet gebruikt. Ondanks zijn tekortkomingen is JPEG echter zeer wijdverspreid geworden vanwege de vrij hoge (in vergelijking met alternatieven die bestonden op het moment van verschijnen) compressieverhouding, ondersteuning voor compressie van kleurenafbeeldingen en relatief lage rekencomplexiteit.

JPEG-compressieprestaties

Om het compressieproces volgens de JPEG-standaard te versnellen, wordt traditioneel gebruik gemaakt van parallellisatie van berekeningen, vooral bij het berekenen van DCT. Historisch gezien wordt een van de eerste pogingen om het compressieproces met deze aanpak te versnellen beschreven in een artikel dat in 1993 werd gepubliceerd door Kasperovich en Babkin, waarin een originele DCT-benadering werd voorgesteld die het mogelijk maakt om berekeningen efficiënt te parallelliseren met behulp van 32-bits algemene doeleinden. registers van Intel 80386-processors. Degenen die later productievere computercircuits verschenen, gebruikten SIMD-uitbreidingen van de instructieset van x86-processors. Aanzienlijk betere resultaten kunnen worden bereikt door schema's die de rekenmogelijkheden van grafische versnellers (NVIDIA CUDA en AMD FireStream-technologieën) gebruiken om parallelle berekeningen te organiseren van niet alleen DCT, maar ook andere stadia van JPEG-compressie (conversie van kleurruimte, run-level, statistische codering, enz.), en voor elk 8x8 blok gecodeerde of gedecodeerde afbeelding. Het artikel was voor het eerst [ bron?] presenteert een implementatie van parallellisatie van alle fasen van het JPEG-algoritme met behulp van CUDA-technologie, die de prestaties van compressie en decodering met behulp van de JPEG-standaard aanzienlijk versnelde.

In 2010 plaatsten wetenschappers van het PLANETS-project instructies voor het lezen van het JPEG-formaat in een speciale capsule, die in een speciale bunker in de Zwitserse Alpen werd geplaatst. Dit werd gedaan met als doel informatie over digitale formaten die aan het begin van de 21e eeuw populair waren, voor het nageslacht te bewaren.