TUGAS AKHIR – SM 1330
SUPER-RESOLUSI MENGGUNAKAN ALGORITMA PAPOULIS-GERHCBERG KARINA 1205 100 053 Dosen Pembimbing Drs. Soetrisno, MIKomp.
JURUSAN MATEMATIKA Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Sepuluh Nopember Surabaya 2009
1
FINAL PROJECT – SM 1330
SUPER-RESOLUTION USING PAPOULISGERCHBERG ALGORITHM KARINA NRP. 1205 100 053 Student’s Advisor : Drs. Soetrisno, MIKomp. DEPARTMENT OF MATHEMATICS Faculty of Mathematics and Science Sepuluh Nopember Institute of Technology Surabaya 2009
2
LEMBAR PENGESAHAN
SUPER-RESOLUSI MENGGUNAKAN ALGORITMA PAPOULIS-GERCHBERG
TUGAS AKHIR Diajukan Untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains pada Bidang Minat Ilmu Komputer Program Studi S-1 Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Sepuluh Nopember Oleh : KARINA NRP. 1205 100 053
Disetujui oleh Pembimbing Tugas Akhir : Drs. Soetrisno, MIKomp. NIP. 131 629 805
(
SURABAYA, Agustus 2009
3
)
SUPER-RESOLUSI MENGGUNAKAN ALGORITMA PAPOULISGERCHBERG Nama Mahasiswa NRP Jurusan Dosen Pembimbing
: : : :
Karina 1205 100 053 Matematika FMIPA-ITS Drs. Soetrisno, MIKomp.
Abstrak Super-Resolusi merupakan teknik pemrosesan citra digital yang melakukan penyusunan ulang (rekonstruksi) rangkaian citra resolusi rendah menjadi citra tunggal atau rangkaian citra resolusi tinggi. Hal ini dimungkinkan karena adanya informasi piksel dari rangkaian citra masukan yang dapat diproses untuk menjadi informasi baru dalam pembentukan citra baru beresolusi tinggi. Dalam Tugas Akhir ini, Super-Resolusi untuk rekonstruksi citra diterapkan menggunakan algoritma Papoulis-Gerchberg. Rekonstruksi yang dilakukan bersifat statis, dimana input dalam prosesnya berupa rangkaian citra resolusi rendah, sedangkan output-nya adalah citra tunggal beresolusi tinggi. Dalam rekonstruksi tersebut, diperhitungkan estimasi pergerakan (tidak bersifat motionless) dan format untuk citra masukan dibatasi hanya untuk file berekstensi TIFF. Proses rekonstruksi dilakukan dalam domain frekuensi dimana transformasi Fourier sangat berperan penting di dalamnya. Setelah citra hasil rekonstruksi terbentuk, dilakukan pengukuran hasil Super-Resolusi menggunakan Peak Signal to Noise Ratio (PSNR), serta dilihat juga citra hasil peningkatan resolusi secara visual. Dari uji coba yang telah dilakukan, dapat diambil kesimpulan bahwa algoritma Papoulis-Gerchberg dalam teknik Super-Resolusi merekonstruksi citra lebih pada ketegasan dan kejelasan garis, sementara untuk kekonsistenan warna kurang dapat diandalkan dengan baik. Kualitas citra hasil rekonstruksi sendiri bergantung pada jumlah citra masukkan dan tingkat kerumitan citra yang akan direkonstruksi serta pada citra input yang menjadi dasar grid resolusi tinggi.
Kata kunci: Super-Resolusi, Rekonstruksi Citra, Algoritma PapoulisGerchberg, Domain Frekuensi, Transformasi Fourier, Peak Signal to Noise Ratio.
4
SUPER-RESOLUTION USING PAPOULIS-GERCHBERG ALGORITHM Student’s Name NRP Department of Student’s Advisor
: : : :
Karina 1205 100 053 Mathematics FMIPA-ITS Drs. Soetrisno, MIKomp.
Abstract Super-Resolution is a technique of digital image processing which reconstructs a series of low resolution images into a high resolution image. It is possible because there are some information of pixels from the input images which can be processed to be new information in designing a high resolution image. In this Final Project, Super-Resolution for image reconstruction is applied by using Papoulis-Gerchberg algorithm. The recosntruction is stationary where input in the process is a series of low resolution images while the output is a single high resolution image. In the reconstruction, motion estimation is estimated and the format of input images is constainted for the file which extension is TIFF only. The reconstraction is processed in frequency domain where Fourier transform is very essential. After the reconstruction image is formed, a value of Peak Signal to Noise Ratio (PSNR) is calculated to measure the quality of the image numerically. The quality is also measured visually by comparing input images with the reconstruction image. Some experiments show that Papoulis-Gerchberg algorithm in Super-Resolution reconstructs images more on line clearness, while it does not very good on color consistency. The quality of a reconstruction image depends on the number of low resolution images as input, the subtly level of input images that will be reconstructed, and the input image which is being the base of high resolution image grid.
Keywords : Super-Resolution, Image Reconstruction, PapoulisGerchberg Algorithm, Frequency domain, Fourier Transform, Peak Signal to Noise Ratio.
5
KATA PENGANTAR Dengan syukur yang mendalam, saya ingin bereterima kasih kepada alam semesta beserta setiap orang yang telah datang dalam hidup saya, yang mengilhami, menyentuh, dan menerangi saya melalui kehadirannya sehingga Tugas Akhir dengan judul SuperResolusi Menggunakan Algoritma Papoulis-Gerchberg ini dapat terselesaikan. Salah satu tujuan dari disusunnya Tugas Akhir ini adalah untuk memenuhi sebagian persyaratan dalam mencapai jenjang Sarjana Sains dari Jurusan Matematika Institut Teknologi Sepuluh Nopember Surabaya. Tugas Akhir ini dapat terselesaikan dengan baik dan lancar berkat kerja sama, bantuan dan dukungan dari banyak pihak. Sehubungan dengan hal itu, penulis bermaksud menyampaikan ucapan terima kasih dan penghargaan kepada: 1. Drs. Soetrisno, MIKomp. dan Bapak Budi Setiyono, SSi, MT selaku Dosen Pembimbing yang telah banyak memberi bimbingan dalam penyusunan Tugas Akhir ini; 2. Bapak Prof. DR. Basuki Widodo, MSc selaku Ketua Jurusan Matematika; 3. Drs. Sentot Didik Surjanto, MSi selaku Dosen Wali. 4. Drs. M. Setijo Winarko, Msi, Drs. Kamiran, Msi, dan Dra. Mardlijah, MT selaku dosen penguji; 5. Para sahabat tercinta: Tia, Dian, Wilis Penulis menyadari bahwa dalam penyusunan Tugas Akhir ini masih jauh dari sempurna. Oleh karena itu, penulis sangat mengharapkan saran dan kritik dari pembaca. Harapan penulis semoga Tugas Akhir ini bermanfaat bagi semua pihak yang berkepentingan. Surabaya, Agustus 2009 Penulis
6
Special Thanks To : 1. Papa Superman, Ibu Wonderwoman, dan adik-adik (Sasa, Dira, & Aya) para anggota Power Rangers tercinta di rumah (saat ini di Semarang, entah tahun depan di mana), serta seluruh keluarga besar di Tasik Bersinar. Terima kasih atas cinta dan support (dalam segala bentuk) yang telah kalian berikan dengan tulus selama ini. Kalian lah motivasi terbesar saya dalam menjalani hidup; 2. Sahabat-sahabat terdekat: Tia, Dian, Wilis yang telah bersamasama saya menyelami dalam dunia “otak-atik angka” yang kadang memberikan opsi untuk putus asa (haduh, lebay…hehe). Tapi, berkat kebersamaan kita, saya rasa opsi itu terlumatkan dengan mudah (^_*); 3. Seseorang yang telah dengan tulus memberikan bantuan penuh cintanya selama ini: A.A. Gde Rai Supratha. Terima Kasih. Semoga kamu menemukan seseorang yang tepat di kemudian hari…however, all of those memories will last forever… senyum nae… (^_^); 4. Kembang-kembang cantik GK_28 : Lizzie ‘Huny’ (thx for our every moment ☺), Ditha, Slashz, Garonk, Sinta, Winda, Yani, Dhini, Ome Tere, dll (I’m gonna miss u all) serta adik-adik kecil para personil baru: Laras, Fira, & Fira.. (selamat datang di dunia baru, keep ur cheerness!! ☺ ). Tidak lupa juga untuk Ibu&Bpk Harry, Mas Gema, & Puri yang telah menganggap saya sebagai bagian dari keluarganya… 5. Aa-Aa serta sahabat-sahabat di Keluarga Mahasiswa Jawa Barat (KM Jabar) ITS: A Ndank, A Fatuh, A Aris, A Aji, Papih Sinchan, Boro, Acil, Fahmi, Desti, The Wati, dll. (thx for being great brothers&sisters ☺ ); 6. Kawan-kawan seperjuangan TA, calon wisudawan ke-99, terima kasih atas kebersamaannya dalam suka dan duka; 7. Seluruh teman-teman Jurusan Matematika angkatan 2005 yang tidak dapat disebutkan satu per satu, terimakasih atas dukungan dan kebersamaannya selama ini…masa-masa indah itu tidak akan saya lupakan ☺;
7
8. Dosen-dosen, staff, serta para mahasiswa PAPSI (Program Ahli Pemrograman Sistem Informasi) ITS yang telah banyak memberikan saya kesempatan untuk berpengalaman hidup. (Anda ingin mahir dalam pemrograman? Gabung aja di PAPSI ITS!!hehe…) 9. Ashutosh Singh (India) & Maximillien Summers (Canada). Thx for entertaining and spiriting me up while I’m working on this Final Project. U know guys, u both make me realize that nothing is impossible in this world ☺; (@Ashu: I love your quote Work smarter, not harder!!haha… and also this one it’s very easy to critic but very difficult to appreciate…I’ll learn to do the opposite as u do ☺ )
8
DAFTAR ISI
Halaman JUDUL ABSTRAK ............................................................................... 4 KATA PENGANTAR ............................................................. 6 DAFTAR ISI............................................................................ 9 DAFTAR GAMBAR ...............................................................12 DAFTAR TABEL....................................................................14 DAFTAR LAMPIRAN............................................................15 BAB I PENDAHULUAN ..................................................... 16 1.1 Latar Belakang Masalah.................................... 16 1.2 Rumusan Masalah ............................................ 17 1.3 Batasan Masalah .............................................. 18 1.4 Tujuan ............................................................... 18 1.5 Metodologi Penelitian ....................................... 19 1.6 Sistematika Penulisan ........................................ 20 1.7 Relevansi ........................................................... 20 BAB II DASAR TEORI ....................................................... 21 2.1 Citra Digital ....................................................... 21 2.1.1 Model Citra Digital ................................. 21 2.1.2 Elemen-elemen Dasar Citra .................... 22 2.1.3 Resolusi Citra .......................................... 24 2.1.4 Dasar Warna Citra Digital ....................... 24 2.1.5 Tipe Citra Digital ..................................... 27 2.2 Operasi Pengolahan Citra ................................ 30 2.2.1 Rekonstruksi Citra ................................... 31 2.2.2 Registrasi Citra......................................... 32 2.2.3 Interpolasi................................................. 33 2.2.4 Pelembutan Citra ...................................... 34 2.3 Super-Resolusi .................................................. 35 2.3.1 Jenis Super-Resolusi untuk Rekonstruksi Citra ......................................................... 36
9
2.4 Metode Domain Frekuensi ............................... 37 2.4.1 Transformasi Fourier Dua Dimensi ......... 38 2.4.2 Transformasi Fourier Diskrit Dua Dimensi ..................................................... 39 2.4.3 Hubungan Antara Transformasi Fourier dengan Transformasi Fourier Diskrit ....... 44 2.5 Algoritma Papoulis-Gerchberg ......................... 45 2.6 Teknik Pengukuran Kualitas Citra ................... 48 2.6.1 Mean Square Error (MSE) ..................... 48 2.6.2 Peak Signal to Noise Ratio (PSNR) ......... 48 BAB III ANALISIS SISTEM DAN PERANCANGAN PERANGKAT LUNAK .................................................................. 49 3.1 Analisis Sistem .................................................. 49 3.1.1 Analisis Sistem Program Super-Resolusi. 49 3.1.2 Analisis Sistem Pembuatan Model Observasi .................................................. 50 3.1.3 Analisis Sistem Pengujian Hasil Menggunakan PSNR................................ 51 3.2 Analisis Penyelesaian Teknik ............................ 55 3.2.1 Analisis Teknik Pembuatan Model Observasi .................................................. 55 3.2.2 Analisis Teknik Super-Resolusi ............... 56 3.2.3 Analisis Rekonstruksi Citra Menggunakan Algortima Papoulis-Gerchberg ................. 57 3.3 Perancangan Perangkat Lunak ......................... 58 3.3.1 Data Flow Diagram (DFD) ..................... 58 3.3.2 Fungsi-fungsi yang Dibutuhkan Sistem ... 63 BAB IV IMPLEMENTASI SISTEM ...................................... 68 4.1 Lingkungan Implementasi ....................................... 68 4.2 Desain Tampilan ..................................................... 68 4.3 Proses Pemuatan Citra ............................................. 73 4.4 Proses Pembentukan Model Observasi .................... 73 4.5 Proses Pengaturan Estimasi Pergerakan (Motion Estimation) .............................................................. 75
10
4.6 Proses Penyimpanan File ......................................... 79 4.7 Proses Rekonstruksi Citra Menggunakan Algoritma Papoulis-Gerchberg ................................................. 80 4.8 Proses Mencari Nilai PSNR ..................................... 81
BAB V PENGUJIAN DAN ANALISIS PERANGKAT LUNAK ...................................................................... 83 5.1 Lingkungan Uji Coba .............................................. 83 5.2 Data Uji Coba .......................................................... 83 5.3 Pelaksanaan Uji Coba dan Evaluasi ......................... 85 5.3.1 Uji Coba Pada Citra ”Elips.tif”....................... 85 5.3.2 Uji Coba Pada Citra ”elipsC.tif”..................... 89 5.3.3 Uji Coba Pada Citra ”plat nomor angkot.tif”.. 96 5.4 Evaluasi ....................................................................103 5.4.1 Nilai PNSR Rata-rata pada Citra Hasil SuperResolusi Menggunakan Algoritma PapoulisGerchberg ......................................................103 5.4.2 Perbedaan Citra Hasil Super-Resolusi Menggunakan Algoritma Papoulis-Gerchberg terhadap Jumlah Citra Observasi secara Visual .............................................................103 BAB VI KESIMPULAN DAN SARAN ................................109 6.1 Kesimpulan .............................................................109 6.2 Saran ........................................................................110 DAFTAR PUSTAKA .............................................................111 BIODATA ..............................................................................113
11
DAFTAR GAMBAR
Halaman Gambar 2.1 Menentukan Kepekaan Kontras pada Mata manusia ............................................................ 23 Gambar 2.2 Citra Sebagai Fungsi Dua Variabel x dan y ...... 25 Gambar 2.3 Sistem Koordinat Piksel pada Citra Digital ..... 26 Gambar 2.4 Tiga Warna Dasar Citra Berwarna .................... 26 Gambar 2.5 Nilai-nilai Piksel dari Citra Biner ..................... 27 Gambar 2.6 Contoh Citra Berindeks ..................................... 28 Gambar 2.7 Nilai Piksel pada Citra Hitam-Putih yang Didefinisikan oleh Level Keabuan ................... 29 Gambar 2.8 Contoh Citra RGB............................................. 30 Gambar 2.9 Model Degradasi ............................................... 31 Gambar 2.10 Contoh Kalkulasi Energi pada Sudut Citra ....... 32 Gambar 2.11 Langkah-langkah Teknik Super-Resolusi ......... 36 Gambar 2.12 (a) Rekonstruksi Citra Statis ............................. 37 (b) Rekonstruksi Citra Dinamis ....................... 38 Gambar 2.13 Ilustrasi Ekstrapolasi g(t) Menggunakan Algoritma Papoulis-Gerchberg ......................... 47 Gambar 3.1 Diagram alur program Super-Resolusi menggunakan algoritma PapoulisGerchberg.......................................................... 52 Gambar 3.2 Diagram alur sistem pembuatan citra observasi ........................................................... 53 Gambar 3.3 Diagram alur program PSNR ............................. 54 Gambar 3.4 Langkah-langkah keseluruhan proses SuperResolusi untuk Rekonstruksi Citra .................... 57 Gambar 3.5 Langkah-langkah Penyelesaian Super-Resolusi Menggunakan Algoritma Papoulis-Gerchberg . 58 Gambar 3.6 Context Diagram Teknik Super-Resolusi untuk Rekonstruksi Citra............................................. 59 Gambar 3.7 DFD Level 1 Teknik Super-Resolusi untuk Rekonstruksi Citra............................................. 60
12
Gambar 3.8 DFD Level 2, Fungsi Pembuatan Model Observasi ............................................................ 61 Gambar 3.9 DFD Level 2, Fungsi Rekonstruksi Citra Menggunakan Algoritma Papoulis-Gerchberg . 63 Gambar 4.1 Desain Antarmuka Program Super-Resolusi Menggunakan Algoritma Papoulis-Gerchberg . 71 Gambar 4.2 Desain Antarmuka Program Generasi Citra....... 72 Gambar 4.3 Desain Antarmuka Program PSNR .................... 73 Gambar 4.4 Kode Program Pemuatan Citra Input ................. 74 Gambar 4.5 Kode Program Pergeseran dan Perputaran Citra 75 Gambar 4.6 Kode Program Pengaburan (Blurring) dan Desimasi Citra .................................................... 75 Gambar 4.7 Kode Program Penambahan Noise atau Gangguan pada Citra .......................................... 76 Gambar 4.8 Kode Program untuk Estimasi Perputaran ......... 77 Gambar 4.9 Kode Program untuk Estimasi Pergeseran ......... 78 Gambar 4.10 Kode Program untuk Estimasi Pergerakan ........ 80 Gambar 4.11 Kode Program untuk Penyimpanan Citra .......... 81 Gambar 4.12 Kode Program untuk Rekonstruksi Citra Menggunakan Algoritma Papoulis-Gerchberg ... 81 Gambar 4.13 Kode Program untuk Mencari Nilai PSNR ....... 82 Gambar 5.1 Rangkaian Citra Observasi Beresolusi Rendah dari Gambar “Elips.tif” ....................................... 86 Gambar 5.2 Hasil Pembesaran 2x Salah Satu Citra Observasi Resolusi Rendah dari Gambar ”Elips.tif” ........... 86 Gambar 5.3 Citra ”Elips.tif” Hasil Rekonstruksi Menggunakan Algoritma Papoulis-Gerchberg ... 87 Gambar 5.4 (a) Potongan salah satu citra input dengan pembesaran 8x, (b) Potongan citra hasil rekonstruksi menggunakan algoritma PapoulisGerchberg dengan pembesaran 4x ...................... 88 Gambar 5.5 Grafik Nilai PSNR citra ”Elips.tif” terhadap jumlah citra observasi ......................................... 89 Gambar 5.6 (a) Salah satu dari rangkaian citra observasi beresolusi rendah dari gambar ”elipsC.tif”, (b) Hasil pembesaran 2x citra (a) ...................... 90
13
Gambar 5.7 Citra ”elipsC.tif” Hasil Rekonstruksi Menggunakan Algoritma Papoulis-Gerchberg . 91 Gambar 5.8 (a) Potongan salah satu citra input ”elipsC.tif” dengan pembesaran 8x, (b)Potongan citra ”elipsC.tif” hasil rekonstruksi menggunakan algoritma Papoulis-Gerchberg dengan pembesaran 4x................................................... 91 Gambar 5.9 Grafik Nilai PSNR citra ”elipsC.tif” terhadap jumlah citra observasi ....................................... 93 Gambar 5.10 Hasil Pembesaran 2x Salah Satu Citra Observasi Resolusi Rendah dari Gambar ”Elips.tif” ......... 93 Gambar 5.11 Citra ”tes_mata.tif” Hasil Rekonstruksi Menggunakan Algoritma Papoulis-Gerchberg . 94 Gambar 5.12 Grafik Nilai PSNR citra ”tes_mata.tif” terhadap jumlah citra observasi ....................................... 95 Gambar 5.13 Rangkaian Citra Observasi Beresolusi Rendah dari Gambar “plat nomor angkot.tif” ................ 97 Gambar 5.14 (a) Hasil Pembesaran 2x Salah Satu Citra Observasi Resolusi Rendah dari Gambar ”plat nomor angkot.tif”, (b) Hasil rekonstruksi menggunakan algoritma Papoulis-Gerchberg ... 98 Gambar 5.15 Citra “plat nomor angkot.tif” hasil rekonstruksi dengan pembesaran 2x ...................................... 99 Gambar 5.16 Grafik Nilai PSNR citra ”plat nomor angkot.tif” terhadap jumlah citra observasi......................... 101 Gambar 5.17 Hasil rekonstruksi citra ”plat nomor angkot.tif” dengan citra dasar adalah citra ke-2 .................. 102 Gambar 5.18 Hasil rekonstruksi citra ”plat nomor angkot.tif” dengan citra dasar adalah citra ke-3 .................. 102
14
DAFTAR TABEL
Halaman Tabel 4.1 Tabel 5.1 Tabel 5.2 Tabel 5.3 Tabel 5.4 Tabel 5.5 Tabel 5.6 Tabel 5.7 Tabel 5.8
Lingkungan Implementasi Perangkat Lunak ........ 68 Lingkungan Pengujian Perangkat Lunak .............. 82 Data Citra Referensi (Citra Asli) .......................... 83 Data nilai PSNR citra ”Elips.tif” terhadap jumlah citra observasi....................................................... 88 Data nilai PSNR citra ”elipsC.tif” terhadap jumlah citra observasi....................................................... 92 Data nilai PSNR citra ”tes_mata.tif” terhadap jumlah citra observasi........................................... 95 Data nilai PSNR citra ”plat nomor angkot.tif” terhadap jumlah citra observasi ............................ 100 Nilai PSNR rata-rata untuk Super-Resolusi menggunakan Algoritma Papoulis-Gerchberg ..... 103 Perbedaan citra hasil rekonstruksi terhadap jumlah model observasi secara visual .............................. 104
15
