PENDEKATAN ALJABAR LINEAR UNTUK KOMPRESI DATA DENGAN WAVELET Agus Sukmana" Abstract In the last twenty years, wavelet theory has rapidly developed. One of its applications is in data compression. Most of data compression with wavelet use wavelet thresholding techniques, which aim to eliminate insignificant or redundant signal components and only store relevant signals. In general, wavelet analysis is performed through Fourier analysis; however in this paper the analysis is performed using linear algebra approach which has been introduced in mathematics courses in most of computer science departments.
1.PENDAHULUAN Teori wavelet mengalami perkembangan yang sangat pesat dalam 20 tahun terakhir, di tahun 80-an Y.Meyer, I.Daubechies, S Mallat dkk mengembangkannya meskipun sebetulnya tahun 1909 A. Haar telah membahas wavelet pada tesisnya. Penggunaan wavelet untuk kompresi data dikenal luas di berbagai bidang, sebagai contoh kompresi data: sidik jari di FBI [1], deret waktu {time series) dalam jumlah besar [10], industri proses secara on-line [6], radiographic image dari komponen pesawat terbang [9], dan reduksi data nonstasioner berbentuk kurva yang sangat kompleks [4]. Teknik kompresi data dengan wavelet pada umumnya dilakukan dengan menghilangkan komponen sinyal yang tidak berarti {insignificant) dan berlebih {redundant), dan hanya menyimpan sinyal-sinyal yang relevan. Teori wavelet telah dibahas pada banyak buku, antara lain oleh [8] dan [11], Sebagian besar pembahasan teori wavelet dilakukan melalui pendekatan analisis Fourier, karena analisis wavelet dapat dipandang sebagai analisis Fourier dengan basis berupa fungsi yang bersifat compact support. Sedangkan Fourier menggunakan basis sinus dan cosinus yang tidak compact support. Pengantar tentang analisis Fourier jarang diberikan pada kurikulum mata kuliah matematika untuk program studi llmu komputer. Tulisan ini bertujuan membahas kompresi data dengan wavelet Haar melalui pendekatan aljabar linear dan matriks yang dipelajari pada mata kuliah matematika dasar.
2. KONSTRUKSI WAVELET HAAR Pada bagian ini dibahas bagaimana mengkonstruksi basis wavelet, dan bagaimana menyatakan suatu fungsi konstan bagian-demi-bagian {piecewise constant functions) dalam basis wavelet. Wavelet Haar dipilih karena sederhana sehingga relatif mudah menjelaskannya.
Dosen tetap Jurusan Matematika, Universitas Katolik Parahyangan, Bandung, e-mail:
[email protected].
Pendekatan Aljabar Linear... (A. Sukmana)
185
Fungsi skala atau father wavelet adalah sebuah fungsi konstan yang didefinisikan sebagai berikut:
fl 0<x
{x) = { [0 yang lainnya
(1)
Kemudian perhatikan sebuah himpunan V° yang berisi fungsi-fungsi konstan yang terdefinisi pada selang [0,1) dan memenuhi syarat sebagai ruang vektor [3, him 51] dengan basis {^(.v)}. Ini berarti setiap fungsi konstan di ruang vektor F" dapat dituliskan sebagai kelipatan dari fungsi Misalkan ruang vektor V
yang berisi fungsi konstan bagian-demi-bagian
terdefinisi pada dua selang [0, \ ) dan [\ ,1), dengan basis { ^ ( x ) , 0l(x)}
.
[1
0<x < \
«*d(*Hn (0 dan
[1 $(x) = \ (0
yang
di mana:
(2a)
,• " yang lainnya l <x <1
(2b)
yang lainnya
Proses dilanjutkan dengan membagi selang [0,1) kedalam 2' selang yang sama panjang, Secara umum basis ruang vektor diperoleh dari rumus :
j{x) = <j>{2'x-i), Sebagai
contoh,
2
2
ruang
{^ 0 (x),^, (x),^ 2 (x),^(x)}
berupa 2' buah fungsi yang
i=0,1,...,2'-\. vektor
2
I"
di
V2
mana
(3) memiliki
2:=
4
fungsi
^ ( . Y ) = (4x - \) = <j)(4[x - } ) )
yaitu yang
berarti bahwa fungsi father wavelet (/>(x) ditranslasi kearah kanan sejauh \ dan diperkecil (dilatasi) menjadi 2
}{x).,(/): (x),(j) (x) diperkecil
j
ukuran semula. Demikian pula untuk fungsi
berturut-turut digeser ke kanan sejauh j - ,
~, 1 kemudian
~ ukuran semula. Hasilnya dapat dilihat pada gambar 1 untuk j=1 dan
7=2. Basis untuk ruang vektor V' saling ortogonal , memenuhi hasil kali dalam [3, him 276]:
(:(x\
i(x))=\j;(x)tt(x)dx l!y' II
2' 0
186
/* k
Jurnal llmiah llmu Komputer, Vol. 4 No. 3 September 2006: 185-196
1
I
•JG
1 1
T
Li
U
• 1
Uh
I. b
i
j=0
4
U |
II
-
1
•
11?
1
•h
Ufl
'i
=1
— I!-J
0 B
0-
r...
OJ
04
n • J
,i
a:
G4
06
08
U j
i
U i
l> 6
U 4
(J 6
OB
1
OB-
0B
OE
US
04
o;
:j ?
(,i.;
n t
at
uh
3
i
[il'
a t)
1
y=2 Gambar 1. Basis untuk ruang vektor
Pendekatan Aljabar Linear.. (A. Sukmana)
//" J/'
^ 187
Bila kita ambil sebarang fungsi
y0 di V°, ternyata dapat dituliskan sebagai
kombinasi linear dari basis {$J(x), \{x)}:
yo=a[0l(x)+$(x)] sehingga y0 e Vs, atau F° c: F 1 . Bila diperumum berlaku:
K" c F ' c F 2 c ...
(5)
Menurut teorema [5, hal 229], terdapat ruang vektor
W
yang merupakan
+ l
komplemen ortogonal dari V' pada ruang vektor V ' , dan berlaku:
VJ+] =VJ ®Wj
(6)
Fungsi konstan bagian-demi-bagian berikut disebut mother wavelet: i//(x) =
0
0<x<{ \<x<\ yang lainnya
(7)
Basis untuk ruang vektor W ' didefinisikan sebagai berikut:
i//l'(x) =
i = 0,1,...,2'-1
(8)
selanjutnya disebut wavelet Haar: Penjelasan penggunaan rumus (8) sama dengan rumus (3) tetapi dengan menggunakan fungsi mother wavelet (7). Hasilnya dapat dilihat pada Gambar 2 untuk j = 0, 1 dan 2.
0 5-
0-
)
02
04
06
0B
•0 5
I
j=0
188
Jurnal llrmiah llmu Komputer, Vol. 4 No. 3 September 2006: 185-196
r
r
0 5-
05
0 1
112
06
fid
am
i
•i
r. ?
04
f.lF
an
D5
05
• l
• 1
j=1 1:
0 5-
05
a 1
o:
0 4
06
08
0
1
-0 5
a:
u
06
a,B
0 2
L14
06
OS
i
05
-1.
• 1 .
t:
['•
05
0 5-
P-
<3
130 L'
04
01
08
1
'
-0 5-
-0 5-
.1:
• 1
y = 2 Gambar 2. Basis untuk ruang vektor
yang disebut wavelet Haar.
Perhatikan ruang vektor f^dengan basis terurut S = {$,$,...,$]. vektor tersebut dituliskan dalam bentuk: V' =V~(BW2 menjadi T2 =\$,$,l,$,y/l,y/*,y/l,y/l\. Pendekatan Aljabar Linear... (A. Sukmana)
Bila ruang
maka basis terurutnya
Ruang vektor V3 dapat pula ditulis
189
V2, = V' © W' © W2
dengan basis terurut 7[ = j$J, \, y/\, (//,', i//n2, t//2, y/22, i//2)
^ 3 = V° © ^ " © Jf' © W2
dan
2
2
2
T0 =l0Q,i//f),i//(),i//l,i/s ),i// j//j,y/ \.
dengan
basis
terurut
Dapat disimpulkan bahwa setiap fungsi di
V' dapat dinyatakan sebagai kombinasi linear basis S, 7,, 7], 7J, tergantung pada resolusi mana fungsi tersebut akan diuraikan. Untuk uraian dengan resolusi tinggi gunakan basis T0. Langkah-langkah yang telah dibahas di atas disebut Analisis Multi Resolusi dari Mallat. Secara umum : H H
v> = v © w
yJ =V'-2 @Wh2 ®WH V
V,®Wi®...®W'~2®WH
=
V = V" ©W° ©Wx
®...®W'~2®WH
3. TRANSFORMASI WAVELET Sebagai ilustrasi misalkan terdapat fungsi konstan bagian-demi-bagian / d i V2, ditulis:
/' = <j)^ - \ $ + 2\ + $ - 2(/>l + 3^j - l + yJ,- <j>] dalam bentuk koordinat
terhadap basis terurut S adalah:
71=0 - 1 2 1 - 2 3 - 1 4) J
2-
1
1-
1)
0.2
DE
0 4
OB
1
< 1
?
Gambar 3. Grafik fungsi konstan bagian-demi-bagian /
Bila
/
ingin dinyatakan dalam basis ortonormal
di V'
T* (diperoleh dengan cara
membagi setiap vektor di T2 dengan panjangnya) maka diperlukan matriks transisi R. 190
yang akan mentransformasikan
[/']..
kedalam [ / ] , . .
Matriks transisi
Jurnal llmiah llmu Komputer, Vol. 4 No. 3 September 2006: 185-196
diperoleh dengan menggunakan rumus:
V.s = [til* W \ - $ L
(9)
Sebagai ilustrasi untuk memperoleh kolom pertama dari matriks transisi
R,
tuliskan vektor fy sebagai kombinasi linear basis ortonormal T2 : "0
]
0*o . + o <*' + . i
A" II
J.2
II
|| /2|i
V 2 p{) ||
||^ ||
/T
y/
II
'/', + 0. VT - + ... + 0.
"
V2 ||y/(l J
||(//, J
|y/3 J
Sehingga koordinat ^J terhadap basis ortonormal T2* dapat dinyatakan dalam bentuk vektor kolom : 72
0 0
M, -
0 I
72
0 0
Bila proses dilanjutkan untuk kolom 2 sampai dengan kolom 8 maka diperoleh matriks transisi yang ortogonal sebagai berikut:
/?...
1
I
72
7:
0
0
1
0
0
0
0
0
0
0
1
i
72
72
0
0
0
0
0
0
0
1
0
0
0
0
0
0
72
1
1
72
V2
0
0
0
72
Ji
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
72
1
1
72
72
0
0
Koordinat /' terhadap basis T dihitung dengan [f]r [/]';• = ( 4
*#
4
-0,42426...
Pendekatan Aljabar Linear... (A. Sukmana)
i f
f
1
1
72
= RT4_S [f]s
- i f
7
:
-0,9899...)
191
Dengan menggunakan cara yang serupa dengan proses mencari R,
, diperoleh
Matriks transisi dari basis ortonormal T* ke dalam basis ortonormal 7J* adalah : 0
0
0
0
0"
0
0
-J-
77
jj
u
0
0
0
0
0
(I
jl 0
•4r
0
0
0
0
0
(I
0
0
1 0
0
0
0
0
0
0
0
1 0
(I
0
0
0
0
0
1 0
0
0
0
0
0
0
0
I
0 0 0 0
0
1
Koordinat f terhadap basis T adalah [/]';, =(l.75
0.2
-1,25
0.8
&
4-
-*&
-0.9899...)
Matriks transisi dan basis ortonormal Tx kedalam basis ortonormal T' : L v'2
I
0
v'j
I
Ji
Jl
(I
0
0 0
0
0
0 0
0 0
0
0
(I
0 0 0 0"
0 0 0 0 0 0 I 0 0 0 0 0 0 I 0 0 0 0 0 0 I 0 0 0 0 0 (I 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1
Koordinat / terhadap basis T adalah: [ / ] - , • = (1.3788.. 1.0960... -1.25 0.8
1,0606... 0.7071... -3.5355... -0,9899...)
Sehingga sekarang kita telah mendapatkan 3 cara untuk menuliskan koordinat fungsi /
ke dalam basis wavelet dalam berbagai tingkat resolusi.
4. KOMPRESI DATA 2 DIMENSI Misalkan terdapat matriks P ukuran nxn dengan « = 2' , J bilangan bulat positif. Matriks P ini dapat berupa matriks pixel dari suatu gambar (image). Pada makalah ini akan dibahas bentuk data telah berupa matriks P. Sebagai ilustrasi diambil kasus pada J=3. Bila kita ingin mentransformasikan baris-baris dari matriks P dalam basis 192
Jurnal llmiah llmu Komputer, Vol. 4 No. 3 September 2006: 185-196
V,r
Q
V*
A'
7, t - \
/"
(10)
Untuk menyederhanakan penulisan kita misalkan:
R.
r„ <-/;
= /?,,
V*
*,.
^;V.v
= R„
sehingga persamaan (10) menjadi: (11) Kemudian untuk kolom-kolomnya dilakukan transformasi terhadap matriks O', sehingga diperoleh:
C = [(JR()R,R2] C disebut matriks yang telah dikompresi, Ra,RrR2
(12) disebut matriks filter. Untuk
kembali mendapatkan matriks P dilakukan proses yang disebut dekompresi data sebagai berikut: Tuliskan /?„/?,/?, = W , sehingga matriks (12) menjadi lebih sederhana:
c = (PW)'wl =[W P'W~J =[W PW~\
(13)
dan matriks P dapat kembali diperoleh dari:
p = [W'i}cw-]
(14)
Karena dipilih matriks filter R yang ortogonal sehingga invers W dan W relatif mudah dicari yaitu :
W] =[R0RAV = R?R;]R»] -R^K
d5)
Prinsip dari kompresi data dengan wavelet disamping mentransformasikan data kedalam berbagai basis wavelet, juga berusaha mengeliminasi data yang tidak berarti atau berlebih. Dalam wavelet, informasi tersebut dinyatakan oleh nilai mutlak koefisien wavelet yang kecil. Metoda untuk memilah-milah koefisien mana yang kecil dan dijadikan nol disebut metoda thresholding. Berbagai metoda telah dibahas antara lain pada makalah-makalah yang ditulis Donoho antara lain [2] dengan berbagai kriteria optimasi, tetapi pada makalah ini ambang-batas (threshold) akan ditetapkan secara subyektif. Akibat penggunaan metoda thresholding, ketika matriks C didekompresi tidak mungkin dapat kembali kebentuk P tetapi cukup mendekati. Dalam praktek seringkali menguntungkan karena yang terbuang adalah sinyal-sinyal yang berbentuk gangguan (noise) sehingga meskipun hasil dekompresi tidak sama dengan data aslinya tetapi sebagian besar noisenya telah terbuang. Sebagai ilustrasi bagaimana sistem ini bekerja, kita bahas contoh berikut: Misalkan diketahui matriks P berukuran 8x8 :
Pendekatan Aljabar Linear... (A. Sukmana)
193
Sebagai ilustrasi bagaimana sistem ini bekerja, kita bahas contoh berikut: Misalkan diketahui matriks P berukuran 8x8 : 20 50 28 19 12 61 10 10
P=
10
[0
10
10
10
14
10
10
10
-13
5
14
10
10
11
6
15
17
13
12
45
9
11
10
10
10
10
20
10
40
50
60
13
20
15
17
10
32
10
10
10 -10 20 14
14
32
23
41
10
30
15
IX
10
10
10
7
Matriks kompresi dari P adalah:
C =
535 1
-S3 2
357I
-14
87 1
109V2 8
13 7 2 8
-9
-1972 8
17372
9_
8
1
59-72 8
19 2
Jl 1
-51V2
1771
4
4
4372 8
-10972 8
19 4
-15
1372 4
63 2
7
23 72 4
4971
-15
-79 4
-3
-2972 4
-15
i
103 4
-(.9 4
-4372 4
#
8
-8V2
4
7i
25 2
•25
7_
73
1"
4J2^ 77
10
-23 4
-59 1
-11
25. 1
14
8972 4
-3
72
-II
-7
72
72
-45
0
-5
-18
2
-15
-14
-1
-13
-y/2 2
Matriks C memuat lebih banyak nol dan lebih banyak nilai yang "kecil" dibandingkan dengan matriks P, nilai yang kecil ini akan dibuat menjadi nol sehingga matriks semakin banyak memuat unsur nol. Pilih nilai ambang-batas s > 0 , dan semua unsur dari matriks C yang berniiai lebih kecil atau sama dengan e diubah menjadi nol. Prosedur sederhana ini disebut ambang-batas-seragam (uniform thresholding). Perbandingan (rasio) banyaknya unsur tak nol pada matriks C dengan matriks P disebut rasio kompresi. Pada contoh di atas rasio kompresinya adalah % = 98,4375%, dan prosedur thresholding dapat menurunkan rasio kompresi. Sebagai contoh bila dipilih £ = 5maka rasio kompresi menjadi 4%4 = 76,5625% . Penerapan prosedur thresholding terhadap matriks C menghasilkan matriks C* sebagai berikut:
194
Jurnal llmiah llmu Komputer, Vol. 4 No. 3 September 2006: 185-196
5.15 4
-14 109 V 2 8
.5 1 87
1 59-v/i X
-109 7:
0
7.W2 X
11
0
-15
2.WI
49^2 4
8
X
2
7
-79 I
0
-29^2 4
-15
10? 4
-(.9 4
-4.1v 2 1
4*
,* (
-l>
35V3 K
4
4
0
-2.1 4
is
-.Mv'2 4
I7V2 4
4
0 4
0
-15
14
0
0
2
0
0
-18
0
0
-15
14
6
10
0
-13
-9
V2
72
-8V2
27
4f
dan apabila dilakukan dekompresi dengan P* = [W] hampiran matriks sebagai berikut: 19.469
51.719
9.4688
11.719
' C W ' akan menghasilkan
25.156
20.656
11.594 60.594 11.156 9.6562
11.656 9.6562 -11.094 4.5938 14.281 18.531 12.219
7.1562 13.594 11.219
9.5938 13.594 11.156 9.6562 9.4062 9.4062 9.4688 7.9688
10.469
12.281
21.281
7.8438
9.5938 39.594 52.156 58.656 12.281 -8.7188 14.594 16.594 12.156 30.656 19.406 13.406 13.594 3 1.594 21.656 43.156
27.844
13.406
7.4062
5.9688 12.469 13.344 13.344
16.969
44.781 8.7812
11.844
17.594 9.5938 8.6562
10.344
12.156
Alternatif prosedur thresholding selain uniform thresholding adalah selective thresholding, di mana prosedur thresholding dilakukan tidak sekaligus pada seluruh koefisien wavelet tetapi dilakukan perblok sesuai dengan tingkat resolusinya. Prosedur ini sedikit dibahas pada [7,him 170-171].
5. PENUTUP Telah dipaparkan bagaimana dengan menggunakan Ajabar Linear Elementer (pada umumnya telah diberikan pada mata kuliah Matematika, setidaknya pengalaman penulis mengajar matakuliah AMA-211 Aljabar Linear dan Matriks di Progran Studi llmu Komputer Unpar) kita dapat mengkonstrusksi basis wavelet Haar tanpa melalui pendekatan analisis Fourier, kemudian menggunakan metoda perubahan basis untuk menyatakan fungsi yang sama tetapi dalam tingkat resolusi yang berbeda, pemahaman operasi matriks dan sifat matriks ortogonal membantu proses kompresi dan dekompresi data berbentuk matriks. Semoga tulisan ini dapat menjadi salah satu contoh untuk menunjukkan relevansi mata kuliah Matematika dengan topik dalam llmu Komputer yang sering ditanyakan oleh mahasiswa peserta kuliah Matematika. Pendekatan Aljabar Linear... (A Sukmana)
195
DAFTAR PUSTAKA [I] Brislawn, Christopher M.; Fingerprints Go Digital, Notices of the American Mathematical Society, 42, 7:1278-1282, 1995. [2] Donoho,David et al.; Density Estimation by Wavelet Thresholding, The Annals of Statistics, 24, 2:508-539, 1996 [3] Howard, Anton; Elementary Linear Algebra, 8th edition, John Wiley & Sons, New York, 2000. [4] Jeong, Myong K. et al; Wavelet-Based Data Reduction Techniques for Process Fault Detection, Technometrics, 48, 1:26-40, 2006. [5] Kolman, Bernard and Hill, David R.; Elementary Linear Algebra, 7th edition, Prentice-hall, New Jersey, 2000. [6] Misra.Manish, et.al ; On-line Data Compression and Error Analysis Using Wavelet Technology, American Institute of Chemical Engineers AichE Journal,46,VA 19-132, 2000. [7] Mihalia, loana and Sansgiry, Prashan S.; Introducing Wavelets and Image Compression as Applications in A Linear Algebra Class-Part II, Mathematics and Computer Educations, 36, 2:167-175, 2002. [8] Nievergelt, Yves; Wavelets Made Easy, Birkhaiiser, 1999. [9] Shark, L.K. et al; Lossless Compression of Radiographic Images of aircraft Components, Aircraft Engineering and Aerospace Technology,75,A.358-364, 2003. [10] Sukmana, Agus; Wavelet Shrinkage for Modeling Time Series Data: a Data Compression Method, Theses, University of Twente, Enschede, 1999. [ I I ] Walnut, David F.; An Introduction to Wavelet analysis, Birkhaiiser, 2001.
BIODATA PENULIS Agus Sukmana, MSc in Engineering Mathematics dari University of Twente, Belanda, Bidang Statistics and Operations Research, Lektor pada Jurusan Matematika Universitas Katolik Parahyangan, Research Interest: Risk Theory, Inventory Models, Wavelets Applications in Time Series Anaysis, Statistical Quality Control. E-mail:[email protected], http://home.unpar.ac.id/~asukmana.
196
Jurnal llmiah llmu Komputer, Vol. 4 No. 3 September 2006: 185-196
