BAB 2 LANDASAN TEORI
2.1
Teori Pengenalan Obyek Dalam kehidupan sehari-hari manusia melihat dan mengenali berbagai bentuk obyek disekitarnya. Obyek dikenali berdasarkan perbedaan titik-titik (dari sisi depan, samping dan belakang) pada tempat yang berbeda dan ukuran yang berbeda. Ada beberapa teori pengenalan obyek, masingmasing dengan cara pengenalan yang berbeda, diantaranya PFT (Particulate Feature Theory ) dan RBC (Recognition by Component). PFT merupakan teori pengenalan obyek dimana obyek hanya dilihat secara lokal saja, jika seluruh keistimewaan lokal dipenuhi maka obyek tetap dikenali dengan tidak mempertimbangkan hubungan antar komponen lokal yang seharusnya dipenuhi. Sebagai ilustrasinya, suatu obyek tetap dikenali sebagai manusia ketika komponen-komponennya dapat dikenali (adanya kepala, badan dan kaki) walaupun hubungan antar komponennya tidak sesuai dengan yang seharusnya (misalnya, kepala di bawah, kaki di tengah dan badan di atas) RBC adalah sebuah teori tentang pengenalan obyek pada manusia yang berkerja untuk keberhasilan identifikasi obyek meskipun terdapat perubahan dalam ukuran atau orientasi obyek. Dalam hal ini RBC merupakan penerapan pengenalan PFT tetapi dengan mempertimbangkan hubungan komponen-komponen lokal yang
7
harus dipenuhi agar suatu obyek dapat dikenali secara tepat. Jika dikenali sebagai manusia tetapi memiliki kaki di atas, kepala di bawah dan kepala di antaranya maka pengenalan tesebut adalah pengenalan yang salah. RBC tidak akan mengenali obyek seperti itu sebagai manusia, karena selain melakukan pengenalan lokal juga pengenalan secara global.
2.2
Pengenalan Computer Vision Computer Vision atau dapat juga disebut machine vision adalah ilmu pengetahuan yang mengembangkan teori-teori dan algoritma dimana informasi yang berguna mengenai dunia dapat secara otomatis diekstraksi dan dianalisis dari sebuah citra penelitian, sekumpulan citra, atau citra yang berurutan dari sebuah komputasi yang dibuat oleh komputer. Computer Vision berhubungan dengan otomatisasi interpretasi citra untuk membuat berbagai pengukuran yang objektif atau untuk meningkatkan visibilitas ketelitian. Computer Vision oleh beberapa ahli didefinisikan sebagai berikut: •
Michael C. Fairhurst (1995) Computer Vision sesuai dengan sifatnya, merupakan suatu subyek yang merangkul berbagai disiplin tradisional secara luas guna
mendasari
prinsip-prinsip
formalnya,
dan
dalam
mengembangkan suatu metodologi yang berlainan dari apa yang dimilikinya, pertama-tama harus menggabungkan dan secara berurutan membangun materi yang mendasari ini.
8
•
Adrian Low (1991) Computer Vision berhubungan dengan perolehan gambar, pemrosesan, klasifikasi, pengenalan, dan menjadi penggabungan, pengurutan pembuatan keputusan menuju pengenalan.
•
J.R.Parker (1994) Computer Vision menyangkut pengekstrakan informasi dari
citra, dan dalam identifikasi dan klasifikasi objek-objek dalam citra. Masalah umum dari Computer Vision adalah manusia tidak tahu bagaimana mereka mengenali objek-objek.
2.3
Citra
2.3.1 Pengertian Citra Pada Computer Vision •
Pearson (1991) Citra adalah representasi dua dimensi dari dunia visual, menyangkut berbagai macam disiplin ilmu yang mencakup seni, human vision, astronomi, tehnik, dsb. Citra merupakan suatu kumpulan piksel-piksel atau titik-titik yang berwarna yang berbentuk dua dimensi.
•
Michael C. Fairhust (1994) Citra adalah suatu fungsi 2 dimensi, dimana harga-harga fungsi tersebut f(x,y) pada koordinat spasial (x,y) di bidang x-y mendefinisikan suatu ukuran intensitas cahaya atau kecemerlangan titik tersebut.
9
•
Foley, James D (1996, p816) Citra adalah array dari nilai-nilai dimana sebuah nilai adalah sekumpulan angka yang mendeskripsikan atribut dari piksel di dalamnya.
•
J.R Parker (1994) Sebuah gambar yang tersimpan dalam komputer adalah 2 dimensi dan terbatas pada 2 dimensi itu, terdiri dari sejumlah warna atau tingkat keabuan. Gambar itu juga tersimpan dalam bentuk numerik. Representasi dari yang mengkarakterisasi semua properti di atas disebut raster image dan itu adalah cara yang paling umum dalam menyimpan gambar dalam komputer. Raster image juga dikenal sebagai format image bitmap, dimana format ini sering digunakan pada foto hasil kamera digital. Ukuran dari format ini adalah yang terbesar di antara format-format gambar lain seperti GIF (Graphic Interchange Format), JPEG (Joint Photografic Expert Group) dan PNG (Portable Network Grapfic), karena pada format ini tidak dilakukan kompresi.
•
Wolfram Research, Inc. (2002) Citra digital adalah sinyal diskrit 2 dimensi. Secara matematis, sinyal ini dapat direpresentasikkan sebagai fungsi dari variable-variabel 2 dimensi. Setiap elemen dari array disebut piksel.
•
Anonymous (2001) Suatu citra yang menggambarkan “dunia nyata” dianggap sebagai suatu fungsi dari 2 variabel, sebagai contoh, a(x,y) dimana a adalah brightness dari citra yang terletak pada posisi koordinat (x,y). Citra 2
10
dimensi a(x,y) ini dibagi menjadi N baris dan M kolom. Pemotongan dari baris dan kolom disebut piksel. Nilai yang terdapat pada koordinat [m,n] dengan {m=0,1,2,…,M-1} dan {n=0,1,2,…,N-1} adalah a[m,n]. Dalam beberapa kasus a(x,y) adalah sebuah fungsi dengan variabel seperti depth(z), color(λ), dan time(t). •
Windows XP Esperiences Glossary “A stored description of a graphic picture, either as a set of brightness and coler values of pixels or as a set of intructions for reprodusing the picture”. Dimana citra adalah deskripsi dari gambar grafik yang tersimpan sebagai kumpulan nilai warna dan tingkat cahaya dari piksel atau kumpulan intruksi untuk menghasilkan gambar. Berdasarkan pengertian citra pada Computer Vision di atas maka dapat disimpulkan bahwa citra pada Computer Vision adalah citra yang terdiri dari array 2 dimensi dari titik-titik piksel. Dimana definisi piksel itu sendiri menurut para ahli adalah:
Michael C. Fairhust (1995) Piksel adalah titik pada suatu citra yang telah didigitkan
secara spasial dan terdiri dari NxN sample yang terdistribusi secara sama.
J.R Parker (1994) Piksel adalah bagian array 2 dimensi dari suatu raster
image. Setiap piksel merepresentasikan warna atau tingkat keabuan
11
dan terletak pada posisi vertikal dan horisontal, atau yang lebih dikenal dengan baris dan kolom.
Murni (1992) Piksel (picture element) merupakan bagian terkecil dari
gambar yang mengandung informasi.
Adrian Low (1991) Piksel dianggap sebagai bagian terkecil dari citra. Dapat
berupa logic maupu fisik. Dengan kata lain dapat berupa lokasi elemen dari suatu citra atau menampilkan salah satu dari tingkat keabuan.
Oliver (1996) Piksel adalah titik yang merupakan penyusun dari citra yang
ditampilkan komputer.
2.3.2 Representasi Citra Menurut J.R Parker (1994), hal-hal yang harus dibuat agar suatu gambar dapat tampil pada komputer adalah resolusi. Setiap piksel merepresentasikan area kecil dari gambar aslinya dan tidak ada yang lebih kecil daripada piksel. Ukuran dari piksel bergantung pada jumlah piksel yang dibutuhkan untuk merepresentasikan gambar dan mendefinisikan resolusi dari suatu gambar. Sebuah gambar yang beresolusi tinggi, terdiri dari sejumlah besar piksel, dimana masing-masing menyimpan daerah kecil dari gambar. Sebuah gambar yang beresolusi rendah, terdiri dari
12
piksel yang berjumlah lebih sedikit, dimana masing-masing menyimpan daerah yang lebih besar dari setiap gambar. Pada image bitmap keanekaragaman warna diperoleh dari perpaduan nilai dari masing-masing unsur warna R, G, dan B dimana pada umumnya bernilai dari 0 sampai 255 atau bisa dikatakan merupakan format pixel 24-bit. Hal ini dikarenakan masing-masing unsur R, G, dan B mempunyai nilai sebesar 28 yang menghasilkan kombinasi warna sebanyak 28 x 28 x 28 = 224 = 16.777.216 warna. Menurur Oliver (1996, p566), pada model piksel RGB direpresentasikan dengan 24-bit warna. 8-bit untuk masing-masing R, G, dan B. Dengan ini masing-masing warna R, G, dan B memiliki 256 tingkatan intensitas, yang menghasilkan sekitar 16 juta kombinasi warna.
2.4
Pengolahan Citra Pengolahan citra adalah suatu pernyataan yang digunakan untuk menggambarkan operasi-operasi yang dilakukan pada suatu citra, dengan sasaran mencapai suatu tujuan tertentu. Menurut Murni (1992), pengolah citra merupakan peningkatan mutu citra yang bertujuan untuk memperbaiki mutu citra untuk memperoleh keindahan gambar, untuk kepentingan analisa citra, dan untuk mengkoreksi citra dari segala gangguan yang terjadi sewaktu perekaman data. Ada 3 bagian yaitu:
13
a. Peningkatan tingkat keabuan citra Bertujuan
meningkatkan
mutu
suatu
citra
melalui
perbaikan kontras. b. Filtering Bertujuan menggulangi gangguan seperti: •
Ganggguan bersifat frekuensi rendah, dimana terjadi proses pemerataan intensitas cahaya pada suatu titik sampel dengan titik-titik tetangganya.
•
Terjadinya gangguan berbentuk garis-garis sebagai akibat adanya kerusakan sebagian detector sensor.
•
Gangguan dalam bentuk bercak hitam yang acak.
c. Transformasi 2 dimensi dan koreksi geometri •
Transformasi 2 dimensi Umumnya untuk gangguan bersifat sederhana dan bersifat linier. Gangguan ini terjadi karena adanya: a. Pergeseran pusat b. Perubahan ukuran citra c. Perubahan orientase koordinat atau skewed Untuk mengatasinya maka diberlakukan transformasi 2 dimensi yaitu: a. Rotasi citra b. Skala citra
14
c. Translasi citra •
Koreksi geometri Meningkatkan mutu citra dengan ketelitian yang tinggi, misalnya untuk pembentukan peta dasar. Menurut Allan Hanbury (1998). Pengolahan citra secara kasar dibagi
menjadi 3 bagian, yaiutu : Image Compression, Image Enhancement and Restoration, Measurement Extraction. Image Compression mengurangi jumlah memori yang dibutuhkan untuk menampilkan gambar digital. Sedangkan Image Enhancement and Restoration berguna untuk perbaikan gambar. Image
Measurement
Extraction
operation
digunakan
untuk
mengambil informasi yang berguna dari citra tujuannya adalah untuk mencari distribusi luas dari objek yang terdapat pada citra tersebut. Langkah Pertama
adalah
memisahkan
objek
dengan
background,
dengan
menggunakan tehnik thresholding dimana meng-set nilai piksel yang di atas ( atas sebagai objek dan bawah sebagai background) menjadi warna putih, dan sisanya sebagai warna hitam. Menurut anonymous (2001) pengolahan citra adalah tekhnologi digital modern yang dapat memanipulasi sinyal multi dimensi dengan system yang berjangkauan dari sirkuit teknologi sederhana sampai paralel komputer canggih. Teknologi ini memanipulasi citra dan hasil manipulasi juga berupa citra.
15
2.4.1 Grayscale (tingkat keabuan) Mencari tingkat keabuan adalah proses pengubahan warna citra menjadi format warna yang hanya berdasarkan tingkat keabuan. Proses ini menghilangkan informasi hue dan saturation dari piksel dan hanya meninggalkan nilai brightness. Setiap piksel dari tingkat keabuan citra memiliki nilai brightness antara 0 (hitam) sampai 255 (putih). Foto hitam putih merupakan contoh umum dari model warna tingkat keabuan. Walaupun disebut hitam putih, sesungguhnya foto tersebut terbentuk dari banyak warna abu-abu yang berbeda.
Gambar 2.1 Nilai tingkat keabuan pada Adobe Photoshop
Tujuan perhitungan tingkat keabuan adalah memudahkan proses selanjutnya yaitu proses thresholding. Dengan algoritma perhitungan tingkat keabuan, piksel dari suatu citra yang mengandung warna-warna RGB (merah, hijau dan biru) diubah menjadi warna dalam berbagai tingkat keabuan ( I ) dengan menjumlahkan nilai warna merah, hijau dan biru kemudian dibagi tiga sehingga didapakan nila rata-rata dari ketiga warna. I = R+G+B 3
16
2.4.2 Binerisasi (Thresholding) Thresholding adalah proses penyederhanaan citra dari tingkat keabuan menjadi warna biner sehingga berdasarkan tingkat keabuannya piksel-piksel dibagi menjadi latar dan objek interest. Tujuan thresholding adalah untuk memisahkan objek dengan latar belakang. Hal ini dilakukan dengan cara mengubah intensitas piksel-piksel dari suatu citra yang ada menjadi hanya 2 intensitas yaitu hitam dan putih. Thresholding dapat dikatakan sebagai modifikasi tingkat keabuan yang mengubah intensitas-intensitas piksel yang ada, menjadi hanya 2 intensitas saja, yaitu hitam dan putih. Menurut Adrian Low (1998), thresholding mengubah dari tingkat keabuan yang lama ke tingkat keabuan yang baru (hanya 2) jadi contrast antar tingkat keabuan yang terpilih dapat ditingkatkan. Menurut J.R Parker (1994), thresholding adalah mengubah citra menjadi citra biner. Thresholding melihat pada setiap piksel kemudian memutuskannya apakah dibuat putih (255) atau hitam (0). Keputusan ini secara umum dibuat dengan cara membandingkan nilai numeric piksel dengan nilai tertentu yang disebut dengan threshold. Jika nilai piksel lebih kecil daripada threshold, maka piksel tersebut diubah menjadi 0; sebaliknya yang lain diubah menjadi 255. Hal ini juga dapat dilakukan sebaliknya. Menurut Antti Nurminen (1996), thresholding merupakan cara termudah untuk membagi citra tingkat keabuan. Dengan memilih suatu nilai tertentu, dan mengatus semua piksel yang bernilai di bawahnya menjadi
17
(putih), dan sumua piksel diatasnya menjadi 0 (hitam), maka akan didapatkan citra biner. Menurut Ma Yi (1996), thresholding merupakan suatu cara untuk menyingkirkan efek dari noise dan meningkatkan rasio signal-noise. Menurut
anonymous
(2001)
thresholding
merupakan
tehnik
memisahkan antara obyek dan latar belakang. Tehnik ini didasarkan pada konsep sederhana. Sebuah parameter θ disebut brightness threshold dipilih dan diterapkan pada citra a[m, n] sbb: If a[m, n] ≥ θ
a[m, n] = obyek = 1
Else
a[m, n] = background = 0
Jika hendak dipilih obyek berwarna hitam dan latar belakang putih maka : If a[m, n] < θ
a[m, n] = obyek = 1
Else
a[m, n] = background = 0
Outputnya adalah label obyek dan latar belakang yang dapat direpresentasikan sebagai variable Boolean “1” atau “0”. Secara prinsip, kondisi ini juga bias berlaku dengan property lain ketimbang hanya dengan brightness. Sebagai contoh, jika (Redness { a[m, n] >= θred ).
2.4.3 Filtering / Noise Removal Noise adalah warna piksel pada citra yang tidak memberikan informasi atau bahkan memberikan informasi yang salah/ informasi yang
18
tidak diinginkan. Penyebab terdapatnya noise pada citra sangat banyak, untuk kasus pengenal buah ini, penyebab noise antara lain: •
kotoran/kesalahan pada obyek asli, seperti tempelan-tempelan kertas pada buah, kesalahan pada tekhnik pengambilan citra.
•
jika citra inputan berasal dari hasil scan, kemungkinan terjadi kerusakan sebagian pada berkas/foto atau hardware yang digunakan.
2.5
Edge Detection Menurut Michael C. Fairhust (1995), penurunan batas outline dari obyek dalam sebuah citra sama saja halnya dengan menandai tepi yang membagi obyek itu sendiri dari latar belakangnya. Algoritma yang mengoperasikan demikian guna menandai piksel citra yang terletak pada suatu tepi ini disebut dengan deteksi tepi. Sebuah metode yang lazim menandakan adanya dikontinuitas intesitas yang menandai tepi obyek mencakup perhitungan sebuah gradien terhadap intesitas citra, berdasarkan bahwa suatu gradien intesitas local yang sangat tinggi menandai transisi intesitas mendadak, kelihatannya sangat kuat menyatakan terjadinya diskontinuitas tepi. Pada operator deteksi tepi, operator Sobel merupakan salah satu yang patut untuk dipertimbangkan, dimana operator ini mempunyai keuntungan dapat menampung tingkat keterpaduan penghalusan bertetangga, sebqgai tambahan terhadap fungsi utamanya dalam mengevaluasikan sebuah harga
19
gradien. Operator Sobel menggunakan jendela 3x3 dalam menghitung fungsi gradien G(x, y).
G(x. y) = √ [ { ( f(x+1, y+1) + 2f(x+1, y) + f(x+1, y-1)) – (f(x-1, y+1) + 2f(x-1, y) + f(x-1, y-1) ) }2 + { ( f(x-1, y-1) + 2f (x, y-1) + f(x+1, y-1) ) – ( f(x-1, y+1) + 2f(x,y+1) + f(x+1, y+1) ) }2 ] (x-1, y+1)
(x, y+1)
(x+1, y+1)
(x-1, y)
(x, y)
(x+1, y )
(x-1, y-1)
(x, y-1)
(x+1, y-1)
Gambar 2.2 Model jendela 3x3
Operator deteksi tepi yang telah diproses akan menghasilkan sebuah larik yang setiap titik diberi suatu harga (harga tepi) yang memperkirakan kemungkinan bahwa titik yang dimaksud terletak pada sebuah tepi dalam citra semula. Semakin tinggi harga tepi, semakin besar kemungkinan bahwa titik tersebut membentuk bagian dari tepi sebuah obyek, Kita perlu untuk memberi ambang batass untuk menumukan titik-tiitik tepi yang sebenarnya. G(x,y) > θ
→
titik (x,y) adalah sebuah titik tepi
G(x,y) ≤ θ
→
titik (x,y) bukanlah sebuah titik tepi
Dalam memberikan ambang batas, maka pemilihan ideal θ umunya tidak mencapai dalam praktek, memungkinkan munculnya harga θ yang
20
terlalu tinggi, atau harga θ yang terlalu rendah, sehingga gambar tepi yang dihasilkan menjadi tidak terlalu jelas. Outline yang dihasilkan oleh suatu urutan gradien operator / ambang tidak akan sempurna, keduanya mengandung tepi-tepi serta diskontinuitas yang palsu pada tepi yang berlaku, sehingga dibutuhkan langkah berikut yaitu penghalusan dan pelicinan. Menurut J.R. Parker (1994), edge detection adalah suatu cara yang berguna untuk mencari batas-batas dari obyek pada suatu citra. Tujuannya adalah untuk memisahkandan mengidentifikasi obyek pada suatu citra. Terdapat suatu prinsip dalam edge detection yaitu: “Batas antara dua wilayah (edge) ditandai oleh suatu perubahan mendadak pada tingkat keabuan”. Adalah
suatu
keharusan
pada
metode
edge
detection
untuk
mempertimbangkan semua arah yang mungkin. Pemikiran mask pada implementasi merupakan salah satu hal yang paling banyak disebut dalam masalah edge detection. Suatu mask adalah gambar kecil, biasanya 3x3 piksel, dimana piksel bagian tengah merupakan bagian yang diperiksa. Nilai dari setiap piksel pada mask dikalikan dengan nilai dari piksel citra yang berkorespondensi dengan orientasi terakhir. Nilai baru piksel yang berada di tengah adalah jumlah dari produk individual tadi. Mask dapat diaplikasikan pada semua piksel pada ditra yang pertama kali, kemudian hasilnya dapat diakumulasikan pada gambar berikutnya. Proses ini disebut discrete convolution. Jika suatu mask merepresentasikan sebuah operator edge detection maka hasil citranya akan jelas menunjukkan edge, sebaliknya bila tidak maka hasilnya adalah gelap atau hitam.
21
Menurut Luong Chi Mai (1999), edge detection amat berguna karena edge dari suatu citramengandung banyak informasi. Suatu edge dapat memberi tahu dimana suatu obyek berada, apa bentuk dan berapa ukurannya, dan teksturnya. Edge dari suatu citra adalah intesitas suatu citra dari nilai palig rendah sampai nilai paling tinggi. Menurut Adrian Low (1991), edge detection, merupakan cara pertama yang baik untuk menemukan bentuk geomtrik dari suatu obyek dalam citra. Sebuah edge detector yaitu operator Sobel, memberikan pengukuran seberapa pantas setiap piksel menjadi bagian dari edge yang sesungguhnya. Ukuran ini disebut juga gradient magnitude. Edge detection yang optimal harus memenuhi kondisi berikut: 1. Edge detection dapat menemukan seluruh edge yang ada, tidak ada satu pun edge yang hilang/terlewatkan. 2. Selisih jarak antara batasan piksel yang ditemukan dengan edge yang sesungguhnya harus seminimal mungkin 3. Jika hanya ada satu edge maka edge detection tidak boleh mendeteksinya sebagai piksel ganda.
2.6
Pengenal Pola Pengenalan pola merupakan “suatu fakta yang secara psikologis tidak bisa
dimengerti, tapi kita bisa meng-simulasikannya apabila kita mengerti sifat-sifat”. Pengenalan pola akan menghasilkan suatu pola yang kemudian akan diambil ciricirinya atau fitur-fiturnya. Menurut Parker (1994), fitur adalah semua pengukuran
22
yang dilakukan terhadap suatu citra, dapat berupa panjang, luas, keliling, roundness, kelengkungan, orientasi dan sebagainya. Fitur digunakan untuk mengkarakterisasi obyek-obyek dalam citra. Lebih baik mempergunakan banyak fitur yang mudah untuk dihitung secara akurat daripada fitur yang sedikit tapi kompleks dengan tingkat keakuratkan yang kecil. Cara untuk menemukan fitur dalam citra juga harus mendapat perhatian khusus karena hal tersebut tidaklah mudah dilakukan. Tehnik pengenalan pola terbagi menjadi 2 tehnik, yaitu prototype dan statistical method. Prototipe merupakan teknik pengenalan pola dimana dalam prosees klasifikasi membutuhkan basis data. Obyek yang akan diuji akan dibandingkan dengan ata yang dimiliki pada basis data. Apabila obyek tersebut dikenali maka proses klasifikasi dapat berjalan dengan baik. Sedangkan pada teknik statistical method terdapat 2 langkah penting, yaitu : ekstraksi fitur yang tugasnya mengumpulkan dan mengorganisasi yang data yang menyangkut obyek-obyek yang terdapat pada citra, kemudian hasilnya yang berupa vector akan diberikan pada Pattern classifier, kemudian Pattern classifier dengan menggunakan classifier akan melokasikan ke kelas yang paling cocok, serupa, atau paling tidak mendekati berdasarkan pole yang diterima dari ekstraksi fitur.
Input Pattern
Feature Extractor
Classifier
Gambar 2.3 Statistical pattern recognizer
23
Decision
Menurut Sing-Tze Bow (1984), pengenalan pola kita dapat membagi keseluruhan kerja dalam 3 tahap: •
perolehan data
•
data preprocessing
•
decision classification
Phase 1 Physical Variable
Object Acquisition
Phase 2
Data Prepocessing X (r) X (n)
Phase 3
Decision clasification
Gambar 2.4 Conceptual representation of a pattern recognition problem
Dalam fase akuisisi data analog dari dunia nyata akan dikumpulkan oleh transducer lalu dikonversi ke dalam format digital yang cocok untuk preprocessing yang dilakukan komputer. Dalam tahap ini, variabel-variabel fisik dikonversi menjadi data terukur yang mengindikasi intesitas cahaya dan transducernya adalah photocell. Data-data yang terukur kemudian akan dijadikan sebagai input fase dua (data preprocessing) dan kemudian dikumpulkan menjadi satu set characteristic fitur (x(r)) sebagai output. Fase ketiga sebenarnya adalah classifier dimana diddalamnya adalah sekumpulan dari decisionfunctions. Dengan kumpulan dari firut ini ( X(n) ) obyek tersebut akan diklasifikasi. Menurut Michael C. Fairhust (1995), pattern didefinisikan dengan sebuah vector pattern (X), yang mengandung elemen-elemen yang bersesuaian dengan ciriciri yang dapat diukur dari pattern atau data yang diamati.
24
Jadi X = {x1, x2, x3, …, xn} adalah suatu vector berdimensi ke-n, dimana x1, x2, x3, …, xn merupakan pengukuran karakteristik pattern, yang biasa diacu sebagai cir-ciri atau pendefini pattern. Pada system pengenal pola perlu dipikirkan mengenai keanggotaan pattern tersebut dalam suatu kelas tertentu atau kategori. Suatu kelas pattern dapat didefinisikan sebagai sekelompok pola yang mengambil bagian dalam beberapa karakteristik dan atribut yang sama. Lingkungan
Alat Sensor
Pemroses pola
Pengukuran ciri
Informasi Tambahan (bias)
Pengklasifikasi
Keputusan
Gambar 2.5 Kerangka umum sistem pengenalan pola
Menurut J.R. Parker (1994, semua program yang menampilkan pengenalan pola mempunyai 2 komponen utama. Pertama, ekstraksi fitur, bertugas untuk mengumpulkan dan mengorganisasi informasi yang menyangkut obyek pada citra. Kedua, classifier, menempatkan pattern dari obyek pada kelas berdasarkan fitur yang tersedia. Menurut Luong Chi Mai (1999), masalah pada pengenalan pola dapat didefinisiakan sebagai memberi label pada obyek. Idealnya adalah system diberi
25
citra yang terdiri dari obyek-obyek dan satu set dari label yang berkorespondensi ke model yang sudah dikenal oleh system, kemudian system tersebut memberikan label kepada daerah obyek pada citra. Dalam melaksanakan tugasnya sebuah pengenalan pola harus mempunyai beberapa komponen, yaitu : •
Database dari model Berisi semua model yang sudah dikenal oleh system.
•
Pendeteksi fitur Pendeteksi
fitur
menerapkan
operator
pada
citra
dan
mengidentifikasi lokasi dari fitur yang akan menolong dalam membentuk hipotesis obyek. •
2.7
Penghipotesis (hypothesizer)
Artificial Neural Network (Jaringan Saraf Tiruan) Berdasarkan pendapat Rao (1995, p2) Neural Network atau yang biasa
disebut juga Artificial neural network merupakan jaringan saraf tiruan dari otak manusia sehingga memiliki prinsip kerja yang sama dengan otak manusia. Pendapat dari Fausett (1993, p3) menyatakan “An artificial neural networks is an information-processing system that has certain perfomance characteristic in common with biological neural networks.” Atau menyatakan jaringan saraf tiruan adalah sistem pemrosesan informasi dengan mengikuti cara kerja jaringan saraf pada manusia.
26
Menurut Haykin (1999, p1), jaringan saraf tiruan adalah prosesor yang didistribusikan secara paralel dalam jumlah besar yang sebenarnya merupakan processing unit sederhana, memiliki kecenderungan alami untuk menyimpan pengetahuan (knowledge) yang sudag dilatih sebelumnya dan dapat dipakai kapan saja. Neural network memiliki sifat seperti otak manusia dalam dua macam bentuk, yaitu: •
diperoleh
knowledge
dari
jaringan
setelah
mealui
proses
pembelajaran (learning process) •
Hubungan antar-neuron yang juga dikenal sebagai sypnatic weight digunakan untuk menyimpan knowledge yang sudah diperoleh sebelumnya.
Knowledge sendiri didefinisikan (Haykin, 1999, p23) sebagai informasi yang disimpan
atau
model
yang
dipakai
oleh
seseorang
atau
mesin
untuk
menginterpretasikan, memperkirakan, dan memberikan respon yang tepat terhadap dunia luar. Jaringan saraf tiruan digunakan jika terdapat kondisi yang memerlukan: 1. Ketidaklinearan (nonlinearity) Jaringan saraf tiruan terbuat dari interkoneksi neuron non linear. Sifat ketidaklinearan ini terdistribusi dalam jaringan. Ketidaklinearan adalah properti yang sangat penting, terutama bila mekanisma fisik yang mendasarinya bertanggungjawab dalam menghasilkan sinyal input.
27
2. Input-output mapping Paradigma
pembelajaran
yang
popuer
sering
disebut
supervised learning yang melibatkan modifikasi dari bobot sinapsis sebuah jaringan neural dengan melibatkan contoh pelatihan yang terlabel. 3. Neurobiological Analogy Perancangan neural network dimotivasi oleh anatomi otak, dimana pemrosesan paralel toleransi kesalahan tidak hanya memungkinkan secara fisik, tapi juga secara kecepatan 4. Adaptivity Neural meyesuaikan
network bobot
mempunyai untuk
kemampuan
mengubah
dasar
lingkungan
untuk sekitar.
Neuralnetwork yang terlatih di lingkungan khusus dapat dilatih ulang dengan mudah dalam menghadapi perubahan yang sedikit dalam mengubah kondisi lingkungan yang sedang beroperasi. 5. Evidental response (respon yang jelas) Pada klasifikasi pola (pattern classification), neural network dapat dirancang untuk menyediakan informasi tidak hanya pola yang penting yang terpilih, tapi juga kepercayaan dalam pembuatan keputusan. Informasi yang terakhir ini dapat digunakan untuk menolal pola yang tidak jelas.
28
6. Fault tolerance (toleransi kesalahan) Ketika jaringan saraf tiruan diimplementasikan dalam bentuk hardware, kemungkinan untuk menjadi toleransi kesalahan yang terpadu
atau
kemampuan
dari
komputasi
yang
kuat
dan
perkerjaannya, dapat menurun secara perlahan di bawah kondisi pengoperasian yang kurang baik. Misal, bila sebuah neuron atau sambungan
koneksinya
rusak,
pemanggilan
kembali
pola
penyimpanannya rendah. Namun karena penyimpanan informasi dalam jaringan terdistribusi, kerusakan dapat diperluas sebelum respons jaringan diturunkan dengan sungguh-sungguh. Sebuah jaringan saraf buatan terdiri dari sejumlah elemen pemrosesan (processing element/PE) sederhana, yaitu sel/neuron yang terhubungkan satu sama lain dengan weight yang akan digunakan untuk menyelesaikan masalah dalam jaringan. Elemen pemrosesan ini menerima masukan berupa sinyal elektrik yang direpresentasikan dalam nilai numerik (angka). Berbeda dengan cara kerja otak manusia, pada jaringan saraf tiruan total sinyal yang diterima akan dihitung oleh fungsi aktivasi untuk menentukan besarnya kekuatan sinyal keluaran sebuah elemen pemrosesan. Jaringan saraf tiruan telah dikembangkan sebagai hasil generalisasi dari model matematika yang berasal dari saraf manusia dengan dasar asumsi sebagai berikut (Fausett, 1994, p3): a. Pemrosesan informasi terjadi pada banyak elemen sederhana (neuron). b. Sinyal dikirim antar neuro melalui connection link.
29
c. Setiap connection link mempunyai weight yang saling berhubungan. d. Setiap neuron mempunyai sebuah fungsi activasi dalam masukkan jaringan untuk menentukan sinyal keluaran
Gambar 2.6 Struktur sebuah Neuron Karakteristik dari jaringan saraf tiruan (Fausett, 1994,p3) adalah: 1. Pola koneksi antara neuron atau arsitektur 2. Kemampuan untuk menentukan weight pada koneksi (training, learning atau algoritma) 3. Fungsi aktivasinya.
2.7.1 Arsitektur Jaringan Saraf Tiruan Sebuah jaringan saraf tiruan terdiri dari sekumpulan elemen dimana satu subgroup melakukan perhitungan independent dan mengirimkan hasilnya kepada subgroup lainnya (Rao, 1993, P2). Neuron biasanya dioperasikan secara paralel atau dikonfigurasikan pada arsitektur yang regular. Neuron juga sering dihubungkan secara layer (lapisan). Setiap koneksi diwakilkan dengan angka yang disebut weight (bobot), yang berubah-ubah sesuai dengan input yang diberikan. Pada kenyataannya,
30
kebanyakkan JST harus dilatih untuk memperlajari pola dari masukkan-masukkan yang diberikan. Jaringan saraf tiruan terdiri dari tiga proses, yaitu : learning, networks storing, dan recalling. Setelah semua citra diproses dan fitur diekstrak, data akan dipelajari oleh Jaringan saraf tiruan melalui proses learning yang akan menghasilkan data yang direpresentasikan dalam bentuk nilai weight. Kemudian weight hasil learning yang mengandung data identitas buah dan karakteristik buah akan disimpan ke dalam sebuah file melalui proses network storing, yang dapat digunakan untuk proses recalling pada saat pengujian.
2.7.2 Backpropagation (Propagasi Balik) Backpropagasi merupakan metode pelatihan yang menggunakan multilayer perceptron untuk memecahkan masalah yang rumit dengan metode pelatihan terawasi, yaitu pelatihan yang menggunakan pasangan masukan dan keluaran dimana bobot yang akan dihitung, disesuaikan berdasarkan proses pelatihan yang dilakukan hingga mencapai target keluaran yang diinginkan. Backpropagation diperkenalkan pertama kali oleh G. E. Hinton, E. Rumehart dan R.J. Williams pada tahun 1986 sebagai sebuah teknik umum untuk melakukan pelatihan pada jaringan saraf tiruan berlayer banyak yang memegang peranan penting yang membuat jaringan saraf tiruan alat bantu untuk memecahkan banyak variasi masalah. Paradigma dan algoritma backpropagation dikembangkan oleh Paul Werbos. Menurut Rao (1995, p87), tipe network ini adalah yang paling umum digunakan karena memiliki prosedur pelatihan yang relatif mudah.
31
Haykin (1994, p156)
mengatajan backpropagation sendiri menggunakan memory yang labi sedikit daripada algoritma yang lainnya dan dapat memberikan hasil dengan tingkat kesalahan yang masih dapat diterima dengan kecepatan pemrosesan yang cukup cepat. Pada metode ini, jaringan tidak memiliki koneksi khusus untuk melakukan perhitungan mundur dari satu layer menuju layer sebelumnya. Namun error pada output layer akan dipropagasikan ke belakang menuju input layer.
2.7.2.1 Arsitektur Backpropagation Backpropagation merupakan jaringan saraf tiruan dengan multilayer, yang terdiri dari input layer (lapisan masukan), hidden layer (lapisan tersembunyi/ tengah), output layer (lapisan keluaran) (Fausett, 1994, p290). Banyaknya lapisan pada lapisan tengah dapat terdiri dari 1 atau lebih lapisan. Selain itu, lapisan keluaran dan lapisan tengah dapat mempunyai bias. Tiap lapisan pada backpropagation terdiri dari unit-unit yang saling terhubung antar lapisan. Jadi setiap neuron pada suatu lapisan dalam backpropagasi mendapat nilai masukan dari semua neuron pada lapisan sebelumnya beserta satu sinyal bias.
Gambar 2.7 Lapisan Neural Network 32
2.7.2.2 Metode kerja Backpropagation Backpropagasi memiliki metode pembelajaran supervised learning dimana lapisan masukan akan menerima pola masukan dan melakukan proses komputasi berdasarkan bobot awal yang diperoleh secara acak (random). Jika keluaran dari jeringan berbeda dengan target yang diharapkan maka jaringan melakukan penyesuaian terhadap bobot yang ada. Proses ini akan terus berlanjut hingga keluaran dari jaringan dan target yang diharapkan menjadi sama. Proses pembelajaran membutuhkan waktu yang lama hingga mencapai nilai tersebut. Oleh karena itu proses learning dibatasi dan akan berhenti jika perbedaan antara output dan target sudah mencapai nilai yang lebih kecil dari nilai toleransi (error rate). Besarnya penyesuaian bobot pada setiap siklus pembelajaran ditentukan oleh parameter yang disebut learning rate. Setelah tahap pembelajaran, jaringan saraf tiruan siap untuk memasuki tahap rcalling / searching yang merupakan proses dimana jaringan saraf tiruan menerima masukan dari dunia luar melalui lapisan masukan dan melalui komputasi pda masing-masing neuron yang terdapat di dalam lapisan akan dihasilkan keluaran pada lapisan keluaran Analogi pada otak manusia seperti menerima masukan berupa gambar buah kemudian otak manusia akan melakukan komputasi sehingga mengenali nama buah tersebut. Pada pelatihan backpropagation terdapat 2 fase, yaitu proses propagasi nilai aktivasi atau masukan dan proses penyesuaian dengan keluaran yang diharapkan (Fausett, 1994, p290). Proses propagasi nilai aktivasi tersebut adalah proses perubahan nilai bobot koneksi antar neuron yang menghubungkan lapisan jaringan,
33
baik itu antar lapisan masukan dengan lapisan tersembunyi, lapisan tersembunyi yang satu dengan yang lainnya, maupun bobot koneksi lapisan tersembunyi dengan lapisan keluaran. Nilai neuron dari setiap keluaran merupakan hasil dari fungsi aktivasi. Fungsi ini biasanya digunakan untuk menurunkan nilai aktivasi dan mengubahnya menjadi suatu nilai keluaran yang berarti. Kadang-kadang fungsi ini juga digunakan untuk menambahkan nilai bias. Fungsi sigmoid merupakan fungsi aktivasi yang digunakan dalam skripsi ini. Selain fungsi sigmoid biner ini, fungsi aktivasi lainnya adalah step, ramp, dan linear. Dikenal dua fungsi sigmoid, yaitu bipolar sigmoid dan binary sigmoid (sigmoid biner). Menurut Fausett (1994, p293) fungsi sigmoid memiliki dua jenis formula yang berbeda dalam hal rentang nilai yang dihasilkan :
1. ƒ(x) =
2
- 1, akan menghasilkan rentang nilai antara -1 sampai 1
1 + ℮ -x
Gambar 2.8 Fungsi Sigmoid Bipolar 2. ƒ(x) =
1
,akan menghasilkan rentang nilai antara 0 sampai 1
1+ ℮ -x
34
Gambar 2.9 Fungsi Sigmoid biner
Ciri-ciri node fungsi aktivasi adalah sebagai berikut : a. Kontinu b. Dapat dideteksi c. Turunan fungsi mudah dihitung d. Fungsi yang banyak digunakan: Fungsi sigmoid biner dan sigmoid bipolar.
Gambar 2.10 Model fungsi sigmoid biner
Proses penyesuaian dengan keluaran yang diharapkan adalah pengecekan nilai keluaran yang dihasilkan oleh jaringan dengan keluaran yang diharapkan
35
dengan batas toleransi kesalahan tertentu. Selama nilai keluaran tidak sesuai dengan keluaran yang diharapakan, maka proses pelatihan akan diulang kembali.
2.7.2.3 Tahapan Pelatihan Backpropagation Seperti halnya otak manusia membutuhkan proses learning (belajar) dimana otak akan menerima semua input dari semua indera disimpan dalam memory (ingatan manusia). Demikian juga pada jaringan saraf tiruan membutuhkan sebuah proses pembelajaran yang disebut proses pembelajaran/training/learing/storing. Haykin (1999, p50) mengatakan learning adalah proses dimana parameter bebas dari jaringan saraf tiruan diadaptasi melalui stimulasi dari lingkungan di mana jaringan tersebut diletakkan. Dalam proses pelatihan jaringan backpropagation ini, digunakan fungsi nilai ambang batas binary sigmoid. Sebelum melakukan proses pelatihan, terdapat beberapa parameter jaringan yang harus ditentukan dahulu (Fausett, 1994, p292) yaitu: a.
Tingkat pelatihan (learning rate) yang dilambangkan dengan alpha. Parameter ini harus diberikan dan mempunyai nilai positif kurang dari 1. Semakin tinggi nilainya, semakin cepat kemampuan jaringan untuk belajar, tetapi hal ini kurang baik karena error yang dihasilkan tidak merata.
b.
Toleransi kesalahan (error tolerance), semakin kecil maka jaringan akan
memiliki
nilai
bobot
memperpanjang waktu pelatihan.
36
yang
lebih
akurat,
tetapi
akan
c.
Nilai ambang batas atau bias (threshold value), dilambangkan dengan Theta. Parameter ini tidak harus diberikan (optional).
Secara garis besar langkah-langkah yang terjadi di dalam backpropagation pada saat proses pembelajaran terbagi menjadi tiga tahapan: 1. Feedforward Pada tahap ini setiap unit pada unit masukan menerima masukan dari fitus yang telah diekstrak, kemudian masukan tersebut akan diproses oleh unit dengan fungsi aktivasi yang digunakanuntuk menghasilkan keluaran. Hasil keluaran yang didapatkan akan diteruskan oleh unit masukan ke setiap unit pada unit di lapisan tengah pertama, kedua dan seterusnya. Setiap unit pada unit lapisan tengah akan menjumlahkan semua masukan yang dterima, kemudia memprosesnya dengan fungsi aktivasi yang digunakan untuk menghasilkan keluaran yang akan diteruskan ke unit lapisan tengah seterunya atau ke unit lapisan keluaran. Terakhir, setiap unit pada unit lapisan keluaran akan menjumlahkan semua masukan yang diterima dari unit lapisan tengah terakhir yang akan diproses dengan fungsi aktivasi yang di gunakan untuk mendapatkan sebuah nilai keluaran yang akan dibandingkan dengan nilai target yang telah ditentukan. 2. Backpropagation of the associated error Hasil perbandingan nilai keluaran yang dihasilkan oleh unit lapisan keluaran dengan nilai terget keluaran yang telah
37
ditentukan akan digunakan untuk menghitung error system (nilai mutlak dari selisih nilai keluaran pada unit lapisan keluaran dengan target keluara yang telah ditentukan). Kemudian nilai error tersebut digunakan untuk menghitung error di setiap unit pada lapisan tengah yang akan digunakan pada weight adjusment. 3. Adjustment of the weight Setelah didapatkan nilai error disetiap unit pada lapisan tengah semua bobot yang menghubungkan unit pada lapisan masukan denan unit lapisan tengah, unit lapisan tengah dengan unit lapisan tengah lain dan unit lapisan tengah dengan unit lapisan keluaran akan diperbaharui berdasarkan learning rate (kecepatan belajar pada jaringan) dan nilai error yang didapatkan disetiap unit.
2.7.2.4
Algoritma pelatihan backpropagation Berikut adalah algoritma untuk melakukan tahapan-tahapan pelatihan metode
backpropagation: Feedforward: Input dan output untuk input unit; FOR a = 0 TO x i_ina = feature ke-a yang diekstrak dari pola i_outa = i_ina END FOR
38
Input dan output untuk hidden units: FOR b = 0 TO y h_inb = 0 FOR a = 0 TO x+1 h_inb = h_inb + i_outa * iab END FOR h_outb =activation (h_inb) END FOR
Input dan output untuk output units: FOR c = 0 TO z o_inc = 0 FOR b = 0 TO y+1 o_inc = o_inc + h_outb * hbc END FOR o_outc = activation (o_inc) END FOR
Backpropagation of error Error input dan error output pada output units: FOR c = 0 TO z
39
o_errinc = (target keluaran dari pola yang ke-c – o_outc) * deactivation (o_inc) o_erroutc = o_errinc FOR b = 0 TO y+1 h_correctionbc = a * o_erroutc * h_outb dimana a adalah learning rate END FOR END FOR
Error input dan erro output pada hidden units: FOR b = 0 TO y h_errinb = FOR c = 0 TO z h_errinb = h_errinb + o_erroutc * hbc END FOR h_erroutb = h_errinb * deactivation (h_inb) FOR a = 0 To x+1 i_correctionab = a * h_erroutb * i_outa END FOR END FOR
Weight adjustment: Weight dari hidden units ke output units:
40
FOR b = 0 TO y+1 FOR c = 0 TO z Hbc = hbc + h_correctionbc END FOR END FOR Weight dari input units ke hidden units: FOR a = 0 TO x+1 FOR b = 0 TO y Iab = iab + i_correctionab END FOR END FOR
41