[JS]
[DE]
[PLUGIN] ../../build/popup.plugin
[PLUGIN] ../../build/ca.plugin
[PLUGIN] ../../build/file.plugin
[PLUGIN] ../../build/image.plugin
[PLUGIN] ../../build/math.plugin
[TITLE] Zelluläre Automaten (Parallele Systeme)
[AUTHOR] Stefan Bosse
[VERSION] 5.2020
[FUN]
```
function jsexec (text,stdout,stderr) {
  var oldprint=print;
  print=stdout;
  try {
    stdout(eval(text)||'Ok.');
  } catch (e) {
    stderr(e.toString())
  }
  print=oldprint;
}
```
# Hinweise

- Dieses interaktive Notebook enthält statische Inhalte und Code Snippets die direkt im Notebook ausgeführt werden können 
- In Code Snippets: Linker Play Knopf startet die Ausführung des Codes. Der rechte Knopf ermöglicht das Löschen der Ausgabe!
- Bei Animationen gibt es es noch einen Stop Knopf der zur unmittelbaren Terminierung der Animation führt.
- Der Code kann verändert werden!
- Alle editierbaren Inhalte können gespeichert werden: Rechts oben (Save Notebook) Knopf
- Alle editierbaren Inhalte können wieder geladen werden und überschreiben Inhalte: Links oben (Load Notebook) Knopf
- Es können Notizen in Markdown Syntax gemacht werden, die auch gespeichert werden (Oben, Stift Knopf)
- Der Code ist in JavaScript - eine Einführung gibt es hier [tutorial6.html](http://edu-9.de/lehre/tutorial6.html)

# Zelluläre Automaten

## Einführung

- Ein zellulärer Automat besteht aus einer Menge von zustandsbasierten Zellen *ZA*={*z*~1~,*z*~2~,..,*z*~n~}.

- Eine Zelle besitzt eine Anzahl von Zellenvariablen die den veränderlichen (Daten) Zustand *S* bestimmen: *S*(*z*~i~)={*x*~1~,..,*x*~k~}

- Der nächste Zustand der Zellen wird über eine *activity* Funktion berechnet.

- Der Zustandsübergang einer Zelle erfolgt i.A. in der *before* oder *after* Funktion.

- Ein Scheduler führt die einzelnen Berechnungsfunktionen einer Zelle sequenziell in drei Phasen aus (obwohl ein ZA ein parelleles System ist!):
  1. *before*
  2. *activity*
  3. *after*

- Dabei gibt es verschiedene Scheduler Algorithmen wie räumlich die Zellen nacheinander ausgewählt werden:
  + *UPRIGHT* (Phase 1: aufsteigende Reihenfolge *before* aller Zellen, Phase 2: aufsteigend *activity*  aller Zellen,)
  + *DOWNLEFT* (Phase 1: absteigende Reihenfolge *before* aller Zellen, Phase 2: absteigend *activity*  aller Zellen,)
  + *RANDOM* (Phase 1: zusammen *before*;*activity* einer Zelle, zufällige Reihenfolge aller Zellen)
  + *RANDOM0* (Phase 1: aufsteigend *before* aller Zellen, Phase 2: zufällig *activity*)

## Architektur und Grundprinzip

- Der Zelluläre Automat ist hier ein Simulator für ein paralleles und verteiltes System! 
- Jede Zelle repräsentiert einen Computer mit Netzwerkverbindungen zu den Nachbarzellen!

![#loops width=50%](images/ca01.png)
*Zellulärer Automat als Netzwerk aus einfachen kommunizierenden Berechnungseinheiten*

## Nachbarschaft

- Nachbarschaftsrelationen sind auch bei Agenten wichtige Eigenschaft

![#loops width=50%](images/ca02.png)
*Verschiedene Nachbarschaftsrelationen*

## Zustände

- Eine Zelle des ZA ist ein endlicher Zustandsautomat

- Ein Zustandsautomat hat einen Kontrollzustand γ und Datenzustand δ, d.h., σ(*t*)=⟨γ,δ⟩(*t*)

- Rein "funktionale" Automaten besitzen nur einen Datenzustand der sich durch eine Übergangsfunktion schrittweise ändert (einfachste Zelle), d.h., σ(*t*)=δ(*t*)

$
\sigma_{i,j}(t + 1) = f(\sigma_{i,j}(t))
$

# Experimente

## Setup

[IMAGE] Load and Show Test Image { eval:jsexec }
```js

image = {}
File.load('test.png','image/png',function (data) {
  image.name='test.png';
  print(data.length+' bytes');
  image.data=PNG.decode(data);
  image.binary=PNG.toBinaryArray(image.data,50,false);
  print(image.data.width,image.data.height)
  show(image.binary);
});
```
[IMAGE] Create and Show Noisy Image { eval:jsexec }
```js
var noiseK = 0.01;
image.noise = image.binary.map (function (row) {
    return row.map(function(v) {
      if (Math.random()<noiseK) return v?0:1;
      else return v;
    })
  });
show(image.noise)
```

- Das Array *image.binary* enthält ein binäres Bild (schwarz:0, weiß:1}

## Bildglättung 1 (Naiver Ansatz)

- Sehr naiver Rauschfilter durch Nachbarschaftsglättung. Wichtig: Binäre Bilder erlauben Grauwertinterpolation!

- Ein Pixelwert wird durch die "Mehrheit" der Nachbarschaft gsetzt (1/0)

[CA] Bildglättung Majority { id:ca1 }
```js
{
  rows: 100,
  columns : 100,
  neighbors : 8,
  palette : ['white','black'],
  parameter : {
    thresHold:4,
  },
  cell : {
    name : 'mean',
    size : 4,
    // Die Zustandsvariablen einer Zelle
    state : { pixel:0, pixel0:0 },
    // Phase 1: Zustandsübergang ohne Berechnung!
    before : function () {
      this.pixel0 = this.pixel;
    },
    // Phase 2: Brechnen des nächsten Zustandes
    activity : function (neighbors,x,y) {
      var surrounding = this.ask(neighbors, 'count', 'pixel0');
      this.pixel = surrounding > this.thresHold?1:0;
    },
    // Phase 0: Einmalige Initialisierung der Zelle
    init : function (x,y) {
      this.pixel = this.data[y][x];
    },
    // Farbe aus Palette (Index) in Abhaengigkeit vom Zustand
    color : function () { return this.pixel ?  0:1 },
  },
  // Initialisierung mit Pseudozufallszahlen [0,1)
  data : image.noise,
  steps : 3,
  scheduler : 'UPRIGHT', // 'DOWNLEFT', 'RANDOM', 'RANDOM0'
  start :  [{ name: 'mean', distribution: 100 }],
}
```

[EXERCISE] A
[QUESTION] A1
Untersuche die Abhängigkeit der Bildglättung von den Parametern *thresHold* und *steps* bei verschiedenen Rauschanteilen  *noiseK*={0.01,0.1,0.3}. Wie können die Bildergebnisse bewertet werden (qualitativ)? Verwende den `UPRIGHT` Scheduler.

[INPUT]

[QUESTION] A2
Untersuche die Abhängigkeit der Bildglättung bei verschiedenen Scheduler Algorithmen. Welchen Einfluss hat die Reihenfolge der Zellaktivierung und Ein- und Zweiphasenaktivierung?

[INPUT]

[EXERCISE]

## Bildglättung 2 (Musterbasiert)

- Lese [Rosin,2002](http://edu-9.de/uploads/articles/Rosinmanuscript2.pdf)

- Versuche die im Artikel gezeigten Muster zur Rauschunterdrückung in folgende Code einzubauen. Teste den Algorithmus

- Die Variable *neighbors* enthält alle acht Nachbarzellen in folgender Reihenfolge (an Rändern können einige Einträge *null* enthalten):

```
neighbors(x,y) = [
  { x:x-1,y:y-1, ... },
  { x:x  ,y:y-1, ... },
  { x:x+1,y:y-1, ... },
  { x:x-1,y:y,   ... },
  { x:x+1,y:y,   ... },
  { x:x-1,y:y+1, ... },
  { x:x  ,y:y+1, ... },
  { x:x+1,y:y+1, ... },
]

+-----> (x)
  |
  |
  v
  (y)

0 1 2 
  3 X 4
  5 6 7   (index in array)
```

[CA] Bildglättung durch Mustersuche und Regelsätzen { id:ca2 }
```js
{
  rows: 100,
  columns : 100,
  neighbors : 8,
  palette : ['white','black'],
  parameter : {
    rules : [
      {pattern:[0,0,0,0,0,0,0,0], pixel0:1, pixel:0 } // pattern:  pixel0 values of neighbors
    ]
  },
  cell : {
    name : 'mean',
    size : 4,
    // Die Zustandsvariablen einer Zelle
    state : { pixel:0, pixel0:0 },
    // Phase 1: Zustandsübergang ohne Berechnung!
    before : function () {
      this.pixel0 = this.pixel;
    },
    // Phase 2: Brechnen des nächsten Zustandes
    activity : function (neighbors,x,y) {
      var set=0;
      var test = neighbors.map(function (cell) {
        if (!cell) return 0;
        return cell.pixel0;
      })
      for(var pi=0;pi<this.rules.length;pi++) {
        var rule=this.rules[pi];
        if (rule.pattern.match(test) && this.pixel0==rule.pixel0) {
            this.pixel=rule.pixel; break 
        };
      };
    },
    // Phase 0: Einmalige Initialisierung der Zelle
    init : function (x,y) {
      this.pixel = this.data[y][x];
    },
    // Farbe aus Palette (Index) in Abhaengigkeit vom Zustand
    color : function () { return this.pixel ?  0:1 },
  },
  // Initialisierung mit Pseudozufallszahlen [0,1)
  data : image.noise,
  steps : 1,
  scheduler : 'UPRIGHT', // 'DOWNLEFT', 'RANDOM', 'RANDOM0'
  start :  [{ name: 'mean', distribution: 100 }],
}
```
[CA] Kantendetektion mit Mustersuche und Regelsätzen { id:ca3 }
```js
// Plathalter für Experiment kantendetektion - aus obigen Code kopieren
{

}
```

[EXERCISE] B
1. Ergänze die Musterregeln damit auch schwarzes Rauschen reduziert wird
2. Nehme dann den Musterregelsatz für Rauschunterdrückung aus [Rosin,2002].
3. Nehme schließlich den Musterregelsatz für Kantendetektion aus [Rosin,2002].

[QUESTION] B1
Untersuche die Abhängigkeit der Qualität der Bildglättung von den Parameter *steps* sowie *scheduler* bei verschiedenen Rauscnanteilen  *noiseK*={0.01,0.1,0.3}. Wie können die Bildergebnisse bewertet werden (qualitativ)? Was funktioniert gut, ewann nicht?
Ist das Ergebnis überhaupt abhängig von der Anzahl von Itertaionen (*steps*>1)?

[INPUT]

[QUESTION] B2
Funktioniert die Kantendetektion? Ist das Ergebnis abhängig on der Anzahl von Iterationen (*steps*>1)? Wird es vom Scheduler Algorithmus beeinflusst?

[INPUT]

[QUESTION] B3
Wie ist das Ergebnis bei *RANDOM* Scheduling? Wie müssten Zellen sich synchronisieren.

[INPUT]

[EXERCISE]

Hinweise

Dieses interaktive Notebook enthält statische Inhalte und Code Snippets die direkt im Notebook ausgeführt werden können
In Code Snippets: Linker Play Knopf startet die Ausführung des Codes. Der rechte Knopf ermöglicht das Löschen der Ausgabe!
Bei Animationen gibt es es noch einen Stop Knopf der zur unmittelbaren Terminierung der Animation führt.
Der Code kann verändert werden!
Alle editierbaren Inhalte können gespeichert werden: Rechts oben (Save Notebook) Knopf
Alle editierbaren Inhalte können wieder geladen werden und überschreiben Inhalte: Links oben (Load Notebook) Knopf
Es können Notizen in Markdown Syntax gemacht werden, die auch gespeichert werden (Oben, Stift Knopf)
Der Code ist in JavaScript - eine Einführung gibt es hier tutorial6.html

Zelluläre Automaten

Einführung

Ein zellulärer Automat besteht aus einer Menge von zustandsbasierten Zellen ZA={z₁,z₂,..,z_n}.
Eine Zelle besitzt eine Anzahl von Zellenvariablen die den veränderlichen (Daten) Zustand S bestimmen: S(z_i)={x₁,..,x_k}
Der nächste Zustand der Zellen wird über eine activity Funktion berechnet.
Der Zustandsübergang einer Zelle erfolgt i.A. in der before oder after Funktion.
Ein Scheduler führt die einzelnen Berechnungsfunktionen einer Zelle sequenziell in drei Phasen aus (obwohl ein ZA ein parelleles System ist!):
1. before
2. activity
3. after
Dabei gibt es verschiedene Scheduler Algorithmen wie räumlich die Zellen nacheinander ausgewählt werden:
- UPRIGHT (Phase 1: aufsteigende Reihenfolge before aller Zellen, Phase 2: aufsteigend activity aller Zellen,)
- DOWNLEFT (Phase 1: absteigende Reihenfolge before aller Zellen, Phase 2: absteigend activity aller Zellen,)
- RANDOM (Phase 1: zusammen before;activity einer Zelle, zufällige Reihenfolge aller Zellen)
- RANDOM0 (Phase 1: aufsteigend before aller Zellen, Phase 2: zufällig activity)

Architektur und Grundprinzip

Der Zelluläre Automat ist hier ein Simulator für ein paralleles und verteiltes System!
Jede Zelle repräsentiert einen Computer mit Netzwerkverbindungen zu den Nachbarzellen!

#loops
Zellulärer Automat als Netzwerk aus einfachen kommunizierenden Berechnungseinheiten

Nachbarschaft

Nachbarschaftsrelationen sind auch bei Agenten wichtige Eigenschaft

#loops
Verschiedene Nachbarschaftsrelationen

Zustände

Eine Zelle des ZA ist ein endlicher Zustandsautomat
Ein Zustandsautomat hat einen Kontrollzustand γ und Datenzustand δ, d.h., σ(t)=⟨γ,δ⟩(t)
Rein "funktionale" Automaten besitzen nur einen Datenzustand der sich durch eine Übergangsfunktion schrittweise ändert (einfachste Zelle), d.h., σ(t)=δ(t)

\[ \sigma_{i,j}(t + 1) = f(\sigma_{i,j}(t)) \]

Experimente

Setup

Load and Show Test Image


image = {}
File.load('test.png','image/png',function (data) {
  image.name='test.png';
  print(data.length+' bytes');
  image.data=PNG.decode(data);
  image.binary=PNG.toBinaryArray(image.data,50,false);
  print(image.data.width,image.data.height)
  show(image.binary);
});

▸

✗

Create and Show Noisy Image

var noiseK = 0.01;
image.noise = image.binary.map (function (row) {
    return row.map(function(v) {
      if (Math.random()<noiseK) return v?0:1;
      else return v;
    })
  });
show(image.noise)

▸

✗

Das Array image.binary enthält ein binäres Bild (schwarz:0, weiß:1}

Bildglättung 1 (Naiver Ansatz)

Sehr naiver Rauschfilter durch Nachbarschaftsglättung. Wichtig: Binäre Bilder erlauben Grauwertinterpolation!
Ein Pixelwert wird durch die "Mehrheit" der Nachbarschaft gsetzt (1/0)

Bildglättung Majority [ca1]

{
  rows: 100,
  columns : 100,
  neighbors : 8,
  palette : ['white','black'],
  parameter : {
    thresHold:4,
  },
  cell : {
    name : 'mean',
    size : 4,
    // Die Zustandsvariablen einer Zelle
    state : { pixel:0, pixel0:0 },
    // Phase 1: Zustandsübergang ohne Berechnung!
    before : function () {
      this.pixel0 = this.pixel;
    },
    // Phase 2: Brechnen des nächsten Zustandes
    activity : function (neighbors,x,y) {
      var surrounding = this.ask(neighbors, 'count', 'pixel0');
      this.pixel = surrounding > this.thresHold?1:0;
    },
    // Phase 0: Einmalige Initialisierung der Zelle
    init : function (x,y) {
      this.pixel = this.data[y][x];
    },
    // Farbe aus Palette (Index) in Abhaengigkeit vom Zustand
    color : function () { return this.pixel ?  0:1 },
  },
  // Initialisierung mit Pseudozufallszahlen [0,1)
  data : image.noise,
  steps : 3,
  scheduler : 'UPRIGHT', // 'DOWNLEFT', 'RANDOM', 'RANDOM0'
  start :  [{ name: 'mean', distribution: 100 }],
}

▸

◼

✗

Aufgabe. A

Frage. A1 Untersuche die Abhängigkeit der Bildglättung von den Parametern thresHold und steps bei verschiedenen Rauschanteilen noiseK={0.01,0.1,0.3}. Wie können die Bildergebnisse bewertet werden (qualitativ)? Verwende den UPRIGHT Scheduler.

Frage. A2 Untersuche die Abhängigkeit der Bildglättung bei verschiedenen Scheduler Algorithmen. Welchen Einfluss hat die Reihenfolge der Zellaktivierung und Ein- und Zweiphasenaktivierung?

Bildglättung 2 (Musterbasiert)

Lese Rosin,2002
Versuche die im Artikel gezeigten Muster zur Rauschunterdrückung in folgende Code einzubauen. Teste den Algorithmus
Die Variable neighbors enthält alle acht Nachbarzellen in folgender Reihenfolge (an Rändern können einige Einträge null enthalten):

neighbors(x,y) = [
  { x:x-1,y:y-1, ... },
  { x:x  ,y:y-1, ... },
  { x:x+1,y:y-1, ... },
  { x:x-1,y:y,   ... },
  { x:x+1,y:y,   ... },
  { x:x-1,y:y+1, ... },
  { x:x  ,y:y+1, ... },
  { x:x+1,y:y+1, ... },
]

  +-----> (x)
  |
  |
  v
  (y)

  0 1 2 
  3 X 4
  5 6 7   (index in array)

Bildglättung durch Mustersuche und Regelsätzen [ca2]

{
  rows: 100,
  columns : 100,
  neighbors : 8,
  palette : ['white','black'],
  parameter : {
    rules : [
      {pattern:[0,0,0,0,0,0,0,0], pixel0:1, pixel:0 } // pattern:  pixel0 values of neighbors
    ]
  },
  cell : {
    name : 'mean',
    size : 4,
    // Die Zustandsvariablen einer Zelle
    state : { pixel:0, pixel0:0 },
    // Phase 1: Zustandsübergang ohne Berechnung!
    before : function () {
      this.pixel0 = this.pixel;
    },
    // Phase 2: Brechnen des nächsten Zustandes
    activity : function (neighbors,x,y) {
      var set=0;
      var test = neighbors.map(function (cell) {
        if (!cell) return 0;
        return cell.pixel0;
      })
      for(var pi=0;pi<this.rules.length;pi++) {
        var rule=this.rules[pi];
        if (rule.pattern.match(test) && this.pixel0==rule.pixel0) {
            this.pixel=rule.pixel; break 
        };
      };
    },
    // Phase 0: Einmalige Initialisierung der Zelle
    init : function (x,y) {
      this.pixel = this.data[y][x];
    },
    // Farbe aus Palette (Index) in Abhaengigkeit vom Zustand
    color : function () { return this.pixel ?  0:1 },
  },
  // Initialisierung mit Pseudozufallszahlen [0,1)
  data : image.noise,
  steps : 1,
  scheduler : 'UPRIGHT', // 'DOWNLEFT', 'RANDOM', 'RANDOM0'
  start :  [{ name: 'mean', distribution: 100 }],
}

▸

◼

✗

Kantendetektion mit Mustersuche und Regelsätzen [ca3]

// Plathalter für Experiment kantendetektion - aus obigen Code kopieren
{

}

▸

◼

✗

Aufgabe. B

Ergänze die Musterregeln damit auch schwarzes Rauschen reduziert wird
Nehme dann den Musterregelsatz für Rauschunterdrückung aus [Rosin,2002].
Nehme schließlich den Musterregelsatz für Kantendetektion aus [Rosin,2002].

Frage. B1 Untersuche die Abhängigkeit der Qualität der Bildglättung von den Parameter steps sowie scheduler bei verschiedenen Rauscnanteilen noiseK={0.01,0.1,0.3}. Wie können die Bildergebnisse bewertet werden (qualitativ)? Was funktioniert gut, ewann nicht? Ist das Ergebnis überhaupt abhängig von der Anzahl von Itertaionen (steps>1)?

Frage. B2 Funktioniert die Kantendetektion? Ist das Ergebnis abhängig on der Anzahl von Iterationen (steps>1)? Wird es vom Scheduler Algorithmus beeinflusst?

Frage. B3 Wie ist das Ergebnis bei RANDOM Scheduling? Wie müssten Zellen sich synchronisieren.

Created by the NoteBook Compiler Ver. 1.3.5 (c) Dr. Stefan Bosse