Pemampatan Citra Menggunakan Dekomposisi Nilai Singular

Khaeroni, S.Si 1 Institut Agama Islam Negeri Sultan Maulana Hasanuddin Banten

Jl. Jend. Sudirman No. 30 Serang Banten onny_11_49@yahoo.com

Abstrak Dekomposisi nilai singular adalah suatu pemfaktoran matriks dengan mengurai suatu matriks ke

dalam dua matriks uniter U dan V, dan sebuah matriks diagonal S yang berisi faktor skala yang disebut dengan nilai singular. Setiap nilai singular dalam S bersesuaian dengan suatu citra 2-dimensi yang dibangun oleh satu kolom dari U dan satu baris dari V. Citra hasil rekonstruksi adalah jumlah dari setiap citra parsial yang telah diubah skalanya menggunakan nilai singular yang bersesuaian dalam S. Nilai singular terkecil dan citra yang bersesuaian dengan nilai singular ini tidak akan ikut membangun citra asli secara signifikan. Dengan mengabaikan nilai singular yang kecil bersama dengan kolom-kolom pada U dan baris-baris pada V yang telah difaktorkan oleh nilai singular ini, citra asli akan direkonstruksi dengan cukup tepat oleh suatu himpunan data yang jauh lebih kecil dari pada matriks citra aslinya.

Kata Kunci : Nilai singular, dekomposisi nilai singular, Rayleigh Quotient, extended maximal principle, principal component basis

I. Pendahuluan

Dekomposisi nilai singular atau singular value decomposition (SVD) adalah salah satu dari sekian banyak dekomposisi matriks. 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): 1. Penyelesaian persamaan Ax = b dan Pseudo-

Invers 2. Penghitungan rank suatu matriks 3. Menyelesaikan sensitifitas sistem persamaan 4. 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.

II. Konsep dasar

Konsep dasar pemampatan data (dalam terminologi tulisan ini) 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.

Penyelesaian permasalahan mencari vektor-vektor yang memenuhi ketentuan di atas 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).

III. Batasan masalah

Dalam dunia komputer, data compression secara melibatkan 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. Kemudian, untuk mendapatkan informasi dari file ini dilakukan proses balikan yang disebut dengan decompress. Informasi yang diperoleh dari data hasil decompress bisa sama atau tidak sama dengan informasi sebenarnya.

Tulisan ini sebatas memberikan metode secara umum. Tidak membicarakan mengenai file yang disimpan 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 ini bisa disebut data compression. Tapi, dilihat dari langkah-langkah dalam metode tersebut, secara konsep ‘belum’ bisa dikatakan sebagai data compression.

Jadi, tulisan ini 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. Untuk selanjutnya, pengertian yang sama dengan batasan ini tetap disebut dengan pemampatan data khususnya citra.

IV. Dekomposisi Nilai Singular

Diberikan A matriks m x n dengan r(A) = r. Akar nilai eigen positif dari AHA disebut dengan nilai singular dari A.

Misalkan A sebarang matriks berukuran m x n dengan r(A) = r. Dekomposisi nilai singular atau Singular Value Decomposition (SVD) dari A adalah faktorisasi dalam bentuk (Nicholson, W.K., 2001):

A = USVH

dengan U = [U1 U2 . . . Um] dan V = [V1 V2 . . . Vn] merupakan matriks uniter. Matriks U berukuran m x m dan V berukuran n x n, dan S = diag(σ1, σ2, . .) adalah matriks diagonal berukuran m x n dengan σ1 ≥ σ2 ≥ . . . ≥ 0.

Dari sini,

0, , ,0 0 ,

σ⎡ ⎤= ⎢ ⎥

⎣ ⎦

HA U Vm n m m n nm n

dengan σ = diag(σ1, σ2, . . ., σr)

Kolom-kolom dari U, yaitu Ui disebut dengan vektor singular kiri (left singular vector) dan kolom-kolom dari V, yaitu Vj disebut dengan vektor singular kanan (right singular vector).

Teorema 1. Sifat-sifat SVD (Nicholson, W.K., 2001) Diberikan A matriks berukuran m x n dengan r(A) = r, dan nilai singular tak nol 1 2σ σ σ≥ ≥ ≥ r . Misalkan A dapat difaktorkan dalam bentuk

A = UDVH

dengan U = [U1 U2 . . . Um] dan V = [V1 V2 . . . Vn] merupakan matriks uniter dengan U berukuran m x m dan V berukuran n x n, dan D = diag(d1, d2, . . .) adalah matriks diagonal berukuran m x n dengan d1 ≥ d2 ≥ . . . . ≥ 0, maka 1. D = S

2. 1σ

=i ii

U AV untuk 1 ≤ i ≤ r, AVi = 0 untuk i >

r dan (AHA)Vi = σi2Vi untuk 1 ≤ i ≤ n.

3. AHUi = σiVi untuk 1 ≤ i ≤ r. 4. AHUi = 0, untuk i > r dan AAHUi = Uσi

2 untuk 1 ≤ i ≤ n.

5. {U1, U2, . . , Um} merupakan vektor-vektor eigen dari AAH dan {V1, V2, . . ., Vn} merupakan vektor-vektor eigen dari AHA.

V. Citra

Citra digital dibangun oleh pixel-pixel yang dapat dianggap sebagai sebuah titik kecil pada layar. Citra dengan ukuran m x n, adalah citra yang dibangun oleh m pixel pada arah vertikal dan n pixel pada arah horisontal. Citra digital direpesentasikan dengan matriks atas bilangan dimana setiap bilangan tersebut merepresentasikan nilai intensitas di suatu titik. Titik pada citra inilah yang disebut dengan pixel.

Jika C adalah matriks dua dimensi maka Crc adalah nilai intensitas pada posisi yang bersesuaian dengan entri pada baris r dan kolom c citra yang direpresentasikan oleh matriks tersebut.

Gambar 1. The Pixel Coordinate System

Untuk merepresentasikan citra berukuran

640 x 480 pixel, dimana setiap pixel direpresentasikan dengan 1 byte memori, memerlukan 640 x 480 x 1 byte = 307.200 byte = 300 KB = 0,29 MB.

Pada citra berwarna, nilai gray level merupakan kumpulan tiga bilangan yang merepresentasikan intensitas komponen warna merah, hijau, dan biru (RGB components).

VI. Rayleigh Quotient

Diberikan A matriks hermitian berukuran n x n dengan nilai eigen (real) λ1 ≥ . . . ≥ λn.. Misalkan x, y sebarang vektor tak nol di Cn. Karena A hermitian, ⟨Ax,y⟩ = ⟨x,Ay⟩ ∀ x,y ∈ Cn.

Rayleigh Quotient R(x) dari A terhadap x dengan dengan x ≠ 0 didefinisikan sebagai,

2

,( ) =

Ax xR x

x

Teorema 2. (Scheick , J.T., 1997) Diberikan A matriks hermitian berukuran n x n dengan nilai eigen (real) λ λ≥ ≥1 n . Jika x adalah vektor eigen dari A yang bersesuaian dengan λi maka

1. R(x) =λi , untuk suatu i. 2. λ1 ≥ R(x) ≥ λn untuk setiap x ≠ 0 di dalam Cn. 3. λ1 = max{R(x) : x ≠ 0 ∈ Cn} dan

λn = min{R(x) : x ≠ 0 ∈ Cn}.

Teorema 3. Extended Maximal Principle (Scheick, J.T., 1997). Diberikan A matriks hermitian berukuran n x n dengan nilai eigen (real) 1 2λ λ λ≤ ≤ ≤ n , dan

{ } 1=n

k ke merupakan basis eigen ortogonal untuk A, maka: 1. λn = max{R(x) : x ≠ 0} 2. λi = max{R(x) : x ≠ 0, x ⊥ en, en – 1, . . . , ei + 1}

untuk i = 1, 2, . . ., n – 1

VII. Konsep dasar pemampatan data

Diberikan n vektor data X1, X2, . . ., Xn ∈ Cm. Karena vektor-vektor data tersebut di dalam Cm maka untuk menganalisis masalah ini digunakan hasil kali dalam standar. Kemudian, dicari vektor-vektor arah yang terbaik e1, e2, . . . untuk vektor data tersebut.

Perhatikan ilustrasi berikut

Gambar 2. Vektor data didekati

dalam terminologi arah

Untuk suatu vektor unit e maka (⟨f,e⟩)e merupakan proyeksi skalar dari f pada span{e}. Pada Gambar 2, misalkan proyeksi skalar Xk pada ruang yang dibangun oleh e1 adalah a, begitu juga untuk proyeksi skalar 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 adalah vektor yang arahnya paling mendekati atau yang hampir sama dengan vektor data Xk.

Dalam tinjauan aproksimasi, jarak antara Xk dengan vektor proyeksi ini adalah yang paling dekat. Sehingga masalah yang timbul adalah meminimalkan −kX c , atau sama dengan

meminimalkan 2−kX c . Jadi,

2 2 2− = −k kX c X c

dan nilai dari 2

kX adalah tetap maka

meminimalkan 2−kX c sama dengan

meminimalkan 2− c atau memaksimalkan 2c .

Dalam tinjauan norm, pada ilustrasi di atas, terlihat bahwa agar vektor c menunjuk arah yang paling tepat dengan Xk, norm dari c harus dimaksimalkan.

Perhatikan bahwa,

2 22 23 3 3 3

2

3

, ,

,

= =

=

k k

k

c X e e X e e

X e

Dari sini didefinisikan

2

1

( ) ,=

≡ ∑n

kk

D e X e , sehingga D(e) merupakan

ukuran seberapa baik e 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). Pemilihan e = ep yang ortogonal dengan e1, . . ., ep -1, untuk suatu p, dimaksudkan agar penjumlahan D(e) seperti definisi di atas dapat dilakukan.

Perhatikan bahwa 2

1 1

( ) , , ,= =

= =∑ ∑n n

k k kk k

D e X e X e X e

1 1

, ,= =

= =∑ ∑n n

H Hk k k k

k k

X e e X e X X e

Sehingga

( ) = =H H HD e e XX e e Qe ,

dengan 1[ ]= nX X X dan Q = XXH.

VIII. Konstruksi masalah

Permasalahan di atas dapat disajikan sebagai berikut:

Memaksimumkan eHQe dengan 1=e Jika diberikan e1, . . ., ep-1, permasalahan

di atas menjadi: Memaksimumkan eHQe dengan 1=e ,

dan e ⊥ e1, . . ., ep-1 Permasalahan ini tidak lain merupakan

extended maximal principle untuk Rayleigh Quotient dari Q, dengan

2

,( )

1= = =

HHQe e e QeR e e Qe

e

Menurut Teorema 3 vektor pemaksimal

R(e) merupakan vektor-vektor eigen dari Q yang ortogonal, sebut e1, e2, . . .em. Dan menurut Teorema 2, diperoleh barisan nilai maksimumnya adalah D(e1) = λ1, D(e2) = λ2, . . . , D(em) = λm, dengan 1 2λ λ λ≤ ≤ ≤ m tak lain merupakan nilai-nilai eigen dari Q. Jika m kecil dan λm tidak terlalu kecil (tidak dekat ke nol) maka nilai eigen dan vektor eigen tersebut bisa dihitung dari Q dengan cara biasa.

Di lain pihak, perhatikan bahwa nilai eigen tak nol dari Q = XXH tak lain adalah 2λ σ=i i dan menurut Teorema 1 bagian 4), vektor eigennya adalah ei = Ui dengan X = USVH merupakan dekomposisi nilai singular dari X dengan nilai singular dari X adalah σ i .

Basis { } 1=

mk k

e untuk Cm yang ditemukan dalam proses di atas adalah ortonormal karena U uniter. Dengan demikian setiap x ∈ Cm dapat ditulis sebagai

1ξ

=

= ∑m

i ii

x e dengan 2

,,ξ = =i

i i

i

x ex e

e

Koordinat dari x di dalam basis ini, yaitu ξ i , disebut principal components dari x. Basis

{ } 1=

mk k

e disebut principal component basis. Permasalahan yang muncul dalam

pemampatan data adalah: Berapa banyak ξ i yang diperlukan agar cukup efisien untuk merepresentasikan x?

Misalkan 1

ξ=

= ∑p

p i ii

s e merupakan

proyeksi dari x pada span{ } 1=

pk k

e . Dari sini,

2 22

2 2 2 2

1 1

2 2

1 1

2

1

ξ ξ

ξ ξ

ξ

= =

= =

= +

− = −

= −

= −

=

∑ ∑

∑ ∑

∑

p p

pm

i i i ii i

pm

i ii i

m

ii p

x s x s

e e

.

Jika residu ini diabaikan maka sp bisa

diterima sebagai aproksimasi untuk x. Kemudian, akan ditentukan berapa banyak term yang dibutuhan jika x adalah salah satu dari Xk. Perhatikan bahwa,

2 2

1

1

1

, ,

ξ= +

= +

= +

− =

=

=

∑

∑

∑

m

p ii p

m

i ii p

mH Hi i

i p

x s

x e x e

e xx e

Jika diambil x = Xk dan menjumlahkan

semua atas k serta dari kenyataan bahwa λ=i i iQe e atau λ λ= =H H

i i i i i ie Qe e e , diperoleh

2

1 1 1

1 1

1 1

( )

.λ

= = = +

= + =

= + = +

− =

⎛ ⎞= ⎜ ⎟

⎝ ⎠

= =

∑ ∑ ∑

∑ ∑

∑ ∑

n n mH H

k p k i k k ik k i p

m nH Hi k k i

i p k

m mHi i i

i p i p

X s X e X X e

e X X e

e Qe

Sehingga untuk merepresentasikan x dalam himpunan { } 1=

nk k

X , cukup dengan memilih

p sedemikian sehingga 1 1

/λ λ= + =∑ ∑

m m

i ii p i

kecil.

Selanjutnya, proyeksi suatu vektor x dapat dihitung dengan memotong ekspansi principal components-nya

1 1

1 1

,= =

= =

⎡ ⎤ ⎡ ⎤= ⎣ ⎦ ⎣ ⎦

∑ ∑p p

Hp i i i i

i iH

p p

s x e e e e x

e e e e x

Karena dengan mengambil nilai p seperti

di atas dapat diterima, berarti sub ruang span{ } 1=

pk k

e memuat sebagian besar informasi sebenarnya.

IX. Langkah Pemampatan Citra

Langkah-langkah pemampatan citra dengan menerapkan proses yang telah diuraikan sebelumnya adalah sebagai berikut: 1. Ambil sebuah citra, berupa file. 2. Temukan principal component basis dengan

mendekomposisikan matriks citra tersebut ke dalam SVD, principal component basis adalah left-singular vector matriks tersebut.

3. Gunakan (*) dengan p = 1, 2, . . . untuk menyusun citra yang baru.

Hal ini menunjukkan bagaimana sub ruang span{ } 1=

pk k

e menangkap gambaran utama dari citra asli (original object).

Sebuah citra bitmap dapat ditangkap ke dalam suatu incidence matrix P, dimana pij = 1 jika pixel bernilai 1 dan 0 untuk yang lain. Setiap kolom Pk dapat dianggap sebagai satu vektor data, yaitu Xk = Pk sehingga X = P. Misalkan SVD dari P adalah P = USVH, sehingga principal component basis-nya tak lain adalah ek = Uk. Proyeksi setiap vektor data Pk pada span{ } 1=

pk k

e diperoleh menggunakan (*), menjadi

1 2 1 2⎡ ⎤ ⎡ ⎤= ⎣ ⎦ ⎣ ⎦H

p p p pP U U U U U U P

Kemudian menyusun citranya kembali

1 2

1 2 1 2

⎡ ⎤= ⎣ ⎦

⎡ ⎤ ⎡ ⎤= ⎣ ⎦ ⎣ ⎦

p

H

p p

P P P P

U U U U U U P

Dari (**), secara umum dapat diturunkan langkah-langkah pemampatan citra sebagai berikut:

Algoritma 1. 1. Ambil sebuah citra, misalkan P. 2. Tentukan dekomposisi nilai singular dari P,

misalkan P = USVH. 3. Susun kembali citra yang baru menggunakan

(**) dengan parameter p. Perhatikan bahwa dari (**), diperoleh

1

1 2

21 2 1

1( ) ( )σσ = =

⎡ ⎤= ⎣ ⎦

⎡ ⎤⎣ ⎦ i

p

H p np i i

i

P U U U

V V V diag diag

Tetapi, karena pada saat menyusun citra

yang baru disertakan parameter p, dimana parameter ini juga bersesuaian dengan banyaknya nilai singular yang disertakan. Artinya, dalam penyusunan citra yang baru hanya disertakan sebanyak p nilai singular. Dari sini diperoleh

1

1

1 2

21 2 1

1 2 1 2

1( ) ( )

( )

σσ

σ

=

=

=

⎡ ⎤= ⎣ ⎦

⎡ ⎤⎣ ⎦

⎡ ⎤ ⎡ ⎤= ⎣ ⎦ ⎣ ⎦=

i

i

p

H p pp i i

iHp

p i p

H

P U U U

V V V diag diag

U U U diag V V V

USV dengan

1

1 2

1 2

;

( ) ;

.

σ=

⎡ ⎤= ⎣ ⎦=

⎡ ⎤= ⎣ ⎦

i

p

pi

p

U U U U

S diag

V V V V

Dengan demikian, diperoleh langkah lain

untuk memampatkan citra sebagai berikut:

Algoritma 2. 1. Ambil sebuah citra, misalkan P 2. Dekomposisikan P ke dalam SVD, misalkan

SVD dari P adalah P = USVH 3. Susun kembali citra baru menggunakan (***)

dengan parameter p. Dari Algoritma 1 dan Algoritma 2,

langkah penyelesaian permasalahan ini adalah dengan mendekomposisikan suatu matriks yang kolom-kolomnya merupakan vektor-vektor data yang akan dicari pendekatannya ke dalam SVD.

(*)

(**)

(***)

Tetapi, pada rekonstruksi vektor-vektor pendekatan ini tidak menyertakan semua nilai singular, hanya sebanyak p nilai singular terbesar saja yang disertakan.

X. Implementasi

Sebuah citra A yang berukuran p x q pixel dengan SVD dari A adalah A = USVH, artinya U berkuran m x m, S berukuran m x n, dan V berukuran n x n. Pada citra hasil pemampatan dengan r nilai singular terbesar, citra tersebut dibangun sebagai jumlahan sebanyak r suku dimana masing-masing suku merupakan hasil perkalian antara satu kolom dari U dengan satu baris dari V yang telah dikalikan dengan nilai singular yang bersesuaian dengan kolom dan baris tersebut. Secara matematis diberikan sebagai berikut. Misalkan citra hasil pemampatan direkonstruksi dengan hanya 2 nilai singular, yaitu

1σ dan 2σ . Nilai singular ini bersesuaian dengan s11 dan s22. Dari sini, suku pertama adalah

1 1 1 1σ=A U v ,

dengan U1 adalah kolom ke-1 dari U, jadi U1 berukuran m x 1 dan V1 adalah baris ke-1 dari V, jadi V1 berukuran 1 x n. Dari sini, A1 berukuran m x n. Jika A2 adalah suku yang diperoleh dengan cara yang sama seperti A1, maka A2 juga berukuran m x n. Sehingga jika A1 dan A2 dijumlahkan diperoleh matriks berukuran m x n yang tak lain merupakan citra hasil pemampatan tersebut.

Telah disebutkan bahwa tujuan SVD adalah memfaktorkan matriks A ke USVH. Matriks U berisi left-singular vector, matriks V berisi right-singular vector, dan S berisi nilai singular. Nilai singular ini disusun pada diagonal utama dengan urutan σ1 ≥ σ2 ≥ ... ≥ σr > σr+1 = . . . = σp = 0. Tujuan memfaktorkan matriks A ke USVH adalah untuk mencari pendekatan bagi matriks A yang berukuran m x n dengan menggunakan entri yang jauh lebih sedikit dari pada matriks asli. Hal ini diperoleh dengan menghilangkan informasi yang berlebih, yaitu kolom-kolom yang tidak bebas linear dari A jika r < m atau r < n.

Jika A adalah matriks berukuran m x n maka r(A) = r adalah banyaknya kolom atau baris yang bebas linear. Nilai r ini bersesuaian dengan banyaknya nilai singular tak nol dari A. Sehingga, jika nilai singular yang disertakan melebihi r maka yang terjadi adalah pemborosan atau redudancy.

Perhatikan bahwa, jika SVD dari A adalah A = USVH, diperoleh

A = σ1U1V1H + σ2U2V2

H+ ... + σrUrVrH + 0Ur+1Vr+1

H + 0 + ...

Karena nilai singular selalu lebih besar

dari nol, menambahkan suku yang tidak independen yang nilai singularnya sama dengan nol tidak akan berpengaruh pada citra A. Dari sini, diperoleh

A = σ1U1V1

H + σ2U2V2H + ... + σrUrVr

H Pendekatan selanjutnya adalah dengan

mengambil sebanyak kurang dari r nilai singular saja. Karena nilai singular pada S disusun dengan urutan dari yang terbesar ke yang terkecil (decreasing order), suku-suku di belakang atau terakhir hanya memiliki pengaruh yang sangat kecil bagi keseluruhan citra A. Dengan mengabaikan nilai-nilai singular ini (sangat kecil bahkan dekat ke nol) tentunya akan mengurangi jumlah ruang yang diperlukan untuk menyimpan citra ini ke dalam komputer atau storage device.

Citra di bawah ini berukuran 256 x 256 pixel. Citra ini tak lain merupakan matriks berukuran 256 x 256 dengan entri berupa bilangan bulat 8-bit (nilai diantara 0 – 255). Sehingga ukuran file yang dibutuhkan untuk menyimpan citra ini adalah 256 x 256 = 65536 byte atau 65536/1024 = 64 kilo byte (KB).

Gambar 3. lena.bmp

Sebut matriks yang merepresentasikan

citra tersebut adalah M, dan dekomposisi nilai singular dari M adalah

M = USVH

Sehingga dari dekomposisi ini, diperoleh

tiga buah matriks U, S, dan V yang semuanya berukuran 256 x 256. Matriks S adalah diagonal dengan entri pada tiap diagonalnya merupakan nilai singular dari matriks M.

Enam puluh lima nilai singular pertama dari matriks atau citra di atas adalah sebagai berikut (semuanya berjumlah 254):

Tabel 1. Nilai singular citra lena.bmp

k σ k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

3,2356 x 104 5,2895 x 103 4,0840 x 103 3,2420 x 103 2,9472 x 103 2,7868 x 103 2,2875 x 103 2,0475 x 103 1,6869 x 103 1,5896 x 103 1,3384 x 103 1,2214 x 103 1,2067 x 103 1,1560 x 103 1,0906 x 103 1,0830 x 103 1,0427 x 103 926,6837 861,8731 847,6364 815,1662 800,1618 729,2711 673,4731 658,3523 652,1497 618,1443 608,0146 577,7306 555,6676 541,9216 527,5845 521,0986 507,8607 502,2631 498,7934 471,2519 464,3750 462,3591 450,1892 431,7701 426,0162 417,1466 406,0570 402,8205 389,3284 379,5878 370,0344 365,5331 357,9349 354,0090 340,3797 336,2773

Gambar berikut adalah hasil rekonstruksi dengan menyertakan nilai singular terbesar.

Gambar 4. Citra dengan

nilai singular terbesar Terlihat, hasil di atas belum cukup untuk

merepresentasikan citra asli dengan baik. Tetapi, citra di atas hanya membutuhkan 256+1+256 = 513 byte. Kemudian dilakukan rekonstruksi dengan 5 nilai singular pertama, hasilnya adalah sebagai berikut:

Gambar 5. Citra dengan 5 nilai singular terbesar

Citra di atas hanya membutuhkan 256x5

+ 5 + 256x5 = 2565 byte. Sekarang, dicoba untuk 10 nilai singular terbesar, sehingga hanya membutuhkan (256 + 1 + 256)x10 = 5130 byte atau hanya sebesar 7,83% dari citra asli. Hasilnya sebagai berikut:

Gambar 6. Citra dengan 10 nilai singular terbesar

Berikut ini hasil yang diperoleh untuk 20,

30, 40, dan 50 nilai singular.

Gambar 7. Hasil pemampatan

dengan 20, 30, 40, dan 50 nilai singular Terlihat, pada hasil pemampatan dengan

50 nilai singular sudah cukup merepresentasikan citra asli dengan ukuran file (256 + 1 + 256)x50 = 25650 byte, atau hanya 39% dari yang dibutuhkan oleh citra asli. Pada tabel, untuk nilai singular ke-51 dan seterusnya sudah lebih kecil sehingga cukup dengan mengambil 50 nilai singular saja.

XI. Kesimpulan

Dalam pemampatan data, SVD digunakan untuk mencari vektor-vektor pendekatan yang disebut dengan principal component basis, dan vektor-vektor ini menempati arah yang paling tepat dengan vektor-vektor data tersebut. Jika vektor-vektor data tersebut direpresentasikan ke dalam kolom-kolom matriks, misalkan A, dan SVD dari A adalah A = USVH maka principal component basis yang dicari adalah left-singular vector dari A, yaitu Uk. Jadi, SVD digunakan untuk mendapatkan principal component basis dari suatu kumpulan vektor-vektor data.

Dengan menggunakan Algoritma 2, sebuah citra A yang berukuran p x q pixel dengan SVD dari A adalah A = USVH, artinya U berkuran m x m, S berukuran m x n, dan V berukuran n x n. Pada citra hasil pemampatan dengan k nilai singular terbesar, citra tersebut dibangun sebagai jumlahan sebanyak k suku dimana masing-masing suku merupakan hasil perkalian antara satu kolom dari U dengan satu baris dari V yang telah dikalikan dengan nilai singular yang bersesuaian dengan kolom dan baris tersebut. Nilai singular dalam terminologi ini berperan sebagai faktor skala.

XII. Referensi

1. Drakos, N., 1997, Data Compression with The Singular Value Decomposition, University of Leeds, England, http://sepwww.stanford.edu/public/docs/sep73/ray1/paper_html/node3.html

2. Echegaray, S., 2000, Image Compression with Singular Value Decomposition, http://peter.wreck.org/reports/Math4305/

3. Sandberg, K., 2000, The Singular Value Decomposition of an Image, Dept. of Applied Mathematics University of Colorado at Boulder, Boulder, http://amath.colorado.edu/courses/4720/2000Spr/Labs/SVD/svd.html

4. Scheick, J.T., 1997, Linear Algebra with Applications, International Edition, Mc-Graw-Hill, Inc., Singapore.

5. Wall, M.E., Rechtsteiner, A., Rocha, L.M., 2003, Singular Value Decomposition and Principal Component Analysis, Los Alamos National Laboratory, Los Alamos, http://public.lanl.gov/mewall/kluwer2002.html.