Jaka jest różnica między różnicą falki Gaussa, Laplace'a Gaussa i meksykańskiego kapelusza Wavelet?

W CV zastosowano trzy techniki, które wydają się bardzo do siebie podobne, ale z subtelnymi różnicami:

Laplacian Gaussa: $\nabla^2\left[g(x,y,t)\ast f(x,y)\right]$
Różnica Gaussów: $\left[g_1(x,y,t)\ast f(x,y)\right] - \left[g_2(x,y,t)\ast f(x,y)\right]$
Splot za pomocą falki Rickera : $\textrm{Ricker}(x,y,t)\ast f(x,y)$

Jak rozumiem obecnie: DoG jest przybliżeniem LoG. Oba są używane w wykrywaniu kropel i oba działają zasadniczo jako filtry pasmowo-przepustowe. Wydaje się, że konwekcja z falą meksykańskiego kapelusza / rikera daje bardzo podobny efekt.

Zastosowałem wszystkie trzy techniki do sygnału impulsu (z wymaganym skalowaniem, aby uzyskać podobne wielkości), a wyniki są bardzo bliskie. W rzeczywistości LoG i Ricker wyglądają prawie identycznie. Jedyną prawdziwą różnicą, jaką zauważyłem, jest DoG, miałem 2 wolne parametry do dostrojenia ( i ) vs 1 dla LoG i Rickera. Odkryłem również, że falka jest najłatwiejsza / najszybsza, ponieważ można to zrobić za pomocą pojedynczego splotu (wykonanego przez pomnożenie w przestrzeni Fouriera za pomocą FT jądra) vs 2 dla DoG i splotu plus Laplaciana dla LoG. $\sigma_1$ $\sigma_1$

Jakie są zalety / wady każdej techniki?
Czy istnieją różne przypadki użycia, w których jeden przyćmiewa drugi?

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

Zastosowanie tej operacji do gaussa powoduje powstanie falki Ricker / Hat. Co więcej, ponieważ LoG i DoG są powiązane z równaniem dyfuzji ciepła, uważam, że mógłbym dopasować oba z wystarczającą ilością parametrów.

(Nadal mam mokre stopy z tego powodu, aby swobodnie je korygować / wyjaśniać!)

image-processing filters wavelet opencv multi-scale-analysis DeusXMachina
źródło

Odpowiedzi:

Laplace Gaussa

$f$

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

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

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

Można go zatem obliczyć jako dodanie dwóch zwojów obrazu wejściowego z drugimi pochodnymi jądra Gaussa (w 3D są to 3 zwoje itd.). Jest to interesujące, ponieważ jądro Gaussa można rozdzielić, podobnie jak jego pochodne. To jest,

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

co oznacza, że zamiast splotu 2D możemy obliczyć to samo za pomocą dwóch splotów 1D. Oszczędza to wiele obliczeń. Dla najmniejszego możliwego do wyobrażenia jądra Gaussa miałbyś 5 próbek wzdłuż każdego wymiaru. Splot 2D wymaga 25 zwielokrotnień i dodatków, dwa splot 1D wymagają 10. Im większe jądro lub im więcej wymiarów na obrazie, tym większe są te oszczędności obliczeniowe.

Zatem LoG można obliczyć przy użyciu czterech zwojów 1D. Jednak samego jądra LoG nie da się oddzielić.

$\nabla^2$ jest implementowany z wykorzystaniem różnic skończonych, co prowadzi do jądra 3x3 z -4 w środku i 1 w jego czterech sąsiadujących brzegach.

Operator falki Ricker lub kapelusz meksykański są identyczne jak LoG, aż do skalowania i normalizacji .

Różnica Gaussów

$f$

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

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

Tak więc, podobnie jak w przypadku LoG, DoG może być postrzegane jako pojedynczy nierozdzielny splot 2D lub suma (różnica w tym przypadku) dwóch oddzielnych splotów. Patrząc w ten sposób, wygląda na to, że korzystanie z DoG w porównaniu z LoG nie ma przewagi obliczeniowej. Jednak DoG jest przestrajalnym filtrem pasmowo-przepustowym, LoG nie jest strojony w ten sam sposób i powinien być postrzegany jako operator pochodnej. DoG pojawia się również naturalnie w ustawieniu przestrzeni skali, gdzie obraz jest filtrowany w wielu skalach (Gaussianie z różnymi sigmatami), różnica między kolejnymi skalami jest DoG.

Istnieje przybliżenie jądra DoG, które można oddzielić, co zmniejsza koszt obliczeń o połowę, chociaż to przybliżenie nie jest izotropowe, co prowadzi do zależności rotacyjnej filtra.

Kiedyś pokazałem (dla mnie) równoważność LoG i DoG, dla DoG, w którym różnica w sigma między dwoma ziarnami gaussowskimi jest nieskończenie mała (aż do skalowania). Nie mam zapisów na ten temat, ale nie było trudno to pokazać.

Inne formy obliczania tych filtrów

Odpowiedź Laurenta wspomina o filtrowaniu rekurencyjnym, a OP wspomina o obliczeniach w domenie Fouriera. Te koncepcje dotyczą zarówno LoG, jak i DoG.

Gaussa i jej pochodne mogą być obliczane przy użyciu przyczynowego i anty-przyczynowy filtra IIR. Tak więc wszystkie wyżej wymienione sploty 1D mogą być stosowane w stałym czasie przez sigma. Pamiętaj, że jest to skuteczne tylko w przypadku większych sigm.

Podobnie każdy splot można obliczyć w domenie Fouriera, więc zarówno jądra 2D DoG, jak i LoG 2D można przekształcić w domenę Fouriera (lub raczej tam obliczyć) i zastosować przez mnożenie.

Podsumowując

Nie ma istotnych różnic w złożoności obliczeniowej tych dwóch podejść. Muszę jeszcze znaleźć dobry powód, aby zbliżyć LoG za pomocą DoG.

Cris Luengo
źródło

To fantastyczna odpowiedź! Zamierzam zaktualizować to jako nową odpowiedź, nie dlatego, że odpowiedź Laurenta jest błędna lub niekompletna, ale poświęciłeś czas, aby dodać świetną drugą perspektywę do pytania, na które odpowiedział rok.

DeusXMachina

DoG i LoG spotykają się w skali „kory”

Laurent Duval,

Falka Rikera, (izotropowa) falka Marra, kapelusz meksykański lub Laplacian Gaussa należą do tej samej koncepcji: ciągłe dopuszczalne falki (spełniające określone warunki). Tradycyjnie falka Ricker jest wersją 1D. Falka Marra lub kapelusz meksykański to nazwy nadane w kontekście dekompozycji obrazów 2D, można rozważyć na przykład rozdział 2.2 Panoramy na wieloskalowych reprezentacjach geometrycznych, przeplatając selektywność przestrzenną, kierunkową i częstotliwościową , Signal Processing, 2011, L. Jacques et glin. Laplacian Gaussa to wielowymiarowe uogólnienie.

Jednak w praktyce ludzie akceptują różne rodzaje dyskretyzacji, na różnych poziomach.

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

Ale inne wskaźniki zostały zastosowane, na przykład w niektórych piramidach Laplacian, które zmieniają DoG w bardziej ogólne filtry pasmowe lub detektory krawędzi.

Ostatnie odniesienie: dopasowanie obrazu za pomocą uogólnionych punktów zainteresowania w skali i przestrzeni , T. Lindeberg, 2015.

Laurent Duval
źródło

Bardzo pouczające, dziękuję! Brzmi więc to jak z szybkiego wygładzania gaussowskiego, że DoG ma zalety obliczeniowe, ponieważ można to zrobić bezpośrednio w dziedzinie przestrzeni, więc wyobrażam sobie np. Przetwarzanie sygnału na chipie dla CCD / zintegrowanej wizji komputerowej. Również Panorama wygląda jak fantastycznym przeczytane ogólnej, dzięki!

DeusXMachina

Dzięki szybkim przybliżeniom możesz rzeczywiście wykonać wiele operacji niezależnie od skali

Laurent Duval

Skąd pochodzi współczynnik 1.6? Jeśli napiszesz matematykę, zobaczysz, że istnieje dokładna równoważność między drugą pochodną Gaussa a różnicą Gaussa z nieskończenie małą różnicą w sigmie (aż do skalowania).

Cris Luengo

Z Marr i Hildreth, 1980, załącznik B, nazywają to „najlepszym przybliżeniem inżynieryjnym”, z kompromisem między szerokością pasma a czułością, opartą na krzywych osiągów, zmieniając jednocześnie stosunek szerokości. W przeszłości spotkałem kilka prac ludzi w Delft o tej samej nazwie. Zbieg okoliczności?

Laurent Duval,

@LaurentDuval: Zrobiłem doktorat w Delft. Nie ma tam innych ludzi z moim imieniem, AFAIK. Widzę, jak można uzyskać (subiektywne) optimum w oparciu o czułość i szerokość pasma. Jeśli stosunek jest zbyt mały, odpowiedź jest zbyt niska, prawdopodobnie bardziej zależna od hałasu dyskretyzacyjnego niż cokolwiek innego; jeśli stosunek jest zbyt wysoki, nie jest to interesujący filtr. Ma sens. Dzięki!

Cris Luengo