非對稱數字系統在數位影像上的聯合壓縮和加密應用

The Asymmetric Numeral System and Its Application to Joint Compression and Encryption of Digital Images

謝秉昂(Ping-Ang Hsieh)

指導教授 ： 吳家麟

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2021年)

https://doi.org/10.6342/NTU202102531

摘要

在Entropy壓縮方式中，Huffman Coding及Arithmetic Coding最為經典的演算法。Huffman Coding以編解碼快速著稱，而在壓縮效能上有其侷限之處，反之 Arithmetic Coding 則以壓縮比高為特色，但在編解碼速度上有其限制。Asymmetric Numeral System(以下簡稱ANS)是一個近幾年來非常受到產業界重視的新entropy壓縮方式2007年ANS理論第一次被提出，之後在2015年Facebook 和Apple分別對ANS進行實作ANS之所以受到業界重視正是因為它擷取了Huffman Coding和Arithmetic Coding兩者好處 。

不過將ANS應用在影像壓縮上的工作並不多見，JPEG在2017年提出了一個新的影像壓縮標準模-JPEG XL，此標準即採用ANS作為其Entropy壓縮方式。然而由於ANS的實現牽涉到組合最佳化且方法不唯ㄧ，國內學產兩界幾乎無人注意到此一重要Entropy壓縮方式的進展 。

本論文目的是想深入探討ANS的特性並發展其應用。ANS除了壓縮功能外並具備以下的特性: 特性一 “混亂性”，ANS的混亂性體現在兩個面向上，其一是原始輸入改變一點點，壓縮後的輸入改變很多；反向將壓縮域表示法改動一點點，則解壓縮後的結果也會改變很多。其二則是將一張影像壓縮過後，會產生兩個結果 : 一個正整數(state)以及一段為位元流(bitstream)。 如果把這兩個特性用在藝術收藏影像或醫學影像上，即可同時擁有回溯性，壓縮性及加密性。

關鍵字

影像壓縮 ； 非對稱數字系統 ； 熵編碼 ； 霍夫曼編碼 ； 算術編碼

並列摘要

Among the entropy compression methods, Huffman Coding and Arithmetic Coding are the most classic algorithms. Huffman Coding is known for its fast encoding and decoding but has its limitations in compression performance. On the contrary, Arithmetic Coding is characterized by a high compression ratio but has its limitations in encoding and decoding speed. Asymmetric Numeral System (from now on referred to as ANS) is a new entropy compression method that the industry has highly valued in recent years. The ANS theory was first proposed in 2007, and then Facebook and Apple implemented ANS separately in 2015. ANS is valued by the industry precisely because it captures the benefits of both Huffman Coding and Arithmetic Coding.

However, the application of ANS to image compression is rare. In 2017, JPEG proposed a new image compression standard-JPEG XL, which uses ANS as its entropy compression method. However, due to the fact that the realization of ANS involves combination optimization and the process is not unique, almost no one in the domestic academia and industry has noticed the progress of this vital entropy compression method.

The purpose of this paper is to explore the characteristics of ANS in-depth and develop its applications. In addition to the compression function, ANS has the following characteristics: Characteristic one is "chaos." The chaos of ANS is reflected in two aspects. One is that the original input changes a little bit, and the compressed input changes a lot; the reverse will compress the domain. If the compressed data are changed a little, the result after decompression will also change a lot. The second is that after compressing an image, it will produce two outcomes: a positive integer(state) and a bitstream segment. If these two characteristics are used in art collection images or medical images, you can simultaneously have retrospection, compression, and encryption.

並列關鍵字

Image Compression ； Asymmetric Numeral System ； Entropy Encoding ； Huffman Coding ； Arithmetic Coding

參考文獻

[1] J. Duda, “Asymmetric numeral systems,” 2009, arXiv:0902.0271.

[2] J. Duda,, “Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding,” 2014,arXiv:1311.2540v2.

[3] J. Duda, K. Tahboub, N. J. Gadgil, and E. J. Delp, “The use of asymmetric numeral systems as an accurate replacement for Huffman coding,” in Proceedings of the Picture Coding Symposium, Cairns, Australia, May 2015, pp. 65–69.

[4] H. Fujisaki, “Invariant measures for the subshifts associated with the asymmetric binary systems,” in Proceedings of the International Sym- posium on Information Theory and its Applications, Singapore, October 2018, pp. 675–679.

[5] H. Fujisaki, “On irreducibility of the stream version of the asymmetric binary systems,” in Proceedings of the SITA Symposium, Iwaki, Fukushima, Japan, December 2018, pp. 218–222.