Softwaretechnologie für FortgeschritteneTeil Thaller
Stunde I: Bildverarbeitung I
Köln 6. November 2014
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
Soundex
Problem: 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.
3A, 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
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger
Tegenberger
Tekekenperger
7
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger
Tegenberger
Tekekenperger
T Regel 1
8
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger
Tegenberger
Tekekenperger
Tx Regel 2
9
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger
Tegenberger
Tekekenperger
T x Regel 3
10
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger
Tegenberger
Tekekenperger
T 2 Regel 4.2
11
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger
Tegenberger
Tekekenperger
T 2x Regel 5
12
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger
Tegenberger
Tekekenperger
T 2 x Regel 3
13
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger
Tegenberger
Tekekenperger
T 2 5 Regel 4.5
14
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger
Tegenberger
Tekekenperger
T 2 51 Regel 4.1
15
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger T251
Tegenberger
Tekekenperger
16
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger T251
Tegenberger
Tekekenperger
T Regel 1
17
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger T251
Tegenberger
Tekekenperger
Tx Regel 2
18
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger T251
Tegenberger
Tekekenperger
T 2 Regel 4.2
19
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger T251
Tegenberger
Tekekenperger
T 2x Regel 3
20
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger T251
Tegenberger
Tekekenperger
T 2 5 Regel 4.5
21
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger T251
Tegenberger T251
Tekekenperger
T 2 51 Regel 4.1
22
Soundex
Problem: Welche der drei folgenden Namen sind gleich?
Theckenperger T251
Tegenberger T251
Tekekenperger
T 2 2 Regeln 4.2 / 5 / 3
23
Soundex
Problem: 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 Hanoi
Situation 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 Hanoi
Lö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 Hanoi
Lö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 Hanoi
Lösung III
function transport( int n, stack spindel1, stack spindel2, stack spindel3) { if (n >1) transport(n-1,spindel1,spindel3,spindel2); schritt(spindel1,turm2); if (n>1) transport(n-1,spindel3,turm2,spindel1); }
function schritt( stack spindel1, stack spindel2) { spindel2.push(spindel1.pop()); }
39
Towers of Hanoi
Fragen
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 250
45
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 250
46
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 250
47
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 250
48
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 250
49
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 250
50
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 250
51
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 250
52
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 250
53
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 I
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);
Basistransformationen
71
Gradgenaue Rotation:
for (int y=0;y<image->height();y++) { h=image->height()-y; for (int x=0;x<image->width();x++) { rho=sqrt((double)(x*x)+(double)(h*h)); theta=atan((double)h/(double)x)-usearc; newx=(int)rint(rho*cos(theta)+xmin); newy=ysize-((int)rint(rho*sin(theta)+ymin)); *(inter+(newy*xsize)+newx)= *(image->scanLine(y) + x); } }
72
Bildschirm
73
Bildschirm mit Bild
74
Bildschirm mit Bild
75
Bildschirm mit Bild, 45 °
76
Bildschirm mit Bild, 45 °
77
Bildschirm mit Bild, 45 °
78
Rotation, Prinzip
79
Rotation, Stufe I
80
Rotation, Stufe II
81
Rotation, Stufe III
Erinnerung: Winkelfunktionen
82
y/r = sin(β)
β = asin(y/r)
x/r = cos(β)
β = acos(x/r)
y/x = tan(β)
β = atan(y/x)
Basistransformationen
83
Gradgenaue Rotation / Erzeugung des Bildes:
s. vollständigen Quellcode / sorry, zu umfangreich für Powerpoint
Basistransformationen
84
Gradgenaue Rotation / Vorbereitungen:
double arcfactor=M_PI/180.0; short int *inter, *use; int size; double rho,theta,usearc,xmin,ymin; int xsize,ysize,newx,newy,h; QImage result=TIrotatetarget(image,angle,&xmin,&ymin);usearc=arcfactor*angle; xsize = result.width(); ysize = result.height(); size=(xsize+1)*(ysize+1); inter=new short int[size];for (int i=0;i<size;i++) inter[i]= -1;
Basistransformationen
85
Gradgenaue Rotation:
for (int y=0;y<image->height();y++) { h=image->height()-y; for (int x=0;x<image->width();x++) { rho=sqrt((double)(x*x)+(double)(h*h)); theta=atan((double)h/(double)x)-usearc; newx=(int)rint(rho*cos(theta)+xmin); newy=ysize-((int)rint(rho*sin(theta)+ymin)); *(inter+(newy*xsize)+newx)= *(image->scanLine(y) + x); } }
Basistransformationen
86
Nachgeschobene Interpolation zur Rotation:
offset[0]= -1; offset[1]= 1; offset[2]= xsize*-1; offset[3]= xsize;use=inter;
for (int y=0;y<result.height();y++) { for (int x=0;x<result.width();x++,use++) { if (*use>=0) *(result.scanLine(y)+x) = *use; else if (*(use-1)<0 || *(use+1)<0) *(result.scanLine(y)+x) = 0; else { *(result.scanLine(y)+x) = *(use+offset[now]); if (++now==4) now=0; } }}
Danke für heute!
87