Een simpel algoritme voor foto-compressie

download spic download complete Delphi-7 project

Nieuw: versie 5

spic versie 5 heeft de volgende eigenschappen
    - maximale grootte van plaatjes 4000 * 3000 (h*v) pixels
    - gedecomprimeerde (*.pic) plaatjes kunnen weer als *bmp bestand worden bewaard
    - ook .jpg afbeeldingen kunnen worden geladen
download spic5 programma download complete Delphi-7 project

Image Compressie

In dit artikel beschrijf ik het Delphi project spic dat plaatjes comprimeert.
Die plaatjes staan in bitmaps.
Het project produceert uit de bitmap pixels een (.pic) bestand, dat uit minder bits bestaat dan de bitmap.

Bekende formaten van gecomprimeerde bitmaps zijn: .gif , .jpg en .png.
Verderop in dit artikel zal ik de resultaten van .pic hiermee vergelijken.
Afbeeldingen zijn ruwweg in twee categorieŽn te verdelen: foto's en geometrische figuren.
De eerste hebben meestal veel kleuren en kleurschakeringen en de tweede tonen vaak
rechthoekige vlakken van ťťn kleur en rechte lijnen.

Mijn spic project richt zich op foto's en schilderijen.
Voor geometrische figuren zijn betere compressiemethoden te bedenken al zijn de resultaten van spic ook niet slecht.

Hieronder een verkleinde afbeelding van spic aan het werk:
Het schilderij van de zeeslag is gereduceerd tot 16,07% van de oorspronkelijke omvang van het .bmp formaat.

Aanpak.

Een bitmap waarin de pixels willekeurige kleuren hebben is nauwelijks te comprimeren.
Compressie is alleen mogelijk als er een bepaalde regelmaat in het plaatje aanwezig is.
Te denken is dan aan zich herhalende patronen, delen met dezelfde kleur of delen van de figuur met een beperkt aantal kleuren.
Ook is reductie te bereiken door het aantal mogelijke kleuren te beperken.
Ik heb een aantal benaderingen onderzocht en zo is gaandeweg het beste resultaat bereikt,
althans voor het type plaatjes als de zeeslag hierboven.
Uiteindelijk zegevierde een opvallend simpele aanpak.

Kleuren.

Een bitmap in true color formaat heeft meestal kleuren van 24 bits, die in het 32 bit format
zo in de bitmap zijn opgeslagen:
De intensiteit van de drie basiskleuren loopt van 00000000 .. 11111111 (0..255) dus 8 bits per kleur.
Spic gebruikt het 32 bit pixelformat omdat dit simpele en snelle adressering mogelijk maakt.

Nu zijn voor het menselijk oog verschillen in de laagste paar bits nauwelijks te zien.
Wat geŽxperimenteer leverde op, dat zelfs de kleuren wel op 4 bits, dus veelvouden van 16,
konden worden afgerond. Zodat 12 bits kleuren (maximaal 4096) overblijven.
Dat lijkt drastisch, maar wat is de afrondingsfout?
1110 1000 afronden naar 1111 0000 levert slechts een fout van 8/256 = 3,125%.
Eigenlijk iets meer, want de "hogere" kleuren leveren voor het oog meer verschil dan de lagere.
Een andere kleine reductie is om de kleur 0000 niet toe te staan.
Voor het oog is er geen verschil tussen 0000 0000 en 0001 0000.
Per basiskleur zijn nu dus 15 intensiteiten mogelijk 0001 (1) .. 1111 (15)
Het zeeslagplaatje heeft trouwens dit kleurformaat.

De afronding gaat iets anders in zijn werk dan men aanvankelijk zou verwachten.
I.h.a. gaat afronden van een getal op een veelvoud als volgt
    - tel de helft van het veelvoud op bij het getal
    - kap af op een veelvoud
Nu doet zich een probleem voor als we 1111 1100 afronden:
    1111 1100
    0000 1000 +
    ----------------
    10000 0100 afkappen op 16 tallen:
    10000 0000
Maar nu heeft de kleur (rood, groen of blauw) de waarde 16, wat niet past in 4 bits.
Daarom wordt de waarde met 1 verminderd, dus 1 0000 - 1 = 1111 .
Het eindresultaat is , dat de basiskleuren worden gereduceerd tot 4 bits,
dat is hexadecimaal $1 .. $f, waarbij $1 staat voor $1f en $f voor $ff.
Zo blijft de helderheid behouden, want het verschil tussen $ff ff ff (wit) en $f0 f0 f0 is nog wel te zien.

Pixels

Bij het inkleuren van een bitmap zijn er twee variabelen: de positie [x,y] en de kleur.
De kleur is in ons geval 12 bits, maar de positie is minstens 2 x 10 = 20 bits.
Het handigst is dus om de pixels volgens een vaste volgorde te doorlopen en de kleur erbij te zoeken,
niet omgekeerd.
Spic heeft 5 manieren om per pixel de kleur te bepalen
    1. KopiŽren van de linkerbuur
    2. KopiŽren van de bovenbuur
    3. Kiezen uit een tabel (stack) van eerder gebruikte kleuren
    4. De linkerbuurkleur een beetje veranderen
    5. Een nieuwe kleur toevoegen
Eerst verliep de scan over horizontale lijnen van linksboven naar rechtsonder.
Maar meer reductie bleek mogelijk door te scannen per blokje van 4 x 4 pixels, zie plaatje:
In latere versies is de blokgrootte verhoogd tot 16 * 16 pixels.

Elke pixel wordt dus ťťn keer bezocht, waarbij meteen de kleur wordt vastgesteld.
De commandocodes zijn 2 bits groot, soms gevolgd door een 2 bit subcode en
nog een rijtje bits voor kleur of stack adres:
    00 00 rrrr gggg bbbb nieuwe kleur met rood, groen,blauw
    00 01 Hmarker
    00 10 Vmarker
    00 11 rgb ddd Delta
    01 sssss kleur uit stack[sssss] (0..31)
    10 kopieer kleur van linkerbuur
    11 kopieer kleur van bovenbuur
Als (in het ongunstigste geval) voor elk pixel een nieuwe kleur moet worden gekozen,
dan is de reductie ten opzichte van een 24bit kleur 16/24 = 66,7%

Als altijd een buur gekopieerd kan worden (het gunstigste geval) dan is de reductie 2/24=8,3% .
Veel meer zullen we zien.

Keuze van een kleur uit het stack levert een reductie tot 8/24 = 33%.

Met de codes heb ik uitgebreid gevarieerd: korte codes voor veel voorkomende gevallen,
lange codes voor situaties waarin veel reductie mogelijk was zoals in ťťn keer invullen van hele vlakken.
Je kunt bijvoorbeeld alleen een 1 gebruiken voor het kopiŽren van de linkerbuur en
voor andere gevallen 01, 001 enzovoorts gebruiken.
Maar de keuze hierboven won het.

Markers

Een .pic bestand is een stroom bits van aaneengeregen commando's in de volgorde van de gescande pixels.
Als een rijtje pixels dezelfde kleur heeft, dan levert dat op:
    101010101010101010101010101010 (15 keer linkerkleur gekopiŽerd)
Dit patroon komt vaak voor, vooral natuurlijk bij geometrische figuren.
Zodat het voor de hand ligt om deze bitstream ook weer te comprimeren.
Dat zou kunnen door er een "envelopje" van extra commando's omheen te doen,
maar dat levert extra bits op wat de compressie vermindert.
Zou er geen manier zijn om hier compresssie te bereiken zonder overhead?
Dat kan, de eerste versies van spic gebruikten een ongebruikte codecombinatie.
Maar de bitsream compressie leverde zoveel op, dat het voordelig was om andere codes
iets groter te maken voor juist korte -in line- codes voor de bitstream compressie.
Een marker staat voor een aantal opvolgende -10- of -11- codes.
Een -10- of -11- code wordt niet meteen geschreven, maar verhoogt alleen een teller.
Bij voldoende codes wordt de marker geschreven en niet de codes.
Ingestelde waarde is -10101010- of -11111111- per marker.
Dat geeft al meteen een extra reductie tot 50% want een marker is 4 bits lang.
Maar het gaat verder. Nadat de marker is geschreven staat de compressie in marked mode.
Elke volgende -10101010- of -11111111- stroom wordt nu vervangen door een enkele -1-.
De marked mode wordt beŽindigd door een enkele -0- te schrijven.
De cumulatieve reductie van 12 opvolgende -10- of -11- (copy) codes is dus (4+2+1)/(12*24) = 2,4%

Het stack

Een stackgrootte van 32 kleuren bleek optimaal.

Elke ingevulde pixelkleur wordt (in 12 bit formaat) aan het stack toegevoegd op de eerste plaats,
waarbij de al aanwezige kleuren ťťn plaats omlaag zakken en de onderste kleur verdwijnt.
Zo bevat het stack dus steeds de 32 meest recente kleuren.
Komt een toegevoegde kleur al in het stack voor, dan stijgt die kleur naar de eerste plaats en
de kleuren in stack[0......kleur-1] zakken ťťn plaats.

Delta

Op schilderijen en foto's gaan kleuren vaak vloeiend in elkaar over.
Er is maar een beetje verschil tussen twee buurpixels.
Het delta commando kan de basiskleuren van de linkerbuur iets verhogen of verlagen om de nieuwe kleur te maken.

Het rgb veld is een rijtje van 3 bits,
    0 : geen verandering voor deze basiskleur 1 : wel verandering
Het ddd veld geeft per basiskleur het type verandering
    0 : +1 maar: als de kleur $f is, dan -2
    1 : -1 maar: als de kleur al $1 is, dan +2

Samenvatting

Hieronder staan de mogelijke kleurselecties voor een pixel nog eens op een rij:


File formaat

De commando's worden naar array[0.. maxdir] of dword genaamd director geschreven:
Het eerste dword bevat de file identificatie, het tweede de bitmap afmetingen,
type en een revisienummer. C1,C2... zijn de bitstream commando's.

Hiermee is het .pic formaat beschreven voor de reductie van 24 bit kleuren.
Het is op te vatten als een soort RISC (reduced instruction set).
De winst zit in de superkorte codes en de bitstream compressie.

Trucs die het niet gehaald hebben

1. De Mixer
Dit commando had het format xx rgb.
Voor r=0 werd de rode basiskleur van de linkerbuur gebruikt, voor r=1 van de bovenbuur.
Enzovoorts. De extra code woog niet op tegen de paar hits.

2. Bevriende kleuren
In een array[0..7, 0..4095] werden per kleur tot 8 buurkleuren bewaard.
Zelfde nadeel als bij 1.

3. Meerdere pixels bewerken per commando
Is geprobeerd in vorige compressieprogramma's, maar de reductie is nooit onder de 30% uitgekomen.
Wel is veel reductie te behalen bij geometrische figuren, waar vlakken met ťťn commando ingekleurd kunnen worden.

Grijstinten

Als extraatje heb ik de mogelijkheid ingebouwd om kleurenplaatjes in grijstinten uit te beelden.
Dan geldt dus dat de velden rood-groen-blauw allemaal gelijk zijn, hun waarde varieert van 1..15
Voor de compressie van een grijs plaatje zijn er deze commando's
    00 00 delta +
    00 01 Hmarker
    00 10 Vmarker
    00 11 delta -
    01 ggggnieuwe kleur
    10kopiŽer linkerpixel
    11kopiŽer bovenpixel
Gebruik van een stack levert geen voordeel op omdat een kleur maar 4 bits heeft.
De grijstinten worden verkregen door optelling van de 12 bits kleuren en deling door drie:
    (rrrr 1111 + gggg 1111 + bbbb 1111 ) / 3 or $0f0f0f

Bitmap adressering

Na het laden van een bitmap (bm) wordt deze in het 32bit formaat gezet met
    bm.pixelformat := pf32bit
Zie hierboven voor de layout.
De TBitmap class heeft oa. de property scanline[y] , die de pointer levert naar het adres
van het meest linkse pixel van rij y.
Ik vind het handig om die pointers als dword te bewaren en er mee te rekenen:
type PDW = ^dword;
var po,ps,p : dword;
.....
p0 := dword(scanline[0]);
ps := p0-dword(scanline[i];//ps = pointer step tussen opvolgende     
                           //rijen

Pixel [x,y] is nu te lezen met

p := p0 - y*ps + (x shl 2); // x * 4 om van byte adres een dword 
                            //adres te maken.
color := PDW(p)^;
Merk op: p + ps wijst naar de bovenbuur van p.

Randen

Voor y = 0 is er geen bovenbuur en voor x=0 geen linkerbuur.
Maar we veronderstellen een wit randje om het plaatje,
zodat op deze lijnen de commando's -10- en -11- wel zijn te gebruiken om een pixel wit te kleuren.

Bitstromen

Bij het maken of lezen van een .pic bestand wordt gewerkt met korte bitstrings
van verschillende lengtes (maar altijd < 32)
Het .pic bestand wordt aangemaakt in een array genaamd director.
De variabele dirPtr is de index.
Voor de assemblage van een dword dient een variabele genaamd accu.
acount is het aantal bits in (de) accu.
var director : array[0..maxdir] of dword;
      dirPtr : dword;
      accu   : dword;
      acount : byte;
Het plaatje hieronder laat zien hoe drie opvolgende bitstrings naar de director geschreven worden:
Strings 1,2,3 worden achtereenvolgens via accu naar de director geschreven.
Is de accu vol (acount = 32) dan wordt de accu naar director[dirPtr] geschreven en dirPtr wordt 1 verhoogd,
acount wordt 0 gemaakt.
Hierboven is voor de duidelijkheid de accu twee maal getekend,
zodat is te zien waar het niet passende stukje van string 3 blijft.

Bij het lezen verschijnt eerst het laagste bit.
Als pakketje 10101010 in ťťn opdracht is geschreven maar bit voor bit wordt teruggelezen
dan verschijnt de rechter 0 eerst en daarna de 1.

Resultaten

Hieronder staan wat resultaten met verschillende plaatjes
    zeeslaghuizenMadoffraster strepenfill
    naam% gif% png% pic
    zeeslag23,666,216,07
    huizen18,157,514,75
    Madoff1714,812,39
    raster10,52,54
    strepen0,970,972,06
    fill0,890,4610,81
De tekst bij "Madoff" (die door rechercheurs wordt ondervraagd) luidt:
"Where did you get the idea of paying early investors with the money of late investors?".
Antwoord: "from the social security system".

png is dus zeer sterk bij geometrische figuren maar heel zwak bij foto's en schilderijen.
Overigens is jpg klassen beter, maar wel ten koste van kwaliteitsverlies.
De zeeslag wordt door jpg bij 100% kwaliteit tot 33% gecomprimeerd.
Bij 50% kwaliteit tot maar liefst 4,2% .
Als de afmetingen van een plaatje worden gehalveerd voor .pic compressie,
dan is bij de zeeslag reductie te verwachten tot 0,25 * 16 = 4%.
Daarna moet de afbeelding natuurlijk 2 x vergroot worden.

Het spic project

Dat bestaat uit
    - form1 / unit1
      - knoppen voor load, store, compressen, decompressen, grijsmaken
      - event methods
      - controle van het programma
      - statistiek
      - paintbox voor het weergeven van de bitmaps
      - labels voor het tonen van gegevens en statistiek.
    - compressunit
      - procedures voor compressen en decompressen
      - procedures voor het tellen van het aantal kleuren tbv de statistiek

Data flows

Na decompressie van de directorlijst naar bitmap dmap,
vindt een pixel voor pixel vergelijking plaats met het oorspronkelijke beeld in bm.
Het heeft een weekje gekost voor dat foutloos ging.

O ja, er is nog een bitmap backupmap, die een kopie bevat van bm.
Met een klik op de restore knop wordt bm herladen met backupmap.

Data formaten

12 bit kleur in bitmap
12 bit kleur in stack
Tellen van het aantal verschillende kleuren:

In een tabel van 4096 bits (128 dwords) wordt bit [rrrr gggg bbbb] op de waarde -1- gezet.
Nadat alle pixels zijn bekeken worden de -1- bits in de tabel geteld.

Programma code

Tot slot van dit artikel nog wat programmacode.

1. Lezen en schrijven van bitstreams van / naar de director tabel
Het implementatiegedeelte van de compressunit begint met
type PDW = ^dword;

const maxdir   = 250000;
      stacklength = 32;
      pic = 'pic';
      spic = 'spic';
      
var director    : array[0..maxdir] of dword;
    dirPtr      : dword;
    accu        : dword;  //bit asembly register
    acount      : byte;   //nr of valid bitsin accu
    map         : Tbitmap;
    p0          : dword;  //left top canvas pointer
    ps          : dword;  //line downstep value
    cc          : array[0..127] of dword; //colorcount bits
    stack       : array[0..stacklength-1] of word;   //rrrrggggbbbb
schrijven van n bits naar de director:
procedure storeCode(w : dword; n : byte);
//store n bits of w to dirictor (via accu)
//n = 1 ..16
var space : byte;
begin
 space := 32 - acount;
 accu := accu or (w shl acount);
 if space >= n then            //if space
  begin
   acount := acount + n;
   if acount = 32 then
    begin
     acount := 0;
     director[dirPtr] := accu;
     inc(dirPtr);
     accu := 0;
    end;
  end
  else                         //if no space
   begin
    director[dirPtr] := accu;
    accu := 0;
    inc(dirPtr);
    accu := w shr space;
    acount := n - space;
   end;
end;
Lezen van n bits uit de director:
function readcode(n : byte) : dword;
//read n bits from director table
var mask : dword;
    space : byte;
begin
 if acount= 0 then
  begin
   accu := director[dirPtr];
   inc(dirPtr);
  end;
 mask := (1 shl n) -1;
 space := 32 - acount;
 result := accu shr acount;
 acount := acount + n;
 if acount = 32 then acount := 0
  else if acount > 32 then
        begin
         accu := director[dirPtr];
         inc(dirPtr);
         dec(acount,32);
         result := (result or (accu shl space));
        end;
 result := result and mask;
end;
Als een nieuwe bitmap is gelezen van disk, dan moet deze in het 12-bit formaat worden gezet:
function fixRGB12(c : byte) : byte; //hulpje van colorfix12
//round 4 bit to $1f,$2f.....$ff
var c1 :  word;
begin
 c1 := (c + $8) and $1f0;
 if c1 < $20 then c1 := $20;
 dec(c1);
 result := c1 and $ff;
end;

procedure colorfix12;
//reduce colors in map to 12 bit
var x,y : word;
    Pline,p  : dword;
    color : dword;
    r,g,b : word;
begin
 clearCC;  //clear colorcount array
 for y := 0 to map.Height-1 do
  begin
   Pline := p0 - y*ps;
   for x := 0 to map.Width-1 do
    begin
     p := pline + (x shl 2);
     color := PDW(p)^;
     r := (color shr 16) and $ff;
     g := (color shr 8) and $ff;
     b := color and $ff;
     r := fixRGB12(r);
     g := fixRGB12(g);
     b := fixRGB12(b);
     color := b or (g shl 8) or (r shl 16);
     PDW(p)^ := color;
     setcolorbit(r,g,b);         //for colorcount;
    end;
  end;
 countcolors;
end;
Voor de programmacode van het gehele project met de compressie- en decompressie procedures
kan met mij contact worden opgenomen. (david@davdata.nl)

Bediening

Het spic programma bevat geen help informatie.
De paar knoppen spreken voor zichzelf.
De unpack (decompress) knop houdt ook in dat de geproduceerde bitmap (dmap)
met de oorspronkelijke bitmap (bm) wordt vergeleken.

Statistiek
Gedurende het compressieproces worden diverse tellers bijgehouden.
Ze staan op het form afgebeeld:
    left aantal kopiŽn van de linkerbuur
    exp.leftaantal kopiŽn van de linkerbuur met compressie (exp = expanded)
    top aantal kopiŽn van de bovenbuur
    exp.topaantal kopiŽn van de bovenbuur met compressie (exp = expanded)
    stackaantal malen dat de kleur door het stack werd geleverd
    new aantal malen dat een nieuwe kleur werd ingevoegd
De optelling van deze tellers is gelijk aan de pixelcount.

Grootte

Er is geen test op te grote bitmaps
Constante maxDir stelt de lengte van de director tabel in.
Nu is de grootte 250000 dwords.
Bij 25% compressie zijn dus nog plaatjes van 4 megabytes te verwerken.
De paintbox om de bitmaps af te beelden is 800 pixels breed en 600 pixels hoog.