Самая быстрая реализация размытия по Гауссу - PullRequest
32 голосов
/ 19 сентября 2008

Как реализовать алгоритм максимально быстрого размытия по Гауссу ?

Я собираюсь реализовать его на Java, поэтому решения GPU исключены. Мое приложение, planetGenesis , является кроссплатформенным, поэтому я не хочу JNI .

Ответы [ 16 ]

26 голосов
/ 19 сентября 2008

Вы должны использовать тот факт, что ядро ​​Гаусса отделимо, т.е. е. Вы можете выразить двумерную свертку как комбинацию двух одномерных сверток.

Если фильтр большой, может также иметь смысл использовать тот факт, что свертка в пространственной области эквивалентна умножению в частотной (Фурье) области. Это означает, что вы можете взять преобразование Фурье изображения и фильтра, умножить (комплексные) результаты и затем выполнить обратное преобразование Фурье. Сложность БПФ (быстрого преобразования Фурье) составляет O (n log n), а сложность свертки - O (n ^ 2). Кроме того, если вам нужно размыть много изображений одним и тем же фильтром, вам потребуется только один раз взять БПФ фильтра.

Если вы решите использовать FFT, библиотека FFTW будет хорошим выбором.

20 голосов
/ 19 сентября 2008

Математические спортсмены, вероятно, знают это, но для кого-то еще ..

Благодаря хорошей математической характеристике гауссовского изображения вы можете быстро размыть 2D-изображение, сначала запустив 1-мерное размытие по Гауссу в каждой строке изображения, а затем запустив 1-мерное размытие в каждом столбце.

17 голосов
/ 20 сентября 2008
  1. Я нашел Квазимондо: Инкубатор: Обработка: быстрое размытие по Гауссу . Этот метод содержит множество приближений, таких как использование целых чисел и поиск таблиц вместо чисел с плавающей запятой и делений с плавающей запятой. Я не знаю, насколько это ускорение в современном Java-коде.

  2. Быстрые тени на прямоугольниках имеет алгоритм аппроксимации, использующий B-сплайны .

  3. Алгоритм быстрого размытия по Гауссу в C # утверждает, что имеет несколько классных оптимизаций.

  4. Также, Быстрое размытие по Гауссу (PDF) Дэвида Эверли имеет быстрый метод обработки размытия по Гауссу.

Я бы попробовал различные методы, протестировал их и выложил результаты здесь.

Для моих целей я скопировал и внедрил из Интернета базовый (независимо от оси X) процесс и метод Fast Gaussian Blur Дэвида Эверли. Они отличаются по параметрам, поэтому я не могу сравнить их напрямую. Однако последний проходит намного меньшее количество итераций для большого радиуса размытия. Также последний является приблизительным алгоритмом.

13 голосов
/ 22 августа 2013

окончательное решение

Я был очень смущен большим количеством информации и реализаций, я не знал, какой из них мне следует доверять. После того, как я понял это, я решил написать свою собственную статью. Надеюсь, это сэкономит вам часы времени.

Самое быстрое размытие по Гауссу (по линейному времени)

Он содержит исходный код, который (я надеюсь) короткий, чистый и легко перезаписывается на любой другой язык. Пожалуйста, проголосуйте, чтобы другие могли видеть это.

8 голосов
/ 19 сентября 2008

Возможно, вы хотите, чтобы окно размылось, что намного быстрее. См. эту ссылку , где вы найдете отличный учебник и немного кода для копирования и вставки C .

7 голосов
/ 12 февраля 2009

Для большего радиуса размытия попробуйте применить размытие окна три раза. Это очень хорошо будет приближаться к размытию по Гауссу и будет намного быстрее, чем настоящее размытие по Гауссу.

2 голосов
/ 09 июля 2016

Я преобразовал реализацию быстрого размытия по Гауссу от Ивана Кукира, которая использует три прохода с линейными прямоугольными размытиями, в 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;
        }
    }
}
2 голосов
/ 14 сентября 2010

Я боролся с этой проблемой в своих исследованиях и попробовал и интересный метод для быстрого размытия по Гауссу. Во-первых, как уже упоминалось, лучше всего разделить размытие на две 1D-размытия, но в зависимости от вашего оборудования для фактического расчета значений пикселей, вы можете предварительно рассчитать все возможные значения и сохранить их в справочной таблице.

Другими словами, предварительно рассчитайте каждую комбинацию Gaussian coefficient * input pixel value. Конечно, вам нужно будет дискретизировать ваши коэффициенты, но я просто хотел добавить это решение. Если у вас подписка IEEE , вы можете узнать больше в Быстрое размытие изображения с помощью таблицы поиска для извлечения объектов в реальном времени .

В конечном итоге я использовал CUDA , хотя:)

2 голосов
/ 04 сентября 2009

В 1D:

Размытие с использованием практически любого ядра неоднократно приведет к образованию гауссовского ядра. Это то, что так круто в распределении Гаусса, и именно поэтому статистикам это нравится. Так что выберите что-то, с чем легко размыть и примените это несколько раз.

Например, с помощью ядра в форме коробки легко размыть изображение. Сначала рассчитайте совокупную сумму:

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

, то:

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

Повторите несколько раз.

Или вы можете несколько раз переходить назад и вперед с каким-либо разнообразным фильтром IIR , они также быстры.

В 2D или выше:

Размытие в каждом измерении одно за другим, как сказал ДаренВ.

2 голосов
/ 19 сентября 2008
  • Шаг 1: SIMD 1-мерное размытие по Гауссу
  • Шаг 2: транспонировать
  • Шаг 3: повторите шаг 1

Лучше всего это делать на небольших блоках, так как транспонирование полного изображения происходит медленно, в то время как транспонирование небольших блоков может быть выполнено очень быстро с использованием цепочки PUNPCKs ( PUNPCKHBW, PUNPCKHDQ, PUNPCKHWD, PUNPCKLBW, PUNPCKLDQ, PUNPCKLWD ).

...