PERBANDINGAN METODE SVD DAN SSVD PADA KOMPRESI CITRA
KHAERONI
SEKOLAH PASCA SARJANA INSTITUT PERTANIAN BOGOR BOGOR 2012
PERYATAAN MENGENAI TESIS DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa tesis dengan judul Perbandingan Metode SVD dan SSVD pada Kompresi Citra adalah karya saya sendiri dengan arahan dari komisi pembimbing, dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini.
Bogor, Februari 2012
Khaeroni NRP G551090341
ABSTRACT KHAERONI. A Comparation Between SVD and SSVD Method on Image Compression. Supervised by SRI NURDIATI and SISWADI. Data compression is the process of converting an input data into other data which has a smaller size. The data can be a file on a computer or a buffer in the computer’s memory. Compression is useful because it helps reduce the consumption of resources such as data space or transmission capacity. The use of singular value decomposition (SVD) in image compression has been widely studied. If the image, when considered as a matrix, has low rank, or can be approximated sufficiently well by a matrix of low rank, then SVD can be used to find this approximation. That is, by not include some elements of the image, the approximation has been able to represents the original image. This thesis presents a variation for SVD image compression technique proposed by Ranade et al. called SSVD. This variation can be viewed as a preprocessing step in which the input image is permuted by independent data permutation after it is fed to the standard SVD algorithm. Likewise, this decompression algorithm can be viewed as the standard SVD algorithm followed by a postprocessing step which applies the inverse permutation. On experimenting with some standard images, SSVD performs substantially better than SVD. This thesis also presents experiment evidence with other simulated images, which appears that SSVD isn’t better than SVD. Keywords: image compression, singular value decomposition, shuffle
RINGKASAN KHAERONI. Perbandingan Metode SVD dan SSVD pada Kompresi Citra. Dibimbing oleh SRI NURDIATI dan SISWADI. Kompresi data adalah proses mengubah sebuah data masukan menjadi data yang lain yang memiliki ukuran yang lebih kecil. Data tersebut bisa berupa file di komputer atau sebuah buffer di dalam memori komputer. Tujuan kompresi pada citra adalah untuk mengurangi ketidakrelevanan dan redundansi data citra dengan maksud agar disimpan atau dikirimkan dalam bentuk yang lebih efisien. Pemanfaatan singular value decomposition (SVD) atau dekomposisi nilai singular untuk mengompres citra telah cukup lama dipelajari. Jika suatu matriks citra berpangkat rendah atau dapat diaproksimasi cukup baik oleh suatu matriks yang juga berpangkat rendah, maka SVD dapat digunakan untuk menentukan aproksimasi tersebut (Ranade et al. 2006). Artinya, dengan tidak menyertakan beberapa elemen dari citra aproksimasi tersebut sudah dapat merepresentasikan citra aslinya. Ranade et al. (2006) menjelaskan salah satu modifikasi dari proses atau metode kompresi menggunakan SVD dan dari beberapa percobaan memberikan hasil kompresi yang lebih baik dibandingkan dengan metode kompresi SVD. Metode modifikasi ini dikenal dengan nama shuffle-SVD (SSVD). Dinamakan demikian karena sebelum dilakukan dekomposisi, matriks A terlebih dahulu dipermutasi dengan sebuah data permutasi independen. Ranade et al. (2006) mengklaim bahwa teknik shuffle yang diterapkan terhadap metode SVD untuk mengompres citra selalu memberikan hasil yang lebih baik daripada tanpa menerapkan shuffle. Demikian juga dengan Hafsah et al. (2007) menyatakan bahwa metode SSVD selalu lebih baik daripada metode SVD dalam mengompres citra. Tujuan dari penelitian ini adalah untuk menyusun algoritme kompresi citra menggunakan SVD dan SSVD kemudian mengetahui efektivitas penerapan teknik shuffle terhadap metode SVD dan mengetahui benar atau tidaknya klaim bahwa teknik shuffle yang diterapkan pada metode SVD selalu memberikan hasil yang lebih baik daripada tanpa di-shuffle sebelumnya. Penelitian ini menggunakan metode studi literatur dan kemudian mengimplementasikan metode kompresi citra ke dalam program komputer menggunakan software MATLAB. Pada bagian awal, diberikan contoh implementasi metode SVD dan SSVD pada beberapa matriks. Langkah ini dilakukan untuk melihat apakah SSVD selalu bekerja lebih baik daripada metode SVD. Selain itu pada penelitian ini kedua metode juga diterapkan pada beberapa citra yang direpresentasikan oleh sebuah matriks. Tujuan dari langkah ini adalah untuk mengetahui apakah metode SSVD selalu memberikan hasil yang lebih baik dibandingkan dengan metode SVD. Langkah-langkah yang dilakukan pada penelitian ini terdiri atas dua tahap. Tahap pertama adalah menyiapkan alat uji berupa program yang disusun
menggunakan bahasa pemrograman MATLAB. Tahap kedua adalah membandingkan efektivitas teknik shuffle yang diajukan oleh Ranade et al. (2006) dengan cara menerapkan teknik tersebut terhadap metode SVD untuk beberapa citra dan kemudian menghitung MSE yang dihasilkan oleh setiap metode. Tahap ketiga adalah memberikan contoh kontra ketidakefektifan teknik shuffle tersebut. Untuk membandingkan perbedaan metode SVD dan SSVD dilakukan dengan cara mengukur kualitas citra hasil kompresi dari masing-masing metode. Untuk menentukan kualitas citra yang telah dikompres digunakan pengukuran baku yaitu MSE. Semakin kecil nilai MSE antara citra asli dan citra hasil kompresi, semakin baik kompresi citra tersebut (Hafsah 2007). Kompresi citra menggunakan SVD pertama kali dilakukan dengan mengambil nilai piksel citra melalui MATLAB. Kemudian ditentukan SVD matriks A dengan menggunakan built in function MATLAB yaitu svd() untuk menentukan matriks U, dan V. Langkah berikutnya adalah memotong nilai U, dan V sesuai dengan rank yang diinginkan, misalnya p, sehingga diperoleh nilai Up, p dan Vp. Terakhir matriks Ap diperoleh dengan cara merekonstruksi Up, p dan Vp. Langkah kompresi citra menggunakan SSVD didahului dengan melakukan permutasi terhadap matriks citra A dengan suatu permutasi independen P yang disebut dengan shuffle (Ranade et al. 2006). Matriks yang dihasilkan, misalkan X = P(A) kemudian didekomposisi menggunakan SVD. Misalkan 1 T X p P U p pVp merupakan aproksimasi untuk A.
Proses shuffle ini dilakukan dengan harapan bahwa rank matriks citra akan berkurang dari rank sebelumnya. Pada beberapa citra, proses shuffle yang diterapkan tidak mengurangi nilai rank atau justru menjadi lebih besar dari rank sebelumnya walau dengan tingkat ketelitian atau toleransi yang cukup besar. Dari hasil pengujian terhadap citra lena484.jpg, dapat disimpulkan bahwa teknik shuffle yang diterapkan pada metode SVD bekerja cukup efektif. Terbukti bahwa, selain mengurangi MSE teknik shuffle yang diterapkan juga mampu mengurangi ukuran file citra menjadi lebih kecil daripada metode SVD sendiri. Akan tetapi, untuk citra sample_101.jpg, pada beberapa kasus, teknik shuffle yang diterapkan baik pada metode SVD maupun SSVD memperlihatkan perilaku yang berbeda dengan sebelumnya. Penerapan teknik shuffle justru memperbesar MSE dan ukuran file citra walaupun dengan perbedaan yang sangat kecil. Demikian juga untuk citra sample_900.jpg. Secara umum dapat disimpulkan bahwa teknik shuffle yang diterapkan pada metode SVD tidak selalu bekerja lebih baik daripada metode SVD sendiri. Pada beberapa citra, metode SSVD bekerja lebih baik. Akan tetapi pada citra yang lain metode SSVD tidak bekerja lebih baik. Jadi efektivitas metode SSVD juga ditentukan oleh pemilihan sampel citra yang digunakan. Selain itu, metode SSVD juga bergantung pada pemilihan rank (parameter kompresi). Dengan demikian justifikasi bahwa metode SSVD bekerja selalu lebih baik daripada metode SVD tidak dapat dibenarkan. Kata Kunci: pemampatan citra, dekomposisi nilai singular, shuffle
© Hak Cipta milik IPB, tahun 2012 Hak Cipta dilindungi Undang-undang 1.
2.
Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya a. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah. b. Pengutipan tersebut tidak merugikan kepentingan yang wajar IPB. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis dalam bentuk apapun tanpa izin IPB.
PERBANDINGAN METODE SVD DAN SSVD PADA KOMPRESI CITRA
KHAERONI
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Matematika Terapan
SEKOLAH PASCA SARJANA INSTITUT PERTANIAN BOGOR BOGOR 2012
Penguji Luar Komisi pada Ujian Tesis: Dr. Sugi Guritman
Judul Tesis Nama NRP
: Perbandingan Metode SVD dan SSVD pada Kompresi Citra : Khaeroni : G551090341
Disetujui Komisi Pembimbing :
Dr. Ir. Sri Nurdiati, M.Sc Ketua
Dr. Ir. Siswadi, M.Sc Anggota
Diketahui :
Ketua Program Studi Matematika Terapan
Dekan Sekolah Pascasarjana
Dr. Ir. Endar H. Nugrahani, M.S.
Dr. Ir. Dahrul Syah, M.Sc.Agr.
Tanggal Ujian: 21 Februari 2012
Tanggal Lulus:
PRAKATA Segala puja dan puji syukur hanya pantas bermuara pada Allah SWT. Dia– lah yang memberikan kita sebanyak–banyak kenikmatan. Sebesar apapun kesyukuran kita, tidak akan pernah bisa menyamai kenikmatan yang telah Dia berikan. Maha Suci Engkau dengan segala Kuasa-Mu. Atas Kuasa-Nya pula, tesis yang berjudul Perbandingan Metode SVD dan SSVD pada Kompresi Citra ini dapat penulis selesaikan. Penulis mengakui dan menyadari bahwa selama proses penulisan tugas akhir ini tidak luput dari bantuan banyak pihak. Mulai dari material, moral, spiritual, dan juga psikologis. Karena itu, dalam kesempatan kali ini penulis hendak menyampaikan sebanyak-banyak terima kasih kepada: 1. Allah SWT yang telah menganugerahi kita hikmah. Sehingga kita diberi pemahaman melebihi malaikat. Kasih Sayang-Nya yang tiada batas, menghindarkan kita dari kejahiliahan. 2. Istri tercinta, Sri Apriatni, S.Pd atas do’a, dukungan, dan kesabarannya. 3. Bapak Rektor dan Dekan Fakultas Tarbiyah dan Adab serta Bapak EkoWahyu Wibowo, M.Si selaku atasan penulis di Pusat Komputer IAIN “SMH” Banten yang telah memberikan izin untuk melanjutkan studi di SPs IPB. 4. Ibu Dr. Ir. Sri Nurdiati, M.Sc dan Bapak Dr. Ir. Siswadi, M.Sc, selaku komisi pembimbing yang telah memberikan pengarahan, masukan, dan bimbingan, serta bersedia untuk direpotkan. 5. Bapak Dr. Sugi Guritman sebagai penguji luar komisi yang telah memberikan masukan dan koreksi yang sangat berharga saat ujian tesis. 6. Segenap dosen Program Studi Matematika Terapan SPs IPB. 7. Bapak, ibu, kakak, dan adik-adikku tercinta atas doanya untuk penulis. 8. Teman-teman mahasiswa Program Studi Matematika Terapan SPs IPB, khususnya angkatan 2009. 9. Serta semua pihak yang tidak bisa penulis sebutkan satu-per-satu. Semoga setiap yang penulis libatkan dalam penyusunan tesis ini dibalas setiap kebaikannya dengan kebaikan yang lain secara berlipat. Sebuah kenyataan bahwa tesis ini masih terdapat banyak kekurangan. Oleh karena itu, saran dan kritik demi perbaikan dan kemajuan penulis dalam penyusunan karya ilmiah dikesempatan yang akan datang sangat penulis nantikan melalui e-mail
[email protected] atau web site www.khaeroni.net. Semoga karya yang sederhana ini dapat bermanfaat bagi ummat. Khoirunnas an fa ahum linnas. In tansurullaha yan surkum wa yu tsabbit aqdaa ma kum. Sebaikbaik manusia adalah yang paling bermanfaat bagi manusia. Barang siapa yang menolong agama Allah, niscaya Allah akan menolongnya dan meneguhkan pijakannya. Bogor, Februari 2012
Khaeroni
RIWAYAT HIDUP
Penulis dilahirkan di Serang pada tanggal 18 Maret 1983 dari Bapak Abdul Adim dan Ibu Yumnah. Penulis merupakan anak kelima dari tujuh bersaudara. Tahun 2001 penulis lulus dari SMA Negeri 1 Serang dan lulus seleksi masuk Universitas Gadjah Mada melalui jalur Ujian Masuk Perguruan Tinggi Negeri (UMPTN) pada Program Studi Matematika Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam dan selesai pada tahun 2005. Pertengahan tahun 2006 penulis lulus seleksi penerimaan Pegawai Negeri Sipil (PNS) dan ditugaskan sebagai Dosen Tetap pada Jurusan Pendidikan Guru Madrasah Ibtida’iyah Fakultas Tarbiyah dan Adab Institut Agama Islam Negeri Sultan Maulana Hasanuddin Banten. Pada tahun 2009 penulis lulus seleksi masuk Program Magister pada Program Studi Matematika Terapan di Institut Pertanian Bogor melalui jalur Beasiswa Pendidikan Pascasarjana (BPPS) Dikti.
DAFTAR ISI Halaman DAFTAR TABEL ....................................................................................... ...... xi DAFTAR GAMBAR .................................................................................. ..... xii DAFTAR LAMPIRAN ............................................................................... .....xiv I.
PENDAHULUAN ...................................................................................... 1 1.1 Latar Belakang ................................................................................... 1 1.2 Rumusan Penelitian............................................................................ 3 1.3 Tujuan Penelitian ............................................................................... 3
II.
TINJAUAN PUSTAKA ............................................................................. 5 2.1 Nilai Singular ..................................................................................... 5 2.2 Norm Vektor ...................................................................................... 5 2.3 Norm Matriks ..................................................................................... 5 2.3.1 Norm Frobenius .................................................................... 6 2.3.2 p-norm Matrix ....................................................................... 6 2.4 Mean Square Error ............................................................................ 6 2.5 Dekomposisi Nilai Singular ............................................................... 7 2.6 Ruang Null dan Ruang Kolom........................................................... 8 2.7 Rayleigh Quotient .............................................................................. 9 2.8 Diagonalisasi ..................................................................................... 10 2.9 Karhunen–Loève Transform ............................................................. 10 2.10 Konsep Dasar Kompresi Data ........................................................... 11 2.10.1 Principal Component Basis .................................................. 13 2.11 Konsep Teori Informasi .................................................................... 14 2.12 Aproksimasi Matriks Rank Rendah .................................................. 15 2.13 Citra Digital ...................................................................................... 15 2.13.1 Representasi Citra Digital .................................................... 15 2.13.2 Menyimpan dan Menampilkan Citra Digital........................ 18 2.13.3 Tipe Citra Digital pada MATLAB ....................................... 20 2.14 Kompresi Citra Digital ...................................................................... 21 2.14.1 Teknik Kompresi Citra Digital ............................................. 23 2.14.2 Kompresi Citra dengan SVD ................................................ 26 2.14.3 Kompresi Citra dengan SSVD ............................................. 27 2.14.4 Atribut Kompresi Citra Digital............................................. 29 2.15 Citra dan Pengolahan Citra di MATLAB ......................................... 30 2.15.1 Membaca dan Menulis File Citra ......................................... 30 2.15.2 Menampilkan Citra di MATLAB ......................................... 32
III. METODE PENELITIAN ........................................................................... 35 3.1 Metode Penelitian............................................................................. 35
3.2 3.3
Instrumen Penelitian ......................................................................... 35 Langkah Penelitian ........................................................................... 36 3.3.1 Menyiapkan Alat Uji ............................................................ 36 3.3.2 Membandingkan Efektivitas Teknik Shuffle......................... 37
IV. HASIL DAN PEMBAHASAN .................................................................. 43 4.1. Penelitian Kompresi Citra ................................................................ 43 4.2. Algoritme Kompresi Citra ................................................................ 45 4.2.1. Metode Kompresi SVD ........................................................ 45 4.2.2. Metode Kompresi SSVD ...................................................... 47 4.3. Ilustrasi Metode Kompresi Citra ...................................................... 48 4.4. Rancangan Uji Coba ......................................................................... 50 4.5. Hasil Uji Coba dan Analisis ............................................................. 52 V.
KESIMPULAN .......................................................................................... 71
DAFTAR PUSTAKA ......................................................................................... .73 LAMPIRAN ....................................................................................................... .77
DAFTAR TABEL Halaman 2.1
Fungsi untuk membaca dan menulis file citra pada MATLAB .............. 30
2.2
Fungsi untuk menampilkan citra ............................................................. 33
4.1
Nilai-nilai MSE dan rank dari matriks A, A1, X1, dan X1–1 ...................... 49
4.2
Nilai-nilai MSE dan rank dari matriks B, B1, Y1, dan Y1–1 ...................... 49
4.3
Nilai e(p) untuk citra lena484.jpg. ....................................................... 53
4.4
Nilai rank citra lena484.jpg dengan parameter kompresi 1 ................. 57
4.5
Nilai rank citra lena484.jpg dengan parameter kompresi 20 ............... 58
4.6
Nilai rank citra lena484.jpg dengan parameter kompresi 65 ............... 60
4.7
Ukuran citra lena484.jpg dengan parameter kompresi 65 ................... 61
4.8
Nilai CPU Time dan MSE kompresi untuk citra lena484.jpg.............. 61
4.9
Ukuran file citra dan rasio hasil kompresi lena484.jpg ........................ 63
4.10 Nilai rank citra lena484.jpg sebelum dan sesudah shuffle ................... 63 4.11 Beberapa nilai e(p) untuk citra sample_101.jpg. .................................. 64 4.12 Atribut hasil kompresi citra sample_101.jpg ........................................ 65 4.13 Nilai rank citra sample_101.jpg untuk p = 65 ...................................... 66 4.14 Nilai CPU Time dan MSE kompresi untuk citra sample_101.jpg ........ 66 4.15 Ukuran file citra dan rasio hasil kompresi citra sample_101.jpg.......... 67 4.16 Beberapa nilai e(p) untuk citra sample_900.jpg. .................................. 68 4.17 Nilai CPU Time dan MSE kompresi untuk citra sample_900.jpg ........ 69 4.18 Nilai rank citra sample_900.jpg untuk p = 163 dan toleransi 0.4......... 69 4.19 Ukuran file citra dan rasio hasil kompresi sample_900.jpg .................. 70
DAFTAR GAMBAR Halaman 2.1
Vektor data didekati dalam terminologi arahnya. ................................... 11
2.2
The Pixel Coordinate System. ................................................................. 16
2.3
Contoh Vector Image. ............................................................................. 16
2.4
Contoh bentuk rasterized dari huruf ‘a’ diperbesar 16 kali dan menggunakan piksel dengan ketelitian ganda. ........................................ 17
2.5
Bidang warna RGB Image dengan class double. .................................... 21
2.6
Citra format bitmap yang ditampilkan dengan penampil citra IrfanView. ............................................................................................... 22
2.7
Informasi detail file citra lena.bmp melalui IrfanView. ......................... 22
2.8
Contoh Run-length Encoding. ................................................................. 23
2.9
Contoh hasil Run-length Encoding. ........................................................ 24
2.10 Contoh informasi file citra dengan format JPEG. ................................... 25 2.11 Menampilkan file citra dalam MATLAB. ............................................... 33 2.12 Menggunakan subplot. .......................................................................... 34 3.1
Skema pemrosesan metode SVD untuk citra berwarna. ......................... 38
3.2
Skema pemrosesan metode SSVD. ......................................................... 39
3.3
Diagram penghitungan MSE antara citra asli dengan citra hasil kompresi. ................................................................................................. 40
3.4
Skema langkah-langkah penelitian.......................................................... 41
4.1
Citra lena484.jpg asli. .......................................................................... 51
4.2
Atribut file citra lena484.jpg. ............................................................... 51
4.3
Citra SVD_r1_lena484.jpg. ................................................................... 54
4.4
Atribut file citra SVD_r1_lena484.jpg. ................................................. 55
4.5
Citra SSVD_r1_lena484.jpg. ................................................................ 56
4.6
Atribut file citra SSVD_r1_lena484.jpg................................................ 56
4.7
Citra SVD_r20_lena484.jpg. ................................................................ 57
4.8
Citra SSVD_r20_lena484.jpg. .............................................................. 58
4.9
Citra SVD_r65_lena484.jpg. ................................................................ 59
4.10 Citra SSVD_r65_lena484.jpg. .............................................................. 59 4.11 Grafik respon perubahan rank terhadap MSE dari kedua metode untuk citra lena484.jpg. Rank/term yang digunakan adalah 1, 2, 3, 4, 5, 10, 20, 40, 65, 80, 100, 120, 140, 180, dan 200...................................... 62 4.12 Citra simulasi. ......................................................................................... 64 4.13 Hasil kompresi citra sample_101.jpg dengan parameter kompresi 65 . .......................................................................................................... 65 4.14 Hasil kompresi citra sample_900.jpg dengan parameter kompresi 163 .. ....................................................................................................... 68
DAFTAR LAMPIRAN Halaman 1.1 Lemma 2.1 ................................................................................................... 77 1.2 Teorema 2.1 ................................................................................................. 78 1.3 Teorema 2.2 ................................................................................................. 78 1.4 Teorema 2.3 ................................................................................................. 79 2.1 Kompresi Citra dengan SVD ....................................................................... 81 2.2 Kompresi Citra dengan SSVD ..................................................................... 84 3.1 Contoh Penghitungan MSE Metode SVD dan SSVD ................................. 91 3.2 Contoh Langkah Menyimpan Variabel MATLAB ke MAT-File ............... 93
BAB I PENDAHULUAN
1.1
Latar Belakang Internet kini menjadi media yang efektif dan efisien untuk memperoleh
informasi. Baik itu berupa teks biasa (plain text) seperti artikel maupun berupa gambar. Salah satu jenis gambar yang sering disertakan dalam suatu laman web (web page) adalah citra (image). Besar kecilnya ukuran citra akan memengaruhi cepat lambatnya laman tersebut terbuka. Oleh karena itu, dilakukan beberapa cara untuk mempercepat terbukanya sebuah laman yang memuat citra. Salah satu cara mempercepatnya adalah dengan mengompres citra tersebut. Tujuannya adalah agar citra yang disertakan ukurannya menjadi lebih kecil sehingga beban yang diberikan kepada browser dalam membuka laman tersebut menjadi lebih kecil dengan tanpa kehilangan kelayakan citra untuk dilihat secara kasat mata. Selain itu, juga dapat mengurangi ruang penyimpanan di dalam media penyimpanan. Kompresi data adalah proses mengubah sebuah data masukan menjadi data yang lain yang memiliki ukuran yang lebih kecil. Data tersebut bisa berupa file di komputer atau sebuah buffer di dalam memori komputer. Tujuan kompresi pada citra adalah untuk mengurangi ketidakrelevanan dan redundansi data citra dengan maksud agar disimpan atau dikirimkan dalam bentuk yang lebih efisien. Pemanfaatan singular value decomposition (SVD) atau dekomposisi nilai singular untuk mengompres citra telah cukup lama dipelajari. Beberapa di antaranya seperti yang dituliskan oleh Scheick (1997) dalam Linear Algebra with Applications dan Khaeroni (2005) dalam Pemampatan Citra Menggunakan Dekomposisi Nilai Singular. Jika suatu citra (yang juga merupakan matriks) berpangkat rendah (low rank) atau dapat diaproksimasi cukup baik oleh suatu matriks yang juga berpangkat rendah, maka SVD dapat digunakan untuk menentukan aproksimasi tersebut (Ranade et al. 2006). Artinya, dengan tidak menyertakan beberapa elemen dari citra aproksimasi tersebut sudah dapat merepresentasikan citra aslinya. 1
2 Ranade et al. (2006) menjelaskan salah satu modifikasi dari proses atau metode kompresi menggunakan SVD dan dari beberapa percobaan memberikan hasil kompresi yang lebih baik dibandingkan dengan metode kompresi SVD. Metode modifikasi ini dikenal dengan nama shuffle-SVD (SSVD). Dinamakan demikian karena sebelum dilakukan dekomposisi, matriks A terlebih dahulu dipermutasi dengan sebuah data permutasi independen P. Misalkan X adalah matriks hasil permutasi sedemikian sehingga X = P(A). Matriks X kemudian didekomposisi menggunakan SVD. Misalkan rank dari A adalah r dan aproksimasi rank p dari X adalah Xp dengan p ≤ r. Secara empiris diperoleh bahwa untuk nilai p yang sama, P–1(Xp) akan menghasilkan aproksimasi yang lebih baik untuk A dibandingkan Ap, di mana P–1 menyatakan permutasi balikan (re-shuffle) dari P. Dengan melakukan shuffle (SSVD) diharapkan akan diperoleh hasil kompresi yang lebih baik dibandingkan bila tidak di-shuffle sebelumnya (SVD). Sementara Hafsah et al. (2007) membandingkan hasil penerapan metode SSVD pada pemrosesan secara global dengan pemrosesan secara blocking dimana block yang digunakan adalah square-block pada pemrosesan citra dan dengan teknik blocking dan ukuran block-nya seragam (uniform). Dari penelitian yang dilakukan dapat disimpulkan bahwa melalui pemrosesan secara global SSVD lebih unggul dibandingkan SVD, tetapi melalui pemrosesan terhadap block yang dipilah-pilah (blocking) SSVD tidak terbukti lebih unggul dibandingkan SVD. Ranade et al. (2006) dan Hafsah et al. (2007) menerapkan metode SVD dan SSVD terhadap citra keabuan (grayscale image), baik dengan teknik global maupun teknik blocking. Penelitian ini menerapkan metode SVD dan SSVD terhadap citra berwarna (color image) dengan teknik global kemudian membandingkan hasil kompresi dari kedua metode tersebut secara empiris. Ranade et al. (2006) mengklaim bahwa teknik shuffle yang diterapkan terhadap metode SVD untuk mengompres citra selalu memberikan hasil yang lebih baik daripada tanpa menerapkan shuffle. Demikian juga dengan Hafsah et al. (2007) menyatakan bahwa metode SSVD selalu lebih baik daripada metode SVD dalam mengompres citra.
3
1.2
Rumusan Penelitian Untuk memudahkan langkah-langkah dan metode penelitian, maka dibuat
rumusan dari penelitian ini, yaitu sebagai berikut: 1.
Bagaimana algoritme kompresi citra menggunakan SVD dan SSVD.
2.
Bagaimana efektivitas penerapan teknik shuffle terhadap metode SVD.
3.
Bagaimana kebenaran klaim bahwa teknik shuffle yang diterapkan pada metode SVD selalu memberikan hasil yang lebih baik daripada tanpa dishuffle sebelumnya.
1.3
Tujuan Penelitian Berdasarkan latar belakang masalah di atas, maka tujuan dari penelitian ini
adalah untuk menyusun algoritme kompresi citra menggunakan SVD dan SSVD kemudian mengetahui efektivitas penerapan teknik shuffle terhadap metode SVD dan mengetahui benar atau tidaknya klaim bahwa teknik shuffle yang diterapkan pada metode SVD selalu memberikan hasil yang lebih baik daripada tanpa dishuffle sebelumnya.
4
BAB II TINJAUAN PUSTAKA
2.1
Nilai Singular Diberikan A matriks m x n dengan rank(A) = r. Akar nilai ciri positif dari
ATA disebut dengan nilai singular dari A (Goldberg 1991).
2.2
Norm Vektor Norm vektor (vector norm) pada n didefinisikan sebagai fungsi
f : n sedemikian sehingga untuk setiap x, y n dan memenuhi ketiga aksioma berikut. (1) f x 0 dan f x 0 x 0 (2) f x y f x f y (3) f x f x Untuk selanjutnya norm vektor x ditulis x (Golub dan Loan 1996). Salah satu jenis dari norm vektor adalah p-norm vektor dan didefinisikan sebagai x
p
p
x1 xn
p
1 p
,
p 1.
Dengan menggunakan definisi di atas, diperoleh norm 1, 2, dan ∞ untuk sebarang x n sebagai berikut
x 1 x1 xn
2
x 2 x1 xn x
1 2 2
1
xT x 2
max xi 1i n
Untuk selanjutnya, jika tidak disebutkan secara jelas, simbol x digunakan untuk menyatakan x 2 .
2.3
Norm Matriks Fungsi f : mxn disebut norm matriks (matrix norm) jika untuk 5
6 setiap A, B mxn dan memenuhi ketiga aksioma berikut: (1) f A 0 dan f A 0 A 0 (2) f A B f A f B (3) f A f A Untuk memudahkan penulisan, norm matriks A ditulis A sehingga A f A (Golub dan Loan 1996).
2.3.1 Norm Frobenius Untuk sebarang matriks A berukuran m x n, norm Frobenius (Frobenius Norm) dari matriks A didefinisikan sebagai (Meyer 2000) A
2 F
aij trace AT A 2
i, j
2.3.2 p-norm Matrix Untuk sebarang matriks A berukuran m x n, p-norm dari matriks A didefinisikan sebagai (Golub dan Loan 1996) A p max Ax x p 1
p
Untuk selanjutnya, jika tidak disebutkan secara jelas, simbol A digunakan untuk menyatakan A 2 .
2.4
Mean Square Error Mean Square Error (MSE) merupakan salah satu ukuran yang dapat
digunakan untuk menentukan kualitas suatu aproksimasi. Misalkan matriks A berukuran m x n dan B merupakan aproksimasi untuk A. Jika aij menyatakan elemen baris ke-i dan kolom ke-j dari A, maka MSE antara matriks A dengan B didefinisikan sebagai
MSE
2 1 m n aij bij (Thyagarajan 2006) mn i 1 j 1
7 Dari sini MSE dapat dinyatakan dalam norm Frobenius, yaitu MSE
1 A B mn
2 F
1 T trace A B A B mn
2.5
Dekomposisi Nilai Singular Misalkan A sebarang matriks berukuran m x n dengan rank(A) = r.
Singular Value Decomposition (SVD) atau dekomposisi nilai singular dari A adalah faktorisasi dalam bentuk
A U V T
(2.1)
dengan U = [U1 U2 . . . Um] dan V = [V1 V2 . . . Vn] merupakan matriks ortogonal. Matriks U berukuran m x m dan V berukuran n x n, dan 0 matriks
berukuran
m
x
n
dengan
0 adalah 0
diag ( 1 , 2 ,, r )
dan
0 T 1 2 r 0 (Nicholson 2001). Dari sini, Am,n U m,m Vn ,n . 0 0 m,n Misalkan A sebarang matriks berukuran m x n dan 1 , , n menyatakan nilai ciri dari matriks ATA. Selanjutnya digunakan notasi sedemikian sehingga
1 2 3 n . Misalkan
x, y menyatakan hasil kali dalam baku antara vektor x dan
vektor y. Diambil sebarang {V1, . . ., Vn} basis ortonormal untuk
n
dan Vi
merupakan vektor ciri yang bersesuaian dengan nilai ciri dari ATA, yaitu i untuk setiap i. Dengan kata lain {V1, . . ., Vn} merupakan basis ciri ortonormal untuk ATA. Karena {V1, V2, . . ., Vn} ortonormal maka Vi , V j 0 untuk i j dan
Vi ,Vi
Vi
2
12 1. Sehingga untuk setiap Vi dapat ditulis Vi , V j ij
(2.2)
Perhatikan bahwa untuk setiap i dan j AVi , AV j ( AVi )T AV j Vi T ( AT AV j ) Vi T ( jV j ) j Vi , V j j ij . (2.3)
Karena Vi 1 untuk setiap i, dengan mengambil i = j diperoleh
8
i AVi
2
untuk setiap i = 1, 2, . . ., n.
Terlihat bahwa i 0 untuk setiap i. Sehingga bilangan
i i untuk i = 1, 2, . . ., r tidak lain merupakan nilai singular dari A dengan 1 2 r 0 dan 2
AVi
i2
(2.4)
untuk setiap i.
2.6
Ruang Null dan Ruang Kolom Misalkan A sebarang matriks berukuran m x n dengan A = [A1 A2 . . . An]
Himpunan N(A) = {x dan CS(A) = {x
n
: Ax = 0}
n
disebut ruang null (null space) dari A
: x = 1 A1 + 2 A2 +. . .+ n An , i
m
}
m
disebut ruang
kolom (column space) dari A (Anton 2000). Lemma 2.1 (Nicholson 2001) Misalkan A sebarang matriks berukuran m x n dan rank(A) = r dan {V1, . . ., Vn} merupakan basis ciri ortonormal untuk ATA. 1) Matriks A memiliki tepat r nilai singular. 2) {AV1, AV2, . . ., AVr} merupakan basis ortogonal untuk CS(A). Bukti pada Lampiran 1, sub 1.1.
AVi i 0 , i = 1, 2, . . ., r. Jika
Dari Lemma di atas, diperoleh didefinisikan vektor unit Ui
untuk i = 1, 2, . . ., r dalam
1
i
(2.5)
AVi
m
, maka {U1, U2, . . ., Ur} merupakan himpunan
yang ortonormal. Kemudian ditentukan sebanyak m – r vektor yang saling ortogonal dengan {U1, U2, . . ., Ur} dan U j 1 , j = r + 1, . . ., m. Sehingga {U1, U2, . . ., Ur, Ur+1, . . ., Um} tetap merupakan basis ortonormal untuk
m
. Dari sini
9 dibentuk U = [U1 U2 . . . Um] dan V = [V1 V2 . . . Vn]. Perhatikan pula bahwa
U i ,U j AVi / i , AV j / j 1/ ( i j ) Vi , AT AV j 1/ ( i j ) Vi , 2j V j ( j / i ) ij ij . Jika Ui menyatakan kolom ke-i dari U maka U iT adalah baris ke-i dari UT. Diperoleh (U TU )ij U iTU j dan U TU U iT U j U j ,U i [ ji ] [ ij ] I , V T V Vi T V j V j , Vi [ ji ] [ ij ] I . Jadi U dan V ortogonal. Teorema 2.1 (Goldberg 1991) Diberikan A sebarang matriks berukuran m x n dengan rank(A) = r dan nilai singular 1 r . Jika didefinisikan U, , dan V seperti uraian di atas, maka U dan V matriks ortogonal dan A dapat didekomposisikan sebagai A U V T
(2.6)
Bukti pada Lampiran 1, sub 1.2.
2.7
Rayleigh Quotient Diberikan A matriks simetri berukuran n x n dengan nilai ciri 1 n .
Misalkan x, y sebarang vektor tak nol di
Ax, y x, Ay
x, y
n
n
. Karena A simetri maka
. Rayleigh Quotient R(x) dari matriks simetri A
terhadap x dengan x 0 didefinisikan sebagai R( x)
Ax, x x
2
(Scheick 1997).
Teorema 2.2 (Scheick 1997) Diberikan A matriks simetri berukuran n x n dengan nilai ciri 1 n dan sebarang x
n
dengan x ≠ 0.
10 1) Jika x adalah vektor ciri dari A yang bersesuaian dengan i maka R(x) = i , untuk suatu i. 2) 1 R( x) n . 3) λ1 = max{R(x) dan λn = min{R(x) . Bukti pada Lampiran 1, sub 1.3. Teorema 2.3 Extended Maximal Principle (Scheick 1997) Diberikan A matriks simetri berukuran n x n dengan nilai ciri 1 2 n dan
ek k 1 merupakan basis ciri ortogonal untuk A, maka: n
1)
1 max{R( x) : x 0}
(2.7)
2) i max{R ( x) : x 0, x e1 , e2 , , ei 1} untuk i 2,, n .
(2.8)
Bukti pada Lampiran 1, sub 1.4.
2.8
Diagonalisasi Diberikan matriks A berukuran n x n. Matriks A dikatakan dapat
didiagonalkan (diagonalizable) jika terdapat matriks invertibel sedemikian sehingga 1 A merupakan matriks diagonal atau A 1 . Dalam hal ini dikatakan mendiagonalkan matriks A (Nicholson 2001). Untuk setiap matriks simetri R, terdapat matriks ortogonal sedemikian sehingga T R atau R dimana merupakan matriks diagonal yang entrinya merupakan nilai ciri dari matriks R (Jain 1989). Dengan demikian dapat ditulis R k k k , 1 ≤ k ≤ n dimana k merupakan vektor ciri dari R yang bersesuaian dengan nilai ciri k .
2.9
Karhunen–Loève Transform Definisi lebih lengkap mengenai Karhunen–Loève Transform dapat dilihat
pada Jain (1989). Misalkan x adalah vektor acak berukuran n x 1, dengan x[k] adalah peubah acak pada suatu ruang peluang untuk 1 ≤ k ≤ n. Misalkan R =
11 E[xxT] adalah matriks autokorelasi dari x, jelas bahwa R = RT atau R merupakan matriks simetri.
Misalkan vk adalah vektor ciri matriks R yang bersesuaian
dengan nilai ciri k . Himpunan { k } dibentuk dari {vk} dengan terlebih dahulu melakukan proses ortogonalisasi dan normalisasi sehingga tetap berlaku (Jain 1989) R k k k , untuk 1 ≤ k ≤ n Jika 1
2 n maka merupakan matriks ortogonal (uniter)
sehingga T 1 . Karhunen–Loève Transform (KLT) dari x didefinisikan sebagai (Jain 1989) y T x
2.10
Konsep Dasar Kompresi Data Diberikan n vektor data X1, X2, . . ., Xn
m
. Kemudian dicari vektor-
vektor e1, e2, . . . dengan arah yang terbaik untuk vektor data tersebut.
Gambar 2.1
Vektor data didekati dalam terminologi arahnya.
Untuk suatu vektor unit e maka
f , e e merupakan proyeksi vektor dari f
pada span{e}. Pada Gambar 2.1, misalkan proyeksi vektor Xk pada ruang yang dibangun oleh e1 adalah a, begitu juga untuk proyeksi vektor Xk pada ruang yang dibangun oleh e2 dan e3 adalah b dan c. Terlihat pada gambar di atas, dibandingkan dengan vektor a dan b, vektor c merupakan vektor yang arahnya paling mendekati atau yang hampir sama dengan vektor data Xk. Dalam tinjauan
12 aproksimasi, jarak antara Xk dengan vektor proyeksi ini adalah yang paling dekat. Sehingga masalah yang timbul adalah meminimumkan X k c atau sama dengan 2
meminimumkan X k c , maka 2
Xk c Xk
dan nilai dari X k
2
meminimumkan c
2
c
2
adalah tetap maka meminimumkan X k c 2
2
sama dengan
2
atau memaksimumkan c .
Perhatikan bahwa, 2
2
c X k , e3 e3 n
Misalkan D (e) X k , e
2
X k , e3
2
e3
2
2
X k , e3
maka D(e) merupakan ukuran seberapa baik e
k 1
menunjuk pada arah Xk, k = 1, . . ., n sebagai sebuah himpunan. Misalkan pertama kali dipilih vektor unit e = e1, maka vektor arah ini akan memaksimumkan jumlahan tersebut. Untuk mendapatkan arah terbaik berikutnya, dicari suatu vektor e e1 dengan D(e) maksimum, katakan vektor ini e2. Secara umum, setelah ditemukan e1, . . ., ep-1, dicari e = ep yang ortogonal dengan vektor-vektor tersebut dan memaksimumkan D(e). n
Perhatikan bahwa D (e) X k , e k 1
2
n
eT X k X kT e , sehingga k 1
D(e) eT XX T e eT Qe ,
(2.9)
X [ X 1 X n ] dan Q = XXT.
(2.10)
dengan
Permasalahan di atas dapat disajikan sebagai berikut: Memaksimumkan eTQe dengan e 1 . Jika diberikan e1, . . ., ep-1, permasalahan di atas menjadi Memaksimumkan eTQe dengan e 1 , dan e e1, . . ., ep-1. Permasalahan tersebut tidak lain merupakan extended maximal principle 2
untuk Rayleigh Quotient dari Q, dengan R (e) Qe, e / e eT Qe /1 eT Qe .
13 Menurut Teorema 2.3 vektor pemaksimal R(e) merupakan vektor ciri dari Q yang ortogonal, sebut e1, e2, . . .em. Menurut Teorema 2.2, diperoleh barisan nilai maksimumnya adalah D(e1 ) 1 , D(e2 ) 2 , . . . , D(em ) m , dengan
1 2 m tak lain merupakan akar ciri dari Q. Di lain pihak, perhatikan bahwa akar ciri tak nol dari Q=XXT tak lain adalah i i2 dan vektor ciri–nya adalah ei = Ui dengan X = UVT merupakan SVD dari X dengan nilai singular dari X adalah i .
2.10.1 Principal Component Basis Basis
ek k 1 m
m
untuk
yang ditemukan melalui proses di atas adalah m
ortonormal karena U ortogonal. Dengan demikian, setiap x m
x i ei , i x, ei / ei
2
dapat ditulis
x, ei .
i 1
(2.11)
Koordinat dari x di dalam basis ini, yaitu i , disebut principal components dari x. Basis ek k 1 disebut principal component basis. m
Permasalahan yang muncul dalam kompresi data adalah berapa banyak i p
yang diperlukan untuk merepresentasikan x? Misalkan s p i ei merupakan i 1
proyeksi dari x pada span ek k 1 . Dari sini, p
x sp
2
2
x sp
2
m
p
m
p
i ei i ei i i 2
2
i 1
2
2
i 1
i 1
2
i 1
2
m
i p 1
2
i .
Jika residu ini diabaikan maka sp bisa diterima sebagai aproksimasi untuk x. Kemudian ditentukan berapa banyak term yang dibutuhkan jika x adalah salah satu dari Xk. Perhatikan bahwa
x sp
2
m
i p 1
2 i
m
e
i p 1
T i
xxT ei
Jika diambil x = Xk dan dijumlahkan semua atas k serta dari kenyataan bahwa Qei i ei atau eiT Qei eiT ei i i , diperoleh
14
n
k 1
n
X k sp ( X k ) 2
m
k 1 i p 1
eiT X k X kT ei
n m m T T T e X X e e Qe i i i i p 1 i . k k i i p 1 k 1 i p 1 m
Sehingga untuk merepresentasikan x dalam himpunan
X k k 1 , n
cukup
dengan memilih p sedemikian sehingga m
i
i p 1 m
(2.12)
i 1
i
kecil. Selanjutnya, proyeksi suatu vektor x dapat dihitung dengan memotong ekspansi principal components-nya p
p
i 1
i 1
s p x, ei ei ei eiT x e1 e p e1 e p x T
(2.13)
Jika dengan mengambil nilai p seperti di atas dapat diterima, berarti sub-ruang span ek k 1 memuat sebagian besar informasi sebenarnya. p
2.11
Konsep Teori Informasi Teori informasi pertama kali diperkenalkan oleh Shannon (1948). Teori
tersebut dianggap sebagai dasar teori penelitian kompresi data (Zadeh 1965; Acharya dan Ray 2005). Shannon membuktikan bahwa terdapat batas pada kompresi data lossless. Batas itu disebut entropy rate yang disimbolkan dengan H. Nilai H bergantung pada sumber informasi, sehingga memungkinkan untuk melakukan kompresi sumber informasi secara lossless dengan nilai kompresi mendekati H (Hafsah 2007). Shannon juga menemukan teori kompresi data lossy yang dikenal dengan teori rate-distortion. Pada kompresi data lossy, data yang telah diekstrak tidak harus sama dengan data asli (original). Meskipun demikian, sejumlah distorsi dapat ditolerir (Hafsah 2007).
15
2.12
Aproksimasi Matriks Rank Rendah Misalkan A matriks berukuran m x n dengan rank(A) = r dan SVD dari A
dinyatakan sebagai r
A iU iVi T
(2.14)
i 1
Jika nilai singular p 1 , , r lebih kecil dibandingkan dengan 1 , , p maka dengan ‘membuang’ sebanyak r – p term pada (2.14) akan memberikan aproksimasi untuk A dan memiliki rank yang lebih kecil daripada r (Greenacre 1984). Teorema aproksimasi dengan rank rendah (low rank approximation) pertama kali dinyatakan dan dibuktikan oleh Eckart dan Young (1936) dan pada beberapa jurnal disebut dengan Eckart-Young Theorem. Teorema tersebut menyebutkan bahwa jika matriks A berukuran m x n dengan rank(A) = r dan SVD r
p
i 1
i 1
dari A adalah A iU iVi T maka Ap iU iVi T merupakan aproksimasi terbaik dengan rank p untuk A, yaitu Ap meminimumkan m
n
(a i 1 j 1
ij
xij )2 trace A X
T
A X
(2.15)
untuk setiap matriks X dengan rank p atau kurang (Greenacre 1984).
2.13
Citra Digital
2.13.1 Representasi Citra Digital Komputer menampilkan citra sebagai koleksi titik-titik (dot) yang disebut dengan pixel (picture element) atau piksel. Informasi visual disimpan dalam struktur data array atas bit-bit bilangan. Setiap titik dari gambar dipetakan ke satu atau lebih bit dalam memori komputer. Citra digital dibangun oleh piksel-piksel yang dapat dianggap sebagai sebuah titik kecil pada layar. Citra dengan ukuran m x n adalah citra yang dibangun oleh m piksel pada arah vertikal dan n piksel pada arah horisontal. Citra digital direpesentasikan dengan suatu matriks atas bilangan-bilangan di mana setiap bilangan tersebut merepresentasikan nilai intensitas di suatu titik. Titik pada citra inilah yang disebut dengan piksel. Intensitas piksel disebut dengan gray
16 levels. Jika C adalah matriks citra berukuran m x n maka Crc adalah nilai intensitas pada posisi yang bersesuaian dengan entri pada baris r dan kolom c citra yang direpresentasikan oleh matriks tersebut.
Gambar 2.2
The Pixel Coordinate System.
Salah satu cara untuk merepresentasikan sebuah citra menggunakan komputer adalah dengan menyatakan sebuah citra menggunakan angka-angka untuk merepresentasikan entri-nya berdasarkan posisi dan ukuran bentuk geometris dan bentuk seperti garis, kurva, persegi, atau lingkaran. Citra seperti ini disebut dengan citra vektor (vector image).
draw circle center radius fill-color stroke-color stroke-width draw circle center radius fill-color draw circle center radius fill-color draw line start end stroke-color stroke-width
Gambar 2.3
0.5, 0.5 0.4 yellow black 0.05 0.35, 0.4 0.05 black 0.65, 0.4 0.05 black 0.3, 0.6 0.7, 0.6 black 0.1
Contoh Vector Image.
17 Citra yang disimpan dan ditampilkan dengan cara yang sama disebut bitmapped image atau bitmap (Sutopo 2002). Citra bitmap (atau raster images) adalah
“foto
digital”,
bentuk
yang
paling
sering
digunakan
untuk
merepresentasikan citra alami dan juga merupakan bentuk grafis dengan detail yang sangat banyak. Citra bitmap bisa juga menyatakan bagaimana suatu grafis disimpan ke dalam memori video komputer. Terminologi bitmap merujuk pada bagaimana memberikan pola bit-bit di dalam peta piksel ke suatu warna yang spesifik.
Gambar 2.4
Contoh bentuk rasterized dari huruf ‘a’ diperbesar 16 kali dan menggunakan piksel dengan ketelitian ganda.
Citra bitmap berbentuk sebuah larik (array) di mana nilai pada setiap elemen disebut dengan piksel (pixel – picture element) yang bersesuaian dengan warna yang diberikan oleh citra tersebut. Setiap garis horisontal di dalam citra disebut dengan garis pindai (scan line). Huruf ‘a’ direpresentasian dengan sebuah matriks berukuran 12 x 14 sebagaimana yang diperlihatkan pada Gambar 2.3, bilangan-bilangan
di
dalam
matriks
menggambarkan
tingkat
kecerahan
(brightness) dari pikselnya. Bilangan yang lebih besar bersesuaian dengan area yang lebih terang sedangkan yang lebih rendah adalah lebih gelap.
18
2.13.2 Menyimpan dan Menampilkan Citra Digital Citra digital memerlukan ruang penyimpanan yang besar. Untuk merepresentasikan citra berukuran 640 x 480 piksel, di mana setiap piksel direpresentasikan dengan 1 byte memori (merepresentasikan bilangan 0–255), memerlukan 640 x 480 x 1 byte = 307.200 byte = 300 KB = 0.29 MB memori. Komputer menyimpan sebuah file citra ke dalam disk atau media penyimpanan lainnya dalam bentuk biner (binary). Komputer menyimpan informasi data piksel dan metadata yang berisi informasi pendukung tambahan, seperti dimensi dan tag. Menyimpan sebuah file citra erat kaitannya dengan format penyimpanan yang digunakan. Biasanya file citra disimpan oleh software tertentu yang akan menerapkan algoritme sesuai dengan format digunakan. Salah satu format penyimpanan yang sering digunakan adalah JPEG (Joint Photographic Experts Group). Format JPEG merupakan skema kompresi file bitmap. Awalnya, file yang menyimpan hasil foto digital memiliki ukuran yang besar sehingga tidak praktis. Dengan format baru ini, hasil foto yang semula berukuran besar berhasil dikompresi sehingga ukurannya kecil. Format ini dikembangkan pada awal tahun 1980 oleh Joint Photographic Experts Group (JPEG). JPEG merupakan format yang paling sering digunakan di internet. Implementasi format JPEG terbaru dimulai sejak tahun 1996 dan semakin berkembang dengan inovasi format baru yang menyertai perkembangan teknologi yang memanfaatkan format JPEG lebih luas. Walaupun format JPEG merupakan metode kompresi gambar yang gratis, sebuah perusahaan bernama Forgent pada tahun 2002 mempatenkan format ini dan akan menarik biaya lisensi. Segera grup JPEG mengumumkan sebuah format JPEG 2000 sebagai sebuah format pengganti. Namun dua hal di atas terlambat, karena JPEG sudah digunakan secara luas dan hak paten belum ditetapkan oleh pengadilan. Standar kompresi file gambar yang dibuat oleh kelompok JPEG ini menghasilkan kompresi yang sangat besar tetapi dengan akibat berupa adanya distorsi pada gambar yang hampir selalu tidak terlihat. JPEG adalah sebuah format gambar yang sangat berguna untuk membuat gambar jenis fotografi
19 berkualitas tinggi dalam ukuran file yang sangat kecil. Format file grafis ini telah diterima oleh Telecommunication Standardization Sector atau ITU-T dan Organisasi Internasional untuk Standardisasi atau ISO. JPEG kebanyakan digunakan untuk melakukan kompresi gambar menggunakan analisis Discrete Cosine Transform (DCT). Meskipun kompresi gambar JPEG sangatlah efisien dan selalu menyimpan gambar dalam kategori warna true color (24 bit), format ini bersifat lossy yang berarti bahwa kualitas gambar dikorbankan bila tingkat kompresi yang dipilih semakin tinggi. Ketika ada file citra berukuran 100 x 100 piksel dan disimpan dengan format JPEG maka file tersebut akan dimanipulasi dengan suatu algoritme yang membuang nilai di posisi-posisi tertentu karena memang tidak dilihat manusia. Format penyimpanan JPEG bisa lebih kecil daripada ukuran file sebenarnya karena ia membuang beberapa data warna yang tidak terlalu tampak secara visual oleh indera mata manusia. Intinya, jika mata manusia sulit melihatnya maka komputer tidak perlu menyimpannya. Dengan tingkat kompresi moderat dan jika dilihat sepintas, secara visual, citra berformat JPEG sulit dibedakan dengan citra asli. Bagaimana JPEG melakukan hal tersebut dapat dilihat pada referensireferensi terkait. Terdapat perbedaan terminologi antara ‘menyimpan’ dan ‘menampilkan’. Format JPEG, BMP, PNG, DWF, GIF, dan adalah format penyimpanan. Supaya bisa dilihat, format penyimpanan itu harus dibuka, dibaca, dan direkonstruksi ke dalam format penampilan. Lazimnya format penampilan adalah bitmap. Oleh karena itu, semua format penyimpanan itu akan selalu menampilkan citra dalam format bitmap yang berarti bahwa ukuran citra di memori akan selalu tetap sesuai dengan resolusinya. Dalam hal ini harus ada mekanisme rekonstruksi dari menyimpan ke menampilkan, kemudian dari menampilkan ke menyimpan. Mekanisme ini disebut algoritme. Algoritme ini biasanya yang membedakan sebuah software manipulasi gambar itu bagus atau tidak.
20
2.13.3 Tipe Citra Digital pada MATLAB MATLAB menyimpan citra sebagai larikan (array) dua dimensi, yaitu matriks. Setiap elemen dari matriks ini bersesuaian dengan satu piksel dalam citra yang ditampilkan. Sebagai contoh, suatu citra yang terdiri atas 200 baris dan 300 kolom atas titik-titik warna yang berbeda, disimpan oleh MATLAB sebagai matriks berukuran 200 x 300. Oleh karena itu, bekerja dengan citra di MATLAB serupa dengan bekerja terhadap sebarang matriks data yang lain. Sebagai contoh, untuk mengambil piksel tunggal dari suatu matriks citra digunakan operasi pengacuan matriks biasa, misal I(2,15). Perintah ini mengembalikan nilai piksel pada baris ke-2 dan kolom ke-15 citra I. MATLAB mampu mengolah banyak tipe citra digital, salah satunya adalah RGB image. RGB (Red, Green, Blue) image atau dikenal dengan nama truecolor image, di dalam MATLAB disimpan sebagai larikan data berukuran m x n x 3 yang menggambarkan komponen-komponen warna merah, hijau, dan biru untuk setiap piksel. Warna pada tiap piksel ditentukan dengan kombinasi intensitas warna merah, hijau, dan biru yang disimpan dalam tiap bidang warna pada lokasi piksel tersebut. Format file RGB, menyimpan RGB images sebagai citra 24-bit dengan masing-masing komponen warna merah, hijau, dan biru adalah 8-bits. Dari sini diperoleh kemungkinan 16 juta kombinasi warna untuk satu piksel. Suatu larikan RGB MATLAB bisa dari class double, uint8, atau uint16. Larikan RGB dari class double setiap komponennya warna merupakan suatu nilai di antara 0 and 1. Piksel yang komponen warnanya (0,0,0) ditampilkan sebagai hitam, dan piksel yang komponen warnanya (1,1,1) ditampilkan sebagai putih. Ketiga komponen warna dari tiap piksel disimpan sepanjang dimensi ketiga dari larikan data. Sebagai contoh komponen warna merah, hijau, dan biru dari piksel (10,5) disimpan dalam RGB(10,5,1), RGB(10,5,2), dan RGB(10,5,3). Gambar 2.5 melukiskan RGB image dari class double.
21
Gambar 2.5
2.14
Bidang warna RGB Image dengan class double.
Kompresi Citra Digital Kompresi citra merupakan salah satu bentuk kompresi data. Kompresi
citra digital adalah proses digital dimana jumlah data (dalam ukuran bit) pada citra direduksi sesuai dengan yang diinginkan (Thyagarajan 2006). Pada kompresi citra, pengodean entropy biasanya didahului oleh dekorelasi untuk mengurangi redundansi pada data citra dan kompresi lossy didahului oleh kuantisasi. Keefektifan kompresi citra dapat diikur melalui kuantitas kompresi yang dicapai dan melalui kualitas citra yang direkonstruksi (Hafsah 2007). Citra bitmap mengambil banyak memori, kompresi citra mengurangi jumlah memori yang dibutuhkan untuk menyimpan sebuah citra di dalam disk. Secara sederhana, citra RGB 8 bit berukuran 1600 x 1200 membutuhkan 1600 x 1200 x 3 bytes = 5760000 bytes = 5.5 MB di memori. Ini adalah ukuran citra tanpa kompresi. Citra bitmap merepresentasikan setiap piksel dengan setiap bilangan satu per satu. Hal ini membuat citra yang disimpan dalam format bitmap sangat bergantung dengan ukuran (resolusi). Gambar 2.6 menampilkan citra dengan format bitmap yang ditampilkan dengan penampil citra IrfanView. Rasio kompresi (compression ratio) adalah perbandingan antara citra hasil kompresi dengan citra sebelum dilakukan kompres, sebagai contoh untuk citra yang disebutkan di atas, disimpan sebagai file JPEG dengan ukuran 512 KB dan rasio kompresi sebesar 0.5 MB : 5.5 MB = 1:11 = 9.09%.
22
Gambar 2.6
Citra format bitmap yang ditampilkan dengan penampil citra IrfanView.
Citra di atas berukuran 512 pada arah vertikal dan 512 piksel pada arah horisontal, merupakan citra RGB dengan kedalaman warna 8 bit setiap bidang warna, sehingga kedalaman warna untuk setiap piksel adalah 24 bit. Oleh karena itu, ukuran file citra di memori adalah 512 x 512 x 24 = 6291456 bit = 786432 byte = 768 KB. Informasi detail citra ini ditampilkan dalam Gambar 2.7.
Gambar 2.7
Informasi detail file citra lena.bmp melalui IrfanView.
23 Dari gambar di atas, terlihat bahwa citra tersebut membutuhkan ruang penyimpanan yang sama besar dengan memori yang dibutuhkan oleh citra tersebut untuk ditampilkan, yaitu 768 KB karena citra disimpan dalam format bitmap.
2.14.1 Teknik Kompresi Citra Digital Ada dua macam teknik untuk mengompres citra, yaitu lossless dan lossy (Castleman 1996). Teknik lossless memberikan jaminan bahwa citra yang telah di-decompress benar-benar identik dengan citra sebelum dikompres, misalnya Run Length encoding, Huffman encoding, Entropy coding (Lempel/Ziv), dan area coding (Hafsah 2007). Ketika sebuah citra dikompres secara lossless maka pengulangan dan kemungkinan-kemungkinan digunakan untuk merepresentasikan semua informasi menggunakan memori yang lebih sedikit. Citra asli juga kemudian dapat dikembalikan (decompress). Salah satu metode kompresi lossless yang paling sederhana adalah Run-Length Ecoding (RLE). RLE meng-encode nilai yang sama yang berulang sebagai satu bagian pada data secara keseluruhan.
70, 5, 25, 5, 27, 4, 26, 4, 25, 6, 24, 6, 23, 3, 2, 3, 22, 3, 2, 3, 21, 3, 5, 2, 20, 3, 5, 2, 19, 3, 7, 2, 18, 3, 7, 2, 17, 14, 16, 14, 15, 3, 11, 2, 14, 3, 11, 2, 13, 3, 13, 2, 12, 3, 13, 2, 11, 3, 15, 2, 10, 3, 15, 2, 8, 6, 12, 6, 6, 6, 12, 6, 64
Gambar 2.8
Contoh Run-length Encoding.
24 Pada Gambar 2.8, gambar rumah hitam putih telah dikompres dengan menggunakan RLE. Gambar bitmap tersebut terlihat sebagai satu string panjang dari piksel hitam atau putih, encoding-nya adalah berapa banyak byte warna yang sama muncul setelah warna yang lain. 70, 5, 5, 4, 4, 6, 6, 3, 3, 3, 3, 3, 3, 14, 14, 3, 3, 3, 3, 3, 3, 6, 6,
25, 27, 26, 25, 24, 23, 2, 2, 5, 5, 7, 7, 16, 15, 11, 11, 13, 13, 15, 15, 12, 12,
3, 3, 2, 2, 2, 2,
22, 21, 20, 19, 18, 17,
2, 2, 2, 2, 2, 2, 6, 6,
14, 13, 12, 11, 10, 8, 6, 64
Gambar 2.9
15, 5, 6, 4, 4, 6, 6, 3, 3, 3, 3, 3, 3, 14, 14, 3, 3, 3, 3, 3, 3, 6, 6,
0, 15, 0, 15, 0, 10, 15, 0, 10, 15, 0, 12, 15, 0, 11, 15, 0, 10, 15, 0, 9, 15, 0, 8, 2, 3, 15, 0, 7, 2, 3, 15, 0, 6, 5, 2, 15, 0, 5, 5, 2, 15, 0, 4, 7, 2, 15, 0, 3, 7, 2, 15, 0, 2 15, 0, 1 15, 11, 2, 14, 11, 2, 13, 13, 2, 12, 13, 2, 11, 15, 2, 10, 15, 2, 8, 12, 6, 6, 12, 6, 15, 0, 15, 0, 15, 0, 15, 0, 4
Contoh hasil Run-length Encoding.
Pada gambar di atas, hasil encoding yang baru adalah 113 nibbles, satu nibble adalah 4 bit dan dapat merepresentasikan nilai di antara 0 dan 4, sehingga hanya dibutuhkan 113 x 4 : 8 = 56.5 byte untuk menyimpan semua nilai-nilai tersebut. Kapasitas penyimpanan ini lebih kecil dari 93 byte jika citra disimpan dengan citra 1 bit dan jauh lebih kecil dari 750 byte jika digunakan satu byte untuk setiap piksel. Beberapa aplikasi tidak membutuhkan pengembalian data keseluruhan dari citra aslinya, oleh karena itu digunakan teknik lossy. Contoh teknik ini adalah transform coding (SVD/KLT/DCT/Wavelets/ Gabor), vector quantisation, metode segmentasi
dan
aproksimasi,
metode
spline
aproksimasi
(Interpolasi
Bilinear/Regulariasi), dan Fractal Coding (texture synthesis, iterated function system (IFS), recursives IFS (RIFS)) (Castleman 1996).
25 Teknik kompresi citra lossy mengambil keuntungan dari ketidakmampuan mata manusia untuk melihat hal-hal yang sangat kecil dan dari fakta bahwa beberapa jenis informasi jauh lebih penting daripada informasi yang lainnya. Kompresi lossy ditentukan oleh nilai akurasi citra terekonstruksi yang dapat diterima sejalan dengan peningkatan kompresi. Jika distorsi yang terjadi dapat ditolerir maka peningkatan pada kompresi menjadi signifikan (Gonzales dan Woods 2002). Keuntungan kompresi citra lossy adalah kecacatannya tidak dapat terdeteksi melalui penglihatan manusia. Contoh kompresi lossy adalah JPEG. Pada JPEG implementasi format file kompresinya berdasarkan DCT bersama dengan algoritme lossless akan memberikan rasio kompresi yang sangat bagus. Cara JPEG bekerja sangat cocok untuk citra dengan rentang tonal yang kontinu seperti foto, logo, teks hasil pemindaian, dan citra-citra yang lain dengan banyak kontur ketajaman/garis. Gambar berikut menampilkan informasi detail file citra dalam format JPEG.
Gambar 2.10 Contoh informasi file citra dengan format JPEG. Informasi yang tertera pada gambar di atas menyebutkan bahwa citra berukuran 1156 x 1156 piksel. Ukuran memori yang dibutuhkan untuk ditampilkan adalah sebesar 1156 x 1156 x 24 = 32072064 bit = 4009008 byte =
26 3915.05 KB = 3.82 MB. Tetapi, dengan menggunakan format JPEG citra tersebut hanya membutuhkan 114.77 KB untuk disimpan di dalam disk. Penampil IrfanView melakukan decoding (decompress) terhadap file citra yang disimpan di dalam disk sebelum ditampilkan sehingga ukurannya di dalam disk yang semula 114.7 KB menjadi 3.82 MB setelah di-load ke dalam memori (RAM) komputer.
2.14.2 Kompresi Citra dengan SVD Diberikan citra A matriks real dengan ukuran m x n dan rank(A) = r. Matriks ini tidak dipandang sebagai transformasi linear atau sebuah objek aljabar. Matriks ini secara sederhana merupakan tabel dengan mn bilangan dan akan ditentukan aproksimasi yang menangkap tampilan data yang paling signifikan. Rank matriks menunjukkan banyaknya kolom atau baris yang saling bebas linear, maka rank juga merupakan ukuran redundansi (Kalman 1996). Matriks dengan rank rendah memiliki banyak redundansi sehingga dapat diekspresikan dengan lebih efisien. Sebagai contoh, misalkan B merupakan matriks berukuran m x n dengan rank 1, maka semua kolom-kolom dari B merupakan kelipatan antara satu dan lainnya (ruang kolom berdimensi 1). Jika u merupakan basis dari ruang kolom B, maka setiap kolom merupakan kelipatan dari u. Misalkan kolom ke-j dari B adalah vju maka B v1u v2u vnu uvT . Sebanyak mn entri matriks B ditentukan oleh m entri pada kolom dan n entri pada baris. Dengan analogi yang sama dapat diperoleh kompresi yang sangat besar untuk A jika A dapat diaproksimasi oleh matriks dengan rank 1. Akan lebih sedikit menyimpan m + n entri untuk merepresentasikan aproksimasi dengan rank 1 untuk A daripada sebanyak mn entri matriks A (Kalman 1996). Pertama kali ditentukan SVD dari matriks A, yaitu A = UVT dimana 0
0 , diag(σ1, σ2, ..., σr) dan σ1 ≥ σ2 ≥ ... ≥ σr > 0. Matriks U dan V 0
ortogonal dan σi merupakan nilai singular dari A. Aproksimasi dengan rank p dari A dengan p ≤ r adalah Ap = UppVpT di mana p adalah matriks tetapi hanya diambil sebanyak p nilai singular, jadi p berukuran p x p. Matriks Up berisi p
27 kolom pertama U dan Vp berisi p kolom pertama V. Dekomposisi seperti ini cukup menarik karena Up, p, dan VpT menghasilkan aproksimasi terbaik dengan rank p untuk A (Ranade et al. 2006) dalam terminologi bahwa rekonstruksi ketiga matriks tersebut menghasilkan aproksimasi dengan rank p yang paling baik untuk A. Ukuran baik atau tidaknya aproksimasi tersebut bisa menggunakan ukuran secara matematis seperti MSE atau penilaian secara kualitatif, yaitu menurut pengamatan secara kasat mata. Jika SVD dari A adalah A = UVT, diperoleh A = σ1U1V1T + σ2U2V2T+ ... + σrUrVrT + 0Ur+1Vr+1T + 0 + ... Karena nilai singular pada disusun dengan urutan dari yang terbesar ke yang terkecil (decreasing order) maka suku-suku yang nilai singularnya sangat kecil tidak banyak berpengaruh pada citra A. Dari sini dapat ditentukan aproksimasi untuk A dengan rank yang lebih kecil dari r, misalkan Ap = σ1U1V1T + σ2U2V2T + ... + σpUpVpT, dan p < r. Dengan melakukan seperti ini matriks citra akan disimpan dengan sejumlah bilangan yang berulang (vektor yang tidak bebas linear), sehingga ketika disimpan file citra akan mengambil ruang penyimpanan yang lebih kecil. Langkah kompresi citra dengan metode SVD seperti yang diuraikan di atas adalah dengan mengambil sebanyak p (atau kurang) kolom dari U, p kolom dari V, dan p x p sub-matriks dari . Representasi ini cukup baik jika A memiliki rank rendah.
2.14.3 Kompresi Citra dengan SSVD Diberikan A matriks berukuran N x N dengan N = n2 untuk suatu bilangan bulat n. Kemudian dipilih operator shuffle P untuk A. Ranade et al. (2006) membentuk X = P(A) dengan langkah sebagai berikut: (i)
Memecah A menjadi blok berukuran n x n
(ii)
Mengambil blok ke-i pada urutan mayor baris dan menyusun kembali nilai pixel citra pada mayor baris menjadi baris ke-i dari X. Untuk lebih jelasnya, diberikan rumus sebagai berikut: i j X n , (i mod n)n ( j mod n) A[i, j ] n n
(2.16)
28 Sebagai contoh, diberikan matriks sebagai berikut 1 2 3 4 5 6 7 8 A 9 10 11 12 13 14 15 16 Matriks di atas berukuran 4 x 4 dan 4 = 22, sehingga n = 2. Pertama kali matriks A dipecah menjadi blok n x n, yaitu blok berukuran 2 x 2 sebagai berikut 1 2 3 4 5 6 7 8 A 9 10 11 12 13 14 15 16 1 2 Diperoleh empat blok berukuran n x n dengan urutan blok ke-1 adalah , 5 6 3 4 9 10 blok ke-2 adalah , blok ke-3 adalah , dan blok ke-4 adalah 7 8 13 14 11 12 15 16 . Kemudian baris-baris pada blok ke-i disusun kembali menjadi baris ke-i. Baris-baris blok ke-1 disusun menjadi baris ke-1 dari X. Baris-baris blok ke-2 disusun menjadi baris ke-2 dari X. Baris-baris blok ke-3 disusun menjadi baris ke3 dari X. Terakhir, baris-baris blok ke-4 disusun menjadi baris ke-4 dari X. Dengan demikian, diperoleh matriks hasil shuffle sebagai berikut: 1 2 5 6 3 4 7 8 X 9 10 13 14 11 12 15 16 Setiap citra dalam penyusunan ini, yaitu setiap kolom dari X dibangun dengan mengambil satu elemen dari setiap blok A. Dalam kasus SSVD, citra-citra penyusunnya merupakan sub-sample dari citra asli yang memiliki resolusi rendah. Titik ke-j dari setiap sample diambil dari n x n blok tunggal citra asli. Sebagaimana telah disebutkan sebelumnya bahwa untuk memperoleh citra
29 kompresi dilakukan mengambil p kolom dari U, p kolom dari V dan p x p submatriks dari . Representasi ini akan baik jika X memiliki rank rendah. Dengan melakukan shuffle, Ranade et al. (2006) mengharapkan X memiliki rank lebih rendah dari sebelumnya.
2.14.4 Atribut Kompresi Citra Digital Kompresi citra digital ditentukan oleh tiga faktor utama, yaitu: 1.
Rasio Kompresi
2.
Kecepatan Kompresi
3.
Kualitas Citra
Rasio kompresi memberikan indikasi seberapa banyak kompresi yang dicapai terhadap citra yang telah diproses. Rasio kompresi menunjukkan kinerja algoritme atau teknik kompresi citra yang digunakan. Hubungan antara rasio kompresi dengan kualitas citra adalah salah satu hal yang penting untuk dijadikan bahan pertimbangan dalam pengolahan citra (Hafsah 2007). Waktu kompresi dan waktu mengekstrak didefinisikan sebagai kuantitas waktu yang digunakan untuk melakukan kompresi dan mengekstrak sebuah citra. Ukuran kecepatan tersebut bergantung pada: -
Kompleksitas algoritme kompresi
-
Efesiensi implementasi perangkat lunak atau perangkat keras dari algoritme
-
Kecepatan processor atau perangkat keras tambahan/pendukung
Kualitas citra menunjukkan apakah citra kompresi masih sama dengan citra aslinya atau tidak. Metode kompresi citra dapat dikategorikan sebagai kompresi lossy dan lossless. Kinerja kedua metode ini dipengaruhi oleh tingkat kualitas citra yang diinginkan oleh pengguna. Hubungan antara rasio kompresi berbanding terbalik dengan kecepatan kompresi dan kualitas citra. Jika rasio kompresinya besar yang menandakan bahwa rasio baik, maka kecepatan kompresi dan kualitas citra akan rendah, sedangkan jika kecepatan kompresi dan kualitas citra tinggi, maka rasio kompresi yang dihasilkan akan kecil yang berarti bahwa rasio kompresi yang dihasilkan
30 kurang baik (Hafsah 2007).
2.15
Citra dan Pengolahan Citra di MATLAB
2.15.1 Membaca dan Menulis File Citra Sebelum melakukan pengolahan dengan MATLAB, sebuah citra harus dibaca terlebih dahulu. Setelah selesai melakukan pengolahan, citra hasil pengolahan dapat disimpan (save) atau ditulis (write) kembali ke dalam sebuah file dengan format yang sama. Untuk melakukan pembacaan dan penulisan file citra ke dan dari MATLAB digunakan fungsi imread dan imwrite. Fungsi-fungsi ini membutuhkan toolbox image processing. Tabel 2.1 Fungsi untuk membaca dan menulis file citra pada MATLAB Fungsi Imread(namafile) Imwrite (namafile,format)
Kegunaan Membaca sebuah citra. Nama file citra yang akan dibaca ditulis dengan diapit tanda petik tunggal ‘ ‘ Menulis citra ke file. Format diisi dengan format citra dan ditulis dengan diapit tanda petik tunggal ‘ ‘
Contoh penggunaannya sebagai berikut. >> rgb=imread('peppers.png');
Sementara, perintah >> imwrite(rgb,'mypeppers.tif');
memanggil fungsi imwrite untuk menulis citra rgb ke dalam file dengan nama mypeppers.tif. Fungsi ini menentukan format citra yang digunakan berdasarkan
ekstensi dari nama file-nya, dalam hal ini adalah TIF. Namun, kita juga bisa menggunakan nama file untuk tujuan yang berbeda. Untuk kasus ini, kita bisa menambahkan argumen ketiga pada perintah imwrite untuk memberitahu format citra yang digunakan. Contohnya sebagai berikut: >> imwrite(rgb,'test_image.study_013','tif');
31 Perintah di atas digunakan untuk menyimpan file citra dengan nama test_image.study_013 dalam format TIF.
Kebanyakan format file citra mendukung beberapa bentuk kompresi. Hal ini berarti bahwa citra akan mengambil ruang penyimpanan yang lebih kecil daripada ukuran yang diperoleh berdasarkan hasil perhitungan sederhana (seperti yang pernah dilakukan di atas). Sebagai contoh, array rgb di atas mengambil memori sebesar 576 KB. >> bytes_in_memory_peppers = numel(rgb)
bytes_in_memory_peppers =
589824
Jika citra tersebut disimpan dalam format citra yang menggunakan kompresi maka akan mengambil ruang memori yang lebih kecil. Sebagai contoh, jika citra di atas disimpan dalam format PNG. >> imwrite(rgb,'mypeppers.png') >> info = imfinfo('mypeppers.png'); >> bytes_on_disk_peppers_png = info.FileSize
bytes_on_disk_peppers_png =
287589
Kemudian dihitung rasio kompresinya >> CR=bytes_in_memory_peppers/bytes_on_disk_peppers_png
CR =
2.0509
Format file PNG menggunakan kompresi lossless. Hal ini berarti kita dapat mengembalikan data file citra asli dengan tepat.
32
>> peppers2=imread('mypeppers.png'); >> isequal(rgb,peppers2)
ans =
1
Format file citra yang lain, seperti JPEG, menggunakan kompresi lossy. Dengan kompresi lossy, karakteristik sistem penglihatan manusia dieksploitasi untuk mengurangi ukuran di disk, tetapi piksel asli tidak dapat dikembalikan dengan tepat. >> imwrite(rgb,'peppers.jpg'); >> info=imfinfo('peppers.jpg'); >> bytes_on_disk_peppers_jpg = info.FileSize
bytes_on_disk_peppers_jpg =
23509
Kemudian dihitung rasio kompresinya >> CR=bytes_in_memory_peppers/bytes_on_disk_peppers_jpg
CR =
25.0893
Terlihat bahwa rasio kompresi menggunakan JPEG jauh lebih besar daripada menggunakan PNG. Akan tetapi, kompresi JPEG akan mengurangi kualitas citra. JPEG bekerja dengan baik dalam hal mengurangi ruang yang dibutuhkan untuk menyimpan dengan tanpa memperhitungkan kualitas citra.
2.15.2 Menampilkan Citra di MATLAB Untuk menampilkan sebuah citra di MATLAB sebagai berikut
33 Tabel 2.2 Fungsi untuk menampilkan citra Fungsi imagesc(x) imshow(x)
Kegunaan Menampilkan citra yang direpresentasikan oleh matriks x Menampilkan citra yang direpresentasikan oleh matriks atau file dengan nama x
MATLAB menampilkan citra di dalam sebuah jendela yang disebut dengan Figure. Contoh penggunaan perintah imshow adalah sebagai berikut. >> imshow('peppers.jpg')
Perintah di atas digunakan menampilkan citra dalam sebuah jendela. Hasil dari perintah di atas ditampilkan dalam Gambar 2.11.
Gambar 2.11 Menampilkan file citra dalam MATLAB. Perintah >> subplot(1,2,1) >> imshow('peppers.png') >> limits=[232 276 215 248]; >> axis(limits) >> title('Original');
34
>> subplot(1,2,2) >> imshow('peppers.jpg') >> axis(limits) >> title('JPEG Compression');
Akan menampilkan perbandingan secara detail antara citra asli dengan citra hasil kompresi menggunakan format JPEG. Perintah subplot digunakan untuk ‘memecah’ jendela penampil citra pada MATLAB sesuai dengan keinginan. Perintah subplot(1,2,x) akan membagi jendela penampil (Figure) sehingga memiliki 1 baris dan 2 kolom. Sementara argumen x digunakan sebagai pengindeks (lokasi) di mana plot akan ditampilkan. Hasil dari perintah di atas adalah sebagai berikut.
Gambar 2.12 Menggunakan subplot. Pada gambar di atas, terlihat bahwa kompresi JPEG membuat kualitas citra berkurang. Akan tetapi, kemampuan visual manusia masih bisa melihatnya dengan baik.
BAB III METODE PENELITIAN
Pada bab ini dipaparkan langkah-langkah yang digunakan untuk membahas permasalahan yang diambil dalam penelitian. Di bagian ini juga disebutkan instrumen dan metode yang digunakan untuk melakukan pemampatan data baik menggunakan SVD maupun SSVD.
3.1
Metode Penelitian Penelitian ini menggunakan metode studi literatur dan kemudian
mengimplementasikan metode kompresi citra ke dalam program komputer menggunakan software MATLAB. Pada bagian awal, diberikan contoh implementasi metode SVD dan SSVD pada beberapa matriks. Langkah ini dilakukan untuk melihat apakah SSVD selalu bekerja lebih baik daripada metode SVD. Selain itu pada penelitian ini kedua metode juga diterapkan pada sebuah citra yang direpresentasikan oleh sebuah matriks. Tujuan dari langkah ini adalah untuk mengetahui apakah metode SSVD selalu memberikan hasil yang lebih baik dibandingkan dengan metode SVD. Citra yang digunakan adalah citra tes standar untuk
pengolahan
citra,
yaitu
lena484.jpg.
http://www.imagecompression.info/test_images.
Citra
Selain
ini
diunduh
dari
citra
tersebut,
juga
digunakan beberapa citra yang lain sebagai alat uji dari sampel citra yang berbeda-beda.
3.2
Instrumen Penelitian Instrumen yang digunakan dalam penelitian ini terdiri atas dua jenis, yaitu
perangkat keras (hardware) dan perangkat lunak (software). Perangkat keras yang digunakan adalah sebuah notebook/laptop dengan spesifikasi sebagai berikut: a. Processor
: Intel® Core™ i5-2520M CPU @ 2.50GHz
b. Physical Memory
: 6144 MB RAM
c. Display Adapter
: NVIDIA GeForce 315M 2133 MB
d. Display Mode
: 1366 x 768 (32 bit) (60Hz) 35
36
Perangkat lunak yang digunakan memiliki spesifikasi sebagai berikut: a.
OS
: Windows 7 Professional 32-bit
b.
OS Version
: 6.1 Service Pack 1, Build 7601
c.
MATLAB Version
: 7.1.0.246 (R14) Service Pack 3
d.
Java VM Version
: Java 1.5.0 with Sun Microsystems Inc. Java HotSpot™ Client VM
e.
MATLAB Toolbox
: Image Processing Toolbox Version 5.1
f.
Image Viewer
: IrfanView for Windows 9x, NT, 2000, XP, Vista, and 7 Version 4.32.
3.3
Langkah Penelitian Langkah-langkah yang dilakukan pada penelitian ini terdiri atas dua tahap.
Tahap pertama adalah menyiapkan alat uji berupa program yang disusun menggunakan
bahasa
pemrograman
MATLAB.
Tahap
kedua
adalah
membandingkan efektivitas teknik shuffle yang diajukan oleh Ranade et al. (2006) dengan cara menerapkan teknik tersebut terhadap metode SVD untuk beberapa citra dan kemudian menghitung MSE yang dihasilkan oleh setiap metode. Tahap ketiga adalah memberikan contoh kontra ketidakefektifan teknik shuffle tersebut.
3.3.1
Menyiapkan Alat Uji Pada tahap ini, dilakukan langkah-langkah sebagai berikut:
1.
Mengidentifikasi masalah Masalah pada penelitian ini adalah klaim dari Ranade et al. (2006) yang menyatakan bahwa teknik shuffle yang diterapkan pada metode SVD selalu memberikan hasil yang lebih baik daripada tanpa di-shuffle sebelumnya. Ukuran yang digunakan oleh Ranade et al. (2006) adalah MSE antara citra asli dengan citra hasil kompresi oleh setiap metode.
2.
Menentukan tujuan Tujuan dari penelitian ini adalah untuk menunjukkan apakah klaim yang dinyatakan tersebut selalu berlaku untuk setiap matriks citra.
37
3.
Studi literatur Studi literatur dilakukan untuk mengkaji metode kompresi citra menggunakan SVD dan SSVD. Selain itu, studi literatur juga dilakukan untuk mengkaji penelitian-penelitian terdahulu yang terkait.
4.
Menyusun algoritme Setelah melakukan studi literatur, langkah selanjutnya adalah menyusun algoritme kompresi citra menggunakan metode SVD dan SSVD.
5.
Menyusun program komputer Algoritme yang telah disusun kemudian diimplementasikan ke dalam salah satu bahasa pemrograman komputer yaitu MATLAB. MATLAB dipilih karena fungsi-fungsi yang berkaitan dengan SVD telah tersedia dan siap digunakan. Di samping itu, dengan adanya Image Processing Toolbox, MATLAB juga mendukung pengolahan citra sehingga operasi-operasi pada citra dapat dilakukan. Program yang disusun diharapkan menerima input berupa sebuah citra dan parameter kompresi. Setelah dijalankan, program memberikan output berupa citra hasil kompresi.
Selain program utama, disusun juga script MATLAB lain yang digunakan untuk menentukan nilai MSE antara dua buah matriks dan untuk mengambil informasi ukuran file citra yang tersimpan di dalam hard disk. 3.3.2
Membandingkan Efektivitas Teknik Shuffle Pertama dijelaskan terlebih dahulu mengenai langkah memperoleh citra
hasil kompresi menggunakan program yang telah disusun. 1.
Kompresi Citra Berwarna Menggunakan SVD Pada tahap ini akan diterapkan metode SVD terhadap citra berwarna. Secara struktur, citra berwarna terdiri atas tiga bidang warna. Sehingga sebuah citra berwarna direpresentasikan dengan tiga buah matriks. Tahap pengerjaan kompresi citra berwarna menggunakan metode SVD dapat dilihat pada flowchart berikut.
38
Citra, p
A = imread(citra)
AR = A(:,:,1) AG = A(:,:,2) AB = A(:,:,3) Tentukan SVD untuk AR, AG, dan AB ARp = URp RpVRpT
AGp = UGp GpVGpT
ABp = UBp BpVBpT
Ap(:,:,1) = ARp Ap(:,:,2) = AGp Ap(:,:,3) = ABp
Ap
imwrite(Ap, nama_file)
Gambar 3.1
Skema pemrosesan metode SVD untuk citra berwarna.
Nilai MSE dihitung antara A dan Ap dengan cara menghitung rata-rata MSE untuk setiap bidang warna.
2.
Kompresi Citra Berwarna Menggunakan SSVD Pada tahap ini diterapkan metode SSVD terhadap citra berwarna. Secara struktur, citra berwarna terdiri atas tiga bidang warna. Sehingga sebuah citra berwarna direpresentasikan dengan tiga buah matriks. Tahap pengerjaannya bisa dilihat pada flowchart berikut:
39
Citra, p
A = imread(citra)
AR = A(:,:,1) AG = A(:,:,2) AB = A(:,:,3) XR = P(AR) XG = P(AG) XB = P(AB)
shuffle
Tentukan SVD untuk XR, XG, dan XB XRp = URp RpVRpT
XGp = UGp GpVGpT
Ap(:,:,1) = P–1(XRp) Ap(:,:,2) = P–1(XGp) Ap(:,:,3) = P–1(XBp)
XBp = UBp BpVBpT
re-shuffle
Ap
imwrite(Ap, nama_file)
Gambar 3.2
Skema pemrosesan metode SSVD.
Nilai MSE dihitung antara A dan Ap (bukan Xp) dengan cara menghitung rata-rata MSE untuk setiap bidang warna.
Untuk membandingkan perbedaan metode SVD dan SSVD dilakukan dengan cara mengukur kualitas citra hasil kompresi dari masing-masing metode. Untuk menentukan kualitas citra yang telah dikompres digunakan pengukuran baku yaitu MSE. Semakin kecil nilai MSE antara citra asli dan citra hasil
40
kompresi, semakin baik kompresi citra tersebut (Hafsah 2007). Selain MSE, ukuran file juga digunakan sebagai bahan perbandingan efektivitas teknik shuffle yang diterapkan pada metode SVD dalam mengompres citra. MSE mengukur kinerja metode dari sisi matematis dan kualitas citra, akan tetapi tinjauan utama dari penelitian ini adalah dari sisi kompresi yang berkaitan erat dengan ruang yang dibutuhkan oleh file citra untuk disimpan ke dalam media penyimpanan. Kompresi yang baik akan menghasilkan ukuran file citra yang lebih kecil dibandingkan dengan file citra aslinya. Akan tetapi, walapun ukuran file-nya lebih kecil perlu juga dilihat kualitas citra yang dihasilkan untuk menjaga kelayakan citra ketika dilihat secara kasat mata. Salah satu ukuran kelayakan tersebut bisa digunakan MSE. Oleh karena itu, kedua ukuran ini yaitu MSE dan ukuran file perlu digunakan untuk mengukuran efektivitas suatu kompresi. Pada penelitian ini dilakukan uji coba terhadap beberapa matriks citra dan diterapkan metode kompresi SVD dan SSVD dengan menggunakan beberapa parameter kompresi. Parameter kompresi yang dimaksud adalah p dimana Ap merupakan aproksimasi rank p untuk A. Setelah diterapkan metode kompresi, diperoleh citra hasil kompresi. Untuk setiap parameter kompresi, dihitung MSE dan ukuran file antara citra asli dengan citra hasil kompresi baik menggunakan metode SVD maupun metode SSVD sehingga diperoleh data MSE dan ukuran file yang dihasilkan oleh metode SVD dan SSVD untuk setiap parameter.
SVD
Matriks citra A
MSE(A, Ap)
shuffle
X = P(A)
Gambar 3.3
Ap (rank p)
MSE(A, Ap)
SVD
Xp (rank ??)
re-shuffle
Ap = P–1(Xp) (rank ???)
Diagram penghitungan MSE antara citra asli dengan citra hasil kompresi.
41
Unjuk kinerja masing-masing metode dapat dilihat dari respon grafik MSE dan ukuran file untuk setiap nilai rank/term yang berbeda-beda. Dengan menggunakan grafik ini dapat dilihat kelebihan dan kekurangan kedua metode kasus per kasus satu sama lain. Analisis data tidak dapat dilakukan secara statistik karena pengumpulan data MSE dan ukuran file diperoleh dari sampel citra yang berbeda-beda. Dari uraian di atas, digambarkan langkah-langkah yang dilakukan dalam penelitian ini sebagai berikut :
Mulai
Mengidentifikasi masalah Menentukan tujuan Studi literatur Menyusun algoritme Menyusun program dengan MATLAB
Ulangi untuk beberapa nilai p
Kompresi dengan parameter p terhadap citra berwarna A menggunakan SVD dan SSVD
Membandingkan MSE dan ukuran file citra yang dihasilkan oleh kedua metode dan simpulkan
Selesai Gambar 3.4
Skema langkah-langkah penelitian.
42
BAB IV HASIL DAN PEMBAHASAN Bab ini menjelaskan tentang hasil uji coba yang telah dilakukan untuk menjawab pertanyaan yang diberikan pada perumusan masalah. Pembahasan diawali dengan penjelasan mengenai penelitian kompresi citra yang pernah dilakukan oleh peneliti terdahulu serta argumentasi matematis untuk menjawab pertanyaan tersebut. Selanjutnya diberikan juga algoritme kompresi citra baik menggunakan metode SVD maupun menggunakan metode SSVD dan terakhir disajikan ilustrasi penerapan kedua metode dan membandingkan hasilnya berdasarkan MSE dan ukuran file citra hasil kompresi terhadap beberapa sampel citra.
4.1.
Penelitian Kompresi Citra Banyak peneliti yang telah menggunakan teknik SVD untuk melakukan
kompresi terhadap citra. SVD dipilih sebagai salah satu teknik untuk kompresi citra karena pada SVD dapat dilakukan pemotongan rank. Teknik kompresi data menggunakan SVD pertama kali dinyatakan oleh Eckart dan Young (1936) dalam artikelnya yang berjudul The Approximation of One Matrix by Another of Lower Rank. Dalam artikel tersebut, Eckart dan Young (1936) menuliskan teorema mengenai aproksimasi rank rendah untuk sebuah matriks. Teorema tersebut menyebutkan bahwa jika matriks A berukuran m x n p
r
dengan rank(A) = r dan SVD dari A adalah A iU iVi maka Ap iU iVi T T
i 1
i 1
merupakan aproksimasi terbaik dengan rank p untuk A, yaitu Ap meminimumkan m
n
(a i 1 j 1
ij
xij ) 2 trace A X
T
A X
untuk setiap matriks X dengan rank p atau kurang (Greenacre 1984). Menurut teorema ini, aproksimasi dengan rank p yang paling baik adalah Ap yang dibentuk dari p nilai singular pertama dari A dan p vektor-vektor singular Ui dan Vi pertama dari A. Teorema tersebut menjamin ketunggalan solusi permasalahan minimisasi 43
44 di atas, yaitu jika ada matriks B dengan rank p yang memenuhi permasalahan p
tersebut maka B Ap iU iVi T . Artinya, tidak mungkin ditemukan matriks i 1
lain sebagai aproksimasi untuk A dengan rank p selain Ap. Penggabungan SVD dengan teknik lain juga dikembangkan oleh beberapa peneliti. Salah satunya adalah penelitian Waldemar dan Ramstad (1997) yang melakukan penelitian tentang kompresi citra dengan menggabungkan teknik KLT dan SVD. Teknik ini digunakan untuk menentukan transformasi blok yang sesuai. Waldemar dan Ramstad membandingkan pendekatan teknik KLT-SVD dengan sistem pengodean KLT. Dari perbandingan ini kemudian ditemukan analisis dengan pendekatan sintetis yang menggunakan pertukaran antara sistem pengodean KLT dan gabungan KLT-SVD. Pertukarannya diimplementasikan dengan menggunakan standar global rate-distortion. Kesimpulan penelitian itu adalah penggunaan metode gabungan KLT-SVD lebih baik dibandingkan dengan penggunaan KLT. Namun kompleksitas metode gabungan KLT-SVD cukup tinggi (Hafsah 2007). Teknik SVD menghasilkan aproksimasi rank k terbaik untuk suatu matriks, akan tetapi secara umum, bahkan aproksimasi SVD sekecil apapun tetap membutuhkan ruang penyimpanan yang lebih besar dibandingkan matriks aslinya jika matriks-nya adalah matriks jarang (sparse matrix) Kolda dan O’Leary (1998). Algoritme SSVD merupakan varian SVD yang diajukan oleh Ranade et al. (2006). Ranade mengadaptasi penelitian Waldemar dan Ramstad (1997) dengan mengganti operator permutasi pada KLT-SVD dengan shuffle (Hafsah 2007). Teknik shuffle pada SSVD sangat menguntungkan untuk citra yang memiliki rank rendah. Dampak yang diharapkan dengan melakukan teknik shuffle adalah rank matriks citra yang dihasilkan lebih kecil dibandingkan dengan rank matriks citra aslinya dan setelah dilakukan kompresi kualitas citra yang dihasilkan oleh metode SSVD lebih baik dibandingkan dengan metode SVD. Langkah kompresi citra menggunakan SSVD didahului dengan melakukan permutasi terhadap matriks citra A dengan suatu permutasi independen P yang disebut dengan shuffle (Ranade et al. 2006). Matriks yang dihasilkan, misalkan X
45 = P(A) kemudian didekomposisi menggunakan SVD. Misalkan X p U p pVpT merupakan aproksimasi rank p untuk X. Dari hasil uji coba untuk beberapa citra, diperoleh bahwa untuk nilai p yang sama, citra P–1(Xp) memberikan aproksimasi yang lebih baik untuk A daripada Ap. Akan tetapi, kita juga perlu melihat apakah SSVD memberikan hasil lebih baik daripada metode SVD untuk citra yang lain. Diberikan A matriks berukuran N x N dengan N = n2 untuk suatu bilangan asli n. Ranade et al. (2006) membentuk operator shuffle P sedemikian sehingga X = P(A) dengan langkah sebagai berikut: 1. Memecah A menjadi blok matriks berukuran n x n 2. Mengambil blok ke-i dalam urutan baris utama, kemudian menyusun baris-baris pada blok tersebut menjadi baris ke-i dari X. Secara
matematis,
operator
shuffle
tersebut diekspresikan dalam
persamaan berikut: i j X n , (i mod n)n ( j mod n) A[i, j ] n n
(4.1)
Setiap citra dalam penyusunan ini, yaitu setiap kolom dari X dibangun dengan mengambil satu elemen dari setiap blok A sebagaimana yang didefinisikan di atas. Dalam kasus SSVD, citra-citra penyusunnya merupakan sub-sample dari citra asli yang memiliki resolusi rendah. Titik ke-j dari setiap sample diambil dari n x n blok tunggal citra asli. Sedangkan operator re-shuffle (P–1) digunakan untuk mengembalikan matriks A yang telah di-shuffle menjadi matriks A. Secara matematis, operator reshuffle diekspresikan dalam persamaan berikut: i j A[i, j ] X n , (i mod n)n ( j mod n) n n
4.2.
(4.2)
Algoritme Kompresi Citra
4.2.1. Metode Kompresi SVD Pada dasarnya cara kerja algoritme SVD adalah mengompres citra yang telah direpresentasikan menjadi sebuah matriks dengan cara memotong rank
46 tertentu. Dengan demikian citra yang dikompres tersebut merupakan citra dengan aproksimasi rank SVD citra asli. Sebelum menentukan SVD sebuah citra, pertama mengonversi citra terlebih dahulu menjadi sebuah matriks, yaitu dengan mengambil nilai piksel citra. Untuk mengambil nilai piksel citra asli
dapat menggunakan fungsi
imread() yang termuat di dalam Toolbox Image Processing MATLAB. Nilai-
nilai piksel dari sebuah citra disimpan dalam bentuk matriks. Untuk citra berwarna, matriks citra terdiri atas tiga komponen/bidang warna. Masing-masing komponen merepresentasikan ketiga bidang warna pada citra sehingga memerlukan tiga buah matriks untuk menyimpan informasi ketiga bidang warna tersebut, misalkan Ared, Agreen, dan Ablue. Sedangkan SVD matriks A dicari menggunakan built in function MATLAB yaitu svd() untuk menentukan matriks U, dan V. Langkah berikutnya adalah memotong nilai U, dan V sesuai dengan rank yang diinginkan, misalnya p, sehingga diperoleh nilai Up, p dan Vp. Terakhir matriks Ap diperoleh dengan cara merekonstruksi Up, p dan Vp. Proses ini dilakukan masing-masing terhadap bidang warna Red, Green, dan Blue dari citranya. Terakhir, ketiga bidang warna tersebut disusun kembali menjadi satu matriks hasil kompresi. Berikut ini adalah algoritme kompresi citra menggunakan metode SVD untuk citra berwarna.
Algoritme 1 Metode Kompresi SVD untuk Citra Berwarna 1. Baca file citra 2. Pecah menjadi tiga buah matriks (matriks bidang warna) 3. Tentukan rank aproksimasi p 4. Tentukan SVD dari ketiga matriks 5. Susun matriks Up, p dan Vp dengan hanya mengambil sebanyak p kolom dari masing-masing dekomposisi matriks untuk ketiga matriks bidang warna 6. Susun matriks aproksimasi Ap dengan cara mengalikan Up, p dan VpT
47 untuk ketiga matriks bidang warna 7. Satukan kembali menjadi matriks citra berwarna 8. Simpan hasilnya ke dalam file Kompleksitas algoritme SVD untuk sebarang matriks berukuran m x n adalah O(min(mn2, m2n)), sedangkan untuk matriks persegi adalah O(n3) (Hafsah 2007). Dari keseluruhan proses yang digambarkan oleh Algoritme 1 di atas, terlihat bahwa penyumbang kompleksitas terbesar adalah saat penentuan SVD. Oleh karena itu, kompleksitas Algoritme 1 ditentukan oleh algoritme SVD, yaitu O(min(mn2, m2n)) untuk m ≠ n dan O(n3) untuk m = n (Hafsah 2007).
4.2.2. Metode Kompresi SSVD Langkah awal algoritme kompresi citra menggunakan metode SSVD adalah melakukan proses shuffle terhadap matriks A. Selanjutnya menentukan dekomposisi SVD dari matriks A untuk menentukan matriks U, dan V. Kemudian melakukan pemotongan rank sesuai dengan rank yang diinginkan dan merekonstruksinya
kembali
menjadi
matriks
Xp.
Dilanjutkan
dengan
mengembalikan matriks Xp ke Ap dengan cara menerapkan re–shuffle terhadap matriks Xp. Proses ini dilakukan masing-masing terhadap bidang warna Red, Green, dan Blue dari citranya. Terakhir, ketiga bidang warna tersebut disusun kembali menjadi satu matriks hasil kompresi. Berikut ini adalah algoritme kompresi citra menggunakan metode SSVD untuk citra berwarna.
Algoritme 2 Metode Kompresi SSVD untuk Citra Berwarna 1. Baca file citra 2. Pecah menjadi tiga buah matriks (matriks bidang warna) 3. Tentukan rank aproksimasi p 4. Lakukan shuffle terhadap ketiga matriks bidang warna 5. Tentukan SVD dari ketiga matriks bidang warna 6. Susun matriks Up, p dan Vp dengan hanya mengambil sebanyak p kolom dari masing-masing dekomposisi matriks untuk ketiga matriks
48 bidang warna 7. Susun matriks aproksimasi Ap dengan cara mengalikan Up, p dan VpT untuk ketiga matriks bidang warna 8. Lakukan re–shuffle terhadap ketiga matriks yang diperoleh dari langkah ketujuh 9. Satukan kembali menjadi matriks citra berwarna 10. Simpan hasilnya ke dalam file Proses shuffle mempunyai kompleksitas komputasi O(n2), sedangkan untuk proses SVD mempunyai kompleksitas O(n3) (Hafsah 2007). Kemudian proses re-shuffle mempunyai kompleksitas komputasi O(n2). Jadi, kompleksitas Algoritme 2 ditentukan oleh kompleksitas penentuan SVD, karena pada Algoritme 2 proses SVD mempunyai kompleksitas terbesar, yaitu O(n3).
4.3.
Ilustrasi Metode Kompresi Citra Sebagai ilustrasi penerapan metode kompresi citra menggunakan metode
SVD dan SSVD di atas adalah dengan menerapkan kedua metode tersebut terhadap beberapa matriks berukuran kecil kemudian menghitung MSE hasil kompresi kedua metode. Pertama, menerapkan kedua metode terhadap matriks 1 1 A 1 1
2 5 1 3
3 2 4 4
1 2 1 5
Dengan menggunakan parameter kompresi p = 1, nilai MSE yang dihasilkan1 oleh metode SVD adalah 0.9811 sementara MSE yang dihasilkan oleh metode SSVD adalah 0.6444. Dari hasil tersebut, terlihat bahwa MSE yang diperoleh dari metode SVD lebih besar daripada MSE yang diperoleh melalui metode SSVD. Artinya untuk matriks tersebut, SSVD bekerja lebih baik daripada 1
Penghitungan selengkapnya diberikan pada Lampiran 3
49 SVD dilihat dari nilai MSE yang dihasilkan. Untuk kasus ini SSVD memberikan galat yang lebih kecil dibandingkan SVD. Selanjutnya kedua metode diterapkan terhadap matriks berikut 1 2 3 4 5 6 7 8 B 9 10 11 12 13 14 15 16 Dengan menggunakan parameter kompresi p = 1, nilai MSE yang dihasilkan oleh metode SVD adalah 0.2681 sementara MSE yang dihasilkan oleh metode SSVD adalah 0.7792. Keadaan ini berbalik dari keadaan sebelumnya, yaitu metode SSVD menghasilkan MSE yang lebih besar daripada MSE yang dihasilkan oleh metode SVD. Dari sini kemudian muncul pertanyaan, apakah teorema Eckart-Young tidak dapat diterima dari sisi ketunggalannya? Padahal teorema Eckart-Young menjamin ketunggalan solusi aproksimasi matriks dengan rank yang sama. Untuk menjawabnya, perhatikan tabel berikut. Tabel 4.1 Nilai-nilai MSE dan rank dari matriks A, A1, X1, dan X1–1 Atribut MSE terhadap A rank
Matriks A
A1
X1
X1–1
0.0000 4
0.9811 1
2.9468 1
0.6444 4
Tabel 4.2 Nilai-nilai MSE dan rank dari matriks B, B1, Y1, dan Y1–1 Atribut MSE terhadap B rank
Matriks B
B1
Y1
Y1–1
0.0000 2
0.2681 1
2.1490 1
0.7792 4
Pada contoh di atas, nilai MSE dihitung antara matriks A dengan X1–1 dan matriks B dengan Y1–1. Dari Tabel 4.1 terlihat bahwa MSE yang dihasilkan
50 menggunakan metode SSVD lebih kecil daripada metode SVD. Akan tetapi, rank matriks A dan X1–1 sama (full rank). Terkait dengan Teorema Eckart-Young, matriks A1 memiliki rank 1 dan matriks X1–1 memiliki rank 4. Teorema tersebut menyebutkan bahwa untuk nilai rank yang sama, maka solusinya adalah tunggal. Dengan demikian, hasil ini tidak bertentangan dengan teorema tersebut, karena nilai rank kedua matriks tidak sama. Untuk nilai rank yang sama, yaitu X1 justru memberikan MSE yang jauh lebih besar daripada A1. Kemudian dari Tabel 4.2 terlihat bahwa SSVD memberikan MSE yang lebih besar daripada metode SVD. Dari tabel ini juga terlihat hal yang sama dengan Tabel 4.1, yaitu Y1 juga memberikan MSE yang jauh lebih besar daripada B1 padahal dengan nilai rank yang sama. Hal yang sangat menarik yang terlihat dari Tabel 4.2, yaitu nilai rank matriks B yang semula 2, kemudian diterapkan teknik shuffle dan re-shuffle ternyata menghasilkan matriks dengan rank yang lebih besar (Y1–1). Hal ini mengakibatkan metode SSVD menghasilkan MSE yang lebih besar daripada yang dihasilkan oleh metode SVD.
4.4.
Rancangan Uji Coba Uji coba dilakukan terhadap citra berwarna lena484.jpg. Data citra ini
diunduh dari http://www.imagecompression.info/test_images yang merupakan citra sampel standar dalam pengolahan citra sehingga dapat didistribusikan dan legal digunakan. Data citra tersebut dapat dilihat pada Gambar 4.1.
51
Gambar 4.1
Citra lena484.jpg asli.
Berikut ini adalah atribut dari data citra tersebut.
Gambar 4.2
Atribut file citra lena484.jpg.
Citra di atas merupakan citra dalam format JPEG dengan ukuran file sebesar 38.14 KB dengan resolusi 484 x 484 piksel. Dengan melakukan penghitungan sederhana, file citra memiliki ukuran sebesar 484 x 484 x 24 = 5622144 bits = 702768 byte = 686.3 KB dengan format BMP (bitmap image).
52 Data citra dengan format BMP dapat diunduh dari laman yang sama. Data citra bitmap tidak digunakan dalam uji coba pada penelitian ini. Penyimpanan data citra sangat terkait dengan format yang digunakan. Format bitmap adalah format uncompressed, sehingga ketika dilakukan penyimpanan matriks data citra ke dalam file dengan format bitmap maka software penyimpan file citra tidak akan melakukan kompresi terhadap file yang dihasilkan. Hal ini dikarenakan format citra bitmap menyimpan data sesuai data citra asli, apa adanya. Sebagai contoh data citra di atas, setelah dilakukan kompresi ukuran file citra yang dihasilkan selalu sama (tetap, tidak ada pengurangan). Salah satu cara yang dapat dilakukan agar teknik kompresi ‘terlihat’ bekerja pada citra bitmap adalah dengan menyimpan citra hasil kompresi dalam format JPEG tetapi ekstensi dari file citra tetap, yaitu bitmap (*.bmp). Perintah MATLAB yang dapat digunakan adalah sebagai berikut.
>> imwrite(A, ‘citra_hasil_kompresi.bmp’, ‘JPG’);
Perintah di atas digunakan untuk menyimpan citra yang ada pada variabel A ke dalam file dengan nama citra_hasil_kompresi.bmp dan menggunakan format JPEG. Selain citra tersebut, digunakan juga beberapa citra lain yang diperoleh secara simulatif untuk membandingkan efektivitas penerapan teknik shufffle terhadap metode SVD.
4.5.
Hasil Uji Coba dan Analisis Rasio kompresi adalah salah satu ukuran kemampuan suatu metode dalam
mengurangi
ukuran
file.
Teknik
SVD
memungkinkan
kita
melakukan
pengurangan ukuran file sekecil mungkin, dengan cara memperkecil parameter kompresi. Akan tetapi, ukuran file yang sangat kecil berakibat pada berkurangnya kualitas citra agar dapat dilihat secara kasat mata. Oleh karena itu, pada penelitian ini digunakan ambang batas (threshold) sebesar 90%. Artinya, parameter
53 kompresi diatur sedemikian sehingga kualitas citra hanya berkurang 10% dari kualitas sebenarnya agar masih dapat terlihat secara kasat mata dengan baik. Berdasarkan (2.12) didefinisikan persamaan sebagai berikut. r
e( p )
i p 1 r
i 1
2 i
(4.3) 2 i
Dari persamaan di atas, dengan threshold 90% atau kualitas citra berkurang paling banyak 10% = 0.10 maka p adalah bilangan bulat terkecil sedemikian sehingga e(p) < 0.10. Tabel 4.3 menampilkan beberapa nilai e(p) untuk citra lena484.jpg. Tabel 4.3 Nilai e(p) untuk citra lena484.jpg p
e(p)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0.30836 0.26329 0.23246 0.20837 0.18665 0.16766 0.15645 0.14707 0.13991 0.13334 0.12795 0.12268 0.11823 0.11425 0.11085 0.10741 0.10395 0.10122 0.09867
Terlihat pada tabel di atas, nilai p terkecil yang dapat diterima agar menghasilkan citra dengan kualitas 90% adalah 19. Jika threshold dinaikkan menjadi 95% maka nilai p yang diambil adalah 65 (penghitungan menggunakan MATLAB).
54 Selanjutnya, diterapkan teknik kompresi menggunakan SVD dan SSVD. Pertama, dilakukan kompresi untuk nilai p = 1. Kompresi dilakukan dengan menggunakan bantuan MATLAB dan memanggil script metode kompresi SVD yang telah disusun sebelumnya. Script dipanggil dengan menyertakan parameter nama file citra lena484.jpg dan p = 1. Hasil dari script tersebut adalah sebuah file citra dengan nama SVD_r1_lena484.jpg dengan ukuran sebesar 12 KB.
Gambar 4.3
Citra SVD_r1_lena484.jpg.
55
Gambar 4.4
Atribut file citra SVD_r1_lena484.jpg.
Ukuran file citra tersebut tetap sama dengan sebelumnya yaitu 484 x 484 piksel. Karena komputer menggunakan format penampilan bitmap, maka decoder komputer men-dekompres file citra dan memuatnya ke dalam memori sehingga ukuran file citra di memori tetap, yaitu 686.39 KB. Kualitas citra di atas adalah 69.16% dari kualitas aslinya dengan ukuran berkurang sebesar 26675 bytes = 26.05 KB atau sekitar 68%. Dari sini dapat disimpulkan bahwa metode SVD bekerja dengan baik, akan tetapi kualitas citra tersebut belum dapat dilihat dengan baik secara kasat mata. Untuk membandingkan dengan metode SSVD, langkah selanjutnya adalah menerapkan metode SSVD terhadap file citra dan parameter kompresi yang sama. Kompresi dilakukan dengan menggunakan bantuan MATLAB dan memanggil script metode kompresi SSVD yang telah disusun sebelumnya. Script dipanggil dengan menyertakan parameter nama file citra lena484.jpg dan p = 1. Hasil dari script tersebut adalah sebuah file citra dengan nama SSVD_r1_lena484.jpg dengan ukuran sebesar 16 KB.
56
Gambar 4.5
Citra SSVD_r1_lena484.jpg.
Gambar 4.6
Atribut file citra SSVD_r1_lena484.jpg.
Dari kedua gambar di atas, terlihat bahwa metode SSVD memberikan hasil yang sedikit lebih baik daripada hasil yang diberikan oleh metode SVD tetapi dengan ukuran file yang lebih besar daripada ukuran file yang dihasilkan oleh metode SVD untuk parameter kompresi yang sama. Untuk menjelaskan fenomena ini, dihitung rank citra asli, rank citra hasil kompresi menggunakan SVD, dan
57 SSVD. Hasilnya sebagai berikut. Tabel 4.4 Nilai rank citra lena484.jpg dengan parameter kompresi 1 Bidang Warna Red Green Blue Maksimum Minimum
Asli
Citra SVD
SSVD
484 484 484 484 484
472 465 460 472 465
484 484 484 484 484
Dari tabel di atas, terlihat bahwa untuk parameter kompresi 1, nilai rank yang dihasilkan oleh metode SSVD lebih besar daripada nilai rank yang dihasilkan oleh metode SVD. Hal ini yang menyebabkan rekonstruksi citra yang dihasilkan metode SSVD lebih baik dan ukuran file yang lebih besar daripada citra yang dihasilkan oleh metode SVD. Hasil di atas tidak dapat dijadikan sebagai landasan untuk menentukan apakah teknik shuffle yang diterapkan pada metode SVD bekerja dengan efektif karena kualitas citra yang dihasilkan masih jauh dari harapan. Oleh karena itu, uji coba selanjutnya adalah dengan mengambil parameter kompresi 20 untuk mendapatkan kualitas citra 90% dari citra aslinya. Pertama, untuk metode SVD hasilnya sebagai berikut.
Gambar 4.7
Citra SVD_r20_lena484.jpg.
58 Citra di atas memiliki ukuran file sebesar 25.40 KB. Selanjutnya adalah melakukan metode kompresi SSVD terhadap citra yang sama dengan parameter kompresi p = 20. Hasilnya sebagai berikut.
Gambar 4.8
Citra SSVD_r20_lena484.jpg.
Citra di atas memiliki ukuran file sebesar 26.48 KB. Dari dua hasil tersebut, terlihat bahwa teknik shuffle yang diterapkan pada metode SVD tidak memberikan hasil sesuai dengan harapan karena ukuran file yang dihasilkan ternyata masih lebih besar dibandingkan dengan tanpa di-shuffle sebelumnya. Akan tetapi, secara kasat mata metode SSVD menghasilkan citra yang cukup baik dibandingkan dengan citra hasil kompresi menggunakan metode SVD. Metode SSVD hanya dengan sebanyak 20 term citra esensial (principal images) untuk menghasilkan citra tersebut. Berikut ini adalah nilai rank citra lena484.jpg dengan parameter kompresi p = 20. Tabel 4.5 Nilai rank citra lena484.jpg dengan parameter kompresi 20 Bidang Warna Red Green Blue Maksimum Minimum
Asli
Citra SVD
SSVD
484 484 484 484 484
484 484 484 484 484
484 484 484 484 484
59 Uji coba selanjutnya adalah dengan mengambil parameter kompresi 65 untuk mendapatkan kualitas citra 95% dari citra aslinya. Pertama, untuk metode SVD hasilnya sebagai berikut.
Gambar 4.9
Citra SVD_r65_lena484.jpg.
Citra tersebut memiliki ukuran file sebesar 34.21 KB. Selanjutnya, hasil untuk metode SSVD adalah sebagai berikut.
Gambar 4.10 Citra SSVD_r65_lena484.jpg.
60 Tabel 4.6 Nilai rank citra lena484.jpg dengan parameter kompresi 65 Bidang Warna Red Green Blue Maksimum Minimum
Asli
Citra SVD
SSVD
484 484 484 484 484
484 484 484 484 484
484 484 484 484 484
Citra tersebut memiliki ukuran file sebesar 32.49 KB. Terlihat bahwa selain memberikan kualitas citra yang lebih baik metode SSVD juga memberikan citra hasil kompresi dengan ukuran file yang lebih kecil. Dengan demikian, dari dua tinjauan tersebut dapat disimpulkan bahwa metode SSVD bekerja lebih baik dibandingkan metode SVD untuk citra lena484.jpg dan parameter kompresi p = 65. Dari hasil uji coba di atas juga dapat disimpulkan bahwa untuk nilai p yang kurang dari 20, metode SSVD justru tidak bekerja lebih baik dibandingkan metode SVD ditinjau dari sisi ukuran file. Sedangkan untuk nilai p tersebut, SSVD memberikan kualitas citra yang lebih baik. Hal ini dikarenakan nilai rank yang dihasilkan setelah proses re-shuffle jauh lebih besar daripada nilai rank citra hasil metode SVD seperti yang terlihat pada Tabel 4.4. Keadaan ini pula yang mengakibatkan ukuran file citra hasil kompresi metode SSVD lebih besar daripada metode SVD. Pada uji coba di atas, citra disimpan dalam format JPEG. Sebagaimana yang telah disebutkan sebelumnya, bahwa penyimpanan citra erat kaitannya dengan format penyimpanannya. Oleh karena itu, perlu dilakukan penyimpanan file yang objektif, artinya tidak terkait dengan format penyimpanan citra apapun. Pada penelitian ini, untuk parameter kompresi p = 65 dilakukan penyimpanan data langsung melalui MATLAB, yaitu berupa MAT-file dengan ekstensi *.mat. Langkah penyimpanan data tersebut dapat dilihat pada Lampiran 3. Berikut ini adalah hasil penyimpanan data citra yang dilakukan oleh MATLAB.
61 Tabel 4.7 Ukuran citra lena484.jpg dengan parameter kompresi 65 Nama File
Ukuran (KB)
Original_lena484.jpg.mat SVD_r65_lena484.jpg.mat SSVD_r65_lena484.jpg.mat
548 547 523
Keterangan Citra asli Citra hasil metode kompresi SVD Citra hasil metode kompresi SSVD
Terlihat bahwa metode SSVD memberikan ukuran file yang lebih kecil daripada metode SVD. File tersebut ketika disimpan kembali dengan format JPEG akan menghasilkan ukuran file yang lebih kecil karena JPEG menerapkan teknik kompresi juga. Selain dua tinjauan di atas, untuk menentukan keefektifan suatu metode dapat digunakan ukuran baku, yaitu MSE. Setelah dilakukan kompresi, diperoleh citra hasil kompresi kemudian dihitung nilai MSE antara citra asli dengan citra hasil kompresi sehingga diperoleh beberapa nilai MSE baik setelah diterapkan metode SVD atau SSVD. Semakin kecil nilai MSE antara citra asli dan citra hasil kompresi, semakin baik kompresi citra tersebut (Hafsah 2007). Tabel 4.8 Nilai CPU Time dan MSE kompresi untuk citra lena484.jpg Rank/ term 1 2 3 4 5 10 20 40 65 80 100 120 140 180 200
CPU Time (detik) SSVD SVD 3.85337 2.62966 2.57992 2.54309 2.52157 2.52649 2.52290 2.59650 2.57409 2.56355 2.54481 2.54598 3.27820 2.72118 2.57854
4.62982 3.76210 3.83416 3.82838 3.84525 3.84018 3.87563 4.01724 3.87434 3.87855 3.97810 3.92669 3.93276 4.00550 4.06255
MSE SVD 31.80717 27.28077 24.43725 22.57316 20.89637 16.79036 12.26518 9.00284 6.40620 5.06355 3.61520 2.48958 1.68900 0.76396 0.50396
SSVD 17.65081 15.20598 14.13028 12.83289 11.91644 10.18852 8.57482 6.42677 4.24301 3.23522 2.23557 1.54982 1.07623 0.53116 0.37224
62 Setelah melakukan uji coba, untuk menentukan apakah metode SSVD lebih baik dibandingkan dengan metode SVD, data MSE yang diperoleh tersebut dianalisis melalui grafik pada Gambar 4.11 sebagai berikut. Grafik respon citra lena484.jpg Mean Square Error (MSE)
35 30 25 20 15
SVD
10
SSVD
5 0 1
2
3
4
5
10 20 40 65 80 100 120 140 180 200 Rank/Term
Gambar 4.11 Grafik respon perubahan rank terhadap MSE dari kedua metode untuk citra lena484.jpg. Rank/term yang digunakan adalah 1, 2, 3, 4, 5, 10, 20, 40, 65, 80, 100, 120, 140, 180, dan 200. Dari Gambar 4.11 terlihat bahwa untuk semua nilai rank/term, MSE yang dihasilkan oleh metode SSVD lebih kecil daripada MSE yang dihasilkan oleh metode SVD. Untuk rank yang kecil, terdapat perbedaan MSE yang cukup besar. Akan tetapi, semakin nilai rank/term mendekati nilai rank citra tersebut maka perbedaan MSE keempat metode menjadi semakin kecil. Untuk citra lena484.jpg,
jika diterapkan teknik shuffle akan memberikan hasil yang lebih
baik dibandingkan dengan tanpa menerapkan teknik shuffle terhadap SVD. Selanjutnya, perlu juga ditinjau bagaimana kualitas dan ukuran file citra untuk nilai-nilai rank tersebut. Berikut ini adalah ukuran file citra hasil kompresi untuk beberapa nilai rank/term.
63 Tabel 4.9 Ukuran file citra dan rasio hasil kompresi lena484.jpg Rank/ term
Ukuran file (KB) SVD SSVD
1 2 3 4 5 10 20 40 65 80 100 120 140 180 200
12.087 14.327 15.988 16.962 17.996 21.575 25.405 30.870 34.213 35.472 36.563 37.213 37.548 37.780 37.845
16.787 18.746 19.499 20.206 20.814 23.293 26.476 30.094 32.495 33.544 34.654 35.661 36.458 37.588 37.827
Rasio kompresi (%) SVD SSVD 68.306 62.432 58.076 55.523 52.812 43.427 33.384 19.054 10.289 6.988 4.128 2.422 1.544 0.935 0.766
55.982 50.845 48.871 47.017 45.421 38.922 30.577 21.090 14.793 12.043 9.131 6.491 4.402 1.439 0.812
Dari Gambar 4.11 dan Tabel 4.9 di atas, terlihat bahwa mulai rank/term 65 metode SSVD memberikan ukuran file yang lebih kecil dibandingkan metode SVD. Seperti yang telah disebutkan sebelumnya bahwa Ranade et al. (2006) mengharapkan dengan melakukan shuffle dapat mengurangi rank matriks aslinya. Berikut ini ditampilkan nilai rank untuk matriks citra lena484.jpg sebelum dan sesudah dilakukan shuffle. Tabel 4.10 Nilai rank citra lena484.jpg sebelum dan sesudah shuffle Bidang Warna Red Green Blue
Nilai Rank Sebelum Shuffle Setelah Shuffle 484 484 484
291 198 178
Pada Tabel 4.10 terlihat bahwa setelah di–shuffle nilai rank citra menjadi lebih kecil dibandingkan nilai rank citra sebelum di–shuffle. Hal ini sesuai dengan
64 harapan dari Ranade et al. (2006). Uji coba selanjutnya diterapkan pada citra simulasi yang dibuat menggunakan script MATLAB. Citra tersebut adalah citra sample_101.jpg yang merupakan citra keabuan (grayscale) dengan format JPEG, berdimensi 100 x 100 pixel dan berukuran 6.13 KB. Citra simulasi yang kedua adalah citra sample_900.jpg
yang merupakan citra berwarna (RGB image) dengan format
JPEG, berdimensi 289 x 289 pixel dan berukuran 50.9 KB. Kedua citra ini dapat diunduh dari website http://www.khaeroni.net. Data citra tersebut ditampilkan pada Gambar 4.12 berikut.
(a) (b) Gambar 4.12 Citra simulasi (a) sample_101.jpg, (b) sample_900.jpg. Berdasarkan (4.3), diperoleh nilai e(p) untuk beberapa nilai p sebagai berikut. Tabel 4.11 Beberapa nilai e(p) untuk citra sample_101.jpg p
e(p)
56 57 58 59 60 61 62 63 64 65
0.13828 0.13366 0.12893 0.12441 0.11988 0.11544 0.11103 0.10681 0.10248 0.09829
65 Dari tabel di atas, dapat disimpulkan bahwa dengan threshold 90% diperoleh nilai p yang memenuhi adalah 65 dan dari perhitungan lainnya, dengan threshold 95% diperoleh nilai p yang memenuhi adalah 75. Pertama dilakukan kompresi dengan parameter p = 65. Diperoleh hasil sebagai berikut.
(a) (b) Gambar 4.13 Hasil kompresi citra sample_101.jpg dengan parameter kompresi 65 (a) SVD; (b) SSVD. Secara kasat mata, terlihat bahwa citra yang dihasilkan oleh metode SVD justru lebih baik daripada citra yang dihasilkan oleh metode SSVD. Berikut ini diberikan informasi lain dari hasil kompresi tersebut. Tabel 4.12 Atribut hasil kompresi citra sample_101.jpg Nama file Sample_101.jpg SVD_r65_sample_101.jpg SSVD_r65_sample_101.jpg
Ukuran file di memori (KB)
Atribut Ukuran file di harddisk (KB)
MSE terhadap citra asli
10.80469 10.80469 10.80469
6.13965 6.08594 6.08887
0.0000 54.1550 57.2293
Dari Tabel 4.12 terlihat bahwa selain menghasilkan citra dengan kualitas yang tidak lebih baik daripada citra hasil metode SVD, metode SSVD juga menghasilkan citra dengan ukuran file citra yang (sedikit) lebih besar dan MSE yang lebih besar. Dengan demikian, teknik shuffle yang diterapkan pada metode SVD bekerja tidak lebih baik daripada metode SVD untuk citra sample_101.jpg. Untuk mengonfirmasi-nya, berikut ini diperlihatkan nilai rank matriks citra
66 sebelum shuffle, setelah shuffle, dan setelah re-shuffle. Tabel 4.13 Nilai rank citra sample_101.jpg untuk p = 65 Shuffle Sebelum Sesudah Re-shuffle
Rank 100 100 100
Tabel 4.14 menampilkan nilai MSE yang lain dan CPU time yang dihasilkan oleh kedua metode untuk citra sample_101.jpg. Tabel 4.14 Nilai CPU Time dan MSE kompresi untuk citra sample_101.jpg Rank/ term 1 2 3 4 5 10 20 40 65 75 100
CPU Time (detik) SVD SSVD 0.09582 0.21675 0.03330 0.09690 0.02287 0.08578 0.02207 0.08548 0.02345 0.09651 0.03251 0.10249 0.04953 0.12626 0.04436 0.13154 0.01980 0.09969 0.03580 0.08830 0.02960 0.12333
MSE SVD 115.8271 114.8020 114.1833 114.1141 113.6555 110.3005 105.0774 92.3572 54.1550 26.9881 0.0000
SSVD 116.8464 116.5776 115.7407 115.6327 115.5130 112.2954 107.5405 93.5853 57.2293 30.8547 0.0000
Dari Tabel 4.14 di atas, terlihat bahwa metode SSVD justru memberikan MSE yang lebih besar dari MSE yang dihasilkan oleh metode SVD. Artinya, untuk citra sample_101.jpg, teknik shuffle tidak bekerja lebih baik jika diterapkan pada metode SVD atau dengan kata lain, metode SSVD tidak bekerja lebih baik daripada metode SVD untuk citra tersebut. Tabel 4.15 menyajikan daftar ukuran file citra hasil kompresi.
67 Tabel 4.15 Ukuran file citra dan rasio hasil kompresi citra sample_101.jpg Rank/ term 1 2 3 4 5 10 20 40 65 75 100
Ukuran file (KB) SVD SSVD 1.96777 1.70117 2.97168 2.94043 3.54492 3.56836 3.91211 3.91699 4.18262 4.20801 4.86719 4.89551 5.45996 5.47852 5.88184 5.87988 6.08594 6.08887 6.12402 6.12988 6.13770 6.13965
Rasio kompresi (%) SVD SSVD 81.78781 72.49638 67.19091 63.79247 61.28884 54.95298 49.46675 45.56215 43.67315 43.32071 43.19409
84.25526 72.78561 66.97396 63.74731 61.05385 54.69087 49.29497 45.58028 43.64603 43.26647 43.17605
Ide dasar dari kompresi data adalah bagaimana mengurangi ruang yang dibutuhkan untuk menyimpan data ke dalam media penyimpanan pada komputer. Teknik shuffle yang diterapkan pada metode SVD justru selain menghasilkan MSE yang lebih besar dari MSE yang dihasilkan oleh metode SVD, juga menghasilkan citra dengan ukuran file yang lebih besar dari ukuran file citra yang dihasilkan oleh metode SVD (tanpa shuffle). Dengan demikian, dari dua tinjauan di atas, dapat disimpulkan bahwa metode SSVD untuk citra sample_101.jpg tidak bekerja lebih baik jika diterapkan pada metode SVD. Uji coba terakhir adalah menerapkan metode kompresi SVD dan SSVD pada citra sample_900.jpg. Pertama kali ditentukan banyaknya parameter kompresi yang digunakan berdasarkan threshold 90%. Berikut ini adalah beberapa nilai e(p) untuk citra sample_900.jpg.
68 Tabel 4.16 Beberapa nilai e(p) untuk citra sample_900.jpg p
e(p)
154 155 156 157 158 159 160 161 162 163
0.11091 0.10967 0.10843 0.10718 0.10593 0.10468 0.10344 0.10222 0.10099 0.09975
Jadi, untuk dengan threshold sebesar 90% dapat diambil parameter kompresi p = 163. Dengan menggunakan cara yang sama, diperoleh parameter kompresi p = 209 untuk memenuhi threshold 95%. Oleh karena itu, untuk uji coba terakhir diambil p = 163. Diperoleh hasil sebagai berikut.
(a) (b) Gambar 4.14 Hasil kompresi citra sample_900.jpg dengan parameter kompresi 163 (a) SVD; (b) SSVD. Secara kasat mata, terlihat bahwa citra yang dihasilkan oleh metode SVD justru lebih baik daripada citra yang dihasilkan oleh metode SSVD. Berikut adalah hasil uji coba untuk nilai p yang lain.
69 Tabel 4.17 Nilai CPU Time dan MSE kompresi untuk citra sample_900.jpg Rank/ term 1 2 3 4 5 10 20 40 60 80 100 120 140 163 209
CPU Time (detik) SSVD SVD 0.56099 0.57379 0.53517 0.51645 0.52784 0.56522 0.52407 0.53952 0.54818 0.56166 0.54238 0.54728 0.55134 0.56535 0.59346
0.75223 0.75879 0.74225 0.74865 0.72249 0.73701 0.75701 0.74644 0.75689 0.78719 0.76172 0.77069 0.79971 0.80529 0.85718
MSE SVD 36.50478 36.43880 36.38853 36.34362 36.26444 35.97137 35.37107 34.08929 32.67932 31.10717 29.18657 26.86399 23.83291 19.40552 7.74850
SSVD 36.53511 36.49704 36.39741 36.28828 36.24992 35.96869 35.33331 34.02057 32.66548 31.01241 29.10364 26.79348 23.89297 19.56467 7.807520
Dari Tabel 4.16 di atas, terlihat bahwa metode SSVD justru memberikan MSE yang lebih besar dari MSE yang dihasilkan oleh metode SVD walau dengan perbedaan yang kecil. Keadaan ini sama dengan keadaan sebelumnya. Artinya, untuk citra sample_900.jpg, teknik shuffle tidak bekerja lebih baik jika diterapkan pada metode SVD atau dengan kata lain, metode SSVD tidak bekerja lebih baik daripada metode SVD untuk citra tersebut. Teknik shuffle mungkin saja dapat mengurangi rank matriks menjadi lebih kecil (atau tetap) daripada tidak di shuffle. Akan tetapi, rank matriks juga bisa jadi lebih besar (atau tetap) ketika dilakukan proses re-shuffle. Tabel 4.18 Nilai rank citra sample_900.jpg untuk p = 163 dan toleransi 0.4 Bidang Warna Red Green Blue
Sebelum shuffle
Rank Setelah shuffle
Setelah re-shuffle
289 288 288
288 289 289
289 289 289
70 Tabel 4.19 Ukuran file citra dan rasio hasil kompresi sample_900.jpg Rank/ term 1 2 3 4 5 10 20 40 60 80 100 120 140 163 209
Ukuran file (KB) SVD SSVD 8.97461 6.28906 12.19531 10.37598 14.21289 12.82031 15.85156 14.83594 17.29004 16.60352 23.16113 22.92676 29.68750 30.03711 36.51660 36.70508 40.21680 40.26758 42.51758 42.53613 44.19336 44.13379 45.31250 45.27930 46.14648 46.18262 46.87988 46.80371 47.41016 47.40430
Rasio kompresi (%) SVD SSVD 82.39396 76.07572 72.11771 68.90303 66.08107 54.56340 41.76022 28.36316 21.10425 16.59067 13.30319 11.10771 9.47164 8.03288 6.99260
87.66237 79.64481 74.84962 70.89543 67.42786 55.02318 41.07437 27.99341 21.00463 16.55428 13.42005 11.17284 9.40074 8.18231 7.00409
Teknik shuffle yang diterapkan pada metode SSVD justru selain menghasilkan MSE yang lebih besar dari MSE yang dihasilkan oleh metode SVD, juga menghasilkan citra dengan ukuran file yang lebih besar dari ukuran file citra yang dihasilkan oleh metode SVD. Dengan demikian, dari dua tinjauan di atas, dapat disimpulkan bahwa teknik shuffle untuk citra sample_900.jpg tidak bekerja lebih baik jika diterapkan pada metode SVD.
BAB V KESIMPULAN
Kompresi citra menggunakan SSVD dilakukan dengan terlebih dahulu melakukan proses shuffle terhadap matriks citra. Proses shuffle ini dilakukan dengan harapan bahwa rank matriks citra akan berkurang dari rank sebelumnya. Pada beberapa citra, proses shuffle yang diterapkan tidak mengurangi nilai rank atau justru menjadi lebih besar dari rank sebelumnya walau dengan tingkat ketelitian atau toleransi yang cukup besar. Ketika ketelitian yang digunakan semakin kecil (sangat teliti), maka nilai rank yang dihasilkan dari proses shuffle selalu lebih kecil atau paling tidak sama dengan nilai rank sebelum dilakukan proses shuffle. Dari hasil pengujian terhadap citra lena484.jpg, dapat disimpulkan bahwa teknik shuffle yang diterapkan pada metode SVD bekerja cukup efektif. Terbukti bahwa, selain mengurangi MSE teknik shuffle yang diterapkan juga mampu mengurangi ukuran file citra menjadi lebih kecil daripada metode SVD sendiri. Akan tetapi, untuk citra sample_101.jpg, pada beberapa kasus, teknik shuffle yang diterapkan baik pada metode SVD maupun SSVD memperlihatkan perilaku yang berbeda dengan sebelumnya. Penerapan teknik shuffle justru memperbesar MSE dan ukuran file citra walaupun dengan perbedaan yang sangat kecil. Demikian juga untuk citra sample_900.jpg. Secara umum dapat disimpulkan bahwa teknik shuffle yang diterapkan pada metode SVD tidak selalu bekerja lebih baik daripada metode SVD sendiri. Pada beberapa citra, metode SSVD bekerja lebih baik. Akan tetapi pada citra yang lain metode SSVD tidak bekerja lebih baik. Jadi efektivitas metode SSVD juga ditentukan oleh pemilihan sampel citra yang digunakan. Selain itu, metode SSVD juga bergantung pada pemilihan rank yang digunakan. Dengan demikian justifikasi bahwa metode SSVD bekerja selalu lebih baik daripada metode SVD tidak dapat dibenarkan. Penelitian lanjutan yang dapat dilakukan adalah menganalisis karakteristik citra di mana metode SSVD bekerja lebih baik daripada metode SVD dan 71
72
sebaliknya. Selain itu, penelitian lain yang juga dapat dilakukan adalah mencari teknik shuffle yang lain untuk memperbaiki teknik shuffle yang diajukan oleh Ranade et. al.
DAFTAR PUSTAKA
Acharya T, Ray AK. 2005. Image Processing: Principles and Applications. New Jersey: J. Wiley. Anton H. 2000. Elementary Linear Algebra. Ed ke-8. New Jersey: J. Wiley. Castleman RK. 1996. Digital Image Processing. New Jersey: Prentice-Hall. Eckart C, Young G. 1936. The Approximation of One Matrix by Another of Lower Rank. Psychometrika 1:211-218. Goldberg JL. 1991. Matrix Theory with Applications. Singapore: McGraw-Hill. Greenacre MJ. 1984. Theory and Applications of Correspondence Analysis. London: Academic Press. Golub GH, Loan CFV. 1996. Matrix Computations. Ed ke-3. Baltimore: The Johns Hopkins University Press. Gonzales RC, Woods RE. 2002. Digital Image Processing. New Jersey: PrenticeHall. Hafsah AN. 2007. Pemampatan Citra Biomedik menggunakan SVD dan Variasinya [tesis]. Jakarta: Fakultas Ilmu Komputer Universitas Indonesia. Hafsah AN, Basaruddin T, Jaya D. 2007. Variasi SVD pada Kompresi Citra. Proceedings of National Conference on Computer Science & Information Technology 29-30:300–303. Jain AK. 1989. Fundamental of Digital Image Processing. New Jersey: PrenticeHall. Kalman D. 1996. A Singularly Valuable Decomposition: The SVD of a Matrix. The College Mathematics Journal 27:1–23. Khaeroni. 2005. Pemampatan Citra Menggunakan Dekomposisi Nilai Singular [skripsi]. Jogjakarta: Jurusan Matematika FMIPA UGM. Kolda TG, O’Leary DP. 1998. A Semidiscrete Matrix Decomposition for Latent Semantic Indexing in Information Retrieval. ACM Transactions on Information Systems 16:322–346. Meyer CD. 2000. Matrix Analysis and Applied Linear Algebra. Philadelphia: SIAM. 73
74
Nicholson WK. 2001. Elementary Linear Algebra. Singapore: McGraw-Hill. Ranade A, Srikath SM, Kale S. 2006. A Variation on SVD Based Image Compression. Image and Vision Computing 25:771–777. Scheick JT. 1997. Linear Algebra with Applications. Singapore: McGraw-Hill. Shannon CE. 1948. A Mathematical Theory of Communication. Bell System Technical 27:379–423. Sutopo AH. 2002. Pengantar Grafika Komputer. Jogjakarta: Gava Media. Thyagarajan KS. 2006. Digital Image Processing with Application to Digital Cinema. Burlington: Focal Press. Waldemar P, Ramstad TA. 1997. Hybrid KLT-SVD Image Compression. IEEE International Conference on Acoustics, Speech, and Signal Processing 4:2713-2716. Zadeh LA. 1965. Fuzzy Sets. Information and Control 8:338-353.
LAMPIRAN
77
Lampiran 1 Bukti Lemma dan Teorema 1.1
Lemma 2.1 (Nicholson 2001) Misalkan A sebarang matriks berukuran m x n dan rank(A) = r dan {V1, . . ., Vn} merupakan basis ciri ortonormal untuk ATA. 1) Matriks A memiliki tepat r nilai singular. 2) {AV1, AV2, . . ., AVr} merupakan basis ortogonal untuk CS(A) = im(A). Bukti. Untuk membuktikan Lemma di atas, digunakan dua teorema di bawah ini. Teorema ini diambil dari Anton (2000). Teorema 1.1.a (Anton 2000) Semua basis untuk ruang vektor berdimensi hingga mempunyai banyak anggota yang sama. Teorema 1.1.b (Anton 2000) Misalkan V ruang vektor atas lapangan F berdimensi n dan S = {v1, . . ., vn} V. Jika S bebas linear atau S sebagai pembangun V maka S basis dari V. Selanjutnya, Lemma 2.1 dibuktikan sebagai berikut. Anggap sebanyak s nilai singular dari A, yaitu i , dan disusun 1 2 s dan
s 1 n 0 untuk suatu bilangan asli s. Misalkan = {AV1, AV2, . . ., AVs}, maka im(A) dan berdasarkan (2.3) dan (2.4) ortogonal. Jadi, karena dim(im(A)) = r = rank(A), untuk membuktikan 1) dan 2) cukup dibuktikan bahwa membangun im(A). Diambil sebarang vektor x n , dengan x = r1V1 + r2V2 + . . . + rnVn untuk suatu ri . Karena
s 1 n 0 , diperoleh Ax r1 AV1 r2 AV2 rs AVs rn AVn r1 AV1 r2 AV2 rs AVs span() Karena im(A) = {Ax : x n }, hal ini menunjukkan bahwa membangun im(A) menurut Teorema 1.1.b, basis untuk im(A) = CS(A) dan menurut Teorema 1.1.a, s=r. ■
78
1.2
Teorema 2.1 (Goldberg 1991) Diberikan A sebarang matriks berukuran m x n dengan rank(A) = r dan nilai singular 1 r . Jika didefinisikan U, , dan V seperti uraian di atas, maka U dan V matriks ortogonal, dan A dapat didekomposisikan sebagai A = UVT. Bukti.
U U1 U 2
1 0 0 2 Um 0 0 0 0 0 0
1U1 2U 2 rU r
0 0
r
0 0
0 0 0 0 0 0 0 0 0 0
0 0 .
Di lain pihak, V V1 V2 Vn , dari (2.4) dan (2.5) diperoleh AV AV1
AV2 AVn 1U1 2U 2 rU r
0 0 .
Terlihat UΣ = AV, karena V ortogonal maka A = UΣVT. ■ 1.3
Teorema 2.2 (Scheick 1997) Diberikan A matriks simetri berukuran n x n dengan nilai ciri 1 n dan sebarang x Թn dengan x ≠ 0. 1) Jika x adalah vektor ciri dari A yang bersesuaian dengan i maka R(x) = i , untuk suatu i. 2)
1 R( x) n .
3) λ1 = max{R(x)} dan λn = min{R(x)} Bukti. 1) Karena x vektor ciri, maka berlaku Ax i x . Dari sini diperoleh R( x)
Ax, x x
2
i x, x x, x
i x, x x, x
i
79 2) Karena A simetri, diambil ek k 1 basis ortonormal untuk n dengan n
n
Aei i ei untuk setiap i. Diambil x i ei n untuk suatu i , i 1
n
n
i 1
i 1
dan x 0 . Karena Aei i ei dan x i ei maka Ax i i ei . Sehingga Ax, x
n
n
n
i i ei , i ei i i i 1
i 1
2
ei
2
ei .
i 1
2
dan 2
x x, x
n
n
n
e , e i 1
i i
i 1
i
i i
i 1
2
Karena i n dan i 1 untuk setiap i maka n
Ax, x n i
2
i 1
ei
2
ei
2
n
n i
2
i 1
ei
2
ei
2
2
n x
Ax, x x
2
n
dan n
Ax, x 1 i
2
i 1
n
1 i i 1
2
2
1 x
Ax, x x
2
1 .
Diperoleh 1 R ( x) dan R( x) n atau 1 R( x) n . 3) Dari bukti 2) diperoleh untuk setiap x berlaku 1 R( x) n . Tetapi dari bukti 1), R(x) = k untuk suatu k, begitu juga R(x) = n dipenuhi untuk suatu x, yaitu vektor ciri yang bersesuaian dengan n , dan R(x) = 1 dipenuhi untuk suatu x di dalam n, yaitu vektor ciri yang bersesuaian dengan 1 . Jadi
1 max{R( x) : x 0 n } dan n min{R( x) : x 0 n } . ■
1.4
Teorema 2.3 Extended Maximal Principle (Scheick 1997)
Diberikan A matriks simetri berukuran n x n dengan nilai ciri
1 2 n dan ek k 1 merupakan basis ciri ortogonal untuk A, maka n
80
1)
1 max{R( x) : x 0}
2)
i max{R( x) : x 0, x e1 , e2 ,, ei 1} untuk i 2,, n
Bukti.
1) Poin (1) sudah dibuktikan pada pembuktian Teorema 2.2. 2) Karena
ek k 1 n
n
basis, diambil x j e j 0 untuk suatu j dan j 1
berlaku x e1 , e2 ,, ei 1 . Oleh karena itu, untuk j > i berlaku
x, e j
j
ej
(* )
0.
2
Diperoleh i
R( x)
j 1 i
j
j
j 1
2
2
ej
2
ej
j
i
2
i j j 1
i
j 1
2 j
2
2
ej ej
2
i .
Dengan mengganti j dengan bilangan terbesar i , diperoleh i
R ( x)
i j j 1
i
j 1
2 j
2
2
ej ej
2
i .
Menurut teorema ek k 1 bebas linear sehingga x = 0 dipenuhi untuk j = 0 n
dan dari (*) keadaan ini dipenuhi untuk j > i. Jika x = ei, maka
x e1 , e2 ,, ei 1 karena ek k 1 ortonormal. Sehingga untuk i = 2, . . ., n, n
diperoleh i max{R( x) : x 0, x en , en 1 ,, ei 1} . ■
81
Lampiran 2 Kode Sumber 2.1
Kompresi Citra dengan SVD function [Ar]=SVDGlobal(Citra,r); % Fungsi SVDGlobal.m % (c) Khaeroni, S.Si - Math IPB 2009/2011 % Deskripsi : %
Script ini dibuat untuk mengimplementasikan metode
%
pemampatan citra menggunakan teknik SVD. Secara
%
sederhana, metode kompresi citra dengan menggunakan
%
teknik SVD adalah memotong ekspansi citra sampai dengan
%
batas yang diinginkan.
% Cara penggunaan : %
Ar = SVDGlobal(Citra,r)
%
SVDGlobal(Citra,r)
% di mana %
Ar
: matriks citra hasil kompresi
%
Citra : nama file citra, lengkap dengan path-nya.
%
Kecuali path sudah didefinisikan pada MATLAB
%
path, cukup dituliskan nama file-nya saja.
%
r
: parameter pemotongan rank
% Kebutuhan : %
Script ini membutuhkan fungsi-fungsi yang terdapat pada
%
toolbox image processing. Jadi, pastikan toolbox image
%
processing sudah terinstall pada MATLAB Anda. Selain
%
itu, script ini juga membutuhkan fungsi sbb:
%
Built-in function
%
* svd.m
% Informasi : %
* Tanggal dibuat = 08-02-2011
%
* Tanggal direvisi = 14-02-2011
%
* Revisi ke-2
if (exist(Citra)==2) A = imread(Citra); else warndlg('The file does not exist.',' Warning '); Ar=[]; return
82
end if isrgb(A) if isa(A(:,:,1),'uint8') % The R layer red = double(A(:,:,1)); [U,S,V] = svd(red); Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); imred = uint8(Ur*Sr*transpose(Vr)); % The G layer green = double(A(:,:,2)); [U,S,V] = svd(green); Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); imgreen = uint8(Ur*Sr*transpose(Vr)); % The B layer blue = double(A(:,:,3)); [U,S,V] = svd(blue); Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); imblue = uint8(Ur*Sr*transpose(Vr)); Ar(:,:,1) = imred; Ar(:,:,2) = imgreen; Ar(:,:,3) = imblue; imwrite(Ar,strcat('Svd_r',num2str(r),'_',Citra)); return; end if isa(A(:,:,1),'uint16') % The R layer red = double(A(:,:,1)); [U,S,V] = svd(red); Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); imred = uint16(Ur*Sr*transpose(Vr));
83
% The G layer green = double(A(:,:,2)); [U,S,V] = svd(green); Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); imgreen = uint16(Ur*Sr*transpose(Vr)); % The B layer blue = double(A(:,:,3)); [U,S,V] = svd(blue); Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); imblue = uint16(Ur*Sr*transpose(Vr)); Ar(:,:,1) = imred; Ar(:,:,2) = imgreen; Ar(:,:,3) = imblue; imwrite(Ar,strcat('Svd_r',num2str(r),'_',Citra)); return; end if isa(A(:,:,1),'double') % The R layer red = double(A(:,:,1)); [U,S,V] = svd(red); Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); imred = double(Ur*Sr*transpose(Vr)); % The G layer green = double(A(:,:,2)); [U,S,V] = svd(green); Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); imgreen = double(Ur*Sr*transpose(Vr)); % The B layer blue = double(A(:,:,3)); [U,S,V] = svd(blue);
84
Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); imblue = double(Ur*Sr*transpose(Vr)); Ar(:,:,1) = imred; Ar(:,:,2) = imgreen; Ar(:,:,3) = imblue; imwrite(Ar,strcat('Svd_r',num2str(r),'_',Citra)); return; end end if isgray(A) dvalue=double(A)+1; [U,S,V] = svd(dvalue); Ur=U(:,1:r); Vr=V(:,1:r); Sr=S(1:r,1:r); if isa(A,'uint8') Ar = uint8(Ur * Sr * transpose(Vr)); end if isa(A,'uint16') Ar = uint16(Ur * Sr * transpose(Vr)); end if isa(A,'double') Ar = (Ur * Sr * transpose(Vr)); end imwrite(Ar,strcat('Svd_r',num2str(r),'_',Citra)); return; end
2.2
Kompresi Citra dengan SSVD function [Ar]=SSVDGlobal(Citra,r); % Fungsi SSVDGlobal.m % (c) Khaeroni, S.Si - Math IPB 2009/2011 % Deskripsi : %
Script ini dibuat untuk mengimplementasikan metode
%
pemampatan citra menggunakan teknik SSVD. Perbedaan
85
%
dengan SVD adalah, sebelum di dekomposisi dengan SVD
%
matriks terlebih dahulu di shuffle dengan suatu
%
operator permutasi P. Operator permutasi P didasarkan
%
pada algoritma SSVD milik Hafsah (2007).Setelah di-
%
shuffle, baru kemudian didekomposisi dengan SVD dan
%
direkonstruksi kembali menggunakan operator re-shuffle
%
(atau invers P).
% Cara penggunaan : %
Ar = SSVDGlobal(Citra,r)
%
SSVDGlobal(Citra,r)
% dimana %
Ar
: matriks citra hasil kompresi
%
Citra : nama file citra, lengkap dengan path-nya.
%
Kecuali path sudah didefinisikan pada MATLAB
%
path, cukup dituliskan nama file-nya saja.
%
r
: parameter pemotongan rank
% Kebutuhan : %
Script ini membutuhkan fungsi-fungsi yang terdapat pada
%
toolbox image processing. Jadi, pastikan toolbox image
%
processing sudah terinstall pada MATLAB Anda. Selain
%
itu, script ini juga membutuhkan fungsi sbb:
%
Built-in function
%
* svd.m
%
User defined function
%
* P.m - operator permutasi
%
* PInvers.m - invers operator permutasi
% Informasi : %
* Tanggal dibuat = 13-02-2011
%
* Tanggal direvisi =
%
* Revisi ke-
if (exist(Citra)==2) A = imread(Citra); else warndlg('The file does not exist.',' Warning '); Ar=[]; return end
86
if isrgb(A) if isa(A(:,:,1),'uint8') % The R layer red = double(A(:,:,1)); % Shuffle Xred = S(red); [U,S,V] = svd(Xred); Ur=[]; Vr=[]; Sr=zeros(r,r); for i = 1:r Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end % Reshuffle and then convert it imred = uint8(SInvers(Ur*Sr*transpose(Vr))); % The G layer green = double(A(:,:,2)); Xgreen = S(green); [U,S,V] = svd(Xgreen); Ur=[]; Vr=[]; Sr=zeros(r,r); for i = 1:r Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end imgreen = uint8(SInvers(Ur*Sr*transpose(Vr))); % The B layer blue = double(A(:,:,3)); Xblue = S(blue); [U,S,V] = svd(Xblue); Ur=[]; Vr=[]; Sr=zeros(r,r); for i = 1:r
87
Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end imblue = uint8(SInvers(Ur*Sr*transpose(Vr))); Ar(:,:,1) = imred; Ar(:,:,2) = imgreen; Ar(:,:,3) = imblue; imwrite(Ar,strcat('SSvd_r',num2str(r),'_',Citra)); return; end if isa(A(:,:,1),'uint16') % The R layer red = double(A(:,:,1)); Xred = S(red); [U,S,V] = svd(Xred); Ur=[]; Vr=[]; Sr=zeros(r,r); for i = 1:r Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end imred = uint16(SInvers(Ur*Sr*transpose(Vr))); % The G layer green = double(A(:,:,2)); Xgreen = S(green); [U,S,V] = svd(Xgreen); Ur=[]; Vr=[]; Sr=zeros(r,r); for i = 1:r Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end imgreen = uint16(SInvers(Ur*Sr*transpose(Vr)));
88
% The B layer blue = double(A(:,:,3)); Xblue = S(blue); [U,S,V] = svd(Xblue); Ur=[]; Vr=[]; Sr=zeros(r,r); for i = 1:r Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end imblue = uint16(SInvers(Ur*Sr*transpose(Vr))); Ar(:,:,1) = imred; Ar(:,:,2) = imgreen; Ar(:,:,3) = imblue; imwrite(Ar,strcat('SSvd_r',num2str(r),'_',Citra)); return; end if isa(A(:,:,1),'double') % The R layer red = double(A(:,:,1)); Xred = S(red); [U,S,V] = svd(Xred); Ur=[]; Vr=[]; Sr=zeros(r,r); for i = 1:r Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end imred = double(SInvers(Ur*Sr*transpose(Vr))); % The G layer green = double(A(:,:,2)); Xgreen = S(green); [U,S,V] = svd(Xgreen); for i = 1:r
89
Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end imgreen = double(SInvers(Ur*Sr*transpose(Vr))); % The B layer blue = double(A(:,:,3)); Xblue = S(blue); [U,S,V] = svd(Xblue); Ur=[]; Vr=[]; Sr=zeros(r,r); for i = 1:r Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end imblue = double(SInvers(Ur*Sr*transpose(Vr))); Ar(:,:,1) = imred; Ar(:,:,2) = imgreen; Ar(:,:,3) = imblue; imwrite(Ar,strcat('SSvd_r',num2str(r),'_',Citra)); return; end end if isgray(A) dvalue=double(A); Xdvalue=S(dvalue); [U,S,V] = svd(Xdvalue); Ur=[]; Vr=[]; Sr=zeros(r,r); for i = 1:r Ur=[Ur U(:,i)]; Vr=[Vr V(:,i)]; Sr(i,i)=S(i,i); end if isa(A,'uint8')
90
Ar = uint8(SInvers(Ur * Sr * transpose(Vr))); end if isa(A,'uint16') Ar = uint16(SInvers(Ur * Sr * transpose(Vr))); end if isa(A,'double') Ar = (SInvers(Ur * Sr * transpose(Vr))); end imwrite(Ar,strcat('SSvd_r',num2str(r),'_',Citra)); return; end
91
Lampiran 3 Script MATLAB 3.1
Contoh Penghitungan MSE Metode SVD dan SSVD
>> A=[1 2 3 4;5 6 7 8;9 10 11 12;13 14 15 16]; % Matriks A >> p=1; % Parameter kompresi >> [U,S,V]=svd(A); % Tentukan SVD dari A >> UA=U(:,1:p); % Left singular vector >> SA=S(1:p,1:p); %Diagonal matrix which entry is singular value >> VA=V(:,1:p); % Right singular vector >> A1=UA*SA*VA'; % Konstruksi matriks aproksimasi untuk A >> sum(sum((A-A1).*(A-A1)))/16 % Hitung MSE antara A dengan A1 ans = 0.2681 >> X=P(A); % Matriks X diperoleh dari matriks A yang di-shuffle >> [U,S,V]=svd(X); >> UX=U(:,1:p); >> SX=S(1:p,1:p); >> VX=V(:,1:p); >> X1=PInvers(UX*SX*VX'); >> sum(sum((A-X1).*(A-X1)))/16 % Hitung MSE antara A dan X1 ans = 0.7792
>> A=[1 2 3 1;1 5 2 2;1 1 4 1;1 3 4 5]; % Matriks yang lain >> p=1; % parameter kompresi >> [U,S,V]=svd(A); % Tentukan SVD dari A >> UA=U(:,1:p); % Left singular vector >> SA=S(1:p,1:p); % Singular value >> VA=V(:,1:p) % Right singular vector
92
>> A1=UA*SA*VA'; % Konstruksi A1 >> sum(sum((A-A1).*(A-A1)))/16 % Hitung MSE antara A dan A1 ans = 0.9811 >> X=P(A); % X adalah matriks A yang di-shuffle >> [U,S,V]=svd(X); % Hitung SVD dari X >> UX=U(:,1:p); >> SX=S(1:p,1:p); >> VX=V(:,1:p); >> X1=PInvers(UX*SX*VX'); % Konstruksi kemudian invers-kan >> sum(sum((A-X1).*(A-X1)))/16 % Hitung MSE antara A dan X1 ans = 0.6444
>> A=[1 2 3 1;1 5 2 2;1 1 4 1;1 3 4 5]; % Matriks A >> rank(A) % rank dari A ans = 4 >> p=2; % p <= r >> [U,S,V]=svd(A); % SVD dari A >> UA=U(:,1:p); % Left singular vector >> SA=S(1:p,1:p); % singular diagonal matrix >> VA=V(:,1:p); % Right singular vector >> A2=UA*SA*VA'; % Rekonstruksi hasil kompresi >> sum(sum((A-A2).*(A-A2)))/16 % MSE ans = 0.3625 >> X=P(A); % Matriks A di-shuffle
93
>> [U,S,V]=svd(X); % SVD dari X >> UX=U(:,1:p); % Left singular vector >> SX=S(1:p,1:p); % Singular diagonal matrix >> VX=V(:,1:p); % Right singular vector >> X2=SInvers(UX*SX*VX'); % Rekonstruksi dan invers-kan >> sum(sum((A-X2).*(A-X2)))/16 % Hitung MSE ans = 0.0484
3.2
Contoh Langkah Menyimpan Variabel MATLAB ke MAT-File
>> A=imread('lena484.jpg'); >> AR=double(A(:,:,1)); >> AG=double(A(:,:,2)); >> AB=double(A(:,:,3)); >> [U,S,V]=svd(AR); >> p=65; >> Up_red=uint8(U(:,1:p)); >> Up_red=U(:,1:p); >> Sp_red=S(1:p,1:p); >> Vp_red=V(:,1:p); >> [U,S,V]=svd(AG); >> Up_green=U(:,1:p); >> Sp_green=S(1:p,1:p); >> Vp_green=V(:,1:p); >> [U,S,V]=svd(AB); >> Up_blue=U(:,1:p); >> Sp_blue=S(1:p,1:p); >> Vp_blue=V(:,1:p); >> Ap(:,:,1)=uint8(Up_red*Sp_red*Vp_red'); >> Ap(:,:,2)=uint8(Up_green*Sp_green*Vp_green'); >> Ap(:,:,3)=uint8(Up_blue*Sp_blue*Vp_blue'); >> save SVD_r65_lena484.jpg.mat Ap;
