Cómo aplicar correctamente FFT en la eliminación de ruido de imágenes

8

Estoy escribiendo un programa (Qt widgets / c ++) para eliminar el ruido de las imágenes. Como método de eliminación de ruido, seleccioné el método de medios no locales . Este método tiene una calidad increíble de imágenes restauradas (es por eso que es el único método de eliminación de ruido en OpenCV), pero tiene un costo de cálculo enorme , por lo que hice muchas variantes modificadas de este método (algunas con subprocesamiento múltiple, algunas algorítmicas). Pero tengo un problema con el que involucra FFT

Seguí todos los pasos de este artículo (solo una página, 1430) y todo funciona perfectamente, excepto la parte FFT, solo hay 2 líneas al respecto en el documento y no puedo entender, ¿CÓMO se debe usar fft?

Este problema me ha molestado durante meses, cualquier ayuda o idea sería muy apreciada.

Versión abreviada de la pregunta: ¿Cómo puedo obtener la diferencia cuadrada sumada de dos matrices en la imagen (la de arriba y la de en medio, los valores son colores) rápidamente? (O (n ^ 2) es un costo enorme, hay muchas operaciones de este tipo, según el documento anterior, que se puede hacer a través de FFT con O (n * log n) (dice que estas 2 matrices forman de algún modo convolución circular) )

ingrese la descripción de la imagen aquí

Shf
fuente
¿Qué finalmente terminaste haciendo para calcular FFT? Incluso si FFT está precalculado, la multiplicación por puntos y la adición de todos los elementos de parche requierenO(|P|) tiempo donde |P|es el tamaño del parche ¿Cómo superaste esto?
curryage

Respuestas:

5

El truco dentro del papel es el siguiente:

  1. Lo que quieres calcular es iW|I(x+i)I(y+i)|2, dónde I es una imagen x y y dos píxeles ruidosos y i es un desplazamiento 2D usado para definir un parche.
  2. Expandir la expresión produce: iI2(x+i)+iI2(y+i)2iI(x+i)I(y+i)=A+B2C.
  3. A y B se calculan utilizando una imagen integral al cuadrado, es decir, una imagen integral de la imagen original al cuadrado.
  4. C es la convolución entre los dos parches centrados en x y y. Por lo tanto, se puede calcular en el dominio de Fourier, donde se convierte en una multiplicación. Obtienes el valor deC calculando la transformación de Fourier del parche alrededor x, el parche alrededor y, multiplicando puntualmente estos resultados y tomando la transformada inversa de Fourier del resultado de la multiplicación.

La transformación de Fourier es obviamente una transformación 2D, ya que está trabajando con datos 2D. Lo que obtienes para un parche dado es una matriz 2D de valores complejos.

Notas adicionales

En mi opinión, este artículo no es la mejor estrategia de aceleración de NL-means. Los experimentos que realicé en 2007/2008 muestran que la preselección de parches es mejor (tanto en términos de velocidad como de calidad de los resultados). He comenzado a bloguear sobre esto aquí , pero desafortunadamente estoy buscando tiempo para terminar las publicaciones.

Los documentos originales de NL significa medios implementaciones en bloque que pueden ser interesantes. Existen fundamentalmente 2 formas de implementar NL-means:

  1. escribir un bucle de eliminación de ruido para cada píxel de la imagen
  2. escribir un bucle de eliminación de ruido para cada parche, luego proyectar hacia atrás los parches para formar una imagen.

La primera impolementación es el enfoque original, porque en 2005 la memoria y las CPU multinúcleo eran caras. Por otro lado, elegí el número 2 en hardware reciente en los últimos 2 años. Depende de su tamaño de imagen típico y si desea poder calcular transformaciones de dominio como DFT / DCT (como en el documento propuesto y en BM3D).

sansuiso
fuente
Muchas gracias por su respuesta, eso es exactamente lo que necesitaba, todo estaba listo y funcionando hace mucho tiempo, excepto el cuarto elemento de esa lista, pero ahora está mucho más claro. Aunque una pregunta más, si no le importa: ¿qué devolverá la transformada de Fourier del parche x o y? ¿Matriz, vector o valor único? ¿Y qué se requiere para usar la transformación inversa? Porque estoy pensando en precalcular fft para cada píxel (parches centrados alrededor de él) y escribir los resultados en la matriz 2d antes de eliminar el ruido y luego solo usar esas matrices para obtener fft inverso, pero no sé si esto será suficiente para fft inverso
Shf
ah, y ¿debería usar 2d fft o traducir el parche a 1d array? por cierto, estaba planeando escribir después de esta implementación en parches de todos modos, gracias por un consejo :) algo similar a esto también hace mucho tiempo- ipol.im/pub/art/2011/bcm_nlm
Shf
He actualizado la respuesta.
sansuiso
ok, así que puedo precalcular FFT para parches, centrado alrededor de cada píxel antes de donoizar, aunque tomará mucha memoria (m n size_of_patch size_of_patch sizeof (double)), pero cuando cuente los pesos, aún necesitaría puntualizar multiplicar 2 matrices complejas y después de hacer fft inverso en la matriz 2d recibida, es aún más que O (n ^ 2) si no me equivoco
Shf
2
Buena respuesta, pero ¿cómo estás derivando eso? Ces una convolución? La forma en que está escrito es un producto elemento por elemento. ¿Dónde está la convolución?
TheGrapeBeyond