Strahlenmengen schneiden durch Raumtransformation



  • Guten Tag Forumer,

    wie im Topic angedeutet, hab ich zwei Mengen an Strahlen. Die Anzahl kann ich reltiv frei bestimmen, ich denke ich brauche mindestens soviele, wie das System dimensioniert ist. Jede dieser Mengen hat einen Ursprung, ich kenne auch die Paare, also welcher Strahl von der ersten Menge mit welchem Strahl der zweiten Menge, die sich schneiden.
    Ich muss jetzt eine Transformation (Rotation+Translation) bestimmen, die die zweite Menge so in den Raum der ersten positioniert, dass alle "Strahlenpaare" sich schneiden.

    Mir reicht es, wenn ich entweder die 3 Schnittpunkte oder die relative Transformation des Ursprungs habe, dann kann ich den Rest ausrechnen, aber z.Z. hab ich soviele unbekannte und dennoch ein so strikt bestimmtes System, dass mir kein Lösungsansatz einfällt.

    Beispiel:

    Strahlenmenge 1:
    O0+D0*r0=A
    O0+D1*r1=B
    O0+D2*r2=C
    Strahlenmenge 2:
    Oa+Da*ra=A
    Oa+Db*rb=B
    Oa+Dc*rc=C
    

    Wobei O der Ursprung ist, D die Dichtung und r jeweils die Länge.

    Als ersten schritt nehm ich an dass der Ursprung von der ersten Menge im Ursprung des Koordinatensystems liegt, dadurch hab ich nur noch Richtungen * Länge.

    Strahlenmenge 1:
    D0*r0=A
    D1*r1=B
    D2*r2=C
    Strahlenmenge 2:
    Oa(-O0)+Da*ra=A  -> oa+Da*ra=A
    Oa(-O0)+Db*rb=B  -> oa+Db*rb=B
    Oa(-O0)+Dc*rc=C  -> oa+Dc*rc=C
    

    Dann hab ich überlegt ein Gleichungssystem zu erstellen, aber da ich nicht weiss wo der zweite Urpsrung ist, transformiere ich nur das Gleichungssystem um wenn ich es mit Gauss löse, oder? 3 Dimensional:

    r0   r1    r2   ra   rb  rc   oax   oay   oaz
    D0x   0     0   -Dax 0   0    1      0     0
    0    D1x    0   0   -Dax 0    1      0     0
    0     0    D2x  0   0   -Dbx  1      0     0
    D0y   0     0   -Day 0   0    0      1     0
    0    D1y    0   0   -Day 0    0      1     0
    0     0    D2y  0   0   -Dby  0      1     0
    D0z   0     0   -Daz 0   0    0      0     1
    0    D1z    0   0   -Daz 0    0      0     1
    0     0    D2z  0   0   -Dbz  0      0     1
    

    Und mit Gaus zu lösen, aber es ist 9x9 und die letzten Reihen sind linear abhängig.Hmm.

    Ich hab auch überlegt es geometrisch zu lösen. Ich kann den ersten Schnittpunkt frei bestimmen und beide Mengen so verschieben, dass ein Strahlenpaar sich schneidet.
    Aber nun ist der zweite Schnittpunkt auch vom Dritten abhängig. Ich kann den zweiten raum zwar so rotieren, dass der zweite Schnittpunkt stimmt, aber beim dritten muss ich sowohl den Raum transformieren als auch die Schnittpunkte B und C anpassen.

    Jemand eine gute Idee?



  • Das klingt so, als wolltest du bei einem Stereokamerasystem (wobei die intrinsischen Parameter schon kalibriert wurden) die "Essential-Matrix" bestimmen und faktorisieren.

    Siehe hier
    https://en.wikipedia.org/wiki/Essential_matrix



  • Wenn ich mich richtig erinnere, kommt da ein homogenes Gleichungssystem raus, wo Du aber an einer nichttrivialen Lösung interessiert bist. Du suchst also:

    A * e = 0

    wobei du |e|=1 erzwingst und e dir dann die Einträge der Essential Matrix verrät. Das kann man mit der Singulärwertzerlegung ausrechnen:

    U*S*V^T = A

    Bei absteigend sortierten Singulärwerten in S ist das e, was A*e=0 mit |e|=1 im Sinne der kleinsten Fehlerquadrate löst, gegeben durch die letzte Spalte in V.



  • Wichtig ist, dass der kleinste Singulärwert nahe 0 ist und das der nächst größere auch signifikant größer ist (relativ gesehen). Wenn das nicht der Fall ist, ist die berechnete Lösung nicht eindeutig oder ggf schlecht. Das hieße dann, dass die Strahlenmengen ungünstig und/oder zu klein waren.

    Wenn du irgendwas wissenschaftliches machst, 'ne Masterarbeit schreibst oder sowas, dann leih Dir mal "Multiple View Geometry" von Hartley und Zisserman aus. Das kann man dann auch prima referenzieren, das Buch.

    Viel Erfolg.



  • Deine Beschreibung ist sehr vage.

    Ich muss jetzt eine Transformation (Rotation+Translation) bestimmen, die die zweite Menge so in den Raum der ersten positioniert, dass alle "Strahlenpaare" sich schneiden.

    Reicht nicht, 1.) da ich einfach die Translation so waehlen kann, dass der eine Strahlursprung der ersten Menge auf den der zweiten Menge verschoben werden kann. 2.) ich eine Rotation so waehlen kann, dass keine Strahlenpaare parallel sind (fuer den 2D-Fall).

    aber da ich nicht weiss wo der zweite Urpsrung ist,

    Aber du hast doch die Strahlen ... 😕

    Koenntest du bitte mal formal aufschreiben, was gegeben ist? Also wie in der Schule mit "gegeben" und "gesucht". Eine Skizze waere auch sehr hilfreich.



  • Ich habe das so verstanden:
    Gegeben sind n Paare von "Strahlen" (a,b), wobei die Strahlen jeweils im 0-Punkt starten und in einer bekannten Richtung weiterlaufen. a_i und b_i seien hier die 3D Richtungsvektoren des i-ten Strahlenpaars. Gesucht ist eine Rotation R und Translation t der Strahlen b_i, so dass sich b_i mit a_i für jedes i im Sinne der kleinsten Fehlerquadrate "schneidet". Formelmäßig lässt sich das als schreiben als
    \left( \vec{a\_i} \times left( R \vec{b\_i} \right) \right) \cdot \vec{t} = \vec{0} \forall i
    Die zwei Strahlenursprünge (0 und t) und der Schnittpunkt ergeben ein Dreieck. Das Kreuzprodukt links liefert die Normale des Dreiecks, welche senkrecht zu t steht. Dementsprechend muss das Skalarprodukt zwischen Normale und Kante 0 sein. Auffällig ist hier, dass t offensichtlich nur bis auf einen Skalierungsfaktor bestimmt werden kann. Das richtige Stichwort dazu hatte ich ja auch schon genannt: "Essential Matrix".

    Find's nur schade, dass der OP nichts mehr von sich hören lässt. Vielleicht haben ihm/ihr schon meine kurzen Antworten gereicht. Das Problem ist ja kein neues. Es ist ein sehr bekanntes aus dem Bereich Computer Vision.



  • Upps... Da fehlte ein Backslash:
    (a_i×(Rb_i))t=0\left( \vec{a\_i} \times \left( R \cdot \vec{b\_i} \right) \right) \cdot \vec{t} = \vec{0}



  • Und das Skalarprodukt liefert natürlich keinen Vektor:
    (a_i×(Rb_i))t=0\left( \vec{a\_i} \times \left( R \cdot \vec{b\_i} \right) \right) \cdot \vec{t} = 0

    So! Bin jetzt erst mal still. 🙂



  • Und das kann man umschreiben als

    a_iTEb_i=0\vec{a\_i}^T \cdot E \cdot \vec{b\_i} = 0

    wobei R und t in der 3x3-Matrix ("Essential-Matrix") E stecken. Und das lässt sich wiederum schreiben als

    Mie=0M_i \cdot \vec{e} = 0

    wobei e hier ein 9D Vektor ist, der die Elemente der Matrix E enthält und M_i eine 1x9-Matrix ist, wo a_i und b_i drin stecken. Über alle i ergibt das ein homogenes Gleichungssystem:

    (M1M2Mn)e=0\begin{pmatrix} M_1 \\ M_2 \\ \vdots \\ M_n \end{pmatrix} \cdot \vec{e} = \vec{0}

    Eine nicht-triviale Lösung (e != 0) lässt sich über eine SVD finden.

    Wahrscheinlich sollte man diese Lösung aber nur als Startwert eines iterativen Optimierungsverfahrens verwenden. Es ist zu erwarten, dass dadurch ein "besserer Fit" berechnet werden kann.


Log in to reply