Discussion :

[jokoss]

Bonjour à tous,

Je m'intéresse en ce moment à la transformée de hough dans le cadre de la détection de lignes.

Après avoir épluché pas mal de documents traîtant le sujet, je pense avoir asse bien compris le principe mais malheureusement je sèche 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 compréhensible. Imaginons 3 points P1(0,1) P2(1,3) P3(2,5). Ces points sont alignés et forme une droite d'équation y = 2x+1. Donc voilà je me lance dans le développement.

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

Code :

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

1
2
3
4
5
 
double maxRho = sqrt( width_input*width_input + height_input*height_input );
double maxIndexTheta=180;
int maxIndexRho=(int)maxRho;
int acc[maxIndexTheta][maxIndexRho];

Ensuite voici mon algo:

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
for (i = 0; i < maxIndexTheta ; i++){
       for (j = 0 ; j < maxIndexRho ; j++){
        acc[i][j] = 0;
    }
} 
 
// parcourt en hauteur de l'image    
for(i=0;i<height_input;i++) {
    // parcourt une ligne
    for(j=0;j<width_input;j++) {
 
        if (image[i*width_input+j] == 0) {
 
            continue;
        }
        // boucle sur les angles theta.                            
        for(indexTheta=0; indexTheta<maxIndexTheta; indexTheta+=1) {
 
                theta = (2*PI*indexTheta)/maxIndexTheta;
 
                // compute corresponding rho value
                rho = j*cos(theta) + i*sin(theta);
 
                if (rho<0) continue;
 
                // ligne reprise de la rubrique contribuez (pas entièrement comprise) une sorte d'arrondi à l'unité supérieur?
                indexRho = (int) (0.5 + (rho* maxIndexRho/maxRho) );
 
                // Pourquoi faire un test sur "indexThetaRad" alors que c'est déja le gardien de la boucle?)
                if (indexTheta<maxIndexTheta && indexRho<maxIndexRho) {
                    acc[indexTheta][indexRho]++;
                }
            }
 
        }
    }

Je pense que j'ai un problème du coté du calcul du rho. En effet pour des petites valeurs de (x, y) (ici appelée (i, j)), les valeurs de rho quelque soit le theta sont très basses. Dans le cas extrême du point (0,0) , tous les rho valent 0 --> ne ressemble pas trop à une sinusoïde .

Enfin voilà , si quelqu'un pouvait me dire où j'ai faux ou bien me donner les résultats 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 implémentation de reference.

Code :

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

1
2
3
4
5
6
7
8
 
// ligne reprise de la rubrique contribuez (pas entièrement comprise) une sorte d'arrondi à l'unité supérieur?
indexRho = (int) (0.5 + (rho* maxIndexRho/maxRho) );
 
// Pourquoi faire un test sur "indexThetaRad" alors que c'est déja le gardien de la boucle?)
if (indexTheta<maxIndexTheta && indexRho<maxIndexRho) {
    acc[indexTheta][indexRho]++;
}

Les 2 remarques sont pertinentes. Ces calculs/tests supplémentaires 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 problème du coté du calcul du rho. En effet pour des petites valeurs de (x, y) (ici appelée (i, j)), les valeurs de rho quelque soit le theta sont très basses. Dans le cas extrême du point (0,0) , tous les rho valent 0 --> ne ressemble pas trop à une sinusoïde .

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 représentées par les valeurs entre (0,0) et (0,180°)

[jokoss]

Bonjour,

merci pour tes réponses.

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.

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
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
 
indexTheta = 0, rho = 1.000000, indexRho = 1
 indexTheta = 1, rho = 1.034290, indexRho = 1
 indexTheta = 2, rho = 1.067320, indexRho = 1
 indexTheta = 3, rho = 1.099050, indexRho = 1
 indexTheta = 4, rho = 1.129441, indexRho = 1
 indexTheta = 5, rho = 1.158456, indexRho = 1
 indexTheta = 6, rho = 1.186059, indexRho = 1
 indexTheta = 7, rho = 1.212217, indexRho = 1
 indexTheta = 8, rho = 1.236899, indexRho = 1
 indexTheta = 9, rho = 1.260073, indexRho = 1
 indexTheta = 10, rho = 1.281713, indexRho = 1
 indexTheta = 11, rho = 1.301790, indexRho = 1
 indexTheta = 12, rho = 1.320282, indexRho = 1
 indexTheta = 13, rho = 1.337165, indexRho = 1
 indexTheta = 14, rho = 1.352419, indexRho = 1
 indexTheta = 15, rho = 1.366025, indexRho = 1
 indexTheta = 16, rho = 1.377967, indexRho = 1
 indexTheta = 17, rho = 1.388230, indexRho = 1
 indexTheta = 18, rho = 1.396802, indexRho = 1
 indexTheta = 19, rho = 1.403672, indexRho = 1
 indexTheta = 20, rho = 1.408832, indexRho = 1
 indexTheta = 21, rho = 1.412275, indexRho = 1
 indexTheta = 22, rho = 1.413998, indexRho = 1
 indexTheta = 23, rho = 1.413998, indexRho = 1
 indexTheta = 24, rho = 1.412275, indexRho = 1
 indexTheta = 25, rho = 1.408832, indexRho = 1
 indexTheta = 26, rho = 1.403672, indexRho = 1
 indexTheta = 27, rho = 1.396802, indexRho = 1
 indexTheta = 28, rho = 1.388231, indexRho = 1
 indexTheta = 29, rho = 1.377968, indexRho = 1
 indexTheta = 30, rho = 1.366026, indexRho = 1
 indexTheta = 31, rho = 1.352420, indexRho = 1
 indexTheta = 32, rho = 1.337166, indexRho = 1
 indexTheta = 33, rho = 1.320283, indexRho = 1
 indexTheta = 34, rho = 1.301791, indexRho = 1
 indexTheta = 35, rho = 1.281713, indexRho = 1
 indexTheta = 36, rho = 1.260074, indexRho = 1
 indexTheta = 37, rho = 1.236900, indexRho = 1
 indexTheta = 38, rho = 1.212218, indexRho = 1
 indexTheta = 39, rho = 1.186060, indexRho = 1
 indexTheta = 40, rho = 1.158457, indexRho = 1
 indexTheta = 41, rho = 1.129442, indexRho = 1
 indexTheta = 42, rho = 1.099051, indexRho = 1
 indexTheta = 43, rho = 1.067322, indexRho = 1
 indexTheta = 44, rho = 1.034292, indexRho = 1
 indexTheta = 45, rho = 1.000001, indexRho = 1
 indexTheta = 46, rho = 0.964493, indexRho = 1
 indexTheta = 47, rho = 0.927809, indexRho = 1
 indexTheta = 48, rho = 0.889995, indexRho = 1
 indexTheta = 49, rho = 0.851097, indexRho = 1
 indexTheta = 50, rho = 0.811161, indexRho = 1
 indexTheta = 51, rho = 0.770238, indexRho = 1
 indexTheta = 52, rho = 0.728376, indexRho = 1
 indexTheta = 53, rho = 0.685626, indexRho = 1
 indexTheta = 54, rho = 0.642042, indexRho = 1
 indexTheta = 55, rho = 0.597675, indexRho = 1
 indexTheta = 56, rho = 0.552579, indexRho = 1
 indexTheta = 57, rho = 0.506811, indexRho = 1
 indexTheta = 58, rho = 0.460425, indexRho = 0
 indexTheta = 59, rho = 0.413478, indexRho = 0
 indexTheta = 60, rho = 0.366028, indexRho = 0
 indexTheta = 61, rho = 0.318131, indexRho = 0
 indexTheta = 62, rho = 0.269847, indexRho = 0
 indexTheta = 63, rho = 0.221234, indexRho = 0
 indexTheta = 64, rho = 0.172352, indexRho = 0
 indexTheta = 65, rho = 0.123260, indexRho = 0
 indexTheta = 66, rho = 0.074017, indexRho = 0
 indexTheta = 67, rho = 0.024684, indexRho = 0
 indexTheta = 158, rho = 0.024675, indexRho = 0
 indexTheta = 159, rho = 0.074008, indexRho = 0
 indexTheta = 160, rho = 0.123250, indexRho = 0
 indexTheta = 161, rho = 0.172343, indexRho = 0
 indexTheta = 162, rho = 0.221225, indexRho = 0
 indexTheta = 163, rho = 0.269838, indexRho = 0
 indexTheta = 164, rho = 0.318122, indexRho = 0
 indexTheta = 165, rho = 0.366019, indexRho = 0
 indexTheta = 166, rho = 0.413469, indexRho = 0
 indexTheta = 167, rho = 0.460416, indexRho = 0
 indexTheta = 168, rho = 0.506802, indexRho = 1
 indexTheta = 169, rho = 0.552571, indexRho = 1
 indexTheta = 170, rho = 0.597666, indexRho = 1
 indexTheta = 171, rho = 0.642033, indexRho = 1
 indexTheta = 172, rho = 0.685618, indexRho = 1
 indexTheta = 173, rho = 0.728368, indexRho = 1
 indexTheta = 174, rho = 0.770230, indexRho = 1
 indexTheta = 175, rho = 0.811154, indexRho = 1
 indexTheta = 176, rho = 0.851089, indexRho = 1
 indexTheta = 177, rho = 0.889988, indexRho = 1
 indexTheta = 178, rho = 0.927802, indexRho = 1
 indexTheta = 179, rho = 0.964486, indexRho = 1

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

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
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
 
indexTheta = 0, rho = 2.000000, indexRho = 2
indexTheta = 1, rho = 2.068581, indexRho = 2
indexTheta = 2, rho = 2.134641, indexRho = 2
indexTheta = 3, rho = 2.198101, indexRho = 2
indexTheta = 4, rho = 2.258882, indexRho = 2
indexTheta = 5, rho = 2.316912, indexRho = 2
indexTheta = 6, rho = 2.372118, indexRho = 2
indexTheta = 7, rho = 2.424435, indexRho = 2
indexTheta = 8, rho = 2.473798, indexRho = 2
indexTheta = 9, rho = 2.520147, indexRho = 3
indexTheta = 10, rho = 2.563425, indexRho = 3
indexTheta = 11, rho = 2.603581, indexRho = 3
indexTheta = 12, rho = 2.640564, indexRho = 3
indexTheta = 13, rho = 2.674330, indexRho = 3
indexTheta = 14, rho = 2.704838, indexRho = 3
indexTheta = 15, rho = 2.732050, indexRho = 3
indexTheta = 16, rho = 2.755934, indexRho = 3
indexTheta = 17, rho = 2.776461, indexRho = 3
indexTheta = 18, rho = 2.793604, indexRho = 3
indexTheta = 19, rho = 2.807344, indexRho = 3
indexTheta = 20, rho = 2.817664, indexRho = 3
indexTheta = 21, rho = 2.824551, indexRho = 3
indexTheta = 22, rho = 2.827996, indexRho = 3
indexTheta = 23, rho = 2.827996, indexRho = 3
indexTheta = 24, rho = 2.824551, indexRho = 3
indexTheta = 25, rho = 2.817664, indexRho = 3
indexTheta = 26, rho = 2.807345, indexRho = 3
indexTheta = 27, rho = 2.793605, indexRho = 3
indexTheta = 28, rho = 2.776461, indexRho = 3
indexTheta = 29, rho = 2.755935, indexRho = 3
indexTheta = 30, rho = 2.732051, indexRho = 3
indexTheta = 31, rho = 2.704839, indexRho = 3
indexTheta = 32, rho = 2.674331, indexRho = 3
indexTheta = 33, rho = 2.640565, indexRho = 3
indexTheta = 34, rho = 2.603582, indexRho = 3
indexTheta = 35, rho = 2.563427, indexRho = 3
indexTheta = 36, rho = 2.520148, indexRho = 3
indexTheta = 37, rho = 2.473800, indexRho = 2
indexTheta = 38, rho = 2.424437, indexRho = 2
indexTheta = 39, rho = 2.372120, indexRho = 2
indexTheta = 40, rho = 2.316914, indexRho = 2
indexTheta = 41, rho = 2.258884, indexRho = 2
indexTheta = 42, rho = 2.198103, indexRho = 2
indexTheta = 43, rho = 2.134643, indexRho = 2
indexTheta = 44, rho = 2.068583, indexRho = 2
indexTheta = 45, rho = 2.000003, indexRho = 2
indexTheta = 46, rho = 1.928985, indexRho = 2
indexTheta = 47, rho = 1.855618, indexRho = 2
indexTheta = 48, rho = 1.779990, indexRho = 2
indexTheta = 49, rho = 1.702193, indexRho = 2
indexTheta = 50, rho = 1.622323, indexRho = 2
indexTheta = 51, rho = 1.540475, indexRho = 2
indexTheta = 52, rho = 1.456751, indexRho = 1
indexTheta = 53, rho = 1.371253, indexRho = 1
indexTheta = 54, rho = 1.284083, indexRho = 1
indexTheta = 55, rho = 1.195349, indexRho = 1
indexTheta = 56, rho = 1.105159, indexRho = 1
indexTheta = 57, rho = 1.013622, indexRho = 1
indexTheta = 58, rho = 0.920850, indexRho = 1
indexTheta = 59, rho = 0.826957, indexRho = 1
indexTheta = 60, rho = 0.732056, indexRho = 1
indexTheta = 61, rho = 0.636263, indexRho = 1
indexTheta = 62, rho = 0.539694, indexRho = 1
indexTheta = 63, rho = 0.442469, indexRho = 0
indexTheta = 64, rho = 0.344704, indexRho = 0
indexTheta = 65, rho = 0.246519, indexRho = 0
indexTheta = 66, rho = 0.148034, indexRho = 0
indexTheta = 67, rho = 0.049368, indexRho = 0
indexTheta = 158, rho = 0.049350, indexRho = 0
indexTheta = 159, rho = 0.148015, indexRho = 0
indexTheta = 160, rho = 0.246500, indexRho = 0
indexTheta = 161, rho = 0.344685, indexRho = 0
indexTheta = 162, rho = 0.442450, indexRho = 0
indexTheta = 163, rho = 0.539676, indexRho = 1
indexTheta = 164, rho = 0.636244, indexRho = 1
indexTheta = 165, rho = 0.732038, indexRho = 1
indexTheta = 166, rho = 0.826939, indexRho = 1
indexTheta = 167, rho = 0.920833, indexRho = 1
indexTheta = 168, rho = 1.013605, indexRho = 1
indexTheta = 169, rho = 1.105142, indexRho = 1
indexTheta = 170, rho = 1.195332, indexRho = 1
indexTheta = 171, rho = 1.284066, indexRho = 1
indexTheta = 172, rho = 1.371236, indexRho = 1
indexTheta = 173, rho = 1.456735, indexRho = 1
indexTheta = 174, rho = 1.540460, indexRho = 2
indexTheta = 175, rho = 1.622307, indexRho = 2
indexTheta = 176, rho = 1.702178, indexRho = 2
indexTheta = 177, rho = 1.779975, indexRho = 2
indexTheta = 178, rho = 1.855604, indexRho = 2
indexTheta = 179, rho = 1.928972, indexRho = 2

Ce qui me gêne c'est que l'on traîte un rho = 1.5 ou rho = 2.4 de la même manière, à 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 différentes?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
IndexTheta = 63, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3
IndexTheta = 64, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3
IndexTheta = 65, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3
IndexTheta = 66, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3
IndexTheta = 67, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3
IndexTheta = 158, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3
IndexTheta = 159, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3
IndexTheta = 160, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3
IndexTheta = 161, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3
IndexTheta = 162, IndexRho = 0, acc[IndexTheta ][IndexRho ] = 3

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 zéro 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" négatifs, tu peux restreindre l'anglet entre 0 et 180°

Pour ton problème d'arrondi, il faut voir que l'algo de Hough repose sur un système de "votes" discrétisés. Ca a du sens pour une image "bitmap" car il n'y a pas de différences "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 coordonnée et que je tranfère dans un repère a,b, j'aurai un seul maximum en (1,0), ce qui me donnerai y = 1*x+0.

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
 
IndexTheta = 125, IndexRho = 0, acc[i][j] = 3
IndexTheta = 126, IndexRho = 0, acc[i][j] = 3
IndexTheta = 127, IndexRho = 0, acc[i][j] = 3
IndexTheta = 128, IndexRho = 0, acc[i][j] = 3
IndexTheta = 129, IndexRho = 0, acc[i][j] = 3
IndexTheta = 130, IndexRho = 0, acc[i][j] = 3
IndexTheta = 131, IndexRho = 0, acc[i][j] = 3
IndexTheta = 132, IndexRho = 0, acc[i][j] = 3
IndexTheta = 133, IndexRho = 0, acc[i][j] = 3
IndexTheta = 134, IndexRho = 0, acc[i][j] = 3
IndexTheta = 135, IndexRho = 0, acc[i][j] = 3
IndexTheta = 316, IndexRho = 0, acc[i][j] = 3
IndexTheta = 317, IndexRho = 0, acc[i][j] = 3
IndexTheta = 318, IndexRho = 0, acc[i][j] = 3
IndexTheta = 319, IndexRho = 0, acc[i][j] = 3
IndexTheta = 320, IndexRho = 0, acc[i][j] = 3
IndexTheta = 321, IndexRho = 0, acc[i][j] = 3
IndexTheta = 322, IndexRho = 0, acc[i][j] = 3
IndexTheta = 323, IndexRho = 0, acc[i][j] = 3
IndexTheta = 324, IndexRho = 0, acc[i][j] = 3
IndexTheta = 325, IndexRho = 0, acc[i][j] = 3

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

Code :

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

1
2
3
 
rho = ( rho/maxIndexRho )*maxRho = 0;
theta = ( theta/maxIndexTheta )*2*PI = 5;

et donc

Code :

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

1
2
3
 
a = -cos(theta )/sin(theta ) = 0.29;
b = rho/sin(theta ) = 0;

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)

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
23
24
25
26
27
28
29
30
31
1 1 1 0 0 0 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 0 0 0 0 0 
1 1 0 1 0 0 0 0 0 0 0 0 0 0 
1 1 0 1 0 0 0 0 0 0 0 0 0 0 
1 1 0 1 0 0 0 0 0 0 0 0 0 0 
1 1 0 1 0 0 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 0 0 0 0 0 
1 2 0 0 0 0 0 0 0 0 0 0 0 0 
2 1 0 0 0 0 0 0 0 0 0 0 0 0 
3 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 
3 0 0 0 0 0 0 0 0 0 0 0 0 0 
2 1 0 0 0 0 0 0 0 0 0 0 0 0 
1 2 0 0 0 0 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 0 0 0 0 0

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 très voisines, qu'on peut fusionner (moyenne):

y = 1.0577157269468138.x - 0.0392735248563596

[jokoss]

j'obtiens le même 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 consécutifs. Peut être que chaque groupe doit être considéré comme une seule droite (prendre la moyenne de chaque groupe?)

Sinon, comment connaître la taille optimale de l'accumulateur?

En ayant le même tableau que toi j'ai encore la même équation de droite avec a = 0.3 donc le bug doit se situer à la transformation finale, je vais regarder ca de plus près.

[pseudocode]

Sinon, comment connaître 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 problème dans la reconversion dans le système (x,y)

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

Code :

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

1
2
3
 
rho = ( rho/maxIndexRho )*maxRho = 0
theta = ( theta /maxIndexTheta )*2*PI = (11/31)*2*PI = 2.229515

-->

Code :

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

1
2
3
 
a = -cos(theta)/sin(theta) = 0.7738
b = rho /sin(theta) = 0

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 précision sur les tailles d'accumulateur. C'est vrai que je l'avais déjà 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.

Code java :

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

1
2
3
4
5
6
7
 
public double[] winner() {
/* ... */
double rho   = ( (winrho+0.5)/maxIndexRho )*maxRho;
double theta = ( (wintheta+0.5)/maxIndexTheta )*2*Math.PI;
/* ... */
}

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

[jokoss]

merci beaucoup , ca fonctionne.

J'ai malheureusement un dernier(du moins j'espère) petit problème.

En fait je n'ai pas exactement le même tableau que toi (rho-theta).
J'ai bien comme premier point (0,11) mais comme deuxième j'ai (0,28) à la place de (0,27), ce qui change beaucoup le résultat.

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,

Code :

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

1
2
3
 
theta = (2*PI*indexTheta)/maxIndexTheta = 5.4724
rho = j*cos(theta) + i*sin(theta) = -0.035832

Pourrais-tu me dire à quel moment tes résultats diffèrent-ils des miens?

[pseudocode]

Pourrais-tu me dire à quel moment tes résultats diffèrent-ils des miens?

Ah. j'avais oublié de reporter l'approximation dans le remplissage des accumulateurs . Faut que j'arrete de faire 3 trucs en même temps.

Code java :

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

1
2
3
4
 
for(int indexTheta=0; indexTheta<maxIndexTheta; indexTheta+=1) {
	double theta = (2*Math.PI*(indexTheta+0.5))/maxIndexTheta;
	/* ...*/

[jokoss]

Parfait ça fonctionne très bien.

Un tout grand merci!

Je fais quelques tests plus compliqués et je mets en résolu.

[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

Après 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 érronées.

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

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

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

[pseudocode]

Seul le troisième 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 près d'un maxima, et il faut en extraire les coordonnées 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 "collés" alors que l'image est tres grande. Donc la detection ne va pas etre très fiable. Si tu es souvent dans ce cas, il y a d'autre variante de Hough qui sont mieux adaptées.

[jokoss]

d'accord je comprend bien, dans mon cas je n'aurai pas des points collés comme ceci, c'est vraiment à titre de petit exemple pour mieux maîtriser les résultats.

SI je prend des points assez petits (2,5) (3,7) et (4,9) , la transformée me donne un bon résultats, à savoir y = 2.11*x+1.16

Mais si j'essaye avec des points plus espacés, les résultats deviennent vraiment étrange. exemple : (2, 5) (10, 21) et (18, 37)

Avec maxIndexTheta = 71, maxRho = 806 (obtenus par les calculs précédents), 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 dépasse 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'après 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 dépasse pas 1 dans aucune de ces cases.

Le problème 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 résolution de la discrétisation, on se retrouve avec un amas dont l'extrema est plus simple a trouver. Ce genre de problème arrive moins fréquemment 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 suggère l'approche souvent proposée 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 résultats très précis car on remplit seulement l'accumulateur correspondant EXACTEMENT a une droite.

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

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
 
private void vote(int x0,int y0, int x1, int y1) {
	// calcul du (rho,theta) pour la droite (x0,y0)-(x1,y1)
	double theta= Math.PI - Math.atan2(x1-x0, y1-y0);
	double rho = x0*Math.cos(theta) + y0*Math.sin(theta);
	if (rho<0) {
		rho=-rho;
		theta=(theta+Math.PI)%(2*Math.PI);
	}
 
 
	// (rho,theta) -> index
	int indexTheta  = (int) (0.5 + (theta/(2*Math.PI)) * maxIndexTheta  );
	int indexRho    = (int) (0.5 + (rho/maxRho) * maxIndexRho  );
 
	acc[indexRho][indexTheta]++;
	if (acc[indexRho][indexTheta]>highestvote)
		highestvote=acc[indexRho][indexTheta];
	}
}

[jokoss]

ok merci pour l'information.

En testant sur un cas réel (plusieurs milliers de points), j' ai encore des soucis avec la première version de la transformée. D'après ce que je comprend la technique peut donner des résultats érronés principalement si il n' y a pas beaucoup de point. Hors dans mon cas ça marche très bien avec (de nouveau theta = 360) sinon pour d'autres valeurs, j'ai tout de même un très bon coeficient a mais le b n'est pas bon.

J'ai mis en pièce jointe une image typique à traiter.

Peux tu me dire s'il est normal avec ce type d'images d'obtenir de mauvais résultats 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 réduis encore ces dimensions pour avoir quelquechose qui tienne en mémoire.