Двумерное гауссово размытие можно представить как суперпозицию двух одномерных. Это сильно облегчает возможности для распараллеливания.
Мы строим линейный вектор коэффициентов для свёртки, в окне радиусом 3 сигмы. 3 сигмы - это примерно 0.1% на концах, что меньше динамического диапазона (255 уровней в канале). Можно было искать радиус вручную, но и так сойдёт.
Поскольку радиус - в пикселях, то округляем вверх. Итого размер вектора - 2r + 1 = 6s + 1 (+1 это центральный пиксель).
Вектор нормирован, в сумме = 1. Нормировка делается вручную, - во-первых, чтобы не "1/sqrt(2pi*sigma^2)", а во-вторых, чтобы убрать любые ошибки округления, хоть мы и в 3 сигмах.
Для каждой сканлинии (строки или столбца битмапа) слева и справа добавляем одинаковые пиксели в количестве радиус штук, равные краевым пикселям. Это нужно, чтобы цвет пикселя после размытия был "естественным", а не белым-чёрным-прозрачным и т.п.
Размытие сканлинии - это свёртка её пикселей с вектором коэффициентов. На входе - расширенная сканлиния, на выходе - точно в размер линии битмапа.
Поскольку свёртки сканлиний не влияют друг на друга, они выполняются параллельно.
Два этапа: сперва по строкам, и строго за тем - по столбцам. (Можно наоборот, непринципиально).
Для экономии памяти, битмап не копируется, а перезаписывается.
Поскольку нельзя просто так взять и расшарить битмап между воркерами, то мы вынуждены копировать каждую сканлинию.
Также мы не можем просто так взять и перезаписывать сканлинию во время свёртки. (Ну то есть, можем, но там получится хитроумное уравнение и набежит погрешность).
Таким образом, полный расход памяти - это
- сам битмап, из которого мы извлекаем сканлинии и куда записываем их обратно
- исходные сканлинии (фрагмент битмапа с полями по горизонтали либо вертикали)
- полученные сканлинии (фрагмент битмапа)
Фрагмент битмапа равен количеству одновременно обрабатываемых сканлиний (см. ниже).
Через границу потоков (между окном и воркерами) битмап и-или сканлинии передаются не копированием, а перемещением (transfer), это экономит память, но это семантика монопольного владения и временных данных.
Перезапись битмапа также означает семантику монопольного владения. Нельзя просто так взять и вызвать функцию размытия одновременно несколько раз к одному битмапу!
Ради эксперимента, сделал 4 разными способами.
- no worker - запихал функцию в корутину главного оконного потока, а чтобы она не замораживала окно, напихал туда setTimeout'ов
- single thread - запускаю функцию целиком во внешнем потоке
- new worker for each line - запускаю поток для каждой функции свёртки сканлинии - это чертовски невыгодно, поскольку быстро создаётся гора потоков
- fixed pool of threads фиксированный пул потоков с протоколом общения: передаю коэффициенты один раз на старте, затем каждый запрос - это свёртка какой-то сканлинии, уникально идентифицированной.
Количество одновременных корутин-заявок задаётся произведением pool size * crowd factor.
Это сделано для того, чтобы, с одной стороны, не забивать очередь сообщений, а с другой, чтобы пул не простаивал.
- При факторе толпы = 1 каждый поток пула, фактически, обслуживает одну корутину в режиме пинг-понга.
- При факторе = 2 получаем две корутины на поток, поэтому одна заявка обслуживается, а вторая отправила данные в очередь сообщений. Таким образом, мы работаем чуть эффективнее
- При факторе < 1 пул недогружен
- При факторе > 1 заявки буферизуются (чем больше, тем сильнее нагрузка на память, но на производительность это влияет мало)
В случае с методом "свой воркер для каждой сканлинии" это ограничивает количество потоков количеством корутин.
В случае с методом "один воркер" эти параметры игнорируются.
В случае с методом "без воркера" это просто определяет количество корутин. Поток-исполнитель один, и это - главный поток окна.
Адаптивный способ - для маленьких картинок запускает однопоточную версию, для больших пул потоков.
На странице выполняются асинхронные действия двух видов
- сброс картинки (загрузка новой из ресурса, восстановление исходной из кеша)
- размытие (длительный процесс)
Многократный запуск размытия приводит к последовательному их применению (каждый новый запуск дожидается завершения предыдущего)
Сброс останавливает все размытия (исполняемое и запланированные) в любой момент времени.
Предпочёл экмаскрипт с модулями, потому что не разобрался, как красиво делать импорты без них.
Каждый способ оформлен как модуль, в котором есть клиентская функция и тело воркера. Воркер запускается отдельным модулем, все эти body.ts выглядят одинаково. Наверное, можно наколдовать в виде сериализации скрипта в урл... (TODO попробовать)
Битмап и сканлинии представлены классами-обёртками над сырыми байтовыми массивами.
Функции высшего порядка - по необходимости. Колбеки там передавать всякие. Если честно, то не хотел преждевременно нормализовать код в ущерб наглядности, а возможно, что и в ущерб производительности.
Вот эта гиря node_modules - это стандартный http-server.
Я не виноват, что npm install http-server втянул такую гирю.
Сайт статический. Он состоит из 3 каталогов
- /html/main.html
- /distrib/**/*.js
- /images/*.png
Но просто сохранить и открывать в схеме file:// нельзя, у браузера сработает защита.
Надо запустить вебсервер (самый тупой, npm run http-server прописан в package.json).
- Запустить веб-сервер!!!
- Загрузить файл (кнопка Load file...) или указать урл картинки и нажать "Load!"
- Дождаться изображения
- Установить желаемые параметры размытия (сигму и технические детали реализации)
- Нажать "Blur"
- Картинка блюрится в реальном времени (перерисовывается канва)
- Многократное нажатие "Blur" размывает её всё больше и больше
- Чтобы вернуться к исходному состоянию, - нажать "Reset"
- distrib - сюда генереруются javascript-файлы, структура совпадает с src
- html
- main.html - главная и единственная страничка
- images - примеры картинок для опытов над ними
- bgd-cure-2.png - фотография моего параплана
- sky-crane.png - какой-то странный вертолёт - летающий кран
- src - исходники на typescript
- main - скрипт для main.html
- dom - то, что требует HTML DOM (выполняется в контексте страницы)
- workers - то, что требует WebWorkers
- tests - тесты (включая и самописный фреймворк) (js тестов генерируются сюда же)
- tsmain - фейковый корневой проект typescript, который подтягивает остальные по зависимостям
Убедиться, что в системе есть node.js и typescript.
Я не смог полноценно настроить окружение в Win11, пошёл простым путём - установил dev-container в WSL,
контейнер называется typescript-node, полное имя
mcr.microsoft.com/devcontainers/typescript-node:1-22-bookworm
(TODO - сделать герметичный докер приложения, научить его вешаться на нужный порт и всё такое)
Выполнить сборку npm run build = tsc -b tsmain
Для тестов (nodejs) выполнить npm run test = tsc - b tsmain && node run ./tests/all_tests.js