39

可能な限り最速のガウスぼかしアルゴリズムをどのように実装しますか？

Javaで実装するので、GPUソリューションは除外されます。私のアプリケーションplanetGenesisはクロスプラットフォームなので、 JNIは必要ありません。

4

16 に答える 16

33

ガウスカーネルが分離可能であるという事実を使用する必要があります。つまり、2D畳み込みを2つの1D畳み込みの組み合わせとして表現できます。

フィルタが大きい場合は、空間領域での畳み込みが周波数（フーリエ）領域での乗算と同等であるという事実を使用することも理にかなっています。これは、画像とフィルターのフーリエ変換を実行し、（複雑な）結果を乗算してから、逆フーリエ変換を実行できることを意味します。FFT（高速フーリエ変換）の複雑さはO（n log n）ですが、畳み込みの複雑さはO（n ^ 2）です。また、同じフィルターで多くの画像をぼかす必要がある場合は、フィルターのFFTを1回だけ取得する必要があります。

FFTを使用する場合は、FFTWライブラリが適しています。

于 2008-09-19T14:31:31.763 に答える
28

数学のジョークはこれを知っている可能性が高いですが、他の人にとっては..

ガウスの優れた数学的特性により、最初に画像の各行で 1D ガウスぼかしを実行し、次に各列で 1D ぼかしを実行することにより、2D 画像をすばやくぼかします。

于 2008-09-19T01:58:05.297 に答える
23

究極のソリューション

私は非常に多くの情報と実装に非常に混乱し、どれを信頼すべきかわかりませんでした。それを理解した後、私は自分の記事を書くことにしました。何時間もの時間を節約できることを願っています。

最速のガウスぼかし (線形時間)

これにはソースコードが含まれています。これは (私が望む) 短く、クリーンで、他の言語に簡単に書き直すことができます。他の人が見ることができるように、投票してください。

于 2013-08-22T08:40:47.530 に答える
17

  1. Quasimondo : Incubator : Processing : Fast Gaussian Blurを見つけました。このメソッドには、浮動小数点数や浮動小数点除算の代わりに整数やルックアップ テーブルを使用するなど、多くの近似が含まれています。最新の Java コードでどれだけ高速化されているかはわかりません。

  2. 長方形の高速シャドウには、 B-スプラインを使用した近似アルゴリズムがあります。

  3. C# の Fast Gaussian Blur Algorithm は、いくつかの優れた最適化があると主張しています。

  4. また、David Everly によるFast Gaussian Blur (PDF) には、ガウスぼかし処理の高速な方法があります。

さまざまな方法を試し、それらをベンチマークし、結果をここに投稿します。

私の目的のために、インターネットから基本的な (XY 軸を個別に処理する) メソッドと David Everly のFast Gaussian Blurメソッドをコピーして実装しました。パラメータが違うので直接比較はできません。ただし、後者は、ぼかし半径が大きい場合、反復回数がはるかに少なくなります。また、後者は近似アルゴリズムです。

于 2008-09-19T21:18:09.633 に答える
8

あなたはおそらくボックスブラーが欲しいでしょう、それははるかに速いです。優れたチュートリアルとCコードのコピー＆ペーストについては、このリンクを参照してください。

于 2008-09-19T00:38:21.043 に答える
7

ぼかしの半径を大きくするには、ボックスぼかしを3 回適用してみてください。これは、ガウスぼかしを非常によく近似し、真のガウスぼかしよりもはるかに高速です。

于 2009-02-11T22:22:40.290 に答える
3

私は Ivan Kuckir の高速ガウス ブラーの実装を Java に変換しました。彼が自身のブログで述べているように、結果として得られるプロセスは O(n)です。3 タイム ボックス ブラーがガウス ブラー (3%) に近似する理由について詳しく知りたい場合は、ボックス ブラーとガウス ブラーを参照してください。

これが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;
        }
    }
}
于 2016-07-09T18:47:59.753 に答える
2

特に大きなカーネルを使用したい場合は、このためにCUDAまたは他のGPUプログラミングツールキットを使用することを検討します。それができない場合は、アセンブリでループを手動で微調整する必要があります。

于 2008-09-19T00:44:45.020 に答える
2

私は自分の研究のためにこの問題に苦労し、高速ガウスぼかしのための興味深い方法を試しました。まず、前述のように、ブラーを2つの1Dブラーに分割するのが最善ですが、ピクセル値を実際に計算するハードウェアによっては、可能なすべての値を実際に事前計算して、ルックアップテーブルに保存できます。

Gaussian coefficientつまり、 *のすべての組み合わせを事前に計算しますinput pixel value。もちろん、係数を慎重にする必要がありますが、私はこのソリューションを追加したかっただけです。IEEEサブスクリプションをお持ちの場合は、ルックアップテーブルを使用してリアルタイムの特徴抽出を行う高速画像ブラーで詳細を読むことができます。

最終的に、私はCUDAを使用することになりました:)

于 2010-09-14T19:06:04.110 に答える
2
  • ステップ 1: SIMD 1 次元ガウスぼかし
  • ステップ 2: 移調
  • ステップ 3: ステップ 1 を繰り返す

フルイメージの転置は遅いため、小さなブロックで行うのが最適ですが、小さなブロックの転置は PUNPCK のチェーン ( PUNPCKHBW、PUNPCKHDQ、PUNPCKHWD、PUNPCKLBW、PUNPCKLDQ、PUNPCKLWD ) を使用して非常に高速に実行できます。

于 2008-09-19T02:03:20.713 に答える
2

1D で:

ほぼすべてのカーネルを繰り返し使用してぼかしを行うと、ガウス カーネルになる傾向があります。これがガウス分布の優れた点であり、統計学者が好む理由です。ぼかしやすいものを選んで、何回も重ね塗りしてください。

例えば、箱型のカーネルでぼかすのは簡単です。最初に累積合計を計算します。

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

それから：

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

数回繰り返します。

または、さまざまなIIRフィルターを使用して数回行ったり来たりすることもできますが、これらは同様に高速です。

2D 以上の場合:

DarenWが言ったように、各次元で次々にぼかします。

于 2009-09-04T03:01:41.863 に答える
1

私はさまざまな場所でいくつかの回答を見てきましたが、ここにそれらを集めて、それらをまとめて後で覚えておくことができるようにします。

使用するアプローチに関係なく、単一の正方形フィルターを使用するのではなく、1D フィルターを使用して水平方向と垂直方向の寸法を別々にフィルター処理します。

  • 標準的な「遅い」アプローチ: 畳み込みフィルター
  • SIFT のように解像度を下げた画像の階層ピラミッド
  • 中心極限定理によって動機付けられた反復ボックス ブラー。Box Blur は、私の記憶が正しければ、Viola と Jones の顔検出の中心であり、積分画像と呼ばれています。Haar のような機能も同様のものを使用していると思います。
  • Stack Blur : 畳み込みアプローチとボックス ブラー アプローチの間のキューベースの代替手段
  • IIR フィルター

これらすべてを見直した後、単純で貧弱な近似が実際にはうまく機能することが多いことを思い出しました。別の分野では、Alex Krizhevsky は ReLU が彼の画期的な AlexNet の古典的なシグモイド関数よりも高速であることを発見しました。

于 2018-02-19T14:38:12.667 に答える
0

2D データのガウス ブラーには、いくつかの高速な方法があります。あなたが知っておくべきこと。

  1. これは分離可能なフィルターであるため、2 つの 1d 畳み込みのみが必要です。
  2. 大きなカーネルの場合、イメージの縮小コピーを処理して、アップスケール バックよりも処理できます。
  3. 適切な近似は、複数のボックス フィルター (分離可能) によって行うことができます (反復回数とカーネル サイズを調整できます)。
  4. IIR フィルターによる正確なガウス近似のための O(n) 複雑度アルゴリズム (任意のカーネル サイズ) が存在します。

選択は、必要な速度、精度、および実装の複雑さに依存します。

于 2014-03-10T10:49:40.033 に答える
0

ここで行った方法で Box Blur を使用してみてください: 拡張 Box Blur を使用したガウスぼかしの近似

これが最良の概算です。

Integral Images を使用すると、さらに高速化できます。
もしそうなら、あなたの解決策を共有してください。

于 2014-05-24T07:53:19.460 に答える
0

Java を使用した GPU テクノロジには多くの新しい進歩があるため、現在 (2016 年現在) 実装されている新しいライブラリでこの古い質問に答えます。

他のいくつかの回答で示唆されているように、CUDA は代替手段です。しかし、Java は現在 CUDA をサポートしています。

IBM CUDA4J ライブラリー: GPU デバイス、ライブラリー、カーネル、およびメモリーを管理およびアクセスするための Java API を提供します。これらの新しい API を使用すると、GPU デバイスの特性を管理し、Java メモリ モデル、例外、および自動リソース管理の利便性を利用して作業を GPU にオフロードする Java プログラムを作成できます。

Jcuda: NVIDIA CUDA および関連ライブラリの Java バインディング。JCuda を使用すると、Java プログラムから CUDA ランタイムおよびドライバー API を操作できます。

Aparapi: Java 開発者は、ローカル CPU に限定されるのではなく、GPU でデータ並列コード フラグメントを実行することにより、GPU および APU デバイスの計算能力を活用できます。

一部のJava OpenCL バインディングライブラリ

https://github.com/ochafik/JavaCL : OpenCL の Java バインディング: 自動生成された低レベルのバインディングに基づく、オブジェクト指向の OpenCL ライブラリ

http://jogamp.org/jocl/www/ : OpenCL の Java バインディング: 自動生成された低レベルのバインディングに基づく、オブジェクト指向の OpenCL ライブラリ

http://www.lwjgl.org/ : OpenCL の Java バインディング: 自動生成された低レベルのバインディングとオブジェクト指向の便利なクラス

http://jocl.org/ : OpenCL の Java バインディング: 元の OpenCL API の 1:1 マッピングである低レベルのバインディング

上記のライブラリはすべて、CPU 上の Java でのどの実装よりも高速に Gaussian Blur を実装するのに役立ちます。

于 2016-06-23T10:50:18.397 に答える