Kawaboongawa / Zolver

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

.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.