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

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

Ketten-Kode-Bilder und Wörter

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

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

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

Klassische Entscheidungsprobleme

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

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

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

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

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

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

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