# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  transforme de hough : quelques questions

## jokoss

Bonjour  tous,

Je m'intresse en ce moment  la transforme de hough dans le cadre de la dtection de lignes.

Aprs avoir pluch pas mal de documents tratant le sujet, je pense avoir asse bien compris le principe mais malheureusement je sche sur un point ou l'autre.

Je me suis largement inspir du post de pseudocode de la rubrique contribuez.

Je vais illustrer par un exemple pour faire plus comprhensible. Imaginons 3 points P1(0,1) P2(1,3) P3(2,5). Ces points sont aligns et forme une droite d'quation y = 2x+1. Donc voil je me lance dans le dveloppement. 

J'ai une image dans mon exemple 650*478 pixels (normalement pas important). Pour le moment donc je n'ai que les 3 points P P2 et P3 qui sont noirs. 
J'ai donc 


```

```

Ensuite voici mon algo:



```

```

Je pense que j'ai un problme du cot du calcul du rho. En effet pour des petites valeurs de (x, y) (ici appele (i, j)), les valeurs de rho quelque soit le theta sont trs basses. Dans le cas extrme du point (0,0) , tous les rho valent 0 --> ne ressemble pas trop  une sinusode  ::): .

Enfin voil , si quelqu'un pouvait me dire o j'ai faux ou bien me donner les rsultats que je devrait obtenir avec ce petit exemple je lui en serait fort reconnaissant.

----------


## pseudocode

> Je me suis largement inspir du post de pseudocode de la rubrique contribuez.


C'etait juste un exemple, pas une implmentation de reference.



```

```

Les 2 remarques sont pertinentes. Ces calculs/tests supplmentaires datent d'une 1ere version du code. Elles n'ont plus de raison d'tre. Je mettrais a jour demain.  :;): 




> Je pense que j'ai un problme du cot du calcul du rho. En effet pour des petites valeurs de (x, y) (ici appele (i, j)), les valeurs de rho quelque soit le theta sont trs basses. Dans le cas extrme du point (0,0) , tous les rho valent 0 --> ne ressemble pas trop  une sinusode .


Non c'est normal. 

Une ligne en 2d <--->  couple (distance  l'origine, angle d'orientation) dans Hough

Toutes les lignes qui passent par (0,0) sont a une distance=0 de l'origine. Dans l'espace de hough toutes ces lignes sont reprsentes par les valeurs entre (0,0) et (0,180)

----------


## jokoss

Bonjour,

merci pour tes rponses.

Pour le moment j'essaye avec les points (0,0) (1,1) et (2,2). Pour le point (0,0), j'ai donc tous mes rho  0 pour chaque valeur de theta.

Voici pour le point (1,1) : mon rho varie entre 0 et 1. 


```

```

Voici pour le point (2,2) : mon rho varie entre 0 et 3. 


```

```

Ce qui me gne c'est que l'on trate un rho = 1.5 ou rho = 2.4 de la mme manire,  savoir un arrondi  2. Du moins pour de petites valeurs ca me parait bizard d'arrondir  ce point.

D'ailleur lorsque je cherche le maximum accumul, j'obtiens 10 maximums donc 10 points d'intersection donc 10 droite diffrentes?



```

```

O se cache l'erreur?

----------


## pseudocode

> O se cache l'erreur?


Il n'y a pas d'erreur. 

Une ligne passant par le point (0,2) est a une distance MAXIMUM de 2 par rapport a l'origine (0,0). Au minimum la distance est de zro dans le cas de la ligne horizontale car elle passe par (0,2) et par (0,0).

Donc les "rho" pour les lignes passant par le point (0,2) sont entre 0 et 2.

ATTENTION: si tu choisis de prendre des "rho" toujours positifs, l'angle theta doit varier entre 0 et 360. Si tu permets des "rho" ngatifs, tu peux restreindre l'anglet entre 0 et 180

Pour ton problme d'arrondi, il faut voir que l'algo de Hough repose sur un systme de "votes" discrtiss. Ca a du sens pour une image "bitmap" car il n'y a pas de diffrences "visuelles" entre les 2 droites "y=2x+1" et "y=2x+1.3".

----------


## jokoss

ok merci j'ai corrig j'ai donc mis 360 degr au lieu de 180.

J'ai maintenant 21 maximums. Je devrai en avoir un seul normalement.
En tout cas si je ne changeait pas de coordonne et que je tranfre dans un repre a,b, j'aurai un seul maximum en (1,0), ce qui me donnerai  y = 1*x+0.



```

```

Si je prend comme maximum le point (125,0), j'obtiens



```

```

et donc



```

```

Ce qui est faux.

----------


## pseudocode

> J'ai maintenant 21 maximums. Je devrai en avoir un seul normalement.


Hum... tu dois avoir un bug quelquepart.

Pour une image 10x10 avec les points (0,0) (1,1) (2,2), j'obtiens cela:

Accumulateurs (taille 14x31)


```

```

maxima=3 at (0,11) -> y = 0.9505708820718327.x + 0.6968560962189071
maxima=3 at (0,27) -> y = 1.1648605718217948.x - 0.7754031459316263

Donc 2 droites trs voisines, qu'on peut fusionner (moyenne):

y = 1.0577157269468138.x - 0.0392735248563596

----------


## jokoss

j'obtiens le mme tableau que toi quand je mets la taille de mon accumulateur a 31.

Je l'avais mis a 360 comme le nombre de degr et je me rend compte maintenant que j'en avait 20 et que c'tait 2 groupe de 10 conscutifs. Peut tre que chaque groupe doit tre considr comme une seule droite (prendre la moyenne de chaque groupe?)

Sinon, comment connatre la taille optimale de l'accumulateur?

En ayant le mme tableau que toi j'ai encore la mme quation de droite avec a = 0.3 donc le bug doit se situer  la transformation finale, je vais regarder ca de plus prs.

----------


## pseudocode

> Sinon, comment connatre la taille optimale de l'accumulateur?


Tiens, c'est pas la premiere fois que je lis cette question:




> (...) le plus petit angle (non nul) entre 2 droites :
> 
> Dans le cas ou width>height, c'est l'angle entre la droite horizontale (0,0)-(width,0) et la droite (0,0)-(width,1).  Comme les 3 points (0,0) (width,0) et (width,1) forment un triangle rectangle, on a tan(theta) = Hauteur/Longueur = 1/width.
> 
> Idem dans le cas height>width.
> 
> D'ou la taille du tableau 2*PI/Arctan(1/max(width,height));

----------


## jokoss

J'ai donc un problme dans la reconversion dans le systme (x,y)

Si je pars du point (0,11) dans un accumulateur de taille 14x31, j'ai 



```

```

-->


```

```

J'obtiens donc au coeficient a , la valeur que tu obtiens pour b.
Et pour b j'obtiens 0, je ne vois pas comment tu peux obtenir autre chose tant donn que rho vaut 0.

remarque : j'ai repris ma conversion du post contribuez.

EDIT : la valeur de mon a ne correspond pas  ton b. J'ai t un peu vite.

----------


## jokoss

merci pour les prcision sur les tailles d'accumulateur. C'est vrai que je l'avais dj lu en plus mais je pensais que ce n'tait valable que pour la taille de l'axe rho et que dans tous les cas il fallait tester tous les angles.

----------


## pseudocode

> J'obtiens donc au coeficient a , la valeur que tu obtiens pour b.
> Et pour b j'obtiens 0, je ne vois pas comment tu peux obtenir autre chose tant donn que rho vaut 0.
> 
> remarque : j'ai repris ma conversion du post contribuez.


Ah, exact. J'ai arrondi differement les valeurs de rho/theta dans mon test. 



```

```


Je vais mettre a jour le code dans la rubrique contribuez.  :;):

----------


## jokoss

merci beaucoup , ca fonctionne.

J'ai malheureusement un dernier(du moins j'espre) petit problme.

En fait je n'ai pas exactement le mme tableau que toi (rho-theta).
J'ai bien comme premier point (0,11) mais comme deuxime j'ai (0,28)  la place de (0,27), ce qui change beaucoup le rsultat.

Pour le point (1,1) j'obtiens un rho = -0.035832 et pour (2,2) j'obtiens rho = -0.071665, cela pour un theta = 27. Il ne passe donc pas le test du rho positif.

J'ai donc indexTheta = 27, 

Ensuite,



```

```

Pourrais-tu me dire  quel moment tes rsultats diffrent-ils des miens?

----------


## pseudocode

> Pourrais-tu me dire  quel moment tes rsultats diffrent-ils des miens?


Ah. j'avais oubli de reporter l'approximation dans le remplissage des accumulateurs  ::oops:: . Faut que j'arrete de faire 3 trucs en mme temps.



```

```

----------


## jokoss

Parfait a fonctionne trs bien.

Un tout grand merci!

Je fais quelques tests plus compliqus et je mets en rsolu.

----------


## jokoss

J'essaye avec les points P1(0,1) P2(1,3) P3(2,5)
--> equation y = x+1

J'ai une image 650*478 

j'ai donc : maxIndexTheta = 71, maxRho = 806

Aprs traitement, j'ai 3 couples de valeurs qui sont au maximum (3)
IndexTheta = 28, IndexRho = 1
IndexTheta = 29, IndexRho = 1
IndexTheta = 30, IndexRho = 0

j'obtiens dans l'ordre :

a = 1.40, b = 2.58
a = 1.70, b = 2.96
a = 2.11, b = 1.168

au lieu de a = 1 et b = 1.

En prenant les valeurs optimale de maxRho et maxTheta j'obtiens ici 3 couples de valeurs (normal ou pas normal?)

Ensuite les valeurs sont rrones. 

Je n'arrive pas  voir d'o vient l'erreur.

EDIT : l'quation est y = 2x+1 

Seul le troisime couple  l'air correct.
Devrais-je obtenir juste un couple (le dernier) ou bien 2 comme avec l'autre exemple?

----------


## pseudocode

> Seul le troisime couple  l'air correct.
> Devrais-je obtenir juste un couple (le dernier) ou bien 2 comme avec l'autre exemple?


En fait dans l'espace de Hough tu obtiens un "amas" de points prs d'un maxima, et il faut en extraire les coordonnes d'un seul (rho,theta). 

L'approximation (rhomax+0.5,thetamax+0.5) n'est pas forcement la meilleure. Surtout dans les cas ou le maxima n'est pas unique dans le voisinage.

De plus, dans ton cas les 3 points sont "colls" alors que l'image est tres grande. Donc la detection ne va pas etre trs fiable. Si tu es souvent dans ce cas, il y a d'autre variante de Hough qui sont mieux adaptes.

----------


## jokoss

d'accord je comprend bien, dans mon cas je n'aurai pas des points colls comme ceci, c'est vraiment  titre de petit exemple pour mieux matriser les rsultats.

SI je prend des points assez petits (2,5) (3,7) et (4,9) , la transforme me donne un bon rsultats,  savoir y = 2.11*x+1.16

Mais si j'essaye avec des points plus espacs, les rsultats deviennent vraiment trange. exemple : (2, 5) (10, 21) et (18, 37)

Avec maxIndexTheta = 71, maxRho = 806 (obtenus par les calculs prcdents), j'obtiens y =  22.5*x - 373.3
Ce qui est donc completement faux. Ils faut savoir que dans ce cas-ci l'accumulateur ne dpasse pas 1 dans aucune de ces cases.

Par contre si je mets maxIndexTheta = 360, alors j'obtiens y = 2.005 * x + 1.12

Ce qui est quasiment parfait.


Je me pose donc la question du calcul de maxIndexTheta. D'aprs ce que j'observe il devrait varier pas uniquement en fonction de la taille de l'image mais aussi en fonction de l'endroit des points noirs la constituant.

----------


## pseudocode

> Ce qui est donc completement faux. Ils faut savoir que dans ce cas-ci l'accumulateur ne dpasse pas 1 dans aucune de ces cases.


Le problme c'est de determiner l'extrema dans un amas de points. Du fait de la discretisation, ce n'est pas la valeur la plus grande mais la valeur "centrale". Comme tu l'as remarqu, si on change la rsolution de la discrtisation, on se retrouve avec un amas dont l'extrema est plus simple a trouver. Ce genre de problme arrive moins frquemment si on a beaucoup de points (par rapport  la taille de l'image). 

Comme je te l'ai dit, dans ton cas il vaut mieux prendre une autre approche pour remplir les accumulateurs. Je te suggre l'approche souvent propose par Toto13:

1. prendre 2 points au hasards
2. calculer le (rho,theta) de l'unique droite passant par ces 2 points
3. incrementer l'accumulateur pour (rho,theta)
4. boucler a l'tape 2 (avec un critere d'arret)

Cette approche, bien que probabiliste, donne des rsultats trs prcis car on remplit seulement l'accumulateur correspondant EXACTEMENT a une droite.

Dans mon code, cela revient a modifier la methode "vote()":


```

```

----------


## jokoss

ok merci pour l'information.

En testant sur un cas rel (plusieurs milliers de points), j' ai encore des soucis avec la premire version de la transforme. D'aprs ce que je comprend la technique peut donner des rsultats rrons principalement si il n' y a pas beaucoup de point. Hors dans mon cas a marche trs bien avec (de nouveau theta = 360) sinon pour d'autres valeurs, j'ai tout de mme un trs bon coeficient a mais le b n'est pas bon.

J'ai mis en pice jointe une image typique  traiter.

Peux tu me dire s'il est normal avec ce type d'images d'obtenir de mauvais rsultats pour de basse valeurs de maxTheta.

merci

----------


## pseudocode

Tu es sur de ton calcul de maxIndexRho/maxIndexTheta ?

image 650x478 -> maxIndexRho=806, maxIndexTheta=4084

Habituellement, je rduis encore ces dimensions pour avoir quelquechose qui tienne en mmoire.

----------


## jokoss

heu je fais



```

```

sans le *(180/PI) , j'obtiens bien 4084. Je me suis dis qu il fallait convertir en degr le rsultat de l'arctangente.

non?

Parce que sinon 4084 ca va commencer  faire mal niveau temps de calcul

----------


## jokoss

A mon avis je dois avoir un problme quelque part d'autre parce que il n' y a l'air d'y avoir que la valeur 360 qui marche bien ( du moins  chaque fois).

exemple avec mon image en attachement :

- avec 360 j'obtiens : a = -0.131654, b = 197.391470

- avec 361 ou tout autre (4098 ou mme 70) , j'obtiens 
a = -0.118028, b = 454.097421

----------


## pseudocode

> Je me suis dis qu il fallait convertir en degr le rsultat de l'arctangente.


Ah. Tu peux, mais alors la plage pour l'angle doit aussi etre en degr:

maxIndexTheta = (int)(360/(atan2(1, max(height_input,width_input))*(180/PI)));

ce qui revient au meme que ma formule, aprs simplification.





> Parce que sinon 4084 ca va commencer  faire mal niveau temps de calcul


C'est clair. Ce calcul est une estimation de l'angle le plus petit (non nul) d'une ligne dans l'image. Dans ton cas, ca fait une prcision d'angle de 360/4084 = 0.088. Gnralement, je me limite  une prcision au degr (ou au demi-degr).

----------


## jokoss

parfait merci, je pense en effet qu'une prcision de 1 degr est dj pas mal.

Pour en revenir au post prcdent o je disais qu'il y avait une erreur avec le maxTheta = 4098, en fait non

a = -0.118028, b = 454.097421 

correspond juste  une autre ligne, le cot oppos.

C'est donc bon aussi.

----------


## jokoss

Bonjour,

J'aurai une question concernant le choix des lignes une fois l'accumulateur rempli.

Y a t'il moyen de pouvoir slectionner les n lignes les plus importantes d'une image sans un parcourt pralable de la matrice d'accumulation. Dis autrement, y'aurait il moyen de trouver un bon seuillage automatique pour l'accumulateur.

merci

----------


## pseudocode

> Y a t'il moyen de pouvoir slectionner les n lignes les plus importantes d'une image sans un parcourt pralable de la matrice d'accumulation. Dis autrement, y'aurait il moyen de trouver un bon seuillage automatique pour l'accumulateur.


Tu peux maintenir une liste des "N plus grandes valeurs" de l'accumulateur.

Personnellement, je travaille par zone. Je fais un quadrillage de l'accumulateur et je maintient le min/max/total de chaque case du quadrillage.

----------


## jokoss

ah oui c'est une bonne ide le travail par zone. 

qu'entends tu par  "min/max/total" , d'aprs ce que je comprend il faudrait juste prendre le score max de chaque zone ou bien les 2-3 scores max. 

Ensuite confronter l'ensemble des solutions entre elles.

De plus ca me permettrai d'liminer une partie des droites redondantes.

----------


## pseudocode

> qu'entends tu par  "min/max/total" , d'aprs ce que je comprend il faudrait juste prendre le score max de chaque zone ou bien les 2-3 scores max.


Je prends ces 3 valeurs pour filtrer un peu les rsultats. 

Par exemple si max=1000 et total=1000, ca veut dire que j'ai un pic "parfait", donc une forte probabilit de droite. Si j'ai max=1000 mais un total=9999..., ca veut dire que j'ai un pic trs tal, donc il faut une analyse plus pousse.

Ca ressemble beaucoup aux techniques utilises en segmentation (quadtree, ...).

----------


## jokoss

oui je comprend bien merci.

Mais dans un cas o les lignes  ont une paisseur non ngligeable , il est quasiment certain d'avoir plusieurs lignes (trs proche) dans les environs du maxima, non?

Mme si je conois trs bien que ce nombre est limit en comparaison avec  d'autres droites non voulues, par exemple trouves  cause d'amas de points dans l'image de dpart.

----------


## pseudocode

> Mais dans un cas o les lignes  ont une paisseur non ngligeable , il est quasiment certain d'avoir plusieurs lignes (trs proche) dans les environs du maxima, non?


1. Il faut affiner l'image de dpart (thinning) pour eviter d'avoir des lignes trop paisses.

2. Il faut fusionner les maxima qui sont trs proches dans l'accumulateur.

Avec ces 2 etapes, on doit normalement avoir une detection assez propre.

----------


## jokoss

parfait merci, je vais me renseigner sur le thinning.

----------

