Algorithmus für Punkte mit bestimmter Eigenschaft

Wissenschaft Mathematik
#1

Ich hoffe ich schaffe es die Frage überhaupt verständlich zu formulieren…

Abstrakt:
Ich habe eine Menge von Daten A wobei jeweils zwei x1,x2 \in A eine Eigenschaft definieren können die dann viele Punkte haben können.
ich suche nun die größte menge an Daten {xi} \subset A die zusammen eine solche Eigenschaft haben bzw. die am meisten verbreitete Eigenschaft…

Konkret:
Es geht um ein mehr oder weniger großes Bild, in dem eine Menge von Punkten liegt (z.B. Binärbild 1000x1000 in dem ca. 50 Punkte liegen).
Ich suche nun einen bestimmten Teil der Punkte in diesem Bild, wobei ich weiß, dass diese dann auf einem Raster liegen (zwei Punkte mit einem passenden Abstand definieren dann ein Raster). Von dem Raster weiß ich allerdings nur die ungefähre Gitterweite und das Raster kann gedreht sein.

Ich denke das geht in die Richtung Kombinatorik und wollte mal wissen ob es für sowas interessante/schnelle Lösungsansätze gibt?(mir reicht auch ein Stichwort nach dem ich googlen kann. Über die uni-bib kann ich auf fast alle Paper online zugreifen…)

meine Idee:
Ich würde mir sukzessive ein Array bauen in dem ich das Raster und die zugehörigen Punkte speichere um später das „beste“ Raster zu finden. gehe ich dann zu einem neuen Punkt schaut man ob man auf einem der Raster liegt (Rasterwertung+1) oder man fügt ein neues Raster hinzu.
Das schein mir aber ein bisschen zu plump^^

Danke für alle Tips John

#2

Hi John,

das habe ich noch nicht ganz verstanden:

Ich hoffe ich schaffe es die Frage überhaupt verständlich zu
formulieren…

Abstrakt:
Ich habe eine Menge von Daten A wobei jeweils zwei x1,x2 \in A
eine Eigenschaft definieren können die dann viele Punkte haben
können.
ich suche nun die größte menge an Daten {xi} \subset A die
zusammen eine solche Eigenschaft haben bzw. die am meisten
verbreitete Eigenschaft…

Die Eigenschaft, über die x1 und x2 verbunden sind, ist also vorher nicht nicht bekannt? Eigentlich läuft es ja anders herum, einge Eigenschaft wird vorgegeben und zwei Elemente der Relation passen dazu oder nicht.

Gibt doch mal ein Beispiel für so eine Eigenschaft. Und wenn es wirklich unterschiedliche Eigenschaften sind, wie man auf diese kommt.

Grüße

powerblue

#3

Hi,

um mal greifbaren Kontext zu haben:

Du hast z.B. ein Förderband, auf dem Produkte laufen, und jedes Produkt hat eine Kennung, die aus Punkten in einem Raster bestehen. Aber da es eine Kennung ist, ist das Raster natürlich nicht vollständig gefüllt. Wie z.B in einem QR-Code.

Die Produkte sind zufällig auf das Band gepurzelt und werden von oben beim Durchlaufen von einer Kamera fotografiert. Jetzt soll bei der Nachbearbeitung das Bild, und evtl. später mechanisch das Produkt, so gedreht werden, dass das der Kennung zugrunde liegende Raster „aufrecht“ steht.

Ist das in etwa Dein Problem?

Gruß Lutz

#4

Im konkreten Fall geht es darum, dass wir aus einer vorherigen Houghtransformation die Mittelpunkte von gesuchten Objekten haben aber halt auch „Störpunkte“ die bei einzelner Betrachtung nicht von den Objektmittelpunkten unterschieden werden können (wir haben ein Binärbild vorliegen).
Allerdings wissen wir, dass die gesuchten Objekte und damit die Mittelpunkte auf einem Raster liegen(von dem wir die ungefähre Gitterbreite kennen).
Die gesuchten Mittelpunkte haben halt die Eigenschaft, dass sie auf einem Raster auf dem sehr vielen Punkte liegen, während die Störpunkte zwar auch auf einem Raster liegen können (zwei Punkte können ein Raster definieren mit entsprechender Gitterbriete), dieses aber aller Wahrscheinlichkeit nicht sehr viele Punkte gleichzeitig enthält, da die Störpunkte zufällig angeordnet sind.

Mein Ansatz war halt das meistbesetzte Raster mit der vorgegebenen Gitterbreite zu finden und dann die Punkte zu wählen, die auf diesem Gitter liegen.
Das Suchen des Gitter würde ich dann wieder ähnlich einer Houghtransformation realisieren, ich glaube aber, dass diese Ansatz etwas unglücklich ist…
(ich hoffe mein Aufsatz hat etwas verdeutlicht worum es geht :wink:

Gruß john