MODUL TEORI
PENGOLAHAN CITRA Penyusun : Abdul Jabbar Lubis, ST, M.Kom
PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TINGGI TEKNIK HARAPAN MEDAN 2013
PENGANTAR PENGOLAHAN CITRA
Visi Komputer Visi komputer merupakan ilmu yang dideskripsikan sebagai gambar yang diolah, diproduksi oleh kamera dan dianalisis oleh komputer. Kamera dan komputer menyajikan mesin yang setara dengan kemampuan visual manusia, seperti melihat, berpikir, dan merespon. Computer Vision mempunyai tujuan utama untuk menganalisa obyek fisik yang nyata berdasarkan image yang ditangkap dari sensor. Visi komputer diciptakan untuk membangun sebuah mesin pandai yang dapat melihat, berikut merupakan prosesnya meliputi preprocessing dan proses recognition atau pengenalan pola. Tahapan Preprocessing meliputi : Pengolahan Citra Citra adalah gambar pada bidang dwimatra (dua dimensi). Ditinjau dari sudut pandang matematis, citra merupakan fungsi menerus (countinue) dari intensitas cahaya pada bidang dwimatra. Sumber cahaya menerangi objek, objek memantulkan kembali sebagian dari berkas cahaya tersebut. Pantulan cahaya ini ditangkap oleh alat-alat optik, misalnya mata pada manusia, kamera, pemindai (scanner), dan sebagainya, sehingga bayangan objek yang disebut citra terekam. Meskipun sebuah citra kaya informasi, namun seringkali citra yang kita miliki mengalami penurunan mutu (degradasi), misalnya mengandung cacat atau derau (noise), warnanya terlalu kontras, kurang tajam, kabur (blurring), dan sebagainya. Citra yang seperti ini tentu saja menjadi lebih sulit diinterpretasi karena informasi yang disampaikan oleh citra tersebut menjadi berkurang.
1
Agar citra yang mengalami gangguan mudah diinterpretasi (baik oleh manusia maupun mesin), maka citra tersebut perlu dimanipulasi menjadi citra lain yang kualitasnya lebih baik. Bidang studi yang menyangkut hal ini adalah Pengolahan Citra (Image Processing). Pengolahan Citra adalah suatu metode yang digunakan untuk memproses atau memanipulasi image dalam 2 dimensi, segala operasi untuk memperbaiki, penganalisaan, dan pengubahan suatu gambar disebut pengolahan citra. Konsep dasar pemrosesan suatu obyek yang menggunakan pengolahan citra. Diambil dari kemampuan indera penglihatan manusia yang selanjutnya dihubungkan dengan kemampuan otak manusia. Dalam sejarahnya, pengolahan citra telah di aplikasikan dalam berbagai bentuk, dengan tingkat kesuksesan yang cukup besar, seperti berbagai cabang ilmu lainnya, pengolahan citra. Menyangkut pula berbagai gabungan cabang – cabang ilmu, diantaranya optik, elektronik, matematika, fotografi, dan teknologi komputer. Beberapa faktor menyebabkan perkembangan sistem pengolahan citra menjadi lebih berkembang pesat pada saat ini. Salah satu yang utama adalah dibutuhkannya suatu teknologi yang dapat bekerja secara mandiri dalam arti teknologi yang dapat memproses data – data yang diterima dan pada akhirnya teknologi tersebut dapat mengambil keputusan sendiri dari hasil pengolahan data sebelumnya. Selain itu penurunan biaya akan peralatan komputer yang dibutuhkan serta peningkatan tersedianya peralatan untuk proses tampilan gambar juga menjadi salah satu faktor semakin berkembangnya pengolahan citra. Pada umumnya, objektif dari pengolahan citra adalah mentransformasikan atau menganalisis suatu gambar sehingga informasi baru tentang gambar di buat lebih jelas.
2
Ada 4 klasifikasi dasar dalam pengolahan citra., yaitu: berbasis point, berbasis area, berbasis geometric, dan berbasis frame. ¾ Berbasis Point / berbasis piksel yaitu, memproses nilai piksel image berdasarkan nilai atau posisi dari piksel tersebut. Contoh dari proses point adalah adding, subtracting, contrast, stretching, dan lainnya. ¾ Berbasis Area yaitu memproses nilai piksel – piksel suatu image berdasarkan nilai piksel tersebut beserta nilai piksel
tetangga – tetangga (area
sekelilingnya). Contoh dari proses area adalah convolution, blurring, sharpening, filtering dan lainnya. ¾ Berbasis Geometric digunakan untuk merubah posisi dari pixel – pixel. Contoh dari proses geometric adalah scalling, rotation, mirroring, dan lainnya. ¾ Berbasis Frame yaitu memproses nilai pixel berdasarkan operasi dari 2 (dua) buah image atau lebih. Contoh dari proses frame adalah addition, subtraction, and/or, dan lainnya. Perbedaan proses frame disini dengan proses point yaitu pada proses point nilai – nilai pixelnya di proses (ditambahkan, dikurangkan, dan lainnya)
dengan suatu nilai tertentu, sedangkan pada proses frame
pemrosesan nilai-nilai pixelnya dilakukan antara dua image. Operasi-operasi pada pengolahan citra diterapkan pada citra bila : 1. Perbaikan atau memodifikasi citra perlu dilakukan untuk meningkatkan kualitas penampakan atau untuk menonjolkan beberapa aspek informasi yang terkandung di dalam citra 2. Elemen di dalam citra perlu dikelompokkan, dicocokkan, atau diukur 3. Sebagian citra perlu digabung dengan bagian citra yang lain Pengolahan citra bertujuan memperbaiki kualitas citra agar mudah diinterpretasi oleh manusia atau mesin (dalam hal ini komputer). Teknik-teknik
3
pengolahan citra mentransformasikan citra mejadi citra lain. Jadi, masukannya adalah citra dan keluarannya juga citra.
Pengolahan
CITRA
CITRA
Citra Gambar Input dan Output untuk proses Pengolahan Citra Pengubahan citra pada gambar 2.2 adalah contoh operasi pengolahan citra. Contoh operasi pengolahan citra lainnya adalah penghilangan derau (noise) pada citra lena (gambar 2.3). Citra lena yang disebelah kiri mengandung derau berupa bintik-bintik putih (derau). Dengan operasi penapisan (filtering) derau pada citra masukan ini dapat dikurangi sehingga dihasilkan citra yang kualitasnya lebih baik.
(a)
(b)
Gambar (a) Citra Burung Nuri yang agak gelap, (b) Citra burung yang telah diperbaiki kontrasnya sehingga terlihat jelas dan tajam
4
(a)
(b)
Gambar 2.3 Citra Lena yang mengandung derau, (b) hasil dari operasi penapisan derau (filtering)
Visi Komputer dan Hubungannya Dengan Pengolahan Citra Terminologi lain yang berkaitan erat dengan pengolahan citra adalah visi komputer atau machine vision. Pada hakikatnya, visi komputer mencoba meniru cara kerja sistem visi manusia (human vision). Visi manusia sesungguhnya sangat kompleks. Manusia melihat objek dengan indera penglihatan (mata), lalu citra objek diteruskan ke otak untuk diinterpretasi sehingga manusia mengerti objek apa yang tampak dalam pandangan matanya. Hasil interpretasi ini mungkin digunakan untuk pengambilan keputusan (misalnya menghindar kalau melihat mobil melaju di depan). Visi komputer merupakan proses otomatis yang mengintegrasikan sejumlah besar proses untuk persepsi visual, seperti akuisisi citra, pengolahan citra, klasifikasi, pengenalan (recognition), dan membuat keputusan.
5
Visi komputer terdiri dari teknik-teknik untuk mengestimasi ciri- ciri objek di dalam citra, pengukuran ciri yang berkaitan dengan geometri objek, dan menginterpretasi informasi geometri tersebut. Proses – proses di dalam visi komputer dapat dibagi menjadi tiga aktivitas: 1. Memperoleh atau mengakuisisi citra dijital. 2. Melakukan teknik komputasi untuk memproses atau memodifikasi data citra (operasi – operasi pengolahan citra). 3. Menganalisis dan menginterpretasi citra dan menggunakan hasil pemrosesan untuk tujuan tertentu, misalnya memandu robot, mengontrol peralatan, memantau proses manufaktur, dan lain -lain.
Mengklasifikasikan proses-proses didalam visi komputer didalam hirarki sebagai berikut: Hirarki Pemrosesan
Contoh Algoritma
Preprocessing
Noise removal Contrast enhancement
Lowest-level feature extraction
Edge detection Texture detection
Intermediate-level feature identification
connectivity Pattern matching Boundary coding
High-level scene interpretation via images
Model Base Recognition
6
Dari penjelasan di atas, dapat kita lihat bahwa pengolahan citra dan pengenalan pola merupakan bagian dari visi komputer. Pengolahan citra merupakan proses awal (preprocessing) pada visi komputer, sedangkan pengenalan pola merupakan proses untuk menginterpretasi citra. Teknik-teknik di dalam pengenalan pola memainkan peranan penting dalam visi komputer untuk mengenali objek. Citra dijital Citra dijital memiliki informasi berupa gambar dan terdiri dari elemen terkecil yaitu piksel. Citra dijital direpresentasikan dalam bentuk matriks 2 dimensi yang setiap elemen merepresentasikan piksel pada gambar. Warna pada Citra Dijital Semua warna yang ada merupakan perpaduan dari 3 macam warna primer yaitu : -
Warna merah
-
Warna hijau
-
Warna biru Perpaduan dari ketiga warna primer ini dipakai pada
sistem warna RGB. Bila ketiga warna primer dicampur, maka akan dihasilkan suatu warna tertentu, tergantung dari komposisi ketiga warna primer tersebut. Gambar pada sistem dijital dapat diwakili dengan format RGB untuk setiap titiknya, dimana setiap komponen R, G, dan B mempunyai variasi dari 0 sampai 255. Total variasi yang dihasilkan untuk sistem warna dijital ini adalah 256 x 256 x 256 atau 16.777.216 jenis warna. Karena setiap warna diwakili dengan satu byte atau delapan bit, maka total bit yang digunakan untuk merepresentasikan warna RGB adalah 8 + 8 + 8 atau 24 bit.
7
Kalkulasi pemrosesan
gambar dengan sistem RGB
sangatlah memboroskan memory dan juga waktu. Untuk itu diperlukan reduksi warna. Dalam pemrosesan gambar terutama pengenalan obyek, sistem RGB sendiri tidaklah memberikan respon yang baik, sehingga digunakan sistem format grayscale atau gray level, dimana format gambar warna di konversi menjadi format gambar abu-abu. Sistem grayscale memerlukan 1 byte (delapan bit) untuk penyimpanan data, mempunyai kemungkinan warna dari 0 (hitam) sampai 255 (putih) Cara konversi dari sistem warna RGB menjadi grayscale ini ada beberapa macam: ¾
Dengan merata-rata setiap komponen warna pada RGB GRAY = ( R+G+B) 3
¾
Menggunakan nilai maksimal dari komponen RGB GRAY MAX {R, G, B}
Citra akan di konversi menjadi citra grayscale (Grayscaling) Citra yang di masukkan akan diproses menjadi citra grayscale, dengan cara diambil nilai R, G, B dari masing – masing pixel dari citra atau dengan merata – rata setiap komponen warna pada RGB. Perhitungan untuk mendapatkan nilai grayscale untuk masing – masing pixel adalah : grayscale = R ¾
1 1 1 +G + B 30 59 11
Menggunakan sistem YUV (sistem warna pada NTSC),
yaitu dengan
cara
mengambil
komponen
Y
(iluminasi).
8
Komponen Y sendiri dapat diperoleh dari sistem warna RGB dengan konversi (Wikipedia, diakses Mei 2009). GRAY = Y = 0,299 * R + 0,587 * G + 0,114 * B Cara yang paling terakhir ini yang paling sering digunakan untuk konversi sistem warna ke sistem grayscale. Warna hitam - putih Kompleksitas gambar biner dibatasi oleh nilai threshold. Untuk mendapatkan warna hitam – putih dalam suatu image diperlukan proses thresholding. Proses thresholding digunakan untuk mengubah nilai piksel bergantung pada besar kecilnya nilai piksel tersebut terhadap nilai threshold
yang telah ditentukan.
Jika suatu nilai piksel lebih besar atau sama dengan nilai threshold maka piksel tersebut akan di-set ke nilai maksimum, dalam grayscale nilai piksel maksimum adalah 255 (warna putih). Sedangkan bila suatu nilai piksel kurang dari nilai threshold maka piksel tersebut akan di-set ke nilai minimum, dalam grayscale nilai piksel minimum adalah 0 (warna hitam) untuk mencari nilai thresholding yaitu digunakan metode otsu algorithm. ¾
Otsu Threshold algorithm
Metode Otsu (Otsu, 1979) adalah metode yang paling populer diantara semua metode thresholding yang ada. Teknik Otsu ini memaksimalkan kecocokan dari sebuah threshold sehingga dapat memisahkan objek dengan
latar belakangnya. Semua ini
didapatkan dengan memilih nilai threshold yang memberikan pembagian kelas yang terbaik untuk semua piksel yang ada didalam image. Dasarnya adalah dengan menggunakan histogram yang telah dinormalisasi dimana jumlah tiap poin pada setiap level dibagi dengan jumlah total poin pada image.
9
Thinning dan Cropping Thinning adalah suatu proses untuk membuat garis pada sebuah gambar menjadi bentuk yang lebih sederhana. Dengan melakukan proses thinning maka garis – garis yang ada pada gambar akan memiliki ketebalan 1 piksel, proses thinning ini berguna pada saat huruf akan di training maupun di recognize karena akan menghasilkan fitur yang lebih baik (Petra Christian University Library). Tujuan dari thinning adalah menghilangkan piksel tertentu pada objek sehingga tebal objek tersebut menjadi hanya satu piksel. Thinning tidak boleh : ¾ Menghilangkan end-point ¾ Memutuskan koneksi yang ada ¾ Mengakibatkan excessive erosi Salah satu kegunaan thinning adalah pada proses pengenalan karakter / huruf, ada banyak cara mengimplementasikan thinning salah satu diantaranya adalah dengan hit-or-miss transform. Thinning dapat didefinisikan sebagai: Thinning(A,{B}) = A – (A * {B}) = A – ((...(A*B1)*B2)..Bn) Dengan B1, B2, B3..Bn adalah A-(A*B) berarti kebalikan dari A*B Thinning pada pengolahan citra biasanya diaplikasikan pada citra biner, terdapat cukup banyak algoritma untuk image thinning dengan tingkat kompleksitas, efisiensi dan akurasi yang berbeda – beda. Berikut merupakan algoritma thinning yang cukup populer yaitu algoritma zhang suen. Algoritma zhang suen digunakan sebagai suatu basis untuk perbandingan thinning, setiap iterasi dari metode ini terdiri dari dua subiterasi yang berurutan yang dilakukan terhadap contour point dari wilayah
10
citra. Contour point adalah setiap piksel dengan nilai 1 dan memiliki setidaknya satu 8-neighbor dengan nilai 0. Langkah langkah algoritma zhang suen : 1. Menandai contour point p untuk dihapus jika semua kondisi ini dipenuhi (a) 2 ≤ N(p1) ≤ 6; (b) S(p1) = 1; (c) p2 . p4 . p6 = 0; (d) p4 . p6 . p8 = 0; Dimana N(p1) adalah jumlah tetangga dari p1 yang tidak 0 yaitu: N(p1) = p2 + p3 + ... + p8 + p9 P9
P2
P3
P8
P1
P4
P7
P6
P5
Dan S(p1) adalah jumlah dari transisi 0-1 pada urutan p2,p3,....,p8,p9. 2. Kondisi (a) dan (b) sama dengan langkah pertama, sedangkan kondisi (c) dan (d) diubah menjadi : (c’) p2.p4.p8 = 0; (d’) p2.p6.p8 = 0; Langkah pertama dilakukan terhadap semua border piksel di citra. Jika salah satu dari keempat kondisi di atas tidak dipenuhi atau dilanggar maka nilai piksel yang bersangkutan tidak diubah. Sebaliknya jika semua kondisi tersebut dipenuhi maka piksel tersebut ditandai untuk penghapusan. Piksel yang ditandai tidak dihapus sebelum semua border point selesai diproses, setelah langkah 1 selesai dilakukan untuk semua border point maka dilakukan penghapusan untuk titik yang telah ditandai (diubah menjadi 0). Setelah dilakukan langkah 2 pada data
11
hasil dari langkah 1 dengan cara yang sama dengan langkah 1, sehingga dalam satu kali iterasi urutan algoritma nya terdiri dari : (1) Menjalankan langkah 1 untuk menandai border point yang akan di hapus (2) Hapus titik - titik yang ditandai dengan menggantinya mejadi angka 0 (3) Menjalankan langkah 2 pada sisa border points yang pada langkah 1 belum dihapus lalu yang sesuai dengan semua kondisi yang seharusnya di penuhi
pada langkah 2 kemudian ditandai untuk
dihapus. (4) Hapus titik-titik yang ditandai dengan menggantinya menjadi angka 0. Prosedur ini dilakukan secara iteratif sampai tidak lagi titik yang dapat dihapus. Pada saat algoritma ini selesai maka dihasilkan skeleton dari citra awal. Kelebihan zhang suen : •
Algoritma sederhana
•
Dalam pemrosesan termasuk cepat (untuk memperoleh hasil)
Dalam proses cropping dilakukan, hanya untuk mendapatkan informasi yang penting atau yang nantinya akan digunakan seperlunya dari dalam citra. Metode yang dilakukan adalah dengan menghilangkan space kosong (berwarna putih) yang tidak terpakai di dalam citra.
Segmentasi (Segmentation) Dalam visi komputer, segmentasi berarti proses membagi citra dijital
menjadi
banyak
segmen.
Tujuan
dari
segmentasi
adalah
menyederhanakan dan/atau mengubah representasi dari citra menjadi sesuatu yang lebih berarti dan mudah untuk dianalisa. Segmentasi citra
12
biasanya digunakan untuk mencari lokasi objek dan batas bidang dalam citra. Ada banyak metode – metode segmentasi, beberapa diantaranya adalah : • Metode Clustering Algoritma dasarnya adalah : a. Ambil K pusat cluster, secara acak atau dengan pendekatan heuristic b. Tetapkan masing – masing piksel dalam citra ke dalam cluster yang akan meminimalkan variasi antara piksel dan pusat cluster c. Menghitung ulang pusat – pusat cluster dengan merata – ratakan semua piksel dalam cluster d. Ulangi tahap b dan c sampai tercapai konvergen • Metode Berbasis-Histogram Metode berbasis histogram sangat efisien jika dibandingkan dengan metode segmentasi citra yang lain karena biasanya hanya membutuhkan satu kali melewati piksel. Dalam teknik ini, histogram dihitung dari seluruh piksel dalam citra, dan puncak serta lembah di dalam histogram digunakan untuk mencari cluster dalam citra. Pengembangan dari teknik ini adalah secara rekursif melakukan metode pencarian secara histogram di dalam citra untuk membagi mereka menjadi cluster yang lebih kecil. Ini dilakukan terus – menerus dengan cluster yang lebih kecil hingga tidak ada lagi cluster yang terbuat. • Metode Deteksi Sisi • Metode Pengembangan Daerah
Pengenalan Pola Pengenalan pola merupakan salah satu bidang dalam komputer sains, yang memetakan suatu data ke dalam konsep tertentu yang telah didefinisikan sebelumnya. Konsep tertentu ini disebut kelas atau kategori. Proses pemetaan ini
13
menyangkut inferensi, baik secara eksplisit secara statistik (misalnya dalam aturan bayesian) maupun tak eksplisit dengan suatu jaringan keputusan (misalnya jaringan saraf tiruan atau logika samar). Pengenalan pola memainkan peranan penting dalam berbagai bidang rekayasa salah satunya dalam tugas akhir ini penulis melakukan pengenalan tulisan tangan yang nantinya menggunakan metode jaringan saraf tiruan atau tak eksplisit yang dibandingkan dengan SVM, adapun metode statistik (StatPR) dan metode sintaktik. Dalam metode jaringan syaraf tiruan (NeuroPR), pemilahan dilakukan berdasarkan tanggapan suatu neuron jaringan pengolah sinyal (neuron) terhadap stimulus masukan (pola). Pengetahuan disimpan dalam sambungan antar neuron dan kekuatan sinaptik, NeuroPR dapat dilatih, non-algoritmik, dan memakai strategi Black Box, NeuroPR sangat menarik karena : ¾
Pengetahuan apriori yang diperlukan hanya sedikit
¾
Dengan jumlah lapisan dan neuron secukupnya, JST dapat membentuk semua jenis daerah keputusan yang rumit sekalipun Secara mendasar, suatu sistem pengenalan pola terdiri dari komponen-
komponen berikut: sensor, mekanisme pre-processing, mekanisme pencari fitur (manual/otomatis), algoritma pemilih dan sekumpulan contoh pelatihan yang telah dipilih. ¾
Sensor, berfungsi untuk menangkap objek dari dunia nyata menjadi sinyalsinyal listrik (dan selanjutnya dalam bilangan-bilangan setelah proses dijitasi)
¾
Preprocessing, berfungsi untuk menonjolkan sinyal informasi dan menekan derau dalam sinyal
¾
Pencari fitur, mengambil peranan komponen tertentu dari sinyal yang mewakili sifat utama sinyal, sekaligus mengurangi dimensi sinyal mejadi sekumpulan bilangan yang lebih sedikit tetapi representatif
¾
Algoritma pemilah, melakukan assignment fitur ke kelas yang sesuai
14
¾
Sekumpulan contoh pelatihan, dipakai untuk mendapatkan representasi kelas Pembuatan suatu sistem pengenal pola yang baik mengikuti beberapa
tahap, dimulai dari pengumpulan data, pemilihan fitur, pemilihan teknik pemilah atau model yang sesuai, pelatihan dan pengujian. ¾
Pengumpulan data, bagian paling intensif dalam proyek pengenalan pola
¾
Pemilihan fitur, bagian paling kritis dari keberhasilan sistem PR (Probabilistic Reasoning)
¾
Pemilihan model, memilih model pengenal yang sesuai apakah dengan pendekatan statistik, neural dan struktural.
¾
Pelatihan, diberikan kumpulan fitur dan model kosong, adaptasikan untuk menjelaskan data apakah dengan supervised atau unsupervised
¾
Pengujian, mengevaluasi seberapa bagus kinerja dari model yang sudah dilatih. Setelah melalui tahap preprocessing, Ada dua jenis proses recognition
yang digunakan, yaitu proses image correlation dan proses feature extraction. Pada proses image correlation, template yang digunakan adalah dengan bentuk semua kemungkinan dari objek dan hasil pengenalannya dapat langsung ditentukan dari karakteristik template, sedangkan pada proses feature extraction, template yang digunakan merupakan bentuk fitur dari suatu objek yang akan dikenali dengan tujuan mencari fitur-fitur yang ada pada objek. Keluaran yang dihasilkan berupa keterangan yang menjelaskan arti sebuah objek. Ketepatan pengenalan ditentukan oleh dua parameter yaitu nilai notasi dan tinggi notasi. Kedua hasil pengenalan tersebut akan dibandingkan dengan menggunakan teknik akurasi. Dari hasil perbandingan diperoleh bahwa penggunaan proses feature extraction lebih baik jika dibanding proses image correlation karena pada notasi balok variasi bentuk objeknya sangat banyak, tetapi memiliki fitur yang jauh lebih sedikit.
15
Gambar Perbandingan tiga teknik pengenal pola : neural, statistik, struktural/sintaktik Ekstraksi Fitur Ekstraksi fitur merupakan proses mencari nilai karakteristik yang unik dari sebuah image. Dengan adanya nilai-nilai tersebut, maka sebuah image dapat dibedakan dengan image lainnya. Nilai karakteristik yang dihasilkan feature ekstraction selanjutnya akan digunakan sebagai support vector Zoning adalah salah satu metode dari ekstraksi fitur dimana untuk mendapatkan nilai yang unik dari sebuah image, diperoleh dengan cara membagi image menjadi n x n, selanjutnya dari setiap daerah / zone akan dihitung rata-rata jumlah pixel yg terdapat pada daerah / zone tsb. Secara umum metode ini disebut metode zoning n x n.
16
Support Vector Machine Support Vector Machine pertama kali diperkenalkan oleh Vapnik pada tahun 1992 sebagai rangkaian harmonis konsep – konsep unggulan dalam bidang pengenalan pola. Sebagai salah satu metode pengenalan pola, usia SVM terbilang masih relatif muda. Walaupun demikian, evaluasi kemampuannya dalam berbagai aplikasi menempatkannya sebagai sebuah karya terbaik dalam pengenalan pola, dan dewasa ini merupakan salah satu tema yang berkembang dengan pesat. SVM adalah metode learning machine yang bekerja atas prinsip Structural Risk Minimization (SRM) dengan tujuan menemukan hyperplane terbaik yang memisahkan dua buah kelas pada ruang input. Konsep dasar SVM sebenarnya merupakan kombinasi harmonis dari teori-teori komputasi yang telah ada puluhan tahun sebelumnya, seperti margin hyperplane (Duda & Hart tahun 1973, Cover tahun 1965, Vapnik 1964, dsb.), kernel diperkenalkan oleh Aronszajn tahun 1950, dan demikian juga dengan konsep-konsep pendukung yang lain. Akan tetapi hingga tahun 1992, belum pernah ada upaya merangkaikan komponenkomponen tersebut. Berbeda dengan strategi neural network yang berusaha mencari hyperplane pemisah antar kelas, SVM berusaha menemukan hyperplane yang terbaik pada input space. Prinsip dasar SVM adalah linear classifier, dan selanjutnya dikembangkan agar dapat bekerja pada problem non-linear. Dengan memasukkan konsep kernel trick pada ruang kerja berdimensi tinggi. Perkembangan ini memberikan rangsangan minat penelitian di bidang pengenalan pola untuk investigasi potensi kemampuan SVM secara teoritis maupun dari segi aplikasi. Dewasa ini SVM telah berhasil diaplikasikan dalam aplikasi di dunia nyata dan secara umum memberikan solusi yang lebih baik dibandingkan metode konvensional seperti misalnya artificial neural network. Support vector machines (SVM) telah terbukti sukses diaplikasikan dalam menyelesaikan masalah klasifikasi dan estimasi fungsi setelah pengenalan yang dilakukan oleh Vapnik dalam konteks teori statistical learning dan structure risk
17
minimization. Vapnik mengkonstruksikan SVM standar untuk memisahkan data-data pelatihan menjadi dua kelas. Tujuan dari pelatihan pada SVM adalah untuk menemukan fungsi pemisah (classifier) f ( x ) = ω ⋅ x + b sehingga kita dapat menggunakan classifier tersebut untuk mengklasifikasi data. Training set: set{xi , yi }i =1 , di mana xi ∈ ℜ n berperan sebagai l
input dan yi ∈ {− 1 + 1} menjadi output, mengindikasikan kelas. Formulasi SVM dimulai dari asumsi bahwa kasus yang dapat dipisahkan secara linear adalah: ⎧ω T xi + b ≥ +1, if yi = +1 ⎨ T ⎩ω xi + b ≤ −1, if yi = −1
(3)
Untuk kasus yang tidak dapat dipisahkan ⎧ω Tφ ( xi ) + b ≥ +1, if yi = +1 ⎨ T ⎩ω φ ( xi ) + b ≤ −1, if yi = −1
(4)
Dimana φ (.) menunjukkan sebuah pemetaan dari input menjadi sesuatu yang disebut ruang fitur berdimensi tinggi. Dalam metode kernel suatu data x di input space dipetakan ke kernel feature space yang lebih tinggi melalui map < sebagai berikut : < : x → < (x). Karena itu data x di input space, menjadi < (x) di kernel space. Dalam kernel space ini, dot product dua vektor <x, x> menjadi << (x), < (x)’>. Suatu fungsi kernel, K(x, x’), bisa digunakan untuk menggantikan dot product << (x),< (x)’>. Untuk setiap fungsi yang continuous dan positive definite, akan ada suatu pemetaan < , sehingga K(x,y)= ( < (x), < (y) ) untuk semua x,y אԸO, dimana ԸO adalah input space (Mercer’s Theorem). Dalam ruang ini, permukaan keputusan linear dibangun dengan property unik yang menjamin kemampuan generalisasi yang tinggi dalam jaringan. Ditunjukkan dalam
18
gambar diagram di bawah ini, bahwa fungsi kernel nonlinear memungkinkan untuk menghitung hyperplane pemisah dengan margin maksimum di feature space.
Gambar Pemetaan ruang fitur menggunakan fungsi kernel
Kita harus menemukan, di antara semua hyperplane yang memisahkan data-data, sebuah jarak maksimum
2 di antara kedua kelas. Masalah yang ada ditransformasikan ω
ke dalam bentuk Quadratic Programming (QP) problem l 1 min ω T ω + C ∑ ξ i 2 i =1
(
s.t y i ω t φ (x i
) + b) = 1 − ξ i ,ξ i
(5)
≥ 0, i = 1,...l
dimana C adalah parameter yang ditransaksikan antara error dengan margin. Quadratic Programming adalah suatu teknik Optimisasi yang meminimalisasi sejumlah n dalam notasi matriks. Masalah Quadratic Programming dapat dipecahkan dengan lagrangian multipliers α dapat dihasilkan memenuhi i ∈ ℜ . Solusi kondisi menggunakan Karush-Kuhn-Tucker (KKT). ω dicariyang dengan menggunakan
19 l
ω = ∑ α i y i φ ( x i ) , dimana xi bukan nol dan α i adalah support vector. Decision i =1
boundary hanya ditentukan oleh support vector. Diketahui t , ( j 1, ..., s) menjadi titiktitik dari s support vector. Maka kita dapat menuliskan kembali fungsi yang ada menjadi : s
ω = ∑ α tj ytj φ (xtj )
(6)
j =1
Masalah Quadratic Programming dipecahkan dengan menambahkan Dual Problem max α Q(α ) = −
1 l ∑ α iα j yi y j K (xi , x j ) 2 i , j =1
(7)
(8) dengan kernel trick (mercer theorem):
K (xi , x j ) = φ ( x i )T φ (x j )
(9)
Beberapa tipe dari kernel seperti linear, polynomial, splines, RBF, and MLP, dapat di manfaatkan di dalam SVM. Proses ini akhirnya menghasilkan hasil berikut ini: ⎛ l ⎞ y ( x ) = sign⎜ ∑ α i yi K ( x, xi + b )⎟ ⎝ i =1 ⎠
(10)
Pengenalan pola dalam Support Vector Machines Konsep SVM dapat dijelaskan secara sederhana sebagai usaha mencari hyperplane terbaik yang berfungsi sebagai pemisah dua buah kelas pada input space. Gambar 2.4a memperlihatkan beberapa pola yang merupakan anggota dari dua buah kelas : +1 dan –1. Pola yang tergabung pada kelas –1 disimbolkan dengan warna merah (kotak), sedangkan pola pada kelas +1, disimbolkan dengan warna biru (lingkaran). Masalah klasifikasi dapat diterjemahkan sebagai usaha menemukan garis (hyperplane) yang memisahkan antara kedua kelompok
20
tersebut. Berbagai alternatif garis pemisah (discrimination boundaries) ditunjukkan pada gambar (a)
(a) Cat : garis-garis di atas merupakan Discrimination Boundaries
21
S1
H
Margin
S2
w.x + b >= +1 w.x + b = 0 w.x + b <= -1
Class +1
Class -1
(b) Gambar Kelebihan SVM dalam pembentukan hyperplane terbaik Hyperplane pemisah terbaik antara kedua kelas dapat ditemukan dengan mengukur margin dari hyperplane tersebut. dan mencari titik maksimalnya. Margin adalah jarak antara hyperplane tersebut dengan pola terdekat dari masing-masing kelas. Pola yang paling dekat ini disebut sebagai support vector. Garis solid pada gambar 2.5b menunjukkan hyperplane yang terbaik, yaitu yang terletak tepat pada tengah-tengah kedua kelas, sedangkan titik merah dan biru yang berada dalam lingkaran hitam adalah support vector. Usaha untuk mencari lokasi hyperplane ini merupakan inti dari proses pelatihan pada SVM. LIBSVM ( Library for Support Vector Machines) LIBSVM merupakan library untuk mendukung vector machine (SVM), tujuannya adalah agar pengguna dapat dengan mudah menggunakan SVM
22
dimana dikatakan sebagai paket informasi, disini formulasi yang digunakan LIBSVM meliputi : C- Support Vector Classification (C-SVC), Nu-Support Vector. Classification ( v-SVC), Distribution Estimation
(one class SVM), €-
Support Vector Regression (€-SVR), dan Nu-Support Vector Regression (vSVR). Untuk algoritma pelatihan pada SVM guna mempercepat algoritma decomposition digunakan strategi Shrinking dan Caching (Krisantus Sembiring 2007, p19) ¾ Shrinking Abaikan bounded support vector ( α = C ) karena umumnya setelah beberapa iterasi dapat diidentifikasi dan bernilai tetap sampai akhir iterasi, akibatnya jumlah variabel yang harus dioptimasi lebih sedikit. ¾ Caching Simpan nilai output fungsi kernel yang baru digunakan di memori sehingga tidak perlu dihitung ulang setiap iterasi. Parameter parameter dalam model SVM di estimasi dengan teknik LIBSVM selanjutnya parameter tersebut dioptimasi dengan menggunakan Quadratic Programming. Pencarian solusi optimal untuk permasalahan kuadratik dapat dilakukan dengan metode yang sudah ada, yaitu Metode Interior Point. Dimana pergerakkan titik – titiknya berada dalam daerah interior lalu menuju titik solusi optimalnya. Akan tetapi metode tersebut hanya dapat dilakukan pada permasalahan kuadratik yang kondisi matriks pada fungsi tujuannya bersifat positif definite, namun belum dapat mengatasi permasalahan kuadratik jika kondisi matriksnya bersifat indefinite. Sehingga dikembangkan metode NewtonKKT Interior Point untuk mengatasi permasalahan tersebut. Optimasi Berdasarkan tingkat ketergantungan pada mesin, teknik optimasi dibagi menjadi: 1. Machine dependent optimizer
23
Kode dioptimasi sehingga optimal dan efisien pada mesin tertetu saja. Optimasi ini memerlukan informasi mengenai feature yang ada pada mesin tujuan, mengambil keuntungan dari mesin tujuan agar kode lebih pendek dan eksekusinya cepat. Yang dioptimasi adalah object code 2. Machine independent optimizer Optimasi ini dapat diaplikasikan tanpa tergantung pada mesin tujuan yang dioptimasi adalah intermediate code.
Karakteristik masalah optimasi meliputi : 1. Keputusan (Decisions) 2. Kendala (constraint) 3. Tujuan (objectives) Bentuk umum optimasi : f0(X1, X2, …, Xn)
MAX (or MIN):
Subject to: f1(X1, X2, …, Xn)<=b1 : fk(X1, X2, …, Xn)>=bk : fm(X1, X2, …, Xn)=bm Perhitungan solusi Optimal : Contoh :
Dan
X1 + X2 = 200
(1)
9X1 + 6X2 =1566
(2)
¾ Dari (1) kita dapatkan (2) = 200 – X1
(3)
¾ Substitusi (3) ke dalam (2), dan kita punya : 9X1 + 6 (200 – X1) =1566 Yang menghasilkan X1 = 122
24
¾ Sehingga solusi optimalnya adalah : X1=122, X2= 200 – X1=78
Linear Programming Jika seluruh fungsi bersifat linear, maka disebut dengan masalah program
linear
atau
linear
programming
(LP)
problem.
Linear
Programming merupakan salah satu teknik analisis yang memakai model matematika dengan tujuan untuk mencari, memilih, dan menentukan alternatif terbaik dari sekian alternatif yang tersedia.
Alokasi optimum
dilakukan dengan cara memaksimalkan / meminimumkan fungsi tujuan dengan syarat ikatan (kendala) dalam bentuk ketidaksamaan linear. Syaratsyarat tersebut adalah : ¾ Fungsi tujuan Primal → maksimum → dampak positif , keuntungan, manfaat yang ingin di maksimumkan Dual → minimum → dampak negatif, resiko-resiko, biaya-biaya, jarak dan hal-hal lain yang ingin diminimumkan ¾ Keterbatasan Sumber Daya Keterbatasan waktu, biaya, tenaga, ruangan → kendala (syarat ikatan) ¾ Perumusan Kuantitatif Model matematika → ketidaksamaan ¾ Cara penyelesaian yang bisa digunakan a. Metode Grafis b. Metode Simplex c. Program Komputer Problem
dalam
linear
programming
adalah
memperhatikan
penggunaan atau alokasi yang efisien dari sumberdaya-sumberdaya yang terbatas untuk mencapai tujuan yang diinginkan. (Soekartawi, 1992).
25
Nasendi dan Affendi Anwar (1985) dalam bukunya linear programming dan variasinya menyatakan bahwa ada tiga unsur yang harus dipenuhi yang dapat dirumuskan secara matematis yaitu fungsi tujuan, berbagai kendala fungsional dan kendala yang tidak boleh negatif. (Nasendi dan Affendi Anwar, 1985). Disamping itu ada 5 asumsi – asumsi dasar yang harus dipenuhi yaitu : a. Linieritas b. Proporsionalitas c. Adivitas d. Divisibilitas e. Deterministik Kelebihan-kelebihan yang dimiliki linear programming adalah : a.Mudah dilaksanakan, apabila menggunakan alat bantu komputer. b.Dapat menggunakan banyak variabel, sehingga kemungkinan untuk memperoleh pemanfaatan sumberdaya yang optimum dapat dicapai. c.Fungsi tujuan (objective function) dapat difleksiblekan sesuai dengan tujuan penelitian atau berdasarkan data yang tersedia Metode yang bisa digunakan : 1. Primal : metode ini digunakan untuk mencari pendapatan Gross Financial Marginal
(GFM)
dengan
keterbatasan
sumberdaya,
meminimumkan biaya-biaya, risiko-risiko untuk mencari nilai pendapatan maksimum. 2. Dual : untuk sumberdaya yang langka dan pembatasan terhadap ketentuan nilai output per unit, berapakah sebenarnya jumlah nilainilai tersebut per unit sumber daya yang langka tersebut yang dapat meminimumkan total nilai dari penggunaan sumberdaya yang terbatas. Masalah Program Linear :
26
MAX (or MIN):
c1X1+ c2X2+ …+ cnXn
Subject to:
a11X1+ a12X2+ …+ a1nXn<= b1 : ak1X1+ ak2X2+ …+ aknXn>=bk : am1X1+ am2X2+ …+ amnXn= bm
Quadratic Programming Quadratic Programming adalah program non linear. Data yang tadi nya linear menjadi non linear diselesaikan dengan Quadratic Programming. Pencarian solusi optimal untuk permasalahan kuadratik dapat dilakukan dengan metode yang sudah ada, yaitu Metode Interior Point. Dimana pergerakkan titik – titiknya berada dalam daerah interior lalu menuju titik solusi optimalnya. Akan tetapi metode tersebut hanya dapat dilakukan pada permasalahan kuadratik yang kondisi matriks pada fungsi tujuannya nya bersifat positif definite, namun belum dapat mengatasi permasalahan kuadratik
jika
kondisi
matriks
nya
bersifat
indefinite. Sehingga
dikembangkan metode Newton-KKT Interior Point untuk mengatasi permasalahan tersebut. 1.
Metode Interior Point Metode Interior Point pertama diperkenalkan oleh Karmarkar, adalah merupakan metode untuk menyelesaikan pemrograman linear. Metode
ini banyak digunakan dalam operasipenelitian (operation
research) karena efisien,reliabel dan akurat. Metode ini kemudian dikembangkan oleh James A. Momoh dkk dengan berdasarkan pada perbaikan kondisi awal sehingga bisa digunakan untuk menyelesaikan permasalahan dengan pemrograman linier maupun kuadratik (non linier) yang dikenal dengan metode EQIP (ExtendedQuadratic Interior Point method). Yang paling penting dalam algoritma ini adalah titik start awal
27
dapat ditentukan dahulu. Kemudian mencari solusi optimal dalam interior polytope yang didefinisikanoleh kendala-kendala sampai dicapai titik optimal. quadratic interior point didefinisikan sebagai berikut :
dimana : X = variabel yang tidak diketahui (unknown) n-vektor a = konstanta n-vektor bmin,bmax = konstanta m-vektor Q = matrik bujursangkar simetris A = matriks koefisien mxn dengan m < n Program linier dapat diperoleh dengan kasus khusus Q=0. Pada umumnya, dua m-vektor baru dibentuk yaitu S1 dan S2, dinamakan variabel slack, diperkenalkan untuk merubah kendala ketidaksamaan (5) menjadi bentuk persamaan:
28
(6) AX+
s2 = bmax
(7)
sehingga bisa didefinisikan variabel baru : 0
nx2m )
0 2mx2m
(8)
(9)
dan
A :::
-I
0
( mxm )
(mxm)
0 ( mxm )) I , ( mxm )
AX - st = bmm _ b max AX + 'S'2 -
sehingga bisa didefinisikan variabel bam
Onx2m ) 0 2mx2m a 6.( (l (11xl ) ), = a( 2 mxl)
dan
- (A( rnxn)
A.t> A
(mxn)
- I( rnxm ) 0
(mxm)
0
(mxm))
I
(mxm) '
(10)
29
Dengan I adalah matriks identitas mxm sehingga permasalahan optimasi quadratic (4) dan (5) mempunyai bentuk minimisasi sebagai :
Masalah optimasi quadratik yang diperlihatkan pada (11) – (13) di atas dengan mengasumsikan memiliki batas titik awal ( bounded interior point )
2.
Metode Newton-KKT Interior Point Kondisi Karush-Kuhn-Tucker (KKT). ω dapat dicari dengan l
menggunakan ω = ∑ α i y i φ ( x i ) , dimana xi bukan nol dan α i adalah i =1
support vector. Decision boundary hanya ditentukan oleh support vector. Diketahui t , ( j 1, ..., s) menjadi titik-titik dari s support vector. Maka kita dapat melihat persamaan (11) – (18) Pelatihan dengan Support Vector Machine Penggunaan SVM baik dalam bentuk supervised maupun unsupervised pada prinsipnya menyelesaikan sebuah permasalahan quadratic programming. Oleh karena itu, proses pelatihannya hampir sama dan tahapannya dapat dilihat pada gambar 2.6, Akan tetapi untuk unsupervised learning dengan SVM data pelatihan dan data pengujian adalah data yang sama. Selain itu, untuk proses pelatihannya dapat juga hanya menggunakan sebagian data dari data pengujian sehingga proses waktu pelatihan menjadi lebih singkat, tetapi hal ini mungkin menurunkan akurasi pada tahap pengujian.Sedangkan untuk supervised learning justru sebaliknya, dapat meningkatkan akurasi pada tahap pengujiannya.
30
Sehingga dalam penulisan skripsi ini, penulis menggunakan metode supervised
Parameter
Feature vector
learning.
Gambar Pelatihan dengan SVM
Kernel Batas kemampuan komputasi fungsi linier dibahas pada tahun 1960an oleh Minsky dan Papert. Secara umum, pada kasus dunia nyata, pengklasifikasian domain permasalahan memerlukan ekspresi yang lebih kompleks dibanding fungsi linier (misalnya fungsi polynomial, eksponensial, atau fungsi periodik). Trik kernel menawarkan solusi dengan memproyeksikan data ke dalam ruang dimensi yang lebih tinggi (disebut juga dengan feature space) untuk meningkatkan kemampuan komputasi fungsi linier. Yang dimaksud dengan dimensi di sini merupakan ruang dimensi vektor w berada, yang akan mempengaruhi besar nilai n. Adapun pemetaan ke ruang dimensi yang lebih tinggi dilakukan untuk memetakan input ke ruang dimensi yang baru, di mana diharapkan bahwa pada ruang dimensi yang baru, domain input dapat dipisahkan
31
oleh suatu vektor sederhana, yang tidak dapat dilakukan sebelumnya pada ruang dimensi awal. Adapun salah satu pemetaan ulang data, dapat dicapai dengan memetakan x ≡ (x1 ,..., x 2 ) → φ ( x) ≡ (φ1 ( x),..., φ d ( x)), d < n. Sehingga fungsi penentu berubah menjadi : 1. Kernel Linear
Gambar Contoh pemetaan Kernel Linear
2. Kernel Polynomial
k(x, x') = (γxx'+coef)degree
32
Gambar Contoh pemetaan Kernel Polynomial X = Support Vector X’ = Besarnya Vector Fungsi Kernel polynomial adalah directional, yaitu output tergantung pada arah 2 vector dalam ruang dimensi rendah, hal ini disebabkan produksi titik di dalam kernel yang menunjukkan bentuk dua dimensi yang jumlahnya banyak. Semua vector dengan arah yang sama akan lebih tinggi dari output kernelnya, yang besar dari outputnya juga tergantung pada besarnya vektor. 3. Kernel Radial Basis Function ⎛ k ( x, x' ) = exp⎜ − ⎜ ⎝
2 x − x' ⎟⎞ 2σ 2 ⎟ ⎠
33
Gambar Contoh Pemetaan Kernel RBF
Gambar Kernel RBF. Kiri : Original space. Kanan : Feature space Fungsi radial basis yang sering digunakan adalah fungsi gaussian karena mempunyai sifat lokal, yaitu bila input dekat dengan rata – rata (pusat), maka fungsi akan menghasilkan nilai satu, sedangkan bila input jauh dari rata – rata, maka fungsi memberikan nilai nol. Ada beberapa fungsi radial basis diantaranya adalah :
34
1. Fungsi Thin Plate Spline f (z) = ( z - m) 2 log(z - m)
2. Fungsi Multikuadratik f (z) =[( z - m) 2 +s 2 ]1/ 2
3. Fungsi Invers Multikuadratik f (z) =[( z - m) 2 +s 2 ]-1/ 2
4. Fungsi Gaussian f (z) = exp[-(z - m)2 / s 2 ] .
4. Kernel Sigmoid
Gambar Contoh Pemetaan Kernel Sigmoid
35
Klasifikasi Hyperplane Dalam bagian ini, akan dijelaskan sebuah algoritma pelatihan hyperplane yang dapat dilaksanakan di ruang dot product (seperti ruang fitur yang sudah kami perkenalkan sebelumnya). Seperti yang dijelaskan di bagian sebelumnya, untuk belajar desain algoritma efektivitas statistik yang dapat dikontrol, satu kebutuhan yang akan datang dengan satu kelas fungsi yang dapat menghitung kapasitas. w, x + b = 0 where w ∈ H , b ∈ ℜ,
(19)
Berhubungan dengan fungsi keputusan f ( x) = sgn( w, x + b),
(20)
Dan menawarkan sebuah algoritma pelatihan untuk masalah-masalah yang dipisahkan oleh hyperplane (terkadang disebut juga sebagai linearly separable) yang diistilahkan Generalized Potret, untuk membuat f dari data empiris. Dalam kasus ini, kita harus melakukan beberapa tambahan untuk mencari vektor normal yang mengarah ke margin terbesar. Untuk membuat hyperplane yang optimal, kita harus memecahkan minimize τ (w) = w∈H ,b∈ℜ
1 w 2
2
mengacu kepada yi ( w, xi + b) ≥ 1 untuk semua i = 1,…,m.
(21)
(22)
Fungsi τ di (21) disebut fungsi objektif, sementara (22) disebut inequality constraints. Bersama-sama, mereka membentuk yang disebut masalah optimisasi konstrain. Masalah semacam ini akan berhadapan dengan pengenalan Lagrange multipliers αI ≥ 0 dan sebuah lagrangian
36
L(w, b, α ) =
1 2 m w − ∑ α i ( y i ( xi , w + b) − 1). 2 i =1
(23)
Lagrangian L harus diminimalkan dengan memandang primal variables w dan b dan memaksimalkan dengan memandang ke dual variables αI (dengan kata lain poin penentu harus sudah ditemukan). Pernyataan bahwa pada poin penentu, yang derivatif dari L dengan memandang primal variable harus dihilangkan, ∂ ∂ L(w, b, α ) = 0dan L(w, b, α ) = 0, ∂b ∂w
(24)
mengarah ke m
∑α
i
yi = 0
(25)
i =1
dan m
w = ∑ α i y i xi
(26)
i =1
Vektor solusi yang dijelaskan dengan maksud dari sebuah subset dari pola pelatihan, disebut Support Vectors. Dengan kondisi KKT,
α i [y i ( xi , w + b ) − 1] = 0 untuk semua i = 1, … , m ,
(27)
Dengan menggantikan (25) dan (26) ke dalam Lagrangian, pertama hilangkan primal variables w dan b, tiba pada apa yang disebut optimasi dual problem, di mana masalah yang biasanya dipecahkan dalam pelatihan:
37 m
W (α ) = ∑ α i − maximize m α ∈ℜ
i =1
1 m ∑ α iα j y i y j xi , x j 2 i , j =1
(28)
m
Mengarah ke αi ≥ 0 untuk setiap i = 1,…,m dan
∑α
i
yi = 0
(29)
i =1
Dengan menggunakan (28), fungsi keputusan hyperplane dapat ditulis sebagai berikut ⎛ m ⎞ f ( x) = sgn⎜ ∑ y iα i x, xi + b⎟, ⎝ i=1 ⎠
Gambar Support Vector Menggunakan Kernel RBF
Multikelas Support Vector Machine Dalam perancangan aplikasi Handwriting Recognition digunakan SVM sebagai pengklasifikasi atau classifier, untuk mengenali karakter apa yang menjadi input ke dalam aplikasi ini.
38
Pada awalnya SVM dirancang hanya untuk menyelesaikan masalah klasifikasi biner, yaitu dari data – data yang ada, diklasifikasikan menjadi dua kelas. SVM memiliki pendekatan yang berbeda dibanding NN, dimana SVM mencari
hyperplane
pemisah
dua
kelas
yang
paling
optimal.
Untuk
mengklasifikasikan data yang terdiri dari lebih dari dua kelas, SVM tidak dapat langsung digunakan. Ada beberapa metode yang dapat dipakai untuk mengatasi masalah klasifikasi multiclass SVM yaitu : One-vs-One (OVO), One-vs-All (OVA) / One-vs-Rest, dan Directed Acyclic Graph Support Vector Machine (DAGSVM). Untuk menyelesaikan masalah klasifikasi multiclass pada SVM metode One_vs_one (OVO), One_vs_all (OVA)
digunakan
dan Directed Acyclic Graph
Support Vector Machine (DAGSVM). 1.
One-vs-One (OVO) Dengan metode ini, dibangun
buah model klasifikasi biner (k
adalah jumlah kelas). Setiap model klasifikasi dilatih pada data dari dua kelas. Untuk data pelatihan dari kelas ke – i dan kelas ke – j, dilakukan pencarian solusi untuk persoalan optimasi konstrain. Terdapat beberapa metode untuk melakukan pengujian setelah keseluruhan k(k1)/2 model klasifikasi selesai dibangun. Salah satunya adalah metode voting.
Table Contoh 6 SVM biner dengan metode OVO yi = 1
yi = -1
Hipotesa
Kelas 1
Kelas 2
f12(x)
Kelas 1 Kelas 1
Kelas 3 Kelas 4
f13(x)
f14(x)
Kelas 2
Kelas 3
f23(x)
Kelas 2
Kelas 4
f24(x)
Kelas 3
Kelas 4
f34(x)
39
xi
f12(x)
Kelas 1
f13(x)
Kelas 1
f14(x)
f23(x)
f24(x)
f34(x)
Kelas 1
Kelas 2
Kelas 4
Kelas 4
Gambar Contoh klasifikasi dengan metode OVO
Jika data x dimasukkan ke dalam fungsi hasil pelatihan dan hasilnya menyatakan x adalah kelas i, maka suara untuk kelas i ditambah satu. Kelas dari data x akan ditentukan dari jumlah suara terbanyak. Jika terdapat dua buah kelas yang jumlah suaranya sama, maka kelas yang indeksnya lebih kecil dinyatakan sebagai kelas dari data. 2.
One-vs-All (OVA) / One-vs-Rest Dengan metode ini, dibangun k buah model SVM biner (k adalah jumlah
kelas). Setiap model klasifikasi ke-i dilatih dengan menggunakan keseluruhan data, untuk mencari solusi permasalahan. Contohnya, terdapat permasalahan klasifikasi dengan 4 buah kelas. Untuk pelatihan digunakan 4 buah SVM biner seperti pada tabel 1 dan penggunaannya dalam mengklasifikasi data baru dapat dilihat pada Gambar 5. Table Contoh 4 SVM biner dengan metode OVA
yi = 1
yi = -1
Hipotesa
Kelas 1
Bukan Kelas 1
f1(x)
Kelas 2 Kelas 3
Bukan Kelas 2 Bukan Kelas 3
f2(x) f3(x)
Kelas 4
Bukan Kelas 4
f4(x)
40
f1(x)
xi
f2(x)
Kelas 1 Kelas 2
f3(x) f4(x)
Kelas 3
Kelas 4
unknown
Gambar 2.15 Contoh klasifikasi dengan metode OVA
3.
Directed Acyclic Graph Support Vector Machine (DAGSVM) Dengan metode ini, sama dengan metode OVO, pelatihan dilakukan
dengan membangun
buah model klasifikasi SVM biner. Akan tetapi, pada
saat pengujian digunakan binary directed acyclic graph. Setiap node merupakan model SVM biner dari kelas ke – i dan kelas ke – j. Pada saat memprediksi kelas data pengujian, maka hipotesis dimulai dari simpul akar, kemudian bergerak ke kiri atau ke kanan tergantung nilai output dari hipotesis. Table 2.3 Contoh 6 SVM biner dengan metode DAGSVM yi = 1
yi = -1
Hipotesa
Bukan Kelas 2
Bukan Kelas 1
f12(x)
Bukan Kelas 3 Bukan Kelas 4
Bukan Kelas 1 Bukan Kelas 1
f13(x) f14(x)
Bukan Kelas 3
Bukan Kelas 2
f23(x)
Bukan Kelas 4
Bukan Kelas 2
f24(x)
Bukan Kelas 4
Bukan Kelas 3
f34(x)
41
f 12(x)
xi
Not 1
Not 2
f 13(x)
f23(x) Not 2 Not 4f
Kelas 3
34
(x)
Not 3
Kelas 4
Not 3
Not f134(x)
Not 3
12
Not 4
f (x)Not 2
Kelas 2
Kelas 4
Not 4
f14(x)
Kelas 1
No t 1
Kelas 4
Not 4
Not 3
Kelas 3
Kelas 4
Gambar 2.16 Contoh klasifikasi dengan metode DAGSVM
Dalam tugas akhir ini, digunakan metode OVO, dikarenakan pustaka LibSVM yang kami pakai sudah built-in dalam pemakaian multiclass SVM dengan metode OVO.
Klasifikasi Linear Dalam proses supervised learning, mesin diberikan kumpulan contoh data (disebut juga input), dan label yang terasosiasi (disebut juga output), dan contoh input dalam bentuk vektor sehingga domain input merupakan himpunan real. Setelah contoh data dan labelnya tersedia, sejumlah metode dapat dipilih untuk melakukan proses klasifikasi pada masalah tersebut. Salah satu metode yang paling dimengerti dan paling sederhana adalah menggunakan metode fungsi linier (1) Linear classifier biasa digunakan untuk klasifikasi biner, yaitu kasus di mana domain outputnya hanya terdiri dari 2 kemungkinan saja (kelas positif dan kelas negatif). Klasifikasi ini biasanya dilakukan menggunakan fungsi
dengan
aturan untuk sembarang input x, akan diberikan label kelas +, apabila f(x) >= 1,
42
dan sebaliknya kelas –, apabila f(x) <= -1. Karena adalah fungsi linear, maka dapat lebih lanjut ditulis sebagai: f(x)
= (w,x) + b =
n
∑
i −1
wi xi + b
= (w1x1) + (w2x2) + (w3x3) + … + (wnxn) + b
(2)
Di sini, w merupakan vektor di ruang dimensi n, sehingga wi (w1 sampai wn) merupakan komponen – komponen nilai penyusun vektor w di ruang dimensi n, dan nilai dari vektor w disinilah yang akan menjadi classifier.
Gambar 2.17 Sebuah vektor sebagai pemisah 2 daerah W dan b merupakan parameter fungsi yang akan ditentukan dari proses pelatihan dari contoh – contoh data yang diberikan ke klasifikasi linear yang bersangkutan, dan hasilnya akan diberikan oleh
sgn ( f (x )) .Dalam proses
pengenalan data dan klasifikasi dalam tugas akhir ini kami menggunakan pendekatan algoritma SupportVector Machine.
43
Gambar 2.18 Contoh klasifikasi biner dari yang paling mudah (kiri) ke kanan yang paling kompeks (kanan)
Machine Learning Machine Learning adalah sebuah bidang dari ilmu kecerdasan buatan yang menaruh perhatian lebih pada penelitian tentang algoritma komputer yang dapat memperbaiki dirinya sendiri secara otomatis melalui pengalaman. Mesin akan belajar dari input-input yang diberikan sebelumnya untuk memperbaiki performa di masa depan. Fokus utama dari machine learning adalah untuk secara otomatis menghasilkan model, seperti rule dan pola, dari data. Algoritma-algoritma pada machine learning dapat dikelompokkan ke dalam dua kelompok, yaitu: •
Supervised Learning
•
Unsupervised Learning
Supervised Learning Supervised learning adalah teknik pelatihan mesin dengan membuat suatu fungsi dari data latihan. Data latihan terdiri dari pasangan nilai input (biasa dalam bentuk vektor), dan output yang diharapkan untuk input yang bersangkutan. Tugas dari mesin supervised learning adalah memprediksi nilai
44
fungsi untuk semua nilai input yang mungkin, setelah melalui sejumlah pelatihan. Contohnya pada pengenalan pola. Tujuan pada pembelajaran supervised learning adalah untuk menentukan nilai bobot-bobot koneksi di dalam jaringan sehingga jaringan dapat melakukan pemetaan ( mapping) dari input ke output sesuai yang diinginkan. Pemetaan ini ditentukan melalui satu set pola contoh atau data pelatihan (training data set). Setiap pasangan pola p terdiri dari vektor input xp dan vektor target tp. Setelah selesai pelatihan, jika diberikan masukan xp seharusnya jaringan menghasilkan nilai output tp. Besarnya perbedaan antara nilai vektor target dengan output aktual diukur dengan nilai error yang disebut juga dengan cost function:
di mana n adalah banyaknya unit pada output layer. Tujuan dari training ini pada dasarnya sama dengan mencari suatu nilai minimum global dari E. Untuk mencapai tujuan ini, mesin harus dapat melakukan proses generalisasi dari data latihan yang diberikan, untuk memprediksikan nilai output dari input yang belum pernah diberikan sebelumnya. Beberapa pendekatan dan algoritma yang umum dipakai adalah system syaraf buatan, backpropagation, dan Support Vector Machine. Pendekatan dan algoritma pada supervised learning, dapat penulis bahas misal nya neural network. Neural network (Jaringan Saraf Tiruan) sudah mulai banyak dimanfaatkan sebagai solusi terhadap berbagai macam kasus yang muncul beberapa dekade terakhir, sejarah ANN (Artificial Neural Network) menunjukan pembahasan terhadap masalah ini muncul sekitar awal tahun 1900an namun implementasinya baru banyak muncul beberapa dekade terakhir. Pemanfaatan ANN juga mulai merambah dunia security khususnya untuk
45
memecahkan masalah-masalah yang sifatnya tidak tetap sehingga sulit untuk di pecahkan dengan menggunakan tehnik pemrograman konvensional yang ada saat ini. Artificial Neural Network merupakan suatu jaringan saraf tiruan yang dibangun untuk meniru cara kerja otak manusia. Dengan jaringan saraf tiruan maka kita dapat memberikan semacam kecerdasan pada sistem, dimana sistem tersebut akan diberikan waktu untuk 'belajar' dan kemudian diharapkan dari proses belajarnya, sistem bisa memberikan solusi dari suatu kasus. Analoginya seperti mengajarkan seorang anak kecil untuk mengetahui bentuk kursi, kita akan menunjukan pada anak tersebut berbagai macam bentuk kursi dan bukan kursi. Kita akan memperlihatkan mana saja yang termasuk kursi dan mana yang bukan, proses ini disebut proses training. Setelah proses training selesai, maka tiba waktunya untuk melakukan test terhadap anak tersebut dengan menunjukan suatu bentuk kursi dan menanyakan apakah itu termasuk kursi atau bukan. Hal yang menarik adalah pada saat kita menunjukan suatu bentuk kursi yang belum pernah diajarkan pada anak tersebut dan apabila itu memang variasi dari kursi (dengan ciri misalnya: kakinya ada 4, ada pegangan tangannya, bentuknya seperti angka 4, dll) maka dia dapat mengambil kesimpulan bahwa benda tersebut adalah kursi, apabila jawaban si anak salah maka kita kembali melatihnya (proses training) dengan memasukan bentuk kursi yang baru tadi kedalam data latih, sehingga si anak dapat mengambil kesimpulan bahwa benda tersebut (dan yang mirip benda tersebut dimasa yang akan datang) adalah kursi. Hal yang sama terjadi pada sistem dimana sistem akan diajarkan dengan berbagai macam contoh (disebut data latih) dan kemudian diharapkan sistem akan dapat mengambil keputusan atas suatu masalah yang berhubungan dengan data latih sistem tersebut. Pemanfaatan ANN sekarang ini sudah cukup banyak dan telah diterapkan pada berbagai bidang, misalnya untuk mengetahui keadaan bursa saham di masa yang akan datang berdasarkan keadaan saat ini, menentukan jenis kelamin seseorang berdasarkan bentuk wajah, dll.
46
Dasar algoritma ANN : Mesin ANN bekerja pada 2 mode yang pertama adalah trainning dan yang kedua adalah execution. Pada saat proses training, kita akan melatih sistem dengan memberikannya sebanyak mungkin contoh data input serta output yang akan dihasilkan oleh data input tersebut. Contoh paling mudah adalah mengajarkan sistem operasi penjumlahan: input ke-1 = 0.1 input ke-2 = 0.2 output = 0.3 pada contoh tersebut, kita mengajarkan pada sistem apabila inputan terdiri dari angka "0.1" dan "0.2" maka outputnya adalah "0.3". Jika hanya diberikan satu contoh maka sistem tidak akan belajar dengan baik, untuk itu sistem sebaiknya diberikan contoh data dengan jumlah yang sangat besar sehingga kecerdasan sistem bisa lebih handal. Konsep pertama yang harus di pahami sebelum masuk pada tahap coding adalah layer. ANN umumnya terdiri dari 3 layer, yaitu "input layer", "hidden layer", dan "output layer". Ketiga layer inilah yang akan membentuk topologi ANN. Tiap layer terdiri dari unit-unit node yang jumlahnya dapat kita tentukan sendiri, bisa dibayangkan bahwa tiap node pada ANN ibaratnya seperti neuron pada otak manusia. Jumlah node pada input layer tergantung pada jumlah data input yang akan masuk pada sistem, misalnya pada operasi penjumlahan diatas maka jumlah node pada input layer sebanyak 2 buah.Jumlah node pada hidden layer bervariasi, dan terdapat banyak teori yang dapat menjelaskan bagaimana mencari jumlah node yang tepat pada hidden layer, namun pada umumnya 5 buah node pada hidden layer suatu ANN sudah mencukupi untuk memecahkan berbagai macam kasus. Node pada output layer tergantung dari jumlah output
47
pada sistem, pada contoh operasi penjumlahan diatas dapat dilihat bahwa jumlah node di output layernya sebanyak 1 buah. Konsep kedua yang penting adalah nilai Error minimum yang diharapkan. Pada saat ANN di inisialisasi akan dibangkitkan nilai random untuk koneksi antar node dari suatu layer dengan layer sesudahnya, jadi antar node-node di hidden layer saling terkoneksi satu sama lain dengan node-node di hidden layer, dan antar node-node di hidden layer akan saling terkoneksi satu sama lain dengan node-node pada output layer. Nilai koneksi antar node tersebut sering disebut 'bobot'. Nilai bobot inilah yang akan menentukan kecerdasan suatu sistem. Pada saat proses training, nilai bobot tersebut akan terus berubah sehingga didapatkan kesesuaian antara input dengan output dengan Error minimum. Dengan kata lain, pada proses training kita akan menentukan nilai minimum error yang bisa di tolerir oleh sistem,seperti yang disampaikan diatas bahwa sistem tidak akan memberikan kepastian jawaban untuk suatu kasus yang tidak pernah dilatihkan kepadanya, pasti ada nilai Error dari jawaban sistem dengan jawaban yang seharusnya, nah nilai Error tersebut yang harus di definisikan oleh kita sebelum melatih sistem sehingga sistem bisa menjawab dengan tingkat kebenaran semaksimal mungkin (misal: tingkat kebenaran sistem 99,9999% dengan nilai Error 0.0001). Arsitektur Komputasi Neural 1.
Memiliki beberapa hal yang menarik komputasi lokal, adaptive interaction between Paralel
2.
Simple processing elements
3.
High degree of interconnections
4.
Masalah sering direpresentasikan dalam struktur
5.
Memungkinkan implementasi hardware (VLSI, optical)
48
Selain NN ada juga Support vector machine, Baik SVM maupun NN pembelajarannya dilakukan dengan menggunakan pasangan data input dan data output berupa sasaran yang diinginkan. Pembelajaran dengan cara ini disebut dengan pembelajaran terarah (supervised learning). Dengan pembelajaran terarah ini akan diperoleh fungsi yang menggambarkan bentuk ketergantungan input dan outputnya. Selanjutnya, diharapkan fungsi yang diperoleh mempunyai kemampuan generalisasi yang baik, dalam arti bahwa fungsi tersebut dapat digunakan untuk data input di luar data pembelajaran. SVM (support vector machine), yang dikembangkan oleh Vapnik.Algoritma ini mentransform input ke dimensi yang lebih tinggi (higher dimensional feature space) dengan menggunakan nonlinear mapping (fungsi kernel). Dengan kernel yang sesuai, SVM menentukan hyperplane yang maksimum atau pembatas (decision boundary) sedemikian hingga jarak antara hyperplane dan objek yang terdekat dalam setiap klas adalah maksimum
Unsupervised Learning Unsupervised learning adalah sebuah teknik pelatihan mesin dimana mesin mencari
bagaimana
data-data
yang
ada
diorganisasikan.
Pada
proses
unsupervised learning, data yang diberikan adalah data yang tidak memiliki label (unlabeled), maksudnya
tidak diketahui sebelumnya data yang diberikan
termasuk kelompok yang mana contohnya clustering dan fuzzy. Clustering
dapat
didefinisikan
sebagai
proses
mengelompokkan
sekumpulan objek sedemikian hingga objek dalam satu grup lebih serupa karakteristiknya dibandingkan dengan objek-objek di grup-grup yang lain. Clustering juga dikenal sebagai unsupervised learning karena objek-objek dalam database tidak memiliki kelas (tipe) yang membedakan antara satu objek dengan objek yang lain. Analisa grup sangat bermanfaat untuk mengetahui dan memahami distribusi data dan sering sekali digunakan sebagai proses awal sebelum teknik-teknik data mining lain digunakan.Secara garis besar teknik-
49
teknik clustering dapat dikategorikan dalam 3 kelompok. Teknik clustering berdasarkan jarak (distance-based), berdasarkan kepadatan (density-based), and teknik
clustering berdasarkan
hirarki
(hierarchy-based). Hierarchy-based
clustering terbagi menjadi 2 jenis yaitu agglomerative dan divisive. Pendekatan secara agglomerative memulai clustering dengan mengambil setiap objek sebagai objek yang terpisah satu sama lainnya dan menggabungkannya satu persatu berdasarkan suatu metric (measurement). Sebaliknya, divisive memulai clustering dengan menganggap bahwa semua objek berada dalam satu cluster kemudian memecahkannya satu persatu sehingga pada akhirnya setiap objek merupakan suatu cluster tersendiri. Unsupervised learning meminta sistem untuk terus
melakukan pembelajaran dengan
performansi sistem pada setiap iterasi.
mengevaluasi model,
mengukur
50
TRANSFORMASI FOURIER
Dasar-dasar Transformasi Fourier Transformasi Fourier adalah suatu model transformasi yang memindahkan domain spasial atau domain waktu menjadi domain frekwensi.
Transformasi
F(t)
F()
Fourier
Gambar 4.1. Transformasi Fourier
Transformasi Fourier merupakan suatu proses yang banyak digunakan untuk memindahkan domain dari suatu fungsi atau obyek ke dalam domain frekwensi. Di dalam pengolahan citra digital, transformasi fourier digunakan untuk mengubah domain spasial pada citra menjadi domain frekwensi. Analisa-analisa dalam domain frekwensi banyak digunakan seperti filtering. Dengan menggunakan transformasi fourier, sinyal atau citra dapat dilihat sebagai suatu obyek dalam domain frekwensi.
Transformasi Fourier 1D Transformasi Fourier kontinu 1D dari suatu fungsi waktu f(t) didefinisikan dengan: F ( )
f (t ).e
jt
dt
51
dimana F( ) adalah fungsi dalam domain frekwensi adalah frekwensi radial 0 – 2 f, atau dapat dituliskan bahwa =2 f Contoh. Diketahui fungsi f(t) sebagai berikut: f(t) 3
-1
0
1
t
Transformasi Fourier dari f(t) di atas adalah: 1
1
1
1
F ( ) (3)e jt dt 3 e jt dt
3 j t e j
1
1
3 j 6 sin( ) e e j j
Hasil dari transformasi Fourier untuk
= 0 s/d 2
adalah :
Gambar 4.2. Contoh hasil transformasi fourier
52
Transformasi Fourier 2D Transformasi Fourier kontinu 2D dari suatu fungsi spasial f(x,y) didefinisikan dengan:
f ( x, y).e
F (1 , 2 )
j 1 x 2 y
dxdy
dimana F(
1,
2)
adalah fungsi dalam domain frekwensi
f(x,y) adalah fungsi spasial atau citra dan
adalah frekwensi radial 0 – 2 .
2
Transformasi fourier yang digunakan dalam pengolahan citra digital adalah transformasi fourier 2D.
f(x,y)
Contoh 4.2.
1
Diketahui fungsi spasial f(x,y) berikut: 1
1
y
x
Transformasi fourier dari f(x,y) di atas adalah:
F 1 , 2
1 1
(1).e
j 1 x 2 y
dydx
1 1
1
1 e j1x j2 y sin( 2 ) j1x e dx e dx j 2 2 1 1 1 1
1
sin( 2 ) e j1x sin( 2 ) sin( 1 ) . 2 j1 1 2 1 sin( 2 ) sin( 1 )
21
Hasil dari transformasi fourier untuk 0<
1,
2<2
, adalah sebagai berikut :
53
Gambar 4.3. Contoh hasil transformasi fourier 2D
Gambar 4.4. Hasil transformasi fourier dalam surface
Transformasi Fourier semacam ini disebut dengan continuous fourier transform, dan sulit dikomputasi karena ada operasi integral dan sifat kontinunya itu sendiri.
Transformasi Fourier Diskrit Transformasi fourier diskrit atau disebut dengan Discrete Fourier Transform (DFT) adalah model transformasi fourier yang dikenakan pada fungsi diskrit, dan hasilnya juga diskrit. DFT didefinisikan dengan : N
F (k ) f (n).e j 2knT / N n 1
54
4.2.1. DFT 1D DFT seperti rumus di atas dinamakan dengan DFT 1 dimensi, DFT semacam ini banyak digunakan dalam pengolahan sinyal digital. Contoh 4.3 : Diketahui f(t) dalam bentuk diskrit f(n) sebagai berikut : f(t)
0
1
2
t
3
DFT dengan T=1 dari fungsi f(n) di atas adalah :
k=0
3
3
n 0
n 0
F (0) f (n).e jn0 f (n) 1111 4 3
F (1) f (n).e j 2n / 4
k=1
n0
3
f (n).e
0.5 jn
0
n0
k=2
k=3
3
3
n 0
n 0
F (2) f (n).e j 4 n / 4 f (n).e jn 0 3
3
n 0
n 0
F (3) f (n).e j 6 nn / 4 f (n).e j1.5 n 0
Hasil dari DFT untuk T (periode sampling) yang berbeda akan juga berbeda. Sehingga dalam proses perhitungan DFT, penentuan nilai T juga merupakan perhatian penting. Sebagai acuan dapat digunakan aturan frekwensi Niquist bahwa frekwensi sampling minimal dua kali frekwensi informasi (data), atau dengan kata lain periode sampling maksimal setengah kali periode dari nilai fungsinya.
55
Contoh 4.3 : Diketahui f(t) dalam bentuk diskrit f(n) sebagai berikut : f(t) 2 1 t 0
1
2
3
0
1
2
3
DFT dengan T=1 dari fungsi f(n) di atas adalah : 7
7
n 0
n 0
F (k ) f (n).e j 2nk / 8 f (n).e jnk / 8
Hasil DFT fungsi f(t) di atas adalah : k
F(k)
0
12
1
0
2
-2 – 2j
3
0
4
0
5
0
6
-2 + 2j
7
0
56
Terlihat bahwa hasil dari DFT adalah bilangan komplek, yang terdiri dari unsur real dan imaginer. Sehingga dapat dipisahkan dalam unsur real dan imaginer sebagai berikut : k Real{F(k)} Im{F(k)} 0
12
0
1
0
0
2
-2
-2
3
0
0
4
0
0
5
0
0
6
-2
2
7
0
0
Dan dapat digambarkan sebagai berikut :
Bagian Real
Bagian Imaginer
Gambar 4.5. Contoh DFT real dan imaginer
57
Atau dapat dinyatakan dalam magnitude dan phase dengan definisi sebagai berikut :
Re f (k )2 Im f (k )2
Magnitude :
F (k )
Phase :
Arg F (k )
ImF (k ) ReF (k )
Magnitude
Phase Gambar 4.6. Contoh DFT real dan imaginer
Bila DFT dihitung untuk k=0 s/d 15 maka hasilnya adalah: k F(k) K
F(k)
0
12
8
12
1
0
9
0
2
-2 – 2j
10
-2 – 2j
3
0
11
0
4
0
12
0
5
0
13
0
6
-2 + 2j
14
-2 + 2j
7
0
15
0
58
Terlihat terjadi pengulangan hasil, hal ini disebabkan proses DFT memang mengakibatkan terjadinya periodik. Ini sebagai akibat dari adanya unsur radial 2 dalam bentuk transformasi fourier. Sehingga dalam proses perhitungan DFT, perhitungan cukup dilakukan sampai 1/2 periodik saja. Dan perhitungan inilah yang dinamakan dengan FFT (Fast Fourier Transform).
Transformasi Fourier Diskrit 2D Transformasi Fourier Diskrit (DFT) 2 Dimensi adalah tranformasi fourier diskrit yang dikenakan pada fungsi 2D (fungsi dengan dua variabel bebas), yang didefinisikan sebagai berikut : F ( k1 , k 2 )
N1
N2
f (n , n
n1 0 n2 0
1
2
).e j 2T ( k1n1 / N1 k2 n2 / N 2 )
DFT 2D ini banyak digunakan dalam pengolahan citra digital, karena data citra dinyatakan sebagai fungsi 2D. Contoh : Diketahui f(x,y) adalah sebagai berikut : 0
1
1
1
1
0
1
1
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
Bila digambarkan hasilnya adalah sebagai berikut :
Gambar 4.7. Contoh citra dalam f(x,y)
59
DFT dari fungsi f(x,y) di atas adalah :
F (k1 , k 2 )
4
6
f (n , n 1
n1 0 n2 0
).e j 2T ( k1n1 / 4 k2n2 / 6)
2
Hasil dari DFT adalah sebagai berikut : 16
0
-2 - 3.46i
0
-2 + 3.46i
0
0
-1.27 4.73i
0
0
0
4.73 1.27i
0
0
0
0
0
0
0
-4.73+ 1.27i
0
0
0
1.27 + 4.73i
Secara Grafis dapat ditunjukkan bahwa :
Bagian Real
Bagian Imaginer Gambar 4.8. Contoh hasil DFT 2D
Hasil DFT dalam bentuk magnitude dan phase adalah sebagai berikut : Magnitude = 16.0000
0
0
4.8990
0
0
0
4.8990
Phase =
4.0000 0 0
0 0
0 0
4.0000 0
0 0
4.8990 0
0
4.8990
0
60
0
0 -2.0944
0 -1.8326 0
0
0
2.8798
0
0
2.0944
0
0
0 0
0 -2.8798 0
0
0
0 0
1.8326
Secara grafis dapat digambarkan sebagai berikut :
Magnitude
Phase
Gambar 4.9. Contoh hasil DFT 2D dalam magnitude dan phase
Fast Fourier Transform FFT (Fast Fourier Transform) adalah teknik perhitungan cepat dari DFT. Untuk pembahasan FFT ini, akan dijelaskan FFT untuk 1D dan FFT untuk 2D. Dimana FFT 2D adalah pengembangan dari DFT 2D.
FFT 1D FFT adalah DFT dengan teknik perhitungan yang cepat dengan memanfaatkan sifat periodikal dari transformasi fourier. Perhatikan definisi dari DFT : N
F (k ) f (n).e j 2knT / N n 1
61
Atau dapat dituliskan dengan : N
N
n 1
n 1
F (k ) f (n) cos( 2nkT / N ) j f (n) sin( 2nkT / N )
Perhatikan fungsi cosinus berikut ini :
Gambar 4.10. Gambar fungsi cosinus 1 periode Pada gambar tersebut, dapat dilihat bahwa nilai fungsi cosinus untuk setangah bagian bila dilihat dari kiri dan setengah bagian dari kanan akan sama, atau dapat dikatakan bahwa nilai fungsi cosinus untuk setengah periode adalah kebalikan horisontal (shift) dari nilai setengah periode sebelumnya, atau dapat dituliskan bahwa ; cos(T/2-x) = -cos(x), untuk 0<x
Gambar 4.11. Gambar fungsi sinus 1 periode
62
Pada gambar tersebut, dapat dilihat bahwa nilai fungsi sinus untuk setengah periode adalah kebalikan dari nilai setengah periode sebelumnya, atau dapat dituliskan bahwa ; sin(x+T/2) = -sin(x), untuk 0<x
F(k)
k
F(k)
0
12
5
0
1
0
6
-2 + 2j
2
-2 – 2j
7
0
3
0
8
12
4
0
Untuk menghitung hasil tersebut diperlukan 8x8 = 64 kali perhitungan (looping). Bila dihitung dengan menggunakan FFT seperti diatas, maka akan diperoleh ( 5x8 + 4 ) = 44 kali perhitungan, hal ini terlihat sangat meng/hemat perhitungan. Tentunya dengan bertambahnya ukuran data, maka perbedaan kecepatan perhitungannya akan semakin terasa. Untuk n buah data, DFT memerlukan n2 kali perhitungan, dan FFT memerlukan (n/2 + 1)xn + n/2 kali perhitungan. Misalkan jumlah data n=100 maka dengan menggunakan DFT diperlukan 100x100 = 10.000 kali perhitungan, dengan dengan menggunakan FFT cukup dilakukan (51x100 + 50) = 5150 kali perhitungan.
63
Cara perhitungan FFT adalah sebagai berikut. (1) Hitung dengan cara DFT Untuk k=0 : F(0) = 12 + 0j Untuk k=1 : F(1) = 0 + 0 j Untuk k=2 : F(2) = -2 – 2j Untuk k=3 : F(3) = 0 + 0 j Untuk k=4 : F(4) = 0 + 0 j (karena posisi ditengah) (2) Perhitungan selanjutnya dilakukan dengan menggunakan cara konjugate diatas. Untuk k=5 : F(5) = Real{F(3)} - Im{F(1)} = 0 + 0 j Untuk k=6 : F(6) = Real{F(2)} - Im{F(2)} = -2 + 2 j Untuk k=7 : F(7) = Real{F(1)} - Im{F(3)} = 0 + 0 j
FFT 2D FFT 2D adalah DFT 2D dengan teknik perhitungan yang cepat dengan memanfaatkan sifat periodikal dari transformasi fourier. Seperti halnya FFT 1D, maka dengan menggunakan sifat fungsi sinus dan cosinus, algoritma dari FFt 2D ini adalah : (1) Hitung FFT 2D untuk n1 = 1 s/d N1/2 dan n2 = 1 s/d N2/2 menggunakan rumus DFT. (2) Untuk selanjutnya digunakan teknk konjugate 2D.
64
Contoh 4.6 : Perhatikan contoh 4.4. dengan fungsi f(x,y) sebagai berikut : 0
1
1
1
1
0
1
1
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
DFT dari fungsi ini adalah sebagai berikut : 16
0
-2 - 3.46i
0
-2 + 3.46i
0
0
-1.27 4.73i
0
0
0
4.73 1.27i
0
0
0
0
0
0
0
-4.73+ 1.27i
0
0
0
-1.27 + 4.73i
Jumlah perhitungan DFT di atas adalah (4x6)2 = 576 kali.
Dengan menggunakan FFT, maka perhitungannya adalah : (1) Hitung DFT untuk ukuran 4x4 sehingga diperoleh : F(0,0) = 16 F(0,1) = 0 F(0,2) = -2 – 3.46i
F(0,3) = 0
F(1,0) = 0
F(1,1) = -1.27 – 4.73i
F(1,2) = 0
F(1,3) = 0
65
F(2,0) = 0
F(2,1) = 0
F(2,2) = 0
F(2,3) = 0
F(3,0) = 0
F(3,1) = -4.73 + 1.27i
F(3,2) = 0
F(3,3) = 0
(2) Dengan cara konjugate dapat diperoleh : F(0,4) = conjugate(F(0,2)) = -2 + 3.46i F(0,5) = conjugate(F(0,1)) = 0 F(1,4) = conjugate(F(3,2)) = 0 F(1,5) = conjugate(F(3,1)) = -4.73 – 1.27i F(2,4) = conjugate(F(2,2)) = 0 F(2,5) = conjugate(F(2,1)) = 0 F(2,4) = conjugate(F(1,2)) = 0 F(2,5) = conjugate(F(1,1)) = -1.27 + 4.73i Jumlah perhitungan dari FFT adalah (4x4x4x6) + 2x4 = 392 kali.
Membuat Program Transformasi Fourier Pada Citra Pada dasarnya citra adalah fungsi 2D, sehingga transformasi fourier yang digunakan adalah transformasi fourier 2D. Langkah-langkah untuk membuat program transformasi fourier pada citra menggunakan Visual Basic adalah sebagai berikut : (1) Buat Project baru dengan menekan
, sehingga muncul tampilan project baru dengan form kosong yang kemudian buatlah form seperti gambar 4.12.
66
Gambar 4.12. Form untuk proses transformasi fourier
67
(2) Isilah property pada setiap obyek dan form sebagai berikut: Obyek Property Nilai Form
Name
FormFourier
Caption
Transformasi Fourier
Picture
Nama file gambar
Appereance
Flat
Picture2
Appereance
Flat
Picture3
Appereance
Flat
Picture4
Appereance
Flat
Picture5
Appereance
Flat
Command1
Caption
Transformasi Fourier
Command2
Caption
Magnitude Phase
Command3
Caption
Keluar
Label1
Caption
BAGIAN REAL
Background
&H8000000C&
Caption
BAGIAN IMAGINER
Background
&H8000000C&
Caption
MAGNITUDE
Background
&H8000000C&
Caption
PHASE
Background
&H8000000C&
Picture1
Label2
Label3
Label4
68
(3) Click bagian form yang kosong, dan isikan program inisialisasi proses berikut ini: Dim n1, n2, m1, m2 As Integer Dim x(400, 400) As Integer Dim xr(400, 400), xi(400, 400) As Single
Private Sub Form_Load() m1 = 16: m2 = 16 End Sub (4) Click Command1, dan isikan program untuk proses perhitungan Transformasi Fourier menggunakan DFT: Private Sub Command1_Click() n1 = 0 For i = 1 To Picture1.ScaleWidth Step 15 n1 = n1 + 1 n2 = 0 For j = 1 To Picture1.ScaleHeight Step 15 warna = Picture1.Point(i, j) r = warna And RGB(255, 0, 0) g = Int((warna And RGB(0, 255, 0)) / 256) b = Int(Int((warna And RGB(0, 0, 255)) / 256) / 256) n2 = n2 + 1 x(n1, n2) = Int((r + g + b) / 3) Picture1.PSet (i, j), RGB(x(n1, n2), x(n1, n2), x(n1, n2)) Next j Next i Picture2.ScaleHeight = m1 + 1 Picture2.ScaleWidth = m2 + 1 Picture3.ScaleHeight = m1 + 1 Picture3.ScaleWidth = m2 + 1 For i = 1 To m1 For j = 1 To m2 fr = 0 fi = 0 For k1 = 1 To n1 For k2 = 1 To n2 fr = fr + x(k1, k2) * Cos(6.28 * (i * k1 / m1 + j * k2 / m2)) fi = fi - x(k1, k2) * Sin(6.28 * (i * k1 / m1 + j * k2 / m2)) Next k2 Next k1 w = 255 * Abs(fr) / (n1 * n2) Picture2.Line (i - 0.5, j - 0.5)-(i + 0.5, j + 0.5), RGB(w, w, w), BF
69 w = 255 * Abs(fi) / (n1 * n2) Picture3.Line (i - 0.5, j - 0.5)-(i + 0.5, j + 0.5), RGB(w, w, w), BF xr(i, j) = fr xi(i, j) = fi Next j Next i End Sub (5) Click Command2, dan isikan program untuk proses perhitungan magnitude dan phase berikut ini: Private Sub Command2_Click() Dim xa(100, 100), xg(100, 100) As Integer Picture4.ScaleHeight = m1 + 1 Picture4.ScaleWidth = m2 + 1 Picture5.ScaleHeight = m1 + 1 Picture5.ScaleWidth = m2 + 1 xam = 0 xgm = 0 For i = 1 To m1 For j = 1 To m2 xa(i, j) = (xr(i, j) ^ 2 + xi(i, j) ^ 2) ^ 0.5 xg(i, j) = xi(i, j) / xr(i, j) If xa(i, j) > xam Then xam = xa(i, j) If Abs(xg(i, j)) > xgm Then xgm = Abs(xg(i, j)) Next j Next i For i = 1 To m1 For j = 1 To m2 w = Int(256 * xa(i, j) / xam) Picture4.Line (i - 0.5, j - 0.5)-(i + 0.5, j + 0.5), RGB(w, w, w), BF w = Int(256 * Abs(xg(i, j)) / xgm) Picture5.Line (i - 0.5, j - 0.5)-(i + 0.5, j + 0.5), RGB(w, w, w), BF Next j Next i End Sub (6) Click Command3, dan isikan program untuk proses keluar dari program berikut ini: Private Sub Command3_Click()
Unload Me End Sub (7) Simpan form ini dengan nama formFourier seperti nama formnya, dan simpan projectnya dengan nama ProjectFourier. Contoh hasil transformasi fourier adalah sebagai berikut :
70
Gambar 4.23. Contoh transformasi fourier dengan 8x8 Untuk mengubah ukuran window dari hasil transformasi fourier dapat dilakukan dengan mengganti nilai m1 dan m2 pada fungsi form load.
Gambar 4.24. Contoh transformasi fourier dengan 16x16 Pada beberapa citra program di atas menyebabkan hasilnya hanya memperlihatkan suatu titik putih di pojok kiri atas atau dipojok kanan bawah pada gambar magnitudenya. Hal ini tentunya membuat lebih sulit dalam melakukan analisa terhadap frekwensi suatu citra. Hal ini disebabkan terjadinya nilai dominan pada suatu frekwensi. Untuk mengurangi dominansi tersebut digunakan fungsi logaritma yang dikenakan pada magnitude. Dengan memperhatikan bahwa posisi kiri atas menyatakan frekwensi rendah dan posisi kanan bawah menyatakan frekwensi tinggi seperti format gambar berikut :
71
low
m2
1
m1
high
Gambar 4.25. Format koordinat frekwensi Perhatikan nilai magnitude dari gambar 4.23 dan gambar 4.24, maka akan terlihat bahwa nilai pada daerah frekwensi rendah secara rata-rata lebih tinggi dari nilai-nilai pada frekwensi tinggi. Dari hal ini dapat dikatakan bahwa citra bekerja di frekwensi rendah. Sehingga bila frekwensi rendah ini dihilangkan maka gambarnya akan hilang, tetapi bila frekwensi tinggi yang dihilangkan maka hanya sedikit bagian citra yang hilang. Pada proses filtering citra, beberapa keperluan yang mempertahankan citra lebih banyak menggunakan Low Pass Filter (Filter yang mengambil frekwensi rendah dan membuang frekwensi tinggi) seperti reduksi noise, proses blur dan lain-lain. Meskipun demikian terkadang diperlukan proses High Pass Filter (Filter yang membuang frekwensi rendah dan mengambil frekwensi tinggi) seperti deteksi tepi.
Transformasi Cosinus Diskrit Transformasi Cosinus Diskrit atau disebut dengan Discrete Cosine Transform (DCT) adalah model transformasi fourier yang dikenakan pada fungsi diskrit dengan hnaya mengambil bagian cosinus dari eksponensial kompleks, dan hasilnya juga diskrit. DCT didefinisikan dengan : N
F (k ) f (n). cos( 2nk / N ) n 1
Berbeda dengan DFT yang hasilnya berupa variabel kompleks dengan bagian real dan imaginer, maka hasil DCT hanya berupa real tanp ada imaginer. Hal ini banyak membantu karena dapat mengurangi perhitungan. Dalam DCT nilai magnitude adalah hasil dari DCT itu sendiri dan tidak diperlukan phase. DCT 1D DCT seperti rumus di atas dinamakan dengan DCT 1 dimensi, DCT semacam ini banyak digunakan dalam pengolahan sinyal digital.
72
Contoh : Diketahui f(t) dalam bentuk diskrit f(n) sebagai berikut : f(t)
0
1
2
t
3
DFT dengan T=1 dari fungsi f(n) di atas adalah :
k=0
3
3
n 0
n 0
F (0) f (n). cos(0) f (n) 1111 4
k=1
k=2
k=3
3
3
n 0
n 0
F (1) f (n). cos( 4n / 4) f (n). cos( n ) 0 3
3
n 0
n 0
F (2) f (n). cos(8n / 4) f (n). cos( 2n ) 0 3
3
n 0
n 0
F (3) f (n). cos(12n / 4) f (n). cos(3n ) 0
Contoh : Diketahui f(t) dalam bentuk diskrit f(n) sebagai berikut : f(t) 2 1 t 0
1
2
3
0
1
2
3
73
DCT dengan T=1 dari fungsi f(n) di atas adalah : 7
7
n 0
n 0
F (k ) f (n). cos( 2nk / 8) f (n). cos( nk / 4)
Hasil DCT fungsi f(t) di atas adalah : k
F(k)
0
12
1
0
2
-2
3
0
4
0
5
0
6
-2
7
0
Secara grafik dapat digambarkan hasil DCT seperti gambar berikut :
Gambar 4.26. Contoh hasil DCT
74
DCT 2D DCT 2 dimensi adalah tranformasi fourier diskrit yang dikenakan pada fungsi 2D (fungsi dengan dua variabel bebas) dengan hanya mengambil bagian cosinus dari eksponensial imaginer, yang didefinisikan sebagai berikut : F ( k1 , k 2 )
N1
N2
f (n , n
n1 0 n2 0
1
2
). cos( 2k1 n1 / N 1 ). cos( 2k 2 n2 / N 2 )
DCT 2D ini banyak digunakan dalam pengolahan citra digital, karena data citra dinyatakan sebagai fungsi 2D. Contoh : Diketahui f(x,y) adalah sebagai berikut : 0
1
1
1
1
0
1
1
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
Bila digambarkan hasilnya adalah sebagai berikut :
Gambar 4.27. Contoh citra dalam f(x,y) DCT dari fungsi f(x,y) di atas adalah :
F (k1 , k 2 )
4
6
f (n , n
n1 0 n2 0
1
2
). cos( 2n1 k1 / 4). cos( 2n2 k 2 / 6)
75
Hasil dari DFT adalah sebagai berikut : 16
0
-2
0
-2
0
0
-1.27
0
0
0
4.73
0
0
0
0
0
0
0
-4.73
0
0
0
1.27
Secara Grafis dapat ditunjukkan bahwa :
Gambar 4.28. Contoh hasil DCT 2D
Pada dasarnya citra adalah fungsi 2D, sehingga transformasi fourier yang digunakan adalah transformasi fourier 2D. Langkah-langkah untuk membuat program transformasi cosinus pada citra menggunakan Visual Basic adalah sebagai berikut : (1) Buat Project baru dengan menekan , sehingga muncul tampilan project baru dengan form kosong yang kemudian buatlah form seperti gambar 4.29. (2) Isilah property pada setiap obyek dan form sebagai berikut: Obyek Property Nilai Form
Name
FormFourier
Caption
Transformasi Fourier
Picture
Nama file gambar
Appereance
Flat
Picture2
Appereance
Flat
Command1
Caption
Transformasi Fourier
Command3
Caption
Keluar
Label1
Caption
BAGIAN REAL
Background
&H8000000C&
Picture1
76
Gambar 4.28. Form untuk proses transformasi cosinus (3) Click bagian form yang kosong, dan isikan program inisialisasi proses berikut ini: Dim n1, n2, m1, m2 As Integer Dim x(400, 400) As Integer Dim xr(400, 400) As Single Private Sub Form_Load() m1 = 16: m2 = 16 End Sub (4) Click Command1, dan isikan program untuk proses perhitungan Transformasi Fourier menggunakan DFT berikut ini: Private Sub Command1_Click() n1 = 0 For i = 1 To Picture1.ScaleWidth Step 15 n1 = n1 + 1 n2 = 0 For j = 1 To Picture1.ScaleHeight Step 15 warna = Picture1.Point(i, j) r = warna And RGB(255, 0, 0) g = Int((warna And RGB(0, 255, 0)) / 256) b = Int(Int((warna And RGB(0, 0, 255)) / 256) / 256) n2 = n2 + 1 x(n1, n2) = Int((r + g + b) / 3) Picture1.PSet (i, j), RGB(x(n1, n2), x(n1, n2), x(n1, n2)) Next j Next i Picture2.ScaleHeight = m1 + 1 Picture2.ScaleWidth = m2 + 1 Picture3.ScaleHeight = m1 + 1 Picture3.ScaleWidth = m2 + 1 For i = 1 To m1 For j = 1 To m2 fr = 0 For k1 = 1 To n1 For k2 = 1 To n2
77 fr = fr + x(k1, k2) * Cos(6.28 * (i * k1 / m1 + j * k2 / m2)) Next k2 Next k1 w = 255 * Abs(fr) / (n1 * n2) Picture2.Line (i - 0.5, j - 0.5)-(i + 0.5, j + 0.5), RGB(w, w, w), BF w = 255 * Abs(fi) / (n1 * n2) xr(i, j) = fr Next j Next i End Sub (5) Click Command3, dan isikan program untuk proses keluar dari program berikut ini: Private Sub Command3_Click() Unload Me End Sub (6) Simpan form ini dengan nama formDCT seperti nama formnya, dan simpan projectnya dengan nama ProjectDCT.
Untuk mengubah ukuran window dari hasil transformasi fourier dapat dilakukan dengan mengganti nilai m1 dan m2 pada fungsi form load.
Gambar 4.29. Contoh transformasi fourier dengan 16x1
LATIHAN 1) Tuliskan definisi transformasi fourier pada citra, dan apa yang dapat diharapkan dengan melakukan transformasi fourier ini. 2) Pada citra-citra yang bergradiasi tinggi (mempunyai warna yang banyak), bagaimana hasil transformasi fouriernya ? 3) Pada citra-citra yang bergradiasi rendah (mempunyai warna yang sedikit atau berupa sketsa), bagaimana hasil transformasi fouriernya ? 4) Hitunglah transformasi fourier diskrit 2D dari data berikut ini : 7 5 3 0 5
4
2
1
3
2
3
1
78
0
1
1
0
5) Hitunglah transformasi cosinus dari data pada soal no 4. Apa perbedaan transformasi fourier dan transformasi cosinus ? 6) Dengan menggunakan program transformasi fourier yang sudah dibuat, gambarkan hasil transformasi fourier dari gambar-gambar berikut ini. Apa perbedaan hasil transformasi fourier dari keempat gambar di atas ?
Gambar 4.30. Contoh gambar untuk DFT dan DCT 7) Dengan menggunakan program transformasi cosinus yang sudah dibuat, gambarkan hasil transformasi cosinus dari gambar-gambar pada gambar 4.30 diatas. Apa perbedaan hasil transformasi cosinus dari keempat gambar di atas ?
79
DAFTAR PUSTAKA
Ahmad, Usman, Pengolahan Citra Digital & Teknik Pemrogramannya, Graha Ilmu, Yogyakarta, 2005. Away, Gunaidi Abdia. The Shortcut of Matlab programming, Informatika. Bandung, Juni 2006. Gonzalez, Rafael C. and Woods, Richard E., Digital Image Processing, Prentice Hall. New Jersey, 2002. Munir, A, Pengantar Pengolahan Citra, PT. Elek Media Komputindo Kelompok Gramedia. Jakarta,1992. Munir, Rinaldi., Pengolahan Citra Digital dengan Pendekatan Algoritmik, Informatika. Bandung, 2004. Sugiharto, Aris. Pemrograman GUI dengan Matlab, Andi. Yogyakarta, Januari 2006. Supandiman, Iman. Hematologi Klinik Edisi Revisi, Alumni. Jakarta, 2004. Usman, Koredianto. Perhitungan Sel Darah Merah Bertumpuk Berbasis Pengolahan Citra Digital Dengan Operasi Morfologi, Seminar Nasional Informatika 2008 (semnasIF 2008). Yogyakarta, Mei 2008. Wijaya, Marvin Ch & Agus Prijono. Pengolahan Citra Digital Menggunakan Matlab Image Processing Toolbox, Informatika. Bandung, November 2007. World Health Organization, Iron deficiency anemia assessment, prevention and control. A guide for programme managers.2001. http://id.wikipedia.org/wiki/Anemia http://www.koransindo.com/kesehatan.html
