Image Processing Reference
In-Depth Information
∈
Aufgabe
4.12 (Schnelle Faltung mit der diskreten Fouriertransformation)
.
Die Faltung von
u
,
v
C
Z
ist definiert durch
)
k
=
n∈
Z
u
k
v
n−k
.
(
∗
u
v
C
Z
ist
Der
Träger
von
u
∈
Z
u
k
=
=
{
∈
}
supp
u
k
0
.
C
Z
mit supp
u
1.
Es seien
u
,
h
∈
=
{
0, . . . ,
N
−
1
}
und supp
h
=
{−
r
,...,
r
}
. Dann gilt
supp
u
(wieso?). Entwickeln und implementieren Sie einen Al-
gorithmus
, der die Faltung von
u
und
v
auf dem gesamten Träger mit Hilfe der
Fouriertransformation berechnet. Eingabe: Zwei Vektoren
u
,
C
N
,
h
∗
v
⊂{−
r
,...,
N
+
r
−
1
}
C
2
r
+1
. Ausgabe: Das
∈
C
N
+
2
r
Ergebnis
w
∈
der Faltung von
u
und
v
.
2.
Entwickeln und implementieren Sie analog zum vorigen Aufgabenteil eine zweidimensio-
nale schnelle Faltung
. Eingabe: Ein Grauwertbild
u
R
N×M
und ein Faltungs-
∈
R
2
r
+1
×
2
s
+1
. Ausgabe: Die Faltung
u
R
N
+2
r
,
M
+2
s
.
kern
h
∈
∗
h
∈
3.
Was ist der Aufwand für die schnelle Faltung im Gegensatz zur direkten Auswertung der
Summen? Für welche Größen von
u
und
h
lohnt sich die schnelle Faltung in dieser Hin-
sicht?
4.
Testen Sie den Algorithmus
an dem in
OnlinePLUS
zur Verfügung gestelltem
Bild mit Faltungskernen Ihrer Wahl. Vergleichen Sie Ergebnisse und Laufzeiten mit einer
Implementierung der direkten Summenbildung nach Unterabschnitt 3.3.3 (auch vor dem
Hintergrund der Aufwandsabschätzungen).
C
M
ein Faltungskern, wel-
cher wesentlich kürzer als das Signal ist, so kann die Faltung von
u
mit
h
um einiges effizienter
als in Aufgabe 4.12 berechnet werden. Ist
M
ein Teiler von
N
, so zerlege man
u
in
N
/
M
Teilblöcke
der Länge
M
:
C
N
ein Signal und
h
Aufgabe
4.13 (Overlap-Add-Faltung)
.
Ist
u
∈
∈
u
N
/
M
−
1
falls 0
≤
n
≤
M
−
1
u
n
−
rM
,
mit
u
n
=
(
r
−
1
)
M
+
n
r
=0
u
n
=
0
sonst.
u
0
u
1
..
.
u
M
−
1
u
M
u
M
+
1
.
..
u
2
M
−
1
...
u
1
u
2
(Hier haben wir (ohne es zu sagen) alle Vektoren durch Nullfortsetzung als Vektoren auf ganz
Z
aufgefasst.) Die Faltung von
u
mit
h
kann nun durch schnelle Faltung der Teile
u
r
mit
h
realisiert
werden: Man berechnet
v
r
u
r
=
∗
O
(
)
h
(was nach Aufgabe 4.12 mit Aufwand
M
log
M
geht) und
erhält auf Grund der Linearität der Faltung
N
/
M
−
1
v
r
.
r
=0
u
∗
h
=
und
v
r
+
1
Hierbei ist zu beachten, dass sich
v
r
überlappen. Diese Prozedur nennt sich auch
Overlap-Add-Verfahren.
1.
O
(
)
Zeigen Sie, dass der Aufwand der Overlap-Add-Faltung
N
log
M
ist.
2.
Entwickeln, implementieren und dokumentieren Sie einen Algorithmus
, der
die Faltung von
u
und
v
auf dem gesamten Träger mit dem Overlap-Add-Verfahren be-
rechnet. Eingabe: Zwei Vektoren
u
C
N
,
h
C
M
wobei
M
ein Teiler von
N
ist. Ausgabe:
∈
∈
C
N
+
M−
1
∈
Das Ergebnis
w
der Faltung von
u
und
v
.
