BAB II LANDASAN TEORI
II.1 Retrival Citra Berbasis Konten Dalam berbagai aplikasi computer vision yang banyak digunakan adalah proses meretrif citra yang diinginkan dari koleksi citra yang besar berdasarkan fitur yang dapat secara otomatis diekstrak dari citra tersebut. Sistem ini disebut RCBK (Retrival Citra Berbasis Konten). RCBK telah menjadi perhatian banyak orang dalam retrival citra sehingga berbagai teknik pun diusulkan untuk mendapatkan hasil yang lebih baik. Algoritma yang digunakan dalam RCBK dapat dibagi menjadi 3 bagian, yaitu : ekstraksi, seleksi dan klasifikasi. Ekstraksi mengubah konten citra ke berbagai fitur konten. Ekstraksi fitur adalah proses menghasilkan fitur yang akan digunakan dalam seleksi dan klasifikasi. Seleksi fitur mengurangi jumlah fitur yang ada untuk klasifikasi. Fiturfitur yang merupakan diskriminator dipilih dan digunakan dalam proses klasifikasi. Fitur yang tidak dipakai dibuang. Dari tiga bagian tersebut, ekstraksi fitur merupakan bagian yang paling penting karena fitur diskriminasi yang ada mempengaruhi efektivitas proses klasifikasi. Hasil akhir dari proses ekstraksi adalah sejumlah fitur yang biasa disebut fitur vektor yang merepresentasikan sebuah citra.
8
Citra Kueri
Citra Basis data
Ekstraksi Fitur
Fitur Kueri
Similarity measure
Fitur Basis data
Citra retrif Gambar 2.1 Diagram proses RCBK.
Umumnya sistem CBIR terdiri dari tiga modul utama seperti modul basis data, modul kueri dan modul retrival. Pada modul basis data, fitur vektor (warna, tekstur, bentuk) diekstrak dari citra basis data. Fitur vektor tersebut kemudian disimpan dengan citra aslinya. Di lain pihak, ketika citra query memasuki modul kueri, fitur vektor dari citra kueri diekstrak. Pada modul retrival, fitur vektor kueri yang telah diekstrak deibandingkan dengan fitur vektor yang disimpan pada citra basis data. Hasil dari kueri, citra yang mirip diretrif berdasarkan nilai kemiripan tertinggi, sehingga citra yang diharapkan dapat diambil dari citra yang telah diretrif, seperti ditunjukkan pada gambar 2.1.
II.1.1 Retrival Citra Mammogram
Retrival citra berbasis konten yang telah dipelajari untuk aplikasi non
medis bisa digunakan pada domain medis. Citra medis mengandung fitur yang
9
kaya, bervariasi dan halus yang merupakan fitur yang penting secara klinis. Hal inilah yang membedakan retrival pada domain medis dengan retrival pada domain multimedia (Akgul, Rubin, Napel, Beaulieu, Greenspan, & Acar, 2010). Kueri berdasarkan deskriptor citra konten dapat membantu dalam proses diagnosis. Fitur visual dapat digunakan untuk mencari citra yang diinginkan dan meretrif informasi yang relevan untuk kasus klinis. Salah satu contohnya adalah retrival citra berbasis konten yang mendukung citra mammogram. Sampai sejauh ini, mammography masih merupakan cara yang paling efektif untuk mendeteksi kanker payudara dini. Terlepas dari kemajuan teknologi dalam beberapa tahun terakhir, menganalisis mammogram masih merupakan tugas klinis yang sulit. Beberapa kanker payudara mungkin menghasilkan perubahan yang halus dan sulit dikenali pada mammogram sehingga bisa menyebabkan intepretasi yang salah (El-Naqa, Yang, Galatsanos, Nishikawa, & Wernick, 2004). Pemilihan fitur yang cocok untuk retrival citra mammogram menjadi hal yang sangat penting. Hal ini sangat diperlukan untuk mengurangi adanya semantic gap (hasil yang diharapkan tidak sesuai dengan hasil retrival) dan dokter bisa semakin percaya pada hasil retrival (Zhou, et al., 2008). Berbagai jenis fitur dan teknik telah digunakan untuk menciptakan suatu sistem retrival mammogram yang handal. Adapun teknik yang sudah digunakan dalam penelitian-penelitian sebelumnya, antara lain menggunakan fitur tekstur dengan teknik gray level co-occurence matrices (GLCM) untuk meretrif citra mammogram berdasarkan kelas abnormalitasnya (Wei, Li, & Wilson, 2005).
10
Selain itu, ada juga yang menggunakan teknik gray level aura matrix (GLAM) (Wiesmuller & Chandy, 2010), fungsi gabor filtering (Wei, Li, & Li, 2007), dan lain sebagainya.
II.2 Ekstraksi Fitur Fitur didefinisikan sebagai fungsi dari satu atau lebih pengukuran yang masing-masing menentukan sifat kuantitatif dari suatu objek dan dihitung sedemikian rupa sehingga mengkuantifikasikan beberapa karakteristik objek yang signifikan. Berbagai fitur diklasifikasikan sebagai berikut : -
Fitur umum : Fitur aplikasi independen seperti warna, tekstur, dan bentuk. Menurut tingkat abstraksi, fitur ini dapat dibagi lagi menjadi : o Fitur piksel : Fitur dihitung pada setiap piksel, misalnya warna, lokasi. o Fitur lokal : Fitur dihitung dari hasil bagian citra dari segmentasi citra atau deteksi tepi. o Fitur global : Fitur dihitung dari seluruh citra atau bagian dari suatu citra.
-
Fitur Domain-Specific : Fitur aplikasi dependen seperti wajah manusia, sidik jari dan fitur konseptual. Fitur-fitur ini merupakan sintesis fitur tingkat rendah (low-level) untuk domain tertentu. Di sisi lain, semua fitur dapat diklasifikasikan menjadi fitur tingkat rendah
dan fitur tingkat tinggi (high-level). Fitur tingkat rendah dapat diekstrak langsung
11
dari citra asli, sedangkan ekstraksi fitur tingkat tinggi berdasarkan fitur tingkat rendah.
II.2.1 Warna Fitur warna adalah salah satu fitur visual yang paling banyak digunakan dalam retrival citra (Sumana, 2008). Citra yang dicirikan oleh fitur warna memiliki banyak keuntungan antara lain : -
Ketahanan. Histogram warna invarian terhadap rotasi gambar pada sumbu axis dan perubahan yang kecil ketika di rotasi atau diskalakan. Biasanya juga tidak
sensitif
terhadap
perubahan
dalam resolusi gambar,
histogram
dan oklusi. -
Efektivitas. Ada relevansi yang tinggi antara citra kueri dengan citra ekstrak yang sesuai.
-
Kesederhanaan implementasi. Pembentukan histogram warna merupakan proses langsung, termasuk pemindaian citra, menempatkan nilai warna pada resolusi histogram dan membentuk histogram menggunakan komponen warna sebagai index.
-
Kesederhanaan komputasi. Perhitungan histogram mempunyai kompleksitas O(X, Y ) untuk citra dengan ukuran X × Y . Kompleksitas untuk kesesuaian citra tunggal adalah linear, O(n), dimana n adalah jumlah warna yang berbeda atau resolusi histogram.
-
Kebutuhan kapasitas yang rendah. Ukuran histogram warna secara signifikan lebih kecil dari pada citra itu sendiri.
12
II.2.2 Tekstur Tekstur merupakan salah satu properti yang penting dari sebuah citra. Tekstur merupakan deskriptor regional yang kuat yang sangat membantu dalam proses retrival. Tekstur sendiri tidak mempunyai kemampuan untuk mencari citra yang mirip, tapi tekstur dapat digunakan
untuk mengklasifikasikan citra
bertekstur dari citra yang tidak bertekstur, kemudian dikombinasikan dengan atribut visual lain seperti warna untuk melakukan retrival secara lebih efektif. Ada dua jenis pendekatan ekstraksi fitur tekstur, antara lain pada domain spasial dan domain spektral. Klasifikasi metode ekstraksi fitur tekstur ditunjukkan pada gambar di bawah ini.
Gambar 2.2 Klasifikasi metode ekstraksi fitur tekstur (Sumana, 2008).
Pendekatan domain spasial peka terhadap noise sehingga perubahan kecil pada citra yang disebabkan oleh noise dapat mempengaruhi keseluruhan proses
13
ekstraksi fitur. Ketika citra yang sama dengan dan tanpa noise dibandingkan, nilai dari fitur tekstur berbeda, sehingga walaupun citranya mirip dan ada noise, citra tersebut mungkin tidak akan diretrif dalam CBIR yang menggunakan fitur spasial.
Gambar 2.3 Citra sebelah kanan dibuat dengan menambahkan Gaussian Noise (mean = 0, varian = 0,01) pada citra sebelah kiri (Sumana, 2008).
Pada gambar 2.3, citra sebelah kanan dibuat dengan menambahkan Gaussian noise pada citra sebelah kiri. Mean dan standar deviasi kemudian dikalkulasi dari koefisien domain spasialnya. Citra sebelah kirim mempunyai mean 198.26 dan standar deviasi 52.84. Akan tetapi, citra sebelah kanan mempunyai mean 196,88 dan standar deviasi 56,97. Jika retrival dilakukan dengan menggunakan tekstur spasial, kedua citra tersebut akan diperlakukan sebagai citra yang berbeda karena fitur masing-masing mempunyai perbedaan yang besar. Fitur tekstur Tamura merupakan jenis fitur pada domain spasial. Fitur tekstur Tamura terdiri dari 6 komponen, antara lain: kekasaran (coarseness), kontras
(contrast),
direksional
(directionality),
kesesuaian
(likeliness),
keteraturan (regularity) dan kekesatan (roughness). Di antara semua komponen tersebut, kekasaran, kontras dan direksional dianggap lebih penting. Deskriptor
14
fitur Tamura tidak efektif jika digunakan untuk merepresentasikan citra yang cacat karena fitur ini sensitif terhadap skala dan orientasi. (Sumana, 2008). Di sisi lain, metode pada domain spektral seperti wavelet multi resolusi, filter Gabor, Transformasi Kosinus Diskrit dan model
multiresolution
simultaneous autoregressive memiliki keuntungan yaitu tidak sensitif terhadap noise.
Oleh
karena
itu,
transformasi
ini
banyak
digunakan
untuk
merepresentasikan tekstur citra. Karena keuntungan dari fitur tekstur domain spektral atas metode spasial, domain spektral telah banyak digunakan dalam CBIR.
II.2.3 Bentuk Retrival citra berdasarkan bentuk berbasis pada pengukuran kemiripan antara bentuk yang diwakili dengan fiturnya. Bentuk adalah fitur visual yang penting dan merupakan salah satu fitur sederhana untuk deskripsi konten citra. Deskripsi konten citra sulit diterapkan karena pengukuran kemiripan antar bentuk sulit dilakukan. Oleh karena itu, ada dua langkah penting dalam CBIR berdasarkan bentuk, antara lain : ekstraksi fitur dan pengukuran kemiripan antar fitur yang diekstrak. Deskriptor bentuk dapat dibagi menjadi dua kategori utama, yaitu berbasis wilayah dan berbasis kontur. Metode berbasis wilayah menggunakan seluruh wilayah dari sebuah objek sebagai deskripsi bentuk, sedangkan metode berbasis kontur hanya menggunakan informasi yang ada di kontur sebuah objek. Penjelasan singkat deskriptor bentuk sebagai berikut :
15
-
Fitur dikalkulasi dari kontur objek : circularity, aspect ratio, discontinuity angle irregularity, length irregularity, complexity, right-angleness, sharpness, directedness. Those are translation, rotation (kecuali sudut), dan scale invariant shape descriptors. Hal ini memungkinkan untuk mengekstrak kontur citra dari tepi yang terdeteksi. Dari objek kontur, informasi tentang bentuk berasal.
-
Deskriptor berbasis wilayah menggunakan satu set momen Zernike yang dihitung pada pusat citra.
II.3 Low Rank Approximations Text processing, data mining dan image processing menyimpan informasi yang berhubungan dalam suatu matriks yang besar (misalkan matriks A). Matriks A ini besar, sparse dan seringkali nilainya non-negative. Dalam beberapa dekade terakhir, para peneliti menyadari bahwa matriks data dapat diganti dengan matriks yang berhubungan dengan rank yang lebih rendah (Langville, Meyer, Albright, Cox, & Duling). Low rank approximation pada matriks data A memberikan beberapa keuntungan antara lain mengurangi ruang penyimpanan. Tetapi yang paling penting, matriks low rank memberikan hubungan yang lebih jelas, lebih efisien antara elemen data. Low rank approximation mengidentifikasikan komponen-komponen data yang paling penting dengan mengabaikan komponenkomponen yang tidak penting seperti noise atau inkonsistensi. Beberapa teknik low rank approximation yang bisa digunakan antara lain Principal Component Analysis (PCA), Singular Value Decomposition (SVD), Vector Quantization, Factor Analysis, QR decomposition dan berbagai teknik lainnya.
16
II.3.1 Principle Component Analysis
Principle component Analysis (PCA) yang juga disebut metode eigenface,
merupakan metode linear appearance-based yang popular dalam reduksi dimensi pada pengenalan wajah. Teori yang digunakan pada PCA berdasarkan transformasi Karhunen-Loeve (Chen, Pan, Fang, Li, & Tang, 2008). PCA secara konvensional mengadopsi metode analisis statsitikal yang memfasilitasi pengurangan redudansi dengan memproyeksikan data asli ke basis yang tepat. Tujuan PCA adalah untuk menciptakan representasi yang lebih relevan dengan mereduksi dimensi dari vektor asli (Huang, Kuo, Chang, Liu, Moon, & Chen, 2005). PCA bertujuan menyoroti variabilitas data (Bhattacharjee, Banerjee, & Chowdhury). Misalkan kita mempunyai jumlah point data (Sn) dalam ruang dua dimensi. Jika direpresentasikan sebagai (xi, yi) {i = 1, 2, ...... Sn}, mean dari data point dikalkulasikan dengan persamaan berikut. ∑
(2.6)
∑
(2.7)
Nilai mean kemudian dikurangkan dari data point untuk tujuan normalisasi. ′
′
Data yang disesuaikan =
(2.8) ′
′
Kemudian dapat melakukan perhitungan variabilitas relatif dari dimensi dalam matriks covarian. , ,
,
(2.9)
,
17
Dimana diagonal utama menunjukkan varians dari masing-masing dimensi x dan y. Covarian dari x,y dapat dikalkulasi sebagai berikut. ,
∑
,
(2.10)
Dari matriks covarian, nilai eigen dihitung. Dari nilai eigen maka vektor eigen dikalkulasi. Dua vektor eigen yang berkoresponden dengan dua nilai eigen akan saling orthogonal. Dari sisi PCA, vektor eigen merupakan panjang unit. Vektor eigen dengan nilai eigen tertinggi disebut componen utama dari dataset karena memberikan informasi yang maksimum tentang pola dalam data. Informasi pola yang diberikan oleh vektor eigen lainnya berkurang dengan nilai eigen. Sehingga suatu vektor dari vektor eigen terbentuk dari nilai eigen dengan urutan menurun. Fitur vektor = (eig_vek1 eig_vek2)
(2.11)
Vektor eigen dengan urutan yang kecil dapat diabaikan karena vektor tersebut hanya memberikan informasi yang sangat kecil dalam dataset. Data final didapat dengan persamaan berikut. Data final = Data yang disesuaikanT x fitur vektorT
(2.12)
Akan tetapi, PCA tidak mampu untuk mengekploitasi seluruh informasi fitur klasifikasi dan pemilihan elemen komponen utama masih merupakan suatu masalah. Sehingga, PCA tidak bisa memberikan hasil yang memuaskan dalam hal pengenalan pola (Chen, Pan, Fang, Li, & Tang, 2008).
II.3.2 Singular Value Decomposition Singular
Value
Decomposition
(SVD)
sering
digunakan
untuk
membangun suatu low rank approximation pada matriks term-by-document dalam
18
retrival infomasi (Langville, Meyer, Albright, Cox, & Duling). Nyatanya, untuk membangun suatu rank-k approximation Ak pada matriks A rank r term-bydocument, gunakan hanya komponen singular k yang paling signifikan dimana k
∑
(2.13)
adalah nilai singular A ke-i,
dan
adalah vekotr singular. Teknik
menggantikan matriks A dengan Ak yang sudah direduksi disebut Latent Semantic Indexing (LSI) karena low rank approximation mengungkapkan makna dan hubungan antar dokumen yang tersembunyi atau laten dalam data matriks asli. SVD yang terpotong memberikan dasar yang bagus dimana semua low rank approximation yang lain dapat dinilai untuk akurasi kuantitif. Matriks A selalu merupakan suatu matriks nonnegatif, akan tetapi komponen singular tandanya (+/-) bercampur.Hilangnya struktur non negatif pada matriks berarti bahwa faktor dari SVD tidak memberikan interpretabilitas. Beberapa keuntungan dari SVD, antara lain: 1. Optimal. SVD yang dipotong menghasilkan approximation rank – k yang terbaik. 2. Cepat dan komputasi yang robust. 3. Faktorisasi yang unik. Inisialisasi tidak mempengaruhi algoritma SVD. 4. Orthogonalitas, menghasilkan basis vektor yang orthogonal dan mampu mengkonseptualisasi data asli sebagai vektor dalam ruang.
19
II.3.3 Non-Negative Matrix Factorization Non-Negative Matrix Factorization (NMF) adalah teknik reduksi dimensi linear yang berbeda dengan metode seperti Principal Component Analysis (PCA) karena batasan non-negatifnya. Batasan ini menghasilkan suatu representasi berbasis-bagian karena batasan ini hanya memperbolehkan penambahan, bukan pengurangan ataupun kombinasi keduanya (Okun, 2004). Basis data awal diekspresikan sebagai n x m matriks A dimana setiap kolomnya adalah sebuah vektor non-negatif dimensi n dari basis data aslinya (vektor m). Permasalahan umum NMF adalah mencari dua matriks baru W dan H hasil reduksi untuk memperkirakan matriks A dari produk WH. Setiap kolom dari W berisi vektor dasar sementara setiap kolom H berisi bobot yang diperlukan memperkirakan kolom A yang sesuai menggunakan vektor dasar dari W. . Dimensi matriks W dan H adalah n x r dan r x m. Biasanya, jumlah kolom matriks baru W dipilih sehingga r << m. Pemilihan nilai r umumnya tergantung aplikasi, bisa juga tergantung karakteriktik basis data tertentu dalam aplikasi. NMF menggunakan suatu prosedur iteratif untuk memodifikasi nilai awal dari
dan
supaya hasilnya WH mendekati A. Prosedur tersebut berhenti
ketika pendekatan error konvergen atau jumlah iterasi yang ditentukan tercapai. Dekomposisi NMF tidak unik, matriks W dan H bergantung pada penggunaan algoritma NMF dan perhitungan error digunakan untuk memeriksa konvergensi. Pendekatan untuk permasalahan NMF adalah memperkirakan matriks A dengan menghitung matriks W dan H untuk memperkecil perbedaan Frobenius norm A – WH. Secara matematis, dapat dirumuskan sebagai berikut :
20
adalah suatu matriks input non-negatif. dan H
dengan bilangan integer r < m. Tujuannya
adalah untuk memecahkan masalah optimasi. , dengan
,
0 dan
0 untuk setiap i dan j.
Algoritma NMF dapat dibagi menjadi 3 kelas, yaitu multiplicative update (MU), alternating lease squares (ALS), dan gradien descent GC) (Berry & Kogan, 2010). Algoritma umum NMF ditunjukkan dalam pseudocode sebagai berikut : Diberikan matriks A E Rmxn dengan k << min {m,n} for rep = 1 to maxrepetition do W = rand(m,k); H = rand(n,k); for i = 1 to maxiter do Lakukan langkah NMF update Cek kriteria terminasi end for end for Kebanyakan algoritma memerlukan faktor inisialisasi W dan H, tetapi beberapa algoritma (seperti algoritma ALS) hanya memerlukan 1 faktor inisialisasi. Langkah update untuk algorima Multiplicative update adalah berdasarkan fungsi objektif mean squared error. Kemudian menambahkan nilai
untuk
menghindari pembagian oleh nol. Nilai yang biasa digunakan untuk adalah 10-9. Berikut adalah langkah update untuk algoritma MU.
21
a. b.
Algoritma ALS hanya perlu untuk menginisialisasi faktor W, faktor H kemudian dihitung pada iterasi pertama. Setiap elemen non negatif yang dihasilkan dari komputasi least squared diset menjadi 0 untuk memastikan nonnegatifitas. Berikut adalah langkah update untuk algoritma ALS. -
Untuk H. WTWH = WTA; Set semua elemen negatif pada H menjadi 0.
-
Untuk W. HHTWT = HAT; Set semua elemen negatif pada W menjadi 0. Kedua algoritma MU dan ALS adalah iteratif dan bergantung pada
inisialisasi dari W dan H. Karena iterasi biasanya konvergen ke local minimum, beberapa algoritma berjalan dengan menggunakan inisialisasi acak yang berbeda untuk mendapatkan solusi yang terbaik. Kompleksitas perhitungan Algoritma MM adalah O(rnm) tiap iterasi (Pauca, Shahnaz, Berry, & Plemmons, 2004). Jika data ditambahkan ke basis data, data tersebut dapat ditambahkan secara langsung pada matriks dasar W dengan sedikit modifikasi pada matriks H, atau jika r diubah, maka iterasi selanjutnya dapat diterapkan mulai dari W dan H saat itu sebagai perkiraan awal. Keuntungan dari NMF adalah :
22
1. Sparsity dan nonnegativity. Faktorisasi mengatur properti ini pada matriks asli. 2. Reduksi dalam ruang penyimpanan. 3. Interpretabilitas. Basis vektor biasanya sesuai dengan properti konseptual data. Kekurangan dari NMF adalah masalah konvergen. Tidak seperti SVD dan faktorisasinya yang unik, NMF tidak mempunyai faktorisasi yang unik, karena algoritma NMF yang berbeda dapat konvergen ke local minima yang berbeda sehingga inisialisasi awal menjadi kritital.
II.4 Dual-Tree Complex Wavelet Transform Wavelet telah banyak digunakan dalam berbagai bidang. Wavelet menawarkan beberapa keuntungan sebagai alat untuk pengolahan citra, seperti formulasi
multiresolusi
yang
memungkinkan
pengurangan
kompleksitas
komputasi. Aspek ini sangat penting karena waktu retrival yang cepat diperlukan dalam proses retrival pada basis data yang besar. (Mumtaz, M, Hameed, & Jameel, 2008,). Selain itu, teknik ini cocok untuk representasi dan dekomposisi citra karena teknik ini mampu mendekomposisikan citra ke beberapa level menjadi citra dengan ukuran yang lebih kecil dan tetap mampu menyediakan informasi yang kuat dalam enam arah yang berbeda pada beberapa skala (Sai & Patil, 2011). Dual-Tree
Complex
Wavelet
Transform
(DT
CWT)
merupakan
pengembangan dari Discrete Wavlete Transform (DWT) dengan beberapa keuntungan. DT CWT dalam sebuah sinyal menggunakan dua pohon yang terpisah dari filter riil DWT di mana operasinya secara paralel untuk
23
menghasilkan bagian riil dan imajiner dari filter kompleks. Hal itu berarti bahwa jumlah dari koefisien pada output dari DT CWT adalah dua kali lipat dibandingkan dengan jumlah dari koefisien DWT. Penggandaan dari DT CWT adalah 2:1 untuk sinyal satu dimensi dan 4:1 untuk sinyal dua dimensi. Kelebihan utama dari DT CWT dibandingkan dengan DWT antara lain : 1. Shift Invariance DWT memiliki kekurangan pada shift invariance, yang berarti bahwa pergeseran kecil dalam sinyal input dapat menyebabkan variasi yang besar dalam distribusi energi antara koefisien transformasi wavelet pada skala berbeda. Masalah ini disebabkan oleh aliasing yang dilakukan karena subsampling pada setiap level wavelet. 2. Directional selectivity Kekurangan yang lainnya dari DWT adalah buruk dalam directional selectivity untuk feature diagonal. DWT 2 dimensi mendekomposisi gambar dengan arah horizontal (0o) atau HL, vertikal (90o) atau LH dan diagonal (±45o) atau HH. DWT tidak dapat membedakan antara dua arah diagonal yang berlawanan (±75o). Perbedaan utama antara DT CWT dan DWT yaitu DT CWT menggunakan 2 filter tree seperti yang ditunjukkan oleh gambar 2.4 (Corio et al, 2007).
24
Gambar 2.4 Struktur 2 Filter Tree DT CWT Sumber : Corio et al (2007)
Jika level atau skala dari output filter yang ditunjukkan dengan s maka himpunan koefisien highpass complex wavelet yang dihasilkan oleh DT CWT pada skala s adalah :
ys [k ] = ysa [k ] + jysb [k ] di mana
ysa [k ]
(2.1)
menunjukkan koefisien output dari tree A dan ysb [k ]
menunjukkan koefisien output dari tree B. Koefisien kompleks dapat ditulis dalam bentuk polar sebagai berikut :
ys [k ] = ms [k ]e jθ ,[k ]
(2.2)
di mana magnitude/besarnya setiap koefisien sebagai berikut :
ms = ysa2 [k ] + ysb2 [k ]
(2.3)
Dan fasenya :
⎛ ysa [k ] ⎞ ⎟⎟ [ ] y k ⎝ sb ⎠
θ s [k ] = tan −1⎜⎜
(2.4) 25
Jumlah dari koefisien kompleks yang dihasilkan pada skala s adalah
Ns di mana 2
N adalah jumlah sample sinyal input. Gambar 2.5 menunjukkan respon impuls dua dimensi dari rekonstruksi filter dalam 2D DT CWT. Setiap level transformasi menghasilkan koefisien kompleks yang sesuai dengan output filter 6 arah. Himpunan dari koefisien highpass wavelet kompleks dalam skala s dan arah d dapat ditulis sebagai berikut:
y s ,d [u , v ] = m s ,d [u , v ]e
jθ s , d [u , v ]
(2.5)
Untuk d = 1,2....,6. Variable u dan v menentukan lokasi koefisien komplek di tiap sub-band. Dengan menggunakan notasi matriks, koefisien dalam sebuah subband dilambangkan dengan Ys,d dan jumlah koefisien kompleks dalam tiap subband adalah N / 2 s × M / 2 s di mana N dan M adalah dimensi citra dalam piksel. Gambar 2.6 menunjukkan struktur output tipe wavelet untuk subband 6 arah pada setiap level DT CWT. Riil
15o
45 o
75 o
-75 o
-45 o
-15 o
Imajiner Gambar 2.5 Respon Impuls Dua Dimensi dari Rekonstruksi Filter 2D DT CWT Sumber : Corio et al (2007).
26
Gambar 2.6 Struktur Koefisien DT CWT untuk Dekomposisi 4 Level Sumber : Corio et al (2007).
II.5 Similarity Measure Setelah fitur diekstark dari setiap citra di basis data dan kueri, similarity measure menjadi isu yang krusial dalam retrival citra berbasis konten. Similarity measure merupakan proses perhitungan kemiripan atau perbedaan antara citra kueri dan citra basis data dengan menggunakan fitur. Urutan citra basis data kemudian diurutkan berdasarkan urutan ascending menurut perbedaan antara citra kueri dengan citra yang diretrif. Beberapa metode yang digunakan untuk menghitung perbedaan antara lain Minkowski-Form distance, quadratic form distance, Mahalonobis distance, Kullback-Leibler divergence dan JeffryDivergence (Sai & Patil, 2011). Euclidean distance, dikenal sebagai L2 distance, merupakan variasi dari Minkowski Form distance. Euclidean distance telah banyak digunakan dalam berbagai pendekatan retrival citra berbasis konten. Euclidean distance dijelaskan seperti di bawah ini.
27
d
|f
f |
∑
f
,
f
(1)
,
Di mana f adalah fitur kueri dan f adalah fitur dari basis data, dengan n adalah banyaknya jumlah fitur. Semakin kecil jarak (d) antara dua buah gambar, semakin besar derajat kesamaan antara dua buah gambar. Metode ini dapat dipakai ketika elemen fitur vektor citra sama penting dan fitur vektor tersebut independen terhadap satu sama lain. Euclidean distance telah digunakan dalam RCBK berbasis bentuk, retrival dengan menggunakan transformasi wavelet, dan lainnya. Oleh karena itu, Euclidean disatnce menjadi standar pengukuruan similarity dalam proses RCBK.
II.6 Precision dan Recall Precision dan Recall secara kolektif digunakan untuk mengukur efektivitas sistem retrival. Precision mengukur akurasi retrival. Precision didefinisikan sebagai jumlah rasio dari hasil retrival yang relevan dibanding jumlah total hasil retrival. Rumus dari precision adalah sebagai berikut:
Semakin tinggi precision, semakin tinggi performa retrival. Recall mengukur kapasitas untuk meretrif item dengan informasi yang relevan dari basis data. Recall didefinisikan sebagai jumlah rasio hasil retrival yang relevan dibanding jumlah total citra yang relevan di basis data (Lu, 1999). Semakin tinggi recall, semakin bagus performanya.
28
Dalam prakteknya, Precision dan recall dipertimbangkan secara bersamasama. Biasanya semakin tinggi recall, maka precision semakin rendah. Hal ini dikarenakan dalam prosesnya untuk meretrif semua item yang relevant dengan kueri, beberapa item yang tidak relevan juga ikut diretrif sehingga mengurangi precision. Suatu sistem dengan recall yang tinggi tetapi precision rendah berarti sitem tersebut akan banyak mengembalikan hasil item yang tidak relevan. Sebaliknya suatu sistem dengan precision yang tinggi tetapi recall yang rendah berarti bahwa banyak item yang relevan dengan kueri tidak diretrif. Jadi, sistem retrival yang bagus harus mempunyai recall dan precision yang seimbang. Oleh karena itu, untuk membandingkan performa antara dua sistem retrival, perbandingan precision dan recall diperlukan. Salah satu cara untuk melakukannya adalah menetapkan nilai precision dengan nilai recall antara 0 sampai 1 dan gambarkan dalam grafik nilai precision – recall untuk masingmasing sistem seperti pada gambar 2.7. Precision 1
B A
Recall (0,0)
1
Gambar 2.7 Grafik Precision – Recall.
29
Grafik pada gambar 2.7 menunjukkan bahwa suatu sistem dengan grafik yang lebih jauh dari aslinya mempunyai performa yang lebih tinggi. Sehingga pada grafik yang telah digambarkan menunjukkan bahwa sistem yang ditunjukkan pada grafik B mempunyai performa yang lebih baik dari sistem yang ditunjukkan pada grafik A.
30
