13
III METODOLOGI PENELITIAN 3.1 Kerangka Penelitian Penelitian dilakukan dalam lima tahapan utama, yaitu ekstraksi frame video, ekstraksi fitur SIFT dari seluruh frame, pembentukan kantong kata visual (“visual bag of words”), temu kembali dan evaluasi kinerja sistem (Gambar 5). Ekstrak frame Ekstraksi frame
video
Metode: Frame format *.jpg grayscale Tipe nilai digital piksel adalah double
Ekstrak frame frame Ekstraksi
Ekstrak fitur SIFT Ekstraksi fitur SIFT Metode: Detektor keypoint: Difference of Gaussian Deskriptor: SIFT
Ekstrak fitur Ekstraksi fiturSIFT SIFT
Kantong deskriptor SIFT
Pembentukan BoW & inverted file Metode: Clustering k-means Jarak Euclidean
Pembentukan Kantong kata visual (“visualBag bag of words”) (Visual Words)
Inverted files
Sistem temu kembali Metode: idft tf*idft sim(q,d)
Vector Space Model
Evaluasi sistem
Recall, Recall Precision, Precision F-measure
Gambar 5 Kerangka pemikiran penelitian
14
Kelima tahapan tersebut terdiri atas beberapa proses yang saling berhubungan, yaitu: 1 Ekstraksi frame video. Pada tahap ini dilakukan ekstraksi frame video menjadi citra grayscale berformat .jpg. Frame yang diekstraksi setiap detik adalah sebanyak tiga frame/detik. Tipe data nilai digital piksel dikonversi menjadi format double dalam selang 0 dan 1. 2 Ekstraksi fitur SIFT. Setelah seluruh frame video berhasil diekstraksi, kemudian dari setiap frame dilakukan pendeteksian fitur SIFT. Ada dua matriks fitur SIFT (Vedaldi 2007), yaitu: a
Matriks keypoint dengan ukuran 4×k, matriks ini berisi informasi lokasi (koordinat x, y di dalam frame), skala dan arah orientasi keypoint.
b
Matriks deskriptor dengan ukuran 128×k, dimana k adalah jumlah deskriptor yang berhasil dideteksi pada frame tersebut.
Deskriptor yang berhasil diekstraksi dari seluruh frame yang ada kemudian disimpan ke dalam sebuah matriks besar yang berukuran 128×(k*N), dimana N adalah jumlah frame yang diproses. 3 Pembentukan Bag of Words (BoW). Pada tahap ini dilakukan kuantisasi seluruh fitur SIFT yang sudah berhasil diekstraksi pada tahap 2 seperti terlihat pada ilustrasi Gambar 6. Kuantisasi dilakukan dengan menggunakan teknik clustering k-means. Setiap titik pusat cluster dianalogikan sebagai kata visual yang ada pada sebuah frame.
a) Cuplikan klip video
b) Frame dengan deskriptor SIFT
c) Kantong kata visual (BoW)
Gambar 6 Ilustrasi proses ekstraksi fitur SIFT dan pembentukan BoW dari sebuah klip video.
15
4 Sistem temu kembali, mencakup kueri citra objek/frame sebagai masukan. Vector Space Model digunakan untuk mengukur tingkat kemiripan antara kueri dengan frame yang ada. 5 Evaluasi kinerja sistem, pengukuran hasil temu kembali berdasarkan pada nilai precision, recall dan F-measure. 3.2 Alat Bantu Penelitian Peralatan yang digunakan untuk melaksanakan penelitian dibagi menjadi dua, yaitu perangkat keras dan perangkat lunak. Perangkat keras berupa satu unit komputer dengan spesifikasi prosesor Intel dual core, RAM 2 GB, Harddisk 80 GB dengan layar beresolusi 1280 x 800 piksel. Perangkat lunak yang diperlukan untuk perancangan dan pengujian sistem adalah MATLAB 7 dengan platform sistem operasi Microsoft Windows XP. 3.3 Tata Laksana Penelitian 3.3.1
Ekstraksi Frame Video Data merupakan data sekunder berupa cuplikan video diambil dari
situs internet www.youtube.com.
Video berformat *.flv kemudian
dikonversi ke dalam format .mpeg dengan frame rate sebesar 30 frame/detik. Frame diekstraksi sebanyak tiga frame/detik, kemudian frame tersebut dikonversi menjadi citra abu-abu dan disimpan dalam format *.jpg (Gambar 7). 3.3.2
Ekstraksi Fitur SIFT Fitur SIFT diekstraksi dari setiap frame yang sudah disimpan ke dalam
format *.jpg. Fitur SIFT terdiri atas dua komponen, yaitu: 1
Keypoints SIFT
Keypoints SIFT merupakan matriks berukuran 4 × k, dimana k adalah jumlah deskriptor yang berhasil diekstraksi dari sebuah citra. Adapun 4 elemen tersebut antara lain data: KEYPOINT(1:2,k), elemen (X,Y) merupakan pusat region deskriptor ke-k, KEYPOINT(3,k), skala SIGMA ( ) region deskriptor ke-k, KEYPOINT(4,k), orientasi THETA
region deskriptor ke-k.
16
2
Deskriptor SIFT
Deskriptor SIFT merupakan matriks berukuran 128×k, dimana setiap kolom menyimpan 1 set deskriptor (128 elemen). Sebuah set deskriptor merupakan histogram yang terdiri atas 8 selang kelas, dan setiap deskriptor berisikan array 4 histogram yang mengelilingi keypoint. Dengan demikian vektor fitur SIFT berisi 128 elemen (4 × 4 × 8). Input Video
frame Ekstrak frame Ekstraksi
If k < Jum Frame Jumlah Frame
Tidak NO
1. BoW 2. Temu Kembali 3. Evalusi Kinerja Sistem
YES Ya
Konversi frame ke dalam format grayscale (tipe data double)
Normalisasi nilai elemen matriks frame [0, 1]
Ekstrak deskriptor Ekstraksi deskriptorSIFT SIFT [SIFT_Frame, [SIFT_Frame, SIFT SIFT Deskriptor] Deskriptor]
Tulis Deskriptor Simpan deskriptor ke dalam tabel DWH
Visualisasi SIFT Deskriptor
Gambar 7 Alur proses ekstraksi deskriptor SIFT dari media video.
17
3.3.3
Pembentukan Bag of Words (BoW) Kuantisasi fitur akan memberikan gambaran distribusi kata visual yang
ada di dalam video. Sebaran ini merupakan inverted index dari kata visual terhadap frame yang ada di dalam video. Gambar 8 menunjukkan ilustrasi pembentukan kantong kata visual (BoW):
Deteksi dan ekstraksi fitur SIFT.
Pembentukan kata visual dengan kuantisasi vektor sekaligus pembentukan kantong kata visual (BoW).
Gambar 8 Proses umum pembentukan kantong kata visual (BoW). BoW dibentuk dengan melakukan kuantisasi fitur SIFT yang sudah berhasil diekstraksi. Kuantisasi dilakukan dengan teknik clustering k-means (Gambar 9).
kuantisasi vektor
Gambar 9 Proses kuantisasi fitur SIFT dalam pembentukan kantong kata visual (BoW).
18
3.3.4
Temu Kembali Proses temu kembali citra dilakukan melalui penghitungan indeks
kemiripan (similarity) antara frame dan citra kueri. Kemiripan ditentukan dengan menggunakan model VSM, semakin tinggi indeks kemiripan maka semakin tinggi hubungan citra kueri dengan frame yang berhasil ditemukembalikan (Gambar 10).
Kueri
Penghitungan vektor tf*idf VSM
Kantong Fitur SIFT
Temu kembali berdasarkan indeks kemiripan vektor kueri dengan matriks idf
Frame hasil temu kembali
Gambar 10 Tata laksana temu kembali objek.
3.3.5
Evaluasi Kinerja Sistem Evaluasi kinerja sistem dilakukan penilaian tingkat keefektifan proses
temu kembali terhadap sejumlah koleksi. Pengujian dilakukan dengan menghitung nilai recall, precision dan F-measure dari proses temu kembali berdasarkan penilaian relevansinya. Penentuan relevansi hasil temu kembali dibuat berdasarkan frame yang ada di dalam video.
