Bonjour,
 
Je sollicite votre aide sur un problème mathématique (et un peu physique aussi) auquel j'ai trouvé quelques solutions mais pas forcément satisfaisantes. Voilà, je cherche un algo permettant de localiser la source d'émission d'une fréquence (en général qui provoque un brouillage). Pour ça, un véhicule se balade et fait des tirs gonio, chaque tir se caractérisant par un timestamp, les coordonnées GPS du véhicule au moment du tir, l'angle du tir (azimut, de 0 à 360°), le niveau du signal reçu (de 0 à 100) et la qualité du signal reçu (de 0 à 10).
 
J'ai fait 2 algos.  
 
ALGO n°1 :
Il conserve les tirs ayant une qualité de tir >= Q1 et un niveau >= N1 puis il calcule les intersections des tirs (2 à 2). Pour chaque intersection, on vérifie qu'elle est située à une distance acceptable des 2 tirs concernés. Si elle est située trop loin, on ne la conserve pas.
Au final, on fait la moyenne des intersections. Cette moyenne est censée être la source de l'émission.
 
ALGO n°2 :
Il conserve les tirs ayant un niveau >= N2 (avec N2 < N1) et établie une grille de cellules de quelques dizaines de mètres de côté. Il va calculer les intersections des tirs (2 à 2) puis va comptabiliser le nb d'intersections dans chaque cellule de la grille.
Au final, il calcule la moyenne des coordonnées des centres des cellules pondérées par le nb d'intersections par cellule. Cette moyenne est censée être la source de l'émission.
 
Le problème, c'est que la qualité des tirs est très disparate (plus le pb des multi-trajets). Quand on est loin de l'objectif, toutes les mesures ont un niveau faible et souvent une faible qualité. Dans ce cas, il faut que l'algo ne fasse pas trop la fine bouche. Par contre, quand on est près de l'objectif, il faut au contraire que l'algo arrive à éliminer les tirs "aberrants". Le problème, c'est qu'on ignore justement si on est proche ou pas de l'objectif...
 
Vous auriez une idée, svp ? Merci par avance

Je ne suis pas vraiment spécialiste de la chose mais plutôt que te baser sur une valeur de référence en ce qui concerne le niveau et la qualité, tu pourrais utiliser des variables pondérées basées sur les tirs précédents avec des paliers de références.
 
Comme ça au fur et à mesure de l'avancée des tirs, la base de référence évoluera en même temps que l'opérateur se rapproche de la cible.

Le palier de base est calculé en fonction du min/max des niveaux relevés.
 
Après, le parcours du véhicule pour effectuer les relevés étant un peu au pif en phase de première recherche, on n'obtient pas forcément des meilleurs niveaux en avançant car on ne se rapproche pas forcément de l'objectif. Par ailleurs, il arrive aussi qu'on se rapproche mais qu'on ait de moins bons niveaux à cause d'obstacles ou de multi-trajets.
 
Je me demandais donc si, dans le domaine du traitement du signal, il n'y aurait pas des algos permettant de faire intelligemment le tri entre les bonnes et mauvaises valeurs (ie, obstacles, multi-trajets). A moins qu'il existe des algos plus spécifiques, dédiés justement à ce genre de recherche. J'ai cherché dans Google, mais j'ai pas trouvé grand chose adapté à mon cas. Concernant le traitement de nuages de points, je tombe beaucoup sur des algos d'analyse de la variance.
 
Je me demandais si une ACP, ça le ferait. Après, faut que j'aie le niveau de compétence pour implémenter ce genre d'algo, pas forcément évident

C'est un problème de recherche d'outliers, cherche Ransac sur google.

Effectivement, ça a l'air pas mal. Par contre, pour le "modèle", je suis pas sûr de trouver l'équation qui correspond à mon cas de figure.

T'as pensé à la transformée de Hough ?

Tu transformes ton nuage de droites en un nuage de points (la transformée de Hough transforme une droite en un point, et inversement).
 
Tu vas certainement obtenir des points aglutinés le long d'une droite (qui représente la source d'émission que tu cherches), tous les autres points étant des outliers.
 
L'idée  c'est de mettre en évidence cette droite avec un Ransac.
 

Non, je n'y avais pas pensé. J'ai regardé l'article mais je ne suis pas sûr d'avoir tout bien compris : https://fr.wikipedia.org/wiki/Trans [...] 9sentation
 
Si on se réfère au schéma présenté dans l'article, les points A et C sont les extrémités d'un tir gonio et B est ma source d'émission (à trouver).  
 
1) Il va alors falloir pour le point A, calculer pour chaque angle variant de 0 à 360° la transformée de Hough, ce qui va me donner une sinusoïde. Je vais devoir faire la même chose pour C puis calculer l'intersection des 2 sinusoïdes, ce qui me donnera un angle et une distance.
 
2) faire l'étape 1 pour tous les tirs gonio.
 
3) et après, je fais quoi de tout ça
 
Edit : pour 3), je crois comprendre qu'il faut que je trouve un point B qui, par sa transformée de hough, tombe sur un maximum d'intersections de sinusoïdes, c'est ça ? Dis autrement, il va falloir trouver Xs et Ys tels que pour une majorité d'angles A (A étant l'un des angles correspondant à une intersection de 2 sinusoïdes), je retombe sur la distance D (D correspondant à la distance associée à l'angle A d'intersection). Si c'est bien ça, ça me parait assez chaud

C'est pas ca, relis bien mon poste precedent, il est tres synthetique mais donne tous les details de l'algo, chaque mot a son importance.
 
J'ai parlé d'une transformée qui transforme un point en une droite, pas en sinusoide (il y a plusieurs variantes de Hough), cherche sur le net l'explication de la bonne variante (celle qui transforme une droite en un point).
 
Pour ton problème chaque tir gonio est une droite qu'on transforme en point.
 
Si tu as bien compris le principe de Hough et Ransac (je reconnais c'est pas du tout évident au premier abord), tu devrais t'en sortir.

Le point dont tu parles, n'est-ce pas tout simplement l'intersection des sinusoïdes des points appartenant à une droite ?
 
Dans ton premier poste, tu dis "Tu transformes ton nuage de droites en un nuage de points". Et maintenant, tu me parles "d'une transformée qui transforme un point en une droite".
 
Moi, ce que j'ai compris de la transformée de Hough, c'est que si on trouve un angle t pour lequel :
x1*cos(t) + y1*sin(t) = x2*cos(t) + y2*sin(t) = x3*cos(t) + y3*sin(t)
alors :
(x1,y1), (x2,y2) et (x3,y3) appartiennent à la même droite.
 
Du coup, pour chaque point (x,y), il faut calculer x*cos(t) + y*sin(t) pour les 360 valeurs de t. Le résultat te donne une sinusoïde.
 
Edit : j'ai trouvé cet algo : http://www.developpez.net/forums/d [...] gne-hough/

 
Oui parce parce que c'est le cas !
 
C'est expliqué dans ces 2 pdf (schéma p. 2)
 
http://www.cs.indiana.edu/pub/techreports/TR663.pdf
 
http://elynxsdk.free.fr/ext-docs/D [...] -espic.pdf

Ok, c'est bon, j'ai capté. En fait, moi, j'avais compris la page n°3 du premier PDF.
 
Le 2ème PDF, j'étais tombé dessus et m'étais attardé sur les pages 4 et 5.
 
Du coup, je comprends que je dois transformer mes tirs gonio qui sont exprimés sous la forme d'équations de droites Yi = ai*Xi + bi et je vais obtenir un nuage de points ai,bi. Ces points devraient être globalement alignés sur une droite dont j'obtiendrai l'équation via une régression linéaire, c'est bien ça ?
 
Ensuite, cette droite me servira de modèle pour Ransac et devrait me permettre de séparer les "bons points" (ie les bons tirs gonio) des "mauvais" (tirs aberrants). J'ai bon ?

C'est à peu près ça, juste que t'as pas besoin de faire de régression linéaire, tu dis juste à Ransac, j'ai des points alignés dans mon nuage de points, trouve moi l'équation de la droite.

Salut Rufo
 
Tu conserves les tirs les mieux notés (en qualité), et ce par secteurs géographiques, car:
-Un tir ayant un faible niveau doit être conservé, si sa note est acceptable.
-Un tir lointain doit être conservé, il pourra former une perpendiculaire qui augmentera la précision de la localisation.
 
Donc:
Tu enregistres tous tes tirs, avec éventuellement un seuil de qualité et tu fais un nettoyage régulier par secteurs géographiques afin de ne garder que les mieux notés, et aussi toujours conserver les plus lointains également bien notés.
Tu crée un nuage de points issu de chaque intersection de tirs.
Tu fais un médiane quartile en latitude et longitude de ton nuage de points et tu obtiens ta localisation.
 
C'est une solution simplifiée qui est fonctionnelle.
 
 

Ce que tu décris ressemble beaucoup à mon algo N°1 (cf mon premier post) à la différence que tu proposes de calculer une médiane quartile sur le nuage de points obtenu (par intersections des tirs) alors que je fais une moyenne pondérée (pondération des coordonnées par le produit Q1*N1).
 
Tu penses que ça apporte quoi la médiane quartile ?