Übereinstimmungsmenge von x, y zeigt auf eine andere Menge, die skaliert, gedreht, übersetzt und mit fehlenden Elementen versehen ist
( Warum mache ich das? Siehe Erklärung unten )
Betrachten Sie zwei Gruppen von Punkten, A und B , wie unten gezeigt.
Es sieht vielleicht nicht so aus, aber set A ist innerhalb von set B "versteckt". Es ist nicht einfach zu sehen, da Punkte in B skaliert, gedreht und in (x, y) in Bezug auf A übersetzt werden. Noch schlimmer, einige Punkte in A fehlen in B , und B enthält viele Punkte, die nicht in A sind.
Ich muss die passende Skalierung, Rotation und Übersetzung finden, die auf den B -Satz angewendet werden muss, um ihn mit set A zu vergleichen. In dem oben gezeigten Fall sind die korrekten Werte:
was die (gut genug) Übereinstimmung erzeugt
(in rot werden nur die übereinstimmenden B Punkte angezeigt; diese befinden sich im Sektor 1000<x<2000, y~2000 in der ersten Abbildung rechts). Angesichts der vielen Freiheitsgrade (DoF: Skalierung + Rotation + 2D-Translation) ist mir die Möglichkeit eines Miss-Match bekannt, aber die Koordinaten der Punkte sind nicht zufällig (obwohl sie so aussehen mögen) also die Wahrscheinlichkeit dafür passiert ist sehr klein.
Der Code, den ich geschrieben habe (siehe unten), verwendet Brute-Force, um alle möglichen DoF-Werte zu durchlaufen, die aus vordefinierten Bereichen für jeden einzelnen ausgewählt wurden. Der Kern des Codes basiert auf der Minimierung der Entfernung jedes Punktes in A zu jedem Punkt in B
Der Code funktioniert (er hat tatsächlich die oben erwähnte Lösung erzeugt), aber da die Anzahl der Lösungen (dh die Kombinationen akzeptierter Werte für jedes DoF) mit größeren Bereichen skaliert, kann er ziemlich schnell unannehmbar langsam werden (auch er isst) den gesamten RAM in meinem System hoch)
Wie kann ich die Leistung des Codes verbessern? Ich bin offen für jede Lösung einschließlich numpy und / oder scipy . Vielleicht etwas wie Basing-Hopping um nach dem zu suchen beste Übereinstimmung (oder eine relativ enge) anstelle der Brute-Force-Methode, die ich derzeit verwende?
Warum mache ich das?
Wenn ein Astronom ein Sternfeld beobachtet, muss er auch ein so genanntes "Standardfeld von Sternen" beobachten. Dies wird benötigt, um die "Instrumentalgrößen" (ein logarithmisches Helligkeitsmaß) der beobachteten Sterne auf eine gemeinsame universelle Skala umrechnen zu können, da diese Größen vom verwendeten optischen System (Teleskop + CCD-Array) abhängen. In dem hier gezeigten Beispiel ist das Standardfeld links unten und das beobachtete Feld rechts zu sehen.
Beachten Sie, dass die Punkte in der Menge A (oben verwendet) die markierten Sterne im Standardfeld sind, und die Menge B sind die Sterne im beobachteten Feld (oben rot markiert)
Der Prozess der Identifizierung jener Sterne in dem beobachteten Feld, die den im Standardfeld markierten Sternen entsprechen, erfolgt mit dem Auge noch heute. Dies liegt an der Komplexität der Aufgabe.
In dem oben beobachteten Bild gibt es eine Menge Skalierung, aber keine Rotation und wenig Translation. Dies ist ein eher günstiges Szenario; es könnte viel schlimmer sein. Ich versuche, einen einfachen Algorithmus zu entwickeln, um zu vermeiden, Sterne im beobachteten Feld manuell als Sterne im Standardfeld einzeln identifizieren zu müssen.
Lösung vorgeschlagen von literpresence
Dies ist ein Skript, das ich nach der Antwort von literpresence erstellt habe.
%Vor%Die Methode ist fast sofort und erzeugt die richtige Übereinstimmung:
%Vor% 
2 Antworten
1) Ich würde dieses Problem angehen, indem ich alle Punkte beschreibe und alle möglichen Kombinationen von 3 Punkten aus jedem Satz finde.
%Vor%Wie alle Permutationen einer Liste in generiert werden Python
2) Berechnen Sie für jede 3-Punkte-Gruppe die Seiten des jeweiligen Dreiecks; Wiederholen Sie den Vorgang für Gruppe A und Gruppe B.
%Vor%Wie finde ich den Abstand zwischen zwei Punkten?
3) Reduziere dann das Verhältnis der Seiten für jedes so, dass die kleinste Seite jedes Dreiecks dann gleich 1 ist; die anderen Seiten sind im jeweiligen Verhältnis zurückgegangen.
In zwei ähnlichen Dreiecken:
Die Umfänge der zwei Dreiecke sind im gleichen Verhältnis wie die Seiten. Die entsprechenden Seiten, Mediane und Höhen sind alle in das gleiche Verhältnis.
4) Schließlich für jedes ein Dreieck aus der Gruppe A, vergleichen Sie mit jedem Dreieck aus der Gruppe B, mit elementweiser Subtraktion. Dann summiere die resultierenden Elemente und finde die Dreiecke aus A und B mit der kleinsten Summe.
%Vor%Subtrahieren von 2 Listen in Python
5) Gegebene übereinstimmende Dreiecke; Die richtige Skalierung, Translation und Rotation sollte relativ trivial in Bezug auf CPU / RAM sein.
ETA1: Rohentwurfsskript
ETA2: Patch-Fehler in den Kommentaren: mit sum (abs ()) anstelle von abs (sum ()). Jetzt klappt es auch, schnell!
%Vor%Es gibt einen Algorithmus namens Multi Dimensional Scaling oder MDS ( Ссылка ) ), die das Ausmaß solcher Transformationen findet. Es ist eng verwandt mit der Hauptkomponentenanalyse, verwendet aber einen Vektor linearer Unähnlichkeiten anstelle von Kovarianzen (die eine Art quadratische Unähnlichkeit darstellen).
Um die Rotation und den Offset wiederherzustellen, können Sie RANSAC ( Ссылка verwenden ).
Tags und Links python performance geometry astronomy affinetransform