Deforming bit maps using ML

To complete this diversion you will need:

A means of looking at BMP bitmap files

BMP is the standard used by MS Windows and others. If you are using Windows then PaintBrush will do. If you are using an X system then you may have access to xv which will process BMP files and will also write to other formats such as GIF used by WWW viewers. (Local users only: if xv does not work then your path is not set up properly, try the command /usr/local/X11R6/bin/xv at Craiglockhart or /apps/bin/xv from Merchiston)

Some bitmaps to deform. You can use xv to grab any image that shows up on your screen or you can use one of mine: for socialists, for nationalists or for Baywatch fans. Save one of these to your own file space - I refer to labour.bmp throughout. Note that even if your viewer does not show these files as pictures you can still save them.

We choose to represent a BMP file internally as a four tuple consisting of:

width, in pixels
height in pixels
The colour map (this maps 1,4 or 8 bit numbers onto 24 bit colour values.) It takes the form of a string, each entry in the colour table occupies 4 bytes even though only the first three are significant.
A function which gives the colour (index) at any pixel (x,y) where x runs from 0 to width-1 and y runs from 0 to height-1.

The copy readbmp and attendant functions into an ML window. Do the same with writebmp

Transforming BMPs

Given that we can read and write bitmaps we can now do any processing in between. For example consider the function transpose which swaps it's two input. We can generate a new bit map using the function swap:

fun swap(x,y)=(y,x);
fun transpose(w,h,c,f) = (h, w, c, f o swap);
writebmp (transpose(readbmp "labour.bmp")) "tmp.bmp";

Use xv to take a look at the input file "labour.bmp" and the output file "tmp.bmp".

Getting stuck in

To apply transformations to graphics files we will apply functions over the 2D plane. Initially this function maps from (0..w-1,0..h-1) where w and h are the width and height respectively. However it is more convenient to consider functions which deform a square centred on the origin - that is the square from (~1.0,~1.0) to (1.0,1.0). The following function applies the function f over the input bit map as if the input were mapped onto this square.

fun trans f (w,h,c,f') = let
	fun toSq (x,y)=(2.0*real x/real w - 1.0,2.0*real y/real h - 1.0)
	fun frmSq(x,y)=(floor((x+1.0)*real w/2.0),floor((y+1.0)*real h/2.0))
	in (w,h,c,f' o frmSq o f o toSq)end;
fun lookat f = writebmp (trans f (readbmp "labour.bmp")) "tmp.bmp";

We can lookat any function which takes two real numbers and returns two real numbers try the function bigger as defined here:

fun bigger(x,y)=(2.0*x,2.0*y);
lookat bigger;

Use xv to look at the file "tmp.bmp" now.

Here are some more functions to try. Copy them all into ML then try some.

fun relf(x,y)=(~x:real,y);
fun blow(x,y) = (x*0.5,y*0.5);
fun fish(x,y)=let val r=sqrt(x*x+y*y) in (r*x,r*y) end;
fun unfish p (x,y)=let val r=(sqrt(x*x+y*y)+p)/(1.0+p) in (x/r,y/r) end;
fun wasp(x,y)=(x/(y*y+1.0)*2.0,y);
fun fat p (x,y) = (x*(y*y+p)/p,y:real);
fun rot a (x,y) = let val c=cos a val s=sin a in (x*c-y*s,x*s+y*c) end;
fun whirl(x,y)=let val r=sqrt(x*x+y*y) in rot (1.0-r)(x,y) end;
fun wave(x,y)=(x+sin(3.0*y)/4.0,y);
fun shear(x,y)=(x+y/2.0,y);
fun polo(x,y)=(2.0*arctan(x/y)/3.1415,sqrt(x*x+y*y)-0.2);

lookat wasp;

lookat (rot 1.0);
You can of course make up your own functions either by definition or by composition of some of the above.

So why does "bigger" make the picture smaller?

The function bigger has the effect of doubling both x and y coordinates, for example if you give (0.5,0.5) to bigger it returns (1.0,1.0).

The point (0.5,0.5) is halfway from the centre to the top right corner, (1.0,1.0) is that top right corner. The colour of the point (0.5,0.5) on the transformed image is taken from the colour of the point (1.0,1.0) on the original.

Thus the image seen represents the inverse of the function applied. We can apply the function forwards - by mapping each point of the original onto a point on the new, but there might be gaps if the function is an enlargement at any point.
Anyone wishing to pursue this might consider using a ByteArray to write to. One might use a ByteArray to store a row of pixels and hold an Array of these to represent the pixel plane. These structures are "non-strict" - that is they do not have the property of referential transparency and should be avoided wherever possible.
Rather than encourage such unfunctionally correct programming I shall merely give a few pointers:

open the structures ByteArray and Array to find out how they work
for every pixel in the source, update the point corresponding to the transformed coordinates
to obtain 3D transformations maintain a colour array and a z-buffer, the z-buffer holds the distance of the nearest point plotted, only over-plot points which are nearer
to wrap a BMP onto a surface you will need a triple of parametric equations for the surface, for example:
- sphere: (x,y) -> (cos x cos y, sin x cos y, sin y)
- toroid: (x,y) -> (cos x(R+rcos y),sin x(R+rcos y),r sin y)
- cone: (x,y) -> (y cos x,y sin x, y)

A little bit about how it works

We use the functions open_in and input to read the file into several strings. The open_in function takes the file name as a string and returns a file handle. The input function takes a file handle and the number of bytes required and returns a string of the correct length.

open_in: string -> instream
input: instream * int -> string

The header of a BMP file contains 54 bytes.

val fh = open_in "test.bmp";
val header = input(fh,54);

The format of the BMP file is quite involved and you do need to know the details - skip this if you are not interested:
The header includes some numbers, some are stored as two byte values, with the most significant first, some are four byte values again with the MSB first. We use the functions get2 and get4 to convert two byte or four byte strings into integers:

fun get2 s = 256*ordof(s,0) + ordof(s,1)
fun get4 s = 256*(256*(256*ordof(s,0)+ordof(s,1))+ordof(s,2))+ordof(s,3);

Within the header there is the width and height at position 18 and 22 respectively, these are both 4 byte values:

fun width h = get4(substring(h,18,4));
fun height h = get4(substring(h,22,4));

There is also a colour table, the size of which is in position 10, and the bit map itself, the size of which is in position 34. There may be either 1, 4 or 8 bits per pixel (there may even be 24 bits but I have not allowed for this). The function bits extracts from byte b the sth group of n bits. As an added complication each row in the bitmap must start on a "double word" boundary - that is each row is padded to make it a multiple of 4 bytes in length.