Discussion :

[saraza]

Bonjour,

Je suis bloqué depuis plusieurs sur un problème algorithmique, donc je viens solliciter votre aide


J'ai cette image qui est générée par un robot qui a un laser pour mesurer les distances.
Ces points représentent une pièce.

A partir de ces points, j'aimerais identifier les droites. (L'image est un exemple, ça dépend de la pièce)
J'ai regardé la transformée de Hough,avec notamment le framework Aforge.

Malheureusement je ne suis parvenu à rien, car ce ne sont pas des segments qu'on récupère mais des droites.

J'espère avoir été assez clair :/

Merci beaucoup

[kolodz]

Fonction principale :
Tu devrais te basé sur une régression linéaire à partir de 2 points.

Y=A*X+B

Une fois l’équation de la droite pour ces deux points trouvés, il t'est possible d'identifier les points qui font ou qui ne font pas partie de cette droite (avec un certain delta).
Avec l'ensemble des points identifié comme appartenant à cette droite. Tu réitère le processus régression linéaire/ajout de points, jusqu'au moment ou tu n'ajoute pas de point à le seconde étape.

Fonction de gestion : Sélection des deux points et exclusion des droits incohérentes.
La fonction principale prend en entré deux points initiaux et une liste de point potentiel. Cependant, il est possible que le résultat de la fonction ne soit pas acceptable. (Une droite à 2/3 points par exemple). Il faut donc ajouter un filtre sur les droites à retenir après coup. (5/6 points minimum par exemple)
De même pour éviter d'avoir trop de points à tester sur chaque itération, il est préférable d'exclure les points qui sont déjà présent dans l'une des droites que tu as déjà retenu.

Logiquement les droites présente dans ta liste de points se succèdent. Il est très peu probable que tu détecte un point dans ta droite, si les 5 précédentes n'était pas dedans.

Dans un premier temps, tu peux utiliser une application tiers pour ce genre de chose. Regressi est très pratique dans ce genre de cas. Il est capable de te faire la régression linaire très rapidement et tu peux ajuster les bornes de celle-ci via le graphique. En plus, il te donne l’écart-type et l'intervalle de confiance. et les coefficients qui vont bien.

Exemple d'utilisation de Régressi :


Cordialement,
Patrick Kolodziejczyk.

Source :
Site de l'auteur de Regressi http://jean-michel.millet.pagesperso-orange.fr/
http://fr.wikipedia.org/wiki/R%C3%A9..._lin%C3%A9aire

[saraza]

J'ai essayé quelque chose d'à peu près similaire :
1. Relier tous les points ensemble
2. Calculer le nombre de points proches de ce segment, et s'il y en a suffisamment par rapport à la distance, alors je garde cette droite.
3. Je compare toutes les droites qu'il me reste, et si 2 droites ont la même équation, je supprime la plus courte. (En vérifiant les distances entre les droites pour vérifier qu'elles sont bien à côté).

J'ai obtenu ça :

Cependant le résultat n'est pas exceptionnel...
Car le but est de générer le plan d'une pièce, donc je souhaiterais mettre les distances en dessous des droites (segments...).


Concernant ta proposition, quels sont les 2 points que je dois prendre au départ, comment les choisir ?
Je ne risque pas de tomber sur le même problème que ce que j'ai déjà essayé (au dessus) ?

Merci

[kolodz]

Les deux points initiaux devraient être logiquement les premiers points de ta liste. Le premier et le second ou le troisième ou le quatrième en fonction de la proximité des points. Si tu ne trouve pas une droite avec assez de points du décale d'un cran dans ta liste (seconde et troisième ou second et quatrième).

Si tu peux nous donnée une liste de points exemple. On pourrai te donner plus d'aide.

Cordialement,
Patrick Kolodziejczyk.

[saraza]

Ok, j'essaie de faire quelque chose ne partant là dessus.

Entre temps, voilà une liste de points, ils sont en X,Y et correspondent à ceux de l'image.

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
P(243,-3)
P(243,1)
P(243,5)
P(243,10)
P(241,14)
P(241,18)
P(242,23)
P(240,27)
P(241,31)
P(240,36)
P(238,40)
P(239,44)
P(238,49)
P(238,53)
P(237,57)
P(236,62)
P(236,66)
P(238,71)
P(149,69)
P(139,68)
P(129,66)
P(127,68)
P(120,67)
P(115,67)
P(112,68)
P(108,68)
P(104,68)
P(99,68)
P(96,68)
P(92,68)
P(89,68)
P(85,68)
P(82,68)
P(79,68)
P(76,68)
P(74,68)
P(71,68)
P(68,68)
P(66,68)
P(63,68)
P(61,68)
P(59,68)
P(57,68)
P(54,68)
P(52,68)
P(50,67)
P(48,67)
P(47,67)
P(45,67)
P(43,67)
P(41,67)
P(40,67)
P(38,67)
P(36,67)
P(35,67)
P(33,67)
P(32,67)
P(30,67)
P(29,67)
P(27,67)
P(26,67)
P(25,67)
P(23,67)
P(22,67)
P(20,67)
P(19,67)
P(18,67)
P(17,67)
P(15,67)
P(14,67)
P(13,66)
P(12,67)
P(10,67)
P(9,67)
P(8,67)
P(7,67)
P(5,67)
P(4,67)
P(3,67)
P(2,67)
P(1,67)
P(-1,67)
P(-2,67)
P(-3,67)
P(-4,66)
P(-5,67)
P(-7,67)
P(-8,67)
P(-9,66)
P(-10,67)
P(-12,67)
P(-13,66)
P(-14,67)
P(-15,67)
P(-16,66)
P(-18,67)
P(-19,66)
P(-20,67)
P(-21,66)
P(-23,67)
P(-24,67)
P(-26,67)
P(-27,66)
P(-28,66)
P(-29,65)
P(-31,66)
P(-33,66)
P(-34,67)
P(-36,67)
P(-37,67)
P(-39,67)
P(-41,67)
P(-42,67)
P(-44,67)
P(-46,67)
P(-47,67)
P(-49,67)
P(-51,67)
P(-53,67)
P(-55,66)
P(-57,67)
P(-59,67)
P(-61,67)
P(-63,67)
P(-65,67)
P(-68,67)
P(-70,67)
P(-73,66)
P(-75,66)
P(-78,67)
P(-81,66)
P(-84,66)
P(-87,66)
P(-90,66)
P(-95,67)
P(-98,67)
P(-101,66)
P(-104,66)
P(-109,66)
P(-113,66)
P(-118,66)
P(-122,66)
P(-127,65)
P(-133,66)
P(-139,65)
P(-145,65)
P(-153,65)
P(-161,66)
P(-166,64)
P(-176,65)
P(-272,59)
P(-272,54)
P(-273,49)
P(-274,44)
P(-272,39)
P(-266,33)
P(-273,29)
P(-272,24)
P(-270,19)
P(-272,15)
P(-272,10)
P(-268,4)
P(-270,0)
P(-268,-5)
P(-273,-10)
P(-272,-15)
P(-270,-20)
P(-272,-25)
P(-271,-30)
P(-273,-35)
P(-277,-41)
P(-272,-45)
P(-275,-51)
P(-275,-56)
P(-274,-61)
P(-273,-66)
P(-271,-71)
P(-272,-76)
P(-221,-79)
P(-197,-79)
P(-187,-79)
P(-175,-78)
P(-169,-79)
P(-160,-79)
P(-152,-78)
P(-146,-78)
P(-139,-78)
P(-133,-78)
P(-128,-78)
P(-122,-78)
P(-117,-78)
P(-113,-78)
P(-108,-78)
P(-105,-78)
P(-100,-78)
P(-96,-78)
P(-92,-77)
P(-89,-78)
P(-86,-77)
P(-83,-78)
P(-80,-77)
P(-77,-77)
P(-74,-78)
P(-71,-77)
P(-68,-77)
P(-66,-77)
P(-64,-77)
P(-62,-77)
P(-59,-77)
P(-57,-77)
P(-55,-77)
P(-53,-77)
P(-51,-77)
P(-48,-77)
P(-47,-77)
P(-45,-77)
P(-43,-77)
P(-41,-77)
P(-39,-77)
P(-37,-76)
P(-36,-76)
P(-34,-76)
P(-32,-76)
P(-31,-77)
P(-29,-76)
P(-27,-76)
P(-26,-76)
P(-24,-76)
P(-23,-76)
P(-21,-76)
P(-20,-76)
P(-18,-76)
P(-17,-76)
P(-16,-76)
P(-14,-76)
P(-13,-76)
P(-11,-76)
P(-10,-76)
P(-8,-76)
P(-7,-76)
P(-6,-76)
P(-4,-76)
P(-3,-76)
P(-2,-76)
P(0,-76)
P(1,-76)
P(3,-76)
P(4,-76)
P(5,-76)
P(7,-76)
P(8,-76)
P(9,-76)
P(11,-76)
P(12,-76)
P(14,-76)
P(15,-76)
P(16,-76)
P(18,-76)
P(19,-76)
P(21,-76)
P(22,-76)
P(24,-76)
P(25,-76)
P(27,-76)
P(28,-76)
P(30,-76)
P(31,-76)
P(33,-76)
P(35,-76)
P(36,-76)
P(38,-76)
P(40,-76)
P(41,-76)
P(43,-76)
P(45,-76)
P(47,-76)
P(49,-76)
P(50,-76)
P(52,-76)
P(54,-76)
P(56,-76)
P(58,-76)
P(61,-76)
P(63,-76)
P(65,-76)
P(68,-77)
P(70,-76)
P(72,-76)
P(75,-76)
P(78,-76)
P(81,-76)
P(84,-76)
P(87,-76)
P(89,-76)
P(93,-76)
P(112,-83)
P(115,-82)
P(120,-83)
P(126,-84)
P(129,-82)
P(133,-81)
P(141,-83)
P(143,-81)
P(154,-83)
P(242,-71)
P(240,-66)
P(243,-62)
P(242,-57)
P(240,-52)
P(239,-47)
P(240,-43)
P(240,-38)
P(241,-34)
P(242,-29)
P(242,-25)
P(241,-20)
P(242,-16)
P(243,-11)
P(241,-7)

[Flodelarab]

Bonjour,

Est-il autorisé de pré-supposer qu'il y a 2 droites à-peu-près verticales et 2 droites à-peu-près horizontales ?

[saraza]

Malheureusement non

On pourrait avoir une pièce comme cella là par exemple

[Flodelarab]

Un point de coordonnées (x1;y1) appartient à une droite théorique d'équation ax+by+c=0 si ax1+by1 est constant et plutôt égal à -c.

L'algo (puisque c'est la question) consisterait à faire des groupes.
Chaque couple de points peut générer un groupe.
On prend donc les points un par un; s'il peut être intégré à 1 ou plusieurs groupes, on le range, sinon il génère un nouveau groupe avec les autres points générateurs.
Une fois les groupes constitués, il suffit de faire un ajustement affine pour interpoler ton nuage de points.

Dans le premier cas tu obtiendras 4 groupes.
Dans le second, tu auras des cas douteux de droites ayant 4 intersections avec ton périmètre, sans que cela soit un mur. Tu peux alors exclure tout groupe ayant moins de 10 points, par exemple.

[saraza]

J'ai essayé, le résultat n'est pas très probant, je dois sûrement faire une erreur quelque part...

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
public void generate()
        {
            bool end = false;//Fin de la boucle
            int k = 0;
            Point point1;
            Point point2;
            Droite droitetmp;
            double a, b;
            int xtmp, ytmp;
            Point remove = null; //Si un point doit être supprimé de tmpPoint
            while(end==false)
            {
                point1 = tmpPoint[k];//On récupère un premier point  et le point qui suit dans la liste
                point2 = tmpPoint[k+1];
                droitetmp = new Droite(point1.getX(), point1.getY(), point2.getX(), point2.getY());//On créé une nouvelle droite avec ces deux points
                //Les a et b de y = ax + b sont calculés automatiquement
 
                foreach(Point point in tmpPoint)//On parcourt tous les points
                {
                    if (point.isEqual(point1) || point.isEqual(point2)) break;//on quitte la boucle si ce sont les mêmes points
 
                    remove = null;
                    if (droitetmp.hasA0()) a = 0;
                    else a = droitetmp.getA();//On récupère le a de la droite
                    b = droitetmp.getB(); //On récupère le b de la droite
 
                    xtmp = point.getX();//on récupère le x et y du point
                    ytmp = point.getY();
 
                    if(Math.Abs(a * xtmp + b - ytmp) < 5) //Est ce que ce point convient à peu près à l'équation de la droite en cours ?
                    {
                        //Oui il convient
                        remove = point;//On va le supprimer après de tmpPoint
                        droitetmp.groupe.Add(point);//On l'ajoute au groupe de la droite
                    }
                }
 
                if (remove != null) tmpPoint.Remove(remove);
                if(droitetmp.groupe.Count >3) droites.Add(droitetmp);//On ajoute la droite dans la liste des droites que si le groupe contient au moins 3 points
                k++;
                if (k >= (tmpPoint.Count-1)) end = true;
            }
 
        }

Edit : j'ai trouvé un des problèmes dans mon algo : je ne trace pas la droite entre les deux points les plus éloignés du groupe. Je corrige ça

[saraza]

J'obtiens des résultats mitigés, sans parvenir à les améliorer.
Voici l'algo que j'ai fais en suivant vos conseils, et en faisant les corrections par rapport à mon dernier post :

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
        public void generate()
        {
 
            bool end = false;
            int k = 0;
            Point point1;
            Point point2;
            Droite droitetmp;
            double a, b;
            int xtmp, ytmp;
            List<Point> remove = new List<Point>();
            while(end==false)//Boucle, tant que pas fini on parcourt droitetmp
            {
                point1 = tmpPoint[k];//On récupère un permier point et un deuxième
                point2 = tmpPoint[k+1];
                droitetmp = new Droite(point1.getX(), point1.getY(), point2.getX(), point2.getY());//On créé une droite avec ces 2 points
                remove.Clear();//On vide la lsite remove
                foreach(Point point in tmpPoint)//On parcourt tou sles points
                {
                    if (point.isEqual(point1) || point.isEqual(point2)) break;
 
                    a = droitetmp.getA();//On récupère le a et b de l'qéquation y=ax+b
                    b = droitetmp.getB();
 
                    xtmp = point.getX();//On récupère le x et y 
                    ytmp = point.getY();
 
                    //On vérifie si ce points vérifie l'quation de la droite en cours. Si oui on l'ajoute à la list remove pour qu'il soit supprimé de droitetmp. Et on l'ajoute au groupe de la droite
                    if((droitetmp.hasA0() && Math.Abs(xtmp - droitetmp.getX1()) < 100)
                        || (!droitetmp.hasA0() && Math.Abs(a * xtmp + b - ytmp) < 100))
                    {
                        //file.WriteLine("Yes");
                        remove.Add(point);
                        droitetmp.groupe.Add(point);
                    }
                }
 
                //On supprimer
                if (remove.Count != 0)
                {
                    foreach(Point point in remove)
                    {
                        tmpPoint.Remove(point);
                    }
                }
 
                //On ajoute la droite seulement si le groupe a plus de 3 pointss
                if(droitetmp.groupe.Count >3) droites.Add(droitetmp);
                k++;
                if (k >= (tmpPoint.Count-1)) end = true;
            }

Ce qui me donne :

Ensuite j'ai corrigé l'algo, car mon tracé de droite n'était pas bon. Je pend maintenant les 2 points les plus espacés d'un groupe pour former une droite :

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
            double disMax = 0;
            Point A, B;
            foreach(Droite droite in droites)
            {
                A = null;
                B = null;
                disMax = 0;
 
                foreach(Point point1 in droite.groupe)
                {
                    foreach (Point point2 in droite.groupe)
                    {
                        if(point1.distanceTo(point2) > disMax)
                        {
                            disMax = point1.distanceTo(point2);
                            A = point1;
                            B = point2;
                        }
                    }
                }
                droite.setX1(A.getX());
                droite.setY1(A.getY());
                droite.setX2(B.getX());
                droite.setY2(B.getY());
            }

Le résultat n'est pas beaucoup mieux :/

Je ne trouve pas l'erreur dans mon algo...

Merci

[Flodelarab]

Le résultat n'est pas mal du tout au contraire. J'augmenterais la tolérance et je supprimerais les droites qui ont moins de 10 points. La droite en travers est l'ennemi à abattre.

Comme dit plus haut, je ne déterminerais pas l'équation par seulement 2 points (Il suffit de prendre un point foireux pour que ton robot fonce dans le mur à pleine vitesse) mais par méthode des moindres carrés. Avec, en cerise sur le gâteau, un changement de repère si la droite est trop verticale dans le repère naturel.

[saraza]

Ok, j'ai compris le fonctionnement de la méthode des moindres carrés, cependant je ne vois pas quand l'appliquer.
Dois-je l'appliquer une fois que j'ai trouvé les groupes ?

[Flodelarab]

Oui. Chaque groupe a une équation.

[saraza]

C'est ce qui me semblait le plus logique.

Mais pour choisir les groupes, à l'heure actuelle je fais comme ça :
- Je prends les 2 premiers points
- Je récupère l'équation de la droite pour ces deux points
- Je vérifie si tous les autres points font partie du même groupe. Si oui je les ajoute.

Donc pour l'isolation des groupes, j'établis l'équation avec 2 points ?

Le résultat à l'heure actuelle d'isolation des groupes est :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
A(7,67) B(5,67) a = 0, b = 67
A(-9,66) B(-10,67) a = -1, b = 57
A(-27,66) B(-28,66) a = 0, b = 66
A(-51,67) B(-53,67) a = 0, b = 67
A(-90,66) B(-95,67) a = -0,2, b = 48
A(-27,-76) B(-26,-76) a = 0, b = -76
A(-8,-76) B(-7,-76) a = 0, b = -76
A(11,-76) B(12,-76) a = 0, b = -76
A(33,-76) B(35,-76) a = 0, b = -76
A(63,-76) B(65,-76) a = 0, b = -76
A(133,-81) B(141,-83) a = -0,25, b = -47,75

[Flodelarab]

Je ne comprends pas le résultat que tu affiches. En admettant que ton A et ton B soient des points différents pour lesquels tu recycles le nom, que sont a et b ? les coefficients de ax+by+c=0 ? Si oui, pourquoi 7 8 9 et 10 ont la même équation mais ne sont pas identifiés comme étant du même groupe ?

[saraza]

Oui, a et b sont les a,b de y = ax +b.

Oui il devrait être dans le même groupe, mon algo pour trouver les groupes a un problème au vu des résultats...

[anapurna]

salut

ce ne peut être que des droite que tu mesure ou peut il y avoir des courbe
si ce n'est que des droite

ne serait il pas plus simple de diviser ton image en ligne et en colonne

toute les cellules contenant au moins trois point sont discriminant les autre tu les supprime
tu subdivise tes ligne et tes colonne afin d'englober les points
une fois les colonne et les lignes définient un simple calcul de régression linéaire devrai suffire

[anapurna]

salut

bon pour aller plus loin je pense que tu n'as pas pris le problème du bon coté
il existe des algorithme qui te permette de retrouver une enveloppe a partir de nuage de point
tel que l'algorithme de Graham
une fois le contour défini je pense qu'il seras facile d'identifier tes droites

[ToTo13]

Les pièces ne sont pas forcément rectangulaire, il peut y avoir des recoins.

[anapurna]

salut

dans ce cas ma première solution de créer une grille sur le dessin afin de repérer les points remarquables semble être une solution viable
connaissant tes coordonnée mini et maxi en x et en y tu divise la longueur et la largeur en 3,6 ou 9 tu repère les cases où les points se trouvent
une fois les lignes et les colonnes constituées tu peut affiner ... un peut a l'instar des archéologue qui définissent des zone et ensuite progresse doucement pour découvrir les secret enfui dans certain coin