51
JNTETI, Vol. 6, No. 1, Februari 2017
Spatial Fuzzy C-means dan Rapid Region Merging untuk Pemisahan Sel Kanker Payudara Desmin Tuwohingide1, Chastine Fatichah2 Abstract—Segmentation and overlapped cells separation are important phases in microscopic image processing of breast cancer, because the accuracy of overlapped cells separation result determines the accuracy of breast cancer cell calculation. The amount of breast cancer cells is considered by doctor in determining the action towards patients. Two of the most common topics discussed in previous studies are the problem of increasing the accuracy of overlapped cancer cell separation result by calculating the number of cancer cell and oversegmentation problem. Compared to watershed method, clustering method produces higher accuracy in separating overlapped cancer cells. In this paper, a combination of Spatial Fuzzy C-Means (SFCM) and Rapid Region Merging (RRM) method is proposed to separate the overlapped cells and handling the over-segmentation problem. The input image of overlapped cells separation phase is the result of breast cancer cell identification by Gram-Schmidt (GS) method, while the clustered cancer cells are overlapped cancer cells which are detected based on the area of geometric feature. 40 microscopic breast cancer cells image of benign and malignant type is used as the datasets. The average value of Mean Square Error (MSE) for cell identification is 0.07 and the average accuracy of overlapped cells separation using SFCM and RRM is 78.41%. Intisari—Segmentasi dan pemisahan sel bertumpuk merupakan tahapan penting dalam proses pengolahan citra mikroskopis sel kanker payudara, karena akurasi hasil pemisahan sel bertumpuk akan menentukan akurasi perhitungan sel kanker payudara. Hasil perhitungan jumlah sel kanker payudara merupakan salah satu faktor pertimbangan bagi dokter untuk melakukan tindakan terhadap pasien. Masalah peningkatan akurasi hasil pemisahan sel kanker bertumpuk berdasarkan perhitungan jumlah sel kanker dan masalah over-segmentation adalah topik yang paling umum dibahas pada penelitian-penelitian sebelumnya. Metode clustering yang digunakan untuk pemisahan sel kanker darah bertumpuk menghasilkan nilai akurasi yang tinggi dibandingkan metode watershed. Pada makalah ini diusulkan kombinasi metode Spatial Fuzzy C-Means (SFCM) dan Rapid Region Merging (RRM) untuk pemisahan sel bertumpuk dan penanganan masalah over-segmentation. Citra masukan pada tahapan pemisahan sel bertumpuk adalah citra hasil identifikasi sel kanker payudara berdasarkan metode Gram-Schmidt (GS), sedangkan sel kanker yang akan dipisahkan adalah sel kanker 1 Mahasiswa, Jurusan Teknik Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember, Jln Teknik Kimia, Gedung Informatika, Kampus ITS Sukolilo, Kota Surabaya, Jawa Timur 60111 (telp: 031-5939214; fax: 031-5913804; e-mail:
[email protected]) 2, Dosen,, Jurusan Teknik Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember, Jln Teknik Kimia, Gedung Informatika, Kampus ITS Sukolilo, Kota Surabaya, Jawa Timur 60111 (telp: 031-5939214; fax: 031-5913804; e-mail:
[email protected])
Desmin Tuwohingide: Spatial Fuzzy C-Means dan ...
yang dideteksi bertumpuk berdasarkan ciri (feature) geometri area. Data set yang digunakan sebanyak 40 citra mikroskopis sel kanker payudara jenis benign dan malignant. Pada makalah ini dihasilkan nilai rata-rata Mean Square Error (MSE) identifikasi sel sebesar 0,07 dan rata-rata akurasi hasil pemisahan sel bertumpuk menggunakan metode SFCM dan RRM sebesar 78,41%. Kata Kunci— Segmentasi Sel Bertumpuk, Citra Mikroskopis, Sel Kanker Payudara, Spatial Fuzzy C-Means, Rapid Region Merging
I. PENDAHULUAN Pada umumnya, kanker payudara didiagnosis melalui pemeriksaan rutin atau ketika pasien menyadari gejala-gejala tertentu. Tetapi pemeriksaan fisik saja tidak cukup untuk mengonfirmasi diagnosis kanker payudara, sehingga dilakukan perangkaian prosedur pemeriksaan seperti mamografi, biopsi, dan lain sebagainya untuk memperoleh informasi terkait diagnosis dan kebutuhan terapi pasien. Salah satu data yang informasinya digunakan untuk diagnosis penyakit kanker payudara adalah data sel kanker berupa citra mikroskopis yang diambil dari tubuh pasien menggunakan kamera khusus. Citra mikroskopis tersebut yang kemudian akan dianalisis oleh tim medis untuk mengonfirmasi kesehatan pasien. Penerapan teknik pengolahan citra untuk menganalisis citra mikroskopis sel kanker payudara dilakukan untuk mempermudah diagnosis penyakit kanker payudara. Pada penerapannya, terdapat berbagai permasalahan dalam implementasi pengolahan citra, antara lain teknik segmentasi tradisional tidak bisa secara maksimal melakukan segmentasi dan pemisahan sel bertumpuk pada citra mikroskopis yang memiliki beragam karakteristik dari segi warna, bentuk, ukuran dan tekstur. Keberagaman ini yang menjadi tantangan dalam pengolahan citra mikroskopis, sehingga banyak dilakukan penelitian dan pengembangan metode terkait pengolahan citra mikroskopis sel kanker payudara. Masalah identifikasi sel kanker payudara pada citra mikroskopis sel kanker payudara telah dipaparkan pada beberapa penelitian [1], [2]. Permasalahan lainnya adalah proses pemisahan sel bertumpuk pada citra mikroskopis sel kanker payudara. Proses pemisahan sel bertumpuk merupakan salah satu tahapan terpenting dalam proses segmentasi citra mikroskopis sel kanker payudara dikarenakan keakuratan hasil pemisahan sel bertumpuk akan menentukan akurasi perhitungan jumlah sel kanker payudara. Hasil perhitungan sel kanker payudara merupakan salah satu faktor pertimbangan bagi tim medis untuk melakukan tindakan terhadap pasien. Beberapa penelitian telah melakukan segmentasi dan pemisahan sel bertumpuk pada citra mikroskopis. Sebuah penelitian menerapkan deteksi sel kanker payudara bertumpuk
ISSN 2301 - 4156
52 menggunakan deteksi concave point [3]. Karena bentuk sel kanker payudara yang beragam, dilakukan deteksi titik yang memiliki concavity yang tinggi pada daerah boundaries. Titiktitik concavity ditentukan dengan teknik pendeteksian sudut berdasarkan informasi global dan local curvature dan metode Watershed untuk pemisahan sel bertumpuk. Hasil nilai akurasi yang diperoleh pada penelitian tersebut adalah 89,20% untuk data set 1 dan 92,70% untuk data set 2. Secara berkelanjutan, beberapa penelitian yang menerapkan Watershed untuk pemisahan sel bertumpuk berdasarkan fuzzy active contour model dan deteksi concave point menggunakan konstruksi concave vertex graph dan pemilihan jalur garis terpendek untuk inisialisasi garis pemisah, dan menghasilkan nilai akurasi sebesar 96,23% [2], [4], [5]. Dalam sebuah penelitian lain, kombinasi metode Region-Based Active Contour dan Bayesian untuk pemisahan sel bertumpuk menghasilkan nilai rata-rata akurasi sebesar 61,30%, sementara kombinasi metode Region-Based Active Contour dan Watershed menghasilkan rata-rata nilai akurasi sebesar 65% [6]. Selanjutnya, telah dilakukan juga penelitian deteksi dan pemisahan sel bertumpuk pada citra mikroskopis sel darah menggunakan informasi ciri (feature) geometri dan analisis KMeans Clustering untuk pemisahan sel kanker bertumpuk [7]. Hasilnya menunjukkan bahwa metode ini memiliki rata-rata akurasi yang lebih tinggi, yaitu 96,46%, dan nilai galat (error) yang lebih rendah dibandingkan dengan metode Classical Watershed yang memperoleh rata-rata nilai akurasi sebesar 79,87% dan metode Condition Erosion Watershed yang menghasilkan rata-rata nilai akurasi sebesar 87,22%. Berdasarkan penelitian-penelitian tersebut, ada beberapa hal yang sangat untuk dilakukan dan dikembangkan agar dihasilkan segmentasi dan pemisahan sel kanker bertumpuk yang nilai akurasinya tinggi. Identifikasi sel kanker payudara menggunakan metode Gram-Schmidt (GS) merupakan salah satu metode yang memberikan nilai Mean Square Error (MSE) yang rendah [1]. Deteksi sel kanker payudara perlu dilakukan untuk mengurangi kemungkinan over-segmentation dan under-segmentation berdasarkan informasi ciri (feature) geometri area dengan memberikan asumsi luasan sel kanker tunggal dan luasan sel kanker bertumpuk [8]. Untuk pemisahan sel bertumpuk, metode clustering menghasilkan pemisahan sel darah bertumpuk yang baik dan memperoleh nilai akurasi yang tinggi dibandingkan dengan metode classical watershed dan metode condition erosion watershed, sehingga dapat dikembangkan lagi untuk menghasilkan nilai akurasi yang semakin tinggi [7]. Pada penelitian lain, dipaparkan metode clustering Spatial Fuzzy C-Means (SFCM) yang merupakan metode clustering berdasarkan informasi spasial dan probabilitas ketetanggaan, serta merupakan pengembangan dari metode Fuzzy C-Means clustering, karena informasi spasial dan probabilitas ketetanggaan memiliki korelasi yang tinggi dan sangat penting, sehingga algoritme ini tidak hanya tegar (robust) terhadap derau tapi juga mengurangi kesalahan pengelompokan [9], [10]. Selain beberapa masalah tersebut, over-segmentation menjadi salah satu masalah utama yang harus ditangani dalam
ISSN 2301 – 4156
JNTETI, Vol. 6, No. 1, Februari 2017 proses pemisahan sel bertumpuk. Metode Region Merging adalah metode yang diimplementasikan untuk mengurangi masalah over-segmentation. Salah satunya adalah Rapid Region Merging (RRM), yang merupakan metode penggabungan daerah berdasarkan kemiripan region, yang mampu meningkatkan nilai akurasi segmentasi karena mampu mengatasi masalah over-segmentation [11]. Berdasarkan uraian di atas, pada makalah ini diusulkan metode untuk pemisahan sel kanker bertumpuk pada citra mikroskopis sel kanker payudara menggunakan SFCM dan RRM. Tahapan pertama adalah melakukan segmentasi sel kanker pada citra mikroskopis sel kanker payudara berdasarkan identifikasi sel menggunakan metode GS, kemudian dilakukan deteksi sel kanker bertumpuk dan inisialisasi jumlah sel bertumpuk berdasarkan informasi ciri geometri area. Selanjutnya adalah melakukan pemisahan sel kanker bertumpuk menggunakan clustering SFCM, sementara metode RRM mengatasi masalah over-segmentation. II. USULAN METODE A. Data Data set yang digunakan adalah data citra mikroskopis sel kanker payudara, sebanyak 40 citra, yang terdiri atas data set tipe malignant dan benign. Data set dapat diunduh di www.bioimage.ucsb.edu. Berdasarkan data set groundtruth yang diperoleh, diperlukan proses cropping citra secara manual untuk memperoleh bagian citra yang sesuai dengan groundtruth menggunakan tools Adobe Photoshop CS3, seperti pada Gbr. 1.
(a)
(b)
(c)
(d)
(f)
(g)
Gbr. 1 Citra mikroskopis sel kanker payudara (a)(b)(c) Citra data benign (d)(e)(f) Citra data malignant.
B. Identifikasi Sel Kanker dan Pemisahan Sel Bertumpuk Secara garis besar, penelitian ini terbagi ke dalam dua tahapan penting. Tahapan pertama adalah identifikasi sel kanker payudara atau tahapan segmentasi awal dan tahapan kedua adalah pemisahan sel kanker bertumpuk, sesuai yang disajikan pada Gbr. 2. Tahapan pertama adalah tahapan identifikasi sel kanker payudara berdasarkan metode GS [1]. Pada metode ini, dilakukan penentuan tiga vektor warna. Vektor warna pertama
Desmin Tuwohingide: Spatial Fuzzy C-Means dan ...
53
JNTETI, Vol. 6, No. 1, Februari 2017 adalah vektor warna yang akan diperkuat atau diinisialisasi sebagai sel kanker, sedangkan vektor warna kedua dan ketiga adalah vektor warna yang dianggap sebagai derau dan background. Penentuan vektor warna dilakukan dengan memilih tiga citra data set secara acak dan mengambil nilai tengahnya sebagai vektor warna. Kemudian dilakukan thresholding untuk memperoleh citra biner. Nilai thresholding yang digunakan adalah 0,03. Nilai ini diperoleh berdasarkan uji coba terhadap 20 data set yang dipilih secara acak. Proses terakhir pada tahapan identifikasi sel adalah penghapusan derau menggunakan operasi morfologi. Tahapan kedua adalah pemisahan sel kanker bertumpuk berdasarkan metode SFCM dan RRM. Tahapan ini terdiri atas beberapa proses, yaitu deteksi sel kanker bertumpuk, pemisahan sel kanker bertumpuk menggunakan SFCM, dan penggabungan daerah yang mengalami over-segmentation berdasarkan RRM. Data masukan yang digunakan pada tahapan ini adalah citra hasil segmentasi sel kanker payudara berdasarkan metode GS, yang diperoleh pada tahapan pertama. Deteksi sel bertumpuk dilakukan berdasarkan informasi ciri geometri area dengan mengasumsikan setiap sel yang memiliki nilai ciri geometri luasan di atas nilai threshold adalah bertumpuk. Nilai threshold ditentukan berdasarkan uji coba terhadap 20 citra yang dipilih secara acak. Nilai threshold dengan hasil terbaik adalah 340. Mulai
Citra Mikroskopis Sel Kanker Payudara
𝑝
𝑞
Deteksi Sel Bertumpuk (Fitur Geometri)
Ya
Pemisahan sel bertumpuk (SFCM dan rapid region merging)
Tidak Citra Hasil Segmentasi Sel Bertumpuk
Selesai
Gbr. 2 Diagram alir tahapan yang dilakukan.
1) Spatial Fuzzy C-Means: Salah satu karakteristik penting sebuah citra adalah ketetanggaan piksel yang berkorelasi tinggi. Dengan kata lain, ketetanggaan piksel memiliki
Desmin Tuwohingide: Spatial Fuzzy C-Means dan ...
𝑝
𝑞
∗ = 𝑢𝑖𝑗 ℎ𝑖𝑗 �∑𝑐𝑘=1 𝑢𝑘𝑗 ℎ𝑘𝑗 𝑢𝑖𝑗
∗ ∑𝑘𝑗=1 𝑢𝑖𝑗 =1
(1)
(2)
Berdasarkan (2) dengan parameter 𝑐𝑗 adalah centroid cluster ke- 𝑗, 𝐷() adalah jarak data dan centroid, sedangkan 𝑤 adalah parameter bobot pangkat (weighting exponent). 𝑤 tidak memiliki nilai ketetapan, biasanya nilai 𝑤 > 1 dan umumnya diberi nilai 2 [9]. −2⁄𝑤−1
�∑𝑘𝑙=1 𝐷(𝑥𝑖 , 𝑐𝑖 )−2⁄𝑤−1
(3)
ℎ𝑖𝑗 = 1 + �∑𝑡∈Ωj 𝑢𝑖𝑡 𝑝𝑖𝑗 �∑𝑐𝑘=1 ∑𝑡𝜖Ω𝑗 𝑢𝑘𝑡 𝑝𝑘𝑗 �
(4)
𝑢𝑖𝑗 = 𝐷�𝑥𝑖 , 𝑐𝑗 �
Segmentasi Sel Kanker (Gram Schmidt)
Bertumpuk
kemiripan nilai ciri, dan kemungkinan berada dalam cluster yang sama sangat besar. Hubungan spasial adalah hal penting dalam clustering, tetapi hal ini tidak digunakan pada Fuzzy CMeans (FCM) standar, sehingga FCM standar sangat rentan terhadap derau. Untuk mengatasi masalah tersebut, dapat dimanfaatkan informasi spasial yang dibentuk menggunakan distribusi statistika dari ketetanggaan piksel dan prior probability untuk memperoleh sebuah fungsi keanggotaan (membership function) baru yang digunakan pada SFCM [9]. Metode ini tidak hanya efektif menghapus derau tetapi juga mengurangi kesalahan pengelompokan piksel. Diasumsikan sejumlah data dalam himpunan data 𝑋 yang berisi sejumlah 𝑛 data yang dinotasikan 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 }, dengan setiap data mempunyai ciri 𝑟 dimensi 𝑥𝑖1 , 𝑥𝑖2 , … , 𝑥𝑖𝑟 yang dinotasikan 𝑥𝑖 = {𝑥𝑖1 , 𝑥𝑖2 , … , 𝑥𝑖𝑟 }. Ada sejumlah cluster 𝐶 dengan titik pusat cluster 𝑐1 , 𝑐2 , … , 𝑐𝑘 , dengan k adalah jumlah cluster. Setiap data mempunyai derajat keanggotaan ∗ , seperti pada setiap cluster, yang dinyatakan dengan 𝑢𝑖𝑗 ditunjukkan pada (1), dengan 𝑖 menyatakan data 𝑥𝑖 dan 𝑗 menyatakan 𝑐𝑗 . Jumlah nilai derajat keanggotaan setiap data 𝑥𝑖 selalu sama dengan 1, seperti pada (5) [9].
Perhitungan spatial function sesuai (3) dengan 𝑥𝑗 merepresentasikan nilai ciri, Ω merepresentasikan sebuah jendela persegi yang titik tengahnya berada pada piksel 𝑥𝑗 . ℎ𝑖𝑗 merepresentasikan probabiltas piksel 𝑥𝑗 menjadi anggota sebuah cluster. Pada spatial function, 𝑐 merupakan jumlah cluster yang diinginkan, 𝑃𝑖𝑗 adalah faktor kontribusi dari tetangga 𝑥𝑡 , dan bobot 𝑢𝑖𝑡 adalah membership pattern 𝑥𝑡 dan prior probability. Secara umum, prior probability dari 𝑝𝑖𝑗 merupakan hasil perbandingan dari 𝑁𝑗𝑖 jumlah ketetanggaan piksel yang menjadi anggota cluster dan 𝑁𝑗 jumlah ketetanggaan piksel pada 𝑥𝑗 . [9]. 𝑝𝑖𝑗 = 𝑁𝑗𝑖 �𝑁𝑗
(5)
Untuk menghitung titik pusat cluster 𝑐𝑙 pada fitur 𝑗 , digunakan (6), dengan parameter 𝑁 adalah jumlah data, 𝑤 adalah bobot pangkat, dan 𝑢𝑖𝑗 adalah derajat keanggotaan data 𝑥𝑖 ke cluster 𝑐𝑙 . Sementara, fungsi objektif dihitung sesuai (9) [9]. Penentuan jumlah cluster dilakukan berdasarkan perhitungan sesuai dengan (7), dengan 𝑎 adalah ciri geometri area bertumpuk, 𝑏 adalah nilai threshold bertumpuk, dan 𝑐 adalah nilai threshold sebesar 1,5. Nilai 𝑐 diperoleh
ISSN 2301 - 4156
54
JNTETI, Vol. 6, No. 1, Februari 2017
berdasarkan uji coba terhadap data set dari rentang nilai 1,1 sampai 2. Nilai objektif dihitung berdasarkan (8). 𝑁 𝑤 𝑤 𝑐𝑙𝑗 = ∑𝑁 𝑖=1(𝑢𝑖𝑙 ) 𝑥𝑖𝑗 ⁄∑𝑖=1(𝑢𝑖𝑙 )
𝑘 = 𝑎⁄(𝑏⁄𝑐 )
𝑤
𝑘 2 𝐽 = ∑𝑁 𝑖=1 ∑𝑙=1�𝑢𝑖𝑗 � 𝐷(𝑥𝑖 , 𝑐𝑙 )
(6) (7) (8)
Tahapan metode SFCM yang dilakukan dapat disimpulkan sebagai berikut. 1. Inisialisasi jumlah cluster (𝑘 ≥ 2) berdasarkan asumsi banyaknya sel tunggal yang menumpuk pada daerah yang dianggap sel bertumpuk, mengikuti perhitungan pada (7). 2. Penentuan bobot pangkat (𝑤 ≥ 1) , penentuan jumlah iterasi maksimal, penentuan nilai ambang batas perubahan fungsi objektif. 3. Memberikan nilai awal pada matriks fuzzy pseudopartition, dengan syarat seperti pada (2) dan menghitung nilai centroid awal menggunakan (6). 4. Menghitung spatial function dan prior probability ketetanggaan menggunakan (4) dan (5). 5. Menghitung kembali keanggotaan matriks fuzzy pseudopartition menggunakan (1) dan memperbarui nilai titik pusat cluster. 6. Memperbarui perhitungan. Jika memenuhi syarat maksimum iterasi, atau syarat perubahan nilai objektif di bawah nilai ambang batas, maka berhenti. Jika tidak, kembali ke tahapan ke-2. 2) Rapid Region Merging (RRM): Metode RRM merupakan metode penggabungan sebuah daerah yang memiliki maximum similarity dengan daerah tetangganya atau daerah yang memiliki region adjacent dengan dirinya. Tahapan penggabungan daerah menggunakan algoritme RRM dimulai dengan menentukan terlebih dahulu daerah yang pseudo-blob dan daerah yang real-blob. Pada makalah ini, daerah pseudo-blob ditentukan berdasarkan informasi ciri geometri area. Selanjutnya, daerah yang dianggap sebagai daerah pseudo-blob atau daerah yang terbentuk akibat oversegmentation akan diproses dengan menghitung nilai kemiripannya dengan daerah real-blob yang merupakan tetangganya atau yang memiliki region adjacent dengan pseudo-blob. Penggabungan daerah pseudo-blob dan real-blob dilakukan berdasarkan perhitungan nilai maximum similarity. Daerah tetangga yang memiliki nilai maximum similarity akan ditandai sebagai winner block P. Winner block P ditandai berdasarkan (9) dan parameter yang digunakan untuk menghitung kemiripan antara pseudo-blob dan real-blob adalah gray level contrasts 𝐺(𝑎, 𝑏), kemiripan ridge 𝐸(𝑎, 𝑏), dan region adjacency𝐴(𝑎, 𝑏) [11]. 𝐵𝑙𝑜𝑐𝑘 𝑃 = 𝑀𝑎𝑥(𝑆𝑖𝑚(𝑎, 𝑏), 𝑆𝑖𝑚(𝑎, 𝑐), 𝑆𝑖𝑚 (𝑎, 𝑑)
(9)
Penggabungan daerah menggunakan metode RRM dilakukan dengan cara menghitung kemiripan daerah yang dianggap sebagai daerah over-segmentation atau pseudo-blob dengan sel tetangganya yang dianggap real-blob. Untuk menghitung kemiripan antar cluster, parameter yang digunakan adalah gray level contrasts 𝐺(𝑎, 𝑏) , kemiripan
ISSN 2301 – 4156
ridge 𝐸(𝑎, 𝑏), dan region adjacency 𝐴(𝑎, 𝑏) mengikuti (10). Gray level contrasts 𝐺(𝑎, 𝑏) dihitung berdasarkan jumlah piksel di region a, 𝑅𝑎 , dan region b, 𝑅𝑏 , serta rata-rata keabuan pada region a, 𝜇𝑎 , dan region b, 𝜇𝑏 , mengikuti (11). 𝑆𝑖𝑚(𝑎, 𝑏) = 1⁄𝐺(𝑎, 𝑏). 𝐸(𝑎, 𝑏). 𝐴(𝑎, 𝑏)
𝐺(𝑎, 𝑏) = (𝑅𝑎 − 𝑅𝑏 ⁄𝑅𝑎 + 𝑅𝑏 ) (𝜇𝑎 − 𝜇𝑏
(10)
)2
𝐸(𝑎, 𝑏) = (|𝜋𝑎 − 𝜋𝑏 | + 1)⁄(𝜎𝑎 + 𝜎𝑏 + 1)
(11) (12)
Kemiripan ridge 𝐸(𝑎, 𝑏) dihitung mengikuti (12), dengan 𝜎 adalah rata-rata keabuan piksel di daerah boundary pada kedua sisi ridge dan 𝜋 adalah variasi keabuan piksel di daerah boundary pada kedua sisi. Jika ridge adalah boundary, gray level piksel pada kedua sisi akan menunjukkan perubahan yang signifikan, |𝜋𝑎 − 𝜋𝑏 | akan menjadi lebih besar, sedangkan 𝜎𝑎 dan 𝜎𝑏 akan menjadi lebih kecil. Aturan region adjacency 𝐴(𝑎, 𝑏) mengikuti (13) [11]. 1 𝑎 𝑑𝑎𝑛 𝑏 𝑎𝑑𝑗𝑎𝑐𝑒𝑛𝑡 𝐴(𝑎, 𝑏) = � (13) ∞ 𝑎 𝑑𝑎𝑛 𝑏 𝑡𝑖𝑑𝑎𝑘 𝑎𝑑𝑗𝑎𝑐𝑒𝑛𝑡 C. Skenario Uji Coba dan Metode Evaluasi Pengukuran unjuk kerja metode yang diusulkan perlu dilakukan untuk mengetahui tingkat keberhasilan. Dilakukan dua skenario uji coba untuk mengukur keberhasilan metode usulan yang diterapkan pada tahapan identifikasi sel kanker dan tahapan pemisahan sel kanker bertumpuk. Skenario pertama adalah membandingkan hasil segmentasi awal atau hasil identifikasi sel pada citra mikroskopis sel kanker payudara menggunakan metode yang diusulkan dengan metode Region Based Active Contour (RBAC) [6]. Skenario kedua adalah membandingkan hasil pemisahan sel bertumpuk berdasarkan perhitungan jumlah sel menggunakan metode yang diusulkan dan dengan menggunakan metode KMeans. Evaluasi skenario uji coba pertama dilakukan dengan menghitung nilai MSE atau rata-rata galat untuk mengukur keberhasilan metode yang diusulkan dan metode pembanding dalam melakukan identifikasi sel berdasarkan citra groundtruth. Nilai MSE merupakan hasil perbandingkan nilai selisih piksel-piksel pada citra asal 𝑓(𝑥, 𝑦) dengan pikselpiksel pada citra hasil 𝑔(𝑥, 𝑦)di posisi piksel yang sama, yang secara matematis dinyatakan dalam (14). Semakin kecil nilai MSE yang diperoleh, maka semakin tinggi akurasi identifikasi sel yang diperoleh. 𝑀𝑆𝐸 =
1
𝑀𝑁
𝑁 2 ∑𝑀 𝑥=1 ∑𝑦=1[𝑓(𝑥, 𝑦) − 𝑔(𝑥, 𝑦)]
TABEL I CONFUSION MATRIX
Confusion Matrix Actual
(14)
Positive Negative
Predicted Positive Negative TP TN FP FN
Evaluasi skenario uji coba kedua dilakukan dengan menghitung nilai akurasi untuk mengukur keberhasilan metode yang diusulkan dan metode pembanding. Sel kanker yang diidentifikasikan benar adalah sel kanker yang terpisah sesuai dengan jumlah sel bertumpuk pada citra asli dengan
Desmin Tuwohingide: Spatial Fuzzy C-Means dan ...
55
JNTETI, Vol. 6, No. 1, Februari 2017 memperhatikan ketepatan garis pemotong pada kondisi tertentu. Selain itu, jumlah sel yang mengalami oversegmentation dihitung berdasarkan jumlah cluster, sedangkan under-segmentation dihitung berdasarkan jumlah cluster yang kurang dari jumlah sel bertumpuk yang sebenarnya. Nilai akurasi yang dihasilkan oleh metode yang diusulkan akan dibandingkan dengan nilai akurasi metode K-Means Clustering [7]. Nilai akurasi dihitung berdasarkan perbandingan jumlah sel benar dan jumlah sel pada citra asli sesuai dengan (15) berdasarkan confusion matrix pada Tabel I, dengan true positive (𝑇𝑃) adalah jumlah sel yang diidentifikasi dengan benar dan true negative (𝑇𝑁) adalah jumlah sel benar yang tidak teridentifikasi. 𝐴𝑘𝑢𝑟𝑎𝑠𝑖 = 𝑇𝑃 ⁄(𝑇𝑃 + 𝑇𝑁) × 100
(15)
hasil tersebut dapat dihitung jumlah sel yang benar, jumlah sel over-segmentation, dan jumlah sel under-segmentation seperti yang ditampilkan pada Gbr. 4. Sel benar dihitung berdasarkan jumlah cluster dan hasil clustering yang sesuai dengan jumlah sel pada citra asli seperti yang ditampilkan pada Gbr.4(a). Sel over-segmentation berarti jumlah cluster lebih banyak dari jumlah sel pada citra asli, seperti yang ditampilkan pada Gbr. 4(b), ditandai dalam sel yang diberi label 58 dan 60, dan pada Gbr. 4(d) ditandai dalam sel yang diberi label 80 dan 78. Sel under-segmentation dihitung berdasarkan jumlah cluster yang lebih sedikit dari jumlah sel pada citra asli, seperti pada Gbr. 4(c) di sel yang dilabeli angka 76. TABEL II HASIL PERHITUNGAN NILAI MSE PADA UJI COBA SKENARIO 1
III. HASIL DAN ANALISIS
Citra Ke
A. Hasil Uji Coba Skenario 1 Pada Tabel II, ditunjukkan hasil identifikasi sel menggunakan metode GS dan metode RBAC. Uji coba skenario pertama dilakukan dengan membandingkan hasil identifikasi sel kanker dari metode yang diusulkan dengan metode RBAC dalam melakukan segmentasi awal atau identifikasi kanker berdasarkan perhitungan nilai MSE. Berdasarkan perhitungan nilai MSE yang ditampilkan pada Tabel II, dengan metode GS menghasilkan nilai MSE yang berada dalam rentang nilai 0,0398 sampai 0,1220 dan nilai rata-rata kesalahan segmentasi sebesar 0,0745, nilai MSE terendah dihasilkan oleh citra ke-11 dan nilai MSE tertinggi dihasilkan oleh citra ke-39. Identifikasi menggunakan metode RBAC menghasilkan nilai MSE dalam rentang nilai 0,0728 sampai 0,9578, dengan nilai MSE terendah dihasilkan oleh citra ke-12 dan nilai MSE tertinggi berada pada citra ke-10, dengan rata-rata kesalahan segmentasi sebesar 0,6505.
1 2 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 31 32 33 34 35 36 37 38 39 40 Rata-rata
B. Hasil Uji Coba Skenario 2 Uji coba skenario kedua dilakukan untuk mengetahui perbandingan nilai akurasi tahapan pemisahan sel menggunakan metode usulan dan metode K-Means berdasarkan perhitungan jumlah sel yang dipisahkan secara benar. Sel benar dihitung berdasarkan jumlah cluster yang sama dengan jumlah sel pada citra asli dan dengan memperhatikan garis pemisah. Sel over-segmentation dihitung berdasarkan sel yang memiliki jumlah cluster lebih dari jumlah sel pada citra asli. Sel under-segmentation adalah sel yang memiliki jumlah cluster kurang dari jumlah sel pada citra asli. Nilai akurasi diperoleh berdasarkan perbandingan jumlah sel yang benar dengan jumlah sel kanker pada citra asli. Berdasarkan hasil pemisahan sel bertumpuk pada 40 citra mikroskopis sebagai data uji yang disajikan pada Gbr. 3, dapat dilihat perbedaan hasil pemisahan sel kanker bertumpuk menggunakan metode usulan dan metode K-Means. Pemisahan sel kanker bertumpuk menggunakan metode KMeans menghasilkan lebih banyak sel yang over-segmentation dibandingkan dengan metode yang diusulkan. Berdasarkan
Desmin Tuwohingide: Spatial Fuzzy C-Means dan ...
Nilai MSE Gram-Schmidt 0,0622 0,0719 0,0822 0,1054 0,0989 0,0850 0,0458 0,0990 0,0552 0,0461 0,0398 0,0541 0,0844 0,0827 0,0604 0,0854 0,0879 0,0418 0,1035 0,0859 0,0851 0,0552 0,0899 0,0642 0,0794 0,0589 0,0585 0,0960 0,0409 0,0662 0,0782 0,0785 0,1080 0,0368 0,0785 0,0647 0,0958 0,0770 0,1225 0,0335 0,0736
RBAC 0,8855 0,0816 0,8646 0,9002 0,9158 0,9119 0,0610 0,9045 0,9346 0,9578 0,9177 0,0728 0,1384 0,1706 0,1383 0,1552 0,8384 0,9061 0,8658 0,7977 0,8573 0,1959 0,1626 0,2253 0,8363 0,8411 0,8836 0,7324 0,7505 0,8508 0,9105 0,0991 0,8859 0,8955 0,9123 0,8650 0,1352 0,8879 0,8311 0,8428 0,6505
ISSN 2301 - 4156
56
JNTETI, Vol. 6, No. 1, Februari 2017 adalah sebanyak 1333 sel benar, 382 sel over-segmentation, dan 35 sel under-segmentation. Jumlah sel yang diperoleh dengan metode usulan adalah sebanyak 1486 sel benar, 197 sel over-segmentation, dan 72 sel under-segmentation. TABEL III PERHITUNGAN JUMLAH SEL BERDASARKAN CITRA HASIL PEMISAHAN SEL BERTUMPUK MENGGUNAKAN METODE USULAN PADA UJI COBA SKENARIO 2
(a)
(b)
(c)
Gbr. 3 Hasil pemisahan sel bertumpuk (a) Citra groundtruth (b) Pemisahan sel bertumpuk menggunakan K-Means(c) Pemisahan sel bertumpuk menggunakan kombinasi SFCM dan RRM.
(a)
(b)
(c)
(d)
Gbr. 4 (a) Sel Benar, (b) Sel Over-segmentation, (c) Sel Under-segmentation, (d) Sel Over-segmentation.
Dari hasil perhitungan sel secara manual berdasarkan citra hasil pemisahan sel bertumpuk pada 40 citra data set, didapatkan hasil uji coba skenario 2 seperti disajikan pada Tabel III dan Tabel IV, berturut-turut menggunakan metode usulan dan metode K-Means. Berdasarkan hasil perhitungan manual yang disajikan pada Tabel III, kombinasi metode SFCM dan RRM menghasilkan nilai akurasi terendah sebesar 42,11% pada citra ke-14 dan nilai akurasi tertinggi sebesar 95,83% pada oleh citra ke-20, serta menghasilkan rata-rata akurasi sebesar 78,41%. Hasil perhitungan manual berdasarkan hasil pemisahan sel bertumpuk menggunakan metode K-Means, seperti yang ditampilkan pada Tabel IV, menunjukkan nilai akurasi terendah sebesar 21,05% yang dihasilkan oleh citra ke-14 dan nilai akurasi tertinggi sebesar 86,57% pada citra ke-5, dengan rata-rata akurasi sebesar 68,73%. Perbandingan hasil perhitungan jumlah sel kanker benar, sel over-segmentation, dan sel under-segmentation dari metode yang diusulkan dan metode K-Means terhadap 40 citra mikroskopis sel kanker payudara dapat dilihat pada Tabel V. Jumlah total sel kanker pada 40 citra mikroskopis sebanyak 1856. Jumlah sel yang diperoleh dengan metode K-Means
ISSN 2301 – 4156
Citra ke 1 2 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 31 32 33 34 35 36 37 38 39 40
Sel di Sel Benar Citra Asli 47 34 44 34 34 26 46 32 67 54 57 44 42 32 28 16 27 19 29 17 32 27 47 40 62 52 19 9 27 19 40 34 74 61 36 27 71 56 26 23 82 67 42 34 31 20 23 20 46 41 40 34 50 35 61 50 43 40 39 30 74 62 89 72 53 36 26 20 47 36 43 36 54 41 31 20 108 94 26 22 Rata-rata akurasi
Sel Over 10 8 5 10 1 1 2 13 7 8 3 2 2 9 8 6 0 1 0 1 1 2 10 4 3 4 12 9 0 2 6 0 12 6 3 3 9 8 1 4
Sel Under 3 1 0 0 5 1 1 0 0 1 1 1 2 0 2 0 5 3 4 0 7 2 1 0 0 3 1 1 2 4 6 4 0 0 1 1 0 0 9 0
Akurasi (%) 70,21 75,00 85,29 69,57 80,60 78,95 76,19 55,56 70,73 67,86 84,38 89,63 83,87 42,11 70,37 85,00 86,49 86,11 78,87 95,83 82,93 80,95 64,52 81,82 89,13 82,50 74,00 81,97 93,02 82,05 83,78 84,27 69,81 69,23 76,60 83,72 84,48 68,00 87,04 84,62 78,41
C. Analisis Hasil Uji Coba Berdasarkan hasil uji coba pada skenario 1, metode yang diusulkan menghasilkan nilai MSE yang lebih baik dibandingkan metode RBAC. Rata-rata kesalahan segmentasi metode yang diusulkan adalah 0,0745, sedangkan rata-rata kesalahan segmentasi metode RBAC adalah 0,6505. Hal ini menunjukkan bahwa metode yang diusulkan mampu memberikan hasil identifikasi sel yang lebih baik dibandingkan dengan metode RBAC.
Desmin Tuwohingide: Spatial Fuzzy C-Means dan ...
57
JNTETI, Vol. 6, No. 1, Februari 2017 TABEL IV PERHITUNGAN JUMLAH SEL BERDASARKAN CITRA HASIL PEMISAHAN SEL BERTUMPUK MENGGUNAKAN METODE K-MEANS CLUSTERING PADA UJI COBA SKENARIO 2
Citra ke 1 2 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 31 32 33 34 35 36 37 38 39 40
Sel di Sel Benar Citra Asli 47 28 44 25 34 24 46 28 67 58 57 42 42 27 28 14 27 16 29 17 32 22 47 35 62 43 19 4 27 17 40 27 74 61 36 30 71 55 26 18 82 70 42 27 31 18 23 16 46 30 40 31 50 33 61 47 43 35 39 32 74 61 89 72 53 32 26 14 47 33 43 30 54 43 31 10 108 87 26 21 Rata-rata akurasi
Sel Over 17 15 10 13 0 4 7 14 10 9 8 8 12 13 10 13 3 3 0 6 3 11 13 6 14 7 17 13 7 6 9 4 17 10 7 8 15 15 16 5
Sel Under 1 2 0 0 2 1 1 0 0 0 0 0 1 0 0 0 5 2 5 0 3 0 0 0 0 2 0 0 0 0 4 3 0 0 0 2 0 0 1 0
Akurasi (%) 59,57 56,82 70,59 60,87 86,57 73,68 64,29 51,85 59,26 60,71 68,75 74,47 69,35 21,05 62,96 67,50 82,43 83,33 77,46 75,00 85,37 64,29 58,06 72,73 65,22 77,50 66,00 77,05 81,40 82,05 82,43 80,90 60,38 53,85 70,21 69,77 74,14 40,00 80,56 80,77 68,73
TABEL V PERBANDINGAN HASIL PERHITUNGAN SEL METODE YANG DIUSULKAN DAN METODE K-MEANS
K-Means SFCM dan RRM
Jumlah Benar 1333 1486
Jumlah Over 382 197
Jumlah Under 35 72
Pada hasil uji coba skenario 2, berdasarkan perhitungan manual jumlah sel benar, sel over-segmentation, dan sel under-segmentation pada citra hasil pemisahan sel kanker bertumpuk, diperoleh hasil bahwa metode usulan mampu memberikan nilai akurasi yang lebih tinggi dibandingkan metode K-Means. Keunggulan metode usulan juga terlihat
Desmin Tuwohingide: Spatial Fuzzy C-Means dan ...
dari hasil perhitungan jumlah sel yang mengalami oversegmentation, yaitu metode usulan mampu mereduksi jumlah sel yang mengalami over-segmentation. Namun, metode usulan memiliki kelemahan, yaitu mengakibatkan meningkatnya jumlah sel yang mengalami undersegmentation. Ini disebabkan belum maksimalnya penerapan ciri geometri area dalam penentuan pseudo-blob. IV. KESIMPULAN DAN SARAN Berdasarkan hasil dan analisis hasil uji coba yang telah dijelaskan, dapat disimpulkan bahwa skema segmentasi dan identifikasi sel kanker berdasarkan metode GS yang dilakukan memberikan hasil yang baik. Hal ini ditunjukkan dengan diperolehnya rata-rata nilai MSE sebesar 0,07. Metode yang diusulkan mampu memberikan hasil pemisahan sel bertumpuk yang lebih tinggi nilai akurasinya dibandingkan dengan metode K-Means. Hal ini ditunjukkan dengan dihasilkannya nilai rata-rata akurasi sebesar 78,41%. Metode ini juga mampu mereduksi jumlah sel yang mengalami over-segmentation, tetapi pada beberapa kasus terjadi peningkatan jumlah sel yang mengalami under-segmentation, yang diakibatkan oleh proses penggabungan daerah yang memproses semua sel hasil clustering. Untuk penelitian selanjutnya, perlu dilakukan pengembangan metode untuk mendeteksi daerah oversegmentation atau pseudo-blob sebelum proses penggabungan daerah untuk menghindari masalah under-segmentation. REFERENSI [1]
C. Fatichah and N. Suciati, “Nuclei Segmentation of Microscopic Breast Cancer Image using Gram-Schmidt and Cluster Validation Algorithm,” ICCSCE , pp. 27–29, November, 2015. [2] A. Mouelhi, M. Sayadi, and F. Fnaiech, “A Supervised Segmentation Scheme Based on Multilayer Neural Network and Color Active Contour Model for Breast Cancer Nuclei Detection,” ICEESA, 2013. [3] S. Xie, L. Chen, J. Chen, and H. Nie, “Image segmentation using iterative watershed and ridge detection,” J. Comput. Appl., vol. 29, no. 10, pp. 2668–2670, 2009. [4] A. Mouelhi, M. Sayadi, and F. Fnaiech, “Automatic segmentation of clustered breast cancer cells using watershed and concave vertex graph,” 2011 Int. Conf. Commun. Comput. Control Appl. CCCA 2011, no. 1, pp. 2–7, 2011. [5] A. Mouelhi, M. Sayadi, F. Fnaiech, and S. Member, “Hybrid Segmentation of Breast Cancer Cell Images Using a New Fuzzy Active Contour Model and an Enhanced Watershed Method”, CoDIT, no. 1, pp. 382–387, 2013. [6] N. Aini, C. Fatichah, and B. Amaliah, “Pemisahan Sel Bertumpuk Citra Sel Kanker Payudara Menggunakan Metode Region-Based Active Contour dan Bayesia,” SCAN-Jurnal Teknologi Informasi dan Komunikasi, pp. 1–7, 2015. [7] C. Fatichah, D. Purwitasari, V. Hariadi, and F. Effendy, “Overlapping White Blood Cell Segmentation And Counting on Microscopis Blood Cell Image,” International Journal on Smart Sensing and Intelligent Systems, vol. 7, no. 3, pp. 1271–1286, 2014. [8] P. Phukpattaranont and P. Boonyaphiphat, “Color Based Segmentation of Nuclear Stained Breast Cancer Cell Images,” Communications, vol. 5, no. 2, pp. 158–164, 2007. [9] Y. Li and Y. Shen, “Fuzzy c-means clustering based on spatial neighborhood information for image segmentation,” Journal of Systems Engineering and Electronics, vol. 21, no. 2, pp. 323–328, 2010. [10] S. Z. Beevi, M. M. Sathik, K. Senthamaraikannan, and J. H. J. Yasmin, “A RobustT Fuzzy Clustering Technique With Spatial Neighborhood Information for Effective Noisy Medical Image Segmentation,” ICCCNT, 2010. [11] Y. Chen and J. Chen, “A Watershed Segmentation Algorithm Based on Ridge Detection and Rapid Region Merging”, ICSPCC, 2014.
ISSN 2301 - 4156