Переменный радиус размытия по Гауссу, аппроксимирующий ядро

Question

Я пишу размытие по Гауссу с переменным радиусом (стандартное отклонение), то есть каждый пиксель изображения свернут с использованием другого ядра. Стандартные методы вычисления размытия по Гауссу здесь не работают: БПФ, разделение по осям, повторное размытие по прямоугольнику - все они предполагают, что ядро ​​одинаково для всего изображения.

Теперь я пытаюсь приблизить его по следующей схеме:

Аппроксимируем ядро ​​Гаусса K (x, y) кусочно-постоянной функцией f (x, y), определенной набором N прямоугольников, выровненных по оси R _k и коэффициентами α _k как:

f (x, y) = ∑ _{k = 1} ^N α _k · χ _{R k} (х, у)

Пусть g (x, y) будет нашим изображением, тогда

∬ _{ℝ ²} K (x, y) · g (x, y) dxdy ≈ 10 _{ℝ ²} f (x, y) · g (x, y) dxdy = ∑ _{k = 1} ^N α _к · ∬ _{R K * +1041 ** 1 042 * г (х, у) йхйу * * 1 043 Интеграл по RHS - это простой интеграл по прямоугольнику, и как таковой он может быть вычислен за постоянное время путем предварительного вычисления частичных сумм для всего изображения.}

Полученный алгоритм работает в O (W · H · N), где W и H - размеры изображения, а N - (AFAIK), обратно пропорциональный погрешности аппроксимации.

Оставшаяся часть - найти хорошую функцию приближения f (x, y). Как найти оптимальное приближение к гауссову, когда задано либо количество прямоугольников N (минимизирует ошибку), либо с учетом ошибки (минимизировано количество прямоугольников)?

Answer 1

Учитывая расположение и размер прямоугольников, вам будет довольно легко определить ваши коэффициенты, поэтому реальная проблема заключается в том, чтобы определить, куда поместить прямоугольники.

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

Это можно решить с помощью динамического программирования. Предположим, что вы работаете снаружи в середине. На этапе N вы разработали таблицу nxk, которая дает вам наилучшую возможную ошибку аппроксимации из 1,2 ... N колец внешних пикселей для более 1,2, ... K различных прямоугольников и размера самого внутреннего прямоугольника. ответственность за эту лучшую ошибку. Чтобы проработать этап N + 1, вы учитываете все возможные размеры для того, что будет самым внутренним прямоугольником на данный момент, добавляя x колец пикселей во внешнюю область. Вы определяете альфа для этого прямоугольника, который наилучшим образом подходит для пикселей в новом кольце и для тех колец, которые находятся вне него, а не для внешних прямоугольников. Используя уже рассчитанные значения в таблице, вы знаете наилучшую возможную ошибку, которую получите, когда оставите до k внешних прямоугольников, чтобы покрыть эти области, чтобы вы могли определить наилучшую суммарную ошибку, полученную из того, что сейчас является N + 1 кольцами пикселей. , Это позволяет заполнить записи таблицы для N + 1 внешних пикселей. Проложив свой путь в центр области, вы сможете найти оптимальное решение для всей области.