在這資料爆炸的時代，如何有效地節省影像儲存空間及傳輸頻寬是非常重要的，因此影像壓縮是必須的。區塊截短編碼(Block Truncation Coding, BTC)是一種簡單且有效的壓縮技術，但BTC技術所需的位元率(bit rate)相較於JPEG或JPEG2000高。至今有很多關於如何降低BTC位元率的演算法被提出，但這些演算法在提高壓縮率同時，也會產生一些image artifact，甚至犧牲了BTC低複雜度的特性。因此，一個低複雜度且能降低image artifact，提供一個良好的影像品質的區塊截短編碼是不可或缺的。
在本論文中，我們提出一個基於半色調式區塊截短編碼技術的影像壓縮演算法。我們利用四元樹分割(quadtree decomposition)的概念，將影像根據細節度多寡切割成變動大小的影像區塊，並且搭配誤差擴散的技術，改善區塊跟區塊間的差異性，以降低區塊效應(blocking effect)的發生。除此之外，我們採用了一個適應性的機制，根據每張影像的特性來決定四元樹分割所需的門檻值，以讓每張影像都能得到最佳的壓縮效果。

In the age of information explosion, reducing the storage and bandwidth needed to store and transmit the images efficiently has become one important issue. Hence, methods to compress the image data are essential nowadays. Block Truncation Coding (BTC) is a simple and efficient technique. However the bit rate of the original BTC algorithm is relatively high compared to modern compression techniques such as JPEG or JPEG2000. Some investigations have been proposed to further reduce the bit rate so far. Nevertheless, these algorithms produce some annoying image artifacts caused by the low bit rate configuration and some even sacrifice the low-complexity characteristic of BTC. Hence, a low-complexity BTC technique that can reduce the perceptual artifacts effectively and provide good image quality at the low bit rate is crucial.
Two image compression algorithms are proposed on the basis of halftoning-based BTC in this thesis. We apply the concept of quadtree decomposition to the proposed methods. The non-overlapping blocks of an image are segmented into smaller blocks based on the texture of the image. To reduce the blocking effect, we utilize the error diffusion technique which diffuses the quantized error into neighboring unprocessed pixels to maintain the local gray level. An adaptive scheme which is used to decide the thresholds of the partitioning process according to the value of spatial frequency measurement (SFM) is adopted to achieve the better image compression ratio.

[1] M. Analoui and J. P. Allebach, “Model-based halftoning using direct binary search,” pp. 96-108, 1992.
[2] F. Belgassem, E. Rhoma, and A. Dziech, “Performance evaluation of interpolative BTC image coding algorithms,” in International Conference on Signals and Electronic Systems (ICSES), pp. 189-192, 2008.
[3] Z. Bing and Y. Neuvo, “Interpolative BTC image coding with vector quantization,” IEEE Transactions on Communications, vol. 41, pp. 1436-1438, 1993.
[4] E. J. Delp and O. R. Mitchell, “Image Compression Using Block Truncation Coding,” IEEE Transactions on Communications, vol. 27, pp. 1335-1342, 1979.
[5] A. M. Eskicioglu and P. S. Fisher, “Image quality measures and their performance,” IEEE Transactions on Communications, vol. 43, pp. 2959-2965, 1995.
[6] R. Floyd and L. Steinberg, An adaptive algorithm for spatial gray scale, 1975.
[7] J. M. Guo, “Improved block truncation coding using modified error diffusion,” Electronics Letters, vol. 44, p. 462, 2008.
[8] J. M. Guo and Y. F. Liu, “Improved Block Truncation Coding using Optimized Dot Diffusion,” in Proceedings of 2010 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 2634-2637, 2010.
[9] J. M. Guo and W. Ming-Feng, “Improved Block Truncation Coding Based on the Void-and-Cluster Dithering Approach,” IEEE Transactions on Image Processing, vol. 18, pp. 211-213, 2009.
[10] J. M. Guo and C. C. Su, “Improved Block Truncation Coding Using Extreme Mean Value Scaling and Block-Based High Speed Direct Binary Search,” IEEE Signal Processing Letters, vol. 18, pp. 694-697, 2011.
[11] Y.-C. Hu, “Low-complexity and low-bit-rate image compression scheme based on absolute moment block truncation coding,” Optical Engineering, vol. 42, p. 1964, 2003.
[12] J. F. Jarvis, C. N. Judice, and W. H. Ninke, “A survey of techniques for the display of continuous tone pictures on bilevel displays,” Computer Graphics and Image Processing, vol. 5, pp. 13-40, 1976.
[13] A. Kumar and P. Singh, “Enhanced Block Truncation Coding for Gray Scale Image,” Int. J. Comput. Techn. Appl, vol. 2, pp. 525-530, 2011.
[14] M. Lema and O. R. Mitchell, “Absolute Moment Block Truncation Coding and Its Application to Color Images,” IEEE Transactions on Communications, vol. 32, pp. 1148-1157, 1984.
[15] P. Stucki, A Multiple-error Correction Computation Algorithm for Bilevel Image Hardcopy Reproduction. R. Oldenbourg, 1982.
[16] V. Udpikar and J. Raina, “BTC Image Coding Using Vector Quantization,” IEEE Transactions on Communications, vol. 35, pp. 352-356, 1987.
[17] R. Ulichney, Digital halftoning. MIT Press, 1987.
[18] A. Weitzman and H. B. Mitchell, “An interblock BTC-VQ image coder,” in Proceedings of 11th IAPR International Conference on Pattern Recognition, III, Conference The Hague, Netherlands, pp. 426-429, 1992.
[19] Wikipedia. Just noticeable difference [Online]. Available: http://en.wikipedia.org/wiki/Just-noticeable_difference
[20] Y. Wu and D. C. Coll, “BTC-VQ-DCT hybrid coding of digital images,” IEEE Transactions on Communications, vol. 39, pp. 1283-1287, 1991.
[21] B. Zeng, “Two interpolative BTC image coding schemes,” Electronics Letters, vol. 27, pp. 1126-1128, 1991.