Softwaretechnologie für Fortgeschrittene Teil Eide Stunde I: Bildverarbeitung (auf Basis von...

Softwaretechnologie für FortgeschritteneTeil Eide

Stunde I: Bildverarbeitung(auf Basis von Thaller 2014–15)

Köln 26. November 2015

I. Rekapitulation

2

Abstrakte Überlegungen zum Wesen der Information.

Darstellung von Information in geeigneten Strukturen auf (digitalen) Rechnern.

Entwicklung von Algorithmen, die auf diesen Strukturen operieren.

Einbettung in eine Methodologie, die die Konstruktion von Programmen aus geeigneten Strukturen und Algorithmen ermöglicht. 3

Gegenstand

1. "Selbstabbildende Information". Es kann "gerechnet" werden. Bilder.

2. "Kodierte Information". Zeichenketten und Teilketten können verglichen werden. Texte.

3. "Symbolische Information". Terme können verglichen werden. Terminologien, "Ontologien" u.ä.

„Arten“ von Information

4

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

5

Soundex1 Das erste Zeichen jedes Namens wird beibehalten.2 W und H werden ignoriert.

3 A, E, I, O, U und Y ergeben keinen Codewert, gelten jedoch als "Trenner" (s.Regel 5).

4 Die anderen Zeichen werden nach folgenden Regeln umgewandelt. 4.1 B, P, F, V ==> 1

4.2 C, G, J, K, Q, S, X, Z ==> 2

4.3 D, T ==> 3

4.4 L ==> 4

4.5 M, N ==> 5

4.6 R ==> 6

5

Ergeben zwei aufeinanderfolgende Zeichen denselben Code, wird er nur einmal gewertet. Sind sie durch einen "Trenner" (s. oben Regel 3) getrennt, wird er jedoch wiederholt. 6

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

7

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

T Regel 1

8

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

Tx Regel 2

9

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

T x Regel 3

10

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

T 2 Regel 4.2

11

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

T 2x Regel 5

12

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

T 2 x Regel 3

13

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

T 2 5 Regel 4.5

14

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger

Tegenberger

Tekekenperger

T 2 51 Regel 4.1

15

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger T251

Tegenberger

Tekekenperger

16

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger T251

Tegenberger

Tekekenperger

T Regel 1

17

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger T251

Tegenberger

Tekekenperger

Tx Regel 2

18

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger T251

Tegenberger

Tekekenperger

T 2 Regel 4.2

19

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger T251

Tegenberger

Tekekenperger

T 2x Regel 3

20

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger T251

Tegenberger

Tekekenperger

T 2 5 Regel 4.5

21

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger T251

Tegenberger T251

Tekekenperger

T 2 51 Regel 4.1

22

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger T251

Tegenberger T251

Tekekenperger

T 2 2 Regeln 4.2 / 5 / 3

23

SoundexProblem: Welche der drei folgenden Namen sind gleich?

Theckenperger T251

Tegenberger T251

Tekekenperger T225

*24

Ein Algorithmus ist eine Funktion f(Dein, Daus), die Eingabedaten Dein in Ausgabedaten Daus schrittweise transformiert und dabei bestimmte Bedingungen erfüllt.

Algorithmen: Definition

25

1.Exaktheit. Die Funktion f kann präzise auf formale Weise beschrieben werden.

2.Finitheit. Die Beschreibung von f ist endlich lang. 3.Vollständigkeit. Die Beschreibung von f umfasst alle vorkommenden Fälle.

4.Effektivität. Die Einzelschritte sind elementar und real ausführbar.

5.Terminierung. Die Funktion f hält nach endlich vielen Schritten an und liefert ein Resultat.

6.Determinismus. Die Funktion f liefert bei gleichen Eingabewerten stets das gleiche Ergebnis, wobei die Folge der Einzelschritte für jeden Eingabewert genau festgelegt ist.

Algorithmen: Eigenschaften

26

1. "Selbstabbildende Information". Es kann "gerechnet" werden. Bilder.

2. "Kodierte Information". Zeichenketten und Teilketten können verglichen werden. Texte.

3. "Symbolische Information". Terme können verglichen werden. Terminologien, "Ontologien" u.ä.

„Arten“ von Information

27

Towers of HanoiSituation in einem Tempel in Hanoi: • Ein Turm von 100 Scheiben auf einer Spindel (S1). • Eine leere Spindel (S2). • Eine weitere leere Spindel (S3).

Transportiere S1 so nach S2 - wobei S3 als Zwischenlager verwendet werden darf - dass:• Jeweils nur die oberste Scheibe von einem Turm genommen wird. • Niemals eine größere Scheibe auf einer kleineren liegt.

Prophezeiung: Ist das erledigt, ist das Ende der Welt gekommen.

28

Towers of Hanoi

S1 S2 S3 29

Towers of Hanoi

S1 S2 S3 30

Towers of Hanoi

S1 S2 S3 31

Towers of Hanoi

S1 S2 S3 32

Towers of Hanoi

S1 S2 S3 33

Towers of Hanoi

S1 S2 S3 34

Towers of Hanoi

S1 S2 S3 35

Towers of Hanoi

S1 S2 S3 36

Towers of HanoiLösung I

1. Finde jemand, der die obersten 99 Scheiben von S1 nach S3 transportiert.

2. Transportiere die unterste Scheibe von S1 nach S2. 3. Finde jemand, der die obersten 99 Scheiben von S3 nach S2

transportiert.

37

Towers of HanoiLösung II

1. Besteht der zu transportierende Turm aus mehr als einer Scheibe, finde jemand, der einen Turm von n-1 Scheiben von S1 nach S3 transportiert. Nutze S2 als Zwischenablage.

2. Transportiere selbst die unterste Scheibe von S1 nach S2. 3. Besteht der zu transportierende Turm aus mehr als einer Scheibe,

finde jemand, der einen Turm von n-1 Scheiben von S3 nach S2 transportiert. Nutze S1 als Zwischenablage.

38

Towers of HanoiLösung III

function transport( int n, stack spindel1, stack spindel2, stack spindel3) { if (n >1) transport(n-1,spindel1,spindel3,spindel2); schritt(spindel1,spindel2); if (n>1) transport(n-1,spindel3,spindel2,spindel1); }

function schritt( stack spindel1, stack spindel2) { spindel2.push(spindel1.pop()); }

39

Towers of HanoiFragen

1. Wie viele Mitarbeiter werden benötigt? n 2. Wieviele Transferschritte? 2n -13. Wie lange? 2100-1 Schritte == ca. 1030

1 Schritt == 1 Sekunde ==> ca. 1030 Sekunden == ca. 4 * 1022 Jahre

* 40

1. "Selbstabbildende Information". Es kann "gerechnet" werden. Bilder.

2. "Kodierte Information". Zeichenketten und Teilketten können verglichen werden. Texte.

3. "Symbolische Information". Terme können verglichen werden. Terminologien, "Ontologien" u.ä.

„Arten“ von Information

41

Minimal neighbour

Original Ergebnis

42

Ersetze in jeder Zeile jedes Pixel durch den niedrigsten Pixelwert der dieses Pixels umschreibenden 3 x 3 Matrix.

Minimal neighbour

43

Minimal neighbour

44

Minimal neighbour

250 250 250 250 250 250 250 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 250 250 250 250 250 250 25045

Minimal neighbour

250 250 250 250 250 250 250 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 250 250 250 250 250 250 25046

Minimal neighbour

250 250 250 250 250 250 250 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 250 250 250 250 250 250 25047

Minimal neighbour

250 250 250 250 250 250 250 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 250 250 250 250 250 250 25048

Minimal neighbour

250 250 250 250 250 250 250 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 250 250 250 250 250 250 25049

Minimal neighbour

250 250 250 250 250 250 250 250 250 250 250 250

250 250 50 50 50 50 50 50 50 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 250 250 250 250 250 250 25050

Minimal neighbour

250 250 250 250 250 250 250 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 250 250 250 250 250 250 25051

Minimal neighbour

250 250 250 250 250 250 250 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 250 250 50 50 250 250 250 250 250

250 250 250 50 50 50 50 50 50 250 250 250

250 250 250 250 250 250 250 250 250 250 250 25052

Minimal neighbour

250 250 50 50 50 50 50 50 50 50 250 250

250 250 50 50 50 50 50 50 50 50 250 250

250 250 50 50 50 50 50 50 50 50 250 250

250 250 250 250 50 50 50 50 250 250 250 250

250 250 250 250 50 50 50 50 250 250 250 250

250 250 250 250 50 50 50 50 250 250 250 250

250 250 250 250 50 50 50 50 250 250 250 250

250 250 250 250 50 50 50 50 250 250 250 250

250 250 250 250 50 50 50 50 250 250 250 250

250 250 50 50 50 50 50 50 50 50 250 250

250 250 50 50 50 50 50 50 50 50 250 250

250 250 50 50 50 50 50 50 50 50 250 25053

Minimal neighbour

* 54

Abstrakte Überlegungen zum Wesen der Information.

Darstellung von Information in geeigneten Strukturen auf (digitalen) Rechnern.

Entwicklung von Algorithmen, die auf diesen Strukturen operieren.

Einbettung in eine Methodologie, die die Konstruktion von Programmen aus geeigneten Strukturen und Algorithmen ermöglicht. 55

Gegenstand

II. Bildverarbeitung

56

Bildverarbeitung

57

Bildverarbeitung hier ::= Bearbeitung von Bildern, die als strukturierter Bytestream im Memory geladen sind.

Basisalgorithmus Bildverarbeitung

58

Unter Annahme eines Bildes als:

struct image { int zeilen; int spalten; unsigned char *bytes; } o;

for (i=0;i<o.spalten;i++) for (j=0;j<o.zeilen;j++) transform(* (o.bytes + (j*spalten) + i) );

Ein Algorithmus ist eine Funktion f(Dein, Daus), die Eingabedaten Dein in Ausgabedaten Daus schrittweise transformiert und dabei bestimmte Bedingungen erfüllt.

Algorithmen: Definition

59

Basisalgorithmus Bildverarbeitung

60

Oder allgemeiner:

struct image { int zeilen; int spalten; pixel *pixel; } o;

for (i=0;i<o.spalten;i++) for (j=0;j<o.zeilen;j++) transform(* (o.pixel + (j*spalten) + i) );

Basisalgorithmus Bildverarbeitung

61

Eingebunden in den Kontext von Qt (i.e., QImage):Beispiel: Negation 8 Bit

for (int y=0;y<image->height();y++) for (int x=0;x<image->width();x++) { oldVal = *(image->scanLine(y) + x); newVal=255-oldVal; *(image->scanLine(y) + x) = newVal; }

Basisalgorithmus Bildverarbeitung

62

Eingebunden in den Kontext von Qt (i.e., QImage):Beispiel: Negation 24 Bit

for (int y=0;y<image->height();y++) for (int x=0;x<image->width();x++) { RGB=(QRgb *)image->scanLine(y) + x; oldRed = qRed(*RGB); newRed=255-oldRed; oldGreen = qGreen(*RGB); newGreen=255-oldGreen; oldBlue = qBlue(*RGB); newBlue=255-oldBlue; *RGB = qRgb(newRed,newGreen,newBlue); }

Basisalgorithmus Bildverarbeitung

63

Dabei gilt jedoch:

for (int y=0;y<result.height();y++) { for (int x=0;x<result.width();x++) { *(result.scanLine(y) + x) = meineTransformation(*(image.scanLine(y)) ; }

Etwa eine Größenordnung langsamer als:

Basisalgorithmus Bildverarbeitung

64

for (int y=0;y<result.height();y++) { newpixel=result.scanLine(y); oldpixel=image.scanLine(y); for (int x=0;x<result.width();x++) *(newpixel++) = meineTransformation(*(oldpixel++)); }

Basisalgorithmus Bildverarbeitung

65

Merke:

Bildverarbeitung muss performant sein!

Basistransformationen

66

Negation:

oldVal = *(image->scanLine(y) + x);newVal=255-oldVal;*(image->scanLine(y) + x) = newVal;

Basistransformationen

67

Horizontale Spiegelung:

for (int y=0;y<image->height();y++) for (int target=0,source=image->width()-1; target<limit;target++,source--) { pixel=*(image->scanLine(y) + source); *(image->scanLine(y) + source) = *(image->scanLine(y) + target); *(image->scanLine(y) + target) = pixel; }

Basistransformationen

68

Vertikale Spiegelung:

for (int target=0,source=image->height()-1; target<limit;target++,source--) for (int x=0;x<image->width();x++) { pixel=*(image->scanLine(source) + x); *(image->scanLine(source) + x) = *(image->scanLine(target) + x); *(image->scanLine(target) + x) = pixel; }

Basistransformationen

69

Farbbandextraktion (Qt spezifisch, lookup table):

for (int y=0;y<image->height();y++) for (int x=0;x<image->width();x++) { RGBval=image->colorTable() [*(image->scanLine(y) + x)]; pixel=qRed(RGBval); *(result.scanLine(y) + x) = pixel; }

Basistransformationen

70

Quadrantenrotation:

for (int oldy=0,newx=image->height()-1;oldy<image->height(); oldy++,newx--) for (int oldx=0,newy=0;oldx<image->width(); oldx++,newy++) *(result.scanLine(newy) + newx) = *(image->scanLine(oldy) + oldx);

71

y/r = sin(β)

β = asin(y/r)

x/r = cos(β)

β = acos(x/r)

y/x = tan(β)

β = atan(y/x)

Gradgenaue Rotation: Winkelfunktionen

Basistransformationen

Danke für heute!

72