Qual é a diferença entre a diferença de Gaussian, Laplace de Gaussian e Mexican Hat Wavelet?

10

Existem três técnicas usadas no CV que parecem muito semelhantes entre si, mas com diferenças sutis:

  • Laplaciano de Gaussiano:2[g(x,y,t)f(x,y)]
  • Diferença de Gaussianos:[g1 1(x,y,t)f(x,y)]-[g2(x,y,t)f(x,y)]
  • Convolução com a wavelet de Ricker :Ricker(x,y,t)f(x,y)

Pelo que entendi atualmente: DoG é uma aproximação do LoG. Ambos são usados ​​na detecção de blob e atuam essencialmente como filtros de passagem de banda. A convolução com uma wavelet mexicana Hat / Ricker parece alcançar praticamente o mesmo efeito.

Eu apliquei todas as três técnicas a um sinal de pulso (com escala necessária para obter as magnitudes semelhantes) e os resultados são muito próximos. De fato, LoG e Ricker parecem quase idênticos. A única diferença real que notei é que com o DoG, eu tinha 2 parâmetros livres para ajustar ( e ) vs 1 para LoG e Ricker. Eu também achei que a wavelet era a mais fácil / mais rápida, pois isso poderia ser feito com uma única convolução (feita através da multiplicação no espaço de Fourier com FT de um kernel) vs 2 para o DoG e uma convolução mais um Laplaciano para o LoG. σ1 1σ1 1

Resultados da convolução de wavelets de Ricker, Laplaciano de Gaussiano e Diferença de Gaussiano

  • Quais são as vantagens / desvantagens comparativas de cada técnica?
  • Existem diferentes casos de uso em que um supera o outro?

Também tenho o pensamento intuitivo de que, em amostras discretas, LoG e Ricker degeneram para a mesma operação, pois pode ser implementado como o kernel .2

[-1 1,2,-1 1]ou[0 0-1 10 0-1 14-1 10 0-1 10 0]para imagens 2D

A aplicação dessa operação a um gaussiano dá origem à wavelet Ricker / Hat. Além disso, como LoG e DoG estão relacionados à equação de difusão de calor, eu acho que eu poderia fazer com que ambos correspondessem a parâmetros suficientes.

(Ainda estou molhando meus pés com essas coisas para me sentir livre para corrigir / esclarecer isso!)

DeusXMachina
fonte

Respostas:

6

Laplace of Gaussian

f

2(fg)=f2g

g

f2g=f(2x2g+2y2g)=f2x2g+f2y2g

Assim, é possível computá-lo como a adição de duas convoluções da imagem de entrada com segundas derivadas do núcleo gaussiano (em 3D são 3 convoluções, etc.). Isso é interessante porque o núcleo gaussiano é separável, assim como seus derivados. Isso é,

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

o que significa que, em vez de uma convolução 2D, podemos calcular a mesma coisa usando duas convoluções 1D. Isso economiza muitos cálculos. Para o menor núcleo Gaussiano pensável, você teria 5 amostras ao longo de cada dimensão. Uma convolução 2D requer 25 multiplicações e adições, duas convoluções 1D exigem 10. Quanto maior o kernel, ou mais dimensões na imagem, mais significativas são essas economias computacionais.

Assim, o LoG pode ser calculado usando quatro convoluções 1D. O próprio kernel LoG, no entanto, não é separável.

2

A wavelet Ricker ou o operador de chapéu mexicano são idênticos ao LoG, até o dimensionamento e a normalização .

Diferença de Gaussians

f

fg(1 1)-fg(2)=f(g(1 1)-g(2))

Portanto, assim como no LoG, o DoG pode ser visto como uma única convolução 2D não separável ou a soma (diferença neste caso) de duas convoluções separáveis. Vendo desta maneira, parece que não há vantagem computacional em usar o DoG sobre o LoG. No entanto, o DoG é um filtro passante de banda ajustável, o LoG não é ajustável da mesma maneira e deve ser visto como o operador derivado que é. O DoG também aparece naturalmente na configuração do espaço de escala, onde a imagem é filtrada em várias escalas (gaussianas com sigmas diferentes), a diferença entre as escalas subsequentes é um DoG.

Existe uma aproximação ao kernel do DoG que é separável, reduzindo o custo computacional pela metade, embora essa aproximação não seja isotrópica, levando à dependência rotacional do filtro.

Uma vez mostrei (para mim) a equivalência entre LoG e DoG, para um DoG em que a diferença de sigma entre os dois núcleos gaussianos é infinitesimalmente pequena (até a escala). Não tenho registros disso, mas não foi difícil de mostrar.

Outras formas de calcular esses filtros

A resposta de Laurent menciona a filtragem recursiva e o OP menciona a computação no domínio de Fourier. Esses conceitos se aplicam ao LoG e ao DoG.

O Gaussiano e seus derivados podem ser calculados usando um filtro IIR causal e anti-causal. Portanto, todas as convoluções 1D mencionadas acima podem ser aplicadas em tempo constante, com base no sigma. Observe que isso só é eficiente para sigmas maiores.

Da mesma forma, qualquer convolução pode ser calculada no domínio de Fourier, de modo que os kernels DoG e LoG 2D podem ser transformados no domínio de Fourier (ou melhor, computados lá) e aplicados por multiplicação.

Em conclusão

Não há diferenças significativas na complexidade computacional dessas duas abordagens. Ainda não encontrei um bom motivo para aproximar o LoG usando o DoG.

Cris Luengo
fonte
Esta é uma resposta fantástica! Vou atualizar isso como a nova resposta, não que a resposta de Laurent esteja errada ou incompleta, mas você teve tempo para adicionar uma ótima segunda perspectiva a uma pergunta respondida de um ano de idade.
DeusXMachina 19/0318
2
DoG e LoG encontram-se na escala de "casca"
Laurent Duval
4

A wavelet Ricker, a wavelet Marr (isotrópica), o chapéu mexicano ou o Laplaciano de Gaussianos pertencem ao mesmo conceito: wavelets contínuas admissíveis (que satisfazem certas condições). Tradicionalmente, a wavelet Ricker é a versão 1D. A wavelet de Marr ou o chapéu mexicano são nomes dados no contexto de decomposições de imagem 2D. Você pode considerar, por exemplo, a Seção 2.2 de Um panorama sobre representações geométricas em várias escalas, entrelaçando a seletividade espacial, direcional e de frequência , Processamento de Sinais, 2011, L. Jacques et al. O Laplaciano de Gaussiano é a generalização multidimensional.

No entanto, na prática, as pessoas aceitam diferentes tipos de discretizações, em diferentes níveis.

3×33×3

(0 0-1 10 0-1 14-1 10 0-1 10 0)

(-1 1-1 1-1 1-1 18-1 1-1 1-1 1-1 1)
5×5 Laplaciano / Laplaciano de Gauss .

σ1 1σ2

Mas outras razões foram usadas, em algumas pirâmides do Laplaciano, por exemplo, que transformam o Dogg em filtros de passagem de banda ou detectores de borda mais genéricos.

Última referência: Correspondência de imagens usando pontos de interesse de escala e espaço generalizados , T. Lindeberg, 2015.

Laurent Duval
fonte
11
Muito esclarecedor, obrigado! Parece que, pelo Fast Gaussian Smoothing, o DoG tem vantagens computacionais, pois pode ser feito diretamente no domínio espacial, por isso imagino, por exemplo, processamento de sinal no chip para CCD / visão computacional integrada. Além disso, A Panorama parece uma leitura fantástica em geral, obrigado!
DeusXMachina 17/02
Com aproximações rápido, você pode de fato um número de operações independente da escala
Laurent Duval
11
De onde vem a proporção 1,6? Se você escrever a matemática, poderá ver que há uma equivalência exata entre a segunda derivada do gaussiano e a diferença do gaussiano com uma diferença infinitesimal do sigma (até a escala).
Cris Luengo
11
De Marr e Hildreth, apêndice B de 1980, eles chamam de "melhor aproximação de engenharia", com uma troca entre largura de banda e sensibilidade, com base em curvas de mérito e variando a proporção da largura. Conheci alguns trabalhos no passado de pessoas em Delft, com o mesmo nome. Coincidência?
Laurent Duval
11
@LaurentDuval: Eu fiz meu doutorado em Delft. Não há outras pessoas lá com o meu nome, AFAIK. Eu posso ver como você pode obter um ótimo (subjetivo) com base na sensibilidade e na largura de banda. Se a proporção for muito pequena, a resposta é muito baixa, provavelmente mais dependente do ruído de discretização do que qualquer outra coisa; se a proporção for muito alta, não é um filtro interessante. Faz sentido. Obrigado!
Cris Luengo