Was ist der Unterschied zwischen dem Unterschied von Gauß, Laplace von Gauß und mexikanischem Hut Wavelet?

Im Lebenslauf werden drei Techniken verwendet, die einander sehr ähnlich zu sein scheinen, jedoch subtile Unterschiede aufweisen:

Laplace von Gauß: $\nabla^2\left[g(x,y,t)\ast f(x,y)\right]$
Unterschied der Gaußschen: $\left[g_1(x,y,t)\ast f(x,y)\right] - \left[g_2(x,y,t)\ast f(x,y)\right]$
Faltung mit Ricker-Wavelet : $\textrm{Ricker}(x,y,t)\ast f(x,y)$

So wie ich es derzeit verstehe: DoG ist eine Annäherung an LoG. Beide werden bei der Blob-Erkennung verwendet und arbeiten im Wesentlichen als Bandpassfilter. Die Faltung mit einem mexikanischen Hat / Ricker-Wavelet scheint fast den gleichen Effekt zu erzielen.

Ich habe alle drei Techniken auf ein Impulssignal angewendet (mit der erforderlichen Skalierung, um die Größen ähnlich zu erhalten), und die Ergebnisse sind verdammt nahe. Tatsächlich sehen LoG und Ricker fast identisch aus. Der einzige wirkliche Unterschied, den ich bemerkt habe, ist, dass ich bei DoG 2 freie Parameter ( und ) gegen 1 für LoG und Ricker einstellen musste. Ich fand auch, dass das Wavelet das einfachste / schnellste war, da es mit einer einzelnen Faltung (durch Multiplikation im Fourierraum mit FT eines Kernels) gegen 2 für DoG und einer Faltung plus einem Laplace für LoG durchgeführt werden konnte. $\sigma_1$ $\sigma_1$

Was sind die komparativen Vor- und Nachteile jeder Technik?
Gibt es verschiedene Anwendungsfälle, in denen einer den anderen überstrahlt?

Ich habe auch den intuitiven Gedanken, dass LoG und Ricker bei diskreten Samples zu derselben Operation degenerieren, da als Kernel implementiert werden kann. . $\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}$

Wenn diese Operation auf einen Gaußschen angewendet wird, entsteht das Ricker / Hat-Wavelet. Da LoG und DoG mit der Wärmediffusionsgleichung zusammenhängen, gehe ich davon aus, dass ich beide dazu bringen könnte, mit genügend Parameterfummelei übereinzustimmen.

(Ich mache immer noch meine Füße nass mit diesem Zeug, um mich frei zu fühlen, irgendetwas davon zu korrigieren / zu klären!)

image-processing filters wavelet opencv multi-scale-analysis DeusXMachina
quelle

Antworten:

Laplace von Gauß

Der Laplace of Gaussian (LoG) von Bild kann wie folgt geschrieben werden $f$

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

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

mit der Gaußsche Kern und die Faltung. Das heißt, der Laplace des durch einen Gaußschen Kernel geglätteten Bildes ist identisch mit dem mit dem Laplace des Gaußschen Kernels gefalteten Bild. Diese Faltung kann im 2D-Fall als weiter ausgebaut werden $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$

Somit ist es möglich, es als Addition von zwei Windungen des Eingabebildes mit zweiten Ableitungen des Gaußschen Kernels zu berechnen (in 3D sind dies 3 Windungen usw.). Dies ist interessant, da der Gaußsche Kernel ebenso wie seine Ableitungen trennbar sind. Das ist,

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)$

Dies bedeutet, dass wir anstelle einer 2D-Faltung dasselbe mit zwei 1D-Faltungen berechnen können. Dies spart viele Berechnungen. Für den kleinsten denkbaren Gaußschen Kernel hätten Sie 5 Samples entlang jeder Dimension. Eine 2D-Faltung erfordert 25 Multiplikationen und Additionen, zwei 1D-Faltungen erfordern 10. Je größer der Kernel oder je mehr Dimensionen im Bild, desto bedeutender sind diese Recheneinsparungen.

Somit kann der LoG unter Verwendung von vier 1D-Faltungen berechnet werden. Der LoG-Kernel selbst ist jedoch nicht trennbar.

Es gibt eine Näherung, bei der das Bild zuerst mit einem Gaußschen Kernel gefaltet wird und dann unter Verwendung endlicher Differenzen implementiert wird, was zum 3x3-Kernel mit -4 in der Mitte und 1 in seinen vier Randnachbarn führt. $\nabla^2$

Das Ricker-Wavelet oder der mexikanische Hutoperator sind bis zur Skalierung und Normalisierung mit dem LoG identisch .

Unterschied der Gaußschen

Die Differenz der Gaußschen (DoG) von Bild kann wie folgt geschrieben werden $f$

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

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

Genau wie beim LoG kann das DoG als einzelne nicht trennbare 2D-Faltung oder als Summe (in diesem Fall Differenz) zweier trennbarer Faltungen angesehen werden. Wenn man es so sieht, sieht es so aus, als gäbe es keinen Rechenvorteil bei der Verwendung des DoG gegenüber dem LoG. Das DoG ist jedoch ein abstimmbares Bandpassfilter, das LoG ist nicht auf die gleiche Weise abstimmbar und sollte als der abgeleitete Operator angesehen werden, der es ist. Das DoG erscheint natürlich auch in der Skalenraumeinstellung, in der das Bild in vielen Skalen (Gaußschen mit unterschiedlichen Sigmen) gefiltert wird. Der Unterschied zwischen nachfolgenden Skalen ist ein DoG.

Es gibt eine trennbare Annäherung an den DoG-Kernel, die den Rechenaufwand halbiert, obwohl diese Annäherung nicht isotrop ist, was zu einer Rotationsabhängigkeit des Filters führt.

Ich habe einmal (für mich) die Äquivalenz von LoG und DoG für ein DoG gezeigt, bei dem der Sigma-Unterschied zwischen den beiden Gaußschen Kernen unendlich klein ist (bis zur Skalierung). Ich habe keine Aufzeichnungen darüber, aber es war nicht schwer zu zeigen.

Andere Formen der Berechnung dieser Filter

Laurents Antwort erwähnt die rekursive Filterung, und das OP erwähnt die Berechnung im Fourier-Bereich. Diese Konzepte gelten sowohl für das LoG als auch für das DoG.

Der Gaußsche und seine Ableitungen können unter Verwendung eines kausalen und antikausalen IIR-Filters berechnet werden. So können alle oben erwähnten 1D-Faltungen in konstanter Zeit für das Sigma angewendet werden. Beachten Sie, dass dies nur bei größeren Sigmen effizient ist.

Ebenso kann jede Faltung in der Fourier-Domäne berechnet werden, so dass sowohl der DoG- als auch der LoG-2D-Kern in die Fourier-Domäne transformiert (oder vielmehr dort berechnet) und durch Multiplikation angewendet werden können.

Abschließend

Es gibt keine signifikanten Unterschiede in der rechnerischen Komplexität dieser beiden Ansätze. Ich habe noch keinen guten Grund gefunden, das LoG mithilfe des DoG zu approximieren.

Cris Luengo
quelle

Das ist eine fantastische Antwort! Ich werde dies als neue Antwort aktualisieren, nicht dass Laurents Antwort falsch oder unvollständig ist, aber Sie haben sich die Zeit genommen, einer einjährigen beantworteten Frage eine großartige zweite Perspektive hinzuzufügen.

DeusXMachina

DoG und LoG treffen sich auf der "Rinden"

Laurent Duval

Das Ricker-Wavelet, das (isotrope) Marr-Wavelet, der mexikanische Hut oder der Laplace-Gaußsche gehören zum selben Konzept: kontinuierliche zulässige Wavelets (die bestimmte Bedingungen erfüllen). Traditionell ist das Ricker Wavelet die 1D-Version. Das Marr-Wavelet oder der mexikanische Hut sind Namen, die im Zusammenhang mit 2D-Bildzerlegungen vergeben werden. Sie können beispielsweise Abschnitt 2.2 eines Panoramas über mehrskalige geometrische Darstellungen betrachten, die räumliche, gerichtete und Frequenzselektivität miteinander verflechten , Signal Processing, 2011, L. Jacques et al. Der Laplace-Wert von Gauß ist die mehrdimensionale Verallgemeinerung.

In der Praxis akzeptieren Menschen jedoch verschiedene Arten von Diskretisierungen auf verschiedenen Ebenen.

Ich neige dazu zu glauben (sofern nicht näher angegeben), dass ein diskreter Gradientenkern, der auf einen Gaußschen angewendet wird, nicht der ursprüngliche Ricker ist, sondern eine Vereinfachung, die subtile Unterschiede in der Grafik erklärt. Ich interessiere mich für Referenzen. In der Tat können Sie mindestens zwei natürliche Diskretisierungen des Laplace-Operators (4- und 8-Nachbarn) haben: $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}$

oder Es gibt auch andere Näherungen, zum Beispiel mit a Kernel oder andere Avatare des Laplace / Laplace von Gauß .

(\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$

Mit einer richtigen Wahl in ihren Varianzverhältnissen und (normalerweise um 1,6) liefert eine Differenz der Gaußschen eine schöne trennbare Annäherung an das LoG (siehe zum Beispiel Fast Almost-Gaussian Filtering , P. Kovesi). Diese Gaußschen können wiederum durch rekursive Näherungsgaußsche approximiert werden . $\sigma_1$ $\sigma_2$

Es wurden jedoch andere Verhältnisse verwendet, beispielsweise in einigen Laplace-Pyramiden, die DoG mehr in allgemeinere Bandpassfilter oder Kantendetektoren verwandeln.

Letzte Referenz: Bildanpassung unter Verwendung verallgemeinerter Scale-Space-Interessenpunkte , T. Lindeberg, 2015.

Laurent Duval
quelle

Sehr aufschlussreich, danke! Aus Fast Gaussian Smoothing geht hervor, dass DoG Rechenvorteile hat, da es direkt im räumlichen Bereich durchgeführt werden kann. Daher stelle ich mir beispielsweise eine On-Chip-Signalverarbeitung für CCD / integrierte Computer Vision vor. Außerdem sieht A Panorama insgesamt wie eine fantastische Lektüre aus, danke!

DeusXMachina

Mit schnellen Annäherungen können Sie in der Tat eine Reihe von Operationen unabhängig von der Skala

Laurent Duval

Woher kommt das Verhältnis 1.6? Wenn Sie die Mathematik aufschreiben, können Sie sehen, dass es eine genaue Äquivalenz zwischen der zweiten Ableitung des Gaußschen und dem Unterschied des Gaußschen mit einem infinitesimalen Unterschied im Sigma gibt (bis zur Skalierung).

Cris Luengo

Von Marr und Hildreth, 1980, Anhang B, nennen sie es eine "beste technische Näherung" mit einem Kompromiss zwischen Bandbreite und Empfindlichkeit, basierend auf Leistungskurven, während das Breitenverhältnis variiert wird. Ich habe in der Vergangenheit einige Werke von gleichnamigen Menschen in Delft getroffen. Zufall?

Laurent Duval

@LaurentDuval: Ich habe in Delft promoviert. Keine anderen Leute dort mit meinem Namen, AFAIK. Ich kann sehen, wie Sie ein (subjektives) Optimum basierend auf Empfindlichkeit und Bandbreite ableiten können. Wenn das Verhältnis zu klein ist, ist die Reaktion zu niedrig, was wahrscheinlich mehr vom Diskretisierungsrauschen als von irgendetwas anderem abhängt. Wenn das Verhältnis zu hoch ist, ist es kein interessanter Filter. Macht Sinn. Vielen Dank!

Cris Luengo