Seminar Nasional Ilmu Komputer dan Teknologi Informasi 2003
PERBANDINGAN PERFORMANCE IMAGE MATCHING MENGGUNAKAN KESAMAAN LANGSUNG DAN KESAMAAN SETELAH SEGMENTASI NANA RAMADIJANTI, ACHMAD BASUKI Jurusan Teknologi Informasi – Lab Image Processing Politeknik Eletronika Negeri Surabaya ITS Institut Teknologi Sepuluh Nopember Surabaya Kampus PENS-ITS, Keputih, Sukolilo, Surabaya 60111, Indonesia Email :
[email protected],
[email protected]
ABSTRAK Salah satu tahapan yang harus dilalui pada sistem image retrieval adalah proses matching diantara citra query dengan citra pada database. Metode matching yang digunakan pada proses image retrieval dapat menpengaruhi hasil citra yang akan ditampilkan dalam hal kemiripannya dengan citra query. Pada paper ini metode matching yang akan dibandingkan dan diamati hasilnya adalah metode matching berdasarkan perhitungan kesamaan langsung dan matching yang didahului segmentasi citra thresholding pada citra gray level query dengan citra gray level database. Nilai kemiripan diantara citra query dengan citra database dihitung dari ratarata selisih dari citra query dengan citra databse terhadap nilai 1. Dari data sample citra berjumlah 180 diantara bermacam-macam kelas citra yang ada didapatkan bahwa kedua metode matching langsung dan matching dengan segmentasi dapat menghasilkan nilai kemiripan citra query dengan citra database 100% pada citra yang persis sama. Sedangkan pada citra yang mirip dengan citra query diharapkan metode matching yang didahului proses segmentasi biner dapat memberikan hasil yang lebih baik dibandingkan metode matching berdasarkan pengukuran kesamaan secara langsung. Kata Kunci : citra query, citra database, matching dengan kesamaan langsung, matching segmentasi, nilai kemiripan
1.
PENDAHULUAN Pada bidang komputer vision, teknik matching menjadi salah satu metode yang digunakan pada banyak aplikasi di bidang pattern recognition, dan yang lebih luas lagi di bidang content based image retrieval untuk menampilkan citra yang mirip dengan citra query, yang kemudian digunakan untuk pencarian data berbasis image. Proses matching dilakukan untuk mencari ada tidaknya ciri suatu obyek citra query pada citra database. Metode matching yang baik mempunyai nilai kemiripan yang tinggi untuk citra yang query yang mirip dengan citra database dan nilai kemiripan yang kecil untuk citra query yang berbeda dengan citra database. Metode untuk mendapatkan nilai similarity yang sesuai dengan kemiripan citra berdasarkan kelasnya merupakan permasalahan tersendiri, yang membutuhkan perbandingan beberapa metode matching yang terbaik.
Metode matching langsung dan metode matching dengan segmentasi adalah metode matching yang banyak digunakan pada system pencocokan pola, untuk mendapatkan hasil yang baik pada proses berikutnya, nilai similarity dari dua metode matching ini akan dibandingkan pada beberapa kelas citra yang terdapat pada citra database.
2. DETEKSI
DAN
PENCOCOKAN
CITRA Plate matching, adalah salah satu metode dasar deteksi dan pencocokan citra. Metode ini membandingkan obyek pada plate dengan unknown obyek pada suatu citra dan memperhatikan bahwa obyeknya adalah obyek yang sama dengan yang ada di plate. Penggunaan proses plate matching, plate discaning pada citra
Seminar Nasional Ilmu Komputer dan Teknologi Informasi 2003
target dan diukur derajat kemiripannya sesudah posisinya digeser. Kemiripan didefinisikan sebagai nilai hubungan R(u,v). Misalkan ukuran plate adalah N1xN2 dan ukuran citra target adalah M1xM2. F(i,j) adalah nilai gray level
N
R
(u
,v
N
∑ ∑
)=
1
i=1
⎡ ⎢ ⎣
N
N
∑ ∑ 1
i=1
2
2
T
j =1
2
T
citra pada titik (i,j) yang discaning. T(k,l) adalah nilai gray level plate pada titik (k,l). Dan hubungan (correlation) diantara semuanya adalah :
(u
)F (i
,v
+ u , j + v
)
j =1
⎤ (i , j )⎥ ⎦
1 2
⎡ ⎢ ⎣
N
N
∑ ∑ 1
i=1
2
j =1
F
2
⎤ (i + u , j + v )⎥ ⎦
1 2
Ekspresi persamaan R(u,v) dalam matrik: T
R (u , v) =
T • F u ,v T
1 2 2
Nilai terbesar dari correlasi adalah 1, yang muncul hanya selama pencocokan diantara plate dan citra target persis sama. Pada kenyataannya, nilai correlasi biasanya kurang dari 1 karena noise pada citra dan pengaruh perubahan obyek plate atau rotasi. R(u,v) adalah nilai yang terbesar hanya pada
1 Ds (u, v ) = N1 N 2
F u ,v
1 2 2
kasus yang paling besar kemiripannya diantara citra obyek dengan citra plate. Dua jenis metode perhitungan ketidaksamaan yaitu algoritma mean square distortion (MSD) dan algoritma mean absolution distortion (MAD). Algoritma MSD : 2
N1 N 2
∑∑ [F (i + u, j + v ) − T (i, j )] i =1 j =1
Algoritma MAD :
Da (u , v ) =
1 N1 N 2
∑∑ F (i + u, j + v ) − T (i, j )
Perbedaan pada hasil perhitungan ketika obyek sub citra dicocokkan dengan plate, dari nilai R(u,v) dan Da(u,v) atau Ds(u,v). R(u,v) adalah nilai terbesar, Da(u,v) dan Ds(u,v) adalah nilai terkecil. Algoritma MSD dan MAD menyatakan perbedaan diantara sub- citra dengan plate, karena itu, dia menjadi minimum.. Jika Da(u,v) lebih kecil dari nilai threshold pada posisi (u,v) = La. Apabila nilai threshold La dapat dinyatakan menurut hasil sebenarnya, idealnya
pencocokan yang cepat diberikan. Ketika nilai ketidakcocokan lebih besar dibanding La selama proses akumulasi titik diantara sub citra dan plate, perhitungan dihentikan dan mulai pada scaning citra posisi berikutnya. Dan metode ini disebut serangkaian algoritma deteksi kemiripan (sequence similar detection algorithm).
Seminar Nasional Ilmu Komputer dan Teknologi Informasi 2003
3. 1. PROSES MATCHING LANGSUNG Pada pencocokan langsung ini, akan dikerjakan dengan tahapan : 1. Masukan adalah citra query yang akan dicari kemiripannya diantara sekumpulan database citra. Citra query diwakili dengan F(i,j), Ukuran citra query nx * ny. 2. Proses berikutnya citra query berwarna kita konversi dahulu ke dalam citra gray level 3. Tahap berikutnya citra gray level dirubah lagi ke dalam bentuk citra biner, dengan alasan penyederhanaan proses komputasi. Proses binarisasi dilakukan dengan global threshold dari citra If F(i,j) ≥ Th then FB(i,j) = 1 If F(i,j) < Th then FB(i,j) = 0
4. Setelah mendapatkan matrik citra biner dari citra query, kita ulangi lagi langkah nomer 2 dan 3 pada masing-masing citra database. Citra database ini di wakili dengan T(i,j) If T(i,j) ≥ Th then TB(i,j) = 1 If T(i,j) < Th then TB(i,j) = 0
5. Hitung nilai perbedaan diantara dua citra citra query dan satu citra pada database menggunakan MAD. Semakin mirip citra database dengan citra query maka nilai perbedaannya akan kecil atau minimal Beda = ∑∑ FB(i + u, j + v ) − TB(i, j )
6. Dari nilai perbedaan selanjutnya dihitung nilai kesamaannya (similaritynya) dengan mengurangkan dengan 1 (nilai kesamaan yang maksimum) Similarity =
(1 − Beda ) nx * ny
7. Ulangi pada keseluruhan citra database proses nomer 4 sampai dengan nomer 6.
3. 2. PROSES MATCHING SEGMENTASI Pada pencocokan langsung ini, akan dikerjakan dengan tahapan : 1. Masukan adalah citra query yang akan dicari kemiripannya diantara sekumpulan database citra. Citra query diwakili dengan F(i,j) 2. Proses berikutnya citra query berwarna kita konversi dahulu ke dalam citra gray level Similarity =
(1 − Beda ) nx * ny
3. Lakukan proses segmentasi dengan membagi lebar dan tinggi citra query dengan 8, sehingga area citra yang akan dibandingkan menjadi lebih besar mx =
nx 8
dan
my =
ny 8
4. Nilai area citra per delapanan ini diwakili dengan nilai rata-rata gray level dari seluruh area perdelapanan ini 8
8
∑∑ F (i, j ) FMean(n1,n2) =
i =1 j =1
n1 * n2
5. Tahap berikutnya citra gray level yang sudah disegmentasi per delapanan area dirubah lagi ke dalam bentuk citra biner, dengan alasan untuk penyederhanaan proses komputasi. Proses binarisasi dilakukan dengan global threshold dari citra If FMean(i,j)≥Th then FB(i,j)= 1 If FMean(i,j)
|
6. Setelah mendapatkan matrik citra biner dari citra query, kita ulangi lagi langkah nomer 2 dan 3 pada masing-masing citra database. Citra database ini di wakili dengan T(i,j) 8
8
∑∑ T (i, j ) TMean(n1,n2) =
i =1 j =1
n1 * n2
If TMean(i,j)≥Th then TB(i,j)= 1 If TMean(i,j)
|
7. Hitung nilai perbedaan diantara dua citra citra query dan satu citra pada database menggunakan MAD. Semakin mirip citra database dengan citra query maka nilai perbedaannya akan kecil atau minimal Beda = ∑∑ FB(i + u, j + v ) − TB(i, j )
8. Dari nilai perbedaan selanjutnya dihitung nilai kesamaannya (similaritynya) dengan mengurangkan dengan 1 (nilai kesamaan yang maksimum) 9. Ulangi pada keseluruhan citra database proses nomer 6 sampai dengan nomer 8.
Seminar Nasional Ilmu Komputer dan Teknologi Informasi 2003
4. HASIL PERCOBAAN Data citra yang digunakan pada percobaan ini adalah sejumlah 180 citra non texture dan 100 citra texture. Pengamatan dilakukan dari citra sejenis, citra yang beragam, dari masing-masing metode matching berdasarkan kesamaan langsung dan
a)
metode matching setelah dilakukan proses segmentasi baru dihitung kesamaan. Perhatikan gambar 1 sampai dengan gambar 4 sebagai contoh hasil yang didapatkan.
b)
Gambar 1. a) Citra Asli b) Citra Biner Hasil Matching - Hasil Retrieve Citra Dengan Metode Matching Langsung ( Citra bertanda adalah Citra Query, dan Nilai yang ditampilkan adalah nilai kemiripan - similarity – Citra database menggunakan citra yang mirip dengan citra query)
a)
b)
Gambar 2. a) Citra Asli b) Citra Biner Hasil Retrieve Citra Dengan Metode Matching Segmentasi ( Citra bertanda adalah Citra Query, dan Nilai yang ditampilkan adalah nilai kemiripan - similarity – Citra database menggunakan citra mirip dengan citra query)
Seminar Nasional Ilmu Komputer dan Teknologi Informasi 2003
a)
b)
Gambar 3. a) Citra Asli b) Citra Biner Hasil Retrieve Citra Dengan Metode Matching Langsung ( Citra bertanda adalah Citra Query, dan Nilai yang ditampilkan adalah nilai kemiripan - similarity – Citra database dan citra query menggunakan citra texture)
a)
b)
Gambar 4. a) Citra Asli b) Citra Biner Hasil Retrieve Citra Dengan Metode Matching Segmentasi ( Citra bertanda adalah Citra Query, dan Nilai yang ditampilkan adalah nilai kemiripan - similarity – Citra database dan citra query menggunakan citra texture) 5. KESIMPULAN Berdasarkan hasil percobaan pada beberapa citra non tekstur dan citra tekstur dapat disimpulkan sebagai berikut : • Metode matching langsung maupun matching didahului segmentasi dapat mengenali citra query dengan nilai similarity 1.
6. DAFTAR PUSTAKA [1]Gonzales, “Digital Image Processing”,Addison Wesley Publishing Company,1993
[2] G.J. Awcock and R.Thomas, “Applied Image Processing”, MacGraw-Hill 1996 [3] John Eakins,Margaret Graham, “Contentbased Image Retrieval : A Report to the JISC Technology Applications Program”l, University of Northumbria at Newcastle,October 1999
• Tidak terdapat perbedaan yang signifikan pada perbandingan hasil nilai similaritynya baik matching langsung maupun matching dengan didahului proses segmentasi. • Penggunaan citra biner dapat menyederhanakan proses komputasi pada saat matching. Lebih sederhana lagi pada saat citra biner yang terbentuk didahului proses segmentasi.
[4] J.R. Parker, “Algorithms For Image Processing and Computer Vision”, Wiley Computer Publishing,1997 [5] Luo Qiang,Ren Qingli, Luo Li, Luo Jingti, “Genetic Algorithm Used on the Image Detecting and Matching”,Xidian University [6]http://amazon.ece.utexas.edu/~qasim/sample_q ueries.htm: database citra non tekstur [7]http://sipi.usc.edu/services/database: database brodatz citra texture
