INTERPRETASI SINGULAR VALUE DECOMPISITION

INTERPRETASI SINGULAR VALUE DECOMPISITION (SVD) PADA PENGOLAHAN CITRA DIGITAL Della Maulidiya Program Studi Pendidikan Matematika Jurusan PMIPA FKIP Universitas Bengkulu ABSTRAK Singular Value Decomposition (SVD) merupakan sebuah teknik komputasi numerik yang melakukan faktorisasi terhadap sebuah matriks tak nol sehingga diperoleh tiga matriks tak nol yang baru. Salah satu matriks yang diperoleh dari proses SVD akan memuat nilai-nilai singular dari matriks asal. Nilai-nilai singulir berguna untuk suatu matriks yang merupakan transformasi dari sebuah ruang vektor ke ruang vektor yang lain atau dimensi berbeda. Tiga karakteristik SVD yaitu matriks hanger, stretcher dan aligner dimanfaatkan dalam pengolahan citra digital. Asumsi yang digunakan yaitu sebuah citra digital m x n pixel diterjemahkan sebagai sebuah matriks berukuran m x n. Informasi yang disimpan dalam matriks tersebut bilangan-bilangan yang menyatakan intensitas warna tiap pixel citra. Proses SVD pada matriks citra akan mendekomposisi matriks tersebut menjadi tiga matriks baru. Setiap matriks memuat informasi spesifik tentang citra yang diproses. Penelitian ini meneliti jenis informasi yang disimpan dalam masing-masing matriks hasil faktorisasi matriks citra menggunakan SVD. Selanjutnya diteliti pengaruh perubahan pada satu atau lebih matriks hasil SVD terhadap citra jika ketiga matriks tersebut direkonstruksi kembali. Penelitian ini diawali dengan melakukan studi literatur untuk menganalisis algoritma-algoritma SVD. Selanjutnya berdasarkan algoritma yang telah dianalisis peneliti membuat program menggunakan MATLAB untuk memvisualisasikan informasi yang disimpan dalam matriks citra dan matriks hasil proses SVD. Citra digital yang akan digunakan berupa citra grayscale dengan ukuran yang berbeda yaitu citra lenna.jpg dan cameramen.jpg. Kata Kunci : Singular Value Decomposition, matriks hanger, matriks stretcher, matriks aligner, pengolahan citra digital

I. PENDAHULUAN Singular Value Decomposition (SVD) merupakan teknik komputasi numerik yang melakukan faktorisasi terhadap sebuah matriks tak nol sehingga diperoleh tiga matriks tak nol. Salah satu matriks yang diperoleh dari proses SVD akan memuat nilai-nilai singular dari matriks asal. Istilah “nilai singulir” menyatakan jarak antara sebuah matriks dan himpunan matriks-matriks singulir. Nilai-nilai singulir berguna untuk suatu matriks yang merupakan transformasi dari sebuah ruang vektor ke ruang vektor yang lain atau dimensi berbeda. Sistem persamaan aljabar yang overdetermined atau undetermined adalah contoh transformasi ruang vektor berbeda. Alkiviadis dan Gennadi (2002) memaparkan tiga karakteristik SVD, yaitu matriks hanger, stretcher dan aligner. Matriks U merupakan matriks hanger, matriks  adalah matriks strecther dan matriks V menjadi matriks aligner. Pada dasarnya matriks apapun dapat dibagi menjadi ketiga matriks tersebut. Matriks hanger dan aligner merupakan matriks ortogonal, maka perkalian dengan kedua matriks tersebut tidak akan mengubah bentuk objek karena kedua matriks itu akan mempertahankan bentuk objek. Sementara itu, matriks stretcher merupakan matriks diagonal. Perkalian dengan matriks stretcher akan merentangkan suatu objek. Jika suatu kurva dikalikan dengan matriks diagonal, maka semua nilai pada kurva sepanjang sumbu x dan y akan terentang. Misal, jika terdapat sebuah kurva berbentuk lingkaran, maka setelah kurvia tersebut dikalikan dengan matriks stretcher, bentuk kurva akan menjadi elips. Untuk mengembalikan kurva ke bentuk asalnya, dapat dilakukan perkalian dengan matriks yang komponen-komponennya merupakan kebalikan dari matriks stretcher. Sifat ketiga matriks tidak hanya berlaku saat matriks-matriks tersebut dikalikan dengan objek lain saja, namun juga dalam pembentukan suatu objek. Ketiga karakteristik SVD tersebut dimanfaatkan dalam pengolahan citra digital. Asumsi yang digunakan yaitu sebuah citra digital m x n pixel diterjemahkan sebagai sebuah matriks berukuran m x n. Informasi yang disimpan dalam matriks tersebut bilangan-bilangan yang menyatakan intensitas warna tiap pixel citra. Proses SVD pada matriks citra akan mendekomposisi matriks tersebut menjadi tiga matriks baru. Masing-masing matriks memuat informasi spesifik tentang citra yang diproses. Penelitian ini meneliti jenis informasi yang disimpan dalam masing-masing matriks hasil faktorisasi matriks citra menggunakan SVD. Selanjutnya diteliti pengaruh perubahan pada satu atau lebih matriks hasil SVD terhadap citra jika ketiga matriks tersebut direkonstruksi kembali.

II. METODOLOGI PENELITIAN Penelitian ini dilaksanakan menggunakan metode-metode : studi literatur, pembuatan program menggunakan MATLAB dan eksperimen menggunakan citra digital sebagai masukan pada program yang telah dibuat. Penelitian ini diawali dengan melakukan studi literatur menggunakan berbagai referensi berupa buku, jurnal ilmiah, dan sumber elektronik. Studi literatur digunakan untuk menganalisis algoritma-algoritma SVD. Selanjutnya berdasarkan algoritma yang telah dianalisis peneliti membuat kode program SVD menggunakan MATLAB untuk memvisualisasikan informasi yang disimpan dalam matriks citra dan matriks hasil proses SVD. Citra digital yang akan digunakan berupa citra grayscale dengan ukuran yang berbeda yaitu citra lenna.jpg 512x512 piksel dan cameramen.jpg 256x256 piksel. III. HASIL PENELITIAN DAN PEMBAHASAN Moler (2004) menyatakan bahwa sebuah nilai singulir dan pasangan vektor-vektor singulir dari sebuah matriks A adalah skalar tak-negatif σ dan dua vektor tak nol u dan v . Pendefinisian nilai-nilai singulir dapat dinyatakan dalam bentuk matriks berikut. AV = U ATU = VT Notasi AT menyatakan transpose matriks A. Matriks  adalah matriks diagonal yang berukuran sama dengan A. Vektor-vektor singulir selalu dapat ditentukan saling tegak lurus (ortogonal), sehingga matriks U dan V memiliki kolom berupa vektor singulir ternormalisasi. Jika A adalah matriks berukuran m x n, maka nilai-nilai singulir A didefinisikan sebagai akar kuadrat dari nilai-nilai eigen ATA. Nilai-nilai singulir A yaitu 1, 2, . . . , n memenuhi kondisi : 1 ≥ 2 ≥. . . ≥ n ≥ 0. Dengan demikian matriks A dapat difaktorkan sebagai berikut. A = UVT Dalam aljabar linier, pemfaktoran di atas dikatakan relevan jika matriks Am x n merupakan pemetaan dari ruang-n ke ruang-m. Faktorisasi matriks A tersebut dinamakan Singular Value Decomposition (SVD). Matriks Um x m dan matriks Vn x n merupakan matriks ortogonal. Matriks m x n memuat nilai-nilai singulir 1 ≥ 2 ≥. . . ≥ r ≥ 0 dan r+1 = r+2 = n = 0. Matriks U dan V tidak secara unik ditentukan oleh A tetapi matriks  harus memuat nilai-nilai singulir matriks A. Kolom-kolom V dinamakan vektor-vektor singulir kanan matriks A. Untuk baris ortonormal {v1, . . ., vn} yang memuat vektor-vektor dari matriks simetris ATA yang berukuran n x n maka matriks V dinyatakan sebagai V  v1  v n . Kolom-kolom U dinamakan vektor-vektor

  u m , dimana {u , . . ., u } adalah himpunan ortonormal di R

m U  u1  dan 1 r 1 setiap ui didefinisikan sebagai u i  Avi untuk i = 1, 2, . . ., r dan r = rank(A). Rank matriks A menyatakan i

singulir kiri matriks A yaitu

banyaknya baris tak nol dari bentuk bebas linier matriks A. Sensitivitas nilai-nilai singulir lebih mudah untuk dikarakterisasi dibanding nilai-nilai eigen karena masalah nilai singulir selalu perfectly well conditioned [Moler: 2004]. Sebuah analisis perturbasi memuat persamaan

    U H  A  AV . Tetapi karena U dan V bersifat ortogonal, maka akan diperoleh   A . Perturbasi dan akurasi diukur terhadap norm suatu matriks atau ekivalen dengan nilai singulir terbesar

A

2

  1 . Sedangkan akurasi nilai singulir yang lebih kecil diukur terhadap nilai singulir yang lebih besar.

Algoritma yang digunakan untuk menghitung SVD pada MATLAB yaitu algoritma faktorisasi QR dan LQ berdasarkan rutin LAPACK dengan batas maksimum 75 iterasi. Fungsi svd pada MATLAB selalu menghitung nilai-nilai singulir dengan akurasi full floating-point. Komputasi SVD menggunakan rutin LAPACK dilakukan berdasarkan dua tahap berikut [Anderson dkk. : 1999]. (1) Matriks Am x n direduksi menjadi bentuk bidiagonal A = U1BV1T dimana U1 dan V1 adalah matriks ortogonal. Matriks B adalah matriks upper-bidiagonal jika m  n dan lower-bidiagonal untuk m < n. Dengan demikian B memiliki elemen tak-nol hanya pada diagonal utama dan superdiagonal pertama (untuk m  n) atau subdiagonal pertama (untuk m < n).

 a1  B   

b1   a2   atau B   bn1   an 

 a1 b  1   

a2 

 bn1

     an 

(2) SVD untuk matriks bidiagonal B dihitung sebagai berikut : B = U2 V2T dimana U2 dan V2 matriks diagonal dan  adalah matriks diagonal. Vektor-vektor singulir A yaitu U = U1U2 dan V = V1V2. Tahap kedua dikerjakan menggunakan faktorisasi QR secara iteratif. Kompleksitas algoritma tersebut yaitu O((mn)3) dimana m x n adalah ukuran matriks A. Algoritma SVD di atas

  T

bersifat bacward stable, artinya SVD terkomputasi untuk matriks Amxn yaitu UV matriks A + E dimana

E A

2

mendekati SVD eksak dari

 p m, n 

2

Fungsi p(m,n) adalah fungsi pembangkit m dan n. Jadi SVD eksak yaitu :

     A  E  U  U  V  V







      U  U dan V  V adalah matriks ortogonal dimana U  p m, n  dan V  p m, n  .  Setiap nilai singulir terkomputasi  i memiliki selisih terhadap nilai singulir eksak  i yang dirumuskan Sehingga

sebagai berikut.

  i   i  pm, n      1 Jadi nilai-nilai singulir yang besar (mendekati 1) dihitung dengan akurasi relatif tinggi tetapi perhitungan nilai yang lebih kecil mempunyai akurasi relatif rendah. Vektor-vektor singulir terkomputasi selalu mendekati ortogonal, dimana presisi yang digunakan tergantung seberapa jauh selisih vektor tersebut terhadap vektor singulir eksak, yang dirumuskan sebagai berikut.

  u iT u j  O  

untuk i  j

Sedangkan angular difference antara vektor singulir kiri terkomputasi memenuhi batas aproksimasi berikut.

 u i dan vektor singulir kiri eksak u i

pm, n     A 2   u i , u i   min j i  i   j Untuk n < m, angular difference di atas didefinisikan sebagai berikut.

  u i , u i  

pm, n     A



2

min min j i  n   j ,  n



Batas galat (error) yang dijelaskan di atas juga berlaku untuk vektor singulir kanan terkomputasi singulir kanan eksak

 vi dan vektor

vi .

Komputasi SVD untuk matriks bidiagonal dilakukan dengan lebih akurat karena reduksi sebuah matriks menjadi matriks bidiagonal akan menimbulkan galat baru. Setiap nilai singulir tekomputasi untuk matriks bidiagonal dihitung dengan menggunakan batas galat berikut.

  i   i  p m, n      i Sedangkan angular error untuk singulir kiri terkomputasi sebagai berikut.

  u i , u i  

min j  i

 u i dan vektor singulir kiri eksak u i dirumuskan

p m, n    i  j i   j

Batas tersebut berlaku pula untuk vektor singulir kanan terkomputasi

 vi dan vektor singulir kanan eksak vi .

Sebuah citra digital m x n piksel dapat dianggap sebagai matriks m x n pada ranah bilangan riil R. Sebagai sebuah matriks, citra digital dapat difaktorisasi menggunakan SVD. Pada objek citra, matriks stretcher (matriks singulir ) menyatakan tingkat kecerahan tiap kanal pada citra. Makin besar nilai singulir yang terkandung dalam matriks , makin cerah citra tersebut [Ganic dan Eskicioglu: 2004]. Nilai-nilai singulir terbesar menentukan kualitas visual citra sedangkan nilai-nilai singulir yang lebih kecil sangat sensitif terhadap noise [Kong dkk.: 2006]. Gambar di bawah ini memperlihatkan perbandingan tingkat kecerahan sebuah citra jika nilai-nilai singulir terbesar diubah.

Gambar 1. Pengaruh perubahan nilai singulir terbesar terhadap tingkat kecerahan citra digital

Nilai-nilai singulir juga memiliki tingkat stabilitas yang sangat baik sehingga nilai singular ini tidak akan mengalami perubahan signifikan jika terjadi sedikit gangguan pada citra [Liu dan Tan: 2002]. Sebagian besar teknik penyisipan tanda air berbasis SVD menyisipkan tanda air pada matriks  dengan memanfaatkan sifat tersebut sehingga penyisipan yang dilakukan tidak menimbulkan gangguan yang berarti. Matriks U dan V akan mempertahan bentuk obyek sehingga bentuk geometris dan tampilan citra ditentukan oleh kedua matriks tersebut [Ganic dan Eskicioglu, 2004]. Gambar di bawah ini memperlihatkan pengaruh perubahan matriks U dan V terhadap tampilan citra. Gambar 2 memperlihatkan bahwa pengubahan matriks U akan menimbulkan noise secara horisontal sedangkan pengubahan matriks V menyebabkan noise secara vertikal.

Gambar 2. Pengaruh perubahan matriks U dan V terhadap kualitas visual citra Eksperimen Zhang dan Li (2005) menunjukkan bahwa jika kedua matriks U dan V sebuah citra diganti menggunakan matriks U dan V citra lain maka secara visual, citra hasil rekonstruksi SVD tersebut akan mirip dengan citra kedua, seperti diperlihatkan dalam gambar 3(c). Namun nilai-nilai singulir citra hasil rekonstruksi sama dengan nilai-nilai singulir citra pertama.

Gambar 1. Pengaruh penggantian kedua matriks U dan V sebuah citra terhadap kualitas visual citra Pada eksperimen di atas, gambar 3 (b) menggunakan matriks U dan V dari citra cameraman 256x256 piksel sedangkan gambar 3(c) menggunakan citra cameraman 512 x 512 piksel untuk menggantikan matriks U dan V citra lenna 512x512 piksel. Berdasarkan penelitian ini maka disimpulkan bahwa pada pemrosesan citra digital, nilai-nilai singulir hasil proses SVD pada sebuah citra menyatakan luminansi/tingkat kecerahan dan vektor-vektor singulir merepresentasikan geometris citra. IV. SIMPULAN DAN SARAN Proses SVD pada matriks citra akan mendekomposisi matriks tersebut menjadi tiga matriks baru yaitu matriks hanger, stretcher dan aligner. Pada objek citra, matriks stretcher (matriks singulir ) menyatakan tingkat kecerahan tiap kanal pada citra vektor-vektor singulir (hanger dan aligner) merepresentasikan geometris citra. Makin besar nilai singulir yang terkandung dalam matriks , makin cerah citra tersebut. Nilai-nilai singulir terbesar menentukan kualitas visual citra sedangkan nilai-nilai singulir yang lebih kecil sangat sensitif terhadap noise. Pengolahan citra digital menggunakan SVD baik untuk kebutuhan pemampatan (kompresi), pemberian tanda air (watermarking) atau proses lainnya perlu mempertimbangkan pengaruh proses pengubahan nilai pada satu atau lebih matriks hanger, stretcher atau aligner terhadap kualitas citra hasil proses. DAFTAR PUSTAKA Ganic, E. and Eskicioglu, Ahmet M. 2004. Robust DWT-SVD domain image watermarking : embedding data in all frequencies. ACM Multimedia and Security Workshop. Magdeburg. Germany. Pp. 166-174.

Gonzalez, R.C. and Wintz, P. 2002. Digital image processing. Prentice Hall. Kaufman, Jason R. 2006. Digital video watermarking using Singular Value Decomposition and TwoDimensional Principal Component Analysis. Thesis. The College of Engineering and Technology of Ohio University. Kim, Kyung-Su. Lee, Min-Jeong. And Lee, Heung-Kyu. Blind image watermarking scheme in DWT-SVD domain. IEEE Kong, Wenhai. Yang, Bian. Wu, Di. and Niu, Xiamu. 2006. SVD based blind video watermarking algorithm. Proceedings of the First International Conference on Innovative Computing, Information and Control (ICICIC'06). IEEE. Liu, Ruizhen. and Tan, Tieniu. 2002. An SVD-based watermarking scheme for protecting rightful ownership. IEEE Transactions on Multimedia. Vol. 4. No.1. Moler, Cleve B. 2004. Numerical computing with MATLAB. The Society for Industrial and Applied Mathematics (SIAM). Poole, D. 2003. Linear algebra : a modern introduction. The Wadsworth Group. Thomson Learning. Inc. Zhang, Xiao-Ping. 2005. Comments on “An SVD-based watermarking scheme for protecting rightful ownership”. IEEE Transactions on Multimedia. Vol. 7. No.2.