BAB II TINJAUAN PUSTAKA
2.1
Teknik Pengkodean Video Konvensional Teknik pengkodean video merupakan software untuk video kompresi pada
video digital. Seiring dengan munculnya berbagai macam aplikasi video digital, dibutuhkan standar pengkodean video yang dapat meningkatkan kompresi. Teknik pengkodean konvensional cocok digunakan untuk televisi digital, penyimpanan digital dan video streaming. Proses prediksi interframe (arah pergerakan) pengkodean video konvensional terjadi dienkoder. Seperti ditunjukkan pada gambar 2.1.
Prediksi Interframe Enkoder
X
Prediksi Intraframe Dekoder
Y
Y
X’
Side information Gambar 2.1 Model Teknik Pengkodean Video Konvensional (Sumber : Widyantara, O., 2011)
Gambar 2.1 menjelaskan bahwa proses prediksi interframe digunakan informasi yang diperoleh dari eksploitasi spasial dan temporal pada objek yang sama antara dua frame yang berurutan dienkoder. Sehingga fungsi dekoder hanya merekonstruksi interframe yang dikirim oleh enkoder.
7
8
Gambar 2.2 Arsitektur Teknik Pengkodean Video Konvensional (Sumber : Richardson, 2002)
Dari gambar 2.2 dapat dijelaskan sebagai berikut: 1.
Proses perkiraan arah pergerakan (motion estimation) Proses ini bertujuan untuk membentuk prediksi arah pergerakan frame sekarang dari frame yang menjadi frame referensi. Frame yang menjadi frame referensi adalah frame sebelumnya atau frame yang telah direkonstruksi. Teknik yang paling akurat digunakan dalam proses perkiraan arah pergerakan yaitu teknik Block Matching ’model’. Proses ini membandingkan piksel antara frame sekarang dengan frame referensi dalam jendela pencarian yang telah diatur, dapat dilihat pada gambar 2.3. Sasarannya adalah untuk mendapatkan nilai Mean Square Erorr (MSE) terkecil. Maka untuk setiap blok dari frame sekarang, algoritma untuk mendapatkan arah pergerakan frame yang berupa vektor adalah yang memberikan nilai MSE terkecil yang dibandingkan dengan blok pada frame sebelumnya.
Gambar 2.3 Teknik Block Matching (Sumber : Kondoz, A., 2009)
9
2.
Kompensasi Pergerakan (Motion Compensation) Kompensasi pergerakan frame sekarang yaitu mengurangkan frame sekarang dengan ’model’ untuk menghasilkan sebuah frame residual yang terkompensasi pergerakannya. Frame ini kemudian dikirimkan ditambah dengan informasi-informasi (frame encode residual) yang diperlukan oleh dekoder untuk merekonstruksi sebuah model. Informasi ini berupa susunan pergerakan vektor. Di dekoder, frame residual yang telah dikodekan (frame encode residual) dikodekan kembali dan ditambahkan dengan ’model’ untuk merekonstruksi frame sekarang. Frame hasil rekonstruksi ini kemudian disimpan untuk digunakan sebagai frame referensi. Dari proses arah pergerakan dan kompensasi pergerakan seperti gambar 2.2
menyebabkan banyak data yang dibuang untuk memperoleh bit rate yang sekecil mungkin. Adapun data yang akan dibuang dikelompokkan menjadi 3 jenis (Kondoz, A., 2009) yaitu: a.
Redundansi Spasial Redundansi spasial adalah redundansi yang terdapat dalam suatu frame yang disebabkan adanya korelasi antara sebuah piksel dengan piksel disekitarnya. Redundansi ini dimanfaatkan untuk melakukan kompresi intraframe. Pada gambar 2.4 ditunjukkan terdapat redundansi spasial pada area kulit.
Gambar 2.4 Redundansi Spasial (Sumber : Kondoz, A., 2009)
10
b.
Redundasi Temporal Redundansi temporal adalah redundansi yang terdapat diantara sebuah frame dengan frame sebelum atau sesudahnya. Hal ini disebabkan piksel-piksel yang berkorelasi diantara frame-frame tersebut. Redundansi ini terutama dikarenakan banyak bagian frame yang tidak berubah dibanding frame sebelum dan sesudahnya. Redundansi temporal dimanfaatkan untuk melakukan kompresi interframe. Pada gambar 2.5 ditunjukkan dua frame secara berturut-turut pada rangkaian video dan menunjukkan terdapat perbedaan yang sangat kecil pada kedua frame tersebut.
Gambar 2.5 Redundansi Temporal (Sumber : Kondoz, A., 2009)
c.
Redundansi Pengkodean Sumber Redundansi ini terjadi jika simbol yang dihasilkan oleh video codec tidak efisien jika dipetakan menjadi aliran bit biner. Teknik entropi dapat digunakan untuk mengeksploitasi probabilitas keluaran dari data video ketika beberapa simbol memiliki probabilitas kemunculan lebih banyak dari yang lainnya.
11
2.2
Teknik Pengkodean Video H.264 Semakin meningkatnya revolusi pada siaran pertelevisian dan industri
entertainment seperti Digital Video Disc (DVD) membawa paradigma baru sebuah standar pengkodean video untuk meningkatkan kualitas kompresi. Menjawab kebutuhan tersebut ( Wiegand,T., 2003) ITU-T bekerja sama dengan MPEG (Motion Picture Expert Group) mengeluarkan standar video digital terbaru, yaitu H.264 atau Advance Video Coding (AVC). Tujuan pengembangan H.264/AVC adalah untuk membuat suatu standar video digital yang dapat menghasilkan kualitas video yang baik pada bit rate yang lebih kecil dibandingkan dengan standar video digital sebelumnya (MPEG-2, H.263) tanpa harus melakukan perubahan yang kompleks dan dapat diimplementasikan dengan biaya yang murah. Pada proses dekoding H.264/AVC, entropy dekoder mendekodekan koefisien kuantisasi dan data gerakan yang digunakan untuk intraframe (prediksi kompensasi pergerakan). Seperti pada proses enkoding, sinyal prediksi dihasilkan dari intraframe yang ditambahkan dengan invers koefisien transformasi. Setelah deblocking filter, makroblok telah selesai didekodekan dan disimpan di memori untuk prediksi berikutnya. Teknik pengkodean ini cocok digunakan pada aplikasi seperti, video telepon, penyimpanan, broadcast dan streaming. 2.3
Pengkodean Citra Joint Photographic Experts Group (JPEG) Selama beberapa tahun terakhir, upaya standardisasi yang dikenal oleh JPEG
(Joint Photographic Experts Group), telah bekerja menuju pembentukan pertama citra internasional standar kompresi digital untuk peningkatan kualitas gambar, baik grayscale dan warna (Wallace, GK., 1991). JPEG adalah teknik kompresi grafis high color bit-mapped yang merupakan teknik dan standar universal untuk kompresi dan dekompresi citra tidak bergerak untuk digunakan pada kamera digital dan sistem pencitraan menggunakan komputer. Umumnya digunakan untuk kompresi citra berwarna maupun grayscale. Format file grafis ini telah diterima oleh Telecommunication Standardization Sector atau ITU-T dan Organisasi Internasional untuk Standardisasi atau ISO (Wikipedia, 2011). JPEG
12
kebanyakan digunakan untuk melakukan kompresi gambar diam menggunakan analisis Discrete Cosine Transform (DCT). JPEG juga dapat digunakan untuk koding video yang dinamakan dengan motion JPEG. Motion JPEG digunakan pada banyak aplikasi, terutama pada video koding untuk transmisi melalui jaringan paket UBR, seperti Internet. Pada motion JPEG setiap frame dikodekan secara independen. Meskipun kompresi gambar JPEG sangatlah efisien dan selalu menyimpan gambar dalam kategori warna true color (24 bit), format ini bersifat lossy, yang berarti bahwa kualitas gambar dikorbankan bila tingkat kompresi yang dipilih semakin tinggi. JPEG menggunakan Lossy Compression Scheme, berarti bahwa pada faktanya akan kehilangan beberapa data pada saat melakukan kompresi file. Dengan kata lain terjadi penurunan kualitas gambar pada saat membuka, mengubah, dan kemudian menyimpan gambar tersebut (Wikipedia, 2011). Format file ini mampu mengkompres objek dengan tingkat kualitas sesuai dengan pilihan yang disediakan. Format file sering dimanfaatkan untuk menyimpan gambar yang akan digunakan untuk keperluan halaman web, multimedia, dan publikasi elektronik lainnya. Format file ini mampu menyimpan gambar dengan mode warna RGB, CMYK, dan Grayscale. Format file ini juga mampu menyimpan alpha channel, namun karena orientasinya ke publikasi elektronik maka format ini berukuran relatif lebih kecil dibandingkan dengan format file lainnya. 2.4
Teorema Dasar Teknik Pengkodean Video Terdistribusi Teknik pengkodean video terdistribusi mengadopsi paradigma codec yang
berbeda berdasarkan struktur teori distributed source coding (DSC) dimana dalam hal teknik eksploitasi redundansi data video dilakukan hanya di dekoder, secara penuh atau sebagian. Pendekatan pengkodean video terdistribusi ini didasarkan pada dua teorema berdasarkan teori informasi, yaitu teorema Slepian-Wolf dan Wyner-Ziv. Konsep pengkodean video terdistribusi menyimpang dari paradigma pengkodean sumber secara konvensional dalam konteks proses pengkodean sumber yang berkorelasi. Pada pendekatan konvensional sumber yang berkorelasi secara statistik dapat dikodekan dan didekodekan kembali secara bersama-sama.
13
Sebaliknya pada DSC mengusulkan proses independen pengkodean sumber dari sumber yang secara statistik dependen namun dikodekan kembali secara bersamasama. 2.4.1 Teorema Slepian-Wolf Asumsi X dan Y adalah dua rangkaian acak diskrit bergantung secara statistik yang mana didistribusikan secara bebas dan sama. Menganggap rangkaian frame dienkode secara terpisah dengan nilai R X dan RY berturut-turut tetapi didekode secara bersama-sama dan dibuat korelasi antara keduanya diilustrasikan pada gambar 2.6. Slepian dan Wolf ditunjukkan pada analisis kemungkinan kombinasi nilai R X dan RY untuk direkonstruksi pada X dan Y dengan probabilitas kesalahan terkecil. X Enkoder 1 Rx
Statistically dependent
Dekoder Gabungan
Enkoder 2
X’Y’
Ry
Y Gambar 2.6 Sumber-Sumber Dependen Secara Statistik (Sumber : Brites, C., 2005)
Teorema Slepian-Wolf ditunjukkan pada: R X H X / Y ......................................................................................(2.1)
RY H Y / X ......................................................................................(2.2) R X RY H X , Y ..............................................................................(2.3)
Dimana H X / Y dan H Y / X adalah kondisi entropi dan H X , Y adalah entropi bersama pada X dan Y. Untuk menghitung nilai entropi digunakan persamaan (2.4).
14
n 1 bit / simbol ....................................................................(2.4) H i pij log 2 p i 1 ij
Yang terpenting dari teorema Slepian-Wolf adalah kurva rate yang mengindikasikan bahwa jika sumber adalah i.i.d (independently and identically distributed) dan saling bergantung secara statistik, penjumlahan dari dua rate sumber dapat mencapai entropi joint H(X,Y). Ini membuktikan bahwa dengan memisahkan enkoder untuk kedua sumber, maka pendekodean secara joint dapat dilakukan hanya di dekoder. Gambar 2.7 merupakan ilustrasi daerah pencapaian rate pada pengkodean video terdistribusi yang saling bergantung secara statistik dengan sumber X dan Y pada informasi yang didapat dari probabilitas error terkecil. RY [bits]
Joint Encoding and Decoding
H(Y)
H(YIX) RX + RY = H(X,Y) RX [bits] H(XIY)
H(X)
Gambar 2.7 Daerah Pencapaian Rate Slepian-Wolf (Sumber : Brites, C., 2005)
Dari teorema Slepian-Wolf di atas, sasaran utama Slepian-Wolf adalah melakukan pengkodean tanpa rugi salah satunya mengkaji korelasi spasial pada frame, karena korelasinya selalu berubah. Mengkaji korelasi spasial pada frame bertujuan
untuk
menghilangkan
redundansi
menggunakan proses transformasi dan kuantisasi.
spasial
pada
suatu
frame
15
2.4.2 Teorema Wyner-Ziv Teorema Wyner-Ziv berhubungan dengan Slepian-Wolf, biasa dikenal dengan “skenario kompresi secara lossy pada SI di dekoder”.
Rwz (d)
X Enkoder
Dekoder
Statistically dependent
X’
Y
Gambar 2.8 Kompresi Beban Dengan Side Information Dekoder (Sumber : Brites, C., 2005)
Konsep ini mengambil distorsi level d yang cocok secara terbatas antara sumber informasi X dan dekode output X’ yang sesuai. Maka dari itu disebut “lossy compression”. Asumsi sebuah informasi content Y yang berhubungan secara statistik pada X memungkinkan terjadi pada dekoder. Wyner dan Ziv mencoba untuk sebuah batas bawah bit rate disampaikan antara enkoder dengan istilah RWZ (d ) , agar mencapai distorsi d antara input dan output. Teorema Wyner-Ziv ditunjukkan pada:
R xwz| y (d ) R X / Y (d ) , d 0 .......................................................................(2.5) Dimana RWZ (d ) disebut dengan Wyner-Ziv minimum encoding rate (untuk X) dan R X / Y (d ) menunjukkan rate minimum terutama pada encode X saat Y memungkinkan secara simultan pada enkoder dan dekoder untuk rata-rata distorsi d yang sama. RWZ (d ) dan R X / Y (d ) disebut dengan fungsi Rate-Distortion (RD). 2.5
Codec Existing Wyner-Ziv Video Coding Paradigma baru dalam pengkodean video terdistribusi merupakan alternatif
untuk memperoleh hasil kinerja pembangkitan SI yang powerfull. Kualitas dari SI pada pengkodean video terdistribusi memiliki peranan penting pada keseluruhan kinerja RD. Tanpa mekanisme pembangkitan SI yang powerfull, maka tidak ada
16
kinerja RD yang layak yang dapat di capai oleh codec pengkodean video terdistribusi. Dilihat dari permasalahan tersebut membawa pengembangan paradigma baru pengkodean video, yaitu Wyner-Ziv Video Coding (WZVC) dimana SI pada pendekatan pengkodean video Wyner-Ziv diperoleh dengan mengeksploitasi korelasi diantara frame-frame yang telah didekodekan. Beberapa aplikasi yang menggunakan teknik pengkodean video Wyner-Ziv adalah aplikasi yang digunakan untuk sistem keamanan, komunikasi video mobile, sistem pengamatan bencana yang potensial untuk penggunaan secara komersial. Proses prediksi interframe pengkodean video Wyner-Ziv terjadi di dekoder. Dalam proses prediksi ini dekoder tidak memperoleh intraframe dari enkoder. Untuk mendapatkan informasi tersebut, maka dekoder harus menggunakan teknik pergerakan estimasi tertentu sehingga interframe yang diprediksi didekoder mendekati intraframe. Seperti pada gambar 2.9.
Slepian-Wolf Intraframe di Enkoder
Slepian-Wolf Interframe di Dekoder
Y
X
X’
Side Information Gambar 2.9 Model Teknik Pengkodean Video Wyner-Ziv (Sumber : Widyantara, O., 2011)
Karakteristik utama dari pengkodean terdistribusi adalah eksplorasi statistik sumber video dilakukan didekoder untuk membuang redundansi informasi.
Teknik-teknik
interpolasi
diterapkan
pada
frame-frame
yang
didekodekan sebelumnya, untuk memperoleh sebuah estimasi dari frame yang telah dienkodekan. Frame-frame hasil interpolasi ini digunakan sebagai SI untuk proses dekoding. Pemilihan terhadap sebuah teknik interpolasi frame yang digunakan untuk membangkitkan SI dapat mempengaruhi secara signifikan unjuk
17
kerja RD skema pengkodean Wyner-Ziv. SI yang lebih akurat yang dihasilkan oleh teknik interpolasi berarti akan terdapat lebih sedikit error (frame WZ sangat mirip dengan frame key) sehingga dekoder akan membutuhkan lebih sedikit bitbit parity dan bit rate dapat diturunkan pada kualitas yang sama. 2.5.1 Arsitektur Codec Pengkodean Video WZ Stanford Arsitektur Stanford utamanya dikarakteristikan oleh pengkodean SlepianWolf berbasis frame, menggunakan Turbo Codes dan kanal umpan balik untuk membentuk kontrol rate di dekoder. Arsitektur pengkodean video Wyner-Ziv Stanford, pertama kali diperkenalkan sekitar tahun 2002 oleh Stanford University, untuk domain piksel dan kemudian dilanjutkan ke domain transform. Pendekatan pada domain transform, koefisien-koefisien transform dikodekan WZ untuk ekploitasi redundansi spasial dan menurunkan kompleksitas, seperti ditunjukkan pada gambar 2.10. Decoded Wyner-Ziv frame
Wyner-Ziv frame
Enkoder Intraframe
W
Dekoder Intraframe
W’
DCT
Xk
IDCT
qk 2M level kuantizer
qk'
Bit-plane 1 Ekstrak bitplanes
: :
Enkoder Turbo
Dekoder Turbo
Buffer
Xk’ Rekonstruksi
Bit-plane Mk Band koefisien transform
Request bits
Side Information DCT
W^ Interpolasi/ ekstrapolasi Frame Key K
Dekoder Intraframe konvensinal
Enkoder Intraframe konvensinal
Decoded Frame Key K’
Gambar 2.10 Arsitektur Pengkodean Video WZ Stanford (Sumber : Aaron, A., 2004)
Guillemot, C., dkk (2007) menyatakan bahwa kinerja RD yang dihasilkan oleh codec di atas ternyata belum sampai pada level yang sama dengan
18
pengkodean prediksi seperti yang digunakan pada JPEG, H.264 dan lainnya. Maka, untuk pengkodean video terdistribusi harus memperhatikan keseimbangan kompleksitas pengkodean di enkoder dan dekoder. Di sisi Enkoder : 1.
Klasifikasi Frame Deretan video dibagi ke dalam frame WZ dan frame Key, masing-masing diidentifikasi sebagai frame X dan Y. Frame key dikodekan intra, dalam arti pengkodean dengan tanpa eksploitasi redudansi temporal yaitu tanpa membentuk prosedur estimasi gerak. Pengkodean ini dapat menggunakan standar H.263+ intra, H.264/AVC atau JPEG. Frame key secara periodik disisipkan untuk menentukan ukuran GOP (Group Of Picture).
2.
Transformasi Spatial Transformasi berbasis blok menggunakan DCT, diterapkan pada semua frame WZ. Koefisien DCT dari masing-masing frame WZ kemudian digrupkan besama-sama, sesuai dengan posisi koefisien DCT dalam sebuah blok, membentuk band-band koefisien DCT.
3.
Kuantisasi Setiap band DCT dikuantisasi seragam (uniform) dengan jumlah level bergantung pada kualitas target. Untuk sebuah band, bit-bit dari simbolsimbol yang terkuantisasi dikelompokan bersama-sama membentuk bitplane selanjutnya bit plane ini dikodekan dengan Turbo Code secara independen.
4.
Pengkodean Turbo Setiap band DCT dikodekan Turbo dimulai dengan Most Significant Bit plane (MSB). Informasi parity dibangkitkan untuk setiap bit-plane kemudian disimpan dalam buffer dan dikirimkan ke dekoder dalam bentuk paket disesuaikan dengan permintaan dekoder. Prosedur meminta bit parity menggunakan sebuah kanal feedback.
19
Di Sisi Dekoder: 1.
Pembuatan Side Information Dekoder membuat SI untuk setiap frame WZ dengan membentuk motioncompensation frame interpolation (atau extrapolation) menggunakan frameframe terdekode sebelumnya yang paling dekat. SI untuk setiap frame WZ diambil dari sebuah estimasi dari frame WZ asli. Kualitas estimasi yang baik, maka jumlah kesalahan yang harus diperbaiki oleh turbo dekoder menjadi lebih sedikit dan makin sedikit jumlah bit parity yang harus dikirimkan oleh enkoder.
2.
Pemodelan Noise Korelasi Statistik residu di antara koefisien-koefisin DCT yang saling berhubungan dalam frame WZ dan frame SI diasumsikan dapat dimodelkan sebagai distribusi Laplacian, yang mana parameter-parameternya telah diestimasi sebelumnya menggunakan phase pelatihan. Pendekatan ini sebenarnya tidak realistis karena mengasumsikan data asli tersedia di dekoder atau SI tersedia di enkoder.
3.
Pendekodean Turbo Ketika sebuah band koefisien-koefisien DCT, dimana koefisien-koefisien DCT side information dan statistik residu sudah diketahui, masing-masing bit plane kemudian di turbo dekoder (dimulai dari MSB). Turbo dekoder menerima sederetan potongan-potongan bit parity dari enkoder, sesuai dengan permintaannya melalui sebuah kanal feedback. Untuk memutuskan apakah diperlukan bit-bit parity tambahan atau tidak untuk keberhasilan sebuah proses pendekodean dari sebuah bit plane, dekoder menggunakan kriteria pemberhentian mekanisme request. Di awal, kriteria ini diasumsikan tersedianya frame asli di dekoder. Pendekatan ini tentunya masih tidak realistis. Setelah berhasilnya proses pendekodean Turbo MSB sebuah bit plane dari sebuah band DCT, dekoder Turbo di proses dengan cara analog dengan menjaga bit-planes yang tergabung dalam band yang sama. Jika
20
seluruh bit-planes dari sebuah band DCT telah berhasil di turbo decodec, maka turbo dekoder mulai mendekodekan band DCT berikutnya. 4.
Rekonstruksi Setelah pendekodean Turbo, seluruh bit-planes yang berhubungan dengan masing-masing band DCT digabungkan bersama-sama untuk membentuk deretan simbol terkuantisasi yang berhubungan dengan masing-masing band. Setelah seluruh simbol-simbol terkuantisasi ini di peroleh adalah mungkin untuk merekonstruksi seluruh koefisien DCT dengan bantuan koefisien SI.
5.
Inverse Transform Setelah seluruh band DCT direkonstruksi, sebuah inverse DCT (IDCT) di bentuk dan frame WZ dapat diperoleh.
6.
Penggabungan Frame Akhirnya, untuk memperoleh deretan video yang telah didekodekan, frame key terdekode dan frame WZ kemudian digabungkan.
2.5.2 Teknik Pengkodean Video Wyner-Ziv dengan Unsupervised Motion Vector Learning Berbasis Algoritma Expectation Maximization (EM) Metode pembangkitan SI dengan motion vector learning sepanjang proses dekoding menggunakan algoritma EM untuk sistem pengkodean video Wyner-Ziv telah diajukan (Varodayan,V., 2008). Metode berbasis learning menggunakan algoritma EM, melakukan disparitas kompensasi dan kompensasi bidang gerak berbasis blok, sehingga profil dari disparitas dan bidang gerak dibatasi oleh granuralitas ukuran blok k-by-k blok. Arsitektur EM berbasis unsupervised motion vector learning seperti pada gambar 2.11.
21
Gambar 2.11 Arsitektur EM-Based Unsupervised Motion Vektor Learning (Sumber : Widyantara, O., 2011)
Dengan mengasumsikan frame X (WZ) dan frame Y (key) adalah frameframe luminance dari video, dimana X
berkaitan dengan Y melalui sebuah
lapangan bidang gerak (M). Frame residu dari X ketika dilakukan kompensasi gerak dengan frame X, diberlakukan sebagai noise Laplacian Independen. Sebuah model a posteriori distribusi probabilitas dari sumber X didasarkan pada parameter , dapat dinyatakan dengan : Papp X PX ;
i, j, X i, j .......................................................(2.6) i, j
Dimana (I,j,w) = Papp{X(i,j) = w} adalah soft estimasi dari X(i,j) pada nilai luminance w {0,……,2d-1}. Dalam hal ini dekoder bermaksud untuk menghitung distribusi probabilitas dari bidang gerak, dengan tahap kedua hukum Bayes, yaitu :
PappM P M|Yˆ;S; PM P Yˆ;S|M; ...............................................(2.7) Dimana P{M|Y,S; } adalah probabilitas observasi medan gerak vektor M diperoleh ketika dan S, diketahui. Bentuk persamaan di atas mengekspresikan sebuah solusi iteratif algoritma EM. Algoritma ini melakukan proses iterasi dengan dua tahapan yaitu E-step dan
22
M-step. E-step memperbaharui distribusi medan vektor dengan referensi ke parameter-parameter
model
sumber,
sedangkan
M-step
memperbaharui
parameter-parameter sumber dengan referensi ke distribusi medan vektor.
E-step Algoritma E-step memperbaharui distribusi estimasi pada M dari
(t-1)
yang diperoleh
dari inisialisasi awal ditulis sebagai :
(t ) (t 1) M : Papp M P Yˆ , S | M ; (t 1) ................................................(2.8) Papp
Dimana persamaan diatas sangat mahal karena nilai M yang harus diproses terlalu besar. Penyerderhanaan dilakukan pada penelitian ini, yaitu pertama, mengabaikan sindrom S, karena ini dapat dieksploitasi di M-step dan kedua adalah estimasi medan vector M, dilakukan dengan vector gerak berbasis blok, Mu,v. Untuk ukuran blok yang sudah ditetapkan sebesar k, setiap blok k x k dari
(t-1) di bandingkan pada blok pada posisi yang sama di frame Y, kemudian dilakukan proses pencarian dalam range window yang tetap. Untuk blok u(t,v1) dengan piksel kiri atas dilokasikan di (u,v), distribusi pergeseran Mu,v diperbaharui seperti di bawah dan dinormalisasi :
(t ) (t 1) M P Yˆ(u,v)Mu,v | M u,v ; u(t,v1) ...............................(2.9) Papp M u,v : Papp
Dimana :
Yˆ(u ,v ) M u ,v
adalah blok k x k dari Y
((u,v)+Mu,v)
P Yˆ(u,v) M u,v | M u,v ; u(t,v1)
dengan piksel kiri atas di
adalah probabilitas observasi Y^
(u,v)+Mu,v
ketika
vektor Mu,v dari Xu,v diparameterkan oleh u(t,v1) diketahui. Persamaan tersebut ditunjukkan pada proses motion estimator pada gambar 2.12.
23
M-step Algoritma M-Step memperbaharui soft estimasi
dengan memaksimalkan
kemungkinan nilai Ŷ dan sindrom S.
(t ) M mP Yˆ, S | M m; .............(2.10) t : arg max P Yˆ , S ; arg max Papp
m
Dimana penjumlahannya adalah semua konfigurasi M dari bidang gerak. Jika nilai M-Step sudah maksimal pendekatan ini dilakukan dengan membuat soft SI ᴪ(t) diikuti dengan iterasi dari LDPC dekoding untuk menghasilkan
(t)
.
Blockwise pada bidang gerak terdistribusi Papp(t){Mu,v}, bobot pergerakan dari masing-masing blok Ŷ(u,v)+Mu,v, yang kemudian dijumlahkan menjadi soft SI u,v(t) seperti ditunjukkan pada probabilitas model gambar 2.12. Secara umum,
probabilitas yang dicampur SI memiliki nilai W pada piksel (i, j) adalah
P M mp Yˆ (i, j )
(t ) M mP X (i, j) | M m, Yˆ ……............................(2.11) (t ) i, j, Papp m
(t ) app
Z
m
m
Dimana pZ(z) adalah fungsi probabilitas massa dari noise additive independen
Z,
dan
Ŷm
adalah
kerangka
direkonstruksi
sebelumnya
dikompensasikan melalui konfigurasi gerak m.
k k Motion pmf Estimate motion pmf per block
Weights
m
Soft Matching
Ŷ
a.
Papp(Mu,v)
m
Motion Estimator
Mu,v
+ m
+ m
b.
Ŷ1
Probabilitas Model
Gambar 2.12 Algoritma EM Bidang Gerak Pada Codec WZVC (Sumber : Widyantara, O., 2011)
24
Seperti telah dipaparkan pada persamaan 2.11 metode unsupervised motion vector learning dengan algoritma EM, melakukan estimasi bidang gerak Papp(M) pada basis block-by-block. Iterasi pada penerapan estimasi bidang gerak berbasis blok pada algoritma EM, menyebabkan profil bidang gerak (M) dibatasi oleh granularitas blok. Proses kerja dekoder berhenti dengan baik jika estimasi Xˆ(i, j) = arg maxw θ(i, j,w) menghasilkan syndrome yang sama dengan S. Perbaikan profil bidang gerak dapat dilakukan dengan memperkirakan batas dari bidang gerak menggunakan teknik interpolasi dari basis blok ke piksel dan perbaikannya dilakukan pada setiap iterasi.
Gambar 2.13 Arsitektur Teknik Pengkodean Video Wyner-Ziv (Sumber : Widyantara, O., 2011)
Pada aplikasi pengkodean video terdistribusi, perbedaan karakteristik bidang gerak di antara deretan frame video memungkinkan disain codec WZVC menerapkan teknik interpolasi yang berbeda, dengan batasan pada kinerja RD dan kompleksitas dekoding. Maka pada tugas akhir ini mengadopsi metode interpolasi Tetangga Terdekat dan Supersampling untuk memperbaiki estimasi bidang gerak (M) dan membandingkan kinerjanya pada codec WZVC dengan sekuen video masukan yang berbeda. Kerangka kerja algoritma EM dengan perbaikan estimasi
25
bidang gerak, ditunjukan pada gambar 2.13, dimana prosedur interpolasi ditambahkan untuk memperbaiki estimasi bidang gerak yang dihasilkan oleh proses motion estimator berbasis blok. 2.6
Geometric Image Tranformation Dalam transformasi geometrik, grid dari piksel citra input tidak harus
dipetakan ke grid piksel dalam gambar output. Oleh karena itu, untuk menghitung intensitas piksel dalam citra output, fungsi transformasi geometrik diperlukan interpolasi nilai intensitas piksel beberapa masukan yang dipetakan ke lingkungan tertentu dari output piksel. Transformasi geometris dapat menggunakan berbagai algoritma interpolasi. Ketika memanggil fungsi transformasi geometrik Intel ® IPP (Integrated Performance Primitive), kode aplikasi menentukan modus interpolasi, yaitu jenis algoritma interpolasi dengan menggunakan interpolasi parameter. Intel ® IPP mengimplementasikan fungsi-fungsi pengolahan citra yang melakukan operasi geometrik mengubah pemutaran dan penskalaan gambar. 2.6.1 Rotate (Pemutaran) Rotasi merupakan transformasi geometri untuk memindahkan nilai piksel dari posisi awal (x1, y1), ke posisi akhir (x2, y2) dan ditentukan oleh rotasi sebesar θ terhadap koordinat titik pusat (m,n). Adapun persamaan proses rotasi adalah sebagai berikut : x2 cos( ) ( x1 m) sin( ) ( y1 n) m ...................................(2.12) y2 sin( ) ( x1 m) cos( ) ( y1 n) n
Dimana m, n adalah koordinat pusat rotasi pada gambar input dan Ѳ adalah sudut rotasi dengan rotasi searah jarum jam yang memiliki sudut positif. Rotasi menghasilkan output lokasi x2,y2 yang tidak sesuai dalam batas-batas dari gambar seperti yang didefinisikan oleh dimensi gambar input asli. Dalam kasus tersebut, tujuan unsur-unsur yang telah dipetakan di luar gambar diabaikan oleh banyak implementasi.
26
2.6.2 Scalling (Penskalaan) Penskalaan adalah operasi geometri transformasi spasial untuk memberikan efek memperbesar atau memperkecil ukuran citra input sesuai dengan variabel penskalaannya. Transformasi semacam ini dapat dilakukan untuk poligon dengan mengalikan masing-masing koordinat poligon oleh faktor skala. Sp dan Si yang pada gilirannya menghasilkan koordinat baru (x, y) sebagai (x1, y1). Adapun persamaannya adalah sebagai berikut : x1 S P x y1 S l y
……………………………………………………….. (2.13)
Dimana (x, y) adalah ukuran citra inputnya dan (x1, y1) ukuran citra output. (Sp, Si) merupakan variabel penskalaan dimana S adalah scaling matriks. Jika nilai-nilai faktor skala lebih besar dari 1 maka objek diperbesar dan jika kurang dari 1 objek diperkecil. Apabila nilai faktor skala sama dengan 1 maka tidak akan ada perubahan pada objek. Untuk setiap titik pada citra hasil, dengan koordinat x1 dan y1 diketahui, maka dapat dicari titik asalnya yaitu koordinat x dan y dengan transformasi balik. Titik asal dapat dicari dengan membagi titik hasil dan nilai faktor skala. Karena adanya operasi pembagian, seringkali diperoleh nilai koordinat titik asal yang tidak bulat. Untuk mengatasinya harus menggunakan salah satu interpolasi yang ada. Algoritma interpolasi yang digunakan berdasarkan transformasi pada Intel ® IPP dalam tugas akhir ini adalah interpolasi Nearest Neighbor dan Supersampling.
Interpolasi Nearest Neighbor (Tetangga Terdekat) Interpolasi Tetangga Terdekat adalah nilai keabuan titik hasil diambil dari
nilai keabuan pada titik asal yang paling dekat dengan koordinat hasil perhitungan transformasi spasial. Metode ini memperkirakan nilai tunggal untuk setiap variabel bidang gerak daerah perbatasan dan menyempurnakannya pada setiap
27
iterasi. Seluruh piksel pada blok k-by-k menggunakan model a posteriori probabilitas distribusi gerak Papp(t){Mu,v} tunggal.
Maka, model a posteriori
probabilitas distribusi gerak berbasis pixel-by-pixel, dinyatakan dengan persamaan sebagai berikut : i j …………........................(2.14) (t ) (t ) M i, j Papp Papp M u ,v k , k
Dimana M(i,j) adalah bidang gerak berbasis piksel dan M(u,v) adalah bidang gerak berbasis blok serta k adalah ukuran blok yang digunakan. Ketika terdapat korelasi yang erat antara blok-blok pada frame WZ sekarang dengan
blok-blok pada frame sebelumnya, maka interpolasi berbasis piksel
Tetangga Terdekat dapat secara efisien memanfaatkan nilai rata-rata piksel pada blok tersebut, untuk posisi piksel pada bidang gerak sekarang.
Interpolasi Supersampling Tujuan sebenarnya dari interpolasi Supersampling adalah memperkecil
resolusi citra. Parameter yang paling penting dalam algoritma ini adalah xfactor dan yfactor, yaitu suatu parameter yang menunjukan besarnya penurunan resolusi dari citra sumber yang dikehendaki. Algoritma Supersampling untuk memperkecil resolusi (sesuai dengan teori di dokumentasi Intel IPP) adalah sebagai berikut : 1. Bagi ROI persegi panjang (rectangular) citra sumber menjadi persegi-persegi panjang (rectangles) berukuran sama, dimana setiap kotak berhubungan dengan beberapa piksel dalam citra tujuan. Perhatikan bahwa setiap piksel sumber dinyatakan dengan kotak (square) 1 x 1. 2. Hitung jumlah bobot nilai-nilai piksel sumber untuk : a. Seluruh piksel yang terdapat dalam persegi panjang, b. Atau piksel yang memiliki irisan (interseksi tidak nol) dengan persegi panjang. Prosedur pembotannya adalah sebagai berikut :
28
a. Jika kotak piksel sumber (1x1 square), sepenuhnya berada dalam persegi panjang, maka nilai piksel tersebut diambil dengan bobot 1. b. Jika persegi panjang dan kotak piksel sumber (1x1 square) memiliki irisan (intersection) pada area a < 1, maka nilai piksel ditempat tersebut diambil dengan bobot a. 3. Untuk menghitung nilai piksel pada citra tujuan, bagi jumlah bobot (B) dengan ratio dari area persegi panjang sumber dan tujuan : Ssrc / Sdst = 1/(xfaktor*yfaktor) ………………………………………(2.15)
Dimana xfaktor dan yfaktor adalah parameter yang menentukan perubahan ROI citra sumber pada dimensi x dan y. 2.6
Perbandingan Tertinggi Sinyal Video Terhadap Gangguan (PSNR) Penilaian secara obyektif dilakukan dengan suatu simulasi terhadap
pengamatan dengan model matematis. Penilaian obyektif yang sering digunakan adalah perbandingan tertinggi sinyal video terhadap gangguan atau peak to peak signal to noise ratio (PSNR) yaitu pengukuran distorsi relatif suatu frame terhadap frame referensi. Pengukuran MSE untuk setiap frame video dari sekuen video merupakan komponen utama dalam perhitungan PSNR. Berikut ini adalah persamaan untuk MSE setiap frame video: MSE f
1 N
N 1
( X f (n) X f (n)) 2 ..........................................................(2.16) n 0
Dimana Xf adalah nilai piksel dari frame referensi dan X
f
adalah nilai
piksel dari frame terdistorsi. n adalah jumlah frame dari sekuen video. Setiap frame terdiri dari N piksel. Persamaan PSNR adalah sebagai berikut. PSNRf = 10 log10
(2 k 1) 2 ..…………....................................…........(2.17) MSE f
29
Dimana k adalah bit per piksel dari suatu frame. Nilai k adalah 8 yakni nilai untuk uji coba untuk sebuah frame video. Maka dari persamaan 2.17 dengan nilai k=8 diperoleh persamaan 2.18.
PSNRf = 10 log10
255 2 1 N
N 1
(x n 0
f
(n) X f (n))
..........................................(2.18) 2
Dimana sinyal puncak dari resolusi 8-bit per piksel adalah 255, dan noisenya adalah kuadrat antara perbedaan piksel-piksel (error) antara frame referensi dan frame yang sedang diproses. Secara umum, nilai PSNR yang tinggi mengindikasikan kualitas frame yang tinggi pula. Penurunan kualitas akibat proses pengkodean atau error pada proses transmisi mengakibatkan penurunan nilai PSNR (Winkler. S., 2004). Untuk mendapatkan perbandingan rata-rata dari kualitas dua deretan video dilakukan dengapn membandingkan PSNR dari setiap frame dalam setiap deretan, relative terhadap deretan video aslinya. Perhitungan rata-rata PSNR dari semua frame dalam deretan video menghasilkan pengukuran dalam dB dari kualitas deretan (Richardson, Iain., 1999). Untuk komponen luminance pada pengkodean video, nilai PSNR secara umum (Klaune, J., 2003) dapat dinyatakan sebagai berikut : Tabel 2.1 Kategori PSNR Untuk Komponen Luminance Kategori
Nilai PSNR
Sangat Baik Baik Cukup Kurang Sangat Kurang
> 37 dB 31 dB – 37 dB 25 dB – 31 dB 20 – 25 dB < 20 dB
