Algoritma FCM (Fuzzy C-Means) Clustering adalah salah satu algoritma yang digunakan dalam pengolahan citra. Contoh yang dibahas kali ini adalah mengenai pemotongan gambar sesuai dengan kelompok warnanya.
Algoritma ini merupakan penggabungan dari Algoritma Fuzzy Logic dan Algoritma K-Means Clustering yang sudah pernah dibahas sebelumnya. K-Means Clustering adalah salah satu algoritma klasifikasi data yang cukup banyak dipakai untuk memecahkan masalah. Hanya saja metode tersebut tidak memiliki nilai pengembalian berupa sebuah nilai pembanding untuk masing-masing cluster, sehingga digunakan algoritma Fuzzy untuk menghitung skor dari sebuah data. Dalam kasus ini Fuzzy juga digunakan untuk membatasi nilai sebuah titik warna pada masing-masing cluster agar selalu memiliki nilai total satu. Masing-masing cluster memiliki warna perwakilan yang diambil dari nilai centroid, dan semua titik yang masuk dalam sebuah cluster akan berubah warna menjadi warna centroid pada cluster tersebut.
Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan Jumlah Cluster
Jumlah Cluster adalah jumlah dari pengelompokan data yang ingin dilakukan
Jumlah Cluster nilainya harus diantara 2 dan jumlah data
Nilai jumlah cluster dapat diset melalui input jumlah cluster pada layar
Dim jumlahCluster As Integer = CInt(numJumlahCluster.Value)
* Tentukan Jumlah maksimal perulangan / iterasi
Nilai jumlah maksimal iterasi dapat diset melalui input maksimal iterasi pada layar
Dim maksIterasi As Integer = CInt(numMaksIterasi.Value)
* Tentukan batas minimal selisih perhitungan dalam setiap iterasi
Nilai batas minimal iterasi dapat diset melalui input batas minimal selisih pada layar
Dim batasMinimalSelisihPerhitungan As Double = CDbl(numBatasMinimalSelisih.Value)
* Tentukan faktor fuzzy
Faktor fuzzy harus bernilai diatas 1
Diasumsikan dalam kasus ini, faktor fuzzy bernilai 2
Const faktorFuzzy As Single = 2
Langkah-langkah penggunaan algoritma ini adalah
1. Masukkan data titik, yaitu masing-masing warna dalam setiap pixel gambar beserta posisinya
Dim points As New List(Of ClusterPoint)() For i As Integer = 0 To gmbContoh.Width - 1 For j As Integer = 0 To gmbContoh.Height - 1 Dim warna As Color = gmbContoh.GetPixel(i, j) points.Add(New ClusterPoint(i, j, warna)) Next Next
* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class ClusterPoint untuk menampung data posisi titik, warna pixel dan indeks cluster dimana titik tersebut berada. Deklarasi Class ClusterPoint adalah sebagai berikut:
Public Class ClusterPoint
Private m_X As Double 'posisi X sebuah titik
Private m_Y As Double 'posisi Y sebuah titik
Private m_warnaPixel As Color 'warna perubahan sebuah pixel setelah masuk ke dalam cluster
Private m_warnaOriginalPixel As Color 'warna asli sebuah pixel sebelum masuk ke dalam cluster
Private m_indeksCluster As Double 'indeks cluster dimana titik ini berada
Public Property X() As Double
Get
Return m_X
End Get
Set(value As Double)
m_X = value
End Set
End Property
Public Property Y() As Double
Get
Return m_Y
End Get
Set(value As Double)
m_Y = value
End Set
End Property
Public Property warnaPixel() As Color
Get
Return m_warnaPixel
End Get
Set(value As Color)
m_warnaPixel = value
End Set
End Property
Public Property warnaOriginalPixel() As Color
Get
Return m_warnaOriginalPixel
End Get
Set(value As Color)
m_warnaOriginalPixel = value
End Set
End Property
Public Property indeksCluster() As Double
Get
Return m_indeksCluster
End Get
Set(value As Double)
m_indeksCluster = value
End Set
End Property
Public Sub New(x As Double, y As Double, col As Color)
Me.X = x
Me.Y = y
Me.warnaPixel = col
Me.warnaOriginalPixel = col
Me.indeksCluster = -1
End Sub
End Class
2. Tentukan titik acak sebanyak jumlah cluster untuk dimasukkan ke dalam masing-masing cluster
Dim centroids As New List(Of ClusterCentroid)() For i As Integer = 0 To jumlahCluster - 1 Dim posisiXAcak As Integer = random.Next(gmbContoh.Width) Dim posisiYAcak As Integer = random.Next(gmbContoh.Height) Dim warna As Color = gmb.GetPixel(posisiXAcak, posisiYAcak) centroids.Add(New ClusterCentroid(posisiXAcak, posisiYAcak, warna)) Next
* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class ClusterCentroid untuk menampung data posisi titik, jumlah masing-masing komponen warna, jumlah pixel dan warna pixel. Deklarasi Class ClusterCentroid adalah sebagai berikut:
Public Class ClusterCentroid
Private m_X As Double 'posisi X sebuah centroid
Private m_Y As Double 'posisi Y sebuah centroid
Private m_jumlahKomponenMerah As Double 'Jumlah dari nilai komponen merah pada semua titik pada cluster, digunakan untuk menghitung rata-rata
Private m_jumlahKomponenHijau As Double 'Jumlah dari nilai komponen hijau pada semua titik pada cluster, digunakan untuk menghitung rata-rata
Private m_jumlahKomponenBiru As Double 'Jumlah dari nilai komponen biru pada semua titik pada cluster, digunakan untuk menghitung rata-rata
Private m_jumlahPixelPerCluster As Double 'Jumlah pixel dalam cluster, digunakan untuk menghitung rata-rata
Private m_jumlahPixel As Double 'Jumlah pixel pada semua cluster
Private m_warnaPixel As Color 'warna perubahan sebuah pixel setelah masuk ke dalam cluster
Private m_warnaOriginalPixel As Color 'warna asli sebuah pixel sebelum masuk ke dalam cluster
Public Property X() As Double
Get
Return m_X
End Get
Set(value As Double)
m_X = value
End Set
End Property
Public Property Y() As Double
Get
Return m_Y
End Get
Set(value As Double)
m_Y = value
End Set
End Property
Public Property jumlahKomponenMerah() As Double
Get
Return m_jumlahKomponenMerah
End Get
Set(value As Double)
m_jumlahKomponenMerah = value
End Set
End Property
Public Property jumlahKomponenHijau() As Double
Get
Return m_jumlahKomponenHijau
End Get
Set(value As Double)
m_jumlahKomponenHijau = value
End Set
End Property
Public Property jumlahKomponenBiru() As Double
Get
Return m_jumlahKomponenBiru
End Get
Set(value As Double)
m_jumlahKomponenBiru = value
End Set
End Property
Public Property jumlahPixelPerCluster() As Double
Get
Return m_jumlahPixelPerCluster
End Get
Set(value As Double)
m_jumlahPixelPerCluster = value
End Set
End Property
Public Property jumlahPixel() As Double
Get
Return m_jumlahPixel
End Get
Set(value As Double)
m_jumlahPixel = value
End Set
End Property
Public Property warnaPixel() As Color
Get
Return m_warnaPixel
End Get
Set(value As Color)
m_warnaPixel = value
End Set
End Property
Public Property warnaOriginalPixel() As Color
Get
Return m_warnaOriginalPixel
End Get
Set(value As Color)
m_warnaOriginalPixel = value
End Set
End Property
Public Sub New(x As Double, y As Double, col As Color)
Me.X = x
Me.Y = y
Me.jumlahKomponenMerah = 0
Me.jumlahKomponenHijau = 0
Me.jumlahKomponenBiru = 0
Me.jumlahPixelPerCluster = 0
Me.jumlahPixel = 0
Me.warnaPixel = col
Me.warnaOriginalPixel = col
End Sub
End Class
3. Lakukan perhitungan sebanyak jumlah iterasi (poin 3a – 3i)
Dim iterasi As Integer = 0 Do While iterasi < maksIterasi . . .
3a. Hitung nilai fungsi pada gambar awal
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
fcm.nilaiFungsi = fcm.hitungNilaiFungsi()
* Gunakan fungsi ini untuk menghitung nilai fungsi dari sebuah gambar
Nilai masing-masing titik pada semua cluster dihitung dengan rumus
Jk = nilai jarak dipangkatkan faktor fuzzy * kuadrat dari (nilai jarak titik tersebut pada masing-masing cluster)
Nilai fungsi sebuah gambar adalah jumlah dari semua nilai Jk yang sudah dihitung sebelumnya
Public Function hitungNilaiFungsi() As Double Dim Jk As Double = 0.0 For i As Integer = 0 To Me.Points.Count - 1 For j As Integer = 0 To Me.Clusters.Count - 1 Jk += Math.Pow(U(i, j), Me.faktorFuzzy) * Math.Pow(Me.HitungJarak(Points(i), Clusters(j)), 2) Next Next Return Jk End Function
* Gunakan fungsi ini untuk menghitung jarak dari data dan centroid
metode yang digunakan adalah jarak Euclidean, dengan rumus akar dari (jumlah dari (kuadrat dari (data - centroid)))
Karena terdapat 3 komponen warna pada setiap pixel, maka masing-masing komponen warna akan dihitung selisihnya
Private Function HitungJarak(p As ClusterPoint, c As ClusterCentroid) As Double Return Math.Sqrt(Math.Pow(CInt(p.warnaPixel.R) - CInt(c.warnaPixel.R), 2.0) + Math.Pow(CInt(p.warnaPixel.G) - CInt(c.warnaPixel.G), 2.0) + Math.Pow(CInt(p.warnaPixel.B) - CInt(c.warnaPixel.B), 2.0)) End Function
3b. Lakukan proses perhitungan centroid baru untuk masing-masing cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3b1 - 3b2)
fcm.UpdateCentroids()
Memasuki perhitungan pada fungsi UpdateCentroids
3b1. Lakukan perhitungan pada masing-masing titik pada masing-masing cluster (poin 3b1a - 3b1d)
For j As Integer = 0 To Me.Clusters.Count - 1 Dim c As ClusterCentroid = Me.Clusters(j) Dim nilaiFuzzyJarak As Double = 0.0 For i As Integer = 0 To Me.Points.Count - 1 Dim p As ClusterPoint = Me.Points(i) . . .
3b1a. Hitung nilai fuzzy masing-masing jarak dengan rumus = nilai jarak dipangkatkan faktor fuzzy
nilaiFuzzyJarak = Math.Pow(U(i, j), Me.faktorFuzzy)
3b1b. Jumlahkan masing-masing komponen warna pada masing-masing cluster
Kemudian jumlahkan semua nilai fuzzy pada masing-masing jarak diatas
c.jumlahKomponenMerah += nilaiFuzzyJarak * p.warnaPixel.R c.jumlahKomponenHijau += nilaiFuzzyJarak * p.warnaPixel.G c.jumlahKomponenBiru += nilaiFuzzyJarak * p.warnaPixel.B c.jumlahPixel += nilaiFuzzyJarak
3b1c. Catat jumlah titik pada masing-masing cluster
If U(i, j) = p.indeksCluster Then c.jumlahPixelPerCluster += 1 End If
3b1d. Hitung warna pixel centroid yang baru
c.warnaPixel = Color.FromArgb(CByte(c.jumlahKomponenMerah / c.jumlahPixel), CByte(c.jumlahKomponenHijau / c.jumlahPixel), CByte(c.jumlahKomponenBiru / c.jumlahPixel))
3b2. Lakukan proses pengubahan gambar sesuai warna centroid pada masing-masing cluster
Semua titik yang masuk kedalam sebuah centroid, maka warna titik tersebut akan berubah menjadi warna centroid untuk titik tersebut
Dim tmp As New Bitmap(lebarGambar, panjangGambar, PixelFormat.Format32bppRgb) For j As Integer = 0 To Me.Points.Count - 1 For i As Integer = 0 To Me.Clusters.Count - 1 Dim p As ClusterPoint = Me.Points(j) If U(j, i) = p.indeksCluster Then tmp.SetPixel(CInt(p.X), CInt(p.Y), Me.Clusters(i).warnaPixel) End If Next Next gambarHasilPerhitungan = tmp
3c. Lakukan proses pengelompokan masing-masing titik pada cluster yang baru
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3c1 - 3c2)
fcm.Cluster()
Memasuki perhitungan pada fungsi Cluster
3c1. Lakukan perhitungan pada semua cluster dan semua titik (poin 3c1a - 3c1c)
For c As Integer = 0 To Clusters.Count - 1 For h As Integer = 0 To Points.Count - 1 . . .
3c1a. Hitung jarak dengan masing-masing centroid pada masing-masing cluster
Dim top As Double = HitungJarak(Points(h), Clusters(c)) If top < Epsilon Then top = Epsilon
3c1b. Hitung jumlah jarak titik dengan cluster pada semua cluster
Dim jumlahJarak As Double = 0.0 For ck As Integer = 0 To Clusters.Count - 1 jumlahJarak += top / HitungJarak(Points(h), Clusters(ck)) Next
3c1c. Masukkan nilai jarak yang baru untuk sebuah titik pada masing-masing cluster
U(h, c) = CDbl(1.0 / Math.Pow(jumlahJarak, (2 / (Me.faktorFuzzy - 1))))
* Lakukan proses perpindahan titik ke cluster lain apabila diperlukan
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
Me.UpdateCluster()
Memasuki perhitungan pada fungsi UpdateCluster
3c2. Lakukan perulangan pada masing-masing titik (poin 3c2a - 3c2d)
3c2a. Cari nilai minimal dan maksimal sebuah titik pada masing-masing cluster
For j As Integer = 0 To Me.Clusters.Count - 1 maks = If(U(i, j) > maks, U(i, j), maks) min = If(U(i, j) < min, U(i, j), min) Next
3c2b. Lakukan normalisasi nilai titik pada masing-masing cluster
Normalisasi dihitung dengan rumus = (nilai awal - nilai minimal) / (nilai maksimal - nilai minimal)
Kemudian jumlahkan semua nilai yang baru
For j As Integer = 0 To Me.Clusters.Count - 1 U(i, j) = (U(i, j) - min) / (maks - min) total += U(i, j) Next
3c2c. Lakukan update nilai titik pada masing-masing fungsi, yaitu nilai baru dibagi totalnya
Kemudian cari nilai maksimal yang baru dari nilai yang baru diupdate ini
For j As Integer = 0 To Me.Clusters.Count - 1 U(i, j) = U(i, j) / total If Double.IsNaN(U(i, j)) Then U(i, j) = 0.0 maksBaru = If(U(i, j) > maksBaru, U(i, j), maksBaru) Next
3c2d. Pindahkan titik ke cluster yang memiliki nilai tertinggi
p.indeksCluster = maksBaru
3d. Hitung nilai fungsi pada gambar yang telah mengalami pengelompokan
Fungsi untuk mencari nilai fungsi sudah dijelaskan pada penjelasan sebelumnya
Dim nilaiFungsiBaru As Double = fcm.hitungNilaiFungsi()
3e. Tampilkan selisih perhitungan sementara pada layar
bw.ReportProgress((100 * iterasi) / maksIterasi, New UpdateLabel(lblSelisihPerhitungan, "Selisih Perhitungan " & Math.Abs(fcm.nilaiFungsi - nilaiFungsiBaru).ToString("F2")))
3f. Tampilkan waktu perhitungan sementara pada layar
Dim waktu As String = [String].Format("{0:00}:{1:00}:{2:00}.{3:00}", sw.Elapsed.Hours, sw.Elapsed.Minutes, sw.Elapsed.Seconds, sw.Elapsed.Milliseconds / 10)
bw.ReportProgress((100 * iterasi) / maksIterasi, New UpdateLabel(lblLamaPerhitungan, Convert.ToString("Lama Perhitungan: ") & waktu))
3g. Tampilkan hasil perhitungan gambar sementara pada layar
picHasil.Image = DirectCast(fcm.getGambarHasilPerhitungan, Bitmap)
3h. Tampilkan jumlah perulangan yang telah dilakukan pada layar
bw.ReportProgress((100 * iterasi) / maksIterasi, New UpdateLabel(lblIterasi, "Iterasi " & iterasi))
3i. Apabila selisih nilai fungsi kurang dari batas minimal selisih perhitungan, maka hentikan perhitungan
If Math.Abs(fcm.nilaiFungsi - nilaiFungsiBaru) < batasMinimalSelisihPerhitungan Then Exit Do
4. Simpan hasil pengelompokan pixel gambar
picHasil.Image = DirectCast(fcm.getGambarHasilPerhitungan.Clone(), Bitmap)
fcm.getGambarHasilPerhitungan.Save("HasilFCM.png")
5. Buat gambar baru untuk mengetahui hasil potongan gambar awal pada masing-masing cluster
Dim jarak As Double(,) = fcm.U
Dim bmpPerCluster As Bitmap() = New Bitmap(centroids.Count - 1) {}
For i As Integer = 0 To centroids.Count - 1
bmpPerCluster(i) = New Bitmap(gmbContoh.Width, gmbContoh.Height, PixelFormat.Format32bppRgb)
Next
6. Masukkan hasil gambar pada masing-masing cluster
For j As Integer = 0 To points.Count - 1 For k As Integer = 0 To centroids.Count - 1 Dim p As ClusterPoint = points(j) If jarak(j, k) = p.indeksCluster Then bmpPerCluster(k).SetPixel(CInt(p.X), CInt(p.Y), p.warnaOriginalPixel) End If Next Next
7. Simpan hasil potongan gambar pada masing-masing cluster
For i As Integer = 0 To centroids.Count - 1
bmpPerCluster(i).Save("HasilFCM_Cluster" & i & ".png")
Next
8. Tampilkan jumlah perulangan akhir pada layar
bw.ReportProgress(100, New UpdateLabel(lblIterasi, "Selesai dalam " & iterasi & " iterasi."))
9. Tampilkan total waktu perhitungan pada layar
Dim waktuSelesai As String = [String].Format("{0:00}:{1:00}:{2:00}.{3:00}", sw.Elapsed.Hours, sw.Elapsed.Minutes, sw.Elapsed.Seconds, sw.Elapsed.Milliseconds / 10)
bw.ReportProgress(100, New UpdateLabel(lblLamaPerhitungan, "Waktu perhitungan " & waktuSelesai & ""))
Hasil akhir adalah: (klik untuk perbesar gambar)
Hasil akhir gambar bergantung dari parameter jumlah cluster yang dihitung, semakin banyak cluster, maka hasil akhir gambar akan semakin baik, tetapi perhitungan akan semakin lama. Sesuai perhitungan pada poin 4 sampai dengan 7, setiap potongan data gambar yang mengalami pengelompokan akan disimpan sendiri-sendiri, sehingga dapat diketahui potongan gambar awal yang mana yang termasuk dalam masing-masing cluster
Berikut adalah perbandingan antara gambar awal dan hasil perhitungan gambar dengan 3 cluster
 |
 |
 |
Karena menggunakan 3 cluster, maka terdapat 3 potongan gambar sesuai dengan cluster masing-masing. Potongan gambar tersebut adalah sebagai berikut
 |
 |
 |
Hanya sebagai catatan saja, dalam perhitungan tersebut digunakan 20 perulangan / iterasi, tetapi perhitungan selesai pada iterasi ke 13, karena selisih perhitungan pada iterasi ke 12 dan 13 adalah 0, sehingga tidak perlu meneruskan perhitungan sampai selesai. Waktu perhitungan adalah 1 menit lebih 5,97 detik
Contoh kedua adalah perbandingan antara gambar awal dan hasil perhitungan gambar dengan 10 cluster
|
|
 |
|
Dapat dilihat bahwa hasil perhitungan gambar akan lebih bagus, karena semakin banyak cluster yang dipakai
Karena menggunakan 10 cluster, maka terdapat 10 potongan gambar sesuai dengan cluster masing-masing. Potongan gambar tersebut adalah sebagai berikut
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
Hanya sebagai catatan saja, dalam perhitungan tersebut digunakan 50 perulangan / iterasi, dan perhitungan selesai pada iterasi ke 49, karena selisih perhitungan pada iterasi ke 48 dan 49 adalah 0, sehingga tidak perlu meneruskan perhitungan sampai selesai. Waktu perhitungan adalah 24 menit lebih 4,61 detik. Waktu perhitungan yang cukup lama dibandingkan perhitungan sebelumnya dengan jumlah cluster yang lebih sedikit
Contoh source code lengkap dalam bahasa VB (Visual Basic) dapat didownload disini:
Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.