Representasi Haskell apa yang direkomendasikan untuk 2D, array piksel tanpa kotak dengan jutaan piksel?

Saya ingin mengatasi beberapa masalah pemrosesan gambar di Haskell. Saya bekerja dengan gambar bitonal (bitmap) dan berwarna dengan jutaan piksel. Saya punya sejumlah pertanyaan:

1. Atas dasar apa saya harus memilih antara Vector.Unboxeddan UArray? Keduanya adalah array yang tidak dikotakkan, tetapi Vectorabstraksi tampaknya banyak diiklankan, khususnya di sekitar fusi loop. Apakah Vectorselalu lebih baik? Jika tidak, kapan saya harus menggunakan representasi yang mana?

2. Untuk gambar berwarna, saya ingin menyimpan tiga kali lipat bilangan bulat 16-bit atau tiga kali lipat angka floating-point presisi tunggal. Untuk tujuan ini, apakah salah satu Vectoratau UArraylebih mudah digunakan? Lebih berkinerja?

3. Untuk gambar bitonal saya hanya perlu menyimpan 1 bit per piksel. Apakah ada tipe data standar yang dapat membantu saya di sini dengan mengemas beberapa piksel menjadi satu kata, atau saya sendiri?

4. Akhirnya, array saya adalah dua dimensi. Saya kira saya bisa menangani tipuan ekstra yang dikenakan oleh representasi sebagai "array array" (atau vektor vektor), tetapi saya lebih suka abstraksi yang memiliki dukungan pemetaan indeks. Adakah yang bisa merekomendasikan sesuatu dari perpustakaan standar atau dari Hackage?

Saya seorang programmer fungsional dan tidak membutuhkan mutasi :-)

Untuk array multi-dimensi, opsi terbaik saat ini di Haskell, menurut saya, adalah repa .

Repa menyediakan array paralel polimorfik bentuk berkinerja tinggi, teratur, multi-dimensi. Semua data numerik disimpan tanpa kotak. Fungsi yang ditulis dengan kombinator Repa secara otomatis paralel asalkan Anda menyediakan + RTS -N apa pun yang ada di baris perintah saat menjalankan program.

Baru-baru ini, ini telah digunakan untuk beberapa masalah pemrosesan gambar:

• Deteksi tepi waktu nyata
• Konvolusi Stensil Paralel yang Efisien di Haskell

Saya sudah mulai menulis tutorial tentang penggunaan repa , yang merupakan tempat yang baik untuk memulai jika Anda sudah mengetahui array Haskell, atau pustaka vektor. Batu loncatan utama adalah penggunaan tipe bentuk, bukan tipe indeks sederhana, untuk menangani indeks multidimensi (dan bahkan stensil).

Paket repa-io menyertakan dukungan untuk membaca dan menulis file gambar .bmp, meskipun dukungan untuk lebih banyak format diperlukan.

Mengatasi pertanyaan spesifik Anda, berikut adalah grafik, dengan diskusi:

Atas dasar apa saya harus memilih antara Vector.Unboxed dan UArray?

Mereka memiliki representasi dasar yang kira-kira sama, namun, perbedaan utamanya adalah luasnya API untuk bekerja dengan vektor: mereka memiliki hampir semua operasi yang biasanya Anda kaitkan dengan daftar (dengan kerangka kerja pengoptimalan yang digerakkan fusi), sementara UArrayhampir semuanya tidak ada API.

Untuk gambar berwarna, saya ingin menyimpan tiga kali lipat bilangan bulat 16-bit atau tiga kali lipat angka floating-point presisi tunggal.

UArraymemiliki dukungan yang lebih baik untuk data multi-dimensi, karena dapat menggunakan tipe data arbitrer untuk pengindeksan. Meskipun hal ini dimungkinkan Vector(dengan menulis sebuah instance dari UAuntuk jenis elemen Anda), ini bukanlah tujuan utama Vector- sebaliknya, ini adalah tempat Repamasuk, membuatnya sangat mudah untuk menggunakan tipe data kustom yang disimpan dengan cara yang efisien, berkat pengindeksan bentuk .

Dalam Repa, celana pendek Anda akan memiliki tipe:

Array DIM3 Word16

Artinya, array 3D Word16s.

Untuk gambar bitonal saya hanya perlu menyimpan 1 bit per piksel.

UArrays mengemas Bools sebagai bit, Vector menggunakan instance untuk Bool yang melakukan pengemasan bit, alih-alih menggunakan representasi berdasarkan Word8. Namun, mudah untuk menulis implementasi bit-packing untuk vektor - ini salah satunya , dari pustaka uvector (usang). Di bawah kap, Repamenggunakan Vectors, jadi saya pikir itu mewarisi pilihan representasi perpustakaan.

Apakah ada tipe data yang telah ditentukan yang dapat membantu saya di sini dengan mengemas beberapa piksel menjadi satu kata

Anda dapat menggunakan contoh yang ada untuk salah satu pustaka, untuk jenis kata yang berbeda, tetapi Anda mungkin perlu menulis beberapa pembantu menggunakan Data.Bits untuk menggulung dan membuka gulungan data yang dikemas.

Akhirnya, array saya adalah dua dimensi

UArray dan Repa mendukung array multi-dimensi yang efisien. Repa juga memiliki antarmuka yang kaya untuk melakukannya. Vektor sendiri tidak.

Sebutan penting:

• hmatrix , tipe array kustom dengan binding ekstensif ke paket aljabar linier. Harus terikat untuk menggunakan vectoratau repatipe.
• ix-shapeable , mendapatkan pengindeksan yang lebih fleksibel dari array biasa
• papan tulis , perpustakaan Andy Gill untuk memanipulasi gambar 2D
• codec-image-devil , baca dan tulis berbagai format gambar ke UArray

Setelah saya meninjau fitur pustaka array Haskell yang penting bagi saya, dan menyusun tabel perbandingan (hanya spreadsheet: tautan langsung ). Jadi saya akan mencoba menjawab.

Atas dasar apa saya harus memilih antara Vector.Unboxed dan UArray? Keduanya adalah array yang tidak dikotakkan, tetapi abstraksi Vektor tampaknya banyak diiklankan, khususnya di sekitar fusi loop. Apakah Vector selalu lebih baik? Jika tidak, kapan saya harus menggunakan representasi yang mana?

UArray mungkin lebih disukai daripada Vektor jika seseorang membutuhkan array dua dimensi atau multi-dimensi. Tetapi Vector memiliki API yang lebih bagus untuk memanipulasi, ya, vektor. Secara umum, Vector tidak cocok untuk simulasi array multi-dimensi.

Vector.Unboxed tidak dapat digunakan dengan strategi paralel. Saya menduga UArray juga tidak dapat digunakan, tetapi setidaknya sangat mudah untuk beralih dari UArray ke Array kotak dan melihat apakah manfaat paralelisasi lebih besar daripada biaya tinju.

Untuk gambar berwarna, saya ingin menyimpan tiga kali lipat bilangan bulat 16-bit atau tiga kali lipat angka floating-point presisi tunggal. Untuk tujuan ini, apakah Vector atau UArray lebih mudah digunakan? Lebih berkinerja?

Saya mencoba menggunakan Array untuk merepresentasikan gambar (meskipun saya hanya membutuhkan gambar grayscale). Untuk gambar berwarna saya menggunakan pustaka Codec-Image-DevIL untuk membaca / menulis gambar (mengikat ke pustaka DevIL), untuk gambar grayscale saya menggunakan pgm library (Haskell murni).

Masalah utama saya dengan Array adalah ia hanya menyediakan penyimpanan akses acak, tetapi tidak menyediakan banyak cara untuk membangun algoritme Array juga tidak dilengkapi dengan perpustakaan rutinitas array yang siap digunakan (tidak berinteraksi dengan perpustakaan aljabar linier, bukan tidak memungkinkan untuk mengekspresikan konvolusi, fft dan transformasi lainnya).

Hampir setiap kali Array baru harus dibangun dari Array yang sudah ada, daftar nilai antara harus dibuat (seperti perkalian matriks dari Pendahuluan Lembut). Biaya konstruksi larik sering kali melebihi manfaat dari akses acak yang lebih cepat, sampai-sampai representasi berbasis daftar lebih cepat dalam beberapa kasus penggunaan saya.

STUArray dapat membantu saya, tetapi saya tidak suka berkelahi dengan kesalahan jenis samar dan upaya yang diperlukan untuk menulis kode polimorfik dengan STUArray .

Jadi masalah dengan Array adalah Array tidak cocok untuk perhitungan numerik. Hmatrix 'Data.Packed.Vector dan Data.Packed.Matrix lebih baik dalam hal ini, karena mereka datang bersama dengan perpustakaan matriks yang solid (perhatian: lisensi GPL). Dari segi performa, pada perkalian matriks, hmatrix cukup cepat ( hanya sedikit lebih lambat dari Oktaf ), tetapi sangat haus memori (dikonsumsi beberapa kali lebih banyak daripada Python / SciPy).

Ada juga pustaka blas untuk matriks, tetapi tidak dibangun di atas GHC7.

Saya belum memiliki banyak pengalaman dengan Repa, dan saya tidak memahami kode repa dengan baik. Dari apa yang saya lihat, ia memiliki rentang yang sangat terbatas dari matriks siap pakai dan algoritme larik yang ditulis di atasnya, tetapi setidaknya dimungkinkan untuk mengekspresikan algoritme penting melalui perpustakaan. Misalnya, sudah ada rutinitas untuk perkalian matriks dan konvolusi dalam algoritma repa. Sayangnya, tampaknya konvolusi sekarang terbatas pada kernel 7 × 7 (ini tidak cukup bagi saya, tetapi seharusnya cukup untuk banyak kegunaan).

Saya tidak mencoba pengikatan OpenCV Haskell. Mereka harus cepat, karena OpenCV sangat cepat, tetapi saya tidak yakin apakah binding sudah lengkap dan cukup bagus untuk dapat digunakan. Selain itu, OpenCV pada dasarnya sangat penting, penuh dengan pembaruan yang merusak. Saya kira sulit untuk mendesain antarmuka fungsional yang bagus dan efisien di atasnya. Jika salah satu menggunakan cara OpenCV, dia cenderung menggunakan representasi gambar OpenCV di mana-mana, dan menggunakan rutinitas OpenCV untuk memanipulasinya.

Untuk gambar bitonal saya hanya perlu menyimpan 1 bit per piksel. Apakah ada tipe data standar yang dapat membantu saya di sini dengan mengemas beberapa piksel menjadi satu kata, atau saya sendiri?

Sejauh yang saya tahu, array Bools yang tidak dikotak menangani pengepakan dan pembongkaran vektor bit. Saya ingat melihat implementasi array Bools di perpustakaan lain, dan tidak melihatnya di tempat lain.

Akhirnya, array saya adalah dua dimensi. Saya kira saya bisa menangani tipuan ekstra yang dikenakan oleh representasi sebagai "array array" (atau vektor vektor), tetapi saya lebih suka abstraksi yang memiliki dukungan pemetaan indeks. Adakah yang bisa merekomendasikan sesuatu dari perpustakaan standar atau dari Hackage?

Selain Vektor (dan daftar sederhana), semua pustaka array lainnya mampu mewakili array atau matriks dua dimensi. Saya kira mereka menghindari tipu muslihat yang tidak perlu.

Meskipun, ini tidak benar-benar menjawab pertanyaan Anda dan bahkan tidak benar-benar haskell seperti itu, saya akan merekomendasikan untuk melihat perpustakaan CV atau CV-combinators di hackage. Mereka mengikat banyak pemrosesan gambar dan operator vision yang cukup berguna dari pustaka-opencv dan membuat bekerja dengan masalah visi mesin jauh lebih cepat.

Akan lebih bagus jika seseorang mengetahui bagaimana repa atau beberapa perpustakaan array bisa langsung digunakan dengan opencv.

Ini adalah pustaka Pemrosesan Gambar Haskell baru yang dapat menangani semua tugas yang dimaksud dan banyak lagi. Saat ini ia menggunakan paket Repa dan Vektor untuk representasi yang mendasarinya, yang akibatnya mewarisi fusi, komputasi paralel, mutasi, dan sebagian besar barang lain yang disertakan dengan pustaka tersebut. Ini menyediakan antarmuka yang mudah digunakan yang alami untuk manipulasi gambar:

• 2D pengindeksan dan tanpa box piksel dengan presisi sewenang-wenang ( Double, Float, Word16, dll ..)
• semua fungsi penting seperti map, fold, zipWith, traverse...
• dukungan untuk berbagai ruang warna: RGB, HSI, skala abu-abu, Bi-tonal, Kompleks, dll.
• fungsi pemrosesan gambar umum:
  • Morfologi biner
  • Lilitan
  • Interpolasi
  • Transformasi Fourier
  • Pembuatan plot histogram
  • dll.
• Kemampuan untuk memperlakukan piksel dan gambar sebagai angka biasa.
• Membaca dan menulis format gambar umum melalui perpustakaan JuicyPixels

Yang terpenting, ini adalah pustaka Haskell murni, jadi tidak bergantung pada program eksternal apa pun. Ini juga sangat dapat diperpanjang, ruang warna baru dan representasi gambar dapat diperkenalkan.

Satu hal yang tidak dilakukannya adalah mengemas beberapa piksel biner dalam a Word, melainkan menggunakan Wordpiksel per biner, mungkin di masa mendatang ...