Discussion :

[serveurperso]

Bonjour les développeurs !

Je crois que c'est mon premier post sur le forum. Donc une mini présentation s'impose, je développe (sans aucun but lucratif pour l'instant, c'est juste par passion) sur diverses technos web et microcontrôleurs comprenant du C / C++ / NodeJS / JavaScript / PHP / CSS / (x)HTML5 et éventuellement d'autres.

Afin de perfectionner un algo de SLAM = localisation et cartographie simultanée (ultra léger par rapport à tout ce qui existe sur le sujet, nuage de points en 2D de faible résolution sur microcontrôleur) j'ai besoin de la brique élémentaire algorithmique suivante :

Extraire les moyennes des N plus grands blocs de nombres proches (à N près) dans un tableau.
(En C à destination d'un microcontrôleur 32 bits 80MHz, le type des valeurs du tableau est int16_t et son index rentre dans de l'uint8_t mais cela n'a pas d'importance).

Ce que j'ai déjà c'est une fonction de quickSort qui me permet de grouper les valeurs similaires.
"Si je trace la courbe de ce tableau trié, j'ai une sorte d'escalier avec des marches plus ou moins grandes, des plateaux. Il me faut extraire la hauteur moyenne des N plus grandes marches."

Peut être qu'il faut que je passe dans le domaine fréquentiel à l'aide de transformations de Fourier, j'ai déjà un algo qui fait du fourier en arithmétique entière... mais j’aimerais bien trouver un algo plus léger...
peut être que quelqu'un à une idée d'un algo déjà existant à utiliser en une ou plusieurs passes... Toute idées mathématiques peuvent m'aider à implémenter l'algo recherché.


Pour qui cela intéresse de voir ma création loisir du moment, voici la page web de loisir (zéro publicité) concernant le sujet de mon post ici : https://www.serveurperso.com/?page=robot (n'importe quel visiteur peux jouer avec le robot de façon limitée sauf si demande sur un chat et j'accorde les droits de le piloter complètement)

Il s'agit d'un robot avec des capacités autonomes et de pilotage en temps réel depuis le net n'exploitant qu'une seule puce 32 bits 80MHz et un scanner à balayage laser "RPLIDAR A2".
Il est géolocalisé à l'aide "d'Amers" (balises) fixes, un algo qui ressemble à du SLAM mais incapable de fonctionner sans configuration très simple, mais manuelle de repères caractéristique.
Algo que je souhaite encore améliorer pour qu'il s'adapte automatiquement à l'environnement et deviennent du vrais SLAM.


Merci

Pascal

EDIT : reformulations...

[tbc92]

Je résume :
L'objectif est de : Extraire les moyennes des N plus grands blocs de nombres proches (à N près) dans un tableau.

J'essaie de reformuler, parce que je ne comprend pas :
N = 10
J'ai un tableau de P nombres ( par exemple P = 50), voici ces 50 nombres :
5 6 8 13 15 17 25 26 27 27 28 28 28 29 38 39 41 68 69 69 70 76 etc etc

Je peux avoir des doublons ( 28 est répété 3 fois ici ...)
Je construis les blocs de nombres proches à N Près. Comme N=10, j'ai un premier bloc des nombres entre 5 et 15. Puis un 2ème bloc de 6 à 15, un 3ème bloc de 8 à 17, etc etc
Pour chaque bloc, je peux claculer son effectif
Bloc 5..15 effectif = 5
Bloc 6..15 effectif = 4
Bloc 8..17 effectif = 5
...
Bloc 25..29 effectif = 8
Je retiens les 10 blocs qui ont le plus grand effectif. Ici, je retiens le bloc 25..29 par exemple. Et pour ce bloc, je calcule la moyenne des 8 nombres 25 26 27 27 28 28 28 et 29.

C'est ça ?

[serveurperso]

C'est exactement ça. Le but c'est de reussir à localiser dans le tableau les blocs de nombre quasi identique, la moyenne peux être faite séparément...

Pour tout expliquer c'est que je cherche une méthode plus rapide qu'un RDP (ramer douglas peucker - https://fr.wikipedia.org/wiki/Algori...ouglas-Peucker) pour récupérer les lignes dans le nuage de points de mon lidar. et surtout uniquement les perpendiculaires, alignées dans le plan cartésien. (d'ou les valeurs similaires en X et en Y séparément)

En gros j'ai bien besoin de localiser les valeurs presque identiques dans un tableau, trié ou pas trié (selon l'optimisation de l'ensemble final) afin d'extraire les N plus grandes lignes en X, idem pour Y

Compter l'effectif à N (tolérance) près. exemple une ligne quasi perpendiculaire, dont l'erreur (bruit + erreur d'angle) ne dépasse pas 100mm
Et récupérer la valeur moyenne de tout ses points : pour augmenter la précision de cet "Amer" utilisé pour géolocaliser le robot.

Actuellement j'exploite des amers perpendiculaires les uns des autres, connus, pré configurés dans le robot. et ça fonctionne du tonnerre, il roule à toute vitesse avec la fiabilité d'un automate industriel - comparé à du SLAM avancé avec EKF / corrélation de frame par plus proches voisins (ICP) et compagnie ou, on vois souvent le robot avancer tout doucement et avec parfois des bug de localisation. Or que le robot avec mon algo simple peux faire un déplacement répété 24/7 sans jamais foirer.
Il est géolocalisé en absolu dans tout mon appart (avec seulement 6 ou 7 amers). mon but est de générer/supprimer les amers de façon dynamique.

[serveurperso]

La méthode de recherche bourrin par blocs semble super consommatrice surtout que j'ai besoin de scanner un espace de 16 bits...

Une autre méthode de réduire la résolution de recherche pose des problèmes de pertes de points si la ligne tombe entre 2 gros "pixel"

Une autre méthode qui exploite la dérivée (courante - ancienne) ne fonctionne pas car elle laisse passer des aberrations de folie, la tolérance doit être effective sur chacun des bloc entiers et non entre les valeurs.
La tolérance est la pour limiter l’excursion maximum au sein d'un bloc.

j'aimerais bien trouver une façon de faire plus performante sinon je vais devoir faire avec RDP (ou il reste 1 dernier bug pour joindre le premier et le dernier élément:s)

[pseudocode]

C'est exactement ça. Le but c'est de reussir à localiser dans le tableau les blocs de nombre quasi identique, la moyenne peux être faite séparément...

Donc c'est plutôt de la clusterisation, genre méthode de Ward ou Otsu... bref minimiser la variance intraclasse (= minimiser les écarts à l'intérieur du bloc).

Du coup je ne comprend pas pourquoi exploiter la dérivée pose problème: ca permet assez rapidement de trouver une séparation entre les blocs.
Si |x[i+1]-x[i]| > N, alors forcément x[i+1] et x[i] ne sont pas dans le même bloc... et donc on peut séparer le problème en deux.

[serveurperso]

C'est exactement de ce genre d'idée que j'ai besoin. Une question bien formulée est à moitié répondue, faut il encore être capable de bien la formuler je suis encore en mode intuition... une intuition qui me dit qu'il faut explorer quelque chose de plus précis et peut être plus rapide de RDP qui génère des lignes approximatives qui "tremblent" d'une trame sur l'autre. Or que si je clusterise et fait la moyenne des mesure je vais avoir une ligne précise de ouf par rapport à RDP qui se base bêtement sur le premier et dernier point !!!

Déjà je peux faire mes tableaux utilitaires (X-Y) de dérivées à partir de mes tableaux trié.

Puis faire une seconde et d'autres passes afin de vérifier que mes blocs ne dérivent pas de trop justement, car un cercle de grand rayon va générer des dérivées faiblardes dont la somme dépasse toute tolérance...
Je vais regarder comment fonctionnent les méthodes de Ward et Otsu si ça m'inspire...

le robot :

sauf que maintenant il est OK Google (webservice pour lui demander depuis l'assistant & IFTTT sur smartphone d'aller me récupérer une boisson dans un mini frigo, reste à lui apprendre a nettoyer la cuisine lol)

[serveurperso]

Bon le Otsu ça m'aide pas car il fait lui même son thresholding
Et Ward https://onlinecourses.science.psu.edu/stat857/node/108 c'est du regroupement hiérarchique ? ça fait bien plus que ce que j'ai besoin ! (pas besoin de comparer la dissimilarité entre mes "blocs")

Je crois qu'il faut clusteriser moi même à l'aide de dérivées, car dans le cas nominal ça va fonctionner du premier coup (pas de courbes pièges dans l'appart), et en suite faire une passe d'élimination des blocs anomalies !
en suite vu qu'il me reste que des clusters répondants au exigences je calcul mes moyennes et génère mon segment de droite dessus et adieu le tremblements typiques de l'algo RDP

[pseudocode]

Je crois qu'il faut clusteriser moi même à l'aide de dérivées, car dans le cas nominal ça va fonctionner du premier coup (pas de courbes pièges dans l'appart), et en suite faire une passe d'élimination des blocs anomalies !

Tout a fait. J'ai cité Ward/Otsu pour illustrer ce dont je parlais, mais ces méthodes ne sont pas adaptées ici.

Le découpage suivant les max locaux de la dérivée fonctionne bien pour les valeurs d'exemple de tbc92
Exemple, pour un max local de 5, on obtient 6 groupes:

valeurs: 5 6 8 13 15 17 25 26 27 27 28 28 28 29 38 39 41 68 69 69 70 76
              |        |                       |        |           |
derivés:  1 2 5  2  2  8  1  1  0  1  0  0  1  9  1  2  27 1  0  1  6
              |        |                       |        |           |

Group A: pop=3, valeur= 6.3 ± 1.5 
Group B: pop=3, valeur=15.0 ± 2
Group C: pop=8, valeur=27.2 ± 2
Group D: pop=3, valeur=39.3 ± 1.5
Group E: pop=4, valeur=69.0 ± 1
Group F: pop=1, valeur=76.0 ± 0 

Ca ne fonctionne évidement pas aussi bien pour les cas où la dérivée n'a pas de grand max local (valeurs en pente douce) ou pour les cas où il y a beaucoup de max locaux.
Mais ces cas doivent être traités différemment car ils reflètent surement une situation particulière de ton robot.

[serveurperso]

Ca ne fonctionne évidement pas aussi bien pour les cas où la dérivée n'a pas de grand max local (valeurs en pente douce) ou pour les cas où il y a beaucoup de max locaux.
Mais ces cas doivent être traités différemment car ils reflètent surement une situation particulière de ton robot.

Exact et c'est ce qui m'a fait éliminer l'utilisation de la dérivée dans ma première réflexion rapide or :

Une série de grandes dérivées signifie qu'il ne s'agit ni d'une cloison perpendiculaires (ce qui est recherché) ni d'une cloison piège (cas de cloison inclinée ou arrondie à filter en seconde passe) mais de petits obstacles en tout genre dont la taille ou l'aspérité rend la zone non exploitable en référence de localisation. -> zone a ignorer -> Ce que fait très bien cette première passe.

Il ne reste donc que des objets avec des suites de faibles dérivées ou il faut éliminer les cloisons pièges arrondies ou non perpendiculaires.

Et pour ça il suffit de chercher le min et le max du bloc lui même (pas de la dérivée lol) et de vérifier si il rentre dans la tolérance ! si oui on le garde et on calcul la distance moyenne sinon discard

Plus qu'à coder et tester