Schnellste Gaußsche Unschärfe-Implementierung

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.

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.

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.

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.

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.

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.

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.

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;
        }
    }
}