Algoritma Mean Shift adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Contoh yang dibahas kali ini adalah mengenai penentuan jurusan siswa berdasarkan nilai skor siswa.
Algoritma ini merupakan pengembangan dari Algoritma Mean Shift yang sudah pernah dibahas sebelumnya, dimana pada saat contoh kasus ini, algoritma tersebut digunakan untuk melakukan segmentasi warna pada sebuah gambar. Hasil perhitungan adalah gambar dengan kumpulan warna yang lebih sederhana.
Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan gambar yang akan diolah
Perlu diingat bahwa semakin besar ukuran gambar, maka semakin lama perhitungannya
gmb = double( imread('Wallpaper XP.jpg') );
* Tentukan bandwidth dari spasial citra, yang disimbolkan dengan hs
Diasumsikan dalam kasus ini, nilai hs adalah 20
hs = 20;
* Tentukan bandwidth dari motif / corak citra, yang disimbolkan dengan hr
Diasumsikan dalam kasus ini, nilai hr adalah 32
hr = 32;
* Tentukan epsilon, yaitu batas selisih minimal antara mean sekarang dengan mean pada perhitungan sebelumnya
Jika selisih antara kedua mean tersebut kurang dari nilai ini, maka perhitungan akan dihentikan
Nilai default yang direkomendasikan adalah 0.25
Diasumsikan dalam kasus ini, nilai epsilon adalah 0.1
eps = 1 / 100;
Langkah-langkah penggunaan algoritma ini adalah
* Lakukan proses pengelompokan dengan metode Mean Shift
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 4)
gmbHasil = MeanShiftGmb(gmb, 20, 32, eps);
Memasuki perhitungan utama pada fungsi MeanShiftGmb
1. Hitung panjang, lebar, dan kedalaman gambar
[panjangGmb,lebarGmb,kedalamanGmb] = size(gmb);
2. Tambahkan angka pada masing-masing batas gambar untuk mengantisipasi perhitungan pada batas border gambar
Fungsi ini akan menambahkan angka pada sebelum dan sesudah masing-masing dimensi panjang dan lebar
Nilai yang ditambahkan sesuai dengan nilai pencerminan dari masing-masing angka
Sebagai contoh:
[ 1 2 ]
[ 3 4 ]
akan menjadi
[ 4 3 3 4 4 3 ]
[ 2 1 1 2 2 1 ]
[ 2 1 [1 2] 2 1 ]
[ 4 3 [3 4] 4 3 ]
[ 4 3 3 4 4 3 ]
[ 2 1 1 2 2 1 ]
PaddedGmb = padarray(gmb,[panjangGmb,lebarGmb,0],'symmetric');
3. Tentukan tabel bobot untuk digunakan dalam perhitungan
Nilai yang dibuat ada 255^2 buah, dengan rentang nilai berkisar antara 0 sampai dengan 1
tabelBobot = exp( -(0:255^2)/hr^2 );
4. Lakukan perhitungan selama nilai rata-rata mean shift lebih dari nilai epsilon (poin 4a – 4e)
while rata2MS > eps . . .
4a. Lakukan perhitungan 2 dimensi dari nilai negatif bandwidth spasial ke nilai positif bandwidth spasial (poin 4a1 – 4a8)
for i = -hs:hs for j = -hs:hs . . .
4a1. Lakukan perhitungan berikut apabila nilai kedua dimensi bukan 0
if ( i~=0 || j~=0 ) . . .
4a2. Hitung bobot kernel spasial
bobotKernelSpasial = 1;
4a3. Tentukan potongan gambar pada posisi yang sedang dihitung
tmpGmb = PaddedGmb(panjangGmb+i:2*panjangGmb+i-1, lebarGmb+j:2*lebarGmb+j-1, 1:kedalamanGmb);
4a4. Hitung kuadrat selisih jarak antara potongan gambar dengan gambar awal
kuadratSelisihGmb = (gmbHasil - tmpGmb).^2;
4a5. Hitung bobot kernel intensitas
bobotKernelIntensitas = repmat( prod( reshape( tabelBobot( kuadratSelisihGmb+1 ), panjangGmb, lebarGmb, kedalamanGmb) , 3 ), [1,1, kedalamanGmb]);
4a6. Lakukan perkalian isi dari matriks bobot kernel Spasial dan bobot kernel intensitas
bobotKernel = bobotKernelSpasial.*bobotKernelIntensitas;
4a7. Tambahkan nilai bobot kernel ke dalam jumlah bobot
jumlahBobot = jumlahBobot + bobotKernel;
4a8. Lakukan perkalian isi dari potongan gambar dikali dengan bobot kernel
Kemudian tambahkan nilai tersebut ke dalam jumlah Y
jumlahY = jumlahY + tmpGmb.*bobotKernel;
4b. Hitung nilai gambar hasil sementara, yaitu jumlah Y dibagi dengan jumlah bobot
Penambahan nilai epsilon pada jumlah bobot bertujuan untuk mencegah error pembagian dengan nol
tmpGmbHasil = jumlahY./(jumlahBobot+eps);
4c. Hitung rata-rata dari selisih antara gambar hasil sekarang dan gambar hasil sebelumnya
rata2MS = mean(abs(round(tmpGmbHasil(:))-round(gmbHasil(:))));
4d. Masukkan nilai rata-rata tersebut ke dalam daftar rata-rata
daftarRata2MS(jumlahIterasi+1) = rata2MS;
4e. Lakukan penggambaran hasil perhitungan pada layar
subplot(132), imshow(uint8(gmbHasil)),axis image, title(['jumlah iterasi = ' num2str(jumlahIterasi) '; rata-rata Mean Shift = ' num2str(rata2MS)]);
subplot(133), plot(0:jumlahIterasi, daftarRata2MS ), xlabel('iterasi'), ylabel('rata-rata Mean Shift'); axis square; title(['lama perhitungan = ' num2str(toc) ' detik']);
drawnow
Hasil akhir adalah: (klik untuk perbesar gambar)
Perlu diingat bahwa lama perhitungan sangat bergantung dari banyaknya pixel gambar yang dihitung. Berikut adalah perhitungan dengan menggunakan gambar dengan ukuran 32 x 32 pixel.
Perhitungan selesai setelah melakukan perulangan sebanyak 43 kali, dan waktu perhitungan adalah 9,02 detik. Waktu yang cukup cepat karena ukuran gambar yang kecil
Berikut adalah perhitungan dengan menggunakan gambar dengan ukuran 800 x 600 pixel.
Perhitungan selesai setelah melakukan perulangan sebanyak 16 kali, lebih cepat dari contoh sebelumnya. Tetapi waktu perhitungan yang dibutuhkan adalah sekitar 1.300 detik atau 21 menit lebih. Jauh lebih lama karena pixel gambar yang digunakan juga jauh lebih banyak.
Contoh modul / source code menggunakan Matlab 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.