Klasifikasi Online Citra Daun berdasarkan Fitur Bentuk dan Ruas Daun Agus Zainal Arifin 1, Bayu Bagus 2, Dini Adni Navastara 3 Jurusan Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Email :
[email protected] 1,
[email protected] 2,
[email protected] 3
Abstrak Sistem temu kembali citra untuk aplikasi pengklasifikasian citra daun berdasarkan bentuk dan ruas daun sangat dibutuhkan dalam ilmu botani. Paper ini menjelaskan tentang suatu metode pengenalan jenis daun berdasarkan input berupa sketsa bentuk daun yang dibandingkan terhadap database sketsa daun yang ada. Sistem ini dapat dilakukan secara online sehingga dapat diakses dimanapun dan kapanpun user berada. Metode pengenalan ini meliputi Minimum Perimeter Polygon untuk ekstraksi fitur bentuk pada citra daun, Venation Mathing untuk ekstraksi fitur ruas daun pada citra daun. Untuk mendukung kinerja dua metode diatas, penulis memperkenalkan metode Windowing matrix untuk mendeteksi ujung dan pangkal ruas daun, Thinning Algorithm menjadikan ruas daun lebih sederhana (lining one pixel), dan Rotation Invariant untuk mengubah orientasi daun menjadi tegak lurus. Setelah melalui uji coba dan analisa, dapat disimpulkan bahwa hasil pencarian dengan menggunakan metode diatas mampu menghasilkan F1 Score atau tingkat akurasi 95.83%, Recall sebesar 100%, dan Precision sebesar 92.59%. Kata Kunci: Klasifikasi, online, system temu kembali, fitur bentuk daun, fitur ruas daun, Minimum Perimeter Polygon, Venation Matching, Windowing Matrix, Thinning Algorithm, Rotation Invariant. 1. Pendahuluan Pada beberapa sistem temu kembali citra, sebuah citra dapat direpresentasikan oleh beberapa fitur seperti warna, tekstur, bentuk dan struktur. Citra yang mirip ditentukan oleh kedekatan nilai fitur yang dipakai. Sementara itu di bidang ilmu botani, sangat dibutuhkan teknologi pencarian citra daun secara otomatis dari berbagai koleksi citra daun yang ada. Pada citra daun yang paling banyak adalah berwarna hijau atau coklat. Maka dari itu, fitur warna tidak dapat digunakan pada query citra daun. Tetapi, tiap daun memiliki bentuk dan ruas daun yang berbeda yang dapat digunakan sebagai fitur untuk dilakukan query. Sistem temu kembali citra berdasarkan fitur bentuk telah diakui sebagai pendekatan yang efisien. Contohnya dapat ditemukan
pada sistem pengenalan wajah, sistem pengenalan iris mata dan sistem pengenalan sidik jari. Representasi bentuk obyek dapat diklasifikasikan menjadi 2 kategori, yaitu boundary-based dan regionbased. Dimana boundary-based mendeskripsikan bagian yang menggunakan karakteristik eksternal, dan regionbased merepresentasikan bagian yang menggunakan karakteristik internal. Pada paper ini, karena fokus utama terletak pada karakteristik bentuk seperti tepi obyek, orientasi garis lurus, penggabungan beberapa titik, dan sejumlah lekukan pada tepi obyek, maka dapat menggunakan representasi eksternal. Untuk melakukan representasi bentuk obyek pada citra dapat digunakan metode Minimum Perimeter Polygon [1]. MPP adalah sebuah metode perkiraan poligon atau penelusuran tepi dimana yang diukur adalah tepi obyek pada citra. Meskipun demikian, metode ini mempunyai beberapa kelemahan salah satunya adalah dalam penelusuran titik. Fitur ruas daun belum sepenuhnya dieksploitasi sebagai ukuran kemiripan daun. Yang menarik adalah beberapa spesies tumbuhan mempunyai pola kontur yang hampir sama. Contoh, Nuphar Japonicum dan Nuphar Pumilum adalah anggota dari family Nymphaeaceae. Maka dari itu, fitur ruas daun secara umum dapat digunakan sebagai ukuran kemiripan daun. Oleh karena itu, penulis membangun sebuah sistem klasifikasi citra daun menggunakan fitur bentuk dan ruas daun yang dapat dilakukan secara online. Metode yang digunakan adalah Minimum Perimeter Polygon [2] untuk melakukan ekstraksi fitur bentuk daun. Dan metode Venation Matching [5] untuk melakukan ekstraksi fitur ruas daun. Pada metode tersebut seharusnya dapat dimungkinkan mengenali citra daun dalam posisi berbeda orientasi. Dalam hal ini, digunakan Rotation Invariant (tidak membedakan arah) dan metode yang lebih handal dalam menangani ukuran ruas daun yang berbeda. Oleh karena itu, diusulkan sebuah metode pengenalan citra daun yang mampu menormalisasi orientasi daun menjadi tegak lurus sehingga pengenalan menjadi lebih akurat serta mekanisme pencarian ujung dan pangkal ruas daun secara cepat dan tepat.
1
2. Teori 2.1. Leaf Sketch Image Leaf Sketch Image merupakan citra grayscale yang berisi sketsa obyek daun. Leaf Sketch Image terdapat tepi daun dan ruas ruas daun. Contoh Leaf Sketch Image terdapat pada Gambar 1.
Gambar 1 leaf sketch image
metode penelusuran titik hitam terdekat dengan perkiraan tepi kontur bersambung menjadi sederetan angka, masing-masing angka mewakili sebuah arah kontur. Freeman Code biasanya digunakan dalam 4 titik tetangga atau 8 titik tetangga. Ilustrasi dari Freeman code terdapat pada Gambar 5. Freeman Code dapat digunakan pada garis tepi obyek yang berlekuk lekuk dan tertutup (membentuk bangun lingkar). Pada dasarnya, ada 3 parameter untuk melakukan metode Freeman code. Parameter itu adalah : titik hitam pertama (Po), tahap (L) pencarian titik hitam tetangga (menggunakan diagram arah), terakhir adalah mendapatkan Jalur (T4) sebagai fitur berupa sederetan angka(arah Jalur bisa searah jarum jam atau sebaliknya).
Boundary Leaf merupakan tepi obyek daun yang dapat digunakan sebagai fitur bentuk. Contoh tepi obyek daun dapat dilihat pada Gambar 2.
Gambar 2 boundary leaf Gambar 5 Ilustrasi Freeman code Venation Leaf merupakan ruas ruas daun yang dapat digunakan sebagai fitur ruas daun. Contoh ruas ruas daun dapat dilihat pada Gambar 3.
Gambar 3 venation leaf Tipe ruas daun dibagi menjadi 3 jenis yaitu tipe Pinnate, Parallel dan Palmate. Tipe Pinnate memiliki karakteristik pada tumbuhan dikotil yaitu ada pangkal utama dan ruas ruas yang menyamping. Pada tipe Parallel memiliki karakteristik pada tumbuhan monokotil yaitu hanya ada pangkal utama dan tidak mempunyai ruas daun. Sedangkan pada tipe Palmate, pangkal utama berupa titik yang sebagai pusat ruas ruas daunnya. Tipe ruas daun dapat dilihat pada Gambar 4.
Digunakan : {Po,L,T4} dalam menyatakan parameter-parameter dari Freeman coding. Selanjutnya melihat bagaimana masing-masing parameter menentukan hasil proses dari penelusuran tepi kontur. Memilih titik hitam pertama (Po) dengan cara scanning piksel terhadap warna hitam, diharapkan bisa mendapatkan hasil penelusuran tepi kontur yang sama. L adalah jarak antara titik asal dengan titik tetangga terpilih yang membentuk kontur. Dalam percobaan, nilai L=1 agar representasi bentuk mendapatkan fitur yang akurat. Perbedaan hasil dari penelusuran diagram arah pada sistem adalah jelas, apabila {0,1,2,3,4,5,6,7} dibandingkan dengan {4,5,6,7,0,1,2,3} bentuk obyek jelas akan berbeda. Penjelasan ada pada Gambar 6.
Gambar 6 Perbedaan dalam penelusuran diagram arah
Gambar 4 venation type 2.2. Freeman Code Metode sederhana untuk merepresentasikan nilai dari sebuah tepi kontur adalah Freeman code [8], sebuah
Nilai sederetan angka dalam metode Freeman code adalah mewakili arah jalur. Dimana perbedaan nilai dalam Freeman code mencerminkan ciri atau keunikan bentuk obyek pada setiap citra. Berikut ini adalah implementasi program dari proses Freeman Code : 2
• Pencarian Titik Hitam Pertama Pada langkah kali ini adalah dilakukan scanning titik hitam pertama sebagai acuan penentuan titik hitam berikutnya. • Penelusuran Titik Hitam Tetangga Setelah ditemukan titik hitam pertama, maka langkah selanjutnya adalah menelusuri titik hitam berikutnya sampai sejumlah data arah yang telah ditentukan. • Penyimpanan Data Arah Langkah terakhir dari metode ini adalah mendapatkan sekumpulan data arah atau kode rantai. 2.3. First Different Code Setelah mendapatkan kode rantai, selanjutnya perlu dilakukan pembobotan nilai arah atau dinamakan First Different Code [8]. Proses ini mengacu pada diagram arah dengan berputar searah jarum jam yang dapat dilihat pada Gambar 7.
Gambar 7 Kalkulasi First Different Code Misalkan diketahui sebuah kode rantai 66776221225324 maka vektor bobot arahnya adalah 60701401705216. Hasil tersebut diperoleh dari kode 4 berputar ke kode 6 menghasilkan 6 simpangan, kode 6 berputar ke kode 6 menghasilkan 0 simpangan, kode 6 berputar ke kode 7 menghasilkan 7 simpangan, kode 7 berputar ke kode 7 menghasilkan 0 simpangan dan seterusnya sampai kode rantai habis. 2.4. Rotation Invariant Algoritma [1] ini digunakan untuk merotasi citra berdasarkan sudut tertentu yang didapat dari Criterion dan titik baru. Hal hal penting dari proses ini adalah sebagai berikut : 1. Mencari Criterion dan Titik Baru pada obyek. 2. Misal a, b, c adalah panjang sisi segitiga. A adalah sudut yang berhadapan dengan sisi a. Maka :
cos A = 3.
b2 + c2 − a2 2bc
Maka panjang sisi a dapat dirumuskan :
a = ( x j − xi ) 2 + ( y j − y i ) 2 4. 5.
(1)
(2)
Dimana (xi,yi) dan (xj,yj) : koordinat sudut B dan C. Simulasinya dapat dilihat pada Gambar 8.
Gambar 8 Deskripsi Rotation Adjustment 2.5. Thinning Algorithm Thinning [9] merupakan suatu proses penting sebelum melakukan proses-proses atau operasi-operasi pengolahan citra, seperti dalam proses pengenalan karakter optic, pengenalan sidik jari, pemrosesan teks, dan lain sebagainya. Thinning mengakibatkan points atau lapisan yang diluar dari pola (pattern) dihilangkan sampai berbentuk single pixel lebarnya(berbentuk garis). Garis ini dinamakan kerangka (skeleton) dari objek. Garis yang dihasilkan tersebut tidak dapat dibuat bentuk matematikanya. Piksel-piksel yang ditepi sebagai pembatas sehingga terbentuk pola garis (skeleton). Algoritma Thinning melakukan pengulangan (iteration), dimana piksel-piksel ini diseleksi dengan kriteria-kriteria tertentu untuk memutuskan atau membedakan antara piksel yang akan dihilangkan dan yang tidak. Disini Algoritma Thinning yang dibahas adalah Zhang Suen. Hal hal penting dari algoritma ini adalah sebagai berikut : 1. Proses reduksi piksel pada citra biner sehingga lebar obyek menjadi 1 piksel. 2. Angka 1 adalah piksel hitam dan 0 adalah putih. 3. N(P1) adalah jumlah tetangga P1 bernilai 1. 4. S(P1) adalah jumlah perpindahan nilai 0-1; P2,P3…P9. 5. P2 * P3 = 0 diartikan P2 atau P3 bernilai 0 (nol). Untuk penjelasan aturan pada algoritma ini dapat dilihat pada Gambar 9.
Gambar 9 Penjelasan aturan Thinning 2.6. Normalisasi dan Perhitungan Jarak Nilai normalisasi [8] digunakan untuk menyederhanakan data, dimana data nilai piksel dari sebuah citra tersebut cenderung besar, dengan demikian butuh adanya normalisasi. Dengan normalisasi ini maka data tersebut hanya memiliki range antara nol sampai satu. X= {i0, i1, i2, ....in} Maka |X| =
i +i +i 2
2
2
0
1
2
+ ... + in 2
(3)
X’=(i0/|X|, i1/|X|, ...., in/|X|) , dimana : X = nilai vektor. |X| = nilai pembagi. X’ = nilai vektor hasil. 3
Euclidean Distance dapat dianggap sebagai jarak yang paling pendek antar dua titik, fungsi jarak Euclidean [8] pada dasarnya sama halnya dengan persamaan Pythagoras ketika digunakan di dalam dua dimensi. Secara matematis dapat ditulis di dalam persamaan berikut : d(i,j)=
3.2. Venation Matching Venation Matching digunakan untuk melakukan ekstraksi fitur ruas daun dari obyek. Intinya adalah pendeteksian titik titik ujung dan pangkal ruas daun untuk menentukan tipe ruas daun.
| xi1 −xj1 |2 +| xi2 −xj2 |2 +.....+| xip −xjp |2 , (4) dimana : d(i,j) xi xj
= nilai jarak. = nilai nilai pada fitur 1. = nilai nilai pada fitur 2.
3. Metode Metode yang digunakan dalam membangun sistem temu kembali citra daun ini adalah sebagai berikut : 3.1. Minimum Perimeter Polygon Minimum Perimeter Polygon [7] digunakan untuk ekstraksi fitur bentuk dari obyek. Intinya adalah penyederhanaan bentuk obyek dengan cara reduksi kode rantai dengan hasil berupa poligon sebagai bentuk obyek yang lebih sederhana. Langkah pertama algoritma adalah memilih data masukan berupa Leaf Sketch Image. Kemudian langkah kedua adalah menentukan nilai kompleksitas cell dan menandai area obyek berdasarkan cell. Dalam menentukan nilai cell, telah dilakukan ujicoba pada nilai 2, 3, dan 5. Pengujian nilai cell ini dapat dilihat pada bab lampiran. Nilai yang terbaik adalah 3 karena membutuhkan waktu yang efisien dan fitur hasil juga memenuhi syarat untuk diambil tepi obyeknya. Dilanjutkan dengan merotasi obyek dengan algoritma Rotational Adjustment. Dilakukan penelusuran kode rantai tepi obyek menggunakan Freeman Code dahulu sebelum melakukan reduksi kode rantai dengan tujuan menyederhanakan bentuk obyek. Proses reduksi kode rantai dilakukan dengan pengambilan sejumlah titik. Jumlah titik yang diambil untuk mereduksi kode rantai adalah 14 buah, yang diperoleh dari ujicoba dengan nilai 7, 14, dan 21 dengan alasan nilai 14 titik menghasilkan poligon yang lebih sederhana dan dapat mewakili fitur bentuk obyek. Langkah berikutnya adalah membentuk poligon dari titik titik posisi kode rantai yang sudah direduksi dan menelusuri kode rantai dari tepi polygon menggunakan Freeman Code sekalian dicari vektor bobot arah menggunakan First Different Code. Akhirnya menghasilkan vektor bobot arah yang akan digunakan sebagai fitur bentuk dan dimasukkan ke dalam database.
Gambar 11 Deskripsi ruas daun
Gambar 12 Deskripsi tipe tipe ruas daun Langkah dari algoritma ini adalah melakukan ekstraksi ruas daun dengan menghapus tepi obyek memakai brushing pixel. Kemudian melakukan rotasi obyek ruas daun dengan Rotational Adjustment dengan cara mencari Criterion atas dan bawah yang digunakan posisi x dan y untuk menandai titik baru sehingga dari tiga titik tersebut apabila dihubungkan akan membentuk segitiga. Segitiga yang ada kemudian dicari sudut sudutnya, dimana salah satu sudutnya akan diproses untuk merotasi obyek. Dan dilanjutkan dengan menentukan nilai kompleksitas cell, lalu menandai area obyek ruas daun berdasarkan cell. Dalam menentukan nilai cell, telah dilakukan ujicoba pada nilai 2, 3, dan 5. Pengujian nilai cell ini dapat dilihat pada bab lampiran. Nilai yang terbaik adalah 3 karena membutuhkan waktu yang efisien dan fitur hasil juga memenuhi syarat untuk diambil ruas daunnya. Dari hasil fitur selanjutnya adalah melakukan proses Thinning untuk menyempurnakan fitur ruas daun. Algoritma Thinning Zhang suen disini adalah bertujuan untuk menyederhanakan ruas daun sehingga terbentuk obyek dengan lining 1 piksel atau lebih tipis dari sebelumnya. Pendeteksian titik-titik ujung dan pangkal ruas daun dengan cara Windowing Matrix (3x3) dengan beberapa matriks yang dapat dilihat pada Gambar 3-4. Pada Gambar 3-4 terdapat tiga buah matriks yang berfungsi untuk mendeteksi ujung ujung ruas daun, 3
Gambar 10 Deskripsi tipe-tipe ruas daun
4
buah matriks untuk pangkal ruas daun dan 4 buah matriks untuk deteksi kondisi tipe Palmate. Lalu dari data titik titik ujung dan pangkal ruas daun seperti pada Gambar 3-3 dapat ditentukan tipe ruas daunnya dimana bagian berwarna hijau merupakan ujung ujung dari ruas daun, bagian berwarna biru adalah pangkal ruas daun, dan bagian berwarna merah tua adalah hasil deteksi pangkal yang mengumpul sebagai kondisi tipe Palmate. Akhirnya didapatkan nilai flag untuk tipe tipe ruas daun sebagai data yang disimpan dalam database.
Tampilan aplikasi system dapat dilihat pada Gambar 16 dimana ketika citra daun dimasukkan sebagai uji coba maka akan dihasilkan klasifikasi jenis daun termasuk pinnate, palmate atau parallel. Aplikasi juga menyediakan simulasi proses metode MPP dapat dilihat pada Gambar 17 dan simulasi proses metode VM dapat dilihat pada Gambar 18.
Gambar 16 Tampilan aplikasi
Gambar 13 Deskripsi Windowing Matrix 4. Uji Coba Uji coba dilakukan untuk mengetahui apakah semua fungsi pada aplikasi berjalan sesuai dengan yang diinginkan. 4.1. Uji Coba Sistem Pada subbab ini akan dilakukan uji coba sistem klasifikasi citra daun berdasarkan fitur bentuk dan ruas daun menggunakan metode Minimum Perimeter Polygon dan Venation Matching. Citra yang digunakan berupa Leaf Sketch Image yang terdiri dari boundary dan venation seperti ditunjukkan pada Gambar 14. Data uji coba dapat dilihat pada Gambar 15.
Gambar 17 Tampilan simulasi metode MPP
Gambar 14 Leaf Sketch Image Gambar 18 Tampilan simulasi metode VM
A
D
B
C
F E Gambar 15 Data Uji coba
Nilai threshold yang dipilih dalam menampilkan hasil pencarian adalah 35%, 55%, 75% dan 95% dengan tujuan untuk mengetahui kecenderungan naik dan turunnya nilai Recall dan Precision dari ujicoba. Selanjutnya nilai Recall dan Precision ini digunakan sebagai parameter pengukuran F1 Score dari sistem. F1 Score ini disebut sebagai nilai akurasi dari percobaan. Dalam pemilihan Threshold disini nilai 35% dapat diartikan bahwa nilai jarak yang ditampilkan sebagai hasil adalah antara 0 sampai 0.35, nilai 55% adalah 5
antara 0 sampai 0.55, nilai 75% adalah antara 0 sampai 0.75, dan pada nilai 95% yang ditampilkan adalah jarak antara 0 sampai 0.95. Jika semakin besar nilai threshold, maka akan menghasilkan jumlah citra semakin banyak dan jika semakin kecil nilai threshold, maka akan menghasilkan jumlah citra semakin sedikit. 4.2. Uji Coba Performa System Pengujian dilakukan pada 12 citra query sebagai Data Testing terhadap Data Training, dimana masingmasing Data Testing akan diuji pada beberapa threshold yaitu threshold 35%, 55%, 75%, 95%. Tabel 1 Data Training dalam Database No Tipe Ruas Daun 1 Pinnate 2 Parallel 3 Palmate Total Jumlah Citra
Jumlah Citra 64 18 18 100
Tabel 2 Rata-rata prosentase Recall, Precision dan F1 Score No 1 2 3 4
Threshold 35% 55% 75% 95%
Recall 61.23% 92.40% 99.53% 100%
Precision 92.76% 92.59% 92.59% 92.59%
F1 Score 69.89% 91.67% 95.59% 95.83%
Data Training adalah berupa seratus citra sketsa daun yang telah diketahui terdiri dari citra bertipe Pinnate, Parallel, dan Palmate dengan perbandingan jumlah berdasarkan tipe ruas daun seperti pada Tabel 1. Dari hasil pengujian pada masing-masing threshold, dihitung prosentase akurasinya dengan cara menghitung nilai Recall dan Precision dahulu. Kemudian dari nilai tersebut dicari bobot rata-ratanya yang dihitung dengan F1 Score. Nilai F1 Score yang dihasilkan dapat disebut dengan nilai akurasi.
Gambar 19 Grafik rata-rata prosentase akurasi citra Dari beberapa pengujian seperti pada Tabel 2, dapat diketahui bahwa semakin besar tingkat threshold maka semakin banyak citra yang dihasilkan, sehingga menyebabkan nilai Recall semakin besar dikarenakan citra yang cocok dengan citra query semakin banyak pula. Dan nilai Precision cenderung semakin kecil dikarenakan citra yang tidak cocok dengan citra query juga sedikit bertambah. Hal hal diatas mengakibatkan
prosentase akurasi yang dihasilkan semakin besar. Begitu juga sebaliknya. Pada Gambar 19 dapat dilihat bahwa nilai recall dan precison pada masing masing threshold cenderung berlawanan alias berbanding-terbalik. Jika recall cenderung mengalami kenaikan, maka kemungkinannya precision akan mengalami sedikit penurunan. 5. Kesimpulan Kesimpulan yang diperoleh berdasarkan uji coba dan analisa hasil yang telah dilakukan adalah sebagai berikut : 1. Metode Minimum Perimeter Polygon cukup efektif untuk penyederhanaan bentuk daun, sehingga fitur bentuk lebih optimal. 2. Metode Venation Matching mampu mendeteksi tipe ruas daun pada citra daun. 3. Kesalahan deteksi ruas daun Pinnate dapat terjadi karena ruas ruas daun yang terlalu berhimpitan, sehingga terdeteksi sebagai ruas daun Palmate. 4. Kinerja sistem temu kembali citra daun ini mampu mencapai nilai Recall 100%, Precision 92.59%, dan F1 Score 95.83% pada Threshold 95%. Daftar Pustaka [1]. Yunyoung Nam, Eenjun Hwang, Dongyoon Kim, A similarity-based leaf image retrieval scheme: Joining shape and venation features ,Computer Vision and Image Understanding 110 (2008) 245–259. [2]. J. Sklansky, R.L. Chazin, and B.J. Hansen,Minimum Perimeter Polygons of Digitized Silhouettes, TC(21), No. 3, March 1972, pp. 260-268. [3]. M. Han, D. Jang, The use of maximum curvature points for the recognition of partially occluded objects, Pattern Recognition 23 (1- 2) (1990) 21– 33. [4]. Z. Wang, Z. Chi, D. Feng, Q. Wang, Leaf Image Retrieval with Shape Features, Lecture Notes in Computer Science 1929 (2000) 477–487. [5]. Y. Li, and Z. Chi, and D. Feng, Leaf vein extraction using independent component analysis, IEEE International Conference on Systems, Man and Cybernetics, 2006, pp. 3890– 3894. [6]. Adam Runions, Martin Fuhrer, Brendan Lane, Pavol Federl, Anne-Gaëlle Rolland-Lagan, and Przemyslaw Prusinkiewicz. Modeling and visualization of leaf venation patterns. ACM Transactions on Graphics 24(3), pp. 702-711. [7]. Magnusson Maria, Digital Image Processing Lecture 12 “Various Topics”, CVL Institutionen for system teknik Tekniska Hogskolan Linkopings Universitet. [8]. Bagus Bayu, 2007 : Image Database menggunakan Content Based Image Retrieval dengan Ekstraksi Fitur Terstruktur, PENS-ITS. [9]. Putro Andhika, 2008 : Algoritma Thinning dan Penjelasannya, http://deckasouza.blogspot.com 6
