Transformasi Kuantisasi Rata-rata Berturut-turut yang Dioptimalkan

Algoritma Successive Mean Quantization Transform (SMQT) adalah transformasi non-linier yang mengungkapkan organisasi atau struktur data dan menghilangkan properti seperti gain dan bias. Dalam makalah berjudul The Successive Mean Quantization Transform, SMQT “diterapkan dalam pemrosesan ucapan dan pemrosesan gambar”. Algoritme ketika diterapkan pada gambar "dapat dilihat sebagai fokus progresif pada detail dalam gambar".

Menurut makalah lain berjudul Operator Pemetaan Nada Berbasis SMQT untuk Gambar Rentang Dinamis Tinggi, itu akan menghasilkan "gambar dengan detail yang disempurnakan". Makalah ini menjelaskan dua teknik penerapan transformasi ini ke gambar.

1. Terapkan SMQT pada pencahayaan setiap piksel - ini menjelaskan rumus untuk mendapatkan pencahayaan dari RGB setiap piksel.

2. Terapkan SMQT pada setiap saluran RGB secara terpisah - untuk saluran R, G, dan B satu per satu.

Gambar berikut menunjukkan hasil dari kedua teknik tersebut:

Dengan menerapkan teknik kedua pada gambar Bruin Theater di malam hari, kita dapat melihat bagaimana algoritme semakin memperbesar detail gambar dan mengungkapkan detail yang awalnya tersembunyi oleh kegelapan:

Pada artikel ini, kita akan melihat lebih dekat cara kerja algoritme ini, dan menjelajahi pengoptimalan sederhana yang memungkinkan algoritme menjadi jauh lebih berperforma dalam aplikasi pemrosesan gambar praktis.

Algoritma SMQT

Dalam makalah asli, algoritma dijelaskan secara abstrak. Untuk lebih memahami SMQT, kita akan membahas beberapa contoh sederhana.

Misalkan kita memiliki vektor berikut (Anda dapat menganggapnya seperti array):

Dalam kasus gambar berwarna, kita dapat menganggapnya sebagai tiga vektor terpisah, masing-masing mewakili saluran warna tertentu (RGB), dan setiap elemen vektor mewakili intensitas piksel yang sesuai.

Langkah-langkah yang terlibat dalam penerapan algoritma SMQT adalah:

1. Hitung mean dari vektor, yang dalam hal ini adalah 29,58.

2. Bagi vektor menjadi dua, sisakan angka yang kurang atau sama dengan 29,58 di bagian kiri, dan angka yang lebih besar di bagian kanan:

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   Baris kedua adalah kode yang akan kita buat untuk setiap nilai. Nilai yang lebih rendah dari atau sama dengan 29,58 mendapatkan 0 dalam kodenya, dan angka yang lebih besar dari 29,58 mendapatkan 1 (ini biner).

3. Sekarang kedua vektor yang dihasilkan dibagi secara individual, dengan cara rekursif, mengikuti aturan yang sama. Dalam contoh kita, mean dari vektor pertama adalah (15 + 4 + 0 + 5 + 18) / 5 = 8.4, dan mean dari vektor kedua adalah (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48,7. Masing-masing dari dua vektor tersebut selanjutnya dipecah menjadi dua vektor lagi, dan sedikit kode kedua ditambahkan ke masing-masing tergantung pada perbandingannya dengan rata-rata. Ini adalah hasilnya:

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   Perhatikan bahwa 0 lagi ditambahkan untuk angka yang lebih rendah dari atau sama dengan rata-rata (untuk setiap vektor) dan 1 untuk angka yang lebih besar dari rata-rata.

4. Algoritma ini diulang secara rekursif:

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10000	10010	10100	11000	11100	11101	11110

   Pada titik ini setiap vektor hanya memiliki satu elemen. Jadi untuk setiap langkah berturut-turut a 0 akan ditambahkan, karena jumlahnya akan selalu sama dengan dirinya sendiri (kondisi untuk a 0 adalah bahwa angka tersebut harus lebih kecil atau sama dengan rata-rata, yang adalah dirinya sendiri).

Sejauh ini kita memiliki tingkat kuantisasi L=5. Jika kita akan menggunakan L=8, kita harus menambahkan tiga 0 untuk setiap kode. Hasil konversi setiap kode dari biner ke integer (untuk L=8) adalah:

Vektor terakhir diurutkan dalam urutan yang meningkat. Untuk mendapatkan vektor keluaran, kita harus mensubstitusi nilai asli vektor masukan dengan kodenya.

Perhatikan bahwa dalam vektor yang dihasilkan:

• Keuntungan telah dihapus. Yang asli memiliki gain yang rendah, dengan rentang dari 0 hingga 64. Sekarang penguatannya dari 0 hingga 240, yang hampir merupakan keseluruhan rentang 8 bit. Dikatakan bahwa gain dihilangkan karena tidak masalah jika kita mengalikan semua elemen dari vektor asli dengan angka, seperti 2, atau jika kita membagi semuanya dengan 2, vektor output akan menjadi hampir sama. Jangkauannya akan menjadi sekitar seluruh jangkauan vektor tujuan (8 bit untuk L=8). Jika kita mengalikan vektor input dengan dua, vektor output sebenarnya akan sama, karena pada setiap langkah angka yang sama yang berada di bawah atau di atas mean akan terus berada di bawah atau di atasnya, dan kita akan menambahkan 0s atau 1s yang sama ke keluaran. Hanya jika kita membaginya maka hasilnya akan hampir sama, dan tidak persis sama, karena angka ganjil seperti 15 harus dibulatkan dan perhitungannya mungkin berbeda. Kami beralih dari gambar gelap ke gambar dengan pikselnya mulai dari warna gelap (0) hingga warna yang lebih terang (240), menggunakan seluruh rentang.
• Bias dihilangkan, meskipun kita tidak dapat mengamatinya dalam contoh ini. Ini karena kita tidak memiliki bias karena nilai terendah kita adalah 0. Jika kita benar-benar memiliki bias, itu akan dihilangkan. Jika kita mengambil angka 'K' dan menambahkannya ke setiap elemen dari vektor input, perhitungan angka di atas dan di bawah rata-rata pada setiap langkah tidak akan berbeda. Outputnya akan tetap sama. Ini juga akan membuat gambar yang terlalu terang menjadi gambar yang berkisar dari warna gelap hingga terang.
• Kami memiliki gambar dengan detail yang disempurnakan. Perhatikan bagaimana untuk setiap langkah rekursif yang kami ambil, kami sebenarnya memperbesar detailnya, dan membangun output dengan mengungkapkan detail tersebut sebanyak mungkin. Dan karena kami akan menerapkan teknik ini ke setiap saluran RGB, kami akan mengungkapkan detail sebanyak mungkin, meskipun kehilangan informasi tentang nada asli dari setiap warna.

Diberikan gambar seperti vektor piksel RGB, dengan setiap titik menjadi 8 bit untuk R, 8 untuk G, dan 8 untuk B; kita dapat mengekstrak tiga vektor darinya, satu untuk setiap warna, dan menerapkan algoritme ke setiap vektor. Kemudian kita membentuk vektor RGB lagi dari ketiga vektor keluaran tersebut dan kita memiliki gambar yang diproses SMQT, seperti yang dilakukan dengan salah satu Teater Bruin.

Kompleksitas

Algoritme mensyaratkan bahwa untuk setiap level kuantisasi (L), N elemen harus diperiksa pada lintasan pertama untuk menemukan mean untuk setiap vektor, dan kemudian pada lintasan kedua, masing-masing elemen N tersebut harus dibandingkan dengan mean yang sesuai dalam untuk membagi setiap vektor secara bergantian. Akhirnya, elemen N harus diganti dengan kodenya. Oleh karena itu kompleksitas algoritmanya adalah O((L*2*N) + N) = O((2*L + 1)*N), yaitu O(L*N).

Grafik yang diekstraksi dari kertas konsisten dengan kompleksitas O(L*N). Semakin rendah L, semakin cepat pemrosesan dengan cara yang kira-kira linier (jumlah frame per detik yang lebih besar). Untuk meningkatkan kecepatan pemrosesan, makalah ini menyarankan untuk menurunkan nilai L: “memilih level L yang lebih rendah dapat menjadi cara langsung untuk mengurangi kecepatan pemrosesan tetapi dengan mengurangi kualitas gambar”.

Peningkatan

Di sini kita akan menemukan cara untuk meningkatkan kecepatan tanpa mengurangi kualitas gambar. kami akan menganalisis proses transformasi dan menemukan algoritma yang lebih cepat. Untuk mendapatkan perspektif yang lebih lengkap tentang ini, mari kita lihat contoh dengan angka berulang:

Vektor tidak dapat dibagi lagi, dan nol harus ditambahkan sampai kita mendapatkan L yang diinginkan.

Demi kesederhanaan, anggaplah input dapat berubah dari 0 hingga 31, dan output dari 0 hingga 7 (L=3), seperti yang dapat dilihat pada contoh.

Perhatikan bahwa menghitung rata-rata vektor pertama (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 memberikan hasil yang sama dengan menghitung rata-rata seluruh vektor terakhir, karena hanya vektor yang sama dengan elemen dalam urutan yang berbeda: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

Pada langkah kedua kita harus menghitung setiap vektor secara rekursif. Jadi kami menghitung rata-rata dari input berwarna abu-abu, yang merupakan 6 elemen pertama ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8), dan rata-rata dari input kosong, yang merupakan 4 elemen terakhir ((25 + 31 + 31 + 25) / 4 = 28):

Perhatikan lagi bahwa jika kita menggunakan vektor terakhir, yang terurut sepenuhnya, hasilnya sama. Untuk 6 elemen pertama kita memiliki: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8), dan untuk 4 elemen terakhir: ((25 + 25 + 31 + 31) / 4 = 28) . Karena itu hanya tambahan, urutan summand tidak menjadi masalah.

Hal yang sama berlaku untuk langkah selanjutnya:

Perhitungannya sama dengan vektor terakhir: ((7 + 1 + 1 + 7) / 4 = 4) akan sama dengan ((1 + 1 + 7 + 7) / 4 = 4).

Dan hal yang sama akan berlaku untuk vektor dan langkah lainnya.

Perhitungan rata-rata hanyalah jumlah nilai elemen dalam interval, dibagi dengan jumlah elemen dalam interval. Ini berarti bahwa kita dapat menghitung terlebih dahulu semua nilai tersebut dan menghindari pengulangan perhitungan ini sebanyak L kali.

Mari kita lihat langkah-langkah untuk menerapkan apa yang akan kita sebut algoritma FastSMQT ke contoh kita:

1. Buat tabel dengan 32 kolom dan 3 baris seperti yang Anda lihat di bawah ini. Baris pertama dalam tabel mewakili indeks tabel (0 hingga 31) dan tidak perlu disertakan saat mengkode tabel. Tapi itu secara eksplisit ditampilkan untuk membuat contoh lebih mudah diikuti.

2. Ulangi elemen N sekali menghitung frekuensi setiap nilai. Dalam contoh kita, elemen 1, 7, 16, 25 dan 31 semuanya memiliki frekuensi 2. Semua elemen lainnya memiliki frekuensi 0. Langkah ini memiliki kompleksitas O(N).

3. Sekarang setelah vektor frekuensi terisi, kita perlu mengulangi vektor itu (vektor frekuensi, bukan vektor input). Kami tidak mengulangi elemen N lagi, tetapi R (R berada dalam kisaran: 2^L), yang dalam hal ini adalah 32 (0 hingga 31). Saat memproses piksel, N bisa menjadi jutaan (megapiksel), tetapi R biasanya 256 (satu vektor untuk setiap warna). Dalam contoh kita ini adalah 32. Kita akan mengisi dua baris tabel berikut secara bersamaan. Baris pertama (baris kedua) akan memiliki jumlah frekuensi sejauh ini. Yang kedua (ketiga dari tabel) akan memiliki jumlah nilai semua elemen yang muncul sejauh ini.

   Dalam contoh kami, ketika kami mendapatkan 1, kami menempatkan 2 di baris kedua tabel karena dua 1 telah muncul sejauh ini. Dan kami juga menempatkan 2 di baris ketiga tabel, karena 1 + 1 = 2. Kami terus menulis dua nilai itu pada masing-masing posisi berikutnya sampai kami mendapatkan 7. Karena angka 7 muncul dua kali, kami menambahkan 2 ke akumulator baris kedua, karena sekarang 4 angka muncul sejauh ini (1, 1, 7, 7). Dan kami menambahkan 7 + 7 = 14 ke baris ketiga, menghasilkan 2 + 14 = 16, karena 1 + 1 + 7 + 7 = 16. Kami melanjutkan algoritma ini sampai kami menyelesaikan iterasi elemen-elemen tersebut. Kompleksitas langkah ini adalah O(2^L), yang dalam kasus kami adalah O(32), dan saat bekerja dengan piksel RGB, itu adalah O(256).

   saya	0	1	2	...	6	7	8	...	15	16	17	...	24	25	26	...	30	31
   n	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   n-kumulatif	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   jumlah	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. Langkah selanjutnya adalah menghapus dari tabel kolom dengan elemen yang memiliki frekuensi 0, dan untuk melihat contoh lebih jelas, kami juga akan menghapus baris kedua karena tidak relevan lagi, seperti yang akan Anda lihat.

   saya	1	7	16	25	31
   n	2	4	6	8	10
   jumlah	2	16	48	98	160

5. Ingatlah bahwa kita dapat menggunakan vektor terakhir (terurut lengkap) untuk melakukan perhitungan untuk setiap langkah dan hasilnya akan tetap sama. Perhatikan bahwa di sini, dalam tabel ini, kita memiliki vektor terakhir dengan semua pra-perhitungan yang telah dibuat.

   Pada dasarnya kita perlu melakukan algoritma SMQT pada vektor kecil ini, tetapi tidak seperti melakukannya pada vektor asli yang kita mulai, yang ini akan jauh lebih mudah.

   Pertama kita perlu menghitung rata-rata dari semua sampel. Kita dapat menemukannya dengan mudah dengan: sum[31] / n[31] = 160 / 10 = 16. Jadi kita membagi tabel menjadi dua vektor, dan mulai menulis kode biner untuk masing-masing vektor:

   saya	1	7	16	25	31
   n	2	4	6	8	10
   jumlah	2	16	48	98	160
   kode	0	0	0	1	1

   Sekarang kita membagi setiap vektor lagi. Rerata dari vektor pertama adalah: sum[16] / n[16] = 48 / 6 = 8. Dan mean dari vektor kedua adalah: (jumlah[31] – jumlah[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   saya	1	7	16	25	31
   n	2	4	6	8	10
   jumlah	2	16	48	98	160
   kode	00	00	01	10	11

   Hanya ada satu vektor yang tersisa untuk dibagi. Rata-ratanya adalah: jumlah[7] / n[7] = 16/4 = 4.

   saya	1	7	16	25	31
   n	2	4	6	8	10
   jumlah	2	16	48	98	160
   kode	000	001	010	100	110

   Seperti yang Anda lihat, kode untuk setiap elemen sama jika kita mengikuti algoritma aslinya. Dan kami melakukan SMQT pada vektor yang jauh lebih kecil daripada vektor dengan elemen N dan kami juga telah menghitung sebelumnya semua nilai yang kami butuhkan untuk menemukan mean, jadi menghitung vektor yang dihasilkan sangatlah mudah dan cepat.

   Kompleksitas langkah ini adalah O(L*(2^L)), yang untuk L=8, dan dalam kebutuhan pemrosesan gambar praktis, adalah O(8*(256)) = O(2048) = konstan.

6. Langkah terakhir adalah mengulangi N elemen sekali lagi dengan mengganti elemen dengan kodenya untuk setiap elemen: elemen[i] = kode[i]. Kompleksitasnya adalah O(N). Kompleksitas FastSMQT adalah O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

Paralelisme

Kedua algoritme dapat diparalelkan, meskipun lebih efisien untuk menjalankan satu algoritme per inti daripada jika banyak vektor harus diubah. Misalnya, saat memproses gambar, kami dapat memproses setiap saluran RGB di inti yang berbeda alih-alih memparalelkan masing-masing dari ketiga perhitungan tersebut.

Untuk memparalelkan algoritma SMQT, ketika kita membagi sebuah vektor menjadi dua, kita dapat memproses setiap sub-vektor dalam sebuah inti baru jika sebuah inti tersedia (sebenarnya satu sub vektor di inti saat ini dan yang lainnya di inti baru). Ini dapat dilakukan secara rekursif sampai kita mencapai jumlah total inti yang tersedia. Penggantian nilai dengan kode juga dapat dilakukan secara paralel untuk.

Algoritma FastSMQT juga dapat diparalelkan. Pada langkah pertama, vektor input harus dibagi menjadi jumlah core yang tersedia (C). Satu vektor penghitungan frekuensi harus dibuat untuk masing-masing bagian tersebut, dan diisi secara paralel. Kemudian kita tambahkan nilai-nilai vektor tersebut ke dalam satu vektor frekuensi yang dihasilkan. Langkah selanjutnya yang dapat diparalelkan adalah yang terakhir, ketika kita mensubstitusi nilai-nilai tersebut dengan kode-kodenya. Hal ini dapat dilakukan secara paralel untuk.

Perbandingan Kompleksitas

Kompleksitas total dari algoritma SMQT asli adalah O((2*L + 1)*N), yaitu O(L*N).

Kompleksitas FastSMQT adalah O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

Mengingat L tetap, kompleksitas menjadi hanya O(N) untuk keduanya. Tetapi konstanta yang mengalikan N jauh lebih kecil untuk FastSMQT, dan itu membuat perbedaan besar dalam waktu pemrosesan seperti yang akan kita lihat.

Grafik berikut membandingkan kinerja algoritma SMQT dan FastSMQT untuk L=8, yang merupakan kasus untuk pemrosesan gambar. Grafik menunjukkan waktu (dalam milidetik) yang diperlukan untuk memproses N elemen. Perhatikan bahwa kompleksitas (dengan konstanta) SMQT untuk L=8 adalah O(17*N), sedangkan untuk FastSMQT adalah O(2*N + 2304).

Semakin besar N, semakin lama waktu yang dibutuhkan SMQT untuk memproses gambar. Untuk FastSMQT di sisi lain, pertumbuhannya jauh lebih lambat.

Untuk nilai N yang lebih besar, perbedaan kinerja jauh lebih jelas:

Di sini SMQT membutuhkan waktu hingga beberapa detik untuk memproses gambar tertentu, sementara FastSMQT masih berada dalam zona "beberapa milidetik".

Bahkan dengan banyak inti (dua, dalam hal ini), FastSMQT jelas masih lebih unggul daripada hanya SMQT:

FastSMQT tidak bergantung pada L. SMQT, sebaliknya, bergantung secara linier pada nilai L. Misalnya, dengan N = 67108864, runtime SMQT meningkat dengan meningkatnya nilai L, sedangkan FastSMQT tidak:

Kesimpulan

Tidak semua teknik pengoptimalan dapat diterapkan untuk semua algoritme, dan kunci untuk meningkatkan kinerja algoritme sering kali tersembunyi dalam beberapa wawasan tentang cara kerja algoritme. Algoritma FastSMQT ini memanfaatkan kemungkinan nilai pra-perhitungan dan sifat perhitungan rata-rata. Akibatnya memungkinkan pemrosesan lebih cepat daripada SMQT asli. Kecepatan tidak terpengaruh oleh peningkatan L, meskipun L tidak dapat lebih besar dari 8 biasa karena penggunaan memori adalah 2^L, yang untuk 8 adalah 256 yang dapat diterima (jumlah kolom dalam tabel frekuensi kami), tetapi peningkatan kinerja memiliki manfaat praktis yang jelas.

Peningkatan kecepatan ini memungkinkan MiddleMatter untuk menerapkan algoritme dalam aplikasi iOS (dan aplikasi Android) yang meningkatkan gambar dan video yang diambil dalam kondisi kurang cahaya. Dengan peningkatan ini, dimungkinkan untuk melakukan pemrosesan video dalam aplikasi, yang jika tidak, akan terlalu lambat untuk perangkat iOS.

Kode C++ untuk algoritma SMQT dan FastSMQT tersedia di GitHub.