Erkennen einer Matrix in einer Gruppe von Punkten

Ich habe ein Bild, das ich mit meinem Programm ausarbeite, um eine Liste von Koordinaten zu erhalten.Erkennen einer Matrix in einer Gruppe von Punkten

Im Bild dargestellt gibt es eine Matrix. In einem idealen Test würde ich nur die sechzehn zentralen Punkte jedes Quadrats der Matrix bekommen. Aber in tatsächlichen Tests nehme ich ziemlich viele Rauschpunkte.

Ich möchte einen Algorithmus aus der Liste der Koordinaten extrapolieren, die Gruppe von 16 Koordinaten, die am besten eine Matrix darstellen.

Die Matrix kann ein beliebiges Seitenverhältnis (zwischen einem Bereich) haben und etwas gedreht werden. Aber ist immer eine 4x4-Matrix. Die Matrix ist nicht immer im Bild vorhanden, aber ist kein Problem, ich brauche nur die beste Anpassung. Natürlich ist die gegründet Punkt sind immer mehr als 16 (oder i überspringen)

Beispiel gegründet Punkte:

enter image description here

Beispiel desidered Ergebnis:

enter image description here

Wenn jemand kann mir vorschlagen, eine bevorzugte Möglichkeit, dies zu tun wäre großartig.

Ich denke über den euklidischen Abstand zwischen Punkten nach.

For each point in the list: 
    1. calculate the euclidean distance (D) with the others 
    2. filter that points that D * 3 > image.widht (or height) 
    3. see if it have at least 2 point at the same (more or less) distance, 
     if not skip 
    4. if yes put the point in a list and for each same-distance founded points: go to 2nd step.

Am Ende, wenn ich 16 Punkte in der Liste habe, könnte dies eine Matrix sein.

Jeder bessere Vorschlag?

Danke

Quelle

2013-05-24 Univers3

Sie wollen eine Form mit einem regelmäßigen Gitter? Peridocity auf X-Linie oder Y-Linie oder beides? Wie steht es mit der Winkel-Symmetrie? Sie wollen auch Diamantformen? –

Ein Diamant Formen ist nie rappraesentiert. Ich denke, die maximale Drehung (beginnend mit einem perfekten Quadrat) kann 45 ° (und -45 °) betragen. Ja, die Form hat ein periodisches Gitter (X und Y), aber wenn ich die Punkte aus dem Bild extrapoliere, unterscheiden sich die extrapolierten Punkte ein wenig. – Univers3

Wäre ein Quadrat, das um 45 ° gedreht wurde, nicht eine Rautenform? – mbeckish

Dies ist der Algorithmus, der in dem Sinne:

for each pair of points (p1, p2): 
    let d be the distance vector (x and y) between them 
    if d.x > (image.width-p1.x)/3 or d.y > (image.height-p1.y)/3: 
     continue 
    let d_t be d turned 90 degrees (d.y, -d.x) 
    for i from 0 to 3: 
     for j from 0 to 3: 
      if there is no point at p1 + i*d + j*d_t: 
       continue outer loop 
    if you get here, you have a 4*4 grid

die Laufzeit zu halbieren (im Durchschnitt), könnten Sie einfach die p2 wir überlegen, die rechts von p1 sind.

Quelle

2013-05-24 15:05:49

Mit einem kleinen prozentualen Schwellwert für die Anfangsdistanz kann der Algorithmus fehlertolerant sein, indem er die Matrixpunkte findet, indem er die IF ändert mit: 'wenn die Entfernung des nächsten Punktes bei p1 + i * d + j * d_t unterscheiden sich mehr als die 4% mit d' – Univers3

Ja, wenn die Daten sind verrauscht oder Float-Wert tun, dass. Auch mein Algo nimmt an, dass die Matrix quadratisch sein wird, also sei dir dessen bewusst. –

Je nachdem, wie viel Rechenleistung die Sie verwenden möchten, und bedeutet sehr wenig, um eine „kleine Rotation“ unter der Annahme, könnten Sie folgendes versuchen: 1) nehmen nur die X-Koordinaten der Punkte, Suchen Sie nach Clustern der Größe 4.

2) Suchen Sie für jeden Cluster nach jedem Cluster auf der linken Seite mit dem Abstand d, wenn es zwei weitere mit den Abständen 2 * d und 3 * d gibt.

3) Falls ja, vergleichen Sie die y-Koordinaten für jeden dieser Cluster, um zu sehen, ob sie ungefähr gleich sind.

Abhängig von den Daten können Sie eine bessere Leistung erzielen, indem Sie Schritt drei vor Schritt zwei ausführen und damit die von Ihnen berücksichtigten Optionen löschen.

Quelle

2013-05-24 14:47:45

Erkennen einer Matrix in einer Gruppe von Punkten

Antwort

Verwandte Themen