6
2.Landasan Teori 2.1 Konsep Pemetaan Gambar dan Pengambilan Data. Informasi Multi Media pada database diproses untuk mengekstraksi fitur dan gambar .Pada proses pengambilan, fitur dan juga atribut – atribut dari informasi tersebut akan dicari dan juga dibandingkan (Lu,1999). Fitur dan atribut yang di-extract harus lengkap agar mencakup semua isi dari informasi yang ada. Fitur dan atribut dari informasi multimedia akan disimpan secara ringkas. Ekstraksi Fitur merupakan elemen penting pada pemetaan gambar dan juga pengambilan data, Jika kita berbicara mengenai pengambilan data pada bidang multimedia maka hal yang perlu diingat adalah adanya dilakukannya ekstraksi fitur pada gambar. Fitur yang telah ekstraksi ini akan dibandingkan ketika dilakukan pengambilan data, kualitas dari fitur yang telah di-ekstraksi sangat menentukkan tingkat akurasi dari data yang diambil dari database, Hal yang perlu diperhatikan dari ketika dilakukan ekstraksi Fitur antara lain : 1. Fitur yang diekstrak merupakan representasi dari informasi yang terdapat di dalam item baik yang terdapat di dalam database, maupun yang dijadikan query untuk melakukan pengambilan data, oleh karena itu fitur yang di-ekstrak harus lengkap sehingga mampu mewakili informasi yang terdapat di dalam suatu gambar. 2. Perhitungan jarak yang digunakan dilakukan se-efisien mungkin, karena jika tidak dilakukan demikian maka waktu yang dilakukan untuk menghitung jarak antar fitur akan semakin lama. 3. Fitur yang diekstraksi harus mewakili informasi dari gambar dan juga disimpan secara ringkas, karena fitur yang kompleks dan juga sangat besar akan berdampak pada pengambilan gambar dari database sehingga menjadi tidak efektif.
7
Pada dasarnya ada empat pendekatan dalam pemetaan dan juga pencarian gambar. Yang pertama adalah isi dari Gambar dimodelkan sebagai sekumpulan dari atribut yang diekstraksi secara manual dan kemudian dikelola dalam Sistem Menejemen Database yang konvensional. Ekstraksi akan dilakukan berdasarkan pada atribut yang ada. Yang termasuk dalam kategori ini adalah keterangan mengenai gambar seperti tanggal pembuatan, nama file dari gambar tersebut, subjek dari gambar tersebut. Kelemahan terbesar dari metode ini adalah Atribut dari gambar tidak dapat menjelaskan mengenai gambar tersebut secara menyeluruh seperti isi dari gambar tersebut dan query hanya terbatas kepada atribut-atribut yang ada.
Pendekatan yang kedua adalah dengan menggunakan pendekatan ekstrasi fitur atau sub-system pengenalan objek. Subsystem ini dapat meng-automasikan ekstraksi fitur atau pengenalan objek. Akan tetapi pendekatan secara ter-automasi memiliki biaya komputasional yang besar. Pendekatan yang ketiga adalah dengan menggunakan anotasi pada gambar dan juga menerapkan teknologi IR untuk melakukan pengambilan gambar. Pendekatan yang ke-empat adalah dengan menggunakan fitur level rendah dari gambar seperti warna, tekstur untuk melakukan ekstraksi pada gambar. Pada proposal peneliti akan menggunakan pendekatan metode yang ke-empat, Pemetaan gambar dan pengambilan data dengan menggunakan fitur level rendah dari warna karena data yang akan digunakan adalah data yang berupa gambar. Adapun beberapa konsep ekstraksi gambar dengan menggunakan fitur level rendah. Dari keempat pemetaan dan juga pengambilan gambar yang telah dijelaskan diatas, dapat ditarik 4 teknik yang berbeda untuk pemetaan dan juga pengambilan gambar, yaitu :
8
2.1.1
Pemetaan Gambar dan Pengambilan Data Berdasarkan Teks
Pada pendekatan dengan menggunakan teks atau tulisan, pengambilan gambar atau query dilakukan dengan menggunakan teks tanpa menggunakan operator boolean, pengambilan gambar dilakukan dengan menggunakan kesamaan antara tulisan yang dijadikan query dengan teks yang menjelaskan gambar yang ada pada database. Pada pengambilan gambar berdasarkan teks, Anotasi secara teks pada umumnya dilakukan secara manual karena karena pemahaman dari sebuah gambar tidak mungkin dilakukan tanpa adanya anotasi, pada saat melakukan anotasi hal yang perlu diperhatikan adalah bagaimana anotasi dilakukan secara efisien dan juga bagaimana anotasi dapat menjelaskan arti dari sebuah gambar secara lengkap dan juga konsisten. Keuntungan dari penggunaan teks adalah teks dapat menjelaskan menjelaskan arti abstrak pada sebuah gambar, seperti senyuman pada objek dari sebuah gambar, ataupun keadaan dari latar belakang objek dari gambar.
2.1.2
Pemetaan Gambar dan Pengambilan Data Berdasarkan Warna
Pengambilan gambar berdasarkan warna dilakukan dengan cara mengambil gambar dari sebuah database di mana warna pada gambar yang terdapat di dalam database memiliki kesamaan dengan warna pada gambar yang menjadi query. Peng-indeksan dan pengambilan gambar berdasarkan warna dilakukan dengan cara menggunakan metode color histogram, setiap gambar yang terdapat di dalam database akan direpresentasikan ke dalam 3 warna utama yaitu : Merah, Hijau, dan juga Biru. Warna-warna pada gambar yang terdapat di dalam database akan di-diskritkan ke dalam interval m, sehinggan total kombinasi warna n pada gambar sama dengan m3, color Histogram adalah sebuah vektor(h1,h2,......, hj) di mana elemen hj merepresentasikan jumlah pixel yang terdapat
9
pada gambar M , feature vector ini kemudian akan menjadi indeks dari gambar. Pada tahap pengambilan gambar dari database, jarak histogram dari gambar yang dijadikan query dengan histogram dari gambar yang terdapat di dalam database kemudian akan dihitung , gambar yang memiliki jarak histogram yang terkecil kemudian akan ditampilkan sebagai hasil dari query yang dilakukan. Sebagai contoh, jika kita memiliki 3 gambar berukuran 8 x 8 pixel di mana setiap pixel pada gambar memiliki warna C1,......, C8 . Gambar yang pertama memiliki warna setiap warna dari C1,......, C8 . Gambar kedua memiliki 7 pixel dari warna C1,......,C4 dan 9 pixel memiliki warna C5,...., C8 , gambar ketiga memiliki 2 pixel yang memiliki warna C1 dan C2 , serta 10 pixel yang memiliki warna C3,..,C8 maka dari gambaran di atas kita memiliki histogram sebagai berikut : HI = (8, 8, 8, 8, 8, 8, 8, 8) H2 =(7, 7, 7, 7,9,9,9,9) H3 = (2,2, 10, 10, 10, 10, 10, 10) Jarak antar ketiga gambar tersebut adalah : d(HI, H2) = 1+1+1+1+1+1+1+1 = 8 d(H1, H3) = 6+6+2+2+2+2+2+2 = 24 d(H2, H3) = 5+5+3+3+3+1+1+1+1 = 23 dari perhitungan jarak antar Histogram satu gambar dengan gambar lain yang telah dilakukan maka dapat kita simpulkan bahwa gambar pertama mirip ataupun hampir sama dengan gambar yang kedua.
10
2.1.3
Pemetaan Gambar dan Pengambilan Data Berdasarkan Bentuk.
Pada peng-indeksan dan pengambilan gambar berdasarkan bentuk dapat dilakukan bila gambar memiliki representasi yang unik, pengambilan gambar berdasarkan pada bentuk dilakukan dengan mengukur kesamaan dari bentuk gambar yang menjadi query dengan gambar yang terdapat di dalam database gambar yang memiliki bentuk yang sama akan memiliki hasil pengukuram yang sama, pada metode pengambilan gambar berdasarkan pada bentuk, gambar yang memiliki bentuk yang mirip akan memiliki jarak pengukuran yang kecil, sehingga gambar yang akan menjadi hasil query akan diberikan sesuai dengan urutan dari jarak yang nilainya terkecil hingga ke jarak yang nilainya terbesar. Ada empat istilah yang sering digunakan dalam metode peng-indeksan dan juga pengambilan gambar berdasarkan bentuk antara lain : • Major Axis : garis segmentasi lurus yang menggabungkan dua titik lurus yang terjauh • Minor Axis : garis yang terletak tegak lurus dengan Major Axis. • Basic Rectangle : Sebuah Persegi panjang yang terbentuk dengan menggunakan Major Axis dan juga Minor Axis. • Eccentricity : Rasio dari perbandingan antara panjang Minor Axis dengan Major Axis.
2.1.3.1 Region based shape representation Pada thesis ini penulis akan membahas mengenai region based shape representation karena metode ini memiliki tingkat pemanggilan kinerja yang tinggi (J.L. Guo et al). Pada metode ini dilakukan pemberian bilangan biner untuk sebuah gambar dimana pemberian bilangan biner tersebut memiliki ketentuan jika bentuk dari sebuah gambar mancakup 15 % dari ukuran sebuah pixel maka pada pixel tersebut akan diberikan angka 1, jika sebuah
11
bentuk dari gambar tidak mencakup ataupun tidak terdapat pada sebuah pixel maka pixel tersebut akan diberikan angka 0, pemberian angka pada pixel tersebut dilakukan dengan cara memberikan angka dari pixel yang terdapat pada sisi kiri ujung pada sebuah gambar ke sisi kanan ujung dari sebuah gambar dan juga dilakukan secara berurutan dari atas ke bawah sebagai contoh seperti gambar berikut ini :
Gambar 2.1 Contoh region based shape 1 Maka hasil pemberian bilangan biner pada Gambar 2.2.3 adalah sebagai berikut 11100000 11111000 01111110 01111111. Pemberian bilangan biner sangat mudah untuk dilakukan akan tetapi pada pemberian bilangan biner scaling dan rotasi pada gambar akan mempengaruhi hasil. Oleh karena itu dilakukanlah normalisasi agar hasil dari pemberian biner tetap konsisten atau tidak berubah. Terdapat tiga jenis normalisasi, antara lain : 1. Normalisasi Rotasi. Normalisasi ini dilakukan dengan cara memutar sebesar 1800, suatu bentuk akan dirotasikan hingga Major Axis dari bentuk tersebut menjadi pararel dengan x-Axis . Kita akan menggunakan gambar berikut sebagai contoh :
12
Gambar 2.2 Contoh Normalisasi Rotasi 1
Gambar 2.3 Contoh Normalisasi Rotasi 2
Gambar di atas merupakan
kemungkinan dari rotasi yang dilakukan pada sebuah
bentuk dengan menggunakan sumbu x-axis. Dengan mengingat efisiensi dari kapasitas penyimpanan maka hanya akan diambil deretan bilangan biner. akan tetapi pada tahap pengambilan gambar dari database kedua deretan bilangan biner tersebut digunakan.dengan cara dibandingkan dengan data gambar yang lain di dalam database. 2. Normalisasi Skala. Normalisasi skala dilakukan dengan cara mengubah ukuran dari gambar sehingga panjang Major Axes dari gambar tersebut sama panjang.
13
Pada pengambilan bentuk semua gambar yang terdapat di dalam database akan di-index dan bentuk yang merupakan query juga akan di-index, setelah itu bentuk query yang telah diindexed tersebut akan dibandingkan dengan bentuk-bentuk dari gambar yang terdapat di dalam database. Setiap bentuk akan dihitung mengenai Major Axis, Minor axis dan juga accentricity dari setiap gambar akan dihitung, setelah itu dilakukanlah normalisasi rotasi dari gambar, bentuk - bentuk yang telah ternormalisasi akan diberikan deretan biner, lalu deretan biner dan juga panjang dari minor Axis akan disimpan sebagai index dari bentuk. Pada saat pengambilan gambar dilakukanlah pengambilan empat digit bilangan biner yang dilakukan normalisasi rotasi setelah dilakukan normalisasi rotasi, keempat urutan bilangan biner tersebut akan dibandingkan dengan gambar yang memiliki eccentricity yang sama, dilakukanlah perhitungan jarak antara bentuk query dengan setiap gambar yang terdapat di dalam database. dari hasil perhitungan jarak yang telah dilakukan maka gambar akan ditampilakan secara berurutan dari bentuk yang memiliki perbedaan jarak yang terkecil hingga ke jarak yang terbesar, di mana bentuk query yang sama dengan bentuk yang sama yang terdapat di dalam database memiliki jarak sebesar 0.
2.1.4 Pemberian Indeks dan Pengambilan Gambar Berdasarkan Tekstur.
Menurut Tamura et al , tekstur dibagi menjadi 6 bagian kesimpulan ini diperoleh setelah dilakukan penelitian untuk memperoleh pengertian dari tekstur, karena tekstur merupakan salah satu fitur penting dari sebuah gambar akan tetapi pengertian dari sebuah tekstur sangat sukar untuk dideskripsikan dan juga sering bersifat subjektif.
14
Berikut ini adalah 6 fitur yang menggambarkan tekstur :
1. Coarseness
: Coarseness merupakan salah satu fitur fundamental yang terdapat di
dalam tekstur, semakin berbeda elemen - elemen yang terdapat pada
sebuah
gambar maka akan semakin kasar. 2. Contrast
: Contrast dapat ditentukan melalui empat empat parameter, yaitu :
cakupan dari tingkat keabuan dari sebuah gambar, polarisasi dari warna hitam dan juga putih pada histogram warna abu-abu pada gambar, ketajaman dari sudut pada gambar dan juga periode dari berulangnya suatu pola pada gambar. 3. Directionality : Pada directionality dilakukan perhitungan bentuk dan juga posisi dari gambar 4. Line Likeness : Parameter ini berhubungan dengan bentuk dari sebuah tekstur. 5. Regularity
: Regularity berhubungan dengan regular atau irregular dari sebuah
gambar, semakin banyak bentuk elemen yang berbeda dari sebuah gambar maka akana semakin rendah regularity-nya. 6. Roughness
: Parameter ini digunakan untuk mengetahui apakah sebuah tekstur
kasar atau lembut, parameteini dipengaruhi oleh coarseness dan juga contrast.
2.2 Pengolahan Citra Digital Digital Image Processing merupakan sebuah fungsi dua dimensi f(x,y) di mana x dan y adalah koordinat jarak , amplitude f dari setiap pasangan koordinat (x,y) adalah intensitas atau grey level dari sebuah gambar(Gonzales et al, 2002). Ada tiga tahapan dalam digital image processing , yaitu : • Proses tingkat rendah, di mana process ini meliputi proses unutk mengurangi noise, meningkatkan kontras, dan juga penajaman dari gambar.
15
• Proses tingkat menengah, pada proses ini partisi akan dilakukan pada gambar untuk mesegmentasikan gambar menjadi bagian yang lebih kecil atau object, pada proses tingkat menengah gambar merupakan masukan yang akan diekstrak fitur-fiturnya sehingga menjadi hasilnya akan menjadi atribut dari gambar tersebut yang dapat berupa informasi mengenai kontur, sudut dan juga identitas dari setiap objek yang telah diekstrak • Proses tingkat tinggi, pada tahapan ini akan dilakukan analisa dari gambar tersebut.
2.3 Konsep metode Correlogram. Correlogram warna dari dari sebuah gambar adalah sebuah tabel yang di-index dengan menggunakan pasangan warna di mana k yang ke h adalah sebuah titik awal masuk dari (i,j) yang men-spesifikasikan kemungkinan ditemukannya pixel dari warna j pada jarak k dari pixel warna i pada gambar yang dimaksud (Huang et al, 1998). Fitur dari gambar yang demikian memberikan tingkat toleransi yang tinggi pada perubahan gambar dari skema atau topik yang sama yang disebabkan oleh sudut pandang dari pengambilan gambar yang berbeda. Correlogram memberikan gambaran bagaimana hubungan informasi mengenai jarak dari pasangan warna yang berubah terhadap jarak.Misalkan I adalah gambar berukuran n x n , ......,
, warna dari I kita kuantifikasikan menjadi m warna bilangan konstan. Untuk pixel sehingga menghasilkan persamaan . Kita akan menggunakan pixel, untuk pixel
. m merupakan
, I(p) akan menyatakan warnanya . Oleh karena itu notasi - norm untuk menghitung jarak antar
p1 = (x1,y1), p2 = (x2,y2), maka ditetapkan :
16
..................................................(2.1) Setelah itu sekumpulan dari angka{1,2,3,4,5,6,..., n} akan dinyatakan menjadi n . Sehingga diperoleh persamaan sebagai berikut :
(I)Δ
Di mana setiap pixel pada warna
...........................................................(2.2)
pada gambar,
memberikan kemungkinan bahwa
pixel pada jarak yang ke k dari pixel yang diketahui merupakan warna dari
.
Ketika kita menggunakan Correlogram kita harus mengingat akan adanya permasalahan yang menyangkut ukuran dari d yang akan digunakan untuk melakukan komputasi dari Correlogram. Selanjutnya kita akan melakukan perhitungan untuk menghadapi suatu kasus ketika nilai d yang digunakan untuk menghitung nilai Correlogram. Untuk menghitung Correlogam kita terlebih dahulu melakukan perhitungan berikut, di mana perhitungan tersebut sama dengan perhitungan yang dilakukan untuk metode cooccurance matrix yang dilakukan untuk analisa tekstur dan warna abu – abu Adapun rumus untuk melakukan perhitungan pada metode image Correlogram adalah sebagai berikut :
.........................................................(2.3) Kita akan melakukan perhitungan CCM terlebih dahulu, setelah mendapatkan hsail dari perhitungan CCM maka kita akan melakukan pembagian dengan hasil dari perhitungan
17
tersebut dengan menggunakan histogram setelah itu dikalikan dengan 8k,
faktor 8k
dikarenakan oleh 8 pixel tetangga dari pixel pusat. Metode Correlogram akan dijadikan sebagai landasan teori karena metode image Correlogram mampu memberikan informasi spatial dengan menggunakan rumus perhitungan yang telah dijelaskan sebelumnya, sehingga mampu memberikan tingkat ke-akurasian yang tinggi untuk melakukan pencarian gambar. Berikut adalah contoh dari penggunaan metode correlogram : Misalkan kita memiliki gambar I dengan n = 2 dan m = 8, seperti pada gambar berikut
Gambar 2.4: Contoh 1 dan contoh 2
Kedua gambar tersebut memiliki histogram yang sama correlogram dari kedua gambar tersebut akan dijelaskan pada grafik 2.2 . Perubahan pada korelasi warna kuning pada bagian depan dari kedua gambar tersebut dengan jarak sangat berbeda. Pada gambar kedua, korelasi bernilai 0 pada jarak 2, dan kemudian mencapai nilai tertingginya pada jarak 4, berikut ini adalah tampilan grafik pada perhitungan dengan menggunakan metode image Correlogram.
18
Gambar 2.5 Tampilan grafik Correlogram.
2.4 Gray Level Co-occurrance Matrix. Gray Level Co-occurrance Matrix ditemukan oleh Robert Haralick,Ph.D pada tahun1973, Gray Level Coocurrance matrix(yang lebih dikenal dengan istilah glcm) digunakan untuk mengukur intensitas dari tingkat keabu-abuan dari suatu gambar dengan cara menghitung jumlah munculnya suatu pixel dengan sebuah pixel dengan warna abu – abu yang memiliki nilai i muncul secara horizontal dengan pixel yang memiliki nilai j di mana kedua pixel tersebut berdekatan, jika gambar tersebut adalah gambar biner maka glcm akan menskalakan gambar tersebut menjadi dua tingkat keabu-abuan jika gambar tersebut memiliki intensitas maka gambar tersebut akan diskalakan menjadi 8 tingkat keabu-abuan. Gambar 2.3 menunjukkan bagaimana perhitungan glcm dilakukan pada gambar berukutan 4 x 5, element (1,1) memiliki nilai 1 karena pada gambar 5x5 tersebut hanya satu pasang pixel saja yang memiliki 1 dan 1, elemen (1,2) pada glcm memiliki nilai 2 karena pada gambar 2.3 terdapat dua pixel yang memiliki nilai 1 dan 2.
19
Gambar 2.6 Menentukan nilai glcm. Secara default fungsi graycomatrix menciptakan satu glcm dengan informasi spasial, akan tetapi satu glcm tidak cukup untuk menggambarkan fitur tekstur dari sebuah gambar, jika kita menggunakan satu glcm saja maka glcm tersebut tidak dapat memperoleh informasi spasial dari pixel yang memiliki arah vertikal, untuk memperoleh informasi spasial dari arah yang lain kita dapat menggunakan offsets, dengan menggunakan offsets kita dapat memperoleh informasi spasial dari empat arah (vertikal, horizontal, dan juga dua diagonal) serta empat jarak, pada thesis ini gambar yang menjadi query di-representasikan oleh 16 glcm. Berikut ini adalah offsets yang terdapat pada glcm : Sudut
Offset
0
[0 D]
45
[-D D]
90
[-D 0]
135
[-D -D]
tabel 2.1 Offset dari glcm
20
Berikut ini adalah contoh dari penggunaan glcm dengan offset dari empat arah dan juga dengan jarak sebanyak 1. Contoh : offset = [0 1; -1 1; -1 0; -1 -1]
Gambar 2.7 Pixel Offset. Setelah diperoleh nilai-nilai pada glcm maka selanjutnya akan dilakukan pengambilan nilai statistik dari GLCM yang telah terbentuk, statistik berisi mengenai keterangan tekstur pada gambar, berikut ini adalah statistik yang dapat diambil dari glcm : Statistik
Deskripsi
CONTRAST
Mengukur rasio dari intensitas dari warna yang paling terang (putih) hingga ke warna yang paling gelap.
CORRELATION
Mengukur korelasi antara 2 pixel, pada pasangan pixel. Korelasi akan semakin tinggi jika tingkat keabu- abuan dua buah pixel memiliki korelasi yang tinggi.
ENERGY
Menghitung jumlah dari pasangan pixel yang berulang.
HOMOGENEITY
Menghitung kedekatan dari distribusi elemen pada GLCM terhadap GLCM diagonal Tabel 2.2 Statistik dari GLCM.
21
2.5 Pengukuran Kinerja Metode pengukuran kinerja pada thesis ini dilakukan dengan menggunakan metode recall and precision, yang dimaksud dengan recall adalah jumlah dari gambar yang diambil dari database yang relevan dengan gambar yang menjadi query dalam jumlah item yang dikembalikan sesuai dengan query user per sekali pemanggilan. Precision ynag dimaksud dengan precision di sini adalah jumlah dari gambar yang sama dengan gambar yang menjadi query dari user dengan gambar yang relevan dari database, semakin tinggi recall maka semakin tinggi kinerja dari sistem, jika sistem memiliki recall yang rendah maka semakin rendah tingkat kinerja dari suatu sistem, jika sistem memiliki presisi atau precision yang tinggi maka semakin tinggi tingkat akurasi dari sistem. Jika sistem memiliki precision yang rendah maka hal ini mengindikasikan akurasi yang rendah dari sistem.