Memecahkan teka-teki Jigsaw dengan Python dan OpenCV
Memecahkan teka-teki Jigsaw dengan Python dan OpenCV – Pada awal tahun 2018 saya diberi hadiah jigsaw puzzle 5000 buah Star Wars yang mengagumkan (Anda dapat menemukannya di Amazon di sini ). Menyelesaikan teka-teki membutuhkan waktu sekitar 2 bulan kesabaran dan ketekunan, tetapi sekarang saya dapat melihat karya agung saya dengan kepuasan dan kegembiraan.
Memecahkan teka-teki Jigsaw dengan Python dan OpenCV
Baca Juga : Bagaimana Jigsaw Puzzle Dibuat
puzzlehistory – Namun, saya masih ingat ketika saya harus menyelesaikan bagian tengah teka-teki, yang disusun oleh Darth Vader dan Luke Skywalker yang sangat besar (peringatan spoiler: putra Darth Vader!!). Pada dasarnya saya mendapati diri saya duduk di depan seribu keping dalam semua kemungkinan warna hitam dan biru tua, dan menemukan keping yang cocok menjadi hal yang sangat merepotkan.
Saat itulah saya memutuskan untuk memberikan Computer Vision kesempatan dan mencoba menulis sebuah program yang dapat menemukan bagian yang cocok dengan melihat bentuknya. Di bagian pertama ini saya akan menjelaskan bagaimana saya bisa mengekstrak empat sisi dari setiap bagian, untuk mencocokkan bentuk di masa depan. Di sini saya akan menunjukkan satu gambar keluaran untuk memperjelas apa yang ingin saya capai di sini:
1. Buat kumpulan data
Hal pertama yang harus dilakukan adalah mengambil gambar (dengan ponsel saya) lebih dari 200 buah dalam kondisi cahaya yang optimal. Perhatikan bahwa saya mengambil gambar bagian belakang potongan karena saya tidak membutuhkan isi teka-teki hanya bentuknya saja. Saya juga memperbaiki posisi kamera dan teka-teki sehingga memotong bagian-bagian dari seluruh gambar menjadi tugas yang sepele.
2. Segmentasi Potongan
Karena kondisi cahaya dan warna bagian tidak berubah di dalam kumpulan data, segmentasi dicapai menggunakan ambang biner sederhana. Sebelum menerapkan binerisasi, filter median diterapkan pada gambar skala abu-abu untuk menghilangkan white noise pada potongan puzzle. Gambar biner kemudian dihaluskan menggunakan filter rata-rata.
Setelah mendapatkan gambar ambang batas, saya menghapus area positif palsu yang potensial (piksel latar belakang ditandai sebagai piksel potongan puzzle) dengan menggunakan cv2.connectedComponentsfungsi OpenCV dan mengambil komponen yang terhubung dengan area maksimum (yaitu potongan puzzle itu sendiri). Akhirnya saya memotong potongan lebih lanjut menjadi gambar persegi yang memungkinkan rotasi potongan tanpa kehilangan bagiannya.
3. Temukan 4 sudut bagian
Untuk memisahkan setiap sisi potongan puzzle, kita perlu menemukan 4 sudut utama potongan puzzle dengan benar. Ini adalah bagian yang paling penting karena semua langkah berikut akan bekerja dengan sempurna jika sudutnya benar. Pada langkah pertama saya menemukan perkiraan lokasi sudut, sedangkan di bagian 4 saya akan menjelaskan cara menyempurnakan deteksi sudut untuk mendapatkan lokasi yang tepat.
3a. [Tidak berhasil] Canny, Hough Transform, dan KMeans
Dalam upaya pertama saya, saya menggunakan Hough Transform untuk menemukan garis utama potongan puzzle dan mencoba mengelompokkannya menjadi 4 himpunan bagian yang berbeda (satu untuk setiap sisi). Berikut akan saya jelaskan secara singkat langkah-langkah algoritma:
Lakukan deteksi tepi pada gambar biner dengan menerapkan cv2.Cannyfungsi. Terapkan Transformasi Hough untuk deteksi garis: cv2.HoughLines. Untuk setiap baris yang dikembalikan oleh fungsi ini, kami mendapatkan koefisiennya dalam bentuk parametrik.
Hapus garis yang tidak diinginkan dengan memperkirakan orientasi potongan: karena kita mengharapkan empat garis yang melewati keempat sudut potongan membentuk persegi panjang, saya mengelompokkan garis dengan orientasi yang sama untuk memangkas garis yang bukan milik grup ini.
Mengelompokkan garis dengan KMeans: kita dapat mengelompokkan semua garis menjadi 4 kelompok berbeda, satu untuk setiap sisi potongan, berdasarkan koefisiennya.
Hitung garis rata-rata untuk setiap cluster. Hitung persimpangan antara empat garis rata-rata untuk akhirnya mendapatkan 4 buah sudut.
Meskipun sederhana, algoritma ini tidak terbukti kuat: ini terjadi terutama ketika beberapa atau tidak ada garis yang ditemukan di satu sisi potongan puzzle, membuat hasil pengelompokan menjadi tidak dapat diprediksi. Juga, garis tidak selalu cukup mendekati garis samping yang sebenarnya, membuat persimpangannya terlalu jauh dari sudut sebenarnya.
3b. Detektor sudut Harris dan estimasi persegi panjang maksimum
Dalam upaya kedua ini, yang terbukti akurat dan kuat, saya menerapkan deteksi sudut Harris untuk menemukan kandidat sudut terbaik dan menyempurnakan estimasi ini dengan algoritme yang selalu dapat mendeteksi sudut kanan.
Saya pertama kali menerapkan cv2.Harrisfungsi, yang mengembalikan gambar floating-point baru, di mana pada setiap piksel nilai ‘sudut’ dihitung (semakin tinggi, semakin kuat
Saya kemudian menemukan maxima lokal dari gambar Harris di atas ambang batas tertentu. Setelah bagian ini saya memiliki poin-poin terpisah yang mewakili sudut-sudut kandidat dari potongan puzzle. Hal baiknya adalah bahwa untuk setiap potongan teka-teki dalam kumpulan data saya, algoritme mengembalikan sudut kandidat di mana ada sudut nyata.
3. Mengingat semua kandidat sudut, temukan himpunan empat sudut yang memaksimalkan fungsi yang memperhitungkan:
-‘persegi panjang’ bentuk yang dibentuk oleh empat titik: semakin banyak keempat sudut mendekati 90°, semakin baik
-luas bentuk: semakin besar bentuknya, semakin baik (itu karena kami berharap bahwa titik terjauh yang dapat kami temukan adalah sudut nyata itu sendiri)
Algoritma ini terbukti berhasil untuk semua gambar dataset saya. Ya!
4. Sempurnakan deteksi sudut
Sebelum memasuki fase berikutnya, saya memutar potongan puzzle untuk membuatnya horizontal (atau vertikal, tergantung sudut pandang Anda…) dan menghitung tepinya dengan menggunakan detektor tepi Canny. Saya kemudian memperbaiki posisi sudut yang terdeteksi dengan memilih jendela yang berpusat pada sudut yang terdeteksi dan menemukan titik terjauh dari garis berorientasi 45° atau 135° yang melewati bagian tengah potongan puzzle.
5. Pisahkan keempat sisinya
Sekarang setelah kita memiliki beberapa sudut puzzle yang bagus, kita perlu memisahkan perimeter potongan puzzle menjadi empat sisinya. Setiap sisi adalah kurva terhubung yang dimulai dari satu sudut dan berakhir di sudut lain. Ide yang paling sederhana bekerja cukup baik: menghitung empat garis yang melewati empat sudut dan mengklasifikasikan setiap titik perimeter berdasarkan garis terdekat ke titik tersebut.
Namun, ada kasus di mana sebuah sisi memiliki tonjolan besar dan sebagian darinya diklasifikasikan sebagai sisi yang salah, karena paling dekat dengan garis yang salah!
Untuk mengatasi ini, saya memodifikasi pendekatan sederhana menjadi pendekatan yang lebih kuat.
Terapkan ide ‘garis terdekat’ hingga ambang batas maksimum: jika suatu titik jauh dari keempat garis, itu tidak akan diklasifikasikan. Terapkan algoritme histeresis ke semua titik yang tidak terklasifikasi: untuk setiap titik yang tidak terklasifikasi, periksa apakah titik perimeter di lingkungannya telah diklasifikasikan; jika itu benar, atur ‘kelas samping’ yang sama ke intinya dan lanjutkan. Algoritma berakhir ketika semua titik telah diklasifikasikan.
Informasi terakhir yang kita butuhkan adalah orientasi masing-masing sisi: kita perlu tahu apakah sisi masuk atau keluar! (Akan buruk jika algoritma akan memberitahu kita untuk menghubungkan dua sisi yang sama-sama keluar…) Langkah ini cukup sederhana, karena kita hanya perlu memeriksa setiap sisi jika titik rata-rata, yang diperoleh dengan rata-rata semua koordinat titik milik sisi yang sama, dan barycenter dari potongan teka-teki terletak pada setengah bidang yang sama yang diidentifikasi oleh garis samping yang menghubungkan kedua sudutnya; jika kondisi ini benar, maka sisi akan masuk, jika tidak maka akan keluar.
Kesimpulan
Meskipun saya memutuskan untuk menyelesaikan teka-teki Star Wars saya menggunakan pendekatan brute force, saya sangat menikmati menerapkan algoritma Computer Vision ke potongan teka-teki. Bahkan jika tugas tampak sederhana pada pandangan pertama, banyak algoritme perlu digunakan (binarisasi, pemfilteran rata-rata, deteksi tepi, deteksi sudut, komponen terhubung, dan banyak geometri!). Silakan bagikan pendapat Anda dan kemungkinan peningkatan pekerjaan ini, dan mungkin bersama-sama kita akan dapat membangun robot pemecah teka-teki yang sepenuhnya otonom.
