web-gelistirme-sc.com

En hızlı Gauss bulanıklaştırma uygulaması

Mümkün olan en hızlı Gauss bulanıklığı algoritmasını nasıl uygularsınız?

Java ile uygulayacağım, bu yüzden GPU çözümleri ekarte edildi. Uygulamam, planetGenesis , çapraz platform, bu yüzden istemiyorum JNI .

javaimage-processingfilteringgaussian
32
Sid Datta

Bir Gauss çekirdeğinin ayrılabilir olduğu gerçeğini kullanmalısınız, i. e. 2B evrişimi iki 1B evrişimin bir kombinasyonu olarak ifade edebilirsiniz.

Eğer filtre büyükse, uzaysal alandaki evrişimin frekans (Fourier) alandaki çarpma ile aynı olduğu gerçeğini kullanmak mantıklı olabilir. Bu, görüntünün Fourier dönüşümünü ve filtre alabileceğiniz, (karmaşık) sonuçları çarpabileceğiniz ve ardından ters Fourier dönüşümünü alabileceğiniz anlamına gelir. FFT'nin (Hızlı Fourier Dönüşümü) karmaşıklığı O (n log n), bir evrişimin karmaşıklığı O (n ^ 2) 'dir. Ayrıca, aynı filtreyle birçok görüntüyü bulanıklaştırmanız gerekirse, filtrenin FFT'sini yalnızca bir kez çekmeniz gerekir.

Bir FFT kullanmaya karar verirseniz, FFTW kütüphanesi iyi bir seçimdir.

26
Dima

Matematiksel saldırılar bunu bilmesi muhtemeldir, fakat başkaları için ..

Gaussian'ın güzel bir matematiksel özelliği nedeniyle, önce resmin her satırında bir 1D Gauss bulanıklığı çalıştırarak hızlı bir şekilde 2D görüntüsünü bulanıklaştırabilir, ardından her sütun üzerinde 1D bulanıklaştırmayı çalıştırabilirsiniz. 

20
DarenW

  1. Buldum Quasimondo: İnkübatör: İşlem: Hızlı Gauss Bulanıklığı. Bu yöntem, tam sayıları kullanmak ve kayan nokta ve kayan nokta bölümleri yerine tabloları aramak gibi birçok yaklaşım içerir. Modern Java kodunda ne kadar hız olduğunu bilmiyorum.

  2. Dikdörtgenlerde Hızlı Gölgeler, B-splines kullanarak yaklaşık bir algoritmaya sahiptir. 

  3. C # 'daki Hızlı Gauss Bulanıklığı Algoritması bazı harika optimizasyonlara sahip olduğunu iddia ediyor.

  4. Ayrıca, Hızlı Gauss Bulanıklığı (PDF) David Everly tarafından Gauss bulanıklığı işleme için hızlı bir metoda sahiptir.

Çeşitli yöntemleri dener, kıyaslar ve sonuçları buraya yazardım.

Amaçlarım için, temel (X-Y eksenini bağımsız olarak işleme) yöntemini ve David Everly'nin Hızlı Gaussian Blur yöntemini İnternet'ten kopyaladım ve uyguladım. Parametrelerde farklılık gösterirler, bu yüzden onları doğrudan karşılaştıramadım. Bununla birlikte, ikincisi, büyük bir bulanıklık yarıçapı için çok daha az sayıda yinelemeden geçer. Ayrıca, ikincisi yaklaşık bir algoritmadır.

17
Sid Datta

ULTIMATE ÇÖZÜM

Çok fazla bilgi ve uygulama yüzünden kafam karıştı, hangisine güvenmem gerektiğini bilmiyordum. Bunu çözdükten sonra kendi makalemi yazmaya karar verdim. Umarım saatlerce zaman kazandıracaktır.

En Hızlı Gauss Bulanıklığı (doğrusal zamanda)

Kaynak kodunu içerir (umarım) kısa, temiz ve herhangi bir dile kolayca yazılabilir. Lütfen oy kullan, böylece başkaları görebilsin.

12
Ivan Kuckir

Muhtemelen daha hızlı olan kutu bulanıklığını istiyorsun. Harika bir öğretici ve kopyala & yapıştır C kodu için bu bağlantıya bakın.

8
Steve Hanov

Daha büyük bulanıklık yarıçapları için, bir kutu bulanıklığı üç kez uygulamayı deneyin. Bu Gauss bulanıklığını çok iyi yaklaştıracak ve gerçek Gauss bulanıklığından çok daha hızlı olacaktır.

7
Tom Sirgedas
  • 1. Adım: SIMD 1 boyutlu Gauss bulanıklığı
  • 2. Adım: devrik
  • 3. Adım: 1. adımı tekrarlayın

En iyi küçük bloklarda yapılır, tam görüntü devri yavaş olduğundan, küçük blok devresi PUNPCKs ( PUNPCKHBW, PUNPCKHDQ, PUNPCKHWD, PUNPCKLBW, PUNPCKLDQ, PUNPCKLWD ).

2
Dark Shikari

Araştırmam için bu sorunla mücadele ettim ve hızlı bir Gauss bulanıklığı için denenmiş ve ilginç bir yöntem. Öncelikle, belirtildiği gibi, bulanıklığı iki 1B bulanıklığa ayırmak en iyisidir, ancak donanım değerlerine gerçek hesaplanması için donanımınıza bağlı olarak, tüm olası değerleri önceden hesaplayabilir ve bunları bir arama tablosunda saklayabilirsiniz. 

Başka bir deyişle, Gaussian coefficient * input pixel value 'nin her bir kombinasyonunu önceden hesaplayın. Tabii ki katsayılarınızı gizli tutmanız gerekecek, ama ben sadece bu çözümü eklemek istedim. Bir IEEE aboneliğiniz varsa, daha fazla okuyabilirsinizGerçek görüntü özelliği çıkarımı için Arama Tablosunu kullanarak hızlı görüntü bulanıklığı. 

Sonuçta, CUDA olsa :) ile sona erdi :)

2
Ben McIntosh

Ivan Kuckir'in doğrusal geçiş bulanıklığı olan üç geçişi kullanan hızlı Gauss bulanıklığı uygulamasını Java'ya dönüştürdüm. Sonuçta ortaya çıkan süreç O(n) olduğu gibi kendi blogunda belirtti. 3 zamanlı kutu bulanıklığının Gauss bulanıklığına (% 3) neden yaklaştığı hakkında daha fazla bilgi edinmek istiyorsanız, arkadaşım kutu bulanıklığını ve Gauss bulanıklığını kontrol edebilirsiniz.

İşte Java uygulaması. 

@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

Özellikle daha büyük bir çekirdek kullanmak istiyorsanız, bunun için CUDA veya başka bir GPU programlama araç seti kullanmayı düşünürdüm. Bunu başaramazsan, Meclis'teki döngülerinde her zaman ince ayarlamalar vardır.

2
Dana the Sane

1D’de:

Neredeyse herhangi bir çekirdeği kullanarak art arda bulanıklaştırma Gauss çekirdeğine eğilimli olacaktır. Gauss dağılımı için bu kadar iyi olan şey budur ve istatistikçiler neden böyledir? Bu yüzden bulanıklığı kolay bir şey seçin ve birkaç kez uygulayın.

Örneğin, kutu şeklinde bir çekirdekli bulanıklaştırma yapmak kolaydır. İlk önce kümülatif bir toplamı hesaplayın:

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

sonra:

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

Birkaç kez tekrarlayın.

Veya bazı IIR filtresi çeşitleriyle birkaç kez ileri geri gidebilirsiniz, bunlar da aynı şekilde hızlıdır.

2D veya daha yüksek:

DarenW'in dediği gibi her boyutta birbiri ardına bulanıklık.

2
Paul Harrison

Box Blur'u burada yaptığım gibi kullanmayı deneyin: Genişletilmiş Box Blur Kullanarak Gauss Bulanıklığına Yaklaşım

Bu en iyi yaklaşımdır.

Integral Images kullanarak daha da hızlı hale getirebilirsiniz.
Yaparsanız, lütfen çözümünüzü paylaşın.

0
Royi

CWP'den Dave Hale, özyinelemeli Gaussian filtre (Deriche yöntemi ve Van Vliet yöntemi) içeren bir minejtk paketine sahip. Java altyordamı bulunabilir https://github.com/dhale/jtk/blob/0350c23f91256181d415ea7369dbd62855ac4460/core/src/main/Java/edu/mines/jtk/dsp/RecursiveGaussianFilter.Java

Deriche'nin metodu Gauss bulanıklığı için (ve aynı zamanda Gauss'un türevleri için) çok iyi görünüyor. 

0
Kai

Farklı yerlerde birkaç cevap gördüm ve bunları topladım, böylece aklımı etraflarına sarmaya ve daha sonra hatırlamaya çalışabiliyorum:

Hangi yaklaşımı kullanırsanız kullanın, yatay ve dikey ölçüleri ayrı ayrı filtreleyin tek bir kare filtre kullanmak yerine 1D filtrelerle.

  • Standart "yavaş" yaklaşım: evrişim filtresi
  • SIFT'deki gibi düşük çözünürlükte görüntülerin hiyerarşik piramidi
  • Merkezi Sınır Teoremi tarafından motive edilen tekrarlanan kutu bulanıklıkları. Box Blur, Viola ve Jones'un yüz tanıma merkezinde, doğru hatırlıyorsam, onu bütünleyici bir görüntü olarak adlandırıyor. Bence Haar benzeri özellikler de benzer bir şey kullanıyor.
  • Yığın Bulanıklığı : evrişimli ve kutu bulanıklaştırma yaklaşımları arasında bir yerde sıra tabanlı bir alternatif
  • IIR filtreleri

Bunların hepsini inceledikten sonra, basit, zayıf yaklaşımların çoğu zaman pratikte iyi çalıştığını hatırlatıyorum. Farklı bir alanda, Alex Krizhevsky, ilk bakışta Sigmoid'e korkunç bir yaklaşım gibi görünmelerine rağmen, ReLU'nun çığır açan AlexNet'teki klasik sigmoid fonksiyonundan daha hızlı olduğunu buldu.

0
Josiah Yoder

Bu eski soruyu şu anda uygulanmış olan yeni kütüphaneler ile yanıtlamak (2016'dan itibaren), çünkü GPU teknolojisinde Java ile ilgili birçok yeni gelişme vardır. 

Diğer birkaç cevapta önerildiği gibi, CUDA bir alternatiftir. Ama şimdi Java CUDA desteğine sahip şimdi. 

IBM CUDA4J kitaplığı: GPU cihazlarını, kitaplıklarını, çekirdeklerini ve belleğini yönetmek ve erişmek için bir Java API sağlar. Bu yeni API'leri kullanarak, GPU cihaz özelliklerini yöneten ve GPU'ya iş yükünü boşaltan Java programları, istisnalar ve otomatik kaynak yönetimi kolaylığı ile Java programları yazmak mümkündür.

Jcuda: NVIDIA CUDA ve ilgili kütüphaneler için Java ciltlemeleri. JCuda ile Java programlarından CUDA çalışma zamanı ve sürücü API'si ile etkileşime geçmek mümkündür.

Aparapi: Java geliştiricilerinin yerel CPU ile sınırlandırılmak yerine GPU'da veri paralel kod parçalarını çalıştırarak GPU ve APU cihazlarının bilgi işlem gücünden faydalanmalarını sağlar.

Bazı Java OpenCL bağlaması kütüphaneleri

https://github.com/ochafik/JavaCL : OpenCL için Java ciltleri: Otomatik olarak oluşturulan düşük düzeyli ciltlemelere dayanan nesne yönelimli bir OpenCL kütüphanesi

http://jogamp.org/jocl/www/ : OpenCL için Java ciltlemeleri: Otomatik üretilen düşük seviye ciltlemelere dayanan nesne yönelimli bir OpenCL kütüphanesi

http://www.lwjgl.org/ : OpenCL için Java ciltlemeleri: Otomatik üretilen düşük seviyeli ciltlemeler ve nesne yönelimli kolaylık sınıfları

http://jocl.org/ : OpenCL için Java ciltlemeleri: Orijinal OpenCL API'sinin 1: 1 eşlemesi olan düşük seviyeli ciltlemeler

Bu kitaplıkların tümü, Gauss Bulanıklığı'nın Java'daki CPU'daki herhangi bir uygulamadan daha hızlı uygulanmasına yardımcı olacaktır.

0
Tejus Prasad

2d verinin gauss bulanıklığı için birkaç hızlı yöntem vardır. Bilmeniz gerekenler.

  1. Bu ayrılabilir filtredir, bu nedenle sadece iki adet 1d evrişim gerektirir. 
  2. Büyük taneler için, azaltılmış görüntü kopyasını işleyebilir ve daha lüks hale getirebilirsiniz.
  3. İyi yaklaşım, birden fazla kutu filtresiyle (ayrıca ayrılabilir) yapılabilir ((yineleme sayısı ve çekirdek boyutları ayarlanabilir)
  4. IIR filtre ile hassas gauss yaklaşımı için O(n) karmaşıklık algoritması (herhangi bir çekirdek boyutu için) bulunur.

Seçiminiz gereken hız, hassasiyet ve uygulama karmaşıklığına bağlıdır. 

0
minorlogic