簡易檢索 / 詳目顯示

研究生: 林佳婕
Chia-Chieh Lin
論文名稱: 一種以鄰近資料機率作為適應性算術編碼之彩色影像壓縮演算法
A Lossless Color Image Compression Algorithm with Adaptive Arithmetic Coding Based on Adjacent Data Probability
指導教授: 莊謙本
Chuang, Chien-Pen
學位類別: 碩士
Master
系所名稱: 電機工程學系
Department of Electrical Engineering
論文出版年: 2011
畢業學年度: 99
語文別: 中文
論文頁數: 71
中文關鍵詞: 無損數據壓縮算術編碼鄰近資料機率適應性算術編碼
英文關鍵詞: lossless data compression, arithmetic coding, adjacent data probability, adaptive arithmetic coding
論文種類: 學術論文
相關次數: 點閱:143下載:2
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 近年來影像壓縮技術不斷進步,尤其在有損數據壓縮,如JPEG、JPEG 2000都已經發展得相當成熟,且已廣泛的被使用。但壓縮技術在無損數據壓縮方面,礙於無損數據壓縮對於原檔案的資料,不能有任何遺失,頇完整保留,因此壓縮效果較無法明顯的提升。雖有許多無損數據的編碼被發展出來,例如使用熵編碼(Entropy Coding)的算術編碼(Arithmetic Coding)對雜亂資料進行編碼時,能保有良好的壓縮效果,但其無法對不同類型影像有相同的壓縮效果。因此本論文提出一種簡易且能達到泛用的演算法,希望對各類型的影像都有相近的壓縮效果。本演算法分為兩部分,首先以簡單的蛇行掃描(Snake Scan)將資料做相減,以去除像素間的相關性,再開始對資料編碼。接著以適應性算術編碼(Adaptive Arithmetic Coding)中機率模型的建置,不使用整張影像的資料,而是採用待編碼符號鄰近的資料來建立機率模型。以24張Kodak所提供的彩色影像作壓縮的實驗結果,發現本演算法的效率比原適應性算術編碼有效,因此本法具有進步性。

    In the last decade, many advances have been made in the area of image compression. Especially on lost data compression, such as JPEG and JPEG 2000 have been developed quite mature and widely used. However, most lossless data compressions have low Compression Rate because it has to reserve all information. Many data codes had been proposed for lossless data compression. Such as Arithmetic Coding is using Entropy Coding to compress the clutter data with good efficiency. But it cannot compress all kinds of images with the same high Compression Rate. In this paper, we propose a simple lossless algorithm which can compress all types of images with the same high Compression Rate. The algorithm consists of two phases. First, it removes the correlation between pixels with Snake Scan to get residual of data. And then encode the residual of data with an Adaptive Arithmetic Coding. This Adaptive Arithmetic Coding only uses adjacent data to build the probability model. 24 color images provided by Kodak Company were used to test compression rate of this proposed algorithm. The results show the efficiency of this proposed algorithm is better than original Adaptive Arithmetic Coding method.

    摘 要 i Abstract ii 誌 謝 iii 目 錄 iv 圖 目 錄 vi 表 目 錄 viii 第一章 緒論 1 1.1. 研究背景 1 1.2. 研究動機 3 1.3. 論文架構 4 第二章 無損數據壓縮編碼之相關文獻探討 5 2.1. 無損數據壓縮相關編碼理論 5 2.1.1. Huffman Coding霍夫曼編碼 5 2.1.2. LZW 編碼 7 2.1.3. Run Length Coding跑長碼 8 2.1.4. Arithmetic Coding算術編碼 9 2.2. 算術編碼相關文獻探討 . 11 第三章 鄰近資料機率於適應性算術編碼之影像壓縮方式 13 3.1. 鄰近資料彼此相減(Adjacent Difference) 17 3.2. 建立差值位元層模型(Building Difference Bit-plane Model) 20 3.3. 鄰近資料機率之適應性算術編碼(ADAAC) 23 3.4. ADAAC之解壓縮(Decompression of ADAAC) 29 第四章 實驗結果與分析 34 4.1. 實驗說明 36 4.2. RGB分開實驗結果比較 38 4.2.1. RGB分開8個位元層 38 4.2.2. RGB分開4個位元層 41 4.2.3. RGB分開2個位元層 44 4.2.4. RGB分開1個位元層 47 4.3. RGB合併實驗結果比較 50 4.3.1. RGB合併8個位元層 50 4.3.2. RGB合併4個位元層 53 4.4. 各組實驗比較 56 第五章 結論與未來工作 62 5.1. 結論 62 5.2. 未來工作 63 參考文獻 65 自 傳 70 學術成就 71

    [1] K. R. Rao and J. J. Hwang, Techniques & Standards for Image and Video & Audio Coding, USA: Prentice Hall PTR, 1996.
    [2] Scott E Umbaugh, Compression Vision and Image Processing: a practical approach using CVIP tools, USA: Prentice Hall PTR, 1998.
    [3] A. Neubauer, J Freudenberger and V. Kuhn, Coding theory: Algorithm, Architectures and Applications, New York: Wiley, 2007.
    [4] E. Reinhard, G. Ward, S. Pattanaik, and P. Debevec, High Dynamic Range Imaging: Acquisition, Display, and Image-Based Lighting, California: Morgan Kaufmann, 2005.
    [5] C. G. Rafael and E. W. Richard, Digital Image Processing, 2nd ed., New Jersey U.S.A.: Prentice Hall, 2002.
    [6] K. Sayood, Introduction to Data Compression, 3rd Edition, California: Morgan Kaufmann, 2005.
    [7] I. E. Richardso, The H.264 Advanced Video Compression Standard, 2nd ed., New York: Wiley, 2010.
    [8] 施威銘,PC影像處理技術(二) 圖檔壓縮續篇,旗標,1994。
    [9] 李明昌,影像壓縮技術與應用,全華,1995。
    [10] 陳孝同,張真誠,黃國峰,數位影像處理技術Digital Image Processing,旗標,2003。
    [11] 任新明,影像檔案格式剖析,維科,1991。
    [12] T. A. Welch, “A technique for high performance data compression,” IEEE Computer Society, vol. 17, no. 6, pp. 8-19, June 1984.
    [13] J. Rissanen and G. G. Langdon, ”Arithmetic coding,” IBM Journal of Research and Development, vol. 23, no. 2, pp. 149-162, March 1979.
    [14] I. H. Witten, R. M. Neal, and J. G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, vol. 30, no. 6, pp. 520-540, June 1987.
    [15] C. S. Lee and H. W. Park, “Multisymbol data compression using a binary arithmetic coder”, Institution of Engineering and Technology, Electronic letters, vol. 38, no.3, Jan. 2002.
    [16] P. G. Howard and J. S. Vitter, “Arithmetic coding for data compression,” Proceeding of the IEEE, vol. 82, no. 6, pp. 857-865, June 1994.
    [17] W. D. Withers, “A rapid probability estimator and binary arithmetic coder,” IEEE Trans. Information Theory. vol. 47, no. 4, pp. 1533-1537, May 2001.
    [18] D. Marpe, H. Schwarz, and T. Wiegand, “Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard,” IEEE Trans. Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 620-636, July 2003.
    [19] M. Grangetto, E. Magli, and G. Olmo, “Distributed arithmetic coding,” IEEE Communication Letters, vol. 11, no. 11, pp. 883-885, Nov. 2007.
    [20] L. Huynh and A. Moffat, “ A probability-ratio approach to approximate binary arithmetic coding,” IEEE Trans. Information Theory, vol. 43, no. 5, pp. 1658-1662. Sep. 1997.
    [21] N. V. Boulgouris, D. Tzovaras, and M. G. Strintzis, “Lossless image compression based on optimal prediction, adaptive lifting, and conditional arithmetic coding,” IEEE Trans. Image Processing, vol. 10, no. 1, pp. 1-14, Jan. 2011.
    [22] W. B. Pennebaker, J. L. Mitchell, G. G. Langdon, and R. B. Arps, “An overview of the basic principles of the Q-coder adaptive binary arithmetic coder,” IBM Journal of Research and Development, vol. 32, no. 6, pp. 717-726, Nov. 1988.
    [23] 吳和弟,靜態影像壓縮介紹,計算中心通訊,vol. 11:10,pp. 89-92,May 1995。
    [24] D. Huffman, “A method for the construction of minimum-redundancy codes,” in Proc. Institute of Radio Engineers, Sep. 1952, vol. 40, no. 9, pp.1098-1102.
    [25] D. Xu and Y. Cao, “Application research of arithmetic coding,” in Proc. International Conference on Information Science and Engineering, Hangzhou, China, Dec. 2010, pp. 1025-1027.
    [26] K. S. You, D. S. Han, E. S. Jang, S. Y. Jang, S. K. Lee, and H. S. Kwak, “Ranked image generation for arithmetic coding in indexed color image,” in Proc. HEALTHCOM Workshop on Enterprise Networking and Computing in Healthcare Industry, Korea, June 2005, pp. 299-302.
    [27] F. Ling and W. Li, “Dimensional adaptive arithmetic coding for image compression,” in Proc. IEEE International Symposium on Circuits and Systems, Monterey , California, June 1988, vol. 4, pp. 13-16.
    [28] K. Andra, T. Acharya, and C. Chakrabarti, “A multi-bit binary arithmetic coding technique,” in Proc. International Conference on Image Processing, British Columbia , Canada, Sep. 2000, vol. 1, pp. 928-931.
    [29] H. Ye, G. Deng, and J. C. Devlin, “A lossless image compression system using a binary arithmetic coder,” in Proc. International Conference on Signal Processing, Beijing, China, Oct. 1998, pp. 819-822.
    [30] C. Boncelet, “Simple, high performance lossless image compression,” in Proc. International Conference on Image Processing, Thessaloniki, Greece, Oct. 2001, vol. 3, pp. 498-501.
    [31] H. J. Kim, “A new lossless data compression method,” in Proc. IEEE International Conference on Multimedia and Expo, New York, 2009, pp.1740-1743.
    [32] M. Grangetto, E. Magli, and G. Olmo, “Decoder-driven adaptive distributed arithmetic coding,” in Proc. International Conference on Image Procession, California, U.S.A., Oct. 2008, pp. 1128-1131.
    [33] J. Wu, M. Wang, J. Jeong, and L. Jiao, “Adaptive-distributed arithmetic coding for lossless compression,” in Proc. International Conference on Network Infrastructure and Digital Content, Beijing, China, Sep. 2010, pp. 541-545.
    [34] C. Xiong, J. Hou, Z. Gao, and X. He, “Efficient fast algorithm for MQ arithmetic coder,” in Proc. IEEE International Conference on Multimedia and Expo, Beijing, China, July 2007, pp. 759-762.
    [35] R. Apparaju and S. Agarwal, “An arithmetic coding scheme by converting the multisymbol alphabet to m-ary alphabet,” in Proc. International Conference on Computational Intelligence and Multimedia Applications, India, Dec. 2007, vol. 4, pp. 142-146.
    [36] N. V. Boulgouris, A. Leontaris, and M. G. Strintzis, “Wavelet compression of 3D medical images using conditional arithmetic coding,”, in Proc. IEEE International Symposium on Circuits and Systems, Geneva, Switzerland, May 2000, vol. 4, pp. 557-560.
    [37] S. K. Pattanaik, K. K. Mahapatra, and G. Panda, “A novel lossless image compression algorithm using arithmetic modulo operation,” IEEE International Conference on Cybernetics and Intelligent Systems, Bangkok, Thailand, June 2006, pp.1-5.
    [38] M. R. Islam, A. A. Baki, and M. S. H. Palash, “A new image compression scheme using repeat reduction and arithmetic coding,” in Proc. International Conference on Computers and Information Technology, Dhaka, Bangladesh, Dec. 2009, pp. 209-214.
    [39] D. Chikouche, R. Benzid, and M. Bentoumi, “Application of the DCT and arithmetic coding to medical image compression,” International Conference on Information and Communication Technologies: from Theory to Applications, Syria, April 2008, pp. 1-5.
    [40] C. P. Chuang and C. C. Lin, “Adaptive encoding on bit-plane based lossless color image compression,” International Conference on Signal Acquisition and Processing, Singapore, Feb. 2011, pp. V2 90-94.
    [41] JPEG and JPEG 2000. [online] Available at http://www.jpeg.org/.
    [42] Kodak Lossless True Color Image Suit. [online] Available at http://r0k.us/graphics/kodak/http://r0k.us/graphics/kodak/.
    [43] 故宮精緻文物數位博物館知識庫建置計畫。 [online] Available at http://tech2.npm.gov.tw/da/.

    下載圖示
    QR CODE