REPRES ENTAS I S INYAL D ENGAN KAMUS BAS IS LEWAT-LENGKAP
S KRIPS I
Oleh
Albert G S Harlie
1100002070
Kevin Octavio
1100002096
Ricardo S usetia
1100007626
Universitas Bina Nusantara Jakarta 2011
REPRES ENTAS I S INYAL D ENGAN KAMUS BAS IS LEWAT-LENGKAP
S KRIPS I
Diajukan sebagai salah satu syarat untuk gelar kesarjanaan pada Jurusan Sistem Komputer Jenjang Pendidikan S trata-1
Oleh
Albert G S Harlie
1100002070
Kevin Octavio
1100002096
Ricardo S usetia
1100007626
Universitas Bina Nusantara Jakarta 2011 ii
REPRES ENTAS I S INYAL D ENGAN KAMUS BAS IS LEWAT-LENGKAP
S KRIPS I
Disusun oleh:
Albert G S Harlie 1100002070
Kevin Octavio 1100002096
Disetujui oleh: Pembimbing
Endra S .Kom.,MT Pembimbing (D2395)
Universitas Bina Nusantara Jakarta 2011 iii
Ricardo S usetia 1100007626
PERNYATAAN Dengan ini kami, Nama
: Albert Gunawan Santosa Harlie
NIM
: 1100002070
Nama
: Kevin Octavio
NIM
: 1100002096
Nama
: Ricardo Susetia
NIM
: 1100007626
Judul skripsi : Representasi Sinyal dengan Kamus Basis Lewat-Lengkap
M emberikan kepada Universitas Bina Nusantara hak non-eksklusif untuk menyimpan, memperbanyak, dan menyebarluaskan skripsi karya kami, secara keseluruhan atau hanya sebagian atau hanya ringkasannya saja, dalam bentuk format tercetak dan atau elektronik.
M enyatakan bahwa kami, akan mempertahankan hak exclusive kami, untuk menggunakan seluruh atau sebagian isi skripsi kami, guna pengembangan karya di masa depan, misalnya bentuk artikel, buku, perangkat lunak, ataupun sistem informasi.
Jakarta, 08 M aret 2011
Albert G S Harlie
Kevin Octavio
iv
Ricardo Susetia
PRAKATA
Puji syukur ke hadirat Tuhan Yang M aha Esa, sehingga penulis dapat menyelesaikan skripsi dengan judul “Representasi Sinyal dengan Kamus Basis LewatLengkap” sebagai salah satu syarat untuk mencapai gelar kesarjanaan pada Jurusan Sistem Komputer Fakultas Ilmu Komputer Universitas Bina Nusantara. Penulisan skripsi ini tidak lepas dari dukungan bantuan dan bimbingan berbagai pihak. Dalam kesempatan ini penulis mengucapkan terima kasih dan penghargaan yang sebesarbesarnya kepada: 1. Kedua Orang Tua beserta seluruh keluarga penulis yang telah banyak memberikan dorongan semangat, motivasi, materi, dan doa kepada penulis dalam menyusun skripsi ini. 2. Bapak Endra,S.Kom.,M T selaku dosen pembimbing yang telah banyak memberi bimbingan, dukungan, dan semangat hingga terselesaikannya skripsi ini. 3. Bapak Robby Saleh,S.Kom.,M T selaku Sekretaris Jurusan Sistem Komputer yang telah memberikan kontribusi dalam penyusunan skripsi ini. 4. Bapak Rudy Susanto, S.Kom selaku Kepala Laboratorium Perangkat Keras Sistem Komputer Universitas Bina Nusantara yang telah menyediakan waktu, fasilitas, saran, serta dorongan selama penyusunan skripsi ini. 5. Bapak Wiedjaja S.Kom M .Kom selaku Ketua Jurusan Sistem Komputer yang telah memberikan arahan dalam menyelesaikan skripsi ini. 6. Bapak Prof. Dr. Ir. Harjanto Prabowo, MM selaku Rektor Universitas Bina Nusantara dan Bapak Ir. Sablin Yusuf, M .Sc., M .Comp.Sc. selaku Dekan vi
Fakultas Ilmu Komputer yang telah memberikan kesempatan kepada penulis untuk menyusun skripsi ini. 7. Segenap Dosen dan Staff Universitas Bina Nusantara yang telah memberikan bantuan dan masukan serta dukungan selama penulis menimba ilmu di Universitas Bina Nusantara. 8. Segenap Asisten dan Staff Computer Engineering Laboratory Universitas Bina Nusantara yang telah memberikan dukungan moral, saran, dan bantuan selama pembuatan skripsi ini. 9. Seluruh teman-teman mahasiswa dan pihak yang telah membantu dan memberikan kontribusinya selama penyusunan skripsi ini. 10. Semua pihak yang tidak dapat disebutkan satu persatu secara langsung maupun tidak langsung terlibat dalam penyusunan skripsi ini sehingga skripsi ini dapat diselesaikan.
Penulis menyadari bahwa skripsi ini belum sempurna. Oleh karena itu, penulis mengharapkan kritik dan saran dari pembaca untuk menyempurnakan karya-karya yang akan datang. Besar harapan dari penulis semoga skripsi ini dapat berguna bagi siapa saja yang menggunakannya.
Jakarta, Januari 2011
Penulis vii
DAFTAR IS I
Halaman Judul Luar ...................................................................................................
i
Halaman Judul Dalam ................................................................................................
ii
Halaman Persetujuan Hard Cover .............................................................................
iii
Halaman Pemberian Hak Cipta Non Eksklusif dari M ahasiswa ke Universitas Bina Nusantara ...................................................................................................................
iv
Abstrak.......................................................................................................................
v
Prakata........................................................................................................................
vi
Daftar Isi .................................................................................................................... viii Daftar Tabel ...............................................................................................................
xi
Daftar Gambar............................................................................................................ xiii Daftar Persamaan ....................................................................................................... xvii Daftar Lampiran ......................................................................................................... xviii
BAB 1 PENDAHULUAN 1.1
Latar Belakang ......................................................................................
1
1.2
Ruang Lingkup......................................................................................
3
1.3
Tujuan dan M anfaat ..............................................................................
3
1.4
M etodologi Penelitian ...........................................................................
4
1.5
Sistematika Penulisan ...........................................................................
5
BAB 2 LANDAS AN TEORI viii
2.1
Representasi dan Sparsity .....................................................................
6
2.2
Dictionary .............................................................................................
8
2.3
2.2.1
Discrete Cosine Transform (DCT).........................................
9
2.2.2
Transformasi Wavelet ............................................................
11
Sparse Coding .......................................................................................
15
2.3.1 2.4
Orthogonal Matching Pursuit (OMP)....................................
16
Peak Signal to Noise Ratio (PSNR) ......................................................
17
BAB 3 PERUMUS AN PENELITIAN 3.1
Diagram Blok ........................................................................................
19
3.2
Diagram Alir .........................................................................................
37
3.2.1
Umum.....................................................................................
37
3.2.2
Blocking .................................................................................
42
3.2.3
De-Blocking ...........................................................................
47
3.2.4
Orthogonal Matching Pursuit (OMP)....................................
52
3.3 Tampilan User Interface ..........................................................................
55
BAB 4 DATA DAN AN ALIS IS 4.1
Spesifikasi Sistem .................................................................................
62
4.2
Implementasi.........................................................................................
62
4.2.1 Pengujian nilai PSNR dan waktu terhadap aproksimasi dengan DCT ..............................................................................
ix
64
4.2.2 Pengujian nilai PSNR dan waktu terhadap aproksimasi dengan Wavelet .........................................................................
70
4.2.3 Pengujian nilai PSNR dan waktu terhadap aproksimasi dengan Overcomplete................................................................ 4.2.4 Perbandingan nilai PSNR terhadap
76
aproksimasi untuk
berbagai citra dan dictionary.....................................................
83
4.2.5 Pengujian nilai PSNR dan waktu terhadap besar Blocking .......
98
4.2.6 Pengujian nilai PSNR dan waktu terhadap jumlah basis yang digunakan untuk membentuk overcomplete dictionary ............ 102
BAB 5 KES IMPULAN DAN S ARAN 5.1
Kesimpulan ........................................................................................... 107
5.2
Saran...................................................................................................... 108
DAFTAR PUS TAKA ............................................................................................... 109 RIWAYAT HID UP .................................................................................................. 111 LAMPIRAN LAMPIRAN
x
DAFTAR TABEL
Tabel 4.1 Hasil DCT dengan citra Lena.....................................................................
64
Tabel 4.2 Hasil DCT dengan citra Baboon ................................................................
65
Tabel 4.3 Hasil DCT dengan citra Barbara ...............................................................
66
Tabel 4.4 Hasil DCT dengan citra Peppers................................................................
67
Tabel 4.5 Hasil DCT dengan citra Cameraman .........................................................
68
Tabel 4.6 Hasil Wavelet dengan citra Lena................................................................
70
Tabel 4.7 Hasil Wavelet dengan citra Baboon ...........................................................
71
Tabel 4.8 Hasil Wavelet dengan citra Barbara ..........................................................
72
Tabel 4.9 Hasil Wavelet dengan citra Peppers ..........................................................
73
Tabel 4.10 Hasil Wavelet dengan citra Cameraman..................................................
74
Tabel 4.11 Hasil Overcomplete dengan citra Lena ....................................................
76
Tabel 4.12 Hasil Overcomplete dengan citra Baboon................................................
77
Tabel 4.13 Hasil Overcomplete dengan citra Barbara ..............................................
78
Tabel 4.14 Hasil Overcomplete dengan citra Peppers ...............................................
79
Tabel 4.15 Hasil Overcomplete dengan citra Cameraman ........................................
80
Tabel 4.16 Hasil besar blocking dengan aproksimasi 10%........................................
98
Tabel 4.17 Hasil besar blocking dengan aproksimasi 50%........................................
98
Tabel 4.18 Hasil jumlah basis dengan citra Lena ...................................................... 102 Tabel 4.19 Hasil jumlah basis dengan citra Baboon .................................................. 102 Tabel 4.20 Hasil jumlah basis dengan citra Barbara................................................. 103 Tabel 4.21 Hasil jumlah basis dengan citra Peppers ................................................. 103 xi
Tabel 4.22 Hasil jumlah basis dengan citra Cameraman........................................... 104
xii
DAFTAR GAMBAR
Gambar 2.1 (a) Citra asli berukuran 1 M egapiksel ....................................................
7
Gambar 2.1 (b) Koefisien-koefisien wavelet .............................................................
7
Gambar 2.1 (c) Rekonstruksi citra yang didapatkan dengan hanya menggunakan 25.000 koefisien wavelet terbesar ..............................................................................
7
Gambar 2.2 Proses DWT 3 level ................................................................................
13
Gambar 2.3 Proses inverse DWT 3 level....................................................................
14
Gambar 2.4 Berbagai macam jenis mother wavelet...................................................
15
Gambar 3.1 Blok diagram secara umum....................................................................
19
Gambar 3.2 Blok diagram ..........................................................................................
20
Gambar 3.3 Test image yang digunakan ....................................................................
21
Gambar 3.4 Ilustrasi blocking ....................................................................................
22
Gambar 3.5 Ilustrasi Rekonstruksi.............................................................................
31
Gambar 3.6 Diagram alir umum ................................................................................
37
Gambar 3.7 Diagram alir blocking.............................................................................
42
Gambar 3.8 Ilustrasi w dan h serta J dan K ...............................................................
43
Gambar 3.9 Diagram alir de-blocking........................................................................
47
Gambar 3.10 Diagram alir Orthogonal Matching Pursuit (OMP) ............................
52
Gambar 3.11 User Interface.......................................................................................
55
Gambar 3.12 File Input Box.......................................................................................
56
Gambar 3.13 Window Seleksi Image .........................................................................
56
Gambar 3.14 Pesan Error ..........................................................................................
57
xiii
Gambar 3.15 Blocking Size Selection ........................................................................
57
Gambar 3.16 Slider Aproksimasi...............................................................................
58
Gambar 3.17 Daftar Basis / Dictionary .....................................................................
58
Gambar 3.18 Slider Basis...........................................................................................
59
Gambar 3.19 Slider Basis Disabled ...........................................................................
59
Gambar 3.20 Save Image Checkbox ..........................................................................
59
Gambar 3.21 Process Button .....................................................................................
59
Gambar 3.22 Loading Bar .........................................................................................
60
Gambar 3.23 Image Result Window...........................................................................
60
Gambar 3.24 Title ......................................................................................................
61
Gambar 3.25 Tampilan SNR, PSNR, Time.................................................................
61
Gambar 4.1 Grafik perbandingan PSNR terhadap aproksimasi dengan DCT............
69
Gambar 4.2 Grafik perbandingan PSNR terhadap aproksimasi dengan Wavelet ......
75
Gambar 4.3 Grafik perbandingan PSNR terhadap aproksimasi dengan Overcomplete 81 Gambar 4.4 Grafik perbandingan waktu terhadap aproksimasi dengan Overcomplete 82 Gambar 4.5 Grafik perbandingan PSNR DCT, Wavelet, dan Overcomplete dengan Lena............................................................................................................................
83
Gambar 4.6 Grafik perbandingan waktu DCT, Wavelet, dan Overcomplete dengan Lena............................................................................................................................
83
Gambar 4.7 Lena aproksimasi 5% .............................................................................
84
Gambar 4.8 Lena aproksimasi 95% ...........................................................................
85
Gambar 4.9 Grafik perbandingan PSNR DCT, Wavelet, dan Overcomplete dengan Baboon ....................................................................................................................... xiv
86
Gambar 4.10 Grafik perbandingan waktu DCT, Wavelet, dan Overcomplete dengan Baboon .......................................................................................................................
86
Gambar 4.11 Baboon aproksimasi 5%.......................................................................
87
Gambar 4.12 Baboon aproksimasi 95%.....................................................................
88
Gambar 4.13 Grafik perbandingan PSNR DCT, Wavelet, dan Overcomplete dengan Barbara ......................................................................................................................
89
Gambar 4.14 Grafik perbandingan waktu DCT, Wavelet, dan Overcomplete dengan Barbara ......................................................................................................................
89
Gambar 4.15 Barbara aproksimasi 5%......................................................................
90
Gambar 4.16 Barbara aproksimasi 95%....................................................................
91
Gambar 4.17 Grafik perbandingan PSNR DCT, Wavelet, dan Overcomplete dengan Peppers.......................................................................................................................
92
Gambar 4.18 Grafik perbandingan waktu DCT, Wavelet, dan Overcomplete dengan Peppers.......................................................................................................................
92
Gambar 4.19 Peppers aproksimasi 5% ......................................................................
93
Gambar 4.20 Peppers aproksimasi 95% ....................................................................
94
Gambar 4.21 Grafik perbandingan PSNR DCT, Wavelet, dan Overcomplete dengan Cameraman................................................................................................................
95
Gambar 4.22 Grafik perbandingan waktu DCT, Wavelet, dan Overcomplete dengan Cameraman................................................................................................................
95
Gambar 4.23 Cameraman aproksimasi 5% ...............................................................
96
Gambar 4.24 Cameraman aproksimasi 95% .............................................................
97
Gambar 4.25 Grafik perbandingan PSNR terhadap besar Blocking...........................
99
xv
Gambar 4.26 Lena aproksimasi 10% dengan blocking (a) 2x2 (b) 8x8.....................
99
Gambar 4.27 Lena aproksimasi 50% dengan blocking (a) 2x2 (b) 8x8..................... 100 Gambar 4.28 Grafik perbandingan waktu terhadap besar Blocking .......................... 101 Gambar 4.29 Grafik perbandingan PSNR terhadap jumlah basis yang digunakan.... 104 Gambar 4.30 Grafik perbandingan waktu terhadap jumlah basis yang digunakan ... 105
xvi
DAFTAR PERS AMAAN
Persamaan 2.1 Sparse Representation .......................................................................
6
Persamaan 2.2 Union Base Dictionary ......................................................................
9
Persamaan 2.3 Discrete Fourier Transform ..............................................................
9
Persamaan 2.4 Inverse Discrete Fourier Transform..................................................
10
Persamaan 2.5 DCT Coefficient .................................................................................
10
Persamaan 2.6 Wavelet Transform.............................................................................
11
Persamaan 2.7 Inverse Wavelet Transform................................................................
11
Persamaan 2.8 Quadrature Mirror Transform ..........................................................
14
Persamaan 2.9 Sparse Coding norm part 1................................................................
15
Persamaan 2.10 Sparse Coding norm part 2..............................................................
15
Persamaan 2.11 Peak Signal to Noise Ratio ..............................................................
18
Persamaan 2.12 Mean Square Error..........................................................................
18
Persamaan 3.1 Simplified Sparse Representation ......................................................
24
Persamaan 3.2 Reversed Sparse Representation........................................................
24
Persamaan 3.3 Attaining Dictionary or Base.............................................................
25
xvii
DAFTAR LAMPIRAN
Lampiran A •
Source Code Overcomplete.......................................................................... LA-1
•
Source Code DCT ........................................................................................ LA-2
•
Source Code Wavelet ................................................................................... LA-3
•
Source Code Blocking .................................................................................. LA-4
•
Source Code De-blocking ............................................................................ LA-4
xviii
