Proseminar WS98/99 Digitale Bildverarbeitung

 

Binärbilder

Johannes Altaner

Vortrag am 4.12.1998

 

Inhaltsverzeichnis:

 

Binärbilder *

 

1 Datenstrukturen von Binärbildern *

1.1 Regionen *

1.2 Datenstrukturen *

1.3 Vergleich der Datenstrukturen *

1.4 Zusammenfassender Überblick *

 

2 Mengenoperationen *

2.1 Definitionen und Veranschaulichung *

2.2 Zusammenhang *

2.3 Nachbarschaft *

 

3 Merkmale *

3.1 Definitionen *

3.2 Anwendungen: *

3.3 Graphische Übersicht *

 

4 Literaturverzeichnis *

 

 

 

 

  1. Datenstrukturen von Binärbildern
  2.  

    1. Regionen
    2. Ein Punkt wird bei einer Region nicht durch seinen Grauwert in einer Matrix, sondern durch die Zugehörigkeit zu einer Menge von Punkten mit gewissen Eigenschaften charakterisiert.

      Wir erhalten hier das Binärbild, indem wir jene Punkte selektieren, deren Grauwert hoch ist.

      Das Binärbild enthält nur eine Region, aber 11 Zusammenhangskomponenten.

      Definition : Eine Region ist eine Menge von Punkten p des Zn.

      Im weiteren gehen wir davon aus, daß eine Region einen Ausschnitt eines zwei- dimensionalen Bildes modelliert, wir betrachten also nur den Fall Dimension n=2.

      Beispiele für Regionen (mit und ohne Überlappung):

      An dem Beispiel rechts wird eine Eigenschaft von Regionen deutlich:

      Sie sind unabhängig voneinander und werden folglich prinzipiell unabhängig bearbeitet.

       

      Bei der Umsetzung auf eine Datenstruktur taucht das Problem der potentiell unbeschränkten Regionen auf. Folgendes Beispiel soll dies veranschaulichen:

      Das Bild links zeigt eine mikroskopische Aufnahme eines Kapillargefäßes, bei dem im oberen und unteren Bildbereich die Zellen zu erkennen sind und in der Bildmitte der blutdurchflossene Teil.

      Für die weitere Verarbeitung benötigt man die Zellbereiche zwischen den Regionen.

      Das Bild rechts zeigt einen vergrößerten Ausschnitt, wobei die Zellwände umrandet sind.

      Da durch die Vergrößerung auch Teile des Gefäßes überdeckt wurden, ist es notwendig, das Ergebnis wiederum zu verkleinern.

      Doch das Ergebnis ist an den Bildrändern beschnitten (links).

      Erwartet hätte man Regionen, wie sie rechts dargestellt sind.

      Verursacht wird das Problem durch die Einschränkung des Ergebnisses auf einen festen Indexbereich. Eigentlich umfaßt das Ergebnis nämlich Punkte, die außerhalb des Bildes liegen, aber nicht gespeichert werden können. Wird nun schließlich die Verkleinerung des Bildes ausgeführt, so fehlen diese Punkte und die Region wird am Bildrand beschnitten. Viele Systeme versuchen das Problem zu umgehen, indem die Region an den Bildrändern logisch fortgesetzt wird.

       

       

       

       

    3. Datenstrukturen
    4. Es bieten sich drei Möglichkeiten an, Regionen im Rechner darzustellen:

      Binärbilder : Die Darstellung erfolgt als Matrix oder Zeilenarray.

      (bit- oder byteweise)

      [[0,0,1,1],[0,1,1,1],[1,1,0,1],[0,0,0,0]]

      Quadtrees : Das Bild wird rekursiv so lange in Quadrate zerlegt, bis die Pixel innerhalb der Quadrate homogen sind.

      Der Baum besteht aus einer Wurzel, die vier Söhne hat, falls das Bild nicht homogen ist. Jeder dieser Söhne hat im inhomogenen Fall wiederum vier Söhne, usw.

      Lauflängenkodierung : Das Bild wird zeilenweise in Sehnen zerlegt.

      Gespeichert werden Tripel (Zeile, Sehnenanfang, Sehnenende).

      Index

      Zeile

      Anfang

      Ende

      0

      0

      2

      3

      1

      1

      1

      3

      2

      2

      0

      1

      3

      2

      3

      3

       

    5. Vergleich der Datenstrukturen
    6. - hinsichtlich Speicherplatzbedarf:

      Die Kodierung als Binärbild benötigt immer konstanten Speicherplatz, der nur abhängig von der Fläche des Bildes ist. Dies ist nur bei kleinen Flächen von Vorteil.

      Bei Quadtrees kann man vereinfachend sagen, daß der Speicherplatzbedarf abhängig von der Anzahl der Knoten ist. Regionen mit einer komplexen Form benötigen mehr Knoten im Baum und somit mehr Speicherplatz. Der worst case ist hier das Schachbrettmuster, da pro Pixel ein Knoten vorhanden ist.

      Bei Lauflängenkodierung ist der Speicherplatzbedarf abhängig von mehreren Faktoren:

      Anzahl der Punkte (Fläche), Form der Region, Komplexität der Form und Orientierung.

      Regionen mit horizontaler Ausdehnung benötigen weniger Speicherplatz als Regionen mit vertikaler Ausrichtung. Wir betrachten die Extremfälle:

      worst case: senkrechte Linie oder Schachbrettmuster

      best case: horizontale Linie

      Normalfall: Quadrat

      Flugzeug?

       

      Mittlerer Speicherbedarf:

      Beispiel

      Binärbild

      Quadtree

      Lauflängen

      Zellen

      333

      1780

      354

      Buchstaben

      425

      2720

      622

      Flugzeug

      90896

      58480

      6856

      Im Falle kleiner Regionen sind Binärbilder und Lauflängenkodierung etwa gleich gut. Quadtrees schneiden hier deutlich schlechter ab.

      Bei der großen Region dagegen ist die Lauflängenkodierung deutlich überlegen. Eindeutiger Verlierer ist hier die Kodierung durch Binärbilder.

      - hinsichtlich Laufzeitkomplexität:

      Wichtig zur Beurteilung der Datenstrukturen ist auch ein Vergleich der Laufzeit der Algorithmen für häufig benötigten Operationen. Man unterscheidet

      Punktoperationen (Test auf Enthaltensein, Setzen eines Punktes und Löschen eines Punktes)

      und Mengenoperationen, die im nächsten Kapitel behandelt werden.

       

      Wir betrachten zuerst den "Test auf Enthaltensein":

      Beim Binärbild gestaltet sich der Test einfach. Es muß nur durch einen Zugriff auf die Bildmatrix geprüft werden, ob der angegebene Punkt zum Vordergrund gehört. Man erhält eine konstante Laufzeitkomplexität.

      Bei Lauflängenkodierung ist entscheidend, daß die Sehnen aufsteigend sortiert und disjunkt sind. Dies erlaubt einen Test mit Bisektion. Hierbei werden die zu untersuchenden Sehnen in zwei Bereiche aufgeteilt, wobei für jeden getrennt geprüft wird, ob der Punkt enthalten sein kann. Liegt für den Test nur eine Sehne vor, so geschieht dies durch einen Intervalltest. Bei mehreren Sehnen wird geprüft, ob sich der Punkt zwischen dem Startpunkt der ersten Sehne und dem Endpunkt der letzten Sehne befindet. Wenn diese Bedingung erfüllt ist, werden die zugehörigen Sehnen rekursiv aufgeteilt bis alle Tests fehlschlagen oder der Punkt in genau einer Sehne enthalten ist. Da bei jeder Aufteilung der Sehnen deren Anzahl halbiert wird, ergibt sich eine logarithmische Komplexität bezüglich der Anzahl der Sehnen.

      Der Test auf Enthaltensein ist bei Quadtrees rekursiv, wie alle Operationen.

      Für die Komplexität dieser Prozedur ist die Höhe des Baumes relevant, da entlang eines Pfades von der Wurzel zu den Blättern entschieden werden kann, ob ein Punkt im Baum enthalten ist. Es ergibt sich eine logarithmische Komplexität zur Basis 4.

       

       

      Nun zur Laufzeitkomplexität der Vereinigungsmenge:

      Die Bilder werden im folgenden mit X und Y bezeichnet. Ein gesetzter Punkt habe die Farbe Schwarz, ein nicht gesetzter sei weiß.

      Ein Algorithmus für Binärbildkodierung ist leicht gefunden: punktweise Und-Verknüpfung jedes Punktes des Bildes X mit seinem Äquivalent in Y. Dies ergibt eine lineare Abhängigkeit von der Höhe und Breite des Bildes, d.h. von der Fläche.

      Bei Quadtrees ist der Algorithmus wieder rekursiv:

      Die Bilder X und Y werden rekursiv in vier Quadrate zerlegt. Betrachte man jetzt jeweils eines dieser Quadrate in X und Y:

      Ist mindestens eines (X oder Y) homogen schwarz, ist das Ergebnisquadrat auch schwarz.

      Sind beide (X und Y) homogen weiß, ist das Ergebnisquadrat weiß.

      Tritt keiner dieser Fälle ein, wird das Quadrat in weitere vier Quadrate zerlegt.

      Die Laufzeitkomplexität bei Quadtrees ist also abhängig von der Anzahl inhomogen gefärbter Quadrate (Knoten) in (X È Y).

       

       

      Bei Lauflängen benötigt man zwei Prozeduren: Mischen und Packen.

      Mischen: Die Sehnen in X und Y, die sich in der gleichen Zeile befinden, werden

      hintereinander in eine Liste geschrieben (also nach Zeilennummern sortiert).

      Packen: Ist das Ende einer Sehne ³ dem Anfang der nächsten Sehne werden die zwei

      Sehnen zu einer neuen Sehne zusammengepackt.

      Da das Mischen zweier sortierter Listen keinen nennenswerten Aufwand darstellt, ist dieser vernachlässigbar.

      Die Laufzeitkomplexität bei Lauflängenkodierung ist also abhängig von der Summe der Anzahl der Sehnen in X und Y.

       

       

       

       

       

    7. Zusammenfassender Überblick

    Binärbild: + konstante Laufzeitkomplexität

    + beliebig komplexe Regionen

    - benötigt sehr viel Speicher bei großen Bildern

    mit wenig Inhalt

    Lauflängen: + maximale Größe praktisch nicht beschränkt

    + benötigt im Mittel wenig Speicherplatz

    - versagt bei Rauschen (Schachbrettmuster)

    Quadtree: ähnlich wie Lauflängen, aber deutlich mehr Speicherbedarf und schlechteres Laufzeitverhalten

     

     

     

  3. Mengenoperationen
  4.  

    1. Definitionen und Veranschaulichung
    2. Vereinigungsmenge:

       

       

      Schnittmenge:

       

       

      Mengendifferenz:

       

      Komplement:

      Bei der Verarbeitung von Regionen ist es sinnvoll, ein Flag "is_complement" einzuführen.

      Nun kommen uns die Eigenschaften der Mengenoperationen zugute. Es läßt sich nämlich ein Mengenausdruck, in dem Operanden komplementiert sind, so umformen, daß die Komplementoperation nicht explizit ausgeführt werden muß.

      Auf der linken Seite der Tabelle stehen auszuwertende Ausdrücke, die gemäß den Gesetzen der Mengenlehre umgeformt werden können. Auf diese Weise erhält man Ausdrücke, bei denen die Komplementoperation auf keinen der Operanden angewandt werden muß. Komplementiert wird nur gegebenenfalls das Ergebnis. Dieses Prinzip nennt man "lazy evaluation".

       

      Hilfsoperation:

      Translation:

      Translation einer Region um einen Punkt nach rechts

       

       

       

    3. Zusammenhang
    4. Regionen wurden als "Mengen von Punkten" definiert. Dies ist eine sehr abstrakte Definition, die wenig mit dem intuitiven Eindruck zu tun hat, den man bei der Betrachtung von Bildern gewinnt.

      Der Mensch sieht nicht eine Menge von Punkten, sondern zusammenhängende Bereiche, die im weiteren Zusammenhangskomponenten genannt werden.

      Die beiden Bilder zeigen also jeweils eine Region, aber jeweils mit vielen Zusammenhangs- komponenten.

       

    5. Nachbarschaft

    Die horizontal und vertikal benachbarten Pixel werden 4er Nachbarn genannt.

    Zusammen mit den diagonal angrenzenden Pixeln bilden sie die 8er Nachbarn.

    Der Grund für die Unterscheidung liegt in der unterschiedlichen Betrachtung von Vorder- und Hintergrund.

    Betrachte man folgende diagonale Trennlinie (Schwarz stellt den Vordergrund dar):

    Ist diese diagonale Linie zusammenhängend?

     

    Die Linie (Vordergrund) ist nur in der 8er Nachbarschaft zusammenhängend.

    Die zwei weißen Bereiche (Hintergrund) links und rechts von der Trennlinie sollen nicht zusammenhängend sein. Deshalb muß für den Hintergrund die 4er Nachbarschaft gewählt werden.

    Aus diesem Grund wird für die Berechnung des Zusammenhangs die 8er Nachbarschaft für den Vordergrund und die 4er Nachbarschaft für den Hintergrund gewählt.

     

  5. Merkmale
  6. charakterisieren Position, Größe oder Form

     

    1. Definitionen
    2. Fläche: F(R) = |R|

      ist die Anzahl der Punkte

       

       

      Schwerpunkt:

      ist Summe aller Koordinaten (getrennt nach Zeile und Spalte) geteilt durch die Fläche

       

       

       

      Momente: Radien ( und ) und Orientierung ( )

       

       

       

       

      Formmerkmale:

       

      Kompaktheit:

      Verhältnis Fläche : Umfang

      (normiert auf Kreis = 1, sonst kleiner)

       

       

       

      Konvexität:

      Abweichung von der konvexen Hülle

       

       

       

      Anisometrie:

      "Langgestrecktheit" des Objekts

      (Kreis =1, sonst größer)

       

       

       

      Rundheit:

       

       

    3. Anwendungen:
    4.  

       

      Darstellung von Regionen durch die äquivalenten Ellipsen

       

       

       

       

      Auswahl von Regionen mit einer Orientierung im Bereich von 50° bis 80°

       

       

    5. Graphische Übersicht

    Verhalten von Kompaktheit und Rundheit bei Ellipsen und wachsender Anisometrie

     

    Verhalten von Kompaktheit und Rundheit bei Quadraten und untersch. Orientierung

     

    Verhalten von Kompaktheit, Rundheit, Konvexität bei einem Donut mit wachsendem Loch

     

    Verhalten von Kompaktheit, Rundheit, Anisometrie, Konvexität bei Kreisen mit einer Konturstörung (Nadel der Breite 1) wachsender Größe

  7. Literaturverzeichnis

Binärbildverarbeitung in C++, Wolfgang Eckstein, 25.4.1997

 


Die HALCON-Programme des Vortrags:  vortrag.zip (161 KB)

 

Das Ganze als PostScript-Datei: ausarbeitung.ps.gz (970 KB)

 

Das Ganze als Word97-Dokument: ausarbeitung.doc (632 KB)

 

Beschwerden / Anregungen: mailto:altaner@in.tum.de