Berbagi pengetahuan, dari mana saja, dari siapa saja, untuk semua

Matematika dan Kompresi Gambar Digital

Andi memiliki kamera digital single lens reflex (DSLR) model terbaru. Ia mengambil foto ikan mainan seperti pada gambar.

Contoh gambar mentah keluaran dari kamera DSLR.

Contoh gambar mentah keluaran dari kamera DSLR.

Dalam format tidak terkompres (raw format), gambar ini memiliki tinggi 512 pixel dan lebar 768 pixel. Total pixel yang dibutuhkan adalah 512 x 768 = 393.216. Gambar digital disimpan ke dalam tiga kanal warna, yaitu merah, hijau, dan biru (RGB) sehingga total dibutuhkan 393.216 x 3 = 1.179.648 byte atau lebih dari 1 MB.

Jika Andi ingin mengunggah (upload) foto tersebut ke Facebook, secara otomatis server Facebook memperkecil ukuran foto untuk menghemat pemakaian harddisk pada server mereka dan untuk mempercepat komunikasi data. Metode kompresi JPEG (Joint Photographic Expert Group) merupakan salah satu contoh bentuk kompresi yang populer yang kita kenal. Dengan menggunakan kompresi JPEG, kita bisa memperoleh gambar dengan ukuran hanya 80 kB, atau hanya 7% dari kebutuhan memori pada raw format.

Contoh gambar terkompresi dalam format JPEG.

Contoh gambar terkompresi dalam format JPEG.

Dapatkah kalian menunjukkan perbedaan gambar pada raw format dan JPEG? Bagaimanakah prinsip kerja kompresi JPEG tersebut? Mari kita pelajari sekilas tentang ini.

Representasi basis dua

Gambar yang muncul di layar monitor komputer terbagi atas sejumlah pixel. Pixel adalah suatu blok terkecil yang menyusun gambar. Perhatikan gambar grayscale suatu rumah yang memiliki ukuran pixel baris 512 x kolom 768.

Gambar grayscale ini memiliki ukuran pixel baris 512 x kolom 768.

Gambar grayscale ini memiliki ukuran pixel baris 512 x kolom 768.

Untuk menghasilkan gambar tersebut, komputer mendeteksi tingkat kehitaman warna dengan skala 0 (hitam) – 255 (putih).

Ed44-matematika-4

Jika kita perbesar gambar grayscale tersebut sampai batas maksimumnya, kita  dapat melihat blok-blok pixel yang menyusun gambar.

Blok-blok pixel penyusun gambar.

Blok-blok pixel penyusun gambar.

Setiap warna pada blok pixel penyusun gambar merupakan hasil konversi dari angka-angka pada skala grayscale yang bernilai 0-255 seperti ditunjukkan tabel berikut ini.

150 154 160 157 106 140 147 142 141 147 132 150 171 117 136
144 159 125 121 157 143 132 136 153 138 155 164 169 162 152
190 175 169 155 161 136 152 158 141 162 147 153 161 168 169
185 203 139 161 151 159 145 167 179 167 150 155 165 159 158
151 153 163 152 160 152 164 131 131 51 124 152 154 145 143
164 162 158 167 157 164 166 139 132 138 119 148 154 139 146
147 148 143 155 169 160 152 161 159 143 138 163 132 152 146
66 129 163 165 163 161 154 157 167 162 174 153 156 151 156
162 173 172 161 158 158 159 167 171 169 164 159 158 159 162
163 164 161 155 155 158 161 167 171 168 162 162 163 164 166
167 167 165 163 160 160 164 166 169 168 164 163 165 167 170
172 171 170 170 166 163 166 170 169 168 167 165 163 163 160
173 172 170 169 166 163 167 169 170 170 170 165 160 157 148
167 168 165 173 173 172 167 170 170 171 171 169 162 163 162
200 198 189 196 191 188 163 168 172 177 177 186 180 180 188

Dalam pemrosesan data di komputer, angka-angka tersebut diubah ke dalam sistem bilangan basis dua (biner) dengan satuan yang disebut bit. Satu bit memiliki nilai antara satu atau nol. Satu byte adalah satu unit penyimpanan di komputer yang berisi 8 bit. Jika setiap bit dapat mengisi dua data, antara 0 atau 1, dalam 1 byte kita dapat menyimpan sebanyak 28 = 256 nilai yang mungkin. Misalkan angka 125 dalam desimal dapat dituliskan ke dalam basis biner menjadi

125 = 64 + 32 + 16 + 8 + 4 + 1
= 0 x 128 + 1 x 64 + 1 x 32 + 1 x 16 + 1 x 8 + 1 x 4 + 0 x 2 + 1 x 1
= 0 x 27 + 1 x 26 + 1 x 25 + 1 x 24 + 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20
= 011111012

Kode Huffman dan Algoritma Huffman

Ide untuk mengompres data berasal dari David Huffman, yaitu dengan mengganti representasi biner berdasarkan frekuensi kemunculan. Misalkan kita ingin menyumpan data “sassafras”, bila kita simpan karakter dalam bentuk ASCII, representasi biner akan seperti pada tabel berikut.

Huruf ASCII Biner Kemunculan Frekuensi Relatif
s 115 01110011 4 kali 4/9
a 97 01100001 3 kali 1/3
f 102 01100110 1 kali 1/9
r 114 01110010 1 kali 1/9

Kata “sassafras” tersusun atas 9 karakter sehingga total kita membutuhkan 9 x 8= 72 bit memori. Kita dapat mengompres data tersebut sesuai dengan algoritma Huffman.

  1. Urutkan karakter dari frekuensi relatif terkecil ke yang terbesar.Ed44-matematika-6
  1. Dua karakter terendah, yaitu f dan r dijumlahkan, untuk membentuk parent baru, yang bernilai 0,22, dan membuat f dan r sebagai children.Ed44-matematika-7
  1. Mengulang langkah ke-2 untuk karakter a dan parent 0,22.Ed44-matematika-8
  1. Mengulangi kembali langkah ke-3 untuk karakter s dan parent baru 0,55.Ed44-matematika-9
  1. Memberi label 0 untuk cabang yang lebih kecil nilai frekuensi relatifnya dan 1 untuk cabang yang lebih besar nilainya.Ed44-matematika-10

Setelah menerapkan algoritma Huffman, sekarang kita dapat menuliskan “sassafras” ke dalam kode Huffman.

Huruf Biner Huffman
s 01110011 0
a 01100001 11
f 01100110 100
r 01110010 101

Kode Huffman ini hanya membutuhkan 16 bit, atau kita telah menghemat lebih dari 75% memori.

Metode yang sama juga berlaku untuk kompresi data gambar digital. Kode Huffman ini hanyalah contoh sederhana bagaimana kita dapat menghemat alokasi memori yang kita pakai dalam penyimpanan data. Kompresi ini efisien jika variasi data tidak terlalu banyak. Jika teman-teman tertarik untuk melihat bagaimana kode Huffman dapat dipakai juga dalam kompresi data audio MP3, silakan baca juga artikel rubrik matematika majalah 1000guru edisi bulan Juni 2014.

Bahan bacaan:

Penulis:
Eddwi Hesky Hasdeo, mahasiswa doktor di Departemen Fisika, Tohoku University, Jepang.
Kontak: heskyzone(at)gmail(dot)com.