BAB 2 LANDASAN TEORI
Bab ini menguraikan beberapa landasan teori yang mencakup tentang video, kompresi, kompresi video, dan beberapa algoritma kompresi video.
2.1
Video Saat ini informasi menjadi sangat penting. Untuk menyampaikan suatu informasi tentu diperlukan suatu media, baik itu melalui media tulisan, media suara atau media citra/gambar. Dengan media tulisan, seseorang harus membaca terlebih dahulu baru dapat menerima informasi yang disampaikan. Dengan media suara, seseorang harus mendengarkan terlebih dahulu baru dapat menerima informasi yang disampaikan, dan tentunya media ini lebih baik dari media tulisan karena dapat menyampaikan informasi lebih banyak. Dengan media citra, seseorang cukup dengan melihat sebuah citra sebentar saja sudah dapat menerima informasi lebih banyak dari media tulisan dan media suara yang membutuhkan waktu lebih banyak hanya untuk menyampaikan sebuah informasi saja. Kini dengan perkembangan teknologi yang semakin pesat, penyampaian informasi pun semakin mengalami perkembangan. Dari media citra berkembang menjadi media video yang merupakan sekumpulan banyak citra. Dan terus berkembang sehingga video juga dapat menampung media suara yang berjalan bersamaan dengan banyak citra, karena itu video termasuk multimedia.
7
Sehingga dapat dikatakan video adalah suatu multimedia yang merupakan gabungan banyak citra dan media suara dapat diikutsertakan didalamnya, yang berjalan secara bersamaan sehingga menjadi sebuah video.
2.2
Kompresi Kompresi merupakan pengurangan ukuran suatu berkas menjadi ukuran yang lebih kecil dari aslinya. Pengompresian berkas ini sangat menguntungkan manakala terdapat suatu berkas yang berukuran besar dan data di dalamnya mengandung banyak pengulangan karakter. Adapun teknik dari kompresi ini adalah dengan mengganti karakter yang berulang-ulang tersebut dengan suatu pola tertentu sehingga berkas tersebut dapat meminimalisasi ukurannya. Misalnya terdapat kata: "Hari ini adalah hari Jum'at. Hari Jum'at adalah hari yang menyenangkan" Jika kita telaah lagi, kalimat tersebut memiliki pengulangan karakter seperti karaktek pembentuk kata hari, hari Jum'at, dan adalah. Dalam teknik sederhana kompresi pada perangkat lunak, kalimat di atas dapat diubah menjadi pola sebagai berikut: # ini $ %. % $ # ya@ menyena@kan Dimana dalam kalimat diatas, karakter pembentuk hari diubah menjadi karakter #, hari Jum'at menjadi %, adalah menjadi $, ng menjadi @. Proses ini dinamakan proses kompresi (compression). Saat berkas ini akan dibaca kembali, maka perangkat lunak akan mengembalikan karakter tersebut menjadi karakter
8
awal dalam kalimat. Proses pengembalian ke bentuk semula ini dinamakan decompression. Pengubangan karakter menjadi lebih singkat hanya digunakan agar penyimpanan kalimat tersebut dalam memory komputer tidak memakan tempat yang banyak. Proses compression dan decompression inilah yang dinamakan codec (compression/decompression). Implementasi kompresi dalam personal computer (PC) dibagi menjadi tiga cara, yaitu: a.
Pengkompresian berkas berdasarkan kegunaannya (Utility-based file compression) Merupakan jenis kompresi yang melakukan kompresi per berkas dengan menggunakan utilitas kompresi. Untuk melihat berkas yang telah dikompresi, berkas tersebut harus didekompres dengan menggunakan utilitas dekompresi. Dalam jenis ini, sistem operasi tidak tahu menahu mengenai aktivitas kompresian atau dekompresi sebuah berkas. Contoh dari sistem kompresi yang cukup terkenal adalah PKZIP, WinZip, WinRar, dan lain-lain.
b.
Pengkompresian berkas pada sistem operasi (Operating system file compression) Beberapa sistem operasi memiliki system kompresi di dalamnya. Contoh dari sistem operasi yang memiliki sistem kompresi di dalamnya adalah Windows NT yang menggunakan sistem berkas NTFS. Dengan menggunakan sistem kompresi seperti ini, sistem operasi secara otomatis dapat mendekompres berkas yang telah dikompresi manakala berkas tersebut ingin digunakan oleh sebuah program.
9
c.
Pengkompresian isi (Volume Compression) Dengan pengkompresian ini, kita dapat menghemat penggunaan space pada disk tanpa harus mengkompresi tiap berkas di dalamnya secara individual. Setiap berkas yang dikopi ke dalam volume compression akan dikompresi secara otomatis dan akan didekompresi secara otomatis apabila berkas tersebut dibutuhkan oleh sebuah program. Dalam kaitannya dengan mutltimedia, kompresi sangat menguntungkan karena dapat menghemat tempat penyimpanan serta dapat mempercepat proses pengiriman data kepada klien, sebab pengiriman berkas dengan ukuran yang lebih kecil lebih cepat daripada berkas yang memiliki ukuran besar. Kompresi juga penting manakala suatu data di-stream melalui sebuah jaringan.
2.2.1 Klasifikasi Teknik Kompresi Teknik kompresi diklasifikasikan menjadi dua, yaitu: a.
Algoritma lossy compression Keuntungan
dari
algoritma
ini
adalah
bahwa
rasio
kompresi
(perbandingan antara ukuran berkas yang telah dikompresi dengan berkas sebelum dikompresi) cukup tinggi. Namun algoritma ini dapat menyebabkan data pada suatu berkas yang dikompresi hilang ketika didekompresi. Hal ini dikarenakan cara kerja algoritma lossy adalah dengan mengeliminasikan beberapa data dari suatu berkas. Namun data yang dieliminasikan biasanya adalah data yang kurang diperhatikan atau diluar jangkauan manusia, sehingga pengeliminasian data tersebut
10
kemungkinan besar tidak akan mempengaruhi manusia yang berinteraksi dengan berkas tersebut. Contohnya pada pengkompresian berkas audio, kompresi lossy akan mengeleminasi data dari berkas audio yang memiliki frekuensi sangat tinggi/rendah yang berada diluar jangkauan manusia. Beberapa jenis data yang biasanya masih dapat mentoleransi algoritma lossy adalah gambar, audio, dan video. b.
Algoritma lossless compression Berbeda dengan algoritma kompresi lossy, pada algoritma kompresi lossless, tidak terdapat perubahan data ketika mendekompresi berkas yang telah dikompresi dengan kompresi lossless ini. Algoritma ini biasanya diimplementasikan pada kompresi berkas teks, seperti program komputer (berkas zip, rar, gzip, dan lain-lain).
2.3
Kompresi Video Mengingat video adalah gabungan dari banyak citra dan dapat terkandung media suara di dalamnya, tentunya ukuran filenya menjadi sangat besar. Hal ini membuat kebutuhan akan kapasitas media penyimpanan / storage semakin besar pula dan juga pemindahan data file video menjadi sangat sulit dilakukan. Walaupun dapat dilakukan, membutuhkan waktu yang tidak sedikit. Untuk mengatasi hal itu perlu adanya teknik pengurangan size file video dengan atau tanpa mengurangi atau menghilangkan sebagian informasi yang terkandung di dalam video tersebut yang dianggap tidak terlalu penting. Hal ini dikenal dengan sebutan kompresi video.
11
Data video menggunakan jumlah bit yang sangat tinggi. Untuk menyimpan data video, selain memerlukan kapasitas yang besar juga memerlukan bit rate yang tinggi untuk transmisi. Format QCIF yang umum pada videophone memerlukan 38.016 byte per frame. Bila frame rate sebesar 30 frame/s, maka bit ratenya sekitar 9 Mbps. Sedangkan HDTV memiliki ukuran frame sebesar 1920x1080 memilikii bit rate sebesar 160 Mbps. Pada dasarnya untuk mengatasi keperluan akan beban bit yang tinggi ini ada dua cara. Pertama, dengan melebarkan jalan raya informasi, dimana dibangun suatu jaringan yang memiliki bit rate tinggi. Kedua, dengan melakukan kompresi data, dimana data yang akan disimpan atau ditransmisikan dikompres dengan metode tertentu, sehingga membutuhkan jumlah bit yang lebih sedikit. Untuk melakukan kompresi pada data video secara efektif, perlu memanfaatkan sifat-sifat yang ada pada video digital. Dalam data video, terdapat redundansi yang mendukung kompresi, yaitu redundansi spasial dan redundansi temporal. Kompresi video dapat dilakukan dengan melakukan pengurangan kualitas video seperti mengurangi bit rate atau jumlah frame tiap detik, tetapi dengan konsekuensi kualitas video yang kurang baik dibandingkan kualitas video sebelumnya. Teknik kompresi seperti ini termasuk lossy compression karena kualitas video hasil kompresi menjadi kurang baik. Namun kompresi citra atau video bisa saja lossless dimana tidak ada informasi yang hilang pada saat proses kompresi. Citra atau video yang dihasilkan oleh proses decompress sangat identik setiap bitnya dengan citra atau video yang sebelum dikompres.
12
Tujuan kompresi video adalah menggunakan sebanyak mungkin data dari frame lainya, hanya menyimpan atau mentransmisikan perubahan antara sekuensi gambar. Sekuensi video terdiri dari banyak pengurangan yang sementara dikarenakan daerah di dalam gambar diulang per frame. Codecs yang ada pada saat ini (seperti mpeg) terdiri dari tipe-tipe data frame yang berbeda, yakni: intra-frame dan predicted frame. Sebuah intra frame adalah gambar secara keseluruhan yang dikompres dengan cara tertentu dan dapat direkonstruksi ulang tanpa ketergantungan dengan frame lainnya. Predicted frame terdiri dari informasi mengenai perbedaan antara frame sebelumnya dan frame yang sekarang, konstruksi frame selesai memerlukan frame sebelumnya, yang mana dapat dikonstruksi dari predicted frame yang terjadi sebelumnya, gambar dibawah akan menjelaskannya.
Gambar 2.1 Pengaturan intra-frame dan predicted frame dalam video.
2.3.1
Kompresi Intraframe Redundansi spasial adalah redundansi yang terdapat dalam suatu frame. Hal ini disebabkan karena adanya korelasi antara sebuah pixel dengan pixel disekitarnya. Redundansi ini dimanfaatkan untuk melakukan kompresi
13
intraframe. Kompresi intraframe dapat dilakukan dengan beberapa metode. Metode pertama adalah sub sampling, dimana jumlah pixel yang diperlukan untuk merepresentasikan suatu image dikurangi. Metode kedua adalah coarse quantization yang disebut juga bit depth reduction. Metode ini dilakukan dengan mengurangi jumlah bit yang digunakan untuk merepresentasikan suatu pixel. Metode
selanjutnya
adalah
transform
coding,
yang
digunakan
untuk
mentransformasikan data dari suatu domain ke domain lainnya. Cara ini menghasilkan data yang lebih mudah diproses untuk kompresi lebih lanjut. Transformasi yang populer digunakan adalah discrete cosine transform (DCT).
2.3.2
Kompresi Interframe Redundasi temporal adalah redundansi yang terdapat diantara sebuah frame dengan frame sebelum atau sesudahnya. Hal ini disebabkan adanya pixelpixel yang berkorelasi di antara frame-frame tersebut. Redundani ini terutama dikarenakan banyak bagian frame yang tidak berubah dibanding frame sebelum dan sesudahnya. Redundansi ini dimanfaatkan untuk melakukan kompresi interframe. Kompresi interframe dapat dilakukan dengan beberapa metode. Metode pertama adalah sub-sampling yang dilakukan dengan mengurangi jumlah frame dalam data video. Pengurangan itu dilakukan dengan hanya menyimpan atau mentransmisikan frame tertentu, misalnya tiap dua frame. Metode kedua adalah difference coding. Pada metode ini, suatu frame dibandingkan dengan frame sebelumnya, dan hanya pixel-pixel yang berubah saja yang disimpan atau ditransmisikan. Metode ini dikembangan pada metode block based difference
14
coding. Pada metode ini, frame dibagi menjadi blok-blok yang tidak overlap. Tiap blok tersebut dibandingkan dengan block yang bersesuaian pada frame sebelumnya. Hanya blok yang mengalami perubahan signifikan saja yang disimpan. Dibandingkan metode kedua, overhead pada metode ini lebih kecil, karena digunakan hanya untuk tiap blok bukan tiap pixel. Metode kompresi interframe yang umum digunakan adalah block based motion compensation. Pada metode ini, frame juga dibagi menjadi blok-blok yang tidak overlap. Disini dilakukan proses pencocokan blok atau block matching. Tiap blok pada frame tersebut dibandingkan dengan blok-blok berukuran sama pada frame sebelumnya, hingga ditemukan blok yang paling mirip. Perbedaan lokasi antara blok tersebut dengan blok yang mirip pada frame sebelumnya disebut vektor gerak atau motion vector. Metode ini efektif karena hanya vektor gerak saja yang disimpan atau ditransmisikan.
2.4
Algoritma Kompresi Video Beberapa algoritma kompresi video telah disebutkan pada sub-bab sebelumnya. Pada sub-bab ini akan menjelaskan lebih jauh lagi tentang algoritma-algoritma kompresi video tersebut dan bagaimana masing-masing kelebihan dan kekurangannya.
2.4.1
Discrete Cosine Transform (DCT) DCT merupakan algoritma kompresi video yang paling populer dalam dunia kompresi karena algoritma kompresi ini paling banyak digunakan. Video
15
yang telah dikompresi dengan algoritma kompresi DCT juga paling mudah ditemukan di berbagai media, terutama di dunia internet. Prinsip dasar yang dilakukan DCT adalah mentransformasikan data dari domain ruang ke domain frekuensi. Pada domain frekuensi, terdapat frekuensi DC yang merupakan frekuensi inti dari suatu blok yang ditransformasikan dan frekuensi-frekuensi non-DC yang tidak akan mengubah blok secara signifikan bila terjadi distorsi padanya. Mata manusia kurang peka untuk mendeteksi distorsi yang terjadi dengan frekuensi- frekuensi tinggi non-DC ini. Sifat inilah yang dimanfaatkan untuk kompresi, dengan memotong frekuensi-frekuensi tinggi tersebut pada proses kuantisasi. Koefisien DCT yang terkuantisasi kemudian akan di-encode secara runlength sebagai kode-kode variable length yang mengindikasi sejumlah koefisien zero yang diikuti oleh sebuah koefisien non-zero. Contohnya sebuah kode runlength mengindikasi 4 buah koefisien zero yang diikuti oleh sebuah koefisien non-zero dari level 2. Kode variable length yang pendek (contoh: 0110) digunakan untuk kombinasi biasa dari jalannya zero dan level-level koefisien non-zero. Kode variable length yang lebih panjang (contoh: 0000001101) digunakan untuk kombinasi yang sama tetapi untuk kombinasi yang lebih jarang atau tidak biasa. Dengan cara ini, kompresi substansial dari sebuah citra menjadi mungkin. Discrete Cosine Transform itu sendiri paling baik dijelaskan sebagai sebuah satu dimensi (DCT 1D). DCT 2D equivalent untuk memperagakan sebuah DCT 1D dalam setiap baris dari sebuah blok pixel yang diikuti oleh sebuah DCT
16
1D dalam setiap kolom dari blok pixel yang dihasilkan oleh DCT 1D dalam baris-baris. Discrete Cosine Transform satu dimensi dapat diterapkan pada sebuah blok dari sampel N (pixel dalam sebuah citra atau tekanan suara dalam sebuah file audio). Discrete Cosine Transform adalah sebuah matriks N x N dimana barisnya dimisalkan dengan fungsi berikut:
DCT(m,n) = sqrt( (1-delta(m,1)) / N ) * cos( (pi/N) * (n-1/2) * (m-1) ) dimana DCT(m,n) adalah matriks DCT 1D m,n
=
1, …, N
pi
=
3,14159267…
N
=
jumlah sample dalam blok
delta(m,1)
=
1 jika m adalah 1 0 jika selain itu
cos(x)
=
cosine dari x (radian)
*
=
kali
Video codec yang menggunakan algoritma DCT adalah Motion JPEG, Editable MPEG, MPEG-1, MPEG-2, MPEG-4, H. 261, H. 263, dan H. 263+. Adapun kekurangan dan kelemahan yang dimiliki DCT adalah pada kompresi tinggi dapat memblok artifact, pinggiran yang kasar terkadang akan menjadi buram/blur, memerlukan perhitungan yang terperinci sehingga bisa menjadi lambat, namun masih mungkin dilakukan secara real time.
17
2.4.2
Vector Quantization (VQ) Video codec yang menggunakan algoritma kompresi Vector Quantization adalah Indeo 3.2 dan Cinepak. Seperti sebagian besar video digital, Indeo dan Cinepak bekerja dalam dunia warna YUV, bukan RGB misalnya. Ide dasar dari Vector Quantization pada kompresi citra adalah membagi citra tersebut menjadi empat blok (4x4 pixel dalam YUV untuk Indeo dan Cinepak). Biasanya beberapa blok (diharapkan banyak) adalah sama dengan blok-blok lainnya walaupun biasanya tidak identik. Encoder mengidentifikasi sebuah kelas dari blok-blok yang sama dan menggantinya dengan blok-blok ‘generic’ dari kelas blok-blok yang sama. Encoder meng-encode lookup table yang memetakan kode biner pendek menjadi blok-blok ‘generic’. Biasanya kode biner terpendek mewakili kelas-kelas blok yang paling banyak dalam sebuah citra. Decoder dari Vector Quantization menggunakan lookup table untuk merakit atau membentuk kembali sebuah ‘perkiraan citra’ yang terdiri dari blokblok ‘generic’ dalam lookup table. Perlu diperhatikan bahwa secara inheriten hal ini adalah proses lossy compression karena blok-blok yang asli atau sebenarnya diganti dengan blok ‘generic’ yang merupakan perkiraan yang ‘cukup baik’ terhadap blok asli. Proses encoding cenderung lambat dan memerlukan perhitungan yang intensif karena encoder harus mengakumulasi statistik dalam frekuensi blok-blok dan mengkalkulasi persamaan blok dengan bertujuan untuk membangun lookup table. Sedangkan proses decoding begitu cepat karena proses tersebut berdasarkan lookup table. Dalam Vector Quantization, lookup table dapat
18
dikatakan sebagai sebuah codebook. Kode biner yang menunjuk/mengarah ke dalam tabel dapat dikatakan sebagai kata-kata kunci (codewords).
Gambar 2.2 Algoritma Vector Quantization Kompresi yang lebih tinggi dicapai dengan membuat lookup table lebih kecil, jumlah kelas-kelas blok yang sama dalam citra lebih sedikit. Kualitas saat setelah proses decompress menjadi lebih rendah seperti halnya lookup table yang semakin diperkecil. Vector Quantization cenderung memblok artifact jika kompresi semakin ditingkatkan. Sebagai contoh, perhatikan blok pixel 4 x 4 berikut. Setiap pixel memiliki jangkauan nilai diantara 0 – 255. Agar mudah dimengerti berikut ini merupakan citra grayscale. (Block 1) 128 128 128 128
(Block 2) 128 127 128 128
(Block 3) 128 127 126 128
128 128 128 128
128 128 128 128
128 128 128 128
128 128 128 128
128 128 127 128
127 128 128 128
128 128 128 128
128 128 128 128
128 128 128 128
19
Biasanya blok-blok tersebut akan terlihat sama bagi pandangan manusia. Blok ke-dua dan ke-tiga dapat ditukar secara aman dengan blok pertama. Hal ini tdak mengkompres citra. Namun blok perpindahan (Block 1) dapat direpresentasikan dengan sebuah index pendek ke dalam sebuah lookup table 4x4. Lookup Table[1] = 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128
Citra asli dapat diconvert ke dalam sebuah lookup table begitupun urutan index, menjadikannya kompresi yang substansial. Dalam video, lookup table yang sama dapat di digunakan untuk banyak frame, bukan hanya satu frame. Kekurangan dan kelemahan algoritma kompresi Vector Quantization adalah proses decodingnya sangat cepat, memerlukan perhitungan terperinci dan masih belum dapat dilakukan secara real time kecuali pada hardware yang dirancang khusus untuk hal itu, pada kompresi tinggi dapat memblok artifact, dan pada umumnya Discrete Cosine Transform dan Discrete Wavelet Transform dapat mencapai kompresi yang lebih tinggi dibandingkan dengan Vector Quantization.
2.4.3
Fractal Compression Kompresi Fractal ini akan dijelaskan tentang pengertian Fractal dan teknik-teknik dalam fractal.
20
2.4.3.1 Pengertian Fractal Teori pola tak terbatas sebelumnya sudah ada sejak Koch dan Julia melakukan penelitian mereka jauh sebelumnya, namun istilah fractal baru diperkenalkan tahun 1975 oleh Benoit B. Mandelbrot ketika pola fractal yang menarik rasa ingin tahunya dengan tulisan yang berjudul A Theory of Fractal Sets, yang kemudian menjadi buku The Fractal Geometry of Nature pada tahun 1982. (Oliver, 1992, p3, p61, Doerksen dan Lavrosky, 1997).
Gambar 2.3 Himpunan Mandelbrot Awalnya ia melihat pantai Inggris untuk awal studinya mengenai matematika fractal. Ia melihat keseluruhan pantai, mengukurnya dengan beberapa derajat ketelitian. Bagaimanapun yang ia lihat mendekati, ia melihat setiap selat lebih jauh lagi selat dan semenanjung dan didalam tiapnya, pola kontinyu. Karena itu panjang garis pantai terlihat tak terbatas. Garis pantai adalah sebuah kurva fractal, objek satu dimensi, dialokasikan dalam bidang dua dimensi dapat dianggap berada diantara dimensi satu dan dimensi dua. (Doerksen dan Lavrosky, 1997). Kata fractal berasal dari kata sifat dalam bahasa Latin “fractus”, yang berarti permukaan tak beraturan yang menyerupai sebuah pecahan batu. Asal dari kata kerja bahasa Latin “frangere” yang berarti “dipecah” untuk menghasilkan fragmen yang tak beraturan. (Oliver, 1992, p61). “Geometri Fractal memainkan
21
dua peran. Geometri yang menentukan chaos dan dapat juga menggambarkan gunung, awan dan galaksi” - Benoit B. Mandelbrot, 1982. (Oliver, 1992,p61).
2.4.3.2 Single Frame Proses kompresi yang dilakukan serupa dengan pencocokan “inter” frame blocking dalam standar MPEG. Yang mana bergantung pada gambar lainnya, bagian tertentu gambar yang seperti bagian yang lain, jadi informasi bagian ini hanya perlu disimpan satu kali saja. Pengkompresan frame terdiri dari: a.
Kompresi block fractal dari frame yang sekarang atau frame yang sebelumnya.
b.
Membawa block, local, global atau static ke depan. Pada umumnya mengunakan pola segmentasi quadtree.
Gambar 2.4 Pola Segmentasi Quadtree
2.4.3.3 Three Dimension Blocking Penggunaan 3-D blok memiliki potensi rata-rata kompresi yang tinggi dari intraframe coding sejak angka koefisien dibutuhkan untuk encode tiap range
22
blok yang dipilih menjadi sangat kecil dari pixel-pixel dari luar frame dimasukkan dalam range blok. Agar mudah angka dimungkinkan dalam operasi 3-D, kita menggunakan philosophy keterangan operasi spatial dan temporal. Dengan kata lain operasi dalam domain dan range blok pertama digunakan untuk pixel-pixel tiap frame kemudian dalam frame itu sendiri. Satu prinsip coding yang berbeda antara 2-D dan 3-D Fractal Block Coding adalah bahwa sinyal 2-D (gambar) dengan batasan alami dalam semua dimensi dimana sinyal video dengan batasan alami hanya 2 dimensi(spatial) dan menjadi
diperhatikan
untuk tujuan praktis ketidakterbatasan dalam 3
dimensi(temporal).Ini adalah penting bahwa beberapa skema video block coding berisi metode partisi temporal.
2.4.4
Discrete Wavelet Transform (DWT) Video codec yang menggunakan DWT adalah VDOWave dari VDONet, VxTreme, dan Intel Indeo 5.x. Fractal dan wavelet merupakan teknologi yang lebih baru dibandingkan tiga algoritma lain yang telah dibahas pada sub bab sebelumnya. Discrete Wavelet Transform terdiri dari lewatnya sebuah sinyal, seperti citra, yang melalui sepasang pass filter, pass filter rendah dan pass filter tinggi. Pass filter rendah menghasilkan sinyal versi resolusi rendah. Sedangkan pass filter tinggi menghasilkan sebuah detail yang ditambahkan atau sinyal yang berbeda. Output dari dua filter tersebut kemudian mengalami dua proses downsample. Output dari downsample tersebut memiliki jumlah bit yang sama
23
yang kemudian menjadi sinyal input. Parameter dari dua filter tersebut dipilih sehingga nantinya output proses upsample dari pass filter rendah ditambahkan ke output proses upsample dari pass filter tinggi, hingga akhirnya sinyal original dapat dibentuk kembali. Kekurangan dan kelebihan Discrete Wavelet Transform adalah kualitas subjektif dari video dan citra yang dikompresi dengan DWT dapat menghasilkan lebih baik dibandingkan metode DCT untuk rasio kompresi yang sama, dan pada pinggiran yang tajam dapat menjadi buram jika kompresi semakin ditingkatkan.
2.4.5
Algoritma Kompresi Video Lainnya Pada sub bab ini akan dijelaskan mengenai beberapa algoritma kompresi lainnya yang benar-benar ada namun tidak sangat dikenal dan cukup jarang digunakan secara murni, namun biasanya menjadi dasar dari algoritma kompresi video yang telah disebutkan sebelumnya.
2.4.5.1 Run Length Encoding Video codec yang menggunakan Run Length Encoding adalah Microsoft RLE (MRLE). Algoritma ini telah dikembangkan sejak tahun 1950-an dan semenjak itu dijadikan sebagai pendekatan yang standar untuk pengkompresian faxes. Run Length Encoding juga digunakan untuk meng-encode koefisien DCT dalam standarisasi internasional Discrete Cosine Transform (DCT) untuk MPEG, H.261, H.263, dan JPEG.
24
RLE mengencode urutan pixel yang memiliki warna yang sama (seperti misalnya hitam dan putih) sebagai sebuah codeword. Sebagai contoh terdapat urutan pixel 77 77 77 77 77 77 77
dapat dicode menjadi 7 77 (ada tujuh buah untuk 77)
Run Length Encoding dapat bekerja dengan baik untuk citra bi-level (contohnya gambar atau teks hitam putih) dan untuk citra 8 bit, yang biasanya terdiri dari urutan warna-warna yang sama. Namun tidak baik untuk citra natural beresolusi tinggi seperti misalnya citra 24 bit, karena urutan warna yang sama tidak sering muncul seperti pada citra 8 bit. Tipe kompresi yang satu ini akan menghadapi banyak bahaya terhadaap data yang jumlahnya besar, jadi biasanya ada sejenis metode - metode prefiltering yang bekerja untuk memastikan data dapat dikompresi.
2.4.5.2 Contour-Based Image Coding Contour adalah sebuah garis yang merepresentasikan sebuah texture atau bentuk, bagian penting, dan jumlah. Sebuah texture merupakan sebuah representasi
struktur
permukaan.
Contour-Based
Image
Coding
merepresentasikan citra sebagai contour yang memantul pada bagian yang memiliki texture. Sebagai contoh, saat countour dan texture diextract dari sebuah citra, contour tersebut dapat diencode sebagai poin kontrol spline – fungsi polinomial
25
yang digunakan untuk merepresentasikan kurva – yang cocok terhadap contour tersebut. Sedangkan texture dapat diencode sebagai koefisien transformasi dari transformasi frekuensi spasial seperti Discrete Cosine Transform atau varianvarian Discrete Wavelet Transform. Kompresi dapat dicapai melalui coding skalar atau vector quantization parameter kontrol dari spline dan koefisien transformasi yang digunakan untuk texture tersebut. Video codec yang menggunakan Contour-Based Image Coding adalah Surface Fitting Method (SFM) dari Crystal Net.
2.4.5.3 Frame Differencing Frame Differencing memanfaat kenyataan bahwa terdapat perbedaan kecil dari frame ke frame di banyak video atau urutan animasi. Sebagai contoh, di sebuah video menayangkan sebuah bola yang terbang di udara di depan sebuah background atau latar belakang yang diam. Kebanyakan dari citra dan latar belakang tidak berubah dari frame ke frame dalam satu adegan. Video codec yang menggunakan Frame Differencing adalah Cinepak. Namun
Cinepak
biasanya
menggunakan
Frame
Differencing
yang
dikombinasikan dengan Vector Quantization, karena itu Cinepak juga termasuk video codec yang menggunakan algoritma kompresi video Vector Quantization.
2.4.5.4 Motion Compensation Code motion compensation digunakan untuk motion/pergerakan sebuah adegan seperti sebuah bola yang bergerak melewati sebuah background. Standar video international Discrete Cosine Transform (DCT) untuk MPEG-1, MPEG-2,
26
MPEG-4, H.261, dan H.263 menggunakan motion compensation. Motion Compensation mengarah pada sejumlah ide dan algoritma.Metode motion compensation yang digunakan dalam MPEG, H.261 dan H.263 hanya digunakan untuk menterjemahkan sebuah motion. Hal ini cocok untuk objek yang bergerak melewati background. Namun tidak bekerja dengan baik untuk objek yang berputar, perubahan ukuran objek, dan zoom/perbesaran kamera. Motion Compensation membagi citra menjadi blok-blok (16x16 pada MPEG-1). Kompresi dicapai dengan menyimpan hanya vector pergerakan saja (dan sebuah kemungkinan error kecil) bukan nilai pixel untuk seluruh blok. Proses encoding dinamakan Motion Estimation. Proses ini mencari vector pergerakan untuk setiap blok. Sedangkan proses decoding dinamakan Motion Compensation. Motion Compensation mampu mencapai kompresi yang lebih tinggi dibandingkan Frame Differencing sederhana. Kekurangan Motion Compensation adalah pada saat proses encoding (yang mana dikenal dengan Motion Estimation) membutuhkan perhitungan yang terperinci. MPEG-1 dengan frame IP dan B tidak dapat diencode secara real time tanpa hardware yang mendukung. Video codec yang menggunakan Motion Compensation adalah MPEG-1, MPEG-2, MPEG-4, H.261, H.263, H.263+, VxTreme, VDOWave dari VDONet, ClearVideo (RealVideo) Fractal Video Codec dari Iterated Systems.
2.5
Blockmathcing Algoritma Blockmatching adalah sebuah teknik standar untuk encoding gerak dalam video sequence. Bertujuan untuk mendeteksi gerakan sebuah objek
27
antara dua gambar dalam sebuah block-wise sense. Bloknya biasanya dibedakan atau didefinisikan dengan pembagian gambar frame kedalam kotak bagian nonoverlapping. Setiap blok dari current frame dicocokan kedalam sebuah blok tujuan frame dengan shifting pada current block melalui sebuah predefined ketetanggaan pixel dalam frame tujuan. Setiap shift, penjumlahan jarak antara nilai abu-abu (gray) dari dua blok yang dikomputasi. Shift yang mana memberikan jarak total terkecil dipertimbangkan pencocokan yang terbaik. Pada kasus yang umum, pencocokan dua blok mempunyai jumlah pixel yang sama. Ini jarang kali benar karena gerak objek berubah bentuknya dalam pandangan pengamat, pencahayaan dari permukaan objek juga berubah, dan pada akhirnya dalam dunia nyata selalu terdapat noise. Lebih lanjutnya, dari pandangan nilai semantic, dalam scene terdapat gerakan occlusions antar objek, sama baiknya dengan penghilangan objek dan pemunculan objek yang baru. Meskipun masalah-masalah pixel oleh pixel yang serupa, ini cepat untuk komputasi dan digunakan secara luas untuk pencarian pencocokan wilayah. Beberapa yang paling sering kriteria pencocokan yang digunakan berdasarkan pixel. Beberapa permasalahan yang tidak dapat diatasi dengan algoritma dasar block matching adalah aperture problem, global atau lokal perubahan dalam pencahayaan, dan gerakan kamera.
