臺灣博碩士論文加值系統

隨著螢幕的解析度日益增大，導致傳送螢幕資料所需的頻寬需求增加，這不僅需要更多的硬體資源，亦增加耗電量。因此在不產生可察覺影像品質損失的前提下，利用影像壓縮技術來減緩頻寬的需求是解決問題的關鍵。與傳統高複雜度但高效能的壓縮方法如H.264相比，這類的壓縮強調低複雜度但且即時的運算，並且其功能通常嵌入在特定的系統中，又稱之為嵌入式壓縮。為了確保頻寬的條件，本論文著墨於固定壓縮倍率之嵌入式壓縮技術。所開發的嵌入式壓縮系統提供多種演算法平行運算，再從中選出表現最佳的結果來編碼。每個演算法在設計上係針對特殊影像屬性，處理各種紋理類型來達到較佳的壓縮品質。該系統支援Android 5.0提出的「區塊更新」功能，能大幅減少畫面更新時所需傳送的影像資料。因此每個區塊必須進行獨立的壓縮編碼，而無法利用鄰近區塊的資訊。這對於畫素預測準確度與編碼效能是一很大的挑戰。
為了降低所需緩衝記憶體的容量，本系統的壓縮運算是基於2×4大小的區塊來進行，並採用整數的色彩轉換機制作前處理。而在壓縮演算法上，總共使用了包括共同值萃取編碼、特徵值萃取編碼、內插編碼、方塊編碼和向量量化編碼等方法來進行壓縮。其中共同值萃取編碼、特徵值萃取編碼與內插編碼為本文提出之獨特壓縮編碼方法。而方塊編碼是由現有的方塊編碼演算法修改而來。這些演算法都是基於相鄰畫素在空間上的相關特性來進行編碼。向量量化編碼則是將2×4區塊視為一維度為8的向量，並運用預先訓練好之向量碼簿來進行編碼，其中向量碼簿的訓練是基於數張自然影像搭配kmeans方式產生。此外，包括內插編碼、方塊編碼與向量量化編碼，其預測殘值還會利用離散整數轉換，搭配對係數的量化與編碼，進一步增進畫質。綜合各種編碼方式，本論文提出的系統可提供固定三倍壓縮倍率的編碼演算法。
效能表現的部分是以各類型的影像畫面來評估，類型包含: 使用者介面(UI)、工程影像、純文字畫面、遊戲畫面、影片與自然畫面，其中亦包含不同解析度大小、不同畫面複雜度、不同對比度之影像。PSNR值的計算有將各顏色成份分開計算的方式與將整張畫面各顏色成份合起來一併算兩種方式，而將PSNR的表現結果與JPEG比較，實驗結果顯示本論文提出的系統於人工影像中可勝過JPEG的表現，而JPEG於自然影像與複雜影像中有較佳的表現，JPEG的運算是基於8×8的區塊，其大小是本論文提出的系統的8倍大，於複雜的畫面可有較佳的彈性，但其硬體複雜度較大，不可視為嵌入式壓縮，且亦無法達到固定壓縮倍率的壓縮。經主觀測試，本論文提出的系統的壓縮結果失真幅度幾乎無法直接察覺。

The display resolutions of 3C products are growing larger and larger nowadays. This results in a huge increase on the demand of the display data transmission bandwidth. It not only requires more hardware resource, but also increases power consumption significantly. As a result, approaches to alleviate the display transmission bandwidth without suffering perceivable image quality loss are the key to tackle the problems. Compared with existing highly compression efficient yet computationally complicated compression schemes such as H.264, the addressed compression schemes focus on low computing complexity and real time processing. Since these compression schemes are often considered embedded functions tailored to specific systems, they are also termed as embedded compression.
In this thesis, we investigate on embedded video compression with a constant compression rate to assure the compliance with data bandwidth constraints. The proposed embedded compression scheme features an ensemble of compression techniques with each targeting different offset of images with a certain texture property for efficient compression. All compression techniques are evaluated concurrently and the best of all is selected. The proposed system also supports the partial update feature adopted in Android 5.0, and can largely reduce the data transmission bandwidth if only a small portion of the image is updated. To implement this feature, the compression is performed on a per block basis and all blocks should be compressed independently without using information from the adjacent blocks. This, however, poses significant challenges to the prediction accuracy of pixel values and the flexibility of bit allocation in coding, both are crucial to the compression efficiency.
To lower the line buffer storage requirement, an image block of size 2×4 pixels is chosen as the basic compression unit. An integral color space transform, from RGB to YCgCo, is first applied to de-correlate the color components. After this pre-processing step, each color component is processed independently. Compression techniques employed in the proposed system include common value extraction coding, distinct value coding, interpolation-based coding, modified block truncation coding, and vector quantization coding. Among them, common value extraction coding, distinct value coding, and interpolation-based coding are uniquely developed for the proposed system. Modified block truncation coding is derived from an existing one but adds an integer DCT based refinement process. All these techniques aim at exploiting the data correlation in the spatial domain to facilitate efficient prediction and coding. Vector quantization treats the 2×4 block as a vector consisting of 8 tuples and codes the block in an entirety through finding a best match in a pre-defined code book. To enhance the compression efficiency, refinement processes performed in the frequency domain are further applied to the coding results of interpolation-based coding, modified block truncation coding and vector quantization. The compression ratio of the proposed system is fixed while best PSNR values are sought afterward. The compression ratio of the luminance is 2 and those of the two color components are 4. This leads to an overall 3 times constant rate compression. The compression efficiency of the proposed system is evaluated based on a set of test images. These images are captured from various scenarios such as user interface, engineering patterns, text, gaming, video playback and nature scene. They also feature different resolutions, texture complexities and contrasts. The PSNR values of perspective color components as well as the entire image are calculated and compared to the results achieved by the JPEG standard, which uses a 8×8 block as the basic coding unit. The results show that the proposed scheme outperforms JPEG mostly in artificial images containing texts or engineering patterns. JPEG achieves better results in the category of nature scenes or more complicated images. This is mainly attributed to an inherent advantage of a larger coding block adopted in JPEG. However, JPEG, due to its complexity, is not considered an embedded compression scheme, nor can it support a constant rate compression. Subjective test based on visual inspections is also conducted and the distortions caused by the proposed scheme are visually barely noticeable.

摘要 i
Abstract ii
Contents v
List of Figures vii
List of Tables viii
Chapter 1 Introduction 1
1.1 Research Background 1
1.2 Lossless vs Lossy Compression 2
1.3 Constant Rate Embedded Compression 3
1.4 Proposed Research 4
1.5 Organization of the Thesis 6
Chapter 2 Basics of Image Compression 7
2.1. Lossless Image Compression 8
2.1.1. JPEG-LS 8
2.1.2. CALIC 11
2.2. Lossy Image Compression 14
2.2.1. Joint Photographic Experts Group (JPEG) 14
2.2.2. Block Truncation Coding 18
2.3. Summary of Image Compression Schemes 19
Chapter 3 Current Developments of Embedded Compression 21
3.1 VESA DSC Standard 21
3.2 Discussion on Coding Unit Size 25
Chapter 4 Proposed Image Compression Scheme 28
4.1 Overview of the Proposed System 28
4.2 Color Space Transform 29
4.3 Four Distinct Values Coding Scheme 31
4.4 Interpolation-Based Coding Scheme 33
4.4.1 Down Sampling and Interpolation Mode 34
4.4.2 Reference Plus Interpolation Mode 37
4.4.3 Mode Selection 38
4.5 Vector Quantization Coding Scheme 39
4.6 Common Value Extraction Coding Scheme 45
4.7 Block Truncation Coding Plus Integer DCT Scheme 47
4.8 Mode Decision 49
Chapter 5 Simulation Result and Discussion 50
5.1 PSNR Benchmark 50
5.2 Simulation Result 51
5.3 Performance Comparison 69
Chapter 6 Conclusion and Future Work 72
Reference 73

[1]“Information technology -- Lossless and near-lossless compression of continuous-tone still images: Baseline” ISO/IEC 14495-1:1999
http://www.iso.org/iso/catalogue_detail.htm?csnumber=22397
[2]Develop Apps | Android Develpers
https://developer.android.com/develop/index.html
[3]M. J. Weinberger, G. Seroussi, and G. Sapiro, “The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS”, IEEE Trans. Image Process., vol. 9, no. 8, pp 1309-1324, Aug. 2000
[4]X. Wu and N. D. Memon, “Context-Based, Adaptive, Lossless Image Coding”, IEEE Trans. Commun., vol. 45,pp. 437-444 Apr 1997
[5]T.-H. Tsai , Y.-H. Lee, and Y.-Y. Lee “Design and Analysis of High-Throughput Lossless Image Compression Engine Using VLSI-Oriented FELICS Algorithm”, IEEE Trans. on VLSI Syst., vol. 18, no. 1, pp. 39-52, Jan. 2010
[6]A. Skodras, C. Christopoulos, and T Ebrahimi, “The JPEG 2000 still image compression standard,” IEEE Signal Process. Mag., bol 18, no.5, pp 36-58, Sept 2001.
[7]G. K. Wallace, “The JPEG still picture compression standard”, IEEE Trans. on Consumer Electronics, vol. 38, no 1, pp 18-34, Feb. 1992
[8]E. Delp, O. Mitchell, “Image Compression Using Block Truncation Coding”, IEEE Trans. on Comm., vol. 27, no 9, pp 1335-1342, Sep. 1979
[9]ISO/IEC 29170-2:2015, Information technology -- Advanced image coding and evaluation -- Part 2: Evaluation procedure for nearly lossless coding
http://www.iso.org/iso/home/store/catalogue_tc/catalogue_detail.htm?csnumber=66094
[10]VESA Display Stream Compression white paper http://www.vesa.org/wp-content/uploads/2014/04/VESA_DSC-ETP200.pdf
[11]D. Halverson, N. Griswold, G. Wise “A generalized block truncation coding algorithm for image compression”, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 32, no 3, pp 664-668, Jun. 1984
[12]S3 Incorporated, “System and method for fixed-rate block-based image compression with inferred pixel values”, Patent number: US5956431 A
[13]K. Masselos, P. Merakos, T. Stouraitis, and C.E. Goutis, “Novel codebook design techniques for vector quantization image compression”, IEEE International Symposium on Circuits and Systems, Jun. 1997
[14]Han Oh, Ali Bilgin, and Michael W. Marcellin, “Visually Lossless Encoding for JPEG2000”, IEEE Signal Processing Society, pp 189 – 201, Aug. 2012
[15]Yin-Tsung Hwang, Cheng-Chen Lin, and Ming-Wei Liu “ Design and Implementation of a Low Complexity Lossless Video Codec", IEEE APCCAS 2010, Dec. 2010
[16]M. J. Ryan and J. F. Arnold, “The lossless compression of AVIRIS images by vector quantization”, IEEE Trans. Geosci. Remote Sens., vol. 35, no. 3, pp. 546–550, May 1997
[17]J. Mielikäinen and P. Toivanen, “Improved vector quantization for lossless compression of AVIRIS Images”, in Proc. Eur. Signal Process. Conf., pp. 495–497, Sep. 2002
[18]B. Penna, T. Tillo, E. Magli, and G. Olmo, “Progressive 3-D coding of hyperspectral images based on JPEG 2000,” IEEE Geosci. Remote Sens. Lett., vol. 3, no. 1, pp. 125–129, Jan. 2006
[19]Aijun Sang, Lin Cong, and Ping Fu, “Multi-dimensional vector discrete cosine transform coefficients matrix scan mode for image compression”, Future Computer and Communication (ICFCC), 2010., May 2010
[20]F. Rizzo, B. Carpentieri, G. Motta and J. A. Storer, “Low-complexity lossless compression of hyperspectral imagery via linear prediction”, IEEE Signal Process. Lett., vol. 12, no. 2, pp. 138-141, Feb. 2005
[21]E. Magli, “Multiband Lossless compression of hyperspectral images,” IEEE Trans. Geosci. Remote Sens., vol. 47, no. 4, pp. 1168–1178, Apr. 2009
[22]X. Wu and N. D. Memon,”Context-based lossless interband compression-extending CALIC,” IEEE Trans. Image Process., vol. 9, no. 6, pp. 994-1001, Jun. 2000