Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez Discussion :

[image] Détecteur de Ligne (Hough)


Sujet :

Contribuez

  1. #1
    Rédacteur

    [image] Détecteur de Ligne (Hough)
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #2
    Rédacteur

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

    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

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

  4. #4
    Rédacteur

    Citation Envoyé par PRomu@ld Voir le message
    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, ...)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre du Club
    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 !

  6. #6
    Rédacteur

    Citation Envoyé par Electroniktor Voir le message

    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Membre du Club
    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 !

  8. #8
    Rédacteur

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

    les sources du jar

    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Membre régulier
    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

  10. #10
    Rédacteur

    Citation Envoyé par ale2000 Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  11. #11
    Nouveau membre du Club
    Citation Envoyé par pseudocode Voir le message
    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?

  12. #12
    Candidat au Club
    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
    	}
    }

  13. #13
    Rédacteur

    Citation Envoyé par hipish Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  14. #14
    Candidat au Club
    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

  15. #15
    Rédacteur

    Citation Envoyé par hipish Voir le message
    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);
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  16. #16
    Candidat au Club
    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};
    	}

  17. #17
    Rédacteur

    Citation Envoyé par hipish Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  18. #18
    Futur Membre du Club
    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

  19. #19
    Nouveau Candidat au Club
    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?

###raw>template_hook.ano_emploi###