IMPLEMENTASI METODE SCALE INVARIANT FEATURE TRANSFORM DAN METODE CAMSHIFT PADA PENJEJAKAN OBJEK BERGERAK Oleh : Shanty Eka Agustina (1207.1000.24) Dosen Pembimbing: Dr . Imam Mukhlas, S.si, MT
Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Sepuluh Nopember Surabaya
LOGO
LOGO
PENDAHULUAN DASAR TEORI ANALISIS SISTEM DAN PERANCANGAN PERANGKAT LUNAK
IMPLEMENTASI SISTEM PENGUJIAN DAN ANALISIS PERANGKAT LUNAK PENUTUP
PENDAHULUAN Latar Belakang
Sistem Penjejakan Objek Bergerak
LOGO
LOGO
Kelebihan : 1. memiliki kemampuan melakukan adaptasi atau penyesuaian terhadap distribusi probabilitas warna yang selalu berubah tiap pergantian frame dari video.
Alasan: distribusi probabilitas warna yang selalu berubah tiap pergantian frame dari video
PENDAHULUAN(LANJUTAN) Rumusan Masalah 1
• Bagaimana mengaplikasikan metode scale invariant feature transform untuk mendeteksi dan mendeskripsikan fitur – fitur lokal yang terdapat dalam data video.
2
• Bagaimana mengaplikasikan metode camshift untuk mendeteksi objek bergerak dalam data video.
3
• Bagaimana sistem yang telah dibuat dapat menjejaki gerakan dari objek yang telah ditentukan.
LOGO
PENDAHULUAN(LANJUTAN) Batasan Masalah Data video yang akan diamati sebelumnya telah tersimpan dalam penyimpanan komputer. Objek yang akan diamati ditentukan oleh user dengan ketentuan hanya satu kesatuan objek bergerak saja. Penjejakan objek bergerak dengan metode scale invariant feature transform dan metode camshift di implementasikan pada MATLAB R2012a
LOGO
PENDAHULUAN(LANJUTAN) Tujuan Mengaplikasikan metode scale invariant feature transform untuk mendeteksi dan mendeskripsikan fitur- fitur lokal dari citra pada data video Mengaplikasikan metode camshift untuk mendeteksi objek bergerak dalam data video. Mengaplikasikan sistem yang telah dibuat agar dapat menjejaki gerakan dari objek yang telah ditentukan oleh user.
LOGO
PENDAHULUAN(LANJUTAN) Manfaat
1 Dapat memudahkan pengamat dalam melakukan proses pengamatan objek bergerak pada suatu data video.
2 Dihasilkan suatu aplikasi penjejakan objek bergerak pada video yang mampu melakukan penjejakan suatu objek bergerak.
LOGO
LOGO
PENDAHULUAN
DASAR TEORI ANALISIS SISTEM DAN PERANCANGAN PERANGKAT LUNAK
IMPLEMENTASI SISTEM PENGUJIAN DAN ANALISIS PERANGKAT LUNAK PENUTUP
DASAR TEORI Citra Digital Citra adalah kumpulan gambar yang secara keseluruhan merekam suatu adegan melalui media indra visual.Citra dapat dideskripsikan sebagai data dalam dua dimensi dalam bentuk matriks. Citra digital adalah citra dua dimensi yang dapat dipresentasikan dengan fungsi intensitas cahaya yang mana X dan Y menyatakan koordinat spasial.
LOGO
DASAR TEORI (LANJUTAN)
LOGO
Penjejakan Objek Bergerak Penjejakan Objek Bergerak(Obyek Tracking) adalah proses mencari lokasi dari objek yang akan diamati dari suatu data video untuk setiap satu satuan frame dalam data video tersebut.
Penjejakan objek bergerak berdasarkan pengenalan objek.
Penjejakan objek bergerak berdasarkan gerakan objek
Metode yang sering digunakan : 1.Kalman filter 2.extended Kalman filter 3.Particle filter
Metode yang sering digunakan : 1.SIFT 2.RANSAC 3.Mean Shift 4.Camshift
LOGO
DASAR TEORI (LANJUTAN) Cara Kerja Algoritma SIFT Cara Kerja Algoritma SIFT adalah sebagai berikut: 1. Gaussian dan Difference of Gaussian Scale Space Scale Space
Tujuan Pembangun Scale Space
Fungsi Gausian
agar didapatkan fitur-fitur yang stabil (invarian) terhadap berbagai kemungkinan perubahan terhadap skala citra.
Gaussian Scale Space
Difference Of Gaussian Cara Pembentukannya
Rumus
(D(x,y,σ)) = L(x,y,kσ)-L(x,y,σ)
cara mensubstraksi dua citra Gaussian Scale Space yang berdekatan
LOGO
DASAR TEORI (LANJUTAN)
Keterangan – L(x,y,kσ) adalah konvolusi dari citra asli I(x,y) dengan Gaussian filter G(x,y,σ) pada skala kσ dengan k = √2. – L(x,y,σ) adalah konvolusi dari citra asli I(x,y) dengan Gaussian filter G(x,y,σ) pada skala σ
2. Deteksi Ekstremum Deteksi Ekstremum Cara Pembentukannya
membandingkan nilai setiap piksel pada DoG Scale space dengan delapan piksel yang berada di sekelilingnya dan 9 piksel yang bersesuaian pada citra DoG sebelumnya dan setelahnya.
Kriteria Deteksi Ekstremum
Jika nilai piksel yang dimaksud lebih besar atau lebih kecil daripada nilai-nilai piksel pembandingnya maka koordinat piksel tersebut ditandai sebagai ekstremum
DASAR TEORI (LANJUTAN) Lokalisasi dengan akurasi subpiksel
Titik-titik Ekstremum
Alat Pembantu
ekspansi Taylor orde kedua
Posisi Ekstrema Menghitung Nilai Keypoint Pada Ekstrema Kriteria Keypoint
Jika nilai D(z)tidak melebihi suatu nilai threshold ( 0.03) maka keypoint tersebut dihilangkan dan tidak dipakai lagi.
LOGO
LOGO
Penetapan Orientasi Keypoint (Orientation assignment) Alat Pembentuk
Penetapan Orientasi Keypoint
Tujuan
untuk mendapatkan sifat invarian terhadap rotasi objek
citra Gaussian smooth L yang memiliki skala paling dekat dengan skala keypoint Dicari
Gradien Magnitude
Orientasi Dibentuk
Histogram Orientasi Dicari
Puncak Histogram Orientasi = Orientasi Dominan
DASAR TEORI (LANJUTAN)
LOGO
Penentuan Deskriptor Lokal Proses terakhir adalah menghitung vektor deskriptor. Deskriptor dihitung untuk masing-masing keypoint, langkah ini dilakukan pada gambar yang paling dekat dengan skala untuk skala keypoint. Pertama membuat orientasi dengan 4x4 piksel dengan 8 bin untuk tiap masing-masingnya. Histogram ini dihitung dari magnitude dan nilai orientasi dari sampel dalam wilayah 16x16 disekitar keypoint. Magnitude dihitung dengan fungsi Gaussian dengan σ sama dengan satu setengah lebar deskriptor. Kemudian deskriptor menjadi vektor dari semua nilai histogram ini. Karena 4x4= 16 histogram dengan masing-masing memiliki 8bin, maka vektor memiliki 128 elemen.
DASAR TEORI (LANJUTAN) Algoritma Meanshift Langkah-langkah dari algoritma Mean Shift adalah sebagai berikut: Step 1 : Ukuran search window yang sudah ditentukan. Step 2 : Lokasi awal search window yang sudah ditentukan. Step 3 : Hitung daerah mean dalam search window. Step 4 : Posisikan search window ke tengah daerah mean seperti dihitung pada step (3). Step 5 : Ulangi step (3) dan (4) hingga konvergen (atau hingga pergeseran daerah mean kurang dari threshold / batas yang ditentukan).
LOGO
DASAR TEORI (LANJUTAN)
LOGO
Algoritma Camshift Secara umum algoritma camshift meliputi step-step sebagai berikut: Step 1 : Tentukan ukuran awal search window. Step 2 : Tentukan lokasi awal dari search window. Step 3 : Tentukan daerah kalkulasi (calculation region) pada bagian tengah search window dengan ukuran lebih besar dari search window. Step 4 : Frame citra video dikonversi ke dalam sistem warna HSV (Hue, Saturation,Value), dan dilakukan color histogram lookup dalam calculation region yang akan menghasilkan citra distribusi probabilitas warna. Step 5 : Lakukan algoritma Mean Shift seperti di atas (satu atau banyak iterasi) dengan input berupa ukuran dan lokasi search window serta citra distribusi probabilitas warna, simpan zeroth moment. Step 6 : Set nilai x, y, z yang diperoleh dari step (5). Step 7 : Nilai x, y dipakai untuk set titik tengah search window, (2*area1/2). Untuk set ukuran window. Ulangi step(3) untuk setiap pergantian frame citra video.
LOGO
PENDAHULUAN
DASAR TEORI ANALISIS SISTEM DAN PERANCANGAN PERANGKAT LUNAK
IMPLEMENTASI SISTEM PENGUJIAN DAN ANALISIS PERANGKAT LUNAK PENUTUP
Perancangan Perangkat Lunak
LOGO
Software
Program Utama: Penjejakan Objek Bergerak dengan SIFT
Program Utama: Penjejakan Objek Bergerak dengan Camshift
FLOWCHART PENJEJAKAN OBJEK BERGERAK dengan SIFT Mulai Data Video Non Realtime
Menampilkan data video yang telah tersimpan di direktori Konversi video ke frame Ekstrasi fitur-fitur lokal dalam citra uji dengan algoritma SIFT Ekstrasi fitur pencocokan keypoint Tentukan ROI dari objek Penjejakan objek bergerak Update posisi baru dari objek Video hasil tracking
Selesai
LOGO
FLOWCHART PENJEJAKAN OBJEK BERGERAK dengan CAMSHIFT Mulai Data Video Non Realtime Menampilkan data video yang telah tersimpan di direktori
Tentukan ROI dari objek yang akan diamati
Penjejakan Objek Bergerak dengan Camshift Update posisi baru dari objek
Video Hasil Tracking
Selesai
LOGO
Uji Coba Program UJI COBA PROGRAM Data Uji Coba No Nama Video 1
Redcup.avi
2
bola.avi
3
cangkir.avi
Video
LOGO
LOGO
Uji coba pendeteksian fitur keypoint Total citra .jpg ada 100 citra.jpg untuk dataset redcup.avi yaitu 1.jpg sampai dengan 100.jpg.Sedangkan total citra .jpg ada 80.jpg untuk dataset bola.avi yaitu bola1.jpg sampai dengan bola80.jpg. Dan untuk dataset cangkir.avi ada 40 citra yaitu cangkir1.jpg sampai cangkir40.jpg. N o
Citra Uji
Jumlah Fitur Keypoint Yang Terdeteksi
1
Redcup1.jpg
2
Redcup2.jpg
3
Redcup3.jpg
4
Redcup4.jpg
Jumlah Fitur yang terdeteksi 395 keypoint Jumlah Fitur yang terdeteksi 422 keypoint Jumlah Fitur yang terdeteksi 393 keypoint Jumlah Fitur yang terdeteksi 389 keypoint
Untuk dataset Redcup.avi
LOGO
N o
Citra Uji
1
Bola1.jpg
2
Bola2.jpg
3
Bola3.jpg
4
Bola4.jpg
Jumlah Fitur Keypoint Yang Terdeteksi Jumlah Fitur yang terdeteksi 193 keypoint Jumlah Fitur yang terdeteksi 208 keypoint Jumlah Fitur yang terdeteksi 211 keypoint Jumlah Fitur yang terdeteksi 240 keypoint
Untuk dataset Bola.avi
N o
Citra Uji
Jumlah Fitur Keypoint Yang Terdeteksi
1
Cangkir1.jpg
2
Cangkir2.jpg
3
Cangkir3.jpg
4
Cangkir4.jpg
Jumlah Fitur yang terdeteksi 273 keypoint Jumlah Fitur yang terdeteksi 328 keypoint Jumlah Fitur yang terdeteksi 301 keypoint Jumlah Fitur yang terdeteksi 339 keypoint
Untuk dataset cangkir.avi
LOGO
Uji coba ekstrak fitur pencocokan keypoint beserta penjejakan objek bergeraknya
Deteksi fitur match redcup1.jpg dengan redcup2.jpg
Deteksi fitur match redcup3.jpg dengan redcup4.jpg
LOGO
Deteksi fitur match bola1.jpg dengan bola2.jpg
Deteksi fitur match bola3.jpg dengan bola4.jpg
Deteksi fitur match cangkir1.jpg dengan cangkir2.jpg Deteksi fitur match cangkir3.jpg dengan cangkir4.jpg
LOGO
Hasil Tracking Algoritma SIFT untuk dataset redcup.avi
LOGO
Untuk dataset bola.avi
Untuk dataset cangkir.avi
LOGO
•Uji coba penjejakan (tracking) objek bergerak. Input : - Data video penyimpanan direktori - Indeks frame awal sampai dengan indeks frame akhir - Koordinat dari ROI Proses: Proses penjejakan objek bergerak Output :- Koordinat titik pusat dari ROI sesuai dengan hasil penjejakan objek bergerak - Nilai zeroth moment untuk x dan y, Jumlah iterasi untuk setiap proses penjejakan
LOGO
Untuk dataset bola.avi
Untuk dataset cangkir.avi
KESIMPULAN DAN SARAN Dari hasil uji coba diatas menunjukkan bahwa waktu komputasi dari algoritma SIFT lebih efisien dibandingkan dengan algoritma Camshift. Akan tetapi, hasil penjejakan yang dilakukan oleh algoritma Camshift lebih baik dibandingkan dengan algoritma SIFT. Saran Saran yang dapat diberikan dalam pengembangan tugas akhir ini antara lain adalah: •Sebagai pengembangan program, dapat dibuat program penjejakan objek bergerak dengan pengambilan citra secara real time .
LOGO
DAFTAR PUSTAKA
LOGO
Exner David and Bruns Erich,”Fast and robust camshift tracking,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 2010. M. Isard and A. Blake, “Condensation - Conditional density propagation for visual tracking,” Intl. J. of Computer Vision, vol. 29, no. 1, 1998. Pratama, Rangga Yudha, 2005, “Rancang Bangun Perangkat Lunak Untuk Deteksi Objek Bergerak Menggunakan Motion Tracking dan Short Message Services”, Tugas Akhir, Jurusan Matematika ITS. R. Rosales and S. Sclaroff, “3D trajectory recovery for tracking multiple objects and trajectory guided recognition of actions,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, Fort Collins, CO, 1999, pp. 117– 123. Y. Boykov and D. Huttenlocher, “Adaptive Bayesian recognition in tracking rigid objects,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, Hilton Head, SC, 2000, pp. 697–704. Y. Rui and Y. Chen, “Better proposal distributions: Object tracking using unscented particle filter,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, Kauai, Hawaii, volume II, 2001, pp. 786–793
LOGO
Chaoyang Zhu, 2011, “ Video Object Tracking using SIFT and Mean Shift”, Thesis, Department of Signals and Systems Chalmers University Of Technology. Susanto,2008,” Pengembangan Perangkat Lunak Penjejakan Objek Bergerak Menggunakan Metode Mean Shift” Tugas Akhir, Jurusan Matematika ITS. Lowe, D.G., “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, 60, 2, pp. 91-110, 2004. G. R. Bradski. Computer video face tracking for use in a perceptual user interface. Intel Technology Journal, Q2 1998. D. Comaniciu, V. Ramesh, “Real-Time Tracking of Non-Rigid Objects using Mean Shift”, IEEE CVPR, 2000.
