PERCEPATAN MOTION ESTIMATION BERBASIS PHASE ONLY CORRELATION DENGAN TEKNIK FULL SEARCH MENGGUNAKAN PARALLEL THREADING PADA GRAPHICAL PROCESSING UNIT

PERCEPATAN MOTION ESTIMATION BERBASIS PHASE ONLY CORRELATION DENGAN TEKNIK FULL SEARCH MENGGUNAKAN PARALLEL THREADING PADA GRAPHICAL PROCESSING UNIT Rosa A. Asmara1, Cahya Rahmad1, dan Anik N. Handayani2 1

Laboratorium Multimedia, Politeknik Negeri Malang, Jawa Timur 65145, Indonesia [email protected], [email protected]

2

Laboratorium Multimedia, Universitas Negeri Malang, Jawa Timur, 65145 Indonesia [email protected] Abstrak

Penelitian ini menyajikan penggunaan metode Phase Only Correlation (POC) pada motion estimation dengan teknik full 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. Full Search berbasis POC adalah algoritma yang membutuhkan waktu proses lama sehingga sistem yang dicoba pada penelitian ini memproses fungsi POC pada Graphical Processing Unit (GPU) karena 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 hingga 1280x720 pixel. Hasil pengujian menunjukkan bahwa metode yang diselesaikan menggunakan GPU menunjukkan percepatan kecepatan hingga hampir dua kali lipat pada ukuran blok POC 256 x 256 daripada menggunakan CPU. Menggunakan GPU NVidia GeForce 9600GT, dengan eksekusi kernel 256 thread tiap blok, register 32-bit tiap thread berjumlah 9, dan 36 byte memory shared tiap thread blok, menunjukkan okupansi maksimum multiprosesor 100%, dengan 768 thread aktif tiap multiprosesor, 24 Warp aktif tiap multiprosesor, dan 3 thread block aktif tiap multiprosesor. Kata kunci : graphic processing unit, motion estimation

1.

Pendahuluan

Motion Estimation adalah suatu proses untuk menentukan pergerakan suatu objek pada sekuens video. Umumnya motion tersebut diwujudkan dengan vektor motion pada titik yang dipilih di dalam frame sekarang dihubungkan dengan frame lain yang disebut dengan frame referensi. Vektor motion adalah representasi perpindahan dari suatu titik antara frame sekarang dengan frame referensi [1]. Di antara berbagai macam metode estimasi motion, 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 di tengahnya di frame sekarang dibandingkan dengan blok kandidat di frame 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 motion dari titik didapat dari perpindahan blok. Metode untuk mencari block match terbaik diklasifikasikan dalam dua tipe: metode full search dan hierarchical search. Full search lebih cocok untuk mendeteksi motion lokal dari objek-objek individual sementara hierarchical search lebih cocok dipakai untuk mendeteksi motion global dari suatu scene. Full search berbasis POC adalah algoritma dengan komputasi tinggi yang berakibat membutuhkan waktu proses lama sehingga pada penelitian ini sistem yang dibangun membuat fungsi POC agar dapat diproses pada Graphical Processing Unit menggunakan teknologi parallel threading.

Jurnal Ilmu Komputer dan Informasi, Volume 3, Nomor 1, ISSN 1979 – 0732

23

Percepatan Motion Estimation Berbasis Phase Only Correlation dengan Teknik Full Search Menggunakan Parallel Threading pada Graphical Processing Unit

2.

Teori dan Algoritma

2.1. Phase Only Correlation Jika dua buah citra resolusi N1 x N2, f(n1,n2) dan g(n1,n2), yang diasumsikan range index-nya 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, F(k1,k2) dan G(k1,k2) didapat dengan menggunakan Persamaan 1 dan Persamaan 2.

F (k1, k2 ) 

f

(n1, n2 )WNk11n1WNk22 n2

 AF (k1, k2 )e

j F ( k1 , k 2 )

n1n2

(1)

G(k1 , k 2 ) 

 g (n , n )W 1

2

k1n1 k 2 n2 N1 WN 2

 AG (k1 , k 2 )e jG ( k1 ,k2 )

n1n2

(2) k1 = -M1,...,M1

(3)

k2 = -M2,...,M2

(4)

W N1  e

j

WN2  e

nn

1 2

=

rˆ(n1 , n2 ) 

kk

1 2

=

(5)

2 N2



dan didapat

 Rˆ (k1 , k2 )WNk n WNk n 1 1

1

k1k2

M1 k1   M1



2 2

2

(9) M2 k2  M 2

(10)

Asumsikan fc(x1,x2) adalah citra 2D dalam ruang temporal dengan bilangan real disimbolkan sebagai x1 dan x2. Simbol δ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). 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 Persamaan 11 dan 12.

f (n1 , n2 )  f c ( x1 , x2 ) | x1 n1T1 , x2 n2T2

(11)

g (n1 , n2 )  f c ( x1   1 , x2   2 ) | x1 n1T1 , x2 n2T2 T1 dan T2 adalah interval sampling secara spasial, dan range index didapat dari Persamaan 13. n1 = -M1,...,M1 dan n2 = -M2,...,M2.

(6)



M1 n1  M1



M2 n2  M 2

(7)

Pada Persamaan 1 dan 2, AF(k1,k2) dan AG(k1,k2) j F ( k1 ,k2 ) adalah komponen amplitudo, dan e dan jG ( k1 ,k2 ) e adalah komponen fase. Spektrum Cross-phase (atau cross spectrum ternormalisasi)

1 N1 N 2

Rˆ (k1 , k 2 )

(12)

2 N1

j

fourier 2D (2D IDFT) dari dari Persamaan 9.

Rˆ (k1 , k 2 ) didapat dari persamaan 8.

F (k1 , k 2 )G (k1 , k 2 ) Rˆ (k1 , k 2 )   e j ( k1 ,k2 ) F (k1 , k 2 )G (k1 , k 2 ) (8)

(13)

rˆ(n , n )

1 2 antara f(n1,n2) dan g(n1,n2) Fungsi POC didapat dari Persamaan 14.

rˆ(n1 , n2 ) 

sin  (n1   1 ) sin  (n2   2   N1 N 2     sin  (n1   1 ) sin  (n2   2 )  N1   N2 

Dengan α < 1 (14) Posisi puncak dari fungsi POC menyatakan perpindahan antara dua citra, dan nilai puncak α menyatakan derajat kemiripan antara dua citra. Gambar 1 menunjukkan contoh fungsi fitting untuk melakukan estimasi posisi yang benar dan tinggi dari puncak korelasi.

G(k1 , k 2 )

Ekspresi 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

24 _______________________________________________ Jurnal Ilmu Komputer dan Informasi, Volume 3, Nomor 1, ISSN 1979-0732

Rosa A. Asmara, Cahya Rahmad, dan Anik N. Handayani

POC untuk mendapatkan nilai korelasi puncak (didefinisikan sebagai nilai maksimum dari fungsi POC pada persamaan (4)) dan posisi puncak yang akan memberikan nilai pergeseran antara dua citra dengan akurasi tinggi.

Gambar 1. Fungsi fitting untuk estimasi posisi puncak dan koordinat pergeseran 2.2. Metode Full Search Pada bagian ini, kami jelaskan metode full search motion estimation berbasis POC (atau dapat juga disebut POC-FS) yang membutuhkan lebih sedikit kalkulasinya daripada full search biasa tetapi memiliki hasil pencocokan yang lebih akurat. Dianggap dua blok citra dengan ukuran W x W dengan menerapkan fungsi Hanning Window pada ukuran yang sama. Karena setengah lebar dari fungsi Hanning Window adalah , dapat dianggap pergeseran maksimum yang diestimasi antara dua blok citra adalah ± baik horizontal maupun vertikal sehingga daripada memeriksa tiap blok kandidat, kita hanya perlu untuk memeriksa blok kandidat pada interval

piksel pada area yang sama.

Prosedur untuk POC-FS Input: Citra sekarang I( ) Citra referensi J( ) Titik p I( ) Output: Titik korespondensi q dari titik p pada J( ) Motion vector dari titik p Langkah 1: Ekstrak citra perblok dengan ukuran blok W x W dengan titik p berada di bagian tengah pada frame sekarang I( ) Langkah 2: Kalkulasi fungsi POC antara blok citra dari frame sekarang I( ) dan blok kandidat dari

Langkah 3: Identifikasi 3 blok cocok terbaik pada Langkah 2 dan geser blok-blok tersebut menurut nilai pergeserannya sehingga akan didapatkan puncak korelasi pada bagian tengah dari blok. Kalkulasi ulang fungsi POC untuk 3 kandidat blok baru. Blok paling cocok adalah blok dengan korelasi puncak tertinggi diantara tiga blok. Fungsi POC yang digunakan lagi adalah fungsi POC versi sederhana. Titik korespondensi q diposisikan di bagian tengah dari blok yang paling cocok. Langkah 4: Gambarkan motion vektor Pada percobaan, kami menggunakan ukuran window 128x128 dan area pencarian 64 horizontal dan vertikal. 2.3 Parallel Threading GPU GPU dipabrikasi dan lebih cocok dipakai untuk menyelesaikan permasalahan yang dapat diekspresikan ke dalam komputasi parallel-data (program yang sama dieksekusi pada banyak elemen data dalam paralel) dengan intensitas aritmatika tinggi (rasio dari operasi aritmatika dibandingkan operasi memori). Karena program yang sama dieksekusi untuk tiap elemen data, dibutuh spesifikasi yang lebih rendah untuk flow control canggih. Karena dijalankan pada banyak elemen data dan memiliki intensitas aritmatika tinggi, akses memori latency dapat disembunyikan dengan perhitungan tanpa cache data yang besar. Pemrosesan data paralel memetakan elemen data pada thread parallel processing. Banyak aplikasi yang memproses set data berukuran besar dapat menggunakan model pemrograman data-paralel untuk mempercepat perhitungan. Pada rendering 3D, set piksel dan titik berukuran besar dipetakan pada thread paralel. Dengan cara yang sama, aplikasi pemrosesan media dan citra seperti post-processing dari citra dirender, video encoding dan decoding, penskalaan citra, stereo vision, dan pengenalan pola dapat memetakan blok citra dan piksel pada thread parallel processing. Kenyataannya, banyak algoritma selain bidang rendering dan pemrosesan citra dapat dipercepat menggunakan pemrosesan data-parallel, dari pemrosesan sinyal umum ataupun simulasi fisika hingga komputansi financial atau komputasi biologi.

frame referensi J( ) tiap piksel pada area pencarian. Kami gunakan versi sederhana dari fungsi


25


Tipe data dari GPU yang kami gunakan hanya dapat memproses data single precision sehingga kami harus mengkonversi tipe datanya terlebih dahulu jika data kita pada double precision.

Langkah 3: Komputasi paralel FFT paralel GPU. Langkah 4: Buat kernel GPU untuk Cross Correlation untuk melakukan estimasi pergeseran. Pada percobaan, kami menggunakan 256 thread per block. Langkah 5: Komputasi paralel IFFT pada GPU. Langkah 6: Pindahkan kembali hasil pergeseran dari GPU ke CPU. Langkah 7: Konversi kembali tipe data dari single precision ke double precision. Langkah 8: Gambarkan motion vector. Table 1 : Spesifikasi fisik GPU yang digunakan

(a) Threads / Warp

32

Warps / Multiprocessor

24

Threads / Multiprocessor

768

Thread Blocks / Multiprocessor

8

Total # of 32-bit registers /

(b)

Multiprocessor

8192

Register allocation unit size

256

Shared Memory / Multiprocessor (bytes)

16384

Warp allocation granularity (untuk alokasi register)

3.

(c) Gambar 2. (a) translasi pergeseran dari puncak korelasi (b) dan (c) dengan phase only correlation menggunakan GPU Prosedur untuk POC GPU Langkah 1: Konversi tipe data input dari double precision ke single precision. Langkah 2: Pindahkan data single precision dari RAM CPU ke RAM GPU.

2

Eksperimen dan Evaluasi

Untuk melakukan manajemen dari ribuan thread yang berjalan bersamaan, multiprosesor menggunakan arsitektur yang dinamakan SIMT (single instruction, multiple thread). Multiprosesor memetakan tiap thread pada satu core prosesor skalar, dan tiap thread skalar dieksekusi tersendiri sesuai dengan alamat instruksinya dan register pada multiprosesor yang bersangkutan. Unit SIMT dari multiprosesor membuat, mengelola, menjadwal, dan mengeksekusi thread ke dalam group 32 thread paralel dan dinamakan Warp. Maximum Occupancy dari multiprosesor adalah rasio dari jumlah Warp aktif terhadap jumlah maksimum Warp yang dapat ditangani oleh satu multiprosesor GPU. Tiap multiprosesor memiliki sejumlah N register yang dapat digunakan oleh. Register-register ini adalah resource yang di-sharing dan dialokasikan pada thread di dalam block yang dieksekusi. Compiler berusaha untuk meminimalisasi penggunaan register



untuk memaksimalkan jumlah thread yang aktif secara simultan. Jika program mencoba untuk memproses kernel dengan register yang digunakan tiap thread dikalikan dengan thread block lebih besar dari N, proses akan gagal. Ukuran N dari GPU yang digunakan pada penelitian ini adalah 8192 32-bit register tiap multiprosesor. Dari spesifikasi fisik GPU yang ditunjukkan pada Tabel 1, kami dapat mengkalkulasi maximum occupancy multiprocessor sebagai berikut:



x1   min n  | n  

thread per block   thread per warp 

persamaan (8), (9), dan (10), yang nilainya sama dengan thread block aktif per multiprocessor. Active Warp per multiprocessor = Active thread block per multiprocessor X Warp per thread block = 24 (21) Active Threads per Multiprocessor = Active thread block per multiprocessor X thread per block = 768 (22) Multiprocessor Maximum Occupancy = (Active Warp per multiprocessor / Warp per multiprocessor) X 100% = 100% (23)

dengan x1 = 8 (15)

dengan   nilai integers , x1 ≈ Warp tiap thread block Jika

x2   min n | n  x1 , warp allocation granularity

, maka

x3   min n | n  x2  r1  32, y 2  (a)

x3 = 2304 (16) denganr1= register per thread, y2= ukuran unit register allocation, x3 ≈ register tiap thread block

x4   min n  | n  shared mem. per thread,512 x4= 512 (17) dengan x4 ≈

shared memory tiap thread block



x5   max n | n  

Limit warp per multiprocessor   warp per block 

(b)

x5 = 3 (18) dengan x5 ≈

Max. Warp tiap multiprocessor



x6   max n  | n  

Total register per multiproce ssor   register per thread block 

x6 = 3 (19) dengan x6 ≈ Max. Register tiap multiprocessor 

x7   max n  | n  

(c)

shared memory per multiproce ssor   shared memory per thread block 

x7= 32 dengan x7 ≈ Max. Shared multiprocessor. Dengan mengambil nilai

memory minimum

(20) per dari

Gambar 3. (a) Motion Vector dari Mobile Calendar menggunakan blok berukuran 32x32 diambil dari frame referensi (b) dan frame sekarang (c) Chart berikut adalah hasil dari lamanya waktu komputasi dari Full Search dan Hierarchical Search


27


2 Layer menggunakan blok POC berukuran 32x32 hingga 256x256. Bar kuning adalah waktu komputasi pada CPU, dan bar berwarna merah adalah waktu komputasi pada GPU. Full Search POC CPU vs GPU

256x256. Bar kuning adalah rasio waktu komputasi pada full search, bar merah adalah rasio waktu komputasi pada hierarchical 3 layer, dan bar hijau adalah rasio waktu komputasi pada hierarchical search 2 layer. 4. Kesimpulan

40

time (seconds)

35 30 25 FS POC CPU

20

FS POC GPU

15 10 5 0 32

64

128

256

POC Block

Gambar. 4. Waktu komputasi dari Full Search POC GPU dan CPU 2 Layer HS POC CPU vs GPU 160

time (seconds)

140 120 100 HS POC CPU

80

5. Ucapan Terima Kasih

HS POC GPU

60

Penulis mengucapkan terima kasih pada Direktur Jenderal Pendidikan Tinggi, Direktorat Pendidikan Tinggi, Departemen Pendidikan Nasional Indonesia atas dukungan finansialnya sehingga penelitian ini dapat terselesaikan dengan baik.

40 20 0 32

64

128

256

POC Block

Gambar 5. Processing time of Hierarchical Search POC GPU and CPU 2 layer Time Process Ratio GPU/CPU 2.5 2 Ratio

Penelitian pada paper ini menyajikan percepatan motion estimation berbasis POC dengan teknik hierarchical search menggunakan GPU. Pada metode yang digunakan, hasil motion vector didapat dari proses hasil pergeseran blok citra pada GPU. Kami telah menunjukkan bahwa metode yang digunakan rata-rata dapat menyelesaikan komputasi + 1,7 kali lebih cepat dibandingkan menggunakan metode yang sama pada CPU. Menggunakan GPU NVidia GeForce 9600GT, kernel dieksekusi dengan 256 thread per block, 9 32-bit register per thread, dan 36 bytes memory shared untuk tiap thread block, maximum occupancy multiprocessor adalah 100%, dengan 768 threads active per multiprocessor, 24 Warps Active per multiprocessor, dan 3 thread blocks active per multiprosessor.

FS POC

1.5

3 Layer HS POC 1

2 Layer HS POC

0.5 0 32

64

128

256

POC Block

Gambar 6. Rasio waktu komputasi antara POC full search, hierarchical search 3 layer, dan hierarchical search 2 layer pada GPU dan CPU. Gambar 6 adalah hasil dari rasio waktu komputasi antara CPU dan GPU pada hierarchical search 2 layer, hierarchical search 3 layer, dan full search menggunakan blok POC berukuran 32x32 hingga

REFERENSI [1] Loy Hui Chien and Takafumi Aoki, ”Robust Motion Estimation for Video Sequences Based on Phase-Only Correlation,” 6th 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. 163165, 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] GPGPU Vis Course, Minneapolis, USA, 2005.



[6] Nuno Vasconcelos, “Coarse-to-Fine Least Squares Motion Estimator”, October 23, 1993. [7] Sudipta N. Sinha, Jan-Michael Frahm, Marc Pollefeys, Yakup Genc, “GPU-based Video Feature Tracking and Matching”, 2004 [8] Eero P. Simoncelli, “Coarse-to-Fine Estimation of Visual Motion”, 8th Workshop on Image and Multidimensional Signal Processing in Cannes France, IEEE Signal Processing Society, September 1993. [9] John Watkinson, “The Engineer’s Guide to Motion Compensation”, 1994 [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, 2009


29

PERCEPATAN MOTION ESTIMATION BERBASIS PHASE ONLY CORRELATION DENGAN TEKNIK FULL SEARCH MENGGUNAKAN PARALLEL THREADING PADA GRAPHICAL PROCESSING UNIT

Recommend Documents