A15
Seminar Nasional Teknologi Informasi 2010
PENGENALAN TANDA TANGAN DENGAN MENGGUNAKAN NEURAL NETWORK DAN PEMROSESAN AWAL THINNING ZHANG SUEN Chairisni Lubis1) Yuliana Soegianto2) 1)
Fakultas Teknologi Informasi Universitas Tarumanagara Jl. S.Parman No.1 Jakarta 11440 Indonesia email :
[email protected]
2)
Fakultas Teknologi Informasi Universitas Tarumanagara Jl. S.Parman No.1 Jakarta 11440 Indonesia email :
[email protected]
ABSTRAK Pada sistem pengenalan tandatangan ini digunakan Backpropagation Neural Network. Pemrosesan awal yang dilakukan untuk mendapatkan ciri penting sebelum diproses dalam Neural Network adalah proses thinning Zhang Suen, sedangkan ekstraksi cirinya menggunakan proyeksi histogram. Pada sistem pengenalan tandatangan ini, citra tandatangan diperoleh dengan cara menscan tanda tangan yang akan diproses dan disimpam dalam format JPG dan BMP. Program aplikasinya dibuat dengan menggunakan Visual basic.Net dan untuk menyimpan tandatangan yang akan dipakai dalam proses pembelajran digunakan Microsoft Access. Pada proses pengujian digunakan 10 pola tanda tangan, dengan demikian jumlah neuron output pada arsitektur Backpropagation Neural Network yang digunakan sebanyak 10 buah. Jumlah neuron inputnya sebanyak 16 buah yang berasal dari hasil ekstraksi ciri dengan menggunakan proyeksi histogram. Dari hasil pengujian didapat tingkat pengenalan tanda tangan yang diperoleh dengan menggunakan Backpropagation Neural Network dan pemrosesan awal menggunakan thinning Zhang Suen sebesar 94%
1. Pendahuluan Sistem pemeriksaan tanda tangan secara manual memiliki kelemahan dimana pemeriksa kurang teliti dalam membandingkan tanda tangan. Salah satu solusi untuk mengatasi kelemahan sistem manual ini adalah dengan menggunakan Neural Network untuk proses pengenalannya. Neural Network merupakan suatu prosesor yang dapat melakukan pendistribusian secara besar-besaran, yang memiliki kecenderungan alami untuk menyimpan suatu pengenalan yang pernah dialaminya, dengan kata lain Neural Network ini memiliki kemampuan untuk dapat melakukan pembelajaran dan pengenalan terhadap suatu pola. Pada sistem pengenalan tandatangan ini digunakan Backpropagation Neural Network. Sebelum diproses dalam Neural Network, tanda tangan harus diproses awal dahulu (preprosesing). Tujuan pemrosesan awal ini adalah untuk mendapatkan ciri penting dari suatu pola tandatangan melalui proses yang dinamakan ekstraksi ciri. Metoda ekstraksi ciri yang digunakan adalah proyeksi histogram. Tanda tangan yang akan diperiksa kadang-kadang mengalami penebalan (salah satu penyebabnya adalah berasal dari tinta yang digunakan), karena itu pada sistem pengenalan tanda tangan ini digunakan proses thinning Zhang Suen untuk mengambil garis yang lebih tipis dari sebuah tanda tangan Thinning atau penipisan adalah suatu proses pengurangan objek dalam citra digital hingga ukuran minimal yang diperlukan untuk pengenalan objek, hasilnya dikenal dengan skeleton (kerangka) dan proses thinning kadang-kadang dikenal juga sebagai skeletonisasi. Algoritma Thinning Zhang Suen
Key words Backpropagation Neural Network, Proyeksi Histogram, Thinning Zhang Suen.
80
Seminar Nasional Teknologi Informasi 2010
A15
didasarkan pada evaluasi nilai piksel dan 8 piksel tetangga atau dikenal dengan the 8-neighborhood pixel, dengan piksel acuan Selain itu, pada sistem ini digunakan juga Edge detection Sobel untuk mencari garis tepi tanda tangan sebelum diproses sehingga data yang digunakan merupakan data yang tidak terlalu besar.
2. Pengenalan tanda tangan dengan menggunakan Backpropagation Neural Network
p9
p2
p3
p8
p1
p4
p7
p6
p5
Gambar 1 Piksel P1 dengan 8 tetangga
Pada langkah kedua, kondisi 1 dan 2 sama dengan langkah pertama, sedangkan kondisi 3 dan 4 diubah menjadi: 1. p2 . p4 . p8 = 0; 2. p2 . p6 . p8 = 0;
Dalam perancangan program pengenalan tanda tangan ini, terdapat beberapa metode yang akan digunakan, yaitu : 1. Thresholding : Digunakan untuk mengatur jumlah derajat keabuan yang ada pada citra. 2. Edge Detection Sobel Digunakan untuk memperjelas garis-garis batas yang terdapat pada citra. 3. Thinning Zhang Suen Digunakan untuk skeletonizing 4. Proyeksi Histogram Digunakan untuk proses ekstraksi ciri 5. Backpropagation Neural Network (BPNN) Digunakan untuk proses pengenalan tanda tangan.
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 points selesai diproses. Setelah langkah 1 selesai dilakukan untuk semua border points maka dilakukan penghapusan untuk titik yang telah ditandai (diubah menjadi 0). Setelah itu dilakukan langkah 2 pada data hasil dari langkah 1 dengan cara yang sama dengan langkah 1 sehingga, dalam satu kali iterasi urutan algoritmanya terdiri dari:[1] 1. Menjalankan langkah 1 untuk menandai border points yang akan dihapus, 2. Menghapus titik-titik yang ditandai dengan menggantinya menjadi angka 0, 3. Menjalankan langkah 2 pada sisa border points yang ada langkah 1 belum dihapus lalu yang sesuai dengan semua kondisi yang seharusnya dipenuhi pada langkah 2 kemudian ditandai untuk dihapus, 4. Menghapus titik-titik yang ditandai dengan menggantinya menjadi angka 0.
Pada makalah ini hanya dibahas 3 buah metoda yang dianggap paling dominan dalam perancangan program tanda tangan ini, yaitu :
2.1 Thinning Zhang Suen Thinning Zhang Suen adalah salah satu algoritma thinning yang cukup populer dan telah digunakan sebagai suatu basis untuk perbandingan untuk thinning. Setiap iterasi dari metode ini terdiri dari dua sub-iterasi yang berurutan yang dilakukan terhadap contour points dari wilayah citra. Contour point adalah setiap pixel dengan nilai 1 dan memiliki setidaknya satu 8-neighbor dengan nilai 0. Langkah pertama adalah menandai contour point p untuk dihapus jika semua kondisi ini dipenuhi:[1] 2 ≤ N(p1) ≤ 6; S(p1) = 1; p2 . p4 . p6 = 0; (1) p4 . p6 . p8 = 0;
Prosedur ini dilakukan secara iteratif sampai tidak ada lagi titik yang dapat dihapus. Pada saat algoritma ini selesai maka dihasilkan skeleton dari citra awal.[1]
2.2 Proyeksi Histogram Ekstraksi ciri dapat mempersingkat waktu pemprosesan dalam pembelajaran, karena semakin banyak input yang masuk dalam pembelajaran Backpropagation maka akan semakin banyak pula persamaan yang akan diproses hal ini dapat menyebabkan proses yang terlalu lama. Salah satu metode yang dapat
Keterangan : N(p1) = jumlah tetangga dari p1 yang tidak 0 S(p1) = jumlah dari transisi 0-1 pada urutan p2, p3, ..., p8, p9.
81
A15
Seminar Nasional Teknologi Informasi 2010
Citra yang dimasukkan dalam program aplikasi ini adalah citra grayscale dan diproses thresholding. Setelah menentukan format input yang akan digunakan dalam proses pengenalan tanda tangan maka langkah selanjutnya adalah menentukan perangkat lunak dan perangkat keras yang akan digunakan, yang dapat mendukung dalam pembuatan program aplikasi ini. Program aplikasi pengenalan tanda tangan ini menggunakan spesifikasi perangkat lunak yaitu: 1. Microsoft Visual Basic.Net 2005 2. Microsoft Windows XP Profesional Service Pack 3 3. Microsoft Access 2007
digunakan untuk ekstraksi ciri adalah metode proyeksi histogram. Nilai-nilai dari histogram adalah jumlah dari piksel hitam sepanjang arah tertentu. Empat jenis histogram yang ada adalah, di 0 derajat (proyeksi histogram horizontal), di 90 derajat (proyeksi histogram vertikal) dengan melihat pada sumbu horizontal y, positif dan negatif diagonal. Suatu proyeksi histogram horizontal h(x) dari gambar biner f(x,y) adalah jumlah piksel hitam diproyeksikan ke sumbu vertikal x. Sumbu proyeksi histogram vertikal v(y) dari gambar biner f(x,y) adalah jumlah piksel hitam diproyeksikan ke horizontal sumbu y [1] Dari hasil feature vektor akan melakukan pendekatan statistika, yaitu dengan mencari nilai standar deviasi, range, maksimum – median, dan mean dari setiap proyeksi. Rumus statistik yang digunakan adalah:[2] 1. Menghitung standar deviasi: S = n∑x2-∑x2n (n-1) (5) 2. Menghitung Range: Range = Maksimum – Minimum (6) 3. Mengitung Maksimum – Median (7) 4. Menghitung Mean: Mean = ∑xn (8)
Dan spesifikasi perangkat keras yang akan digunakan adalah: 1. 2. 3. 4. 5. 6. 7.
Processor Intel Pentium 4 CPU 2,4 GHz. Harddisk dengan kapasitas 70GB. RAM 512 Mb. Monitor 14”. VGA Card 128 Mb. Mouse. Keyboard.
2.3 Backpropagation Neural Network 1
Dari hasil ekstraksi cirri dengan menggunakan proyeksi histogram terdapat empat nilai yang dihitung dari citra secara vertikal, empat nilai yang dihitung dari citra secara horizontal, empat nilai yang dihitung dari citra secara diagonal positif, dan empat nilai yang dihitung dari citra secara diagonal negative. Empat nilai dari masing-masing arah terdiri dari jumlah nilai tengah piksel, nilai mean, nilai maksimum dikurangi dengan nilai median, dan nilai range. Sehingga menghasilkan input enam belas nilai yang akan menjadi enam belas neuron input yang kemudian diproses dalam backpropagation Neural Network Jumlah hidden layer akan dilakukan beberapa percobaan, dengan beberapa percobaan maka akan didapat hasil jumlah hidden layer yang paling baik untuk dipergunakan dalam proses pengenalan. Output berjumlah sepuluh tanda tangan dari sepuluh orang yang berbeda sehingga neuron output berjumlah sepuluh. Epoch dilakukan sebanyak 10000 kali, akan disesuaikan apabila waktu yang diperlukan untuk proses tersebut terlalu lama maka jumlah maksimum epoch akan dikurangi. Alpha (α) yang dipergunakan antara 0,1 sampai dengan 0,9 dipilih yang menghasilkan nilai output yang terbaik. Dan bobot awal untuk perhitungan awal akan menggunakan bobot acak antara -0.5 sampai dengan 0.5. Arsitektur backpropagation terdapat pada gambar 2 di bawah ini.
1
V01
X1
W01
Z1
V11 V02
V21
Y1
W11 W02 W21
V12 W12
X2
V22
Z2 V141
W22
Y2
Wp1
V142
Wp2
W110 W010
V0p
W210
V2p V1p
X16
V14p
Zp
Wp10
Y10
Gambar 2 Arsitektur Backpropagation untuk pengenalan tanda tangan
3. Hasil Percobaan Pengujian pertama dilakukan dengan tujuan untuk menguji nilai alpha dan jumlah hidden layer yang terbaik yang akan digunakan dalam proses Backpropagation Neural Network, sehingga dalam proses selanjutnya akan menggunakan nilai-nilai ini. Berikut
82
Seminar Nasional Teknologi Informasi 2010
A15
Tabel 3 Perbandingan hasil pengenalan dengan thinning dan tanpa thinning
adalah tabel 3 pengujian untuk menemukan jumlah hidden layer dengan alpha 0.9.
Objek
Dengan thinning
Tanpa thinning
Pena
92%
94%
Boxy
92%
94%
Stabillo
88%
90%
Spidol
94%
94%
Tabel 1 Jumlah Hidden Layer untuk Pembelajaran
Jumlah Hidden Layer 5 15 20 30
Berhenti pada Epoch 8 5 30 50
Nilai Error 0.00078 0.000689 0.000916 0.000818
Dilihat dari hasil yang didapat, maka dapat diperoleh nilai error yang terkecil, yaitu pada hidden layer yang berjumlah lima belas sehingga akan dipergunakan jumlah hidden layer lima belas untuk proses pembelajaran Backpropagation Neural Network. Pengujian berikutnya adalah penentuan nilai alpha terbaik dari jumlah hidden layer lima belas yang akan digunakan pada proses pembelajaran Backpropagation Neural Network.
Dari tabel 3 di atas terlihat bahwa penggunaan thinning dalam proses pengenalan tanda tangan tidak memberikan dampak yang besar pada proses pengenalan, karena gambar tanda tangan yang sudah tipis apabila dimasukkan dalam proses thinning maka citra akan terbuang sehingga tidak ikut dalam proses backpropagation. Seperti contoh gambar 3 hasil thinning di bawah ini.
Tabel 2 Nilai Alpha untuk Pembelajaran
Nilai Alpha 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Berhenti pada Epoch 23 18 17 25 27 18 18 14 17
Nilai Error 0.000692 0.000665 0.000987 0.000794 0.000971 0.000665 0.00089 0.000644 0.000902
Gambar 3 Hasil Thinning
Hasil pengenalan degan menggunakan thinning Zhang Suen sebesar 94 % didapat pada saat menggunakan tingkat ketebalan alat tulis yang lebih besar (spidol), tetapi hasilnya belum lebih baik dengan tanpa menggunakan thinning
Dilihat dari hasil yang didapat, maka dapat diperoleh nilai alpha yang memiliki nilai error terkecil dari pembelajaran dengan thinning yaitu pada alpha ke 0.8. Sehingga untuk proses pembelajaran Backpropagation akan menggunakan alpha 0.8 dan hidden layer lima belas. Pengujian kedua dilakukan dengan tujuan untuk menguji apakah output yang dihasilkan oleh program sesuai dengan konsep yang digunakan. Sampel yang digunakan untuk pengujian tanda tangan ini beasal dari 10 orang . Masing-masing orang memasukkan 5 buah tanda tangan, sehingga jumlah tanda tangan seluruhnya ada 50 tandatangan. Untuk mengetahui pengaruh thinning Zhang Suen pada pengenalan tanda tangan ini, maka digunakan 4 buah alat tulis yang berbeda ketebalannya dan hasilnya dibandingkan dengan pengenalan tanda tangan tanpa menggunakan proses thinning. Hasil proses pengenalan tanda tangan dapat dilihat pada tabel 3.
4. Kesimpulan Pengenalan tanda tangan dengan menggunakan Backpropagation Neural Network dengan pemrosesan awal thinning Zhang Suen tidak memberikan dampak yang cukup baik, persentase yang diperoleh adalah 94% dan dibandingkan proses yang tanpa menggunakan thinning, persentase yang diperoleh juga 94%. Hal ini dikarenakan terdapat penghilangan data gambar tanda tangan setelah proses thinning sehingga hal ini dapat mempengaruhi dalam pengenalannya.
83
A15
Seminar Nasional Teknologi Informasi 2010
REFERENSI [1] Andreas Nataniel, dkk., Algoritma Thinning, http://www.google.co.id/#hl=id&q=1.%09S keleton+dari+citra+kirakira+berada+di+bagian+tengah+dari+citra+awal+sebe lum+dilakukan+thinning&meta=cr%3DcountryID&aq =&oq=1.%09Skeleton+dari+citra+kirakira+berada+di+bagian+tengah+dari+citra+awal+sebe lum+dilakukan+thinning&fp=3c535af0b522fb05, 10 Desember 2009. [2] Histogram Proyeksi, http://4.bp.blogspot.com/_D5l6uqAnYKs/Si 20MQRnZdI/AAAAAAAAAJQ/VHXMyE3Dc0/s1600-h/histproyeksi.jpg, 28 Maret 2010.
Chairisni Lubis, memperoleh gelar Dra dari Jurusan Fisika, Universitas Indonesia dan M.Kom dari Program Pasca Sarjana Ilmu Komputer, Universitas Indonesia .
84