Andi memiliki kamera digital single lens reflex (DSLR) model terbaru. Ia mengambil foto ikan mainan seperti pada gambar.
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.
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.
Untuk menghasilkan gambar tersebut, komputer mendeteksi tingkat kehitaman warna dengan skala 0 (hitam) – 255 (putih).
Jika kita perbesar gambar grayscale tersebut sampai batas maksimumnya, kita dapat melihat blok-blok pixel yang menyusun 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.
- Urutkan karakter dari frekuensi relatif terkecil ke yang terbesar.
- Dua karakter terendah, yaitu f dan r dijumlahkan, untuk membentuk parent baru, yang bernilai 0,22, dan membuat f dan r sebagai children.
- Mengulang langkah ke-2 untuk karakter a dan parent 0,22.
- Mengulangi kembali langkah ke-3 untuk karakter s dan parent baru 0,55.
- Memberi label 0 untuk cabang yang lebih kecil nilai frekuensi relatifnya dan 1 untuk cabang yang lebih besar nilainya.
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.
