SEMINAR NASIONAL ELECTRICAL, INFORMATICS, AND IT’S EDUCATIONS 2009
Percepatan Motion Estimation Berbasis Fase Dengan Teknik Hierarchical Search Menggunakan Graphical Processing Unit (GPU) Rosa A. Asmara dan M. Hariadi Jurusan Elektro Bidang Keahlian Jaringan Cerdas Multimedia Institut Teknologi 10 Nopember Surabaya 60111, Indonesia Email :
[email protected]
Abstrak Pada paper ini menyajikan penggunaan metode Phase Only Correlation (POC) pada motion estimation dengan teknik hierarchical search menggunakan Graphical Processing Unit (GPU). Menggunakan fungsi POC, seseorang dapat melakukan estimasi translasi motion antara dua blok citra referensi dan citra yang diproses. Motion Estimation adalah proses untuk menentukan pergerakan suatu objek pada sekuens video digital. Pergerakannya umumnya diwakili dalam bentuk vector gerakan pada titik yang dipilih dalam frame sekarang dibandingkan dengan frame lain yang disebut sebagai frame referensi. Motion Estimation adalah hal mendasar pada beberapa bidang seperti image processing, image analysis, video coding, dan computer vision. Hierarchical Search berbasis POC adalah algoritma yang membutuhkan waktu proses lama, sehingga system yang dicoba pada tesis ini memproses fungsi POC pada Graphical Processing Unit (GPU), dimana GPU memiliki kelebihan dalam menyelesaikan perhitungan bilangan floating point dibandingkan CPU. Evaluasi dilakukan dengan menghitung kecepatan waktu proses menggunakan GPU pada video resolusi tinggi dengan resolusi 1280 x 720 pixel. Hasil percobaan menunjukkan bahwa metode yang diajukan jika diselesaikan menggunakan GPU akan meningkatkan akselerasi proses hingga lebih dari dua kali lebih cepat dibandingkan jika diselesaikan menggunakan CPU. Kata kunci : Motion Estimation, computer vision, image processing, POC, GPU, CUDA, coarseto-fine search technique.
1. Pendahuluan Estimasi gerakan adalah suatu proses untuk menentukan pergerakan suatu objek pada sekuens video. Umumnya pergerakan tersebut diwujudkan dengan vektor gerakan pada titik yang dipilih didalam frame sekarang dihubungkan dengan frame lain yang disebut dengan frame referensi. Vektor gerakan adalah representasi perpindahan dari suatu titik antara frame sekarang dengan frame referensi [1]. Diantara berbagai macam metode estimasi gerakan, algoritma pencocokan blok adalah yang paling banyak digunakan dan populer karena kesederhanaan dalam aplikasinya. Pada algoritma pencocokan blok, suatu blok citra yang berpusat pada satu titik ditengahnya diframe sekarang dibandingkan dengan blok kandidat diframe referensi berdasarkan perbedaan atau persamaan tertentu untuk menemukan blok cocok yang terbaik pada area yang dicari. Salah satu contoh pengukuran dari perbedaan adalah Sum of Absolute Differences (SAD). Vektor gerakan dari titik didapat dari perpindahan blok. Saat ini, teknik pencocokan citra akurasi tinggi menggunakan fungsi Phase Only Correlation (POC) telah dibuat dan diaplikasikan [1]-[4]. Menggunakan fungsi POC, kita dapat mengestimasi perpindahan translasional sebagai suatu derajat kesamaan
diantara dua blok citra dari lokasi dan tinggi puncak korelasi, secara berturut-turut. Telah ditunjukkan bahwa teknik pencocokan ini dapat mengestimasi perpindahan diantara dua citra dengan 1/100 akurasi pixel pada ukuran citra 100x100 pixel [3]. Salah satu permasalahan umum dari teknik POC ini adalah waktu komputasinya yang lama. Untuk mengatasi hal tersebut, maka proses komputasi dapat dilakukan oleh GPU (Graphical Processing Unit). GPU adalah suatu prosessor khusus yang dibuat untuk melakukan perhitungan rumit. Umumnya GPU digunakan dalam bidang komputer grafis untuk mengolah gambar-gambar dengan tingkat kompleksitas tinggi. Seiring perkembangannya, GPU saat ini telah dapat juga digunakan untuk proses komputasi untuk tujuan umum (General Purpose GPU - GPGPU). Dimulai dengan GPGPU, menggunakan CG-Toolkit. Akan tetapi proses menggunakan CG-Toolkit masih dirasa terlalu merepotkan bagi developer program, karena proses komputasi yang akan diolah GPU harus diubah terlebih dahulu menjadi data citra (Texture mapping). Untuk mengatasi hal tersebut, beberapa manufaktur GPU dunia telah mengembangkan bahasa tingkat tinggi untuk melakukan proses komputasi menggunakan GPU. Penelitian ini mengusulkan perancangan dan pembuatan estimasi gerakan berbasis POC pada B1-60
SEMINAR NASIONAL ELECTRICAL, INFORMATICS, AND IT’S EDUCATIONS 2009
sekuens video dan memanfaatkan GPU sebagai proses komputasinya, diharapkan dari penelitian ini akan didapat suatu aplikasi estimasi gerakan akurasi tinggi dengan proses yang lebih cepat karena komputasinya menggunakan GPU. 2. Phase Only Correlation Phase Only Correlation adalah suatu metode untuk membandingkan fase block pada frame yang dianalisa dengan fase block pada frame referensi. Komponen fase didapat dari hasil transformasi diskrit 2D pada frame. Jika dua buah citra resolusi N1 x N2, f(n1,n2) dan g(n1,n2), dimana kita asumsikan range indexnya adalah n1= -M1,...,M1 dan n2= -M2,...,M2 agar lebih sederhana dalam perhitungan, sehingga N1 = 2M1 + 1 dan N2 = 2M2 + 1. Jika F(k1,k2) dan G(k1,k2) adalah diskrit transformasi fourier 2D (2D DFTs) dari dua buah citra, maka F(k1,k2) dan G(k1,k2) didapat dari,
F (k1 , k 2 ) = ∑ f n1n2
B1-61
Anggap bahwa f(n1,n2) dan g(n1,n2) adalah citra yang tersampling secara spasial dari fc(x1,x2) dan fc(x1- δ1,x2- δ2), dan didefinisikan dengan, f (n1 , n2 ) = f c ( x1 , x 2 ) | x =n T , x =n T , 1
1 1
2
2 2
g (n1 , n2 ) = f c ( x1 − δ 1 , x2 − δ 2 ) | x1 =n1T1 , x2 =n2T2 Dimana T1 dan T2 adalah interval sampling secara spasial, dan range index didapat dari n1 = -M1,...,M1 dan n2 = -M2,...,M2. Fungsi POC rˆ( n1 , n2 ) antara f(n1,n2) dan g(n1,n2) didapat dari,
rˆ(n1, n2 ) ≅
sin{π(n1 +δ1)} sin{π (n2 +δ2} N1N2 π π sin (n1 +δ1) sin (n2 +δ2 ) N1 N2
α
, (5) Dimana α < 1. Posisi puncak dari fungsi POC menyatakan perpindahan antara dua citra, dan nilai k1n1 k2n2 jθ Fpuncak ( k1 , k2 ) α menyatakan derajat kemiripan antara dua (n1 , n2 )W N WN = AF (k1 , k 2 )e citra. 1 2
(1)
G (k1 , k 2 ) = ∑ g ( n1 , n2 )WNk1n1W Nk2n2 = AG (k1 , k 2 )e jθG ( k1 ,k2 ) 1
n1n2
Dimana
W N1 = e
∑ nn
1 2
(2) = -M1,...,M1,
k1 2π
−j
N1
WN2 = e
,
2π −j N2
dinyatakan dengan
2
k2 ,
=
-M2,...,M2,
dan
operator
∑ nM=− M ∑ nM =− M 1
2
1
1
2
2
,
AF(k1,k2) dan AG(k1,k2) adalah komponen amplitudo, jθ ( k , k ) jθ ( k , k ) dan e F 1 2 dan e G 1 2 adalah komponen fase. Spektrum Cross-phase (atau cross spectrum ternormalisasi)
Rˆ (k1 , k 2 ) didapat dari,
F (k1 , k 2 )G (k1 , k 2 ) Rˆ (k1 , k 2 ) = = e jθ ( k1 ,k2 ) F (k1 , k 2 )G (k1 , k 2 ) G (k1 , k 2 )
Dimana
menyatakan
konjugasi
kompleks dari G(k1,k2) dan θ(k1,k2) = θF(k1,k2) – θG(k1,k2). Fungsi Phase Only Correlation rˆ( n1 , n2 ) adalah inverse diskrit transformasi fourier 2D (2D
Rˆ (k1 , k 2 ) dan didapat dari 1 rˆ(n1 , n2 ) = Rˆ (k1 , k 2 )W N−k1n1W N−k2n2 ∑ 1 2 N1 N 2 k1k2
Gambar 1. Fungsi Fitting untuk estimasi posisi puncak 3. Metode Pencarian Hierarki Pada metode estimasi gerakan dengan pencarian hierarki berbasis POC (POC-Hierarchical Search), beberapa versi coarse (halus) dari citra (3) Metode ini juga dikenal masukan awal dibuat. dengan nama coarse-to-fine correspondence search technique [4]. Pencocokan blok berbasis POC dimulai dari layer citra terkasar dan operasinya berlanjut ke layer yang lebih halus. Motion vector yang terdeteksi pada tiap layer di periksa pada layer berikutnya. Untuk lebih jelasnya dapat dilihat pada gambar berikut.
IDFT) dari
∑kk
Dimana
1 2
∑ kM=− M ∑ kM =− M 1
1
2
1
2
2
menyatakan
.
Dianggap fc(x1,x2) adalah citra 2D dalam ruang temporal dengan bilangan real disimbolkan sebagai x1 dan x2. δ1 dan δ2 mewakili perpindahan subpixel fc(x1,x2) pada arah x1 dan x2. Maka citra yang berpindah dapat disimbolkan fc(x1- δ1,x2- δ2).
(4)
SEMINAR NASIONAL ELECTRICAL, INFORMATICS, AND IT’S EDUCATIONS 2009
Gambar 2. Metode Pencarian Hierarki Jika po adalah titik yang diberikan pada citra yang dianalisa, dan qo adalah titik korespondensi pada citra referensi, pl dan ql adalah titik yang cocok pada layer ke-l. Tujuan dari pencarian korespondensi adalah mencari titik korespondensi qo dari titik po dan dengan demikian, akan didapatkan motion vector po sebagai qo – po. Berikut adalah prosedur dari POC-HS : Masukan : Citra yang dianalisa Io(n1,n2)(=I(n1,n2)), Citra referensi Jo(n1,n2)(=J(n1,n2)), Titik po (= p) pada Io(n1,n2) Keluaran : Titik korespondensi qo dari titik po pada Jo(n1,n2), motion vector
B1-62
Citra Referensi (Frame 100)
Citra yang diproses (Frame 105)
v HS po dari titik po.
Langkah 1: Untuk layer l = 1,2,...,lmax, buat layer ke-l pada citra Il(n1,n2) dan Jl(n1,n2), sebagai contoh versi kasar dari Io(n1,n2) dan Jo(n1,n2) adalah:
1 l I l (n1 , n2 ) = ∑ 4 i1 =0 1 l J l ( n1 , n2 ) = ∑ 4 i1 =0
l
∑ I l −1 (2n1 + i1 ,2n2 + i2 ) ,
i2 =0 l
∑ J l −1 (2n1 + i1 ,2n2 + i2 ) .
i2 =0
Pada percobaan yang telah dilakukan [4] telah diset nilai untuk lmax pada 2 atau 3 tergantung pada range gerakan yang diinginkan. Langkah 2: Pada tiap layer l = 1,2,...,lmax, hitung koordinat pl = (pl1,pl2) yang berkorespondensi dengan titik asal po :
1 1 1 pl = pl −1 = pl −1 1 , pl −1 2 2 2 2 Langkah 3: Diasumsikan bahwa qlmax = plmax pada layer terkasar, dengan l = lmax – 1. Langkah 4: Dari citra layer ke-l Il(n1,n2) dan Jl(n1,n2), diambil dua blok citra (dengan ukuran W x W) yaitu fl(n1,n2) dan gl(n1,n2) dengan titik pusatnya secara berturut-turut pada pl dan 2ql+1. Untuk keakurasian pencocokan, ukuran dari blok citra selayaknya besar. Pada penelitian sebelumnya, digunakan 32 x 32 blok citra. Langkah 5: Hitung jarak perpindahan antara fl(n1,n2) dan gl(n1,n2) dengan akurasi pixel menggunakan fungsi POC yang telah disederhanakan. Jika vector jarak perpindahannya adalah δl, maka korespondensi layer ke-l ql didapatkan dengan : ql = 2ql+1 + δl. Langkah 6: Kurangi counter dengan 1 untuk l = l – 1 dan ulangi dari langkah 4 sampai langkah 6 jika l>=0. Langkah 7: Didapatkan nilai motion vector
v HS po = qo − po .
Gambar 3. Hasil motion vector Mobile Calendar 320x240 dengan 8 macroblock dan 4 search parameter 4. Phase Only Correlation menggunakan GPU Beberapa langkah yang harus dilakukan untuk melakukan proses di GPU adalah: 1. Alokasi Memori ke GPU. 2. Perpindahan data dari RAM CPU ke RAM GPU. Pada Matlab, tipe data yang dipakai adalah Double precision, sedangkan perangkat CUDA yang dipakai pada sistem ini hanya mendukung Single Precision. Sehingga sebelum data ditransfer ke RAM GPU, jika data yang akan diproses bertipe Double precision, maka data harus dikonversi ke Single precision. 3. Data pada RAM CPU perlu dialokasikan. 4. Saat data sudah berada di GPU, maka data sudah siap diproses menggunakan CUDA (membuat fungsi sendiri atau library yang ada seperti CUBLAS/CUFFT). 5. Perpindahan data hasil proses dari GPU ke CPU. Jika diperlukan, data dapat dikonversi lagi ke Double precision. 6. Bersihkan alokasi memori pada GPU. Berikut adalah diagram proses dari POC menggunakan GPU:
SEMINAR NASIONAL ELECTRICAL, INFORMATICS, AND IT’S EDUCATIONS 2009
B1-63 3 Layer HS POC CPU vs GPU
time (seconds)
600 500 400 HS POC CPU
300
HS POC GPU
200 100 0 32
64
128
256
POC Block
Gambar 6. Selisih rata-rata waktu proses antara Hierarchical Search CPU dan GPU 3 layer (semakin kecil bar, hasilnya semakin baik) 2 Layer HS POC CPU vs GPU 160
120 100 HS POC CPU
80
HS POC GPU
60 40 20 0 32
64
128
256
POC Block
Gambar 7. Selisih rata-rata waktu proses antara Hierarchical Search CPU dan GPU 2 layer (semakin kecil bar, hasilnya semakin baik) Time Process Ratio GPU/CPU 2.5 2 Ratio
Gambar 4. Diagram Alir POC GPU 5. Hasil Pengujian dan Analisa Sistem yang diusulkan diimplementasikan dan diuji pada PC dengan sistem operasi Windows XP profesional SP2 dengan prosessor Intel Pentium Core2Duo, memori DDR2 512MB, Kartu grafis yang mendukung CUDA dengan spesifikasi Albatron NVIDIA GeForce 9600GT PCIExpress 512MB DDR3. File video yang diproses adalah video dataset dengan format .AVI dengan kecepatan 30 frame per second. Citra yang diproses adalah setiap 5 frame. Perangkat lunak yang digunakan adalah MATLAB 2007ª, untuk editing video menggunakan Ulead Video Studio, sedangkan compiler yang digunakan untuk mengcompile tool MEX CUDA adalah Microsoft Visual C++ 2005. Diagram berikut berturut-turut adalah hasil pengujian yang didapatkan:
time (seconds)
140
FS POC
1.5
3 Layer HS POC 1
2 Layer HS POC
Full Search POC CPU vs GPU 0.5
40
0
time (seconds)
35
32
30
64
128
256
POC Block
25 FS POC CPU
20
FS POC GPU
15 10 5 0 32
64
128
256
POC Block
Gambar 5. Selisih rata-rata waktu proses antara Full Search CPU dan GPU (semakin kecil bar, hasilnya semakin baik)
Gambar 8. Perbandingan kecepatan proses pada Full Search, 3 layer Hierarchical Search, 2 layer Hierarchical Search POC antara GPU dan CPU 6. Kesimpulan Dari hasil percobaan, terlihat perbandingan kecepatan optimal didapat dari POC Hierarchical Search 2 layer pada POC block 256, yaitu bernilai sekitar 2,1. Atau dengan kata lain, dengan POC Hierarchical Search 2 layer pada 256 POC block, diproses menggunakan GPU akan lebih cepat 2,1 kali daripada diproses menggunakan CPU. Tidak menutup kemungkinan, jika teknologi dimasa mendatang lebih maju dan ukuran resolusi video menjadi lebih tinggi, maka sistem ini juga akan
SEMINAR NASIONAL ELECTRICAL, INFORMATICS, AND IT’S EDUCATIONS 2009
dapat menyelesaikan permasalahan dengan lebih cepat tingkat rasionya. 7. Daftar Pustaka [1] Loy Hui Chien and Takafumi Aoki, ”Robust Motion Estimation for Video Sequences th Based on Phase-Only Correlation,” 6 IASTED International Conference Signal and Image Processing, pp. 441-446, August 2004. [2] C.D. Kuglin and D.C. Hines, “The phase correlation image alignment method,” Proc. Int. Conf. on Cybernetics and Society, pp. 163-165, 1975. [3] K. Takita, M.A. Muquit, T. Aoki, and T. Higuchi, “High-Accuracy subpixel image registration based on phase-only correlation,” IEICE Trans. Fundamentals, Vol. E86-A, No. 8, pp. 1925-1934, August 2003. [4] K. Takita, M. A. Muquit, T. Aoki, and T. Higuchi,“A sub-pixel correspondence search technique for computer vision applications,” IEICE Trans. Fundamentals, 2004. [5] Ensiklopedia online, http://www.en.wikipedia.org [6] GPGPU Vis Course, Minneapolis, USA, 2005. [7] Nuno Vasconcelos, “Coarse-to-Fine Least Squares Motion Estimator”, October 23, 1993. [8] Sudipta N. Sinha, Jan-Michael Frahm, Marc Pollefeys, Yakup Genc, “GPU-based Video Feature Tracking and Matching”, 2004 [9] Eero P. Simoncelli, “Coarse-to-Fine Estimation of th Visual Motion”, 8 Workshop on Image and Multidimensional Signal Processing in Cannes France, IEEE Signal Processing Society, September 1993. [10] NVidia Cuda Team, “SC-07 Cuda Tutorial”, 2007 [11] GPGPU VISCOURSE05, International conference on GPGPU, Minneapolis USA, April 20, 2005. [12] Matlab R2007a Documentation, 2007. [13] Nvidia Developer Team, “NVIDIA CUDA Programming Guide Version 2.0”, 6/7/2008. [14] Nvidia Developer Team, “CUDA Reference Manual Version 2.0”, June 2008. [15] Nvidia Developer Team, “CUDA CUFFT Library Manual Version 2.0”, April 2008. [16] Nvidia Developer Team, “CUDA nvcc Manual Version 2.0”, January 04 2008. [17] Nvidia Developer Team, “Nvidia White Paper, Accelerating MATLAB with CUDA using MEX Files”, September 2007. [18] Nvidia CUDA Forums, http://forums.nvidia.com/index.php?showforum=62 8.
B1-64
