Bayangkan jalur 2 dimensi terus menerus yang hanya bisa belok kiri, kanan, atau lurus, tidak dapat berpotongan sendiri, dan harus mengisi kisi persegi seperti kisi piksel dalam gambar. Kami akan menyebut jalur semacam ini ular .
Contoh yang diperbesar ini menunjukkan jalur ular di kisi 10 × 4 yang dimulai merah dan meningkat rona sekitar 2% di setiap langkah sampai berwarna ungu. (Garis hitam hanya untuk menekankan arah yang dibutuhkan.)
Tujuan
Tujuan dalam kontes popularitas ini adalah untuk menulis sebuah algoritma yang mencoba untuk membuat ulang gambar yang diberikan menggunakan ular tunggal yang warnanya terus berubah dalam jumlah kecil.
Program Anda harus mengambil gambar warna sebenarnya dari ukuran apa pun serta nilai titik apung antara 0 dan 1 termasuk toleransi .
Toleransi mendefinisikan jumlah maksimum warna ular diizinkan untuk berubah di setiap langkah berukuran piksel. Kami akan menentukan jarak antara dua warna RGB sebagai jarak Euclidean antara dua titik RGB saat disusun pada kubus warna RGB . Jarak kemudian akan dinormalisasi sehingga jarak maksimum adalah 1 dan jarak minimum adalah 0.
Kode jarak warna: (Asumsikan semua nilai input adalah bilangan bulat dalam kisaran [0, 255]
; output dinormalisasi.)
function ColorDistance(r1, g1, b1, r2, g2, b2)
d = sqrt((r2 - r1)^2 + (g2 - g1)^2 + (b2 - b1)^2)
return d / (255 * sqrt(3))
Jika hasil memanggil fungsi ini pada warna ular saat ini dan warna lain lebih besar dari toleransi yang diberikan maka ular tidak dapat berubah menjadi warna lain.
Jika Anda suka, Anda dapat menggunakan fungsi jarak warna yang berbeda. Itu harus sesuatu yang akurat dan didokumentasikan dengan baik seperti yang terdaftar di http://en.wikipedia.org/wiki/Color_difference . Anda juga harus menormalkannya agar berada di dalam [0, 1]
, yaitu jarak maksimum yang mungkin harus 1 dan minimum harus 0. Beri tahu kami dalam jawaban Anda jika Anda menggunakan metrik jarak yang berbeda.
Gambar Uji
Tentu saja Anda harus memposting gambar output Anda (dan bahkan animasi ular tumbuh jika Anda mau). Saya sarankan memposting berbagai gambar ini menggunakan toleransi rendah yang berbeda (mungkin sekitar 0,005 hingga 0,03).
(Gelombang Besar Yang Lebih Besar)
Menangkan Kriteria
Seperti yang dinyatakan, ini adalah kontes popularitas. Jawaban dengan suara tertinggi akan menang. Jawaban yang memberikan gambaran "jalur ular" yang paling akurat dan menyenangkan dari gambar input harus dipilih.
Setiap pengguna yang diketahui mengirimkan gambar-gambar jahat yang bukan ular sebenarnya akan didiskualifikasi selamanya.
Catatan
- Hanya satu jalur ular yang dapat digunakan dan itu harus sepenuhnya mengisi gambar tanpa menyentuh piksel yang sama dua kali.
- Ular dapat memulai dan mengakhiri di mana saja pada gambar.
- Ular bisa mulai dengan warna apa saja.
- Ular harus tetap berada di batas gambar. Batas-batasnya bukan siklik.
- Ular tidak dapat bergerak secara diagonal atau lebih dari satu piksel pada satu waktu.
sumber
Jawaban:
Python
Saya menghasilkan jalur dinamis untuk meminimalkan perubahan warna saat ular bergerak. Berikut ini beberapa gambar:
toleransi = 0,01
Jalur warna siklik untuk gambar di atas (biru menjadi merah, semakin hijau saat diulang):
Jalur dibuat dengan memulai dengan beberapa jalur awal, kemudian menambahkan 2x2 loop ke atasnya sampai gambar diisi. Keuntungan dari metode ini adalah bahwa loop dapat ditambahkan di mana saja di jalan, sehingga Anda tidak dapat melukis diri sendiri ke sudut dan memiliki lebih banyak kebebasan untuk membangun jalur yang Anda inginkan. Saya melacak kemungkinan loop yang berdekatan dengan jalur saat ini dan menyimpannya di tumpukan, tertimbang oleh perubahan warna sepanjang loop. Saya kemudian mematikan loop dengan perubahan warna paling sedikit dan menambahkannya ke jalan, dan ulangi sampai gambar diisi.
Saya benar-benar melacak loop sendirian ('DetourBlock' dalam kode), kemudian merekonstruksi path; ini adalah kesalahan karena ada beberapa kasus khusus untuk aneh lebar / tinggi dan saya menghabiskan beberapa jam men-debug metode rekonstruksi. Baiklah.
Metrik jalur pembuatan perlu disetel dan saya juga memiliki ide untuk pewarnaan yang lebih baik, tetapi saya pikir saya akan mendapatkan ini terlebih dahulu karena berfungsi dengan baik. Kecuali untuk yang ini, yang tampaknya lebih baik di beberapa jalur tetap:
Ini kode Python, dengan permintaan maaf atas kebiasaan pengkodean saya yang mengerikan:
Dan beberapa gambar lainnya dengan toleransi sangat rendah 0,001 :
Dan juga jalur gelombang yang bagus karena rapi:
EDIT
Pembuatan jalur tampak lebih baik ketika meminimalkan jarak warna antara warna rata-rata blok yang berdekatan, daripada meminimalkan jumlah jarak warna antara piksel yang berdekatan. Selain itu, ternyata Anda dapat membuat rata-rata warna dari dua jalur ular yang sesuai toleransi dan berakhir dengan jalur ular lain yang sesuai toleransi. Jadi saya melintasi jalan baik cara dan rata-rata, yang merapikan banyak artefak. Zombie Lena dan Scary Hands Mona terlihat jauh lebih baik. Versi terakhir:
Toleransi 0,01 :
Toleransi 0,001 :
sumber
Jawa
Program saya menghasilkan jalur ular untuk lebar & tinggi tertentu, menggunakan algoritma yang mirip dengan yang menghasilkan kurva Hilbert.
(permainan kecil: pada gambar di atas, ular mulai di sudut kiri atas. Bisakah Anda menemukan di mana ia berakhir? Semoga beruntung :)
Berikut adalah hasil untuk berbagai nilai toleransi:
Toleransi = 0,01
Toleransi = 0,05
Toleransi = 0,1
Toleransi = 0,01
Dengan blok piksel 4x4 & jalur terlihat
Menghitung jalur ular
Jalur ular disimpan dalam array integer dimensi ganda. Ular selalu memasuki kotak di sudut kiri atas. Ada 4 operasi dasar yang bisa dilakukan program saya pada jalur ular yang diberikan:
buat jalur ular baru untuk kisi dengan lebar 1 atau tinggi 1. Jalur ini hanya garis sederhana yang bergerak dari kiri ke kanan atau ke atas ke bawah, tergantung pada kasingnya.
menambah tinggi kisi, dengan menambahkan di atas jalur ular dari kiri ke kanan, lalu dengan memantulkan kisi (ular harus selalu masuk ke kisi dengan sudut kiri atas)
menambah lebar kisi, dengan menambahkan di sebelah kiri jalur ular dari atas ke bawah, kemudian dengan membalik kisi (ular harus selalu memasuki kisi dengan sudut kiri atas)
gandakan dimensi grid menggunakan algoritma "Hilbert style" (lihat deskripsi di bawah)
Dengan menggunakan serangkaian operasi atom ini, program ini dapat menghasilkan jalur ular dengan ukuran berapa pun.
Kode di bawah ini menghitung (dalam urutan terbalik) yang diperlukan untuk operasi untuk mendapatkan lebar & tinggi yang diberikan. Setelah dihitung, tindakan dieksekusi satu per satu hingga kami mendapatkan jalur ular dengan ukuran yang diharapkan.
Menggandakan ukuran jalur ular:
Algoritma yang menggandakan ukuran berfungsi sebagai berikut:
Pertimbangkan simpul ini yang ditautkan dengan KANAN dan BAWAH. Saya ingin menggandakan ukurannya.
Ada 2 cara untuk menggandakan ukurannya dan tetap keluar yang sama (kanan dan bawah):
atau
Untuk menentukan yang mana yang harus dipilih, saya perlu menangani nilai "shift" untuk setiap simpul, yang menunjukkan apakah pintu keluar digeser ke kiri / kanan atau atas / bawah. Saya mengikuti jalan seperti yang dilakukan ular, dan memperbarui nilai shift di sepanjang jalan. Nilai shift menentukan secara unik blok diperluas yang perlu saya gunakan untuk langkah berikutnya.
sumber
Python
Berikut ini adalah algoritma yang sangat sederhana untuk memulai. Itu dimulai di kiri atas gambar dan berputar searah jarum jam ke dalam, membuat warnanya sedekat mungkin dengan warna piksel berikutnya sambil tetap berada dalam toleransi.
Butuh satu atau dua menit untuk menjalankan gambar yang lebih besar, meskipun saya yakin logika spiral bisa sangat dioptimalkan.
Hasil
Mereka menarik tetapi tidak cantik. Hebatnya toleransi di atas 0,1 menghasilkan hasil yang cukup akurat.
The Great Wave dengan toleransi 0,03:
Mona Lisa pada toleransi 0,02:
Lena pada toleransi 0,03, lalu 0,01, lalu 0,005, lalu 0,003:
Barang lain-lain dengan toleransi 0,1, lalu 0,07, lalu 0,04, lalu 0,01:
sumber
Kobra
Isi gambar dengan ular seperti:
Hal ini memungkinkan penyesuaian warna yang jauh lebih cepat daripada hanya garis-garis dalam arah yang bergantian, tetapi tidak menjadi seperti yang diblokir seperti versi 3-lebar.
Bahkan pada toleransi yang sangat rendah, ujung-ujung gambar masih terlihat (meskipun kehilangan detail dalam resolusi yang lebih kecil).
0,01
0,1
0,01
0,01
0,1
0,03
0,005
sumber
C #
Ular dimulai dari piksel kiri atas dengan warna putih dan berganti dari kiri ke kanan dan kemudian kanan ke kiri bawah gambar.
Toleransi gambar hasil = 0,1
sumber