Не максимальное подавление в алгоритме Кэнни: оптимизировать с помощью SSE
У меня есть «честь» улучшить время выполнения следующего кода кого-то еще. (Это не максимальное подавление от алгоритма canny — «. Моей первой мыслью было использование SSE-внутреннего кода, я очень новичок в этой области, поэтому мой вопрос таков.
Есть ли шанс сделать это?
И если да, может кто-нибудь дать мне несколько советов?
void vNonMaximumSupression(
float* fpDst,
float const*const fpMagnitude,
unsigned char const*const ucpGradient, ///< [in] 0 -> 0°, 1 -> 45°, 2 -> 90°, 3 -> 135°
int iXCount,
int iXOffset,
int iYCount,
int ignoreX,
int ignoreY)
{
memset(fpDst, 0, sizeof(fpDst[0]) * iXCount * iXOffset);
for (int y = ignoreY; y < iYCount - ignoreY; ++y)
{
for (int x = ignoreX; x < iXCount - ignoreX; ++x)
{
int idx = iXOffset * y + x;
unsigned char dir = ucpGradient[idx];
float fMag = fpMagnitude[idx];
if (dir == 0 && fpMagnitude[idx - 1] < fMag && fMag > fpMagnitude[idx + 1] ||
dir == 1 && fpMagnitude[idx - iXCount + 1] < fMag && fMag > fpMagnitude[idx + iXCount - 1] ||
dir == 2 && fpMagnitude[idx - iXCount] < fMag && fMag > fpMagnitude[idx + iXCount] ||
dir == 3 && fpMagnitude[idx - iXCount - 1] < fMag && fMag > fpMagnitude[idx + iXCount + 1]
)
fpDst[idx] = fMag;
else
fpDst[idx] = 0;
}
}
}
Решение
обсуждение
Как отметил @harold, основная проблема векторизации заключается в том, что алгоритм использует различное смещение для каждого пикселя (определяется матрицей направления). Я могу придумать несколько возможных способов векторизации:
- @nikie: оценивать все ветви одновременно, то есть сравнивать каждый пиксель со всеми соседями. Результаты этих сравнений смешиваются в соответствии со значениями направления.
- @PeterCordes: загрузить много пикселей в регистры SSE, затем использовать
_mm_shuffle_epi8выбирать только соседей по заданному направлению. Затем выполните два векторизованных сравнения. - (я): используйте скалярные инструкции, чтобы загрузить правильные два соседних пикселя вдоль направления. Затем объедините эти значения для четырех пикселей в регистры SSE. Наконец, сделайте два сравнения в SSE.
Второй подход очень сложно реализовать эффективно, потому что для пакета из 4 пикселей есть 18 соседних пикселей на выбор. Я думаю, это потребует слишком много перемешиваний.
Первый подход выглядит неплохо, но он будет выполнять в четыре раза больше операций на пиксель. Я полагаю, что ускорение векторных инструкций было бы перегружено слишком большим количеством вычислений.
Я предлагаю использовать третий подход. Ниже вы можете увидеть советы по улучшению производительности.
Гибридный подход
Прежде всего, мы хотим сделать скалярный код максимально быстрым. Представленный вами код содержит слишком много веток. Большинство из них непредсказуемы, например, переключение по направлению.
Для удаления веток предлагаю создать массив delta = {1, stride - 1, stride, stride + 1}, который дает смещение индекса от направления. Используя этот массив, вы можете найти индексы соседних пикселей для сравнения (без ветвей). Затем вы делаете два сравнения. Наконец, вы можете написать троичный оператор, как res = (isMax ? curr : 0);надеясь, что компилятор сможет сгенерировать для него код без ответвлений.
К сожалению, компилятор (по крайней мере, MSVC2013) недостаточно умен, чтобы избежать перехода по isMax, Вот почему мы можем извлечь пользу от переписывания внутреннего цикла с помощью скалярных встроенных функций SSE. Уважать гид для справки. Вам нужны в основном встроенные функции, заканчивающиеся на _ss, так как код полностью скалярный.
Наконец, мы можем векторизовать все, кроме загрузки соседних пикселей. Для загрузки соседних пикселей мы можем использовать _mm_setr_ps внутренности со скалярными аргументами, просящие компилятор сгенерировать хороший код для нас =)
__m128 forw = _mm_setr_ps(src[idx+0 + offset0], src[idx+1 + offset1], src[idx+2 + offset2], src[idx+3 + offset3]);
__m128 back = _mm_setr_ps(src[idx+0 - offset0], src[idx+1 - offset1], src[idx+2 - offset2], src[idx+3 - offset3]);
Я только что реализовал это сам. Протестировано в одной ветке на Ivy Bridge 3.4Ghz. В качестве источника использовалось случайное изображение с разрешением 1024 x 1024. Результаты (в миллисекундах):
original: 13.078 //your code
branchless: 8.556 //'branchless' code
scalarsse: 2.151 //after rewriting to sse intrinsics
hybrid: 1.159 //partially vectorized code
Они подтверждают улучшения производительности на каждом этапе. Окончательный код требует чуть больше одной миллисекунды для обработки изображения размером в один мегапиксель. Общая убыстрение около 11,3 раза. Действительно, вы можете получить лучшую производительность на GPU =)
Я надеюсь, что представленной информации будет достаточно для воспроизведения шагов. Если вы ищете ужасные спойлеры, посмотрите Вот для моих реализаций всех этих этапов.
Другие решения