Rasterformate und -Konverter

Die nachfolgende Abhandlung beschreibt das Labyrinth-Format, das zum Aufbau des Labyrinthes benutzt wurde, und einige wichtige Rasterbildformate, in die es umgewandelt werden kann. Aus didaktischen Gründen beschreiben alle nachstehenden Daten ein sehr einfach gehaltenes Minilabyrinth der Form, wie es unter dem Abschnitt Labyrinth-Format dargestellt ist.

1. Labyrinth-Format
2. Portable-Bitmap-Format (PBM)
3. X11-Bitmap-Format (XBM)
4. Windows- und OS/2-Bitmap-Format (BMP)
5. Formatkonverter
6. Literatur

Labyrinth-Format

Formataufbau

Das Labyrinth-Format besteht aus einer einfachen Textdatei, deren Zeilen gleichlang sein müssen (Kommentare ausgenommen). Jedes Leerzeichen bedeutet einen begehbaren Gang, jedes andere Zeichen eine Wand. Kommentare werden durch ein Semikolon eingeleitet:

; Minilab
###############
#   #         #
# # # # ## ## #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# #   #       #
  ######## ####
# #   #       #
# # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # #     #
# # # # #######
#   #         #
###############

Basisalgorithmus

Hinweis: Die nachfolgenden Algorithmen sind aus didaktischen Gründen sehr einfach gehalten und verstehen daher die im Format möglichen Kommentare nicht. Der Konverter hingegen versteht sie und baut sie nach Möglichkeit in die Grafik­formate ein. Außerdem müssen vor der eigentlichen Ausgabe die Maße des Labs eingelesen werden wie in folgender Routine:

/* File pass 1: get width and height */
x = width = height = 0;
while ((c=getchar()) != EOF)
  switch (c) {
    case '\n': if (x > width) width = x; x = 0; height++; break;
    default  : x++;
    }
rewind(stdin);

Portable-Bitmap-Format (PBM)

Das PBM-Format ist ein von Sun Microsystems entwickeltes monochromes Rasterbildformat unter UNIX. Ursprünglich zum Bildaustausch zwischen Mailsystemen gedacht, wird es heute auch von vielen DOS/WIN-Grafik­programmen verstanden (Irfan View, XNView, Paint Shop Pro etc.). Es gehört zu einer UNIX-Familie von Rasterformaten, der neben PBM auch das Graustufenformat PGM und das Farbformat PPM angehören. Neben dem hier besprochenen ASCII-Bildformat gibt es auch noch eine Binärvariante von PBM.

Formataufbau

Das Format beginnt mit der Magic Number zur Identifi­kation des Dateityps. Die Identifi­kation für PBM im ASCII-Format ist P1. Dann folgen Breite und Höhe des Bildes als dezimale ASCII-Zeichen. Anschließend finden sich die Datenwerte von links oben nach rechts unten. Da es keine Palette gibt, hängt es vom Anzeigeprogramm ab, wie das Bild dargestellt wird. Meist wird der Wert 1 für Schwarz und 0 für Weiß verwendet. Leerzeichen werden ignoriert. Kommentare werden durch # eingeleitet. Jede Zeile darf nur 70 Zeichen lang sein.

P1
# Minilab
16 16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1
0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1
0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0
0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

Basisalgorithmus

/* File pass 2: read lab and print pbm */
printf("P1\n# Created by labconv\n%d %d\n", width, height);
while ((c=getchar()) != EOF) {
  switch (c) {
    case '\n': putchar('\n'); x = 0; break;
    case ' ' : printf("0 "); x++; break;
    default  : printf("1 "); x++;
    }
  if (x == 70/2) {
    putchar('\n'); x = 0; }
  }

X11-Bitmap-Format (XBM)

Das XBM-Format ist ein vom X-Konsortium entwickeltes monochromes Raster­format für UNIX in ASCII-Form, welches die Benutzer­ober­fläche X11 hauptsächlich für kleine Symbol­bilder (engl. Icons) und Kursor­bilder (engl. Cursor) verwendet. Der Format­aufbau entspricht einer Daten­definition in der Programmier­sprache C, so daß eine XBM-Datei direkt in einen C-Quelltext eingebettet werden kann.

Aufgrund seines einfachen Aufbaus ist XBM als eines der wenigen Bild­formate lizenz­frei, so daß die ersten Browser seine Darstellung ermög­lichten. Auch heute noch unterstützen viele HTTP-Klienten XBM (MIME-Typ image/xbm oder image/x-xbitmap), so z.B. Netscape, Opera, Safari, die Mozilla-Browser und der IE (bis V.6; ab V.7, genauer ab Windows XP SP2, entfällt die Unter­stützung).

Die simple Struktur von XBM ermöglichte es zudem, einfache Grafiken benutzer­gesteuert und dynamisch per JavaScript im Browser zu erzeugen. Als Bsp. sei das Online-Spiel Wolfenstein 5k genannt, eine monochrome Mini­variante des originalen Wolfenstein-Spiels von ID Software (Doom, Quake), in dem man sich ebf. durch labyrinth­artige Strukturen (genauer: einen Irrgarten) kämpfen muß; der dem Spiel zugrunde­liegende JavaScript-Code ist kleiner als 5 Kb (!) und gewann 2002 den Wettbewerb „the5K“ (lauffähig unter IE5 und IE6).

Anmerkung Stand 2010: Aktuelle Browser unterstützen die von Wolfenstein 5k verwendete Techno­logie nicht mehr (Wegfall von <img src=javascript:..> und images[n].src=javascript:.., Entfall der XBM-Unter­stützung des IE etc.). Somit dürften die meisten Benutzer Wolfenstein 5k nicht mehr spielen können. Eine browser­basierte Bild­erstellung mit JavaScript funktioniert jedoch noch mit Dritt­biblio­theken (z.B. Walter Zorns Bibliothek, die Bilder durch absolut positio­nierte <div>s emuliert) oder seit kurzem auch mit eingebetteten URLs, dem sog. Data URL Scheme gemäß RFC2397 (Bilder, die direkt in ihren URLs die Bilddaten tragen). Sinnvoller ist aber die Verwendung des HTML5-Elementes <canvas>, für dessen Nutzung JavaScript um einen Grafik-Befehls­satz erweitert wurde. Alternativ ist der Einsatz von SVG oder Java möglich. Als letzte Möglich­keit zur lokalen dynamischen Bild­generierung sei noch die proprietäre und lizenzbehaftete Flash-Technologie erwähnt.

Ein Spiel, in dem man ebf. durch einen Irrgarten läuft, findet sich als Prototyp auf der HTML5-Testseite. Es nutzt bereits das HTML5-Element <canvas> hierzu.

Nachfolgend findet sich das bereits o.g. Mini­labyrinth im XBM-Format (zur besseren Darstellung vergrößert und mit farbigem Hintergrund hinterlegt, da XBM-Bildpunkte meist schwarz dargestellt werden):

Bild im XBM-Format:	Bild im GIF-Format:

Wer das linke Bild sehen kann, dessen Browser kann XBM darstellen.

Formataufbau

Die Pixelwerte werden C-gemäß als char-Feld (Byte) notiert, Breite und Höhe als #define's. Da keine Palette existiert, kodiert der Bitwert 1 Schwarz und der Wert 0 Weiß oder (im Browser) Transparenz. Geschrieben werden die Bildpixel vom LSB in Richtung MSB; der erste Bildpixel findet sich also im LSB (s.a. Basisalgorithmus)! Die Bytes hingegen werden, durch Kommata getrennt, gemäß der Reihenfolge in der Bildzeile in die Datei geschrieben. Überflüssige Bits werden ignoriert.

/* Minilab */
#define x_width 16
#define x_height 16
static char x_bits[] = {
0x00,0x80,0xee,0xbf,0xaa,0xa4,0xaa,0xaa,
0xaa,0xaa,0xaa,0xaa,0xba,0xbf,0x03,0x84,
0xba,0xbf,0xaa,0xaa,0xaa,0xaa,0xaa,0xaa,
0xaa,0xbe,0xaa,0xa0,0xee,0xbf,0x00,0x80
};

Basisalgorithmus

/* File pass 2: read lab and print xbm */
printf("#define img_width %d\n#define img_height %d\nstatic char img_bits[] =
  {\n", width, height);
i = c2 = 0;
while ((c=getchar()) != EOF) {
  if (i==8 || c=='\n') {  /* Put out char if octet or line is full */
    printf("0x%02x,",c2); i = c2 = 0; }
  switch (c) {
    case '\n': printf("\n"); break;
    case ' ' : i++; break;
    default  : c2 += 1<<i++;
    }
  }
printf("};\n");

Windows- und OS/2-Bitmap-Format (BMP)

Das BMP-Format ist das Hausformat von Microsoft für Rasterbilder. Daneben gibt es noch eine leichte Variation des Formates für OS/2. Das Format ist unabhängig vom verwendeten Ausgabegerät definiert und wird mittlerweile auch von Programmen anderer Betriebsysteme unterstützt. BMP liegt das RGB-Farbmodell zugrunde. Durch einen geeigneten Aufbau von Farbtabellen ist auch die Kodierung von monochromen und Graustufenbildern möglich. In BMP kann intern eine Kompression vereinbart sein (RLE), dies wird aber meines Wissens nach unter Windows für BMP selbst nicht genutzt, wohl aber für RLE-Bilder (z.B. Windows-Startlogo), welche nichts anderes als komprimierte BMPs darstellen.

Formataufbau

Das BMP-Format definiert zwei Header, eine Palette und einen Datenbereich: Der BITMAP_FILE-Header enthält Angaben zur Datei, der BITMAP_INFO-Header Angaben zu den Bilddaten (Größe, Farbtiefe, Farbtabelle und Kompressionsart etc.), die RGB_QUAD-Palette die benötigten Farben. Der Datenbereich enthält schließlich die Pixelwerte jedes Punktes einer Linie. Linien werden bündig auf einen durch 32 teilbaren Wert verlängert und mit Null-Werten aufgefüllt. Als Werte für die Farbtiefe sind 1, 4, 8 und 24 zugelassen. Zur Kompression kann der Lauf­längen­kodierungs-Algorithmus für Bilder mit einer Farbtiefe von 4 oder 8 bit/Pixel verwendet werden, wobei jeweils 2 Byte als Informationseinheit aufgefaßt werden. Enthält der erste Bytewert eine Null und ist der zweite Wert größer als drei, so enthält der zweite die Anzahl der folgenden Bytes, die die Farbe des nächsten Pixels als Verweis in die Farbtabelle enthalten (keine Kompression). Ansonsten spezifiziert der erste Bytewert die Anzahl der nächsten Pixel, die mit der Farbe des zweite Bytewertes als Verweis in die Farb­tabelle gesetzt werden sollen. Ist das Bild mit 4 bit/Pixel kodiert, so werden nur 4 bit für diese Information verwendet. So können jeweils zwei Werte in einem Bytewert kodiert werden. BMP definiert im Header weiterhin die Möglichkeit, eine Farb­tabelle anzugeben, deren Farben zur Anzeige des Bildes benutzt werden müssen.

Im nachfolgenden Dump ist der Datenbereich farblich hervorgehoben:

   0  1  2  3  4  5  6  7   8  9  a  b  c  d  e  f
  ------------------------------------------------
0 42 4d 7e 00 00 00 00 00  00 00 3e 00 00 00 28 00 BM~.......>...(.
1 00 00 10 00 00 00 10 00  00 00 01 00 01 00 00 00 ................
2 00 00 40 00 00 00 00 00  00 00 00 00 00 00 02 00 ..@.............
3 00 00 00 00 00 00 00 00  00 00 ff 80 80 00 ff fe ................
4 00 00 88 02 00 00 aa fa  00 00 aa 82 00 00 aa aa ................
5 00 00 aa aa 00 00 aa aa  00 00 a2 02 00 00 3f de ..............?.
6 00 00 a2 02 00 00 aa aa  00 00 aa aa 00 00 aa aa ................
7 00 00 aa da 00 00 88 02  00 00 ff fe 00 00       ..............

Die folgenden Daten­strukturen werden benötigt. Nicht das Packen der Records vergessen, sonst entsteht ein fehler­haftes Bitmap!

#define INCH 2.54057

/* BITMAP_FILE Header */
typedef struct {
  unsigned char bfType[2];  /* Always 'BM' */
  unsigned long bfSize;  /* File size */
  short res1, res2;  /* Reserved */
  unsigned long bfOffs;  /* Offset of data */
  } tbfHd;

/* BITMAP_INFO Header */
typedef struct {
  unsigned long biSize;  /* biHeader size, 40 */
  unsigned long biWidth;  /* Img width */
  unsigned long biHeight;  /* Img height */
  unsigned short biPlanes;  /* Count of planes, must be 1 */
  unsigned short biBitCnt;  /* Bits per pixel, for Monochromes 1 */
  unsigned long biCompr;  /* Type of compression, mostly none = RGB = 0 */
  unsigned long biSizeIm;  /* Size of data block */
  unsigned long biXPelsM;  /* Recommended X resolution per meter */
  unsigned long biYPelsM;  /* Recommended Y resolution per meter */
  unsigned long biClrUsed;  /* Count of colors of palette used */
  unsigned long biClrImp;  /* Count of important colors; 0 = all important */
  } tbiHd;

/* RGB_QUAD Palette */
typedef struct { unsigned char blue, green, red, res; } tPalE;

tbfHd bfHd = { "BM", '?', 0, 0, sizeof(tbfHd)+sizeof(tbiHd)+2*sizeof(tPalE) };
tbiHd biHd = { 40, '?', '?', 1, 1, 0, '?', 72/INCH*100, 72/INCH*100, 2, 0 };
tPalE pal[2] = { {0xff,0xcc,0xcc,0x00}, {0x80,0x00,0x00,0x00} };

Basisalgorithmus

/* Compute and fill in BMP header fields */
int lnbits = 32 * ((width-1)/32 + 1);  /* BMP lines must be a multiple of 32b */
biHd.biSizeIm = lnbits/8 * height;
bfHd.bfSize = bfHd.bfOffs + biHd.biSizeIm;
biHd.biWidth = width;
biHd.biHeight = height;
/* File pass 2: read lab and print pbm */
fwrite(&bfHd, sizeof bfHd, 1, stdout);
fwrite(&biHd, sizeof biHd, 1, stdout);
fwrite(&pal, sizeof pal, 1, stdout);
c2 = 0;
for (y=0; y<height; y++)  /* Lines */
  for (x=0; x<lnbits; x++) {  /* Bit columns */
    if (x < width)  /* Set img bits; padding bits remain 0 */
      if ((c=get01()) != ' ')
        c2 += 128 >> x%8;
    if (x%8 == 7) {  /* A byte is complete now, write out */
      putchar(c2); c2 = 0; }
    }

Formatkonverter

Der Konverter arbeitet als Filter und somit mit Standardein- u. ausgabe, daher werden Umleitungsoperatoren benötigt.

BMP-Bilder werden vom Konverter gespiegelt ausgegeben: da das BMP-Format von links unten anfängt, ein Bild zu beschreiben, müßte man die Textdatei von hinten lesen oder dynamisch einen Puffer reservieren. Der Anschaulichkeit der hier vorgestellten Algo­rithmen halber wurde dies nicht implementiert (zudem man mit jedem Grafik­programm dies nachträglich leicht korrigieren kann).

Der Konverter wird über labconv -p|-x|-b < labfile > imgfile aufgerufen. Ohne Konvertierungs­angabe erscheint die folgende Hilfeausgabe:

labconv -p|-x|-b < labfile > imgfile

  -p converts to PBM
  -x converts to XBM
  -b converts to BMP, mirrored

Literatur

1. Born G.; Referenzhandbuch Dateiformate; Addison-Wesley; Bonn; 1992
2. UNIX Man Pages