Kawaboongawa / Zolver

Zolver ist ein in Python geschriebener Puzzle-Löser. Dieses Projekt zum Abschluss des Studiums wurde von 4 EPITA-Studenten entwickelt. Es löst computergenerierte und reale Puzzles.

Eine kurze Videopräsentation ist verfügbar unter https://www.youtube.com/watch?v=Oq36FtMg0-k

Ein Puzzle

Zolver-Rekonstruktion

Anforderungen

Dieses Projekt wurde unter Linux entwickelt. Windows-Kompatibilität ist nicht garantiert.

  • numpy==1.15.0
  • scipy==1.0.0
  • opencv_python==3.3.0.10
  • scikit_image==0.13.1
  • matplotlib==2.1.0
  • Pillow
  • PyQt5>=5.0
  • scikit_learn>=0.18.1

Um Kompatibilitätsprobleme zu vermeiden, empfehlen wir, eine virtuelle Umgebung einzurichten und dann den Befehl :

„pip install -r requirements.txt“

Verwendung

Mit GUI

Benutzung python3 main.py

Ohne GUI

Benutzung python3 main_no_gui.py path/to/image

Zolver Übersicht

Vorverarbeitung

Zunächst wird ein binärer Schwellenwert auf das verarbeitete Bild angewendet. Der Schwellenwert ist unterschiedlich, je nachdem, ob es sich um ein echtes Puzzle oder um ein echtes Bild handelt. Dann wenden wir einige mathematische Morphologien an, um die Kanten zu verbinden, falls einige Kanten Löcher haben. Schließlich wenden wir die OpenCV-Konturerkennung an.

Kantenklassifizierung

Wir müssen nun vier Kanten jedes Puzzleteils finden. Dazu berechnen wir den relativen Winkel zwischen benachbarten Punkten und erhalten lokale Extrema. Sobald unsere Kanten aufgeteilt sind, klassifizieren wir unsere Kanten in drei Kategorien: Rahmenkanten, Einzugspolsterungskanten und Auszugspolsterungskanten, indem wir Muster mit relativen Winkelkurven erkennen.

Kantenabgleich

Wir verwenden drei verschiedene Methoden, um Kanten abzugleichen:

  • Vergleichen Sie die Kantengröße, um Kanten mit ähnlicher Länge zu finden.
  • Verwenden Sie Farbe, um Kanten abzugleichen. Für jedes Pixel auf der Kante nehmen wir die mittlere Farbe der benachbarten Pixel und vergleichen dann den Abstand zur anderen Kante von Pixel zu Pixel.
  • Vergleichen von Formen unter Verwendung eines euklidischen Abstands entlang der Kanten.

Puzzle lösen

Wir lösen zuerst die Puzzlekante, denn sobald wir ihren Rahmen haben, kann jedes Puzzleteil mit mindestens zwei Kanten zusammengefügt werden. Je mehr Kanten wir haben, um zu prüfen, wie wahrscheinlich es ist, dass das Teil passt, desto geringer ist die Wahrscheinlichkeit, dass Zolver einen Fehler macht. Zolver wird immer versuchen, den leeren Raum mit der höchsten Anzahl von bereits gefüllten Kanten zu füllen.

Autoren

SCIA 2018 – EPITA

  • Cyril Cetre
  • Denis Castéran
  • Jérémy Lugand
  • Hugo Rybinski

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.