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 halaman web (web page) adalah citra (image). Besar kecilnya ukuran citra akan mempengaruhi cepat lambatnya halaman tersebut terbuka. Oleh karena itu, dilakukan beberapa cara untuk mempercepat terbukanya sebuah halaman yang memuat citra.
Salah satu cara mempercepatnya adalah dengan memampatkan data (compress the data) citra tersebut. Tujuannya adalah agar citra yang disertakan ukurannya menjadi lebih kecil. Sehingga beban yang diberikan kepada browser dalam membuka halaman tersebut menjadi lebih kecil dengan tanpa kehilangan kelayakan citra tersebut untuk dilihat secara kasat mata. Selain itu juga dapat mengurangi ruang penyimpanan di dalam media penyimpanan data, dalam hal ini storage device, seperti hard disk, floppy disk, zip drive, flash drive, CD dan lain-lain. Ada banyak metode pemampatan data. Dalam tulisan ini dibahas suatu metode pemampatan data pada citra yang didasarkan pada teori dekomposisi (faktorisasi) matriks.
1.1 Latar Belakang Masalah
Dekomposisi nilai singular atau singular value decomposition (SVD) adalah salah satu dari sekian banyak dekomposisi matriks. Pada dasarnya ada banyak dekomposisi suatu matriks. Ada yang bergantung pada ukuran matriks seperti dekomposisi LU yang mensyaratkan matriks persegi, dan ada yang tidak mempermasalahkannya, seperti dekomposisi yang digunakan dalam metode pemampatan data ini, yaitu Singular Value Decomposition (SVD) atau Dekomposisi Nilai Singular. Dekomposisi ini memfaktorkan suatu matriks menjadi tiga bagian dengan karakterisasinya masing-masing.
Dekomposisi ini memiliki banyak aplikasi pada berbagai bidang. Aplikasi SVD diantaranya adalah sebagai berikut (Scheick, J.T., 1997):
- Penyelesaian persamaan Ax = b dan Pseudo-Invers
- Penghitungan rank suatu matriks
- Menyelesaikan sensitifitas sistem persamaan
- Pattern Recognitions
Aplikasi yang lain diantaranya pada imunology, molecular dynamics, small-angle scattering, information retrieval, signal processing, dan image compression. Pada tulisan ini yang dibahas adalah aplikasi SVD yang terakhir, yaitu image compression. Image compression atau pemampatan citra merupakan aplikasi SVD yang paling umum. Sifat-sifat dari SVD yang memberikan aproksimasi terbaik untuk suatu matriks X, dapat digunakan dalam pemampatan citra.
Seperti metode pemampatan data yang lain, metode pemampatan data menggunakan SVD juga bertujuan meminimalisir ukuran data, tetapi dengan data yang lebih sedikit ini masih tetap bisa memberikan informasi yang mendekati informasi aslinya. Hanya saja pada metode ini ada perbedaan yang cukup mendasar dengan metode yang lain. Pada metode pemampatan data yang lain biasanya melibatkan kode-kode. Kode-kode yang berulang ditulis kembali dalam kode yang lain sehingga lebih singkat dan ini akan mengurangi ukuran data tersebut, atau dengan cara yang lain tetapi masih melibatkan kode-kode. Sedangkan pada metode yang dibahas disini, yang menjadi objek bukan kode-kode melainkan bit-bit bilangan. Bit-bit bilangan ini merepresentasikan intensitas citra di titik-titik tertentu (pixel). Citra adalah matriks dengan entrinya adalah bilangan-bilangan tersebut. Matriks inilah yang diolah untuk mendapatkan citra yang baru dengan metode ini.
Konsep dasar pemampatan data adalah mencari vektor yang menempati arah yang cukup tepat atau hampir sama dengan vektor-vektor data yang akan dimampatkan. Citra yang berukuran m x n pixel (picture element) merupakan suatu matriks berukuran m x n. Jika setiap kolom matriks ini diperlakukan sebagai kumpulan vektor-vektor data maka memampatkan citra tersebut adalah proses menentukan suatu matriks yang kolom-kolomnya merupakan vektor yang memiliki arah yang hampir sama dengan vektor-vektor kolom dari citra aslinya.
Selanjutnya, penyelesaian permasalahan mencari vektor-vektor yang memenuhi ketentuan di atas (menempati arah yang hampir sama) merupakan left-singular vector dari citra aslinya. Langkah ini tidak lain adalah untuk mengekstrak informasi yang cukup dari citra tersebut menggunakan SVD untuk menyusun kembali citra yang mendekati citra asal (original image). Pemahaman yang sederhana dari metode ini terlihat pada bilangan phi (). Sampai saat ini belum ditemukan nilai yang merepresentasikan secara tepat berapakah bilangan ini, yang ada hanyalah nilai pendekatan, seperti 22/7 atau 3,14 atau 3,1415926535897932 384626433832795 dan bilangan-bilangan ini tidak sepenuhnya tepat, karena dengan beberapa keterbatasan hanya mampu merepresentasikan pendekatannya saja. Begitu juga dengan metode pemampatan dalam tulisan ini, yaitu mendapatkan citra lain yang merupakan pendekatan yang cukup baik untuk merepresentasikan citra asli.
Konsep yang mendasari pemikiran ini berangkat dari teorema ‘extended maximal principle’ dari suatu bentuk Rayleigh Quotient. Dimana pemaksimum dari masalah ini tak lain adalah vektor eigen dari suatu matriks hermitian. Lebih lanjut jika dikaitkan dengan dekomposisi nilai singular, pemaksimum masalah ini (dengan suatu kendala) adalah left-singular vector dari matriksnya.
1.2 Perumusan Masalah
Masalah yang diteliti dalam tulisan ini adalah bagaimana dasar pemampatan data dalam tinjauan matematis dan bagaimana cara pemampatan citra menggunakan dekomposisi nilai singular, kemudian mengimplementasikan metode pemampatan citra menggunakan dekomposisi nilai singular ke dalam sebuah program MATLAB. Titik tekan yang dibicarakan dalam tulisan ini diberikan dalam Bab V.
Secara garis besar, perumusan masalah yang dibahas dalam tulisan ini terdiri dari beberapa langkah sebagai berikut:
- Bagaimana definisi nilai singular dan dekomposisi nilai singular.
- Bagaimana menentukan dekomposisi nilai singular dari suatu matriks.
- Bagaimana dasar-dasar pemampatan data secara matematis.
- Bagaimana definisi citra
- Bagaimana cara pemampatan citra menggunakan dekomposisi nilai singular.
- Bagaimana implementasi metode pemampatan citra menggunakan dekomposisi nilai singular ke dalam bahasa pemrograman MATLAB.
1.3 Batasan Masalah
Satu hal yang paling mendasar dan menjadi batasan dalam mengemukakan metode ini adalah pada teknik pemampatannya. Dalam dunia komputer, data compression secara lengkap melibatkan beberapa proses mulai dari compress sampai decompress. Data yang telah dimampatkan disimpan dalam format file (berkas) yang lain. File yang baru ini memiliki ukuran yang lebih kecil dari pada data sebenarnya. Artinya, hasil pemampatan hanya menyimpan data-data karakteristik dari data sebenarnya. Kemudian, untuk mendapatkan informasi dari file ini dilakukan proses balikan yang disebut dengan decompress. Informasi yang diperoleh dari data hasil decompress bisa sama (tidak ada data yang hilang) atau tidak sama (terjadi pengurangan data) dengan informasi sebenarnya.
Tulisan ini hanya sebatas memberikan metode secara umum. Tidak membicarakan mengenai file yang disimpan (dengan ukuran yang lebih kecil) seperti yang disebutkan di atas. Metode yang dibahas dalam tulisan ini bisa dikatakan bukan image compression melainkan membuat salinan suatu file citra dengan ukuran yang lebih kecil. ‘Salinan’ inilah yang disebut sebagai hasil pemampatan. Dilihat dari hasilnya, secara prinsip metode tersebut bisa dikatakan sebagai data compression. Tapi, dilihat dari langkah-langkah dalam metode tersebut, secara konsep ‘belum’ bisa dikatakan sebagai data compression.
Jadi, secara garis besar tulisan tidak memberikan uraian secara lengkap mengenai metode tersebut sesuai dengan kaidah-kaidah atau konsep dalam pemampatan data. Tulisan ini hanya memperlihatkan bagaimana aljabar linear secara sederhana dapat diterapkan pada sebuah file citra sedemikian sehingga diperoleh file citra yang lain dengan informasi yang cukup sama tetapi dengan ukuran file yang lebih kecil. Dengan kata lain, tulisan ini memberikan salah satu contoh aplikasi dekomposisi nilai singular. Untuk selanjutnya, pengertian yang sama dengan batasan ini tetap disebut dengan pemampatan data (data compression) khususnya citra (image compression).
Metode atau algoritma pemampatan data yang dibahas dalam tulisan ini dibatasi pada data citra. Hal ini dikarenakan sejauh ini, yang penulis ketahui hanya data citra yang dapat direpresentasikan ke dalam sebuah matriks. Karena metode ini didasarkan pada teori matriks maka operasi-operasi yang dapat dilakukan hanya terdefinisi pada matriks.
Kemudian, citra yang diperoleh dari hasil pemampatan merupakan citra yang independen (citra yang berbeda). Selain itu telah dijelaskan bahwa citra hasil ini merupakan citra ‘pendekatan’ dari citra asli. Seperti kasus pada bilangan phi, jika diambil bilangan 3,14 maka nilai ini dikatakan nilai yang cukup dekat dengan phi. Nilai pendekatan ini hanya menyertakan dua bagian pertama yang utama dari phi, yaitu 1 dan 4. Karena 3,14 merupakan nilai pendekatan maka tidak mungkin untuk mendapatkan nilai phi yang sebenarnya dari nilai ini. Sehingga dengan demikian dari hasil pemampatan sebuah citra amat mustahil untuk mendapatkan kembali citra dengan resolusi yang lebih baik (tentunya dengan ukuran yang lebih besar) dari pada citra tersebut, karena ada informasi yang tidak disertakan. Tulisan ini juga membatasi permasalahan pada pemampatan data yang tidak menggunakan kode-kode. Tetapi khusus dalam metode ini murni menggunakan operasi matriks.
Pada bagian akhir, diberikan program yang mengimplementasikan metode ini. Program tersebut ditulis dalam bahasa MATLAB dan sepenuhnya menggunakan fungsi-fungsi yang telah tersedia di dalam MATLAB atau fungsi bawaan (built in function). Selain fungsi-fungsi tersebut, juga memanfaatkan fungsi-fungsi yang disediakan dalam toolbox image processing dari MATLAB.
Sebagai sebuah catatan bahwa metode ini bekerja efektif pada format citra yang telah terkompresi (compressed image), contoh: JPEG. Sebaliknya tidak begitu baik pada citra tanpa kompresi (uncompressed image), contoh: BMP, ICO, dan CUR. Walaupun dihasilkan citra dengan kualitas yang tidak sebaik aslinya, bahkan lebih buruk, tetapi tidak banyak mengurangi besarnya ukuran file.
Batasan yang lain, MATLAB mendukung pengolahan citra hanya untuk beberapa format citra. Mulai dari pembacaan sampai menuliskannya kembali ke dalam sebuah file. Namun, ada beberapa format citra yang bisa dibaca oleh MATLAB tetapi tidak disediakan fungsi atau metode untuk menuliskan citra tersebut ke dalam sebuah file. Salah satunya adalah citra dengan format GIF (Graphic Interchange Format). Format ini dapat dibaca oleh MATLAB, tetapi MATLAB tidak menyediakan fungsi atau metode untuk menulis file citra dengan format ini. Oleh karena itu, program yang dibuat untuk mengimplementasikan metode ini ‘tidak menerima’ input file citra dengan format GIF dikarenakan tidak adanya metode untuk menulis file citra dengan format ini.
1.4 Maksud dan Tujuan Penulisan
Maksud penulisan tulisan ini adalah untuk memenuhi salah satu prasyarat untuk mendapatkan gelar sarjana strata satu dibidang matematika. Sedangkan tujuan penulisan tulisan ini adalah untuk:
- Mengetahui salah satu aplikasi dari SVD.
- Membahas teori-teori dasar dekomposisi nilai singular dan konsep dasar pemampatan citra menggunakan dekomposisi nilai singular.
- Menerapkan metode pemampatan ke dalam program menggunakan bahasa pemrograman MATLAB
1.5 Tinjauan Pustaka
Dalam “Linear Algebra with Applications” (Scheick, J.T., 1997) menjelaskan tentang salah satu dekomposisi matriks dan beberapa aplikasinya. Salah satu dekomposisi matriks yang diberikan adalah dekomposisi nilai singular dengan aplikasinya pada pattern recoginition. Khususnya, pada feature capturing, yakni pemampatan citra. Beberapa konsep dasar yang digunakan adalah Rayleigh Quotients dan extended maximal principle.
Beberapa buku penunjang yang dijadikan sebagai referensi dalam menyusun landasan teori SVD diantaranya adalah Howard Anton (2000) dalam “Elementary Linear Algebra”, Jack L. Goldberg (1991) dalam “Matrix Theory with Applications”, W. Keith Nicholson (2001) dalam “Elementary Linear Algebra”, dan Lyod N. Trefethen (1997) dalam “Numerical Linear Agebra” serta beberapa buku komputer yang membahas mengenai citra.
Sumber-sumber dari internet juga membahas metode yang sama pada pemampatan data menggunakan dekomposisi nilai singular. Hanya saja tulisan-tulisan tersebut lebih banyak berbicara pada tinjauan komputer dan sedikit sekali mengupas sisi matematisnya. Bahkan beberapa diantaranya sama sekali tidak membicarakan latar belakang secara matematis mengapa metode ini bisa dilakukan, salah satunya pada artikel “The Singular Value Decomposition of an Image” oleh Kristian Sandberg (1998) yang hanya memberikan lab worksheet menggunakan MATLAB. Namun, bagaimanapun juga sumber-sumber tersebut bisa dijadikan rujukan dalam memperdalam pemahaman metode pemampatan ini.
Artikel yang lain adalah “Image Compression with Singular Value Decomposition” (http://www.prism.gatech.edu/~gtg874a/ imcomp.html) dan “Image Compression with Singular Value Decomposition” (http://peter/wreck.org/reports/Math4305/).
1.6 Sistematika Penulisan
Untuk memberikan gambaran tentang materi pada tulisan ini, maka materi tersebut disusun dalam sistematika tertentu. Sistematika penulisan tulisan ini adalah sebagai berikut:
BAB I: Pendahuluan
Berisi tentang latar belakang masalah, perumusan masalah, batasan masalah, maksud dan tujuan penulisan, serta tinjauan pustaka.
BAB II: Dasar Teori
Berisi tentang dasar-dasar teori yang melandasi teori dekomposisi nilai singular dari suatu matriks.
BAB III: Dekomposisi Nilai Singular
Berisi pembahasan mengenai dekomposisi nilai singular, pembuktian teorema eksistensi, sifat-sifat, contoh-contoh, serta penghitungan dekomposisi nilai singular suatu matriks menggunakan MATLAB
BAB IV: Citra dan Pengolahan Citra dalam MATLAB
Berisi tentang definisi citra secara umum dan pembahasan mengenai perintah-perintah pada MATLAB yang digunakan dalam pengolahan citra khususnya pemampatan citra yang berkaitan dengan dekomposisi nilai singular.
BAB V: Pemampatan Citra Menggunakan Dekomposisi Nilai Singular
Berisi konsep dasar pemampatan data dalam tinjauan matematis, khususnya dengan membawanya pada konsep dan karakteristik dekomposisi nilai singular dari suatu matriks melalui konstruksi permasalahan yang dihadapi. Juga definisi Rayleigh Quotient dari suatu matriks hermitian serta pembuktian teorema extended maximal principle.
BAB VI: Implementasi
Berisi tambahan penjelasan pemrograman di MATLAB, algoritma pemampatan data yang diterapkan dalam program MATLAB, dan melakukan uji coba pemampatan terhadap beberapa file citra.
BAB VII: Penutup
Berisi kesimpulan dan saran-saran yang didapatkan selama penyusunan tulisan ini.
Download Skripsi Lengkap Image Compression With Singular Value Decomposition
