Быстрая реализация гауссовского размытия

Как вы реализуете алгоритм быстрого Gaussian blur?

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

Ответ 1

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

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

Если вы решите использовать БПФ,

Ответ 2

Math jocks, вероятно, знают это, но для кого-то еще.

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

Ответ 3

Я нашел Quasimondo: инкубатор: обработка: быстрое размытие Gaussian. Этот метод содержит множество приближений, таких как использование целых чисел и поиск таблиц вместо float и делений с плавающей запятой. Я не знаю, сколько ускорений в современном Java-коде.
Fast Shadows on Rectangles имеет аппроксимирующий алгоритм с использованием B -сплайны.
Алгоритм быстрого гауссовского размытия в С# утверждает, что имеет некоторые крутые оптимизации.
Кроме того, Быстрое гауссовское размытие (PDF) Дэвида Эверли имеет быстрый метод для размытия Gaussian.

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

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

Ответ 4

ULTIMATE SOLUTION

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

Быстрое гауссовское размытие (в линейном времени)

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

Ответ 5

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

Ответ 6

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

Ответ 7

Я хотел бы использовать CUDA или какой-либо другой инструментарий для программирования GPU, особенно если вы хотите использовать большее ядро. В противном случае всегда необходимо настроить ваши петли в сборке.

Ответ 8

Шаг 1: одномерное гауссовское размытие SIMD
Шаг 2: транспонирование
Шаг 3: Повторите шаг 1

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

Ответ 9

В 1D:

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

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

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

то

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

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

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

В 2D или выше:

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

Ответ 10

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

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

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

Ответ 11

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

Ответ 12

Существует несколько быстрых методов для размытия gauss 2d-данных. О чем вы должны знать.

Это разделимый фильтр, поэтому требуется только одна 1-я свертка.
Для больших ядер вы можете обрабатывать уменьшенную копию изображения, а не назад.
Хорошее приближение может быть выполнено с помощью нескольких фильтров ящиков (также разделенных) (может быть настроено количество итераций и размеры ядра)
Алгоритм сложности Exist O (n) (для любого размера ядра) для точной гауссовой аппроксимации с помощью фильтра IIR.

Ваш выбор зависит от требуемой скорости, точности и сложности реализации.

Ответ 13

Попробуйте использовать Box Blur так, как я сделал здесь: Аппроксимация гауссовского размытия с использованием расширенного размытия ящиков

Это наилучшее приближение.

Используя встроенные изображения, вы можете сделать это еще быстрее.
Если вы это сделаете, поделитесь своим решением.

Ответ 14

Отвечая на этот старый вопрос с новыми библиотеками, которые были реализованы в настоящее время (начиная с 2016 года), потому что есть много новых улучшений для технологии GPU с Java.

Как было предложено в нескольких других ответах, CUDA является альтернативой. Но java теперь поддерживает CUDA.

Библиотека IBM CUDA4J: предоставляет Java API для управления и доступа к устройствам, библиотекам, ядрам и памяти GPU. Используя эти новые API-интерфейсы, можно написать Java-программы, которые управляют характеристиками устройства GPU и нагрузкой на GPU, с удобством модели памяти Java, исключениями и автоматическим управлением ресурсами.

Jcuda: привязки Java для NVIDIA CUDA и связанных библиотек. С JCuda можно взаимодействовать с API-интерфейсом CUDA и API-интерфейсом драйвера из программ Java.

Aparapi: позволяет разработчикам Java использовать вычислительную мощность устройств GPU и APU, выполняя фрагменты данных параллельного кода на графическом процессоре, а не ограничиваясь локальным процессором.

Некоторые библиотеки Java OpenCL

https://github.com/ochafik/JavaCL: привязки Java для OpenCL: объектно-ориентированная библиотека OpenCL на основе автоматически сгенерированных привязок низкого уровня

http://jogamp.org/jocl/www/: привязки Java для OpenCL: объектно-ориентированная библиотека OpenCL на основе автоматических низкоуровневых привязок

http://www.lwjgl.org/: привязки Java для OpenCL: автоматические низкоуровневые привязки и объектно-ориентированные классы удобства

http://jocl.org/: привязки Java для OpenCL: привязки низкого уровня, которые являются сопоставлением 1:1 исходного OpenCL API

Все перечисленные выше библиотеки помогут реализовать Gaussian Blur быстрее, чем любая реализация в Java на процессоре.

Ответ 15

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

Независимо от того, какой подход вы используете, фильтруйте горизонтальные и вертикальные размеры отдельно с 1D-фильтрами, а не с использованием одного квадратного фильтра.

Стандартный "медленный" подход: фильтр свертки
Иерархическая пирамида изображений с уменьшенным разрешением, как в SIFT
Повторяющиеся ящики, мотивированные Центральной предельной теоремой. Box Blur занимает центральное место в обнаружении лица Виолы и Джонса, где они называют это интегральным изображением, если я правильно помню. Я думаю, что функции, подобные Хаару, тоже используют нечто подобное.
Stack Blur: альтернатива на основе очереди где-то между сверточными и размытыми рамками
Фильтры IIR
- Фильтр Дериха (Wikipedia) Второй фильтр IIR
- фильтр van Vliet Я ничего не знаю об этом
- Бесселевые фильтры, хотя есть некоторые дебаты об этих

После рассмотрения всех этих вопросов мне напомнили, что простые, плохие аппроксимации часто хорошо работают на практике. В другой области Алекс Крижевский нашел, что ReLU будет быстрее классической сигмоидной функции в его новаторской AlexNet, хотя они на первый взгляд кажутся ужасным приближением к Sigmoid.