Discussion :

[zolotaya]

Voila j'essai de détécter des droites dans une image avec la transformée de Hough. Le problème est que j'ai du mal à l'implémenter (je fait ca en JAVA).
J'aurais juste aimer avoir des précisions sur quelques points :
- sur le passage dans l'espace de hough
Sur une image avec que les contour en noir et blanc, je cherche les pixels blanc (les bords). Quand j'en trouve un pixel du contour, je fait varié theta de 0 à 2PI. Je calcul ensuite mon Ro à l'aide de mon theta (Ro = ysin(theta) + xcos(theta))
Est-ce que c'est bon jusque la?

-sur l'accumulateur
Pour chaque Ro et théta (de chaque pixel) j'incrémente mon accumulateur de 1 aprés je cherche les maximas de mon tableau.
Ca j'en suis pas sur j'ai pus trop compris à partir de la.

Quelqu'un peu me dire si ce que j'ai fait jusque la est bon ou sinon m'expliquer de la facon la plus simple possible ce qu'il faut faire. J'ai trouvé pas mal de documents mais aucun expliquant de facon simple la facon de faire (c'etais général ou sous matlab <- jamais fait)

Merci d'avance pour votre aide

[ToTo13]

Bonjour,

J'aurais juste aimer avoir des précisions sur quelques points :
- sur le passage dans l'espace de hough
Sur une image avec que les contour en noir et blanc, je cherche les pixels blanc (les bords). Quand j'en trouve un pixel du contour, je fait varié theta de 0 à 2PI. Je calcul ensuite mon Ro à l'aide de mon theta (Ro = ysin(theta) + xcos(theta))
Est-ce que c'est bon jusque la?

Je pense que c'est pas bon...
- 1 - Le "contour d'une droite", c'est plutôt maladroit comme appélation, mais c'est pas le problème.
- 2 - On tire aléatoirement des couples de pixels !!! Et on calcule l'équation de la droite passant pas ces deux points en coordonnée polaire. Donc Theta est l'angle formé par la droite avec l'axe des x et rho la coordonnée en x du point d'intersection de la droite avec l'axe des x.

-sur l'accumulateur
Pour chaque Ro et théta (de chaque pixel) j'incrémente mon accumulateur de 1 aprés je cherche les maximas de mon tableau.
Ca j'en suis pas sur j'ai pus trop compris à partir de la.

Ca en revanche ça m'a l'air correcte.


Bonne continuation...

[Danious]

Bonjour,

Personnellement, je voyais plus ça de la façon suivante :

Avec une matrice (initialisée à 0) dont les lignes représentent les valeurs de theta et les colonnes les valeurs de ro,
tu considère tous les theta, tous les ro possibles et tous les pixels (3 boucles imbriquées dans cet ordre). Si le pixel courant appartient (en tenant compte de l'erreur d'approximation) à ta droite (theta,ro) courante, alors tu incrémentes la valeur dans [theta][ro] dans ta matrice.

Evidemment, le calcul peut être très lourd s'il y a beaucoup de pixels du contour ou si tu testes beaucoup de theta différents par exemple. Tout dépend en fait de la précision qui est nécessaire dans ton cas.

[zolotaya]

En fait le truc sur la transformée de Hough, c'est qu'il y a deux facon de faire (si j'ai bien tout compris) :

- La premiere est celle que de Danious, a savoir qu'on prend tout les points de l'image. A partir de ces points, on fait varrié thetaen calculant Rho à chaque fois. On obtiens alors une sinusoide. L'intersection entre les sinusoide correspond aux droites. Le truc c'est qu'aprés il faut réussir à trouver les intersections correspondantes à nos droites et non celles qui se sont formées avec l'accumulation des sinusoides.

- La deuxieme est (je trouve) plus bourin mais plus efficace (d'aprés ce que j'ai compri). On prend tout les points de l'image (qui ne contients que les contours) et on trace toutes les droites possibles (ou seulement une parties pour aller plus vite en prenant des points aléatoirement). Pour chaque droite tracée, on calcule le Rho et le theta correspondant. On stocke chaque rho et chaque theta dans un tableau (l'accumulateur). On cherche ensuite dans ce dernier les maximas locaux qui nous "indique" une seule droite (par maxima^^).

J'ai dis des bétises ou pas? Si oui faut me le dire pour les corriger, c'est que j'ai pas tout compris...

Maintenant 2 petites questions :
Selon vous c'est quelle méthode la mieu?
Pourquoi recentre t'on en général le repère au centre de l'image au lieu de le laisser en haut à gauche?

[ToTo13]

Maintenant 2 petites questions :
Selon vous c'est quelle méthode la mieu?
Pourquoi recentre t'on en général le repère au centre de l'image au lieu de le laisser en haut à gauche?

1 - Aucune idée, je sais que ce que je t'ai donné fonctionne très bien.
2 - Est ce vraiment utile ? je pense que non, le changement de repère n'apporte aucune information ou facilité

[zolotaya]

J'ai une autre petite question qui peut parraitre simple:
Comment à partir des coordonnées polaire d'une droite je peux retrouver les coordonnées cartésiennes? (Soit sous la forme à y = a*x + b ou trouver X0 X1 et Y0 Y1)?

[ToTo13]

Bonjour,

ta droite en coordonnée polaire ressemble à ça : D(R, theta).
Theta est l'angle, il va donc t'apporter le coefficient directeur de ta droite cartésienne, donc tu te sers du cercle unité :
a = cos(Theta) / sin(Theta) ;
Ensuite tu sais que ta droite de forme y=ax+b passe par le point (R,0). Donc tu remplaces et trouves b.

[ol9245]

Je suis pas spécialiste mais cette question m'intéresse beaucoup. Je me permet donc d'amener mon grain de sel, plutôt de forme de questions aux quelques Dieux du traitement d'image qui hantent la bande passante de DVP :

J'avais en effet encore compris autre chose sur Hough. pour moi, il y avait deux méthodes possibles :

- Algo A (le classique ?) : pour tous les points, je calcule toutes les droites possibles passant par ce point et j'incémente leur accumulateur. Compexité N * 360 si j'ai un acumulateur par degré d'angle.

- Algo B (l'alternatif ? est-il utilisé ?) : pour toutes les paires de point, j'incrémente le seul acumulateur de la seule droite qui passe par ces deux points. Compexité N², mais possibilité de souséchantillonné ls points car il est prouvé que l'algorithme converge assez rapidement.

par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
N = collection des points de contour à traiter
NN = nombre de tirages de paires de points 
faire :
   tirer une paire de point P
   incrémenter l'accumulateur A de la droite passant par P
   si cet accumulateur a atteint un seuil déterminé alors faire :
        définir la droite D qui correspond à A
        identifier sur l'image les points qui appartiennent à D
        supprimer ces points de la collection N
        mette NN à zéro
   fin si
tant que NN / (N * N) < un_coefficient_a_déterminer_voisin_de_10_a_20_%

Dans tous les cas, ce que je vois dans ces algo, c'est que quand j'ai un accumulateur qui crache j'ai bien une droite, mais si ce sont les segments qui m'intéressent, il y a encore du taf...

[pseudocode]

@ol9245:

La "vraie" Transformée de Hough c'est plutot l'idée de l'algo A. C'est a dire, pour chaque point, identifier TOUTES les droites passant par ce point.

Dans le cas des droites, les solutions dans l'espace de Hough sont des sinusoides. On pourrait donc se contenter de stocker les Amplitude/Phase puis cacluler les intersections mathematiquement. Mais bon, c'est un peu compliqué donc on prefere passer par les accumulateurs.

On peut optimiser l'algo A en procedant par "zoom" successif dans l'espace de Hough (c'est a dire affinier le "pas" d'increment d'angle dans l'espace de l'image)

Une autre optimisation tres simple: faire la Transformée de Hough sur le gradient de l'image, puis prendre les lignes perpendiculaires. En effet, les lignes d'isophotes sont perpendiculaires aux lignes de gradient.

[Danious]

La "vraie" Transformée de Hough c'est plutot l'idée de l'algo A. C'est a dire, pour chaque point, identifier TOUTES les droites passant par ce point

C'est également équivalent (en définitive) à ce que j'avais proposé. Il semblerait qu'on soit tous d'accord sur le principe, mais pour les optimisations c'est un autre problème !

[zolotaya]

Bonjour, désolé de remancer ce sujet mais la je séche...
J'ai un (ou plusieurs) erreur dans mon code (ci dessous) et je n'arrive pas à trouver lesquels... Quelqu'un pourrait'il m'éclairer?
Le code est en JAVA

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
for (int x = 0; x < src.getWidth(); x++) {
	for (int y = 0; y < src.getHeight(); y++) {
		int col = src.getRGB(x, y);
		col = col & 0xFF;
		// Si le pixel n'est pas noir (n'appartient pas au fond)
		if (col > 0) {
			compt++;
			// On calcul theta 0 et Rho 0
			double rho0 = Math.sqrt((x*x) + (y*y));
			double theta0 = 2 *  Math.atan((y/rho0)/(1 + x/rho0));
			// On fait vairé theta pour les valeurs qui nous intéréssent
			for (int ang = 88; ang <= 92; ang++) {
				double theta = (ang*Math.PI/180);
				// On calcul la sinusoïde
				double rho = rho0 * Math.cos(theta - theta0);
				accu[(int)(rho+offset + 0.5)][ang - 88]++;
				compt1++;
			} // for angle
		} // if couleur
	} // for y
} // for x

Sinon quelqu'un aurait'il entendu parler de "l'analyse" de droite dans une image à l'aide de la méthode de chaînage?

[pseudocode]

sans avoir testé (ecriture en direct live), je dirais que ca devrait faire un truc comme ca:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
double maxRho = Math.sqrt( (Width/2)*(Width/2) + (Height/2)*(Height/2) );
 
 
for(int deg=0; deg<360; deg+=1) {
 
	double theta = Math.toRadians(deg);
 
	double rho = (x-Width/2)*Math.cos(theta) + (y-Height/2)*Math.sin(theta);
 
 
	int indexTheta = (int) ( theta/(2*Math.PI) * maxIndexTheta);
	int indexRho = (int) ( (1+rho/maxRho)/2 * maxIndexRho);
 
	acc[indexTheta][indexRho]++;
}

[zolotaya]

Merci pour ton code mais juste 2 petite questions :

maxIndexTheta et maxIndexRho sont initialisé comment et servent à quoi exactement?

Aprés tu initialise son maxRho à la diagonale de l'image ca ok, mais pourquoi travailles tu sur une image recentré et ne gardes tu pas ton origine en haut à gauche?
cf

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 double rho = (x-Width/2)*Math.cos(theta) + (y-Height/2)*Math.sin(theta);

[pseudocode]

Merci pour ton code mais juste 2 petite questions :

maxIndexTheta et maxIndexRho sont initialisé comment et servent à quoi exactement?

C'est la taille max du tableau acc[][].

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int indexTTTT= (int) ( TTTT * maxIndexTTTT);

avec 0<=TTTT<=1, donc indexTTTT varie entre 0 et maxIndexTTTT.

Aprés tu initialise son maxRho à la diagonale de l'image ca ok, mais pourquoi travailles tu sur une image recentré et ne gardes tu pas ton origine en haut à gauche?

maxRho est initialisé a la DEMI-diagonale, vu que j'ai recentré l'image.

Quand a savoir pourquoi je la recentre:
1. C'est une vieille habitude en traitement du signal
2. Ca me permet d'avoir un theta qui varie en 0 et 360°, et non pas entre 0 et 90°.

[hosni12]

slt svp je veux detecter plusieurs droites mais je n'arrive pas ,pouvez vous m'aider à resoudre le probleme ,je veux parcourir l'accumulateur et rechercher les max en stockant les indices necessaires dans une autre tableau de dim[i][3]
mais il m'a donné des plusieurs resultats non designé je veux extraire just les droites necessaire (les bords de route) et merci d'avance