====== 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.

→ [[lyx_-_programmiersprache:units:mathematik|Mathematik-Units]] · [[lyx_-_programmiersprache:units:fft|std.fft]] · [[lyx_-_programmiersprache:units:wavelet|std.wavelet]] · [[lyx_-_programmiersprache:guides:image|Bildverarbeitung]]

<code lyx>
import std.convolve;
</code>

Schicht 1, hängt an [[lyx_-_programmiersprache:units:fft|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 |

<box tip>
> **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.
</box>

----

===== Eine Faltung von Hand =====

<code lyx>
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;
}
</code>

<code>
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
</code>

''[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.

<box gh>
> **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.
</box>

----

===== 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 |

<box tip>
> **''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.
</box>

----

===== Offener Punkt =====

<box gh>
> **Die inneren Faltungsschleifen summieren noch naiv** — acht Stellen. Bei sehr langen Signalen mit stark verschiedenen Größenordnungen lohnt eine Gegenprobe über [[lyx_-_programmiersprache:units:sum|std.sum]]. Für Bilddaten und übliche Signallängen fällt es nicht ins Gewicht.
</box>

----

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