Erkennen einer Matrix in einer Gruppe von Punkten

Question

Ich habe ein Bild, das ich mit meinem Programm ausarbeite, um eine Liste von Koordinaten zu erhalten.

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:

Beispiel desidered Ergebnis:

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

Answer 1

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.

Answer 2

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.