Ich habe zwei Listen mit x-y-Koordinaten (von Sternen). Ich könnte auch Größen (Helligkeiten) an jedem Stern haben. Jetzt hat jeder Stern zufällige Positionswackeln und es kann ein paar zusätzliche oder fehlende Punkte in jedem Bild geben. Meine Frage ist: "Was ist der beste 2D-Punkt-Matching-Algorithmus für einen solchen Datensatz?" Ich schätze sowohl für eine einfache lineare (Translation, Rotation, Skalierung) als auch nichtlineare (zB n-Grad Polynome in den Koordinaten). Im Jargon des Punkt-Matching-Feldes suche ich nach den Algorithmen, die bei einem Shootout zwischen 2D-Punkt-Matching-Programmen mit Rauschen und Störpunkten gewinnen würden. Es kann verschiedene "Gewinner" geben, abhängig davon, ob die Beschriftungsinformationen verwendet werden (die Größen) und / oder die Transformation auf lineare Werte beschränkt ist.
Ich bin mir bewusst, dass es viele Klassen von 2D-Punktabgleichalgorithmen und viele Algorithmen in jeder Klasse (wörtlich wahrscheinlich Hunderte insgesamt) gibt, aber ich weiß nicht, welche, wenn überhaupt, die "besten" oder " am meisten Standard "von Menschen im Bereich der Computer Vision. Leider haben viele Artikel zu Artikeln, die ich lesen möchte, keine Online-Versionen und ich kann nur die Zusammenfassung lesen. Bevor ich mich auf einen bestimmten Algorithmus einlasse, wäre es gut, von einigen Experten zu hören, die Spreu vom Weizen zu trennen.
Ich habe ein funktionierendes Matching-Programm, das Dreiecke verwendet, aber es versagt etwas häufig (~ 5% der Zeit), so dass die Lösung Transformation offensichtliche Verzerrungen hat, aber ohne ersichtlichen Grund. Dieses Programm wurde nicht von mir geschrieben und stammt aus einem Papier, das vor fast 20 Jahren geschrieben wurde. Ich möchte eine neue Implementierung schreiben, die am robustesten funktioniert. Ich gehe (hoffend) davon aus, dass in diesem Bereich einige Fortschritte gemacht wurden, die dies plausibel machen.
Wenn Sie an der Sternerkennung interessiert sind, sehen Sie sich den Astrometrie.net Blind Astrometrie-Solver und die es hier zu lesen . Sie verwenden vier Punkt-Quads, um Sternkonfigurationen in Flickr-Bildern des Nachthimmels zu lösen. Sehen Sie sich dieses Interview an.
Es gibt keinen einzigen "besten" Algorithmus dafür. Es gibt viele verschiedene Techniken, die in bestimmten Datensätzen und Datentypen besser funktionieren als andere.
Eine Sache, die ich empfehlen kann, ist diese Einführung in die Bildregistrierung aus den Tutorials der Insight Toolkit. ITK unterstützt VIELE Arten der Bildregistrierung (so wie es sich anhört) und ist in vielen Fällen sehr robust. Die meisten ihrer Benutzer sind im medizinischen Bereich, so dass Sie durch viele medizinische Fachsprache waten müssen, aber die Algorithmen und Code arbeiten mit jeder Art von Bild (einschließlich 1,2,3, und n-dimensionale Bilder, von verschiedenen Typen usw.).
Sie können in Betracht ziehen, Ihren Algorithmus zuerst nur auf die N hellsten Sterne anzuwenden und dann schrittweise die anderen einzuschließen, um das Ergebnis zu verfeinern und gleichzeitig den Suchbereich zu reduzieren.
RANSAC für Robustheit gegenüber Extrapunkten ist auch sehr häufig.
Ich bin mir nicht sicher, dass es funktionieren würde, aber einen Versuch wert:
Führe für jeden Stern die Fourier-Transformation des Kreis-Zeit-Strahls - mittig um ihn herum - von allen anderen Sternen durch (Anmerkung: Dies ist nicht die Standard-Fourier-Transformation, welche die Linie mal Linie ist). Der Phasenraum des Kreises mal Strahl ist ganze Zahlen mal Linie, aber da wir nur endliche Genauigkeit haben, bekommt man nur eine Matrix; Die Abmessungen der Matrix hängen von der Genauigkeit ab. Versuchen Sie nun, die Matrizen miteinander zu koppeln (z. B. mit der Norm L_2).
Vor einiger Zeit habe ich im Fernsehen gesehen, wie Forscher Wale fotografieren und die Flecken (die für jeden Wal einzigartig sind) verwenden, um jeden Wal zu identifizieren. Es benutzte die Winkel zwischen den Spots. Bei der Verwendung der Winkel spielte es keine Rolle, ob das Bild gedreht oder skaliert oder übersetzt wurde. Das klingt ähnlich wie bei deinen Dreiecken.
Ich denke, der "beste" (technischste) Weg wäre die Fourier-Transformation des Originalbildes und des neuen linear modifizierten Bildes. Durch eine einfache Filterung sollte es leicht sein, die Ausrichtung und Skalierung Ihres Bildes in Bezug auf das alte Bild herauszufinden. Es gibt eine Beschreibung der 2d-Fourier-Transformation hier .
Tags und Links algorithm computer-science pattern-matching 2d