133
KOMPRESI CITRA LOSSLESSDENGAN ALGORITMA QUADTREE-OBDD$ Handoko$ ABSTRAK Ordered Binary Decision Diagram (OBDD) telah digunakan untuk mengurangi penyimpanan dan waktu perhitungan yang dibutuhkan untuk menguji kebenaran untai digital. Dalam hal ini, sebuah citra dapat dianggap sebagai fungsi Boolean dengan memandangnya sebagai sebuah kamaugh-map~ Citra dibagi menjadi blok yang lebih kecil dengan Qpadtree dan dikompresi dengan OBDD sesuai dengan karakteristiknya. Hasil uji coba teknik kompresi citra LoSS/lSI dengan Quadtree-OBDD menghasilkan rasio kompresi rata-rata sebesar 1.25, 3.29, 7.47, 30.19 dan 1.02 un~ citra natural, citra text, citra binary, citra buatan dan citra texture. Hasil ini lebih baik dibanding dengan ~etode kompresi GIF untuk seluruh kelompok kecuali citra text dan lebih baik dibanding dengan metode kompresi Losskss JPEG untuk citra binary. Kata Kunci: OBDq Quadtree, kompresi citra
ABSTRACT Ordered Binary Decision Diagram (OBDD) has been used to reduce the amount of space and computing time required for veri~g digital circuits. In this regards, an image can be processed as a Boolean function and modeled as. a kamaugh-map. An image is partitioned into equal sized blocks where each block is represented as an OBDD according to its characteristics. Experimental results show that the lossless image compression technique using QUll-dttee-OBDD produce average compression ratio of 1.25, 3.29, 7.49, 30.19, and 1.02 for natural, text, binary, synthetic and texture images, respectively. These results are better than the GIF scheme for all images classification except for text images, and are better than the Lossless JPEG scheme for binary type
images.
I
Keywords: OBDD, Quadtree, Image Compression
l.PENDAHULUAN Berbagai metode kompresi citra telah dikembangkan dal.arn rangka mencapai raslO kompresi yang tinggi dengan tetap mempertahankan !fIlutu. Secara umum kompresi citra terbagi menjadi dua, yaitu lossless dan lossy. Untuk kelompok Iqssless dikenal beberapa metode misalnya Run Len~ Encoding yang diterapkan pada file PCx, LZW pada file TIFF, Quadtree dan Pengkodean Huffman, dengan metode ini seluruh data dipertahankan atau dengan kata lain tidak ada data )fang hilang. Metode-metode untuk kompresi lokless biasanya mempunyai rasio kompresi yang rendah dan kebanyakan dikerjakan pada! piksel secara linier, tidak memandang citra sebagai blok-blok kecil. karakteristik yang Padahal salah i satu membedakan anrara citra dan data lain adalah karakteristik spasiallnya, artinya nilai antara piksel yang berdekatan sbcara spasial biasanya harnpir sarna. Karakteristik ini yang didekati dengan penggunaan metode OBDD. Quadtree merupakan algoritrna kompresi citra secara spasi~ dan telah digunakan secara luas untuk menyimpan citra pada bidang GIS
(Geographic Information System) dan hasil foto medikal dengan sinar X. Quadtree merupakan algoritrna kompresi yang cepat dengan cara membagi sebuah citra menjadi empat bagian secara rekursi hingga area terkecil yang tidak dapat dibagi lagi tercapai. Binary Decision Diagram (BDD) merupakangraJ directed afYclic dengan dua tipe simpul yang berbeda, yaitu simpul terminal dan simpul nonterminal. Simpul terminal mewakili nilai Boolean '0' dan '1' sedangkan simpul non-terminal menyatakan variabel dari fungsi yang akan direpresentasikan oleh BDD ini. Setiap simpul non-terminal mempunyai dua cabang keluaran yang ditandai dengan konstanta Boolean '1' pada satu cabang dan '0' pada cabang yang lain (Bryant, 1986). Graf BDD selalu diawali dengan satu simpul yang disebut sebagai root yang tidak mempunyai induk/ cabang masukan. BDD memiliki dua sifat penting yaitu bisa diurutkan dan bisa disederhanakan (fownsend et aL, 1999). Ordered BDD (OBDD) merupakan BDD yang setiap variabelnya muncul tidak lebih dari satu kali pada setiap jalurnya dan selalu muncul
penulis skat menyelesaikan studi Master diArian Institute ofTechnolog;, Bangkok, Thailand Teknik Elektro, Fakultas Teknik, UKSW,Jl. Diponegoro 52-60, Salatiga 50711.
S Penelitian § Jurusan
Vol. 15, No.4, Nopember 2004 - Majalah IPTEK
134
dengan urutan yang sama. OBDD pada mulanya digunakan untuk mengurangi kebutuhan kapasitas penyimpanan dan perhitungan yang dibutuhkan untuk menguji kebenaran suatu untai digital. OBDD akan membuang bagian-bagian sub-function yang kembar (redundan~ yang terdapat pada fungsi Boolean. Gambar 1 menunjukkan contoh representasi sebuah fungsi biner (a • c), berturut-turut dengan binary tree, quadtree dan OBDD (Bryant, 1992). OBDD dan Pengkodean Huffman juga telah digunakan sebagai algoritma kompresi citra (Witwiyaruj, 2000). Untuk kompresi citra, OBDD diterapkan pada blok-blok kecil dari citra yang telah dibagi-bagi. Witwiyaruj (Witwiyaruj, 2000) menyimpulkan bahwa kemampuan OBDD untuk melakukan kompresi sangat tergantung pada ukuran blok OBDD, dengan blok 16x16 piksel ukuran data yang terkompresi lebih kecil daripada menggunakan blok 32x32 piksel. N amun penggunaan blok 16x16 piksel akan menyebabkan total ukuran header yang dibutuhkan bertambah. Sebagai contoh, pada blok 64x64 piksel dengan semuanya mempunyai nilai piksel yang seragam, akan lebih baik digunakan ukuran blok 64x64 dibandingkan dengan 32x32 atau 16x16. Dalam penelitian ini akan diperbaiki kinerja kompresi citra metode OBDD dengan secara adaptif menggunakan ukuran blok yang berbedabeda pada sebuah citra. Oleh karena itu digunakan OBDD dengan ukuran blok yang bervariasi tergantung dari kondisi blok citra yang akan dikompresi, dengan pembagian bloknya akan digunakan algoritma Quadtree.
2.
REPRESENTASI OBnn UNTUK CITRA BITMAP OBDD untuk kompresi citra adalah teknik kompresi yang diperkenalkan oleh Starkey dan Bryant (Starkey el ai, 1995), serta Lursinsap, Kanchanasut dan Sirlboon (Lursinsap el aI, 1997). Sebuah citra hitam-putih (binary image) dapat dinyatakan sebagai fungsi biner dengan citra tersebut dipandang sebagai sebuah karnaughmap (I<-Map). Dengan demikian sebuah piksel yang dapat dinyatakan sebagai sebuah fungsi jika sepanjang koordinat x dan koordinat y diberi variabel biner tertentu (Gambar 2a). Jika secara konsisten kita memberi cabang (kiri atau kanan) berdasarkan nilai bit variabel maka OBDD dapat disusun untuk suatu citra. Nilai koordinat menggunakan penomoran big-endian yang lebar bitnya tergantung dari ukuran blok yang akan diproses.
Majalah IPTEK - VoL 15, No.4, Nopember 2004
(a)
(b)
(c)
Gambar 1. Representasi fungsi biner (a) dengan binary tree (b) dengan binary Quadtree (c) dengan OBDD.
OBDD dalam penelitian ini mengacu pada OBDD yang diusulkan oleh Lursinsap, Kanchanasut and Sirlbon (Lursinsap el ai, 1997) dan dibangun dengan urutan variabel tertentu. OBDD yang sederhana didapatkan dengan menerapkan algoritma penyederhanaan dan aturan transformasi. Sebagai contoh, citra pada gambar 2(a) jika dinyatakan dengan fungsi sum of product (SOP) dapat ditulis menjadi f=x1 '. yl' • yO' + xl • xO + xl' • xO' • y1' + xl • yl • yO, dengan hasil dari OBDD dapat ditunjukkan pada gambar 2(c). Ada riga aturan penting untuk membuang simpul kembar yang muncul pada saat membangun OBDD, yaitu (Witwiyaruj, 2000; Akers, 1978):
135
x1xo 00
01
11
10
00 o
,.,
01
>.
11
x1 xU 0 0 0 0 0 0 0 0 1
1 1
1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
I--+--
F
1
0 0 1
1 0 0 1
1 0 0 1 1 0 0 1 1 (b)
0 1 0 1 0 1 0 1 0 1 0
1 1 0 0 1 0 0 0 0 0 0
1
1
0 1 0
1 1
1
1 1
(c) Gambar 2. (a) citra sederhana (4 x 4); (b) tabd kebenaran dati citra untuk menyusun OBDD (c) representasi OBDD untuk citra (a). a) Membuang terminal yang kembar: Simpul terminal yang mempunyai nilai sarna dapat diwakili dengan sebuah simpul saja dan semua cabang yang mengarah ke simpul terminal tersebut diarahkan ke simpul yang mewakili. seperti dicontohkan dalam Gambar 3a. b) Membuang Non-Terminal yang kembar: Jika simpul non-terminal u dan v menyatakan var (v) dan variabd yang sarria var (u) keduanya mempunyai anak yang sarna baik pada cabang '0' maupun cabang '1', maka salah satu simpul tersebut bisa dihilangkan dan input dati keduanya diarahkan ke simpul yang mewakili. seperti dicontohkan dalam Garnbar 3b. c) Membuang Redundant Test: Jika kedua cabang yang keluar dati simpul non-terminal menuju ke simpul yang sarna, maka simpul
=
(c) Gambar 3. Aturan untuk membuang simpul kembar. tersebut bisa dihilangkan mena evaluasi fungsi boolean yang dinyatakan tidak tergantung pada simpul ini, seperti dicontohkan dalam Garnbar 3c. Untuk citra dengan derajat keabuan, algoritma OBDD diterapkan pada setiap bitplane, sehingga sebuah citra dengan derajat keabuan 8 bit akan menghasilkan 8 buah OBDD. Untuk memberi gambaran bagaimana OBDD dihasilkan dari citra derajat keabuan 8 bit, Garnbar 4 menunjukkan bagaimana OBDD disusun untuk citra derajat keabuan 2 bit. Analisis Running Time Complexity a. Kondisi terbaik (Best Case) Akan tercapai bila semua piksd dalam blok '0' atau '1 '. Pada kasus ini tidak tergantung pemilihan urutan variabel yang digunakan, mena akan didapatkan hasil yang selalu sarna. Pada kondisi ini OBDD akan memiliki: a Tinggi levd : 1 a Jumlah Simpul non terminal: 1 a Big-Oh time complexity 0(1) b. Worst Case Kondisi terburuk akan tercapai jika piksd dalam blok membentuk pola seperti papan catur. Secara nyata, citra yang mirip ini adalah citra dengan perubahan intensitas yang sangat cepat tiap piksdnya. Pada kondisi ini OBDD akan memiliki: a Tinggi level: log2 [M+N] a J umlah Simpul non terminal: 2N - 1 Vol. 15, No.4, Nopember 2004 - Majalah IPTEK
136
)(0)(1
00
01
11
10
00 YoY1
01
2 bit grayscale
11 10
(a)
G\ ~.•./
\ .•......... '.
....,
(b) Bitplane #1
Bitplane #2
XOX1
00
01
XOXt
11
10
00
00 YQY1
01
11
10
00 YQY1
01
01
11
11
10
10
(c) Garnbar 4. (a) Citra derajat keabuan 2-bit (b) OBDD bagi tiap bztplane (c) Citra biner untuk tiap bitplane (a).
D
Big-Oh time complexiry: E>(2(pog2 M) + pog2 N) + 1 )
dengan M dan N adalah ukuran blok.
3. QUADTREE Quadtree, yang diusulkan oleh Cohen, Strobach, serta Shusterman dan Feder, adalah sebuah pohon (tree) yang tiap simpulnya memiliki 0, 1,2,3 atau 4 anak. Simpul yang tidak memiliki anak disebut sebagai leaf sedangkan lainnya disebut dengan simpul internal. Tingkat dari sebuah simpul adalah jumlah edge dari akar (root) hingga simpul tersebut. (Cheng, 1996). Quadtree pada penelitian ini digunakan untuk membagi sebuah citra menjadi blok-blok yang lebih kecil untuk selanjutnya diproses dengan algoritma OBDD. Delapan buah Quadtree juga diperlukan untuk menyatakan citra derajat keabuan 8-bit. Untuk setiap bitplane, citra akan dibagi-bagi dan quadtree akan dibentuk. Pada penelitian ini, ukuran blok yang digunakan hanya dua macarn yaitu 32x32 piksel dan 64x64 pikse~ karena dari penelitian sebelumnya, OBDD dengan ukuran blok 16x16 piksel mempunyai rasio kompresi yang terburuk dibandingkan yang lain untuk semua kondisi citra sarnpel. Sedangkan OBDD dengan ukuran blok lebih dari 64x64 piksel dinilai tidak optimal karena Majalah IPTEK - Vol. 15, No.4, Nopember 2004
kemungkinan untuk kompresi lebih kecil. Oleh karena itu pengkodean quadtree dapat dilakukan dengan memberi nilai '1' bagi terminal dengan ukuran blok 32x32 piksel dan '0' untuk blok 64x64 piksel. Keputusan untuk memilih ukuran blok dilakukan dengan beberapa aturan. Citra akan dibagi menjadi ukuran yang lebih kecil hingga ukuran 64x64 pikse~ setelah itu blok citra tersebut dites dengan aturan-aturan tertentu. Aturan ini akan memutuskan apakah blok tersebut harus dibagi menjadi blok-blok yang lebih kecillagi atau tidak. Aturan ini diarnbil dari penelitian yang dilakukan sebelumnya dengan melihat hasil pembandingan antara OBDD dengan berbagai ukuran pada sarnpel citra tertentu. Pada penelitian awal citra dibagi-bagi menjadi ukuran 64x64, 32x32 dan 16x16 kemudian diterapkan OBDD pada tiap blok. Tiap-tiap blok juga dihitung prosentase bit '1' nya untuk dilihat keterkaitan populasi bit '1' dengan ukuran blok yang harus dipakai. Aturan disusun secara urut sebagai berikut (Kanchanasut et al, 2002): a. Nilai bit '1' dihitung untuk tiap quadran Ql, Q2, Q3, dan Q4 adalah quadran 1, 2, 3 dan
4.
~ ~
b. Jika persentasi bit '1' lebih dari 98.5% atau kurang dari 1%, maka proses dekomposisi dihentikan dan OBDD dengan ukuran blok 64x64 piksel akan digunakan pada blok tersebut c. Jika tidak memenuhi, jika salah satu dari antara 4 quadrant mempunyai nilai bit yang sarna entah '0' atau '1' maka blok tersebut akan dibagi lagi menjadi 4 blok 32x32 piksel dan OBDD dengan ukuran 32x32 piksel akan digunakan. d. Jika tidak memenuhi, jika persentasi bit '1' tidak di antara 45% - 55 %, blok akan dibagi 4 dan OBDD ukuran blok 32x32 piksel yang akan digunakan. e. Jika semua di atas tidak terpenuhi, jika perbedaan persentasi antar tiap quadran lebih dari 2.0% maka blok akan dibagi menjadi 4 dan digunakan OBDD dengan ukuran 32x32 piksel. Kurang dari 2.0% mempunyai arti bahwa distribusi bit '1' dapat dikatakan seragam dan diduga tidak akan dapat dikompresi, sehingga OBDD dengan ukuran 64x64 piksel akan lebih baik karena memerlukan header yang lebih kecil dibandingkan dengan penggunaan OBDD dengan ukuran blok 32x32 piksel (Qdiff).
137
4. HASIL VJI CODA Untuk menguji Quadtre-OBDD, beberapa citra standar untuk kompresi digunakan. Citra yang digunakan untuk percobaan adalah citra derajat keabuan 8 bit dengan ukuran 256x256 dan 512x512 pikseL Citra-citra ini diklasifikasikan ke dalam beberapa kelompok yang dinamai natural (pemandangan dan hewan), text, biner, texture, dan citra buatan. Setiap kelompok terdiri dari 5 hingga 10 citra yang berbeda masingmasing dua ukuran (256x256 dan 512x512 piksel). Gambar 5 menunjukkan sebagian citra yang digunakan pada percobaan, sedangkan Tabel 1 menunjukkan statistik ukuran citra yang digunakan. Dari hasil percobaan (fabel2) terlihat bahwa Quadtree-OBDD mencapai hasil terbaiknya jika digunakan untuk mengompresi citra dengan warna yang berupa blok-blok seperti citra buatan citra biner dan citra text. Tabel tersebut juga n:enunjukkan bahwa rasio kompresi untuk citra buatan terbaik di antara citra kategori lain, sedangkan rasio kompresi untuk citra tekstur terburuk. Hal ini disebabkan setiap bit-plane dari citra texture bisa dikatakan random total, sehingga tidak mempunyai pola yang dapat dikompresi dengan OBDD. Rasio kompresi rata-rata untuk citra natural tidak terlalu tinggi karena alasan yang sama, namun masih lebih baik dibandingkan citra texture karena masih mempunyai pola yang berupa blok. Juga diperhatikan bahwa Quadtree-OBDD lebih lambat dibandingkan dengan OBDD dengan ukuran blok 32x32 piksel tapi lebih cepat dibandingkan OBDD dengan ukuran blok 64x64 pikseL Secara rata-rata, semakin besar nilai QDiff akan memerlukan waktu proses yang makin lama karena semakin besar nilai QDiff menyebabkan semakin banyak blok 64x64 piksel yang digunakan. Karena OBDD dengan ukuran 64x64 piksel lebih lambat dari OBDD dengan ukuran blok 32x32, maka semakin banyak blok 64x64 piksel yang digunakan akan memper-Iambat proses.
(e) Binary
(f) Text
(g) Texture
Gambar 5. Sampel citra yang digunakan dan klasifikasinya. Sebaliknya semakin keci1 nilai QDiff, semakin banyak blok 32x32 piksel yang dihasilkan. U:ntuk tiap OBDD dengan ukuran blok 32x32 pikse~ harus digunakan header dengan ukuran 3 byte, dengan byte pertama menunjukkan ukuran data sub-blok dan dua byte berikutnya untuk kode Huffman dan tingkat awal dari tree. Pada OBDD dengan ukuran blok 64x64 piksel dibutuhkan header dengan ukuran 4 byte, dengan dua byte pertama menunjukkan ukuran data sub-blok dan dua byte berikutnya untuk kode Huffman dan tingkat awal dari tree. Dengan ukuran blok 64x64 dibutuhkan 2 byte untuk menyimpan ukuran data pada sub-blok karena uk-uran maksimal yang mungkin dari data pada sub-blok tersebut adalah: (64x64)/8 byte = 512, sehingga 1 byte tidak cukup untuk menyimpan informasi ini. Pada sebuah blok dengan ukuran 64x64 pikseI, jika digunakan OBDD den~ ukuran blok 64x64 piksel, total header yang dibutuhkan adalah 1x4 byte yaitu 4 byte. Sedangkan jika digunakan OBDD dengan ukuran blok 32x32 piksel maka blok 64x64 tersebut terbagi menjadi 4 sub-blok, sehingga besamya header yang dibutuhkan adalah 4x3 byte yaitu 12 byte. VoL 15, No.4, Nopember 2004 - Majalah IPTEK
138
Sehingga semakin banyak biok 32x32 menyebabkan ukuran header makin besar. Untuk citra buatan, digunakan aturan yang berbeda dan hasilnya Iebih baik jika dibandingkan dengan hasil sebe1umnya. Sebenarnya aturan yang Qaru ini sarna saja dengan penggunaan OBDD dengan ukuran biok 64x64 piksel seIuruhnya. Hal ini disebabkan oleh karakteristik. citra itu sendiri yang secara efektif lebih baik dikompresi dengan OBDD ukuran biok 64x64 pikse1. Untuk setiap bit-plane, citra buatan memiliki biok-blok yang dapat dikompresi dengan baik. Dari Tabe1 2 dapat dilihat bahwa untuk citra buatan, OBDD dengan ukuran blok 64x64 piksel Iebih baik dibandingkan dengan Quadtree-OBDD, hal ini dikarenakan Quadtree-OBDD harus menyimpan struktur quad tree pada file output juga. Modifikasi aturan juga diterapkan pada citra biner dengan QDiff dites pada semua populasi bit '1', tidak hanya diantara 45% dan 55%. Hal
ini disebabkan citra biner secara normal memiliki piksel hitam dalam jumlah yang keci1 dan tidak terkonsentrasi pada biok-blok. Untuk ke1ompok citra ini urutan variabe1 OBDD juga diubah dari Yo-Yl-Y2-Xo-Xl-X2-X3-~-Y3-Y4 menjadi Xo-XlX2-Yo-Yl-Y2-X3-~-Y3-Y4 untuk OBDD dengan ukuran biok 32x32. Perubahan ini meningkatkan rasio kompresi citra biner, dan tidak berpengaruh terhadap kelompok citra yang lain, sehingga urutan variabe1 yang berbeda seharusnya diterapkan pada ke1ompok citra yang berbeda juga untuk mendapatkan hasil terbaik pada tiaptiap kelompok citra. Urutan variabe1 akan mempengaruhi rasio kompresi karena urutan variabe1 yang berbeda akan menghasilkan pohon OBDD yang berbeda juga. Urutan variabe1 yang tepat akan menghasilkan pohon OBDD yang keci1 karena memungkinkan adanya pembuangan simpulsimpul yang kembar (redundan~.
Selanjutnya OBDD dibandingkan dengan algoritma lain, yaitu Graphical Interchange Format (GIF) dan Lossless JPEG 2000. GIF diambil sebagai perbandingan sebab format GIF banyak digunakan di halaman web dan untuk citra dengan 256 derajat keabuan GIF memiliki sifat Iossless. Sedangkan LS-JPEG 2000 dipilih karena merupakan metode baru yang dikeluarkan oleh JPEG untuk kompresi lassless. Perbandingan hanya dilakukan untuk rasio kompresi yang hasilnya dapat dilihat pada Tabel 3. Dari hasil tersebut dapat disimpulkan bahwa kinerja Quadtree-OBDD Iebih baik dibandingkan dengan algoritma GIF pada semua ke1ompok citra kecuali citra text. GIF tidak dapat digunakan untuk kompresi citra texture, sedangkan Quadtree-OBDD bisa meskipun dengan rasio kompresi yang keci1. Jika dibandingkan dengan Lossless JPEG, rasio kompresi dengan Quadtree-OBDD Iebih baik hanya untuk citra biner. Secara umum rasio kompresi Quadtree-OBDD lebih buruk dibandingkan dengan Lossless JPEG untuk kelompok citra Iainnya. Keunggulan Qua~tree-
OBDD dibandingkan dengan Lossless JPEG adalah kesederhanaan algoritmanya dengan Lossless JPEG memerlukan persarnaan yang Iebih komplek sedangkan Quadtree-OBDD hanya menggunakan operasi perbandingan saja.
Majalah IPTEK - Vol. 15, No.4, Nopember 2004
TabeL 3.
kompresi an tara
Pada penelitian ini tidak dibandingkan waktu proses an tara Quadtree-OBDD dengan GIF dan Lossless JPEG karena digunakan lingkungan pemrograrnan yang berbeda antara aplikasiaplikasi ini. Aplikasi Lossless JPEG yang digunakan (LOCO) menggunakan lingkungan DOS, sedangkan Quadtree-OBDD mengguna-
139
kan pemrograman visual. Namun secara teoritis, ussless JPEG menggunakan perhitunganperhitungan yang jauh lebih rumit dibandingkan dengan Quadtre-OBDD dan oleh karena alasan yang sama JPEG dapat menghasilkan faktor kompresi yang lebih baik. Untuk pengembangan dapat diterapkan Quadtree-OBDD ini pada citra berwarna. Bila digunakan citra berwarna 24 bit maka diperlukan 24 pohon OBDD untuk tiap-tiap blok. Selain itu jika citra berwarna RGB diubah menjadi YUV maka algoritma Quadtree-OBDD pada citra YUV akan menjadi metode kompresi lossy. Pada penelitian ini dibatasi hanya citra dengan 256 derajat keabuan saja. 5.SIMPULAN a. Quadtree digunakan untuk memutuskan pembagian blok suatu citra. Setelah ditentukan ukuran blok tertentu, blok tersebut akan dikompresi dengan algoritma OBDD dan kemudian dikodekan lagi dengan pengkodean Huffman untuk mendapatkan rasio kompresi yang lebih baik. b. Kinerja algoritma Quadtree-OBDD tergantung pada ukuran blok OBDD dan ukuran OBDD yang akan digunakan tergantung pada karakteristik citra serta urutan variabel. Quadtree-OBDD meningkatkan kinerja OBDD pada aspek rasio kompresi dengan menggunakan ukuran blok yang bervariasi. c. Mirip dengan OBDD, Quadtree-OBDD menghasilkan penyimpanan citra yang lebih kecil untuk citra dengan banyak blok dan sedikit perubahan warna seperti kelompok citra buatan, biner dan text. Kemampuan algoritma ini menurun jika diterapkan untuk citra dengan banyak detil dan variasi warna seperti citra natural dan texture. d Kompresi citra dengan algoritma QuadtreeOBDD menghasilkan rasio kompresi ratarata sebesar 1.25 untuk citra natural, 3.29 untuk citra text, 7.49 untuk citra biner, 30.19 untuk citra buatan dan 1.02 untuk citra texture. Hasil ini lebih baik jika dibandingkan dengan algoritma GIF untuk seluruh kelompok citra kecuali citra text dan lebih baik dibandingkan dengan ussiess JPEG untuk kelompok citra binary saja.
DAFfAR ACUAN Akers, S. B. (1978), 'Binary Decision Diagrams', IEEE Transaction on Computers, Vol. C-27 No.
6. Bryant, R. E. (1986), 'Graph Based Algorithms for Boolean Function Manipulation', IEEE Transaction on Computers, Vol. C-35 No.8. Bryant, R. E. (1992), 'Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams', ACM Computing SU17Jeys, Vol. 24, No.3. Cheng, H., and Li, x., 'On Application of Image Decomposition to Image Compression and Encryption•• (www.scg.uwaterloo.ca/-hchche ng/papers/). Kanchanasut, I<. and Handoko (2002), 'Hybrid Image Representation Using Quadtree and OBDD', Master Thesis, Department of Computer Science, Asian Institute of Technology, Bangkok. Lursinsap,C., Kanchanasut, 1<., Sirlboon, T. (1997), 'Basic Binary Decision Diagram Operations for Image Processing', Proc. 3rd Asian Computing Science Conference, SpringerVerlag, Lecture Notes in Computer Science 1345, pp. 368-370. Starkey, M., and Bryant, R. (1995), Using Ordered Binary-Decision Diagrams for Compressing Images and Image Sequences, Department of Computer Science, Carnegie Mellon University, Pittsburg. Townsend, W., and Thornton, A. (1999), 'Partial Binary Decision Diagrams', Mississippi State University, (http://cs.engr.uky.edu/ -lewis/ papers / merge-alg. pdf). Witwiyaruj, I<. (2000), 'Design and Implementation of A Coding Scheme for Image Compression Using Ordered Binary-Decision Diagram', Master Thesis, Department of Computer Science, Asian Institute of Technology, Bangkok.
Diterima: 15 Maret 2004 Disetujui untuk diterbitkan: 7 Oktober 2004
Vol. 15, No.4, Nopember 2004 - Majalah IPTEK
