ESTIMASI GERAKAN PADA VIDEO ANIMASI 2D MENGGUNAKAN ALGORITMA PENCOCOKAN BLOK (BLOCK MATCHING ALGORITHM) Mursyidah1, Muhammad Nasir2 1 2
Jurusan Teknik Elektro, Politeknik Negeri Lhokseumawe, ACEH, 24312 Jurusan Teknik Elektro, Politeknik Negeri Lhokseumawe, ACEH, 24312 1
[email protected],
[email protected]
Abstrak Estimasi gerakan merupakan proses untuk menentukan pergerakan obyek pada video sekuensial. Pergerakan obyek dikenal dengan istilah motion vector. Sebuah motion vector menunjukkan pergeseran sebuah titik diantara frame sekarang dengan frame referensi. Dari motion vector yang didapat, akan terlihat pergerakan titik-titik yang terjadi antara frame yang diamati. Dalam penelitian ini menggunakan algoritma blok maching SAD (Sum of Absolut Different), yang proses pencarian dilakukan per pixel. Untuk menentukan kualitas gerakan objek pada setiap frame interpolasi yang didapat dengan menghitung nilai PSNR. Nilai PSNR untuk setiap teknik interpolasi yang digunakan pada frame video yang sama berkisar 33 sampai 35. Dari penelitian yang dilakukan dengan menggunakan 24 frame interpolasi didapatkan nilai PSNR semakin menurun sebesar ±1% untuk setiap frame. Kata kunci: estimasi gerakan, animasi 2D
1.
Pendahuluan Animasi atau sering disebut dengan film animasi merupakan hasil pegolahan gambar tangan sehingga menjadi gambar yang bergerak. Pada awal penemuannya, film animasi di buat dari berlembar-lembar kertas gambar yang kemudian di rekam dan diputar sehingga muncul efek gambar bergerak. Dengan bantuan komputer dan grafik komputer, pembuatan film animasi menjadi sangat mudah dan cepat. Seorang animator tidak perlu menggambar gerakan demi gerakan secara manual. Animator hanya perlu menggambarkan dua buah pose, dimana pose adalah gerakan paling ekstrim (keyframe) dari tiap gerakan yang ada. Gambar (frame-frame) baru di dapatkan dengan menggunakan teknik interpolasi. Interpolasi bisa dilakukan apabila arah pergerakan antara dua keyframe sudah diketahui. Dengan demikian perlu dilakukan estimasi gerakan dari kedua pose atau gerakan kuncinya. Estimasi gerakan dari video animasi merupakan proses utama dalam video restoration dan video compressing. Gerakan pada video animasi digambarkan dengan menggunakan istilah motion vector atau pergerakan vektor (x,y), yaitu suatu identifikasi perubahan posisi sebuah piksel atau blok piksel dari lokasi awal pada frame referensi terhadap frame target karena sebuah pergerakan obyek dalam frame.
Teknik estimasi gerakan sudah dilakukan oleh peneliti seperti teknik pixel-based motion estimation dan block matching algorithm Zhang, et al ( 2002). Dari teknik-teknik estimasi yang ada algoritma Block matching merupakan teknik yang paling banyak digunakan, Schilling, et al (1987), Nandhakumar, et al (1988), Moscheni, et al (1995), Ming,et al ( 1997). 2. Metode 2.1 Estimasi Gerakan Estimasi gerakan mempunyai peranan yang sangat penting pada pengolahan video. Banyak sekali aplikasi di pengolahan video yang memerlukan estimasi gerakan, misalkan video coding, super resolusi, restorasi video dan lainlain. Sehingga sampai saat ini estimasi gerakan masih merupakan topik yang menarik untuk diteliti. Estimasi gerakan merupakan proses untuk menentukan pergerakan obyek-obyek pada video sekuensial. Pergerakan obyek tersebut dikenal dengan istilah motion vector. Sebuah motion vector menunjukkan perpindahan sebuah titik diantara frame sekarang dengan frame referensi. Dari motion vector yang didapat, akan terlihat pergerakan titik-titik yang terjadi antar frame yang diamati. Dari situlah akan terlihat korelasi elemen temporal yang terjadi, apakah itu berupa pergerakan obyek ataukah perubahan sudut pandang atau pergerakan kamera. Contoh hasil estimasi motion vector tampak pada Gambar 2.1.
29
Salah satu teknik block matching yang umum digunakan pada pengolahan video adalah Sum of Absolute Differences (SAD). Error matching antara blok pada posisi (n1,n2) pada frame sekarang I1 , dan kandidat blok pada posisi ((n1+d1,n2+d2)) pada frame referensi J2 , dapat didefinisikan oleh Sum of Absolute Differences (SAD) sebagai:
SAD(d1 , d 2 ) =
Gambar 2.1 16x16 Motion vector dari dua frame (Sumber : Richardson 2003) Pada umumnya metoda estimasi gerakan dapat diklasifikasikan menjadi 3 kategori: metoda berbasis feature, metoda berbasis gradient dan metoda berbasis area. Diantara ketiga metoda tersebut yang sangat populer dan banyak digunakan adalah pendekatan berbasis area yang dikenal dengan block matching. Algoritma block matching terkenal akan kesederhanaannya dan kemudahan dalam implementasinya. 2.2 Algoritma Pencocokan Blok (Block Matching Algorthm) Algoritma block matching adalah sebuah cara untuk mencocokkan blok pada frame dari video digital, yang bertujuan untuk mendapatkan motion vector. Pada algoritma block matching, sebuah blok image B berpusat pada sebuah search point ‘p’ pada search frame I (n1,n2) dibandingkan dengan kandidat blok pada target frame J (n1,n2) berdasarkan kriteria matching untuk mendapatkan block matching terbaik didalam suatu pre-defined search area. Motion vector ‘vp’ dari search point ’ p’ diberikan dari pergerakan blok dalam mencari block matching terbaik. Ditunjukkan pada gambar 2.2.
∑| I (n , n ) − J (n
( n1,n 2)∈B
1
2
1
+ d1 , n2 + d 2 ) |
dengan B adalah ukuran blok. Estimasi terbaik untuk blok motion vector (v1,v2), berada pada blok yang memiliki error matching terkecil dengan posisi (n1+d1,n2+d2). Vektor (v1,v2) dapat dicari dengan menggunakan algoritma Full Search (FS) untuk menghitung dan membandingkan error mathcing untuk setiap posisi yang dicari pada frame referensi. Pada saat ini metoda full search cukup optimal dalam menentukan pencocokan blok terbaik, kompleksitas perhitungan sering menjadi penghalang. Untuk mengatasi masalah ini, banyak alternatif strategi pencarian yang cepat seperti tree-step seach, logarithmic search, crosssearch dan hierarchical search. 3.
Data dan Metodologi
Dalam penelitian ini, data yang digunakan adalah video animasi 2 Dimensi gambaran tangan yang di ekstrak menggunakan tools perangkat lunak lain yang sudah tersedia menjadi gambargambar atau frame. dalam file exstensi *jpg seperti ditunjukkan pada gambar 3.1.
Gambar 3.1 Rangkaian frame video animasi 2D Metodologi yang digunakan pada penelitian estimasi gerakan video animasi 2D secara umum ditunjukkan pada gambar 3.2.
Gambar 2.2 Prosedur Pencarian Pada Algoritma Block matching (Sumber : Zhang et al, 2002)
30
Gambar 3.4 Proses Maching Algoritma SAD. 4.
Hasil
Gambar 3.2 Blok Diagram Proses Penelitian Pada tahap pertama untuk membuat sebuah gerakan dari karakter video animasi adalah dengan menentukan dua buah gambar pose gerakan, yaitu pose gerakan awal dan pose gerakan akhir yang disebut dengan keyframe. Gambar 3.3 menunjukkan dua buah frame yang di ambil dari serangkain frame dari video animasi 2D yaitu Popeye The Sailor - Blow Me Down Tahun 1933.
Hasil dari motion estimation di gambarkan dalam bentuk arah vektor. Gambar 4.1. menunjukkan gambar hasil visualisasi dari motion vector.
(a)
(a) (b) Gambar 3.3 Gambar (a)gambar Keyframe-1 dan (b) gambar Keyframe-2 Estimasi gerakan merupakan proses untuk menentukan pergerakan obyek pada video sekuensial. Pergerakan obyek dikenal dengan istilah motion vector. Sebuah motion vector menunjukkan pergeseran sebuah titik diantara frame sekarang dengan frame referensi. Dari motion vector yang didapat, akan terlihat pergerakan titik-titik yang terjadi antar frame yang diamati. Gambar 3.4 (frame-1 sebagai frame referensi, sedangkan frame-2 sebagai frame yang dianalisa dan diestimasi gerakannya.
(b) Gambar 4.1(a), (b) Visualisasi Motion vector menggunakan Algoritma SAD dengan frame yang berbeda Dari hasil estimasi gerakan menggunakan algoritma SAD dilakukan pengujian kualitas gerakan setiap frame dengan perhitungan nilai PSNR. Nilai PSNR untuk setiap frame interpolasi seperti ditunjukkai pada Tabel 1. Tabel 1.Nilai PSNS Menggunakan Estimasi SAD
31
NILAI PSNR FRAME 1652‐1653 MENGGUNAKAN ESTIMASI SAD FRAME
LINIER INTERPOLASI
KUADRAT INTERPOLASI
CUBIC INTERPOLASI
Frame‐1
35.96190528
35.84233278
35.58354314
Frame‐2
35.71466442
35.33607005
35.24266888
Frame‐3
35.70622513
35.16975879
35.12709658
Frame‐4
35.68854046
35.07633541
34.83611062
Frame‐5
35.45834056
34.76554876
34.73063111
Frame‐6
35.42082361
34.59831262
34.67945656
Frame‐7
35.23862462
34.51686455
34.62834783
Frame‐8
35.16805856
34.39269381
34.65863204
Frame‐9
35.10295062
34.29979218
34.65192502
Frame‐10
35.06029048
34.19666494
34.70779277
Frame‐11
34.99850468
34.14673435
34.77671655
Frame‐12
34.97346565
34.12375118
34.83750204
Frame‐13
34.78250043
34.03856326
34.90499215
Frame‐14
34.77349336
34.03664993
34.89081993
Frame‐15
34.73524461
33.991803
34.86846228
Frame‐16
34.68694825
33.97003323
34.8802897
Frame‐17
34.66791242
33.98238037
34.79243849
Frame‐18
34.62783875
33.95377272
34.70958264
Frame‐19
34.52474047
34.00533194
34.68935932
Frame‐20
34.51494576
34.03989538
34.66859863
Frame‐21
34.46122729
34.03393599
34.60506032
Frame‐22
34.43333254
34.04086845
34.56939013
Frame‐23
34.41542316
34.17570517
34.52557043
Frame‐24
34.35974828
34.27917861
34.43603588
Dari gambar 4.2 merupakan grafik perbandingan hasil nilai PSNR menggunakan interpolasi linier, kuadrat dan cubic. Nilai PSNR untuk teknik interpolasi linier terus menurun mengikuti pendekatan garis lurus. Dimana nilai PSNR frame ke_1 = 35,96 ,frame ke_2 = 35,71, frame ke_3 = 35,70 sampai dengan frame ke_24 = 34,35. Dengan menggunakan teknik interpolasi kuadrat, grafik PSNR yang didapatkan dengan jumlah frame interpolasi sebanyak 24 frame. Bentuk grafik mengikuti persamaan bentuk parabola. Pada frame interpolasi ke-1 PSNR sebesar 35.84, frame interpolasi ke-2 = 35.33 dan frame interpolasi k-24= 34.27. Dengan menggunakan teknik interpolasi cubic, grafik PSNR yang didapatkan dengan jumlah frame interpolasi sebanyak 24 frame . Pada frame interpolasi ke-1 nilai PSNR sebesar 35.58, pada frame ke-2 = 35.24 dan pada frame ke-24 = 34.43. Estimasi gerakan dari video animasi 2D menggunakan algoritma Block Maching SAD dengan tiga teknik interpolasi yang dilakukan didapatkan hasil kualitas setiap frame sangat jelek. Semakin banyak frame interpolasi dibangkitkan nilai kualitas frame semakin menurun (jelek). 5.
Kesimpulan Dari hasil penelitian kualitas estimasi gerakan untuk setiap frame semakin menurun (jelek) rata-rata sebesar 1% perframe interpolasi. Metode Sum of Absolute Differences (SAD) tidak mampu melakukan estimasi gerakan apabila posisi gerakan yang di cari dari objek terlalau besar perbedaannya Daftar Pustaka Aggarwal, J.K dan Nandhakumar, N, (1988), “On The Computation Of Motion From Sequences Of Images: A Review”, Proc. IEEE, DOI: 10.1109/5.5965, pp: 76: 917935. Bing, Z.; Rexiang, L; Ming, L.L, (1997), Optimization of fast block motion estimation algorithms. IEEE Trans. Circuits Syst. Video Technol., DOI: 10.1109/76.644063, pp: 7: 833-844. Dufaux F; Moscheni, F, (1995), “Motion Estimation Techniques For Digital TV: A Review And A New Contribution”, Proc. IEEE, DOI: 0018-9219/95, pp: 83: 858876. Puri, A; Hang, H.M; Schilling, D, (1987), “An Efficient Block-Matching Algorithm For Motion Compensated Coding. Proc. International Conference On Acoustic, Speech And Signal Processing”, Texas, USA, April, pp: 1063-1066.
Gambar 4.2 Grafik Perbandingan Nilai PSNR untuk Tiga Teknik Interpolasi
32
Richardson, IEG, (2003), “H.264 And MPEG4Video Compression”, John Wiley & Sons Ltd, England. Wang, Y; Ostermann J; Zhang YQ, (2002), “Video Processing and Communications”, Prentice-Hall.
33
34
