Digital Signal Processing Reference
In-Depth Information
h
(
u, v
)=
g
(
u, v
)
Ortsraum:
g
(
u, v
)
∗
14
Diskrete
Fouriertransformation in 2D
↓
↓
↑
DFT
−
1
(14.15)
DFT
DFT
↓
↓
↑
G
(
m, n
)
Spektralraum:
G
(
m, n
)
·
H
(
m, n
)
−→
Zunachst werden das Bild
g
und die Filterfunktion
h
unabhangig mithilfe
der DFT in den Spektralraum transformiert. Die resultierenden Spektra
G
und
H
werden punktweise multipliziert, das Ergebnis
G
wird an-
schließend mit der inversen DFT in den Ortsraum zurucktransformiert
und ergibt damit das gefilterte Bild
g
.
Ein wesentlicher Vorteil dieses
”
Umwegs“ liegt in der moglichen Ef-
fizienz. Die direkte Faltung erfordert fur ein Bild der Große
M
×
M
(
M
2
N
2
)Operationen.
2
Die Zeit-
komplexitat wachst daher quadratisch mit der Filtergroße, was zwar fur
kleine Filter kein Problem darstellt, großere Filter aber schnell zu auf-
wendig werden lasst. So benotigt etwa ein Filter der Große 50
und eine
N
×
N
große Filtermatrix
O
50 bereits
ca. 2.500 Multiplikationen und Additionen zur Berechnung jedes einzel-
nen Bildelements. Im Gegensatz dazu kann die Transformation in den
Spektralraum und zuruck mit der FFT in
×
(
M
log
2
M
) durchgefuhrt
werden, unabhangig von der Große des Filters (das Filter selbst braucht
nur einmal in den Spektralraum transformiert zu werden), und die Mul-
tiplikation im Spektralraum erfordert nur
M
2
Operationen, unabhangig
von der Große des Filters.
Daruber hinaus konnen bestimmte Filter im Spektralraum leichter
charakterisiert werden als im Ortsraum, wie etwa ein ideales Tiefpassfil-
ter, das im Spektralraum sehr kompakt dargestellt werden kann. Weitere
Details zu Filteroperationen im Spektralraum finden sich z. B. in [30, Ab-
schn. 4.4].
O
14.5.2 Lineare Faltung und Korrelation
Wie bereits in Abschn. 6.3 erwahnt, ist die lineare
Korrelation
identisch
zu einer linearen Faltung mit einer gespiegelten Filterfunktion. Die Kor-
relation kann daher, genauso wie die Faltung, mit der in Gl. 14.15 be-
schriebenen Methode im Spektralraum berechnet werden. Das ist vor
allem beim Vergleich von Bildern mithilfe von Korrelationsmethoden (s.
auch Abschn.17.1.1) vorteilhaft, da in diesem Fall Bildmatrix und Filter-
matrix ahnliche Dimensionen aufweisen, also meist fur eine Realisierung
im Ortsraum zu groß sind.
Auch in ImageJ sind daher einige dieser Operationen, wie
correlate
,
convolve
,
deconvolve
(s. unten), uber die zweidimensionale DFT in der
”
Fourier Domain“ (FD) implementiert (verfugbar uber das Menu
Pro-
cess
→
→
FD Math...
).
FFT
2
Zur Notation
O
() s. Anhang 1.3.
