DISERTASI - KI143541
KOMPRESI CITRA LOSSLESS MENGGUNAKAN TRANSFORMASI BILANGAN BULAT DAN DIFFERENTIAL ENCODING
HENDRA NRP. 5113301001 DOSEN PEMBIMBING Prof.Ir. Handayani Tjandrasa, M.Sc., Ph.D. Dr. Chastine Fatichah, S.Kom, M.Kom.
PROGRAM DOKTOR ILMU KOMPUTER JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNOLOGI INFORMASI INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2017
KOMPRESI CITRA LOSSLESS MENGGUNAKAN TRANSFORMASI BILANGAN BULAT DAN DIFFERENTIAL ENCODING Nama mahasiswa NRP Pembimbing
: Hendra : 5113301001 : Prof. Ir. Handayani Tjandrasa, M.Sc, Ph.D Dr. Chastine Fatichah, S.Kom, M.Kom
ABSTRAK Metode kompresi citra lossless dikembangkan untuk menyimpan atau mentransmisikan citra tanpa menghilangkan sedikit pun detail informasi yang ada dalam citra tersebut. Aplikasi metode ini digunakan pada citra satelit, foto udara, dan data medik. Pendekatan yang umumnya digunakan dalam kompresi citra lossless adalah Predictive Coding, Burrows-Wheeler Transform, dan Variable Block Size Segmentation. Dalam algoritmanya, metode-metode kompresi lossless menggunakan entropy coding untuk mengkodekan citra dengan kode yang lebih efisien. Penelitian ini mengembangkan metode kompresi citra lossless dengan pendekatan yang berbeda yaitu menggunakan konsep reversible watermarking yang dibangun dari transformasi bilangan bulat Reversible Contrast Mapping (RCM) dan Reversible Low Contrast Mapping (RLCM). Penelitian memperkenalkan tiga skema kompresi citra lossless menggunakan transformasi bilangan bulat yaitu skema reversible watermarking dan pendekatan coding dalam skema Average Encoding (AE) dan Hierarchy Average Encoding (HAE). Pada pendekatan coding, penelitian ini mengkolaborasikan RLCM dan Differential Encoding. Metode Cyclic Reversible Low Contrast Mapping (CRLCM) merupakan metode dengan rasio kompresi tertinggi dalam skema reversible watermarking. Pada skema AE, penelitian ini memperkenalkan empat metode coding yaitu 1RLCM (one step RLCM)-Up, Ext-1RLCM-Up, 1RLCM-Dw, dan 1RLCM-0. Metode yang memiliki rasio kompresi tertinggi pada skema ini adalah 1RLCM-0. Skema HAE diimplementasikan dalam dua metode yaitu metode dasar dan MAPHAE. Kompleksitas Algoritma metode-metode dengan pendekatan coding sama dengan Golomb coding yaitu ( ). Rasio kompresi metode 1RLCM-0 pada skema AE dan skema HAE umumnya sama dengan metode kompresi Golomb coding untuk citra standar tetapi metode-metode ini memiliki rasio kompresi yang lebih besar untuk citra medik. Implementasi 1RLCM-0 pada metode kompresi citra JPEG-LS dengan mengganti metode adaptive-Golomb yang digunakan pada metode tersebut menghasilkan rasio kompresi sebanding dengan metode JPEG-LS original. Kata Kunci: Kompresi citra lossless, Transformasi bilangan bulat, Differential Encoding, Reversible Contrast Mapping, Reversible Low Contrast Mapping, Average Encoding, Hierarchy Average Encoding. vii
LOSSLESS IMAGE COMPRESSION USING INTEGER TRANSFORM AND DIFFERENTIAL ENCODING Name Student Id Supervisor
: Hendra : 5113301001 : Prof. Ir. Handayani Tjandrasa, M.Sc, Ph.D Dr. Chastine Fatichah, S.Kom, M.Kom.
ABSTRACT Lossless image compression methods were developed to save and transmit images without losing any detailed information of the images. Applications of these compression methods are for compressing the satellite images, aerial photographs, and medical data. The most common approaches used in this compression type are predictive coding, Burrows-Wheeler Transform, and variable block size segmentation. In the algorithms, lossless image compression methods use entropy coding for more efficient compression result. This research develops a new lossless image compression method using a different approach that exploiting the concept of the reversible watermarking method for the integer transform of Reversible Contrast Mapping (RCM) and Reversible Low Contrast Mapping (RLCM). This research introduces three lossless image compression schemes, i.e. reversible watermarking scheme, coding approach by Average Encoding (AE), and Hierarchy Average Encoding (HAE) Scheme. The coding approach collaborates the RLCM transform and the Differential Encoding. On the reversible watermarking scheme, the Cyclic Reversible Low Contrast Mapping (CRLCM) has the highest compression ratio. In AE scheme, this research introduces four coding methods, i.e. 1RLCM (one step RLCM)-Up, Ext-1RLCMUp, 1RLCM-Dw, and 1RLCM-0. The 1RLCM-0 has the highest compression ratio for this scheme. The HAE scheme is implemented using two approaches, i.e. the basic method and MAP-HAE. The algorithm complexity of the coding approaches is equal to Golomb coding complexity, which is ( ). The compression ratio of the 1RLCM-0 for AE scheme and HAE scheme is generally equal to Golomb coding’s for the standard images, but the proposed methods have significantly higher compression ratio for medical images. Implementation of the 1RLCM-0 in JPEG-LS compression method by replacing the adaptive-Golomb coding in the method results in similar compression ratio compared to the JPEG-LS original. Keywords: Lossless image compression, Integer Transform, Differential Encoding, Reversible Contrast Mapping, Reversible Low Contrast Mapping, Average Encoding, Hierarchy Average Encoding.
ix
KATA PENGANTAR Puji syukur penulis panjatkan kepada Allah SWT atas selesainya penulisan disertasi ini. Disertasi ini disusun untuk memenuhi salah satu syarat akademik Program Doktoral Ilmu Komputer, Jurusan Teknik Informasi, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh November (ITS), Surabaya. Penulis menyadari bahwa dalam proses penyelesaian disertasi ini telah melibatkan berbagai pihak, baik secara langsung maupun tidak langsung. Pada kesempatan ini, penulis mengucapkan terima kasih dan penghargaan yang setinggitingginya kepada: 1. Pemerintah Republik Indonesia melalui Kementerian Ristekdikti yang telah memberikan beasiswa BPPDN selama masa studi; 2. Rektor Universitas Hasanuddin yang telah memberikan ijin tugas belajar, serta segenap civitas akademika UNHAS atas segala dukungannya; 3. Para pembimbing, yaitu: Ibu Prof. Ir. Handayani Tjandrasa, M.Sc., Ph.D selaku Ketua Promotor, Ibu Dr. Chastine Fatichah, S.Kom, M.Kom selaku co-Promotor; yang tidak kenal lelah dalam memberikan bimbingan berupa saran dan masukan serta motivasi selama penulis menempuh studi doktoral Ilmu Komputer di Jurusan Teknik Informatika ITS; 4. Para penguji, yaitu: Bapak Prof. Dr-Ing. Ir. Iping Supriana, DEA; Bapak Prof. Ir. Supeno Djanali, M.Sc, Ph.D; dan Bapak Dr. Ir. R.V. Hari Ginardi, M.Sc yang telah memberikan usulan, saran, dan masukan perbaikan penelitian disertasi ini; 5. Segenap pengelola Program Pascasarjana (PPs) ITS, dosen dan karyawan PPs jurusan Teknik Informatika ITS yang telah memberikan dukungan dan bantuan selama penulis menempuh program pendidikan ini; 6. Istri tercinta Harliana Djafar dan anak-anakku tersayang Ilham dan Indira yang terus memberikan semangat dan harapan dalam menyelesaikan studi; 7. Kedua orang tua tercinta Bapak Mesra Billa dan Almarhum Ibu Djohasan serta semua keluarga yang selalu memberikan doa, motivasi dan dukungan selama menempuh pendidikan ini;
xi
8. Segenap rekan-rekan seperjuangan di Program Doktoral Ilmu Komputer atas segala bantuan, dukungan dan motivasi; 9.
Semua pihak yang telah membantu penulisan disertasi ini yang tidak dapat disebutkan satu persatu. Kiranya Allah SWT membalas amal serta kebaikan Bapak dan Ibu serta
selalu melimpahkan karunia-Nya kepada kita semua. Penulis sangat menyadari bahwa dalam penulisan disertasi ini masih jauh dari sempurna, oleh karena itu penulis mengharapkan kritik dan saran yang membangun dari semua pihak demi perbaikan dan penyempurnaan buku disertasi serta kelanjutan penelitian disertasi ini. Akhirnya, semoga buku disertasi ini bermanfaat dan berguna bagi berbagai pihak, utamanya pemerhati kompresi citra lossless dan kompresi lossless secara umum. Surabaya,
Januari 2017
Hendra
xii
DAFTAR ISI LEMBAR PENGESAHAN DISERTASI ............................................................ iii PERNYATAAN KEASLIAN .............................................................................. v ABSTRAK ........................................................................................................ vii ABSTRACT ....................................................................................................... ix KATA PENGANTAR ........................................................................................ xi DAFTAR ISI .................................................................................................... xiii DAFTAR GAMBAR ....................................................................................... xvii DAFTAR TABEL ............................................................................................ xxi DAFTAR SINGKATAN ................................................................................ xxiii BAB 1 PENDAHULUAN ................................................................................. 1 1.1. Latar Belakang ......................................................................................... 1 1.2. Perumusan Masalah .................................................................................. 4 1.3. Tujuan dan Manfaat Penelitian ................................................................. 4 1.4. Keaslian Penelitian ................................................................................... 5 BAB 2 TINJAUAN PUSTAKA ......................................................................... 7 2.1. Reversible Contrast Mapping (RCM) ....................................................... 7 2.2. Reversible Low Contrast Mapping (RLCM) ........................................... 10 2.3. Differential Encoding ............................................................................. 15 2.4. Recursive Indexing ................................................................................. 16 2.5. Kompresi Lossless .................................................................................. 17 2.5.1. Kode Huffman ................................................................................ 18 2.5.2. Kode Golomb ................................................................................. 19 2.6. Kompresi Citra ....................................................................................... 20 2.6.1. Metode Kompresi CALIC............................................................... 27 2.6.2. Metode Kompresi JPEG-LS............................................................ 29 2.6.3. Metode Kompresi CCSDS SZIP ..................................................... 31 2.6.4. Metode Kompresi SFALIC ............................................................. 32 BAB 3 METODE PENELITIAN ..................................................................... 35 3.1. Alur Kerja .............................................................................................. 35 3.2. Skema Reversible Watermarking ............................................................ 36
xiii
3.2.1. Metode Kompresi RCM.................................................................. 36 3.2.1.1. Algoritma Kompresi ............................................................... 40 3.2.1.2. Algoritma Dekompresi ............................................................ 42 3.2.2. Metode Kompresi RLCM ............................................................... 43 3.2.2.1. Algoritma Kompresi ............................................................... 44 3.2.2.2. Algoritma Dekompresi ............................................................ 46 3.2.3. Metode Kompresi Cyclic Reversible Low Contrast Mapping .......... 49 3.2.3.1. Algoritma Enkode ................................................................... 55 3.2.3.2. Algoritma Dekode................................................................... 57 3.3. Skema Average Encoding ....................................................................... 60 3.3.1. Metode 1RLCM-Up coding ............................................................ 63 3.3.1.1. Algoritma Enkode ................................................................... 63 3.3.1.2. Algoritma Dekode................................................................... 68 3.3.2. Pengembangan 1RLCM-Up coding (Ext-1RLCM-Up) ................... 70 3.3.3. Metode 1RLCM-Dw coding ........................................................... 72 3.3.4. Metode 1RLCM-0 coding ............................................................... 77 3.4. Skema Hierarchy Average Encoding ...................................................... 82 3.4.1. Metode Dasar ................................................................................. 82 3.4.2. Metode MAP-HAE ......................................................................... 85 3.5. Citra Uji ................................................................................................. 85 3.6. Metode Pengukuran ................................................................................ 86 BAB 4 HASIL DAN PEMBAHASAN............................................................. 87 4.1. Skema Kompresi Reversible Watermarking ............................................ 87 4.1.1. Pengujian Metode Kompresi Menggunakan RCM .......................... 87 4.1.2. Pengujian Metode RLCM ............................................................... 91 4.1.3. Pengujian Metode CRLCM ............................................................ 94 4.2. Skema Average Encoding (AE) .............................................................. 99 4.2.1. Pengujian Metode 1RLCM-Up ....................................................... 99 4.2.2. Pengujian Metode Ext-1RLCM-Up............................................... 105 4.2.3. Pengujian Metode 1RLCM-Dw .................................................... 109 4.2.4. Pengujian Metode 1RLCM-0 ........................................................ 112 4.3. Skema Hierarchy Average Encoding (HAE) ......................................... 115
xiv
4.3.1. Pengujian Metode Dasar ............................................................... 115 4.3.2. Pengujian MAP-HAE ................................................................... 120 4.4. Implementasi dan Pengembangan ......................................................... 124 BAB 5 KESIMPULAN DAN SARAN .......................................................... 129 5.1. Kesimpulan .......................................................................................... 129 5.2. Saran .................................................................................................... 132 DAFTAR PUSTAKA ...................................................................................... 135 LAMPIRAN .................................................................................................... 141
xv
DAFTAR PUSTAKA Adjeroh, D. and Bhupathiraju, K.V. (2011), “On lossless image compression using the Burrows-Wheeler Transform”, presented at the 2011 18th IEEE International Conference on Image Processing, pp. 1997–2000. Adjeroh, D., Zhang, Y., Mukherjee, A., Powell, M. and Bell, T. (2002), “DNA sequence compression using the Burrows-Wheeler Transform”, Bioinformatics Conference, 2002. Proceedings. IEEE Computer Society, IEEE, pp. 303–313. Ali, M.A., Khan, A., Javed, M.Y. and Khanum, A. (2010), “Lossless image compression using kernel based Global Structure Transform (GST)”, presented at the 2010 6th International Conference on Emerging Technologies (ICET), pp. 170–174. Artusi, A., Mantiuk, R.K., Richter, T., Korshunov, P., Hanhart, P., Ebrahimi, T. and Agostinelli, M. (2016), “JPEG XT: A Compression Standard for HDR and WCG Images [Standards in a Nutshell]”, IEEE Signal Processing Magazine, Vol. 33 No. 2, pp. 118–124. Aruru, S.B., Ranganathan, N. and Namuduri, K.R. (1996), “A VLSI chip for image compression using variable block size segmentation”, presented at the , 1996 IEEE International Conference on Computer Design: VLSI in Computers and Processors, 1996. ICCD ’96. Proceedings, pp. 500–505. Brahimi, Z., Saadi, K.A. and Baraka, N. (1998), “A lossless image compression algorithm using variable block size segmentation”, Vol. 3, presented at the Proceedings of the 24th Annual Conference of the IEEE Industrial Electronics Society, 1998. IECON ’98, pp. 1471–1476 vol.3. Bruckmann, A. and Uhl, A. (2015), “Selective Medical Image Compression using Wavelet Techniques”, CIT. Journal of Computing and Information Technology, Vol. 6 No. 2, pp. 203–213. Burrows, M. and Wheeler, D.J. (1994), “A block-sorting lossless data compression algorithm”, SRC Research Report 124. Chaumont, M. and Puech, W. (2009), “A high capacity reversible watermarking scheme”, IS&T/SPIE Electronic Imaging, International Society for Optics and Photonics, p. 72571H–72571H. Coltuc, D. (2007), “Improved capacity reversible watermarking”, Image Processing, 2007. ICIP 2007. IEEE International Conference on, Vol. 3, IEEE, pp. III–249.
135
Coltuc, D. and Chassery, J.-M. (2006), “High capacity reversible watermarking”, Image Processing, 2006 IEEE International Conference on, IEEE, pp. 2565–2568. Coltuc, D. and Chassery, J.-M. (2007), “Very fast watermarking by reversible contrast mapping”, Signal Processing Letters, IEEE, Vol. 14 No. 4, pp. 255–258. Dang, T.T. and Huynh, C.X. (2015), “Ideal Cross-Point Regions of Prediction Errors from LOCO-I Algorithm Applied to Lossless Image Compression”, in Toi, V.V. and Lien Phuong, T.H. (Eds.), 5th International Conference on Biomedical Engineering in Vietnam, Vol. 46, Springer International Publishing, Cham, pp. 426–429. Ding, J.-J. and Wang, I.-H. (2016), “Improved frequency table adjusting algorithms for context-based adaptive lossless image coding”, IEEE, pp. 1–2. Duda, J. (2009), “Asymmetric numeral systems”, arXiv Preprint arXiv:0902.0271. Dufaux, F., Sullivan, G.J. and Ebrahimi, T. (2009), “The JPEG XR image coding standard [Standards in a Nutshell]”, IEEE Signal Processing Magazine, Vol. 26 No. 6, pp. 195–199, 204–204. Elias, P. (1975), “Universal codeword sets and representations of the integers”, IEEE Transactions on Information Theory, Vol. 21 No. 2, pp. 194–203. Farrugia, R.A. (2010), “A reversible visible watermarking scheme for compressed images”, presented at the Melecon 2010 - 2010 15th IEEE Mediterranean Electrotechnical Conference, pp. 212–217. Hannuksela, M.M., Lainema, J. and Vadakital, V.K.M. (2015), “The High Efficiency Image File Format Standard [Standards in a Nutshell]”, IEEE Signal Processing Magazine, Vol. 32 No. 4, pp. 150–156. Hendra. (2008), Reversible Watermarking Using Integer Transform, Thesis, Universitas Gadjah Mada. Hendra and Kristanta, M.D. (2012), “Penerapan Reversible Contrast Mapping pada Audio Watermarking”, Jurnal Matematika, Statistika Dan Komputasi, Vol. 8 No. 2, pp. 147–154. Howard, P.G. and Vitter, J.S. (1993), “Fast and efficient lossless image compression”, In Proc. 1993 Data Compression Conference, pp. 351–360. Isenburg, M., Lindstrom, P. and Snoeyink, J. (2005), “Lossless compression of predicted floating-point geometry”, Computer-Aided Design, Vol. 37 No. 8, pp. 869–877.
136
Iyer, R., Borse, R., Shah, R. and Chaudhuri, S. (2011), “Estimation of the Embedding Capacity in Pixel-pair based Watermarking Schemes”, arXiv Preprint arXiv:1111.5653. Langdon, G., Gulati, A. and Seiler, E. (1992), “On the JPEG model for lossless image compression”, IEEE Comput. Soc. Press, pp. 172–180. Maity, H.K. and Maity, S.P. (2012), “Joint robust and reversible watermarking for medical images”, Procedia Technology, Vol. 6, pp. 275–282. Masmoudi, A. and Masmoudi, A. (2015), “A new arithmetic coding model for a block-based lossless image compression based on exploiting inter-block correlation”, Signal, Image and Video Processing, Vol. 9 No. 5, pp. 1021– 1027. Mesra, H., Tjandrasa, H. and Fatichah, C. (2014), “A new approach for lossless image compression using Reversible Contrast Mapping (RCM)”, presented at the International Conference of Information, Communication Technology and System (ICTS), 2014, IEEE, pp. 71–76. Mesra, H., Tjandrasa, H. and Fatichah, C. (2016a), “Lossless Image Compression Method Using Reversible Low Constrast Mapping (RLCM)”, JATIT Journal, Vol. 86 No. 1, pp 18-25. Mesra, H., Tjandrasa, H. and Fatichah, C. (2016b), “New Lossless Compression Method Using Cyclic Reversible Low Contrast Mapping (CRLCM)”, International Journal of Electrical and Computer Engineering, Vol. 6 No. 6. Praveena, P. (2014), “Implementation of LOCO-I Lossless Image Compression Algorithm for Deep Space Applications”, International Journal of Reconfigurable and Embedded Systems (IJRES), Vol. 3 No. 1, pp. 25–30. Pu, I.M. (2005), Fundamental Data Compression, Butterworth-Heinemann. Ramaswamy, V.N., Namuduri, K.R. and Ranganathan, N. (1996), “Lossless image coding using wavelets and variable block size segmentation”, presented at the , Proceedings of the IEEE-SP International Symposium on TimeFrequency and Time-Scale Analysis, 1996, pp. 113–116. Rehman, M., Sharif, M. and Raza, M. (2014), “Image compression: A survey”, Research Journal of Applied Sciences, Engineering and Technology, Vol. 7 No. 4, pp. 656–672. Rice, R.F. (1979), “Practical universal noiseless coding”, 23rd Annual Technical Symposium, International Society for Optics and Photonics, pp. 247–267. Rice, R.F., Yeh, P.-S. and Miller, W.H. (1993), “Algorithms for high speed universal noiseless coding”, Proceedings of the AIAA Computing in Aerospace 9 Conference, pp. 19–21. 137
Sahni, S., Vemuri, B.C., Chen, F., Kapoor, C., Leonard, C. and Fitzsimmons, J. (1997), “State of the art lossless image compression algorithms”, IEEE Proceedings of the International Conference on Image Processing, pp. 948– 952. Sahni, S., Vemuri, B.C., Chen, F., Kapoor, C., Leonard, C. and Fitzsimmons, J. (2003), “Lossless Image Compression”, Encyclopedia of Optical Engineering: Las-Pho, Pages 1025-2048, Vol. 2, p. 1177. Salomon, D. (2007), Data Compression: The Complete Reference, Fourth Edition., Springer Science & Business Media. Sayood, K. (2006), Introduction to Data Compression, Three Edition., Morgan Kaufmann. Sayood, K. and Na, S. (1992), “Recursively indexed quantization of memoryless sources”, Information Theory, IEEE Transactions on, Vol. 38 No. 5, pp. 1602–1609. Schäler, M., Schulze, S., Merkel, R., Saake, G. and Dittmann, J. (2011), “Reliable Provenance Information for Multimedia Data Using Invertible Fragile Watermarks”, in Fernandes, A.A.A., Gray, A.J.G. and Belhajjame, K. (Eds.), Advances in Databases, Springer Berlin Heidelberg, pp. 3–17. Shirsat, T.G. and Bairagi, V.K. (2013), “Lossless medical image compression by integer wavelet and predictive coding”, ISRN Biomedical Engineering, Vol. 2013. Sneyers, J. and Wuille, P. (2016), “FLIF: Free lossless image format based on MANIAC compression”, 2016 IEEE International Conference on Image Processing (ICIP), presented at the 2016 IEEE International Conference on Image Processing (ICIP), pp. 66–70. Starosolski, R. (2007), “Simple Fast and Adaptive Lossless Image Compression Algorithm”, Softw: Pract. Exper., Vol. 37, pp. 65–91. Vitter, J.S. (1987), “Design and analysis of dynamic Huffman codes”, Journal of the ACM (JACM), Vol. 34 No. 4, pp. 825–845. Warkar, H.A. and Jain, S.N. (2013), “Lossless Data Hiding For Image Using Reversible Contrast Mapping (RCM)”, International Journal of Electronics, Communication and Soft Computing Science & Engineering (IJECSCSE), pp. 75-78. Weinberger, M.J., Seroussi, G. and Sapiro, G. (1999), “From LOCO-I to the JPEGLS standard”, Vol. 4, presented at the 1999 International Conference on Image Processing, 1999. ICIP 99. Proceedings, pp. 68–72 vol.4. Welch, T.A. (1984), “A technique for high-performance data compression”, Computer, Vol. 17 No. 6, pp. 8–19. 138
Wibawa, H.A. (2008), “Autentikasi Citra Digital dengan Menggunakan Tranformasi Integer”, Disertasi S2 UGM. Wu, X. and Memon, N. (1996), “CALIC-a context based adaptive lossless image codec”, Acoustics, Speech, and Signal Processing, 1996. ICASSP-96. Conference Proceedings., 1996 IEEE International Conference on, Vol. 4, IEEE, pp. 1890–1893. Yang, Y., Sun, X., Yang, H., Li, C.-T. and Xiao, R. (2009), “A contrast-sensitive reversible visible image watermarking technique”, Circuits and Systems for Video Technology, IEEE Transactions on, Vol. 19 No. 5, pp. 656–667. Yeh, P.-S. (2002), “Implementation of CCSDS lossless data compression for space and data archive applications”, Proc. CCSDS Space Operations Conf, pp. 60–69. Žalik, B. and Lukač, N. (2014), “Chain code lossless compression using move-tofront transform and adaptive run-length encoding”, Signal Processing: Image Communication, Vol. 29 No. 1, pp. 96–106.
139
