Kata kunci : Pemilihan gambar, Pencocokan Graph

ALGORITMA PENCOCOKAN OBJEK GEOMETRI CITRA BERBASIS GRAPH UNTUK PEMILIHAN KEMBALI (RETRIEVAL) Yureska Angelia – 2208100671

Email : [email protected] Bidang Studi Telekomunikasi Multimedia Jurusan Teknik Elektro-FTI, Institut Teknologi Sepuluh Nopember (ITS) Kampus ITS, Keputih – Sukolilo, Surabaya 60111 Abstrak - Metode graph banyak digunakan dalam proses pencocokan, salah satunya adalah dengan pencocokan citra. Dalam proses pencocokan graph atau graph matching biasanya akan ditemukan banyak kesulitan dalam algoritma yang dilakukan. Banyaknya proses dan prosedur yang harus dilakukan sehingga membuat lamanya juga komputasi dalam proses pencocokan graph untuk pemilihan gambar kembali (Image retrieval). Untuk itu, dibuatlah sebuah algoritma baru yang lebih sederhana untuk melakukan proses pencocokan citra dengan metode graph. Algoritma ini akan mengurutkan proses pencocokan dalam beberapa phase atau K phase, setiap phase akan menjelaskan solusi yang berbeda. Dengan kemungkinan bagian yang paling mendekati benar akan diutamakan dalam proses pencariannya. Hanya selisih jumlah yang kecil dalam phase yang akan digunakan untuk proses pencocokan citra (paling optimal). Dalam pengujian ini digunakan sebuah aplikasi dalam bentuk objek geometri yang akan digunakan sebagai pencocokan untuk pemilihan gambar kembali atau content-based image retrieval. Dari pengujian algoritma untuk pemilihan objek ini, hasil pemilihan akan menghasilkan kecocokan dengan menampilkan objek-objek geometri. Dengan tetap menampilkan dissimilarity objek dalam hasil proses pemilihan kembali Kata kunci : Pemilihan gambar, Pencocokan Graph I.

PENDAHULUAN Dalam dasar pengolahan citra terdapat 3 pengolahan citra, yaitu: grafika komputer, visi komputer dan pengolahan citra. Dalam bidang grafika computer banyak dilakukan proses yang bersifat sintesis yang mempunyai ciri data masukan berbentuk deskriptif dengan keluaran hasil proses berbentuk citra. Sedangakan untuk visi computer merupakan proses kebalikan dari grafika computer. Selanjutnya untuk pengolahan citra merupakan prosees pengolahan dan analisis citra yang banyak melibatkan persepsi visual, yakni data masukan maupun data keluarannya berbentuk citra. Pengenalan citra struktur pola masuk dalam kategori visi computer. Dalam proses pengolahannya, membandingkan citra yang terlebih dahulu akan diubah dalam struktur pola yang kemudian akan membentuk penggambaran pola-pola citra sebaik mungkin, selanjutnya akan digunakan untuk mencocokan citra dengan tujuan mengetahui efisiensi metode pencocokan citranya. Metode yang akan digunakan dalam pengenalan citra struktur pola ini adalah dengan metode graph. Metode graph ini mengkodekan image content ke dalam bentuk graph yang nantinya akan dibedakan dalam bentuk saja. Dalam pengkodean graph ini pencarian image yang digunkan adalah metode content-based image retrieval (CBIR), juga dikenal dengan query by image content (QBIC)

Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI-ITS

yang mana ini termasuk dalam aplikasi teknik visi computer. Selanjutnya, query image yang berfungsi sebagai image input akan menginisialisasi content-base untuk selanjutnya akan mencari maksimum kecocokan. Untuk itu, dibuat sebuah algoritma sederhana untuk proses graph matching. Proses pencocokan dalam algoritma ini akan digunakan system K phase, yang mana K akan bernilai 1 jika memiliki nilai paling kecil dalam selisih dua node. Efisiensi hasil dari algoritma ini didapat dari nilai terkecil K, sehingga secara signifikan akan mengurangi ruang pencarian proses pencocokan diantara dua graph[1]. II. TEORI PENUNJANG 2.1 Content-Based Image Retrieval Content-based image retrieval (CBIR) adalah suatu teknik pencarian suatu data gambar atau citra yang diinginkan oleh pengguna terhadap beberapa data citra dalam skala yang besar. CBIR juga biasa dikenal sebagai query by image content (QBIC). “Content-based” maksudnya adalah pencarian yang akan menganalisa bagian-bagian (content) dari citra lebih dari metadata seperti kata kunci, pelabelan, dan deskripsi dari citra tersebut. Content disini lebih merujuk ke dalam bentuk warna, bentuk, texture atau informasi lainnya yang dapat diambil dari image itu sendiri. Dalam mesin pencarian citra, CBIR hanya menggunakan bagian-bagian yang paling penting dalam citra, jadi tidak hanya murni dalam metadata yang biasanya cara ini akan menghasilkan banyak sampah di akhir pencariannya. Selain itu dalam jumlah data base yang besar, metadata akan sangat tidak efisien, mahal dan kemungkinan menangkap setiap kata kunci yang tidak pas. Dengan CBIR sistem akan bisa menyaring citra berdasarkan content yang tersedia dalam bentuk index dan menghasilkan hasil yang lebih akurat. Gambaran umum CBIR pada Gambar 2.1[2]

Gambar 1 Alur umum CBIR 2.2 Teknik Query Banyak sistem CBIR yang telah dikembangkan, meskipun tidak semua permasalahan dapat terselesaikan.

Salah satu metode yang ada adalah teknik query. CBIR sistem menggunakan bagian-bagian yang terpenting dalam mengidentifikasikan citra yang akan di panggil. Untuk mencari suatu data citra akan banyak sekali kata kunci yang akan dimasukan, sehingga akan membuat beratnya kinerja komputer dalam mencari citra yang sesuai dengan yang diinginkan. Untuk itu, CBIR sistem saat ini membuat suatu fitur yang lebih ringan seperti pengidentifikasian dengan tekstur, warna, dan bentuk. Namun, tidak semua sistem bisa menggunakan CBIR sistem, khususnya sistem yang mangggu. Sebuah citra yang terukur jaraknya membandingkan kesamaan dua citra dalam dimensi yang berbeda seperti warna, texture, bentuk dan lainnya.

Gambar 2 Tiga bidang yang berkaitan dengan citra

2.2.1 Warna Pencarian dengan menggunakan pengukuran berdasarkan kesamaan warna adalah dengan memasukannya ke dalam histogram untuk setiap citra yang di identifikasikan dengan piksel secara proposi ke dalam bentuk nilai sehingga bisa dibaca oleh manusia sebagai warna

2.2.2 Teksture Pengukuran teksture untuk mencari pola visual di citra dan bagaimana untuk mendefinisikan spasial nya. Teksture digambarkan dengan texels yang kemudian ditetapkan dalam bentuk angka, selanjutnya tergantung berapa banyak teksture yang terdeteksi pada citra. Ketetapan ini tidak hanya mendeteksi teksture, tapi juga lokasi teksture dalam citra tersebut.

2.2.3 Bentuk Bentuk tidak hanya merujuk ke dalam bentuk citra tapi dalam penerapannya merupakan region atau wilayah yang menjadi pemecahannya. Bentuk biasanya akan digambarkan dalam bentuk segmentasi atau jarak yang terdeteksi di sebuah citra.

Gambar 3 isomorfik G1 dan G2 2.4 Dasar-Dasar Graph Secara umum, graph G didefinisikan sebagai pasangan himpunan (V,E), ditulis dengan G= (V, ε) yang dalam hal ini V adalah himpunan tidak kosong dari simpulsimpul (nodes) dan ε adalah himpunan sisi/busur (edges) yang menghubungkan sepasang simpul.

2.4.1 Graph Isomorphism Graph dikatakan isomorphism apabila dua buah graph yang sama tetapi secara geometri berbeda. Dua buah graph, G1 dan G2 akan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya sedemikian sehingga hubungan keberisian tetap terjaga. Penjelasan untuk graph isomorphism dapat diberikan pada Gambar 3 di atas. Dalam matriknya dapat dijelaskan sebagai berikut

2.3 Pengertian Pengolahan Citra Pada dasarnya ada tiga bidang yang menangani pengolahn data berebentuk citra, yaitu: grafika computer, pengolahan citra, dan visi computer. Pada bidang grafika computer banyak dilakukan proses yang bersifat sintesis yang mempunyai ciri data masukan berbentuk deskriptif dengan keluaran hasil proses yang berbentuk citra. Sedangkan proses di dalam bidang visi komputer merupakan kebalikan dari proses grafika computer. Terakhir, bidang pengolahan citra merupakan proses pengolahan dan analisis citra dengan data masukan maupun data keluarannya berbentuk citra. Pengolahan citra merupakan proses pengolahan dan analisis citra yang banyak melibatkan persepsi visual. Pengolahan citra bertujuan memperbaiki kualitas citra agar mudah diinterprestasi oleh manusia atau mesin (dalam hal ini computer). Teknik-teknik pengolahan citra mentranformasikan citra menjadi citra lain. Jadi, masukannya adalah citra dan keluarannya juga citra. Namun, citra keluaran mempunyai kualitas lebih baik daripada citra masukan Hubungan antara ketiga bidang tersebut ditunjukan pada Gambar 2.[3]


III. PERANCANGAN DAN PEMBUATAN SISTEM 3.1 Perancangan Dalam sebuah graph matching dengan proses image retrieval, hal pertama adalah perlu membuat sebuah citra database untuk dapat diubah ke dalam bentuk graph secara efisien. Dalam kinerja sebuah graph matching, akan terbagi menjadi dua bagian kinerja[4]: 1. Membuat database yang kemudian merubah image ke dalam bentuk graph 2. Membuat algoritma matching untuk memilih kembali citra yang sama. Sebelum membahas algoritma yang akan dirancang, maka dapat dilihat blok diagram secara keseluruhan dari pengukuran kesamaan graph matching. Gambar 4 berikut proses penjelasan blok diagram.

3 2.5

Input image

Ekstraksi ciri

Proses identifikasi graph

Panggil database

2 1.5 1 0.5 0 -0.5

perbandingan Output image matching

-1 -1

-0.5

0

0.5

1

1.5

2

2.5

3

Gambar 8 Query image yang akan diteliti

Gambar 4 Blok diagram proses simulasi

Gambar 5 Blok diagram proses simulasi keseluruhan 3.2 Pembuatan Sistem Gambaran umum image retrieval adalah[5]:

Objek dalam gambar ini akan berfungsi sebagai query image atau bagian-bagian image yang diidentifikasi sebagai node yang ditandai dengan penomoran. Dalam image content, gambar dibuat dalam 10 database yang bervariasi. Setiap objek gambar memiliki nilai sendiri-sendiri sebagai identifikasi node. Yang mana nilai yang ditetapkan pada masing-masing objek gambar tersebut akan menjadi kunci utama dari proses image matching ini. Berikut penomoran yang diberikan pada masing-masing image content. • persegi_besar = 1 • persegi_kecil = 2 • segitiga = 3 • seitiga_siku2 = 4 • polygon = 5 parameter • luas maximum persegi kecil persegi_kecil = 0.5 Dalam pemrograman ini, proses matching dilakukan dengan cara mencari selisih terkecil antara node di G1 dan G2. Seperti yang telah diterangkan pada pemberian lebel diatas. Maka akan ada lima buah label node. Penjelasan lengkapnya dapat dilihat pada gambar 9 berikut.

Gambar 6 Data masukan yang mencari gambar yang mirip Inisialisai ciri gambar sebagai berikut:

3.4 Image Process dengan Teori Garph Berdasarkan teori yang ada, proses image matching diatas juga dapat dijelaskan secara manual. Pelabelan image content menjadi bentuk graph berdasarkan teory dapt dijelaskan dengan dua cara yaitu dengan tiga node dan empat node. 3.4.1 Implementasi Untuk 3 node

Untuk pertama adalah membuat algoritma matrik yang diatur menjadi pij = d(μ1(v1), μ2(vj)). Berikut pemetaan yang dilakukan pada gambar 10. Gambar 7 Pemilihan bagian gambar 3.3 Objek Citra yang Diteliti Dalam proses pembuatan gambar, objek diisi 3 gambar dalam bentuk, warna, dan posisi yang berbeda-beda. Beberapa gambar dibawah adalah image content yang akan diteliti. 2.5

2

1.5

Gambar 9 Gambar yang dicari dan ditemukan

1

0.5

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2


1

2

1

1

3

1

2

2

3

Pada row ke-3 posisi kecocokannya adalah {(1G1,3G2), (2G1,3G2), (3G1,1G2)} dengan matching error adalah 1+1+1= 3

3

2

3

Berdasar dari tabel matrik yang terakhir maka akan didapat pemetaan node yang sederhana, yang mana merepresentasikan pemetaan dengan kesamaan terbaik. Untuk itu dapat dibuat tabel berikut:

Gambar 10 Input graph G1 dan model graph G2

Pemetaan

Tabel 6 kemiripan terbaik Matching error

(1,1) (2,2) (3,3)

Berdasarkan dari proses K phase maka langkah pertama adalah membuat matrik P, yang mana ini merupakan selisih dari tiap node disetiap baris matrik.

0

3.4.1 Implementasi Untuk 3 node ke 4 node Tabel 1 Matrik P 0

2

1

2

0

1

1

1

0

Dalam pemetaan kali ini, node akan mencari node output lebih besar dibanding dengan node di graph ke-1. Berikut penjelasannya.

Tabel 2 Matrik B phase 1 1

1

0

2

1

0

2 2

0

1

0

0

0

1

1

3

Dalam phase 2, matrik B dan B’ akan dibuat dalam langkah iterasi 1

0

1

1

0

1

0

1

0

0

1

0

0

0

1

0

0

Tabel 4 Matrik B step 2/phase 2 dan matrik B’ step 2 phase 2 1

1

0

1

0

0

1

0

1

1

0

0

1

0

0

1

4

2 3

Tabel 7 Matrik P 1 1 0 2

0 1

1

2

1


0

1

1

0

1

0

0

1

0

1

1

1

0

0

1

0

1

0

Setelah itu, matrik diatas diubah ke dalam bentuk biner dengan memberikan nilai 1 untuk selisih terkecil. Maka didapat matrik yang baru seperti berikut. Nilai terkecil pada tiap row adalah langkah pertama yang diambil, jadi bagian ini disebut dengan matrik B/ phase 1.

0

Pada row ke-2 posisi kecocokan denga nilai terkecil kedua adalah {(1G1,3G2), (2G1,3G2), (3G1,3G2)} dan jumlah selisih error adalah 1+1+0= 2.


2

Dapat dibuat dalam selisih di matrik adalah sebagai berikut:

Best matching {(1G1,3G2), (2G1,2G2), (3G1,3G2)} dan didapat selisih error adalah 1+0+0 = 1

0

3

Gambar 11 Dua graph G1 dan G2

1

1

1

3

3


4

Tabel 8 Matrik B/ phase 1 0 0

1

0

1

0

0

0

0

1

0

Berdasarkan table diatas didapat kecocokan dengan nilai selisih terkecil adalah {(1G1,4G2), (2G1,2G2), (3G1,3G2)} dan jumlah total match adalah 0+0+0 = 0 Dalam phase 2, matrik B dan B’ akan dibuat dalam langkah iterasi 1

Tabel 9 Matrik B step 1/phase 2 dan matrik B’ step 1 phase 2 0 1 0 1 0 1 0 0 0 0

1

0

0

1

0

0

1

0

0

0

0

0

1

0

dapat dipetakan {(1G1,2G2), (2G1,2G2), (3G1,3G2)} dan jumlah total matching 1+0+0 = 1 Tabel 10 Matrik B step 2/phase 2 dan matrik B’ step 2 phase 2 0 1 0 1 0 1 0 1 0

0

0

1

0

1

0

1

0

0

1

0

0

0

1

0

Langkah kedua ini, nilai row ke-2 yang memiliki nilai terkecil urutan 2 adalah {(1G1,2G2), (2G1,4G2), (3G1,3G2)} dan jumlah selisih yang terjadi adalah 1+1+0 = 2 Tabel 11 Matrik B step 3/phase 2 dan matrik B’ step 3 phase 2 0 1 0 1 0 1 0 1 0

1

0

1

0

1

0

1

1

0

0

0

1

0

1

0

Langkah ke-3 matriks yang dianggap matching {(1G1,2G2), (2G1,4G2), (3G1,1G2)} dan didapat matching error 1+1+1 = 3 Untuk mendapatkan kecocokan yang maksimal, selalu dimungkinkan untuk memperhitungkan untuk jumlah selisih yang cukup besar. Maka dalam phase selanjutnya ini adalah menghitung untuk nilai terkecil ke-3 seperti langkahlangkah sebelumnya. Phse 3, matrik B dan B’ sama seperti langkah sebelumnya pada langkah 1.

Tabel 12 Matrik B step 3/phase 3 dan matrik B’ step 3 phase 3 0 1 1 1 0 1 1 1 0

1

1

1

0

1

1

1

0

0

0

1

1

0

1

1

Pemetaannya adalah {(1G1,3G2), (3G1,4G2)} dengan nilai error 1+2+1 = 4

IV.PENGUJIAN DAN ANALISA SISTEM 4.1 Hasil Pengujian Gambar Berdasarkan Bentuk Dalam percobaan ini digunakan gambar 2D dengan berbagai macam bentuk bangun dan ciri. Pencarian dimulai memasukan query image sebagai data masukan, untuk dilanjutkan dengan proses inisialisasi mencari gambar sama terbaik diantara banyaknya database. Ketidaksamaan warna dan posisi tidak menjadi parameter penting disini. Dalam pengujian ini query image tidak termasuk dalam anggota dari data base itu sendiri.

4.1.2 Pemilihan Gambar dengan 3 Node Dalam pencarian gambar kembali ini, ada 5 gambar yang digunakan yaitu: • Persegi besar berlabel 1 • Persegi kecil berlabel 2 • Segitiga berlabel 3 • Segitiga siku berlabel 4 • Polygone berlabel 5 Berikut hasil dari pengujian pencarian gambar kembali dengan 3 node. Query Input

Gambar 2 , Error 0

3

3

2

2

1

1

0

0

-1 -1

-1 -1

0

1

2

3

Gambar 1 , Error 1

Tabel 12 Matrik B step 1/phase 3 dan matrik B’ step 1 phase 3 0 0 1

0 1 0

1 0 1

0 1 0

0 0 1

1 1 0

1 0 1

1 1 0

(2G1,3G2),

0

1

2

3

Gambar 3 , Error 2

3

3

2

2

1

1

0

0

-1 -1

-1 -1

0

1

2

3

0

1

2

3

Gambar 12 Hasil uji pencarian gambar kembali Matrik B pada table di atas memberikan 4 kecocokan yaitu, {(1G1,3G2), (2G1,2G2), (3G1,1G2)}, {(1G1,3G2), (2G1,4G2), (3G1,1G2)}, {(1G1,3G2), (2G1,2G2), (3G1,2G2)}, {(1G1,3G2), (2G1,4G2), (3G1,2G2)} dan didapat matching error maksimum pada pemetaan ke-4 dg nilai 1+1+2=4 Tabel 13 Matrik B step 2/phase 3 dan matrik B’ step 2 phase 3 0

1

1

1

0

1

1

1

Query Input 3

3

2

2

1

1

0

0

11

11

3

0 1

0 0

1 1

0 0

0 1

1 0

1 1

{(1G1,3G2), (2G1,3G2), (3G1,1G2)} dengan nilai 1+2+1 = 4


1 0

0

1

2

3

Gambar 1 , Error 1

3

2

2

1

1

0

0

11

11

0

1

2

3

Gambar 2 , Error 0

0

1

2

3

2

3

Gambar 3 , Error 1

0

1

Gambar 13 Hasil uji ke-2 pencarian gambar kembali

Query

Gambar 2 , Error 1

3

3

2

2

1

1

0

0

-1 -1

0

1

2

3

5.1 Kesimpulan

-1 -1

0

Gambar 4 , Error 2 3

2

2

1

1

0

0 0

1

2

1

2

3

Gambar 1 , Error 1

3

-1 -1

V. PENUTUP

3

5.2 Saran

-1 -1

0

1

2

3

Gambar 14 Hasil uji pencarian gambar kembali untuk 3 ke 4 node Query Input

Gambar 2 , Error 2

3

3

2

2

1

1

0

0

-1 -1

0

1

2

3

Berdasarkan hasil pengujian yang dilakuan pada Tugas Akhir ini, perbandingan kesamaan query image pada image processing dengan metode graph, dapat disimpulkan bahwa: 1. Terdapat beberapa kesamaan yang akurat dalam proses pencocokan citra ini, yaitu dalam bentuk dari isi gambar 2. Faktor ukuran gambar tidak berpengaruh pada semua bentuk objek citra. 3. Dalam proses pencarian kembali, penampilan matching error berurutan sesuai error terkecil.

-1 -1

0

1

2

3

Beberapa saran yang berguna untuk pengembangan Tugas Akhir ini antara lain: 1. Untuk penelitian selanjutnya system dapat dikembangkan dengan memperhitungkan posisi dan warna dari image content. 2. Pengujian dapat dikembangkan dengan kuantitas database yang lebih banyak. 3. Factor waktu dapat diperhitungkan dalam proses pencarian gambar. DAFTAR PUSTAKA

Gambar 4 , Error 1 3

3

2

2

1

1

0

0

[1]

[2] -1 -1

0

1

2

3

-1 -1

0

1

2

3

Gambar 14 Hasil uji pencarian gambar kembali untuk 3 ke 4 node

4.2 Analisa pengujian

1 2

Matching error gambar ke-1 0 0



Nilai matching error didapat dari selisih node antar graph yang telah dilabel sebelumnya. Begitu juga dengan proses pencocokan dengan 3 node ke 4 node, algoritma akan mencari gambar yang paling banyak mirip dengan input query image. Tabel 15 Nilai matching error 3 node ke 4 node dalam pengujian Query Matching Matching Matching Image error gambar error gambar error gambar ke-1 ke-2 ke-3 1 1 2 1 2

2

[4]

[5]

Tabel 14 Nilai matching error 3 node dalam pengujian Query Image

[3]

1

1

Berdasarkan dari hasil pengujian diatas terjadi beberapa ketidakcocokan dari hasil akhir dengan keterangan gambar. Hal ini masih dikarenakan belum sempurnanya program yang dibuat. Namun secara keseluruhan bahwa algoritma ini bisa digunakan dalam proses Graph matching.


A. hlaoui and S. Wang, “A node-maping-based algorithm for graph matching,”Universite de sherbrooke, quebec, Canada. Aniati Murni dan Suryana Setiawan. “ Pengatur Pengolahan Citra”, PT. Elex Media Komputindo Rinaldi Munir. “Matematika Diskrit”. Informatika Bandung. Bandung. 2003 A. Hlaoui and S. Wang, “A New Algorithm for Graph Matching With Application to Content-based image retrieval,” in SSPR/SPR, 2002 P. Dasigi and C.V. Jawahar, “Efficient Graph-based Image Matching for Recognation and Retrieval,” Center for Visual Information Technology, IIIT Hyderabad

BIODATA PENULIS Yureska Angelia, dilahirkan di Bangka 28 April 1987, merupakan anak kedua dari tiga bersaudara pasangan Yudawi dan Lihyati. Memulai pendidikan Sekolah Dasar di SDN 63 Belinyu, kemudian meneruskan pendidikan di SLTP Negeri 3 Belinyu dan SMA Negeri 1 Pemali. Pendidikan terakhir di Elektronik Instrumentasi bidang studi instrumentasi UGM. Sekarang sedang mengerjakan tugas akhir di Bidang Studi Telekomunikasi Multimedia, Jurusan Teknik Elektro ITS Surabaya. Email: [email protected]

Kata kunci : Pemilihan gambar, Pencocokan Graph

Recommend Documents