std.convolve — Faltung und Filter

Faltung direkt oder über die FFT, vier Randbehandlungen, zweidimensional und separabel, Overlap-Add für lange Signale, dazu fertige Kerne.

→ Mathematik-Units · std.fft · std.wavelet · Bildverarbeitung

import std.convolve;

Schicht 1, hängt an std.fft, std.math und std.alloc. 22 Funktionen, sieben Konstanten. Alle Beispiele mit lyxc 1.0.21A übersetzt und ausgeführt.

Zwei Entscheidungen vor jeder Faltung

Wie lang ist das Ergebnis?

Konstante	Länge bei `na=5`, `nk=3`	Bedeutung
`CONV_FULL`	7	`na + nk − 1` — alles, auch die Ränder
`CONV_SAME`	5	so lang wie das Eingangssignal
`CONV_VALID`	3	nur wo der Kern vollständig überlappt

ConvOutputLen(na, nk, mode) rechnet es aus — vor dem Reservieren des Zielpuffers.

Was passiert am Rand?

Konstante	Verhalten
`CONV_EDGE_ZERO`	außerhalb ist null
`CONV_EDGE_CLAMP`	der Randwert wird fortgesetzt
`CONV_EDGE_REFLECT`	das Signal wird gespiegelt
`CONV_EDGE_WRAP`	zyklisch, das Ende schließt an den Anfang an

Die Randwahl ist sichtbar, nicht theoretisch. Ein Weichzeichner mit CONV_EDGE_ZERO erzeugt an den Bildrändern einen dunklen Saum, weil dort gegen Schwarz gemittelt wird. CONV_EDGE_CLAMP vermeidet das und ist für Bilder meist richtig; CONV_EDGE_REFLECT ist die bessere Wahl, wenn der Rand Struktur trägt. CONV_EDGE_WRAP gehört zu Signalen, die tatsächlich periodisch sind — sonst mischt es das Ende in den Anfang.

Eine Faltung von Hand

unit main;
import std.io;
import std.string;
import std.alloc;
import std.convolve;

fn ZI(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }
fn ZF(t: pchar, v: f64): void { Print(t); PrintF64(v); }

fn main(): int64 {
    ZI("OutputLen(5,3,FULL)  : ", ConvOutputLen(5, 3, CONV_FULL));
    ZI("OutputLen(5,3,SAME)  : ", ConvOutputLen(5, 3, CONV_SAME));
    ZI("OutputLen(5,3,VALID) : ", ConvOutputLen(5, 3, CONV_VALID));
    ZI("ConvThreshold        : ", ConvThreshold());

    var a: int64 := alloc(3 * 8);
    pokef64(a, 1.0); pokef64(a + 8, 2.0); pokef64(a + 16, 3.0);
    var k: int64 := alloc(2 * 8);
    pokef64(k, 1.0); pokef64(k + 8, 1.0);

    var out: int64 := alloc(8 * 8);
    ConvDirect(a, 3, k, 2, CONV_FULL, CONV_EDGE_ZERO, out);
    Print("FULL:\n");
    var i: int64 := 0;
    while (i < 4) { PrintF64(peekf64(out + i * 8)); i := i + 1; }

    var gl: int64 := ConvGaussLen(1.0);
    ZI("GaussLen(sigma=1)    : ", gl);
    var gk: int64 := alloc(gl * 8);
    ConvKernelGauss1D(gk, gl, 1.0);
    ZF("KernelSum(Gauss)     : ", ConvKernelSum(gk, gl));

    var bx: int64 := alloc(4 * 8);
    ConvKernelBox(bx, 4);
    ZF("KernelSum(Box 4)     : ", ConvKernelSum(bx, 4));
    return 0;
}

OutputLen(5,3,FULL)  : 7
OutputLen(5,3,SAME)  : 5
OutputLen(5,3,VALID) : 3
ConvThreshold        : 64
FULL:
1.000000
3.000000
5.000000
3.000000
GaussLen(sigma=1)    : 7
KernelSum(Gauss)     : 0.999999
KernelSum(Box 4)     : 1.000000

[1, 2, 3] gefaltet mit [1, 1] ergibt [1, 3, 5, 3] — jeder Wert plus sein Vorgänger. Die Kernsummen sind 1: die fertigen Kerne sind normiert, ein Weichzeichner ändert also die mittlere Helligkeit nicht.

Direkt oder über die FFT

Funktion	Aufwand
`ConvDirect`	O(na · nk)
`ConvFft`	O(n log n)
`ConvFilter`	wählt selbst
`ConvOverlapAdd`	langes Signal, kurzer Kern

ConvThreshold() ist 64. Unterhalb dieser Kernlänge ist die direkte Faltung schneller, darüber die FFT — ConvFilter entscheidet danach von selbst und ist deshalb der normale Weg.

ConvOverlapAdd ist für den Fall gedacht, dass das Signal nicht als Ganzes in den Speicher passt oder als Strom eintrifft: es zerlegt in Blöcke, faltet jeden über die FFT und setzt die überlappenden Ränder wieder zusammen.

ConvCorrelateDirect rechnet die Korrelation — dasselbe wie Faltung, nur ohne den Kern zu spiegeln. Bei symmetrischen Kernen fällt der Unterschied nicht auf, bei Ableitungskernen wie Sobel kehrt er das Vorzeichen um.

Fertige Kerne

Funktion	Kern
`ConvKernelBox(out, n)`	gleitender Mittelwert
`ConvKernelGauss1D(out, n, sigma)`	Gauß, eindimensional
`ConvKernelGauss2D(out, n, sigma)`	Gauß, zweidimensional
`ConvGaussLen(sigma)`	passende Kernlänge zu einem `sigma`
`ConvKernelSobelX` / `ConvKernelSobelY`	Kantenerkennung, 3×3
`ConvKernelLaplace`	zweite Ableitung, 3×3
`ConvKernelSharpen`	Schärfen, 3×3

ConvNormalize(k, n) bringt einen selbst gebauten Kern auf Summe 1; ConvKernelSum fragt nach.

Ein Kern mit Summe ungleich 1 ändert die Helligkeit. Bei ConvKernelSharpen und den Sobel-Kernen ist das gewollt — Sobel hat Summe 0, weil er Änderungen misst, nicht Werte. Bei einem selbst gebauten Weichzeichner ist es fast immer ein Fehler, und er fällt erst auf, wenn das Bild sichtbar heller oder dunkler wird.

Zweidimensional

Funktion	Zweck
`Conv2D(img, w, h, …)`	allgemeine 2D-Faltung
`Conv2DCorrelate`	ohne Kernspiegelung
`Conv2DSeparable`	erst zeilenweise, dann spaltenweise
`Conv2DGaussBlur(img, w, h, sigma, …)`	Weichzeichnen in einem Aufruf
`Conv2DSobelMagnitude`	Kantenstärke aus beiden Sobel-Richtungen

Conv2DSeparable ist bei großen Kernen der entscheidende Unterschied. Ein Gauß-Kern lässt sich in zwei eindimensionale zerlegen: statt n² Multiplikationen je Bildpunkt kostet er nur 2n. Bei sigma = 5 und einem 31×31-Kern sind das 961 gegen 62 Operationen — Faktor 15. Conv2DGaussBlur nutzt das von sich aus.

Offener Punkt

Die inneren Faltungsschleifen summieren noch naiv — acht Stellen. Bei sehr langen Signalen mit stark verschiedenen Größenordnungen lohnt eine Gegenprobe über std.sum. Für Bilddaten und übliche Signallängen fällt es nicht ins Gewicht.

Letzte Aktualisierung: 2026-08-16 · alle Beispiele mit lyxc 1.0.21A übersetzt und ausgeführt; Ausgabelängen, Faltungsergebnis und Kernnormierung nachgerechnet.