Pencocokan Citra Berbasis Graph untuk Pengenalan dan Pemilihan Kembali (Retrieval) Oleh: Yureska Angelia (2208100671) Dosen Pembimbing Dr. Ir. Wirawan, DEA
Latar Belakang • Teknik pemodelan struktur graph telah digunakan sebagai cara untuk penggambaran pola dan pengklasifikasian sejak tahun 1970an. • Dalam image matching, penggunaan metode graph dapat menghasilkan proses yang lebih efisien. Sehingga baik digunakan untuk sistem pemanggilan gambar kembali atau content based image retrieval (CBIR) sistem.
Rumusan Masalah • Penerapan metode graph dalam image content untuk selanjutnya membandingkan query image dengan data base gambar
Batasan Masalah • Analisa dilakukan dengan melakukan pencarian citra melalui metode graph • Proses pencocokan gambar adalah dengan pola gambar yang diidentifikasi sebagai node untuk mengetahui maksimum matching image. • Node yang digunakan pada proses image matching adalah maksimal 4 node • Identifikasi graph tidak dipengaruhi edge • Objek gambar tidak dipengaruhi warna dan posisi
Tujuan • Tujuan penelitian tugas akhir ini adalah untuk menunjukan bahwa algoritma dengan metode graph ini bisa memilih kembali citra yang sama berdasarkan variasi bentuk yang diinginkan. • dapat membandingkan kinerja hasil pencocokan gambar setelah dipilih kembali beradasarkan data yang ada.
Graph Matching • Graph biasa digunakan sebagai penggambaran abstrak untuk bagaian-bagian yang komplek. • Apabila dua buah objek dicocokkan sebagai permasalahan pencocokan graph maka objekobjek tersebut diubah menjadi G=(V,E). • G adalah graph yang terbentuk atas kecocokan node-node V yang dihubungkan oleh garis E.
Graph Isomorphism
Content Based Image Retrieval •CBIR adalah teknik pencarian suatu data gambar atau citra yang dinginkan •“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 akan lebih merujuk dalam warna, bentuk, dan teksture •Digunakannya sistem CBIR ini adalah untuk mendapatkan hasil yang maksimal tanpa banyak menghasilkan hasil akhir yang tidak penting
Image retrieval Gambar yang dicari Data masukan yang mencari gambar yang mirip
2.5
2
1.5
1
0.5
Ekstraksi gambar
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
Gambar yang ditemukan
2
Pelabelan gambar =1
=2
=3
=4
=5
Ket gambar : 1. persegi besar 2. persegi kecil 3. segitiga 4. segitiga siku-siku 5. polygone
Diagram Alir Algoritma Call new matching G1 =(V1,E1)
Query input
G2=(V2,E2)
Matrik nxm dibuat pada matrik Pij
Langkah 1 inisialisasi Pij
2.5
model Graph Data base
2
1.5
Matrik kedua nxm matrik Bij
1
0.5
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
Gambar 2 , Error 0
Query Input
3 2 1 0 -1 -1
0
1
2
3
3 2 1 0 -1 -1
3
3 2 1 0 -1 -1
Gambar 1 , Error 1
3 2 1 0 -1 -1
0
1
2
Langkah 2 inisialisasi B dengan diatur bij=0
0
1
2
3
Gambar 3 , Error 1
0
1
2
3
Hasil akhir daftar matching
Langkah 3 bagaian utama K phase
K phase Simpan matching error terkecil. set B’=1
Phase 1, set bij=1 dari matrik P terkecil
Tabel.1 Matrik B phase 1 langkah 1
Phase 2, set bij=1 untuk nilai terkecil ke-2 dari matrik P
Tabel.2 Matrik B’ phase 2 langkah 1
0
0
1
1
0
1
0
1
0
0
1
0
0
0
1
0
0
1
Simpan matching error terkecil. set B’=1
Simpan matching error terkecil. set B’=1
Phase n, set bij=1 untuk nilai terkecil ke-n matrik P
Ilustrasi pemetaan 3 node ke 3 node 1
2
3
3
1
1
Tabel. 2 matrik B phase 1
1
2
3
2 3
G2
G1 Tabel.1 matrik P
2
1
0
0
0
1
0
0
0
1
Tabel.3 Matrik B phase 2 langkah 1 0
0
1
0
2
1
0
1
0
2
0
1
0
0
1
1
1
0
Tabel.4 Matrik B’ phase 2 langkah 1 1
0
1
0
1
0
0
0
1
Tabel.1 matrik P
Tabel.6 Matrik B step 3/phase 2 dan matrik B’ step 3 phase 2
0
2
1
2
0
1
1
1
0
Tabel.5 Matrik B step 2/phase 2 dan matrik B’ step 2 phase 1
0
1
1
0
1
0
0
1
0
1
1
0
0
1
0
0
1
1
0
1
1
0
1
0
1
1
0
1
1
1
0
0
1
0
1
Tabel.7 kecocokan terbaik Pemetaan
Matching error
(1,1) (2,2) (3,3)
0
Ilustrasi Pemetaan Graph 3 node ke 4 node Tabel 2. matrik B phase 1
1
2
1 2
2
1
4
0
0
0
1
0
1
0
0
0
0
1
0
1
Tabel 3. matrik B phase 2 langkah 1
3
3
2 4
0
1
0
0
0
1
0
0
0
0
1
0
3
3
G1
G2 Tabel.1 Matrik P
Tabel 4 Matrik B’ phase 2 langkah 2 0
1
0
1
2
1
1
0
0
1
0
0
3
0
2
1
0
0
1
0
1
2
0
1
Tabel.1 Matrik P 2
1
1
0
3
0
2
1
1
2
0
1
Tabel 7 Matrik B step 2/phase 3 dan matrik B’ step 2 phase 3
Tabel 5 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
Tabel 6 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
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
1
0
1
1
1
1
0
1
0
Tabel 8 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
Image retrieval berdasarkan bentuk Query Input
Gambar 2 , Error 0
3
3
2
2
1
1
0
0
-1 -1
0
1
2
3
-1 -1
Gambar 1 , Error 1 3
2
2
1
1
0
0
0
1
2
1
2
3
Gambar 3 , Error 1
3
-1 -1
0
3
-1 -1
0
1
2
3
Query Input
Gambar 3 , Error 1
3
3
2
2
1
1
0
0
-1 -1
0
1
2
3
-1 -1
Gambar 5 , Error 2 3
2
2
1
1
0
0
0
1
2
1
2
3
Gambar 2 , Error 2
3
-1 -1
0
3
-1 -1
0
1
2
3
Analisa Hasil
Input query Image
1
Gambar 2
2
3
2
0
Gambar 3
1
3
1
0
2
1
1
0
2
0
1
3
1
1
0
2
Gambar 1
4
3
2
0
3
2
1
1
1
0
1
3
2
1
0
2
2
5
0
1
4
1
2
1
4
3
1
0
3
2
Image Retrieval berdasarkan Bentuk untuk Maksimum 4 node
Query Input
Gambar 1 , Error 0
3
3
2
2
1
1
0
0
-1 -1
0
1
2
3
-1 -1
Gambar 10 , Error 1 3
2
2
1
1
0
0 0
1
2
1
2
3
Gambar 7 , Error 3
3
-1 -1
0
3
-1 -1
0
1
2
3
Query Input
Gambar 3 , Error 0
3
3
2
2
1
1
0
0
-1 -1
0
1
2
3
-1 -1
Gambar 6 , Error 1 3
2
2
1
1
0
0
0
1
2
1
2
3
Gambar 10 , Error 2
3
-1 -1
0
3
-1 -1
0
1
2
3
Input query Image
4
Gambar 1
2
5
2
5
Gambar 7
4
3
1
0
1
2
1
3
1
2
3
0
2
1
0
3 Gambar 10
44
3 3 2
24
0
1
2
0
1
2
3
3
2
1
0
2
3
3
3
1
1
1
4
2
2
2
1
1
1
1
Kesimpulan • Dalam pengujian ini terdapat beberapa kesamaan yang akurat dalam proses pencocokan citra ini, yaitu dalam bentuk dari isi gambar • Dalam proses pencarian kembali, penampilan matching error berurutan sesuai error terkecil. • Image retrieval dengan menggunakan perhitungan manual memiliki nilai yang sama dengan yang dihasilkan program.
Terima Kasih
