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)