DÉTECTION DES DROITES DANS UNE IMAGE : HOUGH

Commentaire de Kirua le 19/07/2007 00:22:01

Juste pour être sûr d'avoir compris, parce que je n'ai jamais fait de traitement d'image. Est-ce que ça fonctionne comme ça:

* tu appliques l'opérateur gradient (Sobel) à l'image
* tu binarise au moyen d'un seuil, pour isoler les contours
* pour chaque point "vrai" (blanc) de l'image, tu traces la sinusoïde de Hough associée dans une nouvelle image, en incrémentant la brillance des pixels
* tu utilises un seuil pour binairser l'image résultante, ce qui te donne quelques points blancs
* tu appliques l'inverse de la transformée de Hough à ces points-là, pour obtenir des droites dans l'image original

Correct?

Je sais que ça ressemble fort à la description que tu fais, mais le doute subsiste en moi au niveau de la transformée directe de Hough. J'aurais pas fait comme ça, mais ça a l'air fichtrement plus simple que de calculer des points de concurrence de millions de sinusoïdes e façon analytique ^^.

Commentaire de Kirua le 19/07/2007 12:41:46

Ca m'a bien intéressé ton truc, alors me suis amusé avec matlab hier soir. J'ai programmé un filtre de Sobel, c'est super amusant ^^ (*kirua s'amuse*). Ca donne un effet de crayonné sur les photos :).

Je vais me renseigner sur la transformée de Hough. J'ai déjà lu un article descriptif sur wikipdia, mais il n'y a pas de développement mathématique.

Tu connais d'autres filtres ou traitements qui pourraient être amusants à tester? Ca m'intéresserait de trifatouiller avec tout ça :).

Commentaire de Kirua le 19/07/2007 18:20:27

Je viens de tester tout ça, c'est assez amusant. Le filtre de Prewitt marche bien!

Commentaire de aquamanfx le 24/07/2007 17:42:57

Bonjour,
Ayant fait ma thèse en imagerie numérique sur la reconnaissance de forme et notamment sur transformée de Hough (TH), je ne resiste pas quand je vois des discussions sympa comme celles ci.
Tout d'abord, pour KIRUA qui souhaite un peu plus de mathématiques; je le renvoie à cette excellente référence : http://irevues.inist.fr/bitstream/2042/2334/3/02.PDF+TEXTE.pdf , qui résume et formalise assez bien les principe de base des différentes TH (1 à m et m à 1).
Sans rentrer dans tous les détails et avancées récentes, aujourd'hui les principaux problèmes tournent généralement autour du choix des maxima et des pas de discrétisation dans l'espace d'accumulation de Hough.
Pour le filtrage, si vous avez du temps(!), -c'est un sujet également passionnant- je vous recommande cette page : http://perso.enst.fr/~maitre/BETI/Filtrage.html qui synthétise assez bien quels filtres utiliser selon ce que l'on souhaite chercher.
Si vous avez des questions, n'hésitez pas!

Il faudra un de ces jours que je mette au propre les KM de code que j'ai fait sur ces sujets pour en faire profiter les autres sur ce forum où je ne fais que passer et regarder; faute de temps...
Je n'ai pas eu le temps de regarder le source dans le détail, mais j'y apporterai ma contribution! Promis!
Bonne soirée

Commentaire de aquamanfx le 26/07/2007 19:08:31

Le sujet de ma thèse était "Etude d'algorithmes pour la fonction détection d'obstacles pour les vols en hélicoptères" (qui malheureusement est confidentielle pour 10 ans...).
Dans une partie, j'ai utilisé deux TH pour retrouver dans un espace 3D de points des câbles suspendus; une pour détecter les droites et une autres pour trouver des chaînettes (détail de l'algo ici: www.wipo.int/pctdb/en/wo.jsp?IA=WO2007010113&wo=2007010113&DISPLAY=DOCS ). Pour les droites le principal souci était de trouver les bons seuils et les bons pas de discrétisation. Cette partie n'étant pas la plus coûteuse en temps de calculs le plus dur était de détecter les chaînettes pour tendre vers du temps réel.
Je ne peux sur cette partie de ma thèse (à mon grand regret) que divulguer le principe général de l'algo qui a été protégé par mon entreprise dans le cadre d'un système puisque le brevet est publié (je suis contre les brevets qui protègent du code uniquement que ce soit dit! ^^) mais pas les sources.

Par contre comme je disais plus haut il faudra que je fasse passer sur le site mes algos de TH optimisées pour les droites et les ellipses faits avec glut et opengl. Mais avant il faut que je les commente bien mieux sinon il seront inexploitables! Je vais profiter de mes vacances dans quelques semaines pour m'y atteler, ça fera une meilleure base de discussion. En vrac, pour jeter les bases de l'optimisation, il faut avoir une idée de ce que l'on cherche; c'est à dire as t on une idée du nombre de droites potentielles à trouver ?(pour détecter les lignes d'un cours de tennis par exemple!) Si oui, on fait des heuristiques pour ne pas avoir à reparcourir tout le tableau des max, sinon il faut rentrer dans des algo de recherche de max.
A+

Commentaire de Kirua le 04/08/2007 17:05:18

Youp,

je suis en train de lire le document http://irevues.inist.fr/bitstream/2042/2334/3/02.PDF+TEXTE.pdf, et à la page 5 ils proposent un truc intéressant: plutôt que de décider d'un seuil pour le filtre sobel et d'appliquer la TH aux points conservés (réputés points de contour), une idée est d'appliquer une TH directement après le sobel (sans seuil), mais avec une pondération, ie: on dessine les sinusoides de hough plus ou moins "fort" selon que le gradient au niveau du point considéré était lui-même plus ou moins fort.

Tu as fait des essais dans ce sens? Je serais curieux de savoir ce que ça donne ^^.

Commentaire de zolotaya le 06/08/2007 16:28:59

Salut à vous,

Bon voila, j'essai depuis un moment (mais je n'y arrive pas) d'implémenter la transformée de Hough en JAVA.
Le truc est que je ne sais pas de ou viens mon problème. J'ai déjà chercher sur d'autres forum mais sans succés hélas.
Actuellement je prend une image, je la binarise et j'éfféctue une détéction des contours dessus. Jusque la tout vas bien!
voila mon image binarisée. [URL=http://imageshack.us][IMG]http://img511.imageshack.us/img511/7074/contourbwn0hs4.png[/IMG][/URL]
une foie que j'obtiens cette image, je la parcours et quand je trouve un pixel non noir, je calcul la sinusoïde.
(ca normalement ca marche!) voila le résultat :
[URL=http://imageshack.us][IMG]http://img127.imageshack.us/img127/2691/houghom8.png[/IMG][/URL]
Le graphique est tracé avec JFreeChart, c'est donc pour moi juste un indicateur visuel!
Le problème survient quand je cherche les valeurs maximales dans mon accumulateur. J'obtiens ces valeurs la!

maxi = 38 theta = 85 rho = 74
maxi = 43 theta = 86 rho = 67
maxi = 57 theta = 87 rho = 59
maxi = 65 theta = 87 rho = 60

maxi est mon nombre de pixel par case, theta l'angle en degré et rho la distance. Sauf qu'il y a rien à moin de 120 pixels de l'origine (laissé en haut à gauche).
Voila un bout du code.

for (int x = 0 ; x < bi.getWidth() ; x++) {
   for (int y = 0 ; y < bi.getHeight() ; y++){
   // Si le pixel n'appartient pas au fond (n'est pas noir)
   int rgb = bi.getRGB(x, y);
   rgb = rgb & 0xFF;
      if (rgb > 0){
      // Series pour tracher le graphique
      XYSeries series = new XYSeries("hough"+compt);
         for (int angle = 0 ; angle < 360 ; angle ++){
         double theta = Math.toRadians(angle);
         double rho = x*Math.cos(theta) + y*Math.sin(theta);
         int indexAngle = (int) (angle);
         int indexRho = (int) Math.abs(rho);
         accu[indexAngle][indexRho]++;
         series.add(theta, rho);
         }
      dataset.addSeries(series);
      // BufferdImage pour voir les pixels traités (tous)
      dst.setRGB(x, y, rgb);
      compt++;
      }
   }
}

Auriez vous une idée de ou peut venir ce problème? On m'a dit que la facon de faire étais bonne mais apparament ca suffit pas... A moin que je ne soit pas douer (ca c fort possible aussi).
Sinon j'avais trouvé un site qui traite le calcul des maximums dans l'accumulateur par l'approche de gaussiennes. Si ca vous interesse dite le moi j'essairai de le retrouver ;)

Cordialement,
Zolotaya

Commentaire de zolotaya le 07/08/2007 16:03:48

Salut Pistol,

Merci pour tes conseils, j'ai pu ciblé mon prroblème.
Pour mes maximas, je parcours mon tableau une premiere foie à la recherche du maximum (la plus grande valeur). Pour les maximas suivant cherche le maxima strictement inférieur au dernier maxima trouvé. Je fait cela par rapport à un seuil fixé (10 droites par exemple, ca ca reste à faire).
Sinon apparament, d'aprés quelques essais simple (1 petite droite horizontale et 1 verticale), je me suis appercu que mon accumulateur étais bon (mon theta et mon Rho sont correcte).
Mon problème viens de ma transformée inverse! Elle est toute fausse!
Ca serait possible d'avoir un petit algo sur la transformée inverse?

Zolotaya.

Commentaire de zolotaya le 07/08/2007 16:46:27

J'ai du mal m'expliquer, c'est mon accumulateur que je parcours 10 foies (si je cherche 10 droites) et non mon images.
En gros j'ai mon image de départ (avec 1 droite pour le moment).
Je parcours cette image et des que je trouve un pixel, je trace toutes les droites possibles passant par ce point.
D'un coter je trace un graphique (qui me sert juste pour voir le rendu des sinusoïde) et de l'autre, pour chaque Rho et theta trouvé j'incrémente de 1 la case d'un tableau d'entier corrsespondant (accu[rho][theta]++). C'est ce tableau que je parcours autant de foie que je cherche de droites.
J'ai donc comme informations pour ma transformée inverse juste la distance (Rho) et theta (en degré).

Sinon voila un liens si ca t'interesse sur la TH que je trouve pas mal (un peu complexe pour moi)sur la détéction des maximas.

www.dmi.usherb.ca/~egli/ciro2005.pdf

Bon courage à toi
Zolotaya

Commentaire de Pistol_Pete le 08/08/2007 08:44:40

Salut

Voila Kirua, j'ai apporté les modifications que tu m'avais suggéré.
Tu pourras te forger ta propre opinion mais je ne trouve pas que se soit une meilleure méthode. Elle est beaucoup plus longue et la modification de la TH est légère. Mais il semble quand même que cette méthode permet d'avoir des maxima plus nette. Elles semble donc de meilleur qualité.
A+

Commentaire de Kirua le 09/08/2007 13:26:52

Ca, les critères de qualité, c'est pas tout noir ou tout blanc dans ce genre de disciplines :). C'est cool que t'aies fait le test en tout cas!

Quelqu'un aurait une idée élégante pour détecter les "bornes" des droites trouvées? Sur l'image de l'exemple, assez logiquement, les segments de droite sont considérés comme des droites qui traversent toute l'image. Ce serait vrmnt classe d'arriver à détecter les limites des segments.

Commentaire de Kirua le 09/08/2007 15:04:46

Une idée comme ça: une fois qu'on a la droite, on peut retourner sur l'image qui a servi à calculer la TH et voir quels points de la droite sont "allumés" sur cette image. On prendrait alors les deux extrêmités. Mais ça ne serait pas très précis :/.

Commentaire de Kirua le 09/08/2007 15:51:39

En fait, en relisant ton message, je vois mieux pourquoi on a eu la même idée ^^. Mais t'as raison, les points s'écarteront assez fort. Une idée, ce serait d'essayer de donner une "zone d'influence" aux points de fort gradient, ie: augmenter la valeur des pixels proches pour que de faibles écarts à la droite trouvée ne gênent pas trop.

Une façon de le faire, mais ça prendrait énormément de mémoire, ce serait de retenir, pour chaque pixel de la TH, quels points du gradient ont contribué à augmenter son poids. De cette manière, on aurait la liste des points du segment de droite, et il suffirait de prendre les extrêmes. Mais la quantité de mémoire nécessaire serait de l'ordre de O(n^4) je pense :/. (avec n la largeur de l'image, considérant des images carrées).

Commentaire de Kirua le 09/08/2007 16:09:57

Je ne comprends pas ta dernière remarque. Tant qu'on travaille en polaire, il n'y a pas de singularité du type "x=k".

Commentaire de Kirua le 09/08/2007 16:21:36

Ca serait une question tout à fait légitime ^^. Au premier abord, utiliser une forme polaire parait compliquer l'arithmétique, mais la répartition des droites dans l'espace des paramètres est bien plus homogène comme ça et on n'a pas de singularité à traiter. Que du bonheur quoi ^^.

Commentaire de Arnaud16022 le 06/12/2007 14:07:34

Autre petit truc :
Je ne veux détecter que les lignes verticales.
Est-ce que ça vaut le coup de faire un vrai Sobel ? Pourquoi ne pas appliquer que la dérivée discrète partielle en y ?
Après, je suppose qu'il y a bien moyen d'optimiser aussi l'écriture dans l'image de la transformée .. genre ne pas dessiner la sinosoide sur 200 px de large, mais seulement sur les bords et au milieu...idem pour tous les autres traitements.
Vous en pensez quoi ?

Commentaire de Kirua le 06/12/2007 17:06:33

une dérivée par rapport à x plutôt non? pour les lignes verticales

Commentaire de Kirua le 07/12/2007 17:29:41

ben, ça dépend. si tu cherches des lignes parfaitement horizontales, tu as des lignes dérivées en x nulles sur les dites lignes et des dérivées en y maximales sur les dites lignes. juste non?