Como aplicar corretamente a FFT no denoising de imagem

8

Estou escrevendo programa (Qt widgets / c ++) para remover o ruído das imagens. Como método de denoising, selecionei o método de meios não locais . Este método tem uma qualidade incrível de imagens restauradas (é por isso que é o único método de denoising no OpenCV), mas tem um custo de computação enorme , então eu fiz muitas variantes modificadas desse método (algumas com multithreading, outras algorítmicas). Mas estou tendo problemas com o que envolve a FFT

Eu segui todas as etapas deste artigo (apenas uma página, 1430) e tudo funciona perfeitamente, exceto a parte FFT, existem apenas duas linhas sobre isso no jornal e não consigo entender, como usar fft

Esse problema me incomoda há meses, qualquer ajuda ou insight seria muito apreciado.

Versão resumida da pergunta: Como posso obter a soma da diferença quadrática de duas matrizes na imagem (a na parte superior e a no meio, os valores são cores) rapidamente? (O (n ^ 2) é um custo enorme, existem muitas operações desse tipo, acima dos estados, que podem ser feitas via FFT com O (n * log n) (diz que essas duas matrizes formam alguma convolução circular) )

insira a descrição da imagem aqui

Shf
fonte
O que você finalmente fez para calcular a FFT? Mesmo que a FFT seja pré-computada, a multiplicação por pontos e a adição de todos os elementos do patch levamO(|P|) hora em que |P|é o tamanho do patch. Como você superou isso?
curryage 28/10

Respostas:

5

O truque dentro do papel é o seguinte:

  1. O que você deseja calcular é iW|I(x+i)I(y+i)|2, Onde I é uma imagem x e y dois pixels barulhentos e i é um deslocamento 2D usado para definir um patch.
  2. A expansão da expressão produz: iI2(x+i)+iI2(y+i)2iI(x+i)I(y+i)=A+B2C.
  3. A e B são calculados usando uma imagem integral ao quadrado, ou seja, uma imagem integral da imagem original ao quadrado.
  4. C é a convolução entre os dois patches centrados no x e y. Assim, pode ser computado no domínio de Fourier, onde se torna uma multiplicação. Você obtém o valor deC calculando a transformação de Fourier do patch em torno x, o patch ao redor y, multiplicando por ponto esses resultados e obtendo a transformação de Fourier inversa do resultado da multiplicação.

A transformação de Fourier é obviamente uma transformação 2D, pois você está trabalhando com dados 2D. O que você obtém para um determinado patch é uma matriz 2D de valores complexos.

Notas Adicionais

Na minha opinião, este artigo não é a melhor estratégia de aceleração de NL-significa. As experiências que fiz em 2007/2008 mostram que a pré-seleção de patches é melhor (em termos de velocidade e qualidade dos resultados). Comecei a blogar sobre isso aqui , mas infelizmente estou procurando tempo para terminar as postagens.

Os documentos originais de NL significa mencionar implementações em blocos que podem ser interessantes. Existem basicamente duas maneiras de implementar meios NL:

  1. escrevendo um loop denoising para cada pixel da imagem
  2. escrevendo um loop denoising para cada patch e, em seguida, projete novamente os patches para formar uma imagem.

A primeira impolementação é a abordagem original, porque em 2005 as CPUs de memória e multicore eram caras. Por outro lado, eu escolhi o número 2 em hardware recente nos últimos 2 anos. Depende do tamanho típico da imagem e se você deseja calcular transformações de domínio como DFT / DCT (como no artigo proposto e no BM3D).

sansuiso
fonte
Muito obrigado pela sua resposta, é exatamente isso que eu precisava, tudo estava pronto e funcionando há muito tempo, exceto pelo 4º item dessa lista, mas agora está muito mais claro. Apesar de mais uma pergunta, se você não se importa: o que retornará a transformação de Fourier do patch x ou y? Matriz, vetor ou valor único? E o que é necessário para usar a transformação inversa? Porque estou pensando em pré-computar fft para cada pixel (patches centrados em torno dele) e escrever resultados em 2d array antes de denoising e depois usar essas matrizes para obter fft inverso, mas não sei se isso será suficiente para fft inverso
Shf 27/05
ah, e devo usar 2d fft ou traduzir patch para matriz 1d? a propósito, eu estava planejando escrever após esta implementação patchwise de qualquer maneira, obrigado por um conselho :) algo semelhante a isso também há muito tempo - ipol.im/pub/art/2011/bcm_nlm
Shf
Eu atualizei a resposta.
Sansuiso 28/05
ok, então eu posso pré-calcular a FFT para patches, centrada em todos os pixels antes da obtenção, embora isso consiga muita memória (m n size_of_patch size_of_patch sizeof (double)), mas quando eu contar pesos, ainda precisarei multiplicar por pontos 2 matrizes complexas e depois disso fazer FFT inverso na matriz 2d recebido, é ainda mais, em seguida, o (n ^ 2), se não estiver enganada
SHF
2
Boa resposta, mas como você está derivando isso Cé uma convolução? A forma como está escrito é um produto pontual, elemento por elemento. Onde está a convolução?
TheGrapeBeyond