Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Calculer le point d’intersection de deux segments dans un espace 3D


Sujet :

Algorithmes et structures de données

  1. #1
    Membre habitué
    Calculer le point d’intersection de deux segments dans un espace 3D
    Bonjour tout le monde,

    Mon projet et de trouver la distance d'un objet en comparent 2 photos.
    Un réseau de neurones s'occupe dans un premier temps, d'identifier l'objet et me renvoie deux points (haut/gauche et bas/droite) pour situer cette objet sur cette photo.
    D'un autre côté, je créé une position à mon téléphone grâce au gyroscope et à l’accéléromètre.
    Ensuite, je créé un horizon arbitraire sur lequel je met ma photo et je me retrouve, lorsque j'ai deux photo, avec deux yeux et deux objets, donc, deux segments qui sont:
    - œil_1 à objet_1
    - œil_2 à objet_2

    Dans un monde idéal je retrouverai l'emplacement de mon objet en calculant le point d'intersection des deux segments.
    Mais il peut y avoir des imprécisions sur la localisation du smartphone et des points renvoyer par le réseau de neurones.

    Dans cette situation, les segments ne se croisent pas et je ne peux pas retrouver la position de mon objet.
    Comment puis-je m'y prendre pour obliger un résultat, quitte à en baisser la précision?

    Merci de votre aide.
    Des jours c'est facile, des jours c'est pas facile, mais c'est jamais le même jour.

  2. #2
    Expert confirmé
    salut

    déplacer les origines pour quel soit confondu ?

    je m'explique
    tu as 2 points par objet

    X1Y1 -----|
    -----------|
    -----?-----|
    -----------|
    -----------|X2Y2

    tu cherche le barycentre (ou si tu préfère le point de mire centrale de ton objet)

    X3 = X1-X2 et Y3= Y1-Y2

    tu fait la même chose avec l'autre photo

    de l'a il te suffit juste de déterminer les translations à effectuer pour réduire le décalage
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  3. #3
    Membre habitué
    Bonjour anapurna,

    Je pense que c'est mieux de partir du principe que l'objet n'a qu'une seul adresse parce que ça induis en erreur.
    Du coup ça ne règle pas mon problème parce que ce barycentre peut être faussé d'une photo à l'autre.

    Je vais essayer d'être plus clair.
    J'ai 2 photos:

    Depuis la photo 1 j'ai accès à la localisation de l'objectif (œil_1) et le barycentre de l'objet (objet_1);
    Depuis la photo 2 j'ai accès à la localisation de l'objectif (œil_2) et le barycentre de l'objet (objet_2);

    Le problème est que la position de objet_1 et objet_2 sont approximatifs et ça peut être le cas aussi pour œil_1 et œil_2.
    Si j'avais des données exacts, je suis sur que les segments se croiserai mais là c'est pas le cas.
    Des jours c'est facile, des jours c'est pas facile, mais c'est jamais le même jour.

  4. #4
    Nouveau membre du Club
    Si j'ai bien compris, tu te retrouves donc avec deux segments, qui ne se croisent pas forcément exactement, et on cherche l'endroit où ils sont au plus près de se croiser. Il y a peut-être des astuces possibles, mais je partirait sur un calcul direct :

    On a un segment D1, et un segment D2.
    On va commencer par mettre ces segments sous forme d'équation de droite (on va résoudre le problème pour deux droites, et se ramener au cas des segments par la suite si nécessaire).
    D1 a pour coordonnées a1*x + b1*y + c1*z + d1 = 0
    D2 a pour équation a2*x + b2*y + c2*z + d2 = 0

    Bonus, pour se simplifier la vie, on va normaliser ces équations pour assurer que a1² + b1² + c1² = 1

    On cherche le point de coordonnées (x, y, z), telle que la distance entre ce point et D1 soit la plus faible possible, ainsi que la distance de ce point à D2.

    Il nous faut une métrique unique de la qualité du point. Je propose la somme des carrés des distances : E = d(x, y, z, D1)² + d(x, y, z, D2)²
    La distance du point à la droite est donnée par la formule :

    d(x, y, z, D1)² = (a1*x + b1*y + c1*z + d1)²/(a1² + b1² + c1²)
    Comme on a normalisé nos expressions, ça nous donne :
    d(x, y, z, D1)² = a1 * x + b1 * y + c1 * z + d1

    Regroupons tout ça, on cherche x, y, z, de façon à minimiser E = (a1*x + b1 *y + c1*z + d1)² + (a2*x + b2*y + c2*z + d2)²

    Et ça, c'est la recherche du sommet d'une parabole (en 3D, mais tout de même). Au point x, y, z que l'on cherche, la dérivé de E doit être nulle en tout point.
    On peut donc développer E, le dériver suivant x, suivant y, et suivant z. Et on se retrouve avec 3 équations pour 3 inconnues. C'est fastidieux, mais ça marche.

    Côté programmation, il vaut sans doute mieux utiliser un solveur existant pour résoudre ce système d'équation. Ca sera beaucoup plus simple que de le faire à la main.

    Dernier détail, on a trouvé ici l'intersection approchée de deux droites, et non de deux segments. Si c'est un vrai problème pour l'application, on peut projeter se ramener au cas des segments.
    Disons que l'on a trouvé le point H. Appelons H1 le point de D1 le plus proche de H. Ca sera soit le projeté de H sur la droite, soit une extrémité du segment. On fait pareil pour trouver H2, le point de D2 le plus proche de H. On peut alors prendre le milieu de [H1 H2], c'est notre point "au plus prêt".


    Méthode 2 :

    Si on n'a pas besoin d'un résultat si précis, on pourra aussi chercher le point de D1 qui soit le plus proche possible de D2. Dans le cas ou les deux segments se croisent "presque", cela devrait être presque pareil, et plus simple à calculer.
    Si on choisit cette approche, on cherche x, y, z, sachant que le point est sur D1, on a a1*x+b1*y+c3*z+d = 0
    Et on chercher à minimiser la distance à d2 : (a2*x + b2*y + c2*z + d2)²/(a1² + b1² + c1²)
    Le dénominateur est sans importance, il est positif, et on cherche à minimiser. Il s'agit donc de minimiser E = (a1x + b2*y+ c2*z + d2)²
    Et la même chose qu'avant, en plus simple. On cherche le sommet de la parabole. Donc on dérive E suivant x, y, et z, et on cherche les valeurs qui mette ces trois dérivées à 0. On a 3, là encore, 3 équations et 3 inconnues.


    Méthode 3 : combo

    On peut enfin utiliser la méthode 2 pour trouver H1, le point de D1 le plus proche de D2. On ré-utilise ensuite la même méthode pour trouver H2, le point de D2 le plus proche de D1. Puis, le point que le cherche est simplement le milieur de H1 et H2

  5. #5
    Membre habitué
    Merci Andéol,
    J'ai tout lu, j'ai rien compris.
    Je n'ai visiblement pas les compétences mathématiques requises.
    Ce que je ne comprend pas c'est la formulation de la définition de droite: a1*x + b1*y + c1*z + d1 = 0
    Pourquoi "=0", pourquoi a1, b1 et c1 ne sont pas la même variable , c'est quoi d1, comment je fait pour transformer ça en un ensemble de 2 points?
    Des jours c'est facile, des jours c'est pas facile, mais c'est jamais le même jour.

  6. #6
    Expert éminent sénior
    Bonjour

    Ce que je comprends du problème : on a deux droites de l'espace à 3 dimensions et on cherche la distance minimum entre ces droites. Si les droites se coupent, évidemment, la distance est nulle.
    Voici un lien qui donne la solution (clic). Regarde le paragraphe "Distance de deux droites (D1) et (D2) non parallèles - méthode 2" et la suite. Je propose de prendre comme point qui minimise l'erreur, le barycentre entre A et B (A sur D1 et B sur D2).

    Bonne chance
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  7. #7
    Membre chevronné
    Calculer le point d’intersection de deux segments dans un espace 3D
    Bonjour,

    Je me demande si le problème n'a pas été mal formulé dès le départ, faute d'une représentation géométrique.

    Citation Envoyé par Pecose Voir le message
    ... Mon projet et de trouver la distance d'un objet en comparent 2 photos.
    Un réseau de neurones s'occupe dans un premier temps, d'identifier l'objet et me renvoie deux points (haut/gauche et bas/droite) pour situer cette objet sur cette photo.
    D'un autre côté, je créé une position à mon téléphone grâce au gyroscope et à l’accéléromètre.
    Ensuite, je créé un horizon arbitraire sur lequel je met ma photo et je me retrouve, lorsque j'ai deux photo, avec deux yeux et deux objets, donc, deux segments qui sont:
    - œil_1 à objet_1
    - œil_2 à objet_2 ...
    Il s'agit initialement (si j'ai bien compris) de la restitution spatiale d'un objet réduit à deux points, à partir de deux photographies prises selon des directions différentes. Or un glissement de sens intervient dès la fin de l'énoncé, qui gauchit la discussion vers la recherche de la distance entre deux objets.

    Supposons l'axe optique (Δ1 ou Δ2) de l'objectif maintenu horizontal, et son centre optique à distance fixe (D = OC1 = OC2) d'un point (O) proche de l'objet (AB) - on pourra par la suite y revenir.
    Les images (A1, A2) du point objet (A) résultent de la projection centrale de ce point sur deux plans normaux à l'axe optique correspondant, et placés à une distance d = C1O1 = C2O2 du centre optique de l'objectif, distance très proche de la distance focale.

    Voici ce que donne la projection orthogonale de l'ensemble sur un plan horizontal - cette transformation ne modifiant pas les relations données par la suite:


    Il y a bien deux paires de triangles de même forme, dont la similitude s'exprime par les relations:
    (H1A)/(O1A1) = (C1H1)/(C1O1) ;
    (H2A)/(O2A2) = (C2H2)/(C2O2) ,
    et (en convenant de poser L = OA) complétées par:
    (C1H1) = (C1O) + (OH1) = -D + L.Cos(α1) ;
    (C2H2) = (C2O) + (OH2) = -D + L.Cos(α2) ;
    (O1A1) = x1 ; (O2A2) = x2
    (H1A) = -L.Sin(α1) ; (H2A) = -L.Sin(α2) ;
    α2 = α1 + φ
    (il intervient des valeurs algébriques, de divers signes).
    Il vient par conséquent:
    L.Sin(α1) = (D - L.Cos(α1)(x1/d) ;
    L.Sin(α2) = (D - L.Cos(α2)(x2/d) .

    La détermination d'une dimension de l'objet (L) et de son orientation (α1 ou α2) exige de connaître deux distances longitudinales (d, D) en plus des abscisses (x1, x2) des points images.
    Le fait de supposer l'objet relativement éloigné (L << D) simplifie les relations par approximation
    L.Sin(&#945;1) ~ D(x1/d) ,
    L.Sin(&#945;2) ~ D(x2/d) ,
    mais ne supprime pas la difficulté précédente.

    Rien n'empêche de faire coïncider le point (O) avec le point objet (B), ce qui revient à centrer les images sur (B1) et (B2); le problème demeure cependant, car il faut toujours résoudre le système d'équations à quatre inconnues (D, L, &#945;1 , &#945;2):
    L.Sin(&#945;1) = (D - L.Cos(&#945;1)(x1/d) ;
    L.Sin(&#945;2) = (D - L.Cos(&#945;2)(x2/d) ;
    &#945;2 = &#945;1 + &#966; .
    .


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  8. #8
    Membre chevronné
    Calculer le point d’intersection de deux segments dans un espace 3D
    Citation Envoyé par Pecose Voir le message
    ... J'ai 2 photos:

    Depuis la photo 1 j'ai accès à la localisation de l'objectif (œil_1) et le barycentre de l'objet (objet_1);
    Depuis la photo 2 j'ai accès à la localisation de l'objectif (œil_2) et le barycentre de l'objet (objet_2);

    Le problème est que la position de objet_1 et objet_2 sont approximatifs et ça peut être le cas aussi pour œil_1 et œil_2 ...
    Soyons précis: connais-tu la distance (GCi) séparant le barycentre (G) de chacune des positions (C1, C2) du centre optique ? L'angle &#966; = (C1GC2) déterminé par les directions des deux demi-droites (GC1, GC2) ?
    Ou disposes-tu des coordonnées (géographiques ?) des points (C1, C2) et (G) ?

    Cela peut déboucher, à distance fixe, sur des calculs intéressants.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  9. #9
    Membre expert
    Bonjour question bête (je ne suis pas un matheux dans l'âme) mais par rapport à notre discussion avec wiwaxia sur les polygones (cf les derniers messages), le balayage de lignes "sweep line", ne serait-il pas adapté ici ? ou du moins une variante ? pour trouver cette fameuse intersection ?

    Bon courage

    Jérôme
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  10. #10
    Nouveau membre du Club
    Citation Envoyé par Pecose Voir le message

    Ce que je ne comprend pas c'est la formulation de la définition de droite: a1*x + b1*y + c1*z + d1 = 0
    Pourquoi "=0", pourquoi a1, b1 et c1 ne sont pas la même variable , c'est quoi d1 ?
    Ok, peut-tu nous en dire un peu plus sur ton niveau de math, afin de savoir à quel niveau placer les explications ?

    Dans un premier temps, pour simplifier, oublions les dimensions supplémentaires. Une droite dans le plan a une équation de la forme y = ax+b. Ok jusque-là ? Sauf si elle est verticale, où elle se retrouve avec une équation de la forme x = c
    Pour éviter de toujours manipuler des "sauf", on préfère mettre cette équation sous une forme plus générale. Si y = ax+b, alors -ax + y - b = 0

    Multiplions cette équation par un nombre réel arbitraire "k", et on obtient -kax + ky - kb = 0
    Maintenant, histoire de simplifier ces paramètres, je pose a1 = -ka, b1 = k, et c1 = -kb.
    J’obtiens a1x + b1y + c1 = 0
    C'est la forme canonique de l'équation d'un droite dans un plan. On remarque que ce format marche aussi si la droite est verticale.
    On note aussi que je peux choisir k arbitrairement, dans la manipulation ci-dessus. Il y a donc plusieurs équations possibles pour une même droite. En particulier, on peut imposer une contrainte de normalisation du type a1² + b1² = 1, et être sûr qu'il y a tout de même une solution. Il n'y a en revanche aucune raison pour que a1 et b1 soient égaux. Ils peuvent l'être pour certaines droites bien particulières (si le coefficient directeur de la droite vaux 1, en l’occurrence), mais la plupart du temps, ils ne le sont pas.

    Avec une dimension de plus, c'est pareil. On a juste le "z" et son paramètre associé qui s'ajoutent. On pourrait continuer d'ajouter des dimensions pour manipuler des droites dans un espace de dimension quelconque, l'équation aura toujours la même tête.

  11. #11
    Expert éminent sénior
    Citation Envoyé par Andéol Voir le message
    Dans un premier temps, pour simplifier, oublions les dimensions supplémentaires.
    Sauf que, en deux dimensions, deux droites non parallèles se coupent forcément. Ce qui n'est pas le cas en 3 dimensions. En 2 dimensions, le PO n'aurait pas besoin de poster la question sur un forum.

    Citation Envoyé par Andéol
    D1 a pour coordonnées a1*x + b1*y + c1*z + d1 = 0
    Es-tu au courant que ce que tu donnes ici n'est pas l'équation d'une droite mais l'équation d'un plan ? Et il faut 2 équations pour définir une droite dans un espace à 3 dimensions, à moins d'utiliser des artifices comme celui-ci :
    ( a1*x + b1*y + c1*z + d1 )2 + ( a2*x + b2*y + c2*z + d2 )2 = 0

    Avec une dimension de plus, c'est pareil.
    pffff
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  12. #12
    Membre habitué
    Citation Envoyé par wiwaxia Voir le message
    Soyons précis: connais-tu la distance (GCi) séparant le barycentre (G) de chacune des positions (C1, C2) du centre optique ?
    Ou disposes-tu des coordonnées (géographiques ?) des points (C1, C2) et (G) ?
    Je dispose des coordonnées géographiques du smartphone, donc des coordonnées des points de vues des photos.
    Photos à partir desquelles j'obtient la position de l'objet sur la photo.
    A partir de cette position sur la photo je doit en déduire la position le l'objet dans l'espace.
    Des jours c'est facile, des jours c'est pas facile, mais c'est jamais le même jour.

  13. #13
    Nouveau membre du Club
    Haa, mais quel crétin je fais ! Si sûr de moi alors que je déballe des bêtises. Merci pour la correction, Flodelarab. J'ai du boulot en édition pour corriger mes inepties.

  14. #14
    Membre habitué
    Citation Envoyé par Andéol Voir le message
    Ok, peut-tu nous en dire un peu plus sur ton niveau de math, afin de savoir à quel niveau placer les explications ?
    En fait je ne comprend même pas la formule y = ax+b
    Je n'arrive pas à traduire ça en image dans ma tête.
    Là on est bien dans un plan en 2D?
    Intuitivement, si je devais décrire une droite je chercherai une formule qui se lise: (Ma droite) = (Formule qui décrit ma droite)
    Mais là, j'imagine bien que 'y' c'est pas le nom de ma droite...
    Du coup comment je doit lire cette formule?
    Par ailleurs, 'a' et 'b' c'est quoi concrètement?
    J'ai même des doutes sur 'x' et 'y'.
    Il faut vraiment tout m'expliquer, j'en suis désolé.
    Des jours c'est facile, des jours c'est pas facile, mais c'est jamais le même jour.

  15. #15
    Expert éminent sénior
    Là on est bien dans un plan en 2D?
    Là, c'est moi qui décroche.

    Il faut vraiment tout m'expliquer, j'en suis désolé.
    Mais déjà, est-ce que le postulat de base est vrai ? Peut-on déterminer la position d'un objet à partir de 2 positions et 2 photos ? Après étude, je pense que NON !

    Soit P1 et P2 les 2 positions géographiques d'où l'on prend une photo. P1 et P2 sont immuables car donnés par l'énoncé.
    Soit A le coin supérieur gauche de l'objet.
    Soit B le coin inférieur droit de l'objet.
    On fixe 2 photos symbolisées par 2 segments. 1 vert et 1 cyan.



    Sur la première image, on obtient un objet.
    Sur la seconde image, on obtient un autre objet bien différent en taille, position, etc.
    Pourtant les points de prise de vue P1 et P2 n'ont pas bougé et les photos verte et cyan sont les mêmes.
    Donc l'hypothèse de départ est fausse.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  16. #16
    Membre habitué
    Citation Envoyé par Flodelarab Voir le message

    Pourtant les points de prise de vue P1 et P2 n'ont pas bougé et les photos verte et cyan sont les mêmes.
    Donc l'hypothèse de départ est fausse.
    Oui parce que tu as modifier la distance entre la photo et la prise de vue.
    Cette distance doit être prise arbitrairement puisque qu'elle n'existe pas dans le monde réel.
    Mais elle doit être prise une fois pour toute et suffisamment grande simuler que la photo est très loin de la prise de vue.
    Sinon effectivement on se retrouvent avec des aberrations.
    Des jours c'est facile, des jours c'est pas facile, mais c'est jamais le même jour.

  17. #17
    Membre expérimenté
    Si on suppose que l'objet est petit et situé loin, avec les notations de wiwaxia on a D= c1c2/Phi.
    Phi peut être déterminé en connaissant l'angle dont on a tourné la caméra (Phi1) et le déplacement de l'image sur le capteur Phi2=dx/f. (Phi=Phi1+Phi2).
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  18. #18
    Membre chevronné
    Calculer le point d’intersection de deux segments dans un espace 3D
    Citation Envoyé par Pecose Voir le message
    Je dispose des coordonnées géographiques du smartphone, donc des coordonnées des points de vues des photos.
    Photos à partir desquelles j'obtiens la position de l'objet sur la photo.
    A partir de cette position sur la photo je doit en déduire la position le l'objet dans l'espace.
    Il faut une donnée supplémentaire, afin de localiser l'objet photographié:
    # soit les coordonnées d'un point de l'objet (par ex. le barycentre G),
    # soit les directions des deux axes optiques, qui représentent les orientations dans lesquelles sont prises les photos, par exemple les angles que font ces axes avec le méridien local.

    Le calcul est probablement laborieux, mais réalisable.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  19. #19
    Expert confirmé
    Salut

    les points remarquable de la photo sont déterminé par quel repère ? (le bord de la photo,la distance de l’appareil,... )

    la première question portais sur le calcul de distance entre deux prise de vue
    je suppose pour un même objet

    les éléments connues sont :
    La position de l'appareil photo.

    deux points remarquable par photo d'un même objet

    il manque un point d'attache fixe et connue entre les appareils et les photos.

    par exemple une mire qui est a une distance et a une taille connue. cela permet d'avoir un point fixe de comparaison.

    Je préconise de calculer le barycentre afin d’éliminer les erreur de translation dans le calcul final
    car quelque soit la photos le point d'origine seras le même

    pour conclure il manque donc des éléments afin de pouvoir mettre en place une solution fiable
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  20. #20
    Membre habitué
    Citation Envoyé par anapurna Voir le message
    pour conclure il manque donc des éléments afin de pouvoir mettre en place une solution fiable
    J'ai l'impression que le sujet à dérivé ,
    En fait j'ai déjà réaliser une simulation en 2D qui fonctionne avec uniquement la position, l’orientation du smartphone et la position de l'objet sur les images. Je n'ai besoin de rien d'autre pour trouver la position de l'objet dans l'espace.
    Mon problème intervient lorsque je passe à la 3D, puisque les segments qui relient l’œil à l'image ne se croisent pas forcement.

    Quelqu'un peut t'il m'expliquer y = ax+b?
    Des jours c'est facile, des jours c'est pas facile, mais c'est jamais le même jour.

###raw>template_hook.ano_emploi###