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

[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’ов (двух матриц поэлементно), чем свернуть матрицу с заданным ядром (которое, в общем случае, может быть произвольного размера и с произвольными весами).

Comments

[wra-ripe.livejournal.com]

Ну да, людей с школой DemoDisign'а конца 90х уже нет, всё птицы полёта на высоких уровнях. Кстати, а на nVidia CUDA такие штуки не удобно будет сделать? :)

[yurikhan]

CUDA не надо, вот OpenCL будем пробовать.

[yurikhan]

А вот ещё если соседним пикселям сопоставлять номера битов не по окружности, а по-умному:

1	4	2
64	256	128
8	32	16

то фильтр станет сепарабельным в крапинку…

temp[1:w-1, 0:h-1] = orig[0:w-2, 0:h-1]
orig <<= 1
temp[0:w-2, 0:h-1] |= orig[1:w-1, 0:h-1]
orig <<= 1
temp[0:w-1, 0:h-1] |= orig[0:w-1, 0:h-1]
orig >>= 2
neigh[0:w-1, 0:h-2] = temp[0:w-1, 1:h-1]
temp <<= 3
neigh[0:w-1, 1:h-1] |= temp[0:w-1, 0:h-2]
temp <<= 3 // центральный пиксел с весом 256
           // вываливается за границу байта
neigh[0:w-1, 0:h-1] |= temp[0:w-1, 0:h-1]

[gegmopo4.livejournal.com]

Да, вот тоже хотел это предложить.