В чем разница между различием гауссовского, лапласа гауссовского и мексиканского шляпного вейвлета?

В CV используются три метода, которые кажутся очень похожими друг на друга, но с небольшими различиями:

Лапласиан Гауссова: $\nabla^2\left[g(x,y,t)\ast f(x,y)\right]$
Различие гауссиан: $\left[g_1(x,y,t)\ast f(x,y)\right] - \left[g_2(x,y,t)\ast f(x,y)\right]$
Свертка с вейвлетом Рикера : $\textrm{Ricker}(x,y,t)\ast f(x,y)$

Насколько я понимаю в настоящее время: DoG является приближением к LoG. Оба используются в обнаружении BLOB-объектов, и оба работают в основном как полосовые фильтры. Свертывание с вейвлетом Мексиканская шляпа / Рикер, похоже, дает почти такой же эффект.

Я применил все три метода к импульсному сигналу (с необходимым масштабированием, чтобы получить сходные величины), и результаты чертовски близки. На самом деле, LoG и Ricker выглядят почти одинаково. Единственное реальное отличие, которое я заметил, в DoG, у меня было 2 свободных параметра для настройки ( и ) против 1 для LoG и Ricker. Я также обнаружил, что вейвлет был самым простым / быстрым, поскольку его можно было сделать с помощью одной свертки (с помощью умножения в пространстве Фурье с FT ядра) против 2 для DoG и свертки с лапласианом для LoG. $\sigma_1$ $\sigma_1$

Каковы сравнительные преимущества / недостатки каждого метода?
Существуют ли разные варианты использования, когда один затмевает другой?

У меня также есть интуитивная мысль, что на дискретных выборках LoG и Ricker вырождаются в одну и ту же операцию, поскольку может быть реализовано как ядро . $\nabla^2$

[\begin{matrix} - 1, & 2, & - 1 \end{matrix}] or [\begin{matrix} 0 & - 1 & 0 \\ - 1 & 4 & - 1 \\ 0 & - 1 & 0 \end{matrix}] for 2D images

$\begin{bmatrix}-1,& 2,& -1\end{bmatrix}\quad\text{or}\quad\begin{bmatrix} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{bmatrix}\quad\text{for 2D images}$

Применение этой операции к гауссову приводит к вейвлету Рикера / Хэта. Кроме того, поскольку LoG и DoG связаны с уравнением диффузии тепла, я считаю, что смогу добиться того, чтобы оба соответствовали достаточному изменению параметров.

(Я все еще промокаю от этого материала, чтобы смело исправлять / уточнять все это!)

image-processing filters wavelet opencv multi-scale-analysis DeusXMachina
источник

Ответы:

Лаплас гауссовский

Лапласа Гаусса (LoG) изображения можно записать как $f$

\nabla^{2} (f * g) = f * \nabla^{2} g

$\nabla^2 (f * g) = f * \nabla^2 g$

с гауссово ядро и свертка. Таким образом, Лаплас изображения, сглаженного ядром Гаусса, идентичен изображению, свернутому с Лапласом ядра Гаусса. Эта свертка может быть дополнительно расширена, в 2D случае, как $g$ $*$

f * \nabla^{2} g = f * (\frac{\partial^{2}}{\partial x^{2}} g + \frac{\partial^{2}}{\partial y^{2}} g) = f * \frac{\partial^{2}}{\partial x^{2}} g + f * \frac{\partial^{2}}{\partial y^{2}} g

$f * \nabla^2 g = f * \left(\frac{\partial^2}{\partial x^2}g+\frac{\partial^2}{\partial y^2}g\right) = f * \frac{\partial^2}{\partial x^2}g + f * \frac{\partial^2}{\partial y^2}g$

Таким образом, его можно вычислить как сложение двух сверток входного изображения со вторыми производными ядра Гаусса (в 3D это 3 свертки и т. Д.). Это интересно, поскольку ядро Гаусса отделимо, как и его производные. Это,

f (x, y) * g (x, y) = f (x, y) * (g (x) * g (y)) = (f (x, y) * g (x)) * g (y)

$f(x,y) * g(x,y) = f(x,y) * \left( g(x) * g(y) \right) = \left( f(x,y) * g(x) \right) * g(y)$

Это означает, что вместо двумерной свертки мы можем вычислить одно и то же с использованием двух одномерных сверток. Это экономит много вычислений. Для самого маленького мыслимого ядра Гаусса у вас будет 5 выборок по каждому измерению. 2D свертка требует 25 умножений и сложений, две 1D свертки требуют 10. Чем больше ядро или чем больше размер изображения, тем значительнее эти вычислительные сбережения.

Таким образом, LoG может быть вычислен с использованием четырех 1D сверток. Однако само ядро LoG неразделимо.

Существует приближение, когда изображение сначала сворачивается с ядром Гаусса, а затем реализуется с использованием конечных разностей, что приводит к ядру 3x3 с -4 в середине и 1 в его четырех соседних ребрах. $\nabla^2$

Вейвлет Ricker или оператор мексиканской шляпы идентичны LoG, вплоть до масштабирования и нормализации .

Разница гауссов

Разность гауссианов (DoG) изображения может быть записана как $f$

f * g_{(1)} - f * g_{(2)} = f * (g_{(1)} - g_{(2)})

$f * g_{(1)} - f * g_{(2)} = f * (g_{(1)} - g_{(2)})$

Таким образом, как и в случае с LoG, DoG можно рассматривать как одну неразделимую двумерную свертку или сумму (в данном случае разность) двух отделимых сверток. С этой точки зрения, похоже, что в использовании DoG по сравнению с LoG нет вычислительных преимуществ. Однако DoG является перестраиваемым полосовым фильтром, LoG не настраивается таким же образом, и его следует рассматривать как оператор производной. DoG также естественным образом появляется в масштабном пространстве, где изображение фильтруется во многих масштабах (гауссианы с разными сигмами), разница между последующими масштабами - это DoG.

Существует ядро DoG, которое является отделимым, что вдвое снижает вычислительные затраты, хотя это приближение не является изотропным, что приводит к зависимости фильтра от вращения.

Однажды я показал (для себя) эквивалентность LoG и DoG для DoG, где разница в сигме между двумя гауссовыми ядрами бесконечно мала (вплоть до масштабирования). У меня нет записей об этом, но это было нетрудно показать.

Другие формы вычисления этих фильтров

В ответе Лорана упоминается рекурсивная фильтрация, а в ОП - вычисления в области Фурье. Эти концепции применимы как к LoG, так и к DoG.

Гауссовы и его производные могут быть вычислены с использованием рекурсивного фильтра причинной и анти-причинного. Таким образом, все упомянутые выше одномерные свертки могут быть применены в постоянное время к сигме. Обратите внимание, что это эффективно только для больших сигм.

Аналогичным образом, любая свертка может быть вычислена в области Фурье, поэтому и двумерные ядра DoG и LoG могут быть преобразованы в область Фурье (или, скорее, вычислены там) и применены умножением.

В заключении

Нет существенных различий в вычислительной сложности этих двух подходов. Мне еще предстоит найти вескую причину для аппроксимации LoG с помощью DoG.

Крис Луенго
источник

Это фантастический ответ! Я собираюсь обновить это как новый ответ, не то , чтобы ответ Лорана был неправильным или неполным, но вы нашли время, чтобы добавить отличную вторую перспективу к ответу на вопрос годовалого ребенка.

DeusXMachina

DoG и LoG встречаются в масштабе «коры»

Лоран Дюваль

Вейвлет Рикера, (изотропный) вейвлет Марра, мексиканская шляпа или лапласиан гауссианов принадлежат к одному и тому же понятию: непрерывные допустимые вейвлеты (удовлетворяющие определенным условиям). Традиционно вейвлет Рикера является 1D версией. Вейвлет Марра или мексиканская шляпа - это имена, данные в контексте декомпозиции двумерных изображений, вы можете рассмотреть, например, Раздел 2.2 Панорамы о многомасштабных геометрических представлениях, переплетающих пространственную, направленную и частотную селективность , Обработка сигналов, 2011, Л. Жак и др. и др. Лапласиан Гаусса является многомерным обобщением.

Однако на практике люди принимают разные типы дискретизации на разных уровнях.

Я склонен полагать (если не дать более подробную информацию), что ядро с дискретным градиентом примененное к гауссову, - это не исходный Рикер, а упрощение, объясняющее тонкие различия в графике. Я заинтересован в ссылках. Действительно, вы можете иметь как минимум две естественные дискретизации оператора Лапласа (4- и 8-соседей): $3\times 3$ $3\times 3$

(\begin{matrix} 0 & - 1 & 0 \\ - 1 & 4 & - 1 \\ 0 & - 1 & 0 \end{matrix})

$\begin{pmatrix} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \\ \end{pmatrix}$

или Есть и другие приближения, например, с ядро , или другие аватары лапласиана / лапласиана гауссова .

(\begin{matrix} - 1 & - 1 & - 1 \\ - 1 & 8 & - 1 \\ - 1 & - 1 & - 1 \end{matrix})

$\begin{pmatrix} -1 & -1 & -1 \\ -1 & 8 & -1 \\ -1 & -1 & -1 \\ \end{pmatrix}$

5 \times 5

$5\times 5$

При правильном выборе их коэффициентов дисперсии и (обычно около 1,6) разность гауссианов обеспечивает хорошее сепарабельное приближение к LoG (см., Например, Быструю фильтрацию почти Гаусса , P. Kovesi). Эти гауссианы, в свою очередь, могут быть аппроксимированы рекурсивными приближенными гауссианами . $\sigma_1$ $\sigma_2$

Но были использованы другие соотношения, например, в некоторых лапласовых пирамидах, которые превращают DoG в более общие полосовые фильтры или детекторы краев.

Последняя ссылка: Сопоставление изображений с использованием обобщенных точек интереса в масштабе шкалы , Т. Линдеберг, 2015.

Лоран Дюваль
источник

Очень поучительно, спасибо! Таким образом, из Fast Gaussian Smoothing звучит так, что DoG имеет вычислительные преимущества в том смысле, что его можно выполнять непосредственно в пространственной области, поэтому я предполагаю, например, обработку сигналов на кристалле для CCD / интегрированного компьютерного зрения. Кроме того, Панорама выглядит как фантастическое чтение в целом, спасибо!

DeusXMachina

С быстрыми приближениями вы действительно можете выполнять ряд операций независимо от масштаба

Лоран Дюваль

Откуда берется соотношение 1,6? Если вы напишете математику, вы увидите, что существует точная эквивалентность между второй производной гауссиана и разностью гауссов с бесконечно малой разницей в сигме (с точностью до масштабирования).

Крис Луенго

Из приложения B к Marr and Hildreth, 1980, они называют это «наилучшим инженерным приближением» с компромиссом между пропускной способностью и чувствительностью, основанным на кривых качества, при изменении отношения ширины. В прошлом я встречал некоторые работы в Делфте с таким же именем. Стечение обстоятельств?

Лоран Дюваль

@ LaurentDuval: я защитил докторскую диссертацию в Делфте. Там нет других людей с моим именем, AFAIK. Я вижу, как вы можете получить (субъективный) оптимум на основе чувствительности и пропускной способности. Если отношение слишком мало, отклик слишком низкий, вероятно, больше зависит от шума дискретизации, чем от чего-либо еще; если соотношение слишком высокое, это не интересный фильтр. Имеет смысл. Спасибо!

Cris Luengo