Diskrete Faltung


Diskrete Faltung

In der Mathematik und besonders in der Funktionalanalysis beschreibt die Faltung einen mathematischen Operator, der für zwei Funktionen f und g eine dritte Funktion liefert. Diese gibt eine Art „Überlappung“ zwischen f und einer gespiegelten und verschobenen Version von g an und ähnelt einem gleitenden Durchschnitt.

Inhaltsverzeichnis

Definition

Für zwei auf dem reellen Intervall D definierte Funktionen f, g: D \to\Bbb C wird die Faltung von f mit g als f * g notiert. Sie ist als das Integral über dem Produkt von f mit einer am Ursprung gespiegelten und verschobenen Version von g definiert:

(f*g)(t) = \int_D f(\tau)g(t-\tau)\mathrm{d}\tau\,

Der Integrationsbereich ist der gesamte Definitionsbereich D beider Funktionen. Im Fall eines beschränkten Definitionsbereichs werden f und g oft als periodisch fortgesetzt angenommen, damit der Faktor g(t − τ) stets definiert ist. In diesem Fall wird die Faltungsoperation auch als zirkulare, zyklische oder periodische Faltung bezeichnet. Oder es werden f und g stattdessen durch Null fortgesetzt, wie dies bei der aperiodischen Faltung der Fall ist. In einer anderen Konvention, wie sie vor allem bei Physikern und Ingenieuren üblich ist, könnte man auch die Bedeutung von t und τ so verändern dass man die dort übliche Beziehung \,(f*g)(\tau) = \int_D f(t)g(\tau-t)\mathrm{d}t erhält, wobei τ der sog. Zeitversatz ist.

Bedeutung

Faltung der Rechteckfunktion mit sich selbst ergibt die Dreieckfunktion.

Eine anschauliche Deutung der Faltung ist die Gewichtung einer Funktion mit einer anderen. Der Funktionswert der Gewichtsfunktion f an einer Stelle τ gibt an, wie stark der um τ zurückliegende Wert der gewichteten Funktion, also g(t − τ), in den Wert der Ergebnisfunktion an der Stelle t eingeht.

Die Faltung ist ein geeignetes Modell zur Beschreibung zahlreicher physikalischer Vorgänge.

  • Bei einem linearen, zeitinvarianten Übertragungsglied ergibt sich die Antwort auf eine Anregung durch Faltung der Anregungsfunktion mit der Impulsantwort des Übertragungsglieds. Beispielsweise stellt die lineare Filterung eines elektronischen Signals die Faltung der Original-Funktion mit der Impulsantwort dar.
  • Bei optischen Abbildungen stellt das Bild die Faltung der originalen Bildfunktion mit der Punkt-Verbreiterungs-Funktion (Point Spread Function oder PSF) dar (Unschärfe).
  • Diffusions-Prozesse lassen sich ebenfalls durch die Faltung beschreiben.
  • Wenn X und Y zwei stochastisch unabhängige Zufallsvariablen mit den Wahrscheinlichkeitsdichten f und g sind, dann ist die Dichte der Summe X+Y gleich der Faltung f * g.

Diskrete Faltung

In der digitalen Signalverarbeitung und der digitalen Bildverarbeitung hat man es meist mit diskreten Funktionen zu tun. Hier seien die Funktionen f, g: D \to\Bbb C gegeben. Dabei ist der Definitionsbereich D  \subseteq \Bbb Z.

Die diskrete Faltung ist definiert als:

 
(f * g)(n) = \sum_{k \in D} f(k) g(n - k)

Der Summationsbereich ist der gesamte Definitionsbereich D beider Funktionen. Im Fall eines beschränkten Definitionsbereichs werden f und g meist durch Null fortgesetzt.

Das Produkt zweier Polynome f und g ist z.B. die diskrete Faltung ihrer mit Nullen fortgesetzten Koeffizientenfolgen. Die dabei auftretenden unendlichen Reihen haben stets nur endlich viele Summanden, die ungleich Null sind. Analog definiert man das Produkt zweier formaler Laurentreihen mit endlichem Hauptteil.

Ein in Bezug auf die Rechenleistung effizienter Algorithmus für die Berechnung der diskreten Faltung ist die Schnelle Faltung, die sich ihrerseits auf die Schnelle Fourier-Transformation (FFT) zur effizienten Berechnung der diskreten Fourier-Transformation stützt.

Eine interaktive Visualisierung als Java-Applet ist hierzu zu finden unter [1].

Glättungskern

Eine schöne Methode, eine Funktion f zu „glätten“, besteht darin, sie mit einem so genannten Glättungskern zu falten. Die entstehende Funktion F ist glatt (unendlich oft stetig differenzierbar), ihr Träger ist nur etwas größer als der von f, und die Abweichung in der L1-Norm lässt sich durch eine vorgegebene positive Konstante beschränken.

Ein d-dimensionaler Glättungskern (engl. mollifier) ist eine unendlich oft stetig differenzierbare Funktion j:\R^d\to\R_+, die nichtnegativ ist, ihren Träger in der abgeschlossenen Einheitskugel B(0, 1) hat und das Integral 1, durch entsprechende Wahl einer Konstanten c, besitzt.

Ein Beispiel ist der Glättungskern

j(x) = \begin{cases}
c \cdot \exp\!\left(-\frac{1}{1-x^2}\right) & -1 < x < 1 \\0 & \mathrm{ sonst}\end{cases}

Aus dieser Funktion kann man weitere Glättungskerne bilden, indem man für e eine Zahl zwischen 0 und 1 setzt:


j_e(x) = \frac{1}{e^d}\cdot j\left(\frac{x}{e}\right),
wobei je(x) = 0 für | x | > e.

Glaettungskerne j und j_1/2
Glättungskerne j und j1/2

Beispiele

Sei


f:\R\to\R,\;x\mapsto \begin{cases}1 & -1 \le x \le 2 \\0 & \mathrm{ sonst}
\end{cases}
.

Durch Faltung von f (rot dargestellt) mit dem Glättungskern j1 / 2 entsteht eine glatte Funktion F = f * j1 / 2 (blau dargestellt) mit kompaktem Träger, die von f in der L1-Norm um etwa 0,4 abweicht, d.h.


\int_{-\infty}^{\infty} |F(t)-f(t)| \mathrm{d}t < 0{,}4
.

Glaettung durch Faltung

Bei der Faltung mit je für e kleiner 1/2 erhält man glatte Funktionen, die in der Integralnorm noch dichter bei f liegen.

Eigenschaften der Faltung; Faltungstheorem

Von den folgenden Aussagen ist das sog. Faltungstheorem wegen seiner vielfältigen Anwendungen besonders wichtig:

f*g = g*f\,
f*(g*h) = (f*g)*h = f*g*h\,
f*(g+h) = (f*g) + (f*h)\,
  • Assoziativität mit der skalaren Multiplikation
a(f*g) = (af)*g = f*(ag)\,
Wobei a eine beliebige komplexe Zahl ist.
  • Faltungstheorem
\mathcal{F}(f*g) = (2 \pi)^{\tfrac{n}{2}} \, (\mathcal{F}f)\cdot(\mathcal{F}g),\quad f,g\in\mathbb{R}^n
Wobei \mathcal{F}f die Fouriertransformierte von f beschreibt. Ein ähnliches Theorem gilt auch für die Laplacetransformation.
  • Ableitungsregel
\mathrm{D}(f * g) = \mathrm{D}f * g = f * \mathrm{D}g\,
Dabei ist Df die Ableitung f' von f bzw. im diskreten Fall die Differenz Df(n) = f(n + 1) − f(n).
  • Faltungsalgebra
    • (f*g)(t) = \int\limits_{-\infty}^{\infty}f(\tau)g(t-\tau)\mathrm{d}\tau
    • (Sf * g)(t) = \int\limits_{-\infty}^{\infty}f(-\tau)g(t-\tau)\mathrm{d}\tau = \int\limits_{-\infty}^{\infty}f(\tau)g(\tau+t)\mathrm{d}\tau, wobei S der Spiegelungsoperator mit Sf(t) = f( − t) für alle t ist.
    • (Sf*Sg)(t) = \int\limits_{-\infty}^{\infty}f(\tau)g(-t-\tau)\mathrm{d}\tau

Verallgemeinerungen

Die beiden Faltungsbegriffe können gemeinsam beschrieben und verallgemeinert werden durch einen allgemeinen Faltungsbegriff für komplexwertige m-integrierbare Funktionen auf einer geeigneten topologischen Gruppe G mit einem Maß m (z. B. einer lokalkompakten hausdorffschen topologischen Gruppe mit einem Haar-Maß):

(f * g)(x) = \int_G f(t) g(x t^{-1}) \mathrm{d}m(t)\,

Dieser Faltungsbegriff spielt eine zentrale Rolle in der Darstellungstheorie dieser Gruppen, deren wichtigste Vertreter die Liegruppen bilden. Die Algebra der integrierbaren Funktionen mit dem Faltungsprodukt ist für kompakte Gruppen das Analogon zum Gruppenring einer endlichen Gruppe. Weiterführende Themen sind:

Eine andere Verallgemeinerung ist die Faltung von Distributionen,

(T * \varphi)(x) := T[\tau_x \varphi],

wobei τx die Verschiebung um x nach links bezeichnet.

Anwendung

  • In der Optik können verschiedenste Bildstörungen als Faltung des Originalbildes mit einem entsprechenden Kern modelliert werden. In der digitalen Bildbearbeitung wird die Faltung daher benutzt, um solche Effekte zu simulieren. Auch andere digitale Effekte beruhen auf der Faltung.
  • In der Akustik (Musik) wird die Faltung (unter Zuhilfenahme der FFT = schnelle Fouriertransformation) auch zur digitalen Erzeugung von Hall und Echos und zur Anpassung von Klangeigenschaften verwendet. Dazu wird die Impulsantwort des Raumes, dessen Klangcharakteristik man übernehmen möchte, mit dem Signal, das man beeinflussen möchte, gefaltet.
  • In der Ingenieurmathematik und der Signalverarbeitung werden Eingangssignale (äußere Einflüsse) mit der Übertragungsfunktion (= Impulsantwort = Reaktion des betrachteten Systems auf einen Diracimpuls als Signaleingang) gefaltet, um die Antwort eines LTI-Systems auf beliebige Eingangssignale zu berechnen. Die Übertragungsfunktion ist nicht zu verwechseln mit der Übergangsfunktion. Erstere beschreibt die Gesamtheit aus System und einem Dirac-Impuls als Eingangs-Testfunktion, letztere die Gesamtheit aus System und einer Sprungfunktion als Eingangs-Testfunktion. Die Berechnungen finden meist nicht im Zeitbereich, sondern im Frequenzbereich statt. Dazu müssen sowohl das Signal als auch die das Systemverhalten beschreibende Übertragungsfunktion im Frequenzbereich vorliegen, oder ggf. aus dem Zeitbereich per Fouriertransformation oder einseitiger Laplacetransformation dorthin transformiert werden.
  • In der numerischen Mathematik erhält man durch Faltung der Boxfunktion N0(t) mit Nk − 1(t) die B-Spline Basisfunktion Nk(t) für den Vektorraum der stückweisen Polynome vom Grad k.
  • Ebenfalls in der numerischen Mathematik kann die Faltung für eine effiziente Berechnung der Multiplikation vielstelliger Zahlen eingesetzt werden, da die Multiplikation im wesentlichen eine Faltung mit nachfolgendem Übertrag darstellt. Die Komplexität dieses Vorgehens ist mit \mathcal{O}(n \cdot \log{(n)}) nahe linear, während das „Schulverfahren“ quadratischen Aufwand \mathcal{O}(n^2) hat, wobei n die Zahl der Stellen ist. Dies lohnt sich trotz des zusätzlichen Aufwands, der hierbei für die Fouriertransformation (und deren Umkehrung) erforderlich ist.

Literatur

  • Bourbaki: Integration
  • Kôsaku Yosida: Functional Analysis. Springer-Verlag, ISBN 3-540-58654-7.

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Faltung (Mathematik) — In der Mathematik und besonders in der Funktionalanalysis beschreibt die Faltung, auch Konvolution (von lat. convolvere, „zusammenrollen“), einen mathematischen Operator, der für zwei Funktionen f und g eine dritte Funktion liefert. Anschaulich… …   Deutsch Wikipedia

  • Diskrete Fouriertransformation — Die Diskrete Fourier Transformation oder DFT ist die Fourier Transformation eines zeitdiskreten periodischen Signals. Dabei wird das periodische Signal als Superposition eines Gleichanteils, einer Grundschwingung und ihrer Oberschwingungen in ein …   Deutsch Wikipedia

  • Diskrete Wavelet-Transformation — Mit Wavelet Transformation (WT, engl. wavelet transform) wird eine bestimmte Familie von linearen Zeit Frequenz Transformationen in der Mathematik und den Ingenieurswissenschaften (primär: Nachrichtentechnik, Informatik) bezeichnet. Die WT setzt… …   Deutsch Wikipedia

  • Diskrete Fourier-Transformation — Die Diskrete Fourier Transformation oder DFT ist eine Transformation aus dem Bereich der Fourier Analysis. Sie bildet ein zeitdiskretes, endliches Signal, welches periodisch fortgesetzt wird, auf ein diskretes, periodisches Frequenzspektrum ab,… …   Deutsch Wikipedia

  • Diskrete Kosinus-Transformation — Die Diskrete Kosinustransformation (DCT, engl.: „Discrete Cosine Transformation“) ist eine lineare, orthogonale Transformation, die ähnlich der Diskreten Fouriertransformation (DFT) ein zeitdiskretes Signal vom Orts in den Frequenzbereich… …   Deutsch Wikipedia

  • Diskrete Kosinus Transformation — Die Diskrete Kosinustransformation (DCT, engl.: „Discrete Cosine Transformation“) ist eine lineare, orthogonale Transformation, die ähnlich der Diskreten Fouriertransformation (DFT) ein zeitdiskretes Signal vom Orts in den Frequenzbereich… …   Deutsch Wikipedia

  • Schnelle Faltung — Die Schnelle Faltung ist ein Algorithmus zur Berechnung der diskreten, aperiodischen Faltungsoperation mit Hilfe der schnellen Fourier Transformation (FFT). Dabei wird die rechenintensive aperiodische Faltungsoperation im Zeitbereich durch eine… …   Deutsch Wikipedia

  • Zyklische Faltung — Die zyklische Faltung, auch als zirkulare Faltung oder als periodische Faltung bezeichnet, ist in der Funktionalanalysis eine Form der diskreten Faltung. Dabei werden Folgen der Länge N periodisch fortgesetzt, welche sich durch die zyklische… …   Deutsch Wikipedia

  • Faltungsintegral — In der Mathematik und besonders in der Funktionalanalysis beschreibt die Faltung einen mathematischen Operator, der für zwei Funktionen f und g eine dritte Funktion liefert. Diese gibt eine Art „Überlappung“ zwischen f und einer gespiegelten und… …   Deutsch Wikipedia

  • Faltungsprodukt — In der Mathematik und besonders in der Funktionalanalysis beschreibt die Faltung einen mathematischen Operator, der für zwei Funktionen f und g eine dritte Funktion liefert. Diese gibt eine Art „Überlappung“ zwischen f und einer gespiegelten und… …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.