Zolver to program do rozwiązywania puzzli napisany w pythonie. Ten projekt na zakończenie studiów został opracowany przez 4 studentów EPITA. Rozwiązuje on układanki generowane komputerowo i prawdziwe.
Krótka prezentacja wideo jest dostępna na stronie https://www.youtube.com/watch?v=Oq36FtMg0-k
Układanka
Rekonstrukcja Zolvera
Wymagania
Ten projekt został opracowany na dystrybucji Linux. Kompatybilność z Windows nie jest gwarantowana.
- 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
Aby uniknąć problemów z kompatybilnością, zalecamy utworzenie wirtualnego środowiska, a następnie użycie polecenia :
„pip install -r requirements.txt”
Użycie
Z GUI
Użyj python3 main.py
Bez GUI
Użyj python3 main_no_gui.py path/to/image
Przegląd Zolvera
Przetwarzanie wstępne
Po pierwsze, stosujemy próg binarny do przetworzonego obrazu. Próg jest inny, jeśli przetwarzamy prawdziwe puzzle lub prawdziwe. Następnie stosujemy pewne morfologie matematyczne do łączenia krawędzi w przypadku, gdy niektóre krawędzie mają dziury. Na koniec, stosujemy wykrywanie konturów OpenCV.
Klasyfikacja krawędzi
Teraz musimy znaleźć cztery krawędzie każdego elementu układanki. Aby to zrobić, obliczamy względny kąt między sąsiednimi punktami i uzyskujemy ekstrema lokalne. Po podzieleniu naszych krawędzi klasyfikujemy je na trzy kategorie: krawędzie obramowania, krawędzie wypełnienia wcięcia i krawędzie wypełnienia wcięcia poprzez rozpoznawanie wzorów z krzywymi kątów względnych.
Pasowanie krawędzi
Używamy trzech różnych sposobów dopasowania krawędzi :
- Porównanie rozmiaru krawędzi w celu znalezienia krawędzi o podobnej długości.
- Użycie koloru do dopasowania krawędzi. Dla każdego piksela na krawędzi bierzemy medianę koloru sąsiednich pikseli, a następnie porównujemy odległość do drugiej krawędzi piksel do piksela.
- Porównywanie kształtów przy użyciu odległości euklidesowej wzdłuż krawędzi.
Rozwiązywanie łamigłówek
Najpierw rozwiązujemy krawędź łamigłówki, ponieważ gdy mamy już jej ramkę, każdy element łamigłówki można dopasować przy użyciu co najmniej dwóch krawędzi. Im więcej krawędzi mamy, aby sprawdzić, jak prawdopodobne jest, że kawałek pasuje, tym mniej Zolver jest prawdopodobne, aby popełnić błąd. Zolver zawsze będzie próbował wypełnić puste miejsce największą liczbą krawędzi, które zostały już wypełnione.
Autorzy
SCIA 2018 – EPITA
- Cyril Cetre
- Denis Castéran
- Jérémy Lugand
- Hugo Rybinski
.