Skript Numerische Bildverarbeitung

Frank Wübbeling 21. April 1997

Kapitel 1 Einleitung

1

Kapitel 2

Mathematische Grundlagen

In diesem Kapitel werden wir einige Sätze aus der Integralrechnung mehrerer Veränderlicher und der Funktionalanalysis zusammentragen. Die Beweise sind immer sehr kurz gehalten, ausführlich finden sie sich im Rudin und im Forster.

2.1 Fouriertransformation auf S

Nach der Einleitung müssen wir uns näher mit der Fouriertransformation und der Faltung beschäftigen. Hierzu einige Vorbemerkungen:

Lemma 2.1 Es gilt:

1. Soweit nicht extra darauf hingewiesen wird, sind alle hier auftauchenden Integrale Lebesgue–Integrale.

2. Mit L_{1}(IR^{n}) bezeichnen wir den Vektorraum aller Lebesgue–integrierbaren Funktionen von IR^{n} nach IR über den gesamten IR^{n} modulo aller Funktionen vom Maß 0. |f| = ∫_{IR}_{n} |f(x)|dx ist die kanonische Norm in diesem Vektorraum. Wenn die Dimension aus dem Zusammenhang klar ist, werden wir ihn kurz mit L_{1} bezeichnen.

3. Satz von Fubini: Sei f : IR^{k} × IR^{m} ↦ IR integrierbar. Dann gibt es eine Funktion g mit f = g f.ü., so daß g(·, y) integrierbar ist, und

∫_{IR_{k+m}} f(x, y)d(x, y) = ∫_{IR_{m}} ∫_{IR_{k}} f(x, y)dx dy.

Insbesondere gilt

∫ ∫ f(x, y)dx dy = ∫ ∫ f(x, y)dy dx.

4. Seien f, g ∈ L_{1} und g f.ü. beschränkt. Dann ist fg ∈ L_{1}.

5. Sei φ eine bijektive Abbildung von IR^{n} nach IR^{n}, f ∈ L_{1}. Dann gilt:

∫_{IR_{n}} f(x)dx = ∫_{IR_{n}} f(φ(x))|det((Dφ)(x))|dx.

6. Differenzierbarkeit: Sei f : IR^{k} × IR ↦ IR. Sei f(·, t) integrierbar und f(x, ·) differenzierbar. Weiter sei |\frac{df}{dt}(x, t)| ≤ F (x) für eine integrierbare Funktion f. Dann gilt:

\frac{d}{dt}(∫ f(x, t)dx) = ∫ \frac{df}{dt} (x, t)dx.

7. Satz von der majorisierten Konvergenz:

Sei f_{k} ∈ L_{1}, k ∈ IN. f_{k} konvergiere f.ü. punktweise gegen eine Funktion f, und es sei |f_{k}(x)| ≤ F (x) für eine integrierbare Funktion F. Dann gilt:

lim_{k→∞} ∫ f_{k}(x)dx = ∫ f(x)dx.

8. Es gilt:

∫_{IR_{n}} e^{−x^{t}x}dx = (2π)^{n/2}.

Für die erste Definition benötigen wir noch eine Kurzschreibweise. Sei x ∈ IR^{n} und α, β ∈ IN_{0}^{n}. Dann definieren wir:

x^{β} := Πx_{i}^{β_{i}}, D^{α} = Π (\frac{∂}{∂x_{i}} )^{α_{i}} .

Definition 2.2 Wir definieren den Schwarzschen Raum S durch

S = S(IR^{n}) := {f ∈ C^{∞}(IR^{n}) : sup|x^{β}D^{α}f| < ∞}.

Korollar 2.3 Es gilt:

1. S ist nichtleer.

2. S ⊂ L_{1}.

3. Sei f ∈ S. Dann ist lim_{x→∞} f(x) = 0.

Beweis:

1. e^{−|x|^{2}} ∈ S.

2. Sei n = 1. Sei f ∈ S, dann ist |(x^{2} + 1)f(x)| beschränkt, also |f(x)| ≤ \frac{1}{x^{2}+1}, also ist f integrierbar, denn f ist stetig und \frac{1}{x^{2}+1} ist integrierbar.

3. Es gilt sup(|x|^{2}f(x)) < ∞.

Mit Hilfe des Vektorraums S definieren wir nun die Fourier– Transformierte einer Funktion. Die Fouriertransformierte ist eines der wichtigsten Hilfsmittel der Bildverarbeitung. Wir definieren die Fouriertransformation hier zunächst nur für Funktionen aus S. Aus der Definition wird klar, daß man sie entsprechend für alle L_{1}-Funktionen definieren kann. Wir werden den Definitionsbereich im nächsten Kapitel auf nicht integrierbare Funktionen ausweiten.

Definition 2.4 Fouriertransformation: Sei f ∈ S(IR^{n}). Dann definieren wir die Fouriertransformierte f̂ und die inverse Fouriertransformierte f̃ durch

f̂(ξ) = (2π)^{−n/2} ∫_{IR_{n}} e^{−ixξ}f(x)dx
f̃(ξ) = (2π)^{−n/2} ∫_{IR_{n}} e^{ixξ}f(x)dx

Die vektorielle Multiplikation ist als Skalarprodukt zu verstehen, d.h. xξ = (x, ξ) = x^{t}ξ.

Zur Verdeutlichung rechnen wir zunächst

Beispiel 2.5 Sei f(x) = e^{−|x|^{2}}/2. Sei zunächst n = 1. Dann gilt:

f̂(ξ) = \frac{1}{\sqrt{2π}} ∫_{IR} e^{−x^{2}/2−ixξ}f(x)dx
= \frac{1}{\sqrt{2π}} ∫_{IR} e^{−(x+iξ)^{2}/2−ξ^{2}/2}f(x)dx
= e^{−ξ^{2}/2} \frac{1}{\sqrt{2π}} ∫_{IR} e^{−(x+iξ)^{2}/2}dx

Zur Berechnung dieses Integrals verwenden wir einen Standardtrick aus der Funktionentheorie und betrachten die folgenden Integrale als Riemann-Integrale. Die Funktion f(x) ist holomorph, also verschwindet jedes Integral über einen geschlossenen komplexen Integrationsweg dieser Funktion. Insbesondere gilt für jede positive reelle Zahl R (siehe Zeichnung)

∫_{−R}^{R} f(z + iξ)dz = ∫_{−R}^{R} f(z)dz + i ∫_{0}^{ξ} f(R + iz) − i ∫_{0}^{ξ} f(−R + iz)dz.

Rez Imz  R R + iξ −R + iξ −R

Wir betrachten nun den Grenzwert der rechten Seite für R → ∞.

∫_{0}^{ξ} |f(R + iz)|dz = ∫_{0}^{ξ} |e^{−R^{2}+z^{2}}|dz = e^{−R^{2}} ∫_{0}^{ξ} |e^{z^{2}}|dz → 0.

Ebenso verschwindet das dritte Integral auf der rechten Seite. Nach Vorbemerkung 2.1.8 konvergiert damit die linke Seite gegen \sqrt{2π} und es folgt f̂ = f oder:

f̂(ξ) = e^{−ξ^{2}/2}.

Korollar 2.6 Eigenschaften der Fouriertransformation. Sei f ∈ S(IR^{n}).

1.

ˆ (D^{α}f) (x) = i^{|α|}ξ^{α}f̂(ξ).

2.

ˆ (x^{α}f) (x) = i^{|α|}D^{α}f̂.

3. Sei f_{λ}(x) = f(λx) für ein 0 ≠ λ ∈ IR.

f̂_{λ}(ξ) = λ^{−n}f̂(\frac{ξ}{λ}).

4. Sei f_{y}(x) = f(x + y) für ein y ∈ IR^{n}.

f̂_{y}(ξ) = f̂(ξ)e^{iyξ}.

5. Sei (f ∗ g)(x) = ∫ f(x − y)g(y)dy. Dann gilt:

(f ∗ g)(ξ) = f̂(ξ)ĝ(ξ)(2π)^{n/2}.

Beweis:

1. Sei ohne Einschränkung n = 1, α = (1).

(f′)(ξ) = \frac{1}{\sqrt{2π}} ∫_{IR} e^{−ixξ}f′(x)dx
= \frac{1}{\sqrt{2π}} ∫_{IR} iξe^{−ixξ}f(x)dx.

Die Behauptung folgt durch Induktion.

2. Sei ohne Einschränkung n = 1, α = (1).

ˆ (x^{α}f) (ξ) = \frac{1}{\sqrt{2π}} ∫_{IR} xf(x)e^{−ixξ}dx
= \frac{1}{\sqrt{2π}} ∫_{IR} f(x)x · e^{−ixξ}dx
= \frac{1}{\sqrt{2π}} i ∫_{IR} f(x) (\frac{∂}{∂ξ} e^{−ixξ}) dx
= \frac{1}{\sqrt{2π}} i\frac{∂}{∂ξ} ∫_{IR} f(x)e^{−ixξ}dx
= \frac{1}{\sqrt{2π}} iD^{α} ∫_{IR} f(x)e^{−ixξ}dx.

Die Behauptung folgt durch Induktion. 3.

f̂_{λ}(ξ) = \frac{1}{\sqrt{2π}} ∫_{IR} f_{λ}(x)e^{−ixξ}dx
= \frac{1}{\sqrt{2π}} ∫_{IR} f(λx)e^{−ixξ}dx
= \frac{λ^{−n}}{\sqrt{2π}} ∫_{IR} f(x)e^{−ixξ/λ}dx
= λ^{−n}f̂(ξ/λ)

4.

f̂_{y}(ξ) = \frac{1}{\sqrt{2π}} ∫_{IR} f_{y}(x)e^{−ixξ}dx
= \frac{1}{\sqrt{2π}} ∫_{IR} f(x + y)e^{−ixξ}dx
= \frac{1}{\sqrt{2π}} ∫_{IR} f(x)e^{−ixξ+iyξ}dx
= e^{iyξ}f̂(ξ)

ˆ (f ∗ g) (ξ) = (2π)^{−n/2} ∫_{IR_{n}} ∫_{IR_{n}} f(x − y)g(y)dye^{−ixξ}dx
= (2π)^{−n/2} ∫_{IR} g(y)e^{−iyξ} ∫_{IR_{n}} f(x − y)e^{−i(x−y)ξ}dxdy
= (2π)^{n/2}ĝ(ξ)f̂(ξ)

Mit Hilfe dieser Sätze zeigen wir zunächst, daß die Bezeichung inverse Fouriertransformation gerechtfertigt ist, es gilt nämlich ˆ f̃ = ˜ f̂ = f.

Satz 2.7 Der Operator ist eine Bijektionvon S auf S. Sei f ∈ S. Dann gilt

f = ˜ f̂ = ˆ f̃.

Beweis:

1. f̂ ∈ S: Nach der Vorbemerkung ist D^{α}f̂ = (−i)^{|α|} ˆ (x^{α}f). Insbesondere existiert die Ableitung und damit f̂ ∈ C^{∞}(IR). Es gilt

ξ^{β}D^{α}f̂ = (−i)^{|α|}ξ^{β} ˆ (x^{α}f) = (−i)^{|α|}i^{−|β|} ˆ (D^{β}x^{α}f).

Wegen

|f̂(ξ)| = (2π)^{−n/2}| ∫_{IR_{n}} f(x)e^{−ixξ}dx| ≤ (2π)^{−n/2} ∫_{IR_{n}} |f(x)|dx

ist der Betrag einer Fouriertransformierten nach oben beschränkt und damit auch der Betrag von ξ^{β}D^{α}f̂ als Fouriertransformierter einer Funktion aus S.

2. Seien f, g aus S.

∫_{IR_{n}} f̂(x)g(x)dx = (2π)^{−n/2} ∫_{IR_{n}} ∫_{IR_{n}} f(ξ)e^{−ixξ}dξg(x)dx
= (2π)^{−n/2} ∫_{IR_{n}} f(ξ) ∫_{IR_{n}} e^{−ixξ}g(x)dxdξ
= ∫_{IR_{n}} ĝ(ξ)f(ξ)dξ

3. Sei ϕ ∈ S und wie üblich f_{x}(y) = f(x + y).

∫_{IR_{n}} f̂(ξ)e^{ixξ}ϕ(ξ)dξ = ∫_{IR_{n}} f̂_{x}(ξ)ϕ(ξ)dξ
= ∫_{IR_{n}} f_{x}(y)ϕ̂(y)dy
= ∫_{IR_{n}} f(x + y)ϕ̂(y)dy

4. Sei ϕ_{ϵ}(x) = ϕ(ϵx).

∫_{IR_{n}} f̂(ξ)e^{ixξ}ϕ_{ϵ}(ξ)dξ = ∫_{IR_{n}} f(x + y)ϕ̂_{ϵ}(y)dy
= ∫_{IR_{n}} ϵ^{−n} ∫_{IR_{n}} f(x + y)ϕ̂(y/ϵ)dy
= ∫_{IR_{n}} f(x + ϵy)ϕ̂(y)dy

Wir setzen nun ϕ(x) = e^{−|x|^{2}} und damit ϕ̂ = ϕ. Alle auftretenden Integranden auf der linken und rechten Seite der Gleichung werden durch integrierbare Funktionen majorisiert, wir dürfen also den Grenzwert für ϵ → 0 betrachten und den Satz von der majorisierten Konvergenz anwenden. Die linke Seite konvergiert dann gegen ϕ(0) ∫_{IR}_{n} f̂(ξ)e^{ixξ}dξ = (2π)^{n/2} ˜f̂(x). Die rechte Seite konvergiert gegen f(x) ∫_{IR}_{n} ϕ(y)dy = f(x)(2π)^{n/2}. Damit gilt ˜ f̂ = f. Entsprechend zeigt man ˆ f̃ = f.

Bisher haben wir unsere Funktionen in S als L_{1}-Funktionen untersucht. Sei nun L_{2} der Vektorraum der Funktionen, für die _{IR}^{n}|f^{2}(x)|dx existiert. Es gilt dann mit demselben Beweis wie in 2.3.2 S ⊂ L_{2}. Auf L_{2} können wir das Skalarprodukt (f, g) = ∫_{IR}_{n} f(x)\overline{g}(x)dx einführen. Dann gilt:

Korollar 2.8 (Parselvalsche Formel) Seien f, g ∈ S. Dann gilt

∫_{IR_{n}} f(x)\overline{g(x)}dx = ∫_{IR_{n}} f̂(ξ)\overline{ĝ(ξ)}dξ = ∫_{IR_{n}} f̃(ξ)\overline{g̃(ξ)}dξ.

Beweis: Nach dem zweiten Punkt aus dem Beweis zu Satz 2.7 gilt

∫_{IR_{n}} f(x)\overline{g(x)}dx = ∫_{IR_{n}} ˆ f̃(x)\overline{g(x)}dx = ∫_{IR_{n}} f̃(ξ)ˆ\overline{g}(ξ)dξ.

Da ˆ \overline{g}(ξ) = (2π)^{−n/2} ∫_{IR}_{n} \overline{g}(x)e^{−ixξ}dx = \overline{(2π)^{−n/2} ∫_{IR}_{n} g(x)e^{ixξ}dx} = \overline{g̃(ξ)}, gilt die Behauptung. Beweis für durch Einsetzen von f̂, ĝ für f, g.

Bemerkung 2.9 Wenn man auf S das Skalarprodukt (f, g) = ∫_{IR}_{n} f(x)\overline{g}(x)dx einführt, so gilt für f, g ∈ S die Parsevalsche Beziehung

(f, g) = (f̂, ĝ) = (f̃, g̃).

2.2 Temperierte Distributionen

Die Fouriertransformierte ist so, wie wir sie bisher definiert haben, für die Bildverarbeitung wenig hilfreich. Weder können wir unstetige Bilder verarbeiten, noch zeitkontinuierliche Signale. Die alte Definition verlangt zumindest die Integrierbarkeit von Funktionen, wir können also nicht einmal die Transformierte einer konstanten, nicht verschwindenden Funktion berechnen. Um dies zu tun, müssen wir den Definitionsbereich der Fouriertransformation wesentlich erweitern. Hierzu betten wir die Funktionen in den übergeordneten Vektorraum S′ der Distributionen ein. Hierdurch verallgemeinern wir den Funktionsbegriff. Auf diesem übergeordneten Vektorraum definieren wir nun eine neue Fouriertransformation, die für die Funktionen aus S mit der alten Definition übereinstimmt. In der physikalischen und Ingenieur–Literatur wird der Distributionsbegriff häufig gleichbedeutend mit dem Funktionsbegriff verwendet.

S  L_{1}  S′ Einbettung der Funktionen in die Distributionen

Definition 2.10 Ein lineares Funktional T : S → C heißt temperierte Distribution, falls es Konstanten C ∈ IR und k, l ∈ IN gibt, so daß für jede Funktion f ∈ S gilt

|T f| ≤ C ∑_{|α|≤k,|β|≤l} |f|_{α,β}

mit |f|_{α,β} := sup_{x∈IR^{n}} |x^{β}D^{α}f(x)|. Den Vektorraum der Distributionen nennen wir S′.

Eine temperierte Distribution ist also eine Funktion von S nach IR, die in ihrem Wachstum beschränkt ist. Die Distributionen sind für uns Erweiterungen des Funktionsbegriffs, wir müssen dort also zunächst unsere Funktionen wiederfinden. Wir betrachten deshalb Beispiel 2.11

1. Eine meßbare Funktion g heißt schwach wachsend, wenn es ein k ∈ ZZ

gibt mit

∫_{rz^{n}} |g(x)|(1 + |x|)^{k}dx < ∞.

Insbesondere ist |x|^{m} schwach wachsend, e^{|x|} ist nicht schwach wachsend.

Sei g schwach wachsend. Definiere T_{g}f := ∫_{IR}_{n} g(x)f(x)dx. Dann ist T f ∈ S′, denn:

|T f| = | ∫_{IR_{n}} g(x)(1 + |x|)^{k}(1 + |x|)^{−k}f(x)dx|
≤ ∫_{IR}^{n} |g(x)|(1 + |x|)^{k}dx sup_{x∈IR^{n}}(1 + |x|)^{−k}|f(x)|

Wir haben also für jede schwach wachsende Funktion eine zugehörige Distribution definiert. Wenn der Zusammenhang klar ist, werden wir häufig direkt g für T_{g} schreiben.

2. Diracsche δ–Distribution. Sei f ∈ S. Definiere

δ(f) := f(0)

δ ist Distribution, denn |T f| ≤ sup_{x∈IR^{n}} |f(x)|.

3. Natürlich können wir δ nicht direkt mit einer Funktion identifizieren, denn es gibt keine Funktion g mit δ(f) = f(0) = ∫_{IR}_{n} f(x)g(x)dx für alle Funktionen f ∈ S. Wir können uns aber δ als den Grenzwert einer Funktionenfolge vorstellen. Sei Φ(x) ≥ 0, ∫_{IR}_{n} Φ(x)dx = 1.

Definiere Φ_{ϵ}(x) := ϵ^{−n}Φ(\frac{1}{ϵ}x). Dann ist ∫_{IR}_{n} Φ_{ϵ}(x)dx = 1.

Sei f ∈ S. Wir betrachten den Grenzwert von T_{Φ_{ϵ}}(f) für ϵ → 0. Es gilt

T_{Φ_{ϵ}}(f) = ∫_{IR_{n}} Φ_{ϵ}(x)f(x)dx
= ϵ^{−n} ∫_{IR_{n}} Φ(\frac{1}{ϵ}x)f(x)dx
= ∫_{IR_{n}} Φ(x)f(ϵx)dx
→_{ϵ→0} f(0) ∫_{IR_{n}} Φ(x)dx = f(0) = δ(f).

Der letzte Schluß folgt mit dem Satz von der majorisierten Konvergenz.

Damit gilt (punktweise) T_{Φ_{ϵ}} → δ. Wir wählen zur Verdeutlichung n = 1 und

Φ(x) := \{ \begin{matrix}1 & |x| ≤ \frac{1}{2} \\ 0 & sonst. \end{matrix}

0 −0.5  0.5 12345678

Im Bild sind die Funktionen Φ_{1}, Φ_{1/2}, Φ_{1/4} und Φ_{1/8} dargestellt. Sie konvergieren punktweise gegen eine Funktion, deren Träger nur noch die 0 ist und die am Nullpunkt den Wert ∞ hat. Das Integral über diese Funktion sollte 1 sein. Aufgrund dieser Charakterisierung spricht man auch häufig von δ-Funktion anstatt δ-Distribution.

Wir werden nun einige Operatoren auf Funktionen auf Distributionen erweitern. Sei immer T ∈ S′ und f, g ∈ S.

Definition 2.12

1. Sei α ∈ ZZ^{n}.

(D^{α}T)f := (−1)^{|α|}T D^{α}f.

2. Sei y ∈ IR^{n} und f_{y}(x) := f(x + y).

T_{y}f := T f_{−y}.

3.

(gT)f := T (gf).

4. Sei ǧ(x) := g(−x).

(g ∗ T)(x) := T (ǧ)_{−x}

5.

T̂f := T f̂.

Wir müssen nun zeigen, daß diese Definitionen für Distributionen, die Funktionen sind, mit den üblichen Definitionen übereinstimmen. Sei daher T = T_{ϕ} und ϕ eine Funktion aus S.

1. Sei ohne Einschränkung n = 1 und α = (1). Da wir immer ϕ und T_{ϕ} identifizieren, erwarten wir, daß T′_{ϕ} = T_{ϕ′}.

T′_{ϕ}f = (D^{α}T)f = −T f′ = ∫_{IR} ϕ(x)f′(x)dx = ∫_{IR} ϕ′(x)f(x)dx = T_{ϕ′}f.

2. Übung.

3. Übung.

4.

(g ∗ T_{ϕ})(x) = T_{ϕ}(ǧ)_{−x} = ∫_{IR_{n}} ϕ(y)g(x − y)dy = (ϕ ∗ g)(x) = (g ∗ ϕ)(x).

Die Faltung einer Funktion aus S mit einer Distribution ist also eine Funktion, keine Distribution.

5. Hier müssen wir zeigen, daß T̂_{ϕ}f = T_{ϕ}f.

T̂_{ϕ}f = T_{ϕ}f̂
= ∫_{IR_{n}} ϕ(ξ)f̂(ξ)dξ
= \sqrt{2π}^{−n} ∫_{IR_{n}} ϕ(ξ) ∫_{IR_{n}} f(x)e^{−ixξ}dxdξ
= \sqrt{2π}^{−n} ∫_{IR_{n}} f(x) ∫_{IR_{n}} ϕ(ξ)e^{−ixξ}dξdx
= ∫_{IR_{n}} f(x)ϕ̂(x)dx
= T_{ϕ}f.

Beispiel 2.13 Sei f ∈ S.

1. Die α-Ableitung der δ–Distribution ist die Auswertung der α-Ableitung an der Stelle 0.

(D^{α}δ)f = (−1)^{|α|}δ(D^{α}f) = (−1)^{|α|}(D^{α}f)(0).

2. Sei n = 1. Wir definieren die Heaviside–Funktion H(x) durch

H(x) := \{ \begin{matrix}1 & x ≥ 0 \\ 0 & sonst. \end{matrix}

H ist nicht stetig, besitzt also insbesondere keine Ableitung im klassischen Sinn. Es gilt:

T_{H}f = ∫_{IR} H(x)f(x)dx = ∫_{0}^{∞} f(x)dx.

Für die Ableitung der Distribution T_{H} gilt:

(T′_{H})f = −T_{H}f′ = − ∫_{0}^{∞} f′(x) = f(0) = δf.

Im distributiven Sinn besitzt H also die Ableitung δ.

3. Die δ-Funktion wird oft mit verschobenem Argument benutzt:

δ_{−y}f = δf_{y} = δf(· + y) = f(y).

4. Fouriertransformierte der δ-Distribution:

δ̂f = δf̂ = f̂(0) = ∫_{IR_{n}} f(x)(2π)^{−n/2}dx.

Die Fouriertransformierte der δ-Distribution ist also die Funktion (2π)^{−n/2}. Mit den Rechenregeln der Fouriertransformation gilt δ̂_{−y}(ξ) = (2π)^{−n/2}e^{−iξy}.

Bemerkung:

1. Wir haben keine Multiplikation für Distributionen definiert. Die Distributionen sind für uns ein Vektorraum, keine Algebra.

2. Jede Distribution ist differenzierbar. Insbesondere besitzt jede Funktion von beschränktem Wachstum unendlich viele Ableitungen im distributiven Sinn. Unter Umständen ist diese Ableitung keine Funktion, sondern eine Distribution.

3. Jede Distribution, also auch jede Funktion von beschränktem Wachstum, besitzt eine Fouriertransformierte im distributiven Sinn.

Ohne Beweis zitieren wir den Satz von Plancherel: Die Fouriertransformierte einer L_{2}–Funktion ist eine L_{2}–Funktion.

Satz 2.14 Zu jedem g ∈ L_{2}(IR^{n}) gibt es ein ĝ ∈ L_{2}(IR^{n}) mit T̂g = T_{g} und ||g|| = ||ĝ||.

2.3 Abtasttheoreme

In diesem Abschnitt werden wir uns mit folgender Frage beschäftigen: Sei f die Dichtefunktion eines Bildes. Es sei bekannt, daß f̂ einen kompakten Träger hat. Wir können f nur an diskreten Punkten messen (abtasten). Wieviele Abtastungen von f brauchen wir, um f eindeutig zu bestimmen? Die Antwort hierzu geben die Abtasttheoreme.

Als Beispiel betrachten wir zunächst die sinc-Funktion in IR. Sei

χ(x) = \{ \begin{matrix}1, & −1 ≤ x ≤ 1 \\ 0, & sonst \end{matrix}

Es gilt für x ≠ 0

χ̃(x) = \frac{1}{\sqrt{2π}} ∫_{−1}^{1} e^{ixξ}dξ = \frac{1}{\sqrt{2π}} \frac{2}{x} \frac{e^{ix} − e^{−ix}}{2i} = \sqrt{\frac{2}{π}} \frac{sin x}{x} = \sqrt{\frac{2}{π}} sinc(x)

mit der Definition

Definition 2.15 Sei x ∈ IR^{n}. Dann ist

sinc(x) := ∏_{i=1}^{n} \frac{sin x_{k}}{x_{k}} .

Nach der Vorbemerkung ist im IR^{1} ŝinc(ξ) = \sqrt{\frac{π}{2}}χ(x). Für den IR^{n} gilt entsprechend

Satz 2.16 Sei ξ ∈ IR^{n}.

ŝinc(ξ) = \sqrt{\frac{π}{2}} χ(ξ)

mit der Definition

χ(x) = \{ \begin{matrix}1, & −1 ≤ x_{i} ≤ 1, i = 1 … n \\ 0, & sonst \end{matrix} .

Definition 2.17 Eine Funktion f ∈ L_{2}(IR^{n}) heißt bandbeschränkt mit Bandbreite b, falls f̂(ξ) = 0 für |ξ| ≥ b.

Korollar 2.18

1. sinc ist bandbeschränkt mit Bandbreite 1.

2. sinc_{b}(x) := sinc(bx) hat Bandbreite b.

Im Bild sind zunächst die sinc-Funktion und ihre Transformierte dargestellt. Wir stellen uns nun die linke Funktion als Helligkeitsfunktion vor. sinc ist außerhalb des Intervalls [−π, π] klein. Im dritten Bild, das die zweidimensionale sinc-Funktion als Dichteplot zeigt, kann man deshalb nur einen Kreis mit Radius π erkennen. Angenähert ist die Fouriertransformierte eines Kreises mit Durchmesser 2π also bandbeschränkt mit Bandbreite 1. 2. Umgekehrt ist die Fouriertransformierte der Kastenfunktion χ mit Kastenlänge 2 angenähert ein Kreis mit Radius π, also. Wir können daher die Faustregel aufstellen: Ein Detail der Größe 2π/b ist bandbeschränkt mit Bandbreite b. Je kleiner die auftretenden Details sind, umso größer ist der Träger der Fouriertransformation. Umgekehrt: Je größer der Träger der Fouriertransformation, umso kleiner sind die auftretenden Details, und umso feiner müssen wir abtasten. Dies wird bestätigt durch den folgenden Satz:

Satz 2.19 (Abtasttheorem von Shannon) Sei f ∈ L_{2}(IR^{n}) bandbeschränkt mit Bandbreite b und 0 < h ≤ \frac{π}{b}. Dann ist f eindeutig bestimmt durch die Werte f(kh), k ∈ ZZ^{n}, und es gilt f.ü.

f(x) = ∑_{k∈Z Z^{n}} f(kh)sinc\frac{π}{h}(x − kh).

Bemerkung 2.20

1. Der Satz ist so nur richtig für L_{2}-Funktionen.

2. Die Bedingung h ≤ \frac{π}{b} heißt Nyquist–Bedingung. Für h < \frac{π}{b} sprechen wir von oversampling (Überabtasten), für h > \frac{π}{b} sprechen wir von undersampling (Unterabtasten).

Bevor wir den Satz beweisen, stellen wir einige Sätze über Fourier–Reihen auf endlichen Intervallen zusammen.

Satz 2.21 Fourierreihen: Sei f ∈ L_{2}([−a, a]^{n}). Dann gilt f.ü.

f(x) = ∑_{k∈Z Z^{n}} f̂_{k}e^{ikx/a}

mit

f̂_{k} = (2a)^{−n} ∫_{[−a,a]^{n}} e^{−ikx/a}f(x)dx.

Beweis: Forster III.

Satz 2.22 Parsevalsche Gleichung: Seien f, g ∈ L_{2}([−a, a]^{n}) und f̂, ĝ wie oben definiert. Dann gilt

∫_{[−a,a]^{n}} f(x)\overline{g(x)}dx = (2π)^{n} ∑_{k∈Z Z^{n}} f̂_{k}\overline{ĝ_{k}}.

Beweis: Sei ohne Einschränkung a = π.

∫_{[−π,π]^{n}} f(x)\overline{g(x)}dx = ∫_{[−π,π]^{n}} ( ∑_{k∈Z Z^{n}} f̂_{k}e^{ikx}) ( ∑_{l∈Z Z^{n}} ˆ \overline{g_{l}}e^{−ilx}) dx
= ∑_{k∈Z Z^{n}} ∑_{l∈Z Z^{n}} f̂_{k}\overline{ĝ_{l}} ∫_{[−π,π]^{n}} e^{i(k−l)x}dx

Das Integral verschwindet für k ≠ l und ist (2π)^{n} für k = l, also folgt die Behauptung. Die Vertauschungen dürfen durchgeführt werden nach dem Satz von der majorisierten Konvergenz.

Satz 2.23 Poissonsche Formel: Sei f ∈ S.

∑_{l∈Z Z^{n}} f̂(ξ − 2πl) = (2π)^{−n/2} ∑_{l∈Z Z^{n}} f(l)e^{−ilξ}.

Beweis: Sei g(ξ) := ∑_{l} f̂(ξ − 2πl). Dann ist g eine 2π–periodische Funktion. Für den k. Fourierkoeffizienten von g gilt:

ĝ_{k} = (2π)^{−n} ∫_{[−π,π]^{n}} e^{−ikξ}g(ξ)dξ
= (2π)^{−n} ∑_{l∈Z Z^{n}} ∫_{[−π,π]^{n}} f̂(ξ − 2πl)e^{−ikξ}dξ
= (2π)^{−n} ∑_{l∈Z Z^{n}} ∫_{[−π,π]^{n}} f̂(ξ − 2πl)e^{−ik(ξ−2πl)}dξ
= (2π)^{−n} ∑_{l∈Z Z^{n}} ∫_{[−π,π]^{n}+2πl} f̂(ξ)e^{−ikξ}dξ
= (2π)^{−n} ∫_{IR_{n}} f(ξ)e^{i(−k)ξ}dξ = (2π)^{−n/2}f(−k).

und damit

g(ξ) = ∑_{l∈Z Z^{n}} ĝ_{l}e^{ilξ} = (2π)^{−n/2} = ∑_{l∈Z Z^{n}} f(l)e^{−ilξ}.

Zu ∑_{l∈Z Z^{n}} ∫_{[−π,π]^{n}+2πl} = ∫_{IR}_{n}: Die Integralbereiche, über die integriert wird, bilden eine nicht–überlappende Überdeckung des IR^{n}. Hier ein Beispiel für n = 2:

[−π, π]^{2}^{[−π, π]^{2} + (−2π, 2π)} ^{[−π, π]^{2} + (0, 2π)} ^{[−π, π]^{2} + (2π, 2π)}^{[−π, π]^{2} + (2π, 0)}^{[−π, π]^{2} + (2π, −2π)}^{[−π, π]^{2} + (0, −2π)}^{[−π, π]^{2} + (−2π, −2π)}^{[−π, π]^{2} + (−2π, 0)}

Korollar 2.24 Sei f ∈ S. Dann ist

∑_{l∈Z Z^{n}} f̂(2πl) = (2π)^{−n/2} ∑_{l∈Z Z^{n}} f(l)e^{−ilξ}.

Beweis: Setze ξ = 0 in Satz 2.23. Wir können diese Formel umschreiben zu

∫_{IR_{n}} f(x)dx = (2π)^{−n/2}f̂(0) = ∑_{l} f(l) − (2π)^{n/2} ∑_{l≠0} f̂(2πl).

Sei h ∈ IR. Für die Funktion f_{h}(x) := f(hx) gilt dann

∫_{IR_{n}} f(x)dx = h^{n} ∫_{IR_{n}} f_{h}(x)dx
= h^{n} ∑_{l} f(l) − h^{n}(2π)^{n/2} ∑_{l≠0} f̂_{h}(2πl)
= \underbrace{h^{n} ∑_{l} f(l)} −(2π)^{n/2} ∑_{l≠0} f̂(2πl/h).

Falls f bandbeschränkt ist mit Bandbreite 2π/h, so ist die Trapezregel zur Berechnung des Integrals von f exakt. Beweis des Abtasttheorems von Shannon (2.19): Wir betrachten f, f̂ als Funktion auf [−a, a]. Dann sind f, f̂ ∈ L_{2}([−a, a]) und für die Fourierreihen von f und f̂ gilt

f(x) = ∑_{k∈Z Z^{n}} f̂_{k}e^{ikx/a}, f̂_{k} = (2a)^{−n} ∫_{[−a,a]^{n}} f(x)e^{−iπkx/a}dx

und

f̂(ξ) = ∑_{k∈Z Z^{n}} f_{k}e^{iπkξ/a}, f_{k} = (2a)^{−n} ∫_{[−a,a]^{n}} f̂(ξ)e^{−iπkξ/a}dξ.

Wir wählen a = \frac{h}{π}. Dann ist f̂(ξ) = 0 für ξ ∉ [−a, a]^{n} und es gilt

f_{k} = (2a)^{−n} ∫_{[−a,a]^{n}} f̂(ξ)e^{−ihkξ}dξ
= (2a)^{−n} ∫_{IR_{n}} f̂(ξ)e^{i(−hk)ξ}dξ
= h^{n}(2π)^{−n/2}f(−kh).

Mit

χ_{a}(x) := \{ \begin{matrix}1, & x ∈ [−a, a] \\ 0, & sonst \end{matrix}

gilt

f̂(ξ) = (2π)^{−n/2}h^{n} ∑_{k∈Z Z^{n}} f(kh)χ_{a}(ξ)e^{−ikhξ}.

Durch Fouriertransformation:

f(x) = (2π)^{−n/2}h^{n} ∑_{k∈Z Z^{n}} f(kh) ˜ [χ(x)e^{−ihkx}](x)

Definiere g(x) := sinc((x + kh)/a). Nach den Rechenregeln der Fouriertransformierten gilt

ĝ(ξ) = a^{n}e^{−ihkξ} (\frac{π}{2} )^{n/2} χ_{a}(ξ) = (2π)^{−n/2}h^{n}e^{−ihkξ}χ_{a}(ξ).

Wir studieren nun den Effekt des Über- bzw. Unterabtastens. Oben ist die sinc–Funktion mit den Schrittweiten 1, 2, 3 und 4 abgetastet worden. Überabtastung liefert die richtige Funktion, Unterabtastung liefert eine aufgeweitete Funktion.