Seminar on Application and Research in Industrial Technology, SMART Yogyakarta, 22 Juli 2009
SEGMENTASI KARAKTER TULISAN TANGAN ONLINE MENGGUNAKAN FILTER IIR Suryarini Widodo, Sarifuddin Madenda , dan Prihandoko. Fakultas Teknologi Informasi Universitas Gunadarma Jl. Margonda Raya No. 100 Pondok Cina Depok 16424 Telp: 021 78881144, Fax : 021 7872829 E-mail:
[email protected],
[email protected],
[email protected]
Abstrak Segmentasi karakter merupakan proses yang sangat penting dalam analisa dan pengenalan karakter tulisan tangan. Paper ini adalah mengembangkan suatu metode segmentasi yang dapat menghasilkan segmen karakter tulisan tangan online sesuai dengan segmentasi acuan. Beberapa algoritma segmentasi telah dikembangkan. Sebagian menggunakan pendekatan wavelet dan sebagian lagi menggunakan pendekatan filter. Karakteristik data yang digunakan pada kedua pendekatan tersebut adalah kecepatan linear. Penggunaan karakteristik ini masih menghasilkan derau yang tinggi, sehingga mempersulit proses segmentasi. Hal ini disebabkan karena adanya perbedaan kecepatan menulis dan kecepatan sampling. Sulitnya proses segmentasi terjadi karena adanya lokal maksimum dan minimum yang bukan sebenarnya. Akibatnya, titik potong segmentasi menjadi tidak tepat. Secara keseluruhan proses segmentasi menjadi tidak akurat dan tidak sesuai dengan segmen acuan. Untuk menghilangkan atau memfilter derau tersebut digunakan filter smoothing IIR (infinite impulse response filters). Filter ini memiliki kemampuan yang baik dalam menghilangkan atau memfilter derau. Penghilangan derau pada data karakter tulisan tangan online ini untuk mempermudah proses segmentasi. Selain itu, penggunaan filter IIR ini dapat meningkatkan akurasi posisi pemotongan segmen. Paper ini menggunakan 52 data karakter tulisan tangan online yang terdiri dari dua set data karakter a-z. Hasil eksperimen yang diperoleh menunjukan bahwa filter IIR menghasilkan proses smoothing yang baik. Hal ini dibuktikan dengan sedikitnya lokal maksimum dan minimum yang dihasilkan sehingga memudahkan melakukan pemotongan pada titik segmen dan diperoleh ketepatan jumlah segmen dan posisi pemotongan segmen. Kata Kunci : Segmentasi, Online, Kecepatan, Filter IIR, Derau
1. Latar Belakang Stroke tulisan tangan merupakan gerakan tangan manusia dalam menulis mulai dari pena diletakkan sampai pena diangkat. Stroke tulisan tangan digunakan dan dipelajari pada berbagai bidang penelitian, dengan banyak tujuan. Sebagai contoh, pada pengenalan pola, banyak algoritma dirancang untuk mengenali tulisan tangan berdasar pada sifat dasar stroke yang digunakan untuk menghasilkan karakter. Di bidang pendidikan, banyak metoda pengajaran bersandar pada bagaimana stroke dihasilkan dan penggabungan stroke untuk menghasilkan sebuah karakter dan kata [Simner in Djioua, 2006]. Segmentasi adalah proses membagi keseluruhan tulisan tangan menjadi potongan yang lebih kecil (yaitu segmen atau stroke). Segmentasi dapat dilakukan dari suatu masukan berupa bentuk teks, kata, karakter. Segmentasi tulisan merupakan permasalahan yang sangat sulit dilakukan khususnya untuk sejumlah aplikasi khususnya pengenalan tulisan tangan sambung karena masing-masing karakter menyambung menjadi satu dan banyaknya variasi tulisan tangan yang ditulis oleh orang yang berbeda. Hampir semua pendekatan segmentasi didasarkan pada mensegmen suatu kata atau karakter (huruf) menjadi sub unit yang lebih kecil. Segmentasi ini Jurusan Teknik Mesin dan Industri FT UGM ISBN 978-979-18528-1-4
A-119
Seminar on Application and Research in Industrial Technology, SMART Suryarini Widodo, Sarifuddin Madenda , dan Prihandoko
bertujuan membagi karakter tulisan tangan dalam beberapa bagian untuk mendapatkan ciri dari karakter tersebut. Ciri ini selanjutnya akan digunakan untuk proses pengenalan karakter tulisan tangan. Jika proses segmentasi tidak dapat menentukan secara tepat posisi-posisi pemotongan segmen, maka sistem aplikasi akan gagal atau kurang tepat mengenali tulisan tangan. Tulisan tangan ini seperti terlihat pada gambar 1, secara visual (kasat mata) para peneliti dibidang tulisan tangan [Vinter, Annie., 2005 dan Plamondon, Rejean., 1998] mencoba untuk memahami karakteristik tulisan tangan serta mecari kemungkinan pemecahan setiap karakter menjadi bagian-bagian kecil (segmen). Hal ini dimaksudkan untuk lebih mempermudah dalam melakukan proses pengenalan tulisan tangan. Gambar 1 merepresentasikan segmen-segmen setiap karakter yang dilakukan berdasarkan pendapat sejumlah peneliti [Vinter, 2005 dan Plamondon, 1998]. Dari 26 karakter tulisan tangan huruf latin terdapat total 25 jenis segmen.
Gambar 1 Contoh segmentasi pada karakter a, c, e, f, i, o dan u [Vinter, 2005][Paindavoine, 2005] Secara umum kendala yang dihadapi pada segmentasi karakter tulisan tangan adalah tingginya kandungan derau di dalamnya. Derau ini diakibatkan oleh getaran tangan saat seseorang menulis. Getaran tangan ini dapat mengakibatkan pergeseran acak posisi koordinat dan perubahan acak pada tekanan pensil (pen) pada tablet sensor tulisan tangan. Derau-derau ini sering mengakibat terbentuknya lokal minimum dan maksimum pada sinyal tulisan tangan dan sangat mempengaruhi keakuratan hasil segmentasi karakter. Berdasarkan kenyataan tersebut, para peneliti telah mengembangkan sejumlah teknik segmentasi tulisan tangan diantaranya adalah smoothing dengan metode wavelet yang berdasar pada saliency map [De Stefano, Claudio, Ciro D’elia, Marco Garruto, Angelo Marcelli and Alessandra Scotto Di Freca, 2005] dan smoothing dengan filter menggunakan karakteristik kecepatan linear yang berdasarkan pada kecepatan dalam menulis tangan [Sanchez, E. Gómez., Y.A. Dimitriadis., M. Sánchez-Reyes Más., P. Sánchez García., J.M. Cano Izquierdo., and J. López Coronado., 1998]. Saliency map adalah peta yang menampilkan grafik nilai maksimum yang merupakan representasi multi skala hasil smoothing dengan wavelet. Untuk mensegmentasi kata, De Stefano mengusulkan suatu metode dekomposisi kurva saliency map untuk mensegmen tulisan tangan sambung dalam stroke dasar. De Stefano berasumsi bahwa titik-titik segmentasi ada pada lengkungan maksimum kurva saliency map tersebut karena lengkungan maksimum mengindikasikan bahwa daerah tersebut berhubungan dengan bagian pada tinta di mana dua stroke bergabung. Karena itu De Stefano mengusulkan suatu pendekatan berdasarkan saliency yang secara perceptual mencirikan lengkungan maksimum yang dihasilkan oleh sumber derau yang mempengaruhi proses generasi tulisan tangan. Saliency map dicapai dengan mengkombinasikan semua nilai ke semua skala yang mungkin. Saliency map memperlihatkan nilai lengkungan maksimum yang lebih tinggi pada beberapa scale yang berbeda, hal ini menunjukkan bahwa daerah tersebut adalah daerah di mana dua stroke di gabungkan. Sedangkan Sanchez mencoba melakukan penelitian yang mencoba mengenali tulisan tangan dengan cara mendekomposisi sebuah karakter menjadi beberapa segmen. Sánchez [1998] melakukan segmentasi dengan melalui beberapa tahap. Model segmentasi Sanchez disebut degan model biologi. Tahapan metoda segmentasi berdasarkan pada model biologi Sanchez adalah pertama melakukan penghalusan (smoothing) input data berupa karakter dengan menggunakan FIR low-pass filter. Kemudian melakukan penghitungan kecepatan (velocity). Dari velocity yang didapat kemudian dapat diketahui angular signal untuk menentukan titik-titik Jurusan Teknik Mesin dan Industri FT UGM ISBN 978-979-18528-1-4
A-120
Seminar on Application and Research in Industrial Technology, SMART Suryarini Widodo, Sarifuddin Madenda , dan Prihandoko
sebagai kandidat pemotongan. Kemudian dilakukan penghitungan angular velocity untuk menentukan titik ekstremanya yang letaknya berdekatan dengan titik-titik kandidat segmentasi pada tahap sebelumnya. Dan terakhir didapatkan titik segmentasi yang dipilih dari nilai minimum pada linear velocity. Dari hasil percobaan dengan data UNIPEN dapat disimpulkan bahwa metode Sánchez mempunyai kelebihan cocok untuk pemrosesan real-time dan konsisten, untuk kombinasi beberapa bentuk curvature (lengkungan) khususnya pada segmentasi karakter huruf besar. Sedangkan keterbatasannya, metode ini dinilai lambat dan sangat bergantung pada bagaimana karakter dituliskan, karenanya mempunyai masalah pada tulisan tangan yang ditulis dengan sangat cepat. 2. Metodologi Metode segmentasi yang dikembangkan pada paper ini adalah melakukan segmentasi dengan menggunakan Filter IIR untuk proses penghalusannya dan karakteristik data kecepatan linear melalui lima tahap seperti terlihat pada Gambar 2 di bawah ini. Hitung kecepatan linear
Input data koordinat X, Y dan tekanan
Penentua n Segmen
Segmen
Eliminasi nilai Lokal Maksimum & Minimum
Proses Smoothing dengan Filter IIR Penentuan posisi Lokal Maksimum & Minimum
Gambar 2. Segmentasi dengan metode filter IIR menggunakan data kecepatan linear Algoritma ini di mulai dengan pembacaan data koordinat X dan Y serta tekanan dari karakter yang akan di segmen. Data tekanan digunakan hanya untuk memilah dan memvalidasi pada posisi koordinat mana tulisan itu dimulai dan pada koordinat mana berakhir. Pada tulisan tangan terdapat dua kandungan derau yaitu derau yang muncul di awal dan di akhir tulisan tangan serta derau yang diakibatkan oleh getaran tangan. Berdasarkan pada hasil analisis sejumlah data tulisan tangan untuk semua jenis karakter, umumnya derau yang ada di awal dan di akhir tulisan tangan, memiliki tekanan di bawah atau sama dengan 10 gram. Setelah itu dilakukan penghitungan kecepatan pena dalam menulis (kecepatan linear). Nilai kecepatan tergantung pada pergerakan perubahahan koordinat x dan y. Sinyal kecepatan mengandung derau yang relatif tinggi. Derau ini disebabkan oleh getaran tangan saat menulis dan kedua kecepatan tangan saat menulis sangat bervariasi sementara kecepatan sampling tetap. Hal ini mengakibarkan jarak antara dua titik yang berurutan bisa berbeda-beda secara acak. Secara matematis cara penghitungan kecepatan linear dapat diuraikan sebagai berikut. 2
2
x y v(i) t t
x(i 1) x(i)2 y(i 1) y(i)2 ;
t 1.
(1)
dimana i adalah sample ke i = 1, 2, . . ., N, dan N adalah jumlah total sample (titik) pada setiap karakter tulisan tangan. t adalah jarak waktu diantara dua titik sampling.
Gambar 3 (a) Tulisan tangan huruf ’a’ dan (b) Kurva atau sinyal kecepatan linear dari tulisan pada (a). (c) Sinyal kecepatan linear hasil filter IIR dengan nilai parameter α = 0,75 dan = 0.75
Jurusan Teknik Mesin dan Industri FT UGM ISBN 978-979-18528-1-4
A-121
Seminar on Application and Research in Industrial Technology, SMART Suryarini Widodo, Sarifuddin Madenda , dan Prihandoko
Grafik kecepatan linear yang didapat seperti ditunjukkan pada Gambar 3 (b) masih memperlihatkan derau, sehingga perlu dilakukan penghalusan lebih lanjut dengan filter IIR. Hasil smoothing dari filter ini diperlihatkan pada gambar 3 (c) menggunakan nilai parameter α = 0,75 serta nilai parameter = 0.75. Kelebihan lain dari penggunaan filter IIR adalah proses eliminasi derau tidak dilakukan secara berulang seperti pada proses transformasi wavelet. Sehingga waktu eksekusi algoritma menjadi lebih cepat. Dalam paper ini akan digunakan filter IIR yang dikembangkan oleh Madenda untuk proses eliminasi derau. Secara matematis filter ini dinyatakan dalam fungsi kontinu berikut : (2) 1 1
h( x ) K 2 e x ( 1 cos( x ) sin( x )) 2 2
Kemudian langkah selanjutnya adalah menentukan posisi lokal maksimum dan minimum. Bila setiap titik maksimum lokal dari kecepatan linear ini langsung digunakan sebagai batas segmentasi karakter tulisan ’a’ maka akan diperoleh hasil batas segmentasi yang tidak bersesuaian dengan hasil segmentasi menurut segmen acuan. Sedang bila setiap titik minimum lokal dari kecepatan linear ini langsung digunakan sebagai batas segmentasi karakter tulisan ’a’ maka akan diperoleh hasil batas segmentasi seperti yang ditunjukkan oleh Gambar 4 (c). Secara matematis xi, f(xi) adalah minimum lokal jika : f '(xi) < 0 untuk x < xi dan f '(xi) > 0 untuk x > xi (3)
Gambar 4. (a) Representasi titik-titik maksimum lokal tulisan tangan huruf ’a’. (b) Representasi setelah melalui proses eliminasi titik-titik minimum lokal yang tidak diinginkan (c). Representasi hasil segmentasi kecepatan minimum Karena itu perlu dilakukan eliminasi nilai lokal maksimum dan minimum untuk menghilangkan titik-titik minimum yang bukan titik minimum lokal yang sebenarnya. Pada Gambar 1 terlihat bahwa batas-batas segmen dalam setiap karakter terletak pada posisi dimana terjadinya perubahan arah (persimpangan) yang cukup signifikan pada tulisan tersebut. Hal ini dapat diartikan bahwa pada posisi ini terjadi perubahan kecepatan dengan kata lain kecepatan pena menjadi minimum. Kecepatan minimum inilah yang digunakan untuk menentukan batas titik potong setiap segmen dalam suatu karakter tulisan tangan. Berdasarkan pada titik-titik batas inilah kemudian dilakukan pemotongan karakter menjadi segmen-segmen. 3. Hasil dan Pembahasan Untuk penelitian ini, kami menggunakan 52 karakter tulisan tangan roman dari A sampai Z. Karakter-karakter tersebut didapatkan dari komputer tablet yang menangkap posisi masukan (koordinat xi dan yi) dari gerakan pena dan tekanan pada saat menulis. Kolom pertama pada Tabel 1 menunjukkan 26 karakter tulisan tangan roman dan kolom kedua menyajikan hasil segmentasi yang diperoleh dari algoritma segmentasi yang digunakan.
Jurusan Teknik Mesin dan Industri FT UGM ISBN 978-979-18528-1-4
A-122
Seminar on Application and Research in Industrial Technology, SMART Suryarini Widodo, Sarifuddin Madenda , dan Prihandoko
Tabel 1. Hasil pengujian lokasi titik potong segmentasi dengan metode filter IIR menggunakan karakteristik kecepatan linear Segmentasi Acuan
Hasil Segmentasi
Segmentasi Acuan
Hasil Segmentasi
Segmentasi Acuan
Hasil Segmentasi
Tabel 2 memperlihatkan hasil segmentasi dengan menggunakan data kecepatan linear terhadap 26 data uji karakter tulisan tangan. Dari hasil ini tampak terlihat bahwa hanya terdapat empat karakter yaitu ’c’, ’g’, ’s’ dan ’x’ yang tidak sesuai dengan segmentasi acuan. Sedang karakter-karakter lainnya telah sesuai dengan segmentasi acuan tanpa terjadi pergeseran posisi. Kesalahan yang terjadi diakibat oleh dua hal, yaitu pertama derau yang sangat tinggi pada setiap data karakter dan kedua adalah bentuk penulisan karakter yang tidak sesuai dengan tulisan tangan acuan.
Jurusan Teknik Mesin dan Industri FT UGM ISBN 978-979-18528-1-4
A-123
Seminar on Application and Research in Industrial Technology, SMART Suryarini Widodo, Sarifuddin Madenda , dan Prihandoko
Tabel 2. Hasil pengujian jumlah segmentasi karakter dengan metode filter IIR menggunakan karakteristik kecepatan linear
Karakte r a b c d e f g h i j k l m
4.
Jumlah Segmen Acuan 4 4 2 4 3 4 4 5 2 3 6 3 7
Jumlah Segmen Hasil 4 4 3 4 3 4 5 5 2 3 6 3 7
Karakter N O P Q R S T U V W X Y Z
Jumlah Segmen Acuan 5 3 5 3 4 2 3 4 4 6 3 5 5
Jumlah Segmen Hasil 5 3 5 3 4 4 3 4 4 6 4 5 5
Kesimpulan
Pada paper ini, kami mengimplementasikan algoritma segmentasi untuk pengenalan karakter dengan filter IIR menggunakan nilai parameter α = 0,75 dan = 0.75. Algoritma segmentasi ini berdasarkan karakteristik kecepatan linear. Untuk penelitian ini, kami menggunakan 52 karakter tulisan tangan roman dari A sampai Z. Karakter-karakter tersebut didapatkan dari peralatan online (tablet) yang menangkap posisi input (koordinat xi dan yi) dari gerakan pena serta tekanan dalam menulis. Hasil yang diperoleh sangat memuaskan dengan tingkat keberhasilan segmentasi adalah 80%. 5.
Daftar Pustaka
Anquetil, E and Lorette, G. 1997. “Perceptual Model of Handwriting Drawing Application to the Handwriting Segmentation Problem” IEEE. Bourennane, E., P. Gouton, M. Paindavoine, F. Truchetet, 2002. “Generalization Of Canny– Deriche Filter For Detection Of Noisy Exponential Edge”. Signal Processing. 82 (2002) pp 1317 – 1328. Canny, J.1986. “A Computational Approach To Edge Detection”, IEEE on PAMI. vol. 8, pp. 679-697 De Stefano, Claudio., Ciro D’elia, Marco Garruto, Angelo Marcelli and Alessandra Scotto Di Freca. 2005. “A Wavelet Based Curve Decomposition Method for On-Line Handwriting”. Advances in Graphonomics: Proceedings of IGS. De Stefano, C., Guadagno, G. and Marcelli A. 2004. “A saliency-based segmentation method for on-line cursive handwriting”. International Journal of Pattern Recognition and Artificial Intelligence, vol.18, no. 6, pp. 1139-1156. Deriche, R. 1987. “Using Canny’s Criteria To Derive A Recursively Implemented Optimal Edge Detector”, Computer Vision, vol. 1, no. 2 Djioua, Moussa and R, Plamondon. 2008. “A New Algorithm and System for the Characterzation of Handwriting Strokes with Delta-Lognormal Parameters”. IEEE Transactions on Pattern Analysis and Machine Intelligence. Djioua, Moussa, Christian O’Reilly and R.Plamondon. 2006. “An interactive trajectory synthesizer to study outlier patterns in handwriting recognition and signature verification”. Proceeding of the 18th International Conference on Pattern Recognition (ICPR’06).
Jurusan Teknik Mesin dan Industri FT UGM ISBN 978-979-18528-1-4
A-124
Seminar on Application and Research in Industrial Technology, SMART Suryarini Widodo, Sarifuddin Madenda , dan Prihandoko
Guerfali, Wacef and Plamondon, R. 1995. “The Delta LogNormal Theory for the Generation and Modelling of Cursive Character”, IEEE. Jain, Anil K., Robert, P.W Duin and Jianchang Mao. Januari 2000. “Statistical Pattern Recognition : A Review”. IEEE Trans. on Pattern Anal. and Machine Int., vol. 22, no. 1. Laggoune, H., P.Gouton and R.K. Kovasi. 2000. ”Ridge-Line Optmal Detector”. SPIE Proceedings and Journals. Madenda, S., R. Missaoui, J. Vaillancourt & M. Paindavoine. 2007. “An Enhanced Detector of Blurred and Noisy Edges”. Signal Processing for Image Enhancement and Multimedia Processing Madenda, S., R. Missaoui, J. Vaillancourt & M. Paindavoine. 2006. “An Optimal Edge Detector for Automatic Shape Extraction” SITIS Plamondon, R and Djioua, Moussa. 2005. “Handwriting Stroke Trajectory Variability in the context of the Kinematic Theory”. Advances in Graphonomics: Proceedings of IGS. Plamondon, R and Sargur N. Srihari, Januari 2000. “On-Line and Off-Line Handwriting Recognition : A Comprehensive Survey”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 22, no. 1. Plamondon, R.1996. “A Model-Based Segmentation Framework for Computer Processing of Handwriting”. Plamondon, R and Wacef Guerfali. 1996. “Why Handwriting Segmentation Can Be Misleading”. IEEE Proceeding of ICPR. Sánchez, E. Gómez., Y.A. Dimitriadis., M. Sánchez-Reyes Más., P. Sánchez García., J.M. Cano Izquierdo.., J. López Coronado. 1998. “On-Line Character Analysis and Recognition with Fuzzy Neural Networks”. Intelligent Automation and Soft Computing, vol. 7, no. 3, pp. 161162. Sicard, Rudy., Thierry Artières and Eric Petit. 2005. “Modeling on-line handwriting using pairwise relational features”. Shen, J. and S. Castan. 1986. “An optimal linear operator for edge detection”, Conference on Vision and Pattern Recognition, USA. Srihari, S. 2006. “Handwriting Recognititon, Automatic”. Encyclopedia of Languange & Linguistic, vol. 5, pp. 203-211. Tappert, Charles C., Ching Y. Suen and Toru Wakahara. August 1990. “The State of The Art in Online Handwriting Recognition”. IEEE Transaction on Pattern and Machine Intelligence, vol 17, no. 8.
Jurusan Teknik Mesin dan Industri FT UGM ISBN 978-979-18528-1-4
A-125