Размытие по Гауссу с переменным радиусом, приближающееся к ядру

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

Теперь я пытаюсь аппроксимировать это, используя следующую схему:

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

f(x,y) = ∑k=1N αk·χRk< / под> (х, у)

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

∬ℝ2 K(x,y)·g(x,y) dxdy ≈ ∬ℝ2 f (x,y)·g(x,y) dxdy = ∑k=1N αk·∬Rkg(x,y) dxdy

Интеграл на RHS представляет собой простой интеграл по прямоугольнику, и поэтому его можно вычислить за постоянное время путем предварительного вычисления частичных сумм для всего изображения.

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

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


blur algorithm math gaussian numerical-methods
person Yakov Galka    schedule 24.09.2011    source источник
comment
Как переменный радиус входит в приближение к гауссовскому ядру? Кроме того, ваше уравнение для свертки (размытия) кажется странным: вы хотите написать G(x0, y0) = ∬ K(x-x0,y-y0)·g(x,y) dxdy? В любом случае, другой подход, который вы можете использовать, заключается в выполнении нескольких сверток с разными ядрами, а затем линейной интерполяции между ними в зависимости от положения.   -  person Kipton Barros    schedule 25.09.2011
comment
@Kipton: я предполагаю, что ядро ​​сосредоточено вокруг (0,0) и имеет фиксированный радиус. Перевод и масштабирование набора прямоугольников, которые аппроксимируют его, можно выполнять за постоянное время на пиксель без изменения относительной частоты ошибок.   -  person Yakov Galka    schedule 25.09.2011
comment
@Kipton: Ваш подход имеет линейную временную и пространственную сложность, которая становится квадратичной при стремлении ошибки к нулю.   -  person Yakov Galka    schedule 25.09.2011

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

person mcdowella    schedule 25.09.2011
comment
Совершенно очевидно, что конфигурация симметрична относительно начала координат, и без ограничения общности прямоугольники центрированы (если нет, то есть 4 симметричных прямоугольника, которые можно заменить комбинацией из 4-х центрированных прямоугольников: один большой, два в + рисунок и маленький). Однако я не понимаю, почему вы говорите, что это проблема 1D. Кто сказал, что все прямоугольники имеют одинаковое соотношение сторон? Почему они не могут перекрываться, но не вкладываться? На самом деле я почти уверен, что оптимальное решение будет содержать невложенные прямоугольники. - person Yakov Galka; 25.09.2011
comment
Что я имел в виду под одномерной задачей, так это то, что при ограничениях, которые я предполагал, в прямоугольнике есть только одна степень свободы: его размер. В свою очередь, это означает, что подход динамического программирования может работать вдоль одномерной линии - увеличивая N в моем ответе - что обычно является разницей между проблемой динамического программирования, разрешимой и нет. Если глобальное оптимальное решение не может быть найдено путем рассмотрения вложенных прямоугольников — или, по крайней мере, набора непересекающихся фигур заданной формы — тогда этот подход, вероятно, непрактичен — извините. - person mcdowella; 25.09.2011