Bitmaps vergroten en verkleinen
download
resize program		 download hele
Delpi-7 project		 lees de BMresize
code

Voorwoord

Dit is een nieuwe (5 tot 10 maal snellere) versie van mijn oude bitmap resize programma.
Het oude programma is nog hier te vinden.
De snelheidswinst is gerealiseerd met een snellere adressering van de bitmap pixels
en geoptimaliseerde programma code.

Inleiding

Plaatjes in digitale vorm bestaan uit pixels, gekleurde puntjes op een computerscherm.
Bij elk pixel hoort een getal, dat de kleur aangeeft.
Plaatjes in niet gecomprimeerde vorm worden bewaard als *.bmp (bitmap) bestanden.
Een bitmap is een twee dimensionaal array van pixels.

Bitmaps zijn er in verschillende formaten om de pixelkleur aan te geven.
In dit Delphi project gebruik ik het -true color- 32 bit formaat (pf32bit), zie hieronder:
De drie basiskleuren (rood, groen, blauw) hebben elk een 8 bit veld, dus hun intensiteit loopt van 0 to 255.

En zo ziet een (sterk vergroot) pixel er uit:
Hieronder is een bitmap met enkele coördinaten afgebeeld.
Elk vierkantje is een pixel.

Bovenstaande bitmap heeft 5 kolommen [0..4] en 4 rijen [0..3].

Het Algoritme

Een bitmap (bm1) wordt gekopieerd naar een andere (bm2) met andere afmetingen.
Elk pixel van bm2 moet dus worden berekend.
De aanpak is de pixels van bm2 te scannen van links naar rechts en van boven naar onder.
Elk pixel wordt geprojecteerd op bm1 zodat het één of meer pixels van bm1 overlapt.
De kleuren van de overlapte gebieden worden, evenredig met het percentage van de overlapping,
naar het pixel van bm2 gesommeerd.
Kijk hier:

Bitmap afmetingen en adressering

bm1 heeft kolommen 0..7 en rijen 0 .. 7.
bm2 heeft kolommen 0..2 en rijen 0..2.

Vergrotingsfactor

De vergrotingsfactor f = (bm1 breedte) / (bm2 breedte).
In het plaatje hierboven is f = 8/3 = 2.6667
f > 1 betekent verkleining, f < 1 betekent vergroting.

In detail:
Het rode vierkant is een pixel van bm2 geprojecteerd op bm1.

De (doel) bitmap bm2 pixels worden geadresserd met variabelen x (kolom) en y (rij).
[x,y] is doel pixel in kolom x en rij y.
De (bron) bitmap bm1 pixels worden geadresseerd met i (kolom) en j (rij).
[i,j] is een pixel van de bron bitmap in kolom i en rij j.

Verder nemen we aan, dat doelpixels de afmeting 1*1 hebben.
Het rode vierkant heeft dus zijden met lengte f, de vergrotings factor.

sx1 is the left positie of het rode vierkant, sx1 = f * x.
Net zo, sy1 = f * y is de top positie.
sx2 = sx1 + f.
sy2 = sy1 + f.
Merk op, dat x,y,i,j integers zijn. sx1,sy1,sx2,sy2 zijn kommagetallen.

dx * dy is het overlappingsgebied van de pixels.
dx en dy zijn eveneens kommagetallen.

dx * dy is het deel van de kleur van pixel [i,j] dat aan het doelpixel moet worden toegevoegd.
Dit gebeurt:
    1. lees bron pixel [i,j]
    2. isoleer de basiskleuren rood, groen en blauw
    3. vermenigvuldig die basiskleuren met dx*dy en sommeer de waarden per basiskleur.
    4. herhaal stappen 1..3 voor elk overlappende pixel
    5. zet de gesommeerde basiskleuren op hun plaats in een dword (32 bit integer)
    6. schrijf dit dword in pixel [x,y] van de doel bitmap.
Nog één correctie is nodig:
De gesommeerde kleurwaarden slaan op een gebied f*f, maar het doelpixel is 1*1.
De gesommeerde kleurwaarden moeten dus gedeeld worden door f2.
Omdat delen langer duur dan vermenigvuldigen gebruiken we variabele fi2 = 1/(f*f).

Hiermee is het algoritme beschreven.
Er is echter nog een valkuil.

Floating point nauwkeurigheid

In dit project worden floating point getallen gebruikt van het type single, die zijn 32 bits groot.
De nauwkeurigheid hiervan is 7 cijfers, dus 1.5555555555 wordt afgerond naar 1.555556

Stel dat we een 280*280 bitmap naar 180*180 verkleinen.
f = 280 / 180 = 1.555556.
Als we pixel [179,0] projecteren op de bron bitmap dan zien we
sx1 = 1.555556 * 179 = 278.4445 (afgerond)
sx2 = 280.0001 (afgerond)
Oeps! pixel 280 ligt buiten de bitmap en met een access violation komt ons programma abrupt tot stilstand.

Wat nu?
De oplossing is verkleining van het rode vierkant, door het met 0,9999 te vermenigvuldigen.
Breedte fstep = f * 0.9999 = 1.555400
Nu is sx2 = 278.4445 + 1.555400 = 279.9999, mooi binnen de bitmap.
Eigenlijk corrigeren we hier voor afrondingsfouten.

Ook kopiëren naar een bitmap met dezelfde afmetingen, dus f=1, geeft fouten zonder correctie.
Stel dat we een 100*100 bitmap kopiëren.
Bij pixel 99 zien we:
sx1 = 99
sx2 = 99 + 1 = 100, buiten de bitmap.
Maar met correctie: sx2 = 99.9999, binnen de bitmap.

Berekeningen

i en j start, end waarden

In het voorbeeld hierboven moeten de pixels binnen het rode vierkant worden gescand.
Dit gebeurt in twee loops:
1. een buitenste loop : for j := jstart to jend
2. een binnenste loop : for i := istart to iend

code: 
...
jstart := trunc(sy1);
jend := trunc(sy2);
istart := trunc(sx1);
iend := trunc(sx2);      
...
for j := jstart to jend do
....
  for i := istart to iend do
  ....

Onafhankelijke breedte en hoogte

De schaalfactor f wordt vervangen door gescheiden waarden voor breedte en hoogte.
Het plaatje kan zodoende horizontaal of vertikaal worden uitgerekt. 
fx := bm1.width / bm2.width;
fy := bm1.height / bm2.height;
fxStep := 0.9999*fx;
fyStep := 0.9999*fy;
fix := 1/fx;
fiy := 1/fy;
...
sy1 := y*fy;
sy2 := sy1 + fyStep;
...
sx1 := x*fx;
sx2 := sx1 + fxStep;

dx en dy waarden

Berekeningen moeten zoveel mogelijk buiten een loop plaatsvinden.
dx heeft de keuze uit drie waarden:
1. als i=istart, dx=devx1
2. als i=iend, dx=dx - devx2
3. anders dx=1
Zie het plaatje hieronder::
Pas op: istart en iend kan hetzelfde pixel zijn, dus dx wordt verminderd als i=iend,
een vooraf ingestelde waarde is er niet.

Net zo'n aanpak is er voor dy.
1. als j=jstart , dy=devY1
2. als j=jend, dy = dy-devY2
3. anders dy=1
Zie het plaatje hieronder

Loops

De resize procedure heeft een initialiserings deel, gevolgd door vier geneste loops.
De buitenste loop is for y, en adresseert de doel rijen.
Daarbinnen is een for x loop, voor de doel kolommen.
Daar weer binnen een for j loop, voor de bron pixel rijen.
En tenslotte daar binnen de for i loop voor de bron pixel kolommen.

Voor maximale snelheid dient de code in een loop zo klein mogelijk te zijn.
Dit gebeurt.
Initialisering
Bereken fx, fy, fix, fiy, fxStep, fyStep, destwidth, destheight

Binnen for y := 0 to destheight do...........
Bereken sy1, sy2, jstart, jend, devY1, devY2.

Binnen for x := 0 to destwidth do ...........
Bereken sx1, sx2, istart, iend, devX1, devX2.

Opmerking: deze waarden worden opnieuw berekend voor elke waarde van y.
Deze tijd kan bespaard worden door tabellen te gebruiken.
De code wordt daar echter wel gecompliceerder door.
Variabelen destR, destG,destB zijn de gesommeerde basiskleur waarden per [x,y] pixel.
Die worden hier op 0 gezet.
dy krijgt waarde devY1.

Binnen for j := jstart to jend do ..............
Zet dx = devX1
Pas dy aan als j = jend

Binnen for i := istart to iend do ...............
Pas dx aan als i = iend.
Lees kleur van pixel [i,j] van bron bitmap.
Extraheer sR, sG, sB, de basiskleuren.
Bereken AP = fix*fiy*dx*dy, (area percentage)
Tel kleuren bij destR, destG, destB:
destR := destR + sR*AP.......etc.

Na de i loop........
zet dy = 1.

Na de j loop
rond kleuren af op integer in destR, destG, destB
Zet kleuren in dword en schrijf naar doel bitmap [x,y]

Snel pixels lezen en schrijven

De snelheidswinst komt grotendeels door snellere pixel access en
door de trage properties TBitmap.pixels[ , ] en TBitmap.scanline[ ] te vermijden.
Voor de adressering van pixels gebruiken we pointers, die als 32 bit integers worden bewaard.
Dat laatste maakt berekeningen eenvoudiger. 
type PDW = ^dword
....
var ps0,pd0,psStep,pdStep : dword;
....
ps0 := dword(bm1.scanline[0]);
psStep := ps0 - dword(bm1.scanline[1]);
pd0 := dword(bm2.scanline[0]);
psStep := pd0 - dword(bm2.scanline[1]);
Alleen hier wordt even de scanline property gebruikt.
Om pixel [i,j] van de bron bitmap te lezen (naar variabele color):
var p,color : dword;
....
p := p0 - psStep*j + (i shl 2);
color := PDW(p)^;
Opmerking: i moet met vier worden vermenigvuldigd om een byte adres te maken.

Een bitmap staat in het geheugen met op het laagste adres pixel [0,width-1].
In het pf32bit formaat is de waarde psStep = 4*(bm1.width) en pdStep = 4*(bm2.width).

De pointer berekeningen worden zodanig in de loops geplaatst dat het aantal berekeningen minimaal is.
Voor details verwijs ik naar de sorce code.

Het hele project

Hieronder een verkleinde afbeelding van het project in werking
Er is één form (form1) en drie units:
form1 :
paintboxes (600*600) om de bitmaps te tonen.
buttons om een *.bmp image te laden en om te vergroten.
Edits voor nieuwe breedte en hoogte instelling.

unit1:
Handelt keyboard en mouse events af.
paintbox tekenen, clock initialisatie.
Bitmap creation en destruction.

Resize unit:
Globale bitmaps bm1,bm2 source en destination bitmaps.
procedure BMresize.

TimerUnit:
Een nanoseconds clock om nauwkeurig tijden te meten.