JFA (algoritma yang diuraikan di sini: http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf ) dapat digunakan untuk mendapatkan perkiraan diagram Voronoi, atau transformasi jarak. Ia melakukannya dalam waktu logaritmik berdasarkan pada ukuran gambar yang dihasilkan, bukan pada jumlah biji.

Apa yang Anda lakukan jika gambar Anda tidak memiliki ukuran yang sama pada setiap sumbu?

Jika ukurannya serupa, saya yakin Anda bisa membiarkan sumbu yang lebih pendek memiliki langkah JFA ekstra ukuran 1, sementara sumbu yang lebih besar selesai bekerja (seperti memiliki gambar berukuran 512 x 256). Untuk dimensi sumbu ukuran yang sangat berbeda, ini bisa menjadi jauh lebih tidak efisien - katakanlah Anda memiliki tekstur volume yang 512 x 512 x 4.

Apakah mungkin untuk menjalankan JFA pada setiap sumbu secara terpisah dan masih mendapatkan hasil yang layak?

Atau pada titik itu apakah algoritma yang berbeda lebih tepat untuk digunakan? Jika demikian, algoritma apa itu?

Dalam situasi saya idealnya saya mencari untuk mendukung biji titik tunggal, serta biji berbentuk sewenang-wenang. Kemungkinan bahkan benih tertimbang, di mana jarak ke benih disesuaikan oleh pengganda dan / atau penambah untuk memberikan pengaruh lebih atau kurang.

Jawaban cepat untuk pertanyaan pribadi Anda

Apa yang Anda lakukan jika gambar Anda tidak memiliki ukuran yang sama pada setiap sumbu?

Makalah ini menggunakan gambar persegi dengan panjang sisi yang merupakan kekuatan 2. Ini untuk memudahkan penjelasan, tetapi tidak diperlukan untuk algoritma untuk bekerja. Lihat bagian 3.1:

Tanpa kehilangan keumuman, kita dapat menganggap n adalah kekuatan 2.

Artinya, asumsi ini tidak diperlukan agar algoritma dapat bekerja.

Apakah mungkin untuk menjalankan JFA pada setiap sumbu secara terpisah dan masih mendapatkan hasil yang layak?

Berjalan di setiap sumbu secara terpisah cenderung memberikan hasil piksel yang lebih salah, dan membutuhkan waktu lebih lama untuk berjalan dalam kebanyakan kasus. Dalam kasus ekstrim di mana salah satu panjang sisi gambar kurang dari 8 (jumlah arah lompatan), mungkin lebih cepat karena algoritme memperlakukan 8 arah secara berurutan, tetapi untuk gambar yang lebih luas, memisahkan sumbu kehilangan manfaat merawatnya sejajar.

Dalam situasi saya idealnya saya mencari untuk mendukung kedua biji titik tunggal, serta biji berbentuk sewenang-wenang

Makalah ini menyebutkan biji berbentuk sewenang-wenang di bagian 6 di bawah judul "Diagram Voronoi Umum":

... algoritme kami memperlakukan benih umum tersebut sebagai koleksi benih titik dan karenanya mengharapkan untuk mewarisi kinerja yang baik yang diperoleh benih poin.

Jadi asalkan sesuai dengan tujuan Anda untuk memodelkan bentuk sewenang-wenang sebagai kumpulan piksel, Anda tidak perlu melakukan penyesuaian apa pun pada algoritma. Cukup beri makan dalam tekstur yang label semua piksel dalam benih berbentuk sewenang-wenang dengan nomor benih yang sama, tetapi lokasi yang berbeda.

Kemungkinan bahkan benih tertimbang, di mana jarak ke benih disesuaikan oleh pengganda dan / atau penambah untuk memberikan pengaruh lebih atau kurang

Untuk "memberi bobot pada biji seperti multiplikasi dan aditif", makalah ini hanya menyebutkan kemungkinan untuk lewat di bagian 8, sebagai pekerjaan potensial di masa depan. Namun, ini harus langsung diterapkan asalkan bobot yang Anda inginkan dapat dimasukkan dalam data unggulan yang diteruskan dari piksel ke piksel.

Algoritma saat ini lolos <s, position(s)>untuk menentukan seed dan posisinya, dan hanya satu seed yang disimpan per pixel pada satu waktu. Memperluas ini untuk menyimpan <s, position(s), weight(s)>menyediakan semua informasi yang diperlukan untuk menimbang fungsi jarak dan menghitung apakah benih baru yang diteruskan ke piksel lebih dekat daripada yang disimpan saat ini.

Anda bahkan dapat memasukkan dua bobot, satu multiplikatif dan satu aditif, dan hanya mengatur multiplikatif satu ke 1 dan satu aditif menjadi 0 bila tidak diperlukan. Kemudian algoritma Anda akan mencakup kemungkinan digunakan untuk benih berbobot banyak, benih berbobot tambahan, atau bahkan kombinasi keduanya sekaligus atau sebagian. Ini hanya perlu

<s, position(s), multiplicative(s), additive(s)>

dan algoritma saat ini akan setara dengan menggunakan algoritma baru ini

<s, position(s), 1, 0>

Penjelasan terperinci tentang alasannya

$\log()$

Algoritma tidak perlu diadaptasi untuk panjang sisi yang berbeda

Jika panjang sisi tidak sama, dan bukan kekuatan 2, tidak perlu menyesuaikan algoritma. Ini sudah berurusan dengan piksel di tepi gambar yang beberapa arahan lompatannya mengarah ke luar gambar. Karena algoritma sudah menghilangkan informasi awal untuk arah yang mengarah di luar gambar, lebar atau tinggi yang bukan kekuatan 2 tidak akan menjadi masalah. Untuk gambar dengan lebar W dan tinggi H, ukuran lompatan maksimum yang diperlukan adalah

Untuk kasus lebar dan tinggi N yang sama, ini berkurang menjadi

Dalam hal panjang sisi N yang merupakan kekuatan 2, ini berkurang menjadi

seperti yang digunakan dalam kertas.

Dalam istilah yang lebih intuitif, bulatkan panjang sisi maksimum hingga kekuatan 2 berikutnya, dan kemudian belah dua untuk mendapatkan ukuran lompatan maksimum.

Ini selalu cukup untuk menutupi setiap piksel dalam gambar dari setiap piksel lainnya dalam gambar, karena offset ke piksel apa pun akan berada dalam kisaran 0 hingga N-1 jika panjang sisi terpanjang adalah N. Kombinasi kekuatan 2 dari 0 hingga N / 2 akan mencakup setiap bilangan bulat hingga N-1 jika N adalah kekuatan 2, dan jika N bukan kekuatan 2, kisaran yang dicakup hanya bisa lebih besar dari yang dibutuhkan, karena mengambil plafon logaritma ( pembulatan ke kekuatan berikutnya 2).

Gambar dengan sisi bukan kekuatan 2 tidak akan secara drastis kurang efisien

Jumlah lompatan tergantung pada panjang sisi terpanjang, katakan L. Jika L adalah kekuatan 2 maka jumlah lompatan adalah . Jika L bukan kekuatan 2 maka jumlah lompatan adalah . Untuk gambar yang cukup besar, ini tidak akan menjadi perbedaan besar.⌈ log ( L ) $\log(L)$$\lceil\log(L)\rceil$

Misalnya, gambar 1024 kali 1024 akan membutuhkan 10 iterasi lompatan. Gambar berukuran 512 kali 512 membutuhkan 9 kali iterasi. Apa pun di antara dua ukuran juga akan membutuhkan 10 iterasi. Bahkan dalam kasus terburuk dari suatu gambar hanya lebih dari kekuatan 2, seperti gambar 513 oleh 513, itu hanya akan membutuhkan 1 iterasi tambahan, yang pada skala ini kira-kira 11% lebih banyak (10 bukannya 9).

Gambar non-persegi kurang efisien per area

Karena jumlah iterasi yang diperlukan ditentukan oleh panjang sisi terpanjang, waktu yang dibutuhkan untuk gambar 1024 kali 1024 akan sama dengan gambar 1024 kali 16. Gambar persegi memungkinkan area yang lebih besar untuk dicakup dalam jumlah iterasi yang sama.

Memisahkan sumbu cenderung mengurangi kualitas

Bagian 5 dari makalah ini menjelaskan kemungkinan kesalahan. Setiap piksel dapat dijangkau oleh jalur dari setiap piksel lainnya, tetapi beberapa jalur tidak membawa seed terdekat yang benar, karena seed tersebut bukan yang terdekat dengan pixel sebelumnya di path. Sebuah piksel yang tidak memungkinkan benih untuk menyebar melewati itu dikatakan telah "membunuh" benih itu. Jika seed terdekat ke pixel terbunuh di semua jalur ke pixel itu, maka pixel akan merekam beberapa seed lain dan akan ada warna yang salah pada gambar akhir.

Hanya satu jalur yang perlu ada yang tidak membunuh benih agar hasil akhirnya benar. Warna yang salah hanya terjadi ketika semua jalur dari seed yang benar ke piksel yang diberikan diblokir.

Jika jalur melibatkan lompatan horizontal dan vertikal bergantian, memisahkan sumbu akan membuat jalur ini tidak mungkin (semua lompatan horizontal akan diambil sebelum semua lompatan vertikal, membuat bolak-balik menjadi mustahil). Lompatan diagonal tidak mungkin dilakukan sama sekali. Jadi setiap jalur yang bergantian atau mengandung lompatan diagonal akan dikecualikan. Setiap piksel masih akan memiliki jalur ke setiap piksel lainnya, tetapi karena sekarang ada lebih sedikit jalur, maka ada peluang lebih banyak piksel yang diberikan diblokir untuk menerima seed yang benar, sehingga hasil akhirnya akan lebih rentan kesalahan.

Memisahkan sumbu cenderung membuat algoritma lebih lama

Efisiensi mungkin akan berkurang dengan memisahkan sumbu, karena banjir tidak akan lagi dilakukan secara paralel, tetapi sebaliknya akan diulang untuk setiap sumbu. Untuk 2D ini akan memakan waktu sekitar dua kali lebih lama, dan untuk 3D sekitar 3 kali lebih lama.

Ini mungkin agak dimitigasi oleh kurangnya lompatan diagonal, tapi saya masih mengharapkan pengurangan efisiensi secara keseluruhan.