[TTG4J3] KODING DAN KOMPRESI
Oleh : Ledya Novamizanti Astri Novianty Prodi S1 Teknik Telekomunikasi Fakultas Teknik Elektro Universitas Telkom
RLE adalah teknik sederhana untuk mengkompresi data digital
Teknik untuk mengurangi ukuran data yang mengandung simbol berulang
Simbol yang berulang diistilahkan run
Digunakan untuk kompresi : 1. Teks 2. Image Black and White (BW) [TTG4J3] Koding dan Kompresi
RLE & BW Transform
2
Simbol yang berulang, disebut run
1 run biasanya di‐encode ke dalam 2‐byte data
Byte pertama merepresentasikan jumlah simbol, disebut run count
Byte kedua merepresentasikan simbol yang berulang, disebut run value
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
3
Sebuah string AAAAAAAAAAAAAAA, direpresentasikan dalam 15 byte data
Dengan RLE, di‐encode menjadi 2 bytes data: 15A (ingat 1 buah paket RLE Æ 2 bytes) Byte pertama: 15, run count Byte kedua: A, run value [TTG4J3] Koding dan Kompresi
RLE & BW Transform
4
Sebuah string AAAAAAbbbXXXXXt direpresentasikan dalam 15 bytes data
Dengan RLE, di‐encode menjadi : 6A3b5X1t 4 paket RLE, 8 bytes
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
5
Perhatikan string berikut : Xtmprsqzntwlfb
Tanpa kompresi : 14 bytes data.
Dengan RLE, di‐encode menjadi: 1X1t1m1p1r1s1q1z1n1t1w1l1f1b 14 paket RLE, 28 bytes! [TTG4J3] Koding dan Kompresi
RLE & BW Transform
6
RLE pada teks cocok untuk mengkompresi data teks yang mengandung banyak pengulangan simbol
Jika semua nilai (value) dalam data asli persis sama, RLE dapat mengurangi data menjadi hanya dua nilai.
Jika tidak ada nilai (value) yang berulang dalam data, RLE menjadi dua kali lipat jumlahnya dibandingkan dengan data asli. [TTG4J3] Koding dan Kompresi
RLE & BW Transform
7
Encode menggunakan teknik RLE pada string BBDAAADDDRAAB
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
8
Diimplementasikan pada transmisi data melalui fax Pada image BW :
Hitam direpresentasikan oleh bit ‘1’ Putih direpresentasikan oleh bit ‘0’
Beberapa variasi RLE untuk image BW : Standard CCITT No. 2 dan 4 JR (Japanesse Recommendation) Standard
CCITT Group 3 [TTG4J3] Koding dan Kompresi
RLE & BW Transform
9
Hasil encoding berupa rangkaian nilai integer yang menunjukkan banyaknya pixel berwarna putih (bit ‘0’) dan hitam (bit ‘1’) secara bergantian
Warna pertama yang dinyatakan di dalam encoding adalah warna putih putih – hitam – putih – hitam – … [TTG4J3] Koding dan Kompresi
RLE & BW Transform
10
Misalkan terdapat rangkaian bit pixel sebagai berikut: 00000111100000000111111000
Hasil encode: 5, 4, 8, 6, 3 11111000001100000011111100
Hasil encode: 0, 6, 5, 2, 5, 6, 2
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
11
Karena image yang dikompresi adalah image BW, maka hanya ada 2 transisi warna yang mungkin di dalam image yaitu: Transisi White‐Black (W/B) Transisi Black‐White (B/W)
Yang disimpan sebagai hasil encoding adalah posisi pixel yang merupakan posisi transisi W/B dan B/W
Diasumsikan terdapat pixel putih imajiner di sebelah kiri pixel aktual [TTG4J3] Koding dan Kompresi
RLE & BW Transform
12
Perhatikan ilustrasi berikut: •
• •
• •
• •
• •
•
•
•
•
•
•
• •
•
•
Pixel transisi ditandai oleh dot, baik transisi W/B atau pun B/W
Karena diasumsikan terdapat pixel putih imajiner di sebelah kiri pixel aktual, maka transisi pertama pasti merupakan transisi W/B [TTG4J3] Koding dan Kompresi
RLE & BW Transform
13
Diketahui citra BW 5 x 5 sebagai berikut : 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Tentukan hasil RLE menurut JR CCITT G.3 Jawaban : 3, 5, 6, 9, 12, 14, 15, 16, 18, 24,26 Ket : integer terakhir menunjukkan batas (pixel imajiner) [TTG4J3] Koding dan Kompresi
RLE & BW Transform
14
Tentukan hasil RLE menurut CCITT 2/4 dan JR CCITT G.3 untuk gambar berikut ini :
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
15
Metode ini dikembangkan oleh Michael Burrows dan David Wheeler pada tahun 1994, saat bekerja di DEC Systems Research Center di Palo Alto, California. Karakteristik Algoritma BW Transform :
Seluruh urutan yang akan dikodekan harus tersedia pada
encoder sebelum coding dimulai. Prosedur decoding tidak segera terlihat jelas walaupun prosedur encoding‐nya sudah diketahui.
Metode BW bekerja sangat baik pada gambar, suara, dan teks, dan dapat mencapai rasio kompresi yang sangat tinggi (1 bit per byte atau bahkan lebih baik). [TTG4J3] Koding dan Kompresi
RLE & BW Transform
16
1. 2. 3. 4. 5.
Diberikan sebuah string yang terdiri atas N buah karakter Lakukan rotasi (pergeseran secara siklik) per karakter sebanyak N ‐1 kali Sorting hasil rotasi berdasarkan urutan leksikografi (ascending) Ambil karakter terakhir dari hasil sorting, sebagai hasil transformasi BW Simpan indeks baris, yang berisi string awal (indeks mulai dari 0) [TTG4J3] Koding dan Kompresi
RLE & BW Transform
17
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
18
Misalkan hasil transformasi BW yang akan didecode adalah S yang terdiri atas N buah karakter 1. 2. 3. 4. 5. 6.
Sorting string S secara ascending, misalkan S* Rangkaikan string S dengan hasil sorting tersebut Lakukan sorting terhadap string hasil panggabungan Rangkaikan string S dengan hasil sorting no.3 Ulangi langkah 3 dan 4 hingga diperoleh string dengan N buah karakter String asli ada di nomor indeks key [TTG4J3] Koding dan Kompresi
RLE & BW Transform
19
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
20
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
21
Cari hasil tranformasi Burrows‐Wheeler untuk string adaadasaja
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
22
Apa manfaat transformasi BW? Perhatikan contoh sebelumnya : BANANA@ Æ ANNB@AA
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
23
1.
Adam Drozdek, Elements of Data Compression, Thomson Brooks/Cole, 2002
2.
Khalid Sayood, Introduction to Data Compression, Academic Press, 2000.
3.
T.M. Cover, J.A. Thomas, Elements of Information Theory, John Wiley&Sons.
4.
M. Nelson and J.‐L. Gailly. The Data Compression Book. M&T Books, CA, 1996.
5.
D. Salomon. Data Compression: The Complete Reference. Springer, 1998.
[TTG4J3] Koding dan Kompresi
RLE & BW Transform
24
