Ekstraksi Keyframe dengan Entropy Differences untuk Temu Kembali Konten Video berbasis Speeded-Up Robust Feature M Misbachul Huda
Yenita Dewi Nurseha
Adrianus Yoza Aprilio
Institut Teknologi Sepuluh Nopember Institut Teknologi Sepuluh Nopember Institut Teknologi Sepuluh Nopember (ITS) Surabaya (ITS) Surabaya (ITS) Surabaya
[email protected]
[email protected]
ABSTRAK Salah satu masalah dalam pemilihan keyframe pada temu kembali konten video atau Content Based Video Retrieval (CBVR) adalah penentuan keyframe terbaik yang dapat mewakili konten video. Jumlah keyframe yang terlalu banyak akan meningkatkan beban komputasi, namun jumlah keyframe yang terlalu sedikit akan mengurangi akurasi CBVR. Penelitian ini mengusulkan sebuah metode baru untuk CBVR berbasis Speeded-Up Robust Feature (SURF) dengan mengadaptasi logika metode Entropy Differences (ED) untuk mengekstraksi keyframe secara efektif. ED dioptimalkan untuk proses ekstraksi keyframe dengan menghitung nilai entropi dari setiap frame pada video. Algoritma SURF digunakan sebagai metode descriptor fitur pada citra keyframe untuk proses CBVR. Berdasarkan pengujian, nilai F1 dari metode yang diusulkan mencapai rata-rata 60% dan rata-rata waktu per pencarian 5 ms.
Kata Kunci CBVR, Ekstraksi keyframe, Entropy Differences, SURF descriptor.
1. PENDAHULUAN Perpaduan antara perkembangan kecepatan komputasi, kapasitas penyimpanan, dan teknologi multimedia menjadi beberapa sebab bertambahnya jumlah informasi yang dapat diakses pada internet. Perkembangan ini perlu diimbangi dengan teknik pengorganisasian informasi sehingga dapat memenuhi kebutuhan pengguna akan adanya sistem temu kembali informasi yang efektif sesuai dengan query pengguna. Tanpa adanya mekanisme penemuan kembali informasi yang efektif, pengguna akan mengalami kesulitan dalam menemukan informasi yang diharapkan. Temu kembali konten video atau Content Based Video Retrieval (CBVR) merupakan metode temu kembali berkas video berbasis konten berdasarkan fitur visual dari video yang selama beberapa tahun ini banyak dikembangkan [1]. Konten dalam konteks ini meliputi warna, tekstur, bentuk objek, atau informasi lainnya yang dapat diperoleh untuk merepresentasikan frame citra pada video. Tanpa adanya kemampuan dalam mengamati konten video, sistem pencari harus mengandalkan metadata seperti kata kunci atau deskripsi video yang dapat menyebabkan kesalahan apabila kata kunci dan deskripsi tidak sesuai dengan isi video. CBVR dapat membantu pengguna dalam menemukan video yang sesuai karena didasarkan pada informasi konten. Beberapa pendekatan yang digunakan untuk mengekstraksi informasi konten pada video antara lain histogram warna, informasi bentuk objek, tekstur, dan analisa teks.
30
[email protected]
Dalam CBVR, terlebih dahulu dilakukan tahap praproses untuk setiap video. Tahap praproses terdiri dari proses segmentasi, deteksi shot, dan ekstraksi keyframe. Keyframe dari sebuah video merupakan representasi dari setiap adegan yang ada pada video tersebut. Salah satu masalah dalam pemilihan keyframe adalah penentuan keyframe terbaik yang dapat mewakili konten adegan pada video. Jumlah keyframe yang terlalu banyak akan meningkatkan beban komputasi, namun jumlah keyframe yang terlalu sedikit akan mengurangi akurasi CBVR. Salah satu metode ekstraksi keyframe yang handal dalam menentukan keyframe dengan tepat adalah metode Entropy Differences (ED) yang diusulkan oleh Mentzelopoulo dan Psarrou [2]. Dalam penelitian tersebut, nilai entropi dari setiap frame pada video digunakan untuk mengidentifikasi keyframe. Kelebihan dari metode tersebut terletak pada akurasi hasil segmentasi video yang tinggi dengan menggunakan pendekatan semantik berbasis nilai entropi untuk mewakili objek yang dominan pada setiap frame. Nilai entropi dari dari setiap frame digunakan untuk menentukan keyframe yang dapat mewakili konten video. Sistem manajemen berkas video secara menyeluruh mencakup 3 tahap, yaitu penyimpanan, pengindeksan, dan penemuan kembali. Pengindeksan merupakan tahap yang penting dalam CBVR. Dari metode pengindeksan yang umum digunakan, pendekatan berbasis konten merupakan salah satu metode yang dikenal lebih efisien. Speeded-Up Robust Features (SURF) merupakan sebuah algoritma yang cepat dan akurat untuk proses mendeteksi descriptor lokal dari kesamaan representasi citra invariant [3]. Asha dan Sreeraj [1] mengusulkan sebuah metode CBVR menggunakan algoritma SURF sebagai descriptor fitur pada citra keyframe. Keyframe dari setiap video diekstraksi menggunakan pendekatan histogram thresholding. Dalam metode yang diusulkan tersebut, descriptor SURF sebagai fitur digunakan dalam mencocokkan kemiripan klip keyframe pada video dengan klip query. Dari nilai kemiripan yang dihasilkan, video kemudian diurutkan dan hanya 4 video dengan urutan teratas yang ditampilkan sebagai hasil. Penelitian ini mengusulkan sebuah metode CBVR baru dengan mengadaptasi logika dari metode ED untuk ekstraksi keyframe dan algoritma SURF sebagai descriptor fitur pada keyframe. ED digunakan untuk mengekstraksi keyframe yang secara efektif mampu merepresentasikan konten video. SURF digunakan sebagai metode pendeteksi fitur descriptor dari setiap keyframe untuk pencocokan kemiripan dengan klip query.
M Misbachul Huda, Yenita Dewi Nurseha, Adrianus Yoza Aprilio
Segmentasi Ekstraksi fitur
Video
Pencocokan fitur
Ekstraksi keyframe
Praproses
Pengurutan
Query dan Hasil
Gambar 1. Kerangka Kerja Proses CBVR
2. PENELITIAN TERKAIT Pada penelitian [4], dibahas beberapa metode yang digunakan untuk CBVR. Dalam mendeteksi batasan antar shot, fitur-fitur yang umum diekstraksi antara lain histogram warna [5] [6], histogram blok citra [7], dan transformasi fitur skala invariant. [5] menggunakan alpha-trimmed average histograms yang mengombinasikan frame atau histogram citra dengan operasi filter yang mampu menghasilkan histogram warna yang robust, sehingga dapat mengeliminasi efek variasi warna dan kecerahan pada representasi warna. [6] menganalisa properti invariant dari descriptor warna, dengan taksonomi berdasarkan properti invariant dengan transformasi photometric. Penelitian tersebut juga membahas mengenai perubahan intensitas dan efeknya terhadap warna-warna tertentu dalam pengenalan kategori adegan. Penelitian lain dilakukan pada [7] yang membahas beberapa model Block Truncating Coding (BTC) dan membandingkan dengan pengembangan-pengembangannya, yakni Static Thepade's ternary BTC (STTBTC), Dynamic Thepade's ternary BTC (DTTBTC), dan Thepade's sorted ternary BTC (TSTBTC). BTC menggunakan pendekatan statistik terhadap properti blok citra dan bitmap biner untuk mendapatkan properti/metadata citra dan menghitung threshold. STTBTC dan DTTBTC menambahkan sebuah variabel N untuk perhitungan komponen threshold. Bedanya pada STTBTC, variabel N bersifat statik. Sementara pada DTTBTC, variabel N bersifat dinamik. TSTBTC membagi frame video menjadi 3 bagian (awal-tengah-akhir), dan masing-masing bagian tersebut dirata-rata untuk menghasilkan fitur yang mewakili frame tersebut. Untuk setiap shot, beberapa frame dipilih untuk merepresentasikan konten dari sebuah shot. Zhang [8] menggunakan histogram warna untuk menentukan perbedaan antara frame dengan keyframe sebelumnya untuk dapat mengekstraksi keyframe dalam video. Yu [9] menggunakan pendekatan clustering dengan algoritma Fuzzy K-Means dalam ruang fitur warna. Dalam penelitiannya, seluruh frame dikelompokkan dalam sejumlah cluster dan frame dengan jarak terdekat dengan titik pusat cluster dipilih sebagai keyframe menggunakan algoritma Fuzzy K-Means. Penelitian lain secara sederhana menentukan keyframe dari shot dengan memilih frame paling awal dan frame paling akhir sebagai keyframe. Mentzelopoulo dan Psarrou [2] dalam penelitiannya mengusulkan sebuah metode segmentasi video yang handal dalam menentukan keyframe dengan tepat dari suatu video, yaitu metode ED. Metode yang diusulkan menggunakan perhitungan nilai entropi dari objek dominan pada konten video. Kelebihan dari metode tersebut terletak pada tingginya tingkat
akurasi segmentasi video menjadi keyframe menggunakan pendekatan semantik dari konten video.
dengan
Pada penelitian ini, sistem CBVR yang diusulkan menggunakan algoritma ED dalam mendeteksi batasan shot dan mengekstraksi keyframe dari video. Fitur yang diekstraksi dari keyframe adalah descriptor SURF. Untuk membandingkan kesesuaian antar video, digunakan perhitungan kemiripan jarak Euclidean yang dapat membantu menemukan video dengan selisih perbedaan terkecil. Dari nilai kemiripan yang dihasilkan, video kemudian diurutkan dan hanya 5 video dengan urutan teratas yang ditampilkan sebagai hasil.
3. METODE Secara umum, kerangka kerja dari proses CBVR ditampilkan dalam Gambar 1. Proses CBVR terdiri dari 3 tahap, yaitu tahap praproses, ekstraksi fitur, dan pencocokan fitur. Setiap video yang ada pada media penyimpanan terlebih dahulu melalui tahap praproses yang terdiri dari modul segmentasi video dan ekstraksi keyframe. Hasil dari tahap praproses adalah himpunan keyframe yang telah diekstraksi dari video. Dari himpunan keyframe yang mewakili konten video ini, kemudian dilakukan tahap ekstraksi fitur menggunakan descriptor SURF. Descriptor hasil ekstraksi ini kemudian disimpan dalam pustaka model data. Pada proses penemuan kembali, pengguna memberikan klip/gambar sebagai query masukan. Klip query kemudian melalui tahap ekstraksi fitur menggunakan descriptor SURF untuk mendapatkan fitur descriptornya. Video pada pustaka model data diurutkan berdasarkan kemiripan descriptor video dengan descriptor query. Video yang ditampilkan sebagai hasil pencarian dipilih berdasarkan urutan peringkat kemiripan.
3.1 Segmentasi Video Segmentasi video merupakan proses partisi video ke dalam bagian yang berarti yang disebut sebagai segmen. Segmentasi dapat bersifat temporal, spasial, atau spasio-temporal. Segmentasi temporal membagi video menjadi adegan, shot, atau frame. Pada penelitian ini, setiap video V dengan jumlah frame n direpresentasikan sebagai dengan disegmentasi menjadi frame dan dikonversi menjadi elemen dasar .
3.2 Ekstraksi Keyframe Ekstraksi keyframe merupakan proses yang dilakukan secara otomatis untuk mendeteksi frame kunci dari suatu video. Beberapa frame yang menjadi batas antar adegan yang berurutan diseleksi untuk dipilih sebagai keyframe. Keyframe didefinisikan sebagai frame yang dapat mewakili karakter beberapa frame pada sebuah adegan. Frame pada adegan yang
Jurnal Cybermatika | Vol. 2 No. 2 | Desember 2014 | Artikel 5
31
sama cenderung memiliki karakter visual yang mirip. Dengan adanya keyframe yang dapat mewakili konten penting dalam suatu adegan, maka jumlah informasi yang perlu disimpan untuk sebuah video selama proses indeksing, penyimpanan, dan penemuan kembali menjadi lebih ringkas. Metode ekstraksi keyframe yang diusulkan pada penelitian ini mengadaptasi logika dari metode ED. ED menggunakan nilai entropi dari frame sebagai operator lokal dalam mengidentifikasi citra. Distribusi entropi pada citra dengan nilai paling besar dipilih untuk mendeskripsikan objek yang penting dari seluruh frame yang berurutan pada suatu adegan. Dengan ini, perubahan objek yang terjadi pada suatu video akan ikut mengubah daerah dengan nilai entropi terbesar dan mempengaruhi informasi semantik dari urutan adegan dalam video. Proses ekstraksi keyframe menggunakan ED dimulai dengan memilih frame pertama pada video sebagai keyframe awal dari seluruh frame yang dihasilkan dari tahap segmentasi. Untuk dapat mengatasi adanya kemungkinan perubahan tingkat kecerahan antar frame, dilakukan proses kuantisasi warna dengan mengubah frame citra berwarna menjadi citra abu-abu. Kemudian, nilai entropi dari derajat keabuan k pada frame f berukuran M baris dan N kolom dihitung dengan mempertimbangkan nilai yaitu probabilitas kemunculan derajat keabuan dan nilai
yaitu logaritma negatif dari
probabilitas . Nilai probabilitas dihitung dengan menggunakan nilai sebaran derajat keabuan dari histogram citra . Nilai entropi suatu derajat keabuan citra dapat dihitung dari dengan persamaan: .
(1)
Nilai dan menggunakan persamaan:
masing-masing
dan
dihitung
(2) (3)
Langkah selanjutnya adalah mengurutkan nilai-nilai entropi derajat keabuan k dengan nilai yang terbesar terlebih dahulu. Untuk setiap frame, nilai-nilai entropi yang telah diurutkan kemudian diseleksi dengan memilih entropi yang berada pada urutan diatas threshold, yaitu nilai entropi pada urutan 30% teratas dari keseluruhan entropi. Nilai-nilai entropi tersebut kemudian disimpan dalam himpunan . Setelah didapatkan nilai-nilai entropi , selanjutnya dilakukan perhitungan kemiripan karakter visual antar frame dengan memilih frame yang terletak pada urutan selanjutnya untuk diproses. Untuk setiap nilai-nilai entropi yang merupakan anggota himpunan , dihitung selisih nilai entropi level keabuan m dengan nilai entropi level keabuan m pada frame di urutan selanjutnya. Perhitungan selisih entropi antar frame dilakukan menggunakan persamaan :
, (4) dimana merupakan jumlah banyaknya nilai entropi yang berada pada urutan 30% teratas, merupakan frame yang diproses, dan adalah frame pada urutan selanjutnya. Apabila selisih dari perbedaan entropi lebih besar dari 23% maka terjadi perubahan konten pada urutan frame. Keyframe saat ini disimpan dalam daftar keyframe dan frame pada urutan selanjutnya dipilih sebagai keyframe baru untuk mewakili
32
adegan selanjutnya. Proses kemudian berulang dari tahap kuantisasi warna sampai tahap perhitungan selisih nilai entropi. Namun apabila selisih dari perbedaan entropi tidak lebih besar dari 23% maka dilakukan pengecekan apakah frame pada urutan selanjutnya merupakan frame terakhir. Jika frame pada urutan selanjutnya merupakan frame terakhir, maka proses ekstraksi keyframe berhenti. Namun apabila frame pada urutan selanjutnya bukan frame trakhir, maka proses berulang dari tahap perhitungan kemiripan dengan frame pada urutan selanjutnya sampai tahap perhitungan selisih nilai entropi.
3.3 Ekstraksi Fitur SURF merupakan sebuah algoritma yang cepat dan akurat untuk proses mendeteksi descriptor lokal dari kesamaan representasi citra invariant. Descriptor adalah sebuah ciri-ciri dari suatu citra berdasarkan aturan tertentu dari suatu algoritma. SURF menggunakan citra integral untuk meningkatkan kecepatan komputasi. Algoritma ini didasarkan pada kerangka SURF dari hasil disertasi Herbert Bay [7]. Penggunaan SURF pada CBVR sebelumnya telah diteliti oleh Asha et al. [1]. Secara umum algoritma ini terdiri dari tiga tahap utama. Tahap pertama adalah proses pendeteksian keypoint. Pendeteksian keypoint dilakukan berdasarkan pada matrik Hessian. Tahap ini akan memberikan luaran berupa keypoint, yaitu interest point yang dianggap valid karena sudah berada dibawah batas nilai yang ditetapkan. Determinasi dari matrik Hessian digunakan untuk menentukan lokasi dan skala untuk menyeleksi kandidat interest point. Kandidat interest point akan dianggap valid apabila mempunyai nilai di bawah batas nilai yang diberikan untuk kemudian dilakukan perbaikan pada box-space. Tahap kedua adalah proses pendeskripsian keypoint. Pendeskripsian keypoint dibagi menjadi dua bagian. Bagian pertama adalah menetapkan orientasi berdasarkan informasi dari daerah melingkar di sekitar interest point yang terdeteksi. Bagian kedua adalah membuat grid sebesar 64 (8x8) yang digunakan untuk menampung descriptor yang berkorespondensi dengan histogram pada Haar Wavelet. Tahap ini selanjutnya diikuti oleh tahap ketiga, yaitu pencocokan descriptor. Tahap terakhir dari SURF ini adalah tahap pembandingan kecocokan descriptor antar dua gambar. Perbandingan kecocokan dihitung menggunakan kaedah jarak Euclidean antara semua pasang descriptor. Kecocokan didasarkan pada selisih jarak dengan piksel tetangga.
3.4 Pencocokan Fitur Pada sistem yang dibangun, algoritma k-Nearest Neighbour digunakan sebagai metode pencocokan fitur dengan nilai k yang digunakan adalah 5. Evaluasi tingkat kemiripan dihitung menggunakan jarak Euclidean. Dari nilai kemiripan yang didapatkan, jarak kemudian diurutkan dan k video dengan tingkat kemiripan tertinggi ditampilkan sebagai hasil.
4. PENGUJIAN DAN PEMBAHASAN Pada bab ini akan dijelaskan mengenai pengujian yang dilakukan untuk mengukur performa dari metode yang diusulkan pada penelitian ini. Pengujian yang dilakukan mencakup pengujian efisiensi yang diusulkan dan pengujian komputasi. Pembahasan akan dibagi menjadi tiga bagian, bagian pertama menjelaskan lingkungan pengujian dan data yang digunakan dalam pengujian, bagian kedua menjelaskan hasil pengujian efisiensi, dan bagian ketiga menjelaskan hasil pengujian komputasi.
M Misbachul Huda, Yenita Dewi Nurseha, Adrianus Yoza Aprilio
piksel dan ukuran piksel maksimal 1280 piksel. Rata-rata banyaknya frame per detik (fps) dari seluruh video adalah 25 fps.
4.2 Pengujian Efisiensi Temu Kembali Informasi Video Berbasis Konten Pengujian dilakukan untuk mengetahui efisiensi dalam menemukan informasi dari video berbasis konten. Dari 30 data video yang digunakan, seluruh video diproses menggunakan metode ekstraksi keyframe dan ekstraksi fitur yang diusulkan. Fitur-fitur yang didapatkan dari setiap video kemudian disimpan dalam suatu basis data. Pengujian dilakukan dengan menggunakan 9 citra query. Setiap query telah dilengkapi dengan informasi groundtruth video yang memiliki konten yang relevan dengan query.
Gambar 2. Keyframe pada Video
Proses temu kembali informasi diawali dengan mengambil keyframe dari video-video yang telah didapat dari proses sebelumnya seperti yang ditunjukkan pada Gambar 2. Keyframe tersebut di query dengan menggunakan citra masukan. Proses query dilakukan dengan mencocokkan descriptor antara citra masukan dengan keyframe. Descriptor didapatkan dari hasil pengolahan citra dengan menggunakan metode SURF. Hasil kecocokan antara citra masukan dan keyframe yang melebihi ambang batas tertentu akan ditampilkan sebagai hasil temu kembali. Video yang mengandung keyframe yang memiliki kecocokan dengan citra inputan akan ditambilkan sebagai hasil akhir dari query temu kembali. Video yang digunakan sebagai dataset dipecah menjadi frame kemudian di ekstrak menjadi keyframe. Seperti yang ditunjukkan pada Tabel 1, tujuh dari 30 video yang digunakan, metode yang diusulkan mampu memberikan rasio kecil dari keyframe terhadap frame video. Hal ini menunjukkan keyframe yang dihasilkan dapat mewakili 9 frame pada video. Contoh ekstraksi frame menjadi keyframe dapat dilihat pada Gambar 3 dan 4. Dari 9 frame yang ada pada Gambar 3 dapat diringkas menjadi keyframe pada Gambar 4.
Gambar 3. Contoh Frame Video
Pengujian efisiensi dilakukan dengan menghitung nilai F1 yang didapatkan dari perhitungan nilai presisi dan recall dari hasil temu kembali konten video dengan persamaan :
F1 = 2 .
(5)
Pengujian yang dilakukan sebanyak 9 kali pencarian dimaksudkan untuk mendapatkan hasil yang stabil. Hasil pengujian dapat dilihat pada Tabel 2. Pada hasil pengujian didapat bahwa pada metode yang diusulkan memiliki nilai F1 sebesar 60%, presisi 60%, dan recall 60%.
Tabel 1. Contoh Spesifikasi Data
4.1 Lingkungan Pengujian dan Data Uji
video 1
400
61
Banyaknya frame per detik (fps) 30
Pengujian telah dilakukan pada komputer berbasis Windows 8.1 x64 dengan spesifikasi CPU i5 (2.0 GHz), dan 4GB RAM. Metode diimplementasikan dengan menggunakan bahasa pemrograman C#.
video 2
400
59
30
0.147
video 3
300
27
30
0.090
video 4
255
8
30
0.031
Data yang digunakan adalah 30 video yang diakses dari situs video Youtube pada tanggal 17 Desember 2014. Video-video dikelompokkan menjadi 3 kategori dengan masing-masing kategori terdiri dari 10 video yang berbeda. Kategori video antara lain video animasi, iklan televisi, dan dokumentasi kampanye partai politik. Masing-masing video memiliki durasi 30-60 detik dengan ukuran file bervariasi antara 1 – 15 MB. Video yang digunakan memiliki ukuran piksel minimal 360
video 5
204
23
30
0.112
video 6
246
32
30
0.130
video 7
473
69
30
0.145
Gambar 4. Contoh Keyframe
Video
Jumlah frame
Jumlah keyframe
Jurnal Cybermatika | Vol. 2 No. 2 | Desember 2014 | Artikel 5
Rasio 0.152
33
4.3 Pengujian Waktu Komputasi CBVR Tabel 2. Hasil Pengujian F1 No
Judul
Presisi
Recall
F1
1
query 1
0.4
0.4
0.4
2
query 2
0.2
0.25
0.22
3
query 3
1
1
1
4
query 4
1
1
1
5
query 5
1
1
1
6
query 6
0.4
0.4
0.4
7
query 7
0.4
0.4
0.4
8
query 8
0.2
0.2
0.2
9
query 9
0.8
0.8
0.8
0.6
0.6
0.6
Rata-rata
Pengujian dilakukan untuk mengetahui waktu komputasi metode yang diusulkan dalam ekstraksi keyframe dan pencarian query. Dalam pengujian performa, pengujian waktu komputasi dibagi menjadi dua sub pengujian. Perngujian yang pertama dilakukan untuk mengetahui waktu komputasi ekstraksi keyframe dari 50 video. Pengujian yang kedua dilakukan untuk mengetahui waktu komputasi pencarian pada CBVR dengan melibatkan 100 pencarian. Hasil pengujian waktu ekstraksi keyframe ditunjukkan pada Gambar 5. Pada hasil pengujian dapat diketahui semakin banyak video yang digunakan, semakin tinggi waktu yang diperlukan. Dari hasil pengujian didapat rata-rata waktu ekstraksi keyframe metode yang diusulkan sebesar 537 ms per video yang mempunyai durasi 60 detik. Hasil pengujian waktu pencarian CBVR ditunjukkan pada Gambar 6. Pada hasil pengujian dapat diketahui semakin banyak pencarian yang digunakan, semakin tinggi waktu yang diperlukan. Dari hasil pengujian didapat rata-rata waktu pencarian CBVR metode yang diusulkan adalah 5 ms. Hasil pengujian waktu komputasi yang dilakukan menunjukkan bahwa metode yang diusulkan memiliki waktu komputasi ratarata sebesar 5 ms. Hal ini menjadi kelebihan dalam sistem CBVR yang diusulkan. Namun dalam proses ekstraksi keyframe waktu yang dibutuhkan jauh lebih besar, hal tersebut terjadi karena banyaknya frame yang harus diolah. Hal ini menjadi kekurangan karena semakin banyak frame yang diolah waktu komputasi akan menjadi lebih besar. Permasalahan ini membutuhkan penyelesaian agar tidak semua frame perlu diolah untuk diseleksi menjadi keyframe sehingga beban komputasi menjadi berkurang.
Gambar 5. Grafik Waktu Ekstrasi Keyframe
5. KESIMPULAN Penentuan keyframe dalam CBVR menjadi permasalahan yang banyak diteliti. Penentuan keyframe yang optimal memiliki peranan yang penting dalam CBVR. Penentuan keyframe menjadi penting dalam CVBR untuk mereduksi waktu pencarian dengan tetap mempertimbangkan kualitas hasil pencarian. Hal tersebut dapat dibuktikan dari kualitas hasil pencarian dan waktu komputasi yang diperlukan.
Gambar 6. Grafik Waktu Komputasi Pencarian CBVR Hasil rata-rata 60% untuk nilai F1 didapatkan karena kualitas beberapa jenis video memiliki noise yang tinggi, serta bergantung pada kemampuan SURF dalam mengenali descriptor pada ekstraksi fitur pada keyframe. Descriptor pada SURF memiliki kemungkinan dalam mengenali keypoint yang sama pada dua objek yang sebenarnya berbeda. Hal ini menjadi kendala pada proses query. Dari pengujian efisiensi yang telah dilakukan, metode yang diusulkan menemui kendala dalam mendeteksi keyframe pada video yang memiliki gradasi warna dalam suatu adegan. Jumlah keyframe yang dihasilkan menjadi sama dengan jumlah frame yang ada. Hal ini mempengaruhi efisiensi dalam query CBVR. Waktu pencarian data menjadi lebih besar karena menggunakan jumlah keyframe yang lebih banyak. Secara sederhana, metode ini belum dapat menangani dengan baik video yang mengandung adegan dengan gradasi warna didalamnya.
34
Dari hasil evaluasi yang dilakukan pada 30 sampel video, disimpulkan bahwa metode ekstraksi keyframe dengan ED untuk temu kembali konten video berbasis SURF dapat mengembalikan hasil pencarian dengan baik. Pendekatan ED yang dioptimalkan pada penelitian ini untuk penentuan keyframe dapat memberikan solusi terhadap masalah pemilihan keyframe pada CBVR dari suatu video secara optimal. Berdasarkan pengujian yang dilakukan, nilai F1 dari metode yang diusulkan mencapai rata-rata 60% dengan presisi dan recall mencapai 60%. Performa dari metode yang diusulkan memiliki waktu pencarian rata-rata sebesar 5 ms dengan waktu untuk ekstrasi keyframe pada video sebesar 537 ms. Pengembangan selanjutnya yang dapat dilakukan dari penelitian ini adalah dengan mengombinasikan fitur histogram pada Entropi dengan deteksi objek. Penentuan keyframe yang efektif dapat membuat representasi dari video menjadi akurat. Penambahan fitur objek juga dapat dilakukan untuk membantu SURF dalam mengangkap fitur lebih banyak lagi. Namun untuk CBVR yang membutuhkan waktu komputasi yang rendah, hal ini menjadi tantangan tersendiri. Selain itu, diperlukan sebuah metode baru yang dapat mendeteksi potensi keyframe dalam video agar tidak semua frame diekstrak dan diseleksi untuk menjadi keyframe.
M Misbachul Huda, Yenita Dewi Nurseha, Adrianus Yoza Aprilio
6. DAFTAR PUSTAKA [1] S. Asha and M. Sreeraj, "Content Based Video Retrieval Using SURF Descriptor," in Advances in Computing and Communications (ICACC), 2013 Third International Conference on. IEEE, 2013. [2] M. Markos and P. Alexandra, "Key-frame extraction algorithm using entropy difference," in Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, ACM, 2004. [3] B. Herbert, T. Tinne and V. G. Luc, "Surf: Speeded up robust features," Computer Vision–ECCV 2006, pp. 404417, 2006. [4] W. Hu, "A survey on visual content-based video indexing and retrieval," Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions, vol. 41, no. 6, pp. 797-819, 2011. [5] A. M. Ferman, "Robust color histogram descriptors for video segment retrieval and identification.," Image Processing, IEEE Transactions, vol. 11, no. 5, pp. 497-508, 2002. [6] D. S. Van , "Evaluating color descriptors for object and scene recognition.," Pattern Analysis and Machine Intelligence, IEEE Transactions, vol. 32, no. 9, pp. 15821596, 2010. [7] S. Thepade, "Novel Method for Keyframe Extraction using Block Truncation Coding and Mean Square Error," in Green Computing Communication and Electrical Engineering (ICGCCEE), 2014 International Conference on. IEEE, 2014. [8] H. J. Zhang, "An integrated system for content-based video retrieval and browsing.," Pattern recognition, vol. 30, no. 4, pp. 643-658, 1997. [9] X.-D. Yu, "Multilevel video representation with application to keyframe extraction," in Multimedia Modelling Conference, 2004. Proceedings. 10th International. IEEE, 2004.
Jurnal Cybermatika | Vol. 2 No. 2 | Desember 2014 | Artikel 5
35
