TUGAS AKHIR Implementasi Block Matching Algorithm (BMA) Pada Ekstraksi Objek Bergerak Block Matching Algorithm (BMA) Implementation of Motion Object Extraction
Oleh : Amalia Sulfa Hashlinda NRP. 1208100046
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI SEPULUH NOPEMBER 2011
I. PENDAHULUAN I. PENDAHULUAN 1.1 Latar Belakang 1.1 Latar Belakang
Ektraksi Ektraksipada padavideo video adalah adalahpengambilan pengambilan objek objekyang yangbergerak. bergerak. Objek Objekbergerak bergerakyang yang digunakan digunakanuntuk untukanalisis analisis lebih lebihlanjut. lanjut. Dibutuhkan dalam beberapa aplikasi Dibutuhkan dalam beberapa aplikasi vision-based seperti kamera vision-based seperti kamera pengintai (video survaillence), pengintai (video survaillence), penginderaan jarak jauh (remote penginderaan jarak jauh (remote sensing), diagnosis dan pengobatan sensing), diagnosis dan pengobatan medis. medis.
Segmentasi Gerakan (Motion Segmentation) adalah pengelompokan piksel Segmentasi Gerakan (Motion berdasarkan kecepatan dan Segmentation) arah perpindahannya
Motion Vector Motionadalah Vectorbesar dan arah pergerakan suatu piksel dari satu frame ke frame berikutnya
Estimasi Gerakan (Motion Estimation) Motion Vector dihasilkan oleh Estimasi Gerakan (Motion Estimation)
LANJUTAN...
Segmentasi Gerakan (Motion Segmentation) berbasis Block Matching Algorithm (BMA) untuk mengekstraksi objek bergerak pada sebuah video.
I. PENDAHULUAN 1.2 Rumusan Masalah Permasalahan yang akan dibahas pada Tugas Akhir ini adalah: 1. Bagaimana
mengimplementasikan
Estimasi
Gerakan (Motion Estimation) untuk menghasilkan
Motion Vector dengan metode BMA pada sebuah video? 2. Bagaimana melakukan Segmentasi Gerakan (Motion
Segmentation) berbasis BMA pada sebuah video dengan tujuan mengekstraksi objek bergerak yang ada dalam adegan?
I. PENDAHULUAN 1.3 Batasan Masalah Batasan Masalah dalam Tugas Akhir ini adalah: 1. Video yang akan diteliti adalah video dijital dengan satu objek bergerak 2. Background pada video diasumsikan diam. 3. Metode segmentasi gerakan yang digunakan adalah
K-Means Clustering . 4. Metode BMA yang digunakan adalah algoritma EBMA untuk estimasi gerakannya.
I. PENDAHULUAN 1.4 Tujuan Tujuan dari Tugas Akhir ini adalah membangun sistem untuk mengekstraksi objek bergerak pada sebuah video dengan metode
segmentasi
gerakan
berbasis
Block
Matching
Algorithm (BMA) .
1.5 Manfaat Manfaat yang dapat diambil dari Tugas Akhir ini adalah mendapatkan objek bergerak dalam sebuah adegan video. Hasil dari proses ini dapat dimanfaatkan untuk menganalisis lebih lanjut suatu objek bergerak pada sebuah video. Sebagai contoh, pelacakan dan deteksi objek bergerak pada sistem
Video Survaillence.
II. TINJAUAN PUSTAKA 2.1 Citra Digital Citra
digital
adalah
citra
yang
nilainya di-digitalisasi-kan (dibuat diskrit)
baik
spasialnya
dalam
koordinat
maupun
dalam
intensitasnya. Citra digital dapat digambarkan dalam suatu matriks dengan
baris
dan
kolom
yang
merepresentasikan suatu titik pada citra, dan nilai dari elemen matriks tersebut menunjukkan intensitas di titik tersebut. Setiap citra digital memiliki
beberapa
karakteristik,
antara lain ukuran citra,resolusi, koordinat, noise dan kedalaman bit.
II. TINJAUAN PUSTAKA 2.2 Video Video digital tersusun atas serangkaian frame yang ditampilkan pada layar dengan kecepatan tertentu. Masing-masing frame merupakan citra digital yang direpresentasikan
dengan
sebuah
matriks
yang
masing-masing elemennya merepresentasikan nilai intensitas.
Karakteristik
suatu
video
digital
ditentukan oleh resolusi, kedalaman bit, dan frame
rate. Karakteristik ini menentukan kualitas video.
II. TINJAUAN PUSTAKA 2.3 Ekstraksi Objek Bergerak Ekstraksi objek bergerak pada video
Segmentasi Gerakan (Motion Segmentation) adalah pengelompokan piksel berdasarkan kecepatan dan arah perpindahannya
Motion Vector adalah besar dan arah pergerakan piksel dari satu frame ke frame berikutnya
Estimasi Gerakan (Motion Estimation) adalah suatu proses memperkirakan perubahan gerak piksel antara dua frame yang berurutan 1. 2. 3. 4. 5. 6.
Metode Segmentasi Gerakan: Segmentation Using Two Frame Temporal Integration Clustering in the Motion Parameter Space Maximum Likelihood Segmentation Maximum A Posteriori Probability Segmentation Region- Based ML Segmentation: Fusion of Color and Motion
1. 2. 3. 4.
Metode Estimasi Gerakan: Optical Flow General Methodologies Pixel-Based Motion Estimation Block Matching Algorithm (BMA)
II. TINJAUAN PUSTAKA 2.4 Estimasi Gerakan Suatu proses memperkirakan perpindahan piksel dari frame ke (t-1) ke frame ke-t. Perpindahan tersebut direpresentasikan dengan motion vector. 2.5 Estimasi Gerakan dengan Block Matching Algorithm
(BMA)
Sumber: Video Processing and Communication Hal 164 [6] Fungsi Pencocokan: Mean Absolute Difference (MAD) =
Mean Squared Error (MSE) =
II. TINJAUAN PUSTAKA 2.6 Exchautive Search BMA (EBMA) EBMA disebut juga algoritma pencarian penuh. Algoritma ini membutuhkan perhitungan yang sangat tinggi. Namun, memperoleh posisi blok yang optimal pada search region. Berikut skema pada EBMA
Error / Absolute Difference=
Sumber: Implementation Of A Java Applet For Demonstration Of BlockMatching Motion Estimation Algorithms Hal 7
II. TINJAUAN PUSTAKA
2.7 Segmentasi Gerakan Mengelompokkan piksel-piksel berdasarkan intensitas yang sama dan informasi gerakannya yang sesuai dengan objek tunggal. 2.8 Segmentasi Gerakan dengan Kmeans Clustering Mengelompokkan piksel-piksel berdasarkan jarak terdekat atau ketetanggaannya. Motion vector yang dihasilkan EBMA dikelompokkan menjadi beberapa cluster.
Merepresentasikan piksel-piksel yang merupakan kesatuan gerakan yang sama.
mirip
dan
II. TINJAUAN PUSTAKA 2.8 Segmentasi Gerakan dengan Kmeans Clustering (Lanjutan…) Langkah-langkah Kmeans clustering pada motion vector field: 1. Tentukan K cluster 2. Tentukan pusat-pusat cluster secara acak. 3. Masukkan tiap motion vector ke dalam cluster yang jarak pusatnya paling dekat.
4. Ubah nilai pusat cluster sebagai rata-rata (mean) dari seluruh motion vector dalam cluster.
5.Ulangi langkah 2,3,4 hingga memperoleh hasil yang konvergen.
II. TINJAUAN PUSTAKA 2.9 Pelabelan dengan Minimisasi Energi Oleh Graph cut. Memperoleh pelabelan dengan memetakan setiap piksel x hasil estimasi gerakan dengan label gerakan
𝑚𝑥 ∈ 1, … 𝑀 . Fungsi pelabelan: ⋀ 𝑡 ≔ 𝑥; 𝑚𝑥 𝑡
𝑥∈𝑋
. Akan dicari
nilai ⋀ yang meminimalkan fungsi objektif berikut 𝐽 ∧ = 𝐽𝑚𝑚𝑚 ∧ + 𝐶2 𝐽𝑠𝑠𝑠𝑠 ∧
• 𝐶2 adalah bobot konstan
• 𝐽𝑚𝑚𝑚 ∧ = ∑𝑥 𝑉𝑚𝑚𝑚 𝑥; 𝑚𝑥 , 𝑑𝑑𝑑𝑑𝑑𝑑 𝑉𝑚𝑚𝑚 𝑥; 𝑚𝑥 2 = 𝑓 𝑥; 𝑡 − 𝑓(𝑥 + 𝑢�𝑚𝑥 𝑡 ; 𝑡 − 1) • 𝐽𝑠𝑠𝑠𝑠 ∧ = ∑𝑥 ∑𝑥𝑛 ∈𝑁 𝑥 𝑉𝑠 𝑥, 𝑥𝑛 ; 𝑚𝑥 , 𝑚𝑥𝑛 ,
4 − 𝐶𝐶 𝑓 𝑥 , 𝑚𝑥 ≠ 𝑚𝑥𝑛 𝑉𝑠 (𝑥, 𝑥𝑛 ; 𝑚𝑥 , 𝑚𝑥𝑛 ) = � 0, 𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝐶𝐶 𝑓 𝑥
= CA r x
+ CA g x
+ CA b x
Dengan
deteksi tepi Canny
II. TINJAUAN PUSTAKA 2.9 Pelabelan dengan Minimisasi Energi Oleh Graph cut.
(Lanjutan…)
Minimisasi Energi oleh Graph cut (algoritma 𝜶 − 𝒆𝒆𝒆𝒆𝒆𝒆𝒆𝒆𝒆/perluasan 𝛼) 1. Inisialisasi: mulai dengan pelabelan awal secara acak (clustering). 2. Cycle: untuk setiap label 𝛼
∈ {1, … . . , 𝑀} :
Iterasi: Dapatkan ∧𝑛𝑛𝑛 dalam sebuah pergerakan
perluasan 𝛼.
3. Jika J
∧𝑛𝑛𝑛
∧𝑛𝑛𝑛 <∧𝑝𝑝𝑝𝑝 ,
tetapkan ∧𝑝𝑝𝑝𝑝 sama dengan
dan mulai dengan cycle baru. Sedangkan proses berhenti untuk hasil yang lainnya.
II. TINJAUAN PUSTAKA 2.9 Pelabelan dengan Minimisasi Energi Oleh Graph cut.
(Lanjutan…)
algoritma 𝜶 − 𝒆𝒆𝒆𝒆𝒆𝒆𝒆𝒆𝒆/perluasan 𝛼
Ilustrasi Graph cut
Bobot tepi pada Graph cut
III. Perancangan dan Implementasi Simulasi 3.1 Diagram Alur Sistem
III. Perancangan dan Implementasi Simulasi 3.2 Perancangan Program Dalam membangun simulasi untuk mengekstraksi objek bergerak, program ini terdiri dari 5 program, yaitu 1. Program Pilih Video Berfungsi menginputkan dan memutar video yang akan diekstrak si objek bergeraknya. 2. Program Segmentasi Gerakan Program ini disajikan dalam dua sistem yang berbeda yaitu segmentasi gerakan yang dilakukan per frame dan segmentasi gerakan seluruh frame. Dalam program ini, sistem menjalankan tiga algoritma yaitu Estimasi gerakan dengan BMA, segmentasi gerakan dengan Kmeans Clustering, dan Pelabelan dengan Minimisasi Energi Graph cut.
III. Perancangan dan Implementasi Simulasi 3.2 Perancangan Program 2. Program Segmentasi Gerakan (Lanjutan…)
Flowchart Estimasi Gerakan BMA
Flowchart Segmentasi Gerakan
Flowchart Segmentasi Gerakan Semua Frame
III. Perancangan dan Implementasi Simulasi 3.2 Perancangan Program 3. Program Hasil Segmentasi Per Frame Berfungsi menampilkan hasil ekstraksi objek bergerak per pasangan frame berurutan. Citra objek dan citra background terpisah 4. Program Hasil Segmentasi Semua Frame
(Objek/Foreground)
Berfungsi menampilkan hasil ekstraksi objek bergerak seluruh frame dari video yang diinputkan. Video objek bergerak 5. Program Hasil Segmentasi Semua Frame (Background) Berfungsi menampilkan hasil ekstraksi objek bergerak seluruh frame dari video yang diinputkan. Video background berurutan
III. Perancangan dan Implementasi Simulasi 3.2 Perancangan Program Program Hasil Segmentasi (Lanjutan…)
Flowchart Hasil Ekstraksi Objek Bergerak Per Frame
Flowchart Hasil Ekstraksi Objek Bergerak Semua Frame
IV. Uji Coba Simulasi Uji Coba dilakukan terhadap setiap pasangan frame berurutan. 4.1 Data Uji Coba (video fahmalari.avi)
IV. Uji Coba Simulasi 4.2 Pengujian Estimasi Gerakan , Segmentasi Gerakan, dan Pelabelan
IV. Uji Coba Simulasi 4.2 Pengujian Estimasi Gerakan , Segmentasi Gerakan, dan Pelabelan (Lanjutan…)
IV. Uji Coba Simulasi 4.3 Hasil Ekstraksi Objek Bergerak
Hasil Ekstraksi Objek Bergerak dari Pelabelan 7,8,9
IV. Uji Coba Simulasi 4.4 Evaluasi Pada percobaan di atas secara kasat mata citra hasil ekstraksi objek bergerak pada pasangan frame yang sama dapat berbeda-beda. Ini berhubungan dengan estimasi gerakan menggunakan BMA yaitu pada salah satu variabelnya, ukuran blok. Semakin kecil ukuran blok pada estimasi gerakan BMA, maka hasil ekstraksi objeknya semakin baik.
V. Penutup 5.1 Kesimpulan Dari Uji Coba Simulasi dipeoleh kesimpulan sebagai berikut 1. Algoritma Block Matching Algorithm untuk estimasi gerakan dapat diterapkan dengan ukuran blok yang berbeda. Hasil yang diperoleh pun berbeda-beda. Dari pengujian yang dilakukan dapat ditarik kesimpulan bahwa semakin kecil ukuran blok yang digunakan (4 x 4) akan semakin akurat hasil estimasi gerakan yang diperoleh. 2. Dapat ditarik kesimpulan juga bahwa keakuratan hasil estimasi gerakan akan berpengaruh terhadap hasil pelabelan dengan Graph cut. Semakin kecil ukuran blok yang digunakan pada BMA untuk estimasi gerakan, maka hasil estimasi gerakan semakin akurat, dan pada segmentasi gerakannya akan menghasilkan pelabelan yang lebih baik. 3. Pelabelan dengan Graph cut yang baik, akan diperoleh hasil ekstraksi yang baik pula. Jadi, hasil estimasi gerakan berpengaruh terhadap tingkat keberhasilan pada ekstraksi objek bergerak.
V. Penutup 5.2 Saran Saran yang dapat diberikan dalam pengembangan penelitian ini antara lain adalah: 1. Estimasi gerakan adalah algoritma untuk menghitung perpindahan piksel antara pasangan frame berurutan. Untuk penelitian selanjutnya, penulis menyarankan penggunaan metode estimasi gerakan yang lebih baik yaitu estimasi gerakan yang dilakukan pada setiap piksel frame. Sebagai contoh, algoritma optical flow. Diharapkan dengan algoritma ini akan dihasilkan estimasi gerakan yang jauh lebih akurat dan tentu saja akan menghasilkan ekstraksi objek yang lebih optimal. 2. Untuk menghasilkan esktraksi objek yang lebih optimal juga hendaknya dilakukan segmentasi yang lain selain segmentasi gerakan. Misalnya, segmentasi warna. Dengan demikian, noise dan kehilangan strukstur objek (hasil ekstraksi pada subbab Uji Coba) dapat diminimalkan.
IV. DAFTAR PUSTAKA [1] Barjatya, Aroh.2004.“Block Matching Algorithms For Motion Estimation”.DIP 6620 Spring 2004 Final Project Paper. [2] Bhusan, K. Sasi, Vineela, T., Reddy, N. Venkateswara, Krishna, K.Vamsi, dan Rao, Joseph Abilash. May 2009. “Motion Based Foreground Segmentation using Block Matching Algorithm (BMA)”.International Journal Of Recent Trends in Engineering. Vol. 1, No. 2. [3] Bovik, Al. 2009. The Essential Guide to Video Processing. India : diacriTech [4] Boykov, Yuri, Veksler, Olga, Zabih, Ramin. November 2011. “Fast Approximate Energy Minimization via Graph Cuts”. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, Vol. 23, No. 11. [5] Chung, Ronald H.Y., Chin, Francis Y.L., Wong, Kwan-Yee K., Chow, K.P., Luo, T., dan Fung, Henry, S.K. Apr 2005. “Efficient Block-based Motion Segmentation Method using Motion Vector Consistency”. Conference on Machine Vision Application. [6] Han, Bing, Robert,William, Wu, Dapeng, dan Li, Jian.2007. “Motion-SegmentationBased Change Detection”. Algorithms for Synthetic Aperture Radar Imagery XIV. [7] S. Alexiadis, Dimitrios, D. Sergiadis, George. 2008. “Motion estimation, segmentation and separation, using hypercomplex phase correlation, clustering techniques and graph-based optimization”. Computer Vision and Image Understanding 113 (2009) 212-234. [8] Wang, Yao, Ostermann, Jorn, Zhang, Ya-Qin, Ostermann, Joern, dan Zhang Ya-quin. 2001. Video Processing and Communication. Prentice Hall.
