История повторяется

[yurikhan]

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

Ну, казалось бы, в номере 6­–8 символов. Грубо 50% времени уходит на их нахождение, остальные 50% — на распознавание. Запустим распознавание символов параллельно, получим довольно дёшево 20­–40% прироста производительности.

Щаззз. 5–10% выигрыша есть, но профилировщик показывает, что общее использование процессора (в процессор⋅секундах) увеличилось. Разбиваем по функциям — тормозит нахождение скелета символа. Ну то есть как тормозит: за один запуск на тестовом наборе в 600 картинок параллельная версия проводит там на две секунды больше, чем последовательная.

Разбиваем её подробнее, до уровня вызовов функций библиотеки IPP. Собираем статистику ещё раз. В топе — вызов ippFilter.

Алгоритм скелетизации построен на анализе окрестностей 3×3 каждого пиксела. Если окрестность имеет определённый вид, то точка является краевой и её можно погасить. Когда на очередном шаге гасить нечего, то, что осталось — это и есть скелет.

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

N[x,y] =  8 A[x-1,y+1] +  4 A[x,y+1] +  2 A[x+1,y+1]
       + 16 A[x-1,y]                 +    A[x+1,y]
       + 32 A[x-1,y-1] + 64 A[x,y-1] +128 A[x+1,y-1]

Вот чего проще, вроде бы: бери свёртку A с ядром

8	4	2
16	0	1
32	64	128

и это будет то, что надо.

Оно, конечно, то, что надо. Но вот выходит, что быстрее сделать вот так:

N[0:w-2, 0:h-1]  = A[1:w-1, 0:h-1]
A <<= 1
N[0:w-2, 0:h-2] |= A[1:w-1, 1:h-1]
A <<= 1
N[0:w-1, 0:h-2] |= A[0:w-1, 1:h-1]
A <<= 1
N[1:w-1, 0:h-2] |= A[0:w-2, 1:h-1]
A <<= 1
N[1:w-1, 0:h-1] |= A[0:w-2, 0:h-1]
A <<= 1
N[1:w-1, 1:h-1] |= A[0:w-2, 0:h-2]
A <<= 1
N[0:w-1, 1:h-1] |= A[0:w-1, 0:h-2]
A <<= 1
N[0:w-2, 1:h-1] |= A[1:w-1, 0:h-2]
A >>= 7

И в параллельной версии, что характерно, время тоже перестаёт теряться.

Так что это мне напомнило? А вот была во времена 386’х такая техника: вместо y*320 брать y<<8 + y<<6. Сдвиги и сложение работали быстрее, чем операция умножения произвольных целых чисел (внутри процессора реализованная через те же сдвиги и сложения). Так и сейчас — быстрее сделать 8 сдвигов (уже целой матрицы поэлементно) и 8 побитовых or’ов (двух матриц поэлементно), чем свернуть матрицу с заданным ядром (которое, в общем случае, может быть произвольного размера и с произвольными весами).