Comment appliquer correctement la FFT dans le débruitage d'image

8

J'écris un programme (widgets Qt / c ++) pour supprimer le bruit des images. Comme méthode de débruitage, j'ai choisi la méthode des moyennes non locales . Cette méthode a une qualité incroyable d'images restaurées (c'est pourquoi c'est la seule méthode de débruitage dans OpenCV), mais a un coût de calcul énorme , j'ai donc fait beaucoup de variantes modifiées de cette méthode (certaines avec multithreading, d'autres algorithmiques). Mais, j'ai un problème avec celui, impliquant la FFT

J'ai suivi toutes les étapes de cet article (une seule page, 1430) et tout fonctionne parfaitement, sauf pour la partie FFT, il n'y a que 2 lignes à ce sujet dans le document et je ne peux pas comprendre, COMMENT doit-on utiliser fft

Ce problème me dérange depuis des mois, toute aide ou compréhension serait grandement appréciée.

Version abrégée de la question: Comment puis-je obtenir rapidement la différence au carré de deux tableaux sur l'image (l'un en haut et l'autre au milieu, les valeurs sont des couleurs) rapidement? (O (n ^ 2) est un coût énorme, il y a beaucoup de ce genre d'opérations, le papier ci-dessus déclare, que cela peut être fait via FFT avec O (n * log n) (dit que ces 2 tableaux formant une convolution circulaire en quelque sorte) )

entrez la description de l'image ici

Shf
la source
Qu'avez-vous finalement fait pour calculer la FFT? Même si la FFT est précalculée, la multiplication ponctuelle et l'ajout de tous les éléments de patch prennentO(|P|) moment où |P|est la taille du patch. Comment avez-vous surmonté cela?
curryage

Réponses:

5

L'astuce à l'intérieur du papier est la suivante:

  1. Ce que vous voulez calculer, c'est jeW|je(X+je)-je(y+je)|2, où je est une image, X et y deux pixels bruyants et je est un décalage 2D utilisé pour définir un patch.
  2. L'élargissement de l'expression donne: jeje2(X+je)+jeje2(y+je)-2jeje(X+je)je(y+je)=UNE+B-2C.
  3. UNE et B sont calculés en utilisant une image intégrale au carré, c'est-à-dire une image intégrale à partir de l'image originale au carré.
  4. C est la convolution entre les deux patchs centrée sur X et y. Ainsi, il peut être calculé dans le domaine de Fourier, où il devient une multiplication. Vous obtenez la valeur deC en calculant la transformée de Fourier du patch autour X, le patch autour yen multipliant ces résultats par points et en prenant la transformée de Fourier inverse du résultat de la multiplication.

La transformée de Fourier est évidemment une transformée 2D puisque vous travaillez avec des données 2D. Ce que vous obtenez pour un patch donné est un tableau 2D de valeurs complexes.

Notes complémentaires

À mon avis, cet article n'est pas la meilleure stratégie d'accélération NL-means. Les expériences que j'ai faites en 2007/2008 montrent que la présélection des patchs est meilleure (en termes de vitesse et de qualité des résultats). J'ai commencé à bloguer à ce sujet ici , mais malheureusement je cherche du temps pour terminer les articles.

Les articles NL-means originaux mentionnent des implémentations par blocs qui peuvent être intéressantes. Il existe fondamentalement 2 façons de mettre en œuvre NL-moyens:

  1. écrire une boucle de débruitage pour chaque pixel de l'image
  2. écrire une boucle de débruitage pour chaque patch, puis projeter en arrière les patchs pour former une image.

La première impolémentation est l'approche originale, car en 2005, la mémoire et les processeurs multicœurs étaient chers. J'ai par contre choisi le numéro 2 sur le matériel récent des 2 dernières années. Cela dépend de la taille typique de votre image et si vous voulez être en mesure de calculer des transformations de domaine comme DFT / DCT (comme dans le document proposé et dans BM3D).

sansuiso
la source
Merci beaucoup pour votre réponse, c'est exactement ce dont j'avais besoin, tout était prêt et fonctionnait il y a longtemps, à l'exception du 4ème élément de cette liste, mais maintenant c'est beaucoup plus clair. Encore une question, si cela ne vous dérange pas: qu'est-ce qui retournera la transformée de Fourier du patch x ou y? Tableau, vecteur ou valeur unique? Et que faut-il pour utiliser la transformation inverse? Parce que je pense à précalculer le fft pour chaque pixel (correctifs centrés autour de lui) et à écrire les résultats dans un tableau 2D avant de débruiter, puis d'utiliser simplement cette matrice pour obtenir le fft inverse, mais je ne sais pas si cela sera suffisant pour le fft inverse
Shf
oh, et devrais-je utiliser 2d fft, ou traduire le patch en tableau 1d? par ailleurs, je comptais écrire après cette mise en œuvre de PatchWise de toute façon, merci pour un conseiller :) quelque chose de semblable à cela aussi longtemps ago- ipol.im/pub/art/2011/bcm_nlm
Shf
J'ai mis à jour la réponse.
sansuiso
ok, donc je peux précalculer la FFT pour les correctifs, centrée autour de chaque pixel avant de faire du don mais cela prendra beaucoup de mémoire (m n size_of_patch size_of_patch sizeof (double)), mais quand je compterai les poids, je devrai encore multiplier par point 2 les tableaux complexes et après cela fft inverse sur le tableau 2d reçu, c'est encore plus que O (n ^ 2) si je ne me trompe pas
Shf
2
Bonne réponse, mais comment dérivez-vous cela Cest une convolution? La façon dont il est écrit est un produit élément par élément. Où est la convolution?
TheGrapeBeyond du