Chain code pictures

Chain code images ( Chain Code Pictures ) are images using formal grammars are generated. A word generated by such a grammar is interpreted as exactly one image in that the individual symbols are interpreted as directions and a drawing is thus described in a coordinate system.

Basics

The integer coordinate system and its neighboring points for each point are given ${\displaystyle \mathbb {Z} \times \mathbb {Z} }$ ${\displaystyle z=(m,n)\in \mathbb {Z} \times \mathbb {Z} }$

${\displaystyle u(z)=(m,n+1)}$, , , , ${\displaystyle d(z)=(m,n-1)}$ ${\displaystyle r(z)=(m+1,n)}$ ${\displaystyle l(z)=(m-1,n)}$

wherein , , or intuitive to the upper ( u p), lower ( d own), Right ( r ight) or left ( l eft) are adjacent point. ${\displaystyle u}$ ${\displaystyle d}$ ${\displaystyle r}$ ${\displaystyle l}$

Let the set of directions be defined with . ${\displaystyle \pi }$ ${\displaystyle \pi =\{u,d,r,l\}}$

Furthermore, a unit route is understood to be the route that is connected by two neighboring points. That means, for every point and every direction there is a line between and (diagonal lines are excluded). A unit distance is represented by the pair of points , where and are geometrically the same. ${\displaystyle z=(m,n)\in \mathbb {Z} \times \mathbb {Z} }$ ${\displaystyle b\in \pi }$ ${\displaystyle z}$ ${\displaystyle b(z)}$ ${\displaystyle (z,b(z))}$ ${\displaystyle (z,b(z))}$ ${\displaystyle (b(z),z)}$

A ( simple ) image is a finite set of unit segments and the set of all points of . ${\displaystyle p}$ ${\displaystyle V(p)=\{z\vert (z,z^{'})\in p\vee (z^{'},z)\in p\}}$ ${\displaystyle p}$

This is called a triple , where is a simple picture and the start and end point are called the drawn picture . ${\displaystyle (z,p,z^{'})}$ ${\displaystyle p}$ ${\displaystyle z,z^{'}\in V(p)}$

Two simple images and are equivalent - one writes - if and only if two numbers exist, such that if and only if . Analog hot two drawn images and if and equivalent - to write - if two numbers exist, so if and only if , and , . So, intuitively, images are the same except for a shift in the coordinate system. As one can easily show, are and equivalence relations of all simple or drawn images through the crowd. ${\displaystyle p}$ ${\displaystyle p^{'}}$ ${\displaystyle p\equiv _{b}p^{'}}$ ${\displaystyle m,n\in \mathbb {Z} }$ ${\displaystyle (z,z^{'})\in p}$ ${\displaystyle (z+(m,n),z^{'}+(m,n))\in p^{'}}$ ${\displaystyle q=(z_{1},p,z_{2})}$ ${\displaystyle q^{'}=(z_{1}^{'},p^{'},z_{2}^{'})}$ ${\displaystyle q\equiv _{d}q^{'}}$ ${\displaystyle m,n\in \mathbb {Z} }$ ${\displaystyle (z,z^{'})\in p}$ ${\displaystyle (z+(m,n),z^{'}+(m,n))\in p^{'}}$ ${\displaystyle z_{1}^{'}=z_{1}+(m,n)}$ ${\displaystyle z_{2}^{'}=z_{2}+(m,n)}$ ${\displaystyle \equiv _{b}}$ ${\displaystyle \equiv _{d}}$

A simple picture is called a ( simple ) sub- picture of the simple picture if a simple picture with and exists. ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p^{'}}$ ${\displaystyle p^{'}\subseteq q}$ ${\displaystyle p\equiv _{b}p^{'}}$

A picture is a ( simple ) chain code image when a finite sequence of unit distances with and , , there is so true. Consequently, a chain-code picture is always connected. ${\displaystyle p}$ ${\displaystyle (z_{0},z_{1}),(z_{1},z_{2}),\ldots ,(z_{n-2},z_{n-1}),(z_{n-1},z_{n})}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle z_{i}=b_{i}(z_{i-1})}$ ${\displaystyle b_{i}\in \pi }$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle p=\bigcup _{k=1}^{n}\{(z_{k-1},z_{k})\}}$

Generation through formal grammars

Chain code pictures and words

Due to the definition of chain code pictures that with words (can chain codes or chain codes ) via associated by a chain-code image with the result and , , the word is assigned. ${\displaystyle \pi }$ ${\displaystyle p}$ ${\displaystyle (z_{0},z_{1}),(z_{1},z_{2}),\ldots ,(z_{n-2},z_{n-1}),(z_{n-1},z_{n})}$ ${\displaystyle z_{i}=b_{i}(z_{i-1})}$ ${\displaystyle b_{i}\in \pi }$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle b_{1}b_{2}\cdots b_{n}\in \pi ^{*}}$

On the other hand, it gives each word a signed chain code image ( drawn chain code picture ) inductively as follows: ${\displaystyle w\in \pi ^{*}}$ ${\displaystyle dccp(w)}$

• if so then ${\displaystyle w=\epsilon }$ ${\displaystyle dccp(w)=((0,0),\emptyset ,(0,0))}$
• If , , and , then ${\displaystyle w=w^{'}b}$ ${\displaystyle w^{'}\in \pi ^{*}}$ ${\displaystyle b\in \pi }$ ${\displaystyle dccp(w^{'})=((0,0),p,z)}$ ${\displaystyle dccp(w)=((0,0),p\cup \{(z,b(z))\},b(z))}$

With is the basic chain code picture from . ${\displaystyle dccp(w)=((0,0),p,z)}$ ${\displaystyle bccp(w)=p}$ ${\displaystyle w}$

Words can now be generated with a formal grammar and interpreted as chain code images. Let the set of all images generated by be or , where is the language generated by (see Language generated by G ) - it is also called chain-code-image language . ${\displaystyle G=(N,\pi ,P,S)}$ ${\displaystyle G}$ ${\displaystyle dccp(L(G))=\{dccp(w)\vert w\in L(G)\}}$ ${\displaystyle bccp(L(G))=\{bccp(w)\vert w\in L(G)\}}$ ${\displaystyle L(G)}$ ${\displaystyle G}$

example

Let be a given formal grammar. The language generated by is ${\displaystyle G_{1}=(\{S\},\pi ,\{S\to urdluS,S\to urdlu\},S)}$ ${\displaystyle G_{1}}$

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

The amount of images created by is shown in the figure below: ${\displaystyle dccp(L(G_{1}))}$ ${\displaystyle G_{1}}$

The chain-code-picture-language . The starting point of an image is marked with a green circle and the end point with an orange rectangle. ${\displaystyle dccp(L(G_{1}))}$ ${\displaystyle (0,0)}$

So you get a countable number of stacks of arbitrary but fixed height, which consist of squares the length of the edge . ${\displaystyle 1}$

Chain-Code-Image-Language Hierarchy

Analogous to formal languages , a chain-code-image language is called regular or context-free or monotonic (or context-sensitive) or recursively enumerable if there is a regular or context-free or monotonic (or context-sensitive) or recursively enumerable formal grammar so that applies (see Chomsky hierarchy ). With , , and referred to the quantities (families) of all regular, context-free, monotonous and recursively enumerable chain code picture languages. ${\displaystyle B}$ ${\displaystyle G}$ ${\displaystyle B=bccp(L(G))}$ ${\displaystyle {\mathcal {CCP}}(REG)}$ ${\displaystyle {\mathcal {CCP}}(CF)}$ ${\displaystyle {\mathcal {CCP}}(CS)}$ ${\displaystyle {\mathcal {CCP}}(RE)}$

An important finding is the validity of the inclusions or equality . Thus, in fact, only three real families are considered. ${\displaystyle {\mathcal {CCP}}(REG)\subset {\mathcal {CCP}}(CF)\subset {\mathcal {CCP}}(CS)={\mathcal {CCP}}(RE)}$

Decision problems for chain-code-image languages

Classic decision problems

As for formal languages, important decision problems can be formulated in the same way for chain-code-image languages :

Image problem (also member problem )

• A formal grammar and a chain code image are given . ${\displaystyle G=(N,\pi ,P,S)}$ ${\displaystyle p}$
• Is there a word that makes it true? ${\displaystyle p\in bccp(L(G))}$ ${\displaystyle w\in L(G)}$ ${\displaystyle p=bccp(w)}$

The image problem is decidable for context-free formal grammars and undecidable for context-sensitive formal grammars . This problem is NP-complete for regular formal grammars . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

1. special image problem

• A formal grammar and a chain code image are given . ${\displaystyle G=(N,\pi ,P,S)}$ ${\displaystyle p}$
• Is the amount finite? ${\displaystyle \{w\vert w\in L(G)\wedge bccp(w)=p\}}$

So one asks whether there are finitely or infinitely many words that generate the chain-code image . Like the image problem, this problem is decidable for context-free formal grammars and undecidable for context-sensitive formal grammars . ${\displaystyle p}$ ${\displaystyle G}$ ${\displaystyle G}$

2. special image problem

• A formal grammar and a chain code image are given . ${\displaystyle G=(N,\pi ,P,S)}$ ${\displaystyle p}$
• Does the set have exactly one element? ${\displaystyle \{w\vert w\in L(G)\wedge bccp(w)=p\}}$

Thus, asked whether the chain code picture of exactly one word out is generated. This problem is again decidable for context-free formal grammars and undecidable for context-sensitive formal grammars . ${\displaystyle p}$ ${\displaystyle w}$ ${\displaystyle L(G)}$ ${\displaystyle G}$ ${\displaystyle G}$

Underpicture problem

• A formal grammar and a chain code image are given . ${\displaystyle G=(N,\pi ,P,S)}$ ${\displaystyle p}$
• Is there a chain code image such that is a subimage of ? ${\displaystyle p^{'}\in bccp(L(G))}$ ${\displaystyle p}$ ${\displaystyle p^{'}}$

The sub-picture problem is decidable for context-free formal grammars and undecidable for context-sensitive formal grammars . ${\displaystyle G}$ ${\displaystyle G}$

Universal underpicture problem

• A formal grammar and a chain code image are given . ${\displaystyle G=(N,\pi ,P,S)}$ ${\displaystyle p}$
• Is a sub-picture of every chain code picture ? ${\displaystyle p}$ ${\displaystyle p^{'}\in bccp(L(G))}$

For regular formal grammars the universal sub-picture problem is decidable. ${\displaystyle G}$

Emptiness problem

• A formal grammar is given . ${\displaystyle G=(N,\pi ,P,S)}$
• Is the crowd empty? ${\displaystyle bccp(L(G))}$

The emptiness problem is decidable for context-free formal grammars and undecidable for context-sensitive formal grammars . ${\displaystyle G}$ ${\displaystyle G}$

Finiteness problem

• A formal grammar is given . ${\displaystyle G=(N,\pi ,P,S)}$
• Is the amount finite? ${\displaystyle bccp(L(G))}$

The finiteness problem is decidable for context-free formal grammars and undecidable for context-sensitive formal grammars . ${\displaystyle G}$ ${\displaystyle G}$

Equivalence problem

• There are two formal grammars and . ${\displaystyle G_{1}=(N_{1},\pi ,P_{1},S_{1})}$ ${\displaystyle G_{2}=(N_{2},\pi ,P_{2},S_{2})}$
• Does that mean that both grammars generate the same chain-code images via their words? ${\displaystyle bccp(L(G_{1}))=bccp(L(G_{2}))}$

The equivalence problem is already for regular formal grammars and undecidable. ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

Note that due to the inclusions established in the section Hierarchy of Chain-Code-Image-Languages , the following applies to each of the named problems with formal grammar and : ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle X=\{REG,CF,CS\}}$

• if for with is decidable, for a formal grammar with , and is also decidable. ${\displaystyle P}$ ${\displaystyle bccp(L(G))\in {\mathcal {CCP}}(x)}$ ${\displaystyle x\in X}$ ${\displaystyle P}$ ${\displaystyle G^{'}}$ ${\displaystyle bccp(L(G^{'}))\in {\mathcal {CCP}}(x^{'})}$ ${\displaystyle x^{'}\in X}$ ${\displaystyle {\mathcal {CCP}}(x^{'})\subset {\mathcal {CCP}}(x)}$
• if for with is undecidable, for a formal grammar with , and is also undecidable. ${\displaystyle P}$ ${\displaystyle bccp(L(G))\in {\mathcal {CCP}}(x)}$ ${\displaystyle x\in X}$ ${\displaystyle P}$ ${\displaystyle G^{'}}$ ${\displaystyle bccp(L(G^{'}))\in {\mathcal {CCP}}(x^{'})}$ ${\displaystyle x^{'}\in X}$ ${\displaystyle {\mathcal {CCP}}(x^{'})\supset {\mathcal {CCP}}(x)}$

Geometric decision problems

First some geometric properties of a chain code image are defined below: ${\displaystyle p}$

• ${\displaystyle p}$is a simple curve if all nodes have degree 2 or less. ${\displaystyle p}$
• ${\displaystyle p}$is called a closed simple curve if all nodes have exactly degree 2. ${\displaystyle p}$
• ${\displaystyle p}$is called regular if all nodes have the same degree. ${\displaystyle p}$
• ${\displaystyle p}$is called a tree if it does not contain a closed simple curve as a partial image.
• ${\displaystyle p}$is Eulerian when all nodes are of a degree. ${\displaystyle p}$
• ${\displaystyle p}$is called Hamiltonian when a simple curve has as a partial image that contains all the nodes of . ${\displaystyle p}$ ${\displaystyle p}$

Studies have shown that even for regular formal grammars it is undecidable whether ${\displaystyle G=(N,\pi ,P,S)}$ ${\displaystyle bccp(L(G))}$

• a simple curve,
• a closed simple curve,
• a regular picture,
• a tree,
• an Euler's picture,
• a Hamiltonian picture

includes.

For regular formal grammars , however, it can be decided whether ${\displaystyle G=(N,\pi ,P,S)}$

• all pictures are of closed simple curve, ${\displaystyle bccp(L(G))}$
• all pictures are of rectangles , ${\displaystyle bccp(L(G))}$
• ${\displaystyle bccp(L(G))}$ contains a rectangle,
• ${\displaystyle bccp(L(G))}$contains a convex image.

Furthermore, for context-free formal grammars it can be decided whether all images are of trees. ${\displaystyle G=(N,\pi ,P,S)}$ ${\displaystyle bccp(L(G))}$

Generalizations

In the following some (informal) comments are made about extensions and generalizations of chain code images in order to get better images in a certain way.

Adding new directions

A certainly intuitive approach to expanding chain-code images is to add new directions to the four already known: up, down, right, and left. So can for example for all the neighboring points ${\displaystyle z=(m,n)\in \mathbb {Z} \times \mathbb {Z} }$

${\displaystyle ur(z)=(m+1,n+1)}$, , , , ${\displaystyle ul(z)=(m-1,n+1)}$ ${\displaystyle dl(z)=(m-1,n-1)}$ ${\displaystyle dr(z)=(m+1,n-1)}$

can be added. Accordingly, one obtains the additional upper right directions ( u p r ight), top left ( u p l eft), lower right ( d own r ight) and lower left ( d own l eft), and thus the new alphabet . ${\displaystyle \pi _{F}=\{u,d,r,l,ur,ul,dl,dr\}}$

The above undecidable problems regarding the alphabet also remain undecidable under the alphabet . The situation is similar for the decidable problems. ${\displaystyle \pi }$ ${\displaystyle \pi _{F}}$

Colored chain code pictures

If you want to get colored chain code images, the alphabet can be changed as follows. Instead of just using letters for directions, they are assigned colors. Let be a finite set of colors. Then we get the new alphabet with , i.e. the letters are pairs of the form for and . ${\displaystyle \pi }$ ${\displaystyle C}$ ${\displaystyle \pi _{C}}$ ${\displaystyle \pi _{C}=\pi \times C}$ ${\displaystyle (b,c)}$ ${\displaystyle b\in \pi }$ ${\displaystyle c\in C}$

Here, too, one obtains similar results for the indecisability and decidability of the above problems.

Non-contiguous chain code images

Chain code images are always connected. If you want to allow non-connected chain-code images, you can add two letters to the alphabet , which in a sense mean putting a pencil on and off. The new alphabet is then. Intuitive stands for putting the pen down and putting it on . For a better understanding, consider the example modified from above below. ${\displaystyle \pi }$ ${\displaystyle \pi _{\updownarrow }=\{u,d,r,l,\uparrow ,\downarrow \}}$ ${\displaystyle \uparrow }$ ${\displaystyle \downarrow }$

Be ${\displaystyle 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)}$

a given formal grammar. The language generated by is ${\displaystyle G_{2}}$

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

The generated images look similar to those in the example above, only there are no horizontal stretches, because this is where the pen was always put down and was put back on with the vertical ones:

The amount of images produced by. The starting point of an image is marked with a green circle and the end point with an orange rectangle. ${\displaystyle G_{2}}$ ${\displaystyle (0,0)}$

Analogous to chain code images, the family can also be set up and maintained here with the types of the Chomsky hierarchy ${\displaystyle {\mathcal {CCP}}_{\updownarrow }(X)}$ ${\displaystyle X=\{REG,CF,CS,RE\}}$

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

and

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

With regard to the above decision problems, the situation here is significantly worse due to the non-correlation of the images.

Generation by other grammars

Another way of creating chain-code-image languages ​​is to use other grammars. For example, Lindenmayer systems , turtle grammars , matrix grammars and collage grammars can be used to generate chain code images.

Depending on the type of grammar used, it is possible that certain images cannot be generated from any grammar of one type, but from a grammar of another type. In particular, it can be shown that there are chain code images that are produced by formal grammars but not by collage grammars.

literature

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