Schnellste Gaußsche Unschärfe-Implementierung

Lesezeit: 8 Minuten

Wie setzt man das am schnellsten um Gaußsche Unschärfe Algorithmus?

Ich werde es also in Java implementieren Grafikkarte Lösungen sind ausgeschlossen. Meine Bewerbung, planetGenesisist plattformübergreifend, also möchte ich nicht JNI.

Schnellste Gaussche Unscharfe Implementierung
Dima

Sie sollten die Tatsache nutzen, dass ein Gaußscher Kern trennbar ist, dh Sie können eine 2D-Faltung als Kombination zweier 1D-Faltung ausdrücken.

Wenn der Filter groß ist, kann es auch sinnvoll sein, die Tatsache zu nutzen, dass die Faltung im räumlichen Bereich der Multiplikation im Frequenzbereich (Fourier) entspricht. Das bedeutet, dass Sie die Fourier-Transformation des Bildes und des Filters nehmen, die (komplexen) Ergebnisse multiplizieren und dann die inverse Fourier-Transformation nehmen können. Die Komplexität der FFT (Fast Fourier Transform) ist O(n log n), während die Komplexität einer Faltung O(n^2) ist. Wenn Sie viele Bilder mit demselben Filter weichzeichnen müssen, müssen Sie die FFT des Filters nur einmal durchführen.

Wenn Sie sich für die Verwendung einer FFT entscheiden, wird die FFTW-Bibliothek ist eine gute Wahl.

  • Beachten Sie auch, dass die Menge der Gaußschen Funktionen unter Fourier-Transformationen geschlossen ist – wenn Sie die Fourier-Transformation einer Gaußschen Funktion nehmen, erhalten Sie nur eine andere Gaußsche Funktion.

    – Dietrich Ep

    15. September 2012 um 12:58 Uhr

Mathe-Jocks werden das wahrscheinlich wissen, aber für alle anderen ..

Aufgrund einer netten mathematischen Eigenschaft der Gaußschen Funktion können Sie ein 2D-Bild schnell verwischen, indem Sie zuerst eine 1D-Gaußsche Unschärfe für jede Zeile des Bildes und dann eine 1D-Unschärfe für jede Spalte ausführen.

  • Danke für die Übersetzung “Sie sollten die Tatsache nutzen, dass ein Gaußscher Kern trennbar ist, dh Sie können eine 2D-Faltung als Kombination von zwei 1D-Falten ausdrücken.” (Dima)

    – Josiah Yoder

    26. August 2015 um 14:31 Uhr

  • @JosiahYoder Falls Sie es nicht bemerkt haben, wurde diese Antwort mehr als 12 Stunden vor der Antwort gepostet, die diese Antwort angeblich “übersetzt”.

    – EvilTak

    18. Februar 2018 um 16:32 Uhr

ULTIMATIVE LÖSUNG

Ich war sehr verwirrt von so vielen Informationen und Implementierungen, ich wusste nicht, welcher ich vertrauen sollte. Nachdem ich es herausgefunden hatte, beschloss ich, einen eigenen Artikel zu schreiben. Ich hoffe, es wird Ihnen Stunden Zeit sparen.

Schnellste Gaußsche Unschärfe (in linearer Zeit)

Es enthält den Quellcode, der (hoffentlich) kurz, sauber und leicht in jede andere Sprache überschreibbar ist. Bitte stimmen Sie ab, damit andere Leute es sehen können.

  • Ich habe eine RGBA-Version Ihres Codes erstellt, um Geschwindigkeit und Qualität mit StackBlur zu vergleichen. Hier ist der Code: pastebin.com/mS0fNYFF – Aber ich muss sagen, dass StackBlur immer noch schneller ist und besser mit den Randbedingungen umgeht (nicht sicher, ob etwas fehlt, aber ich sehe einige Überläufe in Ihrem Code)

    – Quasimondo

    21. November 2013 um 17:45 Uhr


  • Was meinst du mit StackBlur? Wenn Sie den “Akkumulator” -Algorithmus meinen, verwende ich ihn in Algorithmus 4.

    – Iwan Kuckir

    21. November 2013 um 20:06 Uhr

  • StackBlur ist ein quasi-Gaußscher Unschärfealgorithmus, der zumindest meines Wissens einer der schnellsten Nicht-Box-Unschärfealgorithmen überhaupt ist. Das Ergebnis für einen Durchgang liegt irgendwo zwischen einem Box Blur und einem Gaußschen und das Ergebnis sollte gut genug sein, wenn Sie es eher für visuelle Effekte als für die wissenschaftliche Bildanalyse benötigen.

    – Quasimondo

    22. November 2013 um 10:03 Uhr

  • @IvanKuckir Ich kann es nicht zum Laufen bringen. Würden Sie bitte ein Beispiel geben, wie Sie Ihre Methode in einer HTML-Seite aufrufen? (sehr dringend benötigt)

    – Kamran

    28. Mai 2016 um 20:38 Uhr


  • @IvanKuckir Könnten Sie sich bitte Folgendes ansehen: Schnellste Gaußsche Unschärfe funktioniert nicht?

    – Kamran

    28. Mai 2016 um 23:01 Uhr

1647101830 192 Schnellste Gaussche Unscharfe Implementierung
Sid Datta

  1. ich fand Quasimondo : Inkubator : Verarbeitung : Schnelle Gaußsche Unschärfe. Diese Methode enthält viele Annäherungen wie die Verwendung von ganzen Zahlen und Nachschlagetabellen anstelle von Gleitkommazahlen und Gleitkommadivisionen. Ich weiß nicht, wie viel Beschleunigung das in modernem Java-Code ist.

  2. Schnelle Schatten auf Rechtecken hat einen Näherungsalgorithmus mit B-Splines.

  3. Schneller Gaußscher Unschärfealgorithmus in C# behauptet, einige coole Optimierungen zu haben.

  4. Ebenfalls, Schnelle Gaußsche Unschärfe (PDF) von David Everly hat eine schnelle Methode zur Verarbeitung von Gaußscher Unschärfe.

Ich würde die verschiedenen Methoden ausprobieren, sie benchmarken und die Ergebnisse hier posten.

Für meine Zwecke habe ich die grundlegende Methode (XY-Achse unabhängig verarbeiten) und die von David Everly kopiert und implementiert Schnelle Gaußsche Unschärfe Methode aus dem Internet. Sie unterscheiden sich in Parametern, daher konnte ich sie nicht direkt vergleichen. Letzteres durchläuft jedoch eine viel geringere Anzahl von Iterationen für einen großen Unschärferadius. Letzteres ist auch ein Näherungsalgorithmus.

Schnellste Gaussche Unscharfe Implementierung
Steve Hanow

Sie möchten wahrscheinlich die Box-Unschärfe, die viel schneller ist. Sehen dieser Link für ein tolles Tutorial und einige C-Code kopieren und einfügen.

  • Wie verbinden Sie die STD des Gaussian Kernel mit der Länge der Box Blur?

    – Royi

    30. April 2014 um 0:00 Uhr

Versuchen Sie für größere Unschärferadien, a anzuwenden Box Unschärfe drei Mal. Dies nähert sich sehr gut einer Gaußschen Unschärfe an und ist viel schneller als eine echte Gaußsche Unschärfe.

  • Wie verbinden Sie die STD des Gaussian Kernel mit der Länge der Box Blur?

    – Royi

    30. April 2014 um 0:00 Uhr

Ich habe Ivan Kuckirs Implementierung einer schnellen Gaußschen Unschärfe, die drei Durchgänge mit linearen Box-Unschärfen verwendet, in Java konvertiert. Der resultierende Prozess ist O(n), wie er gesagt hat in seinem eigenen Blog. Wenn Sie mehr darüber erfahren möchten, warum die 3-Zeit-Box-Unschärfe der Gaußschen Unschärfe (3%) entspricht, können Sie sich das ansehen Box Unschärfe und Gaußsche Unschärfe.

Hier ist die Java-Implementierung.

@Override
public BufferedImage ProcessImage(BufferedImage image) {
    int width = image.getWidth();
    int height = image.getHeight();

    int[] pixels = image.getRGB(0, 0, width, height, null, 0, width);
    int[] changedPixels = new int[pixels.length];

    FastGaussianBlur(pixels, changedPixels, width, height, 12);

    BufferedImage newImage = new BufferedImage(width, height, image.getType());
    newImage.setRGB(0, 0, width, height, changedPixels, 0, width);

    return newImage;
}

private void FastGaussianBlur(int[] source, int[] output, int width, int height, int radius) {
    ArrayList<Integer> gaussianBoxes = CreateGausianBoxes(radius, 3);
    BoxBlur(source, output, width, height, (gaussianBoxes.get(0) - 1) / 2);
    BoxBlur(output, source, width, height, (gaussianBoxes.get(1) - 1) / 2);
    BoxBlur(source, output, width, height, (gaussianBoxes.get(2) - 1) / 2);
}

private ArrayList<Integer> CreateGausianBoxes(double sigma, int n) {
    double idealFilterWidth = Math.sqrt((12 * sigma * sigma / n) + 1);

    int filterWidth = (int) Math.floor(idealFilterWidth);

    if (filterWidth % 2 == 0) {
        filterWidth--;
    }

    int filterWidthU = filterWidth + 2;

    double mIdeal = (12 * sigma * sigma - n * filterWidth * filterWidth - 4 * n * filterWidth - 3 * n) / (-4 * filterWidth - 4);
    double m = Math.round(mIdeal);

    ArrayList<Integer> result = new ArrayList<>();

    for (int i = 0; i < n; i++) {
        result.add(i < m ? filterWidth : filterWidthU);
    }

    return result;
}

private void BoxBlur(int[] source, int[] output, int width, int height, int radius) {
    System.arraycopy(source, 0, output, 0, source.length);
    BoxBlurHorizantal(output, source, width, height, radius);
    BoxBlurVertical(source, output, width, height, radius);
}

private void BoxBlurHorizontal(int[] sourcePixels, int[] outputPixels, int width, int height, int radius) {
    int resultingColorPixel;
    float iarr = 1f / (radius + radius);
    for (int i = 0; i < height; i++) {
        int outputIndex = i * width;
        int li = outputIndex;
        int sourceIndex = outputIndex + radius;

        int fv = Byte.toUnsignedInt((byte) sourcePixels[outputIndex]);
        int lv = Byte.toUnsignedInt((byte) sourcePixels[outputIndex + width - 1]);
        float val = (radius) * fv;

        for (int j = 0; j < radius; j++) {
            val += Byte.toUnsignedInt((byte) (sourcePixels[outputIndex + j]));
        }

        for (int j = 0; j < radius; j++) {
            val += Byte.toUnsignedInt((byte) sourcePixels[sourceIndex++]) - fv;
            resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
            outputPixels[outputIndex++] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
        }

        for (int j = (radius + 1); j < (width - radius); j++) {
            val += Byte.toUnsignedInt((byte) sourcePixels[sourceIndex++]) - Byte.toUnsignedInt((byte) sourcePixels[li++]);
            resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
            outputPixels[outputIndex++] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
        }

        for (int j = (width - radius); j < width; j++) {
            val += lv - Byte.toUnsignedInt((byte) sourcePixels[li++]);
            resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
            outputPixels[outputIndex++] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
        }
    }
}

private void BoxBlurVertical(int[] sourcePixels, int[] outputPixels, int width, int height, int radius) {
    int resultingColorPixel;
    float iarr = 1f / (radius + radius + 1);
    for (int i = 0; i < width; i++) {
        int outputIndex = i;
        int li = outputIndex;
        int sourceIndex = outputIndex + radius * width;

        int fv = Byte.toUnsignedInt((byte) sourcePixels[outputIndex]);
        int lv = Byte.toUnsignedInt((byte) sourcePixels[outputIndex + width * (height - 1)]);
        float val = (radius + 1) * fv;

        for (int j = 0; j < radius; j++) {
            val += Byte.toUnsignedInt((byte) sourcePixels[outputIndex + j * width]);
        }
        for (int j = 0; j <= radius; j++) {
            val += Byte.toUnsignedInt((byte) sourcePixels[sourceIndex]) - fv;
            resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
            outputPixels[outputIndex] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
            sourceIndex += width;
            outputIndex += width;
        }
        for (int j = radius + 1; j < (height - radius); j++) {
            val += Byte.toUnsignedInt((byte) sourcePixels[sourceIndex]) - Byte.toUnsignedInt((byte) sourcePixels[li]);
            resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
            outputPixels[outputIndex] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
            li += width;
            sourceIndex += width;
            outputIndex += width;
        }
        for (int j = (height - radius); j < height; j++) {
            val += lv - Byte.toUnsignedInt((byte) sourcePixels[li]);
            resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
            outputPixels[outputIndex] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
            li += width;
            outputIndex += width;
        }
    }
}

  • Es funktioniert großartig, aber das Ergebnisbild ist in Schwarzweiß. Wie kann ich es farbig machen?

    – Tamer Saleh

    24. November 2021 um 17:33 Uhr

994320cookie-checkSchnellste Gaußsche Unschärfe-Implementierung

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy