dalam contoh ini variance bernilai 2000 || Ip – It || 2 = (200-150)2 + (150-180)2 + (250120) || Ip – It || 2 = 28400. Dp (t) = exp(-28400/2*2000) Dp (t) = 8.251 x 10-4. Untuk bobot t-link {p, t} dengan p merupakan anggota background (B) maka bobot akan bernilai K dengan formulasi perhitungan terlihat pada persamaan 4. Jika p merupakan anggota objek utama (O) maka akan bernilai 0. Setelah graf terbentuk, tahapan selanjutnya adalah melakukan implementasi algoritme Boykov and Kolmogorov max flow/min cut graph. Langkah detail dari algoritme ini adalah sebagai berikut: (Boykov & kolmogorov 2001) 1.
Mencari path atau lintasan dari terminal source ke terminal sink.
2.
Mencari bobot yang paling minimum antara dua buah node yang bertetanggaan dalam path atau lintasan tersebut sebagai representasi minimum cut atau maksimum dari flow yang bisa melewati path atau lintasan tersebut.
3.
Update masing-masing bobot antar node yang bertetanggaan dalam path atau lintasan tersebut dengan nilai yang ditemukan pada langkah kedua dengan mengurangkan setiap bobot pada edge penyusun path.
4.
Lakukan langkah 1 sampai 3 hingga tidak terdapat path atau lintasan dari source ke sink.
5.
Mencari node anggota masing-masing terminal berdasarkan karakteristik terminal.
Dalam sistem segmentasi citra masukan akan dipecah menjadi 4 bagian seperti terlihat pada Gambar 15. Untuk setiap bagian hasil pemecahan citra akan dilakukan segmentsi dengan membentuk graf dan implementasi metode Boykov and Kolmogorov max flow/min cut graph.
Gambar 15 Contoh pembagian citra di dalam sistem segmentasi.
Pengenalan Pada tahapan ini semua citra hasil segmentasi dipilih berdasarkan kriteria tertentu untuk diuji menggunakan sistem Local Binary Pattern (LBP) dan diklasifikasikan menggunakan Probabilistic Neural Network (PNN). HASIL DAN PEMBAHASAN Praproses Data Sebelum semua citra disegmentasi, pada penelitian ini terlebih dahulu citra akan diubah ukurannya. Pada tahapan ini, citra akan diubah ukurannya mejadi berukuran 270x210 pixel atau di bawahnya. Hasil praproses dapat dilihat pada Gambar 16.
Gambar 16 Praproses data. Segmentasi Setelah semua data melalui praproses maka tahapan berikutnya adalah melakukan segmentasi pada data citra. Pada tahapan ini segmentasi dilakukan pada beberapa tipe citra antara lain citra dengan latar belakang sederhana, citra dengan latar belakang kompleks, citra dengan pencahayaan seragam dan citra pencahayaan tidak seragam serta citra dengan keragaman warna objek. Tampilan sistem segmentasi dapat dilihat pada Lampiran 2. Hasil segmentasi untuk keseluruhan jenis citra dapat dilihat pada Lampiran 1. Berikut hasil segmentasi untuk semua tipe citra. Citra dengan latar belakang sederhana Citra dengan latar belakang sederhana merupakan citra yang sebagian besar bagian penyusunnya adalah objek utama. Dalam citra ini objek utama tersusun oleh kumpulan intensitas yang memiliki kemiripan nilai. Untuk komponen background, citra ini hanya memiliki satu komponen background sederhana dan memiliki intensitas yang berbeda dengan komponen objek utama. Pelabelan pada citra jenis ini akan menghasilkan dua wilayah yang besar dan satu wilayah yang kecil. Kedua wilayah yang besar tersebut adalah wilayah objek utama dan wilayah background. Kedua wilayah besar ini
6
terjadi karena citra hanya disusun oleh satu jenis objek utama dan satu background yang sederhana dan masing-masing penyusunnya memiliki kemiripan nilai intensitas. Pada konstruksi link objek utama, semua node memiliki konstruksi yang kuat antara satu node dengan node yang lain. Hal ini ditunjukkan dengan besarnya nilai perhitungan bobot yang terjadi antar pixel dalam objek utama. Untuk konstruksi link background, semua node memiliki konstruksi yang kuat seperti yang terjadi pada konstruksi link objek utama. Namun untuk konstruksi link pada batas antara objek utama dan background, terdapat konstruksi link yang lemah. Konstruksi lemah ini terjadi karena pixel-pixel yang menjadi batas antara objek utama dan background memiliki perbedaan yang besar. Algoritme max flow/min cut mencari path berdasarkan hubungan ketetanggaan yang minimum untuk terminal maupun untuk ketetanggaan antar pixel. Cara kerja ini menyebabkan edge lemah yang terjadi di antara objek utama dan background menjadi anggota path dari source ke sink. Pengambilan ini akan mengakibatkan edge-edge tersebut menjadi cut yang memisahkan objek utama dengan background. Pemisahan ini yang menyebabkan hasil segmentasi untuk citra jenis ini baik. Hasil segmentasi terlihat pada Gambar 17.
Pelabelan pada objek utama menghasilkan inisialisasi wilayah yang baik. Namun untuk background, inisialisasi wilayah tidak berjalan dengan baik. Hasil ini disebabkan oleh keragaman objek pada background yang memiliki intensitas berbeda untuk setiap komponennya. Konstruksi link pada objek utama menghasilkan konstruksi yang kuat antar pixel atau node penyusun objek utama. Konstruksi ini dihasilkan oleh pixel-pixel penyusun yang memiliki nilai yang hampir sama. Untuk konstruksi background, konsruksi akan kuat pada beberapa komponen yang memiliki nilai intensitas yang hampir sama dengan intensitas yang dipilih oleh pengguna. Namun hal yang sama tidak terjadi pada konstruksi antar komponen penyusun background. Kondisi ini disebabkan oleh perbedaan nilai intensitas pada komponen penyusun background. Keragaman objek atau komponen pada background juga menyebabkan segmentasi dilakukan lebih dari satu kali untuk mendapatkan hasil yang baik. Perlakuan ini dilakukan karena algoritme max flow/min cut hanya mampu menghilangkan satu atau dua komponen background dalam satu kali segmentasi. Pada citra jenis ini pengambilan cut terjadi pada batas antara objek utama dan background yang terinisialisasi wilayahnya dan tidak pada seluruh batas antara objek utama dan background untuk satu kali segmentasi. Hasil segmentasi pada citra jenis ini cukup baik seperti terlihat pada Gambar 18.
.
Gambar
17 Contoh hasil segmentasi citra dengan latar belakang sederhana.
Citra dengan latar belakang kompleks Citra dengan latar belakang kompleks merupakan jenis citra yang memiliki bermacam-macam komponen background atau latar. Keragaman objek ini memungkinkan intensitas beberapa komponen background memiliki nilai yang sama atau mirip dengan objek utama. Untuk memperkecil kemungkinan tersebut, citra masukan dibagi menjadi empat bagian yang sama besar.
Gambar
18 Contoh hasil segmentasi citra dengan latar belakang kompleks.
Citra dengan pencahayaan seragam Citra dengan pencahayaan seragam merupakan citra yang memiliki pencahayaan seragam untuk setiap bagian citra. Citra jenis ini sebagian besar merupakan anggota dari citra dengan background yang sederhana.
7
Pelabelan pada citra jenis ini baik karena sebagian besar bagian objek utama dan background dapat diinisialisasi dengan baik. kondisi ini disebabkan oleh perbedaan intensitas antara objek utama dan background. Algoritme max flow/min cut pada citra jenis ini memisahkan objek utama dan background pada batas antara keduanya. Pemisahan ini terjadi karena edge penghubung antara objek utama dan background lemah sehingga mudah terputus pada saat update bobot. Hasil segmentasi pada citra jenis ini cukup baik seperti terlihat pada Gambar 19.
Citra dengan keragaman warna objek Citra dengan keragaman warna objek merupakan citra yang memiliki objek utama dengan beberapa warna. Pada citra jenis ini terdapat dua variasi hasil segmentasi. Variasi yang pertama adalah terpisahnya objek utama dan background dengan baik seperti terlihat pada Gambar 21. Variasi kedua adalah terpisahnya sebagian komponen objek utama seperti terlihat pada Gambar 22.
Gambar
Gambar
21 Contoh hasil segmentasi citra dengan keragaman warna objek.
19 Contoh hasil segmentasi citra dengan pencahayaan seragam.
Citra dengan pencahayaan tidak seragam Citra jenis ini memiliki pencahayaan yang berbeda pada beberapa bagian penyusunnya. pada penelitian ini terdapat beberapa citra yang termasuk dalam tipe ini. Citra-citra tersebut sebagian besar memiliki pencahayaan yang berbeda pada bagian kanan dan kiri objek utama. Pelabelan pada citra jenis ini tidak berjalan dengan baik. Hal ini disebabkan oleh intensitas penyusun objek utama dan background memiliki nilai yang hampir sama yang mengakibatkan wilayah background terinisialisasi sebagai objek utama. Kondisi tersebut menyebabkan terdapat kontruksi link yang kuat antara objek utama dan beberapa bagian background. Algoritme max flow/min cut selalu mencari path berdasarkan edge yang paling minimum. Ketentuan ini akan menghasilkan cut pada objek yang memiliki perbedaan intensitas yang besar. Pada citra jenis ini cut terjadi di antara kedua pencahayaan seperti terlihat pada Gambar 20.
Gambar
20 Contoh hasil segmentasi citra dengan pencahayaan tidak seragam.
(a) Gambar
(b)
(c)
22 Citra dengan keragaman warna objek asli (a), citra dengan keragaman warna segmentasi pertama (b) dan citra dengan keragaman warna segmentasi kedua (c).
Pada variasi pertama, pelabelan berjalan dengan baik pada objek utama dan background. Hasil ini disebabkan oleh kemiripan nilai intensitas yang terjadi pada penyusun objek utama maupun background. Pada variasi ini konstruksi link memiliki karakter yang sama dengan konstruksi link citra yang memiliki background sederhana. Untuk konstruksi ketetanggaan, terjadi link yang kuat antara pixel-pixel penyusun objek utama dan background namun terjadi konstruksi yang lemah di batas antara keduanya. Pada variasi kedua, pelabelan tidak berjalan dengan baik. Kondisi ini disebabkan oleh intensitas penyusun objek utama yang memiliki perbedaan nilai yang besar antar komponennya sehingga pelabelan hanya terjadi pada objek yang telah diinisialisasi oleh pengguna. Selain menyebabkan pelabelan yang tidak baik, perbedaan intensitas tersebut mengakibatkan adanya konstruksi link yang lemah antar penyusun objek utama. Konstruksi ini yang menyebabkan cut yang terjadi berada pada batas
8
antara komponen objek utama yang memiliki perbedaan intensitas dan pada sebagian batas antara objek utama dan background. Pengenalan Tahapan pengenalan merupakan tahapan untuk identifikasi dengan menggunakan citra hasil segmentasi. Tahapan ini menggunakan algoritme Local Binary Pattern dengan jenis Rotation invariant uniform pattern (LBPriu2) dan Probabilistic Neural Network (PNN) untuk mengekstraksi fitur citra hasil segmentasi seperti pada penelitian Kulsum (2010). Untuk LBPriu2, sampling point yang digunakan adalah 8, 16 dan 24 dengan radius 1, 2 dan 3 yang digunakan dalam empat operator yaitu LBPriu2(1,8), LBPriu2(2,8), LBPriu2(2,16) dan LBPriu2(3,24). Pada operator LBP, radius menyatakan ukuran blok yang akan digunakan. Untuk radius 1 memiliki ukuran blok 3x3 pixel, radius 2 memiliki blok berukuran 5x5 pixel dan radius 3 memiliki ukuran blok sebesar 7x7 pixel. Sampling point menyatakan jumlah titik yang melingkari titik pusat pada blok. Pada tahapan ini citra yang digunakan berjumlah 240 atau 24 kelas berdasarkan evaluasi visual. Tabel 2 dan Gambar 23 menunjukkan akurasi rata-rata LBPriu2 dari keempat operator. Tabel 2 Akurasi rata-rata LBPriu2 Tanpa Segmentasi
Dengan Segmentasi
LBPriu2 1,8
0.6250
0.70833
LBPriu2 2,16
0.4444
0.66667
LBPriu2 2,8
0.5694
0.69444
LBPriu2 3,24
0.3888
0.58333
Jenis Operator
Gambar 23 Akurasi rata-rata keempat operator LBPriu2. Tabel 2 menunjukkan bahwa LBPriu2(2,8) memiliki akurasi tertinggi dengan persentase sebesar 70.83% pada citra segmentasi. Dari Tabel 2 terlihat bahwa kenaikan akurasi tertinggi terjadi pada operator LBPriu2 dengan sampling point 16 dan radius 2. Secara umum, penggunaan segmentasi pada citra dapat menaikkan akurasi sebesar 8.33% sampai 22.22% pada operator LBPriu2. Namun secara komputasi, penggunaan radius 1 dan sampling point 8 kurang baik walaupun menghasilkan akurasi tertinggi. Hal ini karena radius 1 memiliki ukuran blok 3x3 yang menyebabkan waktu eksekusi ekstraksi menjadi lebih lama dibandingkan radius 2 atau 3 yang memiliki ukuran blok 5x5 dan 7x7 dengan jumlah sampling point yang sama. Oleh karena itu, fokus pembahasan pada sub bab pengenalan hanya difokuskan pada hasil penggunaan operator LBPriu2 dengan sampling point 8 dan radius 2. Operator LBPriu2 dengan sampling point 8 dan radius 2 atau LBPriu2(2,8) memiliki ukuran blok pengolahan sebesar 5x5 sehingga perhitungan ekstraksi akan lebih cepat dan efektif daripada operator lainnya. Hasil akurasi pada operator LBPriu2(2.8) untuk citra tanpa segmentasi terlihat pada Gambar 24.
9
Gambar 26 Citra tanpa segmentasi yang tak teridentifikasi. Pada Gambar 26 terlihat bahwa citra yang tidak dapat teridentifikasi adalah citra dengan backgound kompleks. Hal menunjukkan bahwa kerumitan background akan memengaruhi tahapan pengenalan. Gambar
24
Akurasi LBPriu2(2,8) segmentasi.
tanpa
Hasil pengenalan menggunakan operator LBPriu2(2,8) pada citra tanpa segmentasi memiliki hasil yang kurang baik. Hal ini terlihat pada akurasi rata-rata yang hanya mencapai 56,94%. Namun pada akurasi kelas, terdapat beberapa kelas yang memiliki akurasi sebesar 100% atau dapat teridentifikasi dengan baik. Kelas-kelas tersebut antara lain kelas 2, 4, 6, 8, 15, 17 dan 18. Contoh citra dari kelas-kelas tersebut dapat dilihat pada Gambar 25.
Hasil pengenalan pada citra dengan segmentasi memiliki akurasi rata-rata yang lebih baik dibandingkan dengan akurasi ratarata citra tanpa segmentasi yaitu 70.83%. Untuk akurasi kelas, kenaikan juga terjadi pada sebagian besar kelas seperti terlihat pada Gambar 27.
Gambar 27 Akurasi LBPriu2(2.8) dengan segmentasi. Gambar
25 Citra tanpa segmentasi yang teridentifikasi 100%.
Pada Gambar 25 terlihat bahwa sebagian besar citra tanpa segmentasi yang teridentifikasi dengan baik adalah citra dengan background yang sederhana walaupun terdapat 2 citra dengan background yang kompleks. Selain terdapat citra yang dapat diidentifikasi dengan baik, terdapat kelas yang tidak dapat diidentifikasi atau memiliki akurasi kelas sebesar 0%. Kelas-kelas tersebut antara lain 9, 14 dan 24. Contoh dari citra tersebut dapat dilihat pada Gambar 26.
Pada Gambar 27 terlihat beberapa kelas yang dapat diidentifikasi dengan baik. Kelaskelas tersebut antara lain kelas 1, 2, 3, 5, 6, 9, 10, 13, 16 dan 17. Contoh citra dari kelas-kelas tersebut dapat dilihat pada Gambar 28.
Gambar 28 Contoh citra dengan akurasi 100% menggunakan segmentasi. Pada hasil akurasi kelas untuk citra segmentasi terdapat kelas yang mengalami
10
kenaikan akurasi sebesar 100%. Kelas tersebut adalah kelas yang tidak dapat diidentifikasi tanpa segmentasi yaitu kelas 9. Kelas 9 merupakan citra dengan latar belakang kompleks dengan berbagai macam penyusunnya. Setelah segmentasi, kelas ini dapat teridentifikasi dengan baik dan memiliki akurasi 100%. Hasil akurasi setiap kelas pada Gambar 27 menunjukkan penurunan akurasi beberapa kelas. Kelas-kelas tersebut antara lain kelas 15, 18,21, 22 dan 23. Contoh citra tanpa segmentasi yang mengalami penurunan akurasi dapat dilihat pada Gambar 29.
Gambar
29 Contoh citra tanpa segmentasi dengan penurunan akurasi.
Citra yang mengalami penurunan akurasi adalah citra dengan intensitas yang hampir seragam pada semua penyusunnya. Hal ini mengakibatkan konstruksi link akan memiliki nilai yang hampir sama untuk semua link. Konstruksi tersebut akan mengakibatkan terjadinya cut pada tempat yang tidak semestinya. Hal ini akan mengakibatkan hasil segmentasi dan hasil pengenalan kurang baik. Contoh hasil segmentasi pada beberapa kelas tersebut terlihat pada Gambar 30.
Saran Pada hasil segmentasi yang kurang baik, dapat dilakukan perbaikan pada sistem segmentasi dengan menambahkan wilayah terminal source dan sink secara dinamis. DAFTAR PUSTAKA Annisa. 2009. Ekstraksi ciri morfologi dan tekstur untuk temu kembali citra helai daun [skripsi]. Bogor: Departemen Ilmu Komputer, Institut Pertanian Bogor. Boykov Y, Jolly M-P. 2001. Interactive graph cut for optimal boundary & region segmentation of object in N-D image. International Conference on Computer vision 1:377-384. Boykov Y, Kolmogorov V. 2004. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. Pattern Analysis and Machine Intelligence. IEEE Transactions 26:1124–1137. Boykov Y, Kolmogorov V. 2001. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. International Workshop on Energy Minimization Method in Computer Vision and Pattern Recognition. Springer-Verlag 2134:359-374. Chartrand G, Oellermann OR. 1993. Applied Algorithmic Graph Theory. New York: McGraw-Hill, Inc. Han J, Ma KK. 2002. Fuzzy Color Histogram and Its Use in Color Image Retrieval. IEEE Transaction on Image Processing, vol. 11, no. 8, 2002.
Gambar 30 Contoh citra segmentasi dengan penurunan akurasi. KESIMPULAN DAN SARAN Kesimpulan Penelitian ini menerapkan metode Boykov and Kolmogorov max flow/ min cut graph untuk melakukan segmentasi pada citra tanaman hias. Metode ini dapat digunakan dengan baik pada citra yang memiliki perbedaan intensitas yang besar antara objek utama dan background. Pada penelitian ini hasil evaluasi terbaik ditunjukkan operator LBPriu2(2.8) dengan akurasi sebesar 69.44%. Pada operator ini akurasi meningkat sebesar 12.5% dari akurasi citra tanpa segmentasi.
Kebapci H, Yanikoglu B, Unal Gozde. Plant Image Retrieval Using Color and Texture Feature. Sabanci University, Faculty of Engineering and Natural Science, 2008. Kulsum, Lies Umi. 2010. Identifikasi tanaman hias secara automatis menggunakan metode Local Binary Descriptor dan Probabilistic Neural Network [skripsi]. Bogor: Departemen Ilmu Komputer, Institut Pertanian Bogor. Mc Andrew. 2004. Digital Image Processing with Matlab. Australia : Victoria University. Ramadhani. 2009. Ekstraksi Fitur Bentuk dan Venasi Citra Daun dengan Pemodelan Fourier dan B-Spline [skripsi]. Bogor: Departemen Ilmu Komputer, Institut Pertanian Bogor.
11
