Посмотрите на сепарационные фильтры. Среди прочего, они допускают массовый параллелизм в тех случаях, когда они работают.
Например, в вашем 3x3 выборки веса и-фильтра случае:
- Образец 1x3 (по горизонтали) пикселей в буфер. Это можно сделать изолированно для каждого пикселя, поэтому изображение 1024x1024 может запускать 1024^2 одновременных задания, все из которых выполняют 3 выборки.
- Образец 3x1 (по вертикали) пикселей из буфера. Опять же, это можно сделать на каждом пикселе одновременно.
- Используйте содержимое буфера, чтобы отбирать пиксели из исходной текстуры.
Преимущество этого подхода, математически, что это сокращает число операций выборки из n^2
в 2n
, хотя она требует буферов равного размера к источнику (если вы уже выполняете копию, что может использоваться как буфер, вы просто не можете изменить исходный источник для шага 2). Чтобы сохранить память в 2n
, вы можете выполнять шаги 2 и 3 вместе (это немного сложно и не совсем приятно); если память не является проблемой, вы можете потратить 3n
на два буфера (источник, hblur, vblur).
Поскольку каждая операция работает в полной изоляции от неизменяемого источника, вы можете выполнять фильтр на каждом пикселе одновременно, если у вас достаточно ядер. Или, в более реалистичном сценарии, вы можете использовать пейджинг и кеширование для загрузки и обработки одного столбца или строки. Это удобно при работе с нечетными шагами, заполнением в конце строки и т. Д. Второй раунд выборок (по вертикали) может зависать с вашим кешем, но в худшем случае один раунд будет кэшировать, и вы обработка разрезов от экспоненциальной к линейной.
Теперь я еще не прикоснулся к случаю хранения данных в битах. Это делает вещи немного сложнее, но не так уж и страшно. Предполагая, что вы можете использовать скатное окно, что-то вроде:
d = s[x-1] + s[x] + s[x+1]
работы. Интересно, что если вы должны были поворачивать изображение на 90 градусов во время выхода шага 1 (тривиальный, образец от (y,x)
при чтении), вы можете уйти с загрузкой не более двух горизонтально смежных байтов для любого образца, и только один байт что-то вроде 75% времени. Это играет немного менее дружелюбно с кешем во время чтения, но значительно упрощает алгоритм (достаточно, чтобы он мог восстановить потерю).
Псевдо-код:
buffer source, dest, vbuf, hbuf;
for_each (y, x) // Loop over each row, then each column. Generally works better wrt paging
{
hbuf(x, y) = (source(y, x-1) + source(y, x) + source(y, x+1))/3 // swap x and y to spin 90 degrees
}
for_each (y, x)
{
vbuf(x, 1-y) = (hbuf(y, x-1) + hbuf(y, x) + hbuf(y, x+1))/3 // 1-y to reverse the 90 degree spin
}
for_each (y, x)
{
dest(x, y) = threshold(hbuf(x, y))
}
Доступ битов в байтах (source(x, y)
указывает доступ/образец) относительно просто сделать, но вид боли, чтобы написать здесь, так что остается для читателя. Принцип, особенно реализованный таким образом (с 90-градусным вращением), требует только 2 прохода из n
выборок каждый и всегда выборки из сразу смежных битов/байтов (никогда не требующих вычисления позиции бит в следующей строке) , В целом, это намного быстрее и проще, чем любая альтернатива.
Является ли ваша ширина изображения кратной 8 или строки заполнены так, что каждый начинается с границы байта? Это обычно так, и это делает вещи немного легче. Вам нужно всего 3 маски вместо 9. –
Ширина изображения произвольная, но каждая строка начинается с границы байта. Строки могут быть дополнены к более крупным границам, но гарантированно будут дополняться байтами. – theotherphil
Каков ваш метод заполнения по краям? Повторить или зажать? – Ani