Zolver este un rezolvator de puzzle-uri scris în python. Acest proiect de sfârșit de studii a fostdezvoltat de 4 studenți EPITA. Rezolvă puzzle-uri jigsaw generate pe calculator și reale.
O scurtă prezentare video este disponibilă la https://www.youtube.com/watch?v=Oq36FtMg0-k
Un puzzle jigsaw
Reconstrucția lui Zolver
Cerințe
Acest proiect a fost dezvoltat pe distribuția Linux. Compatibilitatea cu Windows nu este absolut deloc garantată.
- 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
Pentru a evita problemele de compatibilitate, vă recomandăm să configurați un mediu virtual și apoi să folosiți comanda :
„pip install -r requirements.txt”
Utilizare
Cu GUI
Utilizați python3 main.py
Fără GUI
Utilizați python3 main_no_gui.py path/to/image
Prezentare generală a Zolver
Preprocesare
În primul rând, aplicăm un prag binar imaginii procesate. Pragul este diferit dacă procesăm un puzzle real sau unul real. Aplicăm apoi unele morfologii matematice pentru a lega marginile în cazul în care unele margini au găuri. În cele din urmă, aplicăm detecția de contur OpenCV.
Clasificarea marginilor
Acum trebuie să găsim patru margini ale fiecărei piese de puzzle. Pentru a face acest lucru, calculăm unghiul relativîntre punctele adiacente și obținem extremele locale. Odată ce marginile noastre au fost împărțite, clasificăm marginile noastre în trei categorii: margini de ramă, margini de căptușeală indent și margini de căptușeală outdent prinrecunoașterea modelelor cu curbe de unghiuri relative.
Potrivirea marginilor
Utilizăm trei moduri diferite de a potrivi marginile :
- Compararea dimensiunii marginilor pentru a găsi marginile cu lungime similară.
- Utilizarea culorii pentru a potrivi marginile. Pentru fiecare pixel de pe muchie, luăm culoarea mediană a pixelilor săi vecini și apoi comparăm distanța față de cealaltă muchie, pixel cu pixel.
- Compararea formelor folosind o distanță euclidiană de-a lungul marginilor.
Rezolvarea puzzle-ului
În primul rând rezolvăm muchia puzzle-ului deoarece, odată ce avem cadrul acestuia, fiecare piesă de puzzle poate fi potrivitafolosind cel puțin două muchii. Cu cât avem mai multe muchii pentru a verifica cât de probabilă este potrivirea piesei, cu atât este mai puțin probabil ca Zolver să facă o eroare. Zolver va încerca întotdeauna să umple spațiul gol cu cel mai mare număr de muchii deja umplute.
Autori
SCIA 2018 – EPITA
- Cyril Cetre
- Denis Castéran
- Jérémy Lugand
- Hugo Rybinski
.