PENGENALAN POLA HURUF HIJAIYAH TULISAN TANGAN MENGGUNAKAN LOGIKA FUZZY DENGAN JARINGAN SYARAF TIRUAN BACKPROPAGATION
MAKALAH Disusun Sebagai Salah Satu Syarat Menyelesaikan Jenjang Strata 1 Pada Jurusan Teknik Informatika Fakultas Komunikasi dan Informatika Universitas Muhammadiyah Surakarta
Oleh : Imam Anggara Kanta Pembimbing I : Fajar Suryawan, S.T.,M.Eng, Ph.D Pembimbing II : Aris Rakhmadi, S.T., M.Eng
PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS KOMUNIKASI DAN INFORMATIKA UNIVERSITAS MUHAMMADIYAH SURAKARTA 2013
HALAMAN PENGESAIIAN Publikasi ilmiah dengan judul
lliiaiiah Tulfirin tan$an Minlilgrnrkntr LitEi[a
Pstgenalan Pola Huruf
Eur.y dengan Jaringan Syaraf Tiruan Backpropagation Yang dipersiapkan dan dizusun oleh
:
flffi** )kiiiadT&iii,' L200080176 Telah disetujui Pada
Hari Tanggal Pembimbing
:
: ;
I
Fajar SurErwan S.T..M.Ens. Ph.D
.
NIPNTK,g}4
NIPA.{IK:983
Slaipsi ini telah dit€rima sebagai salah satu persyaratan
uutB qrysusqleh ee!a!
$e{ia$e
Tanggal
;*L*-.
Pengenalan Pola Huruf Hijaiyah Tulisan Tangan Menggunakan Logika Fuzzy dengan Jaringan Syaraf Tiruan Backpropagation Imam Anggara Kanta Teknik Informatika, Fakultas Komunikasi dan Informatika Universitas Muhammadiyah Surakarta E-Mail :
[email protected]
ABSTRAKSI Bagi manusia tentunya tidaklah sulit untuk mengenali sebuah huruf tulisan tangan walaupun berbeda-beda bentuk antara penulis satu dengan penulis lain. Namun hal itu menjadi sulit jika mesin yang berusaha untuk mengenali tulisan tangan dari manusia yang berbeda-beda antara satu dan yang lainnya. Dalam kasus ini lebih sulit jika tulisan tangan yang akan dikenali yaitu tulisan huruf Hijaiyah. Dari permasalahan di atas maka tugas akhir ini akan mencoba teknik lain yang diharapkan lebih efektif guna mengenali huruf tulisan tangan. Metode pengenalan yang diangkat dalam tugas akhir ini adalah dengan menggunakan logika fuzzy dimana sebuah huruf dibagi menjadi beberapa bagian yang disebut segmen untuk menemukan parameter titik awal, titik ujung, dan titik percabangan. Sedangkan untuk proses klasifikasi menggunakan metode jaringan syaraf tiruan propagasi balik (back propagation). Dalam penelitian kali ini bisa disimpulkan bahwa gabungan antara logika fuzzy dengan jaringan syaraf tiruan backpropagation dapat melakukan pengenalan huruf hijaiyah dengan recognition rate sebesar 69%. Pengenalan tersebut didapat dengan membuat beberapa parameter untuk menentukan ciri dari masing – masing huruf tersebut sehingga mempunyai ciri identik untuk membedakan antar huruf. Kata Kunci : Fuzzy Logic, Backpropagation, Pattern Recognition
efektif
Pendahuluan
dalam
pengenalan
huruf
Bagi manusia tentunya tidaklah
hijayah tulisan tangan. Dalam logika
sulit untuk mengenali sebuah huruf
fuzzy tulisan dianggap sebuah graf
tulisan tangan walaupun berbeda-beda
berarah yang mempunyai node dan
bentuk antara penulis satu dengan penulis
edge.
lain. Namun hal itu menjadi sulit jika
klasifikasi
mesin yang berusaha untuk mengenali
syaraf tiruan backpropagation.
tulisan
yang
METODE PENELITIAN
yang
A. Waktu Penelitian
tangan
berbeda-beda
dari
antara
manusia satu
dan
lainnya. Dalam kasus ini lebih sulit jika
Untuk
selanjutnya
menggunakan
Huruf
tulisan huruf Hijaiyah .
Menggunakan Logika
tentang
bagaimana
jaringan
Proses penelitian Pengenalan Pola
tulisan tangan yang akan dikenali yaitu
Saat ini telah banyak penelitian
proses
Hijaiyah
Tulisan
Tangan
Fuzzy Dengan
Jaringan Syaraf Tiruan Backpropagation
melakukan
ini dilaksanakan dalam waktu + 6 bulan,
pengenalan/identifikasi tulisan tangan.
yang dimulai pada bulan Desember 2012
Banyak pula metode yang digunakan
sampai dengan Mei 2013 di Program
seperti
Studi Teknik Informatika Universitas
pencocokan
genetika,
citra,
algoritma
dan pendekatan sintaktik.
Namun metode-metode tersebut kurang
Muhammadiyah Surakarta. B. Peralatan Utama
efektif untuk mengenali tulisan tangan
Peralatan yang dibutuhkan untuk
yang sangat kompleks terutama dari segi
mendukung pelaksanaan penelitian dan
bentuk dan ukuran huruf Hijaiyah.
perancangan aplikasi ini antara lain yaitu:
Dari
permasalahan
tersebut
1. Notebook dengan spesifikasi Intel
maka penulisan tugas akhir ini akan
Processor
Core2Duo,
mencoba metode lain yang bisa lebih
2048MB, HDD 320GB
RAM
2. OS Windows 8 Professional
2. Perancangan Sistem
3. Program
2.1 Preprocessing
Aplikasi
Matlab
R2011b (7.13.0.564)
Pada tahap preprocessing gambar
C. Langkah Penelitian
inputan tersebut akan di ubah menjadi
1. Analisis Kebutuhan
sebuah matrik biner yang selanjutnya
Sistem pengenalan huruf tulisan
dilakukan proses berikut (J. Gilewski,
tangan ini akan menerima input berupa
1997) :
file
akan
1) Filtering, merupakan proses untuk
dilakukan lakukan tiga tahapan, yaitu
menghilangkan noise yang ada pada
preprocessing, fuzzy feature extraction,
file
dan neural network backpropagation.
mengubah file menjadi matrik biner.
gambar
yang
kemudian
input,
Secara garis besar alur penelitian dapat
digambarkan
dalam
dilanjutkan
1 0 0 0 1
flowchart
berikut :
0 1 0 1 0
proses
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1
Gambar 2. Matrik biner
Mulai
2) Thinning,
merupakan
proses
Pengumpulan Data
penghilangan pixel terluar dengan cara tidak
iterative deletion hingga menghasilkan
Pengecekan data, lengkap ?
sebuah pixel tulang (skeleton).
ya Perancangan dan pembuatan program
Pengujian program, berhasil ?
tidak Perbaikan program
ya
Pembuatan laporan
Gambar 3. Proses Thinning Selesai
Gambar 1. Flowchart penelitian
3) Searching vertices, proses menemukan titik-titik ujung serta titik percabangan.
start point, penelusuran dilakukan hingga menemukan kondisi berhenti dimana saat penelusuran
menemukan
percabangan
koordinat
(intersection
points).
Gambar 4. Searching vertices Simpan ke dalam sebuah matrix segment 2.2 Fuzzy Feature Extraction end (MSE). Proses selanjutanya ialah fuzzy Lakukan
penelusuran
dari
titik
feature extraction, yang akan melakukan percabangan dan kondisi berhenti pada proses pencarian segmen terhadap pola saat
menemukan
titik
percabangan
huruf, mengklasifikasikan segmen, serta ataupun titik ujung. Simpan ke matrix membentuk
sebuah
matrik
yang segment intersect (MSI)
mencerminkan pola-pola dari setiap huruf yang akan dikenali dan selanjutnya akan digunakan sebagai inputan bagi tahap neural network backpropagation. LINE
RIGHT
LEFT
LOOP
Gambar 6. Contoh MSE dan MSI
HORIZONTAL
Step2 VERTICAL
Menentukan
apakah
segmen
dengan
memenuhi
RIGHT SLOPE
merupakan
loop
LEFT SLOPE
kondisi Gambar 5. Tipe segmen Langkah untuk proses fuzzy feature extraction : Step1 Lakukan penelusuran dimulai dari tiap-tiap titik ujung yang akan menjadi
d<=(k+d)*α/360,
dimana
d
merupakan jarak antar start point dan end point, k merupakan jumlah state yang ada pada segmen tersebut, dan α merupakan batas sudut toleransi kategori loop.
α
d
Gambar 7. Klasifikasi segmen loop Gambar 9. Rata – rata deviasi
Step3 Berdasarkan koordinat start point dan end point, maka kita dapat mencari dan menentukan persamaan garis linier yang merupakan base line ( y mx c ) dari segmen tersebut untuk menentukan nilai
Setelah mendapatkan nilai D maka kita harus menghitung curve threshold (β), yakni nilai batas minimal Deviasi dimana segmen tersebut dapat dikatakan sebagai sebuah kurva.
gradient (m), dan dari gradient tersebut kita dapat melakukan klasifikasi pertama untuk menentukan jenis segmen F H
R
V
L
H
R
V
L
H
Gambar 10. Curve threshold Step5 Langkah berikut dilakukan setelah
0
45
90
135
180
225
270
315
360
θ
Gambar 7. Fungsi klasifikasi segmen
segmen terklasifikasi sebagai kurva, yaitu
Step4
untuk mengetahui tipe kurva dari segmen kurva
tersebut. Langkah ini dilakukan dengan
maka perlu dihitung rata-rata Deviasi
cara mencari letak dan titik perpotongan
antara koordinat – koordinat segmen
kurva terhadap left line atau right line
terhadap base line.
berdasarkan dari base line dari segmen
Untuk
proses
klasifikasi
tersebut.
segmen tersebut kedalam sebuah matrik Value (matrik yang memiliki dimensi 20 x 8, jumlah baris menunjukkan jumlah Gambar 11. Menghitung titik perpotongan
segmen maksimum yang dimiliki oleh
Pada langkah ini akan lakukan
menunjukkan panjang digit dari nilai bit).
konversi dari tipe segmen hasil klasifikasi
Untuk mengetahui keterhubungan
segmen mulai dari langkah 1 hingga 5
antar segmen maka perlu kita definisikan
menjadi nilai bit yang memiliki panjang 8
menjadi sebuah matrik interrelationship
digit untuk setiap segmen dimana 5 digit
(matrik berdimensi 20 x 20, yang
pertama merupakan klasifikasi jenis line
menunjukan ada maksimal 20 segmen
dan 3 digit terakhir merupakan klasifikasi
dalam tiap hurufnya).
Step6
sebuah
huruf,
dan
jumlah
kolom
jenis kurva
Gambar 12. Konversi bit Gambar 13. Jumlah segmen huruf sin
Step7 Ulangi langkah 1 hingga 6 pada semua segmen dari huruf yang akan dikenali. Simpan semua nilai konversi bit
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Gambar 14. Matrik interrelationship Setelah interrelationship
didapatkan dan
matrik
matrik
2.3 JST Backpropagation
Value,
Pada fase ini akan dibangun sebuah
selnjutnya kedua matrik tersebut diubah
jaringan syaraf tiruan (neural network)
menjadi matrik yang hanya memiliki
backpropagation yang memiliki 560 node
dimensi 1 x 160 (berasal dari matrik
input dan 28 node output. Pelatihan
Value) dan 1 x 400 (berasal dari matrik
menggunakan 420 pola dimana setiap
interrelationship). Setelah itu gabungan
huruf
kedua matrik tersebut akan menjadi
menghasilkan 28 output sesuai jumlah
sebuah matrik baru (matrik JSTinput)
huruf Hijaiyah yang akan dikenali.
yang nantinya akan menjadi input untuk proses neural network backpropagation (matrik dengan dimensi 1 x 560).
memiliki
15
pola
dan
akan
Output Hasil 1 2 3 4 5 Alif Alif Alif Alif Alif Alif 5 Ba Ba Nun Ba Ba Ba 4 Ta Nun Ba Nun Tsa Ba 0 Tsa Nun Tsa Ba Tsa Ba 2 Jim Jim Jim Jim Kho Kho 3 Kha Kha Kha Kha Kha Kha 5 Kho Kho Kho Kho Kho Ghoin 4 Dal Lam Dal Zay Ro Ro 1 Dzal Lam Ro Lam Dzal Dzal 2 Ro Lam Lam Ro Zay Ro 2 Zay Zay Lam Lam Zay Lam 2 Sin Sin Sin Sin Sin Shot 4 Syin Syin Syin Syin Syin Syin 5 Shot Shot Shot Shot Shot Shot 5 Dhot Dhot Dhot Dhot Dhot Dhot 5 Tho' Tho' Tho' Tho' Tho' Tho' 5 Dho' Dho' Dho' Dho' Dho' Dho' 5 Ain Ain Ain Ain Ain Ain 5 Ghoin Ghoin Ghoin Ghoin Tho' Ghoin 4 Fa Fa Fa Fa Fa Ha 4 Qaf Qaf Qaf Qaf Qaf Qaf 5 Kaf Kaf Kaf Dzal Kaf Lam 3 Lam Lam Lam Lam Tho' Lam 4 Mim Mim Mim Mim Ha Mim 4 Nun Nun Ba Ba Ba Nun 2 Ha Ha Ha Ha Syin Ha 4 Wawu Mim Zay Wawu Mim Mim 1 Ya Lam Ba Ba Ba Ba 2 Rata - rata Pengenalan Huruf Input
x1
1
x2
2
x3
3
x560
28
Input layer
Output layer Hidden layers
Gambar 15. Backpropagation 3. Pengujian Sistem Pengujian terhadap sistem dengan cara
menguji
apakah
sistem
dapat
mengenali huruf yang terdapat pada image input-an. Pengujian dilakukan terhadap 28 huruf Hijaiyah dengan masing – masing huruf berjumlah 5 buah citra uji dan dengan 420 citra yang sudah dilatih (15 citra dari masing – masing huruf). Image input berformat *.png dengan dimensi 100 x 100.
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
100% 80% 0% 40% 60% 100% 80% 20% 40% 40% 40% 80% 100% 100% 100% 100% 100% 100% 80% 80% 100% 60% 80% 80% 40% 80% 20% 40% 69%
Gambar 16. Recognition Rate Kesimpulan dan Saran
yang
1. Pengenalan
huruf
dilakukan
dengan
didapat dari rata – rata presentase
Logika
Fuzzy
pengenalan dari masing - masing huruf.
dengan
Jaringan
Recognition rate dari pengenalan huruf
Backpropagation.
dapat dilihat dari tabel berikut :
Rate
Kesimpulan
Dari hasil penelitian didapatkan recognition rate sebesar 69%
Total
Hijaiyah
dapat
menggunakan
yang
digabungkan
Syaraf
Tiruan
2. Sistem pengenalan yang dibangun dengan menggunakan metode logika fuzzy
dan
jaringan
syaraf
tiruan
backpropagation memiliki recognition
jumlah titik dan letak titik antar huruf
rate sebesar 69%.
agar
3. Besarnya
recognition
rate
akan
pola
yang
dihasilkan
lebih
identik.
dipengaruhi oleh beberapa hal antara
2. Sistem akan lebih bermanfaat jika bisa
lain tingkat identik pola yang dimiliki
mengenali huruf hijaiyah sambung,
oleh tiap huruf yang didapatkan dari
bukan hanya hijaiyah pisah.
ekstraksi ciri tiap huruf. Saran 1. Pada tahap features extraction akan lebih baik bila ditambahkan beberapa parameter lain (selain value setiap
3. Pengembangan
sistem
untuk
pengenalan huruf secara real time dengan mengenali huruf yang ditulis manual di layar komputer. 4. Pengembangan
sistem
untuk
huruf dan matrik interrelationship)
pengenalan huruf Hijaiyah sambung
agar menghasilkan pola yang lebih
dan
identik untuk setiap huruf, terutama
dirasakan manfaatnya.
parameter tambahan untuk pengenalan
berharakat
agar
lebih
dapat
DAFTAR PUSTAKA Demuth, Howard and Beale, Mark. 1994. “Neural Network Toolbox For Use with Matlab.” The Math Work Gilewski, J., Phil Philips, S. Yanushkevich, D. Popel. 1997. “Education Aspects: Handwriting Recognition - Neural Networks - Fuzzy Logic”. Proceedings of the IAPR International Conference on Pattern Recognition and Information Processing – PRIP’97, vol. 1, 1997, pp.39-47 Kusumadewi, S, dan Purnomo. 2004. “Aplikasi Logika Fuzzy untuk Pendukung Keputusan”. Yogyakarta : Graha Lam, Louisa., Seong-Whan Lee. “Thinning Metodologies – A Comprehensive Survey”. IEEE Transactions on Pattern Analysis and Machine Intelegence, Vol. 14, No. 9, September 1992, page 879 Marvin & agus Prijono.Juli 2007.Pengolahan Citra Digital Menggunakan Matlab. Bandung : Informatika Nugraha, A.P. 2002. “Metode ekstraksi data untuk pengenalan huruf dan angka tulisan tangan dengan metode jaringan syaraf buatan propagasi balik”. Skripsi. Depok Prakoso, Teguh. “Pengenalan Pola Huruf Arab Tulis Tangan Menggunakan Jaringan Saraf Tiruan dengan Metode Perambatan Balik”. Skripsi. Semarang S. Theodoridis, K. Koutroumbas. 2003. “Pattern Recognition : Second Edition”. USA : Elsevier Santoso, Setiawan. 2010. “Perancangan Dan Pembuatan Perangkat Lunak Pengenalan Huruf Tulisan Tangan Dengan Metode Backpropagation”. Skripsi. Surabaya Saputro, Nico. 2003. “Pengenalan Huruf Dengan Memakai Algoritma Genetika”. Skripsi. Bandung Schalkoff J, Robert. 1992. “Pattern Recognition: Statistical, Structural , and Neural Approaches”. Jhon Wiley & Sons Inc., USA Siang, J.J. 2005. “Jaringan Syaraf Tiruan dan Pemrogramannya menggunakan Matlab”. Yogyakarta : Penerbit Andi Stewart, Robert R. “Median Filtering : Review and A New F/K Analogue Design”. Journal of the Canadian Society of Exploration Geophysicists. 1985 Sugiharto, A. 2005. “Pemograman GUI dengan MATLAB”. Yogyakarta : Penerbit Andi T Sutojo. 2009. ”Aljabar Linier & Matriks”. Yogyakarta : Andi .
ABSTRACT Various studies on the recognition / identification of handwritten letters continue to be developed. Some methods are quite popular is the statistical approach (image matching), genetic algorithms, and syntactic approach. The use of these methods will work well if used to recognize handwritten letters a low level of complexity, in other words, the method will be less effective if it recognizes handwritten letters who possess the type and size may vary. Due to the complexity of handwritten letters will be increased by variation of writing and authorship mood. Of the problems above, this thesis will try other techniques that are expected to be more effective in order to recognize handwritten letters. Recognition method raised in this thesis is to use fuzzy logic which considers handwritten letters as a directed graph, whose vertices consist of its end points and branch points. While its segments are straight lines, curves, and loops. As for the classification process using backpropagation neural network Artificial neural network is a computational method that should work like the human brain neurons. Advantage of this method is the ability to learn and solve complex relationship, which is difficult to describe the input data and output data, it is possible because the neural network is able to be trained on information it receives. Key Words : Fuzzy Logic, Backpropagation, Pattern Recognition