Woran erkennt man hexagonale Fliesen im Brettspiel?

16

Ich möchte die Grenzen einer sechseckigen Kachelung auf einem Foto erkennen, wie im folgenden Bild:

Bildbeschreibung hier eingeben

Es scheint mir, dass ein Standardansatz bei einem quadratischen Raster darin besteht, zuerst Ecken (z. B. canny) zu erkennen und dann die längsten Linien über eine Hough-Transformation oder ähnliches zu extrahieren .

Dies ist bei Hex-Kacheln keine optimale Lösung, da die Länge der äußeren Linien kürzer ist und es schwierig ist, sie von anderen Linien zu trennen.

Gibt es einen Algorithmus, um dieses Problem zu beheben? Es wäre besonders schön, eine Lösung in opencv zu haben, aber ich interessiere mich auch für allgemeine Ideen.

aktualisieren:

Mit Python und OpenCV konnte ich dieses Ergebnis erhalten: Konturen

Hier ist mein Code:

import cv2
import numpy as np

imgOrig = "test1";
img = cv2.imread(imgOrig+".jpg");  
lap = cv2.Laplacian(img, cv2.IPL_DEPTH_32F, ksize = 3)  
imgray = cv2.cvtColor(lap,cv2.COLOR_BGR2GRAY)  
ret,thresh = cv2.threshold(imgray,127,255,0)
contours, hierarchy = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)
size = img.shape
m = np.zeros(size, dtype=np.uint8)
for i, cnt in enumerate(contours):
    if cv2.contourArea(cnt) >= 1:
        color = (255,255,255)
        cv2.drawContours(m, cnt, -1, color, -1)
cv2.imwrite(str(imgOrig)+"contours.jpg", m);

Der Laplace-Wert des Bildes sieht folgendermaßen aus: Laplace

Ich werde versuchen, die Parameter dieses Ansatzes zu optimieren und dann die Grenzen der vier Abschnitte zu interpolieren.

Snalx
quelle
5
Signalverarbeitung trifft auf Euro-Gaming; Meine Geek-Sinne kribbeln!
Nispio
1
Wenn Sie immer die gleiche Kartengröße verwenden und immer ungefähr die gleiche Ansicht der Karte im Bild haben, können Sie das Problem möglicherweise so einfach lösen, wie Sie den Umriss der Karte erkennen, um die Größe und Ausrichtung zu bestimmen. Die Platzierung und Größe der Kacheln ist in Bezug auf die Kanten der Platte konstant. Wenn Sie also wissen, wo sich all Ihre Kanten befinden, sollten Sie in der Lage sein, die Positionen der inneren Kacheln genau zu bestimmen.
Nispio
Vielen Dank für Ihren Vorschlag, @nispio. Die Größe der Platine ist die ganze Zeit gleich, während sich die Ansicht der Platine erheblich ändern kann. Die Farbe des Hintergrunds unterscheidet sich auch in anderen Bildern, was zu einem viel geringeren Kontrast führt. Wenn der Hintergrund beispielsweise beige ist, ist die Position des Umrisses schwer zu bestimmen.
Snalx
1
Wenn Sie keine anderen Antworten erhalten, ist es meiner Meinung nach eine gute Idee, Ihre Änderungen als Antwort auf Ihre eigene Frage zu veröffentlichen. Ich bin nicht sicher, wie das mit dem Kopfgeld interagiert!
lmjohns3
1
@snalx: Wenn du deine Ergebnisse als Antwort postest, werde ich dir das Kopfgeld gewähren. Muss allerdings in den nächsten 12 Stunden erledigt sein.
Januar

Antworten:

6

1. Ansatz:

Verwenden Sie die Haartraining-Methoden von opencv gemäß diesem Tutorial: http://note.sonots.com/SciSoftware/haartraining.html - dies sollte die besten Ergebnisse bringen, aber ich habe bisher noch nicht selbst mit Haartraining gearbeitet ...

2. Ansatz:

Ich würde vorschlagen, Methoden der "markerlosen Verfolgung" der einzelnen Kacheln der Platine zu verwenden. Sie können dies auch mit OpenCV implementieren.

Vorbereitung

  1. Zu diesem Zweck benötigen Sie einige Fotos von jedem Fliesentyp. Nehmen Sie ein Bild aller Kacheltypen auf (jedes als ein Bild), mit einem homogenen Hintergrund von oben nach unten in der Mitte des Bildes.

  2. Verwenden Sie dann einen Feature-Detektor (OpenCV hat dafür mehrere Algorithmen, aber SIFT / SURF sind nicht freie Algorithmen; ich würde vorschlagen, "FAST" zu verwenden), um markante Punkte in den Bildern zu finden.

  3. Verwenden Sie einen Feature-Deskriptor, um das im Bild gefundene Feature zu beschreiben (verwenden Sie z. B. "BRIEF").

Erkennung

Jetzt können Sie die Kacheln in einem Bild erkennen, indem Sie auf dieses Bild dieselben Feature-Detektor- / Deskriptor-Algorithmen anwenden. Wenn Sie die Features / Deskriptoren erworben haben, können Sie den FlannBasedMatcher anwenden, um die Kacheln zu finden.

Hier ist ein Codebeispiel / Tutorial von OpenCV: http://docs.opencv.org/doc/tutorials/features2d/feature_homography/feature_homography.html#feature-homography

Anmerkungen

Die Matcher-Methode gibt Ihnen nur eine Übereinstimmung und kann zu Problemen führen, wenn mehr als ein Plättchen dieses Typs auf dem Brett gefunden wird. Sie können dieses Problem umgehen, indem Sie nur einige Teile des Eingabebilds ausblenden. Ich schlage vor, dies unter Verwendung der Pixelkoordinaten der erkannten Merkmale zu tun. Wenn Sie zuerst den Umriss und die Größe der Kacheln erkennen, können Sie die Position und Größe der Kacheln auf dem Bild grob einschätzen. Filtern Sie Ihre erkannte Feature-Liste (z. B. nur Features innerhalb des x-Pixel-Radius vom erwarteten Mittelpunkt der Kachel), bevor Sie sie abgleichen, und verwenden Sie dann die stärkste Übereinstimmung. Als Ergebnis erhalten Sie die genaue Position der Kachel auf dem Bild (einschließlich ihrer Ausrichtung). Wenn es zu kompliziert ist, den Kartenumriss zu erkennen, können Sie den Benutzer auf die Eckkacheln "zeigen" lassen, um den Umriss manuell zu markieren ...

Alternativer Ansatz

Mit dieser Methode können Sie auch nur eine der Kacheln anhand ihres Umrisses finden. Zeichnen Sie ein "schematisches" Graustufenbild einer Kachel (Sechseck) ohne ein Bild darauf. Beachten Sie, dass die Bereiche "Dunkel" und "Hell" in diesem Bild im Schema korrekt sein müssen und nicht nur einige "Linien". Sie müssen wahrscheinlich damit experimentieren. Sie können versuchen, mehrere Fotos verschiedener Kacheln zu mitteln, um ein "durchschnittliches" Bild einer Kachel zu erhalten. Stellen Sie sicher, dass sich die Ecken an derselben Position befinden (Bilder entsprechend verschieben / skalieren) und schärfen Sie das Bild, wenn Sie fertig sind (klare Ecken / Kanten sollten sichtbar sein), und passen Sie den Kontrast bei Bedarf ein wenig an.

SDwarfs
quelle
Danke für deinen Vorschlag @StefanK. Ich bin ein wenig besorgt, ob der erste und zweite Ansatz noch funktionieren, wenn Spielsteine ​​(Häuser) auf den Fliesen liegen. Ihr alternativer Ansatz sieht vielversprechend aus, das werde ich versuchen (vielleicht nach ein bisschen Vorverarbeitung).
Snalx
Die Erkennung der äußeren Linien scheint in den meisten Fällen möglich zu sein. Ich habe das kürzlich mit Hough transfom an Bildern versucht, die dem Endergebnis meiner Frage ähneln. Ich werde meine Frage aktualisieren, wenn ich eine stabile Lösung gefunden habe.
Snalx
Häuser und andere Spielsteine ​​auf den Plättchen sollten kein Problem sein. Dies führt dazu, dass einige "Merkmale" abgedeckt werden, von denen einige jedoch weiterhin erkannt werden. Mindestens 4 müssen nachweisbar sein. Sie können die Demos zur Funktionserkennung von opencv ausprobieren und sehen, wie viele Funktionen auf jeder Kachel erkannt werden ...
SDwarfs 30.08.13
3

Ich werde meinen aktuellen Ansatz beschreiben, der eine Kombination aus Spielregeln, Bildverarbeitung und Feature-Erkennung darstellt.

Relevante Spielregeln

Realisierung

Zuerst benutze ich Hough-Transformation, um die Position des Spielbretts zu extrahieren. Das Quellbild ähnelt dem fraglichen Endbild, aber mit dickeren Linien und ich habe die kleineren Grenzen gefiltert. Ich benutze nur die Erkennung sehr langer Linien (Größenordnung: ca. 60 Prozent der Bildbreite / -höhe) und sehr kleiner Schwellenwerte für die Linienanpassung. Ich schaue mir auch nur die äußeren 40 Prozent des Bildes an und nehme den Median der erkannten Linien oben, unten, links und rechts. Das Ergebnis ist im Bild unten dargestellt: Hough verwandeln

Ich brauche nur eine grobe Annäherung, also ist das in Ordnung. Von nun an untersuche ich nur das Bild innerhalb der Houghlines, plus etwas zusätzlichen Platz aufgrund der Unsicherheit der Hough-Transformation.

Dann benutze ich die Feature-Erkennung, wie von Stefan K. in seiner Antwort vorgeschlagen, um die Features im Bild zu erkennen, die von den Spielern nicht erfasst werden können, dh Burgen, Ortsplättchen und Berge. Ich benutze dazu den ORB-Algorithmus in opencv-python und den BruteForce-Hamming-Matcher (FlannBased Matcher konnte ich noch nicht zum Laufen bringen). ORB ist skalierungs- und drehungsinvariant. Um das mehrfache Auftreten gleicher Merkmale (zB Burgen) zu erkennen, habe ich das Bild in Teile aufgeteilt, die sich überlappen. Dies funktioniert einwandfrei, solange die Bildauflösung groß genug ist und das Bild direkt von oben aufgenommen wird (es sind noch einige Tests erforderlich). Es ist auch etwas langsam. Das Erkennen von Standortkacheln (Tavernen) ist in der folgenden Abbildung als Beispiel dargestellt Erkennung von Burgmerkmalen

Im Moment versuche ich, die Homographie-Transformation zu finden, um die genaue Position und Orientierung der erkannten Merkmale zu ermitteln.

Ich hoffe, aus diesen Informationen (Lage von Bergen, Burg, Ortsplättchen und in den meisten Fällen Wasser) das Raster rekonstruieren zu können. Strömungsexperimente sehen vielversprechend aus, obwohl eine Menge Feinabstimmung und eine ordnungsgemäße Vorbereitung von Merkmalbildern durchgeführt werden müssen.

Snalx
quelle
Ich habe mit Catan etwas Ähnliches gemacht, aber anstelle der Hoomografie verwende ich den mittleren Farbwert für eine bestimmte Fliese. Identifizieren Sie die Kachel als 6-seitige Polykontur mit Vorverarbeitung, um die Kanten zu isolieren. Konvertieren Sie dann diese ROI in eine Maske und wenden Sie die Maske mit bitweise_und über dem Quellbild an. Sie können dann eine mittlere Farbe erhalten, die ausreicht, um die meisten Kacheln zu identifizieren. Anschließend können Sie einen zusätzlichen Mustervergleich durchführen. Ich habe gerade damit begonnen: youtube.com/watch?v=0ezfyWkio6c
Rex Hardin