Chain Code Pictures

Ketten-Kode-Bilder (Chain Code Pictures) sind Bilder, die in erster Linie mit Hilfe von formalen Grammatiken erzeugt werden. Die von solchen Grammatiken generierten Wörter werden hierbei jeweils als genau ein Bild interpretiert, indem die einzelnen Buchstaben als Richtungen gedeutet werden und damit ein Zeichnen in einem Koordinatensystem beschrieben wird.

Grundlagen

Gegeben sei das ganzzahlige Koordinatensystem $\mathbb{Z} \times \mathbb{Z}$ und für jeden Punkt $z = (m,n) \in \mathbb{Z} \times \mathbb{Z}$ seine Nachbarpunkte mit

u(z) = (m,n + 1), d(z) = (m,n − 1), r(z) = (m + 1,n), l(z) = (m − 1,n),

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

Die Menge π von Richtungen sei mit π = {u,d,r,l} definiert.

Weiterhin versteht man unter einer Einheitsstrecke die Strecke, die durch zwei benachbarte Punkte verbunden wird. Das heißt, für jeden Punkt $z = (m,n) \in \mathbb{Z} \times \mathbb{Z}$ und jede Richtung $b \in \pi$ gibt es eine Strecke zwischen z und b(z) (diagonale Strecken sind damit ausgeschlossen). Eine Einheitsstrecke wird mit dem Punktepaar (z,b(z)) repräsentiert, wobei (z,b(z)) und (b(z),z) geometrisch gesehen gleich sind.

Ein (einfaches) Bild p sei eine endliche Menge von Einheitsstrecken und $V(p) = \{z \vert (z,z^{'}) \in p \vee (z^{'},z) \in p \}$ die Menge aller Punkte von p.

Man nennt das Tripel (z,p,z^'), wobei p ein einfaches Bild ist und $z,z^{'} \in V(p)$ Anfangs- und Endpunkt heißen, gezeichnetes Bild.

Zwei einfache Bilder p und p^' sind genau dann äquivalent – man schreibt $p \equiv_b p^{'}$ –, wenn zwei Zahlen $m,n \in \mathbb{Z}$ existieren, sodass $(z,z^{'}) \in p$ dann und nur dann, wenn $(z + (m,n),z^{'} + (m,n)) \in p^{'}$. Analog heißen zwei gezeichnete Bilder q = (z₁,p,z₂) und $q^{'} = (z_1^{'}, p^{'}, z_2^{'})$ genau dann äquivalent – man schreibt $q \equiv_d q^{'}$ –, wenn zwei Zahlen $m,n \in \mathbb{Z}$ existieren, sodass $(z,z^{'}) \in p$ dann und nur dann, wenn $(z + (m,n),z^{'} + (m,n)) \in p^{'}$ und $z_1^{'} = z_1 + (m,n)$, $z_2^{'} = z_2 + (m,n)$. Intuitiv sind Bilder also bis auf Verschiebung im Koordinatensystem gleich. Wie man leicht zeigen kann, sind $\equiv_b$ und $\equiv_d$ Äquivalenzrelationen über der Menge aller einfachen bzw. gezeichneten Bilder.

Man bezeichnet ein einfaches Bild p als (einfaches) Unterbild des einfachen Bildes q, wenn ein einfaches Bild p^' mit $p^{'} \subseteq q$ und $p \equiv_b p^{'}$ existiert.

Ein Bild p ist ein (einfaches) Ketten-Kode-Bild, wenn eine endliche Folge von Einheitsstrecken $(z_0, z_1), (z_1, z_2), \ldots, (z_{n-2}, z_{n-1}), (z_{n-1}, z_n)$ mit $n \in \mathbb{N}$ und z_i = b_i(z_{i − 1}),$b_i \in \pi$, $1 \leq i \leq n$ existiert, sodass $p = \bigcup_{k = 1}^{n} \{(z_{k-1}, z_k)\}$ gilt. Folglich ist ein Ketten-Kode-Bild stets zusammenhängend.

Generierung durch formale Grammatiken

Ketten-Kode-Bilder und Wörter

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 p mit der Folge $(z_0, z_1), (z_1, z_2), \ldots, (z_{n-2}, z_{n-1}), (z_{n-1}, z_n)$ und z_i = b_i(z_{i − 1}), $b_i \in \pi$, $1 \leq i \leq n$ das Wort $b_1 b_2 \cdots b_n \in \pi^{*}$ zugewiesen wird.

Andererseits weist man jedem Wort $w \in \pi^{*}$ ein gezeichnetes Ketten-Kode-Bild (drawn chain code picture) dccp(w) induktiv wie folgt zu:

• falls w = ε, dann $dccp(w) = ((0,0), \emptyset, (0,0))$
• falls w = w^'b, $w^{'}\in \pi^{*}$, $b \in \pi$ und dccp(w^') = ((0,0),p,z), dann $dccp(w) = ((0,0), p \cup \{(z, b(z))\}, b(z))$

Mit dccp(w) = ((0,0),p,z) ist bccp(w) = p das einfache Ketten-Kode-Bild (basic chain code picture) von w.

Nun können mit einer formalen Grammatik G = (N,π,P,S) Wörter erzeugt und als Ketten-Kode-Bilder interpretiert werden. Die Menge aller von G generierten Bilder sei $dccp(L(G)) = \{ dccp(w) \vert w \in L(G) \}$ bzw. $bccp(L(G)) = \{ bccp(w) \vert w \in L(G) \}$, wobei L(G) die von G erzeugte Sprache (siehe Von G erzeugte Sprache) ist – man nennt sie auch Ketten-Kode-Bild-Sprache.

Beispiel

Sei $G_1 = (\{S\}, \pi, \{S \to urdluS, S \to urdlu\}, S)$ eine gegebene formale Grammatik. Die von G₁ erzeugte Sprache ist

$L(G_1) = \{(urdlu)^n \vert n \in \mathbb{N}\} = \{urdlu, urdluurdlu, urdluurdluurdlu, \ldots\}$.

Die Menge dccp(L(G₁)) der von G₁ erstellten Bilder ist in der nachstehenden Abbildung dargestellt:

Die Ketten-Kode-Bild-Sprache dccp(L(G₁)). Der Anfangspunkt (0,0) 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 1 bestehen.

Hierarchie der Ketten-Kode-Bild-Sprachen

Analog zu formalen Sprachen wird eine Ketten-Kode-Bild-Sprache B 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 G gibt, sodass B = bccp(L(G)) gilt (siehe Chomsky-Hierarchie). Mit $\mathcal{CCP}(REG)$, $\mathcal{CCP}(CF)$, $\mathcal{CCP}(CS)$ und $\mathcal{CCP}(RE)$ 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 $\mathcal{CCP}(REG) \subset \mathcal{CCP}(CF) \subset \mathcal{CCP}(CS) = \mathcal{CCP}(RE)$. Somit betrachtet man in der Tat nur drei echte Familien.

Entscheidungsprobleme für Ketten-Kode-Bild-Sprachen

Klassische Entscheidungsprobleme

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 G = (N,π,P,S) und ein Ketten-Kode-Bild p.
• Gilt $p \in bccp(L(G))$, gibt es also ein Wort $w \in L(G)$, sodass p = bccp(w) wahr wird?

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

1. spezielles Bildproblem

• Gegeben ist eine formale Grammatik G = (N,π,P,S) und ein Ketten-Kode-Bild p.
• Ist die Menge $\{ w \vert w \in L(G) \wedge bccp(w) = p \}$ endlich?

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

2. spezielles Bildproblem

• Gegeben ist eine formale Grammatik G = (N,π,P,S) und ein Ketten-Kode-Bild p.
• Hat die Menge $\{ w \vert w \in L(G) \wedge bccp(w) = p \}$ genau ein Element?

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

Unterbildproblem

• Gegeben ist eine formale Grammatik G = (N,π,P,S) und ein Ketten-Kode-Bild p.
• Gibt es ein Ketten-Kode-Bild $p^{'} \in bccp(L(G))$, sodass p ein Unterbild von p^' ist?

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

Universelles Unterbildproblem

• Gegeben ist eine formale Grammatik G = (N,π,P,S) und ein Ketten-Kode-Bild p.
• Ist p ein Unterbild jedes Ketten-Kode-Bildes $p^{'} \in bccp(L(G))$?

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

Leerheitsproblem

• Gegeben ist eine formale Grammatik G = (N,π,P,S).
• Ist die Menge bccp(L(G)) leer?

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

Endlichkeitsproblem

• Gegeben ist eine formale Grammatik G = (N,π,P,S).
• Ist die Menge bccp(L(G)) endlich?

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

Äquivalenzproblem

• Gegeben sind zwei formale Grammatiken G₁ = (N₁,π,P₁,S₁) und G₂ = (N₂,π,P₂,S₂).
• Gilt bccp(L(G₁)) = bccp(L(G₂)), erzeugen also beide Grammatiken über ihre Wörter dieselben Ketten-Kode-Bilder?

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

Man beachte, dass auf Grund der in Abschnitt Hierarchie der Ketten-Kode-Bild-Sprachen festgestellten Inklusionen für jedes der genannten Probleme P mit der formalen Grammatik G und X = {REG,CF,CS} gilt:

• wenn P für $bccp(L(G)) \in \mathcal{CCP}(x)$ mit $x \in X$ entscheidbar ist, ist P für eine formale Grammatik G^' mit $bccp(L(G^')) \in \mathcal{CCP}(x^')$, $x^' \in X$ und $\mathcal{CCP}(x^') \subset \mathcal{CCP}(x)$ ebenso entscheidbar.
• wenn P für $bccp(L(G)) \in \mathcal{CCP}(x)$ mit $x \in X$ unentscheidbar ist, ist P für eine formale Grammatik G^' mit $bccp(L(G^')) \in \mathcal{CCP}(x^')$, $x^' \in X$ und $\mathcal{CCP}(x^') \supset \mathcal{CCP}(x)$ gleichfalls unentscheidbar.

Geometrische Entscheidungsprobleme

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

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

Untersuchungen haben gezeigt, dass bereits für reguläre formale Grammatiken G = (N,π,P,S) unentscheidbar ist, ob bccp(L(G))

• 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 G = (N,π,P,S) entscheidbar, ob

• alle Bilder von bccp(L(G)) geschlossene einfache Kurve sind,
• alle Bilder von bccp(L(G)) Rechtecke sind,
• bccp(L(G)) ein Rechteck enthält,
• bccp(L(G)) ein konvexes Bild enthält.

Weiterhin kann für eine kontextfreie formale Grammatiken G = (N,π,P,S) entschieden werden, ob alle Bilder von bccp(L(G)) Bäume sind.

Verallgemeinerungen

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

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 $z = (m,n) \in \mathbb{Z} \times \mathbb{Z}$ die Nachbarpunkte

ur(z) = (m + 1,n + 1), ul(z) = (m − 1,n + 1), dl(z) = (m − 1,n − 1), dr(z) = (m + 1,n − 1),

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 π_F = {u,d,r,l,ur,ul,dl,dr}.

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

Farbige Ketten-Kode-Bilder

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 C eine endliche Mengen von Farben. Dann erhalten wir das neue Alphabet π_C mit $\pi_C = \pi \times C$, das heißt die Buchstaben sind Paare der Form (b,c) für $b \in \pi$ und $c \in C$.

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

Nicht-zusammenhängende Ketten-Kode-Bilder

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 $\pi_\updownarrow = \{u, d, r, l, \uparrow, \downarrow\}$.Intuitiv steht $\uparrow$ für das Absetzen des Stifts und $\downarrow$ für das Ansetzen. Für ein besseres Verständnis betrachte man das nachstehende von oben abgeänderte Beispiel.

Sei $G_2 = (\{S\}, \pi_\updownarrow, \{S \to \downarrow{}u\uparrow{}r\downarrow{}d\uparrow{}luS, S \to \downarrow{}u\uparrow{}r\downarrow{}d\uparrow{}lu\}, S)$

eine gegebene formale Grammatik. Die von G₂ erzeugte Sprache ist

$L(G_2) = \{(\downarrow{}u\uparrow{}r\downarrow{}d\uparrow{}lu)^n \vert n \in \mathbb{N}\}$.

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 G₂ erzeugten Bilder. Der Anfangspunkt (0,0) 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 $\mathcal{CCP}_\updownarrow(X)$ mit X = {REG,CF,CS,RE} der Typen der Chomsky-Hierarchie aufstellen und erhält

$\mathcal{CCP}_\updownarrow(REG) \subset \mathcal{CCP}_\updownarrow(CF) \subset \mathcal{CCP}_\updownarrow(CS) = \mathcal{CCP}_\updownarrow(RE)$

und

$\mathcal{CCP}(X) \subset \mathcal{CCP}_\updownarrow(X)$.

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

Generierung durch andere Grammatiken

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

• Jürgen Dassow: Grammatical Picture Generation – Manuscript.