Pull to refresh

Comments 36

По результату, совершенно нет. Суть бокс бобра как я понимаю в похожем архитектурно способе фильтрации изображения, но он эквивалентен единичной матрице свёртки, что очень примитивно. И даёт заметные квадратные паттерны размытия. Мой же даёт матрицу по распределению Лапласа, которое визуально очень близко к Гаусову. При этом для статичного радиуса х7 возможно доп ускорение на битовых

Поправка, матрицы полностью состоящей из единиц (либо некоей одной константы обычно 1/кол-во элементов матрицы)
Ну ок. А давайте тогда про другой подвох спрошу: ваш метод ведь не учитывает нелинейность пространства sRGB? То есть условно, повышение значения RGB в 2 раза не означает повышения яркости пикселя в те же 2 раза.

Эй-эй, так нечестно! Примерно все линейные фильтры делаются без учёта гаммы и т.п. (ещё по древнему-древнему фотошопу помню).
Хотя, возможно, имело бы смысл прогонять через LUT перед фильтром и через обратный после.

Ну и еще надо уточнить. Конкретно для подтыкания коррекций в данную реализацию, скорее всего прийдется отказаться от ускоряющего хака с тремя каналами в одном int. Потому что для коррекции гаммы на вскидку int = LUT[int] будет недостаточно. Если мне не врет память коррекция гаммы связана с тем, что фактическое кол-во света от пиксела это квадрат (его площадь), а значения мы вычитаем линейно. Т.о. что бы без ошибок обрабатывать гамму, потребуется увеличивать битность каналов. (храня в HDR) Либо считать в один проход усложняя алгоритм.
Просто LUT тут маловато, надо расширять диапазон значений, не знаю, хватит тут 16 бит.

aamonster меня опередил, коррекция гаммы в общем случае не относится к алгоритму свёртки/фильтру, она может быть добавленная отдельно к любому. Цветовые профили тоже отдельно реализуются. Сам гаус тоже коррекцию не включает по умолчанию.

Нет, коррекцией гаммы после применения фильтра это не решить. Надо преобразовать значения в линейные, применить эффект, преобразовать значения обратно в sRGB. И чтобы не потерять точность, может понадобиться преобразовать все из 8 в 16-бит (хотя я не уверен).

Именно так как вы и пишите, не затрагивая сам блюр фильтр и можно добавить, только «после» сказали и тут же опровергли вы, а не я. Естественно коррекция на входе и выходе.

Про битность я уточнил как раз перед вами, habr.com/post/427077/#comment_19292437
(И тот факт, что это будет означать, что для удобной коррекции гаммы придется либо отказаться от 3х-канального хака, либо не повышая битность, терпеть большие погрешности)

Кстати для 64бит архитектур возможен качественный запил того же 3х канального хака только с int64 (просто на стадии коррекции понадобиться перепаковать)
> Кстати для 64бит архитектур возможен качественный запил того же 3х канального хака только с int64 (просто на стадии коррекции понадобиться перепаковать)

Ну сейчас все новые CPU 64-битные, мне кажется, стоит на это ориентироваться.

Кстати, вы не думали использовать SIMD-инструкции? Они умеют работать со 128 битами, и даже больше, за раз. То есть вы бы могли сдвигать, суммировать и делать AND сразу 4 32-битным значениям. А в более мощных процессорах по моему и 256 бит за раз можно обработать. Скорость должна получаться зверская. Они доступны в Си в виде функций и макросов.

Не знаю, можно ли их применить на горизонтальный проход, на вертикальный точно можно.
64-битные, стоит на это ориентироваться
Про универсальность (не бейте палкой) — v8 aka Самый популярный движок вездесущего интернета, а по совместительству и webapp, — с вами не согласен. 32бит все что он стандартизировал для всех платформ.

SIMD — Отличная идея для «шейдерного» подхода под CPU, соседние строки/столбцы проходов являются независимыми, потому если оставлять хотя бы 2 прохода, можно. Но на горизонталях вопрос перепаковки (столбцов в строки) встает утяжеляя алгоритм (это даже если все попадает в кеш), так что прирост может на выходе захлебнуться. Надо проверять. В прочем ускорить только вертикальный проход так получиться.

На самом деле я уже пробовал вынимать из ARGB G в отдельный канал, зануляя его в исходнике, чтоб работать с запасом бит, но диже это оказалось медленнее. В исходном алгоритме итак предельно быстрые инструкции
А нельзя ли SIMD'ами оптимизировать именно горизонтальный проход?

У нас формула вида 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 с потерей бита) оптимизировать можно, но даленейшее вычисление зависимо через накопитель. Потому будет какой то оверхед на доп операции, какой — вопрос тестирования. Но может и получиться что то ещё выйграть. В любом случае гарантировано ускорить вертикальный проход в ~четверо было бы неплохо.


Но сейчас основным минусом Алга является константный радиус. Я думаю что возможно рассчитать более качественные константы для больших радиусов.

В статье не хватает выводов с ответом на ваши же вопросы «во сколько раз это быстрее, и стоит ли того потеря 1/32 точности.»

Этот вопрос конечно гипотетический. Потому что даже если Очень строго подходить к оценке, считая например битовую сложность, или хотя бы реализовав на ассемблере и считая такты, остаётся контекст того, что это все таки апроксимация, а не чистый гаус, потому ответ будет в конечном счёте зависит от того отношения скорость/качество которое вы определите для своей задачи как достаточное

Тогда стоит хотя бы указать примерный %. Стоит ли вообще думать о таких апроксимациях, или это экономия на спичках?
Поймите здесь не может быть простого ответа. И нет это не экономия на спичках. Но, возвращаясь опять к дисклеймеру важно заметить контекст в котором задача сравнивается. Наилучшее окружение для данного алгоритма (в котором его преимущество относительно растет) это простые инструкции. (отсутствие деления например и плавающей арифметики). Опять же это CPU алгоритм, его нет смысла сравнивать с GPU. (GPU наверняка будет быстрее). Хотя саму функцию фильтра можно перенести на float и на GPU. И возможно она там даже будет лидировать, но от данного алгоритма эта реализация уйдет очень далеко. Можно однако рассматривать его практически как вариант CPU постпроцессинга (как позиционирует Intel например свой алгоритм CPU АнтиАлиасинга MLAA — если не хочется тратить ресурсы GPU, можно помогать ему и постпроцеcсить на CPU)

upd: вот вы же указываете в профиле что писали на Spectrum 128K — должны бы понимать куда он как раз пригодиться. Ядро алгоритма очень простое, можете расчехлить спектрум и проверить.
Ну так можно же и на спектруме реализовать честного Гаусса. У вас отличная статья. Просто хотелось бы выводов и сравнений, как в этой статье. Но вы уже ответили ниже, чего вполне достаточно. А на спекки реализовать размытие изображений, только дразниться.
только дразниться

В каком смысле? Думаете он не успеет? (Я просто по его скоростям и возможностям не шарю) Или имеете ввиду что под него уже ни кому не надо?

Во втором случае хочу немного заступиться, если не за спеку, то хотя бы за алгоритмы в целом. Сами по себе они в принципе бесполезны, но будучи реализованы под одно дают идеи и подходы, чаще всего переносимые под нужды. Хотя бы ради открытия/освежения этих идей и подходов они оправданы.
Z80 3,5МГц, 8 бит. Но дело не в этом. Там был экран 256 х 192, где пиксели в блоке 8 х 8 могли иметь только два цвета из палитры в 16 цветов.
Для примера
image
Понял свою ошибку.
Ну теперь ради фана и желая идти до конца, — пишем Дизеринг-Блюр!
*иронично* Он может быть еще быстрее (Битовая сложность позволяет)
Учтите, в Z80 по сравнению с i8080 есть второй набор регистров, что довольно выгодно и другие улучшения.

Иными словами, это вопрос к общественности, с целью услышать эмпирическую оценку, о том насколько более быстрым должен быть на ваш взгляд алгоритм, чтобы оправдать постерю точности в ~3%. Но и все равно, данная реализация обрабатывающая три канала за один проход, имеет ценой константный радиус. А если есть блавающая арифметика, и деление в ней быстрое, то радиус может быть разным. Скорость алгоритма в отрыве от железа возможно оценить только асимптотически, и здесь она О(4nm) или O(n*m) если делать однопроходно (но реализация с лучшей асимптотикой здесь медленнее, профессионал понимает что такое может случаться)


Так, что вы хотели конкретно спросить? Какую конструктивную критику здесь несёте.


На вашу постановку вопроса без критерия, абстрактный ответ в статье дан — это 97% эквивалент гауса с примерно втрое большей скоростью

А что на «обычном» железе с аппаратными операциями с плавающей точкой типа AMD x64 + SSE/AVX?
На обычном железе типа AMD x64 ситуация прикидки на пальцах довольно неточна, в связи с тем, что современные настольные процессоры чрезвычайно усложнились в своем устройстве. Они пытаются угадывать условные переходы, выполнять инструкции параллельно, юзать L кеш, так что иной раз могут вообще выходить цифры будто инструкций выполняется больше чем максимальная частота процессора… а иногда нет.
Подробности на хабре уже писали тут: 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 (быстрее этой реализации я не видел, хотя она тоже аппроксимация, но не ограничено точная)

Там в центре стреляет такая функция:
image (Это если что, от инжинеров 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: а все понял. Ну просто вы тоже спрашивали про оценку, я решил ответить сразу в эту ветку (не думаю что я особо много тут комментариев соберу, тема то специфичная)
А TeX вам тоже не близок?

$$f(x|\mu, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x-\mu^2)}{2\sigma^2}\right)$$

image
Ну и так далее. Очень уж вырвиглазные у вас формулы.

μ — математическое ожидание, σ2 — дисперсия.
Здесь согласен, надо осваивать
Как я понимаю, единственный способ увеличивать размытие – делать больше проходов? То есть, чем сильнее блюр, тем он (линейно) медленнее?
И еще нюанс с артефактами: если блюрить белый квадрат, края темнеют:
1.Увеличить размытие в данной реализации нет нельзя, это связанно со скоростным битовым хаком. Данный алгоритм для константного радиуса. Однако константа может быть х7 х15 х31 (однако учтите, что каждая следующая имеет большую погрешность 31 так тот вообще нежелательно использовать без дополнительного прохода х7), если интересно можете попробовать демо тут codepen.io/impfromliga/pen/VERzPJ блюр х7 х15 х31 прибинжен на клавиши 1,2,3
+ в принципе имеющихся уровней размытия достаточно чтобы если нужно больше получать даунсемплированием (масштабировать сжимая -> блюрить -> масштабировать увеличивая) т.к. пикселизация тем менее заметна глазу на картинках, чем более они размыты. (естественно есть потолок у такого способа) реализация такого блюра через даунсемплирование может быть сделано так же однопроходно (встроена в алг, чтоб ни чего не пережимать предварительно, и не тратя памяти и времени, слышал такая практика существует для облегчения шейдеров)

2.Края темнеют (это называется стратегия заполнения, фон за пределами растра считается черным, потому такое размытие вполне честно, стратегии бывают разные, можно поменять алгоритм под белый/серый цвет/ под взятие цвета с противоположной стороны/ под взятие ближайшего крайнего/ под медианку из некоторых пикселей в краевой зоне… по вашему вкусу)
— Здесь чтобы не перегружать суть алгоритма, стратегия была выбрана простейшая

Ковырял Интловый Фильтр, в надежде приспособить его под Ланцош.
(Который прекрасно заездит как детектор конкретной частоты, не в пример быстрее чем БПФурье для всего спектра - отличный трай для гитарного тюнера, на ущербных микроконтроллерах почти без ОЗУ - ему надо всего 3 переменных состояния!!!)

Внезапно оказалось что интловый фильтр и есть Ланцоша... просто его частный случай подгоняется под Гаус Блюр (вероятно коэфициентами при х - т.к. кроме амплитуды визуальных закономерностей от них больше не выявлено - либо их можно упростить, либо они возможно позволяют как то просто управлять альфа кривой. Хотя это не поясняется в оригинале.)

В целом мой фильтр размытия "Лапласа" дает максимально похожую картину распределения, за исключением пика на котором и теряется 3% точности, и теперь мне кажется что кулибины из Intel не особо старались в оптимайз, на самом деле просто юзнули какой то общий IIR фильтр Ланцоша... под блюр подгонкой пары коэффициентов.

В принципе если бы мой 97% точный блюр на Лапласе не был в 4ро быстрее на сдвигах и масках, чем их типа честный Гаус на SSE... то я бы мог тоже подгонные коэффициенты ввести. Плюс на флоат этот отвязывается от константного радиуса

Ну или если я перепишу на SSE то вздеру ихний по скорости раз в 5...
трай https://codepen.io/impfromliga/pen/OJoeeRb

Sign up to leave a comment.

Articles