Comment le décalage d'image sous-pixel à l'aide de DFT fonctionne-t-il vraiment?

12

J'essaie d'évaluer la qualité de plusieurs méthodes d'interpolation d'images pour une application qui implique la génération d'images décalées en sous-pixels. Je pensais pouvoir comparer les résultats d'un décalage de sous-pixel en utilisant toutes ces variantes d'interpolation avec une image parfaitement décalée, mais ce n'est probablement pas possible de l'obtenir (quel serait alors le besoin d'interpolation?).

Je pensais à utiliser le décalage DFT + dans le domaine fréquentiel, et je ne sais pas comment cela fonctionne réellement par rapport à une interpolation explicite de l'image (en utilisant bilinéaire, bicubique, etc ...). Je suis sûr que cela ne peut pas générer une image parfaitement décalée , mais je ne peux pas mettre le doigt dessus. Le décalage de sous-pixels avec DFT équivaut-il à appliquer une interpolation et si oui, lequel? Quel est le biais des valeurs des pixels dans les images obtenues à l'aide de cette méthode? Merci!

EDIT: Après avoir réfléchi à la question, je me suis dit que la FFT est une approximation (encore plus la DFT) de la fonction d'origine en termes d'harmoniques (fonctions sinus), que cela équivaudrait à une sorte d'interpolation trigonométrique. Je me souviens d'une formule "d'interpolation de la série de Fourier" pour les données discrètes qui était une interpolation trigonométrique, mais je ne sais pas si elle est connectée.

neuviemeporte
la source
La transformée de Fourier rapide (FFT) est un algorithme pour la transformée de Fourier discrète. La DFT n'est pas une approximation de la fonction d'origine en termes d'harmoniques, mais plutôt une projection d'un signal sur une base orthogonale exponentielle complexe.
Bryan
D'accord, mais le signal lui-même est une approximation échantillonnée et quantifiée d'une certaine distribution d'intensité, et la DFT est limitée en ce qui concerne le contenu harmonique par rapport à cette distribution théorique. Vous pouvez récupérer le signal exact d'IDFT, mais il y aura un certain biais si vous faites des trucs (comme le décalage) avant de le réintégrer. Ou est-ce que je manque quelque chose?
neuviemeporte
La DFT prend en effet des entrées discrétisées, mais ne se limite pas aux entrées quantifiées. Le signal n'a pas d'importance. Comme vous l'avez souligné, vous pouvez récupérer le signal exact. Cependant, je ne sais pas trop ce que vous entendez par «décalage». Les propriétés de décalage dans le domaine fréquentiel sont bien connues (traduction complexe des fréquences dans le domaine temporel). Si votre désir est de changer dans le domaine "temporel", alors vous devez penser au dual DFT de cela.
Bryan
1
Je veux dire que si j'effectue une opération sur la DFT d'un signal (comme dans mon cas - décalage de sous-pixels d'une image dans le "domaine de pixels" en utilisant le théorème de décalage de Fourier), que l'IDFT retournera des résultats interpolés comme expliqué par @ hotpaw2's répondre. Cette interpolation est imparfaite car le signal n'est pas limité en bande et la DFT elle-même a été calculée à partir d'un ensemble fini d'échantillons quantifiés (0-255).
neuviemeporte

Réponses:

4

Un DFT / FFT, plus un remplissage nul ajouté dans le domaine fréquentiel, puis un IDFT / IFFT plus long, retournent des points interpolés. Ces points seront interpolés à l'aide d'un noyau Sinc périodique, qui est une interpolation parfaite pour les données originales strictement limitées à une bande inférieure à la moitié de la fréquence d'échantillonnage d'origine. Cependant, les données seront traitées comme si elles étaient enveloppées de façon circulaire, ce qui peut produire des résultats étranges sur les bords de certaines images. Donc, vous voudrez peut-être remplir les bords de la source d'origine avec une belle couleur de remplissage ou de cadrage avant l'interpolation.

Si vous suréchantillonnez par 2X (mettez à zéro la FFT pour doubler la longueur avant l'IFFT), vous pouvez alors effectuer un décalage d'un demi-pixel en utilisant les points interpolés. 3X pour un troisième décalage de pixel, etc. Pour le décalage, vous pouvez jeter les points d'origine plus les points interpolés en excès pour obtenir la taille souhaitée.

hotpaw2
la source
5
@ hotpaw2: le noyau d'interpolation pour la DFT n'est pas un sinc () d'étendue infinie, en fait la DFT est une transformée discrète et finie. L'interpolation par la DFT est équivalente à la convolution avec le noyau de Dirichlet, également appelée sinc () périodique par certains auteurs: en.wikipedia.org/wiki/Dirichlet_kernel
Arrigo
@Arrigo: d'accord. Réponse modifiée à corriger.
hotpaw2
@ hotpaw2: lorsque je remplis la FFT à deux fois la taille, l'IFFT donnera une reconstruction de deux fois la taille. Vous ne savez pas quoi faire de l'excédent? Merci
neuviemeporte
Jetez les points excédentaires dont vous n'avez pas besoin. Dans un suréchantillonnage 2X, tous les autres sont décalés, en alternance avec les points d'origine reconstruits. Dans un suréchantillonnage 3X, vous obtenez 2 points décalés (de 1/3 et de 2/3) en alternance avec les originaux. Etc. Plus vous suréchantillonnez, plus vous jetez.
hotpaw2
7

Il existe plusieurs informations clés dont vous avez besoin pour comprendre comment la DFT vous permet de décaler une image.

Tout d'abord, le théorème de Fourier: il est probablement plus facile de regarder d'abord le cas continu (c'est-à-dire analogique). Imaginez que vous ayez une fonction, appelez-la g (t). Pour simplifier, disons que g (t) est un enregistrement audio analogique, donc c'est une fonction unidimensionnelle, qui est continue, et représente la pression instantanée en fonction du temps.

Maintenant, g (t) est une façon de représenter notre enregistrement audio. Un autre est G (f). G (f) est la transformée de Fourier de g (t). Donc, G (f) == FT (g (t)). G (f) a toutes les mêmes informations que g (t), mais il représente ces informations dans le domaine fréquentiel au lieu du domaine temporel. Il y a quelques détails pointilleux sur les transformées de Fourier, que je ne mentionnerai pas.

Vous pouvez en quelque sorte considérer G (f) comme la "distribution des fréquences" contenue dans g (t). Donc, si g (t) est une onde sinusoïdale (c'est-à-dire un ton pur), alors G (f) sera nul partout, sauf à la fréquence de ce ton. C'est probablement un bon point pour mentionner que G (f) est en général une fonction complexe - c'est-à-dire qu'il renvoie des nombres complexes, qui peuvent être considérés comme ayant une composante réelle et imaginaire ou une amplitude et une phase.

δ(w)δ

Ok, alors maintenant nous avons des FT continus à notre actif.

Voici le deuxième aperçu: une transformée de Fourier discrète est une transformée de Fourier comme un signal échantillonné est un signal analogique. Dans ce cas, le «discret» fait référence à la quantification du domaine de la fonction (temps ou fréquence), pas sa plage. (Le signal numérique échantillonné que vous obtenez de votre carte son est quantifié à la fois dans le domaine et dans la plage.)

Le flux d'octets numérique que vous obtenez à partir de votre carte son contient des "échantillons" du signal continu (analogique) original du microphone. Si nous prenons la DFT de notre g (t) échantillonné, nous obtenons toujours un G (f). G (f), rappelez-vous, n'est qu'une façon différente de représenter les informations contenues dans g (t). Si nous obéissons au théorème de Nyquist , le signal échantillonné g (t) contient toute "l'intelligence" du signal continu d'origine, donc notre discret G (f) doit contenir toutes les informations de notre signal continu d'origine. Entre parenthèses, G (f) est toujours une fonction complexe.

C'est là que la magie du décalage sous-pixel entre en jeu, mais dans ce cas, je vais écrire sur le décalage du signal audio dans le temps de moins d'un échantillon, car c'est la même chose.

eiπ2

Cela signifie que nous pouvons changer notre enregistrement audio dans le temps (par tout montant que nous choisissons, y compris une fraction de temps d'échantillonnage) simplement en modifiant la phase de G (t). En fait, cette déclaration est peut-être un peu trop désinvolte. Pour un signal échantillonné non quantifié, la phase peut être ajustée arbitrairement (cela fait partie de la raison pour laquelle j'ai fait la distinction entre quantification du domaine et de la plage plus tôt). Cependant, pour un signal échantillonné quantifié (notre flux d'octets audio, par exemple), la taille du pas de quantification (c'est-à-dire le nombre de bits) détermine la résolution avec laquelle nous pouvons ajuster la phase. Lorsque nous transformons la Fourier inverse G (f) (ou le DIFT, pour ce signal échantillonné), le nouvel ensemble d'échantillons g '(t) = DIFT (G (F)) sera tous décalés dans le temps de la quantité que nous choisissons.

Appliquer cela à vos pixels signifie simplement utiliser un FT à 2 dimensions au lieu du FT à 1 dimension discuté ici.

nick g
la source