it-swarm-eu.dev

Nejrychlejší implementace Gaussova rozostření

Jak realizujete co nejrychlejší Gaussovské rozostření algoritmus?

Budu ji implementovat v Javě, takže GPU solutions jsou vyloučena. Moje aplikace, planetGenesis , je cross platform, takže nechci JNI .

32
Sid Datta

Měli byste použít skutečnost, že Gaussovo jádro je oddělitelné, i. E. můžete vyjádřit 2D konvoluci jako kombinaci dvou 1D konvolucí.

Pokud je filtr velký, může mít smysl použít skutečnost, že konvoluce v prostorové doméně je ekvivalentní násobení ve frekvenční (Fourierově) doméně. To znamená, že můžete vzít Fourierovu transformaci obrazu a filtru, vynásobit (složité) výsledky a pak převzít inverzní Fourierovu transformaci. Složitost FFT (Fast Fourierova transformace) je O (n log n), zatímco složitost konvoluce je O (n ^ 2). Také, pokud potřebujete rozmazat mnoho obrazů se stejným filtrem, stačí, abyste jednou převzali FFT filtru.

Pokud se rozhodnete použít FFT, je dobrou volbou knihovna FFTW .

26
Dima

Matematičtí atleti to pravděpodobně znají, ale pro kohokoli jiného.

Vzhledem k pěkné matematické vlastnosti Gaussova, můžete rychle rozmazat 2D obraz tak, že nejprve spustíte 1D Gaussovské rozostření na každém řádku obrazu a pak na každém sloupci spustíte 1D rozostření. 

20
DarenW

ULTIMATE SOLUTION

Byl jsem velmi zmaten tolika informacemi a implementacemi, nevěděl jsem, komu mám důvěřovat. Poté, co jsem na to přišel, jsem se rozhodl napsat svůj vlastní článek. Doufám, že vám to ušetří hodiny času.

Nejrychlejší Gaussovské rozostření (v lineárním čase)

Obsahuje zdrojový kód, který (doufám) je krátký, čistý a snadno přepisovatelný do jiného jazyka. Prosím, hlasujte, aby to ostatní mohli vidět.

12
Ivan Kuckir

Pravděpodobně budete chtít krabici rozmazat, což je mnohem rychlejší. Viz tento odkaz pro skvělý návod a některé kopírovat a vložit C kód .

8
Steve Hanov

U větších poloměrů rozostření zkuste třikrát použít rozostření boxu . To bude velmi dobře aproximovat Gaussovo rozostření a bude mnohem rychlejší než skutečné Gaussovské rozostření.

7
Tom Sirgedas
  • Krok 1: SIMD 1-rozměrné Gaussovo rozostření
  • Krok 2: provedení
  • Krok 3: Opakujte krok 1

Nejlépe se provádí na malých blocích, protože transponování v plném obraze je pomalé, zatímco malá bloková transpozice může být provedena velmi rychle pomocí řetězce PUNPCK ( PUNPCKHBW, PUNPCKHDQ, PUNPCKHWD, PUNPCKLBW, PUNPCKLDQ, PUNPCKLWD ).

2
Dark Shikari

S tímto problémem jsem se potýkal pro svůj výzkum a vyzkoušel zajímavou metodu pro rychlé Gaussovské rozostření. Za prvé, jak bylo zmíněno, je nejlepší oddělit rozostření na dvě rozostření 1D, ale v závislosti na vašem hardwaru pro skutečný výpočet hodnot pixelů, můžete skutečně předem spočítat všechny možné hodnoty a uložit je do vyhledávací tabulky. 

Jinými slovy, předpočítejte každou kombinaci Gaussian coefficient * input pixel value. Samozřejmě budete muset své koeficienty diskrétizovat, ale chtěl jsem jen přidat toto řešení. Pokud máte IEEE subscription, můžete si přečíst více v Rychlé rozmazání obrazu pomocí vyhledávací tabulky pro extrakci funkcí v reálném čase

Nakonec jsem skončil s použitím CUDA ačkoli :)

2
Ben McIntosh

Převedl jsem Ivan Kuckir na implementaci rychlého Gaussova rozostření, které využívá tři průchody s lineárním rozostřením do Java. Výsledný proces je O(n), jak uvedl na svém vlastním blogu . Pokud byste se chtěli dozvědět více o tom, proč se 3 časové pole rozostření přibližuje Gaussovskému rozostření (3%), můj přítel si můžete vyzkoušet box rozostření a Gaussovské rozostření .

Zde je implementace 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;
        }
    }
}
2
Ali Akdurak

Chtěl bych zvážit použití CUDA nebo nějaké jiné programovací sady pro GPU programování, zejména pokud chcete použít větší jádro. Pokud tomu tak není, vždycky máte ruce, které vám v Shromáždění upravují smyčky.

2
Dana the Sane

V 1D:

Rozmazání používající téměř libovolné jádro bude mít tendenci k Gaussovu jádru. To je to, co je na Gaussově rozložení tak cool, a proto se to líbí statistikům. Vyberte si tedy něco, co je snadné rozmazat a několikrát aplikovat.

Například je snadné rozmazat jádro ve tvaru krabice. Nejprve spočítejte souhrnnou částku:

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

pak:

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

Opakujte několikrát.

Nebo se můžete několikrát vrátit sem a tam s různými filtry IIR /, ty jsou podobně rychlé.

Ve 2D nebo vyšší:

Rozmazání v každé dimenzi jeden po druhém, jak řekl DarenW.

2
Paul Harrison

Zkuste použít Rozmáznutí boxu tak, jak jsem to udělal zde: Přibližné Gaussovské rozostření pomocí rozšířeného rámečku Blur

To je nejlepší aproximace.

Pomocí integrálních snímků můžete provést ještě rychlejší práci.
Pokud ano, podělte se o své řešení.

0
Royi

Dave Hale z CWP má balíček minejtk, který zahrnuje rekurzivní Gaussův filtr (metoda Deriche a Van Vlietova metoda). Podprogram Java najdete na adrese https://github.com/dhale/jtk/blob/0350c23f91256181d415ea7369dbd62855ac4460/core/src/main/Java/edu/mines/jtk/dsp/RecursiveGaussianFilter.Java

Dericheova metoda se jeví jako velmi dobrá pro Gaussovské rozostření (a také pro Gaussovy deriváty). 

0
Kai

Viděl jsem několik odpovědí na různých místech a shromažďuji je zde, abych se mohl pokusit zabalit svou mysl kolem nich a zapamatovat si je pro pozdější dobu:

Bez ohledu na to, jaký přístup používáte, filtrujte vodorovné a svislé rozměry odděleně s 1D filtry, a nikoli pomocí jediného čtvercového filtru.

  • Standardní "pomalý" přístup: konvoluční filtr
  • Hierarchická pyramida obrazů se sníženým rozlišením jako u SIFT
  • Opakované boxové rozostření motivované teorémem centrálního limitu. Box Blur je ústředním bodem detekce obličejů Violy a Jonesa, kde to nazývají integrálním obrazem, pokud si vzpomínám správně. Myslím si, že funkce podobné Haaru používají i něco podobného.
  • Stack Blur : alternativa založená na frontě někde mezi konvolučními a boxovými rozostřovacími přístupy
  • IIR filtry

Po přečtení všech těchto informací jsem upozorněn, že jednoduché, špatné přiblížení často v praxi funguje dobře. V jiném oboru Alex Krizhevsky zjistil, že ReLU je rychlejší než klasická sigmoidní funkce v jeho průlomovém AlexNet, i když se na první pohled jeví jako hrozná aproximace k Sigmoidu.

0
Josiah Yoder

Odpověď na tuto starou otázku s nové knihovny, která byla implementována nyní (od roku 2016), protože existuje mnoho nových vylepšení technologie GPU s jazykem Java. 

Jak bylo naznačeno v několika dalších odpovědích, CUDA je alternativou. Ale Java má podporu CUDA nyní. 

Knihovna IBM CUDA4J: poskytuje rozhraní Java API pro správu a přístup k zařízením GPU, knihovnám, jádrům a paměti. Pomocí těchto nových rozhraní API je možné psát Java programy, které spravují vlastnosti zařízení GPU a práci s výstupem do GPU s pohodlím modelu paměti Java, výjimek a automatické správy prostředků.

Jcuda: Java vazby pro NVIDIA CUDA a příbuzné knihovny. S JCuda je možné komunikovat s CUDA runtime a ovladačem API z Java programů.

Aparapi: umožňuje vývojářům v Javě využít výpočetní výkon zařízení GPU a APU prováděním fragmentů paralelního kódu dat na GPU, nikoli omezením na lokální procesor.

Některé Java OpenCL vázání knihovny

https://github.com/ochafik/JavaCL : Java vazby pro OpenCL: Objektově orientovaná OpenCL knihovna založená na automaticky generovaných nízkoúrovňových vazbách

http://jogamp.org/jocl/www/ : Java vazby pro OpenCL: Objektově orientovaná OpenCL knihovna založená na automaticky generovaných nízkoúrovňových vazbách

http://www.lwjgl.org/ : Java vazby pro OpenCL: Automatické generování nízkoúrovňových vazeb a objektově orientovaných tříd pohodlí

http://jocl.org/ : Java vazby pro OpenCL: Nízkoúrovňové vazby, které jsou mapováním 1: 1 původního OpenCL API

Všechny tyto výše uvedené knihovny pomohou při implementaci Gaussova rozostření rychleji než jakákoliv implementace v Javě na CPU.

0
Tejus Prasad

Existuje několik rychlých metod pro gaussovské rozostření 2d dat. Co byste měli vědět.

  1. To je oddělitelný filtr, takže vyžadují pouze dvě konvoluce 1d. 
  2. Pro velká jádra můžete zpracovat zmenšenou kopii obrazu a pak přepnout zpět.
  3. Dobrá aproximace může být provedena pomocí více boxových filtrů (také oddělitelných), (může být vyladěn počet iterací a velikostí jádra)
  4. Exist O(n) algoritmus složitosti (pro libovolnou velikost jádra) pro precizní aproximaci gaussu IIR filtrem.

Vaše volba závisí na požadované rychlosti, přesnosti a složitosti implementace. 

0
minorlogic