Pieter Edelman
14 October 2016

Zowel Dropbox als Google kwam onlangs met een methode om beelden beter te comprimeren dan jpeg. Hun aanpakken verschillen als dag en nacht.

Jpeg is sinds jaar en dag hét bestandsformaat voor opslag van foto’s vanwege de geringe bestandsgrootte. De researchafdelingen van Dropbox en Google kwamen recentelijk echter allebei naar buiten met nieuwe aanpakken om beelden nog veel kleiner te krijgen dan standaard jpeg. Google’s methode werkt heel anders dan jpeg maar is net als die compressiemethode wel lossy. Dropbox is een beetje verwarrend: wel jpeg, maar niet lossy.

Anders dan bij lossless is het bij lossy compressie toegestaan om de gegevens een beetje te wijzigen als ze daarmee veel beter worden opgeslagen. Hierbij wordt slim gebruikgemaakt van de beperkingen van het menselijke waarnemingsvermogen. Verschillen die we niet of nauwelijks kunnen zien, worden versimpeld of in het geheel weggelaten.

Een voorbeeldje: het menselijke oog kan contrastverschillen met veel hogere resolutie waarnemen dan kleurverschillen (heeft te maken met de staafjes en de kegeltjes). Jpeg en andere lossy methodes kunnen daarom besluiten om alleen contrastverschillen in volledige resolutie op te slaan en de kleurinformatie uit te middelen over twee of vier pixels. Normaal merken we dat niet, zolang de compressie het niet te bont maakt met dit soort trucs.

Voorspelling

Wat Dropbox bedoelt met zijn lossless-aanpak is dat bestaande jpeg-bestanden nog eens meer dan een vijfde kleiner gemaakt kunnen worden, maar wel weer bit voor bit hersteld kunnen worden tot het origineel. Dat is een logische aanpak voor de clouddienst. Gebruikers slaan er miljarden foto’s op en ze verwachten dat die niet ineens veranderen. Dropbox kan echter fors geld besparen als ze gecomprimeerd kunnen worden.

 advertorial 

8-bit Microcontrollers Still Anchor the Majority of Embedded Designs Today

They are tiny, but vitally important. The market for 8-bit microcontrollers continues to grow strongly as a key part of the drive to digitalisation, highlighted by the current chip shortages. Read more about Microchip’s 8-bit devices.

Standaard lossless compressiealgoritmes vangen echter bot bij jpeg. Door de lossy codering zijn er nauwelijks regelmatige patronen te vinden. De Dropbox-researchers moesten dus kijken of er nog op andere manier voorspelbaarheid te behalen valt in jpeg.

Dat bleek het geval. De belangrijkste manier waarop jpeg de bestanden zo klein weet te krijgen, is door de hoogfrequente componenten in het beeld te verzwakken en sterk af te ronden. Intensiteitsverschillen op kleine schaal zijn voor ons niet zo heel duidelijk waarneembaar en vallen doorgaans weg tegen de grovere verschillen.

Jpeg zet het beeld dus om naar het frequentiedomein. Daarvoor wordt een foto opgedeeld in blokjes van acht bij acht pixels. Deze blokjes worden vervolgens (voor elk kleurenkanaal apart) omgezet naar intensiteiten voor 64 standaard bouwstenen van acht bij acht pixels. Die bouwstenen vertegenwoordigen het frequentiedomein; ze worden verkregen door zowel in de x- als in de y-richting met acht opeenvolgende frequenties een sinusvorm te plotten als pixelintensiteit.

De 64 parameters geven aan hoeveel elk van hen bijdraagt aan het beeld; wanneer ze worden vermenigvuldigd met hun bouwsteen en het resultaat bij elkaar wordt opgeteld, verschijnt het originele beeldblokje. In deze representatie kunnen de hoogfrequente componenten dus worden weggemoffeld.

De allerlaagste frequentie laat zich echter niet goed comprimeren; ongeveer acht procent van de data in een gemiddelde jpeg-afbeelding bestaat uit deze zogeheten dc-componenten. Maar Dropbox bedacht dat het wel grotendeels te voorspellen is. Daarvoor wordt eerst het pixelblokje geconstrueerd uit de andere frequenties (de ac-componenten). Door de beeldpunten aan de randen te vergelijken met naastgelegen pixels van reeds gedecodeerde buurblokjes weet de decoder wat ongeveer de intensiteit zal zijn.

voorspelling
De intensiteit van het blokje rechtsonder is heel aardig te voorspellen met de reeds gedecodeerde blokjes.

Er hoeft dus alleen een verschil met deze voorspelling te worden opgeslagen, waarmee ongeveer dertig procent opslagruimte van de dc-componenten af te snoepen is. Wanneer een iets complexere methode wordt gebruikt die naar intensiteitsgradiënten in de naburige blokjes kijkt, neemt de besparing zelfs toe tot bijna veertig procent. Op vergelijkbare manier probeert Dropbox de ac-componenten in een blok te voorspellen uit de context. Daarnaast gebruikt het een slimme manier om deze getallen op te schrijven met een variabel aantal bits. Voor de typische waardes van de ac-coefficiënten levert dit een aanzienlijker compactere schrijfwijze op dan de standaard byte-aanpak.

getal
Dropboxs Lepton-aanpak gebruikt een variabel aantal bits om de ac-componenten op te slaan.

Zwaar gemangeld

De methodes van Dropbox zijn niet helemaal nieuw. Het bedrijf heeft vooral bestaande inzichten samengevoegd en dit in een efficiënte implementatie gegoten, die het nu opensource beschikbaar stelt onder de naam Lepton. Het heeft onder meer afgekeken bij de VP8-codering. Google had hier in 2010 al een eigen lossy formaat op gebaseerd, Webp, dat beter comprimeert dan jpeg. Dat is echter nooit echt aangeslagen.

Het nieuwe werk van Google benadert het probleem van lossy beeldcompressie echter op geheel nieuwe wijze. De zoekmachinegigant pakt het onderwerp op dezelfde manier aan als al zijn problemen vandaag de dag: door er een neuraal netwerk tegenaan te smijten.

Het is een voor de hand liggende gedachte. De convolutionele netwerken die zo veel furore maken binnen de beeldherkenning zijn gebaseerd op het idee dat ze de specifieke hoogniveaukenmerken kunnen abstraheren uit beelden. Zo’n kenmerk kan een horizontale of verticale lijn zijn, of een kleurgradiënt, of een ondefinieerbaar patroon dat veel beelden gemeen hebben – tijdens het trainen van de netwerken komen dit soort patronen vanzelf bovendrijven.

Een eerste aanpak om hier een lossy beeldcompressor van te maken, is om twee complementaire netwerken te trainen. Het eerste is een encodernetwerk. Dat krijgt een blokje pixels in drie kleurdimensies voorgeschoteld, en reduceert dat via een aantal convoluties en andere bewerkingen tot een veel kleiner blokje met veel meer dimensies. Het tweede netwerk, de decoder, neemt dit soort beschrijvingen als input en zet ze weer om in normale pixels.

Deze netwerken dienen gezamenlijk te worden getraind. Per trainingsstap wordt een blokje eerst geëncodeerd en direct weer gedecodeerd. Vervolgens worden de instellingen van beide netwerken aangepast om het verschil tussen het resultaat en het origineel te minimaliseren. Door dit vaak genoeg te herhalen met steeds nieuwe blokjes ontstaan uiteindelijk netwerken die op een brede reeks beelden werken.

vuurtoren
Een neuraal netwerk weet een foto (links) te benaderen, maar het resultaat is niet al te best (midden). Door het verschil met het origineel weer opnieuw te coderen, kan een correctiebeeld worden verkregen.

Het encodernetwerk kan nu worden gebruikt om beelden te reduceren tot een compacte weergave, die als gecomprimeerd bestand wordt opgeslagen. Dit bleek wel te werken, maar het resultaat is niet fantastisch. De beelden lijken op het origineel maar zijn zwaar gemangeld.

De Google-ingenieurs bedachten echter een manier om dat te verbeteren: na de compressie wordt het verschil tussen het origineel en het resultaat opnieuw gevoerd aan een encodernetwerk. Ook dit resultaat wordt toegevoegd aan het bestand. Het decodernetwerk kan deze extra gegevens decomprimeren tot een correctiebeeld voor de eerste afbeelding.

De kwaliteit neemt daarmee gelijk met sprongen toe. Dit kan bovendien nog een aantal keer worden herhaald om het beeld steeds verder te verfijnen. Er moet dan natuurlijk wel steeds meer informatie worden opgeslagen. Net als bij jpeg is er dus een uitruil mogelijk tussen bestandsgrootte en beeldkwaliteit.

Maar de hamvraag was natuurlijk of er een netwerkarchitectuur kan worden gemaakt die beter comprimeert dan jpeg – of Webp – met vergelijkbare kwaliteit. Die was nog niet zo eenvoudig te beantwoorden. Beeldkwaliteit is namelijk vrij subjectief, en de neurale netwerken introduceren andere soorten vertekeningen dan traditionele compressiemethodes.

Uiteindelijk vond het team wel een manier en daarmee denkt het nu een werkende aanpak te hebben. Een belangrijk onderdeel daarvan is het inzetten van een recurrente architectuur. Dit soort neurale netwerken zijn populair voor bijvoorbeeld stemherkenning omdat ze een interne toestand hebben die als ‘kortetermijngeheugen’ werkt: niet alleen de huidige input is van belang maar ook alle voorgaande inputs. Bij de beeldcompressie heeft elke opeenvolgende kwaliteitsstap ook een direct verband met de vorige stap. En inderdaad: met recurrente netwerken lukte het om beelden nog een kwart kleiner te comprimeren dan jpeg.