Punktoperation

Einführung

Digitale Bilder werden aufgrund ihres Wertebereiches der einzelnen Pixel in Farb-, Grauwert oder Binärbilder unterteilt. Beim Binärbild kann, wie der Name schon sagt, ein Pixel nur zwei Zustände einnehmen: 0 oder 1. Wobei noch undefiniert ist, welchem Farb- oder Grauwert diese Werte entsprechen. Im Allgemeinen macht es Sinn, schon für das Verständnis der Punktoperationen, 0 als schwarz und 1 als weiß anzunehmen.
In der digitalen Bildverarbeitung werden Bilder einer Manipulation mehr oder weniger vieler Pixel unterzogen. Zu den elementarsten Funktionen zur Pixelmanipulationen zählen die Punktoperationen. Auf ihnen bauen so ziemlich alle noch so komplexe Operationen auf.
Punktoperationen wirken immer nur auf ein einzelnes Pixel. Umliegende Bildelemente werden nie in Abhängigkeit verändert auch wenn sie Bestandteil einer Operation sein können. Mit anderen Worten gesagt, es wird immer nur ein Pixel bearbeitet und an seinen ursprünglichen Platz geschrieben.
Ganz unten stehen die bitweisen Operationen wie UND, ODER, NEGATATION, ... Diese verknüpfen bzw. negieren die einzelnen Bits der Pixels zweier Bilder oder mit einem Referenzmuster.
Natürlich gibt es auch die logischen Verknüpfungen, die nicht den Grauwert sondern das „Vorhandensein“ von Objekten (Pixel, die nicht die Hintergrundfarbe 0 haben) auswerten.
In den folgenden Kapiteln wird speziell auf die Punktoperationen Shrink und Blow eingegangen, die Bestandteil der Ausarbeitung sind. Sie basieren auf den elementaren Funktionen

Nachbarschaft

Ein digitales Bild besteht aus einer zweidimensionalen Matrix. Das kleinste gespeicherte Element ist hier das Pixel, welches stellvertretend für einen Grauwert steht. Da ein Pixel über das ganze Bild hinweg die gleiche Größe besitzt, lässt sich die Position eines Bildelementes über die Koordinaten x und y genau bestimmen.
Sei s hier ein Bildelement mit den Koordinaten (x,y), dargestellt in der rechten Abbildung. Nun besitzt das Pixel nicht nur eine Grauwerteigenschaft, sondern auch eine Nachbarschaft. Hier spielen nur die direkt umliegenden Elemente eine Rolle.

Unter normalen Umständen kann ein Pixel maximal acht Nachbarelemente haben. Ausnahmen bilden nur die Randpixel eines Bildes. Hier kann es nicht auf allen Seiten einen Nachbarn geben
Man unterscheidet noch die Größe der Nachbarschaft. Häufig vorkommende Beziehungen sind die 4er und die 8er Nachbarschaft. Im ersten Fall fasst man alle Pixel als benachbart auf, die mit dem zentralen Punkt eine Kante gemeinsam haben. Zählt man noch die hinzu, die mit dem Zentrum eine gemeinsame Ecke haben, spricht man von der 8er Nachbarschaft.

Generell ist es möglich, auch andere Beziehungen zu definieren, man spricht dann aber eher von Strukturelementen, da sie auch nicht notwendigerweise eine Symmetrie aufweisen müssen. Wobei hier Vorsicht geboten ist, da ein Strukturelement auch mehr als die acht Pixel um den Ursprungspunkt beinhalten kann. Dies sei aber nur am Rande erwähnt, da in unserem Fall nur die 4er und 8er Nachbarschaft von Belang sind.

Shrink & Blow

Bei den Punktoperationen Shrink und Blow spielt die oben erwähnte Nachbarschaft eine entscheidende Rolle. Sie manipulieren das aktuelle Pixel abhängig von seinen umliegenden Bildpunkten. Mathematisch lassen sich Shrink und Blow mit der booleschen Algebra beschreiben.

SHRINK (S(x,y)) = S(x,y) AND S(x+1,y) AND S(x,y+1) AND S(x-1, y) AND S(x, y-1)
BLOW (S(x,y)) = S(x,y) OR S(x+1,y) OR S(x,y+1) OR S(x-1, y) OR S(x, y-1)

S(x,y) steht für den aktuellen Grauwert an der Bildposition (x,y). Der neue Punkt ergibt sich aus den logischen Verknüpfungen seines eigenen Grauwertes und die der Nachbarn. Je nach Funktion handelt es sich um eine UND (Ç) oder eine ODER (È) Operation.
In obiger Formel wird nur die 4er Nachbarschaft mit einbezogen. Im eigentlichen Quellcode weiter unten gibt es auch eine Umsetzung mit der 8er Nachbarschaft, die im wesentlichen nur aus vier weitere Termen besteht.
Da es schwer fällt, sich anhand der booleschen Gleichung das neu entstehende Bild vorzustellen, noch eine andere Form der Beschreibung.
In einem binären Bild sind nur zwei Farben vorhanden, im einfachsten Fall schwarz und weiß. Nun nimmt man an, dass weiß der Hintergrund und schwarz entsprechend das Objekt sei. Wendet man nun die Blow-Funktion auf ein solches Bild an, wird an jeder Stelle ein schwarzes Pixel gesetzt, wenn mindestens ein Nachbar oder der Ursprung zum Objekt (schwarz) gehören. Umgekehrt bei Shrink, hier wird nur dann ein Bildelement schwarz eingefärbt, wenn alle Nachbarn und der Ursprung zum Objekt gehören. Je nach Operation wird das Objekt vergrößert (Blow) oder verkleinert (Shrink).
Nun stellt sich auch die Frage, nach dem Sinn der beiden Punktoperationen. Es lassen sich zwar ein paar interessante Operationen mit ihnen durchführen, doch sind sie als unterste Stufe der Operationen an Bilddaten für höhere sehr interessant. Z.B. die Morphologischen Operationen Dilatation und Erosion basieren auf den Punktoperationen. Sie führen ähnliche Funktionen aus, nur dass nicht die direkte Nachbarschaft, sondern eine Maske auf bzw. um das Ursprungspixel verwendet wird.
Verknüpft man das ein „Blow“-Bild mit seinem Ursprung XOR, ergibt sich z.B. der Umfang eines Objektes. Führt man das gleiche mit Shrink durch, erhält man den Rand eines Objektes.

Programmierung

Gefordert ist die Umsetzung und die Einbindung der oben erwähnten Punktoperationen Shrink und Blow in das Bildverarbeitungsprogramm AdOculos.
Bei dem Programm AdOculos handelt es sich um eine Software, die die Grundzüge der digitalen Bildverarbeitung auf verständliche Weise veranschaulicht. Sämtliche auf Bilder anwendbare Funktionen sind in Form von dynamischen Windows Bibliotheken (DLL) vorhanden. Der Vorteil in diesem Konzept liegt an der einfachen Erweiterbarkeit durch das Einbinden neuer Bibliotheken.
AdOculos ist vergleichbar mit einer Schnittstelle, die das Einlesen und Ausgeben von Bildern in einer Windowsoberfläche ermöglicht. Zu den Funktionen gibt es ein definiertes Interface, dass Quell-, Zielbilder und eventuell notwendige Parameter an die eigens erstellte Funktion übergibt.
Die Funktonen Shrink und Blow werden in Form einer DLL unter Visual C++ 6.0 erstellt und durch Einträge in eine Konfigurationsdatei dem Programm zugänglich gemacht.
Teil der Aufgabe ist es nicht nur die zwei Punktoperationen umzusetzen, sondern auch jeweils zwei verschiedene Variationen. Die neu berechneten Pixel sollen zum einen auf der 4er, als auch auf der 8er Nachbarschaft basieren.

Quellcode

Die Umsetzung der Operationen ist unterteilt in vier verschiedene Funktionen: shrink4, shrink8, blow4 und blow8. Auf die Abbildung der gesamten Funktion wurde verzichtet, schließlich wird hier nur die Initialisierung von Variablen und die Überprüfung der Ein- und Ausgabebilder vorgenommen. Somit ist die Darstellung nur auf das Wesentliche beschränkt. In allen vier Funktionen handelt es sich um eine zweifach geschachtelte FOR-Schleife.
Leider erweist sich der Zugriff auf die Bilddaten als nicht ganz so einfach, da es nur einen Pointer auf das erste Pixel gibt. Die Operationen erfordern aber einen Zugriff über die Koordinaten (x,y). Dazu ist eine kleine Umrechnung notwendig.
Für jeden möglichen Nachbarn und das Orginalpixel gibt es eine Variable neighbours. Bekannt ist die Breite des Bildes und über die Koordinaten, die durch die Schleife mit (c,r) nachgebildet werden, lässt sich ein Offset berechnen, der die Position ab dem ersten Pixel liefert. Da dies für mehrere Nachbarn notwendig ist, wird das Offset für jeden Nachbarn getrennt berechnet. Addiert man das Offset auf den Pointer, steht man an der Stelle im Speicher, die den benötigten Bildpunkt hält.

shrink4

Shrink4 ist die Shrinkoperation basierend auf der 4er Nachbarschaft. Als einfachste und übersichtlichste Funktion soll sie auch am Ausführlichsten behandelt werden. Zu den restlichen drei Operationen werden nur noch ein paar ergänzende Informationen aufgeführt.
In den Zeilen 2 und 3 befindet sich die elementare geschachtelte FOR-Schleife, die das Bild zeilenweise (r) Spalte für Spalte (c) abtastet. Liegt die aktuelle Position direkt am Rand, ist vereinbart, dass das dortige Pixel den Wert 0xFF (weiß) erhält. Der Vergleich hierzu siehe Zeile 5. Nun stellt sich aber die Frage, warum das zu berechnende Pixel auf 0xFF gesetzt wird, wenn nur einer der Nachbarn außerhalb des Bildes liegt. Die Antwort liegt auf der Hand. Außen liegende Pixel sollen laut Definition wie Hintergrund behandelt werden. Da nun später eine logische UND-Verknüpfung erfolgt und ja mindestens ein Hintergrundpixel gefunden wurde, würde das UND auf jeden Fall ein Hintergrundpixel (Farbe weiß) als Ergebnis besitzen. Nun kann man sich die weiteren Schritte sparen und dem Ursprungspixel gleich weiß zuordnen.
Ist dies nicht der Fall, wird in Zeile 7 fortgefahren. Als erstes wird für den Ursprung (Zeile 9) und die Nachbarn (Zeile 10-13) das Offset berechnet, mit dem der Bildpunkt (c,r) im Speicher gefunden werden kann. Es werden hier die Nachbarn mit der gemeinsamen Kante verwendet.

*lpImgOut++ ist der Zeiger auf das Bildelement im Ausgangsbild. Nach der Zuweisung wird der Pointer automatisch durch den Operator ++ inkrementiert. Beim folgenden Schleifendurchlauf zeigt der Pointer auf die nächste Adresse im Speicher, an die das kommende Pixel geschrieben werden soll. Die Zeilen 15 bis 19 bilden die eigentliche Verknüpfung. Für jeden Bildpunkt wird aus lpImgIn0 und neighbours[x] die Speicheradresse der Punktes berechnet und mit dem logischen UND (&&) verknüpft.
Nun ergeben sich hier leider ein paar kleinere Probleme. Zum einen in der Festlegung, dass nun der Grauwert schwarz das Objekt darstellt, dieser aber dem Zahlenwert 0x00 zugeordnet ist. Nun hat die logische UND-Verknüpfung aber die Eigenschaft, nur dann TRUE (1) zu sein, wenn alle anderen auch TRUE sind. Fakt ist, dass Shrink nur dann ein Pixel zum Objekt machen darf, wenn alle Nachbarn und der Ursprung zum Objekt gehören. Wie schon erwähnt, müsste schwarz (Objekt) der 1 (TRUE) zugeordnet sein.
Dieses kleinere Problem wird gelöst, indem jeder Grauwert einer Negation unterworfen wird. Nun mag diese Konvertierung nicht ganz „sauber“ sein, schließlich kennt die Negation als Ein- und Ausgangswerte nur die 0 und 1. Stellen wir ein schwarz auf dem Monitor etc. dar, wird dafür der Wert 0x00 also 0 genommen. Anders sieht es bei weiß aus, der zugeordnete Wert entspricht 0xFF. Glücklicherweise ist die Negation derart umgesetzt, dass sie Werte ungleich 0 automatisch als 1 interpretiert und dann zu 0 macht.

Würde man die neu errechneten Bildpunkte nun betrachten, käme ein komplett schwarzes Bild heraus. Hier wieder eine kleine Hürde. Der neu entstandene Wert 1 muss noch konvertiert werden in 0xFF, schließlich befinden wir uns auf der darzustellenden Ebene. Nur so bekommt man dann ein SW-Bild. Konvertiert wird mit der kleinen vorstehenden Operation 0xFF - 0xFF * (BYTE). Das in den Datentyp BYTE konvertierten Pixel, welches ja nur den Zustand 0 oder 1 annehmen kann, wird mit 0xFF multipliziert und von 0xFF angezogen. Warum jetzt noch die Subtraktion. Ganz einfach, um die UND-Funktion sinnvoll anwenden zu können, würde einmal negiert und jetzt muss noch „rück“-invertiert werden.

shrink8

Vergleicht man den Quellcode von shrink4 mit shrink8 lassen sich genau drei Unterschiede feststellen.
Das Array int neighbours[9] umfasst nun neun Elemente, was ja auch nachvollziehbar ist, schließlich wird hier die 8er Nachbarschaft angewendet. Entsprechend ist die logische Verknüpfung der Nachbarpixel (Zeile 19-27) um vier Operationen größer. Es sind hier die Nachbarn mit den gemeinsamen Ecken zum Ursprung hinzugekommen.
Verständlicherweise muss bei Einbeziehung der zusätzlichen Nachbarn auch der Grauwert berechnet werden. Zeile 11, 13, 15 und 17 ermitteln die zusätzlich notwendigen Offsets der Pixelposition im Bild.

blow4

Die Punktoperationen Blow und Shrink unterscheiden sich im Wesentlichen nur in der logischen Operationen. Wurde bei den Shrinkoperationen das UND verwendet, ist bei Blow, wie auch schon in Kapitel 1.3 erläutert, eine ODER-Verknüpfung der Nachbarn notwendig.

Sieht man sich den Quellcode etwas genau an, erkennt man auch schnell die Ähnlichkeit zu shrink4 . Es wird wieder nur die 4er Nachbarschaft berücksichtigt, demzufolge nach umfasst das Array neighbours auch nur 5 Elemente (Zeile 1). In den folgenden zwei Zeilen (3 und 4) ist die übliche verschachtelte for-Schleife zu sehen. Sie tastet das Bild wieder zeilenweise Punkt für Punkt ab. Überspringt man jetzt die nächsten Zeilen bis Zeile 27, zeigt sich die gewohnte Struktur der logischen Verknüpfung. Bis auf den kleinen Unterschied, dass hier mit ODER verknüpft wird.
Schwierigkeiten bereiten die Nachbarn bzw. die Ermittlung des Grauwertes. Prinzipiell geschieht dies wie bei shrink4 und shrink8. Problematisch sind bei Blow die Randbereiche. Da hier Objektpixel hinzugefügt werden, das Objekt sich damit auch vergrößert, kann im Randbereich nicht standardmäßig ein Pixel gesetzt (schwarz) oder gelöscht (weiß) werden. Um das Bild nicht zu verfälschen, wird für jeden Nachbarn eine Fallunterscheidung durchgeführt (siehe Zeile 7 bis 38). Liegt ein Nachbar außerhalb des Bildes, z.B. der rechte (Zeile 7) wird die folgende Zeile ausgeführt und der Variablen neighbours[1] der Grauwert des zuvor berechneten Ursprungpixels zugewiesen. Nun könnte man annehmen, dass eine Abfrage auf Randbereiche und eine pauschale Zuweisung des Grauwertes des zentralen Pixels ausreichend wäre. Da ergibt sich aber das Problem, dass ein gegenüber, nicht am Rand liegender Pixel einen vom Ursprung unterschiedlichen Grauwert besitzen und somit das Ergebnis der Operation entscheidend beeinflussen könnte.

Diese eben erwähnte Beeinflussung kann nur bei ODER-Verknüpfungen auftreten, da nur bei dieser Operation mehr als ein positiver Ausgang möglich ist. Und bei einer Überprüfung, die nur die Randposition erfasst, können maximal zwei Eingangsvariablen erfasst werden (z.B. Pixel in Position 0,0). Bei der 4er Nachbarschaft, müssen zur korrekten Auswertung aber alle fünf Variablen erfasst werden.

blow8

Wie zu erwarten, gleichen sich die Funktionen blow4 und blow8 sehr stark. Der einzige Unterschied liegt natürlich in der gestiegenen Anzahl der Nachbarn, die hier acht beträgt. Dies hat zur Folge, dass das Array neighbours nun neun Elemente groß ist. Vier weitere Offset-Berechnungen (Zeile 11-14, 19-22, 27-30 und 35-38) sind notwendig und der Vergleich (Zeile 40-48) ist ebenfalls um vier weitere Elemente größer.

Optimierung

Algorithmen werden programmiert, um in der Regel mathematische Berechnungen möglichst effizient zu lösen. Gerade in der Bildverarbeitung spielt die Effizienz eine entscheidende Rolle. Nun hat die Vergangenheit und auch die Erfahrung gezeigt, dass ein Algorithmus, sei er noch so simpel, fast immer verbesserungsfähig und optimierbar ist.
So verhalten sich auch die diese Umsetzungen von Blow und Shrink. Da die Umsetzung der Operation der Effizienz vorrangig ist, wurde eine ganz offensichtliche Optimierung weggelassen. Sie hat auch den Nachteil, dass sie auf den ersten Blick für Verwirrung sorgt.
Schaut man sich die logische Verknüpfung in Shrink und Blow ein wenig genauer an, erkennt man, dass eine Optimierung nach De Morgan möglich wäre. Im folgenden wird die Shrink-Operation mit 4er Nachbarschaft entsprechend umgeformt.
Um die Umformung nach De Morgan zu verdeutlichen, wird jedes Pixel, also Ursprung und Nachbarn durch eine Variable ersetzt und dann wieder rücktransformiert.

Die obere Abbildung macht deutlich, dass die Operation von logisch UND nach ODER wechselt und statt vier Negationen nur noch eine benötigt wird. Hier hätte man schon ganze drei und bei der 8er Nachbarschaft sogar sieben Operationen durch geschickte Anpassung wegoptimieren können.
Die Anpassung für Blow verhält sich natürlich analog und wird deshalb nicht extra aufgezeichnet, hier tauscht die Operation von logisch ODER nach logisch UND.
Ganz bewusst wurde auf diese Optimierung im Quellcode verzichtet, um den eigentlichen Charakter der Operationen, also die UND- bzw. ODER-Verknüpfung nicht zu verdrehen.

Ergebnis

Um nun die Korrektheit des Verfahrens zu überprüfen, bedarf es im einfachsten Fall nur eines Vergleiches der Ergebnisbilder eines bereits implementierten Verfahrens. Der erste Gedanke war hierbei die Binär-Dilatation bzw. Erosion aus AdOculos mit einem speziell angepassten Strukturelement. Doch unterscheidet sich die Interpretation der Nachbarn eines Randpixels in der Literatur.
Mit den folgenden drei Bildern wird nun die Funktion der Shrink4-Operation überprüft:

Wie zu erkennen ist, stellt die XNOR-Verknüpfung (letzes Bild)aus dem Original und dem Shrink den Rand des ursprünglichen Randes dar. Somit arbeitet dieser Algorithmus einwandfrei. Das passende Ad-Oculos-Set inklusive unten aufgeführten Bildern sind weiter unten als Download verfügbar.

Zur Verifizierung der Blow4-Operation ist ebenfalls ein Set vorhanden. Hier zeigt die XNOR-Verknüpfung (letzes Bild), die Umrandung der Objekte. Auch hier erfüllt die Umsetzung des Algorithmus seinen Zweck.

Download

AdOculos-Sets

AdOculos