¿Cómo funciona realmente el desplazamiento de imágenes de subpíxeles con DFT?

12

Estoy tratando de evaluar la calidad de varios métodos de interpolación de imágenes para una aplicación que implica generar imágenes desplazadas en subpíxeles. Pensé que podría comparar los resultados de un desplazamiento de subpíxeles usando todas estas variantes de interpolación con alguna imagen perfectamente desplazada, pero probablemente no sea posible obtenerla (¿cuál sería la necesidad de interpolación entonces?).

Estaba pensando en usar el desplazamiento DFT + en el dominio de la frecuencia, y no estoy seguro de cómo funciona realmente en comparación con la interpolación explícita de la imagen (usando bilineal, bicúbico, etc.). Estoy seguro de que no puede generar una imagen perfectamente cambiada , pero no puedo señalarlo. ¿El desplazamiento de subpíxeles con DFT es equivalente a aplicar interpolación y, de ser así, cuál? ¿Cuál es el sesgo de los valores de píxeles en las imágenes obtenidas con este método? ¡Gracias!

EDITAR: Después de reflexionar sobre el asunto, pensé que dado que la FFT es una aproximación (aún más la DFT) de la función original en términos de armónicos (funciones sinusoidales), equivaldría a algún tipo de interpolación trigonométrica. Recuerdo una fórmula de "interpolación de la serie de Fourier" para datos discretos que era una interpolación trigonométrica, pero no estoy seguro de si está conectada.

neuviemeporte
fuente
La transformación rápida de Fourier (FFT) es un algoritmo para la transformación discreta de Fourier. El DFT no es una aproximación de la función original en términos de armónicos, sino más bien una proyección de una señal sobre una base ortogonal exponencial compleja.
Bryan
Bien, pero la señal en sí misma es una aproximación muestreada y cuantificada de alguna distribución de intensidad, y el DFT es limitado con respecto al contenido armónico en comparación con esa distribución teórica. Puede recuperar la señal exacta de IDFT, pero habrá algún sesgo si hace algo (como cambiar) antes de devolverlo a IDFT. ¿O me estoy perdiendo algo?
neuviemeporte
El DFT realmente toma entradas discretizadas, pero no se limita a entradas cuantificadas. Lo que es la señal no importa. Como ha señalado, puede recuperar la señal exacta. Sin embargo, no estoy seguro de lo que quieres decir con "desplazamiento". Las propiedades del desplazamiento en el dominio de la frecuencia son bien conocidas (traducción de frecuencia compleja en el dominio del tiempo). Si su deseo es cambiar en el dominio del "tiempo", entonces debe pensar en el doble DFT de eso.
Bryan
1
Quiero decir que si realizo alguna operación en el DFT de una señal (como en mi caso - desplazamiento de subpíxeles de una imagen en el "dominio de píxeles" utilizando el teorema de desplazamiento de Fourier), el IDFT devolverá resultados interpolados como se explica por @ hotpaw2's responder. Esta interpolación es imperfecta porque la señal no está limitada en banda y la propia DFT se calculó a partir de un conjunto finito de muestras cuantificadas (0-255).
neuviemeporte

Respuestas:

4

Un DFT / FFT, más relleno de cero agregado en el dominio de frecuencia, luego un IDFT / IFFT más largo, devuelve puntos interpolados. Estos puntos se interpolarán utilizando un núcleo Sinc periódico, que es una interpolación perfecta para los datos originales que están estrictamente limitados a menos de la mitad de la frecuencia de muestreo original. Sin embargo, los datos actuarán como si estuvieran envueltos de forma circular, lo que puede producir resultados extraños en los bordes de algunas imágenes. Por lo tanto, es posible que desee rellenar los bordes de la fuente original con un buen relleno o color de encuadre antes de la interpolación.

Si sube la muestra en 2X (rellena con cero el FFT para duplicar la longitud antes del IFFT), entonces puede hacer un desplazamiento de medio píxel utilizando los puntos interpolados. 3X para un tercer desplazamiento de píxeles, etc. Para el desplazamiento, puede tirar los puntos originales más cualquier exceso de puntos interpolados para obtener el tamaño deseado.

hotpaw2
fuente
55
@ hotpaw2: el núcleo de interpolación para el DFT no es un sinc () de extensión infinita, de hecho, el DFT es una transformación discreta y finita. La interpolación por el DFT es equivalente a la convolución con el núcleo Dirichlet, también llamado sinc periódico () por algunos autores: en.wikipedia.org/wiki/Dirichlet_kernel
Arrigo
@Arrigo: De acuerdo. Respuesta editada para arreglar.
hotpaw2
@ hotpaw2: cuando llevo el FFT al doble del tamaño, el IFFT producirá una reconstrucción del doble del tamaño. ¿No está seguro de qué hacer con el excedente? Gracias
neuviemeporte
Tire los puntos sobrantes que no necesita. En una muestra ascendente 2X, todas las demás se desplazan, alternando con los puntos originales reconstruidos. En una muestra ascendente 3X, obtienes 2 puntos desplazados (por 1/3 y por 2/3) alternando con los originales. Etc. Cuanto más muestras, más tiras.
hotpaw2
7

Hay varias ideas clave que necesita para comprender cómo DFT le permite cambiar una imagen.

Primero, el teorio de Fourier: probablemente sea más fácil mirar primero el caso continuo (es decir, analógico). Imagine que tiene alguna función, llámela g (t). Para simplificar, digamos que g (t) es una grabación de audio analógica, por lo que es una función unidimensional, que es continua y representa la presión instantánea en función del tiempo.

Ahora, g (t) es una forma de representar nuestra grabación de audio. Otro es G (f). G (f) es la transformada de Fourier de g (t). Entonces, G (f) == FT (g (t)). G (f) tiene la misma información que g (t), pero representa esa información en el dominio de la frecuencia en lugar del dominio del tiempo. Hay algunos detalles quisquillosos sobre las transformadas de Fourier, que no mencionaré.

Puede pensar en G (f) como la "distribución de frecuencias" contenida en g (t). Entonces, si g (t) es una onda sinusoidal (es decir, un tono puro), entonces G (f) será cero en todas partes, excepto en la frecuencia de ese tono. Este es probablemente un buen punto para mencionar que G (f) es, en general, una función compleja, es decir, que devuelve números complejos, que se puede pensar que tienen un componente real e imaginario o una magnitud y fase.

δ(w)δ

Ok, ahora tenemos FT's continuos en nuestro haber.

Aquí está la segunda idea: una Transformada de Fourier discreta es una Transformada de Fourier como una señal muestreada es una señal analógica. En este caso, el "discreto" se refiere a la cuantificación del dominio de la función (tiempo o frecuencia), no su rango. (La señal digital muestreada que obtiene de su tarjeta de sonido se cuantifica tanto en el dominio como en el rango).

El flujo de bytes digital que obtiene de su tarjeta de sonido contiene "muestras" de la señal original continua (analógica) del micrófono. Si tomamos el DFT de nuestra muestra g (t), todavía obtenemos una G (f). G (f), recuerde, es solo una forma diferente de representar la información contenida en g (t). Si obedecemos el teorio de Nyquist , la señal muestreada g (t) contiene toda la "inteligencia" de la señal continua original, por lo que nuestra discreta G (f) debe contener toda la información de nuestra señal continua original. Entre paréntesis, G (f) sigue siendo una función compleja.

Aquí es donde entra en juego la magia del desplazamiento de subpíxeles, pero en este caso voy a escribir sobre cambiar la señal de audio a tiempo en menos de una muestra, ya que es lo mismo.

eiπ2

Eso significa que podemos cambiar nuestra grabación de audio a tiempo (en cualquier cantidad que elijamos, incluida una fracción del tiempo de muestra) simplemente modificando la fase de G (t). En realidad, esa declaración es quizás demasiado informal. Para una señal muestreada no cuantificada, la fase se puede ajustar arbitrariamente (esto es parte de la razón por la que hice la distinción entre la cuantificación del dominio y el rango anterior). Sin embargo, para una señal muestreada cuantificada (nuestro flujo de bytes de audio, por ejemplo), el tamaño del paso de cuantización (es decir, el número de bits) determina la resolución con la que podemos ajustar la fase. Cuando invertimos la Transformada de Fourier G (f) (o la DIFT, para esta señal muestreada), el nuevo conjunto de muestras g '(t) = DIFT (G (F)) se desplazará en el tiempo por la cantidad que escojamos.

Aplicar esto a sus píxeles simplemente significa usar un FT bidimensional en lugar del FT unidimensional discutido aquí.

nick g
fuente