Quelle est la différence entre la différence de Gaussian, Laplace of Gaussian et Mexican Hat Wavelet?

Il existe trois techniques utilisées dans le CV qui semblent très similaires les unes aux autres, mais avec de subtiles différences:

Laplacien de gaussien: $\nabla^2\left[g(x,y,t)\ast f(x,y)\right]$
Différence des gaussiens: $\left[g_1(x,y,t)\ast f(x,y)\right] - \left[g_2(x,y,t)\ast f(x,y)\right]$
Convolution avec ondelette Ricker : $\textrm{Ricker}(x,y,t)\ast f(x,y)$

Si je comprends bien actuellement: DoG est une approximation de LoG. Les deux sont utilisés dans la détection d'objets blob et fonctionnent tous deux essentiellement comme des filtres passe-bande. La convolution avec une ondelette Mexican Hat / Ricker semble obtenir à peu près le même effet.

J'ai appliqué les trois techniques à un signal d'impulsion (avec une mise à l'échelle requise pour obtenir des amplitudes similaires) et les résultats sont sacrément proches. En fait, LoG et Ricker semblent presque identiques. La seule vraie différence que j'ai remarquée est avec DoG, j'avais 2 paramètres gratuits à régler ( et ) contre 1 pour LoG et Ricker. J'ai également trouvé que l'ondelette était la plus facile / la plus rapide, car cela pouvait être fait avec une seule convolution (effectuée via la multiplication dans l'espace de Fourier avec FT d'un noyau) vs 2 pour DoG, et une convolution plus un laplacien pour LoG. $\sigma_1$ $\sigma_1$

Quels sont les avantages / inconvénients comparatifs de chaque technique?
Existe-t-il différents cas d'utilisation où l'un surpasse l'autre?

J'ai également la pensée intuitive que sur des échantillons discrets, LoG et Ricker dégénèrent à la même opération, car peut être implémenté en tant que noyau . $\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}$

L'application de cette opération à une gaussienne donne naissance à l'ondelette Ricker / Hat. De plus, étant donné que LoG et DoG sont liés à l'équation de diffusion de la chaleur, je pense que je pourrais obtenir que les deux correspondent à suffisamment de paramètres.

(Je me mouille toujours les pieds avec ce truc pour me sentir libre de corriger / clarifier tout cela!)

image-processing filters wavelet opencv multi-scale-analysis DeusXMachina
la source

Réponses:

Laplace de Gaussian

Le Laplace de Gaussian (LoG) de l'image peut s'écrire $f$

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

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

avec le noyau gaussien et la convolution. Autrement dit, le Laplace de l'image lissée par un noyau gaussien est identique à l'image convolue avec le Laplace du noyau gaussien. Cette convolution peut être encore développée, dans le cas 2D, comme $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$

Ainsi, il est possible de le calculer comme l'addition de deux convolutions de l'image d'entrée avec des dérivées secondes du noyau gaussien (en 3D c'est 3 convolutions, etc.). Ceci est intéressant car le noyau gaussien est séparable, tout comme ses dérivés. C'est,

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

ce qui signifie qu'au lieu d'une convolution 2D, nous pouvons calculer la même chose en utilisant deux convolutions 1D. Cela permet d'économiser beaucoup de calculs. Pour le plus petit noyau gaussien imaginable, vous auriez 5 échantillons le long de chaque dimension. Une convolution 2D nécessite 25 multiplications et additions, deux convolutions 1D en nécessitent 10. Plus le noyau est grand ou plus il y a de dimensions dans l'image, plus ces économies de calcul sont importantes.

Ainsi, le LoG peut être calculé en utilisant quatre convolutions 1D. Cependant, le noyau LoG lui-même n'est pas séparable.

Il existe une approximation où l'image est d'abord convolutée avec un noyau gaussien, puis est implémenté en utilisant des différences finies, conduisant au noyau 3x3 avec -4 au milieu et 1 dans ses quatre voisins de bord. $\nabla^2$

L'opérateur ondelette Ricker ou chapeau mexicain est identique au LoG, jusqu'à la mise à l'échelle et la normalisation .

Différence des gaussiens

La différence de Gaussiens (DoG) de l'image peut être écrite comme $f$

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

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

Ainsi, tout comme avec le LoG, le DoG peut être considéré comme une seule convolution 2D non séparable ou la somme (différence dans ce cas) de deux convolutions séparables. Vu sous cet angle, il semble qu'il n'y ait aucun avantage informatique à utiliser le DoG par rapport au LoG. Cependant, le DoG est un filtre passe-bande accordable, le LoG n'est pas accordable de la même manière, et doit être considéré comme l'opérateur dérivé qu'il est. Le DoG apparaît également naturellement dans le paramètre échelle-espace, où l'image est filtrée à plusieurs échelles (Gaussiennes avec différents sigmas), la différence entre les échelles suivantes est un DoG.

Il existe une approximation du noyau DoG qui est séparable, ce qui réduit de moitié le coût de calcul, bien que cette approximation ne soit pas isotrope, conduisant à une dépendance en rotation du filtre.

J'ai montré une fois (pour moi) l'équivalence du LoG et du DoG, pour un DoG où la différence de sigma entre les deux noyaux gaussiens est infiniment petite (jusqu'à l'échelle). Je n'ai pas d'enregistrement de cela, mais ce n'était pas difficile à montrer.

Autres formes de calcul de ces filtres

La réponse de Laurent mentionne le filtrage récursif, et l'OP mentionne le calcul dans le domaine de Fourier. Ces concepts s'appliquent à la fois au LoG et au DoG.

Le gaussien et ses dérivés peuvent être calculés à l'aide d'un filtre IIR causal et anti-causal. Ainsi, toutes les convolutions 1D mentionnées ci-dessus peuvent être appliquées en temps constant par rapport au sigma. Notez que cela n'est efficace que pour les sigmas plus importants.

De même, toute convolution peut être calculée dans le domaine de Fourier, de sorte que les noyaux DoG et LoG 2D peuvent être transformés en domaine de Fourier (ou plutôt calculés à cet endroit) et appliqués par multiplication.

En conclusion

Il n'y a pas de différences significatives dans la complexité de calcul de ces deux approches. Je n'ai pas encore trouvé de bonne raison d'approcher le LoG en utilisant le DoG.

Cris Luengo
la source

C'est une réponse fantastique! Je vais mettre à jour cela en tant que nouvelle réponse, non pas que la réponse de Laurent soit fausse ou incomplète, mais vous avez pris le temps d'ajouter une excellente deuxième perspective à une question à laquelle vous avez répondu il y a un an.

DeusXMachina

Le DoG et le LoG se rencontrent sur l'échelle "bark"

Laurent Duval

L'ondelette Ricker, l'ondelette Marr (isotrope), le chapeau mexicain ou le laplacien des Gaussiens appartiennent au même concept: ondelettes admissibles continues (satisfaisant à certaines conditions). Traditionnellement, l'ondelette Ricker est la version 1D. L'ondelette de Marr ou le chapeau mexicain sont des noms donnés dans le contexte des décompositions d'images 2D, vous pouvez considérer par exemple la section 2.2 d' un panorama sur les représentations géométriques multi-échelles, entremêlant la sélectivité spatiale, directionnelle et fréquentielle , Signal Processing, 2011, L. Jacques et Al. Le laplacien du gaussien est la généralisation multidimensionnelle.

Cependant, dans la pratique, les gens acceptent différents types de discrétisation, à différents niveaux.

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

$\sigma_1$ $\sigma_2$

Mais d'autres ratios ont été utilisés, dans certaines pyramides laplaciennes par exemple, qui transforment davantage le DoG en filtres passe-bande ou détecteurs de bord plus génériques.

Dernière référence: Image Matching Using Generalized Scale-Space Interest Points , T. Lindeberg, 2015.

Laurent Duval
la source

Très instructif, merci! Il semble donc que le Fast Gaussian Smoothing ait des avantages de calcul dans la mesure où il peut être effectué directement dans le domaine spatial, donc j'envisage, par exemple, un traitement de signal sur puce pour CCD / vision par ordinateur intégrée. De plus, A Panorama ressemble à une lecture fantastique dans l'ensemble, merci!

DeusXMachina

Avec des approximations rapides, vous pouvez en effet effectuer un certain nombre d'opérations indépendamment de l'échelle

Laurent Duval

D'où vient le rapport 1,6? Si vous écrivez les mathématiques, vous pouvez voir qu'il existe une équivalence exacte entre la dérivée seconde du gaussien et la différence du gaussien avec une différence infinitésimale de sigma (jusqu'à l'échelle).

Cris Luengo

De Marr et Hildreth, 1980, annexe B, ils appellent cela une "meilleure approximation d'ingénierie", avec un compromis entre la bande passante et la sensibilité, basé sur des courbes de mérite tout en faisant varier le rapport de largeur. J'ai rencontré par le passé des oeuvres de gens de Delft, du même nom. Coïncidence?

Laurent Duval

@LaurentDuval: J'ai fait mon doctorat à Delft. Il n'y a personne d'autre avec mon nom, AFAIK. Je peux voir comment vous pourriez dériver un optimum (subjectif) basé sur la sensibilité et la bande passante. Si le rapport est trop petit, la réponse est trop faible, dépendant probablement plus du bruit de discrétisation qu'autre chose; si le rapport est trop élevé, ce n'est pas un filtre intéressant. Logique. Merci!

Cris Luengo