BAB 2 KAJIAN PUS TAKA
2.1
Visi Komputer (Computer Vision) Computer vision merupakan sub disiplin ilmu dari kecerdasan buatan yang
mempelajari bagaimana mesin dapat mengenali objek yang diamati atau diobservasi (sumber : wikipedia). Dapat juga disebut sebagai machine vision, ilmu ini mengembangkan teori-teori dan algoritma dimana informasi yang berguna diekstraksi dan dianalisis dari sebuah citra penelitian, sekumpulan citra, atau citra yang berurutan dari sebuah komputasi yang dibuat oleh computer (http://www.personal.umd.munich.edu). Visi komputer oleh beberapa ahli didefinisikan sebagai berikut : •
Ballard dan Brown (Ballard & Brown, 1982), computer vision adalah otomatis dan integrasi sebuah range yang luas yang terdiri dari proses-proses dan representasi-representasi terhadap persepsi visual.
•
Adrian Low (Low, 1991), visi komputer berhubungan dengan perolehan gambar, pemrosesan, klasifikasi, pengenalan, dan menjadi penggabungan, pengurutan pembuatan keputusan menuju pengenalan.
•
M ichael G. Fairhurst (Fairhurst, 1988), visi komputer sesuai dengan sifatnya, merupakan suatu subyek yang merangkul berbagai disiplin tradisional secara luas guna mendasari prinsip-prinsip formalnya, dan dalam mengembangkan suatu metodologi yang berlainan dari apa yang dimilikinya, pertama-tama harus mengembangkan dan secara berurutan membangun materi yang mendasari ini.
8
9
•
Shapiro dan Stockman (Shapiro & Stockman, 2001), visi komputer adalah suatu bidang yang bertujuan untuk membuat suatu keputusan yang berguna mengenai objek fisik nyata dan keadaan berdasarkan atas sebuah citra. Visi komputer merupakan kombinasi antara pengolahan citra dan pengenalan pola. Hasil keluaran dari proses visi komputer adalah pengertian tentang citra.
Gambar 2.1 Skema hubungan visi komputer dengan bidang lain
Boyle dan Thomas (C & Boyle, 1988), mengatakan bahwa computer vision lebih daripada pengenalan, computer vision melakukan operasi “low level processing” sebagai algoritma image processing yang murni. M ereka juga yang menggolongkan image processing ke dalam computer vision.
10
2.1.1
Pengolahan Citra Pengolahan citra merupakan bidang studi yang mempelajari proses pengolahan
gambar dimana baik masukan maupun keluarannya berbentuk berkas citra digital (Arymurthy & Setiawan, 1992). Juga dijelaskan bahwa pengolahan citra merupakan pengolahan dan analisis citra yang banyak melibatkan persepsi visual. Seperti yang dikemukakan oleh Chen (2003), bahwa kebutuhan untuk memproses sebuah gambar dengan cepat dalam satu aplikasi merupakan salah satu masalah utama dalam melakukan pengolahan citra. Sedangkan untuk aplikasi yang berjalan secara real time lebih bergantung pada pemrosesan piksel atau signal yang cepat daripada metode optimasi lain yang rumit dan memakan waktu. Niblack (Niblack, 1986) menjelaskan image processing sebagai pemrosesan dari citra-citra, kemudian menambahkan bahwa output dari image processing akan juga menjadi sebuah image.
2.1.1.1 Citra Digital Ada beberapa definisi citra digital, yaitu : •
Suatu representasi, kemiripan, atau imitasi dari suatu objek atau benda (menurut kamus webster).
•
Gambar dua dimensi yang dihasilkan dari gambar analog dua dimensi yang kontinu menjadi gambar diskrit melalui proses sampling. Gambar analog adalah representasi visual dari suatu objek menggunakan kamera analog yang secara matematika dapat direpresentasikan sebagai rentang nilai yang menunjukkan letak (posisi) dan intensitas. Gambar analog dibagi menjadi N baris dan M kolom
11
sehingga menjadi gambar diskrit. Persilangan antara baris dan kolom tertentu disebut dengan piksel. Sampling pada penjelasan di atas ada proses untuk menentukan warna pada piksel tertentu pada citra dari sebuah gambar yang kontinu. Pada proses sampling biasanya dicari warna rata-rata dari gambar analog yang kemudian dibulatkan. Proses sampling sering disebut juga dengan proses digitisasi. •
Representasi dari suatu objek nyata baik dalam bentuk dua dimensi maupun tiga dimensi menjadi bentuk gambar digital yang dikenali oleh komputer (Jain, 1989).
•
Fungsi intensitas warna dua dimensi f(x,y) dimana x dan y mewakili koordinat lokasi suatu titik dan nilai dari fungsi yang merupakan tingkat intensitas warna atau tingkat keabu-abuan dari titik tersebut (Schalkoff, 1989).
Gambar 2.2 Citra Digital
12
2.1.2
Pengenalan Wajah (Face Recognition) Sistem pengenalan wajah merupakan subjek yang menarik untuk diteliti sejak
lama. Hal ini dikarenakan pengenalan wajah merupakan cara yang utama bagi manusia untuk mengenali dan mengidentifikasi seseorang. Setiap orang memiliki ciri wajah yang unik dan berbeda. Dengan melihat dari wajah, seseorang dapat dibedakan dengan orang yang lainnya. Tehnik pengenalan wajah telah berkembang jauh sebelum komputer ada. Francis Galton, pada tahun 1888, mengemukakan metode dengan menggunakan pendekatan geometris. Dalam proposalnya, Galton menitikberatkan perhatian pada fitur-fitur penting dari wajah, yang disebut keys points. Keys points ini meliputi alis, mata, hidung, bibir dan sebagainya. Dengan menghitung jarak antara keys points dapat diperoleh ciri wajah seseorang. Akan tetapi tehnik yang dikemukakan oleh Galton sangat sensitif terhadap perubahan wajah, sehingga akan mengalami kegagalan ketika ada penambahan atribut pada wajah. Dalam usaha ingin meniru kemampuan manusia dalam mengenali dan mengidentifikasikan seseorang, para peneliti dalam bidang Computer Vision pun melakukan penelitian. Hasilnya metode-metode dalam sistem pengenalan wajah ini dikelompokkan menjadi dua kategori pendekatan (Chelappa et al 1955) yaitu : featurebased dan holistic. Sedangkan menurut Quintiliano dan Rosa (Quintiliano & Rosa, 2006) dibagi menjadi tiga, yaitu : template-based, feature-based dan appearance-based. Pendekatan template-based sendiri mempunyai dua versi, yang pertama (yang paling sederhana) menggambarkan citra wajah sebagai matriks bidimensional yang nilainya mewakili edges dari tingkat kelonjongan wajah dan factor dari wajah. Yang
13
kedua, lebih lengkap, menggambarkan citra wajah sebagai multiple templates yang dimabil dari berbagai sudut dan arah pandang. Kelebihan dari teknik ini adalah kesederhanaannya meskipun menggunakan memori yang cukup besar dan algoritma yang tidak efisien. (Quintiliano & Rosa, 2006) Pendekatan dengan feature-based pada dasarnya tergantung pendeteksian dan pengkarakterisasian dari feature wajah seseorang serta hubungan geometriknya. Pada umumnya feature yang dimaksud adalah mata, mulut dan hidung. Sedangkan pendekatan holistic lebih melibatkan keseluruhan citra wajah dengan melakukan proses encoding dan memberlakukan “kode” wajah dari hasil encoding tersebut sebagai sebuah titik dalam ruang berdimensi tinggi. Pada pendekatan feature-based, proses awal pada automatisasi proses pengenalan wajah lebih penting. Proses awal ini melibatkan penggunaan tehnik pengolahan citra yang sederhana, seperti pendeteksian sisi dan lain-lain dengan tujuan mendeteksi wajah dan feature-featurenya. Sebagai contoh: tehnik dari Sakai pada tahun 1969 dimana pertama-tama peta sisi diekstrak dari sebuah citra masukan dan kemudian dicocokkan pada template oval yang besar, dengan variasi-variasi posisi dan ukuran yang mungkin. Adanya wajah atau tidak dikonfirmasi dengan mencari sisi-sisi pada lokasi yang diperkirakan dari feature-feature seperti mata dan mulut. Pada tahun 1970, Kelly menggunakan sebuah pendeteksi sisi untuk mengekstrak outline wajah manusia dari berbagai macam latar belakang. Govindaraju, Srihari dan Sher pada tahun 1990 memperkenalkan sebuah teknik dimana meletakkan wajah pada citra kacau yang menggunakan template yang dapat diuraikan. Teknik ini juga mirip dengan penelitian yang dilakukan oleh Yuille, Cohen dan Hallinan pada tahun 1989.
14
Pendekatan ini menunjukkan kinerja yang baik ketika diuji pada sebuah set data yang kecil, tetapi terkadang terdapat peningkatan pada pengenalan yang salah. Sedangkan teknik yang diperkenalkan oleh Kanade pada tahun 1973 serta Harmon dan Hunt pada tahun 1977 merupakan teknik dimana ketika citra wajah dimasukkan akan langsung melakukan perhitungan. Teknik feature-based menggunakan lebih sedikit penghitungan daripada template-based. Sedangkan pendekatan holistic yang paling sukses adalah menggunakan Karhunen Loeve Transform (KLT). Teknik ini pertama kali diperkenalkan oleh Kirby dan Sirovich pada tahun 1990 yang dinamakan sebagai Principal Component Analysis (PCA). Transformasi ini menghasilkan perluasan dari sebuah citra masukan yang berhubungan dengan suatu set dari citra dasar atau dinamakan eigen images. Kemudian pada tahun 1991, Turk dan Pentland memperkenalkan teknik dimana hanya menggunakan beberapa koefisien KLT yang digunakan untuk mempresentasikan wajah yang dinamakan sebagai face space. Sistem bekerja sangat baik bagi citra yang diambil frontal. Tetapi sistem ini tidak dapat mengatasi variasi pada orientasi wajah, posisi dan iluminasi. Sehingga terdapat beberapa penelitian untuk mengatasi masalah ini, seperti pada tahun 1991 yang dilakukan Akamatsu, Sasaki, Fukamachi dan Suenega dimana beberapa proses ditambahkan untuk menstandarisasi citra wajah dalam posisi dan ukuran. Pendekatan holistic lainnya adalah menggunakan Discrete Cosine Transform (DCT) sebagai proses feature extraction untuk klasifikasi selanjutnya DCT dihitung pada citra wajah kemudian hanya dipilih beberapa koefisien yang menjadi feature
15
vector. Feature vector ini dapat dianggap sebagai representasi sebuah titik dalam ruang “wajah” berdimensi tinggi. Secara umum proses pengenalan wajah dibagi menjadi 3, yaitu : a.
Pemisahan gambar dari gambar-gambar yang tidak teratur. Pemisahan biasanya dengan menggunakan algoritma berikut ini. Sebuah sisi di construct, lalu sisi-sisi ini dihubungkan dengan beberapa heuristic, dan sisi-sisi disesuaikan ke dalam bentuk elips dengan menggunakan transformasi Hough. Hal tersebut dilakukan bila input diubah dari video images. Pemisahan dilakukan menggunakan gerakan (motion) sebagai isyarat.
b.
M engekstrak objek dari area wajah Ada 2 tipe objek yang penting: objek holistic (dimana masing-masing objek adalah sebuah karakteristik dari seluruh wajah) dan objek partial membuat beberapa ukuran ke dalam beberapa point penting dari wajah, sedangkan tehnik object holistic selalu menggunakan wajah secara keseluruhan. PCA adalah sebuah tehnik objek holistic.
c.
Keputusan Sebuah keputusan diambil dari data yang terkumpul pada tahap sebelumnya. Tiga tipe keputusan yang dapat diambil adalah: 1.
Identifikasi, nama atau label individu yang didapat.
2.
Pengenalan seseorang, keputusan dimana individu siap dilihat.
3.
Pengkategorian, yang mana wajah harus diberikan dalam kategori.
16
Tehnik pengenalan wajah yang umum berdasarkan Jain et.al.
(Jain, Halici,
Hayashi, Lee, & Tsutsui, 1999) : a. Hidden Markov Models ( HMMs ) Samario & Harter pada tahun 1994 menggunakan konvensional Hidden Markov Models sebagai sebuah pendekatan grafis untuk mengubah informasi fitur dalam bentuk kode. Namun karena kompleksitas perhitungan yang amat tinggi, maka tehnik ini tidak cocok untuk digunakan dalam teknik real time walalupun tingkat akurasi yang tinggi dapat dicapai. b. Eigenface Turk & Pentland pada tahun 1991 menerapkan tehnik ini sebagai pengembangan dari PCA yang telah ada dengan menghitung eigenfaces untuk tiap citra dari data yang didapat baik dalam pelatihan dan pengujian. c. Conventional Networks Laurance, Giles, Tsai dan Back pada tahun 1997 menggunakan sebuah Self Organising Map (SOM ) untuk mengurangi dimensi dari representasi input dan lima layer conventional networks untuk mengatasi masalah translasi dan perubahan citra wajah. Tehnik ini lebih cepat dari pendekatan Hidden Markov Models sebelumnya, namun masih memerlukan waktu pelatihan yang cukup lama. d. Probabilistic Decision-Based Neural Networks Tehnik ini diteliti oleh Lim Kung dan Lim pada tahun 1997, dimana teknik ini bertujuan untuk mengatasi masalah waktu pelatihan dan klasifikasi yang terdapat pada teknik conventional network.
17
e. Radial Basis Function Networks (RBF) Hawell pada tahun 1997 menggunakan pendekatan dengan jaringan Radial Basis Function yang sangat cepat dalam pelatihan dan merupakan yang tercepat untuk klasifikasi dari semua teknik yang ada. f. Continous µ-tuple Classifier Tehnik ini dikembangkan oleh Lucas pada tahun 1997 yang mana merupakan pengembangan dari µ-tuple Classifier sebelumnya. Pengembangan ini dilakukan hanya untuk mengatasi masalah kecepatan dan efisiensi penyimpanan, namun belum mengatasi masalah yang terdapat dalam pengujian di dunia nyata pada pose dan pencahayaan citra. g. Nearest Neighbor Classifier Lucas pada tahun 1997 juga berhasil mencapai performa yang tinggi dengan INearest Neighbor Classifier sederhana menggunakan pengukuran jarak CityBlock.
2.2
Principal Component Analysis M etode transformasi yang umum digunakan adalah Principal Component
Analysis (PCA). Untuk mengenal suatu citra (image) diperlukan suatu vektor karakteristik yang disebut vektor eigen. Untuk memperoleh vektor eigen harus melalui proses-proses sehingga keakuratan pengenalan citra wajah dapat optimal. Proses-proses ini kemudian dikembangkan menjadi metode Principal Component Analysis. A Principal Component Analysis (PCA) is a powerful technique for extracting a structure from potentially high-dimentional data sets, which corresponds to extracting
18
the eigenvectors that are associated with the largest eigenvalues from the input distribution. (Kwang, et.al, 2002) PCA merupakan metode matematik linear untuk merepresentasikan sebuah objek, mengekstrak ciri-ciri sebuah objek dan mereduksi dimensi dari objek tersebut dengan cara mentransformasikan sejumlah variable korelasi ke jumlah yang lebih sedikit. (Lakshminarayana & Neurman, 1999) M erepresentasikan sebuah objek adalah mengubah intensitas piksel pada sebuah citra menjadi bentuk yang lebih sederhana, yaitu berupa kumpulan vektor yang dinamakan Principal Component. PCA mengekstrak ciri-ciri sebuah objek, metode ini tidak membutuhkan input berupa definisi ciri-ciri sebuah objek, tetapi PCA justru mampu mengidentifikasi sendiri ciri-ciri dari sebuah objek. Tujuan penerapan metode PCA yang pertama adalah mereduksi dimensi dari suatu objek, sehingga ukuran dari objek akan lebih ringkas. Kedua, PCA mampu mengambil karakteristik yang paling penting dari objek yang diolah yang biasanya disebut feature extraction. Jika dimens i lebih kecil dan informasi yang terkandung lebih penting (berupa vektor karakteristik), maka objek tersebut akan lebih spesifik dibandingkan objek yang belum diolah sebelumnya. Hal ini tentunya akan mempermudah pemrosesan objek lebih lanjut. PCA menggunakan intensitas piksel citra dalam merepresentasikan citra. Tehnik matematik yang digunakan adalah eigen analysis yang menggunakan nilai eigen dan vektor eigen dalam perhitungan. PCA merupakan tehnik yang bersifat shape-free yang
19
tidak terlalu memperhatikan bentuk dari sebuah citra melainkan mencari intensitas nilai pixel dari penghitungan. Hasil dari Principal Component Analysis (PCA) adalah sebuah objek baru dalam bentuk PCA. Perhitungan pada PCA kurang lebih sebagai berikut : asumsikan data dengan dimensi banyak telah disimpan pada objek TabelData yang merupakan matriks persegi panjang. Jika terdapat banyak perbedaan pada tiap-tiap kolom pada TabelData atau unit-unit pengukuran pada kolom berbeda maka data harus dinormalisasi terlebih dahulu. M enggunakan sebuah PCA pada matriks data ternormalisasi mempunyai pengaruh yang sama seperti menggunakan analisis pada matriks korelasi (matriks kovarian dari data ternormalisasi sama dengan matriks korelasi dari data ini). Kemudian dilakukan pemetaan gambar dari nilai eigen, menggambar nilai eigen untuk mendapatkan ciri dari nilai eigen yang penting. Principal components didapatkan dengan memproyeksikan vektor-vektor data pada tempat kosong terentang oleh vektor eigen. Ini dapat dilakukan dengan dua cara: 1. Langsung dari TabelData tanpa melakukan pembentukan objek PCA terlebih dahulu. Kemudian dapat menggambar konfigurasi atau menampilkan angkaangkanya. 2. M emilih sebuah PCA dan sebuah objek TabelData bersama-sama dan memilih konfigurasi. Dengan cara ini dapat diproyeksikan TabelData pada PCA’s eigenspace. Tehnik matematika yang digunakan dalam PCA disebut analisa eigen, menyelesaikan nilai eigen dan vektor eigen dari sebuah matriks persegi simetri dengan jumlah dari perkalian. Vektor eigen berhubungan dengan nilai eigen terbesar yang
20
mempunyai arah yang sama seperti principal component yang pertama. Vektor eigen berhubungan dengan nilai eigen terbesar kedua menentukan arah dari principal component kedua. Jumlah dari nilai eigen sama dengan pembacaan dari matriks persegi dan jumlah maksimal dari vektor eigen sama dengan jumlah baris (atau kolom) dari matriks ini. Secara matematik, tehnik PCA dapat didefinisikan sebagai berikut : misalnya terdapat himpunan citra, T 1,T 2,T 3, … , Tn maka nilai rata-rata dari himpunan citra tersebut adalah :
1 N Ψ = . Σ Tn N n =1
Ψ : noise N : jumlahgambar
Setelah itu bentuk himpunan citra baru yang bebas dari noise, yaitu Î1, Î2 , Î3,…, În yang didapat dari : În = Tn – Ψ În : himpunan citra bebas noise Kemudian dibangun matriks A yang merupakan kumpulan dari himpunan citra yang bebas dari noise, A = [ Î1, Î2 , Î3,…, În ] Proses selanjutnya adalah mencari nilai covariance dari himpunan citra yang telah bebas dari noise : Covariance = 1/N . At .A Sehingga pada akhirnya akan didapatkan matriks covariance dengan dimensi N x N. Karena dimensi matriks covariance masih cukup tinggi, sehingga untuk mencari N
21
vektor eigen dari matriks covariance masih terlalu sukar, misalkan Vi adalah vektor eigen dari matriks covariance maka: ( A . At ) . Vi = Vi . Vi Tiap ruas dikalikan dengan A : A ( A . At ) . Vi = A ( Vi . Vi ) ( A . At ) . ( A . Vi ) = Vi ( A . Vi ) Dimana A . Vi adalah vektor eigen dari matriks covariance, maka vektor eigen dari matriks covariance dapat dihitung dengan : ⎞ ⎛ ⎜ i1 ⎟ ⎟ ⎜ i2 ⎟ 1, 2, 3,..., N . ⎜ = ⎜ ... ⎟ ⎟⎟ ⎜⎜ ⎝ iN ⎠
V A.Vi = [i i i i ] V V
An . Vi
2.3
Wavelet dan Transformasi Wavelet
2.3.1
Definisi Wavelet
Teori wavelet adalah suatu konsep yang relatif baru dikembangkan. Kata “Wavelet” sendiri diberikan oleh Jean Morlet dan Alex Grossman diawal tahun 1980-an, dan berasal dari bahasa Perancis, “ondelette” yang berarti gelombang kecil. Kata “onde” yang berarti gelombang kemudian diterjemahkan ke bahasa Inggris menjadi “wave”, lalu digabung dengan kata aslinya sehingga terbentuk kata baru “wavelet”. Yang dimaksud dengan wavelet adalah sekumpulan fungsi dalam ruang L2(R) yang memiliki sifat-sifat : a. Berenergi terbatas. b. Merupakan fungsi band-pass. c. Merupakan hasil translasi dan dilasi dari sebuah fungsi tunggal.
22
Wavelet digunakan untuk membagi sebuah fungsi atau sinyal kontinu menjadi komponen-komponen frekuensi yang berbeda dan mempelajari tiap komponen dengan resolusi yang sesuai dengan skalanya.
2.3.2
Transformasi Fourier dan Transformasi Fourier Waktu Singkat
Transformasi Fourier, dinamakan atas Joseph Fourier, adalah sebuah transformasi integral yang menyatakan kembali sebuah fungsi dalam fungsi basis sinusioidal, yaitu sebuah fungsi sinusioidal penjumlahan atau integral dikalikan oleh beberapa koefisien ("amplitudo"). Ada banyak variasi yang berhubungan dekat dari transformasi ini tergantung jenis fungsi yang ditransformasikan. Transformasi Fourier mendekomposisi sebuah sinyal pada fungsi-fungsi eksponensial kompleks dari frekuensi-frekuensi yang ada. Kelemahan utama transformasi Fourier adalah bahwa ia hanya memiliki resolusi frekuensi tanpa ada resolusi waktu. Ini berarti walaupun kita bisa menentukan semua frekuensi yang ada dalam sinyal, kita tidak tahu kapan frekuensi tersebut muncul. Maka dari itu transformasi Fourier tidak baik untuk merepresentasikan sinyal non-stasioner. Untuk memecahkan masalah ini, dalam beberapa dekade terakhir, beberapa solusi telah dikembangkan yang secara kurang lebih mampu merepresentasikan sinyal dalam domain waktu dan frekuensi pada saat yang bersamaan. Solusi awal dari masalah ini adalah Transformasi Fourier Waktu Singkat (Short Time Fourier Transform / STFT). Dalam Transformasi Fourier Waktu Singkat, sinyal dibagi menjadi bagian-bagian berukuran cukup kecil, dimana bagian-bagian sinyal
23
tersebut dapat diasumsikan stasioner. Untuk tujuan ini sebuah fungsi jendela “ω” dipilih. Lebar dari jendela ini harus sama dengan bagian sinyal yang stasionaritasnya valid. Masalah dengan Transformasi Fourier Waktu Singkat berakar pada apa yang dikenal dengan prinsip Ketidakpastian Heisenberg. Prinsip ini menyatakan bahwa seseorang tidak dapat mengetahui komponen spektral apa saja yang ada pada satu waktu. Yang dapat diketahui seseorang adalah selang waktu dimana rentang frekuensi tertentu muncul, yang merupakan masalah resolusi. Masalah dengan Transformasi Fourier Waktu Singkat berkaitan dengan penentuan lebar fungsi jendela yang digunakan. Pada transformasi Fourier kita tahu pasti frekuensi apa yang eksis, yang artinya transformasi Fourier memiliki resolusi yang sempurna. Yang memberikan resolusi sempurna pada transformasi ini adalah fakta bahwa fungsi jendela yang digunakan adalah fungsi transformasinya sendiri, yang lebarnya memanjang dari minus tidak berhingga hingga tidak berhingga. Pada Transformasi Fourier Waktu Singkat, lebar fungsi jendela yang digunakan terbatas, sehingga hanya mencakup sebagian sinyal, yang menyebabkan resolusi frekuensinya kurang baik. Yang dimaksud kurang baik di sini adalah kita tidak lagi tahu secara pasti komponen frekuensi apa yang ada pada sinyal, tetapi kita hanya tahu rentang frekuensi yang ada. Singkatnya, masalah yang dihadapi Transformasi Fourier Waktu Singkat adalah dilema dalam penentuan lebar fungsi jendela. Lebar fungsi jendela yang sempit menghasilkan resolusi waktu yang baik tetapi resolusi frekuensinya buruk. Sedangkan fungsi jendela yang lebar menghasilkan resolusi frekuensi yang baik tetapi resolusi waktu yang buruk.
24
2.3.3
Transformasi Wavelet
Transformasi wavelet adalah proses transformasi (dekomposisi) suatu sinyal ke dalam bentuk superposisi dari fungsi wavelet, yang merupakan hasil dilasi dan translasi fungsi tunggal wavelet induk. Transformasi wavelet dapat dipandang sebagai bentuk representasi waktu-frekuensi untuk sinyal yang kontinu terhadap waktu (sinyal analog). Transformasi wavelet memiliki keunggulan dibanding dengan transformasi Fourier untuk merepresentasikan fungsi yang memiliki diskontinuitas dan kenaikan atau penurunan yang tajam, dan untuk secara akurat mendekomposisi dan merekonstruksi sinyal non-periodik dan/atau sinyal non-stasioner. Secara singkat, dalam transformasi wavelet, sebuah sinyal dilewatkan pada filter lolos tinggi dan filter lolos rendah, yang menyaring bagian berfrekuensi tinggi dan rendah dari sinyal. Prosedur ini diulang-ulang, dan setiap kalinya beberapa bagian dari sinyal yang berkorespondensi dengan frekuensi tertentu dihilangkan dari sinyal. Operasi demikian disebut juga dekomposisi. Transformasi wavelet dikembangkan sebagai pendekatan alternatif atas Transformasi Fourier Waktu Singkat untuk mengatasi masalah resolusi. Analisa wavelet dilakukan dengan cara yang mirip seperti analisa Transformasi Fourier Waktu Singkat, dalam artian sinyal dikalikan dengan sebuah fungsi (wavelet), yang mirip dengan fungsi jendela pada Transformasi Fourier Waktu Singkat, dan transformasinya dihitung secara terpisah untuk tiap-tiap segmen yang berbeda dari sinyal domain waktu (ruang). Tetapi ada dua perbedaan mendasar antara transformasi wavelet dengan Transformasi Fourier Waktu Singkat, yaitu :
25
a.
Transformasi Fourier dari sinyal yang telah dilewatkan oleh fungsi jendela tidak dihitung.
b.
Lebar dari fungsi jendela berubah untuk setiap perhitungan transformasi atas setiap komponen spektral, yang merupakan karakteristik utama transformasi wavelet. Tidak seperti Transformasi Fourier Waktu Singkat yang resolusinya konstan
pada setiap waktu dan frekuensi karena konstannya fungsi jendela, transformasi wavelet memiliki resolusi yang berbeda-beda karena fungsi jendela yang digunakan adalah fungsi-fungsi wavelet anak yang berbeda-beda, yang merupakan hasil turunan dari satu wavelet induk. Transformasi wavelet memiliki resolusi waktu yang baik dan resolusi frekuensi yang buruk pada frekuensi tinggi, dan resolusi frekuensi yang baik dan resolusi waktu yang buruk pada frekuensi rendah. Transformasi wavelet dibagi menjadi 2 bagian besar, yaitu : a. Transformasi wavelet kontinu b. Transformasi wavelet diskrit
2.3.3.1 Transformasi Wavelet Kontinu
Dalam transformasi wavelet kontinu, fungsi-fungsi basis wavelet memiliki parameter geser dan parameter skala yang kontinu. Cara kerja transformasi wavelet kontinu (TWK) adalah dengan menghitung konvolusi sebuah sinyal dengan sebuah jendela modulasi pada setiap waktu dengan setiap skala yang diinginkan. Jendela modulasi yang mempunyai skala fleksibel inilah yang biasa disebut induk wavelet atau fungsi dasar wavelet.
26
Dalam transformasi wavelet digunakan istilah translasi dan skala, karena istilah waktu dan frekuensi sudah digunakan oleh transformasi Fourier. Translasi adalah lokasi jendela modulasi saat digeser sepanjang sinyal, berhubungan dengan informasi waktu. Skala behubungan dengan frekuensi, skala tinggi (frekuensi rendah) berhubungan dengan informasi global dari sebuah sinyal, sedangkan skala rendah (frekuensi tinggi) berhubungan dengan informasi detil. TWK secara matematika dapat didefinisikan sebagai berikut:
γ ( s ,τ ) =
∫
f ( t )ϕ s* ,τ ( t ) dt
Keterangan: γ(s,τ) adalah fungsi sinyal setelah transformasi, dengan variabel s (skala) dan τ (translasi) sebagai dimensi baru. f(t) adalah sinyal asli sebelum transformasi. Fungsi dasar
disebut sebagai wavelet, dengan * menunjukkan
konjugasi kompleks. Dan inversi dari TWK secara matematika dapat didefinisikan sebagai berikut:
f (t ) =
∫∫ γ ( s , τ )ϕ
s ,τ
( t ) d τ ds
Seperti telah dibicarakan sebelumnya, fungsi dasar wavelet ψs,τ(t) dapat didesain sesuai kebutuhan untuk mendapatkan hasil transformasi yang terbaik, ini perbedaan mendasar dengan transformasi Fourier yang hanya menggunakan fungsi sinus sebagai jendela modulasi. Fungsi dasar wavelet secara matematika dapat didefinisikan sebagi berikut:
ϕ
s ,τ
(t) =
1 ⎛ t −τ ⎞ ϕ⎜ ⎟ s ⎝ s ⎠
27
Faktor 1 digunakan untuk normalisasi energi pada skala yang berubah-ubah. s
Mexican Hat, yang merupakan normalisasi dari derivatif kedua fungsi Gaussian adalah salah satu contoh fungsi dasar TWK: 2
−t ⎛ t2 ⎞ 2σ 2 ⎜1 − 2 ⎟e ϕ (t ) = 2π σ 3 ⎜⎝ σ ⎟⎠
1
Contoh lain adalah fungsi dasar Morlet, yang merupakan fungsi bilangan kompleks:
ϕ σ (t ) = c σ π
−
1 4
e
−
1 2
(
t 2 e iσ t − κ σ
)
dengan
κσ = e
−
1 σ 2
2
dan c σ
3 − σ 2 ⎛ 2 −σ = ⎜⎜ 1 + e − 2e 4 ⎝
⎞ ⎟ ⎟ ⎠
−
1 2
2.3.3.2 Transformasi Wavelet Diskrit
Transformasi wavelet diskrit (TWD) merupakan salah satu cara yang banyak digunakan dalam upaya meningkatkan efisiensi dan kecepatan dalam menggunakan PCA dalam domain frekuensi. Dasar dari TWD dimulai pada tahun 1976, dimana tehnik untuk mendekomposisi sinyal waktu ditemukan. Dalam TWD, penggambaran sebuah skala waktu sinyal digital didapatkan dengan menggunakan tehnik filterisasi digital. Secara garis besar proses dalam tehnik ini adalah dengan melewatkan sinyal yang akan dianalisis pada filter dengan frekuensi dan skala yang berbeda. Filterisasi merupakan sebuah fungsi yang digunakan dalam pemrosesan sinyal. Wavelet dapat direalisasikan menggunakan iterasi filter dengan pengskalaan. Resolusi dari sinyal, yang
28
merupakan rata-rata dari jumlah detil informasi dari sinyal, ditentukan melalui filterisasi ini dan skalanya didapatkan dengan unsampling dan down sampling (subsampling). Sebuah sinyal harus dilewatkan dalam dua filterisasi TWD yaitu highpass filter dan lowpass filter agar frekuensi dari sinyal tersebut dapat dianalisis. Pasangan filter high-pass dan low-pass yang digunakan harus merupakan Quadrature Mirror Filter (QMF), yaitu pasangan filter yang memenuhi persamaan berikut:
h[L − 1 − n] = (− 1) .g [n] n
dengan h[n] adalah filtar high-pass, g[n] adalah filter low-pass dan L adalah panjang masing-masing filter. Analisis terhadap frekuensi dilakukan dengan cara menggunakan resolusi yang dihasilkan setelah sinyal melewati filterisasi. Pembagian sinyal menjadi frekuensi tinggi dan frekuensi rendah dalam proses filterisasi highpass filter dan lowpass filter disebut sebagai dekomposisi. Proses dekomposisi dimulai dengan melewatkan sinyal asal melewati highpass filter dan lowpass filter. Misalkan sinyal asal ini memiliki rentang frekuensi dari 0 sampai dengan π rad/s. Dalam melewati highpass filter dan lowpass filter ini, rentang frekuensi di sub sample menjadi dua, sehingga rentang frekuensi tertinggi pada masing-masing sub sample menjadi π/2 rad/s. Setelah filterisasi, setengah dari sample atau salah satu sub sample dapat dieliminasi berdasarkan aturan Nyquist (Terzija, 2006). Sehingga sinyal dapat selalu di-subsample oleh 2 (↓2) dengan cara mengabaikan setiap sample yang kedua. Proses dekomposisi ini dapat melalui salah satu atau lebih tingkatan. Dekomposisi satu tingkat ditulis dengan ekspresi matematika pada persamaan berikut :
29
ytinggi [k ] = ∑ x[n ]g [2k − n ] n
yrendah [k ] = ∑ x[n ]g[2 k − n] n
y[k] tinggi dan y[k] rendah adalah hasil dari highpass filter dan lowpass filter, x[n] merupakan signal asal, h[n] adalah highpass filter dan g[n] adalah lowpass filter. Untuk dekomposisi lebih dari satu tingkat, prosedur di atas dapat digunakan pada masingmasing tingkatan. Contoh penggambaran dekomposisi dipaparkan pada Gambar 2.4 dengan menggunakan dekomposisi tiga tingkat.
Gambar 2.3 Dekomposisi Wavelet Tiga Tingkat Sumber : (Sripathi, 2003) y[k] tinggi dan y[k] rendah adalah hasil dari highpass filter dan lowpass filter, y[k] tinggi disebut sebagai koefisien TWD. y[k] tinggi merupakan detil dari informasi sinyal, sedangkan y[k] rendah merupakan taksiran kasar dari fungsi penskalaan. Dengan menggunakan koefisien TWD ini maka dapat dilakukan proses invers TWD untuk merekonstruksi menjadi signal asal. Persamaan rekonstruksi pada masing-masing tingkatan dapat ditulis sebagai berikut :
x[n] = ∑ ( y tinggi [k ]h[− n + 2k ] + yrendah [k ]g [− n + 2k ]) k
30
Dekomposisi pada citra menghasilkan informasi rentang frekuensi yang berbeda yaitu LL, frekuensi rendah-rendah (low-low frequency), LH, frekuensi rendah-tinggi (low-high frequency), HL, frekuensi tinggi-rendah (high-low frequency), dah HH, frekuensi tinggi-tinggi (high-high frequency). Rentang frekuensi LL merupakan rentang taksiran penskalaan, sedangkan rentang frekuensi LH, HL dan HH merupakan rentang frekuensi detil informasi.
Gambar 2.4 Skala 2-Dimensi Transformasi Wavelet Diskrit Sumber : Chan Pik-Wah (Digital Video Watermarking Techniques for Secure Multimedia Creation and Delivery, The Chinese University of Hongkong, 2004)
Transformasi Wavelet Diskrit ini sering dipilih karena beberapa alasan, yaitu : •
TWD merupakan yang paling dekat dengan HVS (Human Visual System).
•
Distorsi yang disebabkan oleh domain wavelet dalam perbandingan kompresi tinggi tidak terlalu mengganggu dibandingkan domain lain dalam bit rate yang sama.
•
Bit-error rate yang rendah. Bit-error rate merupakan perbandingan antara bit yang salah diekstraksi dengan total bit yang disisipkan.
31
Pada transformasi wavelet diskrit, parameter geser dan skalanya bersifat diskrit. Dibandingkan dengan TWK, transformasi wavelet diskrit (TWD) dianggap relatif lebih mudah pengimplementasiannya. Berkat operasi sub-sampling yang menghilangkan informasi sinyal yang berlebihan, transformasi wavelet telah menjadi salah satu metode kompresi data yang paling handal. Biro Investigasi Federal (FBI) Amerika Serikat menggunakan metode ini dalam proses kompresi data sidik jari mereka.
2.3.3.3 Dual Tree Complex Wavelet Transfrom (DTCWT)
Transformasi complex wavelet (CWT) adalah sebuah perluasan nilai variabel kompleks dari transformasi wavelet diskrit (TWD) standar. Transformasi wavelet complex dalam sebuah signal menggunakan dua pohon yang terpisah dari filter riil TWD di mana operasinya secara pararel untuk menghasilkan bagian riil dan imajiner dari filter kompleks. Hal itu berarti bahwa jumlah dari koefisien pada output pada CWT adalah dua kali lipat dibandingkan dengan jumlah dari koefisien TWD. Penggandaan dari CWT adalah 2:1 untuk signal satu dimensi dan 4:1 untuk sinyal dua dimensi. TWD memiliki beberapa kekurangan yaitu pada shift invariance, yang berarti bahwa pergeseran kecil dalam signal inputan dapat menyebabkan variasi yang besar dalam distribusi energy antara koefisien transformasi wavelet pada skala yang berbeda. Masalah ini disebabkan oleh aliasing yang dilakukan karena subsampling pada setiap level wavelet. Kekurangan yang lainnya adalah buruk dalam directional selectivity untuk feature diagonal. TWD dua dimensi mendekomposisi gambar dengan arah horizontal
32
(00), HL, vertikal (900) atau LH dan diagonal (±450) atau HH. TWD tidak dapat membedakan antara dua arah diagonal yang berlawanan (±750). Tahun 1998, Kingsbury (Kingsbury, 1998) telah menemukan transformasi yang berbasis Complex-Wavelet (CWT) yaitu dual tree complex wavelet transform (DTCWT) yang memiliki beberapa kelebihan yaitu : • Bagus dalam shift invariance. • Bagus dalam directional selectivity. • Memiliki redundansi yang sangat sedikit (2:1 m untuk m-dimensi signal). • Memiliki algoritma perhitungan yang sedikit. Transformasi adalah sebuah variasi dari implementasi TWD, tetapi perbedaan utamanya yaitu bahwa DTCWT menggunakan dua filter tree seperti yang ditunjukkan oleh gambar 2.6 (Corio et al, 2007)
Gambar 2.5 Struktur 2 Filter Tree DT CWT Sumber : Corio et al (2007)
33
2.4
Evaluasi Kualitas Retrival
Suatu metode retrival dikatakan berhasil jika mengandung kesalahan sesedikit mungkin. Tingkat kesalahan dilihat dari akurasi retrival yang diihitung dengan cara : akurasi=
citra yangberhasi di retriva x 100% jumlahcitra output
Selain akurasi, retrival juga harus bersifat reliable, artinya nilai akurasi yang diberikan sama untuk setiap kasus. Dalam percobaan ini, citra dibagi dalam beberapa kelompok yang berisi n-citra. Setiap kelompok dilakukan retrival dan dihitung akurasi per-kelompoknya. Foto 1 2 3 4 5
1 R R R R R
2 T R R T R
3 4 R R T R R R R T T T Tabel 2.1
5 Akurasi R : citra yang relevan R 20 % R 80 % T : citra yang tidak relevan R 100 % T 40 % R 60 % Contoh urutan hasil retrival
Misalkan setiap kelompok terdiri dari 5 citra, maka nilai reliabilitas dihitung sebagai berikut : Kelompok Akurasi 1 60 % 2 80 % 3 60 % 4 40 % 5 60 % Rata-rata akurasi : 60 % Tabel 2.2 Contoh perhitungan akurasi Tingkat reliabilitas dikatakan tinggi jika tiap kelompok menunjukkan tingkat akurasi yang kurang lebih sama. Semakin dekat atau semakin kecil jarak akurasi satu kelompok dengan kelompok lainnya, semakin tinggi nilai reliabilitasnya.
34
Reliabilitas menunjukkan tingkat konsistensi metode retrival, tetapi tidak menjamin keakuratannya. Misalnya, akurasi pada lima kelompok menunjukkan angka 40 %, nilai reliabilitasnya dikatakan tinggi, tetapi nilai akurasinya rendah, sehingga dibutuhkan keakuratan yang baik sekaligus reliabilitas tinggi untuk mendapatkan nilai yang valid.
