4. Parallele Geradeb mit ausreichendem Abstand identifizieren

Parallele Geradeb mit ausreichendem Abstand identifizieren

  • ?

    Hallo,
    ich habe in meinem C++-Programm eine Menge von Geraden (jeweils definiert durch zwei Punkte) die ich analysieren will.

    Ich will alle zueinander parallelen Geraden identifizieren. 2 Probleme gibt es: Problem 1, die Geraden können etwas ungenau sein. Das heißt eine Gerade mit der Steigung von 1 ist in Wahrheit parallel zu einer Geraden mit Steigung 1,2. Problem 2, es können mehrere sehr ähnliche Geraden vorkommen, die in Wahrheit nur eine einzige Gerade sind. Das heißt, diese "überflüssigen" Geraden sollen raus gefiltert und nur ein Mal beachtet werden.

    Ich gehe momentan so vor:
    Ich berechne zu allen Geraden die Steigung m und den Y-Achsenabschnitt n. Nun vergleiche ich in einer geschatelten Schleife:

    for(int i = 0; i < Anzahl der Geraden; i++)
    for(int h = i + 1; h < Anzahl der Geraden; h++)
        wenn m von Gerade i == m von Gerade h +/- Delta
            => Parallel oder Identisch
            wenn n von Geraden i == n von Geraden h +/- Delta  // bzw. dies muss bei allen bereits gefundenen Parallelen geprüft werden
                => Geraden identisch

    Dieses Verfahren birgt aber Probleme. Zum Beispiel wenn eine Gerade parallel zur Y-Achse ist, da dort ein div0 vorkommt. In diesem Fall setze ich die Steigung auf den maximal-Wert und beim Prüfen ob identisch wird das ganze mit dem X-Achsenabschnitt gemacht.
    Hierbei gestaltet sich das Einbeziehen des Deltas als schwierig.
    Aber nicht nur das macht mir Schwierigkeiten, ich habe auch das Gefühl dass ein statisches Delta beim Prüfen der Steigung zu ungewünschten Ergebnissen führt. Beim Betrachten des Ergebnisses hätte ich für hohe Steigungen ein großes Delta genommen, hingegen bei flachen Steigungen eher ein kleines Delta.

    Deshalb bin ich nun auf der Suche nach Verbesserungen und/oder Alternativen.

    Da ich sicher nicht der erste mit diesem Problem bin und ich über eine Google Suche keine Lösung gefunden habe, die ich aus dem Stand als passend empfand, hoffe ich auf Hilfe von euch.

    Vielen Dank

    0
  • G

    Man kann Geraden auf unterschiedliche Art und Weise angeben. Du hast eine Geradengleichung der Art

    f(x) = ax + b

    im Kopf und wenn Du eine Gerade parallel zur y-Achse hast, versagt diese Gleichung.

    Eine bessere Repräsentation von Geraden hast Du, wenn Du sie durch folgende Größen charakterisierst:

    1. Den minimalen Abstand der Geraden zum Ursprung.
    2. Den Winkel, den die kürzeste Verbindung zwischen der Gerade und dem Ursprung mit der x-Achse (oder meinetwegen auch der y-Achse) einschließt.

    Auf der linken Seite der folgenden Grafik ist abgebildet, was ich meine:

    http://campar.in.tum.de/twiki/pub/Students/DaPentenrieder/hough.jpg

    Bei so einer Darstellung hast Du nicht das Problem, dass die Steigung plötzlich unendlich wird.

    0
  • ?

    Hallo Gregor,
    Danke für den Tipp. Die Art der Darstellung wäre sinnvoll. Auf Parallelität zu Prüfen wäre damit einfach. Bei gleichem Winkel Parallel, bei unterschiedlichen Abstand sind sie nicht identisch.

    Doch wie komme ich von 2 Punkten (also z.B. Gerade von A(2/3) nach B(6/9)) am geschicktesten (und für den Rechner am unaufwendigsten) zu dieser Darstellung?

    0
  • Mod

    Xenya schrieb:

    Doch wie komme ich von 2 Punkten (also z.B. Gerade von A(2/3) nach B(6/9)) am geschicktesten (und für den Rechner am unaufwendigsten) zu dieser Darstellung?

    Den Winkel könntest du leicht durch die atan2-Funktion bekommen. Ich würde aber nicht direkt mit dem Winkel arbeiten. Wenn man explizit Winkel ausrechnet, dann ist dies (außer für ein Endergebnis) fast immer ein unnötig umständlicher Weg. Zudem rechenintensiv. Ich würde mit einem Richtungsvektor (A-B) arbeiten. Wenn du die Richtungsvektoren noch normierst, so ist der Winkel zwischen zwei Vektoren am Skalarprodukt ablesbar. Ist das Skalarprodukt größer als der Cosinus der Winkeltoleranz (nur einmal ausrechnen!), sind die Geraden parallel. Wichtig ist noch, dass du den Betrag des Skalarprodukts nimmst, für den Fall, dass die Richtungsvektoren antiparallel sind.

    0
  • ?

    Danke für deine Antwort.

    Ich versuch deine Antwort noch mit den Rechnungen wiederzugeben. Vielleicht gibt es noch Optimierungen, außerdem könnte es jemandem helfen der zufällig auf den Beitrag stößt:

    Ok du meinst also, ich soll anstatt der Polardarstellung (ρ,θ)(\rho, \theta) mit der Vektordarstellung einer Gerade ax+by+c=0ax + by + c = 0 arbeiten:
    Richtungsvektor v⃗=(vx,vy)\vec{v} = (vx, vy) der Geraden \overrightarrow{AB}:

    \begin{align*}vx &= ax - bx\\ vy &= ay - by$ \end{align*}

    Parameter der Vektordarstellung ax+by+c=0ax + by + c = 0:

    \begin{align*}a &= vy\\ b &= -vx\\ c &= -(a \cdot ax + b \cdot ay)\end{align*}

    Normalenvektor der Gerade:
    Beim Durchlauf der Gerade in Richtung v⃗\vec{v}...

    \begin{align*}\text{... nach links: }\vec{n} &= (-b, a)\\ \text{... nach rechts: }\vec{n} &= (b, -a)\end{align*}

    Da mir die Richtung egal ist, nehm ich einfach einen davon.

    Winkel Berechnung zwischen Vektoren:
    cos(φ)=a∘b∣a∣∘∣b∣\cos(\varphi) = \frac{a \circ b}{|a| \circ |b|}
    Bei Normalenvektoren kann man es auf folgende Form kürzen
    cos(φ)=a∘b\cos(\varphi) = a \circ b
    Wenn der Cosinus aus Effizienz-Gründen nicht berechnet werden soll, also nur a∘ba \circ b berechnet wird, kommt bei einer Parallelen entweder 1 oder -1 raus. Hier einfach den Betrag nehmen, also ∣a∘b∣|a \circ b| und mit dem Delta ∣cos(deltaPhi)∣|\cos(deltaPhi)| vergleichen.

    Bis dahin ist auch alles effizient zu berechnen. Beim berechnen des Abstands, also prüfen ob zwei Geraden als identisch angesehen werden können, wirds allerdings bisschen unschön. Abstand dd zu einer Gerade in der Form ax+by+c=0ax + by + c = 0 wird berechnet, in dem ein Punkt der 1. Gerade in die Gleichung d=a⋅x+b⋅y+ca⋅a+b⋅bd = \frac{a \cdot x + b \cdot y + c}{\sqrt{a \cdot a + b \cdot b}} mit dem aa, bb und cc der 2. Gerade eingesetzt wird. Also erst den Punkt berechnen. Dazu setze ich x=0x = 0 in die 1. Gerade ein:
    y=−c_1b_1y = \frac{-c\_1}{b\_1}
    Dann in die Gleichung:
    d=b_2⋅−c_1b_1+c_2a_2⋅a_2+b_2⋅b_2d = \frac{b\_2 \cdot \frac{-c\_1}{b\_1} + c\_2}{\sqrt{a\_2 \cdot a\_2 + b\_2 \cdot b\_2}}
    Da dies negativ sein kann, je nach dem in welche Richtung der Abstand geht, muss dazu noch der Betrag genommen werden. Der kann dann mit dem Abstands Delta verglichen werden.

    Hab ich alles richtig verstanden? Würde ihr die Prüfung auf "identisch" so machen oder habt ihr eine Idee, mit dem es effizienter wird (muss ja doch öfters gemacht werden und da was ohne Wurzel wäre sicher schöner).

    0
  • Mod

    Die Beschreibung der Vektordarstellung der Geraden finde ich bei dir ein wenig umständlich, auch wenn's rechnerisch ungefähr das gleiche sein dürfte. Du hast doch, wenn ich recht verstehe, zwei Punkte A=(a_xa_y)A=\begin{pmatrix}a\_x\\a\_y\end{pmatrix} und B=(b_xb_y)B=\begin{pmatrix}b\_x\\b\_y\end{pmatrix}. Dann ist der Richtungsvektor der Geraden d⃗=(a_x−b_x(a_x−b_x)2+(a_y−b_y)2a_y−b_y(a_x−b_x)2+(a_y−b_y)2)\vec d = \begin{pmatrix}\frac{a\_x-b\_x}{\sqrt{(a\_x-b\_x)^2+(a\_y - b\_y)^2}}\\ \frac{a\_y-b\_y}{\sqrt{(a\_x-b\_x)^2+(a\_y - b\_y)^2}}\end{pmatrix}.

    Der Winkel zwischen zwei Richtungsvektoren d⃗1\vec d_1 und d⃗2\vec d_2 muss dann die Bedingung ∣d⃗_1⋅d⃗_2∣≥cos(ΔWinkel)\left|\vec d\_1 \cdot \vec d\_2 \right| \ge cos(\Delta Winkel) erfüllen, damit du sie als parallel ansiehst.

    Was den Abstand angeht: Wie definierst du den Abstand? In 2D schneiden Geraden sich immer irgendwo, außer sie sind wirklich absolut perfekt parallel (wobei man dann sagen kann, sie schneiden sich im unendlichen), haben mathematisch also immer den Abstand 0. Auch dann, wenn du sie mit deinem toleranten Kriterium als parallel ansiehst.

    0
  • S

    Das habe ich nie verstanden. Wieso kann man sagen, dass sich zwei parallele Geraden im Unendlichen schneiden?

    0
  • ?

    Sone schrieb:

    Das habe ich nie verstanden. Wieso kann man sagen, dass sich zwei parallele Geraden im Unendlichen schneiden?

    Das ist (im Affinen) auch falsch. Es stimmt in der projektiven Ebene P2

    0
  • Mod

    Sone schrieb:

    Das habe ich nie verstanden. Wieso kann man sagen, dass sich zwei parallele Geraden im Unendlichen schneiden?

    Das ist eine Verallgemeinerung der euklidischen Geometrie. In vielen Beweisen fallen dann Formulierungen wie "außer die Geraden sind parallel" weg. Man kann damit auch definieren, was ein unendlich großer Grenzwert ist. Guckst du hier:
    http://en.wikipedia.org/wiki/Projective_geometry

    0
  • ?

    [quote="SeppJ"]

    Sone schrieb:

    Man kann damit auch definieren, was ein unendlich großer Grenzwert ist.

    Was soll das sein?

    0
  • Mod

    gurlkentruppe schrieb:

    SeppJ schrieb:

    Man kann damit auch definieren, was ein unendlich großer Grenzwert ist.

    Was soll das sein?

    Ja, ich wusste, die Formulierung ist blöd, aber mir fiel nichts besseres ein. Zum Beispiel die Gleichung für den Schnittpunkt zweier Geraden hat eben als Grenzwert für den Winkel gegen 0 einen unendlich entfernten Punkt. Das ist somit eine Mögliche Definition, was überhaupt mit "Unendlich" genau gemeint ist.
    http://en.wikipedia.org/wiki/Infinity#Real_analysis
    Das meinte ich mit einem "unendlich großen Grenzwert".

    0
  • ?

    SeppJ schrieb:

    Was den Abstand angeht: Wie definierst du den Abstand? In 2D schneiden Geraden sich immer irgendwo, außer sie sind wirklich absolut perfekt parallel (wobei man dann sagen kann, sie schneiden sich im unendlichen), haben mathematisch also immer den Abstand 0. Auch dann, wenn du sie mit deinem toleranten Kriterium als parallel ansiehst.

    ahhh, da hast du natürlich recht. An das hab ich gar nicht gedacht!

    Aber da ich mit der ax+by+c=0ax + by + c = 0-Darstellung eh nicht direkt den Abstand zweier Geraden errechne, sondern mit der Formel
    d=b_2⋅−c_1b_1+c_2a_2⋅a_2+b_2⋅b_2d = \frac{b\_2 \cdot \frac{-c\_1}{b\_1} + c\_2}{\sqrt{a\_2 \cdot a\_2 + b\_2 \cdot b\_2}}
    die einen Punkt als Hilfsmittel verwendet, habe ich das mathematische Problem nicht, dass sie sich irgend wann evtl schneiden.

    Wie ich den Abstand definiere? Ich kann kurz erklären für was ich es brauche:
    Ich will Bilder auswerten und herausfinden, ob darauf ein Baustein (also prinzipiell ein Quader mit bestimmten Merkmalen) und in welcher Größe vorhanden ist.
    Deshalb suche ich im Bild alle Kanten. Da für einen Computer eine Gerade im Bild nicht so einfach zu erkennen ist wie für einen Menschen, kann es sein dass er mehr Gerade für eine Kante erkennt.

    Das zweite Problem ist, dass auch Geraden gefunden werden, die überhaupt nichts mit dem Objekt zu tun haben.

    Dritte Problem, ich muss die Geraden auch noch interpretieren um zum einen sagen zu können, dass es sich wirklich um ein Quader handelt (und wie groß er ist - das ist aber erst der nächste Schritt).

    Das Erkennen will ich über Eigenschaften des Objekts machen. Also war die erste Überlegung: Alle Kanten stehen bei einem Quader im rechten Winkel auf seinen Nachbarkanten. Also könnte man Geraden als "korrekt" identifizieren, in dem geprüft wird ob an beiden Enden mindestens eine Gerade im rechten Winkel vorhanden ist. Da im perspektivischen Bild (der Stein soll liegen dürfen wie er will) allerdings die Winkel nicht immer als 90° darstellen, habe ich die Idee wieder verworfen.
    Zweite Idee die ich probieren wollte war, dass ich parallele Geraden zähle. Egal wie ich auf den Stein schaue, der Würfel hat von einer "Sorte paralleler Gerade" minimal 2 Kanten und maximal 3 Kanten.
    Deshalb wollte ich alle Geraden durchgehen und prüfen, ob andere Geraden parallel zu dieser stehen und weit genug auseinander sind (sonst sind es nur 2 gefundene Gerade die zu einer Kante gehören). Wenn eine Gerade keine Parallele hat oder mehr als 3 wird sie verworfen.

    Aber ich glaube, ich kann diese Idee auch verwerfen. Weil genauso wie sich Winkel im perspektivischen Bildern verzerren, verzerren sich damit auch die Parallelen. Muss mir eine neue Möglichkeit überlegen.

    Nichtsdestotrotz ist diese Unterhalt sehr gut, weil es kann gut sein, dass ich diese Rechnungen trotzdem noch irgend wann brauche.

    0
  • Mod

    Da habe ich ein paar Feststellungen:
    -Du hast keine Geraden, sondern Linien. Das heißt, du kannst dein tolerantes Parallelitätskriterium noch anwenden, aber, da die Linien einen Anfang und ein Ende haben, kann man schon einen Abstand definieren
    -Da du sicherlich auch noch möchtest, dass die Linien eines Quaders irgendwie "nebeneinander" sind, würde ich ein ganz anderes Kriterium vorschlagen, ob sie (potentiell) zum gleichen Quader gehören: Die Abstände zwischen Anfang und Ende sind (vektoriell gesehen) gleich (im Rahmen einer gewissen Toleranz).
    So erledigst du gleich haufenweise Sonderfälle, die du noch prüfen müsstest, wenn du nur zuerst auf Parallelität prüfst. Zum Beispiel schließt du so aus, dass die Parallelen unterschiedlich lang sind. Falls du weißt, wie groß die Querkanten maximal sein können (Perspektive beachten!), dann kannst du sogar sagen, ob der Abstand zu groß/klein ist, um ein Quader zu sein.
    -Das Problem klingt nach etwas, was bestimmt schon lange und besser gelöst ist. Ich kenne mich weder mit Bilderkennung noch mit Robotern aus, aber da dieses Problem ziemlich essentiell ist und es aber Roboter gibt, würde ich mal annehmen, es gibt auch halbwegs gute Lösungen für das Problem. Mach dich doch mal kundig!

    0
  • J

    SeppJ schrieb:

    Was den Abstand angeht: Wie definierst du den Abstand?

    Na so wie immer in einem metrischen raum: für zwei Mengen A und B ist d(A,B) := inf {d(a,b) | a in A, b in B}. Damit ist übrigens affin der abstand zwischen parallelen geraden auch "mathematisch" nicht 0.

    0
  • ?

    SeppJ schrieb:

    Das Problem klingt nach etwas, was bestimmt schon lange und besser gelöst ist. Ich kenne mich weder mit Bilderkennung noch mit Robotern aus, aber da dieses Problem ziemlich essentiell ist und es aber Roboter gibt, würde ich mal annehmen, es gibt auch halbwegs gute Lösungen für das Problem. Mach dich doch mal kundig!

    Ja, das dachte (denke ich noch immer) ich auch. Einen Ansatz habe ich gefunden, indem man Bilder trainiert. Das heißt von einem gesuchten Objekt viele Bilder aus verschiedenenen Blickrichtungen.

    So kann man dann im neuen Bild nach Ähnlichkeiten suchen.

    Ich hätte allerdings gehofft, dass ich es mit den Eigenschaften finden kann. So kann ich verschiedenste Größen einfach unterscheiden, ohne alle extra aufwendig antrainieren zu müssen.

    Aber meine Suche ist noch nicht zu Ende.

    SeppJ schrieb:

    -Da du sicherlich auch noch möchtest, dass die Linien eines Quaders irgendwie "nebeneinander" sind, würde ich ein ganz anderes Kriterium vorschlagen, ob sie (potentiell) zum gleichen Quader gehören: Die Abstände zwischen Anfang und Ende sind (vektoriell gesehen) gleich (im Rahmen einer gewissen Toleranz).

    Wie meinst du das.

    Wenn ich zum Beispiel die beiden Kanten der oberen Seite vergleiche, dann ist die vordere, die näher an der Kamera ist, länger als die, die weiter entfernt ist.

    0
Anmelden zum Antworten