1
APLIKASI TEMU-KEMBALI POLIGON BERDASARKAN KEMIRIPAN BENTUK
DONY ISNANDI
JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 1999
2
RINGKASAN DONY ISNANDI. Aplikasi Temu-Kembali Poligon berdasarkan Kemiripan Bentuk (Application on Polygon Retrieval based on Shape Similarity). Dibimbing oleh MOHAMMAD NABIL dan ARIF IMAM SUROSO. Retrieval basis data gambar tidak efektif bila dilakukan dengan menggunakan keyword seperti layaknya retrieval basis data teks. Hal ini disebabkan gambar tidak efektif diwakili oleh keyword. Metode yang efektif bagi retrieval gambar adalah retrieval berdasarkan kemiripan. Retrieval ini diharapkan konsisten dengan penglihatan mata manusia, yang diperoleh melalui penghitungan ukuran kemiripan tertentu. ID-Poligon adalah suatu aplikasi yang dapat digunakan untuk membantu manusia dalam melakukan retrieval basis data gambar dengan hanya memasukkan bentuk obyek gambar tersebut. Perbandingan jumlah sudut, kemiripan arah sudut dan kemiripan panjang garis sisi dari dua poligon yang terkait dengan bentuk gambar (tepi obyek) digunakan dalam penghitungan ukuran kemiripan antara keduanya. Hasil ujicoba menunjukkan bahwa retrieval mencapai hasil optimal pada nilai ambang batas presisi 60%.
3
APLIKASI TEMU-KEMBALI POLIGON BERDASARKAN KEMIRIPAN BENTUK
DONY ISNANDI
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Program Studi Ilmu Komputer
JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 1999
4
Judul : Aplikasi Temu-Kembali Poligon Berdasarkan Kemiripan Bentuk Nama : Dony Isnandi N I M : G31.0915
Menyetujui,
Dr. Ir. Mohammad Nabil, M.Sc.
Ir. Arif Imam Suroso, M.Sc. Pembimbing II
Pembimbing I
Mengetahui,
Dr. Ir. Abdurrauf Rambe, M.St. Ketua Program Studi
Tanggal Lulus:
5
RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tanggal 3 Mei 1976 sebagai anak keempat dari enam bersaudara, dari pasangan T. Soeripto Wartaatmadja dan Waliah Hidayat. Tahun 1994 penulis lulus SMA Negeri 1 Bogor dan pada tahun yang sama lulus seleksi masuk IPB melalui jalur Undangan Seleksi Masuk IPB. Penulis kemudian kuliah di Program Studi Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan penulis menjadi asisten pada mata kuliah Fisika Dasar II pada tahun ajaran 1995/1996, mata kuliah Algoritma Pemrograman pada tahun ajaran 1996/1997, mata kuliah Pengenalan Komputer pada tahun ajaran 1996/1997, mata kuliah Bahasa Pemrograman pada tahun ajaran 1996/1997, serta mata kuliah Komunikasi Data dan Jaringan Komputer pada tahun ajaran 1998/1999.
6
PRAKATA Puji dan syukur penulis panjatkan kepada Allah SWT atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih dalam penelitian yang dilakukan sejak bulan Juli 1998 ini ialah retrieval bentuk, dengan judul Aplikasi Temu-Kembali Poligon berdasarkan Kemiripan Bentuk. Terima kasih penulis ucapkan kepada berbagai pihak yang telah membantu penyelesaian karya ilmiah ini, antara lain Bapak Dr. Ir. Mohammad Nabil, M.Sc. dan Bapak Ir. Arief Imam Suroso, M.Sc. selaku pembimbing, Bapak Ir. Julio Adi Santoso, M.Kom yang banyak membantu dalam penyelesaian karya ilmiah ini serta seluruh staf pengajar Program Studi Ilmu Komputer yang telah memberikan bekal ilmu dan wawasan teknologi selama penulis mengikuti perkuliahan di IPB. Ungkapan terima kasih juga disampaikan kepada ayah, ibu, serta seluruh keluarga, atas segala doa dan kasih sayangnya. Semoga karya ilmiah ini bermanfaat.
Bogor, Februari 1999 Dony Isnandi
7
DAFTAR ISI Halaman DAFTAR GAMBAR
............................................................................................................................
v
........................................................................................................................
vi
PENDAHULUAN Latar Belakang ................................................................................................................................ Tujuan Penelitian ............................................................................................................................
1 1
TINJAUAN PUSTAKA Teknik Pengenalan Gambar ............................................................................................................ Poligon ............................................................................................................................................ Keterkaitan-8-tetangga .................................................................................................................... Rantai Kode ..................................................................................................................................... Sistem Evaluasi ............................................................................................................................... Analisis Algoritme ..........................................................................................................................
1 1 1 2 2 2
PERANCANGAN SISTEM Definisi Masalah ............................................................................................................................. Analisis ............................................................................................................................................ Desain Sistem .................................................................................................................................. Implementasi ................................................................................................................................... Pemeliharaan ...................................................................................................................................
3 3 4 6 7
HASIL DAN PEMBAHASAN Nilai Ambang Batas Kemiripan ...................................................................................................... Perbandingan Perlakuan ..................................................................................................................
7 7
KESIMPULAN DAN SARAN Kesimpulan ..................................................................................................................................... Saran ...............................................................................................................................................
8 8
DAFTAR LAMPIRAN
DAFTAR PUSTAKA LAMPIRAN
.........................................................................................................................
10
.......................................................................................................................................
11
8
DAFTAR GAMBAR Halaman 1.
Kode arah keterkaitan-8-tetangga
..................................................................................................
1
2.
Persegi panjang berukuran 7x4
......................................................................................................
2
3.
Diagram Alir Query ID-Poligon
....................................................................................................
4
4.
Rotasi Garis
...................................................................................................................................
5
5.
Contoh perhitungan arah sudut
6.
Grafik recall-precision
......................................................................................................
5
..................................................................................................................
9
9
DAFTAR LAMPIRAN Halaman 1.
Poligon Query
..............................................................................................................................
11
2.
Poligon Pustaka
...........................................................................................................................
12
3.
Poligon Hasil Pemilihan Responden
............................................................................................
15
4.
Poligon Hasil Retrieval ID-Poligon
.............................................................................................
16
1
PENDAHULUAN Latar Belakang Dalam beberapa tahun terakhir ini, telah banyak perkembangan dalam sistem manajemen basis data untuk gambar. Fungsi utama dari sistem manajemen basis data adalah untuk retrieval (menemukan kembali) atau memilih (select) sebagian obyek (atau records) dari basis data yang memenuhi kriteria tertentu. Untuk sistem basis data teks tradisional, penggunakan keyword (kata kunci) cukup untuk melakukan retrieval. Namun, untuk retrieval gambar, penggunaan keyword tidak efektif karena keyword belum tentu mewakili isi gambar tersebut. Metode yang efektif bagi retrieval data gambar adalah berdasarkan isi (content-based retrieval), misalnya retrieval berdasarkan bentuk (shape based retrieval). Dalam retrieval berdasarkan bentuk, gambar query (dicari) terlebih dahulu dianalisis dan diinterpretasikan bentuknya, kemudian dibandingkan dengan gambar dalam database. Perbandingan gambar query dan gambar database menggunakan suatu perhitungan nilai kemiripan (similarity) sehingga gambar database yang di-retrieve mendekati interpretasi pandangan mata manusia. Proses pemilihan atau pengambilan gambar database yang memenuhi nilai kemiripan ini disebut similarity-based retrieval (retrieval berdasarkan kemiripan). Perhitungan nilai kemiripan dapat menggunakan interpretasi bentuk dari gambar query dan gambar database, dan proses retrieval berdasarkan perhitungan ini disebut shape similarity-based retrieval (retrieval berdasarkan kemiripan bentuk). Tujuan Tujuan karya ilmiah ini adalah merancang dan membangun suatu aplikasi retrieval obyek berdasarkan kemiripan bentuk.
TINJAUAN PUSTAKA Teknik Pengenalan Gambar Menurut Mehrotra & Gary (1993), untuk melakukan permintaan pencarian gambar berdasarkan kemiripan, gambar query harus
diproses dan dianalisis untuk diidentifikasikan isinya dan/atau dicari gambar/bagian gambar yang mirip atau sama. Dengan perkataan lain analisis gambar dan interpretasinya harus menjadi komponen strategi yang penting dalam proses pencarian gambar. Baik gambar query maupun yang disimpan harus diproses secara efisien dan diinterpretasikan secara baik. Oleh karena itu harus ada tiga hal penting yang dilakukan dalam merancang teknik pengenalan gambar berdasarkan kemiripan bentuk, yaitu: 1. Representasi bentuk – Representasi digunakan untuk mengatur informasi bentuk dalam struktur indeks bagi retrieval yang efisien. 2. Nilai kemiripan – Untuk menghitung derajat kemiripan bentuk. Sebaiknya nilai ini konsisten dengan penglihatan manusia. 3. Struktur Indeks – Sebuah struktur yang mudah dan efisien namun dapat melakukan penambahan dan penghapusan data gambar selain pencarian gambar yang sama atau mirip. Poligon Poligon digunakan untuk mewakili bentuk obyek gambar dengan cara merepresentasikan tepi obyek (boundary) dengan poligon. Pengenalan obyek gambar dapat dilakukan melalui pengenalan poligon. Poligon adalah bidang datar dengan tiga atau lebih sudut yang dikelilingi oleh sebuah segmen garis lurus yang membentuk sebuah kurva tertutup sederhana (Gullberg 1997). 2 3
1
4
0
5 6
7
Gambar 1. Kode arah keterkaitan-8-tetangga Keterkaitan-8-tetangga Hubungan antara titik-titik sudut dalam poligon digambarkan sebagai bentuk hubungan antara piksel (pixel—picture element) pusat dan piksel tetangga yang dikaitkan dengan pengikatan kode. Jika kita ingin mengaitkan piksel pusat dengan seluruh piksel tetangganya maka kita bekerja pada keterkaitan-8-tetangga
2
(Freeman 1961). Arah pengkodean dengan 8tetangga dapat dilihat pada Gambar 1. Pengaitan antara titik pusat dengan titik lainnya yang jaraknya lebih dari satu piksel dapat dilakukan dengan keterkaitan-8-tetangga juga. Rantai Kode Dalam penyimpanan data dari pengkodean dengan sistem keterkaitan-8-tetangga penting dipertimbangkan efek dari jumlah kode yang selanjutnya berpengaruh kepada perlunya ruang yang besar untuk menyimpannya. Untuk peringkasan data digunakan teknik chain codes atau value point encoding atau rantai kode. Koordinat awal titik direkam dan ditentukan arah pergerakan data (sesuai arah jarum jam atau berlawanan arah jarum jam) yang dalam hal ini diterjemahkan dengan peyimpanan berurutan sesuai arah titik (Freeman 1961). A
4
C
6
2 B
D 0
Gambar 2. Persegi panjang berukuran 7x4 Sebagai contoh, rantai kode untuk Gambar 2 dengan menggunakan kode arah keterkaitan-8arah untuk menentukan arah pergerakan data adalah: 6666000000022224444444 dan dengan menggunakan rantai kode ringkas (compacted chain code), maka rantai kode akan menjadi: (4 6)(7 0)(4 2)(7 4) Bila data disimpan dalam bentuk rantai kode asli, maka dibutuhkan 22 tempat, dan untuk rantai kode ringkas diperlukan 8 tempat. Dengan demikian, rantai kode ringkas lebih baik dari rantai kode biasa karena menghemat tempat. Sistem Evaluasi Metode yang digunakan untuk membandingkan antara hasil retrieval program dengan pandangan manusia adalah dengan menggunakan metode recall-precision-graph (Salton 1989). Metode ini telah digunakan sejak lama untuk mengukur keefektifitan retrieval. Dua
ukuran yang dipakai pada metode ini adalah recall dan precision. Recall adalah proporsi obyek relevan (obyek yang sama dengan pandangan mata manusia) yang di-retrieve dan didefinisikan seperti pada persamaan (1) sedangkan precision adalah proporsi dari obyek di-retrieve yang relevan, yang didefinisikan seperti persamaan (2). Jumlah obyek relevan yang di-retrieve R=
… (1) Jumlah obyek relevan dalam basis data Jumlah obyek relevan yang di-retrieve
P=
… (2) Jumlah obyek yang di-retrieve
Analisis Algoritme Analisis algoritme digunakan untuk memperkirakan waktu (dan kadangkala tempat) yang dibutuhkan oleh sebuah algoritme dalam menyelesaikan suatu masalah (Stinson 1985). Didefinisikan T(n) sebagai waktu yang dibutuhkan oleh suatu algoritme dalam menyelesaikan masalah yang berukuran n. Berdasarkan waktu eksekusi program tersebut dapat diperkirakan laju pertumbuhan dari T(n) yang menunjuk pada kompleksitas algoritme. Kompleksitas algoritme memberikan gambaran yang jelas tentang kecepatan waktu T(n) bereaksi terhadap perubahan n dan tidak tergantung pada implementasi tertentu. Perubahan T(n) yang lebih kecil berarti algoritme tersebut akan lebih cepat, terutama untuk nilai n yang besar. Misalkan f(n) dan g(n) adalah fungsi waktu eksekusi. f(n) adalah Θ(g(n)) jika terdapat bilangan nyata positif c1 dan c2 serta bilangan bulat positif n0 sedemikian sehingga 0 ≤ c1⋅g(n) ≤ f(n) ≤ c2⋅g(n), ∀ n ≥ n0. Selanjutnya, f(n) adalah Ο(g(n)) jika terdapat bilangan nyata positif c dan suatu bilangan bulat positif n0 sedemikian sehingga 0 ≤ f(n) ≤ c⋅g(n), ∀ n ≥ n0. Demikian pula f(n) adalah Ω(g(n)) jika terdapat bilangan nyata positif c dan suatu bilangan bulat positif n0 sedemikian sehingga 0 ≤ c⋅g(n) ≤ f(n), ∀ n ≥ n0.
PERANCANGAN SISTEM Sistem dirancang dengan menggunakan tahapan dalam Siklus Hidup Pengembangan
3
Sistem (System Development Life Cycle). Perancangan dengan tahapan-tahapan yang disediakan berguna untuk membangun sistem secara optimal. Tahapan siklus hidup pengembangan sistem adalah pendefinisian masalah, analisis, desain sistem, implementasi dan pemeliharaan (McLeod 1993). Semua tahapan yang ada saling berhubungan dan memiliki pengaruh besar pada pengembangan sistem. Definisi Masalah Pendifinisian masalah merupakan awal dari tahapan pengembangan sistem. Secara ringkas, masalah yang akan dibahas dalam tulisan ini adalah membangun aplikasi retrieval gambar (poligon) berdasarkan kemiripan bentuk yang harus konsisten dengan penglihatan mata manusia dan cukup efisien. Analisis Analisis sistem berfungsi sebagai jembatan antara alokasi level sistem software dengan desain sistem, yang berguna pada penentuan fungsi dan kinerja sistem. Dari tahapan pendefinisian masalah, hal-hal yang dianalisis adalah representasi bentuk, penentuan fungsi penghitungan nilai kemiripan agar konsisten dengan penglihatan mata manusia, kemudahan penggunaan sistem dan perubahan maupun perbaikan sistem. Penentuan ukuran kemiripan menempati posisi penting dalam analisis, karena fungsi penghitungan nilai kemiripan merupakan inti dari aplikasi pengenalan obyek gambar poligon. Beberapa fungsi yang telah ada dan menjadi bahan pertimbangan antara lain: 1. Tanda kelengkungan (Sign of Curvature) (Scassellati et al. 1994). Dalam metode ini, perbedaan lengkungan antara dua obyek gambar menentukan kemiripan. 2. Teknik Jagadish (Jagadish 1991). Bentuk (hanya bentuk seperti garis lurus yang diperhitungkan) direpresentasikan sebagai sebuah set dari persegi panjang tertutup. Setiap bentuk persegi panjang direpresentasikan sebagai titik dalam ruang berdimensi banyak. Jarak Euclid digunakan sebagai ukuran kemiripan pada saat hipotesis. 3. Sudut belok (Turning Angle) (Scassellati et al. 1994). Representasi bentuk dilakukan dengan memulai pada satu titik tertentu dalam suatu batas pinggir dan menjelaskan
ke arah mana kita akan bergerak dalam batas pinggir tersebut. Untuk sebuah bentuk a, fungsi turning Θa(s) menghitung tangen sudut secara berlawanan arah jarum jam dari beberapa titik referensi dalam batas. Fungsi turning akan menghitung berapa banyak tikungan (turning) yang diperoleh selama kita bergerak sepanjang batas pinggir. Metode tanda kelengkungan bekerja dengan baik pada obyek gambar yang memiliki banyak tonjolan dari pusat obyek gambar, seperti obyek gambar ikan dan manusia. Namun metode ini bekerja dengan buruk pada obyek gambar berupa huruf T dan bentuk persegi panjang yang tidak memiliki tonjolan. Metode ini tidak cocok untuk obyek gambar poligon yang tidak banyak memiliki tonjolan. Teknik Jagadish bekerja baik untuk obyek gambar poligon namun memiliki kelemahan ketika membandingkan dua obyek poligon yang memiliki jarak Euclid sama namun secara bentuk fisik berbeda, seperti jajaran genjang sama sisi dengan bujur sangkar. Metode sudut belok efektif untuk hampir semua obyek gambar. Namun metode ini kurang efektif untuk membandingkan dua obyek poligon yang memiliki panjang sisi sama, karena metode ini hanya menghitung banyaknya tikungan (sudut). Dari ke tiga metode di atas, dipilih metode sudut belok sebagai dasar dan diusulkan perbaikan penentuan ukuran kemiripan dari metode tersebut agar sesuai untuk obyek poligon sebagai berikut: 1. Penghitungan banyaknya sudut, namun berbeda dengan metode sudut belok kita tidak perlu melakukan perhitungan tangen sudut. Penghitungan banyak sudut ini menempati posisi terpenting karena kemiripan banyak sudut menentukan adanya kemiripan bentuk. Obyek gambar yang memiliki banyak sudut berbeda dapat dikatakan tidak mirip. 2. Kemiripan kode arah sudut, digunakan untuk menjelaskan posisi titik sudut dalam obyek gambar dari titik sebelumnya. Untuk penentuan kode arah digunakan kode arah keterkaitan-8-tetangga dan peringkasan kode arah tersebut digunakan metode rantai kode ringkas. 3. Kemiripan panjang garis sisi merupakan tahapan terakhir dari fungsi perhitungan kemiripan yang tidak terlalu penting namun diperlukan untuk memastikan bahwa kedua
4
obyek poligon yang dibandingkan benarbenar mirip satu sama lainnya. Misalkan bujur sangkar dapat dikatakan mirip dengan persegi panjang, namun dengan kemiripan panjang garis sisi dapat ditentukan bahwa antara bujur sangkar dan persegi panjang ada sedikit perbedaan. Desain Sistem Sistem yang dirancang terdiri atas satu program aplikasi, yaitu Aplikasi Retrieval Poligon (ID-Poligon), dan satu file berbasis teks yang berisi data Poligon Pustaka. ID-Poligon dirancang agar mendukung antar muka pengguna yang bersifat query-by-example (QBE). Pengguna dapat menspesifikasikan poligon query dengan menggambarnya di kanvas yang disediakan aplikasi. Setelah poligon query selesai digambar, maka poligon akan di analisis dan di interpretasi oleh aplikasi. Kemudian poligon tersebut diidentifikasi berdasarkan rantai kode dan panjang sisi. Poligon pustaka hasil identifikasi ditampilkan dalam jendela (window) hasil. Sebagai tambahan, jumlah dari poligon pustaka hasil identifikasi dapat diatur dengan memberikan ambang batas (threshold) bagi nilai kemiripan. Poligon pustaka yang memiliki nilai kemiripan lebih tinggi dari ambang batas akan ditampilkan di jendela hasil. Diagram alir (flowchart) query dari aplikasi ini dapat dilihat dengan jelas pada Gambar 3. Pada diagram alir query ini, ID-Poligon disusun atas lima tahap utama yaitu: tahap penggambaran poligon, tahap penyempurnaan poligon, tahap representasi poligon, tahap pembandingan poligon dan tahap output. Tahap Penggambaran Poligon. Pada tahap ini, pengguna menggambar poligon query pada kanvas yang telah disediakan oleh aplikasi dengan menggunakan alat gambar yang disediakan. Penggambaran dilakukan dengan berbasiskan titik. Rangkaian titik pembentuk poligon query digambarkan sebagai rangkaian pointer linked list oleh aplikasi. Aplikasi kemudian menggambar garis-garis yang menghubungkan setiap titik secara berurutan. Analisis algoritme tidak dilakukan pada tahap ini.
Mulai
Penggambaran Poligon Query
Penyempurnaan /Perbaikan Poligon
Representasi Poligon
Pembandingan pustaka dengan query
Nilai Kesamaan lebih dari batas?
Ya Ya
Tampilkan Poligon Pustaka Tidak
Pustaka masih ada?
Tidak
Selesai
Gambar 3. Diagram Alir Query ID-Poligon
5
Tahap Penyempurnaan Poligon. Aplikasi melakukan pemeriksaan terhadap seluruh titik sudut pembentuk poligon query dari adanya dua titik sama berurutan dan melakukan penggambaran ulang poligon. Waktu yang diperlukan untuk proses ini adalah T1a(n) = 5n + 1, dengan n adalah jumlah titik sudut dalam poligon query. Selanjutnya dilakukan pemeriksaan arah rangkaian titik untuk memastikan bahwa arah pergerakan titik berlawanan arah dengan jarum jam. Pemeriksaan dilakukan dengan melakukan rotasi terhadap titik kedua (x2,y2) dan titik ketiga (x3,y3) dengan mengasumsikan titik pertama sebagai titik origin (awal). (xb,yb)
r
r
(x,y)
θ
titik ini terletak di sebelah kiri dari titik rotasi titik kedua maka arah pergerakan titik adalah searah jarum jam dan diperlukan proses pembalikan arah pergerakan. Waktu yang diperlukan mulai dari pengecekan arah hingga proses pembalikan arah pergerakan titik adalah T1b(n) = 5n + 33. Tahap Representasi Poligon. Analisis dan interpretasi poligon query mengacu pada konsep dari metode sudut belok. Representasi titik dan pergerakannya dilakukan dengan kode arah keterkaitan-8-tetangga yang kemudian diringkas dengan metode rantai kode ringkas. Dalam aplikasi ini, rantai kode ringkas dilambangkan dengan kode arah sudut dan panjang garis sisi. Kode arah keterkaitan-8-tetangga diperoleh dengan menggunakan persamaan:
c=
(x',y')
Gambar 4. Rotasi Garis Didefinisikan (xb,yb) sebagai titik awal, (x,y) sebagai titik poligon, θ sebagai besar sudut rotasi, r sebagai jarak Euclid antara titik (xb,yb) dengan (x,y) dan (x’,y’) sebagai titik hasil rotasi, maka persamaan transformasi rotasi (Hearn & Baker 1986) yang digunakan: x' = xb + ( x − xb ) cos θ − ( y − y b ) sin θ ….. (3) y ' = y b + ( y − y b ) cos θ + ( x − xb ) sin θ
Panjang garis r diperoleh dengan menggunakan persamaan (Gullberg 1997):
y …. (6) x
dan membandingkan nilai c dengan nilai tg θ standard. Waktu eksekusi sebanyak T2a(n) = 17n diperlukan untuk memperoleh kode arah dari seluruh garis sisi poligon. Sedangkan panjang garis sisi diperoleh dari persamaan (4) dan memerlukan waktu eksekusi T2b(n) = 7n. Kemudian dilakukan penyatuan dua atau lebih garis yang memiliki kode arah yang sama menjadi satu garis. Secara bersamaan dilakukan perhitungan arah sudut yang dibentuk oleh dua garis yang berbeda kode arahnya (Gambar 5). Kedua proses ini membutuhkan waktu T2c(n) = 11n + 5.
r = ( x − xb ) 2 + ( y − y b ) 2 ….. (4)
3 3
Dan untuk memperoleh nilai θ digunakan rumus trigonometri berikut:
y − y b ….. (5) r
θ = cos −1
Titik kedua dirotasi agar sejajar dengan sumbu y dan terletak di bawah titik pertama (lihat Gambar 4). Dengan menggunakan persamaan (4) dan (5) maka akan diperoleh sudut θ yang diperlukan. Titik rotasi titik ketiga diperoleh dengan menggunakan sudut θ pada persamaan (3). Bila
0
Gambar 5. Contoh perhitungan arah sudut Dengan demikian waktu yang diperlukan untuk menyelesaikan tahap ini adalah T2(n) = T2a(n) + T2b(n) + T2c(n) = 17n + 7n + 11n + 5 = 35n + 5. Tahap Pembandingan Poligon. Pada tahap pembandingan poligon, pustaka poligon yang tersimpan dalam file diambil dan disimpan dalam memori. Kemudian representasi poligon pustaka
6
dibandingkan satu persatu dengan representasi poligon query. Pembandingan ini dilakukan dengan tetap mempertimbangkan kemungkinan adanya transformasi, yaitu: • Skala • Translasi • Rotasi • Atau kombinasi dari dua atau lebih transformasi di atas. dan dihitung nilai kemiripannya. Penghitungan ini harus konsisten dengan interpretasi penglihatan manusia, maka penghitungan harus berdasarkan pada tiga hal, yaitu: • banyaknya sudut • kemiripan kode arah sudut • kemiripan panjang garis sisi Pembandingan banyak sudut digunakan lagi dalam perhitungan nilai pembandingan lainnya. Hal ini dikarenakan kemiripan jumlah sudut dianggap sebagai faktor paling utama dalam penilaian kemiripan poligon berdasarkan bentuknya. Persamaan yang digunakan adalah: jumlah _ sudut _ terkecil …(7) N = 1
jumlah _ sudut _ terbanyak
Sedangkan pembandingan kemiripan kode arah sudut digunakan untuk memastikan bahwa poligon query dan poligon pustaka benar memiliki kemiripan dalam bentuk dan dengan menggunakan persamaan: jumlah _ kode _ sama … (8) N = 2
jumlah _ sudut _ terkecil
Untuk melakukan penghitungan nilai kemiripan panjang garis sisi, digunakan persamaan koefisien korelasi (Flemming & Nellis 1994) berikut:
∑ (x n
N3 =
j =1
∑ (x n
j =1
ij
ij
)(
− x i x kj − x k
− xi
) ∑ (x 2
n
j =1
kj
)
− xk
)
.. (9)
2
Namun apabila seluruh panjang garis sisi nilainya sama atau poligon sama sisi, maka nilai kemiripan panjang garis tidak dapat dihitung dengan menggunakan persamaan (9). Karena itu digunakan persamaan Koefisien Korelasi Pangkat Spearman (Flemming & Nellis 1994) berikut: 1 3 6∑ D 2 + t −t 12 …(10) N3 =1− n n2 −1
(
( )
)
Dari hasil uji-coba sebanyak 100 kali, diketahui nilai kemiripan untuk poligon sama sisi tidak pernah lebih besar dari 10-6 sehingga persamaan (10) dapat diabaikan dan nilai kemiripan untuk poligon sama sisi diperoleh melalui: 1, _ kedua_ poligon _ sama _ sisi
N3 {
0, _ sebaliknya
… (11)
Melalui suatu uji-coba pendahuluan, nilai kemiripan banyak sudut menempati 0,5 dari nilai kemiripan total. Sedangkan nilai kemiripan arah sudut dan nilai kemiripan panjang garis sisi menempati 0,35 dan 0,15 dari nilai kemiripan total setelah dikalikan dengan nilai kemiripan banyak sudut. Dengan demikian nilai kemiripan total diperoleh melalui persamaan berikut: N = ( N1 × 0,5) + (0,35 × N1 × N 2 ) + (0,15 × N1 × N 3 ) … (12) Waktu yang dibutuhkan untuk memperoleh nilai kemiripan ini adalah T3a(n) = 5n+21. Dan dikarenakan nilai kemiripan dihitung untuk seluruh pustaka poligon sejumlah n dan seluruh n kemungkinan transformasi maka total waktu yang dibutuhkan adalah T3(n) = n * n * T3a(n) = 5n3+21n2. Tahap Output. Apabila nilai kemiripan poligon pustaka yang diperoleh pada tahap pembandingan poligon lebih dari nilai batas yang ditetapkan pengguna, maka poligon pustaka dianggap sama dengan poligon query dan ditampilkan pada pengguna. Secara keseluruhan, aplikasi ID-Poligon memerlukan waktu T(n) = T1a + T1b + T2 + T3 = (5n + 1) + (5n + 33) + (35n + 5) + (5n3 + 21n2) = 5n3 + 21n2 + 40n + 39 dan waktu eksekusi O(n3) untuk mengenali satu poligon query. Implementasi Aplikasi ID-Poligon diimplementasikan dengan menggunakan perangkat lunak Borland Delphi 3.0. Perangkat lunak ini dipilih karena memiliki pustaka komponen visual (visual component library – VCL) yang cukup banyak dan memudahkan pengimplementasian aplikasi ini. Bahasa pemograman dasar perangkat lunak ini adalah object Pascal (Pascal berorientasi obyek) yang merupakan pengembangan dari bahasa Pascal. Bahasa Pascal merupakan bahasa yang sangat dipahami penulis, dan menjadi alasan utama mengapa perangkat lunak ini dipilih. ID-Poligon dirancang untuk bekerja di bawah sistem operasi Windows 9x. Spesifikasi minimal
7
sistem komputer yang dianjurkan agar IDPoligon berjalan baik adalah: prosesor 80486DX2-66MHz, RAM 8 MB, monitor VGA 256 warna, mouse dan memiliki sisa ruang hard disk minimal 2 MB.
dengan poligon pustaka yang memiliki nilai kemiripan antara 70%-80%. Begitu seterusnya hingga ambang batas 0% berarti menampilkan seluruh poligon pustaka yang dimiliki aplikasi. Perbandingan Perlakuan
Pemeliharaan Agar sistem dapat terus memenuhi kebutuhan pemakai, perlu adanya pengembangan. Perbaikan maupun pengembangan sistem dilakukan dengan mengkaji kembali tahapan-tahapan dalam siklus hidup pengembangan sistem.
HASIL DAN PEMBAHASAN Untuk membandingkan aplikasi ID-Poligon ini dengan pandangan mata manusia. Sebuah kuisioner yang berisi tujuh poligon query yang berbeda bentuk seperti ditampilkan pada Lampiran 1 dan 70 poligon pustaka yang tercantum pada Lampiran 2 telah dibagikan kepada 30 orang responden dari berbagai tingkatan umur dan pendidikan. Responden diminta untuk memilih satu atau lebih poligon pustaka yang dianggap mirip dengan ke-tujuh poligon query. Poligon hasil pemilihan responden kemudian digabungkan dan hasilnya dapat dilihat pada Lampiran 3. Ketujuh poligon query yang diberikan pada responden kemudian dicobakan pada ID-Poligon dengan menggunakan berbagai perlakuan dan hasil retrieval-nya dapat dilihat pada Lampiran 4. Hasil yang diperoleh dari responden kemudian dibandingkan dengan hasil retrieval dari ID-Poligon, memberikan tingkat keragaman hasil retrieval seperti yang dicantumkan dalam tabel recall-precision pada Tabel 1. Nilai Ambang Batas Kemiripan Nilai Ambang Batas Kemiripan (Similarity Threshold) bertindak sebagai pembatas untuk jumlah poligon hasil yang ingin ditampilkan kepada pengguna. Pada tahap pembandingan poligon, setiap poligon pustaka diberi nilai kemiripan terhadap poligon query. Apabila nilai kemiripan poligon pustaka lebih besar dari ambang batas, maka poligon pustaka tersebut akan ditampilkan kepada pengguna. Poligon pustaka yang dihasilkan oleh ambang batas 70% akan meliputi poligon pustaka yang dihasilkan oleh ambang batas 80% ditambah
Perlakuan I. Nilai Ambang Batas Kemiripan untuk aplikasi ID-Poligon ditetapkan pada 40%. Dari Tabel 1, dapat dilihat bahwa nilai precision untuk Perlakuan I ini merupakan terendah dibandingkan perlakuan lain untuk setiap tingkatan recall. Dalam Perlakuan I, seluruh poligon pustaka yang dianggap mirip oleh responden baru dapat di-retrieve pada tingkat recall 0,3 dengan nilai precision 0,61. Tabel 1. Rata-rata nilai recall-precision dari 7 poligon query yang dicobakan Precision Recall I II III IV V 0.1 0,90 0,93 1 1 1 0.2 0,75 0,89 1 1 1 0.3 0,61 0,79 0,90 1 1 0.4 0,48 0,71 0,85 0,93 1 0.5 0,38 0,62 0,79 0,93 1 0.6 0,32 0,53 0,75 0,89 0,93 0.7 0,27 0,45 0,72 0,87 0,93 0.8 0,24 0,38 0,67 0,83 0,93 0.9 0,21 0,33 0,62 0,79 0,93 1.0 0,18 0,29 0,55 0,76 0,93 Perlakuan II. Nilai Ambang Batas Kemiripan aplikasi ditetapkan sebesar 50%. Pada perlakuan ini, sebagian besar poligon pustaka yang diretrieve oleh ID-Poligon dan mengganggu nilai relevansi telah banyak berkurang. Sehingga terjadi peningkatan nilai precision untuk setiap tingkat recall. Sedangkan seluruh poligon pustaka yang dianggap mirip oleh responden dapat di-retrieve pada tingkat recall 0,4 dengan nilai precision 0,71. Perlakuan III. Nilai Ambang Batas Kemiripan aplikasi ditetapkan sebesar 60%. Pada perlakuan ini, terjadi peningkatan nilai precision yang sangat berarti untuk setiap tingkat recall. Bahkan pada tingkat recall 0,1-0,2 diperoleh nilai precision 1, yang berarti semua poligon yang di-
8
retrieve oleh ID-Poligon merupakan poligon yang dianggap mirip oleh responden. Namun baru pada tingkat recall 0,7 seluruh poligon pustaka yang dianggap mirip oleh responden berhasil di-retrieve ID-Poligon.
pustaka yang dianggap mirip oleh responden masih mampu di-retrieve aplikasi dan merupakan kelebihan perlakuan ini dari perlakuan IV maupun perlakuan V.
Perlakuan IV. Nilai Ambang Batas Kemiripan ditetapkan sebesar 70%. Pada perlakuan ini, ditemukan bahwa pada beberapa poligon query terdapat beberapa poligon pustaka yang dianggap mirip oleh responden tidak di-retrieve oleh aplikasi. Namun nilai precisionnya yang berada di sekitar 0,7-1,0 menandakan bahwa hampir semua poligon yang di-retrieve merupakan poligon pustaka yang dianggap mirip oleh responden.
KESIMPULAN DAN SARAN
Perlakuan V. Nilai Ambang Batas Kemiripan ditetapkan sebesar 80%. Pada perlakuan ini, sebagian besar poligon yang di-retrieve aplikasi merupakan poligon pustaka yang dianggap mirip oleh responden. Hal ini terlihat dari nilai precision tertinggi dibandingkan perlakuan lainnya dengan nilai precision terendah hanya 0,93. Namun sebagai imbalannya, sebagian besar poligon pustaka yang dianggap mirip oleh responden tidak di-retrieve oleh aplikasi. Nilai rata-rata recall-precision masingmasing perlakuan dicantumkan pada Tabel 1. Untuk lebih memperjelas perbedaan hasil dari kelima perlakuan tersebut, pada Gambar 6 ditampilkan grafik yang menggambarkan kelima perlakuan dengan selang nilai precision 0,18-1,0. Seluruh grafik pada Gambar 6 mempunyai nilai precision yang menurun bersamaan dengan bertambahnya nilai recall. Artinya semakin banyak poligon pustaka yang di-retrieve, maka proporsi poligon pustaka yang relevan akan semakin menurun. Dari grafik tersebut dapat diketahui bahwa Perlakuan I menghasilkan kinerja yang paling buruk, yang pada tingkat recall 1,0 memiliki nilai precision lebih rendah 11% dari Perlakuan II. Nilai precision untuk Perlakuan IV dan V merupakan yang paling tinggi dan mendekati nilai sempurna. Namun sebagai imbalannya, tidak semua poligon pustaka yang dianggap mirip oleh responden berhasil di-retrieve oleh aplikasi. ID-Poligon memberikan kinerja paling optimal pada perlakuan III. Pada perlakuan ini, nilai precision ID-Poligon berada hingga 26% lebih baik dari perlakuan II. Semua poligon
Kesimpulan ID-Poligon adalah aplikasi untuk retrieval poligon yang digambar oleh pengguna pada kanvas penggambaran aplikasi. Aplikasi ini berdasarkan pada teknik pengenalan gambar yang disesuaikan untuk masalah poligon. ID-Poligon menggunakan tiga hal untuk memperoleh nilai kemiripan antara dua representasi poligon dan menyesuaikan dengan interpretasi penglihatan manusia, yaitu: banyaknya sudut, kemiripan kode arah sudut dan perbandingan panjang garis sisi poligon. Proses pengenalan satu poligon query hingga menampilkan seluruh poligon pustaka yang dianggap mirip membutuhkan waktu T(n) = 5n3 + 21n2 + 40n + 39 dan waktu eksekusi O(n3) dengan n melambangkan jumlah titik sudut dalam poligon sehingga dapat disimpulkan bahwa algoritme ID-Poligon cukup efisien. Pengguna dapat memperoleh hasil optimal dari aplikasi ini bila menetapkan nilai ambang batas kemiripan poligon pada nilai 60%. Saran Aplikasi temu-kembali poligon disarankan untuk dikembangkan menjadi aplikasi temukembali obyek gambar yang lebih kompleks, misalkan obyek gambar yang mengandung warna dan obyek gambar tiga dimensi.
1,2
1
Precision
0,8
Perlakuan I Perlakuan II Perlakuan III Perlakuan IV Perlakuan V
0,6
0,4
0,2
0 0,1
0,2
0,3
0,4
0,5
0,6 Recall
Gambar 6. Grafik recall-precision
0,7
0,8
0,9
1
10
DAFTAR PUSTAKA Flemming, M. C. and J. G. Nellis. 1994. Principles of Applied Statistics. Routledge, London. Freeman, H. 1961. On Encoding of Arbitrary Geometric Configurational. IEEE Trans. Elec. Computers EC-10:260-268. Gullberg, J. 1997. Mathematics: from the birth of numbers. W W Norton & Company, New York. Hearn, D. & M. P. Baker. 1986. Computer Graphics. Prentice-Hall, New Jersey. Jagadish, H. V. 1991. Retrieval Technique for Similarity Shapes, hlm. 208-217. Di dalam Proceedings of the ACM SIGMOD International Conference on the Management of Data, Denver, Colorado. Mehrotra, R. & J. E. Gary. 1993. FeatureBased Retrieval of Similar Shape, hlm. 108115. Di dalam 9th International Conference on Data Engineering, Vienna, Austria. McLeod, R. Jr. 1993. Management Information System: A Studi of Computer-Based Information Systems. MacMillan, New York. Salton, G. 1989. Automatic Text Processing : The Transformation, Analysis, and Retrieval of Information by Computer. Addison, Wesley Publishing Company, Canada. Scassellati, B., S. Alexopoulos & M. Flickner. 1994. Retrieving images by 2D shape: a comparison of computation methods with human perceptual judgments. Storage and Retrieval for Image and Video Databases II 2185:2-14. Stinson, D. R. 1985. An Introduction to the Design and Analysis of Algorithms. University of Manitoba Press, Winnipeg.
LAMPIRAN
11
Lampiran 1. Poligon Query
Poligon Query 1
Poligon Query 5
Poligon Query 2
Poligon Query 6
Poligon Query 3
Poligon Query 7
Poligon Query 4
12
Lampiran 2. Poligon Pustaka
13
Lampiran 2. (lanjutan)
14
Lampiran 2. (lanjutan)
15
Lampiran 3. Poligon Hasil Pemilihan Responden
Poligon Query 1
Poligon Query 5
Pustaka: 1, 6, 11, 29, 60
Pustaka: 15, 26,38, 46, 66
Poligon Query 2
Poligon Query 6
Pustaka: 2, 13, 16, 24, 28 36, 49, 51, 57, 65
Pustaka: 17, 18, 27, 55, 59, 64, 67
Poligon Query 3
Poligon Query 7
Pustaka: 19
Pustaka: 5, 12, 25, 39, 48, 50, 53, 56, 62, 69
Poligon Query 4 Pustaka: 4, 14, 21, 31, 32, 37, 52, 61
16
Lampiran 4. Poligon Hasil Retrieval ID-Poligon Poligon Query 1
Query 2
Query 3
Query 4
Query 5
Query 6
Query 7
40 1, 6, 29, 68, 11 60, 43, 9, 23, 40, 34, 19, 49, 31, 27, 67, 55, 18, 59, 65, 13, 36, 2, 16, 51, 57, 24, 28, 45, 54, 64 36, 13, 57, 16, 51, 24, 2, 49, 28, 65, 68, 60, 11, 29, 43, 31, 9, 19, 40, 34, 1, 6, 23, 47, 59, 67, 55, 45, 27, 18, 54 19, 8, 68, 9, 34, 24, 36, 16, 51, 29, 40, 11, 60, 31, 1, 6, 23, 13, 65, 57, 47, 8, 49, 54, 28, 45, 27, 67, 55, 18 52, 14, 21, 61, 32, 37, 4, 22, 41, 15, 26, 30, 51, 53, 66, 42, 58, 10, 46, 20, 63, 70, 62, 56, 7, 12, 17, 50, 69, 39, 53, 44, 5, 35, 3, 48, 33, 25, 45, 64, 67, 59 66, 26, 15 38, 41, 46, 4, 37, 21, 63, 8, 32, 10, 61, 22, 7, 52, 35, 30, 70, 20, 42, 58, 64, 44, 12, 27, 55, 67, 69, 59, 3, 45, 18, 5 56, 33, 54, 12, 53, 50, 25, 39, 62, 48 55, 18, 67, 59, 27, 45, 54, 64, 12, 23, 7, 70, 68, 47, 11, 60, 29, 31, 35, 33, 9, 43, 10, 20, 44, 1, 6, 41, 38, 26, 34, 19, 15, 66, 61, 3, 40, 21, 63, 37, 52, 32, 4, 14, 46 39, 48, 56, 12, 53, 50, 25, 69, 62, 5, 58, 42, 32, 21, 30, 61, 52, 14, 37, 4, 41, 38, 26, 66, 22, 15, 63, 46, 20
Tingkat Nilai Batas 50 60 1, 6, 29, 68, 11 60, 1, 6, 29, 68, 11 43, 9, 23, 40, 34, 60, 43, 9, 23 19, 49, 31, 27, 67, 55, 18, 59
70 1, 6, 29, 68, 11 60, 43, 9
80 1, 6
36, 13, 57, 16, 51, 24, 2, 49, 28, 65, 68, 60, 11, 29, 43
36, 13, 57, 16, 51, 24, 2, 49, 28
36, 13, 57, 16, 51
19, 8, 68, 9, 34, 24, 36, 16, 51
19, 8, 68, 9
19, 8
52, 14, 21, 61, 32, 37, 4, 22, 41, 15, 26
52, 14, 21, 61, 32, 37
52, 14, 21
66, 26, 15 38, 41, 46, 4, 37, 21, 63, 8, 32, 10, 61, 22, 7, 52, 35, 30, 70, 20, 42, 58, 64, 44, 12, 27
66, 26, 15 38, 41, 46, 4, 37, 21, 63, 8, 32, 10, 61, 22, 7, 52, 35, 30, 70, 20
66, 26, 15 38, 41,46,4
66, 26, 15
55, 18, 67, 59, 27, 45, 54, 64, 12, 23, 7, 70, 68, 47, 11, 60, 29, 31, 35, 33, 9, 43, 10, 20, 44, 1, 6
55, 18, 67, 59, 27, 45, 54, 64, 12, 23, 7, 70
55, 18, 67, 59, 27, 45, 54, 64
55, 18, 67, 59
39, 48, 56, 12, 53, 50, 25, 69, 62, 5, 58, 42, 32, 21, 30, 61, 52
39, 48, 56, 12, 53, 50, 25, 69, 62, 5
39, 48, 56, 12, 53, 50, 25, 69
39
36, 13, 57, 16, 51, 24, 2, 49, 28, 65, 68, 60, 11, 29, 43, 31, 9, 19, 40, 34, 1, 6, 23, 47 19, 8, 68, 9, 34, 24, 36, 16, 51, 29, 40, 11, 60, 31, 1, 6, 23, 13, 65, 57, 47, 8, 49, 54, 28, 45 52, 14, 21, 61, 32, 37, 4, 22, 41, 15, 26, 30, 51, 53, 66, 42, 58, 10, 46, 20, 63, 70, 62
