Terug in de jaren tachtig ontwikkelde Microsoft een apparaat agnostische beeldweergave-oplossing voor bitmaps: het BMP-bestandsformaat.Wie vroeger Microsoft Paint gebruikte, genoot van de gigantische bestandsgrootte van eenvoudige streken en kleurvullingen.
Het idee achter het BMP-bestandsformaat is dat aan elke pixel een kleurwaarde wordt toegekend. Dus als ik een 480×360 bitmap heb die 16 miljoen kleuren (24 bits) ondersteunt, zou de bitmap uiteindelijk ergens ten noorden van 4MB groot worden.
Dit is natuurlijk niet ideaal als men meerdere afbeeldingen van hoge kwaliteit wil renderen. Vandaar dat de vraag moet worden gesteld. “Is er een manier om de weergave van de bitmap te optimaliseren, zodat de visuele integriteit van de afbeelding behouden blijft, maar met minder middelen?”
Het antwoord is ja. Het blijkt dat gebruikers meestal meer geïnteresseerd zijn in afbeeldingen als visuele hulpmiddelen dan in degelijkheid. Stel bijvoorbeeld dat ik een afbeelding van de Golden Gate Bridge krijg zoals hieronder:
Hoewel ik weet dat de echte brug, wanneer deze in het echt wordt gezien, veel gedetailleerder is, is wat ik hier zie goed genoeg voor het doel. De meeste mensen zijn dus bereid om visuele integriteit in te ruilen voor snelheid, zolang dat maar acceptabel is. Bijvoorbeeld, als de verslechtering in subjectieve visuele kwaliteit 1% is, maar de gebruiker geniet van een ruimtebesparing van 90%, is het voor het grootste deel een welkome ruil.
Hence, one of the key consideration in compressing bitmaps is to optimize for visual indistinguishability. Dat wil zeggen, het verwijderen van bepaalde elementen van een afbeelding waarbij het blote oog niet in staat is het verschil te identificeren. Dit wordt compressie met verlies genoemd, en dit zijn de meeste compressietypes die men ziet bij videostreaming op onlinebeelden. Zo werken H.264-, HEVC-, HEIF- en JPEG-codecs.
Andere soorten afbeeldingen, zoals PNG, worden verliesloos gecomprimeerd. Het idee is dat men de volledige visuele integriteit van de originele afbeelding behoudt, maar minder bytes verbruikt om hetzelfde weer te geven. Er zijn nog andere bestandsformaten, zoals WebP, die zowel lossy als lossless compressie ondersteunen. Waarom willen we verliesloos comprimeren? Zoals hierboven, is het gebaseerd op wat we willen bereiken voor de afbeelding. Bijvoorbeeld, pictogrammen in apps zijn over het algemeen in PNG (en onlangs, in vector graphics formaat).
Verliesloze beeldcompressie bestaat uit een grotere bestandsgrootte in tegenstelling tot lossy compressie. De reden hiervoor is dat er minder mogelijkheden zijn om de eerste te comprimeren dan de tweede. In het kader van deze blog zullen we het hebben over lossy compressie.
De algemene stappen van JPEG-compressie worden tot op de dag van vandaag toegepast bij videocompressie. In de loop der jaren is het algoritme verbeterd, maar de algemene concepten blijven hetzelfde.
STAP 1. Kleurruimteconversie
De beeldconversie begint met het omzetten van het ruwe RGB-beeldformaat naar de Chroma- (r en b) en Luminantie- (Y) waarden. Het idee is dat onze ogen gevoeliger zijn voor veranderingen in helderheid dan voor kleur. Daarom kunnen we het kleurengamma in het beeld downsamplen zonder de visuele kwaliteit van het beeld merkbaar aan te tasten. Dit wordt gedaan door Chroma Subsampling, zoals hieronder uitgelegd.
STAP 2. Chroma Subsampling
Vele gamers herinneren zich wellicht dat subsampling een van de mogelijke knoppen is die zij kunnen instellen om hun spelervaring te optimaliseren. Het idee is dat hoe meer subsampling men doet, hoe sneller de spelprestaties zijn. Dit komt omdat het spel minder kleuren nodig heeft om te renderen.
Chroma subsampling wordt aangeduid met J:a:b waarbij J het aantal pixels is om te subsamplen, a staat voor de pixels in de bovenste rij en b voor de pixels in de onderste rij.
In het geval van 4:4:4 betekent dit dat in een 4×2-pixel de eerste rij (a) 4 kleuren moet hebben en de tweede rij ook. In het geval van 4:2:2 betekent dit dat in een 4×2-pixel de eerste rij twee kleuren moet hebben en de tweede rij ook. In het geval van 4:2:0 betekent dit dat in 4×2 pixels de eerste rij door twee kleuren moet worden weergegeven en dat de tweede rij kopieert wat op de eerste rij staat.
Zoals u ziet, kan men door chroma subsampling het kleurengamma met maar liefst 75% verminderen.
STAP 3. Discrete Cosine Transform
JPEG-compressie wordt uitgevoerd door het oorspronkelijke beeld in stukken van 8×8 pixels te verdelen. In deze stap wijzen we coëfficiënten toe voor de 8×8 brok op basis van de hieronder getoonde signalen.
Het idee hier is dat naarmate het menselijk oog zich van linksboven van de DCT-referentie naar rechtsonder beweegt, het moeilijker wordt om het beeld waar te nemen. Bij het toewijzen van coëfficiënten wordt dus meestal aan de linkerbovenhoek een zeer hoge waarde toegekend, die naarmate men diagonaal naar beneden gaat, steeds lager wordt.
Hier ziet het er in numeriek formaat zo uit:
STAP 4. Kwantisering
Nadat DCT is toegepast, wordt de volgende stap kwantisering genoemd. Hier wordt een kwantiseringstabel toegepast op de resulterende DCT-waarden. De tabel verschilt tussen compressie-algoritmen en sommige software staat de gebruiker toe de hoeveelheid kwantisatie in te stellen die hij wil gebruiken. Hieronder staat een standaardtabel:
Merk op dat de cijfers hoger worden naarmate men van linksboven naar rechtsonder gaat. Dit is met opzet zo gedaan. Het idee van kwantisering is dat de resulterende gegevens van de DCT worden gedeeld met de kwantiseringstabel. Dit is waar het gecomprimeerde beeld veel van zijn gegevens verliest. Omdat de getallen rechtsonder hoog zijn, zullen de meeste waarden uiteindelijk nul worden na deling. Zo zou het eruit kunnen zien:
STAP 5. Entropiecodering met behulp van Huffman-codering
Huffman-codering is de laatste stap in de compressie. Het werkt als volgt.
Stel dat ik een reeks getallen wil weergeven met bits. Bovendien wil ik ze zo weergeven dat ik zo min mogelijk bits verbruik voor de weergave. Dit kan worden gedaan door de sterk herhaalde getallen lagere bits te geven. Als bijvoorbeeld nul veel wordt weergegeven, zou ik het in het algemeen lagere bits toekennen. Een meer diepgaande uitleg van de Huffman-codering kan hier worden gevonden.
Het idee hier is dat je minder bits gebruikt om een langere reeks waarden weer te geven. Huffman-codering is een verliesloos compressie-algoritme dat ook wordt gebruikt bij het comprimeren van tekstbestanden. Door dit te doen, is het mogelijk om tot 50% van de oorspronkelijke grootte te besparen.
What’s Next?
Compressie is slechts een deel van de vergelijking. Wanneer men het beeld moet renderen, moet hij het compressieproces omkeren voordat hij in staat is het beeld op het scherm weer te geven.
JPEG’s zijn ruwweg ongeveer 90% kleiner dan zijn bitmap tegenhanger. Tot op de dag van vandaag is het nog steeds het populairste beeldcompressieformaat. Nieuwere algoritmen zoals HEIF (2013) en AVIF (2018) vergroten het bereik van pixels dat men kan gebruiken voor het compressiealgoritme.²
Ondanks de populariteit van JPEG, bieden nieuwere formaten een betere compressie. WebP bijvoorbeeld is over het algemeen ongeveer 70% kleiner dan JPEG en kan toch de visuele integriteit van het beeld behouden. Daarom heeft Google (het bedrijf dat WebP heeft ontwikkeld) ontwikkelaars aangespoord om hun afbeeldingen te hercoderen van JPEG naar WebP. De ondersteuning voor WebP is echter nog steeds minder dan voor JPEG. Daarom is het noodzakelijk beide formaten te ondersteunen.
¹ “Het BMP-bestandsformaat.” Drukvoorbereiding. Accessed April 19, 2019. https://www.prepressure.com/library/file-formats/bmp.
² Netflix publiceerde de eerste set AVIF-afbeeldingen in 2018. Vanaf dit bericht zijn de afbeeldingen hier nog steeds toegankelijk. Bedrijven als Firefox en Microsoft zullen deze afbeelding binnenkort ondersteunen in hun software-aanbod.