Download ppt - 1 Bildtransformationen New worlds, new opportunities, new challenges. 4

1

Bildtransformationen

“New worlds, new opportunities, new challenges.”

4

2

Bildtransformation Transformation der Bildinformation in eine neue

Darstellung Ausnutzen bestimmter Eigenschaften der

Darstellung zur Bildverarbeitung oder -analyse Rücktransformation der Darstellung in den

Bildbereich

3

Bildtransformation

Unitäre Bildtransformationen Fourier Transformation Cosinus Transformation Walsh-Hadamard Transformation Haar Transformation ...

Parametrische Bildtransformationen Hough Transformation Radon Transformation ...

4

Wichtige Anwendungsgebiete Allgemein Dimensionsreduktion Dekorrelation

Speziell Bildfilterung

Filterung im Frequenzraum

Bildkompression JPEG, etc

Bildmerkmale für Mustererkennung & Klassifikation z.B. Objekterkennung, Gesichtserkennung

5

Fourier-Reihen Erstpublikation 1807, Buch 1822 Übersetzung auf Englisch in 1878 Darstellung von (praktisch) jeder periodischen

Funktion mit Periode T als eine (ggf. unendliche) Summen-Reihe von gewichteten Sinus und Cosinus Wellen

Verlustfreie, invertierbare Transformation

6

Fourier-Reihe

7

Fourier-Reihe))sin()cos(()(

10 tnbtnaatf n

nn

T

dttfT

a0

0 )(1

für 0 < t < T

T

n

T

n

dttntfT

b

dttntfT

a

0

0

)sin()(2

)cos()(2

für n ≥ 1

für n ≥ 1

Fourier-Bereich: ALLE Werte der Funktion f(t) werden bei der Berechnung von dem jeweiligen an und bn einbezogen

Ortsbereich: An jeder Stelle ergibt sich der Funktionswert durch die Überlagerung ALLER sin & cos Wellen

8

Fourier-Reihe

n

tinn

nnn

nnn

nnn

nnn

ega

tnda

tnca

tnbtna

tnbtnaatf

0

10

10

0

10

)sin(

)cos(

)sin()cos(

)sin()cos()(

xjxe xj 2sin2cos2

9

Beispiel Rechteck-Signal

10

11

12

13

14

15

16

17

Beispiel Sägezahn-Signal

18

19

20

21

22

23

24

25

Fourier-Reihe

n

tinn

nnn

nnn

nnn

nnn

ega

tnda

tnca

tnbtna

tnbtnaatf

0

10

10

0

10

)sin(

)cos(

)sin()cos(

)sin()cos()(

xjxe xj 2sin2cos2

26

Fourier Transformation

F f x e dx

f x F e d

j x

j x

( ) ( )

( ) ( )

2

2

xjxe xj 2sin2cos2

ALLE Werte der Funktion f(x) werden bei der Berechnung von dem jeweiligen F(w) einbezogen

27


Fourier Transformierte ist komplex

F F e j( ) ( ) ( )

Aufspaltung in Betrag und Phase

F F F( ) ( ) ( ) 2 2

( ) arctan

( )

( )

F

F

“Spektrum”

“Phase”

F F j F( ) ( ) ( )

28


Beispiel

F f x e dx

A e dx

A

je

A

je

A

je e e

AX e

j x

j x

X

j x X

j X

j X j X j X

j X

( ) ( )

sin( )

2

2

0

20

2

2

21

2

FA

X e

AXX

XAX X

j X( ) sin( )

sin( )

( )

sinc

X

A

AX

X 1

f x( )

F( )

29

Impuls & sinc

30

2D Fourier Transformation

F f x y e dxdy

f x y F e d d

j x y

j x y

( , ) ( , )

( , ) ( , )

( )

( )

1 22

1 22

1 2

1 2

1 2

F F F( , ) ( , ) ( , ) 1 2 1 2

2

1 2

2

( , ) arctan

( , )

( , )

1 2

1 2

1 2

F

F

31

Abtastungf n f x n x n N[ ] ( ), { , , } 0 0 1

Abtastungsgröße

32

Diskrete Fourier Transformation

uN x

1F u

Nf n e

f nN

F u e

n

Nj

un

N

u

Nj

un

N

[ ] [ ]

[ ] [ ]

1

10

1 2

0

1 2

33

Diskrete 2D Fourier Transformation

F v uMN

f m n e

f m nMN

F v u e

n

Nj

un

N

vm

M

m

M

u

Nj

un

N

vm

M

v

M

[ , ] [ , ]

[ , ] [ , ]

1

1

0

12

0

1

0

12

0

1

34

Fourier Spektrum Eine diskrete 2D Matrix mit M x N Werte (= digitales Bild)

wird in eine M x N Matrix mit komplexen Fourier-Koeffizienten transformiert

Jeder dieser komplexen Fourier Koeffizienten läßt sich in Polarkoordinaten ausdrücken:

F F e j( ) ( ) ( )

F F F( ) ( ) ( ) 2 2

( ) arctan

( )

( )

F

F

“Amplituden Spektrum”

“Phasen Spektrum”

35

Fourier Spektrum

N x M Pixel N x M Frequenzen

real komplex

Bild Spektrum

Jeder Eintrag in dem Spektrum definiert eine Cosinus-Welle

Amplitude = Höhe einer Welle (=„Wichtigkeit“)

Phase = Verschiebung der Welle zum Ursprung

Abstand zum Mittelpunkt = Frequenz der Welle

Ausbreitung = Verbindungsgerade zum Mittelpunkt

36

Fourier Wellen Fourier-Bereich: ALLE Werte der Funktion f(t)

werden bei der Berechnung von dem jeweiligen F(w) einbezogen!

ALLE Funktionswerte werden bei der Berechnung JEDER Welle berücksichtigt

Ortsbereich: An jeder Stelle ergibt sich der Funktionswert durch die Überlagerung ALLER Wellen!

JEDE Welle ist ÜBERALL im Bild aktiv

37

Fourier Wellen

38

Fourier Wellen

39

Fourier-Wellen

40

Fourier-Wellen

41

Fourier-Wellen

42

2D Fourier Transformation

f x y( , ) F( , ) 1 2

43

Spektrum-Abtastdichte Relation

44

Fourier Spektra

45

Fourier Spektra

46

Fourier Spektra

47

Fourier Spektra

48

Eigenschaften

f m m n n

F v u ej

un

N

vm

M

[ , ]

[ , ]

0 0

2 0 0

Translation

0

49

Eigenschaften

f r r

F

[ sin , cos ]

[ sin , cos ]

0 0

0 0

Rotation

50

Eigenschaften

F v u F v u N F v M u F v M u N[ , ] [ , ] [ , ] [ , ]

Periodizität

die DFT eines Bildes ist periodisch

Symmetrie

],[],[ uvFuvF

reel ][ falls ][ ][ m,nf,-v, -uF*v,uF

die DFT eines Bildes ist symmetrisch

51

Eigenschaften

Separierbarkeit

f m n[ , ]

n

m

F m u[ , ]

u

m

F v u[ , ]

u

v

Transformation Transformation

der Zeilen der Spalten

F v uMN

e f m n e

f m nMN

e F v u e

jvm

M

n

Nj

un

N

m

M

jvm

M

u

Nj

un

N

v

M

[ , ] [ , ]

[ , ] [ , ]

1

1

2

0

1 2

0

1

2

0

1 2

0

1

52

Eigenschaften

F(0,0) beinhaltet den MxN skalierten Mittelwert des Bildes (i.d.R. ziemlich großer Wert)

Linearität:

53

Fourier Spektra

54

Fourier Spektra

55

Fourier Spektra

56

Fourier Spektra

57

Fourier Spektra

58

Translation & Rotation: Power

59

Translation & Rotation: Phase

60

Manipulation des Fourier Spektrums

Amplitude AmplitudePhase

r eaj a

r eaj b r eb

j a

r ebj b

61

Manipulation des Fourier SpektrumsPhase

Amp = 1Phase = Frau

Amp = Frau Phase = 0

Amp = RechteckPhase = Frau

Amp = FrauPhase = Rechteck

62

Bildtransformation

Fourier Transformation+ Transformierte repräsentiert Bildfrequenzen

(Manipulation)– Transformierte komplex (Spektrum & Phase)– Fließkomma Koeffizienten – Transformierte redundant (Symmetrie)

Suche nach anderen Transformationen zur geeigneten Informationsdarstellung

63

Parametrische Transformation Darstellung der Bildinformation anhand von

veränderten Ortsraumparametern, z.B.

Transformation ist nicht zwingend orthogonal (in der Regel nicht invertierbar)

Bestimmte Informationen sind in der transformierten Darstellung einfacher abzulesen

f m n f r[ , ] [ , ]

64

Radon Transformation Orthogonale Projektion des Bildes bezüglich des

Bildmittelpunktes in Abhängigkeit des Winkels

R x f x y x y dy ( ) ( cos sin , sin cos )

x x y

y x y

cos sin

sin cos

65

Radon Transformation

x

y

R x0 ( )

R x45 ( )

R x90 ( )

66


x

x

x

67


x

max ( ) ,R x xo 94 101

x

68


69


70

Unitäre Bildtransformation

G A FA

F A GA

M N

M

T

N

T* *

Definition einer separablen & symmetrischen Transformation

A A I A A IN N

T

M M

T* *, Orthonormalität

ZeilentransformationBild

Transformiertes Bild

Spaltentransformation

dim( ) , dim( )

dim( ) , dim( )

F G

A A

M N M N

N N M MN M

71

Unitäre Bildtransformation Basisbilder (2D Basisvektoren)

A a ak l k l

T

,* * *

F G A , ,*k l

Ein Bild läßt sich als Linearkombination der mit den Transformationskoeffizienten gewichteten Basisbilder darstellen

F

A a A aM k N l

,

72

Beispiel: Basisbilder des 8x8 Bildraums0 1 3 1 2 0 1 2

2 3 2 0 1 2 2 2

1 1 3 0 2 2 0 1

1 1 1 1 1 2 2 2

0 2 1 1 0 0 0 2

3 0 3 1 0 0 2 2

3 3 0 1 2 1 2 0

2 2 1 1 1 1 1 0

, =

• Lege jede Maske über das Bild• Multipliziere Maske & Pixel paarweise• Addiere alle Teilergebnisse zu einer Zahl• Trage diese an der Masken-Position im transformierten Bild

=> ALLE Pixel des Originals tragen an JEDER Stelle des transformierten Bildes bei!

73

Walsh-Hadamard Transformation Reelle Transformation Schnell (Addition/Subtraktion) Implementierung mit ganzzahligen Koeffizienten möglich Befriedigende Datendekorrelation

A

1

8

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

74

Walsh-Hadamard Transformation

75

Haar Transformation

A

1

8

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

2 2 2 2 0 0 0 0

0 0 0 0 2 2 2 2

2 2 0 0 0 0 0 0

0 0 2 2 0 0 0 0

0 0 0 0 2 2 0 0

0 0 0 0 0 0 2 2

Reelle Transformation Schnell Ortsinformation bleibt teilweise erhalten Mäßige Datendekorrelation

76

Haar Transformation

77

Cosinus Transformation

11,2

)12(cos

2

0,1

][Nu

N

un

N

uNua

Reelle Transformation Pseudofrequenzdarstellung

(DCT ist nicht der Realteil der DFT!) Exzellente Datendekorrelation Effiziente SW, beschleunigte HW

78

Cosinus Transformation