BAB 2 LANDASAN TEORI

7

BAB 2 LANDASAN TEORI

Pada bab ini akan dibahas mengenai teori pendukung dan penelitian sebelumnya yang berhubungan dengan metode ekstraksi fitur, serta metode klasifikasi Support Vector Machine dalam pengenalan citra huruf hijaiyah tulisan tangan. 2.1. Citra Citra merupakan suatu representasi (gambaran), kemiripan, atau imitasi dari suatu objek. Citra sebagai keluaran suatu sistem perekaman data dapat bersifat optik berupa foto, bersifat analog berupa sinyal-sinyal video seperti gambar pada monitor televisi, atau bersifat digital yang dapat langsung disimpan pada suatu media penyimpan (Sutoyo et al, 2009). Citra digital adalah larik angka-angka secara dua dimensional (Liu and Mason, 2009). Citra digital tersimpan dalam suatu bentuk larik (array) angka digital yang merupakan hasil kuantifikasi dari tingkat kecerahan masing-masing piksel penyusun citra tersebut. Citra digital dapat diklasifikasikan menjadi citra biner, citra keabuan dan citra warna. 2.1.1. Citra biner (binary image) Citra biner (binary image) adalah citra digital yang hanya memiliki 2 kemungkinan warna, yaitu hitam dan putih. Citra biner disebut juga dengan citra W&B (White&Black) atau citra monokrom. Hanya dibutuhkan 1 bit untuk mewakili nilai setiap piksel dari citra biner. Pembentukan citra biner memerlukan nilai batas keabuan yang akan digunakan sebagai nilai patokan. Piksel dengan derajat keabuan lebih besar dari nilai batas akan diberi nilai 1 dan sebaliknya piksel dengan derajat keabuan lebih kecil dari nilai batas akan diberi nilai 0. Fungsi dari binerisasi sendiri adalah untuk

Universitas Sumatera Utara

8

mempermudah proses pengenalan pola, karena pola akan lebih mudah terdeteksi pada citra yang mengandung lebih sedikit warna. Contoh citra biner dan representasi dapat dilihat pada Gambar 2.1 dan Gambar 2.2.

Gambar 2.1 citra huruf T (Sutoyo,2009)

Gambar 2.2 representasi citra biner dari huruf T (Sutoyo,2009)

2.1.2. Citra keabuan (grayscale image) Citra keabuan yaitu citra yang pixel-nya mempresentasikan derajat keabuan atau intensitas warna putih. Citra grayscale memiliki banyak variasi nuansa abu-abu sehingga berbeda dengan citra hitam-putih seperti terlihat pada Gambar 2.3 dan 2.4. Jumlah bit yang diperlukan untuk tiap piksel menentukan jumlah tingkat keabuan yang tersedia. Tingkat keabuan yang tersedia pada citra grayscale adalah 28 atau 256.

Gambar2.3 citra hitam-putih (Genta, 2010)

Gambar 2.4 citra grayscale (Genta, 2010)


9

2.1.3. Citra warna (color image) Citra warna merupakan citra yang nilai pixel-nya mempresentasikan warna tertentu berdasarkan jumlah dari bit per-pixel citra yang bersangkutan. Setiap pixel pada citra warna mewakili warna yang merupakan kombinasi dari 3 warna (RGB = Red, Green, Blue). Setiap warna dasar menggunakan penyimpanan 8 bit = 1 byte (nilai maksimum 255 warna) sehingga satu pixel pada citra warna diwakili oleh 3 byte dengan tingkatan warna yang tersedia adalah 256. Jadi untuk tiga warna dasar pada setiap piksel memiliki kombinasi warna sebanyak 224 atau sekitar 16777216. Contoh citra warna ditunjukkan pada Gambar 2.5

Gambar2.5 citra warna (Genta,2010)

2.2. Format Citra Digital Ada beberapa format citra digital, antara lain: BMP, PNG, JPG, GIF dan sebagainya. Masing-masing format mempunyai perbedaan satu dengan yang lain terutama pada header file. Namun ada beberapa yang mempunyai kesamaan, yaitu penggunaan palette untuk penentuan warna piksel.

2.2.1. Bitmap (.bmp) Bitmap adalah representasi dari citra grafis yang terdiri dari susunan titik yang tersimpan di memori komputer. Dikembangkan oleh Microsoft dan nilai setiap titik diawali oleh satu bit data untuk gambar hitam putih, atau lebih bagi gambar berwarna. File format BMP (Windows bitmap) menangani file grafik di sistem operasi Microsoft


10

Windows. Pada umumnya file bmp tidak di kompresi sehingga memiliki ukuran yang sangat besar.

2.2.2 GIF GIF adalah format gambar asli yang dikompres dengan CompuServe. Bitmap dengan jenis ini mendukung 256 warna dan bitmap ini juga sangat popular dalam internet. Format GIF hanya dapat menyimpan gambar dalam 8 bit dan hanya mampu digunakan mode grayscale, bitmap, dan index color.

2.2.3 JPEG JPEG merupakan skema kompresi file bitmap yang banyak digunakan untuk menyimpan gambar-gambar dengan ukuran lebih kecil. Format citra JPEG ini memiliki karakteristik gambar tersendiri antara lain memiliki ekstensi .jpg atau .jpeg. mampu menanyangkan warna dengan kedalaman 24-bit true color. Umumnya format citra ini digunakan untuk menyimpan gambar-gambar hasil foto.

2.3. Pengolahan Citra Pengolahan citra merupakan proses memperbaiki kualitas citra, transformasi citra, melakukan pemilihan ciri citra untuk tujuan analisis dan mendapatkan kualitas citra yang lebih baik (Sutoyo, 2009). Tujuan dari pengolahan citra adalah bagaimana mengolah citra sebaik mungkin sehingga dapat memberikan informasi baru yang lebih bermanfaat. Beberapa teknik pengolahan citra yang digunakan adalah sebagai berikut.

2.3.1. Thresholding Thresholding merupakan suatu proses mengubah citra berderajat keabuan menjadi citra biner atau hitam putih sehingga dapat diketahui daerah mana yang termasuk obyek dan background dari citra secara jelas (Evan, 2010). Citra hasil thresholding biasanya digunakan lebih lanjut untuk proses pengenalan obyek serta ekstraksi fitur. Proses thresholding menggunakan nilai batas (threshold) untuk mengubah nilai piksel pada citra keabuan menjadi hitam atau putih. Jika nilai piksel pada citra keabuan lebih besar dari threshold, maka nilai piksel akan


11

diganti dengan 1 (putih), jika nilai piksel pada citra keabuan lebih kecil dari threshold maka nilai piksel akan diganti dengan 0 (hitam). Citra hasil thresholding dapat didefinisikan sebagaimana Persamaan 2.2.

(2.1)

Dimana : g(x,y) = piksel citra hasil binerisasi f(x,y) = piksel citra asal T

= nilai threshold

Adapun citra hasil threshoding seperti pada Gambar 2.6

(a)

(b)

Gambar 2.6 (a) citra grayscale , (b) citra threshold.

2.3.2. Cropping Cropping merupakan proses pemotongan citra pada koordinat tertentu pada area citra. Dalam memotong bagian dari citra digunakan dua koordinat, yaitu koordinat awal yang merupakan awal koordinat bagi citra hasil pemotongan dan koordinat akhir yang merupakan titik koordinat akhir dari citra hasil pemotongan. Sehingga akan membentuk bangun segi empat yang mana tiap-tiap pixel yang ada pada area koordinat tertentu akan disimpan dalam citra yang baru. Proses cropping terlihat pada Gambar 2.7. Cropping dapat digunakan untuk menambah fokus pada objek, membuang bagian citra yang tidak diperlukan, memperbesar area tertentu pada citra, mengubah orientasi citra, dan mengubah aspect ratio dari sebuah citra.


12

Gambar 2.7 proses cropping (Brigida,2010)

2.3.3. Normalisasi Normalisasi adalah proses mengubah ukuran citra, baik menambah atau mengurangi, menjadi ukuran yang ditentukan tanpa menghilangkan informasi penting dari citra tersebut (Sharma et. al, 2012). Dengan adanya proses normalisasi maka ukuran semua citra yang akan diproses menjadi seragam.

2.3.4. Thinning Proses thinning (penipisan) merupakan operasi pemrosesan reduksi citra biner menjadi rangka (skeleton) yang menghampiri garis sumbu objek. Thinning bertujuan untuk mengurangi bagian yang tidak perlu (redundant) sehingga dihasilkan informasi yang esensial saja. Pola penipisan harus tetap mempunyai bentuk yang menyerupai pola asalnya. Proses thinning dapat dilihat pada Gambar 2.8.

(a)

(b)

Gambar 2.8 (a) citra huruf A hasil scanning citra (b) citra huruf A setelah proses thinning.


13

Citra hitam putih yang diambil sebagai masukan, akan ditipiskan terlebih dahulu. Proses penipisan ini merupakan proses menghilangkan piksel-piksel hitam (mengubah menjadi piksel putih) pada tepi-tepi pola. Penipisan ini dilakukan dengan mengurangi ketebalan sebuah objek hingga ke batas minimum yang di perlukan oleh program sehingga dapat dikenali. Citra hasil penipisan ini akan digunakan sebagai masukan untuk dibandingkan dengan target yang telah disediakan. Citra hasil dari penipisan biasanya disebut dengan skeleton.

2.4. Ekstraksi Fitur Ekstraksi fitur adalah proses pengukuran terhadap data yang telah dinormalisasi untuk membentuk sebuah nilai fitur. Nilai fitur digunakan oleh pengklasifikasi untuk mengenali

unit

masukan

dengan

unit

target

keluaran

dan

memudahkan

pengklasifikasian karena nilai ini mudah untuk dibedakan (Pradeep et. al, 2011). Pada penelitian ini , penulis menggunakan metode ekstraksi zoning.

2.4.1. Ekstraksi Ciri Zoning Zoning adalah salah satu ekstraksi fitur yang paling popular dan sederhana untuk diimplementasikan (Sharma et. al, 2012). Sistem optical character recognition (OCR) komersil yang dikembangkan oleh CALERA menggunakan metode zoning pada citra biner (Bosker, 1992). Setiap citra dibagi menjadi NxM zona dan dari setiap zona tersebut dihitung nilai fitur sehingga didapatkan fitur dengan panjang NxM. Salah satu cara menghitung nilai fitur setiap zona adalah dengan menghitung jumlah piksel hitam setiap zona dan membaginya dengan jumlah piksel hitam terbanyak pada yang terdapat pada salah satu zona. Contoh pembagian 3 zona pada citra biner dapat dilihat pada gambar 2.9.


14

Zona 1 (atas)

Zona 2 (tengah)

Zona 3 (bawah)

Gambar 2.9 Pembagian zona pada citra biner (Isnan,2012)

Ada beberapa algoritme untuk metode ekstraksi ciri zoning, di antaranya metode ekstraksi ciri jarak metrik ICZ (image centroid and zone), metode ekstraksi ciri jarak metrik ZCZ (zone centroid and zone). Kedua algoritma tersebut menggunakan citra digital sebagai input dan menghasilkan fitur untuk klasifikasi dan pengenalan sebagai output-nya. Berikut merupakan tahapan dalam proses ekstraksi ciri ICZ, ZCZ .(Rajashekararadhya dan Ranjan 2008). Algoritme 1: Image Centroid and Zone (ICZ) berdasarkan jarak metrik. Tahapan 1. Hitung centroid dari citra masukan. 2. Bagi citra masukan ke dalam n zona yang sama. 3.

Hitung jarak antara centroid citra dengan masing-masing piksel yang ada dalam zona

4. Ulangi langkah ke 3 untuk setiap piksel yang ada di zona. 5. Hitung rata-rata jarak antara titik-titik tersebut. 6. Ulangi langkah-langkah tersebut untuk keseluruhan zona. 7. Hasilnya adalah n fitur yang akan digunakan dalam klasifikasi dan pengenalan .


15

Algoritma 2: Zone Centroid Zone (ZCZ) berdasarkan jarak metrik. 1. Bagi citra masukan ke dalam sejumlah n bagian yang sama . 2. Hitung centroid dari masing-masing zona. 3. Hitung jarak antara centroid masing-masing zona dan piksel yang ada di zona. 4. Ulangi langkah ke 3 untuk seluruh piksel yang ada di zona. 5.

Hitung rata-rata jarak antara titik-titik tersebut.

6. Ulangi langkah 3-7 untuk setiap zona secara berurutan. 7.

Hasilnya adalah n fitur yang akan digunakan dalam klasifikasi dan pengenalan

2.5. Support Vector Machine (SVM) Support Vector Machine (SVM) adalah suatu teknik untuk melakukan prediksi, baik dalam kasus klasifikasi maupun regresi (Santoso, 2007). SVM berada dalam satu kelas dengan Artificial Neural Network (ANN) dalam hal fungsi dan kondisi permasalahan yang bisa diselesaikan. Keduanya masuk dalam kelas supervised learning. SVM akan mencari hyperplane (bidang pemisah) terbaik yang memisahkan data dari satu permasalahan. Menurut Osuna et al (1997) data dikatakan linearly separable jika permasalahan tersebut dapat dicari pasangan (w, b). Linearly separable data merupakan data yang dapat dipisahkan secara linier. Support Vector Mahine menggunakan model linear sebagai decision boundary dengan bentuk umum sebagai berikut : y(x) = w . x + b

Dimana

(2.2)

w = parameter bobot x = vektor input (label kelas) b = bias

Misalkan {𝑥1 , … , 𝑥𝑛 } merupakan data set dan 𝑦1 € {+1 , -1} merupakan label kelas data dari 𝑥𝑖 . Pada Gambar 2.10 dapat dilihat berbagai alternatif bidang pemisah yang dapat memisahkan semua data set sesuai dengan kelasnya (a). Namun, bidang


16

pemisah terbaik tidak hanya dapat memisahkan data tetapi juga memiliki margin paling besar.

(a)

(b)

Gambar 2.10 (a) alternatif bidang pemisah (b) hyperplane terbaik dengan margin (m) terbesar (Krisantus,2007)

Data yang berada atau terdekat pada bidang pemisah ini disebut support vector. Pada Gambar 2.7 (b) dua kelas dipisahkan oleh sepasang bidang pembatas yang sejajar. Bidang pembatas pertama membatasi kelas pertama (kotak) sedangkan bidang pembatas kedua membatasi kelas kedua (lingkaran), sehingga pattern 𝑥𝑖 yang termasuk kelas 1(sampel negatif) memenuhi pertidaksamaan : 𝑥𝑖 . 𝑤 + 𝑏 ≤ −1

(2.3)

Sedangkan pattern 𝑥𝑖 yang termasuk kelas 2 (sampel positif) dapat dirumuskan sebagai pattern yang memenuhi pertidaksamaan : 𝑥𝑖 . 𝑤 + 𝑏 ≤ +1 Dimana

(2.4)

w = normal bidang (parameter bobot) x = label kelas (vektor input) b = posisi bidang relatif terhadap pusat koordinat (bias)


17

Kedua kelas dapat terpisah secara sempurna oleh bidang pemisah (classifier/Hyperplane). Hyperplane pemisah terbaik antara kedua kelas dapat ditemukan dengan mengukur margin Hyperplane tersebut dan mencari titik maksimalnya. Margin merupakan jarak antara Hyperplane tersebut dengan pattern terdekat dari masing-masing kelas. Nilai margin (jarak) antara hyperplane (berdasarkan rumus jarak ke titik pusat adalah : 1−𝑏−( −1−𝑏 ) 𝑤

=

2

(2.5)

|𝑤|

Dengan mengalikan b dan w dengan sebuah konstanta, akan menghasilkan nilai margin yang dikalikan dengan konstanta yang sama. SVM menggunakan konsep margin yang didefinisikan sebagai jarak terdekat antara decision boundary dengan sembarang data training, dengan memaksimumkan nilai margin maka akan didapat suatu decision boundary tertentu. Margin terbesar didapat dengan memaksimalkan nilai jarak antara hyperplane dan titik terdekatnya yaitu

1 |𝑤|

. Maka pencarian

hyperplane terbaik dengan nilai margin terbesar dapat dirumuskan menjadi masalah optimasi

konstrain

yaitu

mencari

titik

minimal

persamaan

(2.6)

dengan

memperhatikan constraint persamaan (2.7). 1

min 2 |𝑤|2

(2.6)

𝑦𝑖 (𝑥𝑖 . w + b)-1 ≥ 0

(2.7)

Menggunakan metode lagrange multiplier dapat lebih mudah menyelesaikan permasalahan optimasi konstrain dalam mencari titik minimal dengan menggunakan tambahan konstrain 𝛼𝑖 yang disebut sebagai lagrange multiplier dalam fungsi sebagai berikut : (2.8)

Keterangan : 𝛼𝑖 bernilai nol atau positif ( 𝛼𝑖 ≥ 0 ). Dengan meminimumkan Lp terhadap w dan b maka :


18

𝜕 𝜕𝑏

𝐿𝑃 (w,b,α) = 0

∑𝑛𝑖=1 𝛼𝑖 𝑦𝑖 = 0

(2.9)

dan dari 𝜕 𝜕𝑤

𝐿𝑃 (w,b,α) = 0

w = ∑𝑛𝑖=1 𝛼𝑖 𝑦𝑖 𝑥𝑖 = 0

(2.10)

Vektor w sering bernilai besar hingga tak terhingga, tetapi nilai 𝛼𝑖 terhingga. Oleh karena itu formula lagrangian Lp (prima problem) diubah kedalam dual problem 𝐿𝐷 dengan mensubstitusikan persamaan 2.10 ke Lp sehingga diperoleh dual problem 𝐿𝐷 dengan konstrain yang berbeda. 𝐿𝐷 (𝛼) = ∑𝑛𝑖=1 𝛼𝑖 -

1 2

∑𝑛𝑖=1 ,𝑗−1 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 𝑥𝑖 𝑥𝑗

(2.11)

Pencarian hyperplane terbaik dapat dirumuskan sebagai berikut :

(2.12) Dari hasil perhitungan ini diperoleh 𝛼𝑖 > 0 (support vector) , data yang memiliki nilai 𝛼𝑖 yang positif inilah yang berperan pada model decision boundary, sehingga kelas dari data pengujian x dapat ditentukan berdasarkan nilai dari fungsi keputusan: f (𝑥𝑑 ) = ∑𝑛𝑠 𝑖=1 𝛼𝑖 𝑦𝑖 𝑥𝑖 𝑥𝑑 + 𝑏

(2.13)

Dimana : 𝑥𝑖 = support vector 𝑥𝑑 = data yang akan diklasifikasi ns = jumlah support vector

Selain dapat menyelesaikan permasalahan linear. SVM dirancang dapat menyelesaikan permasalahan non linear dengan memetakan permasalahan tersebut ke


19

dalam ruang ciri berdimensi lebih tinggi kemudian diterapkan klasifikasi linear dalam ruang tersebut.

2.5.1 Contoh Kasus Contoh kasus pertama SVM dengan dua kelas dan empat data pada Tabel 2.1 berikut ini merupakan problem linier yang akan ditentukan fungsi klasifikasi (hyperpalane). Adapun formulasi masalahnya adalah sebagai berikut :

Tabel 2.1 Contoh kasus nilai fitur dan kelas Kasus X1 1 -1 1 -1

X2 1 1 -1 -1

Kelas (y) 1 -1 -1 -1

Langkah-langkah yang dilakukan dalam menentukan fungsi klasifikasi(hyperplane) dari contoh kasus diatas adalah : 

Penentuan variabel bobot dari fitur ciri kasus. Terdapat dua fitur ciri pada tabel 3.1 yaitu x1, x2 sehingga w (bobot) akan memiliki 2 fitur yaitu w1 dan w2 .



Optimasi masalah dengan meminimal kan nilai sebagai berikut : min

1 2

(𝑤12 + 𝑤22 ) + C (t1 + t2 + t3 + t4)

Dengan syarat sebagai berikut : yi (w.xi + b) ≥ 1

i = 1, 2, 3, …, N

Konstrain : w1 + w2 + b + t1 ≥ 1 w1 - w2 - b + t2 ≥ 1 -w1 + w2 - b + t3 ≥ 1 w1 + w2 - b + t4 ≥ 1 t1 , t2 , t3, t4 ≥ 0 Karena merupakan kasus klasifikasi linear, maka bisa dipastikan nilai variabel slack ti = 0. Jadi bias dimasukkan nilai C = 0. Setelah menyelesaikan problem optimasi diatas, maka didapat solusi :


20

w1 = 1 , w2 = 1 , b = 1 Jadi persamaan fungsi pemisahnya adalah : f(x) = x1 + x2 -1 Sehingga semua nilai f(x) < 0 diberi label -1 dan f(x) > 0 diberi laber +1.

2.6. Penelitian Terdahulu Penelitian tentang pengenalan pola telah dilakukan dengan menggunakan beberapa metode. Variasi metode ekstraksi ciri yang digunakan adalah metode yang diajukan oleh Rajashekararadhya & Ranjan (2008), yaitu Image Centroid and Zone (ICZ), Zone Centroid and Zone (ZCZ), dan gabungan ICZ dan ZCZ. Dalam penelitian ini diperoleh tingkat pengenalan rata-rata karakter angka Kannada, Telugu, Tamil, dan Malayalam yang di tulis tangan diatas 90% dengan melakukan penggabungan metode ekstraksi ciri ICZ dan ZCZ untuk klasifikasi menggunakan JST dan KNN. Tingkat pengenalan menggunakan metode zoning ini juga mencapai 87% dengan menggabungkan metode ekstraksi ciri diagonal based untuk peningkatan nilai fitur jaringan propagasi balik pada pengenalan angka tulisan tangan oleh Nanda (2012). Support Vector Machine (SVM) merupakan metode klasifikasi yang mencari support vector terbaik yang memisahkan dua buah class dengan margin terbesar. SVM secara konseptual merupakan classifier yang bersifat linier tetapi dapat dimodifikasi dengan menggunakan kernel (fungsi yang memudahkan proses pengklasifikasian data) sehingga dapat menyelesaikan permasalahan yang bersifat tidak linier (non linier). Metode ini telah menyelesaikan kasus pengklasifikasi dan memprediksi angkutan udara jenis penerbangan internasional di Banda Aceh (Sayed,2011) dengan tingkat akurasi model hingga 84,31%.

Tabel 2.2. Penelitian terdahulu No.

Peneliti / Tahun

1.

Rajashekararadhya & Ranjan (2008)

2.

Sayed (2011)

3.

Nanda (2012)

Metode yang digunakan Support Vector Machine K-Nearet Neighbor Support Vector Machine

Zoning dan Diagonal Based Feature Extraction

Akurasi 90% 84,31% 87%


BAB 2 LANDASAN TEORI

Recommend Documents