Wie wird Gaußscher Weichzeichner implementiert?

Ich habe gelesen, dass die Unschärfe in Echtzeit-Grafiken erfolgt, indem sie auf einer Achse und dann auf der anderen ausgeführt wird.

Ich habe in 1D in der Vergangenheit ein bisschen Faltung gemacht, aber ich fühle mich damit nicht besonders wohl und weiß auch nicht genau, was ich in diesem Fall tun soll.

Kann jemand in einfachen Worten erklären, wie ein 2D-Gaußscher Weichzeichner eines Bildes gemacht wird?

Ich habe auch gehört, dass der Radius der Unschärfe die Leistung beeinträchtigen kann. Ist das auf eine größere Faltung zurückzuführen?

In der Faltung werden zwei mathematische Funktionen kombiniert, um eine dritte Funktion zu erzeugen. In der Bildverarbeitung werden Funktionen üblicherweise als Kernel bezeichnet. Ein Kernel ist nichts anderes als ein (quadratisches) Array von Pixeln (sozusagen ein kleines Bild). Normalerweise addieren sich die Werte im Kernel zu eins. Dies soll sicherstellen, dass dem Bild nach der Operation keine Energie hinzugefügt oder entzogen wird.

Insbesondere ist ein Gaußscher Kern (der für die Gaußsche Unschärfe verwendet wird) eine quadratische Anordnung von Pixeln, bei der die Pixelwerte den Werten einer Gaußschen Kurve (in 2D) entsprechen.

Jedes Pixel im Bild wird mit dem Gaußschen Kern multipliziert. Dazu wird das mittlere Pixel des Kernels auf dem Bildpixel platziert und die Werte im Originalbild mit den Pixeln im Kernel multipliziert, die sich überlappen. Die aus diesen Multiplikationen resultierenden Werte werden addiert und dieses Ergebnis wird für den Wert am Zielpixel verwendet. Wenn Sie sich das Bild ansehen, multiplizieren Sie den Wert bei (0,0) im Eingabearray mit dem Wert bei (i) im Kernelarray und den Wert bei (1,0) im Eingabearray mit dem Wert bei (h ) im Kernel-Array und so weiter. Addieren Sie dann alle diese Werte, um den Wert für (1,1) im Ausgabebild zu erhalten.

Um Ihre zweite Frage zuerst zu beantworten, ist die Operation umso teurer, je größer der Kernel ist. Je größer der Radius der Unschärfe ist, desto länger dauert die Operation.

Um Ihre erste Frage zu beantworten, können Sie, wie oben erläutert, die Faltung durchführen, indem Sie jedes Eingabepixel mit dem gesamten Kernel multiplizieren. Wenn der Kern symmetrisch ist (wie ein Gauß-Kernel), können Sie auch jede Achse (x und y) unabhängig multiplizieren, wodurch sich die Gesamtzahl der Multiplikationen verringert. In mathematischen Begriffen kann eine trennbare Matrix in (M × 1) und (1 × N) Matrizen zerlegt werden. Für den obigen Gaußschen Kernel bedeutet dies, dass Sie auch die folgenden Kernel verwenden können:

$$\frac1{256}\cdot\begin{bmatrix} 1&4&6&4&1\\ 4&16&24&16&4\\ 6&24&36&24&6\\ 4&16&24&16&4\\ 1&4&6&4&1 \end{bmatrix} = \frac1{256}\cdot\begin{bmatrix} 1\\4\\6\\4\\1 \end{bmatrix}\cdot\begin{bmatrix} 1&4&6&4&1 \end{bmatrix}$$

Sie würden jetzt jedes Pixel im Eingabebild mit beiden Kerneln multiplizieren und die resultierenden Werte addieren, um den Wert für das Ausgabepixel zu erhalten.

Weitere Informationen darüber, wie Sie feststellen können, ob ein Kernel trennbar ist, finden Sie unter diesem Link .

Bearbeiten: Die beiden oben gezeigten Kernel verwenden leicht unterschiedliche Werte. Dies liegt daran, dass der (Sigma) -Parameter, der für die Gauß-Kurve zum Erstellen dieser Kernel verwendet wurde, in beiden Fällen geringfügig unterschiedlich war. Eine Erklärung, welche Parameter die Form der Gaußschen Kurve und damit die Werte im Kernel beeinflussen, finden Sie unter diesem Link

Bearbeiten: Im zweiten Bild oben steht, dass der verwendete Kernel gespiegelt ist. Dies macht natürlich nur dann einen Unterschied, wenn der von Ihnen verwendete Kernel nicht symmetrisch ist. Der Grund, warum Sie den Kernel umdrehen müssen, hängt mit den mathematischen Eigenschaften der Faltungsoperation zusammen (siehe Link für eine ausführlichere Erklärung zur Faltung). Einfach ausgedrückt: Wenn Sie den Kernel nicht spiegeln würden, würde das Ergebnis der Faltungsoperation gespiegelt. Wenn Sie den Kernel umdrehen, erhalten Sie das richtige Ergebnis.

Hier ist der beste Artikel, den ich zum Thema gelesen habe: Effiziente Gaußsche Unschärfe mit linearer Abtastung . Es beantwortet alle Ihre Fragen und ist wirklich zugänglich.

Für den Laien sehr kurze Erklärung: Gauß ist eine Funktion mit der schönen Eigenschaft, trennbar zu sein, was bedeutet, dass eine 2D-Gaußfunktion berechnet werden kann, indem zwei 1D-Gaußfunktionen kombiniert werden.

Für eine Größe ( ) müssen Sie also nur Werte ( ) auswerten , was erheblich weniger ist. Wenn Ihre Operation darin besteht, ein Texturelement (im Allgemeinen als "Tap" bezeichnet ) zu lesen , ist dies eine gute Nachricht: Weniger Taps sind billiger, da ein Texturabruf Kosten verursacht.$n \times n$$O(n^2)$$2 \times n$$O(n)$

Aus diesem Grund verwenden Unschärfealgorithmen diese Eigenschaft, indem sie zwei Durchgänge ausführen, einen zum horizontalen Unschärfen durch Sammeln der horizontalen Pixel und einen zum vertikalen Unschärfen durch Sammeln der vertikalen Pixel. Das Ergebnis ist die endgültige verschwommene Pixelfarbe.$n$$n$

Im Allgemeinen wird eine Faltung durchgeführt, indem das Integral des Produkts zweier Funktionen in einem Schiebefenster verwendet wird. Wenn Sie jedoch keinen mathematischen Hintergrund haben, ist dies keine sehr hilfreiche Erklärung, und Sie erhalten mit Sicherheit keine nützliche Intuition dafür. Intuitiver lässt eine Faltung zu, dass mehrere Punkte in einem Eingangssignal einen einzelnen Punkt in einem Ausgangssignal beeinflussen.

Da Sie mit Faltungen nicht besonders vertraut sind, lassen Sie uns zunächst untersuchen, was eine Faltung in einem diskreten Kontext wie diesem bedeutet, und dann eine einfachere Unschärfe behandeln.

In unserem diskreten Kontext können wir unsere zwei Signale multiplizieren, indem wir einfach jedes entsprechende Sample multiplizieren. Das Integral ist auch einfach zu diskretisieren. Wir addieren einfach jedes Sample in dem Intervall, über das wir integrieren. Eine einfache diskrete Faltung ist die Berechnung eines gleitenden Durchschnitts. Wenn Sie den gleitenden Durchschnitt von 10 Samples berechnen möchten, können Sie sich vorstellen, dass Ihr Signal durch eine 10-malige und 0,1-malige Verteilung gewickelt wird. Jedes Sample im Fenster wird zuerst mit 0,1 multipliziert und dann werden alle 10 addiert, um zu produzieren der Durchschnitt. Dies zeigt auch einen interessanten und wichtigen Unterschied: Wenn Sie mit einer Faltung verwischen, sollte die verwendete Verteilung über alle Samples hinweg 1,0 ergeben. Andernfalls wird die Gesamthelligkeit des Bildes beim Anwenden erhöht oder verringert.

Nachdem wir uns nun die Windungen angesehen haben, können wir zu Unschärfen übergehen. Eine Gaußsche Unschärfe wird implementiert, indem ein Bild durch eine Gaußsche Verteilung gefaltet wird. Andere Unschärfen werden im Allgemeinen implementiert, indem das Bild durch andere Verteilungen gefaltet wird. Die einfachste Unschärfe ist die Rahmenunschärfe. Sie verwendet die oben beschriebene Verteilung, einen Rahmen mit Flächeneinheit. Wenn Sie einen Bereich von 10 x 10 verwischen möchten, multiplizieren Sie jedes Sample in der Box mit 0,01 und addieren Sie alle Werte, um das mittlere Pixel zu erhalten. Wir müssen weiterhin sicherstellen, dass die Gesamtsumme aller Samples in unserer Unschärfeverteilung 1,0 beträgt, um sicherzustellen, dass das Bild nicht heller oder dunkler wird.

Eine Gaußsche Unschärfe folgt dem gleichen breiten Verfahren wie eine Kastenunschärfe, verwendet jedoch eine komplexere Formel, um die Gewichte zu bestimmen. Die Verteilung kann basierend auf dem Abstand vom Zentrum berechnet werden r, indem ausgewertet wird. Die Summe aller Abtastwerte in einem Gaußschen wird schließlich sein Ungefähr 1,0, wenn Sie jeden einzelnen Pixel abtasten, aber die Tatsache, dass ein Gauß'scher Wert unendlich unterstützt wird (er hat überall Werte), bedeutet, dass Sie eine leicht modifizierte Version verwenden müssen, die mit nur wenigen Werten 1,0 ergibt.

$$\frac{e^{-x^2/2}}{\sqrt{2\pi}}$$

Natürlich können beide Prozesse sehr teuer sein, wenn Sie sie in einem sehr großen Radius ausführen, da Sie viele Pixel abtasten müssen, um die Unschärfe zu berechnen. Hier kommt der letzte Trick ins Spiel: Sowohl eine Gaußsche Unschärfe als auch eine Kastenunschärfe werden als "trennbare" Unschärfe bezeichnet. Dies bedeutet, dass, wenn Sie die Unschärfe entlang einer Achse und anschließend entlang der anderen Achse ausführen, genau das gleiche Ergebnis erzielt wird, als ob Sie sie entlang beider Achsen gleichzeitig ausgeführt hätten. Dies kann enorm wichtig sein. Wenn Ihre Unschärfe 10 Pixel breit ist, werden 100 Proben in der naiven Form benötigt, aber nur 20, wenn sie getrennt sind. Der Unterschied wird nur größer, da die kombinierte Unschärfe , während die getrennte Form .$O(n^2)$$O(n)$

Das Wichtigste, was bei der Implementierung der Gaußschen Unschärfe berücksichtigt werden muss, ist, wie bereits erwähnt, die Aufteilung des 2D-Faltungsfilters in zwei 1D-Faltungen, da hierdurch die Komplexität von auf .$O(n^2)$$O(n)$

Es gibt jedoch noch zwei weitere Tricks, die Sie in einer tatsächlichen Implementierung berücksichtigen sollten:

Der Filter hat einen bestimmten Radius. Aus diesem Grund müssen Sie genau an den Rändern mit Pixeln rechnen, die außerhalb des Bildes liegen. In einem solchen Fall können Sie eine der folgenden Methoden ausprobieren: Für die äußeren Pixel nehmen Sie einfach den zuletzt möglichen Wert (dh das Pixel ganz am Rand, wie in max(x, 0). Oder Sie können das Bild nach außen "spiegeln" (wie in x < 0 ? -x : x). Oder Sie halten einfach an der Grenze an, müssen dann aber den Nenner im Faltungsfilter so einstellen, dass er 1 ergibt. Zum Beispiel:

$$\operatorname{sum} \frac{1}{256} \begin{bmatrix} 1 & 4 & 6 & 4 & 1 \\ 4 & 16 & 24 & 16 & 4 \\ 6 & 24 & 36 & 24 & 6 \\ 4 & 16 & 24 & 16 & 4 \\ 1 & 4 & 6 & 4 & 1 \\ \end{bmatrix} = \operatorname{sum} \frac{1}{225} \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 16 & 24 & 16 & 0 \\ 0 & 24 & 36 & 16 & 0 \\ 0 & 16 & 24 & 16 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} = 1.$$ Ein weiterer Trick betrifft die Berechnung der tatsächlichen Koeffizienten des Kernels. Natürlich könnten Sie versuchen, die Gaußsche Funktion zu implementieren, aber viel schneller können Sie feststellen, dass der 1D-Kernel das Pascalsche Dreieck neu zusammensetzt . Zum Beispiel:

     1
    1 1
   1 2 1
  1 3 3 1
[1 4 6 4 1]