Teil IV-A: Signal- und Bildverarbeitung – Methoden · • Mittels Fourier-Analyse wird deren Darstellung in Form eines trigonometrischen Polynoms gezeigt • Die einzelnen harmonischen

Teil IV-A: Signal- und Bildverarbeitung – Methoden

1. Aufgaben der Signal- / Bildverarbeitung

2. Elementare Verarbeitungsmethoden

3. 2D Fourier-Transformation und Faltung

Signalveränderung / -transformation

§ Verbesserung

Rauschunterdrückung, Verbesserung des Signal-Rausch-Verhältnis, Kontrast, ...

§ Anpassung

Registrierung mehrerer Signale zwecks Vergleich, ...

Aufgaben der Signal- / Bildverarbeitung

Signalveränderung / -transformation

§ Verbesserung

Rauschunterdrückung, Verbesserung des Signal-Rausch-Verhältnis, Kontrast, ...

§ Anpassung

Registrierung mehrerer Signale zwecks Vergleich, ...

Signalverarbeitung

§ Detektion von Kontrasten

Bestimmung von Randkonturen, ...

§ Segmentierung und Extraktion von Merkmalen

Regionenbestimmung, Merkmale für Klassifikation, ...

Aufgaben der Signal- / Bildverarbeitung

Transformation von Intensitätswerten auf der Basis individueller Bildpunkte

Invertierung, Streckung, Stauchung, globale Schwellwerte

Schema: direkte Zuordnung von Ein-/Ausgabe-Wertepaaren

hier: Grauwerte ~ Intensitäten

Elementare Verarbeitungsmethoden Punktoperationen zur Grauwertransformation

T(g) = g*

25500

255

T(g )in

gT

Schwellwertgout

gin

T(g )

25500

255

gout

in

g2g1

g*2

g*1

Streckung, Stauchung

gin2550

0

255 T(gin)

gout

gin

Invertierung

Bsp. 1: Invertierung Röntgenbild

(J.C. Rush. The image processing handbook, 3rd ed. CRC Press, 1999)

Bsp. 2: Bild „Tomo1451.jpg“, Streckung mittlerer Grauwerte (mittels ‚xv‘, UNIX)

Beobachtung: Struktur im mittleren Grauwertbereich wird besser sichtbar;Details in dunklen und sehr hellen Bereichen gehen verloren

Bsp. 3: Bild „Cell.jpg“, Binarisierung (mittels ‚xv‘, UNIX)

Beobachtung: Die Bildstruktur wird in zwei Klassen eingeteilt:schwarz - Zellkerneweiss - Rest

Eigenschaften:

i. Plazierung von ( g1, g1* ) und ( g2 , g2* ) legt die Form der

Streckung T‘( . ) > 1bzw.

Stauchung T‘( . ) < 1 fest

ii. Lineare Abschnitte der Transformation T( . ) mit T‘([ga .. ge]) > 0

è Erhaltung der Ordnung der Funktionswerte

iii. mit g1 = g2 und g1* = 0, g2* = Imax

è T( . ) definiert Schwellwertfunktion mit globaler Schwelle T = gl zur

Erzeugung von Binärbildern

Histogramm-Linearisierung (für diskretes Grauwertspektrum)

Diskrete Intensitätswerte mit relativen Häufigkeiten:

Histogramm:

( )kg gρ

kg

255,,1,0, K=kg

g

relative Summenhäufigkeit

relative Summenhäufigkeit (~ Wahrscheinlichkeitsdichtefunktion, pdf)

Bsp. : (aus R.C. Gonzalez, P. Wintz. Digital image processing, Addison-Wesley, 1977)

geg. : 64 x 64 Bild, mit b = 3 : G = {0, 1, ..., 23 - 1 = 7}Grauwertverteilung (normiert : [0, 1]) :

g anz( gk ) ρρg ( gk ) = anz( gk ) / ( 642 )

7901023

85065632924512281

0.190.250.210.160.080.060.030.02

g0 = 0g1 = 1/7g2 = 2/7g3 = 3/7g4 = 4/7g5 = 5/7g6 = 6/7g7 = 1

Transformationsfunktion mittels relativer Summenhäufigkeit und

Abbildung auf normierte Funktionswerte Gnorm = {0, 1/7, 2/7, ..., 1} :

s gknormk

01234567

0.190.440.650.810.890.950.981.00

1/73/75/76/76/7

111

k (1/7 ~ 0.14)

Anmerkung : diskretes Histogramm ~ Approximation einer pdf

à perfekte lineare Histogramme sind eher selten ... !

.

.

≈ 0.143≈ 0.429≈ 0.714≈ 0.857≈ 0.857

Grauwertabbildung :

Abbildung : g sk

7901023

85065632924512281

g0 = 0g1 = 1/7g2 = 2/7g3 = 3/7g4 = 4/7g5 = 5/7g6 = 6/7g7 = 1

::::::::

s0 = 1/7s1 = 3/7s2 = 5/7

s3 = 6/7

s4 = 1

:::

:

:

7901023

850

985

448

k

(R.C. Gonzalez, R.E. Woods. Digital image processing. Addison-Wesley, 1993)

Anwendungsbeispiel :

(J.C. Rush. The image processing handbook, 3rd ed. CRC Press, 1999)

Primäre Zielsetzung bei der Bildfilterung

Filterverfahren

Bildverbesserung Merkmale

Bildglättung Kontrastdetektion

meist linearauch nicht-linear

meist linearauch nicht-linear

Verfahren / Methoden

(Lineare) Filterung

Lineare Filter und ihre Eigenschaften

Aufgabe :

Generelles Ziel (der ersten Verarbeitungsschritte) :

Abschwächung oder Betonung bestimmter Bereiche

des Frequenzspektrums einer Signal- / Bildfunktion

Extraktion relevanter Bildinhalte

Lineare Filterung und (diskrete) Faltung zur Rauschunterdrückung

§ Problem: Elimination von Störungen (~ hochfrequentes (additives) Rauschen)

§ Ansatz: Beseitigung der lokalen Variationen („Ausreisser“) durch Mittelung

benachbarter Funktionswerte

Konzept: • diskrete (numerische) Maske benachbarter Funktionswerte

• Maske wird zeilenweise in allen

Spalten, d.h. an jedem Bildpunkt, angewendet

(à Behandlung der Ränder)

§ Box-Filter (3 x 3 Maske)

Koeffizienten :

diskrete Faltung ( Bild : f(x, y) ) :

g*(x, y)

x = 0, 1, ..., M-1; y = 0, 1, ..., N-1

Verallgemeinerung (m x m Matrix) :

Diskrete Faltung (für beliebige Maskengrössen) :

m = 2k + 1

m

Box-Tiefpass Filter unterschiedlicher

Grössen – Beispielanwendung


N x N Maske, N = {3, 5, 7, 15, 25}

Kontinuierlicher Fall

geg. : 2D Signalfunktion (Ortsbereich) f(x, y)

à entsprechend der 1D Fourier-Transformation gelten die Transformationspaare(hier: balancierte Notation durch Aufteilung der Skalierungsfaktoren !):

Transformation vom Orts- in den Frequenzraum

mit u = fx , v = fy ;ωωx = 2ππ / Tx = 2ππ u , ωωy = 2ππ / Ty = 2ππ v

2D Fourier-Transformation und Faltung2D Transformationspaar

mit

Ψ

λ

y

x

2D Cosinus-Welle

λ = Tx cos Ψ Tx = l / cos Ψ

λ = Ty cos(90 – Ψ) Ty = l / sin Ψ

sin Ψ

λ

Tx

Ty

Ψ

Ψ

Diskreter Fall

1. Transformation vom Orts- in den Frequenzraum:

i. Matrix mit N x M Bildpunkten

für u = 0, 1, ..., M-1 und v = 0, 1, ..., N-1

Abtastabstände: ∆u = 1 / (M ∆x) und ∆v = 1 / (N ∆y)

ii. quadratische Matrix mit N Bildpunkten (M = N)2

Transformation

Spalten

Zeilen

2. Rücktransformation

i. für N x M Matrix

ii. für quadratische Matrix (N Bildpunkte)2

Bildbeispiele von Amplitudenspektren verschiedener Eingangssignale

Isotropie:Frequenzen in alle Richtungen

Unschärfeprinzip:Frequenzen orthogonal zum Strukturverlauf


Fourier- / Amplituden-Spektrum

Visualisierung von Fourier-Spektren

à Häufig hoher Dynamikbereich in Fourier- (Amplituden-) Spektren durch Dominanz des Gleichanteils, (u, v) = (0, 0)

„Trick“ für Visualisierung:


Eigenschaften

( ) ( )[ ]vuFcvuD ,1log, +⋅=

Signalparameter

§ Für 1-dimensionale Signale s(t)

• Mittels Fourier-Analyse wird deren Darstellung in Form eines trigonometrischen Polynoms gezeigt

• Die einzelnen harmonischen Komponenten werden durch 3 Parameter eindeutig repräsentiert:

i. Amplitude (~ Fourier-Koeffizienten)

ii. Frequenz

iii. Phase (~ Phasenverschiebung)

§ Für 2-dimensionale Signale f(x, y) à weiterer Parameter:

iv. Richtung (~ Richtung einer Wellenfront in der Bildebene)

§ Spektren:

a) Amplituden- oder Magnitudenspektrum

b) Phasenspektrum

Parameter der Fourier-Transformation

| F(u) | bzw. | F(u, v) |

ΦΦ(u) bzw. ΦΦ(u, v)

Bestimmung der Parameter aus F(u, v) ∈∈ C C – Spektral-Eigenschaften

1. Frequenz

(aus den Koordinaten !)

Repräsentiert eine Schwingung, die mit 4 Parametern eindeutig bestimmt ist !

v

uu i

v i

tiefe

mittlere Frequenzen

hohe

Charakteristische Filtereigenschaften

a) Tiefpass : Unterdrückung hoher Frequenzanteile, niederfrequente Anteile passieren weitgehend ungehindert

Funktion: Bildstörungen (~ Rauschen) sind hochfrequent, daher dienen Tiefpassfilter zur Rausch-Unterdrückung (~ Bildglättung)

b) Hochpass : Unterdrückung niedriger Frequenzanteile, hohe Frequenzen passieren weitgehend ungehindert

Funktion: Hervorhebung von Kontrasten (Kanten) der Signalfunktion; Nachteil: Störungen erscheinen wesentlich verstärkt

c) Bandpass : Kombination von Hoch- und Tiefpassfilter

Funktion: Hervorhebung bestimmter Frequenzanteile;Betonung von Kontrasten (Kanten) in verrauschten Daten

2. Amplitude

è Amplitudenspektrum (~ Magnituden- / Leistungsspektrum) :

Beträge (~ Längen) der Vektoren für (alle) Frequenzen des Fourier-Spektrums

Länge des Vektors (= Skalar) der komplexen Zahl an (ui, vi)

|F(u, v)|

u i

v i

Re

Im

|F(.)|

3. Phase

è Phasenspektrum :

Phasenwinkel (ε [-π, π]) für das gesamte Fourier-Spektrum (in geeigneter Codierung zur Darstellung)

Phasenlage (Phasenwinkel) des (komplexen) Funktionswertes

u i

v i

Re

Imcode{Φ}

Φ

4. Richtung

Richtungswinkel des Ortsvektors in Polarkoordinaten-Darstellung

v

uu i

v i

Ψ

a) 2D Signalfunktionb) Betrag des Fourier-Spektrums |F(u, v)|c) helligkeits-codierte Betragsfunktion


Beispiel : Transformation einer verschobenen Box-Funktion

Linearität

a) Superposition :

b) Homogenität :

Ähnlichkeit (Dehnung, Stauchung)

Eigenschaften

Translation im Orts- und Frequenzbereich

1. Verschiebung im Frequenzbereich

2. Verschiebung im Ortsbereich

è Verschiebung der Funktion im „Ziel“-Raum bewirkt lineare Phasendrehungim Komplementär-Raum !

Periodizität und konjugierte Symmetrie (diskrete Fourier-Transformation)

geg.: diskrete Bildfunktion mit homogener Abtastung, ∆x, ∆y, undrechteckiger Fensterfunktion

§ diskrete Fourier-Transformation und ihre Inverse sind periodisch mit den achsenspezifischen Periodenlängen N bzw. M

§ für reelle f(x, y) gilt (* : komplex Konjugierte) :

bzw.u

v

M

N

§ Periodenverschiebung bei diskreter Transformation

Formulierung der diskreten Fourier-Transformation für Werte

u ε [0, N-1] und v ε [0, M-1]

Ergebnis :

è

§ 1D Fall :

Zur Darstellung einer vollen Periode können die jeweils diagonal gegenüberliegenden Quadranten (mit je einer Halbperiode) vertauscht werden !

u

v

0

0

Transformierte erscheint mit jeweils 2 aneinandergrenzenden Halbperioden


Rotation

§ Rotation eines Bildsignals f(x, y) um θθ0 0 bewirkt eine entsprechende Rotation des Spektrum F(u, v)

§ Beispiele:


Differentiation

§ Allgemein

§ Beispiele:

a) Ableitung 1. Ordnung

b) Ableitung 2. Ordnung

c) Laplace-Operator

Kreis-Funktion r 2

Faltung

geg. : 2 analoge / diskrete 2D Signalfunktionen f(x, y) und g(x, y)

§ Faltungsintegral

2D Faltung (Konvolution) und Korrelation

Faltung

geg. : 2 analoge / diskrete 2D Signalfunktionen f(x, y) und g(x, y)

§ Faltungsintegral

§ Faltungssumme (sequentielle Faltung)

geg.: diskrete begrenzte Bildfunktionen und Masken

Problem: Was passiert an den Rändern ?

2D Faltung (Konvolution) und Korrelation

?

?

• Periodenanpassung („extended sequences“)

• Diskretes Faltungsprodukt

für x = 0, 1, ..., M-1 und y = 0, 1, ..., N-1

A x B C x D

A

B

C

D

Maske, g(x, y)

M

N

und

( à Dirichlet‘sche vs. Neumann‘sche Randbedingungen )

Faltungstheorem

Es gilt: a) für analoge Funktionen

FF{f(x, y) g(x, y)} = FF{f(x, y)} FF{g(x, y)}

b) für diskrete Funktionen („extended sequences“)

FF{fe[x, y] ge[x, y]} = FF{fe[x, y]} FF{ge[x, y]}

* .

* .

* .

g(x, y)

f(x, y)

f(x, y) g(x, y)

G(u, v)

F(u, v)

F(u, v) G(u, v)* .

F{.}

F {.}-1

Orts-Bereich

Frequenz-Bereich

Korrelation

§ Korrelationsintegral

§ Korrelationssumme („extended sequences“)

für x = 0, 1, ..., M-1 und y = 0, 1, ..., N-1

è für Autokorrelation

Kreuzkorrelation

§ Zusammenhang mit Faltung und Fourier-Transformation

i. Beziehung zur Faltung

ii. Beziehung zur Fourier-Transformation

Hinweis:

f*(x, y) (komplex Konjugierte)

Beziehungen gelten sowohl für analoge als auch für diskrete Funktionen („extended sequences“) !

Separierte Faltung

geg. : und

§ Faltungsintegral

§ Faltungssumme (mit )

1D-Faltung è Zwischenergebnis

1D-Faltung è N Zeilenvektoren

[ ] [ ] [ ] [ ]yhxkyxgyxf eeee ⋅=,,,

( )yxf , ( ) ( ) ( )yhxkyxg ⋅=,

Faltung und Fourier-Transformation

§ 2D Faltung

• M Spalten, N Zeilen• für jeden Punkt (x, y): M x N (komplexe) Multiplikationen

(M x N) ~ , für N = M :

§ 2D Fourier-Transformation

• Transformation (M x N) (M x N) komplexe Multiplikationen• Filterung 2 M N F.T. für f(.) und g(.)

M N Multiplikation der Spektren F und GM N Rücktransformation

4 M N ~ , für N = M :

§ Separierte Faltung

• M Spalten, N Zeilen• in N Zeilen, für jede Spalte x M Mult. = M N Multiplikationen

in M Spalten, für jede Zeile y N Mult. = M N Multiplikationen

M N + M N ~ für N > M , für N = M :

( )22 NMO2

.22.22

22

22.

2

2

2 2

Berechnungsaufwand (Zeitkomplexität)

( )4NO

( )22 NMO ( )4NO

( )2MNO ( )3NO

§ Schnelle Fourier-Transformation („Fast Fourier Transform“, FFT)

à M = N, N = 2 („Radix-2“)

Zeitkomplexität:

à Master-Theorem für Rekursionsgleichungen (siehe T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to algorithms. MIT Press, 1990, p.61ff)

aus der asymptotischen Abschätzung von T(n) folgt:

Hinweis : Durch Ausnutzung der Struktur 2-dimensionaler Signale kann mittels weiterer Zerlegung der Aufwand auf

reduziert werden!

n

( ) ( )NNONNO loglog 222 =

NN log4

3 2

Unschärferelation zwischen Orts- und Frequenzbereich

gewünscht : Möglichst begrenzte, d.h. auf einen lokalen Wirkungsbereich beschränkte, (Filter-) Funktion bei gleichzeitiger Wirkung auf ähnliche, d.h. benachbarte, Frequenzen !

Minimierung der Unschärfe zw. der Lokalisation von Ort und Frequenz

Paare von Fourier-Transformationen (ausgewählte Beispiele) :

Unschärferelation und Gauss-Filter

(R.N. Bracewell. The Fourier transform and its applications, 2. edition. McGraw-Hill, 1978)

Gauss-Funktion

Fourier-Transformation der Gauss-Funktion (1D und 2D)

Ähnlichkeit zwischen Orts-Funktion und Spektrum der Gauss-Funktion

à wg. der Form des Transformationskerns (exp[-j ω x]) und der Integralbeziehungergibt sich für Exponentialfunktionen ein ähnlicher Funktionsverlauf zwischen der Funktion im Ort und ihrer Transformierten !

Documents

Teil IV-A: Signal- und Bildverarbeitung – Methoden · • Mittels Fourier-Analyse wird deren Darstellung in Form eines trigonometrischen Polynoms gezeigt • Die einzelnen harmonischen