Kapitel 4 - Implementation
In diesem Kapitel wird aufgezeigt wie die Konzepte und Algorithmen vom Kapitel 3 umgesetzt wurden. Hierzu wird das objektorientierte Design mit der Unified Modelling Language UML dargestellt und die Implementation mit C++ kurz umrissen, wobei auf C++ Code nicht eingegangen wird. Dieses Kapitel richtet sich also nur an Leser welche Interesse an der konkreten objektorientierten Umsetzung haben. Wer sich nicht für Objektorientierung oder die Implementation interessiert, kann getrost zum nächsten Kapitel springen, denn hier werden keine neuen Konzepte oder Algorithmen vorgestellt. Die Benutzung der implementierten Applikationen wird im Anhang B ausführlich beschrieben.
4.1 Überblick
Der Ablauf des Hauptprogramms mpeg2points durchläuft drei grundlegende Schritte:
In der ersten Phase werden die Kommandozeilenparameter eingelesen und analysiert. Die Bildsequenz, die Bounding-Box, die Maske und die Erkennungsroutine für die Stiftposition werden hierdurch bestimmt. In der zweiten Phase werden die einzelnen Bilder der Bildsequenz eingelesen, vorverarbeitet und die Differenzbilder erstellt. In diesen Differenzbildern wird nach den Stiftpositionen gesucht welche schliesslich in einer Liste gespeichert werden. In der dritten Phase werden diese Stiftpositionen von der Klasse Interpolator verbessert und von mpeg2points zusammen mit weiteren Informationen abgespeichert.
Die zentrale Verarbeitung in der zweiten Phase geschieht durch die Klasse SlidingWindow. Um die Bildsequenz einlesen zu können, nutzt SlidingWindow die Klasse ImageSource, welche die einfache und abstrahierte Nutzung der unzähligen PPM-Bilder in der Bildsequenz ermöglicht. Die eingelesenen Bilder sind von der Klasse Image abgeleitet und werden durch von FilterStrategy abgeleitete Filter vorverarbeitet. Mit einer von Detector abgeleiteten Klasse wird schliesslich die Stiftposition erfasst und von SlidingWindow an das Hauptprogramm mpeg2points zurückgegeben.
Zur Verarbeitung der definierten Bildsequenz wird SlidingWindow angewiesen, die aktuelle Position auf das erste Bild des Intervalls der Sequenz zu setzen. Der quadratische Fensterbereich, in dem nach neuen Stiftpositionen gesucht werden soll, überdeckt den Anfangsbereich im linken Teil der Bounding-Box. Solange nicht das Ende des Intervalls erreicht ist wird durch den Aufruf der Methode apply der Klasse SlidingWindow eine Stiftposition erfasst und an die resultierende Punkte-Liste angehängt. Wurde eine gültige Stiftposition erkannt, so wird das Zentrum des quadratischen Fensterbereichs an diese Position verschoben. Mittels der Methode moveNext der Klasse SlidingWindow wird das nächste Bild der Sequenz angesteuert um dort wiederum eine Stiftposition zu erkennen.
Bild 47: Grobe Klassenübersicht ohne abgeleitete Klassen
Bild 47 zeigt einen groben Überblick der Klassen. Bei abstrakten Basisklassen wurden die abgeleiteten Klassen ausgeblendet um die Übersichtlichkeit zu wahren. Diese abgeleiteten Klassen werden in den nachfolgenden Abschnitten vorgestellt. Die Klassen Point und Rectangle dienen in vielen anderen Klassen als nützliche Hilfsmittel zur Darstellung der geometrischen Objekte Punkt und Rechteck. Die Klassen vector<> und list<> stammen aus der STL (1) von C++ und dienen als universelle Behälter für beliebige Objekte. Die Klasse PPMReader wird von ImageSource benutzt um die einzelne Bilder der Bildsequenz, welche im PPM-Format vorliegen, einzulesen. mpeg2points nutzt in der dritten Phase der Verarbeitung die Klasse Drawing, um Bilder der Klasse Image mit Linienzügen zu versehen. Diese Bilder werden als Debuginformation von PPMWriter im PPM-Format abgespeichert. Filter dient in SlidingWindow der Erstellung der Differenzbilder. Die Klasse Histogramm wird verwendet, um den Threshold nach dem Algorithmus von Otsu zur Binärisierung des Differenzbilds festzulegen.
Bild 48: Die abstrakten Klassen Image und ImageSource
Die Klassen Image8 und Image24 von Bild 48 sind von der abstrakten Basisklasse Image abgeleitet und repräsentieren digitale Bilder. Image8 repräsentiert ein Graustufenbild, Image24 ein TrueColor-Bild. ImageSource bietet Schnittstellen, um abstrahiert auf Bildquellen zuzugreifen. Entsprechende Methoden dienen der Navigation über die Einzelbilder und liefern die Bilder als Instanz von Image8 oder Image24. Die Klasse ImageSourcePPM implementiert die Möglichkeit, eine numerierte Sequenz von PPM-Bildern zu verarbeiten. Es wäre auch denkbar, eine konkrete Implementation zur direkten Verarbeitung von MPEG-Dateien zu erstellen. Im Programm mpeg2points wären dann nur Änderungen in der konkreten Initialisierung von ImageSource notwendig.
Die abstrakte Basisklasse FilterStrategy definiert die Schnittstelle zum Verarbeiten resp. Filtern von digitalen Bildern. Jede abgeleitete Klasse von FilterStrategy in Bild 49 implementiert einen spezifischen Filter. Jeder dieser Filter nimmt ein Bild als Eingabe und liefert ein verändertes Bild zurück. Diese Filter werden hauptsächlich in der Klasse SlidingWindow zur Vorverarbeitung benutzt.
Bild 49: Die abstrakte Basisklasse FilterStrategy
Eine der abgeleiteten Klassen von Detector von Bild 50 wird in SlidingWindow zur Erkennung der Stiftposition benutzt. Jede dieser abgeleiteten Klassen implementiert eine spezielle Methode zur Festlegung des Zentrums einer Punktmenge.
Bild 50: Die abstrakte Basisklasse Detector
Im weiteren werden die Klassen von Bild 47 bis Bild 50 näherer vorgestellt. Hierzu werden die Attribute und Operationen jeder Klasse als UML-Diagramm dargestellt und deren Verwendung im Text erklärt. Spezialitäten bei der Implementation in C++ werden beschrieben. Weitere Informationen können dem C++ Quellcode entnommen werden.
4.2 Klasse Image
Die abstrakte Klasse Image dient als allgemeine Schnittstelle für den Zugriff auf digitale Bilder. Hierzu werden abstrakte Methoden für die Erstellung, Abfrage und Veränderung von Bildern zur Verfügung gestellt. Die konkreten Klassen Image8 und Image24 repräsentieren Grauwertbilder resp. TrueColor-Bilder und implementieren die abstrakten Methoden. Eine Übersicht über die drei Klassen Image, Image8 und Image24 befindet sich in Bild 51.
Bild 51: Klassen Image8 und Image24 mit abstrakter Basisklasse Image
Zur Erstellung einer Instanz eines digitalen Bildes stehen drei verschiedene Konstruktoren zur Verfügung. Ohne Angabe von Parametern wird ein minimales digitales Bild erstellt, welches aus einem schwarzen Pixel besteht. Werden dem Konstruktor die Breite und Höhe des digitalen Bildes übergeben, dann wird ein schwarzes Bild mit diesen Dimensionen erstellt. Die Angabe eines bestehenden Bilds veranlasst den Konstruktor eine unabhängige Kopie dessen zu erstellen.
Klassenintern wird das digitale Bild als Byte-Feld (myImage) repräsentiert. Beim Grauwertbild (Image8) wird pro Bildpunkt ein Byte-Wert zur Codierung der 256 Graustufen benötigt. Beim TrueColor-Bild (Image24) wird pro Bildpunkt je ein Byte-Wert für die drei Grundfarben (Rot, Grün, Blau) benötigt. Eine Kopie der internen Repräsentation (myImage) wird von den Methoden getImage, getImage24 und getImage8 geliefert. Der Empfänger der Kopie des internen Felds ist verantwortlich für die Verwaltung dieses Speicherbereichs. Die Methoden adoptImage8 und adpotImage24 löschen die interne Repräsentation des Bilds und ersetzen sie mit dem neuen Byte-Feld. Die get-Methoden sind nützlich zur effizienten Speicherung oder Darstellung des Bilds; es findet ein schneller Transfer des ganzen Byte-Felds in einem einzigen Methodenaufruf statt. Die adopt-Methoden eignen sich vortrefflich, um eine von der Festplatte eingelesene Bilddatei im Hauptspeicher abzulegen.
Die Methode copy liefert einen Zeiger auf eine unabhängige Kopie des digitalen Bilds. Der Empfänger ist verantwortlich für dieses Bild und muss es nach der Verwendung aus dem Speicher entfernen.
Die Methode getColor liefert den Farbwert des digitalen Bilds an bestimmten x- und y-Koordinaten. Bei einem Graustufenbild wird der Grauwert als Farbe mit drei gleichwertigen Farbkomponenten kodiert. Die Methode getGreyscale liefert den Grauwert des digitalen Bilds an bestimmten x- und y-Koordinaten. Bei einem TrueColor-Bild wird das arithmetische Mittel der drei Farbkomponenten geliefert. Die Methoden setColor und setGreyscale setzten Farb- bzw. Grauwerte an der entsprechenden Stelle im Bild. Hierbei wird wenn nötig eine Konversion zwischen Grauwerten und Farben vorgenommen. Liegen die Koordinaten dieser Methoden ausserhalb des Bildbereichs, wird automatisch auf den nächstliegenden Punkt am Rande des Bilds zugegriffen. Die Methode setWhite setzt alle Werte im internen Byte-Feld auf 255, was Weiss entspricht. setBlack setzt all diese Werte auf 0, also Schwarz.
4.3 Klassen PPMReader und PPMWriter
Diese Klassen von Bild 52 dienen dem Einlesen und Speichern von PPM-Bildern. PPMReader liest eine PPM-Bilddatei von der Festplatte ein und erstellt in Abhängigkeit des PPM-Bildformats eine entsprechenden Instanz der Klasse Image8 oder Image24. PPMWriter speichert eine Instanz von Image8 oder Image24 auf der Festplatte als PPM-Bild ab.
Bild 52: Klassen PPMWriter und PPMReader
Zum Einlesen eines PPM-Bilds in ein digitales Bild wird die Methode apply einer Instanz der Klasse PPMReader aufgerufen. Als Parameter muss der Dateiname und –pfad zur PPM-Bilddatei angegeben werden. Als Rückgabewert wird ein Zeiger auf ein digitales Bild geliefert. Je nach PPM-Datei verweist dieser Zeiger auf eine Instanz von Image8 (Graustufenbild) oder auf eine Instanz von Image24 (TrueColor-Bild).
Zum Speichern eines digitalen Bilds in eine PPM-Bilddatei muss der Dateiname gesetzt werden. Dies kann einerseits beim Konstruktoraufruf oder andererseits mit der Methode setFilename erledigt werden. Klassenintern wird dieser Dateiname im privaten Attribut filename abgelegt. Die Methode apply speichert das übergebene Bild in der vorher spezifizierten Datei.
4.4 Klasse Drawing
Die Klasse Drawing von Bild 53 ermöglicht einfache Zeichenfunktionen in digitalen Bildern. Bei allen Zeichenfunktionen wird ein Zeiger auf eine Instanz der Klassen Image8 bzw. Image24 übergeben. In dieses Bild werden die grafischen Elemente mit der angegebenen Farbe eingezeichnet.
Die Methode line zeichnet basierend auf den Endpunkten eine Linie in das Bild. Zum Zeichnen der Linie wird der Algorithmus von Bresenham (vgl. [Fel92, Seiten 84-91] und [FvD96, Seiten 74-78]) verwendet. Mittels der Methode rectangle wird in das digitale Bild ein achsenparalleles Rechteck eingezeichnet. Dieses Rechteck wird durch die linke untere und die rechte obere Ecke definiert. Die Methoden point und cross markieren einen einzelnen Punkt. point färbt nur den einzelnen Punkt mit der Farbe ein. Bei der Methode cross wird dieser Punkt durch ein Kreuz markiert.
Bild 53: Klasse Drawing
Die Klasse ImageSource aus Bild 54 bietet eine Schnittstelle zur Navigation über Bildsequenzen an. Diese Sequenzen können z.B. ein MPEG-Video oder eine aufsteigend numerierte Sequenz von PPM-Bildern wie in der Klasse ImageSourcePPM sein. Zur Navigation kann die aktuelle Position sowohl absolut als auch relativ über die Bildsequenz bewegt werden. Die Bilder der Sequenz können an jeder Position abgegriffen werden. Dabei wird auch automatisch die Position in der Sequenz weiter geschoben.
Bild 54: Klasse ImageSourcePPM mit abstrakter Basisklasse ImageSource
Momentan ist nur ImageSourcePPM, eine konkrete Bildquelle für numerierte Sequenzen von PPM-Bildern, implementiert worden. Zur Initialisierung der Klasse ImageSourcePPM muss die Methode setParameters aufgerufen werden. Dabei gibt der Parameter directory das Verzeichnis an, in dem die PPM-Bildsequenz zu finden ist. Die Namen der Bilder dieser Sequenz beginnen mit basename, tragen die Erweiterung extension und werden mit der Anzahl Ziffern des Parameters length numeriert. Nach Aufruf der Methode setParameters werden die Parameter auf Korrektheit geprüft, die erste und letzte Nummer der aufsteigend numerierten Bildsequenz bestimmt und in den privaten Attributen firstImageNumber und lastImageNumber gespeichert. Mittels der Methoden getFirstIndex und getLastIndex sind diese Werte jederzeit zugänglich.
Nach der Initialisierung der Bildsequenz wird die aktuelle Position der Sequenz (actualImageNumber) auf das erste Bild der Sequenz gesetzt. Die Methode setPosition erlaubt direkt auf ein spezielle Position in der Sequenz zu springen. movePosition verschiebt die aktuelle Position relativ zur aktuellen Position, verbleibt aber innerhalb der Numerierung der Sequenz.
Um Bilder aus der Sequenz zu erhalten, stehen die zwei Methoden getImageRelative und getImageAbsolute zur Verfügung. Die Methode getImageRelative verschiebt die Position zuerst relativ und liefert dann eine Kopie des Bilds in Form eines Zeigers auf die Klasse Image zurück. Zum Einlesen der PPM-Bilder wird innerhalb von ImageSourcePPM eine Instanz der Klasse PPMReader verwendet. Standardmässig wird die Bildposition nur um einen Schritt erhöht. Mittels der Methode getImageAbsolute wird eine Kopie des Bilds an einer absolut adressierten Position geliefert.
4.6 Klassen Point und Rectangle
Die Klassen Point (vgl. Bild 55) und Rectangle (vgl. Bild 56) repräsentieren die einfachen geometrischen Strukturen Punkt und Rechteck. Hierzu speichern sie die notwendigen Koordinaten und bieten Zugriff auf diese. Grundlegende Operatoren und spezielle Konstruktoren werden ebenfalls zur Verfügung gestellt.
Die Klasse Point enthält die x- und y-Koordinate als öffentliche Attribute. Ein Instanz der Klasse Point lässt sich auf drei Arten erstellen. Ohne Konstruktor-Parameter wird ein Punkt mit den Koordinaten (-1, -1) erstellt. Beim Kontruktor können aber auch direkt die x- und y-Koordinaten angegeben werden. Die Übergabe eines bestehenden Punktes erstellt eine Kopie ebendessen. Die Koordinaten lassen sich jederzeit ändern.
Bild 55: Klasse Point
Die Methode isValid liefert true, wenn die Koordinaten des Punkts positiv sind. Ansonsten wird false zurückgegeben. Die Methode dist berechnet die euklidische Distanz des Punkts zu einem anderen Punkt. Die Methode operator== implementiert den üblichen Vergleich zweier Instanzen der Klasse Point. Diese Methode liefert true, falls sich die Koordinaten der beiden Punkte entsprechen. Der operator* implementiert die Multiplikation der beiden Koordinaten eines Punkts mit einer Fliesskommazahl.
Ein Rechteck wird durch 2 Koordinaten-Paare repräsentiert. Diese Koordinaten bestimmen zwei gegenüberliegende Ecken des Rechtecks und sind als öffentliche Attribute x1, y1, x2, und y2 implementiert. Eine Instanz der Klasse Rectangle kann auf vielerlei Arten erstellt werden. Der Aufruf des Kontruktors ohne Parameter erstellt ein Rechteck, bei dem alle 4 Koordinaten den Wert –1 annehmen. Durch die Angabe der zwei Koordinaten-Paare als Konstruktor-Parameter wird ein entsprechendes Rechteck erstellt. Hierbei werden die Koordinaten wenn notwendig noch so vertauscht, dass das erste Paar die untere linke Ecke und das zweite Paar die obere rechte Ecke repräsentiert. Werden dem Konstruktor zwei Punkte übergeben, so werden diese als Ecken des Rechtecks interpretiert und die zwei internen Koordinaten-Paare dementsprechend angepasst. Neben der Angabe eines bestehenden Rechtecks zur Erstellung einer unabhängigen Kopie können dem Konstruktor auch der Mittelpunkt und die gewünschten Dimensionen (Breite und Höhe) des Rechtecks übergeben werden. Die zwei internen Koordinaten-Paare werden aus diesen Angaben berechnet und stellen das Rechteck in der gewohnten Form dar.
Bild 56: Klasse Rectangle
Die Methode isValid liefert true, wenn alle Koordinaten des Rechtecks positiv sind. Ansonsten wird false zurückgegeben. Die Methode area berechnet die Fläche des Rechtecks. Die Methode operator== vergleicht zwei Rechtecke und liefert true, falls sich die Werte der Koordinaten der zwei Eckpunkte der beiden Rechtecke entsprechen.
Die abstrakte Basisklasse FilterStrategy definiert eine Schnittstelle zur Verarbeitung von digitalen Bildern. Die zu verarbeitenden Bilder sind Instanzen der Klassen Image8 oder Image24 und werden als Zeiger auf die Klasse Image der Methode apply übergeben. Diese Methode lässt das Quellbild unberührt und erstellt ein neues, verändertes Bild, welches auf der Quelle basiert. Dieses Resultat wird in Form eines Zeigers (Image*) zurückgegeben.
Die von der Basisklasse abgeleiteten Klassen von Bild 57 implementieren verschiedene Aspekte von Filtern, welche auf digitale Bilder angewandt werden können. Einige verwenden zur Erstellung eines Resultats nur das Quellbild, andere verwenden noch zusätzliche Parameter. Diese Parameter werden als private Attribute in der Klasse abgespeichert und können mittels setParameters oder bereits durch den Konstruktoraufruf gesetzt werden. Abfragen lassen sich diese Attribute durch die Methode getParameters.
Bild 57: Abstrakte Basisklasse FilterStrategy mit allen abgeleiteten Klassen
Die Klasse FilterRotate180 implementiert eine einfache Komponente, welche ein Bild um 180° rotiert. Hierzu wird in der Methode apply je nach Typ des Quellbilds (Graustufen oder TrueColor) eine Instanz von Image8 resp. Image24 mit den Dimensionen des Quellbilds erstellt. In das Zielbild werden alle Pixel aus dem Quellbild eingetragen; dabei werden die x- und y-Koordinaten der Quellpixel jeweils gespiegelt und erst dann ins Zielbild eingebracht. Das Resultat wird, wie bei allen apply-Methoden der von FilterStrategy abgeleiteten Klassen, als Zeiger (Image*) zurückgegeben.
Bei der Implementation der Methode apply der Klasse FilterBinarize wird zuerst ein leeres Graustufenbild mit den Dimensionen des Quellbilds erstellt. In das Zielbild wird ein schwarzes Pixel eingetragen, falls die Helligkeit des Quellpixel kleiner als der Schwellwert (myThreshold) ist. Ansonsten wird ein weisses Pixel ins Zielbild eingetragen.
Die Konversion von beliebigen Bildern in Graustufenbilder wird von FilterGreyscale implementiert. Die Konversion von TrueColor-Pixel in Graustufen-Pixel wird bereits von der Methode getGreyscale der Klasse Image24 erledigt. Die Graustufen müssen also nur noch mit getGreyscale aus dem Quellbild gelesen und mit setGreyscale ins Zielbild geschrieben werden.
Die Klasse FilterCutRectangle ermöglicht es, einen rechteckigen Bereich aus einem digitalen Bild auszuschneiden. Dieser rechteckige Bereich wird klassenintern als myRect gespeichert und seine Breite und Höhe bestimmen die Grösse des beim Aufruf der Methode apply resultierenden Zielbilds. Zur Beschneidung des Quellbilds werden alle Pixel ins Zielbild kopiert, welche im Quellbild vom Rechteck überspannt werden.
Mittels der Klasse FilterCutMask können Bilder maskiert werden. Die hierzu notwendige Maske ist ein binäres Bild (Instanz der Klasse Image8) welches klassenintern über den Zeiger myMask verfügbar ist und durch den Konstruktoraufruf oder die Methode setParameters gesetzt werden kann. Die Maske sollte mindestens die Grösse des Quellbilds haben. Alle Pixel des Quellbilds, welche mit einem schwarzen Pixel in der Maske korrespondieren, werden ins Zielbild kopiert. Alle übrigen Pixel werden im Zielbild weiss eingefärbt. Abhängig von der Farbtiefe des Quellbilds ist das Zielbild eine Instanz der Klasse Image8 resp. Image24.
Die Implementation der Klasse FilterExpandBlack dient der Erstellung der Maske aus einem binären Bild des Schriftzugs wie sie bereits in "3.2.3 Generierung der Maske" vorgestellt wurde. Hierbei wird in mehreren Schritten jedes Pixel schwarz eingefärbt, welches schwarze Pixel in seiner 8-Nachbarschaft hat. Die Anzahl der Iterationen wird im privaten Attribut myCount gespeichert und kann über die Methode setParameters oder den Konstruktoraufruf gesetzt werden. Nach dem Aufruf der Methode apply wird zuerst vom rechteckigen Bereich (myBounds) des Quellbilds das Histogramm erstellt und der Threshold nach Otsu berechnet. Mittels diesem Schwellwert wird das Quellbild binärisiert und in einer neu erstellten Instanz von Image8 abgelegt. In jedem Iterationsschritt wird jedes Pixel innerhalb myBounds verarbeitet. Wenn ein Pixel in seiner 8-Nachbarschaft ein schwarzes Pixel hat, so wird es im Zielbild schwarz eingefärbt. Ansonsten wird seine Farbe belassen. Nach jedem Iterationsschritt wird das Zielbild zum Quellbild für den nächsten Iterationsschritt. Wenn alle Schritte abgearbeitet sind, wird das Resultat zurückgegeben.
Die Expansion der Graustufen nach der Formel von Bild 27 wurde in der Klasse FilterExpandGreyscale implementiert. Hierbei werden die Grauwerte im rechteckigen Bereich myBounds des Quellbilds in eine neues Graustufenbild expandiert und als Resultat zurückgegeben. Bei der Berechnung des Grauwerts jedes Pixel im Zielbild wird die 8-Nachbarschaft betrachtet. Innerhalb dieser 8-Nachbarschaft wird der Mittelwert und das Minimum der Grauwerte bestimmt. Das arithmetische Mittel dieser zwei Werte wird im Zielbild der Expansion gespeichert.
Die Klasse FilterScale implementiert einen einfachen Algorithmus zum Skalieren von Bildern. Zuerst wird ein neues Bild des gleichen Typs wie das Quellbild erstellt. Die Dimensionen des Zielbilds sind abhängig vom Skalierungsfaktor, welcher im privaten Attribut myScale abgelegt ist. Die Methode apply berechnet zu jedem Pixel im Zielbild die Koordinaten des Quellpixel (Quellkoordiante = Zielkoordinate / Skalierungsfaktor) und kopiert dessen Farbinformation ins Zielbild. Zur Berechnung der Skalierung wird kein Anti-Alias vorgenommen und es kann zu Artefakten im Zielbild kommen. Ganzzahlige Skalierungen, z.B. um den Faktor zwei, ergeben jedoch gute Resultate.
4.8 Klasse Filter
Die Klasse Filter von Bild 58 enthält Methoden der Bildverarbeitung welche in verschiedenen Klassen verwendet werden. Es stehen Methoden zur Berechnung von einfachen und korrigierten Differenzbildern, zur Mischung von Differenzbildern und zur Elimination von Pixel aus Bildern zur Verfügung.
Bild 58: Klasse Filter
Die Methode applyDeltaImage berechnet ein einfaches Differenzbild nach der Formel von Bild 22 zwischen zwei Bildern (img1 und img2) innerhalb eines rechteckigen Bereichs (bounds). Ein Zeiger auf dieses Differenzbild (Image8) wird als Resultat der Methode zurückgegeben. Bei der Berechnung dieses einfachen Differenzbilds wird zuerst eine neue Instanz der Klasse Image8 mit den Dimensionen der Quellbilder erstellt und weiss eingefärbt. Danach wird für jedes Pixel im rechteckigen Bereich die Differenz berechnet und im Differenzbild abgespeichert. Das Differenzbild wird am Ende der Methode als Resultat an die aufrufende Routine zurückgegeben.
Mitttels der Methode applyDeltaImageCorrection werden Korrekturen aus nachfolgenden Bildern in ein Differenzbild (dest) in einem rechteckigen Bereich (bounds) eingebracht. Diese Methode implementiert die Formel von Bild 23. Die notwendigen Korrekturen werden anhand zweier nachfolgender, benachbarter Bilder (img1 und img2) der Sequenz vorgenommen. Im Gegensatz zur Methode applyDeltaImage ist bei dieser Methode das Zielbild bereits vorhanden und wird, wenn notwendig, nur noch angepasst. Für jedes Pixel im rechteckigen Bereich werden die Differenz zwischen den entsprechenden Pixel in den Bildern img1 und img2 berechnet und daraus resultierende Korrekturen im Zielbild vorgenommen.
Die Methode applySubtractImage subtrahiert Helligkeitswerte eines Bilds (remove) von den Helligkeitswerten eines anderen Bilds (ori). Diese Subtraktion findet gemäss der Formel von Bild 26 und nur innerhalb eines rechteckigen Bereichs statt. Der Helligkeit jedes Pixels im rechteckigen Bereich (bounds) des Zielbilds (ori) wird die Helligkeit des entsprechenden Pixel im anderen Bild (remove) abgezogen. Dabei wird berücksichtigt, dass die Helligkeitswerte auf das Intervall [0 .. 255] beschnitten werden.
Die Mischung zweier Bilder – source wird in dest eingemischt – wird durch die Methode applyMergeImages innerhalb eines rechteckigen Bereichs (bounds) vorgenommen. Die Formel, welche der Implementation dieser Methode zugrunde liegt, ist in Bild 25 aufgeführt. Zur Einmischung eines Bilds in das andere Bild werden die korrespondierenden Pixel im rechteckigen Bereich verglichen und das dunklere Pixel gewählt.
4.9 Klasse Histogram
Mittels der Klasse Histogram kann das Graustufen-Histogramm eines digitalen Bilds erstellt, dargestellt und ein Threshold mit dem Algorithmus von Otsu berechnet werden. Für ein bestimmtes Bild werden die Häufigkeiten jedes Grauwerts bestimmt und sowohl als Zahlenwert, als auch als Prozentsatz aller Grauwerte klassenintern abgespeichert. Diese Verteilung lässt sich als Tabelle und grafisch darstellen. Der Algorithmus von Otsu verwendet diese Verteilung um einen Threshold zu bestimmen, der die Grauwertverteilung in zwei Klassen aufteilt.
Jedes Histogramm basiert auf einem digitalen Bild. Dieses Bild kann entweder beim Konstruktoraufruf oder mit der Methode generate bestimmt werden. Die Methode generate verarbeitet jedes Pixel des Bilds und erstellt dabei die Häufigkeitstabelle myHistCount. In dieser Tabelle wird für jeden der 256 Grauwerte die Anzahl der Pixel im Bild gespeichert. Wird bei der Methode generate noch eine Rechteck angegeben, dann wird die Auswertung des Bilds auf diesen Bereich beschränkt. Aus der Verteilung der Anzahl Pixel pro Graustufe (myHistCount) wird dann die prozentuale Verteilung pro Graustufe (myHistPercent) berechnet. Gleichzeitig werden die hellste (myMaxValue) und die dunkelste (myMinValue) im Bild vorkommende Graustufe und die maximale Anzahl Pixel (myMaxCount) pro Graustufe ermittelt.
Die verschiedenen get-Methoden erlauben den Zugriff auf private Klassenattribute. Hiermit können die Anzahl der ausgezählten Pixel (getPixelcount), die Helligkeit des hellsten (getMaxValue) und dunkelsten (getMinValue) Pixel und die maximale Anzahl Pixel einer Graustufe (getMaxCount) des Histogramms abgefragt werden. Mit getValueCount wird die Anzahl Pixel mit einem bestimmten Grauwert abgefragt. getValuePercent liefert die Häufigkeit dieses Grauwerts.
Die Methoden getHistogramPercent und getHistogramCount liefern je ein ganzes Feld mit den Angaben zur Grauwertverteilung. Die erste Methode liefert die prozentuale Verteilung und die zweite Methode die zahlenmässige Verteilung. Soll das Histogramm grafisch dargestellt werden, so erstellt die Methode createImage ein Bild der Grösse 256 auf 256 Pixel des Histogramms.
Der Algorithmus von Otsu bestimmt basieren auf dem Histogramm einen Threshold. Dieser Threshold kann dann als Schwellwert zur Binärisierung eines Graustufenbilds verwendet (vgl. "3.6.1 Binärisierung aufgrund des Histogramms"). Die einfache Methode otsu liefert nur den Threshold. Die Methode otsudetails liefert zusätzlich noch alle Parameter, welche bei der Berechnung des Otsu-Thresholds mit der Spider-Bibliothek (vgl. [JDS83]) anfallen. Der wichtigste Parameter zur Beurteilung der Brauchbarkeit des Resultats, die Varianz des Histogramms, wird in der Variable vari zurückgegeben. Der eigentliche Otsu-Threshold wird von einem kleinen Fortran-Programm aus der Spider-Bibliothek errechnet. Die notwendigen C-Deklarationen zur Einbindung der externen Fortran-Routine thds2_ werden in der eingebundenen Datei spider.h von Peter Steiner und Jan Holler erledigt.
4.10 Klasse Detector
Die Klasse Detector stellt eine Schnittstelle zur Berechnung von Stiftpositionen anhand von Grauwertbildern zur Verfügung. Hierbei wird das Grauwertbild mit einem Schwellwert binärisiert und aufgrund der schwarzen Pixel in einem rechteckigen Bereich ein Zentrum bestimmt. Auf den Schwellwert, klassenintern im privaten Attribut myThreshold abgespeichert, kann über die Methoden setThreshold und getThreshold zugegriffen werden. Der rechteckige Bereich, in welchem nach einer Stiftposition gesucht wird, ist im privaten Attribut myRectangle abgelegt und wird über die Methoden setRectangle und getRectangle angesprochen.
Die konkrete Implementation der verschiedenen Routinen zur Bestimmung des Zentrums findet wie in Bild 60 dargestellt, in den, von der abstrakten Basisklasse Detector abgeleiteten, Klassen DetectorSimple, DetectorIterative, DetectorMedian und DetectorNeighbour statt. Diese verschiedenen Ansätze wurden bereits in "3.6 Stiftpositionen erfassen" ausführlich erläutert. Zur Bestimmung der verschiedenen Zentren wird jeweils die Methode apply aufgerufen. Dieser Methode muss ein Zeiger auf das zu analysierende Differenzbild (source) und ein rechteckiger Fensterbereich (win) angegeben werden. Die Angabe des Fensterbereichs schränkt die Anzahl zu verarbeitender Pixel weiter ein. Es wird nur in den Teilen des Differenzbilds nach der neuen Stiftposition gesucht, welche sowohl im durch myRectangle (Bounding-Box um den Schriftzug) als auch durch win (Fensterbereich um letzte erfasste Stiftposition) bestimmten Bereich liegen.
Bild 60: Abstrakte Basisklasse Detector mit allen abgeleiteten Klassen
Die Klasse DetectorSimple implementiert die in "3.6.3 Einfacher Mittelpunkt" vorgestellte einfachste Methode zur Bestimmung eines Zentrums von schwarzen Punkten. Diese Methode verarbeitet alle Bildpunkte welche innerhalb win und myRectangle liegen. Ist die Helligkeit eines Pixel nicht grösser als der Schwellwert myThreshold, dann werden die Koordinaten dieses Punkts zur Bestimmung des arithmetischen Mittels verwendet. Wenn alle Pixel verarbeitet sind, dann wird das arithmetische Mittel der x- und y-Koordinaten der schwarzen Punkte bestimmt, auf ganze Zahlen gerundet und zu einem Punkt (Instanz der Klasse Point) zusammengeführt und als Resultat zurückgegeben.
Im ersten Iterationsschritt in der Implementation von DetectorIterative wird ein einfaches arithmetisches Zentrum durch die Klasse DetectorSimple erstellt. Das private Attribut myIterations wird durch die Methoden setIterations oder den Konstruktor gesetzt und bestimmt die Anzahl Iterationsschritte zur Bestimmung des Zentrums. In den weiteren Iterationsschritten von DetectorIterative wird jeder schwarze Punkt im Bildausschnitt gemäss der Formel im Abschnitt "3.6.4 Iterativer Mittelpunkt" gewichtet und ein neues Zentrum berechnet. Das Gewicht ist umgekehrt proportional zur Distanz des schwarzen Punkts zum bisherigen Zentrum.
Bei der Klasse DetectorMedian wird wie in "3.6.5 Mittelpunkt durch Median-Methode" vorgestellt der Median aller x- und aller y-Koordianten der schwarzen Punkte im Bildbereich bestimmt. Hierzu wird zuerst jedes Pixel des Bildbereichs verarbeitet und falls seine Helligkeit geringer als myThreshold ist, werden seine x- und y-Koordinaten je einer Liste zugefügt. Diese Listen sind Instanzen der Template-Klasse list<> aus der STL von C++. Wurden alle Pixel verarbeitet, werden diese Listen mit der Methode sort der Liste list<unsigned int> sortiert. Die zwei mittleren Elemente dieser Listen werden zu einem Punkt kombiniert und als Resultat zurückgegeben.
Die Implementation der Klasse DetectorNeighbour basiert auf den Erläuterungen von "3.6.6 Mittelpunkt durch Neighbour-Methode". Wie bei der Klasse DetectorMedian werden zuerst alle schwarzen Punkte in eine Liste aufgenommen. Zur Repräsentation dieser Liste wird eine Instanz der Template-Klasse vector (vector<Point>) mit dem Namen punkte verwendet. Für jeden Punkt in der Liste punkte wird nun die Summe der Abstandsquadrate zu allen anderen Punkten in dieser Liste berechnet, durch die Anzahl Pixel in der 8-Nachbarschaft des Punkts dividiert und in der Liste distsum (Instanz der Klasse vector<long>) abgespeichert. Nun wird der Punkt mit der kleinsten Abstandssumme gesucht und als Resultat zurückgegeben. Sollte es mehrere Punkte mit dieser minimalen Abstandssumme geben, dann wird derjenige Punkt zum Zentrum erkoren, der am nächsten beim Zentrum des Fensters win liegt.
4.11 Klasse SlidingWindow
Die Klasse SlidingWindow von Bild 61 implementiert den Kern dieser Diplomarbeit. Innerhalb dieser Klasse werden alle bisher vorgestellten Klassen verwendet und koordiniert. SlidingWindow dient dazu ein gedachtes Fenster über die Bildsequenz zu verschieben. Dabei wird für das aktuelle Bildpaar der Sequenz ein Differenzbild erstellt. Dieses Differenzbild wird anhand nachfolgender Bildpaare und der bereits erstellten Differenzbilder korrigiert. Die genaue Funktionsweise der Differenzbilderstellung wurde in "3.4 Erstellung der Differenzbilder" und "3.5 Nachverarbeitung" bereits ausführlich erläutert.
Bild 61: Klasse SlidingWindow
Das gedachte Fenster, welches über die Bildsequenz verschoben wird, ist als Feld von Zeigern auf Bilder realisiert und heisst myImages[]. Das erste Bild dieses Felds entspricht der aktuellen Position der Verarbeitung. Die restlichen Bilder sind die unmittelbaren Nachfolger in der Bildsequenz. Die Anzahl der gespeicherten, nachfolgenden Bilder hängt vom Lookahead der Differenzbilderstellung ab. Je nach Grösse des Lookahead werden mehr oder weniger nachfolgende Bildpaare zur Korrektur des Differenzbilds hinzugezogen. Das aktuelle Differenzbild wird im privaten Attribut myDeltaImage gespeichert. Die letzten paar Summenbilder, d.h. alle bereits erfassten Pixel, werden im Bild-Feld myDeltaMergeWait[] abgelegt.
Die vielen Parameter, welche die Verarbeitung der Bildsequenz steuern, werden in privaten Attributen gespeichert. Der Zugriff auf diese Attribute erfolgt über entsprechende Methoden. Die Bildsequenz wird über die Klasse ImageSource angesteuert. Mittels der Methode setImageSource wird ein Zeiger auf eine konkrete Bildquelle, bislang immer eine Instanz der Klasse ImageSourcePPM, übergeben und im privaten Attribut myImageSource abgelegt. Gleichzeitig werden das Summenbild (myDeltaMergeWait[]) und die Bounding-Box (myBoundingBox) initialisiert. Die Anzahl nachfolgender Bilder, welche korrigierend in die Differenzbilderstellung eingreifen sollen, wird durch die Methode setLookahead im privaten Attribut myLookahead abgelegt. Dementsprechend wird das Bild-Feld myImages[] initialisiert und die dort abgelegten Bilder mittels myImageSource eingelesen. Die Methode setBoundingBox passt das Attribut myBoundingBox an. Dabei wird sichergestellt, dass die Bounding-Box innerhalb des Bildbereichs liegt.
Wenn die Bilder aus der Bildsequenz eingelesen werden sollen, wird die private Methode generateImages aufgerufen. Diese liest für jedes Element des Bild-Felds myImages[] das entsprechende Quellbild ein und lässt von der privaten Methode applyPreprocessing die Vorverarbeitung (Rotation um 180°, Beschneiden auf Bounding-Box, Maskieren) durchführen. Bei der Vorverarbeitung werden der Reihe nach alle Filter der Liste myPreprocessing auf das Quellbild angewandt. Diese Liste legt Zeiger auf die Klasse FilterStrategy ab und wurde mittels der Template-Klasse list<> der STL realisiert. Soll nun in der Vorverarbeitung jedes Quellbild zuerst um 180° rotiert werden, auf die Bounding-Box zugeschnitten und schliesslich maskiert werden, so besteht die Liste myPreprocessing aus je einem Zeiger auf eine Instanz der Klassen FilterRotate180, FilterCutRectangle und FilterCutMask. Diese Filter werden mittels der Methode addPreprocessFilter an die Liste angehängt. Dasselbe geschieht nach der Differenzbilderstellung in der Nachverarbeitung. Die für die Nachverarbeitung benötigten Filter-Klassen werden mit der Methode addPostprocessFilter an die private Liste myPostprocessing angehängt und durch die private Methode applyPostprocessing nacheinander auf das Differenzbild myDeltaImage angewandt.
Die Routine zur Erfassung der Stiftposition aus dem Differenzbild wird durch einen Zeiger auf die Klasse Detector im privaten Attribut myDetector bestimmt. Dieser Zeiger verweist auf eine Instanz der abgeleiteten Klassen von Bild 60 und wird durch die Methode setDetector gesetzt. Der Grenzwert der Varianz des Histogramms des Differenzbilds wird im privaten Attribut myVarianceLimit gespeichert und kann über die Methode setThresholdOtsu gesetzt werden. Dieser Wert definiert, wie in "3.6.1 Binärisierung aufgrund des Histogramms" bereits ausführlich beschrieben wurde, die minimale Varianz, bis zu welcher der resultierendene Threshold des Algorithmus von Otsu noch akzeptiert wird. Das private Attribut myAreaLimit wird über die Methode setAreaLimit gesetzt und steuert wie bereits myVarianceLimit die Akzeptanz der Binärisierung mittels dem Algorithmus von Otsu. Wie in "3.6.2 Aufgespannte Fläche" erwähnt wurde, wird die Binärisierung des Differenzbilds nur dann akzeptiert, wenn die Fläche der Konvexen Hülle der schwarzen Punkte im binären Differenzbild einen bestimmten Anteil (myAreaLimit) an der Gesamtfläche des Fensters win nicht überschreitet. In den vorherigen Abschnitten wurden alle Parameter der Klasse SlidingWindow vorgestellt – nun kann die eigentliche Funktionsweise dieser Klasse vorgestellt werden:
Die Methoden moveFirst, moveLast, moveNext, movePrevious und move dienen der Navigation über die Bildsequenz myImageSource. Um die aktuelle Position der Klasse SlidingWindow auf das erste Bild der Sequenz zu setzen, wird die Methode moveFirst verwendet; moveLast springt ans Ende der Bildsequenz. Mittels der Methoden moveNext und movePrevious wird die Position um eine Stelle nach vorne resp. hinten geschoben. Die Methode move erlaubt eine Verschiebung der Position um die im Parameter step angegebene Anzahl Bilder; positive Werte verschieben die Position vorwärts, negative Werte rückwärts. Entsprechend der durchgeführten Navigation wird der Index der aktuellen Position innerhalb der Bildsequenz im privaten Attribut myPosition angepasst. Zusätzlich wird der Ausschnitt der Bildsequenz, welcher im Bild-Feld myImages[] abgelegt ist, angepasst. Bei einer Verschiebung der Position um eine Stelle werden die Bildreferenzen kopiert und nur das zusätzliche Bild eingelesen und mittels der privaten Methode applyPreprocessing vorverarbeitet. Ansonsten müssen alle Bilder des Felds von der privaten Methode generateImages neu erstellt werden.
Durch den Aufruf der Methode apply wird die eigentliche Aufgabe der Klasse SlidingWindow ausgeführt. Anhand der eingelesenen und vorverarbeiteten Bilder myImages[] der Sequenz myImageSource wird mittels den Methoden applyDeltaImage und applyDeltaImageCorrection der Klasse Filter ein korrigiertes Differenzbild myDeltaImage erstellt. Nach der Nachbearbeitung werden die bereits erkannten Pixel des Summenbilds (myDeltaMergeWait[0]) vom Differenzbild entfernt und danach aufgrund des Histogramms des Differenzbilds ein Schwellwert (myThreshold) nach Otsu bestimmt. Wenn sowohl das Varianz-Kritierium als auch das Kriterium des Anteils der aufgespannten Fläche erfüllt sind, wird die Stiftposition mittels derjenigen Routine, auf die myDetector verweist, ermittelt und als Resultat in Form einer Instanz der Klasse Point der Methode apply zurückgeliefert. Alle Aufgaben innerhalb der Methode apply werden auf den rechteckigen Fensterbereich tmpWindow beschränkt, welcher beim Aufruf der Methode apply als Parameter übergeben wurde.
Das aktuelle Summenbild ist im ersten Element des Felds myDeltaMergeWait[] abgelegt. Vor der Subtraktion des Summenbilds vom Differenzbild wird es noch temporär expandiert. Hierzu wird ein neues Bild tempDeltaMerge durch eine Instanz der Klasse FilterExpandGreyscale (vgl. Bild 57) erstellt. Das expandierte Summenbild wird dann mittels der Methode applySubtractImage der Klasse Filter (vgl. Bild 58) vom Differenzbild myDeltaImage entfernt.
Wenn die Varianz des Histogramms des Differenzbilds grösser als die Schranke myVarianceLimit und der Anteil der aufgespannten Fläche kleiner als die Schranke myAreaLimit ist, dann werden die grauwertigen Pixel des Differenzbilds zum Summenbild gemischt. Weil diese Operation, wie in "3.5 Nachverarbeitung" bereits erklärt wurde, verzögert stattfinden muss, wird das aktuelle Differenzbild mit dem letzten Bild des Felds myDeltaMergeWait[] gemischt und am Ende dieses Feld angehängt. Gleichzeitig wird das erste Element dieses Felds entfernt und die restlichen Elemente werden eine Position noch vorne geschoben. Hierdurch muss das neu eingemischte Differenzbild zuerst in der "Warteschlange" myDeltaMergeWait[] nach vorne wandern und wird daher erst nach einigen Schritten zur Elimination aus einem frisch erstellten Differenzbild verwendet.
4.12 Klasse Interpolator
Die Klasse Interpolator von Bild 62 implementiert die verschiedenen Methoden zur Verbesserung der Online-Daten wie sie in "3.7 Verbesserung und Ausgabe der Positionen" vorgestellt wurden. Die als Punkt-Liste vorliegenden Online-Daten werden dabei eingelesen, analysiert und gegebenenfalls verbessert. Die neue Punkt-Liste wird als Resultat zurückgegeben.
Die privaten Attribute myMaxDistance, myMaxInterpolate und myMaxGaps, welche das Verhalten der Klasse Interpolator steuern, werden über den Klassenkonstruktor oder über die Methode setParameters gesetzt. Die Methode apply interpoliert die Punkt-Liste und liefert das Resultat ebenfalls als Punkt-Liste zurück. Diese Punkt-Liste wird durch die Template-Klasse vector<Point> der STL repräsentiert. Eine solche Punkt-Liste besteht sowohl aus Stiftpositionen als auch aus "leeren" Stiftpositionen, wenn der Stift nicht auf dem Blatt Pappier abgesetzt war. Diese "leeren" Stiftpositionen sind normale Instanzen der Klasse Point, jedoch mit negativen Koordinaten. Die Methode isValid liefert bei diesen Punkten den boolschen Wert false.
Bild 62: Klasse Interpolator
Die genaue Funktionsweise der Methode apply kann nachfolgendem Pseudocode entnommen werden:
Leere Punkt-Liste result erstellen
while Zeiger2 nicht am Ende der Liste
wend |
Die verbesserten Punkte in der Liste result werden schliesslich als Resultat zurückgeliefert.
1) Standard Template Library. Diese C++ Bibilothek enthält einen umfangreichen Satz effizienter, generischer Datenstrukturen und Algorithmen, welche austauschbar und wiederverwendbar sind. Eine Einführung in die STL gibt [Bre96].