aplikasi minimum weight spanning tree pada implementasi

4
Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) ISSN: 2089-9815 Yogyakarta, 10 Maret 2012 132 APLIKASI MINIMUM WEIGHT SPANNING TREE PADA IMPLEMENTASI ALGORITMA SEGMENTASI CITRA BERBASIS GRAPH Victor Hariadi 1 , Aris Sofan Lutfianto 2 1,2 Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Gedung Teknik Informatika, Kampus ITS, Jl. Raya ITS, Sukolilo, Surabaya-60111 email: [email protected] ABSTRAKS Makalah ini mengagas sebuah skema penyelesaian permasalahan segmentasi citra melalui pendeteksian faces/regions/kurva tertutup. Kami membuat predikat-predikat untuk mengidentifikasi batas antar region yang bersinggungan pada sebuah citra dengan menggunakan representasi berbasis graph. Kemudian kami aplikasikan sebuah algoritma segmentasi yang efisien berbasiskan predikat tersebut (yang walaupun dalam aplikasinya algoritma ini seringkali bersifat greedy, namun secara umum tetap dapat memenuhi kebutuhan penyelesaian permasalahan). Kami mengaplikasikan algoritma berbasis graph terhadap permasalahan segmentasi citra ini dengan menggunakan 2 model ketetanggaan yang berbeda untuk membangun graph. Salah satu karakteristik penting dalam penelitian ini adalah kemampuan algoritma ini dalam mengenali detil dalam citra yang berkategori low-variability regions, dan sebaliknya dapat mengabaikan detail gambar (yang tidak perlu) dalam citra yang berkategori high-variability regions. Kata kunci: segmentasi citra, faces/regions, algoritma berbasis graph,low-variability regions, high-variability regions 1. PENDAHULUAN Segmentasi citra merupakan langkah awal untuk proses analisa citra yang bertujuan untuk mengambil informasi yang terdapat di dalam suatu citra. Segmentasi citra dilakukan dengan mempartisi atau membagi sebuah citra ke dalam bagian-bagian atau objek-objek dengan batasan-batasan tertentu. Sampai sejauh mana pembagian tersebut dilakukan akan sangat bergantung pada masalah yang dihadapi. Idealnya, langkah segmentasi tersebut dihentikan pada saat objek yang diinginkan sudah berhasil dipisahkan. Langkah ini akan menentukan berhasil atau tidaknya proses analisa citra. Sampai sejauh ini belum tersedia teknologi yang dapat melakukan segmentasi secara otomatis. Namun jika kita dapat mengembangkan metode segmentasi yang efektif, maka sangat mungkin kita dapat memperoleh hasil yang baik. Dalam sudut pandang yang berbeda, segmentasi citra dapat dikatakan sebagai suatu teknik membagi sebuah citra menjadi wilayah-wilayah yang homogen berdasarkan kriteria keserupaan yang tertentu antara tingkat keabuan suatu piksel dengan tingkat keabuan piksel–piksel tetangganya, kemudian hasil dari proses segmentasi ini akan digunakan untuk proses ke tingkat lebih lanjut yang dapat dilakukan terhadap suatu citra, misalnya proses klasifikasi citra dan proses identifikasi objek. Sejauh ini telah dikembangkan begitu banyak metode segmentasi citra. Namun penelitian- penelitian yang bertujuan menemukan metode baru atau yang bertujuan memperbaiki kinerja metode tertentu juga mash banyak dilakukan hingga saat ini. Dan salah satunya adalah penelitia ini yang akan memanfaatkan pendekatan teori graph dalam proses segmentasi citra. Metode ini bekerja dengan mendefinisikan sebuah predikat untuk menentukan evidence dari sebuah batas antara dua region dengan menggunakan representasi citra berbasis graph. Selanjutnya kita dapat mengembangkan sebuah algoritma segmentasi yang efisien berdasarkan predikat ini, dan menunjukkan bahwa meskipun algoritma ini bersifat greedy, namun algoritma ini tetap dapat menghasilkan segmentasi yang memenuhi ciri-ciri globalnya. Algoritma berbasis graph yang dikembangkan ini dapat bekerja dengan cepat, hampir linier dengan jumlah dari graph edge. Karakteristik penting dari metode ini adalah kemampuannya dalam menyimpan detail region pada citra yang bersifat low-variability dan mengabaikan detail dari region citra pada high-variability. 2. DASAR TEORI Ada banyak sekali literatur yang membahas segmentasi dan clustering, lebih dari 30 tahun, dengan berbagai aplikasi pada berbagai area selain computer vision. Pada bagian ini kami akan membahas beberapa subset graph yang relevan dengan penelitian ini. Beberapa topik graph tersebut antara lain adalah: minimum spanning tree dan metode graph-based. Sementara beberapa teori algoritma lain yang penting adalah: algoritma greedy dan format citra PPM. Minimum Spanning Tree (MST) adalah algoritma yang bertujuan untuk mencari jumlah edge terkecil dari sebuah connected graph, dimana dengan jumlah edge tersebut dapat mempertahankan graph tersebut tetap dalam kondisi connected. Syarat lain yang harus dipenuhi adalah subgraph yang dihasilkan berbentuk tree atau acyclic. Sebuah graph dapat memiliki banyak spanning tree. Sebuah

Upload: phungnhan

Post on 22-Jan-2017

216 views

Category:

Documents


2 download

TRANSCRIPT

Page 1: aplikasi minimum weight spanning tree pada implementasi

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) ISSN: 2089-9815 Yogyakarta, 10 Maret 2012

132

APLIKASI MINIMUM WEIGHT SPANNING TREE PADA IMPLEMENTASI ALGORITMA SEGMENTASI CITRA BERBASIS GRAPH

Victor Hariadi1, Aris Sofan Lutfianto2

1,2Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Gedung Teknik Informatika, Kampus ITS, Jl. Raya ITS, Sukolilo, Surabaya-60111

email: [email protected]

ABSTRAKS Makalah ini mengagas sebuah skema penyelesaian permasalahan segmentasi citra melalui pendeteksian faces/regions/kurva tertutup. Kami membuat predikat-predikat untuk mengidentifikasi batas antar region yang bersinggungan pada sebuah citra dengan menggunakan representasi berbasis graph. Kemudian kami aplikasikan sebuah algoritma segmentasi yang efisien berbasiskan predikat tersebut (yang walaupun dalam aplikasinya algoritma ini seringkali bersifat greedy, namun secara umum tetap dapat memenuhi kebutuhan penyelesaian permasalahan). Kami mengaplikasikan algoritma berbasis graph terhadap permasalahan segmentasi citra ini dengan menggunakan 2 model ketetanggaan yang berbeda untuk membangun graph. Salah satu karakteristik penting dalam penelitian ini adalah kemampuan algoritma ini dalam mengenali detil dalam citra yang berkategori low-variability regions, dan sebaliknya dapat mengabaikan detail gambar (yang tidak perlu) dalam citra yang berkategori high-variability regions.

Kata kunci: segmentasi citra, faces/regions, algoritma berbasis graph,low-variability regions, high-variability regions

1. PENDAHULUAN

Segmentasi citra merupakan langkah awal untuk proses analisa citra yang bertujuan untuk mengambil informasi yang terdapat di dalam suatu citra. Segmentasi citra dilakukan dengan mempartisi atau membagi sebuah citra ke dalam bagian-bagian atau objek-objek dengan batasan-batasan tertentu. Sampai sejauh mana pembagian tersebut dilakukan akan sangat bergantung pada masalah yang dihadapi. Idealnya, langkah segmentasi tersebut dihentikan pada saat objek yang diinginkan sudah berhasil dipisahkan. Langkah ini akan menentukan berhasil atau tidaknya proses analisa citra. Sampai sejauh ini belum tersedia teknologi yang dapat melakukan segmentasi secara otomatis. Namun jika kita dapat mengembangkan metode segmentasi yang efektif, maka sangat mungkin kita dapat memperoleh hasil yang baik.

Dalam sudut pandang yang berbeda, segmentasi citra dapat dikatakan sebagai suatu teknik membagi sebuah citra menjadi wilayah-wilayah yang homogen berdasarkan kriteria keserupaan yang tertentu antara tingkat keabuan suatu piksel dengan tingkat keabuan piksel–piksel tetangganya, kemudian hasil dari proses segmentasi ini akan digunakan untuk proses ke tingkat lebih lanjut yang dapat dilakukan terhadap suatu citra, misalnya proses klasifikasi citra dan proses identifikasi objek.

Sejauh ini telah dikembangkan begitu banyak metode segmentasi citra. Namun penelitian-penelitian yang bertujuan menemukan metode baru atau yang bertujuan memperbaiki kinerja metode tertentu juga mash banyak dilakukan hingga saat ini. Dan salah satunya adalah penelitia ini yang akan memanfaatkan pendekatan teori graph dalam proses segmentasi citra. Metode ini bekerja dengan

mendefinisikan sebuah predikat untuk menentukan evidence dari sebuah batas antara dua region dengan menggunakan representasi citra berbasis graph. Selanjutnya kita dapat mengembangkan sebuah algoritma segmentasi yang efisien berdasarkan predikat ini, dan menunjukkan bahwa meskipun algoritma ini bersifat greedy, namun algoritma ini tetap dapat menghasilkan segmentasi yang memenuhi ciri-ciri globalnya.

Algoritma berbasis graph yang dikembangkan ini dapat bekerja dengan cepat, hampir linier dengan jumlah dari graph edge. Karakteristik penting dari metode ini adalah kemampuannya dalam menyimpan detail region pada citra yang bersifat low-variability dan mengabaikan detail dari region citra pada high-variability.

2. DASAR TEORI Ada banyak sekali literatur yang membahas segmentasi dan clustering, lebih dari 30 tahun, dengan berbagai aplikasi pada berbagai area selain computer vision. Pada bagian ini kami akan membahas beberapa subset graph yang relevan dengan penelitian ini. Beberapa topik graph tersebut antara lain adalah: minimum spanning tree dan metode graph-based. Sementara beberapa teori algoritma lain yang penting adalah: algoritma greedy dan format citra PPM.

Minimum Spanning Tree (MST) adalah algoritma yang bertujuan untuk mencari jumlah edge terkecil dari sebuah connected graph, dimana dengan jumlah edge tersebut dapat mempertahankan graph tersebut tetap dalam kondisi connected. Syarat lain yang harus dipenuhi adalah subgraph yang dihasilkan berbentuk tree atau acyclic. Sebuah graph dapat memiliki banyak spanning tree. Sebuah

Page 2: aplikasi minimum weight spanning tree pada implementasi

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) ISSN: 2089-9815 Yogyakarta, 10 Maret 2012

133

minimum spanning tree atau minimum weight spanning tree adalah sebuah spanning tree dengan weight (bisa berupa jumlah edge atau jumlah bobot edge) yang paling kecil dibandingkan dengan spanning tree yang lain. Jika terdapat sebuah disconnected graph, maka kita dapat menentukan spanning tree untuk masing-masing komponen disconnected graph tersebut. Dan spanning-spanning tree yang berasal dari sebuah disconnected graph kita sebut sebagai spanning forest.

Sedangkan algoritma Greedy adalah algoritma yang mengikuti cara pemecahan masalah metaheuristic dari membuat pilihan lokal optimum di setiap stage dengan harapan dapat menemukan global optimum.

Sebagai contoh, menerapkan greedy strategy ke dalam permasalahan TSP (Travelling Salesman Problem) menghasilkan algoritma seperti berikut, “Pada setiap stage, kunjungi kota yang belum didatangi yang paling dekat dengan kota tempat anda berada sekarang”

Untuk format citra yang digunakan dalam pengujian ini adalah PPM. Citra dengan format PPM ini merupakan bagian dari Netpbm format. PPM format adalah sebutan untuk format citra berwarna yang tidak umum. Perlu diketahui bahwa format ini terkenal karena ketidakefisienannya. Berlebihan pada informasi jumlah warna dimana mata manusia tidak dapat lagi mengidentifikasi dengan benar. Lebih jauh, format ini hanya dapat memberikan sedikit informasi mengenai citra tersebut selain warna dasar yang dimiliki. Sehingga kita harus memasangkan file format ini dengan informasi independen lain untuk mendapatkan hasil yang layak.

3. ALGORITMA GRAPH BASED

SEGMENTATION Terdapat beberapa hal yang perlu kita

dipertimbangkan di dalam menyusun suatu graph-based: a. Bagaimana cara membangun suatu representasi

graph? b. Bagaimana cara memilih titik awal dan titik

akhir pembuatan graph? c. Bagaimana cara menemukan minimum cost-

path? Kita mulai dari membahas bagian pertama, yaitu

representasi graph. Jika G = (V,E) adalah sebuah undirected graph dengan vertex vi V (himpunan elemen yang akan disegmentasikan) dan edge E(vi,vj). Setiap edge memiliki weight w(vi,vj), bukan negatif. Pada kasus segmentasi elemen pada v adalah piksel dan weight dari edgenya adalah nilai dissimilarity antara dua piksel yang terhubung oleh edge tersebut.

Dalam pendekatan graph, sebuah segmentasi S adalah sebuah partisi dari V ke dalam komponen sedemikian hingga tiap komponen C S bersesuaian dengan sebuah komponen yang

terhubung dalam sebuah graph G'=(V,E') dimana E' E. Atau dengan kata lain, segmentasi yang dilakukan diinduksi oleh sebuah subset dari edge dalam E.

Algoritma Graph Based Segmentation ini secara garis besar dapat digambarkan dengan definisi di bawah ini. Definisi 1: Sebuah segmentasi S bisa dikatakan baik jika ada beberapa pasang region C1,C2 S dimana tidak ada evidence untuk sebuah boundary antara keduanya. Definisi 2: Sebuah segmentasi S dikatakan terlalu kasar ketika ada sebuah proper refinement S yang tidak baik. Properti 1: Untuk tiap (finite) graph G = (V,E) akan terdapat beberapa segmentasi S yang mungkin terlalu kasar maupun terlalu halus. Algoritma 1: Input adalah sebuah graph G = (V,E) dengan n vertex dan m edge. Outputnya adalah segmentasi dari V ke dalam komponen S = (C1,...,Cr) 1. Sort E ke dalam π = (01,...,0m) dengan non-

decreasing edge weight; 2. Mulai dengan sebuah segmentasi S0, dimana

setiap vertex vi ada dalam komponennya; 3. Ulangi langkah 3 untuk q = 1,...,m; 4. Bangun Sq given Sq-1; 5. Return S = Sm.

Teorema 1: Segmentasi S yang dihasilkan oleh algoritma 1 tidak akan didapatkan hasil yang sangat baik jika menggunakan definisi 1. Teorema 2: Segmentasi S yang dihasilkan oleh algoritma 1 tidak akan didapatkan hasil yang sangat baik jika menggunakan definisi 2. Teorema 3: Segmentasi yang dihasilkan oleh algoritma 1 tidak akan bergantung pada non-decreasing weight order dari weight yang digunakan.

4. HASIL UJI COBA

Dalam tahap uji coba kami melalukan banyak pengujian terhadap citra sampel. Pengujian dengan banyak sampel ini bertujuan untuk mendapatkan informasi mengenai perubahan parameter-parameter yang dibutuhkan untuk menghasilkan boundary. Contoh citra sampel yang digunakan adalah citra seperti di bawah ini.

Gambar 1. Sample Citra Uji Coba

Page 3: aplikasi minimum weight spanning tree pada implementasi

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) ISSN: 2089-9815 Yogyakarta, 10 Maret 2012

134

Pengujian pertama menggunakan nilai parameter uji coba (sigma=0.1, threshold=500, component=20) akan memberikan hasil citra sebagai berikut:

Gambar 2. Hasil Citra Uji Coba

Pengujian kedua menggunakan nilai parameter uji coba (sigma=0.7, threshold=500, component=20) akan memberikan hasil citra sebagai berikut:

Gambar 3. Hasil Citra Uji Coba

Pengujian ketiga menggunakan nilai parameter

uji coba (sigma=2, threshold=500, component=20) akan memberikan hasil citra sebagai berikut:

Gambar 4. Hasil Citra Uji Coba

Pengujian keempat menggunakan nilai parameter

uji coba (sigma=2, threshold=300, component=20)

akan memberikan hasil citra sebagai berikut:

Gambar 5. Hasil Citra Uji Coba

Pengujian kelima menggunakan nilai parameter

uji coba (sigma=2, threshold=700, component=20) akan memberikan hasil citra sebagai berikut:

Gambar 6. Hasil Citra Uji Coba

Pengujian keenam menggunakan nilai parameter

uji coba (sigma=2, threshold=2000, component=20) akan memberikan hasil citra sebagai berikut:

Gambar 7. Hasil Citra Uji Coba

Pengujian ketujuh menggunakan nilai parameter

uji coba (sigma=2, threshold=500, component=80) akan memberikan hasil citra sebagai berikut:

Page 4: aplikasi minimum weight spanning tree pada implementasi

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) ISSN: 2089-9815 Yogyakarta, 10 Maret 2012

135

Gambar 8. Hasil Citra Uji Coba

Pengujian kedelapan menggunakan nilai

parameter uji coba (sigma=2, threshold=500, component=200) akan memberikan hasil citra sebagai berikut:

Gambar 9. Hasil Citra Uji Coba

Pengujian kesembilan menggunakan nilai

parameter uji coba (sigma=2, threshold=500, component=500) akan memberikan hasil citra sebagai berikut:

Gambar 10. Hasil Citra Uji Coba

4. Kesimpulan

Berdasarkan hasil pengujian segmentasi citra dengan menggunakan metode graph based ini

dihasilkan nilai batasan untuk mengoptimalkan kinerja algoritma. Dimana nilai parameter tersebut meliputi: nilai sigma, nilai threshold citra, dan nilai komponen.

Diharapkan, nilai batasan yang telah didapatkan tersebut akan mampu melakukan deteksi obyek pada citra dengan tingkat akurasi yang cukup signifikan.

Hasil pada beberapa pengujian yang telah dilakukan di atas dapat memberikan kesimpulan, bahwa semakin tinggi nilai sigma untuk proses smoothing citra, maka akan semakin rendah nilai komponen yang dihasilkan, sehingga akan makin terasa kurang realistis terhadap pengenalan obyek yang ada pada citra.

Sedangkan untuk nilai threshold citra, semakin tinggi nilai threshold yang ditentukan, maka akan semakin rendah pula nilai komponen yang dihasilkan. Hal ini dikarenakan threshold yang digunakan untuk mengontrol derajat perbedaan antar komponen harus lebih besar dibanding perbedaan yang terdapat dalam komponen yang sedang dibandingkan.

PUSTAKA Baris Sumengen, B. S. Manjunath, and David J.

Kriegman., “Graph Partitioning Active Contours (GPAC) forImage Segmentation”, Department of Electrical and Computer Engineering University of California, Santa Barbara, CA,2004.

Bob Fisher, “Graph Methods”, Department of Artificial Intelligence-University of Edinburgh, 2003.

Matei Mancas, Bernard Gosellin, Benoit Macq, “Segmentation Using a Region Growing Thresholding,” Faculté Polytechnique de Mons, Circuit Theory and Signal Processing Laboratory Bâtiment MULTITEL/TCTS-Initialis, 1, avenue Copernic, B-7000, Mons, Belgium, 2005.

Netpbm, “PPM Image Format Specification”, Online Posting, 3 October 2003, http://netpbm.sourceforge.net/doc/ppm.html#description.

Pedro F. Felzenszwalb, Daniel P. Huttenlocher, “Efficient Graph-Based Image Segmentation,” Artificial Intelligence Lab-Massachusetts Institute of Technology, Computer Science Department, Cornell University, IEEE, 2004.

Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman , Angela Y. Wu “An Efficient k-Means Clustering Algorithm: Analysis and Implementation”, Department of Computer Science, University of Toronto, Canada, 2002.

Wikipedia, “Segmentation – Image Processing”, Online Posting, 2 Januari 2008, http://en.wikipedia.org/wiki/Segmentation_(image_processing)