Оптимизированные варианты Float Blur

Question

Я ищу оптимизированные функции в C ++ для расчета средних площадных чисел с плавающей точкой. функции передаются исходный массив с плавающей точкой, целевой массив с плавающей точкой (такого же размера, что и исходный массив), ширина и высота массива, ширина и высота области «размытия».

Функция должна "обтекать" края для вычисления размытия / средних значений.

Вот пример кода, который размыт с прямоугольной формой:

/*****************************************
*   Find averages extended variations
*****************************************/

void findaverages_ext(float *floatdata, float *dest_data, int fwidth, int fheight, int scale, int aw, int ah, int weight, int xoff, int yoff)
{
printf("findaverages_ext scale: %d, width: %d, height: %d, weight: %d \n", scale, aw, ah, weight);

float total = 0.0;
int spos = scale * fwidth * fheight;
int apos;

int w = aw;
int h = ah;

float* f_temp       = new float[fwidth * fheight];

// Horizontal
for(int y=0;y<fheight   ;y++)
{
    Sleep(10);      // Do not burn your processor 

    total = 0.0;

    // Process entire window for first pixel (including wrap-around edge)
    for (int kx = 0; kx <= w; ++kx)
        if (kx >= 0 && kx < fwidth)
            total += floatdata[y*fwidth + kx];
    // Wrap
    for (int kx = (fwidth-w); kx < fwidth; ++kx)
        if (kx >= 0 && kx < fwidth)
            total += floatdata[y*fwidth + kx];

    // Store first window
    f_temp[y*fwidth] = (total / (w*2+1));

    for(int x=1;x<fwidth    ;x++)           // x width changes with y
    {
        // Substract pixel leaving window
        if (x-w-1 >= 0)
            total -= floatdata[y*fwidth + x-w-1];

        // Add pixel entering window
        if (x+w < fwidth)
            total += floatdata[y*fwidth + x+w];
        else
            total += floatdata[y*fwidth + x+w-fwidth];

        // Store average
        apos = y * fwidth + x;
        f_temp[apos] = (total / (w*2+1));
    }
}


// Vertical
for(int x=0;x<fwidth    ;x++)
{
    Sleep(10);      // Do not burn your processor 

    total = 0.0;

    // Process entire window for first pixel
    for (int ky = 0; ky <= h; ++ky)             
        if (ky >= 0 && ky < fheight)
            total += f_temp[ky*fwidth + x];
    // Wrap
    for (int ky = fheight-h; ky < fheight; ++ky)                
        if (ky >= 0 && ky < fheight)
            total += f_temp[ky*fwidth + x];

    // Store first if not out of bounds
    dest_data[spos + x] = (total / (h*2+1));

    for(int y=1;y< fheight  ;y++)           // y width changes with x
    {
        // Substract pixel leaving window
        if (y-h-1 >= 0)
            total -= f_temp[(y-h-1)*fwidth + x];

        // Add pixel entering window
        if (y+h < fheight)
            total += f_temp[(y+h)*fwidth + x];
        else
            total += f_temp[(y+h-fheight)*fwidth + x];

        // Store average
        apos = y * fwidth + x;
        dest_data[spos+apos] = (total / (h*2+1));
    }
}

delete f_temp;
}

Мне нужны аналогичные функции, которые для каждого пикселя находят среднее (размытие) пикселей от фигур, отличных от прямоугольных.

Конкретные формы: «S» (острые края), «O» (прямоугольный, но полый), «+» и «X», где среднее значение с плавающей запятой хранится в центральном пикселе массива данных назначения. Размер формы размытия должен быть переменным, ширина и высота.

Функции не обязательно должны быть пиксельными, только оптимизированы для производительности. Для каждой фигуры могут быть отдельные функции.

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

Answer 1

Чтобы добавить к ответу Sellibitze, вы можете использовать таблицу суммированных областей для ваших ядер O, S и + (но не для X). Таким образом, вы можете свертывать пиксель за постоянное время, и это, вероятно, самый быстрый способ сделать это для форм ядра, которые это позволяют.

По сути, SAT - это структура данных, которая позволяет вычислять сумму любого прямоугольника, ориентированного по оси. Для ядра O после того, как вы построили SAT, вы должны взять сумму пикселей внешнего прямоугольника и вычесть сумму пикселей внутреннего прямоугольника. Ядра S и + могут быть реализованы аналогично.

Для ядра X вы можете использовать другой подход. Перекошенный коробчатый фильтр является отделимым:

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

Кроме того, вы можете оптимизировать размытие окна разными способами.

• Удалите два if из внутреннего цикла, разделив этот цикл на три цикла - два коротких цикла, которые выполняют проверки, и один длинный цикл, который этого не делает. Или вы можете дополнить свой массив дополнительными элементами со всех сторон - таким образом вы можете упростить ваш код.
• Рассчитать такие значения, как h * 2 + 1 вне циклов.
• Выражение типа f_temp[ky*fwidth + x] делает два сложения и одно умножение. Вы можете инициализировать указатель на &f_temp[ky*fwidth] вне цикла и просто увеличивать этот указатель в цикле.
• Не делайте деление на h * 2 + 1 в горизонтальном шаге. Вместо этого разделите на квадрат этого шага по вертикали.

Answer 2

То, что вы пытаетесь реализовать, - это различные виды цифровых фильтров для обработки изображений.Это эквивалентно свертке двух сигналов, где 2-й сигнал будет импульсной характеристикой фильтра.До сих пор вы признавали, что «прямоугольное среднее» является отделяемым .Под отделяемым Я имею в виду, вы можете разделить фильтр на две части.Тот, который работает вдоль оси X, и тот, который работает вдоль оси Y - в каждом случае 1D фильтр.Это хорошо и может спасти вас много циклов.Но не каждый фильтр отделим .Усреднение по другим формам (S, O, +, X) неразделимо.Для этого вам нужно вычислить двумерную свертку.

Что касается производительности, вы можете ускорить свои 1D средние, правильно внедрив «скользящее среднее».Правильная реализация «скользящего среднего» требует только фиксированного количества небольшой работы на пиксель независимо от усредняющего «окна».Это может быть сделано путем распознавания того, что соседние пиксели целевого изображения вычисляются в среднем из почти одинаковых пикселей.Вы можете повторно использовать эти суммы для соседнего целевого пикселя, добавив одну новую интенсивность пикселя и вычтя более старую (для одномерного случая).

В случае произвольных неразделимых фильтров ваша лучшая ставка в отношении производительности равна "быстрая свертка "на основе FFT.Оформить заказ www.dspguide.com.Если я правильно помню, есть даже глава о том, как правильно выполнить «быструю свертку» с использованием алгоритма FFT.Хотя они объясняют это для одномерных сигналов, это также относится и к двумерным сигналам.Для изображений необходимо выполнить преобразования 2D-FFT / iFFT.