PENGENALAN OBJEK PADA CITRA DIGITAL MENGGUNAKAN ALGORITMA HIERARCHICAL ALGOMERATIVE CLUSSTERING UmmulKhair, M.Kom1, Rahmadsyah, M.Kom2, Aja Abdurajak3 Program StudiTeknikInformatikaSTT-Harapan Medan Jl. H. M. Joni No.70 C Medan
[email protected] Abstrak Citra digital merupakanrepresentasiobjekataugelombang yang terdapatpadadunianyatadalam format digital.Dalamkehidupansehari-harinyamanusiaseringkalimemanfaatkancitradigitaluntukmerepresentasikanobjek – objek yang beradapadasekitarkitauntuktujuandokumentasiataupuntujuanlainnya.Algoritma hierarchical agglomerative clustering di-implementasikandengancaramengelompokkanpiksel – pikselcitra digital denganmengganggapsetiappikselmerupakansebuahkelompokpadaawalnya. Setiapiterasiatautahapakandilakukanpenggabunganantaraduakelompokmenjadisatukelompok yang baruberdasarkankedekatanwarnaantarakeduakelompoktersebut. Proses pengelompokantersebutterusdilakukansampaijumlahkelompok yang ditentukantercapai. Informasikelompok yang terbentukkemudiandigunakanuntukmengelompokkanpikselobjekpada proses identifikasi. Jumlahpikselpadatiapkelompokkemudiandibandingkandenganjumlahpikseltiapkelompokdariobjek yang telahdilatih.Jikajumlahpikselterpenuhimakaobjektersebut di-identifikasisesuaidengan data informasiobjek yang diperolehpadasaat proses pelatihan. Kata Kunci : Citra Digital, hierarchical agglomerative clustering, piksel. Abstrack Digital imagery is a representation of objects or waves that exist in the real world in digital format. In everyday life, people often use digital images to represent objects around us for documentation or other purposes. Hierarchical agglomerative clustering algorithms are implemented by grouping digital image pixels by assuming each pixel is a group at first. Each iteration or stage will be merged between the two groups into a new group based on the color closeness between the two groups. The grouping process continues until the number of specified groups is reached. The resulting group information is then used to group object pixels in the identification process. The number of pixels in each group is then compared to the number of pixels per group of the trained object. If the number of pixels is fulfilled then the object is identified in accordance with the object information data obtained during the training process. Keywords: Digital Image, hierarchical agglomerative clustering, pixels.
1.
Pendahuluan Citra digital merupakan representasi objek atau gelombang yang terdapat pada dunia nyata dalam format digital[1].Citra digital telah berkembang seiring berkembangnya teknologi manusia. Dalam kehidupan sehari-hari manusia telah memanfaatkan citra digital hampir di setiap bidang seperti kedokteran, industri, pertanian, geologi, kelautan dan lain sebagainya. Kehadiran teknologi citra digital memberikan perkembangan yang sangat signifikan pada bidangbidang tersebut. Dalam kehidupan sehari-harinya manusia seringkali memanfaatkan citra digital untuk merepresentasikan objek – objek yang berada pada sekitar kita untuk tujuan dokumentasi ataupun tujuan lainnya. Objek – objek tertentu memiliki nilai yang sangat tinggi pada beberapa bidang seperti keamanan, kesehatan, pendidikan dan bidang – bidang lainnya. Nilai yang dimiliki dari representasi objek pada citra digital tersebut mendorong munculnya penelitian untuk mengidentifikasi identitas dari objek tersebut. Pengenalan objek atau object recognition telah berkembang seiring berkembangnya teknologi
komputer sehingga melahirkan beberapa bidang baru seperti pengenalan wajah, pengenalan sidik jari sampai pengenalan. Pengenalan objek yang terus berkembang dan telah menjadi kebutuhan pada berbagai bidang mendorong penulis untuk meneliti pengenalan objek pada citra digital dengan menggunakan teknik clustering yaitu metode hierarchical agglomerative. Metode hierarchical agglomerative bekerja dengan mengelompokkan piksel warna pada objek berdasarkan jarak tetangga terdekat. Setiap piksel pada awalnya dianggap sebagai sebuah cluster yang kemudian tiap cluster akan mencari tetangga terdekat untuk bergabung menjadi cluster baru. Proses pembentukan cluster terus dilakukan sampai batas jumlah cluster tercapai. Metode agglomerative hierarchical menawarkan solusi yang cepat dan sederhana dalam pengelompokan piksel. Hasil dari pengelompokkan akan menjadi ciri dari objek yang dikenali sehingga dapat digunakan pada proses uji identifikasi. Tujuan dari penelitian ini, antara lain :
a. Meneliti kemampuan metode hierarchical agglomerative clustering pada pengenalan objek pada citra digital. b. Merancang dan membangun aplikasi pengenalan objek menggunakan metode hierarchical agglomerative clustering pada citra digital. Citra digital merupakan citra f(x,y) yang telah dilakukan digitalisasi baik area koordinat maupun level brightness. Nilai f di koordinat (x,y) menunjukkan level brightness atau grayness dari citra pada titik tersebut. Dengan kata lain sederhananya bahwa citra digital adalah citra yang telah disimpan atau dikonversi ke dalam format digital. [2]
Gambar 1.Citra Lena dalam sumbu koordinat Dari gambar di atas, citra digital dapat didefinisikan sebagai fungsi dua variabel, f(x1,y1), dengan x1 dan y1 adalah koordinat spasial dan nilai f(x1,y1) adalah intensitas citra pada koordinat tersebut. Object Recognition atau pengenalan objek merupakan bidang yang memiliki konsentrasi dalam mendeskripsikan identitas dari sebuah objek yang diamati pada citra digital [3]. Teknik clustering merupakan seni atau teknik mengelompokkan data(objek), kedalam beberapa kluster(kelompok) yang belum diketahui. Berbeda dengan teknik klasifikasi, pada clustering, jumlah dan karakteristik dari kelompok akan diperoleh dari data dan biasanya kelompok-kelompok tersebut belum diketahui maksudnya. Secara umum metode clustering dikelompokkan menjadi dua yaitu metode berbasis hirarki(hierarchical) dan metode berbasis partisi(non hierarchical). Algoritma hirarki menghasilkan pengelompokkan seperti tree atau dendogram. Pada level puncak tree setiap objek dinyatakan sebeagai kluster terpisah.pada level tengah jumlah kluster berkurang dan pada level terbawah semua objek dikelompokkan menjadi satu kluster. Salah satu metode yang tergolong ke dalam metode hirarki dan paling sering digunakan adalah Agglomerative Hierarchical. Berbeda dengan algoritma hirarki yang mengelompokkan objek dengan konsep tree, metode partisi mengelompokkan objek dengan mencari pusat kluster(cluster seeking). Seluruh objek akan dipartisi ke dalam beberapa kluster dengan setiap kluster memiliki pusat kluster. Dalam statistik, pengelompokkan hirarki(hierarchical clustering) adalah metode analisis kelompok yang berusaha untuk membangun sebuah hirarki kelompok[4]. Strategi untuk pengelompokan
hirarki umumnya jatuh ke dalam dua jenis yaitu aglomeratif dan divisif. Pengelompokan hirarki aglomeratif merupakan metode pengelompokan dengan pendekatan bawah-atas(bottom up). Proses pengelompokan dimulai dari masing-masing data sebagai satu buah kelompok, kemudian secara rekursif mencari kelompok terdekat sebagai pasangan untuk bergabung sebagai satu kelompok yang besar. Proses tersebut diulang terus sehingga tampak bergerak keatas membentuk jenjang(hirarki). Algoritma Agglomerative Hierarchical Clustering adalah sebagai berikut : 1. Hitung Matrik Jarak antar data. 2. Ulangi langkah 3 dan 4 higga hanya satu kelompok yang tersisa. 3. Gabungkan dua kelompok terdekat berdasarkan parameter kedekatan yang ditentukan. 4. Perbarui Matrik Jarak antar data untuk merepresentasikan kedekatan diantara kelompok baru dan kelompok yang masih tersisa. 5. Selesai. Membentuk Matrik Jarak, misal dengan Manhattan Distance :
Di mana: d = jarak Single Linkage merupakan salah satu contoh dari bentuk pengelompokan data (clustering). Metode pengelompokan ini menggunakan obyek yang paling dekat atau paling sama antar objek satu dengan yang lain untuk dikelompokkan. Jarak antara dua kluster dipilih dari jarak yang terdekatdari semua pasangan data dalam dua kluster.
Gambar 2. Single Linkage
1.
2.
Untuk menggunakan algoritma ini ada beberapa langkah yang harus dilakukan yaitu : Mulai dengan N cluster, setiap cluster mengandung entiti tunggal dan sebuah matriks simetrik dari jarak (similarities) D = {dik} dengan tipe NxN. Cari matriks jarak untuk pasangan cluster yang terdekat (paling mirip). Misalkan jarak
3.
4.
antara cluster U dan V yang paling mirip adalah duv. Gabungkan cluster U dan V. Label cluster yang baru dibentuk dengan (UV). Update entries pada matrik jarak dengan cara : a) Hapus baris dan kolom yang bersesuaian dengan cluster U dan V b) Tambahkan baris dan kolom yang memberikan jarak-jarak antara cluster(UV) dan cluster-cluster yang tersisa. Ulangi langkah 2 dan 3 sebanyak (N-1) kali. (Semua objek akan berada dalam cluster tunggal setelah algoritma berahir). Catat identitas dari cluster yang digabungkan dan tingkat-tingkat (jarak atau similaritas) di mana penggabungan terjadi.
pada citra digital untuk mengidentifikasi objek objek tersebut. 3. 3.1
Hasil Dan Pembahasan HasilPengujian Penelitian identifikasi objek pada citra digital menggunakan hierarchical agglomerative clustering yang dilakukan pada penelitian ini menghasilkan sebuah sistem aplikasi yang dapat digunakan untuk meng-identifikasi objek pada citra digital menggunakan metode hierarchical agglomerative clustering. Adapun sistem yang dikembangkan pada penelitian ini terdiri dari beberapa form yaitu form utama, form pelatihan dan form identifikasi.
Dalam pengerjaan menggunakan metode ini, ada beberapa perhitungan yang harus dilakukan diantaranya: 1. Mencari nilai rata-rata tiap parameter (2) Di mana : = nilai rata-rata parameter xi = nilai parameter n = jumlah objek 2. Mencari standar devisiasi tiap parameter (3) Di mana: std(x) = nilai standarisasi parameter xi = nilai parameter = nilai rata-rata parameter 3.
Mencari nilai standar untuk masing-masing objek
Gambar 3. Tampilan Form Utama Form utama seperti yang terlihat pada gambar 3merupakan form yang dikembangkan sebagai antarmuka penghubung ke form – form lainnya. Form utama memiliki tiga navigasi utama yaitu menu data objek, menu pelatihan dan menu identifikasi. (4)
Di mana: = nilai standar masing-masing objek xi = nilai parameter = nilai rata-rata parameter std(x) = nilai standarisasi parameter 2.
MetodePenelitian Metode pengumpulan data yang digunakan dalam pembahasan masalah ini adalah sebagai berikut: a. Studi Literatur : yaitu tahap pengumpulan data dengan cara mengumpulkan literatur, jurnal, paper, dan buku-buku yang berkaitan dengan judul penelitian, serta mencari informasi dari berbagai sumber di internet untuk mengetahui perkembangan terbaru dari data yang diambil sebagai bahan dalam pembuatan penelitian. b. Metode Pengembangan: tahap pengembangan aplikasi merupakan tahap pembuatan sistem sistem yang dilakukan dengan menerapkan konsep identifikasi objek pada citra digital yang digunakan untuk menunjang kelengkapan penelitian. c. Metode Analisis: melakukan analisis hasil uji coba program kepada para objek objek yang terdapat
Gambar 4. Form Data Objek Form data objek seperti yang terlihat pada gambar 4. memiliki fitur untuk melakukan perubahan nama objek yang sudah terdaftar pada database. Objek – objek yang terdaftar pada antarmuka data objek ini merupakan data – data objek yang diperoleh dari
proses pelatihan pada antarmuka form pelatihan seperti yang dapat dilihat pada gambar 5 berikut.
menyusun objek pada citra digital input akan dikelompokkan menggunakna algoritm hierarchical agglomerative clustering dan akan di-identifikasi menggunakan tombol “Identifikasi”. 3.2
Pembahasan Analisis dan perancangan sistem merupakan proses analisis secara mendalam terhadap suatu sistem atau lingkungan dalam rangka mengembangkan prosedur dan metode yang dapat merepresentasikan proses dari operasi yang dilakukan oleh sistem yang akan dibangun (Jawahar, 2011). Analisa pada penelitian ini dilakukan secara bertahap yaitu analisis sistem dan analisis algoritma agglomerative clustering. Proses analisa kemudian dilanjutkan dengan tahap perancangan yang mana dimulai dengan perancangan use case diagram dan perancangan flowchart. Gambar 5.Form Pelatihan Form pelatihan seperti yang terlihat pada gambar 5 memiliki fitur untuk membuka gambar objekyang memiliki objek untuk dikenali oleh aplikasi yang dibangun. Informasi piksel yang menyusun objek pada citra digital input akan dikelompokkan menggunakna algoritm hierarchical agglomerative clustering dengan melakukan klik pada tombol “Mulai Proses”. Informasi pengelompokan yang diperoleh kemudian dapat disimpan kedalam database untuk dapat digunakan pada proses identifikasi. Penyimpanan informasi objek kedalam database dapat dilakukan dengan melakukan klik pada tombol “Simpan”. Proses penyimpanan membutuhkan nama objek sehingga nama objek harus di-isi terlebih dahulu pada kolom nama objek.
3.3
Analisis Spesifikasi Sistem Penelitian ini bertujuan untuk membangun sebuah aplikasi yang mampu mengidentifikasi atau mengenali jenis objek yang terdapat pada citra digital. Algoritma yang digunakan untuk proses pengidentifikasian pada penelitian ini menggunakan algoritma agglomerative clustering. Untuk dapat membangun aplikasi yang dimaksud maka diperlukan analisis terhadap spesifikasi dari sistem yang akan dibangun sehingga diperoleh spesifikasi sistem sebagai berikut. 1. Aplikasi dibangun pada lingkungan berbasis desktop dengan menggunakan perangkat lunak pengembangan Microsoft Visual Studio 2010. 2. Aplikasi memiliki fitur pelatihan dan pengenalan objek pada citra digital. 3. Pengenalan objek dilakukan menggunakan algoritma agglomerative clustering. Metode hierarchical agglomerative bekerja dengan mengelompokkan piksel warna pada objek berdasarkan jarak tetangga terdekat. Setiap piksel pada awalnya dianggap sebagai sebuah cluster yang kemudian tiap cluster akan mencari tetangga terdekat untuk bergabung menjadi cluster baru. Proses pembentukan cluster terus dilakukan sampai batas jumlah cluster tercapai (Saad, Mohamed, & AlQutaish, 2012). Pada bagian analisis dari penelitian penelitian ini akan digunakan citra sample atau citra contoh yang akan digunakan sebagai bahan analisis seperti yang dapat dilihat pada gambar 7 berikut :
Gambar 6. Form Identifikasi Form identifikasi gambar 6 memiliki fitur objekyang memiliki objek aplikasi yang dibangun.
seperti yang terlihat pada untuk membuka gambar untuk di-identifikasi oleh Informasi piksel yang
Gambar 7. Contoh Potongan Citra Input Contoh potongan citra input seperti yang terlihat pada gambar 3.2 merupakan citra warna yang setiap pikselnya disusun oleh komponen R, G dan B.
Berikut tabel nilai piksel dari contoh citra yang digunakan. Tabel 1 Nilai Piksel Citra Input (128,250,255) (100,120,100) (55,60,40) (255,120,220) (128,127,100) (40,60,40) (30,120,110) (34,14,50) (10,10,10) Proses pengelompokan menggunakan algoritma agglomerative clustering dapat dijabarkan sebagai berikut : 1. Menentukan jumlah kelompok yang ingin dibentuk.Sebagai analisis diasumsikan kelompok yang akan dibentuk adalah sebanyak tiga kelompok. 2. Membentuk kelompok awal dari setiap piksel C1 = (128,250,255) = Piksel (0,0) / Piksel 1 C2 = (100,120,100) = Piksel (1,0) / Piksel 2 C3 = (55,60,40) = Piksel (2,0) / Piksel 3 C4 = (255,120,220) = Piksel (0,1) / Piksel 4 C5 = (128,127,100) = Piksel (1,1) / Piksel 5 C6 = (40,60,40) = Piksel (2,1) / Piksel 6 C7 = (30,120,110) = Piksel (0,2) / Piksel 7 C8 = (34,14,50) = Piksel (1,2) / Piksel 8 C9 = (10,10,10) = Piksel (2,2) / Piksel 9 3. Mencari pasangan piksel dengan jarak terdekat pada masing – masing piksel dan membentuk kelompok baru dari pasangan tersebut. C1baru = C1Lama + C4Lama = { (128,250,255), (255,120,220) } C2baru = C2Lama + C5Lama = { (100,120,100), (128,127,100) } C3baru = C3Lama + C6Lama = { (55,60,40), (40,60,40) } C4baru = C8Lama + C9Lama = { (34,14,50), (10,10,10) } C5baru = C7Lama = { (30,120,110) } 4. Dikarenakan jumlah kelompok yang diperoleh masih lebih besar dari yang ditentukan maka proses pengelompokkan dilanjutkan dengan membentuk pasangan dari kelompok sebelumnya. Sehingga pada akhirnya diperoleh hasil pengelompokkan dengan tiga kelompok akhir sebagai berikut. C1 = { (128,250,255), (255,120,220), (100,120,100), (128,127,100) } C2 = { (55,60,40), (40,60,40), (34,14,50), (10,10,10) } C3 = { (30,120,110) } 5. Informasi hasil pengelompokkan diatas kemudian disimpan kedalam database untuk digunakan pada proses identifikasi.
2.
4. 4.1
[1]
Penutup Kesimpulan Berdasarkan penelitian yang dilakukan terdapat beberapa kesimpulan: 1. Proses pengenalan objek pada citra digital menggunakan konsep pengelompokan atau clustering berdasarkan pada penelitian yang telah dilakukan dapat disimpulkan bahwa konsep dasarnya adalah melakukan pembagian terhadap
3.
4.2
piksel – piksel pada citra digital ke dalam beberapa kelompok berdasarkan kedekatan warna antara satu piksel dengan piksel lainnya. Berdasarkan kelompok – kelompok yang terbentuk dapat menjadi acuan atau referensi dalam menentukan jenis objek berdasarkan kelompok warna yang terbentu dari objek tersebut. Algoritma hierarchical agglomerative clustering di-implementasikan dengan cara mengelompokkan piksel – piksel citra digital dengan mengganggap setiap piksel merupakan sebuah kelompok pada awalnya. Setiap iterasi atau tahap akan dilakukan penggabungan antara dua kelompok menjadi satu kelompok yang baru berdasarkan kedekatan warna antara kedua kelompok tersebut. Dengan kata lain setiap kelompok akan mencari kelompok lain yang memiliki kesamaan warna terdekat untuk membentuk sebuah kelompok baru. Proses pengelompokan tersebut terus dilakukan sampai jumlah kelompok yang ditentukan tercapai. Informasi kelompok yang terbentuk kemudian digunakan untuk mengelompokkan piksel objek pada proses identifikasi. Jumlah piksel pada tiap kelompok kemudian dibandingkan dengan jumlah piksel tiap kelompok dari objek yang telah dilatih. Jika jumlah piksel terpenuhi maka objek tersebut di-identifikasi sesuai dengan data informasi objek yang diperoleh pada saat proses pelatihan. Akurasi dari algoritma hierarchical agglomerative clustering cukup baik khususnya pada objek yang memiliki warna khusus atau warna yang telah menjadi ciri dari objek tersebut. Saran Berikut beberapa saran yang disampaikan oleh
penulis : 1. Proses identifikasi membutuhkan sumberdaya komputasi yang besar sehingga direkomendasikan spesifikasi komputer yang cukup baik untuk menganalisis metode agglomerative clustering. 2. Proses pengenalan cukup baik namun dapat menghasilkan pengenalan yang buruk jika objek yang berbeda memiliki warna dominan yang sama sehingga untuk penelitian yang akan datang diharapkan perlunya penambahan metode atau algoritma untuk mengatasi kelemahan tersebut. 5.
Daftar Pustaka
Abdul KadirdanAdhiSusanto. 2013. TeoridanaplikasiPengolahan Citra. Yogyakarta :Andi. [2] Ghazali Moenandar Male, Wirawan, Eko Setijadi. 2012. Analisa Kualitas Citra Pada Steganografi Untuk Aplikasi E-Government. Seminar Nasional Jurnal Teknologi XV. [3] Yang, M. H.(2011). Object Recognition. Merced: University of California.
[4]
Prasetyo, Eko.2012. Data Mining KonsepdanAplikasiMenggunakanMatlab.Yog yakarta: Andi