Penghargaan untuk Hobi Calvin karena menyenggol gagasan tantanganku ke arah yang benar.
Pertimbangkan satu set poin di pesawat, yang akan kita sebut situs , dan kaitkan warna dengan masing-masing situs. Sekarang Anda dapat mengecat seluruh bidang dengan mewarnai setiap titik dengan warna situs terdekat. Ini disebut peta Voronoi (atau diagram Voronoi ). Pada prinsipnya, peta Voronoi dapat didefinisikan untuk metrik jarak apa pun, tetapi kami hanya akan menggunakan jarak Euclidean yang biasa r = √(x² + y²)
. ( Catatan: Anda tidak perlu harus tahu cara menghitung dan membuat salah satunya untuk bersaing dalam tantangan ini.)
Berikut ini adalah contoh dengan 100 situs:
Jika Anda melihat sel mana pun, maka semua titik di dalam sel itu lebih dekat ke situs yang sesuai daripada ke situs lain.
Tugas Anda adalah memperkirakan gambar yang diberikan dengan peta Voronoi. Anda diberi gambar dalam format raster grafis nyaman, serta integer N . Anda kemudian harus menghasilkan hingga N situs, dan warna untuk setiap situs, sehingga peta Voronoi berdasarkan situs-situs ini menyerupai gambar input sedekat mungkin.
Anda dapat menggunakan Stack Snippet di bagian bawah tantangan ini untuk membuat peta Voronoi dari output Anda, atau Anda dapat merendernya sendiri jika Anda mau.
Anda dapat menggunakan fungsi bawaan atau pihak ketiga untuk menghitung peta Voronoi dari sekumpulan situs (jika perlu).
Ini adalah kontes popularitas, jadi jawabannya dengan suara terbanyak menang. Pemilih didorong untuk menilai jawaban oleh
- seberapa baik gambar asli dan warnanya diperkirakan.
- seberapa baik algoritma bekerja pada berbagai jenis gambar.
- seberapa baik algoritma ini bekerja untuk N kecil .
- apakah algoritma secara adaptif mengelompokkan titik-titik di wilayah gambar yang memerlukan lebih detail.
Gambar Uji
Berikut adalah beberapa gambar untuk menguji algoritme Anda (beberapa tersangka biasa kami, beberapa yang baru). Klik gambar untuk versi yang lebih besar.
Pantai di baris pertama ditarik oleh Olivia Bell , dan termasuk dengan izinnya.
Jika Anda menginginkan tantangan ekstra, cobalah Yoshi dengan latar belakang putih dan luruskan perutnya.
Anda dapat menemukan semua gambar uji ini di galeri imgur ini di mana Anda dapat mengunduh semuanya sebagai file zip. Album ini juga berisi diagram Voronoi acak sebagai tes lain. Untuk referensi, berikut adalah data yang menghasilkannya .
Harap sertakan diagram contoh untuk berbagai gambar dan N yang berbeda , misalnya 100, 300, 1000, 3000 (serta pastebins ke beberapa spesifikasi sel yang sesuai). Anda dapat menggunakan atau menghilangkan tepi hitam di antara sel yang Anda inginkan (ini mungkin terlihat lebih baik pada beberapa gambar daripada yang lain). Jangan sertakan situsnya (kecuali dalam contoh terpisah, mungkin jika Anda ingin menjelaskan cara kerja penempatan situs Anda, tentu saja).
Jika Anda ingin menunjukkan sejumlah besar hasil, Anda dapat membuat galeri di imgur.com , agar ukuran jawaban tetap masuk akal. Atau, letakkan gambar kecil di pos Anda dan buat tautan ke gambar yang lebih besar, seperti yang saya lakukan pada jawaban referensi saya . Anda bisa mendapatkan thumbnail kecil dengan menambahkan s
nama file di tautan imgur.com (mis. I3XrT.png
-> I3XrTs.png
). Juga, jangan ragu untuk menggunakan gambar uji lain, jika Anda menemukan sesuatu yang bagus.
Renderer
Tempelkan output Anda ke dalam Stack Snippet berikut untuk membuat hasil Anda. Format daftar yang tepat tidak relevan, selama setiap sel ditentukan oleh 5 angka floating point dalam urutan x y r g b
, di mana x
dan y
merupakan koordinat situs sel, dan r g b
merupakan saluran warna merah, hijau dan biru dalam kisaran 0 ≤ r, g, b ≤ 1
.
Cuplikan menyediakan opsi untuk menentukan lebar garis tepi sel, dan apakah situs sel harus ditampilkan atau tidak (yang terakhir sebagian besar untuk tujuan debugging). Tetapi perhatikan bahwa output hanya dirender ulang ketika spesifikasi sel berubah - jadi jika Anda memodifikasi beberapa opsi lain, tambahkan spasi ke sel atau sesuatu.
Penghargaan besar kepada Raymond Hill untuk menulis perpustakaan JS Voronoi yang sangat bagus ini .
Tantangan Terkait
sumber
Jawaban:
Python + scipy + scikit-image , pengambilan sampel disk Poisson tertimbang
Solusi saya agak rumit. Saya melakukan beberapa preprocessing pada gambar untuk menghilangkan noise dan mendapatkan pemetaan seberapa 'menarik' setiap titik (menggunakan kombinasi entropi lokal dan deteksi tepi):
Kemudian saya memilih titik pengambilan sampel menggunakan pengambilan sampel cakram Poisson dengan twist: jarak lingkaran ditentukan oleh berat yang kami tentukan sebelumnya.
Kemudian setelah saya memiliki titik pengambilan sampel, saya membagi gambar dalam segmen voronoi dan menetapkan rata-rata L * a * b * dari nilai warna di dalam setiap segmen untuk setiap segmen.
Saya memiliki banyak heuristik, dan saya juga harus melakukan sedikit matematika untuk memastikan jumlah titik sampel dekat
N
. Saya mendapatkanN
persis dengan overshooting sedikit , dan kemudian menjatuhkan beberapa poin dengan heuristik.Dalam hal runtime, filter ini tidak murah , tetapi tidak ada gambar di bawah ini yang membutuhkan waktu lebih dari 5 detik.
Tanpa basa-basi:
Gambar-gambar
Masing
N
- masing adalah 100, 300, 1000 dan 3000:sumber
C ++
Pendekatan saya cukup lambat, tapi saya sangat senang dengan kualitas hasil yang diberikannya, terutama yang berkaitan dengan menjaga tepi. Misalnya, inilah Yoshi dan Kotak Cornell dengan masing-masing hanya 1000 situs:
Ada dua bagian utama yang membuatnya dicentang. Yang pertama, yang diwujudkan dalam
evaluate()
fungsi mengambil satu set lokasi kandidat situs, menetapkan warna optimal pada mereka dan mengembalikan skor untuk PSNR dari tessellation Voronoi yang diberikan versus gambar target. Warna untuk setiap situs ditentukan oleh rata-rata piksel gambar target yang dicakup oleh sel di sekitar situs. Saya menggunakan algoritma Welford untuk membantu menghitung baik warna terbaik untuk setiap sel dan hasil PSNR menggunakan hanya satu melewati gambar dengan memanfaatkan hubungan antara varians, MSE, dan PSNR. Ini mengurangi masalah menjadi salah satu dari menemukan set lokasi situs terbaik tanpa memperhatikan warna.Bagian kedua, yang terkandung dalam
main()
, mencoba menemukan set ini. Dimulai dengan memilih satu set poin secara acak. Kemudian, di setiap langkah itu menghapus satu titik (round-robin) dan menguji satu set poin kandidat acak untuk menggantinya. Yang menghasilkan PSNR tertinggi dari kelompok itu diterima dan disimpan. Secara efektif, ini menyebabkan situs melompat ke lokasi baru dan umumnya meningkatkan gambar sedikit demi sedikit. Perhatikan bahwa algoritma ini sengaja tidak mempertahankan lokasi asli sebagai kandidat. Terkadang ini berarti lompatan menurunkan kualitas gambar keseluruhan. Membiarkan ini terjadi membantu menghindari terjebak dalam maksima lokal. Ini juga memberikan kriteria berhenti; program berakhir setelah melakukan sejumlah langkah tanpa meningkatkan set situs terbaik yang ditemukan sejauh ini.Perhatikan bahwa implementasi ini cukup mendasar dan dapat dengan mudah menghabiskan waktu berjam-jam untuk CPU-core, terutama ketika jumlah situs bertambah. Ini mengkompilasi ulang peta Voronoi lengkap untuk setiap kandidat dan brute force menguji jarak ke semua situs untuk setiap piksel. Karena setiap operasi melibatkan penghapusan satu titik pada satu waktu dan menambahkan yang lain, perubahan sebenarnya pada gambar pada setiap langkah akan menjadi cukup lokal. Ada algoritma untuk secara efisien memperbarui diagram Voronoi dan saya percaya mereka akan memberikan algoritma ini percepatan yang luar biasa. Untuk kontes ini, bagaimanapun, saya telah memilih untuk menjaga hal-hal sederhana dan kasar.
Kode
Lari
Program ini mandiri dan tidak memiliki dependensi eksternal di luar perpustakaan standar, tetapi memang membutuhkan gambar dalam format PPM biner . Saya menggunakan ImageMagick untuk mengonversi gambar ke PPM, meskipun GIMP dan beberapa program lain juga dapat melakukannya.
Untuk mengkompilasinya, simpan program sebagai
voronoi.cpp
dan kemudian jalankan:Saya berharap ini mungkin akan bekerja pada Windows dengan versi terbaru dari Visual Studio, meskipun saya belum mencoba ini. Anda ingin memastikan bahwa Anda sedang mengompilasi dengan C ++ 11 atau lebih baik dan OpenMP diaktifkan jika Anda melakukannya. OpenMP tidak sepenuhnya diperlukan, tetapi banyak membantu dalam membuat waktu pelaksanaan lebih dapat ditoleransi.
Untuk menjalankannya, lakukan sesuatu seperti:
File yang lebih baru akan diperbarui dengan data situs saat berjalan. Baris pertama akan memiliki lebar dan tinggi gambar, diikuti oleh garis nilai x, y, r, g, b yang cocok untuk menyalin dan menempel ke penyaji Javascript dalam deskripsi masalah.
Tiga konstanta di bagian atas program memungkinkan Anda menyetelnya untuk kecepatan versus kualitas. The
decimation
Faktor coarsens gambar target ketika mengevaluasi satu set situs untuk warna dan PSNR. Semakin tinggi, semakin cepat program akan berjalan. Mengaturnya ke 1 menggunakan gambar resolusi penuh. Thecandidates
kontrol konstan berapa banyak kandidat untuk menguji pada setiap langkah. Lebih tinggi memberikan kesempatan lebih baik untuk menemukan tempat yang baik untuk melompat tetapi membuat program lebih lambat. Terakhir,termination
adalah berapa banyak langkah yang dapat dilakukan program tanpa meningkatkan outputnya sebelum berhenti. Meningkatkannya mungkin memberikan hasil yang lebih baik tetapi membuatnya sedikit lebih lama.Gambar-gambar
N
= 100, 300, 1000, dan 3000:sumber
IDL, penyempurnaan adaptif
Metode ini terinspirasi oleh Penyempurnaan Mesh Adaptif dari simulasi astronomi, dan juga permukaan Pembagian . Ini adalah jenis tugas yang dibanggakan IDL sendiri, yang dapat Anda ketahui dari sejumlah besar fungsi bawaan yang dapat saya gunakan. : D
Saya sudah menampilkan beberapa perantara untuk gambar uji yoshi latar belakang hitam, dengan
n = 1000
.Pertama, kami melakukan skala abu-abu pencahayaan pada gambar (menggunakan
ct_luminance
), dan menerapkan filter Prewitt (prewitt
, lihat wikipedia ) untuk deteksi tepi yang baik:Kemudian muncul pekerjaan kasar yang sebenarnya: kita membagi gambar menjadi 4, dan mengukur varians di setiap kuadran dalam gambar yang difilter. Varians kami tertimbang oleh ukuran subdivisi (yang pada langkah pertama ini sama), sehingga daerah "edgy" dengan varians tinggi tidak dapat dibagi lagi menjadi lebih kecil dan lebih kecil dan lebih kecil. Kemudian, kami menggunakan varian tertimbang untuk menargetkan subdivisi dengan lebih detail, dan secara iteratif membagi masing-masing bagian yang kaya detail menjadi 4 tambahan, hingga kami mencapai jumlah target situs kami (setiap subdivisi berisi tepat satu situs). Karena kami menambahkan 3 situs setiap kali kami melakukan iterate, kami berakhir dengan
n - 2 <= N <= n
situs.Saya membuat .webm dari proses pembagian untuk gambar ini, yang tidak dapat saya embed, tapi ini ada di sini ; warna di setiap subbagian ditentukan oleh varian tertimbang. (Saya membuat jenis video yang sama untuk yoshi latar belakang putih, untuk perbandingan, dengan tabel warna terbalik sehingga mengarah ke putih, bukan hitam; itu di sini .) Produk akhir dari subdivisi terlihat seperti ini:
Setelah kami memiliki daftar subdivisi kami, kami pergi melalui masing-masing subdivisi. Lokasi situs terakhir adalah posisi minimum gambar Prewitt, yaitu, piksel "paling tidak edgy", dan warna bagian adalah warna piksel itu; inilah gambar asli, dengan situs ditandai:
Kemudian, kami menggunakan built-in
triangulate
untuk menghitung triangulasi Delaunay situs, dan built-invoronoi
untuk menentukan simpul dari setiap poligon Voronoi, sebelum menggambar setiap poligon ke buffer gambar dalam warna masing-masing. Akhirnya, kami menyimpan snapshot dari buffer gambar.Kode:
Sebut ini via
voro_map, n, image, output_filename
. Saya juga menyertakanwrapper
prosedur, yang melewati setiap gambar uji dan dijalankan dengan 100, 500, dan 1000 situs.Output dikumpulkan di sini , dan berikut adalah beberapa thumbnail:
n = 100
n = 500
n = 1000
sumber
Python 3 + PIL + SciPy, Fuzzy k-means
Algoritma
Gagasan intinya adalah bahwa k-means mengelompokkan secara alami partisi gambar ke dalam sel Voronoi, karena titik-titik terkait dengan centroid terdekat. Namun, kita perlu menambahkan warna sebagai kendala.
Pertama-tama kita mengonversi setiap piksel ke ruang warna Lab , untuk manipulasi warna yang lebih baik.
Lalu kami melakukan semacam "deteksi tepi orang miskin". Untuk setiap piksel, kita melihat tetangganya yang ortogonal dan diagonal, dan menghitung perbedaan rata-rata kuadrat dalam warna. Kami kemudian mengurutkan semua piksel berdasarkan perbedaan ini, dengan piksel yang paling mirip dengan tetangga mereka di bagian depan daftar, dan piksel yang paling berbeda dengan tetangga mereka di belakang (yaitu, lebih cenderung menjadi titik tepi). Berikut adalah contoh untuk planet ini, di mana semakin terang pikselnya, semakin berbeda dari tetangganya:
(Ada pola kisi-kisi yang jelas pada output yang diberikan di atas. Menurut @randomra, ini mungkin disebabkan oleh enkode JPG yang hilang, atau imgur mengompresi gambar.)
Selanjutnya, kami menggunakan pemesanan piksel ini untuk mengambil sampel sejumlah besar titik yang akan dikelompokkan. Kami menggunakan distribusi eksponensial, memberikan prioritas pada poin yang lebih mirip tepi dan "menarik".
Untuk pengelompokan, kami pertama-tama memilih
N
centroid, yang dipilih secara acak menggunakan distribusi eksponensial yang sama seperti di atas. Iterasi awal dilakukan, dan untuk masing-masing cluster yang dihasilkan, kami menetapkan warna rata-rata dan ambang batas varian warna. Kemudian untuk sejumlah iterasi, kami:(Klik untuk ukuran penuh)
Akhirnya, kami mencicipi sejumlah besar poin, kali ini menggunakan distribusi yang seragam. Menggunakan kd-tree lain, kami menetapkan setiap titik ke pusat massa terdekat, membentuk kelompok. Kami kemudian memperkirakan warna median dari masing-masing cluster menggunakan algoritma mendaki bukit, memberikan warna sel terakhir kami (ide untuk langkah ini berkat @PhiNotPi dan @ MartinBüttner).
Catatan
Selain mengeluarkan file teks untuk snippet (
OUTFILE
), jikaDEBUG
diatur keTrue
program juga akan menampilkan dan menimpa gambar di atas. Algoritme membutuhkan beberapa menit untuk setiap gambar, jadi ini adalah cara yang baik untuk memeriksa kemajuan yang tidak menambah banyak waktu berjalan.Output sampel
N = 32:
N = 100:
N = 1000:
N = 3000:
sumber
Mathematica, Sel Acak
Ini adalah solusi dasar, jadi Anda mendapatkan gagasan tentang minimum yang saya minta dari Anda. Diberi nama file (lokal atau sebagai URL) di
file
dan N din
, kode berikut hanya memilih N piksel acak, dan menggunakan warna yang ditemukan di piksel tersebut. Ini benar-benar naif dan tidak bekerja dengan baik, tetapi saya ingin kalian mengalahkan ini semua. :)Berikut ini semua gambar uji untuk N = 100 (semua gambar terhubung ke versi yang lebih besar):
Seperti yang Anda lihat, ini pada dasarnya tidak berguna. Meskipun mereka mungkin memiliki nilai artistik, dengan cara ekspresionis, gambar asli hampir tidak dikenali.
Untuk N = 500 , situasinya sedikit ditingkatkan, tetapi masih ada artefak yang sangat aneh, gambar terlihat pudar, dan banyak sel yang terbuang pada daerah tanpa detail:
Giliranmu!
sumber
Dimensions@ImageData
dan tidakImageDimensions
? Anda dapat menghindari yang lambatImageData
sama sekali dengan menggunakanPixelValue
.Mathematica
Kita semua tahu Martin mencintai Mathematica, jadi izinkan saya mencobanya dengan Mathematica.
Algoritme saya menggunakan titik acak dari tepi gambar untuk membuat diagram awal voronoi. Diagram kemudian diprettify oleh penyesuaian berulang mesh dengan filter rata-rata sederhana. Ini memberikan gambar dengan kepadatan sel tinggi di dekat daerah kontras tinggi dan sel menyenangkan secara visual tanpa sudut gila.
Gambar-gambar berikut menunjukkan contoh proses yang sedang berjalan. Kesenangannya agak dimanjakan oleh Mathematicas Antialiasing yang buruk, tapi kami mendapatkan grafis vektor, itu pasti berharga.
Algoritma ini, tanpa pengambilan sampel acak, dapat ditemukan dalam
VoronoiMesh
dokumentasi di sini .Gambar Uji (100,300,1000,3000)
Kode
sumber
Graphics@Table[ Append[mp, VertexColors -> RGBColor /@ ImageValue[img, First[mp]]], {mp, MeshPrimitives[voronoiRelaxed, 2]}]
Pembawa acara Python + SciPy +
Algoritma yang saya gunakan adalah sebagai berikut:
Algoritme tampaknya berfungsi dengan sangat baik. Sayangnya itu hanya bisa berjalan dengan masuk akal pada gambar yang bertubuh kecil. Saya belum punya waktu untuk mengambil poin Voronoi dan menerapkannya pada gambar yang lebih besar. Mereka dapat disempurnakan pada saat ini. Saya juga bisa menjalankan MCMC lebih lama untuk mendapatkan minima yang lebih baik. Titik lemah algoritme adalah bahwa itu agak mahal. Saya belum punya waktu untuk meningkatkan lebih dari 1000 poin dan beberapa gambar 1000 poin sebenarnya masih disempurnakan.
(klik kanan dan lihat gambar untuk mendapatkan versi yang lebih besar)
Tautan ke versi yang lebih besar adalah http://imgur.com/a/2IXDT#9 (100 poin), http://imgur.com/a/bBQ7q (300 poin) dan http://imgur.com/a/rr8wJ (1000 poin)
Gambar yang tidak tertutup topeng terlihat seperti berikut ini. Poin acak dipilih dari gambar jika angka acak kurang dari nilai gambar (normed ke 1):
Saya akan memposting gambar yang lebih besar dan poin Voronoi jika saya mendapatkan lebih banyak waktu.
Sunting: Jika Anda menambah jumlah walker menjadi 100 * npts, ubah fungsi biaya menjadi beberapa kuadrat dari penyimpangan di semua saluran, dan tunggu beberapa saat (meningkatkan jumlah iterasi untuk keluar dari loop menjadi 200), dimungkinkan untuk membuat beberapa gambar yang bagus hanya dengan 100 poin:
sumber
Menggunakan energi gambar sebagai peta titik-berat
Dalam pendekatan saya terhadap tantangan ini, saya ingin cara untuk memetakan "relevansi" area gambar tertentu dengan probabilitas bahwa suatu titik tertentu akan dipilih sebagai centroid Voronoi. Namun, saya masih ingin melestarikan nuansa artistik Voronoi mosaicing dengan memilih titik gambar secara acak. Selain itu, saya ingin beroperasi pada gambar besar, jadi saya tidak kehilangan apa pun dalam proses downsampling. Algoritme saya kira-kira seperti ini:
Hasil
N
= 100, 500, 1000, 3000sumber