Ketten-Kode-Bilder

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Ketten-Kode-Bilder (Chain Code Pictures) sind Bilder, die mit Hilfe formaler Grammatiken erzeugt werden. Ein von einer solchen Grammatiken generiertes Wort wird hierbei jeweils als genau ein Bild interpretiert, indem die einzelnen Symbole als Richtungen gedeutet werden und damit ein Zeichnen in einem Koordinatensystem beschrieben wird.

Grundlagen[Bearbeiten | Quelltext bearbeiten]

Gegeben sei das ganzzahlige Koordinatensystem und für jeden Punkt seine Nachbarpunkte mit

, , , ,

wobei , , bzw. intuitiv für den oberen (up), unteren (down), rechten (right) bzw. linken (left) Nachbarpunkt stehen.

Die Menge von Richtungen sei mit definiert.

Weiterhin versteht man unter einer Einheitsstrecke die Strecke, die durch zwei benachbarte Punkte verbunden wird. Das heißt, für jeden Punkt und jede Richtung gibt es eine Strecke zwischen und (diagonale Strecken sind damit ausgeschlossen). Eine Einheitsstrecke wird mit dem Punktepaar repräsentiert, wobei und geometrisch gesehen gleich sind.

Ein (einfaches) Bild sei eine endliche Menge von Einheitsstrecken und die Menge aller Punkte von .

Man nennt das Tripel , wobei ein einfaches Bild ist und Anfangs- und Endpunkt heißen, gezeichnetes Bild.

Zwei einfache Bilder und sind genau dann äquivalent – man schreibt –, wenn zwei Zahlen existieren, sodass dann und nur dann, wenn . Analog heißen zwei gezeichnete Bilder und genau dann äquivalent – man schreibt –, wenn zwei Zahlen existieren, sodass dann und nur dann, wenn und , . Intuitiv sind Bilder also bis auf Verschiebung im Koordinatensystem gleich. Wie man leicht zeigen kann, sind und Äquivalenzrelationen über der Menge aller einfachen bzw. gezeichneten Bilder.

Man bezeichnet ein einfaches Bild als (einfaches) Unterbild des einfachen Bildes , wenn ein einfaches Bild mit und existiert.

Ein Bild ist ein (einfaches) Ketten-Kode-Bild, wenn eine endliche Folge von Einheitsstrecken mit und ,, existiert, sodass gilt. Folglich ist ein Ketten-Kode-Bild stets zusammenhängend.

Generierung durch formale Grammatiken[Bearbeiten | Quelltext bearbeiten]

Ketten-Kode-Bilder und Wörter[Bearbeiten | Quelltext bearbeiten]

Auf Grund der Definition von Ketten-Kode-Bildern können jene mit Wörtern (Ketten-Kodes bzw. chain codes) über assoziiert werden, indem einem Ketten-Kode-Bild mit der Folge und , , das Wort zugewiesen wird.

Andererseits weist man jedem Wort ein gezeichnetes Ketten-Kode-Bild (drawn chain code picture) induktiv wie folgt zu:

  • falls , dann
  • falls , , und , dann

Mit ist das einfache Ketten-Kode-Bild (basic chain code picture) von .

Nun können mit einer formalen Grammatik Wörter erzeugt und als Ketten-Kode-Bilder interpretiert werden. Die Menge aller von generierten Bilder sei bzw. , wobei die von erzeugte Sprache (siehe Von G erzeugte Sprache) ist – man nennt sie auch Ketten-Kode-Bild-Sprache.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Sei eine gegebene formale Grammatik. Die von erzeugte Sprache ist

.

Die Menge der von erstellten Bilder ist in der nachstehenden Abbildung dargestellt:

Die Ketten-Kode-Bild-Sprache . Der Anfangspunkt eines Bildes ist mit einem grünen Kreis gekennzeichnet und der Endpunkt mit einem orangen Rechteck.

Man erhält also abzählbar viele Stapel beliebiger aber fester Höhe, die aus Quadraten der Kantenlänge bestehen.

Hierarchie der Ketten-Kode-Bild-Sprachen[Bearbeiten | Quelltext bearbeiten]

Analog zu formalen Sprachen wird eine Ketten-Kode-Bild-Sprache regulär oder kontextfrei oder monoton (bzw. kontextsensitiv) oder rekursiv aufzählbar genannt, wenn es eine reguläre oder kontextfreie oder monotone (bzw. kontextsensitive) oder rekursiv aufzählbare formale Grammatik gibt, sodass gilt (siehe Chomsky-Hierarchie). Mit , , und bezeichnet man die Mengen (auch Familien) aller regulären, kontextfreien, monotonen und rekursiv aufzählbaren Ketten-Kode-Bild-Sprachen.

Eine wichtige Erkenntnis ist die Gültigkeit der Inklusionen bzw. Gleichheit . Somit betrachtet man in der Tat nur drei echte Familien.

Entscheidungsprobleme für Ketten-Kode-Bild-Sprachen[Bearbeiten | Quelltext bearbeiten]

Klassische Entscheidungsprobleme[Bearbeiten | Quelltext bearbeiten]

Wie für formale Sprachen lassen sich in gleichartiger Weise auch für Ketten-Kode-Bild-Sprachen wichtige Entscheidungsprobleme formulieren:

Bildproblem (auch Mitgliedsproblem)

  • Gegeben ist eine formale Grammatik und ein Ketten-Kode-Bild .
  • Gilt , gibt es also ein Wort , sodass wahr wird?

Das Bildproblem ist für kontextfreie formale Grammatiken entscheidbar und für kontextsensitive formale Grammatiken unentscheidbar. Dabei ist dieses Problem bereits für reguläre formale Grammatiken NP-vollständig.

1. spezielles Bildproblem

  • Gegeben ist eine formale Grammatik und ein Ketten-Kode-Bild .
  • Ist die Menge endlich?

Man fragt also danach, ob es endlich bzw. unendlich viele Wörter gibt, die das Ketten-Kode-Bild erzeugen. Dieses Problem ist, wie das Bildproblem, für kontextfreie formale Grammatiken entscheidbar und für kontextsensitive formale Grammatiken unentscheidbar.

2. spezielles Bildproblem

  • Gegeben ist eine formale Grammatik und ein Ketten-Kode-Bild .
  • Hat die Menge genau ein Element?

Somit wird gefragt, ob das Ketten-Kode-Bild von genau einem Wort aus generiert wird. Dieses Problem ist abermals für kontextfreie formale Grammatiken entscheidbar und für kontextsensitive formale Grammatiken unentscheidbar.

Unterbildproblem

  • Gegeben ist eine formale Grammatik und ein Ketten-Kode-Bild .
  • Gibt es ein Ketten-Kode-Bild , sodass ein Unterbild von ist?

Das Unterbildproblem ist für kontextfreie formale Grammatiken entscheidbar und für kontextsensitive formale Grammatiken unentscheidbar.

Universelles Unterbildproblem

  • Gegeben ist eine formale Grammatik und ein Ketten-Kode-Bild .
  • Ist ein Unterbild jedes Ketten-Kode-Bildes ?

Für reguläre formale Grammatiken ist das universelle Unterbildproblem entscheidbar.

Leerheitsproblem

  • Gegeben ist eine formale Grammatik .
  • Ist die Menge leer?

Das Leerheitsproblem ist für kontextfreie formale Grammatiken entscheidbar und für kontextsensitive formale Grammatiken unentscheidbar.

Endlichkeitsproblem

  • Gegeben ist eine formale Grammatik .
  • Ist die Menge endlich?

Das Endlichkeitsproblem ist für kontextfreie formale Grammatiken entscheidbar und für kontextsensitive formale Grammatiken unentscheidbar.

Äquivalenzproblem

  • Gegeben sind zwei formale Grammatiken und .
  • Gilt , erzeugen also beide Grammatiken über ihre Wörter dieselben Ketten-Kode-Bilder?

Das Äquivalenzproblem ist schon für reguläre formale Grammatiken und unentscheidbar.

Man beachte, dass auf Grund der in Abschnitt Hierarchie der Ketten-Kode-Bild-Sprachen festgestellten Inklusionen für jedes der genannten Probleme mit der formalen Grammatik und gilt:

  • wenn für mit entscheidbar ist, ist für eine formale Grammatik mit , und ebenso entscheidbar.
  • wenn für mit unentscheidbar ist, ist für eine formale Grammatik mit , und gleichfalls unentscheidbar.

Geometrische Entscheidungsprobleme[Bearbeiten | Quelltext bearbeiten]

Zunächst seien einige geometrische Eigenschaften eines Ketten-Kode-Bilds im Nachstehenden definiert:

  • ist eine einfache Kurve, wenn alle Knoten von höchstens den Grad 2 haben.
  • nennt man geschlossene einfache Kurve, wenn alle Knoten von genau den Grad 2 haben.
  • heißt regulär, wenn alle Knoten von den gleichen Grad besitzen.
  • wird Baum genannt, wenn es keine geschlossene einfache Kurve als Teilbild enthält.
  • ist eulersch, wenn alle Knoten von einen graden Grad haben.
  • wird als hamiltonsch bezeichnet, wenn eine einfache Kurve als Teilbild hat, das alle Knoten von enthält.

Untersuchungen haben gezeigt, dass bereits für reguläre formale Grammatiken unentscheidbar ist, ob

  • eine einfache Kurve,
  • eine geschlossene einfache Kurve,
  • ein reguläres Bild,
  • einen Baum,
  • ein eulersches Bild,
  • ein hamiltonsches Bild

beinhaltet.

Hingegen ist für reguläre formale Grammatiken entscheidbar, ob

  • alle Bilder von geschlossene einfache Kurve sind,
  • alle Bilder von Rechtecke sind,
  • ein Rechteck enthält,
  • ein konvexes Bild enthält.

Weiterhin kann für eine kontextfreie formale Grammatiken entschieden werden, ob alle Bilder von Bäume sind.

Verallgemeinerungen[Bearbeiten | Quelltext bearbeiten]

Im Folgenden werden einige (informale) Anmerkungen über Erweiterungen und Verallgemeinerungen von Ketten-Kode-Bildern gemacht, um in gewisser Weise bessere Bilder zu erhalten.

Hinzufügen neuer Richtungen[Bearbeiten | Quelltext bearbeiten]

Ein sicherlich intuitiver Ansatz Ketten-Kode-Bilder zu erweitern, ist das Hinzufügen neuer Richtungen zu den bereits vier bekannten: oben, unten, rechts und links. So können etwa für alle die Nachbarpunkte

, , , ,

ergänzt werden. Entsprechend erhält man die zusätzlichen Richtungen oben rechts (up right), oben links (up left), unten rechts (down right) und unten links (down left), und damit das neue Alphabet .

Die oben stehenden unentscheidbaren Probleme bezüglich des Alphabets bleiben unter dem Alphabet ebenfalls unentscheidbar. Für die entscheidbaren Probleme verhält es sich ähnlich.

Farbige Ketten-Kode-Bilder[Bearbeiten | Quelltext bearbeiten]

Will man farbige Ketten-Kode-Bilder erhalten, so kann das Alphabet wie folgt verändert werden. Statt einfach nur Buchstaben für Richtungen zu verwenden, werden ihnen noch Farben zugewiesen. Sei etwa eine endliche Mengen von Farben. Dann erhalten wir das neue Alphabet mit , das heißt die Buchstaben sind Paare der Form für und .

Auch hier erhält man ähnliche Ergebnisse für die Un- und Entscheidbarkeit der obigen Probleme.

Nicht-zusammenhängende Ketten-Kode-Bilder[Bearbeiten | Quelltext bearbeiten]

Ketten-Kode-Bilder sind stets zusammenhängend. Möchte man nicht-zusammenhängende Ketten-Kode-Bilder zulassen, kann man das Alphabet um zwei Buchstaben erweitern, die gewissermaßen das Ab- und Ansetzen eines Zeichenstifts bedeuten. Das neue Alphabet sei dann .Intuitiv steht für das Absetzen des Stifts und für das Ansetzen. Für ein besseres Verständnis betrachte man das nachstehende von oben abgeänderte Beispiel.

Sei

eine gegebene formale Grammatik. Die von erzeugte Sprache ist

.

Die erzeugten Bilder sehen denen vom obigen Beispiel ähnlich, nur gibt es keine horizontalen Strecken, da genau dort der Stift immer abgesetzt wurde und bei den vertikalen wieder angesetzt wurde:

Die Menge der von erzeugten Bilder. Der Anfangspunkt eines Bildes ist mit einem grünen Kreis gekennzeichnet und der Endpunkt mit einem orangen Rechteck.

Analog zu Ketten-Kode-Bildern kann man auch hier die Familie mit der Typen der Chomsky-Hierarchie aufstellen und erhält

und

.

Bezüglich der oben stehenden Entscheidungsprobleme ist die Situation hier aufgrund des Nicht-Zusammenhangs der Bilder deutlich schlechter.

Generierung durch andere Grammatiken[Bearbeiten | Quelltext bearbeiten]

Eine weitere Möglichkeit Ketten-Kode-Bild-Sprachen zu erzeugen, besteht darin andere Grammatiken zu verwenden. So kann man beispielsweise Lindenmayer-Systeme, Schildkröten-Grammatiken, Matrix-Grammatiken und Collage-Grammatiken für die Generierung von Ketten-Kode-Bildern benutzen.

Je nach Art des verwendeten Grammatik-Typs kann es sein, dass gewisse Bilder von keiner Grammatik eines Typs erzeugt werden können, jedoch von einer Grammatik anderen Typs. Insbesondere kann man zeigen, dass es Ketten-Kode-Bilder gibt, die von formalen Grammatiken aber nicht von Collage-Grammatiken produziert werden.

Literatur[Bearbeiten | Quelltext bearbeiten]