JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5
1
Implementasi Segmentasi Citra dengan Menggunakan Metode Generalized Fuzzy CMeans Clustering Algorithm with Improved Fuzzy Partitions Ivan Hardiyanto, Yudhi Purwananto, S.Kom, M.Kom, dan Rully Soelaiman, S.Kom, M.Kom Jurusan T.Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected] Abstrak—Segmentasi merupakan proses yang sering digunakan dalam pemilahan citra dan telah menjadi subyek kegiatan penelitian selama beberapa tahun terakhir. Fuzzy CMeans (FCM) adalah salah satu algoritma segmentasi yang banyak digunakan dan memiliki banyak varian dari hasil pengembangan metode tersebut. Tugas Akhir ini memberikan alternatif penyelesaian segmentasi citra dengan menerapkan metode pengembangan dari FCM yaitu Generalized Fuzzy CMeans Clustering Algorithm with Improved Fuzzy Partitions (GIFP FCM). Dalam metode ini akan ditambahkan sebuah membership constraint sehingga tahan dalam mengatasi noise dan meningkatkan konvergensi dari proses segmentasi. Dalam Tugas Akhir ini akan dilakukan perbandingan hasil segmentasi citra yang dihasilkan oleh metode FCM dan GIFP FCM. Uji coba dilakukan pada citra grayscale yang telah ditambahkan noise. Hasil dari kedua metode dibandingkan tingkat kualitasnya dengan koefisien partisi (Vpc) dan entropi partisi (Vpe) dan diketahui bahwa metode GIFP FCM lebih baik daripada metode FCM. Kata Kunci—Algoritma Fuzzy Clustering, Fuzzy Partitions, Membership constraint function, Segmentasi Citra.
I. PENDAHULUAN
S
EGMENTASI citra merupakan salah satu topik penting ilmu komputer terutama dalam bidang pengolahan citra digital dan visi komputer. Tujuan segmentasi citra adalah untuk mempartisi gambar menjadi beberapa wilayah yang tidak tumpang tindih dengan karakteristik yang homogen, seperti intensitas, warna, dan tekstur. Seiring dengan berkembangnya teknologi pada aplikasi yang memproses sebuah obyek seperti rekonstruksi tiga dimensi, pengenalan benda, pengenalan tulisan, deteksi wajah, pengkodean obyek dan lain-lain maka proses segmentasi menjadi semakin diperlukan. Hasil segmentasi juga harus semakin akurat karena ketidak akuratan hasil segmentasi akan mempengaruhi pula hasil proses selanjutnya. Dalam beberapa dekade terakhir, banyak algoritma segmentasi telah dikembangkan. Fuzzy clustering adalah salah satu teknik paling banyak digunakan untuk segmentasi citra. Algoritma Fuzzy c-means (FCM) adalah algoritma fuzzy clustering paling populer dan banyak ditemukan algoritma fuzzy clustering baru berasal dari algoritma tersebut. Namun
kelemahan utama dari algoritma fuzzy clustering adalah sensitif terhadap noise pada citra. Untuk mengatasi masalah ini, sebuah membership constraint yang baru diperkenalkan ke fungsi obyektif dari FCM untuk mendapatkan partisi yang lebih jelas. Dalam Tugas Akhir ini diusulkan alternatif penyelesaian segmentasi citra dengan menerapkan metode pengembangan dari FCM yaitu Generalized Fuzzy C-Means Clustering Algorithm with Improved Fuzzy Partitions (GIFP FCM). GIFP FCM adalah sebuah algoritma fuzzy clustering dengan sebuah membership constraint yang baru diperkenalkan ke fungsi obyektif dari FCM untuk mendapatkan partisi yang lebih jelas. Sehingga lebih efektif dan tahan dalam mengatasi noise. Selain itu dengan memperkenalkan membership constraint yang baru maka didapatkan fungsi keanggotaan dan fungsi obyektif yang baru sehingga meningkatkan konvergensi dari proses segmentasi II. METODE A. Segmentasi Segmentasi citra adalah proses membagi citra digital menjadi beberapa daerah atau kelompok, dimana masingmasing daerah terdiri dari sekumpulan piksel. Segmentasi citra menyederhanakan dan merubah representasi citra ke sesuatu yang lebih bermakna dan lebih mudah untuk dianalisis. Segmentasi citra di-gunakan untuk mencari obyek yang ingin di cari dan batas-batas bentuk objek seperti garis, kurva dalam citra. B. Clustering Clustering merupakan proses pengelompokan data dalam kelas-kelas atau cluster-cluster sehingga data dalam suatu cluster memiliki tingkat kesamaan yang tinggi antara data satu dengan yang lainnya tetapi sangat berbeda dengan data pada cluster lain [4]. Clustering juga dapat dianggap sebagai bentuk kompresi data, di mana sejumlah besar sampel diubah menjadi sejumlah kecil perwakilan prototipe atau cluster. Tergantung pada data dan apli-kasi, berbagai jenis ukuran kesamaan dapat digunakan untuk mengidentifikasi kelas, di mana ukuran kesamaan mengontrol bagaimana cluster terbentuk. Beberapa contoh nilai-nilai yang dapat digunakan
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5
2
sebagai parameter kesamaan termasuk jarak, konektivitas dan intensitas. C. Fuzzy C-Means Fuzzy C-Means adalah suatu teknik clustering (pengelom-pokan) data di mana keberadaan titik-titik data dalam suatu cluster ditentukan oleh derajat keanggotaan. Penentuan titik cluster dilakukan secara berulang-ulang hingga diperoleh data yang akurat berdasarkan derajat keanggotaannya. Perulangan ini didasarkan pada minimalisasi fungsi obyektif yang meng-gambarkan jarak dari titik data ke pusat cluster yang terbobot oleh derajat keanggotaan. Akibat adanya derajat keanggotaan tersebut, maka suatu titik data bisa dimiliki lebih dari satu kelompok. Metode ini merupakan minimasi dari fungsi objektif [4].
sebuah parameter pada fungsi obyektif dan fungsi nilai keanggotaan. GIFP FCM dengan parameter yang tepat dapat mempercepat konvergensi daripada metode FCM [6]. Metode ini memiliki fungsi obyektif: (6) Batasan nilai keanggotaan tetap seperti halnya FCM (7) Untuk proses perubahan membership atau keanggotaan data digunakan persamaan (8) dan pembaruan pusat cluster digunakan persamaan (9) berikut ini:
(1)
(8)
Di mana merupakan jarak squared euclidean distance antara titik data ke j dengan pusat cluster ke i, u merupakan matriks partisi dari derajat keanggotaan. Variabel m merupakan angka real yang harus lebih besar dari 1 yang merepresentasikan eksponen pembobotan untuk keanggotaan dan bernilai konstan yang mengontrol pembagian nilai fuzzy. Derajat keanggotaan suatu partisi matriks memiliki syarat dimana jumlah keanggotaan suatu titik data terhadap semua cluster yaitu: (2) Dengan menggunakan fungsi objektif Fuzzy C-Means mempartisi data masuk ke dalam cluster-cluster hingga optimasi dari fungsi objektif tercapai. Untuk proses perubahan membership atau keanggotaan data digunakan persamaan (3) dan pembaruan pusat cluster digunakan persamaan (4) berikut ini (3)
(4) Keanggotaan data terhadap cluster dan pusat cluster akan terus mengalami perubahan mencapai konvergensi di mana perubahan batas minimum distance error (ε) yang telah ditentukan sebagai termination criterion yang ditujukkan dengan persamaan: (5)
D. Generalized fuzzy c-means clustering algorithm with improved fuzzy partitions Generalized fuzzy c-means clustering algorithm with improved fuzzy partitions (GIFP FCM) adalah sebuah algoritma FCM yang dimodifikasi dengan ditambahkan
(9) Karena rumus update nilai keanggotaan telah ditambahkan maka nilai akan berubah setiap kali iterasi, parameter untuk menjadikan 0 <
< 1, maka:
= α min
(10)
dimana parameter α (0 < α < 1) yang mengontrol kecepatan konvergensi dari GIFP FCM. Nilai akan bergantung pada inputan nilai α. Keanggotaan data terhadap cluster dan pusat cluster akan terus mengalami perubahan mencapai konvergensi di mana perubahan batas minimum distance error (ε) yang telah ditentukan sebagai termination criterion yang ditujukkan dengan persamaan: (11) Metode ini memiliki perbedaan dengan Fuzzy C-means dimana untuk proses perubahan nilai keanggotaan (membership) melibatkan nilai . Sedangkan untuk proses pembaruan pusat cluster menggunakan rumus yang sama dengan Fuzzy C-means. III. HASIL DAN PEMBAHASAN A. Fungsi Validitas (Vpc dan Vpe) Fungsi validitas adalah fungsi yang dihitung yang digunakan untuk menilai secara kuantitatif dan mengevaluasi hasil kerja clustering [5]. Fungsi representasi untuk partisi fuzzy adalah koefisien partisi (Vpc) dan entropi partisi (Vpe) yang didefinisikan sebagai :
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5
3
(12) (13)
a
b
c
d
e
f
g
h
i
j
k
l
n
o
dimana: : koefisien partisi : entropi partisi
: Nilai keanggotaan dari fuzzy untuk cluster ke-i dan data ke-j
: Total jumlah pixel pada citra Gagasan kedua fungsi validitas tersebut adalah bahwa partisi dengan ketidakteraturan (fuziness) yang kurang, berarti menunjuk-kan kinerja yang lebih baik. Jadi pengelompokan terbaik dicapai bila Vpc maksimal dan Vpe minimal. B. Hasil Pengamatan Uji coba terhadap sistem untuk melakukan proses segmentasi citra dengan menggunakan metode FCM dan GIFP FCM. Uji coba yang dilakukan diantaranya adalah dengan memasukkan data masukan awal berupa citra grayscale yang di dalamnya diberikan noise. Kemudian dilakukan proses segmentasi sehingga dapat dihasilkan citra yang tersegmentasi yang nantinya akan dibandingkan nilai Vpc dan Vpe-nya. Implementasi pada penelitian ini menggunakan perangkat lunak Matlab dengan processor intel core i3 untuk sengmentasi citra grayscale. Gambar 1a dan 1c menunjukan citra house dan blood yang belum diberikan noise, gambar 1b dan 1d adalah citra house dan blood yang telah diberikan gaussian noise. Citra disegmentasi berdasarkan jumlah inputan cluster mulai n=3, n=4, dan n=5. Selain itu citra disegmentasi berdasarkan perubahan nilai parameter α (alfa) mulai dari α=0.1 hingga α=0.99 serta berdasarkan perubahan tingkat gaussian noise mulai dari (0, 0.006) hingga (0, 0.025). Beberapa hasil dari citra tersebut dapat dilihat pada gambar 1k-1p. Hasil nilai Vpe dan Vpe dapat dilihat pada gambar 2 dan gambar 3. Sedangkan perbandingan nilai Vpc dan Vpe berdasarkan nilai parameter α (alfa) dan berdasarkan tingkta noise dapat dilihat pada gambar 4.–gambar 7. Dari diagram tersebut dapat dilihat bawah hasil Vpc dan Vpe pada GIFP FCM lebih baik dari FCM sedangkan jumlah iterasi pada GIFP FCM lebih sedikit dibanding jumlah iterasi pada FCM. IV. KESIMPULAN/RINGKASAN Berdasarkan sejumlah uji coba yang telah dilakukan didapatkan beberapa kesimpulan, yaitu : 1. Metode GIFP FCM memiliki nilai koefisien partisi (Vpc) lebih baik dibandingkan nilai koefisien partisi metode FCM. 2. Metode GIFP FCM memiliki nilai entropi partisi (Vpe) lebih baik dibandingkan nilai entropi partisi metode FCM.
m
p Gambar. 1. (a)house 256x256 pixel (b)blood 272x265 pixel (c)house with noise (d)blood with noise (e)peppers 256x256 pixel (f)peppers with noise (g)lena 256x256 pixel (h)lena with noise (i)rice 256x256 pixel (j)rice with noise (k)peppers GIFP cluster = 3 (l)house GIFP cluster = 4 (m)lena GIFP cluster = 5 (n)rice GIFP cluster = 3 (o)blood GIFP cluster = 4 (p)blood GIFP cluster = 5
3. Rata-rata jumlah iterasi pada metode GIFP FCM lebih sedikit dibandingkan metode FCM. 4. Jumlah cluster yang diinputkan mempengaruhi hasil segmentasi dibuktikan dengan semakin kecil nilai Vpc dan semakin besar nilai Vpe jika inputan cluster semakin besar. 5. Semakin besar nilai alfa (α) maka hasil Vpc dan Vpe yang dihasilkan semakin baik. 6. Semakin rendah tingkat noise maka hasil Vpe dan Vpe cenderung membaik.
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5
Gambar. 2. Diagram perbandingan nilai Vpc pada FCM dan GIFP FCM
Gambar. 3. Diagram perbandingan nilai Vpe pada FCM dan GIFP FCM
Gambar. 4. Diagram perbandingan nilai Vpc dengan nilai parameter yang bervariasi
Gambar. 5. Diagram perbandingan nilai Vpe dengan nilai parameter yang bervariasi
4
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5
Gambar. 6. Diagram perbandingan nilai Vpc dengan tingkat noise yang bervariasi
Gambar. 7. Diagram perbandingan nilai Vpe dengan tingkat noise yang bervariasi
DAFTAR PUSTAKA [1] [2] [3] [4]
[5]
[6]
[7]
[8] [9]
Youssef,A., "Image Downsampling and Upsampling Methods", Department of EECS, The George Washington University. Gonzalez R.C., Woods R.E, Digital Image Processing, Third Edition, Prentice Hall, 2008. Gonzalez, R. C. and Woods, R. E. Digital Image Processing Using MATLAB, Prentice Hall, Upper Saddle River, NJ. 2004. B. Sowmya, B. Sheela Rani. “Colour image segmentation using fuzzy clustering techniques and competitive neural network”, Elsevier Applied Soft Computing ScienceDirect. Sathyabama University, Old Mamallapuram Road, Chennai 600119, India, 2010. F.Zhao, L.Jiao, H.Liu, and X.Gao, “A novel fuzzy clustering algorithm with non local adaptive spatial constraint for image segmentation”, Signal Process. 91 (12) (2011) 988–999. L. Zhu, F.L. Chung, S.T. Wang, Generalized fuzzy c-means clustering algorithm with improved fuzzy partitions, IEEE Trans. Syst., Man, Cybern. B, Cybern. 39 (3) (2009) 578–591. A. Buades, B. Coll, J.M. Morel, A non-local algorithm for image denoising. in: Proc. IEEE Int. Conf. Comput. Vision Pattern Recognition. (2005) 60–65. http://www.mathworks.com/matlabcentral/fileexchange/13176-nonlocal-means-filter. Image Processing Toolbox, The MathworksInc.
5
