Комментарии 36
en.wikipedia.org/wiki/Box_blur
amritamaz.net/blog/understanding-box-blur
По результату, совершенно нет. Суть бокс бобра как я понимаю в похожем архитектурно способе фильтрации изображения, но он эквивалентен единичной матрице свёртки, что очень примитивно. И даёт заметные квадратные паттерны размытия. Мой же даёт матрицу по распределению Лапласа, которое визуально очень близко к Гаусову. При этом для статичного радиуса х7 возможно доп ускорение на битовых
Эй-эй, так нечестно! Примерно все линейные фильтры делаются без учёта гаммы и т.п. (ещё по древнему-древнему фотошопу помню).
Хотя, возможно, имело бы смысл прогонять через LUT перед фильтром и через обратный после.
aamonster меня опередил, коррекция гаммы в общем случае не относится к алгоритму свёртки/фильтру, она может быть добавленная отдельно к любому. Цветовые профили тоже отдельно реализуются. Сам гаус тоже коррекцию не включает по умолчанию.
Про битность я уточнил как раз перед вами, habr.com/post/427077/#comment_19292437
(И тот факт, что это будет означать, что для удобной коррекции гаммы придется либо отказаться от 3х-канального хака, либо не повышая битность, терпеть большие погрешности)
Кстати для 64бит архитектур возможен качественный запил того же 3х канального хака только с int64 (просто на стадии коррекции понадобиться перепаковать)
Ну сейчас все новые CPU 64-битные, мне кажется, стоит на это ориентироваться.
Кстати, вы не думали использовать SIMD-инструкции? Они умеют работать со 128 битами, и даже больше, за раз. То есть вы бы могли сдвигать, суммировать и делать AND сразу 4 32-битным значениям. А в более мощных процессорах по моему и 256 бит за раз можно обработать. Скорость должна получаться зверская. Они доступны в Си в виде функций и макросов.
Не знаю, можно ли их применить на горизонтальный проход, на вертикальный точно можно.
64-битные, стоит на это ориентироватьсяПро универсальность (не бейте палкой) — v8 aka Самый популярный движок вездесущего интернета, а по совместительству и webapp, — с вами не согласен. 32бит все что он стандартизировал для всех платформ.
SIMD — Отличная идея для «шейдерного» подхода под CPU, соседние строки/столбцы проходов являются независимыми, потому если оставлять хотя бы 2 прохода, можно. Но на горизонталях вопрос перепаковки (столбцов в строки) встает утяжеляя алгоритм (это даже если все попадает в кеш), так что прирост может на выходе захлебнуться. Надо проверять. В прочем ускорить только вертикальный проход так получиться.
На самом деле я уже пробовал вынимать из ARGB G в отдельный канал, зануляя его в исходнике, чтоб работать с запасом бит, но диже это оказалось медленнее. В исходном алгоритме итак предельно быстрые инструкции
У нас формула вида t1 = f(t0) + f(a), где a — старое значение пикселя, t0 и t1 — значения накопителя в разные моменты времени. Вычисление f(a) оптимизируется через SIMD:
— одновременно загружаем 4 соседних пикселя
— одновременно прибавляем 010101
— одновременно делаем сдвиг
— одновременно делаем AND
Остается из непараллельного только сложение с накопителем и обработка значений в накопителе — и то, может и тут как-то схитрить можно? Или переделать формулу? Чтобы мы копировали эти 4 пикселя в другой XMM регистр, сдвигали на 32 бита и складывали.
Что касается сборки пикселей из 4 соседних строк — вроде как тут описан способ загнать 2 32-битных регистра в XMM, может его можно на 4 регистра расширить?
Плюс, там кроме 128-битных есть ведь и 256-битные регистры (AVX). Это уже 8 пикселей за раз можно обрабатывать.
Поканальное деление (на 2 с потерей бита) оптимизировать можно, но даленейшее вычисление зависимо через накопитель. Потому будет какой то оверхед на доп операции, какой — вопрос тестирования. Но может и получиться что то ещё выйграть. В любом случае гарантировано ускорить вертикальный проход в ~четверо было бы неплохо.
Но сейчас основным минусом Алга является константный радиус. Я думаю что возможно рассчитать более качественные константы для больших радиусов.
Этот вопрос конечно гипотетический. Потому что даже если Очень строго подходить к оценке, считая например битовую сложность, или хотя бы реализовав на ассемблере и считая такты, остаётся контекст того, что это все таки апроксимация, а не чистый гаус, потому ответ будет в конечном счёте зависит от того отношения скорость/качество которое вы определите для своей задачи как достаточное
upd: вот вы же указываете в профиле что писали на Spectrum 128K — должны бы понимать куда он как раз пригодиться. Ядро алгоритма очень простое, можете расчехлить спектрум и проверить.
только дразниться
В каком смысле? Думаете он не успеет? (Я просто по его скоростям и возможностям не шарю) Или имеете ввиду что под него уже ни кому не надо?
Во втором случае хочу немного заступиться, если не за спеку, то хотя бы за алгоритмы в целом. Сами по себе они в принципе бесполезны, но будучи реализованы под одно дают идеи и подходы, чаще всего переносимые под нужды. Хотя бы ради открытия/освежения этих идей и подходов они оправданы.
Иными словами, это вопрос к общественности, с целью услышать эмпирическую оценку, о том насколько более быстрым должен быть на ваш взгляд алгоритм, чтобы оправдать постерю точности в ~3%. Но и все равно, данная реализация обрабатывающая три канала за один проход, имеет ценой константный радиус. А если есть блавающая арифметика, и деление в ней быстрое, то радиус может быть разным. Скорость алгоритма в отрыве от железа возможно оценить только асимптотически, и здесь она О(4nm) или O(n*m) если делать однопроходно (но реализация с лучшей асимптотикой здесь медленнее, профессионал понимает что такое может случаться)
Так, что вы хотели конкретно спросить? Какую конструктивную критику здесь несёте.
На вашу постановку вопроса без критерия, абстрактный ответ в статье дан — это 97% эквивалент гауса с примерно втрое большей скоростью
Подробности на хабре уже писали тут: habr.com/company/otus/blog/343566
Чтоб замерить наверняка нужно писать бенчмарк, но отношения благодаря замене деления на сдвиг, и маски, вычисления без распаковки каналов по отдельности из int, будут примерно те же. Троекратное ускорение и больше. Вполне практично можно сделать процессинг на CPU если он слабо занят, для разгрузки видюхи.
Если вы ставите вопросы перед написанием статьи, то стоит давать на них ответы вконце статьи. Даже если точных ответов нет.
Но если вы настаиваете потеоретизировать на предмет прироста скорости на AMDx64
(снимаю с себя какую либо ответственность за дальнейшие размышления)
То предположив точной выдержку из habr.com/company/otus/blog/343566 о скорости инструкций:
Сдвиг ~1 такт (если автор статьи относил его к простым инструкциям)
Целое деление — 12-44 тактов (DIV/IDIV)
Float деление — до 37-39 тактов (FDIV)
SEE деление — 10-40 тактов
SEE умножение — 0.5-5 тактов
Можно предположить что мой выигрыш против CPU реализации гаусса отсюда habr.com/post/151157 (быстрее этой реализации я не видел, хотя она тоже аппроксимация, но не ограничено точная)
Там в центре стреляет такая функция:
(Это если что, от инжинеров Intel software.intel.com/en-us/articles/iir-gaussian-blur-filter-implementation-using-intel-advanced-vector-extensions )посчитав даже по минимому
4x SSE умножения = +4такта
2х сложения = +2 такта
2х вычитания = +2 такта
(игнорируя чтения которых тут больше, но предположим, что все попало в кеш)
= 8 тактов
х 3 канала
= 24 такта
против
2х сдвига = 2 такта
2х маскирование = 2 такта
2х сложение = 2 такта
= 6 тактов (все три канала сразу)
отсюда грязная оценка может быть даже выше х4 прирост относительно «intel-точного» гаус блюра, но с погрешностью 97% и для константного радиуса, зато с понижением требований к окружению исполнения (не требуется SSE, ни плавающей арифметики, ни даже деления, а уж маски и сдвиги и сложения есть везде)
Я его не знаю, у меня просто в закладках уже была хорошая статья, спросил только своего друга, красноглазого сишника, на предмет оценки ее валидности. Он сказал, что результаты похожи на то что он получал. Но в любом случае на это нельзя сколько нибудь строго опираться.
upd: а все понял. Ну просто вы тоже спрашивали про оценку, я решил ответить сразу в эту ветку (не думаю что я особо много тут комментариев соберу, тема то специфичная)
$$f(x|\mu, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x-\mu^2)}{2\sigma^2}\right)$$
Ну и так далее. Очень уж вырвиглазные у вас формулы.
μ — математическое ожидание, σ2 — дисперсия.
И еще нюанс с артефактами: если блюрить белый квадрат, края темнеют:
+ в принципе имеющихся уровней размытия достаточно чтобы если нужно больше получать даунсемплированием (масштабировать сжимая -> блюрить -> масштабировать увеличивая) т.к. пикселизация тем менее заметна глазу на картинках, чем более они размыты. (естественно есть потолок у такого способа) реализация такого блюра через даунсемплирование может быть сделано так же однопроходно (встроена в алг, чтоб ни чего не пережимать предварительно, и не тратя памяти и времени, слышал такая практика существует для облегчения шейдеров)
2.Края темнеют (это называется стратегия заполнения, фон за пределами растра считается черным, потому такое размытие вполне честно, стратегии бывают разные, можно поменять алгоритм под белый/серый цвет/ под взятие цвета с противоположной стороны/ под взятие ближайшего крайнего/ под медианку из некоторых пикселей в краевой зоне… по вашему вкусу)
— Здесь чтобы не перегружать суть алгоритма, стратегия была выбрана простейшая
Ковырял Интловый Фильтр, в надежде приспособить его под Ланцош.
(Который прекрасно заездит как детектор конкретной частоты, не в пример быстрее чем БПФурье для всего спектра - отличный трай для гитарного тюнера, на ущербных микроконтроллерах почти без ОЗУ - ему надо всего 3 переменных состояния!!!)
Внезапно оказалось что интловый фильтр и есть Ланцоша... просто его частный случай подгоняется под Гаус Блюр (вероятно коэфициентами при х - т.к. кроме амплитуды визуальных закономерностей от них больше не выявлено - либо их можно упростить, либо они возможно позволяют как то просто управлять альфа кривой. Хотя это не поясняется в оригинале.)
В целом мой фильтр размытия "Лапласа" дает максимально похожую картину распределения, за исключением пика на котором и теряется 3% точности, и теперь мне кажется что кулибины из Intel не особо старались в оптимайз, на самом деле просто юзнули какой то общий IIR фильтр Ланцоша... под блюр подгонкой пары коэффициентов.
В принципе если бы мой 97% точный блюр на Лапласе не был в 4ро быстрее на сдвигах и масках, чем их типа честный Гаус на SSE... то я бы мог тоже подгонные коэффициенты ввести. Плюс на флоат этот отвязывается от константного радиуса
Ну или если я перепишу на SSE то вздеру ихний по скорости раз в 5...
трай https://codepen.io/impfromliga/pen/OJoeeRb
Laplace Blur — Можно ли блюрить Лапласом вместо Гаусса, во сколько раз это быстрее, и стоит ли того потеря 1/32 точности