Praktikum Bildverarbeitung Bereichswachstum
Auf dieser Seite findest du die Dokumentation zum Praktikum Bildverarbeitung mit dem Thema: "Bereichswachstum (Region Growing)".
Im Jahr 2004 habe ich zusammen mit einem Kommilitonen an diesem Projekt gearbeitet und einen Region-Growing-Algorithmus implementiert, der zur Auswertung von Bilddaten eines Aufnahmetisches im Schulungslabor genutzt werden kann.
1. Inhaltsverzeichnis
2. Allgemeine Problemstellung
3.1.1 Oberfläche des Programms "BVATisch"
3.1.3 Verwendung von Filterparametern
4.1 Entwicklungskonfiguration
4.2 Problemanalyse und Realisation
4.2.2 Initialpunktberechnung (Startpunktberechnung)
4.2.2.1 Ermittlung der lokalen Intensitätsschwellen
4.2.2.2 Eliminierung der Randpunkte von Bereichen als in Frage kommende Startpunkte
4.2.2.3 Aussieben von möglichen Startpunkten
4.2.2.4 Auslöschen nicht benötigter Startpunkte
4.2.3 Wachstum der Startpunkte
4.2.4 Verschmelzen von Bereichen
4.3 Beschreibung grundlegender Datenstrukturen
4.3.2.1 Auflistung und Beschreibung aller eigenen Typen
4.3.2.2 Die Zeigerstruktur der Startpunkt- und Bereichslisten
4.3.3 Verwendete globale Variablen
4.4 Programmorganisationsplan
4.4.1 Aufbau und Struktur der DLL
4.4.2 Funktionsabhängigkeiten untereinander
4.5 Programmtests und Ergebnisse
4.5.1 Programmtests mit kritischen Optionen
4.5.2 Ergebnisse und Beispiele des Filters
4.5.2.1 Beispiele zum Finden von Randpunkten
4.5.2.2 Beispiel für den Einfluss unterschiedlicher lokaler Intensitätsschwellen
4.5.2.3 Beispiele zur Initialpunktberechnung
4.5.2.4 Beispiele zum Bereichswachstum
2. Allgemeine Problemstellung
Flächenwachstum (Region Growing):
Aus der Gruppe der bereichsorientierten Segmentierungsverfahren soll ein spezieller Algorithmus implementiert werden, der eine Segmentierung in annähernd intensitätskonstante Bereiche liefert. In der Literatur werden zwar unterschiedliche Lösungsansätze zum Bereichswachstum beschrieben, hier wird jedoch nur ein Verfahren untersucht (in Anlehnung an die BVA-Vorlesung).
Dazu sollen einige der am XYR-Tisch bereitliegenden Gegenstände auf dem Objektträger platziert werden, so dass die Bildaufnahme gestartet werden kann.
Die beiden Phasen des Verfahrens (Bestimmung der Initialpunkte und Verschmelzung zu intensitätskonstanten Regionen) sollen in Form eines angepassten Plugins implementiert werden, das aus diesen RGB-Daten (3 Bitplanes mit jeweils 1008x767 Pixeln) geeignete Graustufenbilder erzeugt
Zur Darstellung der segmentierten Bereiche im Ergebnisbild bietet sich die Einfärbung mittels Fehlfarben an.
3. Benutzerhandbuch
3.1 Bedienungsanleitung
3.1.1 Oberfläche des Programms "BVATisch"
Das Programm BVATisch stellt die Rahmenbedingung zur Verfügung, damit das Plugin einwandfrei ausgeführt werden kann. Soll nun das Bereichswachstumsverfahren auf ein Bild angewendet werden, so ist zunächst das Quellbild auszuwählen, indem man auf den Datei-Öffnen-Dialog des "BVADoc_0" Fensters klickt und dann das Bild auswählt, das verarbeitet werden soll.
Anschließend wird das Quellbild als Bildquelle 1 festgelegt, indem man per Rechtsklick auf das Bild entsprechendes auswählt. Danach muss noch das Plugin ausgewählt werden, indem man in der oberen Leiste auf das Kettensymbol klickt und anschließend die entsprechende dll-Datei auswählt. Gegebenenfalls können noch über „Plugins -> Filterparameter“ die Parameter für das Plugin gesetzt werden. Dazu mehr in 3.1.3. Mit Klick auf den Playbutton oben rechts beginnt dann die Verarbeitung des Bildes. Nach erfolgreichem Durchlauf öffnet sich dann ein zweites Fenster, worin das Ergebnis angezeigt wird. Im Statusfenster des Ergebnisbildes werden noch zusätzliche Informationen über die Rechendauer und die Anzahl der Bereiche angegeben.
3.1.2 Ablaufbedingungen
Damit die Verarbeitung des Quellbildes optimal funktioniert, müssen folgende Spezifikationen erfüllt sein:
- Das Quellbild muss entweder im Graustufen- oder im RGB- Format vorliegen
- Die Mindestbildgröße sollte 4x4 Pixel betragen
Die Rechengeschwindigkeit des Computers sollte mindestens 1 GHz betragen, da, besonders bei größeren Bildern (z.B. Das Format der Bilder des Grabbertisches 1008 x 728), sehr viele Rechenoperationen durchgeführt werden müssen. Die Verarbeitung eines 1008x728 Pixel großen Bildes beträgt auf einem 1,4 Ghz- Rechner ca. 20 Sekunden
3.1.3 Verwendung von Filterparametern
Das Bereichswachstumsverfahren kann über verschiedene Parameter modifiziert werden, die mithilfe der Filterkernmatrix an das Plugin übergeben werden. Bei Klick auf Plugins -> Filterparameter öffnet sich das Fenster mit der 3x3 Matrix. Dabei hat jedes einzelne der neun Felder eine individuelle Bedeutung, welche alle in der folgenden Tabelle erläutert werden. Dabei entspricht die Position der jeweiligen Erläuterung der Position der Werte in der Matrix. Die Werte in der Matrix des Screenshots zeigen die Default-einstellungen, wenn eines der Felder 0 enthält. Die Optionalen Parameter sind nicht relevant.
|
Anzahl Intensitätskacheln in horizontaler Richtung. |
Anzahl Intensitätskacheln in vertikaler Richtung. |
Aussiebungsfaktor. Nur jeder k-te Punkt in x- und y-Richtung kommt als Startpunkt in Frage (siehe 4.2.2.3) |
|
Randpunkttoleranz. Wert, der bestimmt ab wann ein Punkt nach dem Gradientenverfahren als Randpunkt definiert wird. |
Art des Gradientenverfahren zur Festlegung der Randpunkte eines Objektes im Bild
0 = Sobelgradient 1 = Absolute Pseudolaplace Operator 2 = Robertsgradient |
Farbwertabweichung, die ein Punkt haben darf, um beim ersten Durchlauf des Bereichswachstums noch mit in den Bereich aufgenommen zu werden. |
|
Wert, um den die Farbwertabweichung beim Wachsen nach jedem Durchlauf erhöht wird. |
Wachstumsmodus. Beim „Fastmode“ wachsen die Bereiche pro Durchlauf seriell an, d.h. ein Bereich wächst solange wie es geht, danach der nächste, usw. Beim „Slow-Mode“ wachsen die Bereiche pseudoparallel, d.h. ein Bereich dehnt sich, wenn möglich, am Rand nur um einen Pixel aus, bevor der nächste Bereich mit dem Wachstum beginnt, usw. |
Verschmelzungstoleranz. Nach dem Bereichswachstum hat jeder Bereich einen Durchschnittsfarbwert. Liegt die Differenz der Farbwerte zweier aneinandergrenzender Bereiche innerhalb dieser Toleranz, werden die zwei Bereiche verschmolzen. |
4. Programmierhandbuch
4.1 Entwicklungskonfiguration
Die Entwicklung der Filter-DLL wurde mit Hilfe folgender Konfiguration durchgeführt:
Hardware
Programmierung:
- AMD Athlon XP 1600+ @ 1,4 GHz
- 512 MB Arbeitsspeicher (DDR266)
- Ati Radeon 8500 Grafikkarte, 64 MB
Bildaufnahme:
- Arbeitsrechner im BVA-Labor und XYR-Tisch mit CCD-Farbkamera (M77)
Software
- Betriebssystem: Windows XP
- Programmierumgebung: Delphi 6.0 (Personal Edition)
- Grafikprogramm Photo Impact 6 zum Bilder erstellen, bearbeiten und vergleichen
- UltraEdit-32 Version 10.0 zum Bearbeiten der Quellcodes
- Common Vision Blox (CVB) Paket bzw. als Schnittstelle "BVATisch"
4.2 Problemanalyse und Realisation
In diesem Kapitel werden die einzelnen Verarbeitungsschritte uns Algorithmen des Bereichswachstumsverfahrens ausführlich erläutert.
4.2.1 Graustufenumwandlung
Da das gesamte Verfahren auf Graustufenbildern basiert, muss das Quellfarbbild zuerst in Graustufen umgewandelt werden. Dies wird so gemacht, indem für jeden neuen Graustufenpixel der Durchschnittswert der drei RGB- Kanäle des Farbpixels gebildet wird.
4.2.2 Initialpunktberechnung (Startpunktberechnung)
Bevor mit dem eigentlichen Bereichswachstum begonnen wird, muss zunächst in jedem Bereich des Bildes ein Startpunkt festgelegt werden, von dem aus dann das Wachstum beginnt.
4.2.2.1 Ermittlung der lokalen Intensitätsschwellen
Jedes Bild wird dafür zunächst einmal in gleichgroße Kacheln aufgeteilt. Für jede Kachel wird dann die Differenz zwischen minimalem und maximalem Pixelfarbwert gebildet und durch einen Faktor K geteilt. Die Konstante K wird empirisch bestimmt, meist ist k=3 eine empfehlenswerte Lösung. Nun gibt es für jede Kachel eine individuelle Intensitätsschwelle, was den Vorteil hat, das lokale Kontrastunebenheiten, z.B. durch Beleuchtungseinflüsse, ausgeglichen werden können, da bei den folgenden Berechnungen in Bezug auf Farbunterschiede zwischen zwei Pixeln diese Schwelle als Referenz benutzt wird.
4.2.2.2 Eliminierung der Randpunkte von Bereichen als in Frage kommende Startpunkte
Wenn zwei Bereiche aneinander grenzen, ist es oft der Fall, dass am Übergang Farbverläufe vorkommen, z.B. bedingt durch Schattenbildung. Wenn ein Startpunkt auf dem Rand liegt, besitzt er demnach einen Farbwert, der ungefähr zwischen den Durchschnittswerten der beiden Bereiche liegt. Unter Umständen kann es also vorkommen, dass das Wachstum in beide Bereiche fortschreitet. Um zu vermeiden, dass dies passiert, müssen alle Randpunkte als in Frage kommende Startpunkte eliminiert werden.
Im Plugin sind hierfür drei Gradientenverfahren implementiert.
Als Beispiel sei hier ein Pixel E angeführt, der von acht Pixeln umrahmt ist. Für den Pixel E soll bestimmt werden, ob es sich um einen Randpixel handelt.
Die drei Verfahren(Sobel-, Absolute Pseudo Laplace- und Robertsverfahren) unterscheiden sich in der Art der Berechnung und Einbeziehung der Farbwerte der umliegenden Pixel.
gsob = |(A+2B+C) – (G+2H+I)| + |(A+2D+G) – (C+2F+I)|
gapl = |(D–2E+F) + (B-2E+H)|
grob = max(|A–E|, |B–D|)
Wird ein bestimmter Wert (Parameter, abhängig von lokaler Intensitätsschwelle und einer wählbaren Empfindlichkeitsgröße) überschritten, so wird der Punkt als Randpunkt markiert.
Prinzipiell eignen sich alle drei Verfahren gut, um die Randpunkte zu markieren. Die Sobel- und APL-
Gradienten zeichnen sich durch eine geringere Empfindlichkeit gegenüber Störungen aus, da dort 3x3 Pixel in die Berechnung einfließen, während beim Robertsgradienten nur 2x2 Pixel relevant sind. Dafür sind die Ränder bei diesem schmaler.
4.2.2.3 Aussieben von möglichen Startpunkten
Da nach dem Markieren der Bildränder prinzipiell alle übrigen Punkte in Frage kommen, kommt es bei größeren Bildern beim Auslöschen (4.2.2.4) schnell zu hohen Geschwindigkeitseinbußen. Um diesen Effekt zu unterdrücken, wird in x- und in y- Richtung nur jeder k-te Punkt als in Frage kommender Startpunkt verwendet. Für die Werte 2, 3 und 4 für sähe es in etwa folgendermaßen aus (Startpunkte sind weiß):
K=2
K=3
K=4
Ist der k-te Punkt bereits als Randpunkt markiert, wird dieser natürlich auch nach dem Aussieben nicht als möglicher Startpunkt verwendet.
Welcher Wert für k verwendet wird, sollte nach der Feinheit der Bereiche ermessen werden. Ist ein Bereich beispielsweise 5x5 Pixel groß, wird er bei einem k von 6 schon höchstwahrscheinlich (wegen Berücksichtigung der Randpunkte) nicht mehr erfasst. Prinzipiell sollte gelten: Je kleiner das Bild, desto kleiner kann k gewählt werden. Bei der Auflösung des Grabbertisches (1008 x 767) ist k = 5 ein empfohlener Wert.
4.2.2.4 Auslöschen nicht benötigter Startpunkte
Da jeder Bereich idealerweise nur einen Startpunkt haben sollte, müssen alle noch übrigen Startpunkte eines Bereiches gelöscht werden. Wenn es also einen geschlossenen Weg von einem möglichen Startpunkt zu einem anderen gibt, d.h. alle Wegpixel dürfen eine gewisse Toleranz nicht überschreiten, wird einer der beiden Startpunkte gelöscht. Die Toleranz ist prozentual abhängig von der lokalen Intensitätsschwelle.
Alle nach dem Auslöschen noch übrigen Punkte sollten also in verschiedenen Bereichen liegen.
In diesem Plugin kann es jedoch bei stark verwinkelten Bereichen dazu kommen, dass sich in einem Bereich noch mehr als ein Startpunkt befindet. Dies liegt an dem Wegfindealgorithmus, der, um die Rechengeschwindigkeit nicht zu sehr zu verlangsamen, nur die beiden Wege parallel zu den Koordinatenachsen berücksichtigt. Seien z.B. zwei Startpunkte in einem Bereich, wachsen also erst mal zwei Bereiche an, die nach abgeschlossenem Wachstum verschmolzen werden (Siehe 4.2.4).
4.2.3 Wachstum der Startpunkte
Prinzipiell funktioniert das Bereichswachstum so, dass alle Nachbarpixel eines Bereichsrandpunktes, bzw. des Startpunktes beim ersten Durchlauf, geprüft werden, ob sie in den Bereich mit aufgenommen werden können.
Überschreitet der Farbwert des Nachbarpixels eine (vom Benutzer definierbare) Toleranz, oder gehört er bereits einem anderen Bereich an, so wird dieser Punkt nicht mit aufgenommen. Die Toleranz bezieht sich immer auf den aktuellen Durchschnittswert des Bereiches. Ist der Rand eines Bereichs abgearbeitet oder kann ein Bereich nicht weiter anwachsen, wird mit dem nächsten Bereich fortgesetzt. Kann kein Bereich mehr weiter anwachsen, wird die Toleranz erhöht (Erhöhung ist ebenfalls vom Benutzer einstellbar), und das Wachsen wird fortgesetzt. Diese Prozedur wird solange wiederholt, bis alle Pixel des Bildes einem Bereich zugeordnet sind.
In diesem Plugin sind jedoch zwei Modi des Bereichswachstum implementiert. Die Art und Weise, die oben beschrieben ist, ist der so genannte pseudoparallele „Slow-Mode“. Im „Fast-Mode“ werden nicht nach Bearbeitung aller Randpixel die Bereiche gewechselt, sondern alle Bereiche wachsen nacheinander (seriell) an, bis sie nicht mehr wachsen können. Erst dann wird zum nächsten Bereich gewechselt. Die Vor und Nachteile beider Modi lassen sich im Wesentlichen wie folgt zusammenfassen:
- Der „Fast-Mode“ erfordert erheblich weniger Rechenleistung (Daher auch die Bezeichnungen)
- Durch das quasi gleichzeitige Anwachsen der Bereiche kann es vorkommen, das sich zwei wachsende Bereiche dort treffen, wo eigentlich keine Grenze ist. Jedoch wird durch die unterschiedlichen Durchschnittsfarbwerte eine Grenze entstehen. Dies sollte unbedingt beim Verschmelzen herausgefiltert werden.
- Beim Fast-Mode allerdings kann es passieren, dass ein Startpunkt schon komplett von einem anderen Bereich umschlossen wird, bevor er selbst die Gelegenheit zum Wachsen bekommen hat. In solchen Fällen ist darauf zu achten, dass die Verschmelzungstoleranz (siehe 4.2.4) hoch genug eingestellt ist.
4.2.4 Verschmelzen von Bereichen
Das Verschmelzen dient in erster Linie dazu, mehrere aneinandergrenzende Bereiche, die eigentlich von vornherein einen einzigen Bereich bilden sollten, zu einem zusammenzufassen. Das Verfahren ist im Prinzip trivial. Grenzen zwei Bereich aneinander und liegt der Betrag der Differenz der Durchschnittsfarbwerte innerhalb einer definierten Toleranz, werden die Bereiche verschmolzen.
4.3 Beschreibung grundlegender Datenstrukturen
4.3.1 Verwendete Konstanten
In dem Programm kommen mehrere Konstanten zum Einsatz. Mit ihnen werden wichtige Parameter des Plugins beschrieben, ohne dass der Programmierer den gesamten Quelltext durchsuchen muss. Beide Konstanten befinden sich im Hauptprogramm "bereichswachstum.dpr", werden komplett großgeschrieben (jeder Buchstabe) und beginnen mit einem „C_“ für „const“.
|
Name der Konstanten |
Kurze Beschreibung |
|
C_LEERER_BEREICH = -1; |
Definiert einen Platzhalter für einen leeren oder ungültigen Bereich in der Liste aller Bereiche. |
|
C_DEFAULT : TFilterKern = ((1,1,2), (15,0,20), (8,1,20));
C_MIN : TFilterKern = ((1,1,1), (1,0,1), (1,1,1));
C_MAX : TFilterKern = ((50,50,10), (255,2,255), (255,2,255)); |
Dieses Konstanten-Array enthält die Default-Werte für die verschiedenen Parameter, die das Verhalten des Region Growing steuern. Diese Standard-Werte werden benutzt, wenn der Benutzer keine Parameter oder „0“ an das Plugin übergibt.
|
|
C_INTK = 3; |
Der Wert ist der Teiler bei der Berechnung der Intensitätsschwellen (k). |
4.3.2 Eigene Typen
4.3.2.1 Auflistung und Beschreibung aller eigenen Typen
Hier finden Sie eine Auflistung aller Typen, die im Programm verwendet werden:
|
Typdeklaration |
Beschreibung |
|
TInfoString = record pFilterGroup: PChar; pFilterName: PChar; pFilterAuthor: PChar; pFilterVersion: PChar; end; |
Dieses Record enthält vier Zeiger auf nullterminierte Strings. Die Strings werden nach Ablauf des Plugins an die Host-Anwendung „BVATisch“ übergeben. Sie enthalten die Texte für: „Filtergruppe“, „Name des Filters“, „Entwickler des Filter-Plugins“ und „Version“. |
|
PTFilterKern = ^TFilterKern; TFilterKern = packed array [0..2,0..2] of Single; |
Dieser Typ definiert eine 3x3 Matrix mit Gleitkommawerten für die Übergabe von Parametern an das Plugin. |
|
PTRGBVektor = ^TRGBVektor; TRGBVektor = packed array [0..2] of Single; |
Dieser Typ definiert einen Vektor für die drei Farbanteile Rot, Grün, Blau für die Übergabe einer Farbe als Parameter an das Plugin |
|
TRGB = record r,g,b : pVPAT; end; |
Record mit den drei Farbanteile Rot, Grün, Blau für die Beschreibung einer Farbe. Wird von den CVB-Funktionen genutzt. |
|
TPixel = record wert : Byte; todel : Boolean; Bereich : Longint; si : Byte; end; |
Dieses Record enthält Informationen für einen Pixel des Bildes: Wert: Farbwert (0=schwarz, 255=weiß) Todel: Gibt an, ob der Pixel als Startpunkt für einen Bereich gültig ist (todel=true: ungültig) Bereich: Speichert zu welchem Bereich der Pixel gehört Si: Speichert die Intensitätsschwelle des lokalen Bildfensters, in dem der Pixel liegt |
|
TBild = array of array of TPixel; |
Dieses mehrdimensionale Array speichert alle Pixel des zu bearbeitenden Bildes |
|
TTicks = record summe, gradient, grau, markieren, wachsen, verschmelzen, schwellen : Cardinal end;
|
Dieses Record enthält die jeweils vergangenen Ticks der einzelnen Rechenoperationen des Plugins und ermöglicht so eine genaue Zeitmessung der einzelnen Schritte. |
|
TStartpunktPtr = ^TStartpunkt; TStartpunkt = record x,y : Longint; wert : Byte; si : Byte; prev, next : TStart punktPtr; end; |
Diese Typen werden für die Startpunkt-Liste benutzt. In der doppelt verketteten Liste (prev, next) werden jeweils einzelne Pixel (x,y), deren Farbwert (wert) und die zugehörige Intensitätsschwelle (si) festgehalten. |
|
TGradient = ( Sobel, PseudoLaplace, Roberts); |
Dieser Typ enthält, welcher Gradienten-Operator für die Randpunkterkennung benutzt werden soll |
|
TBereich = record FarbwertSumme : Longint; AnzPunkte : Longint; id : Longint; Wachsbar : Boolean; First, Last : TStart punktPtr; end; |
Dieser Typ definiert die Parameter für einen Bereich im Bild: FarbwertSumme: Enthält die Summe der Farbwerte aller Pixel in dem Bereich AnzPunkte: Gibt an, wie viele Pixel in dem Bereich sind Id: Eindeutige Bereichsnummer (Kennung) Wachsbar: Flag, das angibt, ob der Bereich noch weiter wachsen kann (also noch nicht zugeordnete Bildpunkte angrenzen) First/Last: Ist ein Zeiger auf den Anfang/Ende einer Liste mit Startpunkten des Bereiches (wird bei der Verschmelzung verwendetet) |
4.3.2.2 Die Zeigerstruktur der Startpunkt- und Bereichslisten
Bei den hier eingesetzten Listen handelt es sich zum einen um doppelt verkettete lineare Listen. Diese Listen sind über einen Zeiger „ListPtr“ (kurz: „First“), der auf das erste Element zeigt, zu erreichen. Außerdem wird noch ein zusätzlicher Zeiger auf das letzte Element („Last“) eingesetzt, da dies das Einfügen eines Elements am Ende der Liste vereinfacht. In dieser Listenform werden die Startpunkte bei der Initialpunktzerlegung gespeichert, sowie die neu hinzugekommenen Randpunkte beim Wachstumsverfahren.
Das folgende Beispiel zeigte den Aufbau und die Verkettung der eingesetzten dynamischen Liste. Die eigentlichen Nutzdaten, die in der Liste gespeichert werden sollen, sind unter dem Namen „Data“ zusammengefasst.
► Beispiel zum Einfügen eines neuen Elements am Anfang der Liste:
|
|
Dies ist die Ausgangsliste. Hier soll am Anfang ein neues Element eingefügt werden. |
|
|
Zuerst wird ein neues Element erstellt, dessen Zeiger beide zunächst auf „nil“ zeigen. |
|
|
Als nächster Schritt zeigt das neue Element auf das alte erste Element. |
|
|
Jetzt muss das alte erste Element auf das neue Element zeigen. |
|
|
Als letzter Schritt muss der „ListPtr“ auf das neue erste Element zeigen! |
Neben den doppelt-verketteten Listen kommen außerdem dynamische Arrays zum Einsatz. Diese haben den Vorteil, dass das Durchlaufen der Liste via Index schneller und einfacher realisiert werden kann, da alle Elemente direkt hintereinander im Speicher liegen. Diesen Vorteil nutzt die Bereichsliste aus, die als dynamisches Array realisiert wurde. Nachdem alle Startpunkte gefunden wurden, wird jeder Bereich in dem Array gespeichert. Werden beim Verschmelzvorgang Bereiche zusammengelegt, wird einer der beiden Bereiche als ungültig markiert, da ein „echtes“ Löschen aus dem Array ein Umkopieren zur Folge hätte und zu langsam sein würde.
► Die „Array-Liste“ der Bereiche hat folgenden Aufbau:
4.3.3 Verwendete globale Variablen
Um die Geschwindigkeit zu optimieren und die Programmierung zu vereinfachen sind die wichtigsten Variablen global im Programmcode zu erreichen. Die folgende Liste gibt eine Übersicht. Die Namen beginnen alle mit „g_“ zur Kennzeichnung, dass sie global sind:
|
Variablennamen |
Beschreibung |
|
g_strStatus : String; |
String für die Textausgabe des Plugins. Er wird von Plugin gesetzt und nach Ablauf des Filters von der Host-Anwendung angezeigt. |
|
g_ticks : TTicks; |
Speichert die vergangenen Ticks der einzelnen Rechenschritte des Filters für die Zeitmessung. |
|
g_bild : TBild; |
Speichert jeden Pixel des Bildes, inkl. Farbwert, Bereich-ID, Si-Wert und Gültigkeit |
|
g_breite, g_hoehe : Longint; |
Enthält die Breite und Höhe des Bildes |
|
g_first, g_last : TStartpunktPtr; |
Enthält den Zeiger auf Anfang/Ende der Startpunktliste |
|
g_bereiche : array of TBereich; |
Speichert die Liste aller Bereiche in einem Array |
4.4 Programmorganisationsplan
4.4.1 Aufbau und Struktur der DLL
In der Anwendung „BVATisch“ kann nach Laden/Grabben eines Bildes dieses Plugin mit der Filterfunktion für das Region Growing aufgerufen werden. Damit die Anwendung mit dem Plugin kommunizieren kann, besteht eine definierte Schnittstelle zur Kommunikation.
Das Plugin ist dabei als Windows Dynamic Link Library (DLL) abgelegt und exportiert folgende Funktionen:
|
Funktionsname: |
Beschreibung |
|
function ImageProcess( FirstImageSrcPtr : Pointer; SecondImageSrcPtr: Pointer; ZielImage : TCVImage; FilterKern : TFilterKern; RGBVektor1 : TRGBVektor; RGBVektor2 : TRGBVektor ): Longint; stdcall;
|
Diese Funktion führt die eigentliche Filteroperation aus. Das Eingabebild wird an das Plugin übergeben. Das Ergebnis via Referenz zurückgegeben. |
|
function GetInfo: TInfoString; stdcall; |
Diese Funktion liefert Versionsinfos zum Plugin und wird im MemoFeld des zugeordneten MDI-Childs dargestellt. |
|
function GetStatusString: PChar; stdcall; |
Diese Funktion liefert zusätzliche Infos aus „ImageProcess" an die Hostanwendung BVATisch. |
4.4.2 Funktionsabhängigkeiten untereinander
Das folgende Diagramm beschreibt die Abhängigkeiten der wichtigsten Funktionen des Plugins. Außerdem erkennt man von links nach rechts betrachtend die Aufrufreihenfolge im Programm:
4.5 Programmtests und Ergebnisse
4.5.1 Programmtests mit kritischen Optionen
Im Folgenden werden die wichtigsten Anwendungsfälle und mögliche Fehlerquellen getestet:
|
Testfall |
Erwartetes Ergebnis |
Erzieltes Ergebnis |
|
Aufruf des Plugins, ohne voriges Laden und Auswählen eines primären Bildes |
Fehlermeldung mit Hinweis, dass kein Bild ausgewählt wurde. |
Es wird eine Fehlermeldung ausgegeben: „ImageProcess() – Bitte ein primäres Bild auswählen |
|
Aufruf des Plugins mit einem 1x1 Pixel großen Bild |
Das Bild soll nach Graustufenumwandlung zurückgegeben werden |
Das Bild wird nach Graustufenumwandlung zurückgegeben |
|
Aufruf des Plugins mit einem 24-Bit RGB-Farbbildes |
Umwandlung in Graustufen und anschließende Umwandlung durch das Region Growing Verfahren |
Umwandlung in Graustufen und anschließende Umwandlung durch das Region Growing Verfahren |
|
Aufruf des Plugins mit einem 8-Bit Graustufenbildes |
Umwandlung durch Region Growing in unterschiedliche Bereiche |
Umwandlung durch Region Growing in unterschiedliche Bereiche |
|
Aufruf des Plugins mit einem einfarbigen Bildes |
Das Eingabebild wird als Graustufenbild zurückgeliefert |
Das Eingabebild wird als Graustufenbild zurückgeliefert |
|
Aufruf des Plugins mit ungültigen Filterparametern |
Die ungültigen Filterparameter werden autom. an die zulässigen Grenzen angepasst. Anschließend wird das Region Growing Verfahren gestartet. |
Die ungültigen Filterparameter werden autom. an die zulässigen Grenzen angepasst. Anschließend wird das Region Growing Verfahren gestartet. |
4.5.2 Ergebnisse und Beispiele des Filters
4.5.2.1 Beispiele zum Finden von Randpunkten
Die Anwendung unterschiedlicher Gradientenoperatoren:
Originalbild:
RGB-Farbbild: Das grüne Rechteck ist ein deutlich abgegrenztes Objekt, die Büroklammer liegt vor zwei Hintergründen (weiß und hellgrün) und wirft Schatten. Dadurch entstehen weiche Farbverläufe an den Kanten, die unterschiedlich bearbeitet werden. Außerdem ist sowohl das Rechteck als auch der hellgrüne Hintergrund am unteren Bildrand nicht einfarbig, sondern durch ein leichtes Störmuster gefüllt.
|
Bild, das nur die Randpunkte zeigt: |
|
Zielbild als Ergebnis des gesamten Wachstumsverfahrens: |
|
Sobel-Operator: |
|
|
|
|
Man sieht links einen deutlichen, dicken Rand. Der Sobel Operator markiert viele Punkte. Allerdings werden auch innerhalb des Rechtecks viele Punkte markiert (Bildstörungen), obwohl dies keine Randpunkte sind. Durch den dicken Rand, dessen Punkte nicht als Bereichs-Startpunkte zulässig sind, wird das Rechteck im Gesamtverfahren gut erkannt. Außerdem wird die Büroklammer, die voller Randpunkte ist, im Gesamtverfahren zu wenigen Bereichen zusammengefasst. |
|
|
Pseudo-Laplace-Operator: |
|
|
|
|
Man sieht links, dass alle Objekte durch einen relativ feinen Rahmen abgegrenzt wurden. Jedoch sind innerhalb des Randes mehrere übrig gebliebene Punkte, die nicht zum Rand zählen. Dadurch können Bereichs-Startpunkte auf den Rand des Objekts fallen, was im Gesamtverfahren zu kleinen unschönen Pixel/Bereichen am Rande des Objekts führen kann (wie rechts am Rechteck zu erkennen). Die kleinen Störungen innerhalb der Objekte bzw. im hellgrünen Hintergrund werden aber richtigerweise ignoriert. |
|
|
Roberts-Operator: |
|
|
|
|
Wie links zu erkennen ist, erzeugt auch der Roberts-Operator einen sehr feinen Rand an den Kanten der Objekte, der nicht durch störende Bildpixel unterbrochen ist wie beim Pseudo-Laplace-Operator. Das Rechteck kann (wie rechts zu sehen) eindeutig als Bereich erkannt werden. Die Büroklammer ist aufgrund des dünneren Rands in mehr Bereiche unterteilt als beim Sobel-operator. Jedoch nicht ganz so stark wie beim Pseudo-Laplace Operator, wo durch störende Bildpunkte auch im Randbereich des Objekts einzelne kleine Bereiche entstehen. |
|
4.5.2.2 Beispiel für den Einfluss unterschiedlicher lokaler Intensitätsschwellen
Bei der Bestimmung der Intensitätsschwellen wird auf lokale Bildfenster (Unterteilung des Bildes in Kacheln) zurückgegriffen, um z.B. den Einfluss unterschiedlicher Hintergründe im Bild zu kompensieren. Die folgenden Bilder demonstrieren die Wichtigkeit der Einteilung, wenn Objekte mit geringer Farbabweichung zum Hintergrund noch erkannt werden sollen:
|
Originalbild: |
|
|
|
|
Das Bild besteht aus zwei Objekten die auf weißem Hintergrund liegen. Das obere Objekt hebt sich nur schwach vom Hintergrund ab, dass untere Objekt hingegen sehr deutlich. |
|
|
Unterteilung in 1x1 Kachel: |
|
Unterteilung in 2x2 Kachel: |
|
|
Wählt man für die Intensitätsschwellen nur eine Kachel im Bild aus, wird die Schwelle aus dem Durchschnittswert des gesamten Bildes berechnet. Das helle Objekt kann sich somit nicht mehr vom Hintergrund absetzen und verschwindet vollständig, wie links zu sehen ist. Unterteilt man das Bild jedoch beispielsweise in 4 Kacheln (rechts zu sehen), so wird in jedem Quadranten ein eigener Schwellwert für die Intensität bestimmt. Das obere helle Objekt liegt also in einer weißen Kachel mit geringerer lokalen Intensitätsschwelle (Si –Wert), so dass es sich vom weißen Hintergrund absetzen kann und als eigener Bereich erkannt wird. |
|
4.5.2.3 Beispiele zur Initialpunktberechnung
Die erste Phase des Wachstumsverfahrens besteht darin, für jeden Bereich einen Startpunkt zu finden. Nachdem Mit Hilfe der Gradientenoperatoren alle Randpunkte im Bild ausgeschlossen wurden, gilt es passende Punkte zu finden. Dabei steht zunächst jeder Punkt als Startpunkt zur Verfügung (für Geschwindigkeitsoptimierung nur jeder zweiter, dritter, … i-ter Punkt). Anschließend werden doppelte Punkte in einem Bereich wie oben erklärt entfernt, wenn sie auf einem Weg parallel zu den Achsen verbunden werden können. Welche Startpunkte dabei übrig bleiben, wird im Folgenden an zwei Beispielen demonstriert:
Mehrere Rechtecke, schräge Lage:
Man erkennt deutlich, dass jedem Objekt mindestens ein Punkt zugeordnet ist. In den drei unteren Rechtecken sind z.B. jeweils zwei Punkte gesetzt, obwohl die Farbwerte zwischen den Punkten nahezu identisch sind. Dies liegt an der schrägen Lage des Rechtecks zu den Koordinatenachsen. Der Versuch von einem inneren Punkt zu dem anderen zu kommen scheitert, weil dies auf geraden Wegen parallel zum Achsensystem nicht möglich ist, ohne den Toleranzbereich der Farbwerte zu verlassen. Dies wäre nur durch eine direkte, lineare Verbindung möglich, die aus Performance Gründen allerdings nicht unterstützt wird. Beim späteren Verschmelzvorgang werden die entstandenen Bereiche beider Punkte jedoch wieder zusammengefasst.
Kugel und Pfeil, Farbverläufe:
Auch bei diesem Bild kann man erkennen, dass jedem Bereich mindestens ein Startpunkt zugeordnet wurde. Außerdem wird deutlich, dass aufgrund des vorigen kantenorientierten Verfahren keine Randpunkte gewählt wurden. Innerhalb der Objekte sind mehrere Punkte mit ähnlichen Farbwerten gesetzt, je nach Änderungen der Farbverläufe.
4.5.2.4 Beispiele zum Bereichswachstum
Beim Bereichswachstumsverfahren kann wie weiter oben erläutert zwischen zwei verschiedenen Modi unterschieden werden: „Fastmode On/Off“. Ist „Fastmode“ auf „On“ eingestellt, kann ein Bereich in einem Durchlauf bis zur Toleranzgrenze wachsen, erst dann kommt der nächste an die Reihe, der wiederum bis an seine Toleranzgrenze wächst usw. Ist „Fastmode“ ausgeschaltet, wächst jeder Bereich bei einem Durchlauf nur um einen Pixel am Rand, dann ist der nächste Bereich dran. Die folgenden Bilder zeigen die Unterschiede der beiden Verfahren und demonstrieren jeweilige Vor- und Nachteile:
|
Originalbild: |
|
|
|
|
Das Bild ist gekennzeichnet durch einen grünen Hintergrund im unteren Bereich, der durch die Beleuchtung bei der Aufnahme nicht einfarbig, sondern in einem Farbverlauf von hellen Grüntönen auf der linken Seite zu etwas dunkleren Grüntönen auf der rechten Seite variiert. |
|
|
Beispiel 1: „Fastmode On“ |
|
Beispiel 1: „Fastmode Off“ |
|
|
Wie links im Bild deutlich zu erkennen ist, wurde der Farbverlauf im ursprünglich grünen Hintergrund zu einem großen Bereich zusammengelegt, da der Bereich beim Wachsen bis zur Toleranzgrenze vordringen kann und übrige Startpunkte verschmilzt. Im rechten Bild ist „Fastmode“ jedoch ausgeschaltet und jeder Startpunkt im grünen Hintergrund kann nacheinander ein bisschen wachsen. So ändert sich jeweils die durchschnittliche Intensität des lokalen Bereichs, bis die einzelnen Bereiche aneinandergrenzen. Sie können aufgrund der lokalen Intensität nicht mehr miteinander verschmolzen werden. |
|
|
Beispiel 2: „Fastmode On“ |
|
Beispiel 2: „Fastmode Off“ |
|
|
Dieses Beispiel zeigt ebenso, die Unterteilung in mehrere Bereiche in einem Farbverlauf (rechts im Pfeil). Außerdem wird eine Schwäche des „Fastmode“ im linken Bild deutlich: Im Pfeil entsteht eine kleine Gruppe von grauen Pixeln, die eigentlich dem umliegenden Bereich zugeordnet werden sollte. Dies entsteht, wenn „einsame Pixel“ eine zu hohe Intensität für den umliegenden Bereich haben und sich selber als Bereich nicht viel weiter ausdehnen können. |
|
Die folgenden Bilder demonstrieren den Einfluss der Stärke der Wachstumstoleranz der einzelnen Bereiche:
|
Wachstumstoleranz: 4 Erhöhung: 2 |
|
Wachstumstoleranz: 20 Erhöhung: 8 |
|
|
Im linken Bild ist die Toleranz so klein, dass der Farbverlauf im unteren Hintergrund in mehrere Bereiche unterteilt erscheint. Wird die Toleranz erhöht, wie im rechten Bild zu sehen, wird der ganze Hintergrund zusammengefasst. Auch das innere der schwarzen Kugel wurde stärker zusammengefasst. |
|
|
Wachstumstoleranz: 40 Erhöhung: 20 |
|
Wachstumstoleranz: 100 Erhöhung: 40 |
|
|
Diese beiden Bilder veranschaulichen den Wachstumsvorgang bei noch größeren Werten für die Toleranz. Es werden immer mehr ähnliche Regionen in die Bereiche eingebunden, so dass mehr und mehr Details verloren gehen und nur die eigentlichen Objekte separiert werden. |
|
4.5.2.5 Beispiele zum Verschmelzen
Die untenstehenden Bilder demonstrieren das abschließende Verschmelzen von Bereichen nach dem Wachstumsverfahren. Es werden nur benachbarte Bereiche zusammengefasst, wenn eine bestimmte Toleranz der Farbunterschiede eingehalten wird.
|
Region Growing ohne Verschmelzen der Bereiche: |
|
Region Growing und anschließendes Verschmelzen der Bereich: (Toleranz=100) |
|
|
Das linke Bild zeigt wie ein Farbverlauf beim Wachsvorgang in mehrere Bereiche unterteilt wurde. Im rechten Bild wurde anschließend noch ein zusammenfassen (Verschmelzen) ähnlicher, benachbarter Bereiche mit hoher Toleranz durchgeführt. Dadurch werden die einzelnen Bereiche des Farbverlaufs zu einem Bereich kombiniert. |
|
5. Anhang
5.1 Quellcode des entwickelten Filters
Quellcode Download (Delphi .dpr Datei)
Kommentare 0
Neuen Kommentar schreiben: