Softwaretechnologie für Fortgeschrittene Teil Thaller Stunde I: Bildverarbeitung I Köln 19....

Preview:

Click to see full reader

Citation preview

Softwaretechnologie für FortgeschritteneTeil Thaller

Stunde I: Bildverarbeitung I

Köln 19. November 2009

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

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

25

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.

26

Towers of Hanoi

S1 S2 S3 27

Towers of Hanoi

S1 S2 S3 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

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.

35

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.

36

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()); }

37

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

* 38

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

39

Minimal neighbour

Original Ergebnis

40

Ersetze in jeder Zeile

jedes Pixel

durch den niedrigsten Pixelwert der dieses

Pixels umschreibenden 3 x 3 Matrix.

Minimal neighbour

41

Minimal neighbour

42

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

43

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

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 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

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 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

50

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

51

Minimal neighbour

* 52

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.

53

Gegenstand

II. Bildverarbeitung I

54

Bildverarbeitung

55

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

Basisalgorithmus Bildverarbeitung

56

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

57

Basisalgorithmus Bildverarbeitung

58

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

59

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

60

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

61

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

62

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

63

Merke:

Bildverarbeitung muss performant sein!

Basistransformationen

64

Negation:

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

Basistransformationen

65

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

66

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

67

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

68

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

69

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

70

Nachgeschobene Interpolation zur Rotation:

offset[0]= -1; offset[1]= 1; offset[2]= xsize*-1; offset[3]= xsize;

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!

71

Recommended

Fachbereich 3 TZI - Bildverarbeitung Mathematik ... · TZI - Bildverarbeitung Mathematik / Informatik Fachbereich 3 21.04.05 Bildverarbeitung - Dr.-Ing. Th. Hermes 3 Einleitung ¾Bildpunktoperationen
Documents
Manfred Thaller Köln, 14. Oktober 2010
Documents
3D- Spieleprogrammierung Softwaretechnologie II Dozent: Herr Prof. Dr. Manfred Thaller WS 13/14 Referent: Christian Braun
Documents
3D-Grafik mit der TriBase-Engine Universität zu Köln Softwaretechnologie II WS 11/12 Dozent: Prof. Dr. M. Thaller Referentin: Nadya Steinert
Documents
Bildverarbeitung lassen sich nach verschiedenen Gesichtspunkten klassifizieren: Die in der Bildverarbeitung manipulierten Objekte lassen sich nach verschiedenen
Documents
Was ist Spiel? Erfahrung Bedeutung Vergnügung Narration Simulation Sozial Jonas Zimmer 24.01.2013 Softwaretechnologie II (Teil 2) Prof. Dr. Thaller
Documents
Softwaretechnologie für Fortgeschrittene Teil Thaller Stunde VI: Software Engineering II Köln 22. Januar 2015
Documents
Softwaretechnologie für Fortgeschrittene Teil Thaller Stunde VI: Information revisited
Documents
Aufgabe 1 - Bildverarbeitung - TU Dresden
Documents
AK Softwaretechnologie
Documents
Softwaretechnologie II (Teil 2): Simulation und 3D Programmierung Manfred Thaller SS 2013 Scripting Gems 6 Linda Scholz
Documents
Von der Planung bis zum Hauptmenü Seminar: Softwaretechnologie II Dozent: Prof. Manfred Thaller Referent: Jan Bigalke
Documents
Die Welt der Shader Universität zu Köln WS 14/15 Softwaretechnologie II (Teil 1) Prof. Dr. Manfred Thaller Referent: Lukas Kley Fortgeschrittene Techniken
Documents
Segmentierung in der medizinischen Bildverarbeitung
Documents
Softwaretechnologie für Fortgeschrittene Teil Thaller Stunde IV: Bildverarbeitung IV Köln 15. Januar 2015
Documents
Patrick Schwarzkopf Industrielle Bildverarbeitung Seite 1 08.11.2005 VISION 2005 Industrial Vision Days Industrielle Bildverarbeitung - Marktentwicklung
Documents
Softwaretechnologie für Fortgeschrittene Teil Thaller Stunde I: Bildverarbeitung I Köln 6. November 2014
Documents
Softwaretechnologie II (Teil 1): Simulation und 3D Programmierung Manfred Thaller WS 2011/2012 Stereo-3D-Grafik Linda Scholz
Documents
Manfred Thaller Köln, 16. Oktober 2008
Documents
Einführung in die Informationsverarbeitung Teil Thaller Stunde VI: Wege und warum man sie geht...... Graphen. Manfred Thaller, Universität zu Köln Köln
Documents