Deskripsi algoritma • Mengukur error reduksi warna

Dokumen ini menjelaskan cara ImageMagick melakukan reduksi warna pada gambar. Untuk memahami penjelasan berikut secara utuh, Anda memerlukan pengetahuan dasar mengenai teknik pemrosesan gambar serta struktur data pohon dan terminologinya.

Deskripsi algoritma

Untuk keperluan alokasi warna, gambar adalah himpunan n piksel, dengan setiap piksel merupakan titik dalam ruang RGB. Ruang RGB adalah ruang vektor 3 dimensi, dan setiap piksel p(i) didefinisikan oleh tripel terurut koordinat merah, hijau, dan biru, (r(i), g(i), b(i)).

Setiap komponen warna primer (merah, hijau, atau biru) merepresentasikan intensitas yang bervariasi secara linear dari 0 hingga nilai maksimum, Cmax, yang berkorespondensi dengan saturasi penuh warna tersebut. Alokasi warna didefinisikan pada ranah yang terdiri dari kubus dalam ruang RGB dengan titik sudut yang berlawanan di (0, 0, 0) dan (Cmax, Cmax, Cmax). ImageMagick mensyaratkan Cmax= 255.

Algoritma memetakan ranah ini ke pohon yang setiap simpulnya merepresentasikan kubus di dalam ranah tersebut. Pada pembahasan berikut, kubus-kubus ini didefinisikan oleh koordinat dua titik sudut yang berlawanan: titik sudut yang paling dekat dengan titik asal dalam ruang RGB, dan titik sudut yang paling jauh dari titik asal.

Simpul akar pohon merepresentasikan seluruh ranah, dari (0,0,0) hingga (Cmax, Cmax, Cmax). Setiap tingkat yang lebih rendah dalam pohon dihasilkan dengan membagi kubus suatu simpul menjadi delapan kubus lebih kecil berukuran sama. Hal ini berkorespondensi dengan membelah kubus induk menjadi dua menggunakan bidang yang melewati titik tengah setiap rusuk.

Algoritma dasar beroperasi dalam tiga fase:

1. Klasifikasi
2. Reduksi
3. Penetapan

Klasifikasi

Klasifikasi membangun pohon deskripsi warna untuk gambar tersebut. Reduksi menciutkan pohon hingga jumlah warna yang direpresentasikannya, paling banyak, sama dengan jumlah warna yang diinginkan pada gambar output. Penetapan mendefinisikan peta warna gambar output dan menetapkan warna setiap piksel melalui klasifikasi ulang pada pohon yang telah direduksi. Tujuan kami adalah meminimalkan selisih numerik antara warna asli dan warna hasil kuantisasi. Untuk mempelajari lebih lanjut tentang error kuantisasi, lihat Mengukur error reduksi warna.

Klasifikasi dimulai dengan menginisialisasi pohon deskripsi warna dengan kedalaman yang cukup untuk merepresentasikan setiap kemungkinan warna input dalam satu daun. Namun, untuk nilai Cmax yang realistis, tidak praktis untuk menghasilkan pohon deskripsi warna yang terbentuk penuh pada fase klasifikasi. Jika komponen warna pada gambar input dikuantisasi ke presisi k-bit, sehingga Cmax = 2^k-1, pohon memerlukan k tingkat di bawah simpul akar agar setiap kemungkinan warna input dapat direpresentasikan dalam satu daun. Hal ini menjadi tidak terjangkau karena jumlah total simpul pohon adalah:

total nodes = 1+Sum(8^i), i=1,k

For k=8,
nodes = 1 + (8^1+8^2+....+8^8)
      = 1 + 8(8^8 - 1)/(8 - 1)
      = 19,173,961

Oleh karena itu, untuk menghindari pembuatan pohon yang terisi penuh, ImageMagick:

1. menginisialisasi struktur data untuk simpul hanya saat diperlukan;

2. memilih kedalaman maksimum pohon sebagai fungsi dari jumlah warna yang diinginkan pada gambar output (saat ini logaritma basis dua dari Cmax).

   For Cmax=255, maximum tree depth = log2(256) = 8

Pohon dengan kedalaman ini umumnya memungkinkan representasi terbaik dari gambar sumber dengan kecepatan komputasi tercepat dan penggunaan memori paling sedikit. Namun, kedalaman default tidak sesuai untuk sejumlah gambar. Oleh karena itu, pemanggil dapat meminta kedalaman pohon tertentu.

Untuk setiap piksel pada gambar input, klasifikasi menelusuri ke bawah dari akar pohon deskripsi warna. Pada setiap tingkat pohon, klasifikasi mengidentifikasi satu simpul yang merepresentasikan kubus dalam ruang RGB yang berisi warna piksel tersebut. Klasifikasi memperbarui data berikut untuk setiap simpul tersebut:

n1

jumlah piksel yang warnanya terdapat dalam kubus RGB yang direpresentasikan oleh simpul ini;

n2

jumlah piksel yang warnanya tidak direpresentasikan oleh simpul pada kedalaman yang lebih rendah dalam pohon; pada awalnya, n2=0 untuk semua simpul kecuali daun pohon.

Sr,Sg,Sb

jumlah nilai komponen merah, hijau, dan biru untuk semua piksel yang tidak diklasifikasikan pada kedalaman yang lebih rendah. Kombinasi jumlah ini dengan n2 pada akhirnya akan menentukan warna rata-rata dari sekumpulan piksel yang direpresentasikan oleh simpul ini.

E

kuadrat jarak dalam ruang RGB antara setiap piksel yang terkandung dalam suatu simpul dan pusat simpul tersebut. Ini merepresentasikan error kuantisasi untuk simpul tersebut.

Reduksi

Reduksi memangkas pohon secara berulang hingga jumlah simpul dengan n2 > 0 kurang dari atau sama dengan jumlah maksimum warna yang diizinkan pada gambar output. Pada setiap iterasi pada pohon, reduksi memilih simpul-simpul dengan nilai E minimal untuk dipangkas dan menggabungkan statistik warnanya ke atas. Reduksi menggunakan ambang batas pemangkasan (threshold), Ep, untuk mengatur pemilihan simpul sebagai berikut:

Ep = 0
while number of nodes with (n2 > 0) > required maximum number of colors
   prune all nodes such that E <= Ep
   Set Ep  to minimum E in remaining nodes

Hal ini memiliki efek meminimalkan error kuantisasi saat menggabungkan dua simpul.

Ketika simpul yang akan dipangkas memiliki turunan, prosedur pemangkasan memanggil dirinya sendiri secara rekursif untuk memangkas pohon dari daun ke atas. Nilai n2, Sr, Sg, dan Sb pada simpul yang dipangkas selalu ditambahkan ke data yang bersesuaian pada simpul induknya. Hal ini mempertahankan karakteristik warna simpul yang dipangkas untuk perataan berikutnya.

Untuk setiap simpul, terdapat n2 piksel yang warnanya berada dalam volume terkecil di ruang RGB yang direpresentasikan oleh simpul tersebut. Ketika n2 > 0, simpul tersebut akan secara unik mendefinisikan satu warna pada gambar output. Pada awal reduksi, n2 = 0 untuk semua simpul kecuali daun pohon yang merepresentasikan warna yang ada pada gambar input.

Hitungan piksel lainnya, n1, menunjukkan jumlah total warna dalam volume kubik yang direpresentasikan oleh simpul tersebut. Ini mencakup n1 - n2 piksel yang warnanya harus didefinisikan oleh simpul pada tingkat yang lebih rendah dalam pohon.

Penetapan

Penetapan menghasilkan gambar output dari pohon yang telah dipangkas. Gambar output terdiri dari dua bagian:

1. Peta warna, yaitu sebuah array deskripsi warna (tripel RGB) untuk setiap warna yang ada pada gambar output.
2. Array piksel, yang merepresentasikan setiap piksel sebagai indeks ke dalam array peta warna.

Pertama, fase penetapan melakukan satu kali pemindaian atas pohon deskripsi warna yang telah dipangkas untuk membentuk peta warna gambar. Untuk setiap simpul dengan n2 > 0, fase ini membagi Sr, Sg, dan Sb dengan n2. Hal ini menghasilkan warna rata-rata dari semua piksel yang diklasifikasikan tidak lebih rendah dari simpul ini. Setiap warna tersebut menjadi satu entri pada peta warna.

Terakhir, fase penetapan mengklasifikasikan ulang setiap piksel dalam pohon yang telah dipangkas untuk mengidentifikasi simpul terdalam yang berisi warna piksel tersebut. Nilai piksel dalam array piksel menjadi indeks warna rata-rata simpul ini pada peta warna.

Bukti empiris menunjukkan bahwa jarak dalam ruang warna seperti YUV atau YIQ berkorespondensi lebih dekat dengan perbedaan warna secara perseptual dibandingkan jarak dalam ruang RGB. Ruang warna ini dapat memberikan hasil yang lebih baik saat mereduksi warna gambar. Di sini algoritma bekerja seperti yang dijelaskan sebelumnya, kecuali setiap piksel merupakan titik dalam ruang warna alternatif tersebut. Untuk kemudahan, komponen warna dinormalisasi ke rentang 0 hingga nilai maksimum, Cmax. Reduksi warna kemudian dapat dilakukan seperti yang dijelaskan.

Mengukur error reduksi warna

Tergantung pada gambar, error reduksi warna dapat terlihat jelas atau tidak sama sekali. Gambar dengan frekuensi spasial tinggi (seperti rambut atau rumput) akan menunjukkan error yang jauh lebih sedikit dibandingkan gambar dengan area luas yang bergradasi halus (seperti wajah). Ini karena tepi (edge) kontur berfrekuensi tinggi yang muncul akibat proses reduksi warna tersamarkan oleh frekuensi tinggi pada gambar (Catatan penerjemah: naskah asli tertulis "This because", seharusnya "This is because").

Untuk mengukur perbedaan antara gambar asli dan gambar yang telah direduksi warnanya (total error reduksi warna), ImageMagick menjumlahkan, untuk semua piksel pada gambar, kuadrat jarak dalam ruang RGB antara setiap nilai piksel asli dan nilai piksel hasil reduksi warnanya. ImageMagick mencetak beberapa pengukuran error, termasuk error rata-rata per piksel, error rata-rata ternormalisasi, dan error maksimum ternormalisasi.

Pengukuran error ternormalisasi dapat digunakan untuk membandingkan gambar. Secara umum, semakin dekat error rata-rata ke nol, semakin mirip gambar hasil kuantisasi dengan gambar sumber. Idealnya, error harus berbasis persepsi, karena mata manusia adalah penentu akhir kualitas kuantisasi.

Error ini diukur dan dicetak ketika opsi -colors dan -verbose ditentukan pada baris perintah magick: