Bonjour,

Dans le cadre d'un projet pour mes études, j'essaie actuellement d'implementer informatiquement la méthode de détection des contours proposée dans cet article : https://pdfs.semanticscholar.org/37b6/f30417838c56af4d1ce51176482e108dd9b1.pdf.

J'en suis à cette formule :

Avec "h and w are the height and width of the rectangular region used for this enhancement, C(ro; teta) represents the number of edge points satisfying [...] and Cenh is the enhanced hough image."

Et malheureusement je bloque sur la double intégrale.  J'ai essayé de faire ça bêtement avec des boucles mais du coup ça m'en fait 4 imbriquées donc O(n^4) et ça ne finit pas. Dans l'article il est écrit : "Since ro and teta are quantized, the integral is computed through a convolution with a rectangular mask" sauf que je ne comprends pas le lien entre l'intégrale et la convolution. J'ai cherché sur internet mais sans grand succès...

Pourriez-vous svp m'aider à comprendre comment calculer cette intégrale ? Merci 

Bonjour, 

Je crois que la phrase traduite n'a pas été bien comprise : la convolution permet d'obtenir la formule. La convolution est le fait d'intégrer en déplaçant l'abscisse, rho+y et theta+x, d'où la référence. D'autant plus que je n'ai jamais entendu parlé de méthode "révolutionnaire" pour calculer des intégrales... Quelle méthode utilisez-vous? Si vous voulez diminuez le temps d'exécution, augmentez l'ordre avec des méthodes demandant des pré-calculs, comme l'intégrale de Gauss par exemple. 

Salut,

Je ne m'y suis jamais plongé, mais pour calculer des intégrales multiples, n'est-il pas plus intéressant d'utiliser Monte-Carlo ? Ceci dit je pense qu'ici ça dépend pas mal du contexte, je vais jeter un oeil au lien que tu donnes.

EDIT :

ok il semblerait que la fonction que tu souhaites intégrer a ses valeurs stockées dans un tableau 2D. C'est très différent du cas général où tu as une fonction qui te renvoie une valeur pour un couple de coordonnées en entrée. D'où la remarque sur la convolution.

L'idée d'une convolution est la suivante (DISCLAIMER : je ne traiterai pas la théorie ici, beaucoup plus vaste...) :

pour deux fonctions a et b de R dans R, intégrables, on définit la convolution de a et de b par :

on remarque que cette formule est ici symétrique, mais ça ne servira pas. Pour le cas de l'informatique, on prendra des bornes à cette intégrale, et on l'écrira sous forme de somme.

Revenons à la formule continue. Très simplement, on voit que si l'on choisit a comme une fonction porte,

avec u et v deux réels, la convolution de a et de b devient :

ce qui correspond presque à ce que l'on cherche.

Pour ce qui nous intéresse, on passe en dimension deux (la formule est la même) :

ce qui se réécrit avec un changement de variables :

Ceci étant dit, tout cela est bien beau, mais quel intérêt pour le calcul ? Il est clair que la convolution reste exactement une somme double ici, et donc en O(n^2) pour chaque coordonnée, soit O(n^4). 

C'est là que la magie intervient ! Ce qu'il y a de bien avec les convolutions, c'est que pour un tableau de taille N, on sait faire le calcul de la totalité des valeurs de la convolution en O(n log(n)) au lieu du basique O(n^2). Comment ? Avec la Transformée de Fourier (un seul r entre le u et le i, attention !). En effet, on appelle Transformée de Fourier la fonction qui à une fonction f associe la fonction :

La convention que je donne ici n'est pas unique, parfois on ne met pas le 2π à l'exponentielle, parfois on divise le résultat par racine de 2π, etc. (je choisis cette convention car elle est la plus proche de la convention usuelle pour la transformée de Fourier discrète, en informatique, qui nous intéresse).

L'important à noter est que :

• cette formule s'inverse par la Transformée Inverse de Fourier :
  
  il suffit de changer le - en + dans l'exponentielle, et on retrouve la fonction de départ !
• la transformée d'une convolution est un produit !
  
  
  Bon, dit comme ça ça a pas l'air extraordinaire, mais pris dans l'autre sens :
  
  
  Et là, c'est extraordinaire ! Parce que si l'on possède un moyen rapide (en O(n log(n)), au hasard) pour calculer les Transformées de Fourier de a et b, et la Transformée de Fourier Inverse du produit, alors on aura la convolution de a et b tout aussi vite ! (en O(n log(n)), par exemple...)
• bon la Transformée de Fourier possède tout un tas d'autres propriétés, comme la linéarité, un lien particulier avec la dérivée et l'intégrale, etc. mais ce qui nous intéresse aujourd'hui ce sont vraiment les deux propriétés ci-dessus.
• pour simplifier l'idée, la Transformée de Fourier passe du domaine temporel au domaine des fréquences.

on dispose d'un tableau C[rhô][thêta]
on veut calculer les intégrales centrées sur chaque coordonnées (rhô,thêta)

faire un 0 padding de C afin d'avoir de la place pour calculer les convolutions : rajouter h/2 lignes de zéros au début et à la fin, et w/2 colonnes de 0 au début et à la fin)

créer un tableau "porte" A de la même taille que C après 0-padding, avec des 1 sur le rectangle [0:r, 0:w] et des 0 partout ailleurs

calculer les transformées de Fourier réelles rapides de C et A (donne deux tableaux de même taille) (O(n^2 log(n^2)))

Multiplier les deux transformées coordonnée par coordonnée (O(n^2))

Prendre la transformée de Fourier réelle rapide inverse du tableau produit (O(n^2 log(n^2)))

PR

-
Edité par PR 16 août 2018 à 0:51:46

Salut,

Tout d'abord un énorme merci pour ta réponse  !! Je suis désolé de ne pas avoir répondu plus tôt, mais je n'avais pas vu que j'avais des nouvelles réponses.

J'ai lu avec soin tes explications, et je pense avoir compris les grandes lignes. En ce qui concerne les transformées de Fourier (un seul r entre le u et le i ) je travaille en Python et j'ai trouvé des fonctions toutes faites, donc normalement pas de problème là-dessus.

J'aurais néanmoins une question : je ne suis pas sûr d'avoir bien compris ce qu'on obtient à la fin de ton pseudo-code... Est-ce qu'il s'agit du tableau contenant les valeurs des dénominateurs (dans la formule de C_enh) ?

Et encore merci pour tes explications