SEGMENTASI CITRA MENGGUNAKAN PENGHAPUSAN TEKSTUR DAN K-MEANS DENGAN BATASAN RUANG Gama Wisnu Fajarianto1, Handayani Tjandrasa2 Jurusan Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Email:
[email protected] ABSTRAK Dalam kaitan dengan kesederhanaan dan efisiensi, pendekatan clustering adalah salah satu teknik pertama yang digunakan untuk segmentasi gambar tekstur. Metode yang dikenal dengan K-Means adalah beberapa dari teknik yang paling umum digunakan dalam bidang segmentasi berbasis clustering dan sejauh ini adalah algoritma clustering paling populer digunakan di aplikasi industri dan pembelajaran mesin Langkah pertama segmentasi gambar menggunakan penghapusan tekstur dan K-Means dengan batasan ruang adalah berdasarkan pada prosedur de-texturing yang bertujuan mengubah input alami gambar berwarna menjadi gambar berwarna tanpa tekstur. Setelah gambar de-tekstur ini diestimasi, segmentasi akhir didapat dengan segmentasi K-means dengan batasan ruang. Batasan ruang ini membantu proses perulangan pelabelan dalam K-means agar berhasil menemukan segmentasi yang akurat. Dari hasil keseluruhan skenario percobaan yang dilakukan didapatkan performa tertinggi nilai akurasi PRI 74.21% yaitu dengan nilai threshold, subdivision, size window dan K secara berurutan adalah 0.25, 5000, 5, dan 9 Kata kunci: segmentasi tekstur, K-Means clustering, penghapusan tekstur. ekstraksi fitur pada citra, fitur sampel, yang berupa vektor dikelompokkan bersama sebagai cluster-cluster yang berkorespondensi terhadap kelas dari citra. Sekumpulan connected piksel masuk ke setiap kelas yang di estimasi sehingga menampilkan region-region yang berbeda. Pada makalah ini akan dibahas mengenai salah satu metode segmentasi citra dengan menggunakan penghapusan tekstur dan KMeans dengan batasan ruang.
1. PENDAHULUAN Segmentasi merupakan proses yang penting dalam pengolahan citra. Oleh karena itu Segmentasi telah secara luas dipelajari dan digunakan juga di dalam bidang perindustrian dalam sepuluh tahun terakhir ini. Clustering adalah salah satu teknik yang digunakan dalam segmentasi. Clustering itu sendiri merupakan proses pengelompokan data dalam kelas-kelas atau cluster-cluster sehingga data-data dalam suatu cluster memiliki tingkat persamaan yang tinggi satu dengan yang lainnya tetapi sangat berbeda dengan data pada cluster lain. Dalam kaitannya dengan segmentasi, data pada clustering adalah piksel pada citra. Metode K-Means adalah teknik yang paling umum digunakan dalam segmentasi berbasis clustering. Setelah dilakukan pemilihan dan
2. ANALISIS Pada bagian ini akan dibahas mengenai proses penghapusan tekstur yang terdiri dari perhitungan bin deskriptor, clustering K-Means dengan bin deskriptor sebagai fitur, proses subdivisi, pergantian nilai piksel daerah dan rata-rata nilai piksel antar ruang warna. 1
1
oses segmenttasi K-Meanss Kemudiann dibahas pro dengan batasan ruaang yang terdiri darii p, perhitungaan edge mapp perhitungan edge map homogen,, pengambiilan fitur pada hasill penghapuusan tekstur dan d segmenttasi K-Meanss dengan baatasan ruang.
Dim mana Nx p x di dalam d : Sekumpuulan lokasi piksel N0 x N0 neighborhhood region yang memilikki pusat x h [ ] : Bin deskkriptor : arrayy bertipe floaat dari Nb (h[0], h[1], … , h[[Nb – 1]) Nb = q3 (pannjang bin desskriptor denggan q adalah bilangan b bulatt
2.1 Pengghapusan Teekstur Penghhapusan tek kstur bertuj ujuan untukk menguranngi komplekssitas atau diimensi tinggii fitur deskkriptor yang merupakan karakteristikk pada warnna tekstur. Proses penghapussan tekstur secara s umum m membutuhhkan perhitun ngan bin desskriptor yangg dihitung pada p setiap ru uang warna. Ruang warnaa yang diguunakan ada 10 yaitu RGB B, HSV, YIQ,, XYZ, LA AB, LUV, I1I2I3, H1H2H3, YCbCr, TSL. Hasil perhitungan bin deskriptoor digunakann f untuk proses p clusteering dengann sebagai fitur menggunaakan K-Mean ns. Hasil clusstering setiapp ruang waarna ini men njadi dasar untuk u prosess selanjutnyya. Skema penghapusan tekstur dapatt dilihat padda Gambar 1.. Proses penghapussan tekstur yang skemaa kerjanya dapat dilihatt pada Gambar 1, diawalii dengan menghitung m bin n deskriptor dan d clusteringg K-Means.. Setelah itu melakukan subdivisi s dann menggantti nilai pikseel dengan raata-rata nilaii piksel clusternya. Terakhir dilakukann perhitungan rata-rata nilai piksel antar ruangg warna.
2.1.1
G Gambar 1 Sk kema Penghaapusan Teksttur
M Menghitung Bin Deskriptor
2.1.22
Bin deskriptor dibutuhkan d pada prosess clusteringg K-Means sebagai fitur f vektor. Perhitunggannya yaitu: untuk setiap piksel x e Nx dengan niilai warna Rx, Gx, Bx dihituung
.
. 256
.
. 256
. 25 56
Clustering K-Means mengelompookkan C pikseel ke dalam cluster-clusteer sehingga piksel p dalam m cluster yang y sama memiliki tiingkat kesaamaan yang tinggi tetapi berbeda terhhadap pikseel pada clusster lain, deengan sebeluumnya menentukan sejum mlah K clustter terlebih daahulu. Bin deskriptor yang y digunaakan sebagai fitur
(1)
2
Clusteriing K-Mean ns
vektor pada aplikasi dihitung menggunakan persamaan jarak euclidean d X ,X
∑ X
2.1.3
X,
X,
2.1.5
Rata-rata nilai piksel antar ruang warna adalah melakukan perhitungan rata-rata nilai piksel antar ruang warna. Hasil dari nilai piksel diganti dengan ratarata cluster pada aplikasi, adalah sejumlah 10 ruang warna. Setiap ruang warna memiliki ukuran dan dimensi yang sama. Perhitungan rata-rata nilai piksel dilakukan antar ruang warna dengan dimensinya yang sama. Nilai piksel pada dimensi pertama dirata-rata dengan nilai piksel pada dimensi pertama antar ruang warna yang berbeda, begitu juga dengan dimensi kedua dan ketiga. Hasil dari langkah ini adalah citra hasil penghapusan tekstur.
(2)
X
Melakukan Subdivisi
Subdivisi adalah prosedur splitting dengan membagi semua region yang memiliki ukuran piksel lebih dari bilangan tertentu (W0) menjadi potongan terpisah (region baru) dengan batasan jumlah W0 piksel. Pada aplikasi, prosedur ini dibantu dengan menggunakan region growing dan pola tertentu yang acak yakni 1. 2. 3. 4.
2.2 K-Means dengan Batasan Ruang
Pola 1: (r-1,c), (r+1,c), (r,c-1), (r,c+1) Pola 2: (r,c-1), (r,c+1), (r-1,c), (r+1,c) Pola 3: (r-1,c), (r,c-1), (r+1,c), (r,c+1) Pola 4: (r,c-1), (r-1,c), (r,c+1), (r+1,c)
Segmentasi K-Means dengan batasan ruang dilakukan setelah proses penghapusan tekstur selesai. K-Means dengan batasan ruang menambahkan hubungan ruang pada proses segmentasi K-Means. Tujuannya untuk membantu proses pelabelan pada iterasi K-Means sehingga berhasil dalam menemukan solusi optimal yakni peta segmentasi yang akurat. Proses segmentasi K-Means dengan batasan ruang, dapat dilihat skemanya pada Gambar 2, terdiri dari beberapa tahapan. Pada awalnya melakukan ekstraksi fitur dari citra hasil penghapusan tekstur dan menghitung edge map dari citra setiap ruang warna. Setelah itu dilakukan perhitungan untuk mendapatkan edge map yang homogen dengan berdasarkan pada nilai threshold tertentu. Setelah proses ektraksi fitur dan edge map homogen selesai, dilakukan proses segmentasi K-Means dengan batasan ruang. Terakhir dilakukan proses region fusi. Region fusi bertujuan untuk menggabungkan region yang kecil dengan region tetangganya.
Dimana r,c adalah seed yang menjadi indek piksel awal pada region growing.
2.1.4
Nilai Piksel diganti dengan Nilai Rata-rata Cluster
Nilai piksel diganti dengan nilai rata-rata cluster adalah mengganti nilai piksel dengan rata-rata nilai piksel pada cluster tersebut. Setiap piksel memiliki keanggotaan cluster mana piksel tersebut berada. Pada setiap cluster dilakukan perhitungan rata-rata nilai piksel pada setiap anggota cluster, kemudian hasilnya menggantikan nilai piksel setiap anggota cluster tersebut. Langkah ini dilakukan pada setiap ruang warna dengan dimensi masing-masing ruang warna adalah memiliki 3 dimensi
.
3
Rata-rata Nilai Piksel antar Ruang Warna
2.2.22
Edge Map Homogeen
P Pada edge map m diidentiffikasi sekum mpulan connnected piksel yang edge potential dibbawah thresshold. Hasil iddentifikasi ini adalah Edgee Map yangg homogen daalam konteks tekstural. D Dapat dihitunng dengan nilai piksel makksimal dikali threshold kemudian k dibbandingkan deengan m nilaii piksel edge map. piksel yang edge potensiialnya S Sekumpulan dibaw wah threshoold direpreseentasikan deengan regioon warna. Region warrna menunjuukkan hom mogen dalam konteks k teksttural. Region yang putihh berkorespoondensi terhhadap sekum mpulan pikseel yang edge potensialnyaa di atas thresshold. Regiion yang puutih menunjuukkan inhom mogen dalam m konteks tekkstural
2.2.33
Ekstraksi fituur bertujuan untuk E u mendappatkan fitur vektor padda gambar hasil h penghappusan teksttur, yang dibbutuhkan padda segmentaasi KMeaans dengan baatasan ruang. F Fitur deskripptor vektor didapat deengan mem makai semua nilai warna dari setiap ruang warnna. Hasilnyaa pada ekkstraksi fituur ini didappatkan [n1 x n1 x 3 x 10] dimensi d fitur vektor v denggan n1 x n1 adalah banyaaknya piksel pada overrlaping windoow
Gamb bar 2 Skema Segmentasi K-Means dengan Ba atasan Ruang
2.2.1
Ekstrak ksi Fitur
M Menghitung Edge Map
Mengghitung edgee map berttujuan untukk mendapattkan edge map m dari suattu citra yangg memiliki ruang warn na berbeda-bbeda. Untukk p dilakukan dengan d rumuss menghitunng edge map berikut (3) , + , , , , ,
2.2.44
Dimana h : B Bin deskripto or : array berttipe float darii Nb (h[0], h[1], … , h[Nb – 1]) D : jarak L1 norm n antar vektor binn d deskriptor yang dihitung pada p N 0 x N0 o overlapping window w
Segmenttasi K-M Means Batasan n Ruang
Segmentasi K-Means S K denngan batasan ruang menambahkan hubungan h pem mbandingan edge map pada prosess iterasi K-M Means. Fitur yang diguunakan adalahh fitur deskripptor hasil eksstraksi fitur pada citra haasil penghapuusan tekstur. B Berikut adaalah langkaah-langkah yang dilakkukan untukk melakukann segmentassi KMeaans dengan baatasan ruang 1. Secara acak pilih K1 inisialisasi pusat
Kemudiann hasil dari edge map pada p masing-ruang masing warna w diratta-rata dann dinormaliisasi (0-1).
cluster
4
dengan
,…,
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2. Pada langkah ke k tetapkan sampel xm ke dalam cluster dengan pusat terdekat , yakni ke cluster i jika
,∀
3. a. Untuk setiap region Ri dari edge map b. Cari cluster mayor dari sampel xm e Ri , yakni cluster i jika: ∑
arg max ∑
∈
Ι
Dimana I adalah fungsi indicator menunjukkan cluster ke i dengan sampel ni setelah langkah 2 tentukan cluster baru dengan ratarata sampel dalam cluster 5. Ulangi sampai konvergensi terpenuhi 6. Fusi region yang kecil (yakni sekumpulan connected pixel dari cluster yang ukurannya di bawah 300 piksel)
4.
3. HASIL DAN PEMBAHASAN
Pengujian dilakukan dengan tiga buah skenario. Uji coba pada skenario pertama dilakukan dengan mengubah nilai parameter nilai threshold pada edge map. Uji coba pada skenario kedua dilakukan dengan mengubah nilai jumlah kelas K untuk segmentasi K-Means dengan batasan ruang. Uji coba pada skenario ketiga dilakukan dengan mengubah jumlah size window untuk pengambilan fitur. Detail parameter dapat dilihat pada tabel 2, 3 dan 4
Perangkat lunak Segmentasi Citra berhasil dibangun untuk mengimplementasikan metode Segmentasi Citra Menggunakan Penghapusan Tekstur dan K-Means dengan Batasan Ruang.
3.1 Dataset, Skenario Uji Coba dan Perhitungan Akurasi Dilakukan uji coba terhadap dataset citra tekstur Berkeley sejumlah 30 citra. Data pengujian dapat dilihat pada tabel 1
Tabel 2. Parameter Uji Coba Skenario 1
Tabel 1. Dataset Uji Coba No 1 2
Nama 100075_320.ppm 100080_320.ppm 5
100098_320.ppm 101085_320.ppm 101087_320.ppm 102061_320.ppm 103041_320.ppm 103070_320.ppm 104022_320.ppm 105019_320.ppm 105025_320.ppm 105053_320.ppm 106020_320.ppm 106024_320.ppm 106025_320.ppm 108005_320.ppm 108041_320.ppm 108070_320.ppm 108073_320.ppm 108082_320.ppm 109034_320.ppm 109053_320.ppm 112082_320.ppm 113009_320.ppm 113016_320.ppm 113044_320.ppm 117054_320.ppm 118020_320.ppm 118035_320.ppm 119082_320.ppm
Tabel 6. Hasil Uji Coba Skenario 2
Tabel 3. Parameter Uji Coba Skenario 2
Tabel 7. Hasil Uji Coba Skenario 3 Tabel 4. Parameter Uji Coba Skenario 3 Hasil uji coba pada skenario ke 1 menunjukkan performa terbaik pada percobaan ke dua pada nilai threshold 0.25 dengan nilai akurasi PRI adalah 74.21 %. Kemudian pada skenario ke 2 menunjukkan performa terbaik pada percobaan ke 6 yaitu nilai K = 10 dengan nilai akurasi PRI adalah 73.62 %. Pada skenario ke 3 menunjukkan performa terbaik pada percobaan ke 4 yaitu jumlah size window bernilai 4 dengan nilai akurasi PRI adalah 71.96 %
Evaluasi dilakukan dengan menggunakan perhitungan akurasi Probabilistic Rand Index. Probabilistic Rand Index dihitung dengan menggunakan rumus
(4)
4. KESIMPULAN
Dengan rumus untuk menghitung RI dapat ditulis sebagai berikut
Beberapa kesimpulan yang dapat diambil adalah sebagai berikut: 1. Metode segmentasi citra menggunakan Penghapusan Tekstur dan K-Means dengan Batasan Ruang cukup baik untuk melakukan segmentasi tekstur dari suatu citra. 2. Nilai bin deskriptor dari citra tekstur berwarna dapat digunakan sebagai representasi fitur citra untuk penghapusan tekstur. 3. Nilai edge map yang homogen dari suatu citra dapat digunakan sebagai batasan ruang dengan membantu segmentasi citra pada KMeans. 4. Performa segmentasi citra tekstur ini mampu mencapai 74,21% pada skenario 1 dengan menggunakan nilai subdivision, size window, size fuse, K dan threshold secara berturut-turut adalah 5000, 5, 600, 9, dan 0.2
(5)
3.2 Hasil Uji Coba Hasil uji coba pada 30 gambar masukan pada skenario 1, 2, dan 3 dapat dilihat pada tabel 5, 6, dan 7 dengan nilai akurasi rata untuk masing-masing percobaan Tabel 5. Hasil Uji Coba Skenario 1
6
5. DAFTAR REFERENSI [1] Mignotte, M., 2007. Image denoising by averaging of piecewise constant simulations of image partitions. IEEE Trans. Image Process. 16(2), 523-533 [2] Mignotte, M., 2008. Segmentation by fusion of histogram-based k-means clusters in different color space. IEEE Trans. Image Process. 17(5), 780-787 [3] Mignotte, M., 2010. A de-texturing and spatially constrained K-means approach for image segmentation. Pattern Recognition Letters. 32, 352-367 [4] Gonzalez R.C., Woods R.E, Digital Image Processing, Third Edition, Prentice Hall, 2008 [5] R. Unnikrishnan and M. Hebert. Measures of Similarity. Seventh IEEE Workshop on Applications of Computer Vision, January, 2005, pp. 394-400 [6] Y. B. Chen and Oscal T.-C. Chen, “Semi-automatic image segmentation using dynamic direction prediction”, Dept. of Electrical Engineering, National Chug Cheng University, ChiaYi, Taiwan, R0.C, 2002. [7] K. Karsch, Q. He, Y. Duan, A fast, semi-automatic brain structure segmentation algorithm for magnetic resonance imaging, in: Proc. of IEEE BIBM 2009,November 2009, pp. 297– 302 [8] Y.B. Chen, O.T.-C. Chen, Image segmentation method using thresholds automatically determined from picture contents, EURASIP J. Image Video Process. (2009), Article ID 140492, 15 pp [9] Y.B. Chen, O.T.-C. Chen, Highaccuracy moving object extraction using background subtraction, ICIC Express Lett. 3 (4(A)) (December 2009) 933– 938.
7
