La mise en œuvre la plus rapide du flou gaussien

vous devez utiliser le fait qu'un noyau gaussien est séparable, I. E. vous pouvez exprimer une convolution 2D comme une combinaison de deux convolutions 1D.

si le filtre est grand, il peut également être logique d'utiliser le fait que la convolution dans le domaine spatial est équivalente à la multiplication dans le domaine de fréquence (Fourier). Cela signifie que vous pouvez prendre la Transformée de Fourier de l'image et le filtre, multiplier les résultats (complexes), et puis prendre L'inverse de Fourier transformer. La complexité de la transformation de Fourier rapide est O (N log n), tandis que la complexité d'une convolution est O(N^2). En outre, si vous avez besoin de flouter de nombreuses images avec le même filtre, vous n'aurez besoin de prendre le FFT du filtre qu'une seule fois.

si vous décidez d'utiliser un FFT, la bibliothèque FFTW est un bon choix.

jocks de maths sont susceptibles de savoir cela, mais pour quelqu'un d'autre..

grâce à une belle propriété mathématique du gaussien, vous pouvez brouiller rapidement une image 2D en lançant d'abord un brouillage gaussien 1D sur chaque ligne de l'image, puis exécuter un brouillage 1D sur chaque colonne.

1. j'ai trouvé Quasimondo : incubateur : traitement : Fast Gaussian Blur . Cette méthode contient beaucoup d'approximations comme l'utilisation des entiers et des tables de recherche au lieu des flotteurs et des divisions à virgule flottante. Je ne sais pas si c'est rapide dans le code Java moderne.

2. les ombres rapides sur les Rectangles a un approximation de l'algorithme en utilisant B-splines .

3. L'algorithme de flou gaussien rapide dans C# prétend avoir quelques optimisations fraîches.

4. aussi, Fast Gaussian Blur (PDF) par David Everly a une méthode rapide pour le traitement gaussien flou.

je voudrais essayer les différentes méthodes, les comparer et afficher les résultats ici.

pour mes besoins, j'ai copié et mis en œuvre la méthode de base (process X-Y axis independently) et la méthode Fast Gaussian Blur de David Everly à partir d'Internet. Ils diffèrent dans les paramètres, donc je ne pouvais pas les comparer directement. Cependant ce dernier passe par beaucoup moins d'itérations pour un grand rayon de flou. Aussi, celle-ci est approximatif algorithme.

ULTIMATE SOLUTION

j'étais très confus par tant d'informations et d'implémentations, Je ne savais pas à qui faire confiance. Après avoir compris, j'ai décidé d'écrire mon propre article. J'espère que ça vous fera gagner des heures.

Flou Gaussien le plus rapide (en temps linéaire)

contient le code source, qui (je l'espère) est court, propre et facilement réinscriptible à tout autre langue. S'il vous plaît voter, alors que d'autres gens peuvent le voir.

vous voulez probablement la boîte floue, qui est beaucoup plus rapide. Voir ce lien pour un excellent tutoriel et quelques copier & coller code C .

pour des rayons de flou plus grands, essayez d'appliquer une boîte flou trois fois. Cela se rapprochera très bien d'un gaussien flou, et sera beaucoup plus rapide qu'un vrai gaussien flou.

j'envisagerais D'utiliser CUDA ou une autre boîte à outils de programmation GPU pour cela, surtout si vous voulez utiliser un noyau plus grand. Sinon, il y a toujours la main à ajuster vos boucles dans l'assemblage.

• Étape 1: SIMD 1-dimensions flou Gaussien
• Étape 2: transposer
• Étape 3: répéter l'étape 1

il est préférable de le faire sur de petits blocs, car une transposition pleine image est lente, tandis qu'une transposition petit bloc peut être fait extrêmement rapide en utilisant une chaîne de PUNPCKs ( PUNPCKHBW, PUNPCKHDQ, PUNPCKHWD, PUNPCKLBW, PUNPCKLDQ, PUNPCKLWD ).

en 1D:

Flouant en utilisant presque n'importe quel noyau à plusieurs reprises aura tendance à un noyau gaussien. C'est ce qui est si cool dans la distribution gaussienne, et c'est pourquoi les statisticiens aiment ça. Alors choisissez quelque chose qui est facile à flouter et l'appliquer plusieurs fois.

par exemple, il est facile de flouter avec un noyau en forme de boîte. Calculez d'abord une somme cumulative:

y(i) = y(i-1) + x(i)

puis:

blurred(i) = y(i+radius) - y(i-radius)

Répétez l'opération plusieurs fois.

ou vous pourriez aller et venir plusieurs fois avec une certaine variété d'un filtre IIR , ceux-ci sont également rapides.

en 2D ou plus:

flou dans chaque dimension l'une après l'autre, comme disait DarenW.

j'ai lutté avec ce problème pour ma recherche et essayé et méthode intéressante pour un Gaussian flou rapide. Tout d'abord, comme mentionné, il est préférable de séparer le flou en deux blurs 1D, mais en fonction de votre matériel pour le calcul réel des valeurs des pixels, vous pouvez en fait pré-calculer toutes les valeurs possibles et les stocker dans une table de recherche.

en d'autres termes, pré-calculer chaque combinaison de Gaussian coefficient * input pixel value . Bien sûr, vous aurez besoin de discrétisez vos coefficients, mais je voulais juste ajouter cette solution. Si vous avez un IEEE abonnement, vous pouvez lire plus dans flou image rapide en utilisant la table de recherche pour l'extraction de caractéristique en temps réel .

finalement, j'ai fini par utiliser CUDA cependant:)

j'ai converti la mise en œuvre D'Ivan Kuckir d'un blur gaussien rapide qui utilise trois passes avec la boîte linéaire blurs à java. Le processus qui en résulte est O(n) comme il l'a déclaré sur son propre blog . Si vous souhaitez en savoir plus sur pourquoi 3 fois zone de flou se rapproche de flou Gaussien(3%) mon ami, vous pouvez consulter zone de flou et flou Gaussien .

Voici l'implémentation java.

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

il existe plusieurs méthodes rapides pour Gauss flou de données 2d. Ce que vous devez savoir sur.

1. c'est un filtre séparable , il ne nécessite donc que deux convolutions 1d.
2. pour les gros noyaux vous pouvez traiter la copie réduite de l'image et que le haut de gamme en arrière.
3. bonne approximation peut être fait par plusieurs filtres de boîte (également séparable), (peut être réglé le nombre d'itérations et les tailles de noyau)
4. existent O(n) algorithme de complexité (pour n'importe quelle taille de noyau) pour une approximation précise de gauss par filtre IIR.

votre choix dépend de la vitesse requise, de la précision et de la complexité de la mise en œuvre.

essayez D'utiliser Box flou comme je l'ai fait ici: Le Rapprochement De Flou Gaussien À L'Aide De Longues Zone De Flou

C'est la meilleure approximation.

en utilisant des Images intégrales, vous pouvez le rendre encore plus rapide.

Si vous le faites, s'il vous Plaît partagez votre solution.

répondant à cette vieille question avec nouvelles bibliothèques qui ont été mis en œuvre maintenant(à partir de 2016), parce qu'il ya beaucoup de nouveaux progrès de la technologie GPU avec Java.

comme suggéré dans quelques autres réponses, CUDA est une alternative. Mais java a le support de CUDA maintenant.

IBM bibliothèque CUDA4J: fournit une API Java pour la gestion et l'accès GPU périphériques, bibliothèques, noyaux et mémoire. En utilisant ces nouveaux API, il est possible d'écrire des programmes Java qui gèrent les caractéristiques des appareils GPU et déchargent le travail sur le GPU avec la commodité du modèle de mémoire Java, les exceptions, et la gestion automatique des ressources.

Jcuda: Java liaisons pour NVIDIA CUDA et des bibliothèques. Avec JCuda, il est possible d'interagir avec L'API d'exécution et de pilote CUDA des programmes Java.

Aparapi: permet Java les développeurs de profiter de la puissance de calcul des appareils GPU et APU en exécutant des fragments de code parallèle de données sur le GPU plutôt que d'être confinés au CPU local.

Certains Java OpenCL liaison bibliothèques

https://github.com/ochafik/JavaCL : fixations Java pour OpenCL: une bibliothèque OpenCL orientée objet, basée sur des fixations de bas niveau générées automatiquement

http://jogamp.org/jocl/www/ : liaisons Java pour OpenCL: une bibliothèque OpenCL orientée objet, basée sur des liaisons de bas niveau générées automatiquement

http://www.lwjgl.org / : fixations Java pour OpenCL: Fixations de bas niveau générées automatiquement et classes de commodité orientées objet

http://jocl.org / : fixations Java pour OpenCL: Fixations de bas niveau qui sont un mappage 1:1 de L'API OpenCL d'origine

toutes ces bibliothèques ci-dessus aideront à implémenter Gaussian Blur plus rapidement que n'importe quelle implémentation en Java sur CPU.

j'ai vu plusieurs réponses dans différents endroits et je les collectionne ici pour que je puisse essayer d'enrouler mon esprit autour d'eux et me souvenir d'eux pour plus tard:

quelle que soit l'approche que vous utilisez, filtrer les dimensions horizontales et verticales séparément avec des filtres 1D plutôt qu'en utilisant un seul filtre carré.

• La norme "lent": filtre de convolution
• hiérarchique pyramide d'images à résolution réduite comme dans SIFT
• Répétited box blurs motivé par le théorème de la limite centrale. La boîte floue est au centre de la détection de visage de Viola et Jones où ils appellent une image intégrale si je me souviens bien. Je pense que les traits Haar-like utilisent quelque chose semblable, aussi.
• "1519140920 Pile" Flou : une file d'attente de remplacement de quelque part entre la convolution et la zone de flou approches
• filtres IIR
  • Derich filtre ( Wikipedia ) d'ordre 2 filtre IIR
  • van Vliet filtre je ne sais rien à ce sujet une
  • filtres de Bessel bien qu'il y a débat sur ces

après avoir passé en revue tout cela, je me souviens que des approximations simples et médiocres fonctionnent souvent bien dans la pratique. Dans un autre domaine, Alex Krizhevsky a trouvé que la fonction sigmoïde classique de ReLU était plus rapide dans son AlexNet révolutionnaire, même si elles semblent à première vue être une terrible approximation du sigmoïde.

Dave Hale de CWP a un paquet minejtk, qui comprend un filtre gaussien récursif (méthode Deriche et méthode Van Vliet). Le sous-programme java peut être trouvé à https://github.com/dhale/jtk/blob/0350c23f91256181d415ea7369dbd62855ac4460/core/src/main/java/edu/mines/jtk/dsp/RecursiveGaussianFilter.java

la méthode de Deriche semble être très bonne pour Gaussian blur (et aussi pour les dérivés de Gaussian).