1. #1
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut [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
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    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
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    avril 2005
    Messages
    4 154
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : avril 2005
    Messages : 4 154
    Points : 6 240
    Points
    6 240

    Par défaut

    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
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    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 Avatar de Electroniktor
    Profil pro
    Inscrit en
    juin 2007
    Messages
    150
    Détails du profil
    Informations personnelles :
    Âge : 24
    Localisation : France

    Informations forums :
    Inscription : juin 2007
    Messages : 150
    Points : 55
    Points
    55

    Par défaut

    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
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    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 Avatar de Electroniktor
    Profil pro
    Inscrit en
    juin 2007
    Messages
    150
    Détails du profil
    Informations personnelles :
    Âge : 24
    Localisation : France

    Informations forums :
    Inscription : juin 2007
    Messages : 150
    Points : 55
    Points
    55

    Par défaut

    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
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    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
    Homme Profil pro
    Inscrit en
    mars 2006
    Messages
    134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : mars 2006
    Messages : 134
    Points : 122
    Points
    122

    Par défaut

    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
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    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
    Inscrit en
    juin 2008
    Messages
    52
    Détails du profil
    Informations forums :
    Inscription : juin 2008
    Messages : 52
    Points : 32
    Points
    32

    Par défaut

    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
    Inscrit en
    novembre 2006
    Messages
    3
    Détails du profil
    Informations forums :
    Inscription : novembre 2006
    Messages : 3
    Points : 4
    Points
    4

    Par défaut

    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
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    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
    Inscrit en
    novembre 2006
    Messages
    3
    Détails du profil
    Informations forums :
    Inscription : novembre 2006
    Messages : 3
    Points : 4
    Points
    4

    Par défaut

    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
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    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
    Inscrit en
    novembre 2006
    Messages
    3
    Détails du profil
    Informations forums :
    Inscription : novembre 2006
    Messages : 3
    Points : 4
    Points
    4

    Par défaut

    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
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 027
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 027
    Points : 15 578
    Points
    15 578

    Par défaut

    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
    Profil pro
    Inscrit en
    septembre 2009
    Messages
    20
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2009
    Messages : 20
    Points : 8
    Points
    8

    Par défaut

    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

Discussions similaires

  1. [Débutant] detection de lignes dans une image binaire par T.hough
    Par m_baadeche dans le forum Images
    Réponses: 2
    Dernier message: 07/12/2010, 09h32
  2. Réponses: 2
    Dernier message: 10/11/2006, 14h23
  3. [Traitement D'images] Rechercher une ligne vide
    Par nico-pyright(c) dans le forum Général Algorithmique
    Réponses: 7
    Dernier message: 22/12/2005, 17h10
  4. nombres d'images sur une lign automatique
    Par AnKhCHFR dans le forum Balisage (X)HTML et validation W3C
    Réponses: 2
    Dernier message: 10/03/2005, 11h52
  5. [Image]Dessiner une ligne en dynamique
    Par Bugmaster dans le forum AWT/SWING
    Réponses: 8
    Dernier message: 02/08/2004, 11h56

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo