Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Оптимизация обработки изображений на C с применением SIMD. Медианный фильтр

Anna | 24.06.2014 | нет комментариев

Ранее во вступительной статье я поднимал список задач, с которыми придется столкнуться разработчику, если он захочет оптимизировать оптимизацию обработки изображения при помощи SIMD инструкций. Сейчас пришло время на определенном примере показать, как указанные выше задачи дозволено решить. Я длинно думал, какой алгорифм предпочесть для первого примера, и решил остановиться на медианной фильтрации. Медианная фильтрация является результативным методом подавления шумов, которые неминуемо возникают на цифровых камерах в условиях малого освещения сцены. Алгорифм данный довольно ресурсоемок – так скажем, при обработке серого изображения медианным фильтром 3х3 требуется порядка 50 операций на одну точку изображения. Но в тоже время он оперирует только с 8-битными числами и ему для работы требуется относительно не много входных данных. Эти обстоятельства делают алгорифм довольно простым для SIMD оптимизации и в тоже время разрешают получить из нее крайне значительное убыстрение.

image

Для справки напоминаю суть алгорифма:

  • Для всякой точки начального изображения берется некоторая окрестность (в нашем случае 3×3).
  • Точки данной окрестности сортируются по возрастанию яркости.
  • Средняя точка (5-я для фильтра 3х3) отсортированной окрестности записывается в итоговое изображение.

Для первого примера, я решил упростить задачу и разглядеть случай серого изображения (8 бит на точку) без учета граничных результатов — для этого для фильтрации бралась центральная часть несколько большего изображения. Безусловно, в реальных задачах граничные точки изображения следует рассчитывать по специальному алгорифму, и порой реализация этих специальных алгорифмов может занимать огромную часть кода, но мы остановимся на этих вопросах в иной раз. Помимо того, по аналогичным причинам предполагается, что ширина изображения кратна 32.

Скалярные версии алгорифма

1-я скалярная версия

В этой исходной реализации задача была решена в лоб: окрестность для всякой точки начального изображения копировалась во вспомогательный массив, тот, что после этого сортировался при помощи функции std::sort().

inline void Load(const uint8_t * src, int a[3])
{
    a[0] = src[-1];         
    a[1] = src[0];              
    a[2] = src[1];
}

inline void Load(const uint8_t * src, size_t stride, int a[9])
{
    Load(src - stride, a   0);
    Load(src, a   3);
    Load(src   stride, a   6);
}

inline void Sort(int a[9])
{
    std::sort(a, a   9);
}

void MedianFilter(const uint8_t * src, size_t srcStride, size_t width, size_t height, uint8_t * dst, size_t dstStride)
{
    int a[9];
    for(size_t y = 0; y < height;   y)
    {
        for(size_t x = 0; x < width;   x)
        {
            Load(src   x, srcStride, a);
            Sort(a);
            dst[x] = (uint8_t)a[4];
        }
        src  = srcStride;
        dst  = dstStride; 
    }
}
2-я скалярная версия

У предыдущего способа, однако, сразу видно тесное место – это стандартная функции сортировки. Она предуготовлена для сортировки массива произвольного размера, в ней осуществляется уйма внутренних проверок, следственно она, скорее каждого, не будет оптимальным решением для данной задачи, где массив мал и имеет фиксированный размер. Помимо того, нам вовсе не непременно всецело сортировать массив, довольно, что бы в 4-м элементе было требуемое нами значение. Потому мы можем применить способ сортировки «сетью» (так же знаменит, как способ битонической сортировки):

inline void Sort(int & a, int & b) // сортирует пару чисел
{
    if(a > b)
    {
        int t = a;
        a = b;
        b = t;
    }
}

inline void Sort(int a[9]) //частично сортирует каждый массив
{
    Sort(a[1], a[2]); Sort(a[4], a[5]); Sort(a[7], a[8]); 
    Sort(a[0], a[1]); Sort(a[3], a[4]); Sort(a[6], a[7]);
    Sort(a[1], a[2]); Sort(a[4], a[5]); Sort(a[7], a[8]); 
    Sort(a[0], a[3]); Sort(a[5], a[8]); Sort(a[4], a[7]);
    Sort(a[3], a[6]); Sort(a[1], a[4]); Sort(a[2], a[5]); 
    Sort(a[4], a[7]); Sort(a[4], a[2]); Sort(a[6], a[4]);
    Sort(a[4], a[2]);
}
3-я скалярная версия

Правда 1-й способ и получился гораздо стремительней нулевого (см. итог тестирования ниже), но у него осталось одно тесное место – в этом способе дюже много условных переходов. Как вестимо, совремk!} void MedianFilter(const uint8_t * src, size_t srcStride, size_t width, size_t height, uint8_t * dst, size_t dstStride) { __m128i a[9]; for(size_t y = 0; y < height; y) { for(size_t x = 0; x < width; x = sizeof(__m128i)) { Load(src x, srcStride, a); Sort(a); _mm_storeu_si128((__m128i*)(dst x), a[4]); //сохранение 128 битного вектора по невыровненному по 16 битной границе адресу } src = srcStride; dst = dstStride; } }

AVX2 версия

Целочисленные команды AVX2 определены в заголовочном файле < immintrin.h >. В качестве базового типа выступает __m256i — 256 битный вектор, тот, что в зависимости от контекста может интерпретироваться как комплект 4-х 64 битных, 8-х 32 битных, 16-х 16 битных, 32-х 8 битных знаковых либо беззнаковых чисел. Правда комплект инструкций AVX2 во многом повторяет комплект инструкций SSE2 (с учетом удвоившейся ширины вектора), но он также содержит и довольно много инструкций, у которых нет аналогов в SSE2. Ниже приведена оптимизация медианного фильтра при помощи AVX2 инструкций.

#include < immintrin.h >

inline void Load(const uint8_t * src, __m256i a[3])
{
    a[0] = _mm256_loadu_si256((__m128i*)(src - 1)); //загрузка 256 битного вектора по невыровненному по 32 битной границе адресу
    a[1] = _mm256_loadu_si256((__m128i*)(src));
    a[2] = _mm256_loadu_si256((__m128i*)(src   1));
}

inline void Load(const uint8_t * src, size_t stride, __m256i a[9])
{
    Load(src - stride, a   0);
    Load(src, a   3);
    Load(src   stride, a   6);
}

inline void Sort(__m256i& a, __m256i& b)
{
    __m256i t = a;
    a = _mm256_min_epu8(t, b); //нахождение минимума 2-х 8 битных беззнаковых чисел для всякого из 32 значений вектора
    b = _mm256_max_epu8(t, b); //нахождение максимума 2-х 8 битных беззнаковых чисел для всякого из 32 значений вектора
}

inline void Sort(__m256i a[9]) //частично сортирует каждый массив
{
    Sort(a[1], a[2]); Sort(a[4], a[5]); Sort(a[7], a[8]); 
    Sort(a[0], a[1]); Sort(a[3], a[4]); Sort(a[6], a[7]);
    Sort(a[1], a[2]); Sort(a[4], a[5]); Sort(a[7], a[8]); 
    Sort(a[0], a[3]); Sort(a[5], a[8]); Sort(a[4], a[7]);
    Sort(a[3], a[6]); Sort(a[1], a[4]); Sort(a[2], a[5]); 
    Sort(a[4], a[7]); Sort(a[4], a[2]); Sort(a[6], a[4]);
    Sort(a[4], a[2]);
}

void MedianFilter(const uint8_t * src, size_t srcStride, size_t width, size_t height, uint8_t * dst, size_t dstStride)
{
    __m256i a[9];
    for(size_t y = 0; y < height;   y)
    {
        for(size_t x = 0; x < width;  x  = sizeof(__m256i))
        {
            Load(src   x, srcStride, a);
            Sort(a);
            _mm256_storeu_si256((__m256i*)(dst   x), a[4]); //сохранение 256 битного вектора по невыровненному по 32 битной границе адресу
        }
        src  = srcStride;
        dst  = dstStride; 
    }
}

Примечание: Для приобретения максимального убыстрения от оптимизации код, тот, что содержит AVX2 инструкции, должен быть собран с следующими опцией компилятора: (/arch:AVX для Visual Studio 2012, -march=core-avx2 для GCC). Помимо того, дюже желанно, Дабы в коде не было чередования AVX2 и SSE2 инструкций, так как переключение режима работы процессора в этом случае будет негативно сказывается на всеобщей продуктивности. Исходя из выше сказанного, уместно располагать AVX2 и SSE2 версии алгорифмов в различных “.cpp” файлах.

Тестирование

Тестирование производилось на серых изображениях размером 2 MB (1920 x 1080). Для возрастания точности измерения времени, тесты прогонялись несколько раз. Время выполнения получали делением всеобщего времени исполнения тестов на число прогонов. число прогонов выбиралось таким образом, что всеобщее время исполнения было не поменьше 1 секунды, что должно обеспечить два знака точности при измерении времени исполнения алгорифмов. Алгорифмы были скомпилированы с максимальной оптимизацией под 64 bit Windows 7 на Microsoft Visual Studio 2012 и запущены на процессоре iCore-7 4770 (3.4 GHz).

Время выполнения, мс Относительное убыстрение
Наилучший скалярный SSE2 AVX2 Наилучший скалярный / SSE2 Наилучший скалярный / AVX2 SSE2 / AVX2
24.814 0.565 0.424 43.920 58.566 1.333

Завершение

Как видно из итога тестов, убыстрение алгорифма медианной фильтрации от применения SIMD инструкций на современных процессорах может добиваться от 40 до 60 раз. Как мне кажется это довольная величина, Дабы заморачиваться оптимизацией (если безусловно в вашей программе значима скорость исполнения). В данной публикации я постарался максимально упростить применяемый код.
Так за рамками остались вопросы, связанные выравниванием данных, с обработкой граничных точек, а также многое другое.
Данные вопросы я постараюсь раскрыть в следующих статьях. Если читателя волнует, как будет выглядеть боевой код, реализующий данную функциональность, то он сумеет обнаружить его тут.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB