Complexité d'une transformée de Fourier discrète 2d

Question

J'ai une question concernant une transformation de Fourier 2D. Je suis actuellement en train de comprendre les maths derrière cela, et il y a quelque chose que je ne comprends pas. En ce qui me concerne, la DFT a une complexité de O(N*N). Si je regarde l'algorithme suivant:

Je ne comprends pas comment cela fonctionne. Allons-nous faire cette caluculation pour chaque pixel dans le tranformé image?

exemple

1. Nous avons une image de 2 * 2.
2. Pour chaque pixel dans cette image que nous allons faire la TFD F (x, y)
3. Je vais créer une nouvelle image, et chaque pixel est l'importance de la valeur complexe correpondant

Est-ce ainsi que ça marche ou est-ce qu'il me manque quelque chose? Parce que la façon dont je le vois maintenant, il a une complexité de O(N^4)

Answer 1

L'équation signifie "pour obtenir la valeur de F au pixel (u, v), évaluer (la formule sur le côté droit)." Ainsi, pour obtenir toute l'image transformée, elle est évaluée pour chaque pixel de l'image transformée. Pour calculer une DFT, en utilisant la formule, vous devez effectuer un calcul O (1) pour chaque valeur d'entrée pour chaque valeur de sortie. (Il existe d'autres algorithmes plus rapides pour certains types de données.) Dans votre cas 2D DFT, l'algorithme a une complexité O ((M * N)^2), car le nombre de pixels d'entrée est M * N et le nombre de les pixels de sortie sont également M * N.

modifier: une matrice 2D DFT peut être calculé en O (NM^2 + MN^2) en transformant les lignes et les colonnes dans des étapes séparées. L'algorithme est ici: http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node6.html