Upload
vominh
View
218
Download
0
Embed Size (px)
Citation preview
12.05.11
1
Diskrete Signalverarbeitung und diskrete Systeme
Computer-‐basierte Verarbeitung von Signalen und Realisierung von Systemverhalten erfordern diskrete Signale und diskrete Systembeschreibungen. Wegen der ausgerei?en Theorie für analoge Signale und Systeme finden Systementwicklungen dennoch vorwiegend im Analogen staE. Auch gibt es für die meisten grundlegenden analogen Zusammenhänge genau entsprechende diskrete Zusammenhänge. Allerdings gibt es auch zahlreiche diskrete Verfahren zur Signalverarbeitung, die heurisJsch, ohne fundierte Theorie, angewendet werden. Beispiel: GläEungsoperator mit Gewichten 3!
2!
2!2!2!
1! 1!
1! 1!
!"#$ =%&'!
( &'"'"'"()!
Diskrete Faltung
KonJnuierliche Signalübertragung: Alle Signale mit Abtastwerten beschrieben:
g(t) = h(t) ! s(t)
!"#$%!"& "#$%#="#
#
$%
&'
(
)* +'(#)"
,&$% = *"#$%!"& "#$%
#="#
#
$%
&'
(
)* +'(#)"
,&$%+ '"#$%!"& "#$%
#="#
#
$%
&'
(
)* +'(#)"
,&$%
Daraus folgt für die Abtastwerte (nach einigen SchriEen) für T=1 und unter der Voraussetzung bandbegrenzter Signale :
!"#$ = %"#!&$'"&$&=!"
"
# "Diskrete Faltung"
Schreibweise dafür auch: g(n) = h(n) ∗ s(n) Für kausale Systeme ist die Impulsantwort = 0 für t < 0. Dann gilt:
!"#$ = %"#!&$'"&$&=!"
#
#
Die diskrete Faltung ist die Grundlage für die computerbasierte Berechnung von Systemverhalten!
2
12.05.11
2
3
Lokale 0peratoren
Bildverarbeitung realisiert Faltung häufig mit "lokalen Operatoren".
Erzeuge ein neues Bild , indem ein linearer, lokaler Operator f auf alle Pixel eines Bildes angewandt wird:
ij
Dij
mn
Die Pixelindizes i, j können in von 1 abweichenden SchriEen inkremenJert werden.
Beispiel für Stützfläche
eines lokalen Operators
!"#$ = %&'"( )"* )+++)",-&&&&&&&&"( )"* )+++)", !./0
ˆ g mn
Unter welchen Voraussetzungen ist diese OperaJon eine Faltung?
4
Beispiel: Kontrastverschärfung Bildintensitäten werden durch lokalen Operator mit 3x3 Stützfläche an Kanten verstärkt
"Unscharfes Maskieren" = SubtrakJon eines unscharfen Bildes
!"#$ = "#$ !%
&'&"()
"()"*'#
!" !" !"!" # !"!" !" !"
Diese Technik wurde (früher?) häufig analog realisiert.
12.05.11
3
5
Behandlung von Störungen ("Rauschen")
Abweichungen von einem idealen Bildsignal werden häufig mit addiJvem Rauschen modelliert:
= +
Typische Eigenscha?en:
• MiEelwert 0, Varianz σ2 > 0 • örtlich unkorreliert: E[ rij rmn] = 0 für ij ≠ mn • zeitlich unkorreliert: E[ rij,t1 rij,t2] = 0 für t1 ≠ t2
• Gauss-‐Wahrscheinlichkeitsdichte: !"#$ = %
! &"'# #&
&!&
Rauschen entsteht durch einzelne Ladungsträger ("Schrotrauschen"), elektromagneJsche Einkopplung, thermische Molekularbewegungen und andere Phänomene.
Neben addiJvem Rauschen gibt es mehrere andere Rauschmodelle.
E[x] ist "Erwartungswert"
von x
6
GläEung durch MiEelung
Zwei grundsätzliche Wege zum "AusmiEeln" von Rauschen: -‐ Zeitliches MiEeln, falls mehrere Proben gij,t desselben Pixels zu verschiedenen
Zeitpunkten t = 1 ... T zur Verfügung stehen
-‐ Örtliches MiEeln, falls gmn ≈ gij für alle Pixel gmn in einem Bereich um gij
Wie effekJv ist das MiEeln von Grauwerten?
!"# =$#
"%%=$
#
! " & ProbenmiEelwert nähert sich MiEelwert der Verteilung an
!"# =$#
"%%=$
#
! ist Zufallsvariable, Varianz hängt von K ab
MiEelwert
! "#$% !! #$%"# $%&'"# $% = ! #$%
'"# $% = !(%'
" $) &'
)=(
%
&"
#'
$
%( =
(%'
! $)'"# $% =
)'
%)=(
%
& Varianz
Beispiel: Um die Standardabweichung zu halbieren, müssen 4 Werte gemiEelt werden
! "#$!" #$ =%$
! #&!" #$&=%
$
% = '
Prinzip:
12.05.11
4
7
Einfache GläEungsoperaJonen
1. MiEelung
D ist Region um gij !"#$ =%
&'&"()
"()!*'"
ij
Beispiel einer 3 x 3 Region D
2. BeseiJgung von Ausreißern
!"#$ =!
"#"$%&
$%&!'#" '''()&&''' $*+ #
!"#"
$%&$%&!'#" $ ,
gij
S ist Schwellenwert
3. Gewichtetes MiEeln
!"#$ =%&'!
( &'"'"'"()! wk = Gewichte in D
All dies sind heurisJsche OperaJonen ohne die theoreJschen Fundamente von INF-‐N2!
Beispiel von Gewichten in 3 x 3 Region
! " !" # "! " !
8
Zweidimensionale Diskrete Fourier-‐TransformaJon (DFT)
!"# =$%&
' ()**=+
&!$
")=+
%!$
" ,!-#./)"
%+*#&0
!"# = $ %&''=(
)!*
"&=(
+!*
" ,-#./"&
++#')0
Die TransformaJon basiert auf der Periodizitätsannahme:
Diskrete Fourier-‐TransformaJon: Inverse Diskrete Fourier-‐TransformaJon:
=> Periodische Fortsetzung kann Randeffekte bewirken
für u = 0 ... M-‐1, v = 0 ... N-‐1 für m = 0 ... M-‐1, n = 0 ... N-‐1
NotaJon:
Guv = F{ gmn }
gmn = F-‐1{ Guv }
Anwendung auf Bilder
12.05.11
5
Beispiel eines Amplitudenspektrums
9
10
Schnelle Fourier-‐TransformaJon Normale DFT braucht ~(MN)2 OperaJonen für ein M x N Bild. Beispiel: M = N = 1024, 10-‐12 sek/OperaJon => 1,1 sek
FFT (Fast Fourier Transform) basiert auf einer rekursiven DekomposiJon von gmn in Subsequenzen => parJelle Resultate können mehrfach gebraucht werden => ~MN log2(MN) OperaJonen. Dasselbe Beispiel braucht nur 0.000021 sek.
DekomposiJonsprinzip für die 1D-‐Fourier-‐TransformaJon:
!" =#$
%&&='
$!#" (!)#*"&
${ gn
(1) } = { g2n }
{ gn(2) } = { g2n+1 }
{ gn } = n = 0 .. N/2-‐1
!" =#$
%&'#()
!*"+"*&$ + %&
'*()!*"+"'*&+#(
$#$%
&%
'(%
)%&=,
$*!#
* r = 0 ... N-‐1
Gr = Gr(1) + e
!2"j rN Gr
(2)
r = 0 ... N/2-‐1
Gr+N 2 = Gr(1) ! e
!2"j rN Gr
(2)
Alle Gr können in 2(N/2)2
anstelle von (N)2 OperaJonen berechnet werden!
12.05.11
6
11
Diskrete Faltung mithilfe der FFT
Faltung kann durch TransformaJon in den Frequenzraum mit der FFT insgesamt effizienter ausgeführt werden!
!!"# = $ !%&&='
()*
"%='
+#*
" ,"#%-##& (MN)2 OperaJonen erforderlich
Anwendung der FFT and Filtern im Frequenzraum:
gmn Guv Guv´ gmn´ FFT Huv FFT-‐1
MN log(MN) MN MN log(MN) # der OperaJonen
Beispiel mit M = N = 512: • normale Faltung braucht ~ 1010 OperaJonen • Faltung mithilfe der FFT braucht ~107 OperaJonen