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
