Discussion :

[pseudocode]

Une implémentation Java de l'algorithme de la transformée de Hough

Code java :

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
/**
 * Hough Transform
 * 
 * @author Xavier Philippeau
 *
 */
public class Hough {
 
	// image size
	private int Width,Height;
 
	// max Rho walue (= length of the diagonal)
	private double maxRho;
 
	// size of the accumulators array
	private int maxIndexTheta,maxIndexRho;
 
	// accumulators array
	int[][] acc;
 
	/**
         * Constructor
         * 
         * @param width,height Size of the image
         */
	public Hough(int width,int height) {
		this.Width=width;
		this.Height=height;
 
		this.maxRho = Math.sqrt( width*width + height*height );
		this.maxIndexTheta=360; // precision : 1 degree by cell
		this.maxIndexRho=(int)(1+this.maxRho); // precision : 1 pixel by cell
		this.acc = new int[maxIndexTheta][maxIndexRho];
	}
 
	/**
         * pixel vote
         * 
         * @param x,y coordinates of the pixel
         */
	public void vote(int x,int y) {
		// use origin = center of the image
		x-=Width/2;	y-=Height/2;
 
		// for each theta value
		for(int indexTheta=0; indexTheta<maxIndexTheta; indexTheta+=1) {
			double theta = ((double)indexTheta/maxIndexTheta)*Math.PI;
 
			// compute corresponding rho value
			double rho = x*Math.cos(theta) + y*Math.sin(theta);
 
			// rho -> index
			int indexRho   = (int) (0.5 + (rho/this.maxRho + 0.5)*this.maxIndexRho );
 
			// increment accumulator
			acc[indexTheta][indexRho]++;
		}
	}
 
	/**
         * retrieve winner
         * 
         * @return array={rho,theta}  
         */
	public double[] winner() {
		// parsing the accumulators for max accumulator
		double max=0, winrho=0, wintheta=0;
		for(int r=0;r<maxIndexRho;r++) {
			for(int t=0;t<maxIndexTheta;t++) {
				if (acc[t][r]<max) continue;
				max=acc[t][r];
				winrho=r;
				wintheta=t;
			}
		}
 
		// indexes -> (rho,theta)
		double rho   = ((double)winrho/this.maxIndexRho - 0.5)*this.maxRho;
		double theta = ((double)wintheta/this.maxIndexTheta)*Math.PI;
 
		return new double[] {rho,theta};
	}
 
	// convert (rho,theta) to (a,b) such that Y=a.X+b
	public double[] rhotheta_to_ab(double rho, double theta) {
		double a=0,b=0;
		if(Math.sin(theta)!=0) {
			a = -Math.cos(theta)/Math.sin(theta);
			b = rho/Math.sin(theta)+Height/2-a*Width/2; // use origin = (0,0)
		} else {
			a=Double.MAX_VALUE;
			b=0;
		}
		return new double[] {a,b};
	}
}

Un exemple d'utilisation:

Code java :

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
23
24
25
26
27
28
 
int width=800, height=600;
 
Hough hough = new Hough(width,height);
 
double a = 0.3;
double b = 50;
 
Random rand = new Random(0);
for(int i=0;i<100;i++) {
	double noise = 5*rand.nextGaussian();
 
	int x = rand.nextInt(width);
	int y = (int)(a*x + b + noise );
	if (y<0 || y>=height) {i--;continue;}
 
	hough.vote(x,y);
}
 
double[] rhotheta = hough.winner();
double rho = rhotheta[0];
double theta = rhotheta[1];
 
double[] ab = hough.rhotheta_to_ab(rho, theta);;
double estimated_a = ab[0];
double estimated_b = ab[1];
 
System.out.println(a+","+b+" --> "+estimated_a+","+estimated_b);

Résultat:

0.3,50.0 --> 0.3057306814586603,50.78310362713681

Edit: mise a jour du code. Utilisation de l'espace de hough: rho positif/négatif et 0<=theta<PI.

[pseudocode]

L'implémentation sous forme d'un JAR executable: hough.jar

[PRomu@ld]

Est ce que le passage de la reconnaissance d'une droite à un cercle (une ellipse, ...) nécessite des changements importants dans le code ?

[pseudocode]

Est ce que le passage de la reconnaissance d'une droite à un cercle (une ellipse, ...) nécessite des changements importants dans le code ?

Pour détecter un cercle, il faut un espace de Hough de dimension 3 afin de déterminer les 3 paramètres (centre_x,centre_y,rayon). Les équations sont aussi simples que celles des droites (voir même plus simple).

pour chaque pixel (x,y) de l'image, le centre du cercle "candidat" se trouve a une distance "R" de (x,y). Donc les votes sont les valeurs (a,b,r) telles que (a,b) soit sur un cercle de rayon "r" centré en (x,y). Ça dessine un cône vertical dans l'espace de Hough.

Pour les ellipses je ne sais pas. Je ne l'ai jamais fait.

A noter que la recherche des maxima dans l'espace de Hough devient vite très longue. C'est le cas aussi pour les droites sur de grandes images). Il convient donc d'utiliser des techniques plus évoluées que le simple parcours, par exemple le QuadTree.

A noter également que si l'image contient beaucoup de droites/cercles, la recherche des maxima devient délicate: multiples valeurs très proches, approximations de la discrétisation, ... Il convient la aussi d'employer des techniques plus poussées (interpolation, zéro de la dérivée, mean-shift, ...)

[Electroniktor]

Bonjour !

maxIndexTheta=(int)(2*Math.PI/Math.atan2(1, Math.max(height,width)))/scale;

Est-ce normal que je trouve un nombre négatif ?

En C cela me donne cela :

Code :

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

theta = (2 * 3.14 / atan2 (1, max (height, width))) / scale;

Merci d'avance !

[pseudocode]

Est-ce normal que je trouve un nombre négatif ?

En C cela me donne cela :

Code :

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

theta = (2 * 3.14 / atan2 (1, max (height, width))) / scale;

Non ce n'est pas normal, si toutes les variables sont positive, alors le résultat doit l'être aussi.

Pour ceux qui se demandent d'ou vient cette formule barbare, j'ai choisi de faire une approximation simpliste du plus petit angle (non nul) entre 2 droites.

Dans le cas ou width>height, c'est l'angle entre la ligne 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.

[Electroniktor]

OK merci pour ces explications !

Et j'ai trouvé l'origine du problème : scale valait 0 !
J'ai donc ajouté une sécurité pour éviter ce problème !

Bon ben il ne me reste plus qu'a finir de coder l'algo !

[pseudocode]

Puisque plusieurs personnes me l'ont demandé, voici les sources du JAR (avec la detection de plusieurs lignes)

les sources du jar

[ale2000]

merci pseudocode pour cette contribution.
Je ne sais pas pourquoi, mais je faisais un bloquage sur Hough et là ... tout est limpide ..., à la vue des droites dans l'espace de hough, on comprend le comment du pourquoi

Great

[pseudocode]

merci pseudocode pour cette contribution.
Je ne sais pas pourquoi, mais je faisais un bloquage sur Hough et là ... tout est limpide ..., à la vue des droites dans l'espace de hough, on comprend le comment du pourquoi

Merci... Je ne pensais pas que voir l'espace de de Hough aiderait à comprendre l'algorithme, mais tant mieux.

[afef_master]

Merci... Je ne pensais pas que voir l'espace de de Hough aiderait à comprendre l'algorithme, mais tant mieux.

bonjour,
Merci bcp pseudocode pour cette contribution et surtout concernant la detection des lignes à travers la methode de hough.
mais moi j'ai besoin de tous ca en Matlab vous n'avez pas d'idée?

[hipish]

salut tout le monde, est-ce que quelqu'un peut me dire pourquoi on a choisi ||gradient||^2 > 64^2 ? Comment on sais que ||gradient|| = 64 ??!!!!

Code java :

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

1
2
3
4
5
6
7
8
9
// compute gradient (Sobel) + vote in Hough Space (if gradient>64)
for (int y=1;y<height-1;y++) {
	for (int x=1;x<width-1;x++) {
		int gv = (gray[x+1][y-1]-gray[x-1][y-1])+2*(gray[x+1][y]-gray[x-1][y])+(gray[x+1][y+1]-gray[x-1][y+1]);
		int gh = (gray[x-1][y+1]-gray[x-1][y-1])+2*(gray[x][y+1]-gray[x][y-1])+(gray[x+1][y+1]-gray[x+1][y-1]);
		int g2 = (gv*gv + gh*gh)/(16);
		if (g2>4096) this.hough.vote(x,y); // ||gradient||^2 > 64^2
	}
}

[pseudocode]

salut tout le monde, est-ce que quelqu'un peut me dire pourquoi on a choisi ||gradient||^2 > 64^2 ? Comment on sais que ||gradient|| = 64 ??!!!!

C'est une valeur que j'ai mise au hasard. La norme du gradient varie entre 0 et 256, donc 64 représente 25%. En dessous de ce seuil je considère que la norme du gradient est trop faible.


Edit: je viens de me rendre compte qu'il y a un erreur dans le calcul de "g2". Il faut diviser par (16) et pas par (4). J'ai corrigé le source.

[hipish]

Merci pour la correction su code, mais juste 2 petite questions :
-pourquoi travailles tu sur une image recentré ?
-dans se code pk on on ajoute 0.5? pk 0.5 et non pas une autre valeur comme par exp 1??

Code java :

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

1
2
3
4
5
6
public int RhoToIndex(double rho) { 
		return (int) (0.5 + (rho/this.maxRho + 0.5) * this.maxIndexRho );
}
public double IndexToRho(int index) {
	return ((double)index/this.maxIndexRho - 0.5)*this.maxRho;
}

j'ai vraimen besoin de comprendre, et merci d'avance

[pseudocode]

Merci pour la correction su code, mais juste 2 petite questions :
-pourquoi travailles tu sur une image recentré ?

Il n'y a pas de raison particulière. La première version de ce code utilisait le repère habituel ((0,0) en haut a gauche) et un espace de Hough (rho,theta) avec rho>=0 et 0<=theta<2PI.

Lorsque j'ai modifié l'espace de Hough (rho,theta) avec 0<=theta<PI et rho quelconque, j'ai centré l'image car c'était plus pratique pour me représenter mentalement les "rho négatifs".

-dans se code pk on on ajoute 0.5? pk 0.5 et non pas une autre valeur comme par exp 1??

C'est l'approximation usuelle pour la conversion réel/entier:

round(double x) = (int)floor(x+0.5);

[hipish]

merci beaucoup pseudocode pour cette contribution, et pour les explication

une dernière chose: dans ce code je pense qu'on dois alloué le tableau de Hough avec width et heigth pas avec width et width

Code Java :

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

1
2
3
4
5
6
// called by "Load Image"
private void doTH(BufferedImage img0) {
 
// new Hough Transformer
this.hough = new Hough(width,heigth);
.... }

et il y a une autre chose que je n'arrive pas a comprendre c'est comment tu ajouter à b: +Height/2-a*Width/2 d'aprés ce que je sais, b sera égale à rho/sin(theta) seulement...

Code Java :

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

1
2
3
4
5
6
rhotheta_to_ab(double rho, double theta) {
....
double a = -Math.cos(theta)/Math.sin(theta);
		double b = rho/Math.sin(theta)+Height/2-a*Width/2;
		return new double[] {a,b};
	}

[pseudocode]

une dernière chose: dans ce code je pense qu'on dois alloué le tableau de Hough avec width et heigth pas avec width et width

Oui tout a fait. J'ai codé l'interface rapidement alors il y a peut-etre d'autres coquilles.

et il y a une autre chose que je n'arrive pas a comprendre c'est comment tu ajouter à b: +Height/2-a*Width/2 d'aprés ce que je sais, b sera égale à rho/sin(theta) seulement...

J'ai centré les pixels lors du vote, il faut donc que j'en tienne compte pour calculer l'équation de la droite dans le repère original. Un vote pour la position (theta=?,rho=0) est un vote pour une droite qui passe par le milieu de l'écran.

[jujuj]

Hello j'ai besoin d'utiliser la transformée de Hough mais je ne sais pas comment coder ça en matlab, est ce que quelqu'un a une idée??
Thank you for your help

[Kim_rjs]

Bonjour,

JE suis en train de travailler sur le principe de la transformée de Hough et j'avoue que j'ai quelques difficultés à tout bien comprendre!
Deja la code que vous avez fourni m'aide beaucoup merci! Mais j'ai encore quelques points qui restent flou pour moi:
- qu'est ce que récupère la méthode "winner"? Est ce les valeurs de l'accumulateur supérieures au seuil indiqué?
- comment avez vous trouvé la formule correspondant à indexRho dans la méthode "vote"? Et celle de theta?