JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-5
1
Modifikasi Algoritma Pengelompokan K-Means untuk Segmentasi Citra Ikan Berdasarkan Puncak Histogram Shabrina Mardhi Dalila, Handayani Tjandrasa, dan Nanik Suciati Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia E-mail:
[email protected] Abstrak—Algoritma pengelompokan K-Means adalah metode pengelompokan berdasarkan nilai tertentu ke dalam sejumlah k cluster. Pada pengolahan citra, algoritma pengelompokan KMeans banyak digunakan untuk segmentasi citra. Segmentasi citra ikan merupakan salah satu metode yang dapat digunakan pada aplikasi citra ikan untuk mengenali jenis ikan dilihat dari hasil ekstraksi. Tetapi ada kemungkinan hasil dari segmentasi menggunakan algoritma pengelompokan K-Means kurang baik karena jumlah cluster yang dipilih kurang tepat, sehingga hasil ekstraksi kontur tubuh ikan yang diperoleh pun kurang lengkap. Dalam rangka meningkatkan kualitas hasil segmentasi citra ikan dan mendapatkan jumlah cluster yang tepat, maka pada artikel ini akan dibahas sebuah metode yang merupakan kombinasi antara algoritma pengelompokan K-Means berdasarkan puncak histogram dan ekstraksi kontur tubuh ikan dengan morfologi matematika. Pada hasil segmentasi dilakukan thresholding untuk membagi citra menjadi dua bagian, yaitu hitam dan putih agar dapat dilakukan ekstraksi dengan morfologi matematika. Dengan modifikasi algoritma pengelompokan K-Means dan thresholding, akan diperoleh hasil ekstraksi kontur yang baik. Kata Kunci—Morfologi Matematika, Pengelompokan KMeans, Puncak Histogram, Segmentasi Citra, Thresholding.
P
I. PENDAHULUAN
RODUKSI ikan merupakan salah satu sumber ekonomi pada penduduk di beberapa negara. Teknologi analisis citra diperkenalkan pada sistem diagnosis penyakit ikan oleh para peneliti agar mempercepat dalam pencegahan dan pengobatan penyakit ikan secara akurat. Segmentasi citra ikan adalah langkah dasar dalam memperoleh hasil ekstraksi kontur tubuh ikan. Segmentasi citra ikan ini juga dapat diterapkan pada media pengolahan produk akuatik, perilaku ikan, mengidentifikasi dan mengklasifikasi ikan, dan lain-lain [1]. Algoritma pengelompokan K-Means merupakan salah satu metode untuk melakukan segmentasi citra. Namun, ketika melakukan segmentasi citra menggunakan algoritma pengelompokan K-Means seringkali hasilnya kurang baik apabila jumlah cluster yang ditentukan kurang tepat. Dalam rangka meningkatkan kualitas hasil segmentasi citra dengan algoritma pengelompokan K-Means, pada artikel ini akan dibahas mengenai modifikasi algoritma pengelompokan KMeans untuk memperoleh jumlah cluster secara tepat. Penentuan jumlah cluster pada modifikasi algoritma pengelompokan K-Means ini adalah berdasarkan jumlah
puncak histogram. Selain itu, juga dilakukan seleksi terhadap pusat cluster awal untuk mengatasi pusat cluster awal yang dipilih secara acak agar hasilnya stabil. Dengan demikian, artikel ini membahas mengenai penerapan modifikasi algoritma pengelompokan K-Means dengan jumlah cluster yang diperoleh dari jumlah puncak histogram yang telah dilakukan smoothing, sehingga mendapatkan jumlah cluster yang tepat untuk melakukan segmentasi citra ikan. Implementasi diharapkan dapat digunakan untuk melakukan segmentasi citra ikan dan memberikan hasil yang lebih baik daripada menggunakan algoritma pengelompokan K-Means biasa yang belum dapat menentukan jumlah cluster dengan tepat. II. TINJAUAN PUSTAKA A. Algoritma Pengelompokan K-Means Algoritma pengelompokan K-Means adalah algoritma pengelompokan (clustering) berdasarkan jarak yang membagi data ke dalam sejumlah cluster. Algoritma ini hanya bekerja pada atribut numerik. Algoritma pengelompokan K-Means mengambil sebagian dari banyaknya komponen populasi yang akan dijadikan sebagai pusat cluster awal. Titik pusat cluster awal ditentukan secara acak. Masingmasing titik data dihitung jaraknya ke masing-masing titik pusat cluster. Titik data tersebut memilih pusat cluster terdekat, setelah itu pusat cluster baru ditentukan dengan menghitung nilai rata-rata dari data di dalam pusat cluster yang sama. Clustering tersebut dilakukan kembali, sampai titik data tidak berubah posisinya [1]. B. Histogram Histogram pada pengolahan citra merupakan informasi yang diekstrak dari intensitas citra dan dapat menjadi dasar dari fungsi transformasi intensitas. Histogram memegang peran yang sangat penting dalam pengolahan citra seperti enhancement, kompresi, segmentasi, dan deskripsi. Sumbu horizontal pada histogram menunjukkan nilai piksel citra, sedangkan sumbu vertikal menunjukkan nilai jumlah piksel citra [2]. Grafik histogram yang berbentuk bukit disebut puncak histogram. Sebagai contoh, citra digital memiliki L derajat keabuan, yaitu dari nilai 0 sampai L–1 (misalkan pada citra dengan kuantisasi derajat keabuan 8-bit, nilai derajat keabuan dari 0
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-5
2 Fi(u,v) pada (6) adalah transformasi Fourier dari masingmasing ln i(x,y) dan ln r(x,y). Jika diproses Z(u,v) dengan fungsi filter H(u,v) yang dapat dilihat pada (7). S(u,v) = H(u,v) Z(u,v) = H(u,v) Fi(u,v) + H(u,v) Fr(u,v).
Gambar 1. Histogram citra.
sampai 255). Secara matematis rumus untuk menghitung histogram citra dapat dilihat pada (1), h
ni , i = 0, 1, …, L-1. n
(1)
dimana: ni = Jumlah piksel yang memiliki derajat keabuan i, n = Jumlah seluruh piksel di dalam citra. Plot hi versus fi dinamakan histogram. Gambar 1 adalah contoh sebuah histogram citra. Secara grafis, histogram ditampilkan dengan diagram batang. C. Homomorphic Filtering Homomorphic filtering adalah teknik umum untuk sinyal dan pengolahan citra yang melibatkan pemetaan nonlinier untuk domain yang berbeda dimana teknik filter yang linier diterapkan, diikuti oleh pemetaan kembali ke domain asli. Filter ini dapat digunakan untuk peningkatan kualitas citra, menormalkan kecerahan pada gambar, dan meningkatkan kontras. Tujuan melakukan homomorphic filtering adalah untuk menghilangkan derau multiplikatif [3]. Sebuah gambar f(x,y) dapat dinyatakan sebagai hasil dari pencahayaan dan komponen reflektansi. Pernyataan citra f(x,y) dapat dilihat pada (2), f ( x, y) i( x, y).r ( x, y) .
(2)
tetapi (2) tidak dapat digunakan langsung untuk operasi pemisahan pada frekuensi komponen dari pencahayaan dan komponen reflektansi karena transformasi Fourier hasil dari dua fungsi tidak dipisahkan, dengan kata lain rumus dapat dinotasikan seperti pada (3). F{ f ( x, y)} F{i( x, y)}.F{r ( x, y)} .
z(x,y) = ln f(x,y) = ln i(x,y) + ln r(x,y).
S(u,v) (7) adalah hasil transformasi Fourier. Pada domain spasial, dapat dilihat pada (8). s(x,y) = F-1{S(u,v)} = F-1{H(u,v).Fi(u,v)} + F-1{H(u,v)} Fr(u,v)} = i’(x,y) + r’(x,y).
g(x,y) = es(x,y) = ei’(x,y).er’(x,y) = i0(x,y) r0(x,y).
i0(x,y) = ei’(x,y) dan r0(x,y) = er’(x,y).
E. Akurasi
(5)
Z(u,v) = Fi(u,v) + Fr(u,v).
(6)
(10)
D. Morfologi Matematika Morfologi matematika adalah suatu alat matematika untuk menganalisis citra dengan dasar elemen struktural guna mengukur dan melakukan ekstraksi bentuk yang sesuai pada citra. Morfologi matematika ini merupakan teknik pengolahan citra digital yang didasarkan pada bentuk segmen atau region di dalam citra. Proses morfologi difokuskan pada pengolahan bentuk objek dan biasanya diterapkan pada citra biner (hitamputih). Morfologi matematika termasuk didalamnya, yaitu erosi, dilasi, operasi terbuka, dan operasi tertutup. Rumus untuk masing-masing morfologi matematika dapat dilihat pada (11) sampai dengan (14) [4].
(4)
F{z(x,y)} = F{ln f(x,y)} = F{ln i(x,y)} + F{ln r(x y)}.
(9)
Notasi i0(x,y) dan r0(x,y) pada (9) dituliskan dalam (10).
Erosi = A ⊖ B = {x|Bx ⊆ A}. Dilasi = A ⊕ B = {z|(B)z ∩ A ⊆ A}. Operasi terbuka = A ◦ B = {A ⊖ B} ⊕ B. Operasi tertutup = A . B = {A ⊕ B} ⊖ B.
Oleh karena karakteristik yang dimiliki oleh komponen pencahayaan dan reflektansi bekerja pada domain frekuensi, maka dilakukan transformasi Fourier pada citra yang ditunjukkan pada (5) atau seperti pada (6).
(8)
Tahap terakhir adalah menghilangkan operasi logaritma yang dilakukan pada proses awal dengan melakukan operasi invers (eksponensial) untuk mendapatkan peningkatan kualitas citra, dinotasikan dengan g(x,y) pada (9).
(3)
Misalkan, didefinisikan rumus seperti pada (4).
(7)
(11) (12) (13) (14)
Penghitungan untuk akurasi segmentasi citra dapat dihitung dengan menggunakan rumus pada (15). |𝐴 ∩ 𝑅| 𝑃 𝑅; 𝐴 = × 100%. (15) |𝐴 ∪ 𝑅| Pada (15), R adalah hasil dari proses segmentasi citra dan A adalah citra ground truth. | ∩ | menghitung seberapa banyak piksel citra ground truth yang berhimpitan dengan citra yang sudah tersegmentasi, sedangkan | ∪ | menghitung jumlah keseluruhan piksel yang ada pada baik citra ground truth maupun citra hasil segmentasi [5].
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-5
3
III. METODOLOGI A. Deskripsi Umum Modifikasi algoritma pengelompokan K-Means pada artikel ini dilakukan dengan menentukan nilai k sebagai jumlah cluster berdasarkan jumlah puncak histogram yang telah dilakukan smoothing dan seleksi pusat cluster awal, karena pada algoritma pengelompokan K-Means biasa jumlah cluster secara tepat tidak diketahui. Pada citra yang telah tersegmentasi kemudian dilakukan proses morfologi matematika, sehingga mendapatkan kontur objek. Tahap segmentasi citra menggunakan modifikasi algoritma pengelompokan K-Means dan ekstraksi kontur tubuh ikan ditunjukkan oleh Gambar 2. B. Langkah-langkah Pada bagian ini akan dijelaskan mengenai langkah-langkah segmentasi citra dengan algoritma pengelompokan K-Means yang telah dimodifikasi, meliputi masukan data, preprocessing, proses, dan keluaran. Masukan Masukan berupa citra ikan berwarna. Preprocessing Citra berwarna diubah menjadi citra grayscale. Sebelum melakukan proses segmentasi citra, dilakukan preprocessing terlebih dahulu untuk meningkatkan kualitas citra agar mendapatkan hasil yang maksimal. Preprocessing dalam pengolahan citra ikan ini menggunakan metode filter homomorphic. Setelah preprocessing pada citra, dilakukan pembentukan histogram piksel-piksel citra. Dari histogram yang telah terbentuk kemudian dilakukan smoothing dengan fungsi tertentu yang sesuai dengan bentuk histogram, sehingga terbentuk kurva. Berdasarkan fungsi pembentuk kurva tersebut diperoleh jumlah puncak histogram. Jumlah puncak histogram ini akan digunakan sebagai nilai k, yaitu jumlah cluster dalam algoritma pengelompokan K-Means untuk segmentasi citra. Tahap Segmentasi Pada modifikasi algoritma pengelompokan K-Means untuk segmentasi citra ikan ini dilakukan dengan jumlah cluster sebanyak puncak histogram yang diperoleh dari penurunan fungsi persamaan pembentuk kurva histogram. Setelah mendapatkan jumlah cluster dari jumlah puncak histogram, atur jumlah puncak histogram sebagai nilai k, dan nilai ratarata seluruh piksel kemudian dihitung. Segmentasi citra dengan algoritma pengelompokan K-Means diawali dengan memilih data piksel sejumlah k secara acak sebagai pusat cluster awal. Kemudian nilai rata-rata pusat cluster dari hasil pemilihan piksel secara acak tersebut dihitung. Lalu dilanjutkan dengan menghitung selisih antara nilai rata-rata pusat cluster dengan nilai rata-rata seluruh piksel. Setelah memperoleh nilai selisih, dilakukan perbandingan antara nilai selisih dengan nilai rata-rata seluruh piksel. Apabila nilai selisih lebih besar daripada nilai rata-rata seluruh piksel, dilakukan kembali pemilihan data piksel untuk pusat cluster sejumlah k secara acak sampai akhirnya mendapatkan nilai selisih yang lebih kecil daripada nilai ratarata seluruh piksel. Setelah memperoleh pusat cluster awal dengan melewati tahap seleksi, langkah berikutnya adalah menghitung jarak
gambar asli
diubah menjadi grayscale
histogram
pembentukan histogram smoothing histogram
smooth histogram
hitung puncak histogram
citra grayscale enhancement homomorphic filtering
jumlah puncak diperoleh, k = jumlah puncak histogram
segmentasi dengan modifikasi algoritma pengelompokan KMeans dengan cluster sejumlah k kontur tubuh ikan
morfologi matematika
citra tersegmentasi
Gambar 2. Tahap modifikasi algoritma pengelompokan K-Means dan ekstraksi kontur.
tiap-tiap piksel data citra ke tiap-tiap pusat cluster. Apabila jarak suatu data piksel ke suatu pusat cluster jaraknya lebih dekat daripada ke pusat cluster lainnya, maka data tersebut dikelompokkan pada cluster dengan pusat cluster tersebut. Setelah terbentuk cluster, nilai rata-rata masing-masing cluster dihitung untuk dijadikan pusat cluster baru, kemudian penghitungan jarak tiap-tiap piksel ke tiap-tiap pusat cluster dilakukan kembali. Proses dilakukan terus sampai cluster tidak berubah dan hasil segmentasi diperoleh. Tahap Ekstraksi Hasil keluaran berupa citra ikan tersegmentasi diperoleh dari proses segmentasi. Pada citra yang telah disegmentasi, dilakukan perubahan citra ke dalam piksel hitam dan putih. Piksel citra yang dikelompokkan ke dalam warna hitam bernilai 0, sedangkan pada piksel citra yang dikelompokkan ke dalam warna putih bernilai 1. Penentuan piksel citra menjadi warna hitam dan putih ini menggunakan nilai ambang. Penghitungan nilai ambang diperoleh dengan mengurutkan pusat cluster dari urutan terkecil sampai terbesar dan menghitung selisih diantara pusat cluster berdekatan yang telah diurutkan. Dua pusat cluster berdekatan yang memiliki selisih terbesar akan dicari nilai tengahnya yang akan menjadi nilai ambang. Nilai piksel pada citra tersegmentasi yang lebih besar dari nilai ambang akan menjadi bernilai 1, sedangkan nilai piksel yang lebih kecil daripada nilai ambang akan menjadi bernilai 0. Hasilnya, citra akan menjadi citra hitamputih. Rekonstruksi kemudian dilakukan pada citra hitamputih dengan mengisi lubang pada area boundary dan filter median. Ekstraksi dilakukan dengan morfologi matematika, yaitu hasil dilasi dikurangi hasil erosi. Keluaran dari hasil ekstraksi ini adalah tepi objek.
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-5
(a) (b) Gambar 3. Data uji. (a) Data uji 1 [6], (b) data uji 2 [1].
(b)
(a)
(c)
(d) (e) (f) Gambar 4. Hasil segmentasi modifikasi algoritma pengelompokan KMeans, citra hitam-putih, dan hasil ekstraksi tepi. (a) Hasil segmentasi Gambar 3 (a), (b) citra hitam-putih Gambar 3 (a), (c) hasil ekstraksi tepi Gambar 3 (a), (d) hasil segmentasi Gambar 3 (b), (e) citra hitam-putih Gambar 3 (b), (f) hasil ekstraksi tepi Gambar 3 (b).
(a)
(b)
(c)
(d) (e) (f) Gambar 5. Hasil segmentasi algoritma pengelompokan K-Means biasa, citra hitam-putih, dan hasil ekstraksi tepi. (a) Hasil segmentasi Gambar 3 (a), (b) citra hitam-putih Gambar 3 (a), (c) hasil ekstraksi tepi Gambar 3 (a), (d) hasil segmentasi Gambar 3 (b), (e) citra hitam-putih Gambar 3 (b), (f) hasil ekstraksi tepi Gambar 3 (b).
(a) (b) Gambar 6. Ground truth citra hitam-putih. (a) Ground truth citra hitam-putih Gambar 3 (a), (b) ground truth citra hitam-putih Gambar 3 (b).
IV. UJI COBA DAN PEMBAHASAN A. Uji Coba Pada bagian ini akan dibahas mengenai uji coba hasil dari perbandingan modifikasi algoritma pengelompokan K-Means berdasarkan puncak histogram dan algoritma pengelompokan K-Means biasa. Data uji yang digunakan untuk menunjukkan segmentasi citra ikan menggunakan algoritma pengelompokan K-Means yang telah dimodifikasi pada artikel ini dapat dilihat pada Gambar 3. Uji coba dilakukan dengan membandingkan hasil segmentasi menggunakan modifikasi algoritma pengelompokan K-Means dan hasil segmentasi menggunakan algoritma pengelompokan K-Means biasa yang diubah menjadi citra hitam-putih dan diekstraksi sehingga membentuk tepi. Jumlah cluster pada algoritma pengelompokan K-Means biasa dimasukkan secara manual, yaitu sebanyak 5 cluster, sedangkan pada modifikasi algoritma pengelompokan K-Means, jumlah cluster adalah sama dengan jumlah puncak histogram. Dapat dilihat pada Gambar 4 dan Gambar 5 bahwa modifikasi algoritma pengelompokan KMeans menghasilkan citra hitam-putih dan hasil ekstraksi
4
No. 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. Ratarata
Akurasi 1 (%) 98,31 96,06 96,61 98,21 95,09 90,12 90,63 97,34 94,05 89,44 87,34 95,30 85,23 94,34 93,90 95,44 96,41 95,19 91,45 90,16 97,80 96,36 96,01 85,01 97,87 86,23
Tabel 1 Hasil Uji Coba. Akurasi 2 (%) 83,12 93,24 86,52 93,84 86,23 89,91 85,79 97,32 83,53 73,13 72,78 93,01 73,21 80,57 78,46 95,59 96,71 87,79 91,82 87,79 93,61 92,27 96,98 88,92 96,73 87,65
Akurasi 1 > Akurasi 2 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ X X √ X √ √ √ X X √ X
90,14
87,94
√
kontur tepi yang lebih lengkap daripada algoritma pengelompokan K-Means biasa. Gambar 6 merupakan citra ground truth dari citra hitam-putih. Tabel 1 menunjukkan hasil akurasi citra tersegmentasi menggunakan modifikasi algoritma pengelompokan K-Means dan menggunakan algoritma pengelompokan K-Means biasa yang diubah menjadi citra hitam-putih terhadap citra ground truth pada beberapa data uji. Akurasi 1 pada Tabel 1 menunjukkan akurasi citra hitam-putih yang dihasilkan citra segmentasi menggunakan modifikasi algoritma pengelompokan K-Means terhadap ground truth. Akurasi 2 menunjukkan akurasi citra hitam-putih yang dihasilkan citra segmentasi menggunakan algoritma pengelompokan K-Means biasa terhadap ground truth. B. Hasil Uji Coba Pada Gambar 4 dan Gambar 5 dapat dilihat bahwa hasil segmentasi, citra hitam-putih, dan ekstraksi kontur tepi pada algoritma pengelompokan K-Means yang telah dimodifikasi memberikan hasil tubuh ikan yang lebih lengkap daripada algoritma pengelompokan K-Means biasa. Dapat dilihat pula pada Tabel 1 bahwa nilai rata-rata akurasi citra hitam-putih yang dihasilkan citra segmentasi menggunakan modifikasi algoritma pengelompokan K-Means lebih besar daripada nilai rata-rata akurasi citra hitam-putih yang dihasilkan citra segmentasi menggunakan algoritma pengelompokan K-Means biasa. Hal ini menunjukkan bahwa algoritma pengelompokan K-Means yang telah dimodifikasi memberikan hasil yang lebih baik daripada algoritma pengelompokan K-Means biasa.
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-5 KESIMPULAN 1.
2. 3.
Modifikasi algoritma pengelompokan K-Means berdasarkan puncak histogram memberikan hasil segmentasi dan ekstraksi kontur tubuh ikan yang lebih lengkap daripada algoritma pengelompokan K-Means biasa. Jumlah cluster dan seleksi terhadap pusat cluster awal pada algoritma pengelompokan K-Means mempengaruhi hasil segmentasi citra. Nilai rata-rata akurasi hasil segmentasi menggunakan modifikasi algoritma pengelompokan K-Means yang diubah menjadi citra hitam-putih terhadap ground truth lebih besar daripada nilai rata-rata akurasi hasil segmentasi menggunakan algoritma pengelompokan KMeans biasa yang diubah menjadi citra hitam-putih terhadap ground truth. UCAPAN TERIMA KASIH
Penulis S.M.D. mengucapkan terima kasih kepada Allah SWT, kedua orangtua dan keluarga penulis, dosen pembimbing, kepala jurusan, dosen, dan staf Teknik Informatika, serta kerabat dekat dan pihak yang telah membantu menyelesaikan artikel ini. DAFTAR PUSTAKA [1] [2]
[3] [4] [5] [6]
Qingling Duan, Daoliang Li, and Wang Jianping Hong Yao, "An Improved K-Means Clustering Algorithm for Fish Image Segmentation," Elsevier, Dec. 2012. (2013, June) Ebookbrowse. [Online]. http://ebookbrowse.com/histogram-citra-pdf-d359281839H. Poor, An Introduction to Signal Detection and Estimation. New York: SpringerVerlag (1985) Ch. 4. Rafael C Gonzales and Richard E Woods, "Image Enhancement in the Frequency Domain," in Digital Image Processing, 2nd ed. New Jersey, United States of America: Prentice Hall, 2002, ch. 4, pp. 191-194. Rafael C Gonzales and Richard E Woods, "Morphological Image Processing," in Digital Image Processing, 2nd ed. New Jersey, United States of America: Prentice Hall, 2002, ch. 9, pp. 523-525. Song Wang, Tiecheng Liu Feng Ge, "Image-Segmentation Evaluation From the Perspective of Salient Object Extraction," IEEE Computer Society, 2006. (2013, June) NOVA. [Online]. http://www.pbs.org/wgbh/nova/camo/anat-nf.html
5
