JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6
1
Implementasi Algoritma Block Matching pada Ekstraksi Objek Bergerak Amalia Sulfa Hashlinda dan Imam Mukhlash Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Sepuluh Nopember Surabaya Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected]
Abstrak—Ekstraksi pada video adalah pengambilan objek yang bergerak pada video tersebut. Ekstraksi ini dapat dicapai dengan melakukan segmentasi berbasis gerakan atau yang dikenal dengan istilah segmentasi gerakan (motion segmentation). Hal ini dianggap penting dan dibutuhkan dalam beberapa aplikasi vision-based seperti video surveillance, remote sensing (penginderaan jarak jauh), diagnosis dan pengobatan medis, infrastruktur sipil, dan underwater sensing (penginderaan di bawah air). Segmentasi gerakan adalah pengelompokan piksel citra berdasarkan gerakannya. Oleh karena itu, segmentasi gerakan dilakukan berdasarkan motion vector. Motion vector adalah besar dan arah pergerakan sebuah objek atau piksel dari satu frame ke frame berikutnya. Motion vector ini dihasilkan oleh estimasi gerakan. Estimasi gerakan yang digunakan pada Tugas Akhir ini adalah Block Matching Algorithm (BMA). Segmentasi gerakan dengan K-means clustering diterapkan untuk mengelompokkan motion vector yang dihasilkan oleh BMA berdasarkan kemiripan gerakannya. Kemudian, pelabelan dengan minimisasi energi oleh Graph cut dilakukan terhadap cluster-cluster motion vector tersebut untuk memperoleh citra biner yang merepresentasikan objek dan background. Dengan demikian, diperoleh ekstraksi objek bergerak. Kata Kunci—BMA, Estimasi Gerakan, K-means clustering, Minimisasi Energi oleh Graph cut, Pelabelan, Segmentasi Gerakan.
I. PENDAHULUAN
V
IDEO adalah teknologi untuk menangkap, merekam, memproses, mentransmisikan dan menata ulang citra bergerak. Teknologi ini biasanya menggunakan film seluloid, sinyal elektronik, atau media digital. Video juga dapat diartikan sebagai gabungan citra-citra mati yang dibaca berurutan dalam suatu waktu dengan kecepatan tertentu. Citracitra mati tersebut dinamakan frame dan kecepatan pembacaan gabungan citra disebut dengan frame rate, dengan satuan fps (frame per second). Ekstraksi objek bergerak adalah pengambilan objek yang bergerak dalam adegan pada suatu video. Ekstraksi ini dapat dicapai dengan melakukan segmentasi berbasis gerakan atau yang dikenal dengan istilah segmentasi gerakan (motion segmentation). Hal ini dianggap sebagai langkah penting dan dibutuhkan dalam beberapa aplikasi vision-based seperti kamera pengintai (video surveillance), penginderaan jarak jauh (remote sensing), diagnosis dan pengobatan medis,
infrastruktur sipil, dan penginderaan di bawah air (underwater sensing). Sistem video survaillence dibutuhkan untuk melakukan tugas manusia seperti pelacakan dan deteksi penyusup. Dalam hal ini, objek bergerak yang ada pada video harus diekstraksi terlebih dahulu kemudian dianalisis lebih lanjut. Segmentasi gerakan adalah pengelompokan piksel citra ke dalam beberapa kelas berdasarkan kecepatan dan arah perpindahannya. Oleh karena itu, segmentasi gerakan dilakukan berdasarkan motion vector yang merupakan besar dan arah pergerakan sebuah objek atau piksel dari satu frame ke frame berikutnya. Motion vector ini dihasilkan oleh proses memperkirakan perubahan gerakan antara dua frame yang berurutan pada video yang disebut estimasi gerakan [4]. Pada Tugas Akhir ini, akan dikembangkan sebuah perangkat lunak yang mampu melakukan segmentasi gerakan untuk mengekstraksi objek pada suatu video dengan pendekatan Block Matching Algorithm (BMA). BMA disini berperan untuk mengestimasi gerakan objek pada video tersebut. BMA mempartisi frame menjadi blok-blok dengan ukuran yang telah ditentukan oleh pengguna (user). Masingmasing blok pada frame ke-t dicari kecocokannya dengan blok-blok dalam search region pada frame ke-(t-1). Dengan demikian, akan diperoleh besar dan perpindahan piksel dari satu frame ke frame berikutnya yang direpresentasikan dengan motion vector [14]. Segmentasi gerakan dengan K-means clustering diterapkan untuk mengelompokkan motion vector field yang dihasilkan oleh BMA berdasarkan kemiripan gerakannya. Kemudian, pelabelan piksel dengan minimisasi energi oleh Graph cut dilakukan terhadap cluster-cluster motion vector tersebut untuk memperoleh citra biner yang merepresentasikan objek dan background. II. TINJAUAN PUSTAKA A. Citra Digital Citra (image) adalah gambar pada bidang dua dimensi. Jika ditinjau dari sudut pandang matematis, citra merupakan fungsi kontinu dari intensitas cahaya pada bidang dua dimensi, dimana terdapat sumber cahaya menerangi obyek, kemudian obyek memantulkan kembali sebagian dari berkas cahaya tersebut. Pantulan cahaya ini ditangkap oleh alat-alat optik, misalnya mata, kamera, scanner, dan sebagainya
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6 Dengan
C2
adalah bobot konstan dimana
C 2 = 1000
3 untuk
urutan citra natural dan C 2 = 500 untuk urutan citra buatan [12]. Fungsi objektif yang akan diminimalkan adalah sebagai berikut 1. Term gerakan Term objektif:
J mot (Λ ) =
∑V
mot
(x
; m x ) dengan Vmot (x ; mx ) =
Gambar 3. Bobot tepi pada Graph cut [12]
x
(
)2
f (x ; t ) − f x + uˆ mx (t ) ; t − 1
2. Term Spatial smoothness Untuk memperoleh kejelasan karena adanya noise atau kurangnya tekstur.
J spat (Λ ) =
Vs x, x n ; m x , m xn x ∈N ( x ) n
∑ ∑ ( x
)
dengan
4 − CA{ f ( x )}, m x ≠ m xn Vs x, xn ; mx , mxn = 0
(
Dengan “ x n
)
∈ N ( x) ”
berarti bahwa
xn
adalah persekitaran
dari x. Term CA{f(x)} menunjukkan jumlah output pendeteksi tepi “Canny”. Oleh karena itu, CA{r(x)}, dan hasilnya CA{g(x)}, dan CA{b(x)} ∈ {0,1} CA{f(x)}=CA{r(x)}+CA{g(x)}+CA{b(x)} ∈ {0,1, 2,3} 3. Minimisasi Energi oleh Graph cut Minimisasi ini dapat dicapai menggunakan algoritma perluasan α . Berikut adalah algoritma perluasan α [12]. a) Inisialisasi: mulai dengan pelabelan awal secara acak b) Cycle: untuk setiap label α ∈ {1,........, M }
E. Estimasi Gerakan Estimasi gerakan adalah proses memperkirakan perubahan gerakan dari satu frame ke frame berikutnya. Suatu gerakan umumnya direpresentasikan oleh motion vector (x,y). Motion vector menunjukkan perpindahan piksel atau blok piksel dari frame ke-(t-1) ke frame ke-(t) [4]. Pada tugas akhir ini, estimasi gerakan yang dilakukan menggunakan Block Matching Algorithm (BMA). F. Block Matching Algorithm (BMA) BMA adalah metode estimasi gerakan yang paling popular. BMA dilakukan dengan membagi frame saat ini (current frame) ke dalam bentuk blok-blok piksel kemudian dibandingkan dengan blok yang posisinya sama dan berdekatan dalam search range pada frame sebelumnya (reference frame). Hal ini bertujuan untuk menentukan perpindahan piksel dan direperesentasikan dengan motion vector. Ilustrasi estimasi gerakan dengan BMA ditunjukkan pada Gambar 4 berikut
• Iterasi: Dapatkan ∧ new dalam sebuah pergerakan
perluasan α . c) Jika ∧ new < ∧ prev tetapkan
∧ prev sama dengan ∧ new
dan mulai dengan cycle baru, selesai untuk asil yang lain.
Gambar 4. Ilustrasi prosedur estimasi gerakan dengan BMA [14]
Kecocokan satu blok pada current frame dengan blok-blok di dalam search range pada refference frame diperoleh berdasarkan hasil perhitungan fungsi pencocokan. Fungsi pencocokan yang paling sering digunakan adalah Mean Absolute Difference (MAD) pada persamaan (1) dan Mean Squared Error (MSE) pada persamaan (2) berikut,
1 MAD = N2 Gambar 2. Ilustrasi Graph cut [12]
MSE =
1 N2
N −1 N −1
∑∑ C
ij
− Rij
ij
− Rij
(1)
i=0 j=0
N −1 N −1
∑∑ (C i=0 j=0
)2
(2)
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6 sehingga bayangan obyek yang disebut citra tersebut terekam [1]. Citra ada dua jenis, yaitu citra diam (still image) dan citra bergerak (moving image). Citra diam adalah citra tunggal yang tidak bergerak, sedangkan citra bergerak adalah rangkaian citra diam yang ditampilkan secara sekuensial sehingga memberi kesan pada mata sebagai gambar bergerak [9]. Sebuah citra dapat direpresentasikan sebagai fungsi f(x,y), dimana x dan y adalah koordinat spasial, dan nilai f pada masing-masing koordinat (x,y) disebut intensitas atau level keabuan citra. Citra digital dapat direpresentasikan dalam bentuk matriks. Misalkan terdapat suatu citra berukuran M×N (M baris dan N kolom). Citra tersebut dapat direpresentasikan dalam bentuk matriks seperti yang ditunjukkan pada Gambar 1 berikut f (0,0) f (1,0) f ( x, y ) = f ( M − 1,0)
f (0,1) f (1,1) f ( M − 1,1)
f (0, N − 1) f (1, N − 1) f ( M − 1, N − 1)
Gambar 1. Representasi Citra Digital [9]
Masing-masing elemen dalam matriks disebut dengan elemen citra atau piksel. f(x,y) menggambarkan intensitas citra, sedangkan x dan y menunjukkan posisi piksel dalam citra atau disebut juga dengan koordinat spasial citra. B. Video Video digital pada dasarnya tersusun atas serangkaian frame yang ditampilkan pada layar dengan kecepatan tertentu sesuai frame rate yang diberikan (dalam frame/second). Masing-masing frame merupakan citra digital. Karakteristik suatu video digital ditentukan oleh resolusi, kedalaman bit, dan frame rate. Karakteristik-karakteristik tersebut akan menentukan kualitas video dan akan dijelaskan sebagai berikut • Resolusi adalah ukuran sebuah frame. Resolusi dinyatakan dalam piksel×piksel. Semakin tinggi resolusi, semakin baik kualitas video yang dihasilkan, dalam artian bahwa ukuran fisiknya sama, video dengan resolusi tinggi akan lebih detail. • Kedalaman bit menentukan jumlah bit yang digunakan untuk merepresentasikan tiap piksel pada sebuah frame. Kedalaman bit dinyatakan dalam bit/piksel. semakin banyak bit yang digunakan untuk merepresentasikan sebuah piksel, yang berarti semakin tinggi kedalaman pikselnya, maka semakin baik pula kualitasnya. • Frame rate menunjukkan jumlah frame tiap detik pada suatu video yang dinyatakan dengan frame/second. Video yang berkualitas baik akan memiliki frame rate yang tinggi, setidaknya harus menampilkan sedikitnya 25 frame/second. C. Ekstraksi Objek Bergerak Ekstraksi objek bergerak adalah pemisahan objek bergerak dan background pada suatu video. Salah satu cara untuk
2 mencapai hal ini adalah dengan melakukan segmentasi gerakan. Segmentasi gerakan adalah pengelompokan piksel berdasarkan kecepatan dan arah perpindahannya. Oleh karena itu, segmentasi gerakan dilakukan berdasarkan motion vector. Motion vector adalah besar dan arah perpindahan piksel dari satu frame ke frame berikutnya. Motion vector ini dihasilkan oleh sebuah proses yang memperkirakan perubahan gerakan antara dua frame yang berurutan. Proses ini disebut estimasi gerakan. D. Segmentasi Gerakan Segmentasi gerakan adalah pengelompokan piksel-piksel citra berdasarkan gerakannya. Segmentasi gerakan mengacu pada pelabelan piksel-piksel yang kemudian dihubungkan menjadi suatu objek atau region. Segmentasi gerakan yang dilakukan pada Tugas Akhir ini meliputi 2 tahap yaitu 1) Segmentasi gerakan dengan K-means clustering. Segmentasi ini dilakukan dengan cara mengelompokkan piksel-piksel yang berdekatan jaraknya. Motion vector field yang dihasilkan oleh estimasi gerakan dikelompokkan menjadi beberapa cluster. Setiap cluster merepresentasikan piksel-piksel dengan kesamaan intensitas dan informasi gerakan. Berikut adalah langkah-langkah K-means clustering pada motion vector field [4], 1. Tentukan K cluster ~ ~ ~ 2. Tentukan pusat-pusat cluster C1, C 2 ,...., C k secara acak. 3. Masukkan tiap motion vector
( x1 , x 2 ,...., x n )
C = {C1 , C 2 ,......, C k }
cluster
ke dalam
yang jarak pusatnya
paling dekat. Hal ini bertujuan untuk membagi n motion vector menjadi k cluster dengan ( k ≤ n ) . Adapun persamaan jarak yang digunakan adalah
r = Dengan
~ Ci
arg min c
k
∑∑
~ x j − Ci
2
i =1 x j ∈Ci
adalah titik pusat
Ci
4. Ubah nilai pusat cluster sebagai rata-rata (mean) dari seluruh motion vector dalam cluster
~ Cr =
∑x ∈C Ci ∑x ∈C 1 j
i
j
i
5. Ulangi langkah 3,4 hingga memperoleh hasil yang konvergen. 2) Pelabelan Objek menggunakan Minimisasi Energi oleh Graph cut. Teknik ini bertujuan untuk memperoleh peta segmentasi gerakan atau pelabelan dengan memetakan setiap piksel x yang gerakannya telah diperkirakan dengan label gerakan m x ∈ ( = {1,...., M } . Pelabelan tersebut diwakili oleh persamaan dicari nilai
∧
∧ ( t ) := { x ; m x ( t )} x∈X
yang kemudian
untuk meminimalkan fungsi objektif berikut:
J (Λ ) = J mot (Λ ) + C 2 J spat (Λ )
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6
4
Dengan N adalah ukuran blok, C ij adalah nilai piksel blok pada current frame, dan Rij adalah nilai piksel pada blok-blok dalam search range pada reference frame [2]. Pada Tugas Akhir ini, estimasi gerakan yang dilakukan lebih tepatnya menggunakan salah satu algoritma BMA yaitu EBMA (Exchautive Search BMA) atau algoritma pencarian penuh. Skema pencocokan pada EBMA ditunjukkan pada Gambar 5 berikut
4.
5.
16x16
Fahmalari.avi (62-63)
8x8
6.
4x4
7.
16x16
Gambar 5. Skema pencocokan blok pada EBMA [10]
III. PEMBAHASAN DAN HASIL A. Pengujian Hasil Implementasi Estimasi Gerakan dengan EBMA Estimasi gerakan adalah menghitung nilai perpindahan piksel dari frame ke-(t-1) atau reference frame ke frame ke-(t) atau current frame. Perpindahan tersebut kemudian direpresentasikan dengan motion vector. Beberapa hasil pengujian estimasi gerakan pada beberapa data uji coba disajikan pada Tabel 1 berikut
No.
Lindajalan.avi (69-70)
8x8
Tabel 1. Motion vector field hasil Estimasi Gerakan Nama Video Uk.Blok Motion Vector (frame) EBMA 9.
4x4
10.
16x16
16x16
1.
2.
8.
Fahmalari.avi (1-2)
8x8 Fahmajalan Miring.avi (110-111)
11. 3.
4x4
8x8
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6
5 6.
12.
4x4
7.
B. Pengujian Hasil Implementasi Segmentasi Gerakan dan Pelabelan Segmentasi gerakan bertujuan untuk melabel piksel citra berdasarkan gerakannya. Segmentasi gerakan ini dilakukan terhadap motion vector field yang dihasilkan oleh estimasi gerakan dengan EBMA. Beberapa pengujian estimasi gerakan terhadap beberapa data uji coba telah ditunjukkan pada Tabel 1. Segmentasi gerakan dilakukan menggunakan metode Kmeans clustering yang kemudian dilanjutkan dengan pelabelan piksel menggunakan minimisasi energi oleh Graph cut. Pengujian segmentasi gerakan dan pelabelan akan disajikan pada Tabel 2 berikut sesuai dengan urutan motion vector field pada Tabel 1.
No. 1.
Tabel 2. Segmentasi gerakan dan pelabelan motion vector field Cluster Motion Vector Pelabelan
8.
9.
10. 2.
11. 3.
12. 4.
5.
Dari beberapa data hasil segmentasi gerakan di atas terlihat bahwa ukuran blok pada estimasi gerakan EBMA memberikan pengaruh terhadap hasil pelabelan. Dari Tabel 2 secara kasat mata dapat disimpulkan bahwa pelabelan yang paling baik adalah pelabelan pada motion vector field dengan ukuran blok
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6 EBMA 4x4. Hasil ekstraksi objek bergerak dari pelabelanpelabelan pada Tabel 2 ditunjukkan oleh Gambar 6-8 berikut
(a)
(b)
(c)
Gambar 6. Hasil ekstraksi objek bergerak pada video Fahmalari.avi frame ke-62 dan ke-63 dengan ukuran blok EBMA 16x16 (a), 8x8 (b), dan 4x4 (c)
(a)
(b)
(c)
Gambar 7. Hasil ekstraksi objek bergerak pada video Lindajalan.avi frame ke-69 dan ke-70 dengan ukuran blok EBMA 16x16 (a), 8x8 (b), dan 4x4 (c)
(a)
(b)
(c)
Gambar 8. Hasil ekstraksi objek bergerak pada video Fahmajalanmiring.avi frame ke-110 dan ke-111 dengan ukuran blok EBMA 16x16 (a), 8x8 (b), dan 4x4 (c)
Dari gambar 6,7, dan 8 dapat dilihat secara kasat mata bahwa hasil ekstraksi objek bergerak yang paling baik adalah hasil ekstraksi objek dari estimasi gerakan oleh EBMA dengan ukuran blok 4x4. Waktu komputasi proses ekstraksi objek bergerak dengan masing-masing ukuran blok EBMA juga dibandingkan. Ekstraksi objek bergerak dengan ukuran blok pada EBMA yang semakin kecil membutuhkan waktu yang lebih lama. IV. KESIMPULAN Pada estimasi gerakan dengan menggunakan algoritma Excahutive Search Block Matching (EBMA), semakin kecil ukuran blok yang digunakan (4x4) akan menghasilkan pelabelan yang lebih baik. Dengan demikian, hasil ekstraksi objek bergerak yang dihasilkan juga semakin baik. Ukuran blok EBMA yang digunakan pada estimasi gerakan juga berpengaruh terhadap waktu komputasi untuk menghasilkan pelabelan. Semakin kecil ukuran blok, waktu komputasi yang dibutuhkan semakin lama. Hasil ekstraksi objek bergerak yang diperoleh dapat bermanfaat pada bidang sinematografi, salah satunya yaitu
6 dapat memberi background lain pada objek tersebut untuk menghasilkan video baru. Objek yang dapat dihasilkan pada Tugas Akhir ini masih banyak kehilangan strukturnya. Hal ini terjadi karena metode estimasi gerakan yang digunakan dilakukan terhadap blok-blok piksel. Oleh karena itu, disarankan untuk menggunakan estimasi gerakan yang dilakukan terhadap setiap piksel pada penelitian selanjutnya, misalnya optical flow. DAFTAR PUSTAKA [1] Badru Zaman,Zamzam. 2009. “Sistem Pengukuran Kecepatan Obyek Berbasis Pengolahan Citra Digital”. Tugas Akhir Fisika ITB [2] Barjatya, Aroh.2004.“Block Matching Algorithms For Motion Estimation”.DIP 6620 Spring 2004 Final Project Paper. [3] 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. [4] Bovik, Al. 2009. The Essential Guide to Video Processing. India : diacriTech [5] 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. [6] 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. [7] Gonzales, RC. Woods, RE. 2002. “Digital Image Processing”. New Jersey:Prentice Hall, Inc. [8] Han, Bing, Robert,William, Wu, Dapeng, dan Li, Jian.2007. “MotionSegmentation-Based Change Detection”. Algorithms for Synthetic Aperture Radar Imagery XIV. [9] Krokhin, Andrey. 2005.”Super Resolution in Image Sequences”. Thesis for the degree of Master of Science. Northeastern University. [10] Peinsipp, Holger.2003.”Implementation Of A Java Applet For Demonstration Of Block-Matching Motion-Estimation Algortihms”. Department of Computer Science IV. Faculty of Mathematic and Computer Science. University of Mannheim. [11] Rinaldi, Munir. “Pengolahan Citra Digital”. Informatika ITB. [12] 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. [13] Wang, Yao.2003.”Motion Estimation for Video Coding”. Polytechnic University, Brooklyn, NY11201 [14] Wang, Yao, Ostermann, Jorn, Zhang, Ya-Qin, Ostermann, Joern, dan Zhang Ya-quin. 2001. Video Processing and Communication. Prentice Hall.
