Get best of the week

Perhitungan pusat massa untuk O (1) menggunakan gambar terintegrasi



Gambar terintegrasi adalah algoritma yang memungkinkan Anda menghitung secara efisien jumlah nilai yang terlampir dalam subset persegi panjang dari array multidimensi. Gagasannya berasal dari studi tentang fungsi distribusi probabilitas multidimensi, dan sampai sekarang ia telah menemukan aplikasi yang sukses di area tersebut yang secara langsung menggunakan teori probabilitas sebagai toolkit utama. Misalnya, dalam pengenalan pola.

Hari ini kita akan mempertimbangkan kasus aneh tentang bagaimana menerapkan gambar terintegrasi dalam bidang komputasi fisika yang sangat berbeda. Yaitu, mari kita lihat apa yang terjadi jika kita menghitung dengan mereka pusat massa bidang pulsa, dan manfaat apa yang dapat diperoleh dari simbiosis ini.

Dalam artikel ini saya akan memberi tahu:

  • Tugas macam apa ini?
  • Baca lebih lanjut tentang gambar terintegrasi;
  • N (-);
  • ;
  • , , .

N


Sebuah solusi yang ketat untuk interaksi gravitasi dari suatu sistem benda N mengacu pada algoritma yang memiliki kompleksitas kuadrat: semua benda lain dalam sistem memiliki efek gravitasi pada setiap benda [1] . Akibatnya, kekuatan kebutuhan interaksi gravitasi untuk menghitung untuk setiap N 2 pasangan / 2.

Untuk mengilustrasikan betapa memakan waktu solusi yang ketat, Anda dapat mencoba untuk mengkorelasikan kompleksitas penghitungan sistem nyata dengan kinerja komputer modern.

Untuk menghitung gaya gravitasi antara dua benda dalam ruang tiga dimensi, Anda harus melakukan 20 operasi dengan floating point (FLOP). Di tata surya, ada sekitar 100 benda yang lebih besar dari 200 kilometer (termasuk Matahari, 9 planet, planet kerdil, dan satelit) [2]. Perkiraan jumlah asteroid di orbit dekat-Bumi adalah sekitar 20 ribu [3] . Di sabuk asteroid, ada 1,1 hingga 1,9 juta benda lebih besar dari 1 km [4] dan sekitar satu juta asteroid serupa di kelompok "Trojan" [5] dan "Yunani" di Jupiter. Di sabuk Kuiper, sekitar 100 juta objek lebih besar dari 20 km [6] dan sekitar 2 triliun lebih berada di awan Oort [7] .



Kekuatan komputasi yang diperlukan untuk secara ketat menyelesaikan masalah gravitasi terakhir hanya urutan besarnya lebih kecil dari kekuatan komputasi yang diperlukan untuk mensimulasikan kerja otak manusia pada tingkat saraf (2,5 × 10 26 ) [8]. Itu sebabnya solusi yang ketat biasanya diganti dengan yang perkiraan.

Salah satu algoritma yang paling banyak digunakan untuk solusi perkiraan masalah gravitasi - Tree Code - memiliki kompleksitas waktu quearinear O (N * logN) [9] . Kode Pohon membangun pohon spasial dan untuk setiap simpul di pohon ini menghitung massa total dan pusat massa semua tubuh yang jatuh ke dalamnya. Lebih lanjut, ketika menghitung gaya gravitasi yang bekerja pada masing-masing tubuh, Kode Pohon dapat memperhitungkan bukan pengaruh langsung dari benda lain, tetapi pengaruh simpul pohon, dan tergantung pada jaraknya, ia memilih simpul yang lebih besar yang berisi parameter subset tubuh yang semakin banyak.


Ilustrasi dari Wikipedia. Di tubuh di tengah adalah massa node yang ditunjukkan oleh persegi panjang hijau. Hanya massa badan terdekat yang diperhitungkan secara langsung.

Masalah gravitasi untuk medan momentum


Medan momentum adalah bidang vektor diskret mv (p) , yang mengaitkan pasangan kecepatan-massa dengan setiap titik ruang p yang sedang dipertimbangkan . Bidang pulsa dapat diatur untuk ruang dimensi apa pun. Pasangan kecepatan-massa mencirikan momentum dan mewakili vektor dimensi R + 1, di mana R adalah dimensi ruang tempat medan pulsa diberikan. Misalnya, untuk R = 2 ini bisa menjadi vektor { v x , v y , m }.

Perlu dicatat bahwa versi matematika tradisional dari deskripsi sistem ini adalah kombinasi dari bidang kecepatan vektor dan bidang massa skalar. Dalam hal ini, kami mengizinkan diri kami kebebasan untuk menggabungkan kecepatan dan massa dalam satu vektor, karena kami tidak berpura-pura menjadi matematis.


Sebagian kecil bidang vektor pulsa: massa ditunjukkan oleh warna, arah oleh panah,


bidang vektor pulsa dengan ukuran 729 × 729 elemen. Di sebelah kiri adalah massa. Di sebelah kanan adalah impuls. Pulsa dalam ilustrasi ini diberi kode warna dalam format HSV (Hue adalah arah pulsa, dan Nilai menampilkan urutan nilai absolutnya secara linear sehingga pulsa yang paling tidak dapat dibedakan (Nilai = 0,05) berada di urutan 10 -7 , dan pulsa paling terang (Nilai = 1) , 0) berada di urutan 10 3 dan lebih tinggi).

Mirip dengan ini - grid - metode untuk menggambarkan sistem fisik banyak digunakan dalam astrofisika untuk mensimulasikan evolusi awan gas, pembentukan bintang dan galaksi. Ini termasuk metode SAMR [10] atau model grid hidrodinamika [11] .

Seperti dalam kasus masalah gravitasi benda-benda N, evolusi medan diskrit harus memperhitungkan pengaruh gravitasi semua massa yang membentuk medan ini pada setiap elemen diskritnya. Penting untuk memperhitungkan bahwa kompleksitas masalah secara tidak langsung tergantung pada dimensi ruang R : misalnya, untuk bidang pada bidang yang terdiri dari 1000 × 1000 elemen, jumlah total N akan menjadi 10 6elemen, dan bidang dengan ukuran yang sama dalam ruang tiga dimensi sudah akan mencakup 10 9 elemen.

Namun demikian, ada sejumlah trik yang memungkinkan untuk menyelesaikan masalah gravitasi untuk medan momentum. Metode Multigrid menggunakan diskritisasi hierarkis, mendukung beberapa kisi dengan berbagai ukuran [12] . Multipole Expansion memperlakukan kelompok sumber yang dekat satu sama lain sebagai satu objek [13] . Multigrid memiliki beberapa kompleksitas komputasi dan kompleksitas memori logaritmik. Salah satu opsi Ekspansi Multipole - FMM - menunjukkan kompleksitas komputasi linier dengan imbalan penurunan akurasi komputasi [14] .

Di bawah ini kami mempertimbangkan metode lain yang memungkinkan kami untuk memecahkan masalah gravitasi untuk bidang pulsa yang terpisah dalam waktu quasilinear dan memiliki kompleksitas linear dalam memori.

Gambar terintegrasi


Gambar integral memungkinkan menghitung waktu konstan jumlah elemen gambar asli di wilayah persegi panjang sewenang-wenang [15] . Dalam grafik komputer, gambar terintegrasi pada awalnya diusulkan sebagai alternatif untuk pemetaan mipmapping dan anisotropik [16] . Selain itu, mereka berhasil digunakan untuk pemrosesan gambar digital dan teknik pengenalan pola.

Gambar terintegrasi adalah salah satu contoh yang paling jelas dari pertukaran antara kompleksitas komputasi dan kompleksitas memori. Algoritma "naif" untuk menghitung jumlah elemen gambar memiliki kompleksitas waktu O (M * N) dan kompleksitas memori O (1). Gambar terintegrasi memungkinkan Anda untuk melakukan perhitungan yang sama dalam waktu O (1) dan memiliki kompleksitas memori O (M * N).


Menggunakan gambar terintegrasi untuk menghitung jumlah elemen dalam suatu wilayah tertentu

. Algoritma untuk menghitung gambar integral sangat sederhana, ditandai dengan kompleksitas komputasi linier dan mudah diparalelkan di bawah GPGPU [17] . Ini diimplementasikan seperti filter Gaussian dua laluan [18] : pada lintasan pertama, jumlah parsial untuk baris dipertimbangkan, pada lajur kedua, jumlah parsial ini diakumulasikan dalam kolom.


Perhitungan gambar terintegrasi dalam dua lintasan. Di sebelah kiri adalah gambar asli. Di tengah adalah jumlah parsial untuk garis. Di sebelah kanan adalah gambar terintegrasi akhir.


Di sebelah kiri adalah gambar yang mengandung massa elemen. Di sebelah kanan adalah gambar integralnya. Gambar di sebelah kiri dan kanan menggunakan skala logaritmik yang berbeda.

Solusi perkiraan untuk masalah gravitasi menggunakan gambar terintegrasi


Dengan memiliki citra integral massa, tidak sulit untuk menyesuaikan karakteristik teknik Kode Pohon dan Ekspansi Multipole ke dalamnya. Jadi, untuk setiap elemen bidang diskrit:

  1. Kami langsung memperhitungkan pengaruh massa hanya dari delapan elemen tetangga;
  2. Kami memperhitungkan pengaruh delapan daerah tetangga, yang terdiri dari sembilan elemen (3 × 3), dengan menghitung jumlah massa mereka menggunakan gambar terintegrasi;
  3. Pada setiap langkah selanjutnya, kami menambah ukuran wilayah sebanyak 3 kali (9 × 9, 27 × 27, 81 × 81, dll.) Hingga langkah ini melebihi ukuran seluruh bidang vektor.


Perkiraan perhitungan gaya yang bekerja pada elemen bidang vektor pulsa menggunakan gambar integral massa

Kerumitan solusi perkiraan masalah gravitasi untuk bidang pulsa menggunakan gambar terintegrasi tumbuh secara kuartinear, seperti O (N * 8 * log3 (sqrt (N))) untuk R = 2 dan seperti O (N * 26 * log3 (cbrt (N))) untuk R = 3.



Namun, dalam bentuk ini, solusi ini memiliki kelemahan yang sama dengan teknik Multigrid, yaitu "kekakuan" tangible diskrit dari komponen frekuensi rendah dari fungsi gravitasi. Cara termudah untuk menunjukkan masalah ini jelas.


Gaya dalam ilustrasi ini diberi kode warna dalam format HSV (Hue adalah arah gaya, Nilai secara linear menampilkan urutan nilai absolutnya sedemikian rupa sehingga gaya yang paling tidak dapat dibedakan (Nilai = 0,05) berada di urutan 10 -7 , dan gaya paling terang (Nilai = 1, 0) berada di urutan 10 3 dan lebih tinggi).

Dalam ilustrasi di atas, efek "kekakuan" komponen frekuensi rendah dari fungsi gravitasi terlihat oleh mata telanjang. Tetapi jika dalam "Multigrid" "kekakuan" ini terjadi karena penurunan frekuensi sampling, maka dalam gambar terintegrasi ini adalah karena kurangnya informasi tentang sifat distribusi spasial massa. Faktanya adalah suatu algoritma yang mendekati kekuatan menggunakan gambar terintegrasi menganggap bahwa pusat massa bertepatan dengan pusat wilayah.


Bagian tengah ilustrasi menunjukkan ekstrem massa dengan distribusi massa yang relatif seragam di seluruh bidang, sedangkan ekstrem

massa jatuh ke dalam masing-masing dari empat wilayah persegi panjang. Jelas, posisi pusat massa masing-masing daerah harus kira-kira bertepatan dengan elemen yang ditunjukkan oleh warna putih, yang massanya tiga kali lipat lebih besar daripada massa sebagian besar elemen wilayah yang ditandai dengan warna kuning. Namun, dalam perhitungan komponen frekuensi rendah dari fungsi gravitasi untuk daerah ini, diyakini bahwa pusat massa mereka bertepatan dengan pusat daerah yang ditunjukkan oleh lingkaran.

Masalah ini dapat diselesaikan dengan memasukkan informasi tambahan ke dalam gambar terintegrasi, yang akan memungkinkan untuk menghitung tidak hanya jumlah massa di wilayah tertentu, tetapi juga koordinat pusat massa.

Pertama, mari kita coba membayangkan sebuah gambar, yang masing-masing elemennya mengandung koordinatnya sendiri. Gambar integral yang sesuai akan berisi jumlah koordinat. Oleh karena itu, jumlah wilayah acak dari gambar terintegrasi ini, dibagi dengan jumlah total elemen di wilayah ini, akan sama dengan koordinat pusat wilayah ini.


Gambar integral koordinat

Mari kita ambil contoh wilayah di sudut kiri bawah dengan koordinat {3; 1} dan di kanan atas dengan koordinat {7; 5}. Jumlah koordinat wilayah ini {168; 120} - {18; 45} - {28; 0} + {3; 0} adalah {125; 75}, jumlah total elemen adalah 25, oleh karena itu, koordinat pusatnya adalah {5; 3}.

Yang masih harus dilakukan adalah menggeneralisasi kasus khusus ini di mana kami menganggap bahwa semua elemen gambar memiliki koefisien bobot yang sama dengan kesatuan. Untuk memperhitungkan bobot yang berbeda, kami akan mengalikan koordinat elemen dengan mereka. Dan kita akan mendapatkan koordinat tertimbang dari pusat wilayah jika kita membagi jumlah koordinat tertimbang dengan jumlah faktor bobot.


Gambar terintegrasi koordinat tertimbang. Font yang lebih besar menunjukkan bobot

Pertimbangkan wilayah di sudut kiri bawah dengan koordinat {2; 1} dan di kanan atas dengan koordinat {5; 4}. Jumlah dari koefisien bobot dari wilayah ini 4.8 - 1.0 - 0.6 + 0.2 adalah 3.4, dan jumlah dari koordinat tertimbangnya (11.1; 13.2} - {0,5; 2.0} - {1,5; 0,0} + {0,1; 0,0} sama dengan {9,2; 11.2}. Dengan demikian, koordinat tertimbang dari pusat wilayah ini adalah {2,7; 3.3}.

Untuk memastikan bahwa rangkaian ini benar-benar berfungsi, Anda dapat secara visual - dengan mengonversi gambar terintegrasi dengan koordinat tertimbang ke bidang jarak menggunakan transformasi jarak [19] .


Mengonversi gambar terintegrasi dengan koordinat tertimbang ke bidang jarak. Di sebelah kiri adalah gambar massa. Gambar berikut adalah jarak ke pusat massa untuk wilayah elemen 3 × 3. Berikutnya adalah jarak ke pusat massa untuk daerah dengan ukuran elemen 9 × 9 dan 27 × 27. Nilai jarak dalam ilustrasi ini dinormalisasi dengan ukuran wilayah yang digunakan untuk pengambilan sampel.


Mengonversi gambar terintegrasi dengan koordinat tertimbang ke bidang jarak terarah. Arah dan jarak diberi kode warna dalam format HSV, di mana Hue adalah arahnya, Nilai adalah jarak yang dinormalisasi. Nilai jarak dalam ilustrasi ini dinormalisasi dengan ukuran wilayah yang digunakan untuk pengambilan sampel.

Ringkas semua hal di atas:

  1. , , ( , R = 3) ― , , .
  2. .
  3. O(1).
  4. O(M*N).


. ― . ― .


Waktu untuk memperhatikan salah satu fitur utama dari gambar terintegrasi, yang masih membatasi ruang lingkup aplikasi mereka, yaitu, konsumsi sumber daya dan stabilitas numerik. Jadi, tergantung pada rentang nilai yang berisi gambar asli, tipe data yang lebih panjang mungkin diperlukan untuk gambar integralnya. Misalnya, ketika menghitung penyimpangan standar, selain gambar asli (rentang nilai 0..255), gambar yang berisi kotak dari nilai yang sesuai (rentang nilai 0..65535) digunakan. Dalam hal ini, akurasi tidak cukup untuk menghitung gambar terintegrasi skala besar dari 32 bit [20] .

Situasi serupa diamati dalam kasus gambar terintegrasi dengan koordinat tertimbang. Dengan sendirinya, nilai jumlah koordinat yang harus disimpan dalam gambar terintegrasi tumbuh tergantung pada ukuran gambar N: secara kuadrat untuk kasus satu dimensi 0 + 1 + 2 + ... + N - 1 = (N - 1) * N / 2 dan secara kubik untuk dua dimensi N * (N - 1) * N / 2. Misalnya, untuk menyimpan jumlah satu bilangan bulat koordinat untuk gambar ukuran 2048 × 2048 (sama dengan 4292870144), bilangan bulat 32-bit unsigned (nilai maksimumnya adalah 4294967295) hampir tidak cukup. Saat menghitung gambar terintegrasi yang lebih besar, terjadi overflow.

Penggunaan angka floating-point 32-bit dalam gambar terintegrasi menunda masalah overflow oleh jarak astronomi (10 38 - 10 10), tetapi pada saat yang sama, akurasi perhitungan dengan koordinat tertimbang berkurang secara signifikan karena kesalahan pemotongan diakumulasikan selama penjumlahan [21] .


Nilai absolut dari kesalahan dalam menghitung pusat massa tertimbang dari suatu wilayah dengan ukuran 4 × 4 elemen. Gambar terintegrasi berisi angka presisi tunggal (32 bit).


Nilai absolut dari kesalahan dalam menghitung pusat massa tertimbang dari suatu wilayah dengan ukuran 32 × 32 elemen. Gambar terintegrasi berisi angka presisi tunggal (32 bit).

Nilai absolut terbesar dicapai dengan perhitungan pusat massa tertimbang untuk daerah kecil. Peningkatan ukuran wilayah dengan dua orde magnitudo menyebabkan penurunan besarnya kesalahan absolut perhitungan oleh empat orde magnitudo. Dalam hal ini, tidak ditemukan ketergantungan kesalahan perhitungan pada kisaran nilai koefisien berat (yang digunakan untuk menghitung koordinat bobot elemen) yang ditemukan.


Peningkatan rentang bobot tidak mempengaruhi nilai absolut kesalahan dalam menghitung pusat massa tertimbang. Grafik menunjukkan kesalahan untuk wilayah "terburuk" (di sudut kanan atas gambar terintegrasi). Ukuran gambar terintegrasi adalah 256 × 256 elemen.


Nilai absolut dari kesalahan dalam menghitung pusat massa tertimbang berkurang dengan meningkatnya ukuran wilayah. Grafik menunjukkan kesalahan untuk wilayah "terburuk" (di sudut kanan atas gambar terintegrasi).

Berdasarkan analisis yang dijelaskan di atas, kita dapat menyimpulkan bahwa penggunaan angka presisi tunggal untuk menghitung pusat massa tertimbang menggunakan gambar terintegrasi masuk akal secara praktis hanya untuk gambar berukuran sekitar 512 × 512 elemen. Dengan peningkatan lebih lanjut dalam ukuran, besarnya kesalahan menjadi sebanding dengan ukuran elemen gambar. Dan meskipun kesalahan ini berkurang dengan bertambahnya ukuran wilayah, itu adalah wilayah dengan ukuran kecil yang memiliki dampak terbesar pada hasil akhir - besarnya gaya gravitasi - oleh karena itu, hanya kesalahan yang sesuai yang harus diperhitungkan.

Sedangkan untuk gambar yang lebih besar, Anda dapat menggunakan koordinat berbobot presisi ganda atau menambahkan satu tingkat diskritisasi lagi: bagi gambar asli menjadi beberapa bagian dan baca gambar integral secara terpisah untuk masing-masing bagian ini. Dari sudut pandang kompleksitas komputasi, jika lebih dari satu gambar integral digunakan untuk menghitung jumlah elemen suatu daerah, tetapi "lebih dari satu" ini adalah konstan, kompleksitas algoritma perhitungan jumlah tidak berubah.

Kesimpulan


Contoh penggunaan gambar terintegrasi di atas mungkin dapat diadaptasi untuk mengembangkan algoritma optimal O (1) untuk pengambilan sampel berdasarkan kepentingan (pentingnya pengambilan sampel). Yang ada - dan sangat intensif sumber daya dari sudut pandang GPU - algoritma memiliki kompleksitas linier O (N) dan menemukan aplikasi dalam metode modern pencahayaan global [22, 23] .

Secara umum, menurut pendapat saya, gambar terintegrasi adalah salah satu algoritma yang paling diremehkan. Mereka dapat menjadi alternatif yang sangat baik untuk memetakan dan memfilter anisotrop pada saat yang sama, dan dengan mempertimbangkan bagaimana yang terakhir diimplementasikan pada GPU [24, 25] , sangat mungkin bahwa mereka sudah menjadi ukuran yang lebih efektif.

Referensi


Lihat daftar
  1. en.wikipedia.org/wiki/N-body_problem
  2. en.wikipedia.org/wiki/List_of_Solar_System_objects_by_size
  3. en.wikipedia.org/wiki/Near-Earth_object
  4. en.wikipedia.org/wiki/Asteroid
  5. en.wikipedia.org/wiki/Trojan_(celestial_body)
  6. en.wikipedia.org/wiki/Kuiper_belt
  7. en.wikipedia.org/wiki/Oort_cloud
  8. en.wikipedia.org/wiki/Computer_performance_by_orders_of_magnitude
  9. en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation
  10. link.springer.com/chapter/10.1007/978-1-4612-1252-2_10
  11. www.researchgate.net/publication/281362507_Grid-Based_Hydrodynamics_in_Astrophysical_Fluid_Flows
  12. en.wikipedia.org/wiki/Multigrid_method
  13. en.wikipedia.org/wiki/Multipole_expansion
  14. math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf
  15. en.wikipedia.org/wiki/Summed-area_table
  16. www.florian-oeser.de/wordpress/wp-content/2012/10/crow-1984.pdf
  17. www.nmr.mgh.harvard.edu/~berkin/Bilgic_2010_Integral_Image.pdf
  18. en.wikipedia.org/wiki/Gaussian_blur
  19. en.wikipedia.org/wiki/Distance_transform
  20. staffhome.ecm.uwa.edu.au/~00082689/papers/Shafait-efficient-binarization-SPIE08.pdf
  21. en.wikipedia.org/wiki/Truncation_error
  22. t.co/Muf6I3yq71?amp=1
  23. developer.nvidia.com/gpugems/gpugems3/part-iii-rendering/chapter-20-gpu-based-importance-sampling
  24. en.wikipedia.org/wiki/Mipmap
  25. en.wikipedia.org/wiki/Anisotropic_filtering

More articles:


All Articles